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 #include "induction_var_range.h" 18 19 #include <limits> 20 21 namespace art { 22 23 /** Returns true if 64-bit constant fits in 32-bit constant. */ 24 static bool CanLongValueFitIntoInt(int64_t c) { 25 return std::numeric_limits<int32_t>::min() <= c && c <= std::numeric_limits<int32_t>::max(); 26 } 27 28 /** Returns true if 32-bit addition can be done safely. */ 29 static bool IsSafeAdd(int32_t c1, int32_t c2) { 30 return CanLongValueFitIntoInt(static_cast<int64_t>(c1) + static_cast<int64_t>(c2)); 31 } 32 33 /** Returns true if 32-bit subtraction can be done safely. */ 34 static bool IsSafeSub(int32_t c1, int32_t c2) { 35 return CanLongValueFitIntoInt(static_cast<int64_t>(c1) - static_cast<int64_t>(c2)); 36 } 37 38 /** Returns true if 32-bit multiplication can be done safely. */ 39 static bool IsSafeMul(int32_t c1, int32_t c2) { 40 return CanLongValueFitIntoInt(static_cast<int64_t>(c1) * static_cast<int64_t>(c2)); 41 } 42 43 /** Returns true if 32-bit division can be done safely. */ 44 static bool IsSafeDiv(int32_t c1, int32_t c2) { 45 return c2 != 0 && CanLongValueFitIntoInt(static_cast<int64_t>(c1) / static_cast<int64_t>(c2)); 46 } 47 48 /** Computes a * b for a,b > 0 (at least until first overflow happens). */ 49 static int64_t SafeMul(int64_t a, int64_t b, /*out*/ bool* overflow) { 50 if (a > 0 && b > 0 && a > (std::numeric_limits<int64_t>::max() / b)) { 51 *overflow = true; 52 } 53 return a * b; 54 } 55 56 /** Returns b^e for b,e > 0. Sets overflow if arithmetic wrap-around occurred. */ 57 static int64_t IntPow(int64_t b, int64_t e, /*out*/ bool* overflow) { 58 DCHECK_LT(0, b); 59 DCHECK_LT(0, e); 60 int64_t pow = 1; 61 while (e) { 62 if (e & 1) { 63 pow = SafeMul(pow, b, overflow); 64 } 65 e >>= 1; 66 if (e) { 67 b = SafeMul(b, b, overflow); 68 } 69 } 70 return pow; 71 } 72 73 /** 74 * Detects an instruction that is >= 0. As long as the value is carried by 75 * a single instruction, arithmetic wrap-around cannot occur. 76 */ 77 static bool IsGEZero(HInstruction* instruction) { 78 DCHECK(instruction != nullptr); 79 if (instruction->IsArrayLength()) { 80 return true; 81 } else if (instruction->IsInvokeStaticOrDirect()) { 82 switch (instruction->AsInvoke()->GetIntrinsic()) { 83 case Intrinsics::kMathMinIntInt: 84 case Intrinsics::kMathMinLongLong: 85 // Instruction MIN(>=0, >=0) is >= 0. 86 return IsGEZero(instruction->InputAt(0)) && 87 IsGEZero(instruction->InputAt(1)); 88 case Intrinsics::kMathAbsInt: 89 case Intrinsics::kMathAbsLong: 90 // Instruction ABS(x) is >= 0. 91 return true; 92 default: 93 break; 94 } 95 } 96 int64_t value = -1; 97 return IsInt64AndGet(instruction, &value) && value >= 0; 98 } 99 100 /** Hunts "under the hood" for a suitable instruction at the hint. */ 101 static bool IsMaxAtHint( 102 HInstruction* instruction, HInstruction* hint, /*out*/HInstruction** suitable) { 103 if (instruction->IsInvokeStaticOrDirect()) { 104 switch (instruction->AsInvoke()->GetIntrinsic()) { 105 case Intrinsics::kMathMinIntInt: 106 case Intrinsics::kMathMinLongLong: 107 // For MIN(x, y), return most suitable x or y as maximum. 108 return IsMaxAtHint(instruction->InputAt(0), hint, suitable) || 109 IsMaxAtHint(instruction->InputAt(1), hint, suitable); 110 default: 111 break; 112 } 113 } else { 114 *suitable = instruction; 115 return HuntForDeclaration(instruction) == hint; 116 } 117 return false; 118 } 119 120 /** Post-analysis simplification of a minimum value that makes the bound more useful to clients. */ 121 static InductionVarRange::Value SimplifyMin(InductionVarRange::Value v) { 122 if (v.is_known && v.a_constant == 1 && v.b_constant <= 0) { 123 // If a == 1, instruction >= 0 and b <= 0, just return the constant b. 124 // No arithmetic wrap-around can occur. 125 if (IsGEZero(v.instruction)) { 126 return InductionVarRange::Value(v.b_constant); 127 } 128 } 129 return v; 130 } 131 132 /** Post-analysis simplification of a maximum value that makes the bound more useful to clients. */ 133 static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v, HInstruction* hint) { 134 if (v.is_known && v.a_constant >= 1) { 135 // An upper bound a * (length / a) + b, where a >= 1, can be conservatively rewritten as 136 // length + b because length >= 0 is true. 137 int64_t value; 138 if (v.instruction->IsDiv() && 139 v.instruction->InputAt(0)->IsArrayLength() && 140 IsInt64AndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) { 141 return InductionVarRange::Value(v.instruction->InputAt(0), 1, v.b_constant); 142 } 143 // If a == 1, the most suitable one suffices as maximum value. 144 HInstruction* suitable = nullptr; 145 if (v.a_constant == 1 && IsMaxAtHint(v.instruction, hint, &suitable)) { 146 return InductionVarRange::Value(suitable, 1, v.b_constant); 147 } 148 } 149 return v; 150 } 151 152 /** Tests for a constant value. */ 153 static bool IsConstantValue(InductionVarRange::Value v) { 154 return v.is_known && v.a_constant == 0; 155 } 156 157 /** Corrects a value for type to account for arithmetic wrap-around in lower precision. */ 158 static InductionVarRange::Value CorrectForType(InductionVarRange::Value v, Primitive::Type type) { 159 switch (type) { 160 case Primitive::kPrimShort: 161 case Primitive::kPrimChar: 162 case Primitive::kPrimByte: { 163 // Constants within range only. 164 // TODO: maybe some room for improvement, like allowing widening conversions 165 int32_t min = Primitive::MinValueOfIntegralType(type); 166 int32_t max = Primitive::MaxValueOfIntegralType(type); 167 return (IsConstantValue(v) && min <= v.b_constant && v.b_constant <= max) 168 ? v 169 : InductionVarRange::Value(); 170 } 171 default: 172 return v; 173 } 174 } 175 176 /** Inserts an instruction. */ 177 static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) { 178 DCHECK(block != nullptr); 179 DCHECK(block->GetLastInstruction() != nullptr) << block->GetBlockId(); 180 DCHECK(instruction != nullptr); 181 block->InsertInstructionBefore(instruction, block->GetLastInstruction()); 182 return instruction; 183 } 184 185 /** Obtains loop's control instruction. */ 186 static HInstruction* GetLoopControl(HLoopInformation* loop) { 187 DCHECK(loop != nullptr); 188 return loop->GetHeader()->GetLastInstruction(); 189 } 190 191 // 192 // Public class methods. 193 // 194 195 InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis) 196 : induction_analysis_(induction_analysis), 197 chase_hint_(nullptr) { 198 DCHECK(induction_analysis != nullptr); 199 } 200 201 bool InductionVarRange::GetInductionRange(HInstruction* context, 202 HInstruction* instruction, 203 HInstruction* chase_hint, 204 /*out*/Value* min_val, 205 /*out*/Value* max_val, 206 /*out*/bool* needs_finite_test) { 207 HLoopInformation* loop = nullptr; 208 HInductionVarAnalysis::InductionInfo* info = nullptr; 209 HInductionVarAnalysis::InductionInfo* trip = nullptr; 210 if (!HasInductionInfo(context, instruction, &loop, &info, &trip)) { 211 return false; 212 } 213 // Type int or lower (this is not too restrictive since intended clients, like 214 // bounds check elimination, will have truncated higher precision induction 215 // at their use point already). 216 switch (info->type) { 217 case Primitive::kPrimInt: 218 case Primitive::kPrimShort: 219 case Primitive::kPrimChar: 220 case Primitive::kPrimByte: 221 break; 222 default: 223 return false; 224 } 225 // Find range. 226 chase_hint_ = chase_hint; 227 bool in_body = context->GetBlock() != loop->GetHeader(); 228 int64_t stride_value = 0; 229 *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min */ true)); 230 *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min */ false), chase_hint); 231 *needs_finite_test = NeedsTripCount(info, &stride_value) && IsUnsafeTripCount(trip); 232 chase_hint_ = nullptr; 233 // Retry chasing constants for wrap-around (merge sensitive). 234 if (!min_val->is_known && info->induction_class == HInductionVarAnalysis::kWrapAround) { 235 *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min */ true)); 236 } 237 return true; 238 } 239 240 bool InductionVarRange::CanGenerateRange(HInstruction* context, 241 HInstruction* instruction, 242 /*out*/bool* needs_finite_test, 243 /*out*/bool* needs_taken_test) { 244 bool is_last_value = false; 245 int64_t stride_value = 0; 246 return GenerateRangeOrLastValue(context, 247 instruction, 248 is_last_value, 249 nullptr, 250 nullptr, 251 nullptr, 252 nullptr, 253 nullptr, // nothing generated yet 254 &stride_value, 255 needs_finite_test, 256 needs_taken_test) 257 && (stride_value == -1 || 258 stride_value == 0 || 259 stride_value == 1); // avoid arithmetic wrap-around anomalies. 260 } 261 262 void InductionVarRange::GenerateRange(HInstruction* context, 263 HInstruction* instruction, 264 HGraph* graph, 265 HBasicBlock* block, 266 /*out*/HInstruction** lower, 267 /*out*/HInstruction** upper) { 268 bool is_last_value = false; 269 int64_t stride_value = 0; 270 bool b1, b2; // unused 271 if (!GenerateRangeOrLastValue(context, 272 instruction, 273 is_last_value, 274 graph, 275 block, 276 lower, 277 upper, 278 nullptr, 279 &stride_value, 280 &b1, 281 &b2)) { 282 LOG(FATAL) << "Failed precondition: CanGenerateRange()"; 283 } 284 } 285 286 HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* context, 287 HGraph* graph, 288 HBasicBlock* block) { 289 HInstruction* taken_test = nullptr; 290 bool is_last_value = false; 291 int64_t stride_value = 0; 292 bool b1, b2; // unused 293 if (!GenerateRangeOrLastValue(context, 294 context, 295 is_last_value, 296 graph, 297 block, 298 nullptr, 299 nullptr, 300 &taken_test, 301 &stride_value, 302 &b1, 303 &b2)) { 304 LOG(FATAL) << "Failed precondition: CanGenerateRange()"; 305 } 306 return taken_test; 307 } 308 309 bool InductionVarRange::CanGenerateLastValue(HInstruction* instruction) { 310 bool is_last_value = true; 311 int64_t stride_value = 0; 312 bool needs_finite_test = false; 313 bool needs_taken_test = false; 314 return GenerateRangeOrLastValue(instruction, 315 instruction, 316 is_last_value, 317 nullptr, 318 nullptr, 319 nullptr, 320 nullptr, 321 nullptr, // nothing generated yet 322 &stride_value, 323 &needs_finite_test, 324 &needs_taken_test) 325 && !needs_finite_test && !needs_taken_test; 326 } 327 328 HInstruction* InductionVarRange::GenerateLastValue(HInstruction* instruction, 329 HGraph* graph, 330 HBasicBlock* block) { 331 HInstruction* last_value = nullptr; 332 bool is_last_value = true; 333 int64_t stride_value = 0; 334 bool b1, b2; // unused 335 if (!GenerateRangeOrLastValue(instruction, 336 instruction, 337 is_last_value, 338 graph, 339 block, 340 &last_value, 341 &last_value, 342 nullptr, 343 &stride_value, 344 &b1, 345 &b2)) { 346 LOG(FATAL) << "Failed precondition: CanGenerateLastValue()"; 347 } 348 return last_value; 349 } 350 351 void InductionVarRange::Replace(HInstruction* instruction, 352 HInstruction* fetch, 353 HInstruction* replacement) { 354 for (HLoopInformation* lp = instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop 355 lp != nullptr; 356 lp = lp->GetPreHeader()->GetLoopInformation()) { 357 // Update instruction's information. 358 ReplaceInduction(induction_analysis_->LookupInfo(lp, instruction), fetch, replacement); 359 // Update loop's trip-count information. 360 ReplaceInduction(induction_analysis_->LookupInfo(lp, GetLoopControl(lp)), fetch, replacement); 361 } 362 } 363 364 bool InductionVarRange::IsFinite(HLoopInformation* loop, /*out*/ int64_t* tc) const { 365 HInductionVarAnalysis::InductionInfo *trip = 366 induction_analysis_->LookupInfo(loop, GetLoopControl(loop)); 367 if (trip != nullptr && !IsUnsafeTripCount(trip)) { 368 IsConstant(trip->op_a, kExact, tc); 369 return true; 370 } 371 return false; 372 } 373 374 bool InductionVarRange::IsUnitStride(HInstruction* context, 375 HInstruction* instruction, 376 HGraph* graph, 377 /*out*/ HInstruction** offset) const { 378 HLoopInformation* loop = nullptr; 379 HInductionVarAnalysis::InductionInfo* info = nullptr; 380 HInductionVarAnalysis::InductionInfo* trip = nullptr; 381 if (HasInductionInfo(context, instruction, &loop, &info, &trip)) { 382 if (info->induction_class == HInductionVarAnalysis::kLinear && 383 !HInductionVarAnalysis::IsNarrowingLinear(info)) { 384 int64_t stride_value = 0; 385 if (IsConstant(info->op_a, kExact, &stride_value) && stride_value == 1) { 386 int64_t off_value = 0; 387 if (IsConstant(info->op_b, kExact, &off_value)) { 388 *offset = graph->GetConstant(info->op_b->type, off_value); 389 } else if (info->op_b->operation == HInductionVarAnalysis::kFetch) { 390 *offset = info->op_b->fetch; 391 } else { 392 return false; 393 } 394 return true; 395 } 396 } 397 } 398 return false; 399 } 400 401 HInstruction* InductionVarRange::GenerateTripCount(HLoopInformation* loop, 402 HGraph* graph, 403 HBasicBlock* block) { 404 HInductionVarAnalysis::InductionInfo *trip = 405 induction_analysis_->LookupInfo(loop, GetLoopControl(loop)); 406 if (trip != nullptr && !IsUnsafeTripCount(trip)) { 407 HInstruction* taken_test = nullptr; 408 HInstruction* trip_expr = nullptr; 409 if (IsBodyTripCount(trip)) { 410 if (!GenerateCode(trip->op_b, nullptr, graph, block, &taken_test, false, false)) { 411 return nullptr; 412 } 413 } 414 if (GenerateCode(trip->op_a, nullptr, graph, block, &trip_expr, false, false)) { 415 if (taken_test != nullptr) { 416 HInstruction* zero = graph->GetConstant(trip->type, 0); 417 trip_expr = Insert(block, new (graph->GetArena()) HSelect(taken_test, trip_expr, zero, kNoDexPc)); 418 } 419 return trip_expr; 420 } 421 } 422 return nullptr; 423 } 424 425 // 426 // Private class methods. 427 // 428 429 bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, 430 ConstantRequest request, 431 /*out*/ int64_t* value) const { 432 if (info != nullptr) { 433 // A direct 32-bit or 64-bit constant fetch. This immediately satisfies 434 // any of the three requests (kExact, kAtMost, and KAtLeast). 435 if (info->induction_class == HInductionVarAnalysis::kInvariant && 436 info->operation == HInductionVarAnalysis::kFetch) { 437 if (IsInt64AndGet(info->fetch, value)) { 438 return true; 439 } 440 } 441 // Try range analysis on the invariant, only accept a proper range 442 // to avoid arithmetic wrap-around anomalies. 443 Value min_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ true); 444 Value max_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ false); 445 if (IsConstantValue(min_val) && 446 IsConstantValue(max_val) && min_val.b_constant <= max_val.b_constant) { 447 if ((request == kExact && min_val.b_constant == max_val.b_constant) || request == kAtMost) { 448 *value = max_val.b_constant; 449 return true; 450 } else if (request == kAtLeast) { 451 *value = min_val.b_constant; 452 return true; 453 } 454 } 455 } 456 return false; 457 } 458 459 bool InductionVarRange::HasInductionInfo( 460 HInstruction* context, 461 HInstruction* instruction, 462 /*out*/ HLoopInformation** loop, 463 /*out*/ HInductionVarAnalysis::InductionInfo** info, 464 /*out*/ HInductionVarAnalysis::InductionInfo** trip) const { 465 DCHECK(context != nullptr); 466 DCHECK(context->GetBlock() != nullptr); 467 HLoopInformation* lp = context->GetBlock()->GetLoopInformation(); // closest enveloping loop 468 if (lp != nullptr) { 469 HInductionVarAnalysis::InductionInfo* i = induction_analysis_->LookupInfo(lp, instruction); 470 if (i != nullptr) { 471 *loop = lp; 472 *info = i; 473 *trip = induction_analysis_->LookupInfo(lp, GetLoopControl(lp)); 474 return true; 475 } 476 } 477 return false; 478 } 479 480 bool InductionVarRange::IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const { 481 if (trip != nullptr) { 482 // Both bounds that define a trip-count are well-behaved if they either are not defined 483 // in any loop, or are contained in a proper interval. This allows finding the min/max 484 // of an expression by chasing outward. 485 InductionVarRange range(induction_analysis_); 486 HInductionVarAnalysis::InductionInfo* lower = trip->op_b->op_a; 487 HInductionVarAnalysis::InductionInfo* upper = trip->op_b->op_b; 488 int64_t not_used = 0; 489 return (!HasFetchInLoop(lower) || range.IsConstant(lower, kAtLeast, ¬_used)) && 490 (!HasFetchInLoop(upper) || range.IsConstant(upper, kAtLeast, ¬_used)); 491 } 492 return true; 493 } 494 495 bool InductionVarRange::HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const { 496 if (info != nullptr) { 497 if (info->induction_class == HInductionVarAnalysis::kInvariant && 498 info->operation == HInductionVarAnalysis::kFetch) { 499 return info->fetch->GetBlock()->GetLoopInformation() != nullptr; 500 } 501 return HasFetchInLoop(info->op_a) || HasFetchInLoop(info->op_b); 502 } 503 return false; 504 } 505 506 bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info, 507 int64_t* stride_value) const { 508 if (info != nullptr) { 509 if (info->induction_class == HInductionVarAnalysis::kLinear) { 510 return IsConstant(info->op_a, kExact, stride_value); 511 } else if (info->induction_class == HInductionVarAnalysis::kPolynomial) { 512 return NeedsTripCount(info->op_a, stride_value); 513 } else if (info->induction_class == HInductionVarAnalysis::kWrapAround) { 514 return NeedsTripCount(info->op_b, stride_value); 515 } 516 } 517 return false; 518 } 519 520 bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const { 521 if (trip != nullptr) { 522 if (trip->induction_class == HInductionVarAnalysis::kInvariant) { 523 return trip->operation == HInductionVarAnalysis::kTripCountInBody || 524 trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe; 525 } 526 } 527 return false; 528 } 529 530 bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const { 531 if (trip != nullptr) { 532 if (trip->induction_class == HInductionVarAnalysis::kInvariant) { 533 return trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe || 534 trip->operation == HInductionVarAnalysis::kTripCountInLoopUnsafe; 535 } 536 } 537 return false; 538 } 539 540 InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::InductionInfo* info, 541 HInductionVarAnalysis::InductionInfo* trip, 542 bool in_body, 543 bool is_min) const { 544 DCHECK(info != nullptr); 545 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kLinear); 546 // Detect common situation where an offset inside the trip-count cancels out during range 547 // analysis (finding max a * (TC - 1) + OFFSET for a == 1 and TC = UPPER - OFFSET or finding 548 // min a * (TC - 1) + OFFSET for a == -1 and TC = OFFSET - UPPER) to avoid losing information 549 // with intermediate results that only incorporate single instructions. 550 if (trip != nullptr) { 551 HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a; 552 if (trip_expr->type == info->type && trip_expr->operation == HInductionVarAnalysis::kSub) { 553 int64_t stride_value = 0; 554 if (IsConstant(info->op_a, kExact, &stride_value)) { 555 if (!is_min && stride_value == 1) { 556 // Test original trip's negative operand (trip_expr->op_b) against offset of induction. 557 if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) { 558 // Analyze cancelled trip with just the positive operand (trip_expr->op_a). 559 HInductionVarAnalysis::InductionInfo cancelled_trip( 560 trip->induction_class, 561 trip->operation, 562 trip_expr->op_a, 563 trip->op_b, 564 nullptr, 565 trip->type); 566 return GetVal(&cancelled_trip, trip, in_body, is_min); 567 } 568 } else if (is_min && stride_value == -1) { 569 // Test original trip's positive operand (trip_expr->op_a) against offset of induction. 570 if (HInductionVarAnalysis::InductionEqual(trip_expr->op_a, info->op_b)) { 571 // Analyze cancelled trip with just the negative operand (trip_expr->op_b). 572 HInductionVarAnalysis::InductionInfo neg( 573 HInductionVarAnalysis::kInvariant, 574 HInductionVarAnalysis::kNeg, 575 nullptr, 576 trip_expr->op_b, 577 nullptr, 578 trip->type); 579 HInductionVarAnalysis::InductionInfo cancelled_trip( 580 trip->induction_class, trip->operation, &neg, trip->op_b, nullptr, trip->type); 581 return SubValue(Value(0), GetVal(&cancelled_trip, trip, in_body, !is_min)); 582 } 583 } 584 } 585 } 586 } 587 // General rule of linear induction a * i + b, for normalized 0 <= i < TC. 588 return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min), 589 GetVal(info->op_b, trip, in_body, is_min)); 590 } 591 592 InductionVarRange::Value InductionVarRange::GetPolynomial(HInductionVarAnalysis::InductionInfo* info, 593 HInductionVarAnalysis::InductionInfo* trip, 594 bool in_body, 595 bool is_min) const { 596 DCHECK(info != nullptr); 597 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial); 598 int64_t a = 0; 599 int64_t b = 0; 600 if (IsConstant(info->op_a->op_a, kExact, &a) && CanLongValueFitIntoInt(a) && a >= 0 && 601 IsConstant(info->op_a->op_b, kExact, &b) && CanLongValueFitIntoInt(b) && b >= 0) { 602 // Evaluate bounds on sum_i=0^m-1(a * i + b) + c with a,b >= 0 for 603 // maximum index value m as a * (m * (m-1)) / 2 + b * m + c. 604 Value c = GetVal(info->op_b, trip, in_body, is_min); 605 if (is_min) { 606 return c; 607 } else { 608 Value m = GetVal(trip, trip, in_body, is_min); 609 Value t = DivValue(MulValue(m, SubValue(m, Value(1))), Value(2)); 610 Value x = MulValue(Value(a), t); 611 Value y = MulValue(Value(b), m); 612 return AddValue(AddValue(x, y), c); 613 } 614 } 615 return Value(); 616 } 617 618 InductionVarRange::Value InductionVarRange::GetGeometric(HInductionVarAnalysis::InductionInfo* info, 619 HInductionVarAnalysis::InductionInfo* trip, 620 bool in_body, 621 bool is_min) const { 622 DCHECK(info != nullptr); 623 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric); 624 int64_t a = 0; 625 int64_t f = 0; 626 if (IsConstant(info->op_a, kExact, &a) && 627 CanLongValueFitIntoInt(a) && 628 IsInt64AndGet(info->fetch, &f) && f >= 1) { 629 // Conservative bounds on a * f^-i + b with f >= 1 can be computed without 630 // trip count. Other forms would require a much more elaborate evaluation. 631 const bool is_min_a = a >= 0 ? is_min : !is_min; 632 if (info->operation == HInductionVarAnalysis::kDiv) { 633 Value b = GetVal(info->op_b, trip, in_body, is_min); 634 return is_min_a ? b : AddValue(Value(a), b); 635 } 636 } 637 return Value(); 638 } 639 640 InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, 641 HInductionVarAnalysis::InductionInfo* trip, 642 bool in_body, 643 bool is_min) const { 644 // Special case when chasing constants: single instruction that denotes trip count in the 645 // loop-body is minimal 1 and maximal, with safe trip-count, max int, 646 if (chase_hint_ == nullptr && in_body && trip != nullptr && instruction == trip->op_a->fetch) { 647 if (is_min) { 648 return Value(1); 649 } else if (!instruction->IsConstant() && !IsUnsafeTripCount(trip)) { 650 return Value(std::numeric_limits<int32_t>::max()); 651 } 652 } 653 // Unless at a constant or hint, chase the instruction a bit deeper into the HIR tree, so that 654 // it becomes more likely range analysis will compare the same instructions as terminal nodes. 655 int64_t value; 656 if (IsInt64AndGet(instruction, &value) && CanLongValueFitIntoInt(value)) { 657 // Proper constant reveals best information. 658 return Value(static_cast<int32_t>(value)); 659 } else if (instruction == chase_hint_) { 660 // At hint, fetch is represented by itself. 661 return Value(instruction, 1, 0); 662 } else if (instruction->IsAdd()) { 663 // Incorporate suitable constants in the chased value. 664 if (IsInt64AndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) { 665 return AddValue(Value(static_cast<int32_t>(value)), 666 GetFetch(instruction->InputAt(1), trip, in_body, is_min)); 667 } else if (IsInt64AndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) { 668 return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), 669 Value(static_cast<int32_t>(value))); 670 } 671 } else if (instruction->IsArrayLength()) { 672 // Exploit length properties when chasing constants or chase into a new array declaration. 673 if (chase_hint_ == nullptr) { 674 return is_min ? Value(0) : Value(std::numeric_limits<int32_t>::max()); 675 } else if (instruction->InputAt(0)->IsNewArray()) { 676 return GetFetch(instruction->InputAt(0)->AsNewArray()->GetLength(), trip, in_body, is_min); 677 } 678 } else if (instruction->IsTypeConversion()) { 679 // Since analysis is 32-bit (or narrower), chase beyond widening along the path. 680 // For example, this discovers the length in: for (long i = 0; i < a.length; i++); 681 if (instruction->AsTypeConversion()->GetInputType() == Primitive::kPrimInt && 682 instruction->AsTypeConversion()->GetResultType() == Primitive::kPrimLong) { 683 return GetFetch(instruction->InputAt(0), trip, in_body, is_min); 684 } 685 } 686 // Chase an invariant fetch that is defined by an outer loop if the trip-count used 687 // so far is well-behaved in both bounds and the next trip-count is safe. 688 // Example: 689 // for (int i = 0; i <= 100; i++) // safe 690 // for (int j = 0; j <= i; j++) // well-behaved 691 // j is in range [0, i ] (if i is chase hint) 692 // or in range [0, 100] (otherwise) 693 HLoopInformation* next_loop = nullptr; 694 HInductionVarAnalysis::InductionInfo* next_info = nullptr; 695 HInductionVarAnalysis::InductionInfo* next_trip = nullptr; 696 bool next_in_body = true; // inner loop is always in body of outer loop 697 if (HasInductionInfo(instruction, instruction, &next_loop, &next_info, &next_trip) && 698 IsWellBehavedTripCount(trip) && 699 !IsUnsafeTripCount(next_trip)) { 700 return GetVal(next_info, next_trip, next_in_body, is_min); 701 } 702 // Fetch is represented by itself. 703 return Value(instruction, 1, 0); 704 } 705 706 InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info, 707 HInductionVarAnalysis::InductionInfo* trip, 708 bool in_body, 709 bool is_min) const { 710 if (info != nullptr) { 711 switch (info->induction_class) { 712 case HInductionVarAnalysis::kInvariant: 713 // Invariants. 714 switch (info->operation) { 715 case HInductionVarAnalysis::kAdd: 716 return AddValue(GetVal(info->op_a, trip, in_body, is_min), 717 GetVal(info->op_b, trip, in_body, is_min)); 718 case HInductionVarAnalysis::kSub: // second reversed! 719 return SubValue(GetVal(info->op_a, trip, in_body, is_min), 720 GetVal(info->op_b, trip, in_body, !is_min)); 721 case HInductionVarAnalysis::kNeg: // second reversed! 722 return SubValue(Value(0), 723 GetVal(info->op_b, trip, in_body, !is_min)); 724 case HInductionVarAnalysis::kMul: 725 return GetMul(info->op_a, info->op_b, trip, in_body, is_min); 726 case HInductionVarAnalysis::kDiv: 727 return GetDiv(info->op_a, info->op_b, trip, in_body, is_min); 728 case HInductionVarAnalysis::kRem: 729 return GetRem(info->op_a, info->op_b); 730 case HInductionVarAnalysis::kXor: 731 return GetXor(info->op_a, info->op_b); 732 case HInductionVarAnalysis::kFetch: 733 return GetFetch(info->fetch, trip, in_body, is_min); 734 case HInductionVarAnalysis::kTripCountInLoop: 735 case HInductionVarAnalysis::kTripCountInLoopUnsafe: 736 if (!in_body && !is_min) { // one extra! 737 return GetVal(info->op_a, trip, in_body, is_min); 738 } 739 FALLTHROUGH_INTENDED; 740 case HInductionVarAnalysis::kTripCountInBody: 741 case HInductionVarAnalysis::kTripCountInBodyUnsafe: 742 if (is_min) { 743 return Value(0); 744 } else if (in_body) { 745 return SubValue(GetVal(info->op_a, trip, in_body, is_min), Value(1)); 746 } 747 break; 748 default: 749 break; 750 } 751 break; 752 case HInductionVarAnalysis::kLinear: 753 return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type); 754 case HInductionVarAnalysis::kPolynomial: 755 return GetPolynomial(info, trip, in_body, is_min); 756 case HInductionVarAnalysis::kGeometric: 757 return GetGeometric(info, trip, in_body, is_min); 758 case HInductionVarAnalysis::kWrapAround: 759 case HInductionVarAnalysis::kPeriodic: 760 return MergeVal(GetVal(info->op_a, trip, in_body, is_min), 761 GetVal(info->op_b, trip, in_body, is_min), is_min); 762 } 763 } 764 return Value(); 765 } 766 767 InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1, 768 HInductionVarAnalysis::InductionInfo* info2, 769 HInductionVarAnalysis::InductionInfo* trip, 770 bool in_body, 771 bool is_min) const { 772 // Constant times range. 773 int64_t value = 0; 774 if (IsConstant(info1, kExact, &value)) { 775 return MulRangeAndConstant(value, info2, trip, in_body, is_min); 776 } else if (IsConstant(info2, kExact, &value)) { 777 return MulRangeAndConstant(value, info1, trip, in_body, is_min); 778 } 779 // Interval ranges. 780 Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true); 781 Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false); 782 Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true); 783 Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false); 784 // Positive range vs. positive or negative range. 785 if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { 786 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 787 return is_min ? MulValue(v1_min, v2_min) : MulValue(v1_max, v2_max); 788 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 789 return is_min ? MulValue(v1_max, v2_min) : MulValue(v1_min, v2_max); 790 } 791 } 792 // Negative range vs. positive or negative range. 793 if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) { 794 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 795 return is_min ? MulValue(v1_min, v2_max) : MulValue(v1_max, v2_min); 796 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 797 return is_min ? MulValue(v1_max, v2_max) : MulValue(v1_min, v2_min); 798 } 799 } 800 return Value(); 801 } 802 803 InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1, 804 HInductionVarAnalysis::InductionInfo* info2, 805 HInductionVarAnalysis::InductionInfo* trip, 806 bool in_body, 807 bool is_min) const { 808 // Range divided by constant. 809 int64_t value = 0; 810 if (IsConstant(info2, kExact, &value)) { 811 return DivRangeAndConstant(value, info1, trip, in_body, is_min); 812 } 813 // Interval ranges. 814 Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true); 815 Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false); 816 Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true); 817 Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false); 818 // Positive range vs. positive or negative range. 819 if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { 820 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 821 return is_min ? DivValue(v1_min, v2_max) : DivValue(v1_max, v2_min); 822 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 823 return is_min ? DivValue(v1_max, v2_max) : DivValue(v1_min, v2_min); 824 } 825 } 826 // Negative range vs. positive or negative range. 827 if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) { 828 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 829 return is_min ? DivValue(v1_min, v2_min) : DivValue(v1_max, v2_max); 830 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 831 return is_min ? DivValue(v1_max, v2_min) : DivValue(v1_min, v2_max); 832 } 833 } 834 return Value(); 835 } 836 837 InductionVarRange::Value InductionVarRange::GetRem( 838 HInductionVarAnalysis::InductionInfo* info1, 839 HInductionVarAnalysis::InductionInfo* info2) const { 840 int64_t v1 = 0; 841 int64_t v2 = 0; 842 // Only accept exact values. 843 if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2) && v2 != 0) { 844 int64_t value = v1 % v2; 845 if (CanLongValueFitIntoInt(value)) { 846 return Value(static_cast<int32_t>(value)); 847 } 848 } 849 return Value(); 850 } 851 852 InductionVarRange::Value InductionVarRange::GetXor( 853 HInductionVarAnalysis::InductionInfo* info1, 854 HInductionVarAnalysis::InductionInfo* info2) const { 855 int64_t v1 = 0; 856 int64_t v2 = 0; 857 // Only accept exact values. 858 if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2)) { 859 int64_t value = v1 ^ v2; 860 if (CanLongValueFitIntoInt(value)) { 861 return Value(static_cast<int32_t>(value)); 862 } 863 } 864 return Value(); 865 } 866 867 InductionVarRange::Value InductionVarRange::MulRangeAndConstant( 868 int64_t value, 869 HInductionVarAnalysis::InductionInfo* info, 870 HInductionVarAnalysis::InductionInfo* trip, 871 bool in_body, 872 bool is_min) const { 873 if (CanLongValueFitIntoInt(value)) { 874 Value c(static_cast<int32_t>(value)); 875 return MulValue(GetVal(info, trip, in_body, is_min == value >= 0), c); 876 } 877 return Value(); 878 } 879 880 InductionVarRange::Value InductionVarRange::DivRangeAndConstant( 881 int64_t value, 882 HInductionVarAnalysis::InductionInfo* info, 883 HInductionVarAnalysis::InductionInfo* trip, 884 bool in_body, 885 bool is_min) const { 886 if (CanLongValueFitIntoInt(value)) { 887 Value c(static_cast<int32_t>(value)); 888 return DivValue(GetVal(info, trip, in_body, is_min == value >= 0), c); 889 } 890 return Value(); 891 } 892 893 InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const { 894 if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) { 895 int32_t b = v1.b_constant + v2.b_constant; 896 if (v1.a_constant == 0) { 897 return Value(v2.instruction, v2.a_constant, b); 898 } else if (v2.a_constant == 0) { 899 return Value(v1.instruction, v1.a_constant, b); 900 } else if (v1.instruction == v2.instruction && IsSafeAdd(v1.a_constant, v2.a_constant)) { 901 return Value(v1.instruction, v1.a_constant + v2.a_constant, b); 902 } 903 } 904 return Value(); 905 } 906 907 InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) const { 908 if (v1.is_known && v2.is_known && IsSafeSub(v1.b_constant, v2.b_constant)) { 909 int32_t b = v1.b_constant - v2.b_constant; 910 if (v1.a_constant == 0 && IsSafeSub(0, v2.a_constant)) { 911 return Value(v2.instruction, -v2.a_constant, b); 912 } else if (v2.a_constant == 0) { 913 return Value(v1.instruction, v1.a_constant, b); 914 } else if (v1.instruction == v2.instruction && IsSafeSub(v1.a_constant, v2.a_constant)) { 915 return Value(v1.instruction, v1.a_constant - v2.a_constant, b); 916 } 917 } 918 return Value(); 919 } 920 921 InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) const { 922 if (v1.is_known && v2.is_known) { 923 if (v1.a_constant == 0) { 924 if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) { 925 return Value(v2.instruction, v1.b_constant * v2.a_constant, v1.b_constant * v2.b_constant); 926 } 927 } else if (v2.a_constant == 0) { 928 if (IsSafeMul(v1.a_constant, v2.b_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) { 929 return Value(v1.instruction, v1.a_constant * v2.b_constant, v1.b_constant * v2.b_constant); 930 } 931 } 932 } 933 return Value(); 934 } 935 936 InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) const { 937 if (v1.is_known && v2.is_known && v1.a_constant == 0 && v2.a_constant == 0) { 938 if (IsSafeDiv(v1.b_constant, v2.b_constant)) { 939 return Value(v1.b_constant / v2.b_constant); 940 } 941 } 942 return Value(); 943 } 944 945 InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is_min) const { 946 if (v1.is_known && v2.is_known) { 947 if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) { 948 return Value(v1.instruction, v1.a_constant, 949 is_min ? std::min(v1.b_constant, v2.b_constant) 950 : std::max(v1.b_constant, v2.b_constant)); 951 } 952 } 953 return Value(); 954 } 955 956 bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, 957 HInstruction* instruction, 958 bool is_last_value, 959 HGraph* graph, 960 HBasicBlock* block, 961 /*out*/HInstruction** lower, 962 /*out*/HInstruction** upper, 963 /*out*/HInstruction** taken_test, 964 /*out*/int64_t* stride_value, 965 /*out*/bool* needs_finite_test, 966 /*out*/bool* needs_taken_test) const { 967 HLoopInformation* loop = nullptr; 968 HInductionVarAnalysis::InductionInfo* info = nullptr; 969 HInductionVarAnalysis::InductionInfo* trip = nullptr; 970 if (!HasInductionInfo(context, instruction, &loop, &info, &trip) || trip == nullptr) { 971 return false; // codegen needs all information, including tripcount 972 } 973 // Determine what tests are needed. A finite test is needed if the evaluation code uses the 974 // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot" 975 // the computed range). A taken test is needed for any unknown trip-count, even if evaluation 976 // code does not use the trip-count explicitly (since there could be an implicit relation 977 // between e.g. an invariant subscript and a not-taken condition). 978 bool in_body = context->GetBlock() != loop->GetHeader(); 979 *stride_value = 0; 980 *needs_finite_test = NeedsTripCount(info, stride_value) && IsUnsafeTripCount(trip); 981 *needs_taken_test = IsBodyTripCount(trip); 982 // Handle last value request. 983 if (is_last_value) { 984 DCHECK(!in_body); 985 switch (info->induction_class) { 986 case HInductionVarAnalysis::kLinear: 987 if (*stride_value > 0) { 988 lower = nullptr; 989 } else { 990 upper = nullptr; 991 } 992 break; 993 case HInductionVarAnalysis::kPolynomial: 994 return GenerateLastValuePolynomial(info, trip, graph, block, lower); 995 case HInductionVarAnalysis::kGeometric: 996 return GenerateLastValueGeometric(info, trip, graph, block, lower); 997 case HInductionVarAnalysis::kWrapAround: 998 return GenerateLastValueWrapAround(info, trip, graph, block, lower); 999 case HInductionVarAnalysis::kPeriodic: 1000 return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test); 1001 default: 1002 return false; 1003 } 1004 } 1005 // Code generation for taken test: generate the code when requested or otherwise analyze 1006 // if code generation is feasible when taken test is needed. 1007 if (taken_test != nullptr) { 1008 return GenerateCode(trip->op_b, nullptr, graph, block, taken_test, in_body, /* is_min */ false); 1009 } else if (*needs_taken_test) { 1010 if (!GenerateCode( 1011 trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min */ false)) { 1012 return false; 1013 } 1014 } 1015 // Code generation for lower and upper. 1016 return 1017 // Success on lower if invariant (not set), or code can be generated. 1018 ((info->induction_class == HInductionVarAnalysis::kInvariant) || 1019 GenerateCode(info, trip, graph, block, lower, in_body, /* is_min */ true)) && 1020 // And success on upper. 1021 GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ false); 1022 } 1023 1024 bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::InductionInfo* info, 1025 HInductionVarAnalysis::InductionInfo* trip, 1026 HGraph* graph, 1027 HBasicBlock* block, 1028 /*out*/HInstruction** result) const { 1029 DCHECK(info != nullptr); 1030 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial); 1031 // Detect known coefficients and trip count (always taken). 1032 int64_t a = 0; 1033 int64_t b = 0; 1034 int64_t m = 0; 1035 if (IsConstant(info->op_a->op_a, kExact, &a) && 1036 IsConstant(info->op_a->op_b, kExact, &b) && 1037 IsConstant(trip->op_a, kExact, &m) && m >= 1) { 1038 // Evaluate bounds on sum_i=0^m-1(a * i + b) + c for known 1039 // maximum index value m as a * (m * (m-1)) / 2 + b * m + c. 1040 HInstruction* c = nullptr; 1041 if (GenerateCode(info->op_b, nullptr, graph, block, graph ? &c : nullptr, false, false)) { 1042 if (graph != nullptr) { 1043 Primitive::Type type = info->type; 1044 int64_t sum = a * ((m * (m - 1)) / 2) + b * m; 1045 if (type != Primitive::kPrimLong) { 1046 sum = static_cast<int32_t>(sum); // okay to truncate 1047 } 1048 *result = 1049 Insert(block, new (graph->GetArena()) HAdd(type, graph->GetConstant(type, sum), c)); 1050 } 1051 return true; 1052 } 1053 } 1054 return false; 1055 } 1056 1057 bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::InductionInfo* info, 1058 HInductionVarAnalysis::InductionInfo* trip, 1059 HGraph* graph, 1060 HBasicBlock* block, 1061 /*out*/HInstruction** result) const { 1062 DCHECK(info != nullptr); 1063 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric); 1064 // Detect known base and trip count (always taken). 1065 int64_t f = 0; 1066 int64_t m = 0; 1067 if (IsInt64AndGet(info->fetch, &f) && f >= 1 && IsConstant(trip->op_a, kExact, &m) && m >= 1) { 1068 HInstruction* opa = nullptr; 1069 HInstruction* opb = nullptr; 1070 if (GenerateCode(info->op_a, nullptr, graph, block, &opa, false, false) && 1071 GenerateCode(info->op_b, nullptr, graph, block, &opb, false, false)) { 1072 if (graph != nullptr) { 1073 Primitive::Type type = info->type; 1074 // Compute f ^ m for known maximum index value m. 1075 bool overflow = false; 1076 int64_t fpow = IntPow(f, m, &overflow); 1077 if (info->operation == HInductionVarAnalysis::kDiv) { 1078 // For division, any overflow truncates to zero. 1079 if (overflow || (type != Primitive::kPrimLong && !CanLongValueFitIntoInt(fpow))) { 1080 fpow = 0; 1081 } 1082 } else if (type != Primitive::kPrimLong) { 1083 // For multiplication, okay to truncate to required precision. 1084 DCHECK(info->operation == HInductionVarAnalysis::kMul); 1085 fpow = static_cast<int32_t>(fpow); 1086 } 1087 // Generate code. 1088 if (fpow == 0) { 1089 // Special case: repeated mul/div always yields zero. 1090 *result = graph->GetConstant(type, 0); 1091 } else { 1092 // Last value: a * f ^ m + b or a * f ^ -m + b. 1093 HInstruction* e = nullptr; 1094 if (info->operation == HInductionVarAnalysis::kMul) { 1095 e = new (graph->GetArena()) HMul(type, opa, graph->GetConstant(type, fpow)); 1096 } else { 1097 e = new (graph->GetArena()) HDiv(type, opa, graph->GetConstant(type, fpow), kNoDexPc); 1098 } 1099 *result = Insert(block, new (graph->GetArena()) HAdd(type, Insert(block, e), opb)); 1100 } 1101 } 1102 return true; 1103 } 1104 } 1105 return false; 1106 } 1107 1108 bool InductionVarRange::GenerateLastValueWrapAround(HInductionVarAnalysis::InductionInfo* info, 1109 HInductionVarAnalysis::InductionInfo* trip, 1110 HGraph* graph, 1111 HBasicBlock* block, 1112 /*out*/HInstruction** result) const { 1113 DCHECK(info != nullptr); 1114 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kWrapAround); 1115 // Count depth. 1116 int32_t depth = 0; 1117 for (; info->induction_class == HInductionVarAnalysis::kWrapAround; 1118 info = info->op_b, ++depth) {} 1119 // Handle wrap(x, wrap(.., y)) if trip count reaches an invariant at end. 1120 // TODO: generalize, but be careful to adjust the terminal. 1121 int64_t m = 0; 1122 if (info->induction_class == HInductionVarAnalysis::kInvariant && 1123 IsConstant(trip->op_a, kExact, &m) && m >= depth) { 1124 return GenerateCode(info, nullptr, graph, block, result, false, false); 1125 } 1126 return false; 1127 } 1128 1129 bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info, 1130 HInductionVarAnalysis::InductionInfo* trip, 1131 HGraph* graph, 1132 HBasicBlock* block, 1133 /*out*/HInstruction** result, 1134 /*out*/bool* needs_taken_test) const { 1135 DCHECK(info != nullptr); 1136 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPeriodic); 1137 // Count period and detect all-invariants. 1138 int64_t period = 1; 1139 bool all_invariants = true; 1140 HInductionVarAnalysis::InductionInfo* p = info; 1141 for (; p->induction_class == HInductionVarAnalysis::kPeriodic; p = p->op_b, ++period) { 1142 DCHECK_EQ(p->op_a->induction_class, HInductionVarAnalysis::kInvariant); 1143 if (p->op_a->operation != HInductionVarAnalysis::kFetch) { 1144 all_invariants = false; 1145 } 1146 } 1147 DCHECK_EQ(p->induction_class, HInductionVarAnalysis::kInvariant); 1148 if (p->operation != HInductionVarAnalysis::kFetch) { 1149 all_invariants = false; 1150 } 1151 // Don't rely on FP arithmetic to be precise, unless the full period 1152 // consist of pre-computed expressions only. 1153 if (info->type == Primitive::kPrimFloat || info->type == Primitive::kPrimDouble) { 1154 if (!all_invariants) { 1155 return false; 1156 } 1157 } 1158 // Handle any periodic(x, periodic(.., y)) for known maximum index value m. 1159 int64_t m = 0; 1160 if (IsConstant(trip->op_a, kExact, &m) && m >= 1) { 1161 int64_t li = m % period; 1162 for (int64_t i = 0; i < li; info = info->op_b, i++) {} 1163 if (info->induction_class == HInductionVarAnalysis::kPeriodic) { 1164 info = info->op_a; 1165 } 1166 return GenerateCode(info, nullptr, graph, block, result, false, false); 1167 } 1168 // Handle periodic(x, y) using even/odd-select on trip count. Enter trip count expression 1169 // directly to obtain the maximum index value t even if taken test is needed. 1170 HInstruction* x = nullptr; 1171 HInstruction* y = nullptr; 1172 HInstruction* t = nullptr; 1173 if (period == 2 && 1174 GenerateCode(info->op_a, nullptr, graph, block, graph ? &x : nullptr, false, false) && 1175 GenerateCode(info->op_b, nullptr, graph, block, graph ? &y : nullptr, false, false) && 1176 GenerateCode(trip->op_a, nullptr, graph, block, graph ? &t : nullptr, false, false)) { 1177 // During actual code generation (graph != nullptr), generate is_even ? x : y. 1178 if (graph != nullptr) { 1179 Primitive::Type type = trip->type; 1180 HInstruction* msk = 1181 Insert(block, new (graph->GetArena()) HAnd(type, t, graph->GetConstant(type, 1))); 1182 HInstruction* is_even = 1183 Insert(block, new (graph->GetArena()) HEqual(msk, graph->GetConstant(type, 0), kNoDexPc)); 1184 *result = Insert(block, new (graph->GetArena()) HSelect(is_even, x, y, kNoDexPc)); 1185 } 1186 // Guard select with taken test if needed. 1187 if (*needs_taken_test) { 1188 HInstruction* is_taken = nullptr; 1189 if (GenerateCode(trip->op_b, nullptr, graph, block, graph ? &is_taken : nullptr, false, false)) { 1190 if (graph != nullptr) { 1191 *result = Insert(block, new (graph->GetArena()) HSelect(is_taken, *result, x, kNoDexPc)); 1192 } 1193 *needs_taken_test = false; // taken care of 1194 } else { 1195 return false; 1196 } 1197 } 1198 return true; 1199 } 1200 return false; 1201 } 1202 1203 bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, 1204 HInductionVarAnalysis::InductionInfo* trip, 1205 HGraph* graph, // when set, code is generated 1206 HBasicBlock* block, 1207 /*out*/HInstruction** result, 1208 bool in_body, 1209 bool is_min) const { 1210 if (info != nullptr) { 1211 // If during codegen, the result is not needed (nullptr), simply return success. 1212 if (graph != nullptr && result == nullptr) { 1213 return true; 1214 } 1215 // Handle current operation. 1216 Primitive::Type type = info->type; 1217 HInstruction* opa = nullptr; 1218 HInstruction* opb = nullptr; 1219 switch (info->induction_class) { 1220 case HInductionVarAnalysis::kInvariant: 1221 // Invariants (note that since invariants only have other invariants as 1222 // sub expressions, viz. no induction, there is no need to adjust is_min). 1223 switch (info->operation) { 1224 case HInductionVarAnalysis::kAdd: 1225 case HInductionVarAnalysis::kSub: 1226 case HInductionVarAnalysis::kMul: 1227 case HInductionVarAnalysis::kDiv: 1228 case HInductionVarAnalysis::kRem: 1229 case HInductionVarAnalysis::kXor: 1230 case HInductionVarAnalysis::kLT: 1231 case HInductionVarAnalysis::kLE: 1232 case HInductionVarAnalysis::kGT: 1233 case HInductionVarAnalysis::kGE: 1234 if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) && 1235 GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) { 1236 if (graph != nullptr) { 1237 HInstruction* operation = nullptr; 1238 switch (info->operation) { 1239 case HInductionVarAnalysis::kAdd: 1240 operation = new (graph->GetArena()) HAdd(type, opa, opb); break; 1241 case HInductionVarAnalysis::kSub: 1242 operation = new (graph->GetArena()) HSub(type, opa, opb); break; 1243 case HInductionVarAnalysis::kMul: 1244 operation = new (graph->GetArena()) HMul(type, opa, opb, kNoDexPc); break; 1245 case HInductionVarAnalysis::kDiv: 1246 operation = new (graph->GetArena()) HDiv(type, opa, opb, kNoDexPc); break; 1247 case HInductionVarAnalysis::kRem: 1248 operation = new (graph->GetArena()) HRem(type, opa, opb, kNoDexPc); break; 1249 case HInductionVarAnalysis::kXor: 1250 operation = new (graph->GetArena()) HXor(type, opa, opb); break; 1251 case HInductionVarAnalysis::kLT: 1252 operation = new (graph->GetArena()) HLessThan(opa, opb); break; 1253 case HInductionVarAnalysis::kLE: 1254 operation = new (graph->GetArena()) HLessThanOrEqual(opa, opb); break; 1255 case HInductionVarAnalysis::kGT: 1256 operation = new (graph->GetArena()) HGreaterThan(opa, opb); break; 1257 case HInductionVarAnalysis::kGE: 1258 operation = new (graph->GetArena()) HGreaterThanOrEqual(opa, opb); break; 1259 default: 1260 LOG(FATAL) << "unknown operation"; 1261 } 1262 *result = Insert(block, operation); 1263 } 1264 return true; 1265 } 1266 break; 1267 case HInductionVarAnalysis::kNeg: 1268 if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) { 1269 if (graph != nullptr) { 1270 *result = Insert(block, new (graph->GetArena()) HNeg(type, opb)); 1271 } 1272 return true; 1273 } 1274 break; 1275 case HInductionVarAnalysis::kFetch: 1276 if (graph != nullptr) { 1277 *result = info->fetch; // already in HIR 1278 } 1279 return true; 1280 case HInductionVarAnalysis::kTripCountInLoop: 1281 case HInductionVarAnalysis::kTripCountInLoopUnsafe: 1282 if (!in_body && !is_min) { // one extra! 1283 return GenerateCode(info->op_a, trip, graph, block, result, in_body, is_min); 1284 } 1285 FALLTHROUGH_INTENDED; 1286 case HInductionVarAnalysis::kTripCountInBody: 1287 case HInductionVarAnalysis::kTripCountInBodyUnsafe: 1288 if (is_min) { 1289 if (graph != nullptr) { 1290 *result = graph->GetConstant(type, 0); 1291 } 1292 return true; 1293 } else if (in_body) { 1294 if (GenerateCode(info->op_a, trip, graph, block, &opb, in_body, is_min)) { 1295 if (graph != nullptr) { 1296 *result = 1297 Insert(block, 1298 new (graph->GetArena()) HSub(type, opb, graph->GetConstant(type, 1))); 1299 } 1300 return true; 1301 } 1302 } 1303 break; 1304 case HInductionVarAnalysis::kNop: 1305 LOG(FATAL) << "unexpected invariant nop"; 1306 } // switch invariant operation 1307 break; 1308 case HInductionVarAnalysis::kLinear: { 1309 // Linear induction a * i + b, for normalized 0 <= i < TC. For ranges, this should 1310 // be restricted to a unit stride to avoid arithmetic wrap-around situations that 1311 // are harder to guard against. For a last value, requesting min/max based on any 1312 // known stride yields right value. Always avoid any narrowing linear induction or 1313 // any type mismatch between the linear induction and the trip count expression. 1314 // TODO: careful runtime type conversions could generalize this latter restriction. 1315 if (!HInductionVarAnalysis::IsNarrowingLinear(info) && trip->type == type) { 1316 int64_t stride_value = 0; 1317 if (IsConstant(info->op_a, kExact, &stride_value) && 1318 CanLongValueFitIntoInt(stride_value)) { 1319 const bool is_min_a = stride_value >= 0 ? is_min : !is_min; 1320 if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) && 1321 GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) { 1322 if (graph != nullptr) { 1323 HInstruction* oper; 1324 if (stride_value == 1) { 1325 oper = new (graph->GetArena()) HAdd(type, opa, opb); 1326 } else if (stride_value == -1) { 1327 oper = new (graph->GetArena()) HSub(type, opb, opa); 1328 } else { 1329 HInstruction* mul = 1330 new (graph->GetArena()) HMul(type, graph->GetConstant(type, stride_value), opa); 1331 oper = new (graph->GetArena()) HAdd(type, Insert(block, mul), opb); 1332 } 1333 *result = Insert(block, oper); 1334 } 1335 return true; 1336 } 1337 } 1338 } 1339 break; 1340 } 1341 case HInductionVarAnalysis::kPolynomial: 1342 case HInductionVarAnalysis::kGeometric: 1343 break; 1344 case HInductionVarAnalysis::kWrapAround: 1345 case HInductionVarAnalysis::kPeriodic: { 1346 // Wrap-around and periodic inductions are restricted to constants only, so that extreme 1347 // values are easy to test at runtime without complications of arithmetic wrap-around. 1348 Value extreme = GetVal(info, trip, in_body, is_min); 1349 if (IsConstantValue(extreme)) { 1350 if (graph != nullptr) { 1351 *result = graph->GetConstant(type, extreme.b_constant); 1352 } 1353 return true; 1354 } 1355 break; 1356 } 1357 } // switch induction class 1358 } 1359 return false; 1360 } 1361 1362 void InductionVarRange::ReplaceInduction(HInductionVarAnalysis::InductionInfo* info, 1363 HInstruction* fetch, 1364 HInstruction* replacement) { 1365 if (info != nullptr) { 1366 if (info->induction_class == HInductionVarAnalysis::kInvariant && 1367 info->operation == HInductionVarAnalysis::kFetch && 1368 info->fetch == fetch) { 1369 info->fetch = replacement; 1370 } 1371 ReplaceInduction(info->op_a, fetch, replacement); 1372 ReplaceInduction(info->op_b, fetch, replacement); 1373 } 1374 } 1375 1376 } // namespace art 1377
