Merge "Finalized all components of range analysis needed for dynamic bce."

4 files changed, 426 insertions, 123 deletions

diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index bcc32403d3..cca0baf274 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1169,8 +1169,10 @@ class BCEVisitor : public HGraphVisitor {
   // Return the range resulting from induction variable analysis of "instruction" when the value
   // is used from "context", for example, an index used from a bounds-check inside a loop body.
   ValueRange* LookupInductionRange(HInstruction* context, HInstruction* instruction) {
-    InductionVarRange::Value v1 = induction_range_.GetMinInduction(context, instruction);
-    InductionVarRange::Value v2 = induction_range_.GetMaxInduction(context, instruction);
+    InductionVarRange::Value v1;
+    InductionVarRange::Value v2;
+    bool needs_finite_test = false;
+    induction_range_.GetInductionRange(context, instruction, &v1, &v2, &needs_finite_test);
     if (v1.is_known && (v1.a_constant == 0 || v1.a_constant == 1) &&
         v2.is_known && (v2.a_constant == 0 || v2.a_constant == 1)) {
       DCHECK(v1.a_constant == 1 || v1.instruction == nullptr);
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 5530d261d2..b40ef5aa41 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -75,10 +75,12 @@ static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v) {
   return v;
 }
 
-static HInstruction* Insert(HBasicBlock* preheader, HInstruction* instruction) {
-  DCHECK(preheader != nullptr);
+/** Helper method to insert an instruction. */
+static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) {
+  DCHECK(block != nullptr);
+  DCHECK(block->GetLastInstruction() != nullptr) << block->GetBlockId();
   DCHECK(instruction != nullptr);
-  preheader->InsertInstructionBefore(instruction, preheader->GetLastInstruction());
+  block->InsertInstructionBefore(instruction, block->GetLastInstruction());
   return instruction;
 }
 
@@ -91,48 +93,98 @@ InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis)
   DCHECK(induction_analysis != nullptr);
 }
 
-InductionVarRange::Value InductionVarRange::GetMinInduction(HInstruction* context,
-                                                            HInstruction* instruction) {
-  return GetInduction(context, instruction, /* is_min */ true);
-}
-
-InductionVarRange::Value InductionVarRange::GetMaxInduction(HInstruction* context,
-                                                            HInstruction* instruction) {
-  return SimplifyMax(GetInduction(context, instruction, /* is_min */ false));
+void InductionVarRange::GetInductionRange(HInstruction* context,
+                                          HInstruction* instruction,
+                                          /*out*/Value* min_val,
+                                          /*out*/Value* max_val,
+                                          /*out*/bool* needs_finite_test) {
+  HLoopInformation* loop = context->GetBlock()->GetLoopInformation();  // closest enveloping loop
+  if (loop != nullptr) {
+    // Set up loop information.
+    HBasicBlock* header = loop->GetHeader();
+    bool in_body = context->GetBlock() != header;
+    HInductionVarAnalysis::InductionInfo* info =
+        induction_analysis_->LookupInfo(loop, instruction);
+    HInductionVarAnalysis::InductionInfo* trip =
+        induction_analysis_->LookupInfo(loop, header->GetLastInstruction());
+    // Find range.
+    *min_val = GetVal(info, trip, in_body, /* is_min */ true);
+    *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min */ false));
+    *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip);
+  } else {
+    // No loop to analyze.
+    *min_val = Value();
+    *max_val = Value();
+    *needs_finite_test = false;
+  }
 }
 
 bool InductionVarRange::CanGenerateCode(HInstruction* context,
                                         HInstruction* instruction,
-                                        /*out*/bool* top_test) {
-  return GenerateCode(context, instruction, nullptr, nullptr, nullptr, nullptr, top_test);
+                                        /*out*/bool* needs_finite_test,
+                                        /*out*/bool* needs_taken_test) {
+  return GenerateCode(context,
+                      instruction,
+                      nullptr, nullptr, nullptr, nullptr, nullptr,  // nothing generated yet
+                      needs_finite_test,
+                      needs_taken_test);
 }
 
