Coverage Report

Created: 2017-03-28 09:59

/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
  // Build the SCoP for Region @p R.
58
  void buildScop(Region &R, AssumptionCache &AC);
59
60
  /// Try to build a multi-dimensional fixed sized MemoryAccess from the
61
  /// Load/Store instruction.
62
  ///
63
  /// @param Inst       The Load/Store instruction that access the memory
64
  /// @param Stmt       The parent statement of the instruction
65
  ///
66
  /// @returns True if the access could be built, False otherwise.
67
  bool buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt);
68
69
  /// Try to build a multi-dimensional parameteric sized MemoryAccess.
70
  ///        from the Load/Store instruction.
71
  ///
72
  /// @param Inst       The Load/Store instruction that access the memory
73
  /// @param Stmt       The parent statement of the instruction
74
  ///
75
  /// @returns True if the access could be built, False otherwise.
76
  bool buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt);
77
78
  /// Try to build a MemoryAccess for a memory intrinsic.
79
  ///
80
  /// @param Inst       The instruction that access the memory
81
  /// @param Stmt       The parent statement of the instruction
82
  ///
83
  /// @returns True if the access could be built, False otherwise.
84
  bool buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt);
85
86
  /// Try to build a MemoryAccess for a call instruction.
87
  ///
88
  /// @param Inst       The call instruction that access the memory
89
  /// @param Stmt       The parent statement of the instruction
90
  ///
91
  /// @returns True if the access could be built, False otherwise.
92
  bool buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt);
93
94
  /// Build a single-dimensional parametric sized MemoryAccess
95
  ///        from the Load/Store instruction.
96
  ///
97
  /// @param Inst       The Load/Store instruction that access the memory
98
  /// @param Stmt       The parent statement of the instruction
99
  void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt);
100
101
  /// Build an instance of MemoryAccess from the Load/Store instruction.
102
  ///
103
  /// @param Inst       The Load/Store instruction that access the memory
104
  /// @param Stmt       The parent statement of the instruction
105
  void buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt);
106
107
  /// Analyze and extract the cross-BB scalar dependences (or, dataflow
108
  /// dependencies) of an instruction.
109
  ///
110
  /// @param Inst    The instruction to be analyzed.
111
  void buildScalarDependences(Instruction *Inst);
112
113
  /// Build the escaping dependences for @p Inst.
114
  ///
115
  /// Search for uses of the llvm::Value defined by @p Inst that are not
116
  /// within the SCoP. If there is such use, add a SCALAR WRITE such that
117
  /// it is available after the SCoP as escaping value.
118
  ///
119
  /// @param Inst The instruction to be analyzed.
120
  void buildEscapingDependences(Instruction *Inst);
121
122
  /// Create MemoryAccesses for the given PHI node in the given region.
123
  ///
124
  /// @param PHI                The PHI node to be handled
125
  /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
126
  /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
127
  void buildPHIAccesses(PHINode *PHI, Region *NonAffineSubRegion,
128
                        bool IsExitBlock = false);
129
130
  /// Build the access functions for the subregion @p SR.
131
  ///
132
  /// @param SR           A subregion of @p R.
133
  /// @param InsnToMemAcc The Instruction to MemoryAccess mapping.
134
  void buildAccessFunctions(Region &SR);
135
136
  /// Create ScopStmt for all BBs and non-affine subregions of @p SR.
137
  ///
138
  /// @param SR A subregion of @p R.
139
  ///
140
  /// Some of the statments might be optimized away later when they do not
141
  /// access any memory and thus have no effect.
142
  void buildStmts(Region &SR);
143
144
  /// Build the access functions for the basic block @p BB.
145
  ///
146
  /// @param BB                 A basic block in @p R.
147
  /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
148
  /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
149
  void buildAccessFunctions(BasicBlock &BB,
150
                            Region *NonAffineSubRegion = nullptr,
151
                            bool IsExitBlock = false);
152
153
  /// Create a new MemoryAccess object and add it to #AccFuncMap.
154
  ///
155
  /// @param BB          The block where the access takes place.
156
  /// @param Inst        The instruction doing the access. It is not necessarily
157
  ///                    inside @p BB.
158
  /// @param AccType     The kind of access.
159
  /// @param BaseAddress The accessed array's base address.
160
  /// @param ElemType    The type of the accessed array elements.
161
  /// @param Affine      Whether all subscripts are affine expressions.
162
  /// @param AccessValue Value read or written.
