X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveRangeCalc.cpp;h=dede490d91bac4aeb61e915fdfbe106d6ff2c82b;hb=9bcad42c3aadab118b6ed5f30f2ea0d87228fd3f;hp=d828f25932e72e69e6f186f18b22284e49dc8c41;hpb=b18d779b35909cd5b753871f8bf2ff4f6c17ace1;p=oota-llvm.git

diff --git a/lib/CodeGen/LiveRangeCalc.cpp b/lib/CodeGen/LiveRangeCalc.cpp
index d828f25932e..dede490d91b 100644
--- a/lib/CodeGen/LiveRangeCalc.cpp
+++ b/lib/CodeGen/LiveRangeCalc.cpp
@@ -18,10 +18,11 @@
 
 using namespace llvm;
 
-void LiveRangeCalc::reset(const MachineFunction *MF,
+void LiveRangeCalc::reset(const MachineFunction *mf,
                           SlotIndexes *SI,
                           MachineDominatorTree *MDT,
                           VNInfo::Allocator *VNIA) {
+  MF = mf;
   MRI = &MF->getRegInfo();
   Indexes = SI;
   DomTree = MDT;
@@ -65,7 +66,11 @@ void LiveRangeCalc::extendToUses(LiveInterval *LI, unsigned Reg) {
   // Visit all operands that read Reg. This may include partial defs.
   for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
        E = MRI->reg_nodbg_end(); I != E; ++I) {
-    const MachineOperand &MO = I.getOperand();
+    MachineOperand &MO = I.getOperand();
+    // Clear all kill flags. They will be reinserted after register allocation
+    // by LiveIntervalAnalysis::addKillFlags().
+    if (MO.isUse())
+      MO.setIsKill(false);
     if (!MO.readsReg())
       continue;
     // MI is reading Reg. We may have visited MI before if it happens to be
@@ -100,28 +105,28 @@ void LiveRangeCalc::extendToUses(LiveInterval *LI, unsigned Reg) {
 
 
 // Transfer information from the LiveIn vector to the live ranges.
-void LiveRangeCalc::updateLiveIns(VNInfo *OverrideVNI) {
+void LiveRangeCalc::updateLiveIns() {
+  LiveRangeUpdater Updater;
   for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
          E = LiveIn.end(); I != E; ++I) {
     if (!I->DomNode)
       continue;
     MachineBasicBlock *MBB = I->DomNode->getBlock();
-
-    VNInfo *VNI = OverrideVNI ? OverrideVNI : I->Value;
-    assert(VNI && "No live-in value found");
-
+    assert(I->Value && "No live-in value found");
     SlotIndex Start, End;
     tie(Start, End) = Indexes->getMBBRange(MBB);
 
     if (I->Kill.isValid())
-      I->LI->addRange(LiveRange(Start, I->Kill, VNI));
+      // Value is killed inside this block.
+      End = I->Kill;
     else {
-      I->LI->addRange(LiveRange(Start, End, VNI));
-      // The value is live-through, update LiveOut as well.  Defer the Domtree
-      // lookup until it is needed.
+      // The value is live-through, update LiveOut as well.
+      // Defer the Domtree lookup until it is needed.
       assert(Seen.test(MBB->getNumber()));
-      LiveOut[MBB] = LiveOutPair(VNI, (MachineDomTreeNode *)0);
+      LiveOut[MBB] = LiveOutPair(I->Value, (MachineDomTreeNode *)0);
     }
+    Updater.setDest(I->LI);
+    Updater.add(Start, End, I->Value);
   }
   LiveIn.clear();
 }
@@ -146,13 +151,11 @@ void LiveRangeCalc::extend(LiveInterval *LI,
   // multiple values, and we may need to create even more phi-defs to preserve
   // VNInfo SSA form.  Perform a search for all predecessor blocks where we
   // know the dominating VNInfo.
-  VNInfo *VNI = findReachingDefs(LI, KillMBB, Kill, PhysReg);
+  if (findReachingDefs(LI, KillMBB, Kill, PhysReg))
+    return;
 
   // When there were multiple different values, we may need new PHIs.
-  if (!VNI)
-    updateSSA();
-
-  updateLiveIns(VNI);
+  calculateValues();
 }
 
 
@@ -163,16 +166,18 @@ void LiveRangeCalc::calculateValues() {
   assert(Indexes && "Missing SlotIndexes");
   assert(DomTree && "Missing dominator tree");
   updateSSA();
-  updateLiveIns(0);
+  updateLiveIns();
 }
 
 
-VNInfo *LiveRangeCalc::findReachingDefs(LiveInterval *LI,
-                                        MachineBasicBlock *KillMBB,
-                                        SlotIndex Kill,
-                                        unsigned PhysReg) {
-  // Blocks where LI should be live-in.
-  SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB);
+bool LiveRangeCalc::findReachingDefs(LiveInterval *LI,
+                                     MachineBasicBlock *KillMBB,
+                                     SlotIndex Kill,
+                                     unsigned PhysReg) {
+  unsigned KillMBBNum = KillMBB->getNumber();
+
+  // Block numbers where LI should be live-in.
+  SmallVector<unsigned, 16> WorkList(1, KillMBBNum);
 
   // Remember if we have seen more than one value.
   bool UniqueVNI = true;
@@ -180,7 +185,7 @@ VNInfo *LiveRangeCalc::findReachingDefs(LiveInterval *LI,
 
   // Using Seen as a visited set, perform a BFS for all reaching defs.
   for (unsigned i = 0; i != WorkList.size(); ++i) {
-    MachineBasicBlock *MBB = WorkList[i];
+    MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
 
 #ifndef NDEBUG
     if (MBB->pred_empty()) {
@@ -227,25 +232,50 @@ VNInfo *LiveRangeCalc::findReachingDefs(LiveInterval *LI,
 
        // No, we need a live-in value for Pred as well
        if (Pred != KillMBB)
-          WorkList.push_back(Pred);
+          WorkList.push_back(Pred->getNumber());
        else
           // Loopback to KillMBB, so value is really live through.
          Kill = SlotIndex();
     }
   }
 
-  // Transfer WorkList to LiveInBlocks in reverse order.
-  // This ordering works best with updateSSA().
   LiveIn.clear();
-  LiveIn.reserve(WorkList.size());
-  while(!WorkList.empty())
-    addLiveInBlock(LI, DomTree->getNode(WorkList.pop_back_val()));
 
-  // The kill block may not be live-through.
-  assert(LiveIn.back().DomNode->getBlock() == KillMBB);
-  LiveIn.back().Kill = Kill;
+  // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
+  // neither require it. Skip the sorting overhead for small updates.
+  if (WorkList.size() > 4)
+    array_pod_sort(WorkList.begin(), WorkList.end());
+
+  // If a unique reaching def was found, blit in the live ranges immediately.
+  if (UniqueVNI) {
+    LiveRangeUpdater Updater(LI);
+    for (SmallVectorImpl<unsigned>::const_iterator
+         I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
+       SlotIndex Start, End;
+       tie(Start, End) = Indexes->getMBBRange(*I);
+       // Trim the live range in KillMBB.
+       if (*I == KillMBBNum && Kill.isValid())
+         End = Kill;
+       else
+         LiveOut[MF->getBlockNumbered(*I)] =
+           LiveOutPair(TheVNI, (MachineDomTreeNode *)0);
+       Updater.add(Start, End, TheVNI);
+    }
+    return true;
+  }
+
+  // Multiple values were found, so transfer the work list to the LiveIn array
+  // where UpdateSSA will use it as a work list.
+  LiveIn.reserve(WorkList.size());
+  for (SmallVectorImpl<unsigned>::const_iterator
+       I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
+    MachineBasicBlock *MBB = MF->getBlockNumbered(*I);
+    addLiveInBlock(LI, DomTree->getNode(MBB));
+    if (MBB == KillMBB)
+      LiveIn.back().Kill = Kill;
+  }
 
-  return UniqueVNI ? TheVNI : 0;
+  return false;
 }