Use range analysis for better trip count analysis

Rationale:
Marking more loops as always-taken avoids generating
unnecessary new top tests while marking more loops
are non-infinite enables more optimizations. This
CL helps with these improvements. Also, some more
code is shared between induction and range analysis
and a bug with refining ranges has been fixed.

Bug: 27151190

Change-Id: Iecc0d7f32ae4779ee5424cda9dcc20816220935e
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 37f2d79..a1e1cde 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -379,7 +379,7 @@
Primitive::Type type) {
// Transfer over a shift left: treat shift by restricted constant as equivalent multiplication.
int64_t value = -1;
-  if (a != nullptr && IsIntAndGet(b, &value)) {
+  if (a != nullptr && IsExact(b, &value)) {
// Obtain the constant needed for the multiplication. This yields an existing instruction
// if the constants is already there. Otherwise, this has a side effect on the HIR.
// The restriction on the shift factor avoids generating a negative constant
@@ -546,9 +546,10 @@
// Analyze condition with induction at left-hand-side (e.g. i < U).
InductionInfo* lower_expr = a->op_b;
InductionInfo* upper_expr = b;
-    InductionInfo* stride = a->op_a;
+    InductionInfo* stride_expr = a->op_a;
+    // Constant stride?
int64_t stride_value = 0;
-    if (!IsIntAndGet(stride, &stride_value)) {
+    if (!IsExact(stride_expr, &stride_value)) {
return;
}
// Rewrite condition i != U into i < U or i > U if end condition is reached exactly.
@@ -561,7 +562,7 @@
//   stride < 0, either i > U or i >= U
if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
(stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
-      VisitTripCount(loop, lower_expr, upper_expr, stride, stride_value, type, cmp);
+      VisitTripCount(loop, lower_expr, upper_expr, stride_expr, stride_value, type, cmp);
}
}
}
@@ -569,7 +570,7 @@
void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop,
InductionInfo* lower_expr,
InductionInfo* upper_expr,
-                                           InductionInfo* stride,
+                                           InductionInfo* stride_expr,
int64_t stride_value,
Primitive::Type type,
IfCondition cmp) {
@@ -612,9 +613,10 @@
trip_count = CreateInvariantOp(kAdd, trip_count, CreateConstant(1, type));
}
// Compensate for stride.
-    trip_count = CreateInvariantOp(kAdd, trip_count, stride);
+    trip_count = CreateInvariantOp(kAdd, trip_count, stride_expr);
}
-  trip_count = CreateInvariantOp(kDiv, CreateInvariantOp(kSub, trip_count, lower_expr), stride);
+  trip_count = CreateInvariantOp(
+      kDiv, CreateInvariantOp(kSub, trip_count, lower_expr), stride_expr);
// Assign the trip-count expression to the loop control. Clients that use the information
// should be aware that the expression is only valid under the conditions listed above.
InductionOp tcKind = kTripCountInBodyUnsafe;  // needs both tests
@@ -644,14 +646,25 @@
IfCondition cmp) {
int64_t lower_value;
int64_t upper_value;
-  if (IsIntAndGet(lower_expr, &lower_value) && IsIntAndGet(upper_expr, &upper_value)) {
-    switch (cmp) {
-      case kCondLT: return lower_value <  upper_value;
-      case kCondLE: return lower_value <= upper_value;
-      case kCondGT: return lower_value >  upper_value;
-      case kCondGE: return lower_value >= upper_value;
-      default:      LOG(FATAL) << "CONDITION UNREACHABLE";
-    }
+  switch (cmp) {
+    case kCondLT:
+      return IsAtMost(lower_expr, &lower_value)
+          && IsAtLeast(upper_expr, &upper_value)
+          && lower_value < upper_value;
+    case kCondLE:
+      return IsAtMost(lower_expr, &lower_value)
+          && IsAtLeast(upper_expr, &upper_value)
+          && lower_value <= upper_value;
+    case kCondGT:
+      return IsAtLeast(lower_expr, &lower_value)
+          && IsAtMost(upper_expr, &upper_value)
+          && lower_value > upper_value;
+    case kCondGE:
+      return IsAtLeast(lower_expr, &lower_value)
+          && IsAtMost(upper_expr, &upper_value)
+          && lower_value >= upper_value;
+    default:
+      LOG(FATAL) << "CONDITION UNREACHABLE";
}
return false;  // not certain, may be untaken
}
@@ -660,25 +673,23 @@
int64_t stride_value,
Primitive::Type type,
IfCondition cmp) {
-  const int64_t min = type == Primitive::kPrimInt
-      ? std::numeric_limits<int32_t>::min()
-      : std::numeric_limits<int64_t>::min();
-  const int64_t max = type == Primitive::kPrimInt
-        ? std::numeric_limits<int32_t>::max()
-        : std::numeric_limits<int64_t>::max();
+  const int64_t min = type == Primitive::kPrimInt ? std::numeric_limits<int32_t>::min()
+                                                  : std::numeric_limits<int64_t>::min();
+  const int64_t max = type == Primitive::kPrimInt ? std::numeric_limits<int32_t>::max()
+                                                  : std::numeric_limits<int64_t>::max();
// Some rules under which it is certain at compile-time that the loop is finite.
int64_t value;
switch (cmp) {
case kCondLT:
return stride_value == 1 ||
-          (IsIntAndGet(upper_expr, &value) && value <= (max - stride_value + 1));
+          (IsAtMost(upper_expr, &value) && value <= (max - stride_value + 1));
case kCondLE:
-      return (IsIntAndGet(upper_expr, &value) && value <= (max - stride_value));
+      return (IsAtMost(upper_expr, &value) && value <= (max - stride_value));
case kCondGT:
return stride_value == -1 ||
-          (IsIntAndGet(upper_expr, &value) && value >= (min - stride_value - 1));
+          (IsAtLeast(upper_expr, &value) && value >= (min - stride_value - 1));
case kCondGE:
-      return (IsIntAndGet(upper_expr, &value) && value >= (min - stride_value));
+      return (IsAtLeast(upper_expr, &value) && value >= (min - stride_value));
default:
LOG(FATAL) << "CONDITION UNREACHABLE";
}
@@ -733,7 +744,7 @@
// More exhaustive simplifications are done by later phases once induction nodes are
// translated back into HIR code (e.g. by loop optimizations or BCE).
int64_t value = -1;
-  if (IsIntAndGet(a, &value)) {
+  if (IsExact(a, &value)) {
if (value == 0) {
// Simplify 0 + b = b, 0 * b = 0.
if (op == kAdd) {
@@ -750,7 +761,7 @@
}
}
}
-  if (IsIntAndGet(b, &value)) {
+  if (IsExact(b, &value)) {
if (value == 0) {
// Simplify a + 0 = a, a - 0 = a, a * 0 = 0, -0 = 0.
if (op == kAdd || op == kSub) {
@@ -784,29 +795,16 @@
return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr);
}

-bool HInductionVarAnalysis::IsIntAndGet(InductionInfo* info, int64_t* value) {
-  if (info != nullptr && info->induction_class == kInvariant) {
-    // A direct constant fetch.
-    if (info->operation == kFetch) {
-      DCHECK(info->fetch);
-      if (info->fetch->IsIntConstant()) {
-        *value = info->fetch->AsIntConstant()->GetValue();
-        return true;
-      } else if (info->fetch->IsLongConstant()) {
-        *value = info->fetch->AsLongConstant()->GetValue();
-        return true;
-      }
-    }
-    // Use range analysis to resolve compound values.
-    InductionVarRange range(this);
-    int32_t min_val = 0;
-    int32_t max_val = 0;
-    if (range.IsConstantRange(info, &min_val, &max_val) && min_val == max_val) {
-      *value = min_val;
-      return true;
-    }
-  }
-  return false;
+bool HInductionVarAnalysis::IsExact(InductionInfo* info, int64_t* value) {
+  return InductionVarRange(this).IsConstant(info, InductionVarRange::kExact, value);
+}
+
+bool HInductionVarAnalysis::IsAtMost(InductionInfo* info, int64_t* value) {
+  return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtMost, value);
+}
+
+bool HInductionVarAnalysis::IsAtLeast(InductionInfo* info, int64_t* value) {
+  return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtLeast, value);
}

bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 84d5d82..94d2646 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -189,7 +189,9 @@
InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);

// Constants.
-  bool IsIntAndGet(InductionInfo* info, int64_t* value);
+  bool IsExact(InductionInfo* info, /*out*/ int64_t* value);
+  bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value);
+  bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value);

