Polly 22.0.0git
IslNodeBuilder.cpp
Go to the documentation of this file.
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
22#include "polly/Options.h"
23#include "polly/ScopInfo.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"
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
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(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(OpenMPBackend::GNU), cl::cat(PollyCategory));
113
115 ICmpInst::Predicate &Predicate) {
116 isl::ast_expr Cond = For.cond();
117 isl::ast_expr Iterator = For.iterator();
119 "conditional expression is not an atomic upper bound");
120
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(0);
135
137 "conditional expression is not an atomic upper bound");
138
139 isl::id UBID = Arg0.get_id();
140
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(1);
150}
151
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(Body.get())) {
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.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, SrcVal, true);
199 switch (VUse.getKind()) {
201 // When accelerator-offloading, GlobalValue is a host address whose content
202 // must still be transferred to the GPU.
203 if (isa<GlobalValue>(SrcVal))
204 Values.insert(SrcVal);
205 break;
206
208 SCEVs.insert(VUse.getScevExpr());
209 return;
210
216 break;
217 }
218
219 if (Value *NewVal = GlobalMap.lookup(SrcVal))
220 Values.insert(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(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, Stmt, 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, Stmt, 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, References.Values, References.GlobalMap,
255 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(ParamSpace);
262 }
263
264 if (Access->isLatestArrayKind()) {
265 auto *BasePtr = Access->getLatestScopArrayInfo()->getBasePtr();
266 if (Instruction *OpInst = dyn_cast<Instruction>(BasePtr))
267 if (Stmt->getParent()->contains(OpInst))
268 continue;
269
270 References.Values.insert(BasePtr);
271 continue;
272 }
273
274 if (CreateScalarRefs)
275 References.Values.insert(References.BlockGen.getOrCreateAlloca(*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.
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.
310 SubtreeReferences &References) {
311
312 for (isl::set Set : USet.get_set_list())
313 addReferencesFromStmtSet(Set, &References);
314}
315
316isl::union_map
320
322 SetVector<Value *> &Values,
323 SetVector<const Loop *> &Loops) {
324 SetVector<const SCEV *> SCEVs;
325 SubtreeReferences References = {
326 LI, SE, S, ValueMap, Values, SCEVs, getBlockGenerator(), nullptr};
327
328 Values.insert_range(llvm::make_second_range(IDToValue));
329
330 // NOTE: this is populated in IslNodeBuilder::addParameters
331 for (const auto &I : OutsideLoopIterations)
332 Values.insert(cast<SCEVUnknown>(I.second)->getValue());
333
335 addReferencesFromStmtUnionSet(Schedule, References);
336
337 for (const SCEV *Expr : SCEVs) {
338 findValues(Expr, SE, Values);
339 findLoops(Expr, Loops);
340 }
341
342 Values.remove_if([](const Value *V) { return isa<GlobalValue>(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([this](const Loop *L) {
356 return S.contains(L) || L->contains(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(getLatestValue(V));
368 }
369 Values = ReplacedValues;
370}
371
373 auto It = ValueMap.find(Original);
374 if (It == ValueMap.end())
375 return Original;
376 return It->second;
377}
378
380 auto *Id = isl_ast_node_mark_get_id(Node);
381 auto Child = isl_ast_node_mark_get_node(Node);
382 isl_ast_node_free(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(isl_id_get_name(Id), "SIMD") == 0 &&
387 createForSequential(isl::manage(Child).as<isl::ast_node_for>(), true);
388 isl_id_free(Id);
389 return;
390 }
391
392 BandAttr *ChildLoopAttr = getLoopAttr(isl::manage_copy(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(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);
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.
425 isl::ast_node Body = Node.body();
427 return false;
428
429 isl::ast_node_mark BodyMark = Body.as<isl::ast_node_mark>();
430 auto Id = BodyMark.id();
431 if (strcmp(Id.get_name().c_str(), "Loop Vectorizer Disabled") == 0)
432 return true;
433 return false;
434}
435
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(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(Init.release());
461 ValueUB = ExprBuilder.create(UB.release());
462 ValueInc = ExprBuilder.create(Inc.release());
463
464 MaxType = ExprBuilder.getType(Iterator.get());
465 MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
466 MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
467 MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
468
469 if (MaxType != ValueLB->getType())
470 ValueLB = Builder.CreateSExt(ValueLB, MaxType);
471 if (MaxType != ValueUB->getType())
472 ValueUB = Builder.CreateSExt(ValueUB, MaxType);
473 if (MaxType != ValueInc->getType())
474 ValueInc = Builder.CreateSExt(ValueInc, 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(Predicate, GenSE->getSCEV(ValueLB),
479 GenSE->getSCEV(ValueUB));
480 IV = createLoop(ValueLB, ValueUB, ValueInc, Builder, *GenLI, *GenDT,
481 ExitBlock, Predicate, &Annotator, MarkParallel, UseGuardBB,
482 LoopVectorizerDisabled);
483 IDToValue[IteratorID.get()] = IV;
484
485 create(Body.release());
486
487 Annotator.popLoop(MarkParallel);
488
489 IDToValue.erase(IDToValue.find(IteratorID.get()));
490
491 Builder.SetInsertPoint(ExitBlock, ExitBlock->begin());
492
493 SequentialLoops++;
494}
495
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(Builder.GetInsertBlock(), Builder.GetInsertPoint(), &DT, &LI);
510 ParBB->setName("polly.parallel.for");
511 Builder.SetInsertPoint(ParBB, ParBB->begin());
512
513 Body = isl_ast_node_for_get_body(For);
514 Init = isl_ast_node_for_get_init(For);
515 Inc = isl_ast_node_for_get_inc(For);
516 Iterator = isl_ast_node_for_get_iterator(For);
517 IteratorID = isl_ast_expr_get_id(Iterator);
518 UB = getUpperBound(isl::manage_copy(For).as<isl::ast_node_for>(), Predicate)
519 .release();
520
521 ValueLB = ExprBuilder.create(Init);
522 ValueUB = ExprBuilder.create(UB);
523 ValueInc = ExprBuilder.create(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 ValueUB, Builder.CreateSExt(Builder.getTrue(), ValueUB->getType()));
530
531 MaxType = ExprBuilder.getType(Iterator);
532 MaxType = ExprBuilder.getWidestType(MaxType, ValueLB->getType());
533 MaxType = ExprBuilder.getWidestType(MaxType, ValueUB->getType());
534 MaxType = ExprBuilder.getWidestType(MaxType, ValueInc->getType());
535
536 if (MaxType != ValueLB->getType())
537 ValueLB = Builder.CreateSExt(ValueLB, MaxType);
538 if (MaxType != ValueUB->getType())
539 ValueUB = Builder.CreateSExt(ValueUB, MaxType);
540 if (MaxType != ValueInc->getType())
541 ValueInc = Builder.CreateSExt(ValueInc, MaxType);
542
543 BasicBlock::iterator LoopBody;
544
545 SetVector<Value *> SubtreeValues;
546 SetVector<const Loop *> Loops;
547
548 getReferencesInSubtree(isl::manage_copy(For), 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(LoopInductionVar);
557 }
558
559 ValueMapT NewValues;
560
561 std::unique_ptr<ParallelLoopGenerator> ParallelLoopGenPtr;
562
563 switch (PollyOmpBackend) {
565 ParallelLoopGenPtr.reset(new ParallelLoopGeneratorGOMP(Builder, DL));
566 break;
568 ParallelLoopGenPtr.reset(new ParallelLoopGeneratorKMP(Builder, DL));
569 break;
570 }
571
572 IV = ParallelLoopGenPtr->createParallelLoop(
573 ValueLB, ValueUB, ValueInc, SubtreeValues, NewValues, &LoopBody);
574 BasicBlock::iterator AfterLoop = Builder.GetInsertPoint();
575
576 // Remember the parallel subfunction
577 Function *SubFn = LoopBody->getFunction();
578 ParallelSubfunctions.push_back(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;
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 *SubFn, CalleeTLI, CalleeAC, *SubDT, *SubLI);
607
608 // Switch to the subfunction
609 GenDT = SubDT;
610 GenLI = SubLI;
611 GenSE = SubSE.get();
612 BlockGen.switchGeneratedFunc(SubFn, GenDT, GenLI, GenSE);
613 RegionGen.switchGeneratedFunc(SubFn, GenDT, GenLI, GenSE);
614 ExprBuilder.switchGeneratedFunc(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(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(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>((Value *)NewVal)) {
635 if (S.contains(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(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>((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>((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(NewValuesReverse);
671
672 create(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(CallerFn, CallerDT, CallerLI, CallerSE);
683 RegionGen.switchGeneratedFunc(CallerFn, CallerDT, CallerLI, CallerSE);
684 BlockGen.switchGeneratedFunc(CallerFn, CallerDT, CallerLI, CallerSE);
685 Builder.SetInsertPoint(AfterLoop);
686
687 for (const Loop *L : Loops)
688 OutsideLoopIterations.erase(L);
689
691 isl_ast_expr_free(Iterator);
692 isl_id_free(IteratorID);
693
694 ParallelLoops++;
695}
696
700 return;
701 }
702 bool Parallel = (IslAstInfo::isParallel(isl::manage_copy(For)) &&
704 createForSequential(isl::manage(For).as<isl::ast_node_for>(), Parallel);
705}
706
709
710 Function *F = Builder.GetInsertBlock()->getParent();
711 LLVMContext &Context = F->getContext();
712
713 BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
714 Builder.GetInsertPoint(), GenDT, GenLI);
715 CondBB->setName("polly.cond");
716 BasicBlock *MergeBB = SplitBlock(CondBB, CondBB->begin(), GenDT, GenLI);
717 MergeBB->setName("polly.merge");
718 BasicBlock *ThenBB = BasicBlock::Create(Context, "polly.then", F);
719 BasicBlock *ElseBB = BasicBlock::Create(Context, "polly.else", F);
720
721 GenDT->addNewBlock(ThenBB, CondBB);
722 GenDT->addNewBlock(ElseBB, CondBB);
723 GenDT->changeImmediateDominator(MergeBB, CondBB);
724
725 Loop *L = GenLI->getLoopFor(CondBB);
726 if (L) {
727 L->addBasicBlockToLoop(ThenBB, *GenLI);
728 L->addBasicBlockToLoop(ElseBB, *GenLI);
729 }
730
731 CondBB->getTerminator()->eraseFromParent();
732
733 Builder.SetInsertPoint(CondBB);
734 Value *Predicate = ExprBuilder.create(Cond);
735 Builder.CreateCondBr(Predicate, ThenBB, ElseBB);
736 Builder.SetInsertPoint(ThenBB);
737 Builder.CreateBr(MergeBB);
738 Builder.SetInsertPoint(ElseBB);
739 Builder.CreateBr(MergeBB);
740 Builder.SetInsertPoint(ThenBB, ThenBB->begin());
741
743
744 Builder.SetInsertPoint(ElseBB, ElseBB->begin());
745
748
749 Builder.SetInsertPoint(MergeBB, MergeBB->begin());
750
752
753 IfConditions++;
754}
755
756__isl_give isl_id_to_ast_expr *
758 __isl_keep isl_ast_node *Node) {
759 isl::id_to_ast_expr NewAccesses =
761
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()) {
769 if (!MA->isAffine())
770 continue;
771 if (MA->getLatestScopArrayInfo()->getBasePtrOriginSAI())
772 continue;
773
774 auto *BasePtr =
775 dyn_cast<Instruction>(MA->getLatestScopArrayInfo()->getBasePtr());
776 if (BasePtr && Stmt->getParent()->getRegion().contains(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(Schedule.domain().release());
791 auto AccDom = isl_map_domain(MA->getAccessRelation().release());
792 Dom = isl_set_intersect_params(Dom,
793 Stmt->getParent()->getContext().release());
794 SchedDom = isl_set_intersect_params(
795 SchedDom, 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(AccDom);
801 isl_set_free(SchedDom);
802 isl_set_free(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(Context);
812 if (AccDomain.is_empty())
813 continue;
814
815 isl::ast_expr AccessExpr = Build.access_from(PWAccRel);
816 NewAccesses = NewAccesses.set(MA->getId(), AccessExpr);
817 }
818
819 return NewAccesses.release();
820}
821
823 ScopStmt *Stmt, LoopToScevMapT &LTS) {
825 "Expression of type 'op' expected");
827 "Operation of type 'call' expected");
828 for (int i = 0; i < isl_ast_expr_get_op_n_arg(Expr) - 1; ++i) {
829 isl_ast_expr *SubExpr;
830 Value *V;
831
832 SubExpr = isl_ast_expr_get_op_arg(Expr, i + 1);
833 V = ExprBuilder.create(SubExpr);
834 ScalarEvolution *SE = Stmt->getParent()->getSE();
835 LTS[Stmt->getLoopForDimension(i)] = SE->getUnknown(V);
836 }
837
838 isl_ast_expr_free(Expr);
839}
840
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(isl_ast_expr_copy(Expr), Stmt, VLTS[i]);
851 i++;
852 }
853
854 IDToValue[IteratorID] = OldValue;
855 isl_id_free(IteratorID);
856 isl_ast_expr_free(Expr);
857}
858
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(NewAccesses, (*ReadAccess)->getId().release());
870 auto *LoadValue = ExprBuilder.create(AccessExpr);
871 AccessExpr =
872 isl_id_to_ast_expr_get(NewAccesses, (*WriteAccess)->getId().release());
873 auto *StoreAddr = ExprBuilder.createAccessAddress(AccessExpr).first;
874 Builder.CreateStore(LoadValue, StoreAddr);
875}
876
878 assert(!OutsideLoopIterations.contains(L) &&
879 "trying to materialize loop induction variable twice");
880 const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
881 SE.getUnknown(Builder.getInt64(1)), L,
882 SCEV::FlagAnyWrap);
883 Value *V = generateSCEV(OuterLIV);
884 OutsideLoopIterations[L] = SE.getUnknown(V);
885 return V;
886}
887
889 LoopToScevMapT LTS;
890 isl_id *Id;
891 ScopStmt *Stmt;
892
894 isl_ast_expr *StmtExpr = isl_ast_expr_get_op_arg(Expr, 0);
895 Id = isl_ast_expr_get_id(StmtExpr);
896 isl_ast_expr_free(StmtExpr);
897
898 LTS.insert_range(OutsideLoopIterations);
899
900 Stmt = (ScopStmt *)isl_id_get_user(Id);
901 auto *NewAccesses = createNewAccesses(Stmt, User);
902 if (Stmt->isCopyStmt()) {
903 generateCopyStmt(Stmt, NewAccesses);
904 isl_ast_expr_free(Expr);
905 } else {
906 createSubstitutions(Expr, Stmt, LTS);
907
908 if (Stmt->isBlockStmt())
909 BlockGen.copyStmt(*Stmt, LTS, NewAccesses);
910 else
911 RegionGen.copyStmt(*Stmt, LTS, NewAccesses);
912 }
913
914 isl_id_to_ast_expr_free(NewAccesses);
915 isl_ast_node_free(User);
916 isl_id_free(Id);
917}
918
920 isl_ast_node_list *List = isl_ast_node_block_get_children(Block);
921
922 for (int i = 0; i < isl_ast_node_list_n_ast_node(List); ++i)
923 create(isl_ast_node_list_get_ast_node(List, i));
924
925 isl_ast_node_free(Block);
926 isl_ast_node_list_free(List);
927}
928
930 switch (isl_ast_node_get_type(Node)) {
932 llvm_unreachable("code generation error");
934 createMark(Node);
935 return;
936 case isl_ast_node_for:
937 createFor(Node);
938 return;
939 case isl_ast_node_if:
940 createIf(Node);
941 return;
943 createUser(Node);
944 return;
946 createBlock(Node);
947 return;
948 }
949
950 llvm_unreachable("Unknown isl_ast_node type");
951}
952
954 // If the Id is already mapped, skip it.
955 if (!IDToValue.count(Id)) {
956 auto *ParamSCEV = (const SCEV *)isl_id_get_user(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(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(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(Inst);
977 auto Address = MemInst ? MemInst.getPointerOperand() : nullptr;
978 if (Address && SE.getUnknown(UndefValue::get(Address->getType())) ==
979 SE.getPointerBase(SE.getSCEV(Address))) {
980 } else if (S.getStmtFor(Inst)) {
981 IsDead = false;
982 } else {
983 auto *Domain = S.getDomainConditions(Inst->getParent()).release();
984 IsDead = isl_set_is_empty(Domain);
986 }
987
988 if (IsDead) {
989 V = UndefValue::get(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(ParamSCEV->getType());
1001
1002 if (!preloadInvariantEquivClass(*IAClass)) {
1003 isl_id_free(Id);
1004 return false;
1005 }
1006 }
1007 }
1008
1009 V = V ? V : generateSCEV(ParamSCEV);
1010 IDToValue[Id] = V;
1011 }
1012
1013 isl_id_free(Id);
1014 return true;
1015}
1016
1018 for (unsigned i = 0, e = isl_set_dim(Set, isl_dim_param); i < e; ++i) {
1019 if (!isl_set_involves_dims(Set, isl_dim_param, i, 1))
1020 continue;
1022 if (!materializeValue(Id))
1023 return false;
1024 }
1025 return true;
1026}
1027
1029 for (const SCEV *Param : S.parameters()) {
1030 isl_id *Id = S.getIdForParam(Param).release();
1031 if (!materializeValue(Id))
1032 return false;
1033 }
1034 return true;
1035}
1036
1038 isl_ast_build *Build,
1039 Instruction *AccInst) {
1040 isl_pw_multi_aff *PWAccRel = isl_pw_multi_aff_from_set(AccessRange);
1041 isl_ast_expr *Access =
1043 auto *Address = isl_ast_expr_address_of(Access);
1044 auto *AddressValue = ExprBuilder.create(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 + ".load");
1054 if (LoadInst *PreloadInst = dyn_cast<LoadInst>(PreloadVal))
1055 PreloadInst->setAlignment(cast<LoadInst>(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(AccInst);
1061
1062 return PreloadVal;
1063}
1064
1067 isl_set *AccessRange = isl_map_range(MA.getAddressFunction().release());
1068 AccessRange = isl_set_gist_params(AccessRange, S.getContext().release());
1069
1070 if (!materializeParameters(AccessRange)) {
1071 isl_set_free(AccessRange);
1073 return nullptr;
1074 }
1075
1076 auto *Build =
1077 isl_ast_build_from_context(isl_set_universe(S.getParamSpace().release()));
1079 bool AlwaysExecuted = isl_set_is_equal(Domain, Universe);
1080 isl_set_free(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);
1090 return PreloadVal;
1091 }
1092
1094 isl_ast_build_free(Build);
1095 isl_set_free(AccessRange);
1097 return nullptr;
1098 }
1099
1100 isl_ast_expr *DomainCond = isl_ast_build_expr_from_set(Build, Domain);
1101 Domain = nullptr;
1102
1103 ExprBuilder.setTrackOverflow(true);
1104 Value *Cond = ExprBuilder.createBool(DomainCond);
1105 Value *OverflowHappened = Builder.CreateNot(ExprBuilder.getOverflowState(),
1106 "polly.preload.cond.overflown");
1107 Cond = Builder.CreateAnd(Cond, OverflowHappened, "polly.preload.cond.result");
1108 ExprBuilder.setTrackOverflow(false);
1109
1110 if (!Cond->getType()->isIntegerTy(1))
1111 Cond = Builder.CreateIsNotNull(Cond);
1112
1113 BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
1114 Builder.GetInsertPoint(), GenDT, GenLI);
1115 CondBB->setName("polly.preload.cond");
1116
1117 BasicBlock *MergeBB = SplitBlock(CondBB, CondBB->begin(), GenDT, 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, "polly.preload.exec", F);
1123
1124 GenDT->addNewBlock(ExecBB, CondBB);
1125 if (Loop *L = GenLI->getLoopFor(CondBB))
1126 L->addBasicBlockToLoop(ExecBB, *GenLI);
1127
1128 auto *CondBBTerminator = CondBB->getTerminator();
1129 Builder.SetInsertPoint(CondBB, CondBBTerminator->getIterator());
1130 Builder.CreateCondBr(Cond, ExecBB, MergeBB);
1131 CondBBTerminator->eraseFromParent();
1132
1133 Builder.SetInsertPoint(ExecBB);
1134 Builder.CreateBr(MergeBB);
1135
1136 Builder.SetInsertPoint(ExecBB, ExecBB->getTerminator()->getIterator());
1137 Value *PreAccInst = preloadUnconditionally(AccessRange, Build, AccInst);
1138 Builder.SetInsertPoint(MergeBB, MergeBB->getTerminator()->getIterator());
1139 auto *MergePHI = Builder.CreatePHI(
1140 AccInstTy, 2, "polly.preload." + AccInst->getName() + ".merge");
1141 PreloadVal = MergePHI;
1142
1143 if (!PreAccInst) {
1144 PreloadVal = nullptr;
1145 PreAccInst = UndefValue::get(AccInstTy);
1146 }
1147
1148 MergePHI->addIncoming(PreAccInst, ExecBB);
1149 MergePHI->addIncoming(Constant::getNullValue(AccInstTy), CondBB);
1150
1151 isl_ast_build_free(Build);
1152 return PreloadVal;
1153}
1154
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(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(IAClass.IdentifyingPointer, IAClass.AccessType);
1177 if (!PreloadedPtrs.insert(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(SAI->getBasePtr())) {
1187 if (!preloadInvariantEquivClass(*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(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(i);
1200 SetVector<Value *> Values;
1201 findValues(Dim, SE, Values);
1202 for (auto *Val : Values) {
1203 if (auto *BaseIAClass = S.lookupInvariantEquivClass(Val)) {
1204 if (!preloadInvariantEquivClass(*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(BaseExecutionCtx);
1211 }
1212 }
1213 }
1214
1215 Instruction *AccInst = MA->getAccessInstruction();
1216 Type *AccInstTy = AccInst->getType();
1217
1218 Value *PreloadVal = preloadInvariantLoad(*MA, 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(AccInstTy)) {
1229 isl_id *ParamId = S.getIdForParam(SE.getSCEV(AccInst)).release();
1230 if (ParamId)
1231 IDToValue[ParamId] = PreloadVal;
1232 isl_id_free(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(PreloadVal, Alloca);
1240 ValueMapT PreloadedPointer;
1241 PreloadedPointer[PreloadVal] = AccInst;
1242 Annotator.addAlternativeAliasBases(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.
1267 for (auto *U : MAAccInst->users())
1268 if (Instruction *UI = dyn_cast<Instruction>(U))
1269 if (!S.contains(UI))
1270 EscapeUsers.push_back(UI);
1271
1272 if (EscapeUsers.empty())
1273 continue;
1274
1276 std::make_pair(Alloca, std::move(EscapeUsers));
1277 }
1278
1279 return true;
1280}
1281
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(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(NewArrayType, 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(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>(StartExitBlocks);
1319 Builder.SetInsertPoint(StartBlock,
1320 StartBlock->getTerminator()->getIterator());
1321 auto *CreatedArray = Builder.CreateMalloc(
1322 IntPtrTy, SAI->getElementType(),
1323 ConstantInt::get(Type::getInt64Ty(Ctx), Size),
1324 ConstantInt::get(Type::getInt64Ty(Ctx), ArraySizeInt), nullptr,
1325 SAI->getName());
1326
1327 SAI->setBasePtr(CreatedArray);
1328
1329 // Insert the free call at polly.exiting
1330 BasicBlock *ExitingBlock = std::get<1>(StartExitBlocks);
1331 Builder.SetInsertPoint(ExitingBlock,
1332 ExitingBlock->getTerminator()->getIterator());
1333 Builder.CreateFree(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);
1344 CreatedArray->setAlignment(Align(PollyTargetFirstLevelCacheLineSize));
1345 SAI->setBasePtr(CreatedArray);
1346 }
1347 }
1348}
1349
1351 auto &InvariantEquivClasses = S.getInvariantAccesses();
1352 if (InvariantEquivClasses.empty())
1353 return true;
1354
1355 BasicBlock *PreLoadBB = SplitBlock(Builder.GetInsertBlock(),
1356 Builder.GetInsertPoint(), GenDT, GenLI);
1357 PreLoadBB->setName("polly.preload.begin");
1358 Builder.SetInsertPoint(PreLoadBB, PreLoadBB->begin());
1359
1360 for (auto &IAClass : InvariantEquivClasses)
1361 if (!preloadInvariantEquivClass(IAClass))
1362 return false;
1363
1364 return true;
1365}
1366
1368 // Materialize values for the parameters of the SCoP.
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(S.getEntry());
1378
1379 while (L != nullptr && S.contains(L))
1380 L = L->getParentLoop();
1381
1382 while (L != nullptr) {
1384 L = L->getParentLoop();
1385 }
1386
1387 isl_set_free(Context);
1388}
1389
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, Builder.GetInsertBlock()->getParent(), *GenSE, DL,
1407 "polly", Expr, Expr->getType(), InsertLocation,
1408 &ValueMap, /*LoopToScevMap*/ nullptr,
1409 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,
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(isl::manage_copy(Condition))) {
1425 isl_ast_expr_free(Condition);
1426 return Builder.getFalse();
1427 }
1428
1429 ExprBuilder.setTrackOverflow(true);
1430 Value *RTC = ExprBuilder.create(Condition);
1431 if (!RTC->getType()->isIntegerTy(1))
1432 RTC = Builder.CreateIsNotNull(RTC);
1433 Value *OverflowHappened =
1434 Builder.CreateNot(ExprBuilder.getOverflowState(), "polly.rtc.overflown");
1435
1437 auto *F = Builder.GetInsertBlock()->getParent();
1439 Builder,
1440 "F: " + F->getName().str() + " R: " + S.getRegion().getNameStr() +
1441 "RTC: ",
1442 RTC, " Overflow: ", OverflowHappened,
1443 "\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(RTC, OverflowHappened, "polly.rtc.result");
1450 ExprBuilder.setTrackOverflow(false);
1451
1452 if (!isa<ConstantInt>(RTC))
1453 VersionedScops++;
1454
1455 return RTC;
1456}
polly dump Polly Dump Function
static void findReferencesInInst(Instruction *Inst, ScopStmt *UserStmt, Loop *UserScope, const ValueMapT &GlobalMap, SetVector< Value * > &Values, SetVector< const SCEV * > &SCEVs)
static void findReferencesByUse(Value *SrcVal, ScopStmt *UserStmt, Loop *UserScope, const ValueMapT &GlobalMap, SetVector< Value * > &Values, SetVector< const SCEV * > &SCEVs)
static void addReferencesFromStmtSet(isl::set Set, SubtreeReferences *UserPtr)
Extract the out-of-scop values and SCEVs referenced from a set describing a ScopStmt.
static cl::opt< bool > PollyGenerateRTCPrint("polly-codegen-emit-rtc-print", cl::desc("Emit code that prints the runtime check result dynamically."), cl::Hidden, cl::cat(PollyCategory))
static void addReferencesFromStmtUnionSet(isl::union_set USet, SubtreeReferences &References)
Extract the out-of-scop values and SCEVs referenced from a union set referencing multiple ScopStmts.
static cl::opt< bool > PollyGenerateExpressions("polly-codegen-generate-expressions", cl::desc("Generate AST expressions for unmodified and modified accesses"), cl::Hidden, cl::cat(PollyCategory))
STATISTIC(VersionedScops, "Number of SCoPs that required versioning.")
static bool IsLoopVectorizerDisabled(isl::ast_node_for Node)
Restore the initial ordering of dimensions of the band node.
static void findReferencesInStmt(ScopStmt *Stmt, SetVector< Value * > &Values, ValueMapT &GlobalMap, SetVector< const SCEV * > &SCEVs)
static cl::opt< OpenMPBackend > PollyOmpBackend("polly-omp-backend", cl::desc("Choose the OpenMP library to use:"), cl::values(clEnumValN(OpenMPBackend::GNU, "GNU", "GNU OpenMP"), clEnumValN(OpenMPBackend::LLVM, "LLVM", "LLVM OpenMP")), cl::Hidden, cl::init(OpenMPBackend::GNU), cl::cat(PollyCategory))
static cl::opt< int > PollyTargetFirstLevelCacheLineSize("polly-target-first-level-cache-line-size", cl::desc("The size of the first level cache line size specified in bytes."), cl::Hidden, cl::init(64), cl::cat(PollyCategory))
OpenMPBackend
OpenMP backend options.
llvm::cl::OptionCategory PollyCategory
__isl_give isl_pw_multi_aff * isl_pw_multi_aff_from_set(__isl_take isl_set *set)
Definition isl_aff.c:5608
__isl_export __isl_give isl_ast_expr * isl_ast_node_for_get_init(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1383
__isl_export __isl_give isl_ast_node_list * isl_ast_node_block_get_children(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1576
__isl_null isl_ast_expr * isl_ast_expr_free(__isl_take isl_ast_expr *expr)
Definition isl_ast.c:243
__isl_give isl_ast_expr * isl_ast_expr_address_of(__isl_take isl_ast_expr *expr)
Definition isl_ast.c:649
isl_size isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr)
Definition isl_ast.c:359
enum isl_ast_expr_op_type isl_ast_expr_get_op_type(__isl_keep isl_ast_expr *expr)
Definition isl_ast.c:342
__isl_give isl_ast_expr * isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr *expr, int pos)
Definition isl_ast.c:377
__isl_export __isl_give isl_ast_node * isl_ast_node_mark_get_node(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1650
__isl_export __isl_give isl_ast_expr * isl_ast_node_for_get_inc(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1416
__isl_give isl_ast_node * isl_ast_node_if_get_else(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1517
__isl_export __isl_give isl_ast_node * isl_ast_node_for_get_body(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1348
__isl_give isl_id * isl_ast_expr_get_id(__isl_keep isl_ast_expr *expr)
Definition isl_ast.c:313
__isl_export __isl_give isl_ast_expr * isl_ast_node_user_get_expr(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1629
__isl_export __isl_give isl_ast_expr * isl_ast_node_if_get_cond(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1568
__isl_export __isl_give isl_id * isl_ast_node_mark_get_id(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1640
__isl_export __isl_give isl_ast_expr * isl_ast_node_for_get_iterator(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1375
__isl_null isl_ast_node * isl_ast_node_free(__isl_take isl_ast_node *node)
Definition isl_ast.c:1180
__isl_give isl_ast_node * isl_ast_node_if_get_then(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1482
isl_bool isl_ast_node_if_has_else(__isl_keep isl_ast_node *node)
Definition isl_ast.c:1499
__isl_give isl_ast_expr * isl_ast_expr_copy(__isl_keep isl_ast_expr *expr)
Definition isl_ast.c:195
__isl_overload __isl_give isl_ast_expr * isl_ast_build_access_from_pw_multi_aff(__isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
__isl_export __isl_give isl_ast_build * isl_ast_build_from_context(__isl_take isl_set *set)
__isl_overload __isl_give isl_ast_expr * isl_ast_build_expr_from_set(__isl_keep isl_ast_build *build, __isl_take isl_set *set)
__isl_null isl_ast_build * isl_ast_build_free(__isl_take isl_ast_build *build)
@ isl_ast_expr_id
Definition ast_type.h:78
@ isl_ast_expr_op
Definition ast_type.h:77
#define isl_ast_op_le
Definition ast_type.h:66
#define isl_ast_op_lt
Definition ast_type.h:67
isl_ast_node_type
Definition ast_type.h:82
@ isl_ast_node_block
Definition ast_type.h:86
@ isl_ast_node_for
Definition ast_type.h:84
@ isl_ast_node_mark
Definition ast_type.h:87
@ isl_ast_node_if
Definition ast_type.h:85
@ isl_ast_node_error
Definition ast_type.h:83
@ isl_ast_node_user
Definition ast_type.h:88
#define isl_ast_op_type
Definition ast_type.h:46
#define isl_ast_op_call
Definition ast_type.h:70
bool is_null() const
isl::union_map get_schedule() const
isl::ast_expr access_from(isl::multi_pw_aff mpa) const
isl::id get_id() const
isl::ast_expr get_op_arg(int pos) const
boolean isa() const
isl::val val() const
__isl_give isl_ast_expr * release()
__isl_keep isl_ast_expr * get() const
isl::val get_val() const
isl::ast_node_list children() const
isl::ast_node body() const
isl::ast_expr init() const
isl::ast_expr cond() const
isl::ast_expr inc() const
isl::ast_expr iterator() const
__isl_keep isl_ast_node * get() const
__isl_give isl_ast_node * release()
static isl::id_to_ast_expr alloc(isl::ctx ctx, int min_size)
isl::id_to_ast_expr set(isl::id key, isl::ast_expr val) const
__isl_give isl_id_to_ast_expr * release()
void * get_user() const
__isl_keep isl_id * get() const
__isl_give isl_map * release()
isl::set domain() const
isl::set intersect(isl::set set2) const
isl::id get_tuple_id() const
__isl_give isl_set * copy() const &
isl::set intersect_params(isl::set params) const
boolean is_empty() const
__isl_give isl_set * release()
isl::space align_params(isl::space space2) const
isl::union_set domain() const
__isl_give isl_union_set * release()
isl::set_list get_set_list() const
long get_num_si() const
boolean is_one() const
boolean is_zero() const
SmallVector< Instruction *, 4 > EscapeUserVectorTy
Simple vector of instructions to store escape users.
static bool isParallel(const isl::ast_node &Node)
Is this loop a parallel loop?
Definition IslAst.cpp:578
static bool isExecutedInParallel(const isl::ast_node &Node)
Will the loop be run as thread parallel?
Definition IslAst.cpp:598
static isl::union_map getSchedule(const isl::ast_node &Node)
Get the nodes schedule or a nullptr if not available.
Definition IslAst.cpp:617
static isl::ast_build getBuild(const isl::ast_node &Node)
Get the nodes build context or a nullptr if not available.
Definition IslAst.cpp:634
static bool isReductionParallel(const isl::ast_node &Node)
Is this loop a reduction parallel loop?
Definition IslAst.cpp:593
llvm::MapVector< isl_id *, llvm::AssertingVH< llvm::Value > > IDToValueTy
A map from isl_ids to llvm::Values.
Value * preloadUnconditionally(__isl_take isl_set *AccessRange, isl_ast_build *Build, Instruction *AccInst)
Preload the memory access at AccessRange with Build.
void addParameters(__isl_take isl_set *Context)
Value * preloadInvariantLoad(const MemoryAccess &MA, __isl_take isl_set *Domain)
Preload the memory load access MA.
Value * getLatestValue(Value *Original) const
Return the most up-to-date version of the llvm::Value for code generation.
void create(__isl_take isl_ast_node *Node)
RegionGenerator RegionGen
The generator used to copy a non-affine region.
ScopAnnotator & Annotator
BlockGenerator::AllocaMapTy ScalarMap
Maps used by the block and region generator to demote scalars.
SmallVector< Function *, 8 > ParallelSubfunctions
A collection of all parallel subfunctions that have been created.
IslExprBuilder::IDToValueTy IDToValue
bool preloadInvariantEquivClass(InvariantEquivClassTy &IAClass)
Preload the invariant access equivalence class IAClass.
IslExprBuilder ExprBuilder
void createForSequential(isl::ast_node_for For, bool MarkParallel)
__isl_give isl_id_to_ast_expr * createNewAccesses(ScopStmt *Stmt, __isl_keep isl_ast_node *Node)
Create new access functions for modified memory accesses.
void createForParallel(__isl_take isl_ast_node *For)
Create LLVM-IR that executes a for node thread parallel.
bool preloadInvariantLoads()
Preload all memory loads that are invariant.
Value * generateSCEV(const SCEV *Expr)
Generate code for a given SCEV*.
bool materializeParameters()
Materialize all parameters in the current scop.
const DataLayout & DL
ValueMapT ValueMap
A set of Value -> Value remappings to apply when generating new code.
bool materializeValue(__isl_take isl_id *Id)
Materialize code for Id if it was not done before.
SmallSet< std::pair< const SCEV *, Type * >, 16 > PreloadedPtrs
Set to remember materialized invariant loads.
Value * materializeNonScopLoopInductionVariable(const Loop *L)
Materialize a canonical loop induction variable for L, which is a loop that is not present in the Sco...
virtual void createBlock(__isl_take isl_ast_node *Block)
virtual void createUser(__isl_take isl_ast_node *User)
ScalarEvolution & SE
void createSubstitutionsVector(__isl_take isl_ast_expr *Expr, ScopStmt *Stmt, std::vector< LoopToScevMapT > &VLTS, std::vector< Value * > &IVS, __isl_take isl_id *IteratorID)
DominatorTree * GenDT
Relates to the region where the code is emitted into.
virtual void createFor(__isl_take isl_ast_node *For)
virtual void createMark(__isl_take isl_ast_node *Marker)
Generate code for a marker now.
void allocateNewArrays(BBPair StartExitBlocks)
Allocate memory for all new arrays created by Polly.
virtual isl::union_map getScheduleForAstNode(const isl::ast_node &Node)
Get the schedule for a given AST node.
PollyIRBuilder & Builder
void getReferencesInSubtree(const isl::ast_node &For, SetVector< Value * > &Values, SetVector< const Loop * > &Loops)
Compute the values and loops referenced in this subtree.
ScalarEvolution * GenSE
void generateCopyStmt(ScopStmt *Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses)
Create code for a copy statement.
virtual void createIf(__isl_take isl_ast_node *If)
void createSubstitutions(__isl_take isl_ast_expr *Expr, ScopStmt *Stmt, LoopToScevMapT &LTS)
Generate LLVM-IR that computes the values of the original induction variables in function of the newl...
isl::ast_expr getUpperBound(isl::ast_node_for For, CmpInst::Predicate &Predicate)
BlockGenerator::EscapeUsersAllocaMapTy EscapeMap
See BlockGenerator::EscapeMap.
BlockGenerator BlockGen
The generator used to copy a basic block.
BlockGenerator & getBlockGenerator()
Get the associated block generator.
int getNumberOfIterations(isl::ast_node_for For)
Return non-negative number of iterations in case of the following form of a loop and -1 otherwise.
Value * createRTC(isl_ast_expr *Condition)
Generate code that evaluates Condition at run-time.
IslExprBuilder & getExprBuilder()
MapVector< const Loop *, const SCEV * > OutsideLoopIterations
The current iteration of out-of-scop loops.
static MemAccInst dyn_cast(llvm::Value &V)
Definition ScopHelper.h:178
Represent memory accesses in statements.
Definition ScopInfo.h:431
Instruction * getAccessInstruction() const
Return the access instruction of this memory access.
Definition ScopInfo.h:885
bool isRead() const
Is this a read memory access?
Definition ScopInfo.h:760
isl::map getAddressFunction() const
Get an isl map describing the memory address accessed.
Definition ScopInfo.cpp:577
const ScopArrayInfo * getScopArrayInfo() const
Legacy name of getOriginalScopArrayInfo().
Definition ScopInfo.h:853
Value * getOriginalBaseAddr() const
Get the original base address of this access (e.g.
Definition ScopInfo.h:833
bool isArrayKind() const
Old name of isOriginalArrayKind.
Definition ScopInfo.h:955
This ParallelLoopGenerator subclass handles the generation of parallelized code, utilizing the GNU Op...
This ParallelLoopGenerator subclass handles the generation of parallelized code, utilizing the LLVM O...
Statement of the Scop.
Definition ScopInfo.h:1140
Scop * getParent()
Definition ScopInfo.h:1528
const std::vector< Instruction * > & getInstructions() const
Definition ScopInfo.h:1531
bool isBlockStmt() const
Return true if this statement represents a single basic block.
Definition ScopInfo.h:1321
size_t size() const
Definition ScopInfo.h:1524
Region * getRegion() const
Get the region represented by this ScopStmt (if any).
Definition ScopInfo.h:1330
BasicBlock * getBasicBlock() const
Get the BasicBlock represented by this ScopStmt (if any).
Definition ScopInfo.h:1318
bool isCopyStmt() const
Return true if this is a copy statement.
Definition ScopInfo.h:1324
bool isRegionStmt() const
Return true if this statement represents a whole region.
Definition ScopInfo.h:1333
Loop * getLoopForDimension(unsigned Dimension) const
Get the loop for a dimension.
isl::set getDomain() const
Get the iteration domain of this ScopStmt.
void setAstBuild(isl::ast_build B)
Set the isl AST build.
Definition ScopInfo.h:1562
iterator begin()
Definition ScopInfo.h:1520
ScalarEvolution * getSE() const
Return the scalar evolution.
isl::ctx getIslCtx() const
Get the isl context of this static control part.
LoopInfo * getLI() const
Return the LoopInfo used for this Scop.
Definition ScopInfo.h:2013
bool contains(const Loop *L) const
Check if L is contained in the SCoP.
Definition ScopInfo.h:2095
const Region & getRegion() const
Get the maximum region of this static control part.
Definition ScopInfo.h:2088
isl::set getContext() const
Get the constraint on parameter of this Scop.
Determine the nature of a value's use within a statement.
const SCEV * getScevExpr() const
Return the ScalarEvolution representation of Val.
static VirtualUse create(Scop *S, const Use &U, LoopInfo *LI, bool Virtual)
Get a VirtualUse for an llvm::Use.
UseKind getKind() const
Return the type of use.
#define __isl_take
Definition ctx.h:22
#define __isl_give
Definition ctx.h:19
#define __isl_keep
Definition ctx.h:25
__isl_export __isl_keep const char * isl_id_get_name(__isl_keep isl_id *id)
Definition isl_id.c:41
__isl_null isl_id * isl_id_free(__isl_take isl_id *id)
Definition isl_id.c:207
void * isl_id_get_user(__isl_keep isl_id *id)
Definition isl_id.c:36
enum isl_ast_expr_type isl_ast_expr_get_type(__isl_keep isl_ast_expr *expr)
Definition isl_ast.c:276
enum isl_ast_node_type isl_ast_node_get_type(__isl_keep isl_ast_node *node)
Definition isl_ast.c:907
#define isl_set
#define assert(exp)
__isl_export __isl_give isl_set * isl_map_domain(__isl_take isl_map *bmap)
Definition isl_map.c:8129
__isl_export __isl_give isl_set * isl_map_range(__isl_take isl_map *map)
Definition isl_map.c:6109
aff manage_copy(__isl_keep isl_aff *ptr)
boolean manage(isl_bool val)
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
std::forward_list< MemoryAccess * > MemoryAccessList
Ordered list type to hold accesses.
Definition ScopInfo.h:1091
void findValues(const llvm::SCEV *Expr, llvm::ScalarEvolution &SE, llvm::SetVector< llvm::Value * > &Values)
Find the values referenced by SCEVUnknowns in a given SCEV expression.
void findLoops(const llvm::SCEV *Expr, llvm::SetVector< const llvm::Loop * > &Loops)
Find the loops referenced from a SCEV expression.
llvm::DenseMap< const llvm::Loop *, const llvm::SCEV * > LoopToScevMapT
Same as llvm/Analysis/ScalarEvolutionExpressions.h.
Definition ScopHelper.h:40
llvm::Value * expandCodeFor(Scop &S, llvm::ScalarEvolution &SE, llvm::Function *GenFn, llvm::ScalarEvolution &GenSE, const llvm::DataLayout &DL, const char *Name, const llvm::SCEV *E, llvm::Type *Ty, llvm::BasicBlock::iterator IP, ValueMapT *VMap, LoopToScevMapT *LoopMap, llvm::BasicBlock *RTCBB)
Wrapper for SCEVExpander extended to all Polly features.
@ Value
MemoryKind::Value: Models an llvm::Value.
Definition ScopInfo.h:154
void addReferencesFromStmt(ScopStmt *Stmt, void *UserPtr, bool CreateScalarRefs=true)
Extract the out-of-scop values and SCEVs referenced from a ScopStmt.
BandAttr * getLoopAttr(const isl::id &Id)
Return the BandAttr of a loop's isl::id.
Value * createLoop(Value *LowerBound, Value *UpperBound, Value *Stride, PollyIRBuilder &Builder, LoopInfo &LI, DominatorTree &DT, BasicBlock *&ExitBlock, ICmpInst::Predicate Predicate, ScopAnnotator *Annotator=nullptr, bool Parallel=false, bool UseGuard=true, bool LoopVectDisabled=false)
Create a scalar do/for-style loop.
llvm::DenseMap< llvm::AssertingVH< llvm::Value >, llvm::AssertingVH< llvm::Value > > ValueMapT
Type to remap values.
Definition ScopHelper.h:105
std::pair< llvm::BasicBlock *, llvm::BasicBlock * > BBPair
Type to hold region delimiters (entry & exit block).
Definition Utils.h:31
__isl_export __isl_give isl_set * isl_set_universe(__isl_take isl_space *space)
Definition isl_map.c:6366
__isl_export __isl_give isl_space * isl_set_get_space(__isl_keep isl_set *set)
Definition isl_map.c:603
__isl_export isl_bool isl_set_is_equal(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
Definition isl_map.c:9083
__isl_export __isl_give isl_set * isl_set_intersect_params(__isl_take isl_set *set, __isl_take isl_set *params)
Definition isl_map.c:3982
__isl_export __isl_give isl_set * isl_set_gist_params(__isl_take isl_set *set, __isl_take isl_set *context)
__isl_null isl_set * isl_set_free(__isl_take isl_set *set)
Definition isl_map.c:3513
__isl_export isl_bool isl_set_is_subset(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
isl_bool isl_set_involves_dims(__isl_keep isl_set *set, enum isl_dim_type type, unsigned first, unsigned n)
Definition isl_map.c:2986
isl_size isl_set_dim(__isl_keep isl_set *set, enum isl_dim_type type)
Definition isl_map.c:129
__isl_give isl_id * isl_set_get_dim_id(__isl_keep isl_set *set, enum isl_dim_type type, unsigned pos)
Definition isl_map.c:1003
__isl_export isl_bool isl_set_is_empty(__isl_keep isl_set *set)
Definition isl_map.c:9163
@ isl_dim_param
Definition space_type.h:15
Represent the attributes of a loop.
Definition ScopHelper.h:554
Type for equivalent invariant accesses and their domain context.
Definition ScopInfo.h:1106
MemoryAccessList InvariantAccesses
Memory accesses now treated invariant.
Definition ScopInfo.h:1115
Type * AccessType
The type of the invariant access.
Definition ScopInfo.h:1127
isl::set ExecutionContext
The execution context under which the memory location is accessed.
Definition ScopInfo.h:1121
const SCEV * IdentifyingPointer
The pointer that identifies this equivalence class.
Definition ScopInfo.h:1108
static void createCPUPrinter(PollyIRBuilder &Builder, Args... args)
Print a set of LLVM-IR Values or StringRefs via printf.
static TupleKindPtr Domain("Domain")
static TupleKindPtr Ctx
__isl_give isl_set * isl_set_from_union_set(__isl_take isl_union_set *uset)