[ARM] More MVE compare vector splat combines for ANDs
[llvm-complete.git] / lib / Analysis / ScalarEvolutionExpander.cpp
blobe8a95d35482c0cb5b45877959bf19bafe29c1728
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.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Analysis/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/Debug.h"
28 #include "llvm/Support/raw_ostream.h"
30 using namespace llvm;
31 using namespace PatternMatch;
33 /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
34 /// reusing an existing cast if a suitable one exists, moving an existing
35 /// cast if a suitable one exists but isn't in the right place, or
36 /// creating a new one.
37 Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,
38 Instruction::CastOps Op,
39 BasicBlock::iterator IP) {
40 // This function must be called with the builder having a valid insertion
41 // point. It doesn't need to be the actual IP where the uses of the returned
42 // cast will be added, but it must dominate such IP.
43 // We use this precondition to produce a cast that will dominate all its
44 // uses. In particular, this is crucial for the case where the builder's
45 // insertion point *is* the point where we were asked to put the cast.
46 // Since we don't know the builder's insertion point is actually
47 // where the uses will be added (only that it dominates it), we are
48 // not allowed to move it.
49 BasicBlock::iterator BIP = Builder.GetInsertPoint();
51 Instruction *Ret = nullptr;
53 // Check to see if there is already a cast!
54 for (User *U : V->users())
55 if (U->getType() == Ty)
56 if (CastInst *CI = dyn_cast<CastInst>(U))
57 if (CI->getOpcode() == Op) {
58 // If the cast isn't where we want it, create a new cast at IP.
59 // Likewise, do not reuse a cast at BIP because it must dominate
60 // instructions that might be inserted before BIP.
61 if (BasicBlock::iterator(CI) != IP || BIP == IP) {
62 // Create a new cast, and leave the old cast in place in case
63 // it is being used as an insert point.
64 Ret = CastInst::Create(Op, V, Ty, "", &*IP);
65 Ret->takeName(CI);
66 CI->replaceAllUsesWith(Ret);
67 break;
69 Ret = CI;
70 break;
73 // Create a new cast.
74 if (!Ret)
75 Ret = CastInst::Create(Op, V, Ty, V->getName(), &*IP);
77 // We assert at the end of the function since IP might point to an
78 // instruction with different dominance properties than a cast
79 // (an invoke for example) and not dominate BIP (but the cast does).
80 assert(SE.DT.dominates(Ret, &*BIP));
82 rememberInstruction(Ret);
83 return Ret;
86 static BasicBlock::iterator findInsertPointAfter(Instruction *I,
87 BasicBlock *MustDominate) {
88 BasicBlock::iterator IP = ++I->getIterator();
89 if (auto *II = dyn_cast<InvokeInst>(I))
90 IP = II->getNormalDest()->begin();
92 while (isa<PHINode>(IP))
93 ++IP;
95 if (isa<FuncletPadInst>(IP) || isa<LandingPadInst>(IP)) {
96 ++IP;
97 } else if (isa<CatchSwitchInst>(IP)) {
98 IP = MustDominate->getFirstInsertionPt();
99 } else {
100 assert(!IP->isEHPad() && "unexpected eh pad!");
103 return IP;
106 /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
107 /// which must be possible with a noop cast, doing what we can to share
108 /// the casts.
109 Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
110 Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false);
111 assert((Op == Instruction::BitCast ||
112 Op == Instruction::PtrToInt ||
113 Op == Instruction::IntToPtr) &&
114 "InsertNoopCastOfTo cannot perform non-noop casts!");
115 assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) &&
116 "InsertNoopCastOfTo cannot change sizes!");
118 // Short-circuit unnecessary bitcasts.
119 if (Op == Instruction::BitCast) {
120 if (V->getType() == Ty)
121 return V;
122 if (CastInst *CI = dyn_cast<CastInst>(V)) {
123 if (CI->getOperand(0)->getType() == Ty)
124 return CI->getOperand(0);
127 // Short-circuit unnecessary inttoptr<->ptrtoint casts.
128 if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) &&
129 SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) {
130 if (CastInst *CI = dyn_cast<CastInst>(V))
131 if ((CI->getOpcode() == Instruction::PtrToInt ||
132 CI->getOpcode() == Instruction::IntToPtr) &&
133 SE.getTypeSizeInBits(CI->getType()) ==
134 SE.getTypeSizeInBits(CI->getOperand(0)->getType()))
135 return CI->getOperand(0);
136 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
137 if ((CE->getOpcode() == Instruction::PtrToInt ||
138 CE->getOpcode() == Instruction::IntToPtr) &&
139 SE.getTypeSizeInBits(CE->getType()) ==
140 SE.getTypeSizeInBits(CE->getOperand(0)->getType()))
141 return CE->getOperand(0);
144 // Fold a cast of a constant.
145 if (Constant *C = dyn_cast<Constant>(V))
146 return ConstantExpr::getCast(Op, C, Ty);
148 // Cast the argument at the beginning of the entry block, after
149 // any bitcasts of other arguments.
150 if (Argument *A = dyn_cast<Argument>(V)) {
151 BasicBlock::iterator IP = A->getParent()->getEntryBlock().begin();
152 while ((isa<BitCastInst>(IP) &&
153 isa<Argument>(cast<BitCastInst>(IP)->getOperand(0)) &&
154 cast<BitCastInst>(IP)->getOperand(0) != A) ||
155 isa<DbgInfoIntrinsic>(IP))
156 ++IP;
157 return ReuseOrCreateCast(A, Ty, Op, IP);
160 // Cast the instruction immediately after the instruction.
161 Instruction *I = cast<Instruction>(V);
162 BasicBlock::iterator IP = findInsertPointAfter(I, Builder.GetInsertBlock());
163 return ReuseOrCreateCast(I, Ty, Op, IP);
166 /// InsertBinop - Insert the specified binary operator, doing a small amount
167 /// of work to avoid inserting an obviously redundant operation, and hoisting
168 /// to an outer loop when the opportunity is there and it is safe.
169 Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
170 Value *LHS, Value *RHS,
171 SCEV::NoWrapFlags Flags, bool IsSafeToHoist) {
172 // Fold a binop with constant operands.
173 if (Constant *CLHS = dyn_cast<Constant>(LHS))
174 if (Constant *CRHS = dyn_cast<Constant>(RHS))
175 return ConstantExpr::get(Opcode, CLHS, CRHS);
177 // Do a quick scan to see if we have this binop nearby. If so, reuse it.
178 unsigned ScanLimit = 6;
179 BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
180 // Scanning starts from the last instruction before the insertion point.
181 BasicBlock::iterator IP = Builder.GetInsertPoint();
182 if (IP != BlockBegin) {
183 --IP;
184 for (; ScanLimit; --IP, --ScanLimit) {
185 // Don't count dbg.value against the ScanLimit, to avoid perturbing the
186 // generated code.
187 if (isa<DbgInfoIntrinsic>(IP))
188 ScanLimit++;
190 auto canGenerateIncompatiblePoison = [&Flags](Instruction *I) {
191 // Ensure that no-wrap flags match.
192 if (isa<OverflowingBinaryOperator>(I)) {
193 if (I->hasNoSignedWrap() != (Flags & SCEV::FlagNSW))
194 return true;
195 if (I->hasNoUnsignedWrap() != (Flags & SCEV::FlagNUW))
196 return true;
198 // Conservatively, do not use any instruction which has any of exact
199 // flags installed.
200 if (isa<PossiblyExactOperator>(I) && I->isExact())
201 return true;
202 return false;
204 if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS &&
205 IP->getOperand(1) == RHS && !canGenerateIncompatiblePoison(&*IP))
206 return &*IP;
207 if (IP == BlockBegin) break;
211 // Save the original insertion point so we can restore it when we're done.
212 DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();
213 SCEVInsertPointGuard Guard(Builder, this);
215 if (IsSafeToHoist) {
216 // Move the insertion point out of as many loops as we can.
217 while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
218 if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break;
219 BasicBlock *Preheader = L->getLoopPreheader();
220 if (!Preheader) break;
222 // Ok, move up a level.
223 Builder.SetInsertPoint(Preheader->getTerminator());
227 // If we haven't found this binop, insert it.
228 Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS));
229 BO->setDebugLoc(Loc);
230 if (Flags & SCEV::FlagNUW)
231 BO->setHasNoUnsignedWrap();
232 if (Flags & SCEV::FlagNSW)
233 BO->setHasNoSignedWrap();
234 rememberInstruction(BO);
236 return BO;
239 /// FactorOutConstant - Test if S is divisible by Factor, using signed
240 /// division. If so, update S with Factor divided out and return true.
241 /// S need not be evenly divisible if a reasonable remainder can be
242 /// computed.
243 /// TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made
244 /// unnecessary; in its place, just signed-divide Ops[i] by the scale and
245 /// check to see if the divide was folded.
246 static bool FactorOutConstant(const SCEV *&S, const SCEV *&Remainder,
247 const SCEV *Factor, ScalarEvolution &SE,
248 const DataLayout &DL) {
249 // Everything is divisible by one.
250 if (Factor->isOne())
251 return true;
253 // x/x == 1.
254 if (S == Factor) {
255 S = SE.getConstant(S->getType(), 1);
256 return true;
259 // For a Constant, check for a multiple of the given factor.
260 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
261 // 0/x == 0.
262 if (C->isZero())
263 return true;
264 // Check for divisibility.
265 if (const SCEVConstant *FC = dyn_cast<SCEVConstant>(Factor)) {
266 ConstantInt *CI =
267 ConstantInt::get(SE.getContext(), C->getAPInt().sdiv(FC->getAPInt()));
268 // If the quotient is zero and the remainder is non-zero, reject
269 // the value at this scale. It will be considered for subsequent
270 // smaller scales.
271 if (!CI->isZero()) {
272 const SCEV *Div = SE.getConstant(CI);
273 S = Div;
274 Remainder = SE.getAddExpr(
275 Remainder, SE.getConstant(C->getAPInt().srem(FC->getAPInt())));
276 return true;
281 // In a Mul, check if there is a constant operand which is a multiple
282 // of the given factor.
283 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
284 // Size is known, check if there is a constant operand which is a multiple
285 // of the given factor. If so, we can factor it.
286 const SCEVConstant *FC = cast<SCEVConstant>(Factor);
287 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0)))
288 if (!C->getAPInt().srem(FC->getAPInt())) {
289 SmallVector<const SCEV *, 4> NewMulOps(M->op_begin(), M->op_end());
290 NewMulOps[0] = SE.getConstant(C->getAPInt().sdiv(FC->getAPInt()));
291 S = SE.getMulExpr(NewMulOps);
292 return true;
296 // In an AddRec, check if both start and step are divisible.
297 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
298 const SCEV *Step = A->getStepRecurrence(SE);
299 const SCEV *StepRem = SE.getConstant(Step->getType(), 0);
300 if (!FactorOutConstant(Step, StepRem, Factor, SE, DL))
301 return false;
302 if (!StepRem->isZero())
303 return false;
304 const SCEV *Start = A->getStart();
305 if (!FactorOutConstant(Start, Remainder, Factor, SE, DL))
306 return false;
307 S = SE.getAddRecExpr(Start, Step, A->getLoop(),
308 A->getNoWrapFlags(SCEV::FlagNW));
309 return true;
312 return false;
315 /// SimplifyAddOperands - Sort and simplify a list of add operands. NumAddRecs
316 /// is the number of SCEVAddRecExprs present, which are kept at the end of
317 /// the list.
319 static void SimplifyAddOperands(SmallVectorImpl<const SCEV *> &Ops,
320 Type *Ty,
321 ScalarEvolution &SE) {
322 unsigned NumAddRecs = 0;
323 for (unsigned i = Ops.size(); i > 0 && isa<SCEVAddRecExpr>(Ops[i-1]); --i)
324 ++NumAddRecs;
325 // Group Ops into non-addrecs and addrecs.
326 SmallVector<const SCEV *, 8> NoAddRecs(Ops.begin(), Ops.end() - NumAddRecs);
327 SmallVector<const SCEV *, 8> AddRecs(Ops.end() - NumAddRecs, Ops.end());
328 // Let ScalarEvolution sort and simplify the non-addrecs list.
329 const SCEV *Sum = NoAddRecs.empty() ?
330 SE.getConstant(Ty, 0) :
331 SE.getAddExpr(NoAddRecs);
332 // If it returned an add, use the operands. Otherwise it simplified
333 // the sum into a single value, so just use that.
334 Ops.clear();
335 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Sum))
336 Ops.append(Add->op_begin(), Add->op_end());
337 else if (!Sum->isZero())
338 Ops.push_back(Sum);
339 // Then append the addrecs.
340 Ops.append(AddRecs.begin(), AddRecs.end());
343 /// SplitAddRecs - Flatten a list of add operands, moving addrec start values
344 /// out to the top level. For example, convert {a + b,+,c} to a, b, {0,+,d}.
345 /// This helps expose more opportunities for folding parts of the expressions
346 /// into GEP indices.
348 static void SplitAddRecs(SmallVectorImpl<const SCEV *> &Ops,
349 Type *Ty,
350 ScalarEvolution &SE) {
351 // Find the addrecs.
352 SmallVector<const SCEV *, 8> AddRecs;
353 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
354 while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) {
355 const SCEV *Start = A->getStart();
356 if (Start->isZero()) break;
357 const SCEV *Zero = SE.getConstant(Ty, 0);
358 AddRecs.push_back(SE.getAddRecExpr(Zero,
359 A->getStepRecurrence(SE),
360 A->getLoop(),
361 A->getNoWrapFlags(SCEV::FlagNW)));
362 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Start)) {
363 Ops[i] = Zero;
364 Ops.append(Add->op_begin(), Add->op_end());
365 e += Add->getNumOperands();
366 } else {
367 Ops[i] = Start;
370 if (!AddRecs.empty()) {
371 // Add the addrecs onto the end of the list.
372 Ops.append(AddRecs.begin(), AddRecs.end());
373 // Resort the operand list, moving any constants to the front.
374 SimplifyAddOperands(Ops, Ty, SE);
378 /// expandAddToGEP - Expand an addition expression with a pointer type into
379 /// a GEP instead of using ptrtoint+arithmetic+inttoptr. This helps
380 /// BasicAliasAnalysis and other passes analyze the result. See the rules
381 /// for getelementptr vs. inttoptr in
382 /// http://llvm.org/docs/LangRef.html#pointeraliasing
383 /// for details.
385 /// Design note: The correctness of using getelementptr here depends on
386 /// ScalarEvolution not recognizing inttoptr and ptrtoint operators, as
387 /// they may introduce pointer arithmetic which may not be safely converted
388 /// into getelementptr.
390 /// Design note: It might seem desirable for this function to be more
391 /// loop-aware. If some of the indices are loop-invariant while others
392 /// aren't, it might seem desirable to emit multiple GEPs, keeping the
393 /// loop-invariant portions of the overall computation outside the loop.
394 /// However, there are a few reasons this is not done here. Hoisting simple
395 /// arithmetic is a low-level optimization that often isn't very
396 /// important until late in the optimization process. In fact, passes
397 /// like InstructionCombining will combine GEPs, even if it means
398 /// pushing loop-invariant computation down into loops, so even if the
399 /// GEPs were split here, the work would quickly be undone. The
400 /// LoopStrengthReduction pass, which is usually run quite late (and
401 /// after the last InstructionCombining pass), takes care of hoisting
402 /// loop-invariant portions of expressions, after considering what
403 /// can be folded using target addressing modes.
405 Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin,
406 const SCEV *const *op_end,
407 PointerType *PTy,
408 Type *Ty,
409 Value *V) {
410 Type *OriginalElTy = PTy->getElementType();
411 Type *ElTy = OriginalElTy;
412 SmallVector<Value *, 4> GepIndices;
413 SmallVector<const SCEV *, 8> Ops(op_begin, op_end);
414 bool AnyNonZeroIndices = false;
416 // Split AddRecs up into parts as either of the parts may be usable
417 // without the other.
418 SplitAddRecs(Ops, Ty, SE);
420 Type *IntPtrTy = DL.getIntPtrType(PTy);
422 // Descend down the pointer's type and attempt to convert the other
423 // operands into GEP indices, at each level. The first index in a GEP
424 // indexes into the array implied by the pointer operand; the rest of
425 // the indices index into the element or field type selected by the
426 // preceding index.
427 for (;;) {
428 // If the scale size is not 0, attempt to factor out a scale for
429 // array indexing.
430 SmallVector<const SCEV *, 8> ScaledOps;
431 if (ElTy->isSized()) {
432 const SCEV *ElSize = SE.getSizeOfExpr(IntPtrTy, ElTy);
433 if (!ElSize->isZero()) {
434 SmallVector<const SCEV *, 8> NewOps;
435 for (const SCEV *Op : Ops) {
436 const SCEV *Remainder = SE.getConstant(Ty, 0);
437 if (FactorOutConstant(Op, Remainder, ElSize, SE, DL)) {
438 // Op now has ElSize factored out.
439 ScaledOps.push_back(Op);
440 if (!Remainder->isZero())
441 NewOps.push_back(Remainder);
442 AnyNonZeroIndices = true;
443 } else {
444 // The operand was not divisible, so add it to the list of operands
445 // we'll scan next iteration.
446 NewOps.push_back(Op);
449 // If we made any changes, update Ops.
450 if (!ScaledOps.empty()) {
451 Ops = NewOps;
452 SimplifyAddOperands(Ops, Ty, SE);
457 // Record the scaled array index for this level of the type. If
458 // we didn't find any operands that could be factored, tentatively
459 // assume that element zero was selected (since the zero offset
460 // would obviously be folded away).
461 Value *Scaled = ScaledOps.empty() ?
462 Constant::getNullValue(Ty) :
463 expandCodeFor(SE.getAddExpr(ScaledOps), Ty);
464 GepIndices.push_back(Scaled);
466 // Collect struct field index operands.
467 while (StructType *STy = dyn_cast<StructType>(ElTy)) {
468 bool FoundFieldNo = false;
469 // An empty struct has no fields.
470 if (STy->getNumElements() == 0) break;
471 // Field offsets are known. See if a constant offset falls within any of
472 // the struct fields.
473 if (Ops.empty())
474 break;
475 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0]))
476 if (SE.getTypeSizeInBits(C->getType()) <= 64) {
477 const StructLayout &SL = *DL.getStructLayout(STy);
478 uint64_t FullOffset = C->getValue()->getZExtValue();
479 if (FullOffset < SL.getSizeInBytes()) {
480 unsigned ElIdx = SL.getElementContainingOffset(FullOffset);
481 GepIndices.push_back(
482 ConstantInt::get(Type::getInt32Ty(Ty->getContext()), ElIdx));
483 ElTy = STy->getTypeAtIndex(ElIdx);
484 Ops[0] =
485 SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx));
486 AnyNonZeroIndices = true;
487 FoundFieldNo = true;
490 // If no struct field offsets were found, tentatively assume that
491 // field zero was selected (since the zero offset would obviously
492 // be folded away).
493 if (!FoundFieldNo) {
494 ElTy = STy->getTypeAtIndex(0u);
495 GepIndices.push_back(
496 Constant::getNullValue(Type::getInt32Ty(Ty->getContext())));
500 if (ArrayType *ATy = dyn_cast<ArrayType>(ElTy))
501 ElTy = ATy->getElementType();
502 else
503 break;
506 // If none of the operands were convertible to proper GEP indices, cast
507 // the base to i8* and do an ugly getelementptr with that. It's still
508 // better than ptrtoint+arithmetic+inttoptr at least.
509 if (!AnyNonZeroIndices) {
510 // Cast the base to i8*.
511 V = InsertNoopCastOfTo(V,
512 Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace()));
514 assert(!isa<Instruction>(V) ||
515 SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()));
517 // Expand the operands for a plain byte offset.
518 Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty);
520 // Fold a GEP with constant operands.
521 if (Constant *CLHS = dyn_cast<Constant>(V))
522 if (Constant *CRHS = dyn_cast<Constant>(Idx))
523 return ConstantExpr::getGetElementPtr(Type::getInt8Ty(Ty->getContext()),
524 CLHS, CRHS);
526 // Do a quick scan to see if we have this GEP nearby. If so, reuse it.
527 unsigned ScanLimit = 6;
528 BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin();
529 // Scanning starts from the last instruction before the insertion point.
530 BasicBlock::iterator IP = Builder.GetInsertPoint();
531 if (IP != BlockBegin) {
532 --IP;
533 for (; ScanLimit; --IP, --ScanLimit) {
534 // Don't count dbg.value against the ScanLimit, to avoid perturbing the
535 // generated code.
536 if (isa<DbgInfoIntrinsic>(IP))
537 ScanLimit++;
538 if (IP->getOpcode() == Instruction::GetElementPtr &&
539 IP->getOperand(0) == V && IP->getOperand(1) == Idx)
540 return &*IP;
541 if (IP == BlockBegin) break;
545 // Save the original insertion point so we can restore it when we're done.
546 SCEVInsertPointGuard Guard(Builder, this);
548 // Move the insertion point out of as many loops as we can.
549 while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
550 if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break;
551 BasicBlock *Preheader = L->getLoopPreheader();
552 if (!Preheader) break;
554 // Ok, move up a level.
555 Builder.SetInsertPoint(Preheader->getTerminator());
558 // Emit a GEP.
559 Value *GEP = Builder.CreateGEP(Builder.getInt8Ty(), V, Idx, "uglygep");
560 rememberInstruction(GEP);
562 return GEP;
566 SCEVInsertPointGuard Guard(Builder, this);
568 // Move the insertion point out of as many loops as we can.
569 while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
570 if (!L->isLoopInvariant(V)) break;
572 bool AnyIndexNotLoopInvariant = any_of(
573 GepIndices, [L](Value *Op) { return !L->isLoopInvariant(Op); });
575 if (AnyIndexNotLoopInvariant)
576 break;
578 BasicBlock *Preheader = L->getLoopPreheader();
579 if (!Preheader) break;
581 // Ok, move up a level.
582 Builder.SetInsertPoint(Preheader->getTerminator());
585 // Insert a pretty getelementptr. Note that this GEP is not marked inbounds,
586 // because ScalarEvolution may have changed the address arithmetic to
587 // compute a value which is beyond the end of the allocated object.
588 Value *Casted = V;
589 if (V->getType() != PTy)
590 Casted = InsertNoopCastOfTo(Casted, PTy);
591 Value *GEP = Builder.CreateGEP(OriginalElTy, Casted, GepIndices, "scevgep");
592 Ops.push_back(SE.getUnknown(GEP));
593 rememberInstruction(GEP);
596 return expand(SE.getAddExpr(Ops));
599 Value *SCEVExpander::expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty,
600 Value *V) {
601 const SCEV *const Ops[1] = {Op};
602 return expandAddToGEP(Ops, Ops + 1, PTy, Ty, V);
605 /// PickMostRelevantLoop - Given two loops pick the one that's most relevant for
606 /// SCEV expansion. If they are nested, this is the most nested. If they are
607 /// neighboring, pick the later.
608 static const Loop *PickMostRelevantLoop(const Loop *A, const Loop *B,
609 DominatorTree &DT) {
610 if (!A) return B;
611 if (!B) return A;
612 if (A->contains(B)) return B;
613 if (B->contains(A)) return A;
614 if (DT.dominates(A->getHeader(), B->getHeader())) return B;
615 if (DT.dominates(B->getHeader(), A->getHeader())) return A;
616 return A; // Arbitrarily break the tie.
619 /// getRelevantLoop - Get the most relevant loop associated with the given
620 /// expression, according to PickMostRelevantLoop.
621 const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) {
622 // Test whether we've already computed the most relevant loop for this SCEV.
623 auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr));
624 if (!Pair.second)
625 return Pair.first->second;
627 if (isa<SCEVConstant>(S))
628 // A constant has no relevant loops.
629 return nullptr;
630 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
631 if (const Instruction *I = dyn_cast<Instruction>(U->getValue()))
632 return Pair.first->second = SE.LI.getLoopFor(I->getParent());
633 // A non-instruction has no relevant loops.
634 return nullptr;
636 if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S)) {
637 const Loop *L = nullptr;
638 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
639 L = AR->getLoop();
640 for (const SCEV *Op : N->operands())
641 L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT);
642 return RelevantLoops[N] = L;
644 if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S)) {
645 const Loop *Result = getRelevantLoop(C->getOperand());
646 return RelevantLoops[C] = Result;
648 if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
649 const Loop *Result = PickMostRelevantLoop(
650 getRelevantLoop(D->getLHS()), getRelevantLoop(D->getRHS()), SE.DT);
651 return RelevantLoops[D] = Result;
653 llvm_unreachable("Unexpected SCEV type!");
656 namespace {
658 /// LoopCompare - Compare loops by PickMostRelevantLoop.
659 class LoopCompare {
660 DominatorTree &DT;
661 public:
662 explicit LoopCompare(DominatorTree &dt) : DT(dt) {}
664 bool operator()(std::pair<const Loop *, const SCEV *> LHS,
665 std::pair<const Loop *, const SCEV *> RHS) const {
666 // Keep pointer operands sorted at the end.
667 if (LHS.second->getType()->isPointerTy() !=
668 RHS.second->getType()->isPointerTy())
669 return LHS.second->getType()->isPointerTy();
671 // Compare loops with PickMostRelevantLoop.
672 if (LHS.first != RHS.first)
673 return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first;
675 // If one operand is a non-constant negative and the other is not,
676 // put the non-constant negative on the right so that a sub can
677 // be used instead of a negate and add.
678 if (LHS.second->isNonConstantNegative()) {
679 if (!RHS.second->isNonConstantNegative())
680 return false;
681 } else if (RHS.second->isNonConstantNegative())
682 return true;
684 // Otherwise they are equivalent according to this comparison.
685 return false;
691 Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) {
692 Type *Ty = SE.getEffectiveSCEVType(S->getType());
694 // Collect all the add operands in a loop, along with their associated loops.
695 // Iterate in reverse so that constants are emitted last, all else equal, and
696 // so that pointer operands are inserted first, which the code below relies on
697 // to form more involved GEPs.
698 SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
699 for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(S->op_end()),
700 E(S->op_begin()); I != E; ++I)
701 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
703 // Sort by loop. Use a stable sort so that constants follow non-constants and
704 // pointer operands precede non-pointer operands.
705 llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
707 // Emit instructions to add all the operands. Hoist as much as possible
708 // out of loops, and form meaningful getelementptrs where possible.
709 Value *Sum = nullptr;
710 for (auto I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E;) {
711 const Loop *CurLoop = I->first;
712 const SCEV *Op = I->second;
713 if (!Sum) {
714 // This is the first operand. Just expand it.
715 Sum = expand(Op);
716 ++I;
717 } else if (PointerType *PTy = dyn_cast<PointerType>(Sum->getType())) {
718 // The running sum expression is a pointer. Try to form a getelementptr
719 // at this level with that as the base.
720 SmallVector<const SCEV *, 4> NewOps;
721 for (; I != E && I->first == CurLoop; ++I) {
722 // If the operand is SCEVUnknown and not instructions, peek through
723 // it, to enable more of it to be folded into the GEP.
724 const SCEV *X = I->second;
725 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(X))
726 if (!isa<Instruction>(U->getValue()))
727 X = SE.getSCEV(U->getValue());
728 NewOps.push_back(X);
730 Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, Sum);
731 } else if (PointerType *PTy = dyn_cast<PointerType>(Op->getType())) {
732 // The running sum is an integer, and there's a pointer at this level.
733 // Try to form a getelementptr. If the running sum is instructions,
734 // use a SCEVUnknown to avoid re-analyzing them.
735 SmallVector<const SCEV *, 4> NewOps;
736 NewOps.push_back(isa<Instruction>(Sum) ? SE.getUnknown(Sum) :
737 SE.getSCEV(Sum));
738 for (++I; I != E && I->first == CurLoop; ++I)
739 NewOps.push_back(I->second);
740 Sum = expandAddToGEP(NewOps.begin(), NewOps.end(), PTy, Ty, expand(Op));
741 } else if (Op->isNonConstantNegative()) {
742 // Instead of doing a negate and add, just do a subtract.
743 Value *W = expandCodeFor(SE.getNegativeSCEV(Op), Ty);
744 Sum = InsertNoopCastOfTo(Sum, Ty);
745 Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap,
746 /*IsSafeToHoist*/ true);
747 ++I;
748 } else {
749 // A simple add.
750 Value *W = expandCodeFor(Op, Ty);
751 Sum = InsertNoopCastOfTo(Sum, Ty);
752 // Canonicalize a constant to the RHS.
753 if (isa<Constant>(Sum)) std::swap(Sum, W);
754 Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(),
755 /*IsSafeToHoist*/ true);
756 ++I;
760 return Sum;
763 Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
764 Type *Ty = SE.getEffectiveSCEVType(S->getType());
766 // Collect all the mul operands in a loop, along with their associated loops.
767 // Iterate in reverse so that constants are emitted last, all else equal.
768 SmallVector<std::pair<const Loop *, const SCEV *>, 8> OpsAndLoops;
769 for (std::reverse_iterator<SCEVMulExpr::op_iterator> I(S->op_end()),
770 E(S->op_begin()); I != E; ++I)
771 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I));
773 // Sort by loop. Use a stable sort so that constants follow non-constants.
774 llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT));
776 // Emit instructions to mul all the operands. Hoist as much as possible
777 // out of loops.
778 Value *Prod = nullptr;
779 auto I = OpsAndLoops.begin();
781 // Expand the calculation of X pow N in the following manner:
782 // Let N = P1 + P2 + ... + PK, where all P are powers of 2. Then:
783 // X pow N = (X pow P1) * (X pow P2) * ... * (X pow PK).
784 const auto ExpandOpBinPowN = [this, &I, &OpsAndLoops, &Ty]() {
785 auto E = I;
786 // Calculate how many times the same operand from the same loop is included
787 // into this power.
788 uint64_t Exponent = 0;
789 const uint64_t MaxExponent = UINT64_MAX >> 1;
790 // No one sane will ever try to calculate such huge exponents, but if we
791 // need this, we stop on UINT64_MAX / 2 because we need to exit the loop
792 // below when the power of 2 exceeds our Exponent, and we want it to be
793 // 1u << 31 at most to not deal with unsigned overflow.
794 while (E != OpsAndLoops.end() && *I == *E && Exponent != MaxExponent) {
795 ++Exponent;
796 ++E;
798 assert(Exponent > 0 && "Trying to calculate a zeroth exponent of operand?");
800 // Calculate powers with exponents 1, 2, 4, 8 etc. and include those of them
801 // that are needed into the result.
802 Value *P = expandCodeFor(I->second, Ty);
803 Value *Result = nullptr;
804 if (Exponent & 1)
805 Result = P;
806 for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) {
807 P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap,
808 /*IsSafeToHoist*/ true);
809 if (Exponent & BinExp)
810 Result = Result ? InsertBinop(Instruction::Mul, Result, P,
811 SCEV::FlagAnyWrap,
812 /*IsSafeToHoist*/ true)
813 : P;
816 I = E;
817 assert(Result && "Nothing was expanded?");
818 return Result;
821 while (I != OpsAndLoops.end()) {
822 if (!Prod) {
823 // This is the first operand. Just expand it.
824 Prod = ExpandOpBinPowN();
825 } else if (I->second->isAllOnesValue()) {
826 // Instead of doing a multiply by negative one, just do a negate.
827 Prod = InsertNoopCastOfTo(Prod, Ty);
828 Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod,
829 SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
830 ++I;
831 } else {
832 // A simple mul.
833 Value *W = ExpandOpBinPowN();
834 Prod = InsertNoopCastOfTo(Prod, Ty);
835 // Canonicalize a constant to the RHS.
836 if (isa<Constant>(Prod)) std::swap(Prod, W);
837 const APInt *RHS;
838 if (match(W, m_Power2(RHS))) {
839 // Canonicalize Prod*(1<<C) to Prod<<C.
840 assert(!Ty->isVectorTy() && "vector types are not SCEVable");
841 auto NWFlags = S->getNoWrapFlags();
842 // clear nsw flag if shl will produce poison value.
843 if (RHS->logBase2() == RHS->getBitWidth() - 1)
844 NWFlags = ScalarEvolution::clearFlags(NWFlags, SCEV::FlagNSW);
845 Prod = InsertBinop(Instruction::Shl, Prod,
846 ConstantInt::get(Ty, RHS->logBase2()), NWFlags,
847 /*IsSafeToHoist*/ true);
848 } else {
849 Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(),
850 /*IsSafeToHoist*/ true);
855 return Prod;
858 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
859 Type *Ty = SE.getEffectiveSCEVType(S->getType());
861 Value *LHS = expandCodeFor(S->getLHS(), Ty);
862 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
863 const APInt &RHS = SC->getAPInt();
864 if (RHS.isPowerOf2())
865 return InsertBinop(Instruction::LShr, LHS,
866 ConstantInt::get(Ty, RHS.logBase2()),
867 SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true);
870 Value *RHS = expandCodeFor(S->getRHS(), Ty);
871 return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap,
872 /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS()));
875 /// Move parts of Base into Rest to leave Base with the minimal
876 /// expression that provides a pointer operand suitable for a
877 /// GEP expansion.
878 static void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest,
879 ScalarEvolution &SE) {
880 while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) {
881 Base = A->getStart();
882 Rest = SE.getAddExpr(Rest,
883 SE.getAddRecExpr(SE.getConstant(A->getType(), 0),
884 A->getStepRecurrence(SE),
885 A->getLoop(),
886 A->getNoWrapFlags(SCEV::FlagNW)));
888 if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) {
889 Base = A->getOperand(A->getNumOperands()-1);
890 SmallVector<const SCEV *, 8> NewAddOps(A->op_begin(), A->op_end());
891 NewAddOps.back() = Rest;
892 Rest = SE.getAddExpr(NewAddOps);
893 ExposePointerBase(Base, Rest, SE);
897 /// Determine if this is a well-behaved chain of instructions leading back to
898 /// the PHI. If so, it may be reused by expanded expressions.
899 bool SCEVExpander::isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
900 const Loop *L) {
901 if (IncV->getNumOperands() == 0 || isa<PHINode>(IncV) ||
902 (isa<CastInst>(IncV) && !isa<BitCastInst>(IncV)))
903 return false;
904 // If any of the operands don't dominate the insert position, bail.
905 // Addrec operands are always loop-invariant, so this can only happen
906 // if there are instructions which haven't been hoisted.
907 if (L == IVIncInsertLoop) {
908 for (User::op_iterator OI = IncV->op_begin()+1,
909 OE = IncV->op_end(); OI != OE; ++OI)
910 if (Instruction *OInst = dyn_cast<Instruction>(OI))
911 if (!SE.DT.dominates(OInst, IVIncInsertPos))
912 return false;
914 // Advance to the next instruction.
915 IncV = dyn_cast<Instruction>(IncV->getOperand(0));
916 if (!IncV)
917 return false;
919 if (IncV->mayHaveSideEffects())
920 return false;
922 if (IncV == PN)
923 return true;
925 return isNormalAddRecExprPHI(PN, IncV, L);
928 /// getIVIncOperand returns an induction variable increment's induction
929 /// variable operand.
931 /// If allowScale is set, any type of GEP is allowed as long as the nonIV
932 /// operands dominate InsertPos.
934 /// If allowScale is not set, ensure that a GEP increment conforms to one of the
935 /// simple patterns generated by getAddRecExprPHILiterally and
936 /// expandAddtoGEP. If the pattern isn't recognized, return NULL.
937 Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV,
938 Instruction *InsertPos,
939 bool allowScale) {
940 if (IncV == InsertPos)
941 return nullptr;
943 switch (IncV->getOpcode()) {
944 default:
945 return nullptr;
946 // Check for a simple Add/Sub or GEP of a loop invariant step.
947 case Instruction::Add:
948 case Instruction::Sub: {
949 Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));
950 if (!OInst || SE.DT.dominates(OInst, InsertPos))
951 return dyn_cast<Instruction>(IncV->getOperand(0));
952 return nullptr;
954 case Instruction::BitCast:
955 return dyn_cast<Instruction>(IncV->getOperand(0));
956 case Instruction::GetElementPtr:
957 for (auto I = IncV->op_begin() + 1, E = IncV->op_end(); I != E; ++I) {
958 if (isa<Constant>(*I))
959 continue;
960 if (Instruction *OInst = dyn_cast<Instruction>(*I)) {
961 if (!SE.DT.dominates(OInst, InsertPos))
962 return nullptr;
964 if (allowScale) {
965 // allow any kind of GEP as long as it can be hoisted.
966 continue;
968 // This must be a pointer addition of constants (pretty), which is already
969 // handled, or some number of address-size elements (ugly). Ugly geps
970 // have 2 operands. i1* is used by the expander to represent an
971 // address-size element.
972 if (IncV->getNumOperands() != 2)
973 return nullptr;
974 unsigned AS = cast<PointerType>(IncV->getType())->getAddressSpace();
975 if (IncV->getType() != Type::getInt1PtrTy(SE.getContext(), AS)
976 && IncV->getType() != Type::getInt8PtrTy(SE.getContext(), AS))
977 return nullptr;
978 break;
980 return dyn_cast<Instruction>(IncV->getOperand(0));
984 /// If the insert point of the current builder or any of the builders on the
985 /// stack of saved builders has 'I' as its insert point, update it to point to
986 /// the instruction after 'I'. This is intended to be used when the instruction
987 /// 'I' is being moved. If this fixup is not done and 'I' is moved to a
988 /// different block, the inconsistent insert point (with a mismatched
989 /// Instruction and Block) can lead to an instruction being inserted in a block
990 /// other than its parent.
991 void SCEVExpander::fixupInsertPoints(Instruction *I) {
992 BasicBlock::iterator It(*I);
993 BasicBlock::iterator NewInsertPt = std::next(It);
994 if (Builder.GetInsertPoint() == It)
995 Builder.SetInsertPoint(&*NewInsertPt);
996 for (auto *InsertPtGuard : InsertPointGuards)
997 if (InsertPtGuard->GetInsertPoint() == It)
998 InsertPtGuard->SetInsertPoint(NewInsertPt);
1001 /// hoistStep - Attempt to hoist a simple IV increment above InsertPos to make
1002 /// it available to other uses in this loop. Recursively hoist any operands,
1003 /// until we reach a value that dominates InsertPos.
1004 bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) {
1005 if (SE.DT.dominates(IncV, InsertPos))
1006 return true;
1008 // InsertPos must itself dominate IncV so that IncV's new position satisfies
1009 // its existing users.
1010 if (isa<PHINode>(InsertPos) ||
1011 !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))
1012 return false;
1014 if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
1015 return false;
1017 // Check that the chain of IV operands leading back to Phi can be hoisted.
1018 SmallVector<Instruction*, 4> IVIncs;
1019 for(;;) {
1020 Instruction *Oper = getIVIncOperand(IncV, InsertPos, /*allowScale*/true);
1021 if (!Oper)
1022 return false;
1023 // IncV is safe to hoist.
1024 IVIncs.push_back(IncV);
1025 IncV = Oper;
1026 if (SE.DT.dominates(IncV, InsertPos))
1027 break;
1029 for (auto I = IVIncs.rbegin(), E = IVIncs.rend(); I != E; ++I) {
1030 fixupInsertPoints(*I);
1031 (*I)->moveBefore(InsertPos);
1033 return true;
1036 /// Determine if this cyclic phi is in a form that would have been generated by
1037 /// LSR. We don't care if the phi was actually expanded in this pass, as long
1038 /// as it is in a low-cost form, for example, no implied multiplication. This
1039 /// should match any patterns generated by getAddRecExprPHILiterally and
1040 /// expandAddtoGEP.
1041 bool SCEVExpander::isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
1042 const Loop *L) {
1043 for(Instruction *IVOper = IncV;
1044 (IVOper = getIVIncOperand(IVOper, L->getLoopPreheader()->getTerminator(),
1045 /*allowScale=*/false));) {
1046 if (IVOper == PN)
1047 return true;
1049 return false;
1052 /// expandIVInc - Expand an IV increment at Builder's current InsertPos.
1053 /// Typically this is the LatchBlock terminator or IVIncInsertPos, but we may
1054 /// need to materialize IV increments elsewhere to handle difficult situations.
1055 Value *SCEVExpander::expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
1056 Type *ExpandTy, Type *IntTy,
1057 bool useSubtract) {
1058 Value *IncV;
1059 // If the PHI is a pointer, use a GEP, otherwise use an add or sub.
1060 if (ExpandTy->isPointerTy()) {
1061 PointerType *GEPPtrTy = cast<PointerType>(ExpandTy);
1062 // If the step isn't constant, don't use an implicitly scaled GEP, because
1063 // that would require a multiply inside the loop.
1064 if (!isa<ConstantInt>(StepV))
1065 GEPPtrTy = PointerType::get(Type::getInt1Ty(SE.getContext()),
1066 GEPPtrTy->getAddressSpace());
1067 IncV = expandAddToGEP(SE.getSCEV(StepV), GEPPtrTy, IntTy, PN);
1068 if (IncV->getType() != PN->getType()) {
1069 IncV = Builder.CreateBitCast(IncV, PN->getType());
1070 rememberInstruction(IncV);
1072 } else {
1073 IncV = useSubtract ?
1074 Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") :
1075 Builder.CreateAdd(PN, StepV, Twine(IVName) + ".iv.next");
1076 rememberInstruction(IncV);
1078 return IncV;
1081 /// Hoist the addrec instruction chain rooted in the loop phi above the
1082 /// position. This routine assumes that this is possible (has been checked).
1083 void SCEVExpander::hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
1084 Instruction *Pos, PHINode *LoopPhi) {
1085 do {
1086 if (DT->dominates(InstToHoist, Pos))
1087 break;
1088 // Make sure the increment is where we want it. But don't move it
1089 // down past a potential existing post-inc user.
1090 fixupInsertPoints(InstToHoist);
1091 InstToHoist->moveBefore(Pos);
1092 Pos = InstToHoist;
1093 InstToHoist = cast<Instruction>(InstToHoist->getOperand(0));
1094 } while (InstToHoist != LoopPhi);
1097 /// Check whether we can cheaply express the requested SCEV in terms of
1098 /// the available PHI SCEV by truncation and/or inversion of the step.
1099 static bool canBeCheaplyTransformed(ScalarEvolution &SE,
1100 const SCEVAddRecExpr *Phi,
1101 const SCEVAddRecExpr *Requested,
1102 bool &InvertStep) {
1103 Type *PhiTy = SE.getEffectiveSCEVType(Phi->getType());
1104 Type *RequestedTy = SE.getEffectiveSCEVType(Requested->getType());
1106 if (RequestedTy->getIntegerBitWidth() > PhiTy->getIntegerBitWidth())
1107 return false;
1109 // Try truncate it if necessary.
1110 Phi = dyn_cast<SCEVAddRecExpr>(SE.getTruncateOrNoop(Phi, RequestedTy));
1111 if (!Phi)
1112 return false;
1114 // Check whether truncation will help.
1115 if (Phi == Requested) {
1116 InvertStep = false;
1117 return true;
1120 // Check whether inverting will help: {R,+,-1} == R - {0,+,1}.
1121 if (SE.getAddExpr(Requested->getStart(),
1122 SE.getNegativeSCEV(Requested)) == Phi) {
1123 InvertStep = true;
1124 return true;
1127 return false;
1130 static bool IsIncrementNSW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1131 if (!isa<IntegerType>(AR->getType()))
1132 return false;
1134 unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1135 Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1136 const SCEV *Step = AR->getStepRecurrence(SE);
1137 const SCEV *OpAfterExtend = SE.getAddExpr(SE.getSignExtendExpr(Step, WideTy),
1138 SE.getSignExtendExpr(AR, WideTy));
1139 const SCEV *ExtendAfterOp =
1140 SE.getSignExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1141 return ExtendAfterOp == OpAfterExtend;
1144 static bool IsIncrementNUW(ScalarEvolution &SE, const SCEVAddRecExpr *AR) {
1145 if (!isa<IntegerType>(AR->getType()))
1146 return false;
1148 unsigned BitWidth = cast<IntegerType>(AR->getType())->getBitWidth();
1149 Type *WideTy = IntegerType::get(AR->getType()->getContext(), BitWidth * 2);
1150 const SCEV *Step = AR->getStepRecurrence(SE);
1151 const SCEV *OpAfterExtend = SE.getAddExpr(SE.getZeroExtendExpr(Step, WideTy),
1152 SE.getZeroExtendExpr(AR, WideTy));
1153 const SCEV *ExtendAfterOp =
1154 SE.getZeroExtendExpr(SE.getAddExpr(AR, Step), WideTy);
1155 return ExtendAfterOp == OpAfterExtend;
1158 /// getAddRecExprPHILiterally - Helper for expandAddRecExprLiterally. Expand
1159 /// the base addrec, which is the addrec without any non-loop-dominating
1160 /// values, and return the PHI.
1161 PHINode *
1162 SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
1163 const Loop *L,
1164 Type *ExpandTy,
1165 Type *IntTy,
1166 Type *&TruncTy,
1167 bool &InvertStep) {
1168 assert((!IVIncInsertLoop||IVIncInsertPos) && "Uninitialized insert position");
1170 // Reuse a previously-inserted PHI, if present.
1171 BasicBlock *LatchBlock = L->getLoopLatch();
1172 if (LatchBlock) {
1173 PHINode *AddRecPhiMatch = nullptr;
1174 Instruction *IncV = nullptr;
1175 TruncTy = nullptr;
1176 InvertStep = false;
1178 // Only try partially matching scevs that need truncation and/or
1179 // step-inversion if we know this loop is outside the current loop.
1180 bool TryNonMatchingSCEV =
1181 IVIncInsertLoop &&
1182 SE.DT.properlyDominates(LatchBlock, IVIncInsertLoop->getHeader());
1184 for (PHINode &PN : L->getHeader()->phis()) {
1185 if (!SE.isSCEVable(PN.getType()))
1186 continue;
1188 const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&PN));
1189 if (!PhiSCEV)
1190 continue;
1192 bool IsMatchingSCEV = PhiSCEV == Normalized;
1193 // We only handle truncation and inversion of phi recurrences for the
1194 // expanded expression if the expanded expression's loop dominates the
1195 // loop we insert to. Check now, so we can bail out early.
1196 if (!IsMatchingSCEV && !TryNonMatchingSCEV)
1197 continue;
1199 // TODO: this possibly can be reworked to avoid this cast at all.
1200 Instruction *TempIncV =
1201 dyn_cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
1202 if (!TempIncV)
1203 continue;
1205 // Check whether we can reuse this PHI node.
1206 if (LSRMode) {
1207 if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
1208 continue;
1209 if (L == IVIncInsertLoop && !hoistIVInc(TempIncV, IVIncInsertPos))
1210 continue;
1211 } else {
1212 if (!isNormalAddRecExprPHI(&PN, TempIncV, L))
1213 continue;
1216 // Stop if we have found an exact match SCEV.
1217 if (IsMatchingSCEV) {
1218 IncV = TempIncV;
1219 TruncTy = nullptr;
1220 InvertStep = false;
1221 AddRecPhiMatch = &PN;
1222 break;
1225 // Try whether the phi can be translated into the requested form
1226 // (truncated and/or offset by a constant).
1227 if ((!TruncTy || InvertStep) &&
1228 canBeCheaplyTransformed(SE, PhiSCEV, Normalized, InvertStep)) {
1229 // Record the phi node. But don't stop we might find an exact match
1230 // later.
1231 AddRecPhiMatch = &PN;
1232 IncV = TempIncV;
1233 TruncTy = SE.getEffectiveSCEVType(Normalized->getType());
1237 if (AddRecPhiMatch) {
1238 // Potentially, move the increment. We have made sure in
1239 // isExpandedAddRecExprPHI or hoistIVInc that this is possible.
1240 if (L == IVIncInsertLoop)
1241 hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch);
1243 // Ok, the add recurrence looks usable.
1244 // Remember this PHI, even in post-inc mode.
1245 InsertedValues.insert(AddRecPhiMatch);
1246 // Remember the increment.
1247 rememberInstruction(IncV);
1248 return AddRecPhiMatch;
1252 // Save the original insertion point so we can restore it when we're done.
1253 SCEVInsertPointGuard Guard(Builder, this);
1255 // Another AddRec may need to be recursively expanded below. For example, if
1256 // this AddRec is quadratic, the StepV may itself be an AddRec in this
1257 // loop. Remove this loop from the PostIncLoops set before expanding such
1258 // AddRecs. Otherwise, we cannot find a valid position for the step
1259 // (i.e. StepV can never dominate its loop header). Ideally, we could do
1260 // SavedIncLoops.swap(PostIncLoops), but we generally have a single element,
1261 // so it's not worth implementing SmallPtrSet::swap.
1262 PostIncLoopSet SavedPostIncLoops = PostIncLoops;
1263 PostIncLoops.clear();
1265 // Expand code for the start value into the loop preheader.
1266 assert(L->getLoopPreheader() &&
1267 "Can't expand add recurrences without a loop preheader!");
1268 Value *StartV = expandCodeFor(Normalized->getStart(), ExpandTy,
1269 L->getLoopPreheader()->getTerminator());
1271 // StartV must have been be inserted into L's preheader to dominate the new
1272 // phi.
1273 assert(!isa<Instruction>(StartV) ||
1274 SE.DT.properlyDominates(cast<Instruction>(StartV)->getParent(),
1275 L->getHeader()));
1277 // Expand code for the step value. Do this before creating the PHI so that PHI
1278 // reuse code doesn't see an incomplete PHI.
1279 const SCEV *Step = Normalized->getStepRecurrence(SE);
1280 // If the stride is negative, insert a sub instead of an add for the increment
1281 // (unless it's a constant, because subtracts of constants are canonicalized
1282 // to adds).
1283 bool useSubtract = !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1284 if (useSubtract)
1285 Step = SE.getNegativeSCEV(Step);
1286 // Expand the step somewhere that dominates the loop header.
1287 Value *StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front());
1289 // The no-wrap behavior proved by IsIncrement(NUW|NSW) is only applicable if
1290 // we actually do emit an addition. It does not apply if we emit a
1291 // subtraction.
1292 bool IncrementIsNUW = !useSubtract && IsIncrementNUW(SE, Normalized);
1293 bool IncrementIsNSW = !useSubtract && IsIncrementNSW(SE, Normalized);
1295 // Create the PHI.
1296 BasicBlock *Header = L->getHeader();
1297 Builder.SetInsertPoint(Header, Header->begin());
1298 pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1299 PHINode *PN = Builder.CreatePHI(ExpandTy, std::distance(HPB, HPE),
1300 Twine(IVName) + ".iv");
1301 rememberInstruction(PN);
1303 // Create the step instructions and populate the PHI.
1304 for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1305 BasicBlock *Pred = *HPI;
1307 // Add a start value.
1308 if (!L->contains(Pred)) {
1309 PN->addIncoming(StartV, Pred);
1310 continue;
1313 // Create a step value and add it to the PHI.
1314 // If IVIncInsertLoop is non-null and equal to the addrec's loop, insert the
1315 // instructions at IVIncInsertPos.
1316 Instruction *InsertPos = L == IVIncInsertLoop ?
1317 IVIncInsertPos : Pred->getTerminator();
1318 Builder.SetInsertPoint(InsertPos);
1319 Value *IncV = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1321 if (isa<OverflowingBinaryOperator>(IncV)) {
1322 if (IncrementIsNUW)
1323 cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
1324 if (IncrementIsNSW)
1325 cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
1327 PN->addIncoming(IncV, Pred);
1330 // After expanding subexpressions, restore the PostIncLoops set so the caller
1331 // can ensure that IVIncrement dominates the current uses.
1332 PostIncLoops = SavedPostIncLoops;
1334 // Remember this PHI, even in post-inc mode.
1335 InsertedValues.insert(PN);
1337 return PN;
1340 Value *SCEVExpander::expandAddRecExprLiterally(const SCEVAddRecExpr *S) {
1341 Type *STy = S->getType();
1342 Type *IntTy = SE.getEffectiveSCEVType(STy);
1343 const Loop *L = S->getLoop();
1345 // Determine a normalized form of this expression, which is the expression
1346 // before any post-inc adjustment is made.
1347 const SCEVAddRecExpr *Normalized = S;
1348 if (PostIncLoops.count(L)) {
1349 PostIncLoopSet Loops;
1350 Loops.insert(L);
1351 Normalized = cast<SCEVAddRecExpr>(normalizeForPostIncUse(S, Loops, SE));
1354 // Strip off any non-loop-dominating component from the addrec start.
1355 const SCEV *Start = Normalized->getStart();
1356 const SCEV *PostLoopOffset = nullptr;
1357 if (!SE.properlyDominates(Start, L->getHeader())) {
1358 PostLoopOffset = Start;
1359 Start = SE.getConstant(Normalized->getType(), 0);
1360 Normalized = cast<SCEVAddRecExpr>(
1361 SE.getAddRecExpr(Start, Normalized->getStepRecurrence(SE),
1362 Normalized->getLoop(),
1363 Normalized->getNoWrapFlags(SCEV::FlagNW)));
1366 // Strip off any non-loop-dominating component from the addrec step.
1367 const SCEV *Step = Normalized->getStepRecurrence(SE);
1368 const SCEV *PostLoopScale = nullptr;
1369 if (!SE.dominates(Step, L->getHeader())) {
1370 PostLoopScale = Step;
1371 Step = SE.getConstant(Normalized->getType(), 1);
1372 if (!Start->isZero()) {
1373 // The normalization below assumes that Start is constant zero, so if
1374 // it isn't re-associate Start to PostLoopOffset.
1375 assert(!PostLoopOffset && "Start not-null but PostLoopOffset set?");
1376 PostLoopOffset = Start;
1377 Start = SE.getConstant(Normalized->getType(), 0);
1379 Normalized =
1380 cast<SCEVAddRecExpr>(SE.getAddRecExpr(
1381 Start, Step, Normalized->getLoop(),
1382 Normalized->getNoWrapFlags(SCEV::FlagNW)));
1385 // Expand the core addrec. If we need post-loop scaling, force it to
1386 // expand to an integer type to avoid the need for additional casting.
1387 Type *ExpandTy = PostLoopScale ? IntTy : STy;
1388 // We can't use a pointer type for the addrec if the pointer type is
1389 // non-integral.
1390 Type *AddRecPHIExpandTy =
1391 DL.isNonIntegralPointerType(STy) ? Normalized->getType() : ExpandTy;
1393 // In some cases, we decide to reuse an existing phi node but need to truncate
1394 // it and/or invert the step.
1395 Type *TruncTy = nullptr;
1396 bool InvertStep = false;
1397 PHINode *PN = getAddRecExprPHILiterally(Normalized, L, AddRecPHIExpandTy,
1398 IntTy, TruncTy, InvertStep);
1400 // Accommodate post-inc mode, if necessary.
1401 Value *Result;
1402 if (!PostIncLoops.count(L))
1403 Result = PN;
1404 else {
1405 // In PostInc mode, use the post-incremented value.
1406 BasicBlock *LatchBlock = L->getLoopLatch();
1407 assert(LatchBlock && "PostInc mode requires a unique loop latch!");
1408 Result = PN->getIncomingValueForBlock(LatchBlock);
1410 // For an expansion to use the postinc form, the client must call
1411 // expandCodeFor with an InsertPoint that is either outside the PostIncLoop
1412 // or dominated by IVIncInsertPos.
1413 if (isa<Instruction>(Result) &&
1414 !SE.DT.dominates(cast<Instruction>(Result),
1415 &*Builder.GetInsertPoint())) {
1416 // The induction variable's postinc expansion does not dominate this use.
1417 // IVUsers tries to prevent this case, so it is rare. However, it can
1418 // happen when an IVUser outside the loop is not dominated by the latch
1419 // block. Adjusting IVIncInsertPos before expansion begins cannot handle
1420 // all cases. Consider a phi outside whose operand is replaced during
1421 // expansion with the value of the postinc user. Without fundamentally
1422 // changing the way postinc users are tracked, the only remedy is
1423 // inserting an extra IV increment. StepV might fold into PostLoopOffset,
1424 // but hopefully expandCodeFor handles that.
1425 bool useSubtract =
1426 !ExpandTy->isPointerTy() && Step->isNonConstantNegative();
1427 if (useSubtract)
1428 Step = SE.getNegativeSCEV(Step);
1429 Value *StepV;
1431 // Expand the step somewhere that dominates the loop header.
1432 SCEVInsertPointGuard Guard(Builder, this);
1433 StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front());
1435 Result = expandIVInc(PN, StepV, L, ExpandTy, IntTy, useSubtract);
1439 // We have decided to reuse an induction variable of a dominating loop. Apply
1440 // truncation and/or inversion of the step.
1441 if (TruncTy) {
1442 Type *ResTy = Result->getType();
1443 // Normalize the result type.
1444 if (ResTy != SE.getEffectiveSCEVType(ResTy))
1445 Result = InsertNoopCastOfTo(Result, SE.getEffectiveSCEVType(ResTy));
1446 // Truncate the result.
1447 if (TruncTy != Result->getType()) {
1448 Result = Builder.CreateTrunc(Result, TruncTy);
1449 rememberInstruction(Result);
1451 // Invert the result.
1452 if (InvertStep) {
1453 Result = Builder.CreateSub(expandCodeFor(Normalized->getStart(), TruncTy),
1454 Result);
1455 rememberInstruction(Result);
1459 // Re-apply any non-loop-dominating scale.
1460 if (PostLoopScale) {
1461 assert(S->isAffine() && "Can't linearly scale non-affine recurrences.");
1462 Result = InsertNoopCastOfTo(Result, IntTy);
1463 Result = Builder.CreateMul(Result,
1464 expandCodeFor(PostLoopScale, IntTy));
1465 rememberInstruction(Result);
1468 // Re-apply any non-loop-dominating offset.
1469 if (PostLoopOffset) {
1470 if (PointerType *PTy = dyn_cast<PointerType>(ExpandTy)) {
1471 if (Result->getType()->isIntegerTy()) {
1472 Value *Base = expandCodeFor(PostLoopOffset, ExpandTy);
1473 Result = expandAddToGEP(SE.getUnknown(Result), PTy, IntTy, Base);
1474 } else {
1475 Result = expandAddToGEP(PostLoopOffset, PTy, IntTy, Result);
1477 } else {
1478 Result = InsertNoopCastOfTo(Result, IntTy);
1479 Result = Builder.CreateAdd(Result,
1480 expandCodeFor(PostLoopOffset, IntTy));
1481 rememberInstruction(Result);
1485 return Result;
1488 Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) {
1489 if (!CanonicalMode) return expandAddRecExprLiterally(S);
1491 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1492 const Loop *L = S->getLoop();
1494 // First check for an existing canonical IV in a suitable type.
1495 PHINode *CanonicalIV = nullptr;
1496 if (PHINode *PN = L->getCanonicalInductionVariable())
1497 if (SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty))
1498 CanonicalIV = PN;
1500 // Rewrite an AddRec in terms of the canonical induction variable, if
1501 // its type is more narrow.
1502 if (CanonicalIV &&
1503 SE.getTypeSizeInBits(CanonicalIV->getType()) >
1504 SE.getTypeSizeInBits(Ty)) {
1505 SmallVector<const SCEV *, 4> NewOps(S->getNumOperands());
1506 for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i)
1507 NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType());
1508 Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop(),
1509 S->getNoWrapFlags(SCEV::FlagNW)));
1510 BasicBlock::iterator NewInsertPt =
1511 findInsertPointAfter(cast<Instruction>(V), Builder.GetInsertBlock());
1512 V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), nullptr,
1513 &*NewInsertPt);
1514 return V;
1517 // {X,+,F} --> X + {0,+,F}
1518 if (!S->getStart()->isZero()) {
1519 SmallVector<const SCEV *, 4> NewOps(S->op_begin(), S->op_end());
1520 NewOps[0] = SE.getConstant(Ty, 0);
1521 const SCEV *Rest = SE.getAddRecExpr(NewOps, L,
1522 S->getNoWrapFlags(SCEV::FlagNW));
1524 // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the
1525 // comments on expandAddToGEP for details.
1526 const SCEV *Base = S->getStart();
1527 // Dig into the expression to find the pointer base for a GEP.
1528 const SCEV *ExposedRest = Rest;
1529 ExposePointerBase(Base, ExposedRest, SE);
1530 // If we found a pointer, expand the AddRec with a GEP.
1531 if (PointerType *PTy = dyn_cast<PointerType>(Base->getType())) {
1532 // Make sure the Base isn't something exotic, such as a multiplied
1533 // or divided pointer value. In those cases, the result type isn't
1534 // actually a pointer type.
1535 if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) {
1536 Value *StartV = expand(Base);
1537 assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!");
1538 return expandAddToGEP(ExposedRest, PTy, Ty, StartV);
1542 // Just do a normal add. Pre-expand the operands to suppress folding.
1544 // The LHS and RHS values are factored out of the expand call to make the
1545 // output independent of the argument evaluation order.
1546 const SCEV *AddExprLHS = SE.getUnknown(expand(S->getStart()));
1547 const SCEV *AddExprRHS = SE.getUnknown(expand(Rest));
1548 return expand(SE.getAddExpr(AddExprLHS, AddExprRHS));
1551 // If we don't yet have a canonical IV, create one.
1552 if (!CanonicalIV) {
1553 // Create and insert the PHI node for the induction variable in the
1554 // specified loop.
1555 BasicBlock *Header = L->getHeader();
1556 pred_iterator HPB = pred_begin(Header), HPE = pred_end(Header);
1557 CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar",
1558 &Header->front());
1559 rememberInstruction(CanonicalIV);
1561 SmallSet<BasicBlock *, 4> PredSeen;
1562 Constant *One = ConstantInt::get(Ty, 1);
1563 for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1564 BasicBlock *HP = *HPI;
1565 if (!PredSeen.insert(HP).second) {
1566 // There must be an incoming value for each predecessor, even the
1567 // duplicates!
1568 CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP);
1569 continue;
1572 if (L->contains(HP)) {
1573 // Insert a unit add instruction right before the terminator
1574 // corresponding to the back-edge.
1575 Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One,
1576 "indvar.next",
1577 HP->getTerminator());
1578 Add->setDebugLoc(HP->getTerminator()->getDebugLoc());
1579 rememberInstruction(Add);
1580 CanonicalIV->addIncoming(Add, HP);
1581 } else {
1582 CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP);
1587 // {0,+,1} --> Insert a canonical induction variable into the loop!
1588 if (S->isAffine() && S->getOperand(1)->isOne()) {
1589 assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) &&
1590 "IVs with types different from the canonical IV should "
1591 "already have been handled!");
1592 return CanonicalIV;
1595 // {0,+,F} --> {0,+,1} * F
1597 // If this is a simple linear addrec, emit it now as a special case.
1598 if (S->isAffine()) // {0,+,F} --> i*F
1599 return
1600 expand(SE.getTruncateOrNoop(
1601 SE.getMulExpr(SE.getUnknown(CanonicalIV),
1602 SE.getNoopOrAnyExtend(S->getOperand(1),
1603 CanonicalIV->getType())),
1604 Ty));
1606 // If this is a chain of recurrences, turn it into a closed form, using the
1607 // folders, then expandCodeFor the closed form. This allows the folders to
1608 // simplify the expression without having to build a bunch of special code
1609 // into this folder.
1610 const SCEV *IH = SE.getUnknown(CanonicalIV); // Get I as a "symbolic" SCEV.
1612 // Promote S up to the canonical IV type, if the cast is foldable.
1613 const SCEV *NewS = S;
1614 const SCEV *Ext = SE.getNoopOrAnyExtend(S, CanonicalIV->getType());
1615 if (isa<SCEVAddRecExpr>(Ext))
1616 NewS = Ext;
1618 const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE);
1619 //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n";
1621 // Truncate the result down to the original type, if needed.
1622 const SCEV *T = SE.getTruncateOrNoop(V, Ty);
1623 return expand(T);
1626 Value *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) {
1627 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1628 Value *V = expandCodeFor(S->getOperand(),
1629 SE.getEffectiveSCEVType(S->getOperand()->getType()));
1630 Value *I = Builder.CreateTrunc(V, Ty);
1631 rememberInstruction(I);
1632 return I;
1635 Value *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) {
1636 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1637 Value *V = expandCodeFor(S->getOperand(),
1638 SE.getEffectiveSCEVType(S->getOperand()->getType()));
1639 Value *I = Builder.CreateZExt(V, Ty);
1640 rememberInstruction(I);
1641 return I;
1644 Value *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) {
1645 Type *Ty = SE.getEffectiveSCEVType(S->getType());
1646 Value *V = expandCodeFor(S->getOperand(),
1647 SE.getEffectiveSCEVType(S->getOperand()->getType()));
1648 Value *I = Builder.CreateSExt(V, Ty);
1649 rememberInstruction(I);
1650 return I;
1653 Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) {
1654 Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
1655 Type *Ty = LHS->getType();
1656 for (int i = S->getNumOperands()-2; i >= 0; --i) {
1657 // In the case of mixed integer and pointer types, do the
1658 // rest of the comparisons as integer.
1659 Type *OpTy = S->getOperand(i)->getType();
1660 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1661 Ty = SE.getEffectiveSCEVType(Ty);
1662 LHS = InsertNoopCastOfTo(LHS, Ty);
1664 Value *RHS = expandCodeFor(S->getOperand(i), Ty);
1665 Value *ICmp = Builder.CreateICmpSGT(LHS, RHS);
1666 rememberInstruction(ICmp);
1667 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax");
1668 rememberInstruction(Sel);
1669 LHS = Sel;
1671 // In the case of mixed integer and pointer types, cast the
1672 // final result back to the pointer type.
1673 if (LHS->getType() != S->getType())
1674 LHS = InsertNoopCastOfTo(LHS, S->getType());
1675 return LHS;
1678 Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) {
1679 Value *LHS = expand(S->getOperand(S->getNumOperands()-1));
1680 Type *Ty = LHS->getType();
1681 for (int i = S->getNumOperands()-2; i >= 0; --i) {
1682 // In the case of mixed integer and pointer types, do the
1683 // rest of the comparisons as integer.
1684 Type *OpTy = S->getOperand(i)->getType();
1685 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1686 Ty = SE.getEffectiveSCEVType(Ty);
1687 LHS = InsertNoopCastOfTo(LHS, Ty);
1689 Value *RHS = expandCodeFor(S->getOperand(i), Ty);
1690 Value *ICmp = Builder.CreateICmpUGT(LHS, RHS);
1691 rememberInstruction(ICmp);
1692 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax");
1693 rememberInstruction(Sel);
1694 LHS = Sel;
1696 // In the case of mixed integer and pointer types, cast the
1697 // final result back to the pointer type.
1698 if (LHS->getType() != S->getType())
1699 LHS = InsertNoopCastOfTo(LHS, S->getType());
1700 return LHS;
1703 Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) {
1704 Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
1705 Type *Ty = LHS->getType();
1706 for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1707 // In the case of mixed integer and pointer types, do the
1708 // rest of the comparisons as integer.
1709 Type *OpTy = S->getOperand(i)->getType();
1710 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1711 Ty = SE.getEffectiveSCEVType(Ty);
1712 LHS = InsertNoopCastOfTo(LHS, Ty);
1714 Value *RHS = expandCodeFor(S->getOperand(i), Ty);
1715 Value *ICmp = Builder.CreateICmpSLT(LHS, RHS);
1716 rememberInstruction(ICmp);
1717 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smin");
1718 rememberInstruction(Sel);
1719 LHS = Sel;
1721 // In the case of mixed integer and pointer types, cast the
1722 // final result back to the pointer type.
1723 if (LHS->getType() != S->getType())
1724 LHS = InsertNoopCastOfTo(LHS, S->getType());
1725 return LHS;
1728 Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {
1729 Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
1730 Type *Ty = LHS->getType();
1731 for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1732 // In the case of mixed integer and pointer types, do the
1733 // rest of the comparisons as integer.
1734 Type *OpTy = S->getOperand(i)->getType();
1735 if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
1736 Ty = SE.getEffectiveSCEVType(Ty);
1737 LHS = InsertNoopCastOfTo(LHS, Ty);
1739 Value *RHS = expandCodeFor(S->getOperand(i), Ty);
1740 Value *ICmp = Builder.CreateICmpULT(LHS, RHS);
1741 rememberInstruction(ICmp);
1742 Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umin");
1743 rememberInstruction(Sel);
1744 LHS = Sel;
1746 // In the case of mixed integer and pointer types, cast the
1747 // final result back to the pointer type.
1748 if (LHS->getType() != S->getType())
1749 LHS = InsertNoopCastOfTo(LHS, S->getType());
1750 return LHS;
1753 Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty,
1754 Instruction *IP) {
1755 setInsertPoint(IP);
1756 return expandCodeFor(SH, Ty);
1759 Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty) {
1760 // Expand the code for this SCEV.
1761 Value *V = expand(SH);
1762 if (Ty) {
1763 assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) &&
1764 "non-trivial casts should be done with the SCEVs directly!");
1765 V = InsertNoopCastOfTo(V, Ty);
1767 return V;
1770 ScalarEvolution::ValueOffsetPair
1771 SCEVExpander::FindValueInExprValueMap(const SCEV *S,
1772 const Instruction *InsertPt) {
1773 SetVector<ScalarEvolution::ValueOffsetPair> *Set = SE.getSCEVValues(S);
1774 // If the expansion is not in CanonicalMode, and the SCEV contains any
1775 // sub scAddRecExpr type SCEV, it is required to expand the SCEV literally.
1776 if (CanonicalMode || !SE.containsAddRecurrence(S)) {
1777 // If S is scConstant, it may be worse to reuse an existing Value.
1778 if (S->getSCEVType() != scConstant && Set) {
1779 // Choose a Value from the set which dominates the insertPt.
1780 // insertPt should be inside the Value's parent loop so as not to break
1781 // the LCSSA form.
1782 for (auto const &VOPair : *Set) {
1783 Value *V = VOPair.first;
1784 ConstantInt *Offset = VOPair.second;
1785 Instruction *EntInst = nullptr;
1786 if (V && isa<Instruction>(V) && (EntInst = cast<Instruction>(V)) &&
1787 S->getType() == V->getType() &&
1788 EntInst->getFunction() == InsertPt->getFunction() &&
1789 SE.DT.dominates(EntInst, InsertPt) &&
1790 (SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
1791 SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))
1792 return {V, Offset};
1796 return {nullptr, nullptr};
1799 // The expansion of SCEV will either reuse a previous Value in ExprValueMap,
1800 // or expand the SCEV literally. Specifically, if the expansion is in LSRMode,
1801 // and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded
1802 // literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,
1803 // the expansion will try to reuse Value from ExprValueMap, and only when it
1804 // fails, expand the SCEV literally.
1805 Value *SCEVExpander::expand(const SCEV *S) {
1806 // Compute an insertion point for this SCEV object. Hoist the instructions
1807 // as far out in the loop nest as possible.
1808 Instruction *InsertPt = &*Builder.GetInsertPoint();
1810 // We can move insertion point only if there is no div or rem operations
1811 // otherwise we are risky to move it over the check for zero denominator.
1812 auto SafeToHoist = [](const SCEV *S) {
1813 return !SCEVExprContains(S, [](const SCEV *S) {
1814 if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) {
1815 if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS()))
1816 // Division by non-zero constants can be hoisted.
1817 return SC->getValue()->isZero();
1818 // All other divisions should not be moved as they may be
1819 // divisions by zero and should be kept within the
1820 // conditions of the surrounding loops that guard their
1821 // execution (see PR35406).
1822 return true;
1824 return false;
1827 if (SafeToHoist(S)) {
1828 for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
1829 L = L->getParentLoop()) {
1830 if (SE.isLoopInvariant(S, L)) {
1831 if (!L) break;
1832 if (BasicBlock *Preheader = L->getLoopPreheader())
1833 InsertPt = Preheader->getTerminator();
1834 else
1835 // LSR sets the insertion point for AddRec start/step values to the
1836 // block start to simplify value reuse, even though it's an invalid
1837 // position. SCEVExpander must correct for this in all cases.
1838 InsertPt = &*L->getHeader()->getFirstInsertionPt();
1839 } else {
1840 // If the SCEV is computable at this level, insert it into the header
1841 // after the PHIs (and after any other instructions that we've inserted
1842 // there) so that it is guaranteed to dominate any user inside the loop.
1843 if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
1844 InsertPt = &*L->getHeader()->getFirstInsertionPt();
1845 while (InsertPt->getIterator() != Builder.GetInsertPoint() &&
1846 (isInsertedInstruction(InsertPt) ||
1847 isa<DbgInfoIntrinsic>(InsertPt)))
1848 InsertPt = &*std::next(InsertPt->getIterator());
1849 break;
1854 // IndVarSimplify sometimes sets the insertion point at the block start, even
1855 // when there are PHIs at that point. We must correct for this.
1856 if (isa<PHINode>(*InsertPt))
1857 InsertPt = &*InsertPt->getParent()->getFirstInsertionPt();
1859 // Check to see if we already expanded this here.
1860 auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
1861 if (I != InsertedExpressions.end())
1862 return I->second;
1864 SCEVInsertPointGuard Guard(Builder, this);
1865 Builder.SetInsertPoint(InsertPt);
1867 // Expand the expression into instructions.
1868 ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, InsertPt);
1869 Value *V = VO.first;
1871 if (!V)
1872 V = visit(S);
1873 else if (VO.second) {
1874 if (PointerType *Vty = dyn_cast<PointerType>(V->getType())) {
1875 Type *Ety = Vty->getPointerElementType();
1876 int64_t Offset = VO.second->getSExtValue();
1877 int64_t ESize = SE.getTypeSizeInBits(Ety);
1878 if ((Offset * 8) % ESize == 0) {
1879 ConstantInt *Idx =
1880 ConstantInt::getSigned(VO.second->getType(), -(Offset * 8) / ESize);
1881 V = Builder.CreateGEP(Ety, V, Idx, "scevgep");
1882 } else {
1883 ConstantInt *Idx =
1884 ConstantInt::getSigned(VO.second->getType(), -Offset);
1885 unsigned AS = Vty->getAddressSpace();
1886 V = Builder.CreateBitCast(V, Type::getInt8PtrTy(SE.getContext(), AS));
1887 V = Builder.CreateGEP(Type::getInt8Ty(SE.getContext()), V, Idx,
1888 "uglygep");
1889 V = Builder.CreateBitCast(V, Vty);
1891 } else {
1892 V = Builder.CreateSub(V, VO.second);
1895 // Remember the expanded value for this SCEV at this location.
1897 // This is independent of PostIncLoops. The mapped value simply materializes
1898 // the expression at this insertion point. If the mapped value happened to be
1899 // a postinc expansion, it could be reused by a non-postinc user, but only if
1900 // its insertion point was already at the head of the loop.
1901 InsertedExpressions[std::make_pair(S, InsertPt)] = V;
1902 return V;
1905 void SCEVExpander::rememberInstruction(Value *I) {
1906 if (!PostIncLoops.empty())
1907 InsertedPostIncValues.insert(I);
1908 else
1909 InsertedValues.insert(I);
1912 /// getOrInsertCanonicalInductionVariable - This method returns the
1913 /// canonical induction variable of the specified type for the specified
1914 /// loop (inserting one if there is none). A canonical induction variable
1915 /// starts at zero and steps by one on each iteration.
1916 PHINode *
1917 SCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L,
1918 Type *Ty) {
1919 assert(Ty->isIntegerTy() && "Can only insert integer induction variables!");
1921 // Build a SCEV for {0,+,1}<L>.
1922 // Conservatively use FlagAnyWrap for now.
1923 const SCEV *H = SE.getAddRecExpr(SE.getConstant(Ty, 0),
1924 SE.getConstant(Ty, 1), L, SCEV::FlagAnyWrap);
1926 // Emit code for it.
1927 SCEVInsertPointGuard Guard(Builder, this);
1928 PHINode *V =
1929 cast<PHINode>(expandCodeFor(H, nullptr, &L->getHeader()->front()));
1931 return V;
1934 /// replaceCongruentIVs - Check for congruent phis in this loop header and
1935 /// replace them with their most canonical representative. Return the number of
1936 /// phis eliminated.
1938 /// This does not depend on any SCEVExpander state but should be used in
1939 /// the same context that SCEVExpander is used.
1940 unsigned
1941 SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
1942 SmallVectorImpl<WeakTrackingVH> &DeadInsts,
1943 const TargetTransformInfo *TTI) {
1944 // Find integer phis in order of increasing width.
1945 SmallVector<PHINode*, 8> Phis;
1946 for (PHINode &PN : L->getHeader()->phis())
1947 Phis.push_back(&PN);
1949 if (TTI)
1950 llvm::sort(Phis, [](Value *LHS, Value *RHS) {
1951 // Put pointers at the back and make sure pointer < pointer = false.
1952 if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
1953 return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();
1954 return RHS->getType()->getPrimitiveSizeInBits() <
1955 LHS->getType()->getPrimitiveSizeInBits();
1958 unsigned NumElim = 0;
1959 DenseMap<const SCEV *, PHINode *> ExprToIVMap;
1960 // Process phis from wide to narrow. Map wide phis to their truncation
1961 // so narrow phis can reuse them.
1962 for (PHINode *Phi : Phis) {
1963 auto SimplifyPHINode = [&](PHINode *PN) -> Value * {
1964 if (Value *V = SimplifyInstruction(PN, {DL, &SE.TLI, &SE.DT, &SE.AC}))
1965 return V;
1966 if (!SE.isSCEVable(PN->getType()))
1967 return nullptr;
1968 auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(PN));
1969 if (!Const)
1970 return nullptr;
1971 return Const->getValue();
1974 // Fold constant phis. They may be congruent to other constant phis and
1975 // would confuse the logic below that expects proper IVs.
1976 if (Value *V = SimplifyPHINode(Phi)) {
1977 if (V->getType() != Phi->getType())
1978 continue;
1979 Phi->replaceAllUsesWith(V);
1980 DeadInsts.emplace_back(Phi);
1981 ++NumElim;
1982 DEBUG_WITH_TYPE(DebugType, dbgs()
1983 << "INDVARS: Eliminated constant iv: " << *Phi << '\n');
1984 continue;
1987 if (!SE.isSCEVable(Phi->getType()))
1988 continue;
1990 PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
1991 if (!OrigPhiRef) {
1992 OrigPhiRef = Phi;
1993 if (Phi->getType()->isIntegerTy() && TTI &&
1994 TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
1995 // This phi can be freely truncated to the narrowest phi type. Map the
1996 // truncated expression to it so it will be reused for narrow types.
1997 const SCEV *TruncExpr =
1998 SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType());
1999 ExprToIVMap[TruncExpr] = Phi;
2001 continue;
2004 // Replacing a pointer phi with an integer phi or vice-versa doesn't make
2005 // sense.
2006 if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy())
2007 continue;
2009 if (BasicBlock *LatchBlock = L->getLoopLatch()) {
2010 Instruction *OrigInc = dyn_cast<Instruction>(
2011 OrigPhiRef->getIncomingValueForBlock(LatchBlock));
2012 Instruction *IsomorphicInc =
2013 dyn_cast<Instruction>(Phi->getIncomingValueForBlock(LatchBlock));
2015 if (OrigInc && IsomorphicInc) {
2016 // If this phi has the same width but is more canonical, replace the
2017 // original with it. As part of the "more canonical" determination,
2018 // respect a prior decision to use an IV chain.
2019 if (OrigPhiRef->getType() == Phi->getType() &&
2020 !(ChainedPhis.count(Phi) ||
2021 isExpandedAddRecExprPHI(OrigPhiRef, OrigInc, L)) &&
2022 (ChainedPhis.count(Phi) ||
2023 isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
2024 std::swap(OrigPhiRef, Phi);
2025 std::swap(OrigInc, IsomorphicInc);
2027 // Replacing the congruent phi is sufficient because acyclic
2028 // redundancy elimination, CSE/GVN, should handle the
2029 // rest. However, once SCEV proves that a phi is congruent,
2030 // it's often the head of an IV user cycle that is isomorphic
2031 // with the original phi. It's worth eagerly cleaning up the
2032 // common case of a single IV increment so that DeleteDeadPHIs
2033 // can remove cycles that had postinc uses.
2034 const SCEV *TruncExpr =
2035 SE.getTruncateOrNoop(SE.getSCEV(OrigInc), IsomorphicInc->getType());
2036 if (OrigInc != IsomorphicInc &&
2037 TruncExpr == SE.getSCEV(IsomorphicInc) &&
2038 SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc) &&
2039 hoistIVInc(OrigInc, IsomorphicInc)) {
2040 DEBUG_WITH_TYPE(DebugType,
2041 dbgs() << "INDVARS: Eliminated congruent iv.inc: "
2042 << *IsomorphicInc << '\n');
2043 Value *NewInc = OrigInc;
2044 if (OrigInc->getType() != IsomorphicInc->getType()) {
2045 Instruction *IP = nullptr;
2046 if (PHINode *PN = dyn_cast<PHINode>(OrigInc))
2047 IP = &*PN->getParent()->getFirstInsertionPt();
2048 else
2049 IP = OrigInc->getNextNode();
2051 IRBuilder<> Builder(IP);
2052 Builder.SetCurrentDebugLocation(IsomorphicInc->getDebugLoc());
2053 NewInc = Builder.CreateTruncOrBitCast(
2054 OrigInc, IsomorphicInc->getType(), IVName);
2056 IsomorphicInc->replaceAllUsesWith(NewInc);
2057 DeadInsts.emplace_back(IsomorphicInc);
2061 DEBUG_WITH_TYPE(DebugType, dbgs() << "INDVARS: Eliminated congruent iv: "
2062 << *Phi << '\n');
2063 ++NumElim;
2064 Value *NewIV = OrigPhiRef;
2065 if (OrigPhiRef->getType() != Phi->getType()) {
2066 IRBuilder<> Builder(&*L->getHeader()->getFirstInsertionPt());
2067 Builder.SetCurrentDebugLocation(Phi->getDebugLoc());
2068 NewIV = Builder.CreateTruncOrBitCast(OrigPhiRef, Phi->getType(), IVName);
2070 Phi->replaceAllUsesWith(NewIV);
2071 DeadInsts.emplace_back(Phi);
2073 return NumElim;
2076 Value *SCEVExpander::getExactExistingExpansion(const SCEV *S,
2077 const Instruction *At, Loop *L) {
2078 Optional<ScalarEvolution::ValueOffsetPair> VO =
2079 getRelatedExistingExpansion(S, At, L);
2080 if (VO && VO.getValue().second == nullptr)
2081 return VO.getValue().first;
2082 return nullptr;
2085 Optional<ScalarEvolution::ValueOffsetPair>
2086 SCEVExpander::getRelatedExistingExpansion(const SCEV *S, const Instruction *At,
2087 Loop *L) {
2088 using namespace llvm::PatternMatch;
2090 SmallVector<BasicBlock *, 4> ExitingBlocks;
2091 L->getExitingBlocks(ExitingBlocks);
2093 // Look for suitable value in simple conditions at the loop exits.
2094 for (BasicBlock *BB : ExitingBlocks) {
2095 ICmpInst::Predicate Pred;
2096 Instruction *LHS, *RHS;
2097 BasicBlock *TrueBB, *FalseBB;
2099 if (!match(BB->getTerminator(),
2100 m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
2101 TrueBB, FalseBB)))
2102 continue;
2104 if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
2105 return ScalarEvolution::ValueOffsetPair(LHS, nullptr);
2107 if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, At))
2108 return ScalarEvolution::ValueOffsetPair(RHS, nullptr);
2111 // Use expand's logic which is used for reusing a previous Value in
2112 // ExprValueMap.
2113 ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At);
2114 if (VO.first)
2115 return VO;
2117 // There is potential to make this significantly smarter, but this simple
2118 // heuristic already gets some interesting cases.
2120 // Can not find suitable value.
2121 return None;
2124 bool SCEVExpander::isHighCostExpansionHelper(
2125 const SCEV *S, Loop *L, const Instruction *At,
2126 SmallPtrSetImpl<const SCEV *> &Processed) {
2128 // If we can find an existing value for this scev available at the point "At"
2129 // then consider the expression cheap.
2130 if (At && getRelatedExistingExpansion(S, At, L))
2131 return false;
2133 // Zero/One operand expressions
2134 switch (S->getSCEVType()) {
2135 case scUnknown:
2136 case scConstant:
2137 return false;
2138 case scTruncate:
2139 return isHighCostExpansionHelper(cast<SCEVTruncateExpr>(S)->getOperand(),
2140 L, At, Processed);
2141 case scZeroExtend:
2142 return isHighCostExpansionHelper(cast<SCEVZeroExtendExpr>(S)->getOperand(),
2143 L, At, Processed);
2144 case scSignExtend:
2145 return isHighCostExpansionHelper(cast<SCEVSignExtendExpr>(S)->getOperand(),
2146 L, At, Processed);
2149 if (!Processed.insert(S).second)
2150 return false;
2152 if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) {
2153 // If the divisor is a power of two and the SCEV type fits in a native
2154 // integer (and the LHS not expensive), consider the division cheap
2155 // irrespective of whether it occurs in the user code since it can be
2156 // lowered into a right shift.
2157 if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS()))
2158 if (SC->getAPInt().isPowerOf2()) {
2159 if (isHighCostExpansionHelper(UDivExpr->getLHS(), L, At, Processed))
2160 return true;
2161 const DataLayout &DL =
2162 L->getHeader()->getParent()->getParent()->getDataLayout();
2163 unsigned Width = cast<IntegerType>(UDivExpr->getType())->getBitWidth();
2164 return DL.isIllegalInteger(Width);
2167 // UDivExpr is very likely a UDiv that ScalarEvolution's HowFarToZero or
2168 // HowManyLessThans produced to compute a precise expression, rather than a
2169 // UDiv from the user's code. If we can't find a UDiv in the code with some
2170 // simple searching, assume the former consider UDivExpr expensive to
2171 // compute.
2172 BasicBlock *ExitingBB = L->getExitingBlock();
2173 if (!ExitingBB)
2174 return true;
2176 // At the beginning of this function we already tried to find existing value
2177 // for plain 'S'. Now try to lookup 'S + 1' since it is common pattern
2178 // involving division. This is just a simple search heuristic.
2179 if (!At)
2180 At = &ExitingBB->back();
2181 if (!getRelatedExistingExpansion(
2182 SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), At, L))
2183 return true;
2186 // HowManyLessThans uses a Max expression whenever the loop is not guarded by
2187 // the exit condition.
2188 if (isa<SCEVMinMaxExpr>(S))
2189 return true;
2191 // Recurse past nary expressions, which commonly occur in the
2192 // BackedgeTakenCount. They may already exist in program code, and if not,
2193 // they are not too expensive rematerialize.
2194 if (const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(S)) {
2195 for (auto *Op : NAry->operands())
2196 if (isHighCostExpansionHelper(Op, L, At, Processed))
2197 return true;
2200 // If we haven't recognized an expensive SCEV pattern, assume it's an
2201 // expression produced by program code.
2202 return false;
2205 Value *SCEVExpander::expandCodeForPredicate(const SCEVPredicate *Pred,
2206 Instruction *IP) {
2207 assert(IP);
2208 switch (Pred->getKind()) {
2209 case SCEVPredicate::P_Union:
2210 return expandUnionPredicate(cast<SCEVUnionPredicate>(Pred), IP);
2211 case SCEVPredicate::P_Equal:
2212 return expandEqualPredicate(cast<SCEVEqualPredicate>(Pred), IP);
2213 case SCEVPredicate::P_Wrap: {
2214 auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
2215 return expandWrapPredicate(AddRecPred, IP);
2218 llvm_unreachable("Unknown SCEV predicate type");
2221 Value *SCEVExpander::expandEqualPredicate(const SCEVEqualPredicate *Pred,
2222 Instruction *IP) {
2223 Value *Expr0 = expandCodeFor(Pred->getLHS(), Pred->getLHS()->getType(), IP);
2224 Value *Expr1 = expandCodeFor(Pred->getRHS(), Pred->getRHS()->getType(), IP);
2226 Builder.SetInsertPoint(IP);
2227 auto *I = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
2228 return I;
2231 Value *SCEVExpander::generateOverflowCheck(const SCEVAddRecExpr *AR,
2232 Instruction *Loc, bool Signed) {
2233 assert(AR->isAffine() && "Cannot generate RT check for "
2234 "non-affine expression");
2236 SCEVUnionPredicate Pred;
2237 const SCEV *ExitCount =
2238 SE.getPredicatedBackedgeTakenCount(AR->getLoop(), Pred);
2240 assert(ExitCount != SE.getCouldNotCompute() && "Invalid loop count");
2242 const SCEV *Step = AR->getStepRecurrence(SE);
2243 const SCEV *Start = AR->getStart();
2245 Type *ARTy = AR->getType();
2246 unsigned SrcBits = SE.getTypeSizeInBits(ExitCount->getType());
2247 unsigned DstBits = SE.getTypeSizeInBits(ARTy);
2249 // The expression {Start,+,Step} has nusw/nssw if
2250 // Step < 0, Start - |Step| * Backedge <= Start
2251 // Step >= 0, Start + |Step| * Backedge > Start
2252 // and |Step| * Backedge doesn't unsigned overflow.
2254 IntegerType *CountTy = IntegerType::get(Loc->getContext(), SrcBits);
2255 Builder.SetInsertPoint(Loc);
2256 Value *TripCountVal = expandCodeFor(ExitCount, CountTy, Loc);
2258 IntegerType *Ty =
2259 IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy));
2260 Type *ARExpandTy = DL.isNonIntegralPointerType(ARTy) ? ARTy : Ty;
2262 Value *StepValue = expandCodeFor(Step, Ty, Loc);
2263 Value *NegStepValue = expandCodeFor(SE.getNegativeSCEV(Step), Ty, Loc);
2264 Value *StartValue = expandCodeFor(Start, ARExpandTy, Loc);
2266 ConstantInt *Zero =
2267 ConstantInt::get(Loc->getContext(), APInt::getNullValue(DstBits));
2269 Builder.SetInsertPoint(Loc);
2270 // Compute |Step|
2271 Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero);
2272 Value *AbsStep = Builder.CreateSelect(StepCompare, NegStepValue, StepValue);
2274 // Get the backedge taken count and truncate or extended to the AR type.
2275 Value *TruncTripCount = Builder.CreateZExtOrTrunc(TripCountVal, Ty);
2276 auto *MulF = Intrinsic::getDeclaration(Loc->getModule(),
2277 Intrinsic::umul_with_overflow, Ty);
2279 // Compute |Step| * Backedge
2280 CallInst *Mul = Builder.CreateCall(MulF, {AbsStep, TruncTripCount}, "mul");
2281 Value *MulV = Builder.CreateExtractValue(Mul, 0, "mul.result");
2282 Value *OfMul = Builder.CreateExtractValue(Mul, 1, "mul.overflow");
2284 // Compute:
2285 // Start + |Step| * Backedge < Start
2286 // Start - |Step| * Backedge > Start
2287 Value *Add = nullptr, *Sub = nullptr;
2288 if (PointerType *ARPtrTy = dyn_cast<PointerType>(ARExpandTy)) {
2289 const SCEV *MulS = SE.getSCEV(MulV);
2290 const SCEV *NegMulS = SE.getNegativeSCEV(MulS);
2291 Add = Builder.CreateBitCast(expandAddToGEP(MulS, ARPtrTy, Ty, StartValue),
2292 ARPtrTy);
2293 Sub = Builder.CreateBitCast(
2294 expandAddToGEP(NegMulS, ARPtrTy, Ty, StartValue), ARPtrTy);
2295 } else {
2296 Add = Builder.CreateAdd(StartValue, MulV);
2297 Sub = Builder.CreateSub(StartValue, MulV);
2300 Value *EndCompareGT = Builder.CreateICmp(
2301 Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT, Sub, StartValue);
2303 Value *EndCompareLT = Builder.CreateICmp(
2304 Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, Add, StartValue);
2306 // Select the answer based on the sign of Step.
2307 Value *EndCheck =
2308 Builder.CreateSelect(StepCompare, EndCompareGT, EndCompareLT);
2310 // If the backedge taken count type is larger than the AR type,
2311 // check that we don't drop any bits by truncating it. If we are
2312 // dropping bits, then we have overflow (unless the step is zero).
2313 if (SE.getTypeSizeInBits(CountTy) > SE.getTypeSizeInBits(Ty)) {
2314 auto MaxVal = APInt::getMaxValue(DstBits).zext(SrcBits);
2315 auto *BackedgeCheck =
2316 Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal,
2317 ConstantInt::get(Loc->getContext(), MaxVal));
2318 BackedgeCheck = Builder.CreateAnd(
2319 BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero));
2321 EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck);
2324 EndCheck = Builder.CreateOr(EndCheck, OfMul);
2325 return EndCheck;
2328 Value *SCEVExpander::expandWrapPredicate(const SCEVWrapPredicate *Pred,
2329 Instruction *IP) {
2330 const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr());
2331 Value *NSSWCheck = nullptr, *NUSWCheck = nullptr;
2333 // Add a check for NUSW
2334 if (Pred->getFlags() & SCEVWrapPredicate::IncrementNUSW)
2335 NUSWCheck = generateOverflowCheck(A, IP, false);
2337 // Add a check for NSSW
2338 if (Pred->getFlags() & SCEVWrapPredicate::IncrementNSSW)
2339 NSSWCheck = generateOverflowCheck(A, IP, true);
2341 if (NUSWCheck && NSSWCheck)
2342 return Builder.CreateOr(NUSWCheck, NSSWCheck);
2344 if (NUSWCheck)
2345 return NUSWCheck;
2347 if (NSSWCheck)
2348 return NSSWCheck;
2350 return ConstantInt::getFalse(IP->getContext());
2353 Value *SCEVExpander::expandUnionPredicate(const SCEVUnionPredicate *Union,
2354 Instruction *IP) {
2355 auto *BoolType = IntegerType::get(IP->getContext(), 1);
2356 Value *Check = ConstantInt::getNullValue(BoolType);
2358 // Loop over all checks in this set.
2359 for (auto Pred : Union->getPredicates()) {
2360 auto *NextCheck = expandCodeForPredicate(Pred, IP);
2361 Builder.SetInsertPoint(IP);
2362 Check = Builder.CreateOr(Check, NextCheck);
2365 return Check;
2368 namespace {
2369 // Search for a SCEV subexpression that is not safe to expand. Any expression
2370 // that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely
2371 // UDiv expressions. We don't know if the UDiv is derived from an IR divide
2372 // instruction, but the important thing is that we prove the denominator is
2373 // nonzero before expansion.
2375 // IVUsers already checks that IV-derived expressions are safe. So this check is
2376 // only needed when the expression includes some subexpression that is not IV
2377 // derived.
2379 // Currently, we only allow division by a nonzero constant here. If this is
2380 // inadequate, we could easily allow division by SCEVUnknown by using
2381 // ValueTracking to check isKnownNonZero().
2383 // We cannot generally expand recurrences unless the step dominates the loop
2384 // header. The expander handles the special case of affine recurrences by
2385 // scaling the recurrence outside the loop, but this technique isn't generally
2386 // applicable. Expanding a nested recurrence outside a loop requires computing
2387 // binomial coefficients. This could be done, but the recurrence has to be in a
2388 // perfectly reduced form, which can't be guaranteed.
2389 struct SCEVFindUnsafe {
2390 ScalarEvolution &SE;
2391 bool IsUnsafe;
2393 SCEVFindUnsafe(ScalarEvolution &se): SE(se), IsUnsafe(false) {}
2395 bool follow(const SCEV *S) {
2396 if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
2397 const SCEVConstant *SC = dyn_cast<SCEVConstant>(D->getRHS());
2398 if (!SC || SC->getValue()->isZero()) {
2399 IsUnsafe = true;
2400 return false;
2403 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
2404 const SCEV *Step = AR->getStepRecurrence(SE);
2405 if (!AR->isAffine() && !SE.dominates(Step, AR->getLoop()->getHeader())) {
2406 IsUnsafe = true;
2407 return false;
2410 return true;
2412 bool isDone() const { return IsUnsafe; }
2416 namespace llvm {
2417 bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) {
2418 SCEVFindUnsafe Search(SE);
2419 visitAll(S, Search);
2420 return !Search.IsUnsafe;
2423 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
2424 ScalarEvolution &SE) {
2425 if (!isSafeToExpand(S, SE))
2426 return false;
2427 // We have to prove that the expanded site of S dominates InsertionPoint.
2428 // This is easy when not in the same block, but hard when S is an instruction
2429 // to be expanded somewhere inside the same block as our insertion point.
2430 // What we really need here is something analogous to an OrderedBasicBlock,
2431 // but for the moment, we paper over the problem by handling two common and
2432 // cheap to check cases.
2433 if (SE.properlyDominates(S, InsertionPoint->getParent()))
2434 return true;
2435 if (SE.dominates(S, InsertionPoint->getParent())) {
2436 if (InsertionPoint->getParent()->getTerminator() == InsertionPoint)
2437 return true;
2438 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
2439 for (const Value *V : InsertionPoint->operand_values())
2440 if (V == U->getValue())
2441 return true;
2443 return false;