From 4e996de58cfad27033165d8feb8f296b8cbe20ca Mon Sep 17 00:00:00 2001
From: Chandler Carruth <chandlerc@gmail.com>
Date: Tue, 10 Jul 2012 22:25:21 +0000
Subject: [PATCH] Teach the LiveInterval::join function to use the fast merge
 algorithm, generalizing its implementation sufficiently to support this value
 number scenario as well.

This cuts out another significant performance hit in large functions
(over 10k basic blocks, etc), especially those with "natural" CFG
structures.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160026 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/CodeGen/LiveInterval.h |  2 +-
 lib/CodeGen/LiveInterval.cpp        | 31 ++++++++++++++++-------------
 2 files changed, 18 insertions(+), 15 deletions(-)

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index 83a3b43876e..3fe7c8d58cd 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -505,7 +505,7 @@ namespace llvm {
     Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr);
     void markValNoForDeletion(VNInfo *V);
     void mergeIntervalRanges(const LiveInterval &RHS,
-                             VNInfo *LHSValNo,
+                             VNInfo *LHSValNo = 0,
                              const VNInfo *RHSValNo = 0);
 
     LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 9342439cc3d..01077db92fd 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -450,14 +450,13 @@ void LiveInterval::join(LiveInterval &Other,
     valnos.resize(NumNewVals);  // shrinkify
 
   // Okay, now insert the RHS live ranges into the LHS.
-  iterator InsertPos = begin();
   unsigned RangeNo = 0;
   for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) {
     // Map the valno in the other live range to the current live range.
     I->valno = NewVNInfo[OtherAssignments[RangeNo]];
     assert(I->valno && "Adding a dead range?");
-    InsertPos = addRangeFrom(*I, InsertPos);
   }
+  mergeIntervalRanges(Other);
 
   verify();
 }
@@ -467,8 +466,8 @@ void LiveInterval::join(LiveInterval &Other,
 /// This is a helper routine implementing an efficient merge of another
 /// LiveIntervals ranges into the current interval.
 ///
-/// \param LHSValNo Set as the new value number for every range from RHS which
-///                 is merged into the LHS.
+/// \param LHSValNo If non-NULL, set as the new value number for every range
+///                 from RHS which is merged into the LHS.
 /// \param RHSValNo If non-NULL, then only ranges in RHS whose original value
 ///                 number maches this value number will be merged into LHS.
 void LiveInterval::mergeIntervalRanges(const LiveInterval &RHS,
@@ -477,9 +476,10 @@ void LiveInterval::mergeIntervalRanges(const LiveInterval &RHS,
   if (RHS.empty())
     return;
 
-  // Ensure we're starting with valid ranges.
+  // Ensure we're starting with a valid range. Note that we don't verify RHS
+  // because it may have had its value numbers adjusted in preparation for
+  // merging.
   verify();
-  RHS.verify();
 
   // The strategy for merging these efficiently is as follows:
   //
@@ -529,7 +529,8 @@ void LiveInterval::mergeIntervalRanges(const LiveInterval &RHS,
     if (*RI < R) {
       R = *RI;
       ++RI;
-      R.valno = LHSValNo;
+      if (LHSValNo)
+        R.valno = LHSValNo;
     } else {
       ++LI;
     }
@@ -578,14 +579,16 @@ void LiveInterval::mergeIntervalRanges(const LiveInterval &RHS,
     ranges.insert(LI, NRI, NRE);
 
   // And finally insert any trailing end of RHS (if we have one).
-  for (; RI != RE; ++RI)
+  for (; RI != RE; ++RI) {
+    LiveRange R = *RI;
+    if (LHSValNo)
+      R.valno = LHSValNo;
     if (!ranges.empty() &&
-        ranges.back().valno == LHSValNo && RI->start <= ranges.back().end) {
-      ranges.back().end = std::max(ranges.back().end, RI->end);
-    } else {
-      ranges.push_back(*RI);
-      ranges.back().valno = LHSValNo;
-    }
+        ranges.back().valno == R.valno && R.start <= ranges.back().end)
+      ranges.back().end = std::max(ranges.back().end, R.end);
+    else
+      ranges.push_back(R);
+  }
 
   // Ensure we finished with a valid new sequence of ranges.
   verify();
-- 
2.34.1