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