Bug 999538 - Try to reuse stack slots in the backtracking allocator, r=sunfish.
authorBrian Hackett <bhackett1024@gmail.com>
Mon, 26 Jan 2015 08:11:14 -0700
changeset 239109 efe76955cea51c323507e3ee82028a1751faed38
parent 239108 babd560778269e2f907f4aac40ee714f50b0700d
child 239110 f8d8f84fc7bfd64727068e28783cc97bf6736bd4
push id487
push userbcampen@mozilla.com
push dateMon, 26 Jan 2015 23:32:56 +0000
reviewerssunfish
bugs999538
milestone38.0a1
Bug 999538 - Try to reuse stack slots in the backtracking allocator, r=sunfish.
js/src/jit/BacktrackingAllocator.cpp
js/src/jit/BacktrackingAllocator.h
js/src/jit/LIR.h
js/src/jit/StackSlotAllocator.h
--- a/js/src/jit/BacktrackingAllocator.cpp
+++ b/js/src/jit/BacktrackingAllocator.cpp
@@ -96,31 +96,44 @@ BacktrackingAllocator::go()
     if (!groupAndQueueRegisters())
         return false;
     JitSpew(JitSpew_RegAlloc, "Grouping and queueing registers complete");
 
     if (JitSpewEnabled(JitSpew_RegAlloc))
         dumpRegisterGroups();
 
     JitSpew(JitSpew_RegAlloc, "Beginning main allocation loop");
+
     // Allocate, spill and split register intervals until finished.
     while (!allocationQueue.empty()) {
         if (mir->shouldCancel("Backtracking Allocation"))
             return false;
 
         QueueItem item = allocationQueue.removeHighest();
         if (item.interval ? !processInterval(item.interval) : !processGroup(item.group))
             return false;
     }
     JitSpew(JitSpew_RegAlloc, "Main allocation loop complete");
 
+    if (!pickStackSlots())
+        return false;
+
     if (JitSpewEnabled(JitSpew_RegAlloc))
         dumpAllocations();
 
-    return resolveControlFlow() && reifyAllocations() && populateSafepoints();
+    if (!resolveControlFlow())
+        return false;
+
+    if (!reifyAllocations())
+        return false;
+
+    if (!populateSafepoints())
+        return false;
+
+    return true;
 }
 
 static bool
 LifetimesOverlap(BacktrackingVirtualRegister *reg0, BacktrackingVirtualRegister *reg1)
 {
     // Registers may have been eagerly split in two, see tryGroupReusedRegister.
     // In such cases, only consider the first interval.
     MOZ_ASSERT(reg0->numIntervals() <= 2 && reg1->numIntervals() <= 2);
@@ -378,16 +391,17 @@ BacktrackingAllocator::groupAndQueueRegi
 
         if (!reg.numIntervals())
             continue;
 
         // Eagerly set the canonical spill slot for registers which are fixed
         // for that slot, and reuse it for other registers in the group.
         LDefinition *def = reg.def();
         if (def->policy() == LDefinition::FIXED && !def->output()->isRegister()) {
+            MOZ_ASSERT(!def->output()->isStackSlot());
             reg.setCanonicalSpill(*def->output());
             if (reg.group() && reg.group()->spill.isUse())
                 reg.group()->spill = *def->output();
         }
 
         // Place all intervals for this register on the allocation queue.
         // During initial queueing use single queue items for groups of
         // registers, so that they will be allocated together and reduce the
@@ -925,31 +939,205 @@ BacktrackingAllocator::spill(LiveInterva
             JitSpew(JitSpew_RegAlloc, "    Reusing group spill location %s",
                     reg->group()->spill.toString());
             interval->setAllocation(reg->group()->spill);
             reg->setCanonicalSpill(reg->group()->spill);
             return;
         }
     }
 
-    uint32_t stackSlot = stackSlotAllocator.allocateSlot(reg->type());
-    MOZ_ASSERT(stackSlot <= stackSlotAllocator.stackHeight());
+    uint32_t virtualSlot = numVirtualStackSlots++;
 
-    LStackSlot alloc(stackSlot);
+    // Count virtual stack slots down from the maximum representable value, so
+    // that virtual slots are more obviously distinguished from real slots.
+    LStackSlot alloc(LAllocation::DATA_MASK - virtualSlot);
     interval->setAllocation(alloc);
 
     JitSpew(JitSpew_RegAlloc, "    Allocating spill location %s", alloc.toString());
 
     if (useCanonical) {
         reg->setCanonicalSpill(alloc);
         if (reg->group())
             reg->group()->spill = alloc;
     }
 }
 
