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/FlowAliasAnalysis.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 LoopInfo : public TempObject
29 : {
30 : private:
31 : LoopInfo* outer_;
32 : MBasicBlock* loopHeader_;
33 : MDefinitionVector loopinvariant_;
34 :
35 : public:
36 0 : LoopInfo(TempAllocator& alloc, LoopInfo* outer, MBasicBlock* loopHeader)
37 0 : : outer_(outer), loopHeader_(loopHeader), loopinvariant_(alloc)
38 0 : { }
39 :
40 0 : MBasicBlock* loopHeader() const {
41 0 : return loopHeader_;
42 : }
43 0 : LoopInfo* outer() const {
44 0 : return outer_;
45 : }
46 0 : MDefinitionVector& loopinvariant() {
47 0 : return loopinvariant_;
48 : }
49 : };
50 :
51 : static bool
52 0 : KeepBlock(MBasicBlock *block)
53 : {
54 : // Any block that is predecessor to a loopheader need to be kept.
55 : // We need it to process possible loop invariant loads.
56 0 : if (block->numSuccessors() == 1 && block->getSuccessor(0)->isLoopHeader())
57 0 : return true;
58 :
59 : #ifdef DEBUG
60 : // We assume a predecessor to a loopheader has one successor.
61 0 : for (size_t i = 0; i < block->numSuccessors(); i++)
62 0 : MOZ_ASSERT(!block->getSuccessor(i)->isLoopHeader());
63 : #endif
64 :
65 0 : return false;
66 : }
67 :
68 : class GraphStoreInfo : public TempObject
69 : {
70 : // The current BlockStoreInfo while iterating the block untill,
71 : // it contains the store info at the end of the block.
72 : BlockStoreInfo* current_;
73 :
74 : // Vector with pointer to BlockStoreInfo at the end of the block for every block.
75 : // Only keeping the info during iteration if needed, else contains nullptr.
76 : GraphStoreVector stores_;
77 :
78 : // All BlockStoreInfo's that aren't needed anymore and can be reused.
79 : GraphStoreVector empty_;
80 :
81 : public:
82 0 : explicit GraphStoreInfo(TempAllocator& alloc)
83 0 : : current_(nullptr),
84 : stores_(alloc),
85 0 : empty_(alloc)
86 0 : { }
87 :
88 0 : bool reserve(size_t num) {
89 0 : return stores_.appendN(nullptr, num);
90 : }
91 :
92 0 : BlockStoreInfo& current() {
93 0 : return *current_;
94 : }
95 :
96 0 : void unsetCurrent() {
97 0 : current_ = nullptr;
98 0 : }
99 :
100 0 : BlockStoreInfo* newCurrent(TempAllocator& alloc, MBasicBlock* block) {
101 0 : BlockStoreInfo *info = nullptr;
102 0 : if (empty_.length() != 0) {
103 0 : info = empty_.popCopy();
104 : } else {
105 0 : info = (BlockStoreInfo*) alloc.allocate(sizeof(BlockStoreInfo));
106 0 : if (!info)
107 0 : return nullptr;
108 0 : new(info) BlockStoreInfo(alloc);
109 : }
110 :
111 0 : stores_[block->id()] = info;
112 0 : current_ = info;
113 0 : return current_;
114 : }
115 :
116 0 : void swap(MBasicBlock* block1, MBasicBlock* block2) {
117 0 : BlockStoreInfo* info = stores_[block1->id()];
118 0 : stores_[block1->id()] = stores_[block2->id()];
119 0 : stores_[block2->id()] = info;
120 0 : if (stores_[block1->id()] == current_)
121 0 : current_ = stores_[block2->id()];
122 0 : else if (stores_[block2->id()] == current_)
123 0 : current_ = stores_[block1->id()];
124 0 : }
125 :
126 0 : bool maybeFreePredecessorBlocks(MBasicBlock* block) {
127 0 : for (size_t i=0; i < block->numPredecessors(); i++) {
128 :
129 : // For some blocks we cannot free the store info.
130 0 : if (KeepBlock(block->getPredecessor(i)))
131 0 : continue;
132 :
133 : // Check the given block is the last successor.
134 0 : bool release = true;
135 0 : for (size_t j = 0; j < block->getPredecessor(i)->numSuccessors(); j++) {
136 0 : if (block->getPredecessor(i)->getSuccessor(j)->id() > block->id()) {
137 0 : release = false;
138 0 : break;
139 : }
140 : }
141 0 : if (release) {
142 0 : BlockStoreInfo *info = stores_[block->getPredecessor(i)->id()];
143 0 : if (!empty_.append(info))
144 0 : return false;
145 0 : info->clear();
146 :
147 0 : stores_[block->getPredecessor(i)->id()] = nullptr;
148 : }
149 : }
150 0 : return true;
151 : }
152 :
153 0 : BlockStoreInfo& get(MBasicBlock* block) {
154 0 : MOZ_ASSERT(stores_[block->id()] != current_);
155 0 : return *stores_[block->id()];
156 : }
157 : };
158 :
159 : } // namespace jit
160 : } // namespace js
161 :
162 :
163 0 : FlowAliasAnalysis::FlowAliasAnalysis(MIRGenerator* mir, MIRGraph& graph)
164 : : AliasAnalysisShared(mir, graph),
165 : loop_(nullptr),
166 0 : output_(graph_.alloc()),
167 0 : worklist_(graph_.alloc())
168 : {
169 0 : stores_ = new(graph_.alloc()) GraphStoreInfo(graph_.alloc());
170 0 : }
171 :
172 : template <typename T>
173 : static bool
174 0 : AppendToWorklist(MDefinitionVector& worklist, T& stores)
175 : {
176 0 : if (!worklist.reserve(worklist.length() + stores.length()))
177 0 : return false;
178 :
179 0 : for (size_t j = 0; j < stores.length(); j++) {
180 0 : MOZ_ASSERT(stores[j]);
181 0 : if (stores[j]->isInWorklist())
182 0 : continue;
183 :
184 0 : worklist.infallibleAppend(stores[j]);
185 0 : stores[j]->setInWorklist();
186 : }
187 0 : return true;
188 : }
189 :
190 : static void
191 0 : SetNotInWorkList(MDefinitionVector& worklist)
192 : {
193 0 : for (size_t item = 0; item < worklist.length(); item++)
194 0 : worklist[item]->setNotInWorklistUnchecked();
195 0 : }
196 :
197 : static bool
198 0 : LoadAliasesStore(MDefinition* load, MDefinition* store)
199 : {
200 : // Always alias first instruction of graph.
201 0 : if (store->id() == 0)
202 0 : return true;
203 :
204 : // Default to alias control instructions which indicates loops.
205 : // Control instructions are special, since we need to determine
206 : // if it aliases anything in the full loop. Which we do lateron.
207 0 : if (store->isControlInstruction())
208 0 : return true;
209 :
210 : // Check if the alias categories alias eachother.
211 0 : if ((load->getAliasSet() & store->getAliasSet()).isNone())
212 0 : return false;
213 :
214 : // On any operation that has a specific alias category we can use TI to know
215 : // the objects operating on don't intersect.
216 0 : MDefinition::AliasType mightAlias = AliasAnalysisShared::genericMightAlias(load, store);
217 0 : if (mightAlias == MDefinition::AliasType::NoAlias)
218 0 : return false;
219 :
220 : // Check if the instruction might alias eachother.
221 0 : mightAlias = load->mightAlias(store);
222 0 : if (mightAlias == MDefinition::AliasType::NoAlias)
223 0 : return false;
224 :
225 0 : return true;
226 : }
227 :
228 : #ifdef JS_JITSPEW
229 : static void
230 0 : DumpAliasSet(AliasSet set)
231 : {
232 0 : Fprinter &print = JitSpewPrinter();
233 :
234 0 : if (set.flags() == AliasSet::Any) {
235 0 : print.printf("Any");
236 0 : return;
237 : }
238 :
239 0 : bool first = true;
240 0 : for (AliasSetIterator iter(set); iter; iter++) {
241 0 : if (!first)
242 0 : print.printf(", ");
243 0 : print.printf("%s", AliasSet::Name(*iter));
244 0 : first = false;
245 : }
246 : }
247 : #endif
248 :
249 : #ifdef JS_JITSPEW
250 : static void
251 0 : DumpStoreList(BlockStoreInfo& stores)
252 : {
253 0 : Fprinter &print = JitSpewPrinter();
254 0 : if (stores.length() == 0) {
255 0 : print.printf("empty");
256 0 : return;
257 : }
258 0 : bool first = true;
259 0 : for (size_t i = 0; i < stores.length(); i++) {
260 0 : if (!first)
261 0 : print.printf(", ");
262 0 : if (!stores[i]) {
263 0 : print.printf("nullptr");
264 0 : continue;
265 : }
266 0 : MOZ_ASSERT(stores[i]->isControlInstruction() ||
267 : stores[i]->getAliasSet().isStore() ||
268 : stores[i]->id() == 0);
269 0 : MDefinition::PrintOpcodeName(print, stores[i]->op());
270 0 : print.printf("%d", stores[i]->id());
271 0 : first = false;
272 : }
273 : }
274 : #endif
275 :
276 : static void
277 0 : DumpAnalyzeStart()
278 : {
279 : #ifdef JS_JITSPEW
280 0 : if (JitSpewEnabled(JitSpew_Alias) || JitSpewEnabled(JitSpew_AliasSummaries)) {
281 0 : Fprinter &print = JitSpewPrinter();
282 0 : JitSpewHeader(JitSpewEnabled(JitSpew_Alias) ? JitSpew_Alias : JitSpew_AliasSummaries);
283 0 : print.printf("Running Alias Analysis on graph\n");
284 : }
285 : #endif
286 0 : }
287 :
288 : static void
289 0 : DumpBlockStart(MBasicBlock* block)
290 : {
291 : #ifdef JS_JITSPEW
292 0 : if (JitSpewEnabled(JitSpew_Alias) || JitSpewEnabled(JitSpew_AliasSummaries)) {
293 0 : Fprinter &print = JitSpewPrinter();
294 0 : JitSpewHeader(JitSpewEnabled(JitSpew_Alias)?JitSpew_Alias:JitSpew_AliasSummaries);
295 0 : if (block->isLoopHeader())
296 0 : print.printf(" Visiting block %d (loopheader)\n", block->id());
297 : else
298 0 : print.printf(" Visiting block %d\n", block->id());
299 : }
300 : #endif
301 0 : }
302 :
303 : static void
304 0 : DumpProcessingDeferredLoads(MBasicBlock* loopHeader)
305 : {
306 : #ifdef JS_JITSPEW
307 0 : if (JitSpewEnabled(JitSpew_Alias)) {
308 0 : Fprinter &print = JitSpewPrinter();
309 0 : JitSpewHeader(JitSpew_Alias);
310 0 : print.printf(" Process deferred loads of loop %d\n", loopHeader->id());
311 : }
312 : #endif
313 0 : }
314 :
315 : static void
316 0 : DumpBlockSummary(MBasicBlock* block, BlockStoreInfo& blockInfo)
317 : {
318 : #ifdef JS_JITSPEW
319 0 : if (JitSpewEnabled(JitSpew_AliasSummaries)) {
320 0 : Fprinter &print = JitSpewPrinter();
321 0 : JitSpewHeader(JitSpew_AliasSummaries);
322 0 : print.printf(" Store at end of block: ");
323 0 : DumpStoreList(blockInfo);
324 0 : print.printf("\n");
325 : }
326 : #endif
327 0 : }
328 :
329 : static void
330 0 : DumpStore(MDefinition* store)
331 : {
332 : #ifdef JS_JITSPEW
333 0 : if (JitSpewEnabled(JitSpew_Alias)) {
334 0 : Fprinter &print = JitSpewPrinter();
335 0 : JitSpewHeader(JitSpew_Alias);
336 0 : print.printf(" Store ");
337 0 : store->PrintOpcodeName(print, store->op());
338 0 : print.printf("%d with flags (", store->id());
339 0 : DumpAliasSet(store->getAliasSet());
340 0 : print.printf(")\n");
341 : }
342 : #endif
343 0 : }
344 :
345 : static void
346 0 : DumpLoad(MDefinition* load)
347 : {
348 : #ifdef JS_JITSPEW
349 0 : if (JitSpewEnabled(JitSpew_Alias)) {
350 0 : Fprinter &print = JitSpewPrinter();
351 0 : JitSpewHeader(JitSpew_Alias);
352 0 : print.printf(" Load ");
353 0 : load->PrintOpcodeName(print, load->op());
354 0 : print.printf("%d", load->id());
355 0 : print.printf(" with flag (");
356 0 : DumpAliasSet(load->getAliasSet());
357 0 : print.printf(")\n");
358 : }
359 : #endif
360 0 : }
361 :
362 : static void
363 0 : DumpLoadOutcome(MDefinition* load, MDefinitionVector& stores, bool defer)
364 : {
365 : #ifdef JS_JITSPEW
366 : // Spew what we did.
367 0 : if (JitSpewEnabled(JitSpew_Alias)) {
368 0 : Fprinter &print = JitSpewPrinter();
369 0 : JitSpewHeader(JitSpew_Alias);
370 0 : print.printf(" Marked depending on ");
371 0 : DumpStoreList(stores);
372 0 : if (defer)
373 0 : print.printf(" deferred");
374 0 : print.printf("\n");
375 : }
376 : #endif
377 0 : }
378 :
379 : static void
380 0 : DumpLoopInvariant(MDefinition* load, MBasicBlock* loopheader, bool loopinvariant,
381 : MDefinitionVector& loopInvariantDependency)
382 : {
383 : #ifdef JS_JITSPEW
384 0 : if (JitSpewEnabled(JitSpew_Alias)) {
385 0 : Fprinter &print = JitSpewPrinter();
386 0 : JitSpewHeader(JitSpew_Alias);
387 0 : if (!loopinvariant) {
388 0 : print.printf(" Determine not loop invariant to loop %d.\n", loopheader->id());
389 : } else {
390 0 : print.printf(" Determine loop invariant to loop %d. Dependendy is now: ", loopheader->id());
391 0 : DumpStoreList(loopInvariantDependency);
392 0 : print.printf("\n");
393 : }
394 : }
395 : #endif
396 0 : }
397 :
398 : static void
399 0 : DumpImprovement(MDefinition *load, MDefinitionVector& input, MDefinitionVector& output)
400 : {
401 : #ifdef JS_JITSPEW
402 0 : if (JitSpewEnabled(JitSpew_Alias)) {
403 0 : Fprinter &print = JitSpewPrinter();
404 0 : JitSpewHeader(JitSpew_Alias);
405 0 : print.printf(" Improve dependency from %d", load->id());
406 0 : DumpStoreList(input);
407 0 : print.printf(" to ");
408 0 : DumpStoreList(output);
409 0 : print.printf("\n");
410 : }
411 : #endif
412 0 : }
413 :
414 : // Flow Sensitive Alias Analysis.
415 : //
416 : // This pass annotates every load instructions with the last store instruction
417 : // on which it depends in their dependency_ field. For loop variant instructions
418 : // this will depend on the control instruction in the specific loop it cannot
419 : // get hoisted out (if there is no store between start loopheader and
420 : // instruction).
421 : //
422 : // We visit the graph in RPO and keep track of the last stores in that block.
423 : // Upon entering a block we merge the stores information of the predecessors.
424 : // Only loopheaders are different, since we eagerly make it depend on the
425 : // control instruction of the loopheader.
426 : //
427 : // During the iteration of a block we keep a running store dependeny list.
428 : // At the end of the iteration, this will contain the last stores
429 : // (which we keep for successors).
430 : //
431 : // When encountering a store or load we do:
432 : // - Store: we update the current block store info and put a StoreDependency
433 : // to create a store-chain.
434 : //
435 : // - Load: we take the current block store dependency info and improve that by
436 : // following the store-chain when encountering not aliasing store. Upon
437 : // encountering a control instruction (indicates loop) it solely depends on
438 : // we defer until the loop has been examined.
439 : //
440 : // The algorithm depends on the invariant that both control instructions and effectful
441 : // instructions (stores) are never hoisted.
442 :
443 : bool
444 0 : FlowAliasAnalysis::analyze()
445 : {
446 0 : DumpAnalyzeStart();
447 :
448 : // Type analysis may have inserted new instructions. Since this pass depends
449 : // on the instruction number ordering, all instructions are renumbered.
450 0 : uint32_t newId = 0;
451 :
452 0 : if (!stores_->reserve(graph_.numBlocks()))
453 0 : return false;
454 :
455 0 : for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
456 0 : if (mir->shouldCancel("Alias Analysis (main loop)"))
457 0 : return false;
458 :
459 0 : DumpBlockStart(*block);
460 :
461 0 : if (!computeBlockStores(*block))
462 0 : return false;
463 0 : if (!stores_->maybeFreePredecessorBlocks(*block))
464 0 : return false;
465 :
466 0 : for (MPhiIterator def(block->phisBegin()), end(block->phisEnd()); def != end; ++def)
467 0 : def->setId(newId++);
468 :
469 0 : BlockStoreInfo& blockInfo = stores_->current();
470 :
471 : // When the store dependencies is empty it means we have a disconnected
472 : // graph. Those blocks will never get reached but it is only fixed up
473 : // after GVN. Don't run AA on those blocks.
474 0 : if (blockInfo.length() == 0)
475 0 : continue;
476 :
477 0 : if (block->isLoopHeader())
478 0 : loop_ = new(alloc()) LoopInfo(alloc(), loop_, *block);
479 :
480 0 : for (MInstructionIterator def(block->begin()), end(block->begin(block->lastIns()));
481 : def != end;
482 : ++def)
483 : {
484 0 : def->setId(newId++);
485 :
486 : // For the purposes of alias analysis, all recoverable operations
487 : // are treated as effect free as the memory represented by these
488 : // operations cannot be aliased by others.
489 0 : if (def->canRecoverOnBailout())
490 0 : continue;
491 :
492 0 : AliasSet set = def->getAliasSet();
493 0 : if (set.isStore()) {
494 0 : if (!processStore(blockInfo, *def))
495 0 : return false;
496 0 : } else if (set.isLoad()) {
497 0 : if (!processLoad(blockInfo, *def))
498 0 : return false;
499 : }
500 : }
501 :
502 0 : block->lastIns()->setId(newId++);
503 :
504 0 : if (block->isLoopBackedge()) {
505 0 : stores_->unsetCurrent();
506 :
507 0 : LoopInfo* info = loop_;
508 0 : loop_ = loop_->outer();
509 :
510 0 : if (!processDeferredLoads(info))
511 0 : return false;
512 : }
513 :
514 0 : DumpBlockSummary(*block, blockInfo);
515 : }
516 :
517 0 : spewDependencyList();
518 0 : return true;
519 : }
520 :
521 : bool
522 0 : FlowAliasAnalysis::processStore(BlockStoreInfo& blockInfo, MDefinition* store)
523 : {
524 : // Compute and set dependency information.
525 0 : if (!saveStoreDependency(store, blockInfo))
526 0 : return false;
527 :
528 : // Update the block store dependency vector.
529 0 : blockInfo.clear();
530 0 : if (!blockInfo.append(store))
531 0 : return false;
532 :
533 : // Spew what we did.
534 0 : DumpStore(store);
535 0 : return true;
536 : }
537 :
538 : bool
539 0 : FlowAliasAnalysis::processLoad(BlockStoreInfo& blockInfo, MDefinition* load)
540 : {
541 0 : DumpLoad(load);
542 :
543 : // Compute dependency information.
544 0 : MDefinitionVector& dependencies = blockInfo;
545 0 : if (!improveDependency(load, dependencies, output_))
546 0 : return false;
547 0 : saveLoadDependency(load, output_);
548 :
549 : // If possible defer when better loop information is present.
550 0 : if (deferImproveDependency(output_)) {
551 0 : if (!loop_->loopinvariant().append(load))
552 0 : return false;
553 :
554 0 : DumpLoadOutcome(load, output_, /* defer = */ true);
555 0 : return true;
556 : }
557 :
558 0 : DumpLoadOutcome(load, output_, /* defer = */ false);
559 0 : return true;
560 : }
561 :
562 : bool
563 0 : FlowAliasAnalysis::processDeferredLoads(LoopInfo* info)
564 : {
565 0 : DumpProcessingDeferredLoads(info->loopHeader());
566 0 : MOZ_ASSERT(loopIsFinished(info->loopHeader()));
567 :
568 0 : for (size_t i = 0; i < info->loopinvariant().length(); i++) {
569 0 : MDefinition* load = info->loopinvariant()[i];
570 :
571 0 : DumpLoad(load);
572 :
573 : // Defer load again when this loop still isn't finished yet.
574 0 : if (!loopIsFinished(load->dependency()->block())) {
575 0 : MOZ_ASSERT(loop_);
576 0 : if (!loop_->loopinvariant().append(load))
577 0 : return false;
578 :
579 0 : DumpLoadOutcome(load, output_, /* defer = */ true);
580 0 : continue;
581 : }
582 :
583 0 : MOZ_ASSERT(load->dependency()->block() == info->loopHeader());
584 0 : MDefinition* store = load->dependency();
585 0 : load->setDependency(nullptr);
586 :
587 : // Test if this load is loop invariant and if it is,
588 : // take the dependencies of non-backedge predecessors of the loop header.
589 : bool loopinvariant;
590 0 : if (!isLoopInvariant(load, store, &loopinvariant))
591 0 : return false;
592 : MDefinitionVector &loopInvariantDependency =
593 0 : stores_->get(store->block()->loopPredecessor());
594 :
595 0 : DumpLoopInvariant(load, info->loopHeader(), /* loopinvariant = */ loopinvariant,
596 0 : loopInvariantDependency);
597 :
598 : // When the store dependencies is empty it means we have a disconnected
599 : // graph. Those blocks will never get reached but it is only fixed up
600 : // after GVN. Don't improve dependency for those loads.
601 0 : if (loopInvariantDependency.length() == 0) {
602 0 : load->setDependency(store);
603 0 : continue;
604 : }
605 :
606 0 : if (loopinvariant) {
607 0 : if (!improveDependency(load, loopInvariantDependency, output_))
608 0 : return false;
609 0 : saveLoadDependency(load, output_);
610 :
611 : // If possible defer when better loop information is present.
612 0 : if (deferImproveDependency(output_)) {
613 0 : if (!loop_->loopinvariant().append(load))
614 0 : return false;
615 :
616 0 : DumpLoadOutcome(load, output_, /* defer = */ true);
617 : } else {
618 0 : DumpLoadOutcome(load, output_, /* defer = */ false);
619 : }
620 :
621 : } else {
622 0 : load->setDependency(store);
623 :
624 : #ifdef JS_JITSPEW
625 0 : output_.clear();
626 0 : if (!output_.append(store))
627 0 : return false;
628 0 : DumpLoadOutcome(load, output_, /* defer = */ false);
629 : #endif
630 : }
631 :
632 : }
633 0 : return true;
634 : }
635 :
636 : // Given a load instruction and an initial store dependency list,
637 : // find the most accurate store dependency list.
638 : bool
639 0 : FlowAliasAnalysis::improveDependency(MDefinition* load, MDefinitionVector& inputStores,
640 : MDefinitionVector& outputStores)
641 : {
642 0 : MOZ_ASSERT(inputStores.length() > 0);
643 0 : outputStores.clear();
644 0 : if (!outputStores.appendAll(inputStores))
645 0 : return false;
646 :
647 0 : bool improved = false;
648 0 : bool adjusted = true;
649 0 : while (adjusted) {
650 0 : adjusted = false;
651 0 : if (!improveNonAliasedStores(load, outputStores, outputStores, &improved))
652 0 : return false;
653 0 : MOZ_ASSERT(outputStores.length() != 0);
654 0 : if (!improveStoresInFinishedLoops(load, outputStores, &adjusted))
655 0 : return false;
656 0 : if (adjusted)
657 0 : improved = true;
658 : }
659 :
660 0 : if (improved)
661 0 : DumpImprovement(load, inputStores, outputStores);
662 :
663 0 : return true;
664 : }
665 :
666 : // For every real store dependencies, follow the chain of stores to find the
667 : // unique set of 'might alias' store dependencies.
668 : bool
669 0 : FlowAliasAnalysis::improveNonAliasedStores(MDefinition* load, MDefinitionVector& inputStores,
670 : MDefinitionVector& outputStores, bool* improved,
671 : bool onlyControlInstructions)
672 : {
673 0 : MOZ_ASSERT(worklist_.length() == 0);
674 0 : if (!AppendToWorklist(worklist_, inputStores))
675 0 : return false;
676 0 : outputStores.clear();
677 :
678 0 : for (size_t i = 0; i < worklist_.length(); i++) {
679 0 : MOZ_ASSERT(worklist_[i]);
680 :
681 0 : if (!LoadAliasesStore(load, worklist_[i])) {
682 0 : StoreDependency* dep = worklist_[i]->storeDependency();
683 0 : MOZ_ASSERT(dep);
684 0 : MOZ_ASSERT(dep->get().length() > 0);
685 :
686 0 : if (!AppendToWorklist(worklist_, dep->get()))
687 0 : return false;
688 :
689 0 : *improved = true;
690 0 : continue;
691 : }
692 :
693 0 : if (onlyControlInstructions && !worklist_[i]->isControlInstruction()) {
694 0 : outputStores.clear();
695 0 : break;
696 : }
697 0 : if (!outputStores.append(worklist_[i]))
698 0 : return false;
699 : }
700 :
701 0 : SetNotInWorkList(worklist_);
702 0 : worklist_.clear();
703 0 : return true;
704 : }
705 :
706 : // Given a load instruction and an initial store dependency list,
707 : // find the most accurate store dependency list with only control instructions.
708 : // Returns an empty output list, when there was a non control instructions
709 : // that couldn't get improved to a control instruction.
710 : bool
711 0 : FlowAliasAnalysis::improveLoopDependency(MDefinition* load, MDefinitionVector& inputStores,
712 : MDefinitionVector& outputStores)
713 : {
714 0 : outputStores.clear();
715 0 : if (!outputStores.appendAll(inputStores))
716 0 : return false;
717 :
718 0 : bool improved = false;
719 0 : bool adjusted = true;
720 0 : while (adjusted) {
721 0 : adjusted = false;
722 0 : if (!improveNonAliasedStores(load, outputStores, outputStores, &improved,
723 : /* onlyControlInstructions = */ true))
724 : {
725 0 : return false;
726 : }
727 0 : if (outputStores.length() == 0)
728 0 : return true;
729 0 : if (!improveStoresInFinishedLoops(load, outputStores, &adjusted))
730 0 : return false;
731 0 : if (adjusted)
732 0 : improved = true;
733 : }
734 :
735 0 : if (improved)
736 0 : DumpImprovement(load, inputStores, outputStores);
737 :
738 0 : return true;
739 : }
740 :
741 : // For every control instruction in the output we find out if the load is loop
742 : // invariant to that loop. When it is, improve the output dependency store,
743 : // by pointing to the stores before the loop.
744 : bool
745 0 : FlowAliasAnalysis::improveStoresInFinishedLoops(MDefinition* load, MDefinitionVector& stores,
746 : bool* improved)
747 : {
748 0 : for (size_t i = 0; i < stores.length(); i++) {
749 0 : if (!stores[i]->isControlInstruction())
750 0 : continue;
751 0 : if (!stores[i]->block()->isLoopHeader())
752 0 : continue;
753 :
754 0 : MOZ_ASSERT(!stores[i]->storeDependency());
755 :
756 0 : if (!loopIsFinished(stores[i]->block()))
757 0 : continue;
758 :
759 0 : if (load->dependency() == stores[i])
760 0 : continue;
761 :
762 : bool loopinvariant;
763 0 : if (!isLoopInvariant(load, stores[i], &loopinvariant))
764 0 : return false;
765 0 : if (!loopinvariant)
766 0 : continue;
767 :
768 0 : MBasicBlock* pred = stores[i]->block()->loopPredecessor();
769 0 : BlockStoreInfo& predInfo = stores_->get(pred);
770 :
771 0 : MOZ_ASSERT(predInfo.length() > 0);
772 0 : stores[i] = predInfo[0];
773 0 : for (size_t j = 1; j < predInfo.length(); j++) {
774 0 : if (!stores.append(predInfo[j]))
775 0 : return false;
776 : }
777 :
778 0 : *improved = true;
779 : }
780 :
781 0 : return true;
782 : }
783 :
784 : bool
785 0 : FlowAliasAnalysis::deferImproveDependency(MDefinitionVector& stores)
786 : {
787 : // Look if the store depends only on 1 non finished loop.
788 : // In that case we will defer until that loop has finished.
789 0 : return loop_ && stores.length() == 1 &&
790 0 : stores[0]->isControlInstruction() &&
791 0 : stores[0]->block()->isLoopHeader() &&
792 0 : !loopIsFinished(stores[0]->block());
793 : }
794 :
795 : void
796 0 : FlowAliasAnalysis::saveLoadDependency(MDefinition* load, MDefinitionVector& dependencies)
797 : {
798 0 : MOZ_ASSERT(dependencies.length() > 0);
799 :
800 : // For now we only save the last store before the load for other passes.
801 : // That means the store with the maximum id.
802 0 : MDefinition* max = dependencies[0];
803 0 : MDefinition* maxNonControl = nullptr;
804 0 : for (size_t i = 0; i < dependencies.length(); i++) {
805 0 : MDefinition* ins = dependencies[i];
806 0 : if (max->id() < ins->id())
807 0 : max = ins;
808 0 : if (!ins->isControlInstruction()) {
809 0 : if (!maxNonControl || maxNonControl->id() < ins->id())
810 0 : maxNonControl = ins;
811 : }
812 : }
813 :
814 : // For loop variant loads with no stores between loopheader and the load,
815 : // the control instruction of the loop header is returned.
816 : // That id is higher than any store inside the loopheader itself.
817 : // Fix for dependency on item in loopheader, but before the "test".
818 : // Which would assume it depends on the loop itself.
819 0 : if (maxNonControl != max && maxNonControl) {
820 0 : if (maxNonControl->block() == max->block())
821 0 : max = maxNonControl;
822 : }
823 :
824 0 : load->setDependency(max);
825 0 : }
826 :
827 : bool
828 0 : FlowAliasAnalysis::saveStoreDependency(MDefinition* ins, BlockStoreInfo& prevStores)
829 : {
830 : // To form a store dependency chain, we store the previous last dependencies
831 : // in the current store.
832 :
833 0 : StoreDependency* dependency = new(alloc().fallible()) StoreDependency(alloc());
834 0 : if (!dependency)
835 0 : return false;
836 0 : if (!dependency->init(prevStores))
837 0 : return false;
838 :
839 0 : ins->setStoreDependency(dependency);
840 0 : return true;
841 : }
842 :
843 : // Returns if loop has been processed
844 : // and has complete backedge stores information.
845 : bool
846 0 : FlowAliasAnalysis::loopIsFinished(MBasicBlock* loopheader)
847 : {
848 0 : MOZ_ASSERT(loopheader->isLoopHeader());
849 :
850 0 : if (!loop_)
851 0 : return true;
852 :
853 0 : return loopheader->backedge()->id() <
854 0 : loop_->loopHeader()->backedge()->id();
855 : }
856 :
857 :
858 : // Determines if a load is loop invariant.
859 : //
860 : // Get the last store dependencies of the backedge of the loop and follow
861 : // the store chain until finding the aliased stores. Make sure the computed
862 : // aliased stores is only the loop control instruction or control instructions
863 : // of loops it is also loop invariant. Only in that case the load is
864 : // definitely loop invariant.
865 : bool
866 0 : FlowAliasAnalysis::isLoopInvariant(MDefinition* load, MDefinition* store, bool* loopinvariant)
867 : {
868 0 : MOZ_ASSERT(store->isControlInstruction());
869 0 : MOZ_ASSERT(!store->storeDependency());
870 0 : MOZ_ASSERT(store->block()->isLoopHeader());
871 0 : MOZ_ASSERT(loopIsFinished(store->block()));
872 :
873 0 : *loopinvariant = false;
874 0 : MBasicBlock* backedge = store->block()->backedge();
875 0 : MDefinitionVector output(alloc());
876 :
877 : // To make sure the improve dependency stops at this loop,
878 : // set the loop control instruction as dependency.
879 0 : MDefinition* olddep = load->dependency();
880 0 : load->setDependency(store);
881 0 : if (!improveLoopDependency(load, stores_->get(backedge), output))
882 0 : return false;
883 0 : load->setDependency(olddep);
884 :
885 0 : if (output.length() == 0)
886 0 : return true;
887 :
888 0 : for (size_t i = 0; i < output.length(); i++) {
889 0 : if (output[i]->storeDependency())
890 0 : return true;
891 :
892 0 : if (!output[i]->isControlInstruction())
893 0 : return true;
894 0 : if (!output[i]->block()->isLoopHeader())
895 0 : return true;
896 :
897 0 : if (output[i] == store)
898 0 : continue;
899 :
900 0 : return true;
901 : }
902 :
903 0 : *loopinvariant = true;
904 0 : return true;
905 : }
906 :
907 : // Compute the store dependencies at the start of this MBasicBlock.
908 : bool
909 0 : FlowAliasAnalysis::computeBlockStores(MBasicBlock* block)
910 : {
911 0 : BlockStoreInfo* blockInfo = stores_->newCurrent(alloc(), block);
912 0 : if (!blockInfo)
913 0 : return false;
914 :
915 : // First and osr block depends on the first instruction.
916 0 : if (block == graph_.entryBlock() || block == graph_.osrBlock()) {
917 0 : MDefinition* firstIns = *block->begin();
918 0 : if (!blockInfo->append(firstIns))
919 0 : return false;
920 0 : return true;
921 : }
922 :
923 : // For loopheaders we take the loopheaders control instruction.
924 : // That is not moveable and easy is to detect.
925 0 : if (block->isLoopHeader()) {
926 0 : if (!blockInfo->append(block->lastIns()))
927 0 : return false;
928 0 : return true;
929 : }
930 :
931 :
932 : // Optimization for consecutive blocks.
933 0 : if (block->numPredecessors() == 1) {
934 0 : MBasicBlock* pred = block->getPredecessor(0);
935 0 : if (pred->numSuccessors() == 1) {
936 0 : stores_->swap(block, pred);
937 0 : return true;
938 : }
939 0 : MOZ_ASSERT (pred->numSuccessors() > 1);
940 0 : BlockStoreInfo& predInfo = stores_->get(pred);
941 0 : return blockInfo->appendAll(predInfo);
942 : }
943 :
944 : // Heuristic: in most cases having more than 5 predecessors,
945 : // increases the number of dependencies too much to still be able
946 : // to do an optimization. Therefore don't do the merge work.
947 : // For simplicity we take an non-dominant always existing instruction.
948 : // That way we cannot accidentally move instructions depending on it.
949 0 : if (block->numPredecessors() > 5) {
950 0 : if (!blockInfo->append(block->getPredecessor(0)->lastIns()))
951 0 : return false;
952 0 : return true;
953 : }
954 :
955 : // Merging of multiple predecessors.
956 0 : for (size_t pred = 0; pred < block->numPredecessors(); pred++) {
957 0 : BlockStoreInfo& predInfo = stores_->get(block->getPredecessor(pred));
958 0 : if (!AppendToWorklist(*blockInfo, predInfo))
959 0 : return false;
960 : }
961 0 : SetNotInWorkList(*blockInfo);
962 :
963 0 : return true;
964 : }
|
