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;
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 /// Register units defined by a non-dead physreg def of the current
283 /// instruction, indexed by MCRegUnit. Stamped with InstrGen like
284 /// UsedInInstr, so a unit is set if LiveDefUnits[Unit] == InstrGen.
285 SmallVector<uint32_t, 0> LiveDefUnits;
286
287 SmallVector<unsigned, 8> DefOperandIndexes;
288 // Register masks attached to the current instruction.
289 SmallVector<const uint32_t *> RegMasks;
290
291 // Assign index for each instruction to quickly determine dominance.
292 InstrPosIndexes PosIndexes;
293
294 void setRegUnitState(MCRegUnit Unit, unsigned NewState);
295 unsigned getRegUnitState(MCRegUnit Unit) const;
296
297 void setPhysRegState(MCRegister PhysReg, unsigned NewState);
298 bool isPhysRegFree(MCRegister PhysReg) const;
299
300 /// Mark a physreg as used in this instruction.
301 void markRegUsedInInstr(MCRegister PhysReg) {
302 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg))
303 UsedInInstr[static_cast<unsigned>(Unit)] = InstrGen | 1;
304 }
305
306 // Check if physreg is clobbered by instruction's regmask(s).
307 bool isClobberedByRegMasks(MCRegister PhysReg) const {
308 return llvm::any_of(Range: RegMasks, P: [PhysReg](const uint32_t *Mask) {
309 return MachineOperand::clobbersPhysReg(RegMask: Mask, PhysReg);
310 });
311 }
312
313 /// Check if a physreg or any of its aliases are used in this instruction.
314 bool isRegUsedInInstr(MCRegister PhysReg, bool LookAtPhysRegUses) const {
315 if (LookAtPhysRegUses && isClobberedByRegMasks(PhysReg))
316 return true;
317 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg))
318 if (UsedInInstr[static_cast<unsigned>(Unit)] >=
319 (InstrGen | !LookAtPhysRegUses))
320 return true;
321 return false;
322 }
323
324 /// Mark physical register as being used in a register use operand.
325 /// This is only used by the special livethrough handling code.
326 void markPhysRegUsedInInstr(MCRegister PhysReg) {
327 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
328 assert(UsedInInstr[static_cast<unsigned>(Unit)] <= InstrGen &&
329 "non-phys use before phys use?");
330 UsedInInstr[static_cast<unsigned>(Unit)] = InstrGen;
331 }
332 }
333
334 /// Remove mark of physical register being used in the instruction.
335 void unmarkRegUsedInInstr(MCRegister PhysReg) {
336 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg))
337 UsedInInstr[static_cast<unsigned>(Unit)] = 0;
338 }
339
340 /// Record that a non-dead def of the current instruction keeps every register
341 /// unit of \p PhysReg live.
342 void markLiveDefUnits(MCRegister PhysReg) {
343 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg))
344 LiveDefUnits[static_cast<unsigned>(Unit)] = InstrGen;
345 }
346
347 /// Check if every register unit of \p PhysReg is defined by a non-dead def of
348 /// the current instruction.
349 bool hasLiveDefUnits(MCRegister PhysReg) const {
350 return all_of(Range: TRI->regunits(Reg: PhysReg), P: [this](MCRegUnit Unit) {
351 return LiveDefUnits[static_cast<unsigned>(Unit)] == InstrGen;
352 });
353 }
354
355 enum : unsigned {
356 spillClean = 50,
357 spillDirty = 100,
358 spillPrefBonus = 20,
359 spillImpossible = ~0u
360 };
361
362public:
363 bool ClearVirtRegs;
364
365 bool runOnMachineFunction(MachineFunction &MF);
366
367private:
368 void allocateBasicBlock(MachineBasicBlock &MBB);
369 void expandSubregPseudo(MachineInstr &MI);
370
371 void addRegClassDefCounts(MutableArrayRef<unsigned> RegClassDefCounts,
372 Register Reg) const;
373
374 void findAndSortDefOperandIndexes(const MachineInstr &MI);
375
376 void allocateInstruction(MachineInstr &MI);
377 void handleDebugValue(MachineInstr &MI);
378 void handleBundle(MachineInstr &MI);
379
380 bool usePhysReg(MachineInstr &MI, MCRegister PhysReg);
381 bool definePhysReg(MachineInstr &MI, MCRegister PhysReg);
382 bool displacePhysReg(MachineInstr &MI, MCRegister PhysReg);
383 void freePhysReg(MCRegister PhysReg);
384
385 unsigned calcSpillCost(MCPhysReg PhysReg) const;
386
387 LiveRegMap::iterator findLiveVirtReg(Register VirtReg) {
388 return LiveVirtRegs.find(Key: VirtReg.virtRegIndex());
389 }
390
391 LiveRegMap::const_iterator findLiveVirtReg(Register VirtReg) const {
392 return LiveVirtRegs.find(Key: VirtReg.virtRegIndex());
393 }
394
395 void assignVirtToPhysReg(MachineInstr &MI, LiveReg &, MCRegister PhysReg);
396 void allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint,
397 bool LookAtPhysRegUses = false);
398 void allocVirtRegUndef(MachineOperand &MO);
399 void assignDanglingDebugValues(MachineInstr &Def, Register VirtReg,
400 MCRegister Reg);
401 bool defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
402 Register VirtReg);
403 bool defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,
404 bool LookAtPhysRegUses = false);
405 bool useVirtReg(MachineInstr &MI, MachineOperand &MO, Register VirtReg);
406 bool lowerTiedUse(MachineInstr &MI, MachineOperand &MO, LiveReg &LR);
407
408 MCPhysReg getErrorAssignment(const LiveReg &LR, MachineInstr &MI,
409 const TargetRegisterClass &RC);
410
411 MachineBasicBlock::iterator
412 getMBBBeginInsertionPoint(MachineBasicBlock &MBB,
413 SmallSet<Register, 2> &PrologLiveIns) const;
414
415 void reloadAtBegin(MachineBasicBlock &MBB);
416 bool setPhysReg(MachineInstr &MI, MachineOperand &MO,
417 const LiveReg &Assignment);
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(MF);
448 }
449
450 StringRef getPassName() const override { return "Fast Register Allocator"; }
451
452 void getAnalysisUsage(AnalysisUsage &AU) const override {
453 AU.setPreservesCFG();
454 MachineFunctionPass::getAnalysisUsage(AU);
455 }
456
457 MachineFunctionProperties getRequiredProperties() const override {
458 return MachineFunctionProperties().setNoPHIs();
459 }
460
461 MachineFunctionProperties getSetProperties() const override {
462 MachineFunctionProperties P;
463 if (Impl.ClearVirtRegs)
464 P.setNoVRegs().setTiedOpsRewritten();
465 return P;
466 }
467
468 MachineFunctionProperties getClearedProperties() const override {
469 return MachineFunctionProperties().setIsSSA();
470 }
471};
472
473} // end anonymous namespace
474
475char RegAllocFast::ID = 0;
476
477INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false,
478 false)
479
480bool RegAllocFastImpl::shouldAllocateRegister(const Register Reg) const {
481 assert(Reg.isVirtual());
482 if (!ShouldAllocateRegisterImpl)
483 return true;
484
485 return ShouldAllocateRegisterImpl(*TRI, *MRI, Reg);
486}
487
488void RegAllocFastImpl::setRegUnitState(MCRegUnit Unit, unsigned NewState) {
489 RegUnitStates[static_cast<unsigned>(Unit)] = NewState;
490}
491
492unsigned RegAllocFastImpl::getRegUnitState(MCRegUnit Unit) const {
493 return RegUnitStates[static_cast<unsigned>(Unit)];
494}
495
496void RegAllocFastImpl::setPhysRegState(MCRegister PhysReg, unsigned NewState) {
497 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg))
498 setRegUnitState(Unit, NewState);
499}
500
501bool RegAllocFastImpl::isPhysRegFree(MCRegister PhysReg) const {
502 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
503 if (getRegUnitState(Unit) != regFree)
504 return false;
505 }
506 return true;
507}
508
509/// This allocates space for the specified virtual register to be held on the
510/// stack.
511int RegAllocFastImpl::getStackSpaceFor(Register VirtReg) {
512 // Find the location Reg would belong...
513 int SS = StackSlotForVirtReg[VirtReg];
514 // Already has space allocated?
515 if (SS != -1)
516 return SS;
517
518 // Allocate a new stack object for this spill location...
519 const TargetRegisterClass &RC = *MRI->getRegClass(Reg: VirtReg);
520 unsigned Size = TRI->getSpillSize(RC);
521 Align Alignment = TRI->getSpillAlign(RC);
522
523 const MachineFunction &MF = MRI->getMF();
524 auto &ST = MF.getSubtarget();
525 Align CurrentAlign = ST.getFrameLowering()->getStackAlign();
526 if (Alignment > CurrentAlign && !TRI->canRealignStack(MF))
527 Alignment = CurrentAlign;
528
529 int FrameIdx =
530 MFI->CreateSpillStackObject(Size, Alignment, StackID: TRI->getSpillStackID(RC));
531
532 // Assign the slot.
533 StackSlotForVirtReg[VirtReg] = FrameIdx;
534 return FrameIdx;
535}
536
537static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A,
538 const MachineInstr &B) {
539 uint64_t IndexA, IndexB;
540 PosIndexes.getIndex(MI: A, Index&: IndexA);
541 // getIndex() returns true when it renumbered the block, invalidating IndexA.
542 if (LLVM_UNLIKELY(PosIndexes.getIndex(B, IndexB)))
543 PosIndexes.getIndex(MI: A, Index&: IndexA);
544 return IndexA < IndexB;
545}
546
547/// Returns true if \p MI is a spill of a live-in physical register in a block
548/// targeted by an INLINEASM_BR. Such spills must precede reloads of live-in
549/// virtual registers, so that we do not reload from an uninitialized stack
550/// slot.
551bool RegAllocFastImpl::mayBeSpillFromInlineAsmBr(const MachineInstr &MI) const {
552 int FI;
553 auto *MBB = MI.getParent();
554 if (MBB->isInlineAsmBrIndirectTarget() && TII->isStoreToStackSlot(MI, FrameIndex&: FI) &&
555 MFI->isSpillSlotObjectIndex(ObjectIdx: FI))
556 for (const auto &Op : MI.operands())
557 if (Op.isReg() && Op.getReg().isValid() && MBB->isLiveIn(Reg: Op.getReg()))
558 return true;
559 return false;
560}
561
562/// Returns false if \p VirtReg is known to not live out of the current block.
563bool RegAllocFastImpl::mayLiveOut(Register VirtReg) {
564 if (MayLiveAcrossBlocks.test(Idx: VirtReg.virtRegIndex())) {
565 // Cannot be live-out if there are no successors.
566 return !MBB->succ_empty();
567 }
568
569 const MachineInstr *SelfLoopDef = nullptr;
570
571 // If this block loops back to itself, it is necessary to check whether the
572 // use comes after the def.
573 if (MBB->isSuccessor(MBB)) {
574 // Find the first def in the self loop MBB.
575 for (const MachineInstr &DefInst : MRI->def_instructions(Reg: VirtReg)) {
576 if (DefInst.getParent() != MBB) {
577 MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());
578 return true;
579 } else {
580 if (!SelfLoopDef || dominates(PosIndexes, A: DefInst, B: *SelfLoopDef))
581 SelfLoopDef = &DefInst;
582 }
583 }
584 if (!SelfLoopDef) {
585 MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());
586 return true;
587 }
588 }
589
590 // See if the first \p Limit uses of the register are all in the current
591 // block.
592 static const unsigned Limit = 8;
593 unsigned C = 0;
594 for (const MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg: VirtReg)) {
595 if (UseInst.getParent() != MBB || ++C >= Limit) {
596 MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());
597 // Cannot be live-out if there are no successors.
598 return !MBB->succ_empty();
599 }
600
601 if (SelfLoopDef) {
602 // Try to handle some simple cases to avoid spilling and reloading every
603 // value inside a self looping block.
604 if (SelfLoopDef == &UseInst ||
605 !dominates(PosIndexes, A: *SelfLoopDef, B: UseInst)) {
606 MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());
607 return true;
608 }
609 }
610 }
611
612 return false;
613}
614
615/// Returns false if \p VirtReg is known to not be live into the current block.
616bool RegAllocFastImpl::mayLiveIn(Register VirtReg) {
617 if (MayLiveAcrossBlocks.test(Idx: VirtReg.virtRegIndex()))
618 return !MBB->pred_empty();
619
620 // See if the first \p Limit def of the register are all in the current block.
621 static const unsigned Limit = 8;
622 unsigned C = 0;
623 for (const MachineInstr &DefInst : MRI->def_instructions(Reg: VirtReg)) {
624 if (DefInst.getParent() != MBB || ++C >= Limit) {
625 MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());
626 return !MBB->pred_empty();
627 }
628 }
629
630 return false;
631}
632
633/// Insert spill instruction for \p AssignedReg before \p Before. Update
634/// DBG_VALUEs with \p VirtReg operands with the stack slot.
635void RegAllocFastImpl::spill(MachineBasicBlock::iterator Before,
636 Register VirtReg, MCRegister AssignedReg,
637 bool Kill, bool LiveOut) {
638 LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI) << " in "
639 << printReg(AssignedReg, TRI));
640 int FI = getStackSpaceFor(VirtReg);
641 LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n');
642
643 const TargetRegisterClass &RC = *MRI->getRegClass(Reg: VirtReg);
644 TII->storeRegToStackSlot(MBB&: *MBB, MI: Before, SrcReg: AssignedReg, isKill: Kill, FrameIndex: FI, RC: &RC, VReg: VirtReg);
645 ++NumStores;
646
647 MachineBasicBlock::iterator FirstTerm = MBB->getFirstTerminator();
648
649 // When we spill a virtual register, we will have spill instructions behind
650 // every definition of it, meaning we can switch all the DBG_VALUEs over
651 // to just reference the stack slot.
652 SmallVectorImpl<MachineOperand *> &LRIDbgOperands = LiveDbgValueMap[VirtReg];
653 SmallMapVector<MachineInstr *, SmallVector<const MachineOperand *>, 2>
654 SpilledOperandsMap;
655 for (MachineOperand *MO : LRIDbgOperands)
656 SpilledOperandsMap[MO->getParent()].push_back(Elt: MO);
657 for (const auto &MISpilledOperands : SpilledOperandsMap) {
658 MachineInstr &DBG = *MISpilledOperands.first;
659 // We don't have enough support for tracking operands of DBG_VALUE_LISTs.
660 if (DBG.isDebugValueList())
661 continue;
662 MachineInstr *NewDV = buildDbgValueForSpill(
663 BB&: *MBB, I: Before, Orig: *MISpilledOperands.first, FrameIndex: FI, SpilledOperands: MISpilledOperands.second);
664 assert(NewDV->getParent() == MBB && "dangling parent pointer");
665 (void)NewDV;
666 LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);
667
668 if (LiveOut) {
669 // We need to insert a DBG_VALUE at the end of the block if the spill slot
670 // is live out, but there is another use of the value after the
671 // spill. This will allow LiveDebugValues to see the correct live out
672 // value to propagate to the successors.
673 MachineInstr *ClonedDV = MBB->getParent()->CloneMachineInstr(Orig: NewDV);
674 MBB->insert(I: FirstTerm, MI: ClonedDV);
675 LLVM_DEBUG(dbgs() << "Cloning debug info due to live out spill\n");
676 }
677
678 // Rewrite unassigned dbg_values to use the stack slot.
679 // TODO We can potentially do this for list debug values as well if we know
680 // how the dbg_values are getting unassigned.
681 if (DBG.isNonListDebugValue()) {
682 MachineOperand &MO = DBG.getDebugOperand(Index: 0);
683 if (MO.isReg() && !MO.getReg()) {
684 updateDbgValueForSpill(Orig&: DBG, FrameIndex: FI, Reg: Register());
685 }
686 }
687 }
688 // Now this register is spilled there is should not be any DBG_VALUE
689 // pointing to this register because they are all pointing to spilled value
690 // now.
691 LRIDbgOperands.clear();
692}
693
694/// Insert reload instruction for \p PhysReg before \p Before.
695void RegAllocFastImpl::reload(MachineBasicBlock::iterator Before,
696 Register VirtReg, MCRegister PhysReg) {
697 LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
698 << printReg(PhysReg, TRI) << '\n');
699 int FI = getStackSpaceFor(VirtReg);
700 const TargetRegisterClass &RC = *MRI->getRegClass(Reg: VirtReg);
701 TII->loadRegFromStackSlot(MBB&: *MBB, MI: Before, DestReg: PhysReg, FrameIndex: FI, RC: &RC, VReg: VirtReg);
702 ++NumLoads;
703}
704
705/// Get basic block begin insertion point.
706/// This is not just MBB.begin() because surprisingly we have EH_LABEL
707/// instructions marking the begin of a basic block. This means we must insert
708/// new instructions after such labels...
709MachineBasicBlock::iterator RegAllocFastImpl::getMBBBeginInsertionPoint(
710 MachineBasicBlock &MBB, SmallSet<Register, 2> &PrologLiveIns) const {
711 MachineBasicBlock::iterator I = MBB.begin();
712 while (I != MBB.end()) {
713 if (I->isLabel()) {
714 ++I;
715 continue;
716 }
717
718 // Skip prologues and inlineasm_br spills to place reloads afterwards.
719 if (!TII->isBasicBlockPrologue(MI: *I) && !mayBeSpillFromInlineAsmBr(MI: *I))
720 break;
721
722 // However if a prolog instruction reads a register that needs to be
723 // reloaded, the reload should be inserted before the prolog.
724 for (MachineOperand &MO : I->operands()) {
725 if (MO.isReg())
726 PrologLiveIns.insert(V: MO.getReg());
727 }
728
729 ++I;
730 }
731
732 return I;
733}
734
735/// Reload all currently assigned virtual registers.
736void RegAllocFastImpl::reloadAtBegin(MachineBasicBlock &MBB) {
737 if (LiveVirtRegs.empty())
738 return;
739
740 // Mark live-in registers so the loop below skips reloads into them. The
741 // virtual register mappings this overwrites are not needed anymore.
742 for (MachineBasicBlock::RegisterMaskPair P : MBB.liveins())
743 setPhysRegState(PhysReg: P.PhysReg, NewState: regLiveIn);
744
745 SmallSet<Register, 2> PrologLiveIns;
746
747 // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
748 // of spilling here is deterministic, if arbitrary.
749 MachineBasicBlock::iterator InsertBefore =
750 getMBBBeginInsertionPoint(MBB, PrologLiveIns);
751 for (const LiveReg &LR : LiveVirtRegs) {
752 MCRegister PhysReg = LR.PhysReg;
753 if (!PhysReg || LR.Error)
754 continue;
755
756 MCRegUnit FirstUnit = *TRI->regunits(Reg: PhysReg).begin();
757 if (getRegUnitState(Unit: FirstUnit) == regLiveIn)
758 continue;
759
760 assert(&MBB != &MBB.getParent()->front() &&
761 "no reload in start block. Missing vreg def?");
762
763 if (PrologLiveIns.count(V: PhysReg)) {
764 // FIXME: Theoretically this should use an insert point skipping labels
765 // but I'm not sure how labels should interact with prolog instruction
766 // that need reloads.
767 reload(Before: MBB.begin(), VirtReg: LR.VirtReg, PhysReg);
768 } else
769 reload(Before: InsertBefore, VirtReg: LR.VirtReg, PhysReg);
770 }
771 LiveVirtRegs.clear();
772}
773
774/// Handle the direct use of a physical register. Displace whatever occupies it
775/// and mark it pre-assigned: backwards, a use means live from here upward.
776/// Returns false if nothing was displaced, so the use is a kill. This may add
777/// implicit kills to MO->getParent() and invalidate MO.
778bool RegAllocFastImpl::usePhysReg(MachineInstr &MI, MCRegister Reg) {
779 assert(Reg.isPhysical() && "expected physreg");
780 bool displacedAny = displacePhysReg(MI, PhysReg: Reg);
781 setPhysRegState(PhysReg: Reg, NewState: regPreAssigned);
782 markRegUsedInInstr(PhysReg: Reg);
783 return displacedAny;
784}
785
786/// Displace whatever holds \p Reg and reserve it, so a virtual register def
787/// cannot land on a register this instruction already writes. Released in the
788/// free-def-operands step, after the uses for an early clobber, or by
789/// lowerTiedUse(); if the instruction also reads \p Reg it ends up reserved
790/// for the code above.
791bool RegAllocFastImpl::definePhysReg(MachineInstr &MI, MCRegister Reg) {
792 bool displacedAny = displacePhysReg(MI, PhysReg: Reg);
793 setPhysRegState(PhysReg: Reg, NewState: regPreAssigned);
794 return displacedAny;
795}
796
797/// Mark PhysReg as reserved or free after spilling any virtregs. This is very
798/// similar to defineVirtReg except the physreg is reserved instead of
799/// allocated.
800bool RegAllocFastImpl::displacePhysReg(MachineInstr &MI, MCRegister PhysReg) {
801 bool displacedAny = false;
802
803 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
804 switch (unsigned VirtReg = getRegUnitState(Unit)) {
805 default: {
806 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
807 assert(LRI != LiveVirtRegs.end() && "datastructures in sync");
808 MachineBasicBlock::iterator ReloadBefore =
809 std::next(x: (MachineBasicBlock::iterator)MI.getIterator());
810 while (mayBeSpillFromInlineAsmBr(MI: *ReloadBefore))
811 ++ReloadBefore;
812 reload(Before: ReloadBefore, VirtReg, PhysReg: LRI->PhysReg);
813
814 setPhysRegState(PhysReg: LRI->PhysReg, NewState: regFree);
815 LRI->PhysReg = MCRegister();
816 LRI->Reloaded = true;
817 displacedAny = true;
818 break;
819 }
820 case regPreAssigned:
821 setRegUnitState(Unit, NewState: regFree);
822 displacedAny = true;
823 break;
824 case regFree:
825 break;
826 }
827 }
828 return displacedAny;
829}
830
831void RegAllocFastImpl::freePhysReg(MCRegister PhysReg) {
832 LLVM_DEBUG(dbgs() << "Freeing " << printReg(PhysReg, TRI) << ':');
833
834 MCRegUnit FirstUnit = *TRI->regunits(Reg: PhysReg).begin();
835 switch (unsigned VirtReg = getRegUnitState(Unit: FirstUnit)) {
836 case regFree:
837 LLVM_DEBUG(dbgs() << '\n');
838 return;
839 case regPreAssigned:
840 LLVM_DEBUG(dbgs() << '\n');
841 setPhysRegState(PhysReg, NewState: regFree);
842 return;
843 default: {
844 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
845 assert(LRI != LiveVirtRegs.end());
846 LLVM_DEBUG(dbgs() << ' ' << printReg(LRI->VirtReg, TRI) << '\n');
847 setPhysRegState(PhysReg: LRI->PhysReg, NewState: regFree);
848 LRI->PhysReg = MCRegister();
849 }
850 return;
851 }
852}
853
854/// Return the cost of spilling clearing out PhysReg and aliases so it is free
855/// for allocation. Returns 0 when PhysReg is free or disabled with all aliases
856/// disabled - it can be allocated directly.
857/// \returns spillImpossible when PhysReg or an alias can't be spilled.
858unsigned RegAllocFastImpl::calcSpillCost(MCPhysReg PhysReg) const {
859 for (MCRegUnit Unit : TRI->regunits(Reg: PhysReg)) {
860 switch (unsigned VirtReg = getRegUnitState(Unit)) {
861 case regFree:
862 break;
863 case regPreAssigned:
864 LLVM_DEBUG(dbgs() << "Cannot spill pre-assigned "
865 << printReg(PhysReg, TRI) << '\n');
866 return spillImpossible;
867 default: {
868 bool SureSpill = StackSlotForVirtReg[VirtReg] != -1 ||
869 findLiveVirtReg(VirtReg)->LiveOut;
870 return SureSpill ? spillClean : spillDirty;
871 }
872 }
873 }
874 return 0;
875}
876
877void RegAllocFastImpl::assignDanglingDebugValues(MachineInstr &Definition,
878 Register VirtReg,
879 MCRegister Reg) {
880 auto UDBGValIter = DanglingDbgValues.find(Val: VirtReg);
881 if (UDBGValIter == DanglingDbgValues.end())
882 return;
883
884 SmallVectorImpl<MachineInstr *> &Dangling = UDBGValIter->second;
885 for (MachineInstr *DbgValue : Dangling) {
886 assert(DbgValue->isDebugValue());
887 if (!DbgValue->hasDebugOperandForReg(Reg: VirtReg))
888 continue;
889
890 // Test whether the physreg survives from the definition to the DBG_VALUE.
891 // A tied use that took over its def's register is assigned at an
892 // instruction that overwrites it, so start the scan there.
893 MCRegister SetToReg = Reg;
894 unsigned Limit = 20;
895 MachineBasicBlock::iterator I = Definition.getIterator();
896 if (!Definition.definesRegister(Reg, TRI))
897 ++I;
898 for (MachineBasicBlock::iterator E = DbgValue->getIterator(); I != E; ++I) {
899 if (I->modifiesRegister(Reg, TRI) || --Limit == 0) {
900 LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue
901 << '\n');
902 SetToReg = MCRegister();
903 break;
904 }
905 }
906 for (MachineOperand &MO : DbgValue->getDebugOperandsForReg(Reg: VirtReg)) {
907 MO.setReg(SetToReg);
908 if (SetToReg)
909 MO.setIsRenamable();
910 }
911 }
912 Dangling.clear();
913}
914
915/// This method updates local state so that we know that PhysReg is the
916/// proper container for VirtReg now. The physical register must not be used
917/// for anything else when this is called.
918void RegAllocFastImpl::assignVirtToPhysReg(MachineInstr &AtMI, LiveReg &LR,
919 MCRegister PhysReg) {
920 Register VirtReg = LR.VirtReg;
921 LLVM_DEBUG(dbgs() << "Assigning " << printReg(VirtReg, TRI) << " to "
922 << printReg(PhysReg, TRI) << '\n');
923 assert(!LR.PhysReg && "Already assigned a physreg");
924 assert(PhysReg && "Trying to assign no register");
925 LR.PhysReg = PhysReg;
926 setPhysRegState(PhysReg, NewState: VirtReg.id());
927
928 assignDanglingDebugValues(Definition&: AtMI, VirtReg, Reg: PhysReg);
929}
930
931static bool isCoalescable(const MachineInstr &MI) { return MI.isFullCopy(); }
932
933/// The operand \p MO is tied to.
934static const MachineOperand &getTiedOperand(const MachineInstr &MI,
935 const MachineOperand &MO) {
936 return MI.getOperand(i: MI.findTiedOperandIdx(OpIdx: MI.getOperandNo(I: &MO)));
937}
938
939/// The register \p DefMO's tied use reads, when the two end up in the same
940/// register: a subregister index on either side makes them differ.
941static Register getTiedUseReg(const MachineInstr &MI,
942 const MachineOperand &DefMO) {
943 if (!DefMO.isTied() || DefMO.getSubReg())
944 return Register();
945 const MachineOperand &UseMO = getTiedOperand(MI, MO: DefMO);
946 return UseMO.getSubReg() ? Register() : UseMO.getReg();
947}
948
949Register RegAllocFastImpl::traceCopyChain(Register Reg) const {
950 static const unsigned ChainLengthLimit = 3;
951 for (unsigned C = 0; C <= ChainLengthLimit; ++C) {
952 if (Reg.isPhysical())
953 return Reg;
954 assert(Reg.isVirtual());
955
956 const MachineOperand *DefMO = MRI->getOneDef(Reg);
957 if (!DefMO)
958 return Register();
959 const MachineInstr *Def = DefMO->getParent();
960 if (isCoalescable(MI: *Def)) {
961 Reg = Def->getOperand(i: 1).getReg();
962 continue;
963 }
964 // A two-address instruction's def and tied use end up in the same
965 // register, so the tie continues the chain.
966 Reg = LowerTiedOps ? getTiedUseReg(MI: *Def, DefMO: *DefMO) : Register();
967 if (!Reg)
968 return Register();
969 }
970 return Register();
971}
972
973/// Check if any of \p VirtReg's definitions is a copy or a tied def. If it is
974/// follow the chain of copies to check whether we reach a physical register we
975/// can coalesce with.
976Register RegAllocFastImpl::traceCopies(Register VirtReg) const {
977 static const unsigned DefLimit = 3;
978 unsigned C = 0;
979 for (const MachineOperand &DefMO : MRI->def_operands(Reg: VirtReg)) {
980 const MachineInstr &MI = *DefMO.getParent();
981 Register Reg;
982 if (isCoalescable(MI))
983 Reg = MI.getOperand(i: 1).getReg();
984 else if (LowerTiedOps)
985 Reg = getTiedUseReg(MI, DefMO);
986 if (Reg) {
987 Reg = traceCopyChain(Reg);
988 if (Reg.isValid())
989 return Reg;
990 }
991
992 if (++C >= DefLimit)
993 break;
994 }
995 return Register();
996}
997
998/// Allocates a physical register for VirtReg.
999void RegAllocFastImpl::allocVirtReg(MachineInstr &MI, LiveReg &LR,
1000 Register Hint0, bool LookAtPhysRegUses) {
1001 const Register VirtReg = LR.VirtReg;
1002 assert(!LR.PhysReg);
1003
1004 const TargetRegisterClass &RC = *MRI->getRegClass(Reg: VirtReg);
1005 LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg)
1006 << " in class " << TRI->getRegClassName(&RC)
1007 << " with hint " << printReg(Hint0, TRI) << '\n');
1008
1009 // Take hint when possible.
1010 if (Hint0.isPhysical() && MRI->isAllocatable(PhysReg: Hint0) && RC.contains(Reg: Hint0) &&
1011 !isRegUsedInInstr(PhysReg: Hint0, LookAtPhysRegUses)) {
1012 // Take hint if the register is currently free.
1013 if (isPhysRegFree(PhysReg: Hint0)) {
1014 LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
1015 << '\n');
1016 assignVirtToPhysReg(AtMI&: MI, LR, PhysReg: Hint0);
1017 return;
1018 } else {
1019 LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint0, TRI)
1020 << " occupied\n");
1021 }
1022 } else {
1023 Hint0 = Register();
1024 }
1025
1026 // Try other hint.
1027 Register Hint1 = traceCopies(VirtReg);
1028 if (Hint1.isPhysical() && MRI->isAllocatable(PhysReg: Hint1) && RC.contains(Reg: Hint1) &&
1029 !isRegUsedInInstr(PhysReg: Hint1, LookAtPhysRegUses)) {
1030 // Take hint if the register is currently free.
1031 if (isPhysRegFree(PhysReg: Hint1)) {
1032 LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
1033 << '\n');
1034 assignVirtToPhysReg(AtMI&: MI, LR, PhysReg: Hint1);
1035 return;
1036 } else {
1037 LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint1, TRI)
1038 << " occupied\n");
1039 }
1040 } else {
1041 Hint1 = Register();
1042 }
1043
1044 MCPhysReg BestReg = 0;
1045 unsigned BestCost = spillImpossible;
1046 ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(RC: &RC);
1047 for (MCPhysReg PhysReg : AllocationOrder) {
1048 LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << ' ');
1049 if (isRegUsedInInstr(PhysReg, LookAtPhysRegUses)) {
1050 LLVM_DEBUG(dbgs() << "already used in instr.\n");
1051 continue;
1052 }
1053
1054 unsigned Cost = calcSpillCost(PhysReg);
1055 LLVM_DEBUG(dbgs() << "Cost: " << Cost << " BestCost: " << BestCost << '\n');
1056 // Immediate take a register with cost 0.
1057 if (Cost == 0) {
1058 assignVirtToPhysReg(AtMI&: MI, LR, PhysReg);
1059 return;
1060 }
1061
1062 if (PhysReg == Hint0 || PhysReg == Hint1)
1063 Cost -= spillPrefBonus;
1064
1065 if (Cost < BestCost) {
1066 BestReg = PhysReg;
1067 BestCost = Cost;
1068 }
1069 }
1070
1071 if (!BestReg) {
1072 // Nothing we can do: Report an error and keep going with an invalid
1073 // allocation.
1074 LR.PhysReg = getErrorAssignment(LR, MI, RC);
1075 LR.Error = true;
1076 return;
1077 }
1078
1079 displacePhysReg(MI, PhysReg: BestReg);
1080 assignVirtToPhysReg(AtMI&: MI, LR, PhysReg: BestReg);
1081}
1082
1083void RegAllocFastImpl::allocVirtRegUndef(MachineOperand &MO) {
1084 assert(MO.isUndef() && "expected undef use");
1085 Register VirtReg = MO.getReg();
1086 assert(VirtReg.isVirtual() && "Expected virtreg");
1087 if (!shouldAllocateRegister(Reg: VirtReg))
1088 return;
1089
1090 // If there are multiple undef uses, give them the same register. The def is
1091 // already freed, so take the register from the tie, not the lookup below.
1092 MachineInstr &MI = *MO.getParent();
1093 for (const MachineOperand &Tied : MI.all_uses()) {
1094 if (!Tied.isTied() || Tied.getReg() != VirtReg)
1095 continue;
1096 MCRegister DefReg = getTiedOperand(MI, MO: Tied).getReg().asMCReg();
1097 for (MachineOperand &O : MI.all_uses()) {
1098 if (O.getReg() != VirtReg)
1099 continue;
1100 // The def is already narrowed, so a tie takes its register whole.
1101 unsigned SubIdx = O.isTied() ? 0 : O.getSubReg();
1102 O.setReg(SubIdx ? TRI->getSubReg(Reg: DefReg, Idx: SubIdx) : DefReg);
1103 O.setSubReg(0);
1104 O.setIsRenamable(!MRI->isReserved(PhysReg: O.getReg()));
1105 }
1106 return;
1107 }
1108
1109 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
1110 MCRegister PhysReg;
1111 bool IsRenamable = true;
1112 if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
1113 PhysReg = LRI->PhysReg;
1114 } else {
1115 const TargetRegisterClass &RC = *MRI->getRegClass(Reg: VirtReg);
1116 ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(RC: &RC);
1117 if (AllocationOrder.empty()) {
1118 // All registers in the class were reserved.
1119 //
1120 // It might be OK to take any entry from the class as this is an undef
1121 // use, but accepting this would give different behavior than greedy and
1122 // basic.
1123 PhysReg = getErrorAssignment(LR: *LRI, MI&: *MO.getParent(), RC);
1124 LRI->Error = true;
1125 IsRenamable = false;
1126 } else
1127 PhysReg = AllocationOrder.front();
1128 }
1129
1130 unsigned SubRegIdx = MO.getSubReg();
1131 if (SubRegIdx != 0) {
1132 PhysReg = TRI->getSubReg(Reg: PhysReg, Idx: SubRegIdx);
1133 MO.setSubReg(0);
1134 }
1135 MO.setReg(PhysReg);
1136 MO.setIsRenamable(IsRenamable);
1137}
1138
1139/// Variation of defineVirtReg() with special handling for livethrough regs
1140/// (tied or earlyclobber) that may interfere with preassigned uses.
1141/// \return true if MI's MachineOperands were re-arranged/invalidated.
1142bool RegAllocFastImpl::defineLiveThroughVirtReg(MachineInstr &MI,
1143 unsigned OpNum,
1144 Register VirtReg) {
1145 if (!shouldAllocateRegister(Reg: VirtReg))
1146 return false;
1147 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
1148 if (LRI != LiveVirtRegs.end()) {
1149 MCRegister PrevReg = LRI->PhysReg;
1150 if (PrevReg && isRegUsedInInstr(PhysReg: PrevReg, LookAtPhysRegUses: true)) {
1151 LLVM_DEBUG(dbgs() << "Need new assignment for " << printReg(PrevReg, TRI)
1152 << " (tied/earlyclobber resolution)\n");
1153 freePhysReg(PhysReg: PrevReg);
1154 LRI->PhysReg = MCRegister();
1155 allocVirtReg(MI, LR&: *LRI, Hint0: Register(), LookAtPhysRegUses: true);
1156 MachineBasicBlock::iterator InsertBefore =
1157 std::next(x: (MachineBasicBlock::iterator)MI.getIterator());
1158 LLVM_DEBUG(dbgs() << "Copy " << printReg(LRI->PhysReg, TRI) << " to "
1159 << printReg(PrevReg, TRI) << '\n');
1160 BuildMI(BB&: *MBB, I: InsertBefore, MIMD: MI.getDebugLoc(),
1161 MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: PrevReg)
1162 .addReg(RegNo: LRI->PhysReg, Flags: llvm::RegState::Kill);
1163 }
1164 MachineOperand &MO = MI.getOperand(i: OpNum);
1165 if (MO.getSubReg() && !MO.isUndef()) {
1166 LRI->LastUse = &MI;
1167 }
1168 }
1169 return defineVirtReg(MI, OpNum, VirtReg, LookAtPhysRegUses: true);
1170}
1171
1172/// Allocates a register for VirtReg definition. Typically the register is
1173/// already assigned from a use of the virtreg, however we still need to
1174/// perform an allocation if:
1175/// - It is a dead definition without any uses.
1176/// - The value is live out and all uses are in different basic blocks.
1177///
1178/// \return true if MI's MachineOperands were re-arranged/invalidated.
1179bool RegAllocFastImpl::defineVirtReg(MachineInstr &MI, unsigned OpNum,
1180 Register VirtReg, bool LookAtPhysRegUses) {
1181 assert(VirtReg.isVirtual() && "Not a virtual register");
1182 if (!shouldAllocateRegister(Reg: VirtReg))
1183 return false;
1184 MachineOperand &MO = MI.getOperand(i: OpNum);
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 return setPhysReg(MI, 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.
1317/// \return true if MI's MachineOperands were re-arranged/invalidated.
1318bool RegAllocFastImpl::useVirtReg(MachineInstr &MI, MachineOperand &MO,
1319 Register VirtReg) {
1320 assert(VirtReg.isVirtual() && "Not a virtual register");
1321 if (!shouldAllocateRegister(Reg: VirtReg))
1322 return false;
1323 LiveRegMap::iterator LRI;
1324 bool New;
1325 std::tie(args&: LRI, args&: New) = LiveVirtRegs.insert(Val: LiveReg(VirtReg));
1326 if (New) {
1327 if (!MO.isKill()) {
1328 if (mayLiveOut(VirtReg)) {
1329 LRI->LiveOut = true;
1330 } else {
1331 // It is a last (killing) use without the kill flag; add the flag now.
1332 MO.setIsKill(true);
1333 }
1334 }
1335 } else {
1336 assert((!MO.isKill() || LRI->LastUse == &MI) && "Invalid kill flag");
1337 }
1338
1339 if (LowerTiedOps && MO.isTied() && lowerTiedUse(MI, MO, LR&: *LRI))
1340 return false;
1341
1342 // If necessary allocate a register.
1343 if (!LRI->PhysReg) {
1344 assert(!MO.isTied() && "tied op should be allocated");
1345 Register Hint;
1346 if (MI.isCopy() && MI.getOperand(i: 1).getSubReg() == 0) {
1347 Hint = MI.getOperand(i: 0).getReg();
1348 if (Hint.isVirtual()) {
1349 assert(!shouldAllocateRegister(Hint));
1350 Hint = Register();
1351 } else {
1352 assert(Hint.isPhysical() &&
1353 "Copy destination should already be assigned");
1354 }
1355 }
1356 allocVirtReg(MI, LR&: *LRI, Hint0: Hint, LookAtPhysRegUses: false);
1357 }
1358
1359 LRI->LastUse = &MI;
1360
1361 if (MI.getOpcode() == TargetOpcode::BUNDLE) {
1362 BundleVirtRegsMap[VirtReg] = *LRI;
1363 }
1364 markRegUsedInInstr(PhysReg: LRI->PhysReg);
1365 return setPhysReg(MI, MO, Assignment: *LRI);
1366}
1367
1368/// Query a physical register to use as a filler in contexts where the
1369/// allocation has failed. This will raise an error, but not abort the
1370/// compilation.
1371MCPhysReg RegAllocFastImpl::getErrorAssignment(const LiveReg &LR,
1372 MachineInstr &MI,
1373 const TargetRegisterClass &RC) {
1374 MachineFunction &MF = *MI.getMF();
1375
1376 // Avoid repeating the error every time a register is used.
1377 bool EmitError = !MF.getProperties().hasFailedRegAlloc();
1378 if (EmitError)
1379 MF.getProperties().setFailedRegAlloc();
1380
1381 // If the allocation order was empty, all registers in the class were
1382 // probably reserved. Fall back to taking the first register in the class,
1383 // even if it's reserved.
1384 ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(RC: &RC);
1385 if (AllocationOrder.empty()) {
1386 const Function &Fn = MF.getFunction();
1387 if (EmitError) {
1388 Fn.getContext().diagnose(DI: DiagnosticInfoRegAllocFailure(
1389 "no registers from class available to allocate", Fn,
1390 MI.getDebugLoc()));
1391 }
1392
1393 ArrayRef<MCPhysReg> RawRegs = RC.getRegisters();
1394 assert(!RawRegs.empty() && "register classes cannot have no registers");
1395 return RawRegs.front();
1396 }
1397
1398 if (!LR.Error && EmitError) {
1399 // Nothing we can do: Report an error and keep going with an invalid
1400 // allocation.
1401 if (MI.isInlineAsm()) {
1402 MI.emitInlineAsmError(
1403 ErrMsg: "inline assembly requires more registers than available");
1404 } else {
1405 const Function &Fn = MBB->getParent()->getFunction();
1406 Fn.getContext().diagnose(DI: DiagnosticInfoRegAllocFailure(
1407 "ran out of registers during register allocation", Fn,
1408 MI.getDebugLoc()));
1409 }
1410 }
1411
1412 return AllocationOrder.front();
1413}
1414
1415/// Changes operand OpNum in MI the refer the PhysReg, considering subregs.
1416/// \return true if MI's MachineOperands were re-arranged/invalidated.
1417bool RegAllocFastImpl::setPhysReg(MachineInstr &MI, MachineOperand &MO,
1418 const LiveReg &Assignment) {
1419 MCRegister PhysReg = Assignment.PhysReg;
1420 assert(PhysReg && "assignments should always be to a valid physreg");
1421
1422 if (LLVM_UNLIKELY(Assignment.Error)) {
1423 // Make sure we don't set renamable in error scenarios, as we may have
1424 // assigned to a reserved register.
1425 if (MO.isUse())
1426 MO.setIsUndef(true);
1427 }
1428
1429 if (!MO.getSubReg()) {
1430 MO.setReg(PhysReg);
1431 MO.setIsRenamable(!Assignment.Error);
1432 return false;
1433 }
1434
1435 // Handle subregister index.
1436 MO.setReg(TRI->getSubReg(Reg: PhysReg, Idx: MO.getSubReg()));
1437 MO.setIsRenamable(!Assignment.Error);
1438
1439 // Note: We leave the subreg number around a little longer in case of defs.
1440 // This is so that the register freeing logic in allocateInstruction can still
1441 // recognize this as subregister defs. The code there will clear the number.
1442 if (!MO.isDef())
1443 MO.setSubReg(0);
1444
1445 // A kill flag implies killing the full register. Add corresponding super
1446 // register kill.
1447 if (MO.isKill()) {
1448 MI.addRegisterKilled(IncomingReg: PhysReg, RegInfo: TRI, AddIfNotFound: true);
1449 // Conservatively assume implicit MOs were re-arranged
1450 return true;
1451 }
1452
1453 // A <def,read-undef> of a sub-register requires an implicit def of the full
1454 // register.
1455 if (MO.isDef() && MO.isUndef()) {
1456 if (MO.isDead())
1457 MI.addRegisterDead(Reg: PhysReg, RegInfo: TRI, AddIfNotFound: true);
1458 else
1459 MI.addRegisterDefined(Reg: PhysReg, RegInfo: TRI);
1460 // Conservatively assume implicit MOs were re-arranged
1461 return true;
1462 }
1463 return false;
1464}
1465
1466#ifndef NDEBUG
1467
1468void RegAllocFastImpl::dumpState() const {
1469 for (MCRegUnit Unit : TRI->regunits()) {
1470 switch (unsigned VirtReg = getRegUnitState(Unit)) {
1471 case regFree:
1472 break;
1473 case regPreAssigned:
1474 dbgs() << " " << printRegUnit(Unit, TRI) << "[P]";
1475 break;
1476 case regLiveIn:
1477 llvm_unreachable("Should not have regLiveIn in map");
1478 default: {
1479 dbgs() << ' ' << printRegUnit(Unit, TRI) << '=' << printReg(VirtReg);
1480 LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
1481 assert(I != LiveVirtRegs.end() && "have LiveVirtRegs entry");
1482 if (I->LiveOut || I->Reloaded) {
1483 dbgs() << '[';
1484 if (I->LiveOut)
1485 dbgs() << 'O';
1486 if (I->Reloaded)
1487 dbgs() << 'R';
1488 dbgs() << ']';
1489 }
1490 assert(TRI->hasRegUnit(I->PhysReg, Unit) && "inverse mapping present");
1491 break;
1492 }
1493 }
1494 }
1495 dbgs() << '\n';
1496 // Check that LiveVirtRegs is the inverse.
1497 for (const LiveReg &LR : LiveVirtRegs) {
1498 Register VirtReg = LR.VirtReg;
1499 assert(VirtReg.isVirtual() && "Bad map key");
1500 MCRegister PhysReg = LR.PhysReg;
1501 if (PhysReg) {
1502 assert(PhysReg.isPhysical() && "mapped to physreg");
1503 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
1504 assert(getRegUnitState(Unit) == VirtReg && "inverse map valid");
1505 }
1506 }
1507 }
1508}
1509#endif
1510
1511/// Count number of defs consumed from each register class by \p Reg
1512void RegAllocFastImpl::addRegClassDefCounts(
1513 MutableArrayRef<unsigned> RegClassDefCounts, Register Reg) const {
1514 assert(RegClassDefCounts.size() == TRI->getNumRegClasses());
1515
1516 if (Reg.isVirtual()) {
1517 if (!shouldAllocateRegister(Reg))
1518 return;
1519 const TargetRegisterClass *OpRC = MRI->getRegClass(Reg);
1520 for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();
1521 RCIdx != RCIdxEnd; ++RCIdx) {
1522 const TargetRegisterClass *IdxRC = TRI->getRegClass(i: RCIdx);
1523 // FIXME: Consider aliasing sub/super registers.
1524 if (OpRC->hasSubClassEq(RC: IdxRC))
1525 ++RegClassDefCounts[RCIdx];
1526 }
1527
1528 return;
1529 }
1530
1531 for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();
1532 RCIdx != RCIdxEnd; ++RCIdx) {
1533 const TargetRegisterClass *IdxRC = TRI->getRegClass(i: RCIdx);
1534 for (MCRegAliasIterator Alias(Reg, TRI, true); Alias.isValid(); ++Alias) {
1535 if (IdxRC->contains(Reg: *Alias)) {
1536 ++RegClassDefCounts[RCIdx];
1537 break;
1538 }
1539 }
1540 }
1541}
1542
1543/// Early clobber, partial def, or tied to a use that carries a value: the
1544/// register is occupied while the uses are read.
1545static bool isLiveThroughDef(const MachineInstr &MI, const MachineOperand &MO) {
1546 assert(MO.isDef() && "expected def operand");
1547 if (MO.isEarlyClobber() || MO.readsReg())
1548 return true;
1549 return MO.isTied() &&
1550 !MI.getOperand(i: MI.findTiedOperandIdx(OpIdx: MI.getOperandNo(I: &MO))).isUndef();
1551}
1552
1553/// Compute \ref DefOperandIndexes so it contains the indices of "def" operands
1554/// that are to be allocated. Those are ordered in a way that small classes,
1555/// early clobbers and livethroughs are allocated first.
1556void RegAllocFastImpl::findAndSortDefOperandIndexes(const MachineInstr &MI) {
1557 DefOperandIndexes.clear();
1558
1559 LLVM_DEBUG(dbgs() << "Need to assign livethroughs\n");
1560 for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {
1561 const MachineOperand &MO = MI.getOperand(i: I);
1562 if (!MO.isReg())
1563 continue;
1564 Register Reg = MO.getReg();
1565 if (MO.readsReg()) {
1566 if (Reg.isPhysical()) {
1567 LLVM_DEBUG(dbgs() << "mark extra used: " << printReg(Reg, TRI) << '\n');
1568 markPhysRegUsedInInstr(PhysReg: Reg);
1569 }
1570 }
1571
1572 if (MO.isDef() && Reg.isVirtual() && shouldAllocateRegister(Reg))
1573 DefOperandIndexes.push_back(Elt: I);
1574 }
1575
1576 // Most instructions only have one virtual def, so there's no point in
1577 // computing the possible number of defs for every register class.
1578 if (DefOperandIndexes.size() <= 1)
1579 return;
1580
1581 // Track number of defs which may consume a register from the class. This is
1582 // used to assign registers for possibly-too-small classes first. Example:
1583 // defs are eax, 3 * gr32_abcd, 2 * gr32 => we want to assign the gr32_abcd
1584 // registers first so that the gr32 don't use the gr32_abcd registers before
1585 // we assign these.
1586 SmallVector<unsigned> RegClassDefCounts(TRI->getNumRegClasses(), 0);
1587
1588 for (const MachineOperand &MO : MI.all_defs())
1589 addRegClassDefCounts(RegClassDefCounts, Reg: MO.getReg());
1590
1591 llvm::sort(C&: DefOperandIndexes, Comp: [&](unsigned I0, unsigned I1) {
1592 const MachineOperand &MO0 = MI.getOperand(i: I0);
1593 const MachineOperand &MO1 = MI.getOperand(i: I1);
1594 Register Reg0 = MO0.getReg();
1595 Register Reg1 = MO1.getReg();
1596 const TargetRegisterClass &RC0 = *MRI->getRegClass(Reg: Reg0);
1597 const TargetRegisterClass &RC1 = *MRI->getRegClass(Reg: Reg1);
1598
1599 // Identify regclass that are easy to use up completely just in this
1600 // instruction.
1601 unsigned ClassSize0 = RegClassInfo.getOrder(RC: &RC0).size();
1602 unsigned ClassSize1 = RegClassInfo.getOrder(RC: &RC1).size();
1603
1604 bool SmallClass0 = ClassSize0 < RegClassDefCounts[RC0.getID()];
1605 bool SmallClass1 = ClassSize1 < RegClassDefCounts[RC1.getID()];
1606 if (SmallClass0 > SmallClass1)
1607 return true;
1608 if (SmallClass0 < SmallClass1)
1609 return false;
1610
1611 // Allocate early clobbers and livethrough operands first.
1612 bool Livethrough0 = isLiveThroughDef(MI, MO: MO0);
1613 bool Livethrough1 = isLiveThroughDef(MI, MO: MO1);
1614 if (Livethrough0 > Livethrough1)
1615 return true;
1616 if (Livethrough0 < Livethrough1)
1617 return false;
1618
1619 // Tie-break rule: operand index.
1620 return I0 < I1;
1621 });
1622}
1623
1624void RegAllocFastImpl::allocateInstruction(MachineInstr &MI) {
1625 // Backwards, a def frees a register and a use occupies it. The phases:
1626 // * pre-assigned physreg defs
1627 // * virtual register defs
1628 // * free the def operands' registers
1629 // * displace registers clobbered by regmasks
1630 // * pre-assigned physreg uses
1631 // * virtual register uses, inserting reloads and tied-operand copies
1632 // * undef uses
1633 // * free early-clobber defs
1634 //
1635 // Freeing follows the def allocation so a def is not handed a register this
1636 // instruction also writes, and precedes the uses so a use may take one. It
1637 // skips tied defs, whose register the tied use reads, and early-clobber defs,
1638 // freed last so that no use lands on them.
1639
1640 InstrGen += 2;
1641 // In the event we ever get more than 2**31 instructions...
1642 if (LLVM_UNLIKELY(InstrGen == 0)) {
1643 UsedInInstr.assign(NumElts: UsedInInstr.size(), Elt: 0);
1644 LiveDefUnits.assign(NumElts: LiveDefUnits.size(), Elt: 0);
1645 InstrGen = 2;
1646 }
1647 RegMasks.clear();
1648 BundleVirtRegsMap.clear();
1649
1650 // Scan for special cases; Apply pre-assigned register defs to state.
1651 bool HasPhysRegUse = false;
1652 bool HasRegMask = false;
1653 bool HasVRegDef = false;
1654 bool HasDef = false;
1655 bool HasEarlyClobber = false;
1656 bool HasTiedDef = false;
1657 bool NeedToAssignLiveThroughs = false;
1658 for (MachineOperand &MO : MI.operands()) {
1659 if (MO.isReg()) {
1660 Register Reg = MO.getReg();
1661 if (Reg.isVirtual()) {
1662 if (!shouldAllocateRegister(Reg))
1663 continue;
1664 if (MO.isDef()) {
1665 HasDef = true;
1666 HasVRegDef = true;
1667 if (MO.isEarlyClobber())
1668 HasEarlyClobber = true;
1669 if (LowerTiedOps && MO.isTied())
1670 HasTiedDef = true;
1671 if (isLiveThroughDef(MI, MO))
1672 NeedToAssignLiveThroughs = true;
1673 }
1674 } else if (Reg.isPhysical()) {
1675 if (!MRI->isReserved(PhysReg: Reg)) {
1676 if (MO.isDef()) {
1677 HasDef = true;
1678 bool displacedAny = definePhysReg(MI, Reg);
1679 if (MO.isEarlyClobber())
1680 HasEarlyClobber = true;
1681 if (!displacedAny)
1682 MO.setIsDead(true);
1683 if (!MO.isDead())
1684 markLiveDefUnits(PhysReg: Reg.asMCReg());
1685 }
1686 if (MO.readsReg())
1687 HasPhysRegUse = true;
1688 }
1689 }
1690 } else if (MO.isRegMask()) {
1691 HasRegMask = true;
1692 RegMasks.push_back(Elt: MO.getRegMask());
1693 }
1694 }
1695
1696 // Allocate virtreg defs.
1697 if (HasDef) {
1698 if (HasVRegDef) {
1699 // Note that Implicit MOs can get re-arranged by defineVirtReg(), so loop
1700 // multiple times to ensure no operand is missed.
1701 bool ReArrangedImplicitOps = true;
1702
1703 // Special handling for early clobbers, tied operands or subregister defs:
1704 // Compared to "normal" defs these:
1705 // - Must not use a register that is pre-assigned for a use operand.
1706 // - In order to solve tricky inline assembly constraints we change the
1707 // heuristic to figure out a good operand order before doing
1708 // assignments.
1709 if (NeedToAssignLiveThroughs) {
1710 while (ReArrangedImplicitOps) {
1711 ReArrangedImplicitOps = false;
1712 findAndSortDefOperandIndexes(MI);
1713 for (unsigned OpIdx : DefOperandIndexes) {
1714 MachineOperand &MO = MI.getOperand(i: OpIdx);
1715 LLVM_DEBUG(dbgs() << "Allocating " << MO << '\n');
1716 Register Reg = MO.getReg();
1717 if (isLiveThroughDef(MI, MO)) {
1718 ReArrangedImplicitOps = defineLiveThroughVirtReg(MI, OpNum: OpIdx, VirtReg: Reg);
1719 } else {
1720 ReArrangedImplicitOps = defineVirtReg(MI, OpNum: OpIdx, VirtReg: Reg);
1721 }
1722 // Implicit operands of MI were re-arranged,
1723 // re-compute DefOperandIndexes.
1724 if (ReArrangedImplicitOps)
1725 break;
1726 }
1727 }
1728 } else {
1729 // Assign virtual register defs.
1730 while (ReArrangedImplicitOps) {
1731 ReArrangedImplicitOps = false;
1732 for (MachineOperand &MO : MI.all_defs()) {
1733 Register Reg = MO.getReg();
1734 if (Reg.isVirtual()) {
1735 ReArrangedImplicitOps =
1736 defineVirtReg(MI, OpNum: MI.getOperandNo(I: &MO), VirtReg: Reg);
1737 if (ReArrangedImplicitOps)
1738 break;
1739 }
1740 }
1741 }
1742 }
1743 }
1744
1745 // Free registers occupied by defs.
1746 // Iterate operands in reverse order, so we see the implicit super register
1747 // defs first (we added them earlier in case of <def,read-undef>).
1748 for (MachineOperand &MO : reverse(C: MI.all_defs())) {
1749 Register Reg = MO.getReg();
1750
1751 // A dead def whose register units are all covered by non-dead aliasing
1752 // defs is kept alive by them, so clear the inconsistent dead flag.
1753 if (Reg.isPhysical() && MO.isDead() && hasLiveDefUnits(PhysReg: Reg.asMCReg()))
1754 MO.setIsDead(false);
1755
1756 // subreg defs don't free the full register. We left the subreg number
1757 // around as a marker in setPhysReg() to recognize this case here.
1758 if (Reg.isPhysical() && MO.getSubReg() != 0) {
1759 MO.setSubReg(0);
1760 continue;
1761 }
1762
1763 assert((!MO.isTied() || !isClobberedByRegMasks(MO.getReg())) &&
1764 "tied def assigned to clobbered register");
1765
1766 // Do not free live-through defs.
1767 if (isLiveThroughDef(MI, MO))
1768 continue;
1769 if (!Reg)
1770 continue;
1771 if (Reg.isVirtual()) {
1772 assert(!shouldAllocateRegister(Reg));
1773 continue;
1774 }
1775 assert(Reg.isPhysical());
1776 if (MRI->isReserved(PhysReg: Reg))
1777 continue;
1778 freePhysReg(PhysReg: Reg);
1779 unmarkRegUsedInInstr(PhysReg: Reg);
1780 }
1781 }
1782
1783 // A regmask is a def of every clobbered register: reload what lives in one
1784 // below MI. Nothing is reserved, so the uses may still take those registers.
1785 if (HasRegMask) {
1786 assert(!RegMasks.empty() && "expected RegMask");
1787 // MRI bookkeeping.
1788 for (const auto *RM : RegMasks)
1789 MRI->addPhysRegsUsedFromRegMask(RegMask: RM);
1790
1791 for (const LiveReg &LR : LiveVirtRegs) {
1792 MCRegister PhysReg = LR.PhysReg;
1793 if (PhysReg && isClobberedByRegMasks(PhysReg))
1794 displacePhysReg(MI, PhysReg);
1795 }
1796 }
1797
1798 // Apply pre-assigned register uses to state.
1799 if (HasPhysRegUse) {
1800 for (MachineOperand &MO : MI.operands()) {
1801 if (!MO.isReg() || !MO.readsReg())
1802 continue;
1803 Register Reg = MO.getReg();
1804 if (!Reg.isPhysical())
1805 continue;
1806 if (MRI->isReserved(PhysReg: Reg))
1807 continue;
1808 if (!usePhysReg(MI, Reg))
1809 MO.setIsKill(true);
1810 }
1811 }
1812
1813 // Allocate virtreg uses and insert reloads as necessary.
1814 // Implicit MOs can get moved/removed by useVirtReg(), so loop multiple
1815 // times to ensure no operand is missed.
1816 bool HasUndefUse = false;
1817 bool TiedOnly = HasTiedDef;
1818 bool ReArrangedImplicitMOs = true;
1819 while (ReArrangedImplicitMOs) {
1820 ReArrangedImplicitMOs = false;
1821 for (MachineOperand &MO : MI.operands()) {
1822 if (!MO.isReg() || !MO.isUse())
1823 continue;
1824 Register Reg = MO.getReg();
1825 if (!Reg.isVirtual() || !shouldAllocateRegister(Reg) ||
1826 (TiedOnly && !MO.isTied()))
1827 continue;
1828
1829 if (MO.isUndef()) {
1830 HasUndefUse = true;
1831 continue;
1832 }
1833
1834 // Populate MayLiveAcrossBlocks now: these uses are about to be rewritten
1835 // to physregs, so a def block allocated later can no longer see them.
1836 mayLiveIn(VirtReg: Reg);
1837
1838 assert(!MO.isInternalRead() && "Bundles not supported");
1839 assert(MO.readsReg() && "reading use");
1840 ReArrangedImplicitMOs = useVirtReg(MI, MO, VirtReg: Reg);
1841 if (ReArrangedImplicitMOs)
1842 break;
1843 }
1844 // Given %1 = OP %0, %0(tied-def 0), allocate tied %0 first, so that %0
1845 // takes %1's register. In operand order, the untied %0 would take another
1846 // register and the tied use would need a copy.
1847 if (TiedOnly && !ReArrangedImplicitMOs) {
1848 TiedOnly = false;
1849 ReArrangedImplicitMOs = true;
1850 }
1851 }
1852
1853 // Allocate undef operands. This is a separate step because in a situation
1854 // like ` = OP undef %X, %X` both operands need the same register assign
1855 // so we should perform the normal assignment first.
1856 if (HasUndefUse) {
1857 for (MachineOperand &MO : MI.all_uses()) {
1858 Register Reg = MO.getReg();
1859 if (!Reg.isVirtual() || !shouldAllocateRegister(Reg))
1860 continue;
1861
1862 assert(MO.isUndef() && "Should only have undef virtreg uses left");
1863 allocVirtRegUndef(MO);
1864 }
1865 }
1866
1867 // Free early clobbers. Last, because they must not share a register with any
1868 // use.
1869 if (HasEarlyClobber) {
1870 for (MachineOperand &MO : reverse(C: MI.all_defs())) {
1871 if (!MO.isEarlyClobber())
1872 continue;
1873 assert(!MO.getSubReg() && "should be already handled in def processing");
1874
1875 Register Reg = MO.getReg();
1876 if (!Reg)
1877 continue;
1878 if (Reg.isVirtual()) {
1879 assert(!shouldAllocateRegister(Reg));
1880 continue;
1881 }
1882 assert(Reg.isPhysical() && "should have register assigned");
1883
1884 // We sometimes get odd situations like:
1885 // early-clobber %x0 = INSTRUCTION %x0
1886 // which is semantically questionable as the early-clobber should
1887 // apply before the use. But in practice we consider the use to
1888 // happen before the early clobber now. Don't free the early clobber
1889 // register in this case.
1890 if (MI.readsRegister(Reg, TRI))
1891 continue;
1892
1893 freePhysReg(PhysReg: Reg);
1894 }
1895 }
1896
1897 LLVM_DEBUG(dbgs() << "<< " << MI);
1898 if (MI.isCopy() &&
1899 (MI.getOperand(i: 0).getReg() == MI.getOperand(i: 1).getReg() ||
1900 MI.getOperand(i: 0).isDead()) &&
1901 MI.getNumOperands() == 2) {
1902 LLVM_DEBUG(dbgs() << "Mark unnecessary copy for removal: " << MI);
1903 Coalesced.push_back(Elt: &MI);
1904 }
1905}
1906
1907void RegAllocFastImpl::handleDebugValue(MachineInstr &MI) {
1908 // Ignore DBG_VALUEs that aren't based on virtual registers. These are
1909 // mostly constants and frame indices.
1910 assert(MI.isDebugValue() && "not a DBG_VALUE*");
1911 for (const auto &MO : MI.debug_operands()) {
1912 if (!MO.isReg())
1913 continue;
1914 Register Reg = MO.getReg();
1915 if (!Reg.isVirtual())
1916 continue;
1917 if (!shouldAllocateRegister(Reg))
1918 continue;
1919
1920 // Already spilled to a stackslot?
1921 int SS = StackSlotForVirtReg[Reg];
1922 if (SS != -1) {
1923 // Modify DBG_VALUE now that the value is in a spill slot.
1924 updateDbgValueForSpill(Orig&: MI, FrameIndex: SS, Reg);
1925 LLVM_DEBUG(dbgs() << "Rewrite DBG_VALUE for spilled memory: " << MI);
1926 continue;
1927 }
1928
1929 // See if this virtual register has already been allocated to a physical
1930 // register or spilled to a stack slot.
1931 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg: Reg);
1932 SmallVector<MachineOperand *> DbgOps(
1933 llvm::make_pointer_range(Range: MI.getDebugOperandsForReg(Reg)));
1934
1935 if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
1936 // Update every use of Reg within MI.
1937 for (auto &RegMO : DbgOps)
1938 setPhysReg(MI, MO&: *RegMO, Assignment: *LRI);
1939 } else {
1940 DanglingDbgValues[Reg].push_back(Elt: &MI);
1941 }
1942
1943 // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so
1944 // that future spills of Reg will have DBG_VALUEs.
1945 LiveDbgValueMap[Reg].append(in_start: DbgOps.begin(), in_end: DbgOps.end());
1946 }
1947}
1948
1949void RegAllocFastImpl::handleBundle(MachineInstr &MI) {
1950 MachineBasicBlock::instr_iterator BundledMI = MI.getIterator();
1951 ++BundledMI;
1952 while (BundledMI->isBundledWithPred()) {
1953 for (MachineOperand &MO : BundledMI->operands()) {
1954 if (!MO.isReg())
1955 continue;
1956
1957 Register Reg = MO.getReg();
1958 if (!Reg.isVirtual() || !shouldAllocateRegister(Reg))
1959 continue;
1960
1961 auto DI = BundleVirtRegsMap.find(Val: Reg);
1962 assert(DI != BundleVirtRegsMap.end() && "Unassigned virtual register");
1963
1964 setPhysReg(MI, MO, Assignment: DI->second);
1965 }
1966
1967 ++BundledMI;
1968 }
1969}
1970
1971void RegAllocFastImpl::allocateBasicBlock(MachineBasicBlock &MBB) {
1972 this->MBB = &MBB;
1973 LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);
1974
1975 PosIndexes.unsetInitialized();
1976 RegUnitStates.assign(n: TRI->getNumRegUnits(), val: regFree);
1977 assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
1978
1979 for (const auto &LiveReg : MBB.liveouts())
1980 setPhysRegState(PhysReg: LiveReg.PhysReg, NewState: regPreAssigned);
1981
1982 Coalesced.clear();
1983
1984 // Lowering a tied operand inserts a copy ahead of MI. Its registers are
1985 // already assigned, so visiting it would evict what still lives in the
1986 // source.
1987 for (MachineInstr &MI : make_early_inc_range(Range: reverse(C&: MBB))) {
1988 LLVM_DEBUG(dbgs() << "\n>> " << MI << "Regs:"; dumpState());
1989
1990 // Special handling for debug values. Note that they are not allowed to
1991 // affect codegen of the other instructions in any way.
1992 if (MI.isDebugValue()) {
1993 handleDebugValue(MI);
1994 continue;
1995 }
1996
1997 allocateInstruction(MI);
1998
1999 // Once BUNDLE header is assigned registers, same assignments need to be
2000 // done for bundled MIs.
2001 if (MI.getOpcode() == TargetOpcode::BUNDLE) {
2002 handleBundle(MI);
2003 }
2004 }
2005
2006 LLVM_DEBUG(dbgs() << "Begin Regs:"; dumpState());
2007
2008 // Spill all physical registers holding virtual registers now.
2009 LLVM_DEBUG(dbgs() << "Loading live registers at begin of block.\n");
2010 reloadAtBegin(MBB);
2011
2012 // Erase all the coalesced copies. We are delaying it until now because
2013 // LiveVirtRegs might refer to the instrs.
2014 for (MachineInstr *MI : Coalesced)
2015 MBB.erase(I: MI);
2016 NumCoalesced += Coalesced.size();
2017
2018 for (auto &UDBGPair : DanglingDbgValues) {
2019 for (MachineInstr *DbgValue : UDBGPair.second) {
2020 assert(DbgValue->isDebugValue() && "expected DBG_VALUE");
2021 // Nothing to do if the vreg was spilled in the meantime.
2022 if (!DbgValue->hasDebugOperandForReg(Reg: UDBGPair.first))
2023 continue;
2024 LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue
2025 << '\n');
2026 DbgValue->setDebugValueUndef();
2027 }
2028 }
2029 DanglingDbgValues.clear();
2030
2031 LLVM_DEBUG(MBB.dump());
2032}
2033
2034/// Expand REG_SEQUENCE and INSERT_SUBREG into subregister COPYs: the lowering
2035/// TwoAddressInstructionPass performs when it runs before allocation, plus the
2036/// base-value copy its tie processing provides.
2037void RegAllocFastImpl::expandSubregPseudo(MachineInstr &MI) {
2038 MachineBasicBlock &MBB = *MI.getParent();
2039 const DebugLoc &DL = MI.getDebugLoc();
2040 if (MI.isInsertSubreg()) {
2041 // %d = INSERT_SUBREG %base, %sub, idx -> %d = COPY %base
2042 // %d.idx = COPY %sub
2043 const MachineOperand &BaseMO = MI.getOperand(i: 1);
2044 if (!BaseMO.isUndef())
2045 BuildMI(BB&: MBB, I&: MI, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::COPY),
2046 DestReg: MI.getOperand(i: 0).getReg())
2047 .addReg(RegNo: BaseMO.getReg(), Flags: RegState::NoFlags, SubReg: BaseMO.getSubReg());
2048 unsigned SubIdx = MI.getOperand(i: 3).getImm();
2049 MI.removeOperand(OpNo: 3);
2050 assert(MI.getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
2051 MI.getOperand(i: 0).setSubReg(SubIdx);
2052 MI.getOperand(i: 0).setIsUndef(MI.getOperand(i: 1).isUndef());
2053 MI.removeOperand(OpNo: 1);
2054 MI.setDesc(TII->get(Opcode: TargetOpcode::COPY));
2055 return;
2056 }
2057
2058 // %d = REG_SEQUENCE %s1, idx1, ... -> undef %d.idx1 = COPY %s1
2059 // %d.idx2 = COPY %s2 ...
2060 assert(MI.isRegSequence());
2061 Register Dst = MI.getOperand(i: 0).getReg();
2062 // An undef source needs no copy: the read-undef flag on the first copy
2063 // defines the whole register. One is still needed where a use reads that
2064 // lane on its own, which would otherwise read an undefined subregister.
2065 LaneBitmask ReadLanes = LaneBitmask::getNone();
2066 for (const MachineOperand &Use : MRI->use_nodbg_operands(Reg: Dst))
2067 if (unsigned UseSubIdx = Use.getSubReg())
2068 ReadLanes |= TRI->getSubRegIndexLaneMask(SubIdx: UseSubIdx);
2069
2070 bool DefEmitted = false;
2071 for (unsigned I = 1, E = MI.getNumOperands(); I + 1 < E; I += 2) {
2072 const MachineOperand &SrcMO = MI.getOperand(i: I);
2073 unsigned SubIdx = MI.getOperand(i: I + 1).getImm();
2074 if (SrcMO.isUndef() &&
2075 (ReadLanes & TRI->getSubRegIndexLaneMask(SubIdx)).none())
2076 continue;
2077 BuildMI(BB&: MBB, I&: MI, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::COPY))
2078 .addReg(RegNo: Dst, Flags: RegState::Define | getUndefRegState(B: !DefEmitted), SubReg: SubIdx)
2079 .addReg(RegNo: SrcMO.getReg(), Flags: getUndefRegState(B: SrcMO.isUndef()),
2080 SubReg: SrcMO.getSubReg());
2081 DefEmitted = true;
2082 }
2083 // Every source was undef: uses of Dst still need a definition.
2084 if (!DefEmitted) {
2085 MI.setDesc(TII->get(Opcode: TargetOpcode::IMPLICIT_DEF));
2086 while (MI.getNumOperands() > 1)
2087 MI.removeOperand(OpNo: MI.getNumOperands() - 1);
2088 return;
2089 }
2090 MI.eraseFromParent();
2091}
2092
2093bool RegAllocFastImpl::runOnMachineFunction(MachineFunction &MF) {
2094 LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
2095 << "********** Function: " << MF.getName() << '\n');
2096 MRI = &MF.getRegInfo();
2097 const TargetSubtargetInfo &STI = MF.getSubtarget();
2098 TRI = STI.getRegisterInfo();
2099 TII = STI.getInstrInfo();
2100 MFI = &MF.getFrameInfo();
2101 MRI->freezeReservedRegs();
2102 RegClassInfo.runOnMachineFunction(MF);
2103 unsigned NumRegUnits = TRI->getNumRegUnits();
2104 InstrGen = 0;
2105 UsedInInstr.assign(NumElts: NumRegUnits, Elt: 0);
2106 LiveDefUnits.assign(NumElts: NumRegUnits, Elt: 0);
2107
2108 // MIR that already went through TwoAddressInstructionPass carries
2109 // TiedOpsRewritten, so partial pipelines (-run-pass, -start-before) follow
2110 // the input they are given.
2111 LowerTiedOps = !MF.getProperties().hasTiedOpsRewritten();
2112 if (LowerTiedOps) {
2113 for (MachineBasicBlock &MBB : MF)
2114 for (MachineInstr &MI : make_early_inc_range(Range&: MBB))
2115 if (MI.isRegSequence() || MI.isInsertSubreg())
2116 expandSubregPseudo(MI);
2117 }
2118
2119 // initialize the virtual->physical register map to have a 'null'
2120 // mapping for all virtual registers
2121 unsigned NumVirtRegs = MRI->getNumVirtRegs();
2122 StackSlotForVirtReg.resize(S: NumVirtRegs);
2123 LiveVirtRegs.setUniverse(NumVirtRegs);
2124 MayLiveAcrossBlocks.clear();
2125 MayLiveAcrossBlocks.resize(N: NumVirtRegs);
2126
2127 // Loop over all of the basic blocks, eliminating virtual register references
2128 for (MachineBasicBlock &MBB : MF)
2129 allocateBasicBlock(MBB);
2130
2131 if (ClearVirtRegs) {
2132 // All machine operands and other references to virtual registers have been
2133 // replaced. Remove the virtual registers.
2134 MRI->clearVirtRegs();
2135 }
2136
2137 StackSlotForVirtReg.clear();
2138 LiveDbgValueMap.clear();
2139 return true;
2140}
2141
2142PreservedAnalyses RegAllocFastPass::run(MachineFunction &MF,
2143 MachineFunctionAnalysisManager &) {
2144 MFPropsModifier _(*this, MF);
2145 RegAllocFastImpl Impl(Opts.Filter, Opts.ClearVRegs);
2146 bool Changed = Impl.runOnMachineFunction(MF);
2147 if (!Changed)
2148 return PreservedAnalyses::all();
2149 auto PA = getMachineFunctionPassPreservedAnalyses();
2150 PA.preserveSet<CFGAnalyses>();
2151 return PA;
2152}
2153
2154void RegAllocFastPass::printPipeline(
2155 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
2156 bool PrintFilterName = Opts.FilterName != "all";
2157 bool PrintNoClearVRegs = !Opts.ClearVRegs;
2158 bool PrintSemicolon = PrintFilterName && PrintNoClearVRegs;
2159
2160 OS << "regallocfast";
2161 if (PrintFilterName || PrintNoClearVRegs) {
2162 OS << '<';
2163 if (PrintFilterName)
2164 OS << "filter=" << Opts.FilterName;
2165 if (PrintSemicolon)
2166 OS << ';';
2167 if (PrintNoClearVRegs)
2168 OS << "no-clear-vregs";
2169 OS << '>';
2170 }
2171}
2172
2173FunctionPass *llvm::createFastRegisterAllocator() { return new RegAllocFast(); }
2174
2175FunctionPass *llvm::createFastRegisterAllocator(RegAllocFilterFunc Ftor,
2176 bool ClearVirtRegs) {
2177 return new RegAllocFast(Ftor, ClearVirtRegs);
2178}
2179