contrib/llvm-project/llvm/lib/CodeGen/RegAllocFast.cpp

   1 //===- RegAllocFast.cpp - A fast register allocator for debug code --------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file This register allocator allocates registers to a basic block at a
  10 /// time, attempting to keep values in registers and reusing registers as
  11 /// appropriate.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/ADT/ArrayRef.h"
  16 #include "llvm/ADT/DenseMap.h"
  17 #include "llvm/ADT/IndexedMap.h"
  18 #include "llvm/ADT/SmallSet.h"
  19 #include "llvm/ADT/SmallVector.h"
  20 #include "llvm/ADT/SparseSet.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/CodeGen/MachineBasicBlock.h"
  23 #include "llvm/CodeGen/MachineFrameInfo.h"
  24 #include "llvm/CodeGen/MachineFunction.h"
  25 #include "llvm/CodeGen/MachineFunctionPass.h"
  26 #include "llvm/CodeGen/MachineInstr.h"
  27 #include "llvm/CodeGen/MachineInstrBuilder.h"
  28 #include "llvm/CodeGen/MachineOperand.h"
  29 #include "llvm/CodeGen/MachineRegisterInfo.h"
  30 #include "llvm/CodeGen/RegAllocRegistry.h"
  31 #include "llvm/CodeGen/RegisterClassInfo.h"
  32 #include "llvm/CodeGen/TargetInstrInfo.h"
  33 #include "llvm/CodeGen/TargetOpcodes.h"
  34 #include "llvm/CodeGen/TargetRegisterInfo.h"
  35 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  36 #include "llvm/IR/DebugLoc.h"
  37 #include "llvm/IR/Metadata.h"
  38 #include "llvm/InitializePasses.h"
  39 #include "llvm/MC/MCInstrDesc.h"
  40 #include "llvm/MC/MCRegisterInfo.h"
  41 #include "llvm/Pass.h"
  42 #include "llvm/Support/Casting.h"
  43 #include "llvm/Support/Compiler.h"
  44 #include "llvm/Support/Debug.h"
  45 #include "llvm/Support/ErrorHandling.h"
  46 #include "llvm/Support/raw_ostream.h"
  47 #include <cassert>
  48 #include <tuple>
  49 #include <vector>
  50
  51 using namespace llvm;
  52
  53 #define DEBUG_TYPE "regalloc"
  54
  55 STATISTIC(NumStores, "Number of stores added");
  56 STATISTIC(NumLoads , "Number of loads added");
  57 STATISTIC(NumCoalesced, "Number of copies coalesced");
  58
  59 static RegisterRegAlloc
  60   fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
  61
  62 namespace {
  63
  64   class RegAllocFast : public MachineFunctionPass {
  65   public:
  66     static char ID;
  67
  68     RegAllocFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1) {}
  69
  70   private:
  71     MachineFrameInfo *MFI;
  72     MachineRegisterInfo *MRI;
  73     const TargetRegisterInfo *TRI;
  74     const TargetInstrInfo *TII;
  75     RegisterClassInfo RegClassInfo;
  76
  77     /// Basic block currently being allocated.
  78     MachineBasicBlock *MBB;
  79
  80     /// Maps virtual regs to the frame index where these values are spilled.
  81     IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
  82
  83     /// Everything we know about a live virtual register.
  84     struct LiveReg {
  85       MachineInstr *LastUse = nullptr; ///< Last instr to use reg.
  86       Register VirtReg;                ///< Virtual register number.
  87       MCPhysReg PhysReg = 0;           ///< Currently held here.
  88       unsigned short LastOpNum = 0;    ///< OpNum on LastUse.
  89       bool Dirty = false;              ///< Register needs spill.
  90
  91       explicit LiveReg(Register VirtReg) : VirtReg(VirtReg) {}
  92
  93       unsigned getSparseSetIndex() const {
  94         return Register::virtReg2Index(VirtReg);
  95       }
  96     };
  97
  98     using LiveRegMap = SparseSet<LiveReg>;
  99     /// This map contains entries for each virtual register that is currently
 100     /// available in a physical register.
 101     LiveRegMap LiveVirtRegs;
 102
 103     DenseMap<unsigned, SmallVector<MachineInstr *, 2>> LiveDbgValueMap;
 104
 105     /// Has a bit set for every virtual register for which it was determined
 106     /// that it is alive across blocks.
 107     BitVector MayLiveAcrossBlocks;
 108
 109     /// State of a register unit.
 110     enum RegUnitState {
 111       /// A free register is not currently in use and can be allocated
 112       /// immediately without checking aliases.
 113       regFree,
 114
 115       /// A reserved register has been assigned explicitly (e.g., setting up a
 116       /// call parameter), and it remains reserved until it is used.
 117       regReserved
 118
 119       /// A register state may also be a virtual register number, indication
 120       /// that the physical register is currently allocated to a virtual
 121       /// register. In that case, LiveVirtRegs contains the inverse mapping.
 122     };
 123
 124     /// Maps each physical register to a RegUnitState enum or virtual register.
 125     std::vector<unsigned> RegUnitStates;
 126
 127     SmallVector<Register, 16> VirtDead;
 128     SmallVector<MachineInstr *, 32> Coalesced;
 129
 130     using RegUnitSet = SparseSet<uint16_t, identity<uint16_t>>;
 131     /// Set of register units that are used in the current instruction, and so
 132     /// cannot be allocated.
 133     RegUnitSet UsedInInstr;
 134
 135     void setPhysRegState(MCPhysReg PhysReg, unsigned NewState);
 136
 137     /// Mark a physreg as used in this instruction.
 138     void markRegUsedInInstr(MCPhysReg PhysReg) {
 139       for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
 140         UsedInInstr.insert(*Units);
 141     }
 142
 143     /// Check if a physreg or any of its aliases are used in this instruction.
 144     bool isRegUsedInInstr(MCPhysReg PhysReg) const {
 145       for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
 146         if (UsedInInstr.count(*Units))
 147           return true;
 148       return false;
 149     }
 150
 151     enum : unsigned {
 152       spillClean = 50,
 153       spillDirty = 100,
 154       spillPrefBonus = 20,
 155       spillImpossible = ~0u
 156     };
 157
 158   public:
 159     StringRef getPassName() const override { return "Fast Register Allocator"; }
 160
 161     void getAnalysisUsage(AnalysisUsage &AU) const override {
 162       AU.setPreservesCFG();
 163       MachineFunctionPass::getAnalysisUsage(AU);
 164     }
 165
 166     MachineFunctionProperties getRequiredProperties() const override {
 167       return MachineFunctionProperties().set(
 168           MachineFunctionProperties::Property::NoPHIs);
 169     }
 170
 171     MachineFunctionProperties getSetProperties() const override {
 172       return MachineFunctionProperties().set(
 173           MachineFunctionProperties::Property::NoVRegs);
 174     }
 175
 176   private:
 177     bool runOnMachineFunction(MachineFunction &MF) override;
 178
 179     void allocateBasicBlock(MachineBasicBlock &MBB);
 180     void allocateInstruction(MachineInstr &MI);
 181     void handleDebugValue(MachineInstr &MI);
 182     void handleThroughOperands(MachineInstr &MI,
 183                                SmallVectorImpl<Register> &VirtDead);
 184     bool isLastUseOfLocalReg(const MachineOperand &MO) const;
 185
 186     void addKillFlag(const LiveReg &LRI);
 187 #ifndef NDEBUG
 188     bool verifyRegStateMapping(const LiveReg &LR) const;
 189 #endif
 190
 191     void killVirtReg(LiveReg &LR);
 192     void killVirtReg(Register VirtReg);
 193     void spillVirtReg(MachineBasicBlock::iterator MI, LiveReg &LR);
 194     void spillVirtReg(MachineBasicBlock::iterator MI, Register VirtReg);
 195
 196     void usePhysReg(MachineOperand &MO);
 197     void definePhysReg(MachineBasicBlock::iterator MI, MCPhysReg PhysReg,
 198                        unsigned NewState);
 199     unsigned calcSpillCost(MCPhysReg PhysReg) const;
 200     void assignVirtToPhysReg(LiveReg &, MCPhysReg PhysReg);
 201
 202     LiveRegMap::iterator findLiveVirtReg(Register VirtReg) {
 203       return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
 204     }
 205
 206     LiveRegMap::const_iterator findLiveVirtReg(Register VirtReg) const {
 207       return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
 208     }
 209
 210     void allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint);
 211     void allocVirtRegUndef(MachineOperand &MO);
 212     MCPhysReg defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,
 213                             Register Hint);
 214     LiveReg &reloadVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,
 215                            Register Hint);
 216     void spillAll(MachineBasicBlock::iterator MI, bool OnlyLiveOut);
 217     bool setPhysReg(MachineInstr &MI, MachineOperand &MO, MCPhysReg PhysReg);
 218
 219     Register traceCopies(Register VirtReg) const;
 220     Register traceCopyChain(Register Reg) const;
 221
 222     int getStackSpaceFor(Register VirtReg);
 223     void spill(MachineBasicBlock::iterator Before, Register VirtReg,
 224                MCPhysReg AssignedReg, bool Kill);
 225     void reload(MachineBasicBlock::iterator Before, Register VirtReg,
 226                 MCPhysReg PhysReg);
 227
 228     bool mayLiveOut(Register VirtReg);
 229     bool mayLiveIn(Register VirtReg);
 230
 231     void dumpState() const;
 232   };
 233
 234 } // end anonymous namespace
 235
 236 char RegAllocFast::ID = 0;
 237
 238 INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false,
 239                 false)
 240
 241 void RegAllocFast::setPhysRegState(MCPhysReg PhysReg, unsigned NewState) {
 242   for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI)
 243     RegUnitStates[*UI] = NewState;
 244 }
 245
 246 /// This allocates space for the specified virtual register to be held on the
 247 /// stack.
 248 int RegAllocFast::getStackSpaceFor(Register VirtReg) {
 249   // Find the location Reg would belong...
 250   int SS = StackSlotForVirtReg[VirtReg];
 251   // Already has space allocated?
 252   if (SS != -1)
 253     return SS;
 254
 255   // Allocate a new stack object for this spill location...
 256   const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
 257   unsigned Size = TRI->getSpillSize(RC);
 258   Align Alignment = TRI->getSpillAlign(RC);
 259   int FrameIdx = MFI->CreateSpillStackObject(Size, Alignment);
 260
 261   // Assign the slot.
 262   StackSlotForVirtReg[VirtReg] = FrameIdx;
 263   return FrameIdx;
 264 }
 265
 266 /// Returns false if \p VirtReg is known to not live out of the current block.
 267 bool RegAllocFast::mayLiveOut(Register VirtReg) {
 268   if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg))) {
 269     // Cannot be live-out if there are no successors.
 270     return !MBB->succ_empty();
 271   }
 272
 273   // If this block loops back to itself, it would be necessary to check whether
 274   // the use comes after the def.
 275   if (MBB->isSuccessor(MBB)) {
 276     MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
 277     return true;
 278   }
 279
 280   // See if the first \p Limit uses of the register are all in the current
 281   // block.
 282   static const unsigned Limit = 8;
 283   unsigned C = 0;
 284   for (const MachineInstr &UseInst : MRI->reg_nodbg_instructions(VirtReg)) {
 285     if (UseInst.getParent() != MBB || ++C >= Limit) {
 286       MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
 287       // Cannot be live-out if there are no successors.
 288       return !MBB->succ_empty();
 289     }
 290   }
 291
 292   return false;
 293 }
 294
 295 /// Returns false if \p VirtReg is known to not be live into the current block.
 296 bool RegAllocFast::mayLiveIn(Register VirtReg) {
 297   if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg)))
 298     return !MBB->pred_empty();
 299
 300   // See if the first \p Limit def of the register are all in the current block.
 301   static const unsigned Limit = 8;
 302   unsigned C = 0;
 303   for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {
 304     if (DefInst.getParent() != MBB || ++C >= Limit) {
 305       MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
 306       return !MBB->pred_empty();
 307     }
 308   }
 309
 310   return false;
 311 }
 312
 313 /// Insert spill instruction for \p AssignedReg before \p Before. Update
 314 /// DBG_VALUEs with \p VirtReg operands with the stack slot.
 315 void RegAllocFast::spill(MachineBasicBlock::iterator Before, Register VirtReg,
 316                          MCPhysReg AssignedReg, bool Kill) {
 317   LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI)
 318                     << " in " << printReg(AssignedReg, TRI));
 319   int FI = getStackSpaceFor(VirtReg);
 320   LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n');
 321
 322   const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
 323   TII->storeRegToStackSlot(*MBB, Before, AssignedReg, Kill, FI, &RC, TRI);
 324   ++NumStores;
 325
 326   // If this register is used by DBG_VALUE then insert new DBG_VALUE to
 327   // identify spilled location as the place to find corresponding variable's
 328   // value.
 329   SmallVectorImpl<MachineInstr *> &LRIDbgValues = LiveDbgValueMap[VirtReg];
 330   for (MachineInstr *DBG : LRIDbgValues) {
 331     MachineInstr *NewDV = buildDbgValueForSpill(*MBB, Before, *DBG, FI);
 332     assert(NewDV->getParent() == MBB && "dangling parent pointer");
 333     (void)NewDV;
 334     LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);
 335   }
 336   // Now this register is spilled there is should not be any DBG_VALUE
 337   // pointing to this register because they are all pointing to spilled value
 338   // now.
 339   LRIDbgValues.clear();
 340 }
 341
 342 /// Insert reload instruction for \p PhysReg before \p Before.
 343 void RegAllocFast::reload(MachineBasicBlock::iterator Before, Register VirtReg,
 344                           MCPhysReg PhysReg) {
 345   LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
 346                     << printReg(PhysReg, TRI) << '\n');
 347   int FI = getStackSpaceFor(VirtReg);
 348   const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
 349   TII->loadRegFromStackSlot(*MBB, Before, PhysReg, FI, &RC, TRI);
 350   ++NumLoads;
 351 }
 352
 353 /// Return true if MO is the only remaining reference to its virtual register,
 354 /// and it is guaranteed to be a block-local register.
 355 bool RegAllocFast::isLastUseOfLocalReg(const MachineOperand &MO) const {
 356   // If the register has ever been spilled or reloaded, we conservatively assume
 357   // it is a global register used in multiple blocks.
 358   if (StackSlotForVirtReg[MO.getReg()] != -1)
 359     return false;
 360
 361   // Check that the use/def chain has exactly one operand - MO.
 362   MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(MO.getReg());
 363   if (&*I != &MO)
 364     return false;
 365   return ++I == MRI->reg_nodbg_end();
 366 }
 367
 368 /// Set kill flags on last use of a virtual register.
 369 void RegAllocFast::addKillFlag(const LiveReg &LR) {
 370   if (!LR.LastUse) return;
 371   MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum);
 372   if (MO.isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) {
 373     if (MO.getReg() == LR.PhysReg)
 374       MO.setIsKill();
 375     // else, don't do anything we are problably redefining a
 376     // subreg of this register and given we don't track which
 377     // lanes are actually dead, we cannot insert a kill flag here.
 378     // Otherwise we may end up in a situation like this:
 379     // ... = (MO) physreg:sub1, implicit killed physreg
 380     // ... <== Here we would allow later pass to reuse physreg:sub1
 381     //         which is potentially wrong.
 382     // LR:sub0 = ...
 383     // ... = LR.sub1 <== This is going to use physreg:sub1
 384   }
 385 }
 386
 387 #ifndef NDEBUG
 388 bool RegAllocFast::verifyRegStateMapping(const LiveReg &LR) const {
 389   for (MCRegUnitIterator UI(LR.PhysReg, TRI); UI.isValid(); ++UI) {
 390     if (RegUnitStates[*UI] != LR.VirtReg)
 391       return false;
 392   }
 393
 394   return true;
 395 }
 396 #endif
 397
 398 /// Mark virtreg as no longer available.
 399 void RegAllocFast::killVirtReg(LiveReg &LR) {
 400   assert(verifyRegStateMapping(LR) && "Broken RegState mapping");
 401   addKillFlag(LR);
 402   MCPhysReg PhysReg = LR.PhysReg;
 403   setPhysRegState(PhysReg, regFree);
 404   LR.PhysReg = 0;
 405 }
 406
 407 /// Mark virtreg as no longer available.
 408 void RegAllocFast::killVirtReg(Register VirtReg) {
 409   assert(Register::isVirtualRegister(VirtReg) &&
 410          "killVirtReg needs a virtual register");
 411   LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
 412   if (LRI != LiveVirtRegs.end() && LRI->PhysReg)
 413     killVirtReg(*LRI);
 414 }
 415
 416 /// This method spills the value specified by VirtReg into the corresponding
 417 /// stack slot if needed.
 418 void RegAllocFast::spillVirtReg(MachineBasicBlock::iterator MI,
 419                                 Register VirtReg) {
 420   assert(Register::isVirtualRegister(VirtReg) &&
 421          "Spilling a physical register is illegal!");
 422   LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
 423   assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
 424          "Spilling unmapped virtual register");
 425   spillVirtReg(MI, *LRI);
 426 }
 427
 428 /// Do the actual work of spilling.
 429 void RegAllocFast::spillVirtReg(MachineBasicBlock::iterator MI, LiveReg &LR) {
 430   assert(verifyRegStateMapping(LR) && "Broken RegState mapping");
 431
 432   MCPhysReg PhysReg = LR.PhysReg;
 433
 434   if (LR.Dirty) {
 435     // If this physreg is used by the instruction, we want to kill it on the
 436     // instruction, not on the spill.
 437     bool SpillKill = MachineBasicBlock::iterator(LR.LastUse) != MI;
 438     LR.Dirty = false;
 439
 440     spill(MI, LR.VirtReg, PhysReg, SpillKill);
 441
 442     if (SpillKill)
 443       LR.LastUse = nullptr; // Don't kill register again
 444   }
 445   killVirtReg(LR);
 446 }
 447
 448 /// Spill all dirty virtregs without killing them.
 449 void RegAllocFast::spillAll(MachineBasicBlock::iterator MI, bool OnlyLiveOut) {
 450   if (LiveVirtRegs.empty())
 451     return;
 452   // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
 453   // of spilling here is deterministic, if arbitrary.
 454   for (LiveReg &LR : LiveVirtRegs) {
 455     if (!LR.PhysReg)
 456       continue;
 457     if (OnlyLiveOut && !mayLiveOut(LR.VirtReg))
 458       continue;
 459     spillVirtReg(MI, LR);
 460   }
 461   LiveVirtRegs.clear();
 462 }
 463
 464 /// Handle the direct use of a physical register.  Check that the register is
 465 /// not used by a virtreg. Kill the physreg, marking it free. This may add
 466 /// implicit kills to MO->getParent() and invalidate MO.
 467 void RegAllocFast::usePhysReg(MachineOperand &MO) {
 468   // Ignore undef uses.
 469   if (MO.isUndef())
 470     return;
 471
 472   Register PhysReg = MO.getReg();
 473   assert(PhysReg.isPhysical() && "Bad usePhysReg operand");
 474
 475   markRegUsedInInstr(PhysReg);
 476
 477   for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
 478     switch (RegUnitStates[*UI]) {
 479     case regReserved:
 480       RegUnitStates[*UI] = regFree;
 481       LLVM_FALLTHROUGH;
 482     case regFree:
 483       break;
 484     default:
 485       llvm_unreachable("Unexpected reg unit state");
 486     }
 487   }
 488
 489   // All aliases are disabled, bring register into working set.
 490   setPhysRegState(PhysReg, regFree);
 491   MO.setIsKill();
 492 }
 493
 494 /// Mark PhysReg as reserved or free after spilling any virtregs. This is very
 495 /// similar to defineVirtReg except the physreg is reserved instead of
 496 /// allocated.
 497 void RegAllocFast::definePhysReg(MachineBasicBlock::iterator MI,
 498                                  MCPhysReg PhysReg, unsigned NewState) {
 499   for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
 500     switch (unsigned VirtReg = RegUnitStates[*UI]) {
 501     default:
 502       spillVirtReg(MI, VirtReg);
 503       break;
 504     case regFree:
 505     case regReserved:
 506       break;
 507     }
 508   }
 509
 510   markRegUsedInInstr(PhysReg);
 511   setPhysRegState(PhysReg, NewState);
 512 }
 513
 514 /// Return the cost of spilling clearing out PhysReg and aliases so it is free
 515 /// for allocation. Returns 0 when PhysReg is free or disabled with all aliases
 516 /// disabled - it can be allocated directly.
 517 /// \returns spillImpossible when PhysReg or an alias can't be spilled.
 518 unsigned RegAllocFast::calcSpillCost(MCPhysReg PhysReg) const {
 519   if (isRegUsedInInstr(PhysReg)) {
 520     LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI)
 521                       << " is already used in instr.\n");
 522     return spillImpossible;
 523   }
 524
 525   for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
 526     switch (unsigned VirtReg = RegUnitStates[*UI]) {
 527     case regFree:
 528       break;
 529     case regReserved:
 530       LLVM_DEBUG(dbgs() << printReg(VirtReg, TRI) << " corresponding "
 531                         << printReg(PhysReg, TRI) << " is reserved already.\n");
 532       return spillImpossible;
 533     default: {
 534       LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
 535       assert(LRI != LiveVirtRegs.end() && LRI->PhysReg &&
 536              "Missing VirtReg entry");
 537       return LRI->Dirty ? spillDirty : spillClean;
 538     }
 539     }
 540   }
 541   return 0;
 542 }
 543
 544 /// This method updates local state so that we know that PhysReg is the
 545 /// proper container for VirtReg now.  The physical register must not be used
 546 /// for anything else when this is called.
 547 void RegAllocFast::assignVirtToPhysReg(LiveReg &LR, MCPhysReg PhysReg) {
 548   Register VirtReg = LR.VirtReg;
 549   LLVM_DEBUG(dbgs() << "Assigning " << printReg(VirtReg, TRI) << " to "
 550                     << printReg(PhysReg, TRI) << '\n');
 551   assert(LR.PhysReg == 0 && "Already assigned a physreg");
 552   assert(PhysReg != 0 && "Trying to assign no register");
 553   LR.PhysReg = PhysReg;
 554   setPhysRegState(PhysReg, VirtReg);
 555 }
 556
 557 static bool isCoalescable(const MachineInstr &MI) {
 558   return MI.isFullCopy();
 559 }
 560
 561 Register RegAllocFast::traceCopyChain(Register Reg) const {
 562   static const unsigned ChainLengthLimit = 3;
 563   unsigned C = 0;
 564   do {
 565     if (Reg.isPhysical())
 566       return Reg;
 567     assert(Reg.isVirtual());
 568
 569     MachineInstr *VRegDef = MRI->getUniqueVRegDef(Reg);
 570     if (!VRegDef || !isCoalescable(*VRegDef))
 571       return 0;
 572     Reg = VRegDef->getOperand(1).getReg();
 573   } while (++C <= ChainLengthLimit);
 574   return 0;
 575 }
 576
 577 /// Check if any of \p VirtReg's definitions is a copy. If it is follow the
 578 /// chain of copies to check whether we reach a physical register we can
 579 /// coalesce with.
 580 Register RegAllocFast::traceCopies(Register VirtReg) const {
 581   static const unsigned DefLimit = 3;
 582   unsigned C = 0;
 583   for (const MachineInstr &MI : MRI->def_instructions(VirtReg)) {
 584     if (isCoalescable(MI)) {
 585       Register Reg = MI.getOperand(1).getReg();
 586       Reg = traceCopyChain(Reg);
 587       if (Reg.isValid())
 588         return Reg;
 589     }
 590
 591     if (++C >= DefLimit)
 592       break;
 593   }
 594   return Register();
 595 }
 596
 597 /// Allocates a physical register for VirtReg.
 598 void RegAllocFast::allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint0) {
 599   const Register VirtReg = LR.VirtReg;
 600
 601   assert(Register::isVirtualRegister(VirtReg) &&
 602          "Can only allocate virtual registers");
 603
 604   const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
 605   LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg)
 606                     << " in class " << TRI->getRegClassName(&RC)
 607                     << " with hint " << printReg(Hint0, TRI) << '\n');
 608
 609   // Take hint when possible.
 610   if (Hint0.isPhysical() && MRI->isAllocatable(Hint0) &&
 611       RC.contains(Hint0)) {
 612     // Ignore the hint if we would have to spill a dirty register.
 613     unsigned Cost = calcSpillCost(Hint0);
 614     if (Cost < spillDirty) {
 615       LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
 616                         << '\n');
 617       if (Cost)
 618         definePhysReg(MI, Hint0, regFree);
 619       assignVirtToPhysReg(LR, Hint0);
 620       return;
 621     } else {
 622       LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
 623                         << "occupied\n");
 624     }
 625   } else {
 626     Hint0 = Register();
 627   }
 628
 629   // Try other hint.
 630   Register Hint1 = traceCopies(VirtReg);
 631   if (Hint1.isPhysical() && MRI->isAllocatable(Hint1) &&
 632       RC.contains(Hint1) && !isRegUsedInInstr(Hint1)) {
 633     // Ignore the hint if we would have to spill a dirty register.
 634     unsigned Cost = calcSpillCost(Hint1);
 635     if (Cost < spillDirty) {
 636       LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
 637                         << '\n');
 638       if (Cost)
 639         definePhysReg(MI, Hint1, regFree);
 640       assignVirtToPhysReg(LR, Hint1);
 641       return;
 642     } else {
 643       LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
 644                         << "occupied\n");
 645     }
 646   } else {
 647     Hint1 = Register();
 648   }
 649
 650   MCPhysReg BestReg = 0;
 651   unsigned BestCost = spillImpossible;
 652   ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
 653   for (MCPhysReg PhysReg : AllocationOrder) {
 654     LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << ' ');
 655     unsigned Cost = calcSpillCost(PhysReg);
 656     LLVM_DEBUG(dbgs() << "Cost: " << Cost << " BestCost: " << BestCost << '\n');
 657     // Immediate take a register with cost 0.
 658     if (Cost == 0) {
 659       assignVirtToPhysReg(LR, PhysReg);
 660       return;
 661     }
 662
 663     if (PhysReg == Hint1 || PhysReg == Hint0)
 664       Cost -= spillPrefBonus;
 665
 666     if (Cost < BestCost) {
 667       BestReg = PhysReg;
 668       BestCost = Cost;
 669     }
 670   }
 671
 672   if (!BestReg) {
 673     // Nothing we can do: Report an error and keep going with an invalid
 674     // allocation.
 675     if (MI.isInlineAsm())
 676       MI.emitError("inline assembly requires more registers than available");
 677     else
 678       MI.emitError("ran out of registers during register allocation");
 679     definePhysReg(MI, *AllocationOrder.begin(), regFree);
 680     assignVirtToPhysReg(LR, *AllocationOrder.begin());
 681     return;
 682   }
 683
 684   definePhysReg(MI, BestReg, regFree);
 685   assignVirtToPhysReg(LR, BestReg);
 686 }
 687
 688 void RegAllocFast::allocVirtRegUndef(MachineOperand &MO) {
 689   assert(MO.isUndef() && "expected undef use");
 690   Register VirtReg = MO.getReg();
 691   assert(Register::isVirtualRegister(VirtReg) && "Expected virtreg");
 692
 693   LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
 694   MCPhysReg PhysReg;
 695   if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
 696     PhysReg = LRI->PhysReg;
 697   } else {
 698     const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
 699     ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
 700     assert(!AllocationOrder.empty() && "Allocation order must not be empty");
 701     PhysReg = AllocationOrder[0];
 702   }
 703
 704   unsigned SubRegIdx = MO.getSubReg();
 705   if (SubRegIdx != 0) {
 706     PhysReg = TRI->getSubReg(PhysReg, SubRegIdx);
 707     MO.setSubReg(0);
 708   }
 709   MO.setReg(PhysReg);
 710   MO.setIsRenamable(true);
 711 }
 712
 713 /// Allocates a register for VirtReg and mark it as dirty.
 714 MCPhysReg RegAllocFast::defineVirtReg(MachineInstr &MI, unsigned OpNum,
 715                                       Register VirtReg, Register Hint) {
 716   assert(Register::isVirtualRegister(VirtReg) && "Not a virtual register");
 717   LiveRegMap::iterator LRI;
 718   bool New;
 719   std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
 720   if (!LRI->PhysReg) {
 721     // If there is no hint, peek at the only use of this register.
 722     if ((!Hint || !Hint.isPhysical()) &&
 723         MRI->hasOneNonDBGUse(VirtReg)) {
 724       const MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(VirtReg);
 725       // It's a copy, use the destination register as a hint.
 726       if (UseMI.isCopyLike())
 727         Hint = UseMI.getOperand(0).getReg();
 728     }
 729     allocVirtReg(MI, *LRI, Hint);
 730   } else if (LRI->LastUse) {
 731     // Redefining a live register - kill at the last use, unless it is this
 732     // instruction defining VirtReg multiple times.
 733     if (LRI->LastUse != &MI || LRI->LastUse->getOperand(LRI->LastOpNum).isUse())
 734       addKillFlag(*LRI);
 735   }
 736   assert(LRI->PhysReg && "Register not assigned");
 737   LRI->LastUse = &MI;
 738   LRI->LastOpNum = OpNum;
 739   LRI->Dirty = true;
 740   markRegUsedInInstr(LRI->PhysReg);
 741   return LRI->PhysReg;
 742 }
 743
 744 /// Make sure VirtReg is available in a physreg and return it.
 745 RegAllocFast::LiveReg &RegAllocFast::reloadVirtReg(MachineInstr &MI,
 746                                                    unsigned OpNum,
 747                                                    Register VirtReg,
 748                                                    Register Hint) {
 749   assert(Register::isVirtualRegister(VirtReg) && "Not a virtual register");
 750   LiveRegMap::iterator LRI;
 751   bool New;
 752   std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
 753   MachineOperand &MO = MI.getOperand(OpNum);
 754   if (!LRI->PhysReg) {
 755     allocVirtReg(MI, *LRI, Hint);
 756     reload(MI, VirtReg, LRI->PhysReg);
 757   } else if (LRI->Dirty) {
 758     if (isLastUseOfLocalReg(MO)) {
 759       LLVM_DEBUG(dbgs() << "Killing last use: " << MO << '\n');
 760       if (MO.isUse())
 761         MO.setIsKill();
 762       else
 763         MO.setIsDead();
 764     } else if (MO.isKill()) {
 765       LLVM_DEBUG(dbgs() << "Clearing dubious kill: " << MO << '\n');
 766       MO.setIsKill(false);
 767     } else if (MO.isDead()) {
 768       LLVM_DEBUG(dbgs() << "Clearing dubious dead: " << MO << '\n');
 769       MO.setIsDead(false);
 770     }
 771   } else if (MO.isKill()) {
 772     // We must remove kill flags from uses of reloaded registers because the
 773     // register would be killed immediately, and there might be a second use:
 774     //   %foo = OR killed %x, %x
 775     // This would cause a second reload of %x into a different register.
 776     LLVM_DEBUG(dbgs() << "Clearing clean kill: " << MO << '\n');
 777     MO.setIsKill(false);
 778   } else if (MO.isDead()) {
 779     LLVM_DEBUG(dbgs() << "Clearing clean dead: " << MO << '\n');
 780     MO.setIsDead(false);
 781   }
 782   assert(LRI->PhysReg && "Register not assigned");
 783   LRI->LastUse = &MI;
 784   LRI->LastOpNum = OpNum;
 785   markRegUsedInInstr(LRI->PhysReg);
 786   return *LRI;
 787 }
 788
 789 /// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This
 790 /// may invalidate any operand pointers.  Return true if the operand kills its
 791 /// register.
 792 bool RegAllocFast::setPhysReg(MachineInstr &MI, MachineOperand &MO,
 793                               MCPhysReg PhysReg) {
 794   bool Dead = MO.isDead();
 795   if (!MO.getSubReg()) {
 796     MO.setReg(PhysReg);
 797     MO.setIsRenamable(true);
 798     return MO.isKill() || Dead;
 799   }
 800
 801   // Handle subregister index.
 802   MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : Register());
 803   MO.setIsRenamable(true);
 804   MO.setSubReg(0);
 805
 806   // A kill flag implies killing the full register. Add corresponding super
 807   // register kill.
 808   if (MO.isKill()) {
 809     MI.addRegisterKilled(PhysReg, TRI, true);
 810     return true;
 811   }
 812
 813   // A <def,read-undef> of a sub-register requires an implicit def of the full
 814   // register.
 815   if (MO.isDef() && MO.isUndef())
 816     MI.addRegisterDefined(PhysReg, TRI);
 817
 818   return Dead;
 819 }
 820
 821 // Handles special instruction operand like early clobbers and tied ops when
 822 // there are additional physreg defines.
 823 void RegAllocFast::handleThroughOperands(MachineInstr &MI,
 824                                          SmallVectorImpl<Register> &VirtDead) {
 825   LLVM_DEBUG(dbgs() << "Scanning for through registers:");
 826   SmallSet<Register, 8> ThroughRegs;
 827   for (const MachineOperand &MO : MI.operands()) {
 828     if (!MO.isReg()) continue;
 829     Register Reg = MO.getReg();
 830     if (!Reg.isVirtual())
 831       continue;
 832     if (MO.isEarlyClobber() || (MO.isUse() && MO.isTied()) ||
 833         (MO.getSubReg() && MI.readsVirtualRegister(Reg))) {
 834       if (ThroughRegs.insert(Reg).second)
 835         LLVM_DEBUG(dbgs() << ' ' << printReg(Reg));
 836     }
 837   }
 838
 839   // If any physreg defines collide with preallocated through registers,
 840   // we must spill and reallocate.
 841   LLVM_DEBUG(dbgs() << "\nChecking for physdef collisions.\n");
 842   for (const MachineOperand &MO : MI.operands()) {
 843     if (!MO.isReg() || !MO.isDef()) continue;
 844     Register Reg = MO.getReg();
 845     if (!Reg || !Reg.isPhysical())
 846       continue;
 847     markRegUsedInInstr(Reg);
 848
 849     for (MCRegUnitIterator UI(Reg, TRI); UI.isValid(); ++UI) {
 850       if (!ThroughRegs.count(RegUnitStates[*UI]))
 851         continue;
 852
 853       // Need to spill any aliasing registers.
 854       for (MCRegUnitRootIterator RI(*UI, TRI); RI.isValid(); ++RI) {
 855         for (MCSuperRegIterator SI(*RI, TRI, true); SI.isValid(); ++SI) {
 856           definePhysReg(MI, *SI, regFree);
 857         }
 858       }
 859     }
 860   }
 861
 862   SmallVector<Register, 8> PartialDefs;
 863   LLVM_DEBUG(dbgs() << "Allocating tied uses.\n");
 864   for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
 865     MachineOperand &MO = MI.getOperand(I);
 866     if (!MO.isReg()) continue;
 867     Register Reg = MO.getReg();
 868     if (!Register::isVirtualRegister(Reg))
 869       continue;
 870     if (MO.isUse()) {
 871       if (!MO.isTied()) continue;
 872       LLVM_DEBUG(dbgs() << "Operand " << I << "(" << MO
 873                         << ") is tied to operand " << MI.findTiedOperandIdx(I)
 874                         << ".\n");
 875       LiveReg &LR = reloadVirtReg(MI, I, Reg, 0);
 876       MCPhysReg PhysReg = LR.PhysReg;
 877       setPhysReg(MI, MO, PhysReg);
 878       // Note: we don't update the def operand yet. That would cause the normal
 879       // def-scan to attempt spilling.
 880     } else if (MO.getSubReg() && MI.readsVirtualRegister(Reg)) {
 881       LLVM_DEBUG(dbgs() << "Partial redefine: " << MO << '\n');
 882       // Reload the register, but don't assign to the operand just yet.
 883       // That would confuse the later phys-def processing pass.
 884       LiveReg &LR = reloadVirtReg(MI, I, Reg, 0);
 885       PartialDefs.push_back(LR.PhysReg);
 886     }
 887   }
 888
 889   LLVM_DEBUG(dbgs() << "Allocating early clobbers.\n");
 890   for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
 891     const MachineOperand &MO = MI.getOperand(I);
 892     if (!MO.isReg()) continue;
 893     Register Reg = MO.getReg();
 894     if (!Register::isVirtualRegister(Reg))
 895       continue;
 896     if (!MO.isEarlyClobber())
 897       continue;
 898     // Note: defineVirtReg may invalidate MO.
 899     MCPhysReg PhysReg = defineVirtReg(MI, I, Reg, 0);
 900     if (setPhysReg(MI, MI.getOperand(I), PhysReg))
 901       VirtDead.push_back(Reg);
 902   }
 903
 904   // Restore UsedInInstr to a state usable for allocating normal virtual uses.
 905   UsedInInstr.clear();
 906   for (const MachineOperand &MO : MI.operands()) {
 907     if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue;
 908     Register Reg = MO.getReg();
 909     if (!Reg || !Reg.isPhysical())
 910       continue;
 911     LLVM_DEBUG(dbgs() << "\tSetting " << printReg(Reg, TRI)
 912                       << " as used in instr\n");
 913     markRegUsedInInstr(Reg);
 914   }
 915
 916   // Also mark PartialDefs as used to avoid reallocation.
 917   for (Register PartialDef : PartialDefs)
 918     markRegUsedInInstr(PartialDef);
 919 }
 920
 921 #ifndef NDEBUG
 922
 923 void RegAllocFast::dumpState() const {
 924   for (unsigned Unit = 1, UnitE = TRI->getNumRegUnits(); Unit != UnitE;
 925        ++Unit) {
 926     switch (unsigned VirtReg = RegUnitStates[Unit]) {
 927     case regFree:
 928       break;
 929     case regReserved:
 930       dbgs() << " " << printRegUnit(Unit, TRI) << "[P]";
 931       break;
 932     default: {
 933       dbgs() << ' ' << printRegUnit(Unit, TRI) << '=' << printReg(VirtReg);
 934       LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
 935       assert(I != LiveVirtRegs.end() && "have LiveVirtRegs entry");
 936       if (I->Dirty)
 937         dbgs() << "[D]";
 938       assert(TRI->hasRegUnit(I->PhysReg, Unit) && "inverse mapping present");
 939       break;
 940     }
 941     }
 942   }
 943   dbgs() << '\n';
 944   // Check that LiveVirtRegs is the inverse.
 945   for (const LiveReg &LR : LiveVirtRegs) {
 946     Register VirtReg = LR.VirtReg;
 947     assert(VirtReg.isVirtual() && "Bad map key");
 948     MCPhysReg PhysReg = LR.PhysReg;
 949     if (PhysReg != 0) {
 950       assert(Register::isPhysicalRegister(PhysReg) &&
 951              "mapped to physreg");
 952       for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
 953         assert(RegUnitStates[*UI] == VirtReg && "inverse map valid");
 954       }
 955     }
 956   }
 957 }
 958 #endif
 959
 960 void RegAllocFast::allocateInstruction(MachineInstr &MI) {
 961   const MCInstrDesc &MCID = MI.getDesc();
 962
 963   // If this is a copy, we may be able to coalesce.
 964   Register CopySrcReg;
 965   Register CopyDstReg;
 966   unsigned CopySrcSub = 0;
 967   unsigned CopyDstSub = 0;
 968   if (MI.isCopy()) {
 969     CopyDstReg = MI.getOperand(0).getReg();
 970     CopySrcReg = MI.getOperand(1).getReg();
 971     CopyDstSub = MI.getOperand(0).getSubReg();
 972     CopySrcSub = MI.getOperand(1).getSubReg();
 973   }
 974
 975   // Track registers used by instruction.
 976   UsedInInstr.clear();
 977
 978   // First scan.
 979   // Mark physreg uses and early clobbers as used.
 980   // Find the end of the virtreg operands
 981   unsigned VirtOpEnd = 0;
 982   bool hasTiedOps = false;
 983   bool hasEarlyClobbers = false;
 984   bool hasPartialRedefs = false;
 985   bool hasPhysDefs = false;
 986   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 987     MachineOperand &MO = MI.getOperand(i);
 988     // Make sure MRI knows about registers clobbered by regmasks.
 989     if (MO.isRegMask()) {
 990       MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
 991       continue;
 992     }
 993     if (!MO.isReg()) continue;
 994     Register Reg = MO.getReg();
 995     if (!Reg) continue;
 996     if (Register::isVirtualRegister(Reg)) {
 997       VirtOpEnd = i+1;
 998       if (MO.isUse()) {
 999         hasTiedOps = hasTiedOps ||
1000                             MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1;
1001       } else {
1002         if (MO.isEarlyClobber())
1003           hasEarlyClobbers = true;
1004         if (MO.getSubReg() && MI.readsVirtualRegister(Reg))
1005           hasPartialRedefs = true;
1006       }
1007       continue;
1008     }
1009     if (!MRI->isAllocatable(Reg)) continue;
1010     if (MO.isUse()) {
1011       usePhysReg(MO);
1012     } else if (MO.isEarlyClobber()) {
1013       definePhysReg(MI, Reg,
1014                     (MO.isImplicit() || MO.isDead()) ? regFree : regReserved);
1015       hasEarlyClobbers = true;
1016     } else
1017       hasPhysDefs = true;
1018   }
1019
1020   // The instruction may have virtual register operands that must be allocated
1021   // the same register at use-time and def-time: early clobbers and tied
1022   // operands. If there are also physical defs, these registers must avoid
1023   // both physical defs and uses, making them more constrained than normal
1024   // operands.
1025   // Similarly, if there are multiple defs and tied operands, we must make
1026   // sure the same register is allocated to uses and defs.
1027   // We didn't detect inline asm tied operands above, so just make this extra
1028   // pass for all inline asm.
1029   if (MI.isInlineAsm() || hasEarlyClobbers || hasPartialRedefs ||
1030       (hasTiedOps && (hasPhysDefs || MCID.getNumDefs() > 1))) {
1031     handleThroughOperands(MI, VirtDead);
1032     // Don't attempt coalescing when we have funny stuff going on.
1033     CopyDstReg = Register();
1034     // Pretend we have early clobbers so the use operands get marked below.
1035     // This is not necessary for the common case of a single tied use.
1036     hasEarlyClobbers = true;
1037   }
1038
1039   // Second scan.
1040   // Allocate virtreg uses.
1041   bool HasUndefUse = false;
1042   for (unsigned I = 0; I != VirtOpEnd; ++I) {
1043     MachineOperand &MO = MI.getOperand(I);
1044     if (!MO.isReg()) continue;
1045     Register Reg = MO.getReg();
1046     if (!Reg.isVirtual())
1047       continue;
1048     if (MO.isUse()) {
1049       if (MO.isUndef()) {
1050         HasUndefUse = true;
1051         // There is no need to allocate a register for an undef use.
1052         continue;
1053       }
1054
1055       // Populate MayLiveAcrossBlocks in case the use block is allocated before
1056       // the def block (removing the vreg uses).
1057       mayLiveIn(Reg);
1058
1059       LiveReg &LR = reloadVirtReg(MI, I, Reg, CopyDstReg);
1060       MCPhysReg PhysReg = LR.PhysReg;
1061       CopySrcReg = (CopySrcReg == Reg || CopySrcReg == PhysReg) ? PhysReg : 0;
1062       if (setPhysReg(MI, MO, PhysReg))
1063         killVirtReg(LR);
1064     }
1065   }
1066
1067   // Allocate undef operands. This is a separate step because in a situation
1068   // like  ` = OP undef %X, %X`    both operands need the same register assign
1069   // so we should perform the normal assignment first.
1070   if (HasUndefUse) {
1071     for (MachineOperand &MO : MI.uses()) {
1072       if (!MO.isReg() || !MO.isUse())
1073         continue;
1074       Register Reg = MO.getReg();
1075       if (!Reg.isVirtual())
1076         continue;
1077
1078       assert(MO.isUndef() && "Should only have undef virtreg uses left");
1079       allocVirtRegUndef(MO);
1080     }
1081   }
1082
1083   // Track registers defined by instruction - early clobbers and tied uses at
1084   // this point.
1085   UsedInInstr.clear();
1086   if (hasEarlyClobbers) {
1087     for (const MachineOperand &MO : MI.operands()) {
1088       if (!MO.isReg()) continue;
1089       Register Reg = MO.getReg();
1090       if (!Reg || !Reg.isPhysical())
1091         continue;
1092       // Look for physreg defs and tied uses.
1093       if (!MO.isDef() && !MO.isTied()) continue;
1094       markRegUsedInInstr(Reg);
1095     }
1096   }
1097
1098   unsigned DefOpEnd = MI.getNumOperands();
1099   if (MI.isCall()) {
1100     // Spill all virtregs before a call. This serves one purpose: If an
1101     // exception is thrown, the landing pad is going to expect to find
1102     // registers in their spill slots.
1103     // Note: although this is appealing to just consider all definitions
1104     // as call-clobbered, this is not correct because some of those
1105     // definitions may be used later on and we do not want to reuse
1106     // those for virtual registers in between.
1107     LLVM_DEBUG(dbgs() << "  Spilling remaining registers before call.\n");
1108     spillAll(MI, /*OnlyLiveOut*/ false);
1109   }
1110
1111   // Third scan.
1112   // Mark all physreg defs as used before allocating virtreg defs.
1113   for (unsigned I = 0; I != DefOpEnd; ++I) {
1114     const MachineOperand &MO = MI.getOperand(I);
1115     if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber())
1116       continue;
1117     Register Reg = MO.getReg();
1118
1119     if (!Reg || !Reg.isPhysical() || !MRI->isAllocatable(Reg))
1120       continue;
1121     definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved);
1122   }
1123
1124   // Fourth scan.
1125   // Allocate defs and collect dead defs.
1126   for (unsigned I = 0; I != DefOpEnd; ++I) {
1127     const MachineOperand &MO = MI.getOperand(I);
1128     if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber())
1129       continue;
1130     Register Reg = MO.getReg();
1131
1132     // We have already dealt with phys regs in the previous scan.
1133     if (Reg.isPhysical())
1134       continue;
1135     MCPhysReg PhysReg = defineVirtReg(MI, I, Reg, CopySrcReg);
1136     if (setPhysReg(MI, MI.getOperand(I), PhysReg)) {
1137       VirtDead.push_back(Reg);
1138       CopyDstReg = Register(); // cancel coalescing;
1139     } else
1140       CopyDstReg = (CopyDstReg == Reg || CopyDstReg == PhysReg) ? PhysReg : 0;
1141   }
1142
1143   // Kill dead defs after the scan to ensure that multiple defs of the same
1144   // register are allocated identically. We didn't need to do this for uses
1145   // because we are crerating our own kill flags, and they are always at the
1146   // last use.
1147   for (Register VirtReg : VirtDead)
1148     killVirtReg(VirtReg);
1149   VirtDead.clear();
1150
1151   LLVM_DEBUG(dbgs() << "<< " << MI);
1152   if (CopyDstReg && CopyDstReg == CopySrcReg && CopyDstSub == CopySrcSub) {
1153     LLVM_DEBUG(dbgs() << "Mark identity copy for removal\n");
1154     Coalesced.push_back(&MI);
1155   }
1156 }
1157
1158 void RegAllocFast::handleDebugValue(MachineInstr &MI) {
1159   MachineOperand &MO = MI.getDebugOperand(0);
1160
1161   // Ignore DBG_VALUEs that aren't based on virtual registers. These are
1162   // mostly constants and frame indices.
1163   if (!MO.isReg())
1164     return;
1165   Register Reg = MO.getReg();
1166   if (!Register::isVirtualRegister(Reg))
1167     return;
1168
1169   // See if this virtual register has already been allocated to a physical
1170   // register or spilled to a stack slot.
1171   LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
1172   if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
1173     setPhysReg(MI, MO, LRI->PhysReg);
1174   } else {
1175     int SS = StackSlotForVirtReg[Reg];
1176     if (SS != -1) {
1177       // Modify DBG_VALUE now that the value is in a spill slot.
1178       updateDbgValueForSpill(MI, SS);
1179       LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << MI);
1180       return;
1181     }
1182
1183     // We can't allocate a physreg for a DebugValue, sorry!
1184     LLVM_DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
1185     MO.setReg(Register());
1186   }
1187
1188   // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so
1189   // that future spills of Reg will have DBG_VALUEs.
1190   LiveDbgValueMap[Reg].push_back(&MI);
1191 }
1192
1193 void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) {
1194   this->MBB = &MBB;
1195   LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);
1196
1197   RegUnitStates.assign(TRI->getNumRegUnits(), regFree);
1198   assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
1199
1200   MachineBasicBlock::iterator MII = MBB.begin();
1201
1202   // Add live-in registers as live.
1203   for (const MachineBasicBlock::RegisterMaskPair &LI : MBB.liveins())
1204     if (MRI->isAllocatable(LI.PhysReg))
1205       definePhysReg(MII, LI.PhysReg, regReserved);
1206
1207   VirtDead.clear();
1208   Coalesced.clear();
1209
1210   // Otherwise, sequentially allocate each instruction in the MBB.
1211   for (MachineInstr &MI : MBB) {
1212     LLVM_DEBUG(
1213       dbgs() << "\n>> " << MI << "Regs:";
1214       dumpState()
1215     );
1216
1217     // Special handling for debug values. Note that they are not allowed to
1218     // affect codegen of the other instructions in any way.
1219     if (MI.isDebugValue()) {
1220       handleDebugValue(MI);
1221       continue;
1222     }
1223
1224     allocateInstruction(MI);
1225   }
1226
1227   // Spill all physical registers holding virtual registers now.
1228   LLVM_DEBUG(dbgs() << "Spilling live registers at end of block.\n");
1229   spillAll(MBB.getFirstTerminator(), /*OnlyLiveOut*/ true);
1230
1231   // Erase all the coalesced copies. We are delaying it until now because
1232   // LiveVirtRegs might refer to the instrs.
1233   for (MachineInstr *MI : Coalesced)
1234     MBB.erase(MI);
1235   NumCoalesced += Coalesced.size();
1236
1237   LLVM_DEBUG(MBB.dump());
1238 }
1239
1240 bool RegAllocFast::runOnMachineFunction(MachineFunction &MF) {
1241   LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1242                     << "********** Function: " << MF.getName() << '\n');
1243   MRI = &MF.getRegInfo();
1244   const TargetSubtargetInfo &STI = MF.getSubtarget();
1245   TRI = STI.getRegisterInfo();
1246   TII = STI.getInstrInfo();
1247   MFI = &MF.getFrameInfo();
1248   MRI->freezeReservedRegs(MF);
1249   RegClassInfo.runOnMachineFunction(MF);
1250   UsedInInstr.clear();
1251   UsedInInstr.setUniverse(TRI->getNumRegUnits());
1252
1253   // initialize the virtual->physical register map to have a 'null'
1254   // mapping for all virtual registers
1255   unsigned NumVirtRegs = MRI->getNumVirtRegs();
1256   StackSlotForVirtReg.resize(NumVirtRegs);
1257   LiveVirtRegs.setUniverse(NumVirtRegs);
1258   MayLiveAcrossBlocks.clear();
1259   MayLiveAcrossBlocks.resize(NumVirtRegs);
1260
1261   // Loop over all of the basic blocks, eliminating virtual register references
1262   for (MachineBasicBlock &MBB : MF)
1263     allocateBasicBlock(MBB);
1264
1265   // All machine operands and other references to virtual registers have been
1266   // replaced. Remove the virtual registers.
1267   MRI->clearVirtRegs();
1268
1269   StackSlotForVirtReg.clear();
1270   LiveDbgValueMap.clear();
1271   return true;
1272 }
1273
1274 FunctionPass *llvm::createFastRegisterAllocator() {
1275   return new RegAllocFast();
1276 }