Bug 941652 - IonMonkey: Fix quadradic-time insertion into LiveInterval use lists. r=bhackett
authorDan Gohman <sunfish@google.com>
Sat, 23 Nov 2013 10:38:24 -0800
changeset 157208 baa8541a972e11774d479cb0dadacba2ba53b590
parent 157207 2dc657af34755b67ab1240d0f22d176d8ef68ac2
child 157209 5dd26577d0935184f84bc15cfccffd6174f3e5c7
push id36650
push usersunfish@google.com
push dateSat, 23 Nov 2013 19:06:36 +0000
treeherdermozilla-inbound@baa8541a972e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbhackett
bugs941652
milestone28.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 941652 - IonMonkey: Fix quadradic-time insertion into LiveInterval use lists. r=bhackett
js/src/jit/BacktrackingAllocator.cpp
js/src/jit/LiveRangeAllocator.cpp
js/src/jit/LiveRangeAllocator.h
--- a/js/src/jit/BacktrackingAllocator.cpp
+++ b/js/src/jit/BacktrackingAllocator.cpp
@@ -779,17 +779,17 @@ BacktrackingAllocator::distributeUses(Li
         LiveInterval *addInterval = nullptr;
         for (size_t i = 0; i < newIntervals.length(); i++) {
             LiveInterval *newInterval = newIntervals[i];
             if (newInterval->covers(pos)) {
                 if (!addInterval || newInterval->start() < addInterval->start())
                     addInterval = newInterval;
             }
         }
-        addInterval->addUse(new(alloc()) UsePosition(iter->use, iter->pos));
+        addInterval->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
     }
 }
 
 bool
 BacktrackingAllocator::split(LiveInterval *interval,
                              const LiveIntervalVector &newIntervals)
 {
     if (IonSpewEnabled(IonSpew_RegAlloc)) {
@@ -1617,35 +1617,35 @@ BacktrackingAllocator::splitAtAllRegiste
     }
 
     for (UsePositionIterator iter(interval->usesBegin());
          iter != interval->usesEnd();
          iter++)
     {
         LInstruction *ins = insData[iter->pos].ins();
         if (iter->pos < spillStart) {
-            newIntervals.back()->addUse(new(alloc()) UsePosition(iter->use, iter->pos));
+            newIntervals.back()->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
         } else if (isRegisterUse(iter->use, ins)) {
             // For register uses which are not useRegisterAtStart, pick an
             // interval that covers both the instruction's input and output, so
             // that the register is not reused for an output.
             CodePosition from = inputOf(ins);
             CodePosition to = iter->pos.next();
 
             // Use the same interval for duplicate use positions, except when
             // the uses are fixed (they may require incompatible registers).
             if (newIntervals.empty() || newIntervals.back()->end() != to || iter->use->policy() == LUse::FIXED) {
                 if (!addLiveInterval(newIntervals, vreg, spillInterval, from, to))
                     return false;
             }
 
-            newIntervals.back()->addUse(new(alloc()) UsePosition(iter->use, iter->pos));
+            newIntervals.back()->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
         } else {
             JS_ASSERT(spillIntervalIsNew);
-            spillInterval->addUse(new(alloc()) UsePosition(iter->use, iter->pos));
+            spillInterval->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
         }
     }
 
     if (spillIntervalIsNew && !newIntervals.append(spillInterval))
         return false;
 
     return split(interval, newIntervals) && requeueIntervals(newIntervals);
 }
@@ -1719,37 +1719,37 @@ BacktrackingAllocator::splitAt(LiveInter
             return false;
         lastRegisterUse = interval->start();
     }
 
     size_t activeSplitPosition = NextSplitPosition(0, splitPositions, interval->start());
     for (UsePositionIterator iter(interval->usesBegin()); iter != interval->usesEnd(); iter++) {
         LInstruction *ins = insData[iter->pos].ins();
         if (iter->pos < spillStart) {
-            newIntervals.back()->addUse(new(alloc()) UsePosition(iter->use, iter->pos));
+            newIntervals.back()->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
             activeSplitPosition = NextSplitPosition(activeSplitPosition, splitPositions, iter->pos);
         } else if (isRegisterUse(iter->use, ins)) {
             if (lastRegisterUse.pos() == 0 ||
                 SplitHere(activeSplitPosition, splitPositions, iter->pos))
             {
                 // Place this register use into a different interval from the
                 // last one if there are any split points between the two uses.
                 LiveInterval *newInterval = LiveInterval::New(alloc(), vreg, 0);
                 newInterval->setSpillInterval(spillInterval);
                 if (!newIntervals.append(newInterval))
                     return false;
                 activeSplitPosition = NextSplitPosition(activeSplitPosition,
                                                         splitPositions,
                                                         iter->pos);
             }
-            newIntervals.back()->addUse(new(alloc()) UsePosition(iter->use, iter->pos));
+            newIntervals.back()->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
             lastRegisterUse = iter->pos;
         } else {
             JS_ASSERT(spillIntervalIsNew);
-            spillInterval->addUse(new(alloc()) UsePosition(iter->use, iter->pos));
+            spillInterval->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
         }
     }
 
     // Compute ranges for each new interval that cover all its uses.
     size_t activeRange = interval->numRanges();
     for (size_t i = 0; i < newIntervals.length(); i++) {
         LiveInterval *newInterval = newIntervals[i];
         CodePosition start, end;
--- a/js/src/jit/LiveRangeAllocator.cpp
+++ b/js/src/jit/LiveRangeAllocator.cpp
@@ -280,16 +280,23 @@ LiveInterval::addUse(UsePosition *use)
     }
 
     if (prev)
         uses_.insertAfter(prev, use);
     else
         uses_.pushFront(use);
 }
 
+void
+LiveInterval::addUseAtEnd(UsePosition *use)
+{
+    JS_ASSERT(uses_.empty() || use->pos >= uses_.back()->pos);
+    uses_.pushBack(use);
+}
+
 UsePosition *
 LiveInterval::nextUseAfter(CodePosition after)
 {
     for (UsePositionIterator usePos(usesBegin()); usePos != usesEnd(); usePos++) {
         if (usePos->pos >= after) {
             LUse::Policy policy = usePos->use->policy();
             JS_ASSERT(policy != LUse::RECOVERED_INPUT);
             if (policy != LUse::KEEPALIVE)
--- a/js/src/jit/LiveRangeAllocator.h
+++ b/js/src/jit/LiveRangeAllocator.h
@@ -351,16 +351,17 @@ class LiveInterval
         hint_ = hint;
     }
     bool isSpill() const {
         return alloc_.isStackSlot();
     }
     bool splitFrom(CodePosition pos, LiveInterval *after);
 
     void addUse(UsePosition *use);
+    void addUseAtEnd(UsePosition *use);
     UsePosition *nextUseAfter(CodePosition pos);
     CodePosition nextUsePosAfter(CodePosition pos);
     CodePosition firstIncompatibleUse(LAllocation alloc);
 
     UsePositionIterator usesBegin() const {
         return uses_.begin();
     }