Induction variable range analysis.
Rationale: by computing an upper bound on the trip count of each
loop after induction var analysis has completed, a
simple range analysis yields lower and upper bounds on
all induced expressions in a loop; this analysis
plugs directly into BCE (follow-up CL).
Change-Id: I46a3fe48721ca372547199b39a3498c47992597d
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
new file mode 100644
index 0000000..bd90334
--- /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