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