V4 regalloc: fix intersection calculation.

The previous version was plain wrong: when the first interval had more
than one range, those ranges would never be checked for intersection.

This version iterates over all ranges in the first interval, and returns
the index of the first range in the second interval that overlaps with
that range. Iterating over the second interval is cut off when an
interval is found that starts after the current one end (the ranges of
both intervals are sorted).

Change-Id: I87c254a645164eb6639925c2e3b7fd7c1b1bfa0a
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

1 files changed, 10 insertions, 7 deletions

diff --git a/src/qml/compiler/qv4regalloc.cpp b/src/qml/compiler/qv4regalloc.cpp
index 7ba4bc0ff6..ecf35d46a1 100644
--- a/src/qml/compiler/qv4regalloc.cpp
+++ b/src/qml/compiler/qv4regalloc.cpp
@@ -1004,9 +1004,9 @@ void RegisterAllocator::run(Function *function, const Optimizer &opt)
     {
         QTextStream qout(stdout, QIODevice::WriteOnly);
         qout << "Ranges:" << endl;
-        QList<LifeTimeInterval> handled = _unhandled;
-        std::sort(handled.begin(), handled.end(), LifeTimeInterval::lessThanForTemp);
-        foreach (const LifeTimeInterval &r, handled) {
+        QList<LifeTimeInterval> intervals = _unhandled;
+        std::sort(intervals.begin(), intervals.end(), LifeTimeInterval::lessThanForTemp);
+        foreach (const LifeTimeInterval &r, intervals) {
             r.dump(qout);
             qout << endl;
         }
@@ -1361,14 +1361,17 @@ int RegisterAllocator::nextIntersection(const LifeTimeInterval &current,
         return -1;
 
     LifeTimeInterval::Ranges anotherRanges = another.ranges();
-    int anotherIt = indexOfRangeCoveringPosition(anotherRanges, position);
-    if (anotherIt == -1)
+    const int anotherItStart = indexOfRangeCoveringPosition(anotherRanges, position);
+    if (anotherItStart == -1)
         return -1;
 
     for (int currentEnd = currentRanges.size(); currentIt < currentEnd; ++currentIt) {
         const LifeTimeInterval::Range &currentRange = currentRanges[currentIt];
-        for (int anotherEnd = anotherRanges.size(); anotherIt < anotherEnd; ++anotherIt) {
-            int intersectPos = intersectionPosition(currentRange, anotherRanges[anotherIt]);
+        for (int anotherIt = anotherItStart, anotherEnd = anotherRanges.size(); anotherIt < anotherEnd; ++anotherIt) {
+            const LifeTimeInterval::Range &anotherRange = anotherRanges[anotherIt];
+            if (anotherRange.start > currentRange.end)
+                break;
+            int intersectPos = intersectionPosition(currentRange, anotherRange);
             if (intersectPos != -1)
                 return intersectPos;
         }