Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/include/polly/ScopBuilder.h
Line
Count
Source
1
//===- polly/ScopBuilder.h --------------------------------------*- 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
// Create a polyhedral description for a static control flow region.
11
//
12
// The pass creates a polyhedral description of the Scops detected by the SCoP
13
// detection derived from their LLVM-IR code.
14
//
15
//===----------------------------------------------------------------------===//
16
17
#ifndef POLLY_SCOPBUILDER_H
18
#define POLLY_SCOPBUILDER_H
19
20
#include "polly/ScopInfo.h"
21
#include "polly/Support/ScopHelper.h"
22
#include "llvm/ADT/ArrayRef.h"
23
#include "llvm/ADT/SetVector.h"
24
#include "llvm/ADT/SmallVector.h"
25
#include <algorithm>
26
#include <memory>
27
#include <utility>
28
29
namespace llvm {
30
31
class AssumptionCache;
32
class BasicBlock;
33
class DataLayout;
34
class DominatorTree;
35
class Instruction;
36
class LoopInfo;
37
class PassRegistry;
38
class PHINode;
39
class Region;
40
class ScalarEvolution;
41
class SCEV;
42
class Type;
43
class Value;
44
45
void initializeScopInfoRegionPassPass(PassRegistry &);
46
void initializeScopInfoWrapperPassPass(PassRegistry &);
47
48
} // end namespace llvm
49
50
namespace polly {
51
52
class ScopDetection;
53
54
/// Command line switch whether to model read-only accesses.
55
extern bool ModelReadOnlyScalars;
56
57
/// Build the Polly IR (Scop and ScopStmt) on a Region.
58
class ScopBuilder {
59
  /// The AliasAnalysis to build AliasSetTracker.
60
  AliasAnalysis &AA;
61
62
  /// Target data for element size computing.
63
  const DataLayout &DL;
64
65
  /// DominatorTree to reason about guaranteed execution.
66
  DominatorTree &DT;
67
68
  /// LoopInfo for information about loops.
69
  LoopInfo &LI;
70
71
  /// Valid Regions for Scop
72
  ScopDetection &SD;
73
74
  /// The ScalarEvolution to help building Scop.
75
  ScalarEvolution &SE;
76
77
  /// Set of instructions that might read any memory location.
78
  SmallVector<std::pair<ScopStmt *, Instruction *>, 16> GlobalReads;
79
80
  /// Set of all accessed array base pointers.
81
  SmallSetVector<Value *, 16> ArrayBasePointers;
82
83
  // The Scop
84
  std::unique_ptr<Scop> scop;
85
86
  // Methods for pattern matching against Fortran code generated by dragonegg.
87
  // @{
88
89
  /// Try to match for the descriptor of a Fortran array whose allocation
90
  /// is not visible. That is, we can see the load/store into the memory, but
91
  /// we don't actually know where the memory is allocated. If ALLOCATE had been
92
  /// called on the Fortran array, then we will see the lowered malloc() call.
93
  /// If not, this is dubbed as an "invisible allocation".
94
  ///
95
  /// "<descriptor>" is the descriptor of the Fortran array.
96
  ///
97
  /// Pattern match for "@descriptor":
98
  ///  1. %mem = load double*, double** bitcast (%"struct.array1_real(kind=8)"*
99
  ///    <descriptor> to double**), align 32
100
  ///
101
  ///  2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>]
102
  ///  2 is optional because if you are writing to the 0th index, you don't
103
  ///     need a GEP.
104
  ///
105
  ///  3.1 store/load <memtype> <val>, <memtype>* %slot
106
  ///  3.2 store/load <memtype> <val>, <memtype>* %mem
107
  ///
108
  /// @see polly::MemoryAccess, polly::ScopArrayInfo
109
  ///
110
  /// @note assumes -polly-canonicalize has been run.
111
  ///
112
  /// @param Inst The LoadInst/StoreInst that accesses the memory.
113
  ///
114
  /// @returns Reference to <descriptor> on success, nullptr on failure.
115
  Value *findFADAllocationInvisible(MemAccInst Inst);
116
117
  /// Try to match for the descriptor of a Fortran array whose allocation
118
  /// call is visible. When we have a Fortran array, we try to look for a
119
  /// Fortran array where we can see the lowered ALLOCATE call. ALLOCATE
120
  /// is materialized as a malloc(...) which we pattern match for.
121
  ///
122
  /// Pattern match for "%untypedmem":
123
  ///  1. %untypedmem = i8* @malloc(...)
124
  ///
125
  ///  2. %typedmem = bitcast i8* %untypedmem to <memtype>
126
  ///
127
  ///  3. [%slot = getelementptr inbounds i8, i8* %typedmem, i64 <index>]
128
  ///  3 is optional because if you are writing to the 0th index, you don't
129
  ///     need a GEP.
130
  ///
131
  ///  4.1 store/load <memtype> <val>, <memtype>* %slot, align 8
132
  ///  4.2 store/load <memtype> <val>, <memtype>* %mem, align 8
133
  ///
134
  /// @see polly::MemoryAccess, polly::ScopArrayInfo
135
  ///
136
  /// @note assumes -polly-canonicalize has been run.
137
  ///
138
  /// @param Inst The LoadInst/StoreInst that accesses the memory.
139
  ///
140
  /// @returns Reference to %untypedmem on success, nullptr on failure.
141
  Value *findFADAllocationVisible(MemAccInst Inst);
142
143
  // @}
144
145
  // Build the SCoP for Region @p R.
146
  void buildScop(Region &R, AssumptionCache &AC,
147
                 OptimizationRemarkEmitter &ORE);
148
149
  /// Try to build a multi-dimensional fixed sized MemoryAccess from the
150
  /// Load/Store instruction.
151
  ///
152
  /// @param Inst       The Load/Store instruction that access the memory
153
  /// @param Stmt       The parent statement of the instruction
154
  ///
155
  /// @returns True if the access could be built, False otherwise.
156
  bool buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt);
157
158
  /// Try to build a multi-dimensional parametric sized MemoryAccess.
159
  ///        from the Load/Store instruction.
160
  ///
161
  /// @param Inst       The Load/Store instruction that access the memory
162
  /// @param Stmt       The parent statement of the instruction
163
  ///
164
  /// @returns True if the access could be built, False otherwise.
165
  bool buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt);
