1 //===-- RegisterScavenging.cpp - Machine register scavenging --------------===//
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 // This file implements the machine register scavenger. It can provide
11 // information, such as unused registers, at any point in a machine basic block.
12 // It also provides a mechanism to make registers available by evicting them to
13 // spill slots.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/CodeGen/RegisterScavenging.h"
18 #include "llvm/CodeGen/MachineBasicBlock.h"
19 #include "llvm/CodeGen/MachineFrameInfo.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/CodeGen/MachineInstr.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/ErrorHandling.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include "llvm/Target/TargetInstrInfo.h"
27 #include "llvm/Target/TargetRegisterInfo.h"
28 #include "llvm/Target/TargetSubtargetInfo.h"
29 using namespace llvm;
30 
31 #define DEBUG_TYPE "reg-scavenging"
32 
33 /// setUsed - Set the register units of this register as used.
setRegUsed(unsigned Reg)34 void RegScavenger::setRegUsed(unsigned Reg) {
35   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
36     RegUnitsAvailable.reset(*RUI);
37 }
38 
initRegState()39 void RegScavenger::initRegState() {
40   for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(),
41          IE = Scavenged.end(); I != IE; ++I) {
42     I->Reg = 0;
43     I->Restore = nullptr;
44   }
45 
46   // All register units start out unused.
47   RegUnitsAvailable.set();
48 
49   if (!MBB)
50     return;
51 
52   // Live-in registers are in use.
53   for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
54          E = MBB->livein_end(); I != E; ++I)
55     setRegUsed(*I);
56 
57   // Pristine CSRs are also unavailable.
58   BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB);
59   for (int I = PR.find_first(); I>0; I = PR.find_next(I))
60     setRegUsed(I);
61 }
62 
enterBasicBlock(MachineBasicBlock * mbb)63 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
64   MachineFunction &MF = *mbb->getParent();
65   TII = MF.getSubtarget().getInstrInfo();
66   TRI = MF.getSubtarget().getRegisterInfo();
67   MRI = &MF.getRegInfo();
68 
69   assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) &&
70          "Target changed?");
71 
72   // It is not possible to use the register scavenger after late optimization
73   // passes that don't preserve accurate liveness information.
74   assert(MRI->tracksLiveness() &&
75          "Cannot use register scavenger with inaccurate liveness");
76 
77   // Self-initialize.
78   if (!MBB) {
79     NumRegUnits = TRI->getNumRegUnits();
80     RegUnitsAvailable.resize(NumRegUnits);
81     KillRegUnits.resize(NumRegUnits);
82     DefRegUnits.resize(NumRegUnits);
83     TmpRegUnits.resize(NumRegUnits);
84   }
85 
86   MBB = mbb;
87   initRegState();
88 
89   Tracking = false;
90 }
91 
addRegUnits(BitVector & BV,unsigned Reg)92 void RegScavenger::addRegUnits(BitVector &BV, unsigned Reg) {
93   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
94     BV.set(*RUI);
95 }
96 
determineKillsAndDefs()97 void RegScavenger::determineKillsAndDefs() {
98   assert(Tracking && "Must be tracking to determine kills and defs");
99 
100   MachineInstr *MI = MBBI;
101   assert(!MI->isDebugValue() && "Debug values have no kills or defs");
102 
103   // Find out which registers are early clobbered, killed, defined, and marked
104   // def-dead in this instruction.
105   // FIXME: The scavenger is not predication aware. If the instruction is
106   // predicated, conservatively assume "kill" markers do not actually kill the
107   // register. Similarly ignores "dead" markers.
108   bool isPred = TII->isPredicated(MI);
109   KillRegUnits.reset();
110   DefRegUnits.reset();
111   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
112     const MachineOperand &MO = MI->getOperand(i);
113     if (MO.isRegMask()) {
114 
115       TmpRegUnits.clear();
116       for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd; ++RU) {
117         for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) {
118           if (MO.clobbersPhysReg(*RURI)) {
119             TmpRegUnits.set(RU);
120             break;
121           }
122         }
123       }
124 
125       // Apply the mask.
126       (isPred ? DefRegUnits : KillRegUnits) |= TmpRegUnits;
127     }
128     if (!MO.isReg())
129       continue;
130     unsigned Reg = MO.getReg();
131     if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg))
132       continue;
133 
134     if (MO.isUse()) {
135       // Ignore undef uses.
136       if (MO.isUndef())
137         continue;
138       if (!isPred && MO.isKill())
139         addRegUnits(KillRegUnits, Reg);
140     } else {
141       assert(MO.isDef());
142       if (!isPred && MO.isDead())
143         addRegUnits(KillRegUnits, Reg);
144       else
145         addRegUnits(DefRegUnits, Reg);
146     }
147   }
148 }
149 
unprocess()150 void RegScavenger::unprocess() {
151   assert(Tracking && "Cannot unprocess because we're not tracking");
152 
153   MachineInstr *MI = MBBI;
154   if (!MI->isDebugValue()) {
155     determineKillsAndDefs();
156 
157     // Commit the changes.
158     setUsed(KillRegUnits);
159     setUnused(DefRegUnits);
160   }
161 
162   if (MBBI == MBB->begin()) {
163     MBBI = MachineBasicBlock::iterator(nullptr);
164     Tracking = false;
165   } else
166     --MBBI;
167 }
168 
forward()169 void RegScavenger::forward() {
170   // Move ptr forward.
171   if (!Tracking) {
172     MBBI = MBB->begin();
173     Tracking = true;
174   } else {
175     assert(MBBI != MBB->end() && "Already past the end of the basic block!");
176     MBBI = std::next(MBBI);
177   }
178   assert(MBBI != MBB->end() && "Already at the end of the basic block!");
179 
180   MachineInstr *MI = MBBI;
181 
182   for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(),
183          IE = Scavenged.end(); I != IE; ++I) {
184     if (I->Restore != MI)
185       continue;
186 
187     I->Reg = 0;
188     I->Restore = nullptr;
189   }
190 
191   if (MI->isDebugValue())
192     return;
193 
194   determineKillsAndDefs();
195 
196   // Verify uses and defs.
197 #ifndef NDEBUG
198   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
199     const MachineOperand &MO = MI->getOperand(i);
200     if (!MO.isReg())
201       continue;
202     unsigned Reg = MO.getReg();
203     if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || isReserved(Reg))
204       continue;
205     if (MO.isUse()) {
206       if (MO.isUndef())
207         continue;
208       if (!isRegUsed(Reg)) {
209         // Check if it's partial live: e.g.
210         // D0 = insert_subreg D0<undef>, S0
211         // ... D0
212         // The problem is the insert_subreg could be eliminated. The use of
213         // D0 is using a partially undef value. This is not *incorrect* since
214         // S1 is can be freely clobbered.
215         // Ideally we would like a way to model this, but leaving the
216         // insert_subreg around causes both correctness and performance issues.
217         bool SubUsed = false;
218         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
219           if (isRegUsed(*SubRegs)) {
220             SubUsed = true;
221             break;
222           }
223         bool SuperUsed = false;
224         for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) {
225           if (isRegUsed(*SR)) {
226             SuperUsed = true;
227             break;
228           }
229         }
230         if (!SubUsed && !SuperUsed) {
231           MBB->getParent()->verify(nullptr, "In Register Scavenger");
232           llvm_unreachable("Using an undefined register!");
233         }
234         (void)SubUsed;
235         (void)SuperUsed;
236       }
237     } else {
238       assert(MO.isDef());
239 #if 0
240       // FIXME: Enable this once we've figured out how to correctly transfer
241       // implicit kills during codegen passes like the coalescer.
242       assert((KillRegs.test(Reg) || isUnused(Reg) ||
243               isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
244              "Re-defining a live register!");
245 #endif
246     }
247   }
248 #endif // NDEBUG
249 
250   // Commit the changes.
251   setUnused(KillRegUnits);
252   setUsed(DefRegUnits);
253 }
254 
isRegUsed(unsigned Reg,bool includeReserved) const255 bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const {
256   if (includeReserved && isReserved(Reg))
257     return true;
258   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
259     if (!RegUnitsAvailable.test(*RUI))
260       return true;
261   return false;
262 }
263 
FindUnusedReg(const TargetRegisterClass * RC) const264 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
265   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
266        I != E; ++I)
267     if (!isRegUsed(*I)) {
268       DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) <<
269             "\n");
270       return *I;
271     }
272   return 0;
273 }
274 
275 /// getRegsAvailable - Return all available registers in the register class
276 /// in Mask.
getRegsAvailable(const TargetRegisterClass * RC)277 BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) {
278   BitVector Mask(TRI->getNumRegs());
279   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
280        I != E; ++I)
281     if (!isRegUsed(*I))
282       Mask.set(*I);
283   return Mask;
284 }
285 
286 /// findSurvivorReg - Return the candidate register that is unused for the
287 /// longest after StartMII. UseMI is set to the instruction where the search
288 /// stopped.
289 ///
290 /// No more than InstrLimit instructions are inspected.
291 ///
findSurvivorReg(MachineBasicBlock::iterator StartMI,BitVector & Candidates,unsigned InstrLimit,MachineBasicBlock::iterator & UseMI)292 unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
293                                        BitVector &Candidates,
294                                        unsigned InstrLimit,
295                                        MachineBasicBlock::iterator &UseMI) {
296   int Survivor = Candidates.find_first();
297   assert(Survivor > 0 && "No candidates for scavenging");
298 
299   MachineBasicBlock::iterator ME = MBB->getFirstTerminator();
300   assert(StartMI != ME && "MI already at terminator");
301   MachineBasicBlock::iterator RestorePointMI = StartMI;
302   MachineBasicBlock::iterator MI = StartMI;
303 
304   bool inVirtLiveRange = false;
305   for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
306     if (MI->isDebugValue()) {
307       ++InstrLimit; // Don't count debug instructions
308       continue;
309     }
310     bool isVirtKillInsn = false;
311     bool isVirtDefInsn = false;
312     // Remove any candidates touched by instruction.
313     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
314       const MachineOperand &MO = MI->getOperand(i);
315       if (MO.isRegMask())
316         Candidates.clearBitsNotInMask(MO.getRegMask());
317       if (!MO.isReg() || MO.isUndef() || !MO.getReg())
318         continue;
319       if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
320         if (MO.isDef())
321           isVirtDefInsn = true;
322         else if (MO.isKill())
323           isVirtKillInsn = true;
324         continue;
325       }
326       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
327         Candidates.reset(*AI);
328     }
329     // If we're not in a virtual reg's live range, this is a valid
330     // restore point.
331     if (!inVirtLiveRange) RestorePointMI = MI;
332 
333     // Update whether we're in the live range of a virtual register
334     if (isVirtKillInsn) inVirtLiveRange = false;
335     if (isVirtDefInsn) inVirtLiveRange = true;
336 
337     // Was our survivor untouched by this instruction?
338     if (Candidates.test(Survivor))
339       continue;
340 
341     // All candidates gone?
342     if (Candidates.none())
343       break;
344 
345     Survivor = Candidates.find_first();
346   }
347   // If we ran off the end, that's where we want to restore.
348   if (MI == ME) RestorePointMI = ME;
349   assert (RestorePointMI != StartMI &&
350           "No available scavenger restore location!");
351 
352   // We ran out of candidates, so stop the search.
353   UseMI = RestorePointMI;
354   return Survivor;
355 }
356 
getFrameIndexOperandNum(MachineInstr * MI)357 static unsigned getFrameIndexOperandNum(MachineInstr *MI) {
358   unsigned i = 0;
359   while (!MI->getOperand(i).isFI()) {
360     ++i;
361     assert(i < MI->getNumOperands() &&
362            "Instr doesn't have FrameIndex operand!");
363   }
364   return i;
365 }
366 
scavengeRegister(const TargetRegisterClass * RC,MachineBasicBlock::iterator I,int SPAdj)367 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
368                                         MachineBasicBlock::iterator I,
369                                         int SPAdj) {
370   // Consider all allocatable registers in the register class initially
371   BitVector Candidates =
372     TRI->getAllocatableSet(*I->getParent()->getParent(), RC);
373 
374   // Exclude all the registers being used by the instruction.
375   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
376     MachineOperand &MO = I->getOperand(i);
377     if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
378         !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
379       Candidates.reset(MO.getReg());
380   }
381 
382   // Try to find a register that's unused if there is one, as then we won't
383   // have to spill.
384   BitVector Available = getRegsAvailable(RC);
385   Available &= Candidates;
386   if (Available.any())
387     Candidates = Available;
388 
389   // Find the register whose use is furthest away.
390   MachineBasicBlock::iterator UseMI;
391   unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
392 
393   // If we found an unused register there is no reason to spill it.
394   if (!isRegUsed(SReg)) {
395     DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
396     return SReg;
397   }
398 
399   // Find an available scavenging slot.
400   unsigned SI;
401   for (SI = 0; SI < Scavenged.size(); ++SI)
402     if (Scavenged[SI].Reg == 0)
403       break;
404 
405   if (SI == Scavenged.size()) {
406     // We need to scavenge a register but have no spill slot, the target
407     // must know how to do it (if not, we'll assert below).
408     Scavenged.push_back(ScavengedInfo());
409   }
410 
411   // Avoid infinite regress
412   Scavenged[SI].Reg = SReg;
413 
414   // If the target knows how to save/restore the register, let it do so;
415   // otherwise, use the emergency stack spill slot.
416   if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
417     // Spill the scavenged register before I.
418     assert(Scavenged[SI].FrameIndex >= 0 &&
419            "Cannot scavenge register without an emergency spill slot!");
420     TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex,
421                              RC, TRI);
422     MachineBasicBlock::iterator II = std::prev(I);
423 
424     unsigned FIOperandNum = getFrameIndexOperandNum(II);
425     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
426 
427     // Restore the scavenged register before its use (or first terminator).
428     TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex,
429                               RC, TRI);
430     II = std::prev(UseMI);
431 
432     FIOperandNum = getFrameIndexOperandNum(II);
433     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
434   }
435 
436   Scavenged[SI].Restore = std::prev(UseMI);
437 
438   // Doing this here leads to infinite regress.
439   // Scavenged[SI].Reg = SReg;
440 
441   DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
442         "\n");
443 
444   return SReg;
445 }
446