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