Speed up LiveIntervals::shrinkToUse with some caching.

Blocks with multiple PHI successors only need to go on the worklist
once.  Use a SmallPtrSet to track the live-out blocks that have already
been handled.  This is a lot faster than the two live range check we
would otherwise do.

Also stop recomputing hasPHIKill flags.  Like RenumberValues(), it is
conservatively correct to leave them in, and they are not used for
anything important.

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

1 files changed, 8 insertions, 6 deletions

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index c4a548f9ea..cacbd0a61b 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -747,6 +747,9 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li,
   // Find all the values used, including PHI kills.
   SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
 
+  // Blocks that have already been added to WorkList as live-out.
+  SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
+
   // Visit all instructions reading li->reg.
   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg);
        MachineInstr *UseMI = I.skipInstruction();) {
@@ -780,8 +783,6 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li,
     VNInfo *VNI = *I;
     if (VNI->isUnused())
       continue;
-    // We may eliminate PHI values, so recompute PHIKill flags.
-    VNI->setHasPHIKill(false);
     NewLI.addRange(LiveRange(VNI->def, VNI->def.getNextSlot(), VNI));
 
     // A use tied to an early-clobber def ends at the load slot and isn't caught
@@ -813,13 +814,12 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li,
       // The PHI is live, make sure the predecessors are live-out.
       for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
            PE = MBB->pred_end(); PI != PE; ++PI) {
+        if (!LiveOut.insert(*PI))
+          continue;
         SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
-        VNInfo *PVNI = li->getVNInfoAt(Stop);
         // A predecessor is not required to have a live-out value for a PHI.
-        if (PVNI) {
-          PVNI->setHasPHIKill(true);
+        if (VNInfo *PVNI = li->getVNInfoAt(Stop))
           WorkList.push_back(std::make_pair(Stop, PVNI));
-        }
       }
       continue;
     }
@@ -831,6 +831,8 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li,
     // Make sure VNI is live-out from the predecessors.
     for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
          PE = MBB->pred_end(); PI != PE; ++PI) {
+      if (!LiveOut.insert(*PI))
+        continue;
       SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
       assert(li->getVNInfoAt(Stop) == VNI && "Wrong value out of predecessor");
       WorkList.push_back(std::make_pair(Stop, VNI));