Coverage Report

Created: 2017-03-27 23:01

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/include/polly/CodeGen/IslNodeBuilder.h
Line
Count
Source
1
//===------ IslNodeBuilder.cpp - Translate an isl AST into a LLVM-IR AST---===//
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
// This file contains the IslNodeBuilder, a class to translate an isl AST into
10
// a LLVM-IR AST.
11
//===----------------------------------------------------------------------===//
12
13
#ifndef POLLY_ISL_NODE_BUILDER_H
14
#define POLLY_ISL_NODE_BUILDER_H
15
16
#include "polly/CodeGen/BlockGenerators.h"
17
#include "polly/CodeGen/IslExprBuilder.h"
18
#include "polly/CodeGen/LoopGenerators.h"
19
#include "polly/ScopInfo.h"
20
#include "llvm/ADT/ArrayRef.h"
21
#include "llvm/ADT/SetVector.h"
22
#include "llvm/ADT/SmallSet.h"
23
#include "llvm/ADT/SmallVector.h"
24
#include "isl/ctx.h"
25
#include "isl/union_map.h"
26
#include <utility>
27
#include <vector>
28
29
using namespace polly;
30
using namespace llvm;
31
32
struct isl_ast_node;
33
struct isl_ast_build;
34
struct isl_union_map;
35
36
struct SubtreeReferences {
37
  LoopInfo &LI;
38
  ScalarEvolution &SE;
39
  Scop &S;
40
  ValueMapT &GlobalMap;
41
  SetVector<Value *> &Values;
42
  SetVector<const SCEV *> &SCEVs;
43
  BlockGenerator &BlockGen;
44
};
45
46
/// Extract the out-of-scop values and SCEVs referenced from a ScopStmt.
47
///
48
/// This includes the SCEVUnknowns referenced by the SCEVs used in the
49
/// statement and the base pointers of the memory accesses. For scalar
50
/// statements we force the generation of alloca memory locations and list
51
/// these locations in the set of out-of-scop values as well.
52
///
53
/// @param Stmt             The statement for which to extract the information.
54
/// @param UserPtr          A void pointer that can be casted to a
55
///                         SubtreeReferences structure.
56
/// @param CreateScalarRefs Should the result include allocas of scalar
57
///                         references?
58
isl_stat addReferencesFromStmt(const ScopStmt *Stmt, void *UserPtr,
59
                               bool CreateScalarRefs = true);
60
61
class IslNodeBuilder {
62
public:
63
  IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P,
64
                 const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE,
65
                 DominatorTree &DT, Scop &S, BasicBlock *StartBlock)
66
      : S(S), Builder(Builder), Annotator(Annotator),
67
        ExprBuilder(S, Builder, IDToValue, ValueMap, DL, SE, DT, LI,
68
                    StartBlock),
69
        BlockGen(Builder, LI, SE, DT, ScalarMap, EscapeMap, ValueMap,
70
                 &ExprBuilder, StartBlock),
71
        RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT),
72
258
        StartBlock(StartBlock) {}
73
74
258
  virtual ~IslNodeBuilder() = default;
75
76
  void addParameters(__isl_take isl_set *Context);
77
78
  /// Generate code that evaluates @p Condition at run-time.
79
  ///
80
  /// This function is typically called to generate the LLVM-IR for the
81
  /// run-time condition of the scop, that verifies that all the optimistic
82
  /// assumptions we have taken during scop modeling and transformation
83
  /// hold at run-time.
84
  ///
85
  /// @param Condition The condition to evaluate
86
  ///
87
  /// @result An llvm::Value that is true if the condition holds and false
88
  ///         otherwise.
89
  Value *createRTC(isl_ast_expr *Condition);
90
91
  void create(__isl_take isl_ast_node *Node);
92
93
  /// Allocate memory for all new arrays created by Polly.
94
  void allocateNewArrays();
95
96
  /// Preload all memory loads that are invariant.
97
  bool preloadInvariantLoads();
98
99
  /// Finalize code generation.
100
  ///
101
  /// @see BlockGenerator::finalizeSCoP(Scop &S)
102
253
  virtual void finalize() { BlockGen.finalizeSCoP(S); }
103
104
253
  IslExprBuilder &getExprBuilder() { return ExprBuilder; }
105
106
  /// Get the associated block generator.
107
  ///
