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.h b/compiler/optimizing/induction_var_range.h
new file mode 100644
index 0000000..b079076
--- /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_