From 52be7e759acecc3841dca0ac1b703034d8cad60d Mon Sep 17 00:00:00 2001 From: Aart Bik Date: Thu, 23 Jun 2016 11:20:41 -0700 Subject: Improvements in induction range analysis. Rationale: Uses range analysis while determining whether trip-counts are "safe", which improves analysis of triangular loops. Also implements more effective triangular loop analysis by evaluating induction information only once and using a top level hint (instead of the "iterative refinement" that was used earlier). Also fixes analysis of triangular trip counts that may wrap-around. All with tests. Test: see induction_var_range_test/530-checker-loops* BUG=27151190 Change-Id: I1877c8ce0c9a52005900eb9dfdbb1918df100278 --- compiler/optimizing/induction_var_range.cc | 311 +++++++++++++++-------------- 1 file changed, 158 insertions(+), 153 deletions(-) (limited to 'compiler/optimizing/induction_var_range.cc') diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc index bc920d96b5..5e587e0810 100644 --- a/compiler/optimizing/induction_var_range.cc +++ b/compiler/optimizing/induction_var_range.cc @@ -73,9 +73,12 @@ static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v) { return v; } -/** - * Corrects a value for type to account for arithmetic wrap-around in lower precision. - */ +/** Helper method to test for a constant value. */ +static bool IsConstantValue(InductionVarRange::Value v) { + return v.is_known && v.a_constant == 0; +} + +/** Corrects a value for type to account for arithmetic wrap-around in lower precision. */ static InductionVarRange::Value CorrectForType(InductionVarRange::Value v, Primitive::Type type) { switch (type) { case Primitive::kPrimShort: @@ -85,26 +88,15 @@ static InductionVarRange::Value CorrectForType(InductionVarRange::Value v, Primi // TODO: maybe some room for improvement, like allowing widening conversions const int32_t min = Primitive::MinValueOfIntegralType(type); const int32_t max = Primitive::MaxValueOfIntegralType(type); - return (v.is_known && v.a_constant == 0 && min <= v.b_constant && v.b_constant <= max) + return (IsConstantValue(v) && min <= v.b_constant && v.b_constant <= max) ? v : InductionVarRange::Value(); } default: - // At int or higher. return v; } } -/** Helper method to test for a constant value. */ -static bool IsConstantValue(InductionVarRange::Value v) { - return v.is_known && v.a_constant == 0; -} - -/** Helper method to test for same constant value. */ -static bool IsSameConstantValue(InductionVarRange::Value v1, InductionVarRange::Value v2) { - return IsConstantValue(v1) && IsConstantValue(v2) && v1.b_constant == v2.b_constant; -} - /** Helper method to insert an instruction. */ static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) { DCHECK(block != nullptr); @@ -119,22 +111,22 @@ static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) { // InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis) - : induction_analysis_(induction_analysis) { + : induction_analysis_(induction_analysis), + chase_hint_(nullptr) { DCHECK(induction_analysis != nullptr); } bool InductionVarRange::GetInductionRange(HInstruction* context, HInstruction* instruction, + HInstruction* chase_hint, /*out*/Value* min_val, /*out*/Value* max_val, /*out*/bool* needs_finite_test) { - HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop - if (loop == nullptr) { - return false; // no loop - } - HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction); - if (info == nullptr) { - return false; // no induction information + HLoopInformation* loop = nullptr; + HInductionVarAnalysis::InductionInfo* info = nullptr; + HInductionVarAnalysis::InductionInfo* trip = nullptr; + if (!HasInductionInfo(context, instruction, &loop, &info, &trip)) { + return false; } // Type int or lower (this is not too restrictive since intended clients, like // bounds check elimination, will have truncated higher precision induction @@ -148,45 +140,15 @@ bool InductionVarRange::GetInductionRange(HInstruction* context, default: return false; } - // Set up loop information. - HBasicBlock* header = loop->GetHeader(); - bool in_body = context->GetBlock() != header; - HInductionVarAnalysis::InductionInfo* trip = - induction_analysis_->LookupInfo(loop, header->GetLastInstruction()); // Find range. + chase_hint_ = chase_hint; + bool in_body = context->GetBlock() != loop->GetHeader(); *min_val = GetVal(info, trip, in_body, /* is_min */ true); *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min */ false)); *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip); return true; } -bool InductionVarRange::RefineOuter(/*in-out*/ Value* min_val, - /*in-out*/ Value* max_val) const { - if (min_val->instruction != nullptr || max_val->instruction != nullptr) { - Value v1_min = RefineOuter(*min_val, /* is_min */ true); - Value v2_max = RefineOuter(*max_val, /* is_min */ false); - // The refined range is safe if both sides refine the same instruction. Otherwise, since two - // different ranges are combined, the new refined range is safe to pass back to the client if - // the extremes of the computed ranges ensure no arithmetic wrap-around anomalies occur. - if (min_val->instruction != max_val->instruction) { - Value v1_max = RefineOuter(*min_val, /* is_min */ false); - Value v2_min = RefineOuter(*max_val, /* is_min */ true); - if (!IsConstantValue(v1_max) || - !IsConstantValue(v2_min) || - v1_max.b_constant > v2_min.b_constant) { - return false; - } - } - // Did something change? - if (v1_min.instruction != min_val->instruction || v2_max.instruction != max_val->instruction) { - *min_val = v1_min; - *max_val = v2_max; - return true; - } - } - return false; -} - bool InductionVarRange::CanGenerateCode(HInstruction* context, HInstruction* instruction, /*out*/bool* needs_finite_test, @@ -226,7 +188,7 @@ void InductionVarRange::GenerateTakenTest(HInstruction* context, bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, ConstantRequest request, - /*out*/ int64_t *value) const { + /*out*/ int64_t* value) const { if (info != nullptr) { // A direct 32-bit or 64-bit constant fetch. This immediately satisfies // any of the three requests (kExact, kAtMost, and KAtLeast). @@ -236,27 +198,16 @@ bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, return true; } } - // Try range analysis while traversing outward on loops. - bool in_body = true; // no known trip count - Value v_min = GetVal(info, nullptr, in_body, /* is_min */ true); - Value v_max = GetVal(info, nullptr, in_body, /* is_min */ false); - do { - // Make sure *both* extremes are known to avoid arithmetic wrap-around anomalies. - if (IsConstantValue(v_min) && IsConstantValue(v_max) && v_min.b_constant <= v_max.b_constant) { - if ((request == kExact && v_min.b_constant == v_max.b_constant) || request == kAtMost) { - *value = v_max.b_constant; - return true; - } else if (request == kAtLeast) { - *value = v_min.b_constant; - return true; - } - } - } while (RefineOuter(&v_min, &v_max)); - // Exploit array length + c >= c, with c <= 0 to avoid arithmetic wrap-around anomalies - // (e.g. array length == maxint and c == 1 would yield minint). - if (request == kAtLeast) { - if (v_min.a_constant == 1 && v_min.b_constant <= 0 && v_min.instruction->IsArrayLength()) { - *value = v_min.b_constant; + // Try range analysis on the invariant, but only on proper range to avoid wrap-around anomalies. + Value min_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ true); + Value max_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ false); + if (IsConstantValue(min_val) && + IsConstantValue(max_val) && min_val.b_constant <= max_val.b_constant) { + if ((request == kExact && min_val.b_constant == max_val.b_constant) || request == kAtMost) { + *value = max_val.b_constant; + return true; + } else if (request == kAtLeast) { + *value = min_val.b_constant; return true; } } @@ -264,6 +215,51 @@ bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, return false; } +bool InductionVarRange::HasInductionInfo( + HInstruction* context, + HInstruction* instruction, + /*out*/ HLoopInformation** loop, + /*out*/ HInductionVarAnalysis::InductionInfo** info, + /*out*/ HInductionVarAnalysis::InductionInfo** trip) const { + HLoopInformation* l = context->GetBlock()->GetLoopInformation(); // closest enveloping loop + if (l != nullptr) { + HInductionVarAnalysis::InductionInfo* i = induction_analysis_->LookupInfo(l, instruction); + if (i != nullptr) { + *loop = l; + *info = i; + *trip = induction_analysis_->LookupInfo(l, l->GetHeader()->GetLastInstruction()); + return true; + } + } + return false; +} + +bool InductionVarRange::IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const { + if (trip != nullptr) { + // Both bounds that define a trip-count are well-behaved if they either are not defined + // in any loop, or are contained in a proper interval. This allows finding the min/max + // of an expression by chasing outward. + InductionVarRange range(induction_analysis_); + HInductionVarAnalysis::InductionInfo* lower = trip->op_b->op_a; + HInductionVarAnalysis::InductionInfo* upper = trip->op_b->op_b; + int64_t not_used = 0; + return (!HasFetchInLoop(lower) || range.IsConstant(lower, kAtLeast, ¬_used)) && + (!HasFetchInLoop(upper) || range.IsConstant(upper, kAtLeast, ¬_used)); + } + return true; +} + +bool InductionVarRange::HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const { + if (info != nullptr) { + if (info->induction_class == HInductionVarAnalysis::kInvariant && + info->operation == HInductionVarAnalysis::kFetch) { + return info->fetch->GetBlock()->GetLoopInformation() != nullptr; + } + return HasFetchInLoop(info->op_a) || HasFetchInLoop(info->op_b); + } + return false; +} + bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const { if (info != nullptr) { if (info->induction_class == HInductionVarAnalysis::kLinear) { @@ -299,13 +295,13 @@ InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::Ind HInductionVarAnalysis::InductionInfo* trip, bool in_body, bool is_min) const { - // Detect common situation where an offset inside the trip count cancels out during range + // 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) { + if (trip_expr->type == info->type && trip_expr->operation == HInductionVarAnalysis::kSub) { int64_t stride_value = 0; if (IsConstant(info->op_a, kExact, &stride_value)) { if (!is_min && stride_value == 1) { @@ -349,12 +345,25 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, HInductionVarAnalysis::InductionInfo* trip, bool in_body, 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. + // Stop chasing the instruction at constant or hint. int64_t value; - if (IsIntAndGet(instruction, &value) && CanLongValueFitIntoInt(value)) { + if (IsIntAndGet(instruction, &value) && CanLongValueFitIntoInt(value)) { return Value(static_cast(value)); - } else if (instruction->IsAdd()) { + } else if (instruction == chase_hint_) { + return Value(instruction, 1, 0); + } + // Special cases when encountering a single instruction that denotes trip count in the + // loop-body: min is 1 and, when chasing constants, max of safe trip-count is max int + if (in_body && trip != nullptr && instruction == trip->op_a->fetch) { + if (is_min) { + return Value(1); + } else if (chase_hint_ == nullptr && !IsUnsafeTripCount(trip)) { + return Value(std::numeric_limits::max()); + } + } + // Chase the instruction a bit deeper into the HIR tree, so that it becomes more likely + // range analysis will compare the same instructions as terminal nodes. + if (instruction->IsAdd()) { if (IsIntAndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) { return AddValue(Value(static_cast(value)), GetFetch(instruction->InputAt(1), trip, in_body, is_min)); @@ -362,19 +371,35 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), Value(static_cast(value))); } - } else if (instruction->IsArrayLength() && instruction->InputAt(0)->IsNewArray()) { - return GetFetch(instruction->InputAt(0)->InputAt(0), trip, in_body, is_min); + } else if (instruction->IsArrayLength()) { + // Return extreme values when chasing constants. Otherwise, chase deeper. + if (chase_hint_ == nullptr) { + return is_min ? Value(0) : Value(std::numeric_limits::max()); + } else if (instruction->InputAt(0)->IsNewArray()) { + return GetFetch(instruction->InputAt(0)->InputAt(0), trip, in_body, is_min); + } } else if (instruction->IsTypeConversion()) { // Since analysis is 32-bit (or narrower) we allow a widening along the path. if (instruction->AsTypeConversion()->GetInputType() == Primitive::kPrimInt && instruction->AsTypeConversion()->GetResultType() == Primitive::kPrimLong) { return GetFetch(instruction->InputAt(0), trip, in_body, is_min); } - } else if (is_min) { - // Special case for finding minimum: minimum of trip-count in loop-body is 1. - if (trip != nullptr && in_body && instruction == trip->op_a->fetch) { - return Value(1); - } + } + // Chase an invariant fetch that is defined by an outer loop if the trip-count used + // so far is well-behaved in both bounds and the next trip-count is safe. + // Example: + // for (int i = 0; i <= 100; i++) // safe + // for (int j = 0; j <= i; j++) // well-behaved + // j is in range [0, i ] (if i is chase hint) + // or in range [0, 100] (otherwise) + HLoopInformation* next_loop = nullptr; + HInductionVarAnalysis::InductionInfo* next_info = nullptr; + HInductionVarAnalysis::InductionInfo* next_trip = nullptr; + bool next_in_body = true; // inner loop is always in body of outer loop + if (HasInductionInfo(instruction, instruction, &next_loop, &next_info, &next_trip) && + IsWellBehavedTripCount(trip) && + !IsUnsafeTripCount(next_trip)) { + return GetVal(next_info, next_trip, next_in_body, is_min); } return Value(instruction, 1, 0); } @@ -421,9 +446,8 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct break; } break; - case HInductionVarAnalysis::kLinear: { + case HInductionVarAnalysis::kLinear: return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type); - } case HInductionVarAnalysis::kWrapAround: case HInductionVarAnalysis::kPeriodic: return MergeVal(GetVal(info->op_a, trip, in_body, is_min), @@ -438,20 +462,18 @@ InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::Induct HInductionVarAnalysis::InductionInfo* trip, bool in_body, bool is_min) const { + // Constant times range. + int64_t value = 0; + if (IsConstant(info1, kExact, &value)) { + return MulRangeAndConstant(value, info2, trip, in_body, is_min); + } else if (IsConstant(info2, kExact, &value)) { + return MulRangeAndConstant(value, info1, trip, in_body, is_min); + } + // Interval ranges. 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 first operand. - if (!IsConstantValue(v1_min) && !IsConstantValue(v1_max)) { - RefineOuter(&v1_min, &v1_max); - } - // Constant times range. - if (IsSameConstantValue(v1_min, v1_max)) { - return MulRangeAndConstant(v2_min, v2_max, v1_min, is_min); - } else if (IsSameConstantValue(v2_min, v2_max)) { - return MulRangeAndConstant(v1_min, v1_max, v2_min, is_min); - } // Positive range vs. positive or negative range. if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { @@ -476,14 +498,16 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct HInductionVarAnalysis::InductionInfo* trip, bool in_body, bool is_min) const { + // Range divided by constant. + int64_t value = 0; + if (IsConstant(info2, kExact, &value)) { + return DivRangeAndConstant(value, info1, trip, in_body, is_min); + } + // Interval ranges. 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); - // Range divided by constant. - if (IsSameConstantValue(v2_min, v2_max)) { - return DivRangeAndConstant(v1_min, v1_max, v2_min, is_min); - } // Positive range vs. positive or negative range. if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { @@ -503,18 +527,30 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct return Value(); } -InductionVarRange::Value InductionVarRange::MulRangeAndConstant(Value v_min, - Value v_max, - Value c, - bool is_min) const { - return is_min == (c.b_constant >= 0) ? MulValue(v_min, c) : MulValue(v_max, c); +InductionVarRange::Value InductionVarRange::MulRangeAndConstant( + int64_t value, + HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* trip, + bool in_body, + bool is_min) const { + if (CanLongValueFitIntoInt(value)) { + Value c(static_cast(value)); + return MulValue(GetVal(info, trip, in_body, is_min == value >= 0), c); + } + return Value(); } -InductionVarRange::Value InductionVarRange::DivRangeAndConstant(Value v_min, - Value v_max, - Value c, - bool is_min) const { - return is_min == (c.b_constant >= 0) ? DivValue(v_min, c) : DivValue(v_max, c); +InductionVarRange::Value InductionVarRange::DivRangeAndConstant( + int64_t value, + HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* trip, + bool in_body, + bool is_min) const { + if (CanLongValueFitIntoInt(value)) { + Value c(static_cast(value)); + return DivValue(GetVal(info, trip, in_body, is_min == value >= 0), c); + } + return Value(); } InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const { @@ -580,28 +616,6 @@ InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is return Value(); } -InductionVarRange::Value InductionVarRange::RefineOuter(Value v, bool is_min) const { - if (v.instruction == nullptr) { - return v; // nothing to refine - } - HLoopInformation* loop = - v.instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop - if (loop == nullptr) { - return v; // no loop - } - HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, v.instruction); - if (info == nullptr) { - return v; // no induction information - } - // Set up loop information. - HBasicBlock* header = loop->GetHeader(); - bool in_body = true; // inner always in more outer - HInductionVarAnalysis::InductionInfo* trip = - induction_analysis_->LookupInfo(loop, header->GetLastInstruction()); - // Try to refine "a x instruction + b" with outer loop range information on instruction. - return AddValue(MulValue(Value(v.a_constant), GetVal(info, trip, in_body, is_min)), Value(v.b_constant)); -} - bool InductionVarRange::GenerateCode(HInstruction* context, HInstruction* instruction, HGraph* graph, @@ -611,27 +625,18 @@ bool InductionVarRange::GenerateCode(HInstruction* context, /*out*/HInstruction** taken_test, /*out*/bool* needs_finite_test, /*out*/bool* needs_taken_test) const { - HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop - if (loop == nullptr) { - return false; // no loop - } - HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction); - if (info == nullptr) { - return false; // no induction information - } - // Set up loop information. - HBasicBlock* header = loop->GetHeader(); - bool in_body = context->GetBlock() != header; - HInductionVarAnalysis::InductionInfo* trip = - induction_analysis_->LookupInfo(loop, header->GetLastInstruction()); - if (trip == nullptr) { - return false; // codegen relies on trip count + HLoopInformation* loop = nullptr; + HInductionVarAnalysis::InductionInfo* info = nullptr; + HInductionVarAnalysis::InductionInfo* trip = nullptr; + if (!HasInductionInfo(context, instruction, &loop, &info, &trip) || trip == nullptr) { + return false; // codegen needs all information, including tripcount } // Determine what tests are needed. A finite test is needed if the evaluation code uses the // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot" // the computed range). A taken test is needed for any unknown trip-count, even if evaluation // code does not use the trip-count explicitly (since there could be an implicit relation // between e.g. an invariant subscript and a not-taken condition). + bool in_body = context->GetBlock() != loop->GetHeader(); *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip); *needs_taken_test = IsBodyTripCount(trip); // Code generation for taken test: generate the code when requested or otherwise analyze -- cgit v1.2.3-59-g8ed1b