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