Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/RegAllocFast.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- RegAllocFast.cpp - A fast register allocator for debug code --------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
/// \file This register allocator allocates registers to a basic block at a
10
/// time, attempting to keep values in registers and reusing registers as
11
/// appropriate.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "llvm/ADT/ArrayRef.h"
16
#include "llvm/ADT/DenseMap.h"
17
#include "llvm/ADT/IndexedMap.h"
18
#include "llvm/ADT/SmallSet.h"
19
#include "llvm/ADT/SmallVector.h"
20
#include "llvm/ADT/SparseSet.h"
21
#include "llvm/ADT/Statistic.h"
22
#include "llvm/CodeGen/MachineBasicBlock.h"
23
#include "llvm/CodeGen/MachineFrameInfo.h"
24
#include "llvm/CodeGen/MachineFunction.h"
25
#include "llvm/CodeGen/MachineFunctionPass.h"
26
#include "llvm/CodeGen/MachineInstr.h"
27
#include "llvm/CodeGen/MachineInstrBuilder.h"
28
#include "llvm/CodeGen/MachineOperand.h"
29
#include "llvm/CodeGen/MachineRegisterInfo.h"
30
#include "llvm/CodeGen/RegAllocRegistry.h"
31
#include "llvm/CodeGen/RegisterClassInfo.h"
32
#include "llvm/CodeGen/TargetInstrInfo.h"
33
#include "llvm/CodeGen/TargetOpcodes.h"
34
#include "llvm/CodeGen/TargetRegisterInfo.h"
35
#include "llvm/CodeGen/TargetSubtargetInfo.h"
36
#include "llvm/IR/DebugLoc.h"
37
#include "llvm/IR/Metadata.h"
38
#include "llvm/MC/MCInstrDesc.h"
39
#include "llvm/MC/MCRegisterInfo.h"
40
#include "llvm/Pass.h"
41
#include "llvm/Support/Casting.h"
42
#include "llvm/Support/Compiler.h"
43
#include "llvm/Support/Debug.h"
44
#include "llvm/Support/ErrorHandling.h"
45
#include "llvm/Support/raw_ostream.h"
46
#include <cassert>
47
#include <tuple>
48
#include <vector>
49
50
using namespace llvm;
51
52
#define DEBUG_TYPE "regalloc"
53
54
STATISTIC(NumStores, "Number of stores added");
55
STATISTIC(NumLoads , "Number of loads added");
56
STATISTIC(NumCoalesced, "Number of copies coalesced");
57
58
static RegisterRegAlloc
59
  fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
60
61
namespace {
62
63
  class RegAllocFast : public MachineFunctionPass {
64
  public:
65
    static char ID;
66
67
1.83k
    RegAllocFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1) {}
68
69
  private:
70
    MachineFrameInfo *MFI;
71
    MachineRegisterInfo *MRI;
72
    const TargetRegisterInfo *TRI;
73
    const TargetInstrInfo *TII;
74
    RegisterClassInfo RegClassInfo;
75
76
    /// Basic block currently being allocated.
77
    MachineBasicBlock *MBB;
78
79
    /// Maps virtual regs to the frame index where these values are spilled.
80
    IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
81
82
    /// Everything we know about a live virtual register.
83
    struct LiveReg {
84
      MachineInstr *LastUse = nullptr; ///< Last instr to use reg.
85
      unsigned VirtReg;                ///< Virtual register number.
86
      MCPhysReg PhysReg = 0;           ///< Currently held here.
87
      unsigned short LastOpNum = 0;    ///< OpNum on LastUse.
88
      bool Dirty = false;              ///< Register needs spill.
89
90
123k
      explicit LiveReg(unsigned VirtReg) : VirtReg(VirtReg) {}
91
92
453k
      unsigned getSparseSetIndex() const {
93
453k
        return TargetRegisterInfo::virtReg2Index(VirtReg);
94
453k
      }
95
    };
96
97
    using LiveRegMap = SparseSet<LiveReg>;
98
    /// This map contains entries for each virtual register that is currently
99
    /// available in a physical register.
100
    LiveRegMap LiveVirtRegs;
101
102
    DenseMap<unsigned, SmallVector<MachineInstr *, 2>> LiveDbgValueMap;
103
104
    /// Has a bit set for every virtual register for which it was determined
105
    /// that it is alive across blocks.
106
    BitVector MayLiveAcrossBlocks;
107
108
    /// State of a physical register.
109
    enum RegState {
110
      /// A disabled register is not available for allocation, but an alias may
111
      /// be in use. A register can only be moved out of the disabled state if
112
      /// all aliases are disabled.
113
      regDisabled,
114
115
      /// A free register is not currently in use and can be allocated
116
      /// immediately without checking aliases.
117
      regFree,
118
119
      /// A reserved register has been assigned explicitly (e.g., setting up a
120
      /// call parameter), and it remains reserved until it is used.
121
      regReserved
122
123
      /// A register state may also be a virtual register number, indication
124
      /// that the physical register is currently allocated to a virtual
125
      /// register. In that case, LiveVirtRegs contains the inverse mapping.
126
    };
127
128
    /// Maps each physical register to a RegState enum or a virtual register.
129
    std::vector<unsigned> PhysRegState;
130
131
    SmallVector<unsigned, 16> VirtDead;
132
    SmallVector<MachineInstr *, 32> Coalesced;
133
134
    using RegUnitSet = SparseSet<uint16_t, identity<uint16_t>>;
135
    /// Set of register units that are used in the current instruction, and so
136
    /// cannot be allocated.
137
    RegUnitSet UsedInInstr;
138
139
    void setPhysRegState(MCPhysReg PhysReg, unsigned NewState);
140
141
    /// Mark a physreg as used in this instruction.
142
198k
    void markRegUsedInInstr(MCPhysReg PhysReg) {
143
534k
      for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); 
++Units335k
)
144
335k
        UsedInInstr.insert(*Units);
145
198k
    }
146
147
    /// Check if a physreg or any of its aliases are used in this instruction.
148
142k
    bool isRegUsedInInstr(MCPhysReg PhysReg) const {
149
348k
      for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); 
++Units206k
)
150
207k
        if (UsedInInstr.count(*Units))
151
1.86k
          return true;
152
142k
      
return false140k
;
153
142k
    }
154
155
    enum : unsigned {
156
      spillClean = 50,
157
      spillDirty = 100,
158
      spillPrefBonus = 20,
159
      spillImpossible = ~0u
160
    };
161
162
  public:
163
9.85k
    StringRef getPassName() const override { return "Fast Register Allocator"; }
164
165
1.77k
    void getAnalysisUsage(AnalysisUsage &AU) const override {
166
1.77k
      AU.setPreservesCFG();
167
1.77k
      MachineFunctionPass::getAnalysisUsage(AU);
168
1.77k
    }
169
170
1.77k
    MachineFunctionProperties getRequiredProperties() const override {
171
1.77k
      return MachineFunctionProperties().set(
172
1.77k
          MachineFunctionProperties::Property::NoPHIs);
173
1.77k
    }
174
175
1.77k
    MachineFunctionProperties getSetProperties() const override {
176
1.77k
      return MachineFunctionProperties().set(
177
1.77k
          MachineFunctionProperties::Property::NoVRegs);
178
1.77k
    }
179
180
  private:
181
    bool runOnMachineFunction(MachineFunction &MF) override;
182
183
    void allocateBasicBlock(MachineBasicBlock &MBB);
184
    void allocateInstruction(MachineInstr &MI);
185
    void handleDebugValue(MachineInstr &MI);
186
    void handleThroughOperands(MachineInstr &MI,
187
                               SmallVectorImpl<unsigned> &VirtDead);
188
    bool isLastUseOfLocalReg(const MachineOperand &MO) const;
189
190
    void addKillFlag(const LiveReg &LRI);
191
    void killVirtReg(LiveReg &LR);
192
    void killVirtReg(unsigned VirtReg);
193
    void spillVirtReg(MachineBasicBlock::iterator MI, LiveReg &LR);
194
    void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg);
195
196
    void usePhysReg(MachineOperand &MO);
197
    void definePhysReg(MachineBasicBlock::iterator MI, MCPhysReg PhysReg,
198
                       RegState NewState);
199
    unsigned calcSpillCost(MCPhysReg PhysReg) const;
200
    void assignVirtToPhysReg(LiveReg &, MCPhysReg PhysReg);
201
202
5.46k
    LiveRegMap::iterator findLiveVirtReg(unsigned VirtReg) {
203
5.46k
      return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg));
204
5.46k
    }
