1 //===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the classes used to generate code from scalar expressions.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
15 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
17 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
18 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
19 #include "llvm/Analysis/TargetFolder.h"
20 #include "llvm/IR/IRBuilder.h"
21 #include "llvm/IR/ValueHandle.h"
25 class TargetTransformInfo
;
27 /// Return true if the given expression is safe to expand in the sense that
28 /// all materialized values are safe to speculate.
29 bool isSafeToExpand(const SCEV
*S
, ScalarEvolution
&SE
);
31 /// SCEVExpander - This class uses information about analyze scalars to
32 /// rewrite expressions in canonical form.
34 /// Clients should create an instance of this class when rewriting is needed,
35 /// and destroy it when finished to allow the release of the associated
37 class SCEVExpander
: public SCEVVisitor
<SCEVExpander
, Value
*> {
40 // New instructions receive a name to identifies them with the current pass.
43 // InsertedExpressions caches Values for reuse, so must track RAUW.
44 std::map
<std::pair
<const SCEV
*, Instruction
*>, TrackingVH
<Value
> >
46 // InsertedValues only flags inserted instructions so needs no RAUW.
47 std::set
<AssertingVH
<Value
> > InsertedValues
;
48 std::set
<AssertingVH
<Value
> > InsertedPostIncValues
;
50 /// RelevantLoops - A memoization of the "relevant" loop for a given SCEV.
51 DenseMap
<const SCEV
*, const Loop
*> RelevantLoops
;
53 /// PostIncLoops - Addrecs referring to any of the given loops are expanded
54 /// in post-inc mode. For example, expanding {1,+,1}<L> in post-inc mode
55 /// returns the add instruction that adds one to the phi for {0,+,1}<L>,
56 /// as opposed to a new phi starting at 1. This is only supported in
57 /// non-canonical mode.
58 PostIncLoopSet PostIncLoops
;
60 /// IVIncInsertPos - When this is non-null, addrecs expanded in the
61 /// loop it indicates should be inserted with increments at
63 const Loop
*IVIncInsertLoop
;
65 /// IVIncInsertPos - When expanding addrecs in the IVIncInsertLoop loop,
66 /// insert the IV increment at this position.
67 Instruction
*IVIncInsertPos
;
69 /// Phis that complete an IV chain. Reuse
70 std::set
<AssertingVH
<PHINode
> > ChainedPhis
;
72 /// CanonicalMode - When true, expressions are expanded in "canonical"
73 /// form. In particular, addrecs are expanded as arithmetic based on
74 /// a canonical induction variable. When false, expression are expanded
75 /// in a more literal form.
78 /// When invoked from LSR, the expander is in "strength reduction" mode. The
79 /// only difference is that phi's are only reused if they are already in
83 typedef IRBuilder
<true, TargetFolder
> BuilderType
;
87 const char *DebugType
;
90 friend struct SCEVVisitor
<SCEVExpander
, Value
*>;
93 /// SCEVExpander - Construct a SCEVExpander in "canonical" mode.
94 explicit SCEVExpander(ScalarEvolution
&se
, const char *name
)
95 : SE(se
), IVName(name
), IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr),
96 CanonicalMode(true), LSRMode(false),
97 Builder(se
.getContext(), TargetFolder(se
.DL
)) {
104 void setDebugType(const char* s
) { DebugType
= s
; }
107 /// clear - Erase the contents of the InsertedExpressions map so that users
108 /// trying to expand the same expression into multiple BasicBlocks or
109 /// different places within the same BasicBlock can do so.
111 InsertedExpressions
.clear();
112 InsertedValues
.clear();
113 InsertedPostIncValues
.clear();
117 /// getOrInsertCanonicalInductionVariable - This method returns the
118 /// canonical induction variable of the specified type for the specified
119 /// loop (inserting one if there is none). A canonical induction variable
120 /// starts at zero and steps by one on each iteration.
121 PHINode
*getOrInsertCanonicalInductionVariable(const Loop
*L
, Type
*Ty
);
123 /// getIVIncOperand - Return the induction variable increment's IV operand.
124 Instruction
*getIVIncOperand(Instruction
*IncV
, Instruction
*InsertPos
,
127 /// hoistIVInc - Utility for hoisting an IV increment.
128 bool hoistIVInc(Instruction
*IncV
, Instruction
*InsertPos
);
130 /// replaceCongruentIVs - replace congruent phis with their most canonical
131 /// representative. Return the number of phis eliminated.
132 unsigned replaceCongruentIVs(Loop
*L
, const DominatorTree
*DT
,
133 SmallVectorImpl
<WeakVH
> &DeadInsts
,
134 const TargetTransformInfo
*TTI
= nullptr);
136 /// expandCodeFor - Insert code to directly compute the specified SCEV
137 /// expression into the program. The inserted code is inserted into the
139 Value
*expandCodeFor(const SCEV
*SH
, Type
*Ty
, Instruction
*I
);
141 /// setIVIncInsertPos - Set the current IV increment loop and position.
142 void setIVIncInsertPos(const Loop
*L
, Instruction
*Pos
) {
143 assert(!CanonicalMode
&&
144 "IV increment positions are not supported in CanonicalMode");
146 IVIncInsertPos
= Pos
;
149 /// setPostInc - Enable post-inc expansion for addrecs referring to the
150 /// given loops. Post-inc expansion is only supported in non-canonical
152 void setPostInc(const PostIncLoopSet
&L
) {
153 assert(!CanonicalMode
&&
154 "Post-inc expansion is not supported in CanonicalMode");
158 /// clearPostInc - Disable all post-inc expansion.
159 void clearPostInc() {
160 PostIncLoops
.clear();
162 // When we change the post-inc loop set, cached expansions may no
164 InsertedPostIncValues
.clear();
167 /// disableCanonicalMode - Disable the behavior of expanding expressions in
168 /// canonical form rather than in a more literal form. Non-canonical mode
169 /// is useful for late optimization passes.
170 void disableCanonicalMode() { CanonicalMode
= false; }
172 void enableLSRMode() { LSRMode
= true; }
174 /// clearInsertPoint - Clear the current insertion point. This is useful
175 /// if the instruction that had been serving as the insertion point may
176 /// have been deleted.
177 void clearInsertPoint() {
178 Builder
.ClearInsertionPoint();
181 /// isInsertedInstruction - Return true if the specified instruction was
182 /// inserted by the code rewriter. If so, the client should not modify the
184 bool isInsertedInstruction(Instruction
*I
) const {
185 return InsertedValues
.count(I
) || InsertedPostIncValues
.count(I
);
188 void setChainedPhi(PHINode
*PN
) { ChainedPhis
.insert(PN
); }
191 LLVMContext
&getContext() const { return SE
.getContext(); }
193 /// InsertBinop - Insert the specified binary operator, doing a small amount
194 /// of work to avoid inserting an obviously redundant operation.
195 Value
*InsertBinop(Instruction::BinaryOps Opcode
, Value
*LHS
, Value
*RHS
);
197 /// ReuseOrCreateCast - Arange for there to be a cast of V to Ty at IP,
198 /// reusing an existing cast if a suitable one exists, moving an existing
199 /// cast if a suitable one exists but isn't in the right place, or
200 /// or creating a new one.
201 Value
*ReuseOrCreateCast(Value
*V
, Type
*Ty
,
202 Instruction::CastOps Op
,
203 BasicBlock::iterator IP
);
205 /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
206 /// which must be possible with a noop cast, doing what we can to
208 Value
*InsertNoopCastOfTo(Value
*V
, Type
*Ty
);
210 /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP
211 /// instead of using ptrtoint+arithmetic+inttoptr.
212 Value
*expandAddToGEP(const SCEV
*const *op_begin
,
213 const SCEV
*const *op_end
,
214 PointerType
*PTy
, Type
*Ty
, Value
*V
);
216 Value
*expand(const SCEV
*S
);
218 /// expandCodeFor - Insert code to directly compute the specified SCEV
219 /// expression into the program. The inserted code is inserted into the
220 /// SCEVExpander's current insertion point. If a type is specified, the
221 /// result will be expanded to have that type, with a cast if necessary.
222 Value
*expandCodeFor(const SCEV
*SH
, Type
*Ty
= nullptr);
224 /// getRelevantLoop - Determine the most "relevant" loop for the given SCEV.
225 const Loop
*getRelevantLoop(const SCEV
*);
227 Value
*visitConstant(const SCEVConstant
*S
) {
228 return S
->getValue();
231 Value
*visitTruncateExpr(const SCEVTruncateExpr
*S
);
233 Value
*visitZeroExtendExpr(const SCEVZeroExtendExpr
*S
);
235 Value
*visitSignExtendExpr(const SCEVSignExtendExpr
*S
);
237 Value
*visitAddExpr(const SCEVAddExpr
*S
);
239 Value
*visitMulExpr(const SCEVMulExpr
*S
);
241 Value
*visitUDivExpr(const SCEVUDivExpr
*S
);
243 Value
*visitAddRecExpr(const SCEVAddRecExpr
*S
);
245 Value
*visitSMaxExpr(const SCEVSMaxExpr
*S
);
247 Value
*visitUMaxExpr(const SCEVUMaxExpr
*S
);
249 Value
*visitUnknown(const SCEVUnknown
*S
) {
250 return S
->getValue();
253 void rememberInstruction(Value
*I
);
255 bool isNormalAddRecExprPHI(PHINode
*PN
, Instruction
*IncV
, const Loop
*L
);
257 bool isExpandedAddRecExprPHI(PHINode
*PN
, Instruction
*IncV
, const Loop
*L
);
259 Value
*expandAddRecExprLiterally(const SCEVAddRecExpr
*);
260 PHINode
*getAddRecExprPHILiterally(const SCEVAddRecExpr
*Normalized
,
266 Value
*expandIVInc(PHINode
*PN
, Value
*StepV
, const Loop
*L
,
267 Type
*ExpandTy
, Type
*IntTy
, bool useSubtract
);