1 //===------ IslNodeBuilder.cpp - Translate an isl AST into a LLVM-IR AST---===//
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 //===----------------------------------------------------------------------===//
9 // This file contains the IslNodeBuilder, a class to translate an isl AST into
11 //===----------------------------------------------------------------------===//
13 #ifndef POLLY_ISL_NODE_BUILDER_H
14 #define POLLY_ISL_NODE_BUILDER_H
16 #include "polly/CodeGen/BlockGenerators.h"
17 #include "polly/CodeGen/IslExprBuilder.h"
18 #include "polly/CodeGen/LoopGenerators.h"
19 #include "polly/ScopInfo.h"
21 #include "isl/union_map.h"
23 using namespace polly
;
30 struct SubtreeReferences
{
35 SetVector
<Value
*> &Values
;
36 SetVector
<const SCEV
*> &SCEVs
;
37 BlockGenerator
&BlockGen
;
40 isl_stat
addReferencesFromStmt(const ScopStmt
*Stmt
, void *UserPtr
);
42 class IslNodeBuilder
{
44 IslNodeBuilder(PollyIRBuilder
&Builder
, ScopAnnotator
&Annotator
, Pass
*P
,
45 const DataLayout
&DL
, LoopInfo
&LI
, ScalarEvolution
&SE
,
46 DominatorTree
&DT
, Scop
&S
)
47 : S(S
), Builder(Builder
), Annotator(Annotator
),
48 ExprBuilder(S
, Builder
, IDToValue
, ValueMap
, DL
, SE
, DT
, LI
),
49 BlockGen(Builder
, LI
, SE
, DT
, ScalarMap
, PHIOpMap
, EscapeMap
, ValueMap
,
51 RegionGen(BlockGen
), P(P
), DL(DL
), LI(LI
), SE(SE
), DT(DT
) {}
53 virtual ~IslNodeBuilder() {}
55 void addParameters(__isl_take isl_set
*Context
);
56 void create(__isl_take isl_ast_node
*Node
);
58 /// @brief Allocate memory for all new arrays created by Polly.
59 void allocateNewArrays();
61 /// @brief Preload all memory loads that are invariant.
62 bool preloadInvariantLoads();
64 /// @brief Finalize code generation.
66 /// @see BlockGenerator::finalizeSCoP(Scop &S)
67 virtual void finalize() { BlockGen
.finalizeSCoP(S
); }
69 IslExprBuilder
&getExprBuilder() { return ExprBuilder
; }
71 /// @brief Get the associated block generator.
73 /// @return A referecne to the associated block generator.
74 BlockGenerator
&getBlockGenerator() { return BlockGen
; }
76 /// @brief Return the parallel subfunctions that have been created.
77 const ArrayRef
<Function
*> getParallelSubfunctions() const {
78 return ParallelSubfunctions
;
83 PollyIRBuilder
&Builder
;
84 ScopAnnotator
&Annotator
;
86 IslExprBuilder ExprBuilder
;
88 /// @brief Maps used by the block and region generator to demote scalars.
92 /// @brief See BlockGenerator::ScalarMap.
93 BlockGenerator::ScalarAllocaMapTy ScalarMap
;
95 /// @brief See BlockGenerator::PhiOpMap.
96 BlockGenerator::ScalarAllocaMapTy PHIOpMap
;
98 /// @brief See BlockGenerator::EscapeMap.
99 BlockGenerator::EscapeUsersAllocaMapTy EscapeMap
;
103 /// @brief The generator used to copy a basic block.
104 BlockGenerator BlockGen
;
106 /// @brief The generator used to copy a non-affine region.
107 RegionGenerator RegionGen
;
110 const DataLayout
&DL
;
115 /// @brief The current iteration of out-of-scop loops
117 /// This map provides for a given loop a llvm::Value that contains the current
119 LoopToScevMapT OutsideLoopIterations
;
121 // This maps an isl_id* to the Value* it has in the generated program. For now
122 // on, the only isl_ids that are stored here are the newly calculated loop
124 IslExprBuilder::IDToValueTy IDToValue
;
126 /// @brief A collection of all parallel subfunctions that have been created.
127 SmallVector
<Function
*, 8> ParallelSubfunctions
;
129 /// Generate code for a given SCEV*
131 /// This function generates code for a given SCEV expression. It generated
132 /// code is emitted at the end of the basic block our Builder currently
133 /// points to and the resulting value is returned.
135 /// @param Expr The expression to code generate.
136 llvm::Value
*generateSCEV(const SCEV
*Expr
);
138 /// A set of Value -> Value remappings to apply when generating new code.
140 /// When generating new code for a ScopStmt this map is used to map certain
141 /// llvm::Values to new llvm::Values.
144 /// @brief Materialize code for @p Id if it was not done before.
146 /// @returns False, iff a problem occured and the value was not materialized.
147 bool materializeValue(__isl_take isl_id
*Id
);
149 /// @brief Materialize parameters of @p Set.
151 /// @param All If not set only parameters referred to by the constraints in
152 /// @p Set will be materialized, otherwise all.
154 /// @returns False, iff a problem occurred and the value was not materialized.
155 bool materializeParameters(__isl_take isl_set
*Set
, bool All
);
157 // Extract the upper bound of this loop
159 // The isl code generation can generate arbitrary expressions to check if the
160 // upper bound of a loop is reached, but it provides an option to enforce
161 // 'atomic' upper bounds. An 'atomic upper bound is always of the form
162 // iv <= expr, where expr is an (arbitrary) expression not containing iv.
164 // This function extracts 'atomic' upper bounds. Polly, in general, requires
165 // atomic upper bounds for the following reasons:
167 // 1. An atomic upper bound is loop invariant
169 // It must not be calculated at each loop iteration and can often even be
170 // hoisted out further by the loop invariant code motion.
172 // 2. OpenMP needs a loop invariant upper bound to calculate the number
173 // of loop iterations.
175 // 3. With the existing code, upper bounds have been easier to implement.
176 __isl_give isl_ast_expr
*getUpperBound(__isl_keep isl_ast_node
*For
,
177 CmpInst::Predicate
&Predicate
);
179 /// Return non-negative number of iterations in case of the following form
180 /// of a loop and -1 otherwise.
182 /// for (i = 0; i <= NumIter; i++) {
186 /// NumIter is a non-negative integer value. Condition can have
187 /// isl_ast_op_lt type.
188 int getNumberOfIterations(__isl_keep isl_ast_node
*For
);
190 /// Compute the values and loops referenced in this subtree.
192 /// This function looks at all ScopStmts scheduled below the provided For node
193 /// and finds the llvm::Value[s] and llvm::Loops[s] which are referenced but
194 /// not locally defined.
196 /// Values that can be synthesized or that are available as globals are
197 /// considered locally defined.
199 /// Loops that contain the scop or that are part of the scop are considered
200 /// locally defined. Loops that are before the scop, but do not contain the
201 /// scop itself are considered not locally defined.
203 /// @param For The node defining the subtree.
204 /// @param Values A vector that will be filled with the Values referenced in
206 /// @param Loops A vector that will be filled with the Loops referenced in
208 void getReferencesInSubtree(__isl_keep isl_ast_node
*For
,
209 SetVector
<Value
*> &Values
,
210 SetVector
<const Loop
*> &Loops
);
212 /// Change the llvm::Value(s) used for code generation.
214 /// When generating code certain values (e.g., references to induction
215 /// variables or array base pointers) in the original code may be replaced by
216 /// new values. This function allows to (partially) update the set of values
217 /// used. A typical use case for this function is the case when we continue
218 /// code generation in a subfunction/kernel function and need to explicitly
219 /// pass down certain values.
221 /// @param NewValues A map that maps certain llvm::Values to new llvm::Values.
222 void updateValues(ValueMapT
&NewValues
);
224 /// @brief Generate code for a marker now.
226 /// For mark nodes with an unknown name, we just forward the code generation
227 /// to its child. This is currently the only behavior implemented, as there is
228 /// currently not special handling for marker nodes implemented.
230 /// @param Mark The node we generate code for.
231 virtual void createMark(__isl_take isl_ast_node
*Marker
);
232 virtual void createFor(__isl_take isl_ast_node
*For
);
234 /// @brief Set to remember materialized invariant loads.
236 /// An invariant load is identified by its pointer (the SCEV) and its type.
237 SmallSet
<std::pair
<const SCEV
*, Type
*>, 16> PreloadedPtrs
;
239 /// @brief Preload the memory access at @p AccessRange with @p Build.
241 /// @returns The preloaded value casted to type @p Ty
242 Value
*preloadUnconditionally(__isl_take isl_set
*AccessRange
,
243 isl_ast_build
*Build
, Instruction
*AccInst
);
245 /// @brief Preload the memory load access @p MA.
247 /// If @p MA is not always executed it will be conditionally loaded and
248 /// merged with undef from the same type. Hence, if @p MA is executed only
249 /// under condition C then the preload code will look like this:
251 /// MA_preload = undef;
253 /// MA_preload = load MA;
255 Value
*preloadInvariantLoad(const MemoryAccess
&MA
,
256 __isl_take isl_set
*Domain
);
258 /// @brief Preload the invariant access equivalence class @p IAClass
260 /// This function will preload the representing load from @p IAClass and
261 /// map all members of @p IAClass to that preloaded value, potentially casted
262 /// to the required type.
264 /// @returns False, iff a problem occurred and the load was not preloaded.
265 bool preloadInvariantEquivClass(InvariantEquivClassTy
&IAClass
);
267 void createForVector(__isl_take isl_ast_node
*For
, int VectorWidth
);
268 void createForSequential(__isl_take isl_ast_node
*For
, bool KnownParallel
);
270 /// Create LLVM-IR that executes a for node thread parallel.
272 /// @param For The FOR isl_ast_node for which code is generated.
273 void createForParallel(__isl_take isl_ast_node
*For
);
275 /// @brief Create new access functions for modified memory accesses.
277 /// In case the access function of one of the memory references in the Stmt
278 /// has been modified, we generate a new isl_ast_expr that reflects the
279 /// newly modified access function and return a map that maps from the
280 /// individual memory references in the statement (identified by their id)
281 /// to these newly generated ast expressions.
283 /// @param Stmt The statement for which to (possibly) generate new access
285 /// @param Node The ast node corresponding to the statement for us to extract
286 /// the local schedule from.
287 /// @return A new hash table that contains remappings from memory ids to new
288 /// access expressions.
289 __isl_give isl_id_to_ast_expr
*
290 createNewAccesses(ScopStmt
*Stmt
, __isl_keep isl_ast_node
*Node
);
292 /// Generate LLVM-IR that computes the values of the original induction
293 /// variables in function of the newly generated loop induction variables.
302 /// Schedule: [i,j] -> [i+j, j]
309 /// Assuming the original code consists of two loops which are
310 /// transformed according to a schedule [i,j] -> [c0=i+j,c1=j]. The resulting
311 /// ast models the original statement as a call expression where each argument
312 /// is an expression that computes the old induction variables from the new
313 /// ones, ordered such that the first argument computes the value of induction
314 /// variable that was outermost in the original code.
316 /// @param Expr The call expression that represents the statement.
317 /// @param Stmt The statement that is called.
318 /// @param LTS The loop to SCEV map in which the mapping from the original
319 /// loop to a SCEV representing the new loop iv is added. This
320 /// mapping does not require an explicit induction variable.
321 /// Instead, we think in terms of an implicit induction variable
322 /// that counts the number of times a loop is executed. For each
323 /// original loop this count, expressed in function of the new
324 /// induction variables, is added to the LTS map.
325 void createSubstitutions(__isl_take isl_ast_expr
*Expr
, ScopStmt
*Stmt
,
326 LoopToScevMapT
<S
);
327 void createSubstitutionsVector(__isl_take isl_ast_expr
*Expr
, ScopStmt
*Stmt
,
328 std::vector
<LoopToScevMapT
> &VLTS
,
329 std::vector
<Value
*> &IVS
,
330 __isl_take isl_id
*IteratorID
);
331 virtual void createIf(__isl_take isl_ast_node
*If
);
332 void createUserVector(__isl_take isl_ast_node
*User
,
333 std::vector
<Value
*> &IVS
,
334 __isl_take isl_id
*IteratorID
,
335 __isl_take isl_union_map
*Schedule
);
336 virtual void createUser(__isl_take isl_ast_node
*User
);
337 virtual void createBlock(__isl_take isl_ast_node
*Block
);
339 /// @brief Get the schedule for a given AST node.
341 /// This information is used to reason about parallelism of loops or the
342 /// locality of memory accesses under a given schedule.
344 /// @param Node The node we want to obtain the schedule for.
345 /// @return Return an isl_union_map that maps from the statements executed
346 /// below this ast node to the scheduling vectors used to enumerate
349 virtual __isl_give isl_union_map
*
350 getScheduleForAstNode(__isl_take isl_ast_node
*Node
);