205
206
77.9k
    LiveRegMap::const_iterator findLiveVirtReg(unsigned VirtReg) const {
207
77.9k
      return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg));
208
77.9k
    }
209
210
    void allocVirtReg(MachineInstr &MI, LiveReg &LR, unsigned Hint);
211
    void allocVirtRegUndef(MachineOperand &MO);
212
    MCPhysReg defineVirtReg(MachineInstr &MI, unsigned OpNum, unsigned VirtReg,
213
                            unsigned Hint);
214
    LiveReg &reloadVirtReg(MachineInstr &MI, unsigned OpNum, unsigned VirtReg,
215
                           unsigned Hint);
216
    void spillAll(MachineBasicBlock::iterator MI, bool OnlyLiveOut);
217
    bool setPhysReg(MachineInstr &MI, MachineOperand &MO, MCPhysReg PhysReg);
218
219
    unsigned traceCopies(unsigned VirtReg) const;
220
    unsigned traceCopyChain(unsigned Reg) const;
221
222
    int getStackSpaceFor(unsigned VirtReg);
223
    void spill(MachineBasicBlock::iterator Before, unsigned VirtReg,
224
               MCPhysReg AssignedReg, bool Kill);
225
    void reload(MachineBasicBlock::iterator Before, unsigned VirtReg,
226
                MCPhysReg PhysReg);
227
228
    bool mayLiveOut(unsigned VirtReg);
229
    bool mayLiveIn(unsigned VirtReg);
230
231
    void dumpState();
232
  };
233
234
} // end anonymous namespace
235
236
char RegAllocFast::ID = 0;
237
238
INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false,
239
                false)
240
241
156k
void RegAllocFast::setPhysRegState(MCPhysReg PhysReg, unsigned NewState) {
242
156k
  PhysRegState[PhysReg] = NewState;
243
156k
}
244
245
/// This allocates space for the specified virtual register to be held on the
246
/// stack.
247
10.0k
int RegAllocFast::getStackSpaceFor(unsigned VirtReg) {
248
10.0k
  // Find the location Reg would belong...
249
10.0k
  int SS = StackSlotForVirtReg[VirtReg];
250
10.0k
  // Already has space allocated?
251
10.0k
  if (SS != -1)
252
5.58k
    return SS;
253
4.50k
254
4.50k
  // Allocate a new stack object for this spill location...
255
4.50k
  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
256
4.50k
  unsigned Size = TRI->getSpillSize(RC);
257
4.50k
  unsigned Align = TRI->getSpillAlignment(RC);
258
4.50k
  int FrameIdx = MFI->CreateSpillStackObject(Size, Align);
259
4.50k
260
4.50k
  // Assign the slot.
261
4.50k
  StackSlotForVirtReg[VirtReg] = FrameIdx;
262
4.50k
  return FrameIdx;
263
4.50k
}
264
265
/// Returns false if \p VirtReg is known to not live out of the current block.
266
4.37k
bool RegAllocFast::mayLiveOut(unsigned VirtReg) {
267
4.37k
  if (MayLiveAcrossBlocks.test(TargetRegisterInfo::virtReg2Index(VirtReg))) {
268
1.38k
    // Cannot be live-out if there are no successors.
269
1.38k
    return !MBB->succ_empty();
270
1.38k
  }
271
2.99k
272
2.99k
  // If this block loops back to itself, it would be necessary to check whether
273
2.99k
  // the use comes after the def.
274
2.99k
  if (MBB->isSuccessor(MBB)) {
275
92
    MayLiveAcrossBlocks.set(TargetRegisterInfo::virtReg2Index(VirtReg));
276
92
    return true;
277
92
  }
278
2.90k
279
2.90k
  // See if the first \p Limit uses of the register are all in the current
280
2.90k
  // block.
281
2.90k
  static const unsigned Limit = 8;
282
2.90k
  unsigned C = 0;
283
2.90k
  for (const MachineInstr &UseInst : MRI->reg_nodbg_instructions(VirtReg)) {
284
1.47k
    if (UseInst.getParent() != MBB || 
++C >= Limit0
) {
285
1.47k
      MayLiveAcrossBlocks.set(TargetRegisterInfo::virtReg2Index(VirtReg));
286
1.47k
      // Cannot be live-out if there are no successors.
287
1.47k
      return !MBB->succ_empty();
288
1.47k
    }
289
1.47k
  }
290
2.90k
291
2.90k
  
return false1.42k
;
292
2.90k
}
293
294
/// Returns false if \p VirtReg is known to not be live into the current block.
295
63.1k
bool RegAllocFast::mayLiveIn(unsigned VirtReg) {
296
63.1k
  if (MayLiveAcrossBlocks.test(TargetRegisterInfo::virtReg2Index(VirtReg)))
297
2.25k
    return !MBB->pred_empty();
298
60.9k
299
60.9k
  // See if the first \p Limit def of the register are all in the current block.
300
60.9k
  static const unsigned Limit = 8;
301
60.9k
  unsigned C = 0;
302
60.9k
  for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {
303
2.34k
    if (DefInst.getParent() != MBB || 
++C >= Limit2.23k
) {
304
107
      MayLiveAcrossBlocks.set(TargetRegisterInfo::virtReg2Index(VirtReg));
305
107
      return !MBB->pred_empty();
306
107
    }
307
2.34k
  }
308
60.9k
309
60.9k
  
return false60.7k
;
310
60.9k
}
311
312
/// Insert spill instruction for \p AssignedReg before \p Before. Update
313
/// DBG_VALUEs with \p VirtReg operands with the stack slot.
314
void RegAllocFast::spill(MachineBasicBlock::iterator Before, unsigned VirtReg,
315
5.03k
                         MCPhysReg AssignedReg, bool Kill) {
316
5.03k
  LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI)
317
5.03k
                    << " in " << printReg(AssignedReg, TRI));
318
5.03k
  int FI = getStackSpaceFor(VirtReg);
319
5.03k
  LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n');
320
5.03k
321
5.03k
  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
322
5.03k
  TII->storeRegToStackSlot(*MBB, Before, AssignedReg, Kill, FI, &RC, TRI);
323
5.03k
  ++NumStores;
324
5.03k
325
5.03k
  // If this register is used by DBG_VALUE then insert new DBG_VALUE to
326
5.03k
  // identify spilled location as the place to find corresponding variable's
327
5.03k
  // value.
328
5.03k
  SmallVectorImpl<MachineInstr *> &LRIDbgValues = LiveDbgValueMap[VirtReg];
329
5.03k
  for (MachineInstr *DBG : LRIDbgValues) {
330
28
    MachineInstr *NewDV = buildDbgValueForSpill(*MBB, Before, *DBG, FI);
331
28
    assert(NewDV->getParent() == MBB && "dangling parent pointer");
332
28
    (void)NewDV;
333
28
    LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);
334
28
  }
335
5.03k
  // Now this register is spilled there is should not be any DBG_VALUE
336
5.03k
  // pointing to this register because they are all pointing to spilled value
337
5.03k
  // now.
338
5.03k
  LRIDbgValues.clear();
339
5.03k
}
340
341
/// Insert reload instruction for \p PhysReg before \p Before.
342
void RegAllocFast::reload(MachineBasicBlock::iterator Before, unsigned VirtReg,
343
5.05k
                          MCPhysReg PhysReg) {
344
5.05k
  LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
345
5.05k
                    << printReg(PhysReg, TRI) << '\n');
346
5.05k
  int FI = getStackSpaceFor(VirtReg);
347
5.05k
  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
348
5.05k
  TII->loadRegFromStackSlot(*MBB, Before, PhysReg, FI, &RC, TRI);
349
5.05k
  ++NumLoads;
350
5.05k
}
351
352
/// Return true if MO is the only remaining reference to its virtual register,
353
/// and it is guaranteed to be a block-local register.
354
59.2k
bool RegAllocFast::isLastUseOfLocalReg(const MachineOperand &MO) const {
355
59.2k
  // If the register has ever been spilled or reloaded, we conservatively assume
356
59.2k
  // it is a global register used in multiple blocks.
357
59.2k
  if (StackSlotForVirtReg[MO.getReg()] != -1)
358
10
    return false;
359
59.2k
360
59.2k
  // Check that the use/def chain has exactly one operand - MO.
361
59.2k
  MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(MO.getReg());
362
59.2k
  if (&*I != &MO)
363
3.56k
    return false;
364
55.6k
  return ++I == MRI->reg_nodbg_end();
365
55.6k
}
366
367
/// Set kill flags on last use of a virtual register.
368
60.7k
void RegAllocFast::addKillFlag(const LiveReg &LR) {
369
60.7k
  if (!LR.LastUse) 
return4.79k
;
370
55.9k
  MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum);
