1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ 18 #define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ 19 20 #include "induction_var_analysis.h" 21 22 namespace art { 23 24 /** 25 * This class implements range analysis on expressions within loops. It takes the results 26 * of induction variable analysis in the constructor and provides a public API to obtain 27 * a conservative lower and upper bound value on each instruction in the HIR. 28 * 29 * The range analysis is done with a combination of symbolic and partial integral evaluation 30 * of expressions. The analysis avoids complications with wrap-around arithmetic on the integral 31 * parts but all clients should be aware that wrap-around may occur on any of the symbolic parts. 32 * For example, given a known range for [0,100] for i, the evaluation yields range [-100,100] 33 * for expression -2*i+100, which is exact, and range [x,x+100] for expression i+x, which may 34 * wrap-around anywhere in the range depending on the actual value of x. 35 */ 36 class InductionVarRange { 37 public: 38 /* 39 * A value that can be represented as "a * instruction + b" for 32-bit constants, where 40 * Value() denotes an unknown lower and upper bound. Although range analysis could yield 41 * more complex values, the format is sufficiently powerful to represent useful cases 42 * and feeds directly into optimizations like bounds check elimination. 43 */ 44 struct Value { 45 Value() : instruction(nullptr), a_constant(0), b_constant(0), is_known(false) {} 46 Value(HInstruction* i, int32_t a, int32_t b) 47 : instruction(a != 0 ? i : nullptr), a_constant(a), b_constant(b), is_known(true) {} 48 explicit Value(int32_t b) : Value(nullptr, 0, b) {} 49 // Representation as: a_constant x instruction + b_constant. 50 HInstruction* instruction; 51 int32_t a_constant; 52 int32_t b_constant; 53 // If true, represented by prior fields. Otherwise unknown value. 54 bool is_known; 55 }; 56 57 explicit InductionVarRange(HInductionVarAnalysis* induction); 58 59 /** 60 * Given a context denoted by the first instruction, returns a possibly conservative 61 * lower and upper bound on the instruction's value in the output parameters min_val 62 * and max_val, respectively. The need_finite_test flag denotes if an additional finite-test 63 * is needed to protect the range evaluation inside its loop. Returns false on failure. 64 */ 65 bool GetInductionRange(HInstruction* context, 66 HInstruction* instruction, 67 /*out*/ Value* min_val, 68 /*out*/ Value* max_val, 69 /*out*/ bool* needs_finite_test); 70 71 /** Refines the values with induction of next outer loop. Returns true on change. */ 72 bool RefineOuter(/*in-out*/ Value* min_val, 73 /*in-out*/ Value* max_val) const; 74 75 /** 76 * Returns true if range analysis is able to generate code for the lower and upper 77 * bound expressions on the instruction in the given context. The need_finite_test 78 * and need_taken test flags denote if an additional finite-test and/or taken-test 79 * are needed to protect the range evaluation inside its loop. 80 */ 81 bool CanGenerateCode(HInstruction* context, 82 HInstruction* instruction, 83 /*out*/ bool* needs_finite_test, 84 /*out*/ bool* needs_taken_test); 85 86 /** 87 * Generates the actual code in the HIR for the lower and upper bound expressions on the 88 * instruction in the given context. Code for the lower and upper bound expression are 89 * generated in given block and graph and are returned in the output parameters lower and 90 * upper, respectively. For a loop invariant, lower is not set. 91 * 92 * For example, given expression x+i with range [0, 5] for i, calling this method 93 * will generate the following sequence: 94 * 95 * block: 96 * lower: add x, 0 97 * upper: add x, 5 98 * 99 * Precondition: CanGenerateCode() returns true. 100 */ 101 void GenerateRangeCode(HInstruction* context, 102 HInstruction* instruction, 103 HGraph* graph, 104 HBasicBlock* block, 105 /*out*/ HInstruction** lower, 106 /*out*/ HInstruction** upper); 107 108 /** 109 * Generates explicit taken-test for the loop in the given context. Code is generated in 110 * given block and graph. The taken-test is returned in parameter test. 111 * 112 * Precondition: CanGenerateCode() returns true and needs_taken_test is set. 113 */ 114 void GenerateTakenTest(HInstruction* context, 115 HGraph* graph, 116 HBasicBlock* block, 117 /*out*/ HInstruction** taken_test); 118 119 private: 120 /* 121 * Enum used in IsConstant() request. 122 */ 123 enum ConstantRequest { 124 kExact, 125 kAtMost, 126 kAtLeast 127 }; 128 129 /** 130 * Returns true if exact or upper/lower bound on the given induction 131 * information is known as a 64-bit constant, which is returned in value. 132 */ 133 bool IsConstant(HInductionVarAnalysis::InductionInfo* info, 134 ConstantRequest request, 135 /*out*/ int64_t *value) const; 136 137 bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const; 138 bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const; 139 bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const; 140 141 Value GetLinear(HInductionVarAnalysis::InductionInfo* info, 142 HInductionVarAnalysis::InductionInfo* trip, 143 bool in_body, 144 bool is_min) const; 145 Value GetFetch(HInstruction* instruction, 146 HInductionVarAnalysis::InductionInfo* trip, 147 bool in_body, 148 bool is_min) const; 149 Value GetVal(HInductionVarAnalysis::InductionInfo* info, 150 HInductionVarAnalysis::InductionInfo* trip, 151 bool in_body, 152 bool is_min) const; 153 Value GetMul(HInductionVarAnalysis::InductionInfo* info1, 154 HInductionVarAnalysis::InductionInfo* info2, 155 HInductionVarAnalysis::InductionInfo* trip, 156 bool in_body, 157 bool is_min) const; 158 Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, 159 HInductionVarAnalysis::InductionInfo* info2, 160 HInductionVarAnalysis::InductionInfo* trip, 161 bool in_body, 162 bool is_min) const; 163 164 Value MulRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const; 165 Value DivRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const; 166 167 Value AddValue(Value v1, Value v2) const; 168 Value SubValue(Value v1, Value v2) const; 169 Value MulValue(Value v1, Value v2) const; 170 Value DivValue(Value v1, Value v2) const; 171 Value MergeVal(Value v1, Value v2, bool is_min) const; 172 173 /** 174 * Returns refined value using induction of next outer loop or the input value if no 175 * further refinement is possible. 176 */ 177 Value RefineOuter(Value val, bool is_min) const; 178 179 /** 180 * Generates code for lower/upper/taken-test in the HIR. Returns true on success. 181 * With values nullptr, the method can be used to determine if code generation 182 * would be successful without generating actual code yet. 183 */ 184 bool GenerateCode(HInstruction* context, 185 HInstruction* instruction, 186 HGraph* graph, 187 HBasicBlock* block, 188 /*out*/ HInstruction** lower, 189 /*out*/ HInstruction** upper, 190 /*out*/ HInstruction** taken_test, 191 /*out*/ bool* needs_finite_test, 192 /*out*/ bool* needs_taken_test) const; 193 194 bool GenerateCode(HInductionVarAnalysis::InductionInfo* info, 195 HInductionVarAnalysis::InductionInfo* trip, 196 HGraph* graph, 197 HBasicBlock* block, 198 /*out*/ HInstruction** result, 199 bool in_body, 200 bool is_min) const; 201 202 /** Results of prior induction variable analysis. */ 203 HInductionVarAnalysis *induction_analysis_; 204 205 friend class HInductionVarAnalysis; 206 friend class InductionVarRangeTest; 207 208 DISALLOW_COPY_AND_ASSIGN(InductionVarRange); 209 }; 210 211 } // namespace art 212 213 #endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ 214
