diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp
index 4b9a2d3..1fca034 100644
--- a/lib/CodeGen/LiveIntervalUnion.cpp
+++ b/lib/CodeGen/LiveIntervalUnion.cpp
@@ -144,12 +144,29 @@
 
 // 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;
 }
diff --git a/lib/CodeGen/LiveIntervalUnion.h b/lib/CodeGen/LiveIntervalUnion.h
index 0c9a13a..4425582 100644
--- a/lib/CodeGen/LiveIntervalUnion.h
+++ b/lib/CodeGen/LiveIntervalUnion.h
@@ -75,7 +75,9 @@
   // by their starting position.
   SegmentIter begin() { return Segments.begin(); }
   SegmentIter end() { return Segments.end(); }
+  SegmentIter find(SlotIndex x) { return Segments.find(x); }
   bool empty() { return Segments.empty(); }
+  SlotIndex startIndex() { return Segments.start(); }
 
   // Add a live virtual register to this union and merge its segments.
   void unify(LiveInterval &VirtReg);
@@ -135,6 +137,7 @@
     LiveInterval *VirtReg;
     InterferenceResult FirstInterference;
     SmallVector<LiveInterval*,4> InterferingVRegs;
+    bool CheckedFirstInterference;
     bool SeenAllInterferences;
     bool SeenUnspillableVReg;
 
@@ -149,8 +152,8 @@
     void clear() {
       LiveUnion = NULL;
       VirtReg = NULL;
-      FirstInterference = InterferenceResult();
       InterferingVRegs.clear();
+      CheckedFirstInterference = false;
       SeenAllInterferences = false;
       SeenUnspillableVReg = false;
     }
@@ -187,7 +190,7 @@
 
     // Get the first pair of interfering segments, or a noninterfering result.
     // This initializes the firstInterference_ cache.
-    InterferenceResult firstInterference();
+    const InterferenceResult &firstInterference();
 
     // Treat the result as an iterator and advance to the next interfering pair
     // of segments. Visiting each unique interfering pairs means that the same