Coverage Report

Created: 2017-11-21 03:47

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