166
167
  /// Try to build a MemoryAccess for a memory intrinsic.
168
  ///
169
  /// @param Inst       The instruction that access the memory
170
  /// @param Stmt       The parent statement of the instruction
171
  ///
172
  /// @returns True if the access could be built, False otherwise.
173
  bool buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt);
174
175
  /// Try to build a MemoryAccess for a call instruction.
176
  ///
177
  /// @param Inst       The call instruction that access the memory
178
  /// @param Stmt       The parent statement of the instruction
179
  ///
180
  /// @returns True if the access could be built, False otherwise.
181
  bool buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt);
182
183
  /// Build a single-dimensional parametric sized MemoryAccess
184
  ///        from the Load/Store instruction.
185
  ///
186
  /// @param Inst       The Load/Store instruction that access the memory
187
  /// @param Stmt       The parent statement of the instruction
188
  void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt);
189
190
  /// Build an instance of MemoryAccess from the Load/Store instruction.
191
  ///
192
  /// @param Inst       The Load/Store instruction that access the memory
193
  /// @param Stmt       The parent statement of the instruction
194
  void buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt);
195
196
  /// Analyze and extract the cross-BB scalar dependences (or, dataflow
197
  /// dependencies) of an instruction.
198
  ///
199
  /// @param UserStmt The statement @p Inst resides in.
200
  /// @param Inst     The instruction to be analyzed.
201
  void buildScalarDependences(ScopStmt *UserStmt, Instruction *Inst);
202
203
  /// Build the escaping dependences for @p Inst.
204
  ///
205
  /// Search for uses of the llvm::Value defined by @p Inst that are not
206
  /// within the SCoP. If there is such use, add a SCALAR WRITE such that
207
  /// it is available after the SCoP as escaping value.
208
  ///
209
  /// @param Inst The instruction to be analyzed.
210
  void buildEscapingDependences(Instruction *Inst);
211
212
  /// Create MemoryAccesses for the given PHI node in the given region.
213
  ///
214
  /// @param PHIStmt            The statement @p PHI resides in.