// Helpers.
static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 9566c29..b162696 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -45,17 +45,14 @@
return c2 != 0 && CanLongValueFitIntoInt(static_cast<int64_t>(c1) / static_cast<int64_t>(c2));
}

-/** Returns true for 32/64-bit integral constant. */
-static bool IsIntAndGet(HInstruction* instruction, int32_t* value) {
+/** Returns true for 32/64-bit constant instruction. */
+static bool IsIntAndGet(HInstruction* instruction, int64_t* value) {
if (instruction->IsIntConstant()) {
*value = instruction->AsIntConstant()->GetValue();
return true;
} else if (instruction->IsLongConstant()) {
-    const int64_t c = instruction->AsLongConstant()->GetValue();
-    if (CanLongValueFitIntoInt(c)) {
-      *value = static_cast<int32_t>(c);
-      return true;
-    }
+    *value = instruction->AsLongConstant()->GetValue();
+    return true;
}
return false;
}
@@ -65,8 +62,9 @@
* because length >= 0 is true. This makes it more likely the bound is useful to clients.
*/
static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v) {
-  int32_t value;
-  if (v.a_constant > 1 &&
+  int64_t value;
+  if (v.is_known &&
+      v.a_constant > 1 &&
v.instruction->IsDiv() &&
v.instruction->InputAt(0)->IsArrayLength() &&
IsIntAndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) {
@@ -75,6 +73,16 @@
return v;
}

+/** Helper method to test for a constant value. */
+static bool IsConstantValue(InductionVarRange::Value v) {
+  return v.is_known && v.a_constant == 0;
+}
+
+/** Helper method to test for same constant value. */
+static bool IsSameConstantValue(InductionVarRange::Value v1, InductionVarRange::Value v2) {
+  return IsConstantValue(v1) && IsConstantValue(v2) && v1.b_constant == v2.b_constant;
+}
+
/** Helper method to insert an instruction. */
static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) {
DCHECK(block != nullptr);
@@ -99,29 +107,45 @@
/*out*/Value* max_val,
/*out*/bool* needs_finite_test) {
HLoopInformation* loop = context->GetBlock()->GetLoopInformation();  // closest enveloping loop
-  if (loop != nullptr) {
-    // Set up loop information.
-    bool in_body = context->GetBlock() != header;
-    HInductionVarAnalysis::InductionInfo* info =
-        induction_analysis_->LookupInfo(loop, instruction);
-    HInductionVarAnalysis::InductionInfo* trip =
-    // 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);
-    return true;
+  if (loop == nullptr) {
+    return false;  // no loop
}
-  return false;  // Nothing known
+  HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction);
+  if (info == nullptr) {
+    return false;  // no induction information
+  }
+  // Set up loop information.
+  bool in_body = context->GetBlock() != header;
+  HInductionVarAnalysis::InductionInfo* trip =
+  // 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);
+  return true;
}

-bool InductionVarRange::RefineOuter(/*in-out*/Value* min_val, /*in-out*/Value* max_val) const {
-  Value v1 = RefineOuter(*min_val, /* is_min */ true);
-  Value v2 = RefineOuter(*max_val, /* is_min */ false);
-  if (v1.instruction != min_val->instruction || v2.instruction != max_val->instruction) {
-    *min_val = v1;
-    *max_val = v2;
+bool InductionVarRange::RefineOuter(/*in-out*/ Value* min_val,
+                                    /*in-out*/ Value* max_val) const {
+  Value v1_min = RefineOuter(*min_val, /* is_min */ true);
+  Value v2_max = RefineOuter(*max_val, /* is_min */ false);
+  // The refined range is safe if both sides refine the same instruction. Otherwise, since two
+  // different ranges are combined, the new refined range is safe to pass back to the client if
+  // the extremes of the computed ranges ensure no arithmetic wrap-around anomalies occur.
+  if (min_val->instruction != max_val->instruction) {
+    Value v1_max = RefineOuter(*min_val, /* is_min */ false);
+    Value v2_min = RefineOuter(*max_val, /* is_min */ true);
+    if (!IsConstantValue(v1_max) ||
+        !IsConstantValue(v2_min) ||
+        v1_max.b_constant > v2_min.b_constant) {
+      return false;
+    }
+  }
+  // Did something change?
+  if (v1_min.instruction != min_val->instruction || v2_max.instruction != max_val->instruction) {
+    *min_val = v1_min;
+    *max_val = v2_max;
return true;
}
return false;
@@ -164,6 +188,38 @@
// Private class methods.
//

+bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info,
+                                   ConstantRequest request,
+                                   /*out*/ int64_t *value) const {
+  if (info != nullptr) {
+    // A direct 32-bit or 64-bit constant fetch. This immediately satisfies
+    // any of the three requests (kExact, kAtMost, and KAtLeast).
+    if (info->induction_class == HInductionVarAnalysis::kInvariant &&
+        info->operation == HInductionVarAnalysis::kFetch) {
+      if (IsIntAndGet(info->fetch, value)) {
+        return true;
+      }
+    }
+    // Try range analysis while traversing outward on loops.
+    bool in_body = true;  // no known trip count
+    Value v_min = GetVal(info, nullptr, in_body, /* is_min */ true);
+    Value v_max = GetVal(info, nullptr, in_body, /* is_min */ false);
+    do {
+      // Make sure *both* extremes are known to avoid arithmetic wrap-around anomalies.
+      if (IsConstantValue(v_min) && IsConstantValue(v_max) && v_min.b_constant <= v_max.b_constant) {
+        if ((request == kExact && v_min.b_constant == v_max.b_constant) || request == kAtMost) {
+          *value = v_max.b_constant;
+          return true;
+        } else if (request == kAtLeast) {
+          *value = v_min.b_constant;
+          return true;
+        }
+      }
+    } while (RefineOuter(&v_min, &v_max));
+  }
+  return false;
+}
+
bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const {
if (info != nullptr) {
if (info->induction_class == HInductionVarAnalysis::kLinear) {
@@ -206,12 +262,10 @@
if (trip != nullptr) {
HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a;
if (trip_expr->operation == HInductionVarAnalysis::kSub) {
-      int32_t min_value = 0;
-      int32_t stride_value = 0;
-      if (IsConstantRange(info->op_a, &min_value, &stride_value) && min_value == stride_value) {
+      int64_t stride_value = 0;
+      if (IsConstant(info->op_a, kExact, &stride_value)) {
if (!is_min && stride_value == 1) {
-          // Test original trip's negative operand (trip_expr->op_b) against
-          // the offset of the linear induction.
+          // Test original trip's negative operand (trip_expr->op_b) against offset of induction.
if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) {
// Analyze cancelled trip with just the positive operand (trip_expr->op_a).
HInductionVarAnalysis::InductionInfo cancelled_trip(
@@ -219,8 +273,7 @@
return GetVal(&cancelled_trip, trip, in_body, is_min);
}
} else if (is_min && stride_value == -1) {
-          // Test original trip's positive operand (trip_expr->op_a) against
-          // the offset of the linear induction.
+          // Test original trip's positive operand (trip_expr->op_a) against offset of induction.
if (HInductionVarAnalysis::InductionEqual(trip_expr->op_a, info->op_b)) {
// Analyze cancelled trip with just the negative operand (trip_expr->op_b).
HInductionVarAnalysis::InductionInfo neg(
@@ -248,14 +301,16 @@
bool is_min) const {
// Detect constants and chase the fetch a bit deeper into the HIR tree, so that it becomes
// more likely range analysis will compare the same instructions as terminal nodes.
-  int32_t value;
-  if (IsIntAndGet(instruction, &value)) {
-    return Value(value);
+  int64_t value;
+  if (IsIntAndGet(instruction, &value) && CanLongValueFitIntoInt(value))  {
+    return Value(static_cast<int32_t>(value));
} else if (instruction->IsAdd()) {
-    if (IsIntAndGet(instruction->InputAt(0), &value)) {
-      return AddValue(Value(value), GetFetch(instruction->InputAt(1), trip, in_body, is_min));
-    } else if (IsIntAndGet(instruction->InputAt(1), &value)) {
-      return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), Value(value));
+    if (IsIntAndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) {
+                      GetFetch(instruction->InputAt(1), trip, in_body, is_min));
+    } else if (IsIntAndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) {
+      return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min),
+                      Value(static_cast<int32_t>(value)));
}
} else if (instruction->IsArrayLength() && instruction->InputAt(0)->IsNewArray()) {
return GetFetch(instruction->InputAt(0)->InputAt(0), trip, in_body, is_min);
@@ -331,29 +386,30 @@
Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false);
Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true);
Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false);
-  // Try to refine certain failure.
-  if (v1_min.a_constant && v1_max.a_constant) {
-    v1_min = RefineOuter(v1_min, /* is_min */ true);
-    v1_max = RefineOuter(v1_max, /* is_min */ false);
+  // Try to refine first operand.
+  if (!IsConstantValue(v1_min) && !IsConstantValue(v1_max)) {
+    RefineOuter(&v1_min, &v1_max);
}
-  // Positive or negative range?
-  if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant >= 0) {
-    // Positive range vs. positive or negative range.
-    if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
-      return is_min ? MulValue(v1_min, v2_min)
-                    : MulValue(v1_max, v2_max);
-    } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
-      return is_min ? MulValue(v1_max, v2_min)
-                    : MulValue(v1_min, v2_max);
+  // Constant times range.
+  if (IsSameConstantValue(v1_min, v1_max)) {
+    return MulRangeAndConstant(v2_min, v2_max, v1_min, is_min);
+  } else if (IsSameConstantValue(v2_min, v2_max)) {
+    return MulRangeAndConstant(v1_min, v1_max, v2_min, is_min);
+  }
+  // Positive range vs. positive or negative range.
+  if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) {
+    if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
+      return is_min ? MulValue(v1_min, v2_min) : MulValue(v1_max, v2_max);
+    } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
+      return is_min ? MulValue(v1_max, v2_min) : MulValue(v1_min, v2_max);
}
-  } else if (v1_max.is_known && v1_max.a_constant == 0 && v1_max.b_constant <= 0) {
-    // Negative range vs. positive or negative range.
-    if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
-      return is_min ? MulValue(v1_min, v2_max)
-                    : MulValue(v1_max, v2_min);
-    } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
-      return is_min ? MulValue(v1_max, v2_max)
-                    : MulValue(v1_min, v2_min);
+  }
+  // Negative range vs. positive or negative range.
+  if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) {
+    if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
+      return is_min ? MulValue(v1_min, v2_max) : MulValue(v1_max, v2_min);
+    } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
+      return is_min ? MulValue(v1_max, v2_max) : MulValue(v1_min, v2_min);
}
}
return Value();
@@ -368,43 +424,41 @@
Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false);
Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true);
Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false);
-  // Positive or negative range?
-  if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant >= 0) {
-    // Positive range vs. positive or negative range.
-    if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
-      return is_min ? DivValue(v1_min, v2_max)
-                    : DivValue(v1_max, v2_min);
-    } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
-      return is_min ? DivValue(v1_max, v2_max)
-                    : DivValue(v1_min, v2_min);
+  // Range divided by constant.
+  if (IsSameConstantValue(v2_min, v2_max)) {
+    return DivRangeAndConstant(v1_min, v1_max, v2_min, is_min);
+  }
+  // Positive range vs. positive or negative range.
+  if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) {
+    if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
+      return is_min ? DivValue(v1_min, v2_max) : DivValue(v1_max, v2_min);
+    } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
+      return is_min ? DivValue(v1_max, v2_max) : DivValue(v1_min, v2_min);
}
-  } else if (v1_max.is_known && v1_max.a_constant == 0 && v1_max.b_constant <= 0) {
-    // Negative range vs. positive or negative range.
-    if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
-      return is_min ? DivValue(v1_min, v2_min)
-                    : DivValue(v1_max, v2_max);
-    } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
-      return is_min ? DivValue(v1_max, v2_min)
-                    : DivValue(v1_min, v2_max);
+  }
+  // Negative range vs. positive or negative range.
+  if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) {
+    if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
+      return is_min ? DivValue(v1_min, v2_min) : DivValue(v1_max, v2_max);
+    } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
+      return is_min ? DivValue(v1_max, v2_min) : DivValue(v1_min, v2_max);
}
}
return Value();
}

