diff options
| -rw-r--r-- | compiler/optimizing/induction_var_analysis.cc | 166 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_analysis.h | 20 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_analysis_test.cc | 7 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range.cc | 343 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range.h | 103 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range_test.cc | 341 |
6 files changed, 960 insertions, 20 deletions
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc index 300ffbe03d..3f5a6e7993 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -98,6 +98,9 @@ void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) { DCHECK(stack_.empty()); map_.clear(); + + // Determine the loop's trip count. + VisitControl(loop); } void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) { @@ -346,7 +349,7 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(Inducti HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferShl(InductionInfo* a, InductionInfo* b, - Primitive::Type t) { + Primitive::Type type) { // Transfer over a shift left: treat shift by restricted constant as equivalent multiplication. int64_t value = -1; if (a != nullptr && IsIntAndGet(b, &value)) { @@ -355,10 +358,9 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferShl(Inducti // The restriction on the shift factor avoids generating a negative constant // (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that generalization // for shift factors outside [0,32) and [0,64) ranges is done by earlier simplification. - if (t == Primitive::kPrimInt && 0 <= value && value < 31) { - return TransferMul(a, CreateInvariantFetch(graph_->GetIntConstant(1 << value))); - } else if (t == Primitive::kPrimLong && 0 <= value && value < 63) { - return TransferMul(a, CreateInvariantFetch(graph_->GetLongConstant(1L << value))); + if ((type == Primitive::kPrimInt && 0 <= value && value < 31) || + (type == Primitive::kPrimLong && 0 <= value && value < 63)) { + return TransferMul(a, CreateConstant(1 << value, type)); } } return nullptr; @@ -458,6 +460,111 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopIn return nullptr; } +void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) { + HInstruction* control = loop->GetHeader()->GetLastInstruction(); + if (control->IsIf()) { + HIf* ifs = control->AsIf(); + HBasicBlock* if_true = ifs->IfTrueSuccessor(); + HBasicBlock* if_false = ifs->IfFalseSuccessor(); + HInstruction* if_expr = ifs->InputAt(0); + // Determine if loop has following structure in header. + // loop-header: .... + // if (condition) goto X + if (if_expr->IsCondition()) { + HCondition* condition = if_expr->AsCondition(); + InductionInfo* a = LookupInfo(loop, condition->InputAt(0)); + InductionInfo* b = LookupInfo(loop, condition->InputAt(1)); + Primitive::Type type = condition->InputAt(0)->GetType(); + // Determine if the loop control uses integral arithmetic and an if-exit (X outside) or an + // if-iterate (X inside), always expressed as if-iterate when passing into VisitCondition(). + if (type != Primitive::kPrimInt && type != Primitive::kPrimLong) { + // Loop control is not 32/64-bit integral. + } else if (a == nullptr || b == nullptr) { + // Loop control is not a sequence. + } else if (if_true->GetLoopInformation() != loop && if_false->GetLoopInformation() == loop) { + VisitCondition(loop, a, b, type, condition->GetOppositeCondition()); + } else if (if_true->GetLoopInformation() == loop && if_false->GetLoopInformation() != loop) { + VisitCondition(loop, a, b, type, condition->GetCondition()); + } + } + } +} + +void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, + InductionInfo* a, + InductionInfo* b, + Primitive::Type type, + IfCondition cmp) { + if (a->induction_class == kInvariant && b->induction_class == kLinear) { + // Swap conditions (e.g. U > i is same as i < U). + switch (cmp) { + case kCondLT: VisitCondition(loop, b, a, type, kCondGT); break; + case kCondLE: VisitCondition(loop, b, a, type, kCondGE); break; + case kCondGT: VisitCondition(loop, b, a, type, kCondLT); break; + case kCondGE: VisitCondition(loop, b, a, type, kCondLE); break; + default: break; + } + } else if (a->induction_class == kLinear && b->induction_class == kInvariant) { + // Normalize a linear loop control with a constant, nonzero stride: + // stride > 0, either i < U or i <= U + // stride < 0, either i > U or i >= U + InductionInfo* stride = a->op_a; + InductionInfo* lo_val = a->op_b; + InductionInfo* hi_val = b; + int64_t value = -1; + if (IsIntAndGet(stride, &value)) { + if ((value > 0 && (cmp == kCondLT || cmp == kCondLE)) || + (value < 0 && (cmp == kCondGT || cmp == kCondGE))) { + bool is_strict = cmp == kCondLT || cmp == kCondGT; + VisitTripCount(loop, lo_val, hi_val, stride, value, type, is_strict); + } + } + } +} + +void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, + InductionInfo* lo_val, + InductionInfo* hi_val, + InductionInfo* stride, + int32_t stride_value, + Primitive::Type type, + bool is_strict) { + // Any loop of the general form: + // + // for (i = L; i <= U; i += S) // S > 0 + // or for (i = L; i >= U; i += S) // S < 0 + // .. i .. + // + // can be normalized into: + // + // for (n = 0; n < TC; n++) // where TC = (U + S - L) / S + // .. L + S * n .. + // + // NOTE: The TC (trip-count) expression is only valid if the top-test path is taken at + // least once. Otherwise TC is 0. Also, the expression assumes the loop does not + // have any early-exits. Otherwise, TC is an upper bound. + // + bool cancels = is_strict && abs(stride_value) == 1; // compensation cancels conversion? + if (!cancels) { + // Convert exclusive integral inequality into inclusive integral inequality, + // viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1. + if (is_strict) { + const InductionOp op = stride_value > 0 ? kSub : kAdd; + hi_val = CreateInvariantOp(op, hi_val, CreateConstant(1, type)); + } + // Compensate for stride. + hi_val = CreateInvariantOp(kAdd, hi_val, stride); + } + + // Assign the trip-count expression to the loop control. Clients that use the information + // should be aware that due to the L <= U assumption, the expression is only valid in the + // loop-body proper, and not yet in the loop-header. If the loop has any early exits, the + // trip-count forms a conservative upper bound on the number of loop iterations. + InductionInfo* trip_count = + CreateInvariantOp(kDiv, CreateInvariantOp(kSub, hi_val, lo_val), stride); + AssignInfo(loop, loop->GetHeader()->GetLastInstruction(), trip_count); +} + void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info) { @@ -487,6 +594,15 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInf return nullptr; } +HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateConstant(int64_t value, + Primitive::Type type) { + if (type == Primitive::kPrimInt) { + return CreateInvariantFetch(graph_->GetIntConstant(value)); + } + DCHECK_EQ(type, Primitive::kPrimLong); + return CreateInvariantFetch(graph_->GetLongConstant(value)); +} + HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant( InductionOp op, InductionInfo* a, @@ -504,30 +620,44 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv } else if (op == kMul) { return a; } - } else if (value == 1 && op == kMul) { - // Simplify 1 * b = b. - return b; + } else if (op == kMul) { + // Simplify 1 * b = b, -1 * b = -b + if (value == 1) { + return b; + } else if (value == -1) { + op = kNeg; + a = nullptr; + } } } if (IsIntAndGet(b, &value)) { if (value == 0) { - // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, - 0 = 0. + // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, -0 = 0. if (op == kAdd || op == kSub) { return a; } else if (op == kMul || op == kNeg) { return b; } - } else if (value == 1 && (op == kMul || op == kDiv)) { - // Simplify a * 1 = a, a / 1 = a. - return a; + } else if (op == kMul || op == kDiv) { + // Simplify a * 1 = a, a / 1 = a, a * -1 = -a, a / -1 = -a + if (value == 1) { + return a; + } else if (value == -1) { + op = kNeg; + b = a; + a = nullptr; + } } } else if (b->operation == kNeg) { - // Simplify a + (-b) = a - b, a - (-b) = a + b, - (-b) = b. - switch (op) { - case kAdd: op = kSub; b = b->op_b; break; - case kSub: op = kAdd; b = b->op_b; break; - case kNeg: return b->op_b; - default: break; + // Simplify a + (-b) = a - b, a - (-b) = a + b, -(-b) = b. + if (op == kAdd) { + op = kSub; + b = b->op_b; + } else if (op == kSub) { + op = kAdd; + b = b->op_b; + } else if (op == kNeg) { + return b->op_b; } } return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr); diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h index 180d1f7148..8eccf925c1 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -126,7 +126,7 @@ class HInductionVarAnalysis : public HOptimization { InductionInfo* TransferPhi(InductionInfo* a, InductionInfo* b); InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op); InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b); - InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type t); + InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type); InductionInfo* TransferNeg(InductionInfo* a); // Solvers. @@ -142,9 +142,25 @@ class HInductionVarAnalysis : public HOptimization { bool is_first_call); InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last); + // Trip count information. + void VisitControl(HLoopInformation* loop); + void VisitCondition(HLoopInformation* loop, + InductionInfo* a, + InductionInfo* b, + Primitive::Type type, + IfCondition cmp); + void VisitTripCount(HLoopInformation* loop, + InductionInfo* lo_val, + InductionInfo* hi_val, + InductionInfo* stride, + int32_t stride_value, + Primitive::Type type, + bool is_strict); + // Assign and lookup. void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction); + InductionInfo* CreateConstant(int64_t value, Primitive::Type type); InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b); // Helpers. @@ -168,6 +184,8 @@ class HInductionVarAnalysis : public HOptimization { ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_; friend class InductionVarAnalysisTest; + friend class InductionVarRange; + friend class InductionVarRangeTest; DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis); }; diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc index cfd0b16f23..fca1ca55e5 100644 --- a/compiler/optimizing/induction_var_analysis_test.cc +++ b/compiler/optimizing/induction_var_analysis_test.cc @@ -99,7 +99,7 @@ class InductionVarAnalysisTest : public testing::Test { loop_preheader_[d]->AddInstruction(new (&allocator_) HStoreLocal(basic_[d], constant0_)); HInstruction* load = new (&allocator_) HLoadLocal(basic_[d], Primitive::kPrimInt); loop_header_[d]->AddInstruction(load); - HInstruction* compare = new (&allocator_) HGreaterThanOrEqual(load, constant100_); + HInstruction* compare = new (&allocator_) HLessThan(load, constant100_); loop_header_[d]->AddInstruction(compare); loop_header_[d]->AddInstruction(new (&allocator_) HIf(compare)); load = new (&allocator_) HLoadLocal(basic_[d], Primitive::kPrimInt); @@ -231,6 +231,9 @@ TEST_F(InductionVarAnalysisTest, FindBasicInduction) { EXPECT_STREQ("((1) * i + (0))", GetInductionInfo(store->InputAt(1), 0).c_str()); EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[0], 0).c_str()); + + // Trip-count. + EXPECT_STREQ("(100)", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); } TEST_F(InductionVarAnalysisTest, FindDerivedInduction) { @@ -546,6 +549,8 @@ TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) { EXPECT_STREQ("", GetInductionInfo(store->InputAt(1), d).c_str()); } EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[d], d).c_str()); + // Trip-count. + EXPECT_STREQ("(100)", GetInductionInfo(loop_header_[d]->GetLastInstruction(), d).c_str()); } } diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc new file mode 100644 index 0000000000..bd903340ad --- /dev/null +++ b/compiler/optimizing/induction_var_range.cc @@ -0,0 +1,343 @@ +/* + * Copyright (C) 2015 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <limits.h> + +#include "induction_var_range.h" + +namespace art { + +static bool IsValidConstant32(int32_t c) { + return INT_MIN < c && c < INT_MAX; +} + +static bool IsValidConstant64(int64_t c) { + return INT_MIN < c && c < INT_MAX; +} + +/** Returns true if 32-bit addition can be done safely (and is not an unknown range). */ +static bool IsSafeAdd(int32_t c1, int32_t c2) { + if (IsValidConstant32(c1) && IsValidConstant32(c2)) { + return IsValidConstant64(static_cast<int64_t>(c1) + static_cast<int64_t>(c2)); + } + return false; +} + +/** Returns true if 32-bit subtraction can be done safely (and is not an unknown range). */ +static bool IsSafeSub(int32_t c1, int32_t c2) { + if (IsValidConstant32(c1) && IsValidConstant32(c2)) { + return IsValidConstant64(static_cast<int64_t>(c1) - static_cast<int64_t>(c2)); + } + return false; +} + +/** Returns true if 32-bit multiplication can be done safely (and is not an unknown range). */ +static bool IsSafeMul(int32_t c1, int32_t c2) { + if (IsValidConstant32(c1) && IsValidConstant32(c2)) { + return IsValidConstant64(static_cast<int64_t>(c1) * static_cast<int64_t>(c2)); + } + return false; +} + +/** Returns true if 32-bit division can be done safely (and is not an unknown range). */ +static bool IsSafeDiv(int32_t c1, int32_t c2) { + if (IsValidConstant32(c1) && IsValidConstant32(c2) && c2 != 0) { + return IsValidConstant64(static_cast<int64_t>(c1) / static_cast<int64_t>(c2)); + } + return false; +} + +/** Returns true for 32/64-bit integral constant within known range. */ +static bool IsIntAndGet(HInstruction* instruction, int32_t* value) { + if (instruction->IsIntConstant()) { + const int32_t c = instruction->AsIntConstant()->GetValue(); + if (IsValidConstant32(c)) { + *value = c; + return true; + } + } else if (instruction->IsLongConstant()) { + const int64_t c = instruction->AsLongConstant()->GetValue(); + if (IsValidConstant64(c)) { + *value = c; + return true; + } + } + return false; +} + +// +// Public class methods. +// + +InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis) + : induction_analysis_(induction_analysis) { +} + +InductionVarRange::Value InductionVarRange::GetMinInduction(HInstruction* context, + HInstruction* instruction) { + HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); + if (loop != nullptr && induction_analysis_ != nullptr) { + return GetMin(induction_analysis_->LookupInfo(loop, instruction), GetTripCount(loop, context)); + } + return Value(INT_MIN); +} + +InductionVarRange::Value InductionVarRange::GetMaxInduction(HInstruction* context, + HInstruction* instruction) { + HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); + if (loop != nullptr && induction_analysis_ != nullptr) { + return GetMax(induction_analysis_->LookupInfo(loop, instruction), GetTripCount(loop, context)); + } + return Value(INT_MAX); +} + +// +// Private class methods. +// + +HInductionVarAnalysis::InductionInfo* InductionVarRange::GetTripCount(HLoopInformation* loop, + HInstruction* context) { + // The trip-count expression is only valid when the top-test is taken at least once, + // that means, when the analyzed context appears outside the loop header itself. + // Early-exit loops are okay, since in those cases, the trip-count is conservative. + if (context->GetBlock() != loop->GetHeader()) { + HInductionVarAnalysis::InductionInfo* trip = + induction_analysis_->LookupInfo(loop, loop->GetHeader()->GetLastInstruction()); + if (trip != nullptr) { + // Wrap the trip-count representation in its own unusual NOP node, so that range analysis + // is able to determine the [0, TC - 1] interval without having to construct constants. + return induction_analysis_->CreateInvariantOp(HInductionVarAnalysis::kNop, trip, trip); + } + } + return nullptr; +} + +InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, + int32_t fail_value) { + // Detect constants and chase the fetch a bit deeper into the HIR tree, so that it becomes + // more likely range analysis will compare the same instructions as terminal nodes. + int32_t value; + if (IsIntAndGet(instruction, &value)) { + return Value(value); + } else if (instruction->IsAdd()) { + if (IsIntAndGet(instruction->InputAt(0), &value)) { + return AddValue(Value(value), GetFetch(instruction->InputAt(1), fail_value), fail_value); + } else if (IsIntAndGet(instruction->InputAt(1), &value)) { + return AddValue(GetFetch(instruction->InputAt(0), fail_value), Value(value), fail_value); + } + } + return Value(instruction, 1, 0); +} + +InductionVarRange::Value InductionVarRange::GetMin(HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* trip) { + if (info != nullptr) { + switch (info->induction_class) { + case HInductionVarAnalysis::kInvariant: + // Invariants. + switch (info->operation) { + case HInductionVarAnalysis::kNop: // normalized: 0 + DCHECK_EQ(info->op_a, info->op_b); + return Value(0); + case HInductionVarAnalysis::kAdd: + return AddValue(GetMin(info->op_a, trip), GetMin(info->op_b, trip), INT_MIN); + case HInductionVarAnalysis::kSub: // second max! + return SubValue(GetMin(info->op_a, trip), GetMax(info->op_b, trip), INT_MIN); + case HInductionVarAnalysis::kNeg: // second max! + return SubValue(Value(0), GetMax(info->op_b, trip), INT_MIN); + case HInductionVarAnalysis::kMul: + return GetMul(info->op_a, info->op_b, trip, INT_MIN); + case HInductionVarAnalysis::kDiv: + return GetDiv(info->op_a, info->op_b, trip, INT_MIN); + case HInductionVarAnalysis::kFetch: + return GetFetch(info->fetch, INT_MIN); + } + break; + case HInductionVarAnalysis::kLinear: + // Minimum over linear induction a * i + b, for normalized 0 <= i < TC. + return AddValue(GetMul(info->op_a, trip, trip, INT_MIN), + GetMin(info->op_b, trip), INT_MIN); + case HInductionVarAnalysis::kWrapAround: + case HInductionVarAnalysis::kPeriodic: + // Minimum over all values in the wrap-around/periodic. + return MinValue(GetMin(info->op_a, trip), GetMin(info->op_b, trip)); + } + } + return Value(INT_MIN); +} + +InductionVarRange::Value InductionVarRange::GetMax(HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* trip) { + if (info != nullptr) { + switch (info->induction_class) { + case HInductionVarAnalysis::kInvariant: + // Invariants. + switch (info->operation) { + case HInductionVarAnalysis::kNop: // normalized: TC - 1 + DCHECK_EQ(info->op_a, info->op_b); + return SubValue(GetMax(info->op_b, trip), Value(1), INT_MAX); + case HInductionVarAnalysis::kAdd: + return AddValue(GetMax(info->op_a, trip), GetMax(info->op_b, trip), INT_MAX); + case HInductionVarAnalysis::kSub: // second min! + return SubValue(GetMax(info->op_a, trip), GetMin(info->op_b, trip), INT_MAX); + case HInductionVarAnalysis::kNeg: // second min! + return SubValue(Value(0), GetMin(info->op_b, trip), INT_MAX); + case HInductionVarAnalysis::kMul: + return GetMul(info->op_a, info->op_b, trip, INT_MAX); + case HInductionVarAnalysis::kDiv: + return GetDiv(info->op_a, info->op_b, trip, INT_MAX); + case HInductionVarAnalysis::kFetch: + return GetFetch(info->fetch, INT_MAX); + } + break; + case HInductionVarAnalysis::kLinear: + // Maximum over linear induction a * i + b, for normalized 0 <= i < TC. + return AddValue(GetMul(info->op_a, trip, trip, INT_MAX), + GetMax(info->op_b, trip), INT_MAX); + case HInductionVarAnalysis::kWrapAround: + case HInductionVarAnalysis::kPeriodic: + // Maximum over all values in the wrap-around/periodic. + return MaxValue(GetMax(info->op_a, trip), GetMax(info->op_b, trip)); + } + } + return Value(INT_MAX); +} + +InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1, + HInductionVarAnalysis::InductionInfo* info2, + HInductionVarAnalysis::InductionInfo* trip, + int32_t fail_value) { + Value v1_min = GetMin(info1, trip); + Value v1_max = GetMax(info1, trip); + Value v2_min = GetMin(info2, trip); + Value v2_max = GetMax(info2, trip); + if (v1_min.a_constant == 0 && v1_min.b_constant >= 0) { + // Positive range vs. positive or negative range. + if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) { + return (fail_value < 0) ? MulValue(v1_min, v2_min, fail_value) + : MulValue(v1_max, v2_max, fail_value); + } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) { + return (fail_value < 0) ? MulValue(v1_max, v2_min, fail_value) + : MulValue(v1_min, v2_max, fail_value); + } + } else if (v1_min.a_constant == 0 && v1_min.b_constant <= 0) { + // Negative range vs. positive or negative range. + if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) { + return (fail_value < 0) ? MulValue(v1_min, v2_max, fail_value) + : MulValue(v1_max, v2_min, fail_value); + } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) { + return (fail_value < 0) ? MulValue(v1_max, v2_max, fail_value) + : MulValue(v1_min, v2_min, fail_value); + } + } + return Value(fail_value); +} + +InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1, + HInductionVarAnalysis::InductionInfo* info2, + HInductionVarAnalysis::InductionInfo* trip, + int32_t fail_value) { + Value v1_min = GetMin(info1, trip); + Value v1_max = GetMax(info1, trip); + Value v2_min = GetMin(info2, trip); + Value v2_max = GetMax(info2, trip); + if (v1_min.a_constant == 0 && v1_min.b_constant >= 0) { + // Positive range vs. positive or negative range. + if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) { + return (fail_value < 0) ? DivValue(v1_min, v2_max, fail_value) + : DivValue(v1_max, v2_min, fail_value); + } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) { + return (fail_value < 0) ? DivValue(v1_max, v2_max, fail_value) + : DivValue(v1_min, v2_min, fail_value); + } + } else if (v1_min.a_constant == 0 && v1_min.b_constant <= 0) { + // Negative range vs. positive or negative range. + if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) { + return (fail_value < 0) ? DivValue(v1_min, v2_min, fail_value) + : DivValue(v1_max, v2_max, fail_value); + } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) { + return (fail_value < 0) ? DivValue(v1_max, v2_min, fail_value) + : DivValue(v1_min, v2_max, fail_value); + } + } + return Value(fail_value); +} + +InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2, int32_t fail_value) { + if (IsSafeAdd(v1.b_constant, v2.b_constant)) { + const int32_t b = v1.b_constant + v2.b_constant; + if (v1.a_constant == 0) { + return Value(v2.instruction, v2.a_constant, b); + } else if (v2.a_constant == 0) { + return Value(v1.instruction, v1.a_constant, b); + } else if (v1.instruction == v2.instruction && IsSafeAdd(v1.a_constant, v2.a_constant)) { + return Value(v1.instruction, v1.a_constant + v2.a_constant, b); + } + } + return Value(fail_value); +} + +InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2, int32_t fail_value) { + if (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)) { + return Value(v2.instruction, -v2.a_constant, b); + } else if (v2.a_constant == 0) { + return Value(v1.instruction, v1.a_constant, b); + } else if (v1.instruction == v2.instruction && IsSafeSub(v1.a_constant, v2.a_constant)) { + return Value(v1.instruction, v1.a_constant - v2.a_constant, b); + } + } + return Value(fail_value); +} + +InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2, int32_t fail_value) { + if (v1.a_constant == 0) { + if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) { + return Value(v2.instruction, v1.b_constant * v2.a_constant, v1.b_constant * v2.b_constant); + } + } else if (v2.a_constant == 0) { + if (IsSafeMul(v1.a_constant, v2.b_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) { + return Value(v1.instruction, v1.a_constant * v2.b_constant, v1.b_constant * v2.b_constant); + } + } + return Value(fail_value); +} + +InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2, int32_t fail_value) { + if (v1.a_constant == 0 && v2.a_constant == 0) { + if (IsSafeDiv(v1.b_constant, v2.b_constant)) { + return Value(v1.b_constant / v2.b_constant); + } + } + return Value(fail_value); +} + +InductionVarRange::Value InductionVarRange::MinValue(Value v1, Value v2) { + if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) { + return Value(v1.instruction, v1.a_constant, std::min(v1.b_constant, v2.b_constant)); + } + return Value(INT_MIN); +} + +InductionVarRange::Value InductionVarRange::MaxValue(Value v1, Value v2) { + if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) { + return Value(v1.instruction, v1.a_constant, std::max(v1.b_constant, v2.b_constant)); + } + return Value(INT_MAX); +} + +} // namespace art diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h new file mode 100644 index 0000000000..b079076852 --- /dev/null +++ b/compiler/optimizing/induction_var_range.h @@ -0,0 +1,103 @@ +/* + * Copyright (C) 2015 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ +#define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ + +#include "induction_var_analysis.h" + +namespace art { + +/** + * This class implements induction variable based range analysis on expressions within loops. + * It takes the results of induction variable analysis in the constructor and provides a public + * API to obtain a conservative lower and upper bound value on each instruction in the HIR. + * + * For example, given a linear induction 2 * i + x where 0 <= i <= 10, range analysis yields lower + * bound value x and upper bound value x + 20 for the expression, thus, the range [0, x + 20]. + */ +class InductionVarRange { + public: + /* + * A value that can be represented as "a * instruction + b" for 32-bit constants, where + * Value(INT_MIN) and Value(INT_MAX) denote an unknown lower and upper bound, respectively. + * Although range analysis could yield more complex values, the format is sufficiently powerful + * to represent useful cases and feeds directly into optimizations like bounds check elimination. + */ + struct Value { + Value(HInstruction* i, int32_t a, int32_t b) + : instruction(a ? i : nullptr), + a_constant(a), + b_constant(b) {} + explicit Value(int32_t b) : Value(nullptr, 0, b) {} + HInstruction* instruction; + int32_t a_constant; + int32_t b_constant; + }; + + explicit InductionVarRange(HInductionVarAnalysis* induction); + + /** + * Given a context denoted by the first instruction, returns a, + * possibly conservative, lower bound on the instruction's value. + */ + Value GetMinInduction(HInstruction* context, HInstruction* instruction); + + /** + * Given a context denoted by the first instruction, returns a, + * possibly conservative, upper bound on the instruction's value. + */ + Value GetMaxInduction(HInstruction* context, HInstruction* instruction); + + private: + // + // Private helper methods. + // + + HInductionVarAnalysis::InductionInfo* GetTripCount(HLoopInformation* loop, + HInstruction* context); + + static Value GetFetch(HInstruction* instruction, int32_t fail_value); + + static Value GetMin(HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* trip); + static Value GetMax(HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* trip); + static Value GetMul(HInductionVarAnalysis::InductionInfo* info1, + HInductionVarAnalysis::InductionInfo* info2, + HInductionVarAnalysis::InductionInfo* trip, int32_t fail_value); + static Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, + HInductionVarAnalysis::InductionInfo* info2, + HInductionVarAnalysis::InductionInfo* trip, int32_t fail_value); + + static Value AddValue(Value v1, Value v2, int32_t fail_value); + static Value SubValue(Value v1, Value v2, int32_t fail_value); + static Value MulValue(Value v1, Value v2, int32_t fail_value); + static Value DivValue(Value v1, Value v2, int32_t fail_value); + static Value MinValue(Value v1, Value v2); + static Value MaxValue(Value v1, Value v2); + + /** Results of prior induction variable analysis. */ + HInductionVarAnalysis *induction_analysis_; + + friend class InductionVarRangeTest; + + DISALLOW_COPY_AND_ASSIGN(InductionVarRange); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc new file mode 100644 index 0000000000..d3c3518193 --- /dev/null +++ b/compiler/optimizing/induction_var_range_test.cc @@ -0,0 +1,341 @@ +/* + * Copyright (C) 2015 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <limits.h> + +#include "base/arena_allocator.h" +#include "builder.h" +#include "gtest/gtest.h" +#include "induction_var_analysis.h" +#include "induction_var_range.h" +#include "nodes.h" +#include "optimizing_unit_test.h" + +namespace art { + +using Value = InductionVarRange::Value; + +/** + * Fixture class for the InductionVarRange tests. + */ +class InductionVarRangeTest : public testing::Test { + public: + InductionVarRangeTest() : pool_(), allocator_(&pool_) { + graph_ = CreateGraph(&allocator_); + iva_ = new (&allocator_) HInductionVarAnalysis(graph_); + BuildGraph(); + } + + ~InductionVarRangeTest() { } + + void ExpectEqual(Value v1, Value v2) { + EXPECT_EQ(v1.instruction, v2.instruction); + EXPECT_EQ(v1.a_constant, v2.a_constant); + EXPECT_EQ(v1.b_constant, v2.b_constant); + } + + /** Constructs bare minimum graph. */ + void BuildGraph() { + graph_->SetNumberOfVRegs(1); + HBasicBlock* entry_block = new (&allocator_) HBasicBlock(graph_); + HBasicBlock* exit_block = new (&allocator_) HBasicBlock(graph_); + graph_->AddBlock(entry_block); + graph_->AddBlock(exit_block); + graph_->SetEntryBlock(entry_block); + graph_->SetExitBlock(exit_block); + } + + /** Constructs an invariant. */ + HInductionVarAnalysis::InductionInfo* CreateInvariant(char opc, + HInductionVarAnalysis::InductionInfo* a, + HInductionVarAnalysis::InductionInfo* b) { + HInductionVarAnalysis::InductionOp op; + switch (opc) { + case '+': op = HInductionVarAnalysis::kAdd; break; + case '-': op = HInductionVarAnalysis::kSub; break; + case 'n': op = HInductionVarAnalysis::kNeg; break; + case '*': op = HInductionVarAnalysis::kMul; break; + case '/': op = HInductionVarAnalysis::kDiv; break; + default: op = HInductionVarAnalysis::kNop; break; + } + return iva_->CreateInvariantOp(op, a, b); + } + + /** Constructs a fetch. */ + HInductionVarAnalysis::InductionInfo* CreateFetch(HInstruction* fetch) { + return iva_->CreateInvariantFetch(fetch); + } + + /** Constructs a constant. */ + HInductionVarAnalysis::InductionInfo* CreateConst(int32_t c) { + return CreateFetch(graph_->GetIntConstant(c)); + } + + /** Constructs a trip-count. */ + HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc) { + HInductionVarAnalysis::InductionInfo* trip = CreateConst(tc); + return CreateInvariant('@', trip, trip); + } + + /** Constructs a linear a * i + b induction. */ + HInductionVarAnalysis::InductionInfo* CreateLinear(int32_t a, int32_t b) { + return iva_->CreateInduction(HInductionVarAnalysis::kLinear, CreateConst(a), CreateConst(b)); + } + + /** Constructs a range [lo, hi] using a periodic induction. */ + HInductionVarAnalysis::InductionInfo* CreateRange(int32_t lo, int32_t hi) { + return iva_->CreateInduction( + HInductionVarAnalysis::kPeriodic, CreateConst(lo), CreateConst(hi)); + } + + /** Constructs a wrap-around induction consisting of a constant, followed by a range. */ + HInductionVarAnalysis::InductionInfo* CreateWrapAround(int32_t initial, int32_t lo, int32_t hi) { + return iva_->CreateInduction( + HInductionVarAnalysis::kWrapAround, CreateConst(initial), CreateRange(lo, hi)); + } + + // + // Relay methods. + // + + Value GetMin(HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* induc) { + return InductionVarRange::GetMin(info, induc); + } + + Value GetMax(HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* induc) { + return InductionVarRange::GetMax(info, induc); + } + + Value GetMul(HInductionVarAnalysis::InductionInfo* info1, + HInductionVarAnalysis::InductionInfo* info2, int32_t fail_value) { + return InductionVarRange::GetMul(info1, info2, nullptr, fail_value); + } + + Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, + HInductionVarAnalysis::InductionInfo* info2, int32_t fail_value) { + return InductionVarRange::GetDiv(info1, info2, nullptr, fail_value); + } + + Value AddValue(Value v1, Value v2) { return InductionVarRange::AddValue(v1, v2, INT_MIN); } + Value SubValue(Value v1, Value v2) { return InductionVarRange::SubValue(v1, v2, INT_MIN); } + Value MulValue(Value v1, Value v2) { return InductionVarRange::MulValue(v1, v2, INT_MIN); } + Value DivValue(Value v1, Value v2) { return InductionVarRange::DivValue(v1, v2, INT_MIN); } + Value MinValue(Value v1, Value v2) { return InductionVarRange::MinValue(v1, v2); } + Value MaxValue(Value v1, Value v2) { return InductionVarRange::MaxValue(v1, v2); } + + // General building fields. + ArenaPool pool_; + ArenaAllocator allocator_; + HGraph* graph_; + HInductionVarAnalysis* iva_; + + // Two dummy instructions. + HReturnVoid x_; + HReturnVoid y_; +}; + +// +// The actual InductionVarRange tests. +// + +TEST_F(InductionVarRangeTest, GetMinMaxNull) { + ExpectEqual(Value(INT_MIN), GetMin(nullptr, nullptr)); + ExpectEqual(Value(INT_MAX), GetMax(nullptr, nullptr)); +} + +TEST_F(InductionVarRangeTest, GetMinMaxAdd) { + ExpectEqual(Value(12), + 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(5), + GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); + ExpectEqual(Value(19), + GetMax(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); +} + +TEST_F(InductionVarRangeTest, GetMinMaxSub) { + ExpectEqual(Value(-18), + 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(-25), + GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); + ExpectEqual(Value(-11), + GetMax(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); +} + +TEST_F(InductionVarRangeTest, GetMinMaxNeg) { + ExpectEqual(Value(-20), GetMin(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); + 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)); +} + +TEST_F(InductionVarRangeTest, GetMinMaxMul) { + ExpectEqual(Value(20), + GetMin(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); + ExpectEqual(Value(40), + GetMax(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); +} + +TEST_F(InductionVarRangeTest, GetMinMaxDiv) { + ExpectEqual(Value(3), + GetMin(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); + ExpectEqual(Value(5), + GetMax(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); +} + +TEST_F(InductionVarRangeTest, GetMinMaxConstant) { + ExpectEqual(Value(12345), GetMin(CreateConst(12345), nullptr)); + ExpectEqual(Value(12345), GetMax(CreateConst(12345), nullptr)); +} + +TEST_F(InductionVarRangeTest, GetMinMaxFetch) { + ExpectEqual(Value(&x_, 1, 0), GetMin(CreateFetch(&x_), nullptr)); + ExpectEqual(Value(&x_, 1, 0), GetMax(CreateFetch(&x_), nullptr)); +} + +TEST_F(InductionVarRangeTest, GetMinMaxLinear) { + ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100))); + ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100))); + ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100))); + ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100))); +} + +TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) { + ExpectEqual(Value(-5), GetMin(CreateWrapAround(-5, -1, 10), nullptr)); + ExpectEqual(Value(10), GetMax(CreateWrapAround(-5, -1, 10), nullptr)); + ExpectEqual(Value(-1), GetMin(CreateWrapAround(2, -1, 10), nullptr)); + ExpectEqual(Value(10), GetMax(CreateWrapAround(2, -1, 10), nullptr)); + ExpectEqual(Value(-1), GetMin(CreateWrapAround(20, -1, 10), nullptr)); + ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr)); +} + +TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) { + ExpectEqual(Value(-2), GetMin(CreateRange(-2, 99), nullptr)); + ExpectEqual(Value(99), GetMax(CreateRange(-2, 99), nullptr)); +} + +TEST_F(InductionVarRangeTest, GetMulMin) { + ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), INT_MIN)); + ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), INT_MIN)); + ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), INT_MIN)); + ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), INT_MIN)); +} + +TEST_F(InductionVarRangeTest, GetMulMax) { + ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), INT_MAX)); + ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), INT_MAX)); + ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), INT_MAX)); + ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), INT_MAX)); +} + +TEST_F(InductionVarRangeTest, GetDivMin) { + ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), INT_MIN)); + ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), INT_MIN)); + ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), INT_MIN)); + ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), INT_MIN)); +} + +TEST_F(InductionVarRangeTest, GetDivMax) { + ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), INT_MAX)); + ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), INT_MAX)); + ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), INT_MAX)); + ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), INT_MAX)); +} + +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(INT_MIN), 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))); + // Unsafe. + ExpectEqual(Value(INT_MIN), AddValue(Value(INT_MAX - 5), Value(6))); +} + +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(INT_MIN), 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))); + // Unsafe. + ExpectEqual(Value(INT_MIN), SubValue(Value(INT_MIN + 5), Value(6))); +} + +TEST_F(InductionVarRangeTest, MulValue) { + ExpectEqual(Value(1000), MulValue(Value(10), Value(100))); + ExpectEqual(Value(INT_MIN), MulValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); + ExpectEqual(Value(INT_MIN), 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))); + // Unsafe. + ExpectEqual(Value(INT_MIN), MulValue(Value(90000), Value(-90000))); +} + +TEST_F(InductionVarRangeTest, DivValue) { + ExpectEqual(Value(25), DivValue(Value(100), Value(4))); + ExpectEqual(Value(INT_MIN), DivValue(Value(&x_, 1, -4), Value(&x_, 1, -1))); + ExpectEqual(Value(INT_MIN), DivValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); + ExpectEqual(Value(INT_MIN), DivValue(Value(&x_, 12, 24), Value(3))); + ExpectEqual(Value(INT_MIN), DivValue(Value(55), Value(&y_, 1, -50))); + // Unsafe. + ExpectEqual(Value(INT_MIN), DivValue(Value(1), Value(0))); +} + +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(INT_MIN), MinValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); + ExpectEqual(Value(INT_MIN), MinValue(Value(&x_, 1, 20), Value(3))); + ExpectEqual(Value(INT_MIN), 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(INT_MAX), MaxValue(Value(&x_, 1, 5), Value(&y_, 1, -7))); + ExpectEqual(Value(INT_MAX), MaxValue(Value(&x_, 1, 20), Value(3))); + ExpectEqual(Value(INT_MAX), MaxValue(Value(55), Value(&y_, 1, -50))); +} + +} // namespace art |