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