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