SplitKit.cpp revision 4d440bd786ae4dad7035c30fd09044a9efc8dccd
1//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===// 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// This file contains the SplitAnalysis class as well as mutator functions for 11// live range splitting. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "splitter" 16#include "SplitKit.h" 17#include "VirtRegMap.h" 18#include "llvm/CodeGen/CalcSpillWeights.h" 19#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20#include "llvm/CodeGen/MachineDominators.h" 21#include "llvm/CodeGen/MachineInstrBuilder.h" 22#include "llvm/CodeGen/MachineLoopInfo.h" 23#include "llvm/CodeGen/MachineRegisterInfo.h" 24#include "llvm/Support/CommandLine.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/raw_ostream.h" 27#include "llvm/Target/TargetInstrInfo.h" 28#include "llvm/Target/TargetMachine.h" 29 30using namespace llvm; 31 32static cl::opt<bool> 33AllowSplit("spiller-splits-edges", 34 cl::desc("Allow critical edge splitting during spilling")); 35 36//===----------------------------------------------------------------------===// 37// Split Analysis 38//===----------------------------------------------------------------------===// 39 40SplitAnalysis::SplitAnalysis(const MachineFunction &mf, 41 const LiveIntervals &lis, 42 const MachineLoopInfo &mli) 43 : mf_(mf), 44 lis_(lis), 45 loops_(mli), 46 tii_(*mf.getTarget().getInstrInfo()), 47 curli_(0) {} 48 49void SplitAnalysis::clear() { 50 usingInstrs_.clear(); 51 usingBlocks_.clear(); 52 usingLoops_.clear(); 53 curli_ = 0; 54} 55 56bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) { 57 MachineBasicBlock *T, *F; 58 SmallVector<MachineOperand, 4> Cond; 59 return !tii_.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond); 60} 61 62/// analyzeUses - Count instructions, basic blocks, and loops using curli. 63void SplitAnalysis::analyzeUses() { 64 const MachineRegisterInfo &MRI = mf_.getRegInfo(); 65 for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(curli_->reg); 66 MachineInstr *MI = I.skipInstruction();) { 67 if (MI->isDebugValue() || !usingInstrs_.insert(MI)) 68 continue; 69 MachineBasicBlock *MBB = MI->getParent(); 70 if (usingBlocks_[MBB]++) 71 continue; 72 if (MachineLoop *Loop = loops_.getLoopFor(MBB)) 73 usingLoops_[Loop]++; 74 } 75 DEBUG(dbgs() << " counted " 76 << usingInstrs_.size() << " instrs, " 77 << usingBlocks_.size() << " blocks, " 78 << usingLoops_.size() << " loops.\n"); 79} 80 81/// removeUse - Update statistics by noting that MI no longer uses curli. 82void SplitAnalysis::removeUse(const MachineInstr *MI) { 83 if (!usingInstrs_.erase(MI)) 84 return; 85 86 // Decrement MBB count. 87 const MachineBasicBlock *MBB = MI->getParent(); 88 BlockCountMap::iterator bi = usingBlocks_.find(MBB); 89 assert(bi != usingBlocks_.end() && "MBB missing"); 90 assert(bi->second && "0 count in map"); 91 if (--bi->second) 92 return; 93 // No more uses in MBB. 94 usingBlocks_.erase(bi); 95 96 // Decrement loop count. 97 MachineLoop *Loop = loops_.getLoopFor(MBB); 98 if (!Loop) 99 return; 100 LoopCountMap::iterator li = usingLoops_.find(Loop); 101 assert(li != usingLoops_.end() && "Loop missing"); 102 assert(li->second && "0 count in map"); 103 if (--li->second) 104 return; 105 // No more blocks in Loop. 106 usingLoops_.erase(li); 107} 108 109// Get three sets of basic blocks surrounding a loop: Blocks inside the loop, 110// predecessor blocks, and exit blocks. 111void SplitAnalysis::getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks) { 112 Blocks.clear(); 113 114 // Blocks in the loop. 115 Blocks.Loop.insert(Loop->block_begin(), Loop->block_end()); 116 117 // Predecessor blocks. 118 const MachineBasicBlock *Header = Loop->getHeader(); 119 for (MachineBasicBlock::const_pred_iterator I = Header->pred_begin(), 120 E = Header->pred_end(); I != E; ++I) 121 if (!Blocks.Loop.count(*I)) 122 Blocks.Preds.insert(*I); 123 124 // Exit blocks. 125 for (MachineLoop::block_iterator I = Loop->block_begin(), 126 E = Loop->block_end(); I != E; ++I) { 127 const MachineBasicBlock *MBB = *I; 128 for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), 129 SE = MBB->succ_end(); SI != SE; ++SI) 130 if (!Blocks.Loop.count(*SI)) 131 Blocks.Exits.insert(*SI); 132 } 133} 134 135/// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in 136/// and around the Loop. 137SplitAnalysis::LoopPeripheralUse SplitAnalysis:: 138analyzeLoopPeripheralUse(const SplitAnalysis::LoopBlocks &Blocks) { 139 LoopPeripheralUse use = ContainedInLoop; 140 for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end(); 141 I != E; ++I) { 142 const MachineBasicBlock *MBB = I->first; 143 // Is this a peripheral block? 144 if (use < MultiPeripheral && 145 (Blocks.Preds.count(MBB) || Blocks.Exits.count(MBB))) { 146 if (I->second > 1) use = MultiPeripheral; 147 else use = SinglePeripheral; 148 continue; 149 } 150 // Is it a loop block? 151 if (Blocks.Loop.count(MBB)) 152 continue; 153 // It must be an unrelated block. 154 return OutsideLoop; 155 } 156 return use; 157} 158 159/// getCriticalExits - It may be necessary to partially break critical edges 160/// leaving the loop if an exit block has phi uses of curli. Collect the exit 161/// blocks that need special treatment into CriticalExits. 162void SplitAnalysis::getCriticalExits(const SplitAnalysis::LoopBlocks &Blocks, 163 BlockPtrSet &CriticalExits) { 164 CriticalExits.clear(); 165 166 // A critical exit block contains a phi def of curli, and has a predecessor 167 // that is not in the loop nor a loop predecessor. 168 // For such an exit block, the edges carrying the new variable must be moved 169 // to a new pre-exit block. 170 for (BlockPtrSet::iterator I = Blocks.Exits.begin(), E = Blocks.Exits.end(); 171 I != E; ++I) { 172 const MachineBasicBlock *Succ = *I; 173 SlotIndex SuccIdx = lis_.getMBBStartIdx(Succ); 174 VNInfo *SuccVNI = curli_->getVNInfoAt(SuccIdx); 175 // This exit may not have curli live in at all. No need to split. 176 if (!SuccVNI) 177 continue; 178 // If this is not a PHI def, it is either using a value from before the 179 // loop, or a value defined inside the loop. Both are safe. 180 if (!SuccVNI->isPHIDef() || SuccVNI->def.getBaseIndex() != SuccIdx) 181 continue; 182 // This exit block does have a PHI. Does it also have a predecessor that is 183 // not a loop block or loop predecessor? 184 for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(), 185 PE = Succ->pred_end(); PI != PE; ++PI) { 186 const MachineBasicBlock *Pred = *PI; 187 if (Blocks.Loop.count(Pred) || Blocks.Preds.count(Pred)) 188 continue; 189 // This is a critical exit block, and we need to split the exit edge. 190 CriticalExits.insert(Succ); 191 break; 192 } 193 } 194} 195 196/// canSplitCriticalExits - Return true if it is possible to insert new exit 197/// blocks before the blocks in CriticalExits. 198bool 199SplitAnalysis::canSplitCriticalExits(const SplitAnalysis::LoopBlocks &Blocks, 200 BlockPtrSet &CriticalExits) { 201 // If we don't allow critical edge splitting, require no critical exits. 202 if (!AllowSplit) 203 return CriticalExits.empty(); 204 205 for (BlockPtrSet::iterator I = CriticalExits.begin(), E = CriticalExits.end(); 206 I != E; ++I) { 207 const MachineBasicBlock *Succ = *I; 208 // We want to insert a new pre-exit MBB before Succ, and change all the 209 // in-loop blocks to branch to the pre-exit instead of Succ. 210 // Check that all the in-loop predecessors can be changed. 211 for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(), 212 PE = Succ->pred_end(); PI != PE; ++PI) { 213 const MachineBasicBlock *Pred = *PI; 214 // The external predecessors won't be altered. 215 if (!Blocks.Loop.count(Pred) && !Blocks.Preds.count(Pred)) 216 continue; 217 if (!canAnalyzeBranch(Pred)) 218 return false; 219 } 220 221 // If Succ's layout predecessor falls through, that too must be analyzable. 222 // We need to insert the pre-exit block in the gap. 223 MachineFunction::const_iterator MFI = Succ; 224 if (MFI == mf_.begin()) 225 continue; 226 if (!canAnalyzeBranch(--MFI)) 227 return false; 228 } 229 // No problems found. 230 return true; 231} 232 233void SplitAnalysis::analyze(const LiveInterval *li) { 234 clear(); 235 curli_ = li; 236 analyzeUses(); 237} 238 239const MachineLoop *SplitAnalysis::getBestSplitLoop() { 240 assert(curli_ && "Call analyze() before getBestSplitLoop"); 241 if (usingLoops_.empty()) 242 return 0; 243 244 LoopPtrSet Loops, SecondLoops; 245 LoopBlocks Blocks; 246 BlockPtrSet CriticalExits; 247 248 // Find first-class and second class candidate loops. 249 // We prefer to split around loops where curli is used outside the periphery. 250 for (LoopCountMap::const_iterator I = usingLoops_.begin(), 251 E = usingLoops_.end(); I != E; ++I) { 252 const MachineLoop *Loop = I->first; 253 getLoopBlocks(Loop, Blocks); 254 255 // FIXME: We need an SSA updater to properly handle multiple exit blocks. 256 if (Blocks.Exits.size() > 1) { 257 DEBUG(dbgs() << " multiple exits from " << *Loop); 258 continue; 259 } 260 261 LoopPtrSet *LPS = 0; 262 switch(analyzeLoopPeripheralUse(Blocks)) { 263 case OutsideLoop: 264 LPS = &Loops; 265 break; 266 case MultiPeripheral: 267 LPS = &SecondLoops; 268 break; 269 case ContainedInLoop: 270 DEBUG(dbgs() << " contained in " << *Loop); 271 continue; 272 case SinglePeripheral: 273 DEBUG(dbgs() << " single peripheral use in " << *Loop); 274 continue; 275 } 276 // Will it be possible to split around this loop? 277 getCriticalExits(Blocks, CriticalExits); 278 DEBUG(dbgs() << " " << CriticalExits.size() << " critical exits from " 279 << *Loop); 280 if (!canSplitCriticalExits(Blocks, CriticalExits)) 281 continue; 282 // This is a possible split. 283 assert(LPS); 284 LPS->insert(Loop); 285 } 286 287 DEBUG(dbgs() << " getBestSplitLoop found " << Loops.size() << " + " 288 << SecondLoops.size() << " candidate loops.\n"); 289 290 // If there are no first class loops available, look at second class loops. 291 if (Loops.empty()) 292 Loops = SecondLoops; 293 294 if (Loops.empty()) 295 return 0; 296 297 // Pick the earliest loop. 298 // FIXME: Are there other heuristics to consider? 299 const MachineLoop *Best = 0; 300 SlotIndex BestIdx; 301 for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E; 302 ++I) { 303 SlotIndex Idx = lis_.getMBBStartIdx((*I)->getHeader()); 304 if (!Best || Idx < BestIdx) 305 Best = *I, BestIdx = Idx; 306 } 307 DEBUG(dbgs() << " getBestSplitLoop found " << *Best); 308 return Best; 309} 310 311/// getMultiUseBlocks - if curli has more than one use in a basic block, it 312/// may be an advantage to split curli for the duration of the block. 313bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) { 314 // If curli is local to one block, there is no point to splitting it. 315 if (usingBlocks_.size() <= 1) 316 return false; 317 // Add blocks with multiple uses. 318 for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end(); 319 I != E; ++I) 320 switch (I->second) { 321 case 0: 322 case 1: 323 continue; 324 case 2: { 325 // It doesn't pay to split a 2-instr block if it redefines curli. 326 VNInfo *VN1 = curli_->getVNInfoAt(lis_.getMBBStartIdx(I->first)); 327 VNInfo *VN2 = 328 curli_->getVNInfoAt(lis_.getMBBEndIdx(I->first).getPrevIndex()); 329 // live-in and live-out with a different value. 330 if (VN1 && VN2 && VN1 != VN2) 331 continue; 332 } // Fall through. 333 default: 334 Blocks.insert(I->first); 335 } 336 return !Blocks.empty(); 337} 338 339//===----------------------------------------------------------------------===// 340// LiveIntervalMap 341//===----------------------------------------------------------------------===// 342 343// defValue - Introduce a li_ def for ParentVNI that could be later than 344// ParentVNI->def. 345VNInfo *LiveIntervalMap::defValue(const VNInfo *ParentVNI, SlotIndex Idx) { 346 assert(ParentVNI && "Mapping NULL value"); 347 assert(Idx.isValid() && "Invalid SlotIndex"); 348 assert(parentli_.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI"); 349 350 // Is this a simple 1-1 mapping? Not likely. 351 if (Idx == ParentVNI->def) 352 return mapValue(ParentVNI, Idx); 353 354 // This is a complex def. Mark with a NULL in valueMap. 355 VNInfo *OldVNI = 356 valueMap_.insert(ValueMap::value_type(ParentVNI, 0)).first->second; 357 (void)OldVNI; 358 assert(OldVNI == 0 && "Simple/Complex values mixed"); 359 360 // Should we insert a minimal snippet of VNI LiveRange, or can we count on 361 // callers to do that? We need it for lookups of complex values. 362 VNInfo *VNI = li_.getNextValue(Idx, 0, true, lis_.getVNInfoAllocator()); 363 return VNI; 364} 365 366// mapValue - Find the mapped value for ParentVNI at Idx. 367// Potentially create phi-def values. 368VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx) { 369 assert(ParentVNI && "Mapping NULL value"); 370 assert(Idx.isValid() && "Invalid SlotIndex"); 371 assert(parentli_.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI"); 372 373 // Use insert for lookup, so we can add missing values with a second lookup. 374 std::pair<ValueMap::iterator,bool> InsP = 375 valueMap_.insert(ValueMap::value_type(ParentVNI, 0)); 376 377 // This was an unknown value. Create a simple mapping. 378 if (InsP.second) 379 return InsP.first->second = li_.createValueCopy(ParentVNI, 380 lis_.getVNInfoAllocator()); 381 // This was a simple mapped value. 382 if (InsP.first->second) 383 return InsP.first->second; 384 385 // This is a complex mapped value. There may be multiple defs, and we may need 386 // to create phi-defs. 387 MachineBasicBlock *IdxMBB = lis_.getMBBFromIndex(Idx); 388 assert(IdxMBB && "No MBB at Idx"); 389 390 // Is there a def in the same MBB we can extend? 391 if (VNInfo *VNI = extendTo(IdxMBB, Idx)) 392 return VNI; 393 394 // Now for the fun part. We know that ParentVNI potentially has multiple defs, 395 // and we may need to create even more phi-defs to preserve VNInfo SSA form. 396 // Perform a depth-first search for predecessor blocks where we know the 397 // dominating VNInfo. Insert phi-def VNInfos along the path back to IdxMBB. 398 399 // Track MBBs where we have created or learned the dominating value. 400 // This may change during the DFS as we create new phi-defs. 401 typedef DenseMap<MachineBasicBlock*, VNInfo*> MBBValueMap; 402 MBBValueMap DomValue; 403 404 for (idf_iterator<MachineBasicBlock*> 405 IDFI = idf_begin(IdxMBB), 406 IDFE = idf_end(IdxMBB); IDFI != IDFE;) { 407 MachineBasicBlock *MBB = *IDFI; 408 SlotIndex End = lis_.getMBBEndIdx(MBB); 409 410 // We are operating on the restricted CFG where ParentVNI is live. 411 if (parentli_.getVNInfoAt(End.getPrevSlot()) != ParentVNI) { 412 IDFI.skipChildren(); 413 continue; 414 } 415 416 // Do we have a dominating value in this block? 417 VNInfo *VNI = extendTo(MBB, End); 418 if (!VNI) { 419 ++IDFI; 420 continue; 421 } 422 423 // Yes, VNI dominates MBB. Track the path back to IdxMBB, creating phi-defs 424 // as needed along the way. 425 for (unsigned PI = IDFI.getPathLength()-1; PI != 0; --PI) { 426 // Start from MBB's immediate successor. 427 MachineBasicBlock *Succ = IDFI.getPath(PI-1); 428 std::pair<MBBValueMap::iterator, bool> InsP = 429 DomValue.insert(MBBValueMap::value_type(Succ, VNI)); 430 SlotIndex Start = lis_.getMBBStartIdx(Succ); 431 if (InsP.second) { 432 // This is the first time we backtrack to Succ. Verify dominance. 433 if (Succ->pred_size() == 1 || dt_.dominates(MBB, Succ)) 434 continue; 435 } else if (InsP.first->second == VNI || 436 InsP.first->second->def == Start) { 437 // We have previously backtracked VNI to Succ, or Succ already has a 438 // phi-def. No need to backtrack further. 439 break; 440 } 441 // VNI does not dominate Succ, we need a new phi-def. 442 VNI = li_.getNextValue(Start, 0, true, lis_.getVNInfoAllocator()); 443 VNI->setIsPHIDef(true); 444 InsP.first->second = VNI; 445 MBB = Succ; 446 } 447 448 // No need to search the children, we found a dominating value. 449 // MBB is either the found dominating value, or the last phi-def we created. 450 // Either way, the children of MBB would be shadowed, so don't search them. 451 IDFI.skipChildren(MBB); 452 } 453 454 // The search should at least find a dominating value for IdxMBB. 455 assert(!DomValue.empty() && "Couldn't find a reaching definition"); 456 457 // Since we went through the trouble of a full DFS visiting all reaching defs, 458 // the values in DomValue are now accurate. No more phi-defs are needed for 459 // these blocks, so we can color the live ranges. 460 // This makes the next mapValue call much faster. 461 VNInfo *IdxVNI = 0; 462 for (MBBValueMap::iterator I = DomValue.begin(), E = DomValue.end(); I != E; 463 ++I) { 464 MachineBasicBlock *MBB = I->first; 465 VNInfo *VNI = I->second; 466 SlotIndex Start = lis_.getMBBStartIdx(MBB); 467 if (MBB == IdxMBB) { 468 // Don't add full liveness to IdxMBB, stop at Idx. 469 if (Start != Idx) 470 li_.addRange(LiveRange(Start, Idx, VNI)); 471 IdxVNI = VNI; 472 } else 473 li_.addRange(LiveRange(Start, lis_.getMBBEndIdx(MBB), VNI)); 474 } 475 476 assert(IdxVNI && "Didn't find value for Idx"); 477 return IdxVNI; 478} 479 480// extendTo - Find the last li_ value defined in MBB at or before Idx. The 481// parentli_ is assumed to be live at Idx. Extend the live range to Idx. 482// Return the found VNInfo, or NULL. 483VNInfo *LiveIntervalMap::extendTo(MachineBasicBlock *MBB, SlotIndex Idx) { 484 LiveInterval::iterator I = std::upper_bound(li_.begin(), li_.end(), Idx); 485 if (I == li_.begin()) 486 return 0; 487 --I; 488 if (I->start < lis_.getMBBStartIdx(MBB)) 489 return 0; 490 if (I->end < Idx) 491 I->end = Idx; 492 return I->valno; 493} 494 495// addSimpleRange - Add a simple range from parentli_ to li_. 496// ParentVNI must be live in the [Start;End) interval. 497void LiveIntervalMap::addSimpleRange(SlotIndex Start, SlotIndex End, 498 const VNInfo *ParentVNI) { 499 VNInfo *VNI = mapValue(ParentVNI, Start); 500 // A simple mappoing is easy. 501 if (VNI->def == ParentVNI->def) { 502 li_.addRange(LiveRange(Start, End, VNI)); 503 return; 504 } 505 506 // ParentVNI is a complex value. We must map per MBB. 507 MachineFunction::iterator MBB = lis_.getMBBFromIndex(Start); 508 MachineFunction::iterator MBBE = lis_.getMBBFromIndex(End); 509 510 if (MBB == MBBE) { 511 li_.addRange(LiveRange(Start, End, VNI)); 512 return; 513 } 514 515 // First block. 516 li_.addRange(LiveRange(Start, lis_.getMBBEndIdx(MBB), VNI)); 517 518 // Run sequence of full blocks. 519 for (++MBB; MBB != MBBE; ++MBB) { 520 Start = lis_.getMBBStartIdx(MBB); 521 li_.addRange(LiveRange(Start, lis_.getMBBEndIdx(MBB), 522 mapValue(ParentVNI, Start))); 523 } 524 525 // Final block. 526 Start = lis_.getMBBStartIdx(MBB); 527 if (Start != End) 528 li_.addRange(LiveRange(Start, End, mapValue(ParentVNI, Start))); 529} 530 531/// addRange - Add live ranges to li_ where [Start;End) intersects parentli_. 532/// All needed values whose def is not inside [Start;End) must be defined 533/// beforehand so mapValue will work. 534void LiveIntervalMap::addRange(SlotIndex Start, SlotIndex End) { 535 LiveInterval::const_iterator B = parentli_.begin(), E = parentli_.end(); 536 LiveInterval::const_iterator I = std::lower_bound(B, E, Start); 537 538 // Check if --I begins before Start and overlaps. 539 if (I != B) { 540 --I; 541 if (I->end > Start) 542 addSimpleRange(Start, std::min(End, I->end), I->valno); 543 ++I; 544 } 545 546 // The remaining ranges begin after Start. 547 for (;I != E && I->start < End; ++I) 548 addSimpleRange(I->start, std::min(End, I->end), I->valno); 549} 550 551//===----------------------------------------------------------------------===// 552// Split Editor 553//===----------------------------------------------------------------------===// 554 555/// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 556SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm, 557 SmallVectorImpl<LiveInterval*> &intervals) 558 : sa_(sa), lis_(lis), vrm_(vrm), 559 mri_(vrm.getMachineFunction().getRegInfo()), 560 tii_(*vrm.getMachineFunction().getTarget().getInstrInfo()), 561 curli_(sa_.getCurLI()), 562 dupli_(0), openli_(0), 563 intervals_(intervals), 564 firstInterval(intervals_.size()) 565{ 566 assert(curli_ && "SplitEditor created from empty SplitAnalysis"); 567 568 // Make sure curli_ is assigned a stack slot, so all our intervals get the 569 // same slot as curli_. 570 if (vrm_.getStackSlot(curli_->reg) == VirtRegMap::NO_STACK_SLOT) 571 vrm_.assignVirt2StackSlot(curli_->reg); 572 573} 574 575LiveInterval *SplitEditor::createInterval() { 576 unsigned curli = sa_.getCurLI()->reg; 577 unsigned Reg = mri_.createVirtualRegister(mri_.getRegClass(curli)); 578 LiveInterval &Intv = lis_.getOrCreateInterval(Reg); 579 vrm_.grow(); 580 vrm_.assignVirt2StackSlot(Reg, vrm_.getStackSlot(curli)); 581 return &Intv; 582} 583 584LiveInterval *SplitEditor::getDupLI() { 585 if (!dupli_) { 586 // Create an interval for dupli that is a copy of curli. 587 dupli_ = createInterval(); 588 dupli_->Copy(*curli_, &mri_, lis_.getVNInfoAllocator()); 589 } 590 return dupli_; 591} 592 593VNInfo *SplitEditor::mapValue(const VNInfo *curliVNI) { 594 VNInfo *&VNI = valueMap_[curliVNI]; 595 if (!VNI) 596 VNI = openli_->createValueCopy(curliVNI, lis_.getVNInfoAllocator()); 597 return VNI; 598} 599 600/// Insert a COPY instruction curli -> li. Allocate a new value from li 601/// defined by the COPY. Note that rewrite() will deal with the curli 602/// register, so this function can be used to copy from any interval - openli, 603/// curli, or dupli. 604VNInfo *SplitEditor::insertCopy(LiveInterval &LI, 605 MachineBasicBlock &MBB, 606 MachineBasicBlock::iterator I) { 607 MachineInstr *MI = BuildMI(MBB, I, DebugLoc(), tii_.get(TargetOpcode::COPY), 608 LI.reg).addReg(curli_->reg); 609 SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex(); 610 return LI.getNextValue(DefIdx, MI, true, lis_.getVNInfoAllocator()); 611} 612 613/// Create a new virtual register and live interval. 614void SplitEditor::openIntv() { 615 assert(!openli_ && "Previous LI not closed before openIntv"); 616 openli_ = createInterval(); 617 intervals_.push_back(openli_); 618 liveThrough_ = false; 619} 620 621/// enterIntvBefore - Enter openli before the instruction at Idx. If curli is 622/// not live before Idx, a COPY is not inserted. 623void SplitEditor::enterIntvBefore(SlotIndex Idx) { 624 assert(openli_ && "openIntv not called before enterIntvBefore"); 625 626 // Copy from curli_ if it is live. 627 if (VNInfo *CurVNI = curli_->getVNInfoAt(Idx.getUseIndex())) { 628 MachineInstr *MI = lis_.getInstructionFromIndex(Idx); 629 assert(MI && "enterIntvBefore called with invalid index"); 630 VNInfo *VNI = insertCopy(*openli_, *MI->getParent(), MI); 631 openli_->addRange(LiveRange(VNI->def, Idx.getDefIndex(), VNI)); 632 633 // Make sure CurVNI is properly mapped. 634 VNInfo *&mapVNI = valueMap_[CurVNI]; 635 // We dont have SSA update yet, so only one entry per value is allowed. 636 assert(!mapVNI && "enterIntvBefore called more than once for the same value"); 637 mapVNI = VNI; 638 } 639 DEBUG(dbgs() << " enterIntvBefore " << Idx << ": " << *openli_ << '\n'); 640} 641 642/// enterIntvAtEnd - Enter openli at the end of MBB. 643/// PhiMBB is a successor inside openli where a PHI value is created. 644/// Currently, all entries must share the same PhiMBB. 645void SplitEditor::enterIntvAtEnd(MachineBasicBlock &A, MachineBasicBlock &B) { 646 assert(openli_ && "openIntv not called before enterIntvAtEnd"); 647 648 SlotIndex EndA = lis_.getMBBEndIdx(&A); 649 VNInfo *CurVNIA = curli_->getVNInfoAt(EndA.getPrevIndex()); 650 if (!CurVNIA) { 651 DEBUG(dbgs() << " enterIntvAtEnd, curli not live out of BB#" 652 << A.getNumber() << ".\n"); 653 return; 654 } 655 656 // Add a phi kill value and live range out of A. 657 VNInfo *VNIA = insertCopy(*openli_, A, A.getFirstTerminator()); 658 openli_->addRange(LiveRange(VNIA->def, EndA, VNIA)); 659 660 // FIXME: If this is the only entry edge, we don't need the extra PHI value. 661 // FIXME: If there are multiple entry blocks (so not a loop), we need proper 662 // SSA update. 663 664 // Now look at the start of B. 665 SlotIndex StartB = lis_.getMBBStartIdx(&B); 666 SlotIndex EndB = lis_.getMBBEndIdx(&B); 667 const LiveRange *CurB = curli_->getLiveRangeContaining(StartB); 668 if (!CurB) { 669 DEBUG(dbgs() << " enterIntvAtEnd: curli not live in to BB#" 670 << B.getNumber() << ".\n"); 671 return; 672 } 673 674 VNInfo *VNIB = openli_->getVNInfoAt(StartB); 675 if (!VNIB) { 676 // Create a phi value. 677 VNIB = openli_->getNextValue(SlotIndex(StartB, true), 0, false, 678 lis_.getVNInfoAllocator()); 679 VNIB->setIsPHIDef(true); 680 VNInfo *&mapVNI = valueMap_[CurB->valno]; 681 if (mapVNI) { 682 // Multiple copies - must create PHI value. 683 abort(); 684 } else { 685 // This is the first copy of dupLR. Mark the mapping. 686 mapVNI = VNIB; 687 } 688 689 } 690 691 DEBUG(dbgs() << " enterIntvAtEnd: " << *openli_ << '\n'); 692} 693 694/// useIntv - indicate that all instructions in MBB should use openli. 695void SplitEditor::useIntv(const MachineBasicBlock &MBB) { 696 useIntv(lis_.getMBBStartIdx(&MBB), lis_.getMBBEndIdx(&MBB)); 697} 698 699void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { 700 assert(openli_ && "openIntv not called before useIntv"); 701 702 // Map the curli values from the interval into openli_ 703 LiveInterval::const_iterator B = curli_->begin(), E = curli_->end(); 704 LiveInterval::const_iterator I = std::lower_bound(B, E, Start); 705 706 if (I != B) { 707 --I; 708 // I begins before Start, but overlaps. 709 if (I->end > Start) 710 openli_->addRange(LiveRange(Start, std::min(End, I->end), 711 mapValue(I->valno))); 712 ++I; 713 } 714 715 // The remaining ranges begin after Start. 716 for (;I != E && I->start < End; ++I) 717 openli_->addRange(LiveRange(I->start, std::min(End, I->end), 718 mapValue(I->valno))); 719 DEBUG(dbgs() << " use [" << Start << ';' << End << "): " << *openli_ 720 << '\n'); 721} 722 723/// leaveIntvAfter - Leave openli after the instruction at Idx. 724void SplitEditor::leaveIntvAfter(SlotIndex Idx) { 725 assert(openli_ && "openIntv not called before leaveIntvAfter"); 726 727 const LiveRange *CurLR = curli_->getLiveRangeContaining(Idx.getDefIndex()); 728 if (!CurLR || CurLR->end <= Idx.getBoundaryIndex()) { 729 DEBUG(dbgs() << " leaveIntvAfter " << Idx << ": not live\n"); 730 return; 731 } 732 733 // Was this value of curli live through openli? 734 if (!openli_->liveAt(CurLR->valno->def)) { 735 DEBUG(dbgs() << " leaveIntvAfter " << Idx << ": using external value\n"); 736 liveThrough_ = true; 737 return; 738 } 739 740 // We are going to insert a back copy, so we must have a dupli_. 741 LiveRange *DupLR = getDupLI()->getLiveRangeContaining(Idx.getDefIndex()); 742 assert(DupLR && "dupli not live into black, but curli is?"); 743 744 // Insert the COPY instruction. 745 MachineBasicBlock::iterator I = lis_.getInstructionFromIndex(Idx); 746 MachineInstr *MI = BuildMI(*I->getParent(), llvm::next(I), I->getDebugLoc(), 747 tii_.get(TargetOpcode::COPY), dupli_->reg) 748 .addReg(openli_->reg); 749 SlotIndex CopyIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex(); 750 openli_->addRange(LiveRange(Idx.getDefIndex(), CopyIdx, 751 mapValue(CurLR->valno))); 752 DupLR->valno->def = CopyIdx; 753 DEBUG(dbgs() << " leaveIntvAfter " << Idx << ": " << *openli_ << '\n'); 754} 755 756/// leaveIntvAtTop - Leave the interval at the top of MBB. 757/// Currently, only one value can leave the interval. 758void SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { 759 assert(openli_ && "openIntv not called before leaveIntvAtTop"); 760 761 SlotIndex Start = lis_.getMBBStartIdx(&MBB); 762 const LiveRange *CurLR = curli_->getLiveRangeContaining(Start); 763 764 // Is curli even live-in to MBB? 765 if (!CurLR) { 766 DEBUG(dbgs() << " leaveIntvAtTop at " << Start << ": not live\n"); 767 return; 768 } 769 770 // Is curli defined by PHI at the beginning of MBB? 771 bool isPHIDef = CurLR->valno->isPHIDef() && 772 CurLR->valno->def.getBaseIndex() == Start; 773 774 // If MBB is using a value of curli that was defined outside the openli range, 775 // we don't want to copy it back here. 776 if (!isPHIDef && !openli_->liveAt(CurLR->valno->def)) { 777 DEBUG(dbgs() << " leaveIntvAtTop at " << Start 778 << ": using external value\n"); 779 liveThrough_ = true; 780 return; 781 } 782 783 // We are going to insert a back copy, so we must have a dupli_. 784 LiveRange *DupLR = getDupLI()->getLiveRangeContaining(Start); 785 assert(DupLR && "dupli not live into black, but curli is?"); 786 787 // Insert the COPY instruction. 788 MachineInstr *MI = BuildMI(MBB, MBB.begin(), DebugLoc(), 789 tii_.get(TargetOpcode::COPY), dupli_->reg) 790 .addReg(openli_->reg); 791 SlotIndex Idx = lis_.InsertMachineInstrInMaps(MI).getDefIndex(); 792 793 // Adjust dupli and openli values. 794 if (isPHIDef) { 795 // dupli was already a PHI on entry to MBB. Simply insert an openli PHI, 796 // and shift the dupli def down to the COPY. 797 VNInfo *VNI = openli_->getNextValue(SlotIndex(Start, true), 0, false, 798 lis_.getVNInfoAllocator()); 799 VNI->setIsPHIDef(true); 800 openli_->addRange(LiveRange(VNI->def, Idx, VNI)); 801 802 dupli_->removeRange(Start, Idx); 803 DupLR->valno->def = Idx; 804 DupLR->valno->setIsPHIDef(false); 805 } else { 806 // The dupli value was defined somewhere inside the openli range. 807 DEBUG(dbgs() << " leaveIntvAtTop source value defined at " 808 << DupLR->valno->def << "\n"); 809 // FIXME: We may not need a PHI here if all predecessors have the same 810 // value. 811 VNInfo *VNI = openli_->getNextValue(SlotIndex(Start, true), 0, false, 812 lis_.getVNInfoAllocator()); 813 VNI->setIsPHIDef(true); 814 openli_->addRange(LiveRange(VNI->def, Idx, VNI)); 815 816 // FIXME: What if DupLR->valno is used by multiple exits? SSA Update. 817 818 // closeIntv is going to remove the superfluous live ranges. 819 DupLR->valno->def = Idx; 820 DupLR->valno->setIsPHIDef(false); 821 } 822 823 DEBUG(dbgs() << " leaveIntvAtTop at " << Idx << ": " << *openli_ << '\n'); 824} 825 826/// closeIntv - Indicate that we are done editing the currently open 827/// LiveInterval, and ranges can be trimmed. 828void SplitEditor::closeIntv() { 829 assert(openli_ && "openIntv not called before closeIntv"); 830 831 DEBUG(dbgs() << " closeIntv cleaning up\n"); 832 DEBUG(dbgs() << " open " << *openli_ << '\n'); 833 834 if (liveThrough_) { 835 DEBUG(dbgs() << " value live through region, leaving dupli as is.\n"); 836 } else { 837 // live out with copies inserted, or killed by region. Either way we need to 838 // remove the overlapping region from dupli. 839 getDupLI(); 840 for (LiveInterval::iterator I = openli_->begin(), E = openli_->end(); 841 I != E; ++I) { 842 dupli_->removeRange(I->start, I->end); 843 } 844 // FIXME: A block branching to the entry block may also branch elsewhere 845 // curli is live. We need both openli and curli to be live in that case. 846 DEBUG(dbgs() << " dup2 " << *dupli_ << '\n'); 847 } 848 openli_ = 0; 849 valueMap_.clear(); 850} 851 852/// rewrite - after all the new live ranges have been created, rewrite 853/// instructions using curli to use the new intervals. 854void SplitEditor::rewrite() { 855 assert(!openli_ && "Previous LI not closed before rewrite"); 856 const LiveInterval *curli = sa_.getCurLI(); 857 for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(curli->reg), 858 RE = mri_.reg_end(); RI != RE;) { 859 MachineOperand &MO = RI.getOperand(); 860 MachineInstr *MI = MO.getParent(); 861 ++RI; 862 if (MI->isDebugValue()) { 863 DEBUG(dbgs() << "Zapping " << *MI); 864 // FIXME: We can do much better with debug values. 865 MO.setReg(0); 866 continue; 867 } 868 SlotIndex Idx = lis_.getInstructionIndex(MI); 869 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 870 LiveInterval *LI = dupli_; 871 for (unsigned i = firstInterval, e = intervals_.size(); i != e; ++i) { 872 LiveInterval *testli = intervals_[i]; 873 if (testli->liveAt(Idx)) { 874 LI = testli; 875 break; 876 } 877 } 878 if (LI) { 879 MO.setReg(LI->reg); 880 sa_.removeUse(MI); 881 DEBUG(dbgs() << " rewrite " << Idx << '\t' << *MI); 882 } 883 } 884 885 // dupli_ goes in last, after rewriting. 886 if (dupli_) { 887 if (dupli_->empty()) { 888 DEBUG(dbgs() << " dupli became empty?\n"); 889 lis_.removeInterval(dupli_->reg); 890 dupli_ = 0; 891 } else { 892 dupli_->RenumberValues(lis_); 893 intervals_.push_back(dupli_); 894 } 895 } 896 897 // Calculate spill weight and allocation hints for new intervals. 898 VirtRegAuxInfo vrai(vrm_.getMachineFunction(), lis_, sa_.loops_); 899 for (unsigned i = firstInterval, e = intervals_.size(); i != e; ++i) { 900 LiveInterval &li = *intervals_[i]; 901 vrai.CalculateRegClass(li.reg); 902 vrai.CalculateWeightAndHint(li); 903 DEBUG(dbgs() << " new interval " << mri_.getRegClass(li.reg)->getName() 904 << ":" << li << '\n'); 905 } 906} 907 908 909//===----------------------------------------------------------------------===// 910// Loop Splitting 911//===----------------------------------------------------------------------===// 912 913bool SplitEditor::splitAroundLoop(const MachineLoop *Loop) { 914 SplitAnalysis::LoopBlocks Blocks; 915 sa_.getLoopBlocks(Loop, Blocks); 916 917 // Break critical edges as needed. 918 SplitAnalysis::BlockPtrSet CriticalExits; 919 sa_.getCriticalExits(Blocks, CriticalExits); 920 assert(CriticalExits.empty() && "Cannot break critical exits yet"); 921 922 // Create new live interval for the loop. 923 openIntv(); 924 925 // Insert copies in the predecessors. 926 for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Preds.begin(), 927 E = Blocks.Preds.end(); I != E; ++I) { 928 MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I); 929 enterIntvAtEnd(MBB, *Loop->getHeader()); 930 } 931 932 // Switch all loop blocks. 933 for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Loop.begin(), 934 E = Blocks.Loop.end(); I != E; ++I) 935 useIntv(**I); 936 937 // Insert back copies in the exit blocks. 938 for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Exits.begin(), 939 E = Blocks.Exits.end(); I != E; ++I) { 940 MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I); 941 leaveIntvAtTop(MBB); 942 } 943 944 // Done. 945 closeIntv(); 946 rewrite(); 947 return dupli_; 948} 949 950 951//===----------------------------------------------------------------------===// 952// Single Block Splitting 953//===----------------------------------------------------------------------===// 954 955/// splitSingleBlocks - Split curli into a separate live interval inside each 956/// basic block in Blocks. Return true if curli has been completely replaced, 957/// false if curli is still intact, and needs to be spilled or split further. 958bool SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) { 959 DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n"); 960 // Determine the first and last instruction using curli in each block. 961 typedef std::pair<SlotIndex,SlotIndex> IndexPair; 962 typedef DenseMap<const MachineBasicBlock*,IndexPair> IndexPairMap; 963 IndexPairMap MBBRange; 964 for (SplitAnalysis::InstrPtrSet::const_iterator I = sa_.usingInstrs_.begin(), 965 E = sa_.usingInstrs_.end(); I != E; ++I) { 966 const MachineBasicBlock *MBB = (*I)->getParent(); 967 if (!Blocks.count(MBB)) 968 continue; 969 SlotIndex Idx = lis_.getInstructionIndex(*I); 970 DEBUG(dbgs() << " BB#" << MBB->getNumber() << '\t' << Idx << '\t' << **I); 971 IndexPair &IP = MBBRange[MBB]; 972 if (!IP.first.isValid() || Idx < IP.first) 973 IP.first = Idx; 974 if (!IP.second.isValid() || Idx > IP.second) 975 IP.second = Idx; 976 } 977 978 // Create a new interval for each block. 979 for (SplitAnalysis::BlockPtrSet::const_iterator I = Blocks.begin(), 980 E = Blocks.end(); I != E; ++I) { 981 IndexPair &IP = MBBRange[*I]; 982 DEBUG(dbgs() << " splitting for BB#" << (*I)->getNumber() << ": [" 983 << IP.first << ';' << IP.second << ")\n"); 984 assert(IP.first.isValid() && IP.second.isValid()); 985 986 openIntv(); 987 enterIntvBefore(IP.first); 988 useIntv(IP.first.getBaseIndex(), IP.second.getBoundaryIndex()); 989 leaveIntvAfter(IP.second); 990 closeIntv(); 991 } 992 rewrite(); 993 return dupli_; 994} 995 996 997//===----------------------------------------------------------------------===// 998// Sub Block Splitting 999//===----------------------------------------------------------------------===// 1000 1001/// getBlockForInsideSplit - If curli is contained inside a single basic block, 1002/// and it wou pay to subdivide the interval inside that block, return it. 1003/// Otherwise return NULL. The returned block can be passed to 1004/// SplitEditor::splitInsideBlock. 1005const MachineBasicBlock *SplitAnalysis::getBlockForInsideSplit() { 1006 // The interval must be exclusive to one block. 1007 if (usingBlocks_.size() != 1) 1008 return 0; 1009 // Don't to this for less than 4 instructions. We want to be sure that 1010 // splitting actually reduces the instruction count per interval. 1011 if (usingInstrs_.size() < 4) 1012 return 0; 1013 return usingBlocks_.begin()->first; 1014} 1015 1016/// splitInsideBlock - Split curli into multiple intervals inside MBB. Return 1017/// true if curli has been completely replaced, false if curli is still 1018/// intact, and needs to be spilled or split further. 1019bool SplitEditor::splitInsideBlock(const MachineBasicBlock *MBB) { 1020 SmallVector<SlotIndex, 32> Uses; 1021 Uses.reserve(sa_.usingInstrs_.size()); 1022 for (SplitAnalysis::InstrPtrSet::const_iterator I = sa_.usingInstrs_.begin(), 1023 E = sa_.usingInstrs_.end(); I != E; ++I) 1024 if ((*I)->getParent() == MBB) 1025 Uses.push_back(lis_.getInstructionIndex(*I)); 1026 DEBUG(dbgs() << " splitInsideBlock BB#" << MBB->getNumber() << " for " 1027 << Uses.size() << " instructions.\n"); 1028 assert(Uses.size() >= 3 && "Need at least 3 instructions"); 1029 array_pod_sort(Uses.begin(), Uses.end()); 1030 1031 // Simple algorithm: Find the largest gap between uses as determined by slot 1032 // indices. Create new intervals for instructions before the gap and after the 1033 // gap. 1034 unsigned bestPos = 0; 1035 int bestGap = 0; 1036 DEBUG(dbgs() << " dist (" << Uses[0]); 1037 for (unsigned i = 1, e = Uses.size(); i != e; ++i) { 1038 int g = Uses[i-1].distance(Uses[i]); 1039 DEBUG(dbgs() << ") -" << g << "- (" << Uses[i]); 1040 if (g > bestGap) 1041 bestPos = i, bestGap = g; 1042 } 1043 DEBUG(dbgs() << "), best: -" << bestGap << "-\n"); 1044 1045 // bestPos points to the first use after the best gap. 1046 assert(bestPos > 0 && "Invalid gap"); 1047 1048 // FIXME: Don't create intervals for low densities. 1049 1050 // First interval before the gap. Don't create single-instr intervals. 1051 if (bestPos > 1) { 1052 openIntv(); 1053 enterIntvBefore(Uses.front()); 1054 useIntv(Uses.front().getBaseIndex(), Uses[bestPos-1].getBoundaryIndex()); 1055 leaveIntvAfter(Uses[bestPos-1]); 1056 closeIntv(); 1057 } 1058 1059 // Second interval after the gap. 1060 if (bestPos < Uses.size()-1) { 1061 openIntv(); 1062 enterIntvBefore(Uses[bestPos]); 1063 useIntv(Uses[bestPos].getBaseIndex(), Uses.back().getBoundaryIndex()); 1064 leaveIntvAfter(Uses.back()); 1065 closeIntv(); 1066 } 1067 1068 rewrite(); 1069 return dupli_; 1070} 1071