-bool InductionVarRange::IsConstantRange(HInductionVarAnalysis::InductionInfo* info,
-                                        int32_t *min_value,
-                                        int32_t *max_value) const {
-  bool in_body = true;  // no known trip count
-  Value v_min = GetVal(info, nullptr, in_body, /* is_min */ true);
-  Value v_max = GetVal(info, nullptr, in_body, /* is_min */ false);
-  do {
-    if (v_min.is_known && v_min.a_constant == 0 && v_max.is_known && v_max.a_constant == 0) {
-      *min_value = v_min.b_constant;
-      *max_value = v_max.b_constant;
-      return true;
-    }
-  } while (RefineOuter(&v_min, &v_max));
-  return false;
+InductionVarRange::Value InductionVarRange::MulRangeAndConstant(Value v_min,
+                                                                Value v_max,
+                                                                Value c,
+                                                                bool is_min) const {
+  return is_min == (c.b_constant >= 0) ? MulValue(v_min, c) : MulValue(v_max, c);
+}
+
+InductionVarRange::Value InductionVarRange::DivRangeAndConstant(Value v_min,
+                                                                Value v_max,
+                                                                Value c,
+                                                                bool is_min) const {
+  return is_min == (c.b_constant >= 0) ? DivValue(v_min, c) : DivValue(v_max, c);
}

InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const {
@@ -471,22 +525,25 @@
}

InductionVarRange::Value InductionVarRange::RefineOuter(Value v, bool is_min) const {
-  if (v.instruction != nullptr) {
-    HLoopInformation* loop =
-        v.instruction->GetBlock()->GetLoopInformation();  // closest enveloping loop
-    if (loop != nullptr) {
-      // Set up loop information.
-      bool in_body = true;  // use is always in body of outer loop
-      HInductionVarAnalysis::InductionInfo* info =
-          induction_analysis_->LookupInfo(loop, v.instruction);
-      HInductionVarAnalysis::InductionInfo* trip =
-      // Try to refine "a x instruction + b" with outer loop range information on instruction.
-      return AddValue(MulValue(Value(v.a_constant), GetVal(info, trip, in_body, is_min)),
-                      Value(v.b_constant));
-    }
+  if (v.instruction == nullptr) {
+    return v;  // nothing to refine
}
-  return v;
+  HLoopInformation* loop =
+      v.instruction->GetBlock()->GetLoopInformation();  // closest enveloping loop
+  if (loop == nullptr) {
+    return v;  // no loop
+  }
+  HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, v.instruction);
+  if (info == nullptr) {
+    return v;  // no induction information
+  }
+  // Set up loop information.
+  bool in_body = true;  // inner always in more outer
+  HInductionVarAnalysis::InductionInfo* trip =
+  // Try to refine "a x instruction + b" with outer loop range information on instruction.
+  return AddValue(MulValue(Value(v.a_constant), GetVal(info, trip, in_body, is_min)), Value(v.b_constant));
}

bool InductionVarRange::GenerateCode(HInstruction* context,
@@ -499,44 +556,45 @@
/*out*/bool* needs_finite_test,
/*out*/bool* needs_taken_test) const {
HLoopInformation* loop = context->GetBlock()->GetLoopInformation();  // closest enveloping loop
-  if (loop != nullptr) {
-    // Set up loop information.
-    bool in_body = context->GetBlock() != header;
-    HInductionVarAnalysis::InductionInfo* info =
-        induction_analysis_->LookupInfo(loop, instruction);
-    if (info == nullptr) {
-      return false;  // nothing to analyze
-    }
-    HInductionVarAnalysis::InductionInfo* trip =
-    // Determine what tests are needed. A finite test is needed if the evaluation code uses the
-    // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot"
-    // the computed range). A taken test is needed for any unknown trip-count, even if evaluation
-    // code does not use the trip-count explicitly (since there could be an implicit relation
-    // between e.g. an invariant subscript and a not-taken condition).
-    *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip);
-    *needs_taken_test = 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;
-      }
-    }
-    // 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);
+  if (loop == nullptr) {
+    return false;  // no loop
}
-  return false;
+  HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction);
+  if (info == nullptr) {
+    return false;  // no induction information
+  }
+  // Set up loop information.
+  bool in_body = context->GetBlock() != header;
+  HInductionVarAnalysis::InductionInfo* trip =
+  if (trip == nullptr) {
+    return false;  // codegen relies on trip count
+  }
+  // Determine what tests are needed. A finite test is needed if the evaluation code uses the
+  // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot"
+  // the computed range). A taken test is needed for any unknown trip-count, even if evaluation
+  // code does not use the trip-count explicitly (since there could be an implicit relation
+  // between e.g. an invariant subscript and a not-taken condition).
+  *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip);
+  *needs_taken_test = 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;
+    }
+  }
+  // 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);
}

bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
@@ -639,9 +697,8 @@
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 min_value = 0;
-        int32_t stride_value = 0;
-        if (IsConstantRange(info->op_a, &min_value, &stride_value) && min_value == stride_value) {
+        int64_t stride_value = 0;
+        if (IsConstant(info->op_a, kExact, &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) &&
@@ -666,7 +723,7 @@
// Wrap-around and periodic inductions are restricted to constants only, so that extreme
// values are easy to test at runtime without complications of arithmetic wrap-around.
Value extreme = GetVal(info, trip, in_body, is_min);
-        if (extreme.is_known && extreme.a_constant == 0) {
+        if (IsConstantValue(extreme)) {
if (graph != nullptr) {
*result = graph->GetIntConstant(extreme.b_constant);
}
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 3cb7b4b..0af4156 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -69,7 +69,8 @@
/*out*/ bool* needs_finite_test);

/** Refines the values with induction of next outer loop. Returns true on change. */
-  bool RefineOuter(/*in-out*/Value* min_val, /*in-out*/Value* max_val) const;
+  bool RefineOuter(/*in-out*/ Value* min_val,
+                   /*in-out*/ Value* max_val) const;

/**
* Returns true if range analysis is able to generate code for the lower and upper
@@ -116,6 +117,23 @@
/*out*/ HInstruction** taken_test);

private:
+  /*
+   * Enum used in IsConstant() request.
+   */
+  enum ConstantRequest {
+    kExact,
+    kAtMost,
+    kAtLeast
+  };
+
+  /**
+   * Returns true if exact or upper/lower bound on the given induction
+   * information is known as a 64-bit constant, which is returned in value.
+   */
+  bool IsConstant(HInductionVarAnalysis::InductionInfo* info,
+                  ConstantRequest request,
+                  /*out*/ int64_t *value) const;
+
bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const;
bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
@@ -143,9 +161,8 @@
bool in_body,
bool is_min) const;

-  bool IsConstantRange(HInductionVarAnalysis::InductionInfo* info,
-                       int32_t *min_value,
-                       int32_t *max_value) const;
+  Value MulRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const;
+  Value DivRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const;

Value AddValue(Value v1, Value v2) const;
Value SubValue(Value v1, Value v2) const;
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index 55a654e..c5c33bd 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -215,10 +215,16 @@
return range_.GetDiv(info1, info2, nullptr, /* in_body */ true, is_min);
}

