1 //===-------- InlineSpiller.cpp - Insert spills and restores inline -------===// 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 // The inline spiller modifies the machine function directly instead of 11 // inserting spills and restores in VirtRegMap. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #define DEBUG_TYPE "spiller" 16 #include "Spiller.h" 17 #include "VirtRegMap.h" 18 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 19 #include "llvm/CodeGen/MachineFrameInfo.h" 20 #include "llvm/CodeGen/MachineFunction.h" 21 #include "llvm/CodeGen/MachineRegisterInfo.h" 22 #include "llvm/Target/TargetMachine.h" 23 #include "llvm/Target/TargetInstrInfo.h" 24 #include "llvm/Support/Debug.h" 25 #include "llvm/Support/raw_ostream.h" 26 27 using namespace llvm; 28 29 namespace { 30 class InlineSpiller : public Spiller { 31 MachineFunction &mf_; 32 LiveIntervals &lis_; 33 VirtRegMap &vrm_; 34 MachineFrameInfo &mfi_; 35 MachineRegisterInfo &mri_; 36 const TargetInstrInfo &tii_; 37 const TargetRegisterInfo &tri_; 38 const BitVector reserved_; 39 40 // Variables that are valid during spill(), but used by multiple methods. 41 LiveInterval *li_; 42 const TargetRegisterClass *rc_; 43 int stackSlot_; 44 const SmallVectorImpl<LiveInterval*> *spillIs_; 45 46 ~InlineSpiller() {} 47 48 public: 49 InlineSpiller(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm) 50 : mf_(*mf), lis_(*lis), vrm_(*vrm), 51 mfi_(*mf->getFrameInfo()), 52 mri_(mf->getRegInfo()), 53 tii_(*mf->getTarget().getInstrInfo()), 54 tri_(*mf->getTarget().getRegisterInfo()), 55 reserved_(tri_.getReservedRegs(mf_)) {} 56 57 void spill(LiveInterval *li, 58 std::vector<LiveInterval*> &newIntervals, 59 SmallVectorImpl<LiveInterval*> &spillIs, 60 SlotIndex *earliestIndex); 61 bool reMaterialize(LiveInterval &NewLI, MachineBasicBlock::iterator MI); 62 void insertReload(LiveInterval &NewLI, MachineBasicBlock::iterator MI); 63 void insertSpill(LiveInterval &NewLI, MachineBasicBlock::iterator MI); 64 }; 65 } 66 67 namespace llvm { 68 Spiller *createInlineSpiller(MachineFunction *mf, 69 LiveIntervals *lis, 70 const MachineLoopInfo *mli, 71 VirtRegMap *vrm) { 72 return new InlineSpiller(mf, lis, vrm); 73 } 74 } 75 76 /// reMaterialize - Attempt to rematerialize li_->reg before MI instead of 77 /// reloading it. 78 bool InlineSpiller::reMaterialize(LiveInterval &NewLI, 79 MachineBasicBlock::iterator MI) { 80 SlotIndex UseIdx = lis_.getInstructionIndex(MI).getUseIndex(); 81 LiveRange *LR = li_->getLiveRangeContaining(UseIdx); 82 if (!LR) { 83 DEBUG(dbgs() << "\tundef at " << UseIdx << ", adding <undef> flags.\n"); 84 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 85 MachineOperand &MO = MI->getOperand(i); 86 if (MO.isReg() && MO.isUse() && MO.getReg() == li_->reg) 87 MO.setIsUndef(); 88 } 89 return true; 90 } 91 92 // Find the instruction that defined this value of li_->reg. 93 if (!LR->valno->isDefAccurate()) 94 return false; 95 SlotIndex OrigDefIdx = LR->valno->def; 96 MachineInstr *OrigDefMI = lis_.getInstructionFromIndex(OrigDefIdx); 97 if (!OrigDefMI) 98 return false; 99 100 // FIXME: Provide AliasAnalysis argument. 101 if (!tii_.isTriviallyReMaterializable(OrigDefMI)) 102 return false; 103 104 // A rematerializable instruction may be using other virtual registers. 105 // Make sure they are available at the new location. 106 for (unsigned i = 0, e = OrigDefMI->getNumOperands(); i != e; ++i) { 107 MachineOperand &MO = OrigDefMI->getOperand(i); 108 if (!MO.isReg() || !MO.getReg() || MO.getReg() == li_->reg) 109 continue; 110 // Reserved physregs are OK. Others are not (probably from coalescing). 111 if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 112 if (reserved_.test(MO.getReg())) 113 continue; 114 else 115 return false; 116 } 117 // We don't want to move any virtual defs. 118 if (MO.isDef()) 119 return false; 120 // We have a use of a virtual register other than li_->reg. 121 if (MO.isUndef()) 122 continue; 123 // We cannot depend on virtual registers in spillIs_. They will be spilled. 124 for (unsigned si = 0, se = spillIs_->size(); si != se; ++si) 125 if ((*spillIs_)[si]->reg == MO.getReg()) 126 return false; 127 128 // Is the register available here with the same value as at OrigDefMI? 129 LiveInterval &ULI = lis_.getInterval(MO.getReg()); 130 LiveRange *HereLR = ULI.getLiveRangeContaining(UseIdx); 131 if (!HereLR) 132 return false; 133 LiveRange *DefLR = ULI.getLiveRangeContaining(OrigDefIdx.getUseIndex()); 134 if (!DefLR || DefLR->valno != HereLR->valno) 135 return false; 136 } 137 138 // Finally we can rematerialize OrigDefMI before MI. 139 MachineBasicBlock &MBB = *MI->getParent(); 140 tii_.reMaterialize(MBB, MI, NewLI.reg, 0, OrigDefMI, tri_); 141 SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(--MI).getDefIndex(); 142 DEBUG(dbgs() << "\tremat: " << DefIdx << '\t' << *MI); 143 VNInfo *DefVNI = NewLI.getNextValue(DefIdx, 0, true, 144 lis_.getVNInfoAllocator()); 145 NewLI.addRange(LiveRange(DefIdx, UseIdx.getDefIndex(), DefVNI)); 146 return true; 147 } 148 149 /// insertReload - Insert a reload of NewLI.reg before MI. 150 void InlineSpiller::insertReload(LiveInterval &NewLI, 151 MachineBasicBlock::iterator MI) { 152 MachineBasicBlock &MBB = *MI->getParent(); 153 SlotIndex Idx = lis_.getInstructionIndex(MI).getDefIndex(); 154 tii_.loadRegFromStackSlot(MBB, MI, NewLI.reg, stackSlot_, rc_, &tri_); 155 --MI; // Point to load instruction. 156 SlotIndex LoadIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex(); 157 vrm_.addSpillSlotUse(stackSlot_, MI); 158 DEBUG(dbgs() << "\treload: " << LoadIdx << '\t' << *MI); 159 VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, 0, true, 160 lis_.getVNInfoAllocator()); 161 NewLI.addRange(LiveRange(LoadIdx, Idx, LoadVNI)); 162 } 163 164 /// insertSpill - Insert a spill of NewLI.reg after MI. 165 void InlineSpiller::insertSpill(LiveInterval &NewLI, 166 MachineBasicBlock::iterator MI) { 167 MachineBasicBlock &MBB = *MI->getParent(); 168 SlotIndex Idx = lis_.getInstructionIndex(MI).getDefIndex(); 169 tii_.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, stackSlot_, rc_, &tri_); 170 --MI; // Point to store instruction. 171 SlotIndex StoreIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex(); 172 vrm_.addSpillSlotUse(stackSlot_, MI); 173 DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI); 174 VNInfo *StoreVNI = NewLI.getNextValue(Idx, 0, true, 175 lis_.getVNInfoAllocator()); 176 NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI)); 177 } 178 179 void InlineSpiller::spill(LiveInterval *li, 180 std::vector<LiveInterval*> &newIntervals, 181 SmallVectorImpl<LiveInterval*> &spillIs, 182 SlotIndex *earliestIndex) { 183 DEBUG(dbgs() << "Inline spilling " << *li << "\n"); 184 assert(li->isSpillable() && "Attempting to spill already spilled value."); 185 assert(!li->isStackSlot() && "Trying to spill a stack slot."); 186 187 li_ = li; 188 rc_ = mri_.getRegClass(li->reg); 189 stackSlot_ = vrm_.assignVirt2StackSlot(li->reg); 190 spillIs_ = &spillIs; 191 192 // Iterate over instructions using register. 193 for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(li->reg); 194 MachineInstr *MI = RI.skipInstruction();) { 195 196 // Analyze instruction. 197 bool Reads, Writes; 198 SmallVector<unsigned, 8> Ops; 199 tie(Reads, Writes) = MI->readsWritesVirtualRegister(li->reg, &Ops); 200 201 // Allocate interval around instruction. 202 // FIXME: Infer regclass from instruction alone. 203 unsigned NewVReg = mri_.createVirtualRegister(rc_); 204 vrm_.grow(); 205 LiveInterval &NewLI = lis_.getOrCreateInterval(NewVReg); 206 NewLI.markNotSpillable(); 207 208 // Attempt remat instead of reload. 209 bool NeedsReload = Reads && !reMaterialize(NewLI, MI); 210 211 if (NeedsReload) 212 insertReload(NewLI, MI); 213 214 // Rewrite instruction operands. 215 bool hasLiveDef = false; 216 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 217 MachineOperand &MO = MI->getOperand(Ops[i]); 218 MO.setReg(NewVReg); 219 if (MO.isUse()) { 220 if (!MI->isRegTiedToDefOperand(Ops[i])) 221 MO.setIsKill(); 222 } else { 223 if (!MO.isDead()) 224 hasLiveDef = true; 225 } 226 } 227 228 // FIXME: Use a second vreg if instruction has no tied ops. 229 if (Writes && hasLiveDef) 230 insertSpill(NewLI, MI); 231 232 DEBUG(dbgs() << "\tinterval: " << NewLI << '\n'); 233 newIntervals.push_back(&NewLI); 234 } 235 } 236