-bool InductionVarRange::GenerateCode(HInstruction* context,
-                                     HInstruction* instruction,
-                                     HGraph* graph,
-                                     HBasicBlock* block,
-                                     /*out*/HInstruction** lower,
-                                     /*out*/HInstruction** upper) {
-  return GenerateCode(context, instruction, graph, block, lower, upper, nullptr);
+void InductionVarRange::GenerateRangeCode(HInstruction* context,
+                                          HInstruction* instruction,
+                                          HGraph* graph,
+                                          HBasicBlock* block,
+                                          /*out*/HInstruction** lower,
+                                          /*out*/HInstruction** upper) {
+  bool b1, b2;  // unused
+  if (!GenerateCode(context, instruction, graph, block, lower, upper, nullptr, &b1, &b2)) {
+    LOG(FATAL) << "Failed precondition: GenerateCode()";
+  }
+}
+
+void InductionVarRange::GenerateTakenTest(HInstruction* context,
+                                          HGraph* graph,
+                                          HBasicBlock* block,
+                                          /*out*/HInstruction** taken_test) {
+  bool b1, b2;  // unused
+  if (!GenerateCode(context, context, graph, block, nullptr, nullptr, taken_test, &b1, &b2)) {
+    LOG(FATAL) << "Failed precondition: GenerateCode()";
+  }
 }
 
 //
 // Private class methods.
 //
 
-InductionVarRange::Value InductionVarRange::GetInduction(HInstruction* context,
-                                                         HInstruction* instruction,
-                                                         bool is_min) {
-  HLoopInformation* loop = context->GetBlock()->GetLoopInformation();  // closest enveloping loop
-  if (loop != nullptr) {
-    HBasicBlock* header = loop->GetHeader();
-    bool in_body = context->GetBlock() != header;
-    return GetVal(induction_analysis_->LookupInfo(loop, instruction),
-                  induction_analysis_->LookupInfo(loop, header->GetLastInstruction()),
-                  in_body,
-                  is_min);
+bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) {
+  if (info != nullptr) {
+    if (info->induction_class == HInductionVarAnalysis::kLinear) {
+      return true;
+    } else if (info->induction_class == HInductionVarAnalysis::kWrapAround) {
+      return NeedsTripCount(info->op_b);
+    }
   }
-  return Value();
+  return false;
+}
+
+bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) {
+  if (trip != nullptr) {
+    if (trip->induction_class == HInductionVarAnalysis::kInvariant) {
+      return trip->operation == HInductionVarAnalysis::kTripCountInBody ||
+             trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe;
+    }
+  }
+  return false;
+}
+
+bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) {
+  if (trip != nullptr) {
+    if (trip->induction_class == HInductionVarAnalysis::kInvariant) {
+      return trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe ||
+             trip->operation == HInductionVarAnalysis::kTripCountInLoopUnsafe;
+    }
+  }
+  return false;
 }
 
 InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
@@ -184,11 +236,13 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct
           case HInductionVarAnalysis::kFetch:
             return GetFetch(info->fetch, trip, in_body, is_min);
           case HInductionVarAnalysis::kTripCountInLoop:
+          case HInductionVarAnalysis::kTripCountInLoopUnsafe:
             if (!in_body && !is_min) {  // one extra!
               return GetVal(info->op_a, trip, in_body, is_min);
             }
             FALLTHROUGH_INTENDED;
           case HInductionVarAnalysis::kTripCountInBody:
+          case HInductionVarAnalysis::kTripCountInBodyUnsafe:
             if (is_min) {
               return Value(0);
             } else if (in_body) {
@@ -356,25 +410,42 @@ bool InductionVarRange::GenerateCode(HInstruction* context,
                                      HBasicBlock* block,
                                      /*out*/HInstruction** lower,
                                      /*out*/HInstruction** upper,
-                                     /*out*/bool* top_test) {
+                                     /*out*/HInstruction** taken_test,
+                                     /*out*/bool* needs_finite_test,
+                                     /*out*/bool* needs_taken_test) {
   HLoopInformation* loop = context->GetBlock()->GetLoopInformation();  // closest enveloping loop
   if (loop != nullptr) {
+    // Set up loop information.
     HBasicBlock* header = loop->GetHeader();
     bool in_body = context->GetBlock() != header;
-    HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction);
+    HInductionVarAnalysis::InductionInfo* info =
+        induction_analysis_->LookupInfo(loop, instruction);
+    if (info == nullptr) {
+      return false;  // nothing to analyze
+    }
     HInductionVarAnalysis::InductionInfo* trip =
         induction_analysis_->LookupInfo(loop, header->GetLastInstruction());
-    if (info != nullptr && trip != nullptr) {
-      if (top_test != nullptr) {
-        *top_test = trip->operation != HInductionVarAnalysis::kTripCountInLoop;
+    // Determine what tests are needed.
+    *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip);
+    *needs_taken_test = NeedsTripCount(info) && IsBodyTripCount(trip);
+    // Code generation for taken test: generate the code when requested or otherwise analyze
+    // if code generation is feasible when taken test is needed.
+    if (taken_test != nullptr) {
+      return GenerateCode(
+          trip->op_b, nullptr, graph, block, taken_test, in_body, /* is_min */ false);
+    } else if (*needs_taken_test) {
+      if (!GenerateCode(
+          trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min */ false)) {
+        return false;
       }
-      return
+    }
+    // Code generation for lower and upper.
+    return
         // Success on lower if invariant (not set), or code can be generated.
         ((info->induction_class == HInductionVarAnalysis::kInvariant) ||
             GenerateCode(info, trip, graph, block, lower, in_body, /* is_min */ true)) &&
         // And success on upper.
         GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ false);
-    }
   }
   return false;
 }
