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_analysis.h" 18 #include "induction_var_range.h" 19 20 namespace art { 21 22 /** 23 * Since graph traversal may enter a SCC at any position, an initial representation may be rotated, 24 * along dependences, viz. any of (a, b, c, d), (d, a, b, c) (c, d, a, b), (b, c, d, a) assuming 25 * a chain of dependences (mutual independent items may occur in arbitrary order). For proper 26 * classification, the lexicographically first loop-phi is rotated to the front. 27 */ 28 static void RotateEntryPhiFirst(HLoopInformation* loop, 29 ArenaVector<HInstruction*>* scc, 30 ArenaVector<HInstruction*>* new_scc) { 31 // Find very first loop-phi. 32 const HInstructionList& phis = loop->GetHeader()->GetPhis(); 33 HInstruction* phi = nullptr; 34 size_t phi_pos = -1; 35 const size_t size = scc->size(); 36 for (size_t i = 0; i < size; i++) { 37 HInstruction* other = (*scc)[i]; 38 if (other->IsLoopHeaderPhi() && (phi == nullptr || phis.FoundBefore(other, phi))) { 39 phi = other; 40 phi_pos = i; 41 } 42 } 43 44 // If found, bring that loop-phi to front. 45 if (phi != nullptr) { 46 new_scc->clear(); 47 for (size_t i = 0; i < size; i++) { 48 new_scc->push_back((*scc)[phi_pos]); 49 if (++phi_pos >= size) phi_pos = 0; 50 } 51 DCHECK_EQ(size, new_scc->size()); 52 scc->swap(*new_scc); 53 } 54 } 55 56 /** 57 * Returns true if the from/to types denote a narrowing, integral conversion (precision loss). 58 */ 59 static bool IsNarrowingIntegralConversion(Primitive::Type from, Primitive::Type to) { 60 switch (from) { 61 case Primitive::kPrimLong: 62 return to == Primitive::kPrimByte || to == Primitive::kPrimShort 63 || to == Primitive::kPrimChar || to == Primitive::kPrimInt; 64 case Primitive::kPrimInt: 65 return to == Primitive::kPrimByte || to == Primitive::kPrimShort 66 || to == Primitive::kPrimChar; 67 case Primitive::kPrimChar: 68 case Primitive::kPrimShort: 69 return to == Primitive::kPrimByte; 70 default: 71 return false; 72 } 73 } 74 75 /** 76 * Returns result of implicit widening type conversion done in HIR. 77 */ 78 static Primitive::Type ImplicitConversion(Primitive::Type type) { 79 switch (type) { 80 case Primitive::kPrimShort: 81 case Primitive::kPrimChar: 82 case Primitive::kPrimByte: 83 case Primitive::kPrimBoolean: 84 return Primitive::kPrimInt; 85 default: 86 return type; 87 } 88 } 89 90 // 91 // Class methods. 92 // 93 94 HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph) 95 : HOptimization(graph, kInductionPassName), 96 global_depth_(0), 97 stack_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), 98 map_(std::less<HInstruction*>(), 99 graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), 100 scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), 101 cycle_(std::less<HInstruction*>(), 102 graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), 103 type_(Primitive::kPrimVoid), 104 induction_(std::less<HLoopInformation*>(), 105 graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), 106 cycles_(std::less<HPhi*>(), 107 graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)) { 108 } 109 110 void HInductionVarAnalysis::Run() { 111 // Detects sequence variables (generalized induction variables) during an outer to inner 112 // traversal of all loops using Gerlek's algorithm. The order is important to enable 113 // range analysis on outer loop while visiting inner loops. 114 for (HBasicBlock* graph_block : graph_->GetReversePostOrder()) { 115 // Don't analyze irreducible loops. 116 if (graph_block->IsLoopHeader() && !graph_block->GetLoopInformation()->IsIrreducible()) { 117 VisitLoop(graph_block->GetLoopInformation()); 118 } 119 } 120 } 121 122 void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) { 123 // Find strongly connected components (SSCs) in the SSA graph of this loop using Tarjan's 124 // algorithm. Due to the descendant-first nature, classification happens "on-demand". 125 global_depth_ = 0; 126 DCHECK(stack_.empty()); 127 map_.clear(); 128 129 for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) { 130 HBasicBlock* loop_block = it_loop.Current(); 131 DCHECK(loop_block->IsInLoop()); 132 if (loop_block->GetLoopInformation() != loop) { 133 continue; // Inner loops visited later. 134 } 135 // Visit phi-operations and instructions. 136 for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) { 137 HInstruction* instruction = it.Current(); 138 if (!IsVisitedNode(instruction)) { 139 VisitNode(loop, instruction); 140 } 141 } 142 for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) { 143 HInstruction* instruction = it.Current(); 144 if (!IsVisitedNode(instruction)) { 145 VisitNode(loop, instruction); 146 } 147 } 148 } 149 150 DCHECK(stack_.empty()); 151 map_.clear(); 152 153 // Determine the loop's trip-count. 154 VisitControl(loop); 155 } 156 157 void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) { 158 const uint32_t d1 = ++global_depth_; 159 map_.Put(instruction, NodeInfo(d1)); 160 stack_.push_back(instruction); 161 162 // Visit all descendants. 163 uint32_t low = d1; 164 for (HInstruction* input : instruction->GetInputs()) { 165 low = std::min(low, VisitDescendant(loop, input)); 166 } 167 168 // Lower or found SCC? 169 if (low < d1) { 170 map_.find(instruction)->second.depth = low; 171 } else { 172 scc_.clear(); 173 cycle_.clear(); 174 175 // Pop the stack to build the SCC for classification. 176 while (!stack_.empty()) { 177 HInstruction* x = stack_.back(); 178 scc_.push_back(x); 179 stack_.pop_back(); 180 map_.find(x)->second.done = true; 181 if (x == instruction) { 182 break; 183 } 184 } 185 186 // Type of induction. 187 type_ = scc_[0]->GetType(); 188 189 // Classify the SCC. 190 if (scc_.size() == 1 && !scc_[0]->IsLoopHeaderPhi()) { 191 ClassifyTrivial(loop, scc_[0]); 192 } else { 193 ClassifyNonTrivial(loop); 194 } 195 196 scc_.clear(); 197 cycle_.clear(); 198 } 199 } 200 201 uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) { 202 // If the definition is either outside the loop (loop invariant entry value) 203 // or assigned in inner loop (inner exit value), the traversal stops. 204 HLoopInformation* otherLoop = instruction->GetBlock()->GetLoopInformation(); 205 if (otherLoop != loop) { 206 return global_depth_; 207 } 208 209 // Inspect descendant node. 210 if (!IsVisitedNode(instruction)) { 211 VisitNode(loop, instruction); 212 return map_.find(instruction)->second.depth; 213 } else { 214 auto it = map_.find(instruction); 215 return it->second.done ? global_depth_ : it->second.depth; 216 } 217 } 218 219 void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) { 220 InductionInfo* info = nullptr; 221 if (instruction->IsPhi()) { 222 info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 0); 223 } else if (instruction->IsAdd()) { 224 info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)), 225 LookupInfo(loop, instruction->InputAt(1)), kAdd); 226 } else if (instruction->IsSub()) { 227 info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)), 228 LookupInfo(loop, instruction->InputAt(1)), kSub); 229 } else if (instruction->IsNeg()) { 230 info = TransferNeg(LookupInfo(loop, instruction->InputAt(0))); 231 } else if (instruction->IsMul()) { 232 info = TransferMul(LookupInfo(loop, instruction->InputAt(0)), 233 LookupInfo(loop, instruction->InputAt(1))); 234 } else if (instruction->IsShl()) { 235 HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr); 236 if (mulc != nullptr) { 237 info = TransferMul(LookupInfo(loop, instruction->InputAt(0)), 238 LookupInfo(loop, mulc)); 239 } 240 } else if (instruction->IsSelect()) { 241 info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 1); 242 } else if (instruction->IsTypeConversion()) { 243 info = TransferConversion(LookupInfo(loop, instruction->InputAt(0)), 244 instruction->AsTypeConversion()->GetInputType(), 245 instruction->AsTypeConversion()->GetResultType()); 246 } else if (instruction->IsBoundsCheck()) { 247 info = LookupInfo(loop, instruction->InputAt(0)); // Pass-through. 248 } 249 250 // Successfully classified? 251 if (info != nullptr) { 252 AssignInfo(loop, instruction, info); 253 } 254 } 255 256 void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) { 257 const size_t size = scc_.size(); 258 DCHECK_GE(size, 1u); 259 260 // Rotate proper loop-phi to front. 261 if (size > 1) { 262 ArenaVector<HInstruction*> other(graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)); 263 RotateEntryPhiFirst(loop, &scc_, &other); 264 } 265 266 // Analyze from loop-phi onwards. 267 HInstruction* phi = scc_[0]; 268 if (!phi->IsLoopHeaderPhi()) { 269 return; 270 } 271 272 // External link should be loop invariant. 273 InductionInfo* initial = LookupInfo(loop, phi->InputAt(0)); 274 if (initial == nullptr || initial->induction_class != kInvariant) { 275 return; 276 } 277 278 // Store interesting cycle in each loop phi. 279 for (size_t i = 0; i < size; i++) { 280 if (scc_[i]->IsLoopHeaderPhi()) { 281 AssignCycle(scc_[i]->AsPhi()); 282 } 283 } 284 285 // Singleton is wrap-around induction if all internal links have the same meaning. 286 if (size == 1) { 287 InductionInfo* update = TransferPhi(loop, phi, /*input_index*/ 1, /*adjust_input_size*/ 0); 288 if (update != nullptr) { 289 AssignInfo(loop, phi, CreateInduction(kWrapAround, 290 kNop, 291 initial, 292 update, 293 /*fetch*/ nullptr, 294 type_)); 295 } 296 return; 297 } 298 299 // Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns 300 // temporary meaning to its nodes, seeded from the phi instruction and back. 301 for (size_t i = 1; i < size; i++) { 302 HInstruction* instruction = scc_[i]; 303 InductionInfo* update = nullptr; 304 if (instruction->IsPhi()) { 305 update = SolvePhiAllInputs(loop, phi, instruction); 306 } else if (instruction->IsAdd()) { 307 update = SolveAddSub( 308 loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true); 309 } else if (instruction->IsSub()) { 310 update = SolveAddSub( 311 loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true); 312 } else if (instruction->IsMul()) { 313 update = SolveOp( 314 loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kMul); 315 } else if (instruction->IsDiv()) { 316 update = SolveOp( 317 loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kDiv); 318 } else if (instruction->IsRem()) { 319 update = SolveOp( 320 loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kRem); 321 } else if (instruction->IsShl()) { 322 HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr); 323 if (mulc != nullptr) { 324 update = SolveOp(loop, phi, instruction, instruction->InputAt(0), mulc, kMul); 325 } 326 } else if (instruction->IsShr() || instruction->IsUShr()) { 327 HInstruction* divc = GetShiftConstant(loop, instruction, initial); 328 if (divc != nullptr) { 329 update = SolveOp(loop, phi, instruction, instruction->InputAt(0), divc, kDiv); 330 } 331 } else if (instruction->IsXor()) { 332 update = SolveOp( 333 loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kXor); 334 } else if (instruction->IsEqual()) { 335 update = SolveTest(loop, phi, instruction, 0); 336 } else if (instruction->IsNotEqual()) { 337 update = SolveTest(loop, phi, instruction, 1); 338 } else if (instruction->IsSelect()) { 339 update = SolvePhi(instruction, /*input_index*/ 0, /*adjust_input_size*/ 1); // acts like Phi 340 } else if (instruction->IsTypeConversion()) { 341 update = SolveConversion(loop, phi, instruction->AsTypeConversion()); 342 } 343 if (update == nullptr) { 344 return; 345 } 346 cycle_.Put(instruction, update); 347 } 348 349 // Success if all internal links received the same temporary meaning. 350 InductionInfo* induction = SolvePhi(phi, /*input_index*/ 1, /*adjust_input_size*/ 0); 351 if (induction != nullptr) { 352 switch (induction->induction_class) { 353 case kInvariant: 354 // Construct combined stride of the linear induction. 355 induction = CreateInduction(kLinear, kNop, induction, initial, /*fetch*/ nullptr, type_); 356 FALLTHROUGH_INTENDED; 357 case kPolynomial: 358 case kGeometric: 359 case kWrapAround: 360 // Classify first phi and then the rest of the cycle "on-demand". 361 // Statements are scanned in order. 362 AssignInfo(loop, phi, induction); 363 for (size_t i = 1; i < size; i++) { 364 ClassifyTrivial(loop, scc_[i]); 365 } 366 break; 367 case kPeriodic: 368 // Classify all elements in the cycle with the found periodic induction while 369 // rotating each first element to the end. Lastly, phi is classified. 370 // Statements are scanned in reverse order. 371 for (size_t i = size - 1; i >= 1; i--) { 372 AssignInfo(loop, scc_[i], induction); 373 induction = RotatePeriodicInduction(induction->op_b, induction->op_a); 374 } 375 AssignInfo(loop, phi, induction); 376 break; 377 default: 378 break; 379 } 380 } 381 } 382 383 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduction( 384 InductionInfo* induction, 385 InductionInfo* last) { 386 // Rotates a periodic induction of the form 387 // (a, b, c, d, e) 388 // into 389 // (b, c, d, e, a) 390 // in preparation of assigning this to the previous variable in the sequence. 391 if (induction->induction_class == kInvariant) { 392 return CreateInduction(kPeriodic, 393 kNop, 394 induction, 395 last, 396 /*fetch*/ nullptr, 397 type_); 398 } 399 return CreateInduction(kPeriodic, 400 kNop, 401 induction->op_a, 402 RotatePeriodicInduction(induction->op_b, last), 403 /*fetch*/ nullptr, 404 type_); 405 } 406 407 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopInformation* loop, 408 HInstruction* phi, 409 size_t input_index, 410 size_t adjust_input_size) { 411 // Match all phi inputs from input_index onwards exactly. 412 HInputsRef inputs = phi->GetInputs(); 413 DCHECK_LT(input_index, inputs.size()); 414 InductionInfo* a = LookupInfo(loop, inputs[input_index]); 415 for (size_t i = input_index + 1, n = inputs.size() - adjust_input_size; i < n; i++) { 416 InductionInfo* b = LookupInfo(loop, inputs[i]); 417 if (!InductionEqual(a, b)) { 418 return nullptr; 419 } 420 } 421 return a; 422 } 423 424 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a, 425 InductionInfo* b, 426 InductionOp op) { 427 // Transfer over an addition or subtraction: any invariant, linear, polynomial, geometric, 428 // wrap-around, or periodic can be combined with an invariant to yield a similar result. 429 // Two linear or two polynomial inputs can be combined too. Other combinations fail. 430 if (a != nullptr && b != nullptr) { 431 if (IsNarrowingLinear(a) || IsNarrowingLinear(b)) { 432 return nullptr; // no transfer 433 } else if (a->induction_class == kInvariant && b->induction_class == kInvariant) { 434 return CreateInvariantOp(op, a, b); // direct invariant 435 } else if ((a->induction_class == kLinear && b->induction_class == kLinear) || 436 (a->induction_class == kPolynomial && b->induction_class == kPolynomial)) { 437 // Rule induc(a, b) + induc(a', b') -> induc(a + a', b + b'). 438 InductionInfo* new_a = TransferAddSub(a->op_a, b->op_a, op); 439 InductionInfo* new_b = TransferAddSub(a->op_b, b->op_b, op); 440 if (new_a != nullptr && new_b != nullptr) { 441 return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_); 442 } 443 } else if (a->induction_class == kInvariant) { 444 // Rule a + induc(a', b') -> induc(a', a + b') or induc(a + a', a + b'). 445 InductionInfo* new_a = b->op_a; 446 InductionInfo* new_b = TransferAddSub(a, b->op_b, op); 447 if (b->induction_class == kWrapAround || b->induction_class == kPeriodic) { 448 new_a = TransferAddSub(a, new_a, op); 449 } else if (op == kSub) { // Negation required. 450 new_a = TransferNeg(new_a); 451 } 452 if (new_a != nullptr && new_b != nullptr) { 453 return CreateInduction(b->induction_class, b->operation, new_a, new_b, b->fetch, type_); 454 } 455 } else if (b->induction_class == kInvariant) { 456 // Rule induc(a, b) + b' -> induc(a, b + b') or induc(a + b', b + b'). 457 InductionInfo* new_a = a->op_a; 458 InductionInfo* new_b = TransferAddSub(a->op_b, b, op); 459 if (a->induction_class == kWrapAround || a->induction_class == kPeriodic) { 460 new_a = TransferAddSub(new_a, b, op); 461 } 462 if (new_a != nullptr && new_b != nullptr) { 463 return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_); 464 } 465 } 466 } 467 return nullptr; 468 } 469 470 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) { 471 // Transfer over a unary negation: an invariant, linear, polynomial, geometric (mul), 472 // wrap-around, or periodic input yields a similar but negated induction as result. 473 if (a != nullptr) { 474 if (IsNarrowingLinear(a)) { 475 return nullptr; // no transfer 476 } else if (a->induction_class == kInvariant) { 477 return CreateInvariantOp(kNeg, nullptr, a); // direct invariant 478 } else if (a->induction_class != kGeometric || a->operation == kMul) { 479 // Rule - induc(a, b) -> induc(-a, -b). 480 InductionInfo* new_a = TransferNeg(a->op_a); 481 InductionInfo* new_b = TransferNeg(a->op_b); 482 if (new_a != nullptr && new_b != nullptr) { 483 return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_); 484 } 485 } 486 } 487 return nullptr; 488 } 489 490 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a, 491 InductionInfo* b) { 492 // Transfer over a multiplication: any invariant, linear, polynomial, geometric (mul), 493 // wrap-around, or periodic can be multiplied with an invariant to yield a similar 494 // but multiplied result. Two non-invariant inputs cannot be multiplied, however. 495 if (a != nullptr && b != nullptr) { 496 if (IsNarrowingLinear(a) || IsNarrowingLinear(b)) { 497 return nullptr; // no transfer 498 } else if (a->induction_class == kInvariant && b->induction_class == kInvariant) { 499 return CreateInvariantOp(kMul, a, b); // direct invariant 500 } else if (a->induction_class == kInvariant && (b->induction_class != kGeometric || 501 b->operation == kMul)) { 502 // Rule a * induc(a', b') -> induc(a * a', b * b'). 503 InductionInfo* new_a = TransferMul(a, b->op_a); 504 InductionInfo* new_b = TransferMul(a, b->op_b); 505 if (new_a != nullptr && new_b != nullptr) { 506 return CreateInduction(b->induction_class, b->operation, new_a, new_b, b->fetch, type_); 507 } 508 } else if (b->induction_class == kInvariant && (a->induction_class != kGeometric || 509 a->operation == kMul)) { 510 // Rule induc(a, b) * b' -> induc(a * b', b * b'). 511 InductionInfo* new_a = TransferMul(a->op_a, b); 512 InductionInfo* new_b = TransferMul(a->op_b, b); 513 if (new_a != nullptr && new_b != nullptr) { 514 return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_); 515 } 516 } 517 } 518 return nullptr; 519 } 520 521 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferConversion( 522 InductionInfo* a, 523 Primitive::Type from, 524 Primitive::Type to) { 525 if (a != nullptr) { 526 // Allow narrowing conversion on linear induction in certain cases: 527 // induction is already at narrow type, or can be made narrower. 528 if (IsNarrowingIntegralConversion(from, to) && 529 a->induction_class == kLinear && 530 (a->type == to || IsNarrowingIntegralConversion(a->type, to))) { 531 return CreateInduction(kLinear, kNop, a->op_a, a->op_b, a->fetch, to); 532 } 533 } 534 return nullptr; 535 } 536 537 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HInstruction* phi, 538 size_t input_index, 539 size_t adjust_input_size) { 540 // Match all phi inputs from input_index onwards exactly. 541 HInputsRef inputs = phi->GetInputs(); 542 DCHECK_LT(input_index, inputs.size()); 543 auto ita = cycle_.find(inputs[input_index]); 544 if (ita != cycle_.end()) { 545 for (size_t i = input_index + 1, n = inputs.size() - adjust_input_size; i < n; i++) { 546 auto itb = cycle_.find(inputs[i]); 547 if (itb == cycle_.end() || 548 !HInductionVarAnalysis::InductionEqual(ita->second, itb->second)) { 549 return nullptr; 550 } 551 } 552 return ita->second; 553 } 554 return nullptr; 555 } 556 557 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhiAllInputs( 558 HLoopInformation* loop, 559 HInstruction* entry_phi, 560 HInstruction* phi) { 561 // Match all phi inputs. 562 InductionInfo* match = SolvePhi(phi, /*input_index*/ 0, /*adjust_input_size*/ 0); 563 if (match != nullptr) { 564 return match; 565 } 566 567 // Otherwise, try to solve for a periodic seeded from phi onward. 568 // Only tight multi-statement cycles are considered in order to 569 // simplify rotating the periodic during the final classification. 570 if (phi->IsLoopHeaderPhi() && phi->InputCount() == 2) { 571 InductionInfo* a = LookupInfo(loop, phi->InputAt(0)); 572 if (a != nullptr && a->induction_class == kInvariant) { 573 if (phi->InputAt(1) == entry_phi) { 574 InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); 575 return CreateInduction(kPeriodic, kNop, a, initial, /*fetch*/ nullptr, type_); 576 } 577 InductionInfo* b = SolvePhi(phi, /*input_index*/ 1, /*adjust_input_size*/ 0); 578 if (b != nullptr && b->induction_class == kPeriodic) { 579 return CreateInduction(kPeriodic, kNop, a, b, /*fetch*/ nullptr, type_); 580 } 581 } 582 } 583 return nullptr; 584 } 585 586 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop, 587 HInstruction* entry_phi, 588 HInstruction* instruction, 589 HInstruction* x, 590 HInstruction* y, 591 InductionOp op, 592 bool is_first_call) { 593 // Solve within a cycle over an addition or subtraction. 594 InductionInfo* b = LookupInfo(loop, y); 595 if (b != nullptr) { 596 if (b->induction_class == kInvariant) { 597 // Adding or subtracting an invariant value, seeded from phi, 598 // keeps adding to the stride of the linear induction. 599 if (x == entry_phi) { 600 return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b); 601 } 602 auto it = cycle_.find(x); 603 if (it != cycle_.end()) { 604 InductionInfo* a = it->second; 605 if (a->induction_class == kInvariant) { 606 return CreateInvariantOp(op, a, b); 607 } 608 } 609 } else if (b->induction_class == kLinear && b->type == type_) { 610 // Solve within a tight cycle that adds a term that is already classified as a linear 611 // induction for a polynomial induction k = k + i (represented as sum over linear terms). 612 if (x == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) { 613 InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); 614 InductionInfo* new_a = op == kAdd ? b : TransferNeg(b); 615 if (new_a != nullptr) { 616 return CreateInduction(kPolynomial, kNop, new_a, initial, /*fetch*/ nullptr, type_); 617 } 618 } 619 } 620 } 621 622 // Try some alternatives before failing. 623 if (op == kAdd) { 624 // Try the other way around for an addition if considered for first time. 625 if (is_first_call) { 626 return SolveAddSub(loop, entry_phi, instruction, y, x, op, false); 627 } 628 } else if (op == kSub) { 629 // Solve within a tight cycle that is formed by exactly two instructions, 630 // one phi and one update, for a periodic idiom of the form k = c - k. 631 if (y == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) { 632 InductionInfo* a = LookupInfo(loop, x); 633 if (a != nullptr && a->induction_class == kInvariant) { 634 InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); 635 return CreateInduction(kPeriodic, 636 kNop, 637 CreateInvariantOp(kSub, a, initial), 638 initial, 639 /*fetch*/ nullptr, 640 type_); 641 } 642 } 643 } 644 return nullptr; 645 } 646 647 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveOp(HLoopInformation* loop, 648 HInstruction* entry_phi, 649 HInstruction* instruction, 650 HInstruction* x, 651 HInstruction* y, 652 InductionOp op) { 653 // Solve within a tight cycle for a binary operation k = k op c or, for some op, k = c op k. 654 if (entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) { 655 InductionInfo* c = nullptr; 656 InductionInfo* b = LookupInfo(loop, y); 657 if (b != nullptr && b->induction_class == kInvariant && entry_phi == x) { 658 c = b; 659 } else if (op != kDiv && op != kRem) { 660 InductionInfo* a = LookupInfo(loop, x); 661 if (a != nullptr && a->induction_class == kInvariant && entry_phi == y) { 662 c = a; 663 } 664 } 665 // Found suitable operand left or right? 666 if (c != nullptr) { 667 InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); 668 switch (op) { 669 case kMul: 670 case kDiv: 671 // Restrict base of geometric induction to direct fetch. 672 if (c->operation == kFetch) { 673 return CreateInduction(kGeometric, 674 op, 675 initial, 676 CreateConstant(0, type_), 677 c->fetch, 678 type_); 679 }; 680 break; 681 case kRem: 682 // Idiomatic MOD wrap-around induction. 683 return CreateInduction(kWrapAround, 684 kNop, 685 initial, 686 CreateInvariantOp(kRem, initial, c), 687 /*fetch*/ nullptr, 688 type_); 689 case kXor: 690 // Idiomatic XOR periodic induction. 691 return CreateInduction(kPeriodic, 692 kNop, 693 CreateInvariantOp(kXor, initial, c), 694 initial, 695 /*fetch*/ nullptr, 696 type_); 697 default: 698 LOG(FATAL) << op; 699 UNREACHABLE(); 700 } 701 } 702 } 703 return nullptr; 704 } 705 706 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveTest(HLoopInformation* loop, 707 HInstruction* entry_phi, 708 HInstruction* instruction, 709 int64_t opposite_value) { 710 // Detect hidden XOR construction in x = (x == false) or x = (x != true). 711 int64_t value = -1; 712 HInstruction* x = instruction->InputAt(0); 713 HInstruction* y = instruction->InputAt(1); 714 if (IsExact(LookupInfo(loop, x), &value) && value == opposite_value) { 715 return SolveOp(loop, entry_phi, instruction, graph_->GetIntConstant(1), y, kXor); 716 } else if (IsExact(LookupInfo(loop, y), &value) && value == opposite_value) { 717 return SolveOp(loop, entry_phi, instruction, x, graph_->GetIntConstant(1), kXor); 718 } 719 return nullptr; 720 } 721 722 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveConversion( 723 HLoopInformation* loop, 724 HInstruction* entry_phi, 725 HTypeConversion* conversion) { 726 Primitive::Type from = conversion->GetInputType(); 727 Primitive::Type to = conversion->GetResultType(); 728 // A narrowing conversion is allowed as *last* operation of the cycle of a linear induction 729 // with an initial value that fits the type, provided that the narrowest encountered type is 730 // recorded with the induction to account for the precision loss. The narrower induction does 731 // *not* transfer to any wider operations, however, since these may yield out-of-type values 732 if (entry_phi->InputCount() == 2 && conversion == entry_phi->InputAt(1)) { 733 int64_t min = Primitive::MinValueOfIntegralType(to); 734 int64_t max = Primitive::MaxValueOfIntegralType(to); 735 int64_t value = 0; 736 InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); 737 if (IsNarrowingIntegralConversion(from, to) && 738 IsAtLeast(initial, &value) && value >= min && 739 IsAtMost(initial, &value) && value <= max) { 740 auto it = cycle_.find(conversion->GetInput()); 741 if (it != cycle_.end() && it->second->induction_class == kInvariant) { 742 type_ = to; 743 return it->second; 744 } 745 } 746 } 747 return nullptr; 748 } 749 750 void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) { 751 HInstruction* control = loop->GetHeader()->GetLastInstruction(); 752 if (control->IsIf()) { 753 HIf* ifs = control->AsIf(); 754 HBasicBlock* if_true = ifs->IfTrueSuccessor(); 755 HBasicBlock* if_false = ifs->IfFalseSuccessor(); 756 HInstruction* if_expr = ifs->InputAt(0); 757 // Determine if loop has following structure in header. 758 // loop-header: .... 759 // if (condition) goto X 760 if (if_expr->IsCondition()) { 761 HCondition* condition = if_expr->AsCondition(); 762 InductionInfo* a = LookupInfo(loop, condition->InputAt(0)); 763 InductionInfo* b = LookupInfo(loop, condition->InputAt(1)); 764 Primitive::Type type = ImplicitConversion(condition->InputAt(0)->GetType()); 765 // Determine if the loop control uses a known sequence on an if-exit (X outside) or on 766 // an if-iterate (X inside), expressed as if-iterate when passed into VisitCondition(). 767 if (a == nullptr || b == nullptr) { 768 return; // Loop control is not a sequence. 769 } else if (if_true->GetLoopInformation() != loop && if_false->GetLoopInformation() == loop) { 770 VisitCondition(loop, a, b, type, condition->GetOppositeCondition()); 771 } else if (if_true->GetLoopInformation() == loop && if_false->GetLoopInformation() != loop) { 772 VisitCondition(loop, a, b, type, condition->GetCondition()); 773 } 774 } 775 } 776 } 777 778 void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, 779 InductionInfo* a, 780 InductionInfo* b, 781 Primitive::Type type, 782 IfCondition cmp) { 783 if (a->induction_class == kInvariant && b->induction_class == kLinear) { 784 // Swap condition if induction is at right-hand-side (e.g. U > i is same as i < U). 785 switch (cmp) { 786 case kCondLT: VisitCondition(loop, b, a, type, kCondGT); break; 787 case kCondLE: VisitCondition(loop, b, a, type, kCondGE); break; 788 case kCondGT: VisitCondition(loop, b, a, type, kCondLT); break; 789 case kCondGE: VisitCondition(loop, b, a, type, kCondLE); break; 790 case kCondNE: VisitCondition(loop, b, a, type, kCondNE); break; 791 default: break; 792 } 793 } else if (a->induction_class == kLinear && b->induction_class == kInvariant) { 794 // Analyze condition with induction at left-hand-side (e.g. i < U). 795 InductionInfo* lower_expr = a->op_b; 796 InductionInfo* upper_expr = b; 797 InductionInfo* stride_expr = a->op_a; 798 // Constant stride? 799 int64_t stride_value = 0; 800 if (!IsExact(stride_expr, &stride_value)) { 801 return; 802 } 803 // Rewrite condition i != U into strict end condition i < U or i > U if this end condition 804 // is reached exactly (tested by verifying if the loop has a unit stride and the non-strict 805 // condition would be always taken). 806 if (cmp == kCondNE && ((stride_value == +1 && IsTaken(lower_expr, upper_expr, kCondLE)) || 807 (stride_value == -1 && IsTaken(lower_expr, upper_expr, kCondGE)))) { 808 cmp = stride_value > 0 ? kCondLT : kCondGT; 809 } 810 // Only accept integral condition. A mismatch between the type of condition and the induction 811 // is only allowed if the, necessarily narrower, induction range fits the narrower control. 812 if (type != Primitive::kPrimInt && type != Primitive::kPrimLong) { 813 return; // not integral 814 } else if (type != a->type && 815 !FitsNarrowerControl(lower_expr, upper_expr, stride_value, a->type, cmp)) { 816 return; // mismatched type 817 } 818 // Normalize a linear loop control with a nonzero stride: 819 // stride > 0, either i < U or i <= U 820 // stride < 0, either i > U or i >= U 821 if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) || 822 (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) { 823 VisitTripCount(loop, lower_expr, upper_expr, stride_expr, stride_value, type, cmp); 824 } 825 } 826 } 827 828 void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, 829 InductionInfo* lower_expr, 830 InductionInfo* upper_expr, 831 InductionInfo* stride_expr, 832 int64_t stride_value, 833 Primitive::Type type, 834 IfCondition cmp) { 835 // Any loop of the general form: 836 // 837 // for (i = L; i <= U; i += S) // S > 0 838 // or for (i = L; i >= U; i += S) // S < 0 839 // .. i .. 840 // 841 // can be normalized into: 842 // 843 // for (n = 0; n < TC; n++) // where TC = (U + S - L) / S 844 // .. L + S * n .. 845 // 846 // taking the following into consideration: 847 // 848 // (1) Using the same precision, the TC (trip-count) expression should be interpreted as 849 // an unsigned entity, for example, as in the following loop that uses the full range: 850 // for (int i = INT_MIN; i < INT_MAX; i++) // TC = UINT_MAX 851 // (2) The TC is only valid if the loop is taken, otherwise TC = 0, as in: 852 // for (int i = 12; i < U; i++) // TC = 0 when U <= 12 853 // If this cannot be determined at compile-time, the TC is only valid within the 854 // loop-body proper, not the loop-header unless enforced with an explicit taken-test. 855 // (3) The TC is only valid if the loop is finite, otherwise TC has no value, as in: 856 // for (int i = 0; i <= U; i++) // TC = Inf when U = INT_MAX 857 // If this cannot be determined at compile-time, the TC is only valid when enforced 858 // with an explicit finite-test. 859 // (4) For loops which early-exits, the TC forms an upper bound, as in: 860 // for (int i = 0; i < 10 && ....; i++) // TC <= 10 861 InductionInfo* trip_count = upper_expr; 862 const bool is_taken = IsTaken(lower_expr, upper_expr, cmp); 863 const bool is_finite = IsFinite(upper_expr, stride_value, type, cmp); 864 const bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1; 865 if (!cancels) { 866 // Convert exclusive integral inequality into inclusive integral inequality, 867 // viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1. 868 if (cmp == kCondLT) { 869 trip_count = CreateInvariantOp(kSub, trip_count, CreateConstant(1, type)); 870 } else if (cmp == kCondGT) { 871 trip_count = CreateInvariantOp(kAdd, trip_count, CreateConstant(1, type)); 872 } 873 // Compensate for stride. 874 trip_count = CreateInvariantOp(kAdd, trip_count, stride_expr); 875 } 876 trip_count = CreateInvariantOp( 877 kDiv, CreateInvariantOp(kSub, trip_count, lower_expr), stride_expr); 878 // Assign the trip-count expression to the loop control. Clients that use the information 879 // should be aware that the expression is only valid under the conditions listed above. 880 InductionOp tcKind = kTripCountInBodyUnsafe; // needs both tests 881 if (is_taken && is_finite) { 882 tcKind = kTripCountInLoop; // needs neither test 883 } else if (is_finite) { 884 tcKind = kTripCountInBody; // needs taken-test 885 } else if (is_taken) { 886 tcKind = kTripCountInLoopUnsafe; // needs finite-test 887 } 888 InductionOp op = kNop; 889 switch (cmp) { 890 case kCondLT: op = kLT; break; 891 case kCondLE: op = kLE; break; 892 case kCondGT: op = kGT; break; 893 case kCondGE: op = kGE; break; 894 default: LOG(FATAL) << "CONDITION UNREACHABLE"; 895 } 896 // Associate trip count with control instruction, rather than the condition (even 897 // though it's its use) since former provides a convenient use-free placeholder. 898 HInstruction* control = loop->GetHeader()->GetLastInstruction(); 899 InductionInfo* taken_test = CreateInvariantOp(op, lower_expr, upper_expr); 900 DCHECK(control->IsIf()); 901 AssignInfo(loop, control, CreateTripCount(tcKind, trip_count, taken_test, type)); 902 } 903 904 bool HInductionVarAnalysis::IsTaken(InductionInfo* lower_expr, 905 InductionInfo* upper_expr, 906 IfCondition cmp) { 907 int64_t lower_value; 908 int64_t upper_value; 909 switch (cmp) { 910 case kCondLT: 911 return IsAtMost(lower_expr, &lower_value) 912 && IsAtLeast(upper_expr, &upper_value) 913 && lower_value < upper_value; 914 case kCondLE: 915 return IsAtMost(lower_expr, &lower_value) 916 && IsAtLeast(upper_expr, &upper_value) 917 && lower_value <= upper_value; 918 case kCondGT: 919 return IsAtLeast(lower_expr, &lower_value) 920 && IsAtMost(upper_expr, &upper_value) 921 && lower_value > upper_value; 922 case kCondGE: 923 return IsAtLeast(lower_expr, &lower_value) 924 && IsAtMost(upper_expr, &upper_value) 925 && lower_value >= upper_value; 926 default: 927 LOG(FATAL) << "CONDITION UNREACHABLE"; 928 } 929 return false; // not certain, may be untaken 930 } 931 932 bool HInductionVarAnalysis::IsFinite(InductionInfo* upper_expr, 933 int64_t stride_value, 934 Primitive::Type type, 935 IfCondition cmp) { 936 int64_t min = Primitive::MinValueOfIntegralType(type); 937 int64_t max = Primitive::MaxValueOfIntegralType(type); 938 // Some rules under which it is certain at compile-time that the loop is finite. 939 int64_t value; 940 switch (cmp) { 941 case kCondLT: 942 return stride_value == 1 || 943 (IsAtMost(upper_expr, &value) && value <= (max - stride_value + 1)); 944 case kCondLE: 945 return (IsAtMost(upper_expr, &value) && value <= (max - stride_value)); 946 case kCondGT: 947 return stride_value == -1 || 948 (IsAtLeast(upper_expr, &value) && value >= (min - stride_value - 1)); 949 case kCondGE: 950 return (IsAtLeast(upper_expr, &value) && value >= (min - stride_value)); 951 default: 952 LOG(FATAL) << "CONDITION UNREACHABLE"; 953 } 954 return false; // not certain, may be infinite 955 } 956 957 bool HInductionVarAnalysis::FitsNarrowerControl(InductionInfo* lower_expr, 958 InductionInfo* upper_expr, 959 int64_t stride_value, 960 Primitive::Type type, 961 IfCondition cmp) { 962 int64_t min = Primitive::MinValueOfIntegralType(type); 963 int64_t max = Primitive::MaxValueOfIntegralType(type); 964 // Inclusive test need one extra. 965 if (stride_value != 1 && stride_value != -1) { 966 return false; // non-unit stride 967 } else if (cmp == kCondLE) { 968 max--; 969 } else if (cmp == kCondGE) { 970 min++; 971 } 972 // Do both bounds fit the range? 973 int64_t value = 0; 974 return IsAtLeast(lower_expr, &value) && value >= min && 975 IsAtMost(lower_expr, &value) && value <= max && 976 IsAtLeast(upper_expr, &value) && value >= min && 977 IsAtMost(upper_expr, &value) && value <= max; 978 } 979 980 void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop, 981 HInstruction* instruction, 982 InductionInfo* info) { 983 auto it = induction_.find(loop); 984 if (it == induction_.end()) { 985 it = induction_.Put(loop, 986 ArenaSafeMap<HInstruction*, InductionInfo*>( 987 std::less<HInstruction*>(), 988 graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis))); 989 } 990 it->second.Put(instruction, info); 991 } 992 993 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInformation* loop, 994 HInstruction* instruction) { 995 auto it = induction_.find(loop); 996 if (it != induction_.end()) { 997 auto loop_it = it->second.find(instruction); 998 if (loop_it != it->second.end()) { 999 return loop_it->second; 1000 } 1001 } 1002 if (loop->IsDefinedOutOfTheLoop(instruction)) { 1003 InductionInfo* info = CreateInvariantFetch(instruction); 1004 AssignInfo(loop, instruction, info); 1005 return info; 1006 } 1007 return nullptr; 1008 } 1009 1010 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateConstant(int64_t value, 1011 Primitive::Type type) { 1012 HInstruction* constant; 1013 switch (type) { 1014 case Primitive::kPrimDouble: constant = graph_->GetDoubleConstant(value); break; 1015 case Primitive::kPrimFloat: constant = graph_->GetFloatConstant(value); break; 1016 case Primitive::kPrimLong: constant = graph_->GetLongConstant(value); break; 1017 default: constant = graph_->GetIntConstant(value); break; 1018 } 1019 return CreateInvariantFetch(constant); 1020 } 1021 1022 HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant( 1023 InductionOp op, 1024 InductionInfo* a, 1025 InductionInfo* b) { 1026 // Perform some light-weight simplifications during construction of a new invariant. 1027 // This often safes memory and yields a more concise representation of the induction. 1028 // More exhaustive simplifications are done by later phases once induction nodes are 1029 // translated back into HIR code (e.g. by loop optimizations or BCE). 1030 int64_t value = -1; 1031 if (IsExact(a, &value)) { 1032 if (value == 0) { 1033 // Simplify 0 + b = b, 0 ^ b = b, 0 * b = 0. 1034 if (op == kAdd || op == kXor) { 1035 return b; 1036 } else if (op == kMul) { 1037 return a; 1038 } 1039 } else if (op == kMul) { 1040 // Simplify 1 * b = b, -1 * b = -b 1041 if (value == 1) { 1042 return b; 1043 } else if (value == -1) { 1044 return CreateSimplifiedInvariant(kNeg, nullptr, b); 1045 } 1046 } 1047 } 1048 if (IsExact(b, &value)) { 1049 if (value == 0) { 1050 // Simplify a + 0 = a, a - 0 = a, a ^ 0 = a, a * 0 = 0, -0 = 0. 1051 if (op == kAdd || op == kSub || op == kXor) { 1052 return a; 1053 } else if (op == kMul || op == kNeg) { 1054 return b; 1055 } 1056 } else if (op == kMul || op == kDiv) { 1057 // Simplify a * 1 = a, a / 1 = a, a * -1 = -a, a / -1 = -a 1058 if (value == 1) { 1059 return a; 1060 } else if (value == -1) { 1061 return CreateSimplifiedInvariant(kNeg, nullptr, a); 1062 } 1063 } 1064 } else if (b->operation == kNeg) { 1065 // Simplify a + (-b) = a - b, a - (-b) = a + b, -(-b) = b. 1066 if (op == kAdd) { 1067 return CreateSimplifiedInvariant(kSub, a, b->op_b); 1068 } else if (op == kSub) { 1069 return CreateSimplifiedInvariant(kAdd, a, b->op_b); 1070 } else if (op == kNeg) { 1071 return b->op_b; 1072 } 1073 } else if (b->operation == kSub) { 1074 // Simplify - (a - b) = b - a. 1075 if (op == kNeg) { 1076 return CreateSimplifiedInvariant(kSub, b->op_b, b->op_a); 1077 } 1078 } 1079 return new (graph_->GetArena()) InductionInfo( 1080 kInvariant, op, a, b, nullptr, ImplicitConversion(b->type)); 1081 } 1082 1083 HInstruction* HInductionVarAnalysis::GetShiftConstant(HLoopInformation* loop, 1084 HInstruction* instruction, 1085 InductionInfo* initial) { 1086 DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()); 1087 // Shift-rights are only the same as division for non-negative initial inputs. 1088 // Otherwise we would round incorrectly. 1089 if (initial != nullptr) { 1090 int64_t value = -1; 1091 if (!IsAtLeast(initial, &value) || value < 0) { 1092 return nullptr; 1093 } 1094 } 1095 // Obtain the constant needed to treat shift as equivalent multiplication or division. 1096 // This yields an existing instruction if the constant is already there. Otherwise, this 1097 // has a side effect on the HIR. The restriction on the shift factor avoids generating a 1098 // negative constant (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that 1099 // generalization for shift factors outside [0,32) and [0,64) ranges is done earlier. 1100 InductionInfo* b = LookupInfo(loop, instruction->InputAt(1)); 1101 int64_t value = -1; 1102 if (IsExact(b, &value)) { 1103 Primitive::Type type = instruction->InputAt(0)->GetType(); 1104 if (type == Primitive::kPrimInt && 0 <= value && value < 31) { 1105 return graph_->GetIntConstant(1 << value); 1106 } 1107 if (type == Primitive::kPrimLong && 0 <= value && value < 63) { 1108 return graph_->GetLongConstant(1L << value); 1109 } 1110 } 1111 return nullptr; 1112 } 1113 1114 void HInductionVarAnalysis::AssignCycle(HPhi* phi) { 1115 ArenaSet<HInstruction*>* set = &cycles_.Put(phi, ArenaSet<HInstruction*>( 1116 graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)))->second; 1117 for (HInstruction* i : scc_) { 1118 set->insert(i); 1119 } 1120 } 1121 1122 ArenaSet<HInstruction*>* HInductionVarAnalysis::LookupCycle(HPhi* phi) { 1123 auto it = cycles_.find(phi); 1124 if (it != cycles_.end()) { 1125 return &it->second; 1126 } 1127 return nullptr; 1128 } 1129 1130 bool HInductionVarAnalysis::IsExact(InductionInfo* info, int64_t* value) { 1131 return InductionVarRange(this).IsConstant(info, InductionVarRange::kExact, value); 1132 } 1133 1134 bool HInductionVarAnalysis::IsAtMost(InductionInfo* info, int64_t* value) { 1135 return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtMost, value); 1136 } 1137 1138 bool HInductionVarAnalysis::IsAtLeast(InductionInfo* info, int64_t* value) { 1139 return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtLeast, value); 1140 } 1141 1142 bool HInductionVarAnalysis::IsNarrowingLinear(InductionInfo* info) { 1143 return info != nullptr && 1144 info->induction_class == kLinear && 1145 (info->type == Primitive::kPrimByte || 1146 info->type == Primitive::kPrimShort || 1147 info->type == Primitive::kPrimChar || 1148 (info->type == Primitive::kPrimInt && (info->op_a->type == Primitive::kPrimLong || 1149 info->op_b->type == Primitive::kPrimLong))); 1150 } 1151 1152 bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1, 1153 InductionInfo* info2) { 1154 // Test structural equality only, without accounting for simplifications. 1155 if (info1 != nullptr && info2 != nullptr) { 1156 return 1157 info1->induction_class == info2->induction_class && 1158 info1->operation == info2->operation && 1159 info1->fetch == info2->fetch && 1160 info1->type == info2->type && 1161 InductionEqual(info1->op_a, info2->op_a) && 1162 InductionEqual(info1->op_b, info2->op_b); 1163 } 1164 // Otherwise only two nullptrs are considered equal. 1165 return info1 == info2; 1166 } 1167 1168 std::string HInductionVarAnalysis::FetchToString(HInstruction* fetch) { 1169 DCHECK(fetch != nullptr); 1170 if (fetch->IsIntConstant()) { 1171 return std::to_string(fetch->AsIntConstant()->GetValue()); 1172 } else if (fetch->IsLongConstant()) { 1173 return std::to_string(fetch->AsLongConstant()->GetValue()); 1174 } 1175 return std::to_string(fetch->GetId()) + ":" + fetch->DebugName(); 1176 } 1177 1178 std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) { 1179 if (info != nullptr) { 1180 if (info->induction_class == kInvariant) { 1181 std::string inv = "("; 1182 inv += InductionToString(info->op_a); 1183 switch (info->operation) { 1184 case kNop: inv += " @ "; break; 1185 case kAdd: inv += " + "; break; 1186 case kSub: 1187 case kNeg: inv += " - "; break; 1188 case kMul: inv += " * "; break; 1189 case kDiv: inv += " / "; break; 1190 case kRem: inv += " % "; break; 1191 case kXor: inv += " ^ "; break; 1192 case kLT: inv += " < "; break; 1193 case kLE: inv += " <= "; break; 1194 case kGT: inv += " > "; break; 1195 case kGE: inv += " >= "; break; 1196 case kFetch: inv += FetchToString(info->fetch); break; 1197 case kTripCountInLoop: inv += " (TC-loop) "; break; 1198 case kTripCountInBody: inv += " (TC-body) "; break; 1199 case kTripCountInLoopUnsafe: inv += " (TC-loop-unsafe) "; break; 1200 case kTripCountInBodyUnsafe: inv += " (TC-body-unsafe) "; break; 1201 } 1202 inv += InductionToString(info->op_b); 1203 inv += ")"; 1204 return inv; 1205 } else { 1206 if (info->induction_class == kLinear) { 1207 DCHECK(info->operation == kNop); 1208 return "(" + InductionToString(info->op_a) + " * i + " + 1209 InductionToString(info->op_b) + "):" + 1210 Primitive::PrettyDescriptor(info->type); 1211 } else if (info->induction_class == kPolynomial) { 1212 DCHECK(info->operation == kNop); 1213 return "poly(sum_lt(" + InductionToString(info->op_a) + ") + " + 1214 InductionToString(info->op_b) + "):" + 1215 Primitive::PrettyDescriptor(info->type); 1216 } else if (info->induction_class == kGeometric) { 1217 DCHECK(info->operation == kMul || info->operation == kDiv); 1218 DCHECK(info->fetch != nullptr); 1219 return "geo(" + InductionToString(info->op_a) + " * " + 1220 FetchToString(info->fetch) + 1221 (info->operation == kMul ? " ^ i + " : " ^ -i + ") + 1222 InductionToString(info->op_b) + "):" + 1223 Primitive::PrettyDescriptor(info->type); 1224 } else if (info->induction_class == kWrapAround) { 1225 DCHECK(info->operation == kNop); 1226 return "wrap(" + InductionToString(info->op_a) + ", " + 1227 InductionToString(info->op_b) + "):" + 1228 Primitive::PrettyDescriptor(info->type); 1229 } else if (info->induction_class == kPeriodic) { 1230 DCHECK(info->operation == kNop); 1231 return "periodic(" + InductionToString(info->op_a) + ", " + 1232 InductionToString(info->op_b) + "):" + 1233 Primitive::PrettyDescriptor(info->type); 1234 } 1235 } 1236 } 1237 return ""; 1238 } 1239 1240 } // namespace art 1241