/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/include/polly/CodeGen/IslExprBuilder.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===-IslExprBuilder.h - Helper to generate code for isl AST expressions --===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | //===----------------------------------------------------------------------===// |
11 | | |
12 | | #ifndef POLLY_ISL_EXPR_BUILDER_H |
13 | | #define POLLY_ISL_EXPR_BUILDER_H |
14 | | |
15 | | #include "polly/CodeGen/IRBuilder.h" |
16 | | #include "polly/Support/ScopHelper.h" |
17 | | |
18 | | #include "llvm/ADT/MapVector.h" |
19 | | #include "isl/ast.h" |
20 | | #include "isl/isl-noexceptions.h" |
21 | | |
22 | | namespace llvm { |
23 | | class DataLayout; |
24 | | class ScalarEvolution; |
25 | | } // namespace llvm |
26 | | |
27 | | struct isl_id; |
28 | | |
29 | | namespace llvm { |
30 | | // Provide PointerLikeTypeTraits for isl_id. |
31 | | template <> struct PointerLikeTypeTraits<isl_id *> { |
32 | | |
33 | | public: |
34 | 0 | static inline const void *getAsVoidPointer(isl_id *P) { return (void *)P; } |
35 | 0 | static inline const Region *getFromVoidPointer(void *P) { |
36 | 0 | return (Region *)P; |
37 | 0 | } |
38 | | enum { NumLowBitsAvailable = 0 }; |
39 | | }; |
40 | | } // namespace llvm |
41 | | |
42 | | namespace polly { |
43 | | class ScopArrayInfo; |
44 | | |
45 | | /// LLVM-IR generator for isl_ast_expr[essions] |
46 | | /// |
47 | | /// This generator generates LLVM-IR that performs the computation described by |
48 | | /// an isl_ast_expr[ession]. |
49 | | /// |
50 | | /// Example: |
51 | | /// |
52 | | /// An isl_ast_expr[ession] can look like this: |
53 | | /// |
54 | | /// (N + M) + 10 |
55 | | /// |
56 | | /// The IslExprBuilder could create the following LLVM-IR: |
57 | | /// |
58 | | /// %tmp1 = add nsw i64 %N |
59 | | /// %tmp2 = add nsw i64 %tmp1, %M |
60 | | /// %tmp3 = add nsw i64 %tmp2, 10 |
61 | | /// |
62 | | /// The implementation of this class is mostly a mapping from isl_ast_expr |
63 | | /// constructs to the corresponding LLVM-IR constructs. |
64 | | /// |
65 | | /// The following decisions may need some explanation: |
66 | | /// |
67 | | /// 1) Which data-type to choose |
68 | | /// |
69 | | /// isl_ast_expr[essions] are untyped expressions that assume arbitrary |
70 | | /// precision integer computations. LLVM-IR instead has fixed size integers. |
71 | | /// When lowering to LLVM-IR we need to chose both the size of the data type and |
72 | | /// the sign of the operations we use. |
73 | | /// |
74 | | /// At the moment, we hardcode i64 bit signed computations. Our experience has |
75 | | /// shown that 64 bit are generally large enough for the loop bounds that appear |
76 | | /// in the wild. Signed computations are needed, as loop bounds may become |
77 | | /// negative. |
78 | | /// |
79 | | /// It is possible to track overflows that occurred in the generated IR. See the |
80 | | /// description of @see OverflowState for more information. |
81 | | /// |
82 | | /// FIXME: Hardcoding sizes can cause issues: |
83 | | /// |
84 | | /// - On embedded systems and especially for high-level-synthesis 64 bit |
85 | | /// computations are very costly. |
86 | | /// |
87 | | /// The right approach is to compute the minimal necessary bitwidth and |
88 | | /// signedness for each subexpression during in the isl AST generation and |
89 | | /// to use this information in our IslAstGenerator. Preliminary patches are |
90 | | /// available, but have not been committed yet. |
91 | | /// |
92 | | class IslExprBuilder { |
93 | | public: |
94 | | /// A map from isl_ids to llvm::Values. |
95 | | typedef llvm::MapVector<isl_id *, llvm::AssertingVH<llvm::Value>> IDToValueTy; |
96 | | |
97 | | typedef llvm::MapVector<isl_id *, const ScopArrayInfo *> IDToScopArrayInfoTy; |
98 | | |
99 | | /// A map from isl_ids to ScopArrayInfo objects. |
100 | | /// |
101 | | /// This map is used to obtain ScopArrayInfo objects for isl_ids which do not |
102 | | /// carry a ScopArrayInfo object in their user pointer. This is useful if the |
103 | | /// construction of ScopArrayInfo objects happens only after references (e.g. |
104 | | /// in an AST) to an isl_id are generated and the user pointer of the isl_id |
105 | | /// can not be changed any more. |
106 | | /// |
107 | | /// This is useful for external users who just use the IslExprBuilder for |
108 | | /// code generation. |
109 | | IDToScopArrayInfoTy *IDToSAI = nullptr; |
110 | | |
111 | | /// Set the isl_id to ScopArrayInfo map. |
112 | | /// |
113 | | /// @param NewIDToSAI The new isl_id to ScopArrayInfo map to use. |
114 | 0 | void setIDToSAI(IDToScopArrayInfoTy *NewIDToSAI) { IDToSAI = NewIDToSAI; } |
115 | | |
116 | | /// Construct an IslExprBuilder. |
117 | | /// |
118 | | /// @param Builder The IRBuilder used to construct the |
119 | | /// isl_ast_expr[ession]. The insert location of this |
120 | | /// IRBuilder defines WHERE the corresponding LLVM-IR |
121 | | /// is generated. |
122 | | /// @param IDToValue The isl_ast_expr[ession] may reference parameters or |
123 | | /// variables (identified by an isl_id). The IDTOValue map |
124 | | /// specifies the LLVM-IR Values that correspond to these |
125 | | /// parameters and variables. |
126 | | /// @param GlobalMap A mapping from llvm::Values used in the original scop |
127 | | /// region to a new set of llvm::Values. |
128 | | /// @param DL DataLayout for the current Module. |
129 | | /// @param SE ScalarEvolution analysis for the current function. |
130 | | /// @param DT DominatorTree analysis for the current function. |
131 | | /// @param LI LoopInfo analysis for the current function. |
132 | | /// @param StartBlock The first basic block after the RTC. |
133 | | IslExprBuilder(Scop &S, PollyIRBuilder &Builder, IDToValueTy &IDToValue, |
134 | | ValueMapT &GlobalMap, const llvm::DataLayout &DL, |
135 | | llvm::ScalarEvolution &SE, llvm::DominatorTree &DT, |
136 | | llvm::LoopInfo &LI, llvm::BasicBlock *StartBlock); |
137 | | |
138 | | /// Create LLVM-IR for an isl_ast_expr[ession]. |
139 | | /// |
140 | | /// @param Expr The ast expression for which we generate LLVM-IR. |
141 | | /// |
142 | | /// @return The llvm::Value* containing the result of the computation. |
143 | | llvm::Value *create(__isl_take isl_ast_expr *Expr); |
144 | | |
145 | | /// Return the largest of two types. |
146 | | /// |
147 | | /// @param T1 The first type. |
148 | | /// @param T2 The second type. |
149 | | /// |
150 | | /// @return The largest of the two types. |
151 | | llvm::Type *getWidestType(llvm::Type *T1, llvm::Type *T2); |
152 | | |
153 | | /// Return the type with which this expression should be computed. |
154 | | /// |
155 | | /// The type needs to be large enough to hold all possible input and all |
156 | | /// possible output values. |
157 | | /// |
158 | | /// @param Expr The expression for which to find the type. |
159 | | /// @return The type with which the expression should be computed. |
160 | | llvm::IntegerType *getType(__isl_keep isl_ast_expr *Expr); |
161 | | |
162 | | /// Change if runtime overflows are tracked or not. |
163 | | /// |
164 | | /// @param Enable Flag to enable/disable the tracking. |
165 | | /// |
166 | | /// Note that this will reset the tracking state and that tracking is only |
167 | | /// allowed if the last tracked expression dominates the current insert point. |
168 | | void setTrackOverflow(bool Enable); |
169 | | |
170 | | /// Return the current overflow status or nullptr if it is not tracked. |
171 | | /// |
172 | | /// @return A nullptr if tracking is disabled or otherwise an i1 that has the |
173 | | /// value of "0" if and only if no overflow happened since tracking |
174 | | /// was enabled. |
175 | | llvm::Value *getOverflowState() const; |
176 | | |
177 | | /// Create LLVM-IR that computes the memory location of an access expression. |
178 | | /// |
179 | | /// For a given isl_ast_expr[ession] of type isl_ast_op_access this function |
180 | | /// creates IR that computes the address the access expression refers to. |
181 | | /// |
182 | | /// @param Expr The ast expression of type isl_ast_op_access |
183 | | /// for which we generate LLVM-IR. |
184 | | /// |
185 | | /// @return The llvm::Value* containing the result of the computation. |
186 | | llvm::Value *createAccessAddress(__isl_take isl_ast_expr *Expr); |
187 | | |
188 | | /// Check if an @p Expr contains integer constants larger than 64 bit. |
189 | | /// |
190 | | /// @param Expr The expression to check. |
191 | | /// |
192 | | /// @return True if the ast expression is larger than 64 bit. |
193 | | bool hasLargeInts(isl::ast_expr Expr); |
194 | | |
195 | | private: |
196 | | Scop &S; |
197 | | |
198 | | /// Flag that will be set if an overflow occurred at runtime. |
199 | | /// |
200 | | /// Note that this flag is by default a nullptr and if it is a nullptr |
201 | | /// we will not record overflows but simply perform the computations. |
202 | | /// The intended usage is as follows: |
203 | | /// - If overflows in [an] expression[s] should be tracked, call |
204 | | /// the setTrackOverflow(true) function. |
205 | | /// - Use create(...) for all expressions that should be checked. |
206 | | /// - Call getOverflowState() to get the value representing the current |
207 | | /// state of the overflow flag. |
208 | | /// - To stop tracking call setTrackOverflow(false). |
209 | | llvm::Value *OverflowState; |
210 | | |
211 | | PollyIRBuilder &Builder; |
212 | | IDToValueTy &IDToValue; |
213 | | ValueMapT &GlobalMap; |
214 | | |
215 | | const llvm::DataLayout &DL; |
216 | | llvm::ScalarEvolution &SE; |
217 | | llvm::DominatorTree &DT; |
218 | | llvm::LoopInfo &LI; |
219 | | llvm::BasicBlock *StartBlock; |
220 | | |
221 | | llvm::Value *createOp(__isl_take isl_ast_expr *Expr); |
222 | | llvm::Value *createOpUnary(__isl_take isl_ast_expr *Expr); |
223 | | llvm::Value *createOpAccess(__isl_take isl_ast_expr *Expr); |
224 | | llvm::Value *createOpBin(__isl_take isl_ast_expr *Expr); |
225 | | llvm::Value *createOpNAry(__isl_take isl_ast_expr *Expr); |
226 | | llvm::Value *createOpSelect(__isl_take isl_ast_expr *Expr); |
227 | | llvm::Value *createOpICmp(__isl_take isl_ast_expr *Expr); |
228 | | llvm::Value *createOpBoolean(__isl_take isl_ast_expr *Expr); |
229 | | llvm::Value *createOpBooleanConditional(__isl_take isl_ast_expr *Expr); |
230 | | llvm::Value *createId(__isl_take isl_ast_expr *Expr); |
231 | | llvm::Value *createInt(__isl_take isl_ast_expr *Expr); |
232 | | llvm::Value *createOpAddressOf(__isl_take isl_ast_expr *Expr); |
233 | | |
234 | | /// Create a binary operation @p Opc and track overflows if requested. |
235 | | /// |
236 | | /// @param OpC The binary operation that should be performed [Add/Sub/Mul]. |
237 | | /// @param LHS The left operand. |
238 | | /// @param RHS The right operand. |
239 | | /// @param Name The (base) name of the new IR operations. |
240 | | /// |
241 | | /// @return A value that represents the result of the binary operation. |
242 | | llvm::Value *createBinOp(llvm::BinaryOperator::BinaryOps Opc, |
243 | | llvm::Value *LHS, llvm::Value *RHS, |
244 | | const llvm::Twine &Name); |
245 | | |
246 | | /// Create an addition and track overflows if requested. |
247 | | /// |
248 | | /// @param LHS The left operand. |
249 | | /// @param RHS The right operand. |
250 | | /// @param Name The (base) name of the new IR operations. |
251 | | /// |
252 | | /// @return A value that represents the result of the addition. |
253 | | llvm::Value *createAdd(llvm::Value *LHS, llvm::Value *RHS, |
254 | | const llvm::Twine &Name = ""); |
255 | | |
256 | | /// Create a subtraction and track overflows if requested. |
257 | | /// |
258 | | /// @param LHS The left operand. |
259 | | /// @param RHS The right operand. |
260 | | /// @param Name The (base) name of the new IR operations. |
261 | | /// |
262 | | /// @return A value that represents the result of the subtraction. |
263 | | llvm::Value *createSub(llvm::Value *LHS, llvm::Value *RHS, |
264 | | const llvm::Twine &Name = ""); |
265 | | |
266 | | /// Create a multiplication and track overflows if requested. |
267 | | /// |
268 | | /// @param LHS The left operand. |
269 | | /// @param RHS The right operand. |
270 | | /// @param Name The (base) name of the new IR operations. |
271 | | /// |
272 | | /// @return A value that represents the result of the multiplication. |
273 | | llvm::Value *createMul(llvm::Value *LHS, llvm::Value *RHS, |
274 | | const llvm::Twine &Name = ""); |
275 | | }; |
276 | | } // namespace polly |
277 | | |
278 | | #endif |