xref: /llvm-project/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp (revision b46c085d2b6d15873fb53718f0a70b3848e19e4a)
1 //===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis ------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains the implementation of the scalar evolution expander,
10 // which is used to generate the code corresponding to a given scalar evolution
11 // expression.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallSet.h"
18 #include "llvm/Analysis/InstructionSimplify.h"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/Analysis/TargetTransformInfo.h"
21 #include "llvm/IR/DataLayout.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/IR/IntrinsicInst.h"
24 #include "llvm/IR/LLVMContext.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/IR/PatternMatch.h"
27 #include "llvm/Support/CommandLine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include "llvm/Transforms/Utils/LoopUtils.h"
31 
32 using namespace llvm;
33 
34 cl::opt<unsigned> llvm::SCEVCheapExpansionBudget(
35     "scev-cheap-expansion-budget", cl::Hidden, cl::init(4),
36     cl::desc("When performing SCEV expansion only if it is cheap to do, this "
37              "controls the budget that is considered cheap (default = 4)"));
38 
39 using namespace PatternMatch;
40 
41 /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
42 /// reusing an existing cast if a suitable one (= dominating IP) exists, or
43 /// creating a new one.
44 Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,
45                                        Instruction::CastOps Op,
46                                        BasicBlock::iterator IP) {
47   // This function must be called with the builder having a valid insertion
48   // point. It doesn't need to be the actual IP where the uses of the returned
49   // cast will be added, but it must dominate such IP.
50   // We use this precondition to produce a cast that will dominate all its
51   // uses. In particular, this is crucial for the case where the builder's
52   // insertion point *is* the point where we were asked to put the cast.
53   // Since we don't know the builder's insertion point is actually
54   // where the uses will be added (only that it dominates it), we are
55   // not allowed to move it.
56   BasicBlock::iterator BIP = Builder.GetInsertPoint();
57 
58   Instruction *Ret = nullptr;
59 
60   // Check to see if there is already a cast!
61   for (User *U : V->users()) {
62     if (U->getType() != Ty)
63       continue;
64     CastInst *CI = dyn_cast<CastInst>(U);
65     if (!CI || CI->getOpcode() != Op)
66       continue;
67 
68     // Found a suitable cast that is at IP or comes before IP. Use it. Note that
69     // the cast must also properly dominate the Builder's insertion point.
70     if (IP->getParent() == CI->getParent() && &*BIP != CI &&
71         (&*IP == CI || CI->comesBefore(&*IP))) {
72       Ret = CI;
73       break;
74     }
75   }
76 
77   // Create a new cast.
78   if (!Ret) {
79     Ret = CastInst::Create(Op, V, Ty, V->getName(), &*IP);
80     rememberInstruction(Ret);
81   }
82 
83   // We assert at the end of the function since IP might point to an
84   // instruction with different dominance properties than a cast
85   // (an invoke for example) and not dominate BIP (but the cast does).
86   assert(SE.DT.dominates(Ret, &*BIP));
87 
88   return Ret;
89 }
90 
91 BasicBlock::iterator
92 SCEVExpander::findInsertPointAfter(Instruction *I, Instruction *MustDominate) {
93   BasicBlock::iterator IP = ++I->getIterator();
94   if (auto *II = dyn_cast<InvokeInst>(I))
95     IP = II->getNormalDest()->begin();
96 
97   while (isa<PHINode>(IP))
98     ++IP;
99 
100   if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {
101     ++IP;
102   } else if (isa<CatchSwitchInst>(IP)) {
103     IP = MustDominate->getParent()->getFirstInsertionPt();
104   } else {
105     assert(!IP->isEHPad() && "unexpected eh pad!");
106   }
107 
108   // Adjust insert point to be after instructions inserted by the expander, so
109   // we can re-use already inserted instructions. Avoid skipping past the
110   // original \p MustDominate, in case it is an inserted instruction.
111   while (isInsertedInstruction(&*IP) && &*IP != MustDominate)
112     ++IP;
113 
114   return IP;
115 }
116 
117 /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
118 /// which must be possible with a noop cast, doing what we can to share
119 /// the casts.
120 Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
121   Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false);
122   assert((Op == Instruction::BitCast ||
123           Op == Instruction::PtrToInt ||
124           Op == Instruction::IntToPtr) &&
125          "InsertNoopCastOfTo cannot perform non-noop casts!");
126   assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) &&
127          "InsertNoopCastOfTo cannot change sizes!");
128 
129   // inttoptr only works for integral pointers. For non-integral pointers, we
130   // can create a GEP on i8* null  with the integral value as index. Note that
131   // it is safe to use GEP of null instead of inttoptr here, because only
132   // expressions already based on a GEP of null should be converted to pointers
133   // during expansion.
134   if (Op == Instruction::IntToPtr) {
135     auto *PtrTy = cast<PointerType>(Ty);
136     if (DL.isNonIntegralPointerType(PtrTy)) {
137       auto *Int8PtrTy = Builder.getInt8PtrTy(PtrTy->getAddressSpace());
138       assert(DL.getTypeAllocSize(Int8PtrTy->getElementType()) == 1 &&
139              "alloc size of i8 must by 1 byte for the GEP to be correct");
140       auto *GEP = Builder.CreateGEP(
141           Builder.getInt8Ty(), Constant::getNullValue(Int8PtrTy), V, "uglygep");
142       return Builder.CreateBitCast(GEP, Ty);
143     }
144   }
145   // Short-circuit unnecessary bitcasts.
146   if (Op == Instruction::BitCast) {
147     if (V->getType() == Ty)
148       return V;
149     if (CastInst *CI = dyn_cast<CastInst>(V)) {
150       if (CI->getOperand(0)->getType() == Ty)
151         return CI->getOperand(0);
152     }
153   }
154   // Short-circuit unnecessary inttoptr<->ptrtoint casts.
155   if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) &&
156       SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) {
157     if (CastInst *CI = dyn_cast<CastInst>(V))
158       if ((CI->getOpcode() == Instruction::PtrToInt ||
159            CI->getOpcode() == Instruction::IntToPtr) &&
160           SE.getTypeSizeInBits(CI->getType()) ==
161           SE.getTypeSizeInBits(CI->getOperand(0)->getType()))
162         return CI->getOperand(0);
163     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
164       if ((CE->getOpcode() == Instruction::PtrToInt ||
165            CE->getOpcode() == Instruction::IntToPtr) &&
166           SE.getTypeSizeInBits(CE->getType()) ==
167           SE.getTypeSizeInBits(CE->getOperand(0)->getType()))
168         return CE->getOperand(0);
169   }
170 
171   // Fold a cast of a constant.
172   if (Constant *C = dyn_cast<Constant>(V))
173     return ConstantExpr::getCast(Op, C, Ty);
174 
175   // Cast the argument at the beginning of the entry block, after
176   // any bitcasts of other arguments.
177   if (Argument *A = dyn_cast<Argument>(V)) {
178     BasicBlock::iterator IP = A->getParent()->getEntryBlock().begin();
179     while ((isa<BitCastInst>(IP) &&
180             isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) &&
181             cast<BitCastInst>(IP)->getOperand(0) != A) ||
182            isa<DbgInfoIntrinsic>(IP))
183       ++IP;
184     return ReuseOrCreateCast(A, Ty, Op, IP);
185   }
186 
187   // Cast the instruction immediately after the instruction.
188   Instruction *I = cast<Instruction>(V);
189   BasicBlock::iterator IP = findInsertPointAfter(I, &*Builder.GetInsertPoint());
190   return ReuseOrCreateCast(I, Ty, Op, IP);
191 }
192 
193 /// InsertBinop - Insert the specified binary operator, doing a small amount
194 /// of work to avoid inserting an obviously redundant operation, and hoisting
195 /// to an outer loop when the opportunity is there and it is safe.
196 Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
197                                  Value *LHS, Value *RHS,
198                                  SCEV::NoWrapFlags Flags, bool IsSafeToHoist) {
199   // Fold a binop with constant operands.
200   if (Constant *CLHS = dyn_cast<Constant>(LHS))
201     if (Constant *CRHS = dyn_cast<Constant>(RHS))
202       return ConstantExpr::get(Opcode, CLHS, CRHS);
203 
204   // Do a quick scan to see if we have this binop nearby.  If so, reuse it.
205   unsigned ScanLimit = 6;
206   BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
207   // Scanning starts from the last instruction before the insertion point.
208   BasicBlock::iterator IP = Builder.GetInsertPoint();
209   if (IP != BlockBegin) {
210     --IP;
211     for (; ScanLimit; --IP, --ScanLimit) {
212       // Don't count dbg.value against the ScanLimit, to avoid perturbing the
213       // generated code.
214       if (isa<DbgInfoIntrinsic>(IP))
215         ScanLimit++;
216 
217       auto canGenerateIncompatiblePoison = [&Flags](Instruction *I) {
218         // Ensure that no-wrap flags match.
219         if (isa<OverflowingBinaryOperator>(I)) {
220           if (I->hasNoSignedWrap() != (Flags & SCEV::FlagNSW))
221             return true;
222           if (I->hasNoUnsignedWrap() != (Flags & SCEV::FlagNUW))
223             return true;
224         }
225         // Conservatively, do not use any instruction which has any of exact
226         // flags installed.
227         if (isa<PossiblyExactOperator>(I) && I->isExact())
228           return true;
229         return false;
230       };
231       if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS &&
232           IP->getOperand(1) == RHS && !canGenerateIncompatiblePoison(&*IP))
233         return &*IP;
234       if (IP == BlockBegin) break;
235     }
236   }
237 
238   // Save the original insertion point so we can restore it when we're done.
239   DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();
240   SCEVInsertPointGuard Guard(Builder, this);
241 
242   if (IsSafeToHoist) {
243     // Move the insertion point out of as many loops as we can.
244     while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
245       if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break;
246       BasicBlock *Preheader = L->getLoopPreheader();
247       if (!Preheader) break;
248 
249       // Ok, move up a level.
250       Builder.SetInsertPoint(Preheader->getTerminator());
251     }
252   }
253 
254   // If we haven't found this binop, insert it.
255   Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS));
256   BO->setDebugLoc(Loc);
257   if (Flags & SCEV::FlagNUW)
258     BO->setHasNoUnsignedWrap();
259   if (Flags & SCEV::FlagNSW)
260     BO->setHasNoSignedWrap();
261 
262   return BO;
263 }
264 
265 /// FactorOutConstant - Test if S is divisible by Factor, using signed
266 /// division. If so, update S with Factor divided out and return true.
267 /// S need not be evenly divisible if a reasonable remainder can be
268 /// computed.
269 static bool FactorOutConstant(const SCEV *&S, const SCEV *&Remainder,
270                               const SCEV *Factor, ScalarEvolution &SE,
271                               const DataLayout &DL) {
272   // Everything is divisible by one.
273   if (Factor->isOne())
274     return true;
275 
276   // x/x == 1.
277   if (S == Factor) {
278     S = SE.getConstant(S->getType(), 1);
279     return true;
280   }
281 
282   // For a Constant, check for a multiple of the given factor.
283   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
284     // 0/x == 0.
285     if (C->isZero())
286       return true;
287     // Check for divisibility.
288     if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) {
289       ConstantInt *CI =
290           ConstantInt::get(SE.getContext(), C->getAPInt().sdiv(FC->getAPInt()));
291       // If the quotient is zero and the remainder is non-zero, reject
292       // the value at this scale. It will be considered for subsequent
293       // smaller scales.
294       if (!CI->isZero()) {
295         const SCEV *Div = SE.getConstant(CI);
296         S = Div;
297         Remainder = SE.getAddExpr(
298             Remainder, SE.getConstant(C->getAPInt().srem(FC->getAPInt())));
299         return true;
300       }
301     }
302   }
303 
304   // In a Mul, check if there is a constant operand which is a multiple
305   // of the given factor.
306   if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
307     // Size is known, check if there is a constant operand which is a multiple
308     // of the given factor. If so, we can factor it.
309     if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor))
310       if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0)))
311         if (!C->getAPInt().srem(FC->getAPInt())) {
312           SmallVector<const SCEV *, 4> NewMulOps(M->operands());
313           NewMulOps[0] = SE.getConstant(C->getAPInt().sdiv(FC->getAPInt()));
314           S = SE.getMulExpr(NewMulOps);
315           return true;
316         }
317   }
318 
319   // In an AddRec, check if both start and step are divisible.
320   if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
321     const SCEV *Step = A->getStepRecurrence(SE);
322     const SCEV *StepRem = SE.getConstant(Step->getType(), 0);
323     if (!FactorOutConstant(Step, StepRem, Factor, SE, DL))
324       return false;
325     if (!StepRem->isZero())
326       return false;
327     const SCEV *Start = A->getStart();
328     if (!FactorOutConstant(Start, Remainder, Factor, SE, DL))
329       return false;
330     S = SE.getAddRecExpr(Start, Step, A->getLoop(),
331                          A->getNoWrapFlags(SCEV::FlagNW));
332     return true;
333   }
334 
335   return false;
336 }
337 
338 /// SimplifyAddOperands - Sort and simplify a list of add operands. NumAddRecs
339 /// is the number of SCEVAddRecExprs present, which are kept at the end of
340 /// the list.
341 ///
342 static void SimplifyAddOperands(SmallVectorImpl<const SCEV *> &Ops,
343                                 Type *Ty,
344                                 ScalarEvolution &SE) {
345   unsigned NumAddRecs = 0;
346   for (unsigned i = Ops.size(); i > 0 && isa<SCEVAddRecExpr>(Ops[i-1]); --i)
347     ++NumAddRecs;
348   // Group Ops into non-addrecs and addrecs.
349   SmallVector<const SCEV *, 8> NoAddRecs(Ops.begin(), Ops.end() - NumAddRecs);
350   SmallVector<const SCEV *, 8> AddRecs(Ops.end() - NumAddRecs, Ops.end());
351   // Let ScalarEvolution sort and simplify the non-addrecs list.
352   const SCEV *Sum = NoAddRecs.empty() ?
353                     SE.getConstant(Ty, 0) :
354                     SE.getAddExpr(NoAddRecs);
355   // If it returned an add, use the operands. Otherwise it simplified
356   // the sum into a single value, so just use that.
357   Ops.clear();
358   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum))
359     Ops.append(Add->op_begin(), Add->op_end());
360   else if (!Sum->isZero())
361     Ops.push_back(Sum);
362   // Then append the addrecs.
363   Ops.append(AddRecs.begin(), AddRecs.end());
364 }
365 
366 /// SplitAddRecs - Flatten a list of add operands, moving addrec start values
367 /// out to the top level. For example, convert {a + b,+,c} to a, b, {0,+,d}.
368 /// This helps expose more opportunities for folding parts of the expressions
369 /// into GEP indices.
370 ///
371 static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops,
372                          Type *Ty,
373                          ScalarEvolution &SE) {
374   // Find the addrecs.
375   SmallVector<const SCEV *, 8> AddRecs;
376   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
377     while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) {
378       const SCEV *Start = A->getStart();
379       if (Start->isZero()) break;
380       const SCEV *Zero = SE.getConstant(Ty, 0);
381       AddRecs.push_back(SE.getAddRecExpr(Zero,
382                                          A->getStepRecurrence(SE),
383                                          A->getLoop(),
384                                          A->getNoWrapFlags(SCEV::FlagNW)));
385       if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) {
386         Ops[i] = Zero;
387         Ops.append(Add->op_begin(), Add->op_end());
388         e += Add->getNumOperands();
389       } else {
390         Ops[i] = Start;
391       }
392     }
393   if (!AddRecs.empty()) {
394     // Add the addrecs onto the end of the list.
395     Ops.append(AddRecs.begin(), AddRecs.end());
396     // Resort the operand list, moving any constants to the front.
397     SimplifyAddOperands(Ops, Ty, SE);
398   }
399 }
400 
401 /// expandAddToGEP - Expand an addition expression with a pointer type into
402 /// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps
403 /// BasicAliasAnalysis and other passes analyze the result. See the rules
404 /// for getelementptr vs. inttoptr in
405 /// http://llvm.org/docs/LangRef.html#pointeraliasing
406 /// for details.
407 ///
408 /// Design note: The correctness of using getelementptr here depends on
409 /// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as
410 /// they may introduce pointer arithmetic which may not be safely converted
411 /// into getelementptr.
412 ///
413 /// Design note: It might seem desirable for this function to be more
414 /// loop-aware. If some of the indices are loop-invariant while others
415 /// aren't, it might seem desirable to emit multiple GEPs, keeping the
416 /// loop-invariant portions of the overall computation outside the loop.
417 /// However, there are a few reasons this is not done here. Hoisting simple
418 /// arithmetic is a low-level optimization that often isn't very
419 /// important until late in the optimization process. In fact, passes
420 /// like InstructionCombining will combine GEPs, even if it means
421 /// pushing loop-invariant computation down into loops, so even if the
422 /// GEPs were split here, the work would quickly be undone. The
423 /// LoopStrengthReduction pass, which is usually run quite late (and
424 /// after the last InstructionCombining pass), takes care of hoisting
425 /// loop-invariant portions of expressions, after considering what
426 /// can be folded using target addressing modes.
427 ///
428 Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin,
429                                     const SCEV *const *op_end,
430                                     PointerType *PTy,
431                                     Type *Ty,
432                                     Value *V) {
433   Type *OriginalElTy = PTy->getElementType();
434   Type *ElTy = OriginalElTy;
435   SmallVector<Value *, 4> GepIndices;
436   SmallVector<const SCEV *, 8> Ops(op_begin, op_end);
437   bool AnyNonZeroIndices = false;
438 
439   // Split AddRecs up into parts as either of the parts may be usable
440   // without the other.
441   SplitAddRecs(Ops, Ty, SE);
442 
443   Type *IntIdxTy = DL.getIndexType(PTy);
444 
445   // Descend down the pointer's type and attempt to convert the other
446   // operands into GEP indices, at each level. The first index in a GEP
447   // indexes into the array implied by the pointer operand; the rest of
448   // the indices index into the element or field type selected by the
449   // preceding index.
450   for (;;) {
451     // If the scale size is not 0, attempt to factor out a scale for
452     // array indexing.
453     SmallVector<const SCEV *, 8> ScaledOps;
454     if (ElTy->isSized()) {
455       const SCEV *ElSize = SE.getSizeOfExpr(IntIdxTy, ElTy);
456       if (!ElSize->isZero()) {
457         SmallVector<const SCEV *, 8> NewOps;
458         for (const SCEV *Op : Ops) {
459           const SCEV *Remainder = SE.getConstant(Ty, 0);
460           if (FactorOutConstant(Op, Remainder, ElSize, SE, DL)) {
461             // Op now has ElSize factored out.
462             ScaledOps.push_back(Op);
463             if (!Remainder->isZero())
464               NewOps.push_back(Remainder);
465             AnyNonZeroIndices = true;
466           } else {
467             // The operand was not divisible, so add it to the list of operands
468             // we'll scan next iteration.
469             NewOps.push_back(Op);
470           }
471         }
472         // If we made any changes, update Ops.
473         if (!ScaledOps.empty()) {
474           Ops = NewOps;
475           SimplifyAddOperands(Ops, Ty, SE);
476         }
477       }
478     }
479 
480     // Record the scaled array index for this level of the type. If
481     // we didn't find any operands that could be factored, tentatively
482     // assume that element zero was selected (since the zero offset
483     // would obviously be folded away).
484     Value *Scaled =
485         ScaledOps.empty()
486             ? Constant::getNullValue(Ty)
487             : expandCodeForImpl(SE.getAddExpr(ScaledOps), Ty, false);
488     GepIndices.push_back(Scaled);
489 
490     // Collect struct field index operands.
491     while (StructType *STy = dyn_cast<StructType>(ElTy)) {
492       bool FoundFieldNo = false;
493       // An empty struct has no fields.
494       if (STy->getNumElements() == 0) break;
495       // Field offsets are known. See if a constant offset falls within any of
496       // the struct fields.
497       if (Ops.empty())
498         break;
499       if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0]))
500         if (SE.getTypeSizeInBits(C->getType()) <= 64) {
501           const StructLayout &SL = *DL.getStructLayout(STy);
502           uint64_t FullOffset = C->getValue()->getZExtValue();
503           if (FullOffset < SL.getSizeInBytes()) {
504             unsigned ElIdx = SL.getElementContainingOffset(FullOffset);
505             GepIndices.push_back(
506                 ConstantInt::get(Type::getInt32Ty(Ty->getContext()), ElIdx));
507             ElTy = STy->getTypeAtIndex(ElIdx);
508             Ops[0] =
509                 SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx));
510             AnyNonZeroIndices = true;
511             FoundFieldNo = true;
512           }
513         }
514       // If no struct field offsets were found, tentatively assume that
515       // field zero was selected (since the zero offset would obviously
516       // be folded away).
517       if (!FoundFieldNo) {
518         ElTy = STy->getTypeAtIndex(0u);
519         GepIndices.push_back(
520           Constant::getNullValue(Type::getInt32Ty(Ty->getContext())));
521       }
522     }
523 
524     if (ArrayType *ATy = dyn_cast<ArrayType>(ElTy))
525       ElTy = ATy->getElementType();
526     else
527       // FIXME: Handle VectorType.
528       // E.g., If ElTy is scalable vector, then ElSize is not a compile-time
529       // constant, therefore can not be factored out. The generated IR is less
530       // ideal with base 'V' cast to i8* and do ugly getelementptr over that.
531       break;
532   }
533 
534   // If none of the operands were convertible to proper GEP indices, cast
535   // the base to i8* and do an ugly getelementptr with that. It's still
536   // better than ptrtoint+arithmetic+inttoptr at least.
537   if (!AnyNonZeroIndices) {
538     // Cast the base to i8*.
539     V = InsertNoopCastOfTo(V,
540        Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace()));
541 
542     assert(!isa<Instruction>(V) ||
543            SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()));
544 
545     // Expand the operands for a plain byte offset.
546     Value *Idx = expandCodeForImpl(SE.getAddExpr(Ops), Ty, false);
547 
548     // Fold a GEP with constant operands.
549     if (Constant *CLHS = dyn_cast<Constant>(V))
550       if (Constant *CRHS = dyn_cast<Constant>(Idx))
551         return ConstantExpr::getGetElementPtr(Type::getInt8Ty(Ty->getContext()),
552                                               CLHS, CRHS);
553 
554     // Do a quick scan to see if we have this GEP nearby.  If so, reuse it.
555     unsigned ScanLimit = 6;
556     BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
557     // Scanning starts from the last instruction before the insertion point.
558     BasicBlock::iterator IP = Builder.GetInsertPoint();
559     if (IP != BlockBegin) {
560       --IP;
561       for (; ScanLimit; --IP, --ScanLimit) {
562         // Don't count dbg.value against the ScanLimit, to avoid perturbing the
563         // generated code.
564         if (isa<DbgInfoIntrinsic>(IP))
565           ScanLimit++;
566         if (IP->getOpcode() == Instruction::GetElementPtr &&
567             IP->getOperand(0) == V && IP->getOperand(1) == Idx)
568           return &*IP;
569         if (IP == BlockBegin) break;
570       }
571     }
572 
573     // Save the original insertion point so we can restore it when we're done.
574     SCEVInsertPointGuard Guard(Builder, this);
575 
576     // Move the insertion point out of as many loops as we can.
577     while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
578       if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break;
579       BasicBlock *Preheader = L->getLoopPreheader();
580       if (!Preheader) break;
581 
582       // Ok, move up a level.
583       Builder.SetInsertPoint(Preheader->getTerminator());
584     }
585 
586     // Emit a GEP.
587     return Builder.CreateGEP(Builder.getInt8Ty(), V, Idx, "uglygep");
588   }
589 
590   {
591     SCEVInsertPointGuard Guard(Builder, this);
592 
593     // Move the insertion point out of as many loops as we can.
594     while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
595       if (!L->isLoopInvariant(V)) break;
596 
597       bool AnyIndexNotLoopInvariant = any_of(
598           GepIndices, [L](Value *Op) { return !L->isLoopInvariant(Op); });
599 
600       if (AnyIndexNotLoopInvariant)
601         break;
602 
603       BasicBlock *Preheader = L->getLoopPreheader();
604       if (!Preheader) break;
605 
606       // Ok, move up a level.
607       Builder.SetInsertPoint(Preheader->getTerminator());
608     }
609 
610     // Insert a pretty getelementptr. Note that this GEP is not marked inbounds,
611     // because ScalarEvolution may have changed the address arithmetic to
612     // compute a value which is beyond the end of the allocated object.
613     Value *Casted = V;
614     if (V->getType() != PTy)
615       Casted = InsertNoopCastOfTo(Casted, PTy);
616     Value *GEP = Builder.CreateGEP(OriginalElTy, Casted, GepIndices, "scevgep");
617     Ops.push_back(SE.getUnknown(GEP));
618   }
619 
620   return expand(SE.getAddExpr(Ops));
621 }
622 
623 Value *SCEVExpander::expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty,
624                                     Value *V) {
625   const SCEV *const Ops[1] = {Op};
626   return expandAddToGEP(Ops, Ops + 1, PTy, Ty, V);
627 }
628 
629 /// PickMostRelevantLoop - Given two loops pick the one that's most relevant for
630 /// SCEV expansion. If they are nested, this is the most nested. If they are
631 /// neighboring, pick the later.
632 static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B,
633                                         DominatorTree &DT) {
634   if (!A) return B;
635   if (!B) return A;
636   if (A->contains(B)) return B;
637   if (B->contains(A)) return A;
638   if (DT.dominates(A->getHeader(), B->getHeader())) return B;
639   if (DT.dominates(B->getHeader(), A->getHeader())) return A;
640   return A; // Arbitrarily break the tie.
641 }
642 
643 /// getRelevantLoop - Get the most relevant loop associated with the given
644 /// expression, according to PickMostRelevantLoop.
645 const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) {
646   // Test whether we've already computed the most relevant loop for this SCEV.
647   auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr));
648   if (!Pair.second)
649     return Pair.first->second;
650 
651   if (isa<SCEVConstant>(S))
652     // A constant has no relevant loops.
653     return nullptr;
654   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
655     if (const Instruction *I = dyn_cast<Instruction>(U->getValue()))
656       return Pair.first->second = SE.LI.getLoopFor(I->getParent());
657     // A non-instruction has no relevant loops.
658     return nullptr;
659   }
660   if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) {
661     const Loop *L = nullptr;
662     if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
663       L = AR->getLoop();
664     for (const SCEV *Op : N->operands())
665       L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT);
666     return RelevantLoops[N] = L;
667   }
668   if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) {
669     const Loop *Result = getRelevantLoop(C->getOperand());
670     return RelevantLoops[C] = Result;
671   }
672   if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
673     const Loop *Result = PickMostRelevantLoop(
674         getRelevantLoop(D->getLHS()), getRelevantLoop(D->getRHS()), SE.DT);
675     return RelevantLoops[D] = Result;
676   }
677   llvm_unreachable("Unexpected SCEV type!");
678 }
679 
680 namespace {
681 
682 /// LoopCompare - Compare loops by PickMostRelevantLoop.
683 class LoopCompare {
684   DominatorTree &DT;
685 public:
686   explicit LoopCompare(DominatorTree &dt) : DT(dt) {}
687 
688   bool operator()(std::pair<const Loop *, const SCEV *> LHS,
689                   std::pair<const Loop *, const SCEV *> RHS) const {
690     // Keep pointer operands sorted at the end.
691     if (LHS.second->getType()->isPointerTy() !=
692         RHS.second->getType()->isPointerTy())
693       return LHS.second->getType()->isPointerTy();
694 
695     // Compare loops with PickMostRelevantLoop.
696     if (LHS.first != RHS.first)
697       return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first;
698 
699     // If one operand is a non-constant negative and the other is not,
700     // put the non-constant negative on the right so that a sub can
701     // be used instead of a negate and add.
702     if (LHS.second->isNonConstantNegative()) {
703       if (!RHS.second->isNonConstantNegative())
704         return false;
705     } else if (RHS.second->isNonConstantNegative())
706       return true;
707 
708     // Otherwise they are equivalent according to this comparison.
709     return false;
710   }
711 };
712 
713 }
714 
715 Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) {
716   Type *Ty = SE.getEffectiveSCEVType(S->getType());
717 
718   // Collect all the add operands in a loop, along with their associated loops.
719   // Iterate in reverse so that constants are emitted last, all else equal, and
720   // so that pointer operands are inserted first, which the code below relies on
721   // to form more involved GEPs.
722   SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
723   for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(S->op_end()),
724        E(S->op_begin()); I != E; ++I)
725     OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
726 
727   // Sort by loop. Use a stable sort so that constants follow non-constants and
728   // pointer operands precede non-pointer operands.
729   llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
730 
731   // Emit instructions to add all the operands. Hoist as much as possible
732   // out of loops, and form meaningful getelementptrs where possible.
733   Value *Sum = nullptr;
734   for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) {
735     const Loop *CurLoop = I->first;
736     const SCEV *Op = I->second;
737     if (!Sum) {
738       // This is the first operand. Just expand it.
739       Sum = expand(Op);
740       ++I;
741     } else if (PointerType *PTy = dyn_cast<PointerType>(Sum->getType())) {
742       // The running sum expression is a pointer. Try to form a getelementptr
743       // at this level with that as the base.
744       SmallVector<const SCEV *, 4> NewOps;
745       for (; I != E && I->first == CurLoop; ++I) {
746         // If the operand is SCEVUnknown and not instructions, peek through
747         // it, to enable more of it to be folded into the GEP.
748         const SCEV *X = I->second;
749         if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X))
750           if (!isa<Instruction>(U->getValue()))
751             X = SE.getSCEV(U->getValue());
752         NewOps.push_back(X);
753       }
754       Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum);
755     } else if (PointerType *PTy = dyn_cast<PointerType>(Op->getType())) {
756       // The running sum is an integer, and there's a pointer at this level.
757       // Try to form a getelementptr. If the running sum is instructions,
758       // use a SCEVUnknown to avoid re-analyzing them.
759       SmallVector<const SCEV *, 4> NewOps;
760       NewOps.push_back(isa<Instruction>(Sum) ? SE.getUnknown(Sum) :
761                                                SE.getSCEV(Sum));
762       for (++I; I != E && I->first == CurLoop; ++I)
763         NewOps.push_back(I->second);
764       Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, expand(Op));
765     } else if (Op->isNonConstantNegative()) {
766       // Instead of doing a negate and add, just do a subtract.
767       Value *W = expandCodeForImpl(SE.getNegativeSCEV(Op), Ty, false);
768       Sum = InsertNoopCastOfTo(Sum, Ty);
769       Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap,
770                         /*IsSafeToHoist*/ true);
771       ++I;
772     } else {
773       // A simple add.
774       Value *W = expandCodeForImpl(Op, Ty, false);
775       Sum = InsertNoopCastOfTo(Sum, Ty);
776       // Canonicalize a constant to the RHS.
777       if (isa<Constant>(Sum)) std::swap(Sum, W);
778       Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(),
779                         /*IsSafeToHoist*/ true);
780       ++I;
781     }
782   }
783 
784   return Sum;
785 }
786 
787 Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
788   Type *Ty = SE.getEffectiveSCEVType(S->getType());
789 
790   // Collect all the mul operands in a loop, along with their associated loops.
791   // Iterate in reverse so that constants are emitted last, all else equal.
792   SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
793   for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()),
794        E(S->op_begin()); I != E; ++I)
795     OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
796 
797   // Sort by loop. Use a stable sort so that constants follow non-constants.
798   llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
799 
800   // Emit instructions to mul all the operands. Hoist as much as possible
801   // out of loops.
802   Value *Prod = nullptr;
803   auto I = OpsAndLoops.begin();
804 
805   // Expand the calculation of X pow N in the following manner:
806   // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then:
807   // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK).
808   const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() {
809     auto E = I;
810     // Calculate how many times the same operand from the same loop is included
811     // into this power.
812     uint64_t Exponent = 0;
813     const uint64_t MaxExponent = UINT64_MAX >> 1;
814     // No one sane will ever try to calculate such huge exponents, but if we
815     // need this, we stop on UINT64_MAX / 2 because we need to exit the loop
816     // below when the power of 2 exceeds our Exponent, and we want it to be
817     // 1u << 31 at most to not deal with unsigned overflow.
818     while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) {
819       ++Exponent;
820       ++E;
821     }
822     assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?");
823 
824     // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them
825     // that are needed into the result.
826     Value *P = expandCodeForImpl(I->second, Ty, false);
827     Value *Result = nullptr;
828     if (Exponent & 1)
829       Result = P;
830     for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) {
831       P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap,
832                       /*IsSafeToHoist*/ true);
833       if (Exponent & BinExp)
834         Result = Result ? InsertBinop(Instruction::Mul, Result, P,
835                                       SCEV::FlagAnyWrap,
836                                       /*IsSafeToHoist*/ true)
837                         : P;
838     }
839 
840     I = E;
841     assert(Result && "Nothing was expanded?");
842     return Result;
843   };
844 
845   while (I != OpsAndLoops.end()) {
846     if (!Prod) {
847       // This is the first operand. Just expand it.
848       Prod = ExpandOpBinPowN();
849     } else if (I->second->isAllOnesValue()) {
850       // Instead of doing a multiply by negative one, just do a negate.
851       Prod = InsertNoopCastOfTo(Prod, Ty);
852       Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod,
853                          SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
854       ++I;
855     } else {
856       // A simple mul.
857       Value *W = ExpandOpBinPowN();
858       Prod = InsertNoopCastOfTo(Prod, Ty);
859       // Canonicalize a constant to the RHS.
860       if (isa<Constant>(Prod)) std::swap(Prod, W);
861       const APInt *RHS;
862       if (match(W, m_Power2(RHS))) {
863         // Canonicalize Prod*(1<<C) to Prod<<C.
864         assert(!Ty->isVectorTy() && "vector types are not SCEVable");
865         auto NWFlags = S->getNoWrapFlags();
866         // clear nsw flag if shl will produce poison value.
867         if (RHS->logBase2() == RHS->getBitWidth() - 1)
868           NWFlags = ScalarEvolution::clearFlags(NWFlags, SCEV::FlagNSW);
869         Prod = InsertBinop(Instruction::Shl, Prod,
870                            ConstantInt::get(Ty, RHS->logBase2()), NWFlags,
871                            /*IsSafeToHoist*/ true);
872       } else {
873         Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(),
874                            /*IsSafeToHoist*/ true);
875       }
876     }
877   }
878 
879   return Prod;
880 }
881 
882 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
883   Type *Ty = SE.getEffectiveSCEVType(S->getType());
884 
885   Value *LHS = expandCodeForImpl(S->getLHS(), Ty, false);
886   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
887     const APInt &RHS = SC->getAPInt();
888     if (RHS.isPowerOf2())
889       return InsertBinop(Instruction::LShr, LHS,
890                          ConstantInt::get(Ty, RHS.logBase2()),
891                          SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
892   }
893 
894   Value *RHS = expandCodeForImpl(S->getRHS(), Ty, false);
895   return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap,
896                      /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS()));
897 }
898 
899 /// Move parts of Base into Rest to leave Base with the minimal
900 /// expression that provides a pointer operand suitable for a
901 /// GEP expansion.
902 static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest,
903                               ScalarEvolution &SE) {
904   while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) {
905     Base = A->getStart();
906     Rest = SE.getAddExpr(Rest,
907                          SE.getAddRecExpr(SE.getConstant(A->getType(), 0),
908                                           A->getStepRecurrence(SE),
909                                           A->getLoop(),
910                                           A->getNoWrapFlags(SCEV::FlagNW)));
911   }
912   if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) {
913     Base = A->getOperand(A->getNumOperands()-1);
914     SmallVector<const SCEV *, 8> NewAddOps(A->operands());
915     NewAddOps.back() = Rest;
916     Rest = SE.getAddExpr(NewAddOps);
917     ExposePointerBase(Base, Rest, SE);
918   }
919 }
920 
921 /// Determine if this is a well-behaved chain of instructions leading back to
922 /// the PHI. If so, it may be reused by expanded expressions.
923 bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
924                                          const Loop *L) {
925   if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) ||
926       (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))
927     return false;
928   // If any of the operands don't dominate the insert position, bail.
929   // Addrec operands are always loop-invariant, so this can only happen
930   // if there are instructions which haven't been hoisted.
931   if (L == IVIncInsertLoop) {
932     for (Use &Op : llvm::drop_begin(IncV->operands()))
933       if (Instruction *OInst = dyn_cast<Instruction>(Op))
934         if (!SE.DT.dominates(OInst, IVIncInsertPos))
935           return false;
936   }
937   // Advance to the next instruction.
938   IncV = dyn_cast<Instruction>(IncV->getOperand(0));
939   if (!IncV)
940     return false;
941 
942   if (IncV->mayHaveSideEffects())
943     return false;
944 
945   if (IncV == PN)
946     return true;
947 
948   return isNormalAddRecExprPHI(PN, IncV, L);
949 }
950 
951 /// getIVIncOperand returns an induction variable increment's induction
952 /// variable operand.
953 ///
954 /// If allowScale is set, any type of GEP is allowed as long as the nonIV
955 /// operands dominate InsertPos.
956 ///
957 /// If allowScale is not set, ensure that a GEP increment conforms to one of the
958 /// simple patterns generated by getAddRecExprPHILiterally and
959 /// expandAddtoGEP. If the pattern isn't recognized, return NULL.
960 Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV,
961                                            Instruction *InsertPos,
962                                            bool allowScale) {
963   if (IncV == InsertPos)
964     return nullptr;
965 
966   switch (IncV->getOpcode()) {
967   default:
968     return nullptr;
969   // Check for a simple Add/Sub or GEP of a loop invariant step.
970   case Instruction::Add:
971   case Instruction::Sub: {
972     Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));
973     if (!OInst || SE.DT.dominates(OInst, InsertPos))
974       return dyn_cast<Instruction>(IncV->getOperand(0));
975     return nullptr;
976   }
977   case Instruction::BitCast:
978     return dyn_cast<Instruction>(IncV->getOperand(0));
979   case Instruction::GetElementPtr:
980     for (Use &U : llvm::drop_begin(IncV->operands())) {
981       if (isa<Constant>(U))
982         continue;
983       if (Instruction *OInst = dyn_cast<Instruction>(U)) {
984         if (!SE.DT.dominates(OInst, InsertPos))
985           return nullptr;
986       }
987       if (allowScale) {
988         // allow any kind of GEP as long as it can be hoisted.
989         continue;
990       }
991       // This must be a pointer addition of constants (pretty), which is already
992       // handled, or some number of address-size elements (ugly). Ugly geps
993       // have 2 operands. i1* is used by the expander to represent an
994       // address-size element.
995       if (IncV->getNumOperands() != 2)
996         return nullptr;
997       unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace();
998       if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS)
999           && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS))
1000         return nullptr;
1001       break;
1002     }
1003     return dyn_cast<Instruction>(IncV->getOperand(0));
1004   }
1005 }
1006 
1007 /// If the insert point of the current builder or any of the builders on the
1008 /// stack of saved builders has 'I' as its insert point, update it to point to
1009 /// the instruction after 'I'.  This is intended to be used when the instruction
1010 /// 'I' is being moved.  If this fixup is not done and 'I' is moved to a
1011 /// different block, the inconsistent insert point (with a mismatched
1012 /// Instruction and Block) can lead to an instruction being inserted in a block
1013 /// other than its parent.
1014 void SCEVExpander::fixupInsertPoints(Instruction *I) {
1015   BasicBlock::iterator It(*I);
1016   BasicBlock::iterator NewInsertPt = std::next(It);
1017   if (Builder.GetInsertPoint() == It)
1018     Builder.SetInsertPoint(&*NewInsertPt);
1019   for (auto *InsertPtGuard : InsertPointGuards)
1020     if (InsertPtGuard->GetInsertPoint() == It)
1021       InsertPtGuard->SetInsertPoint(NewInsertPt);
1022 }
1023 
1024 /// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make
1025 /// it available to other uses in this loop. Recursively hoist any operands,
1026 /// until we reach a value that dominates InsertPos.
1027 bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) {
1028   if (SE.DT.dominates(IncV, InsertPos))
1029       return true;
1030 
1031   // InsertPos must itself dominate IncV so that IncV's new position satisfies
1032   // its existing users.
1033   if (isa<PHINode>(InsertPos) ||
1034       !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))
1035     return false;
1036 
1037   if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
1038     return false;
1039 
1040   // Check that the chain of IV operands leading back to Phi can be hoisted.
1041   SmallVector<Instruction*, 4> IVIncs;
1042   for(;;) {
1043     Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true);
1044     if (!Oper)
1045       return false;
1046     // IncV is safe to hoist.
1047     IVIncs.push_back(IncV);
1048     IncV = Oper;
1049     if (SE.DT.dominates(IncV, InsertPos))
1050       break;
1051   }
1052   for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) {
1053     fixupInsertPoints(*I);
1054     (*I)->moveBefore(InsertPos);
1055   }
1056   return true;
1057 }
1058 
1059 /// Determine if this cyclic phi is in a form that would have been generated by
1060 /// LSR. We don't care if the phi was actually expanded in this pass, as long
1061 /// as it is in a low-cost form, for example, no implied multiplication. This
1062 /// should match any patterns generated by getAddRecExprPHILiterally and
1063 /// expandAddtoGEP.
1064 bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
1065                                            const Loop *L) {
1066   for(Instruction *IVOper = IncV;
1067       (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
1068                                 /*allowScale=*/false));) {
1069     if (IVOper == PN)
1070       return true;
1071   }
1072   return false;
1073 }
1074 
1075 /// expandIVInc - Expand an IV increment at Builder's current InsertPos.
1076 /// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may
1077 /// need to materialize IV increments elsewhere to handle difficult situations.
1078 Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
1079                                  Type *ExpandTy, Type *IntTy,
1080                                  bool useSubtract) {
1081   Value *IncV;
1082   // If the PHI is a pointer, use a GEP, otherwise use an add or sub.
1083   if (ExpandTy->isPointerTy()) {
1084     PointerType *GEPPtrTy = cast<PointerType>(ExpandTy);
1085     // If the step isn't constant, don't use an implicitly scaled GEP, because
1086     // that would require a multiply inside the loop.
1087     if (!isa<ConstantInt>(StepV))
1088       GEPPtrTy = PointerType::get(Type::getInt1Ty(SE.getContext()),
1089                                   GEPPtrTy->getAddressSpace());
1090     IncV = expandAddToGEP(SE.getSCEV(StepV), GEPPtrTy, IntTy, PN);
1091     if (IncV->getType() != PN->getType())
1092       IncV = Builder.CreateBitCast(IncV, PN->getType());
1093   } else {
1094     IncV = useSubtract ?
1095       Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") :
1096       Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next");
1097   }
1098   return IncV;
1099 }
1100 
1101 /// Hoist the addrec instruction chain rooted in the loop phi above the
1102 /// position. This routine assumes that this is possible (has been checked).
1103 void SCEVExpander::hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
1104                                   Instruction *Pos, PHINode *LoopPhi) {
1105   do {
1106     if (DT->dominates(InstToHoist, Pos))
1107       break;
1108     // Make sure the increment is where we want it. But don't move it
1109     // down past a potential existing post-inc user.
1110     fixupInsertPoints(InstToHoist);
1111     InstToHoist->moveBefore(Pos);
1112     Pos = InstToHoist;
1113     InstToHoist = cast<Instruction>(InstToHoist->getOperand(0));
1114   } while (InstToHoist != LoopPhi);
1115 }
1116 
1117 /// Check whether we can cheaply express the requested SCEV in terms of
1118 /// the available PHI SCEV by truncation and/or inversion of the step.
1119 static bool canBeCheaplyTransformed(ScalarEvolution &SE,
1120                                     const SCEVAddRecExpr *Phi,
1121                                     const SCEVAddRecExpr *Requested,
1122                                     bool &InvertStep) {
1123   Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType());
1124   Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType());
1125 
1126   if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth())
1127     return false;
1128 
1129   // Try truncate it if necessary.
1130   Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy));
1131   if (!Phi)
1132     return false;
1133 
1134   // Check whether truncation will help.
1135   if (Phi == Requested) {
1136     InvertStep = false;
1137     return true;
1138   }
1139 
1140   // Check whether inverting will help: {R,+,-1} == R - {0,+,1}.
1141   if (SE.getAddExpr(Requested->getStart(),
1142                     SE.getNegativeSCEV(Requested)) == Phi) {
1143     InvertStep = true;
1144     return true;
1145   }
1146 
1147   return false;
1148 }
1149 
1150 static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1151   if (!isa<IntegerType>(AR->getType()))
1152     return false;
1153 
1154   unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1155   Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1156   const SCEV *Step = AR->getStepRecurrence(SE);
1157   const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy),
1158                                             SE.getSignExtendExpr(AR, WideTy));
1159   const SCEV *ExtendAfterOp =
1160     SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1161   return ExtendAfterOp == OpAfterExtend;
1162 }
1163 
1164 static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1165   if (!isa<IntegerType>(AR->getType()))
1166     return false;
1167 
1168   unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1169   Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1170   const SCEV *Step = AR->getStepRecurrence(SE);
1171   const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy),
1172                                             SE.getZeroExtendExpr(AR, WideTy));
1173   const SCEV *ExtendAfterOp =
1174     SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1175   return ExtendAfterOp == OpAfterExtend;
1176 }
1177 
1178 /// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand
1179 /// the base addrec, which is the addrec without any non-loop-dominating
1180 /// values, and return the PHI.
1181 PHINode *
1182 SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
1183                                         const Loop *L,
1184                                         Type *ExpandTy,
1185                                         Type *IntTy,
1186                                         Type *&TruncTy,
1187                                         bool &InvertStep) {
1188   assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position");
1189 
1190   // Reuse a previously-inserted PHI, if present.
1191   BasicBlock *LatchBlock = L->getLoopLatch();
1192   if (LatchBlock) {
1193     PHINode *AddRecPhiMatch = nullptr;
1194     Instruction *IncV = nullptr;
1195     TruncTy = nullptr;
1196     InvertStep = false;
1197 
1198     // Only try partially matching scevs that need truncation and/or
1199     // step-inversion if we know this loop is outside the current loop.
1200     bool TryNonMatchingSCEV =
1201         IVIncInsertLoop &&
1202         SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
1203 
1204     for (PHINode &PN : L->getHeader()->phis()) {
1205       if (!SE.isSCEVable(PN.getType()))
1206         continue;
1207 
1208       // We should not look for a incomplete PHI. Getting SCEV for a incomplete
1209       // PHI has no meaning at all.
1210       if (!PN.isComplete()) {
1211         DEBUG_WITH_TYPE(
1212             DebugType, dbgs() << "One incomplete PHI is found: " << PN << "\n");
1213         continue;
1214       }
1215 
1216       const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
1217       if (!PhiSCEV)
1218         continue;
1219 
1220       bool IsMatchingSCEV = PhiSCEV == Normalized;
1221       // We only handle truncation and inversion of phi recurrences for the
1222       // expanded expression if the expanded expression's loop dominates the
1223       // loop we insert to. Check now, so we can bail out early.
1224       if (!IsMatchingSCEV && !TryNonMatchingSCEV)
1225           continue;
1226 
1227       // TODO: this possibly can be reworked to avoid this cast at all.
1228       Instruction *TempIncV =
1229           dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
1230       if (!TempIncV)
1231         continue;
1232 
1233       // Check whether we can reuse this PHI node.
1234       if (LSRMode) {
1235         if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
1236           continue;
1237         if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos))
1238           continue;
1239       } else {
1240         if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
1241           continue;
1242       }
1243 
1244       // Stop if we have found an exact match SCEV.
1245       if (IsMatchingSCEV) {
1246         IncV = TempIncV;
1247         TruncTy = nullptr;
1248         InvertStep = false;
1249         AddRecPhiMatch = &PN;
1250         break;
1251       }
1252 
1253       // Try whether the phi can be translated into the requested form
1254       // (truncated and/or offset by a constant).
1255       if ((!TruncTy || InvertStep) &&
1256           canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) {
1257         // Record the phi node. But don't stop we might find an exact match
1258         // later.
1259         AddRecPhiMatch = &PN;
1260         IncV = TempIncV;
1261         TruncTy = SE.getEffectiveSCEVType(Normalized->getType());
1262       }
1263     }
1264 
1265     if (AddRecPhiMatch) {
1266       // Potentially, move the increment. We have made sure in
1267       // isExpandedAddRecExprPHI or hoistIVInc that this is possible.
1268       if (L == IVIncInsertLoop)
1269         hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch);
1270 
1271       // Ok, the add recurrence looks usable.
1272       // Remember this PHI, even in post-inc mode.
1273       InsertedValues.insert(AddRecPhiMatch);
1274       // Remember the increment.
1275       rememberInstruction(IncV);
1276       // Those values were not actually inserted but re-used.
1277       ReusedValues.insert(AddRecPhiMatch);
1278       ReusedValues.insert(IncV);
1279       return AddRecPhiMatch;
1280     }
1281   }
1282 
1283   // Save the original insertion point so we can restore it when we're done.
1284   SCEVInsertPointGuard Guard(Builder, this);
1285 
1286   // Another AddRec may need to be recursively expanded below. For example, if
1287   // this AddRec is quadratic, the StepV may itself be an AddRec in this
1288   // loop. Remove this loop from the PostIncLoops set before expanding such
1289   // AddRecs. Otherwise, we cannot find a valid position for the step
1290   // (i.e. StepV can never dominate its loop header).  Ideally, we could do
1291   // SavedIncLoops.swap(PostIncLoops), but we generally have a single element,
1292   // so it's not worth implementing SmallPtrSet::swap.
1293   PostIncLoopSet SavedPostIncLoops = PostIncLoops;
1294   PostIncLoops.clear();
1295 
1296   // Expand code for the start value into the loop preheader.
1297   assert(L->getLoopPreheader() &&
1298          "Can't expand add recurrences without a loop preheader!");
1299   Value *StartV =
1300       expandCodeForImpl(Normalized->getStart(), ExpandTy,
1301                         L->getLoopPreheader()->getTerminator(), false);
1302 
1303   // StartV must have been be inserted into L's preheader to dominate the new
1304   // phi.
1305   assert(!isa<Instruction>(StartV) ||
1306          SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),
1307                                  L->getHeader()));
1308 
1309   // Expand code for the step value. Do this before creating the PHI so that PHI
1310   // reuse code doesn't see an incomplete PHI.
1311   const SCEV *Step = Normalized->getStepRecurrence(SE);
1312   // If the stride is negative, insert a sub instead of an add for the increment
1313   // (unless it's a constant, because subtracts of constants are canonicalized
1314   // to adds).
1315   bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1316   if (useSubtract)
1317     Step = SE.getNegativeSCEV(Step);
1318   // Expand the step somewhere that dominates the loop header.
1319   Value *StepV = expandCodeForImpl(
1320       Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false);
1321 
1322   // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if
1323   // we actually do emit an addition.  It does not apply if we emit a
1324   // subtraction.
1325   bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized);
1326   bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized);
1327 
1328   // Create the PHI.
1329   BasicBlock *Header = L->getHeader();
1330   Builder.SetInsertPoint(Header, Header->begin());
1331   pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1332   PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE),
1333                                   Twine(IVName) + ".iv");
1334 
1335   // Create the step instructions and populate the PHI.
1336   for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1337     BasicBlock *Pred = *HPI;
1338 
1339     // Add a start value.
1340     if (!L->contains(Pred)) {
1341       PN->addIncoming(StartV, Pred);
1342       continue;
1343     }
1344 
1345     // Create a step value and add it to the PHI.
1346     // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the
1347     // instructions at IVIncInsertPos.
1348     Instruction *InsertPos = L == IVIncInsertLoop ?
1349       IVIncInsertPos : Pred->getTerminator();
1350     Builder.SetInsertPoint(InsertPos);
1351     Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1352 
1353     if (isa<OverflowingBinaryOperator>(IncV)) {
1354       if (IncrementIsNUW)
1355         cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
1356       if (IncrementIsNSW)
1357         cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
1358     }
1359     PN->addIncoming(IncV, Pred);
1360   }
1361 
1362   // After expanding subexpressions, restore the PostIncLoops set so the caller
1363   // can ensure that IVIncrement dominates the current uses.
1364   PostIncLoops = SavedPostIncLoops;
1365 
1366   // Remember this PHI, even in post-inc mode.
1367   InsertedValues.insert(PN);
1368 
1369   return PN;
1370 }
1371 
1372 Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
1373   Type *STy = S->getType();
1374   Type *IntTy = SE.getEffectiveSCEVType(STy);
1375   const Loop *L = S->getLoop();
1376 
1377   // Determine a normalized form of this expression, which is the expression
1378   // before any post-inc adjustment is made.
1379   const SCEVAddRecExpr *Normalized = S;
1380   if (PostIncLoops.count(L)) {
1381     PostIncLoopSet Loops;
1382     Loops.insert(L);
1383     Normalized = cast<SCEVAddRecExpr>(normalizeForPostIncUse(S, Loops, SE));
1384   }
1385 
1386   // Strip off any non-loop-dominating component from the addrec start.
1387   const SCEV *Start = Normalized->getStart();
1388   const SCEV *PostLoopOffset = nullptr;
1389   if (!SE.properlyDominates(Start, L->getHeader())) {
1390     PostLoopOffset = Start;
1391     Start = SE.getConstant(Normalized->getType(), 0);
1392     Normalized = cast<SCEVAddRecExpr>(
1393       SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE),
1394                        Normalized->getLoop(),
1395                        Normalized->getNoWrapFlags(SCEV::FlagNW)));
1396   }
1397 
1398   // Strip off any non-loop-dominating component from the addrec step.
1399   const SCEV *Step = Normalized->getStepRecurrence(SE);
1400   const SCEV *PostLoopScale = nullptr;
1401   if (!SE.dominates(Step, L->getHeader())) {
1402     PostLoopScale = Step;
1403     Step = SE.getConstant(Normalized->getType(), 1);
1404     if (!Start->isZero()) {
1405         // The normalization below assumes that Start is constant zero, so if
1406         // it isn't re-associate Start to PostLoopOffset.
1407         assert(!PostLoopOffset && "Start not-null but PostLoopOffset set?");
1408         PostLoopOffset = Start;
1409         Start = SE.getConstant(Normalized->getType(), 0);
1410     }
1411     Normalized =
1412       cast<SCEVAddRecExpr>(SE.getAddRecExpr(
1413                              Start, Step, Normalized->getLoop(),
1414                              Normalized->getNoWrapFlags(SCEV::FlagNW)));
1415   }
1416 
1417   // Expand the core addrec. If we need post-loop scaling, force it to
1418   // expand to an integer type to avoid the need for additional casting.
1419   Type *ExpandTy = PostLoopScale ? IntTy : STy;
1420   // We can't use a pointer type for the addrec if the pointer type is
1421   // non-integral.
1422   Type *AddRecPHIExpandTy =
1423       DL.isNonIntegralPointerType(STy) ? Normalized->getType() : ExpandTy;
1424 
1425   // In some cases, we decide to reuse an existing phi node but need to truncate
1426   // it and/or invert the step.
1427   Type *TruncTy = nullptr;
1428   bool InvertStep = false;
1429   PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy,
1430                                           IntTy, TruncTy, InvertStep);
1431 
1432   // Accommodate post-inc mode, if necessary.
1433   Value *Result;
1434   if (!PostIncLoops.count(L))
1435     Result = PN;
1436   else {
1437     // In PostInc mode, use the post-incremented value.
1438     BasicBlock *LatchBlock = L->getLoopLatch();
1439     assert(LatchBlock && "PostInc mode requires a unique loop latch!");
1440     Result = PN->getIncomingValueForBlock(LatchBlock);
1441 
1442     // We might be introducing a new use of the post-inc IV that is not poison
1443     // safe, in which case we should drop poison generating flags. Only keep
1444     // those flags for which SCEV has proven that they always hold.
1445     if (isa<OverflowingBinaryOperator>(Result)) {
1446       auto *I = cast<Instruction>(Result);
1447       if (!S->hasNoUnsignedWrap())
1448         I->setHasNoUnsignedWrap(false);
1449       if (!S->hasNoSignedWrap())
1450         I->setHasNoSignedWrap(false);
1451     }
1452 
1453     // For an expansion to use the postinc form, the client must call
1454     // expandCodeFor with an InsertPoint that is either outside the PostIncLoop
1455     // or dominated by IVIncInsertPos.
1456     if (isa<Instruction>(Result) &&
1457         !SE.DT.dominates(cast<Instruction>(Result),
1458                          &*Builder.GetInsertPoint())) {
1459       // The induction variable's postinc expansion does not dominate this use.
1460       // IVUsers tries to prevent this case, so it is rare. However, it can
1461       // happen when an IVUser outside the loop is not dominated by the latch
1462       // block. Adjusting IVIncInsertPos before expansion begins cannot handle
1463       // all cases. Consider a phi outside whose operand is replaced during
1464       // expansion with the value of the postinc user. Without fundamentally
1465       // changing the way postinc users are tracked, the only remedy is
1466       // inserting an extra IV increment. StepV might fold into PostLoopOffset,
1467       // but hopefully expandCodeFor handles that.
1468       bool useSubtract =
1469         !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1470       if (useSubtract)
1471         Step = SE.getNegativeSCEV(Step);
1472       Value *StepV;
1473       {
1474         // Expand the step somewhere that dominates the loop header.
1475         SCEVInsertPointGuard Guard(Builder, this);
1476         StepV = expandCodeForImpl(
1477             Step, IntTy, &*L->getHeader()->getFirstInsertionPt(), false);
1478       }
1479       Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1480     }
1481   }
1482 
1483   // We have decided to reuse an induction variable of a dominating loop. Apply
1484   // truncation and/or inversion of the step.
1485   if (TruncTy) {
1486     Type *ResTy = Result->getType();
1487     // Normalize the result type.
1488     if (ResTy != SE.getEffectiveSCEVType(ResTy))
1489       Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy));
1490     // Truncate the result.
1491     if (TruncTy != Result->getType())
1492       Result = Builder.CreateTrunc(Result, TruncTy);
1493 
1494     // Invert the result.
1495     if (InvertStep)
1496       Result = Builder.CreateSub(
1497           expandCodeForImpl(Normalized->getStart(), TruncTy, false), Result);
1498   }
1499 
1500   // Re-apply any non-loop-dominating scale.
1501   if (PostLoopScale) {
1502     assert(S->isAffine() && "Can't linearly scale non-affine recurrences.");
1503     Result = InsertNoopCastOfTo(Result, IntTy);
1504     Result = Builder.CreateMul(Result,
1505                                expandCodeForImpl(PostLoopScale, IntTy, false));
1506   }
1507 
1508   // Re-apply any non-loop-dominating offset.
1509   if (PostLoopOffset) {
1510     if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
1511       if (Result->getType()->isIntegerTy()) {
1512         Value *Base = expandCodeForImpl(PostLoopOffset, ExpandTy, false);
1513         Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy, Base);
1514       } else {
1515         Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result);
1516       }
1517     } else {
1518       Result = InsertNoopCastOfTo(Result, IntTy);
1519       Result = Builder.CreateAdd(
1520           Result, expandCodeForImpl(PostLoopOffset, IntTy, false));
1521     }
1522   }
1523 
1524   return Result;
1525 }
1526 
1527 Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
1528   // In canonical mode we compute the addrec as an expression of a canonical IV
1529   // using evaluateAtIteration and expand the resulting SCEV expression. This
1530   // way we avoid introducing new IVs to carry on the comutation of the addrec
1531   // throughout the loop.
1532   //
1533   // For nested addrecs evaluateAtIteration might need a canonical IV of a
1534   // type wider than the addrec itself. Emitting a canonical IV of the
1535   // proper type might produce non-legal types, for example expanding an i64
1536   // {0,+,2,+,1} addrec would need an i65 canonical IV. To avoid this just fall
1537   // back to non-canonical mode for nested addrecs.
1538   if (!CanonicalMode || (S->getNumOperands() > 2))
1539     return expandAddRecExprLiterally(S);
1540 
1541   Type *Ty = SE.getEffectiveSCEVType(S->getType());
1542   const Loop *L = S->getLoop();
1543 
1544   // First check for an existing canonical IV in a suitable type.
1545   PHINode *CanonicalIV = nullptr;
1546   if (PHINode *PN = L->getCanonicalInductionVariable())
1547     if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))
1548       CanonicalIV = PN;
1549 
1550   // Rewrite an AddRec in terms of the canonical induction variable, if
1551   // its type is more narrow.
1552   if (CanonicalIV &&
1553       SE.getTypeSizeInBits(CanonicalIV->getType()) >
1554       SE.getTypeSizeInBits(Ty)) {
1555     SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
1556     for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
1557       NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
1558     Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
1559                                        S->getNoWrapFlags(SCEV::FlagNW)));
1560     BasicBlock::iterator NewInsertPt =
1561         findInsertPointAfter(cast<Instruction>(V), &*Builder.GetInsertPoint());
1562     V = expandCodeForImpl(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
1563                           &*NewInsertPt, false);
1564     return V;
1565   }
1566 
1567   // {X,+,F} --> X + {0,+,F}
1568   if (!S->getStart()->isZero()) {
1569     SmallVector<const SCEV *, 4> NewOps(S->operands());
1570     NewOps[0] = SE.getConstant(Ty, 0);
1571     const SCEV *Rest = SE.getAddRecExpr(NewOps, L,
1572                                         S->getNoWrapFlags(SCEV::FlagNW));
1573 
1574     // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the
1575     // comments on expandAddToGEP for details.
1576     const SCEV *Base = S->getStart();
1577     // Dig into the expression to find the pointer base for a GEP.
1578     const SCEV *ExposedRest = Rest;
1579     ExposePointerBase(Base, ExposedRest, SE);
1580     // If we found a pointer, expand the AddRec with a GEP.
1581     if (PointerType *PTy = dyn_cast<PointerType>(Base->getType())) {
1582       // Make sure the Base isn't something exotic, such as a multiplied
1583       // or divided pointer value. In those cases, the result type isn't
1584       // actually a pointer type.
1585       if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) {
1586         Value *StartV = expand(Base);
1587         assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!");
1588         return expandAddToGEP(ExposedRest, PTy, Ty, StartV);
1589       }
1590     }
1591 
1592     // Just do a normal add. Pre-expand the operands to suppress folding.
1593     //
1594     // The LHS and RHS values are factored out of the expand call to make the
1595     // output independent of the argument evaluation order.
1596     const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart()));
1597     const SCEV *AddExprRHS = SE.getUnknown(expand(Rest));
1598     return expand(SE.getAddExpr(AddExprLHS, AddExprRHS));
1599   }
1600 
1601   // If we don't yet have a canonical IV, create one.
1602   if (!CanonicalIV) {
1603     // Create and insert the PHI node for the induction variable in the
1604     // specified loop.
1605     BasicBlock *Header = L->getHeader();
1606     pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1607     CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar",
1608                                   &Header->front());
1609     rememberInstruction(CanonicalIV);
1610 
1611     SmallSet<BasicBlock *, 4> PredSeen;
1612     Constant *One = ConstantInt::get(Ty, 1);
1613     for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1614       BasicBlock *HP = *HPI;
1615       if (!PredSeen.insert(HP).second) {
1616         // There must be an incoming value for each predecessor, even the
1617         // duplicates!
1618         CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP);
1619         continue;
1620       }
1621 
1622       if (L->contains(HP)) {
1623         // Insert a unit add instruction right before the terminator
1624         // corresponding to the back-edge.
1625         Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One,
1626                                                      "indvar.next",
1627                                                      HP->getTerminator());
1628         Add->setDebugLoc(HP->getTerminator()->getDebugLoc());
1629         rememberInstruction(Add);
1630         CanonicalIV->addIncoming(Add, HP);
1631       } else {
1632         CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP);
1633       }
1634     }
1635   }
1636 
1637   // {0,+,1} --> Insert a canonical induction variable into the loop!
1638   if (S->isAffine() && S->getOperand(1)->isOne()) {
1639     assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&
1640            "IVs with types different from the canonical IV should "
1641            "already have been handled!");
1642     return CanonicalIV;
1643   }
1644 
1645   // {0,+,F} --> {0,+,1} * F
1646 
1647   // If this is a simple linear addrec, emit it now as a special case.
1648   if (S->isAffine())    // {0,+,F} --> i*F
1649     return
1650       expand(SE.getTruncateOrNoop(
1651         SE.getMulExpr(SE.getUnknown(CanonicalIV),
1652                       SE.getNoopOrAnyExtend(S->getOperand(1),
1653                                             CanonicalIV->getType())),
1654         Ty));
1655 
1656   // If this is a chain of recurrences, turn it into a closed form, using the
1657   // folders, then expandCodeFor the closed form.  This allows the folders to
1658   // simplify the expression without having to build a bunch of special code
1659   // into this folder.
1660   const SCEV *IH = SE.getUnknown(CanonicalIV);   // Get I as a "symbolic" SCEV.
1661 
1662   // Promote S up to the canonical IV type, if the cast is foldable.
1663   const SCEV *NewS = S;
1664   const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType());
1665   if (isa<SCEVAddRecExpr>(Ext))
1666     NewS = Ext;
1667 
1668   const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
1669   //cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
1670 
1671   // Truncate the result down to the original type, if needed.
1672   const SCEV *T = SE.getTruncateOrNoop(V, Ty);
1673   return expand(T);
1674 }
1675 
1676 Value *SCEVExpander::visitPtrToIntExpr(const SCEVPtrToIntExpr *S) {
1677   Value *V =
1678       expandCodeForImpl(S->getOperand(), S->getOperand()->getType(), false);
1679   return Builder.CreatePtrToInt(V, S->getType());
1680 }
1681 
1682 Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {
1683   Type *Ty = SE.getEffectiveSCEVType(S->getType());
1684   Value *V = expandCodeForImpl(
1685       S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1686       false);
1687   return Builder.CreateTrunc(V, Ty);
1688 }
1689 
1690 Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {
1691   Type *Ty = SE.getEffectiveSCEVType(S->getType());
1692   Value *V = expandCodeForImpl(
1693       S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1694       false);
1695   return Builder.CreateZExt(V, Ty);
1696 }
1697 
1698 Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
1699   Type *Ty = SE.getEffectiveSCEVType(S->getType());
1700   Value *V = expandCodeForImpl(
1701       S->getOperand(), SE.getEffectiveSCEVType(S->getOperand()->getType()),
1702       false);
1703   return Builder.CreateSExt(V, Ty);
1704 }
1705 
1706 Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
1707   Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
1708   Type *Ty = LHS->getType();
1709   for (int i = S->getNumOperands()-2; i >= 0; --i) {
1710     // In the case of mixed integer and pointer types, do the
1711     // rest of the comparisons as integer.
1712     Type *OpTy = S->getOperand(i)->getType();
1713     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1714       Ty = SE.getEffectiveSCEVType(Ty);
1715       LHS = InsertNoopCastOfTo(LHS, Ty);
1716     }
1717     Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1718     Value *Sel;
1719     if (Ty->isIntegerTy())
1720       Sel = Builder.CreateIntrinsic(Intrinsic::smax, {Ty}, {LHS, RHS},
1721                                     /*FMFSource=*/nullptr, "smax");
1722     else {
1723       Value *ICmp = Builder.CreateICmpSGT(LHS, RHS);
1724       Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax");
1725     }
1726     LHS = Sel;
1727   }
1728   // In the case of mixed integer and pointer types, cast the
1729   // final result back to the pointer type.
1730   if (LHS->getType() != S->getType())
1731     LHS = InsertNoopCastOfTo(LHS, S->getType());
1732   return LHS;
1733 }
1734 
1735 Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
1736   Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
1737   Type *Ty = LHS->getType();
1738   for (int i = S->getNumOperands()-2; i >= 0; --i) {
1739     // In the case of mixed integer and pointer types, do the
1740     // rest of the comparisons as integer.
1741     Type *OpTy = S->getOperand(i)->getType();
1742     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1743       Ty = SE.getEffectiveSCEVType(Ty);
1744       LHS = InsertNoopCastOfTo(LHS, Ty);
1745     }
1746     Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1747     Value *Sel;
1748     if (Ty->isIntegerTy())
1749       Sel = Builder.CreateIntrinsic(Intrinsic::umax, {Ty}, {LHS, RHS},
1750                                     /*FMFSource=*/nullptr, "umax");
1751     else {
1752       Value *ICmp = Builder.CreateICmpUGT(LHS, RHS);
1753       Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax");
1754     }
1755     LHS = Sel;
1756   }
1757   // In the case of mixed integer and pointer types, cast the
1758   // final result back to the pointer type.
1759   if (LHS->getType() != S->getType())
1760     LHS = InsertNoopCastOfTo(LHS, S->getType());
1761   return LHS;
1762 }
1763 
1764 Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) {
1765   Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
1766   Type *Ty = LHS->getType();
1767   for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1768     // In the case of mixed integer and pointer types, do the
1769     // rest of the comparisons as integer.
1770     Type *OpTy = S->getOperand(i)->getType();
1771     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1772       Ty = SE.getEffectiveSCEVType(Ty);
1773       LHS = InsertNoopCastOfTo(LHS, Ty);
1774     }
1775     Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1776     Value *Sel;
1777     if (Ty->isIntegerTy())
1778       Sel = Builder.CreateIntrinsic(Intrinsic::smin, {Ty}, {LHS, RHS},
1779                                     /*FMFSource=*/nullptr, "smin");
1780     else {
1781       Value *ICmp = Builder.CreateICmpSLT(LHS, RHS);
1782       Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smin");
1783     }
1784     LHS = Sel;
1785   }
1786   // In the case of mixed integer and pointer types, cast the
1787   // final result back to the pointer type.
1788   if (LHS->getType() != S->getType())
1789     LHS = InsertNoopCastOfTo(LHS, S->getType());
1790   return LHS;
1791 }
1792 
1793 Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {
1794   Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
1795   Type *Ty = LHS->getType();
1796   for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1797     // In the case of mixed integer and pointer types, do the
1798     // rest of the comparisons as integer.
1799     Type *OpTy = S->getOperand(i)->getType();
1800     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1801       Ty = SE.getEffectiveSCEVType(Ty);
1802       LHS = InsertNoopCastOfTo(LHS, Ty);
1803     }
1804     Value *RHS = expandCodeForImpl(S->getOperand(i), Ty, false);
1805     Value *Sel;
1806     if (Ty->isIntegerTy())
1807       Sel = Builder.CreateIntrinsic(Intrinsic::umin, {Ty}, {LHS, RHS},
1808                                     /*FMFSource=*/nullptr, "umin");
1809     else {
1810       Value *ICmp = Builder.CreateICmpULT(LHS, RHS);
1811       Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umin");
1812     }
1813     LHS = Sel;
1814   }
1815   // In the case of mixed integer and pointer types, cast the
1816   // final result back to the pointer type.
1817   if (LHS->getType() != S->getType())
1818     LHS = InsertNoopCastOfTo(LHS, S->getType());
1819   return LHS;
1820 }
1821 
1822 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty,
1823                                        Instruction *IP, bool Root) {
1824   setInsertPoint(IP);
1825   Value *V = expandCodeForImpl(SH, Ty, Root);
1826   return V;
1827 }
1828 
1829 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root) {
1830   // Expand the code for this SCEV.
1831   Value *V = expand(SH);
1832 
1833   if (PreserveLCSSA) {
1834     if (auto *Inst = dyn_cast<Instruction>(V)) {
1835       // Create a temporary instruction to at the current insertion point, so we
1836       // can hand it off to the helper to create LCSSA PHIs if required for the
1837       // new use.
1838       // FIXME: Ideally formLCSSAForInstructions (used in fixupLCSSAFormFor)
1839       // would accept a insertion point and return an LCSSA phi for that
1840       // insertion point, so there is no need to insert & remove the temporary
1841       // instruction.
1842       Instruction *Tmp;
1843       if (Inst->getType()->isIntegerTy())
1844         Tmp =
1845             cast<Instruction>(Builder.CreateAdd(Inst, Inst, "tmp.lcssa.user"));
1846       else {
1847         assert(Inst->getType()->isPointerTy());
1848         Tmp = cast<Instruction>(
1849             Builder.CreateGEP(Inst, Builder.getInt32(1), "tmp.lcssa.user"));
1850       }
1851       V = fixupLCSSAFormFor(Tmp, 0);
1852 
1853       // Clean up temporary instruction.
1854       InsertedValues.erase(Tmp);
1855       InsertedPostIncValues.erase(Tmp);
1856       Tmp->eraseFromParent();
1857     }
1858   }
1859 
1860   InsertedExpressions[std::make_pair(SH, &*Builder.GetInsertPoint())] = V;
1861   if (Ty) {
1862     assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&
1863            "non-trivial casts should be done with the SCEVs directly!");
1864     V = InsertNoopCastOfTo(V, Ty);
1865   }
1866   return V;
1867 }
1868 
1869 ScalarEvolution::ValueOffsetPair
1870 SCEVExpander::FindValueInExprValueMap(const SCEV *S,
1871                                       const Instruction *InsertPt) {
1872   SetVector<ScalarEvolution::ValueOffsetPair> *Set = SE.getSCEVValues(S);
1873   // If the expansion is not in CanonicalMode, and the SCEV contains any
1874   // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.
1875   if (CanonicalMode || !SE.containsAddRecurrence(S)) {
1876     // If S is scConstant, it may be worse to reuse an existing Value.
1877     if (S->getSCEVType() != scConstant && Set) {
1878       // Choose a Value from the set which dominates the insertPt.
1879       // insertPt should be inside the Value's parent loop so as not to break
1880       // the LCSSA form.
1881       for (auto const &VOPair : *Set) {
1882         Value *V = VOPair.first;
1883         ConstantInt *Offset = VOPair.second;
1884         Instruction *EntInst = nullptr;
1885         if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) &&
1886             S->getType() == V->getType() &&
1887             EntInst->getFunction() == InsertPt->getFunction() &&
1888             SE.DT.dominates(EntInst, InsertPt) &&
1889             (SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
1890              SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))
1891           return {V, Offset};
1892       }
1893     }
1894   }
1895   return {nullptr, nullptr};
1896 }
1897 
1898 // The expansion of SCEV will either reuse a previous Value in ExprValueMap,
1899 // or expand the SCEV literally. Specifically, if the expansion is in LSRMode,
1900 // and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded
1901 // literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,
1902 // the expansion will try to reuse Value from ExprValueMap, and only when it
1903 // fails, expand the SCEV literally.
1904 Value *SCEVExpander::expand(const SCEV *S) {
1905   // Compute an insertion point for this SCEV object. Hoist the instructions
1906   // as far out in the loop nest as possible.
1907   Instruction *InsertPt = &*Builder.GetInsertPoint();
1908 
1909   // We can move insertion point only if there is no div or rem operations
1910   // otherwise we are risky to move it over the check for zero denominator.
1911   auto SafeToHoist = [](const SCEV *S) {
1912     return !SCEVExprContains(S, [](const SCEV *S) {
1913               if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) {
1914                 if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS()))
1915                   // Division by non-zero constants can be hoisted.
1916                   return SC->getValue()->isZero();
1917                 // All other divisions should not be moved as they may be
1918                 // divisions by zero and should be kept within the
1919                 // conditions of the surrounding loops that guard their
1920                 // execution (see PR35406).
1921                 return true;
1922               }
1923               return false;
1924             });
1925   };
1926   if (SafeToHoist(S)) {
1927     for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
1928          L = L->getParentLoop()) {
1929       if (SE.isLoopInvariant(S, L)) {
1930         if (!L) break;
1931         if (BasicBlock *Preheader = L->getLoopPreheader())
1932           InsertPt = Preheader->getTerminator();
1933         else
1934           // LSR sets the insertion point for AddRec start/step values to the
1935           // block start to simplify value reuse, even though it's an invalid
1936           // position. SCEVExpander must correct for this in all cases.
1937           InsertPt = &*L->getHeader()->getFirstInsertionPt();
1938       } else {
1939         // If the SCEV is computable at this level, insert it into the header
1940         // after the PHIs (and after any other instructions that we've inserted
1941         // there) so that it is guaranteed to dominate any user inside the loop.
1942         if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
1943           InsertPt = &*L->getHeader()->getFirstInsertionPt();
1944 
1945         while (InsertPt->getIterator() != Builder.GetInsertPoint() &&
1946                (isInsertedInstruction(InsertPt) ||
1947                 isa<DbgInfoIntrinsic>(InsertPt))) {
1948           InsertPt = &*std::next(InsertPt->getIterator());
1949         }
1950         break;
1951       }
1952     }
1953   }
1954 
1955   // Check to see if we already expanded this here.
1956   auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
1957   if (I != InsertedExpressions.end())
1958     return I->second;
1959 
1960   SCEVInsertPointGuard Guard(Builder, this);
1961   Builder.SetInsertPoint(InsertPt);
1962 
1963   // Expand the expression into instructions.
1964   ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt);
1965   Value *V = VO.first;
1966 
1967   if (!V)
1968     V = visit(S);
1969   else if (VO.second) {
1970     if (PointerType *Vty = dyn_cast<PointerType>(V->getType())) {
1971       Type *Ety = Vty->getPointerElementType();
1972       int64_t Offset = VO.second->getSExtValue();
1973       int64_t ESize = SE.getTypeSizeInBits(Ety);
1974       if ((Offset * 8) % ESize == 0) {
1975         ConstantInt *Idx =
1976             ConstantInt::getSigned(VO.second->getType(), -(Offset * 8) / ESize);
1977         V = Builder.CreateGEP(Ety, V, Idx, "scevgep");
1978       } else {
1979         ConstantInt *Idx =
1980             ConstantInt::getSigned(VO.second->getType(), -Offset);
1981         unsigned AS = Vty->getAddressSpace();
1982         V = Builder.CreateBitCast(V, Type::getInt8PtrTy(SE.getContext(), AS));
1983         V = Builder.CreateGEP(Type::getInt8Ty(SE.getContext()), V, Idx,
1984                               "uglygep");
1985         V = Builder.CreateBitCast(V, Vty);
1986       }
1987     } else {
1988       V = Builder.CreateSub(V, VO.second);
1989     }
1990   }
1991   // Remember the expanded value for this SCEV at this location.
1992   //
1993   // This is independent of PostIncLoops. The mapped value simply materializes
1994   // the expression at this insertion point. If the mapped value happened to be
1995   // a postinc expansion, it could be reused by a non-postinc user, but only if
1996   // its insertion point was already at the head of the loop.
1997   InsertedExpressions[std::make_pair(S, InsertPt)] = V;
1998   return V;
1999 }
2000 
2001 void SCEVExpander::rememberInstruction(Value *I) {
2002   auto DoInsert = [this](Value *V) {
2003     if (!PostIncLoops.empty())
2004       InsertedPostIncValues.insert(V);
2005     else
2006       InsertedValues.insert(V);
2007   };
2008   DoInsert(I);
2009 
2010   if (!PreserveLCSSA)
2011     return;
2012 
2013   if (auto *Inst = dyn_cast<Instruction>(I)) {
2014     // A new instruction has been added, which might introduce new uses outside
2015     // a defining loop. Fix LCSSA from for each operand of the new instruction,
2016     // if required.
2017     for (unsigned OpIdx = 0, OpEnd = Inst->getNumOperands(); OpIdx != OpEnd;
2018          OpIdx++)
2019       fixupLCSSAFormFor(Inst, OpIdx);
2020   }
2021 }
2022 
2023 /// replaceCongruentIVs - Check for congruent phis in this loop header and
2024 /// replace them with their most canonical representative. Return the number of
2025 /// phis eliminated.
2026 ///
2027 /// This does not depend on any SCEVExpander state but should be used in
2028 /// the same context that SCEVExpander is used.
2029 unsigned
2030 SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
2031                                   SmallVectorImpl<WeakTrackingVH> &DeadInsts,
2032                                   const TargetTransformInfo *TTI) {
2033   // Find integer phis in order of increasing width.
2034   SmallVector<PHINode*, 8> Phis;
2035   for (PHINode &PN : L->getHeader()->phis())
2036     Phis.push_back(&PN);
2037 
2038   if (TTI)
2039     llvm::sort(Phis, [](Value *LHS, Value *RHS) {
2040       // Put pointers at the back and make sure pointer < pointer = false.
2041       if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
2042         return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();
2043       return RHS->getType()->getPrimitiveSizeInBits().getFixedSize() <
2044              LHS->getType()->getPrimitiveSizeInBits().getFixedSize();
2045     });
2046 
2047   unsigned NumElim = 0;
2048   DenseMap<const SCEV *, PHINode *> ExprToIVMap;
2049   // Process phis from wide to narrow. Map wide phis to their truncation
2050   // so narrow phis can reuse them.
2051   for (PHINode *Phi : Phis) {
2052     auto SimplifyPHINode = [&](PHINode *PN) -> Value * {
2053       if (Value *V = SimplifyInstruction(PN, {DL, &SE.TLI, &SE.DT, &SE.AC}))
2054         return V;
2055       if (!SE.isSCEVable(PN->getType()))
2056         return nullptr;
2057       auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));
2058       if (!Const)
2059         return nullptr;
2060       return Const->getValue();
2061     };
2062 
2063     // Fold constant phis. They may be congruent to other constant phis and
2064     // would confuse the logic below that expects proper IVs.
2065     if (Value *V = SimplifyPHINode(Phi)) {
2066       if (V->getType() != Phi->getType())
2067         continue;
2068       Phi->replaceAllUsesWith(V);
2069       DeadInsts.emplace_back(Phi);
2070       ++NumElim;
2071       DEBUG_WITH_TYPE(DebugType, dbgs()
2072                       << "INDVARS: Eliminated constant iv: " << *Phi << '\n');
2073       continue;
2074     }
2075 
2076     if (!SE.isSCEVable(Phi->getType()))
2077       continue;
2078 
2079     PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
2080     if (!OrigPhiRef) {
2081       OrigPhiRef = Phi;
2082       if (Phi->getType()->isIntegerTy() && TTI &&
2083           TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
2084         // This phi can be freely truncated to the narrowest phi type. Map the
2085         // truncated expression to it so it will be reused for narrow types.
2086         const SCEV *TruncExpr =
2087           SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType());
2088         ExprToIVMap[TruncExpr] = Phi;
2089       }
2090       continue;
2091     }
2092 
2093     // Replacing a pointer phi with an integer phi or vice-versa doesn't make
2094     // sense.
2095     if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy())
2096       continue;
2097 
2098     if (BasicBlock *LatchBlock = L->getLoopLatch()) {
2099       Instruction *OrigInc = dyn_cast<Instruction>(
2100           OrigPhiRef->getIncomingValueForBlock(LatchBlock));
2101       Instruction *IsomorphicInc =
2102           dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
2103 
2104       if (OrigInc && IsomorphicInc) {
2105         // If this phi has the same width but is more canonical, replace the
2106         // original with it. As part of the "more canonical" determination,
2107         // respect a prior decision to use an IV chain.
2108         if (OrigPhiRef->getType() == Phi->getType() &&
2109             !(ChainedPhis.count(Phi) ||
2110               isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) &&
2111             (ChainedPhis.count(Phi) ||
2112              isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
2113           std::swap(OrigPhiRef, Phi);
2114           std::swap(OrigInc, IsomorphicInc);
2115         }
2116         // Replacing the congruent phi is sufficient because acyclic
2117         // redundancy elimination, CSE/GVN, should handle the
2118         // rest. However, once SCEV proves that a phi is congruent,
2119         // it's often the head of an IV user cycle that is isomorphic
2120         // with the original phi. It's worth eagerly cleaning up the
2121         // common case of a single IV increment so that DeleteDeadPHIs
2122         // can remove cycles that had postinc uses.
2123         const SCEV *TruncExpr =
2124             SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->getType());
2125         if (OrigInc != IsomorphicInc &&
2126             TruncExpr == SE.getSCEV(IsomorphicInc) &&
2127             SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc) &&
2128             hoistIVInc(OrigInc, IsomorphicInc)) {
2129           DEBUG_WITH_TYPE(DebugType,
2130                           dbgs() << "INDVARS: Eliminated congruent iv.inc: "
2131                                  << *IsomorphicInc << '\n');
2132           Value *NewInc = OrigInc;
2133           if (OrigInc->getType() != IsomorphicInc->getType()) {
2134             Instruction *IP = nullptr;
2135             if (PHINode *PN = dyn_cast<PHINode>(OrigInc))
2136               IP = &*PN->getParent()->getFirstInsertionPt();
2137             else
2138               IP = OrigInc->getNextNode();
2139 
2140             IRBuilder<> Builder(IP);
2141             Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc());
2142             NewInc = Builder.CreateTruncOrBitCast(
2143                 OrigInc, IsomorphicInc->getType(), IVName);
2144           }
2145           IsomorphicInc->replaceAllUsesWith(NewInc);
2146           DeadInsts.emplace_back(IsomorphicInc);
2147         }
2148       }
2149     }
2150     DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Eliminated congruent iv: "
2151                                       << *Phi << '\n');
2152     DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Original iv: "
2153                                       << *OrigPhiRef << '\n');
2154     ++NumElim;
2155     Value *NewIV = OrigPhiRef;
2156     if (OrigPhiRef->getType() != Phi->getType()) {
2157       IRBuilder<> Builder(&*L->getHeader()->getFirstInsertionPt());
2158       Builder.SetCurrentDebugLocation(Phi->getDebugLoc());
2159       NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);
2160     }
2161     Phi->replaceAllUsesWith(NewIV);
2162     DeadInsts.emplace_back(Phi);
2163   }
2164   return NumElim;
2165 }
2166 
2167 Optional<ScalarEvolution::ValueOffsetPair>
2168 SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At,
2169                                           Loop *L) {
2170   using namespace llvm::PatternMatch;
2171 
2172   SmallVector<BasicBlock *, 4> ExitingBlocks;
2173   L->getExitingBlocks(ExitingBlocks);
2174 
2175   // Look for suitable value in simple conditions at the loop exits.
2176   for (BasicBlock *BB : ExitingBlocks) {
2177     ICmpInst::Predicate Pred;
2178     Instruction *LHS, *RHS;
2179 
2180     if (!match(BB->getTerminator(),
2181                m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
2182                     m_BasicBlock(), m_BasicBlock())))
2183       continue;
2184 
2185     if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
2186       return ScalarEvolution::ValueOffsetPair(LHS, nullptr);
2187 
2188     if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
2189       return ScalarEvolution::ValueOffsetPair(RHS, nullptr);
2190   }
2191 
2192   // Use expand's logic which is used for reusing a previous Value in
2193   // ExprValueMap.
2194   ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At);
2195   if (VO.first)
2196     return VO;
2197 
2198   // There is potential to make this significantly smarter, but this simple
2199   // heuristic already gets some interesting cases.
2200 
2201   // Can not find suitable value.
2202   return None;
2203 }
2204 
2205 template<typename T> static InstructionCost costAndCollectOperands(
2206   const SCEVOperand &WorkItem, const TargetTransformInfo &TTI,
2207   TargetTransformInfo::TargetCostKind CostKind,
2208   SmallVectorImpl<SCEVOperand> &Worklist) {
2209 
2210   const T *S = cast<T>(WorkItem.S);
2211   InstructionCost Cost = 0;
2212   // Object to help map SCEV operands to expanded IR instructions.
2213   struct OperationIndices {
2214     OperationIndices(unsigned Opc, size_t min, size_t max) :
2215       Opcode(Opc), MinIdx(min), MaxIdx(max) { }
2216     unsigned Opcode;
2217     size_t MinIdx;
2218     size_t MaxIdx;
2219   };
2220 
2221   // Collect the operations of all the instructions that will be needed to
2222   // expand the SCEVExpr. This is so that when we come to cost the operands,
2223   // we know what the generated user(s) will be.
2224   SmallVector<OperationIndices, 2> Operations;
2225 
2226   auto CastCost = [&](unsigned Opcode) -> InstructionCost {
2227     Operations.emplace_back(Opcode, 0, 0);
2228     return TTI.getCastInstrCost(Opcode, S->getType(),
2229                                 S->getOperand(0)->getType(),
2230                                 TTI::CastContextHint::None, CostKind);
2231   };
2232 
2233   auto ArithCost = [&](unsigned Opcode, unsigned NumRequired,
2234                        unsigned MinIdx = 0,
2235                        unsigned MaxIdx = 1) -> InstructionCost {
2236     Operations.emplace_back(Opcode, MinIdx, MaxIdx);
2237     return NumRequired *
2238       TTI.getArithmeticInstrCost(Opcode, S->getType(), CostKind);
2239   };
2240 
2241   auto CmpSelCost = [&](unsigned Opcode, unsigned NumRequired, unsigned MinIdx,
2242                         unsigned MaxIdx) -> InstructionCost {
2243     Operations.emplace_back(Opcode, MinIdx, MaxIdx);
2244     Type *OpType = S->getOperand(0)->getType();
2245     return NumRequired * TTI.getCmpSelInstrCost(
2246                              Opcode, OpType, CmpInst::makeCmpResultType(OpType),
2247                              CmpInst::BAD_ICMP_PREDICATE, CostKind);
2248   };
2249 
2250   switch (S->getSCEVType()) {
2251   case scCouldNotCompute:
2252     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
2253   case scUnknown:
2254   case scConstant:
2255     return 0;
2256   case scPtrToInt:
2257     Cost = CastCost(Instruction::PtrToInt);
2258     break;
2259   case scTruncate:
2260     Cost = CastCost(Instruction::Trunc);
2261     break;
2262   case scZeroExtend:
2263     Cost = CastCost(Instruction::ZExt);
2264     break;
2265   case scSignExtend:
2266     Cost = CastCost(Instruction::SExt);
2267     break;
2268   case scUDivExpr: {
2269     unsigned Opcode = Instruction::UDiv;
2270     if (auto *SC = dyn_cast<SCEVConstant>(S->getOperand(1)))
2271       if (SC->getAPInt().isPowerOf2())
2272         Opcode = Instruction::LShr;
2273     Cost = ArithCost(Opcode, 1);
2274     break;
2275   }
2276   case scAddExpr:
2277     Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1);
2278     break;
2279   case scMulExpr:
2280     // TODO: this is a very pessimistic cost modelling for Mul,
2281     // because of Bin Pow algorithm actually used by the expander,
2282     // see SCEVExpander::visitMulExpr(), ExpandOpBinPowN().
2283     Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1);
2284     break;
2285   case scSMaxExpr:
2286   case scUMaxExpr:
2287   case scSMinExpr:
2288   case scUMinExpr: {
2289     // FIXME: should this ask the cost for Intrinsic's?
2290     Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);
2291     Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2);
2292     break;
2293   }
2294   case scAddRecExpr: {
2295     // In this polynominal, we may have some zero operands, and we shouldn't
2296     // really charge for those. So how many non-zero coeffients are there?
2297     int NumTerms = llvm::count_if(S->operands(), [](const SCEV *Op) {
2298                                     return !Op->isZero();
2299                                   });
2300 
2301     assert(NumTerms >= 1 && "Polynominal should have at least one term.");
2302     assert(!(*std::prev(S->operands().end()))->isZero() &&
2303            "Last operand should not be zero");
2304 
2305     // Ignoring constant term (operand 0), how many of the coeffients are u> 1?
2306     int NumNonZeroDegreeNonOneTerms =
2307       llvm::count_if(S->operands(), [](const SCEV *Op) {
2308                       auto *SConst = dyn_cast<SCEVConstant>(Op);
2309                       return !SConst || SConst->getAPInt().ugt(1);
2310                     });
2311 
2312     // Much like with normal add expr, the polynominal will require
2313     // one less addition than the number of it's terms.
2314     InstructionCost AddCost = ArithCost(Instruction::Add, NumTerms - 1,
2315                                         /*MinIdx*/ 1, /*MaxIdx*/ 1);
2316     // Here, *each* one of those will require a multiplication.
2317     InstructionCost MulCost =
2318         ArithCost(Instruction::Mul, NumNonZeroDegreeNonOneTerms);
2319     Cost = AddCost + MulCost;
2320 
2321     // What is the degree of this polynominal?
2322     int PolyDegree = S->getNumOperands() - 1;
2323     assert(PolyDegree >= 1 && "Should be at least affine.");
2324 
2325     // The final term will be:
2326     //   Op_{PolyDegree} * x ^ {PolyDegree}
2327     // Where  x ^ {PolyDegree}  will again require PolyDegree-1 mul operations.
2328     // Note that  x ^ {PolyDegree} = x * x ^ {PolyDegree-1}  so charging for
2329     // x ^ {PolyDegree}  will give us  x ^ {2} .. x ^ {PolyDegree-1}  for free.
2330     // FIXME: this is conservatively correct, but might be overly pessimistic.
2331     Cost += MulCost * (PolyDegree - 1);
2332     break;
2333   }
2334   }
2335 
2336   for (auto &CostOp : Operations) {
2337     for (auto SCEVOp : enumerate(S->operands())) {
2338       // Clamp the index to account for multiple IR operations being chained.
2339       size_t MinIdx = std::max(SCEVOp.index(), CostOp.MinIdx);
2340       size_t OpIdx = std::min(MinIdx, CostOp.MaxIdx);
2341       Worklist.emplace_back(CostOp.Opcode, OpIdx, SCEVOp.value());
2342     }
2343   }
2344   return Cost;
2345 }
2346 
2347 bool SCEVExpander::isHighCostExpansionHelper(
2348     const SCEVOperand &WorkItem, Loop *L, const Instruction &At,
2349     InstructionCost &Cost, unsigned Budget, const TargetTransformInfo &TTI,
2350     SmallPtrSetImpl<const SCEV *> &Processed,
2351     SmallVectorImpl<SCEVOperand> &Worklist) {
2352   if (Cost > Budget)
2353     return true; // Already run out of budget, give up.
2354 
2355   const SCEV *S = WorkItem.S;
2356   // Was the cost of expansion of this expression already accounted for?
2357   if (!isa<SCEVConstant>(S) && !Processed.insert(S).second)
2358     return false; // We have already accounted for this expression.
2359 
2360   // If we can find an existing value for this scev available at the point "At"
2361   // then consider the expression cheap.
2362   if (getRelatedExistingExpansion(S, &At, L))
2363     return false; // Consider the expression to be free.
2364 
2365   TargetTransformInfo::TargetCostKind CostKind =
2366       L->getHeader()->getParent()->hasMinSize()
2367           ? TargetTransformInfo::TCK_CodeSize
2368           : TargetTransformInfo::TCK_RecipThroughput;
2369 
2370   switch (S->getSCEVType()) {
2371   case scCouldNotCompute:
2372     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
2373   case scUnknown:
2374     // Assume to be zero-cost.
2375     return false;
2376   case scConstant: {
2377     // Only evalulate the costs of constants when optimizing for size.
2378     if (CostKind != TargetTransformInfo::TCK_CodeSize)
2379       return 0;
2380     const APInt &Imm = cast<SCEVConstant>(S)->getAPInt();
2381     Type *Ty = S->getType();
2382     Cost += TTI.getIntImmCostInst(
2383         WorkItem.ParentOpcode, WorkItem.OperandIdx, Imm, Ty, CostKind);
2384     return Cost > Budget;
2385   }
2386   case scTruncate:
2387   case scPtrToInt:
2388   case scZeroExtend:
2389   case scSignExtend: {
2390     Cost +=
2391         costAndCollectOperands<SCEVCastExpr>(WorkItem, TTI, CostKind, Worklist);
2392     return false; // Will answer upon next entry into this function.
2393   }
2394   case scUDivExpr: {
2395     // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
2396     // HowManyLessThans produced to compute a precise expression, rather than a
2397     // UDiv from the user's code. If we can't find a UDiv in the code with some
2398     // simple searching, we need to account for it's cost.
2399 
2400     // At the beginning of this function we already tried to find existing
2401     // value for plain 'S'. Now try to lookup 'S + 1' since it is common
2402     // pattern involving division. This is just a simple search heuristic.
2403     if (getRelatedExistingExpansion(
2404             SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &At, L))
2405       return false; // Consider it to be free.
2406 
2407     Cost +=
2408         costAndCollectOperands<SCEVUDivExpr>(WorkItem, TTI, CostKind, Worklist);
2409     return false; // Will answer upon next entry into this function.
2410   }
2411   case scAddExpr:
2412   case scMulExpr:
2413   case scUMaxExpr:
2414   case scSMaxExpr:
2415   case scUMinExpr:
2416   case scSMinExpr: {
2417     assert(cast<SCEVNAryExpr>(S)->getNumOperands() > 1 &&
2418            "Nary expr should have more than 1 operand.");
2419     // The simple nary expr will require one less op (or pair of ops)
2420     // than the number of it's terms.
2421     Cost +=
2422         costAndCollectOperands<SCEVNAryExpr>(WorkItem, TTI, CostKind, Worklist);
2423     return Cost > Budget;
2424   }
2425   case scAddRecExpr: {
2426     assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&
2427            "Polynomial should be at least linear");
2428     Cost += costAndCollectOperands<SCEVAddRecExpr>(
2429         WorkItem, TTI, CostKind, Worklist);
2430     return Cost > Budget;
2431   }
2432   }
2433   llvm_unreachable("Unknown SCEV kind!");
2434 }
2435 
2436 Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred,
2437                                             Instruction *IP) {
2438   assert(IP);
2439   switch (Pred->getKind()) {
2440   case SCEVPredicate::P_Union:
2441     return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);
2442   case SCEVPredicate::P_Equal:
2443     return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP);
2444   case SCEVPredicate::P_Wrap: {
2445     auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
2446     return expandWrapPredicate(AddRecPred, IP);
2447   }
2448   }
2449   llvm_unreachable("Unknown SCEV predicate type");
2450 }
2451 
2452 Value *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred,
2453                                           Instruction *IP) {
2454   Value *Expr0 =
2455       expandCodeForImpl(Pred->getLHS(), Pred->getLHS()->getType(), IP, false);
2456   Value *Expr1 =
2457       expandCodeForImpl(Pred->getRHS(), Pred->getRHS()->getType(), IP, false);
2458 
2459   Builder.SetInsertPoint(IP);
2460   auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
2461   return I;
2462 }
2463 
2464 Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
2465                                            Instruction *Loc, bool Signed) {
2466   assert(AR->isAffine() && "Cannot generate RT check for "
2467                            "non-affine expression");
2468 
2469   SCEVUnionPredicate Pred;
2470   const SCEV *ExitCount =
2471       SE.getPredicatedBackedgeTakenCount(AR->getLoop(), Pred);
2472 
2473   assert(!isa<SCEVCouldNotCompute>(ExitCount) && "Invalid loop count");
2474 
2475   const SCEV *Step = AR->getStepRecurrence(SE);
2476   const SCEV *Start = AR->getStart();
2477 
2478   Type *ARTy = AR->getType();
2479   unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType());
2480   unsigned DstBits = SE.getTypeSizeInBits(ARTy);
2481 
2482   // The expression {Start,+,Step} has nusw/nssw if
2483   //   Step < 0, Start - |Step| * Backedge <= Start
2484   //   Step >= 0, Start + |Step| * Backedge > Start
2485   // and |Step| * Backedge doesn't unsigned overflow.
2486 
2487   IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits);
2488   Builder.SetInsertPoint(Loc);
2489   Value *TripCountVal = expandCodeForImpl(ExitCount, CountTy, Loc, false);
2490 
2491   IntegerType *Ty =
2492       IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy));
2493   Type *ARExpandTy = DL.isNonIntegralPointerType(ARTy) ? ARTy : Ty;
2494 
2495   Value *StepValue = expandCodeForImpl(Step, Ty, Loc, false);
2496   Value *NegStepValue =
2497       expandCodeForImpl(SE.getNegativeSCEV(Step), Ty, Loc, false);
2498   Value *StartValue = expandCodeForImpl(Start, ARExpandTy, Loc, false);
2499 
2500   ConstantInt *Zero =
2501       ConstantInt::get(Loc->getContext(), APInt::getNullValue(DstBits));
2502 
2503   Builder.SetInsertPoint(Loc);
2504   // Compute |Step|
2505   Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero);
2506   Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue);
2507 
2508   // Get the backedge taken count and truncate or extended to the AR type.
2509   Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty);
2510   auto *MulF = Intrinsic::getDeclaration(Loc->getModule(),
2511                                          Intrinsic::umul_with_overflow, Ty);
2512 
2513   // Compute |Step| * Backedge
2514   CallInst *Mul = Builder.CreateCall(MulF, {AbsStep, TruncTripCount}, "mul");
2515   Value *MulV = Builder.CreateExtractValue(Mul, 0, "mul.result");
2516   Value *OfMul = Builder.CreateExtractValue(Mul, 1, "mul.overflow");
2517 
2518   // Compute:
2519   //   Start + |Step| * Backedge < Start
2520   //   Start - |Step| * Backedge > Start
2521   Value *Add = nullptr, *Sub = nullptr;
2522   if (PointerType *ARPtrTy = dyn_cast<PointerType>(ARExpandTy)) {
2523     const SCEV *MulS = SE.getSCEV(MulV);
2524     const SCEV *NegMulS = SE.getNegativeSCEV(MulS);
2525     Add = Builder.CreateBitCast(expandAddToGEP(MulS, ARPtrTy, Ty, StartValue),
2526                                 ARPtrTy);
2527     Sub = Builder.CreateBitCast(
2528         expandAddToGEP(NegMulS, ARPtrTy, Ty, StartValue), ARPtrTy);
2529   } else {
2530     Add = Builder.CreateAdd(StartValue, MulV);
2531     Sub = Builder.CreateSub(StartValue, MulV);
2532   }
2533 
2534   Value *EndCompareGT = Builder.CreateICmp(
2535       Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue);
2536 
2537   Value *EndCompareLT = Builder.CreateICmp(
2538       Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, Add, StartValue);
2539 
2540   // Select the answer based on the sign of Step.
2541   Value *EndCheck =
2542       Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT);
2543 
2544   // If the backedge taken count type is larger than the AR type,
2545   // check that we don't drop any bits by truncating it. If we are
2546   // dropping bits, then we have overflow (unless the step is zero).
2547   if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) {
2548     auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits);
2549     auto *BackedgeCheck =
2550         Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal,
2551                            ConstantInt::get(Loc->getContext(), MaxVal));
2552     BackedgeCheck = Builder.CreateAnd(
2553         BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero));
2554 
2555     EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck);
2556   }
2557 
2558   return Builder.CreateOr(EndCheck, OfMul);
2559 }
2560 
2561 Value *SCEVExpander::expandWrapPredicate(const SCEVWrapPredicate *Pred,
2562                                          Instruction *IP) {
2563   const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr());
2564   Value *NSSWCheck = nullptr, *NUSWCheck = nullptr;
2565 
2566   // Add a check for NUSW
2567   if (Pred->getFlags() & SCEVWrapPredicate::IncrementNUSW)
2568     NUSWCheck = generateOverflowCheck(A, IP, false);
2569 
2570   // Add a check for NSSW
2571   if (Pred->getFlags() & SCEVWrapPredicate::IncrementNSSW)
2572     NSSWCheck = generateOverflowCheck(A, IP, true);
2573 
2574   if (NUSWCheck && NSSWCheck)
2575     return Builder.CreateOr(NUSWCheck, NSSWCheck);
2576 
2577   if (NUSWCheck)
2578     return NUSWCheck;
2579 
2580   if (NSSWCheck)
2581     return NSSWCheck;
2582 
2583   return ConstantInt::getFalse(IP->getContext());
2584 }
2585 
2586 Value *SCEVExpander::expandUnionPredicate(const SCEVUnionPredicate *Union,
2587                                           Instruction *IP) {
2588   auto *BoolType = IntegerType::get(IP->getContext(), 1);
2589   Value *Check = ConstantInt::getNullValue(BoolType);
2590 
2591   // Loop over all checks in this set.
2592   for (auto Pred : Union->getPredicates()) {
2593     auto *NextCheck = expandCodeForPredicate(Pred, IP);
2594     Builder.SetInsertPoint(IP);
2595     Check = Builder.CreateOr(Check, NextCheck);
2596   }
2597 
2598   return Check;
2599 }
2600 
2601 Value *SCEVExpander::fixupLCSSAFormFor(Instruction *User, unsigned OpIdx) {
2602   assert(PreserveLCSSA);
2603   SmallVector<Instruction *, 1> ToUpdate;
2604 
2605   auto *OpV = User->getOperand(OpIdx);
2606   auto *OpI = dyn_cast<Instruction>(OpV);
2607   if (!OpI)
2608     return OpV;
2609 
2610   Loop *DefLoop = SE.LI.getLoopFor(OpI->getParent());
2611   Loop *UseLoop = SE.LI.getLoopFor(User->getParent());
2612   if (!DefLoop || UseLoop == DefLoop || DefLoop->contains(UseLoop))
2613     return OpV;
2614 
2615   ToUpdate.push_back(OpI);
2616   SmallVector<PHINode *, 16> PHIsToRemove;
2617   formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, &SE, Builder, &PHIsToRemove);
2618   for (PHINode *PN : PHIsToRemove) {
2619     if (!PN->use_empty())
2620       continue;
2621     InsertedValues.erase(PN);
2622     InsertedPostIncValues.erase(PN);
2623     PN->eraseFromParent();
2624   }
2625 
2626   return User->getOperand(OpIdx);
2627 }
2628 
2629 namespace {
2630 // Search for a SCEV subexpression that is not safe to expand.  Any expression
2631 // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
2632 // UDiv expressions. We don't know if the UDiv is derived from an IR divide
2633 // instruction, but the important thing is that we prove the denominator is
2634 // nonzero before expansion.
2635 //
2636 // IVUsers already checks that IV-derived expressions are safe. So this check is
2637 // only needed when the expression includes some subexpression that is not IV
2638 // derived.
2639 //
2640 // Currently, we only allow division by a nonzero constant here. If this is
2641 // inadequate, we could easily allow division by SCEVUnknown by using
2642 // ValueTracking to check isKnownNonZero().
2643 //
2644 // We cannot generally expand recurrences unless the step dominates the loop
2645 // header. The expander handles the special case of affine recurrences by
2646 // scaling the recurrence outside the loop, but this technique isn't generally
2647 // applicable. Expanding a nested recurrence outside a loop requires computing
2648 // binomial coefficients. This could be done, but the recurrence has to be in a
2649 // perfectly reduced form, which can't be guaranteed.
2650 struct SCEVFindUnsafe {
2651   ScalarEvolution &SE;
2652   bool IsUnsafe;
2653 
2654   SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {}
2655 
2656   bool follow(const SCEV *S) {
2657     if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
2658       const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS());
2659       if (!SC || SC->getValue()->isZero()) {
2660         IsUnsafe = true;
2661         return false;
2662       }
2663     }
2664     if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
2665       const SCEV *Step = AR->getStepRecurrence(SE);
2666       if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
2667         IsUnsafe = true;
2668         return false;
2669       }
2670     }
2671     return true;
2672   }
2673   bool isDone() const { return IsUnsafe; }
2674 };
2675 }
2676 
2677 namespace llvm {
2678 bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) {
2679   SCEVFindUnsafe Search(SE);
2680   visitAll(S, Search);
2681   return !Search.IsUnsafe;
2682 }
2683 
2684 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
2685                       ScalarEvolution &SE) {
2686   if (!isSafeToExpand(S, SE))
2687     return false;
2688   // We have to prove that the expanded site of S dominates InsertionPoint.
2689   // This is easy when not in the same block, but hard when S is an instruction
2690   // to be expanded somewhere inside the same block as our insertion point.
2691   // What we really need here is something analogous to an OrderedBasicBlock,
2692   // but for the moment, we paper over the problem by handling two common and
2693   // cheap to check cases.
2694   if (SE.properlyDominates(S, InsertionPoint->getParent()))
2695     return true;
2696   if (SE.dominates(S, InsertionPoint->getParent())) {
2697     if (InsertionPoint->getParent()->getTerminator() == InsertionPoint)
2698       return true;
2699     if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
2700       if (llvm::is_contained(InsertionPoint->operand_values(), U->getValue()))
2701         return true;
2702   }
2703   return false;
2704 }
2705 
2706 void SCEVExpanderCleaner::cleanup() {
2707   // Result is used, nothing to remove.
2708   if (ResultUsed)
2709     return;
2710 
2711   auto InsertedInstructions = Expander.getAllInsertedInstructions();
2712 #ifndef NDEBUG
2713   SmallPtrSet<Instruction *, 8> InsertedSet(InsertedInstructions.begin(),
2714                                             InsertedInstructions.end());
2715   (void)InsertedSet;
2716 #endif
2717   // Remove sets with value handles.
2718   Expander.clear();
2719 
2720   // Sort so that earlier instructions do not dominate later instructions.
2721   stable_sort(InsertedInstructions, [this](Instruction *A, Instruction *B) {
2722     return DT.dominates(B, A);
2723   });
2724   // Remove all inserted instructions.
2725   for (Instruction *I : InsertedInstructions) {
2726 
2727 #ifndef NDEBUG
2728     assert(all_of(I->users(),
2729                   [&InsertedSet](Value *U) {
2730                     return InsertedSet.contains(cast<Instruction>(U));
2731                   }) &&
2732            "removed instruction should only be used by instructions inserted "
2733            "during expansion");
2734 #endif
2735     assert(!I->getType()->isVoidTy() &&
2736            "inserted instruction should have non-void types");
2737     I->replaceAllUsesWith(UndefValue::get(I->getType()));
2738     I->eraseFromParent();
2739   }
2740 }
2741 }
2742