Lines Matching +full:se +full:- +full:neg
1 //===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
13 //===----------------------------------------------------------------------===//
56 ScalarEvolution *SE;
66 SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,
70 : L(Loop), LI(LI), SE(SE), DT(DT), TTI(TTI), Rewriter(Rewriter),
79 /// specified induction variable. This is the top-level driver that applies
139 switch (UseInst->getOpcode()) {
146 if (IVOperand != UseInst->getOperand(OperIdx) ||
147 !isa<ConstantInt>(UseInst->getOperand(1)))
153 || !isa<ConstantInt>(IVOperand->getOperand(1)))
156 IVSrc = IVOperand->getOperand(0);
158 assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");
160 ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));
161 if (UseInst->getOpcode() == Instruction::LShr) {
163 uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();
164 if (D->getValue().uge(BitWidth))
167 D = ConstantInt::get(UseInst->getContext(),
168 APInt::getOneBitSet(BitWidth, D->getZExtValue()));
170 const auto *LHS = SE->getSCEV(IVSrc);
171 const auto *RHS = SE->getSCEV(D);
172 FoldedExpr = SE->getUDivExpr(LHS, RHS);
175 if (UseInst->isExact() && LHS != SE->getMulExpr(FoldedExpr, RHS))
179 if (!SE->isSCEVable(UseInst->getType()))
183 if (SE->getSCEV(UseInst) != FoldedExpr)
187 << " -> " << *UseInst << '\n');
189 UseInst->setOperand(OperIdx, IVSrc);
190 assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");
193 UseInst->dropPoisonGeneratingFlags();
197 if (IVOperand->use_empty())
204 auto *Preheader = L->getLoopPreheader();
208 ICmpInst::Predicate Pred = ICmp->getPredicate();
209 if (IVOperand != ICmp->getOperand(0)) {
211 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
218 const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
219 const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
220 const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
221 auto LIP = SE->getLoopInvariantPredicate(Pred, S, X, L, ICmp);
224 ICmpInst::Predicate InvariantPredicate = LIP->Pred;
225 const SCEV *InvariantLHS = LIP->LHS;
226 const SCEV *InvariantRHS = LIP->RHS;
229 auto *PHTerm = Preheader->getTerminator();
236 Rewriter.expandCodeFor(InvariantLHS, IVOperand->getType(), PHTerm);
238 Rewriter.expandCodeFor(InvariantRHS, IVOperand->getType(), PHTerm);
240 ICmp->setPredicate(InvariantPredicate);
241 ICmp->setOperand(0, NewLHS);
242 ICmp->setOperand(1, NewRHS);
252 ICmpInst::Predicate Pred = ICmp->getPredicate();
254 if (IVOperand != ICmp->getOperand(0)) {
256 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");
263 const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
264 const SCEV *S = SE->getSCEVAtScope(ICmp->getOperand(IVOperIdx), ICmpLoop);
265 const SCEV *X = SE->getSCEVAtScope(ICmp->getOperand(1 - IVOperIdx), ICmpLoop);
270 for (auto *U : ICmp->users())
273 if (auto Ev = SE->evaluatePredicateAt(Pred, S, X, CtxI)) {
274 SE->forgetValue(ICmp);
275 ICmp->replaceAllUsesWith(ConstantInt::getBool(ICmp->getContext(), *Ev));
281 SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {
284 // optimizations. If we find out that we compare two non-negative values,
287 assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");
290 ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));
300 auto *N = SE->getSCEV(SDiv->getOperand(0));
301 auto *D = SE->getSCEV(SDiv->getOperand(1));
304 const Loop *L = LI->getLoopFor(SDiv->getParent());
305 N = SE->getSCEVAtScope(N, L);
306 D = SE->getSCEVAtScope(D, L);
308 // Replace sdiv by udiv if both of the operands are non-negative
309 if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {
311 BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),
312 SDiv->getName() + ".udiv", SDiv->getIterator());
313 UDiv->setIsExact(SDiv->isExact());
314 SDiv->replaceAllUsesWith(UDiv);
315 UDiv->setDebugLoc(SDiv->getDebugLoc());
326 // i %s n -> i %u n if i >= 0 and n >= 0
328 auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
330 Rem->getName() + ".urem", Rem->getIterator());
331 Rem->replaceAllUsesWith(URem);
332 URem->setDebugLoc(Rem->getDebugLoc());
339 // i % n --> i if i is in [0,n).
341 Rem->replaceAllUsesWith(Rem->getOperand(0));
348 // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).
350 auto *T = Rem->getType();
351 auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);
352 ICmpInst *ICmp = new ICmpInst(Rem->getIterator(), ICmpInst::ICMP_EQ, N, D);
354 SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem->getIterator());
355 Rem->replaceAllUsesWith(Sel);
356 Sel->setDebugLoc(Rem->getDebugLoc());
368 auto *NValue = Rem->getOperand(0);
369 auto *DValue = Rem->getOperand(1);
377 const SCEV *N = SE->getSCEV(NValue);
380 const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
381 N = SE->getSCEVAtScope(N, ICmpLoop);
383 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(N);
389 const SCEV *D = SE->getSCEV(DValue);
390 D = SE->getSCEVAtScope(D, ICmpLoop);
394 if (SE->isKnownPredicate(LT, N, D)) {
399 auto *T = Rem->getType();
400 const auto *NLessOne = SE->getMinusSCEV(N, SE->getOne(T));
401 if (SE->isKnownPredicate(LT, NLessOne, D)) {
407 // Try to replace SRem with URem, if both N and D are known non-negative.
409 if (!IsSigned || !SE->isKnownNonNegative(D))
416 const SCEV *LHS = SE->getSCEV(WO->getLHS());
417 const SCEV *RHS = SE->getSCEV(WO->getRHS());
418 if (!SE->willNotOverflow(WO->getBinaryOp(), WO->isSigned(), LHS, RHS))
425 WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), "", WO->getIterator());
427 if (WO->isSigned())
428 NewResult->setHasNoSignedWrap(true);
430 NewResult->setHasNoUnsignedWrap(true);
434 for (auto *U : WO->users()) {
436 if (EVI->getIndices()[0] == 1)
437 EVI->replaceAllUsesWith(ConstantInt::getFalse(WO->getContext()));
439 assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");
440 EVI->replaceAllUsesWith(NewResult);
441 NewResult->setDebugLoc(EVI->getDebugLoc());
448 EVI->eraseFromParent();
450 if (WO->use_empty())
451 WO->eraseFromParent();
458 const SCEV *LHS = SE->getSCEV(SI->getLHS());
459 const SCEV *RHS = SE->getSCEV(SI->getRHS());
460 if (!SE->willNotOverflow(SI->getBinaryOp(), SI->isSigned(), LHS, RHS))
464 SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI->getIterator());
465 if (SI->isSigned())
466 BO->setHasNoSignedWrap();
468 BO->setHasNoUnsignedWrap();
470 SI->replaceAllUsesWith(BO);
471 BO->setDebugLoc(SI->getDebugLoc());
494 Value *IV = TI->getOperand(0);
495 Type *IVTy = IV->getType();
496 const SCEV *IVSCEV = SE->getSCEV(IV);
497 const SCEV *TISCEV = SE->getSCEV(TI);
503 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
505 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
516 for (auto *U : TI->users()) {
519 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
523 assert(L->contains(ICI->getParent()) && "LCSSA form broken?");
524 if (!(ICI->getOperand(0) == TI && L->isLoopInvariant(ICI->getOperand(1))) &&
525 !(ICI->getOperand(1) == TI && L->isLoopInvariant(ICI->getOperand(0))))
528 if (ICI->isSigned() && !DoesSExtCollapse)
530 if (ICI->isUnsigned() && !DoesZExtCollapse)
538 if (ICI->isUnsigned())
544 if (ICI->isEquality())
546 // Otherwise we can only use zext when comparing two non-negative or two
548 // check for a negative value, because zext(trunc(x)) is non-negative. So
549 // it only make sense to check for non-negativity here.
550 const SCEV *SCEVOP1 = SE->getSCEV(ICI->getOperand(0));
551 const SCEV *SCEVOP2 = SE->getSCEV(ICI->getOperand(1));
552 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
556 bool IsSwapped = L->isLoopInvariant(ICI->getOperand(0));
557 auto *Op1 = IsSwapped ? ICI->getOperand(0) : ICI->getOperand(1);
566 ICmpInst::Predicate Pred = ICI->getPredicate();
578 L->makeLoopInvariant(Ext, Changed);
581 ICI->replaceAllUsesWith(NewCmp);
586 TI->replaceAllUsesWith(PoisonValue::get(TI->getType()));
592 /// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,
601 bool IsSRem = Bin->getOpcode() == Instruction::SRem;
602 if (IsSRem || Bin->getOpcode() == Instruction::URem) {
607 if (Bin->getOpcode() == Instruction::SDiv)
630 if (auto *BB = L->getLoopPreheader())
631 return BB->getTerminator();
638 if (!SE->isSCEVable(I->getType()))
642 const SCEV *S = SE->getSCEV(I);
644 if (!SE->isLoopInvariant(S, L))
655 << " with non-speculable loop invariant: " << *S << '\n');
659 auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);
661 if (!LI->replacementPreservesLCSSAForm(I, Invariant))
664 I->replaceAllUsesWith(Invariant);
671 formLCSSAForInstructions(NeedsLCSSAPhis, *DT, *LI, SE);
683 if (UseInst->getOpcode() != CastInst::SIToFP &&
684 UseInst->getOpcode() != CastInst::UIToFP)
687 Instruction *IVOperand = cast<Instruction>(UseInst->getOperand(0));
689 const SCEV *IV = SE->getSCEV(IVOperand);
691 if (UseInst->getOpcode() == CastInst::SIToFP)
692 MaskBits = (int)SE->getSignedRange(IV).getMinSignedBits();
694 MaskBits = (int)SE->getUnsignedRange(IV).getActiveBits();
695 int DestNumSigBits = UseInst->getType()->getFPMantissaWidth();
697 for (User *U : UseInst->users()) {
703 CastInst::CastOps Opcode = CI->getOpcode();
708 if (IVOperand->getType() != CI->getType()) {
710 StringRef Name = IVOperand->getName();
713 if (SE->getTypeSizeInBits(IVOperand->getType()) >
714 SE->getTypeSizeInBits(CI->getType())) {
715 Conv = Builder.CreateTrunc(IVOperand, CI->getType(), Name + ".trunc");
717 UseInst->getOpcode() == CastInst::UIToFP) {
718 Conv = Builder.CreateZExt(IVOperand, CI->getType(), Name + ".zext");
720 Conv = Builder.CreateSExt(IVOperand, CI->getType(), Name + ".sext");
725 CI->replaceAllUsesWith(Conv);
741 if (!SE->isSCEVable(UseInst->getType()) ||
742 UseInst->getType() != IVOperand->getType())
745 const SCEV *UseSCEV = SE->getSCEV(UseInst);
746 if (UseSCEV != SE->getSCEV(IVOperand))
768 if (!DT || !DT->dominates(IVOperand, UseInst))
771 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
777 if (!SE->canReuseInstruction(UseSCEV, IVOperand, DropPoisonGeneratingInsts))
781 I->dropPoisonGeneratingAnnotations();
786 SE->forgetValue(UseInst);
787 UseInst->replaceAllUsesWith(IVOperand);
801 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
802 /// unsigned-overflow. Returns true if anything changed, false otherwise.
805 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(
811 BO->setHasNoUnsignedWrap(ScalarEvolution::maskFlags(*Flags, SCEV::FlagNUW) ==
813 BO->setHasNoSignedWrap(ScalarEvolution::maskFlags(*Flags, SCEV::FlagNSW) ==
820 // compile-time impact, see https://bugs.llvm.org/show_bug.cgi?id=50384.
829 if (BO->getOpcode() == Instruction::Shl) {
831 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
832 for (auto *U : BO->users()) {
839 if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {
840 Shr->setIsExact(true);
855 for (User *U : Def->users()) {
867 if (!L->contains(UI))
882 /// non-recursively when the operand is already known to be a simpleIVUser.
884 static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {
885 if (!SE->isSCEVable(I->getType()))
889 const SCEV *S = SE->getSCEV(I);
893 if (AR && AR->getLoop() == L)
904 /// instructions in-place during analysis. Rather than rewriting induction
905 /// variables bottom-up from their users, it transforms a chain of IVUsers
906 /// top-down, updating the IR only when it encounters a clear optimization
912 if (!SE->isSCEVable(CurrIV->getType()))
918 // Use-def pairs if IV users waiting to be processed for CurrIV.
951 for (Use &U : UseInst->uses()) {
977 // re-queue uses of the now modified binary operator and fall
985 // Re-queue the potentially new direct uses of IVOperand.
992 V->visitCast(Cast);
995 if (isSimpleIVUser(UseInst, L, SE)) {
1010 std::pair<bool, bool> simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE,
1015 SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, TTI,
1023 bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
1026 SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");
1031 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
1033 simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, TTI, Dead, Rewriter);
1042 //===----------------------------------------------------------------------===//
1043 // Widen Induction Variables - Extend the width of an IV to cover its
1045 //===----------------------------------------------------------------------===//
1055 ScalarEvolution *SE;
1086 // A map with control-dependent ranges for post increment IV uses. The key is
1098 : std::optional<ConstantRange>(It->second);
1110 It->second = R.intersectWith(It->second);
1114 /// Record a link in the Narrow IV def-use chain along with the WideIV that
1189 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
1190 if (PHI->getIncomingValue(i) != Def)
1193 BasicBlock *InsertBB = PHI->getIncomingBlock(i);
1195 if (!DT->isReachableFromEntry(InsertBB))
1199 InsertPt = InsertBB->getTerminator();
1202 InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);
1203 InsertPt = InsertBB->getTerminator();
1215 assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");
1217 auto *L = LI->getLoopFor(DefI->getParent());
1218 assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())));
1220 for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())
1221 if (LI->getLoopFor(DTN->getBlock()) == L)
1222 return DTN->getBlock()->getTerminator();
1231 L(LI->getLoopFor(OrigPhi->getParent())), SE(SEv), DT(DTree),
1234 assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");
1243 for (const Loop *L = LI->getLoopFor(Use->getParent());
1244 L && L->getLoopPreheader() && L->isLoopInvariant(NarrowOper);
1245 L = L->getParentLoop())
1246 Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator());
1257 unsigned Opcode = DU.NarrowUse->getOpcode();
1289 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1291 : createExtendInst(NarrowUse->getOperand(0), WideType,
1293 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1295 : createExtendInst(NarrowUse->getOperand(1), WideType,
1299 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1300 NarrowBO->getName());
1303 WideBO->copyIRFlags(NarrowBO);
1315 unsigned IVOpIdx = (NarrowUse->getOperand(0) == NarrowDef) ? 0 : 1;
1332 return SE->getSignExtendExpr(S, Ty);
1333 return SE->getZeroExtendExpr(S, Ty);
1337 WideLHS = SE->getSCEV(WideDef);
1338 const SCEV *NarrowRHS = SE->getSCEV(NarrowUse->getOperand(1));
1341 const SCEV *NarrowLHS = SE->getSCEV(NarrowUse->getOperand(0));
1343 WideRHS = SE->getSCEV(WideDef);
1348 getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->getOpcode());
1360 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1362 : createExtendInst(NarrowUse->getOperand(0), WideType,
1364 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1366 : createExtendInst(NarrowUse->getOperand(1), WideType,
1370 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1371 NarrowBO->getName());
1375 WideBO->copyIRFlags(NarrowBO);
1382 return It->second;
1389 return SE->getAddExpr(LHS, RHS);
1391 return SE->getMinusSCEV(LHS, RHS);
1393 return SE->getMulExpr(LHS, RHS);
1395 return SE->getUDivExpr(LHS, RHS);
1413 : Opcode(Op->getOpcode()),
1414 Operands({Op->getOperand(0), Op->getOperand(1)}) {
1416 IsNSW = OBO->hasNoSignedWrap();
1417 IsNUW = OBO->hasNoUnsignedWrap();
1429 switch (Op->getOpcode()) {
1436 if (cast<PossiblyDisjointInst>(Op)->isDisjoint())
1437 return BinaryOp(Instruction::Add, Op->getOperand(0), Op->getOperand(1),
1442 if (ConstantInt *SA = dyn_cast<ConstantInt>(Op->getOperand(1))) {
1443 unsigned BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();
1449 if (SA->getValue().ult(BitWidth)) {
1453 // left shifting by bitwidth - 1.
1454 bool IsNUW = Op->hasNoUnsignedWrap();
1455 bool IsNSW = Op->hasNoSignedWrap() &&
1456 (IsNUW || SA->getValue().ult(BitWidth - 1));
1459 ConstantInt::get(Op->getContext(),
1460 APInt::getOneBitSet(BitWidth, SA->getZExtValue()));
1461 return BinaryOp(Instruction::Mul, Op->getOperand(0), X, IsNSW, IsNUW);
1472 /// No-wrap operations can transfer sign extension of their result to their
1483 assert((Op->Opcode == Instruction::Add || Op->Opcode == Instruction::Sub ||
1484 Op->Opcode == Instruction::Mul) &&
1489 const unsigned ExtendOperIdx = Op->Operands[0] == DU.NarrowDef ? 1 : 0;
1490 assert(Op->Operands[1 - ExtendOperIdx] == DU.NarrowDef && "bad DU");
1493 if (!(ExtKind == ExtendKind::Sign && Op->IsNSW) &&
1494 !(ExtKind == ExtendKind::Zero && Op->IsNUW)) {
1497 // For a non-negative NarrowDef, we can choose either type of
1502 if (Op->IsNSW) {
1504 } else if (Op->IsNUW) {
1510 const SCEV *ExtendOperExpr = SE->getSCEV(Op->Operands[ExtendOperIdx]);
1512 ExtendOperExpr = SE->getSignExtendExpr(ExtendOperExpr, WideType);
1514 ExtendOperExpr = SE->getZeroExtendExpr(ExtendOperExpr, WideType);
1519 // flags. This instruction may be guarded by control flow that the no-wrap
1520 // behavior depends on. Non-control-equivalent instructions can be mapped to
1523 const SCEV *lhs = SE->getSCEV(DU.WideDef);
1526 // Let's swap operands to the initial order for the case of non-commutative
1531 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, Op->Opcode));
1533 if (!AddRec || AddRec->getLoop() != L)
1545 if (!DU.NarrowUse->getType()->isIntegerTy())
1548 const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowUse);
1549 if (SE->getTypeSizeInBits(NarrowExpr->getType()) >=
1550 SE->getTypeSizeInBits(WideType)) {
1559 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1563 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1567 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1570 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1574 if (!AddRec || AddRec->getLoop() != L)
1590 Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType(), "",
1593 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1606 // - The signedness of the IV extension and comparison match
1608 // - The narrow IV is always positive (and thus its sign extension is equal
1619 if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))
1622 Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1623 unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
1624 unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1628 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1632 Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);
1633 DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
1664 const unsigned OpCode = NarrowUse->getOpcode();
1672 assert((NarrowUse->getOperand(0) == NarrowDef ||
1673 NarrowUse->getOperand(1) == NarrowDef) &&
1679 bool CanSignExtend = ExtKind == ExtendKind::Sign && OBO->hasNoSignedWrap();
1680 bool CanZeroExtend = ExtKind == ExtendKind::Zero && OBO->hasNoUnsignedWrap();
1684 // - narrow def (in case of we are widening the IV increment);
1685 // - single-input LCSSA Phis;
1686 // - comparison of the chosen type;
1687 // - extend of the chosen type (raison d'etre).
1691 for (Use &U : NarrowUse->uses()) {
1695 if (!L->contains(User)) {
1699 if (LCSSAPhi->getNumOperands() != 1)
1705 auto Pred = ICmp->getPredicate();
1721 if (!User || User->getType() != WideType)
1736 // Because InstCombine turns 'sub nuw' to 'add' losing the no-wrap flag, we
1742 const SCEV *LHS = SE->getSCEV(OBO->getOperand(0));
1743 const SCEV *RHS = SE->getSCEV(OBO->getOperand(1));
1744 // TODO: Support case for NarrowDef = NarrowUse->getOperand(1).
1745 if (NarrowUse->getOperand(0) != NarrowDef)
1747 if (!SE->isKnownNegative(RHS))
1749 bool ProvedSubNUW = SE->isKnownPredicateAt(ICmpInst::ICMP_UGE, LHS,
1750 SE->getNegativeSCEV(RHS), CtxI);
1754 // neg(zext(neg(op))), which is basically sext(op).
1759 const SCEV *Op1 = SE->getSCEV(WideDef);
1761 if (!AddRecOp1 || AddRecOp1->getLoop() != L)
1768 (NarrowUse->getOperand(0) == NarrowDef)
1770 : createExtendInst(NarrowUse->getOperand(0), WideType,
1773 (NarrowUse->getOperand(1) == NarrowDef)
1775 : createExtendInst(NarrowUse->getOperand(1), WideType,
1779 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1780 NarrowBO->getName());
1783 WideBO->copyIRFlags(NarrowBO);
1787 assert(User->getType() == WideType && "Checked before!");
1791 User->replaceAllUsesWith(WideBO);
1796 assert(User->getNumOperands() == 1 && "Checked before!");
1799 Builder.CreatePHI(WideBO->getType(), 1, User->getName() + ".wide");
1800 BasicBlock *LoopExitingBlock = User->getParent()->getSinglePredecessor();
1801 assert(LoopExitingBlock && L->contains(LoopExitingBlock) &&
1803 WidePN->addIncoming(WideBO, LoopExitingBlock);
1804 Builder.SetInsertPoint(User->getParent(),
1805 User->getParent()->getFirstInsertionPt());
1806 auto *TruncPN = Builder.CreateTrunc(WidePN, User->getType());
1807 User->replaceAllUsesWith(TruncPN);
1813 auto ExtendedOp = [&](Value * V)->Value * {
1817 return Builder.CreateZExt(V, WideBO->getType());
1819 return Builder.CreateSExt(V, WideBO->getType());
1821 auto Pred = User->getPredicate();
1822 auto *LHS = ExtendedOp(User->getOperand(0));
1823 auto *RHS = ExtendedOp(User->getOperand(1));
1825 Builder.CreateICmp(Pred, LHS, RHS, User->getName() + ".wide");
1826 User->replaceAllUsesWith(WideCmp);
1841 // This narrow use can be widened by a sext if it's non-negative or its narrow
1848 // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
1850 if (LI->getLoopFor(UsePhi->getParent()) != L) {
1854 if (UsePhi->getNumOperands() != 1)
1860 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1864 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",
1865 UsePhi->getIterator());
1866 WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1867 BasicBlock *WidePhiBB = WidePhi->getParent();
1868 IRBuilder<> Builder(WidePhiBB, WidePhiBB->getFirstInsertionPt());
1869 Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType(), "",
1871 UsePhi->replaceAllUsesWith(Trunc);
1884 if (DU.NarrowUse->getType() != WideType) {
1885 unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
1886 unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1890 NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType(), "",
1900 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1908 DU.NarrowUse->replaceAllUsesWith(NewDef);
1921 auto tryAddRecExpansion = [&]() -> Instruction* {
1941 DU.NarrowUse->hasNoUnsignedWrap() != WideInc->hasNoUnsignedWrap() ||
1942 DU.NarrowUse->hasNoSignedWrap() != WideInc->hasNoSignedWrap();
1960 if (WideAddRec.first != SE->getSCEV(WideUse)) {
1962 << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first
2002 const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
2004 SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
2005 SE->getZero(NarrowSCEV->getType()));
2006 for (User *U : NarrowDef->users()) {
2015 // We might have a control-dependent range information for this context.
2017 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
2028 /// def-use chain. After widenIVUse has processed all interesting IV users, the
2035 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
2041 ? SE->getSignExtendExpr(AddRec, WideType)
2042 : SE->getZeroExtendExpr(AddRec, WideType);
2044 assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
2049 if (!AddRec || AddRec->getLoop() != L)
2052 // An AddRec must have loop-invariant operands. Since this AddRec is
2053 // materialized by a loop header phi, the expression cannot have any post-loop
2056 SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
2057 SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&
2062 // the increment calculate control-dependent range information basing on
2066 // Control-dependent range information is later used to prove that a narrow
2075 // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
2076 // of the phi-SCC dominates the loop entry.
2077 Instruction *InsertPt = &*L->getHeader()->getFirstInsertionPt();
2085 if (ExpandInst->hasNUses(0) &&
2094 // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
2095 if (BasicBlock *LatchBlock = L->getLoopLatch()) {
2097 dyn_cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));
2099 WideIncExpr = SE->getSCEV(WideInc);
2103 cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
2105 WideInc->setDebugLoc(OrigInc->getDebugLoc());
2112 // the same opcode. It is not safe to re-use the flags from the original
2119 WideInc->setHasNoUnsignedWrap(WideInc->hasNoUnsignedWrap() ||
2120 OrigInc->hasNoUnsignedWrap());
2121 WideInc->setHasNoSignedWrap(WideInc->hasNoSignedWrap() ||
2122 OrigInc->hasNoSignedWrap());
2130 // Traverse the def-use chain using a worklist starting at the original IV.
2139 // Process a def-use edge. This may replace the use, so don't hold a
2143 // Follow all def-use edges from the previous narrow use.
2147 // widenIVUse may have removed the def-use edge.
2148 if (DU.NarrowDef->use_empty())
2158 /// Calculates control-dependent range for the given def at the given context
2166 !NarrowDefRHS->isNonNegative())
2180 auto CmpRHSRange = SE->getSignedRange(SE->getSCEV(CmpRHS));
2193 for (Instruction &I : make_range(Ctx->getIterator().getReverse(),
2194 Ctx->getParent()->rend())) {
2203 BasicBlock *NarrowUserBB = NarrowUser->getParent();
2206 if (!DT->isReachableFromEntry(NarrowUserBB))
2209 for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();
2210 L->contains(DTB->getBlock());
2211 DTB = DTB->getIDom()) {
2212 auto *BB = DTB->getBlock();
2213 auto *TI = BB->getTerminator();
2217 if (!BI || !BI->isConditional())
2220 auto *TrueSuccessor = BI->getSuccessor(0);
2221 auto *FalseSuccessor = BI->getSuccessor(1);
2225 DT->dominates(BBE, NarrowUser->getParent());
2229 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);
2232 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);
2246 for (Use &U : NarrowDef->uses()) {
2250 auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];
2251 if (!NarrowUserLoop || !L->contains(NarrowUserLoop))
2265 LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter,
2269 WidenIV Widener(WI, LI, SE, DT, DeadInsts, HasGuards, UsePostIncrementRanges);