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 "regalloc"
  16 #include "SplitKit.h"
  17 #include "LiveRangeEdit.h"
  18 #include "VirtRegMap.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  21 #include "llvm/CodeGen/MachineDominators.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/CodeGen/MachineLoopInfo.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.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 STATISTIC(NumFinished, "Number of splits finished");
  33 STATISTIC(NumSimple,   "Number of splits that were simple");
  34 STATISTIC(NumCopies,   "Number of copies inserted for splitting");
  35 STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");
  36 STATISTIC(NumRepairs,  "Number of invalid live ranges repaired");
  37
  38 //===----------------------------------------------------------------------===//
  39 //                                 Split Analysis
  40 //===----------------------------------------------------------------------===//
  41
  42 SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm,
  43                              const LiveIntervals &lis,
  44                              const MachineLoopInfo &mli)
  45   : MF(vrm.getMachineFunction()),
  46     VRM(vrm),
  47     LIS(lis),
  48     Loops(mli),
  49     TII(*MF.getTarget().getInstrInfo()),
  50     CurLI(0),
  51     LastSplitPoint(MF.getNumBlockIDs()) {}
  52
  53 void SplitAnalysis::clear() {
  54   UseSlots.clear();
  55   UseBlocks.clear();
  56   ThroughBlocks.clear();
  57   CurLI = 0;
  58   DidRepairRange = false;
  59 }
  60
  61 SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) {
  62   const MachineBasicBlock *MBB = MF.getBlockNumbered(Num);
  63   const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor();
  64   std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num];
  65
  66   // Compute split points on the first call. The pair is independent of the
  67   // current live interval.
  68   if (!LSP.first.isValid()) {
  69     MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator();
  70     if (FirstTerm == MBB->end())
  71       LSP.first = LIS.getMBBEndIdx(MBB);
  72     else
  73       LSP.first = LIS.getInstructionIndex(FirstTerm);
  74
  75     // If there is a landing pad successor, also find the call instruction.
  76     if (!LPad)
  77       return LSP.first;
  78     // There may not be a call instruction (?) in which case we ignore LPad.
  79     LSP.second = LSP.first;
  80     for (MachineBasicBlock::const_iterator I = MBB->end(), E = MBB->begin();
  81          I != E;) {
  82       --I;
  83       if (I->getDesc().isCall()) {
  84         LSP.second = LIS.getInstructionIndex(I);
  85         break;
  86       }
  87     }
  88   }
  89
  90   // If CurLI is live into a landing pad successor, move the last split point
  91   // back to the call that may throw.
  92   if (LPad && LSP.second.isValid() && LIS.isLiveInToMBB(*CurLI, LPad))
  93     return LSP.second;
  94   else
  95     return LSP.first;
  96 }
  97
  98 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
  99 void SplitAnalysis::analyzeUses() {
 100   assert(UseSlots.empty() && "Call clear first");
 101
 102   // First get all the defs from the interval values. This provides the correct
 103   // slots for early clobbers.
 104   for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(),
 105        E = CurLI->vni_end(); I != E; ++I)
 106     if (!(*I)->isPHIDef() && !(*I)->isUnused())
 107       UseSlots.push_back((*I)->def);
 108
 109   // Get use slots form the use-def chain.
 110   const MachineRegisterInfo &MRI = MF.getRegInfo();
 111   for (MachineRegisterInfo::use_nodbg_iterator
 112        I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E;
 113        ++I)
 114     if (!I.getOperand().isUndef())
 115       UseSlots.push_back(LIS.getInstructionIndex(&*I).getDefIndex());
 116
 117   array_pod_sort(UseSlots.begin(), UseSlots.end());
 118
 119   // Remove duplicates, keeping the smaller slot for each instruction.
 120   // That is what we want for early clobbers.
 121   UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
 122                              SlotIndex::isSameInstr),
 123                  UseSlots.end());
 124
 125   // Compute per-live block info.
 126   if (!calcLiveBlockInfo()) {
 127     // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
 128     // I am looking at you, RegisterCoalescer!
 129     DidRepairRange = true;
 130     ++NumRepairs;
 131     DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
 132     const_cast<LiveIntervals&>(LIS)
 133       .shrinkToUses(const_cast<LiveInterval*>(CurLI));
 134     UseBlocks.clear();
 135     ThroughBlocks.clear();
 136     bool fixed = calcLiveBlockInfo();
 137     (void)fixed;
 138     assert(fixed && "Couldn't fix broken live interval");
 139   }
 140
 141   DEBUG(dbgs() << "Analyze counted "
 142                << UseSlots.size() << " instrs in "
 143                << UseBlocks.size() << " blocks, through "
 144                << NumThroughBlocks << " blocks.\n");
 145 }
 146
 147 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
 148 /// where CurLI is live.
 149 bool SplitAnalysis::calcLiveBlockInfo() {
 150   ThroughBlocks.resize(MF.getNumBlockIDs());
 151   NumThroughBlocks = NumGapBlocks = 0;
 152   if (CurLI->empty())
 153     return true;
 154
 155   LiveInterval::const_iterator LVI = CurLI->begin();
 156   LiveInterval::const_iterator LVE = CurLI->end();
 157
 158   SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
 159   UseI = UseSlots.begin();
 160   UseE = UseSlots.end();
 161
 162   // Loop over basic blocks where CurLI is live.
 163   MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start);
 164   for (;;) {
 165     BlockInfo BI;
 166     BI.MBB = MFI;
 167     SlotIndex Start, Stop;
 168     tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
 169
 170     // If the block contains no uses, the range must be live through. At one
 171     // point, RegisterCoalescer could create dangling ranges that ended
 172     // mid-block.
 173     if (UseI == UseE || *UseI >= Stop) {
 174       ++NumThroughBlocks;
 175       ThroughBlocks.set(BI.MBB->getNumber());
 176       // The range shouldn't end mid-block if there are no uses. This shouldn't
 177       // happen.
 178       if (LVI->end < Stop)
 179         return false;
 180     } else {
 181       // This block has uses. Find the first and last uses in the block.
 182       BI.FirstInstr = *UseI;
 183       assert(BI.FirstInstr >= Start);
 184       do ++UseI;
 185       while (UseI != UseE && *UseI < Stop);
 186       BI.LastInstr = UseI[-1];
 187       assert(BI.LastInstr < Stop);
 188
 189       // LVI is the first live segment overlapping MBB.
 190       BI.LiveIn = LVI->start <= Start;
 191
 192       // When not live in, the first use should be a def.
 193       if (!BI.LiveIn) {
 194         assert(LVI->start == LVI->valno->def && "Dangling LiveRange start");
 195         assert(LVI->start == BI.FirstInstr && "First instr should be a def");
 196         BI.FirstDef = BI.FirstInstr;
 197       }
 198
 199       // Look for gaps in the live range.
 200       BI.LiveOut = true;
 201       while (LVI->end < Stop) {
 202         SlotIndex LastStop = LVI->end;
 203         if (++LVI == LVE || LVI->start >= Stop) {
 204           BI.LiveOut = false;
 205           BI.LastInstr = LastStop;
 206           break;
 207         }
 208
 209         if (LastStop < LVI->start) {
 210           // There is a gap in the live range. Create duplicate entries for the
 211           // live-in snippet and the live-out snippet.
 212           ++NumGapBlocks;
 213
 214           // Push the Live-in part.
 215           BI.LiveOut = false;
 216           UseBlocks.push_back(BI);
 217           UseBlocks.back().LastInstr = LastStop;
 218
 219           // Set up BI for the live-out part.
 220           BI.LiveIn = false;
 221           BI.LiveOut = true;
 222           BI.FirstInstr = BI.FirstDef = LVI->start;
 223         }
 224
 225         // A LiveRange that starts in the middle of the block must be a def.
 226         assert(LVI->start == LVI->valno->def && "Dangling LiveRange start");
 227         if (!BI.FirstDef)
 228           BI.FirstDef = LVI->start;
 229       }
 230
 231       UseBlocks.push_back(BI);
 232
 233       // LVI is now at LVE or LVI->end >= Stop.
 234       if (LVI == LVE)
 235         break;
 236     }
 237
 238     // Live segment ends exactly at Stop. Move to the next segment.
 239     if (LVI->end == Stop && ++LVI == LVE)
 240       break;
 241
 242     // Pick the next basic block.
 243     if (LVI->start < Stop)
 244       ++MFI;
 245     else
 246       MFI = LIS.getMBBFromIndex(LVI->start);
 247   }
 248
 249   assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
 250   return true;
 251 }
 252
 253 unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
 254   if (cli->empty())
 255     return 0;
 256   LiveInterval *li = const_cast<LiveInterval*>(cli);
 257   LiveInterval::iterator LVI = li->begin();
 258   LiveInterval::iterator LVE = li->end();
 259   unsigned Count = 0;
 260
 261   // Loop over basic blocks where li is live.
 262   MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start);
 263   SlotIndex Stop = LIS.getMBBEndIdx(MFI);
 264   for (;;) {
 265     ++Count;
 266     LVI = li->advanceTo(LVI, Stop);
 267     if (LVI == LVE)
 268       return Count;
 269     do {
 270       ++MFI;
 271       Stop = LIS.getMBBEndIdx(MFI);
 272     } while (Stop <= LVI->start);
 273   }
 274 }
 275
 276 bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
 277   unsigned OrigReg = VRM.getOriginal(CurLI->reg);
 278   const LiveInterval &Orig = LIS.getInterval(OrigReg);
 279   assert(!Orig.empty() && "Splitting empty interval?");
 280   LiveInterval::const_iterator I = Orig.find(Idx);
 281
 282   // Range containing Idx should begin at Idx.
 283   if (I != Orig.end() && I->start <= Idx)
 284     return I->start == Idx;
 285
 286   // Range does not contain Idx, previous must end at Idx.
 287   return I != Orig.begin() && (--I)->end == Idx;
 288 }
 289
 290 void SplitAnalysis::analyze(const LiveInterval *li) {
 291   clear();
 292   CurLI = li;
 293   analyzeUses();
 294 }
 295
 296
 297 //===----------------------------------------------------------------------===//
 298 //                               Split Editor
 299 //===----------------------------------------------------------------------===//
 300
 301 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
 302 SplitEditor::SplitEditor(SplitAnalysis &sa,
 303                          LiveIntervals &lis,
 304                          VirtRegMap &vrm,
 305                          MachineDominatorTree &mdt)
 306   : SA(sa), LIS(lis), VRM(vrm),
 307     MRI(vrm.getMachineFunction().getRegInfo()),
 308     MDT(mdt),
 309     TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
 310     TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
 311     Edit(0),
 312     OpenIdx(0),
 313     SpillMode(SM_Partition),
 314     RegAssign(Allocator)
 315 {}
 316
 317 void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
 318   Edit = &LRE;
 319   SpillMode = SM;
 320   OpenIdx = 0;
 321   RegAssign.clear();
 322   Values.clear();
 323
 324   // Reset the LiveRangeCalc instances needed for this spill mode.
 325   LRCalc[0].reset(&VRM.getMachineFunction());
 326   if (SpillMode)
 327     LRCalc[1].reset(&VRM.getMachineFunction());
 328
 329   // We don't need an AliasAnalysis since we will only be performing
 330   // cheap-as-a-copy remats anyway.
 331   Edit->anyRematerializable(LIS, TII, 0);
 332 }
 333
 334 void SplitEditor::dump() const {
 335   if (RegAssign.empty()) {
 336     dbgs() << " empty\n";
 337     return;
 338   }
 339
 340   for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
 341     dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
 342   dbgs() << '\n';
 343 }
 344
 345 VNInfo *SplitEditor::defValue(unsigned RegIdx,
 346                               const VNInfo *ParentVNI,
 347                               SlotIndex Idx) {
 348   assert(ParentVNI && "Mapping  NULL value");
 349   assert(Idx.isValid() && "Invalid SlotIndex");
 350   assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
 351   LiveInterval *LI = Edit->get(RegIdx);
 352
 353   // Create a new value.
 354   VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
 355
 356   // Use insert for lookup, so we can add missing values with a second lookup.
 357   std::pair<ValueMap::iterator, bool> InsP =
 358     Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id),
 359                                  ValueForcePair(VNI, false)));
 360
 361   // This was the first time (RegIdx, ParentVNI) was mapped.
 362   // Keep it as a simple def without any liveness.
 363   if (InsP.second)
 364     return VNI;
 365
 366   // If the previous value was a simple mapping, add liveness for it now.
 367   if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
 368     SlotIndex Def = OldVNI->def;
 369     LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
 370     // No longer a simple mapping.  Switch to a complex, non-forced mapping.
 371     InsP.first->second = ValueForcePair();
 372   }
 373
 374   // This is a complex mapping, add liveness for VNI
 375   SlotIndex Def = VNI->def;
 376   LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
 377
 378   return VNI;
 379 }
 380
 381 void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
 382   assert(ParentVNI && "Mapping  NULL value");
 383   ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)];
 384   VNInfo *VNI = VFP.getPointer();
 385
 386   // ParentVNI was either unmapped or already complex mapped. Either way, just
 387   // set the force bit.
 388   if (!VNI) {
 389     VFP.setInt(true);
 390     return;
 391   }
 392
 393   // This was previously a single mapping. Make sure the old def is represented
 394   // by a trivial live range.
 395   SlotIndex Def = VNI->def;
 396   Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
 397   // Mark as complex mapped, forced.
 398   VFP = ValueForcePair(0, true);
 399 }
 400
 401 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
 402                                    VNInfo *ParentVNI,
 403                                    SlotIndex UseIdx,
 404                                    MachineBasicBlock &MBB,
 405                                    MachineBasicBlock::iterator I) {
 406   MachineInstr *CopyMI = 0;
 407   SlotIndex Def;
 408   LiveInterval *LI = Edit->get(RegIdx);
 409
 410   // We may be trying to avoid interference that ends at a deleted instruction,
 411   // so always begin RegIdx 0 early and all others late.
 412   bool Late = RegIdx != 0;
 413
 414   // Attempt cheap-as-a-copy rematerialization.
 415   LiveRangeEdit::Remat RM(ParentVNI);
 416   if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) {
 417     Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late);
 418     ++NumRemats;
 419   } else {
 420     // Can't remat, just insert a copy from parent.
 421     CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
 422                .addReg(Edit->getReg());
 423     Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late)
 424             .getDefIndex();
 425     ++NumCopies;
 426   }
 427
 428   // Define the value in Reg.
 429   VNInfo *VNI = defValue(RegIdx, ParentVNI, Def);
 430   VNI->setCopy(CopyMI);
 431   return VNI;
 432 }
 433
 434 /// Create a new virtual register and live interval.
 435 unsigned SplitEditor::openIntv() {
 436   // Create the complement as index 0.
 437   if (Edit->empty())
 438     Edit->create(LIS, VRM);
 439
 440   // Create the open interval.
 441   OpenIdx = Edit->size();
 442   Edit->create(LIS, VRM);
 443   return OpenIdx;
 444 }
 445
 446 void SplitEditor::selectIntv(unsigned Idx) {
 447   assert(Idx != 0 && "Cannot select the complement interval");
 448   assert(Idx < Edit->size() && "Can only select previously opened interval");
 449   DEBUG(dbgs() << "    selectIntv " << OpenIdx << " -> " << Idx << '\n');
 450   OpenIdx = Idx;
 451 }
 452
 453 SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
 454   assert(OpenIdx && "openIntv not called before enterIntvBefore");
 455   DEBUG(dbgs() << "    enterIntvBefore " << Idx);
 456   Idx = Idx.getBaseIndex();
 457   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
 458   if (!ParentVNI) {
 459     DEBUG(dbgs() << ": not live\n");
 460     return Idx;
 461   }
 462   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
 463   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
 464   assert(MI && "enterIntvBefore called with invalid index");
 465
 466   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
 467   return VNI->def;
 468 }
 469
 470 SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) {
 471   assert(OpenIdx && "openIntv not called before enterIntvAfter");
 472   DEBUG(dbgs() << "    enterIntvAfter " << Idx);
 473   Idx = Idx.getBoundaryIndex();
 474   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
 475   if (!ParentVNI) {
 476     DEBUG(dbgs() << ": not live\n");
 477     return Idx;
 478   }
 479   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
 480   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
 481   assert(MI && "enterIntvAfter called with invalid index");
 482
 483   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
 484                               llvm::next(MachineBasicBlock::iterator(MI)));
 485   return VNI->def;
 486 }
 487
 488 SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
 489   assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
 490   SlotIndex End = LIS.getMBBEndIdx(&MBB);
 491   SlotIndex Last = End.getPrevSlot();
 492   DEBUG(dbgs() << "    enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last);
 493   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
 494   if (!ParentVNI) {
 495     DEBUG(dbgs() << ": not live\n");
 496     return End;
 497   }
 498   DEBUG(dbgs() << ": valno " << ParentVNI->id);
 499   VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
 500                               LIS.getLastSplitPoint(Edit->getParent(), &MBB));
 501   RegAssign.insert(VNI->def, End, OpenIdx);
 502   DEBUG(dump());
 503   return VNI->def;
 504 }
 505
 506 /// useIntv - indicate that all instructions in MBB should use OpenLI.
 507 void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
 508   useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
 509 }
 510
 511 void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
 512   assert(OpenIdx && "openIntv not called before useIntv");
 513   DEBUG(dbgs() << "    useIntv [" << Start << ';' << End << "):");
 514   RegAssign.insert(Start, End, OpenIdx);
 515   DEBUG(dump());
 516 }
 517
 518 SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
 519   assert(OpenIdx && "openIntv not called before leaveIntvAfter");
 520   DEBUG(dbgs() << "    leaveIntvAfter " << Idx);
 521
 522   // The interval must be live beyond the instruction at Idx.
 523   SlotIndex Boundary = Idx.getBoundaryIndex();
 524   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);
 525   if (!ParentVNI) {
 526     DEBUG(dbgs() << ": not live\n");
 527     return Boundary.getNextSlot();
 528   }
 529   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
 530   MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);
 531   assert(MI && "No instruction at index");
 532
 533   // In spill mode, make live ranges as short as possible by inserting the copy
 534   // before MI.  This is only possible if that instruction doesn't redefine the
 535   // value.  The inserted COPY is not a kill, and we don't need to recompute
 536   // the source live range.  The spiller also won't try to hoist this copy.
 537   if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) &&
 538       MI->readsVirtualRegister(Edit->getReg())) {
 539     forceRecompute(0, ParentVNI);
 540     defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
 541     return Idx;
 542   }
 543
 544   VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
 545                               llvm::next(MachineBasicBlock::iterator(MI)));
 546   return VNI->def;
 547 }
 548
 549 SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
 550   assert(OpenIdx && "openIntv not called before leaveIntvBefore");
 551   DEBUG(dbgs() << "    leaveIntvBefore " << Idx);
 552
 553   // The interval must be live into the instruction at Idx.
 554   Idx = Idx.getBaseIndex();
 555   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
 556   if (!ParentVNI) {
 557     DEBUG(dbgs() << ": not live\n");
 558     return Idx.getNextSlot();
 559   }
 560   DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
 561
 562   MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
 563   assert(MI && "No instruction at index");
 564   VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
 565   return VNI->def;
 566 }
 567
 568 SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
 569   assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
 570   SlotIndex Start = LIS.getMBBStartIdx(&MBB);
 571   DEBUG(dbgs() << "    leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
 572
 573   VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
 574   if (!ParentVNI) {
 575     DEBUG(dbgs() << ": not live\n");
 576     return Start;
 577   }
 578
 579   VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
 580                               MBB.SkipPHIsAndLabels(MBB.begin()));
 581   RegAssign.insert(Start, VNI->def, OpenIdx);
 582   DEBUG(dump());
 583   return VNI->def;
 584 }
 585
 586 void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
 587   assert(OpenIdx && "openIntv not called before overlapIntv");
 588   const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
 589   assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) &&
 590          "Parent changes value in extended range");
 591   assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
 592          "Range cannot span basic blocks");
 593
 594   // The complement interval will be extended as needed by LRCalc.extend().
 595   if (ParentVNI)
 596     forceRecompute(0, ParentVNI);
 597   DEBUG(dbgs() << "    overlapIntv [" << Start << ';' << End << "):");
 598   RegAssign.insert(Start, End, OpenIdx);
 599   DEBUG(dump());
 600 }
 601
 602 //===----------------------------------------------------------------------===//
 603 //                                  Spill modes
 604 //===----------------------------------------------------------------------===//
 605
 606 void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
 607   LiveInterval *LI = Edit->get(0);
 608   DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
 609   RegAssignMap::iterator AssignI;
 610   AssignI.setMap(RegAssign);
 611
 612   for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
 613     VNInfo *VNI = Copies[i];
 614     SlotIndex Def = VNI->def;
 615     MachineInstr *MI = LIS.getInstructionFromIndex(Def);
 616     assert(MI && "No instruction for back-copy");
 617
 618     MachineBasicBlock *MBB = MI->getParent();
 619     MachineBasicBlock::iterator MBBI(MI);
 620     bool AtBegin;
 621     do AtBegin = MBBI == MBB->begin();
 622     while (!AtBegin && (--MBBI)->isDebugValue());
 623
 624     DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
 625     LI->removeValNo(VNI);
 626     LIS.RemoveMachineInstrFromMaps(MI);
 627     MI->eraseFromParent();
 628
 629     // Adjust RegAssign if a register assignment is killed at VNI->def.  We
 630     // want to avoid calculating the live range of the source register if
 631     // possible.
 632     AssignI.find(VNI->def.getPrevSlot());
 633     if (!AssignI.valid() || AssignI.start() >= Def)
 634       continue;
 635     // If MI doesn't kill the assigned register, just leave it.
 636     if (AssignI.stop() != Def)
 637       continue;
 638     unsigned RegIdx = AssignI.value();
 639     if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
 640       DEBUG(dbgs() << "  cannot find simple kill of RegIdx " << RegIdx << '\n');
 641       forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def));
 642     } else {
 643       SlotIndex Kill = LIS.getInstructionIndex(MBBI).getDefIndex();
 644       DEBUG(dbgs() << "  move kill to " << Kill << '\t' << *MBBI);
 645       AssignI.setStop(Kill);
 646     }
 647   }
 648 }
 649
 650 MachineBasicBlock*
 651 SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
 652                                   MachineBasicBlock *DefMBB) {
 653   if (MBB == DefMBB)
 654     return MBB;
 655   assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");
 656
 657   const MachineLoopInfo &Loops = SA.Loops;
 658   const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);
 659   MachineDomTreeNode *DefDomNode = MDT[DefMBB];
 660
 661   // Best candidate so far.
 662   MachineBasicBlock *BestMBB = MBB;
 663   unsigned BestDepth = UINT_MAX;
 664
 665   for (;;) {
 666     const MachineLoop *Loop = Loops.getLoopFor(MBB);
 667
 668     // MBB isn't in a loop, it doesn't get any better.  All dominators have a
 669     // higher frequency by definition.
 670     if (!Loop) {
 671       DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
 672                    << MBB->getNumber() << " at depth 0\n");
 673       return MBB;
 674     }
 675
 676     // We'll never be able to exit the DefLoop.
 677     if (Loop == DefLoop) {
 678       DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
 679                    << MBB->getNumber() << " in the same loop\n");
 680       return MBB;
 681     }
 682
 683     // Least busy dominator seen so far.
 684     unsigned Depth = Loop->getLoopDepth();
 685     if (Depth < BestDepth) {
 686       BestMBB = MBB;
 687       BestDepth = Depth;
 688       DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#"
 689                    << MBB->getNumber() << " at depth " << Depth << '\n');
 690     }
 691
 692     // Leave loop by going to the immediate dominator of the loop header.
 693     // This is a bigger stride than simply walking up the dominator tree.
 694     MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
 695
 696     // Too far up the dominator tree?
 697     if (!IDom || !MDT.dominates(DefDomNode, IDom))
 698       return BestMBB;
 699
 700     MBB = IDom->getBlock();
 701   }
 702 }
 703
 704 void SplitEditor::hoistCopiesForSize() {
 705   // Get the complement interval, always RegIdx 0.
 706   LiveInterval *LI = Edit->get(0);
 707   LiveInterval *Parent = &Edit->getParent();
 708
 709   // Track the nearest common dominator for all back-copies for each ParentVNI,
 710   // indexed by ParentVNI->id.
 711   typedef std::pair<MachineBasicBlock*, SlotIndex> DomPair;
 712   SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
 713
 714   // Find the nearest common dominator for parent values with multiple
 715   // back-copies.  If a single back-copy dominates, put it in DomPair.second.
 716   for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end();
 717        VI != VE; ++VI) {
 718     VNInfo *VNI = *VI;
 719     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
 720     assert(ParentVNI && "Parent not live at complement def");
 721
 722     // Don't hoist remats.  The complement is probably going to disappear
 723     // completely anyway.
 724     if (Edit->didRematerialize(ParentVNI))
 725       continue;
 726
 727     MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
 728     DomPair &Dom = NearestDom[ParentVNI->id];
 729
 730     // Keep directly defined parent values.  This is either a PHI or an
 731     // instruction in the complement range.  All other copies of ParentVNI
 732     // should be eliminated.
 733     if (VNI->def == ParentVNI->def) {
 734       DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
 735       Dom = DomPair(ValMBB, VNI->def);
 736       continue;
 737     }
 738     // Skip the singly mapped values.  There is nothing to gain from hoisting a
 739     // single back-copy.
 740     if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
 741       DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
 742       continue;
 743     }
 744
 745     if (!Dom.first) {
 746       // First time we see ParentVNI.  VNI dominates itself.
 747       Dom = DomPair(ValMBB, VNI->def);
 748     } else if (Dom.first == ValMBB) {
 749       // Two defs in the same block.  Pick the earlier def.
 750       if (!Dom.second.isValid() || VNI->def < Dom.second)
 751         Dom.second = VNI->def;
 752     } else {
 753       // Different basic blocks. Check if one dominates.
 754       MachineBasicBlock *Near =
 755         MDT.findNearestCommonDominator(Dom.first, ValMBB);
 756       if (Near == ValMBB)
 757         // Def ValMBB dominates.
 758         Dom = DomPair(ValMBB, VNI->def);
 759       else if (Near != Dom.first)
 760         // None dominate. Hoist to common dominator, need new def.
 761         Dom = DomPair(Near, SlotIndex());
 762     }
 763
 764     DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def
 765                  << " for parent " << ParentVNI->id << '@' << ParentVNI->def
 766                  << " hoist to BB#" << Dom.first->getNumber() << ' '
 767                  << Dom.second << '\n');
 768   }
 769
 770   // Insert the hoisted copies.
 771   for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) {
 772     DomPair &Dom = NearestDom[i];
 773     if (!Dom.first || Dom.second.isValid())
 774       continue;
 775     // This value needs a hoisted copy inserted at the end of Dom.first.
 776     VNInfo *ParentVNI = Parent->getValNumInfo(i);
 777     MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
 778     // Get a less loopy dominator than Dom.first.
 779     Dom.first = findShallowDominator(Dom.first, DefMBB);
 780     SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
 781     Dom.second =
 782       defFromParent(0, ParentVNI, Last, *Dom.first,
 783                     LIS.getLastSplitPoint(Edit->getParent(), Dom.first))->def;
 784   }
 785
 786   // Remove redundant back-copies that are now known to be dominated by another
 787   // def with the same value.
 788   SmallVector<VNInfo*, 8> BackCopies;
 789   for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end();
 790        VI != VE; ++VI) {
 791     VNInfo *VNI = *VI;
 792     VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
 793     const DomPair &Dom = NearestDom[ParentVNI->id];
 794     if (!Dom.first || Dom.second == VNI->def)
 795       continue;
 796     BackCopies.push_back(VNI);
 797     forceRecompute(0, ParentVNI);
 798   }
 799   removeBackCopies(BackCopies);
 800 }
 801
 802
 803 /// transferValues - Transfer all possible values to the new live ranges.
 804 /// Values that were rematerialized are left alone, they need LRCalc.extend().
 805 bool SplitEditor::transferValues() {
 806   bool Skipped = false;
 807   RegAssignMap::const_iterator AssignI = RegAssign.begin();
 808   for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(),
 809          ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) {
 810     DEBUG(dbgs() << "  blit " << *ParentI << ':');
 811     VNInfo *ParentVNI = ParentI->valno;
 812     // RegAssign has holes where RegIdx 0 should be used.
 813     SlotIndex Start = ParentI->start;
 814     AssignI.advanceTo(Start);
 815     do {
 816       unsigned RegIdx;
 817       SlotIndex End = ParentI->end;
 818       if (!AssignI.valid()) {
 819         RegIdx = 0;
 820       } else if (AssignI.start() <= Start) {
 821         RegIdx = AssignI.value();
 822         if (AssignI.stop() < End) {
 823           End = AssignI.stop();
 824           ++AssignI;
 825         }
 826       } else {
 827         RegIdx = 0;
 828         End = std::min(End, AssignI.start());
 829       }
 830
 831       // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
 832       DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx);
 833       LiveInterval *LI = Edit->get(RegIdx);
 834
 835       // Check for a simply defined value that can be blitted directly.
 836       ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
 837       if (VNInfo *VNI = VFP.getPointer()) {
 838         DEBUG(dbgs() << ':' << VNI->id);
 839         LI->addRange(LiveRange(Start, End, VNI));
 840         Start = End;
 841         continue;
 842       }
 843
 844       // Skip values with forced recomputation.
 845       if (VFP.getInt()) {
 846         DEBUG(dbgs() << "(recalc)");
 847         Skipped = true;
 848         Start = End;
 849         continue;
 850       }
 851
 852       LiveRangeCalc &LRC = getLRCalc(RegIdx);
 853
 854       // This value has multiple defs in RegIdx, but it wasn't rematerialized,
 855       // so the live range is accurate. Add live-in blocks in [Start;End) to the
 856       // LiveInBlocks.
 857       MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start);
 858       SlotIndex BlockStart, BlockEnd;
 859       tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB);
 860
 861       // The first block may be live-in, or it may have its own def.
 862       if (Start != BlockStart) {
 863         VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End));
 864         assert(VNI && "Missing def for complex mapped value");
 865         DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber());
 866         // MBB has its own def. Is it also live-out?
 867         if (BlockEnd <= End)
 868           LRC.setLiveOutValue(MBB, VNI);
 869
 870         // Skip to the next block for live-in.
 871         ++MBB;
 872         BlockStart = BlockEnd;
 873       }
 874
 875       // Handle the live-in blocks covered by [Start;End).
 876       assert(Start <= BlockStart && "Expected live-in block");
 877       while (BlockStart < End) {
 878         DEBUG(dbgs() << ">BB#" << MBB->getNumber());
 879         BlockEnd = LIS.getMBBEndIdx(MBB);
 880         if (BlockStart == ParentVNI->def) {
 881           // This block has the def of a parent PHI, so it isn't live-in.
 882           assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
 883           VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End));
 884           assert(VNI && "Missing def for complex mapped parent PHI");
 885           if (End >= BlockEnd)
 886             LRC.setLiveOutValue(MBB, VNI); // Live-out as well.
 887         } else {
 888           // This block needs a live-in value.  The last block covered may not
 889           // be live-out.
 890           if (End < BlockEnd)
 891             LRC.addLiveInBlock(LI, MDT[MBB], End);
 892           else {
 893             // Live-through, and we don't know the value.
 894             LRC.addLiveInBlock(LI, MDT[MBB]);
 895             LRC.setLiveOutValue(MBB, 0);
 896           }
 897         }
 898         BlockStart = BlockEnd;
 899         ++MBB;
 900       }
 901       Start = End;
 902     } while (Start != ParentI->end);
 903     DEBUG(dbgs() << '\n');
 904   }
 905
 906   LRCalc[0].calculateValues(LIS.getSlotIndexes(), &MDT,
 907                             &LIS.getVNInfoAllocator());
 908   if (SpillMode)
 909     LRCalc[1].calculateValues(LIS.getSlotIndexes(), &MDT,
 910                               &LIS.getVNInfoAllocator());
 911
 912   return Skipped;
 913 }
 914
 915 void SplitEditor::extendPHIKillRanges() {
 916     // Extend live ranges to be live-out for successor PHI values.
 917   for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(),
 918        E = Edit->getParent().vni_end(); I != E; ++I) {
 919     const VNInfo *PHIVNI = *I;
 920     if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
 921       continue;
 922     unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
 923     LiveInterval *LI = Edit->get(RegIdx);
 924     LiveRangeCalc &LRC = getLRCalc(RegIdx);
 925     MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
 926     for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 927          PE = MBB->pred_end(); PI != PE; ++PI) {
 928       SlotIndex End = LIS.getMBBEndIdx(*PI);
 929       SlotIndex LastUse = End.getPrevSlot();
 930       // The predecessor may not have a live-out value. That is OK, like an
 931       // undef PHI operand.
 932       if (Edit->getParent().liveAt(LastUse)) {
 933         assert(RegAssign.lookup(LastUse) == RegIdx &&
 934                "Different register assignment in phi predecessor");
 935         LRC.extend(LI, End,
 936                    LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator());
 937       }
 938     }
 939   }
 940 }
 941
 942 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
 943 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
 944   for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
 945        RE = MRI.reg_end(); RI != RE;) {
 946     MachineOperand &MO = RI.getOperand();
 947     MachineInstr *MI = MO.getParent();
 948     ++RI;
 949     // LiveDebugVariables should have handled all DBG_VALUE instructions.
 950     if (MI->isDebugValue()) {
 951       DEBUG(dbgs() << "Zapping " << *MI);
 952       MO.setReg(0);
 953       continue;
 954     }
 955
 956     // <undef> operands don't really read the register, so it doesn't matter
 957     // which register we choose.  When the use operand is tied to a def, we must
 958     // use the same register as the def, so just do that always.
 959     SlotIndex Idx = LIS.getInstructionIndex(MI);
 960     if (MO.isDef() || MO.isUndef())
 961       Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex();
 962
 963     // Rewrite to the mapped register at Idx.
 964     unsigned RegIdx = RegAssign.lookup(Idx);
 965     LiveInterval *LI = Edit->get(RegIdx);
 966     MO.setReg(LI->reg);
 967     DEBUG(dbgs() << "  rewr BB#" << MI->getParent()->getNumber() << '\t'
 968                  << Idx << ':' << RegIdx << '\t' << *MI);
 969
 970     // Extend liveness to Idx if the instruction reads reg.
 971     if (!ExtendRanges || MO.isUndef())
 972       continue;
 973
 974     // Skip instructions that don't read Reg.
 975     if (MO.isDef()) {
 976       if (!MO.getSubReg() && !MO.isEarlyClobber())
 977         continue;
 978       // We may wan't to extend a live range for a partial redef, or for a use
 979       // tied to an early clobber.
 980       Idx = Idx.getPrevSlot();
 981       if (!Edit->getParent().liveAt(Idx))
 982         continue;
 983     } else
 984       Idx = Idx.getUseIndex();
 985
 986     getLRCalc(RegIdx).extend(LI, Idx.getNextSlot(), LIS.getSlotIndexes(),
 987                              &MDT, &LIS.getVNInfoAllocator());
 988   }
 989 }
 990
 991 void SplitEditor::deleteRematVictims() {
 992   SmallVector<MachineInstr*, 8> Dead;
 993   for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){
 994     LiveInterval *LI = *I;
 995     for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end();
 996            LII != LIE; ++LII) {
 997       // Dead defs end at the store slot.
 998       if (LII->end != LII->valno->def.getNextSlot())
 999         continue;
1000       MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def);
1001       assert(MI && "Missing instruction for dead def");
1002       MI->addRegisterDead(LI->reg, &TRI);
1003
1004       if (!MI->allDefsAreDead())
1005         continue;
1006
1007       DEBUG(dbgs() << "All defs dead: " << *MI);
1008       Dead.push_back(MI);
1009     }
1010   }
1011
1012   if (Dead.empty())
1013     return;
1014
1015   Edit->eliminateDeadDefs(Dead, LIS, VRM, TII);
1016 }
1017
1018 void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
1019   ++NumFinished;
1020
1021   // At this point, the live intervals in Edit contain VNInfos corresponding to
1022   // the inserted copies.
1023
1024   // Add the original defs from the parent interval.
1025   for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(),
1026          E = Edit->getParent().vni_end(); I != E; ++I) {
1027     const VNInfo *ParentVNI = *I;
1028     if (ParentVNI->isUnused())
1029       continue;
1030     unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
1031     VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def);
1032     VNI->setIsPHIDef(ParentVNI->isPHIDef());
1033     VNI->setCopy(ParentVNI->getCopy());
1034
1035     // Force rematted values to be recomputed everywhere.
1036     // The new live ranges may be truncated.
1037     if (Edit->didRematerialize(ParentVNI))
1038       for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1039         forceRecompute(i, ParentVNI);
1040   }
1041
1042   // Hoist back-copies to the complement interval when in spill mode.
1043   switch (SpillMode) {
1044   case SM_Partition:
1045     // Leave all back-copies as is.
1046     break;
1047   case SM_Size:
1048     hoistCopiesForSize();
1049     break;
1050   case SM_Speed:
1051     llvm_unreachable("Spill mode 'speed' not implemented yet");
1052     break;
1053   }
1054
1055   // Transfer the simply mapped values, check if any are skipped.
1056   bool Skipped = transferValues();
1057   if (Skipped)
1058     extendPHIKillRanges();
1059   else
1060     ++NumSimple;
1061
1062   // Rewrite virtual registers, possibly extending ranges.
1063   rewriteAssigned(Skipped);
1064
1065   // Delete defs that were rematted everywhere.
1066   if (Skipped)
1067     deleteRematVictims();
1068
1069   // Get rid of unused values and set phi-kill flags.
1070   for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I)
1071     (*I)->RenumberValues(LIS);
1072
1073   // Provide a reverse mapping from original indices to Edit ranges.
1074   if (LRMap) {
1075     LRMap->clear();
1076     for (unsigned i = 0, e = Edit->size(); i != e; ++i)
1077       LRMap->push_back(i);
1078   }
1079
1080   // Now check if any registers were separated into multiple components.
1081   ConnectedVNInfoEqClasses ConEQ(LIS);
1082   for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
1083     // Don't use iterators, they are invalidated by create() below.
1084     LiveInterval *li = Edit->get(i);
1085     unsigned NumComp = ConEQ.Classify(li);
1086     if (NumComp <= 1)
1087       continue;
1088     DEBUG(dbgs() << "  " << NumComp << " components: " << *li << '\n');
1089     SmallVector<LiveInterval*, 8> dups;
1090     dups.push_back(li);
1091     for (unsigned j = 1; j != NumComp; ++j)
1092       dups.push_back(&Edit->create(LIS, VRM));
1093     ConEQ.Distribute(&dups[0], MRI);
1094     // The new intervals all map back to i.
1095     if (LRMap)
1096       LRMap->resize(Edit->size(), i);
1097   }
1098
1099   // Calculate spill weight and allocation hints for new intervals.
1100   Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops);
1101
1102   assert(!LRMap || LRMap->size() == Edit->size());
1103 }
1104
1105
1106 //===----------------------------------------------------------------------===//
1107 //                            Single Block Splitting
1108 //===----------------------------------------------------------------------===//
1109
1110 bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI,
1111                                            bool SingleInstrs) const {
1112   // Always split for multiple instructions.
1113   if (!BI.isOneInstr())
1114     return true;
1115   // Don't split for single instructions unless explicitly requested.
1116   if (!SingleInstrs)
1117     return false;
1118   // Splitting a live-through range always makes progress.
1119   if (BI.LiveIn && BI.LiveOut)
1120     return true;
1121   // No point in isolating a copy. It has no register class constraints.
1122   if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike())
1123     return false;
1124   // Finally, don't isolate an end point that was created by earlier splits.
1125   return isOriginalEndpoint(BI.FirstInstr);
1126 }
1127
1128 void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) {
1129   openIntv();
1130   SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber());
1131   SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr,
1132     LastSplitPoint));
1133   if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) {
1134     useIntv(SegStart, leaveIntvAfter(BI.LastInstr));
1135   } else {
1136       // The last use is after the last valid split point.
1137     SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);
1138     useIntv(SegStart, SegStop);
1139     overlapIntv(SegStop, BI.LastInstr);
1140   }
1141 }
1142
1143
1144 //===----------------------------------------------------------------------===//
1145 //                    Global Live Range Splitting Support
1146 //===----------------------------------------------------------------------===//
1147
1148 // These methods support a method of global live range splitting that uses a
1149 // global algorithm to decide intervals for CFG edges. They will insert split
1150 // points and color intervals in basic blocks while avoiding interference.
1151 //
1152 // Note that splitSingleBlock is also useful for blocks where both CFG edges
1153 // are on the stack.
1154
1155 void SplitEditor::splitLiveThroughBlock(unsigned MBBNum,
1156                                         unsigned IntvIn, SlotIndex LeaveBefore,
1157                                         unsigned IntvOut, SlotIndex EnterAfter){
1158   SlotIndex Start, Stop;
1159   tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
1160
1161   DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop
1162                << ") intf " << LeaveBefore << '-' << EnterAfter
1163                << ", live-through " << IntvIn << " -> " << IntvOut);
1164
1165   assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");
1166
1167   assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");
1168   assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");
1169   assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");
1170
1171   MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum);
1172
1173   if (!IntvOut) {
1174     DEBUG(dbgs() << ", spill on entry.\n");
1175     //
1176     //        <<<<<<<<<    Possible LeaveBefore interference.
1177     //    |-----------|    Live through.
1178     //    -____________    Spill on entry.
1179     //
1180     selectIntv(IntvIn);
1181     SlotIndex Idx = leaveIntvAtTop(*MBB);
1182     assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1183     (void)Idx;
1184     return;
1185   }
1186
1187   if (!IntvIn) {
1188     DEBUG(dbgs() << ", reload on exit.\n");
1189     //
1190     //    >>>>>>>          Possible EnterAfter interference.
1191     //    |-----------|    Live through.
1192     //    ___________--    Reload on exit.
1193     //
1194     selectIntv(IntvOut);
1195     SlotIndex Idx = enterIntvAtEnd(*MBB);
1196     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1197     (void)Idx;
1198     return;
1199   }
1200
1201   if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) {
1202     DEBUG(dbgs() << ", straight through.\n");
1203     //
1204     //    |-----------|    Live through.
1205     //    -------------    Straight through, same intv, no interference.
1206     //
1207     selectIntv(IntvOut);
1208     useIntv(Start, Stop);
1209     return;
1210   }
1211
1212   // We cannot legally insert splits after LSP.
1213   SlotIndex LSP = SA.getLastSplitPoint(MBBNum);
1214   assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");
1215
1216   if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter ||
1217                   LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) {
1218     DEBUG(dbgs() << ", switch avoiding interference.\n");
1219     //
1220     //    >>>>     <<<<    Non-overlapping EnterAfter/LeaveBefore interference.
1221     //    |-----------|    Live through.
1222     //    ------=======    Switch intervals between interference.
1223     //
1224     selectIntv(IntvOut);
1225     SlotIndex Idx;
1226     if (LeaveBefore && LeaveBefore < LSP) {
1227       Idx = enterIntvBefore(LeaveBefore);
1228       useIntv(Idx, Stop);
1229     } else {
1230       Idx = enterIntvAtEnd(*MBB);
1231     }
1232     selectIntv(IntvIn);
1233     useIntv(Start, Idx);
1234     assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1235     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1236     return;
1237   }
1238
1239   DEBUG(dbgs() << ", create local intv for interference.\n");
1240   //
1241   //    >>><><><><<<<    Overlapping EnterAfter/LeaveBefore interference.
1242   //    |-----------|    Live through.
1243   //    ==---------==    Switch intervals before/after interference.
1244   //
1245   assert(LeaveBefore <= EnterAfter && "Missed case");
1246
1247   selectIntv(IntvOut);
1248   SlotIndex Idx = enterIntvAfter(EnterAfter);
1249   useIntv(Idx, Stop);
1250   assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1251
1252   selectIntv(IntvIn);
1253   Idx = leaveIntvBefore(LeaveBefore);
1254   useIntv(Start, Idx);
1255   assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1256 }
1257
1258
1259 void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
1260                                   unsigned IntvIn, SlotIndex LeaveBefore) {
1261   SlotIndex Start, Stop;
1262   tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1263
1264   DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
1265                << "), uses " << BI.FirstInstr << '-' << BI.LastInstr
1266                << ", reg-in " << IntvIn << ", leave before " << LeaveBefore
1267                << (BI.LiveOut ? ", stack-out" : ", killed in block"));
1268
1269   assert(IntvIn && "Must have register in");
1270   assert(BI.LiveIn && "Must be live-in");
1271   assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");
1272
1273   if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) {
1274     DEBUG(dbgs() << " before interference.\n");
1275     //
1276     //               <<<    Interference after kill.
1277     //     |---o---x   |    Killed in block.
1278     //     =========        Use IntvIn everywhere.
1279     //
1280     selectIntv(IntvIn);
1281     useIntv(Start, BI.LastInstr);
1282     return;
1283   }
1284
1285   SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1286
1287   if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) {
1288     //
1289     //               <<<    Possible interference after last use.
1290     //     |---o---o---|    Live-out on stack.
1291     //     =========____    Leave IntvIn after last use.
1292     //
1293     //                 <    Interference after last use.
1294     //     |---o---o--o|    Live-out on stack, late last use.
1295     //     ============     Copy to stack after LSP, overlap IntvIn.
1296     //            \_____    Stack interval is live-out.
1297     //
1298     if (BI.LastInstr < LSP) {
1299       DEBUG(dbgs() << ", spill after last use before interference.\n");
1300       selectIntv(IntvIn);
1301       SlotIndex Idx = leaveIntvAfter(BI.LastInstr);
1302       useIntv(Start, Idx);
1303       assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1304     } else {
1305       DEBUG(dbgs() << ", spill before last split point.\n");
1306       selectIntv(IntvIn);
1307       SlotIndex Idx = leaveIntvBefore(LSP);
1308       overlapIntv(Idx, BI.LastInstr);
1309       useIntv(Start, Idx);
1310       assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1311     }
1312     return;
1313   }
1314
1315   // The interference is overlapping somewhere we wanted to use IntvIn. That
1316   // means we need to create a local interval that can be allocated a
1317   // different register.
1318   unsigned LocalIntv = openIntv();
1319   (void)LocalIntv;
1320   DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");
1321
1322   if (!BI.LiveOut || BI.LastInstr < LSP) {
1323     //
1324     //           <<<<<<<    Interference overlapping uses.
1325     //     |---o---o---|    Live-out on stack.
1326     //     =====----____    Leave IntvIn before interference, then spill.
1327     //
1328     SlotIndex To = leaveIntvAfter(BI.LastInstr);
1329     SlotIndex From = enterIntvBefore(LeaveBefore);
1330     useIntv(From, To);
1331     selectIntv(IntvIn);
1332     useIntv(Start, From);
1333     assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1334     return;
1335   }
1336
1337   //           <<<<<<<    Interference overlapping uses.
1338   //     |---o---o--o|    Live-out on stack, late last use.
1339   //     =====-------     Copy to stack before LSP, overlap LocalIntv.
1340   //            \_____    Stack interval is live-out.
1341   //
1342   SlotIndex To = leaveIntvBefore(LSP);
1343   overlapIntv(To, BI.LastInstr);
1344   SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore));
1345   useIntv(From, To);
1346   selectIntv(IntvIn);
1347   useIntv(Start, From);
1348   assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1349 }
1350
1351 void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
1352                                    unsigned IntvOut, SlotIndex EnterAfter) {
1353   SlotIndex Start, Stop;
1354   tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1355
1356   DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
1357                << "), uses " << BI.FirstInstr << '-' << BI.LastInstr
1358                << ", reg-out " << IntvOut << ", enter after " << EnterAfter
1359                << (BI.LiveIn ? ", stack-in" : ", defined in block"));
1360
1361   SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1362
1363   assert(IntvOut && "Must have register out");
1364   assert(BI.LiveOut && "Must be live-out");
1365   assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");
1366
1367   if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) {
1368     DEBUG(dbgs() << " after interference.\n");
1369     //
1370     //    >>>>             Interference before def.
1371     //    |   o---o---|    Defined in block.
1372     //        =========    Use IntvOut everywhere.
1373     //
1374     selectIntv(IntvOut);
1375     useIntv(BI.FirstInstr, Stop);
1376     return;
1377   }
1378
1379   if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) {
1380     DEBUG(dbgs() << ", reload after interference.\n");
1381     //
1382     //    >>>>             Interference before def.
1383     //    |---o---o---|    Live-through, stack-in.
1384     //    ____=========    Enter IntvOut before first use.
1385     //
1386     selectIntv(IntvOut);
1387     SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr));
1388     useIntv(Idx, Stop);
1389     assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1390     return;
1391   }
1392
1393   // The interference is overlapping somewhere we wanted to use IntvOut. That
1394   // means we need to create a local interval that can be allocated a
1395   // different register.
1396   DEBUG(dbgs() << ", interference overlaps uses.\n");
1397   //
1398   //    >>>>>>>          Interference overlapping uses.
1399   //    |---o---o---|    Live-through, stack-in.
1400   //    ____---======    Create local interval for interference range.
1401   //
1402   selectIntv(IntvOut);
1403   SlotIndex Idx = enterIntvAfter(EnterAfter);
1404   useIntv(Idx, Stop);
1405   assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1406
1407   openIntv();
1408   SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr));
1409   useIntv(From, Idx);
1410 }