LCOV - code coverage report
Current view: top level - lib/Analysis - ScalarEvolutionExpander.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 984 1048 93.9 %
Date: 2017-09-14 15:23:50 Functions: 52 53 98.1 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis ------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file contains the implementation of the scalar evolution expander,
      11             : // which is used to generate the code corresponding to a given scalar evolution
      12             : // expression.
      13             : //
      14             : //===----------------------------------------------------------------------===//
      15             : 
      16             : #include "llvm/Analysis/ScalarEvolutionExpander.h"
      17             : #include "llvm/ADT/STLExtras.h"
      18             : #include "llvm/ADT/SmallSet.h"
      19             : #include "llvm/Analysis/InstructionSimplify.h"
      20             : #include "llvm/Analysis/LoopInfo.h"
      21             : #include "llvm/Analysis/TargetTransformInfo.h"
      22             : #include "llvm/IR/DataLayout.h"
      23             : #include "llvm/IR/Dominators.h"
      24             : #include "llvm/IR/IntrinsicInst.h"
      25             : #include "llvm/IR/LLVMContext.h"
      26             : #include "llvm/IR/Module.h"
      27             : #include "llvm/IR/PatternMatch.h"
      28             : #include "llvm/Support/Debug.h"
      29             : #include "llvm/Support/raw_ostream.h"
      30             : 
      31             : using namespace llvm;
      32             : using namespace PatternMatch;
      33             : 
      34             : /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
      35             : /// reusing an existing cast if a suitable one exists, moving an existing
      36             : /// cast if a suitable one exists but isn't in the right place, or
      37             : /// creating a new one.
      38        5568 : Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,
      39             :                                        Instruction::CastOps Op,
      40             :                                        BasicBlock::iterator IP) {
      41             :   // This function must be called with the builder having a valid insertion
      42             :   // point. It doesn't need to be the actual IP where the uses of the returned
      43             :   // cast will be added, but it must dominate such IP.
      44             :   // We use this precondition to produce a cast that will dominate all its
      45             :   // uses. In particular, this is crucial for the case where the builder's
      46             :   // insertion point *is* the point where we were asked to put the cast.
      47             :   // Since we don't know the builder's insertion point is actually
      48             :   // where the uses will be added (only that it dominates it), we are
      49             :   // not allowed to move it.
      50        5568 :   BasicBlock::iterator BIP = Builder.GetInsertPoint();
      51             : 
      52        5568 :   Instruction *Ret = nullptr;
      53             : 
      54             :   // Check to see if there is already a cast!
      55       22332 :   for (User *U : V->users())
      56        6469 :     if (U->getType() == Ty)
      57        1742 :       if (CastInst *CI = dyn_cast<CastInst>(U))
      58        1742 :         if (CI->getOpcode() == Op) {
      59             :           // If the cast isn't where we want it, create a new cast at IP.
      60             :           // Likewise, do not reuse a cast at BIP because it must dominate
      61             :           // instructions that might be inserted before BIP.
      62        1742 :           if (BasicBlock::iterator(CI) != IP || BIP == IP) {
      63             :             // Create a new cast, and leave the old cast in place in case
      64             :             // it is being used as an insert point. Clear its operand
      65             :             // so that it doesn't hold anything live.
      66         388 :             Ret = CastInst::Create(Op, V, Ty, "", &*IP);
      67         194 :             Ret->takeName(CI);
      68         194 :             CI->replaceAllUsesWith(Ret);
      69         194 :             CI->setOperand(0, UndefValue::get(V->getType()));
      70             :             break;
      71             :           }
      72             :           Ret = CI;
      73             :           break;
      74             :         }
      75             : 
      76             :   // Create a new cast.
      77        5568 :   if (!Ret)
      78        7652 :     Ret = CastInst::Create(Op, V, Ty, V->getName(), &*IP);
      79             : 
      80             :   // We assert at the end of the function since IP might point to an
      81             :   // instruction with different dominance properties than a cast
      82             :   // (an invoke for example) and not dominate BIP (but the cast does).
      83             :   assert(SE.DT.dominates(Ret, &*BIP));
      84             : 
      85        5568 :   rememberInstruction(Ret);
      86        5568 :   return Ret;
      87             : }
      88             : 
      89        4601 : static BasicBlock::iterator findInsertPointAfter(Instruction *I,
      90             :                                                  BasicBlock *MustDominate) {
      91       13803 :   BasicBlock::iterator IP = ++I->getIterator();
      92           2 :   if (auto *II = dyn_cast<InvokeInst>(I))
      93           4 :     IP = II->getNormalDest()->begin();
      94             : 
      95        7081 :   while (isa<PHINode>(IP))
      96             :     ++IP;
      97             : 
      98        9201 :   if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {
      99             :     ++IP;
     100        4599 :   } else if (isa<CatchSwitchInst>(IP)) {
     101           3 :     IP = MustDominate->getFirstInsertionPt();
     102             :   } else {
     103             :     assert(!IP->isEHPad() && "unexpected eh pad!");
     104             :   }
     105             : 
     106        4601 :   return IP;
     107             : }
     108             : 
     109             : /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
     110             : /// which must be possible with a noop cast, doing what we can to share
     111             : /// the casts.
     112       54004 : Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
     113       54004 :   Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false);
     114             :   assert((Op == Instruction::BitCast ||
     115             :           Op == Instruction::PtrToInt ||
     116             :           Op == Instruction::IntToPtr) &&
     117             :          "InsertNoopCastOfTo cannot perform non-noop casts!");
     118             :   assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) &&
     119             :          "InsertNoopCastOfTo cannot change sizes!");
     120             : 
     121             :   // Short-circuit unnecessary bitcasts.
     122       54004 :   if (Op == Instruction::BitCast) {
     123       53412 :     if (V->getType() == Ty)
     124             :       return V;
     125         410 :     if (CastInst *CI = dyn_cast<CastInst>(V)) {
     126         820 :       if (CI->getOperand(0)->getType() == Ty)
     127             :         return CI->getOperand(0);
     128             :     }
     129             :   }
     130             :   // Short-circuit unnecessary inttoptr<->ptrtoint casts.
     131        6710 :   if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) &&
     132         592 :       SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) {
     133             :     if (CastInst *CI = dyn_cast<CastInst>(V))
     134         282 :       if ((CI->getOpcode() == Instruction::PtrToInt ||
     135         411 :            CI->getOpcode() == Instruction::IntToPtr) &&
     136         129 :           SE.getTypeSizeInBits(CI->getType()) ==
     137         258 :           SE.getTypeSizeInBits(CI->getOperand(0)->getType()))
     138         129 :         return CI->getOperand(0);
     139           5 :     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
     140          10 :       if ((CE->getOpcode() == Instruction::PtrToInt ||
     141          10 :            CE->getOpcode() == Instruction::IntToPtr) &&
     142           0 :           SE.getTypeSizeInBits(CE->getType()) ==
     143           0 :           SE.getTypeSizeInBits(CE->getOperand(0)->getType()))
     144             :         return CE->getOperand(0);
     145             :   }
     146             : 
     147             :   // Fold a cast of a constant.
     148         421 :   if (Constant *C = dyn_cast<Constant>(V))
     149         421 :     return ConstantExpr::getCast(Op, C, Ty);
     150             : 
     151             :   // Cast the argument at the beginning of the entry block, after
     152             :   // any bitcasts of other arguments.
     153         970 :   if (Argument *A = dyn_cast<Argument>(V)) {
     154        2910 :     BasicBlock::iterator IP = A->getParent()->getEntryBlock().begin();
     155        3694 :     while ((isa<BitCastInst>(IP) &&
     156        3166 :             isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) &&
     157        6562 :             cast<BitCastInst>(IP)->getOperand(0) != A) ||
     158        1881 :            isa<DbgInfoIntrinsic>(IP))
     159             :       ++IP;
     160         970 :     return ReuseOrCreateCast(A, Ty, Op, IP);
     161             :   }
     162             : 
     163             :   // Cast the instruction immediately after the instruction.
     164        4598 :   Instruction *I = cast<Instruction>(V);
     165        4598 :   BasicBlock::iterator IP = findInsertPointAfter(I, Builder.GetInsertBlock());
     166        4598 :   return ReuseOrCreateCast(I, Ty, Op, IP);
     167             : }
     168             : 
     169             : /// InsertBinop - Insert the specified binary operator, doing a small amount
     170             : /// of work to avoid inserting an obviously redundant operation.
     171        4802 : Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
     172             :                                  Value *LHS, Value *RHS) {
     173             :   // Fold a binop with constant operands.
     174         535 :   if (Constant *CLHS = dyn_cast<Constant>(LHS))
     175         221 :     if (Constant *CRHS = dyn_cast<Constant>(RHS))
     176         221 :       return ConstantExpr::get(Opcode, CLHS, CRHS);
     177             : 
     178             :   // Do a quick scan to see if we have this binop nearby.  If so, reuse it.
     179        4581 :   unsigned ScanLimit = 6;
     180        9162 :   BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
     181             :   // Scanning starts from the last instruction before the insertion point.
     182        4581 :   BasicBlock::iterator IP = Builder.GetInsertPoint();
     183        4581 :   if (IP != BlockBegin) {
     184             :     --IP;
     185       29775 :     for (; ScanLimit; --IP, --ScanLimit) {
     186             :       // Don't count dbg.value against the ScanLimit, to avoid perturbing the
     187             :       // generated code.
     188       15476 :       if (isa<DbgInfoIntrinsic>(IP))
     189         221 :         ScanLimit++;
     190       39874 :       if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS &&
     191        1088 :           IP->getOperand(1) == RHS)
     192             :         return &*IP;
     193       15121 :       if (IP == BlockBegin) break;
     194             :     }
     195             :   }
     196             : 
     197             :   // Save the original insertion point so we can restore it when we're done.
     198       12678 :   DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();
     199        8452 :   SCEVInsertPointGuard Guard(Builder, this);
     200             : 
     201             :   // Move the insertion point out of as many loops as we can.
     202        8490 :   while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
     203        1825 :     if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break;
     204          28 :     BasicBlock *Preheader = L->getLoopPreheader();
     205          28 :     if (!Preheader) break;
     206             : 
     207             :     // Ok, move up a level.
     208          38 :     Builder.SetInsertPoint(Preheader->getTerminator());
     209          19 :   }
     210             : 
     211             :   // If we haven't found this binop, insert it.
     212       12678 :   Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS));
     213       12678 :   BO->setDebugLoc(Loc);
     214        4226 :   rememberInstruction(BO);
     215             : 
     216             :   return BO;
     217             : }
     218             : 
     219             : /// FactorOutConstant - Test if S is divisible by Factor, using signed
     220             : /// division. If so, update S with Factor divided out and return true.
     221             : /// S need not be evenly divisible if a reasonable remainder can be
     222             : /// computed.
     223             : /// TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made
     224             : /// unnecessary; in its place, just signed-divide Ops[i] by the scale and
     225             : /// check to see if the divide was folded.
     226        8918 : static bool FactorOutConstant(const SCEV *&S, const SCEV *&Remainder,
     227             :                               const SCEV *Factor, ScalarEvolution &SE,
     228             :                               const DataLayout &DL) {
     229             :   // Everything is divisible by one.
     230        8918 :   if (Factor->isOne())
     231             :     return true;
     232             : 
     233             :   // x/x == 1.
     234        7462 :   if (S == Factor) {
     235         835 :     S = SE.getConstant(S->getType(), 1);
     236         835 :     return true;
     237             :   }
     238             : 
     239             :   // For a Constant, check for a multiple of the given factor.
     240        9662 :   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
     241             :     // 0/x == 0.
     242        3035 :     if (C->isZero())
     243             :       return true;
     244             :     // Check for divisibility.
     245        2924 :     if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) {
     246             :       ConstantInt *CI =
     247       11696 :           ConstantInt::get(SE.getContext(), C->getAPInt().sdiv(FC->getAPInt()));
     248             :       // If the quotient is zero and the remainder is non-zero, reject
     249             :       // the value at this scale. It will be considered for subsequent
     250             :       // smaller scales.
     251        2924 :       if (!CI->isZero()) {
     252        2198 :         const SCEV *Div = SE.getConstant(CI);
     253        2198 :         S = Div;
     254        2198 :         Remainder = SE.getAddExpr(
     255        6594 :             Remainder, SE.getConstant(C->getAPInt().srem(FC->getAPInt())));
     256        2198 :         return true;
     257             :       }
     258             :     }
     259             :   }
     260             : 
     261             :   // In a Mul, check if there is a constant operand which is a multiple
     262             :   // of the given factor.
     263        6803 :   if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
     264             :     // Size is known, check if there is a constant operand which is a multiple
     265             :     // of the given factor. If so, we can factor it.
     266        2485 :     const SCEVConstant *FC = cast<SCEVConstant>(Factor);
     267        7451 :     if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0)))
     268        9924 :       if (!C->getAPInt().srem(FC->getAPInt())) {
     269        7556 :         SmallVector<const SCEV *, 4> NewMulOps(M->op_begin(), M->op_end());
     270        7556 :         NewMulOps[0] = SE.getConstant(C->getAPInt().sdiv(FC->getAPInt()));
     271        1889 :         S = SE.getMulExpr(NewMulOps);
     272        1889 :         return true;
     273             :       }
     274             :   }
     275             : 
     276             :   // In an AddRec, check if both start and step are divisible.
     277        2495 :   if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
     278          66 :     const SCEV *Step = A->getStepRecurrence(SE);
     279          66 :     const SCEV *StepRem = SE.getConstant(Step->getType(), 0);
     280          66 :     if (!FactorOutConstant(Step, StepRem, Factor, SE, DL))
     281             :       return false;
     282          50 :     if (!StepRem->isZero())
     283             :       return false;
     284          50 :     const SCEV *Start = A->getStart();
     285          50 :     if (!FactorOutConstant(Start, Remainder, Factor, SE, DL))
     286             :       return false;
     287         100 :     S = SE.getAddRecExpr(Start, Step, A->getLoop(),
     288             :                          A->getNoWrapFlags(SCEV::FlagNW));
     289          50 :     return true;
     290             :   }
     291             : 
     292             :   return false;
     293             : }
     294             : 
     295             : /// SimplifyAddOperands - Sort and simplify a list of add operands. NumAddRecs
     296             : /// is the number of SCEVAddRecExprs present, which are kept at the end of
     297             : /// the list.
     298             : ///
     299        6119 : static void SimplifyAddOperands(SmallVectorImpl<const SCEV *> &Ops,
     300             :                                 Type *Ty,
     301             :                                 ScalarEvolution &SE) {
     302        6119 :   unsigned NumAddRecs = 0;
     303       12912 :   for (unsigned i = Ops.size(); i > 0 && isa<SCEVAddRecExpr>(Ops[i-1]); --i)
     304          50 :     ++NumAddRecs;
     305             :   // Group Ops into non-addrecs and addrecs.
     306       18357 :   SmallVector<const SCEV *, 8> NoAddRecs(Ops.begin(), Ops.end() - NumAddRecs);
     307       24476 :   SmallVector<const SCEV *, 8> AddRecs(Ops.end() - NumAddRecs, Ops.end());
     308             :   // Let ScalarEvolution sort and simplify the non-addrecs list.
     309        6119 :   const SCEV *Sum = NoAddRecs.empty() ?
     310             :                     SE.getConstant(Ty, 0) :
     311        6119 :                     SE.getAddExpr(NoAddRecs);
     312             :   // If it returned an add, use the operands. Otherwise it simplified
     313             :   // the sum into a single value, so just use that.
     314        6119 :   Ops.clear();
     315        6131 :   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum))
     316          24 :     Ops.append(Add->op_begin(), Add->op_end());
     317        6107 :   else if (!Sum->isZero())
     318         250 :     Ops.push_back(Sum);
     319             :   // Then append the addrecs.
     320       12238 :   Ops.append(AddRecs.begin(), AddRecs.end());
     321        6119 : }
     322             : 
     323             : /// SplitAddRecs - Flatten a list of add operands, moving addrec start values
     324             : /// out to the top level. For example, convert {a + b,+,c} to a, b, {0,+,d}.
     325             : /// This helps expose more opportunities for folding parts of the expressions
     326             : /// into GEP indices.
     327             : ///
     328        7240 : static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops,
     329             :                          Type *Ty,
     330             :                          ScalarEvolution &SE) {
     331             :   // Find the addrecs.
     332       14480 :   SmallVector<const SCEV *, 8> AddRecs;
     333       22258 :   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     334       15712 :     while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) {
     335          56 :       const SCEV *Start = A->getStart();
     336          56 :       if (Start->isZero()) break;
     337          50 :       const SCEV *Zero = SE.getConstant(Ty, 0);
     338         100 :       AddRecs.push_back(SE.getAddRecExpr(Zero,
     339             :                                          A->getStepRecurrence(SE),
     340             :                                          A->getLoop(),
     341             :                                          A->getNoWrapFlags(SCEV::FlagNW)));
     342           4 :       if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) {
     343           8 :         Ops[i] = Zero;
     344           8 :         Ops.append(Add->op_begin(), Add->op_end());
     345           4 :         e += Add->getNumOperands();
     346             :       } else {
     347          92 :         Ops[i] = Start;
     348             :       }
     349             :     }
     350        7240 :   if (!AddRecs.empty()) {
     351             :     // Add the addrecs onto the end of the list.
     352          50 :     Ops.append(AddRecs.begin(), AddRecs.end());
     353             :     // Resort the operand list, moving any constants to the front.
     354          50 :     SimplifyAddOperands(Ops, Ty, SE);
     355             :   }
     356        7240 : }
     357             : 
     358             : /// expandAddToGEP - Expand an addition expression with a pointer type into
     359             : /// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps
     360             : /// BasicAliasAnalysis and other passes analyze the result. See the rules
     361             : /// for getelementptr vs. inttoptr in
     362             : /// http://llvm.org/docs/LangRef.html#pointeraliasing
     363             : /// for details.
     364             : ///
     365             : /// Design note: The correctness of using getelementptr here depends on
     366             : /// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as
     367             : /// they may introduce pointer arithmetic which may not be safely converted
     368             : /// into getelementptr.
     369             : ///
     370             : /// Design note: It might seem desirable for this function to be more
     371             : /// loop-aware. If some of the indices are loop-invariant while others
     372             : /// aren't, it might seem desirable to emit multiple GEPs, keeping the
     373             : /// loop-invariant portions of the overall computation outside the loop.
     374             : /// However, there are a few reasons this is not done here. Hoisting simple
     375             : /// arithmetic is a low-level optimization that often isn't very
     376             : /// important until late in the optimization process. In fact, passes
     377             : /// like InstructionCombining will combine GEPs, even if it means
     378             : /// pushing loop-invariant computation down into loops, so even if the
     379             : /// GEPs were split here, the work would quickly be undone. The
     380             : /// LoopStrengthReduction pass, which is usually run quite late (and
     381             : /// after the last InstructionCombining pass), takes care of hoisting
     382             : /// loop-invariant portions of expressions, after considering what
     383             : /// can be folded using target addressing modes.
     384             : ///
     385        7240 : Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin,
     386             :                                     const SCEV *const *op_end,
     387             :                                     PointerType *PTy,
     388             :                                     Type *Ty,
     389             :                                     Value *V) {
     390        7240 :   Type *OriginalElTy = PTy->getElementType();
     391        7240 :   Type *ElTy = OriginalElTy;
     392       14480 :   SmallVector<Value *, 4> GepIndices;
     393       14480 :   SmallVector<const SCEV *, 8> Ops(op_begin, op_end);
     394        7240 :   bool AnyNonZeroIndices = false;
     395             : 
     396             :   // Split AddRecs up into parts as either of the parts may be usable
     397             :   // without the other.
     398        7240 :   SplitAddRecs(Ops, Ty, SE);
     399             : 
     400        7240 :   Type *IntPtrTy = DL.getIntPtrType(PTy);
     401             : 
     402             :   // Descend down the pointer's type and attempt to convert the other
     403             :   // operands into GEP indices, at each level. The first index in a GEP
     404             :   // indexes into the array implied by the pointer operand; the rest of
     405             :   // the indices index into the element or field type selected by the
     406             :   // preceding index.
     407             :   for (;;) {
     408             :     // If the scale size is not 0, attempt to factor out a scale for
     409             :     // array indexing.
     410        9118 :     SmallVector<const SCEV *, 8> ScaledOps;
     411        8179 :     if (ElTy->isSized()) {
     412        8179 :       const SCEV *ElSize = SE.getSizeOfExpr(IntPtrTy, ElTy);
     413        8179 :       if (!ElSize->isZero()) {
     414       16322 :         SmallVector<const SCEV *, 8> NewOps;
     415       33285 :         for (const SCEV *Op : Ops) {
     416        8802 :           const SCEV *Remainder = SE.getConstant(Ty, 0);
     417        8802 :           if (FactorOutConstant(Op, Remainder, ElSize, SE, DL)) {
     418             :             // Op now has ElSize factored out.
     419        6439 :             ScaledOps.push_back(Op);
     420        6439 :             if (!Remainder->isZero())
     421          35 :               NewOps.push_back(Remainder);
     422             :             AnyNonZeroIndices = true;
     423             :           } else {
     424             :             // The operand was not divisible, so add it to the list of operands
     425             :             // we'll scan next iteration.
     426        2363 :             NewOps.push_back(Op);
     427             :           }
     428             :         }
     429             :         // If we made any changes, update Ops.
     430        8161 :         if (!ScaledOps.empty()) {
     431        6069 :           Ops = NewOps;
     432        6069 :           SimplifyAddOperands(Ops, Ty, SE);
     433             :         }
     434             :       }
     435             :     }
     436             : 
     437             :     // Record the scaled array index for this level of the type. If
     438             :     // we didn't find any operands that could be factored, tentatively
     439             :     // assume that element zero was selected (since the zero offset
     440             :     // would obviously be folded away).
     441       14248 :     Value *Scaled = ScaledOps.empty() ?
     442             :                     Constant::getNullValue(Ty) :
     443       14248 :                     expandCodeFor(SE.getAddExpr(ScaledOps), Ty);
     444        8179 :     GepIndices.push_back(Scaled);
     445             : 
     446             :     // Collect struct field index operands.
     447        1134 :     while (StructType *STy = dyn_cast<StructType>(ElTy)) {
     448        1134 :       bool FoundFieldNo = false;
     449             :       // An empty struct has no fields.
     450        1134 :       if (STy->getNumElements() == 0) break;
     451             :       // Field offsets are known. See if a constant offset falls within any of
     452             :       // the struct fields.
     453        1132 :       if (Ops.empty())
     454             :         break;
     455        1375 :       if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0]))
     456        1056 :         if (SE.getTypeSizeInBits(C->getType()) <= 64) {
     457         528 :           const StructLayout &SL = *DL.getStructLayout(STy);
     458        1056 :           uint64_t FullOffset = C->getValue()->getZExtValue();
     459         528 :           if (FullOffset < SL.getSizeInBytes()) {
     460         497 :             unsigned ElIdx = SL.getElementContainingOffset(FullOffset);
     461         497 :             GepIndices.push_back(
     462         994 :                 ConstantInt::get(Type::getInt32Ty(Ty->getContext()), ElIdx));
     463         497 :             ElTy = STy->getTypeAtIndex(ElIdx);
     464         994 :             Ops[0] =
     465        1491 :                 SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx));
     466         497 :             AnyNonZeroIndices = true;
     467         497 :             FoundFieldNo = true;
     468             :           }
     469             :         }
     470             :       // If no struct field offsets were found, tentatively assume that
     471             :       // field zero was selected (since the zero offset would obviously
     472             :       // be folded away).
     473         847 :       if (!FoundFieldNo) {
     474         350 :         ElTy = STy->getTypeAtIndex(0u);
     475         350 :         GepIndices.push_back(
     476         700 :           Constant::getNullValue(Type::getInt32Ty(Ty->getContext())));
     477             :       }
     478             :     }
     479             : 
     480         939 :     if (ArrayType *ATy = dyn_cast<ArrayType>(ElTy))
     481         939 :       ElTy = ATy->getElementType();
     482             :     else
     483             :       break;
     484             :   }
     485             : 
     486             :   // If none of the operands were convertible to proper GEP indices, cast
     487             :   // the base to i8* and do an ugly getelementptr with that. It's still
     488             :   // better than ptrtoint+arithmetic+inttoptr at least.
     489        7240 :   if (!AnyNonZeroIndices) {
     490             :     // Cast the base to i8*.
     491        1151 :     V = InsertNoopCastOfTo(V,
     492        1151 :        Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace()));
     493             : 
     494             :     assert(!isa<Instruction>(V) ||
     495             :            SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()));
     496             : 
     497             :     // Expand the operands for a plain byte offset.
     498        1151 :     Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty);
     499             : 
     500             :     // Fold a GEP with constant operands.
     501         223 :     if (Constant *CLHS = dyn_cast<Constant>(V))
     502           7 :       if (Constant *CRHS = dyn_cast<Constant>(Idx))
     503          14 :         return ConstantExpr::getGetElementPtr(Type::getInt8Ty(Ty->getContext()),
     504           7 :                                               CLHS, CRHS);
     505             : 
     506             :     // Do a quick scan to see if we have this GEP nearby.  If so, reuse it.
     507        1144 :     unsigned ScanLimit = 6;
     508        2288 :     BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
     509             :     // Scanning starts from the last instruction before the insertion point.
     510        1144 :     BasicBlock::iterator IP = Builder.GetInsertPoint();
     511        1144 :     if (IP != BlockBegin) {
     512             :       --IP;
     513       14007 :       for (; ScanLimit; --IP, --ScanLimit) {
     514             :         // Don't count dbg.value against the ScanLimit, to avoid perturbing the
     515             :         // generated code.
     516        6842 :         if (isa<DbgInfoIntrinsic>(IP))
     517         895 :           ScanLimit++;
     518       15448 :         if (IP->getOpcode() == Instruction::GetElementPtr &&
     519       10568 :             IP->getOperand(0) == V && IP->getOperand(1) == Idx)
     520             :           return &*IP;
     521        6809 :         if (IP == BlockBegin) break;
     522             :       }
     523             :     }
     524             : 
     525             :     // Save the original insertion point so we can restore it when we're done.
     526        2222 :     SCEVInsertPointGuard Guard(Builder, this);
     527             : 
     528             :     // Move the insertion point out of as many loops as we can.
     529        2246 :     while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
     530         998 :       if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break;
     531          12 :       BasicBlock *Preheader = L->getLoopPreheader();
     532          12 :       if (!Preheader) break;
     533             : 
     534             :       // Ok, move up a level.
     535          24 :       Builder.SetInsertPoint(Preheader->getTerminator());
     536          12 :     }
     537             : 
     538             :     // Emit a GEP.
     539        3333 :     Value *GEP = Builder.CreateGEP(Builder.getInt8Ty(), V, Idx, "uglygep");
     540        1111 :     rememberInstruction(GEP);
     541             : 
     542             :     return GEP;
     543             :   }
     544             : 
     545             :   {
     546       12178 :     SCEVInsertPointGuard Guard(Builder, this);
     547             : 
     548             :     // Move the insertion point out of as many loops as we can.
     549       12562 :     while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
     550        4749 :       if (!L->isLoopInvariant(V)) break;
     551             : 
     552        1823 :       bool AnyIndexNotLoopInvariant = any_of(
     553        3964 :           GepIndices, [L](Value *Op) { return !L->isLoopInvariant(Op); });
     554             : 
     555        1823 :       if (AnyIndexNotLoopInvariant)
     556             :         break;
     557             : 
     558         192 :       BasicBlock *Preheader = L->getLoopPreheader();
     559         192 :       if (!Preheader) break;
     560             : 
     561             :       // Ok, move up a level.
     562         384 :       Builder.SetInsertPoint(Preheader->getTerminator());
     563         192 :     }
     564             : 
     565             :     // Insert a pretty getelementptr. Note that this GEP is not marked inbounds,
     566             :     // because ScalarEvolution may have changed the address arithmetic to
     567             :     // compute a value which is beyond the end of the allocated object.
     568        6089 :     Value *Casted = V;
     569        6089 :     if (V->getType() != PTy)
     570          50 :       Casted = InsertNoopCastOfTo(Casted, PTy);
     571       18267 :     Value *GEP = Builder.CreateGEP(OriginalElTy, Casted, GepIndices, "scevgep");
     572        6089 :     Ops.push_back(SE.getUnknown(GEP));
     573        6089 :     rememberInstruction(GEP);
     574             :   }
     575             : 
     576        6089 :   return expand(SE.getAddExpr(Ops));
     577             : }
     578             : 
     579             : /// PickMostRelevantLoop - Given two loops pick the one that's most relevant for
     580             : /// SCEV expansion. If they are nested, this is the most nested. If they are
     581             : /// neighboring, pick the later.
     582       10417 : static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B,
     583             :                                         DominatorTree &DT) {
     584       10417 :   if (!A) return B;
     585         394 :   if (!B) return A;
     586         344 :   if (A->contains(B)) return B;
     587         186 :   if (B->contains(A)) return A;
     588          72 :   if (DT.dominates(A->getHeader(), B->getHeader())) return B;
     589          39 :   if (DT.dominates(B->getHeader(), A->getHeader())) return A;
     590             :   return A; // Arbitrarily break the tie.
     591             : }
     592             : 
     593             : /// getRelevantLoop - Get the most relevant loop associated with the given
     594             : /// expression, according to PickMostRelevantLoop.
     595       31873 : const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) {
     596             :   // Test whether we've already computed the most relevant loop for this SCEV.
     597      127492 :   auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr));
     598       31873 :   if (!Pair.second)
     599        9433 :     return Pair.first->second;
     600             : 
     601       44880 :   if (isa<SCEVConstant>(S))
     602             :     // A constant has no relevant loops.
     603             :     return nullptr;
     604       29684 :   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
     605       19348 :     if (const Instruction *I = dyn_cast<Instruction>(U->getValue()))
     606       13582 :       return Pair.first->second = SE.LI.getLoopFor(I->getParent());
     607             :     // A non-instruction has no relevant loops.
     608             :     return nullptr;
     609             :   }
     610        8059 :   if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) {
     611        3489 :     const Loop *L = nullptr;
     612        3553 :     if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
     613          64 :       L = AR->getLoop();
     614       11173 :     for (const SCEV *Op : N->operands())
     615        7684 :       L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT);
     616        6978 :     return RelevantLoops[N] = L;
     617             :   }
     618        1869 :   if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) {
     619         788 :     const Loop *Result = getRelevantLoop(C->getOperand());
     620        1576 :     return RelevantLoops[C] = Result;
     621             :   }
     622         586 :   if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
     623         293 :     const Loop *Result = PickMostRelevantLoop(
     624         586 :         getRelevantLoop(D->getLHS()), getRelevantLoop(D->getRHS()), SE.DT);
     625         586 :     return RelevantLoops[D] = Result;
     626             :   }
     627           0 :   llvm_unreachable("Unexpected SCEV type!");
     628             : }
     629             : 
     630             : namespace {
     631             : 
     632             : /// LoopCompare - Compare loops by PickMostRelevantLoop.
     633             : class LoopCompare {
     634             :   DominatorTree &DT;
     635             : public:
     636             :   explicit LoopCompare(DominatorTree &dt) : DT(dt) {}
     637             : 
     638       14655 :   bool operator()(std::pair<const Loop *, const SCEV *> LHS,
     639             :                   std::pair<const Loop *, const SCEV *> RHS) const {
     640             :     // Keep pointer operands sorted at the end.
     641       43965 :     if (LHS.second->getType()->isPointerTy() !=
     642       29310 :         RHS.second->getType()->isPointerTy())
     643       14560 :       return LHS.second->getType()->isPointerTy();
     644             : 
     645             :     // Compare loops with PickMostRelevantLoop.
     646        7375 :     if (LHS.first != RHS.first)
     647        2440 :       return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first;
     648             : 
     649             :     // If one operand is a non-constant negative and the other is not,
     650             :     // put the non-constant negative on the right so that a sub can
     651             :     // be used instead of a negate and add.
     652        4935 :     if (LHS.second->isNonConstantNegative()) {
     653         127 :       if (!RHS.second->isNonConstantNegative())
     654             :         return false;
     655        4808 :     } else if (RHS.second->isNonConstantNegative())
     656             :       return true;
     657             : 
     658             :     // Otherwise they are equivalent according to this comparison.
     659             :     return false;
     660             :   }
     661             : };
     662             : 
     663             : }
     664             : 
     665        9734 : Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) {
     666       19468 :   Type *Ty = SE.getEffectiveSCEVType(S->getType());
     667             : 
     668             :   // Collect all the add operands in a loop, along with their associated loops.
     669             :   // Iterate in reverse so that constants are emitted last, all else equal, and
     670             :   // so that pointer operands are inserted first, which the code below relies on
     671             :   // to form more involved GEPs.
     672       19468 :   SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
     673       29202 :   for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(S->op_end()),
     674       39806 :        E(S->op_begin()); I != E; ++I)
     675       61014 :     OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
     676             : 
     677             :   // Sort by loop. Use a stable sort so that constants follow non-constants and
     678             :   // pointer operands precede non-pointer operands.
     679       38936 :   std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(SE.DT));
     680             : 
     681             :   // Emit instructions to add all the operands. Hoist as much as possible
     682             :   // out of loops, and form meaningful getelementptrs where possible.
     683        9734 :   Value *Sum = nullptr;
     684       19468 :   for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) {
     685       19810 :     const Loop *CurLoop = I->first;
     686       19810 :     const SCEV *Op = I->second;
     687       19810 :     if (!Sum) {
     688             :       // This is the first operand. Just expand it.
     689        9734 :       Sum = expand(Op);
     690        9734 :       ++I;
     691       16659 :     } else if (PointerType *PTy = dyn_cast<PointerType>(Sum->getType())) {
     692             :       // The running sum expression is a pointer. Try to form a getelementptr
     693             :       // at this level with that as the base.
     694        6583 :       SmallVector<const SCEV *, 4> NewOps;
     695       20805 :       for (; I != E && I->first == CurLoop; ++I) {
     696             :         // If the operand is SCEVUnknown and not instructions, peek through
     697             :         // it, to enable more of it to be folded into the GEP.
     698        7111 :         const SCEV *X = I->second;
     699       10646 :         if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X))
     700        7070 :           if (!isa<Instruction>(U->getValue()))
     701        4456 :             X = SE.getSCEV(U->getValue());
     702        7111 :         NewOps.push_back(X);
     703             :       }
     704       19749 :       Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum);
     705        3493 :     } else if (PointerType *PTy = dyn_cast<PointerType>(Op->getType())) {
     706             :       // The running sum is an integer, and there's a pointer at this level.
     707             :       // Try to form a getelementptr. If the running sum is instructions,
     708             :       // use a SCEVUnknown to avoid re-analyzing them.
     709           0 :       SmallVector<const SCEV *, 4> NewOps;
     710           0 :       NewOps.push_back(isa<Instruction>(Sum) ? SE.getUnknown(Sum) :
     711           0 :                                                SE.getSCEV(Sum));
     712           0 :       for (++I; I != E && I->first == CurLoop; ++I)
     713           0 :         NewOps.push_back(I->second);
     714           0 :       Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, expand(Op));
     715        3493 :     } else if (Op->isNonConstantNegative()) {
     716             :       // Instead of doing a negate and add, just do a subtract.
     717         359 :       Value *W = expandCodeFor(SE.getNegativeSCEV(Op), Ty);
     718         359 :       Sum = InsertNoopCastOfTo(Sum, Ty);
     719         359 :       Sum = InsertBinop(Instruction::Sub, Sum, W);
     720         359 :       ++I;
     721             :     } else {
     722             :       // A simple add.
     723        3134 :       Value *W = expandCodeFor(Op, Ty);
     724        3134 :       Sum = InsertNoopCastOfTo(Sum, Ty);
     725             :       // Canonicalize a constant to the RHS.
     726        3134 :       if (isa<Constant>(Sum)) std::swap(Sum, W);
     727        3134 :       Sum = InsertBinop(Instruction::Add, Sum, W);
     728        3134 :       ++I;
     729             :     }
     730             :   }
     731             : 
     732       19468 :   return Sum;
     733             : }
     734             : 
     735         964 : Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
     736        1928 :   Type *Ty = SE.getEffectiveSCEVType(S->getType());
     737             : 
     738             :   // Collect all the mul operands in a loop, along with their associated loops.
     739             :   // Iterate in reverse so that constants are emitted last, all else equal.
     740        1928 :   SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
     741        2892 :   for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()),
     742        4405 :        E(S->op_begin()); I != E; ++I)
     743        7431 :     OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
     744             : 
     745             :   // Sort by loop. Use a stable sort so that constants follow non-constants.
     746        3856 :   std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(SE.DT));
     747             : 
     748             :   // Emit instructions to mul all the operands. Hoist as much as possible
     749             :   // out of loops.
     750         964 :   Value *Prod = nullptr;
     751         964 :   auto I = OpsAndLoops.begin();
     752             : 
     753             :   // Expand the calculation of X pow N in the following manner:
     754             :   // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then:
     755             :   // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK).
     756        9915 :   const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() {
     757        1872 :     auto E = I;
     758             :     // Calculate how many times the same operand from the same loop is included
     759             :     // into this power.
     760        1872 :     uint64_t Exponent = 0;
     761        1872 :     const uint64_t MaxExponent = UINT64_MAX >> 1;
     762             :     // No one sane will ever try to calculate such huge exponents, but if we
     763             :     // need this, we stop on UINT64_MAX / 2 because we need to exit the loop
     764             :     // below when the power of 2 exceeds our Exponent, and we want it to be
     765             :     // 1u << 31 at most to not deal with unsigned overflow.
     766       13108 :     while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) {
     767        2341 :       ++Exponent;
     768        2341 :       ++E;
     769             :     }
     770             :     assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?");
     771             : 
     772             :     // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them
     773             :     // that are needed into the result.
     774        1872 :     Value *P = expandCodeFor(I->second, Ty);
     775        1872 :     Value *Result = nullptr;
     776        1872 :     if (Exponent & 1)
     777        1855 :       Result = P;
     778        2036 :     for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) {
     779          82 :       P = InsertBinop(Instruction::Mul, P, P);
     780          82 :       if (Exponent & BinExp)
     781          25 :         Result = Result ? InsertBinop(Instruction::Mul, Result, P) : P;
     782             :     }
     783             : 
     784        1872 :     I = E;
     785             :     assert(Result && "Nothing was expanded?");
     786        1872 :     return Result;
     787         964 :   };
     788             : 
     789        2972 :   while (I != OpsAndLoops.end()) {
     790        2008 :     if (!Prod) {
     791             :       // This is the first operand. Just expand it.
     792         964 :       Prod = ExpandOpBinPowN();
     793        1044 :     } else if (I->second->isAllOnesValue()) {
     794             :       // Instead of doing a multiply by negative one, just do a negate.
     795         136 :       Prod = InsertNoopCastOfTo(Prod, Ty);
     796         136 :       Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod);
     797         136 :       ++I;
     798             :     } else {
     799             :       // A simple mul.
     800         908 :       Value *W = ExpandOpBinPowN();
     801         908 :       Prod = InsertNoopCastOfTo(Prod, Ty);
     802             :       // Canonicalize a constant to the RHS.
     803         908 :       if (isa<Constant>(Prod)) std::swap(Prod, W);
     804             :       const APInt *RHS;
     805        1816 :       if (match(W, m_Power2(RHS))) {
     806             :         // Canonicalize Prod*(1<<C) to Prod<<C.
     807             :         assert(!Ty->isVectorTy() && "vector types are not SCEVable");
     808        1018 :         Prod = InsertBinop(Instruction::Shl, Prod,
     809        1527 :                            ConstantInt::get(Ty, RHS->logBase2()));
     810             :       } else {
     811         399 :         Prod = InsertBinop(Instruction::Mul, Prod, W);
     812             :       }
     813             :     }
     814             :   }
     815             : 
     816        1928 :   return Prod;
     817             : }
     818             : 
     819         179 : Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
     820         358 :   Type *Ty = SE.getEffectiveSCEVType(S->getType());
     821             : 
     822         179 :   Value *LHS = expandCodeFor(S->getLHS(), Ty);
     823         343 :   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
     824         164 :     const APInt &RHS = SC->getAPInt();
     825         164 :     if (RHS.isPowerOf2())
     826             :       return InsertBinop(Instruction::LShr, LHS,
     827         109 :                          ConstantInt::get(Ty, RHS.logBase2()));
     828             :   }
     829             : 
     830          70 :   Value *RHS = expandCodeFor(S->getRHS(), Ty);
     831          70 :   return InsertBinop(Instruction::UDiv, LHS, RHS);
     832             : }
     833             : 
     834             : /// Move parts of Base into Rest to leave Base with the minimal
     835             : /// expression that provides a pointer operand suitable for a
     836             : /// GEP expansion.
     837         199 : static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest,
     838             :                               ScalarEvolution &SE) {
     839         201 :   while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) {
     840           1 :     Base = A->getStart();
     841           3 :     Rest = SE.getAddExpr(Rest,
     842             :                          SE.getAddRecExpr(SE.getConstant(A->getType(), 0),
     843             :                                           A->getStepRecurrence(SE),
     844             :                                           A->getLoop(),
     845             :                                           A->getNoWrapFlags(SCEV::FlagNW)));
     846           1 :   }
     847         251 :   if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) {
     848         104 :     Base = A->getOperand(A->getNumOperands()-1);
     849         208 :     SmallVector<const SCEV *, 8> NewAddOps(A->op_begin(), A->op_end());
     850         104 :     NewAddOps.back() = Rest;
     851          52 :     Rest = SE.getAddExpr(NewAddOps);
     852          52 :     ExposePointerBase(Base, Rest, SE);
     853             :   }
     854         199 : }
     855             : 
     856             : /// Determine if this is a well-behaved chain of instructions leading back to
     857             : /// the PHI. If so, it may be reused by expanded expressions.
     858           9 : bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
     859             :                                          const Loop *L) {
     860          54 :   if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) ||
     861          11 :       (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))
     862             :     return false;
     863             :   // If any of the operands don't dominate the insert position, bail.
     864             :   // Addrec operands are always loop-invariant, so this can only happen
     865             :   // if there are instructions which haven't been hoisted.
     866           8 :   if (L == IVIncInsertLoop) {
     867           0 :     for (User::op_iterator OI = IncV->op_begin()+1,
     868           0 :            OE = IncV->op_end(); OI != OE; ++OI)
     869           0 :       if (Instruction *OInst = dyn_cast<Instruction>(OI))
     870           0 :         if (!SE.DT.dominates(OInst, IVIncInsertPos))
     871             :           return false;
     872             :   }
     873             :   // Advance to the next instruction.
     874          24 :   IncV = dyn_cast<Instruction>(IncV->getOperand(0));
     875             :   if (!IncV)
     876             :     return false;
     877             : 
     878           8 :   if (IncV->mayHaveSideEffects())
     879             :     return false;
     880             : 
     881           8 :   if (IncV != PN)
     882             :     return true;
     883             : 
     884             :   return isNormalAddRecExprPHI(PN, IncV, L);
     885             : }
     886             : 
     887             : /// getIVIncOperand returns an induction variable increment's induction
     888             : /// variable operand.
     889             : ///
     890             : /// If allowScale is set, any type of GEP is allowed as long as the nonIV
     891             : /// operands dominate InsertPos.
     892             : ///
     893             : /// If allowScale is not set, ensure that a GEP increment conforms to one of the
     894             : /// simple patterns generated by getAddRecExprPHILiterally and
     895             : /// expandAddtoGEP. If the pattern isn't recognized, return NULL.
     896        3865 : Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV,
     897             :                                            Instruction *InsertPos,
     898             :                                            bool allowScale) {
     899        3865 :   if (IncV == InsertPos)
     900             :     return nullptr;
     901             : 
     902        3863 :   switch (IncV->getOpcode()) {
     903             :   default:
     904             :     return nullptr;
     905             :   // Check for a simple Add/Sub or GEP of a loop invariant step.
     906        3021 :   case Instruction::Add:
     907             :   case Instruction::Sub: {
     908        6149 :     Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));
     909         107 :     if (!OInst || SE.DT.dominates(OInst, InsertPos))
     910        6024 :       return dyn_cast<Instruction>(IncV->getOperand(0));
     911             :     return nullptr;
     912             :   }
     913          37 :   case Instruction::BitCast:
     914          74 :     return dyn_cast<Instruction>(IncV->getOperand(0));
     915         784 :   case Instruction::GetElementPtr:
     916        3146 :     for (auto I = IncV->op_begin() + 1, E = IncV->op_end(); I != E; ++I) {
     917         793 :       if (isa<Constant>(*I))
     918         793 :         continue;
     919          17 :       if (Instruction *OInst = dyn_cast<Instruction>(*I)) {
     920          17 :         if (!SE.DT.dominates(OInst, InsertPos))
     921             :           return nullptr;
     922             :       }
     923          25 :       if (allowScale) {
     924             :         // allow any kind of GEP as long as it can be hoisted.
     925           1 :         continue;
     926             :       }
     927             :       // This must be a pointer addition of constants (pretty), which is already
     928             :       // handled, or some number of address-size elements (ugly). Ugly geps
     929             :       // have 2 operands. i1* is used by the expander to represent an
     930             :       // address-size element.
     931          48 :       if (IncV->getNumOperands() != 2)
     932             :         return nullptr;
     933          72 :       unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace();
     934          48 :       if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS)
     935          42 :           && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS))
     936             :         return nullptr;
     937             :       break;
     938         759 :     }
     939        1538 :     return dyn_cast<Instruction>(IncV->getOperand(0));
     940             :   }
     941             : }
     942             : 
     943             : /// If the insert point of the current builder or any of the builders on the
     944             : /// stack of saved builders has 'I' as its insert point, update it to point to
     945             : /// the instruction after 'I'.  This is intended to be used when the instruction
     946             : /// 'I' is being moved.  If this fixup is not done and 'I' is moved to a
     947             : /// different block, the inconsistent insert point (with a mismatched
     948             : /// Instruction and Block) can lead to an instruction being inserted in a block
     949             : /// other than its parent.
     950         226 : void SCEVExpander::fixupInsertPoints(Instruction *I) {
     951         226 :   BasicBlock::iterator It(*I);
     952         226 :   BasicBlock::iterator NewInsertPt = std::next(It);
     953         226 :   if (Builder.GetInsertPoint() == It)
     954           2 :     Builder.SetInsertPoint(&*NewInsertPt);
     955         679 :   for (auto *InsertPtGuard : InsertPointGuards)
     956           1 :     if (InsertPtGuard->GetInsertPoint() == It)
     957           1 :       InsertPtGuard->SetInsertPoint(NewInsertPt);
     958         226 : }
     959             : 
     960             : /// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make
     961             : /// it available to other uses in this loop. Recursively hoist any operands,
     962             : /// until we reach a value that dominates InsertPos.
     963        3711 : bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) {
     964        3711 :   if (SE.DT.dominates(IncV, InsertPos))
     965             :       return true;
     966             : 
     967             :   // InsertPos must itself dominate IncV so that IncV's new position satisfies
     968             :   // its existing users.
     969         693 :   if (isa<PHINode>(InsertPos) ||
     970         227 :       !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))
     971             :     return false;
     972             : 
     973         227 :   if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
     974             :     return false;
     975             : 
     976             :   // Check that the chain of IV operands leading back to Phi can be hoisted.
     977             :   SmallVector<Instruction*, 4> IVIncs;
     978             :   for(;;) {
     979         230 :     Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true);
     980         230 :     if (!Oper)
     981             :       return false;
     982             :     // IncV is safe to hoist.
     983         228 :     IVIncs.push_back(IncV);
     984         228 :     IncV = Oper;
     985         228 :     if (SE.DT.dominates(IncV, InsertPos))
     986             :       break;
     987             :   }
     988         901 :   for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) {
     989         226 :     fixupInsertPoints(*I);
     990         226 :     (*I)->moveBefore(InsertPos);
     991             :   }
     992             :   return true;
     993             : }
     994             : 
     995             : /// Determine if this cyclic phi is in a form that would have been generated by
     996             : /// LSR. We don't care if the phi was actually expanded in this pass, as long
     997             : /// as it is in a low-cost form, for example, no implied multiplication. This
     998             : /// should match any patterns generated by getAddRecExprPHILiterally and
     999             : /// expandAddtoGEP.
    1000        3584 : bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
    1001             :                                            const Loop *L) {
    1002        3584 :   for(Instruction *IVOper = IncV;
    1003        7270 :       (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
    1004        3635 :                                 /*allowScale=*/false));) {
    1005        3590 :     if (IVOper == PN)
    1006             :       return true;
    1007             :   }
    1008             :   return false;
    1009             : }
    1010             : 
    1011             : /// expandIVInc - Expand an IV increment at Builder's current InsertPos.
    1012             : /// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may
    1013             : /// need to materialize IV increments elsewhere to handle difficult situations.
    1014        2383 : Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
    1015             :                                  Type *ExpandTy, Type *IntTy,
    1016             :                                  bool useSubtract) {
    1017             :   Value *IncV;
    1018             :   // If the PHI is a pointer, use a GEP, otherwise use an add or sub.
    1019        2383 :   if (ExpandTy->isPointerTy()) {
    1020         603 :     PointerType *GEPPtrTy = cast<PointerType>(ExpandTy);
    1021             :     // If the step isn't constant, don't use an implicitly scaled GEP, because
    1022             :     // that would require a multiply inside the loop.
    1023        1206 :     if (!isa<ConstantInt>(StepV))
    1024         100 :       GEPPtrTy = PointerType::get(Type::getInt1Ty(SE.getContext()),
    1025             :                                   GEPPtrTy->getAddressSpace());
    1026         603 :     const SCEV *const StepArray[1] = { SE.getSCEV(StepV) };
    1027         603 :     IncV = expandAddToGEP(StepArray, StepArray+1, GEPPtrTy, IntTy, PN);
    1028         603 :     if (IncV->getType() != PN->getType()) {
    1029         699 :       IncV = Builder.CreateBitCast(IncV, PN->getType());
    1030         233 :       rememberInstruction(IncV);
    1031             :     }
    1032             :   } else {
    1033        3560 :     IncV = useSubtract ?
    1034        1832 :       Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") :
    1035        8848 :       Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next");
    1036        1780 :     rememberInstruction(IncV);
    1037             :   }
    1038        2383 :   return IncV;
    1039             : }
    1040             : 
    1041             : /// \brief Hoist the addrec instruction chain rooted in the loop phi above the
    1042             : /// position. This routine assumes that this is possible (has been checked).
    1043        3440 : void SCEVExpander::hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
    1044             :                                   Instruction *Pos, PHINode *LoopPhi) {
    1045             :   do {
    1046        3440 :     if (DT->dominates(InstToHoist, Pos))
    1047             :       break;
    1048             :     // Make sure the increment is where we want it. But don't move it
    1049             :     // down past a potential existing post-inc user.
    1050           0 :     fixupInsertPoints(InstToHoist);
    1051           0 :     InstToHoist->moveBefore(Pos);
    1052           0 :     Pos = InstToHoist;
    1053           0 :     InstToHoist = cast<Instruction>(InstToHoist->getOperand(0));
    1054           0 :   } while (InstToHoist != LoopPhi);
    1055        3440 : }
    1056             : 
    1057             : /// \brief Check whether we can cheaply express the requested SCEV in terms of
    1058             : /// the available PHI SCEV by truncation and/or inversion of the step.
    1059          12 : static bool canBeCheaplyTransformed(ScalarEvolution &SE,
    1060             :                                     const SCEVAddRecExpr *Phi,
    1061             :                                     const SCEVAddRecExpr *Requested,
    1062             :                                     bool &InvertStep) {
    1063          24 :   Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType());
    1064          24 :   Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType());
    1065             : 
    1066          24 :   if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth())
    1067             :     return false;
    1068             : 
    1069             :   // Try truncate it if necessary.
    1070          24 :   Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy));
    1071             :   if (!Phi)
    1072             :     return false;
    1073             : 
    1074             :   // Check whether truncation will help.
    1075          12 :   if (Phi == Requested) {
    1076           1 :     InvertStep = false;
    1077           1 :     return true;
    1078             :   }
    1079             : 
    1080             :   // Check whether inverting will help: {R,+,-1} == R - {0,+,1}.
    1081          22 :   if (SE.getAddExpr(Requested->getStart(),
    1082             :                     SE.getNegativeSCEV(Requested)) == Phi) {
    1083           2 :     InvertStep = true;
    1084           2 :     return true;
    1085             :   }
    1086             : 
    1087             :   return false;
    1088             : }
    1089             : 
    1090        2369 : static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
    1091        7107 :   if (!isa<IntegerType>(AR->getType()))
    1092             :     return false;
    1093             : 
    1094        7064 :   unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
    1095        3532 :   Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
    1096        1766 :   const SCEV *Step = AR->getStepRecurrence(SE);
    1097        1766 :   const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy),
    1098        1766 :                                             SE.getSignExtendExpr(AR, WideTy));
    1099             :   const SCEV *ExtendAfterOp =
    1100        1766 :     SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy);
    1101        1766 :   return ExtendAfterOp == OpAfterExtend;
    1102             : }
    1103             : 
    1104        2369 : static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
    1105        7107 :   if (!isa<IntegerType>(AR->getType()))
    1106             :     return false;
    1107             : 
    1108        7064 :   unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
    1109        3532 :   Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
    1110        1766 :   const SCEV *Step = AR->getStepRecurrence(SE);
    1111        1766 :   const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy),
    1112        1766 :                                             SE.getZeroExtendExpr(AR, WideTy));
    1113             :   const SCEV *ExtendAfterOp =
    1114        1766 :     SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy);
    1115        1766 :   return ExtendAfterOp == OpAfterExtend;
    1116             : }
    1117             : 
    1118             : /// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand
    1119             : /// the base addrec, which is the addrec without any non-loop-dominating
    1120             : /// values, and return the PHI.
    1121             : PHINode *
    1122        5875 : SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
    1123             :                                         const Loop *L,
    1124             :                                         Type *ExpandTy,
    1125             :                                         Type *IntTy,
    1126             :                                         Type *&TruncTy,
    1127             :                                         bool &InvertStep) {
    1128             :   assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position");
    1129             : 
    1130             :   // Reuse a previously-inserted PHI, if present.
    1131        5875 :   BasicBlock *LatchBlock = L->getLoopLatch();
    1132        5875 :   if (LatchBlock) {
    1133        5875 :     PHINode *AddRecPhiMatch = nullptr;
    1134        5875 :     Instruction *IncV = nullptr;
    1135        5875 :     TruncTy = nullptr;
    1136        5875 :     InvertStep = false;
    1137             : 
    1138             :     // Only try partially matching scevs that need truncation and/or
    1139             :     // step-inversion if we know this loop is outside the current loop.
    1140             :     bool TryNonMatchingSCEV =
    1141       11535 :         IVIncInsertLoop &&
    1142       17195 :         SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
    1143             : 
    1144       70101 :     for (auto &I : *L->getHeader()) {
    1145        9203 :       auto *PN = dyn_cast<PHINode>(&I);
    1146       46994 :       if (!PN || !SE.isSCEVable(PN->getType()))
    1147       37791 :         continue;
    1148             : 
    1149       16653 :       const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(PN));
    1150         967 :       if (!PhiSCEV)
    1151         967 :         continue;
    1152             : 
    1153        7843 :       bool IsMatchingSCEV = PhiSCEV == Normalized;
    1154             :       // We only handle truncation and inversion of phi recurrences for the
    1155             :       // expanded expression if the expanded expression's loop dominates the
    1156             :       // loop we insert to. Check now, so we can bail out early.
    1157        7843 :       if (!IsMatchingSCEV && !TryNonMatchingSCEV)
    1158        4295 :           continue;
    1159             : 
    1160             :       Instruction *TempIncV =
    1161        7096 :           cast<Instruction>(PN->getIncomingValueForBlock(LatchBlock));
    1162             : 
    1163             :       // Check whether we can reuse this PHI node.
    1164        3548 :       if (LSRMode) {
    1165        3539 :         if (!isExpandedAddRecExprPHI(PN, TempIncV, L))
    1166          39 :           continue;
    1167        3500 :         if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos))
    1168           0 :           continue;
    1169             :       } else {
    1170           9 :         if (!isNormalAddRecExprPHI(PN, TempIncV, L))
    1171           7 :           continue;
    1172             :       }
    1173             : 
    1174             :       // Stop if we have found an exact match SCEV.
    1175        3502 :       if (IsMatchingSCEV) {
    1176        3490 :         IncV = TempIncV;
    1177        3490 :         TruncTy = nullptr;
    1178        3490 :         InvertStep = false;
    1179        3490 :         AddRecPhiMatch = PN;
    1180        3490 :         break;
    1181             :       }
    1182             : 
    1183             :       // Try whether the phi can be translated into the requested form
    1184             :       // (truncated and/or offset by a constant).
    1185          24 :       if ((!TruncTy || InvertStep) &&
    1186          12 :           canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) {
    1187             :         // Record the phi node. But don't stop we might find an exact match
    1188             :         // later.
    1189           3 :         AddRecPhiMatch = PN;
    1190           3 :         IncV = TempIncV;
    1191           6 :         TruncTy = SE.getEffectiveSCEVType(Normalized->getType());
    1192             :       }
    1193             :     }
    1194             : 
    1195        5875 :     if (AddRecPhiMatch) {
    1196             :       // Potentially, move the increment. We have made sure in
    1197             :       // isExpandedAddRecExprPHI or hoistIVInc that this is possible.
    1198        3493 :       if (L == IVIncInsertLoop)
    1199        3440 :         hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch);
    1200             : 
    1201             :       // Ok, the add recurrence looks usable.
    1202             :       // Remember this PHI, even in post-inc mode.
    1203       10479 :       InsertedValues.insert(AddRecPhiMatch);
    1204             :       // Remember the increment.
    1205        3493 :       rememberInstruction(IncV);
    1206        3493 :       return AddRecPhiMatch;
    1207             :     }
    1208             :   }
    1209             : 
    1210             :   // Save the original insertion point so we can restore it when we're done.
    1211        4764 :   SCEVInsertPointGuard Guard(Builder, this);
    1212             : 
    1213             :   // Another AddRec may need to be recursively expanded below. For example, if
    1214             :   // this AddRec is quadratic, the StepV may itself be an AddRec in this
    1215             :   // loop. Remove this loop from the PostIncLoops set before expanding such
    1216             :   // AddRecs. Otherwise, we cannot find a valid position for the step
    1217             :   // (i.e. StepV can never dominate its loop header).  Ideally, we could do
    1218             :   // SavedIncLoops.swap(PostIncLoops), but we generally have a single element,
    1219             :   // so it's not worth implementing SmallPtrSet::swap.
    1220        7146 :   PostIncLoopSet SavedPostIncLoops = PostIncLoops;
    1221        2382 :   PostIncLoops.clear();
    1222             : 
    1223             :   // Expand code for the start value into the loop preheader.
    1224             :   assert(L->getLoopPreheader() &&
    1225             :          "Can't expand add recurrences without a loop preheader!");
    1226        2382 :   Value *StartV = expandCodeFor(Normalized->getStart(), ExpandTy,
    1227        7146 :                                 L->getLoopPreheader()->getTerminator());
    1228             : 
    1229             :   // StartV must have been be inserted into L's preheader to dominate the new
    1230             :   // phi.
    1231             :   assert(!isa<Instruction>(StartV) ||
    1232             :          SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),
    1233             :                                  L->getHeader()));
    1234             : 
    1235             :   // Expand code for the step value. Do this before creating the PHI so that PHI
    1236             :   // reuse code doesn't see an incomplete PHI.
    1237        2382 :   const SCEV *Step = Normalized->getStepRecurrence(SE);
    1238             :   // If the stride is negative, insert a sub instead of an add for the increment
    1239             :   // (unless it's a constant, because subtracts of constants are canonicalized
    1240             :   // to adds).
    1241        2382 :   bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
    1242             :   if (useSubtract)
    1243          13 :     Step = SE.getNegativeSCEV(Step);
    1244             :   // Expand the step somewhere that dominates the loop header.
    1245        7146 :   Value *StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front());
    1246             : 
    1247             :   // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if
    1248             :   // we actually do emit an addition.  It does not apply if we emit a
    1249             :   // subtraction.
    1250        2382 :   bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized);
    1251        2382 :   bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized);
    1252             : 
    1253             :   // Create the PHI.
    1254        4764 :   BasicBlock *Header = L->getHeader();
    1255        4764 :   Builder.SetInsertPoint(Header, Header->begin());
    1256        4764 :   pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
    1257        4764 :   PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE),
    1258        9528 :                                   Twine(IVName) + ".iv");
    1259        2382 :   rememberInstruction(PN);
    1260             : 
    1261             :   // Create the step instructions and populate the PHI.
    1262        9528 :   for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
    1263        4764 :     BasicBlock *Pred = *HPI;
    1264             : 
    1265             :     // Add a start value.
    1266       11910 :     if (!L->contains(Pred)) {
    1267        2382 :       PN->addIncoming(StartV, Pred);
    1268        2382 :       continue;
    1269             :     }
    1270             : 
    1271             :     // Create a step value and add it to the PHI.
    1272             :     // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the
    1273             :     // instructions at IVIncInsertPos.
    1274        2674 :     Instruction *InsertPos = L == IVIncInsertLoop ?
    1275        2382 :       IVIncInsertPos : Pred->getTerminator();
    1276        2382 :     Builder.SetInsertPoint(InsertPos);
    1277        2382 :     Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
    1278             : 
    1279        4764 :     if (isa<OverflowingBinaryOperator>(IncV)) {
    1280        1779 :       if (IncrementIsNUW)
    1281        1500 :         cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
    1282        1779 :       if (IncrementIsNSW)
    1283        2258 :         cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
    1284             :     }
    1285        2382 :     PN->addIncoming(IncV, Pred);
    1286             :   }
    1287             : 
    1288             :   // After expanding subexpressions, restore the PostIncLoops set so the caller
    1289             :   // can ensure that IVIncrement dominates the current uses.
    1290        4764 :   PostIncLoops = SavedPostIncLoops;
    1291             : 
    1292             :   // Remember this PHI, even in post-inc mode.
    1293        7146 :   InsertedValues.insert(PN);
    1294             : 
    1295        2382 :   return PN;
    1296             : }
    1297             : 
    1298        5875 : Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
    1299       11750 :   Type *STy = S->getType();
    1300        5875 :   Type *IntTy = SE.getEffectiveSCEVType(STy);
    1301        5875 :   const Loop *L = S->getLoop();
    1302             : 
    1303             :   // Determine a normalized form of this expression, which is the expression
    1304             :   // before any post-inc adjustment is made.
    1305        5875 :   const SCEVAddRecExpr *Normalized = S;
    1306        5875 :   if (PostIncLoops.count(L)) {
    1307        4568 :     PostIncLoopSet Loops;
    1308        2284 :     Loops.insert(L);
    1309        4568 :     Normalized = cast<SCEVAddRecExpr>(normalizeForPostIncUse(S, Loops, SE));
    1310             :   }
    1311             : 
    1312             :   // Strip off any non-loop-dominating component from the addrec start.
    1313       11750 :   const SCEV *Start = Normalized->getStart();
    1314        5875 :   const SCEV *PostLoopOffset = nullptr;
    1315       11750 :   if (!SE.properlyDominates(Start, L->getHeader())) {
    1316           1 :     PostLoopOffset = Start;
    1317           2 :     Start = SE.getConstant(Normalized->getType(), 0);
    1318           3 :     Normalized = cast<SCEVAddRecExpr>(
    1319           1 :       SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE),
    1320             :                        Normalized->getLoop(),
    1321             :                        Normalized->getNoWrapFlags(SCEV::FlagNW)));
    1322             :   }
    1323             : 
    1324             :   // Strip off any non-loop-dominating component from the addrec step.
    1325        5875 :   const SCEV *Step = Normalized->getStepRecurrence(SE);
    1326        5875 :   const SCEV *PostLoopScale = nullptr;
    1327       11750 :   if (!SE.dominates(Step, L->getHeader())) {
    1328           0 :     PostLoopScale = Step;
    1329           0 :     Step = SE.getConstant(Normalized->getType(), 1);
    1330           0 :     if (!Start->isZero()) {
    1331             :         // The normalization below assumes that Start is constant zero, so if
    1332             :         // it isn't re-associate Start to PostLoopOffset.
    1333             :         assert(!PostLoopOffset && "Start not-null but PostLoopOffset set?");
    1334           0 :         PostLoopOffset = Start;
    1335           0 :         Start = SE.getConstant(Normalized->getType(), 0);
    1336             :     }
    1337           0 :     Normalized =
    1338           0 :       cast<SCEVAddRecExpr>(SE.getAddRecExpr(
    1339             :                              Start, Step, Normalized->getLoop(),
    1340             :                              Normalized->getNoWrapFlags(SCEV::FlagNW)));
    1341             :   }
    1342             : 
    1343             :   // Expand the core addrec. If we need post-loop scaling, force it to
    1344             :   // expand to an integer type to avoid the need for additional casting.
    1345        5875 :   Type *ExpandTy = PostLoopScale ? IntTy : STy;
    1346             :   // We can't use a pointer type for the addrec if the pointer type is
    1347             :   // non-integral.
    1348             :   Type *AddRecPHIExpandTy =
    1349        5879 :       DL.isNonIntegralPointerType(STy) ? Normalized->getType() : ExpandTy;
    1350             : 
    1351             :   // In some cases, we decide to reuse an existing phi node but need to truncate
    1352             :   // it and/or invert the step.
    1353        5875 :   Type *TruncTy = nullptr;
    1354        5875 :   bool InvertStep = false;
    1355             :   PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy,
    1356        5875 :                                           IntTy, TruncTy, InvertStep);
    1357             : 
    1358             :   // Accommodate post-inc mode, if necessary.
    1359             :   Value *Result;
    1360        5875 :   if (!PostIncLoops.count(L))
    1361             :     Result = PN;
    1362             :   else {
    1363             :     // In PostInc mode, use the post-incremented value.
    1364        2284 :     BasicBlock *LatchBlock = L->getLoopLatch();
    1365             :     assert(LatchBlock && "PostInc mode requires a unique loop latch!");
    1366        2284 :     Result = PN->getIncomingValueForBlock(LatchBlock);
    1367             : 
    1368             :     // For an expansion to use the postinc form, the client must call
    1369             :     // expandCodeFor with an InsertPoint that is either outside the PostIncLoop
    1370             :     // or dominated by IVIncInsertPos.
    1371        6852 :     if (isa<Instruction>(Result) &&
    1372        6852 :         !SE.DT.dominates(cast<Instruction>(Result),
    1373        4568 :                          &*Builder.GetInsertPoint())) {
    1374             :       // The induction variable's postinc expansion does not dominate this use.
    1375             :       // IVUsers tries to prevent this case, so it is rare. However, it can
    1376             :       // happen when an IVUser outside the loop is not dominated by the latch
    1377             :       // block. Adjusting IVIncInsertPos before expansion begins cannot handle
    1378             :       // all cases. Consider a phi outide whose operand is replaced during
    1379             :       // expansion with the value of the postinc user. Without fundamentally
    1380             :       // changing the way postinc users are tracked, the only remedy is
    1381             :       // inserting an extra IV increment. StepV might fold into PostLoopOffset,
    1382             :       // but hopefully expandCodeFor handles that.
    1383             :       bool useSubtract =
    1384           1 :         !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
    1385             :       if (useSubtract)
    1386           0 :         Step = SE.getNegativeSCEV(Step);
    1387             :       Value *StepV;
    1388             :       {
    1389             :         // Expand the step somewhere that dominates the loop header.
    1390           2 :         SCEVInsertPointGuard Guard(Builder, this);
    1391           3 :         StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front());
    1392             :       }
    1393           1 :       Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
    1394             :     }
    1395             :   }
    1396             : 
    1397             :   // We have decided to reuse an induction variable of a dominating loop. Apply
    1398             :   // truncation and/or invertion of the step.
    1399        5875 :   if (TruncTy) {
    1400           3 :     Type *ResTy = Result->getType();
    1401             :     // Normalize the result type.
    1402           3 :     if (ResTy != SE.getEffectiveSCEVType(ResTy))
    1403           0 :       Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy));
    1404             :     // Truncate the result.
    1405           3 :     if (TruncTy != Result->getType()) {
    1406           9 :       Result = Builder.CreateTrunc(Result, TruncTy);
    1407           3 :       rememberInstruction(Result);
    1408             :     }
    1409             :     // Invert the result.
    1410           3 :     if (InvertStep) {
    1411           6 :       Result = Builder.CreateSub(expandCodeFor(Normalized->getStart(), TruncTy),
    1412             :                                  Result);
    1413           2 :       rememberInstruction(Result);
    1414             :     }
    1415             :   }
    1416             : 
    1417             :   // Re-apply any non-loop-dominating scale.
    1418        5875 :   if (PostLoopScale) {
    1419             :     assert(S->isAffine() && "Can't linearly scale non-affine recurrences.");
    1420           0 :     Result = InsertNoopCastOfTo(Result, IntTy);
    1421           0 :     Result = Builder.CreateMul(Result,
    1422             :                                expandCodeFor(PostLoopScale, IntTy));
    1423           0 :     rememberInstruction(Result);
    1424             :   }
    1425             : 
    1426             :   // Re-apply any non-loop-dominating offset.
    1427        5875 :   if (PostLoopOffset) {
    1428           1 :     if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
    1429           2 :       if (Result->getType()->isIntegerTy()) {
    1430           1 :         Value *Base = expandCodeFor(PostLoopOffset, ExpandTy);
    1431           1 :         const SCEV *const OffsetArray[1] = {SE.getUnknown(Result)};
    1432           1 :         Result = expandAddToGEP(OffsetArray, OffsetArray + 1, PTy, IntTy, Base);
    1433             :       } else {
    1434           0 :         const SCEV *const OffsetArray[1] = {PostLoopOffset};
    1435           0 :         Result =
    1436           0 :             expandAddToGEP(OffsetArray, OffsetArray + 1, PTy, IntTy, Result);
    1437             :       }
    1438             :     } else {
    1439           0 :       Result = InsertNoopCastOfTo(Result, IntTy);
    1440           0 :       Result = Builder.CreateAdd(Result,
    1441             :                                  expandCodeFor(PostLoopOffset, IntTy));
    1442           0 :       rememberInstruction(Result);
    1443             :     }
    1444             :   }
    1445             : 
    1446        5875 :   return Result;
    1447             : }
    1448             : 
    1449        6173 : Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
    1450        6173 :   if (!CanonicalMode) return expandAddRecExprLiterally(S);
    1451             : 
    1452         596 :   Type *Ty = SE.getEffectiveSCEVType(S->getType());
    1453         298 :   const Loop *L = S->getLoop();
    1454             : 
    1455             :   // First check for an existing canonical IV in a suitable type.
    1456         298 :   PHINode *CanonicalIV = nullptr;
    1457         298 :   if (PHINode *PN = L->getCanonicalInductionVariable())
    1458         168 :     if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))
    1459         156 :       CanonicalIV = PN;
    1460             : 
    1461             :   // Rewrite an AddRec in terms of the canonical induction variable, if
    1462             :   // its type is more narrow.
    1463         156 :   if (CanonicalIV &&
    1464         156 :       SE.getTypeSizeInBits(CanonicalIV->getType()) >
    1465         156 :       SE.getTypeSizeInBits(Ty)) {
    1466           9 :     SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
    1467           9 :     for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
    1468          12 :       NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
    1469           6 :     Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
    1470           3 :                                        S->getNoWrapFlags(SCEV::FlagNW)));
    1471             :     BasicBlock::iterator NewInsertPt =
    1472           6 :         findInsertPointAfter(cast<Instruction>(V), Builder.GetInsertBlock());
    1473           3 :     V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
    1474           3 :                       &*NewInsertPt);
    1475           3 :     return V;
    1476             :   }
    1477             : 
    1478             :   // {X,+,F} --> X + {0,+,F}
    1479         590 :   if (!S->getStart()->isZero()) {
    1480         588 :     SmallVector<const SCEV *, 4> NewOps(S->op_begin(), S->op_end());
    1481         294 :     NewOps[0] = SE.getConstant(Ty, 0);
    1482         294 :     const SCEV *Rest = SE.getAddRecExpr(NewOps, L,
    1483         147 :                                         S->getNoWrapFlags(SCEV::FlagNW));
    1484             : 
    1485             :     // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the
    1486             :     // comments on expandAddToGEP for details.
    1487         294 :     const SCEV *Base = S->getStart();
    1488         147 :     const SCEV *RestArray[1] = { Rest };
    1489             :     // Dig into the expression to find the pointer base for a GEP.
    1490         147 :     ExposePointerBase(Base, RestArray[0], SE);
    1491             :     // If we found a pointer, expand the AddRec with a GEP.
    1492         200 :     if (PointerType *PTy = dyn_cast<PointerType>(Base->getType())) {
    1493             :       // Make sure the Base isn't something exotic, such as a multiplied
    1494             :       // or divided pointer value. In those cases, the result type isn't
    1495             :       // actually a pointer type.
    1496         159 :       if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) {
    1497          53 :         Value *StartV = expand(Base);
    1498             :         assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!");
    1499          53 :         return expandAddToGEP(RestArray, RestArray+1, PTy, Ty, StartV);
    1500             :       }
    1501             :     }
    1502             : 
    1503             :     // Just do a normal add. Pre-expand the operands to suppress folding.
    1504             :     //
    1505             :     // The LHS and RHS values are factored out of the expand call to make the
    1506             :     // output independent of the argument evaluation order.
    1507         188 :     const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart()));
    1508          94 :     const SCEV *AddExprRHS = SE.getUnknown(expand(Rest));
    1509          94 :     return expand(SE.getAddExpr(AddExprLHS, AddExprRHS));
    1510             :   }
    1511             : 
    1512             :   // If we don't yet have a canonical IV, create one.
    1513         148 :   if (!CanonicalIV) {
    1514             :     // Create and insert the PHI node for the induction variable in the
    1515             :     // specified loop.
    1516         156 :     BasicBlock *Header = L->getHeader();
    1517         156 :     pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
    1518         234 :     CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar",
    1519          78 :                                   &Header->front());
    1520          78 :     rememberInstruction(CanonicalIV);
    1521             : 
    1522         156 :     SmallSet<BasicBlock *, 4> PredSeen;
    1523          78 :     Constant *One = ConstantInt::get(Ty, 1);
    1524         316 :     for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
    1525         160 :       BasicBlock *HP = *HPI;
    1526         160 :       if (!PredSeen.insert(HP).second) {
    1527             :         // There must be an incoming value for each predecessor, even the
    1528             :         // duplicates!
    1529           0 :         CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP);
    1530           0 :         continue;
    1531             :       }
    1532             : 
    1533         320 :       if (L->contains(HP)) {
    1534             :         // Insert a unit add instruction right before the terminator
    1535             :         // corresponding to the back-edge.
    1536         164 :         Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One,
    1537             :                                                      "indvar.next",
    1538         164 :                                                      HP->getTerminator());
    1539         328 :         Add->setDebugLoc(HP->getTerminator()->getDebugLoc());
    1540          82 :         rememberInstruction(Add);
    1541          82 :         CanonicalIV->addIncoming(Add, HP);
    1542             :       } else {
    1543          78 :         CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP);
    1544             :       }
    1545             :     }
    1546             :   }
    1547             : 
    1548             :   // {0,+,1} --> Insert a canonical induction variable into the loop!
    1549         296 :   if (S->isAffine() && S->getOperand(1)->isOne()) {
    1550             :     assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&
    1551             :            "IVs with types different from the canonical IV should "
    1552             :            "already have been handled!");
    1553             :     return CanonicalIV;
    1554             :   }
    1555             : 
    1556             :   // {0,+,F} --> {0,+,1} * F
    1557             : 
    1558             :   // If this is a simple linear addrec, emit it now as a special case.
    1559          68 :   if (S->isAffine())    // {0,+,F} --> i*F
    1560             :     return
    1561         204 :       expand(SE.getTruncateOrNoop(
    1562          68 :         SE.getMulExpr(SE.getUnknown(CanonicalIV),
    1563             :                       SE.getNoopOrAnyExtend(S->getOperand(1),
    1564             :                                             CanonicalIV->getType())),
    1565          68 :         Ty));
    1566             : 
    1567             :   // If this is a chain of recurrences, turn it into a closed form, using the
    1568             :   // folders, then expandCodeFor the closed form.  This allows the folders to
    1569             :   // simplify the expression without having to build a bunch of special code
    1570             :   // into this folder.
    1571           0 :   const SCEV *IH = SE.getUnknown(CanonicalIV);   // Get I as a "symbolic" SCEV.
    1572             : 
    1573             :   // Promote S up to the canonical IV type, if the cast is foldable.
    1574           0 :   const SCEV *NewS = S;
    1575           0 :   const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType());
    1576           0 :   if (isa<SCEVAddRecExpr>(Ext))
    1577           0 :     NewS = Ext;
    1578             : 
    1579           0 :   const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
    1580             :   //cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
    1581             : 
    1582             :   // Truncate the result down to the original type, if needed.
    1583           0 :   const SCEV *T = SE.getTruncateOrNoop(V, Ty);
    1584           0 :   return expand(T);
    1585             : }
    1586             : 
    1587         212 : Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {
    1588         212 :   Type *Ty = SE.getEffectiveSCEVType(S->getType());
    1589         212 :   Value *V = expandCodeFor(S->getOperand(),
    1590         424 :                            SE.getEffectiveSCEVType(S->getOperand()->getType()));
    1591         636 :   Value *I = Builder.CreateTrunc(V, Ty);
    1592         212 :   rememberInstruction(I);
    1593         212 :   return I;
    1594             : }
    1595             : 
    1596         368 : Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {
    1597         368 :   Type *Ty = SE.getEffectiveSCEVType(S->getType());
    1598         368 :   Value *V = expandCodeFor(S->getOperand(),
    1599         736 :                            SE.getEffectiveSCEVType(S->getOperand()->getType()));
    1600        1104 :   Value *I = Builder.CreateZExt(V, Ty);
    1601         368 :   rememberInstruction(I);
    1602         368 :   return I;
    1603             : }
    1604             : 
    1605         140 : Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
    1606         140 :   Type *Ty = SE.getEffectiveSCEVType(S->getType());
    1607         140 :   Value *V = expandCodeFor(S->getOperand(),
    1608         280 :                            SE.getEffectiveSCEVType(S->getOperand()->getType()));
    1609         420 :   Value *I = Builder.CreateSExt(V, Ty);
    1610         140 :   rememberInstruction(I);
    1611         140 :   return I;
    1612             : }
    1613             : 
    1614         156 : Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
    1615         312 :   Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
    1616         156 :   Type *Ty = LHS->getType();
    1617         314 :   for (int i = S->getNumOperands()-2; i >= 0; --i) {
    1618             :     // In the case of mixed integer and pointer types, do the
    1619             :     // rest of the comparisons as integer.
    1620         316 :     if (S->getOperand(i)->getType() != Ty) {
    1621           0 :       Ty = SE.getEffectiveSCEVType(Ty);
    1622           0 :       LHS = InsertNoopCastOfTo(LHS, Ty);
    1623             :     }
    1624         316 :     Value *RHS = expandCodeFor(S->getOperand(i), Ty);
    1625         474 :     Value *ICmp = Builder.CreateICmpSGT(LHS, RHS);
    1626         158 :     rememberInstruction(ICmp);
    1627         316 :     Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax");
    1628         158 :     rememberInstruction(Sel);
    1629         158 :     LHS = Sel;
    1630             :   }
    1631             :   // In the case of mixed integer and pointer types, cast the
    1632             :   // final result back to the pointer type.
    1633         312 :   if (LHS->getType() != S->getType())
    1634           0 :     LHS = InsertNoopCastOfTo(LHS, S->getType());
    1635         156 :   return LHS;
    1636             : }
    1637             : 
    1638          44 : Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
    1639          88 :   Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
    1640          44 :   Type *Ty = LHS->getType();
    1641          88 :   for (int i = S->getNumOperands()-2; i >= 0; --i) {
    1642             :     // In the case of mixed integer and pointer types, do the
    1643             :     // rest of the comparisons as integer.
    1644          88 :     if (S->getOperand(i)->getType() != Ty) {
    1645           0 :       Ty = SE.getEffectiveSCEVType(Ty);
    1646           0 :       LHS = InsertNoopCastOfTo(LHS, Ty);
    1647             :     }
    1648          88 :     Value *RHS = expandCodeFor(S->getOperand(i), Ty);
    1649         132 :     Value *ICmp = Builder.CreateICmpUGT(LHS, RHS);
    1650          44 :     rememberInstruction(ICmp);
    1651          88 :     Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax");
    1652          44 :     rememberInstruction(Sel);
    1653          44 :     LHS = Sel;
    1654             :   }
    1655             :   // In the case of mixed integer and pointer types, cast the
    1656             :   // final result back to the pointer type.
    1657          88 :   if (LHS->getType() != S->getType())
    1658           0 :     LHS = InsertNoopCastOfTo(LHS, S->getType());
    1659          44 :   return LHS;
    1660             : }
    1661             : 
    1662       14225 : Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty,
    1663             :                                    Instruction *IP) {
    1664       14225 :   setInsertPoint(IP);
    1665       14225 :   return expandCodeFor(SH, Ty);
    1666             : }
    1667             : 
    1668       60168 : Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) {
    1669             :   // Expand the code for this SCEV.
    1670       60168 :   Value *V = expand(SH);
    1671       60168 :   if (Ty) {
    1672             :     assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&
    1673             :            "non-trivial casts should be done with the SCEVs directly!");
    1674       48266 :     V = InsertNoopCastOfTo(V, Ty);
    1675             :   }
    1676       60168 :   return V;
    1677             : }
    1678             : 
    1679             : ScalarEvolution::ValueOffsetPair
    1680       58120 : SCEVExpander::FindValueInExprValueMap(const SCEV *S,
    1681             :                                       const Instruction *InsertPt) {
    1682       58120 :   SetVector<ScalarEvolution::ValueOffsetPair> *Set = SE.getSCEVValues(S);
    1683             :   // If the expansion is not in CanonicalMode, and the SCEV contains any
    1684             :   // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.
    1685       58120 :   if (CanonicalMode || !SE.containsAddRecurrence(S)) {
    1686             :     // If S is scConstant, it may be worse to reuse an existing Value.
    1687       52126 :     if (S->getSCEVType() != scConstant && Set) {
    1688             :       // Choose a Value from the set which dominates the insertPt.
    1689             :       // insertPt should be inside the Value's parent loop so as not to break
    1690             :       // the LCSSA form.
    1691       38762 :       for (auto const &VOPair : *Set) {
    1692        9591 :         Value *V = VOPair.first;
    1693        9591 :         ConstantInt *Offset = VOPair.second;
    1694        9591 :         Instruction *EntInst = nullptr;
    1695       28614 :         if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) &&
    1696        8152 :             S->getType() == V->getType() &&
    1697        6872 :             EntInst->getFunction() == InsertPt->getFunction() &&
    1698       14010 :             SE.DT.dominates(EntInst, InsertPt) &&
    1699        7379 :             (SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
    1700        2949 :              SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))
    1701        3153 :           return {V, Offset};
    1702             :       }
    1703             :     }
    1704             :   }
    1705      109934 :   return {nullptr, nullptr};
    1706             : }
    1707             : 
    1708             : // The expansion of SCEV will either reuse a previous Value in ExprValueMap,
    1709             : // or expand the SCEV literally. Specifically, if the expansion is in LSRMode,
    1710             : // and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded
    1711             : // literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,
    1712             : // the expansion will try to reuse Value from ExprValueMap, and only when it
    1713             : // fails, expand the SCEV literally.
    1714       76597 : Value *SCEVExpander::expand(const SCEV *S) {
    1715             :   // Compute an insertion point for this SCEV object. Hoist the instructions
    1716             :   // as far out in the loop nest as possible.
    1717      153194 :   Instruction *InsertPt = &*Builder.GetInsertPoint();
    1718      175119 :   for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
    1719       21925 :        L = L->getParentLoop())
    1720       98522 :     if (SE.isLoopInvariant(S, L)) {
    1721       48502 :       if (!L) break;
    1722       21925 :       if (BasicBlock *Preheader = L->getLoopPreheader())
    1723       21642 :         InsertPt = Preheader->getTerminator();
    1724             :       else {
    1725             :         // LSR sets the insertion point for AddRec start/step values to the
    1726             :         // block start to simplify value reuse, even though it's an invalid
    1727             :         // position. SCEVExpander must correct for this in all cases.
    1728         849 :         InsertPt = &*L->getHeader()->getFirstInsertionPt();
    1729             :       }
    1730             :     } else {
    1731             :       // If the SCEV is computable at this level, insert it into the header
    1732             :       // after the PHIs (and after any other instructions that we've inserted
    1733             :       // there) so that it is guaranteed to dominate any user inside the loop.
    1734       50020 :       if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
    1735       20973 :         InsertPt = &*L->getHeader()->getFirstInsertionPt();
    1736      125782 :       while (InsertPt->getIterator() != Builder.GetInsertPoint() &&
    1737       14562 :              (isInsertedInstruction(InsertPt) ||
    1738       11892 :               isa<DbgInfoIntrinsic>(InsertPt))) {
    1739        5590 :         InsertPt = &*std::next(InsertPt->getIterator());
    1740             :       }
    1741             :       break;
    1742       21925 :     }
    1743             : 
    1744             :   // Check to see if we already expanded this here.
    1745      153194 :   auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
    1746      229791 :   if (I != InsertedExpressions.end())
    1747       41638 :     return I->second;
    1748             : 
    1749      111556 :   SCEVInsertPointGuard Guard(Builder, this);
    1750       55778 :   Builder.SetInsertPoint(InsertPt);
    1751             : 
    1752             :   // Expand the expression into instructions.
    1753       55778 :   ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt);
    1754       55778 :   Value *V = VO.first;
    1755             : 
    1756       55778 :   if (!V)
    1757       52949 :     V = visit(S);
    1758        2829 :   else if (VO.second) {
    1759          10 :     if (PointerType *Vty = dyn_cast<PointerType>(V->getType())) {
    1760           4 :       Type *Ety = Vty->getPointerElementType();
    1761           4 :       int64_t Offset = VO.second->getSExtValue();
    1762           2 :       int64_t ESize = SE.getTypeSizeInBits(Ety);
    1763           2 :       if ((Offset * 8) % ESize == 0) {
    1764             :         ConstantInt *Idx =
    1765           2 :             ConstantInt::getSigned(VO.second->getType(), -(Offset * 8) / ESize);
    1766           2 :         V = Builder.CreateGEP(Ety, V, Idx, "scevgep");
    1767             :       } else {
    1768             :         ConstantInt *Idx =
    1769           2 :             ConstantInt::getSigned(VO.second->getType(), -Offset);
    1770           1 :         unsigned AS = Vty->getAddressSpace();
    1771           4 :         V = Builder.CreateBitCast(V, Type::getInt8PtrTy(SE.getContext(), AS));
    1772           3 :         V = Builder.CreateGEP(Type::getInt8Ty(SE.getContext()), V, Idx,
    1773             :                               "uglygep");
    1774           3 :         V = Builder.CreateBitCast(V, Vty);
    1775             :       }
    1776             :     } else {
    1777          12 :       V = Builder.CreateSub(V, VO.second);
    1778             :     }
    1779             :   }
    1780             :   // Remember the expanded value for this SCEV at this location.
    1781             :   //
    1782             :   // This is independent of PostIncLoops. The mapped value simply materializes
    1783             :   // the expression at this insertion point. If the mapped value happened to be
    1784             :   // a postinc expansion, it could be reused by a non-postinc user, but only if
    1785             :   // its insertion point was already at the head of the loop.
    1786      223112 :   InsertedExpressions[std::make_pair(S, InsertPt)] = V;
    1787             :   return V;
    1788             : }
    1789             : 
    1790       26171 : void SCEVExpander::rememberInstruction(Value *I) {
    1791       52342 :   if (!PostIncLoops.empty())
    1792        6438 :     InsertedPostIncValues.insert(I);
    1793             :   else
    1794       72075 :     InsertedValues.insert(I);
    1795       26171 : }
    1796             : 
    1797             : /// getOrInsertCanonicalInductionVariable - This method returns the
    1798             : /// canonical induction variable of the specified type for the specified
    1799             : /// loop (inserting one if there is none).  A canonical induction variable
    1800             : /// starts at zero and steps by one on each iteration.
    1801             : PHINode *
    1802           0 : SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L,
    1803             :                                                     Type *Ty) {
    1804             :   assert(Ty->isIntegerTy() && "Can only insert integer induction variables!");
    1805             : 
    1806             :   // Build a SCEV for {0,+,1}<L>.
    1807             :   // Conservatively use FlagAnyWrap for now.
    1808           0 :   const SCEV *H = SE.getAddRecExpr(SE.getConstant(Ty, 0),
    1809           0 :                                    SE.getConstant(Ty, 1), L, SCEV::FlagAnyWrap);
    1810             : 
    1811             :   // Emit code for it.
    1812           0 :   SCEVInsertPointGuard Guard(Builder, this);
    1813             :   PHINode *V =
    1814           0 :       cast<PHINode>(expandCodeFor(H, nullptr, &L->getHeader()->front()));
    1815             : 
    1816           0 :   return V;
    1817             : }
    1818             : 
    1819             : /// replaceCongruentIVs - Check for congruent phis in this loop header and
    1820             : /// replace them with their most canonical representative. Return the number of
    1821             : /// phis eliminated.
    1822             : ///
    1823             : /// This does not depend on any SCEVExpander state but should be used in
    1824             : /// the same context that SCEVExpander is used.
    1825             : unsigned
    1826        9543 : SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
    1827             :                                   SmallVectorImpl<WeakTrackingVH> &DeadInsts,
    1828             :                                   const TargetTransformInfo *TTI) {
    1829             :   // Find integer phis in order of increasing width.
    1830       19086 :   SmallVector<PHINode*, 8> Phis;
    1831       61222 :   for (auto &I : *L->getHeader()) {
    1832       23050 :     if (auto *PN = dyn_cast<PHINode>(&I))
    1833       13507 :       Phis.push_back(PN);
    1834             :     else
    1835             :       break;
    1836             :   }
    1837             : 
    1838        9543 :   if (TTI)
    1839       22432 :     std::sort(Phis.begin(), Phis.end(), [](Value *LHS, Value *RHS) {
    1840             :       // Put pointers at the back and make sure pointer < pointer = false.
    1841       24695 :       if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
    1842       18740 :         return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();
    1843        2261 :       return RHS->getType()->getPrimitiveSizeInBits() <
    1844        2261 :              LHS->getType()->getPrimitiveSizeInBits();
    1845             :     });
    1846             : 
    1847        9543 :   unsigned NumElim = 0;
    1848       19086 :   DenseMap<const SCEV *, PHINode *> ExprToIVMap;
    1849             :   // Process phis from wide to narrow. Map wide phis to their truncation
    1850             :   // so narrow phis can reuse them.
    1851       42136 :   for (PHINode *Phi : Phis) {
    1852       13507 :     auto SimplifyPHINode = [&](PHINode *PN) -> Value * {
    1853       38626 :       if (Value *V = SimplifyInstruction(PN, {DL, &SE.TLI, &SE.DT, &SE.AC}))
    1854             :         return V;
    1855       13501 :       if (!SE.isSCEVable(PN->getType()))
    1856             :         return nullptr;
    1857       11616 :       auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));
    1858             :       if (!Const)
    1859             :         return nullptr;
    1860           4 :       return Const->getValue();
    1861       13507 :     };
    1862             : 
    1863             :     // Fold constant phis. They may be congruent to other constant phis and
    1864             :     // would confuse the logic below that expects proper IVs.
    1865       13516 :     if (Value *V = SimplifyPHINode(Phi)) {
    1866          10 :       if (V->getType() != Phi->getType())
    1867       13449 :         continue;
    1868           9 :       Phi->replaceAllUsesWith(V);
    1869           9 :       DeadInsts.emplace_back(Phi);
    1870           9 :       ++NumElim;
    1871             :       DEBUG_WITH_TYPE(DebugType, dbgs()
    1872             :                       << "INDVARS: Eliminated constant iv: " << *Phi << '\n');
    1873           9 :       continue;
    1874             :     }
    1875             : 
    1876       13497 :     if (!SE.isSCEVable(Phi->getType()))
    1877        1889 :       continue;
    1878             : 
    1879       23216 :     PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
    1880       11608 :     if (!OrigPhiRef) {
    1881       11547 :       OrigPhiRef = Phi;
    1882       27953 :       if (Phi->getType()->isIntegerTy() && TTI &&
    1883        9718 :           TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
    1884             :         // This phi can be freely truncated to the narrowest phi type. Map the
    1885             :         // truncated expression to it so it will be reused for narrow types.
    1886             :         const SCEV *TruncExpr =
    1887         598 :           SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType());
    1888         299 :         ExprToIVMap[TruncExpr] = Phi;
    1889             :       }
    1890       11547 :       continue;
    1891             :     }
    1892             : 
    1893             :     // Replacing a pointer phi with an integer phi or vice-versa doesn't make
    1894             :     // sense.
    1895         183 :     if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy())
    1896           2 :       continue;
    1897             : 
    1898          59 :     if (BasicBlock *LatchBlock = L->getLoopLatch()) {
    1899         118 :       Instruction *OrigInc = dyn_cast<Instruction>(
    1900          59 :           OrigPhiRef->getIncomingValueForBlock(LatchBlock));
    1901             :       Instruction *IsomorphicInc =
    1902         118 :           dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
    1903             : 
    1904          59 :       if (OrigInc && IsomorphicInc) {
    1905             :         // If this phi has the same width but is more canonical, replace the
    1906             :         // original with it. As part of the "more canonical" determination,
    1907             :         // respect a prior decision to use an IV chain.
    1908          57 :         if (OrigPhiRef->getType() == Phi->getType() &&
    1909         221 :             !(ChainedPhis.count(Phi) ||
    1910          98 :               isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) &&
    1911          71 :             (ChainedPhis.count(Phi) ||
    1912           4 :              isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
    1913           2 :           std::swap(OrigPhiRef, Phi);
    1914             :           std::swap(OrigInc, IsomorphicInc);
    1915             :         }
    1916             :         // Replacing the congruent phi is sufficient because acyclic
    1917             :         // redundancy elimination, CSE/GVN, should handle the
    1918             :         // rest. However, once SCEV proves that a phi is congruent,
    1919             :         // it's often the head of an IV user cycle that is isomorphic
    1920             :         // with the original phi. It's worth eagerly cleaning up the
    1921             :         // common case of a single IV increment so that DeleteDeadPHIs
    1922             :         // can remove cycles that had postinc uses.
    1923             :         const SCEV *TruncExpr =
    1924          57 :             SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->getType());
    1925         112 :         if (OrigInc != IsomorphicInc &&
    1926         110 :             TruncExpr == SE.getSCEV(IsomorphicInc) &&
    1927         166 :             SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc) &&
    1928          54 :             hoistIVInc(OrigInc, IsomorphicInc)) {
    1929             :           DEBUG_WITH_TYPE(DebugType,
    1930             :                           dbgs() << "INDVARS: Eliminated congruent iv.inc: "
    1931             :                                  << *IsomorphicInc << '\n');
    1932          46 :           Value *NewInc = OrigInc;
    1933          46 :           if (OrigInc->getType() != IsomorphicInc->getType()) {
    1934          13 :             Instruction *IP = nullptr;
    1935          14 :             if (PHINode *PN = dyn_cast<PHINode>(OrigInc))
    1936           2 :               IP = &*PN->getParent()->getFirstInsertionPt();
    1937             :             else
    1938          12 :               IP = OrigInc->getNextNode();
    1939             : 
    1940          26 :             IRBuilder<> Builder(IP);
    1941          52 :             Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc());
    1942          26 :             NewInc = Builder.CreateTruncOrBitCast(
    1943             :                 OrigInc, IsomorphicInc->getType(), IVName);
    1944             :           }
    1945          46 :           IsomorphicInc->replaceAllUsesWith(NewInc);
    1946          46 :           DeadInsts.emplace_back(IsomorphicInc);
    1947             :         }
    1948             :       }
    1949             :     }
    1950             :     DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Eliminated congruent iv: "
    1951             :                                       << *Phi << '\n');
    1952          59 :     ++NumElim;
    1953          59 :     Value *NewIV = OrigPhiRef;
    1954          59 :     if (OrigPhiRef->getType() != Phi->getType()) {
    1955          80 :       IRBuilder<> Builder(&*L->getHeader()->getFirstInsertionPt());
    1956          64 :       Builder.SetCurrentDebugLocation(Phi->getDebugLoc());
    1957          32 :       NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);
    1958             :     }
    1959          59 :     Phi->replaceAllUsesWith(NewIV);
    1960          59 :     DeadInsts.emplace_back(Phi);
    1961             :   }
    1962       19086 :   return NumElim;
    1963             : }
    1964             : 
    1965         514 : Value *SCEVExpander::getExactExistingExpansion(const SCEV *S,
    1966             :                                                const Instruction *At, Loop *L) {
    1967             :   Optional<ScalarEvolution::ValueOffsetPair> VO =
    1968        1028 :       getRelatedExistingExpansion(S, At, L);
    1969         522 :   if (VO && VO.getValue().second == nullptr)
    1970           7 :     return VO.getValue().first;
    1971             :   return nullptr;
    1972             : }
    1973             : 
    1974             : Optional<ScalarEvolution::ValueOffsetPair>
    1975        2372 : SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At,
    1976             :                                           Loop *L) {
    1977             :   using namespace llvm::PatternMatch;
    1978             : 
    1979        4744 :   SmallVector<BasicBlock *, 4> ExitingBlocks;
    1980        2372 :   L->getExitingBlocks(ExitingBlocks);
    1981             : 
    1982             :   // Look for suitable value in simple conditions at the loop exits.
    1983        9508 :   for (BasicBlock *BB : ExitingBlocks) {
    1984             :     ICmpInst::Predicate Pred;
    1985             :     Instruction *LHS, *RHS;
    1986             :     BasicBlock *TrueBB, *FalseBB;
    1987             : 
    1988        7266 :     if (!match(BB->getTerminator(),
    1989       12110 :                m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
    1990             :                     TrueBB, FalseBB)))
    1991        2099 :       continue;
    1992             : 
    1993         323 :     if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
    1994           6 :       return ScalarEvolution::ValueOffsetPair(LHS, nullptr);
    1995             : 
    1996         321 :     if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
    1997          84 :       return ScalarEvolution::ValueOffsetPair(RHS, nullptr);
    1998             :   }
    1999             : 
    2000             :   // Use expand's logic which is used for reusing a previous Value in
    2001             :   // ExprValueMap.
    2002        2342 :   ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At);
    2003        2342 :   if (VO.first)
    2004             :     return VO;
    2005             : 
    2006             :   // There is potential to make this significantly smarter, but this simple
    2007             :   // heuristic already gets some interesting cases.
    2008             : 
    2009             :   // Can not find suitable value.
    2010             :   return None;
    2011             : }
    2012             : 
    2013        4101 : bool SCEVExpander::isHighCostExpansionHelper(
    2014             :     const SCEV *S, Loop *L, const Instruction *At,
    2015             :     SmallPtrSetImpl<const SCEV *> &Processed) {
    2016             : 
    2017             :   // If we can find an existing value for this scev available at the point "At"
    2018             :   // then consider the expression cheap.
    2019        8202 :   if (At && getRelatedExistingExpansion(S, At, L))
    2020             :     return false;
    2021             : 
    2022             :   // Zero/One operand expressions
    2023        7512 :   switch (S->getSCEVType()) {
    2024             :   case scUnknown:
    2025             :   case scConstant:
    2026             :     return false;
    2027          12 :   case scTruncate:
    2028          24 :     return isHighCostExpansionHelper(cast<SCEVTruncateExpr>(S)->getOperand(),
    2029          12 :                                      L, At, Processed);
    2030          12 :   case scZeroExtend:
    2031          24 :     return isHighCostExpansionHelper(cast<SCEVZeroExtendExpr>(S)->getOperand(),
    2032          12 :                                      L, At, Processed);
    2033          11 :   case scSignExtend:
    2034          22 :     return isHighCostExpansionHelper(cast<SCEVSignExtendExpr>(S)->getOperand(),
    2035          11 :                                      L, At, Processed);
    2036             :   }
    2037             : 
    2038        1461 :   if (!Processed.insert(S).second)
    2039             :     return false;
    2040             : 
    2041        1695 :   if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
    2042             :     // If the divisor is a power of two and the SCEV type fits in a native
    2043             :     // integer, consider the division cheap irrespective of whether it occurs in
    2044             :     // the user code since it can be lowered into a right shift.
    2045         465 :     if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS()))
    2046         231 :       if (SC->getAPInt().isPowerOf2()) {
    2047             :         const DataLayout &DL =
    2048         232 :             L->getHeader()->getParent()->getParent()->getDataLayout();
    2049         348 :         unsigned Width = cast<IntegerType>(UDivExpr->getType())->getBitWidth();
    2050         232 :         return DL.isIllegalInteger(Width);
    2051             :       }
    2052             : 
    2053             :     // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
    2054             :     // HowManyLessThans produced to compute a precise expression, rather than a
    2055             :     // UDiv from the user's code. If we can't find a UDiv in the code with some
    2056             :     // simple searching, assume the former consider UDivExpr expensive to
    2057             :     // compute.
    2058         118 :     BasicBlock *ExitingBB = L->getExitingBlock();
    2059         118 :     if (!ExitingBB)
    2060             :       return true;
    2061             : 
    2062             :     // At the beginning of this function we already tried to find existing value
    2063             :     // for plain 'S'. Now try to lookup 'S + 1' since it is common pattern
    2064             :     // involving division. This is just a simple search heuristic.
    2065         118 :     if (!At)
    2066             :       At = &ExitingBB->back();
    2067         354 :     if (!getRelatedExistingExpansion(
    2068         236 :             SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L))
    2069             :       return true;
    2070             :   }
    2071             : 
    2072             :   // HowManyLessThans uses a Max expression whenever the loop is not guarded by
    2073             :   // the exit condition.
    2074        3584 :   if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S))
    2075             :     return true;
    2076             : 
    2077             :   // Recurse past nary expressions, which commonly occur in the
    2078             :   // BackedgeTakenCount. They may already exist in program code, and if not,
    2079             :   // they are not too expensive rematerialize.
    2080        2177 :   if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(S)) {
    2081        2990 :     for (auto *Op : NAry->operands())
    2082        2226 :       if (isHighCostExpansionHelper(Op, L, At, Processed))
    2083             :         return true;
    2084             :   }
    2085             : 
    2086             :   // If we haven't recognized an expensive SCEV pattern, assume it's an
    2087             :   // expression produced by program code.
    2088             :   return false;
    2089             : }
    2090             : 
    2091         775 : Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred,
    2092             :                                             Instruction *IP) {
    2093             :   assert(IP);
    2094         775 :   switch (Pred->getKind()) {
    2095         714 :   case SCEVPredicate::P_Union:
    2096         714 :     return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);
    2097          11 :   case SCEVPredicate::P_Equal:
    2098          11 :     return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP);
    2099          50 :   case SCEVPredicate::P_Wrap: {
    2100          50 :     auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
    2101          50 :     return expandWrapPredicate(AddRecPred, IP);
    2102             :   }
    2103             :   }
    2104           0 :   llvm_unreachable("Unknown SCEV predicate type");
    2105             : }
    2106             : 
    2107          11 : Value *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred,
    2108             :                                           Instruction *IP) {
    2109          11 :   Value *Expr0 = expandCodeFor(Pred->getLHS(), Pred->getLHS()->getType(), IP);
    2110          11 :   Value *Expr1 = expandCodeFor(Pred->getRHS(), Pred->getRHS()->getType(), IP);
    2111             : 
    2112          11 :   Builder.SetInsertPoint(IP);
    2113          33 :   auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
    2114          11 :   return I;
    2115             : }
    2116             : 
    2117          50 : Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
    2118             :                                            Instruction *Loc, bool Signed) {
    2119             :   assert(AR->isAffine() && "Cannot generate RT check for "
    2120             :                            "non-affine expression");
    2121             : 
    2122         100 :   SCEVUnionPredicate Pred;
    2123             :   const SCEV *ExitCount =
    2124          50 :       SE.getPredicatedBackedgeTakenCount(AR->getLoop(), Pred);
    2125             : 
    2126             :   assert(ExitCount != SE.getCouldNotCompute() && "Invalid loop count");
    2127             : 
    2128          50 :   const SCEV *Step = AR->getStepRecurrence(SE);
    2129         100 :   const SCEV *Start = AR->getStart();
    2130             : 
    2131          50 :   unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType());
    2132         100 :   unsigned DstBits = SE.getTypeSizeInBits(AR->getType());
    2133             : 
    2134             :   // The expression {Start,+,Step} has nusw/nssw if
    2135             :   //   Step < 0, Start - |Step| * Backedge <= Start
    2136             :   //   Step >= 0, Start + |Step| * Backedge > Start
    2137             :   // and |Step| * Backedge doesn't unsigned overflow.
    2138             : 
    2139          50 :   IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits);
    2140          50 :   Builder.SetInsertPoint(Loc);
    2141          50 :   Value *TripCountVal = expandCodeFor(ExitCount, CountTy, Loc);
    2142             : 
    2143             :   IntegerType *Ty =
    2144         100 :       IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(AR->getType()));
    2145             : 
    2146          50 :   Value *StepValue = expandCodeFor(Step, Ty, Loc);
    2147          50 :   Value *NegStepValue = expandCodeFor(SE.getNegativeSCEV(Step), Ty, Loc);
    2148          50 :   Value *StartValue = expandCodeFor(Start, Ty, Loc);
    2149             : 
    2150             :   ConstantInt *Zero =
    2151         100 :       ConstantInt::get(Loc->getContext(), APInt::getNullValue(DstBits));
    2152             : 
    2153          50 :   Builder.SetInsertPoint(Loc);
    2154             :   // Compute |Step|
    2155         100 :   Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero);
    2156         100 :   Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue);
    2157             : 
    2158             :   // Get the backedge taken count and truncate or extended to the AR type.
    2159         100 :   Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty);
    2160         200 :   auto *MulF = Intrinsic::getDeclaration(Loc->getModule(),
    2161          50 :                                          Intrinsic::umul_with_overflow, Ty);
    2162             : 
    2163             :   // Compute |Step| * Backedge
    2164         200 :   CallInst *Mul = Builder.CreateCall(MulF, {AbsStep, TruncTripCount}, "mul");
    2165         150 :   Value *MulV = Builder.CreateExtractValue(Mul, 0, "mul.result");
    2166         150 :   Value *OfMul = Builder.CreateExtractValue(Mul, 1, "mul.overflow");
    2167             : 
    2168             :   // Compute:
    2169             :   //   Start + |Step| * Backedge < Start
    2170             :   //   Start - |Step| * Backedge > Start
    2171         100 :   Value *Add = Builder.CreateAdd(StartValue, MulV);
    2172         100 :   Value *Sub = Builder.CreateSub(StartValue, MulV);
    2173             : 
    2174         150 :   Value *EndCompareGT = Builder.CreateICmp(
    2175          50 :       Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue);
    2176             : 
    2177         150 :   Value *EndCompareLT = Builder.CreateICmp(
    2178          50 :       Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, Add, StartValue);
    2179             : 
    2180             :   // Select the answer based on the sign of Step.
    2181             :   Value *EndCheck =
    2182         100 :       Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT);
    2183             : 
    2184             :   // If the backedge taken count type is larger than the AR type,
    2185             :   // check that we don't drop any bits by truncating it. If we are
    2186             :   // droping bits, then we have overflow (unless the step is zero).
    2187          50 :   if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) {
    2188         117 :     auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits);
    2189             :     auto *BackedgeCheck =
    2190         117 :         Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal,
    2191          39 :                            ConstantInt::get(Loc->getContext(), MaxVal));
    2192         117 :     BackedgeCheck = Builder.CreateAnd(
    2193             :         BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero));
    2194             : 
    2195          78 :     EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck);
    2196             :   }
    2197             : 
    2198         100 :   EndCheck = Builder.CreateOr(EndCheck, OfMul);
    2199          50 :   return EndCheck;
    2200             : }
    2201             : 
    2202          50 : Value *SCEVExpander::expandWrapPredicate(const SCEVWrapPredicate *Pred,
    2203             :                                          Instruction *IP) {
    2204         100 :   const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr());
    2205          50 :   Value *NSSWCheck = nullptr, *NUSWCheck = nullptr;
    2206             : 
    2207             :   // Add a check for NUSW
    2208          50 :   if (Pred->getFlags() & SCEVWrapPredicate::IncrementNUSW)
    2209          24 :     NUSWCheck = generateOverflowCheck(A, IP, false);
    2210             : 
    2211             :   // Add a check for NSSW
    2212          50 :   if (Pred->getFlags() & SCEVWrapPredicate::IncrementNSSW)
    2213          26 :     NSSWCheck = generateOverflowCheck(A, IP, true);
    2214             : 
    2215          50 :   if (NUSWCheck && NSSWCheck)
    2216           0 :     return Builder.CreateOr(NUSWCheck, NSSWCheck);
    2217             : 
    2218          50 :   if (NUSWCheck)
    2219             :     return NUSWCheck;
    2220             : 
    2221          26 :   if (NSSWCheck)
    2222             :     return NSSWCheck;
    2223             : 
    2224           0 :   return ConstantInt::getFalse(IP->getContext());
    2225             : }
    2226             : 
    2227         714 : Value *SCEVExpander::expandUnionPredicate(const SCEVUnionPredicate *Union,
    2228             :                                           Instruction *IP) {
    2229         714 :   auto *BoolType = IntegerType::get(IP->getContext(), 1);
    2230         714 :   Value *Check = ConstantInt::getNullValue(BoolType);
    2231             : 
    2232             :   // Loop over all checks in this set.
    2233        2203 :   for (auto Pred : Union->getPredicates()) {
    2234          61 :     auto *NextCheck = expandCodeForPredicate(Pred, IP);
    2235          61 :     Builder.SetInsertPoint(IP);
    2236         122 :     Check = Builder.CreateOr(Check, NextCheck);
    2237             :   }
    2238             : 
    2239         714 :   return Check;
    2240             : }
    2241             : 
    2242             : namespace {
    2243             : // Search for a SCEV subexpression that is not safe to expand.  Any expression
    2244             : // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
    2245             : // UDiv expressions. We don't know if the UDiv is derived from an IR divide
    2246             : // instruction, but the important thing is that we prove the denominator is
    2247             : // nonzero before expansion.
    2248             : //
    2249             : // IVUsers already checks that IV-derived expressions are safe. So this check is
    2250             : // only needed when the expression includes some subexpression that is not IV
    2251             : // derived.
    2252             : //
    2253             : // Currently, we only allow division by a nonzero constant here. If this is
    2254             : // inadequate, we could easily allow division by SCEVUnknown by using
    2255             : // ValueTracking to check isKnownNonZero().
    2256             : //
    2257             : // We cannot generally expand recurrences unless the step dominates the loop
    2258             : // header. The expander handles the special case of affine recurrences by
    2259             : // scaling the recurrence outside the loop, but this technique isn't generally
    2260             : // applicable. Expanding a nested recurrence outside a loop requires computing
    2261             : // binomial coefficients. This could be done, but the recurrence has to be in a
    2262             : // perfectly reduced form, which can't be guaranteed.
    2263             : struct SCEVFindUnsafe {
    2264             :   ScalarEvolution &SE;
    2265             :   bool IsUnsafe;
    2266             : 
    2267        9239 :   SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {}
    2268             : 
    2269       31408 :   bool follow(const SCEV *S) {
    2270         229 :     if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
    2271         442 :       const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS());
    2272         426 :       if (!SC || SC->getValue()->isZero()) {
    2273          16 :         IsUnsafe = true;
    2274          16 :         return false;
    2275             :       }
    2276             :     }
    2277        7127 :     if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
    2278        7127 :       const SCEV *Step = AR->getStepRecurrence(SE);
    2279        7132 :       if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
    2280           0 :         IsUnsafe = true;
    2281           0 :         return false;
    2282             :       }
    2283             :     }
    2284             :     return true;
    2285             :   }
    2286             :   bool isDone() const { return IsUnsafe; }
    2287             : };
    2288             : }
    2289             : 
    2290             : namespace llvm {
    2291        9239 : bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) {
    2292        9239 :   SCEVFindUnsafe Search(SE);
    2293        9239 :   visitAll(S, Search);
    2294        9239 :   return !Search.IsUnsafe;
    2295             : }
    2296             : }

Generated by: LCOV version 1.13