-  bool IsConstantRange(HInductionVarAnalysis::InductionInfo* info,
-                       int32_t* min_value,
-                       int32_t* max_value) {
-    return range_.IsConstantRange(info, min_value, max_value);
+  bool IsExact(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
+    return range_.IsConstant(info, InductionVarRange::kExact, value);
+  }
+
+  bool IsAtMost(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
+    return range_.IsConstant(info, InductionVarRange::kAtMost, value);
+  }
+
+  bool IsAtLeast(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
+    return range_.IsConstant(info, InductionVarRange::kAtLeast, value);
}

Value AddValue(Value v1, Value v2) { return range_.AddValue(v1, v2); }
@@ -249,6 +255,34 @@
// Tests on private methods.
//

+TEST_F(InductionVarRangeTest, IsConstant) {
+  int64_t value;
+  // Constant.
+  EXPECT_TRUE(IsExact(CreateConst(12345), &value));
+  EXPECT_EQ(12345, value);
+  EXPECT_TRUE(IsAtMost(CreateConst(12345), &value));
+  EXPECT_EQ(12345, value);
+  EXPECT_TRUE(IsAtLeast(CreateConst(12345), &value));
+  EXPECT_EQ(12345, value);
+  // Constant trivial range.
+  EXPECT_TRUE(IsExact(CreateRange(111, 111), &value));
+  EXPECT_EQ(111, value);
+  EXPECT_TRUE(IsAtMost(CreateRange(111, 111), &value));
+  EXPECT_EQ(111, value);
+  EXPECT_TRUE(IsAtLeast(CreateRange(111, 111), &value));
+  EXPECT_EQ(111, value);
+  // Constant non-trivial range.
+  EXPECT_FALSE(IsExact(CreateRange(11, 22), &value));
+  EXPECT_TRUE(IsAtMost(CreateRange(11, 22), &value));
+  EXPECT_EQ(22, value);
+  EXPECT_TRUE(IsAtLeast(CreateRange(11, 22), &value));
+  EXPECT_EQ(11, value);
+  // Symbolic.
+  EXPECT_FALSE(IsExact(CreateFetch(x_), &value));
+  EXPECT_FALSE(IsAtMost(CreateFetch(x_), &value));
+  EXPECT_FALSE(IsAtLeast(CreateFetch(x_), &value));
+}
+
TEST_F(InductionVarRangeTest, TripCountProperties) {
EXPECT_FALSE(NeedsTripCount(nullptr));
EXPECT_FALSE(NeedsTripCount(CreateConst(1)));
@@ -367,6 +401,10 @@
}

TEST_F(InductionVarRangeTest, GetMulMin) {
+  ExpectEqual(Value(-14), GetMul(CreateConst(2), CreateRange(-7, 8), true));
+  ExpectEqual(Value(-16), GetMul(CreateConst(-2), CreateRange(-7, 8), true));
+  ExpectEqual(Value(-14), GetMul(CreateRange(-7, 8), CreateConst(2), true));
+  ExpectEqual(Value(-16), GetMul(CreateRange(-7, 8), CreateConst(-2), true));
ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true));
ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true));
ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), true));
@@ -379,6 +417,10 @@
}