@@ -387,19 +458,38 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
                                      bool in_body,
                                      bool is_min) {
   if (info != nullptr) {
+    // Handle current operation.
     Primitive::Type type = Primitive::kPrimInt;
     HInstruction* opa = nullptr;
     HInstruction* opb = nullptr;
-    int32_t value = 0;
     switch (info->induction_class) {
       case HInductionVarAnalysis::kInvariant:
         // Invariants.
         switch (info->operation) {
           case HInductionVarAnalysis::kAdd:
+          case HInductionVarAnalysis::kLT:
+          case HInductionVarAnalysis::kLE:
+          case HInductionVarAnalysis::kGT:
+          case HInductionVarAnalysis::kGE:
             if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) &&
                 GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
               if (graph != nullptr) {
-                *result = Insert(block, new (graph->GetArena()) HAdd(type, opa, opb));
+                HInstruction* operation = nullptr;
+                switch (info->operation) {
+                  case HInductionVarAnalysis::kAdd:
+                    operation = new (graph->GetArena()) HAdd(type, opa, opb); break;
+                  case HInductionVarAnalysis::kLT:
+                    operation = new (graph->GetArena()) HLessThan(opa, opb); break;
+                  case HInductionVarAnalysis::kLE:
+                    operation = new (graph->GetArena()) HLessThanOrEqual(opa, opb); break;
+                  case HInductionVarAnalysis::kGT:
+                    operation = new (graph->GetArena()) HGreaterThan(opa, opb); break;
+                  case HInductionVarAnalysis::kGE:
+                    operation = new (graph->GetArena()) HGreaterThanOrEqual(opa, opb); break;
+                  default:
+                    LOG(FATAL) << "unknown operation";
+                }
+                *result = Insert(block, operation);
               }
               return true;
             }
@@ -427,11 +517,13 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
             }
             return true;
           case HInductionVarAnalysis::kTripCountInLoop:
+          case HInductionVarAnalysis::kTripCountInLoopUnsafe:
             if (!in_body && !is_min) {  // one extra!
               return GenerateCode(info->op_a, trip, graph, block, result, in_body, is_min);
             }
             FALLTHROUGH_INTENDED;
           case HInductionVarAnalysis::kTripCountInBody:
+          case HInductionVarAnalysis::kTripCountInBodyUnsafe:
             if (is_min) {
               if (graph != nullptr) {
                 *result = graph->GetIntConstant(0);
@@ -452,23 +544,31 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
             break;
         }
         break;
-      case HInductionVarAnalysis::kLinear:
-        // Linear induction a * i + b, for normalized 0 <= i < TC. Restrict to unit stride only
-        // to avoid arithmetic wrap-around situations that are hard to guard against.
-        if (GetConstant(info->op_a, &value)) {
-          if (value == 1 || value == -1) {
-            const bool is_min_a = value == 1 ? is_min : !is_min;
-            if (GenerateCode(trip,       trip, graph, block, &opa, in_body, is_min_a) &&
-                GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
-              if (graph != nullptr) {
-                *result = Insert(block, new (graph->GetArena()) HAdd(type, opa, opb));
+      case HInductionVarAnalysis::kLinear: {
+          // Linear induction a * i + b, for normalized 0 <= i < TC. Restrict to unit stride only
+          // to avoid arithmetic wrap-around situations that are hard to guard against.
+          int32_t stride_value = 0;
+          if (GetConstant(info->op_a, &stride_value)) {
+            if (stride_value == 1 || stride_value == -1) {
+              const bool is_min_a = stride_value == 1 ? is_min : !is_min;
+              if (GenerateCode(trip,       trip, graph, block, &opa, in_body, is_min_a) &&
+                  GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
+                if (graph != nullptr) {
+                  HInstruction* oper;
+                  if (stride_value == 1) {
+                    oper = new (graph->GetArena()) HAdd(type, opa, opb);
+                  } else {
+                    oper = new (graph->GetArena()) HSub(type, opb, opa);
+                  }
+                  *result = Insert(block, oper);
+                }
+                return true;
               }
-              return true;
             }
           }
         }
         break;
-      default:  // TODO(ajcbik): add more cases
+      default:
         break;
     }
   }
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 7fa5a26dce..7984871b08 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -57,29 +57,33 @@ class InductionVarRange {
   explicit InductionVarRange(HInductionVarAnalysis* induction);
 
   /**
-   * Given a context denoted by the first instruction, returns a,
-   * possibly conservative, lower bound on the instruction's value.
+   * Given a context denoted by the first instruction, returns a possibly conservative
+   * lower and upper bound on the instruction's value in the output parameters min_val
+   * and max_val, respectively. The need_finite_test flag denotes if an additional finite-test
+   * is needed to protect the range evaluation inside its loop.
    */
-  Value GetMinInduction(HInstruction* context, HInstruction* instruction);
+  void GetInductionRange(HInstruction* context,
+                         HInstruction* instruction,
+                         /*out*/Value* min_val,
+                         /*out*/Value* max_val,
+                         /*out*/bool* needs_finite_test);
 
   /**
-   * Given a context denoted by the first instruction, returns a,
-   * possibly conservative, upper bound on the instruction's value.
+   * Returns true if range analysis is able to generate code for the lower and upper
+   * bound expressions on the instruction in the given context. The need_finite_test
+   * and need_taken test flags denote if an additional finite-test and/or taken-test
+   * are needed to protect the range evaluation inside its loop.
    */
-  Value GetMaxInduction(HInstruction* context, HInstruction* instruction);
-
-  /**
-   * Returns true if range analysis is able to generate code for the lower and upper bound
-   * expressions on the instruction in the given context. Output parameter top_test denotes
-   * whether a top test is needed to protect the trip-count expression evaluation.
-   */
-  bool CanGenerateCode(HInstruction* context, HInstruction* instruction, /*out*/bool* top_test);
+  bool CanGenerateCode(HInstruction* context,
+                       HInstruction* instruction,
+                       /*out*/bool* needs_finite_test,
+                       /*out*/bool* needs_taken_test);
 
   /**
    * Generates the actual code in the HIR for the lower and upper bound expressions on the
    * instruction in the given context. Code for the lower and upper bound expression are
-   * generated in given block and graph and are returned in lower and upper, respectively.
-   * For a loop invariant, lower is not set.
+   * generated in given block and graph and are returned in the output parameters lower and
+   * upper, respectively. For a loop invariant, lower is not set.
    *
    * For example, given expression x+i with range [0, 5] for i, calling this method
    * will generate the following sequence:
@@ -87,20 +91,35 @@ class InductionVarRange {
    * block:
    *   lower: add x, 0
    *   upper: add x, 5
+   *
+   * Precondition: CanGenerateCode() returns true.
    */
-  bool GenerateCode(HInstruction* context,
-                    HInstruction* instruction,
-                    HGraph* graph,
-                    HBasicBlock* block,
-                    /*out*/HInstruction** lower,
-                    /*out*/HInstruction** upper);
+  void GenerateRangeCode(HInstruction* context,
+                         HInstruction* instruction,
+                         HGraph* graph,
+                         HBasicBlock* block,
+                         /*out*/HInstruction** lower,
+                         /*out*/HInstruction** upper);
+
+  /**
+   * Generates explicit taken-test for the loop in the given context. Code is generated in
+   * given block and graph. The taken-test is returned in parameter test.
+   *
+   * Precondition: CanGenerateCode() returns true and needs_taken_test is set.
+   */
+  void GenerateTakenTest(HInstruction* context,
+                         HGraph* graph,
+                         HBasicBlock* block,
+                         /*out*/HInstruction** taken_test);
 
  private:
   //
   // Private helper methods.
   //
 
-  Value GetInduction(HInstruction* context, HInstruction* instruction, bool is_min);
+  static bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info);
+  static bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip);
+  static bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip);
 
   static Value GetFetch(HInstruction* instruction,
                         HInductionVarAnalysis::InductionInfo* trip,
@@ -130,8 +149,8 @@ class InductionVarRange {
   static Value MergeVal(Value v1, Value v2, bool is_min);
 
   /**
-   * Generates code for lower/upper expression in the HIR. Returns true on success.
-   * With graph == nullptr, the method can be used to determine if code generation
+   * Generates code for lower/upper/taken-test in the HIR. Returns true on success.
+   * With values nullptr, the method can be used to determine if code generation
    * would be successful without generating actual code yet.
    */
   bool GenerateCode(HInstruction* context,
@@ -140,7 +159,9 @@ class InductionVarRange {
                     HBasicBlock* block,
                     /*out*/HInstruction** lower,
                     /*out*/HInstruction** upper,
-                    bool* top_test);
+                    /*out*/HInstruction** taken_test,
+                    /*out*/bool* needs_finite_test,
+                    /*out*/bool* needs_taken_test);
 
   static bool GenerateCode(HInductionVarAnalysis::InductionInfo* info,
                            HInductionVarAnalysis::InductionInfo* trip,
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index ce8926ad72..fda5153d43 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -46,6 +46,10 @@ class InductionVarRangeTest : public testing::Test {
     EXPECT_EQ(v1.is_known, v2.is_known);
   }
 
+  //
+  // Construction methods.
+  //
+
   /** Constructs bare minimum graph. */
   void BuildGraph() {
     graph_->SetNumberOfVRegs(1);
@@ -58,7 +62,7 @@ class InductionVarRangeTest : public testing::Test {
   }
 
   /** Constructs loop with given upper bound. */
-  void BuildLoop(HInstruction* upper) {
+  void BuildLoop(int32_t lower, HInstruction* upper, int32_t stride) {
     // Control flow.
     loop_preheader_ = new (&allocator_) HBasicBlock(graph_);
     graph_->AddBlock(loop_preheader_);
@@ -75,18 +79,22 @@ class InductionVarRangeTest : public testing::Test {
     HLocal* induc = new (&allocator_) HLocal(0);
     entry_block_->AddInstruction(induc);
     loop_preheader_->AddInstruction(
-        new (&allocator_) HStoreLocal(induc, graph_->GetIntConstant(0)));  // i = 0
+        new (&allocator_) HStoreLocal(induc, graph_->GetIntConstant(lower)));  // i = l
     loop_preheader_->AddInstruction(new (&allocator_) HGoto());
     HInstruction* load = new (&allocator_) HLoadLocal(induc, Primitive::kPrimInt);
           loop_header->AddInstruction(load);
-    condition_ = new (&allocator_) HLessThan(load, upper);
+    if (stride > 0) {
+      condition_ = new (&allocator_) HLessThan(load, upper);  // i < u
+    } else {
+      condition_ = new (&allocator_) HGreaterThan(load, upper);  // i > u
+    }
     loop_header->AddInstruction(condition_);
-    loop_header->AddInstruction(new (&allocator_) HIf(condition_));  // i < u
+    loop_header->AddInstruction(new (&allocator_) HIf(condition_));
     load = new (&allocator_) HLoadLocal(induc, Primitive::kPrimInt);
     loop_body->AddInstruction(load);
-    increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, load, graph_->GetIntConstant(1));
+    increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, load, graph_->GetIntConstant(stride));
     loop_body->AddInstruction(increment_);
-    loop_body->AddInstruction(new (&allocator_) HStoreLocal(induc, increment_));  // i++
+    loop_body->AddInstruction(new (&allocator_) HStoreLocal(induc, increment_));  // i += s
     loop_body->AddInstruction(new (&allocator_) HGoto());
     exit_block_->AddInstruction(new (&allocator_) HReturnVoid());
   }
@@ -124,8 +132,20 @@ class InductionVarRangeTest : public testing::Test {
   }
 
   /** Constructs a trip-count. */
-  HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc) {
-    return iva_->CreateTripCount(HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc), nullptr);
+  HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc, bool in_loop, bool safe) {
+    if (in_loop && safe) {
+      return iva_->CreateTripCount(
+          HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc), nullptr);
+    } else if (in_loop) {
+      return iva_->CreateTripCount(
+          HInductionVarAnalysis::kTripCountInLoopUnsafe, CreateConst(tc), nullptr);
+    } else if (safe) {
+      return iva_->CreateTripCount(
+          HInductionVarAnalysis::kTripCountInBody, CreateConst(tc), nullptr);
+    } else {
+      return iva_->CreateTripCount(
+          HInductionVarAnalysis::kTripCountInBodyUnsafe, CreateConst(tc), nullptr);
+    }
   }
 
   /** Constructs a linear a * i + b induction. */
@@ -139,16 +159,34 @@ class InductionVarRangeTest : public testing::Test {
         HInductionVarAnalysis::kPeriodic, CreateConst(lo), CreateConst(hi));
   }
 
+  /** Constructs a wrap-around induction consisting of a constant, followed info */
+  HInductionVarAnalysis::InductionInfo* CreateWrapAround(
+      int32_t initial,
+      HInductionVarAnalysis::InductionInfo* info) {
+    return iva_->CreateInduction(HInductionVarAnalysis::kWrapAround, CreateConst(initial), info);
+  }
+
   /** Constructs a wrap-around induction consisting of a constant, followed by a range. */
   HInductionVarAnalysis::InductionInfo* CreateWrapAround(int32_t initial, int32_t lo, int32_t hi) {
-    return iva_->CreateInduction(
-        HInductionVarAnalysis::kWrapAround, CreateConst(initial), CreateRange(lo, hi));
+    return CreateWrapAround(initial, CreateRange(lo, hi));
   }
 
   //
   // Relay methods.
   //
 
+  bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) {
+    return InductionVarRange::NeedsTripCount(info);
+  }
+
+  bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) {
+    return InductionVarRange::IsBodyTripCount(trip);
+  }
+
+  bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) {
+    return InductionVarRange::IsUnsafeTripCount(trip);
+  }
+
   Value GetMin(HInductionVarAnalysis::InductionInfo* info,
                HInductionVarAnalysis::InductionInfo* induc) {
     return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ true);
