From e6dc3c899ef0dcce9ccb1117542f435d5a70d089 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Thu, 9 Dec 2010 01:06:52 +0000 Subject: 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. llvm-svn: 121344 --- llvm/lib/CodeGen/LiveIntervalUnion.cpp | 23 ++++++++++++++++++++--- 1 file changed, 20 insertions(+), 3 deletions(-) (limited to 'llvm/lib/CodeGen/LiveIntervalUnion.cpp') diff --git a/llvm/lib/CodeGen/LiveIntervalUnion.cpp b/llvm/lib/CodeGen/LiveIntervalUnion.cpp index 4b9a2d302c0..1fca034fdcb 100644 --- a/llvm/lib/CodeGen/LiveIntervalUnion.cpp +++ b/llvm/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; } -- cgit v1.2.3