llvm/lib/CodeGen/RegAllocFast.cpp

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