tor-browser

MoveResolver.cpp (14054B)

---

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "jit/MoveResolver.h"

#include "mozilla/ScopeExit.h"

#include "jit/MacroAssembler.h"
#include "jit/RegisterSets.h"

using namespace js;
using namespace js::jit;

MoveOperand::MoveOperand(MacroAssembler& masm, const ABIArg& arg) : disp_(0) {
 switch (arg.kind()) {
   case ABIArg::GPR:
     kind_ = Kind::Reg;
     code_ = arg.gpr().code();
     break;
#ifdef JS_CODEGEN_REGISTER_PAIR
   case ABIArg::GPR_PAIR:
     kind_ = Kind::RegPair;
     code_ = arg.evenGpr().code();
     MOZ_ASSERT(code_ % 2 == 0);
     MOZ_ASSERT(code_ + 1 == arg.oddGpr().code());
     break;
#endif
   case ABIArg::FPU:
     kind_ = Kind::FloatReg;
     code_ = arg.fpu().code();
     break;
   case ABIArg::Stack:
     kind_ = Kind::Memory;
     if (IsHiddenSP(masm.getStackPointer())) {
       MOZ_CRASH(
           "Hidden SP cannot be represented as register code on this "
           "platform");
     } else {
       code_ = AsRegister(masm.getStackPointer()).code();
     }
     disp_ = arg.offsetFromArgBase();
     break;
   case ABIArg::Uninitialized:
     MOZ_CRASH("Uninitialized ABIArg kind");
 }
}

MoveResolver::MoveResolver() : numCycles_(0), curCycles_(0) {}

void MoveResolver::resetState() {
 numCycles_ = 0;
 curCycles_ = 0;
}

bool MoveResolver::addMove(const MoveOperand& from, const MoveOperand& to,
                          MoveOp::Type type) {
 // Assert that we're not doing no-op moves.
 MOZ_ASSERT(!(from == to));
 PendingMove* pm = movePool_.allocate(from, to, type);
 if (!pm) {
   return false;
 }
 pending_.pushBack(pm);
 return true;
}

// Given move (A -> B), this function attempts to find any move (B -> *) in the
// pending move list, and returns the first one.
MoveResolver::PendingMove* MoveResolver::findBlockingMove(
   const PendingMove* last) {
 for (PendingMoveIterator iter = pending_.begin(); iter != pending_.end();
      iter++) {
   PendingMove* other = *iter;

   if (other->from().aliases(last->to())) {
     // We now have pairs in the form (A -> X) (X -> y). The second pair
     // blocks the move in the first pair, so return it.
     return other;
   }
 }

 // No blocking moves found.
 return nullptr;
}

// Given move (A -> B), this function attempts to find any move (B -> *) in the
// move list iterator, and returns the first one.
// N.B. It is unclear if a single move can complete more than one cycle, so to
// be conservative, this function operates on iterators, so the caller can
// process all instructions that start a cycle.
MoveResolver::PendingMove* MoveResolver::findCycledMove(
   PendingMoveIterator* iter, PendingMoveIterator end,
   const PendingMove* last) {
 for (; *iter != end; (*iter)++) {
   PendingMove* other = **iter;
   if (other->from().aliases(last->to())) {
     // We now have pairs in the form (A -> X) (X -> y). The second pair
     // blocks the move in the first pair, so return it.
     (*iter)++;
     return other;
   }
 }
 // No blocking moves found.
 return nullptr;
}

#ifdef JS_CODEGEN_ARM
static inline bool MoveIsDouble(const MoveOperand& move) {
 if (!move.isFloatReg()) {
   return false;
 }
 return move.floatReg().isDouble();
}
#endif

#ifdef JS_CODEGEN_ARM
static inline bool MoveIsSingle(const MoveOperand& move) {
 if (!move.isFloatReg()) {
   return false;
 }
 return move.floatReg().isSingle();
}
#endif

