lib/CodeGen/SplitKit.cpp

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