Line data Source code
1 : //===- RegAllocFast.cpp - A fast register allocator for debug code --------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : /// \file This register allocator allocates registers to a basic block at a
11 : /// time, attempting to keep values in registers and reusing registers as
12 : /// appropriate.
13 : //
14 : //===----------------------------------------------------------------------===//
15 :
16 : #include "llvm/ADT/ArrayRef.h"
17 : #include "llvm/ADT/DenseMap.h"
18 : #include "llvm/ADT/IndexedMap.h"
19 : #include "llvm/ADT/SmallSet.h"
20 : #include "llvm/ADT/SmallVector.h"
21 : #include "llvm/ADT/SparseSet.h"
22 : #include "llvm/ADT/Statistic.h"
23 : #include "llvm/CodeGen/MachineBasicBlock.h"
24 : #include "llvm/CodeGen/MachineFrameInfo.h"
25 : #include "llvm/CodeGen/MachineFunction.h"
26 : #include "llvm/CodeGen/MachineFunctionPass.h"
27 : #include "llvm/CodeGen/MachineInstr.h"
28 : #include "llvm/CodeGen/MachineInstrBuilder.h"
29 : #include "llvm/CodeGen/MachineOperand.h"
30 : #include "llvm/CodeGen/MachineRegisterInfo.h"
31 : #include "llvm/CodeGen/RegAllocRegistry.h"
32 : #include "llvm/CodeGen/RegisterClassInfo.h"
33 : #include "llvm/CodeGen/TargetInstrInfo.h"
34 : #include "llvm/CodeGen/TargetOpcodes.h"
35 : #include "llvm/CodeGen/TargetRegisterInfo.h"
36 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
37 : #include "llvm/IR/DebugLoc.h"
38 : #include "llvm/IR/Metadata.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(NumCopies, "Number of copies coalesced");
58 :
59 : static RegisterRegAlloc
60 : fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
61 :
62 : namespace {
63 :
64 : class RegAllocFast : public MachineFunctionPass {
65 : public:
66 : static char ID;
67 :
68 7228 : RegAllocFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1) {}
69 :
70 : private:
71 : MachineFrameInfo *MFI;
72 : MachineRegisterInfo *MRI;
73 : const TargetRegisterInfo *TRI;
74 : const TargetInstrInfo *TII;
75 : RegisterClassInfo RegClassInfo;
76 :
77 : /// Basic block currently being allocated.
78 : MachineBasicBlock *MBB;
79 :
80 : /// Maps virtual regs to the frame index where these values are spilled.
81 : IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
82 :
83 : /// Everything we know about a live virtual register.
84 : struct LiveReg {
85 : MachineInstr *LastUse = nullptr; ///< Last instr to use reg.
86 : unsigned VirtReg; ///< Virtual register number.
87 : MCPhysReg PhysReg = 0; ///< Currently held here.
88 : unsigned short LastOpNum = 0; ///< OpNum on LastUse.
89 : bool Dirty = false; ///< Register needs spill.
90 :
91 34582782 : explicit LiveReg(unsigned v) : VirtReg(v) {}
92 :
93 0 : unsigned getSparseSetIndex() const {
94 0 : return TargetRegisterInfo::virtReg2Index(VirtReg);
95 : }
96 : };
97 :
98 : using LiveRegMap = SparseSet<LiveReg>;
99 :
100 : /// This map contains entries for each virtual register that is currently
101 : /// available in a physical register.
102 : LiveRegMap LiveVirtRegs;
103 :
104 : DenseMap<unsigned, SmallVector<MachineInstr *, 4>> LiveDbgValueMap;
105 :
106 : /// Track the state of a physical register.
107 : enum RegState {
108 : /// A disabled register is not available for allocation, but an alias may
109 : /// be in use. A register can only be moved out of the disabled state if
110 : /// all aliases are disabled.
111 : regDisabled,
112 :
113 : /// A free register is not currently in use and can be allocated
114 : /// immediately without checking aliases.
115 : regFree,
116 :
117 : /// A reserved register has been assigned explicitly (e.g., setting up a
118 : /// call parameter), and it remains reserved until it is used.
119 : regReserved
120 :
121 : /// A register state may also be a virtual register number, indication
122 : /// that the physical register is currently allocated to a virtual
123 : /// register. In that case, LiveVirtRegs contains the inverse mapping.
124 : };
125 :
126 : /// One of the RegState enums, or a virtreg.
127 : std::vector<unsigned> PhysRegState;
128 :
129 : SmallVector<unsigned, 16> VirtDead;
130 : SmallVector<MachineInstr *, 32> Coalesced;
131 :
132 : /// Set of register units.
133 : using UsedInInstrSet = SparseSet<unsigned>;
134 :
135 : /// Set of register units that are used in the current instruction, and so
136 : /// cannot be allocated.
137 : UsedInInstrSet UsedInInstr;
138 :
139 : /// Mark a physreg as used in this instruction.
140 46446309 : void markRegUsedInInstr(MCPhysReg PhysReg) {
141 228303303 : for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
142 270821370 : UsedInInstr.insert(*Units);
143 46446309 : }
144 :
145 : /// Check if a physreg or any of its aliases are used in this instruction.
146 21135673 : bool isRegUsedInInstr(MCPhysReg PhysReg) const {
147 103265471 : for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units)
148 61044990 : if (UsedInInstr.count(*Units))
149 : return true;
150 21084808 : return false;
151 : }
152 :
153 : /// This flag is set when LiveRegMap will be cleared completely after
154 : /// spilling all live registers. LiveRegMap entries should not be erased.
155 : bool isBulkSpilling = false;
156 :
157 : enum : unsigned {
158 : spillClean = 1,
159 : spillDirty = 100,
160 : spillImpossible = ~0u
161 : };
162 :
163 : public:
164 7202 : StringRef getPassName() const override { return "Fast Register Allocator"; }
165 :
166 7198 : void getAnalysisUsage(AnalysisUsage &AU) const override {
167 7198 : AU.setPreservesCFG();
168 7198 : MachineFunctionPass::getAnalysisUsage(AU);
169 7198 : }
170 :
171 7198 : MachineFunctionProperties getRequiredProperties() const override {
172 7198 : return MachineFunctionProperties().set(
173 7198 : MachineFunctionProperties::Property::NoPHIs);
174 : }
175 :
176 7198 : MachineFunctionProperties getSetProperties() const override {
177 7198 : return MachineFunctionProperties().set(
178 7198 : MachineFunctionProperties::Property::NoVRegs);
179 : }
180 :
181 : private:
182 : bool runOnMachineFunction(MachineFunction &MF) override;
183 : void allocateBasicBlock(MachineBasicBlock &MBB);
184 : void handleThroughOperands(MachineInstr &MI,
185 : SmallVectorImpl<unsigned> &VirtDead);
186 : int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass &RC);
187 : bool isLastUseOfLocalReg(const MachineOperand &MO) const;
188 :
189 : void addKillFlag(const LiveReg &LRI);
190 : void killVirtReg(LiveRegMap::iterator LRI);
191 : void killVirtReg(unsigned VirtReg);
192 : void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator);
193 : void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg);
194 :
195 : void usePhysReg(MachineOperand &MO);
196 : void definePhysReg(MachineBasicBlock::iterator MI, MCPhysReg PhysReg,
197 : RegState NewState);
198 : unsigned calcSpillCost(MCPhysReg PhysReg) const;
199 : void assignVirtToPhysReg(LiveReg &, MCPhysReg PhysReg);
200 :
201 : LiveRegMap::iterator findLiveVirtReg(unsigned VirtReg) {
202 7757014 : return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg));
203 : }
204 :
205 : LiveRegMap::const_iterator findLiveVirtReg(unsigned VirtReg) const {
206 5404531 : return LiveVirtRegs.find(TargetRegisterInfo::virtReg2Index(VirtReg));
207 : }
208 :
209 : LiveRegMap::iterator assignVirtToPhysReg(unsigned VirtReg, MCPhysReg PhysReg);
210 : LiveRegMap::iterator allocVirtReg(MachineInstr &MI, LiveRegMap::iterator,
211 : unsigned Hint);
212 : LiveRegMap::iterator defineVirtReg(MachineInstr &MI, unsigned OpNum,
213 : unsigned VirtReg, unsigned Hint);
214 : LiveRegMap::iterator reloadVirtReg(MachineInstr &MI, unsigned OpNum,
215 : unsigned VirtReg, unsigned Hint);
216 : void spillAll(MachineBasicBlock::iterator MI);
217 : bool setPhysReg(MachineInstr &MI, unsigned OpNum, MCPhysReg PhysReg);
218 :
219 : void dumpState();
220 : };
221 :
222 : } // end anonymous namespace
223 :
224 : char RegAllocFast::ID = 0;
225 :
226 85147 : INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false,
227 : false)
228 :
229 : /// This allocates space for the specified virtual register to be held on the
230 : /// stack.
231 3093831 : int RegAllocFast::getStackSpaceFor(unsigned VirtReg,
232 : const TargetRegisterClass &RC) {
233 : // Find the location Reg would belong...
234 3093831 : int SS = StackSlotForVirtReg[VirtReg];
235 : // Already has space allocated?
236 3093831 : if (SS != -1)
237 : return SS;
238 :
239 : // Allocate a new stack object for this spill location...
240 1389842 : unsigned Size = TRI->getSpillSize(RC);
241 : unsigned Align = TRI->getSpillAlignment(RC);
242 1389842 : int FrameIdx = MFI->CreateSpillStackObject(Size, Align);
243 :
244 : // Assign the slot.
245 1389842 : StackSlotForVirtReg[VirtReg] = FrameIdx;
246 1389842 : return FrameIdx;
247 : }
248 :
249 : /// Return true if MO is the only remaining reference to its virtual register,
250 : /// and it is guaranteed to be a block-local register.
251 16370274 : bool RegAllocFast::isLastUseOfLocalReg(const MachineOperand &MO) const {
252 : // If the register has ever been spilled or reloaded, we conservatively assume
253 : // it is a global register used in multiple blocks.
254 32740548 : if (StackSlotForVirtReg[MO.getReg()] != -1)
255 : return false;
256 :
257 : // Check that the use/def chain has exactly one operand - MO.
258 16370254 : MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(MO.getReg());
259 16370254 : if (&*I != &MO)
260 : return false;
261 : return ++I == MRI->reg_nodbg_end();
262 : }
263 :
264 : /// Set kill flags on last use of a virtual register.
265 0 : void RegAllocFast::addKillFlag(const LiveReg &LR) {
266 0 : if (!LR.LastUse) return;
267 0 : MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum);
268 0 : if (MO.isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) {
269 0 : if (MO.getReg() == LR.PhysReg)
270 : MO.setIsKill();
271 : // else, don't do anything we are problably redefining a
272 : // subreg of this register and given we don't track which
273 : // lanes are actually dead, we cannot insert a kill flag here.
274 : // Otherwise we may end up in a situation like this:
275 : // ... = (MO) physreg:sub1, implicit killed physreg
276 : // ... <== Here we would allow later pass to reuse physreg:sub1
277 : // which is potentially wrong.
278 : // LR:sub0 = ...
279 : // ... = LR.sub1 <== This is going to use physreg:sub1
280 : }
281 : }
282 :
283 : /// Mark virtreg as no longer available.
284 16971180 : void RegAllocFast::killVirtReg(LiveRegMap::iterator LRI) {
285 16971180 : addKillFlag(*LRI);
286 : assert(PhysRegState[LRI->PhysReg] == LRI->VirtReg &&
287 : "Broken RegState mapping");
288 16971180 : PhysRegState[LRI->PhysReg] = regFree;
289 : // Erase from LiveVirtRegs unless we're spilling in bulk.
290 16971180 : if (!isBulkSpilling)
291 14995489 : LiveVirtRegs.erase(LRI);
292 16971180 : }
293 :
294 : /// Mark virtreg as no longer available.
295 415 : void RegAllocFast::killVirtReg(unsigned VirtReg) {
296 : assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
297 : "killVirtReg needs a virtual register");
298 : LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
299 415 : if (LRI != LiveVirtRegs.end())
300 415 : killVirtReg(LRI);
301 415 : }
302 :
303 : /// This method spills the value specified by VirtReg into the corresponding
304 : /// stack slot if needed.
305 1087404 : void RegAllocFast::spillVirtReg(MachineBasicBlock::iterator MI,
306 : unsigned VirtReg) {
307 : assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
308 : "Spilling a physical register is illegal!");
309 : LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
310 : assert(LRI != LiveVirtRegs.end() && "Spilling unmapped virtual register");
311 1087404 : spillVirtReg(MI, LRI);
312 1087404 : }
313 :
314 : /// Do the actual work of spilling.
315 3063095 : void RegAllocFast::spillVirtReg(MachineBasicBlock::iterator MI,
316 : LiveRegMap::iterator LRI) {
317 : LiveReg &LR = *LRI;
318 : assert(PhysRegState[LR.PhysReg] == LRI->VirtReg && "Broken RegState mapping");
319 :
320 3063095 : if (LR.Dirty) {
321 : // If this physreg is used by the instruction, we want to kill it on the
322 : // instruction, not on the spill.
323 1506718 : bool SpillKill = MachineBasicBlock::iterator(LR.LastUse) != MI;
324 1506718 : LR.Dirty = false;
325 : LLVM_DEBUG(dbgs() << "Spilling " << printReg(LRI->VirtReg, TRI) << " in "
326 : << printReg(LR.PhysReg, TRI));
327 1506718 : const TargetRegisterClass &RC = *MRI->getRegClass(LRI->VirtReg);
328 1506718 : int FI = getStackSpaceFor(LRI->VirtReg, RC);
329 : LLVM_DEBUG(dbgs() << " to stack slot #" << FI << "\n");
330 1506718 : TII->storeRegToStackSlot(*MBB, MI, LR.PhysReg, SpillKill, FI, &RC, TRI);
331 : ++NumStores; // Update statistics
332 :
333 : // If this register is used by DBG_VALUE then insert new DBG_VALUE to
334 : // identify spilled location as the place to find corresponding variable's
335 : // value.
336 : SmallVectorImpl<MachineInstr *> &LRIDbgValues =
337 1506718 : LiveDbgValueMap[LRI->VirtReg];
338 1506760 : for (MachineInstr *DBG : LRIDbgValues) {
339 42 : MachineInstr *NewDV = buildDbgValueForSpill(*MBB, MI, *DBG, FI);
340 : assert(NewDV->getParent() == MBB && "dangling parent pointer");
341 : (void)NewDV;
342 : LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:"
343 : << "\n"
344 : << *NewDV);
345 : }
346 : // Now this register is spilled there is should not be any DBG_VALUE
347 : // pointing to this register because they are all pointing to spilled value
348 : // now.
349 : LRIDbgValues.clear();
350 1506718 : if (SpillKill)
351 1493216 : LR.LastUse = nullptr; // Don't kill register again
352 : }
353 3063095 : killVirtReg(LRI);
354 3063095 : }
355 :
356 : /// Spill all dirty virtregs without killing them.
357 4857616 : void RegAllocFast::spillAll(MachineBasicBlock::iterator MI) {
358 4857616 : if (LiveVirtRegs.empty()) return;
359 1456469 : isBulkSpilling = true;
360 : // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
361 : // of spilling here is deterministic, if arbitrary.
362 1975691 : for (LiveRegMap::iterator I = LiveVirtRegs.begin(), E = LiveVirtRegs.end();
363 3432160 : I != E; ++I)
364 1975691 : spillVirtReg(MI, I);
365 : LiveVirtRegs.clear();
366 1456469 : isBulkSpilling = false;
367 : }
368 :
369 : /// Handle the direct use of a physical register. Check that the register is
370 : /// not used by a virtreg. Kill the physreg, marking it free. This may add
371 : /// implicit kills to MO->getParent() and invalidate MO.
372 5658079 : void RegAllocFast::usePhysReg(MachineOperand &MO) {
373 : // Ignore undef uses.
374 5658079 : if (MO.isUndef())
375 : return;
376 :
377 5658071 : unsigned PhysReg = MO.getReg();
378 : assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
379 : "Bad usePhysReg operand");
380 :
381 5658071 : markRegUsedInInstr(PhysReg);
382 11316142 : switch (PhysRegState[PhysReg]) {
383 : case regDisabled:
384 : break;
385 5658058 : case regReserved:
386 5658058 : PhysRegState[PhysReg] = regFree;
387 : LLVM_FALLTHROUGH;
388 5658061 : case regFree:
389 : MO.setIsKill();
390 : return;
391 0 : default:
392 : // The physreg was allocated to a virtual register. That means the value we
393 : // wanted has been clobbered.
394 0 : llvm_unreachable("Instruction uses an allocated register");
395 : }
396 :
397 : // Maybe a superregister is reserved?
398 66 : for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
399 : MCPhysReg Alias = *AI;
400 112 : switch (PhysRegState[Alias]) {
401 : case regDisabled:
402 : break;
403 18 : case regReserved:
404 : // Either PhysReg is a subregister of Alias and we mark the
405 : // whole register as free, or PhysReg is the superregister of
406 : // Alias and we mark all the aliases as disabled before freeing
407 : // PhysReg.
408 : // In the latter case, since PhysReg was disabled, this means that
409 : // its value is defined only by physical sub-registers. This check
410 : // is performed by the assert of the default case in this loop.
411 : // Note: The value of the superregister may only be partial
412 : // defined, that is why regDisabled is a valid state for aliases.
413 : assert((TRI->isSuperRegister(PhysReg, Alias) ||
414 : TRI->isSuperRegister(Alias, PhysReg)) &&
415 : "Instruction is not using a subregister of a reserved register");
416 : LLVM_FALLTHROUGH;
417 : case regFree:
418 18 : if (TRI->isSuperRegister(PhysReg, Alias)) {
419 : // Leave the superregister in the working set.
420 0 : PhysRegState[Alias] = regFree;
421 0 : MO.getParent()->addRegisterKilled(Alias, TRI, true);
422 0 : return;
423 : }
424 : // Some other alias was in the working set - clear it.
425 18 : PhysRegState[Alias] = regDisabled;
426 18 : break;
427 0 : default:
428 0 : llvm_unreachable("Instruction uses an alias of an allocated register");
429 : }
430 : }
431 :
432 : // All aliases are disabled, bring register into working set.
433 20 : PhysRegState[PhysReg] = regFree;
434 : MO.setIsKill();
435 : }
436 :
437 : /// Mark PhysReg as reserved or free after spilling any virtregs. This is very
438 : /// similar to defineVirtReg except the physreg is reserved instead of
439 : /// allocated.
440 6190536 : void RegAllocFast::definePhysReg(MachineBasicBlock::iterator MI,
441 : MCPhysReg PhysReg, RegState NewState) {
442 6190536 : markRegUsedInInstr(PhysReg);
443 12381072 : switch (unsigned VirtReg = PhysRegState[PhysReg]) {
444 : case regDisabled:
445 : break;
446 1044235 : default:
447 1044235 : spillVirtReg(MI, VirtReg);
448 : LLVM_FALLTHROUGH;
449 4446450 : case regFree:
450 : case regReserved:
451 4446450 : PhysRegState[PhysReg] = NewState;
452 4446450 : return;
453 : }
454 :
455 : // This is a disabled register, disable all aliases.
456 1744086 : PhysRegState[PhysReg] = NewState;
457 14682964 : for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
458 : MCPhysReg Alias = *AI;
459 26155278 : switch (unsigned VirtReg = PhysRegState[Alias]) {
460 : case regDisabled:
461 : break;
462 43169 : default:
463 43169 : spillVirtReg(MI, VirtReg);
464 : LLVM_FALLTHROUGH;
465 321827 : case regFree:
466 : case regReserved:
467 321827 : PhysRegState[Alias] = regDisabled;
468 321827 : if (TRI->isSuperRegister(PhysReg, Alias))
469 138761 : return;
470 : break;
471 : }
472 : }
473 : }
474 :
475 : /// Return the cost of spilling clearing out PhysReg and aliases so it is
476 : /// free for allocation. Returns 0 when PhysReg is free or disabled with all
477 : /// aliases disabled - it can be allocated directly.
478 : /// \returns spillImpossible when PhysReg or an alias can't be spilled.
479 15565972 : unsigned RegAllocFast::calcSpillCost(MCPhysReg PhysReg) const {
480 15565972 : if (isRegUsedInInstr(PhysReg)) {
481 : LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI)
482 : << " is already used in instr.\n");
483 : return spillImpossible;
484 : }
485 31062594 : switch (unsigned VirtReg = PhysRegState[PhysReg]) {
486 : case regDisabled:
487 : break;
488 : case regFree:
489 : return 0;
490 23882 : case regReserved:
491 : LLVM_DEBUG(dbgs() << printReg(VirtReg, TRI) << " corresponding "
492 : << printReg(PhysReg, TRI) << " is reserved already.\n");
493 23882 : return spillImpossible;
494 : default: {
495 : LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
496 : assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
497 2901940 : return I->Dirty ? spillDirty : spillClean;
498 : }
499 : }
500 :
501 : // This is a disabled register, add up cost of aliases.
502 : LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << " is disabled.\n");
503 : unsigned Cost = 0;
504 63367022 : for (MCRegAliasIterator AI(PhysReg, TRI, false); AI.isValid(); ++AI) {
505 : MCPhysReg Alias = *AI;
506 111979346 : switch (unsigned VirtReg = PhysRegState[Alias]) {
507 : case regDisabled:
508 : break;
509 1739712 : case regFree:
510 1739712 : ++Cost;
511 1739712 : break;
512 18221 : case regReserved:
513 18221 : return spillImpossible;
514 : default: {
515 : LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
516 : assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
517 2502591 : Cost += I->Dirty ? spillDirty : spillClean;
518 2502591 : break;
519 : }
520 : }
521 : }
522 7377349 : return Cost;
523 : }
524 :
525 : /// This method updates local state so that we know that PhysReg is the
526 : /// proper container for VirtReg now. The physical register must not be used
527 : /// for anything else when this is called.
528 : void RegAllocFast::assignVirtToPhysReg(LiveReg &LR, MCPhysReg PhysReg) {
529 : LLVM_DEBUG(dbgs() << "Assigning " << printReg(LR.VirtReg, TRI) << " to "
530 : << printReg(PhysReg, TRI) << "\n");
531 16971180 : PhysRegState[PhysReg] = LR.VirtReg;
532 : assert(!LR.PhysReg && "Already assigned a physreg");
533 16971180 : LR.PhysReg = PhysReg;
534 : }
535 :
536 : RegAllocFast::LiveRegMap::iterator
537 : RegAllocFast::assignVirtToPhysReg(unsigned VirtReg, MCPhysReg PhysReg) {
538 : LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
539 : assert(LRI != LiveVirtRegs.end() && "VirtReg disappeared");
540 : assignVirtToPhysReg(*LRI, PhysReg);
541 : return LRI;
542 : }
543 :
544 : /// Allocates a physical register for VirtReg.
545 16971180 : RegAllocFast::LiveRegMap::iterator RegAllocFast::allocVirtReg(MachineInstr &MI,
546 : LiveRegMap::iterator LRI, unsigned Hint) {
547 16971180 : const unsigned VirtReg = LRI->VirtReg;
548 :
549 : assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
550 : "Can only allocate virtual registers");
551 :
552 : // Take hint when possible.
553 16971180 : const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
554 8426812 : if (TargetRegisterInfo::isPhysicalRegister(Hint) &&
555 25343541 : MRI->isAllocatable(Hint) && RC.contains(Hint)) {
556 : // Ignore the hint if we would have to spill a dirty register.
557 8011328 : unsigned Cost = calcSpillCost(Hint);
558 8011328 : if (Cost < spillDirty) {
559 7756916 : if (Cost)
560 493991 : definePhysReg(MI, Hint, regFree);
561 : // definePhysReg may kill virtual registers and modify LiveVirtRegs.
562 : // That invalidates LRI, so run a new lookup for VirtReg.
563 7756916 : return assignVirtToPhysReg(VirtReg, Hint);
564 : }
565 : }
566 :
567 : // First try to find a completely free register.
568 9214264 : ArrayRef<MCPhysReg> AO = RegClassInfo.getOrder(&RC);
569 69355056 : for (MCPhysReg PhysReg : AO) {
570 131388606 : if (PhysRegState[PhysReg] == regFree && !isRegUsedInInstr(PhysReg)) {
571 : assignVirtToPhysReg(*LRI, PhysReg);
572 5553511 : return LRI;
573 : }
574 : }
575 :
576 : LLVM_DEBUG(dbgs() << "Allocating " << printReg(VirtReg) << " from "
577 : << TRI->getRegClassName(&RC) << "\n");
578 :
579 : unsigned BestReg = 0;
580 : unsigned BestCost = spillImpossible;
581 7557459 : for (MCPhysReg PhysReg : AO) {
582 7554644 : unsigned Cost = calcSpillCost(PhysReg);
583 : LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << "\n");
584 : LLVM_DEBUG(dbgs() << "\tCost: " << Cost << "\n");
585 : LLVM_DEBUG(dbgs() << "\tBestCost: " << BestCost << "\n");
586 : // Cost is 0 when all aliases are already disabled.
587 7554644 : if (Cost == 0) {
588 : assignVirtToPhysReg(*LRI, PhysReg);
589 3657938 : return LRI;
590 : }
591 3896706 : if (Cost < BestCost)
592 2362965 : BestReg = PhysReg, BestCost = Cost;
593 : }
594 :
595 2815 : if (BestReg) {
596 5600 : definePhysReg(MI, BestReg, regFree);
597 : // definePhysReg may kill virtual registers and modify LiveVirtRegs.
598 : // That invalidates LRI, so run a new lookup for VirtReg.
599 2800 : return assignVirtToPhysReg(VirtReg, BestReg);
600 : }
601 :
602 : // Nothing we can do. Report an error and keep going with a bad allocation.
603 15 : if (MI.isInlineAsm())
604 15 : MI.emitError("inline assembly requires more registers than available");
605 : else
606 0 : MI.emitError("ran out of registers during register allocation");
607 30 : definePhysReg(MI, *AO.begin(), regFree);
608 15 : return assignVirtToPhysReg(VirtReg, *AO.begin());
609 : }
610 :
611 : /// Allocates a register for VirtReg and mark it as dirty.
612 16483662 : RegAllocFast::LiveRegMap::iterator RegAllocFast::defineVirtReg(MachineInstr &MI,
613 : unsigned OpNum,
614 : unsigned VirtReg,
615 : unsigned Hint) {
616 : assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
617 : "Not a virtual register");
618 : LiveRegMap::iterator LRI;
619 : bool New;
620 16483662 : std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
621 16483662 : if (New) {
622 : // If there is no hint, peek at the only use of this register.
623 25613430 : if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) &&
624 10229363 : MRI->hasOneNonDBGUse(VirtReg)) {
625 9097418 : const MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(VirtReg);
626 : // It's a copy, use the destination register as a hint.
627 : if (UseMI.isCopyLike())
628 4416842 : Hint = UseMI.getOperand(0).getReg();
629 : }
630 15384067 : LRI = allocVirtReg(MI, LRI, Hint);
631 1099595 : } else if (LRI->LastUse) {
632 : // Redefining a live register - kill at the last use, unless it is this
633 : // instruction defining VirtReg multiple times.
634 1099595 : if (LRI->LastUse != &MI || LRI->LastUse->getOperand(LRI->LastOpNum).isUse())
635 1097696 : addKillFlag(*LRI);
636 : }
637 : assert(LRI->PhysReg && "Register not assigned");
638 16483662 : LRI->LastUse = &MI;
639 16483662 : LRI->LastOpNum = OpNum;
640 16483662 : LRI->Dirty = true;
641 16483662 : markRegUsedInInstr(LRI->PhysReg);
642 16483662 : return LRI;
643 : }
644 :
645 : /// Make sure VirtReg is available in a physreg and return it.
646 18099120 : RegAllocFast::LiveRegMap::iterator RegAllocFast::reloadVirtReg(MachineInstr &MI,
647 : unsigned OpNum,
648 : unsigned VirtReg,
649 : unsigned Hint) {
650 : assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
651 : "Not a virtual register");
652 : LiveRegMap::iterator LRI;
653 : bool New;
654 18099120 : std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
655 18099120 : MachineOperand &MO = MI.getOperand(OpNum);
656 18099120 : if (New) {
657 1587113 : LRI = allocVirtReg(MI, LRI, Hint);
658 1587113 : const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
659 1587113 : int FrameIndex = getStackSpaceFor(VirtReg, RC);
660 : LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
661 : << printReg(LRI->PhysReg, TRI) << "\n");
662 3174226 : TII->loadRegFromStackSlot(*MBB, MI, LRI->PhysReg, FrameIndex, &RC, TRI);
663 : ++NumLoads;
664 16512007 : } else if (LRI->Dirty) {
665 16370274 : if (isLastUseOfLocalReg(MO)) {
666 : LLVM_DEBUG(dbgs() << "Killing last use: " << MO << "\n");
667 13876937 : if (MO.isUse())
668 : MO.setIsKill();
669 : else
670 : MO.setIsDead();
671 2493337 : } else if (MO.isKill()) {
672 : LLVM_DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n");
673 : MO.setIsKill(false);
674 2493335 : } else if (MO.isDead()) {
675 : LLVM_DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n");
676 : MO.setIsDead(false);
677 : }
678 141733 : } else if (MO.isKill()) {
679 : // We must remove kill flags from uses of reloaded registers because the
680 : // register would be killed immediately, and there might be a second use:
681 : // %foo = OR killed %x, %x
682 : // This would cause a second reload of %x into a different register.
683 : LLVM_DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n");
684 : MO.setIsKill(false);
685 141733 : } else if (MO.isDead()) {
686 : LLVM_DEBUG(dbgs() << "Clearing clean dead: " << MO << "\n");
687 : MO.setIsDead(false);
688 : }
689 : assert(LRI->PhysReg && "Register not assigned");
690 18099120 : LRI->LastUse = &MI;
691 18099120 : LRI->LastOpNum = OpNum;
692 18099120 : markRegUsedInInstr(LRI->PhysReg);
693 18099120 : return LRI;
694 : }
695 :
696 : /// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This
697 : /// may invalidate any operand pointers. Return true if the operand kills its
698 : /// register.
699 34580978 : bool RegAllocFast::setPhysReg(MachineInstr &MI, unsigned OpNum,
700 : MCPhysReg PhysReg) {
701 34580978 : MachineOperand &MO = MI.getOperand(OpNum);
702 : bool Dead = MO.isDead();
703 34580978 : if (!MO.getSubReg()) {
704 34228122 : MO.setReg(PhysReg);
705 34228122 : MO.setIsRenamable(true);
706 34228122 : return MO.isKill() || Dead;
707 : }
708 :
709 : // Handle subregister index.
710 352856 : MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0);
711 352856 : MO.setIsRenamable(true);
712 : MO.setSubReg(0);
713 :
714 : // A kill flag implies killing the full register. Add corresponding super
715 : // register kill.
716 352856 : if (MO.isKill()) {
717 337130 : MI.addRegisterKilled(PhysReg, TRI, true);
718 337130 : return true;
719 : }
720 :
721 : // A <def,read-undef> of a sub-register requires an implicit def of the full
722 : // register.
723 15726 : if (MO.isDef() && MO.isUndef())
724 245 : MI.addRegisterDefined(PhysReg, TRI);
725 :
726 : return Dead;
727 : }
728 :
729 : // Handles special instruction operand like early clobbers and tied ops when
730 : // there are additional physreg defines.
731 5571 : void RegAllocFast::handleThroughOperands(MachineInstr &MI,
732 : SmallVectorImpl<unsigned> &VirtDead) {
733 : LLVM_DEBUG(dbgs() << "Scanning for through registers:");
734 5571 : SmallSet<unsigned, 8> ThroughRegs;
735 27137 : for (const MachineOperand &MO : MI.operands()) {
736 26002 : if (!MO.isReg()) continue;
737 9641 : unsigned Reg = MO.getReg();
738 9641 : if (!TargetRegisterInfo::isVirtualRegister(Reg))
739 : continue;
740 5205 : if (MO.isEarlyClobber() || (MO.isUse() && MO.isTied()) ||
741 1901 : (MO.getSubReg() && MI.readsVirtualRegister(Reg))) {
742 2406 : if (ThroughRegs.insert(Reg).second)
743 : LLVM_DEBUG(dbgs() << ' ' << printReg(Reg));
744 : }
745 : }
746 :
747 : // If any physreg defines collide with preallocated through registers,
748 : // we must spill and reallocate.
749 : LLVM_DEBUG(dbgs() << "\nChecking for physdef collisions.\n");
750 27137 : for (const MachineOperand &MO : MI.operands()) {
751 21566 : if (!MO.isReg() || !MO.isDef()) continue;
752 6468 : unsigned Reg = MO.getReg();
753 6468 : if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
754 4002 : markRegUsedInInstr(Reg);
755 136509 : for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
756 265014 : if (ThroughRegs.count(PhysRegState[*AI]))
757 2 : definePhysReg(MI, *AI, regFree);
758 : }
759 : }
760 :
761 : SmallVector<unsigned, 8> PartialDefs;
762 : LLVM_DEBUG(dbgs() << "Allocating tied uses.\n");
763 27137 : for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
764 21566 : const MachineOperand &MO = MI.getOperand(I);
765 21566 : if (!MO.isReg()) continue;
766 9641 : unsigned Reg = MO.getReg();
767 9641 : if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
768 5205 : if (MO.isUse()) {
769 2739 : if (!MO.isTied()) continue;
770 : LLVM_DEBUG(dbgs() << "Operand " << I << "(" << MO
771 : << ") is tied to operand " << MI.findTiedOperandIdx(I)
772 : << ".\n");
773 204 : LiveRegMap::iterator LRI = reloadVirtReg(MI, I, Reg, 0);
774 204 : MCPhysReg PhysReg = LRI->PhysReg;
775 204 : setPhysReg(MI, I, PhysReg);
776 : // Note: we don't update the def operand yet. That would cause the normal
777 : // def-scan to attempt spilling.
778 4366 : } else if (MO.getSubReg() && MI.readsVirtualRegister(Reg)) {
779 : LLVM_DEBUG(dbgs() << "Partial redefine: " << MO << "\n");
780 : // Reload the register, but don't assign to the operand just yet.
781 : // That would confuse the later phys-def processing pass.
782 1900 : LiveRegMap::iterator LRI = reloadVirtReg(MI, I, Reg, 0);
783 1900 : PartialDefs.push_back(LRI->PhysReg);
784 : }
785 : }
786 :
787 : LLVM_DEBUG(dbgs() << "Allocating early clobbers.\n");
788 27137 : for (unsigned I = 0, E = MI.getNumOperands(); I != E; ++I) {
789 21566 : const MachineOperand &MO = MI.getOperand(I);
790 30906 : if (!MO.isReg()) continue;
791 9641 : unsigned Reg = MO.getReg();
792 9641 : if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
793 5001 : if (!MO.isEarlyClobber())
794 : continue;
795 : // Note: defineVirtReg may invalidate MO.
796 301 : LiveRegMap::iterator LRI = defineVirtReg(MI, I, Reg, 0);
797 301 : MCPhysReg PhysReg = LRI->PhysReg;
798 301 : if (setPhysReg(MI, I, PhysReg))
799 107 : VirtDead.push_back(Reg);
800 : }
801 :
802 : // Restore UsedInInstr to a state usable for allocating normal virtual uses.
803 : UsedInInstr.clear();
804 27137 : for (const MachineOperand &MO : MI.operands()) {
805 21566 : if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue;
806 7366 : unsigned Reg = MO.getReg();
807 7366 : if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
808 : LLVM_DEBUG(dbgs() << "\tSetting " << printReg(Reg, TRI)
809 : << " as used in instr\n");
810 4479 : markRegUsedInInstr(Reg);
811 : }
812 :
813 : // Also mark PartialDefs as used to avoid reallocation.
814 7471 : for (unsigned PartialDef : PartialDefs)
815 1900 : markRegUsedInInstr(PartialDef);
816 5571 : }
817 :
818 : #ifndef NDEBUG
819 : void RegAllocFast::dumpState() {
820 : for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) {
821 : if (PhysRegState[Reg] == regDisabled) continue;
822 : dbgs() << " " << printReg(Reg, TRI);
823 : switch(PhysRegState[Reg]) {
824 : case regFree:
825 : break;
826 : case regReserved:
827 : dbgs() << "*";
828 : break;
829 : default: {
830 : dbgs() << '=' << printReg(PhysRegState[Reg]);
831 : LiveRegMap::iterator I = findLiveVirtReg(PhysRegState[Reg]);
832 : assert(I != LiveVirtRegs.end() && "Missing VirtReg entry");
833 : if (I->Dirty)
834 : dbgs() << "*";
835 : assert(I->PhysReg == Reg && "Bad inverse map");
836 : break;
837 : }
838 : }
839 : }
840 : dbgs() << '\n';
841 : // Check that LiveVirtRegs is the inverse.
842 : for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
843 : e = LiveVirtRegs.end(); i != e; ++i) {
844 : assert(TargetRegisterInfo::isVirtualRegister(i->VirtReg) &&
845 : "Bad map key");
846 : assert(TargetRegisterInfo::isPhysicalRegister(i->PhysReg) &&
847 : "Bad map value");
848 : assert(PhysRegState[i->PhysReg] == i->VirtReg && "Bad inverse map");
849 : }
850 : }
851 : #endif
852 :
853 2822299 : void RegAllocFast::allocateBasicBlock(MachineBasicBlock &MBB) {
854 2822299 : this->MBB = &MBB;
855 : LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);
856 :
857 2822299 : PhysRegState.assign(TRI->getNumRegs(), regDisabled);
858 : assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");
859 :
860 2822299 : MachineBasicBlock::iterator MII = MBB.begin();
861 :
862 : // Add live-in registers as live.
863 3756358 : for (const MachineBasicBlock::RegisterMaskPair LI : MBB.liveins())
864 934059 : if (MRI->isAllocatable(LI.PhysReg))
865 934059 : definePhysReg(MII, LI.PhysReg, regReserved);
866 :
867 : VirtDead.clear();
868 : Coalesced.clear();
869 :
870 : // Otherwise, sequentially allocate each instruction in the MBB.
871 40544607 : for (MachineInstr &MI : MBB) {
872 37722308 : const MCInstrDesc &MCID = MI.getDesc();
873 : LLVM_DEBUG(dbgs() << "\n>> " << MI << "Regs:"; dumpState());
874 :
875 : // Debug values are not allowed to change codegen in any way.
876 37722308 : if (MI.isDebugValue()) {
877 144 : MachineInstr *DebugMI = &MI;
878 144 : MachineOperand &MO = DebugMI->getOperand(0);
879 :
880 : // Ignore DBG_VALUEs that aren't based on virtual registers. These are
881 : // mostly constants and frame indices.
882 144 : if (!MO.isReg())
883 : continue;
884 110 : unsigned Reg = MO.getReg();
885 110 : if (!TargetRegisterInfo::isVirtualRegister(Reg))
886 : continue;
887 :
888 : // See if this virtual register has already been allocated to a physical
889 : // register or spilled to a stack slot.
890 : LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
891 98 : if (LRI != LiveVirtRegs.end())
892 96 : setPhysReg(*DebugMI, 0, LRI->PhysReg);
893 : else {
894 2 : int SS = StackSlotForVirtReg[Reg];
895 2 : if (SS != -1) {
896 : // Modify DBG_VALUE now that the value is in a spill slot.
897 2 : updateDbgValueForSpill(*DebugMI, SS);
898 : LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:"
899 : << "\t" << *DebugMI);
900 2 : continue;
901 : }
902 :
903 : // We can't allocate a physreg for a DebugValue, sorry!
904 : LLVM_DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
905 0 : MO.setReg(0);
906 : }
907 :
908 : // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so
909 : // that future spills of Reg will have DBG_VALUEs.
910 96 : LiveDbgValueMap[Reg].push_back(DebugMI);
911 96 : continue;
912 : }
913 :
914 37722164 : if (MI.isDebugLabel())
915 : continue;
916 :
917 : // If this is a copy, we may be able to coalesce.
918 : unsigned CopySrcReg = 0;
919 : unsigned CopyDstReg = 0;
920 : unsigned CopySrcSub = 0;
921 : unsigned CopyDstSub = 0;
922 37722159 : if (MI.isCopy()) {
923 9098863 : CopyDstReg = MI.getOperand(0).getReg();
924 9098863 : CopySrcReg = MI.getOperand(1).getReg();
925 : CopyDstSub = MI.getOperand(0).getSubReg();
926 : CopySrcSub = MI.getOperand(1).getSubReg();
927 : }
928 :
929 : // Track registers used by instruction.
930 : UsedInInstr.clear();
931 :
932 : // First scan.
933 : // Mark physreg uses and early clobbers as used.
934 : // Find the end of the virtreg operands
935 : unsigned VirtOpEnd = 0;
936 : bool hasTiedOps = false;
937 : bool hasEarlyClobbers = false;
938 : bool hasPartialRedefs = false;
939 : bool hasPhysDefs = false;
940 210294444 : for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
941 172572285 : MachineOperand &MO = MI.getOperand(i);
942 : // Make sure MRI knows about registers clobbered by regmasks.
943 172572285 : if (MO.isRegMask()) {
944 2035217 : MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
945 2035217 : continue;
946 : }
947 170537068 : if (!MO.isReg()) continue;
948 105837757 : unsigned Reg = MO.getReg();
949 105837757 : if (!Reg) continue;
950 73756167 : if (TargetRegisterInfo::isVirtualRegister(Reg)) {
951 34580882 : VirtOpEnd = i+1;
952 34580882 : if (MO.isUse()) {
953 18097220 : hasTiedOps = hasTiedOps ||
954 17859596 : MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1;
955 : } else {
956 16483662 : if (MO.isEarlyClobber())
957 : hasEarlyClobbers = true;
958 16485807 : if (MO.getSubReg() && MI.readsVirtualRegister(Reg))
959 : hasPartialRedefs = true;
960 : }
961 34580882 : continue;
962 : }
963 39175285 : if (!MRI->isAllocatable(Reg)) continue;
964 10417749 : if (MO.isUse()) {
965 5658079 : usePhysReg(MO);
966 4759670 : } else if (MO.isEarlyClobber()) {
967 3681 : definePhysReg(MI, Reg,
968 4 : (MO.isImplicit() || MO.isDead()) ? regFree : regReserved);
969 : hasEarlyClobbers = true;
970 : } else
971 : hasPhysDefs = true;
972 : }
973 :
974 : // The instruction may have virtual register operands that must be allocated
975 : // the same register at use-time and def-time: early clobbers and tied
976 : // operands. If there are also physical defs, these registers must avoid
977 : // both physical defs and uses, making them more constrained than normal
978 : // operands.
979 : // Similarly, if there are multiple defs and tied operands, we must make
980 : // sure the same register is allocated to uses and defs.
981 : // We didn't detect inline asm tied operands above, so just make this extra
982 : // pass for all inline asm.
983 37722159 : if (MI.isInlineAsm() || hasEarlyClobbers || hasPartialRedefs ||
984 1097549 : (hasTiedOps && (hasPhysDefs || MCID.getNumDefs() > 1))) {
985 5571 : handleThroughOperands(MI, VirtDead);
986 : // Don't attempt coalescing when we have funny stuff going on.
987 : CopyDstReg = 0;
988 : // Pretend we have early clobbers so the use operands get marked below.
989 : // This is not necessary for the common case of a single tied use.
990 : hasEarlyClobbers = true;
991 : }
992 :
993 : // Second scan.
994 : // Allocate virtreg uses.
995 108256156 : for (unsigned I = 0; I != VirtOpEnd; ++I) {
996 70533997 : const MachineOperand &MO = MI.getOperand(I);
997 70533997 : if (!MO.isReg()) continue;
998 51509929 : unsigned Reg = MO.getReg();
999 51509929 : if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
1000 34580377 : if (MO.isUse()) {
1001 18097016 : LiveRegMap::iterator LRI = reloadVirtReg(MI, I, Reg, CopyDstReg);
1002 18097016 : MCPhysReg PhysReg = LRI->PhysReg;
1003 18097016 : CopySrcReg = (CopySrcReg == Reg || CopySrcReg == PhysReg) ? PhysReg : 0;
1004 18097016 : if (setPhysReg(MI, I, PhysReg))
1005 13907670 : killVirtReg(LRI);
1006 : }
1007 : }
1008 :
1009 : // Track registers defined by instruction - early clobbers and tied uses at
1010 : // this point.
1011 : UsedInInstr.clear();
1012 37722159 : if (hasEarlyClobbers) {
1013 27137 : for (const MachineOperand &MO : MI.operands()) {
1014 21566 : if (!MO.isReg()) continue;
1015 9641 : unsigned Reg = MO.getReg();
1016 9641 : if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
1017 : // Look for physreg defs and tied uses.
1018 7124 : if (!MO.isDef() && !MO.isTied()) continue;
1019 4539 : markRegUsedInInstr(Reg);
1020 : }
1021 : }
1022 :
1023 37722159 : unsigned DefOpEnd = MI.getNumOperands();
1024 37722159 : if (MI.isCall()) {
1025 : // Spill all virtregs before a call. This serves one purpose: If an
1026 : // exception is thrown, the landing pad is going to expect to find
1027 : // registers in their spill slots.
1028 : // Note: although this is appealing to just consider all definitions
1029 : // as call-clobbered, this is not correct because some of those
1030 : // definitions may be used later on and we do not want to reuse
1031 : // those for virtual registers in between.
1032 : LLVM_DEBUG(dbgs() << " Spilling remaining registers before call.\n");
1033 2035317 : spillAll(MI);
1034 : }
1035 :
1036 : // Third scan.
1037 : // Allocate defs and collect dead defs.
1038 210631574 : for (unsigned I = 0; I != DefOpEnd; ++I) {
1039 172909415 : const MachineOperand &MO = MI.getOperand(I);
1040 172909415 : if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber())
1041 156426054 : continue;
1042 37074306 : unsigned Reg = MO.getReg();
1043 :
1044 37074306 : if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1045 20590945 : if (!MRI->isAllocatable(Reg)) continue;
1046 14263063 : definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved);
1047 4755997 : continue;
1048 : }
1049 16483361 : LiveRegMap::iterator LRI = defineVirtReg(MI, I, Reg, CopySrcReg);
1050 16483361 : MCPhysReg PhysReg = LRI->PhysReg;
1051 16483361 : if (setPhysReg(MI, I, PhysReg)) {
1052 308 : VirtDead.push_back(Reg);
1053 : CopyDstReg = 0; // cancel coalescing;
1054 : } else
1055 16483053 : CopyDstReg = (CopyDstReg == Reg || CopyDstReg == PhysReg) ? PhysReg : 0;
1056 : }
1057 :
1058 : // Kill dead defs after the scan to ensure that multiple defs of the same
1059 : // register are allocated identically. We didn't need to do this for uses
1060 : // because we are crerating our own kill flags, and they are always at the
1061 : // last use.
1062 37722574 : for (unsigned VirtReg : VirtDead)
1063 415 : killVirtReg(VirtReg);
1064 : VirtDead.clear();
1065 :
1066 37722159 : if (CopyDstReg && CopyDstReg == CopySrcReg && CopyDstSub == CopySrcSub) {
1067 : LLVM_DEBUG(dbgs() << "-- coalescing: " << MI);
1068 7769659 : Coalesced.push_back(&MI);
1069 : } else {
1070 : LLVM_DEBUG(dbgs() << "<< " << MI);
1071 : }
1072 : }
1073 :
1074 : // Spill all physical registers holding virtual registers now.
1075 : LLVM_DEBUG(dbgs() << "Spilling live registers at end of block.\n");
1076 2822299 : spillAll(MBB.getFirstTerminator());
1077 :
1078 : // Erase all the coalesced copies. We are delaying it until now because
1079 : // LiveVirtRegs might refer to the instrs.
1080 10591958 : for (MachineInstr *MI : Coalesced)
1081 : MBB.erase(MI);
1082 : NumCopies += Coalesced.size();
1083 :
1084 : LLVM_DEBUG(MBB.dump());
1085 2822299 : }
1086 :
1087 : /// Allocates registers for a function.
1088 207413 : bool RegAllocFast::runOnMachineFunction(MachineFunction &MF) {
1089 : LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1090 : << "********** Function: " << MF.getName() << '\n');
1091 207413 : MRI = &MF.getRegInfo();
1092 207413 : const TargetSubtargetInfo &STI = MF.getSubtarget();
1093 207413 : TRI = STI.getRegisterInfo();
1094 207413 : TII = STI.getInstrInfo();
1095 207413 : MFI = &MF.getFrameInfo();
1096 207413 : MRI->freezeReservedRegs(MF);
1097 207413 : RegClassInfo.runOnMachineFunction(MF);
1098 : UsedInInstr.clear();
1099 207413 : UsedInInstr.setUniverse(TRI->getNumRegUnits());
1100 :
1101 : // initialize the virtual->physical register map to have a 'null'
1102 : // mapping for all virtual registers
1103 207413 : unsigned NumVirtRegs = MRI->getNumVirtRegs();
1104 207413 : StackSlotForVirtReg.resize(NumVirtRegs);
1105 207413 : LiveVirtRegs.setUniverse(NumVirtRegs);
1106 :
1107 : // Loop over all of the basic blocks, eliminating virtual register references
1108 3029712 : for (MachineBasicBlock &MBB : MF)
1109 2822299 : allocateBasicBlock(MBB);
1110 :
1111 : // All machine operands and other references to virtual registers have been
1112 : // replaced. Remove the virtual registers.
1113 207413 : MRI->clearVirtRegs();
1114 :
1115 : StackSlotForVirtReg.clear();
1116 207413 : LiveDbgValueMap.clear();
1117 207413 : return true;
1118 : }
1119 :
1120 7225 : FunctionPass *llvm::createFastRegisterAllocator() {
1121 7225 : return new RegAllocFast();
1122 : }
|