108
  /// @return A referecne to the associated block generator.
109
26
  BlockGenerator &getBlockGenerator() { return BlockGen; }
110
111
  /// Return the parallel subfunctions that have been created.
112
258
  const ArrayRef<Function *> getParallelSubfunctions() const {
113
258
    return ParallelSubfunctions;
114
258
  }
115
116
protected:
117
  Scop &S;
118
  PollyIRBuilder &Builder;
119
  ScopAnnotator &Annotator;
120
121
  IslExprBuilder ExprBuilder;
122
123
  /// Maps used by the block and region generator to demote scalars.
124
  ///
125
  ///@{
126
127
  /// See BlockGenerator::ScalarMap.
128
  BlockGenerator::AllocaMapTy ScalarMap;
129
130
  /// See BlockGenerator::EscapeMap.
131
  BlockGenerator::EscapeUsersAllocaMapTy EscapeMap;
132
133
  ///@}
134
135
  /// The generator used to copy a basic block.
136
  BlockGenerator BlockGen;
137
138
  /// The generator used to copy a non-affine region.
139
  RegionGenerator RegionGen;
140
141
  Pass *const P;
142
  const DataLayout &DL;
143
  LoopInfo &LI;
144
  ScalarEvolution &SE;
145
  DominatorTree &DT;
146
  BasicBlock *StartBlock;
147
148
  /// The current iteration of out-of-scop loops
149
  ///
150
  /// This map provides for a given loop a llvm::Value that contains the current
151
  /// loop iteration.
152
  LoopToScevMapT OutsideLoopIterations;
153
154
  // This maps an isl_id* to the Value* it has in the generated program. For now
155
  // on, the only isl_ids that are stored here are the newly calculated loop
156
  // ivs.
157
  IslExprBuilder::IDToValueTy IDToValue;
158
159
  /// A collection of all parallel subfunctions that have been created.
160
  SmallVector<Function *, 8> ParallelSubfunctions;
161
162
  /// Generate code for a given SCEV*
163
  ///
164
  /// This function generates code for a given SCEV expression. It generated
165
  /// code is emitted at the end of the basic block our Builder currently
166
  /// points to and the resulting value is returned.
167
  ///
168
  /// @param Expr The expression to code generate.
169
  llvm::Value *generateSCEV(const SCEV *Expr);
170
171
  /// A set of Value -> Value remappings to apply when generating new code.
172
  ///
173
  /// When generating new code for a ScopStmt this map is used to map certain
174
  /// llvm::Values to new llvm::Values.
175
  ValueMapT ValueMap;
176
177
  /// Materialize code for @p Id if it was not done before.
178
  ///
179
  /// @returns False, iff a problem occured and the value was not materialized.
180
  bool materializeValue(__isl_take isl_id *Id);
181
182
  /// Materialize parameters of @p Set.
183
  ///
184
  /// @returns False, iff a problem occurred and the value was not materialized.
185
  bool materializeParameters(__isl_take isl_set *Set);
186
187
  /// Materialize all parameters in the current scop.
188
  ///
189
  /// @returns False, iff a problem occurred and the value was not materialized.
190
  bool materializeParameters();
191
192
  // Extract the upper bound of this loop
193
  //
194
  // The isl code generation can generate arbitrary expressions to check if the
195
  // upper bound of a loop is reached, but it provides an option to enforce
196
  // 'atomic' upper bounds. An 'atomic upper bound is always of the form
197
  // iv <= expr, where expr is an (arbitrary) expression not containing iv.
198
  //
199
  // This function extracts 'atomic' upper bounds. Polly, in general, requires
200
  // atomic upper bounds for the following reasons:
201
  //
202
  // 1. An atomic upper bound is loop invariant
203
  //
204
  //    It must not be calculated at each loop iteration and can often even be
205
  //    hoisted out further by the loop invariant code motion.
206
  //
207
  // 2. OpenMP needs a loop invariant upper bound to calculate the number
208
  //    of loop iterations.
209
  //
210
  // 3. With the existing code, upper bounds have been easier to implement.
211
  __isl_give isl_ast_expr *getUpperBound(__isl_keep isl_ast_node *For,
212
                                         CmpInst::Predicate &Predicate);
213
214
  /// Return non-negative number of iterations in case of the following form
215
  /// of a loop and -1 otherwise.
216
  ///
217
  /// for (i = 0; i <= NumIter; i++) {
