Defer sanity checks on live intervals until after all have been updated. Hold (LiveIn...
[oota-llvm.git] / lib / CodeGen / LiveIntervalAnalysis.cpp
index e84e8009ad441214db01a1a1d98f6121963ec76a..2a7830dcc6b703812001cb585426fa042bbee3ff 100644 (file)
@@ -1028,254 +1028,256 @@ bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
 /// HMEditor is a toolkit used by handleMove to trim or extend live intervals.
 class LiveIntervals::HMEditor {
 private:
-  LiveIntervals& lis;
-  SlotIndex newIdx;
+  LiveIntervals& LIS;
+  const MachineRegisterInfo& MRI;
+  const TargetRegisterInfo& TRI;
+  SlotIndex NewIdx;
 
-public:
-  HMEditor(LiveIntervals& lis, SlotIndex newIdx)
-    : lis(lis), newIdx(newIdx) {}
-
-  // Update lr to be defined at newIdx. Preserves lr.
-  void moveDef(LiveRange& lr, LiveInterval& li) {
-    lr.start = newIdx.getRegSlot();
-    lr.valno->def = newIdx.getRegSlot();
-    assert(intervalRangesSane(li) && "Broke live interval moving def.");
-  }
-
-  // Removes lr from li, inserting a new dead-def range starting at newIdx.
-  void moveDeadDefOrEC(LiveRange& lr, LiveInterval& li, bool isEC) {
-    LiveRange t(lr);
-    t.start = newIdx.getRegSlot(isEC);
-    t.valno->def = newIdx.getRegSlot(isEC);
-    t.end = isEC ? newIdx.getRegSlot() : newIdx.getDeadSlot();
-    li.removeRange(lr);
-    li.addRange(t);
-    assert(intervalRangesSane(li) && "Broke live interval moving dead def.");
-  }
+  typedef std::pair<LiveInterval*, LiveRange*> IntRangePair;
+  typedef DenseSet<IntRangePair> RangeSet;
 
-  void moveUseDown(SlotIndex oldIdx, LiveRange& lr, LiveInterval& li,
-                   const MachineBasicBlock* mbb) {
-    bool liveThrough = lr.end > oldIdx.getRegSlot();
-    if (!liveThrough) {
-      // Easy fix - just update the range endpoint.
-      lr.end = newIdx.getRegSlot();
-    } else {
-      bool liveOut = lr.end >= lis.getSlotIndexes()->getMBBEndIdx(mbb);
-      if (!liveOut) {
-        moveKillFlags(li.reg, lr.end, newIdx);
-        lr.end = newIdx.getRegSlot();
-      }
-    }
-    assert(intervalRangesSane(li) && "Broke live interval moving use.");
-  }
-
-  void moveUseUp(SlotIndex oldIdx, LiveRange& lr, LiveInterval& li) {
-    bool liveThrough = lr.end > oldIdx.getRegSlot();
-    if (liveThrough)
-      return; // If we moving up and live through there's nothing to do.
-    SlotIndex lastUseInRange = newIdx.getRegSlot();
-    for (MachineRegisterInfo::use_nodbg_iterator
-           useI = lis.mri_->use_nodbg_begin(li.reg),
-           useE = lis.mri_->use_nodbg_end();
-         useI != useE; ++useI) {
-      const MachineInstr* mopI = &*useI;
-      const MachineOperand& mop = useI.getOperand();
-      SlotIndex instSlot = lis.getSlotIndexes()->getInstructionIndex(mopI);
-      SlotIndex opSlot = instSlot.getRegSlot(mop.isEarlyClobber());
-      if (opSlot > lastUseInRange && opSlot < oldIdx)
-        lastUseInRange = opSlot;
-    }
+public:
+  HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
+           const TargetRegisterInfo& TRI, SlotIndex NewIdx)
+    : LIS(LIS), MRI(MRI), TRI(TRI), NewIdx(NewIdx) {}
+
+  // Update intervals for all operands of MI from OldIdx to NewIdx.
+  // This assumes that MI used to be at OldIdx, and now resides at
+  // NewIdx.
+  void moveAllOperandsFrom(MachineInstr* MI, SlotIndex OldIdx) {
+    // Collect the operands.
+    RangeSet Entering, Internal, Exiting;
+    collectRanges(MI, Entering, Internal, Exiting, OldIdx);
 
-    // If we found a new instr endpoint update the kill flags.
-    if (lastUseInRange != newIdx.getRegSlot())
-      moveKillFlags(li.reg, newIdx, lastUseInRange);
+    moveAllEnteringFrom(OldIdx, Entering);
+    moveAllInternalFrom(OldIdx, Internal);
+    moveAllExitingFrom(OldIdx, Exiting);
 
-    // Fix up the range end.
-    lr.end = lastUseInRange;
+#ifndef NDEBUG
+    LIValidator validator;
+    std::for_each(Entering.begin(), Entering.end(), validator);
+    std::for_each(Internal.begin(), Internal.end(), validator);
+    std::for_each(Exiting.begin(), Exiting.end(), validator);
+    assert(validator.rangesOk() && "moveOperandsFrom broke liveness.");
+#endif
 
-    assert(intervalRangesSane(li) && "Broke live interval moving use.");
+// TODO: Update reg mask slots.
+//      assert((OldIdx == SlotIndex() || !MO.isRegMask()) &&
+//             "Unexpected RegMask operand.");
+//       if (MO.isRegMask()) {
+//         updateRegMaskSlots(OldIdx);
+//         continue;
+//       }
   }
 
-  // Update intervals for all operands of mi from oldIndex to newIndex.
-  void moveAllOperandsFrom(MachineInstr* mi, SlotIndex oldIdx) {
-    // Figure out the direction we're moving.
-    bool movingUp = newIdx < oldIdx;
+private:
 
-    // Collect the operands.
-    DenseSet<unsigned> uses, defs, deadDefs, ecs;
-    for (MachineInstr::mop_iterator mopItr = mi->operands_begin(),
-                                    mopEnd = mi->operands_end();
-         mopItr != mopEnd; ++mopItr) {
-      const MachineOperand& mop = *mopItr;
-
-      if (mop.isRegMask()) {
-        updateRegMaskSlots(oldIdx);
-        continue;
+#ifndef NDEBUG
+  class LIValidator {
+  private:
+    DenseSet<const LiveInterval*> Checked, Bogus;
+  public:
+    void operator()(const IntRangePair& P) {
+      const LiveInterval* LI = P.first;
+      if (Checked.count(LI))
+        return;
+      Checked.insert(LI);
+      if (LI->empty())
+        return;
+      SlotIndex LastEnd = LI->begin()->start;
+      for (LiveInterval::const_iterator LRI = LI->begin(), LRE = LI->end();
+           LRI != LRE; ++LRI) {
+        const LiveRange& LR = *LRI;
+        if (LastEnd > LR.start || LR.start >= LR.end)
+          Bogus.insert(LI);
+        LastEnd = LR.end;
       }
+    }
+
+    bool rangesOk() const {
+      return Bogus.empty();
+    }
+  };
+#endif
 
-      if (!mop.isReg() || mop.getReg() == 0)
+  // Collect IntRangePairs for all operands of MI that may need fixing.
+  // Treat's MI's index as OldIdx (regardless of what it is in SlotIndexes'
+  // maps).
+  void collectRanges(MachineInstr* MI, RangeSet& Entering, RangeSet& Internal,
+                     RangeSet& Exiting, SlotIndex OldIdx) {
+    for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
+                                    MOE = MI->operands_end();
+         MOI != MOE; ++MOI) {
+      const MachineOperand& MO = *MOI;
+      if (!MO.isReg() || MO.getReg() == 0)
         continue;
 
-      unsigned reg = mop.getReg();
+      unsigned Reg = MO.getReg();
 
       // TODO: Currently we're skipping uses that are reserved or have no
       // interval, but we're not updating their kills. This should be
       // fixed.
-      if (!lis.hasInterval(reg) ||
-          (TargetRegisterInfo::isPhysicalRegister(reg) && lis.isReserved(reg)))
+      if (!LIS.hasInterval(Reg) ||
+          (TargetRegisterInfo::isPhysicalRegister(Reg) && LIS.isReserved(Reg)))
         continue;
 
-      if (mop.readsReg() && !ecs.count(reg)) {
-        uses.insert(reg);
+      LiveInterval* LI = &LIS.getInterval(Reg);
+
+      if (MO.readsReg()) {
+        LiveRange* LR = LI->getLiveRangeContaining(OldIdx);
+        if (LR != 0)
+          Entering.insert(std::make_pair(LI, LR));
       }
-      if (mop.isDef()) {
-        if (mop.isDead()) {
-          assert(!defs.count(reg) && "Can't mix defs with dead-defs.");
-          deadDefs.insert(reg);
-        } else if (mop.isEarlyClobber()) {
-          uses.erase(reg);
-          ecs.insert(reg);
+      if (MO.isDef()) {
+        if (MO.isEarlyClobber()) {
+          LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot(true));
+          assert(LR != 0 && "No EC range?");
+          if (LR->end > OldIdx.getDeadSlot())
+            Exiting.insert(std::make_pair(LI, LR));
+          else
+            Internal.insert(std::make_pair(LI, LR));         
+        } else if (MO.isDead()) {
+          LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot());
+          assert(LR != 0 && "No dead-def range?");
+          Internal.insert(std::make_pair(LI, LR));
         } else {
-          assert(!deadDefs.count(reg) && "Can't mix defs with dead-defs.");
-          defs.insert(reg);
+          LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getDeadSlot());
+          assert(LR && LR->end > OldIdx.getDeadSlot() &&
+                 "Non-dead-def should have live range exiting.");
+          Exiting.insert(std::make_pair(LI, LR));
         }
       }
     }
-
-    if (movingUp) {
-      moveUsesUp(oldIdx, uses);
-      moveECs(oldIdx, ecs);
-      moveDeadDefs(oldIdx, deadDefs);
-      moveDefs(oldIdx, defs);
-    } else {
-      moveDefs(oldIdx, defs);
-      moveDeadDefs(oldIdx, deadDefs);
-      moveECs(oldIdx, ecs);
-      moveUsesDown(oldIdx, uses, mi->getParent());
-    }
   }
 
-private:
+  void moveKillFlags(unsigned reg, SlotIndex OldIdx, SlotIndex newKillIdx) {
+    MachineInstr* OldKillMI = LIS.getInstructionFromIndex(OldIdx);
+    if (!OldKillMI->killsRegister(reg))
+      return; // Bail out if we don't have kill flags on the old register.
+    MachineInstr* NewKillMI = LIS.getInstructionFromIndex(newKillIdx);
+    assert(OldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill.");
+    assert(!NewKillMI->killsRegister(reg) && "New kill instr is already a kill.");
+    OldKillMI->clearRegisterKills(reg, &TRI);
+    NewKillMI->addRegisterKilled(reg, &TRI);
+  }
 
-#ifndef NDEBUG
-    bool intervalRangesSane(const LiveInterval& li) {
-    if (li.empty()) {
-      return true;
-    }
+  void updateRegMaskSlots(SlotIndex OldIdx) {
+    SmallVectorImpl<SlotIndex>::iterator RI =
+      std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(),
+                       OldIdx);
+    assert(*RI == OldIdx && "No RegMask at OldIdx.");
+    *RI = NewIdx;
+    assert(*prior(RI) < *RI && *RI < *next(RI) &&
+           "RegSlots out of order. Did you move one call across another?");
+  }
 
-    SlotIndex lastEnd = li.begin()->start;
-    for (LiveInterval::const_iterator lrItr = li.begin(), lrEnd = li.end();
-         lrItr != lrEnd; ++lrItr) {
-      const LiveRange& lr = *lrItr;
-      if (lastEnd > lr.start || lr.start >= lr.end)
-        return false;
-      lastEnd = lr.end;
+  // Return the last use of reg between NewIdx and OldIdx.
+  SlotIndex findLastUseBefore(unsigned Reg, SlotIndex OldIdx) {
+    SlotIndex LastUse = NewIdx;
+    for (MachineRegisterInfo::use_nodbg_iterator
+           UI = MRI.use_nodbg_begin(Reg),
+           UE = MRI.use_nodbg_end();
+         UI != UE; ++UI) {
+      const MachineInstr* MI = &*UI;
+      SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
+      if (InstSlot > LastUse && InstSlot < OldIdx)
+        LastUse = InstSlot;
     }
-
-    return true;
+    return LastUse;
   }
-#endif
 
-  void moveKillFlags(unsigned reg, SlotIndex oldIdx, SlotIndex newKillIdx) {
-    MachineInstr* oldKillMI = lis.getInstructionFromIndex(oldIdx);
-    if (!oldKillMI->killsRegister(reg))
-      return; // Bail out if we don't have kill flags on the old register.
-    MachineInstr* newKillMI = lis.getInstructionFromIndex(newKillIdx);
-    assert(oldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill.");
-    assert(!newKillMI->killsRegister(reg) && "New kill instr is already a kill.");
-    oldKillMI->clearRegisterKills(reg, lis.tri_);
-    newKillMI->addRegisterKilled(reg, lis.tri_);
+  void moveEnteringUpFrom(SlotIndex OldIdx, IntRangePair& P) {
+    LiveInterval* LI = P.first;
+    LiveRange* LR = P.second;
+    bool LiveThrough = LR->end > OldIdx.getRegSlot();
+    if (LiveThrough)
+      return;
+    SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx);
+    if (LastUse != NewIdx)
+      moveKillFlags(LI->reg, NewIdx, LastUse);
+    LR->end = LastUse.getRegSlot(LR->end.isEarlyClobber());
   }
 
-  template <typename DefSetT>
-  void moveDefs(SlotIndex oldIdx, const DefSetT& defs) {
-    typedef typename DefSetT::const_iterator DefItr;
-    for (DefItr di = defs.begin(), de = defs.end(); di != de; ++di) {
-      unsigned def = *di;
-      LiveInterval& li = lis.getInterval(def);
-      LiveRange* lr = li.getLiveRangeContaining(oldIdx.getRegSlot());
-      assert(lr != 0 && "No range?");
-      moveDef(*lr, li);
+  void moveEnteringDownFrom(SlotIndex OldIdx, IntRangePair& P) {
+    LiveInterval* LI = P.first;
+    LiveRange* LR = P.second;
+    bool LiveThrough = LR->end > OldIdx.getRegSlot();
+    if (LiveThrough) {
+      MachineBasicBlock* MBB = LIS.getInstructionFromIndex(NewIdx)->getParent();
+      bool LiveOut = LR->end >= LIS.getSlotIndexes()->getMBBEndIdx(MBB);
+      if (!LiveOut) {
+        moveKillFlags(LI->reg, LR->end, NewIdx);
+        LR->end = NewIdx.getRegSlot(LR->end.isEarlyClobber());
+      }
+    } else {
+      // Not live through. Easy - just update the range endpoint.
+      LR->end = NewIdx.getRegSlot(LR->end.isEarlyClobber());
     }
   }
 
-  template <typename DeadDefSetT>
-  void moveDeadDefs(SlotIndex oldIdx, const DeadDefSetT& deadDefs) {
-    typedef typename DeadDefSetT::const_iterator DeadDefItr;
-    for (DeadDefItr di = deadDefs.begin(),de = deadDefs.end(); di != de; ++di) {
-      unsigned deadDef = *di;
-      LiveInterval& li = lis.getInterval(deadDef);
-      LiveRange* lr = li.getLiveRangeContaining(oldIdx.getRegSlot());
-      assert(lr != 0 && "No range for dead def?");
-      assert(lr->start == oldIdx.getRegSlot() && "Bad dead range start?");
-      assert(lr->end == oldIdx.getDeadSlot() && "Bad dead range end?");
-      assert(lr->valno->def == oldIdx.getRegSlot() && "Bad dead valno def.");
-      moveDeadDefOrEC(*lr, li, false);
+  void moveAllEnteringFrom(SlotIndex OldIdx, RangeSet& Entering) {
+    bool GoingUp = NewIdx < OldIdx;
+
+    if (GoingUp) {
+      for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
+           EI != EE; ++EI)
+        moveEnteringUpFrom(OldIdx, *EI);
+    } else {
+      for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
+           EI != EE; ++EI)
+        moveEnteringDownFrom(OldIdx, *EI);
     }
   }
 
-  template <typename ECSetT>
-  void moveECs(SlotIndex oldIdx, const ECSetT& ecs) {
-    typedef typename ECSetT::const_iterator ECItr;
-    for (ECItr eci = ecs.begin(), ece = ecs.end(); eci != ece; ++eci) {
-      unsigned ec = *eci;
-      LiveInterval& li = lis.getInterval(ec);
-      LiveRange* lr = li.getLiveRangeContaining(oldIdx.getRegSlot(true));
-      assert(lr != 0 && "No range for early clobber?");
-      assert(lr->start == oldIdx.getRegSlot(true) && "Bad EC range start?");
-      assert(lr->end == oldIdx.getRegSlot() && "Bad EC range end.");
-      assert(lr->valno->def == oldIdx.getRegSlot(true) && "Bad EC valno def.");
-      moveDeadDefOrEC(*lr, li, true);
-    }
+  void moveInternalFrom(SlotIndex OldIdx, IntRangePair& P) {
+    LiveInterval* LI = P.first;
+    LiveRange* LR = P.second;
+    assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() &&
+           LR->end <= OldIdx.getDeadSlot() &&
+           "Range should be internal to OldIdx.");
+    LiveRange Tmp(*LR);
+    Tmp.start = NewIdx.getRegSlot(LR->start.isEarlyClobber());
+    Tmp.valno->def = Tmp.start;
+    Tmp.end = LR->end.isDead() ? NewIdx.getDeadSlot() : NewIdx.getRegSlot();
+    LI->removeRange(*LR);
+    LI->addRange(Tmp);
   }
 
-  template <typename UseSetT>
-  void moveUsesUp(SlotIndex oldIdx, const UseSetT &uses) {
-    typedef typename UseSetT::const_iterator UseItr;
-    for (UseItr ui = uses.begin(), ue = uses.end(); ui != ue; ++ui) {
-      unsigned use = *ui;
-      LiveInterval& li = lis.getInterval(use);
-      LiveRange* lr = li.getLiveRangeBefore(oldIdx.getRegSlot());
-      assert(lr != 0 && "No range for use?");
-      moveUseUp(oldIdx, *lr, li);
-    }
+  void moveAllInternalFrom(SlotIndex OldIdx, RangeSet& Internal) {
+    for (RangeSet::iterator II = Internal.begin(), IE = Internal.end();
+         II != IE; ++II)
+      moveInternalFrom(OldIdx, *II);
   }
 
-  template <typename UseSetT>
-  void moveUsesDown(SlotIndex oldIdx, const UseSetT &uses,
-                    const MachineBasicBlock* mbb) {
-    typedef typename UseSetT::const_iterator UseItr;
-    for (UseItr ui = uses.begin(), ue = uses.end(); ui != ue; ++ui) {
-      unsigned use = *ui;
-      LiveInterval& li = lis.getInterval(use);
-      LiveRange* lr = li.getLiveRangeBefore(oldIdx.getRegSlot());
-      assert(lr != 0 && "No range for use?");
-      moveUseDown(oldIdx, *lr, li, mbb);
-    }
+  void moveExitingFrom(SlotIndex OldIdx, IntRangePair& P) {
+    LiveRange* LR = P.second;
+    assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() &&
+           "Range should start in OldIdx.");
+    assert(LR->end > OldIdx.getDeadSlot() && "Range should exit OldIdx.");
+    SlotIndex NewStart = NewIdx.getRegSlot(LR->start.isEarlyClobber());
+    LR->start = NewStart;
+    LR->valno->def = NewStart;
   }
 
-  void updateRegMaskSlots(SlotIndex oldIdx) {
-    SmallVectorImpl<SlotIndex>::iterator rmItr =
-      std::lower_bound(lis.RegMaskSlots.begin(), lis.RegMaskSlots.end(),
-                       oldIdx);
-    assert(*rmItr == oldIdx && "No RegMask at oldIdx.");
-    *rmItr = newIdx;
-    assert(*prior(rmItr) < *rmItr && *rmItr < *next(rmItr) &&
-           "RegSlots out of order. Did you move one call across another?");
+  void moveAllExitingFrom(SlotIndex OldIdx, RangeSet& Exiting) {
+    for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end();
+         EI != EE; ++EI)
+      moveExitingFrom(OldIdx, *EI);
   }
+
 };
 
-void LiveIntervals::handleMove(MachineInstr* mi) {
-  SlotIndex oldIndex = indexes_->getInstructionIndex(mi);
-  indexes_->removeMachineInstrFromMaps(mi);
-  SlotIndex newIndex = mi->isInsideBundle() ?
-                        indexes_->getInstructionIndex(mi->getBundleStart()) :
-                        indexes_->insertMachineInstrInMaps(mi);
-  assert(getMBBStartIdx(mi->getParent()) <= oldIndex &&
-         oldIndex < getMBBEndIdx(mi->getParent()) &&
+void LiveIntervals::handleMove(MachineInstr* MI) {
+  SlotIndex OldIndex = indexes_->getInstructionIndex(MI);
+  indexes_->removeMachineInstrFromMaps(MI);
+  SlotIndex NewIndex = MI->isInsideBundle() ?
+                        indexes_->getInstructionIndex(MI->getBundleStart()) :
+                        indexes_->insertMachineInstrInMaps(MI);
+  assert(getMBBStartIdx(MI->getParent()) <= OldIndex &&
+         OldIndex < getMBBEndIdx(MI->getParent()) &&
          "Cannot handle moves across basic block boundaries.");
-  assert(!mi->isBundled() && "Can't handle bundled instructions yet.");
+  assert(!MI->isBundled() && "Can't handle bundled instructions yet.");
 
-  HMEditor hme(*this, newIndex);
-  hme.moveAllOperandsFrom(mi, oldIndex);
+  HMEditor HME(*this, *mri_, *tri_, NewIndex);
+  HME.moveAllOperandsFrom(MI, OldIndex);
 }