Coverage Report

Created: 2017-06-23 12:40

/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_SCOP_BUILDER_H
18
#define POLLY_SCOP_BUILDER_H
19
20
#include "polly/ScopInfo.h"
21
22
namespace polly {
23
24
/// Build the Polly IR (Scop and ScopStmt) on a Region.
25
class ScopBuilder {
26
  //===-------------------------------------------------------------------===//
27
  ScopBuilder(const ScopBuilder &) = delete;
28
  const ScopBuilder &operator=(const ScopBuilder &) = delete;
29
30
  /// The AliasAnalysis to build AliasSetTracker.
31
  AliasAnalysis &AA;
32
33
  /// Target data for element size computing.
34
  const DataLayout &DL;
35
36
  /// DominatorTree to reason about guaranteed execution.
37
  DominatorTree &DT;
38
39
  /// LoopInfo for information about loops.
40
  LoopInfo &LI;
41
42
  /// Valid Regions for Scop
43
  ScopDetection &SD;
44
45
  /// The ScalarEvolution to help building Scop.
46
  ScalarEvolution &SE;
47
48
  /// Set of instructions that might read any memory location.
49
  SmallVector<Instruction *, 16> GlobalReads;
50
51
  /// Set of all accessed array base pointers.
52
  SmallSetVector<Value *, 16> ArrayBasePointers;
53
54
  // The Scop
55
  std::unique_ptr<Scop> scop;
56
57
  // Methods for pattern matching against Fortran code generated by dragonegg.
58
  // @{
59
60
  /// Try to match for the descriptor of a Fortran array whose allocation
61
  /// is not visible. That is, we can see the load/store into the memory, but
62
  /// we don't actually know where the memory is allocated. If ALLOCATE had been
63
  /// called on the Fortran array, then we will see the lowered malloc() call.
64
  /// If not, this is dubbed as an "invisible allocation".
65
  ///
66
  /// "<descriptor>" is the descriptor of the Fortran array.
67
  ///
68
  /// Pattern match for "@descriptor":
69
  ///  1. %mem = load double*, double** bitcast (%"struct.array1_real(kind=8)"*
70
  ///    <descriptor> to double**), align 32
71
  ///
72
  ///  2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>]
73
  ///  2 is optional because if you are writing to the 0th index, you don't
74
  ///     need a GEP.
75
  ///
76
  ///  3.1 store/load <memtype> <val>, <memtype>* %slot
77
  ///  3.2 store/load <memtype> <val>, <memtype>* %mem
78
  ///
79
  /// @see polly::MemoryAccess, polly::ScopArrayInfo
80
  ///
81
  /// @note assumes -polly-canonicalize has been run.
82
  ///
83
  /// @param Inst The LoadInst/StoreInst that accesses the memory.
84
  ///
85
  /// @returns Reference to <descriptor> on success, nullptr on failure.
86
  Value *findFADAllocationInvisible(MemAccInst Inst);
87
88
  /// Try to match for the descriptor of a Fortran array whose allocation
89
  /// call is visible. When we have a Fortran array, we try to look for a
90
  /// Fortran array where we can see the lowered ALLOCATE call. ALLOCATE
91
  /// is materialized as a malloc(...) which we pattern match for.
92
  ///
93
  /// Pattern match for "%untypedmem":
94
  ///  1. %untypedmem = i8* @malloc(...)
95
  ///
96
  ///  2. %typedmem = bitcast i8* %untypedmem to <memtype>
97
  ///
98
  ///  3. [%slot = getelementptr inbounds i8, i8* %typedmem, i64 <index>]
99
  ///  3 is optional because if you are writing to the 0th index, you don't
100
  ///     need a GEP.
101
  ///
102
  ///  4.1 store/load <memtype> <val>, <memtype>* %slot, align 8
103
  ///  4.2 store/load <memtype> <val>, <memtype>* %mem, align 8
104
  ///
105
  /// @see polly::MemoryAccess, polly::ScopArrayInfo
106
  ///
107
  /// @note assumes -polly-canonicalize has been run.
108
  ///
109
  /// @param Inst The LoadInst/StoreInst that accesses the memory.
110
  ///
111
  /// @returns Reference to %untypedmem on success, nullptr on failure.
112
  Value *findFADAllocationVisible(MemAccInst Inst);
113
114
  // @}
115
116
  // Build the SCoP for Region @p R.
117
  void buildScop(Region &R, AssumptionCache &AC);
118
119
  /// Try to build a multi-dimensional fixed sized MemoryAccess from the
120
  /// Load/Store instruction.
121
  ///
122
  /// @param Inst       The Load/Store instruction that access the memory
123
  /// @param Stmt       The parent statement of the instruction
124
  ///
125
  /// @returns True if the access could be built, False otherwise.
126
  bool buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt);
127
128
  /// Try to build a multi-dimensional parametric sized MemoryAccess.
129
  ///        from the Load/Store instruction.
130
  ///
131
  /// @param Inst       The Load/Store instruction that access the memory
132
  /// @param Stmt       The parent statement of the instruction
133
  ///
134
  /// @returns True if the access could be built, False otherwise.
135
  bool buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt);
