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
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;
}