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 /// @brief Build the Polly IR (Scop and ScopStmt) on a Region.
26 //===-------------------------------------------------------------------===//
27 ScopBuilder(const ScopBuilder
&) = delete;
28 const ScopBuilder
&operator=(const ScopBuilder
&) = delete;
30 /// @brief The AliasAnalysis to build AliasSetTracker.
33 /// @brief Target data for element size computing.
36 /// @brief DominatorTree to reason about guaranteed execution.
39 /// @brief LoopInfo for information about loops
42 /// @biref Valid Regions for Scop
45 /// @brief The ScalarEvolution to help building Scop.
48 /// @brief Set of instructions that might read any memory location.
49 SmallVector
<Instruction
*, 16> GlobalReads
;
51 /// @brief Set of all accessed array base pointers.
52 SmallSetVector
<Value
*, 16> ArrayBasePointers
;
55 std::unique_ptr
<Scop
> scop
;
57 // Build the SCoP for Region @p R.
58 void buildScop(Region
&R
, AssumptionCache
&AC
);
60 /// @brief Try to build a multi-dimensional fixed sized MemoryAccess from
61 /// the Load/Store instruction.
63 /// @param Inst The Load/Store instruction that access the memory
64 /// @param L The parent loop of the instruction
66 /// @returns True if the access could be built, False otherwise.
67 bool buildAccessMultiDimFixed(MemAccInst Inst
, Loop
*L
);
69 /// @brief Try to build a multi-dimensional parameteric sized MemoryAccess
70 /// from the Load/Store instruction.
72 /// @param Inst The Load/Store instruction that access the memory
73 /// @param L The parent loop of the instruction
75 /// @returns True if the access could be built, False otherwise.
76 bool buildAccessMultiDimParam(MemAccInst Inst
, Loop
*L
);
78 /// @brief Try to build a MemoryAccess for a memory intrinsic.
80 /// @param Inst The instruction that access the memory
81 /// @param L The parent loop of the instruction
83 /// @returns True if the access could be built, False otherwise.
84 bool buildAccessMemIntrinsic(MemAccInst Inst
, Loop
*L
);
86 /// @brief Try to build a MemoryAccess for a call instruction.
88 /// @param Inst The call instruction that access the memory
89 /// @param L The parent loop of the instruction
91 /// @returns True if the access could be built, False otherwise.
92 bool buildAccessCallInst(MemAccInst Inst
, Loop
*L
);
94 /// @brief Build a single-dimensional parametric sized MemoryAccess
95 /// from the Load/Store instruction.
97 /// @param Inst The Load/Store instruction that access the memory
98 /// @param L The parent loop of the instruction
99 void buildAccessSingleDim(MemAccInst Inst
, Loop
*L
);
101 /// @brief Build an instance of MemoryAccess from the Load/Store instruction.
103 /// @param Inst The Load/Store instruction that access the memory
104 /// @param L The parent loop of the instruction
105 void buildMemoryAccess(MemAccInst Inst
, Loop
*L
);
107 /// @brief Analyze and extract the cross-BB scalar dependences (or,
108 /// dataflow dependencies) of an instruction.
110 /// @param Inst The instruction to be analyzed.
111 void buildScalarDependences(Instruction
*Inst
);
113 /// @brief Search for uses of the llvm::Value defined by @p Inst that are not
114 /// within the SCoP. If there is such use, add a SCALAR WRITE such that
115 /// it is available after the SCoP as escaping value.
117 /// @param Inst The instruction to be analyzed.
118 void buildEscapingDependences(Instruction
*Inst
);
120 /// @brief Create MemoryAccesses for the given PHI node in the given region.
122 /// @param PHI The PHI node to be handled
123 /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
124 /// @param IsExitBlock Flag to indicate that @p PHI is in the exit BB.
125 void buildPHIAccesses(PHINode
*PHI
, Region
*NonAffineSubRegion
,
126 bool IsExitBlock
= false);
128 /// @brief Build the access functions for the subregion @p SR.
130 /// @param SR A subregion of @p R.
131 /// @param InsnToMemAcc The Instruction to MemoryAccess mapping.
132 void buildAccessFunctions(Region
&SR
);
134 /// @brief Create ScopStmt for all BBs and non-affine subregions of @p SR.
136 /// @param SR A subregion of @p R.
138 /// Some of the statments might be optimized away later when they do not
139 /// access any memory and thus have no effect.
140 void buildStmts(Region
&SR
);
142 /// @brief Build the access functions for the basic block @p BB
144 /// @param BB A basic block in @p R.
145 /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
146 /// @param IsExitBlock Flag to indicate that @p BB is in the exit BB.
147 void buildAccessFunctions(BasicBlock
&BB
,
148 Region
*NonAffineSubRegion
= nullptr,
149 bool IsExitBlock
= false);
151 /// @brief Create a new MemoryAccess object and add it to #AccFuncMap.
153 /// @param BB The block where the access takes place.
154 /// @param Inst The instruction doing the access. It is not necessarily
156 /// @param AccType The kind of access.
157 /// @param BaseAddress The accessed array's base address.
158 /// @param ElemType The type of the accessed array elements.
159 /// @param Affine Whether all subscripts are affine expressions.
160 /// @param AccessValue Value read or written.
161 /// @param Subscripts Access subscripts per dimension.
162 /// @param Sizes The array dimension's sizes.
163 /// @param Kind The kind of memory accessed.
165 /// @return The created MemoryAccess, or nullptr if the access is not within
167 MemoryAccess
*addMemoryAccess(BasicBlock
*BB
, Instruction
*Inst
,
168 MemoryAccess::AccessType AccType
,
169 Value
*BaseAddress
, Type
*ElemType
, bool Affine
,
171 ArrayRef
<const SCEV
*> Subscripts
,
172 ArrayRef
<const SCEV
*> Sizes
,
173 ScopArrayInfo::MemoryKind Kind
);
175 /// @brief Create a MemoryAccess that represents either a LoadInst or
178 /// @param MemAccInst The LoadInst or StoreInst.
179 /// @param AccType The kind of access.
180 /// @param BaseAddress The accessed array's base address.
181 /// @param ElemType The type of the accessed array elements.
182 /// @param IsAffine Whether all subscripts are affine expressions.
183 /// @param Subscripts Access subscripts per dimension.
184 /// @param Sizes The array dimension's sizes.
185 /// @param AccessValue Value read or written.
187 /// @see ScopArrayInfo::MemoryKind
188 void addArrayAccess(MemAccInst MemAccInst
, MemoryAccess::AccessType AccType
,
189 Value
*BaseAddress
, Type
*ElemType
, bool IsAffine
,
190 ArrayRef
<const SCEV
*> Subscripts
,
191 ArrayRef
<const SCEV
*> Sizes
, Value
*AccessValue
);
193 /// @brief Create a MemoryAccess for writing an llvm::Instruction.
195 /// The access will be created at the position of @p Inst.
197 /// @param Inst The instruction to be written.
199 /// @see ensureValueRead()
200 /// @see ScopArrayInfo::MemoryKind
201 void ensureValueWrite(Instruction
*Inst
);
203 /// @brief Ensure an llvm::Value is available in the BB's statement, creating
204 /// a MemoryAccess for reloading it if necessary.
206 /// @param V The value expected to be loaded.
207 /// @param UserBB Where to reload the value.
209 /// @see ensureValueStore()
210 /// @see ScopArrayInfo::MemoryKind
211 void ensureValueRead(Value
*V
, BasicBlock
*UserBB
);
213 /// @brief Create a write MemoryAccess for the incoming block of a phi node.
215 /// Each of the incoming blocks write their incoming value to be picked in the
218 /// @param PHI PHINode under consideration.
219 /// @param IncomingBlock Some predecessor block.
220 /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
221 /// @param IsExitBlock When true, uses the .s2a alloca instead of the
222 /// .phiops one. Required for values escaping through a
223 /// PHINode in the SCoP region's exit block.
224 /// @see addPHIReadAccess()
225 /// @see ScopArrayInfo::MemoryKind
226 void ensurePHIWrite(PHINode
*PHI
, BasicBlock
*IncomingBlock
,
227 Value
*IncomingValue
, bool IsExitBlock
);
229 /// @brief Create a MemoryAccess for reading the value of a phi.
231 /// The modeling assumes that all incoming blocks write their incoming value
232 /// to the same location. Thus, this access will read the incoming block's
233 /// value as instructed by this @p PHI.
235 /// @param PHI PHINode under consideration; the READ access will be added
238 /// @see ensurePHIWrite()
239 /// @see ScopArrayInfo::MemoryKind
240 void addPHIReadAccess(PHINode
*PHI
);
243 explicit ScopBuilder(Region
*R
, AssumptionCache
&AC
, AliasAnalysis
&AA
,
244 const DataLayout
&DL
, DominatorTree
&DT
, LoopInfo
&LI
,
245 ScopDetection
&SD
, ScalarEvolution
&SE
);
248 /// @brief Try to build the Polly IR of static control part on the current
251 /// @return Give up the ownership of the scop object or static control part
253 std::unique_ptr
<Scop
> getScop() { return std::move(scop
); }
256 } // end namespace polly
260 void initializeScopInfoRegionPassPass(llvm::PassRegistry
&);
261 void initializeScopInfoWrapperPassPass(llvm::PassRegistry
&);