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 that has been declared
61 /// global, and is allocated in this module.
63 /// "@globaldescriptor" is the descriptor of the Fortran Array.
65 /// Pattern match for "@globaldescriptor":
66 /// 1. %mem = load double*, double** bitcast (%"struct.array1_real(kind=8)"*
67 /// @globaldescriptor to double**), align 32
69 /// 2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>]
70 /// 2 is optional because if you are writing to the 0th index, you don't
73 /// 3.1 store/load <memtype> <val>, <memtype>* %slot, align 8
74 /// 3.2 store/load <memtype> <val>, <memtype>* %mem, align 8
76 /// @see polly::MemoryAccess, polly::ScopArrayInfo
78 /// @note assumes -polly-canonicalize has been run.
80 /// @param Inst The LoadInst/StoreInst that accesses the memory.
82 /// @returns Reference to @globaldescriptor on success, nullptr on failure.
83 Value
*findFADGlobalAlloc(MemAccInst Inst
);
85 /// Try to match for the descriptor of a Fortran Array that has been declared
86 /// global, and is being accessed across modules.
88 /// Pattern match for "@globaldescriptor":
89 /// 1. %mem = load double*, double** bitcast (%"struct.array1_real(kind=8)"*
90 /// @globaldescriptor to double**), align 32
92 /// 2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>]
93 /// 2 is optional because if you are writing to the 0th index, you don't
96 /// 3.1 store/load <memtype> <val>, <memtype>* %slot, align 8
97 /// 3.2 store/load <memtype> <val>, <memtype>* %mem, align 8
99 /// @see polly::MemoryAccess, polly::ScopArrayInfo
101 /// @note assumes -polly-canonicalize has been run.
103 /// @param Inst The LoadInst/StoreInst that accesses the memory.
105 /// @returns Reference to @globaldescriptor on success, nullptr on failure.
106 Value
*findFADGlobalNonAlloc(MemAccInst Inst
);
108 /// Try to match for the descriptor of a Fortran array that is a parameter
109 /// to a function, and has not been allocated.
111 /// Pattern match for "%param":
112 /// 1. %mem = bitcast %"struct.array1_integer(kind=4)"* %param to i32**
114 /// 2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>]
115 /// 2 is optional because if you are writing to the 0th index, you don't
118 /// 3.1 store/load <memtype> <val>, <memtype>* %slot, align 8
119 /// 3.2 store/load <memtype> <val>, <memtype>* %mem, align 8
121 /// @see polly::MemoryAccess, polly::ScopArrayInfo
123 /// @note assumes -polly-canonicalize has been run.
125 /// @param Inst The LoadInst/StoreInst that accesses the memory.
127 /// @returns Reference to "%param" on success, nullptr on failure.
128 Value
*findFADLocalNonAlloc(MemAccInst Inst
);
131 // Build the SCoP for Region @p R.
132 void buildScop(Region
&R
, AssumptionCache
&AC
);
134 /// Try to build a multi-dimensional fixed sized MemoryAccess from the
135 /// Load/Store instruction.
137 /// @param Inst The Load/Store instruction that access the memory
138 /// @param Stmt The parent statement of the instruction
140 /// @returns True if the access could be built, False otherwise.
141 bool buildAccessMultiDimFixed(MemAccInst Inst
, ScopStmt
*Stmt
);
143 /// Try to build a multi-dimensional parameteric sized MemoryAccess.
144 /// from the Load/Store instruction.
146 /// @param Inst The Load/Store instruction that access the memory
147 /// @param Stmt The parent statement of the instruction
149 /// @returns True if the access could be built, False otherwise.
150 bool buildAccessMultiDimParam(MemAccInst Inst
, ScopStmt
*Stmt
);
152 /// Try to build a MemoryAccess for a memory intrinsic.
154 /// @param Inst The instruction that access the memory
155 /// @param Stmt The parent statement of the instruction
157 /// @returns True if the access could be built, False otherwise.
158 bool buildAccessMemIntrinsic(MemAccInst Inst
, ScopStmt
*Stmt
);
160 /// Try to build a MemoryAccess for a call instruction.
162 /// @param Inst The call instruction that access the memory
163 /// @param Stmt The parent statement of the instruction
165 /// @returns True if the access could be built, False otherwise.
166 bool buildAccessCallInst(MemAccInst Inst
, ScopStmt
*Stmt
);
168 /// Build a single-dimensional parametric sized MemoryAccess
169 /// from the Load/Store instruction.
171 /// @param Inst The Load/Store instruction that access the memory
172 /// @param Stmt The parent statement of the instruction
173 void buildAccessSingleDim(MemAccInst Inst
, ScopStmt
*Stmt
);
175 /// Build an instance of MemoryAccess from the Load/Store instruction.
177 /// @param Inst The Load/Store instruction that access the memory
178 /// @param Stmt The parent statement of the instruction
179 void buildMemoryAccess(MemAccInst Inst
, ScopStmt
*Stmt
);
181 /// Analyze and extract the cross-BB scalar dependences (or, dataflow
182 /// dependencies) of an instruction.
184 /// @param Inst The instruction to be analyzed.
185 void buildScalarDependences(Instruction
*Inst
);
187 /// Build the escaping dependences for @p Inst.
189 /// Search for uses of the llvm::Value defined by @p Inst that are not
190 /// within the SCoP. If there is such use, add a SCALAR WRITE such that
191 /// it is available after the SCoP as escaping value.
193 /// @param Inst The instruction to be analyzed.
194 void buildEscapingDependences(Instruction
*Inst
);
196 /// Create MemoryAccesses for the given PHI node in the given region.
198 /// @param PHI The PHI node to be handled
199 /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
200 /// @param IsExitBlock Flag to indicate that @p PHI is in the exit BB.
201 void buildPHIAccesses(PHINode
*PHI
, Region
*NonAffineSubRegion
,
202 bool IsExitBlock
= false);
204 /// Build the access functions for the subregion @p SR.
206 /// @param SR A subregion of @p R.
207 /// @param InsnToMemAcc The Instruction to MemoryAccess mapping.
208 void buildAccessFunctions(Region
&SR
);
210 /// Create ScopStmt for all BBs and non-affine subregions of @p SR.
212 /// @param SR A subregion of @p R.
214 /// Some of the statments might be optimized away later when they do not
215 /// access any memory and thus have no effect.
216 void buildStmts(Region
&SR
);
218 /// Build the access functions for the basic block @p BB.
220 /// @param BB A basic block in @p R.
221 /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
222 /// @param IsExitBlock Flag to indicate that @p BB is in the exit BB.
223 void buildAccessFunctions(BasicBlock
&BB
,
224 Region
*NonAffineSubRegion
= nullptr,
225 bool IsExitBlock
= false);
227 /// Create a new MemoryAccess object and add it to #AccFuncMap.
229 /// @param BB The block where the access takes place.
230 /// @param Inst The instruction doing the access. It is not necessarily
232 /// @param AccType The kind of access.
233 /// @param BaseAddress The accessed array's base address.
234 /// @param ElemType The type of the accessed array elements.
235 /// @param Affine Whether all subscripts are affine expressions.
236 /// @param AccessValue Value read or written.
237 /// @param Subscripts Access subscripts per dimension.
238 /// @param Sizes The array dimension's sizes.
239 /// @param Kind The kind of memory accessed.
241 /// @return The created MemoryAccess, or nullptr if the access is not within
243 MemoryAccess
*addMemoryAccess(BasicBlock
*BB
, Instruction
*Inst
,
244 MemoryAccess::AccessType AccType
,
245 Value
*BaseAddress
, Type
*ElemType
, bool Affine
,
247 ArrayRef
<const SCEV
*> Subscripts
,
248 ArrayRef
<const SCEV
*> Sizes
, MemoryKind Kind
);
250 /// Create a MemoryAccess that represents either a LoadInst or
253 /// @param MemAccInst The LoadInst or StoreInst.
254 /// @param AccType The kind of access.
255 /// @param BaseAddress The accessed array's base address.
256 /// @param ElemType The type of the accessed array elements.
257 /// @param IsAffine Whether all subscripts are affine expressions.
258 /// @param Subscripts Access subscripts per dimension.
259 /// @param Sizes The array dimension's sizes.
260 /// @param AccessValue Value read or written.
263 void addArrayAccess(MemAccInst MemAccInst
, MemoryAccess::AccessType AccType
,
264 Value
*BaseAddress
, Type
*ElemType
, bool IsAffine
,
265 ArrayRef
<const SCEV
*> Subscripts
,
266 ArrayRef
<const SCEV
*> Sizes
, Value
*AccessValue
);
268 /// Create a MemoryAccess for writing an llvm::Instruction.
270 /// The access will be created at the position of @p Inst.
272 /// @param Inst The instruction to be written.
274 /// @see ensureValueRead()
276 void ensureValueWrite(Instruction
*Inst
);
278 /// Ensure an llvm::Value is available in the BB's statement, creating a
279 /// MemoryAccess for reloading it if necessary.
281 /// @param V The value expected to be loaded.
282 /// @param UserBB Where to reload the value.
284 /// @see ensureValueStore()
286 void ensureValueRead(Value
*V
, BasicBlock
*UserBB
);
288 /// Create a write MemoryAccess for the incoming block of a phi node.
290 /// Each of the incoming blocks write their incoming value to be picked in the
293 /// @param PHI PHINode under consideration.
294 /// @param IncomingBlock Some predecessor block.
295 /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
296 /// @param IsExitBlock When true, uses the .s2a alloca instead of the
297 /// .phiops one. Required for values escaping through a
298 /// PHINode in the SCoP region's exit block.
299 /// @see addPHIReadAccess()
301 void ensurePHIWrite(PHINode
*PHI
, BasicBlock
*IncomingBlock
,
302 Value
*IncomingValue
, bool IsExitBlock
);
304 /// Create a MemoryAccess for reading the value of a phi.
306 /// The modeling assumes that all incoming blocks write their incoming value
307 /// to the same location. Thus, this access will read the incoming block's
308 /// value as instructed by this @p PHI.
310 /// @param PHI PHINode under consideration; the READ access will be added
313 /// @see ensurePHIWrite()
315 void addPHIReadAccess(PHINode
*PHI
);
318 explicit ScopBuilder(Region
*R
, AssumptionCache
&AC
, AliasAnalysis
&AA
,
319 const DataLayout
&DL
, DominatorTree
&DT
, LoopInfo
&LI
,
320 ScopDetection
&SD
, ScalarEvolution
&SE
);
323 /// Try to build the Polly IR of static control part on the current
326 /// @return Give up the ownership of the scop object or static control part
328 std::unique_ptr
<Scop
> getScop() { return std::move(scop
); }
331 } // end namespace polly
335 void initializeScopInfoRegionPassPass(llvm::PassRegistry
&);
336 void initializeScopInfoWrapperPassPass(llvm::PassRegistry
&);