1 //===- polly/ScopBuilder.h -------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Create a polyhedral description for a static control flow region.
12 // The pass creates a polyhedral description of the Scops detected by the SCoP
13 // detection derived from their LLVM-IR code.
15 //===----------------------------------------------------------------------===//
17 #ifndef POLLY_SCOP_BUILDER_H
18 #define POLLY_SCOP_BUILDER_H
20 #include "polly/ScopInfo.h"
24 /// Build the Polly IR (Scop and ScopStmt) on a Region.
26 //===-------------------------------------------------------------------===//
27 ScopBuilder(const ScopBuilder
&) = delete;
28 const ScopBuilder
&operator=(const ScopBuilder
&) = delete;
30 /// The AliasAnalysis to build AliasSetTracker.
33 /// Target data for element size computing.
36 /// DominatorTree to reason about guaranteed execution.
39 /// LoopInfo for information about loops.
42 /// Valid Regions for Scop
45 /// The ScalarEvolution to help building Scop.
48 /// Set of instructions that might read any memory location.
49 SmallVector
<Instruction
*, 16> GlobalReads
;
51 /// Set of all accessed array base pointers.
52 SmallSetVector
<Value
*, 16> ArrayBasePointers
;
55 std::unique_ptr
<Scop
> scop
;
57 // Methods for pattern matching against Fortran code generated by dragonegg.
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".
66 /// "<descriptor>" is the descriptor of the Fortran array.
68 /// Pattern match for "@descriptor":
69 /// 1. %mem = load double*, double** bitcast (%"struct.array1_real(kind=8)"*
70 /// <descriptor> to double**), align 32
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
76 /// 3.1 store/load <memtype> <val>, <memtype>* %slot
77 /// 3.2 store/load <memtype> <val>, <memtype>* %mem
79 /// @see polly::MemoryAccess, polly::ScopArrayInfo
81 /// @note assumes -polly-canonicalize has been run.
83 /// @param Inst The LoadInst/StoreInst that accesses the memory.
85 /// @returns Reference to <descriptor> on success, nullptr on failure.
86 Value
*findFADAllocationInvisible(MemAccInst Inst
);
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.
93 /// Pattern match for "%untypedmem":
94 /// 1. %untypedmem = i8* @malloc(...)
96 /// 2. %typedmem = bitcast i8* %untypedmem to <memtype>
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
102 /// 4.1 store/load <memtype> <val>, <memtype>* %slot, align 8
103 /// 4.2 store/load <memtype> <val>, <memtype>* %mem, align 8
105 /// @see polly::MemoryAccess, polly::ScopArrayInfo
107 /// @note assumes -polly-canonicalize has been run.
109 /// @param Inst The LoadInst/StoreInst that accesses the memory.
111 /// @returns Reference to %untypedmem on success, nullptr on failure.
112 Value
*findFADAllocationVisible(MemAccInst Inst
);
116 // Build the SCoP for Region @p R.
117 void buildScop(Region
&R
, AssumptionCache
&AC
);
119 /// Try to build a multi-dimensional fixed sized MemoryAccess from the
120 /// Load/Store instruction.
122 /// @param Inst The Load/Store instruction that access the memory
123 /// @param Stmt The parent statement of the instruction
125 /// @returns True if the access could be built, False otherwise.
126 bool buildAccessMultiDimFixed(MemAccInst Inst
, ScopStmt
*Stmt
);
128 /// Try to build a multi-dimensional parameteric sized MemoryAccess.
129 /// from the Load/Store instruction.
131 /// @param Inst The Load/Store instruction that access the memory
132 /// @param Stmt The parent statement of the instruction
134 /// @returns True if the access could be built, False otherwise.
135 bool buildAccessMultiDimParam(MemAccInst Inst
, ScopStmt
*Stmt
);
137 /// Try to build a MemoryAccess for a memory intrinsic.
139 /// @param Inst The instruction that access the memory
140 /// @param Stmt The parent statement of the instruction
142 /// @returns True if the access could be built, False otherwise.
143 bool buildAccessMemIntrinsic(MemAccInst Inst
, ScopStmt
*Stmt
);
145 /// Try to build a MemoryAccess for a call instruction.
147 /// @param Inst The call instruction that access the memory
148 /// @param Stmt The parent statement of the instruction
150 /// @returns True if the access could be built, False otherwise.
151 bool buildAccessCallInst(MemAccInst Inst
, ScopStmt
*Stmt
);
153 /// Build a single-dimensional parametric sized MemoryAccess
154 /// from the Load/Store instruction.
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
);
160 /// Build an instance of MemoryAccess from the Load/Store instruction.
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
);
166 /// Analyze and extract the cross-BB scalar dependences (or, dataflow
167 /// dependencies) of an instruction.
169 /// @param Inst The instruction to be analyzed.
170 void buildScalarDependences(Instruction
*Inst
);
172 /// Build the escaping dependences for @p Inst.
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.
178 /// @param Inst The instruction to be analyzed.
179 void buildEscapingDependences(Instruction
*Inst
);
181 /// Create MemoryAccesses for the given PHI node in the given region.
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);
189 /// Build the access functions for the subregion @p SR.
191 /// @param SR A subregion of @p R.
192 /// @param InsnToMemAcc The Instruction to MemoryAccess mapping.
193 void buildAccessFunctions(Region
&SR
);
195 /// Create ScopStmt for all BBs and non-affine subregions of @p SR.
197 /// @param SR A subregion of @p R.
199 /// Some of the statments might be optimized away later when they do not
200 /// access any memory and thus have no effect.
201 void buildStmts(Region
&SR
);
203 /// Build the access functions for the basic block @p BB.
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);
212 /// Create a new MemoryAccess object and add it to #AccFuncMap.
214 /// @param BB The block where the access takes place.
215 /// @param Inst The instruction doing the access. It is not necessarily
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.
226 /// @return The created MemoryAccess, or nullptr if the access is not within
228 MemoryAccess
*addMemoryAccess(BasicBlock
*BB
, Instruction
*Inst
,
229 MemoryAccess::AccessType AccType
,
230 Value
*BaseAddress
, Type
*ElemType
, bool Affine
,
232 ArrayRef
<const SCEV
*> Subscripts
,
233 ArrayRef
<const SCEV
*> Sizes
, MemoryKind Kind
);
235 /// Create a MemoryAccess that represents either a LoadInst or
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.
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
);
253 /// Create a MemoryAccess for writing an llvm::Instruction.
255 /// The access will be created at the position of @p Inst.
257 /// @param Inst The instruction to be written.
259 /// @see ensureValueRead()
261 void ensureValueWrite(Instruction
*Inst
);
263 /// Ensure an llvm::Value is available in the BB's statement, creating a
264 /// MemoryAccess for reloading it if necessary.
266 /// @param V The value expected to be loaded.
267 /// @param UserBB Where to reload the value.
269 /// @see ensureValueStore()
271 void ensureValueRead(Value
*V
, BasicBlock
*UserBB
);
273 /// Create a write MemoryAccess for the incoming block of a phi node.
275 /// Each of the incoming blocks write their incoming value to be picked in the
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()
286 void ensurePHIWrite(PHINode
*PHI
, BasicBlock
*IncomingBlock
,
287 Value
*IncomingValue
, bool IsExitBlock
);
289 /// Create a MemoryAccess for reading the value of a phi.
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.
295 /// @param PHI PHINode under consideration; the READ access will be added
298 /// @see ensurePHIWrite()
300 void addPHIReadAccess(PHINode
*PHI
);
303 explicit ScopBuilder(Region
*R
, AssumptionCache
&AC
, AliasAnalysis
&AA
,
304 const DataLayout
&DL
, DominatorTree
&DT
, LoopInfo
&LI
,
305 ScopDetection
&SD
, ScalarEvolution
&SE
);
308 /// Try to build the Polly IR of static control part on the current
311 /// @return Give up the ownership of the scop object or static control part
313 std::unique_ptr
<Scop
> getScop() { return std::move(scop
); }
316 } // end namespace polly
320 void initializeScopInfoRegionPassPass(llvm::PassRegistry
&);
321 void initializeScopInfoWrapperPassPass(llvm::PassRegistry
&);