+bool
+BacktrackingAllocator::pickStackSlots()
+{
+    for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
+        BacktrackingVirtualRegister *reg = &vregs[i];
+
+        if (mir->shouldCancel("Backtracking Pick Stack Slots"))
+            return false;
+
+        for (size_t j = 0; j < reg->numIntervals(); j++) {
+            LiveInterval *interval = reg->getInterval(j);
+            if (!pickStackSlot(interval))
+                return false;
+        }
+    }
+
+    return true;
+}
+
+bool
+BacktrackingAllocator::pickStackSlot(LiveInterval *interval)
+{
+    LAllocation alloc = *interval->getAllocation();
+    MOZ_ASSERT(!alloc.isUse());
+
+    if (!isVirtualStackSlot(alloc))
+        return true;
+
+    BacktrackingVirtualRegister &reg = vregs[interval->vreg()];
+
+    // Get a list of all the intervals which will share this stack slot.
+    LiveIntervalVector commonIntervals;
+
+    if (!commonIntervals.append(interval))
+        return false;
+
+    if (reg.canonicalSpill() && alloc == *reg.canonicalSpill()) {
+        // Look for other intervals in the vreg using this spill slot.
+        for (size_t i = 0; i < reg.numIntervals(); i++) {
+            LiveInterval *ninterval = reg.getInterval(i);
+            if (ninterval != interval && *ninterval->getAllocation() == alloc) {
+                if (!commonIntervals.append(ninterval))
+                    return false;
+            }
+        }
+
+        // Look for intervals in other registers with the same group using this
+        // spill slot.
+        if (reg.group() && alloc == reg.group()->spill) {
+            for (size_t i = 0; i < reg.group()->registers.length(); i++) {
+                uint32_t nvreg = reg.group()->registers[i];
+                if (nvreg == interval->vreg())
+                    continue;
+                BacktrackingVirtualRegister &nreg = vregs[nvreg];
+                for (size_t j = 0; j < nreg.numIntervals(); j++) {
+                    LiveInterval *ninterval = nreg.getInterval(j);
+                    if (*ninterval->getAllocation() == alloc) {
+                        if (!commonIntervals.append(ninterval))
+                            return false;
+                    }
+                }
+            }
+        }
+    } else {
+        MOZ_ASSERT_IF(reg.group(), alloc != reg.group()->spill);
+    }
+
+    if (!reuseOrAllocateStackSlot(commonIntervals, reg.type(), &alloc))
+        return false;
+
+    MOZ_ASSERT(!isVirtualStackSlot(alloc));
+
+    // Set the physical stack slot for each of the intervals found earlier.
+    for (size_t i = 0; i < commonIntervals.length(); i++)
+        commonIntervals[i]->setAllocation(alloc);
+
+    return true;
+}
+
+bool
+BacktrackingAllocator::reuseOrAllocateStackSlot(const LiveIntervalVector &intervals, LDefinition::Type type,
+                                                LAllocation *palloc)
+{
+    SpillSlotList *slotList;
+    switch (StackSlotAllocator::width(type)) {
+      case 4:  slotList = &normalSlots; break;
+      case 8:  slotList = &doubleSlots; break;
+      case 16: slotList = &quadSlots;   break;
+      default:
+        MOZ_CRASH("Bad width");
+    }
+
+    // Maximum number of existing spill slots we will look at before giving up
+    // and allocating a new slot.
+    static const size_t MAX_SEARCH_COUNT = 10;
+
+    if (!slotList->empty()) {
+        size_t searches = 0;
+        SpillSlot *stop = nullptr;
+        while (true) {
+            SpillSlot *spill = *slotList->begin();
+            if (!stop) {
+                stop = spill;
+            } else if (stop == spill) {
+                // We looked through every slot in the list.
+                break;
+            }
+
+            bool success = true;
+            for (size_t i = 0; i < intervals.length() && success; i++) {
+                LiveInterval *interval = intervals[i];
+                for (size_t j = 0; j < interval->numRanges(); j++) {
+                    AllocatedRange range(interval, interval->getRange(j)), existing;
+                    if (spill->allocated.contains(range, &existing)) {
+                        success = false;
+                        break;
+                    }
+                }
+            }
+            if (success) {
+                // We can reuse this physical stack slot for the new intervals.
+                // Update the allocated ranges for the slot.
+                if (!insertAllRanges(spill->allocated, intervals))
+                    return false;
+                *palloc = spill->alloc;
+                return true;
+            }
+
+            // On a miss, move the spill to the end of the list. This will cause us
+            // to make fewer attempts to allocate from slots with a large and
+            // highly contended range.
+            slotList->popFront();
+            slotList->pushBack(spill);
+
+            if (++searches == MAX_SEARCH_COUNT)
+                break;
+        }
+    }
+
+    // We need a new physical stack slot.
+    uint32_t stackSlot = stackSlotAllocator.allocateSlot(type);
+
+    // Make sure the virtual and physical stack slots don't start overlapping.
+    if (isVirtualStackSlot(LStackSlot(stackSlot)))
+        return false;
+
+    SpillSlot *spill = new(alloc()) SpillSlot(stackSlot, alloc().lifoAlloc());
+    if (!spill)
+        return false;
+
+    if (!insertAllRanges(spill->allocated, intervals))
+        return false;
+
+    *palloc = spill->alloc;
+
+    slotList->pushFront(spill);
+    return true;
+}
+
+bool
+BacktrackingAllocator::insertAllRanges(AllocatedRangeSet &set, const LiveIntervalVector &intervals)
+{
+    for (size_t i = 0; i < intervals.length(); i++) {
+        LiveInterval *interval = intervals[i];
+        for (size_t j = 0; j < interval->numRanges(); j++) {
+            AllocatedRange range(interval, interval->getRange(j));
+            if (!set.insert(range))
+                return false;
+        }
+    }
+    return true;
+}
+
 // Add moves to resolve conflicting assignments between a block and its
 // predecessors. XXX try to common this with LinearScanAllocator.
 bool
 BacktrackingAllocator::resolveControlFlow()
 {
     JitSpew(JitSpew_RegAlloc, "Resolving control flow (vreg loop)");
 
     // Virtual register number 0 is unused.
--- a/js/src/jit/BacktrackingAllocator.h
+++ b/js/src/jit/BacktrackingAllocator.h
@@ -171,19 +171,38 @@ class BacktrackingAllocator
         PhysicalRegister() : allocatable(false) {}
     };
     mozilla::Array<PhysicalRegister, AnyRegister::Total> registers;
 
     // Ranges of code which are considered to be hot, for which good allocation
     // should be prioritized.
     AllocatedRangeSet hotcode;
 