163
  /// @param Subscripts  Access subscripts per dimension.
164
  /// @param Sizes       The array dimension's sizes.
165
  /// @param Kind        The kind of memory accessed.
166
  ///
167
  /// @return The created MemoryAccess, or nullptr if the access is not within
168
  ///         the SCoP.
169
  MemoryAccess *addMemoryAccess(BasicBlock *BB, Instruction *Inst,
170
                                MemoryAccess::AccessType AccType,
171
                                Value *BaseAddress, Type *ElemType, bool Affine,
172
                                Value *AccessValue,
173
                                ArrayRef<const SCEV *> Subscripts,
174
                                ArrayRef<const SCEV *> Sizes, MemoryKind Kind);
175
176
  /// Create a MemoryAccess that represents either a LoadInst or
177
  /// StoreInst.
178
  ///
179
  /// @param MemAccInst  The LoadInst or StoreInst.
180
  /// @param AccType     The kind of access.
181
  /// @param BaseAddress The accessed array's base address.
182
  /// @param ElemType    The type of the accessed array elements.
183
  /// @param IsAffine    Whether all subscripts are affine expressions.
184
  /// @param Subscripts  Access subscripts per dimension.
185
  /// @param Sizes       The array dimension's sizes.
186
  /// @param AccessValue Value read or written.
187
  ///
188
  /// @see MemoryKind
189
  void addArrayAccess(MemAccInst MemAccInst, MemoryAccess::AccessType AccType,
190
                      Value *BaseAddress, Type *ElemType, bool IsAffine,
191
                      ArrayRef<const SCEV *> Subscripts,
192
                      ArrayRef<const SCEV *> Sizes, Value *AccessValue);
193
194
  /// Create a MemoryAccess for writing an llvm::Instruction.
195
  ///
196
  /// The access will be created at the position of @p Inst.
197
  ///
198
  /// @param Inst The instruction to be written.
199
  ///
200
  /// @see ensureValueRead()
201
  /// @see MemoryKind
202
  void ensureValueWrite(Instruction *Inst);
203
204
  /// Ensure an llvm::Value is available in the BB's statement, creating a
205
  /// MemoryAccess for reloading it if necessary.
206
  ///
207
  /// @param V      The value expected to be loaded.
208
  /// @param UserBB Where to reload the value.
209
  ///
210
  /// @see ensureValueStore()
211
  /// @see MemoryKind
212
  void ensureValueRead(Value *V, BasicBlock *UserBB);
213
214
  /// Create a write MemoryAccess for the incoming block of a phi node.
215
  ///
216
  /// Each of the incoming blocks write their incoming value to be picked in the
217
  /// phi's block.
218
  ///
219
  /// @param PHI           PHINode under consideration.
220
  /// @param IncomingBlock Some predecessor block.
221
  /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
222
  /// @param IsExitBlock   When true, uses the .s2a alloca instead of the
223
  ///                      .phiops one. Required for values escaping through a
224
  ///                      PHINode in the SCoP region's exit block.
225
  /// @see addPHIReadAccess()
226
  /// @see MemoryKind
227
  void ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
228
                      Value *IncomingValue, bool IsExitBlock);
229
230
  /// Create a MemoryAccess for reading the value of a phi.
231
  ///
232
  /// The modeling assumes that all incoming blocks write their incoming value
233
  /// to the same location. Thus, this access will read the incoming block's
234
  /// value as instructed by this @p PHI.
235
  ///
236
  /// @param PHI PHINode under consideration; the READ access will be added
237
  /// here.
238
  ///
239
  /// @see ensurePHIWrite()
240
  /// @see MemoryKind
241
  void addPHIReadAccess(PHINode *PHI);
242
243
public:
244
  explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
245
                       const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
246
                       ScopDetection &SD, ScalarEvolution &SE);
247
934
  ~ScopBuilder() {}
248
249
  /// Try to build the Polly IR of static control part on the current
250
  /// SESE-Region.
251
  ///
252
  /// @return Give up the ownership of the scop object or static control part
253
  ///         for the region
254
934
  std::unique_ptr<Scop> getScop() { return std::move(scop); }
255
};
256
257
} // end namespace polly
258
259
namespace llvm {
260
class PassRegistry;
261
void initializeScopInfoRegionPassPass(llvm::PassRegistry &);
262
void initializeScopInfoWrapperPassPass(llvm::PassRegistry &);
263
} // namespace llvm
264
265
#endif