1// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/compiler/backend/loops.h"
6
7#include "vm/bit_vector.h"
8#include "vm/compiler/backend/il.h"
9
10namespace dart {
11
12// Private class to perform induction variable analysis on a single loop
13// or a full loop hierarchy. The analysis implementation is based on the
14// paper by M. Gerlek et al. "Beyond Induction Variables: Detecting and
15// Classifying Sequences Using a Demand-Driven SSA Form" (ACM Transactions
16// on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995).
17//
18// The algorithm discovers and classifies definitions within loops that
19// behave like induction variables, and attaches an InductionVar record
20// to it (this mapping is stored in the loop data structure). The algorithm
21// first finds strongly connected components in the flow graph and classifies
22// each component as an induction when possible. Due to the descendant-first
23// nature, classification happens "on-demand" (e.g. basic induction is
24// classified before derived induction).
25class InductionVarAnalysis : public ValueObject {
26 public:
27 // Constructor to set up analysis phase.
28 explicit InductionVarAnalysis(const GrowableArray<BlockEntryInstr*>& preorder)
29 : preorder_(preorder),
30 stack_(),
31 scc_(),
32 cycle_(),
33 map_(),
34 current_index_(0),
35 zone_(Thread::Current()->zone()) {}
36
37 // Detects induction variables on the full loop hierarchy.
38 void VisitHierarchy(LoopInfo* loop);
39
40 // Detects induction variables on a single loop.
41 void VisitLoop(LoopInfo* loop);
42
43 private:
44 // An information node needed during SCC traversal that can
45 // reside in a map without any explicit memory allocation.
46 struct SCCInfo {
47 SCCInfo() : depth(-1), done(false) {}
48 explicit SCCInfo(intptr_t d) : depth(d), done(false) {}
49 intptr_t depth;
50 bool done;
51 bool operator!=(const SCCInfo& other) const {
52 return depth != other.depth || done != other.done;
53 }
54 bool operator==(const SCCInfo& other) const {
55 return depth == other.depth && done == other.done;
56 }
57 };
58 typedef RawPointerKeyValueTrait<Definition, SCCInfo> VisitKV;
59
60 // Traversal methods.
61 bool Visit(LoopInfo* loop, Definition* def);
62 intptr_t VisitDescendant(LoopInfo* loop, Definition* def);
63 void Classify(LoopInfo* loop, Definition* def);
64 void ClassifySCC(LoopInfo* loop);
65 void ClassifyControl(LoopInfo* loop);
66
67 // Transfer methods. Compute how induction of the operands, if any,
68 // tranfers over the operation performed by the given definition.
69 InductionVar* TransferPhi(LoopInfo* loop, Definition* def, intptr_t idx = -1);
70 InductionVar* TransferDef(LoopInfo* loop, Definition* def);
71 InductionVar* TransferBinary(LoopInfo* loop, Definition* def);
72 InductionVar* TransferUnary(LoopInfo* loop, Definition* def);
73
74 // Solver methods. Compute how temporary meaning given to the
75 // definitions in a cycle transfer over the operation performed
76 // by the given definition.
77 InductionVar* SolvePhi(LoopInfo* loop, Definition* def, intptr_t idx = -1);
78 InductionVar* SolveConstraint(LoopInfo* loop,
79 Definition* def,
80 InductionVar* init);
81 InductionVar* SolveBinary(LoopInfo* loop,
82 Definition* def,
83 InductionVar* init);
84 InductionVar* SolveUnary(LoopInfo* loop, Definition* def, InductionVar* init);
85
86 // Lookup.
87 InductionVar* Lookup(LoopInfo* loop, Definition* def);
88 InductionVar* LookupCycle(Definition* def);
89
90 // Arithmetic.
91 InductionVar* Add(InductionVar* x, InductionVar* y);
92 InductionVar* Sub(InductionVar* x, InductionVar* y);
93 InductionVar* Mul(InductionVar* x, InductionVar* y);
94
95 // Bookkeeping data (released when analysis goes out of scope).
96 const GrowableArray<BlockEntryInstr*>& preorder_;
97 GrowableArray<Definition*> stack_;
98 GrowableArray<Definition*> scc_;
99 GrowableArray<BranchInstr*> branches_;
100 DirectChainedHashMap<LoopInfo::InductionKV> cycle_;
101 DirectChainedHashMap<VisitKV> map_;
102 intptr_t current_index_;
103 Zone* zone_;
104
105 DISALLOW_COPY_AND_ASSIGN(InductionVarAnalysis);
106};
107
108// Helper method that finds phi-index of the initial value
109// that comes from a block outside the loop. Note that the
110// algorithm still works if there are several of these.
111static intptr_t InitIndex(LoopInfo* loop) {
112 BlockEntryInstr* header = loop->header();
113 for (intptr_t i = 0; i < header->PredecessorCount(); ++i) {
114 if (!loop->Contains(header->PredecessorAt(i))) { // pick first
115 return i;
116 }
117 }
118 UNREACHABLE();
119 return -1;
120}
121
122// Helper method that determines if a definition is a constant.
123static bool IsConstant(Definition* def, int64_t* val) {
124 if (def->IsConstant()) {
125 const Object& value = def->AsConstant()->value();
126 if (value.IsInteger()) {
127 *val = Integer::Cast(value).AsInt64Value(); // smi and mint
128 return true;
129 }
130 }
131 return false;
132}
133
134// Helper method to determine if a non-strict (inclusive) bound on
135// a unit stride linear induction can be made strict (exclusive)
136// without arithmetic wrap-around complications.
137static bool CanBeMadeExclusive(LoopInfo* loop,
138 InductionVar* x,
139 Instruction* branch,
140 bool is_lower) {
141 InductionVar* min = nullptr;
142 InductionVar* max = nullptr;
143 if (x->CanComputeBounds(loop, branch, &min, &max)) {
144 int64_t end = 0;
145 if (is_lower) {
146 if (InductionVar::IsConstant(min, &end)) {
147 return kMinInt64 < end;
148 }
149 } else if (InductionVar::IsConstant(max, &end)) {
150 return end < kMaxInt64;
151 } else if (InductionVar::IsInvariant(max) && max->mult() == 1 &&
152 Definition::IsArrayLength(max->def())) {
153 return max->offset() < 0; // a.length - C, C > 0
154 }
155 }
156 return false;
157}
158
159// Helper method to adjust a range [lower_bound,upper_bound] into the
160// range [lower_bound+lower_bound_offset,upper_bound+upper_bound+offset]
161// without arithmetic wrap-around complications. On entry, we know that
162// lower_bound <= upper_bound is enforced by an actual comparison in the
163// code (so that even if lower_bound > upper_bound, the loop is not taken).
164// This method ensures the resulting range has the same property by
165// very conservatively testing if everything stays between constants
166// or a properly offset array length.
167static bool SafelyAdjust(Zone* zone,
168 InductionVar* lower_bound,
169 int64_t lower_bound_offset,
170 InductionVar* upper_bound,
171 int64_t upper_bound_offset,
172 InductionVar** min,
173 InductionVar** max) {
174 bool success = false;
175 int64_t lval = 0;
176 int64_t uval = 0;
177 if (InductionVar::IsConstant(lower_bound, &lval)) {
178 const int64_t l = lval + lower_bound_offset;
179 if (InductionVar::IsConstant(upper_bound, &uval)) {
180 // Make sure a proper new range [l,u] results. Even if bounds
181 // were subject to arithmetic wrap-around, we preserve the
182 // property that the minimum is in l and the maximum in u.
183 const int64_t u = uval + upper_bound_offset;
184 success = (l <= u);
185 } else if (InductionVar::IsInvariant(upper_bound) &&
186 upper_bound->mult() == 1 &&
187 Definition::IsArrayLength(upper_bound->def())) {
188 // No arithmetic wrap-around on the lower bound, and a properly
189 // non-positive offset on an array length, which is always >= 0.
190 const int64_t c = upper_bound->offset() + upper_bound_offset;
191 success = ((lower_bound_offset >= 0 && lval <= l) ||
192 (lower_bound_offset < 0 && lval > l)) &&
193 (c <= 0);
194 }
195 }
196 if (success) {
197 *min = (lower_bound_offset == 0)
198 ? lower_bound
199 : new (zone) InductionVar(lval + lower_bound_offset);
200 *max = (upper_bound_offset == 0)
201 ? upper_bound
202 : new (zone)
203 InductionVar(upper_bound->offset() + upper_bound_offset,
204 upper_bound->mult(), upper_bound->def());
205 }
206 return success;
207}
208
209void InductionVarAnalysis::VisitHierarchy(LoopInfo* loop) {
210 for (; loop != nullptr; loop = loop->next_) {
211 VisitLoop(loop);
212 VisitHierarchy(loop->inner_);
213 }
214}
215
216void InductionVarAnalysis::VisitLoop(LoopInfo* loop) {
217 loop->ResetInduction();
218 // Find strongly connected components (SSCs) in the SSA graph of this
219 // loop using Tarjan's algorithm. Due to the descendant-first nature,
220 // classification happens "on-demand".
221 current_index_ = 0;
222 ASSERT(stack_.is_empty());
223 ASSERT(map_.IsEmpty());
224 ASSERT(branches_.is_empty());
225 for (BitVector::Iterator it(loop->blocks_); !it.Done(); it.Advance()) {
226 BlockEntryInstr* block = preorder_[it.Current()];
227 ASSERT(block->loop_info() != nullptr);
228 if (block->loop_info() != loop) {
229 continue; // inner loop
230 }
231 // Visit phi-operations.
232 if (block->IsJoinEntry()) {
233 for (PhiIterator it(block->AsJoinEntry()); !it.Done(); it.Advance()) {
234 Visit(loop, it.Current());
235 }
236 }
237 // Visit instructions and collect branches.
238 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
239 Instruction* instruction = it.Current();
240 Visit(loop, instruction->AsDefinition());
241 if (instruction->IsBranch()) {
242 branches_.Add(instruction->AsBranch());
243 }
244 }
245 }
246 ASSERT(stack_.is_empty());
247 map_.Clear();
248 // Classify loop control.
249 ClassifyControl(loop);
250 branches_.Clear();
251}
252
253bool InductionVarAnalysis::Visit(LoopInfo* loop, Definition* def) {
254 if (def == nullptr || map_.HasKey(def)) {
255 return false; // no def, or already visited
256 }
257 intptr_t d = ++current_index_;
258 map_.Insert(VisitKV::Pair(def, SCCInfo(d)));
259 stack_.Add(def);
260
261 // Visit all descendants.
262 intptr_t low = d;
263 for (intptr_t i = 0, n = def->InputCount(); i < n; i++) {
264 Value* input = def->InputAt(i);
265 if (input != nullptr) {
266 low = Utils::Minimum(low, VisitDescendant(loop, input->definition()));
267 }
268 }
269
270 // Lower or found SCC?
271 if (low < d) {
272 map_.Lookup(def)->value.depth = low;
273 } else {
274 // Pop the stack to build the SCC for classification.
275 ASSERT(scc_.is_empty());
276 while (!stack_.is_empty()) {
277 Definition* top = stack_.RemoveLast();
278 scc_.Add(top);
279 map_.Lookup(top)->value.done = true;
280 if (top == def) {
281 break;
282 }
283 }
284 // Classify.
285 if (scc_.length() == 1) {
286 Classify(loop, scc_[0]);
287 } else {
288 ASSERT(scc_.length() > 1);
289 ASSERT(cycle_.IsEmpty());
290 ClassifySCC(loop);
291 cycle_.Clear();
292 }
293 scc_.Clear();
294 }
295 return true;
296}
297
298intptr_t InductionVarAnalysis::VisitDescendant(LoopInfo* loop,
299 Definition* def) {
300 // The traversal stops at anything not defined in this loop
301 // (either a loop invariant entry value defined outside the
302 // loop or an inner exit value defined by an inner loop).
303 if (def->GetBlock()->loop_info() != loop) {
304 return current_index_;
305 }
306 // Inspect descendant node.
307 if (!Visit(loop, def) && map_.Lookup(def)->value.done) {
308 return current_index_;
309 }
310 return map_.Lookup(def)->value.depth;
311}
312
313void InductionVarAnalysis::Classify(LoopInfo* loop, Definition* def) {
314 // Classify different kind of instructions.
315 InductionVar* induc = nullptr;
316 if (loop->IsHeaderPhi(def)) {
317 intptr_t idx = InitIndex(loop);
318 induc = TransferPhi(loop, def, idx);
319 if (induc != nullptr) {
320 InductionVar* init = Lookup(loop, def->InputAt(idx)->definition());
321 // Wrap-around (except for unusual header phi(x,..,x) = x).
322 if (!init->IsEqual(induc)) {
323 induc =
324 new (zone_) InductionVar(InductionVar::kWrapAround, init, induc);
325 }
326 }
327 } else if (def->IsPhi()) {
328 induc = TransferPhi(loop, def);
329 } else {
330 induc = TransferDef(loop, def);
331 }
332 // Successfully classified?
333 if (induc != nullptr) {
334 loop->AddInduction(def, induc);
335 }
336}
337
338void InductionVarAnalysis::ClassifySCC(LoopInfo* loop) {
339 intptr_t size = scc_.length();
340 // Find a header phi, usually at the end.
341 intptr_t p = -1;
342 for (intptr_t i = size - 1; i >= 0; i--) {
343 if (loop->IsHeaderPhi(scc_[i])) {
344 p = i;
345 break;
346 }
347 }
348 // Rotate header phi up front.
349 if (p >= 0) {
350 Definition* phi = scc_[p];
351 intptr_t idx = InitIndex(loop);
352 InductionVar* init = Lookup(loop, phi->InputAt(idx)->definition());
353 // Inspect remainder of the cycle. The cycle mapping assigns temporary
354 // meaning to instructions, seeded from the phi instruction and back.
355 // The init of the phi is passed as marker token to detect first use.
356 cycle_.Insert(LoopInfo::InductionKV::Pair(phi, init));
357 for (intptr_t i = 1, j = p; i < size; i++) {
358 if (++j >= size) j = 0;
359 Definition* def = scc_[j];
360 InductionVar* update = nullptr;
361 if (def->IsPhi()) {
362 update = SolvePhi(loop, def);
363 } else if (def->IsBinaryIntegerOp()) {
364 update = SolveBinary(loop, def, init);
365 } else if (def->IsUnaryIntegerOp()) {
366 update = SolveUnary(loop, def, init);
367 } else if (def->IsConstraint()) {
368 update = SolveConstraint(loop, def, init);
369 } else {
370 Definition* orig = def->OriginalDefinitionIgnoreBoxingAndConstraints();
371 if (orig != def) {
372 update = LookupCycle(orig); // pass-through
373 }
374 }
375 // Continue cycle?
376 if (update == nullptr) {
377 return;
378 }
379 cycle_.Insert(LoopInfo::InductionKV::Pair(def, update));
380 }
381 // Success if all internal links (inputs to the phi that are along
382 // back-edges) received the same temporary meaning. The external
383 // link (initial value coming from outside the loop) is excluded
384 // while taking this join.
385 InductionVar* induc = SolvePhi(loop, phi, idx);
386 if (induc != nullptr) {
387 // Invariant means linear induction.
388 if (induc->kind_ == InductionVar::kInvariant) {
389 induc = new (zone_) InductionVar(InductionVar::kLinear, init, induc);
390 } else {
391 ASSERT(induc->kind_ == InductionVar::kPeriodic);
392 }
393 // Classify first phi and then the rest of the cycle "on-demand".
394 loop->AddInduction(phi, induc);
395 for (intptr_t i = 1, j = p; i < size; i++) {
396 if (++j >= size) j = 0;
397 Classify(loop, scc_[j]);
398 }
399 }
400 }
401}
402
403void InductionVarAnalysis::ClassifyControl(LoopInfo* loop) {
404 for (auto branch : branches_) {
405 // Proper comparison?
406 ComparisonInstr* compare = branch->comparison();
407 if (compare->InputCount() != 2) {
408 continue;
409 }
410 Token::Kind cmp = compare->kind();
411 // Proper loop exit? Express the condition in "loop while true" form.
412 TargetEntryInstr* ift = branch->true_successor();
413 TargetEntryInstr* iff = branch->false_successor();
414 if (loop->Contains(ift) && !loop->Contains(iff)) {
415 // ok as is
416 } else if (!loop->Contains(ift) && loop->Contains(iff)) {
417 cmp = Token::NegateComparison(cmp);
418 } else {
419 continue;
420 }
421 // Comparison against linear constant stride induction?
422 // Express the comparison such that induction appears left.
423 int64_t stride = 0;
424 auto left = compare->left()
425 ->definition()
426 ->OriginalDefinitionIgnoreBoxingAndConstraints();
427 auto right = compare->right()
428 ->definition()
429 ->OriginalDefinitionIgnoreBoxingAndConstraints();
430 InductionVar* x = Lookup(loop, left);
431 InductionVar* y = Lookup(loop, right);
432 if (InductionVar::IsLinear(x, &stride) && InductionVar::IsInvariant(y)) {
433 // ok as is
434 } else if (InductionVar::IsInvariant(x) &&
435 InductionVar::IsLinear(y, &stride)) {
436 InductionVar* tmp = x;
437 x = y;
438 y = tmp;
439 cmp = Token::FlipComparison(cmp);
440 } else {
441 continue;
442 }
443 // Can we find a strict (exclusive) comparison for the looping condition?
444 // Note that we reject symbolic bounds in non-strict (inclusive) looping
445 // conditions like i <= U as upperbound or i >= L as lowerbound since this
446 // could loop forever when U is kMaxInt64 or L is kMinInt64 under Dart's
447 // 64-bit arithmetic wrap-around. Non-unit strides could overshoot the
448 // bound due to aritmetic wrap-around.
449 switch (cmp) {
450 case Token::kLT:
451 // Accept i < U (i++).
452 if (stride == 1) break;
453 continue;
454 case Token::kGT:
455 // Accept i > L (i--).
456 if (stride == -1) break;
457 continue;
458 case Token::kLTE: {
459 // Accept i <= U (i++) as i < U + 1
460 // only when U != MaxInt is certain.
461 if (stride == 1 &&
462 CanBeMadeExclusive(loop, y, branch, /*is_lower=*/false)) {
463 y = Add(y, new (zone_) InductionVar(1));
464 break;
465 }
466 continue;
467 }
468 case Token::kGTE: {
469 // Accept i >= L (i--) as i > L - 1
470 // only when L != MinInt is certain.
471 if (stride == -1 &&
472 CanBeMadeExclusive(loop, y, branch, /*is_lower=*/true)) {
473 y = Sub(y, new (zone_) InductionVar(1));
474 break;
475 }
476 continue;
477 }
478 case Token::kNE: {
479 // Accept i != E as either i < E (i++) or i > E (i--)
480 // for constants bounds that make the loop always-taken.
481 int64_t start = 0;
482 int64_t end = 0;
483 if (InductionVar::IsConstant(x->initial_, &start) &&
484 InductionVar::IsConstant(y, &end)) {
485 if ((stride == +1 && start < end) || (stride == -1 && start > end)) {
486 break;
487 }
488 }
489 continue;
490 }
491 default:
492 continue;
493 }
494 // We found a strict upper or lower bound on a unit stride linear
495 // induction. Note that depending on the intended use of this
496 // information, clients should still test dominance on the test
497 // and the initial value of the induction variable.
498 x->bounds_.Add(InductionVar::Bound(branch, y));
499 // Record control induction.
500 if (branch == loop->header_->last_instruction()) {
501 loop->control_ = x;
502 }
503 }
504}
505
506InductionVar* InductionVarAnalysis::TransferPhi(LoopInfo* loop,
507 Definition* def,
508 intptr_t idx) {
509 InductionVar* induc = nullptr;
510 for (intptr_t i = 0, n = def->InputCount(); i < n; i++) {
511 if (i != idx) {
512 InductionVar* x = Lookup(loop, def->InputAt(i)->definition());
513 if (x == nullptr) {
514 return nullptr;
515 } else if (induc == nullptr) {
516 induc = x;
517 } else if (!induc->IsEqual(x)) {
518 return nullptr;
519 }
520 }
521 }
522 return induc;
523}
524
525InductionVar* InductionVarAnalysis::TransferDef(LoopInfo* loop,
526 Definition* def) {
527 if (def->IsBinaryIntegerOp()) {
528 return TransferBinary(loop, def);
529 } else if (def->IsUnaryIntegerOp()) {
530 return TransferUnary(loop, def);
531 } else {
532 // Note that induction analysis does not really need the second
533 // argument of a bound check, since it will just pass-through the
534 // index. However, we do a lookup on the, most likely loop-invariant,
535 // length anyway, to make sure it is stored in the induction
536 // environment for later lookup during BCE.
537 if (auto check = def->AsCheckBoundBase()) {
538 Definition* len = check->length()
539 ->definition()
540 ->OriginalDefinitionIgnoreBoxingAndConstraints();
541 Lookup(loop, len); // pre-store likely invariant length
542 }
543 // Proceed with regular pass-through.
544 Definition* orig = def->OriginalDefinitionIgnoreBoxingAndConstraints();
545 if (orig != def) {
546 return Lookup(loop, orig); // pass-through
547 }
548 }
549 return nullptr;
550}
551
552InductionVar* InductionVarAnalysis::TransferBinary(LoopInfo* loop,
553 Definition* def) {
554 InductionVar* x = Lookup(loop, def->InputAt(0)->definition());
555 InductionVar* y = Lookup(loop, def->InputAt(1)->definition());
556
557 switch (def->AsBinaryIntegerOp()->op_kind()) {
558 case Token::kADD:
559 return Add(x, y);
560 case Token::kSUB:
561 return Sub(x, y);
562 case Token::kMUL:
563 return Mul(x, y);
564 default:
565 return nullptr;
566 }
567}
568
569InductionVar* InductionVarAnalysis::TransferUnary(LoopInfo* loop,
570 Definition* def) {
571 InductionVar* x = Lookup(loop, def->InputAt(0)->definition());
572 switch (def->AsUnaryIntegerOp()->op_kind()) {
573 case Token::kNEGATE: {
574 InductionVar* zero = new (zone_) InductionVar(0);
575 return Sub(zero, x);
576 }
577 default:
578 return nullptr;
579 }
580}
581
582InductionVar* InductionVarAnalysis::SolvePhi(LoopInfo* loop,
583 Definition* def,
584 intptr_t idx) {
585 InductionVar* induc = nullptr;
586 for (intptr_t i = 0, n = def->InputCount(); i < n; i++) {
587 if (i != idx) {
588 InductionVar* c = LookupCycle(def->InputAt(i)->definition());
589 if (c == nullptr) {
590 return nullptr;
591 } else if (induc == nullptr) {
592 induc = c;
593 } else if (!induc->IsEqual(c)) {
594 return nullptr;
595 }
596 }
597 }
598 return induc;
599}
600
601InductionVar* InductionVarAnalysis::SolveConstraint(LoopInfo* loop,
602 Definition* def,
603 InductionVar* init) {
604 InductionVar* c = LookupCycle(def->InputAt(0)->definition());
605 if (c == init) {
606 // Record a non-artifical bound constraint on a phi.
607 ConstraintInstr* constraint = def->AsConstraint();
608 if (constraint->target() != nullptr) {
609 loop->limit_ = constraint;
610 }
611 }
612 return c;
613}
614
615InductionVar* InductionVarAnalysis::SolveBinary(LoopInfo* loop,
616 Definition* def,
617 InductionVar* init) {
618 InductionVar* x = Lookup(loop, def->InputAt(0)->definition());
619 InductionVar* y = Lookup(loop, def->InputAt(1)->definition());
620 switch (def->AsBinaryIntegerOp()->op_kind()) {
621 case Token::kADD:
622 if (InductionVar::IsInvariant(x)) {
623 InductionVar* c = LookupCycle(def->InputAt(1)->definition());
624 // The init marker denotes first use, otherwise aggregate.
625 if (c == init) {
626 return x;
627 } else if (InductionVar::IsInvariant(c)) {
628 return Add(x, c);
629 }
630 }
631 if (InductionVar::IsInvariant(y)) {
632 InductionVar* c = LookupCycle(def->InputAt(0)->definition());
633 // The init marker denotes first use, otherwise aggregate.
634 if (c == init) {
635 return y;
636 } else if (InductionVar::IsInvariant(c)) {
637 return Add(c, y);
638 }
639 }
640 return nullptr;
641 case Token::kSUB:
642 if (InductionVar::IsInvariant(x)) {
643 InductionVar* c = LookupCycle(def->InputAt(1)->definition());
644 // Note that i = x - i is periodic. The temporary
645 // meaning is expressed in terms of the header phi.
646 if (c == init) {
647 InductionVar* next = Sub(x, init);
648 if (InductionVar::IsInvariant(next)) {
649 return new (zone_)
650 InductionVar(InductionVar::kPeriodic, init, next);
651 }
652 }
653 }
654 if (InductionVar::IsInvariant(y)) {
655 InductionVar* c = LookupCycle(def->InputAt(0)->definition());
656 // The init marker denotes first use, otherwise aggregate.
657 if (c == init) {
658 InductionVar* zero = new (zone_) InductionVar(0);
659 return Sub(zero, y);
660 } else if (InductionVar::IsInvariant(c)) {
661 return Sub(c, y);
662 }
663 }
664 return nullptr;
665 default:
666 return nullptr;
667 }
668}
669
670InductionVar* InductionVarAnalysis::SolveUnary(LoopInfo* loop,
671 Definition* def,
672 InductionVar* init) {
673 InductionVar* c = LookupCycle(def->InputAt(0)->definition());
674 switch (def->AsUnaryIntegerOp()->op_kind()) {
675 case Token::kNEGATE:
676 // Note that i = - i is periodic. The temporary
677 // meaning is expressed in terms of the header phi.
678 if (c == init) {
679 InductionVar* zero = new (zone_) InductionVar(0);
680 InductionVar* next = Sub(zero, init);
681 if (InductionVar::IsInvariant(next)) {
682 return new (zone_) InductionVar(InductionVar::kPeriodic, init, next);
683 }
684 }
685 return nullptr;
686 default:
687 return nullptr;
688 }
689}
690
691InductionVar* InductionVarAnalysis::Lookup(LoopInfo* loop, Definition* def) {
692 InductionVar* induc = loop->LookupInduction(def);
693 if (induc == nullptr) {
694 // Loop-invariants are added lazily.
695 int64_t val = 0;
696 if (IsConstant(def, &val)) {
697 induc = new (zone_) InductionVar(val);
698 loop->AddInduction(def, induc);
699 } else if (!loop->Contains(def->GetBlock())) {
700 // Look "under the hood" of invariant definitions to expose
701 // more details on common constructs like "length - 1".
702 induc = TransferDef(loop, def);
703 if (induc == nullptr) {
704 induc = new (zone_) InductionVar(0, 1, def);
705 }
706 loop->AddInduction(def, induc);
707 }
708 }
709 return induc;
710}
711
712InductionVar* InductionVarAnalysis::LookupCycle(Definition* def) {
713 LoopInfo::InductionKV::Pair* pair = cycle_.Lookup(def);
714 if (pair != nullptr) {
715 return pair->value;
716 }
717 return nullptr;
718}
719
720InductionVar* InductionVarAnalysis::Add(InductionVar* x, InductionVar* y) {
721 if (InductionVar::IsInvariant(x)) {
722 if (InductionVar::IsInvariant(y)) {
723 // Invariant + Invariant : only for same or just one instruction.
724 if (x->def_ == y->def_) {
725 return new (zone_)
726 InductionVar(x->offset_ + y->offset_, x->mult_ + y->mult_, x->def_);
727 } else if (y->mult_ == 0) {
728 return new (zone_)
729 InductionVar(x->offset_ + y->offset_, x->mult_, x->def_);
730 } else if (x->mult_ == 0) {
731 return new (zone_)
732 InductionVar(x->offset_ + y->offset_, y->mult_, y->def_);
733 }
734 } else if (y != nullptr) {
735 // Invariant + Induction.
736 InductionVar* i = Add(x, y->initial_);
737 InductionVar* n =
738 y->kind_ == InductionVar::kLinear ? y->next_ : Add(x, y->next_);
739 if (i != nullptr && n != nullptr) {
740 return new (zone_) InductionVar(y->kind_, i, n);
741 }
742 }
743 } else if (InductionVar::IsInvariant(y)) {
744 if (x != nullptr) {
745 // Induction + Invariant.
746 ASSERT(!InductionVar::IsInvariant(x));
747 InductionVar* i = Add(x->initial_, y);
748 InductionVar* n =
749 x->kind_ == InductionVar::kLinear ? x->next_ : Add(x->next_, y);
750 if (i != nullptr && n != nullptr) {
751 return new (zone_) InductionVar(x->kind_, i, n);
752 }
753 }
754 } else if (InductionVar::IsLinear(x) && InductionVar::IsLinear(y)) {
755 // Linear + Linear.
756 InductionVar* i = Add(x->initial_, y->initial_);
757 InductionVar* n = Add(x->next_, y->next_);
758 if (i != nullptr && n != nullptr) {
759 return new (zone_) InductionVar(InductionVar::kLinear, i, n);
760 }
761 }
762 return nullptr;
763}
764
765InductionVar* InductionVarAnalysis::Sub(InductionVar* x, InductionVar* y) {
766 if (InductionVar::IsInvariant(x)) {
767 if (InductionVar::IsInvariant(y)) {
768 // Invariant + Invariant : only for same or just one instruction.
769 if (x->def_ == y->def_) {
770 return new (zone_)
771 InductionVar(x->offset_ - y->offset_, x->mult_ - y->mult_, x->def_);
772 } else if (y->mult_ == 0) {
773 return new (zone_)
774 InductionVar(x->offset_ - y->offset_, x->mult_, x->def_);
775 } else if (x->mult_ == 0) {
776 return new (zone_)
777 InductionVar(x->offset_ - y->offset_, -y->mult_, y->def_);
778 }
779 } else if (y != nullptr) {
780 // Invariant - Induction.
781 InductionVar* i = Sub(x, y->initial_);
782 InductionVar* n;
783 if (y->kind_ == InductionVar::kLinear) {
784 InductionVar* zero = new (zone_) InductionVar(0, 0, nullptr);
785 n = Sub(zero, y->next_);
786 } else {
787 n = Sub(x, y->next_);
788 }
789 if (i != nullptr && n != nullptr) {
790 return new (zone_) InductionVar(y->kind_, i, n);
791 }
792 }
793 } else if (InductionVar::IsInvariant(y)) {
794 if (x != nullptr) {
795 // Induction - Invariant.
796 ASSERT(!InductionVar::IsInvariant(x));
797 InductionVar* i = Sub(x->initial_, y);
798 InductionVar* n =
799 x->kind_ == InductionVar::kLinear ? x->next_ : Sub(x->next_, y);
800 if (i != nullptr && n != nullptr) {
801 return new (zone_) InductionVar(x->kind_, i, n);
802 }
803 }
804 } else if (InductionVar::IsLinear(x) && InductionVar::IsLinear(y)) {
805 // Linear - Linear.
806 InductionVar* i = Sub(x->initial_, y->initial_);
807 InductionVar* n = Sub(x->next_, y->next_);
808 if (i != nullptr && n != nullptr) {
809 return new (zone_) InductionVar(InductionVar::kLinear, i, n);
810 }
811 }
812 return nullptr;
813}
814
815InductionVar* InductionVarAnalysis::Mul(InductionVar* x, InductionVar* y) {
816 // Swap constant left.
817 if (!InductionVar::IsConstant(x)) {
818 InductionVar* tmp = x;
819 x = y;
820 y = tmp;
821 }
822 // Apply constant to any induction.
823 if (InductionVar::IsConstant(x) && y != nullptr) {
824 if (y->kind_ == InductionVar::kInvariant) {
825 return new (zone_)
826 InductionVar(x->offset_ * y->offset_, x->offset_ * y->mult_, y->def_);
827 }
828 return new (zone_)
829 InductionVar(y->kind_, Mul(x, y->initial_), Mul(x, y->next_));
830 }
831 return nullptr;
832}
833
834bool InductionVar::CanComputeDifferenceWith(const InductionVar* other,
835 int64_t* diff) const {
836 if (IsInvariant(this) && IsInvariant(other)) {
837 if (def_ == other->def_ && mult_ == other->mult_) {
838 *diff = other->offset_ - offset_;
839 return true;
840 }
841 } else if (IsLinear(this) && IsLinear(other)) {
842 return next_->IsEqual(other->next_) &&
843 initial_->CanComputeDifferenceWith(other->initial_, diff);
844 }
845 // TODO(ajcbik): examine other induction kinds too?
846 return false;
847}
848
849bool InductionVar::CanComputeBoundsImpl(LoopInfo* loop,
850 Instruction* pos,
851 InductionVar** min,
852 InductionVar** max) {
853 // Refine symbolic part of an invariant with outward induction.
854 if (IsInvariant(this)) {
855 if (mult_ == 1 && def_ != nullptr) {
856 for (loop = loop->outer(); loop != nullptr; loop = loop->outer()) {
857 InductionVar* induc = loop->LookupInduction(def_);
858 InductionVar* i_min = nullptr;
859 InductionVar* i_max = nullptr;
860 // Accept i+C with i in [L,U] as [L+C,U+C] when this adjustment
861 // does not have arithmetic wrap-around complications.
862 if (IsInduction(induc) &&
863 induc->CanComputeBounds(loop, pos, &i_min, &i_max)) {
864 Zone* z = Thread::Current()->zone();
865 return SafelyAdjust(z, i_min, offset_, i_max, offset_, min, max);
866 }
867 }
868 }
869 // Otherwise invariant itself suffices.
870 *min = *max = this;
871 return true;
872 }
873 // Refine unit stride induction with lower and upper bound.
874 // for (int i = L; i < U; i++)
875 // j = i+C in [L+C,U+C-1]
876 int64_t stride = 0;
877 int64_t off = 0;
878 if (IsLinear(this, &stride) && Utils::Abs(stride) == 1 &&
879 CanComputeDifferenceWith(loop->control(), &off)) {
880 // Find ranges on both L and U first (and not just minimum
881 // of L and maximum of U) to avoid arithmetic wrap-around
882 // complications such as the one shown below.
883 // for (int i = 0; i < maxint - 10; i++)
884 // for (int j = i + 20; j < 100; j++)
885 // j in [minint, 99] and not in [20, 100]
886 InductionVar* l_min = nullptr;
887 InductionVar* l_max = nullptr;
888 if (initial_->CanComputeBounds(loop, pos, &l_min, &l_max)) {
889 // Find extreme using a control bound for which the branch dominates
890 // the given position (to make sure it really is under its control).
891 // Then refine with anything that dominates that branch.
892 for (auto bound : loop->control()->bounds()) {
893 if (pos->IsDominatedBy(bound.branch_)) {
894 InductionVar* u_min = nullptr;
895 InductionVar* u_max = nullptr;
896 if (bound.limit_->CanComputeBounds(loop, bound.branch_, &u_min,
897 &u_max)) {
898 Zone* z = Thread::Current()->zone();
899 return stride > 0 ? SafelyAdjust(z, l_min, 0, u_max, -stride - off,
900 min, max)
901 : SafelyAdjust(z, u_min, -stride - off, l_max, 0,
902 min, max);
903 }
904 }
905 }
906 }
907 }
908 // Failure. TODO(ajcbik): examine other kinds of induction too?
909 return false;
910}
911
912// Driver method to compute bounds with per-loop memoization.
913bool InductionVar::CanComputeBounds(LoopInfo* loop,
914 Instruction* pos,
915 InductionVar** min,
916 InductionVar** max) {
917 // Consult cache first.
918 LoopInfo::MemoKV::Pair* pair1 = loop->memo_cache_.Lookup(this);
919 if (pair1 != nullptr) {
920 LoopInfo::MemoVal::PosKV::Pair* pair2 = pair1->value->memo_.Lookup(pos);
921 if (pair2 != nullptr) {
922 *min = pair2->value.first;
923 *max = pair2->value.second;
924 return true;
925 }
926 }
927 // Compute and cache.
928 if (CanComputeBoundsImpl(loop, pos, min, max)) {
929 ASSERT(*min != nullptr && *max != nullptr);
930 LoopInfo::MemoVal* memo = nullptr;
931 if (pair1 != nullptr) {
932 memo = pair1->value;
933 } else {
934 memo = new LoopInfo::MemoVal();
935 loop->memo_cache_.Insert(LoopInfo::MemoKV::Pair(this, memo));
936 }
937 memo->memo_.Insert(
938 LoopInfo::MemoVal::PosKV::Pair(pos, std::make_pair(*min, *max)));
939 return true;
940 }
941 return false;
942}
943
944void InductionVar::PrintTo(BaseTextBuffer* f) const {
945 switch (kind_) {
946 case kInvariant:
947 if (mult_ != 0) {
948 f->Printf("(%" Pd64 " + %" Pd64 " x %.4s)", offset_, mult_,
949 def_->ToCString());
950 } else {
951 f->Printf("%" Pd64, offset_);
952 }
953 break;
954 case kLinear:
955 f->Printf("LIN(%s + %s * i)", initial_->ToCString(), next_->ToCString());
956 break;
957 case kWrapAround:
958 f->Printf("WRAP(%s, %s)", initial_->ToCString(), next_->ToCString());
959 break;
960 case kPeriodic:
961 f->Printf("PERIOD(%s, %s)", initial_->ToCString(), next_->ToCString());
962 break;
963 }
964}
965
966const char* InductionVar::ToCString() const {
967 char buffer[1024];
968 BufferFormatter f(buffer, sizeof(buffer));
969 PrintTo(&f);
970 return Thread::Current()->zone()->MakeCopyOfString(buffer);
971}
972
973LoopInfo::LoopInfo(intptr_t id, BlockEntryInstr* header, BitVector* blocks)
974 : id_(id),
975 header_(header),
976 blocks_(blocks),
977 back_edges_(),
978 induction_(),
979 memo_cache_(),
980 limit_(nullptr),
981 control_(nullptr),
982 outer_(nullptr),
983 inner_(nullptr),
984 next_(nullptr) {}
985
986void LoopInfo::AddBlocks(BitVector* blocks) {
987 blocks_->AddAll(blocks);
988}
989
990void LoopInfo::AddBackEdge(BlockEntryInstr* block) {
991 back_edges_.Add(block);
992}
993
994bool LoopInfo::IsBackEdge(BlockEntryInstr* block) const {
995 for (intptr_t i = 0, n = back_edges_.length(); i < n; i++) {
996 if (back_edges_[i] == block) {
997 return true;
998 }
999 }
1000 return false;
1001}
1002
1003bool LoopInfo::IsAlwaysTaken(BlockEntryInstr* block) const {
1004 // The loop header is always executed when executing a loop (including
1005 // loop body of a do-while). Reject any other loop body block that is
1006 // not directly controlled by header.
1007 if (block == header_) {
1008 return true;
1009 } else if (block->PredecessorCount() != 1 ||
1010 block->PredecessorAt(0) != header_) {
1011 return false;
1012 }
1013 // If the loop has a control induction, make sure the condition is such
1014 // that the loop body is entered at least once from the header.
1015 if (control_ != nullptr) {
1016 InductionVar* limit = nullptr;
1017 for (auto bound : control_->bounds()) {
1018 if (bound.branch_ == header_->last_instruction()) {
1019 limit = bound.limit_;
1020 break;
1021 }
1022 }
1023 // Control iterates at least once?
1024 if (limit != nullptr) {
1025 int64_t stride = 0;
1026 int64_t begin = 0;
1027 int64_t end = 0;
1028 if (InductionVar::IsLinear(control_, &stride) &&
1029 InductionVar::IsConstant(control_->initial(), &begin) &&
1030 InductionVar::IsConstant(limit, &end) &&
1031 ((stride == 1 && begin < end) || (stride == -1 && begin > end))) {
1032 return true;
1033 }
1034 }
1035 }
1036 return false;
1037}
1038
1039bool LoopInfo::IsHeaderPhi(Definition* def) const {
1040 return def != nullptr && def->IsPhi() && def->GetBlock() == header_ &&
1041 !def->AsPhi()->IsRedundant(); // phi(x,..,x) = x
1042}
1043
1044bool LoopInfo::IsIn(LoopInfo* loop) const {
1045 if (loop != nullptr) {
1046 return loop->Contains(header_);
1047 }
1048 return false;
1049}
1050
1051bool LoopInfo::Contains(BlockEntryInstr* block) const {
1052 return blocks_->Contains(block->preorder_number());
1053}
1054
1055intptr_t LoopInfo::NestingDepth() const {
1056 intptr_t nesting_depth = 1;
1057 for (LoopInfo* o = outer_; o != nullptr; o = o->outer()) {
1058 nesting_depth++;
1059 }
1060 return nesting_depth;
1061}
1062
1063void LoopInfo::ResetInduction() {
1064 induction_.Clear();
1065 memo_cache_.Clear();
1066}
1067
1068void LoopInfo::AddInduction(Definition* def, InductionVar* induc) {
1069 ASSERT(def != nullptr);
1070 ASSERT(induc != nullptr);
1071 induction_.Insert(InductionKV::Pair(def, induc));
1072}
1073
1074InductionVar* LoopInfo::LookupInduction(Definition* def) const {
1075 InductionKV::Pair* pair = induction_.Lookup(def);
1076 if (pair != nullptr) {
1077 return pair->value;
1078 }
1079 return nullptr;
1080}
1081
1082// Checks if an index is in range of a given length:
1083// for (int i = initial; i <= length - C; i++) {
1084// .... a[i] .... // initial >= 0 and C > 0:
1085// }
1086bool LoopInfo::IsInRange(Instruction* pos, Value* index, Value* length) {
1087 InductionVar* induc = LookupInduction(
1088 index->definition()->OriginalDefinitionIgnoreBoxingAndConstraints());
1089 InductionVar* len = LookupInduction(
1090 length->definition()->OriginalDefinitionIgnoreBoxingAndConstraints());
1091 if (induc != nullptr && len != nullptr) {
1092 // First, try the most common case. A simple induction directly
1093 // bounded by [c>=0,length-C>=0) for the length we are looking for.
1094 int64_t stride = 0;
1095 int64_t val = 0;
1096 int64_t diff = 0;
1097 if (InductionVar::IsLinear(induc, &stride) && stride == 1 &&
1098 InductionVar::IsConstant(induc->initial(), &val) && 0 <= val) {
1099 for (auto bound : induc->bounds()) {
1100 if (pos->IsDominatedBy(bound.branch_) &&
1101 len->CanComputeDifferenceWith(bound.limit_, &diff) && diff <= 0) {
1102 return true;
1103 }
1104 }
1105 }
1106 // If that fails, try to compute bounds using more outer loops.
1107 // Since array lengths >= 0, the conditions used during this
1108 // process avoid arithmetic wrap-around complications.
1109 InductionVar* min = nullptr;
1110 InductionVar* max = nullptr;
1111 if (induc->CanComputeBounds(this, pos, &min, &max)) {
1112 return InductionVar::IsConstant(min, &val) && 0 <= val &&
1113 len->CanComputeDifferenceWith(max, &diff) && diff < 0;
1114 }
1115 }
1116 return false;
1117}
1118
1119void LoopInfo::PrintTo(BaseTextBuffer* f) const {
1120 f->Printf("%*c", static_cast<int>(2 * NestingDepth()), ' ');
1121 f->Printf("loop%" Pd " B%" Pd " ", id_, header_->block_id());
1122 intptr_t num_blocks = 0;
1123 for (BitVector::Iterator it(blocks_); !it.Done(); it.Advance()) {
1124 num_blocks++;
1125 }
1126 f->Printf("#blocks=%" Pd, num_blocks);
1127 if (outer_ != nullptr) f->Printf(" outer=%" Pd, outer_->id_);
1128 if (inner_ != nullptr) f->Printf(" inner=%" Pd, inner_->id_);
1129 if (next_ != nullptr) f->Printf(" next=%" Pd, next_->id_);
1130 f->AddString(" [");
1131 for (intptr_t i = 0, n = back_edges_.length(); i < n; i++) {
1132 f->Printf(" B%" Pd, back_edges_[i]->block_id());
1133 }
1134 f->AddString(" ]");
1135}
1136
1137const char* LoopInfo::ToCString() const {
1138 char buffer[1024];
1139 BufferFormatter f(buffer, sizeof(buffer));
1140 PrintTo(&f);
1141 return Thread::Current()->zone()->MakeCopyOfString(buffer);
1142}
1143
1144LoopHierarchy::LoopHierarchy(ZoneGrowableArray<BlockEntryInstr*>* headers,
1145 const GrowableArray<BlockEntryInstr*>& preorder)
1146 : headers_(headers), preorder_(preorder), top_(nullptr) {
1147 Build();
1148}
1149
1150void LoopHierarchy::Build() {
1151 // Link every entry block to the closest enveloping loop.
1152 for (intptr_t i = 0, n = headers_->length(); i < n; ++i) {
1153 LoopInfo* loop = (*headers_)[i]->loop_info();
1154 for (BitVector::Iterator it(loop->blocks_); !it.Done(); it.Advance()) {
1155 BlockEntryInstr* block = preorder_[it.Current()];
1156 if (block->loop_info() == nullptr) {
1157 block->set_loop_info(loop);
1158 } else {
1159 ASSERT(block->loop_info()->IsIn(loop));
1160 }
1161 }
1162 }
1163 // Build hierarchy from headers.
1164 for (intptr_t i = 0, n = headers_->length(); i < n; ++i) {
1165 BlockEntryInstr* header = (*headers_)[i];
1166 LoopInfo* loop = header->loop_info();
1167 LoopInfo* dom_loop = header->dominator()->loop_info();
1168 ASSERT(loop->outer_ == nullptr);
1169 ASSERT(loop->next_ == nullptr);
1170 if (loop->IsIn(dom_loop)) {
1171 loop->outer_ = dom_loop;
1172 loop->next_ = dom_loop->inner_;
1173 dom_loop->inner_ = loop;
1174 } else {
1175 loop->next_ = top_;
1176 top_ = loop;
1177 }
1178 }
1179 // If tracing is requested, print the loop hierarchy.
1180 if (FLAG_trace_optimization) {
1181 Print(top_);
1182 }
1183}
1184
1185void LoopHierarchy::Print(LoopInfo* loop) const {
1186 for (; loop != nullptr; loop = loop->next_) {
1187 THR_Print("%s {", loop->ToCString());
1188 for (BitVector::Iterator it(loop->blocks_); !it.Done(); it.Advance()) {
1189 THR_Print(" B%" Pd, preorder_[it.Current()]->block_id());
1190 }
1191 THR_Print(" }\n");
1192 Print(loop->inner_);
1193 }
1194}
1195
1196void LoopHierarchy::ComputeInduction() const {
1197 InductionVarAnalysis(preorder_).VisitHierarchy(top_);
1198}
1199
1200} // namespace dart
1201