TEST_F(InductionVarRangeTest, GetMulMax) {
+  ExpectEqual(Value(16), GetMul(CreateConst(2), CreateRange(-7, 8), false));
+  ExpectEqual(Value(14), GetMul(CreateConst(-2), CreateRange(-7, 8), false));
+  ExpectEqual(Value(16), GetMul(CreateRange(-7, 8), CreateConst(2), false));
+  ExpectEqual(Value(14), GetMul(CreateRange(-7, 8), CreateConst(-2), false));
ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false));
ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false));
ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), false));
@@ -391,6 +433,8 @@
}

TEST_F(InductionVarRangeTest, GetDivMin) {
+  ExpectEqual(Value(-5), GetDiv(CreateRange(-10, 20), CreateConst(2), true));
+  ExpectEqual(Value(-10), GetDiv(CreateRange(-10, 20), CreateConst(-2), true));
ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true));
ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true));
ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), true));
@@ -403,6 +447,8 @@
}

TEST_F(InductionVarRangeTest, GetDivMax) {
+  ExpectEqual(Value(10), GetDiv(CreateRange(-10, 20), CreateConst(2), false));
+  ExpectEqual(Value(5), GetDiv(CreateRange(-10, 20), CreateConst(-2), false));
ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false));
ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false));
ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), false));
@@ -414,18 +460,6 @@
ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false));
}

-TEST_F(InductionVarRangeTest, IsConstantRange) {
-  int32_t min_value;
-  int32_t max_value;
-  ASSERT_TRUE(IsConstantRange(CreateConst(12345), &min_value, &max_value));
-  EXPECT_EQ(12345, min_value);
-  EXPECT_EQ(12345, max_value);
-  ASSERT_TRUE(IsConstantRange(CreateRange(1, 2), &min_value, &max_value));
-  EXPECT_EQ(1, min_value);
-  EXPECT_EQ(2, max_value);
-  EXPECT_FALSE(IsConstantRange(CreateFetch(x_), &min_value, &max_value));
-}
-
ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1)));
@@ -459,6 +493,24 @@
ExpectEqual(Value(), MulValue(Value(90000), Value(-90000)));  // unsafe
}

+TEST_F(InductionVarRangeTest, MulValueSpecial) {
+  const int32_t min_value = std::numeric_limits<int32_t>::min();
+  const int32_t max_value = std::numeric_limits<int32_t>::max();
+
+  // Unsafe.
+  ExpectEqual(Value(), MulValue(Value(min_value), Value(min_value)));
+  ExpectEqual(Value(), MulValue(Value(min_value), Value(-1)));
+  ExpectEqual(Value(), MulValue(Value(min_value), Value(max_value)));
+  ExpectEqual(Value(), MulValue(Value(max_value), Value(max_value)));
+
+  // Safe.
+  ExpectEqual(Value(min_value), MulValue(Value(min_value), Value(1)));
+  ExpectEqual(Value(max_value), MulValue(Value(max_value), Value(1)));
+  ExpectEqual(Value(-max_value), MulValue(Value(max_value), Value(-1)));
+  ExpectEqual(Value(-1), MulValue(Value(1), Value(-1)));
+  ExpectEqual(Value(1), MulValue(Value(-1), Value(-1)));
+}
+
TEST_F(InductionVarRangeTest, DivValue) {
ExpectEqual(Value(25), DivValue(Value(100), Value(4)));
ExpectEqual(Value(), DivValue(Value(x_, 1, -4), Value(x_, 1, -1)));
@@ -468,6 +520,23 @@
ExpectEqual(Value(), DivValue(Value(1), Value(0)));  // unsafe
}

