1//===- IslNodeBuilder.cpp - Translate an isl AST into a LLVM-IR AST -------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains the IslNodeBuilder, a class to translate an isl AST into
10// a LLVM-IR AST.
11//
12//===----------------------------------------------------------------------===//
13
14#include "polly/CodeGen/IslNodeBuilder.h"
15#include "polly/CodeGen/BlockGenerators.h"
16#include "polly/CodeGen/CodeGeneration.h"
17#include "polly/CodeGen/IslAst.h"
18#include "polly/CodeGen/IslExprBuilder.h"
19#include "polly/CodeGen/LoopGeneratorsGOMP.h"
20#include "polly/CodeGen/LoopGeneratorsKMP.h"
21#include "polly/CodeGen/RuntimeDebugBuilder.h"
22#include "polly/Options.h"
23#include "polly/ScopInfo.h"
24#include "polly/Support/ISLTools.h"
25#include "polly/Support/SCEVValidator.h"
26#include "polly/Support/ScopHelper.h"
27#include "polly/Support/VirtualInstruction.h"
28#include "llvm/ADT/APInt.h"
29#include "llvm/ADT/PostOrderIterator.h"
30#include "llvm/ADT/SetVector.h"
31#include "llvm/ADT/SmallPtrSet.h"
32#include "llvm/ADT/Statistic.h"
33#include "llvm/Analysis/LoopInfo.h"
34#include "llvm/Analysis/RegionInfo.h"
35#include "llvm/Analysis/ScalarEvolution.h"
36#include "llvm/Analysis/ScalarEvolutionExpressions.h"
37#include "llvm/IR/BasicBlock.h"
38#include "llvm/IR/Constant.h"
39#include "llvm/IR/Constants.h"
40#include "llvm/IR/DataLayout.h"
41#include "llvm/IR/DerivedTypes.h"
42#include "llvm/IR/Dominators.h"
43#include "llvm/IR/Function.h"
44#include "llvm/IR/InstrTypes.h"
45#include "llvm/IR/Instruction.h"
46#include "llvm/IR/Instructions.h"
47#include "llvm/IR/Type.h"
48#include "llvm/IR/Value.h"
49#include "llvm/Support/Casting.h"
50#include "llvm/Support/CommandLine.h"
51#include "llvm/Support/ErrorHandling.h"
52#include "llvm/Transforms/Utils/BasicBlockUtils.h"
53#include "isl/aff.h"
54#include "isl/aff_type.h"
55#include "isl/ast.h"
56#include "isl/ast_build.h"
57#include "isl/isl-noexceptions.h"
58#include "isl/map.h"
59#include "isl/set.h"
60#include "isl/union_map.h"
61#include "isl/union_set.h"
62#include "isl/val.h"
63#include <algorithm>
64#include <cassert>
65#include <cstdint>
66#include <cstring>
67#include <string>
68#include <utility>
69#include <vector>
70
71using namespace llvm;
72using namespace polly;
73
74#define DEBUG_TYPE "polly-codegen"
75
76STATISTIC(VersionedScops, "Number of SCoPs that required versioning.");
77
78STATISTIC(SequentialLoops, "Number of generated sequential for-loops");
79STATISTIC(ParallelLoops, "Number of generated parallel for-loops");
80STATISTIC(IfConditions, "Number of generated if-conditions");
81
82/// OpenMP backend options
83enum class OpenMPBackend { GNU, LLVM };
84
85static cl::opt<bool> PollyGenerateRTCPrint(
86 "polly-codegen-emit-rtc-print",
87 cl::desc("Emit code that prints the runtime check result dynamically."),
88 cl::Hidden, cl::cat(PollyCategory));
89
90// If this option is set we always use the isl AST generator to regenerate
91// memory accesses. Without this option set we regenerate expressions using the
92// original SCEV expressions and only generate new expressions in case the
93// access relation has been changed and consequently must be regenerated.
94static cl::opt<bool> PollyGenerateExpressions(
95 "polly-codegen-generate-expressions",
96 cl::desc("Generate AST expressions for unmodified and modified accesses"),
97 cl::Hidden, cl::cat(PollyCategory));
98
99static cl::opt<int> PollyTargetFirstLevelCacheLineSize(
100 "polly-target-first-level-cache-line-size",
101 cl::desc("The size of the first level cache line size specified in bytes."),
102 cl::Hidden, cl::init(Val: 64), cl::cat(PollyCategory));
103
104static cl::opt<OpenMPBackend> PollyOmpBackend(
105 "polly-omp-backend", cl::desc("Choose the OpenMP library to use:"),
106 cl::values(clEnumValN(OpenMPBackend::GNU, "GNU", "GNU OpenMP"),
107 clEnumValN(OpenMPBackend::LLVM, "LLVM", "LLVM OpenMP")),
108 cl::Hidden, cl::init(Val: OpenMPBackend::GNU), cl::cat(PollyCategory));
109
110isl::ast_expr IslNodeBuilder::getUpperBound(isl::ast_node_for For,
111 ICmpInst::Predicate &Predicate) {
112 isl::ast_expr Cond = For.cond();
113 isl::ast_expr Iterator = For.iterator();
114 assert(isl_ast_expr_get_type(Cond.get()) == isl_ast_expr_op &&
115 "conditional expression is not an atomic upper bound");
116
117 isl_ast_op_type OpType = isl_ast_expr_get_op_type(expr: Cond.get());
118
119 switch (OpType) {
120 case isl_ast_op_le:
121 Predicate = ICmpInst::ICMP_SLE;
122 break;
123 case isl_ast_op_lt:
124 Predicate = ICmpInst::ICMP_SLT;
125 break;
126 default:
127 llvm_unreachable("Unexpected comparison type in loop condition");
128 }
129
130 isl::ast_expr Arg0 = Cond.get_op_arg(pos: 0);
131
132 assert(isl_ast_expr_get_type(Arg0.get()) == isl_ast_expr_id &&
133 "conditional expression is not an atomic upper bound");
134
135 isl::id UBID = Arg0.get_id();
136
137 assert(isl_ast_expr_get_type(Iterator.get()) == isl_ast_expr_id &&
138 "Could not get the iterator");
139
140 isl::id IteratorID = Iterator.get_id();
141
142 assert(UBID.get() == IteratorID.get() &&
143 "conditional expression is not an atomic upper bound");
144
145 return Cond.get_op_arg(pos: 1);
146}
147
148int IslNodeBuilder::getNumberOfIterations(isl::ast_node_for For) {
149 assert(isl_ast_node_get_type(For.get()) == isl_ast_node_for);
150 isl::ast_node Body = For.body();
151
152 // First, check if we can actually handle this code.
153 switch (isl_ast_node_get_type(node: Body.get())) {
154 case isl_ast_node_user:
155 break;
156 case isl_ast_node_block: {
157 isl::ast_node_block BodyBlock = Body.as<isl::ast_node_block>();
158 isl::ast_node_list List = BodyBlock.children();
159 for (isl::ast_node Node : List) {
160 isl_ast_node_type NodeType = isl_ast_node_get_type(node: Node.get());
161 if (NodeType != isl_ast_node_user)
162 return -1;
163 }
164 break;
165 }
166 default:
167 return -1;
168 }
169
170 isl::ast_expr Init = For.init();
171 if (!Init.isa<isl::ast_expr_int>() || !Init.val().is_zero())
172 return -1;
173 isl::ast_expr Inc = For.inc();
174 if (!Inc.isa<isl::ast_expr_int>() || !Inc.val().is_one())
175 return -1;
176 CmpInst::Predicate Predicate;
177 isl::ast_expr UB = getUpperBound(For, Predicate);
178 if (!UB.isa<isl::ast_expr_int>())
179 return -1;
180 isl::val UpVal = UB.get_val();
181 int NumberIterations = UpVal.get_num_si();
182 if (NumberIterations < 0)
183 return -1;
184 if (Predicate == CmpInst::ICMP_SLT)
185 return NumberIterations;
186 else
187 return NumberIterations + 1;
188}
189
190static void findReferencesByUse(Value *SrcVal, ScopStmt *UserStmt,
191 Loop *UserScope, const ValueMapT &GlobalMap,
192 SetVector<Value *> &Values,
193 SetVector<const SCEV *> &SCEVs) {
194 VirtualUse VUse = VirtualUse::create(UserStmt, UserScope, Val: SrcVal, Virtual: true);
195 switch (VUse.getKind()) {
196 case VirtualUse::Constant:
197 // When accelerator-offloading, GlobalValue is a host address whose content
198 // must still be transferred to the GPU.
199 if (isa<GlobalValue>(Val: SrcVal))
200 Values.insert(X: SrcVal);
201 break;
202
203 case VirtualUse::Synthesizable:
204 SCEVs.insert(X: VUse.getScevExpr());
205 return;
206
207 case VirtualUse::Block:
208 case VirtualUse::ReadOnly:
209 case VirtualUse::Hoisted:
210 case VirtualUse::Intra:
211 case VirtualUse::Inter:
212 break;
213 }
214
215 if (Value *NewVal = GlobalMap.lookup(Val: SrcVal))
216 Values.insert(X: NewVal);
217}
218
219static void findReferencesInInst(Instruction *Inst, ScopStmt *UserStmt,
220 Loop *UserScope, const ValueMapT &GlobalMap,
221 SetVector<Value *> &Values,
222 SetVector<const SCEV *> &SCEVs) {
223 for (Use &U : Inst->operands())
224 findReferencesByUse(SrcVal: U.get(), UserStmt, UserScope, GlobalMap, Values, SCEVs);
225}
226
227static void findReferencesInStmt(ScopStmt *Stmt, SetVector<Value *> &Values,
228 ValueMapT &GlobalMap,
229 SetVector<const SCEV *> &SCEVs) {
230 LoopInfo *LI = Stmt->getParent()->getLI();
231
232 BasicBlock *BB = Stmt->getBasicBlock();
233 Loop *Scope = LI->getLoopFor(BB);
234 for (Instruction *Inst : Stmt->getInstructions())
235 findReferencesInInst(Inst, UserStmt: Stmt, UserScope: Scope, GlobalMap, Values, SCEVs);
236
237 if (Stmt->isRegionStmt()) {
238 for (BasicBlock *BB : Stmt->getRegion()->blocks()) {
239 Loop *Scope = LI->getLoopFor(BB);
240 for (Instruction &Inst : *BB)
241 findReferencesInInst(Inst: &Inst, UserStmt: Stmt, UserScope: Scope, GlobalMap, Values, SCEVs);
242 }
243 }
244}
245
246void polly::addReferencesFromStmt(ScopStmt *Stmt, void *UserPtr,
247 bool CreateScalarRefs) {
248 auto &References = *static_cast<SubtreeReferences *>(UserPtr);
249
250 findReferencesInStmt(Stmt, Values&: References.Values, GlobalMap&: References.GlobalMap,
251 SCEVs&: References.SCEVs);
252
253 for (auto &Access : *Stmt) {
254 if (References.ParamSpace) {
255 isl::space ParamSpace = Access->getLatestAccessRelation().get_space();
256 (*References.ParamSpace) =
257 References.ParamSpace->align_params(space2: ParamSpace);
258 }
259
260 if (Access->isLatestArrayKind()) {
261 auto *BasePtr = Access->getLatestScopArrayInfo()->getBasePtr();
262 if (Instruction *OpInst = dyn_cast<Instruction>(Val: BasePtr))
263 if (Stmt->getParent()->contains(I: OpInst))
264 continue;
265
266 References.Values.insert(X: BasePtr);
267 continue;
268 }
269
270 if (CreateScalarRefs)
271 References.Values.insert(X: References.BlockGen.getOrCreateAlloca(Access: *Access));
272 }
273}
274
275/// Extract the out-of-scop values and SCEVs referenced from a set describing
276/// a ScopStmt.
277///
278/// This includes the SCEVUnknowns referenced by the SCEVs used in the
279/// statement and the base pointers of the memory accesses. For scalar
280/// statements we force the generation of alloca memory locations and list
281/// these locations in the set of out-of-scop values as well.
282///
283/// @param Set A set which references the ScopStmt we are interested in.
284/// @param UserPtr A void pointer that can be casted to a SubtreeReferences
285/// structure.
286static void addReferencesFromStmtSet(isl::set Set, SubtreeReferences *UserPtr) {
287 isl::id Id = Set.get_tuple_id();
288 auto *Stmt = static_cast<ScopStmt *>(Id.get_user());
289 addReferencesFromStmt(Stmt, UserPtr);
290}
291
292/// Extract the out-of-scop values and SCEVs referenced from a union set
293/// referencing multiple ScopStmts.
294///
295/// This includes the SCEVUnknowns referenced by the SCEVs used in the
296/// statement and the base pointers of the memory accesses. For scalar
297/// statements we force the generation of alloca memory locations and list
298/// these locations in the set of out-of-scop values as well.
299///
300/// @param USet A union set referencing the ScopStmts we are interested
301/// in.
302/// @param References The SubtreeReferences data structure through which
303/// results are returned and further information is
304/// provided.
305static void addReferencesFromStmtUnionSet(isl::union_set USet,
306 SubtreeReferences &References) {
307
308 for (isl::set Set : USet.get_set_list())
309 addReferencesFromStmtSet(Set, UserPtr: &References);
310}
311
312isl::union_map
313IslNodeBuilder::getScheduleForAstNode(const isl::ast_node &Node) {
314 return IslAstInfo::getSchedule(Node);
315}
316
317void IslNodeBuilder::getReferencesInSubtree(const isl::ast_node &For,
318 SetVector<Value *> &Values,
319 SetVector<const Loop *> &Loops) {
320 SetVector<const SCEV *> SCEVs;
321 SubtreeReferences References = {
322 .LI: LI, .SE: SE, .S: S, .GlobalMap: ValueMap, .Values: Values, .SCEVs: SCEVs, .BlockGen: getBlockGenerator(), .ParamSpace: nullptr};
323
324 for (const auto &I : IDToValue)
325 Values.insert(X: I.second);
326
327 // NOTE: this is populated in IslNodeBuilder::addParameters
328 for (const auto &I : OutsideLoopIterations)
329 Values.insert(X: cast<SCEVUnknown>(Val: I.second)->getValue());
330
331 isl::union_set Schedule = getScheduleForAstNode(Node: For).domain();
332 addReferencesFromStmtUnionSet(USet: Schedule, References);
333
334 for (const SCEV *Expr : SCEVs) {
335 findValues(Expr, SE, Values);
336 findLoops(Expr, Loops);
337 }
338
339 Values.remove_if(P: [](const Value *V) { return isa<GlobalValue>(Val: V); });
340
341 /// Note: Code generation of induction variables of loops outside Scops
342 ///
343 /// Remove loops that contain the scop or that are part of the scop, as they
344 /// are considered local. This leaves only loops that are before the scop, but
345 /// do not contain the scop itself.
346 /// We ignore loops perfectly contained in the Scop because these are already
347 /// generated at `IslNodeBuilder::addParameters`. These `Loops` are loops
348 /// whose induction variables are referred to by the Scop, but the Scop is not
349 /// fully contained in these Loops. Since there can be many of these,
350 /// we choose to codegen these on-demand.
351 /// @see IslNodeBuilder::materializeNonScopLoopInductionVariable.
352 Loops.remove_if(P: [this](const Loop *L) {
353 return S.contains(L) || L->contains(BB: S.getEntry());
354 });
355
356 // Contains Values that may need to be replaced with other values
357 // due to replacements from the ValueMap. We should make sure
358 // that we return correctly remapped values.
359 // NOTE: this code path is tested by:
360 // 1. test/Isl/CodeGen/OpenMP/single_loop_with_loop_invariant_baseptr.ll
361 // 2. test/Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll
362 SetVector<Value *> ReplacedValues;
363 for (Value *V : Values) {
364 ReplacedValues.insert(X: getLatestValue(Original: V));
365 }
366 Values = ReplacedValues;
367}
368
369void IslNodeBuilder::updateValues(ValueMapT &NewValues) {
370 SmallPtrSet<Value *, 5> Inserted;
371
372 for (const auto &I : IDToValue) {
373 IDToValue[I.first] = NewValues[I.second];
374 Inserted.insert(Ptr: I.second);
375 }
376
377 for (const auto &I : NewValues) {
378 if (Inserted.count(Ptr: I.first))
379 continue;
380
381 ValueMap[I.first] = I.second;
382 }
383}
384
385Value *IslNodeBuilder::getLatestValue(Value *Original) const {
386 auto It = ValueMap.find(Val: Original);
387 if (It == ValueMap.end())
388 return Original;
389 return It->second;
390}
391
392void IslNodeBuilder::createMark(__isl_take isl_ast_node *Node) {
393 auto *Id = isl_ast_node_mark_get_id(node: Node);
394 auto Child = isl_ast_node_mark_get_node(node: Node);
395 isl_ast_node_free(node: Node);
396 // If a child node of a 'SIMD mark' is a loop that has a single iteration,
397 // it will be optimized away and we should skip it.
398 if (strcmp(s1: isl_id_get_name(id: Id), s2: "SIMD") == 0 &&
399 isl_ast_node_get_type(node: Child) == isl_ast_node_for) {
400 createForSequential(For: isl::manage(ptr: Child).as<isl::ast_node_for>(), MarkParallel: true);
401 isl_id_free(id: Id);
402 return;
403 }
404
405 BandAttr *ChildLoopAttr = getLoopAttr(Id: isl::manage_copy(ptr: Id));
406 BandAttr *AncestorLoopAttr;
407 if (ChildLoopAttr) {
408 // Save current LoopAttr environment to restore again when leaving this
409 // subtree. This means there was no loop between the ancestor LoopAttr and
410 // this mark, i.e. the ancestor LoopAttr did not directly mark a loop. This
411 // can happen e.g. if the AST build peeled or unrolled the loop.
412 AncestorLoopAttr = Annotator.getStagingAttrEnv();
413
414 Annotator.getStagingAttrEnv() = ChildLoopAttr;
415 }
416
417 create(Node: Child);
418
419 if (ChildLoopAttr) {
420 assert(Annotator.getStagingAttrEnv() == ChildLoopAttr &&
421 "Nest must not overwrite loop attr environment");
422 Annotator.getStagingAttrEnv() = AncestorLoopAttr;
423 }
424
425 isl_id_free(id: Id);
426}
427
428/// Restore the initial ordering of dimensions of the band node
429///
430/// In case the band node represents all the dimensions of the iteration
431/// domain, recreate the band node to restore the initial ordering of the
432/// dimensions.
433///
434/// @param Node The band node to be modified.
435/// @return The modified schedule node.
436static bool IsLoopVectorizerDisabled(isl::ast_node_for Node) {
437 assert(isl_ast_node_get_type(Node.get()) == isl_ast_node_for);
438 isl::ast_node Body = Node.body();
439 if (isl_ast_node_get_type(node: Body.get()) != isl_ast_node_mark)
440 return false;
441
442 isl::ast_node_mark BodyMark = Body.as<isl::ast_node_mark>();
443 auto Id = BodyMark.id();
444 if (strcmp(s1: Id.get_name().c_str(), s2: "Loop Vectorizer Disabled") == 0)
445 return true;
446 return false;
447}
448
449void IslNodeBuilder::createForSequential(isl::ast_node_for For,
450 bool MarkParallel) {
451 Value *ValueLB, *ValueUB, *ValueInc;
452 Type *MaxType;
453 BasicBlock *ExitBlock;
454 Value *IV;
455 CmpInst::Predicate Predicate;
456
457 bool LoopVectorizerDisabled = IsLoopVectorizerDisabled(Node: For);
458
459 isl::ast_node Body = For.body();
460
461 // isl_ast_node_for_is_degenerate(For)
462 //
463 // TODO: For degenerated loops we could generate a plain assignment.
464 // However, for now we just reuse the logic for normal loops, which will
465 // create a loop with a single iteration.
466
467 isl::ast_expr Init = For.init();
468 isl::ast_expr Inc = For.inc();
469 isl::ast_expr Iterator = For.iterator();
470 isl::id IteratorID = Iterator.get_id();
471 isl::ast_expr UB = getUpperBound(For, Predicate);
472
473 ValueLB = ExprBuilder.create(Expr: Init.release());
474 ValueUB = ExprBuilder.create(Expr: UB.release());
475 ValueInc = ExprBuilder.create(Expr: Inc.release());
476
477 MaxType = ExprBuilder.getType(Expr: Iterator.get());
478 MaxType = ExprBuilder.getWidestType(T1: MaxType, T2: ValueLB->getType());
479 MaxType = ExprBuilder.getWidestType(T1: MaxType, T2: ValueUB->getType());
480 MaxType = ExprBuilder.getWidestType(T1: MaxType, T2: ValueInc->getType());
481
482 if (MaxType != ValueLB->getType())
483 ValueLB = Builder.CreateSExt(V: ValueLB, DestTy: MaxType);
484 if (MaxType != ValueUB->getType())
485 ValueUB = Builder.CreateSExt(V: ValueUB, DestTy: MaxType);
486 if (MaxType != ValueInc->getType())
487 ValueInc = Builder.CreateSExt(V: ValueInc, DestTy: MaxType);
488
489 // If we can show that LB <Predicate> UB holds at least once, we can
490 // omit the GuardBB in front of the loop.
491 bool UseGuardBB =
492 !SE.isKnownPredicate(Pred: Predicate, LHS: SE.getSCEV(V: ValueLB), RHS: SE.getSCEV(V: ValueUB));
493 IV = createLoop(LowerBound: ValueLB, UpperBound: ValueUB, Stride: ValueInc, Builder, LI, DT, ExitBlock,
494 Predicate, Annotator: &Annotator, Parallel: MarkParallel, UseGuard: UseGuardBB,
495 LoopVectDisabled: LoopVectorizerDisabled);
496 IDToValue[IteratorID.get()] = IV;
497
498 create(Node: Body.release());
499
500 Annotator.popLoop(isParallel: MarkParallel);
501
502 IDToValue.erase(Iterator: IDToValue.find(Key: IteratorID.get()));
503
504 Builder.SetInsertPoint(&ExitBlock->front());
505
506 SequentialLoops++;
507}
508
509/// Remove the BBs contained in a (sub)function from the dominator tree.
510///
511/// This function removes the basic blocks that are part of a subfunction from
512/// the dominator tree. Specifically, when generating code it may happen that at
513/// some point the code generation continues in a new sub-function (e.g., when
514/// generating OpenMP code). The basic blocks that are created in this
515/// sub-function are then still part of the dominator tree of the original
516/// function, such that the dominator tree reaches over function boundaries.
517/// This is not only incorrect, but also causes crashes. This function now
518/// removes from the dominator tree all basic blocks that are dominated (and
519/// consequently reachable) from the entry block of this (sub)function.
520///
521/// FIXME: A LLVM (function or region) pass should not touch anything outside of
522/// the function/region it runs on. Hence, the pure need for this function shows
523/// that we do not comply to this rule. At the moment, this does not cause any
524/// issues, but we should be aware that such issues may appear. Unfortunately
525/// the current LLVM pass infrastructure does not allow to make Polly a module
526/// or call-graph pass to solve this issue, as such a pass would not have access
527/// to the per-function analyses passes needed by Polly. A future pass manager
528/// infrastructure is supposed to enable such kind of access possibly allowing
529/// us to create a cleaner solution here.
530///
531/// FIXME: Instead of adding the dominance information and then dropping it
532/// later on, we should try to just not add it in the first place. This requires
533/// some careful testing to make sure this does not break in interaction with
534/// the SCEVBuilder and SplitBlock which may rely on the dominator tree or
535/// which may try to update it.
536///
537/// @param F The function which contains the BBs to removed.
538/// @param DT The dominator tree from which to remove the BBs.
539static void removeSubFuncFromDomTree(Function *F, DominatorTree &DT) {
540 DomTreeNode *N = DT.getNode(BB: &F->getEntryBlock());
541 std::vector<BasicBlock *> Nodes;
542
543 // We can only remove an element from the dominator tree, if all its children
544 // have been removed. To ensure this we obtain the list of nodes to remove
545 // using a post-order tree traversal.
546 for (po_iterator<DomTreeNode *> I = po_begin(G: N), E = po_end(G: N); I != E; ++I)
547 Nodes.push_back(x: I->getBlock());
548
549 for (BasicBlock *BB : Nodes)
550 DT.eraseNode(BB);
551}
552
553void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) {
554 isl_ast_node *Body;
555 isl_ast_expr *Init, *Inc, *Iterator, *UB;
556 isl_id *IteratorID;
557 Value *ValueLB, *ValueUB, *ValueInc;
558 Type *MaxType;
559 Value *IV;
560 CmpInst::Predicate Predicate;
561
562 // The preamble of parallel code interacts different than normal code with
563 // e.g., scalar initialization. Therefore, we ensure the parallel code is
564 // separated from the last basic block.
565 BasicBlock *ParBB = SplitBlock(Old: Builder.GetInsertBlock(),
566 SplitPt: &*Builder.GetInsertPoint(), DT: &DT, LI: &LI);
567 ParBB->setName("polly.parallel.for");
568 Builder.SetInsertPoint(&ParBB->front());
569
570 Body = isl_ast_node_for_get_body(node: For);
571 Init = isl_ast_node_for_get_init(node: For);
572 Inc = isl_ast_node_for_get_inc(node: For);
573 Iterator = isl_ast_node_for_get_iterator(node: For);
574 IteratorID = isl_ast_expr_get_id(expr: Iterator);
575 UB = getUpperBound(For: isl::manage_copy(ptr: For).as<isl::ast_node_for>(), Predicate)
576 .release();
577
578 ValueLB = ExprBuilder.create(Expr: Init);
579 ValueUB = ExprBuilder.create(Expr: UB);
580 ValueInc = ExprBuilder.create(Expr: Inc);
581
582 // OpenMP always uses SLE. In case the isl generated AST uses a SLT
583 // expression, we need to adjust the loop bound by one.
584 if (Predicate == CmpInst::ICMP_SLT)
585 ValueUB = Builder.CreateAdd(
586 LHS: ValueUB, RHS: Builder.CreateSExt(V: Builder.getTrue(), DestTy: ValueUB->getType()));
587
588 MaxType = ExprBuilder.getType(Expr: Iterator);
589 MaxType = ExprBuilder.getWidestType(T1: MaxType, T2: ValueLB->getType());
590 MaxType = ExprBuilder.getWidestType(T1: MaxType, T2: ValueUB->getType());
591 MaxType = ExprBuilder.getWidestType(T1: MaxType, T2: ValueInc->getType());
592
593 if (MaxType != ValueLB->getType())
594 ValueLB = Builder.CreateSExt(V: ValueLB, DestTy: MaxType);
595 if (MaxType != ValueUB->getType())
596 ValueUB = Builder.CreateSExt(V: ValueUB, DestTy: MaxType);
597 if (MaxType != ValueInc->getType())
598 ValueInc = Builder.CreateSExt(V: ValueInc, DestTy: MaxType);
599
600 BasicBlock::iterator LoopBody;
601
602 SetVector<Value *> SubtreeValues;
603 SetVector<const Loop *> Loops;
604
605 getReferencesInSubtree(For: isl::manage_copy(ptr: For), Values&: SubtreeValues, Loops);
606
607 // Create for all loops we depend on values that contain the current loop
608 // iteration. These values are necessary to generate code for SCEVs that
609 // depend on such loops. As a result we need to pass them to the subfunction.
610 // See [Code generation of induction variables of loops outside Scops]
611 for (const Loop *L : Loops) {
612 Value *LoopInductionVar = materializeNonScopLoopInductionVariable(L);
613 SubtreeValues.insert(X: LoopInductionVar);
614 }
615
616 ValueMapT NewValues;
617
618 std::unique_ptr<ParallelLoopGenerator> ParallelLoopGenPtr;
619
620 switch (PollyOmpBackend) {
621 case OpenMPBackend::GNU:
622 ParallelLoopGenPtr.reset(
623 p: new ParallelLoopGeneratorGOMP(Builder, LI, DT, DL));
624 break;
625 case OpenMPBackend::LLVM:
626 ParallelLoopGenPtr.reset(p: new ParallelLoopGeneratorKMP(Builder, LI, DT, DL));
627 break;
628 }
629
630 IV = ParallelLoopGenPtr->createParallelLoop(
631 LB: ValueLB, UB: ValueUB, Stride: ValueInc, Values&: SubtreeValues, VMap&: NewValues, LoopBody: &LoopBody);
632 BasicBlock::iterator AfterLoop = Builder.GetInsertPoint();
633 Builder.SetInsertPoint(&*LoopBody);
634
635 // Remember the parallel subfunction
636 ParallelSubfunctions.push_back(Elt: LoopBody->getFunction());
637
638 // Save the current values.
639 auto ValueMapCopy = ValueMap;
640 IslExprBuilder::IDToValueTy IDToValueCopy = IDToValue;
641
642 updateValues(NewValues);
643 IDToValue[IteratorID] = IV;
644
645 ValueMapT NewValuesReverse;
646
647 for (auto P : NewValues)
648 NewValuesReverse[P.second] = P.first;
649
650 Annotator.addAlternativeAliasBases(NewMap&: NewValuesReverse);
651
652 create(Node: Body);
653
654 Annotator.resetAlternativeAliasBases();
655 // Restore the original values.
656 ValueMap = ValueMapCopy;
657 IDToValue = IDToValueCopy;
658
659 Builder.SetInsertPoint(&*AfterLoop);
660 removeSubFuncFromDomTree(F: (*LoopBody).getParent()->getParent(), DT);
661
662 for (const Loop *L : Loops)
663 OutsideLoopIterations.erase(Key: L);
664
665 isl_ast_node_free(node: For);
666 isl_ast_expr_free(expr: Iterator);
667 isl_id_free(id: IteratorID);
668
669 ParallelLoops++;
670}
671
672void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) {
673 if (IslAstInfo::isExecutedInParallel(Node: isl::manage_copy(ptr: For))) {
674 createForParallel(For);
675 return;
676 }
677 bool Parallel = (IslAstInfo::isParallel(Node: isl::manage_copy(ptr: For)) &&
678 !IslAstInfo::isReductionParallel(Node: isl::manage_copy(ptr: For)));
679 createForSequential(For: isl::manage(ptr: For).as<isl::ast_node_for>(), MarkParallel: Parallel);
680}
681
682void IslNodeBuilder::createIf(__isl_take isl_ast_node *If) {
683 isl_ast_expr *Cond = isl_ast_node_if_get_cond(node: If);
684
685 Function *F = Builder.GetInsertBlock()->getParent();
686 LLVMContext &Context = F->getContext();
687
688 BasicBlock *CondBB = SplitBlock(Old: Builder.GetInsertBlock(),
689 SplitPt: &*Builder.GetInsertPoint(), DT: &DT, LI: &LI);
690 CondBB->setName("polly.cond");
691 BasicBlock *MergeBB = SplitBlock(Old: CondBB, SplitPt: &CondBB->front(), DT: &DT, LI: &LI);
692 MergeBB->setName("polly.merge");
693 BasicBlock *ThenBB = BasicBlock::Create(Context, Name: "polly.then", Parent: F);
694 BasicBlock *ElseBB = BasicBlock::Create(Context, Name: "polly.else", Parent: F);
695
696 DT.addNewBlock(BB: ThenBB, DomBB: CondBB);
697 DT.addNewBlock(BB: ElseBB, DomBB: CondBB);
698 DT.changeImmediateDominator(BB: MergeBB, NewBB: CondBB);
699
700 Loop *L = LI.getLoopFor(BB: CondBB);
701 if (L) {
702 L->addBasicBlockToLoop(NewBB: ThenBB, LI);
703 L->addBasicBlockToLoop(NewBB: ElseBB, LI);
704 }
705
706 CondBB->getTerminator()->eraseFromParent();
707
708 Builder.SetInsertPoint(CondBB);
709 Value *Predicate = ExprBuilder.create(Expr: Cond);
710 Builder.CreateCondBr(Cond: Predicate, True: ThenBB, False: ElseBB);
711 Builder.SetInsertPoint(ThenBB);
712 Builder.CreateBr(Dest: MergeBB);
713 Builder.SetInsertPoint(ElseBB);
714 Builder.CreateBr(Dest: MergeBB);
715 Builder.SetInsertPoint(&ThenBB->front());
716
717 create(Node: isl_ast_node_if_get_then(node: If));
718
719 Builder.SetInsertPoint(&ElseBB->front());
720
721 if (isl_ast_node_if_has_else(node: If))
722 create(Node: isl_ast_node_if_get_else(node: If));
723
724 Builder.SetInsertPoint(&MergeBB->front());
725
726 isl_ast_node_free(node: If);
727
728 IfConditions++;
729}
730
731__isl_give isl_id_to_ast_expr *
732IslNodeBuilder::createNewAccesses(ScopStmt *Stmt,
733 __isl_keep isl_ast_node *Node) {
734 isl::id_to_ast_expr NewAccesses =
735 isl::id_to_ast_expr::alloc(ctx: Stmt->getParent()->getIslCtx(), min_size: 0);
736
737 isl::ast_build Build = IslAstInfo::getBuild(Node: isl::manage_copy(ptr: Node));
738 assert(!Build.is_null() && "Could not obtain isl_ast_build from user node");
739 Stmt->setAstBuild(Build);
740
741 for (auto *MA : *Stmt) {
742 if (!MA->hasNewAccessRelation()) {
743 if (PollyGenerateExpressions) {
744 if (!MA->isAffine())
745 continue;
746 if (MA->getLatestScopArrayInfo()->getBasePtrOriginSAI())
747 continue;
748
749 auto *BasePtr =
750 dyn_cast<Instruction>(Val: MA->getLatestScopArrayInfo()->getBasePtr());
751 if (BasePtr && Stmt->getParent()->getRegion().contains(Inst: BasePtr))
752 continue;
753 } else {
754 continue;
755 }
756 }
757 assert(MA->isAffine() &&
758 "Only affine memory accesses can be code generated");
759
760 isl::union_map Schedule = Build.get_schedule();
761
762#ifndef NDEBUG
763 if (MA->isRead()) {
764 auto Dom = Stmt->getDomain().release();
765 auto SchedDom = isl_set_from_union_set(uset: Schedule.domain().release());
766 auto AccDom = isl_map_domain(bmap: MA->getAccessRelation().release());
767 Dom = isl_set_intersect_params(set: Dom,
768 params: Stmt->getParent()->getContext().release());
769 SchedDom = isl_set_intersect_params(
770 set: SchedDom, params: Stmt->getParent()->getContext().release());
771 assert(isl_set_is_subset(SchedDom, AccDom) &&
772 "Access relation not defined on full schedule domain");
773 assert(isl_set_is_subset(Dom, AccDom) &&
774 "Access relation not defined on full domain");
775 isl_set_free(set: AccDom);
776 isl_set_free(set: SchedDom);
777 isl_set_free(set: Dom);
778 }
779#endif
780
781 isl::pw_multi_aff PWAccRel = MA->applyScheduleToAccessRelation(Schedule);
782
783 // isl cannot generate an index expression for access-nothing accesses.
784 isl::set AccDomain = PWAccRel.domain();
785 isl::set Context = S.getContext();
786 AccDomain = AccDomain.intersect_params(params: Context);
787 if (AccDomain.is_empty())
788 continue;
789
790 isl::ast_expr AccessExpr = Build.access_from(pma: PWAccRel);
791 NewAccesses = NewAccesses.set(key: MA->getId(), val: AccessExpr);
792 }
793
794 return NewAccesses.release();
795}
796
797void IslNodeBuilder::createSubstitutions(__isl_take isl_ast_expr *Expr,
798 ScopStmt *Stmt, LoopToScevMapT &LTS) {
799 assert(isl_ast_expr_get_type(Expr) == isl_ast_expr_op &&
800 "Expression of type 'op' expected");
801 assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_call &&
802 "Operation of type 'call' expected");
803 for (int i = 0; i < isl_ast_expr_get_op_n_arg(expr: Expr) - 1; ++i) {
804 isl_ast_expr *SubExpr;
805 Value *V;
806
807 SubExpr = isl_ast_expr_get_op_arg(expr: Expr, pos: i + 1);
808 V = ExprBuilder.create(Expr: SubExpr);
809 ScalarEvolution *SE = Stmt->getParent()->getSE();
810 LTS[Stmt->getLoopForDimension(Dimension: i)] = SE->getUnknown(V);
811 }
812
813 isl_ast_expr_free(expr: Expr);
814}
815
816void IslNodeBuilder::createSubstitutionsVector(
817 __isl_take isl_ast_expr *Expr, ScopStmt *Stmt,
818 std::vector<LoopToScevMapT> &VLTS, std::vector<Value *> &IVS,
819 __isl_take isl_id *IteratorID) {
820 int i = 0;
821
822 Value *OldValue = IDToValue[IteratorID];
823 for (Value *IV : IVS) {
824 IDToValue[IteratorID] = IV;
825 createSubstitutions(Expr: isl_ast_expr_copy(expr: Expr), Stmt, LTS&: VLTS[i]);
826 i++;
827 }
828
829 IDToValue[IteratorID] = OldValue;
830 isl_id_free(id: IteratorID);
831 isl_ast_expr_free(expr: Expr);
832}
833
834void IslNodeBuilder::generateCopyStmt(
835 ScopStmt *Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
836 assert(Stmt->size() == 2);
837 auto ReadAccess = Stmt->begin();
838 auto WriteAccess = ReadAccess++;
839 assert((*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite());
840 assert((*ReadAccess)->getElementType() == (*WriteAccess)->getElementType() &&
841 "Accesses use the same data type");
842 assert((*ReadAccess)->isArrayKind() && (*WriteAccess)->isArrayKind());
843 auto *AccessExpr =
844 isl_id_to_ast_expr_get(hmap: NewAccesses, key: (*ReadAccess)->getId().release());
845 auto *LoadValue = ExprBuilder.create(Expr: AccessExpr);
846 AccessExpr =
847 isl_id_to_ast_expr_get(hmap: NewAccesses, key: (*WriteAccess)->getId().release());
848 auto *StoreAddr = ExprBuilder.createAccessAddress(Expr: AccessExpr).first;
849 Builder.CreateStore(Val: LoadValue, Ptr: StoreAddr);
850}
851
852Value *IslNodeBuilder::materializeNonScopLoopInductionVariable(const Loop *L) {
853 assert(!OutsideLoopIterations.contains(L) &&
854 "trying to materialize loop induction variable twice");
855 const SCEV *OuterLIV = SE.getAddRecExpr(Start: SE.getUnknown(V: Builder.getInt64(C: 0)),
856 Step: SE.getUnknown(V: Builder.getInt64(C: 1)), L,
857 Flags: SCEV::FlagAnyWrap);
858 Value *V = generateSCEV(Expr: OuterLIV);
859 OutsideLoopIterations[L] = SE.getUnknown(V);
860 return V;
861}
862
863void IslNodeBuilder::createUser(__isl_take isl_ast_node *User) {
864 LoopToScevMapT LTS;
865 isl_id *Id;
866 ScopStmt *Stmt;
867
868 isl_ast_expr *Expr = isl_ast_node_user_get_expr(node: User);
869 isl_ast_expr *StmtExpr = isl_ast_expr_get_op_arg(expr: Expr, pos: 0);
870 Id = isl_ast_expr_get_id(expr: StmtExpr);
871 isl_ast_expr_free(expr: StmtExpr);
872
873 LTS.insert(I: OutsideLoopIterations.begin(), E: OutsideLoopIterations.end());
874
875 Stmt = (ScopStmt *)isl_id_get_user(id: Id);
876 auto *NewAccesses = createNewAccesses(Stmt, Node: User);
877 if (Stmt->isCopyStmt()) {
878 generateCopyStmt(Stmt, NewAccesses);
879 isl_ast_expr_free(expr: Expr);
880 } else {
881 createSubstitutions(Expr, Stmt, LTS);
882
883 if (Stmt->isBlockStmt())
884 BlockGen.copyStmt(Stmt&: *Stmt, LTS, NewAccesses);
885 else
886 RegionGen.copyStmt(Stmt&: *Stmt, LTS, IdToAstExp: NewAccesses);
887 }
888
889 isl_id_to_ast_expr_free(hmap: NewAccesses);
890 isl_ast_node_free(node: User);
891 isl_id_free(id: Id);
892}
893
894void IslNodeBuilder::createBlock(__isl_take isl_ast_node *Block) {
895 isl_ast_node_list *List = isl_ast_node_block_get_children(node: Block);
896
897 for (int i = 0; i < isl_ast_node_list_n_ast_node(list: List); ++i)
898 create(Node: isl_ast_node_list_get_ast_node(list: List, index: i));
899
900 isl_ast_node_free(node: Block);
901 isl_ast_node_list_free(list: List);
902}
903
904void IslNodeBuilder::create(__isl_take isl_ast_node *Node) {
905 switch (isl_ast_node_get_type(node: Node)) {
906 case isl_ast_node_error:
907 llvm_unreachable("code generation error");
908 case isl_ast_node_mark:
909 createMark(Node);
910 return;
911 case isl_ast_node_for:
912 createFor(For: Node);
913 return;
914 case isl_ast_node_if:
915 createIf(If: Node);
916 return;
917 case isl_ast_node_user:
918 createUser(User: Node);
919 return;
920 case isl_ast_node_block:
921 createBlock(Block: Node);
922 return;
923 }
924
925 llvm_unreachable("Unknown isl_ast_node type");
926}
927
928bool IslNodeBuilder::materializeValue(__isl_take isl_id *Id) {
929 // If the Id is already mapped, skip it.
930 if (!IDToValue.count(Key: Id)) {
931 auto *ParamSCEV = (const SCEV *)isl_id_get_user(id: Id);
932 Value *V = nullptr;
933
934 // Parameters could refer to invariant loads that need to be
935 // preloaded before we can generate code for the parameter. Thus,
936 // check if any value referred to in ParamSCEV is an invariant load
937 // and if so make sure its equivalence class is preloaded.
938 SetVector<Value *> Values;
939 findValues(Expr: ParamSCEV, SE, Values);
940 for (auto *Val : Values) {
941 // Check if the value is an instruction in a dead block within the SCoP
942 // and if so do not code generate it.
943 if (auto *Inst = dyn_cast<Instruction>(Val)) {
944 if (S.contains(I: Inst)) {
945 bool IsDead = true;
946
947 // Check for "undef" loads first, then if there is a statement for
948 // the parent of Inst and lastly if the parent of Inst has an empty
949 // domain. In the first and last case the instruction is dead but if
950 // there is a statement or the domain is not empty Inst is not dead.
951 auto MemInst = MemAccInst::dyn_cast(V: Inst);
952 auto Address = MemInst ? MemInst.getPointerOperand() : nullptr;
953 if (Address && SE.getUnknown(V: UndefValue::get(T: Address->getType())) ==
954 SE.getPointerBase(V: SE.getSCEV(V: Address))) {
955 } else if (S.getStmtFor(Inst)) {
956 IsDead = false;
957 } else {
958 auto *Domain = S.getDomainConditions(BB: Inst->getParent()).release();
959 IsDead = isl_set_is_empty(set: Domain);
960 isl_set_free(set: Domain);
961 }
962
963 if (IsDead) {
964 V = UndefValue::get(T: ParamSCEV->getType());
965 break;
966 }
967 }
968 }
969
970 if (auto *IAClass = S.lookupInvariantEquivClass(Val)) {
971 // Check if this invariant access class is empty, hence if we never
972 // actually added a loads instruction to it. In that case it has no
973 // (meaningful) users and we should not try to code generate it.
974 if (IAClass->InvariantAccesses.empty())
975 V = UndefValue::get(T: ParamSCEV->getType());
976
977 if (!preloadInvariantEquivClass(IAClass&: *IAClass)) {
978 isl_id_free(id: Id);
979 return false;
980 }
981 }
982 }
983
984 V = V ? V : generateSCEV(Expr: ParamSCEV);
985 IDToValue[Id] = V;
986 }
987
988 isl_id_free(id: Id);
989 return true;
990}
991
992bool IslNodeBuilder::materializeParameters(__isl_take isl_set *Set) {
993 for (unsigned i = 0, e = isl_set_dim(set: Set, type: isl_dim_param); i < e; ++i) {
994 if (!isl_set_involves_dims(set: Set, type: isl_dim_param, first: i, n: 1))
995 continue;
996 isl_id *Id = isl_set_get_dim_id(set: Set, type: isl_dim_param, pos: i);
997 if (!materializeValue(Id))
998 return false;
999 }
1000 return true;
1001}
1002
1003bool IslNodeBuilder::materializeParameters() {
1004 for (const SCEV *Param : S.parameters()) {
1005 isl_id *Id = S.getIdForParam(Parameter: Param).release();
1006 if (!materializeValue(Id))
1007 return false;
1008 }
1009 return true;
1010}
1011
1012Value *IslNodeBuilder::preloadUnconditionally(__isl_take isl_set *AccessRange,
1013 isl_ast_build *Build,
1014 Instruction *AccInst) {
1015 isl_pw_multi_aff *PWAccRel = isl_pw_multi_aff_from_set(set: AccessRange);
1016 isl_ast_expr *Access =
1017 isl_ast_build_access_from_pw_multi_aff(build: Build, pma: PWAccRel);
1018 auto *Address = isl_ast_expr_address_of(expr: Access);
1019 auto *AddressValue = ExprBuilder.create(Expr: Address);
1020 Value *PreloadVal;
1021
1022 // Correct the type as the SAI might have a different type than the user
1023 // expects, especially if the base pointer is a struct.
1024 Type *Ty = AccInst->getType();
1025
1026 auto *Ptr = AddressValue;
1027 auto Name = Ptr->getName();
1028 auto AS = Ptr->getType()->getPointerAddressSpace();
1029 Ptr = Builder.CreatePointerCast(V: Ptr, DestTy: Ty->getPointerTo(AddrSpace: AS), Name: Name + ".cast");
1030 PreloadVal = Builder.CreateLoad(Ty, Ptr, Name: Name + ".load");
1031 if (LoadInst *PreloadInst = dyn_cast<LoadInst>(Val: PreloadVal))
1032 PreloadInst->setAlignment(cast<LoadInst>(Val: AccInst)->getAlign());
1033
1034 // TODO: This is only a hot fix for SCoP sequences that use the same load
1035 // instruction contained and hoisted by one of the SCoPs.
1036 if (SE.isSCEVable(Ty))
1037 SE.forgetValue(V: AccInst);
1038
1039 return PreloadVal;
1040}
1041
1042Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA,
1043 __isl_take isl_set *Domain) {
1044 isl_set *AccessRange = isl_map_range(map: MA.getAddressFunction().release());
1045 AccessRange = isl_set_gist_params(set: AccessRange, context: S.getContext().release());
1046
1047 if (!materializeParameters(Set: AccessRange)) {
1048 isl_set_free(set: AccessRange);
1049 isl_set_free(set: Domain);
1050 return nullptr;
1051 }
1052
1053 auto *Build =
1054 isl_ast_build_from_context(set: isl_set_universe(space: S.getParamSpace().release()));
1055 isl_set *Universe = isl_set_universe(space: isl_set_get_space(set: Domain));
1056 bool AlwaysExecuted = isl_set_is_equal(set1: Domain, set2: Universe);
1057 isl_set_free(set: Universe);
1058
1059 Instruction *AccInst = MA.getAccessInstruction();
1060 Type *AccInstTy = AccInst->getType();
1061
1062 Value *PreloadVal = nullptr;
1063 if (AlwaysExecuted) {
1064 PreloadVal = preloadUnconditionally(AccessRange, Build, AccInst);
1065 isl_ast_build_free(build: Build);
1066 isl_set_free(set: Domain);
1067 return PreloadVal;
1068 }
1069
1070 if (!materializeParameters(Set: Domain)) {
1071 isl_ast_build_free(build: Build);
1072 isl_set_free(set: AccessRange);
1073 isl_set_free(set: Domain);
1074 return nullptr;
1075 }
1076
1077 isl_ast_expr *DomainCond = isl_ast_build_expr_from_set(build: Build, set: Domain);
1078 Domain = nullptr;
1079
1080 ExprBuilder.setTrackOverflow(true);
1081 Value *Cond = ExprBuilder.create(Expr: DomainCond);
1082 Value *OverflowHappened = Builder.CreateNot(V: ExprBuilder.getOverflowState(),
1083 Name: "polly.preload.cond.overflown");
1084 Cond = Builder.CreateAnd(LHS: Cond, RHS: OverflowHappened, Name: "polly.preload.cond.result");
1085 ExprBuilder.setTrackOverflow(false);
1086
1087 if (!Cond->getType()->isIntegerTy(Bitwidth: 1))
1088 Cond = Builder.CreateIsNotNull(Arg: Cond);
1089
1090 BasicBlock *CondBB = SplitBlock(Old: Builder.GetInsertBlock(),
1091 SplitPt: &*Builder.GetInsertPoint(), DT: &DT, LI: &LI);
1092 CondBB->setName("polly.preload.cond");
1093
1094 BasicBlock *MergeBB = SplitBlock(Old: CondBB, SplitPt: &CondBB->front(), DT: &DT, LI: &LI);
1095 MergeBB->setName("polly.preload.merge");
1096
1097 Function *F = Builder.GetInsertBlock()->getParent();
1098 LLVMContext &Context = F->getContext();
1099 BasicBlock *ExecBB = BasicBlock::Create(Context, Name: "polly.preload.exec", Parent: F);
1100
1101 DT.addNewBlock(BB: ExecBB, DomBB: CondBB);
1102 if (Loop *L = LI.getLoopFor(BB: CondBB))
1103 L->addBasicBlockToLoop(NewBB: ExecBB, LI);
1104
1105 auto *CondBBTerminator = CondBB->getTerminator();
1106 Builder.SetInsertPoint(CondBBTerminator);
1107 Builder.CreateCondBr(Cond, True: ExecBB, False: MergeBB);
1108 CondBBTerminator->eraseFromParent();
1109
1110 Builder.SetInsertPoint(ExecBB);
1111 Builder.CreateBr(Dest: MergeBB);
1112
1113 Builder.SetInsertPoint(ExecBB->getTerminator());
1114 Value *PreAccInst = preloadUnconditionally(AccessRange, Build, AccInst);
1115 Builder.SetInsertPoint(MergeBB->getTerminator());
1116 auto *MergePHI = Builder.CreatePHI(
1117 Ty: AccInstTy, NumReservedValues: 2, Name: "polly.preload." + AccInst->getName() + ".merge");
1118 PreloadVal = MergePHI;
1119
1120 if (!PreAccInst) {
1121 PreloadVal = nullptr;
1122 PreAccInst = UndefValue::get(T: AccInstTy);
1123 }
1124
1125 MergePHI->addIncoming(V: PreAccInst, BB: ExecBB);
1126 MergePHI->addIncoming(V: Constant::getNullValue(Ty: AccInstTy), BB: CondBB);
1127
1128 isl_ast_build_free(build: Build);
1129 return PreloadVal;
1130}
1131
1132bool IslNodeBuilder::preloadInvariantEquivClass(
1133 InvariantEquivClassTy &IAClass) {
1134 // For an equivalence class of invariant loads we pre-load the representing
1135 // element with the unified execution context. However, we have to map all
1136 // elements of the class to the one preloaded load as they are referenced
1137 // during the code generation and therefor need to be mapped.
1138 const MemoryAccessList &MAs = IAClass.InvariantAccesses;
1139 if (MAs.empty())
1140 return true;
1141
1142 MemoryAccess *MA = MAs.front();
1143 assert(MA->isArrayKind() && MA->isRead());
1144
1145 // If the access function was already mapped, the preload of this equivalence
1146 // class was triggered earlier already and doesn't need to be done again.
1147 if (ValueMap.count(Val: MA->getAccessInstruction()))
1148 return true;
1149
1150 // Check for recursion which can be caused by additional constraints, e.g.,
1151 // non-finite loop constraints. In such a case we have to bail out and insert
1152 // a "false" runtime check that will cause the original code to be executed.
1153 auto PtrId = std::make_pair(x&: IAClass.IdentifyingPointer, y&: IAClass.AccessType);
1154 if (!PreloadedPtrs.insert(V: PtrId).second)
1155 return false;
1156
1157 // The execution context of the IAClass.
1158 isl::set &ExecutionCtx = IAClass.ExecutionContext;
1159
1160 // If the base pointer of this class is dependent on another one we have to
1161 // make sure it was preloaded already.
1162 auto *SAI = MA->getScopArrayInfo();
1163 if (auto *BaseIAClass = S.lookupInvariantEquivClass(Val: SAI->getBasePtr())) {
1164 if (!preloadInvariantEquivClass(IAClass&: *BaseIAClass))
1165 return false;
1166
1167 // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx and
1168 // we need to refine the ExecutionCtx.
1169 isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext;
1170 ExecutionCtx = ExecutionCtx.intersect(set2: BaseExecutionCtx);
1171 }
1172
1173 // If the size of a dimension is dependent on another class, make sure it is
1174 // preloaded.
1175 for (unsigned i = 1, e = SAI->getNumberOfDimensions(); i < e; ++i) {
1176 const SCEV *Dim = SAI->getDimensionSize(Dim: i);
1177 SetVector<Value *> Values;
1178 findValues(Expr: Dim, SE, Values);
1179 for (auto *Val : Values) {
1180 if (auto *BaseIAClass = S.lookupInvariantEquivClass(Val)) {
1181 if (!preloadInvariantEquivClass(IAClass&: *BaseIAClass))
1182 return false;
1183
1184 // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx
1185 // and we need to refine the ExecutionCtx.
1186 isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext;
1187 ExecutionCtx = ExecutionCtx.intersect(set2: BaseExecutionCtx);
1188 }
1189 }
1190 }
1191
1192 Instruction *AccInst = MA->getAccessInstruction();
1193 Type *AccInstTy = AccInst->getType();
1194
1195 Value *PreloadVal = preloadInvariantLoad(MA: *MA, Domain: ExecutionCtx.copy());
1196 if (!PreloadVal)
1197 return false;
1198
1199 for (const MemoryAccess *MA : MAs) {
1200 Instruction *MAAccInst = MA->getAccessInstruction();
1201 assert(PreloadVal->getType() == MAAccInst->getType());
1202 ValueMap[MAAccInst] = PreloadVal;
1203 }
1204
1205 if (SE.isSCEVable(Ty: AccInstTy)) {
1206 isl_id *ParamId = S.getIdForParam(Parameter: SE.getSCEV(V: AccInst)).release();
1207 if (ParamId)
1208 IDToValue[ParamId] = PreloadVal;
1209 isl_id_free(id: ParamId);
1210 }
1211
1212 BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
1213 auto *Alloca = new AllocaInst(AccInstTy, DL.getAllocaAddrSpace(),
1214 AccInst->getName() + ".preload.s2a",
1215 EntryBB->getFirstInsertionPt());
1216 Builder.CreateStore(Val: PreloadVal, Ptr: Alloca);
1217 ValueMapT PreloadedPointer;
1218 PreloadedPointer[PreloadVal] = AccInst;
1219 Annotator.addAlternativeAliasBases(NewMap&: PreloadedPointer);
1220
1221 for (auto *DerivedSAI : SAI->getDerivedSAIs()) {
1222 Value *BasePtr = DerivedSAI->getBasePtr();
1223
1224 for (const MemoryAccess *MA : MAs) {
1225 // As the derived SAI information is quite coarse, any load from the
1226 // current SAI could be the base pointer of the derived SAI, however we
1227 // should only change the base pointer of the derived SAI if we actually
1228 // preloaded it.
1229 if (BasePtr == MA->getOriginalBaseAddr()) {
1230 assert(BasePtr->getType() == PreloadVal->getType());
1231 DerivedSAI->setBasePtr(PreloadVal);
1232 }
1233
1234 // For scalar derived SAIs we remap the alloca used for the derived value.
1235 if (BasePtr == MA->getAccessInstruction())
1236 ScalarMap[DerivedSAI] = Alloca;
1237 }
1238 }
1239
1240 for (const MemoryAccess *MA : MAs) {
1241 Instruction *MAAccInst = MA->getAccessInstruction();
1242 // Use the escape system to get the correct value to users outside the SCoP.
1243 BlockGenerator::EscapeUserVectorTy EscapeUsers;
1244 for (auto *U : MAAccInst->users())
1245 if (Instruction *UI = dyn_cast<Instruction>(Val: U))
1246 if (!S.contains(I: UI))
1247 EscapeUsers.push_back(Elt: UI);
1248
1249 if (EscapeUsers.empty())
1250 continue;
1251
1252 EscapeMap[MA->getAccessInstruction()] =
1253 std::make_pair(x&: Alloca, y: std::move(EscapeUsers));
1254 }
1255
1256 return true;
1257}
1258
1259void IslNodeBuilder::allocateNewArrays(BBPair StartExitBlocks) {
1260 for (auto &SAI : S.arrays()) {
1261 if (SAI->getBasePtr())
1262 continue;
1263
1264 assert(SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize(0) &&
1265 "The size of the outermost dimension is used to declare newly "
1266 "created arrays that require memory allocation.");
1267
1268 Type *NewArrayType = nullptr;
1269
1270 // Get the size of the array = size(dim_1)*...*size(dim_n)
1271 uint64_t ArraySizeInt = 1;
1272 for (int i = SAI->getNumberOfDimensions() - 1; i >= 0; i--) {
1273 auto *DimSize = SAI->getDimensionSize(Dim: i);
1274 unsigned UnsignedDimSize = static_cast<const SCEVConstant *>(DimSize)
1275 ->getAPInt()
1276 .getLimitedValue();
1277
1278 if (!NewArrayType)
1279 NewArrayType = SAI->getElementType();
1280
1281 NewArrayType = ArrayType::get(ElementType: NewArrayType, NumElements: UnsignedDimSize);
1282 ArraySizeInt *= UnsignedDimSize;
1283 }
1284
1285 if (SAI->isOnHeap()) {
1286 LLVMContext &Ctx = NewArrayType->getContext();
1287
1288 // Get the IntPtrTy from the Datalayout
1289 auto IntPtrTy = DL.getIntPtrType(C&: Ctx);
1290
1291 // Get the size of the element type in bits
1292 unsigned Size = SAI->getElemSizeInBytes();
1293
1294 // Insert the malloc call at polly.start
1295 Builder.SetInsertPoint(std::get<0>(in&: StartExitBlocks)->getTerminator());
1296 auto *CreatedArray = Builder.CreateMalloc(
1297 IntPtrTy, AllocTy: SAI->getElementType(),
1298 AllocSize: ConstantInt::get(Ty: Type::getInt64Ty(C&: Ctx), V: Size),
1299 ArraySize: ConstantInt::get(Ty: Type::getInt64Ty(C&: Ctx), V: ArraySizeInt), MallocF: nullptr,
1300 Name: SAI->getName());
1301
1302 SAI->setBasePtr(CreatedArray);
1303
1304 // Insert the free call at polly.exiting
1305 Builder.SetInsertPoint(std::get<1>(in&: StartExitBlocks)->getTerminator());
1306 Builder.CreateFree(Source: CreatedArray);
1307 } else {
1308 auto InstIt = Builder.GetInsertBlock()
1309 ->getParent()
1310 ->getEntryBlock()
1311 .getTerminator()
1312 ->getIterator();
1313
1314 auto *CreatedArray = new AllocaInst(NewArrayType, DL.getAllocaAddrSpace(),
1315 SAI->getName(), InstIt);
1316 if (PollyTargetFirstLevelCacheLineSize)
1317 CreatedArray->setAlignment(Align(PollyTargetFirstLevelCacheLineSize));
1318 SAI->setBasePtr(CreatedArray);
1319 }
1320 }
1321}
1322
1323bool IslNodeBuilder::preloadInvariantLoads() {
1324 auto &InvariantEquivClasses = S.getInvariantAccesses();
1325 if (InvariantEquivClasses.empty())
1326 return true;
1327
1328 BasicBlock *PreLoadBB = SplitBlock(Old: Builder.GetInsertBlock(),
1329 SplitPt: &*Builder.GetInsertPoint(), DT: &DT, LI: &LI);
1330 PreLoadBB->setName("polly.preload.begin");
1331 Builder.SetInsertPoint(&PreLoadBB->front());
1332
1333 for (auto &IAClass : InvariantEquivClasses)
1334 if (!preloadInvariantEquivClass(IAClass))
1335 return false;
1336
1337 return true;
1338}
1339
1340void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
1341 // Materialize values for the parameters of the SCoP.
1342 materializeParameters();
1343
1344 // Generate values for the current loop iteration for all surrounding loops.
1345 //
1346 // We may also reference loops outside of the scop which do not contain the
1347 // scop itself, but as the number of such scops may be arbitrarily large we do
1348 // not generate code for them here, but only at the point of code generation
1349 // where these values are needed.
1350 Loop *L = LI.getLoopFor(BB: S.getEntry());
1351
1352 while (L != nullptr && S.contains(L))
1353 L = L->getParentLoop();
1354
1355 while (L != nullptr) {
1356 materializeNonScopLoopInductionVariable(L);
1357 L = L->getParentLoop();
1358 }
1359
1360 isl_set_free(set: Context);
1361}
1362
1363Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) {
1364 /// We pass the insert location of our Builder, as Polly ensures during IR
1365 /// generation that there is always a valid CFG into which instructions are
1366 /// inserted. As a result, the insertpoint is known to be always followed by a
1367 /// terminator instruction. This means the insert point may be specified by a
1368 /// terminator instruction, but it can never point to an ->end() iterator
1369 /// which does not have a corresponding instruction. Hence, dereferencing
1370 /// the insertpoint to obtain an instruction is known to be save.
1371 ///
1372 /// We also do not need to update the Builder here, as new instructions are
1373 /// always inserted _before_ the given InsertLocation. As a result, the
1374 /// insert location remains valid.
1375 assert(Builder.GetInsertBlock()->end() != Builder.GetInsertPoint() &&
1376 "Insert location points after last valid instruction");
1377 Instruction *InsertLocation = &*Builder.GetInsertPoint();
1378 return expandCodeFor(S, SE, DL, Name: "polly", E: Expr, Ty: Expr->getType(),
1379 IP: InsertLocation, VMap: &ValueMap,
1380 RTCBB: StartBlock->getSinglePredecessor());
1381}
1382
1383/// The AST expression we generate to perform the run-time check assumes
1384/// computations on integer types of infinite size. As we only use 64-bit
1385/// arithmetic we check for overflows, in case of which we set the result
1386/// of this run-time check to false to be conservatively correct,
1387Value *IslNodeBuilder::createRTC(isl_ast_expr *Condition) {
1388 auto ExprBuilder = getExprBuilder();
1389
1390 // In case the AST expression has integers larger than 64 bit, bail out. The
1391 // resulting LLVM-IR will contain operations on types that use more than 64
1392 // bits. These are -- in case wrapping intrinsics are used -- translated to
1393 // runtime library calls that are not available on all systems (e.g., Android)
1394 // and consequently will result in linker errors.
1395 if (ExprBuilder.hasLargeInts(Expr: isl::manage_copy(ptr: Condition))) {
1396 isl_ast_expr_free(expr: Condition);
1397 return Builder.getFalse();
1398 }
1399
1400 ExprBuilder.setTrackOverflow(true);
1401 Value *RTC = ExprBuilder.create(Expr: Condition);
1402 if (!RTC->getType()->isIntegerTy(Bitwidth: 1))
1403 RTC = Builder.CreateIsNotNull(Arg: RTC);
1404 Value *OverflowHappened =
1405 Builder.CreateNot(V: ExprBuilder.getOverflowState(), Name: "polly.rtc.overflown");
1406
1407 if (PollyGenerateRTCPrint) {
1408 auto *F = Builder.GetInsertBlock()->getParent();
1409 RuntimeDebugBuilder::createCPUPrinter(
1410 Builder,
1411 args: "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() +
1412 "RTC: ",
1413 args: RTC, args: " Overflow: ", args: OverflowHappened,
1414 args: "\n"
1415 " (0 failed, -1 succeeded)\n"
1416 " (if one or both are 0 falling back to original code, if both are -1 "
1417 "executing Polly code)\n");
1418 }
1419
1420 RTC = Builder.CreateAnd(LHS: RTC, RHS: OverflowHappened, Name: "polly.rtc.result");
1421 ExprBuilder.setTrackOverflow(false);
1422
1423 if (!isa<ConstantInt>(Val: RTC))
1424 VersionedScops++;
1425
1426 return RTC;
1427}
1428

source code of polly/lib/CodeGen/IslNodeBuilder.cpp