InlineSpiller.cpp revision a8feeb15c84015b9d3b4cb9acd47f7c6bd5f9ba0
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 "LiveRangeEdit.h" 18#include "SplitKit.h" 19#include "VirtRegMap.h" 20#include "llvm/CodeGen/LiveIntervalAnalysis.h" 21#include "llvm/CodeGen/LiveStackAnalysis.h" 22#include "llvm/CodeGen/MachineFrameInfo.h" 23#include "llvm/CodeGen/MachineFunction.h" 24#include "llvm/CodeGen/MachineLoopInfo.h" 25#include "llvm/CodeGen/MachineRegisterInfo.h" 26#include "llvm/Target/TargetMachine.h" 27#include "llvm/Target/TargetInstrInfo.h" 28#include "llvm/Support/CommandLine.h" 29#include "llvm/Support/Debug.h" 30#include "llvm/Support/raw_ostream.h" 31 32using namespace llvm; 33 34static cl::opt<bool> 35VerifySpills("verify-spills", cl::desc("Verify after each spill/split")); 36 37namespace { 38class InlineSpiller : public Spiller { 39 MachineFunctionPass &pass_; 40 MachineFunction &mf_; 41 LiveIntervals &lis_; 42 LiveStacks &lss_; 43 MachineLoopInfo &loops_; 44 VirtRegMap &vrm_; 45 MachineFrameInfo &mfi_; 46 MachineRegisterInfo &mri_; 47 const TargetInstrInfo &tii_; 48 const TargetRegisterInfo &tri_; 49 const BitVector reserved_; 50 51 SplitAnalysis splitAnalysis_; 52 53 // Variables that are valid during spill(), but used by multiple methods. 54 LiveRangeEdit *edit_; 55 const TargetRegisterClass *rc_; 56 int stackSlot_; 57 58 // Values that failed to remat at some point. 59 SmallPtrSet<VNInfo*, 8> usedValues_; 60 61 ~InlineSpiller() {} 62 63public: 64 InlineSpiller(MachineFunctionPass &pass, 65 MachineFunction &mf, 66 VirtRegMap &vrm) 67 : pass_(pass), 68 mf_(mf), 69 lis_(pass.getAnalysis<LiveIntervals>()), 70 lss_(pass.getAnalysis<LiveStacks>()), 71 loops_(pass.getAnalysis<MachineLoopInfo>()), 72 vrm_(vrm), 73 mfi_(*mf.getFrameInfo()), 74 mri_(mf.getRegInfo()), 75 tii_(*mf.getTarget().getInstrInfo()), 76 tri_(*mf.getTarget().getRegisterInfo()), 77 reserved_(tri_.getReservedRegs(mf_)), 78 splitAnalysis_(mf, lis_, loops_) {} 79 80 void spill(LiveInterval *li, 81 SmallVectorImpl<LiveInterval*> &newIntervals, 82 SmallVectorImpl<LiveInterval*> &spillIs); 83 84 void spill(LiveRangeEdit &); 85 86private: 87 bool split(); 88 89 bool reMaterializeFor(MachineBasicBlock::iterator MI); 90 void reMaterializeAll(); 91 92 bool coalesceStackAccess(MachineInstr *MI); 93 bool foldMemoryOperand(MachineBasicBlock::iterator MI, 94 const SmallVectorImpl<unsigned> &Ops); 95 void insertReload(LiveInterval &NewLI, MachineBasicBlock::iterator MI); 96 void insertSpill(LiveInterval &NewLI, MachineBasicBlock::iterator MI); 97}; 98} 99 100namespace llvm { 101Spiller *createInlineSpiller(MachineFunctionPass &pass, 102 MachineFunction &mf, 103 VirtRegMap &vrm) { 104 return new InlineSpiller(pass, mf, vrm); 105} 106} 107 108/// split - try splitting the current interval into pieces that may allocate 109/// separately. Return true if successful. 110bool InlineSpiller::split() { 111 splitAnalysis_.analyze(&edit_->getParent()); 112 113 // Try splitting around loops. 114 if (const MachineLoop *loop = splitAnalysis_.getBestSplitLoop()) { 115 SplitEditor(splitAnalysis_, lis_, vrm_, *edit_) 116 .splitAroundLoop(loop); 117 return true; 118 } 119 120 // Try splitting into single block intervals. 121 SplitAnalysis::BlockPtrSet blocks; 122 if (splitAnalysis_.getMultiUseBlocks(blocks)) { 123 SplitEditor(splitAnalysis_, lis_, vrm_, *edit_) 124 .splitSingleBlocks(blocks); 125 return true; 126 } 127 128 // Try splitting inside a basic block. 129 if (const MachineBasicBlock *MBB = splitAnalysis_.getBlockForInsideSplit()) { 130 SplitEditor(splitAnalysis_, lis_, vrm_, *edit_) 131 .splitInsideBlock(MBB); 132 return true; 133 } 134 135 return false; 136} 137 138/// reMaterializeFor - Attempt to rematerialize edit_->getReg() before MI instead of 139/// reloading it. 140bool InlineSpiller::reMaterializeFor(MachineBasicBlock::iterator MI) { 141 SlotIndex UseIdx = lis_.getInstructionIndex(MI).getUseIndex(); 142 VNInfo *OrigVNI = edit_->getParent().getVNInfoAt(UseIdx); 143 144 if (!OrigVNI) { 145 DEBUG(dbgs() << "\tadding <undef> flags: "); 146 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 147 MachineOperand &MO = MI->getOperand(i); 148 if (MO.isReg() && MO.isUse() && MO.getReg() == edit_->getReg()) 149 MO.setIsUndef(); 150 } 151 DEBUG(dbgs() << UseIdx << '\t' << *MI); 152 return true; 153 } 154 155 LiveRangeEdit::Remat RM = edit_->canRematerializeAt(OrigVNI, UseIdx, false, 156 lis_); 157 if (!RM) { 158 usedValues_.insert(OrigVNI); 159 DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI); 160 return false; 161 } 162 163 // If the instruction also writes edit_->getReg(), it had better not require 164 // the same register for uses and defs. 165 bool Reads, Writes; 166 SmallVector<unsigned, 8> Ops; 167 tie(Reads, Writes) = MI->readsWritesVirtualRegister(edit_->getReg(), &Ops); 168 if (Writes) { 169 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 170 MachineOperand &MO = MI->getOperand(Ops[i]); 171 if (MO.isUse() ? MI->isRegTiedToDefOperand(Ops[i]) : MO.getSubReg()) { 172 usedValues_.insert(OrigVNI); 173 DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI); 174 return false; 175 } 176 } 177 } 178 179 // Alocate a new register for the remat. 180 LiveInterval &NewLI = edit_->create(mri_, lis_, vrm_); 181 NewLI.markNotSpillable(); 182 183 // Finally we can rematerialize OrigMI before MI. 184 SlotIndex DefIdx = edit_->rematerializeAt(*MI->getParent(), MI, NewLI.reg, RM, 185 lis_, tii_, tri_); 186 DEBUG(dbgs() << "\tremat: " << DefIdx << '\n'); 187 188 // Replace operands 189 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 190 MachineOperand &MO = MI->getOperand(Ops[i]); 191 if (MO.isReg() && MO.isUse() && MO.getReg() == edit_->getReg()) { 192 MO.setReg(NewLI.reg); 193 MO.setIsKill(); 194 } 195 } 196 DEBUG(dbgs() << "\t " << UseIdx << '\t' << *MI); 197 198 VNInfo *DefVNI = NewLI.getNextValue(DefIdx, 0, lis_.getVNInfoAllocator()); 199 NewLI.addRange(LiveRange(DefIdx, UseIdx.getDefIndex(), DefVNI)); 200 DEBUG(dbgs() << "\tinterval: " << NewLI << '\n'); 201 return true; 202} 203 204/// reMaterializeAll - Try to rematerialize as many uses as possible, 205/// and trim the live ranges after. 206void InlineSpiller::reMaterializeAll() { 207 // Do a quick scan of the interval values to find if any are remattable. 208 if (!edit_->anyRematerializable(lis_, tii_, 0)) 209 return; 210 211 usedValues_.clear(); 212 213 // Try to remat before all uses of edit_->getReg(). 214 bool anyRemat = false; 215 for (MachineRegisterInfo::use_nodbg_iterator 216 RI = mri_.use_nodbg_begin(edit_->getReg()); 217 MachineInstr *MI = RI.skipInstruction();) 218 anyRemat |= reMaterializeFor(MI); 219 220 if (!anyRemat) 221 return; 222 223 // Remove any values that were completely rematted. 224 bool anyRemoved = false; 225 for (LiveInterval::vni_iterator I = edit_->getParent().vni_begin(), 226 E = edit_->getParent().vni_end(); I != E; ++I) { 227 VNInfo *VNI = *I; 228 if (VNI->hasPHIKill() || !edit_->didRematerialize(VNI) || 229 usedValues_.count(VNI)) 230 continue; 231 MachineInstr *DefMI = lis_.getInstructionFromIndex(VNI->def); 232 DEBUG(dbgs() << "\tremoving dead def: " << VNI->def << '\t' << *DefMI); 233 lis_.RemoveMachineInstrFromMaps(DefMI); 234 vrm_.RemoveMachineInstrFromMaps(DefMI); 235 DefMI->eraseFromParent(); 236 VNI->def = SlotIndex(); 237 anyRemoved = true; 238 } 239 240 if (!anyRemoved) 241 return; 242 243 // Removing values may cause debug uses where parent is not live. 244 for (MachineRegisterInfo::use_iterator RI = mri_.use_begin(edit_->getReg()); 245 MachineInstr *MI = RI.skipInstruction();) { 246 if (!MI->isDebugValue()) 247 continue; 248 // Try to preserve the debug value if parent is live immediately after it. 249 MachineBasicBlock::iterator NextMI = MI; 250 ++NextMI; 251 if (NextMI != MI->getParent()->end() && !lis_.isNotInMIMap(NextMI)) { 252 SlotIndex Idx = lis_.getInstructionIndex(NextMI); 253 VNInfo *VNI = edit_->getParent().getVNInfoAt(Idx); 254 if (VNI && (VNI->hasPHIKill() || usedValues_.count(VNI))) 255 continue; 256 } 257 DEBUG(dbgs() << "Removing debug info due to remat:" << "\t" << *MI); 258 MI->eraseFromParent(); 259 } 260} 261 262/// If MI is a load or store of stackSlot_, it can be removed. 263bool InlineSpiller::coalesceStackAccess(MachineInstr *MI) { 264 int FI = 0; 265 unsigned reg; 266 if (!(reg = tii_.isLoadFromStackSlot(MI, FI)) && 267 !(reg = tii_.isStoreToStackSlot(MI, FI))) 268 return false; 269 270 // We have a stack access. Is it the right register and slot? 271 if (reg != edit_->getReg() || FI != stackSlot_) 272 return false; 273 274 DEBUG(dbgs() << "Coalescing stack access: " << *MI); 275 lis_.RemoveMachineInstrFromMaps(MI); 276 MI->eraseFromParent(); 277 return true; 278} 279 280/// foldMemoryOperand - Try folding stack slot references in Ops into MI. 281/// Return true on success, and MI will be erased. 282bool InlineSpiller::foldMemoryOperand(MachineBasicBlock::iterator MI, 283 const SmallVectorImpl<unsigned> &Ops) { 284 // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied 285 // operands. 286 SmallVector<unsigned, 8> FoldOps; 287 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 288 unsigned Idx = Ops[i]; 289 MachineOperand &MO = MI->getOperand(Idx); 290 if (MO.isImplicit()) 291 continue; 292 // FIXME: Teach targets to deal with subregs. 293 if (MO.getSubReg()) 294 return false; 295 // Tied use operands should not be passed to foldMemoryOperand. 296 if (!MI->isRegTiedToDefOperand(Idx)) 297 FoldOps.push_back(Idx); 298 } 299 300 MachineInstr *FoldMI = tii_.foldMemoryOperand(MI, FoldOps, stackSlot_); 301 if (!FoldMI) 302 return false; 303 lis_.ReplaceMachineInstrInMaps(MI, FoldMI); 304 vrm_.addSpillSlotUse(stackSlot_, FoldMI); 305 MI->eraseFromParent(); 306 DEBUG(dbgs() << "\tfolded: " << *FoldMI); 307 return true; 308} 309 310/// insertReload - Insert a reload of NewLI.reg before MI. 311void InlineSpiller::insertReload(LiveInterval &NewLI, 312 MachineBasicBlock::iterator MI) { 313 MachineBasicBlock &MBB = *MI->getParent(); 314 SlotIndex Idx = lis_.getInstructionIndex(MI).getDefIndex(); 315 tii_.loadRegFromStackSlot(MBB, MI, NewLI.reg, stackSlot_, rc_, &tri_); 316 --MI; // Point to load instruction. 317 SlotIndex LoadIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex(); 318 vrm_.addSpillSlotUse(stackSlot_, MI); 319 DEBUG(dbgs() << "\treload: " << LoadIdx << '\t' << *MI); 320 VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, 0, 321 lis_.getVNInfoAllocator()); 322 NewLI.addRange(LiveRange(LoadIdx, Idx, LoadVNI)); 323} 324 325/// insertSpill - Insert a spill of NewLI.reg after MI. 326void InlineSpiller::insertSpill(LiveInterval &NewLI, 327 MachineBasicBlock::iterator MI) { 328 MachineBasicBlock &MBB = *MI->getParent(); 329 SlotIndex Idx = lis_.getInstructionIndex(MI).getDefIndex(); 330 tii_.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, stackSlot_, rc_, &tri_); 331 --MI; // Point to store instruction. 332 SlotIndex StoreIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex(); 333 vrm_.addSpillSlotUse(stackSlot_, MI); 334 DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI); 335 VNInfo *StoreVNI = NewLI.getNextValue(Idx, 0, lis_.getVNInfoAllocator()); 336 NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI)); 337} 338 339void InlineSpiller::spill(LiveInterval *li, 340 SmallVectorImpl<LiveInterval*> &newIntervals, 341 SmallVectorImpl<LiveInterval*> &spillIs) { 342 LiveRangeEdit edit(*li, newIntervals, spillIs); 343 spill(edit); 344 if (VerifySpills) 345 mf_.verify(&pass_); 346} 347 348void InlineSpiller::spill(LiveRangeEdit &edit) { 349 edit_ = &edit; 350 DEBUG(dbgs() << "Inline spilling " << edit.getParent() << "\n"); 351 assert(edit.getParent().isSpillable() && 352 "Attempting to spill already spilled value."); 353 assert(!edit.getParent().isStackSlot() && "Trying to spill a stack slot."); 354 355 if (split()) 356 return; 357 358 reMaterializeAll(); 359 360 // Remat may handle everything. 361 if (edit_->getParent().empty()) 362 return; 363 364 rc_ = mri_.getRegClass(edit.getReg()); 365 stackSlot_ = edit.assignStackSlot(vrm_); 366 367 // Update LiveStacks now that we are committed to spilling. 368 LiveInterval &stacklvr = lss_.getOrCreateInterval(stackSlot_, rc_); 369 if (!stacklvr.hasAtLeastOneValue()) 370 stacklvr.getNextValue(SlotIndex(), 0, lss_.getVNInfoAllocator()); 371 stacklvr.MergeRangesInAsValue(edit_->getParent(), stacklvr.getValNumInfo(0)); 372 373 // Iterate over instructions using register. 374 for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(edit.getReg()); 375 MachineInstr *MI = RI.skipInstruction();) { 376 377 // Debug values are not allowed to affect codegen. 378 if (MI->isDebugValue()) { 379 // Modify DBG_VALUE now that the value is in a spill slot. 380 uint64_t Offset = MI->getOperand(1).getImm(); 381 const MDNode *MDPtr = MI->getOperand(2).getMetadata(); 382 DebugLoc DL = MI->getDebugLoc(); 383 if (MachineInstr *NewDV = tii_.emitFrameIndexDebugValue(mf_, stackSlot_, 384 Offset, MDPtr, DL)) { 385 DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); 386 MachineBasicBlock *MBB = MI->getParent(); 387 MBB->insert(MBB->erase(MI), NewDV); 388 } else { 389 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); 390 MI->eraseFromParent(); 391 } 392 continue; 393 } 394 395 // Stack slot accesses may coalesce away. 396 if (coalesceStackAccess(MI)) 397 continue; 398 399 // Analyze instruction. 400 bool Reads, Writes; 401 SmallVector<unsigned, 8> Ops; 402 tie(Reads, Writes) = MI->readsWritesVirtualRegister(edit.getReg(), &Ops); 403 404 // Attempt to fold memory ops. 405 if (foldMemoryOperand(MI, Ops)) 406 continue; 407 408 // Allocate interval around instruction. 409 // FIXME: Infer regclass from instruction alone. 410 LiveInterval &NewLI = edit.create(mri_, lis_, vrm_); 411 NewLI.markNotSpillable(); 412 413 if (Reads) 414 insertReload(NewLI, MI); 415 416 // Rewrite instruction operands. 417 bool hasLiveDef = false; 418 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 419 MachineOperand &MO = MI->getOperand(Ops[i]); 420 MO.setReg(NewLI.reg); 421 if (MO.isUse()) { 422 if (!MI->isRegTiedToDefOperand(Ops[i])) 423 MO.setIsKill(); 424 } else { 425 if (!MO.isDead()) 426 hasLiveDef = true; 427 } 428 } 429 430 // FIXME: Use a second vreg if instruction has no tied ops. 431 if (Writes && hasLiveDef) 432 insertSpill(NewLI, MI); 433 434 DEBUG(dbgs() << "\tinterval: " << NewLI << '\n'); 435 } 436} 437