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