218
  ///   loop body;
219
  /// }
220
  ///
221
  /// NumIter is a non-negative integer value. Condition can have
222
  /// isl_ast_op_lt type.
223
  int getNumberOfIterations(__isl_keep isl_ast_node *For);
224
225
  /// Compute the values and loops referenced in this subtree.
226
  ///
227
  /// This function looks at all ScopStmts scheduled below the provided For node
228
  /// and finds the llvm::Value[s] and llvm::Loops[s] which are referenced but
229
  /// not locally defined.
230
  ///
231
  /// Values that can be synthesized or that are available as globals are
232
  /// considered locally defined.
233
  ///
234
  /// Loops that contain the scop or that are part of the scop are considered
235
  /// locally defined. Loops that are before the scop, but do not contain the
236
  /// scop itself are considered not locally defined.
237
  ///
238
  /// @param For    The node defining the subtree.
239
  /// @param Values A vector that will be filled with the Values referenced in
240
  ///               this subtree.
241
  /// @param Loops  A vector that will be filled with the Loops referenced in
242
  ///               this subtree.
243
  void getReferencesInSubtree(__isl_keep isl_ast_node *For,
244
                              SetVector<Value *> &Values,
245
                              SetVector<const Loop *> &Loops);
246
247
  /// Change the llvm::Value(s) used for code generation.
248
  ///
249
  /// When generating code certain values (e.g., references to induction
250
  /// variables or array base pointers) in the original code may be replaced by
251
  /// new values. This function allows to (partially) update the set of values
252
  /// used. A typical use case for this function is the case when we continue
253
  /// code generation in a subfunction/kernel function and need to explicitly
254
  /// pass down certain values.
255
  ///
256
  /// @param NewValues A map that maps certain llvm::Values to new llvm::Values.
257
  void updateValues(ValueMapT &NewValues);
258
259
  /// Generate code for a marker now.
260
  ///
261
  /// For mark nodes with an unknown name, we just forward the code generation
262
  /// to its child. This is currently the only behavior implemented, as there is
263
  /// currently not special handling for marker nodes implemented.
264
  ///
265
  /// @param Mark The node we generate code for.
266
  virtual void createMark(__isl_take isl_ast_node *Marker);
267
  virtual void createFor(__isl_take isl_ast_node *For);
268
269
  /// Set to remember materialized invariant loads.
270
  ///
271
  /// An invariant load is identified by its pointer (the SCEV) and its type.
272
  SmallSet<std::pair<const SCEV *, Type *>, 16> PreloadedPtrs;
273
274
  /// Preload the memory access at @p AccessRange with @p Build.
275
  ///
276
  /// @returns The preloaded value casted to type @p Ty
277
  Value *preloadUnconditionally(__isl_take isl_set *AccessRange,
278
                                isl_ast_build *Build, Instruction *AccInst);
279
280
  /// Preload the memory load access @p MA.
281
  ///
282
  /// If @p MA is not always executed it will be conditionally loaded and
283
  /// merged with undef from the same type. Hence, if @p MA is executed only
284
  /// under condition C then the preload code will look like this:
285
  ///
286
  /// MA_preload = undef;
287
  /// if (C)
288
  ///   MA_preload = load MA;
289
  /// use MA_preload
290
  Value *preloadInvariantLoad(const MemoryAccess &MA,
291
                              __isl_take isl_set *Domain);
292
293
  /// Preload the invariant access equivalence class @p IAClass
294
  ///
295
  /// This function will preload the representing load from @p IAClass and
296
  /// map all members of @p IAClass to that preloaded value, potentially casted
297
  /// to the required type.
298
  ///
299
  /// @returns False, iff a problem occurred and the load was not preloaded.
300
  bool preloadInvariantEquivClass(InvariantEquivClassTy &IAClass);
301
302
  void createForVector(__isl_take isl_ast_node *For, int VectorWidth);
303
  void createForSequential(__isl_take isl_ast_node *For, bool KnownParallel);
304
305
  /// Create LLVM-IR that executes a for node thread parallel.
306
  ///
307
  /// @param For The FOR isl_ast_node for which code is generated.
308
  void createForParallel(__isl_take isl_ast_node *For);
309
310
  /// Create new access functions for modified memory accesses.
311
  ///
312
  /// In case the access function of one of the memory references in the Stmt
