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