@@ -202,6 +240,26 @@ class InductionVarRangeTest : public testing::Test {
 // Tests on static methods.
 //
 
+TEST_F(InductionVarRangeTest, TripCountProperties) {
+  EXPECT_FALSE(NeedsTripCount(nullptr));
+  EXPECT_FALSE(NeedsTripCount(CreateConst(1)));
+  EXPECT_TRUE(NeedsTripCount(CreateLinear(1, 1)));
+  EXPECT_FALSE(NeedsTripCount(CreateWrapAround(1, 2, 3)));
+  EXPECT_TRUE(NeedsTripCount(CreateWrapAround(1, CreateLinear(1, 1))));
+
+  EXPECT_FALSE(IsBodyTripCount(nullptr));
+  EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, true)));
+  EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, false)));
+  EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, true)));
+  EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, false)));
+
+  EXPECT_FALSE(IsUnsafeTripCount(nullptr));
+  EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, true, true)));
+  EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, true, false)));
+  EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, false, true)));
+  EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, false, false)));
+}
+
 TEST_F(InductionVarRangeTest, GetMinMaxNull) {
   ExpectEqual(Value(), GetMin(nullptr, nullptr));
   ExpectEqual(Value(), GetMax(nullptr, nullptr));
@@ -279,10 +337,10 @@ TEST_F(InductionVarRangeTest, GetMinMaxFetch) {
 }
 
 TEST_F(InductionVarRangeTest, GetMinMaxLinear) {
-  ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100)));
-  ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100)));
-  ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100)));
-  ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100)));
+  ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100, true, true)));
+  ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100, true, true)));
+  ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100, true, true)));
+  ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100, true, true)));
 }
 
 TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) {
@@ -398,61 +456,98 @@ TEST_F(InductionVarRangeTest, MaxValue) {
 // Tests on instance methods.
 //
 
-TEST_F(InductionVarRangeTest, FindRangeConstantTripCount) {
-  BuildLoop(graph_->GetIntConstant(1000));
+TEST_F(InductionVarRangeTest, ConstantTripCountUp) {
+  BuildLoop(0, graph_->GetIntConstant(1000), 1);
   PerformInductionVarAnalysis();
   InductionVarRange range(iva_);
 
+  Value v1, v2;
+  bool needs_finite_test = true;
+
   // In context of header: known.
-  ExpectEqual(Value(0), range.GetMinInduction(condition_, condition_->InputAt(0)));
-  ExpectEqual(Value(1000), range.GetMaxInduction(condition_, condition_->InputAt(0)));
+  range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(0), v1);
+  ExpectEqual(Value(1000), v2);
 
   // In context of loop-body: known.
-  ExpectEqual(Value(0), range.GetMinInduction(increment_, condition_->InputAt(0)));
-  ExpectEqual(Value(999), range.GetMaxInduction(increment_, condition_->InputAt(0)));
-  ExpectEqual(Value(1), range.GetMinInduction(increment_, increment_));
-  ExpectEqual(Value(1000), range.GetMaxInduction(increment_, increment_));
+  range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(0), v1);
+  ExpectEqual(Value(999), v2);
+  range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(1), v1);
+  ExpectEqual(Value(1000), v2);
 }
 
