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