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