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