371
55.9k
  if (MO.isUse() && 
!LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)55.5k
) {
372
53.1k
    if (MO.getReg() == LR.PhysReg)
373
52.0k
      MO.setIsKill();
374
53.1k
    // else, don't do anything we are problably redefining a
375
53.1k
    // subreg of this register and given we don't track which
376
53.1k
    // lanes are actually dead, we cannot insert a kill flag here.
377
53.1k
    // Otherwise we may end up in a situation like this:
378
53.1k
    // ... = (MO) physreg:sub1, implicit killed physreg
379
53.1k
    // ... <== Here we would allow later pass to reuse physreg:sub1
380
53.1k
    //         which is potentially wrong.
381
53.1k
    // LR:sub0 = ...
382
53.1k
    // ... = LR.sub1 <== This is going to use physreg:sub1
383
53.1k
  }
384
55.9k
}
385
386
/// Mark virtreg as no longer available.
387
58.2k
void RegAllocFast::killVirtReg(LiveReg &LR) {
388
58.2k
  addKillFlag(LR);
389
58.2k
  assert(PhysRegState[LR.PhysReg] == LR.VirtReg &&
390
58.2k
         "Broken RegState mapping");
391
58.2k
  setPhysRegState(LR.PhysReg, regFree);
392
58.2k
  LR.PhysReg = 0;
393
58.2k
}
394
395
/// Mark virtreg as no longer available.
396
377
void RegAllocFast::killVirtReg(unsigned VirtReg) {
397
377
  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
398
377
         "killVirtReg needs a virtual register");
399
377
  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
400
377
  if (LRI != LiveVirtRegs.end() && LRI->PhysReg)
401
377
    killVirtReg(*LRI);
402
377
}
403
404
/// This method spills the value specified by VirtReg into the corresponding
405
/// stack slot if needed.
406
void RegAllocFast::spillVirtReg(MachineBasicBlock::iterator MI,
407
4.98k
                                unsigned VirtReg) {
408
4.98k
  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
409
4.98k
         "Spilling a physical register is illegal!");
410
4.98k
  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
411
4.98k
  assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
412
4.98k
         "Spilling unmapped virtual register");
413
4.98k
  spillVirtReg(MI, *LRI);
414
4.98k
}
415
416
/// Do the actual work of spilling.
417
8.95k
void RegAllocFast::spillVirtReg(MachineBasicBlock::iterator MI, LiveReg &LR) {
418
8.95k
  assert(PhysRegState[LR.PhysReg] == LR.VirtReg && "Broken RegState mapping");
419
8.95k
420
8.95k
  if (LR.Dirty) {
421
5.03k
    // If this physreg is used by the instruction, we want to kill it on the
422
5.03k
    // instruction, not on the spill.
423
5.03k
    bool SpillKill = MachineBasicBlock::iterator(LR.LastUse) != MI;
424
5.03k
    LR.Dirty = false;
425
5.03k
426
5.03k
    spill(MI, LR.VirtReg, LR.PhysReg, SpillKill);
427
5.03k
428
5.03k
    if (SpillKill)
429
4.79k
      LR.LastUse = nullptr; // Don't kill register again
430
5.03k
  }
431
8.95k
  killVirtReg(LR);
432
8.95k
}
433
434
/// Spill all dirty virtregs without killing them.
435
14.5k
void RegAllocFast::spillAll(MachineBasicBlock::iterator MI, bool OnlyLiveOut) {
436
14.5k
  if (LiveVirtRegs.empty())
437
2.61k
    return;
438
11.8k
  // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
439
11.8k
  // of spilling here is deterministic, if arbitrary.
440
58.0k
  
for (LiveReg &LR : LiveVirtRegs)11.8k
{
441
58.0k
    if (!LR.PhysReg)
442
52.4k
      continue;
443
5.65k
    if (OnlyLiveOut && 
!mayLiveOut(LR.VirtReg)4.37k
)
444
1.68k
      continue;
445
3.97k
    spillVirtReg(MI, LR);
446
3.97k
  }
447
11.8k
  LiveVirtRegs.clear();
448
11.8k
}
449
450
/// Handle the direct use of a physical register.  Check that the register is
451
/// not used by a virtreg. Kill the physreg, marking it free. This may add
452
/// implicit kills to MO->getParent() and invalidate MO.
453
24.4k
void RegAllocFast::usePhysReg(MachineOperand &MO) {
454
24.4k
  // Ignore undef uses.
455
24.4k
  if (MO.isUndef())
456
6
    return;
457
24.4k
458
24.4k
  unsigned PhysReg = MO.getReg();
459
24.4k
  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
460
24.4k
         "Bad usePhysReg operand");
461
24.4k
462
24.4k
  markRegUsedInInstr(PhysReg);
463
24.4k
  switch (PhysRegState[PhysReg]) {
464
24.4k
  case regDisabled:
465
11
    break;
466
24.4k
  case regReserved:
467
24.4k
    PhysRegState[PhysReg] = regFree;
468
24.4k
    LLVM_FALLTHROUGH;
469
24.4k
  case regFree:
470
24.4k
    MO.setIsKill();
471
24.4k
    return;
472
24.4k
  default:
473
0
    // The physreg was allocated to a virtual register. That means the value we
474
0
    // wanted has been clobbered.
475
0
    llvm_unreachable("Instruction uses an allocated register");
476
11
  }
477
11
478
11
  // Maybe a superregister is reserved?
479
81
  
for (MCRegAliasIterator AI(PhysReg, TRI, false); 11
AI.isValid();
++AI70
) {
480
70
    MCPhysReg Alias = *AI;
481
70
    switch (PhysRegState[Alias]) {
482
70
    case regDisabled:
483
50
      break;
484
70
    case regReserved:
485
20
      // Either PhysReg is a subregister of Alias and we mark the
486
20
      // whole register as free, or PhysReg is the superregister of
487
20
      // Alias and we mark all the aliases as disabled before freeing
488
20
      // PhysReg.
489
20
      // In the latter case, since PhysReg was disabled, this means that
490
20
      // its value is defined only by physical sub-registers. This check
491
20
      // is performed by the assert of the default case in this loop.
492
20
      // Note: The value of the superregister may only be partial
493
20
      // defined, that is why regDisabled is a valid state for aliases.
494
20
      assert((TRI->isSuperRegister(PhysReg, Alias) ||
495
20
              TRI->isSuperRegister(Alias, PhysReg)) &&
496
20
             "Instruction is not using a subregister of a reserved register");
497
20
      LLVM_FALLTHROUGH;
498
20
    case regFree:
499
20
      if (TRI->isSuperRegister(PhysReg, Alias)) {
500
0
        // Leave the superregister in the working set.
501
0
        setPhysRegState(Alias, regFree);
502
0
        MO.getParent()->addRegisterKilled(Alias, TRI, true);
503
0
        return;
504
0
      }
505
20
      // Some other alias was in the working set - clear it.
506
20
      setPhysRegState(Alias, regDisabled);
507
20
      break;
508
20
    default:
509
0
      llvm_unreachable("Instruction uses an alias of an allocated register");
510
70
    }
511
70
  }
512
11
513
11
  // All aliases are disabled, bring register into working set.
514
11
  setPhysRegState(PhysReg, regFree);
515
11
  MO.setIsKill();
516
11
}
517
518
/// Mark PhysReg as reserved or free after spilling any virtregs. This is very
519
/// similar to defineVirtReg except the physreg is reserved instead of
520
/// allocated.
521
void RegAllocFast::definePhysReg(MachineBasicBlock::iterator MI,
522
35.1k
                                 MCPhysReg PhysReg, RegState NewState) {
523
35.1k
  markRegUsedInInstr(PhysReg);
524
35.1k
  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
525
35.1k
  case regDisabled:
526
17.1k
    break;
527
35.1k
  default:
528
4.58k
    spillVirtReg(MI, VirtReg);
529
4.58k
    LLVM_FALLTHROUGH;
530
18.0k
  case regFree:
531
18.0k
  case regReserved:
532
18.0k
    setPhysRegState(PhysReg, NewState);
533
18.0k
    return;
534
17.1k
  }
535
17.1k
536
17.1k
  // This is a disabled register, disable all aliases.
537
17.1k
  setPhysRegState(PhysReg, NewState);
538
85.7k
  for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); 