-TEST_F(InductionVarRangeTest, FindRangeSymbolicTripCount) {
-  HInstruction* parameter = new (&allocator_) HParameterValue(
-      graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
-  entry_block_->AddInstruction(parameter);
-  BuildLoop(parameter);
+TEST_F(InductionVarRangeTest, ConstantTripCountDown) {
+  BuildLoop(1000, graph_->GetIntConstant(0), -1);
   PerformInductionVarAnalysis();
   InductionVarRange range(iva_);
 
-  // In context of header: full range unknown.
-  ExpectEqual(Value(0), range.GetMinInduction(condition_, condition_->InputAt(0)));
-  ExpectEqual(Value(), range.GetMaxInduction(condition_, condition_->InputAt(0)));
+  Value v1, v2;
+  bool needs_finite_test = true;
+
+  // In context of header: known.
+  range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(0), v1);
+  ExpectEqual(Value(1000), v2);
 
   // In context of loop-body: known.
-  ExpectEqual(Value(0), range.GetMinInduction(increment_, condition_->InputAt(0)));
-  ExpectEqual(Value(parameter, 1, -1), range.GetMaxInduction(increment_, condition_->InputAt(0)));
-  ExpectEqual(Value(1), range.GetMinInduction(increment_, increment_));
-  ExpectEqual(Value(parameter, 1, 0), range.GetMaxInduction(increment_, increment_));
+  range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(1), v1);
+  ExpectEqual(Value(1000), v2);
+  range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(0), v1);
+  ExpectEqual(Value(999), v2);
 }
 