#ifdef JS_CODEGEN_ARM
bool MoveResolver::isDoubleAliasedAsSingle(const MoveOperand& move) {
 if (!MoveIsDouble(move)) {
   return false;
 }

 for (auto iter = pending_.begin(); iter != pending_.end(); ++iter) {
   PendingMove* other = *iter;
   if (other->from().aliases(move) && MoveIsSingle(other->from())) {
     return true;
   }
   if (other->to().aliases(move) && MoveIsSingle(other->to())) {
     return true;
   }
 }
 return false;
}
#endif

#ifdef JS_CODEGEN_ARM
static MoveOperand SplitIntoLowerHalf(const MoveOperand& move) {
 if (MoveIsDouble(move)) {
   FloatRegister lowerSingle = move.floatReg().asSingle();
   return MoveOperand(lowerSingle);
 }

 MOZ_ASSERT(move.isMemoryOrEffectiveAddress());
 return move;
}
#endif

#ifdef JS_CODEGEN_ARM
static MoveOperand SplitIntoUpperHalf(const MoveOperand& move) {
 if (MoveIsDouble(move)) {
   FloatRegister lowerSingle = move.floatReg().asSingle();
   FloatRegister upperSingle =
       VFPRegister(lowerSingle.code() + 1, VFPRegister::Single);
   return MoveOperand(upperSingle);
 }

 MOZ_ASSERT(move.isMemoryOrEffectiveAddress());
 return MoveOperand(move.base(), move.disp() + sizeof(float));
}
#endif