215
  /// @param PHI                The PHI node to be handled
216
  /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
217
  /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
218
  void buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
219
                        Region *NonAffineSubRegion, bool IsExitBlock = false);
220
221
  /// Build the access functions for the subregion @p SR.
222
  void buildAccessFunctions();
223
224
  /// Should an instruction be modeled in a ScopStmt.
225
  ///
226
  /// @param Inst The instruction to check.
227
  /// @param L    The loop in which context the instruction is looked at.
228
  ///
229
  /// @returns True if the instruction should be modeled.
230
  bool shouldModelInst(Instruction *Inst, Loop *L);
231
232
  /// Create ScopStmt for all BBs and non-affine subregions of @p SR.
233
  ///
234
  /// @param SR A subregion of @p R.
235
  ///
236
  /// Some of the statements might be optimized away later when they do not
237
  /// access any memory and thus have no effect.
238
  void buildStmts(Region &SR);
239
240
  /// Build the access functions for the statement @p Stmt in or represented by
241
  /// @p BB.
242
  ///
243
  /// @param Stmt               Statement to add MemoryAccesses to.
244
  /// @param BB                 A basic block in @p R.
245
  /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
246
  /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
247
  void buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
248
                            Region *NonAffineSubRegion = nullptr,
249
                            bool IsExitBlock = false);
250
251
  /// Create a new MemoryAccess object and add it to #AccFuncMap.
252
  ///
253
  /// @param Stmt        The statement where the access takes place.
254
  /// @param Inst        The instruction doing the access. It is not necessarily
255
  ///                    inside @p BB.
256
  /// @param AccType     The kind of access.
257
  /// @param BaseAddress The accessed array's base address.
258
  /// @param ElemType    The type of the accessed array elements.
259
  /// @param Affine      Whether all subscripts are affine expressions.
260
  /// @param AccessValue Value read or written.
261
  /// @param Subscripts  Access subscripts per dimension.
262
  /// @param Sizes       The array dimension's sizes.
263
  /// @param Kind        The kind of memory accessed.
264
  ///
265
  /// @return The created MemoryAccess, or nullptr if the access is not within
266
  ///         the SCoP.
267
  MemoryAccess *addMemoryAccess(ScopStmt *Stmt, Instruction *Inst,
268
                                MemoryAccess::AccessType AccType,
269
                                Value *BaseAddress, Type *ElemType, bool Affine,
270
                                Value *AccessValue,
271
                                ArrayRef<const SCEV *> Subscripts,
272
                                ArrayRef<const SCEV *> Sizes, MemoryKind Kind);
273
274
  /// Create a MemoryAccess that represents either a LoadInst or
275
  /// StoreInst.
276
  ///
277
  /// @param Stmt        The statement to add the MemoryAccess to.
278
  /// @param MemAccInst  The LoadInst or StoreInst.
279
  /// @param AccType     The kind of access.
280
  /// @param BaseAddress The accessed array's base address.
281
  /// @param ElemType    The type of the accessed array elements.
282
  /// @param IsAffine    Whether all subscripts are affine expressions.
283
  /// @param Subscripts  Access subscripts per dimension.
284
  /// @param Sizes       The array dimension's sizes.
285
  /// @param AccessValue Value read or written.
286
  ///
287
  /// @see MemoryKind
288
  void addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst,
289
                      MemoryAccess::AccessType AccType, Value *BaseAddress,
290
                      Type *ElemType, bool IsAffine,
291
                      ArrayRef<const SCEV *> Subscripts,
292
                      ArrayRef<const SCEV *> Sizes, Value *AccessValue);
293
294
  /// Create a MemoryAccess for writing an llvm::Instruction.
295
  ///
296
  /// The access will be created at the position of @p Inst.
297
  ///
298
  /// @param Inst The instruction to be written.
299
  ///
300
  /// @see ensureValueRead()
301
  /// @see MemoryKind
302
  void ensureValueWrite(Instruction *Inst);
303
304
  /// Ensure an llvm::Value is available in the BB's statement, creating a
305
  /// MemoryAccess for reloading it if necessary.
306
  ///
307
  /// @param V        The value expected to be loaded.
308
  /// @param UserStmt Where to reload the value.
