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
318 return IslAstInfo::getSchedule(Node);
319}
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
372Value *IslNodeBuilder::getLatestValue(Value *Original) const {
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) {
564 case OpenMPBackend::GNU:
565 ParallelLoopGenPtr.reset(new ParallelLoopGeneratorGOMP(Builder, DL));
566 break;
567 case OpenMPBackend::LLVM:
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();
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
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
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");
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
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");
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::id id() 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.
void switchGeneratedFunc(Function *GenFn, DominatorTree *GenDT, LoopInfo *GenLI, ScalarEvolution *GenSE)
Change the function that code is emitted into.
void copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses)
Copy the basic block.
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
bool hasLargeInts(isl::ast_expr Expr)
Check if an Expr contains integer constants larger than 64 bit.
void setTrackOverflow(bool Enable)
Change if runtime overflows are tracked or not.
llvm::Value * getOverflowState() const
Return the current overflow status or nullptr if it is not tracked.
llvm::MapVector< isl_id *, llvm::AssertingVH< llvm::Value > > IDToValueTy
A map from isl_ids to llvm::Values.
llvm::Value * create(__isl_take isl_ast_expr *Expr)
Create LLVM-IR for an isl_ast_expr[ession].
llvm::Type * getWidestType(llvm::Type *T1, llvm::Type *T2)
Return the largest of two types.
std::pair< llvm::Value *, llvm::Type * > createAccessAddress(__isl_take isl_ast_expr *Expr)
Create LLVM-IR that computes the memory location of an access expression.
llvm::IntegerType * getType(__isl_keep isl_ast_expr *Expr)
Return the type with which this expression should be computed.
void switchGeneratedFunc(llvm::Function *GenFn, llvm::DominatorTree *GenDT, llvm::LoopInfo *GenLI, llvm::ScalarEvolution *GenSE)
Change the function that code is emitted into.
llvm::Value * createBool(__isl_take isl_ast_expr *Expr)
Create LLVM-IR for an isl_ast_expr[ession] and cast it to i1.
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.
DominatorTree & DT
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...
void copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS, __isl_keep isl_id_to_ast_expr *IdToAstExp)
Copy the region statement Stmt.
void resetAlternativeAliasBases()
Delete the set of alternative alias bases.
Definition: IRBuilder.h:86
BandAttr *& getStagingAttrEnv()
Definition: IRBuilder.h:90
void addAlternativeAliasBases(llvm::DenseMap< llvm::AssertingVH< llvm::Value >, llvm::AssertingVH< llvm::Value > > &NewMap)
Add alternative alias based pointers.
Definition: IRBuilder.h:79
void popLoop(bool isParallel)
Remove the last added loop.
Definition: IRBuilder.cpp:117
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.
Definition: ScopInfo.cpp:1231
isl::set getDomain() const
Get the iteration domain of this ScopStmt.
Definition: ScopInfo.cpp:1237
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.
Definition: ScopInfo.cpp:2300
isl::ctx getIslCtx() const
Get the isl context of this static control part.
Definition: ScopInfo.cpp:2171
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.
Definition: ScopInfo.cpp:1830
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 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
struct isl_set isl_set
Definition: map_type.h:26
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::pair< llvm::BasicBlock *, llvm::BasicBlock * > BBPair
Type to hold region delimiters (entry & exit block).
Definition: Utils.h:31
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::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.
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.
Definition: ScopHelper.cpp:874
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:106
llvm::DenseMap< const llvm::Loop *, const llvm::SCEV * > LoopToScevMapT
Same as llvm/Analysis/ScalarEvolutionExpressions.h.
Definition: ScopHelper.h:40
std::forward_list< MemoryAccess * > MemoryAccessList
Ordered list type to hold accesses.
Definition: ScopInfo.h:1091
__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)