1//===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===//
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 defines the classes used to generate code from scalar expressions.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
14#define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
15
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/Analysis/InstSimplifyFolder.h"
20#include "llvm/Analysis/ScalarEvolutionExpressions.h"
21#include "llvm/Analysis/ScalarEvolutionNormalization.h"
22#include "llvm/Analysis/TargetTransformInfo.h"
23#include "llvm/IR/IRBuilder.h"
24#include "llvm/IR/ValueHandle.h"
25#include "llvm/Support/CommandLine.h"
26#include "llvm/Support/InstructionCost.h"
27
28namespace llvm {
29extern cl::opt<unsigned> SCEVCheapExpansionBudget;
30
31/// struct for holding enough information to help calculate the cost of the
32/// given SCEV when expanded into IR.
33struct SCEVOperand {
34 explicit SCEVOperand(unsigned Opc, int Idx, const SCEV *S) :
35 ParentOpcode(Opc), OperandIdx(Idx), S(S) { }
36 /// LLVM instruction opcode that uses the operand.
37 unsigned ParentOpcode;
38 /// The use index of an expanded instruction.
39 int OperandIdx;
40 /// The SCEV operand to be costed.
41 const SCEV* S;
42};
43
44struct PoisonFlags {
45 unsigned NUW : 1;
46 unsigned NSW : 1;
47 unsigned Exact : 1;
48 unsigned Disjoint : 1;
49 unsigned NNeg : 1;
50
51 PoisonFlags(const Instruction *I);
52 void apply(Instruction *I);
53};
54
55/// This class uses information about analyze scalars to rewrite expressions
56/// in canonical form.
57///
58/// Clients should create an instance of this class when rewriting is needed,
59/// and destroy it when finished to allow the release of the associated
60/// memory.
61class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> {
62 friend class SCEVExpanderCleaner;
63
64 ScalarEvolution &SE;
65 const DataLayout &DL;
66
67 // New instructions receive a name to identify them with the current pass.
68 const char *IVName;
69
70 /// Indicates whether LCSSA phis should be created for inserted values.
71 bool PreserveLCSSA;
72
73 // InsertedExpressions caches Values for reuse, so must track RAUW.
74 DenseMap<std::pair<const SCEV *, Instruction *>, TrackingVH<Value>>
75 InsertedExpressions;
76
77 // InsertedValues only flags inserted instructions so needs no RAUW.
78 DenseSet<AssertingVH<Value>> InsertedValues;
79 DenseSet<AssertingVH<Value>> InsertedPostIncValues;
80
81 /// Keep track of the existing IR values re-used during expansion.
82 /// FIXME: Ideally re-used instructions would not be added to
83 /// InsertedValues/InsertedPostIncValues.
84 SmallPtrSet<Value *, 16> ReusedValues;
85
86 /// Original flags of instructions for which they were modified. Used
87 /// by SCEVExpanderCleaner to undo changes.
88 DenseMap<PoisoningVH<Instruction>, PoisonFlags> OrigFlags;
89
90 // The induction variables generated.
91 SmallVector<WeakVH, 2> InsertedIVs;
92
93 /// A memoization of the "relevant" loop for a given SCEV.
94 DenseMap<const SCEV *, const Loop *> RelevantLoops;
95
96 /// Addrecs referring to any of the given loops are expanded in post-inc
97 /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
98 /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
99 /// phi starting at 1. This is only supported in non-canonical mode.
100 PostIncLoopSet PostIncLoops;
101
102 /// When this is non-null, addrecs expanded in the loop it indicates should
103 /// be inserted with increments at IVIncInsertPos.
104 const Loop *IVIncInsertLoop;
105
106 /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV
107 /// increment at this position.
108 Instruction *IVIncInsertPos;
109
110 /// Phis that complete an IV chain. Reuse
111 DenseSet<AssertingVH<PHINode>> ChainedPhis;
112
113 /// When true, SCEVExpander tries to expand expressions in "canonical" form.
114 /// When false, expressions are expanded in a more literal form.
115 ///
116 /// In "canonical" form addrecs are expanded as arithmetic based on a
117 /// canonical induction variable. Note that CanonicalMode doesn't guarantee
118 /// that all expressions are expanded in "canonical" form. For some
119 /// expressions literal mode can be preferred.
120 bool CanonicalMode;
121
122 /// When invoked from LSR, the expander is in "strength reduction" mode. The
123 /// only difference is that phi's are only reused if they are already in
124 /// "expanded" form.
125 bool LSRMode;
126
127 typedef IRBuilder<InstSimplifyFolder, IRBuilderCallbackInserter> BuilderType;
128 BuilderType Builder;
129
130 // RAII object that stores the current insertion point and restores it when
131 // the object is destroyed. This includes the debug location. Duplicated
132 // from InsertPointGuard to add SetInsertPoint() which is used to updated
133 // InsertPointGuards stack when insert points are moved during SCEV
134 // expansion.
135 class SCEVInsertPointGuard {
136 IRBuilderBase &Builder;
137 AssertingVH<BasicBlock> Block;
138 BasicBlock::iterator Point;
139 DebugLoc DbgLoc;
140 SCEVExpander *SE;
141
142 SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
143 SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
144
145 public:
146 SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
147 : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
148 DbgLoc(B.getCurrentDebugLocation()), SE(SE) {
149 SE->InsertPointGuards.push_back(Elt: this);
150 }
151
152 ~SCEVInsertPointGuard() {
153 // These guards should always created/destroyed in FIFO order since they
154 // are used to guard lexically scoped blocks of code in
155 // ScalarEvolutionExpander.
156 assert(SE->InsertPointGuards.back() == this);
157 SE->InsertPointGuards.pop_back();
158 Builder.restoreIP(IP: IRBuilderBase::InsertPoint(Block, Point));
159 Builder.SetCurrentDebugLocation(DbgLoc);
160 }
161
162 BasicBlock::iterator GetInsertPoint() const { return Point; }
163 void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
164 };
165
166 /// Stack of pointers to saved insert points, used to keep insert points
167 /// consistent when instructions are moved.
168 SmallVector<SCEVInsertPointGuard *, 8> InsertPointGuards;
169
170#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
171 const char *DebugType;
172#endif
173
174 friend struct SCEVVisitor<SCEVExpander, Value *>;
175
176public:
177 /// Construct a SCEVExpander in "canonical" mode.
178 explicit SCEVExpander(ScalarEvolution &se, const DataLayout &DL,
179 const char *name, bool PreserveLCSSA = true)
180 : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA),
181 IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true),
182 LSRMode(false),
183 Builder(se.getContext(), InstSimplifyFolder(DL),
184 IRBuilderCallbackInserter(
185 [this](Instruction *I) { rememberInstruction(I); })) {
186#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
187 DebugType = "";
188#endif
189 }
190
191 ~SCEVExpander() {
192 // Make sure the insert point guard stack is consistent.
193 assert(InsertPointGuards.empty());
194 }
195
196#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
197 void setDebugType(const char *s) { DebugType = s; }
198#endif
199
200 /// Erase the contents of the InsertedExpressions map so that users trying
201 /// to expand the same expression into multiple BasicBlocks or different
202 /// places within the same BasicBlock can do so.
203 void clear() {
204 InsertedExpressions.clear();
205 InsertedValues.clear();
206 InsertedPostIncValues.clear();
207 ReusedValues.clear();
208 OrigFlags.clear();
209 ChainedPhis.clear();
210 InsertedIVs.clear();
211 }
212
213 ScalarEvolution *getSE() { return &SE; }
214 const SmallVectorImpl<WeakVH> &getInsertedIVs() const { return InsertedIVs; }
215
216 /// Return a vector containing all instructions inserted during expansion.
217 SmallVector<Instruction *, 32> getAllInsertedInstructions() const {
218 SmallVector<Instruction *, 32> Result;
219 for (const auto &VH : InsertedValues) {
220 Value *V = VH;
221 if (ReusedValues.contains(Ptr: V))
222 continue;
223 if (auto *Inst = dyn_cast<Instruction>(Val: V))
224 Result.push_back(Elt: Inst);
225 }
226 for (const auto &VH : InsertedPostIncValues) {
227 Value *V = VH;
228 if (ReusedValues.contains(Ptr: V))
229 continue;
230 if (auto *Inst = dyn_cast<Instruction>(Val: V))
231 Result.push_back(Elt: Inst);
232 }
233
234 return Result;
235 }
236
237 /// Return true for expressions that can't be evaluated at runtime
238 /// within given \b Budget.
239 ///
240 /// \p At is a parameter which specifies point in code where user is going to
241 /// expand these expressions. Sometimes this knowledge can lead to
242 /// a less pessimistic cost estimation.
243 bool isHighCostExpansion(ArrayRef<const SCEV *> Exprs, Loop *L,
244 unsigned Budget, const TargetTransformInfo *TTI,
245 const Instruction *At) {
246 assert(TTI && "This function requires TTI to be provided.");
247 assert(At && "This function requires At instruction to be provided.");
248 if (!TTI) // In assert-less builds, avoid crashing
249 return true; // by always claiming to be high-cost.
250 SmallVector<SCEVOperand, 8> Worklist;
251 SmallPtrSet<const SCEV *, 8> Processed;
252 InstructionCost Cost = 0;
253 unsigned ScaledBudget = Budget * TargetTransformInfo::TCC_Basic;
254 for (auto *Expr : Exprs)
255 Worklist.emplace_back(Args: -1, Args: -1, Args&: Expr);
256 while (!Worklist.empty()) {
257 const SCEVOperand WorkItem = Worklist.pop_back_val();
258 if (isHighCostExpansionHelper(WorkItem, L, At: *At, Cost, Budget: ScaledBudget, TTI: *TTI,
259 Processed, Worklist))
260 return true;
261 }
262 assert(Cost <= ScaledBudget && "Should have returned from inner loop.");
263 return false;
264 }
265
266 /// Return the induction variable increment's IV operand.
267 Instruction *getIVIncOperand(Instruction *IncV, Instruction *InsertPos,
268 bool allowScale);
269
270 /// Utility for hoisting \p IncV (with all subexpressions requried for its
271 /// computation) before \p InsertPos. If \p RecomputePoisonFlags is set, drops
272 /// all poison-generating flags from instructions being hoisted and tries to
273 /// re-infer them in the new location. It should be used when we are going to
274 /// introduce a new use in the new position that didn't exist before, and may
275 /// trigger new UB in case of poison.
276 bool hoistIVInc(Instruction *IncV, Instruction *InsertPos,
277 bool RecomputePoisonFlags = false);
278
279 /// Return true if both increments directly increment the corresponding IV PHI
280 /// nodes and have the same opcode. It is not safe to re-use the flags from
281 /// the original increment, if it is more complex and SCEV expansion may have
282 /// yielded a more simplified wider increment.
283 static bool canReuseFlagsFromOriginalIVInc(PHINode *OrigPhi, PHINode *WidePhi,
284 Instruction *OrigInc,
285 Instruction *WideInc);
286
287 /// replace congruent phis with their most canonical representative. Return
288 /// the number of phis eliminated.
289 unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
290 SmallVectorImpl<WeakTrackingVH> &DeadInsts,
291 const TargetTransformInfo *TTI = nullptr);
292
293 /// Return true if the given expression is safe to expand in the sense that
294 /// all materialized values are safe to speculate anywhere their operands are
295 /// defined, and the expander is capable of expanding the expression.
296 bool isSafeToExpand(const SCEV *S) const;
297
298 /// Return true if the given expression is safe to expand in the sense that
299 /// all materialized values are defined and safe to speculate at the specified
300 /// location and their operands are defined at this location.
301 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const;
302
303 /// Insert code to directly compute the specified SCEV expression into the
304 /// program. The code is inserted into the specified block.
305 Value *expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I);
306 Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I) {
307 return expandCodeFor(SH, Ty, I: I->getIterator());
308 }
309
310 /// Insert code to directly compute the specified SCEV expression into the
311 /// program. The code is inserted into the SCEVExpander's current
312 /// insertion point. If a type is specified, the result will be expanded to
313 /// have that type, with a cast if necessary.
314 Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
315
316 /// Generates a code sequence that evaluates this predicate. The inserted
317 /// instructions will be at position \p Loc. The result will be of type i1
318 /// and will have a value of 0 when the predicate is false and 1 otherwise.
319 Value *expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc);
320
321 /// A specialized variant of expandCodeForPredicate, handling the case when
322 /// we are expanding code for a SCEVComparePredicate.
323 Value *expandComparePredicate(const SCEVComparePredicate *Pred,
324 Instruction *Loc);
325
326 /// Generates code that evaluates if the \p AR expression will overflow.
327 Value *generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc,
328 bool Signed);
329
330 /// A specialized variant of expandCodeForPredicate, handling the case when
331 /// we are expanding code for a SCEVWrapPredicate.
332 Value *expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc);
333
334 /// A specialized variant of expandCodeForPredicate, handling the case when
335 /// we are expanding code for a SCEVUnionPredicate.
336 Value *expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc);
337
338 /// Set the current IV increment loop and position.
339 void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
340 assert(!CanonicalMode &&
341 "IV increment positions are not supported in CanonicalMode");
342 IVIncInsertLoop = L;
343 IVIncInsertPos = Pos;
344 }
345
346 /// Enable post-inc expansion for addrecs referring to the given
347 /// loops. Post-inc expansion is only supported in non-canonical mode.
348 void setPostInc(const PostIncLoopSet &L) {
349 assert(!CanonicalMode &&
350 "Post-inc expansion is not supported in CanonicalMode");
351 PostIncLoops = L;
352 }
353
354 /// Disable all post-inc expansion.
355 void clearPostInc() {
356 PostIncLoops.clear();
357
358 // When we change the post-inc loop set, cached expansions may no
359 // longer be valid.
360 InsertedPostIncValues.clear();
361 }
362
363 /// Disable the behavior of expanding expressions in canonical form rather
364 /// than in a more literal form. Non-canonical mode is useful for late
365 /// optimization passes.
366 void disableCanonicalMode() { CanonicalMode = false; }
367
368 void enableLSRMode() { LSRMode = true; }
369
370 /// Set the current insertion point. This is useful if multiple calls to
371 /// expandCodeFor() are going to be made with the same insert point and the
372 /// insert point may be moved during one of the expansions (e.g. if the
373 /// insert point is not a block terminator).
374 void setInsertPoint(Instruction *IP) {
375 assert(IP);
376 Builder.SetInsertPoint(IP);
377 }
378
379 void setInsertPoint(BasicBlock::iterator IP) {
380 Builder.SetInsertPoint(TheBB: IP->getParent(), IP);
381 }
382
383 /// Clear the current insertion point. This is useful if the instruction
384 /// that had been serving as the insertion point may have been deleted.
385 void clearInsertPoint() { Builder.ClearInsertionPoint(); }
386
387 /// Set location information used by debugging information.
388 void SetCurrentDebugLocation(DebugLoc L) {
389 Builder.SetCurrentDebugLocation(std::move(L));
390 }
391
392 /// Get location information used by debugging information.
393 DebugLoc getCurrentDebugLocation() const {
394 return Builder.getCurrentDebugLocation();
395 }
396
397 /// Return true if the specified instruction was inserted by the code
398 /// rewriter. If so, the client should not modify the instruction. Note that
399 /// this also includes instructions re-used during expansion.
400 bool isInsertedInstruction(Instruction *I) const {
401 return InsertedValues.count(V: I) || InsertedPostIncValues.count(V: I);
402 }
403
404 void setChainedPhi(PHINode *PN) { ChainedPhis.insert(V: PN); }
405
406 /// Determine whether there is an existing expansion of S that can be reused.
407 /// This is used to check whether S can be expanded cheaply.
408 ///
409 /// L is a hint which tells in which loop to look for the suitable value.
410 ///
411 /// Note that this function does not perform an exhaustive search. I.e if it
412 /// didn't find any value it does not mean that there is no such value.
413 bool hasRelatedExistingExpansion(const SCEV *S, const Instruction *At,
414 Loop *L);
415
416 /// Returns a suitable insert point after \p I, that dominates \p
417 /// MustDominate. Skips instructions inserted by the expander.
418 BasicBlock::iterator findInsertPointAfter(Instruction *I,
419 Instruction *MustDominate) const;
420
421private:
422 LLVMContext &getContext() const { return SE.getContext(); }
423
424 /// Recursive helper function for isHighCostExpansion.
425 bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,
426 const Instruction &At, InstructionCost &Cost,
427 unsigned Budget,
428 const TargetTransformInfo &TTI,
429 SmallPtrSetImpl<const SCEV *> &Processed,
430 SmallVectorImpl<SCEVOperand> &Worklist);
431
432 /// Insert the specified binary operator, doing a small amount of work to
433 /// avoid inserting an obviously redundant operation, and hoisting to an
434 /// outer loop when the opportunity is there and it is safe.
435 Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
436 SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
437
438 /// We want to cast \p V. What would be the best place for such a cast?
439 BasicBlock::iterator GetOptimalInsertionPointForCastOf(Value *V) const;
440
441 /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
442 /// cast if a suitable one exists, moving an existing cast if a suitable one
443 /// exists but isn't in the right place, or creating a new one.
444 Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op,
445 BasicBlock::iterator IP);
446
447 /// Insert a cast of V to the specified type, which must be possible with a
448 /// noop cast, doing what we can to share the casts.
449 Value *InsertNoopCastOfTo(Value *V, Type *Ty);
450
451 /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
452 /// ptrtoint+arithmetic+inttoptr.
453 Value *expandAddToGEP(const SCEV *Op, Value *V);
454
455 /// Find a previous Value in ExprValueMap for expand.
456 /// DropPoisonGeneratingInsts is populated with instructions for which
457 /// poison-generating flags must be dropped if the value is reused.
458 Value *FindValueInExprValueMap(
459 const SCEV *S, const Instruction *InsertPt,
460 SmallVectorImpl<Instruction *> &DropPoisonGeneratingInsts);
461
462 Value *expand(const SCEV *S);
463 Value *expand(const SCEV *S, BasicBlock::iterator I) {
464 setInsertPoint(I);
465 return expand(S);
466 }
467 Value *expand(const SCEV *S, Instruction *I) {
468 setInsertPoint(I);
469 return expand(S);
470 }
471
472 /// Determine the most "relevant" loop for the given SCEV.
473 const Loop *getRelevantLoop(const SCEV *);
474
475 Value *expandMinMaxExpr(const SCEVNAryExpr *S, Intrinsic::ID IntrinID,
476 Twine Name, bool IsSequential = false);
477
478 Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
479
480 Value *visitVScale(const SCEVVScale *S);
481
482 Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
483
484 Value *visitTruncateExpr(const SCEVTruncateExpr *S);
485
486 Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
487
488 Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
489
490 Value *visitAddExpr(const SCEVAddExpr *S);
491
492 Value *visitMulExpr(const SCEVMulExpr *S);
493
494 Value *visitUDivExpr(const SCEVUDivExpr *S);
495
496 Value *visitAddRecExpr(const SCEVAddRecExpr *S);
497
498 Value *visitSMaxExpr(const SCEVSMaxExpr *S);
499
500 Value *visitUMaxExpr(const SCEVUMaxExpr *S);
501
502 Value *visitSMinExpr(const SCEVSMinExpr *S);
503
504 Value *visitUMinExpr(const SCEVUMinExpr *S);
505
506 Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);
507
508 Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
509
510 void rememberInstruction(Value *I);
511
512 void rememberFlags(Instruction *I);
513
514 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
515
516 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
517
518 Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
519 PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
520 const Loop *L, Type *&TruncTy,
521 bool &InvertStep);
522 Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
523 bool useSubtract);
524
525 void fixupInsertPoints(Instruction *I);
526
527 /// Create LCSSA PHIs for \p V, if it is required for uses at the Builder's
528 /// current insertion point.
529 Value *fixupLCSSAFormFor(Value *V);
530
531 /// Replace congruent phi increments with their most canonical representative.
532 /// May swap \p Phi and \p OrigPhi, if \p Phi is more canonical, due to its
533 /// increment.
534 void replaceCongruentIVInc(PHINode *&Phi, PHINode *&OrigPhi, Loop *L,
535 const DominatorTree *DT,
536 SmallVectorImpl<WeakTrackingVH> &DeadInsts);
537};
538
539/// Helper to remove instructions inserted during SCEV expansion, unless they
540/// are marked as used.
541class SCEVExpanderCleaner {
542 SCEVExpander &Expander;
543
544 /// Indicates whether the result of the expansion is used. If false, the
545 /// instructions added during expansion are removed.
546 bool ResultUsed;
547
548public:
549 SCEVExpanderCleaner(SCEVExpander &Expander)
550 : Expander(Expander), ResultUsed(false) {}
551
552 ~SCEVExpanderCleaner() { cleanup(); }
553
554 /// Indicate that the result of the expansion is used.
555 void markResultUsed() { ResultUsed = true; }
556
557 void cleanup();
558};
559} // namespace llvm
560
561#endif
562