313
  /// has been modified, we generate a new isl_ast_expr that reflects the
314
  /// newly modified access function and return a map that maps from the
315
  /// individual memory references in the statement (identified by their id)
316
  /// to these newly generated ast expressions.
317
  ///
318
  /// @param Stmt  The statement for which to (possibly) generate new access
319
  ///              functions.
320
  /// @param Node  The ast node corresponding to the statement for us to extract
321
  ///              the local schedule from.
322
  /// @return A new hash table that contains remappings from memory ids to new
323
  ///         access expressions.
324
  __isl_give isl_id_to_ast_expr *
325
  createNewAccesses(ScopStmt *Stmt, __isl_keep isl_ast_node *Node);
326
327
  /// Generate LLVM-IR that computes the values of the original induction
328
  /// variables in function of the newly generated loop induction variables.
329
  ///
330
  /// Example:
331
  ///
332
  ///   // Original
333
  ///   for i
334
  ///     for j
335
  ///       S(i)
336
  ///
337
  ///   Schedule: [i,j] -> [i+j, j]
338
  ///
339
  ///   // New
340
  ///   for c0
341
  ///     for c1
342
  ///       S(c0 - c1, c1)
343
  ///
344
  /// Assuming the original code consists of two loops which are
345
  /// transformed according to a schedule [i,j] -> [c0=i+j,c1=j]. The resulting
346
  /// ast models the original statement as a call expression where each argument
347
  /// is an expression that computes the old induction variables from the new
348
  /// ones, ordered such that the first argument computes the value of induction
349
  /// variable that was outermost in the original code.
350
  ///
351
  /// @param Expr The call expression that represents the statement.
352
  /// @param Stmt The statement that is called.
353
  /// @param LTS  The loop to SCEV map in which the mapping from the original
354
  ///             loop to a SCEV representing the new loop iv is added. This
355
  ///             mapping does not require an explicit induction variable.
356
  ///             Instead, we think in terms of an implicit induction variable
357
  ///             that counts the number of times a loop is executed. For each
358
  ///             original loop this count, expressed in function of the new
359
  ///             induction variables, is added to the LTS map.
360
  void createSubstitutions(__isl_take isl_ast_expr *Expr, ScopStmt *Stmt,
361
                           LoopToScevMapT &LTS);
362
  void createSubstitutionsVector(__isl_take isl_ast_expr *Expr, ScopStmt *Stmt,
363
                                 std::vector<LoopToScevMapT> &VLTS,
364
                                 std::vector<Value *> &IVS,
365
                                 __isl_take isl_id *IteratorID);
366
  virtual void createIf(__isl_take isl_ast_node *If);
367
  void createUserVector(__isl_take isl_ast_node *User,
368
                        std::vector<Value *> &IVS,
369
                        __isl_take isl_id *IteratorID,
370
                        __isl_take isl_union_map *Schedule);
371
  virtual void createUser(__isl_take isl_ast_node *User);
372
  virtual void createBlock(__isl_take isl_ast_node *Block);
373
374
  /// Get the schedule for a given AST node.
375
  ///
376
  /// This information is used to reason about parallelism of loops or the
377
  /// locality of memory accesses under a given schedule.
378
  ///
379
  /// @param Node The node we want to obtain the schedule for.
380
  /// @return Return an isl_union_map that maps from the statements executed
381
  ///         below this ast node to the scheduling vectors used to enumerate
382
  ///         them.
383
  ///
384
  virtual __isl_give isl_union_map *
385
  getScheduleForAstNode(__isl_take isl_ast_node *Node);
386
387
private:
388
  /// Create code for a copy statement.
389
  ///
390
  /// A copy statement is expected to have one read memory access and one write
391
  /// memory access (in this very order). Data is loaded from the location
392
  /// described by the read memory access and written to the location described
393
  /// by the write memory access. @p NewAccesses contains for each access
394
  /// the isl ast expression that describes the location accessed.
395
  ///
396
  /// @param Stmt The copy statement that contains the accesses.
397
  /// @param NewAccesses The hash table that contains remappings from memory
398
  ///                    ids to new access expressions.
399
  void generateCopyStmt(ScopStmt *Stmt,
400
                        __isl_keep isl_id_to_ast_expr *NewAccesses);
401
};
402
403
#endif // POLLY_ISL_NODE_BUILDER_H