Coverage Report

Created: 2019-04-21 11:35

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