commit 0d345cf8db01f40db250f80de5104e0df24234fa
author Aart Bik <ajcbik@google.com> Wed Mar 16 10:49:38 2016 -0700
committer Aart Bik <ajcbik@google.com> Mon Mar 21 12:53:33 2016 -0700
tree ebeac7adff399e908e5dcd3c855505ed02fe72b8
parent 4485c6964ad414d5c6d0535622cfad1c0a6b640f

Generalize induction and range analysis across type conversions.

Rationale:
This changelist implements allowing narrowing conversions within
inductions and loop control. More induction and loops recognized,
more bounds eliminated. We all win. The basic idea is pretty simple
(record type with detected induction) but one has to get all the
details right, as illustrated by the many new unit tests.

BUG=27151098

Change-Id: I254020bfa5fa623799b31bbbb5ccc97d4d5a0100

compiler/optimizing/induction_var_analysis.h

diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 94d2646..f1965f0 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -97,17 +97,20 @@
                   InductionOp op,
                   InductionInfo* a,
                   InductionInfo* b,
-                  HInstruction* f)
+                  HInstruction* f,
+                  Primitive::Type t)
         : induction_class(ic),
           operation(op),
           op_a(a),
           op_b(b),
-          fetch(f) {}
+          fetch(f),
+          type(t) {}
     InductionClass induction_class;
     InductionOp operation;
     InductionInfo* op_a;
     InductionInfo* op_b;
     HInstruction* fetch;
+    Primitive::Type type;  // precision of induction
   };
 
   bool IsVisitedNode(HInstruction* instruction) const {
@@ -121,17 +124,24 @@
 
   InductionInfo* CreateInvariantFetch(HInstruction* f) {
     DCHECK(f != nullptr);
-    return new (graph_->GetArena()) InductionInfo(kInvariant, kFetch, nullptr, nullptr, f);
+    return new (graph_->GetArena())
+        InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType());
   }
 
-  InductionInfo* CreateTripCount(InductionOp op, InductionInfo* a, InductionInfo* b) {
+  InductionInfo* CreateTripCount(InductionOp op,
+                                 InductionInfo* a,
+                                 InductionInfo* b,
+                                 Primitive::Type type) {
     DCHECK(a != nullptr);
-    return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr);
+    return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, type);
   }
 
-  InductionInfo* CreateInduction(InductionClass ic, InductionInfo* a, InductionInfo* b) {
+  InductionInfo* CreateInduction(InductionClass ic,
+                                 InductionInfo* a,
+                                 InductionInfo* b,
+                                 Primitive::Type type) {
     DCHECK(a != nullptr && b != nullptr);
-    return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr);
+    return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr, type);
   }
 
   // Methods for analysis.
@@ -148,6 +158,7 @@
   InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
   InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type);
   InductionInfo* TransferNeg(InductionInfo* a);
+  InductionInfo* TransferCnv(InductionInfo* a, Primitive::Type from, Primitive::Type to);
 
   // Solvers.
   InductionInfo* SolvePhi(HInstruction* phi, size_t input_index);
@@ -161,6 +172,7 @@
                              HInstruction* y,
                              InductionOp op,
                              bool is_first_call);
+  InductionInfo* SolveCnv(HTypeConversion* conversion);
 
   // Trip count information.
   void VisitControl(HLoopInformation* loop);
@@ -181,6 +193,11 @@
                 int64_t stride_value,
                 Primitive::Type type,
                 IfCondition cmp);
+  bool FitsNarrowerControl(InductionInfo* lower_expr,
+                           InductionInfo* upper_expr,
+                           int64_t stride_value,
+                           Primitive::Type type,
+                           IfCondition cmp);
 
   // Assign and lookup.
   void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
@@ -205,6 +222,7 @@
   ArenaVector<HInstruction*> scc_;
   ArenaSafeMap<HInstruction*, NodeInfo> map_;
   ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
+  Primitive::Type type_;
 
   /**
    * Maintains the results of the analysis as a mapping from loops to a mapping from instructions