Bug 983752 - Consider conflicting intervals when splitting backtracking intervals, r=sunfish.
authorBrian Hackett <bhackett1024@gmail.com>
Sun, 16 Mar 2014 16:44:53 -0600
changeset 191045 e526749f8eca154b84d22435a9a5a79ee85dabab
parent 191044 db542ae460d98c339e1ac14244c5ab8f51bf58fd
child 191046 485a6d64cca2efd7a28ab8ef2ceddfb4af1aa442
push id3503
push userraliiev@mozilla.com
push dateMon, 28 Apr 2014 18:51:11 +0000
treeherdermozilla-beta@c95ac01e332e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssunfish
bugs983752
milestone30.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 983752 - Consider conflicting intervals when splitting backtracking intervals, r=sunfish.
js/src/jit/BacktrackingAllocator.cpp
js/src/jit/BacktrackingAllocator.h
--- a/js/src/jit/BacktrackingAllocator.cpp
+++ b/js/src/jit/BacktrackingAllocator.cpp
@@ -474,17 +474,17 @@ BacktrackingAllocator::processInterval(L
     // In general, we want to minimize the amount of interval splitting
     // (which generally necessitates spills), so allocate longer lived, lower
     // weight intervals first and evict and split them later if they prevent
     // allocation for higher weight intervals.
 
     bool canAllocate = setIntervalRequirement(interval);
 
     bool fixed;
-    LiveInterval *conflict;
+    LiveInterval *conflict = nullptr;
     for (size_t attempt = 0;; attempt++) {
         if (canAllocate) {
             bool success = false;
             fixed = false;
             conflict = nullptr;
 
             // Ok, let's try allocating for this interval.
             if (interval->requirement()->kind() == Requirement::FIXED) {
@@ -515,17 +515,17 @@ BacktrackingAllocator::processInterval(L
         // A minimal interval cannot be split any further. If we try to split
         // it at this point we will just end up with the same interval and will
         // enter an infinite loop. Weights and the initial live intervals must
         // be constructed so that any minimal interval is allocatable.
         JS_ASSERT(!minimalInterval(interval));
 
         if (canAllocate && fixed)
             return splitAcrossCalls(interval);
-        return chooseIntervalSplit(interval);
+        return chooseIntervalSplit(interval, conflict);
     }
 }
 
 bool
 BacktrackingAllocator::processGroup(VirtualRegisterGroup *group)
 {
     if (IonSpewEnabled(IonSpew_RegAlloc)) {
         IonSpew(IonSpew_RegAlloc, "Allocating group v%u [priority %lu] [weight %lu]",
@@ -578,27 +578,36 @@ BacktrackingAllocator::setIntervalRequir
     // require the interval to be split.
     interval->setHint(Requirement());
     interval->setRequirement(Requirement());
 
     BacktrackingVirtualRegister *reg = &vregs[interval->vreg()];
 
     // Set a hint if another interval in the same group is in a register.
     if (VirtualRegisterGroup *group = reg->group()) {
-        if (group->allocation.isRegister())
+        if (group->allocation.isRegister()) {
+            if (IonSpewEnabled(IonSpew_RegAlloc)) {
+                IonSpew(IonSpew_RegAlloc, "Hint %s, used by group allocation",
+                        group->allocation.toString());
+            }
             interval->setHint(Requirement(group->allocation));
+        }
     }
 
     if (interval->index() == 0) {
         // The first interval is the definition, so deal with any definition
         // constraints/hints.
 
         LDefinition::Policy policy = reg->def()->policy();
         if (policy == LDefinition::PRESET) {
             // Preset policies get a FIXED requirement.
+            if (IonSpewEnabled(IonSpew_RegAlloc)) {
+                IonSpew(IonSpew_RegAlloc, "Requirement %s, preset by definition",
+                        reg->def()->output()->toString());
+            }
             interval->setRequirement(Requirement(*reg->def()->output()));
         } else if (reg->ins()->isPhi()) {
             // Phis don't have any requirements, but they should prefer their
             // input allocations. This is captured by the group hints above.
         } else {
             // Non-phis get a REGISTER requirement.
             interval->setRequirement(Requirement(Requirement::REGISTER));
         }
@@ -608,16 +617,21 @@ BacktrackingAllocator::setIntervalRequir
     for (UsePositionIterator iter = interval->usesBegin();
          iter != interval->usesEnd();
          iter++)
     {
         LUse::Policy policy = iter->use->policy();
         if (policy == LUse::FIXED) {
             AnyRegister required = GetFixedRegister(reg->def(), iter->use);
 
+            if (IonSpewEnabled(IonSpew_RegAlloc)) {
+                IonSpew(IonSpew_RegAlloc, "Requirement %s, due to use at %u",
+                        required.name(), iter->pos.pos());
+            }
+
             // If there are multiple fixed registers which the interval is
             // required to use, fail. The interval will need to be split before
             // it can be allocated.
             if (!interval->addRequirement(Requirement(LAllocation(required))))
                 return false;
         } else if (policy == LUse::REGISTER) {
             if (!interval->addRequirement(Requirement(Requirement::REGISTER)))
                 return false;
@@ -1510,37 +1524,40 @@ BacktrackingAllocator::trySplitAcrossHot
     SplitPositionVector splitPositions;
     if (!splitPositions.append(hotRange->from) || !splitPositions.append(hotRange->to))
         return false;
     *success = true;
     return splitAt(interval, splitPositions);
 }
 
 bool
-BacktrackingAllocator::trySplitAfterLastRegisterUse(LiveInterval *interval, bool *success)
+BacktrackingAllocator::trySplitAfterLastRegisterUse(LiveInterval *interval, LiveInterval *conflict, bool *success)
 {
     // If this interval's later uses do not require it to be in a register,
-    // split it after the last use which does require a register.
+    // split it after the last use which does require a register. If conflict
+    // is specified, only consider register uses before the conflict starts.
 
     CodePosition lastRegisterFrom, lastRegisterTo, lastUse;
 
     for (UsePositionIterator iter(interval->usesBegin());
          iter != interval->usesEnd();
          iter++)
     {
         LUse *use = iter->use;
         LInstruction *ins = insData[iter->pos].ins();
 
         // Uses in the interval should be sorted.
         JS_ASSERT(iter->pos >= lastUse);
         lastUse = inputOf(ins);
 
-        if (isRegisterUse(use, ins, /* considerCopy = */ true)) {
-            lastRegisterFrom = inputOf(ins);
-            lastRegisterTo = iter->pos.next();
+        if (!conflict || outputOf(ins) < conflict->start()) {
+            if (isRegisterUse(use, ins, /* considerCopy = */ true)) {
+                lastRegisterFrom = inputOf(ins);
+                lastRegisterTo = iter->pos.next();
+            }
         }
     }
 
     if (!lastRegisterFrom.pos() || lastRegisterFrom == lastUse) {
         // Can't trim non-register uses off the end by splitting.
         return true;
     }
 
@@ -1776,24 +1793,24 @@ BacktrackingAllocator::splitAcrossCalls(
         }
     }
     JS_ASSERT(callPositions.length());
 
     return splitAt(interval, callPositions);
 }
 
 bool
-BacktrackingAllocator::chooseIntervalSplit(LiveInterval *interval)
+BacktrackingAllocator::chooseIntervalSplit(LiveInterval *interval, LiveInterval *conflict)
 {
     bool success = false;
 
     if (!trySplitAcrossHotcode(interval, &success))
         return false;
     if (success)
         return true;
 
-    if (!trySplitAfterLastRegisterUse(interval, &success))
+    if (!trySplitAfterLastRegisterUse(interval, conflict, &success))
         return false;
     if (success)
         return true;
 
     return splitAtAllRegisterUses(interval);
 }
--- a/js/src/jit/BacktrackingAllocator.h
+++ b/js/src/jit/BacktrackingAllocator.h
@@ -231,22 +231,22 @@ class BacktrackingAllocator
     // Heuristic methods.
 
     size_t computePriority(const LiveInterval *interval);
     size_t computeSpillWeight(const LiveInterval *interval);
 
     size_t computePriority(const VirtualRegisterGroup *group);
     size_t computeSpillWeight(const VirtualRegisterGroup *group);
 
-    bool chooseIntervalSplit(LiveInterval *interval);
+    bool chooseIntervalSplit(LiveInterval *interval, LiveInterval *conflict);
 
     bool splitAt(LiveInterval *interval,
                  const SplitPositionVector &splitPositions);
     bool trySplitAcrossHotcode(LiveInterval *interval, bool *success);
-    bool trySplitAfterLastRegisterUse(LiveInterval *interval, bool *success);
+    bool trySplitAfterLastRegisterUse(LiveInterval *interval, LiveInterval *conflict, bool *success);
     bool splitAtAllRegisterUses(LiveInterval *interval);
     bool splitAcrossCalls(LiveInterval *interval);
 };
 
 } // namespace jit
 } // namespace js
 
 #endif /* jit_BacktrackingAllocator_h */