1 //===- llvm/Analysis/IVDescriptors.cpp - IndVar Descriptors -----*- C++ -*-===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
30 #define DEBUG_TYPE "iv-descriptors"
34   for (const Use &Use : I->operands())  in areAllUsesIn()
64 /// Determines if Phi may have been type-promoted. If Phi has a single user
71   if (!Phi->hasOneUse())  in lookThroughAnd()
75   Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());  in lookThroughAnd()
77   // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT  in lookThroughAnd()
82       RT = IntegerType::get(Phi->getContext(), Bits);  in lookThroughAnd()
98   const DataLayout &DL = Exit->getDataLayout();  in computeRecurrenceType()
99   uint64_t MaxBitWidth = DL.getTypeSizeInBits(Exit->getType());  in computeRecurrenceType()
107     auto Mask = DB->getDemandedBits(Exit);  in computeRecurrenceType()
108     MaxBitWidth = Mask.getBitWidth() - Mask.countl_zero();  in computeRecurrenceType()
111   if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {  in computeRecurrenceType()
116     auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());  in computeRecurrenceType()
117     MaxBitWidth = NumTypeBits - NumSignBits;  in computeRecurrenceType()
120       // If the value is not known to be non-negative, we set IsSigned to true,  in computeRecurrenceType()
125       // will get properly sign-extended.  in computeRecurrenceType()
131   return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),  in computeRecurrenceType()
147   MinWidthCastToRecurTy = -1U;  in collectCastInstrs()
153       if (Cast->getSrcTy() == RecurrenceType) {  in collectCastInstrs()
160       if (Cast->getDestTy() == RecurrenceType) {  in collectCastInstrs()
163         // when finding the widest type for in-loop reductions without any  in collectCastInstrs()
166             MinWidthCastToRecurTy, Cast->getSrcTy()->getScalarSizeInBits());  in collectCastInstrs()
170     // Add all operands to the work list if they are loop-varying values that  in collectCastInstrs()
172     for (Value *O : cast<User>(Val)->operands())  in collectCastInstrs()
174         if (TheLoop->contains(I) && !Visited.count(I))  in collectCastInstrs()
187   if (Kind == RecurKind::FAdd && Exit->getOpcode() != Instruction::FAdd)  in checkOrderedReduction()
195   if (Exit != ExactFPMathInst || Exit->hasNUsesOrMore(3))  in checkOrderedReduction()
200   auto *Op0 = Exit->getOperand(0);  in checkOrderedReduction()
201   auto *Op1 = Exit->getOperand(1);  in checkOrderedReduction()
204   if (Kind == RecurKind::FMulAdd && Exit->getOperand(2) != Phi)  in checkOrderedReduction()
217   if (Phi->getNumIncomingValues() != 2)  in AddReductionVar()
221   if (Phi->getParent() != TheLoop->getHeader())  in AddReductionVar()
226   Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());  in AddReductionVar()
244   // variables (such as ADD). We must have a single out-of-block user. The cycle  in AddReductionVar()
248   // To recognize min/max patterns formed by a icmp select sequence, we store  in AddReductionVar()
249   // the number of instruction we saw from the recognized min/max pattern,  in AddReductionVar()
254   // Data used for determining if the recurrence has been type-promoted.  in AddReductionVar()
255   Type *RecurrenceType = Phi->getType();  in AddReductionVar()
269   if (RecurrenceType->isFloatingPointTy()) {  in AddReductionVar()
272   } else if (RecurrenceType->isIntegerTy()) {  in AddReductionVar()
278     // Pointer min/max may exist, but it is not supported as a reduction op.  in AddReductionVar()
289   // The first instruction in the use-def chain of the Phi node that requires  in AddReductionVar()
294   //  - By the reduction:  in AddReductionVar()
295   //      - Reduction operation:  in AddReductionVar()
296   //        - One use of reduction value (safe).  in AddReductionVar()
297   //        - Multiple use of reduction value (not safe).  in AddReductionVar()
298   //      - PHI:  in AddReductionVar()
299   //        - All uses of the PHI must be the reduction (safe).  in AddReductionVar()
300   //        - Otherwise, not safe.  in AddReductionVar()
301   //  - By instructions outside of the loop (safe).  in AddReductionVar()
304   //  - By store instructions with a loop invariant address (safe with  in AddReductionVar()
308   //  - By an instruction that is not part of the reduction (not safe).  in AddReductionVar()
313     Instruction *Cur = Worklist.pop_back_val();  in AddReductionVar()  local
317     if (auto *SI = dyn_cast<StoreInst>(Cur)) {  in AddReductionVar()
324       const SCEV *PtrScev = SE->getSCEV(SI->getPointerOperand());  in AddReductionVar()
328             SE->getSCEV(IntermediateStore->getPointerOperand());  in AddReductionVar()
332                             << "inside the loop: " << *SI->getPointerOperand()  in AddReductionVar()
334                             << *IntermediateStore->getPointerOperand() << '\n');  in AddReductionVar()
340       if (!SE->isLoopInvariant(PtrScev, TheLoop)) {  in AddReductionVar()
341         LLVM_DEBUG(dbgs() << "Storing reduction value to non-uniform address "  in AddReductionVar()
342                           << "inside the loop: " << *SI->getPointerOperand()  in AddReductionVar()
355     if (Cur->use_empty())  in AddReductionVar()
358     bool IsAPhi = isa<PHINode>(Cur);  in AddReductionVar()
361     if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())  in AddReductionVar()
366     if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&  in AddReductionVar()
367         !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) &&  in AddReductionVar()
368         !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))  in AddReductionVar()
373     // type-promoted).  in AddReductionVar()
374     if (Cur != Start) {  in AddReductionVar()
376           isRecurrenceInstr(TheLoop, Phi, Cur, Kind, ReduxDesc, FuncFMF);  in AddReductionVar()
384         FastMathFlags CurFMF = ReduxDesc.getPatternInst()->getFastMathFlags();  in AddReductionVar()
386           // Accept FMF on either fcmp or select of a min/max idiom.  in AddReductionVar()
387           // TODO: This is a hack to work-around the fact that FMF may not be  in AddReductionVar()
390           if (auto *FCmp = dyn_cast<FCmpInst>(Sel->getCondition()))  in AddReductionVar()
391             CurFMF |= FCmp->getFastMathFlags();  in AddReductionVar()
402     bool IsASelect = isa<SelectInst>(Cur);  in AddReductionVar()
407         hasMultipleUsesOf(Cur, VisitedInsts, 2))  in AddReductionVar()
412         !isAnyOfRecurrenceKind(Kind) && hasMultipleUsesOf(Cur, VisitedInsts, 1))  in AddReductionVar()
416     if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))  in AddReductionVar()
420         (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))  in AddReductionVar()
423         (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))  in AddReductionVar()
427     FoundReduxOp |= !IsAPhi && Cur != Start;  in AddReductionVar()
429     // Process users of current instruction. Push non-PHI nodes after PHI nodes  in AddReductionVar()
434     for (User *U : Cur->users()) {  in AddReductionVar()
440         if (Cur == UI->getOperand(0) || Cur == UI->getOperand(1))  in AddReductionVar()
444       BasicBlock *Parent = UI->getParent();  in AddReductionVar()
445       if (!TheLoop->contains(Parent)) {  in AddReductionVar()
448         if (ExitInstruction == Cur)  in AddReductionVar()
453         // previous iteration, in which case we would loose "VF-1" iterations of  in AddReductionVar()
455         if (ExitInstruction != nullptr || Cur == Phi)  in AddReductionVar()
459         // before we feed back to the reduction phi. Otherwise, we loose VF-1  in AddReductionVar()
461         if (!is_contained(Phi->operands(), Cur))  in AddReductionVar()
464         ExitInstruction = Cur;  in AddReductionVar()
469       // value must only be used once, except by phi nodes and min/max  in AddReductionVar()
477           if (SI && SI->getPointerOperand() == Cur) {  in AddReductionVar()
503   // llvm.min/max intrinsic, which is always OK.  in AddReductionVar()
515     if (!is_contained(Phi->operands(), IntermediateStore->getValueOperand())) {  in AddReductionVar()
524         IntermediateStore->getValueOperand() != ExitInstruction) {  in AddReductionVar()
534       ExitInstruction = cast<Instruction>(IntermediateStore->getValueOperand());  in AddReductionVar()
546     // arithmetic reduction to determine if it may have been type-promoted.  in AddReductionVar()
559     // type-shrinking. It does this by inserting instructions to truncate the  in AddReductionVar()
592   // only have a single instruction with out-of-loop users.  in AddReductionVar()
594   // The ExitInstruction(Instruction which is allowed to have out-of-loop users)  in AddReductionVar()
621 // any two non-constants, provided they are loop invariant. The only thing
624 // across-vector reduction after the loop simply involves choosing the start
634     if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))  in isAnyOfPattern()
645   if (OrigPhi == dyn_cast<PHINode>(SI->getTrueValue()))  in isAnyOfPattern()
646     NonPhi = SI->getFalseValue();  in isAnyOfPattern()
647   else if (OrigPhi == dyn_cast<PHINode>(SI->getFalseValue()))  in isAnyOfPattern()
648     NonPhi = SI->getTrueValue();  in isAnyOfPattern()
655   if (!Loop->isLoopInvariant(NonPhi))  in isAnyOfPattern()
658   return InstDesc(I, isa<ICmpInst>(I->getOperand(0)) ? RecurKind::IAnyOf  in isAnyOfPattern()
674     if (auto *Select = dyn_cast<SelectInst>(*I->user_begin()))  in isMinMaxPattern()
678   // Only match select with single use cmp condition, or a min/max intrinsic.  in isMinMaxPattern()
684   // Look for a min/max pattern.  in isMinMaxPattern()
713 /// Returns true if the select instruction has users in the compare-and-add
728   CmpInst *CI = dyn_cast<CmpInst>(SI->getCondition());  in isConditionalRdxPattern()
730   if (!CI || !CI->hasOneUse())  in isConditionalRdxPattern()
733   Value *TrueVal = SI->getTrueValue();  in isConditionalRdxPattern()
734   Value *FalseVal = SI->getFalseValue();  in isConditionalRdxPattern()
744   if (!I1 || !I1->isBinaryOp())  in isConditionalRdxPattern()
750          I1->isFast()) ||  in isConditionalRdxPattern()
751         (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast())) ||  in isConditionalRdxPattern()
770   switch (I->getOpcode()) {  in isRecurrenceInstr()
789                     I->hasAllowReassoc() ? nullptr : I);  in isRecurrenceInstr()
793                     I->hasAllowReassoc() ? nullptr : I);  in isRecurrenceInstr()
807      if (isa<FPMathOperator>(I) && I->hasNoNaNs() && I->hasNoSignedZeros())  in isRecurrenceInstr()
819                       I->hasAllowReassoc() ? nullptr : I);  in isRecurrenceInstr()
828   for (const Use &U : I->operands()) {  in hasMultipleUsesOf()
843   BasicBlock *Header = TheLoop->getHeader();  in isReductionPHI()
844   Function &F = *Header->getParent();  in isReductionPHI()
847       F.getFnAttribute("no-nans-fp-math").getValueAsBool());  in isReductionPHI()
849       F.getFnAttribute("no-signed-zeros-fp-math").getValueAsBool());  in isReductionPHI()
914     LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n");  in isReductionPHI()
951   if (Phi->getParent() != TheLoop->getHeader() ||  in isFixedOrderRecurrence()
952       Phi->getNumIncomingValues() != 2)  in isFixedOrderRecurrence()
957   auto *Preheader = TheLoop->getLoopPreheader();  in isFixedOrderRecurrence()
958   auto *Latch = TheLoop->getLoopLatch();  in isFixedOrderRecurrence()
963   if (Phi->getBasicBlockIndex(Preheader) < 0 ||  in isFixedOrderRecurrence()
964       Phi->getBasicBlockIndex(Latch) < 0)  in isFixedOrderRecurrence()
969   auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));  in isFixedOrderRecurrence()
972   // latch until we find a non-phi value. Use this as the new Previous, all uses  in isFixedOrderRecurrence()
974   // after the non-phi previous value.  in isFixedOrderRecurrence()
977     if (PrevPhi->getParent() != Phi->getParent())  in isFixedOrderRecurrence()
981     Previous = dyn_cast<Instruction>(PrevPhi->getIncomingValueForBlock(Latch));  in isFixedOrderRecurrence()
984   if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous))  in isFixedOrderRecurrence()
994   BasicBlock *PhiBB = Phi->getParent();  in isFixedOrderRecurrence()
1003     if (DT->dominates(Previous,  in isFixedOrderRecurrence()
1007     if (SinkCandidate->getParent() != PhiBB ||  in isFixedOrderRecurrence()
1008         SinkCandidate->mayHaveSideEffects() ||  in isFixedOrderRecurrence()
1009         SinkCandidate->mayReadFromMemory() || SinkCandidate->isTerminator())  in isFixedOrderRecurrence()
1026     for (User *User : Current->users()) {  in isFixedOrderRecurrence()
1049     // AND-ing a number with an all-1 value does not change it.  in getRecurrenceIdentity()
1050     return ConstantInt::get(Tp, -1, true);  in getRecurrenceIdentity()
1058     // use -0.0. However, this will currently result in mixed vectors of 0.0/-0.0.  in getRecurrenceIdentity()
1060     // nodes where possible, and 2) PHIs with the nsz flag + -0.0 use 0.0. This would  in getRecurrenceIdentity()
1064     return ConstantFP::get(Tp, -0.0L);  in getRecurrenceIdentity()
1066     return ConstantInt::get(Tp, -1, true);  in getRecurrenceIdentity()
1071                             APInt::getSignedMaxValue(Tp->getIntegerBitWidth()));  in getRecurrenceIdentity()
1074                             APInt::getSignedMinValue(Tp->getIntegerBitWidth()));  in getRecurrenceIdentity()
1081            "nnan, nsz is expected to be set for FP max reduction.");  in getRecurrenceIdentity()
1148   // more expensive than out-of-loop reductions, and need to be costed more  in getReductionOpChain()
1154   auto getNextInstruction = [&](Instruction *Cur) -> Instruction * {  in getReductionOpChain()  argument
1155     for (auto *User : Cur->users()) {  in getReductionOpChain()
1161         // instruction if we can. We already know that Cur has 2 uses.  in getReductionOpChain()
1170   auto isCorrectOpcode = [&](Instruction *Cur) {  in getReductionOpChain()  argument
1174           matchSelectPattern(Cur, LHS, RHS).Flavor);  in getReductionOpChain()
1177     if (isFMulAddIntrinsic(Cur))  in getReductionOpChain()
1180     return Cur->getOpcode() == RedOp;  in getReductionOpChain()
1187     if (ExitPhi->getNumIncomingValues() != 2)  in getReductionOpChain()
1190     Instruction *Inc0 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(0));  in getReductionOpChain()
1191     Instruction *Inc1 = dyn_cast<Instruction>(ExitPhi->getIncomingValue(1));  in getReductionOpChain()
1209   if (!isCorrectOpcode(RdxInstr) || !LoopExitInstr->hasNUses(2))  in getReductionOpChain()
1212   // Check that the Phi has one (or two for min/max) uses, plus an extra use  in getReductionOpChain()
1214   if (!Phi->hasNUses(ExpectedUses + ExtraPhiUses))  in getReductionOpChain()
1217   Instruction *Cur = getNextInstruction(Phi);  in getReductionOpChain()  local
1221   while (Cur != RdxInstr) {  in getReductionOpChain()
1222     if (!Cur || !isCorrectOpcode(Cur) || !Cur->hasNUses(ExpectedUses))  in getReductionOpChain()
1225     ReductionOperations.push_back(Cur);  in getReductionOpChain()
1226     Cur = getNextInstruction(Cur);  in getReductionOpChain()
1229   ReductionOperations.push_back(Cur);  in getReductionOpChain()
1242   assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&  in InductionDescriptor()
1244   assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&  in InductionDescriptor()
1247   // Check the Step Value. It should be non-zero integer value.  in InductionDescriptor()
1248   assert((!getConstIntStepValue() || !getConstIntStepValue()->isZero()) &&  in InductionDescriptor()
1251   assert((IK == IK_FpInduction || Step->getType()->isIntegerTy()) &&  in InductionDescriptor()
1254   assert((IK != IK_FpInduction || Step->getType()->isFloatingPointTy()) &&  in InductionDescriptor()
1258            (InductionBinOp->getOpcode() == Instruction::FAdd ||  in InductionDescriptor()
1259             InductionBinOp->getOpcode() == Instruction::FSub))) &&  in InductionDescriptor()
1271     return dyn_cast<ConstantInt>(cast<SCEVConstant>(Step)->getValue());  in getConstIntStepValue()
1280   assert(Phi->getType()->isFloatingPointTy() && "Unexpected Phi type");  in isFPInductionPHI()
1282   if (TheLoop->getHeader() != Phi->getParent())  in isFPInductionPHI()
1287   if (Phi->getNumIncomingValues() != 2)  in isFPInductionPHI()
1290   if (TheLoop->contains(Phi->getIncomingBlock(0))) {  in isFPInductionPHI()
1291     BEValue = Phi->getIncomingValue(0);  in isFPInductionPHI()
1292     StartValue = Phi->getIncomingValue(1);  in isFPInductionPHI()
1294     assert(TheLoop->contains(Phi->getIncomingBlock(1)) &&  in isFPInductionPHI()
1296     BEValue = Phi->getIncomingValue(1);  in isFPInductionPHI()
1297     StartValue = Phi->getIncomingValue(0);  in isFPInductionPHI()
1305   if (BOp->getOpcode() == Instruction::FAdd) {  in isFPInductionPHI()
1306     if (BOp->getOperand(0) == Phi)  in isFPInductionPHI()
1307       Addend = BOp->getOperand(1);  in isFPInductionPHI()
1308     else if (BOp->getOperand(1) == Phi)  in isFPInductionPHI()
1309       Addend = BOp->getOperand(0);  in isFPInductionPHI()
1310   } else if (BOp->getOpcode() == Instruction::FSub)  in isFPInductionPHI()
1311     if (BOp->getOperand(0) == Phi)  in isFPInductionPHI()
1312       Addend = BOp->getOperand(1);  in isFPInductionPHI()
1319     if (TheLoop->contains(I))  in isFPInductionPHI()
1323   const SCEV *Step = SE->getUnknown(Addend);  in isFPInductionPHI()
1328 /// This function is called when we suspect that the update-chain of a phi node
1333 /// cast instructions that are involved in the update-chain of this induction.
1352 ///   ExtTrunc1:    %casted_phi = and  %x, 2^n-1
1358 /// we found, namely %casted_phi and the instructions on its use-def chain up
1366   auto *PN = cast<PHINode>(PhiScev->getValue());  in getCastsForInductionPHI()
1368   const Loop *L = AR->getLoop();  in getCastsForInductionPHI()
1370   // Find any cast instructions that participate in the def-use chain of  in getCastsForInductionPHI()
1372   // FORNOW/TODO: We currently expect the def-use chain to include only  in getCastsForInductionPHI()
1373   // two-operand instructions, where one of the operands is an invariant.  in getCastsForInductionPHI()
1378   auto getDef = [&](const Value *Val) -> Value * {  in getCastsForInductionPHI()
1382     Value *Op0 = BinOp->getOperand(0);  in getCastsForInductionPHI()
1383     Value *Op1 = BinOp->getOperand(1);  in getCastsForInductionPHI()
1385     if (L->isLoopInvariant(Op0))  in getCastsForInductionPHI()
1387     else if (L->isLoopInvariant(Op1))  in getCastsForInductionPHI()
1394   BasicBlock *Latch = L->getLoopLatch();  in getCastsForInductionPHI()
1397   Value *Val = PN->getIncomingValueForBlock(Latch);  in getCastsForInductionPHI()
1401   // Follow the def-use chain until the induction phi is reached.  in getCastsForInductionPHI()
1404   // as part of the cast-sequence that can be ignored.  in getCastsForInductionPHI()
1410     if (!Inst || !L->contains(Inst)) {  in getCastsForInductionPHI()
1418       // uses outside the induction def-use chain.  in getCastsForInductionPHI()
1420         if (!Inst->hasOneUse())  in getCastsForInductionPHI()
1436   Type *PhiTy = Phi->getType();  in isInductionPHI()
1440   // recurrent expression from the PHI node in-place.  in isInductionPHI()
1442   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy() && !PhiTy->isFloatTy() &&  in isInductionPHI()
1443       !PhiTy->isDoubleTy() && !PhiTy->isHalfTy())  in isInductionPHI()
1446   if (PhiTy->isFloatingPointTy())  in isInductionPHI()
1481   Type *PhiTy = Phi->getType();  in isInductionPHI()
1483   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())  in isInductionPHI()
1487   const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);  in isInductionPHI()
1495   if (AR->getLoop() != TheLoop) {  in isInductionPHI()
1506   assert(Phi->getParent() == AR->getLoop()->getHeader()  in isInductionPHI()
1510       Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());  in isInductionPHI()
1512   BasicBlock *Latch = AR->getLoop()->getLoopLatch();  in isInductionPHI()
1516   const SCEV *Step = AR->getStepRecurrence(*SE);  in isInductionPHI()
1520   if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))  in isInductionPHI()
1523   if (PhiTy->isIntegerTy()) {  in isInductionPHI()
1525         dyn_cast<BinaryOperator>(Phi->getIncomingValueForBlock(Latch));  in isInductionPHI()
1531   assert(PhiTy->isPointerTy() && "The PHI must be a pointer");  in isInductionPHI()
1533   // This allows induction variables w/non-constant steps.  in isInductionPHI()