LCOV - code coverage report
Current view: top level - lib/CodeGen - RegAllocFast.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 430 439 97.9 %
Date: 2017-09-14 15:23:50 Functions: 33 33 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13