LLVM 24.0.0git
ScalarEvolutionExpander.cpp
Go to the documentation of this file.
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
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/ScopeExit.h"
23#include "llvm/IR/DataLayout.h"
24#include "llvm/IR/Dominators.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
42 "scev-cheap-expansion-budget", cl::Hidden, cl::init(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
50 NUW = false;
51 NSW = false;
52 Exact = false;
53 Disjoint = false;
54 NNeg = false;
55 SameSign = false;
57 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(I)) {
58 NUW = OBO->hasNoUnsignedWrap();
59 NSW = OBO->hasNoSignedWrap();
60 }
61 if (auto *PEO = dyn_cast<PossiblyExactOperator>(I))
62 Exact = PEO->isExact();
63 if (auto *PDI = dyn_cast<PossiblyDisjointInst>(I))
64 Disjoint = PDI->isDisjoint();
65 if (auto *PNI = dyn_cast<PossiblyNonNegInst>(I))
66 NNeg = PNI->hasNonNeg();
67 if (auto *TI = dyn_cast<TruncInst>(I)) {
68 NUW = TI->hasNoUnsignedWrap();
69 NSW = TI->hasNoSignedWrap();
70 }
72 GEPNW = GEP->getNoWrapFlags();
73 if (auto *ICmp = dyn_cast<ICmpInst>(I))
74 SameSign = ICmp->hasSameSign();
75}
76
79 I->setHasNoUnsignedWrap(NUW);
80 I->setHasNoSignedWrap(NSW);
81 }
83 I->setIsExact(Exact);
84 if (auto *PDI = dyn_cast<PossiblyDisjointInst>(I))
85 PDI->setIsDisjoint(Disjoint);
86 if (auto *PNI = dyn_cast<PossiblyNonNegInst>(I))
87 PNI->setNonNeg(NNeg);
88 if (isa<TruncInst>(I)) {
89 I->setHasNoUnsignedWrap(NUW);
90 I->setHasNoSignedWrap(NSW);
91 }
93 GEP->setNoWrapFlags(GEPNW);
94 if (auto *ICmp = dyn_cast<ICmpInst>(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,
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>(V)) {
118 // Check to see if there is already a cast!
119 for (User *U : V->users()) {
120 if (U->getType() != Ty)
121 continue;
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(&*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, Ty, 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
155 Instruction *MustDominate) const {
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(&*IP) && &*IP != MustDominate)
169 ++IP;
170
171 return IP;
172}
173
175 SmallVector<Value *> WorkList;
176 SmallPtrSet<Value *, 8> DeletedValues;
178 while (!WorkList.empty()) {
179 Value *V = WorkList.pop_back_val();
180 if (DeletedValues.contains(V))
181 continue;
182 auto *I = dyn_cast<Instruction>(V);
183 if (!I || I == Root || !isInsertedInstruction(I) ||
185 continue;
186 append_range(WorkList, I->operands());
187 InsertedValues.erase(I);
188 InsertedPostIncValues.erase(I);
189 DeletedValues.insert(I);
190 I->eraseFromParent();
191 }
192}
193
195SCEVExpander::GetOptimalInsertionPointForCastOf(Value *V) const {
196 // Cast the instruction immediately after the instruction.
198 return findInsertPointAfter(I, &*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.
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) {
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>(Ty);
229 if (DL.isNonIntegralPointerType(PtrTy))
230 return Builder.CreatePtrAdd(Constant::getNullValue(PtrTy), V, "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>(V)) {
237 if (CI->getOperand(0)->getType() == Ty)
238 return CI->getOperand(0);
239 }
240 }
241 // Short-circuit unnecessary inttoptr<->ptrtoint casts.
242 if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) &&
243 SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) {
244 if (CastInst *CI = dyn_cast<CastInst>(V))
245 if ((CI->getOpcode() == Instruction::PtrToInt ||
246 CI->getOpcode() == Instruction::IntToPtr) &&
247 SE.getTypeSizeInBits(CI->getType()) ==
248 SE.getTypeSizeInBits(CI->getOperand(0)->getType()))
249 return CI->getOperand(0);
250 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
251 if ((CE->getOpcode() == Instruction::PtrToInt ||
252 CE->getOpcode() == Instruction::IntToPtr) &&
253 SE.getTypeSizeInBits(CE->getType()) ==
254 SE.getTypeSizeInBits(CE->getOperand(0)->getType()))
255 return CE->getOperand(0);
256 }
257
258 // Fold a cast of a constant.
259 if (Constant *C = dyn_cast<Constant>(V))
260 return ConstantExpr::getCast(Op, C, Ty);
261
262 // Try to reuse existing cast, or insert one.
263 return ReuseOrCreateCast(V, Ty, Op, 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>(LHS))
274 if (Constant *CRHS = dyn_cast<Constant>(RHS))
275 if (Constant *Res = ConstantFoldBinaryOpOperands(Opcode, CLHS, 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.
289 if (I->hasNoSignedWrap() != any(Flags & SCEV::FlagNSW))
290 return true;
291 if (I->hasNoUnsignedWrap() != any(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>(I) && I->isExact())
297 return true;
298 return false;
299 };
300 if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS &&
301 IP->getOperand(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(Builder.GetInsertBlock())) {
314 if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(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(Flags & SCEV::FlagNUW);
326 bool IsNSW = any(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(PostIncLoops, [&](const Loop *L) {
331 return !L->contains(Builder.GetInsertBlock());
332 })) {
333 auto *BO = BinaryOperator::Create(Opcode, LHS, RHS);
334 if (IsNUW)
335 BO->setHasNoUnsignedWrap();
336 if (IsNSW)
337 BO->setHasNoSignedWrap();
338 return Builder.Insert(BO);
339 }
340 return Builder.CreateNoWrapBinOp(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) {
372 SE.DT.dominates(cast<Instruction>(V), &*Builder.GetInsertPoint()));
373
374 Value *Idx = expand(Offset);
375 GEPNoWrapFlags NW = any(Flags & SCEV::FlagNUW)
377 : GEPNoWrapFlags::none();
378
379 // Fold a GEP with constant operands.
380 if (Constant *CLHS = dyn_cast<Constant>(V))
381 if (Constant *CRHS = dyn_cast<Constant>(Idx))
382 return Builder.CreatePtrAdd(CLHS, CRHS, "", 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>(IP)) {
393 if (GEP->getPointerOperand() == V &&
394 GEP->getSourceElementType() == Builder.getInt8Ty() &&
395 GEP->getOperand(1) == Idx) {
396 rememberFlags(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(Builder.GetInsertBlock())) {
410 if (!L->isLoopInvariant(V) || !L->isLoopInvariant(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(V, Idx, "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(B)) return B;
430 if (B->contains(A)) return A;
431 if (DT.dominates(A->getHeader(), B->getHeader())) return B;
432 if (DT.dominates(B->getHeader(), 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(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:
461 const Loop *L = nullptr;
462 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
463 L = AR->getLoop();
464 for (const SCEV *Op : S->operands())
465 L = PickMostRelevantLoop(L, getRelevantLoop(Op), SE.DT);
466 return RelevantLoops[S] = L;
467 }
468 case scUnknown: {
469 const SCEVUnknown *U = cast<SCEVUnknown>(S);
470 if (const Instruction *I = dyn_cast<Instruction>(U->getValue()))
471 return Pair.first->second = SE.LI.getLoopFor(I->getParent());
472 // A non-instruction has no relevant loops.
473 return nullptr;
474 }
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(LHS.first, 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(S, m_scev_URem(m_SCEV(URemLHS), m_SCEV(URemRHS), SE))) {
521 Value *LHS = expand(URemLHS);
522 Value *RHS = expandDivisor(URemRHS);
523 return InsertBinop(Instruction::URem, LHS, RHS, 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;
531 m_scev_UMax(m_SCEVConstant(C2), m_SCEV(UMaxRHS)))) &&
532 C1->getAPInt() == -C2->getAPInt()) {
533 Value *LHS = expand(UMaxRHS);
534 Value *RHS = C2->getValue();
535 return Builder.CreateIntrinsic(Intrinsic::usub_sat, {S->getType()},
536 {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.
544 for (SCEVUse Op : reverse(S->operands()))
545 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(Op), 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(OpsAndLoops, 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(Op);
560 ++I;
561 continue;
562 }
563
564 assert(!Op->getType()->isPointerTy() && "Only first op can be pointer");
565 if (isa<PointerType>(Sum->getType())) {
566 // The running sum expression is a pointer. Try to form a getelementptr
567 // at this level with that as the base.
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>(X))
574 if (!isa<Instruction>(U->getValue()))
575 X = SE.getSCEV(U->getValue());
576 NewOps.push_back(X);
577 }
578 Sum = expandAddToGEP(SE.getAddExpr(NewOps), Sum, S.getNoWrapFlags());
579 } else if (Op->isNonConstantNegative()) {
580 // Instead of doing a negate and add, just do a subtract.
581 Value *W = expand(SE.getNegativeSCEV(Op));
582 Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagNone,
583 /*IsSafeToHoist*/ true);
584 ++I;
585 } else {
586 // A simple add.
587 Value *W = expand(Op);
588 // Canonicalize a constant to the RHS.
589 if (isa<Constant>(Sum))
590 std::swap(Sum, W);
591 Sum = InsertBinop(Instruction::Add, Sum, W, 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)
608 m_scev_UDiv(m_SCEV(Val), m_SCEVConstant(C2)))) &&
609 C1 == C2 && C1->getAPInt().isPowerOf2()) {
610 Value *LHS = expand(Val);
611 unsigned ShAmtC = C1->getAPInt().logBase2();
612 unsigned BitWidth = Ty->getScalarSizeInBits();
613 APInt Mask(APInt::getBitsSetFrom(BitWidth, ShAmtC));
614 Value *Res = InsertBinop(Instruction::And, LHS, ConstantInt::get(Ty, Mask),
615 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.
622 for (const SCEV *Op : reverse(S->operands()))
623 OpsAndLoops.push_back(std::make_pair(getRelevantLoop(Op), Op));
624
625 // Sort by loop. Use a stable sort so that constants follow non-constants.
626 llvm::stable_sort(OpsAndLoops, 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(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(Instruction::Mul, P, P, SCEV::FlagNone,
660 /*IsSafeToHoist*/ true);
661 if (Exponent & BinExp)
662 Result = Result
663 ? InsertBinop(Instruction::Mul, Result, P, 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(Instruction::Sub, Constant::getNullValue(Ty), Prod,
680 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>(Prod)) std::swap(Prod, W);
687 const APInt *RHS;
688 if (match(W, m_Power2(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(NWFlags, SCEV::FlagNSW);
695 Prod = InsertBinop(Instruction::Shl, Prod,
696 ConstantInt::get(Ty, RHS->logBase2()), NWFlags,
697 /*IsSafeToHoist*/ true);
698 } else {
699 Prod = InsertBinop(Instruction::Mul, Prod, W, 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->getLHS());
710 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
711 const APInt &RHS = SC->getAPInt();
712 if (RHS.isPowerOf2())
713 return InsertBinop(Instruction::LShr, LHS,
714 ConstantInt::get(SC->getType(), RHS.logBase2()),
715 SCEV::FlagNone, /*IsSafeToHoist*/ true);
716 }
717
718 Value *RHS = expandDivisor(S->getRHS());
719 return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagNone,
720 /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS()));
721}
722
723Value *SCEVExpander::expandDivisor(const SCEV *Divisor) {
724 Value *V = expand(Divisor);
725 if (!SafeDivisorMode)
726 return V;
727
728 bool GuaranteedNotPoison =
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(Divisor) || !GuaranteedNotPoison)
737 V = Builder.CreateIntrinsic(V->getType(), Intrinsic::umax,
738 {V, ConstantInt::get(V->getType(), 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>(IncV) ||
747 (isa<CastInst>(IncV) && !isa<BitCastInst>(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(IncV->operands()))
754 if (Instruction *OInst = dyn_cast<Instruction>(Op))
755 if (!SE.DT.dominates(OInst, IVIncInsertPos))
756 return false;
757 }
758 // Advance to the next instruction.
759 IncV = dyn_cast<Instruction>(IncV->getOperand(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.
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: {
794 if (!OInst || SE.DT.dominates(OInst, InsertPos))
795 return dyn_cast<Instruction>(IncV->getOperand(0));
796 return nullptr;
797 }
798 case Instruction::BitCast:
799 return dyn_cast<Instruction>(IncV->getOperand(0));
800 case Instruction::GetElementPtr:
801 for (Use &U : llvm::drop_begin(IncV->operands())) {
802 if (isa<Constant>(U))
803 continue;
804 if (Instruction *OInst = dyn_cast<Instruction>(U)) {
805 if (!SE.DT.dominates(OInst, 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>(IncV)->getSourceElementType()->isIntegerTy(8))
814 return nullptr;
815 break;
816 }
817 return dyn_cast<Instruction>(IncV->getOperand(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) {
830 BasicBlock::iterator NewInsertPt = std::next(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.
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>(I))
849 if (auto Flags = SE.getStrengthenedNoWrapFlagsFromBinOp(OBO)) {
850 auto *BO = cast<BinaryOperator>(I);
851 BO->setHasNoUnsignedWrap(
853 BO->setHasNoSignedWrap(
855 }
856 };
857
858 if (SE.DT.dominates(IncV, 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>(InsertPos) ||
867 !SE.DT.dominates(InsertPos->getParent(), IncV->getParent()))
868 return false;
869
870 if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos))
871 return false;
872
873 // Check that the chain of IV operands leading back to Phi can be hoisted.
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(IncV);
881 IncV = Oper;
882 if (SE.DT.dominates(IncV, InsertPos))
883 break;
884 }
885 for (Instruction *I : llvm::reverse(IVIncs)) {
886 fixupInsertPoints(I);
887 I->moveBefore(InsertPos->getIterator());
888 if (RecomputePoisonFlags)
889 FixupPoisonFlags(I);
890 }
891 return true;
892}
893
895 PHINode *WidePhi,
896 Instruction *OrigInc,
897 Instruction *WideInc) {
898 return match(OrigInc, m_c_BinOp(m_Specific(OrigPhi), m_Value())) &&
899 match(WideInc, m_c_BinOp(m_Specific(WidePhi), 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(IVOper, 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(PN, StepV, "scevgep");
929 } else {
930 IncV = useSubtract ?
931 Builder.CreateSub(PN, StepV, Twine(IVName) + ".iv.next") :
932 Builder.CreateAdd(PN, StepV, 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.
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>(SE.getTruncateOrNoop(Phi, 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(Requested->getStart(), 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(LatchBlock, IVIncInsertLoop->getHeader());
995
996 for (PHINode &PN : L->getHeader()->phis()) {
997 if (!SE.isSCEVable(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()) {
1004 DebugType, dbgs() << "One incomplete PHI is found: " << PN << "\n");
1005 continue;
1006 }
1007
1008 const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(&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 =
1022 if (!TempIncV)
1023 continue;
1024
1025 // Check whether we can reuse this PHI node.
1026 if (LSRMode) {
1027 if (!isExpandedAddRecExprPHI(&PN, TempIncV, L))
1028 continue;
1029 } else {
1030 if (!isNormalAddRecExprPHI(&PN, 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, PhiSCEV, 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(AddRecPhiMatch);
1059 // Remember the increment.
1060 rememberInstruction(IncV);
1061 // Those values were not actually inserted but re-used.
1062 ReusedValues.insert(AddRecPhiMatch);
1063 ReusedValues.insert(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(Normalized->getStart(), 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(Step);
1103 // Expand the step somewhere that dominates the loop header.
1104 Value *StepV = expand(Step, 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(Instruction::Add, /*Signed=*/false, Normalized, Step);
1112 bool IncrementIsNSW =
1113 CanHaveNoWrap &&
1114 SE.willNotOverflow(Instruction::Add, /*Signed=*/true, Normalized, Step);
1115
1116 // Create the PHI.
1117 BasicBlock *Header = L->getHeader();
1118 Builder.SetInsertPoint(Header->begin());
1119 PHINode *PN =
1120 Builder.CreatePHI(ExpandTy, pred_size(Header), Twine(IVName) + ".iv");
1121
1122 // Create the step instructions and populate the PHI.
1123 for (BasicBlock *Pred : predecessors(Header)) {
1124 // Add a start value.
1125 if (!L->contains(Pred)) {
1126 PN->addIncoming(StartV, 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
1139 if (IncrementIsNUW)
1140 cast<BinaryOperator>(IncV)->setHasNoUnsignedWrap();
1141 if (IncrementIsNSW)
1142 cast<BinaryOperator>(IncV)->setHasNoSignedWrap();
1143 }
1144 PN->addIncoming(IncV, 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(PN);
1154 InsertedIVs.push_back(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(L)) {
1167 Loops.insert(L);
1168 Normalized = cast<SCEVAddRecExpr>(
1169 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(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(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>(Result)) {
1198 auto *I = cast<Instruction>(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>(Result) &&
1209 !SE.DT.dominates(cast<Instruction>(Result),
1210 &*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(Step);
1224 Value *StepV;
1225 {
1226 // Expand the step somewhere that dominates the loop header.
1227 SCEVInsertPointGuard Guard(Builder, this);
1228 StepV = expand(Step, 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(Result);
1239 // Truncate the result.
1240 if (TruncTy != Result->getType())
1241 Result = Builder.CreateTrunc(Result, TruncTy);
1242
1243 // Invert the result.
1244 if (InvertStep)
1245 Result = Builder.CreateSub(expand(Normalized->getStart()), Result);
1246 }
1247
1248 return Result;
1249}
1250
1251std::pair<PHINode *, const SCEV *>
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(EB, 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>(ExitSCEV))
1265 return nullptr;
1266 const SCEV *Diff = SE.getMinusSCEV(S, ExitSCEV);
1267 const SCEV *Op = Diff;
1272 return nullptr;
1273 return Diff;
1274 };
1275
1276 for (auto &PN : EB->phis()) {
1277 if (!SE.isSCEVable(PN.getType()))
1278 continue;
1279 auto *ExitSCEV = SE.getSCEV(&PN);
1280 if (!isa<SCEVAddRecExpr>(ExitSCEV))
1281 continue;
1282 Type *PhiTy = PN.getType();
1283 const SCEV *Diff = nullptr;
1284 if (STy->isIntegerTy() && PhiTy->isPointerTy() &&
1285 SE.getDataLayout().getAddressType(PhiTy) == STy) {
1286 const SCEV *AddrSCEV = SE.getPtrToAddrExpr(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, Builder.GetInsertBlock());
1304 if (!PN)
1305 return nullptr;
1306 Value *DiffV = expand(Diff);
1307 Value *BaseV = fixupLCSSAFormFor(PN);
1308 if (PN->getType()->isPointerTy()) {
1309 if (S->getType()->isPointerTy())
1310 return Builder.CreatePtrAdd(BaseV, DiffV);
1311 BaseV = Builder.CreatePtrToAddr(BaseV);
1312 }
1313 return Builder.CreateAdd(BaseV, 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(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(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(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(S->getOperand(i), CanonicalIV->getType());
1346 Value *V = expand(
1347 SE.getAddRecExpr(NewOps, S->getLoop(), S.getNoWrapFlags(SCEV::FlagNW)));
1348 BasicBlock::iterator NewInsertPt =
1350 &*Builder.GetInsertPoint())
1351 : Builder.GetInsertPoint();
1352 V = expand(SE.getTruncateExpr(SE.getUnknown(V), Ty), 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>(S->getType())) {
1363 Value *StartV = expand(SE.getPointerBase(S));
1364 return expandAddToGEP(SE.removePointerBase(S), StartV,
1366 }
1367
1368 // {X,+,F} --> X + {0,+,F}
1369 if (!S->getStart()->isZero()) {
1370 const SCEV *Rest = SE.getAddRecExpr(SE.getZero(Ty), S->getOperand(1), L,
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(expand(S->getStart()));
1378 const SCEV *AddExprRHS = SE.getUnknown(expand(Rest));
1379 return expand(SE.getAddExpr(AddExprLHS, 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(Header), HPE = pred_end(Header);
1388 CanonicalIV = PHINode::Create(Ty, std::distance(HPB, HPE), "indvar");
1389 CanonicalIV->insertBefore(Header->begin());
1390 rememberInstruction(CanonicalIV);
1391
1392 SmallPtrSet<BasicBlock *, 4> PredSeen;
1393 Constant *One = ConstantInt::get(Ty, 1);
1394 for (pred_iterator HPI = HPB; HPI != HPE; ++HPI) {
1395 BasicBlock *HP = *HPI;
1396 if (!PredSeen.insert(HP).second) {
1397 // There must be an incoming value for each predecessor, even the
1398 // duplicates!
1399 CanonicalIV->addIncoming(CanonicalIV->getIncomingValueForBlock(HP), HP);
1400 continue;
1401 }
1402
1403 if (L->contains(HP)) {
1404 // Insert a unit add instruction right before the terminator
1405 // corresponding to the back-edge.
1406 Instruction *Add = BinaryOperator::CreateAdd(CanonicalIV, One,
1407 "indvar.next",
1408 HP->getTerminator()->getIterator());
1409 Add->setDebugLoc(HP->getTerminator()->getDebugLoc());
1410 rememberInstruction(Add);
1411 CanonicalIV->addIncoming(Add, HP);
1412 } else {
1413 CanonicalIV->addIncoming(Constant::getNullValue(Ty), HP);
1414 }
1415 }
1416 }
1417
1418 // {0,+,F} --> {0,+,1} * F
1419 return expand(SE.getMulExpr(SE.getUnknown(CanonicalIV), S->getOperand(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
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>(PtrOp))
1441 return nullptr;
1442 for (User *U : PtrOp->users()) {
1443 auto *CI = dyn_cast<CastInst>(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->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(V, Ty, DL, [&](const CastInst *CI) {
1460 return &*BIP != CI && SE.DT.dominates(CI, &*BIP);
1461 }))
1462 return CI;
1463
1464 return ReuseOrCreateCast(V, Ty, CastInst::PtrToAddr,
1465 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>(S->getOperand())) {
1475 Value *PtrOp = expand(PtrToAddr->getOperand());
1476 if (!isa<Constant>(PtrOp)) {
1477 BasicBlock::iterator BIP = Builder.GetInsertPoint();
1478 for (User *U : PtrOp->users()) {
1479 auto *CI = dyn_cast<CastInst>(U);
1480 if (CI && CI->getType() == Ty &&
1481 CI->getOpcode() == CastInst::PtrToInt && &*BIP != CI &&
1482 SE.DT.dominates(CI, &*BIP))
1483 return CI;
1484 }
1485 }
1486 }
1487
1488 Value *V = expand(S->getOperand());
1489 return Builder.CreateTrunc(V, S->getType());
1490}
1491
1492Value *
1493SCEVExpander::visitZeroExtendExpr(SCEVUseT<const SCEVZeroExtendExpr *> S) {
1494 Value *V = expand(S->getOperand());
1495 return Builder.CreateZExt(V, S->getType(), "",
1496 SE.isKnownNonNegative(S->getOperand()));
1497}
1498
1499Value *
1500SCEVExpander::visitSignExtendExpr(SCEVUseT<const SCEVSignExtendExpr *> S) {
1501 Value *V = expand(S->getOperand());
1502 return Builder.CreateSExt(V, 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->getOperand(S->getNumOperands() - 1));
1511 Type *Ty = LHS->getType();
1512 if (IsSequential)
1513 LHS = Builder.CreateFreeze(LHS);
1514 for (int i = S->getNumOperands() - 2; i >= 0; --i) {
1515 SafeDivisorMode = (IsSequential && i != 0) || PrevSafeMode;
1516 Value *RHS = expand(S->getOperand(i));
1517 if (IsSequential && i != 0)
1518 RHS = Builder.CreateFreeze(RHS);
1519 Value *Sel;
1520 if (Ty->isIntegerTy())
1521 Sel = Builder.CreateIntrinsic(IntrinID, {Ty}, {LHS, RHS},
1522 /*FMFSource=*/nullptr, Name);
1523 else {
1524 Value *ICmp =
1525 Builder.CreateICmp(MinMaxIntrinsic::getPredicate(IntrinID), LHS, RHS);
1526 Sel = Builder.CreateSelectWithUnknownProfile(ICmp, LHS, RHS,
1527 "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, Intrinsic::smax, "smax");
1537}
1538
1539Value *SCEVExpander::visitUMaxExpr(SCEVUseT<const SCEVUMaxExpr *> S) {
1540 return expandMinMaxExpr(S, Intrinsic::umax, "umax");
1541}
1542
1543Value *SCEVExpander::visitSMinExpr(SCEVUseT<const SCEVSMinExpr *> S) {
1544 return expandMinMaxExpr(S, Intrinsic::smin, "smin");
1545}
1546
1547Value *SCEVExpander::visitUMinExpr(SCEVUseT<const SCEVUMinExpr *> S) {
1548 return expandMinMaxExpr(S, Intrinsic::umin, "umin");
1549}
1550
1551Value *SCEVExpander::visitSequentialUMinExpr(
1553 return expandMinMaxExpr(S, Intrinsic::umin, "umin",
1554 /*IsSequential*/ true);
1555}
1556
1557Value *SCEVExpander::visitVScale(SCEVUseT<const SCEVVScale *> S) {
1558 return Builder.CreateVScale(S->getType());
1559}
1560
1563 setInsertPoint(IP);
1564 return expandCodeFor(SH, Ty);
1565}
1566
1568 // Expand the code for this SCEV.
1569 Value *V = expand(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.
1589 return nullptr;
1590
1591 for (Value *V : SE.getSCEVValues(S)) {
1592 Instruction *EntInst = dyn_cast<Instruction>(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(EntInst, InsertPt) ||
1601 !(SE.LI.getLoopFor(EntInst->getParent()) == nullptr ||
1602 SE.LI.getLoopFor(EntInst->getParent())->contains(InsertPt)))
1603 continue;
1604
1605 // Make sure reusing the instruction is poison-safe.
1606 if (SE.canReuseInstruction(S, 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);
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(S, [](const SCEV *S) {
1642 if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) {
1643 if (const auto *SC = dyn_cast<SCEVConstant>(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(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(L))
1673 InsertPt = L->getHeader()->getFirstInsertionPt();
1674
1675 while (InsertPt != Builder.GetInsertPoint() &&
1676 (isInsertedInstruction(&*InsertPt))) {
1677 InsertPt = std::next(InsertPt);
1678 }
1679 break;
1680 }
1681 }
1682 }
1683
1684 // Check to see if we already expanded this here.
1685 auto I = InsertedExpressions.find(std::make_pair(S, &*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);
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, &*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(S, &*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(I, PoisonFlags(I));
1730}
1731
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>(I))
1738 if (SE.isSCEVable(OBO->getType()))
1739 if (auto Flags = SE.getStrengthenedNoWrapFlagsFromBinOp(OBO)) {
1740 auto *BO = cast<BinaryOperator>(I);
1741 BO->setHasNoUnsignedWrap(
1743 BO->setHasNoSignedWrap(
1745 }
1746 if (auto *NNI = dyn_cast<PossiblyNonNegInst>(I)) {
1747 auto *Src = NNI->getOperand(0);
1749 Constant::getNullValue(Src->getType()), I,
1750 SE.getDataLayout())
1751 .value_or(false))
1752 NNI->setNonNeg(true);
1753 }
1754}
1755
1756void SCEVExpander::replaceCongruentIVInc(
1757 PHINode *&Phi, PHINode *&OrigPhi, Loop *L, const DominatorTree *DT,
1759 BasicBlock *LatchBlock = L->getLoopLatch();
1760 if (!LatchBlock)
1761 return;
1762
1763 Instruction *OrigInc =
1764 dyn_cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
1765 Instruction *IsomorphicInc =
1766 dyn_cast<Instruction>(Phi->getIncomingValueForBlock(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(Phi);
1775 if (!(Chained || isExpandedAddRecExprPHI(OrigPhi, OrigInc, L)) &&
1776 (Chained || isExpandedAddRecExprPHI(Phi, IsomorphicInc, L))) {
1777 std::swap(OrigPhi, Phi);
1778 std::swap(OrigInc, 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(SE.getSCEV(OrigInc), IsomorphicInc->getType());
1793 if (OrigInc == IsomorphicInc || TruncExpr != SE.getSCEV(IsomorphicInc) ||
1794 !SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc))
1795 return;
1796
1797 bool BothHaveNUW = false;
1798 bool BothHaveNSW = false;
1799 auto *OBOIncV = dyn_cast<OverflowingBinaryOperator>(OrigInc);
1800 auto *OBOIsomorphic = dyn_cast<OverflowingBinaryOperator>(IsomorphicInc);
1801 if (OBOIncV && OBOIsomorphic) {
1802 BothHaveNUW =
1803 OBOIncV->hasNoUnsignedWrap() && OBOIsomorphic->hasNoUnsignedWrap();
1804 BothHaveNSW =
1805 OBOIncV->hasNoSignedWrap() && OBOIsomorphic->hasNoSignedWrap();
1806 }
1807
1808 if (!hoistIVInc(OrigInc, 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()) {
1830 if (PHINode *PN = dyn_cast<PHINode>(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(OrigInc, IsomorphicInc->getType(), IVName);
1839 }
1840 IsomorphicInc->replaceAllUsesWith(NewInc);
1841 DeadInsts.emplace_back(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
1853 const TargetTransformInfo *TTI) {
1854 // Find integer phis in order of increasing width.
1856 llvm::make_pointer_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(Phis, [](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;
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(PN, {DL, &SE.TLI, &SE.DT, &SE.AC}))
1876 return V;
1877 if (!SE.isSCEVable(PN->getType()))
1878 return nullptr;
1879 auto *Const = dyn_cast<SCEVConstant>(SE.getSCEV(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(Phi);
1891 Phi->replaceAllUsesWith(V);
1892 DeadInsts.emplace_back(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(Phi->getType()))
1901 continue;
1902
1903 PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
1904 if (!OrigPhiRef) {
1905 OrigPhiRef = Phi;
1906 if (Phi->getType()->isIntegerTy() && TTI &&
1907 TTI->isTruncateFree(Phi->getType(), 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(Phi);
1912 if (isa<SCEVAddRecExpr>(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(PhiExpr, 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, OrigPhiRef, L, DT, DeadInsts);
1929 SCEV_DEBUG_WITH_TYPE(DebugType,
1930 dbgs() << "INDVARS: Eliminated congruent iv: " << *Phi
1931 << '\n');
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(OrigPhiRef, Phi->getType(), IVName);
1940 }
1941 Phi->replaceAllUsesWith(NewIV);
1942 DeadInsts.emplace_back(Phi);
1943 }
1944 return NumElim;
1945}
1946
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(BB->getTerminator(),
1961 m_Br(m_ICmp(Pred, m_Instruction(LHS), m_Instruction(RHS)),
1963 continue;
1964
1965 if (SE.getSCEV(LHS) == S && SE.DT.dominates(LHS, At))
1966 return true;
1967
1968 if (SE.getSCEV(RHS) == S && SE.DT.dominates(RHS, 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, At, DropPoisonGeneratingInsts) != nullptr;
1978}
1979
1980template<typename T> static InstructionCost costAndCollectOperands(
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.
2000
2001 auto CastCost = [&](unsigned Opcode) -> InstructionCost {
2002 Operations.emplace_back(Opcode, 0, 0);
2003 return TTI.getCastInstrCost(Opcode, S->getType(),
2004 S->getOperand(0)->getType(),
2005 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, 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, OpType, CmpInst::makeCmpResultType(OpType),
2022 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:
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(Instruction::PHI, CostKind) * NumRecurrences;
2105 Cost +=
2106 TTI.getArithmeticInstrCost(Instruction::Add, 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(Instruction::Add, 1, 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,
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>(S) && !Processed.insert(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, L))
2144 return false; // Consider the expression to be free.
2145
2147 L->getHeader()->getParent()->hasMinSize()
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>(S)->getAPInt();
2163 Type *Ty = S->getType();
2165 WorkItem.ParentOpcode, 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.
2186 SE.getAddExpr(S, SE.getConstant(S->getType(), 1)), &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");
2212 WorkItem, TTI, CostKind, Worklist);
2213 return Cost > Budget;
2214 }
2215 }
2216 llvm_unreachable("Unknown SCEV kind!");
2217}
2218
2220 Instruction *IP) {
2221 assert(IP);
2222 switch (Pred->getKind()) {
2227 case SCEVPredicate::P_Wrap: {
2228 auto *AddRecPred = cast<SCEVWrapPredicate>(Pred);
2229 return expandWrapPredicate(AddRecPred, IP);
2230 }
2231 }
2232 llvm_unreachable("Unknown SCEV predicate type");
2233}
2234
2236 Instruction *IP) {
2237 Value *Expr0 = expand(Pred->getLHS(), IP);
2238 Value *Expr1 = expand(Pred->getRHS(), IP);
2239
2240 Builder.SetInsertPoint(IP);
2241 auto InvPred = ICmpInst::getInversePredicate(Pred->getPredicate());
2242 auto *I = Builder.CreateICmp(InvPred, Expr0, Expr1, "ident.check");
2243 return I;
2244}
2245
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.
2253 const SCEV *ExitCount =
2254 SE.getPredicatedSymbolicMaxBackedgeTakenCount(AR->getLoop(), 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(ExitCount->getType());
2263 unsigned DstBits = SE.getTypeSizeInBits(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(ExitCount, Loc);
2272
2273 IntegerType *Ty =
2274 IntegerType::get(Loc->getContext(), SE.getTypeSizeInBits(ARTy));
2275
2276 Value *StepValue = expand(Step, Loc);
2277 Value *NegStepValue = expand(SE.getNegativeSCEV(Step), Loc);
2278 Value *StartValue = expand(Start, Loc);
2279
2280 ConstantInt *Zero =
2281 ConstantInt::get(Loc->getContext(), APInt::getZero(DstBits));
2282
2283 Builder.SetInsertPoint(Loc);
2284 // Compute |Step|
2285 Value *StepCompare = Builder.CreateICmp(ICmpInst::ICMP_SLT, StepValue, Zero);
2286 Value *AbsStep = Builder.CreateSelectWithUnknownProfile(
2287 StepCompare, NegStepValue, StepValue, "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(TripCountVal, AbsStep, Loc);
2301 auto I = InsertedOverflowChecks.find(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(TripCountVal, Ty);
2308 Value *Mul = Builder.CreateIntrinsic(Intrinsic::umul_with_overflow, Ty,
2309 {AbsStep, TruncTripCount},
2310 /*FMFSource=*/nullptr, "mul");
2311 MulV = Builder.CreateExtractValue(Mul, 0, "mul.result");
2312 OfMul = Builder.CreateExtractValue(Mul, 1, "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(Step);
2320 bool NeedNegCheck = !SE.isKnownPositive(Step);
2321
2322 if (isa<PointerType>(ARTy)) {
2323 Value *NegMulV = Builder.CreateNeg(MulV);
2324 if (NeedPosCheck)
2325 Add = Builder.CreatePtrAdd(StartValue, MulV);
2326 if (NeedNegCheck)
2327 Sub = Builder.CreatePtrAdd(StartValue, NegMulV);
2328 } else {
2329 if (NeedPosCheck)
2330 Add = Builder.CreateAdd(StartValue, MulV);
2331 if (NeedNegCheck)
2332 Sub = Builder.CreateSub(StartValue, MulV);
2333 }
2334
2335 Value *EndCompareLT = nullptr;
2336 Value *EndCompareGT = nullptr;
2337 Value *EndCheck = nullptr;
2338 if (NeedPosCheck)
2339 EndCheck = EndCompareLT = Builder.CreateICmp(
2341 if (NeedNegCheck)
2342 EndCheck = EndCompareGT = Builder.CreateICmp(
2344 if (NeedPosCheck && NeedNegCheck) {
2345 // Select the answer based on the sign of Step.
2346 EndCheck = Builder.CreateSelectWithUnknownProfile(
2347 StepCompare, EndCompareGT, EndCompareLT, "scev-expander");
2348 }
2349 return Builder.CreateOr(EndCheck, 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(DstBits).zext(SrcBits);
2358 auto *BackedgeCheck =
2359 Builder.CreateICmp(ICmpInst::ICMP_UGT, TripCountVal,
2360 ConstantInt::get(Loc->getContext(), MaxVal));
2361 BackedgeCheck = Builder.CreateAnd(
2362 BackedgeCheck, Builder.CreateICmp(ICmpInst::ICMP_NE, StepValue, Zero));
2363
2364 EndCheck = Builder.CreateOr(EndCheck, BackedgeCheck);
2365 }
2366
2367 return EndCheck;
2368}
2369
2371 Instruction *IP) {
2372 const auto *A = cast<SCEVAddRecExpr>(Pred->getExpr());
2373 Value *NSSWCheck = nullptr, *NUSWCheck = nullptr;
2374
2375 // Add a check for NUSW
2376 if (Pred->getFlags() & SCEVWrapPredicate::IncrementNUSW)
2377 NUSWCheck = generateOverflowCheck(A, IP, false);
2378
2379 // Add a check for NSSW
2380 if (Pred->getFlags() & SCEVWrapPredicate::IncrementNSSW)
2381 NSSWCheck = generateOverflowCheck(A, IP, true);
2382
2383 if (NUSWCheck && NSSWCheck)
2384 return Builder.CreateOr(NUSWCheck, NSSWCheck);
2385
2386 if (NUSWCheck)
2387 return NUSWCheck;
2388
2389 if (NSSWCheck)
2390 return NSSWCheck;
2391
2392 return ConstantInt::getFalse(IP->getContext());
2393}
2394
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(expandCodeForPredicate(Pred, IP));
2401 Builder.SetInsertPoint(IP);
2402 }
2403
2404 if (Checks.empty())
2405 return ConstantInt::getFalse(IP->getContext());
2406 return Builder.CreateOr(Checks);
2407}
2408
2409Value *SCEVExpander::fixupLCSSAFormFor(Value *V) {
2410 auto *DefI = dyn_cast<Instruction>(V);
2411 if (!PreserveLCSSA || !DefI)
2412 return V;
2413
2414 BasicBlock::iterator InsertPt = Builder.GetInsertPoint();
2415 Loop *DefLoop = SE.LI.getLoopFor(DefI->getParent());
2416 Loop *UseLoop = SE.LI.getLoopFor(InsertPt->getParent());
2417 if (!DefLoop || UseLoop == DefLoop || DefLoop->contains(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(DefI->getContext(), 0);
2430 else
2431 ToTy = Type::getInt32Ty(DefI->getContext());
2432 Instruction *User =
2433 CastInst::CreateBitOrPointerCast(DefI, ToTy, "tmp.lcssa.user", InsertPt);
2434 llvm::scope_exit RemoveUserOnExit([User]() { User->eraseFromParent(); });
2435
2437 ToUpdate.push_back(DefI);
2438 SmallVector<PHINode *, 16> PHIsToRemove;
2439 SmallVector<PHINode *, 16> InsertedPHIs;
2440 formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, &SE, &PHIsToRemove,
2441 &InsertedPHIs);
2442 for (PHINode *PN : InsertedPHIs)
2443 rememberInstruction(PN);
2444 for (PHINode *PN : PHIsToRemove) {
2445 if (!PN->use_empty())
2446 continue;
2447 InsertedValues.erase(PN);
2448 InsertedPostIncValues.erase(PN);
2449 PN->eraseFromParent();
2450 }
2451
2452 return User->getOperand(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>(S)) {
2484 if (!SE.isKnownNonZero(D->getRHS()) ||
2485 !SE.isGuaranteedNotToBePoison(D->getRHS())) {
2486 IsUnsafe = true;
2487 return false;
2488 }
2489 }
2490 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(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
2506 SCEVFindUnsafe Search(SE, CanonicalMode);
2507 visitAll(S, Search);
2508 return !Search.IsUnsafe;
2509}
2510
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, InsertionPoint->getParent()))
2522 return true;
2523 if (SE.dominates(S, InsertionPoint->getParent())) {
2524 if (InsertionPoint->getParent()->getTerminator() == InsertionPoint)
2525 return true;
2526 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
2527 if (llvm::is_contained(InsertionPoint->operand_values(), U->getValue()))
2528 return true;
2529 }
2530 return false;
2531}
2532
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
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(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(PoisonValue::get(I->getType()));
2564 I->eraseFromParent();
2565 }
2566}
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
uint64_t Imm
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define X(NUM, ENUM, NAME)
Definition ELF.h:665
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static Expected< BitVector > expand(StringRef S, StringRef Original)
Hexagon Common GEP
Hexagon Hardware Loops
#define I(x, y, z)
Definition MD5.cpp:57
#define T
#define P(N)
if(PassOpts->AAPipeline)
This file contains the declarations for profiling metadata utility functions.
int64_t C1
This file contains some templates that are useful if you are working with the STL at all.
static const Loop * PickMostRelevantLoop(const Loop *A, const Loop *B, DominatorTree &DT)
PickMostRelevantLoop - Given two loops pick the one that's most relevant for SCEV expansion.
static InstructionCost costAndCollectOperands(const SCEVOperand &WorkItem, const TargetTransformInfo &TTI, TargetTransformInfo::TargetCostKind CostKind, SmallVectorImpl< SCEVOperand > &Worklist)
static bool canBeCheaplyTransformed(ScalarEvolution &SE, const SCEVAddRecExpr *Phi, const SCEVAddRecExpr *Requested, bool &InvertStep)
Check whether we can cheaply express the requested SCEV in terms of the available PHI SCEV by truncat...
#define SCEV_DEBUG_WITH_TYPE(TYPE, X)
static bool canReuseCastForPtrToAddr(const CastInst *CI, Type *Ty, const DataLayout &DL)
Return true if CI computes the same value as a ptrtoaddr of its pointer operand to Ty.
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
Definition APInt.cpp:1057
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition APInt.h:202
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition APInt.h:196
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Definition APInt.h:282
LLVM Basic Block Representation.
Definition BasicBlock.h:62
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition BasicBlock.h:509
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
InstListType::iterator iterator
Instruction iterators...
Definition BasicBlock.h:170
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Definition BasicBlock.h:237
static LLVM_ABI BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
This is the base class for all instructions that perform data casts.
Definition InstrTypes.h:512
Type * getSrcTy() const
Return the source type, as a convenience.
Definition InstrTypes.h:679
static LLVM_ABI Instruction::CastOps getCastOpcode(const Value *Val, bool SrcIsSigned, Type *Ty, bool DstIsSigned)
Returns the opcode necessary to cast Val into Ty using usual casting rules.
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition InstrTypes.h:674
static LLVM_ABI CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
@ ICMP_SLT
signed less than
Definition InstrTypes.h:769
@ ICMP_UGT
unsigned greater than
Definition InstrTypes.h:763
@ ICMP_SGT
signed greater than
Definition InstrTypes.h:767
@ ICMP_ULT
unsigned less than
Definition InstrTypes.h:765
@ ICMP_NE
not equal
Definition InstrTypes.h:762
@ ICMP_SGE
signed greater or equal
Definition InstrTypes.h:768
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition InstrTypes.h:852
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
This is the shared class of boolean and integer constants.
Definition Constants.h:87
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:122
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
static GEPNoWrapFlags noUnsignedWrap()
static GEPNoWrapFlags none()
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition IRBuilder.h:2990
LLVM_ABI void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
LLVM_ABI void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI void insertBefore(InstListType::iterator InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified position.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
LLVM_ABI bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Class to represent integer types.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition Type.cpp:333
bool contains(const LoopT *L) const
Return true if the specified loop is contained within this loop.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
ICmpInst::Predicate getPredicate() const
Returns the comparison predicate underlying the intrinsic.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
bool isComplete() const
If the PHI node is complete which means all of its parent's predecessors have incoming value in this ...
Value * getIncomingValueForBlock(const BasicBlock *BB) const
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PointerType * get(LLVMContext &C, unsigned AddressSpace)
This constructs an opaque pointer to an object in a numbered address space.
Definition Type.cpp:882
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This node represents a polynomial recurrence on the trip count of the specified loop.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
SCEVUse getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
ConstantInt * getValue() const
const APInt & getAPInt() const
LLVM_ABI Value * generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed)
Generates code that evaluates if the AR expression will overflow.
LLVM_ABI bool hasRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Determine whether there is an existing expansion of S that can be reused.
SmallVector< Instruction *, 32 > getAllInsertedInstructions() const
Return a vector containing all instructions inserted during expansion.
LLVM_ABI bool isSafeToExpand(const SCEV *S) const
Return true if the given expression is safe to expand in the sense that all materialized values are s...
LLVM_ABI bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const
Return true if the given expression is safe to expand in the sense that all materialized values are d...
LLVM_ABI unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
replace congruent phis with their most canonical representative.
static LLVM_ABI void dropPoisonGeneratingAnnotationsAndReinfer(ScalarEvolution &SE, Instruction *I)
Drop poison-generating flags from I, then try re-infer via SCEV.
LLVM_ABI Value * expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
static LLVM_ABI CastInst * findReusableCastForPtrToAddr(Value *PtrOp, Type *Ty, const DataLayout &DL, function_ref< bool(const CastInst *)> Dominates)
Find an existing cast among PtrOp's users that computes the same value as a ptrtoaddr of PtrOp to Ty ...
LLVM_ABI bool hoistIVInc(Instruction *IncV, Instruction *InsertPos, bool RecomputePoisonFlags=false)
Utility for hoisting IncV (with all subexpressions requried for its computation) before InsertPos.
bool isInsertedInstruction(Instruction *I) const
Return true if the specified instruction was inserted by the code rewriter.
LLVM_ABI Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
static LLVM_ABI bool canReuseFlagsFromOriginalIVInc(PHINode *OrigPhi, PHINode *WidePhi, Instruction *OrigInc, Instruction *WideInc)
Return true if both increments directly increment the corresponding IV PHI nodes and have the same op...
LLVM_ABI Value * expandCodeFor(SCEVUse SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
LLVM_ABI Value * expandComparePredicate(const SCEVComparePredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
LLVM_ABI Value * expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
LLVM_ABI Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
LLVM_ABI void eraseDeadInstructions(Value *Root)
Remove inserted instructions that are dead, e.g.
LLVM_ABI BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate) const
Returns a suitable insert point after I, that dominates MustDominate.
static LLVM_ABI std::pair< PHINode *, const SCEV * > findReusableLCSSAPhi(ScalarEvolution &SE, SCEVUseT< const SCEVAddRecExpr * > S, const BasicBlock *InsertBB)
Find a phi in the exit block of S's loop, which must dominate InsertBB, such that S can be expanded i...
void setInsertPoint(Instruction *IP)
Set the current insertion point.
This class represents an assumption made using SCEV expressions which can be checked at run-time.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an assumption made on an AddRec expression.
This class represents an analyzed expression in the program.
static constexpr auto FlagNUW
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
static constexpr auto FlagNSW
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
Type * getType() const
Return the LLVM type of this SCEV expression.
static constexpr auto FlagNone
SCEVTypes getSCEVType() const
static constexpr auto FlagNW
The main scalar evolution driver.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
static LLVM_ABI bool isGuaranteedNotToBePoison(const SCEV *Op)
Returns true if Op is guaranteed to not be poison.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
static SCEVFlags clearFlags(SCEVFlags Flags, SCEVFlags OffFlags)
static SCEVFlags maskFlags(SCEVFlags Flags, SCEVFlags Mask)
Convenient SCEVFlags manipulation.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM_ABI InstructionCost getIntImmCostInst(unsigned Opc, unsigned Idx, const APInt &Imm, Type *Ty, TargetCostKind CostKind, Instruction *Inst=nullptr) const
Return the expected cost of materialization for the given integer immediate of the specified type for...
TargetCostKind
The kind of cost model.
@ TCK_RecipThroughput
Reciprocal throughput.
@ TCK_CodeSize
Instruction code size.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition Twine.h:82
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
LLVM_ABI unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
Definition Type.h:283
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
Definition Type.cpp:294
bool isPointerTy() const
True if this is an instance of PointerType.
Definition Type.h:277
LLVM_ABI unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition Type.h:354
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition Type.h:252
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
op_range operands()
Definition User.h:267
Value * getOperand(unsigned i) const
Definition User.h:207
unsigned getNumOperands() const
Definition User.h:229
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:548
LLVMContext & getContext() const
All values hold a context through their type.
Definition Value.h:260
iterator_range< user_iterator > users()
Definition Value.h:428
bool use_empty() const
Definition Value.h:348
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
Definition ilist_node.h:34
self_iterator getIterator()
Definition ilist_node.h:123
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition ilist_node.h:348
#define UINT64_MAX
Definition DataTypes.h:77
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr bool any(E Val)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
bool match(Val *V, const Pattern &P)
match_bind< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_BasicBlock()
Match an arbitrary basic block value and ignore it.
auto m_Value()
Match an arbitrary value and ignore it.
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
brc_match< Cond_t, match_bind< BasicBlock >, match_bind< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
cst_pred_ty< is_all_ones > m_scev_AllOnes()
Match an integer with all bits set.
SCEVUnaryExpr_match< SCEVPtrToAddrExpr, Op0_t > m_scev_PtrToAddr(const Op0_t &Op0)
match_bind< const SCEVMulExpr > m_scev_Mul(const SCEVMulExpr *&V)
SCEVBinaryExpr_match< SCEVUDivExpr, Op0_t, Op1_t > m_scev_UDiv(const Op0_t &Op0, const Op1_t &Op1)
SCEVBinaryExpr_match< SCEVUMaxExpr, Op0_t, Op1_t, SCEV::FlagNone, true > m_scev_UMax(const Op0_t &Op0, const Op1_t &Op1)
match_bind< const SCEVAddExpr > m_scev_Add(const SCEVAddExpr *&V)
SCEVURem_match< Op0_t, Op1_t > m_scev_URem(Op0_t LHS, Op1_t RHS, ScalarEvolution &SE)
Match the mathematical pattern A - (A / B) * B, where A and B can be arbitrary expressions.
@ CE
Windows NT (Windows on ARM)
Definition MCAsmInfo.h:51
initializer< Ty > init(const Ty &Val)
@ User
could "use" a pointer
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition STLExtras.h:316
@ Offset
Definition DWP.cpp:577
void stable_sort(R &&Range)
Definition STLExtras.h:2132
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1755
InstructionCost Cost
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
Definition STLExtras.h:2570
auto pred_end(const MachineBasicBlock *BB)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
constexpr from_range_t from_range
constexpr NextUseDistance min(NextUseDistance A, NextUseDistance B)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2224
auto pred_size(const MachineBasicBlock *BB)
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition Local.cpp:408
auto reverse(ContainerTy &&C)
Definition STLExtras.h:408
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI cl::opt< unsigned > SCEVCheapExpansionBudget
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
LLVM_ABI const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE, bool CheckInvertible=true)
Normalize S to be post-increment for all loops present in Loops.
TargetTransformInfo TTI
constexpr NextUseDistance max(NextUseDistance A, NextUseDistance B)
@ Mul
Product of integers.
@ Sub
Subtraction of integers.
@ Add
Sum of integers.
DWARFExpression::Operation Op
PredIterator< BasicBlock, Value::user_iterator > pred_iterator
Definition CFG.h:93
SCEVFlags
SCEVFlags are bitfield indices into SCEV's SubclassData.
constexpr unsigned BitWidth
LLVM_ABI bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.
Definition LCSSA.cpp:328
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
SmallPtrSet< const Loop *, 2 > PostIncLoopSet
auto predecessors(const MachineBasicBlock *BB)
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition iterator.h:368
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1963
LLVM_ABI std::optional< bool > isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL)
Return the boolean condition value in the context of the given instruction if it is known based on do...
SCEVUseT< const SCEV * > SCEVUse
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:881
LLVM_ABI void apply(Instruction *I)
LLVM_ABI PoisonFlags(const Instruction *I)
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
const SCEV * S
The SCEV operand to be costed.
unsigned ParentOpcode
LLVM instruction opcode that uses the operand.
int OperandIdx
The use index of an expanded instruction.
SCEVFlags getNoWrapFlags(SCEVFlags Mask=SCEVFlags::FlagsNoWrapMask) const
Return the flags for this SCEVUse, which is the union of the use-specific flags and the underlying SC...