1 //===- RegAllocFast.cpp - A fast register allocator for debug code --------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file This register allocator allocates registers to a basic block at a
10 /// time, attempting to keep values in registers and reusing registers as
11 /// appropriate.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/IndexedMap.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/SparseSet.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineFrameInfo.h"
24 #include "llvm/CodeGen/MachineFunction.h"
25 #include "llvm/CodeGen/MachineFunctionPass.h"
26 #include "llvm/CodeGen/MachineInstr.h"
27 #include "llvm/CodeGen/MachineInstrBuilder.h"
28 #include "llvm/CodeGen/MachineOperand.h"
29 #include "llvm/CodeGen/MachineRegisterInfo.h"
30 #include "llvm/CodeGen/RegAllocRegistry.h"
31 #include "llvm/CodeGen/RegisterClassInfo.h"
32 #include "llvm/CodeGen/TargetInstrInfo.h"
33 #include "llvm/CodeGen/TargetOpcodes.h"
34 #include "llvm/CodeGen/TargetRegisterInfo.h"
35 #include "llvm/CodeGen/TargetSubtargetInfo.h"
36 #include "llvm/IR/DebugLoc.h"
37 #include "llvm/IR/Metadata.h"
38 #include "llvm/InitializePasses.h"
39 #include "llvm/MC/MCInstrDesc.h"
40 #include "llvm/MC/MCRegisterInfo.h"
41 #include "llvm/Pass.h"
42 #include "llvm/Support/Casting.h"
43 #include "llvm/Support/Compiler.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Support/ErrorHandling.h"
46 #include "llvm/Support/raw_ostream.h"
47 #include <cassert>
48 #include <tuple>
49 #include <vector>
50
51 using namespace llvm;
52
53 #define DEBUG_TYPE "regalloc"
54
55 STATISTIC(NumStores, "Number of stores added");
56 STATISTIC(NumLoads , "Number of loads added");
57 STATISTIC(NumCoalesced, "Number of copies coalesced");
58
59 // FIXME: Remove this switch when all testcases are fixed!
60 static cl::opt<bool> IgnoreMissingDefs("rafast-ignore-missing-defs",
61 cl::Hidden);
62
63 static RegisterRegAlloc
64 fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
65
66 namespace {
67
68 class RegAllocFast : public MachineFunctionPass {
69 public:
70 static char ID;
71
RegAllocFast()72 RegAllocFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1) {}
73
74 private:
75 MachineFrameInfo *MFI;
76 MachineRegisterInfo *MRI;
77 const TargetRegisterInfo *TRI;
78 const TargetInstrInfo *TII;
79 RegisterClassInfo RegClassInfo;
80
81 /// Basic block currently being allocated.
82 MachineBasicBlock *MBB;
83
84 /// Maps virtual regs to the frame index where these values are spilled.
85 IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
86
87 /// Everything we know about a live virtual register.
88 struct LiveReg {
89 MachineInstr *LastUse = nullptr; ///< Last instr to use reg.
90 Register VirtReg; ///< Virtual register number.
91 MCPhysReg PhysReg = 0; ///< Currently held here.
92 bool LiveOut = false; ///< Register is possibly live out.
93 bool Reloaded = false; ///< Register was reloaded.
94 bool Error = false; ///< Could not allocate.
95
LiveReg__anon56c217e30111::RegAllocFast::LiveReg96 explicit LiveReg(Register VirtReg) : VirtReg(VirtReg) {}
97
getSparseSetIndex__anon56c217e30111::RegAllocFast::LiveReg98 unsigned getSparseSetIndex() const {
99 return Register::virtReg2Index(VirtReg);
100 }
101 };
102
103 using LiveRegMap = SparseSet<LiveReg>;
104 /// This map contains entries for each virtual register that is currently
105 /// available in a physical register.
106 LiveRegMap LiveVirtRegs;
107
108 /// Stores assigned virtual registers present in the bundle MI.
109 DenseMap<Register, MCPhysReg> BundleVirtRegsMap;
110
111 DenseMap<unsigned, SmallVector<MachineInstr *, 2>> LiveDbgValueMap;
112 /// List of DBG_VALUE that we encountered without the vreg being assigned
113 /// because they were placed after the last use of the vreg.
114 DenseMap<unsigned, SmallVector<MachineInstr *, 1>> DanglingDbgValues;
115
116 /// Has a bit set for every virtual register for which it was determined
117 /// that it is alive across blocks.
118 BitVector MayLiveAcrossBlocks;
119
120 /// State of a register unit.
121 enum RegUnitState {
122 /// A free register is not currently in use and can be allocated
123 /// immediately without checking aliases.
124 regFree,
125
126 /// A pre-assigned register has been assigned before register allocation
127 /// (e.g., setting up a call parameter).
128 regPreAssigned,
129
130 /// Used temporarily in reloadAtBegin() to mark register units that are
131 /// live-in to the basic block.
132 regLiveIn,
133
134 /// A register state may also be a virtual register number, indication
135 /// that the physical register is currently allocated to a virtual
136 /// register. In that case, LiveVirtRegs contains the inverse mapping.
137 };
138
139 /// Maps each physical register to a RegUnitState enum or virtual register.
140 std::vector<unsigned> RegUnitStates;
141
142 SmallVector<MachineInstr *, 32> Coalesced;
143
144 using RegUnitSet = SparseSet<uint16_t, identity<uint16_t>>;
145 /// Set of register units that are used in the current instruction, and so
146 /// cannot be allocated.
147 RegUnitSet UsedInInstr;
148 RegUnitSet PhysRegUses;
149 SmallVector<uint16_t, 8> DefOperandIndexes;
150
151 void setPhysRegState(MCPhysReg PhysReg, unsigned NewState);
152 bool isPhysRegFree(MCPhysReg PhysReg) const;
153
154 /// Mark a physreg as used in this instruction.
markRegUsedInInstr(MCPhysReg PhysReg)155 void markRegUsedInInstr(MCPhysReg PhysReg) {
156 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
157 UsedInInstr.insert(*Units);
158 }
159
160 /// Check if a physreg or any of its aliases are used in this instruction.
isRegUsedInInstr(MCPhysReg PhysReg,bool LookAtPhysRegUses) const161 bool isRegUsedInInstr(MCPhysReg PhysReg, bool LookAtPhysRegUses) const {
162 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
163 if (UsedInInstr.count(*Units))
164 return true;
165 if (LookAtPhysRegUses && PhysRegUses.count(*Units))
166 return true;
167 }
168 return false;
169 }
170
171 /// Mark physical register as being used in a register use operand.
172 /// This is only used by the special livethrough handling code.
markPhysRegUsedInInstr(MCPhysReg PhysReg)173 void markPhysRegUsedInInstr(MCPhysReg PhysReg) {
174 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
175 PhysRegUses.insert(*Units);
176 }
177
178 /// Remove mark of physical register being used in the instruction.
unmarkRegUsedInInstr(MCPhysReg PhysReg)179 void unmarkRegUsedInInstr(MCPhysReg PhysReg) {
180 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
181 UsedInInstr.erase(*Units);
182 }
183
184 enum : unsigned {
185 spillClean = 50,
186 spillDirty = 100,
187 spillPrefBonus = 20,
188 spillImpossible = ~0u
189 };
190
191 public:
getPassName() const192 StringRef getPassName() const override { return "Fast Register Allocator"; }
193
getAnalysisUsage(AnalysisUsage & AU) const194 void getAnalysisUsage(AnalysisUsage &AU) const override {
195 AU.setPreservesCFG();
196 MachineFunctionPass::getAnalysisUsage(AU);
197 }
198
getRequiredProperties() const199 MachineFunctionProperties getRequiredProperties() const override {
200 return MachineFunctionProperties().set(
201 MachineFunctionProperties::Property::NoPHIs);
202 }
203
getSetProperties() const204 MachineFunctionProperties getSetProperties() const override {
205 return MachineFunctionProperties().set(
206 MachineFunctionProperties::Property::NoVRegs);
207 }
208
getClearedProperties() const209 MachineFunctionProperties getClearedProperties() const override {
210 return MachineFunctionProperties().set(
211 MachineFunctionProperties::Property::IsSSA);
212 }
213
214 private:
215 bool runOnMachineFunction(MachineFunction &MF) override;
216
217 void allocateBasicBlock(MachineBasicBlock &MBB);
218
219 void addRegClassDefCounts(std::vector<unsigned> &RegClassDefCounts,
220 Register Reg) const;
221
222 void allocateInstruction(MachineInstr &MI);
223 void handleDebugValue(MachineInstr &MI);
224 void handleBundle(MachineInstr &MI);
225
226 bool usePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
227 bool definePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
228 bool displacePhysReg(MachineInstr &MI, MCPhysReg PhysReg);
229 void freePhysReg(MCPhysReg PhysReg);
230
231 unsigned calcSpillCost(MCPhysReg PhysReg) const;
232
findLiveVirtReg(Register VirtReg)233 LiveRegMap::iterator findLiveVirtReg(Register VirtReg) {
234 return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
235 }
236
findLiveVirtReg(Register VirtReg) const237 LiveRegMap::const_iterator findLiveVirtReg(Register VirtReg) const {
238 return LiveVirtRegs.find(Register::virtReg2Index(VirtReg));
239 }
240
241 void assignVirtToPhysReg(MachineInstr &MI, LiveReg &, MCPhysReg PhysReg);
242 void allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint,
243 bool LookAtPhysRegUses = false);
244 void allocVirtRegUndef(MachineOperand &MO);
245 void assignDanglingDebugValues(MachineInstr &Def, Register VirtReg,
246 MCPhysReg Reg);
247 void defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
248 Register VirtReg);
249 void defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,
250 bool LookAtPhysRegUses = false);
251 void useVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg);
252
253 MachineBasicBlock::iterator
254 getMBBBeginInsertionPoint(MachineBasicBlock &MBB,
255 SmallSet<Register, 2> &PrologLiveIns) const;
256
257 void reloadAtBegin(MachineBasicBlock &MBB);
258 void setPhysReg(MachineInstr &MI, MachineOperand &MO, MCPhysReg PhysReg);
259
260 Register traceCopies(Register VirtReg) const;
261 Register traceCopyChain(Register Reg) const;
262
263 int getStackSpaceFor(Register VirtReg);
264 void spill(MachineBasicBlock::iterator Before, Register VirtReg,
265 MCPhysReg AssignedReg, bool Kill, bool LiveOut);
266 void reload(MachineBasicBlock::iterator Before, Register VirtReg,
267 MCPhysReg PhysReg);
268
269 bool mayLiveOut(Register VirtReg);
270 bool mayLiveIn(Register VirtReg);
271
272 void dumpState() const;
273 };
274
275 } // end anonymous namespace
276
277 char RegAllocFast::ID = 0;
278
279 INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false,
280 false)
281
setPhysRegState(MCPhysReg PhysReg,unsigned NewState)282 void RegAllocFast::setPhysRegState(MCPhysReg PhysReg, unsigned NewState) {
283 for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI)
284 RegUnitStates[*UI] = NewState;
285 }
286
isPhysRegFree(MCPhysReg PhysReg) const287 bool RegAllocFast::isPhysRegFree(MCPhysReg PhysReg) const {
288 for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
289 if (RegUnitStates[*UI] != regFree)
290 return false;
291 }
292 return true;
293 }
294
295 /// This allocates space for the specified virtual register to be held on the
296 /// stack.
getStackSpaceFor(Register VirtReg)297 int RegAllocFast::getStackSpaceFor(Register VirtReg) {
298 // Find the location Reg would belong...
299 int SS = StackSlotForVirtReg[VirtReg];
300 // Already has space allocated?
301 if (SS != -1)
302 return SS;
303
304 // Allocate a new stack object for this spill location...
305 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
306 unsigned Size = TRI->getSpillSize(RC);
307 Align Alignment = TRI->getSpillAlign(RC);
308 int FrameIdx = MFI->CreateSpillStackObject(Size, Alignment);
309
310 // Assign the slot.
311 StackSlotForVirtReg[VirtReg] = FrameIdx;
312 return FrameIdx;
313 }
314
dominates(MachineBasicBlock & MBB,MachineBasicBlock::const_iterator A,MachineBasicBlock::const_iterator B)315 static bool dominates(MachineBasicBlock &MBB,
316 MachineBasicBlock::const_iterator A,
317 MachineBasicBlock::const_iterator B) {
318 auto MBBEnd = MBB.end();
319 if (B == MBBEnd)
320 return true;
321
322 MachineBasicBlock::const_iterator I = MBB.begin();
323 for (; &*I != A && &*I != B; ++I)
324 ;
325
326 return &*I == A;
327 }
328
329 /// Returns false if \p VirtReg is known to not live out of the current block.
mayLiveOut(Register VirtReg)330 bool RegAllocFast::mayLiveOut(Register VirtReg) {
331 if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg))) {
332 // Cannot be live-out if there are no successors.
333 return !MBB->succ_empty();
334 }
335
336 const MachineInstr *SelfLoopDef = nullptr;
337
338 // If this block loops back to itself, it is necessary to check whether the
339 // use comes after the def.
340 if (MBB->isSuccessor(MBB)) {
341 SelfLoopDef = MRI->getUniqueVRegDef(VirtReg);
342 if (!SelfLoopDef) {
343 MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
344 return true;
345 }
346 }
347
348 // See if the first \p Limit uses of the register are all in the current
349 // block.
350 static const unsigned Limit = 8;
351 unsigned C = 0;
352 for (const MachineInstr &UseInst : MRI->use_nodbg_instructions(VirtReg)) {
353 if (UseInst.getParent() != MBB || ++C >= Limit) {
354 MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
355 // Cannot be live-out if there are no successors.
356 return !MBB->succ_empty();
357 }
358
359 if (SelfLoopDef) {
360 // Try to handle some simple cases to avoid spilling and reloading every
361 // value inside a self looping block.
362 if (SelfLoopDef == &UseInst ||
363 !dominates(*MBB, SelfLoopDef->getIterator(), UseInst.getIterator())) {
364 MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
365 return true;
366 }
367 }
368 }
369
370 return false;
371 }
372
373 /// Returns false if \p VirtReg is known to not be live into the current block.
mayLiveIn(Register VirtReg)374 bool RegAllocFast::mayLiveIn(Register VirtReg) {
375 if (MayLiveAcrossBlocks.test(Register::virtReg2Index(VirtReg)))
376 return !MBB->pred_empty();
377
378 // See if the first \p Limit def of the register are all in the current block.
379 static const unsigned Limit = 8;
380 unsigned C = 0;
381 for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {
382 if (DefInst.getParent() != MBB || ++C >= Limit) {
383 MayLiveAcrossBlocks.set(Register::virtReg2Index(VirtReg));
384 return !MBB->pred_empty();
385 }
386 }
387
388 return false;
389 }
390
391 /// Insert spill instruction for \p AssignedReg before \p Before. Update
392 /// DBG_VALUEs with \p VirtReg operands with the stack slot.
spill(MachineBasicBlock::iterator Before,Register VirtReg,MCPhysReg AssignedReg,bool Kill,bool LiveOut)393 void RegAllocFast::spill(MachineBasicBlock::iterator Before, Register VirtReg,
394 MCPhysReg AssignedReg, bool Kill, bool LiveOut) {
395 LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI)
396 << " in " << printReg(AssignedReg, TRI));
397 int FI = getStackSpaceFor(VirtReg);
398 LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n');
399
400 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
401 TII->storeRegToStackSlot(*MBB, Before, AssignedReg, Kill, FI, &RC, TRI);
402 ++NumStores;
403
404 MachineBasicBlock::iterator FirstTerm = MBB->getFirstTerminator();
405
406 // When we spill a virtual register, we will have spill instructions behind
407 // every definition of it, meaning we can switch all the DBG_VALUEs over
408 // to just reference the stack slot.
409 SmallVectorImpl<MachineInstr *> &LRIDbgValues = LiveDbgValueMap[VirtReg];
410 for (MachineInstr *DBG : LRIDbgValues) {
411 MachineInstr *NewDV = buildDbgValueForSpill(*MBB, Before, *DBG, FI);
412 assert(NewDV->getParent() == MBB && "dangling parent pointer");
413 (void)NewDV;
414 LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);
415
416 if (LiveOut) {
417 // We need to insert a DBG_VALUE at the end of the block if the spill slot
418 // is live out, but there is another use of the value after the
419 // spill. This will allow LiveDebugValues to see the correct live out
420 // value to propagate to the successors.
421 MachineInstr *ClonedDV = MBB->getParent()->CloneMachineInstr(NewDV);
422 MBB->insert(FirstTerm, ClonedDV);
423 LLVM_DEBUG(dbgs() << "Cloning debug info due to live out spill\n");
424 }
425
426 // Rewrite unassigned dbg_values to use the stack slot.
427 MachineOperand &MO = DBG->getOperand(0);
428 if (MO.isReg() && MO.getReg() == 0)
429 updateDbgValueForSpill(*DBG, FI);
430 }
431 // Now this register is spilled there is should not be any DBG_VALUE
432 // pointing to this register because they are all pointing to spilled value
433 // now.
434 LRIDbgValues.clear();
435 }
436
437 /// Insert reload instruction for \p PhysReg before \p Before.
reload(MachineBasicBlock::iterator Before,Register VirtReg,MCPhysReg PhysReg)438 void RegAllocFast::reload(MachineBasicBlock::iterator Before, Register VirtReg,
439 MCPhysReg PhysReg) {
440 LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
441 << printReg(PhysReg, TRI) << '\n');
442 int FI = getStackSpaceFor(VirtReg);
443 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
444 TII->loadRegFromStackSlot(*MBB, Before, PhysReg, FI, &RC, TRI);
445 ++NumLoads;
446 }
447
448 /// Get basic block begin insertion point.
449 /// This is not just MBB.begin() because surprisingly we have EH_LABEL
450 /// instructions marking the begin of a basic block. This means we must insert
451 /// new instructions after such labels...
452 MachineBasicBlock::iterator
getMBBBeginInsertionPoint(MachineBasicBlock & MBB,SmallSet<Register,2> & PrologLiveIns) const453 RegAllocFast::getMBBBeginInsertionPoint(
454 MachineBasicBlock &MBB, SmallSet<Register, 2> &PrologLiveIns) const {
455 MachineBasicBlock::iterator I = MBB.begin();
456 while (I != MBB.end()) {
457 if (I->isLabel()) {
458 ++I;
459 continue;
460 }
461
462 // Most reloads should be inserted after prolog instructions.
463 if (!TII->isBasicBlockPrologue(*I))
464 break;
465
466 // However if a prolog instruction reads a register that needs to be
467 // reloaded, the reload should be inserted before the prolog.
468 for (MachineOperand &MO : I->operands()) {
469 if (MO.isReg())
470 PrologLiveIns.insert(MO.getReg());
471 }
472
473 ++I;
474 }
475
476 return I;
477 }
478
479 /// Reload all currently assigned virtual registers.
reloadAtBegin(MachineBasicBlock & MBB)480 void RegAllocFast::reloadAtBegin(MachineBasicBlock &MBB) {
481 if (LiveVirtRegs.empty())
482 return;
483
484 for (MachineBasicBlock::RegisterMaskPair P : MBB.liveins()) {
485 MCPhysReg Reg = P.PhysReg;
486 // Set state to live-in. This possibly overrides mappings to virtual
487 // registers but we don't care anymore at this point.
488 setPhysRegState(Reg, regLiveIn);
489 }
490
491
492 SmallSet<Register, 2> PrologLiveIns;
493
494 // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
495 // of spilling here is deterministic, if arbitrary.
496 MachineBasicBlock::iterator InsertBefore
497 = getMBBBeginInsertionPoint(MBB, PrologLiveIns);
498 for (const LiveReg &LR : LiveVirtRegs) {
499 MCPhysReg PhysReg = LR.PhysReg;
500 if (PhysReg == 0)
501 continue;
502
503 MCRegister FirstUnit = *MCRegUnitIterator(PhysReg, TRI);
504 if (RegUnitStates[FirstUnit] == regLiveIn)
505 continue;
506
507 assert((&MBB != &MBB.getParent()->front() || IgnoreMissingDefs) &&
508 "no reload in start block. Missing vreg def?");
509
510 if (PrologLiveIns.count(PhysReg)) {
511 // FIXME: Theoretically this should use an insert point skipping labels
512 // but I'm not sure how labels should interact with prolog instruction
513 // that need reloads.
514 reload(MBB.begin(), LR.VirtReg, PhysReg);
515 } else
516 reload(InsertBefore, LR.VirtReg, PhysReg);
517 }
518 LiveVirtRegs.clear();
519 }
520
521 /// Handle the direct use of a physical register. Check that the register is
522 /// not used by a virtreg. Kill the physreg, marking it free. This may add
523 /// implicit kills to MO->getParent() and invalidate MO.
usePhysReg(MachineInstr & MI,MCPhysReg Reg)524 bool RegAllocFast::usePhysReg(MachineInstr &MI, MCPhysReg Reg) {
525 assert(Register::isPhysicalRegister(Reg) && "expected physreg");
526 bool displacedAny = displacePhysReg(MI, Reg);
527 setPhysRegState(Reg, regPreAssigned);
528 markRegUsedInInstr(Reg);
529 return displacedAny;
530 }
531
definePhysReg(MachineInstr & MI,MCPhysReg Reg)532 bool RegAllocFast::definePhysReg(MachineInstr &MI, MCPhysReg Reg) {
533 bool displacedAny = displacePhysReg(MI, Reg);
534 setPhysRegState(Reg, regPreAssigned);
535 return displacedAny;
536 }
537
538 /// Mark PhysReg as reserved or free after spilling any virtregs. This is very
539 /// similar to defineVirtReg except the physreg is reserved instead of
540 /// allocated.
displacePhysReg(MachineInstr & MI,MCPhysReg PhysReg)541 bool RegAllocFast::displacePhysReg(MachineInstr &MI, MCPhysReg PhysReg) {
542 bool displacedAny = false;
543
544 for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
545 unsigned Unit = *UI;
546 switch (unsigned VirtReg = RegUnitStates[Unit]) {
547 default: {
548 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
549 assert(LRI != LiveVirtRegs.end() && "datastructures in sync");
550 MachineBasicBlock::iterator ReloadBefore =
551 std::next((MachineBasicBlock::iterator)MI.getIterator());
552 reload(ReloadBefore, VirtReg, LRI->PhysReg);
553
554 setPhysRegState(LRI->PhysReg, regFree);
555 LRI->PhysReg = 0;
556 LRI->Reloaded = true;
557 displacedAny = true;
558 break;
559 }
560 case regPreAssigned:
561 RegUnitStates[Unit] = regFree;
562 displacedAny = true;
563 break;
564 case regFree:
565 break;
566 }
567 }
568 return displacedAny;
569 }
570
freePhysReg(MCPhysReg PhysReg)571 void RegAllocFast::freePhysReg(MCPhysReg PhysReg) {
572 LLVM_DEBUG(dbgs() << "Freeing " << printReg(PhysReg, TRI) << ':');
573
574 MCRegister FirstUnit = *MCRegUnitIterator(PhysReg, TRI);
575 switch (unsigned VirtReg = RegUnitStates[FirstUnit]) {
576 case regFree:
577 LLVM_DEBUG(dbgs() << '\n');
578 return;
579 case regPreAssigned:
580 LLVM_DEBUG(dbgs() << '\n');
581 setPhysRegState(PhysReg, regFree);
582 return;
583 default: {
584 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
585 assert(LRI != LiveVirtRegs.end());
586 LLVM_DEBUG(dbgs() << ' ' << printReg(LRI->VirtReg, TRI) << '\n');
587 setPhysRegState(LRI->PhysReg, regFree);
588 LRI->PhysReg = 0;
589 }
590 return;
591 }
592 }
593
594 /// Return the cost of spilling clearing out PhysReg and aliases so it is free
595 /// for allocation. Returns 0 when PhysReg is free or disabled with all aliases
596 /// disabled - it can be allocated directly.
597 /// \returns spillImpossible when PhysReg or an alias can't be spilled.
calcSpillCost(MCPhysReg PhysReg) const598 unsigned RegAllocFast::calcSpillCost(MCPhysReg PhysReg) const {
599 for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
600 switch (unsigned VirtReg = RegUnitStates[*UI]) {
601 case regFree:
602 break;
603 case regPreAssigned:
604 LLVM_DEBUG(dbgs() << "Cannot spill pre-assigned "
605 << printReg(PhysReg, TRI) << '\n');
606 return spillImpossible;
607 default: {
608 bool SureSpill = StackSlotForVirtReg[VirtReg] != -1 ||
609 findLiveVirtReg(VirtReg)->LiveOut;
610 return SureSpill ? spillClean : spillDirty;
611 }
612 }
613 }
614 return 0;
615 }
616
assignDanglingDebugValues(MachineInstr & Definition,Register VirtReg,MCPhysReg Reg)617 void RegAllocFast::assignDanglingDebugValues(MachineInstr &Definition,
618 Register VirtReg, MCPhysReg Reg) {
619 auto UDBGValIter = DanglingDbgValues.find(VirtReg);
620 if (UDBGValIter == DanglingDbgValues.end())
621 return;
622
623 SmallVectorImpl<MachineInstr*> &Dangling = UDBGValIter->second;
624 for (MachineInstr *DbgValue : Dangling) {
625 assert(DbgValue->isDebugValue());
626 MachineOperand &MO = DbgValue->getOperand(0);
627 if (!MO.isReg())
628 continue;
629
630 // Test whether the physreg survives from the definition to the DBG_VALUE.
631 MCPhysReg SetToReg = Reg;
632 unsigned Limit = 20;
633 for (MachineBasicBlock::iterator I = std::next(Definition.getIterator()),
634 E = DbgValue->getIterator(); I != E; ++I) {
635 if (I->modifiesRegister(Reg, TRI) || --Limit == 0) {
636 LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue
637 << '\n');
638 SetToReg = 0;
639 break;
640 }
641 }
642 MO.setReg(SetToReg);
643 if (SetToReg != 0)
644 MO.setIsRenamable();
645 }
646 Dangling.clear();
647 }
648
649 /// This method updates local state so that we know that PhysReg is the
650 /// proper container for VirtReg now. The physical register must not be used
651 /// for anything else when this is called.
assignVirtToPhysReg(MachineInstr & AtMI,LiveReg & LR,MCPhysReg PhysReg)652 void RegAllocFast::assignVirtToPhysReg(MachineInstr &AtMI, LiveReg &LR,
653 MCPhysReg PhysReg) {
654 Register VirtReg = LR.VirtReg;
655 LLVM_DEBUG(dbgs() << "Assigning " << printReg(VirtReg, TRI) << " to "
656 << printReg(PhysReg, TRI) << '\n');
657 assert(LR.PhysReg == 0 && "Already assigned a physreg");
658 assert(PhysReg != 0 && "Trying to assign no register");
659 LR.PhysReg = PhysReg;
660 setPhysRegState(PhysReg, VirtReg);
661
662 assignDanglingDebugValues(AtMI, VirtReg, PhysReg);
663 }
664
isCoalescable(const MachineInstr & MI)665 static bool isCoalescable(const MachineInstr &MI) {
666 return MI.isFullCopy();
667 }
668
traceCopyChain(Register Reg) const669 Register RegAllocFast::traceCopyChain(Register Reg) const {
670 static const unsigned ChainLengthLimit = 3;
671 unsigned C = 0;
672 do {
673 if (Reg.isPhysical())
674 return Reg;
675 assert(Reg.isVirtual());
676
677 MachineInstr *VRegDef = MRI->getUniqueVRegDef(Reg);
678 if (!VRegDef || !isCoalescable(*VRegDef))
679 return 0;
680 Reg = VRegDef->getOperand(1).getReg();
681 } while (++C <= ChainLengthLimit);
682 return 0;
683 }
684
685 /// Check if any of \p VirtReg's definitions is a copy. If it is follow the
686 /// chain of copies to check whether we reach a physical register we can
687 /// coalesce with.
traceCopies(Register VirtReg) const688 Register RegAllocFast::traceCopies(Register VirtReg) const {
689 static const unsigned DefLimit = 3;
690 unsigned C = 0;
691 for (const MachineInstr &MI : MRI->def_instructions(VirtReg)) {
692 if (isCoalescable(MI)) {
693 Register Reg = MI.getOperand(1).getReg();
694 Reg = traceCopyChain(Reg);
695 if (Reg.isValid())
696 return Reg;
697 }
698
699 if (++C >= DefLimit)
700 break;
701 }
702 return Register();
703 }
704
705 /// Allocates a physical register for VirtReg.
allocVirtReg(MachineInstr & MI,LiveReg & LR,Register Hint0,bool LookAtPhysRegUses)706 void RegAllocFast::allocVirtReg(MachineInstr &MI, LiveReg &LR,
707 Register Hint0, bool LookAtPhysRegUses) {
708 const Register VirtReg = LR.VirtReg;
709 assert(LR.PhysReg == 0);
710
711 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
712 LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg)
713 << " in class " << TRI->getRegClassName(&RC)
714 << " with hint " << printReg(Hint0, TRI) << '\n');
715
716 // Take hint when possible.
717 if (Hint0.isPhysical() && MRI->isAllocatable(Hint0) && RC.contains(Hint0) &&
718 !isRegUsedInInstr(Hint0, LookAtPhysRegUses)) {
719 // Take hint if the register is currently free.
720 if (isPhysRegFree(Hint0)) {
721 LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
722 << '\n');
723 assignVirtToPhysReg(MI, LR, Hint0);
724 return;
725 } else {
726 LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint0, TRI)
727 << " occupied\n");
728 }
729 } else {
730 Hint0 = Register();
731 }
732
733
734 // Try other hint.
735 Register Hint1 = traceCopies(VirtReg);
736 if (Hint1.isPhysical() && MRI->isAllocatable(Hint1) && RC.contains(Hint1) &&
737 !isRegUsedInInstr(Hint1, LookAtPhysRegUses)) {
738 // Take hint if the register is currently free.
739 if (isPhysRegFree(Hint1)) {
740 LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
741 << '\n');
742 assignVirtToPhysReg(MI, LR, Hint1);
743 return;
744 } else {
745 LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint1, TRI)
746 << " occupied\n");
747 }
748 } else {
749 Hint1 = Register();
750 }
751
752 MCPhysReg BestReg = 0;
753 unsigned BestCost = spillImpossible;
754 ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
755 for (MCPhysReg PhysReg : AllocationOrder) {
756 LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << ' ');
757 if (isRegUsedInInstr(PhysReg, LookAtPhysRegUses)) {
758 LLVM_DEBUG(dbgs() << "already used in instr.\n");
759 continue;
760 }
761
762 unsigned Cost = calcSpillCost(PhysReg);
763 LLVM_DEBUG(dbgs() << "Cost: " << Cost << " BestCost: " << BestCost << '\n');
764 // Immediate take a register with cost 0.
765 if (Cost == 0) {
766 assignVirtToPhysReg(MI, LR, PhysReg);
767 return;
768 }
769
770 if (PhysReg == Hint0 || PhysReg == Hint1)
771 Cost -= spillPrefBonus;
772
773 if (Cost < BestCost) {
774 BestReg = PhysReg;
775 BestCost = Cost;
776 }
777 }
778
779 if (!BestReg) {
780 // Nothing we can do: Report an error and keep going with an invalid
781 // allocation.
782 if (MI.isInlineAsm())
783 MI.emitError("inline assembly requires more registers than available");
784 else
785 MI.emitError("ran out of registers during register allocation");
786
787 LR.Error = true;
788 LR.PhysReg = 0;
789 return;
790 }
791
792 displacePhysReg(MI, BestReg);
793 assignVirtToPhysReg(MI, LR, BestReg);
794 }
795
allocVirtRegUndef(MachineOperand & MO)796 void RegAllocFast::allocVirtRegUndef(MachineOperand &MO) {
797 assert(MO.isUndef() && "expected undef use");
798 Register VirtReg = MO.getReg();
799 assert(Register::isVirtualRegister(VirtReg) && "Expected virtreg");
800
801 LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
802 MCPhysReg PhysReg;
803 if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
804 PhysReg = LRI->PhysReg;
805 } else {
806 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
807 ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
808 assert(!AllocationOrder.empty() && "Allocation order must not be empty");
809 PhysReg = AllocationOrder[0];
810 }
811
812 unsigned SubRegIdx = MO.getSubReg();
813 if (SubRegIdx != 0) {
814 PhysReg = TRI->getSubReg(PhysReg, SubRegIdx);
815 MO.setSubReg(0);
816 }
817 MO.setReg(PhysReg);
818 MO.setIsRenamable(true);
819 }
820
821 /// Variation of defineVirtReg() with special handling for livethrough regs
822 /// (tied or earlyclobber) that may interfere with preassigned uses.
defineLiveThroughVirtReg(MachineInstr & MI,unsigned OpNum,Register VirtReg)823 void RegAllocFast::defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
824 Register VirtReg) {
825 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
826 if (LRI != LiveVirtRegs.end()) {
827 MCPhysReg PrevReg = LRI->PhysReg;
828 if (PrevReg != 0 && isRegUsedInInstr(PrevReg, true)) {
829 LLVM_DEBUG(dbgs() << "Need new assignment for " << printReg(PrevReg, TRI)
830 << " (tied/earlyclobber resolution)\n");
831 freePhysReg(PrevReg);
832 LRI->PhysReg = 0;
833 allocVirtReg(MI, *LRI, 0, true);
834 MachineBasicBlock::iterator InsertBefore =
835 std::next((MachineBasicBlock::iterator)MI.getIterator());
836 LLVM_DEBUG(dbgs() << "Copy " << printReg(LRI->PhysReg, TRI) << " to "
837 << printReg(PrevReg, TRI) << '\n');
838 BuildMI(*MBB, InsertBefore, MI.getDebugLoc(),
839 TII->get(TargetOpcode::COPY), PrevReg)
840 .addReg(LRI->PhysReg, llvm::RegState::Kill);
841 }
842 MachineOperand &MO = MI.getOperand(OpNum);
843 if (MO.getSubReg() && !MO.isUndef()) {
844 LRI->LastUse = &MI;
845 }
846 }
847 return defineVirtReg(MI, OpNum, VirtReg, true);
848 }
849
850 /// Allocates a register for VirtReg definition. Typically the register is
851 /// already assigned from a use of the virtreg, however we still need to
852 /// perform an allocation if:
853 /// - It is a dead definition without any uses.
854 /// - The value is live out and all uses are in different basic blocks.
defineVirtReg(MachineInstr & MI,unsigned OpNum,Register VirtReg,bool LookAtPhysRegUses)855 void RegAllocFast::defineVirtReg(MachineInstr &MI, unsigned OpNum,
856 Register VirtReg, bool LookAtPhysRegUses) {
857 assert(VirtReg.isVirtual() && "Not a virtual register");
858 MachineOperand &MO = MI.getOperand(OpNum);
859 LiveRegMap::iterator LRI;
860 bool New;
861 std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
862 if (New) {
863 if (!MO.isDead()) {
864 if (mayLiveOut(VirtReg)) {
865 LRI->LiveOut = true;
866 } else {
867 // It is a dead def without the dead flag; add the flag now.
868 MO.setIsDead(true);
869 }
870 }
871 }
872 if (LRI->PhysReg == 0)
873 allocVirtReg(MI, *LRI, 0, LookAtPhysRegUses);
874 else {
875 assert(!isRegUsedInInstr(LRI->PhysReg, LookAtPhysRegUses) &&
876 "TODO: preassign mismatch");
877 LLVM_DEBUG(dbgs() << "In def of " << printReg(VirtReg, TRI)
878 << " use existing assignment to "
879 << printReg(LRI->PhysReg, TRI) << '\n');
880 }
881
882 MCPhysReg PhysReg = LRI->PhysReg;
883 assert(PhysReg != 0 && "Register not assigned");
884 if (LRI->Reloaded || LRI->LiveOut) {
885 if (!MI.isImplicitDef()) {
886 MachineBasicBlock::iterator SpillBefore =
887 std::next((MachineBasicBlock::iterator)MI.getIterator());
888 LLVM_DEBUG(dbgs() << "Spill Reason: LO: " << LRI->LiveOut << " RL: "
889 << LRI->Reloaded << '\n');
890 bool Kill = LRI->LastUse == nullptr;
891 spill(SpillBefore, VirtReg, PhysReg, Kill, LRI->LiveOut);
892 LRI->LastUse = nullptr;
893 }
894 LRI->LiveOut = false;
895 LRI->Reloaded = false;
896 }
897 if (MI.getOpcode() == TargetOpcode::BUNDLE) {
898 BundleVirtRegsMap[VirtReg] = PhysReg;
899 }
900 markRegUsedInInstr(PhysReg);
901 setPhysReg(MI, MO, PhysReg);
902 }
903
904 /// Allocates a register for a VirtReg use.
useVirtReg(MachineInstr & MI,unsigned OpNum,Register VirtReg)905 void RegAllocFast::useVirtReg(MachineInstr &MI, unsigned OpNum,
906 Register VirtReg) {
907 assert(VirtReg.isVirtual() && "Not a virtual register");
908 MachineOperand &MO = MI.getOperand(OpNum);
909 LiveRegMap::iterator LRI;
910 bool New;
911 std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
912 if (New) {
913 MachineOperand &MO = MI.getOperand(OpNum);
914 if (!MO.isKill()) {
915 if (mayLiveOut(VirtReg)) {
916 LRI->LiveOut = true;
917 } else {
918 // It is a last (killing) use without the kill flag; add the flag now.
919 MO.setIsKill(true);
920 }
921 }
922 } else {
923 assert((!MO.isKill() || LRI->LastUse == &MI) && "Invalid kill flag");
924 }
925
926 // If necessary allocate a register.
927 if (LRI->PhysReg == 0) {
928 assert(!MO.isTied() && "tied op should be allocated");
929 Register Hint;
930 if (MI.isCopy() && MI.getOperand(1).getSubReg() == 0) {
931 Hint = MI.getOperand(0).getReg();
932 assert(Hint.isPhysical() &&
933 "Copy destination should already be assigned");
934 }
935 allocVirtReg(MI, *LRI, Hint, false);
936 if (LRI->Error) {
937 const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
938 ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
939 setPhysReg(MI, MO, *AllocationOrder.begin());
940 return;
941 }
942 }
943
944 LRI->LastUse = &MI;
945
946 if (MI.getOpcode() == TargetOpcode::BUNDLE) {
947 BundleVirtRegsMap[VirtReg] = LRI->PhysReg;
948 }
949 markRegUsedInInstr(LRI->PhysReg);
950 setPhysReg(MI, MO, LRI->PhysReg);
951 }
952
953 /// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This
954 /// may invalidate any operand pointers. Return true if the operand kills its
955 /// register.
setPhysReg(MachineInstr & MI,MachineOperand & MO,MCPhysReg PhysReg)956 void RegAllocFast::setPhysReg(MachineInstr &MI, MachineOperand &MO,
957 MCPhysReg PhysReg) {
958 if (!MO.getSubReg()) {
959 MO.setReg(PhysReg);
960 MO.setIsRenamable(true);
961 return;
962 }
963
964 // Handle subregister index.
965 MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : MCRegister());
966 MO.setIsRenamable(true);
967 // Note: We leave the subreg number around a little longer in case of defs.
968 // This is so that the register freeing logic in allocateInstruction can still
969 // recognize this as subregister defs. The code there will clear the number.
970 if (!MO.isDef())
971 MO.setSubReg(0);
972
973 // A kill flag implies killing the full register. Add corresponding super
974 // register kill.
975 if (MO.isKill()) {
976 MI.addRegisterKilled(PhysReg, TRI, true);
977 return;
978 }
979
980 // A <def,read-undef> of a sub-register requires an implicit def of the full
981 // register.
982 if (MO.isDef() && MO.isUndef()) {
983 if (MO.isDead())
984 MI.addRegisterDead(PhysReg, TRI, true);
985 else
986 MI.addRegisterDefined(PhysReg, TRI);
987 }
988 }
989
990 #ifndef NDEBUG
991
dumpState() const992 void RegAllocFast::dumpState() const {
993 for (unsigned Unit = 1, UnitE = TRI->getNumRegUnits(); Unit != UnitE;
994 ++Unit) {
995 switch (unsigned VirtReg = RegUnitStates[Unit]) {
996 case regFree:
997 break;
998 case regPreAssigned:
999 dbgs() << " " << printRegUnit(Unit, TRI) << "[P]";
1000 break;
1001 case regLiveIn:
1002 llvm_unreachable("Should not have regLiveIn in map");
1003 default: {
1004 dbgs() << ' ' << printRegUnit(Unit, TRI) << '=' << printReg(VirtReg);
1005 LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
1006 assert(I != LiveVirtRegs.end() && "have LiveVirtRegs entry");
1007 if (I->LiveOut || I->Reloaded) {
1008 dbgs() << '[';
1009 if (I->LiveOut) dbgs() << 'O';
1010 if (I->Reloaded) dbgs() << 'R';
1011 dbgs() << ']';
1012 }
1013 assert(TRI->hasRegUnit(I->PhysReg, Unit) && "inverse mapping present");
1014 break;
1015 }
1016 }
1017 }
1018 dbgs() << '\n';
1019 // Check that LiveVirtRegs is the inverse.
1020 for (const LiveReg &LR : LiveVirtRegs) {
1021 Register VirtReg = LR.VirtReg;
1022 assert(VirtReg.isVirtual() && "Bad map key");
1023 MCPhysReg PhysReg = LR.PhysReg;
1024 if (PhysReg != 0) {
1025 assert(Register::isPhysicalRegister(PhysReg) &&
1026 "mapped to physreg");
1027 for (MCRegUnitIterator UI(PhysReg, TRI); UI.isValid(); ++UI) {
1028 assert(RegUnitStates[*UI] == VirtReg && "inverse map valid");
1029 }
1030 }
1031 }
1032 }
1033 #endif
1034
1035 /// Count number of defs consumed from each register class by \p Reg
addRegClassDefCounts(std::vector<unsigned> & RegClassDefCounts,Register Reg) const1036 void RegAllocFast::addRegClassDefCounts(std::vector<unsigned> &RegClassDefCounts,
1037 Register Reg) const {
1038 assert(RegClassDefCounts.size() == TRI->getNumRegClasses());
1039
1040 if (Reg.isVirtual()) {
1041 const TargetRegisterClass *OpRC = MRI->getRegClass(Reg);
1042 for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();
1043 RCIdx != RCIdxEnd; ++RCIdx) {
1044 const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx);
1045 // FIXME: Consider aliasing sub/super registers.
1046 if (OpRC->hasSubClassEq(IdxRC))
1047 ++RegClassDefCounts[RCIdx];
1048 }
1049
1050 return;
1051 }
1052
1053 for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();
1054 RCIdx != RCIdxEnd; ++RCIdx) {
1055 const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx);
1056 for (MCRegAliasIterator Alias(Reg, TRI, true); Alias.isValid(); ++Alias) {
1057 if (IdxRC->contains(*Alias)) {
1058 ++RegClassDefCounts[RCIdx];
1059 break;
1060 }
1061 }
1062 }
1063 }
1064
allocateInstruction(MachineInstr & MI)1065 void RegAllocFast::allocateInstruction(MachineInstr &MI) {
1066 // The basic algorithm here is:
1067 // 1. Mark registers of def operands as free
1068 // 2. Allocate registers to use operands and place reload instructions for
1069 // registers displaced by the allocation.
1070 //
1071 // However we need to handle some corner cases:
1072 // - pre-assigned defs and uses need to be handled before the other def/use
1073 // operands are processed to avoid the allocation heuristics clashing with
1074 // the pre-assignment.
1075 // - The "free def operands" step has to come last instead of first for tied
1076 // operands and early-clobbers.
1077
1078 UsedInInstr.clear();
1079 BundleVirtRegsMap.clear();
1080
1081 // Scan for special cases; Apply pre-assigned register defs to state.
1082 bool HasPhysRegUse = false;
1083 bool HasRegMask = false;
1084 bool HasVRegDef = false;
1085 bool HasDef = false;
1086 bool HasEarlyClobber = false;
1087 bool NeedToAssignLiveThroughs = false;
1088 for (MachineOperand &MO : MI.operands()) {
1089 if (MO.isReg()) {
1090 Register Reg = MO.getReg();
1091 if (Reg.isVirtual()) {
1092 if (MO.isDef()) {
1093 HasDef = true;
1094 HasVRegDef = true;
1095 if (MO.isEarlyClobber()) {
1096 HasEarlyClobber = true;
1097 NeedToAssignLiveThroughs = true;
1098 }
1099 if (MO.isTied() || (MO.getSubReg() != 0 && !MO.isUndef()))
1100 NeedToAssignLiveThroughs = true;
1101 }
1102 } else if (Reg.isPhysical()) {
1103 if (!MRI->isReserved(Reg)) {
1104 if (MO.isDef()) {
1105 HasDef = true;
1106 bool displacedAny = definePhysReg(MI, Reg);
1107 if (MO.isEarlyClobber())
1108 HasEarlyClobber = true;
1109 if (!displacedAny)
1110 MO.setIsDead(true);
1111 }
1112 if (MO.readsReg())
1113 HasPhysRegUse = true;
1114 }
1115 }
1116 } else if (MO.isRegMask()) {
1117 HasRegMask = true;
1118 }
1119 }
1120
1121 // Allocate virtreg defs.
1122 if (HasDef) {
1123 if (HasVRegDef) {
1124 // Special handling for early clobbers, tied operands or subregister defs:
1125 // Compared to "normal" defs these:
1126 // - Must not use a register that is pre-assigned for a use operand.
1127 // - In order to solve tricky inline assembly constraints we change the
1128 // heuristic to figure out a good operand order before doing
1129 // assignments.
1130 if (NeedToAssignLiveThroughs) {
1131 DefOperandIndexes.clear();
1132 PhysRegUses.clear();
1133
1134 // Track number of defs which may consume a register from the class.
1135 std::vector<unsigned> RegClassDefCounts(TRI->getNumRegClasses(), 0);
1136 assert(RegClassDefCounts[0] == 0);
1137
1138 LLVM_DEBUG(dbgs() << "Need to assign livethroughs\n");
1139 for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {
1140 const MachineOperand &MO = MI.getOperand(I);
1141 if (!MO.isReg())
1142 continue;
1143 Register Reg = MO.getReg();
1144 if (MO.readsReg()) {
1145 if (Reg.isPhysical()) {
1146 LLVM_DEBUG(dbgs() << "mark extra used: " << printReg(Reg, TRI)
1147 << '\n');
1148 markPhysRegUsedInInstr(Reg);
1149 }
1150 }
1151
1152 if (MO.isDef()) {
1153 if (Reg.isVirtual())
1154 DefOperandIndexes.push_back(I);
1155
1156 addRegClassDefCounts(RegClassDefCounts, Reg);
1157 }
1158 }
1159
1160 llvm::sort(DefOperandIndexes, [&](uint16_t I0, uint16_t I1) {
1161 const MachineOperand &MO0 = MI.getOperand(I0);
1162 const MachineOperand &MO1 = MI.getOperand(I1);
1163 Register Reg0 = MO0.getReg();
1164 Register Reg1 = MO1.getReg();
1165 const TargetRegisterClass &RC0 = *MRI->getRegClass(Reg0);
1166 const TargetRegisterClass &RC1 = *MRI->getRegClass(Reg1);
1167
1168 // Identify regclass that are easy to use up completely just in this
1169 // instruction.
1170 unsigned ClassSize0 = RegClassInfo.getOrder(&RC0).size();
1171 unsigned ClassSize1 = RegClassInfo.getOrder(&RC1).size();
1172
1173 bool SmallClass0 = ClassSize0 < RegClassDefCounts[RC0.getID()];
1174 bool SmallClass1 = ClassSize1 < RegClassDefCounts[RC1.getID()];
1175 if (SmallClass0 > SmallClass1)
1176 return true;
1177 if (SmallClass0 < SmallClass1)
1178 return false;
1179
1180 // Allocate early clobbers and livethrough operands first.
1181 bool Livethrough0 = MO0.isEarlyClobber() || MO0.isTied() ||
1182 (MO0.getSubReg() == 0 && !MO0.isUndef());
1183 bool Livethrough1 = MO1.isEarlyClobber() || MO1.isTied() ||
1184 (MO1.getSubReg() == 0 && !MO1.isUndef());
1185 if (Livethrough0 > Livethrough1)
1186 return true;
1187 if (Livethrough0 < Livethrough1)
1188 return false;
1189
1190 // Tie-break rule: operand index.
1191 return I0 < I1;
1192 });
1193
1194 for (uint16_t OpIdx : DefOperandIndexes) {
1195 MachineOperand &MO = MI.getOperand(OpIdx);
1196 LLVM_DEBUG(dbgs() << "Allocating " << MO << '\n');
1197 unsigned Reg = MO.getReg();
1198 if (MO.isEarlyClobber() || MO.isTied() ||
1199 (MO.getSubReg() && !MO.isUndef())) {
1200 defineLiveThroughVirtReg(MI, OpIdx, Reg);
1201 } else {
1202 defineVirtReg(MI, OpIdx, Reg);
1203 }
1204 }
1205 } else {
1206 // Assign virtual register defs.
1207 for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {
1208 MachineOperand &MO = MI.getOperand(I);
1209 if (!MO.isReg() || !MO.isDef())
1210 continue;
1211 Register Reg = MO.getReg();
1212 if (Reg.isVirtual())
1213 defineVirtReg(MI, I, Reg);
1214 }
1215 }
1216 }
1217
1218 // Free registers occupied by defs.
1219 // Iterate operands in reverse order, so we see the implicit super register
1220 // defs first (we added them earlier in case of <def,read-undef>).
1221 for (unsigned I = MI.getNumOperands(); I-- > 0;) {
1222 MachineOperand &MO = MI.getOperand(I);
1223 if (!MO.isReg() || !MO.isDef())
1224 continue;
1225
1226 // subreg defs don't free the full register. We left the subreg number
1227 // around as a marker in setPhysReg() to recognize this case here.
1228 if (MO.getSubReg() != 0) {
1229 MO.setSubReg(0);
1230 continue;
1231 }
1232
1233 // Do not free tied operands and early clobbers.
1234 if (MO.isTied() || MO.isEarlyClobber())
1235 continue;
1236 Register Reg = MO.getReg();
1237 if (!Reg)
1238 continue;
1239 assert(Reg.isPhysical());
1240 if (MRI->isReserved(Reg))
1241 continue;
1242 freePhysReg(Reg);
1243 unmarkRegUsedInInstr(Reg);
1244 }
1245 }
1246
1247 // Displace clobbered registers.
1248 if (HasRegMask) {
1249 for (const MachineOperand &MO : MI.operands()) {
1250 if (MO.isRegMask()) {
1251 // MRI bookkeeping.
1252 MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
1253
1254 // Displace clobbered registers.
1255 const uint32_t *Mask = MO.getRegMask();
1256 for (LiveRegMap::iterator LRI = LiveVirtRegs.begin(),
1257 LRIE = LiveVirtRegs.end(); LRI != LRIE; ++LRI) {
1258 MCPhysReg PhysReg = LRI->PhysReg;
1259 if (PhysReg != 0 && MachineOperand::clobbersPhysReg(Mask, PhysReg))
1260 displacePhysReg(MI, PhysReg);
1261 }
1262 }
1263 }
1264 }
1265
1266 // Apply pre-assigned register uses to state.
1267 if (HasPhysRegUse) {
1268 for (MachineOperand &MO : MI.operands()) {
1269 if (!MO.isReg() || !MO.readsReg())
1270 continue;
1271 Register Reg = MO.getReg();
1272 if (!Reg.isPhysical())
1273 continue;
1274 if (MRI->isReserved(Reg))
1275 continue;
1276 bool displacedAny = usePhysReg(MI, Reg);
1277 if (!displacedAny && !MRI->isReserved(Reg))
1278 MO.setIsKill(true);
1279 }
1280 }
1281
1282 // Allocate virtreg uses and insert reloads as necessary.
1283 bool HasUndefUse = false;
1284 for (unsigned I = 0; I < MI.getNumOperands(); ++I) {
1285 MachineOperand &MO = MI.getOperand(I);
1286 if (!MO.isReg() || !MO.isUse())
1287 continue;
1288 Register Reg = MO.getReg();
1289 if (!Reg.isVirtual())
1290 continue;
1291
1292 if (MO.isUndef()) {
1293 HasUndefUse = true;
1294 continue;
1295 }
1296
1297
1298 // Populate MayLiveAcrossBlocks in case the use block is allocated before
1299 // the def block (removing the vreg uses).
1300 mayLiveIn(Reg);
1301
1302
1303 assert(!MO.isInternalRead() && "Bundles not supported");
1304 assert(MO.readsReg() && "reading use");
1305 useVirtReg(MI, I, Reg);
1306 }
1307
1308 // Allocate undef operands. This is a separate step because in a situation
1309 // like ` = OP undef %X, %X` both operands need the same register assign
1310 // so we should perform the normal assignment first.
1311 if (HasUndefUse) {
1312 for (MachineOperand &MO : MI.uses()) {
1313 if (!MO.isReg() || !MO.isUse())
1314 continue;
1315 Register Reg = MO.getReg();
1316 if (!Reg.isVirtual())
1317 continue;
1318
1319 assert(MO.isUndef() && "Should only have undef virtreg uses left");
1320 allocVirtRegUndef(MO);
1321 }
1322 }
1323
1324 // Free early clobbers.
1325 if (HasEarlyClobber) {
1326 for (unsigned I = MI.getNumOperands(); I-- > 0; ) {
1327 MachineOperand &MO = MI.getOperand(I);
1328 if (!MO.isReg() || !MO.isDef() || !MO.isEarlyClobber())
1329 continue;
1330 // subreg defs don't free the full register. We left the subreg number
1331 // around as a marker in setPhysReg() to recognize this case here.
1332 if (MO.getSubReg() != 0) {
1333 MO.setSubReg(0);
1334 continue;
1335 }
1336
1337 Register Reg = MO.getReg();
1338 if (!Reg)
1339 continue;
1340 assert(Reg.isPhysical() && "should have register assigned");
1341
1342 // We sometimes get odd situations like:
1343 // early-clobber %x0 = INSTRUCTION %x0
1344 // which is semantically questionable as the early-clobber should
1345 // apply before the use. But in practice we consider the use to
1346 // happen before the early clobber now. Don't free the early clobber
1347 // register in this case.
1348 if (MI.readsRegister(Reg, TRI))
1349 continue;
1350
1351 freePhysReg(Reg);
1352 }
1353 }
1354
1355 LLVM_DEBUG(dbgs() << "<< " << MI);
1356 if (MI.isCopy() && MI.getOperand(0).getReg() == MI.getOperand(1).getReg() &&
1357 MI.getNumOperands() == 2) {
1358 LLVM_DEBUG(dbgs() << "Mark identity copy for removal\n");
1359 Coalesced.push_back(&MI);
1360 }
1361 }
1362
handleDebugValue(MachineInstr & MI)1363 void RegAllocFast::handleDebugValue(MachineInstr &MI) {
1364 MachineOperand &MO = MI.getDebugOperand(0);
1365
1366 // Ignore DBG_VALUEs that aren't based on virtual registers. These are
1367 // mostly constants and frame indices.
1368 if (!MO.isReg())
1369 return;
1370 Register Reg = MO.getReg();
1371 if (!Register::isVirtualRegister(Reg))
1372 return;
1373
1374 // Already spilled to a stackslot?
1375 int SS = StackSlotForVirtReg[Reg];
1376 if (SS != -1) {
1377 // Modify DBG_VALUE now that the value is in a spill slot.
1378 updateDbgValueForSpill(MI, SS);
1379 LLVM_DEBUG(dbgs() << "Rewrite DBG_VALUE for spilled memory: " << MI);
1380 return;
1381 }
1382
1383 // See if this virtual register has already been allocated to a physical
1384 // register or spilled to a stack slot.
1385 LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
1386 if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
1387 setPhysReg(MI, MO, LRI->PhysReg);
1388 } else {
1389 DanglingDbgValues[Reg].push_back(&MI);
1390 }
1391
1392 // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so
1393 // that future spills of Reg will have DBG_VALUEs.
1394 LiveDbgValueMap[Reg].push_back(&MI);
1395 }
1396
handleBundle(MachineInstr & MI)1397 void RegAllocFast::handleBundle(MachineInstr &MI) {
1398 MachineBasicBlock::instr_iterator BundledMI = MI.getIterator();
1399 ++BundledMI;
1400 while (BundledMI->isBundledWithPred()) {
1401 for (unsigned I = 0; I < BundledMI->getNumOperands(); ++I) {
1402 MachineOperand &MO = BundledMI->getOperand(I);
1403 if (!MO.isReg())
1404 continue;
1405
1406 Register Reg = MO.getReg();
1407 if (!Reg.isVirtual())
1408 continue;
1409
1410 DenseMap<Register, MCPhysReg>::iterator DI;
1411 DI = BundleVirtRegsMap.find(Reg);
1412 assert(DI != BundleVirtRegsMap.end() && "Unassigned virtual register");
1413
1414 setPhysReg(MI, MO, DI->second);
1415 }
1416
1417 ++BundledMI;
1418 }
1419 }
1420
allocateBasicBlock(MachineBasicBlock & MBB)1421 void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) {
1422 this->MBB = &MBB;
1423 LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);
1424
1425 RegUnitStates.assign(TRI->getNumRegUnits(), regFree);
1426 assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
1427
1428 for (MachineBasicBlock *Succ : MBB.successors()) {
1429 for (const MachineBasicBlock::RegisterMaskPair &LI : Succ->liveins())
1430 setPhysRegState(LI.PhysReg, regPreAssigned);
1431 }
1432
1433 Coalesced.clear();
1434
1435 // Traverse block in reverse order allocating instructions one by one.
1436 for (MachineInstr &MI : reverse(MBB)) {
1437 LLVM_DEBUG(
1438 dbgs() << "\n>> " << MI << "Regs:";
1439 dumpState()
1440 );
1441
1442 // Special handling for debug values. Note that they are not allowed to
1443 // affect codegen of the other instructions in any way.
1444 if (MI.isDebugValue()) {
1445 handleDebugValue(MI);
1446 continue;
1447 }
1448
1449 allocateInstruction(MI);
1450
1451 // Once BUNDLE header is assigned registers, same assignments need to be
1452 // done for bundled MIs.
1453 if (MI.getOpcode() == TargetOpcode::BUNDLE) {
1454 handleBundle(MI);
1455 }
1456 }
1457
1458 LLVM_DEBUG(
1459 dbgs() << "Begin Regs:";
1460 dumpState()
1461 );
1462
1463 // Spill all physical registers holding virtual registers now.
1464 LLVM_DEBUG(dbgs() << "Loading live registers at begin of block.\n");
1465 reloadAtBegin(MBB);
1466
1467 // Erase all the coalesced copies. We are delaying it until now because
1468 // LiveVirtRegs might refer to the instrs.
1469 for (MachineInstr *MI : Coalesced)
1470 MBB.erase(MI);
1471 NumCoalesced += Coalesced.size();
1472
1473 for (auto &UDBGPair : DanglingDbgValues) {
1474 for (MachineInstr *DbgValue : UDBGPair.second) {
1475 assert(DbgValue->isDebugValue() && "expected DBG_VALUE");
1476 MachineOperand &MO = DbgValue->getOperand(0);
1477 // Nothing to do if the vreg was spilled in the meantime.
1478 if (!MO.isReg())
1479 continue;
1480 LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue
1481 << '\n');
1482 MO.setReg(0);
1483 }
1484 }
1485 DanglingDbgValues.clear();
1486
1487 LLVM_DEBUG(MBB.dump());
1488 }
1489
runOnMachineFunction(MachineFunction & MF)1490 bool RegAllocFast::runOnMachineFunction(MachineFunction &MF) {
1491 LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1492 << "********** Function: " << MF.getName() << '\n');
1493 MRI = &MF.getRegInfo();
1494 const TargetSubtargetInfo &STI = MF.getSubtarget();
1495 TRI = STI.getRegisterInfo();
1496 TII = STI.getInstrInfo();
1497 MFI = &MF.getFrameInfo();
1498 MRI->freezeReservedRegs(MF);
1499 RegClassInfo.runOnMachineFunction(MF);
1500 unsigned NumRegUnits = TRI->getNumRegUnits();
1501 UsedInInstr.clear();
1502 UsedInInstr.setUniverse(NumRegUnits);
1503 PhysRegUses.clear();
1504 PhysRegUses.setUniverse(NumRegUnits);
1505
1506 // initialize the virtual->physical register map to have a 'null'
1507 // mapping for all virtual registers
1508 unsigned NumVirtRegs = MRI->getNumVirtRegs();
1509 StackSlotForVirtReg.resize(NumVirtRegs);
1510 LiveVirtRegs.setUniverse(NumVirtRegs);
1511 MayLiveAcrossBlocks.clear();
1512 MayLiveAcrossBlocks.resize(NumVirtRegs);
1513
1514 // Loop over all of the basic blocks, eliminating virtual register references
1515 for (MachineBasicBlock &MBB : MF)
1516 allocateBasicBlock(MBB);
1517
1518 // All machine operands and other references to virtual registers have been
1519 // replaced. Remove the virtual registers.
1520 MRI->clearVirtRegs();
1521
1522 StackSlotForVirtReg.clear();
1523 LiveDbgValueMap.clear();
1524 return true;
1525 }
1526
createFastRegisterAllocator()1527 FunctionPass *llvm::createFastRegisterAllocator() {
1528 return new RegAllocFast();
1529 }
1530