++AI68.6k
) {
539
70.4k
    MCPhysReg Alias = *AI;
540
70.4k
    switch (unsigned VirtReg = PhysRegState[Alias]) {
541
70.4k
    case regDisabled:
542
67.5k
      break;
543
70.4k
    default:
544
402
      spillVirtReg(MI, VirtReg);
545
402
      LLVM_FALLTHROUGH;
546
2.86k
    case regFree:
547
2.86k
    case regReserved:
548
2.86k
      setPhysRegState(Alias, regDisabled);
549
2.86k
      if (TRI->isSuperRegister(PhysReg, Alias))
550
1.75k
        return;
551
1.11k
      break;
552
70.4k
    }
553
70.4k
  }
554
17.1k
}
555
556
/// Return the cost of spilling clearing out PhysReg and aliases so it is free
557
/// for allocation. Returns 0 when PhysReg is free or disabled with all aliases
558
/// disabled - it can be allocated directly.
559
/// \returns spillImpossible when PhysReg or an alias can't be spilled.
560
139k
unsigned RegAllocFast::calcSpillCost(MCPhysReg PhysReg) const {
561
139k
  if (isRegUsedInInstr(PhysReg)) {
562
1.86k
    LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI)
563
1.86k
                      << " is already used in instr.\n");
564
1.86k
    return spillImpossible;
565
1.86k
  }
566
137k
  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
567
137k
  case regDisabled:
568
40.2k
    break;
569
137k
  case regFree:
570
38.9k
    return 0;
571
137k
  case regReserved:
572
2.34k
    LLVM_DEBUG(dbgs() << printReg(VirtReg, TRI) << " corresponding "
573
2.34k
                      << printReg(PhysReg, TRI) << " is reserved already.\n");
574
2.34k
    return spillImpossible;
575
137k
  default: {
576
55.9k
    LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
577
55.9k
    assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
578
55.9k
           "Missing VirtReg entry");
579
55.9k
    return LRI->Dirty ? 
spillDirty43.0k
:
spillClean12.9k
;
580
40.2k
  }
581
40.2k
  }
582
40.2k
583
40.2k
  // This is a disabled register, add up cost of aliases.
584
40.2k
  LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << " is disabled.\n");
585
40.2k
  unsigned Cost = 0;
586
748k
  for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); 
++AI707k
) {
587
707k
    MCPhysReg Alias = *AI;
588
707k
    switch (unsigned VirtReg = PhysRegState[Alias]) {
589
707k
    case regDisabled:
590
673k
      break;
591
707k
    case regFree:
592
12.2k
      ++Cost;
593
12.2k
      break;
594
707k
    case regReserved:
595
123
      return spillImpossible;
596
707k
    default: {
597
22.0k
      LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
598
22.0k
      assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
599
22.0k
             "Missing VirtReg entry");
600
22.0k
      Cost += LRI->Dirty ? 
spillDirty21.0k
:
spillClean1.02k
;
601
22.0k
      break;
602
707k
    }
603
707k
    }
604
707k
  }
605
40.2k
  
return Cost40.1k
;
606
40.2k
}
607
608
/// This method updates local state so that we know that PhysReg is the
609
/// proper container for VirtReg now.  The physical register must not be used
610
/// for anything else when this is called.
611
59.9k
void RegAllocFast::assignVirtToPhysReg(LiveReg &LR, MCPhysReg PhysReg) {
612
59.9k
  unsigned VirtReg = LR.VirtReg;
613
59.9k
  LLVM_DEBUG(dbgs() << "Assigning " << printReg(VirtReg, TRI) << " to "
614
59.9k
                    << printReg(PhysReg, TRI) << '\n');
615
59.9k
  assert(LR.PhysReg == 0 && "Already assigned a physreg");
616
59.9k
  assert(PhysReg != 0 && "Trying to assign no register");
617
59.9k
  LR.PhysReg = PhysReg;
618
59.9k
  setPhysRegState(PhysReg, VirtReg);
619
59.9k
}
620
621
28.7k
static bool isCoalescable(const MachineInstr &MI) {
622
28.7k
  return MI.isFullCopy();
623
28.7k
}
624
625
4.78k
unsigned RegAllocFast::traceCopyChain(unsigned Reg) const {
626
4.78k
  static const unsigned ChainLengthLimit = 3;
627
4.78k
  unsigned C = 0;
628
5.24k
  do {
629
5.24k
    if (TargetRegisterInfo::isPhysicalRegister(Reg))
630
4.50k
      return Reg;
631
741
    assert(TargetRegisterInfo::isVirtualRegister(Reg));
632
741
633
741
    MachineInstr *VRegDef = MRI->getUniqueVRegDef(Reg);
634
741
    if (!VRegDef || 
!isCoalescable(*VRegDef)596
)
635
268
      return 0;
636
473
    Reg = VRegDef->getOperand(1).getReg();
637
473
  } while (++C <= ChainLengthLimit);
638
4.78k
  
return 016
;
639
4.78k
}
640
641
/// Check if any of \p VirtReg's definitions is a copy. If it is follow the
642
/// chain of copies to check whether we reach a physical register we can
643
/// coalesce with.
644
31.5k
unsigned RegAllocFast::traceCopies(unsigned VirtReg) const {
645
31.5k
  static const unsigned DefLimit = 3;
646
31.5k
  unsigned C = 0;
647
31.5k
  for (const MachineInstr &MI : MRI->def_instructions(VirtReg)) {
648
28.1k
    if (isCoalescable(MI)) {
649
4.78k
      unsigned Reg = MI.getOperand(1).getReg();
650
4.78k
      Reg = traceCopyChain(Reg);
651
4.78k
      if (Reg != 0)
652
4.50k
        return Reg;
653
23.6k
    }
654
23.6k
655
23.6k
    if (++C >= DefLimit)
656
122
      break;
657
23.6k
  }
658
31.5k
  
return 027.0k
;
659
31.5k
}
660
661
/// Allocates a physical register for VirtReg.
662
59.9k
void RegAllocFast::allocVirtReg(MachineInstr &MI, LiveReg &LR, unsigned Hint0) {
663
59.9k
  const unsigned VirtReg = LR.VirtReg;
664
59.9k
665
59.9k
  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
666
59.9k
         "Can only allocate virtual registers");
667
59.9k
668
59.9k
  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
669
59.9k
  LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg)
670
59.9k
                    << " in class " << TRI->getRegClassName(&RC)
671
59.9k
                    << " with hint " << printReg(Hint0, TRI) << '\n');
672
59.9k
673
59.9k
  // Take hint when possible.
674
59.9k
  if (TargetRegisterInfo::isPhysicalRegister(Hint0) &&
675
59.9k
      
MRI->isAllocatable(Hint0)34.0k
&&
RC.contains(Hint0)33.7k
) {
676
30.5k
    // Ignore the hint if we would have to spill a dirty register.
677
30.5k
    unsigned Cost = calcSpillCost(Hint0);
678
30.5k
    if (Cost < spillDirty) {
679
28.4k
      LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
680
28.4k
                        << '\n');
681
28.4k
      if (Cost)
682
1.97k
        definePhysReg(MI, Hint0, regFree);
683
28.4k
      assignVirtToPhysReg(LR, Hint0);
684
28.4k
      return;
685
28.4k
    } else {
686
2.15k
      LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
687
2.15k
                        << "occupied\n");
688
2.15k
    }
689
30.5k
  } else {
690
29.3k
    Hint0 = 0;
691
29.3k
  }
692
59.9k
693
59.9k
  // Try other hint.
694
59.9k
  unsigned Hint1 = traceCopies(VirtReg);
695
31.5k
  if (TargetRegisterInfo::isPhysicalRegister(Hint1) &&
696
31.5k
      
MRI->isAllocatable(Hint1)4.50k
&&
RC.contains(Hint1)4.17k
&&
697
31.5k
      
!isRegUsedInInstr(Hint1)2.86k
) {
698
2.86k
    // Ignore the hint if we would have to spill a dirty register.
699
2.86k
    unsigned Cost = calcSpillCost(Hint1);
700
2.86k
    if (Cost < spillDirty) {
701
1.16k
      LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
702
1.16k
                        << '\n');
703
1.16k
      if (Cost)
704
1.04k
        definePhysReg(MI, Hint1, regFree);
705
1.16k
      assignVirtToPhysReg(LR, Hint1);
706
1.16k
      return;
707
1.70k
    } else {
708
1.70k
      LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
709
1.70k
                        << "occupied\n");
710
1.70k
    }
711
28.6k
  } else {
712
28.6k
    Hint1 = 0;
713
28.6k
  }
714
31.5k
715
31.5k
  MCPhysReg BestReg = 0;
