2283 lines · cpp
1//===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements induction variable simplification. It does10// not define any actual pass or policy, but provides a single function to11// simplify a loop's induction variables based on ScalarEvolution.12//13//===----------------------------------------------------------------------===//14 15#include "llvm/Transforms/Utils/SimplifyIndVar.h"16#include "llvm/ADT/SmallVector.h"17#include "llvm/ADT/Statistic.h"18#include "llvm/Analysis/LoopInfo.h"19#include "llvm/Analysis/ValueTracking.h"20#include "llvm/IR/Dominators.h"21#include "llvm/IR/IRBuilder.h"22#include "llvm/IR/Instructions.h"23#include "llvm/IR/IntrinsicInst.h"24#include "llvm/IR/PatternMatch.h"25#include "llvm/Support/Debug.h"26#include "llvm/Support/raw_ostream.h"27#include "llvm/Transforms/Utils/Local.h"28#include "llvm/Transforms/Utils/LoopUtils.h"29#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"30 31using namespace llvm;32using namespace llvm::PatternMatch;33 34#define DEBUG_TYPE "indvars"35 36STATISTIC(NumElimIdentity, "Number of IV identities eliminated");37STATISTIC(NumElimOperand, "Number of IV operands folded into a use");38STATISTIC(NumFoldedUser, "Number of IV users folded into a constant");39STATISTIC(NumElimRem , "Number of IV remainder operations eliminated");40STATISTIC(41 NumSimplifiedSDiv,42 "Number of IV signed division operations converted to unsigned division");43STATISTIC(44 NumSimplifiedSRem,45 "Number of IV signed remainder operations converted to unsigned remainder");46STATISTIC(NumElimCmp , "Number of IV comparisons eliminated");47 48namespace {49 /// This is a utility for simplifying induction variables50 /// based on ScalarEvolution. It is the primary instrument of the51 /// IndvarSimplify pass, but it may also be directly invoked to cleanup after52 /// other loop passes that preserve SCEV.53 class SimplifyIndvar {54 Loop *L;55 LoopInfo *LI;56 ScalarEvolution *SE;57 DominatorTree *DT;58 const TargetTransformInfo *TTI;59 SCEVExpander &Rewriter;60 SmallVectorImpl<WeakTrackingVH> &DeadInsts;61 62 bool Changed = false;63 bool RunUnswitching = false;64 65 public:66 SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, DominatorTree *DT,67 LoopInfo *LI, const TargetTransformInfo *TTI,68 SCEVExpander &Rewriter,69 SmallVectorImpl<WeakTrackingVH> &Dead)70 : L(Loop), LI(LI), SE(SE), DT(DT), TTI(TTI), Rewriter(Rewriter),71 DeadInsts(Dead) {72 assert(LI && "IV simplification requires LoopInfo");73 }74 75 bool hasChanged() const { return Changed; }76 bool runUnswitching() const { return RunUnswitching; }77 78 /// Iteratively perform simplification on a worklist of users of the79 /// specified induction variable. This is the top-level driver that applies80 /// all simplifications to users of an IV.81 void simplifyUsers(PHINode *CurrIV, IVVisitor *V = nullptr);82 83 void pushIVUsers(Instruction *Def,84 SmallPtrSet<Instruction *, 16> &Simplified,85 SmallVectorImpl<std::pair<Instruction *, Instruction *>>86 &SimpleIVUsers);87 88 Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand);89 90 bool eliminateIdentitySCEV(Instruction *UseInst, Instruction *IVOperand);91 bool replaceIVUserWithLoopInvariant(Instruction *UseInst);92 bool replaceFloatIVWithIntegerIV(Instruction *UseInst);93 94 bool eliminateOverflowIntrinsic(WithOverflowInst *WO);95 bool eliminateSaturatingIntrinsic(SaturatingInst *SI);96 bool eliminateTrunc(TruncInst *TI);97 bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand);98 bool makeIVComparisonInvariant(ICmpInst *ICmp, Instruction *IVOperand);99 void eliminateIVComparison(ICmpInst *ICmp, Instruction *IVOperand);100 void simplifyIVRemainder(BinaryOperator *Rem, Instruction *IVOperand,101 bool IsSigned);102 void replaceRemWithNumerator(BinaryOperator *Rem);103 void replaceRemWithNumeratorOrZero(BinaryOperator *Rem);104 void replaceSRemWithURem(BinaryOperator *Rem);105 bool eliminateSDiv(BinaryOperator *SDiv);106 bool strengthenBinaryOp(BinaryOperator *BO, Instruction *IVOperand);107 bool strengthenOverflowingOperation(BinaryOperator *OBO,108 Instruction *IVOperand);109 bool strengthenRightShift(BinaryOperator *BO, Instruction *IVOperand);110 };111}112 113/// Find a point in code which dominates all given instructions. We can safely114/// assume that, whatever fact we can prove at the found point, this fact is115/// also true for each of the given instructions.116static Instruction *findCommonDominator(ArrayRef<Instruction *> Instructions,117 DominatorTree &DT) {118 Instruction *CommonDom = nullptr;119 for (auto *Insn : Instructions)120 CommonDom =121 CommonDom ? DT.findNearestCommonDominator(CommonDom, Insn) : Insn;122 assert(CommonDom && "Common dominator not found?");123 return CommonDom;124}125 126/// Fold an IV operand into its use. This removes increments of an127/// aligned IV when used by a instruction that ignores the low bits.128///129/// IVOperand is guaranteed SCEVable, but UseInst may not be.130///131/// Return the operand of IVOperand for this induction variable if IVOperand can132/// be folded (in case more folding opportunities have been exposed).133/// Otherwise return null.134Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) {135 Value *IVSrc = nullptr;136 const unsigned OperIdx = 0;137 const SCEV *FoldedExpr = nullptr;138 bool MustDropExactFlag = false;139 switch (UseInst->getOpcode()) {140 default:141 return nullptr;142 case Instruction::UDiv:143 case Instruction::LShr:144 // We're only interested in the case where we know something about145 // the numerator and have a constant denominator.146 if (IVOperand != UseInst->getOperand(OperIdx) ||147 !isa<ConstantInt>(UseInst->getOperand(1)))148 return nullptr;149 150 // Attempt to fold a binary operator with constant operand.151 // e.g. ((I + 1) >> 2) => I >> 2152 if (!isa<BinaryOperator>(IVOperand)153 || !isa<ConstantInt>(IVOperand->getOperand(1)))154 return nullptr;155 156 IVSrc = IVOperand->getOperand(0);157 // IVSrc must be the (SCEVable) IV, since the other operand is const.158 assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand");159 160 ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1));161 if (UseInst->getOpcode() == Instruction::LShr) {162 // Get a constant for the divisor. See createSCEV.163 uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth();164 if (D->getValue().uge(BitWidth))165 return nullptr;166 167 D = ConstantInt::get(UseInst->getContext(),168 APInt::getOneBitSet(BitWidth, D->getZExtValue()));169 }170 const SCEV *LHS = SE->getSCEV(IVSrc);171 const SCEV *RHS = SE->getSCEV(D);172 FoldedExpr = SE->getUDivExpr(LHS, RHS);173 // We might have 'exact' flag set at this point which will no longer be174 // correct after we make the replacement.175 if (UseInst->isExact() && LHS != SE->getMulExpr(FoldedExpr, RHS))176 MustDropExactFlag = true;177 }178 // We have something that might fold it's operand. Compare SCEVs.179 if (!SE->isSCEVable(UseInst->getType()))180 return nullptr;181 182 // Bypass the operand if SCEV can prove it has no effect.183 if (SE->getSCEV(UseInst) != FoldedExpr)184 return nullptr;185 186 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand187 << " -> " << *UseInst << '\n');188 189 UseInst->setOperand(OperIdx, IVSrc);190 assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper");191 192 if (MustDropExactFlag)193 UseInst->dropPoisonGeneratingFlags();194 195 ++NumElimOperand;196 Changed = true;197 if (IVOperand->use_empty())198 DeadInsts.emplace_back(IVOperand);199 return IVSrc;200}201 202bool SimplifyIndvar::makeIVComparisonInvariant(ICmpInst *ICmp,203 Instruction *IVOperand) {204 auto *Preheader = L->getLoopPreheader();205 if (!Preheader)206 return false;207 unsigned IVOperIdx = 0;208 CmpPredicate Pred = ICmp->getCmpPredicate();209 if (IVOperand != ICmp->getOperand(0)) {210 // Swapped211 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");212 IVOperIdx = 1;213 Pred = ICmpInst::getSwappedCmpPredicate(Pred);214 }215 216 // Get the SCEVs for the ICmp operands (in the specific context of the217 // current loop)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);222 if (!LIP)223 return false;224 ICmpInst::Predicate InvariantPredicate = LIP->Pred;225 const SCEV *InvariantLHS = LIP->LHS;226 const SCEV *InvariantRHS = LIP->RHS;227 228 // Do not generate something ridiculous.229 auto *PHTerm = Preheader->getTerminator();230 if (Rewriter.isHighCostExpansion({InvariantLHS, InvariantRHS}, L,231 2 * SCEVCheapExpansionBudget, TTI, PHTerm) ||232 !Rewriter.isSafeToExpandAt(InvariantLHS, PHTerm) ||233 !Rewriter.isSafeToExpandAt(InvariantRHS, PHTerm))234 return false;235 auto *NewLHS =236 Rewriter.expandCodeFor(InvariantLHS, IVOperand->getType(), PHTerm);237 auto *NewRHS =238 Rewriter.expandCodeFor(InvariantRHS, IVOperand->getType(), PHTerm);239 LLVM_DEBUG(dbgs() << "INDVARS: Simplified comparison: " << *ICmp << '\n');240 ICmp->setPredicate(InvariantPredicate);241 ICmp->setOperand(0, NewLHS);242 ICmp->setOperand(1, NewRHS);243 RunUnswitching = true;244 return true;245}246 247/// SimplifyIVUsers helper for eliminating useless248/// comparisons against an induction variable.249void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp,250 Instruction *IVOperand) {251 unsigned IVOperIdx = 0;252 CmpPredicate Pred = ICmp->getCmpPredicate();253 ICmpInst::Predicate OriginalPred = Pred;254 if (IVOperand != ICmp->getOperand(0)) {255 // Swapped256 assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand");257 IVOperIdx = 1;258 Pred = ICmpInst::getSwappedCmpPredicate(Pred);259 }260 261 // Get the SCEVs for the ICmp operands (in the specific context of the262 // current loop)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);266 267 // If the condition is always true or always false in the given context,268 // replace it with a constant value.269 SmallVector<Instruction *, 4> Users;270 for (auto *U : ICmp->users())271 Users.push_back(cast<Instruction>(U));272 const Instruction *CtxI = findCommonDominator(Users, *DT);273 if (auto Ev = SE->evaluatePredicateAt(Pred, S, X, CtxI)) {274 SE->forgetValue(ICmp);275 ICmp->replaceAllUsesWith(ConstantInt::getBool(ICmp->getContext(), *Ev));276 DeadInsts.emplace_back(ICmp);277 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');278 } else if (makeIVComparisonInvariant(ICmp, IVOperand)) {279 // fallthrough to end of function280 } else if (ICmpInst::isSigned(OriginalPred) &&281 SE->isKnownNonNegative(S) && SE->isKnownNonNegative(X)) {282 // If we were unable to make anything above, all we can is to canonicalize283 // the comparison hoping that it will open the doors for other284 // optimizations. If we find out that we compare two non-negative values,285 // we turn the instruction's predicate to its unsigned version. Note that286 // we cannot rely on Pred here unless we check if we have swapped it.287 assert(ICmp->getPredicate() == OriginalPred && "Predicate changed?");288 LLVM_DEBUG(dbgs() << "INDVARS: Turn to unsigned comparison: " << *ICmp289 << '\n');290 ICmp->setPredicate(ICmpInst::getUnsignedPredicate(OriginalPred));291 ICmp->setSameSign();292 } else293 return;294 295 ++NumElimCmp;296 Changed = true;297}298 299bool SimplifyIndvar::eliminateSDiv(BinaryOperator *SDiv) {300 // Get the SCEVs for the ICmp operands.301 const SCEV *N = SE->getSCEV(SDiv->getOperand(0));302 const SCEV *D = SE->getSCEV(SDiv->getOperand(1));303 304 // Simplify unnecessary loops away.305 const Loop *L = LI->getLoopFor(SDiv->getParent());306 N = SE->getSCEVAtScope(N, L);307 D = SE->getSCEVAtScope(D, L);308 309 // Replace sdiv by udiv if both of the operands are non-negative310 if (SE->isKnownNonNegative(N) && SE->isKnownNonNegative(D)) {311 auto *UDiv = BinaryOperator::Create(312 BinaryOperator::UDiv, SDiv->getOperand(0), SDiv->getOperand(1),313 SDiv->getName() + ".udiv", SDiv->getIterator());314 UDiv->setIsExact(SDiv->isExact());315 SDiv->replaceAllUsesWith(UDiv);316 UDiv->setDebugLoc(SDiv->getDebugLoc());317 LLVM_DEBUG(dbgs() << "INDVARS: Simplified sdiv: " << *SDiv << '\n');318 ++NumSimplifiedSDiv;319 Changed = true;320 DeadInsts.push_back(SDiv);321 return true;322 }323 324 return false;325}326 327// i %s n -> i %u n if i >= 0 and n >= 0328void SimplifyIndvar::replaceSRemWithURem(BinaryOperator *Rem) {329 auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);330 auto *URem = BinaryOperator::Create(BinaryOperator::URem, N, D,331 Rem->getName() + ".urem", Rem->getIterator());332 Rem->replaceAllUsesWith(URem);333 URem->setDebugLoc(Rem->getDebugLoc());334 LLVM_DEBUG(dbgs() << "INDVARS: Simplified srem: " << *Rem << '\n');335 ++NumSimplifiedSRem;336 Changed = true;337 DeadInsts.emplace_back(Rem);338}339 340// i % n --> i if i is in [0,n).341void SimplifyIndvar::replaceRemWithNumerator(BinaryOperator *Rem) {342 Rem->replaceAllUsesWith(Rem->getOperand(0));343 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');344 ++NumElimRem;345 Changed = true;346 DeadInsts.emplace_back(Rem);347}348 349// (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).350void SimplifyIndvar::replaceRemWithNumeratorOrZero(BinaryOperator *Rem) {351 auto *T = Rem->getType();352 auto *N = Rem->getOperand(0), *D = Rem->getOperand(1);353 ICmpInst *ICmp = new ICmpInst(Rem->getIterator(), ICmpInst::ICMP_EQ, N, D);354 ICmp->setDebugLoc(Rem->getDebugLoc());355 SelectInst *Sel =356 SelectInst::Create(ICmp, ConstantInt::get(T, 0), N, "iv.rem", Rem->getIterator());357 Rem->replaceAllUsesWith(Sel);358 Sel->setDebugLoc(Rem->getDebugLoc());359 LLVM_DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');360 ++NumElimRem;361 Changed = true;362 DeadInsts.emplace_back(Rem);363}364 365/// SimplifyIVUsers helper for eliminating useless remainder operations366/// operating on an induction variable or replacing srem by urem.367void SimplifyIndvar::simplifyIVRemainder(BinaryOperator *Rem,368 Instruction *IVOperand,369 bool IsSigned) {370 auto *NValue = Rem->getOperand(0);371 auto *DValue = Rem->getOperand(1);372 // We're only interested in the case where we know something about373 // the numerator, unless it is a srem, because we want to replace srem by urem374 // in general.375 bool UsedAsNumerator = IVOperand == NValue;376 if (!UsedAsNumerator && !IsSigned)377 return;378 379 const SCEV *N = SE->getSCEV(NValue);380 381 // Simplify unnecessary loops away.382 const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());383 N = SE->getSCEVAtScope(N, ICmpLoop);384 385 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(N);386 387 // Do not proceed if the Numerator may be negative388 if (!IsNumeratorNonNegative)389 return;390 391 const SCEV *D = SE->getSCEV(DValue);392 D = SE->getSCEVAtScope(D, ICmpLoop);393 394 if (UsedAsNumerator) {395 auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;396 if (SE->isKnownPredicate(LT, N, D)) {397 replaceRemWithNumerator(Rem);398 return;399 }400 401 auto *T = Rem->getType();402 const SCEV *NLessOne = SE->getMinusSCEV(N, SE->getOne(T));403 if (SE->isKnownPredicate(LT, NLessOne, D)) {404 replaceRemWithNumeratorOrZero(Rem);405 return;406 }407 }408 409 // Try to replace SRem with URem, if both N and D are known non-negative.410 // Since we had already check N, we only need to check D now411 if (!IsSigned || !SE->isKnownNonNegative(D))412 return;413 414 replaceSRemWithURem(Rem);415}416 417bool SimplifyIndvar::eliminateOverflowIntrinsic(WithOverflowInst *WO) {418 const SCEV *LHS = SE->getSCEV(WO->getLHS());419 const SCEV *RHS = SE->getSCEV(WO->getRHS());420 if (!SE->willNotOverflow(WO->getBinaryOp(), WO->isSigned(), LHS, RHS))421 return false;422 423 // Proved no overflow, nuke the overflow check and, if possible, the overflow424 // intrinsic as well.425 426 BinaryOperator *NewResult = BinaryOperator::Create(427 WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), "", WO->getIterator());428 429 if (WO->isSigned())430 NewResult->setHasNoSignedWrap(true);431 else432 NewResult->setHasNoUnsignedWrap(true);433 434 SmallVector<ExtractValueInst *, 4> ToDelete;435 436 for (auto *U : WO->users()) {437 if (auto *EVI = dyn_cast<ExtractValueInst>(U)) {438 if (EVI->getIndices()[0] == 1)439 EVI->replaceAllUsesWith(ConstantInt::getFalse(WO->getContext()));440 else {441 assert(EVI->getIndices()[0] == 0 && "Only two possibilities!");442 EVI->replaceAllUsesWith(NewResult);443 NewResult->setDebugLoc(EVI->getDebugLoc());444 }445 ToDelete.push_back(EVI);446 }447 }448 449 for (auto *EVI : ToDelete)450 EVI->eraseFromParent();451 452 if (WO->use_empty())453 WO->eraseFromParent();454 455 Changed = true;456 return true;457}458 459bool SimplifyIndvar::eliminateSaturatingIntrinsic(SaturatingInst *SI) {460 const SCEV *LHS = SE->getSCEV(SI->getLHS());461 const SCEV *RHS = SE->getSCEV(SI->getRHS());462 if (!SE->willNotOverflow(SI->getBinaryOp(), SI->isSigned(), LHS, RHS))463 return false;464 465 BinaryOperator *BO = BinaryOperator::Create(466 SI->getBinaryOp(), SI->getLHS(), SI->getRHS(), SI->getName(), SI->getIterator());467 if (SI->isSigned())468 BO->setHasNoSignedWrap();469 else470 BO->setHasNoUnsignedWrap();471 472 SI->replaceAllUsesWith(BO);473 BO->setDebugLoc(SI->getDebugLoc());474 DeadInsts.emplace_back(SI);475 Changed = true;476 return true;477}478 479bool SimplifyIndvar::eliminateTrunc(TruncInst *TI) {480 // It is always legal to replace481 // icmp <pred> i32 trunc(iv), n482 // with483 // icmp <pred> i64 sext(trunc(iv)), sext(n), if pred is signed predicate.484 // Or with485 // icmp <pred> i64 zext(trunc(iv)), zext(n), if pred is unsigned predicate.486 // Or with either of these if pred is an equality predicate.487 //488 // If we can prove that iv == sext(trunc(iv)) or iv == zext(trunc(iv)) for489 // every comparison which uses trunc, it means that we can replace each of490 // them with comparison of iv against sext/zext(n). We no longer need trunc491 // after that.492 //493 // TODO: Should we do this if we can widen *some* comparisons, but not all494 // of them? Sometimes it is enough to enable other optimizations, but the495 // trunc instruction will stay in the loop.496 Value *IV = TI->getOperand(0);497 Type *IVTy = IV->getType();498 const SCEV *IVSCEV = SE->getSCEV(IV);499 const SCEV *TISCEV = SE->getSCEV(TI);500 501 // Check if iv == zext(trunc(iv)) and if iv == sext(trunc(iv)). If so, we can502 // get rid of trunc503 bool DoesSExtCollapse = false;504 bool DoesZExtCollapse = false;505 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))506 DoesSExtCollapse = true;507 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))508 DoesZExtCollapse = true;509 510 // If neither sext nor zext does collapse, it is not profitable to do any511 // transform. Bail.512 if (!DoesSExtCollapse && !DoesZExtCollapse)513 return false;514 515 // Collect users of the trunc that look like comparisons against invariants.516 // Bail if we find something different.517 SmallVector<ICmpInst *, 4> ICmpUsers;518 for (auto *U : TI->users()) {519 // We don't care about users in unreachable blocks.520 if (isa<Instruction>(U) &&521 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))522 continue;523 ICmpInst *ICI = dyn_cast<ICmpInst>(U);524 if (!ICI) return false;525 assert(L->contains(ICI->getParent()) && "LCSSA form broken?");526 if (!(ICI->getOperand(0) == TI && L->isLoopInvariant(ICI->getOperand(1))) &&527 !(ICI->getOperand(1) == TI && L->isLoopInvariant(ICI->getOperand(0))))528 return false;529 // If we cannot get rid of trunc, bail.530 if (ICI->isSigned() && !DoesSExtCollapse)531 return false;532 if (ICI->isUnsigned() && !DoesZExtCollapse)533 return false;534 // For equality, either signed or unsigned works.535 ICmpUsers.push_back(ICI);536 }537 538 auto CanUseZExt = [&](ICmpInst *ICI) {539 // Unsigned comparison can be widened as unsigned.540 if (ICI->isUnsigned())541 return true;542 // Is it profitable to do zext?543 if (!DoesZExtCollapse)544 return false;545 // For equality, we can safely zext both parts.546 if (ICI->isEquality())547 return true;548 // Otherwise we can only use zext when comparing two non-negative or two549 // negative values. But in practice, we will never pass DoesZExtCollapse550 // check for a negative value, because zext(trunc(x)) is non-negative. So551 // it only make sense to check for non-negativity here.552 const SCEV *SCEVOP1 = SE->getSCEV(ICI->getOperand(0));553 const SCEV *SCEVOP2 = SE->getSCEV(ICI->getOperand(1));554 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);555 };556 // Replace all comparisons against trunc with comparisons against IV.557 for (auto *ICI : ICmpUsers) {558 bool IsSwapped = L->isLoopInvariant(ICI->getOperand(0));559 auto *Op1 = IsSwapped ? ICI->getOperand(0) : ICI->getOperand(1);560 IRBuilder<> Builder(ICI);561 Value *Ext = nullptr;562 // For signed/unsigned predicate, replace the old comparison with comparison563 // of immediate IV against sext/zext of the invariant argument. If we can564 // use either sext or zext (i.e. we are dealing with equality predicate),565 // then prefer zext as a more canonical form.566 // TODO: If we see a signed comparison which can be turned into unsigned,567 // we can do it here for canonicalization purposes.568 ICmpInst::Predicate Pred = ICI->getPredicate();569 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);570 if (CanUseZExt(ICI)) {571 assert(DoesZExtCollapse && "Unprofitable zext?");572 Ext = Builder.CreateZExt(Op1, IVTy, "zext");573 Pred = ICmpInst::getUnsignedPredicate(Pred);574 } else {575 assert(DoesSExtCollapse && "Unprofitable sext?");576 Ext = Builder.CreateSExt(Op1, IVTy, "sext");577 assert(Pred == ICmpInst::getSignedPredicate(Pred) && "Must be signed!");578 }579 bool Changed;580 L->makeLoopInvariant(Ext, Changed);581 (void)Changed;582 auto *NewCmp = Builder.CreateICmp(Pred, IV, Ext);583 ICI->replaceAllUsesWith(NewCmp);584 DeadInsts.emplace_back(ICI);585 }586 587 // Trunc no longer needed.588 TI->replaceAllUsesWith(PoisonValue::get(TI->getType()));589 DeadInsts.emplace_back(TI);590 return true;591}592 593/// Eliminate an operation that consumes a simple IV and has no observable594/// side-effect given the range of IV values. IVOperand is guaranteed SCEVable,595/// but UseInst may not be.596bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst,597 Instruction *IVOperand) {598 if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {599 eliminateIVComparison(ICmp, IVOperand);600 return true;601 }602 if (BinaryOperator *Bin = dyn_cast<BinaryOperator>(UseInst)) {603 bool IsSRem = Bin->getOpcode() == Instruction::SRem;604 if (IsSRem || Bin->getOpcode() == Instruction::URem) {605 simplifyIVRemainder(Bin, IVOperand, IsSRem);606 return true;607 }608 609 if (Bin->getOpcode() == Instruction::SDiv)610 return eliminateSDiv(Bin);611 }612 613 if (auto *WO = dyn_cast<WithOverflowInst>(UseInst))614 if (eliminateOverflowIntrinsic(WO))615 return true;616 617 if (auto *SI = dyn_cast<SaturatingInst>(UseInst))618 if (eliminateSaturatingIntrinsic(SI))619 return true;620 621 if (auto *TI = dyn_cast<TruncInst>(UseInst))622 if (eliminateTrunc(TI))623 return true;624 625 if (eliminateIdentitySCEV(UseInst, IVOperand))626 return true;627 628 return false;629}630 631static Instruction *GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint) {632 if (auto *BB = L->getLoopPreheader())633 return BB->getTerminator();634 635 return Hint;636}637 638/// Replace the UseInst with a loop invariant expression if it is safe.639bool SimplifyIndvar::replaceIVUserWithLoopInvariant(Instruction *I) {640 if (!SE->isSCEVable(I->getType()))641 return false;642 643 // Get the symbolic expression for this instruction.644 const SCEV *S = SE->getSCEV(I);645 646 if (!SE->isLoopInvariant(S, L))647 return false;648 649 // Do not generate something ridiculous even if S is loop invariant.650 if (Rewriter.isHighCostExpansion(S, L, SCEVCheapExpansionBudget, TTI, I))651 return false;652 653 auto *IP = GetLoopInvariantInsertPosition(L, I);654 655 if (!Rewriter.isSafeToExpandAt(S, IP)) {656 LLVM_DEBUG(dbgs() << "INDVARS: Can not replace IV user: " << *I657 << " with non-speculable loop invariant: " << *S << '\n');658 return false;659 }660 661 auto *Invariant = Rewriter.expandCodeFor(S, I->getType(), IP);662 bool NeedToEmitLCSSAPhis = false;663 if (!LI->replacementPreservesLCSSAForm(I, Invariant))664 NeedToEmitLCSSAPhis = true;665 666 I->replaceAllUsesWith(Invariant);667 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *I668 << " with loop invariant: " << *S << '\n');669 670 if (NeedToEmitLCSSAPhis) {671 SmallVector<Instruction *, 1> NeedsLCSSAPhis;672 NeedsLCSSAPhis.push_back(cast<Instruction>(Invariant));673 formLCSSAForInstructions(NeedsLCSSAPhis, *DT, *LI, SE);674 LLVM_DEBUG(dbgs() << " INDVARS: Replacement breaks LCSSA form"675 << " inserting LCSSA Phis" << '\n');676 }677 ++NumFoldedUser;678 Changed = true;679 DeadInsts.emplace_back(I);680 return true;681}682 683/// Eliminate redundant type cast between integer and float.684bool SimplifyIndvar::replaceFloatIVWithIntegerIV(Instruction *UseInst) {685 if (UseInst->getOpcode() != CastInst::SIToFP &&686 UseInst->getOpcode() != CastInst::UIToFP)687 return false;688 689 Instruction *IVOperand = cast<Instruction>(UseInst->getOperand(0));690 // Get the symbolic expression for this instruction.691 const SCEV *IV = SE->getSCEV(IVOperand);692 int MaskBits;693 if (UseInst->getOpcode() == CastInst::SIToFP)694 MaskBits = (int)SE->getSignedRange(IV).getMinSignedBits();695 else696 MaskBits = (int)SE->getUnsignedRange(IV).getActiveBits();697 int DestNumSigBits = UseInst->getType()->getFPMantissaWidth();698 if (MaskBits <= DestNumSigBits) {699 for (User *U : UseInst->users()) {700 // Match for fptosi/fptoui of sitofp and with same type.701 auto *CI = dyn_cast<CastInst>(U);702 if (!CI)703 continue;704 705 CastInst::CastOps Opcode = CI->getOpcode();706 if (Opcode != CastInst::FPToSI && Opcode != CastInst::FPToUI)707 continue;708 709 Value *Conv = nullptr;710 if (IVOperand->getType() != CI->getType()) {711 IRBuilder<> Builder(CI);712 StringRef Name = IVOperand->getName();713 // To match InstCombine logic, we only need sext if both fptosi and714 // sitofp are used. If one of them is unsigned, then we can use zext.715 if (SE->getTypeSizeInBits(IVOperand->getType()) >716 SE->getTypeSizeInBits(CI->getType())) {717 Conv = Builder.CreateTrunc(IVOperand, CI->getType(), Name + ".trunc");718 } else if (Opcode == CastInst::FPToUI ||719 UseInst->getOpcode() == CastInst::UIToFP) {720 Conv = Builder.CreateZExt(IVOperand, CI->getType(), Name + ".zext");721 } else {722 Conv = Builder.CreateSExt(IVOperand, CI->getType(), Name + ".sext");723 }724 } else725 Conv = IVOperand;726 727 CI->replaceAllUsesWith(Conv);728 DeadInsts.push_back(CI);729 LLVM_DEBUG(dbgs() << "INDVARS: Replace IV user: " << *CI730 << " with: " << *Conv << '\n');731 732 ++NumFoldedUser;733 Changed = true;734 }735 }736 737 return Changed;738}739 740/// Eliminate any operation that SCEV can prove is an identity function.741bool SimplifyIndvar::eliminateIdentitySCEV(Instruction *UseInst,742 Instruction *IVOperand) {743 if (!SE->isSCEVable(UseInst->getType()) ||744 UseInst->getType() != IVOperand->getType())745 return false;746 747 const SCEV *UseSCEV = SE->getSCEV(UseInst);748 if (UseSCEV != SE->getSCEV(IVOperand))749 return false;750 751 // getSCEV(X) == getSCEV(Y) does not guarantee that X and Y are related in the752 // dominator tree, even if X is an operand to Y. For instance, in753 //754 // %iv = phi i32 {0,+,1}755 // br %cond, label %left, label %merge756 //757 // left:758 // %X = add i32 %iv, 0759 // br label %merge760 //761 // merge:762 // %M = phi (%X, %iv)763 //764 // getSCEV(%M) == getSCEV(%X) == {0,+,1}, but %X does not dominate %M, and765 // %M.replaceAllUsesWith(%X) would be incorrect.766 767 if (isa<PHINode>(UseInst))768 // If UseInst is not a PHI node then we know that IVOperand dominates769 // UseInst directly from the legality of SSA.770 if (!DT || !DT->dominates(IVOperand, UseInst))771 return false;772 773 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))774 return false;775 776 // Make sure the operand is not more poisonous than the instruction.777 if (!impliesPoison(IVOperand, UseInst)) {778 SmallVector<Instruction *> DropPoisonGeneratingInsts;779 if (!SE->canReuseInstruction(UseSCEV, IVOperand, DropPoisonGeneratingInsts))780 return false;781 782 for (Instruction *I : DropPoisonGeneratingInsts)783 I->dropPoisonGeneratingAnnotations();784 }785 786 LLVM_DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n');787 788 SE->forgetValue(UseInst);789 UseInst->replaceAllUsesWith(IVOperand);790 ++NumElimIdentity;791 Changed = true;792 DeadInsts.emplace_back(UseInst);793 return true;794}795 796bool SimplifyIndvar::strengthenBinaryOp(BinaryOperator *BO,797 Instruction *IVOperand) {798 return (isa<OverflowingBinaryOperator>(BO) &&799 strengthenOverflowingOperation(BO, IVOperand)) ||800 (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand));801}802 803/// Annotate BO with nsw / nuw if it provably does not signed-overflow /804/// unsigned-overflow. Returns true if anything changed, false otherwise.805bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,806 Instruction *IVOperand) {807 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(808 cast<OverflowingBinaryOperator>(BO));809 810 if (!Flags)811 return false;812 813 BO->setHasNoUnsignedWrap(ScalarEvolution::maskFlags(*Flags, SCEV::FlagNUW) ==814 SCEV::FlagNUW);815 BO->setHasNoSignedWrap(ScalarEvolution::maskFlags(*Flags, SCEV::FlagNSW) ==816 SCEV::FlagNSW);817 818 // The getStrengthenedNoWrapFlagsFromBinOp() check inferred additional nowrap819 // flags on addrecs while performing zero/sign extensions. We could call820 // forgetValue() here to make sure those flags also propagate to any other821 // SCEV expressions based on the addrec. However, this can have pathological822 // compile-time impact, see https://bugs.llvm.org/show_bug.cgi?id=50384.823 return true;824}825 826/// Annotate the Shr in (X << IVOperand) >> C as exact using the827/// information from the IV's range. Returns true if anything changed, false828/// otherwise.829bool SimplifyIndvar::strengthenRightShift(BinaryOperator *BO,830 Instruction *IVOperand) {831 if (BO->getOpcode() == Instruction::Shl) {832 bool Changed = false;833 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));834 for (auto *U : BO->users()) {835 const APInt *C;836 if (match(U,837 m_AShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C))) ||838 match(U,839 m_LShr(m_Shl(m_Value(), m_Specific(IVOperand)), m_APInt(C)))) {840 BinaryOperator *Shr = cast<BinaryOperator>(U);841 if (!Shr->isExact() && IVRange.getUnsignedMin().uge(*C)) {842 Shr->setIsExact(true);843 Changed = true;844 }845 }846 }847 return Changed;848 }849 850 return false;851}852 853/// Add all uses of Def to the current IV's worklist.854void SimplifyIndvar::pushIVUsers(855 Instruction *Def, SmallPtrSet<Instruction *, 16> &Simplified,856 SmallVectorImpl<std::pair<Instruction *, Instruction *>> &SimpleIVUsers) {857 for (User *U : Def->users()) {858 Instruction *UI = cast<Instruction>(U);859 860 // Avoid infinite or exponential worklist processing.861 // Also ensure unique worklist users.862 // If Def is a LoopPhi, it may not be in the Simplified set, so check for863 // self edges first.864 if (UI == Def)865 continue;866 867 // Only change the current Loop, do not change the other parts (e.g. other868 // Loops).869 if (!L->contains(UI))870 continue;871 872 // Do not push the same instruction more than once.873 if (!Simplified.insert(UI).second)874 continue;875 876 SimpleIVUsers.push_back(std::make_pair(UI, Def));877 }878}879 880/// Return true if this instruction generates a simple SCEV881/// expression in terms of that IV.882///883/// This is similar to IVUsers' isInteresting() but processes each instruction884/// non-recursively when the operand is already known to be a simpleIVUser.885///886static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) {887 if (!SE->isSCEVable(I->getType()))888 return false;889 890 // Get the symbolic expression for this instruction.891 const SCEV *S = SE->getSCEV(I);892 893 // Only consider affine recurrences.894 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S);895 if (AR && AR->getLoop() == L)896 return true;897 898 return false;899}900 901/// Iteratively perform simplification on a worklist of users902/// of the specified induction variable. Each successive simplification may push903/// more users which may themselves be candidates for simplification.904///905/// This algorithm does not require IVUsers analysis. Instead, it simplifies906/// instructions in-place during analysis. Rather than rewriting induction907/// variables bottom-up from their users, it transforms a chain of IVUsers908/// top-down, updating the IR only when it encounters a clear optimization909/// opportunity.910///911/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.912///913void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {914 if (!SE->isSCEVable(CurrIV->getType()))915 return;916 917 // Instructions processed by SimplifyIndvar for CurrIV.918 SmallPtrSet<Instruction*,16> Simplified;919 920 // Use-def pairs if IV users waiting to be processed for CurrIV.921 SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers;922 923 // Push users of the current LoopPhi. In rare cases, pushIVUsers may be924 // called multiple times for the same LoopPhi. This is the proper thing to925 // do for loop header phis that use each other.926 pushIVUsers(CurrIV, Simplified, SimpleIVUsers);927 928 while (!SimpleIVUsers.empty()) {929 std::pair<Instruction*, Instruction*> UseOper =930 SimpleIVUsers.pop_back_val();931 Instruction *UseInst = UseOper.first;932 933 // If a user of the IndVar is trivially dead, we prefer just to mark it dead934 // rather than try to do some complex analysis or transformation (such as935 // widening) basing on it.936 // TODO: Propagate TLI and pass it here to handle more cases.937 if (isInstructionTriviallyDead(UseInst, /* TLI */ nullptr)) {938 DeadInsts.emplace_back(UseInst);939 continue;940 }941 942 // Bypass back edges to avoid extra work.943 if (UseInst == CurrIV) continue;944 945 // Try to replace UseInst with a loop invariant before any other946 // simplifications.947 if (replaceIVUserWithLoopInvariant(UseInst))948 continue;949 950 // Go further for the bitcast 'prtoint ptr to i64' or if the cast is done951 // by truncation952 if ((isa<PtrToIntInst>(UseInst)) || (isa<TruncInst>(UseInst)))953 for (Use &U : UseInst->uses()) {954 Instruction *User = cast<Instruction>(U.getUser());955 if (replaceIVUserWithLoopInvariant(User))956 break; // done replacing957 }958 959 Instruction *IVOperand = UseOper.second;960 for (unsigned N = 0; IVOperand; ++N) {961 assert(N <= Simplified.size() && "runaway iteration");962 (void) N;963 964 Value *NewOper = foldIVUser(UseInst, IVOperand);965 if (!NewOper)966 break; // done folding967 IVOperand = dyn_cast<Instruction>(NewOper);968 }969 if (!IVOperand)970 continue;971 972 if (eliminateIVUser(UseInst, IVOperand)) {973 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);974 continue;975 }976 977 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(UseInst)) {978 if (strengthenBinaryOp(BO, IVOperand)) {979 // re-queue uses of the now modified binary operator and fall980 // through to the checks that remain.981 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);982 }983 }984 985 // Try to use integer induction for FPToSI of float induction directly.986 if (replaceFloatIVWithIntegerIV(UseInst)) {987 // Re-queue the potentially new direct uses of IVOperand.988 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);989 continue;990 }991 992 CastInst *Cast = dyn_cast<CastInst>(UseInst);993 if (V && Cast) {994 V->visitCast(Cast);995 continue;996 }997 if (isSimpleIVUser(UseInst, L, SE)) {998 pushIVUsers(UseInst, Simplified, SimpleIVUsers);999 }1000 }1001}1002 1003namespace llvm {1004 1005void IVVisitor::anchor() { }1006 1007/// Simplify instructions that use this induction variable1008/// by using ScalarEvolution to analyze the IV's recurrence.1009/// Returns a pair where the first entry indicates that the function makes1010/// changes and the second entry indicates that it introduced new opportunities1011/// for loop unswitching.1012std::pair<bool, bool> simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE,1013 DominatorTree *DT, LoopInfo *LI,1014 const TargetTransformInfo *TTI,1015 SmallVectorImpl<WeakTrackingVH> &Dead,1016 SCEVExpander &Rewriter, IVVisitor *V) {1017 SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, DT, LI, TTI,1018 Rewriter, Dead);1019 SIV.simplifyUsers(CurrIV, V);1020 return {SIV.hasChanged(), SIV.runUnswitching()};1021}1022 1023/// Simplify users of induction variables within this1024/// loop. This does not actually change or add IVs.1025bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT,1026 LoopInfo *LI, const TargetTransformInfo *TTI,1027 SmallVectorImpl<WeakTrackingVH> &Dead) {1028 SCEVExpander Rewriter(*SE, SE->getDataLayout(), "indvars");1029#if LLVM_ENABLE_ABI_BREAKING_CHECKS1030 Rewriter.setDebugType(DEBUG_TYPE);1031#endif1032 bool Changed = false;1033 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {1034 const auto &[C, _] =1035 simplifyUsersOfIV(cast<PHINode>(I), SE, DT, LI, TTI, Dead, Rewriter);1036 Changed |= C;1037 }1038 return Changed;1039}1040 1041} // namespace llvm1042 1043namespace {1044//===----------------------------------------------------------------------===//1045// Widen Induction Variables - Extend the width of an IV to cover its1046// widest uses.1047//===----------------------------------------------------------------------===//1048 1049class WidenIV {1050 // Parameters1051 PHINode *OrigPhi;1052 Type *WideType;1053 1054 // Context1055 LoopInfo *LI;1056 Loop *L;1057 ScalarEvolution *SE;1058 DominatorTree *DT;1059 1060 // Does the module have any calls to the llvm.experimental.guard intrinsic1061 // at all? If not we can avoid scanning instructions looking for guards.1062 bool HasGuards;1063 1064 bool UsePostIncrementRanges;1065 1066 // Statistics1067 unsigned NumElimExt = 0;1068 unsigned NumWidened = 0;1069 1070 // Result1071 PHINode *WidePhi = nullptr;1072 Instruction *WideInc = nullptr;1073 const SCEV *WideIncExpr = nullptr;1074 SmallVectorImpl<WeakTrackingVH> &DeadInsts;1075 1076 SmallPtrSet<Instruction *,16> Widened;1077 1078 enum class ExtendKind { Zero, Sign, Unknown };1079 1080 // A map tracking the kind of extension used to widen each narrow IV1081 // and narrow IV user.1082 // Key: pointer to a narrow IV or IV user.1083 // Value: the kind of extension used to widen this Instruction.1084 DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;1085 1086 using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;1087 1088 // A map with control-dependent ranges for post increment IV uses. The key is1089 // a pair of IV def and a use of this def denoting the context. The value is1090 // a ConstantRange representing possible values of the def at the given1091 // context.1092 DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;1093 1094 std::optional<ConstantRange> getPostIncRangeInfo(Value *Def,1095 Instruction *UseI) {1096 DefUserPair Key(Def, UseI);1097 auto It = PostIncRangeInfos.find(Key);1098 return It == PostIncRangeInfos.end()1099 ? std::optional<ConstantRange>(std::nullopt)1100 : std::optional<ConstantRange>(It->second);1101 }1102 1103 void calculatePostIncRanges(PHINode *OrigPhi);1104 void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);1105 1106 void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {1107 DefUserPair Key(Def, UseI);1108 auto [It, Inserted] = PostIncRangeInfos.try_emplace(Key, R);1109 if (!Inserted)1110 It->second = R.intersectWith(It->second);1111 }1112 1113public:1114 /// Record a link in the Narrow IV def-use chain along with the WideIV that1115 /// computes the same value as the Narrow IV def. This avoids caching Use*1116 /// pointers.1117 struct NarrowIVDefUse {1118 Instruction *NarrowDef = nullptr;1119 Instruction *NarrowUse = nullptr;1120 Instruction *WideDef = nullptr;1121 1122 // True if the narrow def is never negative. Tracking this information lets1123 // us use a sign extension instead of a zero extension or vice versa, when1124 // profitable and legal.1125 bool NeverNegative = false;1126 1127 NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD,1128 bool NeverNegative)1129 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),1130 NeverNegative(NeverNegative) {}1131 };1132 1133 WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,1134 DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,1135 bool HasGuards, bool UsePostIncrementRanges = true);1136 1137 PHINode *createWideIV(SCEVExpander &Rewriter);1138 1139 unsigned getNumElimExt() { return NumElimExt; };1140 unsigned getNumWidened() { return NumWidened; };1141 1142protected:1143 Value *createExtendInst(Value *NarrowOper, Type *WideType, bool IsSigned,1144 Instruction *Use);1145 1146 Instruction *cloneIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR);1147 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,1148 const SCEVAddRecExpr *WideAR);1149 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);1150 1151 ExtendKind getExtendKind(Instruction *I);1152 1153 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;1154 1155 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);1156 1157 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);1158 1159 const SCEV *getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,1160 unsigned OpCode) const;1161 1162 Instruction *widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter,1163 PHINode *OrigPhi, PHINode *WidePhi);1164 void truncateIVUse(NarrowIVDefUse DU);1165 1166 bool widenLoopCompare(NarrowIVDefUse DU);1167 bool widenWithVariantUse(NarrowIVDefUse DU);1168 1169 void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);1170 1171private:1172 SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;1173};1174} // namespace1175 1176/// Determine the insertion point for this user. By default, insert immediately1177/// before the user. SCEVExpander or LICM will hoist loop invariants out of the1178/// loop. For PHI nodes, there may be multiple uses, so compute the nearest1179/// common dominator for the incoming blocks. A nullptr can be returned if no1180/// viable location is found: it may happen if User is a PHI and Def only comes1181/// to this PHI from unreachable blocks.1182static Instruction *getInsertPointForUses(Instruction *User, Value *Def,1183 DominatorTree *DT, LoopInfo *LI) {1184 PHINode *PHI = dyn_cast<PHINode>(User);1185 if (!PHI)1186 return User;1187 1188 Instruction *InsertPt = nullptr;1189 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {1190 if (PHI->getIncomingValue(i) != Def)1191 continue;1192 1193 BasicBlock *InsertBB = PHI->getIncomingBlock(i);1194 1195 if (!DT->isReachableFromEntry(InsertBB))1196 continue;1197 1198 if (!InsertPt) {1199 InsertPt = InsertBB->getTerminator();1200 continue;1201 }1202 InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);1203 InsertPt = InsertBB->getTerminator();1204 }1205 1206 // If we have skipped all inputs, it means that Def only comes to Phi from1207 // unreachable blocks.1208 if (!InsertPt)1209 return nullptr;1210 1211 auto *DefI = dyn_cast<Instruction>(Def);1212 if (!DefI)1213 return InsertPt;1214 1215 assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");1216 1217 auto *L = LI->getLoopFor(DefI->getParent());1218 assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())));1219 1220 for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())1221 if (LI->getLoopFor(DTN->getBlock()) == L)1222 return DTN->getBlock()->getTerminator();1223 1224 llvm_unreachable("DefI dominates InsertPt!");1225}1226 1227WidenIV::WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,1228 DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,1229 bool HasGuards, bool UsePostIncrementRanges)1230 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),1231 L(LI->getLoopFor(OrigPhi->getParent())), SE(SEv), DT(DTree),1232 HasGuards(HasGuards), UsePostIncrementRanges(UsePostIncrementRanges),1233 DeadInsts(DI) {1234 assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");1235 ExtendKindMap[OrigPhi] = WI.IsSigned ? ExtendKind::Sign : ExtendKind::Zero;1236}1237 1238Value *WidenIV::createExtendInst(Value *NarrowOper, Type *WideType,1239 bool IsSigned, Instruction *Use) {1240 // Set the debug location and conservative insertion point.1241 IRBuilder<> Builder(Use);1242 // Hoist the insertion point into loop preheaders as far as possible.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());1247 1248 return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :1249 Builder.CreateZExt(NarrowOper, WideType);1250}1251 1252/// Instantiate a wide operation to replace a narrow operation. This only needs1253/// to handle operations that can evaluation to SCEVAddRec. It can safely return1254/// 0 for any operation we decide not to clone.1255Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,1256 const SCEVAddRecExpr *WideAR) {1257 unsigned Opcode = DU.NarrowUse->getOpcode();1258 switch (Opcode) {1259 default:1260 return nullptr;1261 case Instruction::Add:1262 case Instruction::Mul:1263 case Instruction::UDiv:1264 case Instruction::Sub:1265 return cloneArithmeticIVUser(DU, WideAR);1266 1267 case Instruction::And:1268 case Instruction::Or:1269 case Instruction::Xor:1270 case Instruction::Shl:1271 case Instruction::LShr:1272 case Instruction::AShr:1273 return cloneBitwiseIVUser(DU);1274 }1275}1276 1277Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {1278 Instruction *NarrowUse = DU.NarrowUse;1279 Instruction *NarrowDef = DU.NarrowDef;1280 Instruction *WideDef = DU.WideDef;1281 1282 LLVM_DEBUG(dbgs() << "Cloning bitwise IVUser: " << *NarrowUse << "\n");1283 1284 // Replace NarrowDef operands with WideDef. Otherwise, we don't know anything1285 // about the narrow operand yet so must insert a [sz]ext. It is probably loop1286 // invariant and will be folded or hoisted. If it actually comes from a1287 // widened IV, it should be removed during a future call to widenIVUse.1288 bool IsSigned = getExtendKind(NarrowDef) == ExtendKind::Sign;1289 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)1290 ? WideDef1291 : createExtendInst(NarrowUse->getOperand(0), WideType,1292 IsSigned, NarrowUse);1293 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)1294 ? WideDef1295 : createExtendInst(NarrowUse->getOperand(1), WideType,1296 IsSigned, NarrowUse);1297 1298 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);1299 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,1300 NarrowBO->getName());1301 IRBuilder<> Builder(NarrowUse);1302 Builder.Insert(WideBO);1303 WideBO->copyIRFlags(NarrowBO);1304 return WideBO;1305}1306 1307Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,1308 const SCEVAddRecExpr *WideAR) {1309 Instruction *NarrowUse = DU.NarrowUse;1310 Instruction *NarrowDef = DU.NarrowDef;1311 Instruction *WideDef = DU.WideDef;1312 1313 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");1314 1315 unsigned IVOpIdx = (NarrowUse->getOperand(0) == NarrowDef) ? 0 : 1;1316 1317 // We're trying to find X such that1318 //1319 // Widen(NarrowDef `op` NonIVNarrowDef) == WideAR == WideDef `op.wide` X1320 //1321 // We guess two solutions to X, sext(NonIVNarrowDef) and zext(NonIVNarrowDef),1322 // and check using SCEV if any of them are correct.1323 1324 // Returns true if extending NonIVNarrowDef according to `SignExt` is a1325 // correct solution to X.1326 auto GuessNonIVOperand = [&](bool SignExt) {1327 const SCEV *WideLHS;1328 const SCEV *WideRHS;1329 1330 auto GetExtend = [this, SignExt](const SCEV *S, Type *Ty) {1331 if (SignExt)1332 return SE->getSignExtendExpr(S, Ty);1333 return SE->getZeroExtendExpr(S, Ty);1334 };1335 1336 if (IVOpIdx == 0) {1337 WideLHS = SE->getSCEV(WideDef);1338 const SCEV *NarrowRHS = SE->getSCEV(NarrowUse->getOperand(1));1339 WideRHS = GetExtend(NarrowRHS, WideType);1340 } else {1341 const SCEV *NarrowLHS = SE->getSCEV(NarrowUse->getOperand(0));1342 WideLHS = GetExtend(NarrowLHS, WideType);1343 WideRHS = SE->getSCEV(WideDef);1344 }1345 1346 // WideUse is "WideDef `op.wide` X" as described in the comment.1347 const SCEV *WideUse =1348 getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->getOpcode());1349 1350 return WideUse == WideAR;1351 };1352 1353 bool SignExtend = getExtendKind(NarrowDef) == ExtendKind::Sign;1354 if (!GuessNonIVOperand(SignExtend)) {1355 SignExtend = !SignExtend;1356 if (!GuessNonIVOperand(SignExtend))1357 return nullptr;1358 }1359 1360 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)1361 ? WideDef1362 : createExtendInst(NarrowUse->getOperand(0), WideType,1363 SignExtend, NarrowUse);1364 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)1365 ? WideDef1366 : createExtendInst(NarrowUse->getOperand(1), WideType,1367 SignExtend, NarrowUse);1368 1369 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);1370 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,1371 NarrowBO->getName());1372 1373 IRBuilder<> Builder(NarrowUse);1374 Builder.Insert(WideBO);1375 WideBO->copyIRFlags(NarrowBO);1376 return WideBO;1377}1378 1379WidenIV::ExtendKind WidenIV::getExtendKind(Instruction *I) {1380 auto It = ExtendKindMap.find(I);1381 assert(It != ExtendKindMap.end() && "Instruction not yet extended!");1382 return It->second;1383}1384 1385const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,1386 unsigned OpCode) const {1387 switch (OpCode) {1388 case Instruction::Add:1389 return SE->getAddExpr(LHS, RHS);1390 case Instruction::Sub:1391 return SE->getMinusSCEV(LHS, RHS);1392 case Instruction::Mul:1393 return SE->getMulExpr(LHS, RHS);1394 case Instruction::UDiv:1395 return SE->getUDivExpr(LHS, RHS);1396 default:1397 llvm_unreachable("Unsupported opcode.");1398 };1399}1400 1401namespace {1402 1403// Represents a interesting integer binary operation for1404// getExtendedOperandRecurrence. This may be a shl that is being treated as a1405// multiply or a 'or disjoint' that is being treated as 'add nsw nuw'.1406struct BinaryOp {1407 unsigned Opcode;1408 std::array<Value *, 2> Operands;1409 bool IsNSW = false;1410 bool IsNUW = false;1411 1412 explicit BinaryOp(Instruction *Op)1413 : Opcode(Op->getOpcode()),1414 Operands({Op->getOperand(0), Op->getOperand(1)}) {1415 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(Op)) {1416 IsNSW = OBO->hasNoSignedWrap();1417 IsNUW = OBO->hasNoUnsignedWrap();1418 }1419 }1420 1421 explicit BinaryOp(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,1422 bool IsNSW = false, bool IsNUW = false)1423 : Opcode(Opcode), Operands({LHS, RHS}), IsNSW(IsNSW), IsNUW(IsNUW) {}1424};1425 1426} // end anonymous namespace1427 1428static std::optional<BinaryOp> matchBinaryOp(Instruction *Op) {1429 switch (Op->getOpcode()) {1430 case Instruction::Add:1431 case Instruction::Sub:1432 case Instruction::Mul:1433 return BinaryOp(Op);1434 case Instruction::Or: {1435 // Convert or disjoint into add nuw nsw.1436 if (cast<PossiblyDisjointInst>(Op)->isDisjoint())1437 return BinaryOp(Instruction::Add, Op->getOperand(0), Op->getOperand(1),1438 /*IsNSW=*/true, /*IsNUW=*/true);1439 break;1440 }1441 case Instruction::Shl: {1442 if (ConstantInt *SA = dyn_cast<ConstantInt>(Op->getOperand(1))) {1443 unsigned BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();1444 1445 // If the shift count is not less than the bitwidth, the result of1446 // the shift is undefined. Don't try to analyze it, because the1447 // resolution chosen here may differ from the resolution chosen in1448 // other parts of the compiler.1449 if (SA->getValue().ult(BitWidth)) {1450 // We can safely preserve the nuw flag in all cases. It's also safe to1451 // turn a nuw nsw shl into a nuw nsw mul. However, nsw in isolation1452 // requires special handling. It can be preserved as long as we're not1453 // left shifting by bitwidth - 1.1454 bool IsNUW = Op->hasNoUnsignedWrap();1455 bool IsNSW = Op->hasNoSignedWrap() &&1456 (IsNUW || SA->getValue().ult(BitWidth - 1));1457 1458 ConstantInt *X =1459 ConstantInt::get(Op->getContext(),1460 APInt::getOneBitSet(BitWidth, SA->getZExtValue()));1461 return BinaryOp(Instruction::Mul, Op->getOperand(0), X, IsNSW, IsNUW);1462 }1463 }1464 1465 break;1466 }1467 }1468 1469 return std::nullopt;1470}1471 1472/// No-wrap operations can transfer sign extension of their result to their1473/// operands. Generate the SCEV value for the widened operation without1474/// actually modifying the IR yet. If the expression after extending the1475/// operands is an AddRec for this loop, return the AddRec and the kind of1476/// extension used.1477WidenIV::WidenedRecTy1478WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {1479 auto Op = matchBinaryOp(DU.NarrowUse);1480 if (!Op)1481 return {nullptr, ExtendKind::Unknown};1482 1483 assert((Op->Opcode == Instruction::Add || Op->Opcode == Instruction::Sub ||1484 Op->Opcode == Instruction::Mul) &&1485 "Unexpected opcode");1486 1487 // One operand (NarrowDef) has already been extended to WideDef. Now determine1488 // if extending the other will lead to a recurrence.1489 const unsigned ExtendOperIdx = Op->Operands[0] == DU.NarrowDef ? 1 : 0;1490 assert(Op->Operands[1 - ExtendOperIdx] == DU.NarrowDef && "bad DU");1491 1492 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);1493 if (!(ExtKind == ExtendKind::Sign && Op->IsNSW) &&1494 !(ExtKind == ExtendKind::Zero && Op->IsNUW)) {1495 ExtKind = ExtendKind::Unknown;1496 1497 // For a non-negative NarrowDef, we can choose either type of1498 // extension. We want to use the current extend kind if legal1499 // (see above), and we only hit this code if we need to check1500 // the opposite case.1501 if (DU.NeverNegative) {1502 if (Op->IsNSW) {1503 ExtKind = ExtendKind::Sign;1504 } else if (Op->IsNUW) {1505 ExtKind = ExtendKind::Zero;1506 }1507 }1508 }1509 1510 const SCEV *ExtendOperExpr = SE->getSCEV(Op->Operands[ExtendOperIdx]);1511 if (ExtKind == ExtendKind::Sign)1512 ExtendOperExpr = SE->getSignExtendExpr(ExtendOperExpr, WideType);1513 else if (ExtKind == ExtendKind::Zero)1514 ExtendOperExpr = SE->getZeroExtendExpr(ExtendOperExpr, WideType);1515 else1516 return {nullptr, ExtendKind::Unknown};1517 1518 // When creating this SCEV expr, don't apply the current operations NSW or NUW1519 // flags. This instruction may be guarded by control flow that the no-wrap1520 // behavior depends on. Non-control-equivalent instructions can be mapped to1521 // the same SCEV expression, and it would be incorrect to transfer NSW/NUW1522 // semantics to those operations.1523 const SCEV *lhs = SE->getSCEV(DU.WideDef);1524 const SCEV *rhs = ExtendOperExpr;1525 1526 // Let's swap operands to the initial order for the case of non-commutative1527 // operations, like SUB. See PR21014.1528 if (ExtendOperIdx == 0)1529 std::swap(lhs, rhs);1530 const SCEVAddRecExpr *AddRec =1531 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, Op->Opcode));1532 1533 if (!AddRec || AddRec->getLoop() != L)1534 return {nullptr, ExtendKind::Unknown};1535 1536 return {AddRec, ExtKind};1537}1538 1539/// Is this instruction potentially interesting for further simplification after1540/// widening it's type? In other words, can the extend be safely hoisted out of1541/// the loop with SCEV reducing the value to a recurrence on the same loop. If1542/// so, return the extended recurrence and the kind of extension used. Otherwise1543/// return {nullptr, ExtendKind::Unknown}.1544WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {1545 if (!DU.NarrowUse->getType()->isIntegerTy())1546 return {nullptr, ExtendKind::Unknown};1547 1548 const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowUse);1549 if (SE->getTypeSizeInBits(NarrowExpr->getType()) >=1550 SE->getTypeSizeInBits(WideType)) {1551 // NarrowUse implicitly widens its operand. e.g. a gep with a narrow1552 // index. So don't follow this use.1553 return {nullptr, ExtendKind::Unknown};1554 }1555 1556 const SCEV *WideExpr;1557 ExtendKind ExtKind;1558 if (DU.NeverNegative) {1559 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);1560 if (isa<SCEVAddRecExpr>(WideExpr))1561 ExtKind = ExtendKind::Sign;1562 else {1563 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);1564 ExtKind = ExtendKind::Zero;1565 }1566 } else if (getExtendKind(DU.NarrowDef) == ExtendKind::Sign) {1567 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);1568 ExtKind = ExtendKind::Sign;1569 } else {1570 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);1571 ExtKind = ExtendKind::Zero;1572 }1573 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);1574 if (!AddRec || AddRec->getLoop() != L)1575 return {nullptr, ExtendKind::Unknown};1576 return {AddRec, ExtKind};1577}1578 1579/// This IV user cannot be widened. Replace this use of the original narrow IV1580/// with a truncation of the new wide IV to isolate and eliminate the narrow IV.1581void WidenIV::truncateIVUse(NarrowIVDefUse DU) {1582 auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);1583 if (!InsertPt)1584 return;1585 LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "1586 << *DU.NarrowUse << "\n");1587 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);1588 IRBuilder<> Builder(InsertPt);1589 Value *Trunc =1590 Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType(), "",1591 DU.NeverNegative || ExtKind == ExtendKind::Zero,1592 DU.NeverNegative || ExtKind == ExtendKind::Sign);1593 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);1594}1595 1596/// If the narrow use is a compare instruction, then widen the compare1597// (and possibly the other operand). The extend operation is hoisted into the1598// loop preheader as far as possible.1599bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {1600 ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse);1601 if (!Cmp)1602 return false;1603 1604 // We can legally widen the comparison in the following two cases:1605 //1606 // - The signedness of the IV extension and comparison match1607 //1608 // - The narrow IV is always non-negative (and thus its sign extension is1609 // equal to its zero extension). For instance, let's say we're zero1610 // extending %narrow for the following use1611 //1612 // icmp slt i32 %narrow, %val ... (A)1613 //1614 // and %narrow is always non-negative. Then1615 //1616 // (A) == icmp slt i32 sext(%narrow), sext(%val)1617 // == icmp slt i32 zext(%narrow), sext(%val)1618 bool IsSigned = getExtendKind(DU.NarrowDef) == ExtendKind::Sign;1619 bool CmpPreferredSign = Cmp->hasSameSign() ? IsSigned : Cmp->isSigned();1620 if (!DU.NeverNegative && IsSigned != CmpPreferredSign)1621 return false;1622 1623 Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);1624 unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());1625 unsigned IVWidth = SE->getTypeSizeInBits(WideType);1626 assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");1627 1628 // Widen the compare instruction.1629 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);1630 1631 // Widen the other operand of the compare, if necessary.1632 if (CastWidth < IVWidth) {1633 // If the narrow IV is always non-negative and the other operand is sext,1634 // widen using sext so we can combine them. This works for all non-signed1635 // comparison predicates.1636 if (DU.NeverNegative && isa<SExtInst>(Op) && !Cmp->isSigned())1637 CmpPreferredSign = true;1638 1639 Value *ExtOp = createExtendInst(Op, WideType, CmpPreferredSign, Cmp);1640 DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);1641 }1642 return true;1643}1644 1645// The widenIVUse avoids generating trunc by evaluating the use as AddRec, this1646// will not work when:1647// 1) SCEV traces back to an instruction inside the loop that SCEV can not1648// expand, eg. add %indvar, (load %addr)1649// 2) SCEV finds a loop variant, eg. add %indvar, %loopvariant1650// While SCEV fails to avoid trunc, we can still try to use instruction1651// combining approach to prove trunc is not required. This can be further1652// extended with other instruction combining checks, but for now we handle the1653// following case (sub can be "add" and "mul", "nsw + sext" can be "nus + zext")1654//1655// Src:1656// %c = sub nsw %b, %indvar1657// %d = sext %c to i641658// Dst:1659// %indvar.ext1 = sext %indvar to i641660// %m = sext %b to i641661// %d = sub nsw i64 %m, %indvar.ext11662// Therefore, as long as the result of add/sub/mul is extended to wide type, no1663// trunc is required regardless of how %b is generated. This pattern is common1664// when calculating address in 64 bit architecture1665bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {1666 Instruction *NarrowUse = DU.NarrowUse;1667 Instruction *NarrowDef = DU.NarrowDef;1668 Instruction *WideDef = DU.WideDef;1669 1670 // Handle the common case of add<nsw/nuw>1671 const unsigned OpCode = NarrowUse->getOpcode();1672 // Only Add/Sub/Mul instructions are supported.1673 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&1674 OpCode != Instruction::Mul)1675 return false;1676 1677 // The operand that is not defined by NarrowDef of DU. Let's call it the1678 // other operand.1679 assert((NarrowUse->getOperand(0) == NarrowDef ||1680 NarrowUse->getOperand(1) == NarrowDef) &&1681 "bad DU");1682 1683 const OverflowingBinaryOperator *OBO =1684 cast<OverflowingBinaryOperator>(NarrowUse);1685 ExtendKind ExtKind = getExtendKind(NarrowDef);1686 bool CanSignExtend = ExtKind == ExtendKind::Sign && OBO->hasNoSignedWrap();1687 bool CanZeroExtend = ExtKind == ExtendKind::Zero && OBO->hasNoUnsignedWrap();1688 auto AnotherOpExtKind = ExtKind;1689 1690 // Check that all uses are either:1691 // - narrow def (in case of we are widening the IV increment);1692 // - single-input LCSSA Phis;1693 // - comparison of the chosen type;1694 // - extend of the chosen type (raison d'etre).1695 SmallVector<Instruction *, 4> ExtUsers;1696 SmallVector<PHINode *, 4> LCSSAPhiUsers;1697 SmallVector<ICmpInst *, 4> ICmpUsers;1698 for (Use &U : NarrowUse->uses()) {1699 Instruction *User = cast<Instruction>(U.getUser());1700 if (User == NarrowDef)1701 continue;1702 if (!L->contains(User)) {1703 auto *LCSSAPhi = cast<PHINode>(User);1704 // Make sure there is only 1 input, so that we don't have to split1705 // critical edges.1706 if (LCSSAPhi->getNumOperands() != 1)1707 return false;1708 LCSSAPhiUsers.push_back(LCSSAPhi);1709 continue;1710 }1711 if (auto *ICmp = dyn_cast<ICmpInst>(User)) {1712 auto Pred = ICmp->getPredicate();1713 // We have 3 types of predicates: signed, unsigned and equality1714 // predicates. For equality, it's legal to widen icmp for either sign and1715 // zero extend. For sign extend, we can also do so for signed predicates,1716 // likeweise for zero extend we can widen icmp for unsigned predicates.1717 if (ExtKind == ExtendKind::Zero && ICmpInst::isSigned(Pred))1718 return false;1719 if (ExtKind == ExtendKind::Sign && ICmpInst::isUnsigned(Pred))1720 return false;1721 ICmpUsers.push_back(ICmp);1722 continue;1723 }1724 if (ExtKind == ExtendKind::Sign)1725 User = dyn_cast<SExtInst>(User);1726 else1727 User = dyn_cast<ZExtInst>(User);1728 if (!User || User->getType() != WideType)1729 return false;1730 ExtUsers.push_back(User);1731 }1732 if (ExtUsers.empty()) {1733 DeadInsts.emplace_back(NarrowUse);1734 return true;1735 }1736 1737 // We'll prove some facts that should be true in the context of ext users. If1738 // there is no users, we are done now. If there are some, pick their common1739 // dominator as context.1740 const Instruction *CtxI = findCommonDominator(ExtUsers, *DT);1741 1742 if (!CanSignExtend && !CanZeroExtend) {1743 // Because InstCombine turns 'sub nuw' to 'add' losing the no-wrap flag, we1744 // will most likely not see it. Let's try to prove it.1745 if (OpCode != Instruction::Add)1746 return false;1747 if (ExtKind != ExtendKind::Zero)1748 return false;1749 const SCEV *LHS = SE->getSCEV(OBO->getOperand(0));1750 const SCEV *RHS = SE->getSCEV(OBO->getOperand(1));1751 // TODO: Support case for NarrowDef = NarrowUse->getOperand(1).1752 if (NarrowUse->getOperand(0) != NarrowDef)1753 return false;1754 // We cannot use a different extend kind for the same operand.1755 if (NarrowUse->getOperand(1) == NarrowDef)1756 return false;1757 if (!SE->isKnownNegative(RHS))1758 return false;1759 bool ProvedSubNUW = SE->isKnownPredicateAt(ICmpInst::ICMP_UGE, LHS,1760 SE->getNegativeSCEV(RHS), CtxI);1761 if (!ProvedSubNUW)1762 return false;1763 // In fact, our 'add' is 'sub nuw'. We will need to widen the 2nd operand as1764 // neg(zext(neg(op))), which is basically sext(op).1765 AnotherOpExtKind = ExtendKind::Sign;1766 }1767 1768 // Verifying that Defining operand is an AddRec1769 const SCEV *Op1 = SE->getSCEV(WideDef);1770 const SCEVAddRecExpr *AddRecOp1 = dyn_cast<SCEVAddRecExpr>(Op1);1771 if (!AddRecOp1 || AddRecOp1->getLoop() != L)1772 return false;1773 1774 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");1775 1776 // Generating a widening use instruction.1777 Value *LHS =1778 (NarrowUse->getOperand(0) == NarrowDef)1779 ? WideDef1780 : createExtendInst(NarrowUse->getOperand(0), WideType,1781 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);1782 Value *RHS =1783 (NarrowUse->getOperand(1) == NarrowDef)1784 ? WideDef1785 : createExtendInst(NarrowUse->getOperand(1), WideType,1786 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);1787 1788 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);1789 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,1790 NarrowBO->getName());1791 IRBuilder<> Builder(NarrowUse);1792 Builder.Insert(WideBO);1793 WideBO->copyIRFlags(NarrowBO);1794 ExtendKindMap[NarrowUse] = ExtKind;1795 1796 for (Instruction *User : ExtUsers) {1797 assert(User->getType() == WideType && "Checked before!");1798 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *User << " replaced by "1799 << *WideBO << "\n");1800 ++NumElimExt;1801 User->replaceAllUsesWith(WideBO);1802 DeadInsts.emplace_back(User);1803 }1804 1805 for (PHINode *User : LCSSAPhiUsers) {1806 assert(User->getNumOperands() == 1 && "Checked before!");1807 Builder.SetInsertPoint(User);1808 auto *WidePN =1809 Builder.CreatePHI(WideBO->getType(), 1, User->getName() + ".wide");1810 BasicBlock *LoopExitingBlock = User->getParent()->getSinglePredecessor();1811 assert(LoopExitingBlock && L->contains(LoopExitingBlock) &&1812 "Not a LCSSA Phi?");1813 WidePN->addIncoming(WideBO, LoopExitingBlock);1814 Builder.SetInsertPoint(User->getParent(),1815 User->getParent()->getFirstInsertionPt());1816 auto *TruncPN = Builder.CreateTrunc(WidePN, User->getType());1817 User->replaceAllUsesWith(TruncPN);1818 DeadInsts.emplace_back(User);1819 }1820 1821 for (ICmpInst *User : ICmpUsers) {1822 Builder.SetInsertPoint(User);1823 auto ExtendedOp = [&](Value * V)->Value * {1824 if (V == NarrowUse)1825 return WideBO;1826 if (ExtKind == ExtendKind::Zero)1827 return Builder.CreateZExt(V, WideBO->getType());1828 else1829 return Builder.CreateSExt(V, WideBO->getType());1830 };1831 auto Pred = User->getPredicate();1832 auto *LHS = ExtendedOp(User->getOperand(0));1833 auto *RHS = ExtendedOp(User->getOperand(1));1834 auto *WideCmp =1835 Builder.CreateICmp(Pred, LHS, RHS, User->getName() + ".wide");1836 User->replaceAllUsesWith(WideCmp);1837 DeadInsts.emplace_back(User);1838 }1839 1840 return true;1841}1842 1843/// Determine whether an individual user of the narrow IV can be widened. If so,1844/// return the wide clone of the user.1845Instruction *WidenIV::widenIVUse(WidenIV::NarrowIVDefUse DU,1846 SCEVExpander &Rewriter, PHINode *OrigPhi,1847 PHINode *WidePhi) {1848 assert(ExtendKindMap.count(DU.NarrowDef) &&1849 "Should already know the kind of extension used to widen NarrowDef");1850 1851 // This narrow use can be widened by a sext if it's non-negative or its narrow1852 // def was widened by a sext. Same for zext.1853 bool CanWidenBySExt =1854 DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Sign;1855 bool CanWidenByZExt =1856 DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Zero;1857 1858 // Stop traversing the def-use chain at inner-loop phis or post-loop phis.1859 if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {1860 if (LI->getLoopFor(UsePhi->getParent()) != L) {1861 // For LCSSA phis, sink the truncate outside the loop.1862 // After SimplifyCFG most loop exit targets have a single predecessor.1863 // Otherwise fall back to a truncate within the loop.1864 if (UsePhi->getNumOperands() != 1)1865 truncateIVUse(DU);1866 else {1867 // Widening the PHI requires us to insert a trunc. The logical place1868 // for this trunc is in the same BB as the PHI. This is not possible if1869 // the BB is terminated by a catchswitch.1870 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))1871 return nullptr;1872 1873 PHINode *WidePhi =1874 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",1875 UsePhi->getIterator());1876 WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));1877 BasicBlock *WidePhiBB = WidePhi->getParent();1878 IRBuilder<> Builder(WidePhiBB, WidePhiBB->getFirstInsertionPt());1879 Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType(), "",1880 CanWidenByZExt, CanWidenBySExt);1881 UsePhi->replaceAllUsesWith(Trunc);1882 DeadInsts.emplace_back(UsePhi);1883 LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "1884 << *WidePhi << "\n");1885 }1886 return nullptr;1887 }1888 }1889 1890 // Our raison d'etre! Eliminate sign and zero extension.1891 if ((match(DU.NarrowUse, m_SExtLike(m_Value())) && CanWidenBySExt) ||1892 (isa<ZExtInst>(DU.NarrowUse) && CanWidenByZExt)) {1893 Value *NewDef = DU.WideDef;1894 if (DU.NarrowUse->getType() != WideType) {1895 unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());1896 unsigned IVWidth = SE->getTypeSizeInBits(WideType);1897 if (CastWidth < IVWidth) {1898 // The cast isn't as wide as the IV, so insert a Trunc.1899 IRBuilder<> Builder(DU.NarrowUse);1900 NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType(), "",1901 CanWidenByZExt, CanWidenBySExt);1902 }1903 else {1904 // A wider extend was hidden behind a narrower one. This may induce1905 // another round of IV widening in which the intermediate IV becomes1906 // dead. It should be very rare.1907 LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi1908 << " not wide enough to subsume " << *DU.NarrowUse1909 << "\n");1910 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);1911 NewDef = DU.NarrowUse;1912 }1913 }1914 if (NewDef != DU.NarrowUse) {1915 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse1916 << " replaced by " << *DU.WideDef << "\n");1917 ++NumElimExt;1918 DU.NarrowUse->replaceAllUsesWith(NewDef);1919 DeadInsts.emplace_back(DU.NarrowUse);1920 }1921 // Now that the extend is gone, we want to expose it's uses for potential1922 // further simplification. We don't need to directly inform SimplifyIVUsers1923 // of the new users, because their parent IV will be processed later as a1924 // new loop phi. If we preserved IVUsers analysis, we would also want to1925 // push the uses of WideDef here.1926 1927 // No further widening is needed. The deceased [sz]ext had done it for us.1928 return nullptr;1929 }1930 1931 auto tryAddRecExpansion = [&]() -> Instruction* {1932 // Does this user itself evaluate to a recurrence after widening?1933 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);1934 if (!WideAddRec.first)1935 WideAddRec = getWideRecurrence(DU);1936 assert((WideAddRec.first == nullptr) ==1937 (WideAddRec.second == ExtendKind::Unknown));1938 if (!WideAddRec.first)1939 return nullptr;1940 1941 auto CanUseWideInc = [&]() {1942 if (!WideInc)1943 return false;1944 // Reuse the IV increment that SCEVExpander created. Recompute flags,1945 // unless the flags for both increments agree and it is safe to use the1946 // ones from the original inc. In that case, the new use of the wide1947 // increment won't be more poisonous.1948 bool NeedToRecomputeFlags =1949 !SCEVExpander::canReuseFlagsFromOriginalIVInc(1950 OrigPhi, WidePhi, DU.NarrowUse, WideInc) ||1951 DU.NarrowUse->hasNoUnsignedWrap() != WideInc->hasNoUnsignedWrap() ||1952 DU.NarrowUse->hasNoSignedWrap() != WideInc->hasNoSignedWrap();1953 return WideAddRec.first == WideIncExpr &&1954 Rewriter.hoistIVInc(WideInc, DU.NarrowUse, NeedToRecomputeFlags);1955 };1956 1957 Instruction *WideUse = nullptr;1958 if (CanUseWideInc())1959 WideUse = WideInc;1960 else {1961 WideUse = cloneIVUser(DU, WideAddRec.first);1962 if (!WideUse)1963 return nullptr;1964 }1965 // Evaluation of WideAddRec ensured that the narrow expression could be1966 // extended outside the loop without overflow. This suggests that the wide use1967 // evaluates to the same expression as the extended narrow use, but doesn't1968 // absolutely guarantee it. Hence the following failsafe check. In rare cases1969 // where it fails, we simply throw away the newly created wide use.1970 if (WideAddRec.first != SE->getSCEV(WideUse)) {1971 LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "1972 << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first1973 << "\n");1974 DeadInsts.emplace_back(WideUse);1975 return nullptr;1976 };1977 1978 // if we reached this point then we are going to replace1979 // DU.NarrowUse with WideUse. Reattach DbgValue then.1980 replaceAllDbgUsesWith(*DU.NarrowUse, *WideUse, *WideUse, *DT);1981 1982 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;1983 // Returning WideUse pushes it on the worklist.1984 return WideUse;1985 };1986 1987 if (auto *I = tryAddRecExpansion())1988 return I;1989 1990 // If use is a loop condition, try to promote the condition instead of1991 // truncating the IV first.1992 if (widenLoopCompare(DU))1993 return nullptr;1994 1995 // We are here about to generate a truncate instruction that may hurt1996 // performance because the scalar evolution expression computed earlier1997 // in WideAddRec.first does not indicate a polynomial induction expression.1998 // In that case, look at the operands of the use instruction to determine1999 // if we can still widen the use instead of truncating its operand.2000 if (widenWithVariantUse(DU))2001 return nullptr;2002 2003 // This user does not evaluate to a recurrence after widening, so don't2004 // follow it. Instead insert a Trunc to kill off the original use,2005 // eventually isolating the original narrow IV so it can be removed.2006 truncateIVUse(DU);2007 return nullptr;2008}2009 2010/// Add eligible users of NarrowDef to NarrowIVUsers.2011void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {2012 const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);2013 bool NonNegativeDef =2014 SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,2015 SE->getZero(NarrowSCEV->getType()));2016 for (User *U : NarrowDef->users()) {2017 Instruction *NarrowUser = cast<Instruction>(U);2018 2019 // Handle data flow merges and bizarre phi cycles.2020 if (!Widened.insert(NarrowUser).second)2021 continue;2022 2023 bool NonNegativeUse = false;2024 if (!NonNegativeDef) {2025 // We might have a control-dependent range information for this context.2026 if (auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))2027 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();2028 }2029 2030 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,2031 NonNegativeDef || NonNegativeUse);2032 }2033}2034 2035/// Process a single induction variable. First use the SCEVExpander to create a2036/// wide induction variable that evaluates to the same recurrence as the2037/// original narrow IV. Then use a worklist to forward traverse the narrow IV's2038/// def-use chain. After widenIVUse has processed all interesting IV users, the2039/// narrow IV will be isolated for removal by DeleteDeadPHIs.2040///2041/// It would be simpler to delete uses as they are processed, but we must avoid2042/// invalidating SCEV expressions.2043PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {2044 // Is this phi an induction variable?2045 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));2046 if (!AddRec)2047 return nullptr;2048 2049 // Widen the induction variable expression.2050 const SCEV *WideIVExpr = getExtendKind(OrigPhi) == ExtendKind::Sign2051 ? SE->getSignExtendExpr(AddRec, WideType)2052 : SE->getZeroExtendExpr(AddRec, WideType);2053 2054 assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&2055 "Expect the new IV expression to preserve its type");2056 2057 // Can the IV be extended outside the loop without overflow?2058 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);2059 if (!AddRec || AddRec->getLoop() != L)2060 return nullptr;2061 2062 // An AddRec must have loop-invariant operands. Since this AddRec is2063 // materialized by a loop header phi, the expression cannot have any post-loop2064 // operands, so they must dominate the loop header.2065 assert(2066 SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&2067 SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&2068 "Loop header phi recurrence inputs do not dominate the loop");2069 2070 // Iterate over IV uses (including transitive ones) looking for IV increments2071 // of the form 'add nsw %iv, <const>'. For each increment and each use of2072 // the increment calculate control-dependent range information basing on2073 // dominating conditions inside of the loop (e.g. a range check inside of the2074 // loop). Calculated ranges are stored in PostIncRangeInfos map.2075 //2076 // Control-dependent range information is later used to prove that a narrow2077 // definition is not negative (see pushNarrowIVUsers). It's difficult to do2078 // this on demand because when pushNarrowIVUsers needs this information some2079 // of the dominating conditions might be already widened.2080 if (UsePostIncrementRanges)2081 calculatePostIncRanges(OrigPhi);2082 2083 // The rewriter provides a value for the desired IV expression. This may2084 // either find an existing phi or materialize a new one. Either way, we2085 // expect a well-formed cyclic phi-with-increments. i.e. any operand not part2086 // of the phi-SCC dominates the loop entry.2087 Instruction *InsertPt = &*L->getHeader()->getFirstInsertionPt();2088 Value *ExpandInst = Rewriter.expandCodeFor(AddRec, WideType, InsertPt);2089 // If the wide phi is not a phi node, for example a cast node, like bitcast,2090 // inttoptr, ptrtoint, just skip for now.2091 if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {2092 // if the cast node is an inserted instruction without any user, we should2093 // remove it to make sure the pass don't touch the function as we can not2094 // wide the phi.2095 if (ExpandInst->use_empty() &&2096 Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))2097 DeadInsts.emplace_back(ExpandInst);2098 return nullptr;2099 }2100 2101 // Remembering the WideIV increment generated by SCEVExpander allows2102 // widenIVUse to reuse it when widening the narrow IV's increment. We don't2103 // employ a general reuse mechanism because the call above is the only call to2104 // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.2105 if (BasicBlock *LatchBlock = L->getLoopLatch()) {2106 WideInc =2107 dyn_cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));2108 if (WideInc) {2109 WideIncExpr = SE->getSCEV(WideInc);2110 // Propagate the debug location associated with the original loop2111 // increment to the new (widened) increment.2112 auto *OrigInc =2113 cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));2114 2115 WideInc->setDebugLoc(OrigInc->getDebugLoc());2116 // We are replacing a narrow IV increment with a wider IV increment. If2117 // the original (narrow) increment did not wrap, the wider increment one2118 // should not wrap either. Set the flags to be the union of both wide2119 // increment and original increment; this ensures we preserve flags SCEV2120 // could infer for the wider increment. Limit this only to cases where2121 // both increments directly increment the corresponding PHI nodes and have2122 // the same opcode. It is not safe to re-use the flags from the original2123 // increment, if it is more complex and SCEV expansion may have yielded a2124 // more simplified wider increment.2125 if (SCEVExpander::canReuseFlagsFromOriginalIVInc(OrigPhi, WidePhi,2126 OrigInc, WideInc) &&2127 isa<OverflowingBinaryOperator>(OrigInc) &&2128 isa<OverflowingBinaryOperator>(WideInc)) {2129 WideInc->setHasNoUnsignedWrap(WideInc->hasNoUnsignedWrap() ||2130 OrigInc->hasNoUnsignedWrap());2131 WideInc->setHasNoSignedWrap(WideInc->hasNoSignedWrap() ||2132 OrigInc->hasNoSignedWrap());2133 }2134 }2135 }2136 2137 LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");2138 ++NumWidened;2139 2140 // Traverse the def-use chain using a worklist starting at the original IV.2141 assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );2142 2143 Widened.insert(OrigPhi);2144 pushNarrowIVUsers(OrigPhi, WidePhi);2145 2146 while (!NarrowIVUsers.empty()) {2147 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();2148 2149 // Process a def-use edge. This may replace the use, so don't hold a2150 // use_iterator across it.2151 Instruction *WideUse = widenIVUse(DU, Rewriter, OrigPhi, WidePhi);2152 2153 // Follow all def-use edges from the previous narrow use.2154 if (WideUse)2155 pushNarrowIVUsers(DU.NarrowUse, WideUse);2156 2157 // widenIVUse may have removed the def-use edge.2158 if (DU.NarrowDef->use_empty())2159 DeadInsts.emplace_back(DU.NarrowDef);2160 }2161 2162 // Attach any debug information to the new PHI.2163 replaceAllDbgUsesWith(*OrigPhi, *WidePhi, *WidePhi, *DT);2164 2165 return WidePhi;2166}2167 2168/// Calculates control-dependent range for the given def at the given context2169/// by looking at dominating conditions inside of the loop2170void WidenIV::calculatePostIncRange(Instruction *NarrowDef,2171 Instruction *NarrowUser) {2172 Value *NarrowDefLHS;2173 const APInt *NarrowDefRHS;2174 if (!match(NarrowDef, m_NSWAdd(m_Value(NarrowDefLHS),2175 m_APInt(NarrowDefRHS))) ||2176 !NarrowDefRHS->isNonNegative())2177 return;2178 2179 auto UpdateRangeFromCondition = [&](Value *Condition, bool TrueDest) {2180 CmpPredicate Pred;2181 Value *CmpRHS;2182 if (!match(Condition, m_ICmp(Pred, m_Specific(NarrowDefLHS),2183 m_Value(CmpRHS))))2184 return;2185 2186 CmpPredicate P = TrueDest ? Pred : ICmpInst::getInverseCmpPredicate(Pred);2187 2188 auto CmpRHSRange = SE->getSignedRange(SE->getSCEV(CmpRHS));2189 auto CmpConstrainedLHSRange =2190 ConstantRange::makeAllowedICmpRegion(P, CmpRHSRange);2191 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(2192 *NarrowDefRHS, OverflowingBinaryOperator::NoSignedWrap);2193 2194 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);2195 };2196 2197 auto UpdateRangeFromGuards = [&](Instruction *Ctx) {2198 if (!HasGuards)2199 return;2200 2201 for (Instruction &I : make_range(Ctx->getIterator().getReverse(),2202 Ctx->getParent()->rend())) {2203 Value *C = nullptr;2204 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(C))))2205 UpdateRangeFromCondition(C, /*TrueDest=*/true);2206 }2207 };2208 2209 UpdateRangeFromGuards(NarrowUser);2210 2211 BasicBlock *NarrowUserBB = NarrowUser->getParent();2212 // If NarrowUserBB is statically unreachable asking dominator queries may2213 // yield surprising results. (e.g. the block may not have a dom tree node)2214 if (!DT->isReachableFromEntry(NarrowUserBB))2215 return;2216 2217 for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();2218 L->contains(DTB->getBlock());2219 DTB = DTB->getIDom()) {2220 auto *BB = DTB->getBlock();2221 auto *TI = BB->getTerminator();2222 UpdateRangeFromGuards(TI);2223 2224 auto *BI = dyn_cast<BranchInst>(TI);2225 if (!BI || !BI->isConditional())2226 continue;2227 2228 auto *TrueSuccessor = BI->getSuccessor(0);2229 auto *FalseSuccessor = BI->getSuccessor(1);2230 2231 auto DominatesNarrowUser = [this, NarrowUser] (BasicBlockEdge BBE) {2232 return BBE.isSingleEdge() &&2233 DT->dominates(BBE, NarrowUser->getParent());2234 };2235 2236 if (DominatesNarrowUser(BasicBlockEdge(BB, TrueSuccessor)))2237 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);2238 2239 if (DominatesNarrowUser(BasicBlockEdge(BB, FalseSuccessor)))2240 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);2241 }2242}2243 2244/// Calculates PostIncRangeInfos map for the given IV2245void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {2246 SmallPtrSet<Instruction *, 16> Visited;2247 SmallVector<Instruction *, 6> Worklist;2248 Worklist.push_back(OrigPhi);2249 Visited.insert(OrigPhi);2250 2251 while (!Worklist.empty()) {2252 Instruction *NarrowDef = Worklist.pop_back_val();2253 2254 for (Use &U : NarrowDef->uses()) {2255 auto *NarrowUser = cast<Instruction>(U.getUser());2256 2257 // Don't go looking outside the current loop.2258 auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];2259 if (!NarrowUserLoop || !L->contains(NarrowUserLoop))2260 continue;2261 2262 if (!Visited.insert(NarrowUser).second)2263 continue;2264 2265 Worklist.push_back(NarrowUser);2266 2267 calculatePostIncRange(NarrowDef, NarrowUser);2268 }2269 }2270}2271 2272PHINode *llvm::createWideIV(const WideIVInfo &WI,2273 LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter,2274 DominatorTree *DT, SmallVectorImpl<WeakTrackingVH> &DeadInsts,2275 unsigned &NumElimExt, unsigned &NumWidened,2276 bool HasGuards, bool UsePostIncrementRanges) {2277 WidenIV Widener(WI, LI, SE, DT, DeadInsts, HasGuards, UsePostIncrementRanges);2278 PHINode *WidePHI = Widener.createWideIV(Rewriter);2279 NumElimExt = Widener.getNumElimExt();2280 NumWidened = Widener.getNumWidened();2281 return WidePHI;2282}2283