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 //===----------------------------------------------------------------------===//
10 // This file contains the IslNodeBuilder, a class to translate an isl AST into
13 //===----------------------------------------------------------------------===//
15 #include "polly/CodeGen/IslNodeBuilder.h"
16 #include "polly/CodeGen/BlockGenerators.h"
17 #include "polly/CodeGen/CodeGeneration.h"
18 #include "polly/CodeGen/IslAst.h"
19 #include "polly/CodeGen/IslExprBuilder.h"
20 #include "polly/CodeGen/LoopGenerators.h"
21 #include "polly/CodeGen/Utils.h"
22 #include "polly/Config/config.h"
23 #include "polly/DependenceInfo.h"
24 #include "polly/LinkAllPasses.h"
25 #include "polly/ScopInfo.h"
26 #include "polly/Support/GICHelper.h"
27 #include "polly/Support/SCEVValidator.h"
28 #include "polly/Support/ScopHelper.h"
29 #include "llvm/ADT/PostOrderIterator.h"
30 #include "llvm/ADT/SmallPtrSet.h"
31 #include "llvm/Analysis/LoopInfo.h"
32 #include "llvm/Analysis/PostDominators.h"
33 #include "llvm/IR/DataLayout.h"
34 #include "llvm/IR/Module.h"
35 #include "llvm/IR/Verifier.h"
36 #include "llvm/Support/CommandLine.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
41 #include "isl/ast_build.h"
45 #include "isl/union_map.h"
46 #include "isl/union_set.h"
48 using namespace polly
;
51 // The maximal number of dimensions we allow during invariant load construction.
52 // More complex access ranges will result in very high compile time and are also
53 // unlikely to result in good code. This value is very high and should only
54 // trigger for corner cases (e.g., the "dct_luma" function in h264, SPEC2006).
55 static int const MaxDimensionsInAccessRange
= 9;
57 __isl_give isl_ast_expr
*
58 IslNodeBuilder::getUpperBound(__isl_keep isl_ast_node
*For
,
59 ICmpInst::Predicate
&Predicate
) {
60 isl_id
*UBID
, *IteratorID
;
61 isl_ast_expr
*Cond
, *Iterator
, *UB
, *Arg0
;
64 Cond
= isl_ast_node_for_get_cond(For
);
65 Iterator
= isl_ast_node_for_get_iterator(For
);
66 isl_ast_expr_get_type(Cond
);
67 assert(isl_ast_expr_get_type(Cond
) == isl_ast_expr_op
&&
68 "conditional expression is not an atomic upper bound");
70 Type
= isl_ast_expr_get_op_type(Cond
);
74 Predicate
= ICmpInst::ICMP_SLE
;
77 Predicate
= ICmpInst::ICMP_SLT
;
80 llvm_unreachable("Unexpected comparision type in loop conditon");
83 Arg0
= isl_ast_expr_get_op_arg(Cond
, 0);
85 assert(isl_ast_expr_get_type(Arg0
) == isl_ast_expr_id
&&
86 "conditional expression is not an atomic upper bound");
88 UBID
= isl_ast_expr_get_id(Arg0
);
90 assert(isl_ast_expr_get_type(Iterator
) == isl_ast_expr_id
&&
91 "Could not get the iterator");
93 IteratorID
= isl_ast_expr_get_id(Iterator
);
95 assert(UBID
== IteratorID
&&
96 "conditional expression is not an atomic upper bound");
98 UB
= isl_ast_expr_get_op_arg(Cond
, 1);
100 isl_ast_expr_free(Cond
);
101 isl_ast_expr_free(Iterator
);
102 isl_ast_expr_free(Arg0
);
103 isl_id_free(IteratorID
);
109 /// @brief Return true if a return value of Predicate is true for the value
110 /// represented by passed isl_ast_expr_int.
111 static bool checkIslAstExprInt(__isl_take isl_ast_expr
*Expr
,
112 isl_bool (*Predicate
)(__isl_keep isl_val
*)) {
113 if (isl_ast_expr_get_type(Expr
) != isl_ast_expr_int
) {
114 isl_ast_expr_free(Expr
);
117 auto ExprVal
= isl_ast_expr_get_val(Expr
);
118 isl_ast_expr_free(Expr
);
119 if (Predicate(ExprVal
) != true) {
120 isl_val_free(ExprVal
);
123 isl_val_free(ExprVal
);
127 int IslNodeBuilder::getNumberOfIterations(__isl_keep isl_ast_node
*For
) {
128 assert(isl_ast_node_get_type(For
) == isl_ast_node_for
);
129 auto Body
= isl_ast_node_for_get_body(For
);
131 // First, check if we can actually handle this code
132 switch (isl_ast_node_get_type(Body
)) {
133 case isl_ast_node_user
:
135 case isl_ast_node_block
: {
136 isl_ast_node_list
*List
= isl_ast_node_block_get_children(Body
);
137 for (int i
= 0; i
< isl_ast_node_list_n_ast_node(List
); ++i
) {
138 isl_ast_node
*Node
= isl_ast_node_list_get_ast_node(List
, i
);
139 int Type
= isl_ast_node_get_type(Node
);
140 isl_ast_node_free(Node
);
141 if (Type
!= isl_ast_node_user
) {
142 isl_ast_node_list_free(List
);
143 isl_ast_node_free(Body
);
147 isl_ast_node_list_free(List
);
151 isl_ast_node_free(Body
);
154 isl_ast_node_free(Body
);
156 auto Init
= isl_ast_node_for_get_init(For
);
157 if (!checkIslAstExprInt(Init
, isl_val_is_zero
))
159 auto Inc
= isl_ast_node_for_get_inc(For
);
160 if (!checkIslAstExprInt(Inc
, isl_val_is_one
))
162 CmpInst::Predicate Predicate
;
163 auto UB
= getUpperBound(For
, Predicate
);
164 if (isl_ast_expr_get_type(UB
) != isl_ast_expr_int
) {
165 isl_ast_expr_free(UB
);
168 auto UpVal
= isl_ast_expr_get_val(UB
);
169 isl_ast_expr_free(UB
);
170 int NumberIterations
= isl_val_get_num_si(UpVal
);
172 if (NumberIterations
< 0)
174 if (Predicate
== CmpInst::ICMP_SLT
)
175 return NumberIterations
;
177 return NumberIterations
+ 1;
180 /// @brief Extract the values and SCEVs needed to generate code for a block.
181 static int findReferencesInBlock(struct SubtreeReferences
&References
,
182 const ScopStmt
*Stmt
, const BasicBlock
*BB
) {
183 for (const Instruction
&Inst
: *BB
)
184 for (Value
*SrcVal
: Inst
.operands()) {
185 auto *Scope
= References
.LI
.getLoopFor(BB
);
186 if (canSynthesize(SrcVal
, References
.S
, &References
.LI
, &References
.SE
,
188 References
.SCEVs
.insert(References
.SE
.getSCEVAtScope(SrcVal
, Scope
));
190 } else if (Value
*NewVal
= References
.GlobalMap
.lookup(SrcVal
))
191 References
.Values
.insert(NewVal
);
196 /// Extract the out-of-scop values and SCEVs referenced from a ScopStmt.
198 /// This includes the SCEVUnknowns referenced by the SCEVs used in the
199 /// statement and the base pointers of the memory accesses. For scalar
200 /// statements we force the generation of alloca memory locations and list
201 /// these locations in the set of out-of-scop values as well.
203 /// @param Stmt The statement for which to extract the information.
204 /// @param UserPtr A void pointer that can be casted to a SubtreeReferences
206 isl_stat
addReferencesFromStmt(const ScopStmt
*Stmt
, void *UserPtr
) {
207 auto &References
= *static_cast<struct SubtreeReferences
*>(UserPtr
);
209 if (Stmt
->isBlockStmt())
210 findReferencesInBlock(References
, Stmt
, Stmt
->getBasicBlock());
212 assert(Stmt
->isRegionStmt() &&
213 "Stmt was neither block nor region statement");
214 for (const BasicBlock
*BB
: Stmt
->getRegion()->blocks())
215 findReferencesInBlock(References
, Stmt
, BB
);
218 for (auto &Access
: *Stmt
) {
219 if (Access
->isArrayKind()) {
220 auto *BasePtr
= Access
->getScopArrayInfo()->getBasePtr();
221 if (Instruction
*OpInst
= dyn_cast
<Instruction
>(BasePtr
))
222 if (Stmt
->getParent()->contains(OpInst
))
225 References
.Values
.insert(BasePtr
);
229 References
.Values
.insert(References
.BlockGen
.getOrCreateAlloca(*Access
));
235 /// Extract the out-of-scop values and SCEVs referenced from a set describing
238 /// This includes the SCEVUnknowns referenced by the SCEVs used in the
239 /// statement and the base pointers of the memory accesses. For scalar
240 /// statements we force the generation of alloca memory locations and list
241 /// these locations in the set of out-of-scop values as well.
243 /// @param Set A set which references the ScopStmt we are interested in.
244 /// @param UserPtr A void pointer that can be casted to a SubtreeReferences
246 static isl_stat
addReferencesFromStmtSet(isl_set
*Set
, void *UserPtr
) {
247 isl_id
*Id
= isl_set_get_tuple_id(Set
);
248 auto *Stmt
= static_cast<const ScopStmt
*>(isl_id_get_user(Id
));
251 return addReferencesFromStmt(Stmt
, UserPtr
);
254 /// Extract the out-of-scop values and SCEVs referenced from a union set
255 /// referencing multiple ScopStmts.
257 /// This includes the SCEVUnknowns referenced by the SCEVs used in the
258 /// statement and the base pointers of the memory accesses. For scalar
259 /// statements we force the generation of alloca memory locations and list
260 /// these locations in the set of out-of-scop values as well.
262 /// @param USet A union set referencing the ScopStmts we are interested
264 /// @param References The SubtreeReferences data structure through which
265 /// results are returned and further information is
268 addReferencesFromStmtUnionSet(isl_union_set
*USet
,
269 struct SubtreeReferences
&References
) {
270 isl_union_set_foreach_set(USet
, addReferencesFromStmtSet
, &References
);
271 isl_union_set_free(USet
);
274 __isl_give isl_union_map
*
275 IslNodeBuilder::getScheduleForAstNode(__isl_keep isl_ast_node
*For
) {
276 return IslAstInfo::getSchedule(For
);
279 void IslNodeBuilder::getReferencesInSubtree(__isl_keep isl_ast_node
*For
,
280 SetVector
<Value
*> &Values
,
281 SetVector
<const Loop
*> &Loops
) {
283 SetVector
<const SCEV
*> SCEVs
;
284 struct SubtreeReferences References
= {
285 LI
, SE
, S
, ValueMap
, Values
, SCEVs
, getBlockGenerator()};
287 for (const auto &I
: IDToValue
)
288 Values
.insert(I
.second
);
290 for (const auto &I
: OutsideLoopIterations
)
291 Values
.insert(cast
<SCEVUnknown
>(I
.second
)->getValue());
293 isl_union_set
*Schedule
= isl_union_map_domain(getScheduleForAstNode(For
));
294 addReferencesFromStmtUnionSet(Schedule
, References
);
296 for (const SCEV
*Expr
: SCEVs
) {
297 findValues(Expr
, SE
, Values
);
298 findLoops(Expr
, Loops
);
301 Values
.remove_if([](const Value
*V
) { return isa
<GlobalValue
>(V
); });
303 /// Remove loops that contain the scop or that are part of the scop, as they
304 /// are considered local. This leaves only loops that are before the scop, but
305 /// do not contain the scop itself.
306 Loops
.remove_if([this](const Loop
*L
) {
307 return S
.contains(L
) || L
->contains(S
.getEntry());
311 void IslNodeBuilder::updateValues(ValueMapT
&NewValues
) {
312 SmallPtrSet
<Value
*, 5> Inserted
;
314 for (const auto &I
: IDToValue
) {
315 IDToValue
[I
.first
] = NewValues
[I
.second
];
316 Inserted
.insert(I
.second
);
319 for (const auto &I
: NewValues
) {
320 if (Inserted
.count(I
.first
))
323 ValueMap
[I
.first
] = I
.second
;
327 void IslNodeBuilder::createUserVector(__isl_take isl_ast_node
*User
,
328 std::vector
<Value
*> &IVS
,
329 __isl_take isl_id
*IteratorID
,
330 __isl_take isl_union_map
*Schedule
) {
331 isl_ast_expr
*Expr
= isl_ast_node_user_get_expr(User
);
332 isl_ast_expr
*StmtExpr
= isl_ast_expr_get_op_arg(Expr
, 0);
333 isl_id
*Id
= isl_ast_expr_get_id(StmtExpr
);
334 isl_ast_expr_free(StmtExpr
);
335 ScopStmt
*Stmt
= (ScopStmt
*)isl_id_get_user(Id
);
336 std::vector
<LoopToScevMapT
> VLTS(IVS
.size());
338 isl_union_set
*Domain
= isl_union_set_from_set(Stmt
->getDomain());
339 Schedule
= isl_union_map_intersect_domain(Schedule
, Domain
);
340 isl_map
*S
= isl_map_from_union_map(Schedule
);
342 auto *NewAccesses
= createNewAccesses(Stmt
, User
);
343 createSubstitutionsVector(Expr
, Stmt
, VLTS
, IVS
, IteratorID
);
344 VectorBlockGenerator::generate(BlockGen
, *Stmt
, VLTS
, S
, NewAccesses
);
345 isl_id_to_ast_expr_free(NewAccesses
);
348 isl_ast_node_free(User
);
351 void IslNodeBuilder::createMark(__isl_take isl_ast_node
*Node
) {
352 auto *Id
= isl_ast_node_mark_get_id(Node
);
353 auto Child
= isl_ast_node_mark_get_node(Node
);
354 isl_ast_node_free(Node
);
355 // If a child node of a 'SIMD mark' is a loop that has a single iteration,
356 // it will be optimized away and we should skip it.
357 if (!strcmp(isl_id_get_name(Id
), "SIMD") &&
358 isl_ast_node_get_type(Child
) == isl_ast_node_for
) {
359 bool Vector
= PollyVectorizerChoice
== VECTORIZER_POLLY
;
360 int VectorWidth
= getNumberOfIterations(Child
);
361 if (Vector
&& 1 < VectorWidth
&& VectorWidth
<= 16)
362 createForVector(Child
, VectorWidth
);
364 createForSequential(Child
, true);
372 void IslNodeBuilder::createForVector(__isl_take isl_ast_node
*For
,
374 isl_ast_node
*Body
= isl_ast_node_for_get_body(For
);
375 isl_ast_expr
*Init
= isl_ast_node_for_get_init(For
);
376 isl_ast_expr
*Inc
= isl_ast_node_for_get_inc(For
);
377 isl_ast_expr
*Iterator
= isl_ast_node_for_get_iterator(For
);
378 isl_id
*IteratorID
= isl_ast_expr_get_id(Iterator
);
380 Value
*ValueLB
= ExprBuilder
.create(Init
);
381 Value
*ValueInc
= ExprBuilder
.create(Inc
);
383 Type
*MaxType
= ExprBuilder
.getType(Iterator
);
384 MaxType
= ExprBuilder
.getWidestType(MaxType
, ValueLB
->getType());
385 MaxType
= ExprBuilder
.getWidestType(MaxType
, ValueInc
->getType());
387 if (MaxType
!= ValueLB
->getType())
388 ValueLB
= Builder
.CreateSExt(ValueLB
, MaxType
);
389 if (MaxType
!= ValueInc
->getType())
390 ValueInc
= Builder
.CreateSExt(ValueInc
, MaxType
);
392 std::vector
<Value
*> IVS(VectorWidth
);
395 for (int i
= 1; i
< VectorWidth
; i
++)
396 IVS
[i
] = Builder
.CreateAdd(IVS
[i
- 1], ValueInc
, "p_vector_iv");
398 isl_union_map
*Schedule
= getScheduleForAstNode(For
);
399 assert(Schedule
&& "For statement annotation does not contain its schedule");
401 IDToValue
[IteratorID
] = ValueLB
;
403 switch (isl_ast_node_get_type(Body
)) {
404 case isl_ast_node_user
:
405 createUserVector(Body
, IVS
, isl_id_copy(IteratorID
),
406 isl_union_map_copy(Schedule
));
408 case isl_ast_node_block
: {
409 isl_ast_node_list
*List
= isl_ast_node_block_get_children(Body
);
411 for (int i
= 0; i
< isl_ast_node_list_n_ast_node(List
); ++i
)
412 createUserVector(isl_ast_node_list_get_ast_node(List
, i
), IVS
,
413 isl_id_copy(IteratorID
), isl_union_map_copy(Schedule
));
415 isl_ast_node_free(Body
);
416 isl_ast_node_list_free(List
);
420 isl_ast_node_dump(Body
);
421 llvm_unreachable("Unhandled isl_ast_node in vectorizer");
424 IDToValue
.erase(IDToValue
.find(IteratorID
));
425 isl_id_free(IteratorID
);
426 isl_union_map_free(Schedule
);
428 isl_ast_node_free(For
);
429 isl_ast_expr_free(Iterator
);
432 void IslNodeBuilder::createForSequential(__isl_take isl_ast_node
*For
,
433 bool KnownParallel
) {
435 isl_ast_expr
*Init
, *Inc
, *Iterator
, *UB
;
437 Value
*ValueLB
, *ValueUB
, *ValueInc
;
439 BasicBlock
*ExitBlock
;
441 CmpInst::Predicate Predicate
;
444 Parallel
= KnownParallel
|| (IslAstInfo::isParallel(For
) &&
445 !IslAstInfo::isReductionParallel(For
));
447 Body
= isl_ast_node_for_get_body(For
);
449 // isl_ast_node_for_is_degenerate(For)
451 // TODO: For degenerated loops we could generate a plain assignment.
452 // However, for now we just reuse the logic for normal loops, which will
453 // create a loop with a single iteration.
455 Init
= isl_ast_node_for_get_init(For
);
456 Inc
= isl_ast_node_for_get_inc(For
);
457 Iterator
= isl_ast_node_for_get_iterator(For
);
458 IteratorID
= isl_ast_expr_get_id(Iterator
);
459 UB
= getUpperBound(For
, Predicate
);
461 ValueLB
= ExprBuilder
.create(Init
);
462 ValueUB
= ExprBuilder
.create(UB
);
463 ValueInc
= ExprBuilder
.create(Inc
);
465 MaxType
= ExprBuilder
.getType(Iterator
);
466 MaxType
= ExprBuilder
.getWidestType(MaxType
, ValueLB
->getType());
467 MaxType
= ExprBuilder
.getWidestType(MaxType
, ValueUB
->getType());
468 MaxType
= ExprBuilder
.getWidestType(MaxType
, ValueInc
->getType());
470 if (MaxType
!= ValueLB
->getType())
471 ValueLB
= Builder
.CreateSExt(ValueLB
, MaxType
);
472 if (MaxType
!= ValueUB
->getType())
473 ValueUB
= Builder
.CreateSExt(ValueUB
, MaxType
);
474 if (MaxType
!= ValueInc
->getType())
475 ValueInc
= Builder
.CreateSExt(ValueInc
, MaxType
);
477 // If we can show that LB <Predicate> UB holds at least once, we can
478 // omit the GuardBB in front of the loop.
480 !SE
.isKnownPredicate(Predicate
, SE
.getSCEV(ValueLB
), SE
.getSCEV(ValueUB
));
481 IV
= createLoop(ValueLB
, ValueUB
, ValueInc
, Builder
, P
, LI
, DT
, ExitBlock
,
482 Predicate
, &Annotator
, Parallel
, UseGuardBB
);
483 IDToValue
[IteratorID
] = IV
;
487 Annotator
.popLoop(Parallel
);
489 IDToValue
.erase(IDToValue
.find(IteratorID
));
491 Builder
.SetInsertPoint(&ExitBlock
->front());
493 isl_ast_node_free(For
);
494 isl_ast_expr_free(Iterator
);
495 isl_id_free(IteratorID
);
498 /// @brief Remove the BBs contained in a (sub)function from the dominator tree.
500 /// This function removes the basic blocks that are part of a subfunction from
501 /// the dominator tree. Specifically, when generating code it may happen that at
502 /// some point the code generation continues in a new sub-function (e.g., when
503 /// generating OpenMP code). The basic blocks that are created in this
504 /// sub-function are then still part of the dominator tree of the original
505 /// function, such that the dominator tree reaches over function boundaries.
506 /// This is not only incorrect, but also causes crashes. This function now
507 /// removes from the dominator tree all basic blocks that are dominated (and
508 /// consequently reachable) from the entry block of this (sub)function.
510 /// FIXME: A LLVM (function or region) pass should not touch anything outside of
511 /// the function/region it runs on. Hence, the pure need for this function shows
512 /// that we do not comply to this rule. At the moment, this does not cause any
513 /// issues, but we should be aware that such issues may appear. Unfortunately
514 /// the current LLVM pass infrastructure does not allow to make Polly a module
515 /// or call-graph pass to solve this issue, as such a pass would not have access
516 /// to the per-function analyses passes needed by Polly. A future pass manager
517 /// infrastructure is supposed to enable such kind of access possibly allowing
518 /// us to create a cleaner solution here.
520 /// FIXME: Instead of adding the dominance information and then dropping it
521 /// later on, we should try to just not add it in the first place. This requires
522 /// some careful testing to make sure this does not break in interaction with
523 /// the SCEVBuilder and SplitBlock which may rely on the dominator tree or
524 /// which may try to update it.
526 /// @param F The function which contains the BBs to removed.
527 /// @param DT The dominator tree from which to remove the BBs.
528 static void removeSubFuncFromDomTree(Function
*F
, DominatorTree
&DT
) {
529 DomTreeNode
*N
= DT
.getNode(&F
->getEntryBlock());
530 std::vector
<BasicBlock
*> Nodes
;
532 // We can only remove an element from the dominator tree, if all its children
533 // have been removed. To ensure this we obtain the list of nodes to remove
534 // using a post-order tree traversal.
535 for (po_iterator
<DomTreeNode
*> I
= po_begin(N
), E
= po_end(N
); I
!= E
; ++I
)
536 Nodes
.push_back(I
->getBlock());
538 for (BasicBlock
*BB
: Nodes
)
542 void IslNodeBuilder::createForParallel(__isl_take isl_ast_node
*For
) {
544 isl_ast_expr
*Init
, *Inc
, *Iterator
, *UB
;
546 Value
*ValueLB
, *ValueUB
, *ValueInc
;
549 CmpInst::Predicate Predicate
;
551 // The preamble of parallel code interacts different than normal code with
552 // e.g., scalar initialization. Therefore, we ensure the parallel code is
553 // separated from the last basic block.
554 BasicBlock
*ParBB
= SplitBlock(Builder
.GetInsertBlock(),
555 &*Builder
.GetInsertPoint(), &DT
, &LI
);
556 ParBB
->setName("polly.parallel.for");
557 Builder
.SetInsertPoint(&ParBB
->front());
559 Body
= isl_ast_node_for_get_body(For
);
560 Init
= isl_ast_node_for_get_init(For
);
561 Inc
= isl_ast_node_for_get_inc(For
);
562 Iterator
= isl_ast_node_for_get_iterator(For
);
563 IteratorID
= isl_ast_expr_get_id(Iterator
);
564 UB
= getUpperBound(For
, Predicate
);
566 ValueLB
= ExprBuilder
.create(Init
);
567 ValueUB
= ExprBuilder
.create(UB
);
568 ValueInc
= ExprBuilder
.create(Inc
);
570 // OpenMP always uses SLE. In case the isl generated AST uses a SLT
571 // expression, we need to adjust the loop blound by one.
572 if (Predicate
== CmpInst::ICMP_SLT
)
573 ValueUB
= Builder
.CreateAdd(
574 ValueUB
, Builder
.CreateSExt(Builder
.getTrue(), ValueUB
->getType()));
576 MaxType
= ExprBuilder
.getType(Iterator
);
577 MaxType
= ExprBuilder
.getWidestType(MaxType
, ValueLB
->getType());
578 MaxType
= ExprBuilder
.getWidestType(MaxType
, ValueUB
->getType());
579 MaxType
= ExprBuilder
.getWidestType(MaxType
, ValueInc
->getType());
581 if (MaxType
!= ValueLB
->getType())
582 ValueLB
= Builder
.CreateSExt(ValueLB
, MaxType
);
583 if (MaxType
!= ValueUB
->getType())
584 ValueUB
= Builder
.CreateSExt(ValueUB
, MaxType
);
585 if (MaxType
!= ValueInc
->getType())
586 ValueInc
= Builder
.CreateSExt(ValueInc
, MaxType
);
588 BasicBlock::iterator LoopBody
;
590 SetVector
<Value
*> SubtreeValues
;
591 SetVector
<const Loop
*> Loops
;
593 getReferencesInSubtree(For
, SubtreeValues
, Loops
);
595 // Create for all loops we depend on values that contain the current loop
596 // iteration. These values are necessary to generate code for SCEVs that
597 // depend on such loops. As a result we need to pass them to the subfunction.
598 for (const Loop
*L
: Loops
) {
599 const SCEV
*OuterLIV
= SE
.getAddRecExpr(SE
.getUnknown(Builder
.getInt64(0)),
600 SE
.getUnknown(Builder
.getInt64(1)),
601 L
, SCEV::FlagAnyWrap
);
602 Value
*V
= generateSCEV(OuterLIV
);
603 OutsideLoopIterations
[L
] = SE
.getUnknown(V
);
604 SubtreeValues
.insert(V
);
608 ParallelLoopGenerator
ParallelLoopGen(Builder
, P
, LI
, DT
, DL
);
610 IV
= ParallelLoopGen
.createParallelLoop(ValueLB
, ValueUB
, ValueInc
,
611 SubtreeValues
, NewValues
, &LoopBody
);
612 BasicBlock::iterator AfterLoop
= Builder
.GetInsertPoint();
613 Builder
.SetInsertPoint(&*LoopBody
);
615 // Remember the parallel subfunction
616 ParallelSubfunctions
.push_back(LoopBody
->getFunction());
618 // Save the current values.
619 auto ValueMapCopy
= ValueMap
;
620 IslExprBuilder::IDToValueTy IDToValueCopy
= IDToValue
;
622 updateValues(NewValues
);
623 IDToValue
[IteratorID
] = IV
;
625 ValueMapT NewValuesReverse
;
627 for (auto P
: NewValues
)
628 NewValuesReverse
[P
.second
] = P
.first
;
630 Annotator
.addAlternativeAliasBases(NewValuesReverse
);
634 Annotator
.resetAlternativeAliasBases();
635 // Restore the original values.
636 ValueMap
= ValueMapCopy
;
637 IDToValue
= IDToValueCopy
;
639 Builder
.SetInsertPoint(&*AfterLoop
);
640 removeSubFuncFromDomTree((*LoopBody
).getParent()->getParent(), DT
);
642 for (const Loop
*L
: Loops
)
643 OutsideLoopIterations
.erase(L
);
645 isl_ast_node_free(For
);
646 isl_ast_expr_free(Iterator
);
647 isl_id_free(IteratorID
);
650 void IslNodeBuilder::createFor(__isl_take isl_ast_node
*For
) {
651 bool Vector
= PollyVectorizerChoice
== VECTORIZER_POLLY
;
653 if (Vector
&& IslAstInfo::isInnermostParallel(For
) &&
654 !IslAstInfo::isReductionParallel(For
)) {
655 int VectorWidth
= getNumberOfIterations(For
);
656 if (1 < VectorWidth
&& VectorWidth
<= 16) {
657 createForVector(For
, VectorWidth
);
662 if (IslAstInfo::isExecutedInParallel(For
)) {
663 createForParallel(For
);
666 createForSequential(For
, false);
669 void IslNodeBuilder::createIf(__isl_take isl_ast_node
*If
) {
670 isl_ast_expr
*Cond
= isl_ast_node_if_get_cond(If
);
672 Function
*F
= Builder
.GetInsertBlock()->getParent();
673 LLVMContext
&Context
= F
->getContext();
675 BasicBlock
*CondBB
= SplitBlock(Builder
.GetInsertBlock(),
676 &*Builder
.GetInsertPoint(), &DT
, &LI
);
677 CondBB
->setName("polly.cond");
678 BasicBlock
*MergeBB
= SplitBlock(CondBB
, &CondBB
->front(), &DT
, &LI
);
679 MergeBB
->setName("polly.merge");
680 BasicBlock
*ThenBB
= BasicBlock::Create(Context
, "polly.then", F
);
681 BasicBlock
*ElseBB
= BasicBlock::Create(Context
, "polly.else", F
);
683 DT
.addNewBlock(ThenBB
, CondBB
);
684 DT
.addNewBlock(ElseBB
, CondBB
);
685 DT
.changeImmediateDominator(MergeBB
, CondBB
);
687 Loop
*L
= LI
.getLoopFor(CondBB
);
689 L
->addBasicBlockToLoop(ThenBB
, LI
);
690 L
->addBasicBlockToLoop(ElseBB
, LI
);
693 CondBB
->getTerminator()->eraseFromParent();
695 Builder
.SetInsertPoint(CondBB
);
696 Value
*Predicate
= ExprBuilder
.create(Cond
);
697 Builder
.CreateCondBr(Predicate
, ThenBB
, ElseBB
);
698 Builder
.SetInsertPoint(ThenBB
);
699 Builder
.CreateBr(MergeBB
);
700 Builder
.SetInsertPoint(ElseBB
);
701 Builder
.CreateBr(MergeBB
);
702 Builder
.SetInsertPoint(&ThenBB
->front());
704 create(isl_ast_node_if_get_then(If
));
706 Builder
.SetInsertPoint(&ElseBB
->front());
708 if (isl_ast_node_if_has_else(If
))
709 create(isl_ast_node_if_get_else(If
));
711 Builder
.SetInsertPoint(&MergeBB
->front());
713 isl_ast_node_free(If
);
716 __isl_give isl_id_to_ast_expr
*
717 IslNodeBuilder::createNewAccesses(ScopStmt
*Stmt
,
718 __isl_keep isl_ast_node
*Node
) {
719 isl_id_to_ast_expr
*NewAccesses
=
720 isl_id_to_ast_expr_alloc(Stmt
->getParent()->getIslCtx(), 0);
722 auto *Build
= IslAstInfo::getBuild(Node
);
723 assert(Build
&& "Could not obtain isl_ast_build from user node");
724 Stmt
->setAstBuild(Build
);
726 for (auto *MA
: *Stmt
) {
727 if (!MA
->hasNewAccessRelation())
730 auto Schedule
= isl_ast_build_get_schedule(Build
);
731 auto PWAccRel
= MA
->applyScheduleToAccessRelation(Schedule
);
733 auto AccessExpr
= isl_ast_build_access_from_pw_multi_aff(Build
, PWAccRel
);
734 NewAccesses
= isl_id_to_ast_expr_set(NewAccesses
, MA
->getId(), AccessExpr
);
740 void IslNodeBuilder::createSubstitutions(isl_ast_expr
*Expr
, ScopStmt
*Stmt
,
741 LoopToScevMapT
<S
) {
742 assert(isl_ast_expr_get_type(Expr
) == isl_ast_expr_op
&&
743 "Expression of type 'op' expected");
744 assert(isl_ast_expr_get_op_type(Expr
) == isl_ast_op_call
&&
745 "Opertation of type 'call' expected");
746 for (int i
= 0; i
< isl_ast_expr_get_op_n_arg(Expr
) - 1; ++i
) {
747 isl_ast_expr
*SubExpr
;
750 SubExpr
= isl_ast_expr_get_op_arg(Expr
, i
+ 1);
751 V
= ExprBuilder
.create(SubExpr
);
752 ScalarEvolution
*SE
= Stmt
->getParent()->getSE();
753 LTS
[Stmt
->getLoopForDimension(i
)] = SE
->getUnknown(V
);
756 isl_ast_expr_free(Expr
);
759 void IslNodeBuilder::createSubstitutionsVector(
760 __isl_take isl_ast_expr
*Expr
, ScopStmt
*Stmt
,
761 std::vector
<LoopToScevMapT
> &VLTS
, std::vector
<Value
*> &IVS
,
762 __isl_take isl_id
*IteratorID
) {
765 Value
*OldValue
= IDToValue
[IteratorID
];
766 for (Value
*IV
: IVS
) {
767 IDToValue
[IteratorID
] = IV
;
768 createSubstitutions(isl_ast_expr_copy(Expr
), Stmt
, VLTS
[i
]);
772 IDToValue
[IteratorID
] = OldValue
;
773 isl_id_free(IteratorID
);
774 isl_ast_expr_free(Expr
);
777 void IslNodeBuilder::createUser(__isl_take isl_ast_node
*User
) {
782 isl_ast_expr
*Expr
= isl_ast_node_user_get_expr(User
);
783 isl_ast_expr
*StmtExpr
= isl_ast_expr_get_op_arg(Expr
, 0);
784 Id
= isl_ast_expr_get_id(StmtExpr
);
785 isl_ast_expr_free(StmtExpr
);
787 LTS
.insert(OutsideLoopIterations
.begin(), OutsideLoopIterations
.end());
789 Stmt
= (ScopStmt
*)isl_id_get_user(Id
);
790 auto *NewAccesses
= createNewAccesses(Stmt
, User
);
791 createSubstitutions(Expr
, Stmt
, LTS
);
793 if (Stmt
->isBlockStmt())
794 BlockGen
.copyStmt(*Stmt
, LTS
, NewAccesses
);
796 RegionGen
.copyStmt(*Stmt
, LTS
, NewAccesses
);
798 isl_id_to_ast_expr_free(NewAccesses
);
799 isl_ast_node_free(User
);
803 void IslNodeBuilder::createBlock(__isl_take isl_ast_node
*Block
) {
804 isl_ast_node_list
*List
= isl_ast_node_block_get_children(Block
);
806 for (int i
= 0; i
< isl_ast_node_list_n_ast_node(List
); ++i
)
807 create(isl_ast_node_list_get_ast_node(List
, i
));
809 isl_ast_node_free(Block
);
810 isl_ast_node_list_free(List
);
813 void IslNodeBuilder::create(__isl_take isl_ast_node
*Node
) {
814 switch (isl_ast_node_get_type(Node
)) {
815 case isl_ast_node_error
:
816 llvm_unreachable("code generation error");
817 case isl_ast_node_mark
:
820 case isl_ast_node_for
:
823 case isl_ast_node_if
:
826 case isl_ast_node_user
:
829 case isl_ast_node_block
:
834 llvm_unreachable("Unknown isl_ast_node type");
837 bool IslNodeBuilder::materializeValue(isl_id
*Id
) {
838 // If the Id is already mapped, skip it.
839 if (!IDToValue
.count(Id
)) {
840 auto *ParamSCEV
= (const SCEV
*)isl_id_get_user(Id
);
843 // Parameters could refere to invariant loads that need to be
844 // preloaded before we can generate code for the parameter. Thus,
845 // check if any value refered to in ParamSCEV is an invariant load
846 // and if so make sure its equivalence class is preloaded.
847 SetVector
<Value
*> Values
;
848 findValues(ParamSCEV
, SE
, Values
);
849 for (auto *Val
: Values
) {
851 // Check if the value is an instruction in a dead block within the SCoP
852 // and if so do not code generate it.
853 if (auto *Inst
= dyn_cast
<Instruction
>(Val
)) {
854 if (S
.contains(Inst
)) {
857 // Check for "undef" loads first, then if there is a statement for
858 // the parent of Inst and lastly if the parent of Inst has an empty
859 // domain. In the first and last case the instruction is dead but if
860 // there is a statement or the domain is not empty Inst is not dead.
861 auto MemInst
= MemAccInst::dyn_cast(Inst
);
862 auto Address
= MemInst
? MemInst
.getPointerOperand() : nullptr;
864 SE
.getUnknown(UndefValue::get(Address
->getType())) ==
865 SE
.getPointerBase(SE
.getSCEV(Address
))) {
866 } else if (S
.getStmtFor(Inst
)) {
869 auto *Domain
= S
.getDomainConditions(Inst
->getParent());
870 IsDead
= isl_set_is_empty(Domain
);
871 isl_set_free(Domain
);
875 V
= UndefValue::get(ParamSCEV
->getType());
881 if (auto *IAClass
= S
.lookupInvariantEquivClass(Val
)) {
883 // Check if this invariant access class is empty, hence if we never
884 // actually added a loads instruction to it. In that case it has no
885 // (meaningful) users and we should not try to code generate it.
886 if (IAClass
->InvariantAccesses
.empty())
887 V
= UndefValue::get(ParamSCEV
->getType());
889 if (!preloadInvariantEquivClass(*IAClass
)) {
896 V
= V
? V
: generateSCEV(ParamSCEV
);
904 bool IslNodeBuilder::materializeParameters(isl_set
*Set
, bool All
) {
905 for (unsigned i
= 0, e
= isl_set_dim(Set
, isl_dim_param
); i
< e
; ++i
) {
906 if (!All
&& !isl_set_involves_dims(Set
, isl_dim_param
, i
, 1))
908 isl_id
*Id
= isl_set_get_dim_id(Set
, isl_dim_param
, i
);
909 if (!materializeValue(Id
))
915 /// @brief Add the number of dimensions in @p BS to @p U.
916 static isl_stat
countTotalDims(isl_basic_set
*BS
, void *U
) {
917 unsigned *NumTotalDim
= static_cast<unsigned *>(U
);
918 *NumTotalDim
+= isl_basic_set_total_dim(BS
);
919 isl_basic_set_free(BS
);
923 Value
*IslNodeBuilder::preloadUnconditionally(isl_set
*AccessRange
,
924 isl_ast_build
*Build
,
925 Instruction
*AccInst
) {
927 // TODO: This check could be performed in the ScopInfo already.
928 unsigned NumTotalDim
= 0;
929 isl_set_foreach_basic_set(AccessRange
, countTotalDims
, &NumTotalDim
);
930 if (NumTotalDim
> MaxDimensionsInAccessRange
) {
931 isl_set_free(AccessRange
);
935 isl_pw_multi_aff
*PWAccRel
= isl_pw_multi_aff_from_set(AccessRange
);
936 isl_ast_expr
*Access
=
937 isl_ast_build_access_from_pw_multi_aff(Build
, PWAccRel
);
938 auto *Address
= isl_ast_expr_address_of(Access
);
939 auto *AddressValue
= ExprBuilder
.create(Address
);
942 // Correct the type as the SAI might have a different type than the user
943 // expects, especially if the base pointer is a struct.
944 Type
*Ty
= AccInst
->getType();
946 auto *Ptr
= AddressValue
;
947 auto Name
= Ptr
->getName();
948 Ptr
= Builder
.CreatePointerCast(Ptr
, Ty
->getPointerTo(), Name
+ ".cast");
949 PreloadVal
= Builder
.CreateLoad(Ptr
, Name
+ ".load");
950 if (LoadInst
*PreloadInst
= dyn_cast
<LoadInst
>(PreloadVal
))
951 PreloadInst
->setAlignment(dyn_cast
<LoadInst
>(AccInst
)->getAlignment());
953 // TODO: This is only a hot fix for SCoP sequences that use the same load
954 // instruction contained and hoisted by one of the SCoPs.
955 if (SE
.isSCEVable(Ty
))
956 SE
.forgetValue(AccInst
);
961 Value
*IslNodeBuilder::preloadInvariantLoad(const MemoryAccess
&MA
,
964 isl_set
*AccessRange
= isl_map_range(MA
.getAddressFunction());
965 AccessRange
= isl_set_gist_params(AccessRange
, S
.getContext());
967 if (!materializeParameters(AccessRange
, false)) {
968 isl_set_free(AccessRange
);
969 isl_set_free(Domain
);
973 auto *Build
= isl_ast_build_from_context(isl_set_universe(S
.getParamSpace()));
974 isl_set
*Universe
= isl_set_universe(isl_set_get_space(Domain
));
975 bool AlwaysExecuted
= isl_set_is_equal(Domain
, Universe
);
976 isl_set_free(Universe
);
978 Instruction
*AccInst
= MA
.getAccessInstruction();
979 Type
*AccInstTy
= AccInst
->getType();
981 Value
*PreloadVal
= nullptr;
982 if (AlwaysExecuted
) {
983 PreloadVal
= preloadUnconditionally(AccessRange
, Build
, AccInst
);
984 isl_ast_build_free(Build
);
985 isl_set_free(Domain
);
989 if (!materializeParameters(Domain
, false)) {
990 isl_ast_build_free(Build
);
991 isl_set_free(AccessRange
);
992 isl_set_free(Domain
);
996 isl_ast_expr
*DomainCond
= isl_ast_build_expr_from_set(Build
, Domain
);
999 ExprBuilder
.setTrackOverflow(true);
1000 Value
*Cond
= ExprBuilder
.create(DomainCond
);
1001 Value
*OverflowHappened
= Builder
.CreateNot(ExprBuilder
.getOverflowState(),
1002 "polly.preload.cond.overflown");
1003 Cond
= Builder
.CreateAnd(Cond
, OverflowHappened
, "polly.preload.cond.result");
1004 ExprBuilder
.setTrackOverflow(false);
1006 if (!Cond
->getType()->isIntegerTy(1))
1007 Cond
= Builder
.CreateIsNotNull(Cond
);
1009 BasicBlock
*CondBB
= SplitBlock(Builder
.GetInsertBlock(),
1010 &*Builder
.GetInsertPoint(), &DT
, &LI
);
1011 CondBB
->setName("polly.preload.cond");
1013 BasicBlock
*MergeBB
= SplitBlock(CondBB
, &CondBB
->front(), &DT
, &LI
);
1014 MergeBB
->setName("polly.preload.merge");
1016 Function
*F
= Builder
.GetInsertBlock()->getParent();
1017 LLVMContext
&Context
= F
->getContext();
1018 BasicBlock
*ExecBB
= BasicBlock::Create(Context
, "polly.preload.exec", F
);
1020 DT
.addNewBlock(ExecBB
, CondBB
);
1021 if (Loop
*L
= LI
.getLoopFor(CondBB
))
1022 L
->addBasicBlockToLoop(ExecBB
, LI
);
1024 auto *CondBBTerminator
= CondBB
->getTerminator();
1025 Builder
.SetInsertPoint(CondBBTerminator
);
1026 Builder
.CreateCondBr(Cond
, ExecBB
, MergeBB
);
1027 CondBBTerminator
->eraseFromParent();
1029 Builder
.SetInsertPoint(ExecBB
);
1030 Builder
.CreateBr(MergeBB
);
1032 Builder
.SetInsertPoint(ExecBB
->getTerminator());
1033 Value
*PreAccInst
= preloadUnconditionally(AccessRange
, Build
, AccInst
);
1034 Builder
.SetInsertPoint(MergeBB
->getTerminator());
1035 auto *MergePHI
= Builder
.CreatePHI(
1036 AccInstTy
, 2, "polly.preload." + AccInst
->getName() + ".merge");
1037 PreloadVal
= MergePHI
;
1040 PreloadVal
= nullptr;
1041 PreAccInst
= UndefValue::get(AccInstTy
);
1044 MergePHI
->addIncoming(PreAccInst
, ExecBB
);
1045 MergePHI
->addIncoming(Constant::getNullValue(AccInstTy
), CondBB
);
1047 isl_ast_build_free(Build
);
1051 bool IslNodeBuilder::preloadInvariantEquivClass(
1052 InvariantEquivClassTy
&IAClass
) {
1053 // For an equivalence class of invariant loads we pre-load the representing
1054 // element with the unified execution context. However, we have to map all
1055 // elements of the class to the one preloaded load as they are referenced
1056 // during the code generation and therefor need to be mapped.
1057 const MemoryAccessList
&MAs
= IAClass
.InvariantAccesses
;
1061 MemoryAccess
*MA
= MAs
.front();
1062 assert(MA
->isArrayKind() && MA
->isRead());
1064 // If the access function was already mapped, the preload of this equivalence
1065 // class was triggered earlier already and doesn't need to be done again.
1066 if (ValueMap
.count(MA
->getAccessInstruction()))
1069 // Check for recursion which can be caused by additional constraints, e.g.,
1070 // non-finite loop constraints. In such a case we have to bail out and insert
1071 // a "false" runtime check that will cause the original code to be executed.
1072 auto PtrId
= std::make_pair(IAClass
.IdentifyingPointer
, IAClass
.AccessType
);
1073 if (!PreloadedPtrs
.insert(PtrId
).second
)
1076 // The execution context of the IAClass.
1077 isl_set
*&ExecutionCtx
= IAClass
.ExecutionContext
;
1079 // If the base pointer of this class is dependent on another one we have to
1080 // make sure it was preloaded already.
1081 auto *SAI
= MA
->getScopArrayInfo();
1082 if (auto *BaseIAClass
= S
.lookupInvariantEquivClass(SAI
->getBasePtr())) {
1083 if (!preloadInvariantEquivClass(*BaseIAClass
))
1086 // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx and
1087 // we need to refine the ExecutionCtx.
1088 isl_set
*BaseExecutionCtx
= isl_set_copy(BaseIAClass
->ExecutionContext
);
1089 ExecutionCtx
= isl_set_intersect(ExecutionCtx
, BaseExecutionCtx
);
1092 Instruction
*AccInst
= MA
->getAccessInstruction();
1093 Type
*AccInstTy
= AccInst
->getType();
1095 Value
*PreloadVal
= preloadInvariantLoad(*MA
, isl_set_copy(ExecutionCtx
));
1099 for (const MemoryAccess
*MA
: MAs
) {
1100 Instruction
*MAAccInst
= MA
->getAccessInstruction();
1101 assert(PreloadVal
->getType() == MAAccInst
->getType());
1102 ValueMap
[MAAccInst
] = PreloadVal
;
1105 if (SE
.isSCEVable(AccInstTy
)) {
1106 isl_id
*ParamId
= S
.getIdForParam(SE
.getSCEV(AccInst
));
1108 IDToValue
[ParamId
] = PreloadVal
;
1109 isl_id_free(ParamId
);
1112 BasicBlock
*EntryBB
= &Builder
.GetInsertBlock()->getParent()->getEntryBlock();
1113 auto *Alloca
= new AllocaInst(AccInstTy
, AccInst
->getName() + ".preload.s2a");
1114 Alloca
->insertBefore(&*EntryBB
->getFirstInsertionPt());
1115 Builder
.CreateStore(PreloadVal
, Alloca
);
1117 for (auto *DerivedSAI
: SAI
->getDerivedSAIs()) {
1118 Value
*BasePtr
= DerivedSAI
->getBasePtr();
1120 for (const MemoryAccess
*MA
: MAs
) {
1121 // As the derived SAI information is quite coarse, any load from the
1122 // current SAI could be the base pointer of the derived SAI, however we
1123 // should only change the base pointer of the derived SAI if we actually
1125 if (BasePtr
== MA
->getBaseAddr()) {
1126 assert(BasePtr
->getType() == PreloadVal
->getType());
1127 DerivedSAI
->setBasePtr(PreloadVal
);
1130 // For scalar derived SAIs we remap the alloca used for the derived value.
1131 if (BasePtr
== MA
->getAccessInstruction()) {
1132 if (DerivedSAI
->isPHIKind())
1133 PHIOpMap
[BasePtr
] = Alloca
;
1135 ScalarMap
[BasePtr
] = Alloca
;
1140 for (const MemoryAccess
*MA
: MAs
) {
1142 Instruction
*MAAccInst
= MA
->getAccessInstruction();
1143 // Use the escape system to get the correct value to users outside the SCoP.
1144 BlockGenerator::EscapeUserVectorTy EscapeUsers
;
1145 for (auto *U
: MAAccInst
->users())
1146 if (Instruction
*UI
= dyn_cast
<Instruction
>(U
))
1147 if (!S
.contains(UI
))
1148 EscapeUsers
.push_back(UI
);
1150 if (EscapeUsers
.empty())
1153 EscapeMap
[MA
->getAccessInstruction()] =
1154 std::make_pair(Alloca
, std::move(EscapeUsers
));
1160 void IslNodeBuilder::allocateNewArrays() {
1161 for (auto &SAI
: S
.arrays()) {
1162 if (SAI
->getBasePtr())
1165 Type
*NewArrayType
= nullptr;
1166 for (unsigned i
= SAI
->getNumberOfDimensions() - 1; i
>= 1; i
--) {
1167 auto *DimSize
= SAI
->getDimensionSize(i
);
1168 unsigned UnsignedDimSize
= static_cast<const SCEVConstant
*>(DimSize
)
1173 NewArrayType
= SAI
->getElementType();
1175 NewArrayType
= ArrayType::get(NewArrayType
, UnsignedDimSize
);
1179 Builder
.GetInsertBlock()->getParent()->getEntryBlock().getTerminator();
1180 Value
*CreatedArray
=
1181 new AllocaInst(NewArrayType
, SAI
->getName(), &*InstIt
);
1182 SAI
->setBasePtr(CreatedArray
);
1186 bool IslNodeBuilder::preloadInvariantLoads() {
1188 auto &InvariantEquivClasses
= S
.getInvariantAccesses();
1189 if (InvariantEquivClasses
.empty())
1192 BasicBlock
*PreLoadBB
= SplitBlock(Builder
.GetInsertBlock(),
1193 &*Builder
.GetInsertPoint(), &DT
, &LI
);
1194 PreLoadBB
->setName("polly.preload.begin");
1195 Builder
.SetInsertPoint(&PreLoadBB
->front());
1197 for (auto &IAClass
: InvariantEquivClasses
)
1198 if (!preloadInvariantEquivClass(IAClass
))
1204 void IslNodeBuilder::addParameters(__isl_take isl_set
*Context
) {
1206 // Materialize values for the parameters of the SCoP.
1207 materializeParameters(Context
, /* all */ true);
1209 // Generate values for the current loop iteration for all surrounding loops.
1211 // We may also reference loops outside of the scop which do not contain the
1212 // scop itself, but as the number of such scops may be arbitrarily large we do
1213 // not generate code for them here, but only at the point of code generation
1214 // where these values are needed.
1215 Loop
*L
= LI
.getLoopFor(S
.getEntry());
1217 while (L
!= nullptr && S
.contains(L
))
1218 L
= L
->getParentLoop();
1220 while (L
!= nullptr) {
1221 const SCEV
*OuterLIV
= SE
.getAddRecExpr(SE
.getUnknown(Builder
.getInt64(0)),
1222 SE
.getUnknown(Builder
.getInt64(1)),
1223 L
, SCEV::FlagAnyWrap
);
1224 Value
*V
= generateSCEV(OuterLIV
);
1225 OutsideLoopIterations
[L
] = SE
.getUnknown(V
);
1226 L
= L
->getParentLoop();
1229 isl_set_free(Context
);
1232 Value
*IslNodeBuilder::generateSCEV(const SCEV
*Expr
) {
1233 Instruction
*InsertLocation
= &*--(Builder
.GetInsertBlock()->end());
1234 return expandCodeFor(S
, SE
, DL
, "polly", Expr
, Expr
->getType(),
1235 InsertLocation
, &ValueMap
);