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