1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
/* -*- 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;
}
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++) {
// 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;
}