-TEST_F(InductionVarRangeTest, CodeGeneration) {
+TEST_F(InductionVarRangeTest, SymbolicTripCountUp) {
   HInstruction* parameter = new (&allocator_) HParameterValue(
       graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
   entry_block_->AddInstruction(parameter);
-  BuildLoop(parameter);
+  BuildLoop(0, parameter, 1);
   PerformInductionVarAnalysis();
   InductionVarRange range(iva_);
 
+  Value v1, v2;
+  bool needs_finite_test = true;
+  bool needs_taken_test = true;
+
+  // In context of header: upper unknown.
+  range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(0), v1);
+  ExpectEqual(Value(), v2);
+
+  // In context of loop-body: known.
+  range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(0), v1);
+  ExpectEqual(Value(parameter, 1, -1), v2);
+  range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(1), v1);
+  ExpectEqual(Value(parameter, 1, 0), v2);
+
   HInstruction* lower = nullptr;
   HInstruction* upper = nullptr;
-  bool top_test = false;
+  HInstruction* taken = nullptr;
 
   // Can generate code in context of loop-body only.
-  EXPECT_FALSE(range.CanGenerateCode(condition_, condition_->InputAt(0), &top_test));
-  ASSERT_TRUE(range.CanGenerateCode(increment_, condition_->InputAt(0), &top_test));
-  EXPECT_TRUE(top_test);
+  EXPECT_FALSE(range.CanGenerateCode(
+      condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
+  ASSERT_TRUE(range.CanGenerateCode(
+      increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
+  EXPECT_FALSE(needs_finite_test);
+  EXPECT_TRUE(needs_taken_test);
 
   // Generates code.
-  EXPECT_TRUE(range.GenerateCode(
-      increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper));
+  range.GenerateRangeCode(increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper);
 
   // Verify lower is 0+0.
   ASSERT_TRUE(lower != nullptr);
@@ -462,7 +557,7 @@ TEST_F(InductionVarRangeTest, CodeGeneration) {
   ASSERT_TRUE(lower->InputAt(1)->IsIntConstant());
   EXPECT_EQ(0, lower->InputAt(1)->AsIntConstant()->GetValue());
 
-  // Verify upper is (V-1)+0
+  // Verify upper is (V-1)+0.
   ASSERT_TRUE(upper != nullptr);
   ASSERT_TRUE(upper->IsAdd());
   ASSERT_TRUE(upper->InputAt(0)->IsSub());
@@ -471,6 +566,91 @@ TEST_F(InductionVarRangeTest, CodeGeneration) {
   EXPECT_EQ(1, upper->InputAt(0)->InputAt(1)->AsIntConstant()->GetValue());
   ASSERT_TRUE(upper->InputAt(1)->IsIntConstant());
   EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue());
+
+  // Verify taken-test is 0<V.
+  range.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
+  ASSERT_TRUE(taken != nullptr);
+  ASSERT_TRUE(taken->IsLessThan());
+  ASSERT_TRUE(taken->InputAt(0)->IsIntConstant());
+  EXPECT_EQ(0, taken->InputAt(0)->AsIntConstant()->GetValue());
+  EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
+}
+
+TEST_F(InductionVarRangeTest, SymbolicTripCountDown) {
+  HInstruction* parameter = new (&allocator_) HParameterValue(
+      graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
+  entry_block_->AddInstruction(parameter);
+  BuildLoop(1000, parameter, -1);
+  PerformInductionVarAnalysis();
+  InductionVarRange range(iva_);
+
+  Value v1, v2;
+  bool needs_finite_test = true;
+  bool needs_taken_test = true;
+
+  // In context of header: lower unknown.
+  range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(), v1);
+  ExpectEqual(Value(1000), v2);
+
+  // In context of loop-body: known.
+  range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(parameter, 1, 1), v1);
+  ExpectEqual(Value(1000), v2);
+  range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+  EXPECT_FALSE(needs_finite_test);
+  ExpectEqual(Value(parameter, 1, 0), v1);
+  ExpectEqual(Value(999), v2);
+
+  HInstruction* lower = nullptr;
+  HInstruction* upper = nullptr;
+  HInstruction* taken = nullptr;
+
+  // Can generate code in context of loop-body only.
+  EXPECT_FALSE(range.CanGenerateCode(
+      condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
+  ASSERT_TRUE(range.CanGenerateCode(
+      increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
+  EXPECT_FALSE(needs_finite_test);
+  EXPECT_TRUE(needs_taken_test);
+
+  // Generates code.
+  range.GenerateRangeCode(increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper);
+
+  // Verify lower is 1000-(-(V-1000)-1).
+  ASSERT_TRUE(lower != nullptr);
+  ASSERT_TRUE(lower->IsSub());
+  ASSERT_TRUE(lower->InputAt(0)->IsIntConstant());
+  EXPECT_EQ(1000, lower->InputAt(0)->AsIntConstant()->GetValue());
+  lower = lower->InputAt(1);
+  ASSERT_TRUE(lower->IsSub());
+  ASSERT_TRUE(lower->InputAt(1)->IsIntConstant());
+  EXPECT_EQ(1, lower->InputAt(1)->AsIntConstant()->GetValue());
+  lower = lower->InputAt(0);
+  ASSERT_TRUE(lower->IsNeg());
+  lower = lower->InputAt(0);
+  ASSERT_TRUE(lower->IsSub());
+  EXPECT_TRUE(lower->InputAt(0)->IsParameterValue());
+  ASSERT_TRUE(lower->InputAt(1)->IsIntConstant());
+  EXPECT_EQ(1000, lower->InputAt(1)->AsIntConstant()->GetValue());
+
+  // Verify upper is 1000-0.
+  ASSERT_TRUE(upper != nullptr);
+  ASSERT_TRUE(upper->IsSub());
+  ASSERT_TRUE(upper->InputAt(0)->IsIntConstant());
+  EXPECT_EQ(1000, upper->InputAt(0)->AsIntConstant()->GetValue());
+  ASSERT_TRUE(upper->InputAt(1)->IsIntConstant());
+  EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue());
+
+  // Verify taken-test is 1000>V.
+  range.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
+  ASSERT_TRUE(taken != nullptr);
+  ASSERT_TRUE(taken->IsGreaterThan());
+  ASSERT_TRUE(taken->InputAt(0)->IsIntConstant());
+  EXPECT_EQ(1000, taken->InputAt(0)->AsIntConstant()->GetValue());
+  EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
 }
 
 }  // namespace art