// Resolves the pending_ list to a list in orderedMoves_.
bool MoveResolver::resolve() {
 resetState();
 orderedMoves_.clear();

 // Upon return from this function, the pending_ list must be cleared.
 auto clearPending = mozilla::MakeScopeExit([this]() { pending_.clear(); });

#ifdef JS_CODEGEN_ARM
 // Some of ARM's double registers alias two of its single registers,
 // but the algorithm below assumes that every register can participate
 // in at most one cycle. To satisfy the algorithm, any double registers
 // that may conflict are split into their single-register halves.
 //
 // This logic is only applicable because ARM only uses registers d0-d15,
 // all of which alias s0-s31. Double registers d16-d31 are unused.
 // Therefore there is never a double move that cannot be split.
 // If this changes in the future, the algorithm will have to be fixed.

 bool splitDoubles = false;
 for (auto iter = pending_.begin(); iter != pending_.end(); ++iter) {
   PendingMove* pm = *iter;

   if (isDoubleAliasedAsSingle(pm->from()) ||
       isDoubleAliasedAsSingle(pm->to())) {
     splitDoubles = true;
     break;
   }
 }

 if (splitDoubles) {
   for (auto iter = pending_.begin(); iter != pending_.end(); ++iter) {
     PendingMove* pm = *iter;

     if (!MoveIsDouble(pm->from()) && !MoveIsDouble(pm->to())) {
       continue;
     }

     MoveOperand fromLower = SplitIntoLowerHalf(pm->from());
     MoveOperand toLower = SplitIntoLowerHalf(pm->to());

     PendingMove* lower =
         movePool_.allocate(fromLower, toLower, MoveOp::FLOAT32);
     if (!lower) {
       return false;
     }

     // Insert the new node before the current position to not affect
     // iteration.
     pending_.insertBefore(pm, lower);

     // Overwrite pm in place for the upper move. Iteration proceeds as normal.
     MoveOperand fromUpper = SplitIntoUpperHalf(pm->from());
     MoveOperand toUpper = SplitIntoUpperHalf(pm->to());
     pm->overwrite(fromUpper, toUpper, MoveOp::FLOAT32);
   }
 }
#endif

 InlineList<PendingMove> stack;

 // This is a depth-first-search without recursion, which tries to find
 // 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:
 //      Let |root| be any pending move removed from P
 //      Add |root| to the traversal stack.
 //      As long as S is not empty:
 //          Let |L| be the most recent move added to S.
 //
 //          Find any pending move M whose source is L's destination, thus
 //          preventing L's move until M has completed.
 //
 //          If a move M was found,
 //              Remove M from the pending list.
 //              If M's destination is |root|,
 //                  Annotate M and |root| as cycles.
 //                  Add M to S.
 //                  do not Add M to O, since M may have other conflictors in P
 //                  that have not yet been processed.
 //              Otherwise,
 //                  Add M to S.
 //         Otherwise,
 //              Remove L from S.
 //              Add L to O.
 //
 while (!pending_.empty()) {
   PendingMove* pm = pending_.popBack();

   // Add this pending move to the cycle detection stack.
   stack.pushBack(pm);

   while (!stack.empty()) {
     PendingMove* blocking = findBlockingMove(stack.peekBack());

     if (blocking) {
       PendingMoveIterator stackiter = stack.begin();
       PendingMove* cycled = findCycledMove(&stackiter, stack.end(), blocking);
       if (cycled) {
         // Find the cycle's start.
         // We annotate cycles at each move in the cycle, and
         // assert that we do not find two cycles in one move chain
         // traversal (which would indicate two moves to the same
         // destination).
         // Since there can be more than one cycle, find them all.
         do {
           cycled->setCycleEnd(curCycles_);
           cycled = findCycledMove(&stackiter, stack.end(), blocking);
         } while (cycled);

         blocking->setCycleBegin(pm->type(), curCycles_);
         curCycles_++;
         pending_.remove(blocking);
         stack.pushBack(blocking);
       } else {
         // This is a new link in the move chain, so keep
         // searching for a cycle.
         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 (!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.aliases(move)) {
     break;
   }
 }

 return orderedMoves_.append(move);
}

void MoveResolver::reorderMove(size_t from, size_t to) {
 MOZ_ASSERT(from != to);

 MoveOp op = orderedMoves_[from];
 if (from < to) {
   for (size_t i = from; i < to; i++) {
     orderedMoves_[i] = orderedMoves_[i + 1];
   }
 } else {
   for (size_t i = from; i > to; i--) {
     orderedMoves_[i] = orderedMoves_[i - 1];
   }
 }
 orderedMoves_[to] = op;
}

void MoveResolver::sortMemoryToMemoryMoves() {
 // Try to reorder memory->memory moves so that they are executed right
 // before a move that clobbers some register. This will allow the move
 // emitter to use that clobbered register as a scratch register for the
 // memory->memory move, if necessary.
 for (size_t i = 0; i < orderedMoves_.length(); i++) {
   const MoveOp& base = orderedMoves_[i];
   if (!base.from().isMemory() || !base.to().isMemory()) {
     continue;
   }
   if (base.type() != MoveOp::GENERAL && base.type() != MoveOp::INT32) {
     continue;
   }

   // Look for an earlier move clobbering a register.
   bool found = false;
   for (int j = i - 1; j >= 0; j--) {
     const MoveOp& previous = orderedMoves_[j];
     if (previous.aliases(base) || previous.isCycleBegin() ||
         previous.isCycleEnd()) {
       break;
     }

     if (previous.to().isGeneralReg()) {
       reorderMove(i, j);
       found = true;
       break;
     }
   }
   if (found) {
     continue;
   }

   // Look for a later move clobbering a register.
   if (i + 1 < orderedMoves_.length()) {
     bool found = false, skippedRegisterUse = false;
     for (size_t j = i + 1; j < orderedMoves_.length(); j++) {
       const MoveOp& later = orderedMoves_[j];
       if (later.aliases(base) || later.isCycleBegin() || later.isCycleEnd()) {
         break;
       }

       if (later.to().isGeneralReg()) {
         if (skippedRegisterUse) {
           reorderMove(i, j);
           found = true;
         } else {
           // There is no move that uses a register between the
           // original memory->memory move and this move that
           // clobbers a register. The move should already be able
           // to use a scratch register, so don't shift anything
           // around.
         }
         break;
       }

       if (later.from().isGeneralReg()) {
         skippedRegisterUse = true;
       }
     }

     if (found) {
       // Redo the search for memory->memory moves at the current
       // index, so we don't skip the move just shifted back.
       i--;
     }
   }
 }
}