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/AliasAnalysis.h"
8
9 #include <stdio.h>
10
11 #include "jit/Ion.h"
12 #include "jit/IonBuilder.h"
13 #include "jit/JitSpewer.h"
14 #include "jit/MIR.h"
15 #include "jit/MIRGraph.h"
16
17 #include "vm/Printer.h"
18
19 using namespace js;
20 using namespace js::jit;
21
22 using mozilla::Array;
23
24 namespace js {
25 namespace jit {
26
27 class LoopAliasInfo : public TempObject
28 {
29 private:
30 LoopAliasInfo* outer_;
31 MBasicBlock* loopHeader_;
32 MInstructionVector invariantLoads_;
33
34 public:
LoopAliasInfo(TempAllocator & alloc,LoopAliasInfo * outer,MBasicBlock * loopHeader)35 LoopAliasInfo(TempAllocator& alloc, LoopAliasInfo* outer, MBasicBlock* loopHeader)
36 : outer_(outer), loopHeader_(loopHeader), invariantLoads_(alloc)
37 { }
38
loopHeader() const39 MBasicBlock* loopHeader() const {
40 return loopHeader_;
41 }
outer() const42 LoopAliasInfo* outer() const {
43 return outer_;
44 }
addInvariantLoad(MInstruction * ins)45 bool addInvariantLoad(MInstruction* ins) {
46 return invariantLoads_.append(ins);
47 }
invariantLoads() const48 const MInstructionVector& invariantLoads() const {
49 return invariantLoads_;
50 }
firstInstruction() const51 MInstruction* firstInstruction() const {
52 return *loopHeader_->begin();
53 }
54 };
55
56 } // namespace jit
57 } // namespace js
58
59 namespace {
60
61 // Iterates over the flags in an AliasSet.
62 class AliasSetIterator
63 {
64 private:
65 uint32_t flags;
66 unsigned pos;
67
68 public:
AliasSetIterator(AliasSet set)69 explicit AliasSetIterator(AliasSet set)
70 : flags(set.flags()), pos(0)
71 {
72 while (flags && (flags & 1) == 0) {
73 flags >>= 1;
74 pos++;
75 }
76 }
operator ++(int)77 AliasSetIterator& operator ++(int) {
78 do {
79 flags >>= 1;
80 pos++;
81 } while (flags && (flags & 1) == 0);
82 return *this;
83 }
operator bool() const84 explicit operator bool() const {
85 return !!flags;
86 }
operator *() const87 unsigned operator*() const {
88 MOZ_ASSERT(pos < AliasSet::NumCategories);
89 return pos;
90 }
91 };
92
93 } /* anonymous namespace */
94
AliasAnalysis(MIRGenerator * mir,MIRGraph & graph)95 AliasAnalysis::AliasAnalysis(MIRGenerator* mir, MIRGraph& graph)
96 : mir(mir),
97 graph_(graph),
98 loop_(nullptr)
99 {
100 }
101
102 // Whether there might be a path from src to dest, excluding loop backedges. This is
103 // approximate and really ought to depend on precomputed reachability information.
104 static inline bool
BlockMightReach(MBasicBlock * src,MBasicBlock * dest)105 BlockMightReach(MBasicBlock* src, MBasicBlock* dest)
106 {
107 while (src->id() <= dest->id()) {
108 if (src == dest)
109 return true;
110 switch (src->numSuccessors()) {
111 case 0:
112 return false;
113 case 1: {
114 MBasicBlock* successor = src->getSuccessor(0);
115 if (successor->id() <= src->id())
116 return true; // Don't iloop.
117 src = successor;
118 break;
119 }
120 default:
121 return true;
122 }
123 }
124 return false;
125 }
126
127 static void
IonSpewDependency(MInstruction * load,MInstruction * store,const char * verb,const char * reason)128 IonSpewDependency(MInstruction* load, MInstruction* store, const char* verb, const char* reason)
129 {
130 if (!JitSpewEnabled(JitSpew_Alias))
131 return;
132
133 Fprinter& out = JitSpewPrinter();
134 out.printf("Load ");
135 load->printName(out);
136 out.printf(" %s on store ", verb);
137 store->printName(out);
138 out.printf(" (%s)\n", reason);
139 }
140
141 static void
IonSpewAliasInfo(const char * pre,MInstruction * ins,const char * post)142 IonSpewAliasInfo(const char* pre, MInstruction* ins, const char* post)
143 {
144 if (!JitSpewEnabled(JitSpew_Alias))
145 return;
146
147 Fprinter& out = JitSpewPrinter();
148 out.printf("%s ", pre);
149 ins->printName(out);
150 out.printf(" %s\n", post);
151 }
152
153 // This pass annotates every load instruction with the last store instruction
154 // on which it depends. The algorithm is optimistic in that it ignores explicit
155 // dependencies and only considers loads and stores.
156 //
157 // Loads inside loops only have an implicit dependency on a store before the
158 // loop header if no instruction inside the loop body aliases it. To calculate
159 // this efficiently, we maintain a list of maybe-invariant loads and the combined
160 // alias set for all stores inside the loop. When we see the loop's backedge, this
161 // information is used to mark every load we wrongly assumed to be loop invariant as
162 // having an implicit dependency on the last instruction of the loop header, so that
163 // it's never moved before the loop header.
164 //
165 // The algorithm depends on the invariant that both control instructions and effectful
166 // instructions (stores) are never hoisted.
167 bool
analyze()168 AliasAnalysis::analyze()
169 {
170 Vector<MInstructionVector, AliasSet::NumCategories, JitAllocPolicy> stores(alloc());
171
172 // Initialize to the first instruction.
173 MInstruction* firstIns = *graph_.entryBlock()->begin();
174 for (unsigned i = 0; i < AliasSet::NumCategories; i++) {
175 MInstructionVector defs(alloc());
176 if (!defs.append(firstIns))
177 return false;
178 if (!stores.append(Move(defs)))
179 return false;
180 }
181
182 // Type analysis may have inserted new instructions. Since this pass depends
183 // on the instruction number ordering, all instructions are renumbered.
184 uint32_t newId = 0;
185
186 for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
187 if (mir->shouldCancel("Alias Analysis (main loop)"))
188 return false;
189
190 if (block->isLoopHeader()) {
191 JitSpew(JitSpew_Alias, "Processing loop header %d", block->id());
192 loop_ = new(alloc()) LoopAliasInfo(alloc(), loop_, *block);
193 }
194
195 for (MPhiIterator def(block->phisBegin()), end(block->phisEnd()); def != end; ++def)
196 def->setId(newId++);
197
198 for (MInstructionIterator def(block->begin()), end(block->begin(block->lastIns()));
199 def != end;
200 ++def)
201 {
202 def->setId(newId++);
203
204 AliasSet set = def->getAliasSet();
205 if (set.isNone())
206 continue;
207
208 // For the purposes of alias analysis, all recoverable operations
209 // are treated as effect free as the memory represented by these
210 // operations cannot be aliased by others.
211 if (def->canRecoverOnBailout())
212 continue;
213
214 if (set.isStore()) {
215 for (AliasSetIterator iter(set); iter; iter++) {
216 if (!stores[*iter].append(*def))
217 return false;
218 }
219
220 if (JitSpewEnabled(JitSpew_Alias)) {
221 Fprinter& out = JitSpewPrinter();
222 out.printf("Processing store ");
223 def->printName(out);
224 out.printf(" (flags %x)\n", set.flags());
225 }
226 } else {
227 // Find the most recent store on which this instruction depends.
228 MInstruction* lastStore = firstIns;
229
230 for (AliasSetIterator iter(set); iter; iter++) {
231 MInstructionVector& aliasedStores = stores[*iter];
232 for (int i = aliasedStores.length() - 1; i >= 0; i--) {
233 MInstruction* store = aliasedStores[i];
234 if (def->mightAlias(store) && BlockMightReach(store->block(), *block)) {
235 if (lastStore->id() < store->id())
236 lastStore = store;
237 break;
238 }
239 }
240 }
241
242 def->setDependency(lastStore);
243 IonSpewDependency(*def, lastStore, "depends", "");
244
245 // If the last store was before the current loop, we assume this load
246 // is loop invariant. If a later instruction writes to the same location,
247 // we will fix this at the end of the loop.
248 if (loop_ && lastStore->id() < loop_->firstInstruction()->id()) {
249 if (!loop_->addInvariantLoad(*def))
250 return false;
251 }
252 }
253 }
254
255 // Renumber the last instruction, as the analysis depends on this and the order.
256 block->lastIns()->setId(newId++);
257
258 if (block->isLoopBackedge()) {
259 MOZ_ASSERT(loop_->loopHeader() == block->loopHeaderOfBackedge());
260 JitSpew(JitSpew_Alias, "Processing loop backedge %d (header %d)", block->id(),
261 loop_->loopHeader()->id());
262 LoopAliasInfo* outerLoop = loop_->outer();
263 MInstruction* firstLoopIns = *loop_->loopHeader()->begin();
264
265 const MInstructionVector& invariant = loop_->invariantLoads();
266
267 for (unsigned i = 0; i < invariant.length(); i++) {
268 MInstruction* ins = invariant[i];
269 AliasSet set = ins->getAliasSet();
270 MOZ_ASSERT(set.isLoad());
271
272 bool hasAlias = false;
273 for (AliasSetIterator iter(set); iter; iter++) {
274 MInstructionVector& aliasedStores = stores[*iter];
275 for (int i = aliasedStores.length() - 1;; i--) {
276 MInstruction* store = aliasedStores[i];
277 if (store->id() < firstLoopIns->id())
278 break;
279 if (ins->mightAlias(store)) {
280 hasAlias = true;
281 IonSpewDependency(ins, store, "aliases", "store in loop body");
282 break;
283 }
284 }
285 if (hasAlias)
286 break;
287 }
288
289 if (hasAlias) {
290 // This instruction depends on stores inside the loop body. Mark it as having a
291 // dependency on the last instruction of the loop header. The last instruction is a
292 // control instruction and these are never hoisted.
293 MControlInstruction* controlIns = loop_->loopHeader()->lastIns();
294 IonSpewDependency(ins, controlIns, "depends", "due to stores in loop body");
295 ins->setDependency(controlIns);
296 } else {
297 IonSpewAliasInfo("Load", ins, "does not depend on any stores in this loop");
298
299 if (outerLoop && ins->dependency()->id() < outerLoop->firstInstruction()->id()) {
300 IonSpewAliasInfo("Load", ins, "may be invariant in outer loop");
301 if (!outerLoop->addInvariantLoad(ins))
302 return false;
303 }
304 }
305 }
306 loop_ = loop_->outer();
307 }
308 }
309
310 MOZ_ASSERT(loop_ == nullptr);
311 return true;
312 }
313