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