Copy single reaching defs directly into the LiveInterval.

When findReachingDefs() finds that only one value can reach the basic
block, just copy the work list of visited blocks directly into the live
interval.

Sort the block list and use a LiveRangeUpdater to make the bulk add
fast.

When multiple reaching defs are found, transfer the work list to the
updateSSA() work list as before. Also use LiveRangeUpdater in
updateLiveIns() following updateSSA().

This makes live interval analysis more than 3x faster on one huge test
case.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175685 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/CodeGen/LiveRangeCalc.cpp b/lib/CodeGen/LiveRangeCalc.cpp
index c3ff4f1b6d2eb6708cdd5c0f3ca31da28b7f402c..dede490d91bac4aeb61e915fdfbe106d6ff2c82b 100644 (file)
--- 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;
@@ -104,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();
 }
@@ -150,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();
 }
 
 
@@ -167,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;
@@ -184,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()) {
@@ -231,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;
 }
 
 

diff --git a/lib/CodeGen/LiveRangeCalc.h b/lib/CodeGen/LiveRangeCalc.h
index 909829b228519c5c16364be0cffb298c82782c59..57cab7b3422081e4f2fc951d4b92bd51c0bdfa7d 100644 (file)
--- a/lib/CodeGen/LiveRangeCalc.h
+++ b/lib/CodeGen/LiveRangeCalc.h
@@ -34,6 +34,7 @@ template <class NodeT> class DomTreeNodeBase;
 typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
 
 class LiveRangeCalc {
+  const MachineFunction *MF;
   const MachineRegisterInfo *MRI;
   SlotIndexes *Indexes;
   MachineDominatorTree *DomTree;
@@ -100,17 +101,20 @@ class LiveRangeCalc {
   /// used to add entries directly.
   SmallVector<LiveInBlock, 16> LiveIn;
 
-  /// findReachingDefs - Assuming that LI is live-in to KillMBB and killed at
-  /// Kill, search for values that can reach KillMBB.  All blocks that need LI
-  /// to be live-in are added to LiveIn.  If a unique reaching def is found,
-  /// its value is returned, if Kill is jointly dominated by multiple values,
-  /// NULL is returned.
+  /// Assuming that LI is live-in to KillMBB and killed at Kill, find the set
+  /// of defs that can reach it.
+  ///
+  /// If only one def can reach Kill, all paths from the def to kill are added
+  /// to LI, and the function returns true.
+  ///
+  /// If multiple values can reach Kill, the blocks that need LI to be live in
+  /// are added to the LiveIn array, and the function returns false.
   ///
   /// PhysReg, when set, is used to verify live-in lists on basic blocks.
-  VNInfo *findReachingDefs(LiveInterval *LI,
-                           MachineBasicBlock *KillMBB,
-                           SlotIndex Kill,
-                           unsigned PhysReg);
+  bool findReachingDefs(LiveInterval *LI,
+                        MachineBasicBlock *KillMBB,
+                        SlotIndex Kill,
+                        unsigned PhysReg);
 
   /// updateSSA - Compute the values that will be live in to all requested
   /// blocks in LiveIn.  Create PHI-def values as required to preserve SSA form.
@@ -119,12 +123,11 @@ class LiveRangeCalc {
   /// blocks.  No values are read from the live ranges.
   void updateSSA();
 
-  /// updateLiveIns - Add liveness as specified in the LiveIn vector, using VNI
-  /// as a wildcard value for LiveIn entries without a value.
-  void updateLiveIns(VNInfo *VNI);
+  /// Add liveness as specified in the LiveIn vector.
+  void updateLiveIns();
 
 public:
-  LiveRangeCalc() : MRI(0), Indexes(0), DomTree(0), Alloc(0) {}
+  LiveRangeCalc() : MF(0), MRI(0), Indexes(0), DomTree(0), Alloc(0) {}
 
   //===--------------------------------------------------------------------===//
   // High-level interface.