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