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