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