1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #include "jit/InstructionReordering.h"
8 #include "jit/MIRGraph.h"
11 using namespace js::jit
;
13 static void MoveBefore(MBasicBlock
* block
, MInstruction
* at
,
19 // Update instruction numbers.
20 for (MInstructionIterator
iter(block
->begin(at
)); *iter
!= ins
; iter
++) {
21 MOZ_ASSERT(iter
->id() < ins
->id());
22 iter
->setId(iter
->id() + 1);
24 ins
->setId(at
->id() - 1);
25 block
->moveBefore(at
, ins
);
28 static bool IsLastUse(MDefinition
* ins
, MDefinition
* input
,
29 MBasicBlock
* loopHeader
) {
30 // If we are in a loop, this cannot be the last use of any definitions from
31 // outside the loop, as those definitions can be used in future iterations.
32 if (loopHeader
&& input
->block()->id() < loopHeader
->id()) {
35 for (MUseDefIterator
iter(input
); iter
; iter
++) {
36 // Watch for uses defined in blocks which ReorderInstructions hasn't
37 // processed yet. These nodes have not had their ids set yet.
38 if (iter
.def()->block()->id() > ins
->block()->id()) {
41 if (iter
.def()->id() > ins
->id()) {
48 bool jit::ReorderInstructions(MIRGraph
& graph
) {
49 // Renumber all instructions in the graph as we go.
52 // List of the headers of any loops we are in.
53 Vector
<MBasicBlock
*, 4, SystemAllocPolicy
> loopHeaders
;
55 for (ReversePostorderIterator
block(graph
.rpoBegin());
56 block
!= graph
.rpoEnd(); block
++) {
57 // Renumber all definitions inside the basic blocks.
58 for (MPhiIterator
iter(block
->phisBegin()); iter
!= block
->phisEnd();
60 iter
->setId(nextId
++);
63 for (MInstructionIterator
iter(block
->begin()); iter
!= block
->end();
65 iter
->setId(nextId
++);
68 // Don't reorder instructions within entry blocks, which have special
70 if (*block
== graph
.entryBlock() || *block
== graph
.osrBlock()) {
74 if (block
->isLoopHeader()) {
75 if (!loopHeaders
.append(*block
)) {
80 MBasicBlock
* innerLoop
= loopHeaders
.empty() ? nullptr : loopHeaders
.back();
82 MInstruction
* top
= block
->safeInsertTop();
83 MInstructionReverseIterator rtop
= ++block
->rbegin(top
);
84 for (MInstructionIterator
iter(block
->begin(top
)); iter
!= block
->end();) {
85 MInstruction
* ins
= *iter
;
87 // Filter out some instructions which are never reordered.
88 if (ins
->isEffectful() || !ins
->isMovable() || ins
->resumePoint() ||
89 ins
== block
->lastIns()) {
94 // Move constants with a single use in the current block to the
95 // start of the block. Constants won't be reordered by the logic
96 // below, as they have no inputs. Moving them up as high as
97 // possible can allow their use to be moved up further, though,
98 // and has no cost if the constant is emitted at its use.
99 if (ins
->isConstant() && ins
->hasOneUse() &&
100 ins
->usesBegin()->consumer()->block() == *block
&&
101 !IsFloatingPointType(ins
->type())) {
103 MInstructionIterator targetIter
= block
->begin();
104 while (targetIter
->isConstant() || targetIter
->isInterruptCheck()) {
105 if (*targetIter
== ins
) {
110 MoveBefore(*block
, *targetIter
, ins
);
114 // Look for inputs where this instruction is the last use of that
115 // input. If we move this instruction up, the input's lifetime will
116 // be shortened, modulo resume point uses (which don't need to be
117 // stored in a register, and can be handled by the register
118 // allocator by just spilling at some point with no reload).
119 Vector
<MDefinition
*, 4, SystemAllocPolicy
> lastUsedInputs
;
120 for (size_t i
= 0; i
< ins
->numOperands(); i
++) {
121 MDefinition
* input
= ins
->getOperand(i
);
122 if (!input
->isConstant() && IsLastUse(ins
, input
, innerLoop
)) {
123 if (!lastUsedInputs
.append(input
)) {
129 // Don't try to move instructions which aren't the last use of any
130 // of their inputs (we really ought to move these down instead).
131 if (lastUsedInputs
.length() < 2) {
136 MInstruction
* target
= ins
;
137 MInstruction
* postCallTarget
= nullptr;
138 for (MInstructionReverseIterator riter
= ++block
->rbegin(ins
);
139 riter
!= rtop
; riter
++) {
140 MInstruction
* prev
= *riter
;
141 if (prev
->isInterruptCheck()) {
145 // The instruction can't be moved before any of its uses.
147 for (size_t i
= 0; i
< ins
->numOperands(); i
++) {
148 if (ins
->getOperand(i
) == prev
) {
157 // The instruction can't be moved before an instruction that
158 // stores to a location read by the instruction.
159 if (prev
->isEffectful() &&
160 (ins
->getAliasSet().flags() & prev
->getAliasSet().flags()) &&
161 ins
->mightAlias(prev
) != MDefinition::AliasType::NoAlias
) {
165 // Make sure the instruction will still be the last use of one
166 // of its inputs when moved up this far.
167 for (size_t i
= 0; i
< lastUsedInputs
.length();) {
169 for (size_t j
= 0; j
< prev
->numOperands(); j
++) {
170 if (prev
->getOperand(j
) == lastUsedInputs
[i
]) {
176 lastUsedInputs
[i
] = lastUsedInputs
.back();
177 lastUsedInputs
.popBack();
182 if (lastUsedInputs
.length() < 2) {
186 // If we see a captured call result, either move the instruction before
187 // the corresponding call or don't move it at all.
188 if (prev
->isCallResultCapture()) {
189 if (!postCallTarget
) {
190 postCallTarget
= target
;
192 } else if (postCallTarget
) {
193 MOZ_ASSERT(prev
->isWasmCall() || prev
->isIonToWasmCall());
194 postCallTarget
= nullptr;
197 // We can move the instruction before this one.
201 if (postCallTarget
) {
202 // We would have plonked this instruction between a call and its
203 // captured return value. Instead put it after the last corresponding
205 target
= postCallTarget
;
209 MoveBefore(*block
, target
, ins
);
212 if (block
->isLoopBackedge()) {
213 loopHeaders
.popBack();