1 files changed, 73 insertions, 205 deletions

diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index 5b9f49d11a..bce606c3ef 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -363,10 +363,8 @@ VNInfo *LiveIntervalMap::defValue(const VNInfo *ParentVNI, SlotIndex Idx) {
   if (Idx == ParentVNI->def)
     return mapValue(ParentVNI, Idx);
 
-  // This is a complex def. Mark with a NULL in valueMap.
-  VNInfo *&OldVNI = valueMap_[ParentVNI];
-  assert(!OldVNI && "Simple/Complex values mixed");
-  OldVNI = 0;
+  // This is now a complex def. Mark with a NULL in valueMap.
+  valueMap_[ParentVNI] = 0;
 
   // Should we insert a minimal snippet of VNI LiveRange, or can we count on
   // callers to do that? We need it for lookups of complex values.
@@ -417,10 +415,10 @@ VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx) {
          IDFI = idf_begin(IdxMBB),
          IDFE = idf_end(IdxMBB); IDFI != IDFE;) {
     MachineBasicBlock *MBB = *IDFI;
-    SlotIndex End = lis_.getMBBEndIdx(MBB);
+    SlotIndex End = lis_.getMBBEndIdx(MBB).getPrevSlot();
 
     // We are operating on the restricted CFG where ParentVNI is live.
-    if (parentli_.getVNInfoAt(End.getPrevSlot()) != ParentVNI) {
+    if (parentli_.getVNInfoAt(End) != ParentVNI) {
       IDFI.skipChildren();
       continue;
     }
@@ -489,7 +487,7 @@ VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx) {
      if (MBB == IdxMBB) {
        // Don't add full liveness to IdxMBB, stop at Idx.
        if (Start != Idx)
-         li_->addRange(LiveRange(Start, Idx, VNI));
+         li_->addRange(LiveRange(Start, Idx.getNextSlot(), VNI));
        // The caller had better add some liveness to IdxVNI, or it leaks.
        IdxVNI = VNI;
      } else
@@ -511,8 +509,8 @@ VNInfo *LiveIntervalMap::extendTo(MachineBasicBlock *MBB, SlotIndex Idx) {
   --I;
   if (I->start < lis_.getMBBStartIdx(MBB))
     return 0;
-  if (I->end < Idx)
-    I->end = Idx;
+  if (I->end <= Idx)
+    I->end = Idx.getNextSlot();
   return I->valno;
 }
 
@@ -574,6 +572,20 @@ void LiveIntervalMap::addRange(SlotIndex Start, SlotIndex End) {
     addSimpleRange(I->start, std::min(End, I->end), I->valno);
 }
 
+VNInfo *LiveIntervalMap::defByCopyFrom(unsigned Reg,
+                                       const VNInfo *ParentVNI,
+                                       MachineBasicBlock &MBB,
+                                       MachineBasicBlock::iterator I) {
+  const TargetInstrDesc &TID = MBB.getParent()->getTarget().getInstrInfo()->
+    get(TargetOpcode::COPY);
+  MachineInstr *MI = BuildMI(MBB, I, DebugLoc(), TID, li_->reg).addReg(Reg);
+  SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
+  VNInfo *VNI = defValue(ParentVNI, DefIdx);
+  VNI->setCopy(MI);
+  li_->addRange(LiveRange(DefIdx, DefIdx.getNextSlot(), VNI));
+  return VNI;
+}
+
 //===----------------------------------------------------------------------===//
 //                               Split Editor
 //===----------------------------------------------------------------------===//
@@ -600,122 +612,56 @@ SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm,
 }
 
 LiveInterval *SplitEditor::createInterval() {
-  unsigned curli = sa_.getCurLI()->reg;
-  unsigned Reg = mri_.createVirtualRegister(mri_.getRegClass(curli));
+  unsigned Reg = mri_.createVirtualRegister(mri_.getRegClass(curli_->reg));
   LiveInterval &Intv = lis_.getOrCreateInterval(Reg);
   vrm_.grow();
-  vrm_.assignVirt2StackSlot(Reg, vrm_.getStackSlot(curli));
+  vrm_.assignVirt2StackSlot(Reg, vrm_.getStackSlot(curli_->reg));
   return &Intv;
 }
 
-LiveInterval *SplitEditor::getDupLI() {
+/// Create a new virtual register and live interval.
+void SplitEditor::openIntv() {
+  assert(!openli_.getLI() && "Previous LI not closed before openIntv");
+
   if (!dupli_.getLI()) {
     // Create an interval for dupli that is a copy of curli.
     dupli_.reset(createInterval());
     dupli_.getLI()->Copy(*curli_, &mri_, lis_.getVNInfoAllocator());
   }
-  return dupli_.getLI();
-}
-
-VNInfo *SplitEditor::mapValue(const VNInfo *curliVNI) {
-  VNInfo *&VNI = valueMap_[curliVNI];
-  if (!VNI)
-    VNI = openli_.getLI()->createValueCopy(curliVNI, lis_.getVNInfoAllocator());
-  return VNI;
-}
-
-/// Insert a COPY instruction curli -> li. Allocate a new value from li
-/// defined by the COPY. Note that rewrite() will deal with the curli
-/// register, so this function can be used to copy from any interval - openli,
-/// curli, or dupli.
-VNInfo *SplitEditor::insertCopy(LiveInterval &LI,
-                                MachineBasicBlock &MBB,
-                                MachineBasicBlock::iterator I) {
-  MachineInstr *MI = BuildMI(MBB, I, DebugLoc(), tii_.get(TargetOpcode::COPY),
-                             LI.reg).addReg(curli_->reg);
-  SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
-  return LI.getNextValue(DefIdx, MI, true, lis_.getVNInfoAllocator());
-}
 
-/// Create a new virtual register and live interval.
-void SplitEditor::openIntv() {
-  assert(!openli_.getLI() && "Previous LI not closed before openIntv");
   openli_.reset(createInterval());
   intervals_.push_back(openli_.getLI());
-  liveThrough_ = false;
 }
 
 /// enterIntvBefore - Enter openli before the instruction at Idx. If curli is
 /// not live before Idx, a COPY is not inserted.
 void SplitEditor::enterIntvBefore(SlotIndex Idx) {
   assert(openli_.getLI() && "openIntv not called before enterIntvBefore");
-
-  // Copy from curli_ if it is live.
-  if (VNInfo *CurVNI = curli_->getVNInfoAt(Idx.getUseIndex())) {
-    MachineInstr *MI = lis_.getInstructionFromIndex(Idx);
-    assert(MI && "enterIntvBefore called with invalid index");
-    VNInfo *VNI = insertCopy(*openli_.getLI(), *MI->getParent(), MI);
-    openli_.getLI()->addRange(LiveRange(VNI->def, Idx.getDefIndex(), VNI));
-
-    // Make sure CurVNI is properly mapped.
-    VNInfo *&mapVNI = valueMap_[CurVNI];
-    // We dont have SSA update yet, so only one entry per value is allowed.
-    assert(!mapVNI && "enterIntvBefore called more than once for the same value");
-    mapVNI = VNI;
+  VNInfo *ParentVNI = curli_->getVNInfoAt(Idx.getUseIndex());
+  if (!ParentVNI) {
+    DEBUG(dbgs() << "    enterIntvBefore " << Idx << ": not live\n");
+    return;
   }
+  MachineInstr *MI = lis_.getInstructionFromIndex(Idx);
+  assert(MI && "enterIntvBefore called with invalid index");
+  openli_.defByCopyFrom(curli_->reg, ParentVNI, *MI->getParent(), MI);
   DEBUG(dbgs() << "    enterIntvBefore " << Idx << ": " << *openli_.getLI()
                << '\n');
 }
 
 /// enterIntvAtEnd - Enter openli at the end of MBB.
-/// PhiMBB is a successor inside openli where a PHI value is created.
-/// Currently, all entries must share the same PhiMBB.
-void SplitEditor::enterIntvAtEnd(MachineBasicBlock &A, MachineBasicBlock &B) {
+void SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
   assert(openli_.getLI() && "openIntv not called before enterIntvAtEnd");
-
-  SlotIndex EndA = lis_.getMBBEndIdx(&A);
-  VNInfo *CurVNIA = curli_->getVNInfoAt(EndA.getPrevIndex());
-  if (!CurVNIA) {
-    DEBUG(dbgs() << "    enterIntvAtEnd, curli not live out of BB#"
-                 << A.getNumber() << ".\n");
-    return;
-  }
-
-  // Add a phi kill value and live range out of A.
-  VNInfo *VNIA = insertCopy(*openli_.getLI(), A, A.getFirstTerminator());
-  openli_.getLI()->addRange(LiveRange(VNIA->def, EndA, VNIA));
-
-  // FIXME: If this is the only entry edge, we don't need the extra PHI value.
-  // FIXME: If there are multiple entry blocks (so not a loop), we need proper
-  // SSA update.
-
-  // Now look at the start of B.
-  SlotIndex StartB = lis_.getMBBStartIdx(&B);
-  SlotIndex EndB = lis_.getMBBEndIdx(&B);
-  const LiveRange *CurB = curli_->getLiveRangeContaining(StartB);
-  if (!CurB) {
-    DEBUG(dbgs() << "    enterIntvAtEnd: curli not live in to BB#"
-                 << B.getNumber() << ".\n");
+  SlotIndex End = lis_.getMBBEndIdx(&MBB);
+  VNInfo *ParentVNI = curli_->getVNInfoAt(End.getPrevSlot());
+  if (!ParentVNI) {
+    DEBUG(dbgs() << "    enterIntvAtEnd " << End << ": not live\n");
     return;
   }
-
-  VNInfo *VNIB = openli_.getLI()->getVNInfoAt(StartB);
-  if (!VNIB) {
-    // Create a phi value.
-    VNIB = openli_.getLI()->getNextValue(SlotIndex(StartB, true), 0, false,
-                                         lis_.getVNInfoAllocator());
-    VNIB->setIsPHIDef(true);
-    VNInfo *&mapVNI = valueMap_[CurB->valno];
-    if (mapVNI) {
-      // Multiple copies - must create PHI value.
-      abort();
-    } else {
-      // This is the first copy of dupLR. Mark the mapping.
-      mapVNI = VNIB;
-    }
-
-  }
-
+  VNInfo *VNI = openli_.defByCopyFrom(curli_->reg, ParentVNI,
+                                      MBB, MBB.getFirstTerminator());
+  // Make sure openli is live out of MBB.
+  openli_.getLI()->addRange(LiveRange(VNI->def, End, VNI));
   DEBUG(dbgs() << "    enterIntvAtEnd: " << *openli_.getLI() << '\n');
 }
 
@@ -726,24 +672,7 @@ void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
 
 void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
   assert(openli_.getLI() && "openIntv not called before useIntv");
-
-  // Map the curli values from the interval into openli_
-  LiveInterval::const_iterator B = curli_->begin(), E = curli_->end();
-  LiveInterval::const_iterator I = std::lower_bound(B, E, Start);
-
-  if (I != B) {
-    --I;
-    // I begins before Start, but overlaps.
-    if (I->end > Start)
-      openli_.getLI()->addRange(LiveRange(Start, std::min(End, I->end),
-                                mapValue(I->valno)));
-    ++I;
-  }
-
-  // The remaining ranges begin after Start.
-  for (;I != E && I->start < End; ++I)
-    openli_.getLI()->addRange(LiveRange(I->start, std::min(End, I->end),
-                                        mapValue(I->valno)));
+  openli_.addRange(Start, End);
   DEBUG(dbgs() << "    use [" << Start << ';' << End << "): "
                << *openli_.getLI() << '\n');
 }
@@ -752,32 +681,24 @@ void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
 void SplitEditor::leaveIntvAfter(SlotIndex Idx) {
   assert(openli_.getLI() && "openIntv not called before leaveIntvAfter");
 
-  const LiveRange *CurLR = curli_->getLiveRangeContaining(Idx.getDefIndex());
-  if (!CurLR || CurLR->end <= Idx.getBoundaryIndex()) {
+  // The interval must be live beyond the instruction at Idx.
+  SlotIndex EndIdx = Idx.getNextIndex().getBaseIndex();
+  VNInfo *ParentVNI = curli_->getVNInfoAt(EndIdx);
+  if (!ParentVNI) {
     DEBUG(dbgs() << "    leaveIntvAfter " << Idx << ": not live\n");
     return;
   }
 
-  // Was this value of curli live through openli?
-  if (!openli_.getLI()->liveAt(CurLR->valno->def)) {
-    DEBUG(dbgs() << "    leaveIntvAfter " << Idx << ": using external value\n");
-    liveThrough_ = true;
-    return;
-  }
+  MachineInstr *MI = lis_.getInstructionFromIndex(Idx);
+  assert(MI && "leaveIntvAfter called with invalid index");
+
+  VNInfo *VNI = dupli_.defByCopyFrom(openli_.getLI()->reg, ParentVNI,
+                                  *MI->getParent(), MI);
+
+  // Finally we must make sure that openli is properly extended from Idx to the
+  // new copy.
+  openli_.mapValue(ParentVNI, VNI->def.getUseIndex());
 
-  // We are going to insert a back copy, so we must have a dupli_.
-  LiveRange *DupLR = getDupLI()->getLiveRangeContaining(Idx.getDefIndex());
-  assert(DupLR && "dupli not live into block, but curli is?");
-
-  // Insert the COPY instruction.
-  MachineBasicBlock::iterator I = lis_.getInstructionFromIndex(Idx);
-  MachineInstr *MI = BuildMI(*I->getParent(), llvm::next(I), I->getDebugLoc(),
-                             tii_.get(TargetOpcode::COPY), dupli_.getLI()->reg)
-                       .addReg(openli_.getLI()->reg);
-  SlotIndex CopyIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
-  openli_.getLI()->addRange(LiveRange(Idx.getDefIndex(), CopyIdx,
-                            mapValue(CurLR->valno)));
-  DupLR->valno->def = CopyIdx;
   DEBUG(dbgs() << "    leaveIntvAfter " << Idx << ": " << *openli_.getLI()
                << '\n');
 }
@@ -788,68 +709,23 @@ void SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
   assert(openli_.getLI() && "openIntv not called before leaveIntvAtTop");
 
   SlotIndex Start = lis_.getMBBStartIdx(&MBB);
-  const LiveRange *CurLR = curli_->getLiveRangeContaining(Start);
+  VNInfo *ParentVNI = curli_->getVNInfoAt(Start);
 
   // Is curli even live-in to MBB?
-  if (!CurLR) {
+  if (!ParentVNI) {
     DEBUG(dbgs() << "    leaveIntvAtTop at " << Start << ": not live\n");
     return;
   }
 
-  // Is curli defined by PHI at the beginning of MBB?
-  bool isPHIDef = CurLR->valno->isPHIDef() &&
-                  CurLR->valno->def.getBaseIndex() == Start;
-
-  // If MBB is using a value of curli that was defined outside the openli range,
-  // we don't want to copy it back here.
-  if (!isPHIDef && !openli_.getLI()->liveAt(CurLR->valno->def)) {
-    DEBUG(dbgs() << "    leaveIntvAtTop at " << Start
-                 << ": using external value\n");
-    liveThrough_ = true;
-    return;
-  }
-
   // We are going to insert a back copy, so we must have a dupli_.
-  LiveRange *DupLR = getDupLI()->getLiveRangeContaining(Start);
-  assert(DupLR && "dupli not live into block, but curli is?");
-
-  // Insert the COPY instruction.
-  MachineInstr *MI = BuildMI(MBB, MBB.begin(), DebugLoc(),
-                             tii_.get(TargetOpcode::COPY), dupli_.getLI()->reg)
-                       .addReg(openli_.getLI()->reg);
-  SlotIndex Idx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
-
-  // Adjust dupli and openli values.
-  if (isPHIDef) {
-    // dupli was already a PHI on entry to MBB. Simply insert an openli PHI,
-    // and shift the dupli def down to the COPY.
-    VNInfo *VNI = openli_.getLI()->getNextValue(SlotIndex(Start,true), 0, false,
-                                                lis_.getVNInfoAllocator());
-    VNI->setIsPHIDef(true);
-    openli_.getLI()->addRange(LiveRange(VNI->def, Idx, VNI));
-
-    dupli_.getLI()->removeRange(Start, Idx);
-    DupLR->valno->def = Idx;
-    DupLR->valno->setIsPHIDef(false);
-  } else {
-    // The dupli value was defined somewhere inside the openli range.
-    DEBUG(dbgs() << "    leaveIntvAtTop source value defined at "
-                 << DupLR->valno->def << "\n");
-    // FIXME: We may not need a PHI here if all predecessors have the same
-    // value.
-    VNInfo *VNI = openli_.getLI()->getNextValue(SlotIndex(Start,true), 0, false,
-                                                lis_.getVNInfoAllocator());
-    VNI->setIsPHIDef(true);
-    openli_.getLI()->addRange(LiveRange(VNI->def, Idx, VNI));
-
-    // FIXME: What if DupLR->valno is used by multiple exits? SSA Update.
-
-    // closeIntv is going to remove the superfluous live ranges.
-    DupLR->valno->def = Idx;
-    DupLR->valno->setIsPHIDef(false);
-  }
+  VNInfo *VNI = dupli_.defByCopyFrom(openli_.getLI()->reg, ParentVNI,
+                                     MBB, MBB.begin());
 
-  DEBUG(dbgs() << "    leaveIntvAtTop at " << Idx << ": " << *openli_.getLI()
+  // Finally we must make sure that openli is properly extended from Start to
+  // the new copy.
+  openli_.mapValue(ParentVNI, VNI->def.getUseIndex());
+
+  DEBUG(dbgs() << "    leaveIntvAtTop at " << Start << ": " << *openli_.getLI()
                << '\n');
 }
 
@@ -861,22 +737,14 @@ void SplitEditor::closeIntv() {
   DEBUG(dbgs() << "    closeIntv cleaning up\n");
   DEBUG(dbgs() << "    open " << *openli_.getLI() << '\n');
 
-  if (liveThrough_) {
-    DEBUG(dbgs() << "    value live through region, leaving dupli as is.\n");
-  } else {
-    // live out with copies inserted, or killed by region. Either way we need to
-    // remove the overlapping region from dupli.
-    getDupLI();
-    for (LiveInterval::iterator I = openli_.getLI()->begin(),
-         E = openli_.getLI()->end(); I != E; ++I) {
-      dupli_.getLI()->removeRange(I->start, I->end);
-    }
-    // FIXME: A block branching to the entry block may also branch elsewhere
-    // curli is live. We need both openli and curli to be live in that case.
-    DEBUG(dbgs() << "    dup2 " << *dupli_.getLI() << '\n');
+  for (LiveInterval::iterator I = openli_.getLI()->begin(),
+       E = openli_.getLI()->end(); I != E; ++I) {
+    dupli_.getLI()->removeRange(I->start, I->end);
   }
+  // FIXME: A block branching to the entry block may also branch elsewhere
+  // curli is live. We need both openli and curli to be live in that case.
+  DEBUG(dbgs() << "    dup2 " << *dupli_.getLI() << '\n');
   openli_.reset(0);
-  valueMap_.clear();
 }
 
 /// rewrite - after all the new live ranges have been created, rewrite
@@ -957,7 +825,7 @@ bool SplitEditor::splitAroundLoop(const MachineLoop *Loop) {
   for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Preds.begin(),
        E = Blocks.Preds.end(); I != E; ++I) {
     MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
-    enterIntvAtEnd(MBB, *Loop->getHeader());
+    enterIntvAtEnd(MBB);
   }
 
   // Switch all loop blocks.