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 or last value on each instruction in the HIR. 28 * The public API also provides a few general-purpose utility methods related to induction. 29 * 30 * The range analysis is done with a combination of symbolic and partial integral evaluation 31 * of expressions. The analysis avoids complications with wrap-around arithmetic on the integral 32 * parts but all clients should be aware that wrap-around may occur on any of the symbolic parts. 33 * For example, given a known range for [0,100] for i, the evaluation yields range [-100,100] 34 * for expression -2*i+100, which is exact, and range [x,x+100] for expression i+x, which may 35 * wrap-around anywhere in the range depending on the actual value of x. 36 */ 37 class InductionVarRange { 38 public: 39 /* 40 * A value that can be represented as "a * instruction + b" for 32-bit constants, where 41 * Value() denotes an unknown lower and upper bound. Although range analysis could yield 42 * more complex values, the format is sufficiently powerful to represent useful cases 43 * and feeds directly into optimizations like bounds check elimination. 44 */ 45 struct Value { ValueValue46 Value() : instruction(nullptr), a_constant(0), b_constant(0), is_known(false) {} ValueValue47 Value(HInstruction* i, int32_t a, int32_t b) 48 : instruction(a != 0 ? i : nullptr), a_constant(a), b_constant(b), is_known(true) {} ValueValue49 explicit Value(int32_t b) : Value(nullptr, 0, b) {} 50 // Representation as: a_constant x instruction + b_constant. 51 HInstruction* instruction; 52 int32_t a_constant; 53 int32_t b_constant; 54 // If true, represented by prior fields. Otherwise unknown value. 55 bool is_known; 56 }; 57 58 explicit InductionVarRange(HInductionVarAnalysis* induction); 59 60 /** 61 * Given a context block, returns a possibly conservative lower 62 * and upper bound on the instruction's value in the output parameters min_val and max_val, 63 * respectively. The need_finite_test flag denotes if an additional finite-test is needed 64 * to protect the range evaluation inside its loop. The parameter chase_hint defines an 65 * instruction at which chasing may stop. Returns false on failure. 66 */ 67 bool GetInductionRange(const HBasicBlock* context, 68 HInstruction* instruction, 69 HInstruction* chase_hint, 70 /*out*/ Value* min_val, 71 /*out*/ Value* max_val, 72 /*out*/ bool* needs_finite_test); 73 74 /** 75 * Returns true if range analysis is able to generate code for the lower and upper 76 * bound expressions on the instruction in the given context. The need_finite_test 77 * and need_taken test flags denote if an additional finite-test and/or taken-test 78 * are needed to protect the range evaluation inside its loop. 79 */ 80 bool CanGenerateRange(const HBasicBlock* context, 81 HInstruction* instruction, 82 /*out*/ bool* needs_finite_test, 83 /*out*/ bool* needs_taken_test); 84 85 /** 86 * Generates the actual code in the HIR for the lower and upper bound expressions on the 87 * instruction in the given context. Code for the lower and upper bound expression are 88 * generated in given block and graph and are returned in the output parameters lower and 89 * upper, respectively. For a loop invariant, lower is not set. 90 * 91 * For example, given expression x+i with range [0, 5] for i, calling this method 92 * will generate the following sequence: 93 * 94 * block: 95 * lower: add x, 0 96 * upper: add x, 5 97 * 98 * Precondition: CanGenerateRange() returns true. 99 */ 100 void GenerateRange(const HBasicBlock* context, 101 HInstruction* instruction, 102 HGraph* graph, 103 HBasicBlock* block, 104 /*out*/ HInstruction** lower, 105 /*out*/ HInstruction** upper); 106 107 /** 108 * Generates explicit taken-test for the given `loop_control` instruction. Code is generated in 109 * given block and graph. Returns generated taken-test. 110 * 111 * Precondition: CanGenerateRange() returns true and needs_taken_test is set. 112 */ 113 HInstruction* GenerateTakenTest(HInstruction* loop_control, HGraph* graph, HBasicBlock* block); 114 115 /** 116 * Returns true if induction analysis is able to generate code for last value of 117 * the given instruction inside the closest enveloping loop. 118 */ 119 bool CanGenerateLastValue(HInstruction* instruction); 120 121 /** 122 * Generates last value of the given instruction in the closest enveloping loop. 123 * Code is generated in given block and graph. Returns generated last value. 124 * 125 * Precondition: CanGenerateLastValue() returns true. 126 */ 127 HInstruction* GenerateLastValue(HInstruction* instruction, HGraph* graph, HBasicBlock* block); 128 129 /** 130 * Updates all matching fetches with the given replacement in all induction information 131 * that is associated with the given instruction. 132 */ 133 void Replace(HInstruction* instruction, HInstruction* fetch, HInstruction* replacement); 134 135 /** 136 * Incrementally updates induction information for just the given loop. 137 */ ReVisit(const HLoopInformation * loop)138 void ReVisit(const HLoopInformation* loop) { 139 induction_analysis_->induction_.erase(loop); 140 for (HInstructionIterator it(loop->GetHeader()->GetPhis()); !it.Done(); it.Advance()) { 141 induction_analysis_->cycles_.erase(it.Current()->AsPhi()); 142 } 143 induction_analysis_->VisitLoop(loop); 144 } 145 146 /** 147 * Lookup an interesting cycle associated with an entry phi. 148 */ LookupCycle(HPhi * phi)149 ArenaSet<HInstruction*>* LookupCycle(HPhi* phi) const { 150 return induction_analysis_->LookupCycle(phi); 151 } 152 153 /** 154 * Checks if the given phi instruction has been classified as anything by 155 * induction variable analysis. Returns false for anything that cannot be 156 * classified statically, such as reductions or other complex cycles. 157 */ IsClassified(HPhi * phi)158 bool IsClassified(HPhi* phi) const { 159 HLoopInformation* lp = phi->GetBlock()->GetLoopInformation(); // closest enveloping loop 160 return (lp != nullptr) && (induction_analysis_->LookupInfo(lp, phi) != nullptr); 161 } 162 163 /** 164 * Checks if header logic of a loop terminates. If trip count is known sets 'trip_count' to its 165 * value. 166 */ 167 bool IsFinite(const HLoopInformation* loop, /*out*/ int64_t* trip_count) const; 168 169 /** 170 * Checks if a trip count is known for the loop and sets 'trip_count' to its value in this case. 171 */ 172 bool HasKnownTripCount(const HLoopInformation* loop, /*out*/ int64_t* trip_count) const; 173 174 /** 175 * Checks if the given instruction is a unit stride induction inside the closest enveloping 176 * loop of the context that is defined by the first parameter (e.g. pass an array reference 177 * as context and the index as instruction to make sure the stride is tested against the 178 * loop that envelops the reference the closest). Returns invariant offset on success. 179 */ 180 bool IsUnitStride(const HBasicBlock* context, 181 HInstruction* instruction, 182 HGraph* graph, 183 /*out*/ HInstruction** offset) const; 184 185 /** 186 * Generates the trip count expression for the given loop. Code is generated in given block 187 * and graph. The expression is guarded by a taken test if needed. Returns the trip count 188 * expression on success or null otherwise. 189 */ 190 HInstruction* GenerateTripCount(const HLoopInformation* loop, HGraph* graph, HBasicBlock* block); 191 192 private: 193 /* 194 * Enum used in IsConstant() request. 195 */ 196 enum ConstantRequest { 197 kExact, 198 kAtMost, 199 kAtLeast 200 }; 201 202 /** 203 * Checks if header logic of a loop terminates. If trip count is known (constant) sets 204 * 'is_constant' to true and 'trip_count' to the trip count value. 205 */ 206 bool CheckForFiniteAndConstantProps(const HLoopInformation* loop, 207 /*out*/ bool* is_constant, 208 /*out*/ int64_t* trip_count) const; 209 210 /** 211 * Returns true if exact or upper/lower bound on the given induction 212 * information is known as a 64-bit constant, which is returned in value. 213 */ 214 bool IsConstant(const HBasicBlock* context, 215 const HLoopInformation* loop, 216 HInductionVarAnalysis::InductionInfo* info, 217 ConstantRequest request, 218 /*out*/ int64_t* value) const; 219 220 /** Returns whether induction information can be obtained. */ 221 bool HasInductionInfo(const HBasicBlock* context, 222 HInstruction* instruction, 223 /*out*/ const HLoopInformation** loop, 224 /*out*/ HInductionVarAnalysis::InductionInfo** info, 225 /*out*/ HInductionVarAnalysis::InductionInfo** trip) const; 226 227 bool HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const; 228 bool NeedsTripCount(const HBasicBlock* context, 229 const HLoopInformation* loop, 230 HInductionVarAnalysis::InductionInfo* info, 231 /*out*/ int64_t* stride_value) const; 232 bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const; 233 bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const; 234 bool IsWellBehavedTripCount(const HBasicBlock* context, 235 const HLoopInformation* loop, 236 HInductionVarAnalysis::InductionInfo* trip) const; 237 238 Value GetLinear(const HBasicBlock* context, 239 const HLoopInformation* loop, 240 HInductionVarAnalysis::InductionInfo* info, 241 HInductionVarAnalysis::InductionInfo* trip, 242 bool is_min) const; 243 Value GetPolynomial(const HBasicBlock* context, 244 const HLoopInformation* loop, 245 HInductionVarAnalysis::InductionInfo* info, 246 HInductionVarAnalysis::InductionInfo* trip, 247 bool is_min) const; 248 Value GetGeometric(const HBasicBlock* context, 249 const HLoopInformation* loop, 250 HInductionVarAnalysis::InductionInfo* info, 251 HInductionVarAnalysis::InductionInfo* trip, 252 bool is_min) const; 253 Value GetFetch(const HBasicBlock* context, 254 const HLoopInformation* loop, 255 HInstruction* instruction, 256 HInductionVarAnalysis::InductionInfo* trip, 257 bool is_min) const; 258 Value GetVal(const HBasicBlock* context, 259 const HLoopInformation* loop, 260 HInductionVarAnalysis::InductionInfo* info, 261 HInductionVarAnalysis::InductionInfo* trip, 262 bool is_min) const; 263 Value GetMul(const HBasicBlock* context, 264 const HLoopInformation* loop, 265 HInductionVarAnalysis::InductionInfo* info1, 266 HInductionVarAnalysis::InductionInfo* info2, 267 HInductionVarAnalysis::InductionInfo* trip, 268 bool is_min) const; 269 Value GetDiv(const HBasicBlock* context, 270 const HLoopInformation* loop, 271 HInductionVarAnalysis::InductionInfo* info1, 272 HInductionVarAnalysis::InductionInfo* info2, 273 HInductionVarAnalysis::InductionInfo* trip, 274 bool is_min) const; 275 Value GetRem(const HBasicBlock* context, 276 const HLoopInformation* loop, 277 HInductionVarAnalysis::InductionInfo* info1, 278 HInductionVarAnalysis::InductionInfo* info2) const; 279 Value GetXor(const HBasicBlock* context, 280 const HLoopInformation* loop, 281 HInductionVarAnalysis::InductionInfo* info1, 282 HInductionVarAnalysis::InductionInfo* info2) const; 283 284 Value MulRangeAndConstant(const HBasicBlock* context, 285 const HLoopInformation* loop, 286 int64_t value, 287 HInductionVarAnalysis::InductionInfo* info, 288 HInductionVarAnalysis::InductionInfo* trip, 289 bool is_min) const; 290 Value DivRangeAndConstant(const HBasicBlock* context, 291 const HLoopInformation* loop, 292 int64_t value, 293 HInductionVarAnalysis::InductionInfo* info, 294 HInductionVarAnalysis::InductionInfo* trip, 295 bool is_min) const; 296 297 Value AddValue(Value v1, Value v2) const; 298 Value SubValue(Value v1, Value v2) const; 299 Value MulValue(Value v1, Value v2) const; 300 Value DivValue(Value v1, Value v2) const; 301 Value MergeVal(Value v1, Value v2, bool is_min) const; 302 303 /** 304 * Generates code for lower/upper/taken-test or last value in the HIR. Returns true on 305 * success. With values nullptr, the method can be used to determine if code generation 306 * would be successful without generating actual code yet. 307 */ 308 bool GenerateRangeOrLastValue(const HBasicBlock* context, 309 HInstruction* instruction, 310 bool is_last_val, 311 HGraph* graph, 312 HBasicBlock* block, 313 /*out*/ HInstruction** lower, 314 /*out*/ HInstruction** upper, 315 /*out*/ HInstruction** taken_test, 316 /*out*/ int64_t* stride_value, 317 /*out*/ bool* needs_finite_test, 318 /*out*/ bool* needs_taken_test) const; 319 320 bool GenerateLastValuePolynomial(const HBasicBlock* context, 321 const HLoopInformation* loop, 322 HInductionVarAnalysis::InductionInfo* info, 323 HInductionVarAnalysis::InductionInfo* trip, 324 HGraph* graph, 325 HBasicBlock* block, 326 /*out*/HInstruction** result) const; 327 328 bool GenerateLastValueGeometric(const HBasicBlock* context, 329 const HLoopInformation* loop, 330 HInductionVarAnalysis::InductionInfo* info, 331 HInductionVarAnalysis::InductionInfo* trip, 332 HGraph* graph, 333 HBasicBlock* block, 334 /*out*/HInstruction** result) const; 335 336 bool GenerateLastValueWrapAround(const HBasicBlock* context, 337 const HLoopInformation* loop, 338 HInductionVarAnalysis::InductionInfo* info, 339 HInductionVarAnalysis::InductionInfo* trip, 340 HGraph* graph, 341 HBasicBlock* block, 342 /*out*/HInstruction** result) const; 343 344 bool GenerateLastValuePeriodic(const HBasicBlock* context, 345 const HLoopInformation* loop, 346 HInductionVarAnalysis::InductionInfo* info, 347 HInductionVarAnalysis::InductionInfo* trip, 348 HGraph* graph, 349 HBasicBlock* block, 350 /*out*/HInstruction** result, 351 /*out*/ bool* needs_taken_test) const; 352 353 bool GenerateCode(const HBasicBlock* context, 354 const HLoopInformation* loop, 355 HInductionVarAnalysis::InductionInfo* info, 356 HInductionVarAnalysis::InductionInfo* trip, 357 HGraph* graph, 358 HBasicBlock* block, 359 bool is_min, 360 /*out*/ HInstruction** result) const; 361 362 void ReplaceInduction(HInductionVarAnalysis::InductionInfo* info, 363 HInstruction* fetch, 364 HInstruction* replacement); 365 366 /** Results of prior induction variable analysis. */ 367 HInductionVarAnalysis* induction_analysis_; 368 369 /** Instruction at which chasing may stop. */ 370 HInstruction* chase_hint_; 371 372 friend class HInductionVarAnalysis; 373 friend class InductionVarRangeTest; 374 375 DISALLOW_COPY_AND_ASSIGN(InductionVarRange); 376 }; 377 378 } // namespace art 379 380 #endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ 381