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