Merge "Various induction/range analysis improvements."
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 0b7fdf8..19e6cbd 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -71,10 +71,10 @@
}
void HInductionVarAnalysis::Run() {
- // Detects sequence variables (generalized induction variables) during an inner-loop-first
- // traversal of all loops using Gerlek's algorithm. The order is only relevant if outer
- // loops would use induction information of inner loops (not currently done).
- for (HPostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
+ // Detects sequence variables (generalized induction variables) during an outer to inner
+ // traversal of all loops using Gerlek's algorithm. The order is important to enable
+ // range analysis on outer loop while visiting inner loops.
+ for (HReversePostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
HBasicBlock* graph_block = it_graph.Current();
if (graph_block->IsLoopHeader()) {
VisitLoop(graph_block->GetLoopInformation());
@@ -745,8 +745,7 @@
if (value == 1) {
return b;
} else if (value == -1) {
- op = kNeg;
- a = nullptr;
+ return CreateSimplifiedInvariant(kNeg, nullptr, b);
}
}
}
@@ -763,26 +762,52 @@
if (value == 1) {
return a;
} else if (value == -1) {
- op = kNeg;
- b = a;
- a = nullptr;
+ return CreateSimplifiedInvariant(kNeg, nullptr, a);
}
}
} else if (b->operation == kNeg) {
// Simplify a + (-b) = a - b, a - (-b) = a + b, -(-b) = b.
if (op == kAdd) {
- op = kSub;
- b = b->op_b;
+ return CreateSimplifiedInvariant(kSub, a, b->op_b);
} else if (op == kSub) {
- op = kAdd;
- b = b->op_b;
+ return CreateSimplifiedInvariant(kAdd, a, b->op_b);
} else if (op == kNeg) {
return b->op_b;
}
+ } else if (b->operation == kSub) {
+ // Simplify - (a - b) = b - a.
+ if (op == kNeg) {
+ return CreateSimplifiedInvariant(kSub, b->op_b, b->op_a);
+ }
}
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::InductionEqual(InductionInfo* info1,
InductionInfo* info2) {
// Test structural equality only, without accounting for simplifications.
@@ -798,33 +823,9 @@
return info1 == info2;
}
-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.
- int32_t range_value;
- if (InductionVarRange::GetConstant(info, &range_value)) {
- *value = range_value;
- return true;
- }
- }
- return false;
-}
-
std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
if (info != nullptr) {
if (info->induction_class == kInvariant) {
- int64_t value = -1;
std::string inv = "(";
inv += InductionToString(info->op_a);
switch (info->operation) {
@@ -840,8 +841,10 @@
case kGE: inv += " >= "; break;
case kFetch:
DCHECK(info->fetch);
- if (IsIntAndGet(info, &value)) {
- inv += std::to_string(value);
+ if (info->fetch->IsIntConstant()) {
+ inv += std::to_string(info->fetch->AsIntConstant()->GetValue());
+ } else if (info->fetch->IsLongConstant()) {
+ inv += std::to_string(info->fetch->AsLongConstant()->GetValue());
} else {
inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName();
}
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index cf35409..84d5d82 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -188,9 +188,11 @@
InductionInfo* CreateConstant(int64_t value, Primitive::Type type);
InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
+ // Constants.
+ bool IsIntAndGet(InductionInfo* info, int64_t* value);
+
// Helpers.
static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
- static bool IsIntAndGet(InductionInfo* info, int64_t* value);
static std::string InductionToString(InductionInfo* info);
// TODO: fine tune the following data structures, only keep relevant data.
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 9d0cde7..ae15fcf 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -119,7 +119,7 @@
}
}
-bool InductionVarRange::RefineOuter(/*in-out*/Value* min_val, /*in-out*/Value* max_val) {
+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) {
@@ -167,7 +167,7 @@
// Private class methods.
//
-bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) {
+bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const {
if (info != nullptr) {
if (info->induction_class == HInductionVarAnalysis::kLinear) {
return true;
@@ -178,7 +178,7 @@
return false;
}
-bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) {
+bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const {
if (trip != nullptr) {
if (trip->induction_class == HInductionVarAnalysis::kInvariant) {
return trip->operation == HInductionVarAnalysis::kTripCountInBody ||
@@ -188,7 +188,7 @@
return false;
}
-bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) {
+bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const {
if (trip != nullptr) {
if (trip->induction_class == HInductionVarAnalysis::kInvariant) {
return trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe ||
@@ -198,10 +198,57 @@
return false;
}
+InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const {
+ // Detect common situation where an offset inside the trip count cancels out during range
+ // analysis (finding max a * (TC - 1) + OFFSET for a == 1 and TC = UPPER - OFFSET or finding
+ // min a * (TC - 1) + OFFSET for a == -1 and TC = OFFSET - UPPER) to avoid losing information
+ // with intermediate results that only incorporate single instructions.
+ 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) {
+ if (!is_min && stride_value == 1) {
+ // Test original trip's negative operand (trip_expr->op_b) against
+ // the offset of the linear 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(
+ trip->induction_class, trip->operation, trip_expr->op_a, trip->op_b, nullptr);
+ 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.
+ 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(
+ HInductionVarAnalysis::kInvariant,
+ HInductionVarAnalysis::kNeg,
+ nullptr,
+ trip_expr->op_b,
+ nullptr);
+ HInductionVarAnalysis::InductionInfo cancelled_trip(
+ trip->induction_class, trip->operation, &neg, trip->op_b, nullptr);
+ return SubValue(Value(0), GetVal(&cancelled_trip, trip, in_body, !is_min));
+ }
+ }
+ }
+ }
+ }
+ // General rule of linear induction a * i + b, for normalized 0 <= i < TC.
+ return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min),
+ GetVal(info->op_b, trip, in_body, is_min));
+}
+
InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
HInductionVarAnalysis::InductionInfo* trip,
bool in_body,
- bool is_min) {
+ 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;
@@ -227,7 +274,7 @@
InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
bool in_body,
- bool is_min) {
+ bool is_min) const {
if (info != nullptr) {
switch (info->induction_class) {
case HInductionVarAnalysis::kInvariant:
@@ -266,13 +313,11 @@
break;
}
break;
- case HInductionVarAnalysis::kLinear:
- // Linear induction a * i + b, for normalized 0 <= i < TC.
- return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min),
- GetVal(info->op_b, trip, in_body, is_min));
+ case HInductionVarAnalysis::kLinear: {
+ return GetLinear(info, trip, in_body, is_min);
+ }
case HInductionVarAnalysis::kWrapAround:
case HInductionVarAnalysis::kPeriodic:
- // Merge values in the wrap-around/periodic.
return MergeVal(GetVal(info->op_a, trip, in_body, is_min),
GetVal(info->op_b, trip, in_body, is_min), is_min);
}
@@ -284,11 +329,17 @@
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
bool in_body,
- bool is_min) {
+ bool is_min) const {
Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true);
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);
+ }
+ // 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) {
@@ -298,7 +349,7 @@
return is_min ? MulValue(v1_max, v2_min)
: MulValue(v1_min, v2_max);
}
- } else if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant <= 0) {
+ } 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)
@@ -315,11 +366,12 @@
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
bool in_body,
- bool is_min) {
+ bool is_min) const {
Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true);
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) {
@@ -329,7 +381,7 @@
return is_min ? DivValue(v1_max, v2_max)
: DivValue(v1_min, v2_min);
}
- } else if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant <= 0) {
+ } 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)
@@ -342,19 +394,23 @@
return Value();
}
-bool InductionVarRange::GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t *value) {
- Value v_min = GetVal(info, nullptr, false, /* is_min */ true);
- Value v_max = GetVal(info, nullptr, false, /* is_min */ false);
- if (v_min.is_known && v_max.is_known) {
- if (v_min.a_constant == 0 && v_max.a_constant == 0 && v_min.b_constant == v_max.b_constant) {
- *value = v_min.b_constant;
+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::AddValue(Value v1, Value v2) {
+InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const {
if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) {
const int32_t b = v1.b_constant + v2.b_constant;
if (v1.a_constant == 0) {
@@ -368,7 +424,7 @@
return Value();
}
-InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) {
+InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) const {
if (v1.is_known && v2.is_known && IsSafeSub(v1.b_constant, v2.b_constant)) {
const int32_t b = v1.b_constant - v2.b_constant;
if (v1.a_constant == 0 && IsSafeSub(0, v2.a_constant)) {
@@ -382,7 +438,7 @@
return Value();
}
-InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) {
+InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) const {
if (v1.is_known && v2.is_known) {
if (v1.a_constant == 0) {
if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) {
@@ -397,7 +453,7 @@
return Value();
}
-InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) {
+InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) const {
if (v1.is_known && v2.is_known && v1.a_constant == 0 && v2.a_constant == 0) {
if (IsSafeDiv(v1.b_constant, v2.b_constant)) {
return Value(v1.b_constant / v2.b_constant);
@@ -406,7 +462,7 @@
return Value();
}
-InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is_min) {
+InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is_min) const {
if (v1.is_known && v2.is_known) {
if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) {
return Value(v1.instruction, v1.a_constant,
@@ -417,7 +473,7 @@
return Value();
}
-InductionVarRange::Value InductionVarRange::RefineOuter(Value v, bool is_min) {
+InductionVarRange::Value InductionVarRange::RefineOuter(Value v, bool is_min) const {
if (v.instruction != nullptr) {
HLoopInformation* loop =
v.instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop
@@ -444,7 +500,7 @@
/*out*/HInstruction** upper,
/*out*/HInstruction** taken_test,
/*out*/bool* needs_finite_test,
- /*out*/bool* needs_taken_test) {
+ /*out*/bool* needs_taken_test) const {
HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop
if (loop != nullptr) {
// Set up loop information.
@@ -492,7 +548,7 @@
HBasicBlock* block,
/*out*/HInstruction** result,
bool in_body,
- bool is_min) {
+ bool is_min) const {
if (info != nullptr) {
// Handle current operation.
Primitive::Type type = Primitive::kPrimInt;
@@ -586,8 +642,9 @@
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 (GetConstant(info->op_a, &stride_value)) {
+ if (IsConstantRange(info->op_a, &min_value, &stride_value) && min_value == 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) &&
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 71b0b1b..974b8fb 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -69,7 +69,7 @@
/*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);
+ 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,46 +116,48 @@
/*out*/HInstruction** taken_test);
private:
- //
- // Private helper methods.
- //
+ bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const;
+ bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
+ bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
- static bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info);
- static bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip);
- static bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip);
+ Value GetLinear(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const;
+ Value GetFetch(HInstruction* instruction,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const;
+ Value GetVal(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const;
+ Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
+ HInductionVarAnalysis::InductionInfo* info2,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const;
+ Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
+ HInductionVarAnalysis::InductionInfo* info2,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
+ bool is_min) const;
- static Value GetFetch(HInstruction* instruction,
- HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
- bool is_min);
- static Value GetVal(HInductionVarAnalysis::InductionInfo* info,
- HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
- bool is_min);
- static Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
- HInductionVarAnalysis::InductionInfo* info2,
- HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
- bool is_min);
- static Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
- HInductionVarAnalysis::InductionInfo* info2,
- HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
- bool is_min);
+ bool IsConstantRange(HInductionVarAnalysis::InductionInfo* info,
+ int32_t *min_value,
+ int32_t *max_value) const;
- static bool GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t *value);
-
- static Value AddValue(Value v1, Value v2);
- static Value SubValue(Value v1, Value v2);
- static Value MulValue(Value v1, Value v2);
- static Value DivValue(Value v1, Value v2);
- static Value MergeVal(Value v1, Value v2, bool is_min);
+ Value AddValue(Value v1, Value v2) const;
+ Value SubValue(Value v1, Value v2) const;
+ Value MulValue(Value v1, Value v2) const;
+ Value DivValue(Value v1, Value v2) const;
+ Value MergeVal(Value v1, Value v2, bool is_min) const;
/**
* Returns refined value using induction of next outer loop or the input value if no
* further refinement is possible.
*/
- Value RefineOuter(Value val, bool is_min);
+ Value RefineOuter(Value val, bool is_min) const;
/**
* Generates code for lower/upper/taken-test in the HIR. Returns true on success.
@@ -170,15 +172,15 @@
/*out*/HInstruction** upper,
/*out*/HInstruction** taken_test,
/*out*/bool* needs_finite_test,
- /*out*/bool* needs_taken_test);
+ /*out*/bool* needs_taken_test) const;
- static bool GenerateCode(HInductionVarAnalysis::InductionInfo* info,
- HInductionVarAnalysis::InductionInfo* trip,
- HGraph* graph,
- HBasicBlock* block,
- /*out*/HInstruction** result,
- bool in_body,
- bool is_min);
+ bool GenerateCode(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** result,
+ bool in_body,
+ bool is_min) const;
/** Results of prior induction variable analysis. */
HInductionVarAnalysis *induction_analysis_;
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index a1c797a..eda9c01 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -30,9 +30,12 @@
*/
class InductionVarRangeTest : public CommonCompilerTest {
public:
- InductionVarRangeTest() : pool_(), allocator_(&pool_) {
- graph_ = CreateGraph(&allocator_);
- iva_ = new (&allocator_) HInductionVarAnalysis(graph_);
+ InductionVarRangeTest()
+ : pool_(),
+ allocator_(&pool_),
+ graph_(CreateGraph(&allocator_)),
+ iva_(new (&allocator_) HInductionVarAnalysis(graph_)),
+ range_(iva_) {
BuildGraph();
}
@@ -58,6 +61,11 @@
graph_->AddBlock(exit_block_);
graph_->SetEntryBlock(entry_block_);
graph_->SetExitBlock(exit_block_);
+ // Two parameters.
+ x_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
+ entry_block_->AddInstruction(x_);
+ y_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
+ entry_block_->AddInstruction(y_);
}
/** Constructs loop with given upper bound. */
@@ -102,7 +110,7 @@
exit_block_->AddInstruction(new (&allocator_) HExit());
}
- /** Performs induction variable analysis. */
+ /** Constructs SSA and performs induction variable analysis. */
void PerformInductionVarAnalysis() {
TransformToSsa(graph_);
iva_->Run();
@@ -179,49 +187,51 @@
//
bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) {
- return InductionVarRange::NeedsTripCount(info);
+ return range_.NeedsTripCount(info);
}
bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) {
- return InductionVarRange::IsBodyTripCount(trip);
+ return range_.IsBodyTripCount(trip);
}
bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) {
- return InductionVarRange::IsUnsafeTripCount(trip);
+ return range_.IsUnsafeTripCount(trip);
}
Value GetMin(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* induc) {
- return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ true);
+ return range_.GetVal(info, induc, /* in_body */ true, /* is_min */ true);
}
Value GetMax(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* induc) {
- return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ false);
+ return range_.GetVal(info, induc, /* in_body */ true, /* is_min */ false);
}
Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
bool is_min) {
- return InductionVarRange::GetMul(info1, info2, nullptr, /* in_body */ true, is_min);
+ return range_.GetMul(info1, info2, nullptr, /* in_body */ true, is_min);
}
Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
bool is_min) {
- return InductionVarRange::GetDiv(info1, info2, nullptr, /* in_body */ true, is_min);
+ return range_.GetDiv(info1, info2, nullptr, /* in_body */ true, is_min);
}
- bool GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t* value) {
- return InductionVarRange::GetConstant(info, value);
+ bool IsConstantRange(HInductionVarAnalysis::InductionInfo* info,
+ int32_t* min_value,
+ int32_t* max_value) {
+ return range_.IsConstantRange(info, min_value, max_value);
}
- Value AddValue(Value v1, Value v2) { return InductionVarRange::AddValue(v1, v2); }
- Value SubValue(Value v1, Value v2) { return InductionVarRange::SubValue(v1, v2); }
- Value MulValue(Value v1, Value v2) { return InductionVarRange::MulValue(v1, v2); }
- Value DivValue(Value v1, Value v2) { return InductionVarRange::DivValue(v1, v2); }
- Value MinValue(Value v1, Value v2) { return InductionVarRange::MergeVal(v1, v2, true); }
- Value MaxValue(Value v1, Value v2) { return InductionVarRange::MergeVal(v1, v2, false); }
+ Value AddValue(Value v1, Value v2) { return range_.AddValue(v1, v2); }
+ Value SubValue(Value v1, Value v2) { return range_.SubValue(v1, v2); }
+ Value MulValue(Value v1, Value v2) { return range_.MulValue(v1, v2); }
+ Value DivValue(Value v1, Value v2) { return range_.DivValue(v1, v2); }
+ Value MinValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, true); }
+ Value MaxValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, false); }
// General building fields.
ArenaPool pool_;
@@ -231,16 +241,17 @@
HBasicBlock* exit_block_;
HBasicBlock* loop_preheader_;
HInductionVarAnalysis* iva_;
+ InductionVarRange range_;
// Instructions.
HInstruction* condition_;
HInstruction* increment_;
- HReturnVoid x_;
- HReturnVoid y_;
+ HInstruction* x_;
+ HInstruction* y_;
};
//
-// Tests on static methods.
+// Tests on private methods.
//
TEST_F(InductionVarRangeTest, TripCountProperties) {
@@ -273,14 +284,14 @@
GetMin(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr));
ExpectEqual(Value(22),
GetMax(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr));
- ExpectEqual(Value(&x_, 1, -20),
- GetMin(CreateInvariant('+', CreateFetch(&x_), CreateRange(-20, -10)), nullptr));
- ExpectEqual(Value(&x_, 1, -10),
- GetMax(CreateInvariant('+', CreateFetch(&x_), CreateRange(-20, -10)), nullptr));
- ExpectEqual(Value(&x_, 1, 10),
- GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(&x_)), nullptr));
- ExpectEqual(Value(&x_, 1, 20),
- GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(&x_)), nullptr));
+ ExpectEqual(Value(x_, 1, -20),
+ GetMin(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
+ ExpectEqual(Value(x_, 1, -10),
+ GetMax(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
+ ExpectEqual(Value(x_, 1, 10),
+ GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr));
+ ExpectEqual(Value(x_, 1, 20),
+ GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr));
ExpectEqual(Value(5),
GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
ExpectEqual(Value(19),
@@ -292,14 +303,14 @@
GetMin(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr));
ExpectEqual(Value(-8),
GetMax(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr));
- ExpectEqual(Value(&x_, 1, 10),
- GetMin(CreateInvariant('-', CreateFetch(&x_), CreateRange(-20, -10)), nullptr));
- ExpectEqual(Value(&x_, 1, 20),
- GetMax(CreateInvariant('-', CreateFetch(&x_), CreateRange(-20, -10)), nullptr));
- ExpectEqual(Value(&x_, -1, 10),
- GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(&x_)), nullptr));
- ExpectEqual(Value(&x_, -1, 20),
- GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(&x_)), nullptr));
+ ExpectEqual(Value(x_, 1, 10),
+ GetMin(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
+ ExpectEqual(Value(x_, 1, 20),
+ GetMax(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr));
+ ExpectEqual(Value(x_, -1, 10),
+ GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr));
+ ExpectEqual(Value(x_, -1, 20),
+ GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr));
ExpectEqual(Value(-25),
GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
ExpectEqual(Value(-11),
@@ -311,8 +322,8 @@
ExpectEqual(Value(-10), GetMax(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr));
ExpectEqual(Value(10), GetMin(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr));
ExpectEqual(Value(20), GetMax(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr));
- ExpectEqual(Value(&x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(&x_)), nullptr));
- ExpectEqual(Value(&x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(&x_)), nullptr));
+ ExpectEqual(Value(x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr));
+ ExpectEqual(Value(x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr));
}
TEST_F(InductionVarRangeTest, GetMinMaxMul) {
@@ -335,8 +346,8 @@
}
TEST_F(InductionVarRangeTest, GetMinMaxFetch) {
- ExpectEqual(Value(&x_, 1, 0), GetMin(CreateFetch(&x_), nullptr));
- ExpectEqual(Value(&x_, 1, 0), GetMax(CreateFetch(&x_), nullptr));
+ ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(x_), nullptr));
+ ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(x_), nullptr));
}
TEST_F(InductionVarRangeTest, GetMinMaxLinear) {
@@ -363,45 +374,70 @@
TEST_F(InductionVarRangeTest, GetMulMin) {
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));
ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), true));
ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), true));
+ ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), true));
+ ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), true));
+ ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), true));
+ ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), true));
}
TEST_F(InductionVarRangeTest, GetMulMax) {
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));
ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), false));
ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), false));
+ ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), false));
+ ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), false));
+ ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), false));
+ ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), false));
}
TEST_F(InductionVarRangeTest, GetDivMin) {
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));
ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), true));
ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), true));
+ ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), true));
+ ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), true));
+ ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, -40), true));
+ ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), true));
}
TEST_F(InductionVarRangeTest, GetDivMax) {
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));
ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), false));
ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false));
+ ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), false));
+ ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), false));
+ ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, 40), false));
+ ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false));
}
-TEST_F(InductionVarRangeTest, GetConstant) {
- int32_t value;
- ASSERT_TRUE(GetConstant(CreateConst(12345), &value));
- EXPECT_EQ(12345, value);
- EXPECT_FALSE(GetConstant(CreateRange(1, 2), &value));
+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));
}
TEST_F(InductionVarRangeTest, AddValue) {
ExpectEqual(Value(110), AddValue(Value(10), Value(100)));
- ExpectEqual(Value(-5), AddValue(Value(&x_, 1, -4), Value(&x_, -1, -1)));
- ExpectEqual(Value(&x_, 3, -5), AddValue(Value(&x_, 2, -4), Value(&x_, 1, -1)));
- ExpectEqual(Value(), AddValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
- ExpectEqual(Value(&x_, 1, 23), AddValue(Value(&x_, 1, 20), Value(3)));
- ExpectEqual(Value(&y_, 1, 5), AddValue(Value(55), Value(&y_, 1, -50)));
+ ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1)));
+ ExpectEqual(Value(x_, 3, -5), AddValue(Value(x_, 2, -4), Value(x_, 1, -1)));
+ ExpectEqual(Value(), AddValue(Value(x_, 1, 5), Value(y_, 1, -7)));
+ ExpectEqual(Value(x_, 1, 23), AddValue(Value(x_, 1, 20), Value(3)));
+ ExpectEqual(Value(y_, 1, 5), AddValue(Value(55), Value(y_, 1, -50)));
const int32_t max_value = std::numeric_limits<int32_t>::max();
ExpectEqual(Value(max_value), AddValue(Value(max_value - 5), Value(5)));
ExpectEqual(Value(), AddValue(Value(max_value - 5), Value(6))); // unsafe
@@ -409,11 +445,11 @@
TEST_F(InductionVarRangeTest, SubValue) {
ExpectEqual(Value(-90), SubValue(Value(10), Value(100)));
- ExpectEqual(Value(-3), SubValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
- ExpectEqual(Value(&x_, 2, -3), SubValue(Value(&x_, 3, -4), Value(&x_, 1, -1)));
- ExpectEqual(Value(), SubValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
- ExpectEqual(Value(&x_, 1, 17), SubValue(Value(&x_, 1, 20), Value(3)));
- ExpectEqual(Value(&y_, -4, 105), SubValue(Value(55), Value(&y_, 4, -50)));
+ ExpectEqual(Value(-3), SubValue(Value(x_, 1, -4), Value(x_, 1, -1)));
+ ExpectEqual(Value(x_, 2, -3), SubValue(Value(x_, 3, -4), Value(x_, 1, -1)));
+ ExpectEqual(Value(), SubValue(Value(x_, 1, 5), Value(y_, 1, -7)));
+ ExpectEqual(Value(x_, 1, 17), SubValue(Value(x_, 1, 20), Value(3)));
+ ExpectEqual(Value(y_, -4, 105), SubValue(Value(55), Value(y_, 4, -50)));
const int32_t min_value = std::numeric_limits<int32_t>::min();
ExpectEqual(Value(min_value), SubValue(Value(min_value + 5), Value(5)));
ExpectEqual(Value(), SubValue(Value(min_value + 5), Value(6))); // unsafe
@@ -421,145 +457,140 @@
TEST_F(InductionVarRangeTest, MulValue) {
ExpectEqual(Value(1000), MulValue(Value(10), Value(100)));
- ExpectEqual(Value(), MulValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
- ExpectEqual(Value(), MulValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
- ExpectEqual(Value(&x_, 9, 60), MulValue(Value(&x_, 3, 20), Value(3)));
- ExpectEqual(Value(&y_, 55, -110), MulValue(Value(55), Value(&y_, 1, -2)));
+ ExpectEqual(Value(), MulValue(Value(x_, 1, -4), Value(x_, 1, -1)));
+ ExpectEqual(Value(), MulValue(Value(x_, 1, 5), Value(y_, 1, -7)));
+ ExpectEqual(Value(x_, 9, 60), MulValue(Value(x_, 3, 20), Value(3)));
+ ExpectEqual(Value(y_, 55, -110), MulValue(Value(55), Value(y_, 1, -2)));
ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe
}
TEST_F(InductionVarRangeTest, DivValue) {
ExpectEqual(Value(25), DivValue(Value(100), Value(4)));
- ExpectEqual(Value(), DivValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
- ExpectEqual(Value(), DivValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
- ExpectEqual(Value(), DivValue(Value(&x_, 12, 24), Value(3)));
- ExpectEqual(Value(), DivValue(Value(55), Value(&y_, 1, -50)));
+ ExpectEqual(Value(), DivValue(Value(x_, 1, -4), Value(x_, 1, -1)));
+ ExpectEqual(Value(), DivValue(Value(x_, 1, 5), Value(y_, 1, -7)));
+ ExpectEqual(Value(), DivValue(Value(x_, 12, 24), Value(3)));
+ ExpectEqual(Value(), DivValue(Value(55), Value(y_, 1, -50)));
ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe
}
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)));
- ExpectEqual(Value(&x_, 4, -4), MinValue(Value(&x_, 4, -4), Value(&x_, 4, -1)));
- ExpectEqual(Value(), MinValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
- ExpectEqual(Value(), MinValue(Value(&x_, 1, 20), Value(3)));
- ExpectEqual(Value(), MinValue(Value(55), Value(&y_, 1, -50)));
+ ExpectEqual(Value(x_, 1, -4), MinValue(Value(x_, 1, -4), Value(x_, 1, -1)));
+ ExpectEqual(Value(x_, 4, -4), MinValue(Value(x_, 4, -4), Value(x_, 4, -1)));
+ ExpectEqual(Value(), MinValue(Value(x_, 1, 5), Value(y_, 1, -7)));
+ ExpectEqual(Value(), MinValue(Value(x_, 1, 20), Value(3)));
+ ExpectEqual(Value(), MinValue(Value(55), Value(y_, 1, -50)));
}
TEST_F(InductionVarRangeTest, MaxValue) {
ExpectEqual(Value(100), MaxValue(Value(10), Value(100)));
- ExpectEqual(Value(&x_, 1, -1), MaxValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
- ExpectEqual(Value(&x_, 4, -1), MaxValue(Value(&x_, 4, -4), Value(&x_, 4, -1)));
- ExpectEqual(Value(), MaxValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
- ExpectEqual(Value(), MaxValue(Value(&x_, 1, 20), Value(3)));
- ExpectEqual(Value(), MaxValue(Value(55), Value(&y_, 1, -50)));
+ ExpectEqual(Value(x_, 1, -1), MaxValue(Value(x_, 1, -4), Value(x_, 1, -1)));
+ ExpectEqual(Value(x_, 4, -1), MaxValue(Value(x_, 4, -4), Value(x_, 4, -1)));
+ ExpectEqual(Value(), MaxValue(Value(x_, 1, 5), Value(y_, 1, -7)));
+ ExpectEqual(Value(), MaxValue(Value(x_, 1, 20), Value(3)));
+ ExpectEqual(Value(), MaxValue(Value(55), Value(y_, 1, -50)));
}
//
-// Tests on instance methods.
+// Tests on public methods.
//
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.
- range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
+ EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
// In context of loop-body: known.
- range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(999), v2);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
- range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
+ range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
+ EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
}
TEST_F(InductionVarRangeTest, ConstantTripCountDown) {
BuildLoop(1000, graph_->GetIntConstant(0), -1);
PerformInductionVarAnalysis();
- InductionVarRange range(iva_);
Value v1, v2;
bool needs_finite_test = true;
// In context of header: known.
- range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
+ EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
// In context of loop-body: known.
- range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
- range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
+ range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(999), v2);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
+ EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
}
TEST_F(InductionVarRangeTest, SymbolicTripCountUp) {
- HInstruction* parameter = new (&allocator_) HParameterValue(
- graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
- entry_block_->AddInstruction(parameter);
- BuildLoop(0, parameter, 1);
+ BuildLoop(0, x_, 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);
+ range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(), v2);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
+ EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
// In context of loop-body: known.
- range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ 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);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
- range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ ExpectEqual(Value(x_, 1, -1), v2);
+ EXPECT_FALSE(range_.RefineOuter(&v1, &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);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
+ ExpectEqual(Value(x_, 1, 0), v2);
+ EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
HInstruction* lower = nullptr;
HInstruction* upper = nullptr;
HInstruction* taken = nullptr;
// Can generate code in context of loop-body only.
- EXPECT_FALSE(range.CanGenerateCode(
+ EXPECT_FALSE(range_.CanGenerateCode(
condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
- ASSERT_TRUE(range.CanGenerateCode(
+ 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);
+ range_.GenerateRangeCode(
+ increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper);
// Verify lower is 0+0.
ASSERT_TRUE(lower != nullptr);
@@ -580,7 +611,7 @@
EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue());
// Verify taken-test is 0<V.
- range.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
+ range_.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
ASSERT_TRUE(taken != nullptr);
ASSERT_TRUE(taken->IsLessThan());
ASSERT_TRUE(taken->InputAt(0)->IsIntConstant());
@@ -589,52 +620,49 @@
}
TEST_F(InductionVarRangeTest, SymbolicTripCountDown) {
- HInstruction* parameter = new (&allocator_) HParameterValue(
- graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
- entry_block_->AddInstruction(parameter);
- BuildLoop(1000, parameter, -1);
+ BuildLoop(1000, x_, -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);
+ range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
+ EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
// In context of loop-body: known.
- range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
- ExpectEqual(Value(parameter, 1, 1), v1);
+ ExpectEqual(Value(x_, 1, 1), v1);
ExpectEqual(Value(1000), v2);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
- range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
+ range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
- ExpectEqual(Value(parameter, 1, 0), v1);
+ ExpectEqual(Value(x_, 1, 0), v1);
ExpectEqual(Value(999), v2);
- EXPECT_FALSE(range.RefineOuter(&v1, &v2));
+ EXPECT_FALSE(range_.RefineOuter(&v1, &v2));
HInstruction* lower = nullptr;
HInstruction* upper = nullptr;
HInstruction* taken = nullptr;
// Can generate code in context of loop-body only.
- EXPECT_FALSE(range.CanGenerateCode(
+ EXPECT_FALSE(range_.CanGenerateCode(
condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
- ASSERT_TRUE(range.CanGenerateCode(
+ 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);
+ range_.GenerateRangeCode(
+ increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper);
- // Verify lower is 1000-(-(V-1000)-1).
+ // Verify lower is 1000-((1000-V)-1).
ASSERT_TRUE(lower != nullptr);
ASSERT_TRUE(lower->IsSub());
ASSERT_TRUE(lower->InputAt(0)->IsIntConstant());
@@ -644,12 +672,10 @@
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());
+ ASSERT_TRUE(lower->InputAt(0)->IsIntConstant());
+ EXPECT_EQ(1000, lower->InputAt(0)->AsIntConstant()->GetValue());
+ EXPECT_TRUE(lower->InputAt(1)->IsParameterValue());
// Verify upper is 1000-0.
ASSERT_TRUE(upper != nullptr);
@@ -660,7 +686,7 @@
EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue());
// Verify taken-test is 1000>V.
- range.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
+ range_.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
ASSERT_TRUE(taken != nullptr);
ASSERT_TRUE(taken->IsGreaterThan());
ASSERT_TRUE(taken->InputAt(0)->IsIntConstant());
diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java
index 3f6e48b..e827b1e 100644
--- a/test/530-checker-loops/src/Main.java
+++ b/test/530-checker-loops/src/Main.java
@@ -27,6 +27,7 @@
/// CHECK-START: int Main.linear(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linear(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -40,6 +41,7 @@
/// CHECK-START: int Main.linearDown(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearDown(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -53,6 +55,7 @@
/// CHECK-START: int Main.linearObscure(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearObscure(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -67,6 +70,7 @@
/// CHECK-START: int Main.linearVeryObscure(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearVeryObscure(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -79,8 +83,26 @@
return result;
}
+ /// CHECK-START: int Main.hiddenStride(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ //
+ /// CHECK-START: int Main.hiddenStride(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
+ static int hiddenStride(int[] a) {
+ int result = 0;
+ for (int i = 1; i <= 1; i++) {
+ // Obscured unit stride.
+ for (int j = 0; j < a.length; j += i) {
+ result += a[j];
+ }
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.linearWhile(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearWhile(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -95,6 +117,7 @@
/// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -112,6 +135,7 @@
/// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -133,6 +157,7 @@
/// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -149,6 +174,7 @@
/// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -169,6 +195,7 @@
/// CHECK-START: int[] Main.linearWithParameter(int) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int[] Main.linearWithParameter(int) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -182,6 +209,7 @@
/// CHECK-START: int[] Main.linearCopy(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int[] Main.linearCopy(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -197,6 +225,7 @@
/// CHECK-START: int Main.linearByTwo(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearByTwo(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -213,6 +242,7 @@
/// CHECK-START: int Main.linearByTwoSkip1(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearByTwoSkip1(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -226,6 +256,7 @@
/// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (after)
/// CHECK-DAG: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -240,6 +271,7 @@
/// CHECK-START: int Main.linearWithCompoundStride() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearWithCompoundStride() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -256,6 +288,7 @@
/// CHECK-START: int Main.linearWithLargePositiveStride() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearWithLargePositiveStride() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -273,6 +306,7 @@
/// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (after)
/// CHECK-DAG: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -290,6 +324,7 @@
/// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -307,6 +342,7 @@
/// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (after)
/// CHECK-DAG: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -324,6 +360,7 @@
/// CHECK-START: int Main.linearForNEUp() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearForNEUp() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -338,6 +375,7 @@
/// CHECK-START: int Main.linearForNEDown() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearForNEDown() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -352,6 +390,7 @@
/// CHECK-START: int Main.linearDoWhileUp() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearDoWhileUp() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -367,6 +406,7 @@
/// CHECK-START: int Main.linearDoWhileDown() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearDoWhileDown() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -382,6 +422,7 @@
/// CHECK-START: int Main.linearShort() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.linearShort() BCE (after)
/// CHECK-DAG: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -397,6 +438,7 @@
/// CHECK-START: int Main.invariantFromPreLoop(int[], int) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.invariantFromPreLoop(int[], int) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -422,6 +464,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
/// CHECK-DAG: ArraySet
+ //
/// CHECK-START: void Main.linearTriangularOnTwoArrayLengths(int) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-DAG: ArrayGet
@@ -451,6 +494,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
/// CHECK-DAG: ArraySet
+ //
/// CHECK-START: void Main.linearTriangularOnOneArrayLength(int) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-DAG: ArrayGet
@@ -480,6 +524,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
/// CHECK-DAG: ArraySet
+ //
/// CHECK-START: void Main.linearTriangularOnParameter(int) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-DAG: ArrayGet
@@ -502,7 +547,54 @@
}
}
- // Verifier for triangular methods.
+ /// CHECK-START: void Main.linearTriangularVariations(int) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ //
+ /// CHECK-START: void Main.linearTriangularVariations(int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: Deoptimize
+ private static void linearTriangularVariations(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--) {
+ a[j] += 1;
+ }
+ for (int j = i; j < n; j++) {
+ a[j] += 1;
+ }
+ for (int j = n - 1; j > i - 1; 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);
for (int i = 0, k = m; i < n; i++) {
@@ -515,6 +607,14 @@
}
}
+ // Verifier for triangular loops.
+ private static void verifyTriangular(int[] a) {
+ int n = a.length;
+ for (int i = 0; i < n; i++) {
+ expectEquals(a[i], n + n);
+ }
+ }
+
/// CHECK-START: void Main.bubble(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
@@ -523,6 +623,7 @@
/// CHECK-DAG: If
/// CHECK-DAG: ArraySet
/// CHECK-DAG: ArraySet
+ //
/// CHECK-START: void Main.bubble(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-DAG: ArrayGet
@@ -546,6 +647,7 @@
/// CHECK-START: int Main.periodicIdiom(int) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.periodicIdiom(int) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -563,6 +665,7 @@
/// CHECK-START: int Main.periodicSequence2(int) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.periodicSequence2(int) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -586,6 +689,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.periodicSequence4(int) BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -610,6 +714,7 @@
/// CHECK-START: int Main.justRightUp1() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.justRightUp1() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -624,6 +729,7 @@
/// CHECK-START: int Main.justRightUp2() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.justRightUp2() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -638,6 +744,7 @@
/// CHECK-START: int Main.justRightUp3() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.justRightUp3() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -652,6 +759,7 @@
/// CHECK-START: int Main.justOOBUp() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.justOOBUp() BCE (after)
/// CHECK-DAG: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -667,6 +775,7 @@
/// CHECK-START: int Main.justRightDown1() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.justRightDown1() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -681,6 +790,7 @@
/// CHECK-START: int Main.justRightDown2() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.justRightDown2() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -695,6 +805,7 @@
/// CHECK-START: int Main.justRightDown3() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.justRightDown3() BCE (after)
/// CHECK-NOT: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -709,6 +820,7 @@
/// CHECK-START: int Main.justOOBDown() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.justOOBDown() BCE (after)
/// CHECK-DAG: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -724,6 +836,7 @@
/// CHECK-START: void Main.lowerOOB(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: void Main.lowerOOB(int[]) BCE (after)
/// CHECK-DAG: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -735,6 +848,7 @@
/// CHECK-START: void Main.upperOOB(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: void Main.upperOOB(int[]) BCE (after)
/// CHECK-DAG: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -746,6 +860,7 @@
/// CHECK-START: void Main.doWhileUpOOB() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: void Main.doWhileUpOOB() BCE (after)
/// CHECK-DAG: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -759,6 +874,7 @@
/// CHECK-START: void Main.doWhileDownOOB() BCE (before)
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: void Main.doWhileDownOOB() BCE (after)
/// CHECK-DAG: BoundsCheck
/// CHECK-NOT: Deoptimize
@@ -770,6 +886,55 @@
} while (-1 <= i);
}
+ /// CHECK-START: int[] Main.multiply1() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ //
+ /// CHECK-START: int[] Main.multiply1() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: Deoptimize
+ private static int[] multiply1() {
+ int[] a = new int[10];
+ try {
+ for (int i = 0; i <= 3; i++) {
+ for (int j = 0; j <= 3; j++) {
+ // Range [0,9]: safe.
+ a[i * j] += 1;
+ }
+ }
+ } catch (Exception e) {
+ a[0] += 1000;
+ }
+ return a;
+ }
+
+ /// CHECK-START: int[] Main.multiply2() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ //
+ /// CHECK-START: int[] Main.multiply2() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ static int[] multiply2() {
+ int[] a = new int[10];
+ try {
+ for (int i = -3; i <= 3; i++) {
+ for (int j = -3; j <= 3; j++) {
+ // Range [-9,9]: unsafe.
+ a[i * j] += 1;
+ }
+ }
+ } catch (Exception e) {
+ a[0] += 1000;
+ }
+ return a;
+ }
+
/// CHECK-START: int Main.linearDynamicBCE1(int[], int, int) BCE (before)
/// CHECK-DAG: StaticFieldGet
/// CHECK-DAG: NullCheck
@@ -777,6 +942,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
/// CHECK-DAG: StaticFieldSet
+ //
/// CHECK-START: int Main.linearDynamicBCE1(int[], int, int) BCE (after)
/// CHECK-DAG: StaticFieldGet
/// CHECK-NOT: NullCheck
@@ -803,6 +969,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
/// CHECK-DAG: StaticFieldSet
+ //
/// CHECK-START: int Main.linearDynamicBCE2(int[], int, int, int) BCE (after)
/// CHECK-DAG: StaticFieldGet
/// CHECK-NOT: NullCheck
@@ -827,6 +994,7 @@
/// CHECK-DAG: ArrayLength
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
+ //
/// CHECK-START: int Main.wrapAroundDynamicBCE(int[]) BCE (after)
/// CHECK-DAG: Deoptimize
/// CHECK-DAG: Deoptimize
@@ -850,6 +1018,7 @@
/// CHECK-DAG: ArrayLength
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
+ //
/// CHECK-START: int Main.periodicDynamicBCE(int[]) BCE (after)
/// CHECK-DAG: Deoptimize
/// CHECK-DAG: Deoptimize
@@ -873,6 +1042,7 @@
/// CHECK-DAG: ArrayLength
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
+ //
/// CHECK-START: int Main.dynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (after)
/// CHECK-NOT: NullCheck
/// CHECK-NOT: ArrayLength
@@ -897,6 +1067,7 @@
/// CHECK-DAG: ArrayLength
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
+ //
/// CHECK-START: int Main.noDynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (after)
/// CHECK-DAG: NullCheck
/// CHECK-DAG: ArrayLength
@@ -918,6 +1089,7 @@
/// CHECK-DAG: ArrayLength
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
+ //
/// CHECK-START: int Main.noDynamicBCEMixedInductionTypes(int[], long, long) BCE (after)
/// CHECK-DAG: NullCheck
/// CHECK-DAG: ArrayLength
@@ -951,6 +1123,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: BoundsCheck
+ //
/// CHECK-START: int Main.dynamicBCEAndConstantIndices(int[], int[][], int, int) BCE (after)
/// CHECK-DAG: NullCheck
/// CHECK-DAG: ArrayLength
@@ -1015,6 +1188,7 @@
/// CHECK-DAG: ArrayGet
/// CHECK-DAG: BoundsCheck
/// CHECK-DAG: ArrayGet
+ //
/// CHECK-START: int Main.dynamicBCEAndConstantIndicesAllTypes(int[], boolean[], byte[], char[], short[], int[], long[], float[], double[], java.lang.Integer[], int, int) BCE (after)
/// CHECK-DAG: If
/// CHECK-NOT: BoundsCheck
@@ -1087,6 +1261,8 @@
expectEquals(55, linearObscure(x));
expectEquals(0, linearVeryObscure(empty));
expectEquals(55, linearVeryObscure(x));
+ expectEquals(0, hiddenStride(empty));
+ expectEquals(55, hiddenStride(x));
expectEquals(0, linearWhile(empty));
expectEquals(55, linearWhile(x));
expectEquals(0, linearThreeWayPhi(empty));
@@ -1144,6 +1320,7 @@
linearTriangularOnTwoArrayLengths(10);
linearTriangularOnOneArrayLength(10);
linearTriangularOnParameter(10);
+ linearTriangularVariations(10);
// Sorting.
int[] sort = { 5, 4, 1, 9, 10, 2, 7, 6, 3, 8 };
@@ -1234,6 +1411,20 @@
}
expectEquals(1055, sResult);
+ // Multiplication.
+ {
+ int[] e1 = { 7, 1, 2, 2, 1, 0, 2, 0, 0, 1 };
+ int[] a1 = multiply1();
+ for (int i = 0; i < 10; i++) {
+ expectEquals(a1[i], e1[i]);
+ }
+ int[] e2 = { 1001, 0, 0, 1, 0, 0, 1, 0, 0, 1 };
+ int[] a2 = multiply2();
+ for (int i = 0; i < 10; i++) {
+ expectEquals(a2[i], e2[i]);
+ }
+ }
+
// Dynamic BCE.
sResult = 0;
try {