716
30.3k
  unsigned BestCost = spillImpossible;
717
30.3k
  ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
718
105k
  for (MCPhysReg PhysReg : AllocationOrder) {
719
105k
    LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << ' ');
720
105k
    unsigned Cost = calcSpillCost(PhysReg);
721
105k
    LLVM_DEBUG(dbgs() << "Cost: " << Cost << " BestCost: " << BestCost << '\n');
722
105k
    // Immediate take a register with cost 0.
723
105k
    if (Cost == 0) {
724
29.3k
      assignVirtToPhysReg(LR, PhysReg);
725
29.3k
      return;
726
29.3k
    }
727
76.6k
728
76.6k
    if (PhysReg == Hint1 || 
PhysReg == Hint075.4k
)
729
1.86k
      Cost -= spillPrefBonus;
730
76.6k
731
76.6k
    if (Cost < BestCost) {
732
19.4k
      BestReg = PhysReg;
733
19.4k
      BestCost = Cost;
734
19.4k
    }
735
76.6k
  }
736
30.3k
737
30.3k
  
if (1.05k
!BestReg1.05k
) {
738
15
    // Nothing we can do: Report an error and keep going with an invalid
739
15
    // allocation.
740
15
    if (MI.isInlineAsm())
741
15
      MI.emitError("inline assembly requires more registers than available");
742
0
    else
743
0
      MI.emitError("ran out of registers during register allocation");
744
15
    definePhysReg(MI, *AllocationOrder.begin(), regFree);
745
15
    assignVirtToPhysReg(LR, *AllocationOrder.begin());
746
15
    return;
747
15
  }
748
1.03k
749
1.03k
  definePhysReg(MI, BestReg, regFree);
750
1.03k
  assignVirtToPhysReg(LR, BestReg);
751
1.03k
}
752
753
3
void RegAllocFast::allocVirtRegUndef(MachineOperand &MO) {
754
3
  assert(MO.isUndef() && "expected undef use");
755
3
  unsigned VirtReg = MO.getReg();
756
3
  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && "Expected virtreg");
757
3
758
3
  LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
759
3
  MCPhysReg PhysReg;
760
3
  if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
761
3
    PhysReg = LRI->PhysReg;
762
3
  } else {
763
0
    const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
764
0
    ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
765
0
    assert(!AllocationOrder.empty() && "Allocation order must not be empty");
766
0
    PhysReg = AllocationOrder[0];
767
0
  }
768
3
769
3
  unsigned SubRegIdx = MO.getSubReg();
770
3
  if (SubRegIdx != 0) {
771
3
    PhysReg = TRI->getSubReg(PhysReg, SubRegIdx);
772
3
    MO.setSubReg(0);
773
3
  }
774
3
  MO.setReg(PhysReg);
775
3
  MO.setIsRenamable(true);
776
3
}
777
778
/// Allocates a register for VirtReg and mark it as dirty.
779
MCPhysReg RegAllocFast::defineVirtReg(MachineInstr &MI, unsigned OpNum,
780
58.9k
                                      unsigned VirtReg, unsigned Hint) {
781
58.9k
  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
782
58.9k
         "Not a virtual register");
783
58.9k
  LiveRegMap::iterator LRI;
784
58.9k
  bool New;
785
58.9k
  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
786
58.9k
  if (!LRI->PhysReg) {
787
54.8k
    // If there is no hint, peek at the only use of this register.
788
54.8k
    if ((!Hint || 
!TargetRegisterInfo::isPhysicalRegister(Hint)26.3k
) &&
789
54.8k
        
MRI->hasOneNonDBGUse(VirtReg)28.5k
) {
790
25.0k
      const MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(VirtReg);
791
25.0k
      // It's a copy, use the destination register as a hint.
792
25.0k
      if (UseMI.isCopyLike())
793
10.8k
        Hint = UseMI.getOperand(0).getReg();
794
25.0k
    }
795
54.8k
    allocVirtReg(MI, *LRI, Hint);
796
54.8k
  } else 
if (4.05k
LRI->LastUse4.05k
) {
797
4.05k
    // Redefining a live register - kill at the last use, unless it is this
798
4.05k
    // instruction defining VirtReg multiple times.
799
4.05k
    if (LRI->LastUse != &MI || LRI->LastUse->getOperand(LRI->LastOpNum).isUse())
800
2.46k
      addKillFlag(*LRI);
801
4.05k
  }
802
58.9k
  assert(LRI->PhysReg && "Register not assigned");
803
58.9k
  LRI->LastUse = &MI;
804
58.9k
  LRI->LastOpNum = OpNum;
805
58.9k
  LRI->Dirty = true;
806
58.9k
  markRegUsedInInstr(LRI->PhysReg);
807
58.9k
  return LRI->PhysReg;
808
58.9k
}
809
810
/// Make sure VirtReg is available in a physreg and return it.
811
RegAllocFast::LiveReg &RegAllocFast::reloadVirtReg(MachineInstr &MI,
812
                                                   unsigned OpNum,
813
                                                   unsigned VirtReg,
814
65.0k
                                                   unsigned Hint) {
815
65.0k
  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
816
65.0k
         "Not a virtual register");
817
65.0k
  LiveRegMap::iterator LRI;
818
65.0k
  bool New;
819
65.0k
  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
820
65.0k
  MachineOperand &MO = MI.getOperand(OpNum);
821
65.0k
  if (!LRI->PhysReg) {
822
5.05k
    allocVirtReg(MI, *LRI, Hint);
823
5.05k
    reload(MI, VirtReg, LRI->PhysReg);
824
59.9k
  } else if (LRI->Dirty) {
825
59.2k
    if (isLastUseOfLocalReg(MO)) {
826
48.3k
      LLVM_DEBUG(dbgs() << "Killing last use: " << MO << '\n');
827
48.3k
      if (MO.isUse())
828
48.3k
        MO.setIsKill();
829
0
      else
830
0
        MO.setIsDead();
831
48.3k
    } else 
if (10.9k
MO.isKill()10.9k
) {
832
0
      LLVM_DEBUG(dbgs() << "Clearing dubious kill: " << MO << '\n');
833
0
      MO.setIsKill(false);
834
10.9k
    } else if (MO.isDead()) {
835
0
      LLVM_DEBUG(dbgs() << "Clearing dubious dead: " << MO << '\n');
836
0
      MO.setIsDead(false);
837
0
    }
838
59.2k
  } else 
if (698
MO.isKill()698
) {
839
0
    // We must remove kill flags from uses of reloaded registers because the
840
0
    // register would be killed immediately, and there might be a second use:
841
0
    //   %foo = OR killed %x, %x
842
0
    // This would cause a second reload of %x into a different register.
843
0
    LLVM_DEBUG(dbgs() << "Clearing clean kill: " << MO << '\n');
844
0
    MO.setIsKill(false);
845
698
  } else if (MO.isDead()) {
846
0
    LLVM_DEBUG(dbgs() << "Clearing clean dead: " << MO << '\n');
847
0
    MO.setIsDead(false);
848
0
  }
849
65.0k
  assert(LRI->PhysReg && "Register not assigned");
850
65.0k
  LRI->LastUse = &MI;
851
65.0k
  LRI->LastOpNum = OpNum;
852
65.0k
  markRegUsedInInstr(LRI->PhysReg);
853
65.0k
  return *LRI;
854
65.0k
}
855
856
/// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This
857
/// may invalidate any operand pointers.  Return true if the operand kills its
858
/// register.
859
bool RegAllocFast::setPhysReg(MachineInstr &MI, MachineOperand &MO,
860
122k
                              MCPhysReg PhysReg) {
861
122k
  bool Dead = MO.isDead();
862
122k
  if (!MO.getSubReg()) {
863
119k
    MO.setReg(PhysReg);
864
119k
    MO.setIsRenamable(true);
865
119k
    return MO.isKill() || 
Dead71.2k
;
866
119k
  }
867
3.35k
868
3.35k
  // Handle subregister index.
869
3.35k
  MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 
00
);
870
3.35k
  MO.setIsRenamable(true);
871
3.35k
  MO.setSubReg(0);
872
3.35k
873
3.35k
  // A kill flag implies killing the full register. Add corresponding super
874
3.35k
  // register kill.
875
3.35k
  if (MO.isKill()) {
876
1.03k
    MI.addRegisterKilled(PhysReg, TRI, true);
877
1.03k
    return true;
878
1.03k
  }
879
2.32k
880
2.32k
  // A <def,read-undef> of a sub-register requires an implicit def of the full
881
2.32k
  // register.
