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 /*out*/ HInstruction** offset) const { 377 HLoopInformation* loop = nullptr; 378 HInductionVarAnalysis::InductionInfo* info = nullptr; 379 HInductionVarAnalysis::InductionInfo* trip = nullptr; 380 if (HasInductionInfo(context, instruction, &loop, &info, &trip)) { 381 if (info->induction_class == HInductionVarAnalysis::kLinear && 382 info->op_b->operation == HInductionVarAnalysis::kFetch && 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) && off_value == 0) { 388 *offset = nullptr; 389 } else { 390 *offset = info->op_b->fetch; 391 } 392 return true; 393 } 394 } 395 } 396 return false; 397 } 398 399 HInstruction* InductionVarRange::GenerateTripCount(HLoopInformation* loop, 400 HGraph* graph, 401 HBasicBlock* block) { 402 HInductionVarAnalysis::InductionInfo *trip = 403 induction_analysis_->LookupInfo(loop, GetLoopControl(loop)); 404 if (trip != nullptr && !IsUnsafeTripCount(trip)) { 405 HInstruction* taken_test = nullptr; 406 HInstruction* trip_expr = nullptr; 407 if (IsBodyTripCount(trip)) { 408 if (!GenerateCode(trip->op_b, nullptr, graph, block, &taken_test, false, false)) { 409 return nullptr; 410 } 411 } 412 if (GenerateCode(trip->op_a, nullptr, graph, block, &trip_expr, false, false)) { 413 if (taken_test != nullptr) { 414 HInstruction* zero = graph->GetConstant(trip->type, 0); 415 trip_expr = Insert(block, new (graph->GetArena()) HSelect(taken_test, trip_expr, zero, kNoDexPc)); 416 } 417 return trip_expr; 418 } 419 } 420 return nullptr; 421 } 422 423 // 424 // Private class methods. 425 // 426 427 bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, 428 ConstantRequest request, 429 /*out*/ int64_t* value) const { 430 if (info != nullptr) { 431 // A direct 32-bit or 64-bit constant fetch. This immediately satisfies 432 // any of the three requests (kExact, kAtMost, and KAtLeast). 433 if (info->induction_class == HInductionVarAnalysis::kInvariant && 434 info->operation == HInductionVarAnalysis::kFetch) { 435 if (IsInt64AndGet(info->fetch, value)) { 436 return true; 437 } 438 } 439 // Try range analysis on the invariant, only accept a proper range 440 // to avoid arithmetic wrap-around anomalies. 441 Value min_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ true); 442 Value max_val = GetVal(info, nullptr, /* in_body */ true, /* is_min */ false); 443 if (IsConstantValue(min_val) && 444 IsConstantValue(max_val) && min_val.b_constant <= max_val.b_constant) { 445 if ((request == kExact && min_val.b_constant == max_val.b_constant) || request == kAtMost) { 446 *value = max_val.b_constant; 447 return true; 448 } else if (request == kAtLeast) { 449 *value = min_val.b_constant; 450 return true; 451 } 452 } 453 } 454 return false; 455 } 456 457 bool InductionVarRange::HasInductionInfo( 458 HInstruction* context, 459 HInstruction* instruction, 460 /*out*/ HLoopInformation** loop, 461 /*out*/ HInductionVarAnalysis::InductionInfo** info, 462 /*out*/ HInductionVarAnalysis::InductionInfo** trip) const { 463 DCHECK(context != nullptr); 464 DCHECK(context->GetBlock() != nullptr); 465 HLoopInformation* lp = context->GetBlock()->GetLoopInformation(); // closest enveloping loop 466 if (lp != nullptr) { 467 HInductionVarAnalysis::InductionInfo* i = induction_analysis_->LookupInfo(lp, instruction); 468 if (i != nullptr) { 469 *loop = lp; 470 *info = i; 471 *trip = induction_analysis_->LookupInfo(lp, GetLoopControl(lp)); 472 return true; 473 } 474 } 475 return false; 476 } 477 478 bool InductionVarRange::IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const { 479 if (trip != nullptr) { 480 // Both bounds that define a trip-count are well-behaved if they either are not defined 481 // in any loop, or are contained in a proper interval. This allows finding the min/max 482 // of an expression by chasing outward. 483 InductionVarRange range(induction_analysis_); 484 HInductionVarAnalysis::InductionInfo* lower = trip->op_b->op_a; 485 HInductionVarAnalysis::InductionInfo* upper = trip->op_b->op_b; 486 int64_t not_used = 0; 487 return (!HasFetchInLoop(lower) || range.IsConstant(lower, kAtLeast, ¬_used)) && 488 (!HasFetchInLoop(upper) || range.IsConstant(upper, kAtLeast, ¬_used)); 489 } 490 return true; 491 } 492 493 bool InductionVarRange::HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const { 494 if (info != nullptr) { 495 if (info->induction_class == HInductionVarAnalysis::kInvariant && 496 info->operation == HInductionVarAnalysis::kFetch) { 497 return info->fetch->GetBlock()->GetLoopInformation() != nullptr; 498 } 499 return HasFetchInLoop(info->op_a) || HasFetchInLoop(info->op_b); 500 } 501 return false; 502 } 503 504 bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info, 505 int64_t* stride_value) const { 506 if (info != nullptr) { 507 if (info->induction_class == HInductionVarAnalysis::kLinear) { 508 return IsConstant(info->op_a, kExact, stride_value); 509 } else if (info->induction_class == HInductionVarAnalysis::kPolynomial) { 510 return NeedsTripCount(info->op_a, stride_value); 511 } else if (info->induction_class == HInductionVarAnalysis::kWrapAround) { 512 return NeedsTripCount(info->op_b, stride_value); 513 } 514 } 515 return false; 516 } 517 518 bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const { 519 if (trip != nullptr) { 520 if (trip->induction_class == HInductionVarAnalysis::kInvariant) { 521 return trip->operation == HInductionVarAnalysis::kTripCountInBody || 522 trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe; 523 } 524 } 525 return false; 526 } 527 528 bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const { 529 if (trip != nullptr) { 530 if (trip->induction_class == HInductionVarAnalysis::kInvariant) { 531 return trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe || 532 trip->operation == HInductionVarAnalysis::kTripCountInLoopUnsafe; 533 } 534 } 535 return false; 536 } 537 538 InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::InductionInfo* info, 539 HInductionVarAnalysis::InductionInfo* trip, 540 bool in_body, 541 bool is_min) const { 542 DCHECK(info != nullptr); 543 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kLinear); 544 // Detect common situation where an offset inside the trip-count cancels out during range 545 // analysis (finding max a * (TC - 1) + OFFSET for a == 1 and TC = UPPER - OFFSET or finding 546 // min a * (TC - 1) + OFFSET for a == -1 and TC = OFFSET - UPPER) to avoid losing information 547 // with intermediate results that only incorporate single instructions. 548 if (trip != nullptr) { 549 HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a; 550 if (trip_expr->type == info->type && trip_expr->operation == HInductionVarAnalysis::kSub) { 551 int64_t stride_value = 0; 552 if (IsConstant(info->op_a, kExact, &stride_value)) { 553 if (!is_min && stride_value == 1) { 554 // Test original trip's negative operand (trip_expr->op_b) against offset of induction. 555 if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) { 556 // Analyze cancelled trip with just the positive operand (trip_expr->op_a). 557 HInductionVarAnalysis::InductionInfo cancelled_trip( 558 trip->induction_class, 559 trip->operation, 560 trip_expr->op_a, 561 trip->op_b, 562 nullptr, 563 trip->type); 564 return GetVal(&cancelled_trip, trip, in_body, is_min); 565 } 566 } else if (is_min && stride_value == -1) { 567 // Test original trip's positive operand (trip_expr->op_a) against offset of induction. 568 if (HInductionVarAnalysis::InductionEqual(trip_expr->op_a, info->op_b)) { 569 // Analyze cancelled trip with just the negative operand (trip_expr->op_b). 570 HInductionVarAnalysis::InductionInfo neg( 571 HInductionVarAnalysis::kInvariant, 572 HInductionVarAnalysis::kNeg, 573 nullptr, 574 trip_expr->op_b, 575 nullptr, 576 trip->type); 577 HInductionVarAnalysis::InductionInfo cancelled_trip( 578 trip->induction_class, trip->operation, &neg, trip->op_b, nullptr, trip->type); 579 return SubValue(Value(0), GetVal(&cancelled_trip, trip, in_body, !is_min)); 580 } 581 } 582 } 583 } 584 } 585 // General rule of linear induction a * i + b, for normalized 0 <= i < TC. 586 return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min), 587 GetVal(info->op_b, trip, in_body, is_min)); 588 } 589 590 InductionVarRange::Value InductionVarRange::GetPolynomial(HInductionVarAnalysis::InductionInfo* info, 591 HInductionVarAnalysis::InductionInfo* trip, 592 bool in_body, 593 bool is_min) const { 594 DCHECK(info != nullptr); 595 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial); 596 int64_t a = 0; 597 int64_t b = 0; 598 if (IsConstant(info->op_a->op_a, kExact, &a) && CanLongValueFitIntoInt(a) && a >= 0 && 599 IsConstant(info->op_a->op_b, kExact, &b) && CanLongValueFitIntoInt(b) && b >= 0) { 600 // Evaluate bounds on sum_i=0^m-1(a * i + b) + c with a,b >= 0 for 601 // maximum index value m as a * (m * (m-1)) / 2 + b * m + c. 602 Value c = GetVal(info->op_b, trip, in_body, is_min); 603 if (is_min) { 604 return c; 605 } else { 606 Value m = GetVal(trip, trip, in_body, is_min); 607 Value t = DivValue(MulValue(m, SubValue(m, Value(1))), Value(2)); 608 Value x = MulValue(Value(a), t); 609 Value y = MulValue(Value(b), m); 610 return AddValue(AddValue(x, y), c); 611 } 612 } 613 return Value(); 614 } 615 616 InductionVarRange::Value InductionVarRange::GetGeometric(HInductionVarAnalysis::InductionInfo* info, 617 HInductionVarAnalysis::InductionInfo* trip, 618 bool in_body, 619 bool is_min) const { 620 DCHECK(info != nullptr); 621 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric); 622 int64_t a = 0; 623 int64_t f = 0; 624 if (IsConstant(info->op_a, kExact, &a) && 625 CanLongValueFitIntoInt(a) && 626 IsInt64AndGet(info->fetch, &f) && f >= 1) { 627 // Conservative bounds on a * f^-i + b with f >= 1 can be computed without 628 // trip count. Other forms would require a much more elaborate evaluation. 629 const bool is_min_a = a >= 0 ? is_min : !is_min; 630 if (info->operation == HInductionVarAnalysis::kDiv) { 631 Value b = GetVal(info->op_b, trip, in_body, is_min); 632 return is_min_a ? b : AddValue(Value(a), b); 633 } 634 } 635 return Value(); 636 } 637 638 InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, 639 HInductionVarAnalysis::InductionInfo* trip, 640 bool in_body, 641 bool is_min) const { 642 // Special case when chasing constants: single instruction that denotes trip count in the 643 // loop-body is minimal 1 and maximal, with safe trip-count, max int, 644 if (chase_hint_ == nullptr && in_body && trip != nullptr && instruction == trip->op_a->fetch) { 645 if (is_min) { 646 return Value(1); 647 } else if (!instruction->IsConstant() && !IsUnsafeTripCount(trip)) { 648 return Value(std::numeric_limits<int32_t>::max()); 649 } 650 } 651 // Unless at a constant or hint, chase the instruction a bit deeper into the HIR tree, so that 652 // it becomes more likely range analysis will compare the same instructions as terminal nodes. 653 int64_t value; 654 if (IsInt64AndGet(instruction, &value) && CanLongValueFitIntoInt(value)) { 655 // Proper constant reveals best information. 656 return Value(static_cast<int32_t>(value)); 657 } else if (instruction == chase_hint_) { 658 // At hint, fetch is represented by itself. 659 return Value(instruction, 1, 0); 660 } else if (instruction->IsAdd()) { 661 // Incorporate suitable constants in the chased value. 662 if (IsInt64AndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) { 663 return AddValue(Value(static_cast<int32_t>(value)), 664 GetFetch(instruction->InputAt(1), trip, in_body, is_min)); 665 } else if (IsInt64AndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) { 666 return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), 667 Value(static_cast<int32_t>(value))); 668 } 669 } else if (instruction->IsArrayLength()) { 670 // Exploit length properties when chasing constants or chase into a new array declaration. 671 if (chase_hint_ == nullptr) { 672 return is_min ? Value(0) : Value(std::numeric_limits<int32_t>::max()); 673 } else if (instruction->InputAt(0)->IsNewArray()) { 674 return GetFetch(instruction->InputAt(0)->AsNewArray()->GetLength(), trip, in_body, is_min); 675 } 676 } else if (instruction->IsTypeConversion()) { 677 // Since analysis is 32-bit (or narrower), chase beyond widening along the path. 678 // For example, this discovers the length in: for (long i = 0; i < a.length; i++); 679 if (instruction->AsTypeConversion()->GetInputType() == Primitive::kPrimInt && 680 instruction->AsTypeConversion()->GetResultType() == Primitive::kPrimLong) { 681 return GetFetch(instruction->InputAt(0), trip, in_body, is_min); 682 } 683 } 684 // Chase an invariant fetch that is defined by an outer loop if the trip-count used 685 // so far is well-behaved in both bounds and the next trip-count is safe. 686 // Example: 687 // for (int i = 0; i <= 100; i++) // safe 688 // for (int j = 0; j <= i; j++) // well-behaved 689 // j is in range [0, i ] (if i is chase hint) 690 // or in range [0, 100] (otherwise) 691 HLoopInformation* next_loop = nullptr; 692 HInductionVarAnalysis::InductionInfo* next_info = nullptr; 693 HInductionVarAnalysis::InductionInfo* next_trip = nullptr; 694 bool next_in_body = true; // inner loop is always in body of outer loop 695 if (HasInductionInfo(instruction, instruction, &next_loop, &next_info, &next_trip) && 696 IsWellBehavedTripCount(trip) && 697 !IsUnsafeTripCount(next_trip)) { 698 return GetVal(next_info, next_trip, next_in_body, is_min); 699 } 700 // Fetch is represented by itself. 701 return Value(instruction, 1, 0); 702 } 703 704 InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info, 705 HInductionVarAnalysis::InductionInfo* trip, 706 bool in_body, 707 bool is_min) const { 708 if (info != nullptr) { 709 switch (info->induction_class) { 710 case HInductionVarAnalysis::kInvariant: 711 // Invariants. 712 switch (info->operation) { 713 case HInductionVarAnalysis::kAdd: 714 return AddValue(GetVal(info->op_a, trip, in_body, is_min), 715 GetVal(info->op_b, trip, in_body, is_min)); 716 case HInductionVarAnalysis::kSub: // second reversed! 717 return SubValue(GetVal(info->op_a, trip, in_body, is_min), 718 GetVal(info->op_b, trip, in_body, !is_min)); 719 case HInductionVarAnalysis::kNeg: // second reversed! 720 return SubValue(Value(0), 721 GetVal(info->op_b, trip, in_body, !is_min)); 722 case HInductionVarAnalysis::kMul: 723 return GetMul(info->op_a, info->op_b, trip, in_body, is_min); 724 case HInductionVarAnalysis::kDiv: 725 return GetDiv(info->op_a, info->op_b, trip, in_body, is_min); 726 case HInductionVarAnalysis::kRem: 727 return GetRem(info->op_a, info->op_b); 728 case HInductionVarAnalysis::kXor: 729 return GetXor(info->op_a, info->op_b); 730 case HInductionVarAnalysis::kFetch: 731 return GetFetch(info->fetch, trip, in_body, is_min); 732 case HInductionVarAnalysis::kTripCountInLoop: 733 case HInductionVarAnalysis::kTripCountInLoopUnsafe: 734 if (!in_body && !is_min) { // one extra! 735 return GetVal(info->op_a, trip, in_body, is_min); 736 } 737 FALLTHROUGH_INTENDED; 738 case HInductionVarAnalysis::kTripCountInBody: 739 case HInductionVarAnalysis::kTripCountInBodyUnsafe: 740 if (is_min) { 741 return Value(0); 742 } else if (in_body) { 743 return SubValue(GetVal(info->op_a, trip, in_body, is_min), Value(1)); 744 } 745 break; 746 default: 747 break; 748 } 749 break; 750 case HInductionVarAnalysis::kLinear: 751 return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type); 752 case HInductionVarAnalysis::kPolynomial: 753 return GetPolynomial(info, trip, in_body, is_min); 754 case HInductionVarAnalysis::kGeometric: 755 return GetGeometric(info, trip, in_body, is_min); 756 case HInductionVarAnalysis::kWrapAround: 757 case HInductionVarAnalysis::kPeriodic: 758 return MergeVal(GetVal(info->op_a, trip, in_body, is_min), 759 GetVal(info->op_b, trip, in_body, is_min), is_min); 760 } 761 } 762 return Value(); 763 } 764 765 InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1, 766 HInductionVarAnalysis::InductionInfo* info2, 767 HInductionVarAnalysis::InductionInfo* trip, 768 bool in_body, 769 bool is_min) const { 770 // Constant times range. 771 int64_t value = 0; 772 if (IsConstant(info1, kExact, &value)) { 773 return MulRangeAndConstant(value, info2, trip, in_body, is_min); 774 } else if (IsConstant(info2, kExact, &value)) { 775 return MulRangeAndConstant(value, info1, trip, in_body, is_min); 776 } 777 // Interval ranges. 778 Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true); 779 Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false); 780 Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true); 781 Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false); 782 // Positive range vs. positive or negative range. 783 if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { 784 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 785 return is_min ? MulValue(v1_min, v2_min) : MulValue(v1_max, v2_max); 786 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 787 return is_min ? MulValue(v1_max, v2_min) : MulValue(v1_min, v2_max); 788 } 789 } 790 // Negative range vs. positive or negative range. 791 if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) { 792 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 793 return is_min ? MulValue(v1_min, v2_max) : MulValue(v1_max, v2_min); 794 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 795 return is_min ? MulValue(v1_max, v2_max) : MulValue(v1_min, v2_min); 796 } 797 } 798 return Value(); 799 } 800 801 InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1, 802 HInductionVarAnalysis::InductionInfo* info2, 803 HInductionVarAnalysis::InductionInfo* trip, 804 bool in_body, 805 bool is_min) const { 806 // Range divided by constant. 807 int64_t value = 0; 808 if (IsConstant(info2, kExact, &value)) { 809 return DivRangeAndConstant(value, info1, trip, in_body, is_min); 810 } 811 // Interval ranges. 812 Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true); 813 Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false); 814 Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true); 815 Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false); 816 // Positive range vs. positive or negative range. 817 if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { 818 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 819 return is_min ? DivValue(v1_min, v2_max) : DivValue(v1_max, v2_min); 820 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 821 return is_min ? DivValue(v1_max, v2_max) : DivValue(v1_min, v2_min); 822 } 823 } 824 // Negative range vs. positive or negative range. 825 if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) { 826 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { 827 return is_min ? DivValue(v1_min, v2_min) : DivValue(v1_max, v2_max); 828 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { 829 return is_min ? DivValue(v1_max, v2_min) : DivValue(v1_min, v2_max); 830 } 831 } 832 return Value(); 833 } 834 835 InductionVarRange::Value InductionVarRange::GetRem( 836 HInductionVarAnalysis::InductionInfo* info1, 837 HInductionVarAnalysis::InductionInfo* info2) const { 838 int64_t v1 = 0; 839 int64_t v2 = 0; 840 // Only accept exact values. 841 if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2) && v2 != 0) { 842 int64_t value = v1 % v2; 843 if (CanLongValueFitIntoInt(value)) { 844 return Value(static_cast<int32_t>(value)); 845 } 846 } 847 return Value(); 848 } 849 850 InductionVarRange::Value InductionVarRange::GetXor( 851 HInductionVarAnalysis::InductionInfo* info1, 852 HInductionVarAnalysis::InductionInfo* info2) const { 853 int64_t v1 = 0; 854 int64_t v2 = 0; 855 // Only accept exact values. 856 if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2)) { 857 int64_t value = v1 ^ v2; 858 if (CanLongValueFitIntoInt(value)) { 859 return Value(static_cast<int32_t>(value)); 860 } 861 } 862 return Value(); 863 } 864 865 InductionVarRange::Value InductionVarRange::MulRangeAndConstant( 866 int64_t value, 867 HInductionVarAnalysis::InductionInfo* info, 868 HInductionVarAnalysis::InductionInfo* trip, 869 bool in_body, 870 bool is_min) const { 871 if (CanLongValueFitIntoInt(value)) { 872 Value c(static_cast<int32_t>(value)); 873 return MulValue(GetVal(info, trip, in_body, is_min == value >= 0), c); 874 } 875 return Value(); 876 } 877 878 InductionVarRange::Value InductionVarRange::DivRangeAndConstant( 879 int64_t value, 880 HInductionVarAnalysis::InductionInfo* info, 881 HInductionVarAnalysis::InductionInfo* trip, 882 bool in_body, 883 bool is_min) const { 884 if (CanLongValueFitIntoInt(value)) { 885 Value c(static_cast<int32_t>(value)); 886 return DivValue(GetVal(info, trip, in_body, is_min == value >= 0), c); 887 } 888 return Value(); 889 } 890 891 InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const { 892 if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) { 893 int32_t b = v1.b_constant + v2.b_constant; 894 if (v1.a_constant == 0) { 895 return Value(v2.instruction, v2.a_constant, b); 896 } else if (v2.a_constant == 0) { 897 return Value(v1.instruction, v1.a_constant, b); 898 } else if (v1.instruction == v2.instruction && IsSafeAdd(v1.a_constant, v2.a_constant)) { 899 return Value(v1.instruction, v1.a_constant + v2.a_constant, b); 900 } 901 } 902 return Value(); 903 } 904 905 InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) const { 906 if (v1.is_known && v2.is_known && IsSafeSub(v1.b_constant, v2.b_constant)) { 907 int32_t b = v1.b_constant - v2.b_constant; 908 if (v1.a_constant == 0 && IsSafeSub(0, v2.a_constant)) { 909 return Value(v2.instruction, -v2.a_constant, b); 910 } else if (v2.a_constant == 0) { 911 return Value(v1.instruction, v1.a_constant, b); 912 } else if (v1.instruction == v2.instruction && IsSafeSub(v1.a_constant, v2.a_constant)) { 913 return Value(v1.instruction, v1.a_constant - v2.a_constant, b); 914 } 915 } 916 return Value(); 917 } 918 919 InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) const { 920 if (v1.is_known && v2.is_known) { 921 if (v1.a_constant == 0) { 922 if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) { 923 return Value(v2.instruction, v1.b_constant * v2.a_constant, v1.b_constant * v2.b_constant); 924 } 925 } else if (v2.a_constant == 0) { 926 if (IsSafeMul(v1.a_constant, v2.b_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) { 927 return Value(v1.instruction, v1.a_constant * v2.b_constant, v1.b_constant * v2.b_constant); 928 } 929 } 930 } 931 return Value(); 932 } 933 934 InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) const { 935 if (v1.is_known && v2.is_known && v1.a_constant == 0 && v2.a_constant == 0) { 936 if (IsSafeDiv(v1.b_constant, v2.b_constant)) { 937 return Value(v1.b_constant / v2.b_constant); 938 } 939 } 940 return Value(); 941 } 942 943 InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is_min) const { 944 if (v1.is_known && v2.is_known) { 945 if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) { 946 return Value(v1.instruction, v1.a_constant, 947 is_min ? std::min(v1.b_constant, v2.b_constant) 948 : std::max(v1.b_constant, v2.b_constant)); 949 } 950 } 951 return Value(); 952 } 953 954 bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, 955 HInstruction* instruction, 956 bool is_last_value, 957 HGraph* graph, 958 HBasicBlock* block, 959 /*out*/HInstruction** lower, 960 /*out*/HInstruction** upper, 961 /*out*/HInstruction** taken_test, 962 /*out*/int64_t* stride_value, 963 /*out*/bool* needs_finite_test, 964 /*out*/bool* needs_taken_test) const { 965 HLoopInformation* loop = nullptr; 966 HInductionVarAnalysis::InductionInfo* info = nullptr; 967 HInductionVarAnalysis::InductionInfo* trip = nullptr; 968 if (!HasInductionInfo(context, instruction, &loop, &info, &trip) || trip == nullptr) { 969 return false; // codegen needs all information, including tripcount 970 } 971 // Determine what tests are needed. A finite test is needed if the evaluation code uses the 972 // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot" 973 // the computed range). A taken test is needed for any unknown trip-count, even if evaluation 974 // code does not use the trip-count explicitly (since there could be an implicit relation 975 // between e.g. an invariant subscript and a not-taken condition). 976 bool in_body = context->GetBlock() != loop->GetHeader(); 977 *stride_value = 0; 978 *needs_finite_test = NeedsTripCount(info, stride_value) && IsUnsafeTripCount(trip); 979 *needs_taken_test = IsBodyTripCount(trip); 980 // Handle last value request. 981 if (is_last_value) { 982 DCHECK(!in_body); 983 switch (info->induction_class) { 984 case HInductionVarAnalysis::kLinear: 985 if (*stride_value > 0) { 986 lower = nullptr; 987 } else { 988 upper = nullptr; 989 } 990 break; 991 case HInductionVarAnalysis::kPolynomial: 992 return GenerateLastValuePolynomial(info, trip, graph, block, lower); 993 case HInductionVarAnalysis::kGeometric: 994 return GenerateLastValueGeometric(info, trip, graph, block, lower); 995 case HInductionVarAnalysis::kWrapAround: 996 return GenerateLastValueWrapAround(info, trip, graph, block, lower); 997 case HInductionVarAnalysis::kPeriodic: 998 return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test); 999 default: 1000 return false; 1001 } 1002 } 1003 // Code generation for taken test: generate the code when requested or otherwise analyze 1004 // if code generation is feasible when taken test is needed. 1005 if (taken_test != nullptr) { 1006 return GenerateCode(trip->op_b, nullptr, graph, block, taken_test, in_body, /* is_min */ false); 1007 } else if (*needs_taken_test) { 1008 if (!GenerateCode( 1009 trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min */ false)) { 1010 return false; 1011 } 1012 } 1013 // Code generation for lower and upper. 1014 return 1015 // Success on lower if invariant (not set), or code can be generated. 1016 ((info->induction_class == HInductionVarAnalysis::kInvariant) || 1017 GenerateCode(info, trip, graph, block, lower, in_body, /* is_min */ true)) && 1018 // And success on upper. 1019 GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ false); 1020 } 1021 1022 bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::InductionInfo* info, 1023 HInductionVarAnalysis::InductionInfo* trip, 1024 HGraph* graph, 1025 HBasicBlock* block, 1026 /*out*/HInstruction** result) const { 1027 DCHECK(info != nullptr); 1028 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial); 1029 // Detect known coefficients and trip count (always taken). 1030 int64_t a = 0; 1031 int64_t b = 0; 1032 int64_t m = 0; 1033 if (IsConstant(info->op_a->op_a, kExact, &a) && 1034 IsConstant(info->op_a->op_b, kExact, &b) && 1035 IsConstant(trip->op_a, kExact, &m) && m >= 1) { 1036 // Evaluate bounds on sum_i=0^m-1(a * i + b) + c for known 1037 // maximum index value m as a * (m * (m-1)) / 2 + b * m + c. 1038 HInstruction* c = nullptr; 1039 if (GenerateCode(info->op_b, nullptr, graph, block, graph ? &c : nullptr, false, false)) { 1040 if (graph != nullptr) { 1041 Primitive::Type type = info->type; 1042 int64_t sum = a * ((m * (m - 1)) / 2) + b * m; 1043 if (type != Primitive::kPrimLong) { 1044 sum = static_cast<int32_t>(sum); // okay to truncate 1045 } 1046 *result = 1047 Insert(block, new (graph->GetArena()) HAdd(type, graph->GetConstant(type, sum), c)); 1048 } 1049 return true; 1050 } 1051 } 1052 return false; 1053 } 1054 1055 bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::InductionInfo* info, 1056 HInductionVarAnalysis::InductionInfo* trip, 1057 HGraph* graph, 1058 HBasicBlock* block, 1059 /*out*/HInstruction** result) const { 1060 DCHECK(info != nullptr); 1061 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric); 1062 // Detect known base and trip count (always taken). 1063 int64_t f = 0; 1064 int64_t m = 0; 1065 if (IsInt64AndGet(info->fetch, &f) && f >= 1 && IsConstant(trip->op_a, kExact, &m) && m >= 1) { 1066 HInstruction* opa = nullptr; 1067 HInstruction* opb = nullptr; 1068 if (GenerateCode(info->op_a, nullptr, graph, block, &opa, false, false) && 1069 GenerateCode(info->op_b, nullptr, graph, block, &opb, false, false)) { 1070 if (graph != nullptr) { 1071 Primitive::Type type = info->type; 1072 // Compute f ^ m for known maximum index value m. 1073 bool overflow = false; 1074 int64_t fpow = IntPow(f, m, &overflow); 1075 if (info->operation == HInductionVarAnalysis::kDiv) { 1076 // For division, any overflow truncates to zero. 1077 if (overflow || (type != Primitive::kPrimLong && !CanLongValueFitIntoInt(fpow))) { 1078 fpow = 0; 1079 } 1080 } else if (type != Primitive::kPrimLong) { 1081 // For multiplication, okay to truncate to required precision. 1082 DCHECK(info->operation == HInductionVarAnalysis::kMul); 1083 fpow = static_cast<int32_t>(fpow); 1084 } 1085 // Generate code. 1086 if (fpow == 0) { 1087 // Special case: repeated mul/div always yields zero. 1088 *result = graph->GetConstant(type, 0); 1089 } else { 1090 // Last value: a * f ^ m + b or a * f ^ -m + b. 1091 HInstruction* e = nullptr; 1092 if (info->operation == HInductionVarAnalysis::kMul) { 1093 e = new (graph->GetArena()) HMul(type, opa, graph->GetConstant(type, fpow)); 1094 } else { 1095 e = new (graph->GetArena()) HDiv(type, opa, graph->GetConstant(type, fpow), kNoDexPc); 1096 } 1097 *result = Insert(block, new (graph->GetArena()) HAdd(type, Insert(block, e), opb)); 1098 } 1099 } 1100 return true; 1101 } 1102 } 1103 return false; 1104 } 1105 1106 bool InductionVarRange::GenerateLastValueWrapAround(HInductionVarAnalysis::InductionInfo* info, 1107 HInductionVarAnalysis::InductionInfo* trip, 1108 HGraph* graph, 1109 HBasicBlock* block, 1110 /*out*/HInstruction** result) const { 1111 DCHECK(info != nullptr); 1112 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kWrapAround); 1113 // Count depth. 1114 int32_t depth = 0; 1115 for (; info->induction_class == HInductionVarAnalysis::kWrapAround; 1116 info = info->op_b, ++depth) {} 1117 // Handle wrap(x, wrap(.., y)) if trip count reaches an invariant at end. 1118 // TODO: generalize, but be careful to adjust the terminal. 1119 int64_t m = 0; 1120 if (info->induction_class == HInductionVarAnalysis::kInvariant && 1121 IsConstant(trip->op_a, kExact, &m) && m >= depth) { 1122 return GenerateCode(info, nullptr, graph, block, result, false, false); 1123 } 1124 return false; 1125 } 1126 1127 bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info, 1128 HInductionVarAnalysis::InductionInfo* trip, 1129 HGraph* graph, 1130 HBasicBlock* block, 1131 /*out*/HInstruction** result, 1132 /*out*/bool* needs_taken_test) const { 1133 DCHECK(info != nullptr); 1134 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPeriodic); 1135 // Count period and detect all-invariants. 1136 int64_t period = 1; 1137 bool all_invariants = true; 1138 HInductionVarAnalysis::InductionInfo* p = info; 1139 for (; p->induction_class == HInductionVarAnalysis::kPeriodic; p = p->op_b, ++period) { 1140 DCHECK_EQ(p->op_a->induction_class, HInductionVarAnalysis::kInvariant); 1141 if (p->op_a->operation != HInductionVarAnalysis::kFetch) { 1142 all_invariants = false; 1143 } 1144 } 1145 DCHECK_EQ(p->induction_class, HInductionVarAnalysis::kInvariant); 1146 if (p->operation != HInductionVarAnalysis::kFetch) { 1147 all_invariants = false; 1148 } 1149 // Don't rely on FP arithmetic to be precise, unless the full period 1150 // consist of pre-computed expressions only. 1151 if (info->type == Primitive::kPrimFloat || info->type == Primitive::kPrimDouble) { 1152 if (!all_invariants) { 1153 return false; 1154 } 1155 } 1156 // Handle any periodic(x, periodic(.., y)) for known maximum index value m. 1157 int64_t m = 0; 1158 if (IsConstant(trip->op_a, kExact, &m) && m >= 1) { 1159 int64_t li = m % period; 1160 for (int64_t i = 0; i < li; info = info->op_b, i++) {} 1161 if (info->induction_class == HInductionVarAnalysis::kPeriodic) { 1162 info = info->op_a; 1163 } 1164 return GenerateCode(info, nullptr, graph, block, result, false, false); 1165 } 1166 // Handle periodic(x, y) using even/odd-select on trip count. Enter trip count expression 1167 // directly to obtain the maximum index value t even if taken test is needed. 1168 HInstruction* x = nullptr; 1169 HInstruction* y = nullptr; 1170 HInstruction* t = nullptr; 1171 if (period == 2 && 1172 GenerateCode(info->op_a, nullptr, graph, block, graph ? &x : nullptr, false, false) && 1173 GenerateCode(info->op_b, nullptr, graph, block, graph ? &y : nullptr, false, false) && 1174 GenerateCode(trip->op_a, nullptr, graph, block, graph ? &t : nullptr, false, false)) { 1175 // During actual code generation (graph != nullptr), generate is_even ? x : y. 1176 if (graph != nullptr) { 1177 Primitive::Type type = trip->type; 1178 HInstruction* msk = 1179 Insert(block, new (graph->GetArena()) HAnd(type, t, graph->GetConstant(type, 1))); 1180 HInstruction* is_even = 1181 Insert(block, new (graph->GetArena()) HEqual(msk, graph->GetConstant(type, 0), kNoDexPc)); 1182 *result = Insert(block, new (graph->GetArena()) HSelect(is_even, x, y, kNoDexPc)); 1183 } 1184 // Guard select with taken test if needed. 1185 if (*needs_taken_test) { 1186 HInstruction* is_taken = nullptr; 1187 if (GenerateCode(trip->op_b, nullptr, graph, block, graph ? &is_taken : nullptr, false, false)) { 1188 if (graph != nullptr) { 1189 *result = Insert(block, new (graph->GetArena()) HSelect(is_taken, *result, x, kNoDexPc)); 1190 } 1191 *needs_taken_test = false; // taken care of 1192 } else { 1193 return false; 1194 } 1195 } 1196 return true; 1197 } 1198 return false; 1199 } 1200 1201 bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, 1202 HInductionVarAnalysis::InductionInfo* trip, 1203 HGraph* graph, // when set, code is generated 1204 HBasicBlock* block, 1205 /*out*/HInstruction** result, 1206 bool in_body, 1207 bool is_min) const { 1208 if (info != nullptr) { 1209 // If during codegen, the result is not needed (nullptr), simply return success. 1210 if (graph != nullptr && result == nullptr) { 1211 return true; 1212 } 1213 // Handle current operation. 1214 Primitive::Type type = info->type; 1215 HInstruction* opa = nullptr; 1216 HInstruction* opb = nullptr; 1217 switch (info->induction_class) { 1218 case HInductionVarAnalysis::kInvariant: 1219 // Invariants (note that since invariants only have other invariants as 1220 // sub expressions, viz. no induction, there is no need to adjust is_min). 1221 switch (info->operation) { 1222 case HInductionVarAnalysis::kAdd: 1223 case HInductionVarAnalysis::kSub: 1224 case HInductionVarAnalysis::kMul: 1225 case HInductionVarAnalysis::kDiv: 1226 case HInductionVarAnalysis::kRem: 1227 case HInductionVarAnalysis::kXor: 1228 case HInductionVarAnalysis::kLT: 1229 case HInductionVarAnalysis::kLE: 1230 case HInductionVarAnalysis::kGT: 1231 case HInductionVarAnalysis::kGE: 1232 if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) && 1233 GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) { 1234 if (graph != nullptr) { 1235 HInstruction* operation = nullptr; 1236 switch (info->operation) { 1237 case HInductionVarAnalysis::kAdd: 1238 operation = new (graph->GetArena()) HAdd(type, opa, opb); break; 1239 case HInductionVarAnalysis::kSub: 1240 operation = new (graph->GetArena()) HSub(type, opa, opb); break; 1241 case HInductionVarAnalysis::kMul: 1242 operation = new (graph->GetArena()) HMul(type, opa, opb, kNoDexPc); break; 1243 case HInductionVarAnalysis::kDiv: 1244 operation = new (graph->GetArena()) HDiv(type, opa, opb, kNoDexPc); break; 1245 case HInductionVarAnalysis::kRem: 1246 operation = new (graph->GetArena()) HRem(type, opa, opb, kNoDexPc); break; 1247 case HInductionVarAnalysis::kXor: 1248 operation = new (graph->GetArena()) HXor(type, opa, opb); break; 1249 case HInductionVarAnalysis::kLT: 1250 operation = new (graph->GetArena()) HLessThan(opa, opb); break; 1251 case HInductionVarAnalysis::kLE: 1252 operation = new (graph->GetArena()) HLessThanOrEqual(opa, opb); break; 1253 case HInductionVarAnalysis::kGT: 1254 operation = new (graph->GetArena()) HGreaterThan(opa, opb); break; 1255 case HInductionVarAnalysis::kGE: 1256 operation = new (graph->GetArena()) HGreaterThanOrEqual(opa, opb); break; 1257 default: 1258 LOG(FATAL) << "unknown operation"; 1259 } 1260 *result = Insert(block, operation); 1261 } 1262 return true; 1263 } 1264 break; 1265 case HInductionVarAnalysis::kNeg: 1266 if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) { 1267 if (graph != nullptr) { 1268 *result = Insert(block, new (graph->GetArena()) HNeg(type, opb)); 1269 } 1270 return true; 1271 } 1272 break; 1273 case HInductionVarAnalysis::kFetch: 1274 if (graph != nullptr) { 1275 *result = info->fetch; // already in HIR 1276 } 1277 return true; 1278 case HInductionVarAnalysis::kTripCountInLoop: 1279 case HInductionVarAnalysis::kTripCountInLoopUnsafe: 1280 if (!in_body && !is_min) { // one extra! 1281 return GenerateCode(info->op_a, trip, graph, block, result, in_body, is_min); 1282 } 1283 FALLTHROUGH_INTENDED; 1284 case HInductionVarAnalysis::kTripCountInBody: 1285 case HInductionVarAnalysis::kTripCountInBodyUnsafe: 1286 if (is_min) { 1287 if (graph != nullptr) { 1288 *result = graph->GetConstant(type, 0); 1289 } 1290 return true; 1291 } else if (in_body) { 1292 if (GenerateCode(info->op_a, trip, graph, block, &opb, in_body, is_min)) { 1293 if (graph != nullptr) { 1294 *result = 1295 Insert(block, 1296 new (graph->GetArena()) HSub(type, opb, graph->GetConstant(type, 1))); 1297 } 1298 return true; 1299 } 1300 } 1301 break; 1302 case HInductionVarAnalysis::kNop: 1303 LOG(FATAL) << "unexpected invariant nop"; 1304 } // switch invariant operation 1305 break; 1306 case HInductionVarAnalysis::kLinear: { 1307 // Linear induction a * i + b, for normalized 0 <= i < TC. For ranges, this should 1308 // be restricted to a unit stride to avoid arithmetic wrap-around situations that 1309 // are harder to guard against. For a last value, requesting min/max based on any 1310 // known stride yields right value. Always avoid any narrowing linear induction or 1311 // any type mismatch between the linear induction and the trip count expression. 1312 // TODO: careful runtime type conversions could generalize this latter restriction. 1313 if (!HInductionVarAnalysis::IsNarrowingLinear(info) && trip->type == type) { 1314 int64_t stride_value = 0; 1315 if (IsConstant(info->op_a, kExact, &stride_value) && 1316 CanLongValueFitIntoInt(stride_value)) { 1317 const bool is_min_a = stride_value >= 0 ? is_min : !is_min; 1318 if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) && 1319 GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) { 1320 if (graph != nullptr) { 1321 HInstruction* oper; 1322 if (stride_value == 1) { 1323 oper = new (graph->GetArena()) HAdd(type, opa, opb); 1324 } else if (stride_value == -1) { 1325 oper = new (graph->GetArena()) HSub(type, opb, opa); 1326 } else { 1327 HInstruction* mul = 1328 new (graph->GetArena()) HMul(type, graph->GetConstant(type, stride_value), opa); 1329 oper = new (graph->GetArena()) HAdd(type, Insert(block, mul), opb); 1330 } 1331 *result = Insert(block, oper); 1332 } 1333 return true; 1334 } 1335 } 1336 } 1337 break; 1338 } 1339 case HInductionVarAnalysis::kPolynomial: 1340 case HInductionVarAnalysis::kGeometric: 1341 break; 1342 case HInductionVarAnalysis::kWrapAround: 1343 case HInductionVarAnalysis::kPeriodic: { 1344 // Wrap-around and periodic inductions are restricted to constants only, so that extreme 1345 // values are easy to test at runtime without complications of arithmetic wrap-around. 1346 Value extreme = GetVal(info, trip, in_body, is_min); 1347 if (IsConstantValue(extreme)) { 1348 if (graph != nullptr) { 1349 *result = graph->GetConstant(type, extreme.b_constant); 1350 } 1351 return true; 1352 } 1353 break; 1354 } 1355 } // switch induction class 1356 } 1357 return false; 1358 } 1359 1360 void InductionVarRange::ReplaceInduction(HInductionVarAnalysis::InductionInfo* info, 1361 HInstruction* fetch, 1362 HInstruction* replacement) { 1363 if (info != nullptr) { 1364 if (info->induction_class == HInductionVarAnalysis::kInvariant && 1365 info->operation == HInductionVarAnalysis::kFetch && 1366 info->fetch == fetch) { 1367 info->fetch = replacement; 1368 } 1369 ReplaceInduction(info->op_a, fetch, replacement); 1370 ReplaceInduction(info->op_b, fetch, replacement); 1371 } 1372 } 1373 1374 } // namespace art 1375