+    // During register allocation, virtual stack slots are used for spills.
+    // These are converted to actual spill locations
+    size_t numVirtualStackSlots;
+
+    // Information about an allocated stack slot.
+    struct SpillSlot : public TempObject, public InlineForwardListNode<SpillSlot> {
+        LStackSlot alloc;
+        AllocatedRangeSet allocated;
+
+        SpillSlot(uint32_t slot, LifoAlloc *alloc)
+          : alloc(slot), allocated(alloc)
+        {}
+    };
+    typedef InlineForwardList<SpillSlot> SpillSlotList;
+
+    // All allocated slots of each width.
+    SpillSlotList normalSlots, doubleSlots, quadSlots;
+
   public:
     BacktrackingAllocator(MIRGenerator *mir, LIRGenerator *lir, LIRGraph &graph)
-      : LiveRangeAllocator<BacktrackingVirtualRegister, /* forLSRA = */ false>(mir, lir, graph)
+      : LiveRangeAllocator<BacktrackingVirtualRegister, /* forLSRA = */ false>(mir, lir, graph),
+        numVirtualStackSlots(0)
     { }
 
     bool go();
 
   private:
 
     typedef Vector<LiveInterval *, 4, SystemAllocPolicy> LiveIntervalVector;
 
@@ -208,17 +227,22 @@ class BacktrackingAllocator
     void spill(LiveInterval *interval);
 
     bool isReusedInput(LUse *use, LNode *ins, bool considerCopy);
     bool isRegisterUse(LUse *use, LNode *ins, bool considerCopy = false);
     bool isRegisterDefinition(LiveInterval *interval);
     bool addLiveInterval(LiveIntervalVector &intervals, uint32_t vreg,
                          LiveInterval *spillInterval,
                          CodePosition from, CodePosition to);
+    bool pickStackSlot(LiveInterval *interval);
+    bool reuseOrAllocateStackSlot(const LiveIntervalVector &intervals, LDefinition::Type type,
+                                  LAllocation *palloc);
+    bool insertAllRanges(AllocatedRangeSet &set, const LiveIntervalVector &intervals);
 
+    bool pickStackSlots();
     bool resolveControlFlow();
     bool reifyAllocations();
     bool populateSafepoints();
 
     void dumpRegisterGroups();
     void dumpFixedRanges();
     void dumpAllocations();
 
@@ -244,14 +268,19 @@ class BacktrackingAllocator
     bool trySplitAfterLastRegisterUse(LiveInterval *interval, LiveInterval *conflict, bool *success);
     bool trySplitBeforeFirstRegisterUse(LiveInterval *interval, LiveInterval *conflict, bool *success);
     bool splitAtAllRegisterUses(LiveInterval *interval);
     bool splitAcrossCalls(LiveInterval *interval);
 
     bool compilingAsmJS() {
         return mir->info().compilingAsmJS();
     }
+
+    bool isVirtualStackSlot(LAllocation alloc) {
+        return alloc.isStackSlot() &&
+               LAllocation::DATA_MASK - alloc.toStackSlot()->slot() < numVirtualStackSlots;
+    }
 };
 
 } // namespace jit
 } // namespace js
 
 #endif /* jit_BacktrackingAllocator_h */