882
2.32k
  if (MO.isDef() && 
MO.isUndef()1.87k
)
883
282
    MI.addRegisterDefined(PhysReg, TRI);
884
2.32k
885
2.32k
  return Dead;
886
2.32k
}
887
888
// Handles special instruction operand like early clobbers and tied ops when
889
// there are additional physreg defines.
890
void RegAllocFast::handleThroughOperands(MachineInstr &MI,
891
5.23k
                                         SmallVectorImpl<unsigned> &VirtDead) {
892
5.23k
  LLVM_DEBUG(dbgs() << "Scanning for through registers:");
893
5.23k
  SmallSet<unsigned, 8> ThroughRegs;
894
20.8k
  for (const MachineOperand &MO : MI.operands()) {
895
20.8k
    if (!MO.isReg()) 
continue11.6k
;
896
9.21k
    unsigned Reg = MO.getReg();
897
9.21k
    if (!TargetRegisterInfo::isVirtualRegister(Reg))
898
4.46k
      continue;
899
4.74k
    if (MO.isEarlyClobber() || 
(4.41k
MO.isUse()4.41k
&&
MO.isTied()2.46k
) ||
900
4.74k
        
(4.15k
MO.getSubReg()4.15k
&&
MI.readsVirtualRegister(Reg)1.59k
)) {
901
2.19k
      if (ThroughRegs.insert(Reg).second)
902
2.19k
        LLVM_DEBUG(dbgs() << ' ' << printReg(Reg));
903
2.19k
    }
904
4.74k
  }
905
5.23k
906
5.23k
  // If any physreg defines collide with preallocated through registers,
907
5.23k
  // we must spill and reallocate.
908
5.23k
  LLVM_DEBUG(dbgs() << "\nChecking for physdef collisions.\n");
909
20.8k
  for (const MachineOperand &MO : MI.operands()) {
910
20.8k
    if (!MO.isReg() || 
!MO.isDef()9.21k
)
continue14.4k
;
911
6.36k
    unsigned Reg = MO.getReg();
912
6.36k
    if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) 
continue2.28k
;
913
4.08k
    markRegUsedInInstr(Reg);
914
137k
    for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); 
++AI132k
) {
915
132k
      if (ThroughRegs.count(PhysRegState[*AI]))
916
1
        definePhysReg(MI, *AI, regFree);
917
132k
    }
918
4.08k
  }
919
5.23k
920
5.23k
  SmallVector<unsigned, 8> PartialDefs;
921
5.23k
  LLVM_DEBUG(dbgs() << "Allocating tied uses.\n");
922
26.0k
  for (unsigned I = 0, E = MI.getNumOperands(); I != E; 
++I20.8k
) {
923
20.8k
    MachineOperand &MO = MI.getOperand(I);
924
20.8k
    if (!MO.isReg()) 
continue11.6k
;
925
9.21k
    unsigned Reg = MO.getReg();
926
9.21k
    if (!TargetRegisterInfo::isVirtualRegister(Reg)) 
continue4.46k
;
927
4.74k
    if (MO.isUse()) {
928
2.46k
      if (!MO.isTied()) 
continue2.20k
;
929
265
      LLVM_DEBUG(dbgs() << "Operand " << I << "(" << MO
930
265
                        << ") is tied to operand " << MI.findTiedOperandIdx(I)
931
265
                        << ".\n");
932
265
      LiveReg &LR = reloadVirtReg(MI, I, Reg, 0);
933
265
      MCPhysReg PhysReg = LR.PhysReg;
934
265
      setPhysReg(MI, MO, PhysReg);
935
265
      // Note: we don't update the def operand yet. That would cause the normal
936
265
      // def-scan to attempt spilling.
937
2.28k
    } else if (MO.getSubReg() && 
MI.readsVirtualRegister(Reg)1.59k
) {
938
1.59k
      LLVM_DEBUG(dbgs() << "Partial redefine: " << MO << '\n');
939
1.59k
      // Reload the register, but don't assign to the operand just yet.
940
1.59k
      // That would confuse the later phys-def processing pass.
941
1.59k
      LiveReg &LR = reloadVirtReg(MI, I, Reg, 0);
942
1.59k
      PartialDefs.push_back(LR.PhysReg);
943
1.59k
    }
944
4.74k
  }
945
5.23k
946
5.23k
  LLVM_DEBUG(dbgs() << "Allocating early clobbers.\n");
947
26.0k
  for (unsigned I = 0, E = MI.getNumOperands(); I != E; 
++I20.8k
) {
948
20.8k
    const MachineOperand &MO = MI.getOperand(I);
949
20.8k
    if (!MO.isReg()) 
continue11.6k
;
950
9.21k
    unsigned Reg = MO.getReg();
951
9.21k
    if (!TargetRegisterInfo::isVirtualRegister(Reg)) 
continue4.72k
;
952
4.48k
    if (!MO.isEarlyClobber())
953
4.15k
      continue;
954
331
    // Note: defineVirtReg may invalidate MO.
955
331
    MCPhysReg PhysReg = defineVirtReg(MI, I, Reg, 0);
956
331
    if (setPhysReg(MI, MI.getOperand(I), PhysReg))
957
107
      VirtDead.push_back(Reg);
958
331
  }
959
5.23k
960
5.23k
  // Restore UsedInInstr to a state usable for allocating normal virtual uses.
961
5.23k
  UsedInInstr.clear();
962
20.8k
  for (const MachineOperand &MO : MI.operands()) {
963
20.8k
    if (!MO.isReg() || 
(9.21k
MO.isDef()9.21k
&&
!MO.isEarlyClobber()6.36k
))
continue13.6k
;
964
7.15k
    unsigned Reg = MO.getReg();
965
7.15k
    if (!Reg || 
!TargetRegisterInfo::isPhysicalRegister(Reg)6.88k
)
continue2.47k
;
966
4.67k
    LLVM_DEBUG(dbgs() << "\tSetting " << printReg(Reg, TRI)
967
4.67k
                      << " as used in instr\n");
968
4.67k
    markRegUsedInInstr(Reg);
969
4.67k
  }
970
5.23k
971
5.23k
  // Also mark PartialDefs as used to avoid reallocation.
972
5.23k
  for (unsigned PartialDef : PartialDefs)
973
1.59k
    markRegUsedInInstr(PartialDef);
974
5.23k
}
975
976
#ifndef NDEBUG
977
void RegAllocFast::dumpState() {
978
  for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) {
979
    if (PhysRegState[Reg] == regDisabled) continue;
980
    dbgs() << " " << printReg(Reg, TRI);
981
    switch(PhysRegState[Reg]) {
982
    case regFree:
983
      break;
984
    case regReserved:
985
      dbgs() << "*";
986
      break;
987
    default: {
988
      dbgs() << '=' << printReg(PhysRegState[Reg]);
989
      LiveRegMap::iterator LRI = findLiveVirtReg(PhysRegState[Reg]);
990
      assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
991
             "Missing VirtReg entry");
992
      if (LRI->Dirty)
993
        dbgs() << "*";
994
      assert(LRI->PhysReg == Reg && "Bad inverse map");
995
      break;
996
    }
997
    }
998
  }
999
  dbgs() << '\n';
1000
  // Check that LiveVirtRegs is the inverse.
1001
  for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
1002
       e = LiveVirtRegs.end(); i != e; ++i) {
1003
    if (!i->PhysReg)
1004
      continue;
1005
    assert(TargetRegisterInfo::isVirtualRegister(i->VirtReg) &&
1006
           "Bad map key");
1007
    assert(TargetRegisterInfo::isPhysicalRegister(i->PhysReg) &&
1008
           "Bad map value");
1009
    assert(PhysRegState[i->PhysReg] == i->VirtReg && "Bad inverse map");
1010
  }
