IntervalMap iterators are heavyweight, so avoid copying them around and use

references instead.

Similarly, IntervalMap::begin() is almost as expensive as find(), so use find(x)
instead of begin().advanceTo(x);

This makes RegAllocBasic run another 5% faster.

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

1 files changed, 20 insertions, 3 deletions

diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp
index 4b9a2d302c..1fca034fdc 100644
--- a/lib/CodeGen/LiveIntervalUnion.cpp
+++ b/lib/CodeGen/LiveIntervalUnion.cpp
@@ -144,12 +144,29 @@ void LiveIntervalUnion::Query::findIntersection(InterferenceResult &IR) const {
 
 // Find the first intersection, and cache interference info
 // (retain segment iterators into both VirtReg and LiveUnion).
-LiveIntervalUnion::InterferenceResult
+const LiveIntervalUnion::InterferenceResult &
 LiveIntervalUnion::Query::firstInterference() {
-  if (FirstInterference != LiveIntervalUnion::InterferenceResult()) {
+  if (CheckedFirstInterference)
     return FirstInterference;
+  CheckedFirstInterference = true;
+  InterferenceResult &IR = FirstInterference;
+
+  // Quickly skip interference check for empty sets.
+  if (VirtReg->empty() || LiveUnion->empty()) {
+    IR.VirtRegI = VirtReg->end();
+  } else if (VirtReg->beginIndex() < LiveUnion->startIndex()) {
+    // VirtReg starts first, perform double binary search.
+    IR.VirtRegI = VirtReg->find(LiveUnion->startIndex());
+    if (IR.VirtRegI != VirtReg->end())
+      IR.LiveUnionI = LiveUnion->find(IR.VirtRegI->start);
+  } else {
+    // LiveUnion starts first, perform double binary search.
+    IR.LiveUnionI = LiveUnion->find(VirtReg->beginIndex());
+    if (IR.LiveUnionI.valid())
+      IR.VirtRegI = VirtReg->find(IR.LiveUnionI.start());
+    else
+      IR.VirtRegI = VirtReg->end();
   }
-  FirstInterference = InterferenceResult(VirtReg->begin(), LiveUnion->begin());
   findIntersection(FirstInterference);
   return FirstInterference;
 }