309
  ///
310
  /// @see ensureValueStore()
311
  /// @see MemoryKind
312
  void ensureValueRead(Value *V, ScopStmt *UserStmt);
313
314
  /// Create a write MemoryAccess for the incoming block of a phi node.
315
  ///
316
  /// Each of the incoming blocks write their incoming value to be picked in the
317
  /// phi's block.
318
  ///
319
  /// @param PHI           PHINode under consideration.
320
  /// @param IncomingStmt  The statement to add the MemoryAccess to.
321
  /// @param IncomingBlock Some predecessor block.
322
  /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
323
  /// @param IsExitBlock   When true, uses the .s2a alloca instead of the
324
  ///                      .phiops one. Required for values escaping through a
325
  ///                      PHINode in the SCoP region's exit block.
326
  /// @see addPHIReadAccess()
327
  /// @see MemoryKind
328
  void ensurePHIWrite(PHINode *PHI, ScopStmt *IncomintStmt,
329
                      BasicBlock *IncomingBlock, Value *IncomingValue,
330
                      bool IsExitBlock);
331
332
  /// Create a MemoryAccess for reading the value of a phi.
333
  ///
334
  /// The modeling assumes that all incoming blocks write their incoming value
335
  /// to the same location. Thus, this access will read the incoming block's
336
  /// value as instructed by this @p PHI.
337
  ///
338
  /// @param PHIStmt Statement @p PHI resides in.
339
  /// @param PHI     PHINode under consideration; the READ access will be added
340
  ///                here.
341
  ///
342
  /// @see ensurePHIWrite()
343
  /// @see MemoryKind
344
  void addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI);
345
346
  /// Build the domain of @p Stmt.
347
  void buildDomain(ScopStmt &Stmt);
348
349
  /// Fill NestLoops with loops surrounding @p Stmt.
350
  void collectSurroundingLoops(ScopStmt &Stmt);
351
352
  /// Check for reductions in @p Stmt.
353
  ///
354
  /// Iterate over all store memory accesses and check for valid binary
355
  /// reduction like chains. For all candidates we check if they have the same
356
  /// base address and there are no other accesses which overlap with them. The
357
  /// base address check rules out impossible reductions candidates early. The
358
  /// overlap check, together with the "only one user" check in
359
  /// collectCandiateReductionLoads, guarantees that none of the intermediate
360
  /// results will escape during execution of the loop nest. We basically check
361
  /// here that no other memory access can access the same memory as the
362
  /// potential reduction.
363
  void checkForReductions(ScopStmt &Stmt);
364
365
  /// Collect loads which might form a reduction chain with @p StoreMA.
366
  ///
367
  /// Check if the stored value for @p StoreMA is a binary operator with one or
368
  /// two loads as operands. If the binary operand is commutative & associative,
369
  /// used only once (by @p StoreMA) and its load operands are also used only
370
  /// once, we have found a possible reduction chain. It starts at an operand
371
  /// load and includes the binary operator and @p StoreMA.
372
  ///
373
  /// Note: We allow only one use to ensure the load and binary operator cannot
374
  ///       escape this block or into any other store except @p StoreMA.
375
  void collectCandiateReductionLoads(MemoryAccess *StoreMA,
376
                                     SmallVectorImpl<MemoryAccess *> &Loads);
377
378
  /// Build the access relation of all memory accesses of @p Stmt.
379
  void buildAccessRelations(ScopStmt &Stmt);
380
381
public:
382
  explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
383
                       const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
384
                       ScopDetection &SD, ScalarEvolution &SE,
385
                       OptimizationRemarkEmitter &ORE);
386
  ScopBuilder(const ScopBuilder &) = delete;
387
  ScopBuilder &operator=(const ScopBuilder &) = delete;
388
1.14k
  ~ScopBuilder() = default;
389
390
  /// Try to build the Polly IR of static control part on the current
391
  /// SESE-Region.
392
  ///
393
  /// @return Give up the ownership of the scop object or static control part
394
  ///         for the region
395
1.14k
  std::unique_ptr<Scop> getScop() { return std::move(scop); }
396
};
397
398
} // end namespace polly
399
400
#endif // POLLY_SCOPBUILDER_H