1 //===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file "describes" induction and recurrence variables. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/Analysis/IVDescriptors.h" 14 #include "llvm/ADT/ScopeExit.h" 15 #include "llvm/Analysis/BasicAliasAnalysis.h" 16 #include "llvm/Analysis/DemandedBits.h" 17 #include "llvm/Analysis/DomTreeUpdater.h" 18 #include "llvm/Analysis/GlobalsModRef.h" 19 #include "llvm/Analysis/InstructionSimplify.h" 20 #include "llvm/Analysis/LoopInfo.h" 21 #include "llvm/Analysis/LoopPass.h" 22 #include "llvm/Analysis/MustExecute.h" 23 #include "llvm/Analysis/ScalarEvolution.h" 24 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 25 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 26 #include "llvm/Analysis/TargetTransformInfo.h" 27 #include "llvm/Analysis/ValueTracking.h" 28 #include "llvm/IR/Dominators.h" 29 #include "llvm/IR/Instructions.h" 30 #include "llvm/IR/Module.h" 31 #include "llvm/IR/PatternMatch.h" 32 #include "llvm/IR/ValueHandle.h" 33 #include "llvm/Pass.h" 34 #include "llvm/Support/Debug.h" 35 #include "llvm/Support/KnownBits.h" 36 37 using namespace llvm; 38 using namespace llvm::PatternMatch; 39 40 #define DEBUG_TYPE "iv-descriptors" 41 42 bool RecurrenceDescriptor::areAllUsesIn(Instruction *I, 43 SmallPtrSetImpl<Instruction *> &Set) { 44 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) 45 if (!Set.count(dyn_cast<Instruction>(*Use))) 46 return false; 47 return true; 48 } 49 50 bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurKind Kind) { 51 switch (Kind) { 52 default: 53 break; 54 case RecurKind::Add: 55 case RecurKind::Mul: 56 case RecurKind::Or: 57 case RecurKind::And: 58 case RecurKind::Xor: 59 case RecurKind::SMax: 60 case RecurKind::SMin: 61 case RecurKind::UMax: 62 case RecurKind::UMin: 63 return true; 64 } 65 return false; 66 } 67 68 bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurKind Kind) { 69 return (Kind != RecurKind::None) && !isIntegerRecurrenceKind(Kind); 70 } 71 72 bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurKind Kind) { 73 switch (Kind) { 74 default: 75 break; 76 case RecurKind::Add: 77 case RecurKind::Mul: 78 case RecurKind::FAdd: 79 case RecurKind::FMul: 80 return true; 81 } 82 return false; 83 } 84 85 /// Determines if Phi may have been type-promoted. If Phi has a single user 86 /// that ANDs the Phi with a type mask, return the user. RT is updated to 87 /// account for the narrower bit width represented by the mask, and the AND 88 /// instruction is added to CI. 89 static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT, 90 SmallPtrSetImpl<Instruction *> &Visited, 91 SmallPtrSetImpl<Instruction *> &CI) { 92 if (!Phi->hasOneUse()) 93 return Phi; 94 95 const APInt *M = nullptr; 96 Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser()); 97 98 // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT 99 // with a new integer type of the corresponding bit width. 100 if (match(J, m_c_And(m_Instruction(I), m_APInt(M)))) { 101 int32_t Bits = (*M + 1).exactLogBase2(); 102 if (Bits > 0) { 103 RT = IntegerType::get(Phi->getContext(), Bits); 104 Visited.insert(Phi); 105 CI.insert(J); 106 return J; 107 } 108 } 109 return Phi; 110 } 111 112 /// Compute the minimal bit width needed to represent a reduction whose exit 113 /// instruction is given by Exit. 114 static std::pair<Type *, bool> computeRecurrenceType(Instruction *Exit, 115 DemandedBits *DB, 116 AssumptionCache *AC, 117 DominatorTree *DT) { 118 bool IsSigned = false; 119 const DataLayout &DL = Exit->getModule()->getDataLayout(); 120 uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType()); 121 122 if (DB) { 123 // Use the demanded bits analysis to determine the bits that are live out 124 // of the exit instruction, rounding up to the nearest power of two. If the 125 // use of demanded bits results in a smaller bit width, we know the value 126 // must be positive (i.e., IsSigned = false), because if this were not the 127 // case, the sign bit would have been demanded. 128 auto Mask = DB->getDemandedBits(Exit); 129 MaxBitWidth = Mask.getBitWidth() - Mask.countLeadingZeros(); 130 } 131 132 if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) { 133 // If demanded bits wasn't able to limit the bit width, we can try to use 134 // value tracking instead. This can be the case, for example, if the value 135 // may be negative. 136 auto NumSignBits = ComputeNumSignBits(Exit, DL, 0, AC, nullptr, DT); 137 auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType()); 138 MaxBitWidth = NumTypeBits - NumSignBits; 139 KnownBits Bits = computeKnownBits(Exit, DL); 140 if (!Bits.isNonNegative()) { 141 // If the value is not known to be non-negative, we set IsSigned to true, 142 // meaning that we will use sext instructions instead of zext 143 // instructions to restore the original type. 144 IsSigned = true; 145 if (!Bits.isNegative()) 146 // If the value is not known to be negative, we don't known what the 147 // upper bit is, and therefore, we don't know what kind of extend we 148 // will need. In this case, just increase the bit width by one bit and 149 // use sext. 150 ++MaxBitWidth; 151 } 152 } 153 if (!isPowerOf2_64(MaxBitWidth)) 154 MaxBitWidth = NextPowerOf2(MaxBitWidth); 155 156 return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth), 157 IsSigned); 158 } 159 160 /// Collect cast instructions that can be ignored in the vectorizer's cost 161 /// model, given a reduction exit value and the minimal type in which the 162 /// reduction can be represented. 163 static void collectCastsToIgnore(Loop *TheLoop, Instruction *Exit, 164 Type *RecurrenceType, 165 SmallPtrSetImpl<Instruction *> &Casts) { 166 167 SmallVector<Instruction *, 8> Worklist; 168 SmallPtrSet<Instruction *, 8> Visited; 169 Worklist.push_back(Exit); 170 171 while (!Worklist.empty()) { 172 Instruction *Val = Worklist.pop_back_val(); 173 Visited.insert(Val); 174 if (auto *Cast = dyn_cast<CastInst>(Val)) 175 if (Cast->getSrcTy() == RecurrenceType) { 176 // If the source type of a cast instruction is equal to the recurrence 177 // type, it will be eliminated, and should be ignored in the vectorizer 178 // cost model. 179 Casts.insert(Cast); 180 continue; 181 } 182 183 // Add all operands to the work list if they are loop-varying values that 184 // we haven't yet visited. 185 for (Value *O : cast<User>(Val)->operands()) 186 if (auto *I = dyn_cast<Instruction>(O)) 187 if (TheLoop->contains(I) && !Visited.count(I)) 188 Worklist.push_back(I); 189 } 190 } 191 192 bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurKind Kind, 193 Loop *TheLoop, bool HasFunNoNaNAttr, 194 RecurrenceDescriptor &RedDes, 195 DemandedBits *DB, 196 AssumptionCache *AC, 197 DominatorTree *DT) { 198 if (Phi->getNumIncomingValues() != 2) 199 return false; 200 201 // Reduction variables are only found in the loop header block. 202 if (Phi->getParent() != TheLoop->getHeader()) 203 return false; 204 205 // Obtain the reduction start value from the value that comes from the loop 206 // preheader. 207 Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()); 208 209 // ExitInstruction is the single value which is used outside the loop. 210 // We only allow for a single reduction value to be used outside the loop. 211 // This includes users of the reduction, variables (which form a cycle 212 // which ends in the phi node). 213 Instruction *ExitInstruction = nullptr; 214 // Indicates that we found a reduction operation in our scan. 215 bool FoundReduxOp = false; 216 217 // We start with the PHI node and scan for all of the users of this 218 // instruction. All users must be instructions that can be used as reduction 219 // variables (such as ADD). We must have a single out-of-block user. The cycle 220 // must include the original PHI. 221 bool FoundStartPHI = false; 222 223 // To recognize min/max patterns formed by a icmp select sequence, we store 224 // the number of instruction we saw from the recognized min/max pattern, 225 // to make sure we only see exactly the two instructions. 226 unsigned NumCmpSelectPatternInst = 0; 227 InstDesc ReduxDesc(false, nullptr); 228 229 // Data used for determining if the recurrence has been type-promoted. 230 Type *RecurrenceType = Phi->getType(); 231 SmallPtrSet<Instruction *, 4> CastInsts; 232 Instruction *Start = Phi; 233 bool IsSigned = false; 234 235 SmallPtrSet<Instruction *, 8> VisitedInsts; 236 SmallVector<Instruction *, 8> Worklist; 237 238 // Return early if the recurrence kind does not match the type of Phi. If the 239 // recurrence kind is arithmetic, we attempt to look through AND operations 240 // resulting from the type promotion performed by InstCombine. Vector 241 // operations are not limited to the legal integer widths, so we may be able 242 // to evaluate the reduction in the narrower width. 243 if (RecurrenceType->isFloatingPointTy()) { 244 if (!isFloatingPointRecurrenceKind(Kind)) 245 return false; 246 } else if (RecurrenceType->isIntegerTy()) { 247 if (!isIntegerRecurrenceKind(Kind)) 248 return false; 249 if (isArithmeticRecurrenceKind(Kind)) 250 Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts); 251 } else { 252 // Pointer min/max may exist, but it is not supported as a reduction op. 253 return false; 254 } 255 256 Worklist.push_back(Start); 257 VisitedInsts.insert(Start); 258 259 // Start with all flags set because we will intersect this with the reduction 260 // flags from all the reduction operations. 261 FastMathFlags FMF = FastMathFlags::getFast(); 262 263 // A value in the reduction can be used: 264 // - By the reduction: 265 // - Reduction operation: 266 // - One use of reduction value (safe). 267 // - Multiple use of reduction value (not safe). 268 // - PHI: 269 // - All uses of the PHI must be the reduction (safe). 270 // - Otherwise, not safe. 271 // - By instructions outside of the loop (safe). 272 // * One value may have several outside users, but all outside 273 // uses must be of the same value. 274 // - By an instruction that is not part of the reduction (not safe). 275 // This is either: 276 // * An instruction type other than PHI or the reduction operation. 277 // * A PHI in the header other than the initial PHI. 278 while (!Worklist.empty()) { 279 Instruction *Cur = Worklist.pop_back_val(); 280 281 // No Users. 282 // If the instruction has no users then this is a broken chain and can't be 283 // a reduction variable. 284 if (Cur->use_empty()) 285 return false; 286 287 bool IsAPhi = isa<PHINode>(Cur); 288 289 // A header PHI use other than the original PHI. 290 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent()) 291 return false; 292 293 // Reductions of instructions such as Div, and Sub is only possible if the 294 // LHS is the reduction variable. 295 if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) && 296 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) && 297 !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0)))) 298 return false; 299 300 // Any reduction instruction must be of one of the allowed kinds. We ignore 301 // the starting value (the Phi or an AND instruction if the Phi has been 302 // type-promoted). 303 if (Cur != Start) { 304 ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr); 305 if (!ReduxDesc.isRecurrence()) 306 return false; 307 // FIXME: FMF is allowed on phi, but propagation is not handled correctly. 308 if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi) 309 FMF &= ReduxDesc.getPatternInst()->getFastMathFlags(); 310 // Update this reduction kind if we matched a new instruction. 311 // TODO: Can we eliminate the need for a 2nd InstDesc by keeping 'Kind' 312 // state accurate while processing the worklist? 313 if (ReduxDesc.getRecKind() != RecurKind::None) 314 Kind = ReduxDesc.getRecKind(); 315 } 316 317 bool IsASelect = isa<SelectInst>(Cur); 318 319 // A conditional reduction operation must only have 2 or less uses in 320 // VisitedInsts. 321 if (IsASelect && (Kind == RecurKind::FAdd || Kind == RecurKind::FMul) && 322 hasMultipleUsesOf(Cur, VisitedInsts, 2)) 323 return false; 324 325 // A reduction operation must only have one use of the reduction value. 326 if (!IsAPhi && !IsASelect && !isMinMaxRecurrenceKind(Kind) && 327 hasMultipleUsesOf(Cur, VisitedInsts, 1)) 328 return false; 329 330 // All inputs to a PHI node must be a reduction value. 331 if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts)) 332 return false; 333 334 if (isIntMinMaxRecurrenceKind(Kind) && 335 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur))) 336 ++NumCmpSelectPatternInst; 337 if (isFPMinMaxRecurrenceKind(Kind) && 338 (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur))) 339 ++NumCmpSelectPatternInst; 340 341 // Check whether we found a reduction operator. 342 FoundReduxOp |= !IsAPhi && Cur != Start; 343 344 // Process users of current instruction. Push non-PHI nodes after PHI nodes 345 // onto the stack. This way we are going to have seen all inputs to PHI 346 // nodes once we get to them. 347 SmallVector<Instruction *, 8> NonPHIs; 348 SmallVector<Instruction *, 8> PHIs; 349 for (User *U : Cur->users()) { 350 Instruction *UI = cast<Instruction>(U); 351 352 // Check if we found the exit user. 353 BasicBlock *Parent = UI->getParent(); 354 if (!TheLoop->contains(Parent)) { 355 // If we already know this instruction is used externally, move on to 356 // the next user. 357 if (ExitInstruction == Cur) 358 continue; 359 360 // Exit if you find multiple values used outside or if the header phi 361 // node is being used. In this case the user uses the value of the 362 // previous iteration, in which case we would loose "VF-1" iterations of 363 // the reduction operation if we vectorize. 364 if (ExitInstruction != nullptr || Cur == Phi) 365 return false; 366 367 // The instruction used by an outside user must be the last instruction 368 // before we feed back to the reduction phi. Otherwise, we loose VF-1 369 // operations on the value. 370 if (!is_contained(Phi->operands(), Cur)) 371 return false; 372 373 ExitInstruction = Cur; 374 continue; 375 } 376 377 // Process instructions only once (termination). Each reduction cycle 378 // value must only be used once, except by phi nodes and min/max 379 // reductions which are represented as a cmp followed by a select. 380 InstDesc IgnoredVal(false, nullptr); 381 if (VisitedInsts.insert(UI).second) { 382 if (isa<PHINode>(UI)) 383 PHIs.push_back(UI); 384 else 385 NonPHIs.push_back(UI); 386 } else if (!isa<PHINode>(UI) && 387 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) && 388 !isa<SelectInst>(UI)) || 389 (!isConditionalRdxPattern(Kind, UI).isRecurrence() && 390 !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()))) 391 return false; 392 393 // Remember that we completed the cycle. 394 if (UI == Phi) 395 FoundStartPHI = true; 396 } 397 Worklist.append(PHIs.begin(), PHIs.end()); 398 Worklist.append(NonPHIs.begin(), NonPHIs.end()); 399 } 400 401 // This means we have seen one but not the other instruction of the 402 // pattern or more than just a select and cmp. 403 if (isMinMaxRecurrenceKind(Kind) && NumCmpSelectPatternInst != 2) 404 return false; 405 406 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) 407 return false; 408 409 if (Start != Phi) { 410 // If the starting value is not the same as the phi node, we speculatively 411 // looked through an 'and' instruction when evaluating a potential 412 // arithmetic reduction to determine if it may have been type-promoted. 413 // 414 // We now compute the minimal bit width that is required to represent the 415 // reduction. If this is the same width that was indicated by the 'and', we 416 // can represent the reduction in the smaller type. The 'and' instruction 417 // will be eliminated since it will essentially be a cast instruction that 418 // can be ignore in the cost model. If we compute a different type than we 419 // did when evaluating the 'and', the 'and' will not be eliminated, and we 420 // will end up with different kinds of operations in the recurrence 421 // expression (e.g., IntegerAND, IntegerADD). We give up if this is 422 // the case. 423 // 424 // The vectorizer relies on InstCombine to perform the actual 425 // type-shrinking. It does this by inserting instructions to truncate the 426 // exit value of the reduction to the width indicated by RecurrenceType and 427 // then extend this value back to the original width. If IsSigned is false, 428 // a 'zext' instruction will be generated; otherwise, a 'sext' will be 429 // used. 430 // 431 // TODO: We should not rely on InstCombine to rewrite the reduction in the 432 // smaller type. We should just generate a correctly typed expression 433 // to begin with. 434 Type *ComputedType; 435 std::tie(ComputedType, IsSigned) = 436 computeRecurrenceType(ExitInstruction, DB, AC, DT); 437 if (ComputedType != RecurrenceType) 438 return false; 439 440 // The recurrence expression will be represented in a narrower type. If 441 // there are any cast instructions that will be unnecessary, collect them 442 // in CastInsts. Note that the 'and' instruction was already included in 443 // this list. 444 // 445 // TODO: A better way to represent this may be to tag in some way all the 446 // instructions that are a part of the reduction. The vectorizer cost 447 // model could then apply the recurrence type to these instructions, 448 // without needing a white list of instructions to ignore. 449 // This may also be useful for the inloop reductions, if it can be 450 // kept simple enough. 451 collectCastsToIgnore(TheLoop, ExitInstruction, RecurrenceType, CastInsts); 452 } 453 454 // We found a reduction var if we have reached the original phi node and we 455 // only have a single instruction with out-of-loop users. 456 457 // The ExitInstruction(Instruction which is allowed to have out-of-loop users) 458 // is saved as part of the RecurrenceDescriptor. 459 460 // Save the description of this reduction variable. 461 RecurrenceDescriptor RD(RdxStart, ExitInstruction, Kind, FMF, 462 ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, 463 IsSigned, CastInsts); 464 RedDes = RD; 465 466 return true; 467 } 468 469 RecurrenceDescriptor::InstDesc 470 RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, 471 const InstDesc &Prev) { 472 assert((isa<CmpInst>(I) || isa<SelectInst>(I)) && 473 "Expected a cmp or select instruction"); 474 475 // We must handle the select(cmp()) as a single instruction. Advance to the 476 // select. 477 CmpInst::Predicate Pred; 478 if (match(I, m_OneUse(m_Cmp(Pred, m_Value(), m_Value())))) { 479 if (auto *Select = dyn_cast<SelectInst>(*I->user_begin())) 480 return InstDesc(Select, Prev.getRecKind()); 481 } 482 483 // Only match select with single use cmp condition. 484 if (!match(I, m_Select(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), m_Value(), 485 m_Value()))) 486 return InstDesc(false, I); 487 488 // Look for a min/max pattern. 489 if (match(I, m_UMin(m_Value(), m_Value()))) 490 return InstDesc(I, RecurKind::UMin); 491 if (match(I, m_UMax(m_Value(), m_Value()))) 492 return InstDesc(I, RecurKind::UMax); 493 if (match(I, m_SMax(m_Value(), m_Value()))) 494 return InstDesc(I, RecurKind::SMax); 495 if (match(I, m_SMin(m_Value(), m_Value()))) 496 return InstDesc(I, RecurKind::SMin); 497 if (match(I, m_OrdFMin(m_Value(), m_Value()))) 498 return InstDesc(I, RecurKind::FMin); 499 if (match(I, m_OrdFMax(m_Value(), m_Value()))) 500 return InstDesc(I, RecurKind::FMax); 501 if (match(I, m_UnordFMin(m_Value(), m_Value()))) 502 return InstDesc(I, RecurKind::FMin); 503 if (match(I, m_UnordFMax(m_Value(), m_Value()))) 504 return InstDesc(I, RecurKind::FMax); 505 506 return InstDesc(false, I); 507 } 508 509 /// Returns true if the select instruction has users in the compare-and-add 510 /// reduction pattern below. The select instruction argument is the last one 511 /// in the sequence. 512 /// 513 /// %sum.1 = phi ... 514 /// ... 515 /// %cmp = fcmp pred %0, %CFP 516 /// %add = fadd %0, %sum.1 517 /// %sum.2 = select %cmp, %add, %sum.1 518 RecurrenceDescriptor::InstDesc 519 RecurrenceDescriptor::isConditionalRdxPattern(RecurKind Kind, Instruction *I) { 520 SelectInst *SI = dyn_cast<SelectInst>(I); 521 if (!SI) 522 return InstDesc(false, I); 523 524 CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition()); 525 // Only handle single use cases for now. 526 if (!CI || !CI->hasOneUse()) 527 return InstDesc(false, I); 528 529 Value *TrueVal = SI->getTrueValue(); 530 Value *FalseVal = SI->getFalseValue(); 531 // Handle only when either of operands of select instruction is a PHI 532 // node for now. 533 if ((isa<PHINode>(*TrueVal) && isa<PHINode>(*FalseVal)) || 534 (!isa<PHINode>(*TrueVal) && !isa<PHINode>(*FalseVal))) 535 return InstDesc(false, I); 536 537 Instruction *I1 = 538 isa<PHINode>(*TrueVal) ? dyn_cast<Instruction>(FalseVal) 539 : dyn_cast<Instruction>(TrueVal); 540 if (!I1 || !I1->isBinaryOp()) 541 return InstDesc(false, I); 542 543 Value *Op1, *Op2; 544 if ((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1) || 545 m_FSub(m_Value(Op1), m_Value(Op2)).match(I1)) && 546 I1->isFast()) 547 return InstDesc(Kind == RecurKind::FAdd, SI); 548 549 if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast())) 550 return InstDesc(Kind == RecurKind::FMul, SI); 551 552 return InstDesc(false, I); 553 } 554 555 RecurrenceDescriptor::InstDesc 556 RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurKind Kind, 557 InstDesc &Prev, bool HasFunNoNaNAttr) { 558 Instruction *UAI = Prev.getUnsafeAlgebraInst(); 559 if (!UAI && isa<FPMathOperator>(I) && !I->hasAllowReassoc()) 560 UAI = I; // Found an unsafe (unvectorizable) algebra instruction. 561 562 switch (I->getOpcode()) { 563 default: 564 return InstDesc(false, I); 565 case Instruction::PHI: 566 return InstDesc(I, Prev.getRecKind(), Prev.getUnsafeAlgebraInst()); 567 case Instruction::Sub: 568 case Instruction::Add: 569 return InstDesc(Kind == RecurKind::Add, I); 570 case Instruction::Mul: 571 return InstDesc(Kind == RecurKind::Mul, I); 572 case Instruction::And: 573 return InstDesc(Kind == RecurKind::And, I); 574 case Instruction::Or: 575 return InstDesc(Kind == RecurKind::Or, I); 576 case Instruction::Xor: 577 return InstDesc(Kind == RecurKind::Xor, I); 578 case Instruction::FDiv: 579 case Instruction::FMul: 580 return InstDesc(Kind == RecurKind::FMul, I, UAI); 581 case Instruction::FSub: 582 case Instruction::FAdd: 583 return InstDesc(Kind == RecurKind::FAdd, I, UAI); 584 case Instruction::Select: 585 if (Kind == RecurKind::FAdd || Kind == RecurKind::FMul) 586 return isConditionalRdxPattern(Kind, I); 587 LLVM_FALLTHROUGH; 588 case Instruction::FCmp: 589 case Instruction::ICmp: 590 if (!isIntMinMaxRecurrenceKind(Kind) && 591 (!HasFunNoNaNAttr || !isFPMinMaxRecurrenceKind(Kind))) 592 return InstDesc(false, I); 593 return isMinMaxSelectCmpPattern(I, Prev); 594 } 595 } 596 597 bool RecurrenceDescriptor::hasMultipleUsesOf( 598 Instruction *I, SmallPtrSetImpl<Instruction *> &Insts, 599 unsigned MaxNumUses) { 600 unsigned NumUses = 0; 601 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; 602 ++Use) { 603 if (Insts.count(dyn_cast<Instruction>(*Use))) 604 ++NumUses; 605 if (NumUses > MaxNumUses) 606 return true; 607 } 608 609 return false; 610 } 611 bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop, 612 RecurrenceDescriptor &RedDes, 613 DemandedBits *DB, AssumptionCache *AC, 614 DominatorTree *DT) { 615 616 BasicBlock *Header = TheLoop->getHeader(); 617 Function &F = *Header->getParent(); 618 bool HasFunNoNaNAttr = 619 F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true"; 620 621 if (AddReductionVar(Phi, RecurKind::Add, TheLoop, HasFunNoNaNAttr, RedDes, DB, 622 AC, DT)) { 623 LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n"); 624 return true; 625 } 626 if (AddReductionVar(Phi, RecurKind::Mul, TheLoop, HasFunNoNaNAttr, RedDes, DB, 627 AC, DT)) { 628 LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n"); 629 return true; 630 } 631 if (AddReductionVar(Phi, RecurKind::Or, TheLoop, HasFunNoNaNAttr, RedDes, DB, 632 AC, DT)) { 633 LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n"); 634 return true; 635 } 636 if (AddReductionVar(Phi, RecurKind::And, TheLoop, HasFunNoNaNAttr, RedDes, DB, 637 AC, DT)) { 638 LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n"); 639 return true; 640 } 641 if (AddReductionVar(Phi, RecurKind::Xor, TheLoop, HasFunNoNaNAttr, RedDes, DB, 642 AC, DT)) { 643 LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n"); 644 return true; 645 } 646 if (AddReductionVar(Phi, RecurKind::SMax, TheLoop, HasFunNoNaNAttr, RedDes, 647 DB, AC, DT)) { 648 LLVM_DEBUG(dbgs() << "Found a SMAX reduction PHI." << *Phi << "\n"); 649 return true; 650 } 651 if (AddReductionVar(Phi, RecurKind::SMin, TheLoop, HasFunNoNaNAttr, RedDes, 652 DB, AC, DT)) { 653 LLVM_DEBUG(dbgs() << "Found a SMIN reduction PHI." << *Phi << "\n"); 654 return true; 655 } 656 if (AddReductionVar(Phi, RecurKind::UMax, TheLoop, HasFunNoNaNAttr, RedDes, 657 DB, AC, DT)) { 658 LLVM_DEBUG(dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n"); 659 return true; 660 } 661 if (AddReductionVar(Phi, RecurKind::UMin, TheLoop, HasFunNoNaNAttr, RedDes, 662 DB, AC, DT)) { 663 LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n"); 664 return true; 665 } 666 if (AddReductionVar(Phi, RecurKind::FMul, TheLoop, HasFunNoNaNAttr, RedDes, 667 DB, AC, DT)) { 668 LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n"); 669 return true; 670 } 671 if (AddReductionVar(Phi, RecurKind::FAdd, TheLoop, HasFunNoNaNAttr, RedDes, 672 DB, AC, DT)) { 673 LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n"); 674 return true; 675 } 676 if (AddReductionVar(Phi, RecurKind::FMax, TheLoop, HasFunNoNaNAttr, RedDes, 677 DB, AC, DT)) { 678 LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n"); 679 return true; 680 } 681 if (AddReductionVar(Phi, RecurKind::FMin, TheLoop, HasFunNoNaNAttr, RedDes, 682 DB, AC, DT)) { 683 LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n"); 684 return true; 685 } 686 // Not a reduction of known type. 687 return false; 688 } 689 690 bool RecurrenceDescriptor::isFirstOrderRecurrence( 691 PHINode *Phi, Loop *TheLoop, 692 DenseMap<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) { 693 694 // Ensure the phi node is in the loop header and has two incoming values. 695 if (Phi->getParent() != TheLoop->getHeader() || 696 Phi->getNumIncomingValues() != 2) 697 return false; 698 699 // Ensure the loop has a preheader and a single latch block. The loop 700 // vectorizer will need the latch to set up the next iteration of the loop. 701 auto *Preheader = TheLoop->getLoopPreheader(); 702 auto *Latch = TheLoop->getLoopLatch(); 703 if (!Preheader || !Latch) 704 return false; 705 706 // Ensure the phi node's incoming blocks are the loop preheader and latch. 707 if (Phi->getBasicBlockIndex(Preheader) < 0 || 708 Phi->getBasicBlockIndex(Latch) < 0) 709 return false; 710 711 // Get the previous value. The previous value comes from the latch edge while 712 // the initial value comes form the preheader edge. 713 auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch)); 714 if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) || 715 SinkAfter.count(Previous)) // Cannot rely on dominance due to motion. 716 return false; 717 718 // Ensure every user of the phi node is dominated by the previous value. 719 // The dominance requirement ensures the loop vectorizer will not need to 720 // vectorize the initial value prior to the first iteration of the loop. 721 // TODO: Consider extending this sinking to handle memory instructions and 722 // phis with multiple users. 723 724 // Returns true, if all users of I are dominated by DominatedBy. 725 auto allUsesDominatedBy = [DT](Instruction *I, Instruction *DominatedBy) { 726 return all_of(I->uses(), [DT, DominatedBy](Use &U) { 727 return DT->dominates(DominatedBy, U); 728 }); 729 }; 730 731 if (Phi->hasOneUse()) { 732 Instruction *I = Phi->user_back(); 733 734 // If the user of the PHI is also the incoming value, we potentially have a 735 // reduction and which cannot be handled by sinking. 736 if (Previous == I) 737 return false; 738 739 // We cannot sink terminator instructions. 740 if (I->getParent()->getTerminator() == I) 741 return false; 742 743 // Do not try to sink an instruction multiple times (if multiple operands 744 // are first order recurrences). 745 // TODO: We can support this case, by sinking the instruction after the 746 // 'deepest' previous instruction. 747 if (SinkAfter.find(I) != SinkAfter.end()) 748 return false; 749 750 if (DT->dominates(Previous, I)) // We already are good w/o sinking. 751 return true; 752 753 // We can sink any instruction without side effects, as long as all users 754 // are dominated by the instruction we are sinking after. 755 if (I->getParent() == Phi->getParent() && !I->mayHaveSideEffects() && 756 allUsesDominatedBy(I, Previous)) { 757 SinkAfter[I] = Previous; 758 return true; 759 } 760 } 761 762 return allUsesDominatedBy(Phi, Previous); 763 } 764 765 /// This function returns the identity element (or neutral element) for 766 /// the operation K. 767 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurKind K, Type *Tp) { 768 switch (K) { 769 case RecurKind::Xor: 770 case RecurKind::Add: 771 case RecurKind::Or: 772 // Adding, Xoring, Oring zero to a number does not change it. 773 return ConstantInt::get(Tp, 0); 774 case RecurKind::Mul: 775 // Multiplying a number by 1 does not change it. 776 return ConstantInt::get(Tp, 1); 777 case RecurKind::And: 778 // AND-ing a number with an all-1 value does not change it. 779 return ConstantInt::get(Tp, -1, true); 780 case RecurKind::FMul: 781 // Multiplying a number by 1 does not change it. 782 return ConstantFP::get(Tp, 1.0L); 783 case RecurKind::FAdd: 784 // Adding zero to a number does not change it. 785 return ConstantFP::get(Tp, 0.0L); 786 case RecurKind::UMin: 787 return ConstantInt::get(Tp, -1); 788 case RecurKind::UMax: 789 return ConstantInt::get(Tp, 0); 790 case RecurKind::SMin: 791 return ConstantInt::get(Tp, 792 APInt::getSignedMaxValue(Tp->getIntegerBitWidth())); 793 case RecurKind::SMax: 794 return ConstantInt::get(Tp, 795 APInt::getSignedMinValue(Tp->getIntegerBitWidth())); 796 case RecurKind::FMin: 797 return ConstantFP::getInfinity(Tp, true); 798 case RecurKind::FMax: 799 return ConstantFP::getInfinity(Tp, false); 800 default: 801 llvm_unreachable("Unknown recurrence kind"); 802 } 803 } 804 805 unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) { 806 switch (Kind) { 807 case RecurKind::Add: 808 return Instruction::Add; 809 case RecurKind::Mul: 810 return Instruction::Mul; 811 case RecurKind::Or: 812 return Instruction::Or; 813 case RecurKind::And: 814 return Instruction::And; 815 case RecurKind::Xor: 816 return Instruction::Xor; 817 case RecurKind::FMul: 818 return Instruction::FMul; 819 case RecurKind::FAdd: 820 return Instruction::FAdd; 821 case RecurKind::SMax: 822 case RecurKind::SMin: 823 case RecurKind::UMax: 824 case RecurKind::UMin: 825 return Instruction::ICmp; 826 case RecurKind::FMax: 827 case RecurKind::FMin: 828 return Instruction::FCmp; 829 default: 830 llvm_unreachable("Unknown recurrence operation"); 831 } 832 } 833 834 SmallVector<Instruction *, 4> 835 RecurrenceDescriptor::getReductionOpChain(PHINode *Phi, Loop *L) const { 836 SmallVector<Instruction *, 4> ReductionOperations; 837 unsigned RedOp = getOpcode(Kind); 838 839 // Search down from the Phi to the LoopExitInstr, looking for instructions 840 // with a single user of the correct type for the reduction. 841 842 // Note that we check that the type of the operand is correct for each item in 843 // the chain, including the last (the loop exit value). This can come up from 844 // sub, which would otherwise be treated as an add reduction. MinMax also need 845 // to check for a pair of icmp/select, for which we use getNextInstruction and 846 // isCorrectOpcode functions to step the right number of instruction, and 847 // check the icmp/select pair. 848 // FIXME: We also do not attempt to look through Phi/Select's yet, which might 849 // be part of the reduction chain, or attempt to looks through And's to find a 850 // smaller bitwidth. Subs are also currently not allowed (which are usually 851 // treated as part of a add reduction) as they are expected to generally be 852 // more expensive than out-of-loop reductions, and need to be costed more 853 // carefully. 854 unsigned ExpectedUses = 1; 855 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) 856 ExpectedUses = 2; 857 858 auto getNextInstruction = [&](Instruction *Cur) { 859 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) { 860 // We are expecting a icmp/select pair, which we go to the next select 861 // instruction if we can. We already know that Cur has 2 uses. 862 if (isa<SelectInst>(*Cur->user_begin())) 863 return cast<Instruction>(*Cur->user_begin()); 864 else 865 return cast<Instruction>(*std::next(Cur->user_begin())); 866 } 867 return cast<Instruction>(*Cur->user_begin()); 868 }; 869 auto isCorrectOpcode = [&](Instruction *Cur) { 870 if (RedOp == Instruction::ICmp || RedOp == Instruction::FCmp) { 871 Value *LHS, *RHS; 872 return SelectPatternResult::isMinOrMax( 873 matchSelectPattern(Cur, LHS, RHS).Flavor); 874 } 875 return Cur->getOpcode() == RedOp; 876 }; 877 878 // The loop exit instruction we check first (as a quick test) but add last. We 879 // check the opcode is correct (and dont allow them to be Subs) and that they 880 // have expected to have the expected number of uses. They will have one use 881 // from the phi and one from a LCSSA value, no matter the type. 882 if (!isCorrectOpcode(LoopExitInstr) || !LoopExitInstr->hasNUses(2)) 883 return {}; 884 885 // Check that the Phi has one (or two for min/max) uses. 886 if (!Phi->hasNUses(ExpectedUses)) 887 return {}; 888 Instruction *Cur = getNextInstruction(Phi); 889 890 // Each other instruction in the chain should have the expected number of uses 891 // and be the correct opcode. 892 while (Cur != LoopExitInstr) { 893 if (!isCorrectOpcode(Cur) || !Cur->hasNUses(ExpectedUses)) 894 return {}; 895 896 ReductionOperations.push_back(Cur); 897 Cur = getNextInstruction(Cur); 898 } 899 900 ReductionOperations.push_back(Cur); 901 return ReductionOperations; 902 } 903 904 InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K, 905 const SCEV *Step, BinaryOperator *BOp, 906 SmallVectorImpl<Instruction *> *Casts) 907 : StartValue(Start), IK(K), Step(Step), InductionBinOp(BOp) { 908 assert(IK != IK_NoInduction && "Not an induction"); 909 910 // Start value type should match the induction kind and the value 911 // itself should not be null. 912 assert(StartValue && "StartValue is null"); 913 assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) && 914 "StartValue is not a pointer for pointer induction"); 915 assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) && 916 "StartValue is not an integer for integer induction"); 917 918 // Check the Step Value. It should be non-zero integer value. 919 assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) && 920 "Step value is zero"); 921 922 assert((IK != IK_PtrInduction || getConstIntStepValue()) && 923 "Step value should be constant for pointer induction"); 924 assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) && 925 "StepValue is not an integer"); 926 927 assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) && 928 "StepValue is not FP for FpInduction"); 929 assert((IK != IK_FpInduction || 930 (InductionBinOp && 931 (InductionBinOp->getOpcode() == Instruction::FAdd || 932 InductionBinOp->getOpcode() == Instruction::FSub))) && 933 "Binary opcode should be specified for FP induction"); 934 935 if (Casts) { 936 for (auto &Inst : *Casts) { 937 RedundantCasts.push_back(Inst); 938 } 939 } 940 } 941 942 ConstantInt *InductionDescriptor::getConstIntStepValue() const { 943 if (isa<SCEVConstant>(Step)) 944 return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue()); 945 return nullptr; 946 } 947 948 bool InductionDescriptor::isFPInductionPHI(PHINode *Phi, const Loop *TheLoop, 949 ScalarEvolution *SE, 950 InductionDescriptor &D) { 951 952 // Here we only handle FP induction variables. 953 assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type"); 954 955 if (TheLoop->getHeader() != Phi->getParent()) 956 return false; 957 958 // The loop may have multiple entrances or multiple exits; we can analyze 959 // this phi if it has a unique entry value and a unique backedge value. 960 if (Phi->getNumIncomingValues() != 2) 961 return false; 962 Value *BEValue = nullptr, *StartValue = nullptr; 963 if (TheLoop->contains(Phi->getIncomingBlock(0))) { 964 BEValue = Phi->getIncomingValue(0); 965 StartValue = Phi->getIncomingValue(1); 966 } else { 967 assert(TheLoop->contains(Phi->getIncomingBlock(1)) && 968 "Unexpected Phi node in the loop"); 969 BEValue = Phi->getIncomingValue(1); 970 StartValue = Phi->getIncomingValue(0); 971 } 972 973 BinaryOperator *BOp = dyn_cast<BinaryOperator>(BEValue); 974 if (!BOp) 975 return false; 976 977 Value *Addend = nullptr; 978 if (BOp->getOpcode() == Instruction::FAdd) { 979 if (BOp->getOperand(0) == Phi) 980 Addend = BOp->getOperand(1); 981 else if (BOp->getOperand(1) == Phi) 982 Addend = BOp->getOperand(0); 983 } else if (BOp->getOpcode() == Instruction::FSub) 984 if (BOp->getOperand(0) == Phi) 985 Addend = BOp->getOperand(1); 986 987 if (!Addend) 988 return false; 989 990 // The addend should be loop invariant 991 if (auto *I = dyn_cast<Instruction>(Addend)) 992 if (TheLoop->contains(I)) 993 return false; 994 995 // FP Step has unknown SCEV 996 const SCEV *Step = SE->getUnknown(Addend); 997 D = InductionDescriptor(StartValue, IK_FpInduction, Step, BOp); 998 return true; 999 } 1000 1001 /// This function is called when we suspect that the update-chain of a phi node 1002 /// (whose symbolic SCEV expression sin \p PhiScev) contains redundant casts, 1003 /// that can be ignored. (This can happen when the PSCEV rewriter adds a runtime 1004 /// predicate P under which the SCEV expression for the phi can be the 1005 /// AddRecurrence \p AR; See createAddRecFromPHIWithCast). We want to find the 1006 /// cast instructions that are involved in the update-chain of this induction. 1007 /// A caller that adds the required runtime predicate can be free to drop these 1008 /// cast instructions, and compute the phi using \p AR (instead of some scev 1009 /// expression with casts). 1010 /// 1011 /// For example, without a predicate the scev expression can take the following 1012 /// form: 1013 /// (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy) 1014 /// 1015 /// It corresponds to the following IR sequence: 1016 /// %for.body: 1017 /// %x = phi i64 [ 0, %ph ], [ %add, %for.body ] 1018 /// %casted_phi = "ExtTrunc i64 %x" 1019 /// %add = add i64 %casted_phi, %step 1020 /// 1021 /// where %x is given in \p PN, 1022 /// PSE.getSCEV(%x) is equal to PSE.getSCEV(%casted_phi) under a predicate, 1023 /// and the IR sequence that "ExtTrunc i64 %x" represents can take one of 1024 /// several forms, for example, such as: 1025 /// ExtTrunc1: %casted_phi = and %x, 2^n-1 1026 /// or: 1027 /// ExtTrunc2: %t = shl %x, m 1028 /// %casted_phi = ashr %t, m 1029 /// 1030 /// If we are able to find such sequence, we return the instructions 1031 /// we found, namely %casted_phi and the instructions on its use-def chain up 1032 /// to the phi (not including the phi). 1033 static bool getCastsForInductionPHI(PredicatedScalarEvolution &PSE, 1034 const SCEVUnknown *PhiScev, 1035 const SCEVAddRecExpr *AR, 1036 SmallVectorImpl<Instruction *> &CastInsts) { 1037 1038 assert(CastInsts.empty() && "CastInsts is expected to be empty."); 1039 auto *PN = cast<PHINode>(PhiScev->getValue()); 1040 assert(PSE.getSCEV(PN) == AR && "Unexpected phi node SCEV expression"); 1041 const Loop *L = AR->getLoop(); 1042 1043 // Find any cast instructions that participate in the def-use chain of 1044 // PhiScev in the loop. 1045 // FORNOW/TODO: We currently expect the def-use chain to include only 1046 // two-operand instructions, where one of the operands is an invariant. 1047 // createAddRecFromPHIWithCasts() currently does not support anything more 1048 // involved than that, so we keep the search simple. This can be 1049 // extended/generalized as needed. 1050 1051 auto getDef = [&](const Value *Val) -> Value * { 1052 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val); 1053 if (!BinOp) 1054 return nullptr; 1055 Value *Op0 = BinOp->getOperand(0); 1056 Value *Op1 = BinOp->getOperand(1); 1057 Value *Def = nullptr; 1058 if (L->isLoopInvariant(Op0)) 1059 Def = Op1; 1060 else if (L->isLoopInvariant(Op1)) 1061 Def = Op0; 1062 return Def; 1063 }; 1064 1065 // Look for the instruction that defines the induction via the 1066 // loop backedge. 1067 BasicBlock *Latch = L->getLoopLatch(); 1068 if (!Latch) 1069 return false; 1070 Value *Val = PN->getIncomingValueForBlock(Latch); 1071 if (!Val) 1072 return false; 1073 1074 // Follow the def-use chain until the induction phi is reached. 1075 // If on the way we encounter a Value that has the same SCEV Expr as the 1076 // phi node, we can consider the instructions we visit from that point 1077 // as part of the cast-sequence that can be ignored. 1078 bool InCastSequence = false; 1079 auto *Inst = dyn_cast<Instruction>(Val); 1080 while (Val != PN) { 1081 // If we encountered a phi node other than PN, or if we left the loop, 1082 // we bail out. 1083 if (!Inst || !L->contains(Inst)) { 1084 return false; 1085 } 1086 auto *AddRec = dyn_cast<SCEVAddRecExpr>(PSE.getSCEV(Val)); 1087 if (AddRec && PSE.areAddRecsEqualWithPreds(AddRec, AR)) 1088 InCastSequence = true; 1089 if (InCastSequence) { 1090 // Only the last instruction in the cast sequence is expected to have 1091 // uses outside the induction def-use chain. 1092 if (!CastInsts.empty()) 1093 if (!Inst->hasOneUse()) 1094 return false; 1095 CastInsts.push_back(Inst); 1096 } 1097 Val = getDef(Val); 1098 if (!Val) 1099 return false; 1100 Inst = dyn_cast<Instruction>(Val); 1101 } 1102 1103 return InCastSequence; 1104 } 1105 1106 bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop, 1107 PredicatedScalarEvolution &PSE, 1108 InductionDescriptor &D, bool Assume) { 1109 Type *PhiTy = Phi->getType(); 1110 1111 // Handle integer and pointer inductions variables. 1112 // Now we handle also FP induction but not trying to make a 1113 // recurrent expression from the PHI node in-place. 1114 1115 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() && 1116 !PhiTy->isDoubleTy() && !PhiTy->isHalfTy()) 1117 return false; 1118 1119 if (PhiTy->isFloatingPointTy()) 1120 return isFPInductionPHI(Phi, TheLoop, PSE.getSE(), D); 1121 1122 const SCEV *PhiScev = PSE.getSCEV(Phi); 1123 const auto *AR = dyn_cast<SCEVAddRecExpr>(PhiScev); 1124 1125 // We need this expression to be an AddRecExpr. 1126 if (Assume && !AR) 1127 AR = PSE.getAsAddRec(Phi); 1128 1129 if (!AR) { 1130 LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n"); 1131 return false; 1132 } 1133 1134 // Record any Cast instructions that participate in the induction update 1135 const auto *SymbolicPhi = dyn_cast<SCEVUnknown>(PhiScev); 1136 // If we started from an UnknownSCEV, and managed to build an addRecurrence 1137 // only after enabling Assume with PSCEV, this means we may have encountered 1138 // cast instructions that required adding a runtime check in order to 1139 // guarantee the correctness of the AddRecurrence respresentation of the 1140 // induction. 1141 if (PhiScev != AR && SymbolicPhi) { 1142 SmallVector<Instruction *, 2> Casts; 1143 if (getCastsForInductionPHI(PSE, SymbolicPhi, AR, Casts)) 1144 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR, &Casts); 1145 } 1146 1147 return isInductionPHI(Phi, TheLoop, PSE.getSE(), D, AR); 1148 } 1149 1150 bool InductionDescriptor::isInductionPHI( 1151 PHINode *Phi, const Loop *TheLoop, ScalarEvolution *SE, 1152 InductionDescriptor &D, const SCEV *Expr, 1153 SmallVectorImpl<Instruction *> *CastsToIgnore) { 1154 Type *PhiTy = Phi->getType(); 1155 // We only handle integer and pointer inductions variables. 1156 if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy()) 1157 return false; 1158 1159 // Check that the PHI is consecutive. 1160 const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi); 1161 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev); 1162 1163 if (!AR) { 1164 LLVM_DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n"); 1165 return false; 1166 } 1167 1168 if (AR->getLoop() != TheLoop) { 1169 // FIXME: We should treat this as a uniform. Unfortunately, we 1170 // don't currently know how to handled uniform PHIs. 1171 LLVM_DEBUG( 1172 dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n"); 1173 return false; 1174 } 1175 1176 Value *StartValue = 1177 Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader()); 1178 1179 BasicBlock *Latch = AR->getLoop()->getLoopLatch(); 1180 if (!Latch) 1181 return false; 1182 BinaryOperator *BOp = 1183 dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch)); 1184 1185 const SCEV *Step = AR->getStepRecurrence(*SE); 1186 // Calculate the pointer stride and check if it is consecutive. 1187 // The stride may be a constant or a loop invariant integer value. 1188 const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step); 1189 if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop)) 1190 return false; 1191 1192 if (PhiTy->isIntegerTy()) { 1193 D = InductionDescriptor(StartValue, IK_IntInduction, Step, BOp, 1194 CastsToIgnore); 1195 return true; 1196 } 1197 1198 assert(PhiTy->isPointerTy() && "The PHI must be a pointer"); 1199 // Pointer induction should be a constant. 1200 if (!ConstStep) 1201 return false; 1202 1203 ConstantInt *CV = ConstStep->getValue(); 1204 Type *PointerElementType = PhiTy->getPointerElementType(); 1205 // The pointer stride cannot be determined if the pointer element type is not 1206 // sized. 1207 if (!PointerElementType->isSized()) 1208 return false; 1209 1210 const DataLayout &DL = Phi->getModule()->getDataLayout(); 1211 int64_t Size = static_cast<int64_t>(DL.getTypeAllocSize(PointerElementType)); 1212 if (!Size) 1213 return false; 1214 1215 int64_t CVSize = CV->getSExtValue(); 1216 if (CVSize % Size) 1217 return false; 1218 auto *StepValue = 1219 SE->getConstant(CV->getType(), CVSize / Size, true /* signed */); 1220 D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue, BOp); 1221 return true; 1222 } 1223