--- a/js/src/jit/LIR.h
+++ b/js/src/jit/LIR.h
@@ -62,29 +62,30 @@ class LAllocation : public TempObject
     // 8-byte aligned.
     static const uintptr_t KIND_BITS = 3;
     static const uintptr_t KIND_SHIFT = 0;
     static const uintptr_t KIND_MASK = (1 << KIND_BITS) - 1;
 
   protected:
     static const uintptr_t DATA_BITS = (sizeof(uint32_t) * 8) - KIND_BITS;
     static const uintptr_t DATA_SHIFT = KIND_SHIFT + KIND_BITS;
-    static const uintptr_t DATA_MASK = (1 << DATA_BITS) - 1;
 
   public:
     enum Kind {
         CONSTANT_VALUE, // Constant js::Value.
         CONSTANT_INDEX, // Constant arbitrary index.
         USE,            // Use of a virtual register, with physical allocation policy.
         GPR,            // General purpose register.
         FPU,            // Floating-point register.
         STACK_SLOT,     // Stack slot.
         ARGUMENT_SLOT   // Argument slot.
     };
 
+    static const uintptr_t DATA_MASK = (1 << DATA_BITS) - 1;
+
   protected:
     uint32_t data() const {
         return uint32_t(bits_) >> DATA_SHIFT;
     }
     void setData(uint32_t data) {
         MOZ_ASSERT(data <= DATA_MASK);
         bits_ &= ~(DATA_MASK << DATA_SHIFT);
         bits_ |= (data << DATA_SHIFT);
--- a/js/src/jit/StackSlotAllocator.h
+++ b/js/src/jit/StackSlotAllocator.h
@@ -70,70 +70,60 @@ class StackSlotAllocator
         }
         return height_ += 4;
     }
 
   public:
     StackSlotAllocator() : height_(0)
     { }
 
-    void freeSlot(LDefinition::Type type, uint32_t index) {
+    static uint32_t width(LDefinition::Type type) {
         switch (type) {
 #if JS_BITS_PER_WORD == 32
           case LDefinition::GENERAL:
           case LDefinition::OBJECT:
           case LDefinition::SLOTS:
 #endif
           case LDefinition::INT32:
-          case LDefinition::FLOAT32:   return freeSlot(index);
+          case LDefinition::FLOAT32:   return 4;
 #if JS_BITS_PER_WORD == 64
           case LDefinition::GENERAL:
           case LDefinition::OBJECT:
           case LDefinition::SLOTS:
 #endif
 #ifdef JS_PUNBOX64
           case LDefinition::BOX:
 #endif
 #ifdef JS_NUNBOX32
           case LDefinition::TYPE:
           case LDefinition::PAYLOAD:
 #endif
-          case LDefinition::DOUBLE:    return freeDoubleSlot(index);
+          case LDefinition::DOUBLE:    return 8;
           case LDefinition::FLOAT32X4:
-          case LDefinition::INT32X4:   return freeQuadSlot(index);
+          case LDefinition::INT32X4:   return 16;
         }
         MOZ_CRASH("Unknown slot type");
     }
 
+    void freeSlot(LDefinition::Type type, uint32_t index) {
+        switch (width(type)) {
+          case 4:  return freeSlot(index);
+          case 8:  return freeDoubleSlot(index);
+          case 16: return freeQuadSlot(index);
+        }
+        MOZ_CRASH("Unknown slot width");
+    }
+
     uint32_t allocateSlot(LDefinition::Type type) {
-        switch (type) {
-#if JS_BITS_PER_WORD == 32
-          case LDefinition::GENERAL:
-          case LDefinition::OBJECT:
-          case LDefinition::SLOTS:
-#endif
-          case LDefinition::INT32:
-          case LDefinition::FLOAT32:   return allocateSlot();
-#if JS_BITS_PER_WORD == 64
-          case LDefinition::GENERAL:
-          case LDefinition::OBJECT:
-          case LDefinition::SLOTS:
-#endif
-#ifdef JS_PUNBOX64
-          case LDefinition::BOX:
-#endif
-#ifdef JS_NUNBOX32
-          case LDefinition::TYPE:
-          case LDefinition::PAYLOAD:
-#endif
-          case LDefinition::DOUBLE:    return allocateDoubleSlot();
-          case LDefinition::FLOAT32X4:
-          case LDefinition::INT32X4:   return allocateQuadSlot();
+        switch (width(type)) {
+          case 4:  return allocateSlot();
+          case 8:  return allocateDoubleSlot();
+          case 16: return allocateQuadSlot();
         }
-        MOZ_CRASH("Unknown slot type");
+        MOZ_CRASH("Unknown slot width");
     }
 
     uint32_t stackHeight() const {
         return height_;
     }
 };
 
 } // namespace jit