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 225789 efe76955cea51c323507e3ee82028a1751faed38
parent 225788 babd560778269e2f907f4aac40ee714f50b0700d
child 225790 f8d8f84fc7bfd64727068e28783cc97bf6736bd4
push id28175
push userryanvm@gmail.com
push dateMon, 26 Jan 2015 21:33:41 +0000
treeherdermozilla-central@a6f037b538ed [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssunfish
bugs999538
milestone38.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 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