1011
}
1012
#endif
1013
1014
103k
void RegAllocFast::allocateInstruction(MachineInstr &MI) {
1015
103k
  const MCInstrDesc &MCID = MI.getDesc();
1016
103k
1017
103k
  // If this is a copy, we may be able to coalesce.
1018
103k
  unsigned CopySrcReg = 0;
1019
103k
  unsigned CopyDstReg = 0;
1020
103k
  unsigned CopySrcSub = 0;
1021
103k
  unsigned CopyDstSub = 0;
1022
103k
  if (MI.isCopy()) {
1023
38.9k
    CopyDstReg = MI.getOperand(0).getReg();
1024
38.9k
    CopySrcReg = MI.getOperand(1).getReg();
1025
38.9k
    CopyDstSub = MI.getOperand(0).getSubReg();
1026
38.9k
    CopySrcSub = MI.getOperand(1).getSubReg();
1027
38.9k
  }
1028
103k
1029
103k
  // Track registers used by instruction.
1030
103k
  UsedInInstr.clear();
1031
103k
1032
103k
  // First scan.
1033
103k
  // Mark physreg uses and early clobbers as used.
1034
103k
  // Find the end of the virtreg operands
1035
103k
  unsigned VirtOpEnd = 0;
1036
103k
  bool hasTiedOps = false;
1037
103k
  bool hasEarlyClobbers = false;
1038
103k
  bool hasPartialRedefs = false;
1039
103k
  bool hasPhysDefs = false;
1040
441k
  for (unsigned i = 0, e = MI.getNumOperands(); i != e; 
++i338k
) {
1041
338k
    MachineOperand &MO = MI.getOperand(i);
1042
338k
    // Make sure MRI knows about registers clobbered by regmasks.
1043
338k
    if (MO.isRegMask()) {
1044
3.26k
      MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
1045
3.26k
      continue;
1046
3.26k
    }
1047
334k
    if (!MO.isReg()) 
continue94.8k
;
1048
240k
    unsigned Reg = MO.getReg();
1049
240k
    if (!Reg) 
continue29.7k
;
1050
210k
    if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1051
122k
      VirtOpEnd = i+1;
1052
122k
      if (MO.isUse()) {
1053
63.4k
        hasTiedOps = hasTiedOps ||
1054
63.4k
                            
MCID.getOperandConstraint(i, MCOI::TIED_TO) != -161.6k
;
1055
63.4k
      } else {
1056
58.9k
        if (MO.isEarlyClobber())
1057
331
          hasEarlyClobbers = true;
1058
58.9k
        if (MO.getSubReg() && 
MI.readsVirtualRegister(Reg)1.87k
)
1059
1.59k
          hasPartialRedefs = true;
1060
58.9k
      }
1061
122k
      continue;
1062
122k
    }
1063
88.0k
    if (!MRI->isAllocatable(Reg)) 
continue43.6k
;
1064
44.3k
    if (MO.isUse()) {
1065
24.4k
      usePhysReg(MO);
1066
24.4k
    } else 
if (19.8k
MO.isEarlyClobber()19.8k
) {
1067
3.67k
      definePhysReg(MI, Reg,
1068
3.67k
                    (MO.isImplicit() || 
MO.isDead()0
) ? regFree :
regReserved0
);
1069
3.67k
      hasEarlyClobbers = true;
1070
3.67k
    } else
1071
16.1k
      hasPhysDefs = true;
1072
44.3k
  }
1073
103k
1074
103k
  // The instruction may have virtual register operands that must be allocated
1075
103k
  // the same register at use-time and def-time: early clobbers and tied
1076
103k
  // operands. If there are also physical defs, these registers must avoid
1077
103k
  // both physical defs and uses, making them more constrained than normal
1078
103k
  // operands.
1079
103k
  // Similarly, if there are multiple defs and tied operands, we must make
1080
103k
  // sure the same register is allocated to uses and defs.
1081
103k
  // We didn't detect inline asm tied operands above, so just make this extra
1082
103k
  // pass for all inline asm.
1083
103k
  if (MI.isInlineAsm() || 
hasEarlyClobbers100k
||
hasPartialRedefs100k
||
1084
103k
      
(98.5k
hasTiedOps98.5k
&&
(2.29k
hasPhysDefs2.29k
||
MCID.getNumDefs() > 12.29k
))) {
1085
5.23k
    handleThroughOperands(MI, VirtDead);
1086
5.23k
    // Don't attempt coalescing when we have funny stuff going on.
1087
5.23k
    CopyDstReg = 0;
1088
5.23k
    // Pretend we have early clobbers so the use operands get marked below.
1089
5.23k
    // This is not necessary for the common case of a single tied use.
1090
5.23k
    hasEarlyClobbers = true;
1091
5.23k
  }
1092
103k
1093
103k
  // Second scan.
1094
103k
  // Allocate virtreg uses.
1095
103k
  bool HasUndefUse = false;
1096
249k
  for (unsigned I = 0; I != VirtOpEnd; 
++I146k
) {
1097
146k
    MachineOperand &MO = MI.getOperand(I);
1098
146k
    if (!MO.isReg()) 
continue7.77k
;
1099
138k
    unsigned Reg = MO.getReg();
1100
138k
    if (!TargetRegisterInfo::isVirtualRegister(Reg)) 
continue16.4k
;
1101
121k
    if (MO.isUse()) {
1102
63.1k
      if (MO.isUndef()) {
1103
3
        HasUndefUse = true;
1104
3
        // There is no need to allocate a register for an undef use.
1105
3
        continue;
1106
3
      }
1107
63.1k
1108
63.1k
      // Populate MayLiveAcrossBlocks in case the use block is allocated before
1109
63.1k
      // the def block (removing the vreg uses).
1110
63.1k
      mayLiveIn(Reg);
1111
63.1k
1112
63.1k
      LiveReg &LR = reloadVirtReg(MI, I, Reg, CopyDstReg);
1113
63.1k
      MCPhysReg PhysReg = LR.PhysReg;
1114
63.1k
      CopySrcReg = (CopySrcReg == Reg || 
CopySrcReg == PhysReg37.1k
) ?
PhysReg26.0k
:
037.1k
;
1115
63.1k
      if (setPhysReg(MI, MO, PhysReg))
1116
48.9k
        killVirtReg(LR);
1117
63.1k
    }
1118
121k
  }
1119
103k
1120
103k
  // Allocate undef operands. This is a separate step because in a situation
1121
103k
  // like  ` = OP undef %X, %X`    both operands need the same register assign
1122
103k
  // so we should perform the normal assignment first.
1123
103k
  if (HasUndefUse) {
1124
12
    for (MachineOperand &MO : MI.uses()) {
1125
12
      if (!MO.isReg() || !MO.isUse())
1126
0
        continue;
1127
12
      unsigned Reg = MO.getReg();
1128
12
      if (!TargetRegisterInfo::isVirtualRegister(Reg))
1129
9
        continue;
1130
3
1131
3
      assert(MO.isUndef() && "Should only have undef virtreg uses left");
1132
3
      allocVirtRegUndef(MO);
1133
3
    }
1134
3
  }
1135
103k
1136
103k
  // Track registers defined by instruction - early clobbers and tied uses at
1137
103k
  // this point.
1138
103k
  UsedInInstr.clear();
1139
103k
  if (hasEarlyClobbers) {
1140
20.8k
    for (const MachineOperand &MO : MI.operands()) {
1141
20.8k
      if (!MO.isReg()) 
continue11.6k
;
1142
9.21k
      unsigned Reg = MO.getReg();
1143
9.21k
      if (!Reg || 
!TargetRegisterInfo::isPhysicalRegister(Reg)8.93k
)
continue2.22k
;
1144
6.98k
      // Look for physreg defs and tied uses.
1145
6.98k
      if (!MO.isDef() && 
!MO.isTied()2.57k
)
continue2.27k
;
1146
4.71k
      markRegUsedInInstr(Reg);
1147
4.71k
    }
1148
5.23k
  }
1149
103k
1150
103k
  unsigned DefOpEnd = MI.getNumOperands();
1151
103k
  if (MI.isCall()) {
1152
3.37k
    // Spill all virtregs before a call. This serves one purpose: If an
1153
3.37k
    // exception is thrown, the landing pad is going to expect to find
1154
3.37k
    // registers in their spill slots.
1155
3.37k
    // Note: although this is appealing to just consider all definitions
1156
3.37k
    // as call-clobbered, this is not correct because some of those
1157
3.37k
    // definitions may be used later on and we do not want to reuse
1158
3.37k
    // those for virtual registers in between.
1159
3.37k
    LLVM_DEBUG(dbgs() << "  Spilling remaining registers before call.\n");
1160
3.37k
    spillAll(MI, /*OnlyLiveOut*/ false);
1161
3.37k
  }
1162
103k
1163
103k
  // Third scan.
1164
103k
  // Mark all physreg defs as used before allocating virtreg defs.
1165
442k
  for (unsigned I = 0; I != DefOpEnd; 
++I339k
) {
1166
339k
    const MachineOperand &MO = MI.getOperand(I);
1167
339k
    if (!MO.isReg() || 
!MO.isDef()241k
||
!MO.getReg()98.4k
||
MO.isEarlyClobber()98.4k
)
1168
245k
      continue;
1169
94.1k
    unsigned Reg = MO.getReg();
1170
94.1k
1171
94.1k
    if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg) ||
1172
94.1k
        
