Coverage Report

Created: 2017-11-23 03:11

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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