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

Generated by: LCOV version 1.13