diff options
| -rw-r--r-- | compiler/optimizing/induction_var_analysis.cc | 71 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_analysis.h | 4 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range.cc | 119 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range.h | 92 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range_test.cc | 286 | ||||
| -rw-r--r-- | test/530-checker-loops/src/Main.java | 193 |
6 files changed, 523 insertions, 242 deletions
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc index 0b7fdf85ea..19e6cbd314 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -71,10 +71,10 @@ HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph) } 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv if (value == 1) { return b; } else if (value == -1) { - op = kNeg; - a = nullptr; + return CreateSimplifiedInvariant(kNeg, nullptr, b); } } } @@ -763,41 +762,27 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv 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::InductionEqual(InductionInfo* info1, - InductionInfo* info2) { - // Test structural equality only, without accounting for simplifications. - if (info1 != nullptr && info2 != nullptr) { - return - info1->induction_class == info2->induction_class && - info1->operation == info2->operation && - info1->fetch == info2->fetch && - InductionEqual(info1->op_a, info2->op_a) && - InductionEqual(info1->op_b, info2->op_b); - } - // Otherwise only two nullptrs are considered equal. - return info1 == info2; -} - bool HInductionVarAnalysis::IsIntAndGet(InductionInfo* info, int64_t* value) { if (info != nullptr && info->induction_class == kInvariant) { // A direct constant fetch. @@ -812,19 +797,35 @@ bool HInductionVarAnalysis::IsIntAndGet(InductionInfo* info, int64_t* value) { } } // Use range analysis to resolve compound values. - int32_t range_value; - if (InductionVarRange::GetConstant(info, &range_value)) { - *value = range_value; + 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. + if (info1 != nullptr && info2 != nullptr) { + return + info1->induction_class == info2->induction_class && + info1->operation == info2->operation && + info1->fetch == info2->fetch && + InductionEqual(info1->op_a, info2->op_a) && + InductionEqual(info1->op_b, info2->op_b); + } + // Otherwise only two nullptrs are considered equal. + return info1 == info2; +} + 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 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) { 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 cf354093f2..84d5d82568 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -188,9 +188,11 @@ class HInductionVarAnalysis : public HOptimization { 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 9d0cde7c9f..ae15fcf381 100644 --- a/compiler/optimizing/induction_var_range.cc +++ b/compiler/optimizing/induction_var_range.cc @@ -119,7 +119,7 @@ void InductionVarRange::GetInductionRange(HInstruction* context, } } -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 @@ void InductionVarRange::GenerateTakenTest(HInstruction* context, // 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 @@ bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* inf 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 @@ bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* tr 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 @@ bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* 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::GetFetch(HInstruction* instruction, 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 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct 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 @@ InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::Induct 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 @@ InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::Induct 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 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct 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 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct 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 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct 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 @@ InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) { 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 @@ InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) { 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 @@ InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) { 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 @@ InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) { 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 @@ InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is 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 @@ bool InductionVarRange::GenerateCode(HInstruction* context, /*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 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, 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 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, 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 71b0b1b4c3..974b8fba06 100644 --- a/compiler/optimizing/induction_var_range.h +++ b/compiler/optimizing/induction_var_range.h @@ -69,7 +69,7 @@ class InductionVarRange { /*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 @@ class InductionVarRange { /*out*/HInstruction** taken_test); private: - // - // Private helper methods. - // - - static bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info); - static bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip); - static bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip); - - static Value GetFetch(HInstruction* instruction, - HInductionVarAnalysis::InductionInfo* trip, - 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); - - 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); + bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const; + bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const; + bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const; + + 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; + + bool IsConstantRange(HInductionVarAnalysis::InductionInfo* info, + int32_t *min_value, + int32_t *max_value) const; + + 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 @@ class InductionVarRange { /*out*/HInstruction** upper, /*out*/HInstruction** taken_test, /*out*/bool* needs_finite_test, - /*out*/bool* needs_taken_test); - - static bool GenerateCode(HInductionVarAnalysis::InductionInfo* info, - HInductionVarAnalysis::InductionInfo* trip, - HGraph* graph, - HBasicBlock* block, - /*out*/HInstruction** result, - bool in_body, - bool is_min); + /*out*/bool* needs_taken_test) const; + + 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 a1c797a80a..eda9c01a01 100644 --- a/compiler/optimizing/induction_var_range_test.cc +++ b/compiler/optimizing/induction_var_range_test.cc @@ -30,9 +30,12 @@ using Value = InductionVarRange::Value; */ 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 @@ class InductionVarRangeTest : public CommonCompilerTest { 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 @@ class InductionVarRangeTest : public CommonCompilerTest { 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 @@ class InductionVarRangeTest : public CommonCompilerTest { // 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 @@ class InductionVarRangeTest : public CommonCompilerTest { 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 @@ TEST_F(InductionVarRangeTest, GetMinMaxAdd) { 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 @@ TEST_F(InductionVarRangeTest, GetMinMaxSub) { 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 @@ TEST_F(InductionVarRangeTest, GetMinMaxNeg) { 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, GetMinMaxConstant) { } 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, GetMinMaxPeriodic) { 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, AddValue) { 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, SubValue) { 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 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { 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, SymbolicTripCountUp) { } 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 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { 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 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { 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 3f6e48bbae..e827b1ed78 100644 --- a/test/530-checker-loops/src/Main.java +++ b/test/530-checker-loops/src/Main.java @@ -27,6 +27,7 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { } } - // 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 @@ public class Main { } } + // 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { } 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { /// 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 @@ public class Main { 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 @@ public class Main { 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 @@ public class Main { } 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 { |