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