Bug 1123874 - Optimize MoveGroups with multiple targets for the same source, r=sunfish.
authorBrian Hackett <bhackett1024@gmail.com>
Thu, 29 Jan 2015 11:54:47 -0700
changeset 226562 b2430b424a00701871090e47043395960a6e8ced
parent 226561 ace4047fc410ad212c9c5f21736985d39d4b130e
child 226563 47f17e4219eafbcd9a22fb4ac7fefc61df89c1e0
push id28200
push userkwierso@gmail.com
push dateThu, 29 Jan 2015 23:01:46 +0000
treeherdermozilla-central@4380ed39de3a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssunfish
bugs1123874
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 1123874 - Optimize MoveGroups with multiple targets for the same source, r=sunfish.
js/src/jit/MoveResolver.cpp
js/src/jit/MoveResolver.h
--- a/js/src/jit/MoveResolver.cpp
+++ b/js/src/jit/MoveResolver.cpp
@@ -79,25 +79,17 @@ bool
 MoveResolver::resolve()
 {
     resetState();
     orderedMoves_.clear();
 
     InlineList<PendingMove> stack;
 
     // This is a depth-first-search without recursion, which tries to find
-    // cycles in a list of moves. The output is not entirely optimal for cases
-    // where a source has multiple destinations, i.e.:
-    //      [stack0] -> A
-    //      [stack0] -> B
-    //
-    // These moves may not occur next to each other in the list, making it
-    // harder for the emitter to optimize memory to memory traffic. However, we
-    // expect duplicate sources to be rare in greedy allocation, and indicative
-    // of an error in LSRA.
+    // cycles in a list of moves.
     //
     // Algorithm.
     //
     // S = Traversal stack.
     // P = Pending move list.
     // O = Ordered list of moves.
     //
     // As long as there are pending moves in P:
@@ -155,23 +147,68 @@ MoveResolver::resolve()
                     pending_.remove(blocking);
                     stack.pushBack(blocking);
                 }
             } else {
                 // Otherwise, pop the last move on the search stack because it's
                 // complete and not participating in a cycle. The resulting
                 // move can safely be added to the ordered move list.
                 PendingMove *done = stack.popBack();
-                if (!orderedMoves_.append(*done))
+                if (!addOrderedMove(*done))
                     return false;
                 movePool_.free(done);
             }
         }
         // If the current queue is empty, it is certain that there are
         // all previous cycles cannot conflict with future cycles,
         // so re-set the counter of pending cycles, while keeping a high-water mark.
         if (numCycles_ < curCycles_)
             numCycles_ = curCycles_;
         curCycles_ = 0;
     }
 
     return true;
 }
+
+bool
+MoveResolver::addOrderedMove(const MoveOp &move)
+{
+    // Sometimes the register allocator generates move groups where multiple
+    // moves have the same source. Try to optimize these cases when the source
+    // is in memory and the target of one of the moves is in a register.
+    MOZ_ASSERT(!move.from().aliases(move.to()));
+
+    if (!move.from().isMemory() || move.isCycleBegin() || move.isCycleEnd())
+        return orderedMoves_.append(move);
+
+    // Look for an earlier move with the same source, where no intervening move
+    // touches either the source or destination of the new move.
+    for (int i = orderedMoves_.length() - 1; i >= 0; i--) {
+        const MoveOp &existing = orderedMoves_[i];
+
+        if (existing.from() == move.from() &&
+            !existing.to().aliases(move.to()) &&
+            existing.type() == move.type() &&
+            !existing.isCycleBegin() &&
+            !existing.isCycleEnd())
+        {
+            MoveOp *after = orderedMoves_.begin() + i + 1;
+            if (existing.to().isGeneralReg() || existing.to().isFloatReg()) {
+                MoveOp nmove(existing.to(), move.to(), move.type());
+                return orderedMoves_.insert(after, nmove);
+            } else if (move.to().isGeneralReg() || move.to().isFloatReg()) {
+                MoveOp nmove(move.to(), existing.to(), move.type());
+                orderedMoves_[i] = move;
+                return orderedMoves_.insert(after, nmove);
+            }
+        }
+
+        if (existing.to().aliases(move.from()) ||
+            existing.to().aliases(move.to()) ||
+            existing.from().aliases(move.to()) ||
+            existing.from().aliases(move.from()))
+        {
+            break;
+        }
+    }
+
+    return orderedMoves_.append(move);
+}
--- a/js/src/jit/MoveResolver.h
+++ b/js/src/jit/MoveResolver.h
@@ -235,16 +235,18 @@ class MoveResolver
     int numCycles_;
     int curCycles_;
     TempObjectPool<PendingMove> movePool_;
 
     InlineList<PendingMove> pending_;
 
     PendingMove *findBlockingMove(const PendingMove *last);
     PendingMove *findCycledMove(PendingMoveIterator *stack, PendingMoveIterator end, const PendingMove *first);
+    bool addOrderedMove(const MoveOp &move);
+
     // Internal reset function. Does not clear lists.
     void resetState();
 
   public:
     MoveResolver();
 
     // Resolves a move group into two lists of ordered moves. These moves must
     // be executed in the order provided. Some moves may indicate that they