• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1  /*
2   * Copyright (C) 2015 The Android Open Source Project
3   *
4   * Licensed under the Apache License, Version 2.0 (the "License");
5   * you may not use this file except in compliance with the License.
6   * You may obtain a copy of the License at
7   *
8   *      http://www.apache.org/licenses/LICENSE-2.0
9   *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  #include "induction_var_analysis.h"
18  #include "induction_var_range.h"
19  
20  namespace art {
21  
22  /**
23   * Since graph traversal may enter a SCC at any position, an initial representation may be rotated,
24   * along dependences, viz. any of (a, b, c, d), (d, a, b, c)  (c, d, a, b), (b, c, d, a) assuming
25   * a chain of dependences (mutual independent items may occur in arbitrary order). For proper
26   * classification, the lexicographically first entry-phi is rotated to the front.
27   */
RotateEntryPhiFirst(HLoopInformation * loop,ArenaVector<HInstruction * > * scc,ArenaVector<HInstruction * > * new_scc)28  static void RotateEntryPhiFirst(HLoopInformation* loop,
29                                  ArenaVector<HInstruction*>* scc,
30                                  ArenaVector<HInstruction*>* new_scc) {
31    // Find very first entry-phi.
32    const HInstructionList& phis = loop->GetHeader()->GetPhis();
33    HInstruction* phi = nullptr;
34    size_t phi_pos = -1;
35    const size_t size = scc->size();
36    for (size_t i = 0; i < size; i++) {
37      HInstruction* other = (*scc)[i];
38      if (other->IsLoopHeaderPhi() && (phi == nullptr || phis.FoundBefore(other, phi))) {
39        phi = other;
40        phi_pos = i;
41      }
42    }
43  
44    // If found, bring that entry-phi to front.
45    if (phi != nullptr) {
46      new_scc->clear();
47      for (size_t i = 0; i < size; i++) {
48        new_scc->push_back((*scc)[phi_pos]);
49        if (++phi_pos >= size) phi_pos = 0;
50      }
51      DCHECK_EQ(size, new_scc->size());
52      scc->swap(*new_scc);
53    }
54  }
55  
56  /**
57   * Returns true if the from/to types denote a narrowing, integral conversion (precision loss).
58   */
IsNarrowingIntegralConversion(Primitive::Type from,Primitive::Type to)59  static bool IsNarrowingIntegralConversion(Primitive::Type from, Primitive::Type to) {
60    switch (from) {
61      case Primitive::kPrimLong:
62        return to == Primitive::kPrimByte || to == Primitive::kPrimShort
63            || to == Primitive::kPrimChar || to == Primitive::kPrimInt;
64      case Primitive::kPrimInt:
65        return to == Primitive::kPrimByte || to == Primitive::kPrimShort
66            || to == Primitive::kPrimChar;
67      case Primitive::kPrimChar:
68      case Primitive::kPrimShort:
69        return to == Primitive::kPrimByte;
70      default:
71        return false;
72    }
73  }
74  
75  /**
76   * Returns narrowest data type.
77   */
Narrowest(Primitive::Type type1,Primitive::Type type2)78  static Primitive::Type Narrowest(Primitive::Type type1, Primitive::Type type2) {
79    return Primitive::ComponentSize(type1) <= Primitive::ComponentSize(type2) ? type1 : type2;
80  }
81  
82  //
83  // Class methods.
84  //
85  
HInductionVarAnalysis(HGraph * graph)86  HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph)
87      : HOptimization(graph, kInductionPassName),
88        global_depth_(0),
89        stack_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
90        scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
91        map_(std::less<HInstruction*>(),
92             graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
93        cycle_(std::less<HInstruction*>(),
94               graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
95        induction_(std::less<HLoopInformation*>(),
96                   graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)) {
97  }
98  
Run()99  void HInductionVarAnalysis::Run() {
100    // Detects sequence variables (generalized induction variables) during an outer to inner
101    // traversal of all loops using Gerlek's algorithm. The order is important to enable
102    // range analysis on outer loop while visiting inner loops.
103    for (HReversePostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
104      HBasicBlock* graph_block = it_graph.Current();
105      // Don't analyze irreducible loops.
106      // TODO(ajcbik): could/should we remove this restriction?
107      if (graph_block->IsLoopHeader() && !graph_block->GetLoopInformation()->IsIrreducible()) {
108        VisitLoop(graph_block->GetLoopInformation());
109      }
110    }
111  }
112  
VisitLoop(HLoopInformation * loop)113  void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) {
114    // Find strongly connected components (SSCs) in the SSA graph of this loop using Tarjan's
115    // algorithm. Due to the descendant-first nature, classification happens "on-demand".
116    global_depth_ = 0;
117    DCHECK(stack_.empty());
118    map_.clear();
119  
120    for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) {
121      HBasicBlock* loop_block = it_loop.Current();
122      DCHECK(loop_block->IsInLoop());
123      if (loop_block->GetLoopInformation() != loop) {
124        continue;  // Inner loops already visited.
125      }
126      // Visit phi-operations and instructions.
127      for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) {
128        HInstruction* instruction = it.Current();
129        if (!IsVisitedNode(instruction)) {
130          VisitNode(loop, instruction);
131        }
132      }
133      for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) {
134        HInstruction* instruction = it.Current();
135        if (!IsVisitedNode(instruction)) {
136          VisitNode(loop, instruction);
137        }
138      }
139    }
140  
141    DCHECK(stack_.empty());
142    map_.clear();
143  
144    // Determine the loop's trip-count.
145    VisitControl(loop);
146  }
147  
VisitNode(HLoopInformation * loop,HInstruction * instruction)148  void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) {
149    const uint32_t d1 = ++global_depth_;
150    map_.Put(instruction, NodeInfo(d1));
151    stack_.push_back(instruction);
152  
153    // Visit all descendants.
154    uint32_t low = d1;
155    for (size_t i = 0, count = instruction->InputCount(); i < count; ++i) {
156      low = std::min(low, VisitDescendant(loop, instruction->InputAt(i)));
157    }
158  
159    // Lower or found SCC?
160    if (low < d1) {
161      map_.find(instruction)->second.depth = low;
162    } else {
163      scc_.clear();
164      cycle_.clear();
165  
166      // Pop the stack to build the SCC for classification.
167      while (!stack_.empty()) {
168        HInstruction* x = stack_.back();
169        scc_.push_back(x);
170        stack_.pop_back();
171        map_.find(x)->second.done = true;
172        if (x == instruction) {
173          break;
174        }
175      }
176  
177      // Type of induction.
178      type_ = scc_[0]->GetType();
179  
180      // Classify the SCC.
181      if (scc_.size() == 1 && !scc_[0]->IsLoopHeaderPhi()) {
182        ClassifyTrivial(loop, scc_[0]);
183      } else {
184        ClassifyNonTrivial(loop);
185      }
186  
187      scc_.clear();
188      cycle_.clear();
189    }
190  }
191  
VisitDescendant(HLoopInformation * loop,HInstruction * instruction)192  uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) {
193    // If the definition is either outside the loop (loop invariant entry value)
194    // or assigned in inner loop (inner exit value), the traversal stops.
195    HLoopInformation* otherLoop = instruction->GetBlock()->GetLoopInformation();
196    if (otherLoop != loop) {
197      return global_depth_;
198    }
199  
200    // Inspect descendant node.
201    if (!IsVisitedNode(instruction)) {
202      VisitNode(loop, instruction);
203      return map_.find(instruction)->second.depth;
204    } else {
205      auto it = map_.find(instruction);
206      return it->second.done ? global_depth_ : it->second.depth;
207    }
208  }
209  
ClassifyTrivial(HLoopInformation * loop,HInstruction * instruction)210  void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
211    InductionInfo* info = nullptr;
212    if (instruction->IsPhi()) {
213      info = TransferPhi(loop, instruction, /* input_index */ 0);
214    } else if (instruction->IsAdd()) {
215      info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
216                            LookupInfo(loop, instruction->InputAt(1)), kAdd);
217    } else if (instruction->IsSub()) {
218      info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
219                            LookupInfo(loop, instruction->InputAt(1)), kSub);
220    } else if (instruction->IsMul()) {
221      info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
222                         LookupInfo(loop, instruction->InputAt(1)));
223    } else if (instruction->IsShl()) {
224      info = TransferShl(LookupInfo(loop, instruction->InputAt(0)),
225                         LookupInfo(loop, instruction->InputAt(1)),
226                         instruction->InputAt(0)->GetType());
227    } else if (instruction->IsNeg()) {
228      info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)));
229    } else if (instruction->IsTypeConversion()) {
230      info = TransferCnv(LookupInfo(loop, instruction->InputAt(0)),
231                         instruction->AsTypeConversion()->GetInputType(),
232                         instruction->AsTypeConversion()->GetResultType());
233  
234    } else if (instruction->IsBoundsCheck()) {
235      info = LookupInfo(loop, instruction->InputAt(0));  // Pass-through.
236    }
237  
238    // Successfully classified?
239    if (info != nullptr) {
240      AssignInfo(loop, instruction, info);
241    }
242  }
243  
ClassifyNonTrivial(HLoopInformation * loop)244  void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
245    const size_t size = scc_.size();
246    DCHECK_GE(size, 1u);
247  
248    // Rotate proper entry-phi to front.
249    if (size > 1) {
250      ArenaVector<HInstruction*> other(graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis));
251      RotateEntryPhiFirst(loop, &scc_, &other);
252    }
253  
254    // Analyze from entry-phi onwards.
255    HInstruction* phi = scc_[0];
256    if (!phi->IsLoopHeaderPhi()) {
257      return;
258    }
259  
260    // External link should be loop invariant.
261    InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
262    if (initial == nullptr || initial->induction_class != kInvariant) {
263      return;
264    }
265  
266    // Singleton is wrap-around induction if all internal links have the same meaning.
267    if (size == 1) {
268      InductionInfo* update = TransferPhi(loop, phi, /* input_index */ 1);
269      if (update != nullptr) {
270        AssignInfo(loop, phi, CreateInduction(kWrapAround, initial, update, type_));
271      }
272      return;
273    }
274  
275    // Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns
276    // temporary meaning to its nodes, seeded from the phi instruction and back.
277    for (size_t i = 1; i < size; i++) {
278      HInstruction* instruction = scc_[i];
279      InductionInfo* update = nullptr;
280      if (instruction->IsPhi()) {
281        update = SolvePhiAllInputs(loop, phi, instruction);
282      } else if (instruction->IsAdd()) {
283        update = SolveAddSub(
284            loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true);
285      } else if (instruction->IsSub()) {
286        update = SolveAddSub(
287            loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true);
288      } else if (instruction->IsTypeConversion()) {
289        update = SolveCnv(instruction->AsTypeConversion());
290      }
291      if (update == nullptr) {
292        return;
293      }
294      cycle_.Put(instruction, update);
295    }
296  
297    // Success if all internal links received the same temporary meaning.
298    InductionInfo* induction = SolvePhi(phi, /* input_index */ 1);
299    if (induction != nullptr) {
300      switch (induction->induction_class) {
301        case kInvariant:
302          // Classify first phi and then the rest of the cycle "on-demand".
303          // Statements are scanned in order.
304          AssignInfo(loop, phi, CreateInduction(kLinear, induction, initial, type_));
305          for (size_t i = 1; i < size; i++) {
306            ClassifyTrivial(loop, scc_[i]);
307          }
308          break;
309        case kPeriodic:
310          // Classify all elements in the cycle with the found periodic induction while
311          // rotating each first element to the end. Lastly, phi is classified.
312          // Statements are scanned in reverse order.
313          for (size_t i = size - 1; i >= 1; i--) {
314            AssignInfo(loop, scc_[i], induction);
315            induction = RotatePeriodicInduction(induction->op_b, induction->op_a);
316          }
317          AssignInfo(loop, phi, induction);
318          break;
319        default:
320          break;
321      }
322    }
323  }
324  
RotatePeriodicInduction(InductionInfo * induction,InductionInfo * last)325  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduction(
326      InductionInfo* induction,
327      InductionInfo* last) {
328    // Rotates a periodic induction of the form
329    //   (a, b, c, d, e)
330    // into
331    //   (b, c, d, e, a)
332    // in preparation of assigning this to the previous variable in the sequence.
333    if (induction->induction_class == kInvariant) {
334      return CreateInduction(kPeriodic, induction, last, type_);
335    }
336    return CreateInduction(
337        kPeriodic, induction->op_a, RotatePeriodicInduction(induction->op_b, last), type_);
338  }
339  
TransferPhi(HLoopInformation * loop,HInstruction * phi,size_t input_index)340  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopInformation* loop,
341                                                                           HInstruction* phi,
342                                                                           size_t input_index) {
343    // Match all phi inputs from input_index onwards exactly.
344    const size_t count = phi->InputCount();
345    DCHECK_LT(input_index, count);
346    InductionInfo* a = LookupInfo(loop, phi->InputAt(input_index));
347    for (size_t i = input_index + 1; i < count; i++) {
348      InductionInfo* b = LookupInfo(loop, phi->InputAt(i));
349      if (!InductionEqual(a, b)) {
350        return nullptr;
351      }
352    }
353    return a;
354  }
355  
TransferAddSub(InductionInfo * a,InductionInfo * b,InductionOp op)356  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a,
357                                                                              InductionInfo* b,
358                                                                              InductionOp op) {
359    // Transfer over an addition or subtraction: any invariant, linear, wrap-around, or periodic
360    // can be combined with an invariant to yield a similar result. Even two linear inputs can
361    // be combined. All other combinations fail, however.
362    if (a != nullptr && b != nullptr) {
363      if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
364        return CreateInvariantOp(op, a, b);
365      } else if (a->induction_class == kLinear && b->induction_class == kLinear) {
366        return CreateInduction(kLinear,
367                               TransferAddSub(a->op_a, b->op_a, op),
368                               TransferAddSub(a->op_b, b->op_b, op),
369                               type_);
370      } else if (a->induction_class == kInvariant) {
371        InductionInfo* new_a = b->op_a;
372        InductionInfo* new_b = TransferAddSub(a, b->op_b, op);
373        if (b->induction_class != kLinear) {
374          DCHECK(b->induction_class == kWrapAround || b->induction_class == kPeriodic);
375          new_a = TransferAddSub(a, new_a, op);
376        } else if (op == kSub) {  // Negation required.
377          new_a = TransferNeg(new_a);
378        }
379        return CreateInduction(b->induction_class, new_a, new_b, type_);
380      } else if (b->induction_class == kInvariant) {
381        InductionInfo* new_a = a->op_a;
382        InductionInfo* new_b = TransferAddSub(a->op_b, b, op);
383        if (a->induction_class != kLinear) {
384          DCHECK(a->induction_class == kWrapAround || a->induction_class == kPeriodic);
385          new_a = TransferAddSub(new_a, b, op);
386        }
387        return CreateInduction(a->induction_class, new_a, new_b, type_);
388      }
389    }
390    return nullptr;
391  }
392  
TransferMul(InductionInfo * a,InductionInfo * b)393  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a,
394                                                                           InductionInfo* b) {
395    // Transfer over a multiplication: any invariant, linear, wrap-around, or periodic
396    // can be multiplied with an invariant to yield a similar but multiplied result.
397    // Two non-invariant inputs cannot be multiplied, however.
398    if (a != nullptr && b != nullptr) {
399      if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
400        return CreateInvariantOp(kMul, a, b);
401      } else if (a->induction_class == kInvariant) {
402        return CreateInduction(b->induction_class,
403                               TransferMul(a, b->op_a),
404                               TransferMul(a, b->op_b),
405                               type_);
406      } else if (b->induction_class == kInvariant) {
407        return CreateInduction(a->induction_class,
408                               TransferMul(a->op_a, b),
409                               TransferMul(a->op_b, b),
410                               type_);
411      }
412    }
413    return nullptr;
414  }
415  
TransferShl(InductionInfo * a,InductionInfo * b,Primitive::Type type)416  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferShl(InductionInfo* a,
417                                                                           InductionInfo* b,
418                                                                           Primitive::Type type) {
419    // Transfer over a shift left: treat shift by restricted constant as equivalent multiplication.
420    int64_t value = -1;
421    if (a != nullptr && IsExact(b, &value)) {
422      // Obtain the constant needed for the multiplication. This yields an existing instruction
423      // if the constants is already there. Otherwise, this has a side effect on the HIR.
424      // The restriction on the shift factor avoids generating a negative constant
425      // (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that generalization
426      // for shift factors outside [0,32) and [0,64) ranges is done by earlier simplification.
427      if ((type == Primitive::kPrimInt  && 0 <= value && value < 31) ||
428          (type == Primitive::kPrimLong && 0 <= value && value < 63)) {
429        return TransferMul(a, CreateConstant(1 << value, type));
430      }
431    }
432    return nullptr;
433  }
434  
TransferNeg(InductionInfo * a)435  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) {
436    // Transfer over a unary negation: an invariant, linear, wrap-around, or periodic input
437    // yields a similar but negated induction as result.
438    if (a != nullptr) {
439      if (a->induction_class == kInvariant) {
440        return CreateInvariantOp(kNeg, nullptr, a);
441      }
442      return CreateInduction(a->induction_class, TransferNeg(a->op_a), TransferNeg(a->op_b), type_);
443    }
444    return nullptr;
445  }
446  
TransferCnv(InductionInfo * a,Primitive::Type from,Primitive::Type to)447  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferCnv(InductionInfo* a,
448                                                                           Primitive::Type from,
449                                                                           Primitive::Type to) {
450    if (a != nullptr) {
451      // Allow narrowing conversion in certain cases.
452      if (IsNarrowingIntegralConversion(from, to)) {
453        if (a->induction_class == kLinear) {
454          if (a->type == to || (a->type == from && IsNarrowingIntegralConversion(from, to))) {
455            return CreateInduction(kLinear, a->op_a, a->op_b, to);
456          }
457        }
458        // TODO: other cases useful too?
459      }
460    }
461    return nullptr;
462  }
463  
SolvePhi(HInstruction * phi,size_t input_index)464  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HInstruction* phi,
465                                                                        size_t input_index) {
466    // Match all phi inputs from input_index onwards exactly.
467    const size_t count = phi->InputCount();
468    DCHECK_LT(input_index, count);
469    auto ita = cycle_.find(phi->InputAt(input_index));
470    if (ita != cycle_.end()) {
471      for (size_t i = input_index + 1; i < count; i++) {
472        auto itb = cycle_.find(phi->InputAt(i));
473        if (itb == cycle_.end() ||
474            !HInductionVarAnalysis::InductionEqual(ita->second, itb->second)) {
475          return nullptr;
476        }
477      }
478      return ita->second;
479    }
480    return nullptr;
481  }
482  
SolvePhiAllInputs(HLoopInformation * loop,HInstruction * entry_phi,HInstruction * phi)483  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhiAllInputs(
484      HLoopInformation* loop,
485      HInstruction* entry_phi,
486      HInstruction* phi) {
487    // Match all phi inputs.
488    InductionInfo* match = SolvePhi(phi, /* input_index */ 0);
489    if (match != nullptr) {
490      return match;
491    }
492  
493    // Otherwise, try to solve for a periodic seeded from phi onward.
494    // Only tight multi-statement cycles are considered in order to
495    // simplify rotating the periodic during the final classification.
496    if (phi->IsLoopHeaderPhi() && phi->InputCount() == 2) {
497      InductionInfo* a = LookupInfo(loop, phi->InputAt(0));
498      if (a != nullptr && a->induction_class == kInvariant) {
499        if (phi->InputAt(1) == entry_phi) {
500          InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
501          return CreateInduction(kPeriodic, a, initial, type_);
502        }
503        InductionInfo* b = SolvePhi(phi, /* input_index */ 1);
504        if (b != nullptr && b->induction_class == kPeriodic) {
505          return CreateInduction(kPeriodic, a, b, type_);
506        }
507      }
508    }
509    return nullptr;
510  }
511  
SolveAddSub(HLoopInformation * loop,HInstruction * entry_phi,HInstruction * instruction,HInstruction * x,HInstruction * y,InductionOp op,bool is_first_call)512  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop,
513                                                                           HInstruction* entry_phi,
514                                                                           HInstruction* instruction,
515                                                                           HInstruction* x,
516                                                                           HInstruction* y,
517                                                                           InductionOp op,
518                                                                           bool is_first_call) {
519    // Solve within a cycle over an addition or subtraction: adding or subtracting an
520    // invariant value, seeded from phi, keeps adding to the stride of the induction.
521    InductionInfo* b = LookupInfo(loop, y);
522    if (b != nullptr && b->induction_class == kInvariant) {
523      if (x == entry_phi) {
524        return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b);
525      }
526      auto it = cycle_.find(x);
527      if (it != cycle_.end()) {
528        InductionInfo* a = it->second;
529        if (a->induction_class == kInvariant) {
530          return CreateInvariantOp(op, a, b);
531        }
532      }
533    }
534  
535    // Try some alternatives before failing.
536    if (op == kAdd) {
537      // Try the other way around for an addition if considered for first time.
538      if (is_first_call) {
539        return SolveAddSub(loop, entry_phi, instruction, y, x, op, false);
540      }
541    } else if (op == kSub) {
542      // Solve within a tight cycle that is formed by exactly two instructions,
543      // one phi and one update, for a periodic idiom of the form k = c - k;
544      if (y == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
545        InductionInfo* a = LookupInfo(loop, x);
546        if (a != nullptr && a->induction_class == kInvariant) {
547          InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
548          return CreateInduction(kPeriodic, CreateInvariantOp(kSub, a, initial), initial, type_);
549        }
550      }
551    }
552  
553    return nullptr;
554  }
555  
SolveCnv(HTypeConversion * conversion)556  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveCnv(HTypeConversion* conversion) {
557    Primitive::Type from = conversion->GetInputType();
558    Primitive::Type to = conversion->GetResultType();
559    // A narrowing conversion is allowed within the cycle of a linear induction, provided that the
560    // narrowest encountered type is recorded with the induction to account for the precision loss.
561    if (IsNarrowingIntegralConversion(from, to)) {
562      auto it = cycle_.find(conversion->GetInput());
563      if (it != cycle_.end() && it->second->induction_class == kInvariant) {
564        type_ = Narrowest(type_, to);
565        return it->second;
566      }
567    }
568    return nullptr;
569  }
570  
VisitControl(HLoopInformation * loop)571  void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) {
572    HInstruction* control = loop->GetHeader()->GetLastInstruction();
573    if (control->IsIf()) {
574      HIf* ifs = control->AsIf();
575      HBasicBlock* if_true = ifs->IfTrueSuccessor();
576      HBasicBlock* if_false = ifs->IfFalseSuccessor();
577      HInstruction* if_expr = ifs->InputAt(0);
578      // Determine if loop has following structure in header.
579      // loop-header: ....
580      //              if (condition) goto X
581      if (if_expr->IsCondition()) {
582        HCondition* condition = if_expr->AsCondition();
583        InductionInfo* a = LookupInfo(loop, condition->InputAt(0));
584        InductionInfo* b = LookupInfo(loop, condition->InputAt(1));
585        Primitive::Type type = condition->InputAt(0)->GetType();
586        // Determine if the loop control uses a known sequence on an if-exit (X outside) or on
587        // an if-iterate (X inside), expressed as if-iterate when passed into VisitCondition().
588        if (a == nullptr || b == nullptr) {
589          return;  // Loop control is not a sequence.
590        } else if (if_true->GetLoopInformation() != loop && if_false->GetLoopInformation() == loop) {
591          VisitCondition(loop, a, b, type, condition->GetOppositeCondition());
592        } else if (if_true->GetLoopInformation() == loop && if_false->GetLoopInformation() != loop) {
593          VisitCondition(loop, a, b, type, condition->GetCondition());
594        }
595      }
596    }
597  }
598  
VisitCondition(HLoopInformation * loop,InductionInfo * a,InductionInfo * b,Primitive::Type type,IfCondition cmp)599  void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop,
600                                             InductionInfo* a,
601                                             InductionInfo* b,
602                                             Primitive::Type type,
603                                             IfCondition cmp) {
604    if (a->induction_class == kInvariant && b->induction_class == kLinear) {
605      // Swap condition if induction is at right-hand-side (e.g. U > i is same as i < U).
606      switch (cmp) {
607        case kCondLT: VisitCondition(loop, b, a, type, kCondGT); break;
608        case kCondLE: VisitCondition(loop, b, a, type, kCondGE); break;
609        case kCondGT: VisitCondition(loop, b, a, type, kCondLT); break;
610        case kCondGE: VisitCondition(loop, b, a, type, kCondLE); break;
611        case kCondNE: VisitCondition(loop, b, a, type, kCondNE); break;
612        default: break;
613      }
614    } else if (a->induction_class == kLinear && b->induction_class == kInvariant) {
615      // Analyze condition with induction at left-hand-side (e.g. i < U).
616      InductionInfo* lower_expr = a->op_b;
617      InductionInfo* upper_expr = b;
618      InductionInfo* stride_expr = a->op_a;
619      // Constant stride?
620      int64_t stride_value = 0;
621      if (!IsExact(stride_expr, &stride_value)) {
622        return;
623      }
624      // Rewrite condition i != U into strict end condition i < U or i > U if this end condition
625      // is reached exactly (tested by verifying if the loop has a unit stride and the non-strict
626      // condition would be always taken).
627      if (cmp == kCondNE && ((stride_value == +1 && IsTaken(lower_expr, upper_expr, kCondLE)) ||
628                             (stride_value == -1 && IsTaken(lower_expr, upper_expr, kCondGE)))) {
629        cmp = stride_value > 0 ? kCondLT : kCondGT;
630      }
631      // Only accept integral condition. A mismatch between the type of condition and the induction
632      // is only allowed if the, necessarily narrower, induction range fits the narrower control.
633      if (type != Primitive::kPrimInt && type != Primitive::kPrimLong) {
634        return;  // not integral
635      } else if (type != a->type &&
636                 !FitsNarrowerControl(lower_expr, upper_expr, stride_value, a->type, cmp)) {
637        return;  // mismatched type
638      }
639      // Normalize a linear loop control with a nonzero stride:
640      //   stride > 0, either i < U or i <= U
641      //   stride < 0, either i > U or i >= U
642      if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
643          (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
644        VisitTripCount(loop, lower_expr, upper_expr, stride_expr, stride_value, type, cmp);
645      }
646    }
647  }
648  
VisitTripCount(HLoopInformation * loop,InductionInfo * lower_expr,InductionInfo * upper_expr,InductionInfo * stride_expr,int64_t stride_value,Primitive::Type type,IfCondition cmp)649  void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop,
650                                             InductionInfo* lower_expr,
651                                             InductionInfo* upper_expr,
652                                             InductionInfo* stride_expr,
653                                             int64_t stride_value,
654                                             Primitive::Type type,
655                                             IfCondition cmp) {
656    // Any loop of the general form:
657    //
658    //    for (i = L; i <= U; i += S) // S > 0
659    // or for (i = L; i >= U; i += S) // S < 0
660    //      .. i ..
661    //
662    // can be normalized into:
663    //
664    //    for (n = 0; n < TC; n++) // where TC = (U + S - L) / S
665    //      .. L + S * n ..
666    //
667    // taking the following into consideration:
668    //
669    // (1) Using the same precision, the TC (trip-count) expression should be interpreted as
670    //     an unsigned entity, for example, as in the following loop that uses the full range:
671    //     for (int i = INT_MIN; i < INT_MAX; i++) // TC = UINT_MAX
672    // (2) The TC is only valid if the loop is taken, otherwise TC = 0, as in:
673    //     for (int i = 12; i < U; i++) // TC = 0 when U < 12
674    //     If this cannot be determined at compile-time, the TC is only valid within the
675    //     loop-body proper, not the loop-header unless enforced with an explicit taken-test.
676    // (3) The TC is only valid if the loop is finite, otherwise TC has no value, as in:
677    //     for (int i = 0; i <= U; i++) // TC = Inf when U = INT_MAX
678    //     If this cannot be determined at compile-time, the TC is only valid when enforced
679    //     with an explicit finite-test.
680    // (4) For loops which early-exits, the TC forms an upper bound, as in:
681    //     for (int i = 0; i < 10 && ....; i++) // TC <= 10
682    InductionInfo* trip_count = upper_expr;
683    const bool is_taken = IsTaken(lower_expr, upper_expr, cmp);
684    const bool is_finite = IsFinite(upper_expr, stride_value, type, cmp);
685    const bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1;
686    if (!cancels) {
687      // Convert exclusive integral inequality into inclusive integral inequality,
688      // viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1.
689      if (cmp == kCondLT) {
690        trip_count = CreateInvariantOp(kSub, trip_count, CreateConstant(1, type));
691      } else if (cmp == kCondGT) {
692        trip_count = CreateInvariantOp(kAdd, trip_count, CreateConstant(1, type));
693      }
694      // Compensate for stride.
695      trip_count = CreateInvariantOp(kAdd, trip_count, stride_expr);
696    }
697    trip_count = CreateInvariantOp(
698        kDiv, CreateInvariantOp(kSub, trip_count, lower_expr), stride_expr);
699    // Assign the trip-count expression to the loop control. Clients that use the information
700    // should be aware that the expression is only valid under the conditions listed above.
701    InductionOp tcKind = kTripCountInBodyUnsafe;  // needs both tests
702    if (is_taken && is_finite) {
703      tcKind = kTripCountInLoop;  // needs neither test
704    } else if (is_finite) {
705      tcKind = kTripCountInBody;  // needs taken-test
706    } else if (is_taken) {
707      tcKind = kTripCountInLoopUnsafe;  // needs finite-test
708    }
709    InductionOp op = kNop;
710    switch (cmp) {
711      case kCondLT: op = kLT; break;
712      case kCondLE: op = kLE; break;
713      case kCondGT: op = kGT; break;
714      case kCondGE: op = kGE; break;
715      default:      LOG(FATAL) << "CONDITION UNREACHABLE";
716    }
717    InductionInfo* taken_test = CreateInvariantOp(op, lower_expr, upper_expr);
718    AssignInfo(loop,
719               loop->GetHeader()->GetLastInstruction(),
720               CreateTripCount(tcKind, trip_count, taken_test, type));
721  }
722  
IsTaken(InductionInfo * lower_expr,InductionInfo * upper_expr,IfCondition cmp)723  bool HInductionVarAnalysis::IsTaken(InductionInfo* lower_expr,
724                                      InductionInfo* upper_expr,
725                                      IfCondition cmp) {
726    int64_t lower_value;
727    int64_t upper_value;
728    switch (cmp) {
729      case kCondLT:
730        return IsAtMost(lower_expr, &lower_value)
731            && IsAtLeast(upper_expr, &upper_value)
732            && lower_value < upper_value;
733      case kCondLE:
734        return IsAtMost(lower_expr, &lower_value)
735            && IsAtLeast(upper_expr, &upper_value)
736            && lower_value <= upper_value;
737      case kCondGT:
738        return IsAtLeast(lower_expr, &lower_value)
739            && IsAtMost(upper_expr, &upper_value)
740            && lower_value > upper_value;
741      case kCondGE:
742        return IsAtLeast(lower_expr, &lower_value)
743            && IsAtMost(upper_expr, &upper_value)
744            && lower_value >= upper_value;
745      default:
746        LOG(FATAL) << "CONDITION UNREACHABLE";
747    }
748    return false;  // not certain, may be untaken
749  }
750  
IsFinite(InductionInfo * upper_expr,int64_t stride_value,Primitive::Type type,IfCondition cmp)751  bool HInductionVarAnalysis::IsFinite(InductionInfo* upper_expr,
752                                       int64_t stride_value,
753                                       Primitive::Type type,
754                                       IfCondition cmp) {
755    const int64_t min = Primitive::MinValueOfIntegralType(type);
756    const int64_t max = Primitive::MaxValueOfIntegralType(type);
757    // Some rules under which it is certain at compile-time that the loop is finite.
758    int64_t value;
759    switch (cmp) {
760      case kCondLT:
761        return stride_value == 1 ||
762            (IsAtMost(upper_expr, &value) && value <= (max - stride_value + 1));
763      case kCondLE:
764        return (IsAtMost(upper_expr, &value) && value <= (max - stride_value));
765      case kCondGT:
766        return stride_value == -1 ||
767            (IsAtLeast(upper_expr, &value) && value >= (min - stride_value - 1));
768      case kCondGE:
769        return (IsAtLeast(upper_expr, &value) && value >= (min - stride_value));
770      default:
771        LOG(FATAL) << "CONDITION UNREACHABLE";
772    }
773    return false;  // not certain, may be infinite
774  }
775  
FitsNarrowerControl(InductionInfo * lower_expr,InductionInfo * upper_expr,int64_t stride_value,Primitive::Type type,IfCondition cmp)776  bool HInductionVarAnalysis::FitsNarrowerControl(InductionInfo* lower_expr,
777                                                  InductionInfo* upper_expr,
778                                                  int64_t stride_value,
779                                                  Primitive::Type type,
780                                                  IfCondition cmp) {
781    int64_t min = Primitive::MinValueOfIntegralType(type);
782    int64_t max = Primitive::MaxValueOfIntegralType(type);
783    // Inclusive test need one extra.
784    if (stride_value != 1 && stride_value != -1) {
785      return false;  // non-unit stride
786    } else if (cmp == kCondLE) {
787      max--;
788    } else if (cmp == kCondGE) {
789      min++;
790    }
791    // Do both bounds fit the range?
792    // Note: The `value` is initialized to please valgrind - the compiler can reorder
793    // the return value check with the `value` check, b/27651442 .
794    int64_t value = 0;
795    return IsAtLeast(lower_expr, &value) && value >= min &&
796           IsAtMost(lower_expr, &value)  && value <= max &&
797           IsAtLeast(upper_expr, &value) && value >= min &&
798           IsAtMost(upper_expr, &value)  && value <= max;
799  }
800  
AssignInfo(HLoopInformation * loop,HInstruction * instruction,InductionInfo * info)801  void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop,
802                                         HInstruction* instruction,
803                                         InductionInfo* info) {
804    auto it = induction_.find(loop);
805    if (it == induction_.end()) {
806      it = induction_.Put(loop,
807                          ArenaSafeMap<HInstruction*, InductionInfo*>(
808                              std::less<HInstruction*>(),
809                              graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)));
810    }
811    it->second.Put(instruction, info);
812  }
813  
LookupInfo(HLoopInformation * loop,HInstruction * instruction)814  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInformation* loop,
815                                                                          HInstruction* instruction) {
816    auto it = induction_.find(loop);
817    if (it != induction_.end()) {
818      auto loop_it = it->second.find(instruction);
819      if (loop_it != it->second.end()) {
820        return loop_it->second;
821      }
822    }
823    if (loop->IsDefinedOutOfTheLoop(instruction)) {
824      InductionInfo* info = CreateInvariantFetch(instruction);
825      AssignInfo(loop, instruction, info);
826      return info;
827    }
828    return nullptr;
829  }
830  
CreateConstant(int64_t value,Primitive::Type type)831  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateConstant(int64_t value,
832                                                                              Primitive::Type type) {
833    if (type == Primitive::kPrimInt) {
834      return CreateInvariantFetch(graph_->GetIntConstant(value));
835    }
836    DCHECK_EQ(type, Primitive::kPrimLong);
837    return CreateInvariantFetch(graph_->GetLongConstant(value));
838  }
839  
CreateSimplifiedInvariant(InductionOp op,InductionInfo * a,InductionInfo * b)840  HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant(
841      InductionOp op,
842      InductionInfo* a,
843      InductionInfo* b) {
844    // Perform some light-weight simplifications during construction of a new invariant.
845    // This often safes memory and yields a more concise representation of the induction.
846    // More exhaustive simplifications are done by later phases once induction nodes are
847    // translated back into HIR code (e.g. by loop optimizations or BCE).
848    int64_t value = -1;
849    if (IsExact(a, &value)) {
850      if (value == 0) {
851        // Simplify 0 + b = b, 0 * b = 0.
852        if (op == kAdd) {
853          return b;
854        } else if (op == kMul) {
855          return a;
856        }
857      } else if (op == kMul) {
858        // Simplify 1 * b = b, -1 * b = -b
859        if (value == 1) {
860          return b;
861        } else if (value == -1) {
862          return CreateSimplifiedInvariant(kNeg, nullptr, b);
863        }
864      }
865    }
866    if (IsExact(b, &value)) {
867      if (value == 0) {
868        // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, -0 = 0.
869        if (op == kAdd || op == kSub) {
870          return a;
871        } else if (op == kMul || op == kNeg) {
872          return b;
873        }
874      } else if (op == kMul || op == kDiv) {
875        // Simplify a * 1 = a, a / 1 = a, a * -1 = -a, a / -1 = -a
876        if (value == 1) {
877          return a;
878        } else if (value == -1) {
879          return CreateSimplifiedInvariant(kNeg, nullptr, a);
880        }
881      }
882    } else if (b->operation == kNeg) {
883      // Simplify a + (-b) = a - b, a - (-b) = a + b, -(-b) = b.
884      if (op == kAdd) {
885        return CreateSimplifiedInvariant(kSub, a, b->op_b);
886      } else if (op == kSub) {
887        return CreateSimplifiedInvariant(kAdd, a, b->op_b);
888      } else if (op == kNeg) {
889        return b->op_b;
890      }
891    } else if (b->operation == kSub) {
892      // Simplify - (a - b) = b - a.
893      if (op == kNeg) {
894        return CreateSimplifiedInvariant(kSub, b->op_b, b->op_a);
895      }
896    }
897    return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, b->type);
898  }
899  
IsExact(InductionInfo * info,int64_t * value)900  bool HInductionVarAnalysis::IsExact(InductionInfo* info, int64_t* value) {
901    return InductionVarRange(this).IsConstant(info, InductionVarRange::kExact, value);
902  }
903  
IsAtMost(InductionInfo * info,int64_t * value)904  bool HInductionVarAnalysis::IsAtMost(InductionInfo* info, int64_t* value) {
905    return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtMost, value);
906  }
907  
IsAtLeast(InductionInfo * info,int64_t * value)908  bool HInductionVarAnalysis::IsAtLeast(InductionInfo* info, int64_t* value) {
909    return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtLeast, value);
910  }
911  
InductionEqual(InductionInfo * info1,InductionInfo * info2)912  bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
913                                             InductionInfo* info2) {
914    // Test structural equality only, without accounting for simplifications.
915    if (info1 != nullptr && info2 != nullptr) {
916      return
917          info1->induction_class == info2->induction_class &&
918          info1->operation       == info2->operation       &&
919          info1->fetch           == info2->fetch           &&
920          info1->type            == info2->type            &&
921          InductionEqual(info1->op_a, info2->op_a)         &&
922          InductionEqual(info1->op_b, info2->op_b);
923    }
924    // Otherwise only two nullptrs are considered equal.
925    return info1 == info2;
926  }
927  
InductionToString(InductionInfo * info)928  std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
929    if (info != nullptr) {
930      if (info->induction_class == kInvariant) {
931        std::string inv = "(";
932        inv += InductionToString(info->op_a);
933        switch (info->operation) {
934          case kNop:   inv += " @ ";  break;
935          case kAdd:   inv += " + ";  break;
936          case kSub:
937          case kNeg:   inv += " - ";  break;
938          case kMul:   inv += " * ";  break;
939          case kDiv:   inv += " / ";  break;
940          case kLT:    inv += " < ";  break;
941          case kLE:    inv += " <= "; break;
942          case kGT:    inv += " > ";  break;
943          case kGE:    inv += " >= "; break;
944          case kFetch:
945            DCHECK(info->fetch);
946            if (info->fetch->IsIntConstant()) {
947              inv += std::to_string(info->fetch->AsIntConstant()->GetValue());
948            } else if (info->fetch->IsLongConstant()) {
949              inv += std::to_string(info->fetch->AsLongConstant()->GetValue());
950            } else {
951              inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName();
952            }
953            break;
954          case kTripCountInLoop:       inv += " (TC-loop) ";        break;
955          case kTripCountInBody:       inv += " (TC-body) ";        break;
956          case kTripCountInLoopUnsafe: inv += " (TC-loop-unsafe) "; break;
957          case kTripCountInBodyUnsafe: inv += " (TC-body-unsafe) "; break;
958        }
959        inv += InductionToString(info->op_b);
960        inv += ")";
961        return inv;
962      } else {
963        DCHECK(info->operation == kNop);
964        if (info->induction_class == kLinear) {
965          return "(" + InductionToString(info->op_a) + " * i + " +
966                       InductionToString(info->op_b) + "):" +
967                       Primitive::PrettyDescriptor(info->type);
968        } else if (info->induction_class == kWrapAround) {
969          return "wrap(" + InductionToString(info->op_a) + ", " +
970                           InductionToString(info->op_b) + "):" +
971                           Primitive::PrettyDescriptor(info->type);
972        } else if (info->induction_class == kPeriodic) {
973          return "periodic(" + InductionToString(info->op_a) + ", " +
974                               InductionToString(info->op_b) + "):" +
975                               Primitive::PrettyDescriptor(info->type);
976        }
977      }
978    }
979    return "";
980  }
981  
982  }  // namespace art
983