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