| /* -*- 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++) { |
| // 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(); |
| |
| for (MPhiIterator iter(block->phisBegin()); iter != block->phisEnd(); iter++) |
| iter->setId(nextId++); |
| |
| for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) |
| iter->setId(nextId++); |
| |
| for (MInstructionIterator iter(block->begin()); 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 != block->rend(); 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)) |
| { |
| 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; |
| } |