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