Bug 670633: Eliminate unnecessary spill stores generated by linear scan register allocator.
authorAndrew Drake <adrake@adrake.org>
Tue, 26 Jul 2011 06:12:01 -0700
changeset 73504 7bd4ed0a22856f5c1d8115b265dc1d60293d6c53
parent 73503 0d79db47e6fa0e148614aba0dc24a37d3339ce3f
child 73505 3be9cb4bc96a175e893b3b600930a48cdb5a0f34
push id34
push userdrakedevel@gmail.com
push dateThu, 28 Jul 2011 00:46:46 +0000
bugs670633
milestone8.0a1
Bug 670633: Eliminate unnecessary spill stores generated by linear scan register allocator.
js/src/ion/LinearScan.cpp
js/src/ion/LinearScan.h
--- a/js/src/ion/LinearScan.cpp
+++ b/js/src/ion/LinearScan.cpp
@@ -822,21 +822,28 @@ LinearScanAllocator::reifyAllocations()
         for (size_t i = 0; i < reg->numUses(); i++) {
             LOperand *use = reg->getUse(i);
             LAllocation *alloc = use->use;
             CodePosition pos = inputOf(use->ins);
             if (interval->covers(pos))
                 *alloc = *interval->getAllocation();
         }
 
-        if (interval->index() == 0) {
+        if (interval->index() == 0)
+        {
             // Erase the def of this interval if it's the first one
             reg->def()->setOutput(*interval->getAllocation());
-        } else {
-            // Insert moves for this interval otherwise
+        }
+        else if (!interval->reg()->canonicalSpill() ||
+                 interval->reg()->canonicalSpill() == interval->getAllocation() ||
+                 *interval->reg()->canonicalSpill() != *interval->getAllocation())
+        {
+            // If this virtual register has no canonical spill location, this
+            // is the first spill to that location, or this is a move to somewhere
+            // completely different, we have to emit a move for this interval.
             LiveInterval *from = reg->getInterval(interval->index() - 1);
             if (!moveBefore(interval->start(), from, interval))
                 return false;
         }
     }
 
     // Strip phis out
     for (size_t i = 0; i < graph.numBlocks(); i++)
@@ -963,44 +970,56 @@ LinearScanAllocator::assign(LAllocation 
                     return false;
 
                 i = inactive.removeAt(i);
                 finishInterval(it);
             } else {
                 i++;
             }
         }
+    } else if (allocation.isMemory()) {
+        if (current->reg()->canonicalSpill())
+            JS_ASSERT(allocation == *current->reg()->canonicalSpill());
+        else
+            current->reg()->setCanonicalSpill(current->getAllocation());
     }
 
     active.insert(current);
 
     return true;
 }
 
 bool
 LinearScanAllocator::spill()
 {
     IonSpew(IonSpew_LSRA, "  Decided to spill current interval");
 
+    if (current->reg()->canonicalSpill()) {
+        IonSpew(IonSpew_LSRA, "  Allocating canonical spill location");
+
+        return assign(*current->reg()->canonicalSpill());
+    }
+
     uint32 stackSlot;
     if (!stackAssignment.allocateSlot(&stackSlot))
         return false;
 
     IonSpew(IonSpew_LSRA, "  Allocated spill slot %u", stackSlot);
 
     return assign(LStackSlot(stackSlot));
 }
 
 void
 LinearScanAllocator::finishInterval(LiveInterval *interval)
 {
     LAllocation *alloc = interval->getAllocation();
     JS_ASSERT(!alloc->isUse());
 
-    if (alloc->isStackSlot()) {
+    bool lastInterval = interval->index() == (interval->reg()->numIntervals() - 1);
+    if (alloc->isStackSlot() && (alloc != interval->reg()->canonicalSpill() || lastInterval)) {
         if (alloc->toStackSlot()->isDouble())
             stackAssignment.freeDoubleSlot(alloc->toStackSlot()->slot());
         else
             stackAssignment.freeSlot(alloc->toStackSlot()->slot());
     }
 
     handled.insert(interval);
 }
--- a/js/src/ion/LinearScan.h
+++ b/js/src/ion/LinearScan.h
@@ -262,25 +262,27 @@ class VirtualRegister : public TempObjec
     uint32 reg_;
     LBlock *block_;
     LInstruction *ins_;
     LDefinition *def_;
     Vector<LiveInterval *, 1, IonAllocPolicy> intervals_;
     Vector<LOperand, 0, IonAllocPolicy> uses_;
     LMoveGroup *inputMoves_;
     LMoveGroup *outputMoves_;
+    LAllocation *canonicalSpill_;
 
   public:
     VirtualRegister()
       : reg_(0),
         block_(NULL),
         ins_(NULL),
         intervals_(),
         inputMoves_(NULL),
-        outputMoves_(NULL)
+        outputMoves_(NULL),
+        canonicalSpill_(NULL)
     { }
 
     bool init(uint32 reg, LBlock *block, LInstruction *ins, LDefinition *def) {
         reg_ = reg;
         block_ = block;
         ins_ = ins;
         def_ = def;
         LiveInterval *initial = new LiveInterval(this, 0);
@@ -338,16 +340,22 @@ class VirtualRegister : public TempObjec
         return inputMoves_;
     }
     void setOutputMoves(LMoveGroup *moves) {
         outputMoves_ = moves;
     }
     LMoveGroup *outputMoves() {
         return outputMoves_;
     }
+    void setCanonicalSpill(LAllocation *alloc) {
+        canonicalSpill_ = alloc;
+    }
+    LAllocation *canonicalSpill() {
+        return canonicalSpill_;
+    }
 
     LiveInterval *intervalFor(CodePosition pos);
     LOperand *nextUseAfter(CodePosition pos);
     CodePosition nextUsePosAfter(CodePosition pos);
     CodePosition nextIncompatibleUseAfter(CodePosition after, LAllocation alloc);
     LiveInterval *getFirstInterval();
 };