136
137
  /// Try to build a MemoryAccess for a memory intrinsic.
138
  ///
139
  /// @param Inst       The instruction that access the memory
140
  /// @param Stmt       The parent statement of the instruction
141
  ///
142
  /// @returns True if the access could be built, False otherwise.
143
  bool buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt);
144
145
  /// Try to build a MemoryAccess for a call instruction.
146
  ///
147
  /// @param Inst       The call instruction that access the memory
148
  /// @param Stmt       The parent statement of the instruction
149
  ///
150
  /// @returns True if the access could be built, False otherwise.
151
  bool buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt);
152
153
  /// Build a single-dimensional parametric sized MemoryAccess
154
  ///        from the Load/Store instruction.
155
  ///
156
  /// @param Inst       The Load/Store instruction that access the memory
157
  /// @param Stmt       The parent statement of the instruction
158
  void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt);
159
160
  /// Build an instance of MemoryAccess from the Load/Store instruction.
161
  ///
162
  /// @param Inst       The Load/Store instruction that access the memory
163
  /// @param Stmt       The parent statement of the instruction
164
  void buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt);
165
166
  /// Analyze and extract the cross-BB scalar dependences (or, dataflow
167
  /// dependencies) of an instruction.
168
  ///
169
  /// @param Inst    The instruction to be analyzed.
170
  void buildScalarDependences(Instruction *Inst);
171
172
  /// Build the escaping dependences for @p Inst.
173
  ///
174
  /// Search for uses of the llvm::Value defined by @p Inst that are not
175
  /// within the SCoP. If there is such use, add a SCALAR WRITE such that
176
  /// it is available after the SCoP as escaping value.
177
  ///
178
  /// @param Inst The instruction to be analyzed.
179
  void buildEscapingDependences(Instruction *Inst);
180
181
  /// Create MemoryAccesses for the given PHI node in the given region.
182
  ///
183
  /// @param PHI                The PHI node to be handled
184
  /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
185
  /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
186
  void buildPHIAccesses(PHINode *PHI, Region *NonAffineSubRegion,
187
                        bool IsExitBlock = false);
188
189
  /// Build the access functions for the subregion @p SR.
190
  ///
191
  /// @param SR           A subregion of @p R.
192
  /// @param InsnToMemAcc The Instruction to MemoryAccess mapping.
193
  void buildAccessFunctions(Region &SR);
194
195
  /// Create ScopStmt for all BBs and non-affine subregions of @p SR.
196
  ///
197
  /// @param SR A subregion of @p R.
198
  ///
199
  /// Some of the statements might be optimized away later when they do not
200
  /// access any memory and thus have no effect.
201
  void buildStmts(Region &SR);
202
203
  /// Build the access functions for the basic block @p BB.
204
  ///
205
  /// @param BB                 A basic block in @p R.
206
  /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
207
  /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
208
  void buildAccessFunctions(BasicBlock &BB,
209
                            Region *NonAffineSubRegion = nullptr,
210
                            bool IsExitBlock = false);
211
212
  /// Create a new MemoryAccess object and add it to #AccFuncMap.
213
  ///
214
  /// @param BB          The block where the access takes place.
215
  /// @param Inst        The instruction doing the access. It is not necessarily
216
  ///                    inside @p BB.
217
  /// @param AccType     The kind of access.
218
  /// @param BaseAddress The accessed array's base address.
219
  /// @param ElemType    The type of the accessed array elements.
220
  /// @param Affine      Whether all subscripts are affine expressions.
221
  /// @param AccessValue Value read or written.
222
  /// @param Subscripts  Access subscripts per dimension.
