Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
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/. */
6 :
7 : #include "jit/InstructionReordering.h"
8 : #include "jit/MIRGraph.h"
9 :
10 : using namespace js;
11 : using namespace js::jit;
12 :
13 : static void
14 35 : MoveBefore(MBasicBlock* block, MInstruction* at, MInstruction* ins)
15 : {
16 35 : if (at == ins)
17 4 : return;
18 :
19 : // Update instruction numbers.
20 189 : for (MInstructionIterator iter(block->begin(at)); *iter != ins; iter++) {
21 158 : MOZ_ASSERT(iter->id() < ins->id());
22 158 : iter->setId(iter->id() + 1);
23 : }
24 31 : ins->setId(at->id() - 1);
25 31 : block->moveBefore(at, ins);
26 : }
27 :
28 : static bool
29 353 : IsLastUse(MDefinition* ins, MDefinition* input, MBasicBlock* loopHeader)
30 : {
31 : // If we are in a loop, this cannot be the last use of any definitions from
32 : // outside the loop, as those definitions can be used in future iterations.
33 353 : if (loopHeader && input->block()->id() < loopHeader->id())
34 39 : return false;
35 645 : 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 443 : if (iter.def()->block()->id() > ins->block()->id())
39 206 : return false;
40 349 : if (iter.def()->id() > ins->id())
41 18 : return false;
42 : }
43 202 : return true;
44 : }
45 :
46 : bool
47 8 : jit::ReorderInstructions(MIRGenerator* mir, MIRGraph& graph)
48 : {
49 : // Renumber all instructions in the graph as we go.
50 8 : size_t nextId = 0;
51 :
52 : // List of the headers of any loops we are in.
53 16 : Vector<MBasicBlock*, 4, SystemAllocPolicy> loopHeaders;
54 :
55 411 : for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) {
56 : // Renumber all definitions inside the basic blocks.
57 578 : for (MPhiIterator iter(block->phisBegin()); iter != block->phisEnd(); iter++)
58 175 : iter->setId(nextId++);
59 :
60 1875 : for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++)
61 1472 : iter->setId(nextId++);
62 :
63 : // Don't reorder instructions within entry blocks, which have special requirements.
64 403 : if (*block == graph.entryBlock() || *block == graph.osrBlock())
65 11 : continue;
66 :
67 392 : if (block->isLoopHeader()) {
68 5 : if (!loopHeaders.append(*block))
69 0 : return false;
70 : }
71 :
72 392 : MBasicBlock* innerLoop = loopHeaders.empty() ? nullptr : loopHeaders.back();
73 :
74 392 : MInstruction* top = block->safeInsertTop();
75 392 : MInstructionReverseIterator rtop = ++block->rbegin(top);
76 1428 : for (MInstructionIterator iter(block->begin(top)); iter != block->end(); ) {
77 1036 : MInstruction* ins = *iter;
78 :
79 : // Filter out some instructions which are never reordered.
80 2984 : if (ins->isEffectful() ||
81 1329 : !ins->isMovable() ||
82 1870 : ins->resumePoint() ||
83 417 : ins == block->lastIns())
84 : {
85 619 : iter++;
86 619 : continue;
87 : }
88 :
89 : // Move constants with a single use in the current block to the
90 : // start of the block. Constants won't be reordered by the logic
91 : // below, as they have no inputs. Moving them up as high as
92 : // possible can allow their use to be moved up further, though,
93 : // and has no cost if the constant is emitted at its use.
94 1686 : if (ins->isConstant() &&
95 111 : ins->hasOneUse() &&
96 1375 : ins->usesBegin()->consumer()->block() == *block &&
97 31 : !IsFloatingPointType(ins->type()))
98 : {
99 31 : iter++;
100 31 : MInstructionIterator targetIter = block->begin();
101 87 : while (targetIter->isConstant() || targetIter->isInterruptCheck()) {
102 28 : if (*targetIter == ins)
103 0 : break;
104 28 : targetIter++;
105 : }
106 31 : MoveBefore(*block, *targetIter, ins);
107 31 : continue;
108 : }
109 :
110 : // Look for inputs where this instruction is the last use of that
111 : // input. If we move this instruction up, the input's lifetime will
112 : // be shortened, modulo resume point uses (which don't need to be
113 : // stored in a register, and can be handled by the register
114 : // allocator by just spilling at some point with no reload).
115 390 : Vector<MDefinition*, 4, SystemAllocPolicy> lastUsedInputs;
116 828 : for (size_t i = 0; i < ins->numOperands(); i++) {
117 442 : MDefinition* input = ins->getOperand(i);
118 442 : if (!input->isConstant() && IsLastUse(ins, input, innerLoop)) {
119 202 : if (!lastUsedInputs.append(input))
120 0 : return false;
121 : }
122 : }
123 :
124 : // Don't try to move instructions which aren't the last use of any
125 : // of their inputs (we really ought to move these down instead).
126 386 : if (lastUsedInputs.length() < 2) {
127 382 : iter++;
128 382 : continue;
129 : }
130 :
131 4 : MInstruction* target = ins;
132 4 : for (MInstructionReverseIterator riter = ++block->rbegin(ins); riter != rtop; riter++) {
133 4 : MInstruction* prev = *riter;
134 4 : if (prev->isInterruptCheck())
135 0 : break;
136 :
137 : // The instruction can't be moved before any of its uses.
138 4 : bool isUse = false;
139 5 : for (size_t i = 0; i < ins->numOperands(); i++) {
140 5 : if (ins->getOperand(i) == prev) {
141 4 : isUse = true;
142 4 : break;
143 : }
144 : }
145 4 : if (isUse)
146 4 : break;
147 :
148 : // The instruction can't be moved before an instruction that
149 : // stores to a location read by the instruction.
150 0 : if (prev->isEffectful() &&
151 0 : (ins->getAliasSet().flags() & prev->getAliasSet().flags()) &&
152 0 : ins->mightAlias(prev) != MDefinition::AliasType::NoAlias)
153 : {
154 0 : break;
155 : }
156 :
157 : // Make sure the instruction will still be the last use of one
158 : // of its inputs when moved up this far.
159 0 : for (size_t i = 0; i < lastUsedInputs.length(); ) {
160 0 : bool found = false;
161 0 : for (size_t j = 0; j < prev->numOperands(); j++) {
162 0 : if (prev->getOperand(j) == lastUsedInputs[i]) {
163 0 : found = true;
164 0 : break;
165 : }
166 : }
167 0 : if (found) {
168 0 : lastUsedInputs[i] = lastUsedInputs.back();
169 0 : lastUsedInputs.popBack();
170 : } else {
171 0 : i++;
172 : }
173 : }
174 0 : if (lastUsedInputs.length() < 2)
175 0 : break;
176 :
177 : // We can move the instruction before this one.
178 0 : target = prev;
179 : }
180 :
181 4 : iter++;
182 4 : MoveBefore(*block, target, ins);
183 : }
184 :
185 392 : if (block->isLoopBackedge())
186 5 : loopHeaders.popBack();
187 : }
188 :
189 8 : return true;
190 : }
|
