Home | History | Annotate | Download | only in CodeGen 
      1 //===-- RegAllocFast.cpp - A fast register allocator for debug code -------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This register allocator allocates registers to a basic block at a time,
     11 // attempting to keep values in registers and reusing registers as appropriate.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "llvm/CodeGen/Passes.h"
     16 #include "llvm/ADT/DenseMap.h"
     17 #include "llvm/ADT/IndexedMap.h"
     18 #include "llvm/ADT/STLExtras.h"
     19 #include "llvm/ADT/SmallSet.h"
     20 #include "llvm/ADT/SmallVector.h"
     21 #include "llvm/ADT/SparseSet.h"
     22 #include "llvm/ADT/Statistic.h"
     23 #include "llvm/CodeGen/MachineFrameInfo.h"
     24 #include "llvm/CodeGen/MachineFunctionPass.h"
     25 #include "llvm/CodeGen/MachineInstr.h"
     26 #include "llvm/CodeGen/MachineInstrBuilder.h"
     27 #include "llvm/CodeGen/MachineRegisterInfo.h"
     28 #include "llvm/CodeGen/RegAllocRegistry.h"
     29 #include "llvm/CodeGen/RegisterClassInfo.h"
     30 #include "llvm/IR/BasicBlock.h"
     31 #include "llvm/Support/CommandLine.h"
     32 #include "llvm/Support/Debug.h"
     33 #include "llvm/Support/ErrorHandling.h"
     34 #include "llvm/Support/raw_ostream.h"
     35 #include "llvm/Target/TargetInstrInfo.h"
     36 #include "llvm/Target/TargetSubtargetInfo.h"
     37 #include <algorithm>
     38 using namespace llvm;
     39 
     40 #define DEBUG_TYPE "regalloc"
     41 
     42 STATISTIC(NumStores, "Number of stores added");
     43 STATISTIC(NumLoads , "Number of loads added");
     44 STATISTIC(NumCopies, "Number of copies coalesced");
     45 
     46 static RegisterRegAlloc
     47   fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
     48 
     49 namespace {
     50   class RAFast : public MachineFunctionPass {
     51   public:
     52     static char ID;
     53     RAFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1),
     54                isBulkSpilling(false) {}
     55   private:
     56     MachineFunction *MF;
     57     MachineRegisterInfo *MRI;
     58     const TargetRegisterInfo *TRI;
     59     const TargetInstrInfo *TII;
     60     RegisterClassInfo RegClassInfo;
     61 
     62     // Basic block currently being allocated.
     63     MachineBasicBlock *MBB;
     64 
     65     // StackSlotForVirtReg - Maps virtual regs to the frame index where these
     66     // values are spilled.
     67     IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
     68 
     69     // Everything we know about a live virtual register.
     70     struct LiveReg {
     71       MachineInstr *LastUse;    // Last instr to use reg.
     72       unsigned VirtReg;         // Virtual register number.
     73       unsigned PhysReg;         // Currently held here.
     74       unsigned short LastOpNum; // OpNum on LastUse.
     75       bool Dirty;               // Register needs spill.
     76 
     77       explicit LiveReg(unsigned v)
     78         : LastUse(nullptr), VirtReg(v), PhysReg(0), LastOpNum(0), Dirty(false){}
     79 
     80       unsigned getSparseSetIndex() const {
     81         return TargetRegisterInfo::virtReg2Index(VirtReg);
     82       }
     83     };
     84 
     85     typedef SparseSet<LiveReg> LiveRegMap;
     86 
     87     // LiveVirtRegs - This map contains entries for each virtual register
     88     // that is currently available in a physical register.
     89     LiveRegMap LiveVirtRegs;
     90 
     91     DenseMap<unsigned, SmallVector<MachineInstr *, 4> > LiveDbgValueMap;
     92 
     93     // RegState - Track the state of a physical register.
     94     enum RegState {
     95       // A disabled register is not available for allocation, but an alias may
     96       // be in use. A register can only be moved out of the disabled state if
     97       // all aliases are disabled.
     98       regDisabled,
     99 
    100       // A free register is not currently in use and can be allocated
    101       // immediately without checking aliases.
    102       regFree,
    103 
    104       // A reserved register has been assigned explicitly (e.g., setting up a
    105       // call parameter), and it remains reserved until it is used.
    106       regReserved
    107 
    108       // A register state may also be a virtual register number, indication that
    109       // the physical register is currently allocated to a virtual register. In
    110       // that case, LiveVirtRegs contains the inverse mapping.
    111     };
    112 
    113     // PhysRegState - One of the RegState enums, or a virtreg.
    114     std::vector<unsigned> PhysRegState;
    115 
    116     // Set of register units.
    117     typedef SparseSet<unsigned> UsedInInstrSet;
    118 
    119     // Set of register units that are used in the current instruction, and so
    120     // cannot be allocated.
    121     UsedInInstrSet UsedInInstr;
    122 
    123     // Mark a physreg as used in this instruction.
    124     void markRegUsedInInstr(unsigned PhysReg) {
    125       for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
    126         UsedInInstr.insert(*Units);
    127     }
    128 
    129     // Check if a physreg or any of its aliases are used in this instruction.
    130     bool isRegUsedInInstr(unsigned PhysReg) const {
    131       for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
    132         if (UsedInInstr.count(*Units))
    133           return true;
    134       return false;
    135     }
    136 
    137     // SkippedInstrs - Descriptors of instructions whose clobber list was
    138     // ignored because all registers were spilled. It is still necessary to
    139     // mark all the clobbered registers as used by the function.
    140     SmallPtrSet<const MCInstrDesc*, 4> SkippedInstrs;
    141 
    142     // isBulkSpilling - This flag is set when LiveRegMap will be cleared
    143     // completely after spilling all live registers. LiveRegMap entries should
    144     // not be erased.
    145     bool isBulkSpilling;
    146 
    147     enum : unsigned {
    148       spillClean = 1,
    149       spillDirty = 100,
    150       spillImpossible = ~0u
    151     };
    152   public:
    153     const char *getPassName() const override {
    154       return "Fast Register Allocator";
    155     }
    156 
    157     void getAnalysisUsage(AnalysisUsage &AU) const override {
    158       AU.setPreservesCFG();
    159       MachineFunctionPass::getAnalysisUsage(AU);
    160     }
    161 
    162   private:
    163     bool runOnMachineFunction(MachineFunction &Fn) override;
    164     void AllocateBasicBlock();
    165     void handleThroughOperands(MachineInstr *MI,
    166                                SmallVectorImpl<unsigned> &VirtDead);
    167     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
    168     bool isLastUseOfLocalReg(MachineOperand&);
    169 
    170     void addKillFlag(const LiveReg&);
    171     void killVirtReg(LiveRegMap::iterator);
    172     void killVirtReg(unsigned VirtReg);
    173     void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator);
    174     void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg);
    175 
    176     void usePhysReg(MachineOperand&);
    177     void definePhysReg(MachineInstr *MI, unsigned PhysReg, RegState NewState);
    178     unsigned calcSpillCost(unsigned PhysReg) const;
    179     void assignVirtToPhysReg(LiveReg&, unsigned PhysReg);
    180     LiveRegMap::iterator findLiveVirtReg(unsigned VirtReg) {
    181       return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg));
    182     }
    183     LiveRegMap::const_iterator findLiveVirtReg(unsigned VirtReg) const {
    184       return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg));
    185     }
    186     LiveRegMap::iterator assignVirtToPhysReg(unsigned VReg, unsigned PhysReg);
    187     LiveRegMap::iterator allocVirtReg(MachineInstr *MI, LiveRegMap::iterator,
    188                                       unsigned Hint);
    189     LiveRegMap::iterator defineVirtReg(MachineInstr *MI, unsigned OpNum,
    190                                        unsigned VirtReg, unsigned Hint);
    191     LiveRegMap::iterator reloadVirtReg(MachineInstr *MI, unsigned OpNum,
    192                                        unsigned VirtReg, unsigned Hint);
    193     void spillAll(MachineBasicBlock::iterator MI);
    194     bool setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg);
    195   };
    196   char RAFast::ID = 0;
    197 }
    198 
    199 /// getStackSpaceFor - This allocates space for the specified virtual register
    200 /// to be held on the stack.
    201 int RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
    202   // Find the location Reg would belong...
    203   int SS = StackSlotForVirtReg[VirtReg];
    204   if (SS != -1)
    205     return SS;          // Already has space allocated?
    206 
    207   // Allocate a new stack object for this spill location...
    208   int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(),
    209                                                             RC->getAlignment());
    210 
    211   // Assign the slot.
    212   StackSlotForVirtReg[VirtReg] = FrameIdx;
    213   return FrameIdx;
    214 }
    215 
    216 /// isLastUseOfLocalReg - Return true if MO is the only remaining reference to
    217 /// its virtual register, and it is guaranteed to be a block-local register.
    218 ///
    219 bool RAFast::isLastUseOfLocalReg(MachineOperand &MO) {
    220   // If the register has ever been spilled or reloaded, we conservatively assume
    221   // it is a global register used in multiple blocks.
    222   if (StackSlotForVirtReg[MO.getReg()] != -1)
    223     return false;
    224 
    225   // Check that the use/def chain has exactly one operand - MO.
    226   MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(MO.getReg());
    227   if (&*I != &MO)
    228     return false;
    229   return ++I == MRI->reg_nodbg_end();
    230 }
    231 
    232 /// addKillFlag - Set kill flags on last use of a virtual register.
    233 void RAFast::addKillFlag(const LiveReg &LR) {
    234   if (!LR.LastUse) return;
    235   MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum);
    236   if (MO.isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) {
    237     if (MO.getReg() == LR.PhysReg)
    238       MO.setIsKill();
    239     else
    240       LR.LastUse->addRegisterKilled(LR.PhysReg, TRI, true);
    241   }
    242 }
    243 
    244 /// killVirtReg - Mark virtreg as no longer available.
    245 void RAFast::killVirtReg(LiveRegMap::iterator LRI) {
    246   addKillFlag(*LRI);
    247   assert(PhysRegState[LRI->PhysReg] == LRI->VirtReg &&
    248          "Broken RegState mapping");
    249   PhysRegState[LRI->PhysReg] = regFree;
    250   // Erase from LiveVirtRegs unless we're spilling in bulk.
    251   if (!isBulkSpilling)
    252     LiveVirtRegs.erase(LRI);
    253 }
    254 
    255 /// killVirtReg - Mark virtreg as no longer available.
    256 void RAFast::killVirtReg(unsigned VirtReg) {
    257   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
    258          "killVirtReg needs a virtual register");
    259   LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
    260   if (LRI != LiveVirtRegs.end())
    261     killVirtReg(LRI);
    262 }
    263 
    264 /// spillVirtReg - This method spills the value specified by VirtReg into the
    265 /// corresponding stack slot if needed.
    266 void RAFast::spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg) {
    267   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
    268          "Spilling a physical register is illegal!");
    269   LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
    270   assert(LRI != LiveVirtRegs.end() && "Spilling unmapped virtual register");
    271   spillVirtReg(MI, LRI);
    272 }
    273 
    274 /// spillVirtReg - Do the actual work of spilling.
    275 void RAFast::spillVirtReg(MachineBasicBlock::iterator MI,
    276                           LiveRegMap::iterator LRI) {
    277   LiveReg &LR = *LRI;
    278   assert(PhysRegState[LR.PhysReg] == LRI->VirtReg && "Broken RegState mapping");
    279 
    280   if (LR.Dirty) {
    281     // If this physreg is used by the instruction, we want to kill it on the
    282     // instruction, not on the spill.
    283     bool SpillKill = LR.LastUse != MI;
    284     LR.Dirty = false;
    285     DEBUG(dbgs() << "Spilling " << PrintReg(LRI->VirtReg, TRI)
    286                  << " in " << PrintReg(LR.PhysReg, TRI));
    287     const TargetRegisterClass *RC = MRI->getRegClass(LRI->VirtReg);
    288     int FI = getStackSpaceFor(LRI->VirtReg, RC);
    289     DEBUG(dbgs() << " to stack slot #" << FI << "\n");
    290     TII->storeRegToStackSlot(*MBB, MI, LR.PhysReg, SpillKill, FI, RC, TRI);
    291     ++NumStores;   // Update statistics
    292 
    293     // If this register is used by DBG_VALUE then insert new DBG_VALUE to
    294     // identify spilled location as the place to find corresponding variable's
    295     // value.
    296     SmallVectorImpl<MachineInstr *> &LRIDbgValues =
    297       LiveDbgValueMap[LRI->VirtReg];
    298     for (unsigned li = 0, le = LRIDbgValues.size(); li != le; ++li) {
    299       MachineInstr *DBG = LRIDbgValues[li];
    300       const MDNode *Var = DBG->getDebugVariable();
    301       const MDNode *Expr = DBG->getDebugExpression();
    302       bool IsIndirect = DBG->isIndirectDebugValue();
    303       uint64_t Offset = IsIndirect ? DBG->getOperand(1).getImm() : 0;
    304       DebugLoc DL = DBG->getDebugLoc();
    305       assert(cast<MDLocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
    306              "Expected inlined-at fields to agree");
    307       MachineInstr *NewDV =
    308           BuildMI(*MBB, MI, DL, TII->get(TargetOpcode::DBG_VALUE))
    309               .addFrameIndex(FI)
    310               .addImm(Offset)
    311               .addMetadata(Var)
    312               .addMetadata(Expr);
    313       assert(NewDV->getParent() == MBB && "dangling parent pointer");
    314       (void)NewDV;
    315       DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV);
    316     }
    317     // Now this register is spilled there is should not be any DBG_VALUE
    318     // pointing to this register because they are all pointing to spilled value
    319     // now.
    320     LRIDbgValues.clear();
    321     if (SpillKill)
    322       LR.LastUse = nullptr; // Don't kill register again
    323   }
    324   killVirtReg(LRI);
    325 }
    326 
    327 /// spillAll - Spill all dirty virtregs without killing them.
    328 void RAFast::spillAll(MachineBasicBlock::iterator MI) {
    329   if (LiveVirtRegs.empty()) return;
    330   isBulkSpilling = true;
    331   // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
    332   // of spilling here is deterministic, if arbitrary.
    333   for (LiveRegMap::iterator i = LiveVirtRegs.begin(), e = LiveVirtRegs.end();
    334        i != e; ++i)
    335     spillVirtReg(MI, i);
    336   LiveVirtRegs.clear();
    337   isBulkSpilling = false;
    338 }
    339 
    340 /// usePhysReg - Handle the direct use of a physical register.
    341 /// Check that the register is not used by a virtreg.
    342 /// Kill the physreg, marking it free.
    343 /// This may add implicit kills to MO->getParent() and invalidate MO.
    344 void RAFast::usePhysReg(MachineOperand &MO) {
    345   unsigned PhysReg = MO.getReg();
    346   assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
    347          "Bad usePhysReg operand");
    348   markRegUsedInInstr(PhysReg);
    349   switch (PhysRegState[PhysReg]) {
    350   case regDisabled:
    351     break;
    352   case regReserved:
    353     PhysRegState[PhysReg] = regFree;
    354     // Fall through
    355   case regFree:
    356     MO.setIsKill();
    357     return;
    358   default:
    359     // The physreg was allocated to a virtual register. That means the value we
    360     // wanted has been clobbered.
    361     llvm_unreachable("Instruction uses an allocated register");
    362   }
    363 
    364   // Maybe a superregister is reserved?
    365   for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
    366     unsigned Alias = *AI;
    367     switch (PhysRegState[Alias]) {
    368     case regDisabled:
    369       break;
    370     case regReserved:
    371       // Either PhysReg is a subregister of Alias and we mark the
    372       // whole register as free, or PhysReg is the superregister of
    373       // Alias and we mark all the aliases as disabled before freeing
    374       // PhysReg.
    375       // In the latter case, since PhysReg was disabled, this means that
    376       // its value is defined only by physical sub-registers. This check
    377       // is performed by the assert of the default case in this loop.
    378       // Note: The value of the superregister may only be partial
    379       // defined, that is why regDisabled is a valid state for aliases.
    380       assert((TRI->isSuperRegister(PhysReg, Alias) ||
    381               TRI->isSuperRegister(Alias, PhysReg)) &&
    382              "Instruction is not using a subregister of a reserved register");
    383       // Fall through.
    384     case regFree:
    385       if (TRI->isSuperRegister(PhysReg, Alias)) {
    386         // Leave the superregister in the working set.
    387         PhysRegState[Alias] = regFree;
    388         MO.getParent()->addRegisterKilled(Alias, TRI, true);
    389         return;
    390       }
    391       // Some other alias was in the working set - clear it.
    392       PhysRegState[Alias] = regDisabled;
    393       break;
    394     default:
    395       llvm_unreachable("Instruction uses an alias of an allocated register");
    396     }
    397   }
    398 
    399   // All aliases are disabled, bring register into working set.
    400   PhysRegState[PhysReg] = regFree;
    401   MO.setIsKill();
    402 }
    403 
    404 /// definePhysReg - Mark PhysReg as reserved or free after spilling any
    405 /// virtregs. This is very similar to defineVirtReg except the physreg is
    406 /// reserved instead of allocated.
    407 void RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg,
    408                            RegState NewState) {
    409   markRegUsedInInstr(PhysReg);
    410   switch (unsigned VirtReg = PhysRegState[PhysReg]) {
    411   case regDisabled:
    412     break;
    413   default:
    414     spillVirtReg(MI, VirtReg);
    415     // Fall through.
    416   case regFree:
    417   case regReserved:
    418     PhysRegState[PhysReg] = NewState;
    419     return;
    420   }
    421 
    422   // This is a disabled register, disable all aliases.
    423   PhysRegState[PhysReg] = NewState;
    424   for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
    425     unsigned Alias = *AI;
    426     switch (unsigned VirtReg = PhysRegState[Alias]) {
    427     case regDisabled:
    428       break;
    429     default:
    430       spillVirtReg(MI, VirtReg);
    431       // Fall through.
    432     case regFree:
    433     case regReserved:
    434       PhysRegState[Alias] = regDisabled;
    435       if (TRI->isSuperRegister(PhysReg, Alias))
    436         return;
    437       break;
    438     }
    439   }
    440 }
    441 
    442 
    443 // calcSpillCost - Return the cost of spilling clearing out PhysReg and
    444 // aliases so it is free for allocation.
    445 // Returns 0 when PhysReg is free or disabled with all aliases disabled - it
    446 // can be allocated directly.
    447 // Returns spillImpossible when PhysReg or an alias can't be spilled.
    448 unsigned RAFast::calcSpillCost(unsigned PhysReg) const {
    449   if (isRegUsedInInstr(PhysReg)) {
    450     DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is already used in instr.\n");
    451     return spillImpossible;
    452   }
    453   switch (unsigned VirtReg = PhysRegState[PhysReg]) {
    454   case regDisabled:
    455     break;
    456   case regFree:
    457     return 0;
    458   case regReserved:
    459     DEBUG(dbgs() << PrintReg(VirtReg, TRI) << " corresponding "
    460                  << PrintReg(PhysReg, TRI) << " is reserved already.\n");
    461     return spillImpossible;
    462   default: {
    463     LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
    464     assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
    465     return I->Dirty ? spillDirty : spillClean;
    466   }
    467   }
    468 
    469   // This is a disabled register, add up cost of aliases.
    470   DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is disabled.\n");
    471   unsigned Cost = 0;
    472   for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
    473     unsigned Alias = *AI;
    474     switch (unsigned VirtReg = PhysRegState[Alias]) {
    475     case regDisabled:
    476       break;
    477     case regFree:
    478       ++Cost;
    479       break;
    480     case regReserved:
    481       return spillImpossible;
    482     default: {
    483       LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
    484       assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
    485       Cost += I->Dirty ? spillDirty : spillClean;
    486       break;
    487     }
    488     }
    489   }
    490   return Cost;
    491 }
    492 
    493 
    494 /// assignVirtToPhysReg - This method updates local state so that we know
    495 /// that PhysReg is the proper container for VirtReg now.  The physical
    496 /// register must not be used for anything else when this is called.
    497 ///
    498 void RAFast::assignVirtToPhysReg(LiveReg &LR, unsigned PhysReg) {
    499   DEBUG(dbgs() << "Assigning " << PrintReg(LR.VirtReg, TRI) << " to "
    500                << PrintReg(PhysReg, TRI) << "\n");
    501   PhysRegState[PhysReg] = LR.VirtReg;
    502   assert(!LR.PhysReg && "Already assigned a physreg");
    503   LR.PhysReg = PhysReg;
    504 }
    505 
    506 RAFast::LiveRegMap::iterator
    507 RAFast::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
    508   LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
    509   assert(LRI != LiveVirtRegs.end() && "VirtReg disappeared");
    510   assignVirtToPhysReg(*LRI, PhysReg);
    511   return LRI;
    512 }
    513 
    514 /// allocVirtReg - Allocate a physical register for VirtReg.
    515 RAFast::LiveRegMap::iterator RAFast::allocVirtReg(MachineInstr *MI,
    516                                                   LiveRegMap::iterator LRI,
    517                                                   unsigned Hint) {
    518   const unsigned VirtReg = LRI->VirtReg;
    519 
    520   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
    521          "Can only allocate virtual registers");
    522 
    523   const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
    524 
    525   // Ignore invalid hints.
    526   if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) ||
    527                !RC->contains(Hint) || !MRI->isAllocatable(Hint)))
    528     Hint = 0;
    529 
    530   // Take hint when possible.
    531   if (Hint) {
    532     // Ignore the hint if we would have to spill a dirty register.
    533     unsigned Cost = calcSpillCost(Hint);
    534     if (Cost < spillDirty) {
    535       if (Cost)
    536         definePhysReg(MI, Hint, regFree);
    537       // definePhysReg may kill virtual registers and modify LiveVirtRegs.
    538       // That invalidates LRI, so run a new lookup for VirtReg.
    539       return assignVirtToPhysReg(VirtReg, Hint);
    540     }
    541   }
    542 
    543   ArrayRef<MCPhysReg> AO = RegClassInfo.getOrder(RC);
    544 
    545   // First try to find a completely free register.
    546   for (ArrayRef<MCPhysReg>::iterator I = AO.begin(), E = AO.end(); I != E; ++I){
    547     unsigned PhysReg = *I;
    548     if (PhysRegState[PhysReg] == regFree && !isRegUsedInInstr(PhysReg)) {
    549       assignVirtToPhysReg(*LRI, PhysReg);
    550       return LRI;
    551     }
    552   }
    553 
    554   DEBUG(dbgs() << "Allocating " << PrintReg(VirtReg) << " from "
    555                << TRI->getRegClassName(RC) << "\n");
    556 
    557   unsigned BestReg = 0, BestCost = spillImpossible;
    558   for (ArrayRef<MCPhysReg>::iterator I = AO.begin(), E = AO.end(); I != E; ++I){
    559     unsigned Cost = calcSpillCost(*I);
    560     DEBUG(dbgs() << "\tRegister: " << PrintReg(*I, TRI) << "\n");
    561     DEBUG(dbgs() << "\tCost: " << Cost << "\n");
    562     DEBUG(dbgs() << "\tBestCost: " << BestCost << "\n");
    563     // Cost is 0 when all aliases are already disabled.
    564     if (Cost == 0) {
    565       assignVirtToPhysReg(*LRI, *I);
    566       return LRI;
    567     }
    568     if (Cost < BestCost)
    569       BestReg = *I, BestCost = Cost;
    570   }
    571 
    572   if (BestReg) {
    573     definePhysReg(MI, BestReg, regFree);
    574     // definePhysReg may kill virtual registers and modify LiveVirtRegs.
    575     // That invalidates LRI, so run a new lookup for VirtReg.
    576     return assignVirtToPhysReg(VirtReg, BestReg);
    577   }
    578 
    579   // Nothing we can do. Report an error and keep going with a bad allocation.
    580   if (MI->isInlineAsm())
    581     MI->emitError("inline assembly requires more registers than available");
    582   else
    583     MI->emitError("ran out of registers during register allocation");
    584   definePhysReg(MI, *AO.begin(), regFree);
    585   return assignVirtToPhysReg(VirtReg, *AO.begin());
    586 }
    587 
    588 /// defineVirtReg - Allocate a register for VirtReg and mark it as dirty.
    589 RAFast::LiveRegMap::iterator
    590 RAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum,
    591                       unsigned VirtReg, unsigned Hint) {
    592   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
    593          "Not a virtual register");
    594   LiveRegMap::iterator LRI;
    595   bool New;
    596   std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
    597   if (New) {
    598     // If there is no hint, peek at the only use of this register.
    599     if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) &&
    600         MRI->hasOneNonDBGUse(VirtReg)) {
    601       const MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(VirtReg);
    602       // It's a copy, use the destination register as a hint.
    603       if (UseMI.isCopyLike())
    604         Hint = UseMI.getOperand(0).getReg();
    605     }
    606     LRI = allocVirtReg(MI, LRI, Hint);
    607   } else if (LRI->LastUse) {
    608     // Redefining a live register - kill at the last use, unless it is this
    609     // instruction defining VirtReg multiple times.
    610     if (LRI->LastUse != MI || LRI->LastUse->getOperand(LRI->LastOpNum).isUse())
    611       addKillFlag(*LRI);
    612   }
    613   assert(LRI->PhysReg && "Register not assigned");
    614   LRI->LastUse = MI;
    615   LRI->LastOpNum = OpNum;
    616   LRI->Dirty = true;
    617   markRegUsedInInstr(LRI->PhysReg);
    618   return LRI;
    619 }
    620 
    621 /// reloadVirtReg - Make sure VirtReg is available in a physreg and return it.
    622 RAFast::LiveRegMap::iterator
    623 RAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum,
    624                       unsigned VirtReg, unsigned Hint) {
    625   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
    626          "Not a virtual register");
    627   LiveRegMap::iterator LRI;
    628   bool New;
    629   std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
    630   MachineOperand &MO = MI->getOperand(OpNum);
    631   if (New) {
    632     LRI = allocVirtReg(MI, LRI, Hint);
    633     const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
    634     int FrameIndex = getStackSpaceFor(VirtReg, RC);
    635     DEBUG(dbgs() << "Reloading " << PrintReg(VirtReg, TRI) << " into "
    636                  << PrintReg(LRI->PhysReg, TRI) << "\n");
    637     TII->loadRegFromStackSlot(*MBB, MI, LRI->PhysReg, FrameIndex, RC, TRI);
    638     ++NumLoads;
    639   } else if (LRI->Dirty) {
    640     if (isLastUseOfLocalReg(MO)) {
    641       DEBUG(dbgs() << "Killing last use: " << MO << "\n");
    642       if (MO.isUse())
    643         MO.setIsKill();
    644       else
    645         MO.setIsDead();
    646     } else if (MO.isKill()) {
    647       DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n");
    648       MO.setIsKill(false);
    649     } else if (MO.isDead()) {
    650       DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n");
    651       MO.setIsDead(false);
    652     }
    653   } else if (MO.isKill()) {
    654     // We must remove kill flags from uses of reloaded registers because the
    655     // register would be killed immediately, and there might be a second use:
    656     //   %foo = OR %x<kill>, %x
    657     // This would cause a second reload of %x into a different register.
    658     DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n");
    659     MO.setIsKill(false);
    660   } else if (MO.isDead()) {
    661     DEBUG(dbgs() << "Clearing clean dead: " << MO << "\n");
    662     MO.setIsDead(false);
    663   }
    664   assert(LRI->PhysReg && "Register not assigned");
    665   LRI->LastUse = MI;
    666   LRI->LastOpNum = OpNum;
    667   markRegUsedInInstr(LRI->PhysReg);
    668   return LRI;
    669 }
    670 
    671 // setPhysReg - Change operand OpNum in MI the refer the PhysReg, considering
    672 // subregs. This may invalidate any operand pointers.
    673 // Return true if the operand kills its register.
    674 bool RAFast::setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg) {
    675   MachineOperand &MO = MI->getOperand(OpNum);
    676   bool Dead = MO.isDead();
    677   if (!MO.getSubReg()) {
    678     MO.setReg(PhysReg);
    679     return MO.isKill() || Dead;
    680   }
    681 
    682   // Handle subregister index.
    683   MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0);
    684   MO.setSubReg(0);
    685 
    686   // A kill flag implies killing the full register. Add corresponding super
    687   // register kill.
    688   if (MO.isKill()) {
    689     MI->addRegisterKilled(PhysReg, TRI, true);
    690     return true;
    691   }
    692 
    693   // A <def,read-undef> of a sub-register requires an implicit def of the full
    694   // register.
    695   if (MO.isDef() && MO.isUndef())
    696     MI->addRegisterDefined(PhysReg, TRI);
    697 
    698   return Dead;
    699 }
    700 
    701 // Handle special instruction operand like early clobbers and tied ops when
    702 // there are additional physreg defines.
    703 void RAFast::handleThroughOperands(MachineInstr *MI,
    704                                    SmallVectorImpl<unsigned> &VirtDead) {
    705   DEBUG(dbgs() << "Scanning for through registers:");
    706   SmallSet<unsigned, 8> ThroughRegs;
    707   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    708     MachineOperand &MO = MI->getOperand(i);
    709     if (!MO.isReg()) continue;
    710     unsigned Reg = MO.getReg();
    711     if (!TargetRegisterInfo::isVirtualRegister(Reg))
    712       continue;
    713     if (MO.isEarlyClobber() || MI->isRegTiedToDefOperand(i) ||
    714         (MO.getSubReg() && MI->readsVirtualRegister(Reg))) {
    715       if (ThroughRegs.insert(Reg).second)
    716         DEBUG(dbgs() << ' ' << PrintReg(Reg));
    717     }
    718   }
    719 
    720   // If any physreg defines collide with preallocated through registers,
    721   // we must spill and reallocate.
    722   DEBUG(dbgs() << "\nChecking for physdef collisions.\n");
    723   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    724     MachineOperand &MO = MI->getOperand(i);
    725     if (!MO.isReg() || !MO.isDef()) continue;
    726     unsigned Reg = MO.getReg();
    727     if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
    728     markRegUsedInInstr(Reg);
    729     for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
    730       if (ThroughRegs.count(PhysRegState[*AI]))
    731         definePhysReg(MI, *AI, regFree);
    732     }
    733   }
    734 
    735   SmallVector<unsigned, 8> PartialDefs;
    736   DEBUG(dbgs() << "Allocating tied uses.\n");
    737   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    738     MachineOperand &MO = MI->getOperand(i);
    739     if (!MO.isReg()) continue;
    740     unsigned Reg = MO.getReg();
    741     if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
    742     if (MO.isUse()) {
    743       unsigned DefIdx = 0;
    744       if (!MI->isRegTiedToDefOperand(i, &DefIdx)) continue;
    745       DEBUG(dbgs() << "Operand " << i << "("<< MO << ") is tied to operand "
    746         << DefIdx << ".\n");
    747       LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0);
    748       unsigned PhysReg = LRI->PhysReg;
    749       setPhysReg(MI, i, PhysReg);
    750       // Note: we don't update the def operand yet. That would cause the normal
    751       // def-scan to attempt spilling.
    752     } else if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) {
    753       DEBUG(dbgs() << "Partial redefine: " << MO << "\n");
    754       // Reload the register, but don't assign to the operand just yet.
    755       // That would confuse the later phys-def processing pass.
    756       LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0);
    757       PartialDefs.push_back(LRI->PhysReg);
    758     }
    759   }
    760 
    761   DEBUG(dbgs() << "Allocating early clobbers.\n");
    762   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    763     MachineOperand &MO = MI->getOperand(i);
    764     if (!MO.isReg()) continue;
    765     unsigned Reg = MO.getReg();
    766     if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
    767     if (!MO.isEarlyClobber())
    768       continue;
    769     // Note: defineVirtReg may invalidate MO.
    770     LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, 0);
    771     unsigned PhysReg = LRI->PhysReg;
    772     if (setPhysReg(MI, i, PhysReg))
    773       VirtDead.push_back(Reg);
    774   }
    775 
    776   // Restore UsedInInstr to a state usable for allocating normal virtual uses.
    777   UsedInInstr.clear();
    778   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    779     MachineOperand &MO = MI->getOperand(i);
    780     if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue;
    781     unsigned Reg = MO.getReg();
    782     if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
    783     DEBUG(dbgs() << "\tSetting " << PrintReg(Reg, TRI)
    784                  << " as used in instr\n");
    785     markRegUsedInInstr(Reg);
    786   }
    787 
    788   // Also mark PartialDefs as used to avoid reallocation.
    789   for (unsigned i = 0, e = PartialDefs.size(); i != e; ++i)
    790     markRegUsedInInstr(PartialDefs[i]);
    791 }
    792 
    793 void RAFast::AllocateBasicBlock() {
    794   DEBUG(dbgs() << "\nAllocating " << *MBB);
    795 
    796   PhysRegState.assign(TRI->getNumRegs(), regDisabled);
    797   assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
    798 
    799   MachineBasicBlock::iterator MII = MBB->begin();
    800 
    801   // Add live-in registers as live.
    802   for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
    803          E = MBB->livein_end(); I != E; ++I)
    804     if (MRI->isAllocatable(*I))
    805       definePhysReg(MII, *I, regReserved);
    806 
    807   SmallVector<unsigned, 8> VirtDead;
    808   SmallVector<MachineInstr*, 32> Coalesced;
    809 
    810   // Otherwise, sequentially allocate each instruction in the MBB.
    811   while (MII != MBB->end()) {
    812     MachineInstr *MI = MII++;
    813     const MCInstrDesc &MCID = MI->getDesc();
    814     DEBUG({
    815         dbgs() << "\n>> " << *MI << "Regs:";
    816         for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) {
    817           if (PhysRegState[Reg] == regDisabled) continue;
    818           dbgs() << " " << TRI->getName(Reg);
    819           switch(PhysRegState[Reg]) {
    820           case regFree:
    821             break;
    822           case regReserved:
    823             dbgs() << "*";
    824             break;
    825           default: {
    826             dbgs() << '=' << PrintReg(PhysRegState[Reg]);
    827             LiveRegMap::iterator I = findLiveVirtReg(PhysRegState[Reg]);
    828             assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
    829             if (I->Dirty)
    830               dbgs() << "*";
    831             assert(I->PhysReg == Reg && "Bad inverse map");
    832             break;
    833           }
    834           }
    835         }
    836         dbgs() << '\n';
    837         // Check that LiveVirtRegs is the inverse.
    838         for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
    839              e = LiveVirtRegs.end(); i != e; ++i) {
    840            assert(TargetRegisterInfo::isVirtualRegister(i->VirtReg) &&
    841                   "Bad map key");
    842            assert(TargetRegisterInfo::isPhysicalRegister(i->PhysReg) &&
    843                   "Bad map value");
    844            assert(PhysRegState[i->PhysReg] == i->VirtReg && "Bad inverse map");
    845         }
    846       });
    847 
    848     // Debug values are not allowed to change codegen in any way.
    849     if (MI->isDebugValue()) {
    850       bool ScanDbgValue = true;
    851       while (ScanDbgValue) {
    852         ScanDbgValue = false;
    853         for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    854           MachineOperand &MO = MI->getOperand(i);
    855           if (!MO.isReg()) continue;
    856           unsigned Reg = MO.getReg();
    857           if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
    858           LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
    859           if (LRI != LiveVirtRegs.end())
    860             setPhysReg(MI, i, LRI->PhysReg);
    861           else {
    862             int SS = StackSlotForVirtReg[Reg];
    863             if (SS == -1) {
    864               // We can't allocate a physreg for a DebugValue, sorry!
    865               DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
    866               MO.setReg(0);
    867             }
    868             else {
    869               // Modify DBG_VALUE now that the value is in a spill slot.
    870               bool IsIndirect = MI->isIndirectDebugValue();
    871               uint64_t Offset = IsIndirect ? MI->getOperand(1).getImm() : 0;
    872               const MDNode *Var = MI->getDebugVariable();
    873               const MDNode *Expr = MI->getDebugExpression();
    874               DebugLoc DL = MI->getDebugLoc();
    875               MachineBasicBlock *MBB = MI->getParent();
    876               assert(
    877                   cast<MDLocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
    878                   "Expected inlined-at fields to agree");
    879               MachineInstr *NewDV = BuildMI(*MBB, MBB->erase(MI), DL,
    880                                             TII->get(TargetOpcode::DBG_VALUE))
    881                                         .addFrameIndex(SS)
    882                                         .addImm(Offset)
    883                                         .addMetadata(Var)
    884                                         .addMetadata(Expr);
    885               DEBUG(dbgs() << "Modifying debug info due to spill:"
    886                            << "\t" << *NewDV);
    887               // Scan NewDV operands from the beginning.
    888               MI = NewDV;
    889               ScanDbgValue = true;
    890               break;
    891             }
    892           }
    893           LiveDbgValueMap[Reg].push_back(MI);
    894         }
    895       }
    896       // Next instruction.
    897       continue;
    898     }
    899 
    900     // If this is a copy, we may be able to coalesce.
    901     unsigned CopySrc = 0, CopyDst = 0, CopySrcSub = 0, CopyDstSub = 0;
    902     if (MI->isCopy()) {
    903       CopyDst = MI->getOperand(0).getReg();
    904       CopySrc = MI->getOperand(1).getReg();
    905       CopyDstSub = MI->getOperand(0).getSubReg();
    906       CopySrcSub = MI->getOperand(1).getSubReg();
    907     }
    908 
    909     // Track registers used by instruction.
    910     UsedInInstr.clear();
    911 
    912     // First scan.
    913     // Mark physreg uses and early clobbers as used.
    914     // Find the end of the virtreg operands
    915     unsigned VirtOpEnd = 0;
    916     bool hasTiedOps = false;
    917     bool hasEarlyClobbers = false;
    918     bool hasPartialRedefs = false;
    919     bool hasPhysDefs = false;
    920     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    921       MachineOperand &MO = MI->getOperand(i);
    922       // Make sure MRI knows about registers clobbered by regmasks.
    923       if (MO.isRegMask()) {
    924         MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
    925         continue;
    926       }
    927       if (!MO.isReg()) continue;
    928       unsigned Reg = MO.getReg();
    929       if (!Reg) continue;
    930       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    931         VirtOpEnd = i+1;
    932         if (MO.isUse()) {
    933           hasTiedOps = hasTiedOps ||
    934                               MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1;
    935         } else {
    936           if (MO.isEarlyClobber())
    937             hasEarlyClobbers = true;
    938           if (MO.getSubReg() && MI->readsVirtualRegister(Reg))
    939             hasPartialRedefs = true;
    940         }
    941         continue;
    942       }
    943       if (!MRI->isAllocatable(Reg)) continue;
    944       if (MO.isUse()) {
    945         usePhysReg(MO);
    946       } else if (MO.isEarlyClobber()) {
    947         definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ?
    948                                regFree : regReserved);
    949         hasEarlyClobbers = true;
    950       } else
    951         hasPhysDefs = true;
    952     }
    953 
    954     // The instruction may have virtual register operands that must be allocated
    955     // the same register at use-time and def-time: early clobbers and tied
    956     // operands. If there are also physical defs, these registers must avoid
    957     // both physical defs and uses, making them more constrained than normal
    958     // operands.
    959     // Similarly, if there are multiple defs and tied operands, we must make
    960     // sure the same register is allocated to uses and defs.
    961     // We didn't detect inline asm tied operands above, so just make this extra
    962     // pass for all inline asm.
    963     if (MI->isInlineAsm() || hasEarlyClobbers || hasPartialRedefs ||
    964         (hasTiedOps && (hasPhysDefs || MCID.getNumDefs() > 1))) {
    965       handleThroughOperands(MI, VirtDead);
    966       // Don't attempt coalescing when we have funny stuff going on.
    967       CopyDst = 0;
    968       // Pretend we have early clobbers so the use operands get marked below.
    969       // This is not necessary for the common case of a single tied use.
    970       hasEarlyClobbers = true;
    971     }
    972 
    973     // Second scan.
    974     // Allocate virtreg uses.
    975     for (unsigned i = 0; i != VirtOpEnd; ++i) {
    976       MachineOperand &MO = MI->getOperand(i);
    977       if (!MO.isReg()) continue;
    978       unsigned Reg = MO.getReg();
    979       if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
    980       if (MO.isUse()) {
    981         LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, CopyDst);
    982         unsigned PhysReg = LRI->PhysReg;
    983         CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0;
    984         if (setPhysReg(MI, i, PhysReg))
    985           killVirtReg(LRI);
    986       }
    987     }
    988 
    989     for (UsedInInstrSet::iterator
    990          I = UsedInInstr.begin(), E = UsedInInstr.end(); I != E; ++I)
    991       MRI->setRegUnitUsed(*I);
    992 
    993     // Track registers defined by instruction - early clobbers and tied uses at
    994     // this point.
    995     UsedInInstr.clear();
    996     if (hasEarlyClobbers) {
    997       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    998         MachineOperand &MO = MI->getOperand(i);
    999         if (!MO.isReg()) continue;
   1000         unsigned Reg = MO.getReg();
   1001         if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
   1002         // Look for physreg defs and tied uses.
   1003         if (!MO.isDef() && !MI->isRegTiedToDefOperand(i)) continue;
   1004         markRegUsedInInstr(Reg);
   1005       }
   1006     }
   1007 
   1008     unsigned DefOpEnd = MI->getNumOperands();
   1009     if (MI->isCall()) {
   1010       // Spill all virtregs before a call. This serves two purposes: 1. If an
   1011       // exception is thrown, the landing pad is going to expect to find
   1012       // registers in their spill slots, and 2. we don't have to wade through
   1013       // all the <imp-def> operands on the call instruction.
   1014       DefOpEnd = VirtOpEnd;
   1015       DEBUG(dbgs() << "  Spilling remaining registers before call.\n");
   1016       spillAll(MI);
   1017 
   1018       // The imp-defs are skipped below, but we still need to mark those
   1019       // registers as used by the function.
   1020       SkippedInstrs.insert(&MCID);
   1021     }
   1022 
   1023     // Third scan.
   1024     // Allocate defs and collect dead defs.
   1025     for (unsigned i = 0; i != DefOpEnd; ++i) {
   1026       MachineOperand &MO = MI->getOperand(i);
   1027       if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber())
   1028         continue;
   1029       unsigned Reg = MO.getReg();
   1030 
   1031       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
   1032         if (!MRI->isAllocatable(Reg)) continue;
   1033         definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved);
   1034         continue;
   1035       }
   1036       LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc);
   1037       unsigned PhysReg = LRI->PhysReg;
   1038       if (setPhysReg(MI, i, PhysReg)) {
   1039         VirtDead.push_back(Reg);
   1040         CopyDst = 0; // cancel coalescing;
   1041       } else
   1042         CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0;
   1043     }
   1044 
   1045     // Kill dead defs after the scan to ensure that multiple defs of the same
   1046     // register are allocated identically. We didn't need to do this for uses
   1047     // because we are crerating our own kill flags, and they are always at the
   1048     // last use.
   1049     for (unsigned i = 0, e = VirtDead.size(); i != e; ++i)
   1050       killVirtReg(VirtDead[i]);
   1051     VirtDead.clear();
   1052 
   1053     for (UsedInInstrSet::iterator
   1054          I = UsedInInstr.begin(), E = UsedInInstr.end(); I != E; ++I)
   1055       MRI->setRegUnitUsed(*I);
   1056 
   1057     if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) {
   1058       DEBUG(dbgs() << "-- coalescing: " << *MI);
   1059       Coalesced.push_back(MI);
   1060     } else {
   1061       DEBUG(dbgs() << "<< " << *MI);
   1062     }
   1063   }
   1064 
   1065   // Spill all physical registers holding virtual registers now.
   1066   DEBUG(dbgs() << "Spilling live registers at end of block.\n");
   1067   spillAll(MBB->getFirstTerminator());
   1068 
   1069   // Erase all the coalesced copies. We are delaying it until now because
   1070   // LiveVirtRegs might refer to the instrs.
   1071   for (unsigned i = 0, e = Coalesced.size(); i != e; ++i)
   1072     MBB->erase(Coalesced[i]);
   1073   NumCopies += Coalesced.size();
   1074 
   1075   DEBUG(MBB->dump());
   1076 }
   1077 
   1078 /// runOnMachineFunction - Register allocate the whole function
   1079 ///
   1080 bool RAFast::runOnMachineFunction(MachineFunction &Fn) {
   1081   DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
   1082                << "********** Function: " << Fn.getName() << '\n');
   1083   MF = &Fn;
   1084   MRI = &MF->getRegInfo();
   1085   TRI = MF->getSubtarget().getRegisterInfo();
   1086   TII = MF->getSubtarget().getInstrInfo();
   1087   MRI->freezeReservedRegs(Fn);
   1088   RegClassInfo.runOnMachineFunction(Fn);
   1089   UsedInInstr.clear();
   1090   UsedInInstr.setUniverse(TRI->getNumRegUnits());
   1091 
   1092   assert(!MRI->isSSA() && "regalloc requires leaving SSA");
   1093 
   1094   // initialize the virtual->physical register map to have a 'null'
   1095   // mapping for all virtual registers
   1096   StackSlotForVirtReg.resize(MRI->getNumVirtRegs());
   1097   LiveVirtRegs.setUniverse(MRI->getNumVirtRegs());
   1098 
   1099   // Loop over all of the basic blocks, eliminating virtual register references
   1100   for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end();
   1101        MBBi != MBBe; ++MBBi) {
   1102     MBB = &*MBBi;
   1103     AllocateBasicBlock();
   1104   }
   1105 
   1106   // Add the clobber lists for all the instructions we skipped earlier.
   1107   for (const MCInstrDesc *Desc : SkippedInstrs)
   1108     if (const uint16_t *Defs = Desc->getImplicitDefs())
   1109       while (*Defs)
   1110         MRI->setPhysRegUsed(*Defs++);
   1111 
   1112   // All machine operands and other references to virtual registers have been
   1113   // replaced. Remove the virtual registers.
   1114   MRI->clearVirtRegs();
   1115 
   1116   SkippedInstrs.clear();
   1117   StackSlotForVirtReg.clear();
   1118   LiveDbgValueMap.clear();
   1119   return true;
   1120 }
   1121 
   1122 FunctionPass *llvm::createFastRegisterAllocator() {
   1123   return new RAFast();
   1124 }
   1125