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