xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/RegAllocFast.cpp (revision ec0ea6efa1ad229d75c394c1a9b9cac33af2b1d3)
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/RegAllocCommon.h"
31 #include "llvm/CodeGen/RegAllocRegistry.h"
32 #include "llvm/CodeGen/RegisterClassInfo.h"
33 #include "llvm/CodeGen/TargetInstrInfo.h"
34 #include "llvm/CodeGen/TargetOpcodes.h"
35 #include "llvm/CodeGen/TargetRegisterInfo.h"
36 #include "llvm/CodeGen/TargetSubtargetInfo.h"
37 #include "llvm/IR/DebugLoc.h"
38 #include "llvm/IR/Metadata.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/MC/MCInstrDesc.h"
41 #include "llvm/MC/MCRegisterInfo.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/Casting.h"
44 #include "llvm/Support/Compiler.h"
45 #include "llvm/Support/Debug.h"
46 #include "llvm/Support/ErrorHandling.h"
47 #include "llvm/Support/raw_ostream.h"
48 #include <cassert>
49 #include <tuple>
50 #include <vector>
51 
52 using namespace llvm;
53 
54 #define DEBUG_TYPE "regalloc"
55 
56 STATISTIC(NumStores, "Number of stores added");
57 STATISTIC(NumLoads , "Number of loads added");
58 STATISTIC(NumCoalesced, "Number of copies coalesced");
59 
60 // FIXME: Remove this switch when all testcases are fixed!
61 static cl::opt<bool> IgnoreMissingDefs("rafast-ignore-missing-defs",
62                                        cl::Hidden);
63 
64 static RegisterRegAlloc
65   fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
66 
67 namespace {
68 
69   class RegAllocFast : public MachineFunctionPass {
70   public:
71     static char ID;
72 
73     RegAllocFast(const RegClassFilterFunc F = allocateAllRegClasses,
74                  bool ClearVirtRegs_ = true) :
75       MachineFunctionPass(ID),
76       ShouldAllocateClass(F),
77       StackSlotForVirtReg(-1),
78       ClearVirtRegs(ClearVirtRegs_) {
79     }
80 
81   private:
82     MachineFrameInfo *MFI;
83     MachineRegisterInfo *MRI;
84     const TargetRegisterInfo *TRI;
85     const TargetInstrInfo *TII;
86     RegisterClassInfo RegClassInfo;
87     const RegClassFilterFunc ShouldAllocateClass;
88 
89     /// Basic block currently being allocated.
90     MachineBasicBlock *MBB;
91 
92     /// Maps virtual regs to the frame index where these values are spilled.
93     IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
94 
95     bool ClearVirtRegs;
96 
97     /// Everything we know about a live virtual register.
98     struct LiveReg {
99       MachineInstr *LastUse = nullptr; ///< Last instr to use reg.
100       Register VirtReg;                ///< Virtual register number.
101       MCPhysReg PhysReg = 0;           ///< Currently held here.
102       bool LiveOut = false;            ///< Register is possibly live out.
103       bool Reloaded = false;           ///< Register was reloaded.
104       bool Error = false;              ///< Could not allocate.
105 
106       explicit LiveReg(Register VirtReg) : VirtReg(VirtReg) {}
107 
108       unsigned getSparseSetIndex() const {
109         return Register::virtReg2Index(VirtReg);
110       }
111     };
112 
113     using LiveRegMap = SparseSet<LiveReg>;
114     /// This map contains entries for each virtual register that is currently
115     /// available in a physical register.
116     LiveRegMap LiveVirtRegs;
117 
118     /// Stores assigned virtual registers present in the bundle MI.
119     DenseMap<Register, MCPhysReg> BundleVirtRegsMap;
120 
121     DenseMap<unsigned, SmallVector<MachineOperand *, 2>> LiveDbgValueMap;
122     /// List of DBG_VALUE that we encountered without the vreg being assigned
123     /// because they were placed after the last use of the vreg.
124     DenseMap<unsigned, SmallVector<MachineInstr *, 1>> DanglingDbgValues;
125 
126     /// Has a bit set for every virtual register for which it was determined
127     /// that it is alive across blocks.
128     BitVector MayLiveAcrossBlocks;
129 
130     /// State of a register unit.
131     enum RegUnitState {
132       /// A free register is not currently in use and can be allocated
133       /// immediately without checking aliases.
134       regFree,
135 
136       /// A pre-assigned register has been assigned before register allocation
137       /// (e.g., setting up a call parameter).
138       regPreAssigned,
139 
140       /// Used temporarily in reloadAtBegin() to mark register units that are
141       /// live-in to the basic block.
142       regLiveIn,
143 
144       /// A register state may also be a virtual register number, indication
145       /// that the physical register is currently allocated to a virtual
146       /// register. In that case, LiveVirtRegs contains the inverse mapping.
147     };
148 
149     /// Maps each physical register to a RegUnitState enum or virtual register.
150     std::vector<unsigned> RegUnitStates;
151 
152     SmallVector<MachineInstr *, 32> Coalesced;
153 
154     using RegUnitSet = SparseSet<uint16_t, identity<uint16_t>>;
155     /// Set of register units that are used in the current instruction, and so
156     /// cannot be allocated.
157     RegUnitSet UsedInInstr;
158     RegUnitSet PhysRegUses;
159     SmallVector<uint16_t, 8> DefOperandIndexes;
160     // Register masks attached to the current instruction.
161     SmallVector<const uint32_t *> RegMasks;
162 
163     void setPhysRegState(MCPhysReg PhysReg, unsigned NewState);
164     bool isPhysRegFree(MCPhysReg PhysReg) const;
165 
166     /// Mark a physreg as used in this instruction.
167     void markRegUsedInInstr(MCPhysReg PhysReg) {
168       for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
169         UsedInInstr.insert(*Units);
170     }
171 
172     // Check if physreg is clobbered by instruction's regmask(s).
173     bool isClobberedByRegMasks(MCPhysReg PhysReg) const {
174       return llvm::any_of(RegMasks, [PhysReg](const uint32_t *Mask) {
175         return MachineOperand::clobbersPhysReg(Mask, PhysReg);
176       });
177     }
178 
179     /// Check if a physreg or any of its aliases are used in this instruction.
180     bool isRegUsedInInstr(MCPhysReg PhysReg, bool LookAtPhysRegUses) const {
181       if (LookAtPhysRegUses && isClobberedByRegMasks(PhysReg))
182         return true;
183       for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
184         if (UsedInInstr.count(*Units))
185           return true;
186         if (LookAtPhysRegUses && PhysRegUses.count(*Units))
187           return true;
188       }
189       return false;
190     }
191 
192     /// Mark physical register as being used in a register use operand.
193     /// This is only used by the special livethrough handling code.
194     void markPhysRegUsedInInstr(MCPhysReg PhysReg) {
195       for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
196         PhysRegUses.insert(*Units);
197     }
198 
199     /// Remove mark of physical register being used in the instruction.
200     void unmarkRegUsedInInstr(MCPhysReg PhysReg) {
201       for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
202         UsedInInstr.erase(*Units);
203     }
204 
205     enum : unsigned {
206       spillClean = 50,
207       spillDirty = 100,
208       spillPrefBonus = 20,
209       spillImpossible = ~0u
210     };
211 
212   public:
213     StringRef getPassName() const override { return "Fast Register Allocator"; }
214 
215     void getAnalysisUsage(AnalysisUsage &AU) const override {
216       AU.setPreservesCFG();
217       MachineFunctionPass::getAnalysisUsage(AU);
218     }
219 
220     MachineFunctionProperties getRequiredProperties() const override {
221       return MachineFunctionProperties().set(
222           MachineFunctionProperties::Property::NoPHIs);
223     }
224 
225     MachineFunctionProperties getSetProperties() const override {
226       if (ClearVirtRegs) {
227         return MachineFunctionProperties().set(
228           MachineFunctionProperties::Property::NoVRegs);
229       }
230 
231       return MachineFunctionProperties();
232     }
233 
234     MachineFunctionProperties getClearedProperties() const override {
235       return MachineFunctionProperties().set(
236         MachineFunctionProperties::Property::IsSSA);
237     }
238 
239   private:
240     bool runOnMachineFunction(MachineFunction &MF) override;
241 
242     void allocateBasicBlock(MachineBasicBlock &MBB);
243 
244     void addRegClassDefCounts(std::vector<unsigned> &RegClassDefCounts,
245                               Register Reg) const;
246 
247     void allocateInstruction(MachineInstr &MI);
248     void handleDebugValue(MachineInstr &MI);
249     void handleBundle(MachineInstr &MI);
250 
251     bool usePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
252     bool definePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
253     bool displacePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
254     void freePhysReg(MCPhysReg PhysReg);
255 
256     unsigned calcSpillCost(MCPhysReg PhysReg) const;
257 
258     LiveRegMap::iterator findLiveVirtReg(Register VirtReg) {
259       return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
260     }
261 
262     LiveRegMap::const_iterator findLiveVirtReg(Register VirtReg) const {
263       return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
264     }
265 
266     void assignVirtToPhysReg(MachineInstr &MI, LiveReg &, MCPhysReg PhysReg);
267     void allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint,
268                       bool LookAtPhysRegUses = false);
269     void allocVirtRegUndef(MachineOperand &MO);
270     void assignDanglingDebugValues(MachineInstr &Def, Register VirtReg,
271                                    MCPhysReg Reg);
272     void defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
273                                   Register VirtReg);
274     void defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,
275                        bool LookAtPhysRegUses = false);
276     void useVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg);
277 
278     MachineBasicBlock::iterator
279     getMBBBeginInsertionPoint(MachineBasicBlock &MBB,
280                               SmallSet<Register, 2> &PrologLiveIns) const;
281 
282     void reloadAtBegin(MachineBasicBlock &MBB);
283     void setPhysReg(MachineInstr &MI, MachineOperand &MO, MCPhysReg PhysReg);
284 
285     Register traceCopies(Register VirtReg) const;
286     Register traceCopyChain(Register Reg) const;
287 
288     int getStackSpaceFor(Register VirtReg);
289     void spill(MachineBasicBlock::iterator Before, Register VirtReg,
290                MCPhysReg AssignedReg, bool Kill, bool LiveOut);
291     void reload(MachineBasicBlock::iterator Before, Register VirtReg,
292                 MCPhysReg PhysReg);
293 
294     bool mayLiveOut(Register VirtReg);
295     bool mayLiveIn(Register VirtReg);
296 
297     void dumpState() const;
298   };
299 
300 } // end anonymous namespace
301 
302 char RegAllocFast::ID = 0;
303 
304 INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false,
305                 false)
306 
307 void RegAllocFast::setPhysRegState(MCPhysReg PhysReg, unsigned NewState) {
308   for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI)
309     RegUnitStates[*UI] = NewState;
310 }
311 
312 bool RegAllocFast::isPhysRegFree(MCPhysReg PhysReg) const {
313   for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
314     if (RegUnitStates[*UI] != regFree)
315       return false;
316   }
317   return true;
318 }
319 
320 /// This allocates space for the specified virtual register to be held on the
321 /// stack.
322 int RegAllocFast::getStackSpaceFor(Register VirtReg) {
323   // Find the location Reg would belong...
324   int SS = StackSlotForVirtReg[VirtReg];
325   // Already has space allocated?
326   if (SS != -1)
327     return SS;
328 
329   // Allocate a new stack object for this spill location...
330   const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
331   unsigned Size = TRI->getSpillSize(RC);
332   Align Alignment = TRI->getSpillAlign(RC);
333   int FrameIdx = MFI->CreateSpillStackObject(Size, Alignment);
334 
335   // Assign the slot.
336   StackSlotForVirtReg[VirtReg] = FrameIdx;
337   return FrameIdx;
338 }
339 
340 static bool dominates(MachineBasicBlock &MBB,
341                       MachineBasicBlock::const_iterator A,
342                       MachineBasicBlock::const_iterator B) {
343   auto MBBEnd = MBB.end();
344   if (B == MBBEnd)
345     return true;
346 
347   MachineBasicBlock::const_iterator I = MBB.begin();
348   for (; &*I != A && &*I != B; ++I)
349     ;
350 
351   return &*I == A;
352 }
353 
354 /// Returns false if \p VirtReg is known to not live out of the current block.
355 bool RegAllocFast::mayLiveOut(Register VirtReg) {
356   if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg))) {
357     // Cannot be live-out if there are no successors.
358     return !MBB->succ_empty();
359   }
360 
361   const MachineInstr *SelfLoopDef = nullptr;
362 
363   // If this block loops back to itself, it is necessary to check whether the
364   // use comes after the def.
365   if (MBB->isSuccessor(MBB)) {
366     SelfLoopDef = MRI->getUniqueVRegDef(VirtReg);
367     if (!SelfLoopDef) {
368       MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
369       return true;
370     }
371   }
372 
373   // See if the first \p Limit uses of the register are all in the current
374   // block.
375   static const unsigned Limit = 8;
376   unsigned C = 0;
377   for (const MachineInstr &UseInst : MRI->use_nodbg_instructions(VirtReg)) {
378     if (UseInst.getParent() != MBB || ++C >= Limit) {
379       MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
380       // Cannot be live-out if there are no successors.
381       return !MBB->succ_empty();
382     }
383 
384     if (SelfLoopDef) {
385       // Try to handle some simple cases to avoid spilling and reloading every
386       // value inside a self looping block.
387       if (SelfLoopDef == &UseInst ||
388           !dominates(*MBB, SelfLoopDef->getIterator(), UseInst.getIterator())) {
389         MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
390         return true;
391       }
392     }
393   }
394 
395   return false;
396 }
397 
398 /// Returns false if \p VirtReg is known to not be live into the current block.
399 bool RegAllocFast::mayLiveIn(Register VirtReg) {
400   if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg)))
401     return !MBB->pred_empty();
402 
403   // See if the first \p Limit def of the register are all in the current block.
404   static const unsigned Limit = 8;
405   unsigned C = 0;
406   for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {
407     if (DefInst.getParent() != MBB || ++C >= Limit) {
408       MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
409       return !MBB->pred_empty();
410     }
411   }
412 
413   return false;
414 }
415 
416 /// Insert spill instruction for \p AssignedReg before \p Before. Update
417 /// DBG_VALUEs with \p VirtReg operands with the stack slot.
418 void RegAllocFast::spill(MachineBasicBlock::iterator Before, Register VirtReg,
419                          MCPhysReg AssignedReg, bool Kill, bool LiveOut) {
420   LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI)
421                     << " in " << printReg(AssignedReg, TRI));
422   int FI = getStackSpaceFor(VirtReg);
423   LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n');
424 
425   const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
426   TII->storeRegToStackSlot(*MBB, Before, AssignedReg, Kill, FI, &RC, TRI);
427   ++NumStores;
428 
429   MachineBasicBlock::iterator FirstTerm = MBB->getFirstTerminator();
430 
431   // When we spill a virtual register, we will have spill instructions behind
432   // every definition of it, meaning we can switch all the DBG_VALUEs over
433   // to just reference the stack slot.
434   SmallVectorImpl<MachineOperand *> &LRIDbgOperands = LiveDbgValueMap[VirtReg];
435   SmallDenseMap<MachineInstr *, SmallVector<const MachineOperand *>>
436       SpilledOperandsMap;
437   for (MachineOperand *MO : LRIDbgOperands)
438     SpilledOperandsMap[MO->getParent()].push_back(MO);
439   for (auto MISpilledOperands : SpilledOperandsMap) {
440     MachineInstr &DBG = *MISpilledOperands.first;
441     MachineInstr *NewDV = buildDbgValueForSpill(
442         *MBB, Before, *MISpilledOperands.first, FI, MISpilledOperands.second);
443     assert(NewDV->getParent() == MBB && "dangling parent pointer");
444     (void)NewDV;
445     LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);
446 
447     if (LiveOut) {
448       // We need to insert a DBG_VALUE at the end of the block if the spill slot
449       // is live out, but there is another use of the value after the
450       // spill. This will allow LiveDebugValues to see the correct live out
451       // value to propagate to the successors.
452       MachineInstr *ClonedDV = MBB->getParent()->CloneMachineInstr(NewDV);
453       MBB->insert(FirstTerm, ClonedDV);
454       LLVM_DEBUG(dbgs() << "Cloning debug info due to live out spill\n");
455     }
456 
457     // Rewrite unassigned dbg_values to use the stack slot.
458     // TODO We can potentially do this for list debug values as well if we know
459     // how the dbg_values are getting unassigned.
460     if (DBG.isNonListDebugValue()) {
461       MachineOperand &MO = DBG.getDebugOperand(0);
462       if (MO.isReg() && MO.getReg() == 0) {
463         updateDbgValueForSpill(DBG, FI, 0);
464       }
465     }
466   }
467   // Now this register is spilled there is should not be any DBG_VALUE
468   // pointing to this register because they are all pointing to spilled value
469   // now.
470   LRIDbgOperands.clear();
471 }
472 
473 /// Insert reload instruction for \p PhysReg before \p Before.
474 void RegAllocFast::reload(MachineBasicBlock::iterator Before, Register VirtReg,
475                           MCPhysReg PhysReg) {
476   LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
477                     << printReg(PhysReg, TRI) << '\n');
478   int FI = getStackSpaceFor(VirtReg);
479   const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
480   TII->loadRegFromStackSlot(*MBB, Before, PhysReg, FI, &RC, TRI);
481   ++NumLoads;
482 }
483 
484 /// Get basic block begin insertion point.
485 /// This is not just MBB.begin() because surprisingly we have EH_LABEL
486 /// instructions marking the begin of a basic block. This means we must insert
487 /// new instructions after such labels...
488 MachineBasicBlock::iterator
489 RegAllocFast::getMBBBeginInsertionPoint(
490   MachineBasicBlock &MBB, SmallSet<Register, 2> &PrologLiveIns) const {
491   MachineBasicBlock::iterator I = MBB.begin();
492   while (I != MBB.end()) {
493     if (I->isLabel()) {
494       ++I;
495       continue;
496     }
497 
498     // Most reloads should be inserted after prolog instructions.
499     if (!TII->isBasicBlockPrologue(*I))
500       break;
501 
502     // However if a prolog instruction reads a register that needs to be
503     // reloaded, the reload should be inserted before the prolog.
504     for (MachineOperand &MO : I->operands()) {
505       if (MO.isReg())
506         PrologLiveIns.insert(MO.getReg());
507     }
508 
509     ++I;
510   }
511 
512   return I;
513 }
514 
515 /// Reload all currently assigned virtual registers.
516 void RegAllocFast::reloadAtBegin(MachineBasicBlock &MBB) {
517   if (LiveVirtRegs.empty())
518     return;
519 
520   for (MachineBasicBlock::RegisterMaskPair P : MBB.liveins()) {
521     MCPhysReg Reg = P.PhysReg;
522     // Set state to live-in. This possibly overrides mappings to virtual
523     // registers but we don't care anymore at this point.
524     setPhysRegState(Reg, regLiveIn);
525   }
526 
527 
528   SmallSet<Register, 2> PrologLiveIns;
529 
530   // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
531   // of spilling here is deterministic, if arbitrary.
532   MachineBasicBlock::iterator InsertBefore
533     = getMBBBeginInsertionPoint(MBB, PrologLiveIns);
534   for (const LiveReg &LR : LiveVirtRegs) {
535     MCPhysReg PhysReg = LR.PhysReg;
536     if (PhysReg == 0)
537       continue;
538 
539     MCRegister FirstUnit = *MCRegUnitIterator(PhysReg, TRI);
540     if (RegUnitStates[FirstUnit] == regLiveIn)
541       continue;
542 
543     assert((&MBB != &MBB.getParent()->front() || IgnoreMissingDefs) &&
544            "no reload in start block. Missing vreg def?");
545 
546     if (PrologLiveIns.count(PhysReg)) {
547       // FIXME: Theoretically this should use an insert point skipping labels
548       // but I'm not sure how labels should interact with prolog instruction
549       // that need reloads.
550       reload(MBB.begin(), LR.VirtReg, PhysReg);
551     } else
552       reload(InsertBefore, LR.VirtReg, PhysReg);
553   }
554   LiveVirtRegs.clear();
555 }
556 
557 /// Handle the direct use of a physical register.  Check that the register is
558 /// not used by a virtreg. Kill the physreg, marking it free. This may add
559 /// implicit kills to MO->getParent() and invalidate MO.
560 bool RegAllocFast::usePhysReg(MachineInstr &MI, MCPhysReg Reg) {
561   assert(Register::isPhysicalRegister(Reg) && "expected physreg");
562   bool displacedAny = displacePhysReg(MI, Reg);
563   setPhysRegState(Reg, regPreAssigned);
564   markRegUsedInInstr(Reg);
565   return displacedAny;
566 }
567 
568 bool RegAllocFast::definePhysReg(MachineInstr &MI, MCPhysReg Reg) {
569   bool displacedAny = displacePhysReg(MI, Reg);
570   setPhysRegState(Reg, regPreAssigned);
571   return displacedAny;
572 }
573 
574 /// Mark PhysReg as reserved or free after spilling any virtregs. This is very
575 /// similar to defineVirtReg except the physreg is reserved instead of
576 /// allocated.
577 bool RegAllocFast::displacePhysReg(MachineInstr &MI, MCPhysReg PhysReg) {
578   bool displacedAny = false;
579 
580   for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
581     unsigned Unit = *UI;
582     switch (unsigned VirtReg = RegUnitStates[Unit]) {
583     default: {
584       LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
585       assert(LRI != LiveVirtRegs.end() && "datastructures in sync");
586       MachineBasicBlock::iterator ReloadBefore =
587           std::next((MachineBasicBlock::iterator)MI.getIterator());
588       reload(ReloadBefore, VirtReg, LRI->PhysReg);
589 
590       setPhysRegState(LRI->PhysReg, regFree);
591       LRI->PhysReg = 0;
592       LRI->Reloaded = true;
593       displacedAny = true;
594       break;
595     }
596     case regPreAssigned:
597       RegUnitStates[Unit] = regFree;
598       displacedAny = true;
599       break;
600     case regFree:
601       break;
602     }
603   }
604   return displacedAny;
605 }
606 
607 void RegAllocFast::freePhysReg(MCPhysReg PhysReg) {
608   LLVM_DEBUG(dbgs() << "Freeing " << printReg(PhysReg, TRI) << ':');
609 
610   MCRegister FirstUnit = *MCRegUnitIterator(PhysReg, TRI);
611   switch (unsigned VirtReg = RegUnitStates[FirstUnit]) {
612   case regFree:
613     LLVM_DEBUG(dbgs() << '\n');
614     return;
615   case regPreAssigned:
616     LLVM_DEBUG(dbgs() << '\n');
617     setPhysRegState(PhysReg, regFree);
618     return;
619   default: {
620       LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
621       assert(LRI != LiveVirtRegs.end());
622       LLVM_DEBUG(dbgs() << ' ' << printReg(LRI->VirtReg, TRI) << '\n');
623       setPhysRegState(LRI->PhysReg, regFree);
624       LRI->PhysReg = 0;
625     }
626     return;
627   }
628 }
629 
630 /// Return the cost of spilling clearing out PhysReg and aliases so it is free
631 /// for allocation. Returns 0 when PhysReg is free or disabled with all aliases
632 /// disabled - it can be allocated directly.
633 /// \returns spillImpossible when PhysReg or an alias can't be spilled.
634 unsigned RegAllocFast::calcSpillCost(MCPhysReg PhysReg) const {
635   for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
636     switch (unsigned VirtReg = RegUnitStates[*UI]) {
637     case regFree:
638       break;
639     case regPreAssigned:
640       LLVM_DEBUG(dbgs() << "Cannot spill pre-assigned "
641                         << printReg(PhysReg, TRI) << '\n');
642       return spillImpossible;
643     default: {
644       bool SureSpill = StackSlotForVirtReg[VirtReg] != -1 ||
645                        findLiveVirtReg(VirtReg)->LiveOut;
646       return SureSpill ? spillClean : spillDirty;
647     }
648     }
649   }
650   return 0;
651 }
652 
653 void RegAllocFast::assignDanglingDebugValues(MachineInstr &Definition,
654                                              Register VirtReg, MCPhysReg Reg) {
655   auto UDBGValIter = DanglingDbgValues.find(VirtReg);
656   if (UDBGValIter == DanglingDbgValues.end())
657     return;
658 
659   SmallVectorImpl<MachineInstr*> &Dangling = UDBGValIter->second;
660   for (MachineInstr *DbgValue : Dangling) {
661     assert(DbgValue->isDebugValue());
662     if (!DbgValue->hasDebugOperandForReg(VirtReg))
663       continue;
664 
665     // Test whether the physreg survives from the definition to the DBG_VALUE.
666     MCPhysReg SetToReg = Reg;
667     unsigned Limit = 20;
668     for (MachineBasicBlock::iterator I = std::next(Definition.getIterator()),
669          E = DbgValue->getIterator(); I != E; ++I) {
670       if (I->modifiesRegister(Reg, TRI) || --Limit == 0) {
671         LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue
672                    << '\n');
673         SetToReg = 0;
674         break;
675       }
676     }
677     for (MachineOperand &MO : DbgValue->getDebugOperandsForReg(VirtReg)) {
678       MO.setReg(SetToReg);
679       if (SetToReg != 0)
680         MO.setIsRenamable();
681     }
682   }
683   Dangling.clear();
684 }
685 
686 /// This method updates local state so that we know that PhysReg is the
687 /// proper container for VirtReg now.  The physical register must not be used
688 /// for anything else when this is called.
689 void RegAllocFast::assignVirtToPhysReg(MachineInstr &AtMI, LiveReg &LR,
690                                        MCPhysReg PhysReg) {
691   Register VirtReg = LR.VirtReg;
692   LLVM_DEBUG(dbgs() << "Assigning " << printReg(VirtReg, TRI) << " to "
693                     << printReg(PhysReg, TRI) << '\n');
694   assert(LR.PhysReg == 0 && "Already assigned a physreg");
695   assert(PhysReg != 0 && "Trying to assign no register");
696   LR.PhysReg = PhysReg;
697   setPhysRegState(PhysReg, VirtReg);
698 
699   assignDanglingDebugValues(AtMI, VirtReg, PhysReg);
700 }
701 
702 static bool isCoalescable(const MachineInstr &MI) {
703   return MI.isFullCopy();
704 }
705 
706 Register RegAllocFast::traceCopyChain(Register Reg) const {
707   static const unsigned ChainLengthLimit = 3;
708   unsigned C = 0;
709   do {
710     if (Reg.isPhysical())
711       return Reg;
712     assert(Reg.isVirtual());
713 
714     MachineInstr *VRegDef = MRI->getUniqueVRegDef(Reg);
715     if (!VRegDef || !isCoalescable(*VRegDef))
716       return 0;
717     Reg = VRegDef->getOperand(1).getReg();
718   } while (++C <= ChainLengthLimit);
719   return 0;
720 }
721 
722 /// Check if any of \p VirtReg's definitions is a copy. If it is follow the
723 /// chain of copies to check whether we reach a physical register we can
724 /// coalesce with.
725 Register RegAllocFast::traceCopies(Register VirtReg) const {
726   static const unsigned DefLimit = 3;
727   unsigned C = 0;
728   for (const MachineInstr &MI : MRI->def_instructions(VirtReg)) {
729     if (isCoalescable(MI)) {
730       Register Reg = MI.getOperand(1).getReg();
731       Reg = traceCopyChain(Reg);
732       if (Reg.isValid())
733         return Reg;
734     }
735 
736     if (++C >= DefLimit)
737       break;
738   }
739   return Register();
740 }
741 
742 /// Allocates a physical register for VirtReg.
743 void RegAllocFast::allocVirtReg(MachineInstr &MI, LiveReg &LR,
744                                 Register Hint0, bool LookAtPhysRegUses) {
745   const Register VirtReg = LR.VirtReg;
746   assert(LR.PhysReg == 0);
747 
748   const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
749   LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg)
750                     << " in class " << TRI->getRegClassName(&RC)
751                     << " with hint " << printReg(Hint0, TRI) << '\n');
752 
753   // Take hint when possible.
754   if (Hint0.isPhysical() && MRI->isAllocatable(Hint0) && RC.contains(Hint0) &&
755       !isRegUsedInInstr(Hint0, LookAtPhysRegUses)) {
756     // Take hint if the register is currently free.
757     if (isPhysRegFree(Hint0)) {
758       LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
759                         << '\n');
760       assignVirtToPhysReg(MI, LR, Hint0);
761       return;
762     } else {
763       LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint0, TRI)
764                         << " occupied\n");
765     }
766   } else {
767     Hint0 = Register();
768   }
769 
770 
771   // Try other hint.
772   Register Hint1 = traceCopies(VirtReg);
773   if (Hint1.isPhysical() && MRI->isAllocatable(Hint1) && RC.contains(Hint1) &&
774       !isRegUsedInInstr(Hint1, LookAtPhysRegUses)) {
775     // Take hint if the register is currently free.
776     if (isPhysRegFree(Hint1)) {
777       LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
778                  << '\n');
779       assignVirtToPhysReg(MI, LR, Hint1);
780       return;
781     } else {
782       LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint1, TRI)
783                  << " occupied\n");
784     }
785   } else {
786     Hint1 = Register();
787   }
788 
789   MCPhysReg BestReg = 0;
790   unsigned BestCost = spillImpossible;
791   ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
792   for (MCPhysReg PhysReg : AllocationOrder) {
793     LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << ' ');
794     if (isRegUsedInInstr(PhysReg, LookAtPhysRegUses)) {
795       LLVM_DEBUG(dbgs() << "already used in instr.\n");
796       continue;
797     }
798 
799     unsigned Cost = calcSpillCost(PhysReg);
800     LLVM_DEBUG(dbgs() << "Cost: " << Cost << " BestCost: " << BestCost << '\n');
801     // Immediate take a register with cost 0.
802     if (Cost == 0) {
803       assignVirtToPhysReg(MI, LR, PhysReg);
804       return;
805     }
806 
807     if (PhysReg == Hint0 || PhysReg == Hint1)
808       Cost -= spillPrefBonus;
809 
810     if (Cost < BestCost) {
811       BestReg = PhysReg;
812       BestCost = Cost;
813     }
814   }
815 
816   if (!BestReg) {
817     // Nothing we can do: Report an error and keep going with an invalid
818     // allocation.
819     if (MI.isInlineAsm())
820       MI.emitError("inline assembly requires more registers than available");
821     else
822       MI.emitError("ran out of registers during register allocation");
823 
824     LR.Error = true;
825     LR.PhysReg = 0;
826     return;
827   }
828 
829   displacePhysReg(MI, BestReg);
830   assignVirtToPhysReg(MI, LR, BestReg);
831 }
832 
833 void RegAllocFast::allocVirtRegUndef(MachineOperand &MO) {
834   assert(MO.isUndef() && "expected undef use");
835   Register VirtReg = MO.getReg();
836   assert(Register::isVirtualRegister(VirtReg) && "Expected virtreg");
837 
838   LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
839   MCPhysReg PhysReg;
840   if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
841     PhysReg = LRI->PhysReg;
842   } else {
843     const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
844     ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
845     assert(!AllocationOrder.empty() && "Allocation order must not be empty");
846     PhysReg = AllocationOrder[0];
847   }
848 
849   unsigned SubRegIdx = MO.getSubReg();
850   if (SubRegIdx != 0) {
851     PhysReg = TRI->getSubReg(PhysReg, SubRegIdx);
852     MO.setSubReg(0);
853   }
854   MO.setReg(PhysReg);
855   MO.setIsRenamable(true);
856 }
857 
858 /// Variation of defineVirtReg() with special handling for livethrough regs
859 /// (tied or earlyclobber) that may interfere with preassigned uses.
860 void RegAllocFast::defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
861                                             Register VirtReg) {
862   LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
863   if (LRI != LiveVirtRegs.end()) {
864     MCPhysReg PrevReg = LRI->PhysReg;
865     if (PrevReg != 0 && isRegUsedInInstr(PrevReg, true)) {
866       LLVM_DEBUG(dbgs() << "Need new assignment for " << printReg(PrevReg, TRI)
867                         << " (tied/earlyclobber resolution)\n");
868       freePhysReg(PrevReg);
869       LRI->PhysReg = 0;
870       allocVirtReg(MI, *LRI, 0, true);
871       MachineBasicBlock::iterator InsertBefore =
872         std::next((MachineBasicBlock::iterator)MI.getIterator());
873       LLVM_DEBUG(dbgs() << "Copy " << printReg(LRI->PhysReg, TRI) << " to "
874                         << printReg(PrevReg, TRI) << '\n');
875       BuildMI(*MBB, InsertBefore, MI.getDebugLoc(),
876               TII->get(TargetOpcode::COPY), PrevReg)
877         .addReg(LRI->PhysReg, llvm::RegState::Kill);
878     }
879     MachineOperand &MO = MI.getOperand(OpNum);
880     if (MO.getSubReg() && !MO.isUndef()) {
881       LRI->LastUse = &MI;
882     }
883   }
884   return defineVirtReg(MI, OpNum, VirtReg, true);
885 }
886 
887 /// Allocates a register for VirtReg definition. Typically the register is
888 /// already assigned from a use of the virtreg, however we still need to
889 /// perform an allocation if:
890 /// - It is a dead definition without any uses.
891 /// - The value is live out and all uses are in different basic blocks.
892 void RegAllocFast::defineVirtReg(MachineInstr &MI, unsigned OpNum,
893                                  Register VirtReg, bool LookAtPhysRegUses) {
894   assert(VirtReg.isVirtual() && "Not a virtual register");
895   MachineOperand &MO = MI.getOperand(OpNum);
896   LiveRegMap::iterator LRI;
897   bool New;
898   std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
899   if (New) {
900     if (!MO.isDead()) {
901       if (mayLiveOut(VirtReg)) {
902         LRI->LiveOut = true;
903       } else {
904         // It is a dead def without the dead flag; add the flag now.
905         MO.setIsDead(true);
906       }
907     }
908   }
909   if (LRI->PhysReg == 0)
910     allocVirtReg(MI, *LRI, 0, LookAtPhysRegUses);
911   else {
912     assert(!isRegUsedInInstr(LRI->PhysReg, LookAtPhysRegUses) &&
913            "TODO: preassign mismatch");
914     LLVM_DEBUG(dbgs() << "In def of " << printReg(VirtReg, TRI)
915                       << " use existing assignment to "
916                       << printReg(LRI->PhysReg, TRI) << '\n');
917   }
918 
919   MCPhysReg PhysReg = LRI->PhysReg;
920   assert(PhysReg != 0 && "Register not assigned");
921   if (LRI->Reloaded || LRI->LiveOut) {
922     if (!MI.isImplicitDef()) {
923       MachineBasicBlock::iterator SpillBefore =
924           std::next((MachineBasicBlock::iterator)MI.getIterator());
925       LLVM_DEBUG(dbgs() << "Spill Reason: LO: " << LRI->LiveOut << " RL: "
926                         << LRI->Reloaded << '\n');
927       bool Kill = LRI->LastUse == nullptr;
928       spill(SpillBefore, VirtReg, PhysReg, Kill, LRI->LiveOut);
929       LRI->LastUse = nullptr;
930     }
931     LRI->LiveOut = false;
932     LRI->Reloaded = false;
933   }
934   if (MI.getOpcode() == TargetOpcode::BUNDLE) {
935     BundleVirtRegsMap[VirtReg] = PhysReg;
936   }
937   markRegUsedInInstr(PhysReg);
938   setPhysReg(MI, MO, PhysReg);
939 }
940 
941 /// Allocates a register for a VirtReg use.
942 void RegAllocFast::useVirtReg(MachineInstr &MI, unsigned OpNum,
943                               Register VirtReg) {
944   assert(VirtReg.isVirtual() && "Not a virtual register");
945   MachineOperand &MO = MI.getOperand(OpNum);
946   LiveRegMap::iterator LRI;
947   bool New;
948   std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
949   if (New) {
950     MachineOperand &MO = MI.getOperand(OpNum);
951     if (!MO.isKill()) {
952       if (mayLiveOut(VirtReg)) {
953         LRI->LiveOut = true;
954       } else {
955         // It is a last (killing) use without the kill flag; add the flag now.
956         MO.setIsKill(true);
957       }
958     }
959   } else {
960     assert((!MO.isKill() || LRI->LastUse == &MI) && "Invalid kill flag");
961   }
962 
963   // If necessary allocate a register.
964   if (LRI->PhysReg == 0) {
965     assert(!MO.isTied() && "tied op should be allocated");
966     Register Hint;
967     if (MI.isCopy() && MI.getOperand(1).getSubReg() == 0) {
968       Hint = MI.getOperand(0).getReg();
969       assert(Hint.isPhysical() &&
970              "Copy destination should already be assigned");
971     }
972     allocVirtReg(MI, *LRI, Hint, false);
973     if (LRI->Error) {
974       const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
975       ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
976       setPhysReg(MI, MO, *AllocationOrder.begin());
977       return;
978     }
979   }
980 
981   LRI->LastUse = &MI;
982 
983   if (MI.getOpcode() == TargetOpcode::BUNDLE) {
984     BundleVirtRegsMap[VirtReg] = LRI->PhysReg;
985   }
986   markRegUsedInInstr(LRI->PhysReg);
987   setPhysReg(MI, MO, LRI->PhysReg);
988 }
989 
990 /// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This
991 /// may invalidate any operand pointers.  Return true if the operand kills its
992 /// register.
993 void RegAllocFast::setPhysReg(MachineInstr &MI, MachineOperand &MO,
994                               MCPhysReg PhysReg) {
995   if (!MO.getSubReg()) {
996     MO.setReg(PhysReg);
997     MO.setIsRenamable(true);
998     return;
999   }
1000 
1001   // Handle subregister index.
1002   MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : MCRegister());
1003   MO.setIsRenamable(true);
1004   // Note: We leave the subreg number around a little longer in case of defs.
1005   // This is so that the register freeing logic in allocateInstruction can still
1006   // recognize this as subregister defs. The code there will clear the number.
1007   if (!MO.isDef())
1008     MO.setSubReg(0);
1009 
1010   // A kill flag implies killing the full register. Add corresponding super
1011   // register kill.
1012   if (MO.isKill()) {
1013     MI.addRegisterKilled(PhysReg, TRI, true);
1014     return;
1015   }
1016 
1017   // A <def,read-undef> of a sub-register requires an implicit def of the full
1018   // register.
1019   if (MO.isDef() && MO.isUndef()) {
1020     if (MO.isDead())
1021       MI.addRegisterDead(PhysReg, TRI, true);
1022     else
1023       MI.addRegisterDefined(PhysReg, TRI);
1024   }
1025 }
1026 
1027 #ifndef NDEBUG
1028 
1029 void RegAllocFast::dumpState() const {
1030   for (unsigned Unit = 1, UnitE = TRI->getNumRegUnits(); Unit != UnitE;
1031        ++Unit) {
1032     switch (unsigned VirtReg = RegUnitStates[Unit]) {
1033     case regFree:
1034       break;
1035     case regPreAssigned:
1036       dbgs() << " " << printRegUnit(Unit, TRI) << "[P]";
1037       break;
1038     case regLiveIn:
1039       llvm_unreachable("Should not have regLiveIn in map");
1040     default: {
1041       dbgs() << ' ' << printRegUnit(Unit, TRI) << '=' << printReg(VirtReg);
1042       LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
1043       assert(I != LiveVirtRegs.end() && "have LiveVirtRegs entry");
1044       if (I->LiveOut || I->Reloaded) {
1045         dbgs() << '[';
1046         if (I->LiveOut) dbgs() << 'O';
1047         if (I->Reloaded) dbgs() << 'R';
1048         dbgs() << ']';
1049       }
1050       assert(TRI->hasRegUnit(I->PhysReg, Unit) && "inverse mapping present");
1051       break;
1052     }
1053     }
1054   }
1055   dbgs() << '\n';
1056   // Check that LiveVirtRegs is the inverse.
1057   for (const LiveReg &LR : LiveVirtRegs) {
1058     Register VirtReg = LR.VirtReg;
1059     assert(VirtReg.isVirtual() && "Bad map key");
1060     MCPhysReg PhysReg = LR.PhysReg;
1061     if (PhysReg != 0) {
1062       assert(Register::isPhysicalRegister(PhysReg) &&
1063              "mapped to physreg");
1064       for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
1065         assert(RegUnitStates[*UI] == VirtReg && "inverse map valid");
1066       }
1067     }
1068   }
1069 }
1070 #endif
1071 
1072 /// Count number of defs consumed from each register class by \p Reg
1073 void RegAllocFast::addRegClassDefCounts(std::vector<unsigned> &RegClassDefCounts,
1074                                         Register Reg) const {
1075   assert(RegClassDefCounts.size() == TRI->getNumRegClasses());
1076 
1077   if (Reg.isVirtual()) {
1078     const TargetRegisterClass *OpRC = MRI->getRegClass(Reg);
1079     for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();
1080          RCIdx != RCIdxEnd; ++RCIdx) {
1081       const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx);
1082       // FIXME: Consider aliasing sub/super registers.
1083       if (OpRC->hasSubClassEq(IdxRC))
1084         ++RegClassDefCounts[RCIdx];
1085     }
1086 
1087     return;
1088   }
1089 
1090   for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();
1091        RCIdx != RCIdxEnd; ++RCIdx) {
1092     const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx);
1093     for (MCRegAliasIterator Alias(Reg, TRI, true); Alias.isValid(); ++Alias) {
1094       if (IdxRC->contains(*Alias)) {
1095         ++RegClassDefCounts[RCIdx];
1096         break;
1097       }
1098     }
1099   }
1100 }
1101 
1102 void RegAllocFast::allocateInstruction(MachineInstr &MI) {
1103   // The basic algorithm here is:
1104   // 1. Mark registers of def operands as free
1105   // 2. Allocate registers to use operands and place reload instructions for
1106   //    registers displaced by the allocation.
1107   //
1108   // However we need to handle some corner cases:
1109   // - pre-assigned defs and uses need to be handled before the other def/use
1110   //   operands are processed to avoid the allocation heuristics clashing with
1111   //   the pre-assignment.
1112   // - The "free def operands" step has to come last instead of first for tied
1113   //   operands and early-clobbers.
1114 
1115   UsedInInstr.clear();
1116   RegMasks.clear();
1117   BundleVirtRegsMap.clear();
1118 
1119   // Scan for special cases; Apply pre-assigned register defs to state.
1120   bool HasPhysRegUse = false;
1121   bool HasRegMask = false;
1122   bool HasVRegDef = false;
1123   bool HasDef = false;
1124   bool HasEarlyClobber = false;
1125   bool NeedToAssignLiveThroughs = false;
1126   for (MachineOperand &MO : MI.operands()) {
1127     if (MO.isReg()) {
1128       Register Reg = MO.getReg();
1129       if (Reg.isVirtual()) {
1130         if (MO.isDef()) {
1131           HasDef = true;
1132           HasVRegDef = true;
1133           if (MO.isEarlyClobber()) {
1134             HasEarlyClobber = true;
1135             NeedToAssignLiveThroughs = true;
1136           }
1137           if (MO.isTied() || (MO.getSubReg() != 0 && !MO.isUndef()))
1138             NeedToAssignLiveThroughs = true;
1139         }
1140       } else if (Reg.isPhysical()) {
1141         if (!MRI->isReserved(Reg)) {
1142           if (MO.isDef()) {
1143             HasDef = true;
1144             bool displacedAny = definePhysReg(MI, Reg);
1145             if (MO.isEarlyClobber())
1146               HasEarlyClobber = true;
1147             if (!displacedAny)
1148               MO.setIsDead(true);
1149           }
1150           if (MO.readsReg())
1151             HasPhysRegUse = true;
1152         }
1153       }
1154     } else if (MO.isRegMask()) {
1155       HasRegMask = true;
1156       RegMasks.push_back(MO.getRegMask());
1157     }
1158   }
1159 
1160   // Allocate virtreg defs.
1161   if (HasDef) {
1162     if (HasVRegDef) {
1163       // Special handling for early clobbers, tied operands or subregister defs:
1164       // Compared to "normal" defs these:
1165       // - Must not use a register that is pre-assigned for a use operand.
1166       // - In order to solve tricky inline assembly constraints we change the
1167       //   heuristic to figure out a good operand order before doing
1168       //   assignments.
1169       if (NeedToAssignLiveThroughs) {
1170         DefOperandIndexes.clear();
1171         PhysRegUses.clear();
1172 
1173         // Track number of defs which may consume a register from the class.
1174         std::vector<unsigned> RegClassDefCounts(TRI->getNumRegClasses(), 0);
1175         assert(RegClassDefCounts[0] == 0);
1176 
1177         LLVM_DEBUG(dbgs() << "Need to assign livethroughs\n");
1178         for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {
1179           const MachineOperand &MO = MI.getOperand(I);
1180           if (!MO.isReg())
1181             continue;
1182           Register Reg = MO.getReg();
1183           if (MO.readsReg()) {
1184             if (Reg.isPhysical()) {
1185               LLVM_DEBUG(dbgs() << "mark extra used: " << printReg(Reg, TRI)
1186                                 << '\n');
1187               markPhysRegUsedInInstr(Reg);
1188             }
1189           }
1190 
1191           if (MO.isDef()) {
1192             if (Reg.isVirtual())
1193               DefOperandIndexes.push_back(I);
1194 
1195             addRegClassDefCounts(RegClassDefCounts, Reg);
1196           }
1197         }
1198 
1199         llvm::sort(DefOperandIndexes, [&](uint16_t I0, uint16_t I1) {
1200           const MachineOperand &MO0 = MI.getOperand(I0);
1201           const MachineOperand &MO1 = MI.getOperand(I1);
1202           Register Reg0 = MO0.getReg();
1203           Register Reg1 = MO1.getReg();
1204           const TargetRegisterClass &RC0 = *MRI->getRegClass(Reg0);
1205           const TargetRegisterClass &RC1 = *MRI->getRegClass(Reg1);
1206 
1207           // Identify regclass that are easy to use up completely just in this
1208           // instruction.
1209           unsigned ClassSize0 = RegClassInfo.getOrder(&RC0).size();
1210           unsigned ClassSize1 = RegClassInfo.getOrder(&RC1).size();
1211 
1212           bool SmallClass0 = ClassSize0 < RegClassDefCounts[RC0.getID()];
1213           bool SmallClass1 = ClassSize1 < RegClassDefCounts[RC1.getID()];
1214           if (SmallClass0 > SmallClass1)
1215             return true;
1216           if (SmallClass0 < SmallClass1)
1217             return false;
1218 
1219           // Allocate early clobbers and livethrough operands first.
1220           bool Livethrough0 = MO0.isEarlyClobber() || MO0.isTied() ||
1221                               (MO0.getSubReg() == 0 && !MO0.isUndef());
1222           bool Livethrough1 = MO1.isEarlyClobber() || MO1.isTied() ||
1223                               (MO1.getSubReg() == 0 && !MO1.isUndef());
1224           if (Livethrough0 > Livethrough1)
1225             return true;
1226           if (Livethrough0 < Livethrough1)
1227             return false;
1228 
1229           // Tie-break rule: operand index.
1230           return I0 < I1;
1231         });
1232 
1233         for (uint16_t OpIdx : DefOperandIndexes) {
1234           MachineOperand &MO = MI.getOperand(OpIdx);
1235           LLVM_DEBUG(dbgs() << "Allocating " << MO << '\n');
1236           unsigned Reg = MO.getReg();
1237           if (MO.isEarlyClobber() || MO.isTied() ||
1238               (MO.getSubReg() && !MO.isUndef())) {
1239             defineLiveThroughVirtReg(MI, OpIdx, Reg);
1240           } else {
1241             defineVirtReg(MI, OpIdx, Reg);
1242           }
1243         }
1244       } else {
1245         // Assign virtual register defs.
1246         for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {
1247           MachineOperand &MO = MI.getOperand(I);
1248           if (!MO.isReg() || !MO.isDef())
1249             continue;
1250           Register Reg = MO.getReg();
1251           if (Reg.isVirtual())
1252             defineVirtReg(MI, I, Reg);
1253         }
1254       }
1255     }
1256 
1257     // Free registers occupied by defs.
1258     // Iterate operands in reverse order, so we see the implicit super register
1259     // defs first (we added them earlier in case of <def,read-undef>).
1260     for (unsigned I = MI.getNumOperands(); I-- > 0;) {
1261       MachineOperand &MO = MI.getOperand(I);
1262       if (!MO.isReg() || !MO.isDef())
1263         continue;
1264 
1265       // subreg defs don't free the full register. We left the subreg number
1266       // around as a marker in setPhysReg() to recognize this case here.
1267       if (MO.getSubReg() != 0) {
1268         MO.setSubReg(0);
1269         continue;
1270       }
1271 
1272       assert((!MO.isTied() || !isClobberedByRegMasks(MO.getReg())) &&
1273              "tied def assigned to clobbered register");
1274 
1275       // Do not free tied operands and early clobbers.
1276       if (MO.isTied() || MO.isEarlyClobber())
1277         continue;
1278       Register Reg = MO.getReg();
1279       if (!Reg)
1280         continue;
1281       assert(Reg.isPhysical());
1282       if (MRI->isReserved(Reg))
1283         continue;
1284       freePhysReg(Reg);
1285       unmarkRegUsedInInstr(Reg);
1286     }
1287   }
1288 
1289   // Displace clobbered registers.
1290   if (HasRegMask) {
1291     assert(!RegMasks.empty() && "expected RegMask");
1292     // MRI bookkeeping.
1293     for (const auto *RM : RegMasks)
1294       MRI->addPhysRegsUsedFromRegMask(RM);
1295 
1296     // Displace clobbered registers.
1297     for (const LiveReg &LR : LiveVirtRegs) {
1298       MCPhysReg PhysReg = LR.PhysReg;
1299       if (PhysReg != 0 && isClobberedByRegMasks(PhysReg))
1300         displacePhysReg(MI, PhysReg);
1301     }
1302   }
1303 
1304   // Apply pre-assigned register uses to state.
1305   if (HasPhysRegUse) {
1306     for (MachineOperand &MO : MI.operands()) {
1307       if (!MO.isReg() || !MO.readsReg())
1308         continue;
1309       Register Reg = MO.getReg();
1310       if (!Reg.isPhysical())
1311         continue;
1312       if (MRI->isReserved(Reg))
1313         continue;
1314       bool displacedAny = usePhysReg(MI, Reg);
1315       if (!displacedAny && !MRI->isReserved(Reg))
1316         MO.setIsKill(true);
1317     }
1318   }
1319 
1320   // Allocate virtreg uses and insert reloads as necessary.
1321   bool HasUndefUse = false;
1322   for (unsigned I = 0; I < MI.getNumOperands(); ++I) {
1323     MachineOperand &MO = MI.getOperand(I);
1324     if (!MO.isReg() || !MO.isUse())
1325       continue;
1326     Register Reg = MO.getReg();
1327     if (!Reg.isVirtual())
1328       continue;
1329 
1330     if (MO.isUndef()) {
1331       HasUndefUse = true;
1332       continue;
1333     }
1334 
1335 
1336     // Populate MayLiveAcrossBlocks in case the use block is allocated before
1337     // the def block (removing the vreg uses).
1338     mayLiveIn(Reg);
1339 
1340 
1341     assert(!MO.isInternalRead() && "Bundles not supported");
1342     assert(MO.readsReg() && "reading use");
1343     useVirtReg(MI, I, Reg);
1344   }
1345 
1346   // Allocate undef operands. This is a separate step because in a situation
1347   // like  ` = OP undef %X, %X`    both operands need the same register assign
1348   // so we should perform the normal assignment first.
1349   if (HasUndefUse) {
1350     for (MachineOperand &MO : MI.uses()) {
1351       if (!MO.isReg() || !MO.isUse())
1352         continue;
1353       Register Reg = MO.getReg();
1354       if (!Reg.isVirtual())
1355         continue;
1356 
1357       assert(MO.isUndef() && "Should only have undef virtreg uses left");
1358       allocVirtRegUndef(MO);
1359     }
1360   }
1361 
1362   // Free early clobbers.
1363   if (HasEarlyClobber) {
1364     for (unsigned I = MI.getNumOperands(); I-- > 0; ) {
1365       MachineOperand &MO = MI.getOperand(I);
1366       if (!MO.isReg() || !MO.isDef() || !MO.isEarlyClobber())
1367         continue;
1368       // subreg defs don't free the full register. We left the subreg number
1369       // around as a marker in setPhysReg() to recognize this case here.
1370       if (MO.getSubReg() != 0) {
1371         MO.setSubReg(0);
1372         continue;
1373       }
1374 
1375       Register Reg = MO.getReg();
1376       if (!Reg)
1377         continue;
1378       assert(Reg.isPhysical() && "should have register assigned");
1379 
1380       // We sometimes get odd situations like:
1381       //    early-clobber %x0 = INSTRUCTION %x0
1382       // which is semantically questionable as the early-clobber should
1383       // apply before the use. But in practice we consider the use to
1384       // happen before the early clobber now. Don't free the early clobber
1385       // register in this case.
1386       if (MI.readsRegister(Reg, TRI))
1387         continue;
1388 
1389       freePhysReg(Reg);
1390     }
1391   }
1392 
1393   LLVM_DEBUG(dbgs() << "<< " << MI);
1394   if (MI.isCopy() && MI.getOperand(0).getReg() == MI.getOperand(1).getReg() &&
1395       MI.getNumOperands() == 2) {
1396     LLVM_DEBUG(dbgs() << "Mark identity copy for removal\n");
1397     Coalesced.push_back(&MI);
1398   }
1399 }
1400 
1401 void RegAllocFast::handleDebugValue(MachineInstr &MI) {
1402   // Ignore DBG_VALUEs that aren't based on virtual registers. These are
1403   // mostly constants and frame indices.
1404   for (Register Reg : MI.getUsedDebugRegs()) {
1405     if (!Register::isVirtualRegister(Reg))
1406       continue;
1407 
1408     // Already spilled to a stackslot?
1409     int SS = StackSlotForVirtReg[Reg];
1410     if (SS != -1) {
1411       // Modify DBG_VALUE now that the value is in a spill slot.
1412       updateDbgValueForSpill(MI, SS, Reg);
1413       LLVM_DEBUG(dbgs() << "Rewrite DBG_VALUE for spilled memory: " << MI);
1414       continue;
1415     }
1416 
1417     // See if this virtual register has already been allocated to a physical
1418     // register or spilled to a stack slot.
1419     LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
1420     SmallVector<MachineOperand *> DbgOps;
1421     for (MachineOperand &Op : MI.getDebugOperandsForReg(Reg))
1422       DbgOps.push_back(&Op);
1423 
1424     if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
1425       // Update every use of Reg within MI.
1426       for (auto &RegMO : DbgOps)
1427         setPhysReg(MI, *RegMO, LRI->PhysReg);
1428     } else {
1429       DanglingDbgValues[Reg].push_back(&MI);
1430     }
1431 
1432     // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so
1433     // that future spills of Reg will have DBG_VALUEs.
1434     LiveDbgValueMap[Reg].append(DbgOps.begin(), DbgOps.end());
1435   }
1436 }
1437 
1438 void RegAllocFast::handleBundle(MachineInstr &MI) {
1439   MachineBasicBlock::instr_iterator BundledMI = MI.getIterator();
1440   ++BundledMI;
1441   while (BundledMI->isBundledWithPred()) {
1442     for (unsigned I = 0; I < BundledMI->getNumOperands(); ++I) {
1443       MachineOperand &MO = BundledMI->getOperand(I);
1444       if (!MO.isReg())
1445         continue;
1446 
1447       Register Reg = MO.getReg();
1448       if (!Reg.isVirtual())
1449         continue;
1450 
1451       DenseMap<Register, MCPhysReg>::iterator DI;
1452       DI = BundleVirtRegsMap.find(Reg);
1453       assert(DI != BundleVirtRegsMap.end() && "Unassigned virtual register");
1454 
1455       setPhysReg(MI, MO, DI->second);
1456     }
1457 
1458     ++BundledMI;
1459   }
1460 }
1461 
1462 void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) {
1463   this->MBB = &MBB;
1464   LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);
1465 
1466   RegUnitStates.assign(TRI->getNumRegUnits(), regFree);
1467   assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
1468 
1469   for (auto &LiveReg : MBB.liveouts())
1470     setPhysRegState(LiveReg.PhysReg, regPreAssigned);
1471 
1472   Coalesced.clear();
1473 
1474   // Traverse block in reverse order allocating instructions one by one.
1475   for (MachineInstr &MI : reverse(MBB)) {
1476     LLVM_DEBUG(
1477       dbgs() << "\n>> " << MI << "Regs:";
1478       dumpState()
1479     );
1480 
1481     // Special handling for debug values. Note that they are not allowed to
1482     // affect codegen of the other instructions in any way.
1483     if (MI.isDebugValue()) {
1484       handleDebugValue(MI);
1485       continue;
1486     }
1487 
1488     allocateInstruction(MI);
1489 
1490     // Once BUNDLE header is assigned registers, same assignments need to be
1491     // done for bundled MIs.
1492     if (MI.getOpcode() == TargetOpcode::BUNDLE) {
1493       handleBundle(MI);
1494     }
1495   }
1496 
1497   LLVM_DEBUG(
1498     dbgs() << "Begin Regs:";
1499     dumpState()
1500   );
1501 
1502   // Spill all physical registers holding virtual registers now.
1503   LLVM_DEBUG(dbgs() << "Loading live registers at begin of block.\n");
1504   reloadAtBegin(MBB);
1505 
1506   // Erase all the coalesced copies. We are delaying it until now because
1507   // LiveVirtRegs might refer to the instrs.
1508   for (MachineInstr *MI : Coalesced)
1509     MBB.erase(MI);
1510   NumCoalesced += Coalesced.size();
1511 
1512   for (auto &UDBGPair : DanglingDbgValues) {
1513     for (MachineInstr *DbgValue : UDBGPair.second) {
1514       assert(DbgValue->isDebugValue() && "expected DBG_VALUE");
1515       // Nothing to do if the vreg was spilled in the meantime.
1516       if (!DbgValue->hasDebugOperandForReg(UDBGPair.first))
1517         continue;
1518       LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue
1519                  << '\n');
1520       DbgValue->setDebugValueUndef();
1521     }
1522   }
1523   DanglingDbgValues.clear();
1524 
1525   LLVM_DEBUG(MBB.dump());
1526 }
1527 
1528 bool RegAllocFast::runOnMachineFunction(MachineFunction &MF) {
1529   LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1530                     << "********** Function: " << MF.getName() << '\n');
1531   MRI = &MF.getRegInfo();
1532   const TargetSubtargetInfo &STI = MF.getSubtarget();
1533   TRI = STI.getRegisterInfo();
1534   TII = STI.getInstrInfo();
1535   MFI = &MF.getFrameInfo();
1536   MRI->freezeReservedRegs(MF);
1537   RegClassInfo.runOnMachineFunction(MF);
1538   unsigned NumRegUnits = TRI->getNumRegUnits();
1539   UsedInInstr.clear();
1540   UsedInInstr.setUniverse(NumRegUnits);
1541   PhysRegUses.clear();
1542   PhysRegUses.setUniverse(NumRegUnits);
1543 
1544   // initialize the virtual->physical register map to have a 'null'
1545   // mapping for all virtual registers
1546   unsigned NumVirtRegs = MRI->getNumVirtRegs();
1547   StackSlotForVirtReg.resize(NumVirtRegs);
1548   LiveVirtRegs.setUniverse(NumVirtRegs);
1549   MayLiveAcrossBlocks.clear();
1550   MayLiveAcrossBlocks.resize(NumVirtRegs);
1551 
1552   // Loop over all of the basic blocks, eliminating virtual register references
1553   for (MachineBasicBlock &MBB : MF)
1554     allocateBasicBlock(MBB);
1555 
1556   if (ClearVirtRegs) {
1557     // All machine operands and other references to virtual registers have been
1558     // replaced. Remove the virtual registers.
1559     MRI->clearVirtRegs();
1560   }
1561 
1562   StackSlotForVirtReg.clear();
1563   LiveDbgValueMap.clear();
1564   return true;
1565 }
1566 
1567 FunctionPass *llvm::createFastRegisterAllocator() {
1568   return new RegAllocFast();
1569 }
1570 
1571 FunctionPass *llvm::createFastRegisterAllocator(
1572   std::function<bool(const TargetRegisterInfo &TRI,
1573                      const TargetRegisterClass &RC)> Ftor, bool ClearVirtRegs) {
1574   return new RegAllocFast(Ftor, ClearVirtRegs);
1575 }
1576