1924 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9/// \file This register allocator allocates registers to a basic block at a10/// time, attempting to keep values in registers and reusing registers as11/// appropriate.12//13//===----------------------------------------------------------------------===//14 15#include "llvm/CodeGen/RegAllocFast.h"16#include "llvm/ADT/ArrayRef.h"17#include "llvm/ADT/DenseMap.h"18#include "llvm/ADT/IndexedMap.h"19#include "llvm/ADT/MapVector.h"20#include "llvm/ADT/SmallSet.h"21#include "llvm/ADT/SmallVector.h"22#include "llvm/ADT/SparseSet.h"23#include "llvm/ADT/Statistic.h"24#include "llvm/CodeGen/MachineBasicBlock.h"25#include "llvm/CodeGen/MachineFrameInfo.h"26#include "llvm/CodeGen/MachineFunction.h"27#include "llvm/CodeGen/MachineFunctionPass.h"28#include "llvm/CodeGen/MachineInstr.h"29#include "llvm/CodeGen/MachineInstrBuilder.h"30#include "llvm/CodeGen/MachineOperand.h"31#include "llvm/CodeGen/MachineRegisterInfo.h"32#include "llvm/CodeGen/RegAllocCommon.h"33#include "llvm/CodeGen/RegAllocRegistry.h"34#include "llvm/CodeGen/RegisterClassInfo.h"35#include "llvm/CodeGen/TargetInstrInfo.h"36#include "llvm/CodeGen/TargetOpcodes.h"37#include "llvm/CodeGen/TargetRegisterInfo.h"38#include "llvm/CodeGen/TargetSubtargetInfo.h"39#include "llvm/InitializePasses.h"40#include "llvm/MC/MCRegisterInfo.h"41#include "llvm/Pass.h"42#include "llvm/Support/Debug.h"43#include "llvm/Support/ErrorHandling.h"44#include "llvm/Support/raw_ostream.h"45#include <cassert>46#include <tuple>47#include <vector>48 49using namespace llvm;50 51#define DEBUG_TYPE "regalloc"52 53STATISTIC(NumStores, "Number of stores added");54STATISTIC(NumLoads, "Number of loads added");55STATISTIC(NumCoalesced, "Number of copies coalesced");56 57// FIXME: Remove this switch when all testcases are fixed!58static cl::opt<bool> IgnoreMissingDefs("rafast-ignore-missing-defs",59 cl::Hidden);60 61static RegisterRegAlloc fastRegAlloc("fast", "fast register allocator",62 createFastRegisterAllocator);63 64namespace {65 66/// Assign ascending index for instructions in machine basic block. The index67/// can be used to determine dominance between instructions in same MBB.68class InstrPosIndexes {69public:70 void unsetInitialized() { IsInitialized = false; }71 72 void init(const MachineBasicBlock &MBB) {73 CurMBB = &MBB;74 Instr2PosIndex.clear();75 uint64_t LastIndex = 0;76 for (const MachineInstr &MI : MBB) {77 LastIndex += InstrDist;78 Instr2PosIndex[&MI] = LastIndex;79 }80 }81 82 /// Set \p Index to index of \p MI. If \p MI is new inserted, it try to assign83 /// index without affecting existing instruction's index. Return true if all84 /// instructions index has been reassigned.85 bool getIndex(const MachineInstr &MI, uint64_t &Index) {86 if (!IsInitialized) {87 init(*MI.getParent());88 IsInitialized = true;89 Index = Instr2PosIndex.at(&MI);90 return true;91 }92 93 assert(MI.getParent() == CurMBB && "MI is not in CurMBB");94 auto It = Instr2PosIndex.find(&MI);95 if (It != Instr2PosIndex.end()) {96 Index = It->second;97 return false;98 }99 100 // Distance is the number of consecutive unassigned instructions including101 // MI. Start is the first instruction of them. End is the next of last102 // instruction of them.103 // e.g.104 // |Instruction| A | B | C | MI | D | E |105 // | Index | 1024 | | | | | 2048 |106 //107 // In this case, B, C, MI, D are unassigned. Distance is 4, Start is B, End108 // is E.109 unsigned Distance = 1;110 MachineBasicBlock::const_iterator Start = MI.getIterator(),111 End = std::next(Start);112 while (Start != CurMBB->begin() &&113 !Instr2PosIndex.count(&*std::prev(Start))) {114 --Start;115 ++Distance;116 }117 while (End != CurMBB->end() && !Instr2PosIndex.count(&*(End))) {118 ++End;119 ++Distance;120 }121 122 // LastIndex is initialized to last used index prior to MI or zero.123 // In previous example, LastIndex is 1024, EndIndex is 2048;124 uint64_t LastIndex =125 Start == CurMBB->begin() ? 0 : Instr2PosIndex.at(&*std::prev(Start));126 uint64_t Step;127 if (End == CurMBB->end())128 Step = static_cast<uint64_t>(InstrDist);129 else {130 // No instruction uses index zero.131 uint64_t EndIndex = Instr2PosIndex.at(&*End);132 assert(EndIndex > LastIndex && "Index must be ascending order");133 unsigned NumAvailableIndexes = EndIndex - LastIndex - 1;134 // We want index gap between two adjacent MI is as same as possible. Given135 // total A available indexes, D is number of consecutive unassigned136 // instructions, S is the step.137 // |<- S-1 -> MI <- S-1 -> MI <- A-S*D ->|138 // There're S-1 available indexes between unassigned instruction and its139 // predecessor. There're A-S*D available indexes between the last140 // unassigned instruction and its successor.141 // Ideally, we want142 // S-1 = A-S*D143 // then144 // S = (A+1)/(D+1)145 // An valid S must be integer greater than zero, so146 // S <= (A+1)/(D+1)147 // =>148 // A-S*D >= 0149 // That means we can safely use (A+1)/(D+1) as step.150 // In previous example, Step is 204, Index of B, C, MI, D is 1228, 1432,151 // 1636, 1840.152 Step = (NumAvailableIndexes + 1) / (Distance + 1);153 }154 155 // Reassign index for all instructions if number of new inserted156 // instructions exceed slot or all instructions are new.157 if (LLVM_UNLIKELY(!Step || (!LastIndex && Step == InstrDist))) {158 init(*CurMBB);159 Index = Instr2PosIndex.at(&MI);160 return true;161 }162 163 for (auto I = Start; I != End; ++I) {164 LastIndex += Step;165 Instr2PosIndex[&*I] = LastIndex;166 }167 Index = Instr2PosIndex.at(&MI);168 return false;169 }170 171private:172 bool IsInitialized = false;173 enum { InstrDist = 1024 };174 const MachineBasicBlock *CurMBB = nullptr;175 DenseMap<const MachineInstr *, uint64_t> Instr2PosIndex;176};177 178class RegAllocFastImpl {179public:180 RegAllocFastImpl(const RegAllocFilterFunc F = nullptr,181 bool ClearVirtRegs_ = true)182 : ShouldAllocateRegisterImpl(F), StackSlotForVirtReg(-1),183 ClearVirtRegs(ClearVirtRegs_) {}184 185private:186 MachineFrameInfo *MFI = nullptr;187 MachineRegisterInfo *MRI = nullptr;188 const TargetRegisterInfo *TRI = nullptr;189 const TargetInstrInfo *TII = nullptr;190 RegisterClassInfo RegClassInfo;191 const RegAllocFilterFunc ShouldAllocateRegisterImpl;192 193 /// Basic block currently being allocated.194 MachineBasicBlock *MBB = nullptr;195 196 /// Maps virtual regs to the frame index where these values are spilled.197 IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;198 199 /// Everything we know about a live virtual register.200 struct LiveReg {201 MachineInstr *LastUse = nullptr; ///< Last instr to use reg.202 Register VirtReg; ///< Virtual register number.203 MCPhysReg PhysReg = 0; ///< Currently held here.204 bool LiveOut = false; ///< Register is possibly live out.205 bool Reloaded = false; ///< Register was reloaded.206 bool Error = false; ///< Could not allocate.207 208 explicit LiveReg(Register VirtReg) : VirtReg(VirtReg) {}209 explicit LiveReg() = default;210 211 unsigned getSparseSetIndex() const { return VirtReg.virtRegIndex(); }212 };213 214 using LiveRegMap = SparseSet<LiveReg, unsigned, identity, uint16_t>;215 /// This map contains entries for each virtual register that is currently216 /// available in a physical register.217 LiveRegMap LiveVirtRegs;218 219 /// Stores assigned virtual registers present in the bundle MI.220 DenseMap<Register, LiveReg> BundleVirtRegsMap;221 222 DenseMap<Register, SmallVector<MachineOperand *, 2>> LiveDbgValueMap;223 /// List of DBG_VALUE that we encountered without the vreg being assigned224 /// because they were placed after the last use of the vreg.225 DenseMap<Register, SmallVector<MachineInstr *, 1>> DanglingDbgValues;226 227 /// Has a bit set for every virtual register for which it was determined228 /// that it is alive across blocks.229 BitVector MayLiveAcrossBlocks;230 231 /// State of a register unit.232 enum RegUnitState {233 /// A free register is not currently in use and can be allocated234 /// immediately without checking aliases.235 regFree,236 237 /// A pre-assigned register has been assigned before register allocation238 /// (e.g., setting up a call parameter).239 regPreAssigned,240 241 /// Used temporarily in reloadAtBegin() to mark register units that are242 /// live-in to the basic block.243 regLiveIn,244 245 /// A register state may also be a virtual register number, indication246 /// that the physical register is currently allocated to a virtual247 /// register. In that case, LiveVirtRegs contains the inverse mapping.248 };249 250 /// Maps each physical register to a RegUnitState enum or virtual register.251 std::vector<unsigned> RegUnitStates;252 253 SmallVector<MachineInstr *, 32> Coalesced;254 255 /// Track register units that are used in the current instruction, and so256 /// cannot be allocated.257 ///258 /// In the first phase (tied defs/early clobber), we consider also physical259 /// uses, afterwards, we don't. If the lowest bit isn't set, it's a solely260 /// physical use (markPhysRegUsedInInstr), otherwise, it's a normal use. To261 /// avoid resetting the entire vector after every instruction, we track the262 /// instruction "generation" in the remaining 31 bits -- this means, that if263 /// UsedInInstr[Idx] < InstrGen, the register unit is unused. InstrGen is264 /// never zero and always incremented by two.265 ///266 /// Don't allocate inline storage: the number of register units is typically267 /// quite large (e.g., AArch64 > 100, X86 > 200, AMDGPU > 1000).268 uint32_t InstrGen;269 SmallVector<unsigned, 0> UsedInInstr;270 271 SmallVector<unsigned, 8> DefOperandIndexes;272 // Register masks attached to the current instruction.273 SmallVector<const uint32_t *> RegMasks;274 275 // Assign index for each instruction to quickly determine dominance.276 InstrPosIndexes PosIndexes;277 278 void setRegUnitState(MCRegUnit Unit, unsigned NewState);279 unsigned getRegUnitState(MCRegUnit Unit) const;280 281 void setPhysRegState(MCRegister PhysReg, unsigned NewState);282 bool isPhysRegFree(MCRegister PhysReg) const;283 284 /// Mark a physreg as used in this instruction.285 void markRegUsedInInstr(MCPhysReg PhysReg) {286 for (MCRegUnit Unit : TRI->regunits(PhysReg))287 UsedInInstr[static_cast<unsigned>(Unit)] = InstrGen | 1;288 }289 290 // Check if physreg is clobbered by instruction's regmask(s).291 bool isClobberedByRegMasks(MCRegister PhysReg) const {292 return llvm::any_of(RegMasks, [PhysReg](const uint32_t *Mask) {293 return MachineOperand::clobbersPhysReg(Mask, PhysReg);294 });295 }296 297 /// Check if a physreg or any of its aliases are used in this instruction.298 bool isRegUsedInInstr(MCRegister PhysReg, bool LookAtPhysRegUses) const {299 if (LookAtPhysRegUses && isClobberedByRegMasks(PhysReg))300 return true;301 for (MCRegUnit Unit : TRI->regunits(PhysReg))302 if (UsedInInstr[static_cast<unsigned>(Unit)] >=303 (InstrGen | !LookAtPhysRegUses))304 return true;305 return false;306 }307 308 /// Mark physical register as being used in a register use operand.309 /// This is only used by the special livethrough handling code.310 void markPhysRegUsedInInstr(MCRegister PhysReg) {311 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {312 assert(UsedInInstr[static_cast<unsigned>(Unit)] <= InstrGen &&313 "non-phys use before phys use?");314 UsedInInstr[static_cast<unsigned>(Unit)] = InstrGen;315 }316 }317 318 /// Remove mark of physical register being used in the instruction.319 void unmarkRegUsedInInstr(MCRegister PhysReg) {320 for (MCRegUnit Unit : TRI->regunits(PhysReg))321 UsedInInstr[static_cast<unsigned>(Unit)] = 0;322 }323 324 enum : unsigned {325 spillClean = 50,326 spillDirty = 100,327 spillPrefBonus = 20,328 spillImpossible = ~0u329 };330 331public:332 bool ClearVirtRegs;333 334 bool runOnMachineFunction(MachineFunction &MF);335 336private:337 void allocateBasicBlock(MachineBasicBlock &MBB);338 339 void addRegClassDefCounts(MutableArrayRef<unsigned> RegClassDefCounts,340 Register Reg) const;341 342 void findAndSortDefOperandIndexes(const MachineInstr &MI);343 344 void allocateInstruction(MachineInstr &MI);345 void handleDebugValue(MachineInstr &MI);346 void handleBundle(MachineInstr &MI);347 348 bool usePhysReg(MachineInstr &MI, MCRegister PhysReg);349 bool definePhysReg(MachineInstr &MI, MCRegister PhysReg);350 bool displacePhysReg(MachineInstr &MI, MCRegister PhysReg);351 void freePhysReg(MCRegister PhysReg);352 353 unsigned calcSpillCost(MCPhysReg PhysReg) const;354 355 LiveRegMap::iterator findLiveVirtReg(Register VirtReg) {356 return LiveVirtRegs.find(VirtReg.virtRegIndex());357 }358 359 LiveRegMap::const_iterator findLiveVirtReg(Register VirtReg) const {360 return LiveVirtRegs.find(VirtReg.virtRegIndex());361 }362 363 void assignVirtToPhysReg(MachineInstr &MI, LiveReg &, MCRegister PhysReg);364 void allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint,365 bool LookAtPhysRegUses = false);366 void allocVirtRegUndef(MachineOperand &MO);367 void assignDanglingDebugValues(MachineInstr &Def, Register VirtReg,368 MCRegister Reg);369 bool defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,370 Register VirtReg);371 bool defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,372 bool LookAtPhysRegUses = false);373 bool useVirtReg(MachineInstr &MI, MachineOperand &MO, Register VirtReg);374 375 MCPhysReg getErrorAssignment(const LiveReg &LR, MachineInstr &MI,376 const TargetRegisterClass &RC);377 378 MachineBasicBlock::iterator379 getMBBBeginInsertionPoint(MachineBasicBlock &MBB,380 SmallSet<Register, 2> &PrologLiveIns) const;381 382 void reloadAtBegin(MachineBasicBlock &MBB);383 bool setPhysReg(MachineInstr &MI, MachineOperand &MO,384 const LiveReg &Assignment);385 386 Register traceCopies(Register VirtReg) const;387 Register traceCopyChain(Register Reg) const;388 389 bool shouldAllocateRegister(const Register Reg) const;390 int getStackSpaceFor(Register VirtReg);391 void spill(MachineBasicBlock::iterator Before, Register VirtReg,392 MCPhysReg AssignedReg, bool Kill, bool LiveOut);393 void reload(MachineBasicBlock::iterator Before, Register VirtReg,394 MCPhysReg PhysReg);395 396 bool mayLiveOut(Register VirtReg);397 bool mayLiveIn(Register VirtReg);398 399 bool mayBeSpillFromInlineAsmBr(const MachineInstr &MI) const;400 401 void dumpState() const;402};403 404class RegAllocFast : public MachineFunctionPass {405 RegAllocFastImpl Impl;406 407public:408 static char ID;409 410 RegAllocFast(const RegAllocFilterFunc F = nullptr, bool ClearVirtRegs_ = true)411 : MachineFunctionPass(ID), Impl(F, ClearVirtRegs_) {}412 413 bool runOnMachineFunction(MachineFunction &MF) override {414 return Impl.runOnMachineFunction(MF);415 }416 417 StringRef getPassName() const override { return "Fast Register Allocator"; }418 419 void getAnalysisUsage(AnalysisUsage &AU) const override {420 AU.setPreservesCFG();421 MachineFunctionPass::getAnalysisUsage(AU);422 }423 424 MachineFunctionProperties getRequiredProperties() const override {425 return MachineFunctionProperties().setNoPHIs();426 }427 428 MachineFunctionProperties getSetProperties() const override {429 if (Impl.ClearVirtRegs) {430 return MachineFunctionProperties().setNoVRegs();431 }432 433 return MachineFunctionProperties();434 }435 436 MachineFunctionProperties getClearedProperties() const override {437 return MachineFunctionProperties().setIsSSA();438 }439};440 441} // end anonymous namespace442 443char RegAllocFast::ID = 0;444 445INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false,446 false)447 448bool RegAllocFastImpl::shouldAllocateRegister(const Register Reg) const {449 assert(Reg.isVirtual());450 if (!ShouldAllocateRegisterImpl)451 return true;452 453 return ShouldAllocateRegisterImpl(*TRI, *MRI, Reg);454}455 456void RegAllocFastImpl::setRegUnitState(MCRegUnit Unit, unsigned NewState) {457 RegUnitStates[static_cast<unsigned>(Unit)] = NewState;458}459 460unsigned RegAllocFastImpl::getRegUnitState(MCRegUnit Unit) const {461 return RegUnitStates[static_cast<unsigned>(Unit)];462}463 464void RegAllocFastImpl::setPhysRegState(MCRegister PhysReg, unsigned NewState) {465 for (MCRegUnit Unit : TRI->regunits(PhysReg))466 setRegUnitState(Unit, NewState);467}468 469bool RegAllocFastImpl::isPhysRegFree(MCRegister PhysReg) const {470 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {471 if (getRegUnitState(Unit) != regFree)472 return false;473 }474 return true;475}476 477/// This allocates space for the specified virtual register to be held on the478/// stack.479int RegAllocFastImpl::getStackSpaceFor(Register VirtReg) {480 // Find the location Reg would belong...481 int SS = StackSlotForVirtReg[VirtReg];482 // Already has space allocated?483 if (SS != -1)484 return SS;485 486 // Allocate a new stack object for this spill location...487 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);488 unsigned Size = TRI->getSpillSize(RC);489 Align Alignment = TRI->getSpillAlign(RC);490 491 const MachineFunction &MF = MRI->getMF();492 auto &ST = MF.getSubtarget();493 Align CurrentAlign = ST.getFrameLowering()->getStackAlign();494 if (Alignment > CurrentAlign && !TRI->canRealignStack(MF))495 Alignment = CurrentAlign;496 497 int FrameIdx = MFI->CreateSpillStackObject(Size, Alignment);498 499 // Assign the slot.500 StackSlotForVirtReg[VirtReg] = FrameIdx;501 return FrameIdx;502}503 504static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A,505 const MachineInstr &B) {506 uint64_t IndexA, IndexB;507 PosIndexes.getIndex(A, IndexA);508 if (LLVM_UNLIKELY(PosIndexes.getIndex(B, IndexB)))509 PosIndexes.getIndex(A, IndexA);510 return IndexA < IndexB;511}512 513/// Returns true if \p MI is a spill of a live-in physical register in a block514/// targeted by an INLINEASM_BR. Such spills must precede reloads of live-in515/// virtual registers, so that we do not reload from an uninitialized stack516/// slot.517bool RegAllocFastImpl::mayBeSpillFromInlineAsmBr(const MachineInstr &MI) const {518 int FI;519 auto *MBB = MI.getParent();520 if (MBB->isInlineAsmBrIndirectTarget() && TII->isStoreToStackSlot(MI, FI) &&521 MFI->isSpillSlotObjectIndex(FI))522 for (const auto &Op : MI.operands())523 if (Op.isReg() && MBB->isLiveIn(Op.getReg()))524 return true;525 return false;526}527 528/// Returns false if \p VirtReg is known to not live out of the current block.529bool RegAllocFastImpl::mayLiveOut(Register VirtReg) {530 if (MayLiveAcrossBlocks.test(VirtReg.virtRegIndex())) {531 // Cannot be live-out if there are no successors.532 return !MBB->succ_empty();533 }534 535 const MachineInstr *SelfLoopDef = nullptr;536 537 // If this block loops back to itself, it is necessary to check whether the538 // use comes after the def.539 if (MBB->isSuccessor(MBB)) {540 // Find the first def in the self loop MBB.541 for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {542 if (DefInst.getParent() != MBB) {543 MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());544 return true;545 } else {546 if (!SelfLoopDef || dominates(PosIndexes, DefInst, *SelfLoopDef))547 SelfLoopDef = &DefInst;548 }549 }550 if (!SelfLoopDef) {551 MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());552 return true;553 }554 }555 556 // See if the first \p Limit uses of the register are all in the current557 // block.558 static const unsigned Limit = 8;559 unsigned C = 0;560 for (const MachineInstr &UseInst : MRI->use_nodbg_instructions(VirtReg)) {561 if (UseInst.getParent() != MBB || ++C >= Limit) {562 MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());563 // Cannot be live-out if there are no successors.564 return !MBB->succ_empty();565 }566 567 if (SelfLoopDef) {568 // Try to handle some simple cases to avoid spilling and reloading every569 // value inside a self looping block.570 if (SelfLoopDef == &UseInst ||571 !dominates(PosIndexes, *SelfLoopDef, UseInst)) {572 MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());573 return true;574 }575 }576 }577 578 return false;579}580 581/// Returns false if \p VirtReg is known to not be live into the current block.582bool RegAllocFastImpl::mayLiveIn(Register VirtReg) {583 if (MayLiveAcrossBlocks.test(VirtReg.virtRegIndex()))584 return !MBB->pred_empty();585 586 // See if the first \p Limit def of the register are all in the current block.587 static const unsigned Limit = 8;588 unsigned C = 0;589 for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {590 if (DefInst.getParent() != MBB || ++C >= Limit) {591 MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());592 return !MBB->pred_empty();593 }594 }595 596 return false;597}598 599/// Insert spill instruction for \p AssignedReg before \p Before. Update600/// DBG_VALUEs with \p VirtReg operands with the stack slot.601void RegAllocFastImpl::spill(MachineBasicBlock::iterator Before,602 Register VirtReg, MCPhysReg AssignedReg, bool Kill,603 bool LiveOut) {604 LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI) << " in "605 << printReg(AssignedReg, TRI));606 int FI = getStackSpaceFor(VirtReg);607 LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n');608 609 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);610 TII->storeRegToStackSlot(*MBB, Before, AssignedReg, Kill, FI, &RC, VirtReg);611 ++NumStores;612 613 MachineBasicBlock::iterator FirstTerm = MBB->getFirstTerminator();614 615 // When we spill a virtual register, we will have spill instructions behind616 // every definition of it, meaning we can switch all the DBG_VALUEs over617 // to just reference the stack slot.618 SmallVectorImpl<MachineOperand *> &LRIDbgOperands = LiveDbgValueMap[VirtReg];619 SmallMapVector<MachineInstr *, SmallVector<const MachineOperand *>, 2>620 SpilledOperandsMap;621 for (MachineOperand *MO : LRIDbgOperands)622 SpilledOperandsMap[MO->getParent()].push_back(MO);623 for (const auto &MISpilledOperands : SpilledOperandsMap) {624 MachineInstr &DBG = *MISpilledOperands.first;625 // We don't have enough support for tracking operands of DBG_VALUE_LISTs.626 if (DBG.isDebugValueList())627 continue;628 MachineInstr *NewDV = buildDbgValueForSpill(629 *MBB, Before, *MISpilledOperands.first, FI, MISpilledOperands.second);630 assert(NewDV->getParent() == MBB && "dangling parent pointer");631 (void)NewDV;632 LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);633 634 if (LiveOut) {635 // We need to insert a DBG_VALUE at the end of the block if the spill slot636 // is live out, but there is another use of the value after the637 // spill. This will allow LiveDebugValues to see the correct live out638 // value to propagate to the successors.639 MachineInstr *ClonedDV = MBB->getParent()->CloneMachineInstr(NewDV);640 MBB->insert(FirstTerm, ClonedDV);641 LLVM_DEBUG(dbgs() << "Cloning debug info due to live out spill\n");642 }643 644 // Rewrite unassigned dbg_values to use the stack slot.645 // TODO We can potentially do this for list debug values as well if we know646 // how the dbg_values are getting unassigned.647 if (DBG.isNonListDebugValue()) {648 MachineOperand &MO = DBG.getDebugOperand(0);649 if (MO.isReg() && MO.getReg() == 0) {650 updateDbgValueForSpill(DBG, FI, 0);651 }652 }653 }654 // Now this register is spilled there is should not be any DBG_VALUE655 // pointing to this register because they are all pointing to spilled value656 // now.657 LRIDbgOperands.clear();658}659 660/// Insert reload instruction for \p PhysReg before \p Before.661void RegAllocFastImpl::reload(MachineBasicBlock::iterator Before,662 Register VirtReg, MCPhysReg PhysReg) {663 LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "664 << printReg(PhysReg, TRI) << '\n');665 int FI = getStackSpaceFor(VirtReg);666 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);667 TII->loadRegFromStackSlot(*MBB, Before, PhysReg, FI, &RC, VirtReg);668 ++NumLoads;669}670 671/// Get basic block begin insertion point.672/// This is not just MBB.begin() because surprisingly we have EH_LABEL673/// instructions marking the begin of a basic block. This means we must insert674/// new instructions after such labels...675MachineBasicBlock::iterator RegAllocFastImpl::getMBBBeginInsertionPoint(676 MachineBasicBlock &MBB, SmallSet<Register, 2> &PrologLiveIns) const {677 MachineBasicBlock::iterator I = MBB.begin();678 while (I != MBB.end()) {679 if (I->isLabel()) {680 ++I;681 continue;682 }683 684 // Skip prologues and inlineasm_br spills to place reloads afterwards.685 if (!TII->isBasicBlockPrologue(*I) && !mayBeSpillFromInlineAsmBr(*I))686 break;687 688 // However if a prolog instruction reads a register that needs to be689 // reloaded, the reload should be inserted before the prolog.690 for (MachineOperand &MO : I->operands()) {691 if (MO.isReg())692 PrologLiveIns.insert(MO.getReg());693 }694 695 ++I;696 }697 698 return I;699}700 701/// Reload all currently assigned virtual registers.702void RegAllocFastImpl::reloadAtBegin(MachineBasicBlock &MBB) {703 if (LiveVirtRegs.empty())704 return;705 706 for (MachineBasicBlock::RegisterMaskPair P : MBB.liveins()) {707 MCRegister Reg = P.PhysReg;708 // Set state to live-in. This possibly overrides mappings to virtual709 // registers but we don't care anymore at this point.710 setPhysRegState(Reg, regLiveIn);711 }712 713 SmallSet<Register, 2> PrologLiveIns;714 715 // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order716 // of spilling here is deterministic, if arbitrary.717 MachineBasicBlock::iterator InsertBefore =718 getMBBBeginInsertionPoint(MBB, PrologLiveIns);719 for (const LiveReg &LR : LiveVirtRegs) {720 MCPhysReg PhysReg = LR.PhysReg;721 if (PhysReg == 0 || LR.Error)722 continue;723 724 MCRegUnit FirstUnit = *TRI->regunits(PhysReg).begin();725 if (getRegUnitState(FirstUnit) == regLiveIn)726 continue;727 728 assert((&MBB != &MBB.getParent()->front() || IgnoreMissingDefs) &&729 "no reload in start block. Missing vreg def?");730 731 if (PrologLiveIns.count(PhysReg)) {732 // FIXME: Theoretically this should use an insert point skipping labels733 // but I'm not sure how labels should interact with prolog instruction734 // that need reloads.735 reload(MBB.begin(), LR.VirtReg, PhysReg);736 } else737 reload(InsertBefore, LR.VirtReg, PhysReg);738 }739 LiveVirtRegs.clear();740}741 742/// Handle the direct use of a physical register. Check that the register is743/// not used by a virtreg. Kill the physreg, marking it free. This may add744/// implicit kills to MO->getParent() and invalidate MO.745bool RegAllocFastImpl::usePhysReg(MachineInstr &MI, MCRegister Reg) {746 assert(Register::isPhysicalRegister(Reg) && "expected physreg");747 bool displacedAny = displacePhysReg(MI, Reg);748 setPhysRegState(Reg, regPreAssigned);749 markRegUsedInInstr(Reg);750 return displacedAny;751}752 753bool RegAllocFastImpl::definePhysReg(MachineInstr &MI, MCRegister Reg) {754 bool displacedAny = displacePhysReg(MI, Reg);755 setPhysRegState(Reg, regPreAssigned);756 return displacedAny;757}758 759/// Mark PhysReg as reserved or free after spilling any virtregs. This is very760/// similar to defineVirtReg except the physreg is reserved instead of761/// allocated.762bool RegAllocFastImpl::displacePhysReg(MachineInstr &MI, MCRegister PhysReg) {763 bool displacedAny = false;764 765 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {766 switch (unsigned VirtReg = getRegUnitState(Unit)) {767 default: {768 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);769 assert(LRI != LiveVirtRegs.end() && "datastructures in sync");770 MachineBasicBlock::iterator ReloadBefore =771 std::next((MachineBasicBlock::iterator)MI.getIterator());772 while (mayBeSpillFromInlineAsmBr(*ReloadBefore))773 ++ReloadBefore;774 reload(ReloadBefore, VirtReg, LRI->PhysReg);775 776 setPhysRegState(LRI->PhysReg, regFree);777 LRI->PhysReg = 0;778 LRI->Reloaded = true;779 displacedAny = true;780 break;781 }782 case regPreAssigned:783 setRegUnitState(Unit, regFree);784 displacedAny = true;785 break;786 case regFree:787 break;788 }789 }790 return displacedAny;791}792 793void RegAllocFastImpl::freePhysReg(MCRegister PhysReg) {794 LLVM_DEBUG(dbgs() << "Freeing " << printReg(PhysReg, TRI) << ':');795 796 MCRegUnit FirstUnit = *TRI->regunits(PhysReg).begin();797 switch (unsigned VirtReg = getRegUnitState(FirstUnit)) {798 case regFree:799 LLVM_DEBUG(dbgs() << '\n');800 return;801 case regPreAssigned:802 LLVM_DEBUG(dbgs() << '\n');803 setPhysRegState(PhysReg, regFree);804 return;805 default: {806 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);807 assert(LRI != LiveVirtRegs.end());808 LLVM_DEBUG(dbgs() << ' ' << printReg(LRI->VirtReg, TRI) << '\n');809 setPhysRegState(LRI->PhysReg, regFree);810 LRI->PhysReg = 0;811 }812 return;813 }814}815 816/// Return the cost of spilling clearing out PhysReg and aliases so it is free817/// for allocation. Returns 0 when PhysReg is free or disabled with all aliases818/// disabled - it can be allocated directly.819/// \returns spillImpossible when PhysReg or an alias can't be spilled.820unsigned RegAllocFastImpl::calcSpillCost(MCPhysReg PhysReg) const {821 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {822 switch (unsigned VirtReg = getRegUnitState(Unit)) {823 case regFree:824 break;825 case regPreAssigned:826 LLVM_DEBUG(dbgs() << "Cannot spill pre-assigned "827 << printReg(PhysReg, TRI) << '\n');828 return spillImpossible;829 default: {830 bool SureSpill = StackSlotForVirtReg[VirtReg] != -1 ||831 findLiveVirtReg(VirtReg)->LiveOut;832 return SureSpill ? spillClean : spillDirty;833 }834 }835 }836 return 0;837}838 839void RegAllocFastImpl::assignDanglingDebugValues(MachineInstr &Definition,840 Register VirtReg,841 MCRegister Reg) {842 auto UDBGValIter = DanglingDbgValues.find(VirtReg);843 if (UDBGValIter == DanglingDbgValues.end())844 return;845 846 SmallVectorImpl<MachineInstr *> &Dangling = UDBGValIter->second;847 for (MachineInstr *DbgValue : Dangling) {848 assert(DbgValue->isDebugValue());849 if (!DbgValue->hasDebugOperandForReg(VirtReg))850 continue;851 852 // Test whether the physreg survives from the definition to the DBG_VALUE.853 MCPhysReg SetToReg = Reg;854 unsigned Limit = 20;855 for (MachineBasicBlock::iterator I = std::next(Definition.getIterator()),856 E = DbgValue->getIterator();857 I != E; ++I) {858 if (I->modifiesRegister(Reg, TRI) || --Limit == 0) {859 LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue860 << '\n');861 SetToReg = 0;862 break;863 }864 }865 for (MachineOperand &MO : DbgValue->getDebugOperandsForReg(VirtReg)) {866 MO.setReg(SetToReg);867 if (SetToReg != 0)868 MO.setIsRenamable();869 }870 }871 Dangling.clear();872}873 874/// This method updates local state so that we know that PhysReg is the875/// proper container for VirtReg now. The physical register must not be used876/// for anything else when this is called.877void RegAllocFastImpl::assignVirtToPhysReg(MachineInstr &AtMI, LiveReg &LR,878 MCRegister PhysReg) {879 Register VirtReg = LR.VirtReg;880 LLVM_DEBUG(dbgs() << "Assigning " << printReg(VirtReg, TRI) << " to "881 << printReg(PhysReg, TRI) << '\n');882 assert(LR.PhysReg == 0 && "Already assigned a physreg");883 assert(PhysReg != 0 && "Trying to assign no register");884 LR.PhysReg = PhysReg;885 setPhysRegState(PhysReg, VirtReg.id());886 887 assignDanglingDebugValues(AtMI, VirtReg, PhysReg);888}889 890static bool isCoalescable(const MachineInstr &MI) { return MI.isFullCopy(); }891 892Register RegAllocFastImpl::traceCopyChain(Register Reg) const {893 static const unsigned ChainLengthLimit = 3;894 unsigned C = 0;895 do {896 if (Reg.isPhysical())897 return Reg;898 assert(Reg.isVirtual());899 900 MachineInstr *VRegDef = MRI->getUniqueVRegDef(Reg);901 if (!VRegDef || !isCoalescable(*VRegDef))902 return 0;903 Reg = VRegDef->getOperand(1).getReg();904 } while (++C <= ChainLengthLimit);905 return 0;906}907 908/// Check if any of \p VirtReg's definitions is a copy. If it is follow the909/// chain of copies to check whether we reach a physical register we can910/// coalesce with.911Register RegAllocFastImpl::traceCopies(Register VirtReg) const {912 static const unsigned DefLimit = 3;913 unsigned C = 0;914 for (const MachineInstr &MI : MRI->def_instructions(VirtReg)) {915 if (isCoalescable(MI)) {916 Register Reg = MI.getOperand(1).getReg();917 Reg = traceCopyChain(Reg);918 if (Reg.isValid())919 return Reg;920 }921 922 if (++C >= DefLimit)923 break;924 }925 return Register();926}927 928/// Allocates a physical register for VirtReg.929void RegAllocFastImpl::allocVirtReg(MachineInstr &MI, LiveReg &LR,930 Register Hint0, bool LookAtPhysRegUses) {931 const Register VirtReg = LR.VirtReg;932 assert(LR.PhysReg == 0);933 934 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);935 LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg)936 << " in class " << TRI->getRegClassName(&RC)937 << " with hint " << printReg(Hint0, TRI) << '\n');938 939 // Take hint when possible.940 if (Hint0.isPhysical() && MRI->isAllocatable(Hint0) && RC.contains(Hint0) &&941 !isRegUsedInInstr(Hint0, LookAtPhysRegUses)) {942 // Take hint if the register is currently free.943 if (isPhysRegFree(Hint0)) {944 LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)945 << '\n');946 assignVirtToPhysReg(MI, LR, Hint0);947 return;948 } else {949 LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint0, TRI)950 << " occupied\n");951 }952 } else {953 Hint0 = Register();954 }955 956 // Try other hint.957 Register Hint1 = traceCopies(VirtReg);958 if (Hint1.isPhysical() && MRI->isAllocatable(Hint1) && RC.contains(Hint1) &&959 !isRegUsedInInstr(Hint1, LookAtPhysRegUses)) {960 // Take hint if the register is currently free.961 if (isPhysRegFree(Hint1)) {962 LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)963 << '\n');964 assignVirtToPhysReg(MI, LR, Hint1);965 return;966 } else {967 LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint1, TRI)968 << " occupied\n");969 }970 } else {971 Hint1 = Register();972 }973 974 MCPhysReg BestReg = 0;975 unsigned BestCost = spillImpossible;976 ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);977 for (MCPhysReg PhysReg : AllocationOrder) {978 LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << ' ');979 if (isRegUsedInInstr(PhysReg, LookAtPhysRegUses)) {980 LLVM_DEBUG(dbgs() << "already used in instr.\n");981 continue;982 }983 984 unsigned Cost = calcSpillCost(PhysReg);985 LLVM_DEBUG(dbgs() << "Cost: " << Cost << " BestCost: " << BestCost << '\n');986 // Immediate take a register with cost 0.987 if (Cost == 0) {988 assignVirtToPhysReg(MI, LR, PhysReg);989 return;990 }991 992 if (PhysReg == Hint0 || PhysReg == Hint1)993 Cost -= spillPrefBonus;994 995 if (Cost < BestCost) {996 BestReg = PhysReg;997 BestCost = Cost;998 }999 }1000 1001 if (!BestReg) {1002 // Nothing we can do: Report an error and keep going with an invalid1003 // allocation.1004 LR.PhysReg = getErrorAssignment(LR, MI, RC);1005 LR.Error = true;1006 return;1007 }1008 1009 displacePhysReg(MI, BestReg);1010 assignVirtToPhysReg(MI, LR, BestReg);1011}1012 1013void RegAllocFastImpl::allocVirtRegUndef(MachineOperand &MO) {1014 assert(MO.isUndef() && "expected undef use");1015 Register VirtReg = MO.getReg();1016 assert(VirtReg.isVirtual() && "Expected virtreg");1017 if (!shouldAllocateRegister(VirtReg))1018 return;1019 1020 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);1021 MCPhysReg PhysReg;1022 bool IsRenamable = true;1023 if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {1024 PhysReg = LRI->PhysReg;1025 } else {1026 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);1027 ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);1028 if (AllocationOrder.empty()) {1029 // All registers in the class were reserved.1030 //1031 // It might be OK to take any entry from the class as this is an undef1032 // use, but accepting this would give different behavior than greedy and1033 // basic.1034 PhysReg = getErrorAssignment(*LRI, *MO.getParent(), RC);1035 LRI->Error = true;1036 IsRenamable = false;1037 } else1038 PhysReg = AllocationOrder.front();1039 }1040 1041 unsigned SubRegIdx = MO.getSubReg();1042 if (SubRegIdx != 0) {1043 PhysReg = TRI->getSubReg(PhysReg, SubRegIdx);1044 MO.setSubReg(0);1045 }1046 MO.setReg(PhysReg);1047 MO.setIsRenamable(IsRenamable);1048}1049 1050/// Variation of defineVirtReg() with special handling for livethrough regs1051/// (tied or earlyclobber) that may interfere with preassigned uses.1052/// \return true if MI's MachineOperands were re-arranged/invalidated.1053bool RegAllocFastImpl::defineLiveThroughVirtReg(MachineInstr &MI,1054 unsigned OpNum,1055 Register VirtReg) {1056 if (!shouldAllocateRegister(VirtReg))1057 return false;1058 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);1059 if (LRI != LiveVirtRegs.end()) {1060 MCPhysReg PrevReg = LRI->PhysReg;1061 if (PrevReg != 0 && isRegUsedInInstr(PrevReg, true)) {1062 LLVM_DEBUG(dbgs() << "Need new assignment for " << printReg(PrevReg, TRI)1063 << " (tied/earlyclobber resolution)\n");1064 freePhysReg(PrevReg);1065 LRI->PhysReg = 0;1066 allocVirtReg(MI, *LRI, 0, true);1067 MachineBasicBlock::iterator InsertBefore =1068 std::next((MachineBasicBlock::iterator)MI.getIterator());1069 LLVM_DEBUG(dbgs() << "Copy " << printReg(LRI->PhysReg, TRI) << " to "1070 << printReg(PrevReg, TRI) << '\n');1071 BuildMI(*MBB, InsertBefore, MI.getDebugLoc(),1072 TII->get(TargetOpcode::COPY), PrevReg)1073 .addReg(LRI->PhysReg, llvm::RegState::Kill);1074 }1075 MachineOperand &MO = MI.getOperand(OpNum);1076 if (MO.getSubReg() && !MO.isUndef()) {1077 LRI->LastUse = &MI;1078 }1079 }1080 return defineVirtReg(MI, OpNum, VirtReg, true);1081}1082 1083/// Allocates a register for VirtReg definition. Typically the register is1084/// already assigned from a use of the virtreg, however we still need to1085/// perform an allocation if:1086/// - It is a dead definition without any uses.1087/// - The value is live out and all uses are in different basic blocks.1088///1089/// \return true if MI's MachineOperands were re-arranged/invalidated.1090bool RegAllocFastImpl::defineVirtReg(MachineInstr &MI, unsigned OpNum,1091 Register VirtReg, bool LookAtPhysRegUses) {1092 assert(VirtReg.isVirtual() && "Not a virtual register");1093 if (!shouldAllocateRegister(VirtReg))1094 return false;1095 MachineOperand &MO = MI.getOperand(OpNum);1096 LiveRegMap::iterator LRI;1097 bool New;1098 std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));1099 if (New) {1100 if (!MO.isDead()) {1101 if (mayLiveOut(VirtReg)) {1102 LRI->LiveOut = true;1103 } else {1104 // It is a dead def without the dead flag; add the flag now.1105 MO.setIsDead(true);1106 }1107 }1108 }1109 if (LRI->PhysReg == 0) {1110 allocVirtReg(MI, *LRI, 0, LookAtPhysRegUses);1111 } else {1112 assert((!isRegUsedInInstr(LRI->PhysReg, LookAtPhysRegUses) || LRI->Error) &&1113 "TODO: preassign mismatch");1114 LLVM_DEBUG(dbgs() << "In def of " << printReg(VirtReg, TRI)1115 << " use existing assignment to "1116 << printReg(LRI->PhysReg, TRI) << '\n');1117 }1118 1119 MCPhysReg PhysReg = LRI->PhysReg;1120 if (LRI->Reloaded || LRI->LiveOut) {1121 if (!MI.isImplicitDef()) {1122 MachineBasicBlock::iterator SpillBefore =1123 std::next((MachineBasicBlock::iterator)MI.getIterator());1124 LLVM_DEBUG(dbgs() << "Spill Reason: LO: " << LRI->LiveOut1125 << " RL: " << LRI->Reloaded << '\n');1126 bool Kill = LRI->LastUse == nullptr;1127 spill(SpillBefore, VirtReg, PhysReg, Kill, LRI->LiveOut);1128 1129 // We need to place additional spills for each indirect destination of an1130 // INLINEASM_BR.1131 if (MI.getOpcode() == TargetOpcode::INLINEASM_BR) {1132 int FI = StackSlotForVirtReg[VirtReg];1133 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);1134 for (MachineOperand &MO : MI.operands()) {1135 if (MO.isMBB()) {1136 MachineBasicBlock *Succ = MO.getMBB();1137 TII->storeRegToStackSlot(*Succ, Succ->begin(), PhysReg, Kill, FI,1138 &RC, VirtReg);1139 ++NumStores;1140 Succ->addLiveIn(PhysReg);1141 }1142 }1143 }1144 1145 LRI->LastUse = nullptr;1146 }1147 LRI->LiveOut = false;1148 LRI->Reloaded = false;1149 }1150 if (MI.getOpcode() == TargetOpcode::BUNDLE) {1151 BundleVirtRegsMap[VirtReg] = *LRI;1152 }1153 markRegUsedInInstr(PhysReg);1154 return setPhysReg(MI, MO, *LRI);1155}1156 1157/// Allocates a register for a VirtReg use.1158/// \return true if MI's MachineOperands were re-arranged/invalidated.1159bool RegAllocFastImpl::useVirtReg(MachineInstr &MI, MachineOperand &MO,1160 Register VirtReg) {1161 assert(VirtReg.isVirtual() && "Not a virtual register");1162 if (!shouldAllocateRegister(VirtReg))1163 return false;1164 LiveRegMap::iterator LRI;1165 bool New;1166 std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));1167 if (New) {1168 if (!MO.isKill()) {1169 if (mayLiveOut(VirtReg)) {1170 LRI->LiveOut = true;1171 } else {1172 // It is a last (killing) use without the kill flag; add the flag now.1173 MO.setIsKill(true);1174 }1175 }1176 } else {1177 assert((!MO.isKill() || LRI->LastUse == &MI) && "Invalid kill flag");1178 }1179 1180 // If necessary allocate a register.1181 if (LRI->PhysReg == 0) {1182 assert(!MO.isTied() && "tied op should be allocated");1183 Register Hint;1184 if (MI.isCopy() && MI.getOperand(1).getSubReg() == 0) {1185 Hint = MI.getOperand(0).getReg();1186 if (Hint.isVirtual()) {1187 assert(!shouldAllocateRegister(Hint));1188 Hint = Register();1189 } else {1190 assert(Hint.isPhysical() &&1191 "Copy destination should already be assigned");1192 }1193 }1194 allocVirtReg(MI, *LRI, Hint, false);1195 }1196 1197 LRI->LastUse = &MI;1198 1199 if (MI.getOpcode() == TargetOpcode::BUNDLE) {1200 BundleVirtRegsMap[VirtReg] = *LRI;1201 }1202 markRegUsedInInstr(LRI->PhysReg);1203 return setPhysReg(MI, MO, *LRI);1204}1205 1206/// Query a physical register to use as a filler in contexts where the1207/// allocation has failed. This will raise an error, but not abort the1208/// compilation.1209MCPhysReg RegAllocFastImpl::getErrorAssignment(const LiveReg &LR,1210 MachineInstr &MI,1211 const TargetRegisterClass &RC) {1212 MachineFunction &MF = *MI.getMF();1213 1214 // Avoid repeating the error every time a register is used.1215 bool EmitError = !MF.getProperties().hasFailedRegAlloc();1216 if (EmitError)1217 MF.getProperties().setFailedRegAlloc();1218 1219 // If the allocation order was empty, all registers in the class were1220 // probably reserved. Fall back to taking the first register in the class,1221 // even if it's reserved.1222 ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);1223 if (AllocationOrder.empty()) {1224 const Function &Fn = MF.getFunction();1225 if (EmitError) {1226 Fn.getContext().diagnose(DiagnosticInfoRegAllocFailure(1227 "no registers from class available to allocate", Fn,1228 MI.getDebugLoc()));1229 }1230 1231 ArrayRef<MCPhysReg> RawRegs = RC.getRegisters();1232 assert(!RawRegs.empty() && "register classes cannot have no registers");1233 return RawRegs.front();1234 }1235 1236 if (!LR.Error && EmitError) {1237 // Nothing we can do: Report an error and keep going with an invalid1238 // allocation.1239 if (MI.isInlineAsm()) {1240 MI.emitInlineAsmError(1241 "inline assembly requires more registers than available");1242 } else {1243 const Function &Fn = MBB->getParent()->getFunction();1244 Fn.getContext().diagnose(DiagnosticInfoRegAllocFailure(1245 "ran out of registers during register allocation", Fn,1246 MI.getDebugLoc()));1247 }1248 }1249 1250 return AllocationOrder.front();1251}1252 1253/// Changes operand OpNum in MI the refer the PhysReg, considering subregs.1254/// \return true if MI's MachineOperands were re-arranged/invalidated.1255bool RegAllocFastImpl::setPhysReg(MachineInstr &MI, MachineOperand &MO,1256 const LiveReg &Assignment) {1257 MCPhysReg PhysReg = Assignment.PhysReg;1258 assert(PhysReg && "assignments should always be to a valid physreg");1259 1260 if (LLVM_UNLIKELY(Assignment.Error)) {1261 // Make sure we don't set renamable in error scenarios, as we may have1262 // assigned to a reserved register.1263 if (MO.isUse())1264 MO.setIsUndef(true);1265 }1266 1267 if (!MO.getSubReg()) {1268 MO.setReg(PhysReg);1269 MO.setIsRenamable(!Assignment.Error);1270 return false;1271 }1272 1273 // Handle subregister index.1274 MO.setReg(TRI->getSubReg(PhysReg, MO.getSubReg()));1275 MO.setIsRenamable(!Assignment.Error);1276 1277 // Note: We leave the subreg number around a little longer in case of defs.1278 // This is so that the register freeing logic in allocateInstruction can still1279 // recognize this as subregister defs. The code there will clear the number.1280 if (!MO.isDef())1281 MO.setSubReg(0);1282 1283 // A kill flag implies killing the full register. Add corresponding super1284 // register kill.1285 if (MO.isKill()) {1286 MI.addRegisterKilled(PhysReg, TRI, true);1287 // Conservatively assume implicit MOs were re-arranged1288 return true;1289 }1290 1291 // A <def,read-undef> of a sub-register requires an implicit def of the full1292 // register.1293 if (MO.isDef() && MO.isUndef()) {1294 if (MO.isDead())1295 MI.addRegisterDead(PhysReg, TRI, true);1296 else1297 MI.addRegisterDefined(PhysReg, TRI);1298 // Conservatively assume implicit MOs were re-arranged1299 return true;1300 }1301 return false;1302}1303 1304#ifndef NDEBUG1305 1306void RegAllocFastImpl::dumpState() const {1307 for (MCRegUnit Unit : TRI->regunits()) {1308 switch (unsigned VirtReg = getRegUnitState(Unit)) {1309 case regFree:1310 break;1311 case regPreAssigned:1312 dbgs() << " " << printRegUnit(Unit, TRI) << "[P]";1313 break;1314 case regLiveIn:1315 llvm_unreachable("Should not have regLiveIn in map");1316 default: {1317 dbgs() << ' ' << printRegUnit(Unit, TRI) << '=' << printReg(VirtReg);1318 LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);1319 assert(I != LiveVirtRegs.end() && "have LiveVirtRegs entry");1320 if (I->LiveOut || I->Reloaded) {1321 dbgs() << '[';1322 if (I->LiveOut)1323 dbgs() << 'O';1324 if (I->Reloaded)1325 dbgs() << 'R';1326 dbgs() << ']';1327 }1328 assert(TRI->hasRegUnit(I->PhysReg, Unit) && "inverse mapping present");1329 break;1330 }1331 }1332 }1333 dbgs() << '\n';1334 // Check that LiveVirtRegs is the inverse.1335 for (const LiveReg &LR : LiveVirtRegs) {1336 Register VirtReg = LR.VirtReg;1337 assert(VirtReg.isVirtual() && "Bad map key");1338 MCPhysReg PhysReg = LR.PhysReg;1339 if (PhysReg != 0) {1340 assert(Register::isPhysicalRegister(PhysReg) && "mapped to physreg");1341 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {1342 assert(getRegUnitState(Unit) == VirtReg && "inverse map valid");1343 }1344 }1345 }1346}1347#endif1348 1349/// Count number of defs consumed from each register class by \p Reg1350void RegAllocFastImpl::addRegClassDefCounts(1351 MutableArrayRef<unsigned> RegClassDefCounts, Register Reg) const {1352 assert(RegClassDefCounts.size() == TRI->getNumRegClasses());1353 1354 if (Reg.isVirtual()) {1355 if (!shouldAllocateRegister(Reg))1356 return;1357 const TargetRegisterClass *OpRC = MRI->getRegClass(Reg);1358 for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();1359 RCIdx != RCIdxEnd; ++RCIdx) {1360 const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx);1361 // FIXME: Consider aliasing sub/super registers.1362 if (OpRC->hasSubClassEq(IdxRC))1363 ++RegClassDefCounts[RCIdx];1364 }1365 1366 return;1367 }1368 1369 for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();1370 RCIdx != RCIdxEnd; ++RCIdx) {1371 const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx);1372 for (MCRegAliasIterator Alias(Reg, TRI, true); Alias.isValid(); ++Alias) {1373 if (IdxRC->contains(*Alias)) {1374 ++RegClassDefCounts[RCIdx];1375 break;1376 }1377 }1378 }1379}1380 1381/// Compute \ref DefOperandIndexes so it contains the indices of "def" operands1382/// that are to be allocated. Those are ordered in a way that small classes,1383/// early clobbers and livethroughs are allocated first.1384void RegAllocFastImpl::findAndSortDefOperandIndexes(const MachineInstr &MI) {1385 DefOperandIndexes.clear();1386 1387 LLVM_DEBUG(dbgs() << "Need to assign livethroughs\n");1388 for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {1389 const MachineOperand &MO = MI.getOperand(I);1390 if (!MO.isReg())1391 continue;1392 Register Reg = MO.getReg();1393 if (MO.readsReg()) {1394 if (Reg.isPhysical()) {1395 LLVM_DEBUG(dbgs() << "mark extra used: " << printReg(Reg, TRI) << '\n');1396 markPhysRegUsedInInstr(Reg);1397 }1398 }1399 1400 if (MO.isDef() && Reg.isVirtual() && shouldAllocateRegister(Reg))1401 DefOperandIndexes.push_back(I);1402 }1403 1404 // Most instructions only have one virtual def, so there's no point in1405 // computing the possible number of defs for every register class.1406 if (DefOperandIndexes.size() <= 1)1407 return;1408 1409 // Track number of defs which may consume a register from the class. This is1410 // used to assign registers for possibly-too-small classes first. Example:1411 // defs are eax, 3 * gr32_abcd, 2 * gr32 => we want to assign the gr32_abcd1412 // registers first so that the gr32 don't use the gr32_abcd registers before1413 // we assign these.1414 SmallVector<unsigned> RegClassDefCounts(TRI->getNumRegClasses(), 0);1415 1416 for (const MachineOperand &MO : MI.all_defs())1417 addRegClassDefCounts(RegClassDefCounts, MO.getReg());1418 1419 llvm::sort(DefOperandIndexes, [&](unsigned I0, unsigned I1) {1420 const MachineOperand &MO0 = MI.getOperand(I0);1421 const MachineOperand &MO1 = MI.getOperand(I1);1422 Register Reg0 = MO0.getReg();1423 Register Reg1 = MO1.getReg();1424 const TargetRegisterClass &RC0 = *MRI->getRegClass(Reg0);1425 const TargetRegisterClass &RC1 = *MRI->getRegClass(Reg1);1426 1427 // Identify regclass that are easy to use up completely just in this1428 // instruction.1429 unsigned ClassSize0 = RegClassInfo.getOrder(&RC0).size();1430 unsigned ClassSize1 = RegClassInfo.getOrder(&RC1).size();1431 1432 bool SmallClass0 = ClassSize0 < RegClassDefCounts[RC0.getID()];1433 bool SmallClass1 = ClassSize1 < RegClassDefCounts[RC1.getID()];1434 if (SmallClass0 > SmallClass1)1435 return true;1436 if (SmallClass0 < SmallClass1)1437 return false;1438 1439 // Allocate early clobbers and livethrough operands first.1440 bool Livethrough0 = MO0.isEarlyClobber() || MO0.isTied() ||1441 (MO0.getSubReg() == 0 && !MO0.isUndef());1442 bool Livethrough1 = MO1.isEarlyClobber() || MO1.isTied() ||1443 (MO1.getSubReg() == 0 && !MO1.isUndef());1444 if (Livethrough0 > Livethrough1)1445 return true;1446 if (Livethrough0 < Livethrough1)1447 return false;1448 1449 // Tie-break rule: operand index.1450 return I0 < I1;1451 });1452}1453 1454// Returns true if MO is tied and the operand it's tied to is not Undef (not1455// Undef is not the same thing as Def).1456static bool isTiedToNotUndef(const MachineOperand &MO) {1457 if (!MO.isTied())1458 return false;1459 const MachineInstr &MI = *MO.getParent();1460 unsigned TiedIdx = MI.findTiedOperandIdx(MI.getOperandNo(&MO));1461 const MachineOperand &TiedMO = MI.getOperand(TiedIdx);1462 return !TiedMO.isUndef();1463}1464 1465void RegAllocFastImpl::allocateInstruction(MachineInstr &MI) {1466 // The basic algorithm here is:1467 // 1. Mark registers of def operands as free1468 // 2. Allocate registers to use operands and place reload instructions for1469 // registers displaced by the allocation.1470 //1471 // However we need to handle some corner cases:1472 // - pre-assigned defs and uses need to be handled before the other def/use1473 // operands are processed to avoid the allocation heuristics clashing with1474 // the pre-assignment.1475 // - The "free def operands" step has to come last instead of first for tied1476 // operands and early-clobbers.1477 1478 InstrGen += 2;1479 // In the event we ever get more than 2**31 instructions...1480 if (LLVM_UNLIKELY(InstrGen == 0)) {1481 UsedInInstr.assign(UsedInInstr.size(), 0);1482 InstrGen = 2;1483 }1484 RegMasks.clear();1485 BundleVirtRegsMap.clear();1486 1487 // Scan for special cases; Apply pre-assigned register defs to state.1488 bool HasPhysRegUse = false;1489 bool HasRegMask = false;1490 bool HasVRegDef = false;1491 bool HasDef = false;1492 bool HasEarlyClobber = false;1493 bool NeedToAssignLiveThroughs = false;1494 for (MachineOperand &MO : MI.operands()) {1495 if (MO.isReg()) {1496 Register Reg = MO.getReg();1497 if (Reg.isVirtual()) {1498 if (!shouldAllocateRegister(Reg))1499 continue;1500 if (MO.isDef()) {1501 HasDef = true;1502 HasVRegDef = true;1503 if (MO.isEarlyClobber()) {1504 HasEarlyClobber = true;1505 NeedToAssignLiveThroughs = true;1506 }1507 if (isTiedToNotUndef(MO) || (MO.getSubReg() != 0 && !MO.isUndef()))1508 NeedToAssignLiveThroughs = true;1509 }1510 } else if (Reg.isPhysical()) {1511 if (!MRI->isReserved(Reg)) {1512 if (MO.isDef()) {1513 HasDef = true;1514 bool displacedAny = definePhysReg(MI, Reg);1515 if (MO.isEarlyClobber())1516 HasEarlyClobber = true;1517 if (!displacedAny)1518 MO.setIsDead(true);1519 }1520 if (MO.readsReg())1521 HasPhysRegUse = true;1522 }1523 }1524 } else if (MO.isRegMask()) {1525 HasRegMask = true;1526 RegMasks.push_back(MO.getRegMask());1527 }1528 }1529 1530 // Allocate virtreg defs.1531 if (HasDef) {1532 if (HasVRegDef) {1533 // Note that Implicit MOs can get re-arranged by defineVirtReg(), so loop1534 // multiple times to ensure no operand is missed.1535 bool ReArrangedImplicitOps = true;1536 1537 // Special handling for early clobbers, tied operands or subregister defs:1538 // Compared to "normal" defs these:1539 // - Must not use a register that is pre-assigned for a use operand.1540 // - In order to solve tricky inline assembly constraints we change the1541 // heuristic to figure out a good operand order before doing1542 // assignments.1543 if (NeedToAssignLiveThroughs) {1544 while (ReArrangedImplicitOps) {1545 ReArrangedImplicitOps = false;1546 findAndSortDefOperandIndexes(MI);1547 for (unsigned OpIdx : DefOperandIndexes) {1548 MachineOperand &MO = MI.getOperand(OpIdx);1549 LLVM_DEBUG(dbgs() << "Allocating " << MO << '\n');1550 Register Reg = MO.getReg();1551 if (MO.isEarlyClobber() || isTiedToNotUndef(MO) ||1552 (MO.getSubReg() && !MO.isUndef())) {1553 ReArrangedImplicitOps = defineLiveThroughVirtReg(MI, OpIdx, Reg);1554 } else {1555 ReArrangedImplicitOps = defineVirtReg(MI, OpIdx, Reg);1556 }1557 // Implicit operands of MI were re-arranged,1558 // re-compute DefOperandIndexes.1559 if (ReArrangedImplicitOps)1560 break;1561 }1562 }1563 } else {1564 // Assign virtual register defs.1565 while (ReArrangedImplicitOps) {1566 ReArrangedImplicitOps = false;1567 for (MachineOperand &MO : MI.all_defs()) {1568 Register Reg = MO.getReg();1569 if (Reg.isVirtual()) {1570 ReArrangedImplicitOps =1571 defineVirtReg(MI, MI.getOperandNo(&MO), Reg);1572 if (ReArrangedImplicitOps)1573 break;1574 }1575 }1576 }1577 }1578 }1579 1580 // Free registers occupied by defs.1581 // Iterate operands in reverse order, so we see the implicit super register1582 // defs first (we added them earlier in case of <def,read-undef>).1583 for (MachineOperand &MO : reverse(MI.all_defs())) {1584 Register Reg = MO.getReg();1585 1586 // subreg defs don't free the full register. We left the subreg number1587 // around as a marker in setPhysReg() to recognize this case here.1588 if (Reg.isPhysical() && MO.getSubReg() != 0) {1589 MO.setSubReg(0);1590 continue;1591 }1592 1593 assert((!MO.isTied() || !isClobberedByRegMasks(MO.getReg())) &&1594 "tied def assigned to clobbered register");1595 1596 // Do not free tied operands and early clobbers.1597 if (isTiedToNotUndef(MO) || MO.isEarlyClobber())1598 continue;1599 if (!Reg)1600 continue;1601 if (Reg.isVirtual()) {1602 assert(!shouldAllocateRegister(Reg));1603 continue;1604 }1605 assert(Reg.isPhysical());1606 if (MRI->isReserved(Reg))1607 continue;1608 freePhysReg(Reg);1609 unmarkRegUsedInInstr(Reg);1610 }1611 }1612 1613 // Displace clobbered registers.1614 if (HasRegMask) {1615 assert(!RegMasks.empty() && "expected RegMask");1616 // MRI bookkeeping.1617 for (const auto *RM : RegMasks)1618 MRI->addPhysRegsUsedFromRegMask(RM);1619 1620 // Displace clobbered registers.1621 for (const LiveReg &LR : LiveVirtRegs) {1622 MCPhysReg PhysReg = LR.PhysReg;1623 if (PhysReg != 0 && isClobberedByRegMasks(PhysReg))1624 displacePhysReg(MI, PhysReg);1625 }1626 }1627 1628 // Apply pre-assigned register uses to state.1629 if (HasPhysRegUse) {1630 for (MachineOperand &MO : MI.operands()) {1631 if (!MO.isReg() || !MO.readsReg())1632 continue;1633 Register Reg = MO.getReg();1634 if (!Reg.isPhysical())1635 continue;1636 if (MRI->isReserved(Reg))1637 continue;1638 if (!usePhysReg(MI, Reg))1639 MO.setIsKill(true);1640 }1641 }1642 1643 // Allocate virtreg uses and insert reloads as necessary.1644 // Implicit MOs can get moved/removed by useVirtReg(), so loop multiple1645 // times to ensure no operand is missed.1646 bool HasUndefUse = false;1647 bool ReArrangedImplicitMOs = true;1648 while (ReArrangedImplicitMOs) {1649 ReArrangedImplicitMOs = false;1650 for (MachineOperand &MO : MI.operands()) {1651 if (!MO.isReg() || !MO.isUse())1652 continue;1653 Register Reg = MO.getReg();1654 if (!Reg.isVirtual() || !shouldAllocateRegister(Reg))1655 continue;1656 1657 if (MO.isUndef()) {1658 HasUndefUse = true;1659 continue;1660 }1661 1662 // Populate MayLiveAcrossBlocks in case the use block is allocated before1663 // the def block (removing the vreg uses).1664 mayLiveIn(Reg);1665 1666 assert(!MO.isInternalRead() && "Bundles not supported");1667 assert(MO.readsReg() && "reading use");1668 ReArrangedImplicitMOs = useVirtReg(MI, MO, Reg);1669 if (ReArrangedImplicitMOs)1670 break;1671 }1672 }1673 1674 // Allocate undef operands. This is a separate step because in a situation1675 // like ` = OP undef %X, %X` both operands need the same register assign1676 // so we should perform the normal assignment first.1677 if (HasUndefUse) {1678 for (MachineOperand &MO : MI.all_uses()) {1679 Register Reg = MO.getReg();1680 if (!Reg.isVirtual() || !shouldAllocateRegister(Reg))1681 continue;1682 1683 assert(MO.isUndef() && "Should only have undef virtreg uses left");1684 allocVirtRegUndef(MO);1685 }1686 }1687 1688 // Free early clobbers.1689 if (HasEarlyClobber) {1690 for (MachineOperand &MO : reverse(MI.all_defs())) {1691 if (!MO.isEarlyClobber())1692 continue;1693 assert(!MO.getSubReg() && "should be already handled in def processing");1694 1695 Register Reg = MO.getReg();1696 if (!Reg)1697 continue;1698 if (Reg.isVirtual()) {1699 assert(!shouldAllocateRegister(Reg));1700 continue;1701 }1702 assert(Reg.isPhysical() && "should have register assigned");1703 1704 // We sometimes get odd situations like:1705 // early-clobber %x0 = INSTRUCTION %x01706 // which is semantically questionable as the early-clobber should1707 // apply before the use. But in practice we consider the use to1708 // happen before the early clobber now. Don't free the early clobber1709 // register in this case.1710 if (MI.readsRegister(Reg, TRI))1711 continue;1712 1713 freePhysReg(Reg);1714 }1715 }1716 1717 LLVM_DEBUG(dbgs() << "<< " << MI);1718 if (MI.isCopy() && MI.getOperand(0).getReg() == MI.getOperand(1).getReg() &&1719 MI.getNumOperands() == 2) {1720 LLVM_DEBUG(dbgs() << "Mark identity copy for removal\n");1721 Coalesced.push_back(&MI);1722 }1723}1724 1725void RegAllocFastImpl::handleDebugValue(MachineInstr &MI) {1726 // Ignore DBG_VALUEs that aren't based on virtual registers. These are1727 // mostly constants and frame indices.1728 assert(MI.isDebugValue() && "not a DBG_VALUE*");1729 for (const auto &MO : MI.debug_operands()) {1730 if (!MO.isReg())1731 continue;1732 Register Reg = MO.getReg();1733 if (!Reg.isVirtual())1734 continue;1735 if (!shouldAllocateRegister(Reg))1736 continue;1737 1738 // Already spilled to a stackslot?1739 int SS = StackSlotForVirtReg[Reg];1740 if (SS != -1) {1741 // Modify DBG_VALUE now that the value is in a spill slot.1742 updateDbgValueForSpill(MI, SS, Reg);1743 LLVM_DEBUG(dbgs() << "Rewrite DBG_VALUE for spilled memory: " << MI);1744 continue;1745 }1746 1747 // See if this virtual register has already been allocated to a physical1748 // register or spilled to a stack slot.1749 LiveRegMap::iterator LRI = findLiveVirtReg(Reg);1750 SmallVector<MachineOperand *> DbgOps(1751 llvm::make_pointer_range(MI.getDebugOperandsForReg(Reg)));1752 1753 if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {1754 // Update every use of Reg within MI.1755 for (auto &RegMO : DbgOps)1756 setPhysReg(MI, *RegMO, *LRI);1757 } else {1758 DanglingDbgValues[Reg].push_back(&MI);1759 }1760 1761 // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so1762 // that future spills of Reg will have DBG_VALUEs.1763 LiveDbgValueMap[Reg].append(DbgOps.begin(), DbgOps.end());1764 }1765}1766 1767void RegAllocFastImpl::handleBundle(MachineInstr &MI) {1768 MachineBasicBlock::instr_iterator BundledMI = MI.getIterator();1769 ++BundledMI;1770 while (BundledMI->isBundledWithPred()) {1771 for (MachineOperand &MO : BundledMI->operands()) {1772 if (!MO.isReg())1773 continue;1774 1775 Register Reg = MO.getReg();1776 if (!Reg.isVirtual() || !shouldAllocateRegister(Reg))1777 continue;1778 1779 DenseMap<Register, LiveReg>::iterator DI = BundleVirtRegsMap.find(Reg);1780 assert(DI != BundleVirtRegsMap.end() && "Unassigned virtual register");1781 1782 setPhysReg(MI, MO, DI->second);1783 }1784 1785 ++BundledMI;1786 }1787}1788 1789void RegAllocFastImpl::allocateBasicBlock(MachineBasicBlock &MBB) {1790 this->MBB = &MBB;1791 LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);1792 1793 PosIndexes.unsetInitialized();1794 RegUnitStates.assign(TRI->getNumRegUnits(), regFree);1795 assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");1796 1797 for (const auto &LiveReg : MBB.liveouts())1798 setPhysRegState(LiveReg.PhysReg, regPreAssigned);1799 1800 Coalesced.clear();1801 1802 // Traverse block in reverse order allocating instructions one by one.1803 for (MachineInstr &MI : reverse(MBB)) {1804 LLVM_DEBUG(dbgs() << "\n>> " << MI << "Regs:"; dumpState());1805 1806 // Special handling for debug values. Note that they are not allowed to1807 // affect codegen of the other instructions in any way.1808 if (MI.isDebugValue()) {1809 handleDebugValue(MI);1810 continue;1811 }1812 1813 allocateInstruction(MI);1814 1815 // Once BUNDLE header is assigned registers, same assignments need to be1816 // done for bundled MIs.1817 if (MI.getOpcode() == TargetOpcode::BUNDLE) {1818 handleBundle(MI);1819 }1820 }1821 1822 LLVM_DEBUG(dbgs() << "Begin Regs:"; dumpState());1823 1824 // Spill all physical registers holding virtual registers now.1825 LLVM_DEBUG(dbgs() << "Loading live registers at begin of block.\n");1826 reloadAtBegin(MBB);1827 1828 // Erase all the coalesced copies. We are delaying it until now because1829 // LiveVirtRegs might refer to the instrs.1830 for (MachineInstr *MI : Coalesced)1831 MBB.erase(MI);1832 NumCoalesced += Coalesced.size();1833 1834 for (auto &UDBGPair : DanglingDbgValues) {1835 for (MachineInstr *DbgValue : UDBGPair.second) {1836 assert(DbgValue->isDebugValue() && "expected DBG_VALUE");1837 // Nothing to do if the vreg was spilled in the meantime.1838 if (!DbgValue->hasDebugOperandForReg(UDBGPair.first))1839 continue;1840 LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue1841 << '\n');1842 DbgValue->setDebugValueUndef();1843 }1844 }1845 DanglingDbgValues.clear();1846 1847 LLVM_DEBUG(MBB.dump());1848}1849 1850bool RegAllocFastImpl::runOnMachineFunction(MachineFunction &MF) {1851 LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"1852 << "********** Function: " << MF.getName() << '\n');1853 MRI = &MF.getRegInfo();1854 const TargetSubtargetInfo &STI = MF.getSubtarget();1855 TRI = STI.getRegisterInfo();1856 TII = STI.getInstrInfo();1857 MFI = &MF.getFrameInfo();1858 MRI->freezeReservedRegs();1859 RegClassInfo.runOnMachineFunction(MF);1860 unsigned NumRegUnits = TRI->getNumRegUnits();1861 InstrGen = 0;1862 UsedInInstr.assign(NumRegUnits, 0);1863 1864 // initialize the virtual->physical register map to have a 'null'1865 // mapping for all virtual registers1866 unsigned NumVirtRegs = MRI->getNumVirtRegs();1867 StackSlotForVirtReg.resize(NumVirtRegs);1868 LiveVirtRegs.setUniverse(NumVirtRegs);1869 MayLiveAcrossBlocks.clear();1870 MayLiveAcrossBlocks.resize(NumVirtRegs);1871 1872 // Loop over all of the basic blocks, eliminating virtual register references1873 for (MachineBasicBlock &MBB : MF)1874 allocateBasicBlock(MBB);1875 1876 if (ClearVirtRegs) {1877 // All machine operands and other references to virtual registers have been1878 // replaced. Remove the virtual registers.1879 MRI->clearVirtRegs();1880 }1881 1882 StackSlotForVirtReg.clear();1883 LiveDbgValueMap.clear();1884 return true;1885}1886 1887PreservedAnalyses RegAllocFastPass::run(MachineFunction &MF,1888 MachineFunctionAnalysisManager &) {1889 MFPropsModifier _(*this, MF);1890 RegAllocFastImpl Impl(Opts.Filter, Opts.ClearVRegs);1891 bool Changed = Impl.runOnMachineFunction(MF);1892 if (!Changed)1893 return PreservedAnalyses::all();1894 auto PA = getMachineFunctionPassPreservedAnalyses();1895 PA.preserveSet<CFGAnalyses>();1896 return PA;1897}1898 1899void RegAllocFastPass::printPipeline(1900 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {1901 bool PrintFilterName = Opts.FilterName != "all";1902 bool PrintNoClearVRegs = !Opts.ClearVRegs;1903 bool PrintSemicolon = PrintFilterName && PrintNoClearVRegs;1904 1905 OS << "regallocfast";1906 if (PrintFilterName || PrintNoClearVRegs) {1907 OS << '<';1908 if (PrintFilterName)1909 OS << "filter=" << Opts.FilterName;1910 if (PrintSemicolon)1911 OS << ';';1912 if (PrintNoClearVRegs)1913 OS << "no-clear-vregs";1914 OS << '>';1915 }1916}1917 1918FunctionPass *llvm::createFastRegisterAllocator() { return new RegAllocFast(); }1919 1920FunctionPass *llvm::createFastRegisterAllocator(RegAllocFilterFunc Ftor,1921 bool ClearVirtRegs) {1922 return new RegAllocFast(Ftor, ClearVirtRegs);1923}1924