diff options
Diffstat (limited to 'js/src/jit/InstructionReordering.cpp')
| -rw-r--r-- | js/src/jit/InstructionReordering.cpp | 190 |
1 files changed, 190 insertions, 0 deletions
diff --git a/js/src/jit/InstructionReordering.cpp b/js/src/jit/InstructionReordering.cpp new file mode 100644 index 000000000..48b619b7c --- /dev/null +++ b/js/src/jit/InstructionReordering.cpp @@ -0,0 +1,190 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * 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; +} + +bool +jit::ReorderInstructions(MIRGenerator* mir, 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++) { + // 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++); + + // Don't reorder instructions within entry blocks, which have special requirements. + if (*block == graph.entryBlock() || *block == graph.osrBlock()) + continue; + + if (block->isLoopHeader()) { + if (!loopHeaders.append(*block)) + return false; + } + + MBasicBlock* innerLoop = loopHeaders.empty() ? nullptr : loopHeaders.back(); + + MInstruction* top = block->safeInsertTop(); + MInstructionReverseIterator rtop = ++block->rbegin(top); + for (MInstructionIterator iter(block->begin(top)); 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; + } + + // Move constants with a single use in the current block to the + // start of the block. Constants won't be reordered by the logic + // below, 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. + if (ins->isConstant() && + ins->hasOneUse() && + ins->usesBegin()->consumer()->block() == *block && + !IsFloatingPointType(ins->type())) + { + iter++; + MInstructionIterator targetIter = block->begin(); + while (targetIter->isConstant() || targetIter->isInterruptCheck()) { + if (*targetIter == ins) + break; + targetIter++; + } + MoveBefore(*block, *targetIter, ins); + 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; + for (MInstructionReverseIterator riter = ++block->rbegin(ins); riter != rtop; riter++) { + MInstruction* prev = *riter; + if (prev->isInterruptCheck()) + 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; + + // We can move the instruction before this one. + target = prev; + } + + iter++; + MoveBefore(*block, target, ins); + } + + if (block->isLoopBackedge()) + loopHeaders.popBack(); + } + + return true; +} |