+TEST_F(InductionVarRangeTest, DivValueSpecial) {
+  const int32_t min_value = std::numeric_limits<int32_t>::min();
+  const int32_t max_value = std::numeric_limits<int32_t>::max();
+
+  // Unsafe.
+  ExpectEqual(Value(), DivValue(Value(min_value), Value(-1)));
+
+  // Safe.
+  ExpectEqual(Value(1), DivValue(Value(min_value), Value(min_value)));
+  ExpectEqual(Value(1), DivValue(Value(max_value), Value(max_value)));
+  ExpectEqual(Value(min_value), DivValue(Value(min_value), Value(1)));
+  ExpectEqual(Value(max_value), DivValue(Value(max_value), Value(1)));
+  ExpectEqual(Value(-max_value), DivValue(Value(max_value), Value(-1)));
+  ExpectEqual(Value(-1), DivValue(Value(1), Value(-1)));
+  ExpectEqual(Value(1), DivValue(Value(-1), Value(-1)));
+}
+
TEST_F(InductionVarRangeTest, MinValue) {
ExpectEqual(Value(10), MinValue(Value(10), Value(100)));
ExpectEqual(Value(x_, 1, -4), MinValue(Value(x_, 1, -4), Value(x_, 1, -1)));
diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java
index deff279..9f344dd 100644
--- a/test/530-checker-loops/src/Main.java
+++ b/test/530-checker-loops/src/Main.java
@@ -471,7 +471,7 @@
//
/// CHECK-START: void Main.linearTriangularOnTwoArrayLengths(int) BCE (after)
/// CHECK-NOT: BoundsCheck
-  /// CHECK-NOT: Deoptimize
+  //  TODO: also CHECK-NOT: Deoptimize, see b/27151190
private static void linearTriangularOnTwoArrayLengths(int n) {
int[] a = new int[n];
for (int i = 0; i < a.length; i++) {
@@ -513,7 +513,7 @@
//
/// CHECK-START: void Main.linearTriangularOnParameter(int) BCE (after)
/// CHECK-NOT: BoundsCheck
-  /// CHECK-NOT: Deoptimize
+  //  TODO: also CHECK-NOT: Deoptimize, see b/27151190
private static void linearTriangularOnParameter(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
@@ -528,22 +528,22 @@
}
}

-  /// CHECK-START: void Main.linearTriangularVariations(int) BCE (before)
+  /// CHECK-START: void Main.linearTriangularVariationsInnerStrict(int) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: BoundsCheck
//
-  /// CHECK-START: void Main.linearTriangularVariations(int) BCE (after)
+  /// CHECK-START: void Main.linearTriangularVariationsInnerStrict(int) BCE (after)
/// CHECK-NOT: BoundsCheck
-  /// CHECK-NOT: Deoptimize
-  private static void linearTriangularVariations(int n) {
+  //  TODO: also CHECK-NOT: Deoptimize, see b/27151190
+  private static void linearTriangularVariationsInnerStrict(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
a[j] += 1;
}
-      for (int j = i - 1; j >= 0; j--) {
+      for (int j = i - 1; j > -1; j--) {
a[j] += 1;
}
for (int j = i; j < n; j++) {
@@ -556,6 +556,34 @@
verifyTriangular(a);
}

+  /// CHECK-START: void Main.linearTriangularVariationsInnerNonStrict(int) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-DAG: BoundsCheck
+  /// CHECK-DAG: BoundsCheck
+  //
+  /// CHECK-START: void Main.linearTriangularVariationsInnerNonStrict(int) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  //  TODO: also CHECK-NOT: Deoptimize, see b/27151190
+  private static void linearTriangularVariationsInnerNonStrict(int n) {
+    int[] a = new int[n];
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j <= i - 1; j++) {
+        a[j] += 1;
+      }
+      for (int j = i - 1; j >= 0; j--) {
+        a[j] += 1;
+      }
+      for (int j = i; j <= n - 1; j++) {
+        a[j] += 1;
+      }
+      for (int j = n - 1; j >= i; j--) {
+        a[j] += 1;
+      }
+    }
+    verifyTriangular(a);
+  }
+
// Verifier for triangular loops.
private static void verifyTriangular(int[] a, int[] b, int m, int n) {
expectEquals(n, a.length);
@@ -583,7 +611,7 @@
//
/// CHECK-START: void Main.bubble(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
-  /// CHECK-NOT: Deoptimize
+  //  TODO: also CHECK-NOT: Deoptimize, see b/27151190
private static void bubble(int[] a) {
for (int i = a.length; --i >= 0;) {
for (int j = 0; j < i; j++) {
@@ -853,6 +881,104 @@
} while (-1 <= i);
}

+  /// CHECK-START: void Main.hiddenOOB1(int) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  //
+  /// CHECK-START: void Main.hiddenOOB1(int) BCE (after)
+  /// CHECK-DAG: Deoptimize
+  //
+  /// CHECK-START: void Main.hiddenOOB1(int) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static void hiddenOOB1(int lo) {
+    int[] a = { 1 } ;
+    for (int i = lo; i <= 10; i++) {
+      // Dangerous loop where careless static range analysis would yield strict upper bound
+      // on index j of 5. When, for instance, lo and thus i = -2147483648, the upper bound
+      // becomes really positive due to arithmetic wrap-around, causing OOB.
+      // Dynamic BCE is feasible though, since it checks the range.
+      for (int j = 4; j < i - 5; j++) {
+        sResult += a[j - 4];
+      }
+    }
+  }
+
+  /// CHECK-START: void Main.hiddenOOB2(int) BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  //
+  /// CHECK-START: void Main.hiddenOOB2(int) BCE (after)
+  /// CHECK-DAG: Deoptimize
+  //
+  /// CHECK-START: void Main.hiddenOOB2(int) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static void hiddenOOB2(int hi) {
+    int[] a = { 1 } ;
+    for (int i = 0; i < hi; i++) {
+      // Dangerous loop where careless static range analysis would yield strict lower bound
+      // on index j of 5. When, for instance, lo and thus i = 2147483647, the upper bound
+      // becomes really negative due to arithmetic wrap-around, causing OOB.
+      // Dynamic BCE is feasible though, since it checks the range.
+      for (int j = 6; j > i + 5; j--) {
+        sResult += a[j - 6];
+      }
+    }
+  }
+
+  /// CHECK-START: void Main.hiddenInfiniteOOB() BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  //
+  /// CHECK-START: void Main.hiddenInfiniteOOB() BCE (after)
+  /// CHECK-DAG: BoundsCheck
+  //
+  /// CHECK-START: void Main.hiddenInfiniteOOB() BCE (after)
+  /// CHECK-NOT: Deoptimize
+  private static void hiddenInfiniteOOB() {
+    int[] a = { 11 } ;
+    for (int i = -1; i <= 0; i++) {
+      // Dangerous loop where careless static range analysis would yield a safe upper bound
+      // of -3. In reality, due to arithmetic wrap-around (when i = -1, j <= 2147483647;
+      // whereas when i = 0, j <= -3), this is an infinite loop that goes OOB.
+      for (int j = -3; j <= 2147483646 * i - 3; j++) {
+        sResult += a[j + 3];
+      }
+    }
+  }
+
+  /// CHECK-START: void Main.hiddenFiniteOOB() BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  //
+  /// CHECK-START: void Main.hiddenFiniteOOB() BCE (after)
+  /// CHECK-DAG: Deoptimize
+  //
+  /// CHECK-START: void Main.hiddenFiniteOOB() BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  private static void hiddenFiniteOOB() {
+    int[] a = { 111 } ;
+    for (int i = -1; i <= 0; i++) {
+      // Dangerous loop similar as above where the loop is now finite, but the
+      // loop still goes out of bounds for i = -1 due to the large upper bound.
+      // Dynamic BCE is feasible though, since it checks the range.
+      for (int j = -4; j < 2147483646 * i - 3; j++) {
+        sResult += a[j + 4];
+      }
+    }
+  }
+
+  /// CHECK-START: int[] Main.add() BCE (before)
+  /// CHECK-DAG: BoundsCheck
+  //
+  /// CHECK-START: int[] Main.add() BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  /// CHECK-NOT: Deoptimize
+  private static int[] add() {
+    int[] a = new int[10];
+    for (int i = 0; i <= 3; i++) {
+      for (int j = 0; j <= 6; j++) {
+        a[i + j] += 1;
+      }
+    }
+    return a;
+  }
+
/// CHECK-START: int[] Main.multiply1() BCE (before)
/// CHECK-DAG: BoundsCheck
//
@@ -1053,6 +1179,37 @@
return result;
}

