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