brintos / llvm-project-archived public Read only

1//===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis ------------===//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 contains the implementation of the scalar evolution expander,10// which is used to generate the code corresponding to a given scalar evolution11// expression.12//13//===----------------------------------------------------------------------===//14 15#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"16#include "llvm/ADT/STLExtras.h"17#include "llvm/ADT/ScopeExit.h"18#include "llvm/Analysis/InstructionSimplify.h"19#include "llvm/Analysis/LoopInfo.h"20#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"21#include "llvm/Analysis/TargetTransformInfo.h"22#include "llvm/Analysis/ValueTracking.h"23#include "llvm/IR/DataLayout.h"24#include "llvm/IR/Dominators.h"25#include "llvm/IR/IntrinsicInst.h"26#include "llvm/IR/PatternMatch.h"27#include "llvm/Support/CommandLine.h"28#include "llvm/Support/raw_ostream.h"29#include "llvm/Transforms/Utils/Local.h"30#include "llvm/Transforms/Utils/LoopUtils.h"31 32#if LLVM_ENABLE_ABI_BREAKING_CHECKS33#define SCEV_DEBUG_WITH_TYPE(TYPE, X) DEBUG_WITH_TYPE(TYPE, X)34#else35#define SCEV_DEBUG_WITH_TYPE(TYPE, X)36#endif37 38using namespace llvm;39 40cl::opt<unsigned> llvm::SCEVCheapExpansionBudget(41    "scev-cheap-expansion-budget", cl::Hidden, cl::init(4),42    cl::desc("When performing SCEV expansion only if it is cheap to do, this "43             "controls the budget that is considered cheap (default = 4)"));44 45using namespace PatternMatch;46using namespace SCEVPatternMatch;47 48PoisonFlags::PoisonFlags(const Instruction *I) {49  NUW = false;50  NSW = false;51  Exact = false;52  Disjoint = false;53  NNeg = false;54  SameSign = false;55  GEPNW = GEPNoWrapFlags::none();56  if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(I)) {57    NUW = OBO->hasNoUnsignedWrap();58    NSW = OBO->hasNoSignedWrap();59  }60  if (auto *PEO = dyn_cast<PossiblyExactOperator>(I))61    Exact = PEO->isExact();62  if (auto *PDI = dyn_cast<PossiblyDisjointInst>(I))63    Disjoint = PDI->isDisjoint();64  if (auto *PNI = dyn_cast<PossiblyNonNegInst>(I))65    NNeg = PNI->hasNonNeg();66  if (auto *TI = dyn_cast<TruncInst>(I)) {67    NUW = TI->hasNoUnsignedWrap();68    NSW = TI->hasNoSignedWrap();69  }70  if (auto *GEP = dyn_cast<GetElementPtrInst>(I))71    GEPNW = GEP->getNoWrapFlags();72  if (auto *ICmp = dyn_cast<ICmpInst>(I))73    SameSign = ICmp->hasSameSign();74}75 76void PoisonFlags::apply(Instruction *I) {77  if (isa<OverflowingBinaryOperator>(I)) {78    I->setHasNoUnsignedWrap(NUW);79    I->setHasNoSignedWrap(NSW);80  }81  if (isa<PossiblyExactOperator>(I))82    I->setIsExact(Exact);83  if (auto *PDI = dyn_cast<PossiblyDisjointInst>(I))84    PDI->setIsDisjoint(Disjoint);85  if (auto *PNI = dyn_cast<PossiblyNonNegInst>(I))86    PNI->setNonNeg(NNeg);87  if (isa<TruncInst>(I)) {88    I->setHasNoUnsignedWrap(NUW);89    I->setHasNoSignedWrap(NSW);90  }91  if (auto *GEP = dyn_cast<GetElementPtrInst>(I))92    GEP->setNoWrapFlags(GEPNW);93  if (auto *ICmp = dyn_cast<ICmpInst>(I))94    ICmp->setSameSign(SameSign);95}96 97/// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,98/// reusing an existing cast if a suitable one (= dominating IP) exists, or99/// creating a new one.100Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,101                                       Instruction::CastOps Op,102                                       BasicBlock::iterator IP) {103  // This function must be called with the builder having a valid insertion104  // point. It doesn't need to be the actual IP where the uses of the returned105  // cast will be added, but it must dominate such IP.106  // We use this precondition to produce a cast that will dominate all its107  // uses. In particular, this is crucial for the case where the builder's108  // insertion point *is* the point where we were asked to put the cast.109  // Since we don't know the builder's insertion point is actually110  // where the uses will be added (only that it dominates it), we are111  // not allowed to move it.112  BasicBlock::iterator BIP = Builder.GetInsertPoint();113 114  Value *Ret = nullptr;115 116  if (!isa<Constant>(V)) {117    // Check to see if there is already a cast!118    for (User *U : V->users()) {119      if (U->getType() != Ty)120        continue;121      CastInst *CI = dyn_cast<CastInst>(U);122      if (!CI || CI->getOpcode() != Op)123        continue;124 125      // Found a suitable cast that is at IP or comes before IP. Use it. Note126      // that the cast must also properly dominate the Builder's insertion127      // point.128      if (IP->getParent() == CI->getParent() && &*BIP != CI &&129          (&*IP == CI || CI->comesBefore(&*IP))) {130        Ret = CI;131        break;132      }133    }134  }135 136  // Create a new cast.137  if (!Ret) {138    SCEVInsertPointGuard Guard(Builder, this);139    Builder.SetInsertPoint(&*IP);140    Ret = Builder.CreateCast(Op, V, Ty, V->getName());141  }142 143  // We assert at the end of the function since IP might point to an144  // instruction with different dominance properties than a cast145  // (an invoke for example) and not dominate BIP (but the cast does).146  assert(!isa<Instruction>(Ret) ||147         SE.DT.dominates(cast<Instruction>(Ret), &*BIP));148 149  return Ret;150}151 152BasicBlock::iterator153SCEVExpander::findInsertPointAfter(Instruction *I,154                                   Instruction *MustDominate) const {155  BasicBlock::iterator IP = ++I->getIterator();156  if (auto *II = dyn_cast<InvokeInst>(I))157    IP = II->getNormalDest()->begin();158 159  while (isa<PHINode>(IP))160    ++IP;161 162  if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {163    ++IP;164  } else if (isa<CatchSwitchInst>(IP)) {165    IP = MustDominate->getParent()->getFirstInsertionPt();166  } else {167    assert(!IP->isEHPad() && "unexpected eh pad!");168  }169 170  // Adjust insert point to be after instructions inserted by the expander, so171  // we can re-use already inserted instructions. Avoid skipping past the172  // original \p MustDominate, in case it is an inserted instruction.173  while (isInsertedInstruction(&*IP) && &*IP != MustDominate)174    ++IP;175 176  return IP;177}178 179void SCEVExpander::eraseDeadInstructions(Value *Root) {180  SmallVector<Value *> WorkList;181  SmallPtrSet<Value *, 8> DeletedValues;182  append_range(WorkList, getAllInsertedInstructions());183  while (!WorkList.empty()) {184    Value *V = WorkList.pop_back_val();185    if (DeletedValues.contains(V))186      continue;187    auto *I = dyn_cast<Instruction>(V);188    if (!I || I == Root || !isInsertedInstruction(I) ||189        !isInstructionTriviallyDead(I))190      continue;191    append_range(WorkList, I->operands());192    InsertedValues.erase(I);193    InsertedPostIncValues.erase(I);194    DeletedValues.insert(I);195    I->eraseFromParent();196  }197}198 199BasicBlock::iterator200SCEVExpander::GetOptimalInsertionPointForCastOf(Value *V) const {201  // Cast the argument at the beginning of the entry block, after202  // any bitcasts of other arguments.203  if (Argument *A = dyn_cast<Argument>(V)) {204    BasicBlock::iterator IP = A->getParent()->getEntryBlock().begin();205    while ((isa<BitCastInst>(IP) &&206            isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) &&207            cast<BitCastInst>(IP)->getOperand(0) != A))208      ++IP;209    return IP;210  }211 212  // Cast the instruction immediately after the instruction.213  if (Instruction *I = dyn_cast<Instruction>(V))214    return findInsertPointAfter(I, &*Builder.GetInsertPoint());215 216  // Otherwise, this must be some kind of a constant,217  // so let's plop this cast into the function's entry block.218  assert(isa<Constant>(V) &&219         "Expected the cast argument to be a global/constant");220  return Builder.GetInsertBlock()221      ->getParent()222      ->getEntryBlock()223      .getFirstInsertionPt();224}225 226/// InsertNoopCastOfTo - Insert a cast of V to the specified type,227/// which must be possible with a noop cast, doing what we can to share228/// the casts.229Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {230  Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false);231  assert((Op == Instruction::BitCast ||232          Op == Instruction::PtrToInt ||233          Op == Instruction::IntToPtr) &&234         "InsertNoopCastOfTo cannot perform non-noop casts!");235  assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) &&236         "InsertNoopCastOfTo cannot change sizes!");237 238  // inttoptr only works for integral pointers. For non-integral pointers, we239  // can create a GEP on null with the integral value as index. Note that240  // it is safe to use GEP of null instead of inttoptr here, because only241  // expressions already based on a GEP of null should be converted to pointers242  // during expansion.243  if (Op == Instruction::IntToPtr) {244    auto *PtrTy = cast<PointerType>(Ty);245    if (DL.isNonIntegralPointerType(PtrTy))246      return Builder.CreatePtrAdd(Constant::getNullValue(PtrTy), V, "scevgep");247  }248  // Short-circuit unnecessary bitcasts.249  if (Op == Instruction::BitCast) {250    if (V->getType() == Ty)251      return V;252    if (CastInst *CI = dyn_cast<CastInst>(V)) {253      if (CI->getOperand(0)->getType() == Ty)254        return CI->getOperand(0);255    }256  }257  // Short-circuit unnecessary inttoptr<->ptrtoint casts.258  if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) &&259      SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) {260    if (CastInst *CI = dyn_cast<CastInst>(V))261      if ((CI->getOpcode() == Instruction::PtrToInt ||262           CI->getOpcode() == Instruction::IntToPtr) &&263          SE.getTypeSizeInBits(CI->getType()) ==264          SE.getTypeSizeInBits(CI->getOperand(0)->getType()))265        return CI->getOperand(0);266    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))267      if ((CE->getOpcode() == Instruction::PtrToInt ||268           CE->getOpcode() == Instruction::IntToPtr) &&269          SE.getTypeSizeInBits(CE->getType()) ==270          SE.getTypeSizeInBits(CE->getOperand(0)->getType()))271        return CE->getOperand(0);272  }273 274  // Fold a cast of a constant.275  if (Constant *C = dyn_cast<Constant>(V))276    return ConstantExpr::getCast(Op, C, Ty);277 278  // Try to reuse existing cast, or insert one.279  return ReuseOrCreateCast(V, Ty, Op, GetOptimalInsertionPointForCastOf(V));280}281 282/// InsertBinop - Insert the specified binary operator, doing a small amount283/// of work to avoid inserting an obviously redundant operation, and hoisting284/// to an outer loop when the opportunity is there and it is safe.285Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,286                                 Value *LHS, Value *RHS,287                                 SCEV::NoWrapFlags Flags, bool IsSafeToHoist) {288  // Fold a binop with constant operands.289  if (Constant *CLHS = dyn_cast<Constant>(LHS))290    if (Constant *CRHS = dyn_cast<Constant>(RHS))291      if (Constant *Res = ConstantFoldBinaryOpOperands(Opcode, CLHS, CRHS, DL))292        return Res;293 294  // Do a quick scan to see if we have this binop nearby.  If so, reuse it.295  unsigned ScanLimit = 6;296  BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();297  // Scanning starts from the last instruction before the insertion point.298  BasicBlock::iterator IP = Builder.GetInsertPoint();299  if (IP != BlockBegin) {300    --IP;301    for (; ScanLimit; --IP, --ScanLimit) {302      auto canGenerateIncompatiblePoison = [&Flags](Instruction *I) {303        // Ensure that no-wrap flags match.304        if (isa<OverflowingBinaryOperator>(I)) {305          if (I->hasNoSignedWrap() != (Flags & SCEV::FlagNSW))306            return true;307          if (I->hasNoUnsignedWrap() != (Flags & SCEV::FlagNUW))308            return true;309        }310        // Conservatively, do not use any instruction which has any of exact311        // flags installed.312        if (isa<PossiblyExactOperator>(I) && I->isExact())313          return true;314        return false;315      };316      if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS &&317          IP->getOperand(1) == RHS && !canGenerateIncompatiblePoison(&*IP))318        return &*IP;319      if (IP == BlockBegin) break;320    }321  }322 323  // Save the original insertion point so we can restore it when we're done.324  DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();325  SCEVInsertPointGuard Guard(Builder, this);326 327  if (IsSafeToHoist) {328    // Move the insertion point out of as many loops as we can.329    while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {330      if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break;331      BasicBlock *Preheader = L->getLoopPreheader();332      if (!Preheader) break;333 334      // Ok, move up a level.335      Builder.SetInsertPoint(Preheader->getTerminator());336    }337  }338 339  // If we haven't found this binop, insert it.340  // TODO: Use the Builder, which will make CreateBinOp below fold with341  // InstSimplifyFolder.342  Instruction *BO = Builder.Insert(BinaryOperator::Create(Opcode, LHS, RHS));343  BO->setDebugLoc(Loc);344  if (Flags & SCEV::FlagNUW)345    BO->setHasNoUnsignedWrap();346  if (Flags & SCEV::FlagNSW)347    BO->setHasNoSignedWrap();348 349  return BO;350}351 352/// expandAddToGEP - Expand an addition expression with a pointer type into353/// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps354/// BasicAliasAnalysis and other passes analyze the result. See the rules355/// for getelementptr vs. inttoptr in356/// http://llvm.org/docs/LangRef.html#pointeraliasing357/// for details.358///359/// Design note: The correctness of using getelementptr here depends on360/// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as361/// they may introduce pointer arithmetic which may not be safely converted362/// into getelementptr.363///364/// Design note: It might seem desirable for this function to be more365/// loop-aware. If some of the indices are loop-invariant while others366/// aren't, it might seem desirable to emit multiple GEPs, keeping the367/// loop-invariant portions of the overall computation outside the loop.368/// However, there are a few reasons this is not done here. Hoisting simple369/// arithmetic is a low-level optimization that often isn't very370/// important until late in the optimization process. In fact, passes371/// like InstructionCombining will combine GEPs, even if it means372/// pushing loop-invariant computation down into loops, so even if the373/// GEPs were split here, the work would quickly be undone. The374/// LoopStrengthReduction pass, which is usually run quite late (and375/// after the last InstructionCombining pass), takes care of hoisting376/// loop-invariant portions of expressions, after considering what377/// can be folded using target addressing modes.378///379Value *SCEVExpander::expandAddToGEP(const SCEV *Offset, Value *V,380                                    SCEV::NoWrapFlags Flags) {381  assert(!isa<Instruction>(V) ||382         SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()));383 384  Value *Idx = expand(Offset);385  GEPNoWrapFlags NW = (Flags & SCEV::FlagNUW) ? GEPNoWrapFlags::noUnsignedWrap()386                                              : GEPNoWrapFlags::none();387 388  // Fold a GEP with constant operands.389  if (Constant *CLHS = dyn_cast<Constant>(V))390    if (Constant *CRHS = dyn_cast<Constant>(Idx))391      return Builder.CreatePtrAdd(CLHS, CRHS, "", NW);392 393  // Do a quick scan to see if we have this GEP nearby.  If so, reuse it.394  unsigned ScanLimit = 6;395  BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();396  // Scanning starts from the last instruction before the insertion point.397  BasicBlock::iterator IP = Builder.GetInsertPoint();398  if (IP != BlockBegin) {399    --IP;400    for (; ScanLimit; --IP, --ScanLimit) {401      if (auto *GEP = dyn_cast<GetElementPtrInst>(IP)) {402        if (GEP->getPointerOperand() == V &&403            GEP->getSourceElementType() == Builder.getInt8Ty() &&404            GEP->getOperand(1) == Idx) {405          rememberFlags(GEP);406          GEP->setNoWrapFlags(GEP->getNoWrapFlags() & NW);407          return &*IP;408        }409      }410      if (IP == BlockBegin) break;411    }412  }413 414  // Save the original insertion point so we can restore it when we're done.415  SCEVInsertPointGuard Guard(Builder, this);416 417  // Move the insertion point out of as many loops as we can.418  while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {419    if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break;420    BasicBlock *Preheader = L->getLoopPreheader();421    if (!Preheader) break;422 423    // Ok, move up a level.424    Builder.SetInsertPoint(Preheader->getTerminator());425  }426 427  // Emit a GEP.428  return Builder.CreatePtrAdd(V, Idx, "scevgep", NW);429}430 431/// PickMostRelevantLoop - Given two loops pick the one that's most relevant for432/// SCEV expansion. If they are nested, this is the most nested. If they are433/// neighboring, pick the later.434static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B,435                                        DominatorTree &DT) {436  if (!A) return B;437  if (!B) return A;438  if (A->contains(B)) return B;439  if (B->contains(A)) return A;440  if (DT.dominates(A->getHeader(), B->getHeader())) return B;441  if (DT.dominates(B->getHeader(), A->getHeader())) return A;442  return A; // Arbitrarily break the tie.443}444 445/// getRelevantLoop - Get the most relevant loop associated with the given446/// expression, according to PickMostRelevantLoop.447const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) {448  // Test whether we've already computed the most relevant loop for this SCEV.449  auto Pair = RelevantLoops.try_emplace(S);450  if (!Pair.second)451    return Pair.first->second;452 453  switch (S->getSCEVType()) {454  case scConstant:455  case scVScale:456    return nullptr; // A constant has no relevant loops.457  case scTruncate:458  case scZeroExtend:459  case scSignExtend:460  case scPtrToInt:461  case scAddExpr:462  case scMulExpr:463  case scUDivExpr:464  case scAddRecExpr:465  case scUMaxExpr:466  case scSMaxExpr:467  case scUMinExpr:468  case scSMinExpr:469  case scSequentialUMinExpr: {470    const Loop *L = nullptr;471    if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))472      L = AR->getLoop();473    for (const SCEV *Op : S->operands())474      L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT);475    return RelevantLoops[S] = L;476  }477  case scUnknown: {478    const SCEVUnknown *U = cast<SCEVUnknown>(S);479    if (const Instruction *I = dyn_cast<Instruction>(U->getValue()))480      return Pair.first->second = SE.LI.getLoopFor(I->getParent());481    // A non-instruction has no relevant loops.482    return nullptr;483  }484  case scCouldNotCompute:485    llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");486  }487  llvm_unreachable("Unexpected SCEV type!");488}489 490namespace {491 492/// LoopCompare - Compare loops by PickMostRelevantLoop.493class LoopCompare {494  DominatorTree &DT;495public:496  explicit LoopCompare(DominatorTree &dt) : DT(dt) {}497 498  bool operator()(std::pair<const Loop *, const SCEV *> LHS,499                  std::pair<const Loop *, const SCEV *> RHS) const {500    // Keep pointer operands sorted at the end.501    if (LHS.second->getType()->isPointerTy() !=502        RHS.second->getType()->isPointerTy())503      return LHS.second->getType()->isPointerTy();504 505    // Compare loops with PickMostRelevantLoop.506    if (LHS.first != RHS.first)507      return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first;508 509    // If one operand is a non-constant negative and the other is not,510    // put the non-constant negative on the right so that a sub can511    // be used instead of a negate and add.512    if (LHS.second->isNonConstantNegative()) {513      if (!RHS.second->isNonConstantNegative())514        return false;515    } else if (RHS.second->isNonConstantNegative())516      return true;517 518    // Otherwise they are equivalent according to this comparison.519    return false;520  }521};522 523}524 525Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) {526  // Recognize the canonical representation of an unsimplifed urem.527  const SCEV *URemLHS = nullptr;528  const SCEV *URemRHS = nullptr;529  if (match(S, m_scev_URem(m_SCEV(URemLHS), m_SCEV(URemRHS), SE))) {530    Value *LHS = expand(URemLHS);531    Value *RHS = expand(URemRHS);532    return InsertBinop(Instruction::URem, LHS, RHS, SCEV::FlagAnyWrap,533                      /*IsSafeToHoist*/ false);534  }535 536  // Collect all the add operands in a loop, along with their associated loops.537  // Iterate in reverse so that constants are emitted last, all else equal, and538  // so that pointer operands are inserted first, which the code below relies on539  // to form more involved GEPs.540  SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;541  for (const SCEV *Op : reverse(S->operands()))542    OpsAndLoops.push_back(std::make_pair(getRelevantLoop(Op), Op));543 544  // Sort by loop. Use a stable sort so that constants follow non-constants and545  // pointer operands precede non-pointer operands.546  llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));547 548  // Emit instructions to add all the operands. Hoist as much as possible549  // out of loops, and form meaningful getelementptrs where possible.550  Value *Sum = nullptr;551  for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) {552    const Loop *CurLoop = I->first;553    const SCEV *Op = I->second;554    if (!Sum) {555      // This is the first operand. Just expand it.556      Sum = expand(Op);557      ++I;558      continue;559    }560 561    assert(!Op->getType()->isPointerTy() && "Only first op can be pointer");562    if (isa<PointerType>(Sum->getType())) {563      // The running sum expression is a pointer. Try to form a getelementptr564      // at this level with that as the base.565      SmallVector<const SCEV *, 4> NewOps;566      for (; I != E && I->first == CurLoop; ++I) {567        // If the operand is SCEVUnknown and not instructions, peek through568        // it, to enable more of it to be folded into the GEP.569        const SCEV *X = I->second;570        if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X))571          if (!isa<Instruction>(U->getValue()))572            X = SE.getSCEV(U->getValue());573        NewOps.push_back(X);574      }575      Sum = expandAddToGEP(SE.getAddExpr(NewOps), Sum, S->getNoWrapFlags());576    } else if (Op->isNonConstantNegative()) {577      // Instead of doing a negate and add, just do a subtract.578      Value *W = expand(SE.getNegativeSCEV(Op));579      Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap,580                        /*IsSafeToHoist*/ true);581      ++I;582    } else {583      // A simple add.584      Value *W = expand(Op);585      // Canonicalize a constant to the RHS.586      if (isa<Constant>(Sum))587        std::swap(Sum, W);588      Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(),589                        /*IsSafeToHoist*/ true);590      ++I;591    }592  }593 594  return Sum;595}596 597Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {598  Type *Ty = S->getType();599 600  // Collect all the mul operands in a loop, along with their associated loops.601  // Iterate in reverse so that constants are emitted last, all else equal.602  SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;603  for (const SCEV *Op : reverse(S->operands()))604    OpsAndLoops.push_back(std::make_pair(getRelevantLoop(Op), Op));605 606  // Sort by loop. Use a stable sort so that constants follow non-constants.607  llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));608 609  // Emit instructions to mul all the operands. Hoist as much as possible610  // out of loops.611  Value *Prod = nullptr;612  auto I = OpsAndLoops.begin();613 614  // Expand the calculation of X pow N in the following manner:615  // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then:616  // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK).617  const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops]() {618    auto E = I;619    // Calculate how many times the same operand from the same loop is included620    // into this power.621    uint64_t Exponent = 0;622    const uint64_t MaxExponent = UINT64_MAX >> 1;623    // No one sane will ever try to calculate such huge exponents, but if we624    // need this, we stop on UINT64_MAX / 2 because we need to exit the loop625    // below when the power of 2 exceeds our Exponent, and we want it to be626    // 1u << 31 at most to not deal with unsigned overflow.627    while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) {628      ++Exponent;629      ++E;630    }631    assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?");632 633    // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them634    // that are needed into the result.635    Value *P = expand(I->second);636    Value *Result = nullptr;637    if (Exponent & 1)638      Result = P;639    for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) {640      P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap,641                      /*IsSafeToHoist*/ true);642      if (Exponent & BinExp)643        Result = Result ? InsertBinop(Instruction::Mul, Result, P,644                                      SCEV::FlagAnyWrap,645                                      /*IsSafeToHoist*/ true)646                        : P;647    }648 649    I = E;650    assert(Result && "Nothing was expanded?");651    return Result;652  };653 654  while (I != OpsAndLoops.end()) {655    if (!Prod) {656      // This is the first operand. Just expand it.657      Prod = ExpandOpBinPowN();658    } else if (I->second->isAllOnesValue()) {659      // Instead of doing a multiply by negative one, just do a negate.660      Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod,661                         SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);662      ++I;663    } else {664      // A simple mul.665      Value *W = ExpandOpBinPowN();666      // Canonicalize a constant to the RHS.667      if (isa<Constant>(Prod)) std::swap(Prod, W);668      const APInt *RHS;669      if (match(W, m_Power2(RHS))) {670        // Canonicalize Prod*(1<<C) to Prod<<C.671        assert(!Ty->isVectorTy() && "vector types are not SCEVable");672        auto NWFlags = S->getNoWrapFlags();673        // clear nsw flag if shl will produce poison value.674        if (RHS->logBase2() == RHS->getBitWidth() - 1)675          NWFlags = ScalarEvolution::clearFlags(NWFlags, SCEV::FlagNSW);676        Prod = InsertBinop(Instruction::Shl, Prod,677                           ConstantInt::get(Ty, RHS->logBase2()), NWFlags,678                           /*IsSafeToHoist*/ true);679      } else {680        Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(),681                           /*IsSafeToHoist*/ true);682      }683    }684  }685 686  return Prod;687}688 689Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {690  Value *LHS = expand(S->getLHS());691  if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {692    const APInt &RHS = SC->getAPInt();693    if (RHS.isPowerOf2())694      return InsertBinop(Instruction::LShr, LHS,695                         ConstantInt::get(SC->getType(), RHS.logBase2()),696                         SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);697  }698 699  const SCEV *RHSExpr = S->getRHS();700  Value *RHS = expand(RHSExpr);701  if (SafeUDivMode) {702    bool GuaranteedNotPoison =703        ScalarEvolution::isGuaranteedNotToBePoison(RHSExpr);704    if (!GuaranteedNotPoison)705      RHS = Builder.CreateFreeze(RHS);706 707    // We need an umax if either RHSExpr is not known to be zero, or if it is708    // not guaranteed to be non-poison. In the later case, the frozen poison may709    // be 0.710    if (!SE.isKnownNonZero(RHSExpr) || !GuaranteedNotPoison)711      RHS = Builder.CreateIntrinsic(RHS->getType(), Intrinsic::umax,712                                    {RHS, ConstantInt::get(RHS->getType(), 1)});713  }714  return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap,715                     /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS()));716}717 718/// Determine if this is a well-behaved chain of instructions leading back to719/// the PHI. If so, it may be reused by expanded expressions.720bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,721                                         const Loop *L) {722  if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) ||723      (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))724    return false;725  // If any of the operands don't dominate the insert position, bail.726  // Addrec operands are always loop-invariant, so this can only happen727  // if there are instructions which haven't been hoisted.728  if (L == IVIncInsertLoop) {729    for (Use &Op : llvm::drop_begin(IncV->operands()))730      if (Instruction *OInst = dyn_cast<Instruction>(Op))731        if (!SE.DT.dominates(OInst, IVIncInsertPos))732          return false;733  }734  // Advance to the next instruction.735  IncV = dyn_cast<Instruction>(IncV->getOperand(0));736  if (!IncV)737    return false;738 739  if (IncV->mayHaveSideEffects())740    return false;741 742  if (IncV == PN)743    return true;744 745  return isNormalAddRecExprPHI(PN, IncV, L);746}747 748/// getIVIncOperand returns an induction variable increment's induction749/// variable operand.750///751/// If allowScale is set, any type of GEP is allowed as long as the nonIV752/// operands dominate InsertPos.753///754/// If allowScale is not set, ensure that a GEP increment conforms to one of the755/// simple patterns generated by getAddRecExprPHILiterally and756/// expandAddtoGEP. If the pattern isn't recognized, return NULL.757Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV,758                                           Instruction *InsertPos,759                                           bool allowScale) {760  if (IncV == InsertPos)761    return nullptr;762 763  switch (IncV->getOpcode()) {764  default:765    return nullptr;766  // Check for a simple Add/Sub or GEP of a loop invariant step.767  case Instruction::Add:768  case Instruction::Sub: {769    Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));770    if (!OInst || SE.DT.dominates(OInst, InsertPos))771      return dyn_cast<Instruction>(IncV->getOperand(0));772    return nullptr;773  }774  case Instruction::BitCast:775    return dyn_cast<Instruction>(IncV->getOperand(0));776  case Instruction::GetElementPtr:777    for (Use &U : llvm::drop_begin(IncV->operands())) {778      if (isa<Constant>(U))779        continue;780      if (Instruction *OInst = dyn_cast<Instruction>(U)) {781        if (!SE.DT.dominates(OInst, InsertPos))782          return nullptr;783      }784      if (allowScale) {785        // allow any kind of GEP as long as it can be hoisted.786        continue;787      }788      // GEPs produced by SCEVExpander use i8 element type.789      if (!cast<GEPOperator>(IncV)->getSourceElementType()->isIntegerTy(8))790        return nullptr;791      break;792    }793    return dyn_cast<Instruction>(IncV->getOperand(0));794  }795}796 797/// If the insert point of the current builder or any of the builders on the798/// stack of saved builders has 'I' as its insert point, update it to point to799/// the instruction after 'I'.  This is intended to be used when the instruction800/// 'I' is being moved.  If this fixup is not done and 'I' is moved to a801/// different block, the inconsistent insert point (with a mismatched802/// Instruction and Block) can lead to an instruction being inserted in a block803/// other than its parent.804void SCEVExpander::fixupInsertPoints(Instruction *I) {805  BasicBlock::iterator It(*I);806  BasicBlock::iterator NewInsertPt = std::next(It);807  if (Builder.GetInsertPoint() == It)808    Builder.SetInsertPoint(&*NewInsertPt);809  for (auto *InsertPtGuard : InsertPointGuards)810    if (InsertPtGuard->GetInsertPoint() == It)811      InsertPtGuard->SetInsertPoint(NewInsertPt);812}813 814/// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make815/// it available to other uses in this loop. Recursively hoist any operands,816/// until we reach a value that dominates InsertPos.817bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos,818                              bool RecomputePoisonFlags) {819  auto FixupPoisonFlags = [this](Instruction *I) {820    // Drop flags that are potentially inferred from old context and infer flags821    // in new context.822    rememberFlags(I);823    I->dropPoisonGeneratingFlags();824    if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(I))825      if (auto Flags = SE.getStrengthenedNoWrapFlagsFromBinOp(OBO)) {826        auto *BO = cast<BinaryOperator>(I);827        BO->setHasNoUnsignedWrap(828            ScalarEvolution::maskFlags(*Flags, SCEV::FlagNUW) == SCEV::FlagNUW);829        BO->setHasNoSignedWrap(830            ScalarEvolution::maskFlags(*Flags, SCEV::FlagNSW) == SCEV::FlagNSW);831      }832  };833 834  if (SE.DT.dominates(IncV, InsertPos)) {835    if (RecomputePoisonFlags)836      FixupPoisonFlags(IncV);837    return true;838  }839 840  // InsertPos must itself dominate IncV so that IncV's new position satisfies841  // its existing users.842  if (isa<PHINode>(InsertPos) ||843      !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))844    return false;845 846  if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))847    return false;848 849  // Check that the chain of IV operands leading back to Phi can be hoisted.850  SmallVector<Instruction*, 4> IVIncs;851  for(;;) {852    Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true);853    if (!Oper)854      return false;855    // IncV is safe to hoist.856    IVIncs.push_back(IncV);857    IncV = Oper;858    if (SE.DT.dominates(IncV, InsertPos))859      break;860  }861  for (Instruction *I : llvm::reverse(IVIncs)) {862    fixupInsertPoints(I);863    I->moveBefore(InsertPos->getIterator());864    if (RecomputePoisonFlags)865      FixupPoisonFlags(I);866  }867  return true;868}869 870bool SCEVExpander::canReuseFlagsFromOriginalIVInc(PHINode *OrigPhi,871                                                  PHINode *WidePhi,872                                                  Instruction *OrigInc,873                                                  Instruction *WideInc) {874  return match(OrigInc, m_c_BinOp(m_Specific(OrigPhi), m_Value())) &&875         match(WideInc, m_c_BinOp(m_Specific(WidePhi), m_Value())) &&876         OrigInc->getOpcode() == WideInc->getOpcode();877}878 879/// Determine if this cyclic phi is in a form that would have been generated by880/// LSR. We don't care if the phi was actually expanded in this pass, as long881/// as it is in a low-cost form, for example, no implied multiplication. This882/// should match any patterns generated by getAddRecExprPHILiterally and883/// expandAddtoGEP.884bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,885                                           const Loop *L) {886  for(Instruction *IVOper = IncV;887      (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),888                                /*allowScale=*/false));) {889    if (IVOper == PN)890      return true;891  }892  return false;893}894 895/// expandIVInc - Expand an IV increment at Builder's current InsertPos.896/// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may897/// need to materialize IV increments elsewhere to handle difficult situations.898Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L,899                                 bool useSubtract) {900  Value *IncV;901  // If the PHI is a pointer, use a GEP, otherwise use an add or sub.902  if (PN->getType()->isPointerTy()) {903    // TODO: Change name to IVName.iv.next.904    IncV = Builder.CreatePtrAdd(PN, StepV, "scevgep");905  } else {906    IncV = useSubtract ?907      Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") :908      Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next");909  }910  return IncV;911}912 913/// Check whether we can cheaply express the requested SCEV in terms of914/// the available PHI SCEV by truncation and/or inversion of the step.915static bool canBeCheaplyTransformed(ScalarEvolution &SE,916                                    const SCEVAddRecExpr *Phi,917                                    const SCEVAddRecExpr *Requested,918                                    bool &InvertStep) {919  // We can't transform to match a pointer PHI.920  Type *PhiTy = Phi->getType();921  Type *RequestedTy = Requested->getType();922  if (PhiTy->isPointerTy() || RequestedTy->isPointerTy())923    return false;924 925  if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth())926    return false;927 928  // Try truncate it if necessary.929  Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy));930  if (!Phi)931    return false;932 933  // Check whether truncation will help.934  if (Phi == Requested) {935    InvertStep = false;936    return true;937  }938 939  // Check whether inverting will help: {R,+,-1} == R - {0,+,1}.940  if (SE.getMinusSCEV(Requested->getStart(), Requested) == Phi) {941    InvertStep = true;942    return true;943  }944 945  return false;946}947 948static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {949  if (!isa<IntegerType>(AR->getType()))950    return false;951 952  unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();953  Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);954  const SCEV *Step = AR->getStepRecurrence(SE);955  const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy),956                                            SE.getSignExtendExpr(AR, WideTy));957  const SCEV *ExtendAfterOp =958    SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy);959  return ExtendAfterOp == OpAfterExtend;960}961 962static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {963  if (!isa<IntegerType>(AR->getType()))964    return false;965 966  unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();967  Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);968  const SCEV *Step = AR->getStepRecurrence(SE);969  const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy),970                                            SE.getZeroExtendExpr(AR, WideTy));971  const SCEV *ExtendAfterOp =972    SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy);973  return ExtendAfterOp == OpAfterExtend;974}975 976/// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand977/// the base addrec, which is the addrec without any non-loop-dominating978/// values, and return the PHI.979PHINode *980SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,981                                        const Loop *L, Type *&TruncTy,982                                        bool &InvertStep) {983  assert((!IVIncInsertLoop || IVIncInsertPos) &&984         "Uninitialized insert position");985 986  // Reuse a previously-inserted PHI, if present.987  BasicBlock *LatchBlock = L->getLoopLatch();988  if (LatchBlock) {989    PHINode *AddRecPhiMatch = nullptr;990    Instruction *IncV = nullptr;991    TruncTy = nullptr;992    InvertStep = false;993 994    // Only try partially matching scevs that need truncation and/or995    // step-inversion if we know this loop is outside the current loop.996    bool TryNonMatchingSCEV =997        IVIncInsertLoop &&998        SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());999 1000    for (PHINode &PN : L->getHeader()->phis()) {1001      if (!SE.isSCEVable(PN.getType()))1002        continue;1003 1004      // We should not look for a incomplete PHI. Getting SCEV for a incomplete1005      // PHI has no meaning at all.1006      if (!PN.isComplete()) {1007        SCEV_DEBUG_WITH_TYPE(1008            DebugType, dbgs() << "One incomplete PHI is found: " << PN << "\n");1009        continue;1010      }1011 1012      const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));1013      if (!PhiSCEV)1014        continue;1015 1016      bool IsMatchingSCEV = PhiSCEV == Normalized;1017      // We only handle truncation and inversion of phi recurrences for the1018      // expanded expression if the expanded expression's loop dominates the1019      // loop we insert to. Check now, so we can bail out early.1020      if (!IsMatchingSCEV && !TryNonMatchingSCEV)1021          continue;1022 1023      // TODO: this possibly can be reworked to avoid this cast at all.1024      Instruction *TempIncV =1025          dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));1026      if (!TempIncV)1027        continue;1028 1029      // Check whether we can reuse this PHI node.1030      if (LSRMode) {1031        if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))1032          continue;1033      } else {1034        if (!isNormalAddRecExprPHI(&PN, TempIncV, L))1035          continue;1036      }1037 1038      // Stop if we have found an exact match SCEV.1039      if (IsMatchingSCEV) {1040        IncV = TempIncV;1041        TruncTy = nullptr;1042        InvertStep = false;1043        AddRecPhiMatch = &PN;1044        break;1045      }1046 1047      // Try whether the phi can be translated into the requested form1048      // (truncated and/or offset by a constant).1049      if ((!TruncTy || InvertStep) &&1050          canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) {1051        // Record the phi node. But don't stop we might find an exact match1052        // later.1053        AddRecPhiMatch = &PN;1054        IncV = TempIncV;1055        TruncTy = Normalized->getType();1056      }1057    }1058 1059    if (AddRecPhiMatch) {1060      // Ok, the add recurrence looks usable.1061      // Remember this PHI, even in post-inc mode.1062      InsertedValues.insert(AddRecPhiMatch);1063      // Remember the increment.1064      rememberInstruction(IncV);1065      // Those values were not actually inserted but re-used.1066      ReusedValues.insert(AddRecPhiMatch);1067      ReusedValues.insert(IncV);1068      return AddRecPhiMatch;1069    }1070  }1071 1072  // Save the original insertion point so we can restore it when we're done.1073  SCEVInsertPointGuard Guard(Builder, this);1074 1075  // Another AddRec may need to be recursively expanded below. For example, if1076  // this AddRec is quadratic, the StepV may itself be an AddRec in this1077  // loop. Remove this loop from the PostIncLoops set before expanding such1078  // AddRecs. Otherwise, we cannot find a valid position for the step1079  // (i.e. StepV can never dominate its loop header).  Ideally, we could do1080  // SavedIncLoops.swap(PostIncLoops), but we generally have a single element,1081  // so it's not worth implementing SmallPtrSet::swap.1082  PostIncLoopSet SavedPostIncLoops = PostIncLoops;1083  PostIncLoops.clear();1084 1085  // Expand code for the start value into the loop preheader.1086  assert(L->getLoopPreheader() &&1087         "Can't expand add recurrences without a loop preheader!");1088  Value *StartV =1089      expand(Normalized->getStart(), L->getLoopPreheader()->getTerminator());1090 1091  // StartV must have been be inserted into L's preheader to dominate the new1092  // phi.1093  assert(!isa<Instruction>(StartV) ||1094         SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),1095                                 L->getHeader()));1096 1097  // Expand code for the step value. Do this before creating the PHI so that PHI1098  // reuse code doesn't see an incomplete PHI.1099  const SCEV *Step = Normalized->getStepRecurrence(SE);1100  Type *ExpandTy = Normalized->getType();1101  // If the stride is negative, insert a sub instead of an add for the increment1102  // (unless it's a constant, because subtracts of constants are canonicalized1103  // to adds).1104  bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative();1105  if (useSubtract)1106    Step = SE.getNegativeSCEV(Step);1107  // Expand the step somewhere that dominates the loop header.1108  Value *StepV = expand(Step, L->getHeader()->getFirstInsertionPt());1109 1110  // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if1111  // we actually do emit an addition.  It does not apply if we emit a1112  // subtraction.1113  bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized);1114  bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized);1115 1116  // Create the PHI.1117  BasicBlock *Header = L->getHeader();1118  Builder.SetInsertPoint(Header, Header->begin());1119  PHINode *PN =1120      Builder.CreatePHI(ExpandTy, pred_size(Header), Twine(IVName) + ".iv");1121 1122  // Create the step instructions and populate the PHI.1123  for (BasicBlock *Pred : predecessors(Header)) {1124    // Add a start value.1125    if (!L->contains(Pred)) {1126      PN->addIncoming(StartV, Pred);1127      continue;1128    }1129 1130    // Create a step value and add it to the PHI.1131    // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the1132    // instructions at IVIncInsertPos.1133    Instruction *InsertPos = L == IVIncInsertLoop ?1134      IVIncInsertPos : Pred->getTerminator();1135    Builder.SetInsertPoint(InsertPos);1136    Value *IncV = expandIVInc(PN, StepV, L, useSubtract);1137 1138    if (isa<OverflowingBinaryOperator>(IncV)) {1139      if (IncrementIsNUW)1140        cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();1141      if (IncrementIsNSW)1142        cast<BinaryOperator>(IncV)->setHasNoSignedWrap();1143    }1144    PN->addIncoming(IncV, Pred);1145  }1146 1147  // After expanding subexpressions, restore the PostIncLoops set so the caller1148  // can ensure that IVIncrement dominates the current uses.1149  PostIncLoops = SavedPostIncLoops;1150 1151  // Remember this PHI, even in post-inc mode. LSR SCEV-based salvaging is most1152  // effective when we are able to use an IV inserted here, so record it.1153  InsertedValues.insert(PN);1154  InsertedIVs.push_back(PN);1155  return PN;1156}1157 1158Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {1159  const Loop *L = S->getLoop();1160 1161  // Determine a normalized form of this expression, which is the expression1162  // before any post-inc adjustment is made.1163  const SCEVAddRecExpr *Normalized = S;1164  if (PostIncLoops.count(L)) {1165    PostIncLoopSet Loops;1166    Loops.insert(L);1167    Normalized = cast<SCEVAddRecExpr>(1168        normalizeForPostIncUse(S, Loops, SE, /*CheckInvertible=*/false));1169  }1170 1171  [[maybe_unused]] const SCEV *Start = Normalized->getStart();1172  const SCEV *Step = Normalized->getStepRecurrence(SE);1173  assert(SE.properlyDominates(Start, L->getHeader()) &&1174         "Start does not properly dominate loop header");1175  assert(SE.dominates(Step, L->getHeader()) && "Step not dominate loop header");1176 1177  // In some cases, we decide to reuse an existing phi node but need to truncate1178  // it and/or invert the step.1179  Type *TruncTy = nullptr;1180  bool InvertStep = false;1181  PHINode *PN = getAddRecExprPHILiterally(Normalized, L, TruncTy, InvertStep);1182 1183  // Accommodate post-inc mode, if necessary.1184  Value *Result;1185  if (!PostIncLoops.count(L))1186    Result = PN;1187  else {1188    // In PostInc mode, use the post-incremented value.1189    BasicBlock *LatchBlock = L->getLoopLatch();1190    assert(LatchBlock && "PostInc mode requires a unique loop latch!");1191    Result = PN->getIncomingValueForBlock(LatchBlock);1192 1193    // We might be introducing a new use of the post-inc IV that is not poison1194    // safe, in which case we should drop poison generating flags. Only keep1195    // those flags for which SCEV has proven that they always hold.1196    if (isa<OverflowingBinaryOperator>(Result)) {1197      auto *I = cast<Instruction>(Result);1198      if (!S->hasNoUnsignedWrap())1199        I->setHasNoUnsignedWrap(false);1200      if (!S->hasNoSignedWrap())1201        I->setHasNoSignedWrap(false);1202    }1203 1204    // For an expansion to use the postinc form, the client must call1205    // expandCodeFor with an InsertPoint that is either outside the PostIncLoop1206    // or dominated by IVIncInsertPos.1207    if (isa<Instruction>(Result) &&1208        !SE.DT.dominates(cast<Instruction>(Result),1209                         &*Builder.GetInsertPoint())) {1210      // The induction variable's postinc expansion does not dominate this use.1211      // IVUsers tries to prevent this case, so it is rare. However, it can1212      // happen when an IVUser outside the loop is not dominated by the latch1213      // block. Adjusting IVIncInsertPos before expansion begins cannot handle1214      // all cases. Consider a phi outside whose operand is replaced during1215      // expansion with the value of the postinc user. Without fundamentally1216      // changing the way postinc users are tracked, the only remedy is1217      // inserting an extra IV increment. StepV might fold into PostLoopOffset,1218      // but hopefully expandCodeFor handles that.1219      bool useSubtract =1220          !S->getType()->isPointerTy() && Step->isNonConstantNegative();1221      if (useSubtract)1222        Step = SE.getNegativeSCEV(Step);1223      Value *StepV;1224      {1225        // Expand the step somewhere that dominates the loop header.1226        SCEVInsertPointGuard Guard(Builder, this);1227        StepV = expand(Step, L->getHeader()->getFirstInsertionPt());1228      }1229      Result = expandIVInc(PN, StepV, L, useSubtract);1230    }1231  }1232 1233  // We have decided to reuse an induction variable of a dominating loop. Apply1234  // truncation and/or inversion of the step.1235  if (TruncTy) {1236    // Truncate the result.1237    if (TruncTy != Result->getType())1238      Result = Builder.CreateTrunc(Result, TruncTy);1239 1240    // Invert the result.1241    if (InvertStep)1242      Result = Builder.CreateSub(expand(Normalized->getStart()), Result);1243  }1244 1245  return Result;1246}1247 1248Value *SCEVExpander::tryToReuseLCSSAPhi(const SCEVAddRecExpr *S) {1249  Type *STy = S->getType();1250  const Loop *L = S->getLoop();1251  BasicBlock *EB = L->getExitBlock();1252  if (!EB || !EB->getSinglePredecessor() ||1253      !SE.DT.dominates(EB, Builder.GetInsertBlock()))1254    return nullptr;1255 1256  for (auto &PN : EB->phis()) {1257    if (!SE.isSCEVable(PN.getType()))1258      continue;1259    auto *ExitSCEV = SE.getSCEV(&PN);1260    if (!isa<SCEVAddRecExpr>(ExitSCEV))1261      continue;1262    Type *PhiTy = PN.getType();1263    if (STy->isIntegerTy() && PhiTy->isPointerTy()) {1264      ExitSCEV = SE.getPtrToIntExpr(ExitSCEV, STy);1265      if (isa<SCEVCouldNotCompute>(ExitSCEV))1266        continue;1267    } else if (S->getType() != PN.getType()) {1268      continue;1269    }1270 1271    // Check if we can re-use the existing PN, by adjusting it with an expanded1272    // offset, if the offset is simpler.1273    const SCEV *Diff = SE.getMinusSCEV(S, ExitSCEV);1274    const SCEV *Op = Diff;1275    match(Op, m_scev_Add(m_SCEVConstant(), m_SCEV(Op)));1276    match(Op, m_scev_Mul(m_scev_AllOnes(), m_SCEV(Op)));1277    match(Op, m_scev_PtrToInt(m_SCEV(Op)));1278    if (!isa<SCEVConstant, SCEVUnknown>(Op))1279      continue;1280 1281    assert(Diff->getType()->isIntegerTy() &&1282           "difference must be of integer type");1283    Value *DiffV = expand(Diff);1284    Value *BaseV = fixupLCSSAFormFor(&PN);1285    if (PhiTy->isPointerTy()) {1286      if (STy->isPointerTy())1287        return Builder.CreatePtrAdd(BaseV, DiffV);1288      BaseV = Builder.CreatePtrToInt(BaseV, DiffV->getType());1289    }1290    return Builder.CreateAdd(BaseV, DiffV);1291  }1292 1293  return nullptr;1294}1295 1296Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {1297  // In canonical mode we compute the addrec as an expression of a canonical IV1298  // using evaluateAtIteration and expand the resulting SCEV expression. This1299  // way we avoid introducing new IVs to carry on the computation of the addrec1300  // throughout the loop.1301  //1302  // For nested addrecs evaluateAtIteration might need a canonical IV of a1303  // type wider than the addrec itself. Emitting a canonical IV of the1304  // proper type might produce non-legal types, for example expanding an i641305  // {0,+,2,+,1} addrec would need an i65 canonical IV. To avoid this just fall1306  // back to non-canonical mode for nested addrecs.1307  if (!CanonicalMode || (S->getNumOperands() > 2))1308    return expandAddRecExprLiterally(S);1309 1310  Type *Ty = SE.getEffectiveSCEVType(S->getType());1311  const Loop *L = S->getLoop();1312 1313  // First check for an existing canonical IV in a suitable type.1314  PHINode *CanonicalIV = nullptr;1315  if (PHINode *PN = L->getCanonicalInductionVariable())1316    if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))1317      CanonicalIV = PN;1318 1319  // Rewrite an AddRec in terms of the canonical induction variable, if1320  // its type is more narrow.1321  if (CanonicalIV &&1322      SE.getTypeSizeInBits(CanonicalIV->getType()) > SE.getTypeSizeInBits(Ty) &&1323      !S->getType()->isPointerTy()) {1324    SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());1325    for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)1326      NewOps[i] = SE.getAnyExtendExpr(S->getOperand(i), CanonicalIV->getType());1327    Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),1328                                       S->getNoWrapFlags(SCEV::FlagNW)));1329    BasicBlock::iterator NewInsertPt =1330        findInsertPointAfter(cast<Instruction>(V), &*Builder.GetInsertPoint());1331    V = expand(SE.getTruncateExpr(SE.getUnknown(V), Ty), NewInsertPt);1332    return V;1333  }1334 1335  // If S is expanded outside the defining loop, check if there is a1336  // matching LCSSA phi node for it.1337  if (Value *V = tryToReuseLCSSAPhi(S))1338    return V;1339 1340  // {X,+,F} --> X + {0,+,F}1341  if (!S->getStart()->isZero()) {1342    if (isa<PointerType>(S->getType())) {1343      Value *StartV = expand(SE.getPointerBase(S));1344      return expandAddToGEP(SE.removePointerBase(S), StartV,1345                            S->getNoWrapFlags(SCEV::FlagNUW));1346    }1347 1348    SmallVector<const SCEV *, 4> NewOps(S->operands());1349    NewOps[0] = SE.getConstant(Ty, 0);1350    const SCEV *Rest = SE.getAddRecExpr(NewOps, L,1351                                        S->getNoWrapFlags(SCEV::FlagNW));1352 1353    // Just do a normal add. Pre-expand the operands to suppress folding.1354    //1355    // The LHS and RHS values are factored out of the expand call to make the1356    // output independent of the argument evaluation order.1357    const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart()));1358    const SCEV *AddExprRHS = SE.getUnknown(expand(Rest));1359    return expand(SE.getAddExpr(AddExprLHS, AddExprRHS));1360  }1361 1362  // If we don't yet have a canonical IV, create one.1363  if (!CanonicalIV) {1364    // Create and insert the PHI node for the induction variable in the1365    // specified loop.1366    BasicBlock *Header = L->getHeader();1367    pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);1368    CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar");1369    CanonicalIV->insertBefore(Header->begin());1370    rememberInstruction(CanonicalIV);1371 1372    SmallPtrSet<BasicBlock *, 4> PredSeen;1373    Constant *One = ConstantInt::get(Ty, 1);1374    for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {1375      BasicBlock *HP = *HPI;1376      if (!PredSeen.insert(HP).second) {1377        // There must be an incoming value for each predecessor, even the1378        // duplicates!1379        CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP);1380        continue;1381      }1382 1383      if (L->contains(HP)) {1384        // Insert a unit add instruction right before the terminator1385        // corresponding to the back-edge.1386        Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One,1387                                                     "indvar.next",1388                                                     HP->getTerminator()->getIterator());1389        Add->setDebugLoc(HP->getTerminator()->getDebugLoc());1390        rememberInstruction(Add);1391        CanonicalIV->addIncoming(Add, HP);1392      } else {1393        CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP);1394      }1395    }1396  }1397 1398  // {0,+,1} --> Insert a canonical induction variable into the loop!1399  if (S->isAffine() && S->getOperand(1)->isOne()) {1400    assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&1401           "IVs with types different from the canonical IV should "1402           "already have been handled!");1403    return CanonicalIV;1404  }1405 1406  // {0,+,F} --> {0,+,1} * F1407 1408  // If this is a simple linear addrec, emit it now as a special case.1409  if (S->isAffine())    // {0,+,F} --> i*F1410    return1411      expand(SE.getTruncateOrNoop(1412        SE.getMulExpr(SE.getUnknown(CanonicalIV),1413                      SE.getNoopOrAnyExtend(S->getOperand(1),1414                                            CanonicalIV->getType())),1415        Ty));1416 1417  // If this is a chain of recurrences, turn it into a closed form, using the1418  // folders, then expandCodeFor the closed form.  This allows the folders to1419  // simplify the expression without having to build a bunch of special code1420  // into this folder.1421  const SCEV *IH = SE.getUnknown(CanonicalIV);   // Get I as a "symbolic" SCEV.1422 1423  // Promote S up to the canonical IV type, if the cast is foldable.1424  const SCEV *NewS = S;1425  const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType());1426  if (isa<SCEVAddRecExpr>(Ext))1427    NewS = Ext;1428 1429  const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);1430 1431  // Truncate the result down to the original type, if needed.1432  const SCEV *T = SE.getTruncateOrNoop(V, Ty);1433  return expand(T);1434}1435 1436Value *SCEVExpander::visitPtrToIntExpr(const SCEVPtrToIntExpr *S) {1437  Value *V = expand(S->getOperand());1438  return ReuseOrCreateCast(V, S->getType(), CastInst::PtrToInt,1439                           GetOptimalInsertionPointForCastOf(V));1440}1441 1442Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {1443  Value *V = expand(S->getOperand());1444  return Builder.CreateTrunc(V, S->getType());1445}1446 1447Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {1448  Value *V = expand(S->getOperand());1449  return Builder.CreateZExt(V, S->getType(), "",1450                            SE.isKnownNonNegative(S->getOperand()));1451}1452 1453Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {1454  Value *V = expand(S->getOperand());1455  return Builder.CreateSExt(V, S->getType());1456}1457 1458Value *SCEVExpander::expandMinMaxExpr(const SCEVNAryExpr *S,1459                                      Intrinsic::ID IntrinID, Twine Name,1460                                      bool IsSequential) {1461  bool PrevSafeMode = SafeUDivMode;1462  SafeUDivMode |= IsSequential;1463  Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));1464  Type *Ty = LHS->getType();1465  if (IsSequential)1466    LHS = Builder.CreateFreeze(LHS);1467  for (int i = S->getNumOperands() - 2; i >= 0; --i) {1468    SafeUDivMode = (IsSequential && i != 0) || PrevSafeMode;1469    Value *RHS = expand(S->getOperand(i));1470    if (IsSequential && i != 0)1471      RHS = Builder.CreateFreeze(RHS);1472    Value *Sel;1473    if (Ty->isIntegerTy())1474      Sel = Builder.CreateIntrinsic(IntrinID, {Ty}, {LHS, RHS},1475                                    /*FMFSource=*/nullptr, Name);1476    else {1477      Value *ICmp =1478          Builder.CreateICmp(MinMaxIntrinsic::getPredicate(IntrinID), LHS, RHS);1479      Sel = Builder.CreateSelect(ICmp, LHS, RHS, Name);1480    }1481    LHS = Sel;1482  }1483  SafeUDivMode = PrevSafeMode;1484  return LHS;1485}1486 1487Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {1488  return expandMinMaxExpr(S, Intrinsic::smax, "smax");1489}1490 1491Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {1492  return expandMinMaxExpr(S, Intrinsic::umax, "umax");1493}1494 1495Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) {1496  return expandMinMaxExpr(S, Intrinsic::smin, "smin");1497}1498 1499Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {1500  return expandMinMaxExpr(S, Intrinsic::umin, "umin");1501}1502 1503Value *SCEVExpander::visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S) {1504  return expandMinMaxExpr(S, Intrinsic::umin, "umin", /*IsSequential*/true);1505}1506 1507Value *SCEVExpander::visitVScale(const SCEVVScale *S) {1508  return Builder.CreateVScale(S->getType());1509}1510 1511Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty,1512                                   BasicBlock::iterator IP) {1513  setInsertPoint(IP);1514  Value *V = expandCodeFor(SH, Ty);1515  return V;1516}1517 1518Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) {1519  // Expand the code for this SCEV.1520  Value *V = expand(SH);1521 1522  if (Ty && Ty != V->getType()) {1523    assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&1524           "non-trivial casts should be done with the SCEVs directly!");1525    V = InsertNoopCastOfTo(V, Ty);1526  }1527  return V;1528}1529 1530Value *SCEVExpander::FindValueInExprValueMap(1531    const SCEV *S, const Instruction *InsertPt,1532    SmallVectorImpl<Instruction *> &DropPoisonGeneratingInsts) {1533  // If the expansion is not in CanonicalMode, and the SCEV contains any1534  // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.1535  if (!CanonicalMode && SE.containsAddRecurrence(S))1536    return nullptr;1537 1538  // If S is a constant or unknown, it may be worse to reuse an existing Value.1539  if (isa<SCEVConstant>(S) || isa<SCEVUnknown>(S))1540    return nullptr;1541 1542  for (Value *V : SE.getSCEVValues(S)) {1543    Instruction *EntInst = dyn_cast<Instruction>(V);1544    if (!EntInst)1545      continue;1546 1547    // Choose a Value from the set which dominates the InsertPt.1548    // InsertPt should be inside the Value's parent loop so as not to break1549    // the LCSSA form.1550    assert(EntInst->getFunction() == InsertPt->getFunction());1551    if (S->getType() != V->getType() || !SE.DT.dominates(EntInst, InsertPt) ||1552        !(SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||1553          SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))1554      continue;1555 1556    // Make sure reusing the instruction is poison-safe.1557    if (SE.canReuseInstruction(S, EntInst, DropPoisonGeneratingInsts))1558      return V;1559    DropPoisonGeneratingInsts.clear();1560  }1561  return nullptr;1562}1563 1564// The expansion of SCEV will either reuse a previous Value in ExprValueMap,1565// or expand the SCEV literally. Specifically, if the expansion is in LSRMode,1566// and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded1567// literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,1568// the expansion will try to reuse Value from ExprValueMap, and only when it1569// fails, expand the SCEV literally.1570Value *SCEVExpander::expand(const SCEV *S) {1571  // Compute an insertion point for this SCEV object. Hoist the instructions1572  // as far out in the loop nest as possible.1573  BasicBlock::iterator InsertPt = Builder.GetInsertPoint();1574 1575  // We can move insertion point only if there is no div or rem operations1576  // otherwise we are risky to move it over the check for zero denominator.1577  auto SafeToHoist = [](const SCEV *S) {1578    return !SCEVExprContains(S, [](const SCEV *S) {1579              if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) {1580                if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS()))1581                  // Division by non-zero constants can be hoisted.1582                  return SC->getValue()->isZero();1583                // All other divisions should not be moved as they may be1584                // divisions by zero and should be kept within the1585                // conditions of the surrounding loops that guard their1586                // execution (see PR35406).1587                return true;1588              }1589              return false;1590            });1591  };1592  if (SafeToHoist(S)) {1593    for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;1594         L = L->getParentLoop()) {1595      if (SE.isLoopInvariant(S, L)) {1596        if (!L) break;1597        if (BasicBlock *Preheader = L->getLoopPreheader()) {1598          InsertPt = Preheader->getTerminator()->getIterator();1599        } else {1600          // LSR sets the insertion point for AddRec start/step values to the1601          // block start to simplify value reuse, even though it's an invalid1602          // position. SCEVExpander must correct for this in all cases.1603          InsertPt = L->getHeader()->getFirstInsertionPt();1604        }1605      } else {1606        // If the SCEV is computable at this level, insert it into the header1607        // after the PHIs (and after any other instructions that we've inserted1608        // there) so that it is guaranteed to dominate any user inside the loop.1609        if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))1610          InsertPt = L->getHeader()->getFirstInsertionPt();1611 1612        while (InsertPt != Builder.GetInsertPoint() &&1613               (isInsertedInstruction(&*InsertPt))) {1614          InsertPt = std::next(InsertPt);1615        }1616        break;1617      }1618    }1619  }1620 1621  // Check to see if we already expanded this here.1622  auto I = InsertedExpressions.find(std::make_pair(S, &*InsertPt));1623  if (I != InsertedExpressions.end())1624    return I->second;1625 1626  SCEVInsertPointGuard Guard(Builder, this);1627  Builder.SetInsertPoint(InsertPt->getParent(), InsertPt);1628 1629  // Expand the expression into instructions.1630  SmallVector<Instruction *> DropPoisonGeneratingInsts;1631  Value *V = FindValueInExprValueMap(S, &*InsertPt, DropPoisonGeneratingInsts);1632  if (!V) {1633    V = visit(S);1634    V = fixupLCSSAFormFor(V);1635  } else {1636    for (Instruction *I : DropPoisonGeneratingInsts) {1637      rememberFlags(I);1638      I->dropPoisonGeneratingAnnotations();1639      // See if we can re-infer from first principles any of the flags we just1640      // dropped.1641      if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(I))1642        if (auto Flags = SE.getStrengthenedNoWrapFlagsFromBinOp(OBO)) {1643          auto *BO = cast<BinaryOperator>(I);1644          BO->setHasNoUnsignedWrap(1645            ScalarEvolution::maskFlags(*Flags, SCEV::FlagNUW) == SCEV::FlagNUW);1646          BO->setHasNoSignedWrap(1647            ScalarEvolution::maskFlags(*Flags, SCEV::FlagNSW) == SCEV::FlagNSW);1648        }1649      if (auto *NNI = dyn_cast<PossiblyNonNegInst>(I)) {1650        auto *Src = NNI->getOperand(0);1651        if (isImpliedByDomCondition(ICmpInst::ICMP_SGE, Src,1652                                    Constant::getNullValue(Src->getType()), I,1653                                    DL).value_or(false))1654          NNI->setNonNeg(true);1655      }1656    }1657  }1658  // Remember the expanded value for this SCEV at this location.1659  //1660  // This is independent of PostIncLoops. The mapped value simply materializes1661  // the expression at this insertion point. If the mapped value happened to be1662  // a postinc expansion, it could be reused by a non-postinc user, but only if1663  // its insertion point was already at the head of the loop.1664  InsertedExpressions[std::make_pair(S, &*InsertPt)] = V;1665  return V;1666}1667 1668void SCEVExpander::rememberInstruction(Value *I) {1669  auto DoInsert = [this](Value *V) {1670    if (!PostIncLoops.empty())1671      InsertedPostIncValues.insert(V);1672    else1673      InsertedValues.insert(V);1674  };1675  DoInsert(I);1676}1677 1678void SCEVExpander::rememberFlags(Instruction *I) {1679  // If we already have flags for the instruction, keep the existing ones.1680  OrigFlags.try_emplace(I, PoisonFlags(I));1681}1682 1683void SCEVExpander::replaceCongruentIVInc(1684    PHINode *&Phi, PHINode *&OrigPhi, Loop *L, const DominatorTree *DT,1685    SmallVectorImpl<WeakTrackingVH> &DeadInsts) {1686  BasicBlock *LatchBlock = L->getLoopLatch();1687  if (!LatchBlock)1688    return;1689 1690  Instruction *OrigInc =1691      dyn_cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));1692  Instruction *IsomorphicInc =1693      dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));1694  if (!OrigInc || !IsomorphicInc)1695    return;1696 1697  // If this phi has the same width but is more canonical, replace the1698  // original with it. As part of the "more canonical" determination,1699  // respect a prior decision to use an IV chain.1700  if (OrigPhi->getType() == Phi->getType()) {1701    bool Chained = ChainedPhis.contains(Phi);1702    if (!(Chained || isExpandedAddRecExprPHI(OrigPhi, OrigInc, L)) &&1703        (Chained || isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {1704      std::swap(OrigPhi, Phi);1705      std::swap(OrigInc, IsomorphicInc);1706    }1707  }1708 1709  // Replacing the congruent phi is sufficient because acyclic1710  // redundancy elimination, CSE/GVN, should handle the1711  // rest. However, once SCEV proves that a phi is congruent,1712  // it's often the head of an IV user cycle that is isomorphic1713  // with the original phi. It's worth eagerly cleaning up the1714  // common case of a single IV increment so that DeleteDeadPHIs1715  // can remove cycles that had postinc uses.1716  // Because we may potentially introduce a new use of OrigIV that didn't1717  // exist before at this point, its poison flags need readjustment.1718  const SCEV *TruncExpr =1719      SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->getType());1720  if (OrigInc == IsomorphicInc || TruncExpr != SE.getSCEV(IsomorphicInc) ||1721      !SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc))1722    return;1723 1724  bool BothHaveNUW = false;1725  bool BothHaveNSW = false;1726  auto *OBOIncV = dyn_cast<OverflowingBinaryOperator>(OrigInc);1727  auto *OBOIsomorphic = dyn_cast<OverflowingBinaryOperator>(IsomorphicInc);1728  if (OBOIncV && OBOIsomorphic) {1729    BothHaveNUW =1730        OBOIncV->hasNoUnsignedWrap() && OBOIsomorphic->hasNoUnsignedWrap();1731    BothHaveNSW =1732        OBOIncV->hasNoSignedWrap() && OBOIsomorphic->hasNoSignedWrap();1733  }1734 1735  if (!hoistIVInc(OrigInc, IsomorphicInc,1736                  /*RecomputePoisonFlags*/ true))1737    return;1738 1739  // We are replacing with a wider increment. If both OrigInc and IsomorphicInc1740  // are NUW/NSW, then we can preserve them on the wider increment; the narrower1741  // IsomorphicInc would wrap before the wider OrigInc, so the replacement won't1742  // make IsomorphicInc's uses more poisonous.1743  assert(OrigInc->getType()->getScalarSizeInBits() >=1744             IsomorphicInc->getType()->getScalarSizeInBits() &&1745         "Should only replace an increment with a wider one.");1746  if (BothHaveNUW || BothHaveNSW) {1747    OrigInc->setHasNoUnsignedWrap(OBOIncV->hasNoUnsignedWrap() || BothHaveNUW);1748    OrigInc->setHasNoSignedWrap(OBOIncV->hasNoSignedWrap() || BothHaveNSW);1749  }1750 1751  SCEV_DEBUG_WITH_TYPE(DebugType,1752                       dbgs() << "INDVARS: Eliminated congruent iv.inc: "1753                              << *IsomorphicInc << '\n');1754  Value *NewInc = OrigInc;1755  if (OrigInc->getType() != IsomorphicInc->getType()) {1756    BasicBlock::iterator IP;1757    if (PHINode *PN = dyn_cast<PHINode>(OrigInc))1758      IP = PN->getParent()->getFirstInsertionPt();1759    else1760      IP = OrigInc->getNextNode()->getIterator();1761 1762    IRBuilder<> Builder(IP->getParent(), IP);1763    Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc());1764    NewInc =1765        Builder.CreateTruncOrBitCast(OrigInc, IsomorphicInc->getType(), IVName);1766  }1767  IsomorphicInc->replaceAllUsesWith(NewInc);1768  DeadInsts.emplace_back(IsomorphicInc);1769}1770 1771/// replaceCongruentIVs - Check for congruent phis in this loop header and1772/// replace them with their most canonical representative. Return the number of1773/// phis eliminated.1774///1775/// This does not depend on any SCEVExpander state but should be used in1776/// the same context that SCEVExpander is used.1777unsigned1778SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,1779                                  SmallVectorImpl<WeakTrackingVH> &DeadInsts,1780                                  const TargetTransformInfo *TTI) {1781  // Find integer phis in order of increasing width.1782  SmallVector<PHINode *, 8> Phis(1783      llvm::make_pointer_range(L->getHeader()->phis()));1784 1785  if (TTI)1786    // Use stable_sort to preserve order of equivalent PHIs, so the order1787    // of the sorted Phis is the same from run to run on the same loop.1788    llvm::stable_sort(Phis, [](Value *LHS, Value *RHS) {1789      // Put pointers at the back and make sure pointer < pointer = false.1790      if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())1791        return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();1792      return RHS->getType()->getPrimitiveSizeInBits().getFixedValue() <1793             LHS->getType()->getPrimitiveSizeInBits().getFixedValue();1794    });1795 1796  unsigned NumElim = 0;1797  DenseMap<const SCEV *, PHINode *> ExprToIVMap;1798  // Process phis from wide to narrow. Map wide phis to their truncation1799  // so narrow phis can reuse them.1800  for (PHINode *Phi : Phis) {1801    auto SimplifyPHINode = [&](PHINode *PN) -> Value * {1802      if (Value *V = simplifyInstruction(PN, {DL, &SE.TLI, &SE.DT, &SE.AC}))1803        return V;1804      if (!SE.isSCEVable(PN->getType()))1805        return nullptr;1806      auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));1807      if (!Const)1808        return nullptr;1809      return Const->getValue();1810    };1811 1812    // Fold constant phis. They may be congruent to other constant phis and1813    // would confuse the logic below that expects proper IVs.1814    if (Value *V = SimplifyPHINode(Phi)) {1815      if (V->getType() != Phi->getType())1816        continue;1817      SE.forgetValue(Phi);1818      Phi->replaceAllUsesWith(V);1819      DeadInsts.emplace_back(Phi);1820      ++NumElim;1821      SCEV_DEBUG_WITH_TYPE(DebugType,1822                           dbgs() << "INDVARS: Eliminated constant iv: " << *Phi1823                                  << '\n');1824      continue;1825    }1826 1827    if (!SE.isSCEVable(Phi->getType()))1828      continue;1829 1830    PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];1831    if (!OrigPhiRef) {1832      OrigPhiRef = Phi;1833      if (Phi->getType()->isIntegerTy() && TTI &&1834          TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {1835        // Make sure we only rewrite using simple induction variables;1836        // otherwise, we can make the trip count of a loop unanalyzable1837        // to SCEV.1838        const SCEV *PhiExpr = SE.getSCEV(Phi);1839        if (isa<SCEVAddRecExpr>(PhiExpr)) {1840          // This phi can be freely truncated to the narrowest phi type. Map the1841          // truncated expression to it so it will be reused for narrow types.1842          const SCEV *TruncExpr =1843              SE.getTruncateExpr(PhiExpr, Phis.back()->getType());1844          ExprToIVMap[TruncExpr] = Phi;1845        }1846      }1847      continue;1848    }1849 1850    // Replacing a pointer phi with an integer phi or vice-versa doesn't make1851    // sense.1852    if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy())1853      continue;1854 1855    replaceCongruentIVInc(Phi, OrigPhiRef, L, DT, DeadInsts);1856    SCEV_DEBUG_WITH_TYPE(DebugType,1857                         dbgs() << "INDVARS: Eliminated congruent iv: " << *Phi1858                                << '\n');1859    SCEV_DEBUG_WITH_TYPE(1860        DebugType, dbgs() << "INDVARS: Original iv: " << *OrigPhiRef << '\n');1861    ++NumElim;1862    Value *NewIV = OrigPhiRef;1863    if (OrigPhiRef->getType() != Phi->getType()) {1864      IRBuilder<> Builder(L->getHeader(),1865                          L->getHeader()->getFirstInsertionPt());1866      Builder.SetCurrentDebugLocation(Phi->getDebugLoc());1867      NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);1868    }1869    Phi->replaceAllUsesWith(NewIV);1870    DeadInsts.emplace_back(Phi);1871  }1872  return NumElim;1873}1874 1875bool SCEVExpander::hasRelatedExistingExpansion(const SCEV *S,1876                                               const Instruction *At,1877                                               Loop *L) {1878  using namespace llvm::PatternMatch;1879 1880  SmallVector<BasicBlock *, 4> ExitingBlocks;1881  L->getExitingBlocks(ExitingBlocks);1882 1883  // Look for suitable value in simple conditions at the loop exits.1884  for (BasicBlock *BB : ExitingBlocks) {1885    CmpPredicate Pred;1886    Instruction *LHS, *RHS;1887 1888    if (!match(BB->getTerminator(),1889               m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),1890                    m_BasicBlock(), m_BasicBlock())))1891      continue;1892 1893    if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))1894      return true;1895 1896    if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))1897      return true;1898  }1899 1900  // Use expand's logic which is used for reusing a previous Value in1901  // ExprValueMap.  Note that we don't currently model the cost of1902  // needing to drop poison generating flags on the instruction if we1903  // want to reuse it.  We effectively assume that has zero cost.1904  SmallVector<Instruction *> DropPoisonGeneratingInsts;1905  return FindValueInExprValueMap(S, At, DropPoisonGeneratingInsts) != nullptr;1906}1907 1908template<typename T> static InstructionCost costAndCollectOperands(1909  const SCEVOperand &WorkItem, const TargetTransformInfo &TTI,1910  TargetTransformInfo::TargetCostKind CostKind,1911  SmallVectorImpl<SCEVOperand> &Worklist) {1912 1913  const T *S = cast<T>(WorkItem.S);1914  InstructionCost Cost = 0;1915  // Object to help map SCEV operands to expanded IR instructions.1916  struct OperationIndices {1917    OperationIndices(unsigned Opc, size_t min, size_t max) :1918      Opcode(Opc), MinIdx(min), MaxIdx(max) { }1919    unsigned Opcode;1920    size_t MinIdx;1921    size_t MaxIdx;1922  };1923 1924  // Collect the operations of all the instructions that will be needed to1925  // expand the SCEVExpr. This is so that when we come to cost the operands,1926  // we know what the generated user(s) will be.1927  SmallVector<OperationIndices, 2> Operations;1928 1929  auto CastCost = [&](unsigned Opcode) -> InstructionCost {1930    Operations.emplace_back(Opcode, 0, 0);1931    return TTI.getCastInstrCost(Opcode, S->getType(),1932                                S->getOperand(0)->getType(),1933                                TTI::CastContextHint::None, CostKind);1934  };1935 1936  auto ArithCost = [&](unsigned Opcode, unsigned NumRequired,1937                       unsigned MinIdx = 0,1938                       unsigned MaxIdx = 1) -> InstructionCost {1939    Operations.emplace_back(Opcode, MinIdx, MaxIdx);1940    return NumRequired *1941      TTI.getArithmeticInstrCost(Opcode, S->getType(), CostKind);1942  };1943 1944  auto CmpSelCost = [&](unsigned Opcode, unsigned NumRequired, unsigned MinIdx,1945                        unsigned MaxIdx) -> InstructionCost {1946    Operations.emplace_back(Opcode, MinIdx, MaxIdx);1947    Type *OpType = S->getType();1948    return NumRequired * TTI.getCmpSelInstrCost(1949                             Opcode, OpType, CmpInst::makeCmpResultType(OpType),1950                             CmpInst::BAD_ICMP_PREDICATE, CostKind);1951  };1952 1953  switch (S->getSCEVType()) {1954  case scCouldNotCompute:1955    llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");1956  case scUnknown:1957  case scConstant:1958  case scVScale:1959    return 0;1960  case scPtrToInt:1961    Cost = CastCost(Instruction::PtrToInt);1962    break;1963  case scTruncate:1964    Cost = CastCost(Instruction::Trunc);1965    break;1966  case scZeroExtend:1967    Cost = CastCost(Instruction::ZExt);1968    break;1969  case scSignExtend:1970    Cost = CastCost(Instruction::SExt);1971    break;1972  case scUDivExpr: {1973    unsigned Opcode = Instruction::UDiv;1974    if (auto *SC = dyn_cast<SCEVConstant>(S->getOperand(1)))1975      if (SC->getAPInt().isPowerOf2())1976        Opcode = Instruction::LShr;1977    Cost = ArithCost(Opcode, 1);1978    break;1979  }1980  case scAddExpr:1981    Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1);1982    break;1983  case scMulExpr:1984    // TODO: this is a very pessimistic cost modelling for Mul,1985    // because of Bin Pow algorithm actually used by the expander,1986    // see SCEVExpander::visitMulExpr(), ExpandOpBinPowN().1987    Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1);1988    break;1989  case scSMaxExpr:1990  case scUMaxExpr:1991  case scSMinExpr:1992  case scUMinExpr:1993  case scSequentialUMinExpr: {1994    // FIXME: should this ask the cost for Intrinsic's?1995    // The reduction tree.1996    Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);1997    Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2);1998    switch (S->getSCEVType()) {1999    case scSequentialUMinExpr: {2000      // The safety net against poison.2001      // FIXME: this is broken.2002      Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 0);2003      Cost += ArithCost(Instruction::Or,2004                        S->getNumOperands() > 2 ? S->getNumOperands() - 2 : 0);2005      Cost += CmpSelCost(Instruction::Select, 1, 0, 1);2006      break;2007    }2008    default:2009      assert(!isa<SCEVSequentialMinMaxExpr>(S) &&2010             "Unhandled SCEV expression type?");2011      break;2012    }2013    break;2014  }2015  case scAddRecExpr: {2016    // Addrec expands to a phi and add per recurrence.2017    unsigned NumRecurrences = S->getNumOperands() - 1;2018    Cost += TTI.getCFInstrCost(Instruction::PHI, CostKind) * NumRecurrences;2019    Cost +=2020        TTI.getArithmeticInstrCost(Instruction::Add, S->getType(), CostKind) *2021        NumRecurrences;2022    // AR start is used in phi.2023    Worklist.emplace_back(Instruction::PHI, 0, S->getOperand(0));2024    // Other operands are used in add.2025    for (const SCEV *Op : S->operands().drop_front())2026      Worklist.emplace_back(Instruction::Add, 1, Op);2027    break;2028  }2029  }2030 2031  for (auto &CostOp : Operations) {2032    for (auto SCEVOp : enumerate(S->operands())) {2033      // Clamp the index to account for multiple IR operations being chained.2034      size_t MinIdx = std::max(SCEVOp.index(), CostOp.MinIdx);2035      size_t OpIdx = std::min(MinIdx, CostOp.MaxIdx);2036      Worklist.emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value());2037    }2038  }2039  return Cost;2040}2041 2042bool SCEVExpander::isHighCostExpansionHelper(2043    const SCEVOperand &WorkItem, Loop *L, const Instruction &At,2044    InstructionCost &Cost, unsigned Budget, const TargetTransformInfo &TTI,2045    SmallPtrSetImpl<const SCEV *> &Processed,2046    SmallVectorImpl<SCEVOperand> &Worklist) {2047  if (Cost > Budget)2048    return true; // Already run out of budget, give up.2049 2050  const SCEV *S = WorkItem.S;2051  // Was the cost of expansion of this expression already accounted for?2052  if (!isa<SCEVConstant>(S) && !Processed.insert(S).second)2053    return false; // We have already accounted for this expression.2054 2055  // If we can find an existing value for this scev available at the point "At"2056  // then consider the expression cheap.2057  if (hasRelatedExistingExpansion(S, &At, L))2058    return false; // Consider the expression to be free.2059 2060  TargetTransformInfo::TargetCostKind CostKind =2061      L->getHeader()->getParent()->hasMinSize()2062          ? TargetTransformInfo::TCK_CodeSize2063          : TargetTransformInfo::TCK_RecipThroughput;2064 2065  switch (S->getSCEVType()) {2066  case scCouldNotCompute:2067    llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");2068  case scUnknown:2069  case scVScale:2070    // Assume to be zero-cost.2071    return false;2072  case scConstant: {2073    // Only evalulate the costs of constants when optimizing for size.2074    if (CostKind != TargetTransformInfo::TCK_CodeSize)2075      return false;2076    const APInt &Imm = cast<SCEVConstant>(S)->getAPInt();2077    Type *Ty = S->getType();2078    Cost += TTI.getIntImmCostInst(2079        WorkItem.ParentOpcode, WorkItem.OperandIdx, Imm, Ty, CostKind);2080    return Cost > Budget;2081  }2082  case scTruncate:2083  case scPtrToInt:2084  case scZeroExtend:2085  case scSignExtend: {2086    Cost +=2087        costAndCollectOperands<SCEVCastExpr>(WorkItem, TTI, CostKind, Worklist);2088    return false; // Will answer upon next entry into this function.2089  }2090  case scUDivExpr: {2091    // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or2092    // HowManyLessThans produced to compute a precise expression, rather than a2093    // UDiv from the user's code. If we can't find a UDiv in the code with some2094    // simple searching, we need to account for it's cost.2095 2096    // At the beginning of this function we already tried to find existing2097    // value for plain 'S'. Now try to lookup 'S + 1' since it is common2098    // pattern involving division. This is just a simple search heuristic.2099    if (hasRelatedExistingExpansion(2100            SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &At, L))2101      return false; // Consider it to be free.2102 2103    Cost +=2104        costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist);2105    return false; // Will answer upon next entry into this function.2106  }2107  case scAddExpr:2108  case scMulExpr:2109  case scUMaxExpr:2110  case scSMaxExpr:2111  case scUMinExpr:2112  case scSMinExpr:2113  case scSequentialUMinExpr: {2114    assert(cast<SCEVNAryExpr>(S)->getNumOperands() > 1 &&2115           "Nary expr should have more than 1 operand.");2116    // The simple nary expr will require one less op (or pair of ops)2117    // than the number of it's terms.2118    Cost +=2119        costAndCollectOperands<SCEVNAryExpr>(WorkItem, TTI, CostKind, Worklist);2120    return Cost > Budget;2121  }2122  case scAddRecExpr: {2123    assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&2124           "Polynomial should be at least linear");2125    Cost += costAndCollectOperands<SCEVAddRecExpr>(2126        WorkItem, TTI, CostKind, Worklist);2127    return Cost > Budget;2128  }2129  }2130  llvm_unreachable("Unknown SCEV kind!");2131}2132 2133Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred,2134                                            Instruction *IP) {2135  assert(IP);2136  switch (Pred->getKind()) {2137  case SCEVPredicate::P_Union:2138    return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);2139  case SCEVPredicate::P_Compare:2140    return expandComparePredicate(cast<SCEVComparePredicate>(Pred), IP);2141  case SCEVPredicate::P_Wrap: {2142    auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);2143    return expandWrapPredicate(AddRecPred, IP);2144  }2145  }2146  llvm_unreachable("Unknown SCEV predicate type");2147}2148 2149Value *SCEVExpander::expandComparePredicate(const SCEVComparePredicate *Pred,2150                                            Instruction *IP) {2151  Value *Expr0 = expand(Pred->getLHS(), IP);2152  Value *Expr1 = expand(Pred->getRHS(), IP);2153 2154  Builder.SetInsertPoint(IP);2155  auto InvPred = ICmpInst::getInversePredicate(Pred->getPredicate());2156  auto *I = Builder.CreateICmp(InvPred, Expr0, Expr1, "ident.check");2157  return I;2158}2159 2160Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,2161                                           Instruction *Loc, bool Signed) {2162  assert(AR->isAffine() && "Cannot generate RT check for "2163                           "non-affine expression");2164 2165  // FIXME: It is highly suspicious that we're ignoring the predicates here.2166  SmallVector<const SCEVPredicate *, 4> Pred;2167  const SCEV *ExitCount =2168      SE.getPredicatedSymbolicMaxBackedgeTakenCount(AR->getLoop(), Pred);2169 2170  assert(!isa<SCEVCouldNotCompute>(ExitCount) && "Invalid loop count");2171 2172  const SCEV *Step = AR->getStepRecurrence(SE);2173  const SCEV *Start = AR->getStart();2174 2175  Type *ARTy = AR->getType();2176  unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType());2177  unsigned DstBits = SE.getTypeSizeInBits(ARTy);2178 2179  // The expression {Start,+,Step} has nusw/nssw if2180  //   Step < 0, Start - |Step| * Backedge <= Start2181  //   Step >= 0, Start + |Step| * Backedge > Start2182  // and |Step| * Backedge doesn't unsigned overflow.2183 2184  Builder.SetInsertPoint(Loc);2185  Value *TripCountVal = expand(ExitCount, Loc);2186 2187  IntegerType *Ty =2188      IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy));2189 2190  Value *StepValue = expand(Step, Loc);2191  Value *NegStepValue = expand(SE.getNegativeSCEV(Step), Loc);2192  Value *StartValue = expand(Start, Loc);2193 2194  ConstantInt *Zero =2195      ConstantInt::get(Loc->getContext(), APInt::getZero(DstBits));2196 2197  Builder.SetInsertPoint(Loc);2198  // Compute |Step|2199  Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero);2200  Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue);2201 2202  // Compute |Step| * Backedge2203  // Compute:2204  //   1. Start + |Step| * Backedge < Start2205  //   2. Start - |Step| * Backedge > Start2206  //2207  // And select either 1. or 2. depending on whether step is positive or2208  // negative. If Step is known to be positive or negative, only create2209  // either 1. or 2.2210  auto ComputeEndCheck = [&]() -> Value * {2211    // Get the backedge taken count and truncate or extended to the AR type.2212    Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty);2213 2214    CallInst *Mul = Builder.CreateIntrinsic(Intrinsic::umul_with_overflow, Ty,2215                                            {AbsStep, TruncTripCount},2216                                            /*FMFSource=*/nullptr, "mul");2217    Value *MulV = Builder.CreateExtractValue(Mul, 0, "mul.result");2218    Value *OfMul = Builder.CreateExtractValue(Mul, 1, "mul.overflow");2219 2220    Value *Add = nullptr, *Sub = nullptr;2221    bool NeedPosCheck = !SE.isKnownNegative(Step);2222    bool NeedNegCheck = !SE.isKnownPositive(Step);2223 2224    if (isa<PointerType>(ARTy)) {2225      Value *NegMulV = Builder.CreateNeg(MulV);2226      if (NeedPosCheck)2227        Add = Builder.CreatePtrAdd(StartValue, MulV);2228      if (NeedNegCheck)2229        Sub = Builder.CreatePtrAdd(StartValue, NegMulV);2230    } else {2231      if (NeedPosCheck)2232        Add = Builder.CreateAdd(StartValue, MulV);2233      if (NeedNegCheck)2234        Sub = Builder.CreateSub(StartValue, MulV);2235    }2236 2237    Value *EndCompareLT = nullptr;2238    Value *EndCompareGT = nullptr;2239    Value *EndCheck = nullptr;2240    if (NeedPosCheck)2241      EndCheck = EndCompareLT = Builder.CreateICmp(2242          Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, Add, StartValue);2243    if (NeedNegCheck)2244      EndCheck = EndCompareGT = Builder.CreateICmp(2245          Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue);2246    if (NeedPosCheck && NeedNegCheck) {2247      // Select the answer based on the sign of Step.2248      EndCheck = Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT);2249    }2250    return Builder.CreateOr(EndCheck, OfMul);2251  };2252  Value *EndCheck = ComputeEndCheck();2253 2254  // If the backedge taken count type is larger than the AR type,2255  // check that we don't drop any bits by truncating it. If we are2256  // dropping bits, then we have overflow (unless the step is zero).2257  if (SrcBits > DstBits) {2258    auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits);2259    auto *BackedgeCheck =2260        Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal,2261                           ConstantInt::get(Loc->getContext(), MaxVal));2262    BackedgeCheck = Builder.CreateAnd(2263        BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero));2264 2265    EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck);2266  }2267 2268  return EndCheck;2269}2270 2271Value *SCEVExpander::expandWrapPredicate(const SCEVWrapPredicate *Pred,2272                                         Instruction *IP) {2273  const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr());2274  Value *NSSWCheck = nullptr, *NUSWCheck = nullptr;2275 2276  // Add a check for NUSW2277  if (Pred->getFlags() & SCEVWrapPredicate::IncrementNUSW)2278    NUSWCheck = generateOverflowCheck(A, IP, false);2279 2280  // Add a check for NSSW2281  if (Pred->getFlags() & SCEVWrapPredicate::IncrementNSSW)2282    NSSWCheck = generateOverflowCheck(A, IP, true);2283 2284  if (NUSWCheck && NSSWCheck)2285    return Builder.CreateOr(NUSWCheck, NSSWCheck);2286 2287  if (NUSWCheck)2288    return NUSWCheck;2289 2290  if (NSSWCheck)2291    return NSSWCheck;2292 2293  return ConstantInt::getFalse(IP->getContext());2294}2295 2296Value *SCEVExpander::expandUnionPredicate(const SCEVUnionPredicate *Union,2297                                          Instruction *IP) {2298  // Loop over all checks in this set.2299  SmallVector<Value *> Checks;2300  for (const auto *Pred : Union->getPredicates()) {2301    Checks.push_back(expandCodeForPredicate(Pred, IP));2302    Builder.SetInsertPoint(IP);2303  }2304 2305  if (Checks.empty())2306    return ConstantInt::getFalse(IP->getContext());2307  return Builder.CreateOr(Checks);2308}2309 2310Value *SCEVExpander::fixupLCSSAFormFor(Value *V) {2311  auto *DefI = dyn_cast<Instruction>(V);2312  if (!PreserveLCSSA || !DefI)2313    return V;2314 2315  BasicBlock::iterator InsertPt = Builder.GetInsertPoint();2316  Loop *DefLoop = SE.LI.getLoopFor(DefI->getParent());2317  Loop *UseLoop = SE.LI.getLoopFor(InsertPt->getParent());2318  if (!DefLoop || UseLoop == DefLoop || DefLoop->contains(UseLoop))2319    return V;2320 2321  // Create a temporary instruction to at the current insertion point, so we2322  // can hand it off to the helper to create LCSSA PHIs if required for the2323  // new use.2324  // FIXME: Ideally formLCSSAForInstructions (used in fixupLCSSAFormFor)2325  // would accept a insertion point and return an LCSSA phi for that2326  // insertion point, so there is no need to insert & remove the temporary2327  // instruction.2328  Type *ToTy;2329  if (DefI->getType()->isIntegerTy())2330    ToTy = PointerType::get(DefI->getContext(), 0);2331  else2332    ToTy = Type::getInt32Ty(DefI->getContext());2333  Instruction *User =2334      CastInst::CreateBitOrPointerCast(DefI, ToTy, "tmp.lcssa.user", InsertPt);2335  auto RemoveUserOnExit =2336      make_scope_exit([User]() { User->eraseFromParent(); });2337 2338  SmallVector<Instruction *, 1> ToUpdate;2339  ToUpdate.push_back(DefI);2340  SmallVector<PHINode *, 16> PHIsToRemove;2341  SmallVector<PHINode *, 16> InsertedPHIs;2342  formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, &SE, &PHIsToRemove,2343                           &InsertedPHIs);2344  for (PHINode *PN : InsertedPHIs)2345    rememberInstruction(PN);2346  for (PHINode *PN : PHIsToRemove) {2347    if (!PN->use_empty())2348      continue;2349    InsertedValues.erase(PN);2350    InsertedPostIncValues.erase(PN);2351    PN->eraseFromParent();2352  }2353 2354  return User->getOperand(0);2355}2356 2357namespace {2358// Search for a SCEV subexpression that is not safe to expand.  Any expression2359// that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely2360// UDiv expressions. We don't know if the UDiv is derived from an IR divide2361// instruction, but the important thing is that we prove the denominator is2362// nonzero before expansion.2363//2364// IVUsers already checks that IV-derived expressions are safe. So this check is2365// only needed when the expression includes some subexpression that is not IV2366// derived.2367//2368// Currently, we only allow division by a value provably non-zero here.2369//2370// We cannot generally expand recurrences unless the step dominates the loop2371// header. The expander handles the special case of affine recurrences by2372// scaling the recurrence outside the loop, but this technique isn't generally2373// applicable. Expanding a nested recurrence outside a loop requires computing2374// binomial coefficients. This could be done, but the recurrence has to be in a2375// perfectly reduced form, which can't be guaranteed.2376struct SCEVFindUnsafe {2377  ScalarEvolution &SE;2378  bool CanonicalMode;2379  bool IsUnsafe = false;2380 2381  SCEVFindUnsafe(ScalarEvolution &SE, bool CanonicalMode)2382      : SE(SE), CanonicalMode(CanonicalMode) {}2383 2384  bool follow(const SCEV *S) {2385    if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {2386      if (!SE.isKnownNonZero(D->getRHS())) {2387        IsUnsafe = true;2388        return false;2389      }2390    }2391    if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {2392      // For non-affine addrecs or in non-canonical mode we need a preheader2393      // to insert into.2394      if (!AR->getLoop()->getLoopPreheader() &&2395          (!CanonicalMode || !AR->isAffine())) {2396        IsUnsafe = true;2397        return false;2398      }2399    }2400    return true;2401  }2402  bool isDone() const { return IsUnsafe; }2403};2404} // namespace2405 2406bool SCEVExpander::isSafeToExpand(const SCEV *S) const {2407  SCEVFindUnsafe Search(SE, CanonicalMode);2408  visitAll(S, Search);2409  return !Search.IsUnsafe;2410}2411 2412bool SCEVExpander::isSafeToExpandAt(const SCEV *S,2413                                    const Instruction *InsertionPoint) const {2414  if (!isSafeToExpand(S))2415    return false;2416  // We have to prove that the expanded site of S dominates InsertionPoint.2417  // This is easy when not in the same block, but hard when S is an instruction2418  // to be expanded somewhere inside the same block as our insertion point.2419  // What we really need here is something analogous to an OrderedBasicBlock,2420  // but for the moment, we paper over the problem by handling two common and2421  // cheap to check cases.2422  if (SE.properlyDominates(S, InsertionPoint->getParent()))2423    return true;2424  if (SE.dominates(S, InsertionPoint->getParent())) {2425    if (InsertionPoint->getParent()->getTerminator() == InsertionPoint)2426      return true;2427    if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))2428      if (llvm::is_contained(InsertionPoint->operand_values(), U->getValue()))2429        return true;2430  }2431  return false;2432}2433 2434void SCEVExpanderCleaner::cleanup() {2435  // Result is used, nothing to remove.2436  if (ResultUsed)2437    return;2438 2439  // Restore original poison flags.2440  for (auto [I, Flags] : Expander.OrigFlags)2441    Flags.apply(I);2442 2443  auto InsertedInstructions = Expander.getAllInsertedInstructions();2444#ifndef NDEBUG2445  SmallPtrSet<Instruction *, 8> InsertedSet(llvm::from_range,2446                                            InsertedInstructions);2447  (void)InsertedSet;2448#endif2449  // Remove sets with value handles.2450  Expander.clear();2451 2452  // Remove all inserted instructions.2453  for (Instruction *I : reverse(InsertedInstructions)) {2454#ifndef NDEBUG2455    assert(all_of(I->users(),2456                  [&InsertedSet](Value *U) {2457                    return InsertedSet.contains(cast<Instruction>(U));2458                  }) &&2459           "removed instruction should only be used by instructions inserted "2460           "during expansion");2461#endif2462    assert(!I->getType()->isVoidTy() &&2463           "inserted instruction should have non-void types");2464    I->replaceAllUsesWith(PoisonValue::get(I->getType()));2465    I->eraseFromParent();2466  }2467}2468