LLVM  mainline
ScalarEvolutionExpander.cpp
Go to the documentation of this file.
00001 //===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis --*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file contains the implementation of the scalar evolution expander,
00011 // which is used to generate the code corresponding to a given scalar evolution
00012 // expression.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Analysis/ScalarEvolutionExpander.h"
00017 #include "llvm/ADT/STLExtras.h"
00018 #include "llvm/ADT/SmallSet.h"
00019 #include "llvm/Analysis/InstructionSimplify.h"
00020 #include "llvm/Analysis/LoopInfo.h"
00021 #include "llvm/Analysis/TargetTransformInfo.h"
00022 #include "llvm/IR/DataLayout.h"
00023 #include "llvm/IR/Dominators.h"
00024 #include "llvm/IR/IntrinsicInst.h"
00025 #include "llvm/IR/LLVMContext.h"
00026 #include "llvm/IR/Module.h"
00027 #include "llvm/IR/PatternMatch.h"
00028 #include "llvm/Support/Debug.h"
00029 #include "llvm/Support/raw_ostream.h"
00030 
00031 using namespace llvm;
00032 using namespace PatternMatch;
00033 
00034 /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
00035 /// reusing an existing cast if a suitable one exists, moving an existing
00036 /// cast if a suitable one exists but isn't in the right place, or
00037 /// creating a new one.
00038 Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,
00039                                        Instruction::CastOps Op,
00040                                        BasicBlock::iterator IP) {
00041   // This function must be called with the builder having a valid insertion
00042   // point. It doesn't need to be the actual IP where the uses of the returned
00043   // cast will be added, but it must dominate such IP.
00044   // We use this precondition to produce a cast that will dominate all its
00045   // uses. In particular, this is crucial for the case where the builder's
00046   // insertion point *is* the point where we were asked to put the cast.
00047   // Since we don't know the builder's insertion point is actually
00048   // where the uses will be added (only that it dominates it), we are
00049   // not allowed to move it.
00050   BasicBlock::iterator BIP = Builder.GetInsertPoint();
00051 
00052   Instruction *Ret = nullptr;
00053 
00054   // Check to see if there is already a cast!
00055   for (User *U : V->users())
00056     if (U->getType() == Ty)
00057       if (CastInst *CI = dyn_cast<CastInst>(U))
00058         if (CI->getOpcode() == Op) {
00059           // If the cast isn't where we want it, create a new cast at IP.
00060           // Likewise, do not reuse a cast at BIP because it must dominate
00061           // instructions that might be inserted before BIP.
00062           if (BasicBlock::iterator(CI) != IP || BIP == IP) {
00063             // Create a new cast, and leave the old cast in place in case
00064             // it is being used as an insert point. Clear its operand
00065             // so that it doesn't hold anything live.
00066             Ret = CastInst::Create(Op, V, Ty, "", &*IP);
00067             Ret->takeName(CI);
00068             CI->replaceAllUsesWith(Ret);
00069             CI->setOperand(0, UndefValue::get(V->getType()));
00070             break;
00071           }
00072           Ret = CI;
00073           break;
00074         }
00075 
00076   // Create a new cast.
00077   if (!Ret)
00078     Ret = CastInst::Create(Op, V, Ty, V->getName(), &*IP);
00079 
00080   // We assert at the end of the function since IP might point to an
00081   // instruction with different dominance properties than a cast
00082   // (an invoke for example) and not dominate BIP (but the cast does).
00083   assert(SE.DT.dominates(Ret, &*BIP));
00084 
00085   rememberInstruction(Ret);
00086   return Ret;
00087 }
00088 
00089 static BasicBlock::iterator findInsertPointAfter(Instruction *I,
00090                                                  BasicBlock *MustDominate) {
00091   BasicBlock::iterator IP = ++I->getIterator();
00092   if (auto *II = dyn_cast<InvokeInst>(I))
00093     IP = II->getNormalDest()->begin();
00094 
00095   while (isa<PHINode>(IP))
00096     ++IP;
00097 
00098   while (IP->isEHPad()) {
00099     if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {
00100       ++IP;
00101     } else if (isa<CatchSwitchInst>(IP)) {
00102       IP = MustDominate->getFirstInsertionPt();
00103     } else {
00104       llvm_unreachable("unexpected eh pad!");
00105     }
00106   }
00107 
00108   return IP;
00109 }
00110 
00111 /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
00112 /// which must be possible with a noop cast, doing what we can to share
00113 /// the casts.
00114 Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
00115   Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false);
00116   assert((Op == Instruction::BitCast ||
00117           Op == Instruction::PtrToInt ||
00118           Op == Instruction::IntToPtr) &&
00119          "InsertNoopCastOfTo cannot perform non-noop casts!");
00120   assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) &&
00121          "InsertNoopCastOfTo cannot change sizes!");
00122 
00123   // Short-circuit unnecessary bitcasts.
00124   if (Op == Instruction::BitCast) {
00125     if (V->getType() == Ty)
00126       return V;
00127     if (CastInst *CI = dyn_cast<CastInst>(V)) {
00128       if (CI->getOperand(0)->getType() == Ty)
00129         return CI->getOperand(0);
00130     }
00131   }
00132   // Short-circuit unnecessary inttoptr<->ptrtoint casts.
00133   if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) &&
00134       SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) {
00135     if (CastInst *CI = dyn_cast<CastInst>(V))
00136       if ((CI->getOpcode() == Instruction::PtrToInt ||
00137            CI->getOpcode() == Instruction::IntToPtr) &&
00138           SE.getTypeSizeInBits(CI->getType()) ==
00139           SE.getTypeSizeInBits(CI->getOperand(0)->getType()))
00140         return CI->getOperand(0);
00141     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
00142       if ((CE->getOpcode() == Instruction::PtrToInt ||
00143            CE->getOpcode() == Instruction::IntToPtr) &&
00144           SE.getTypeSizeInBits(CE->getType()) ==
00145           SE.getTypeSizeInBits(CE->getOperand(0)->getType()))
00146         return CE->getOperand(0);
00147   }
00148 
00149   // Fold a cast of a constant.
00150   if (Constant *C = dyn_cast<Constant>(V))
00151     return ConstantExpr::getCast(Op, C, Ty);
00152 
00153   // Cast the argument at the beginning of the entry block, after
00154   // any bitcasts of other arguments.
00155   if (Argument *A = dyn_cast<Argument>(V)) {
00156     BasicBlock::iterator IP = A->getParent()->getEntryBlock().begin();
00157     while ((isa<BitCastInst>(IP) &&
00158             isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) &&
00159             cast<BitCastInst>(IP)->getOperand(0) != A) ||
00160            isa<DbgInfoIntrinsic>(IP))
00161       ++IP;
00162     return ReuseOrCreateCast(A, Ty, Op, IP);
00163   }
00164 
00165   // Cast the instruction immediately after the instruction.
00166   Instruction *I = cast<Instruction>(V);
00167   BasicBlock::iterator IP = findInsertPointAfter(I, Builder.GetInsertBlock());
00168   return ReuseOrCreateCast(I, Ty, Op, IP);
00169 }
00170 
00171 /// InsertBinop - Insert the specified binary operator, doing a small amount
00172 /// of work to avoid inserting an obviously redundant operation.
00173 Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
00174                                  Value *LHS, Value *RHS) {
00175   // Fold a binop with constant operands.
00176   if (Constant *CLHS = dyn_cast<Constant>(LHS))
00177     if (Constant *CRHS = dyn_cast<Constant>(RHS))
00178       return ConstantExpr::get(Opcode, CLHS, CRHS);
00179 
00180   // Do a quick scan to see if we have this binop nearby.  If so, reuse it.
00181   unsigned ScanLimit = 6;
00182   BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
00183   // Scanning starts from the last instruction before the insertion point.
00184   BasicBlock::iterator IP = Builder.GetInsertPoint();
00185   if (IP != BlockBegin) {
00186     --IP;
00187     for (; ScanLimit; --IP, --ScanLimit) {
00188       // Don't count dbg.value against the ScanLimit, to avoid perturbing the
00189       // generated code.
00190       if (isa<DbgInfoIntrinsic>(IP))
00191         ScanLimit++;
00192       if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS &&
00193           IP->getOperand(1) == RHS)
00194         return &*IP;
00195       if (IP == BlockBegin) break;
00196     }
00197   }
00198 
00199   // Save the original insertion point so we can restore it when we're done.
00200   DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();
00201   BuilderType::InsertPointGuard Guard(Builder);
00202 
00203   // Move the insertion point out of as many loops as we can.
00204   while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
00205     if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break;
00206     BasicBlock *Preheader = L->getLoopPreheader();
00207     if (!Preheader) break;
00208 
00209     // Ok, move up a level.
00210     Builder.SetInsertPoint(Preheader->getTerminator());
00211   }
00212 
00213   // If we haven't found this binop, insert it.
00214   Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS));
00215   BO->setDebugLoc(Loc);
00216   rememberInstruction(BO);
00217 
00218   return BO;
00219 }
00220 
00221 /// FactorOutConstant - Test if S is divisible by Factor, using signed
00222 /// division. If so, update S with Factor divided out and return true.
00223 /// S need not be evenly divisible if a reasonable remainder can be
00224 /// computed.
00225 /// TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made
00226 /// unnecessary; in its place, just signed-divide Ops[i] by the scale and
00227 /// check to see if the divide was folded.
00228 static bool FactorOutConstant(const SCEV *&S, const SCEV *&Remainder,
00229                               const SCEV *Factor, ScalarEvolution &SE,
00230                               const DataLayout &DL) {
00231   // Everything is divisible by one.
00232   if (Factor->isOne())
00233     return true;
00234 
00235   // x/x == 1.
00236   if (S == Factor) {
00237     S = SE.getConstant(S->getType(), 1);
00238     return true;
00239   }
00240 
00241   // For a Constant, check for a multiple of the given factor.
00242   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
00243     // 0/x == 0.
00244     if (C->isZero())
00245       return true;
00246     // Check for divisibility.
00247     if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) {
00248       ConstantInt *CI =
00249           ConstantInt::get(SE.getContext(), C->getAPInt().sdiv(FC->getAPInt()));
00250       // If the quotient is zero and the remainder is non-zero, reject
00251       // the value at this scale. It will be considered for subsequent
00252       // smaller scales.
00253       if (!CI->isZero()) {
00254         const SCEV *Div = SE.getConstant(CI);
00255         S = Div;
00256         Remainder = SE.getAddExpr(
00257             Remainder, SE.getConstant(C->getAPInt().srem(FC->getAPInt())));
00258         return true;
00259       }
00260     }
00261   }
00262 
00263   // In a Mul, check if there is a constant operand which is a multiple
00264   // of the given factor.
00265   if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
00266     // Size is known, check if there is a constant operand which is a multiple
00267     // of the given factor. If so, we can factor it.
00268     const SCEVConstant *FC = cast<SCEVConstant>(Factor);
00269     if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0)))
00270       if (!C->getAPInt().srem(FC->getAPInt())) {
00271         SmallVector<const SCEV *, 4> NewMulOps(M->op_begin(), M->op_end());
00272         NewMulOps[0] = SE.getConstant(C->getAPInt().sdiv(FC->getAPInt()));
00273         S = SE.getMulExpr(NewMulOps);
00274         return true;
00275       }
00276   }
00277 
00278   // In an AddRec, check if both start and step are divisible.
00279   if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
00280     const SCEV *Step = A->getStepRecurrence(SE);
00281     const SCEV *StepRem = SE.getConstant(Step->getType(), 0);
00282     if (!FactorOutConstant(Step, StepRem, Factor, SE, DL))
00283       return false;
00284     if (!StepRem->isZero())
00285       return false;
00286     const SCEV *Start = A->getStart();
00287     if (!FactorOutConstant(Start, Remainder, Factor, SE, DL))
00288       return false;
00289     S = SE.getAddRecExpr(Start, Step, A->getLoop(),
00290                          A->getNoWrapFlags(SCEV::FlagNW));
00291     return true;
00292   }
00293 
00294   return false;
00295 }
00296 
00297 /// SimplifyAddOperands - Sort and simplify a list of add operands. NumAddRecs
00298 /// is the number of SCEVAddRecExprs present, which are kept at the end of
00299 /// the list.
00300 ///
00301 static void SimplifyAddOperands(SmallVectorImpl<const SCEV *> &Ops,
00302                                 Type *Ty,
00303                                 ScalarEvolution &SE) {
00304   unsigned NumAddRecs = 0;
00305   for (unsigned i = Ops.size(); i > 0 && isa<SCEVAddRecExpr>(Ops[i-1]); --i)
00306     ++NumAddRecs;
00307   // Group Ops into non-addrecs and addrecs.
00308   SmallVector<const SCEV *, 8> NoAddRecs(Ops.begin(), Ops.end() - NumAddRecs);
00309   SmallVector<const SCEV *, 8> AddRecs(Ops.end() - NumAddRecs, Ops.end());
00310   // Let ScalarEvolution sort and simplify the non-addrecs list.
00311   const SCEV *Sum = NoAddRecs.empty() ?
00312                     SE.getConstant(Ty, 0) :
00313                     SE.getAddExpr(NoAddRecs);
00314   // If it returned an add, use the operands. Otherwise it simplified
00315   // the sum into a single value, so just use that.
00316   Ops.clear();
00317   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum))
00318     Ops.append(Add->op_begin(), Add->op_end());
00319   else if (!Sum->isZero())
00320     Ops.push_back(Sum);
00321   // Then append the addrecs.
00322   Ops.append(AddRecs.begin(), AddRecs.end());
00323 }
00324 
00325 /// SplitAddRecs - Flatten a list of add operands, moving addrec start values
00326 /// out to the top level. For example, convert {a + b,+,c} to a, b, {0,+,d}.
00327 /// This helps expose more opportunities for folding parts of the expressions
00328 /// into GEP indices.
00329 ///
00330 static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops,
00331                          Type *Ty,
00332                          ScalarEvolution &SE) {
00333   // Find the addrecs.
00334   SmallVector<const SCEV *, 8> AddRecs;
00335   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
00336     while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) {
00337       const SCEV *Start = A->getStart();
00338       if (Start->isZero()) break;
00339       const SCEV *Zero = SE.getConstant(Ty, 0);
00340       AddRecs.push_back(SE.getAddRecExpr(Zero,
00341                                          A->getStepRecurrence(SE),
00342                                          A->getLoop(),
00343                                          A->getNoWrapFlags(SCEV::FlagNW)));
00344       if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) {
00345         Ops[i] = Zero;
00346         Ops.append(Add->op_begin(), Add->op_end());
00347         e += Add->getNumOperands();
00348       } else {
00349         Ops[i] = Start;
00350       }
00351     }
00352   if (!AddRecs.empty()) {
00353     // Add the addrecs onto the end of the list.
00354     Ops.append(AddRecs.begin(), AddRecs.end());
00355     // Resort the operand list, moving any constants to the front.
00356     SimplifyAddOperands(Ops, Ty, SE);
00357   }
00358 }
00359 
00360 /// expandAddToGEP - Expand an addition expression with a pointer type into
00361 /// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps
00362 /// BasicAliasAnalysis and other passes analyze the result. See the rules
00363 /// for getelementptr vs. inttoptr in
00364 /// http://llvm.org/docs/LangRef.html#pointeraliasing
00365 /// for details.
00366 ///
00367 /// Design note: The correctness of using getelementptr here depends on
00368 /// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as
00369 /// they may introduce pointer arithmetic which may not be safely converted
00370 /// into getelementptr.
00371 ///
00372 /// Design note: It might seem desirable for this function to be more
00373 /// loop-aware. If some of the indices are loop-invariant while others
00374 /// aren't, it might seem desirable to emit multiple GEPs, keeping the
00375 /// loop-invariant portions of the overall computation outside the loop.
00376 /// However, there are a few reasons this is not done here. Hoisting simple
00377 /// arithmetic is a low-level optimization that often isn't very
00378 /// important until late in the optimization process. In fact, passes
00379 /// like InstructionCombining will combine GEPs, even if it means
00380 /// pushing loop-invariant computation down into loops, so even if the
00381 /// GEPs were split here, the work would quickly be undone. The
00382 /// LoopStrengthReduction pass, which is usually run quite late (and
00383 /// after the last InstructionCombining pass), takes care of hoisting
00384 /// loop-invariant portions of expressions, after considering what
00385 /// can be folded using target addressing modes.
00386 ///
00387 Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin,
00388                                     const SCEV *const *op_end,
00389                                     PointerType *PTy,
00390                                     Type *Ty,
00391                                     Value *V) {
00392   Type *OriginalElTy = PTy->getElementType();
00393   Type *ElTy = OriginalElTy;
00394   SmallVector<Value *, 4> GepIndices;
00395   SmallVector<const SCEV *, 8> Ops(op_begin, op_end);
00396   bool AnyNonZeroIndices = false;
00397 
00398   // Split AddRecs up into parts as either of the parts may be usable
00399   // without the other.
00400   SplitAddRecs(Ops, Ty, SE);
00401 
00402   Type *IntPtrTy = DL.getIntPtrType(PTy);
00403 
00404   // Descend down the pointer's type and attempt to convert the other
00405   // operands into GEP indices, at each level. The first index in a GEP
00406   // indexes into the array implied by the pointer operand; the rest of
00407   // the indices index into the element or field type selected by the
00408   // preceding index.
00409   for (;;) {
00410     // If the scale size is not 0, attempt to factor out a scale for
00411     // array indexing.
00412     SmallVector<const SCEV *, 8> ScaledOps;
00413     if (ElTy->isSized()) {
00414       const SCEV *ElSize = SE.getSizeOfExpr(IntPtrTy, ElTy);
00415       if (!ElSize->isZero()) {
00416         SmallVector<const SCEV *, 8> NewOps;
00417         for (const SCEV *Op : Ops) {
00418           const SCEV *Remainder = SE.getConstant(Ty, 0);
00419           if (FactorOutConstant(Op, Remainder, ElSize, SE, DL)) {
00420             // Op now has ElSize factored out.
00421             ScaledOps.push_back(Op);
00422             if (!Remainder->isZero())
00423               NewOps.push_back(Remainder);
00424             AnyNonZeroIndices = true;
00425           } else {
00426             // The operand was not divisible, so add it to the list of operands
00427             // we'll scan next iteration.
00428             NewOps.push_back(Op);
00429           }
00430         }
00431         // If we made any changes, update Ops.
00432         if (!ScaledOps.empty()) {
00433           Ops = NewOps;
00434           SimplifyAddOperands(Ops, Ty, SE);
00435         }
00436       }
00437     }
00438 
00439     // Record the scaled array index for this level of the type. If
00440     // we didn't find any operands that could be factored, tentatively
00441     // assume that element zero was selected (since the zero offset
00442     // would obviously be folded away).
00443     Value *Scaled = ScaledOps.empty() ?
00444                     Constant::getNullValue(Ty) :
00445                     expandCodeFor(SE.getAddExpr(ScaledOps), Ty);
00446     GepIndices.push_back(Scaled);
00447 
00448     // Collect struct field index operands.
00449     while (StructType *STy = dyn_cast<StructType>(ElTy)) {
00450       bool FoundFieldNo = false;
00451       // An empty struct has no fields.
00452       if (STy->getNumElements() == 0) break;
00453       // Field offsets are known. See if a constant offset falls within any of
00454       // the struct fields.
00455       if (Ops.empty())
00456         break;
00457       if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0]))
00458         if (SE.getTypeSizeInBits(C->getType()) <= 64) {
00459           const StructLayout &SL = *DL.getStructLayout(STy);
00460           uint64_t FullOffset = C->getValue()->getZExtValue();
00461           if (FullOffset < SL.getSizeInBytes()) {
00462             unsigned ElIdx = SL.getElementContainingOffset(FullOffset);
00463             GepIndices.push_back(
00464                 ConstantInt::get(Type::getInt32Ty(Ty->getContext()), ElIdx));
00465             ElTy = STy->getTypeAtIndex(ElIdx);
00466             Ops[0] =
00467                 SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx));
00468             AnyNonZeroIndices = true;
00469             FoundFieldNo = true;
00470           }
00471         }
00472       // If no struct field offsets were found, tentatively assume that
00473       // field zero was selected (since the zero offset would obviously
00474       // be folded away).
00475       if (!FoundFieldNo) {
00476         ElTy = STy->getTypeAtIndex(0u);
00477         GepIndices.push_back(
00478           Constant::getNullValue(Type::getInt32Ty(Ty->getContext())));
00479       }
00480     }
00481 
00482     if (ArrayType *ATy = dyn_cast<ArrayType>(ElTy))
00483       ElTy = ATy->getElementType();
00484     else
00485       break;
00486   }
00487 
00488   // If none of the operands were convertible to proper GEP indices, cast
00489   // the base to i8* and do an ugly getelementptr with that. It's still
00490   // better than ptrtoint+arithmetic+inttoptr at least.
00491   if (!AnyNonZeroIndices) {
00492     // Cast the base to i8*.
00493     V = InsertNoopCastOfTo(V,
00494        Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace()));
00495 
00496     assert(!isa<Instruction>(V) ||
00497            SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()));
00498 
00499     // Expand the operands for a plain byte offset.
00500     Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty);
00501 
00502     // Fold a GEP with constant operands.
00503     if (Constant *CLHS = dyn_cast<Constant>(V))
00504       if (Constant *CRHS = dyn_cast<Constant>(Idx))
00505         return ConstantExpr::getGetElementPtr(Type::getInt8Ty(Ty->getContext()),
00506                                               CLHS, CRHS);
00507 
00508     // Do a quick scan to see if we have this GEP nearby.  If so, reuse it.
00509     unsigned ScanLimit = 6;
00510     BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
00511     // Scanning starts from the last instruction before the insertion point.
00512     BasicBlock::iterator IP = Builder.GetInsertPoint();
00513     if (IP != BlockBegin) {
00514       --IP;
00515       for (; ScanLimit; --IP, --ScanLimit) {
00516         // Don't count dbg.value against the ScanLimit, to avoid perturbing the
00517         // generated code.
00518         if (isa<DbgInfoIntrinsic>(IP))
00519           ScanLimit++;
00520         if (IP->getOpcode() == Instruction::GetElementPtr &&
00521             IP->getOperand(0) == V && IP->getOperand(1) == Idx)
00522           return &*IP;
00523         if (IP == BlockBegin) break;
00524       }
00525     }
00526 
00527     // Save the original insertion point so we can restore it when we're done.
00528     BuilderType::InsertPointGuard Guard(Builder);
00529 
00530     // Move the insertion point out of as many loops as we can.
00531     while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
00532       if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break;
00533       BasicBlock *Preheader = L->getLoopPreheader();
00534       if (!Preheader) break;
00535 
00536       // Ok, move up a level.
00537       Builder.SetInsertPoint(Preheader->getTerminator());
00538     }
00539 
00540     // Emit a GEP.
00541     Value *GEP = Builder.CreateGEP(Builder.getInt8Ty(), V, Idx, "uglygep");
00542     rememberInstruction(GEP);
00543 
00544     return GEP;
00545   }
00546 
00547   // Save the original insertion point so we can restore it when we're done.
00548   BuilderType::InsertPoint SaveInsertPt = Builder.saveIP();
00549 
00550   // Move the insertion point out of as many loops as we can.
00551   while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
00552     if (!L->isLoopInvariant(V)) break;
00553 
00554     bool AnyIndexNotLoopInvariant =
00555         std::any_of(GepIndices.begin(), GepIndices.end(),
00556                     [L](Value *Op) { return !L->isLoopInvariant(Op); });
00557 
00558     if (AnyIndexNotLoopInvariant)
00559       break;
00560 
00561     BasicBlock *Preheader = L->getLoopPreheader();
00562     if (!Preheader) break;
00563 
00564     // Ok, move up a level.
00565     Builder.SetInsertPoint(Preheader->getTerminator());
00566   }
00567 
00568   // Insert a pretty getelementptr. Note that this GEP is not marked inbounds,
00569   // because ScalarEvolution may have changed the address arithmetic to
00570   // compute a value which is beyond the end of the allocated object.
00571   Value *Casted = V;
00572   if (V->getType() != PTy)
00573     Casted = InsertNoopCastOfTo(Casted, PTy);
00574   Value *GEP = Builder.CreateGEP(OriginalElTy, Casted, GepIndices, "scevgep");
00575   Ops.push_back(SE.getUnknown(GEP));
00576   rememberInstruction(GEP);
00577 
00578   // Restore the original insert point.
00579   Builder.restoreIP(SaveInsertPt);
00580 
00581   return expand(SE.getAddExpr(Ops));
00582 }
00583 
00584 /// PickMostRelevantLoop - Given two loops pick the one that's most relevant for
00585 /// SCEV expansion. If they are nested, this is the most nested. If they are
00586 /// neighboring, pick the later.
00587 static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B,
00588                                         DominatorTree &DT) {
00589   if (!A) return B;
00590   if (!B) return A;
00591   if (A->contains(B)) return B;
00592   if (B->contains(A)) return A;
00593   if (DT.dominates(A->getHeader(), B->getHeader())) return B;
00594   if (DT.dominates(B->getHeader(), A->getHeader())) return A;
00595   return A; // Arbitrarily break the tie.
00596 }
00597 
00598 /// getRelevantLoop - Get the most relevant loop associated with the given
00599 /// expression, according to PickMostRelevantLoop.
00600 const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) {
00601   // Test whether we've already computed the most relevant loop for this SCEV.
00602   auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr));
00603   if (!Pair.second)
00604     return Pair.first->second;
00605 
00606   if (isa<SCEVConstant>(S))
00607     // A constant has no relevant loops.
00608     return nullptr;
00609   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
00610     if (const Instruction *I = dyn_cast<Instruction>(U->getValue()))
00611       return Pair.first->second = SE.LI.getLoopFor(I->getParent());
00612     // A non-instruction has no relevant loops.
00613     return nullptr;
00614   }
00615   if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) {
00616     const Loop *L = nullptr;
00617     if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
00618       L = AR->getLoop();
00619     for (const SCEV *Op : N->operands())
00620       L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT);
00621     return RelevantLoops[N] = L;
00622   }
00623   if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) {
00624     const Loop *Result = getRelevantLoop(C->getOperand());
00625     return RelevantLoops[C] = Result;
00626   }
00627   if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
00628     const Loop *Result = PickMostRelevantLoop(
00629         getRelevantLoop(D->getLHS()), getRelevantLoop(D->getRHS()), SE.DT);
00630     return RelevantLoops[D] = Result;
00631   }
00632   llvm_unreachable("Unexpected SCEV type!");
00633 }
00634 
00635 namespace {
00636 
00637 /// LoopCompare - Compare loops by PickMostRelevantLoop.
00638 class LoopCompare {
00639   DominatorTree &DT;
00640 public:
00641   explicit LoopCompare(DominatorTree &dt) : DT(dt) {}
00642 
00643   bool operator()(std::pair<const Loop *, const SCEV *> LHS,
00644                   std::pair<const Loop *, const SCEV *> RHS) const {
00645     // Keep pointer operands sorted at the end.
00646     if (LHS.second->getType()->isPointerTy() !=
00647         RHS.second->getType()->isPointerTy())
00648       return LHS.second->getType()->isPointerTy();
00649 
00650     // Compare loops with PickMostRelevantLoop.
00651     if (LHS.first != RHS.first)
00652       return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first;
00653 
00654     // If one operand is a non-constant negative and the other is not,
00655     // put the non-constant negative on the right so that a sub can
00656     // be used instead of a negate and add.
00657     if (LHS.second->isNonConstantNegative()) {
00658       if (!RHS.second->isNonConstantNegative())
00659         return false;
00660     } else if (RHS.second->isNonConstantNegative())
00661       return true;
00662 
00663     // Otherwise they are equivalent according to this comparison.
00664     return false;
00665   }
00666 };
00667 
00668 }
00669 
00670 Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) {
00671   Type *Ty = SE.getEffectiveSCEVType(S->getType());
00672 
00673   // Collect all the add operands in a loop, along with their associated loops.
00674   // Iterate in reverse so that constants are emitted last, all else equal, and
00675   // so that pointer operands are inserted first, which the code below relies on
00676   // to form more involved GEPs.
00677   SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
00678   for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(S->op_end()),
00679        E(S->op_begin()); I != E; ++I)
00680     OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
00681 
00682   // Sort by loop. Use a stable sort so that constants follow non-constants and
00683   // pointer operands precede non-pointer operands.
00684   std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(SE.DT));
00685 
00686   // Emit instructions to add all the operands. Hoist as much as possible
00687   // out of loops, and form meaningful getelementptrs where possible.
00688   Value *Sum = nullptr;
00689   for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) {
00690     const Loop *CurLoop = I->first;
00691     const SCEV *Op = I->second;
00692     if (!Sum) {
00693       // This is the first operand. Just expand it.
00694       Sum = expand(Op);
00695       ++I;
00696     } else if (PointerType *PTy = dyn_cast<PointerType>(Sum->getType())) {
00697       // The running sum expression is a pointer. Try to form a getelementptr
00698       // at this level with that as the base.
00699       SmallVector<const SCEV *, 4> NewOps;
00700       for (; I != E && I->first == CurLoop; ++I) {
00701         // If the operand is SCEVUnknown and not instructions, peek through
00702         // it, to enable more of it to be folded into the GEP.
00703         const SCEV *X = I->second;
00704         if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X))
00705           if (!isa<Instruction>(U->getValue()))
00706             X = SE.getSCEV(U->getValue());
00707         NewOps.push_back(X);
00708       }
00709       Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum);
00710     } else if (PointerType *PTy = dyn_cast<PointerType>(Op->getType())) {
00711       // The running sum is an integer, and there's a pointer at this level.
00712       // Try to form a getelementptr. If the running sum is instructions,
00713       // use a SCEVUnknown to avoid re-analyzing them.
00714       SmallVector<const SCEV *, 4> NewOps;
00715       NewOps.push_back(isa<Instruction>(Sum) ? SE.getUnknown(Sum) :
00716                                                SE.getSCEV(Sum));
00717       for (++I; I != E && I->first == CurLoop; ++I)
00718         NewOps.push_back(I->second);
00719       Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, expand(Op));
00720     } else if (Op->isNonConstantNegative()) {
00721       // Instead of doing a negate and add, just do a subtract.
00722       Value *W = expandCodeFor(SE.getNegativeSCEV(Op), Ty);
00723       Sum = InsertNoopCastOfTo(Sum, Ty);
00724       Sum = InsertBinop(Instruction::Sub, Sum, W);
00725       ++I;
00726     } else {
00727       // A simple add.
00728       Value *W = expandCodeFor(Op, Ty);
00729       Sum = InsertNoopCastOfTo(Sum, Ty);
00730       // Canonicalize a constant to the RHS.
00731       if (isa<Constant>(Sum)) std::swap(Sum, W);
00732       Sum = InsertBinop(Instruction::Add, Sum, W);
00733       ++I;
00734     }
00735   }
00736 
00737   return Sum;
00738 }
00739 
00740 Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
00741   Type *Ty = SE.getEffectiveSCEVType(S->getType());
00742 
00743   // Collect all the mul operands in a loop, along with their associated loops.
00744   // Iterate in reverse so that constants are emitted last, all else equal.
00745   SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
00746   for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()),
00747        E(S->op_begin()); I != E; ++I)
00748     OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
00749 
00750   // Sort by loop. Use a stable sort so that constants follow non-constants.
00751   std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(SE.DT));
00752 
00753   // Emit instructions to mul all the operands. Hoist as much as possible
00754   // out of loops.
00755   Value *Prod = nullptr;
00756   for (const auto &I : OpsAndLoops) {
00757     const SCEV *Op = I.second;
00758     if (!Prod) {
00759       // This is the first operand. Just expand it.
00760       Prod = expand(Op);
00761     } else if (Op->isAllOnesValue()) {
00762       // Instead of doing a multiply by negative one, just do a negate.
00763       Prod = InsertNoopCastOfTo(Prod, Ty);
00764       Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod);
00765     } else {
00766       // A simple mul.
00767       Value *W = expandCodeFor(Op, Ty);
00768       Prod = InsertNoopCastOfTo(Prod, Ty);
00769       // Canonicalize a constant to the RHS.
00770       if (isa<Constant>(Prod)) std::swap(Prod, W);
00771       const APInt *RHS;
00772       if (match(W, m_Power2(RHS))) {
00773         // Canonicalize Prod*(1<<C) to Prod<<C.
00774         assert(!Ty->isVectorTy() && "vector types are not SCEVable");
00775         Prod = InsertBinop(Instruction::Shl, Prod,
00776                            ConstantInt::get(Ty, RHS->logBase2()));
00777       } else {
00778         Prod = InsertBinop(Instruction::Mul, Prod, W);
00779       }
00780     }
00781   }
00782 
00783   return Prod;
00784 }
00785 
00786 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
00787   Type *Ty = SE.getEffectiveSCEVType(S->getType());
00788 
00789   Value *LHS = expandCodeFor(S->getLHS(), Ty);
00790   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
00791     const APInt &RHS = SC->getAPInt();
00792     if (RHS.isPowerOf2())
00793       return InsertBinop(Instruction::LShr, LHS,
00794                          ConstantInt::get(Ty, RHS.logBase2()));
00795   }
00796 
00797   Value *RHS = expandCodeFor(S->getRHS(), Ty);
00798   return InsertBinop(Instruction::UDiv, LHS, RHS);
00799 }
00800 
00801 /// Move parts of Base into Rest to leave Base with the minimal
00802 /// expression that provides a pointer operand suitable for a
00803 /// GEP expansion.
00804 static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest,
00805                               ScalarEvolution &SE) {
00806   while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) {
00807     Base = A->getStart();
00808     Rest = SE.getAddExpr(Rest,
00809                          SE.getAddRecExpr(SE.getConstant(A->getType(), 0),
00810                                           A->getStepRecurrence(SE),
00811                                           A->getLoop(),
00812                                           A->getNoWrapFlags(SCEV::FlagNW)));
00813   }
00814   if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) {
00815     Base = A->getOperand(A->getNumOperands()-1);
00816     SmallVector<const SCEV *, 8> NewAddOps(A->op_begin(), A->op_end());
00817     NewAddOps.back() = Rest;
00818     Rest = SE.getAddExpr(NewAddOps);
00819     ExposePointerBase(Base, Rest, SE);
00820   }
00821 }
00822 
00823 /// Determine if this is a well-behaved chain of instructions leading back to
00824 /// the PHI. If so, it may be reused by expanded expressions.
00825 bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
00826                                          const Loop *L) {
00827   if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) ||
00828       (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))
00829     return false;
00830   // If any of the operands don't dominate the insert position, bail.
00831   // Addrec operands are always loop-invariant, so this can only happen
00832   // if there are instructions which haven't been hoisted.
00833   if (L == IVIncInsertLoop) {
00834     for (User::op_iterator OI = IncV->op_begin()+1,
00835            OE = IncV->op_end(); OI != OE; ++OI)
00836       if (Instruction *OInst = dyn_cast<Instruction>(OI))
00837         if (!SE.DT.dominates(OInst, IVIncInsertPos))
00838           return false;
00839   }
00840   // Advance to the next instruction.
00841   IncV = dyn_cast<Instruction>(IncV->getOperand(0));
00842   if (!IncV)
00843     return false;
00844 
00845   if (IncV->mayHaveSideEffects())
00846     return false;
00847 
00848   if (IncV != PN)
00849     return true;
00850 
00851   return isNormalAddRecExprPHI(PN, IncV, L);
00852 }
00853 
00854 /// getIVIncOperand returns an induction variable increment's induction
00855 /// variable operand.
00856 ///
00857 /// If allowScale is set, any type of GEP is allowed as long as the nonIV
00858 /// operands dominate InsertPos.
00859 ///
00860 /// If allowScale is not set, ensure that a GEP increment conforms to one of the
00861 /// simple patterns generated by getAddRecExprPHILiterally and
00862 /// expandAddtoGEP. If the pattern isn't recognized, return NULL.
00863 Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV,
00864                                            Instruction *InsertPos,
00865                                            bool allowScale) {
00866   if (IncV == InsertPos)
00867     return nullptr;
00868 
00869   switch (IncV->getOpcode()) {
00870   default:
00871     return nullptr;
00872   // Check for a simple Add/Sub or GEP of a loop invariant step.
00873   case Instruction::Add:
00874   case Instruction::Sub: {
00875     Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));
00876     if (!OInst || SE.DT.dominates(OInst, InsertPos))
00877       return dyn_cast<Instruction>(IncV->getOperand(0));
00878     return nullptr;
00879   }
00880   case Instruction::BitCast:
00881     return dyn_cast<Instruction>(IncV->getOperand(0));
00882   case Instruction::GetElementPtr:
00883     for (auto I = IncV->op_begin() + 1, E = IncV->op_end(); I != E; ++I) {
00884       if (isa<Constant>(*I))
00885         continue;
00886       if (Instruction *OInst = dyn_cast<Instruction>(*I)) {
00887         if (!SE.DT.dominates(OInst, InsertPos))
00888           return nullptr;
00889       }
00890       if (allowScale) {
00891         // allow any kind of GEP as long as it can be hoisted.
00892         continue;
00893       }
00894       // This must be a pointer addition of constants (pretty), which is already
00895       // handled, or some number of address-size elements (ugly). Ugly geps
00896       // have 2 operands. i1* is used by the expander to represent an
00897       // address-size element.
00898       if (IncV->getNumOperands() != 2)
00899         return nullptr;
00900       unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace();
00901       if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS)
00902           && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS))
00903         return nullptr;
00904       break;
00905     }
00906     return dyn_cast<Instruction>(IncV->getOperand(0));
00907   }
00908 }
00909 
00910 /// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make
00911 /// it available to other uses in this loop. Recursively hoist any operands,
00912 /// until we reach a value that dominates InsertPos.
00913 bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) {
00914   if (SE.DT.dominates(IncV, InsertPos))
00915       return true;
00916 
00917   // InsertPos must itself dominate IncV so that IncV's new position satisfies
00918   // its existing users.
00919   if (isa<PHINode>(InsertPos) ||
00920       !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))
00921     return false;
00922 
00923   if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
00924     return false;
00925 
00926   // Check that the chain of IV operands leading back to Phi can be hoisted.
00927   SmallVector<Instruction*, 4> IVIncs;
00928   for(;;) {
00929     Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true);
00930     if (!Oper)
00931       return false;
00932     // IncV is safe to hoist.
00933     IVIncs.push_back(IncV);
00934     IncV = Oper;
00935     if (SE.DT.dominates(IncV, InsertPos))
00936       break;
00937   }
00938   for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) {
00939     (*I)->moveBefore(InsertPos);
00940   }
00941   return true;
00942 }
00943 
00944 /// Determine if this cyclic phi is in a form that would have been generated by
00945 /// LSR. We don't care if the phi was actually expanded in this pass, as long
00946 /// as it is in a low-cost form, for example, no implied multiplication. This
00947 /// should match any patterns generated by getAddRecExprPHILiterally and
00948 /// expandAddtoGEP.
00949 bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
00950                                            const Loop *L) {
00951   for(Instruction *IVOper = IncV;
00952       (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
00953                                 /*allowScale=*/false));) {
00954     if (IVOper == PN)
00955       return true;
00956   }
00957   return false;
00958 }
00959 
00960 /// expandIVInc - Expand an IV increment at Builder's current InsertPos.
00961 /// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may
00962 /// need to materialize IV increments elsewhere to handle difficult situations.
00963 Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
00964                                  Type *ExpandTy, Type *IntTy,
00965                                  bool useSubtract) {
00966   Value *IncV;
00967   // If the PHI is a pointer, use a GEP, otherwise use an add or sub.
00968   if (ExpandTy->isPointerTy()) {
00969     PointerType *GEPPtrTy = cast<PointerType>(ExpandTy);
00970     // If the step isn't constant, don't use an implicitly scaled GEP, because
00971     // that would require a multiply inside the loop.
00972     if (!isa<ConstantInt>(StepV))
00973       GEPPtrTy = PointerType::get(Type::getInt1Ty(SE.getContext()),
00974                                   GEPPtrTy->getAddressSpace());
00975     const SCEV *const StepArray[1] = { SE.getSCEV(StepV) };
00976     IncV = expandAddToGEP(StepArray, StepArray+1, GEPPtrTy, IntTy, PN);
00977     if (IncV->getType() != PN->getType()) {
00978       IncV = Builder.CreateBitCast(IncV, PN->getType());
00979       rememberInstruction(IncV);
00980     }
00981   } else {
00982     IncV = useSubtract ?
00983       Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") :
00984       Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next");
00985     rememberInstruction(IncV);
00986   }
00987   return IncV;
00988 }
00989 
00990 /// \brief Hoist the addrec instruction chain rooted in the loop phi above the
00991 /// position. This routine assumes that this is possible (has been checked).
00992 static void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
00993                            Instruction *Pos, PHINode *LoopPhi) {
00994   do {
00995     if (DT->dominates(InstToHoist, Pos))
00996       break;
00997     // Make sure the increment is where we want it. But don't move it
00998     // down past a potential existing post-inc user.
00999     InstToHoist->moveBefore(Pos);
01000     Pos = InstToHoist;
01001     InstToHoist = cast<Instruction>(InstToHoist->getOperand(0));
01002   } while (InstToHoist != LoopPhi);
01003 }
01004 
01005 /// \brief Check whether we can cheaply express the requested SCEV in terms of
01006 /// the available PHI SCEV by truncation and/or inversion of the step.
01007 static bool canBeCheaplyTransformed(ScalarEvolution &SE,
01008                                     const SCEVAddRecExpr *Phi,
01009                                     const SCEVAddRecExpr *Requested,
01010                                     bool &InvertStep) {
01011   Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType());
01012   Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType());
01013 
01014   if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth())
01015     return false;
01016 
01017   // Try truncate it if necessary.
01018   Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy));
01019   if (!Phi)
01020     return false;
01021 
01022   // Check whether truncation will help.
01023   if (Phi == Requested) {
01024     InvertStep = false;
01025     return true;
01026   }
01027 
01028   // Check whether inverting will help: {R,+,-1} == R - {0,+,1}.
01029   if (SE.getAddExpr(Requested->getStart(),
01030                     SE.getNegativeSCEV(Requested)) == Phi) {
01031     InvertStep = true;
01032     return true;
01033   }
01034 
01035   return false;
01036 }
01037 
01038 static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
01039   if (!isa<IntegerType>(AR->getType()))
01040     return false;
01041 
01042   unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
01043   Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
01044   const SCEV *Step = AR->getStepRecurrence(SE);
01045   const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy),
01046                                             SE.getSignExtendExpr(AR, WideTy));
01047   const SCEV *ExtendAfterOp =
01048     SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy);
01049   return ExtendAfterOp == OpAfterExtend;
01050 }
01051 
01052 static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
01053   if (!isa<IntegerType>(AR->getType()))
01054     return false;
01055 
01056   unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
01057   Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
01058   const SCEV *Step = AR->getStepRecurrence(SE);
01059   const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy),
01060                                             SE.getZeroExtendExpr(AR, WideTy));
01061   const SCEV *ExtendAfterOp =
01062     SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy);
01063   return ExtendAfterOp == OpAfterExtend;
01064 }
01065 
01066 /// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand
01067 /// the base addrec, which is the addrec without any non-loop-dominating
01068 /// values, and return the PHI.
01069 PHINode *
01070 SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
01071                                         const Loop *L,
01072                                         Type *ExpandTy,
01073                                         Type *IntTy,
01074                                         Type *&TruncTy,
01075                                         bool &InvertStep) {
01076   assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position");
01077 
01078   // Reuse a previously-inserted PHI, if present.
01079   BasicBlock *LatchBlock = L->getLoopLatch();
01080   if (LatchBlock) {
01081     PHINode *AddRecPhiMatch = nullptr;
01082     Instruction *IncV = nullptr;
01083     TruncTy = nullptr;
01084     InvertStep = false;
01085 
01086     // Only try partially matching scevs that need truncation and/or
01087     // step-inversion if we know this loop is outside the current loop.
01088     bool TryNonMatchingSCEV =
01089         IVIncInsertLoop &&
01090         SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
01091 
01092     for (auto &I : *L->getHeader()) {
01093       auto *PN = dyn_cast<PHINode>(&I);
01094       if (!PN || !SE.isSCEVable(PN->getType()))
01095         continue;
01096 
01097       const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(PN));
01098       if (!PhiSCEV)
01099         continue;
01100 
01101       bool IsMatchingSCEV = PhiSCEV == Normalized;
01102       // We only handle truncation and inversion of phi recurrences for the
01103       // expanded expression if the expanded expression's loop dominates the
01104       // loop we insert to. Check now, so we can bail out early.
01105       if (!IsMatchingSCEV && !TryNonMatchingSCEV)
01106           continue;
01107 
01108       Instruction *TempIncV =
01109           cast<Instruction>(PN->getIncomingValueForBlock(LatchBlock));
01110 
01111       // Check whether we can reuse this PHI node.
01112       if (LSRMode) {
01113         if (!isExpandedAddRecExprPHI(PN, TempIncV, L))
01114           continue;
01115         if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos))
01116           continue;
01117       } else {
01118         if (!isNormalAddRecExprPHI(PN, TempIncV, L))
01119           continue;
01120       }
01121 
01122       // Stop if we have found an exact match SCEV.
01123       if (IsMatchingSCEV) {
01124         IncV = TempIncV;
01125         TruncTy = nullptr;
01126         InvertStep = false;
01127         AddRecPhiMatch = PN;
01128         break;
01129       }
01130 
01131       // Try whether the phi can be translated into the requested form
01132       // (truncated and/or offset by a constant).
01133       if ((!TruncTy || InvertStep) &&
01134           canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) {
01135         // Record the phi node. But don't stop we might find an exact match
01136         // later.
01137         AddRecPhiMatch = PN;
01138         IncV = TempIncV;
01139         TruncTy = SE.getEffectiveSCEVType(Normalized->getType());
01140       }
01141     }
01142 
01143     if (AddRecPhiMatch) {
01144       // Potentially, move the increment. We have made sure in
01145       // isExpandedAddRecExprPHI or hoistIVInc that this is possible.
01146       if (L == IVIncInsertLoop)
01147         hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch);
01148 
01149       // Ok, the add recurrence looks usable.
01150       // Remember this PHI, even in post-inc mode.
01151       InsertedValues.insert(AddRecPhiMatch);
01152       // Remember the increment.
01153       rememberInstruction(IncV);
01154       return AddRecPhiMatch;
01155     }
01156   }
01157 
01158   // Save the original insertion point so we can restore it when we're done.
01159   BuilderType::InsertPointGuard Guard(Builder);
01160 
01161   // Another AddRec may need to be recursively expanded below. For example, if
01162   // this AddRec is quadratic, the StepV may itself be an AddRec in this
01163   // loop. Remove this loop from the PostIncLoops set before expanding such
01164   // AddRecs. Otherwise, we cannot find a valid position for the step
01165   // (i.e. StepV can never dominate its loop header).  Ideally, we could do
01166   // SavedIncLoops.swap(PostIncLoops), but we generally have a single element,
01167   // so it's not worth implementing SmallPtrSet::swap.
01168   PostIncLoopSet SavedPostIncLoops = PostIncLoops;
01169   PostIncLoops.clear();
01170 
01171   // Expand code for the start value.
01172   Value *StartV =
01173       expandCodeFor(Normalized->getStart(), ExpandTy, &L->getHeader()->front());
01174 
01175   // StartV must be hoisted into L's preheader to dominate the new phi.
01176   assert(!isa<Instruction>(StartV) ||
01177          SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),
01178                                  L->getHeader()));
01179 
01180   // Expand code for the step value. Do this before creating the PHI so that PHI
01181   // reuse code doesn't see an incomplete PHI.
01182   const SCEV *Step = Normalized->getStepRecurrence(SE);
01183   // If the stride is negative, insert a sub instead of an add for the increment
01184   // (unless it's a constant, because subtracts of constants are canonicalized
01185   // to adds).
01186   bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
01187   if (useSubtract)
01188     Step = SE.getNegativeSCEV(Step);
01189   // Expand the step somewhere that dominates the loop header.
01190   Value *StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front());
01191 
01192   // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if
01193   // we actually do emit an addition.  It does not apply if we emit a
01194   // subtraction.
01195   bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized);
01196   bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized);
01197 
01198   // Create the PHI.
01199   BasicBlock *Header = L->getHeader();
01200   Builder.SetInsertPoint(Header, Header->begin());
01201   pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
01202   PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE),
01203                                   Twine(IVName) + ".iv");
01204   rememberInstruction(PN);
01205 
01206   // Create the step instructions and populate the PHI.
01207   for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
01208     BasicBlock *Pred = *HPI;
01209 
01210     // Add a start value.
01211     if (!L->contains(Pred)) {
01212       PN->addIncoming(StartV, Pred);
01213       continue;
01214     }
01215 
01216     // Create a step value and add it to the PHI.
01217     // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the
01218     // instructions at IVIncInsertPos.
01219     Instruction *InsertPos = L == IVIncInsertLoop ?
01220       IVIncInsertPos : Pred->getTerminator();
01221     Builder.SetInsertPoint(InsertPos);
01222     Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
01223 
01224     if (isa<OverflowingBinaryOperator>(IncV)) {
01225       if (IncrementIsNUW)
01226         cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
01227       if (IncrementIsNSW)
01228         cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
01229     }
01230     PN->addIncoming(IncV, Pred);
01231   }
01232 
01233   // After expanding subexpressions, restore the PostIncLoops set so the caller
01234   // can ensure that IVIncrement dominates the current uses.
01235   PostIncLoops = SavedPostIncLoops;
01236 
01237   // Remember this PHI, even in post-inc mode.
01238   InsertedValues.insert(PN);
01239 
01240   return PN;
01241 }
01242 
01243 Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
01244   Type *STy = S->getType();
01245   Type *IntTy = SE.getEffectiveSCEVType(STy);
01246   const Loop *L = S->getLoop();
01247 
01248   // Determine a normalized form of this expression, which is the expression
01249   // before any post-inc adjustment is made.
01250   const SCEVAddRecExpr *Normalized = S;
01251   if (PostIncLoops.count(L)) {
01252     PostIncLoopSet Loops;
01253     Loops.insert(L);
01254     Normalized = cast<SCEVAddRecExpr>(TransformForPostIncUse(
01255         Normalize, S, nullptr, nullptr, Loops, SE, SE.DT));
01256   }
01257 
01258   // Strip off any non-loop-dominating component from the addrec start.
01259   const SCEV *Start = Normalized->getStart();
01260   const SCEV *PostLoopOffset = nullptr;
01261   if (!SE.properlyDominates(Start, L->getHeader())) {
01262     PostLoopOffset = Start;
01263     Start = SE.getConstant(Normalized->getType(), 0);
01264     Normalized = cast<SCEVAddRecExpr>(
01265       SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE),
01266                        Normalized->getLoop(),
01267                        Normalized->getNoWrapFlags(SCEV::FlagNW)));
01268   }
01269 
01270   // Strip off any non-loop-dominating component from the addrec step.
01271   const SCEV *Step = Normalized->getStepRecurrence(SE);
01272   const SCEV *PostLoopScale = nullptr;
01273   if (!SE.dominates(Step, L->getHeader())) {
01274     PostLoopScale = Step;
01275     Step = SE.getConstant(Normalized->getType(), 1);
01276     Normalized =
01277       cast<SCEVAddRecExpr>(SE.getAddRecExpr(
01278                              Start, Step, Normalized->getLoop(),
01279                              Normalized->getNoWrapFlags(SCEV::FlagNW)));
01280   }
01281 
01282   // Expand the core addrec. If we need post-loop scaling, force it to
01283   // expand to an integer type to avoid the need for additional casting.
01284   Type *ExpandTy = PostLoopScale ? IntTy : STy;
01285   // In some cases, we decide to reuse an existing phi node but need to truncate
01286   // it and/or invert the step.
01287   Type *TruncTy = nullptr;
01288   bool InvertStep = false;
01289   PHINode *PN = getAddRecExprPHILiterally(Normalized, L, ExpandTy, IntTy,
01290                                           TruncTy, InvertStep);
01291 
01292   // Accommodate post-inc mode, if necessary.
01293   Value *Result;
01294   if (!PostIncLoops.count(L))
01295     Result = PN;
01296   else {
01297     // In PostInc mode, use the post-incremented value.
01298     BasicBlock *LatchBlock = L->getLoopLatch();
01299     assert(LatchBlock && "PostInc mode requires a unique loop latch!");
01300     Result = PN->getIncomingValueForBlock(LatchBlock);
01301 
01302     // For an expansion to use the postinc form, the client must call
01303     // expandCodeFor with an InsertPoint that is either outside the PostIncLoop
01304     // or dominated by IVIncInsertPos.
01305     if (isa<Instruction>(Result) &&
01306         !SE.DT.dominates(cast<Instruction>(Result),
01307                          &*Builder.GetInsertPoint())) {
01308       // The induction variable's postinc expansion does not dominate this use.
01309       // IVUsers tries to prevent this case, so it is rare. However, it can
01310       // happen when an IVUser outside the loop is not dominated by the latch
01311       // block. Adjusting IVIncInsertPos before expansion begins cannot handle
01312       // all cases. Consider a phi outide whose operand is replaced during
01313       // expansion with the value of the postinc user. Without fundamentally
01314       // changing the way postinc users are tracked, the only remedy is
01315       // inserting an extra IV increment. StepV might fold into PostLoopOffset,
01316       // but hopefully expandCodeFor handles that.
01317       bool useSubtract =
01318         !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
01319       if (useSubtract)
01320         Step = SE.getNegativeSCEV(Step);
01321       Value *StepV;
01322       {
01323         // Expand the step somewhere that dominates the loop header.
01324         BuilderType::InsertPointGuard Guard(Builder);
01325         StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front());
01326       }
01327       Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
01328     }
01329   }
01330 
01331   // We have decided to reuse an induction variable of a dominating loop. Apply
01332   // truncation and/or invertion of the step.
01333   if (TruncTy) {
01334     Type *ResTy = Result->getType();
01335     // Normalize the result type.
01336     if (ResTy != SE.getEffectiveSCEVType(ResTy))
01337       Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy));
01338     // Truncate the result.
01339     if (TruncTy != Result->getType()) {
01340       Result = Builder.CreateTrunc(Result, TruncTy);
01341       rememberInstruction(Result);
01342     }
01343     // Invert the result.
01344     if (InvertStep) {
01345       Result = Builder.CreateSub(expandCodeFor(Normalized->getStart(), TruncTy),
01346                                  Result);
01347       rememberInstruction(Result);
01348     }
01349   }
01350 
01351   // Re-apply any non-loop-dominating scale.
01352   if (PostLoopScale) {
01353     assert(S->isAffine() && "Can't linearly scale non-affine recurrences.");
01354     Result = InsertNoopCastOfTo(Result, IntTy);
01355     Result = Builder.CreateMul(Result,
01356                                expandCodeFor(PostLoopScale, IntTy));
01357     rememberInstruction(Result);
01358   }
01359 
01360   // Re-apply any non-loop-dominating offset.
01361   if (PostLoopOffset) {
01362     if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
01363       const SCEV *const OffsetArray[1] = { PostLoopOffset };
01364       Result = expandAddToGEP(OffsetArray, OffsetArray+1, PTy, IntTy, Result);
01365     } else {
01366       Result = InsertNoopCastOfTo(Result, IntTy);
01367       Result = Builder.CreateAdd(Result,
01368                                  expandCodeFor(PostLoopOffset, IntTy));
01369       rememberInstruction(Result);
01370     }
01371   }
01372 
01373   return Result;
01374 }
01375 
01376 Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
01377   if (!CanonicalMode) return expandAddRecExprLiterally(S);
01378 
01379   Type *Ty = SE.getEffectiveSCEVType(S->getType());
01380   const Loop *L = S->getLoop();
01381 
01382   // First check for an existing canonical IV in a suitable type.
01383   PHINode *CanonicalIV = nullptr;
01384   if (PHINode *PN = L->getCanonicalInductionVariable())
01385     if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))
01386       CanonicalIV = PN;
01387 
01388   // Rewrite an AddRec in terms of the canonical induction variable, if
01389   // its type is more narrow.
01390   if (CanonicalIV &&
01391       SE.getTypeSizeInBits(CanonicalIV->getType()) >
01392       SE.getTypeSizeInBits(Ty)) {
01393     SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
01394     for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
01395       NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
01396     Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
01397                                        S->getNoWrapFlags(SCEV::FlagNW)));
01398     BasicBlock::iterator NewInsertPt =
01399         findInsertPointAfter(cast<Instruction>(V), Builder.GetInsertBlock());
01400     V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
01401                       &*NewInsertPt);
01402     return V;
01403   }
01404 
01405   // {X,+,F} --> X + {0,+,F}
01406   if (!S->getStart()->isZero()) {
01407     SmallVector<const SCEV *, 4> NewOps(S->op_begin(), S->op_end());
01408     NewOps[0] = SE.getConstant(Ty, 0);
01409     const SCEV *Rest = SE.getAddRecExpr(NewOps, L,
01410                                         S->getNoWrapFlags(SCEV::FlagNW));
01411 
01412     // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the
01413     // comments on expandAddToGEP for details.
01414     const SCEV *Base = S->getStart();
01415     const SCEV *RestArray[1] = { Rest };
01416     // Dig into the expression to find the pointer base for a GEP.
01417     ExposePointerBase(Base, RestArray[0], SE);
01418     // If we found a pointer, expand the AddRec with a GEP.
01419     if (PointerType *PTy = dyn_cast<PointerType>(Base->getType())) {
01420       // Make sure the Base isn't something exotic, such as a multiplied
01421       // or divided pointer value. In those cases, the result type isn't
01422       // actually a pointer type.
01423       if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) {
01424         Value *StartV = expand(Base);
01425         assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!");
01426         return expandAddToGEP(RestArray, RestArray+1, PTy, Ty, StartV);
01427       }
01428     }
01429 
01430     // Just do a normal add. Pre-expand the operands to suppress folding.
01431     return expand(SE.getAddExpr(SE.getUnknown(expand(S->getStart())),
01432                                 SE.getUnknown(expand(Rest))));
01433   }
01434 
01435   // If we don't yet have a canonical IV, create one.
01436   if (!CanonicalIV) {
01437     // Create and insert the PHI node for the induction variable in the
01438     // specified loop.
01439     BasicBlock *Header = L->getHeader();
01440     pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
01441     CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar",
01442                                   &Header->front());
01443     rememberInstruction(CanonicalIV);
01444 
01445     SmallSet<BasicBlock *, 4> PredSeen;
01446     Constant *One = ConstantInt::get(Ty, 1);
01447     for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
01448       BasicBlock *HP = *HPI;
01449       if (!PredSeen.insert(HP).second) {
01450         // There must be an incoming value for each predecessor, even the
01451         // duplicates!
01452         CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP);
01453         continue;
01454       }
01455 
01456       if (L->contains(HP)) {
01457         // Insert a unit add instruction right before the terminator
01458         // corresponding to the back-edge.
01459         Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One,
01460                                                      "indvar.next",
01461                                                      HP->getTerminator());
01462         Add->setDebugLoc(HP->getTerminator()->getDebugLoc());
01463         rememberInstruction(Add);
01464         CanonicalIV->addIncoming(Add, HP);
01465       } else {
01466         CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP);
01467       }
01468     }
01469   }
01470 
01471   // {0,+,1} --> Insert a canonical induction variable into the loop!
01472   if (S->isAffine() && S->getOperand(1)->isOne()) {
01473     assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&
01474            "IVs with types different from the canonical IV should "
01475            "already have been handled!");
01476     return CanonicalIV;
01477   }
01478 
01479   // {0,+,F} --> {0,+,1} * F
01480 
01481   // If this is a simple linear addrec, emit it now as a special case.
01482   if (S->isAffine())    // {0,+,F} --> i*F
01483     return
01484       expand(SE.getTruncateOrNoop(
01485         SE.getMulExpr(SE.getUnknown(CanonicalIV),
01486                       SE.getNoopOrAnyExtend(S->getOperand(1),
01487                                             CanonicalIV->getType())),
01488         Ty));
01489 
01490   // If this is a chain of recurrences, turn it into a closed form, using the
01491   // folders, then expandCodeFor the closed form.  This allows the folders to
01492   // simplify the expression without having to build a bunch of special code
01493   // into this folder.
01494   const SCEV *IH = SE.getUnknown(CanonicalIV);   // Get I as a "symbolic" SCEV.
01495 
01496   // Promote S up to the canonical IV type, if the cast is foldable.
01497   const SCEV *NewS = S;
01498   const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType());
01499   if (isa<SCEVAddRecExpr>(Ext))
01500     NewS = Ext;
01501 
01502   const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
01503   //cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
01504 
01505   // Truncate the result down to the original type, if needed.
01506   const SCEV *T = SE.getTruncateOrNoop(V, Ty);
01507   return expand(T);
01508 }
01509 
01510 Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {
01511   Type *Ty = SE.getEffectiveSCEVType(S->getType());
01512   Value *V = expandCodeFor(S->getOperand(),
01513                            SE.getEffectiveSCEVType(S->getOperand()->getType()));
01514   Value *I = Builder.CreateTrunc(V, Ty);
01515   rememberInstruction(I);
01516   return I;
01517 }
01518 
01519 Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {
01520   Type *Ty = SE.getEffectiveSCEVType(S->getType());
01521   Value *V = expandCodeFor(S->getOperand(),
01522                            SE.getEffectiveSCEVType(S->getOperand()->getType()));
01523   Value *I = Builder.CreateZExt(V, Ty);
01524   rememberInstruction(I);
01525   return I;
01526 }
01527 
01528 Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
01529   Type *Ty = SE.getEffectiveSCEVType(S->getType());
01530   Value *V = expandCodeFor(S->getOperand(),
01531                            SE.getEffectiveSCEVType(S->getOperand()->getType()));
01532   Value *I = Builder.CreateSExt(V, Ty);
01533   rememberInstruction(I);
01534   return I;
01535 }
01536 
01537 Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
01538   Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
01539   Type *Ty = LHS->getType();
01540   for (int i = S->getNumOperands()-2; i >= 0; --i) {
01541     // In the case of mixed integer and pointer types, do the
01542     // rest of the comparisons as integer.
01543     if (S->getOperand(i)->getType() != Ty) {
01544       Ty = SE.getEffectiveSCEVType(Ty);
01545       LHS = InsertNoopCastOfTo(LHS, Ty);
01546     }
01547     Value *RHS = expandCodeFor(S->getOperand(i), Ty);
01548     Value *ICmp = Builder.CreateICmpSGT(LHS, RHS);
01549     rememberInstruction(ICmp);
01550     Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax");
01551     rememberInstruction(Sel);
01552     LHS = Sel;
01553   }
01554   // In the case of mixed integer and pointer types, cast the
01555   // final result back to the pointer type.
01556   if (LHS->getType() != S->getType())
01557     LHS = InsertNoopCastOfTo(LHS, S->getType());
01558   return LHS;
01559 }
01560 
01561 Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
01562   Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
01563   Type *Ty = LHS->getType();
01564   for (int i = S->getNumOperands()-2; i >= 0; --i) {
01565     // In the case of mixed integer and pointer types, do the
01566     // rest of the comparisons as integer.
01567     if (S->getOperand(i)->getType() != Ty) {
01568       Ty = SE.getEffectiveSCEVType(Ty);
01569       LHS = InsertNoopCastOfTo(LHS, Ty);
01570     }
01571     Value *RHS = expandCodeFor(S->getOperand(i), Ty);
01572     Value *ICmp = Builder.CreateICmpUGT(LHS, RHS);
01573     rememberInstruction(ICmp);
01574     Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax");
01575     rememberInstruction(Sel);
01576     LHS = Sel;
01577   }
01578   // In the case of mixed integer and pointer types, cast the
01579   // final result back to the pointer type.
01580   if (LHS->getType() != S->getType())
01581     LHS = InsertNoopCastOfTo(LHS, S->getType());
01582   return LHS;
01583 }
01584 
01585 Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty,
01586                                    Instruction *IP) {
01587   assert(IP);
01588   Builder.SetInsertPoint(IP);
01589   return expandCodeFor(SH, Ty);
01590 }
01591 
01592 Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) {
01593   // Expand the code for this SCEV.
01594   Value *V = expand(SH);
01595   if (Ty) {
01596     assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&
01597            "non-trivial casts should be done with the SCEVs directly!");
01598     V = InsertNoopCastOfTo(V, Ty);
01599   }
01600   return V;
01601 }
01602 
01603 Value *SCEVExpander::expand(const SCEV *S) {
01604   // Compute an insertion point for this SCEV object. Hoist the instructions
01605   // as far out in the loop nest as possible.
01606   Instruction *InsertPt = &*Builder.GetInsertPoint();
01607   for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
01608        L = L->getParentLoop())
01609     if (SE.isLoopInvariant(S, L)) {
01610       if (!L) break;
01611       if (BasicBlock *Preheader = L->getLoopPreheader())
01612         InsertPt = Preheader->getTerminator();
01613       else {
01614         // LSR sets the insertion point for AddRec start/step values to the
01615         // block start to simplify value reuse, even though it's an invalid
01616         // position. SCEVExpander must correct for this in all cases.
01617         InsertPt = &*L->getHeader()->getFirstInsertionPt();
01618       }
01619     } else {
01620       // If the SCEV is computable at this level, insert it into the header
01621       // after the PHIs (and after any other instructions that we've inserted
01622       // there) so that it is guaranteed to dominate any user inside the loop.
01623       if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
01624         InsertPt = &*L->getHeader()->getFirstInsertionPt();
01625       while (InsertPt != Builder.GetInsertPoint()
01626              && (isInsertedInstruction(InsertPt)
01627                  || isa<DbgInfoIntrinsic>(InsertPt))) {
01628         InsertPt = &*std::next(InsertPt->getIterator());
01629       }
01630       break;
01631     }
01632 
01633   // Check to see if we already expanded this here.
01634   auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
01635   if (I != InsertedExpressions.end())
01636     return I->second;
01637 
01638   BuilderType::InsertPointGuard Guard(Builder);
01639   Builder.SetInsertPoint(InsertPt);
01640 
01641   // Expand the expression into instructions.
01642   Value *V = visit(S);
01643 
01644   // Remember the expanded value for this SCEV at this location.
01645   //
01646   // This is independent of PostIncLoops. The mapped value simply materializes
01647   // the expression at this insertion point. If the mapped value happened to be
01648   // a postinc expansion, it could be reused by a non-postinc user, but only if
01649   // its insertion point was already at the head of the loop.
01650   InsertedExpressions[std::make_pair(S, InsertPt)] = V;
01651   return V;
01652 }
01653 
01654 void SCEVExpander::rememberInstruction(Value *I) {
01655   if (!PostIncLoops.empty())
01656     InsertedPostIncValues.insert(I);
01657   else
01658     InsertedValues.insert(I);
01659 }
01660 
01661 /// getOrInsertCanonicalInductionVariable - This method returns the
01662 /// canonical induction variable of the specified type for the specified
01663 /// loop (inserting one if there is none).  A canonical induction variable
01664 /// starts at zero and steps by one on each iteration.
01665 PHINode *
01666 SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L,
01667                                                     Type *Ty) {
01668   assert(Ty->isIntegerTy() && "Can only insert integer induction variables!");
01669 
01670   // Build a SCEV for {0,+,1}<L>.
01671   // Conservatively use FlagAnyWrap for now.
01672   const SCEV *H = SE.getAddRecExpr(SE.getConstant(Ty, 0),
01673                                    SE.getConstant(Ty, 1), L, SCEV::FlagAnyWrap);
01674 
01675   // Emit code for it.
01676   BuilderType::InsertPointGuard Guard(Builder);
01677   PHINode *V =
01678       cast<PHINode>(expandCodeFor(H, nullptr, &L->getHeader()->front()));
01679 
01680   return V;
01681 }
01682 
01683 /// replaceCongruentIVs - Check for congruent phis in this loop header and
01684 /// replace them with their most canonical representative. Return the number of
01685 /// phis eliminated.
01686 ///
01687 /// This does not depend on any SCEVExpander state but should be used in
01688 /// the same context that SCEVExpander is used.
01689 unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
01690                                            SmallVectorImpl<WeakVH> &DeadInsts,
01691                                            const TargetTransformInfo *TTI) {
01692   // Find integer phis in order of increasing width.
01693   SmallVector<PHINode*, 8> Phis;
01694   for (auto &I : *L->getHeader()) {
01695     if (auto *PN = dyn_cast<PHINode>(&I))
01696       Phis.push_back(PN);
01697     else
01698       break;
01699   }
01700 
01701   if (TTI)
01702     std::sort(Phis.begin(), Phis.end(), [](Value *LHS, Value *RHS) {
01703       // Put pointers at the back and make sure pointer < pointer = false.
01704       if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
01705         return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();
01706       return RHS->getType()->getPrimitiveSizeInBits() <
01707              LHS->getType()->getPrimitiveSizeInBits();
01708     });
01709 
01710   unsigned NumElim = 0;
01711   DenseMap<const SCEV *, PHINode *> ExprToIVMap;
01712   // Process phis from wide to narrow. Map wide phis to their truncation
01713   // so narrow phis can reuse them.
01714   for (PHINode *Phi : Phis) {
01715     auto SimplifyPHINode = [&](PHINode *PN) -> Value * {
01716       if (Value *V = SimplifyInstruction(PN, DL, &SE.TLI, &SE.DT, &SE.AC))
01717         return V;
01718       if (!SE.isSCEVable(PN->getType()))
01719         return nullptr;
01720       auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));
01721       if (!Const)
01722         return nullptr;
01723       return Const->getValue();
01724     };
01725 
01726     // Fold constant phis. They may be congruent to other constant phis and
01727     // would confuse the logic below that expects proper IVs.
01728     if (Value *V = SimplifyPHINode(Phi)) {
01729       if (V->getType() != Phi->getType())
01730         continue;
01731       Phi->replaceAllUsesWith(V);
01732       DeadInsts.emplace_back(Phi);
01733       ++NumElim;
01734       DEBUG_WITH_TYPE(DebugType, dbgs()
01735                       << "INDVARS: Eliminated constant iv: " << *Phi << '\n');
01736       continue;
01737     }
01738 
01739     if (!SE.isSCEVable(Phi->getType()))
01740       continue;
01741 
01742     PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
01743     if (!OrigPhiRef) {
01744       OrigPhiRef = Phi;
01745       if (Phi->getType()->isIntegerTy() && TTI
01746           && TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
01747         // This phi can be freely truncated to the narrowest phi type. Map the
01748         // truncated expression to it so it will be reused for narrow types.
01749         const SCEV *TruncExpr =
01750           SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType());
01751         ExprToIVMap[TruncExpr] = Phi;
01752       }
01753       continue;
01754     }
01755 
01756     // Replacing a pointer phi with an integer phi or vice-versa doesn't make
01757     // sense.
01758     if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy())
01759       continue;
01760 
01761     if (BasicBlock *LatchBlock = L->getLoopLatch()) {
01762       Instruction *OrigInc =
01763         cast<Instruction>(OrigPhiRef->getIncomingValueForBlock(LatchBlock));
01764       Instruction *IsomorphicInc =
01765         cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
01766 
01767       // If this phi has the same width but is more canonical, replace the
01768       // original with it. As part of the "more canonical" determination,
01769       // respect a prior decision to use an IV chain.
01770       if (OrigPhiRef->getType() == Phi->getType()
01771           && !(ChainedPhis.count(Phi)
01772                || isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L))
01773           && (ChainedPhis.count(Phi)
01774               || isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
01775         std::swap(OrigPhiRef, Phi);
01776         std::swap(OrigInc, IsomorphicInc);
01777       }
01778       // Replacing the congruent phi is sufficient because acyclic redundancy
01779       // elimination, CSE/GVN, should handle the rest. However, once SCEV proves
01780       // that a phi is congruent, it's often the head of an IV user cycle that
01781       // is isomorphic with the original phi. It's worth eagerly cleaning up the
01782       // common case of a single IV increment so that DeleteDeadPHIs can remove
01783       // cycles that had postinc uses.
01784       const SCEV *TruncExpr = SE.getTruncateOrNoop(SE.getSCEV(OrigInc),
01785                                                    IsomorphicInc->getType());
01786       if (OrigInc != IsomorphicInc
01787           && TruncExpr == SE.getSCEV(IsomorphicInc)
01788           && ((isa<PHINode>(OrigInc) && isa<PHINode>(IsomorphicInc))
01789               || hoistIVInc(OrigInc, IsomorphicInc))) {
01790         DEBUG_WITH_TYPE(DebugType, dbgs()
01791                         << "INDVARS: Eliminated congruent iv.inc: "
01792                         << *IsomorphicInc << '\n');
01793         Value *NewInc = OrigInc;
01794         if (OrigInc->getType() != IsomorphicInc->getType()) {
01795           Instruction *IP = nullptr;
01796           if (PHINode *PN = dyn_cast<PHINode>(OrigInc))
01797             IP = &*PN->getParent()->getFirstInsertionPt();
01798           else
01799             IP = OrigInc->getNextNode();
01800 
01801           IRBuilder<> Builder(IP);
01802           Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc());
01803           NewInc = Builder.
01804             CreateTruncOrBitCast(OrigInc, IsomorphicInc->getType(), IVName);
01805         }
01806         IsomorphicInc->replaceAllUsesWith(NewInc);
01807         DeadInsts.emplace_back(IsomorphicInc);
01808       }
01809     }
01810     DEBUG_WITH_TYPE(DebugType, dbgs()
01811                     << "INDVARS: Eliminated congruent iv: " << *Phi << '\n');
01812     ++NumElim;
01813     Value *NewIV = OrigPhiRef;
01814     if (OrigPhiRef->getType() != Phi->getType()) {
01815       IRBuilder<> Builder(&*L->getHeader()->getFirstInsertionPt());
01816       Builder.SetCurrentDebugLocation(Phi->getDebugLoc());
01817       NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);
01818     }
01819     Phi->replaceAllUsesWith(NewIV);
01820     DeadInsts.emplace_back(Phi);
01821   }
01822   return NumElim;
01823 }
01824 
01825 Value *SCEVExpander::findExistingExpansion(const SCEV *S,
01826                                            const Instruction *At, Loop *L) {
01827   using namespace llvm::PatternMatch;
01828 
01829   SmallVector<BasicBlock *, 4> ExitingBlocks;
01830   L->getExitingBlocks(ExitingBlocks);
01831 
01832   // Look for suitable value in simple conditions at the loop exits.
01833   for (BasicBlock *BB : ExitingBlocks) {
01834     ICmpInst::Predicate Pred;
01835     Instruction *LHS, *RHS;
01836     BasicBlock *TrueBB, *FalseBB;
01837 
01838     if (!match(BB->getTerminator(),
01839                m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
01840                     TrueBB, FalseBB)))
01841       continue;
01842 
01843     if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
01844       return LHS;
01845 
01846     if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
01847       return RHS;
01848   }
01849 
01850   // There is potential to make this significantly smarter, but this simple
01851   // heuristic already gets some interesting cases.
01852 
01853   // Can not find suitable value.
01854   return nullptr;
01855 }
01856 
01857 bool SCEVExpander::isHighCostExpansionHelper(
01858     const SCEV *S, Loop *L, const Instruction *At,
01859     SmallPtrSetImpl<const SCEV *> &Processed) {
01860 
01861   // If we can find an existing value for this scev avaliable at the point "At"
01862   // then consider the expression cheap.
01863   if (At && findExistingExpansion(S, At, L) != nullptr)
01864     return false;
01865 
01866   // Zero/One operand expressions
01867   switch (S->getSCEVType()) {
01868   case scUnknown:
01869   case scConstant:
01870     return false;
01871   case scTruncate:
01872     return isHighCostExpansionHelper(cast<SCEVTruncateExpr>(S)->getOperand(),
01873                                      L, At, Processed);
01874   case scZeroExtend:
01875     return isHighCostExpansionHelper(cast<SCEVZeroExtendExpr>(S)->getOperand(),
01876                                      L, At, Processed);
01877   case scSignExtend:
01878     return isHighCostExpansionHelper(cast<SCEVSignExtendExpr>(S)->getOperand(),
01879                                      L, At, Processed);
01880   }
01881 
01882   if (!Processed.insert(S).second)
01883     return false;
01884 
01885   if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
01886     // If the divisor is a power of two and the SCEV type fits in a native
01887     // integer, consider the division cheap irrespective of whether it occurs in
01888     // the user code since it can be lowered into a right shift.
01889     if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS()))
01890       if (SC->getAPInt().isPowerOf2()) {
01891         const DataLayout &DL =
01892             L->getHeader()->getParent()->getParent()->getDataLayout();
01893         unsigned Width = cast<IntegerType>(UDivExpr->getType())->getBitWidth();
01894         return DL.isIllegalInteger(Width);
01895       }
01896 
01897     // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
01898     // HowManyLessThans produced to compute a precise expression, rather than a
01899     // UDiv from the user's code. If we can't find a UDiv in the code with some
01900     // simple searching, assume the former consider UDivExpr expensive to
01901     // compute.
01902     BasicBlock *ExitingBB = L->getExitingBlock();
01903     if (!ExitingBB)
01904       return true;
01905 
01906     // At the beginning of this function we already tried to find existing value
01907     // for plain 'S'. Now try to lookup 'S + 1' since it is common pattern
01908     // involving division. This is just a simple search heuristic.
01909     if (!At)
01910       At = &ExitingBB->back();
01911     if (!findExistingExpansion(
01912             SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L))
01913       return true;
01914   }
01915 
01916   // HowManyLessThans uses a Max expression whenever the loop is not guarded by
01917   // the exit condition.
01918   if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S))
01919     return true;
01920 
01921   // Recurse past nary expressions, which commonly occur in the
01922   // BackedgeTakenCount. They may already exist in program code, and if not,
01923   // they are not too expensive rematerialize.
01924   if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(S)) {
01925     for (auto *Op : NAry->operands())
01926       if (isHighCostExpansionHelper(Op, L, At, Processed))
01927         return true;
01928   }
01929 
01930   // If we haven't recognized an expensive SCEV pattern, assume it's an
01931   // expression produced by program code.
01932   return false;
01933 }
01934 
01935 Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred,
01936                                             Instruction *IP) {
01937   assert(IP);
01938   switch (Pred->getKind()) {
01939   case SCEVPredicate::P_Union:
01940     return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);
01941   case SCEVPredicate::P_Equal:
01942     return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP);
01943   }
01944   llvm_unreachable("Unknown SCEV predicate type");
01945 }
01946 
01947 Value *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred,
01948                                           Instruction *IP) {
01949   Value *Expr0 = expandCodeFor(Pred->getLHS(), Pred->getLHS()->getType(), IP);
01950   Value *Expr1 = expandCodeFor(Pred->getRHS(), Pred->getRHS()->getType(), IP);
01951 
01952   Builder.SetInsertPoint(IP);
01953   auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
01954   return I;
01955 }
01956 
01957 Value *SCEVExpander::expandUnionPredicate(const SCEVUnionPredicate *Union,
01958                                           Instruction *IP) {
01959   auto *BoolType = IntegerType::get(IP->getContext(), 1);
01960   Value *Check = ConstantInt::getNullValue(BoolType);
01961 
01962   // Loop over all checks in this set.
01963   for (auto Pred : Union->getPredicates()) {
01964     auto *NextCheck = expandCodeForPredicate(Pred, IP);
01965     Builder.SetInsertPoint(IP);
01966     Check = Builder.CreateOr(Check, NextCheck);
01967   }
01968 
01969   return Check;
01970 }
01971 
01972 namespace {
01973 // Search for a SCEV subexpression that is not safe to expand.  Any expression
01974 // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
01975 // UDiv expressions. We don't know if the UDiv is derived from an IR divide
01976 // instruction, but the important thing is that we prove the denominator is
01977 // nonzero before expansion.
01978 //
01979 // IVUsers already checks that IV-derived expressions are safe. So this check is
01980 // only needed when the expression includes some subexpression that is not IV
01981 // derived.
01982 //
01983 // Currently, we only allow division by a nonzero constant here. If this is
01984 // inadequate, we could easily allow division by SCEVUnknown by using
01985 // ValueTracking to check isKnownNonZero().
01986 //
01987 // We cannot generally expand recurrences unless the step dominates the loop
01988 // header. The expander handles the special case of affine recurrences by
01989 // scaling the recurrence outside the loop, but this technique isn't generally
01990 // applicable. Expanding a nested recurrence outside a loop requires computing
01991 // binomial coefficients. This could be done, but the recurrence has to be in a
01992 // perfectly reduced form, which can't be guaranteed.
01993 struct SCEVFindUnsafe {
01994   ScalarEvolution &SE;
01995   bool IsUnsafe;
01996 
01997   SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {}
01998 
01999   bool follow(const SCEV *S) {
02000     if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
02001       const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS());
02002       if (!SC || SC->getValue()->isZero()) {
02003         IsUnsafe = true;
02004         return false;
02005       }
02006     }
02007     if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
02008       const SCEV *Step = AR->getStepRecurrence(SE);
02009       if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
02010         IsUnsafe = true;
02011         return false;
02012       }
02013     }
02014     return true;
02015   }
02016   bool isDone() const { return IsUnsafe; }
02017 };
02018 }
02019 
02020 namespace llvm {
02021 bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) {
02022   SCEVFindUnsafe Search(SE);
02023   visitAll(S, Search);
02024   return !Search.IsUnsafe;
02025 }
02026 }