diff options
Diffstat (limited to 'js/src/jit/InstructionReordering.cpp')
| -rw-r--r-- | js/src/jit/InstructionReordering.cpp | 248 |
1 files changed, 248 insertions, 0 deletions
diff --git a/js/src/jit/InstructionReordering.cpp b/js/src/jit/InstructionReordering.cpp new file mode 100644 index 0000000000..b399e0bb8c --- /dev/null +++ b/js/src/jit/InstructionReordering.cpp @@ -0,0 +1,248 @@ +/* -*- 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/InstructionReordering.h" +#include "jit/MIRGraph.h" + +using namespace js; +using namespace js::jit; + +static void MoveBefore(MBasicBlock* block, MInstruction* at, + MInstruction* ins) { + if (at == ins) { + return; + } + + // Update instruction numbers. + for (MInstructionIterator iter(block->begin(at)); *iter != ins; iter++) { + MOZ_ASSERT(iter->id() < ins->id()); + iter->setId(iter->id() + 1); + } + ins->setId(at->id() - 1); + block->moveBefore(at, ins); +} + +static bool IsLastUse(MDefinition* ins, MDefinition* input, + MBasicBlock* loopHeader) { + // If we are in a loop, this cannot be the last use of any definitions from + // outside the loop, as those definitions can be used in future iterations. + if (loopHeader && input->block()->id() < loopHeader->id()) { + return false; + } + for (MUseDefIterator iter(input); iter; iter++) { + // Watch for uses defined in blocks which ReorderInstructions hasn't + // processed yet. These nodes have not had their ids set yet. + if (iter.def()->block()->id() > ins->block()->id()) { + return false; + } + if (iter.def()->id() > ins->id()) { + return false; + } + } + return true; +} + +static void MoveConstantsToStart(MBasicBlock* block, + MInstruction* insertionPoint) { + // Move constants with a single use in the current block to the start of the + // block. Constants won't be reordered by ReorderInstructions, as they have no + // inputs. Moving them up as high as possible can allow their use to be moved + // up further, though, and has no cost if the constant is emitted at its use. + + MInstructionIterator iter(block->begin(insertionPoint)); + while (iter != block->end()) { + MInstruction* ins = *iter; + iter++; + + if (!ins->isConstant() || !ins->hasOneUse() || + ins->usesBegin()->consumer()->block() != block || + IsFloatingPointType(ins->type())) { + continue; + } + + MOZ_ASSERT(ins->isMovable()); + MOZ_ASSERT(insertionPoint != ins); + + // Note: we don't need to use MoveBefore here because MoveConstantsToStart + // is called right before we renumber all instructions in this block. + block->moveBefore(insertionPoint, ins); + } +} + +bool jit::ReorderInstructions(MIRGraph& graph) { + // Renumber all instructions in the graph as we go. + size_t nextId = 0; + + // List of the headers of any loops we are in. + Vector<MBasicBlock*, 4, SystemAllocPolicy> loopHeaders; + + for (ReversePostorderIterator block(graph.rpoBegin()); + block != graph.rpoEnd(); block++) { + // Don't reorder instructions within entry blocks, which have special + // requirements. + bool isEntryBlock = + *block == graph.entryBlock() || *block == graph.osrBlock(); + + MInstruction* insertionPoint = nullptr; + if (!isEntryBlock) { + // Move constants to the start of the block before renumbering all + // instructions. + insertionPoint = block->safeInsertTop(); + MoveConstantsToStart(*block, insertionPoint); + } + + // Renumber all definitions inside the basic blocks. + for (MPhiIterator iter(block->phisBegin()); iter != block->phisEnd(); + iter++) { + iter->setId(nextId++); + } + + for (MInstructionIterator iter(block->begin()); iter != block->end(); + iter++) { + iter->setId(nextId++); + } + + if (isEntryBlock) { + continue; + } + + if (block->isLoopHeader()) { + if (!loopHeaders.append(*block)) { + return false; + } + } + + MBasicBlock* innerLoop = loopHeaders.empty() ? nullptr : loopHeaders.back(); + + MInstructionReverseIterator rtop = ++block->rbegin(insertionPoint); + for (MInstructionIterator iter(block->begin(insertionPoint)); + iter != block->end();) { + MInstruction* ins = *iter; + + // Filter out some instructions which are never reordered. + if (ins->isEffectful() || !ins->isMovable() || ins->resumePoint() || + ins == block->lastIns()) { + iter++; + continue; + } + + // Look for inputs where this instruction is the last use of that + // input. If we move this instruction up, the input's lifetime will + // be shortened, modulo resume point uses (which don't need to be + // stored in a register, and can be handled by the register + // allocator by just spilling at some point with no reload). + Vector<MDefinition*, 4, SystemAllocPolicy> lastUsedInputs; + for (size_t i = 0; i < ins->numOperands(); i++) { + MDefinition* input = ins->getOperand(i); + if (!input->isConstant() && IsLastUse(ins, input, innerLoop)) { + if (!lastUsedInputs.append(input)) { + return false; + } + } + } + + // Don't try to move instructions which aren't the last use of any + // of their inputs (we really ought to move these down instead). + if (lastUsedInputs.length() < 2) { + iter++; + continue; + } + + MInstruction* target = ins; + MInstruction* postCallTarget = nullptr; + for (MInstructionReverseIterator riter = ++block->rbegin(ins); + riter != rtop; riter++) { + MInstruction* prev = *riter; + if (prev->isInterruptCheck()) { + break; + } + if (prev->isSetInitializedLength()) { + break; + } + + // The instruction can't be moved before any of its uses. + bool isUse = false; + for (size_t i = 0; i < ins->numOperands(); i++) { + if (ins->getOperand(i) == prev) { + isUse = true; + break; + } + } + if (isUse) { + break; + } + + // The instruction can't be moved before an instruction that + // stores to a location read by the instruction. + if (prev->isEffectful() && + (ins->getAliasSet().flags() & prev->getAliasSet().flags()) && + ins->mightAlias(prev) != MDefinition::AliasType::NoAlias) { + break; + } + + // Make sure the instruction will still be the last use of one + // of its inputs when moved up this far. + for (size_t i = 0; i < lastUsedInputs.length();) { + bool found = false; + for (size_t j = 0; j < prev->numOperands(); j++) { + if (prev->getOperand(j) == lastUsedInputs[i]) { + found = true; + break; + } + } + if (found) { + lastUsedInputs[i] = lastUsedInputs.back(); + lastUsedInputs.popBack(); + } else { + i++; + } + } + if (lastUsedInputs.length() < 2) { + break; + } + + // If we see a captured call result, either move the instruction before + // the corresponding call or don't move it at all. + if (prev->isCallResultCapture()) { + if (!postCallTarget) { + postCallTarget = target; + } + } else if (postCallTarget) { + MOZ_ASSERT(MWasmCallBase::IsWasmCall(prev) || + prev->isIonToWasmCall()); + postCallTarget = nullptr; + } + + // We can move the instruction before this one. + target = prev; + } + + if (postCallTarget) { + // We would have plonked this instruction between a call and its + // captured return value. Instead put it after the last corresponding + // return value. + target = postCallTarget; + } + + iter++; + MoveBefore(*block, target, ins); + + // Instruction reordering can move a bailing instruction up past a call + // that throws an exception, causing spurious bailouts. This should rarely + // be an issue in practice, so we only update the bailout kind if we don't + // have anything more specific. + if (ins->bailoutKind() == BailoutKind::TranspiledCacheIR) { + ins->setBailoutKind(BailoutKind::InstructionReordering); + } + } + + if (block->isLoopBackedge()) { + loopHeaders.popBack(); + } + } + + return true; +} |