Coverage Report

Created: 2019-02-20 07:29

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