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