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