+  /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (before)
+  /// CHECK-DAG: BoundsCheck loop:<<InnerLoop:B\d+>>
+  /// CHECK-DAG: ArrayGet    loop:<<InnerLoop>>
+  /// CHECK-DAG: If          loop:<<InnerLoop>>
+  /// CHECK-DAG: If          loop:<<OuterLoop:B\d+>>
+  /// CHECK-EVAL: "<<InnerLoop>>" != "<<OuterLoop>>"
+  //
+  /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (after)
+  /// CHECK-DAG: ArrayGet   loop:<<InnerLoop:B\d+>>
+  /// CHECK-DAG: Deoptimize loop:<<OuterLoop:B\d+>>
+  /// CHECK-EVAL: "<<InnerLoop>>" != "<<OuterLoop>>"
+  //
+  /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (after)
+  /// CHECK-NOT: BoundsCheck
+  //
+  //  No additional top tests were introduced.
+  /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (after)
+  /// CHECK-DAG: If
+  /// CHECK-DAG: If
+  /// CHECK-NOT: If
+  static int dynamicBCEConstantRange(int[] x) {
+    int result = 0;
+    for (int i = 2; i <= 6; i++) {
+      // Range analysis sees that innermost loop is finite and always taken.
+      for (int j = i - 2; j <= i + 2; j++) {
+        result += x[j];
+      }
+    }
+    return result;
+  }
+
/// CHECK-START: int Main.dynamicBCEAndConstantIndices(int[], int[][], int, int) BCE (before)
/// CHECK-DAG: {{l\d+}} ArrayGet loop:<<Loop:B\d+>>
/// CHECK-DAG: {{l\d+}} ArrayGet loop:<<Loop>>
@@ -1239,7 +1396,8 @@
linearTriangularOnTwoArrayLengths(10);
linearTriangularOnOneArrayLength(10);
linearTriangularOnParameter(10);
-    linearTriangularVariations(10);
+    linearTriangularVariationsInnerStrict(10);
+    linearTriangularVariationsInnerNonStrict(10);

// Sorting.
int[] sort = { 5, 4, 1, 9, 10, 2, 7, 6, 3, 8 };
@@ -1330,6 +1488,59 @@
}
expectEquals(1055, sResult);

+    // Hidden OOB.
+    sResult = 0;
+    try {
+      hiddenOOB1(10);  // no OOB
+    } catch (ArrayIndexOutOfBoundsException e) {
+      sResult += 1000;
+    }
+    expectEquals(1, sResult);
+    sResult = 0;
+    try {
+      hiddenOOB1(-2147483648);  // OOB
+    } catch (ArrayIndexOutOfBoundsException e) {
+      sResult += 1000;
+    }
+    expectEquals(1001, sResult);
+    sResult = 0;
+    try {
+      hiddenOOB2(1);  // no OOB
+    } catch (ArrayIndexOutOfBoundsException e) {
+      sResult += 1000;
+    }
+    expectEquals(1, sResult);
+    sResult = 0;
+    try {
+      hiddenOOB2(2147483647);  // OOB
+    } catch (ArrayIndexOutOfBoundsException e) {
+      sResult += 1000;
+    }
+    expectEquals(1002, sResult);
+    sResult = 0;
+    try {
+      hiddenInfiniteOOB();
+    } catch (ArrayIndexOutOfBoundsException e) {
+      sResult += 1000;
+    }
+    expectEquals(1011, sResult);
+    sResult = 0;
+    try {
+      hiddenFiniteOOB();
+    } catch (ArrayIndexOutOfBoundsException e) {
+      sResult += 1000;
+    }
+    expectEquals(1111, sResult);
+
+    {
+      int[] e1 ={ 1, 2, 3, 4, 4, 4, 4, 3, 2, 1 };
+      int[] a1 = add();
+      for (int i = 0; i < 10; i++) {
+        expectEquals(a1[i], e1[i]);
+      }
+    }
+
// Multiplication.
{
int[] e1 = { 7, 1, 2, 2, 1, 0, 2, 0, 0, 1 };
@@ -1388,6 +1599,7 @@
expectEquals(55, dynamicBCEPossiblyInfiniteLoop(x, 0, 9));
expectEquals(55, noDynamicBCEPossiblyInfiniteLoop(x, 0, 9));
expectEquals(55, noDynamicBCEMixedInductionTypes(x, 0, 10));
+    expectEquals(125, dynamicBCEConstantRange(x));

// Dynamic BCE combined with constant indices.
int[][] a;