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

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