223
  /// @param Sizes       The array dimension's sizes.
224
  /// @param Kind        The kind of memory accessed.
225
  ///
226
  /// @return The created MemoryAccess, or nullptr if the access is not within
227
  ///         the SCoP.
228
  MemoryAccess *addMemoryAccess(BasicBlock *BB, Instruction *Inst,
229
                                MemoryAccess::AccessType AccType,
230
                                Value *BaseAddress, Type *ElemType, bool Affine,
231
                                Value *AccessValue,
232
                                ArrayRef<const SCEV *> Subscripts,
233
                                ArrayRef<const SCEV *> Sizes, MemoryKind Kind);
234
235
  /// Create a MemoryAccess that represents either a LoadInst or
236
  /// StoreInst.
237
  ///
238
  /// @param MemAccInst  The LoadInst or StoreInst.
239
  /// @param AccType     The kind of access.
240
  /// @param BaseAddress The accessed array's base address.
241
  /// @param ElemType    The type of the accessed array elements.
242
  /// @param IsAffine    Whether all subscripts are affine expressions.
243
  /// @param Subscripts  Access subscripts per dimension.
244
  /// @param Sizes       The array dimension's sizes.
245
  /// @param AccessValue Value read or written.
246
  ///
247
  /// @see MemoryKind
248
  void addArrayAccess(MemAccInst MemAccInst, MemoryAccess::AccessType AccType,
249
                      Value *BaseAddress, Type *ElemType, bool IsAffine,
250
                      ArrayRef<const SCEV *> Subscripts,
251
                      ArrayRef<const SCEV *> Sizes, Value *AccessValue);
252
253
  /// Create a MemoryAccess for writing an llvm::Instruction.
254
  ///
255
  /// The access will be created at the position of @p Inst.
256
  ///
257
  /// @param Inst The instruction to be written.
258
  ///
259
  /// @see ensureValueRead()
260
  /// @see MemoryKind
261
  void ensureValueWrite(Instruction *Inst);
262
263
  /// Ensure an llvm::Value is available in the BB's statement, creating a
264
  /// MemoryAccess for reloading it if necessary.
265
  ///
266
  /// @param V      The value expected to be loaded.
267
  /// @param UserBB Where to reload the value.
268
  ///
269
  /// @see ensureValueStore()
270
  /// @see MemoryKind
271
  void ensureValueRead(Value *V, BasicBlock *UserBB);
272
273
  /// Create a write MemoryAccess for the incoming block of a phi node.
274
  ///
275
  /// Each of the incoming blocks write their incoming value to be picked in the
276
  /// phi's block.
277
  ///
278
  /// @param PHI           PHINode under consideration.
279
  /// @param IncomingBlock Some predecessor block.
280
  /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
281
  /// @param IsExitBlock   When true, uses the .s2a alloca instead of the
282
  ///                      .phiops one. Required for values escaping through a
283
  ///                      PHINode in the SCoP region's exit block.
284
  /// @see addPHIReadAccess()
285
  /// @see MemoryKind
286
  void ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
287
                      Value *IncomingValue, bool IsExitBlock);
288
289
  /// Create a MemoryAccess for reading the value of a phi.
290
  ///
291
  /// The modeling assumes that all incoming blocks write their incoming value
292
  /// to the same location. Thus, this access will read the incoming block's
293
  /// value as instructed by this @p PHI.
294
  ///
295
  /// @param PHI PHINode under consideration; the READ access will be added
296
  /// here.
297
  ///
298
  /// @see ensurePHIWrite()
299
  /// @see MemoryKind
300
  void addPHIReadAccess(PHINode *PHI);
301
302
public:
303
  explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
304
                       const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
305
                       ScopDetection &SD, ScalarEvolution &SE);
306
1.02k
  ~ScopBuilder() {}
307
308
  /// Try to build the Polly IR of static control part on the current
309
  /// SESE-Region.
310
  ///
311
  /// @return Give up the ownership of the scop object or static control part
312
  ///         for the region
313
1.02k
  std::unique_ptr<Scop> getScop() { return std::move(scop); }
314
};
315
316
} // end namespace polly
317
318
namespace llvm {
319
class PassRegistry;
320
void initializeScopInfoRegionPassPass(llvm::PassRegistry &);
321
void initializeScopInfoWrapperPassPass(llvm::PassRegistry &);
322
} // namespace llvm
323
324
#endif