!MRI->isAllocatable(Reg)35.5k
)
1173
77.9k
      continue;
1174
16.1k
    definePhysReg(MI, Reg, MO.isDead() ? 
regFree2.47k
:
regReserved13.7k
);
1175
16.1k
  }
1176
103k
1177
103k
  // Fourth scan.
1178
103k
  // Allocate defs and collect dead defs.
1179
442k
  for (unsigned I = 0; I != DefOpEnd; 
++I339k
) {
1180
339k
    const MachineOperand &MO = MI.getOperand(I);
1181
339k
    if (!MO.isReg() || 
!MO.isDef()241k
||
!MO.getReg()98.4k
||
MO.isEarlyClobber()98.4k
)
1182
245k
      continue;
1183
94.1k
    unsigned Reg = MO.getReg();
1184
94.1k
1185
94.1k
    // We have already dealt with phys regs in the previous scan.
1186
94.1k
    if (TargetRegisterInfo::isPhysicalRegister(Reg))
1187
35.5k
      continue;
1188
58.6k
    MCPhysReg PhysReg = defineVirtReg(MI, I, Reg, CopySrcReg);
1189
58.6k
    if (setPhysReg(MI, MI.getOperand(I), PhysReg)) {
1190
270
      VirtDead.push_back(Reg);
1191
270
      CopyDstReg = 0; // cancel coalescing;
1192
270
    } else
1193
58.3k
      CopyDstReg = (CopyDstReg == Reg || 
CopyDstReg == PhysReg32.0k
) ?
PhysReg26.2k
:
032.0k
;
1194
58.6k
  }
1195
103k
1196
103k
  // Kill dead defs after the scan to ensure that multiple defs of the same
1197
103k
  // register are allocated identically. We didn't need to do this for uses
1198
103k
  // because we are crerating our own kill flags, and they are always at the
1199
103k
  // last use.
1200
103k
  for (unsigned VirtReg : VirtDead)
1201
377
    killVirtReg(VirtReg);
1202
103k
  VirtDead.clear();
1203
103k
1204
103k
  LLVM_DEBUG(dbgs() << "<< " << MI);
1205
103k
  if (CopyDstReg && 
CopyDstReg == CopySrcReg37.2k
&&
CopyDstSub == CopySrcSub30.3k
) {
1206
30.3k
    LLVM_DEBUG(dbgs() << "Mark identity copy for removal\n");
1207
30.3k
    Coalesced.push_back(&MI);
1208
30.3k
  }
1209
103k
}
1210
1211
135
void RegAllocFast::handleDebugValue(MachineInstr &MI) {
1212
135
  MachineOperand &MO = MI.getOperand(0);
1213
135
1214
135
  // Ignore DBG_VALUEs that aren't based on virtual registers. These are
1215
135
  // mostly constants and frame indices.
1216
135
  if (!MO.isReg())
1217
32
    return;
1218
103
  unsigned Reg = MO.getReg();
1219
103
  if (!TargetRegisterInfo::isVirtualRegister(Reg))
1220
7
    return;
1221
96
1222
96
  // See if this virtual register has already been allocated to a physical
1223
96
  // register or spilled to a stack slot.
1224
96
  LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
1225
96
  if (LRI != LiveVirtRegs.end() && 
LRI->PhysReg94
) {
1226
94
    setPhysReg(MI, MO, LRI->PhysReg);
1227
94
  } else {
1228
2
    int SS = StackSlotForVirtReg[Reg];
1229
2
    if (SS != -1) {
1230
2
      // Modify DBG_VALUE now that the value is in a spill slot.
1231
2
      updateDbgValueForSpill(MI, SS);
1232
2
      LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << MI);
1233
2
      return;
1234
2
    }
1235
0
1236
0
    // We can't allocate a physreg for a DebugValue, sorry!
1237
0
    LLVM_DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
1238
0
    MO.setReg(0);
1239
0
  }
1240
96
1241
96
  // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so
1242
96
  // that future spills of Reg will have DBG_VALUEs.
1243
96
  LiveDbgValueMap[Reg].push_back(&MI);
1244
94
}
1245
1246
11.1k
void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) {
1247
11.1k
  this->MBB = &MBB;
1248
11.1k
  LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);
1249
11.1k
1250
11.1k
  PhysRegState.assign(TRI->getNumRegs(), regDisabled);
1251
11.1k
  assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
1252
11.1k
1253
11.1k
  MachineBasicBlock::iterator MII = MBB.begin();
1254
11.1k
1255
11.1k
  // Add live-in registers as live.
1256
11.1k
  for (const MachineBasicBlock::RegisterMaskPair LI : MBB.liveins())
1257
11.2k
    if (MRI->isAllocatable(LI.PhysReg))
1258
11.2k
      definePhysReg(MII, LI.PhysReg, regReserved);
1259
11.1k
1260
11.1k
  VirtDead.clear();
1261
11.1k
  Coalesced.clear();
1262
11.1k
1263
11.1k
  // Otherwise, sequentially allocate each instruction in the MBB.
1264
103k
  for (MachineInstr &MI : MBB) {
1265
103k
    LLVM_DEBUG(
1266
103k
      dbgs() << "\n>> " << MI << "Regs:";
1267
103k
      dumpState()
1268
103k
    );
1269
103k
1270
103k
    // Special handling for debug values. Note that they are not allowed to
1271
103k
    // affect codegen of the other instructions in any way.
1272
103k
    if (MI.isDebugValue()) {
1273
135
      handleDebugValue(MI);
1274
135
      continue;
1275
135
    }
1276
103k
1277
103k
    allocateInstruction(MI);
1278
103k
  }
1279
11.1k
1280
11.1k
  // Spill all physical registers holding virtual registers now.
1281
11.1k
  LLVM_DEBUG(dbgs() << "Spilling live registers at end of block.\n");
1282
11.1k
  spillAll(MBB.getFirstTerminator(), /*OnlyLiveOut*/ true);
1283
11.1k
1284
11.1k
  // Erase all the coalesced copies. We are delaying it until now because
1285
11.1k
  // LiveVirtRegs might refer to the instrs.
1286
11.1k
  for (MachineInstr *MI : Coalesced)
1287
30.3k
    MBB.erase(MI);
1288
11.1k
  NumCoalesced += Coalesced.size();
1289
11.1k
1290
11.1k
  LLVM_DEBUG(MBB.dump());
1291
11.1k
}
1292
1293
8.06k
bool RegAllocFast::runOnMachineFunction(MachineFunction &MF) {
1294
8.06k
  LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1295
8.06k
                    << "********** Function: " << MF.getName() << '\n');
1296
8.06k
  MRI = &MF.getRegInfo();
1297
8.06k
  const TargetSubtargetInfo &STI = MF.getSubtarget();
1298
8.06k
  TRI = STI.getRegisterInfo();
1299
8.06k
  TII = STI.getInstrInfo();
1300
8.06k
  MFI = &MF.getFrameInfo();
1301
8.06k
  MRI->freezeReservedRegs(MF);
1302
8.06k
  RegClassInfo.runOnMachineFunction(MF);
1303
8.06k
  UsedInInstr.clear();
1304
8.06k
  UsedInInstr.setUniverse(TRI->getNumRegUnits());
1305
8.06k
1306
8.06k
  // initialize the virtual->physical register map to have a 'null'
1307
8.06k
  // mapping for all virtual registers
1308
8.06k
  unsigned NumVirtRegs = MRI->getNumVirtRegs();
1309
8.06k
  StackSlotForVirtReg.resize(NumVirtRegs);
1310
8.06k
  LiveVirtRegs.setUniverse(NumVirtRegs);
1311
8.06k
  MayLiveAcrossBlocks.clear();
1312
8.06k
  MayLiveAcrossBlocks.resize(NumVirtRegs);
1313
8.06k
1314
8.06k
  // Loop over all of the basic blocks, eliminating virtual register references
1315
8.06k
  for (MachineBasicBlock &MBB : MF)
1316
11.1k
    allocateBasicBlock(MBB);
1317
8.06k
1318
8.06k
  // All machine operands and other references to virtual registers have been
1319
8.06k
  // replaced. Remove the virtual registers.
1320
8.06k
  MRI->clearVirtRegs();
1321
8.06k
1322
8.06k
  StackSlotForVirtReg.clear();
1323
8.06k
  LiveDbgValueMap.clear();
1324
8.06k
  return true;
1325
8.06k
}
1326
1327
1.82k
FunctionPass *llvm::createFastRegisterAllocator() {
1328
1.82k
  return new RegAllocFast();
1329
1.82k
}