28#include "llvm/ADT/APInt.h"
29#include "llvm/ADT/PostOrderIterator.h"
30#include "llvm/ADT/SetVector.h"
31#include "llvm/ADT/SmallPtrSet.h"
32#include "llvm/ADT/Statistic.h"
33#include "llvm/Analysis/LoopInfo.h"
34#include "llvm/Analysis/RegionInfo.h"
35#include "llvm/Analysis/ScalarEvolution.h"
36#include "llvm/Analysis/ScalarEvolutionExpressions.h"
37#include "llvm/IR/BasicBlock.h"
38#include "llvm/IR/Constant.h"
39#include "llvm/IR/Constants.h"
40#include "llvm/IR/DataLayout.h"
41#include "llvm/IR/DerivedTypes.h"
42#include "llvm/IR/Dominators.h"
43#include "llvm/IR/Function.h"
44#include "llvm/IR/InstrTypes.h"
45#include "llvm/IR/Instruction.h"
46#include "llvm/IR/Instructions.h"
47#include "llvm/IR/Type.h"
48#include "llvm/IR/Value.h"
49#include "llvm/Support/Casting.h"
50#include "llvm/Support/CommandLine.h"
51#include "llvm/Support/ErrorHandling.h"
52#include "llvm/Transforms/Utils/BasicBlockUtils.h"
74#define DEBUG_TYPE "polly-codegen"
76STATISTIC(VersionedScops,
"Number of SCoPs that required versioning.");
78STATISTIC(SequentialLoops,
"Number of generated sequential for-loops");
79STATISTIC(ParallelLoops,
"Number of generated parallel for-loops");
80STATISTIC(IfConditions,
"Number of generated if-conditions");
86 "polly-codegen-emit-rtc-print",
87 cl::desc(
"Emit code that prints the runtime check result dynamically."),
95 "polly-codegen-generate-expressions",
96 cl::desc(
"Generate AST expressions for unmodified and modified accesses"),
100 "polly-target-first-level-cache-line-size",
101 cl::desc(
"The size of the first level cache line size specified in bytes."),
105 "polly-omp-backend", cl::desc(
"Choose the OpenMP library to use:"),
111 ICmpInst::Predicate &Predicate) {
115 "conditional expression is not an atomic upper bound");
121 Predicate = ICmpInst::ICMP_SLE;
124 Predicate = ICmpInst::ICMP_SLT;
127 llvm_unreachable(
"Unexpected comparison type in loop condition");
133 "conditional expression is not an atomic upper bound");
138 "Could not get the iterator");
143 "conditional expression is not an atomic upper bound");
176 CmpInst::Predicate Predicate;
182 if (NumberIterations < 0)
184 if (Predicate == CmpInst::ICMP_SLT)
185 return NumberIterations;
187 return NumberIterations + 1;
191 Loop *UserScope,
const ValueMapT &GlobalMap,
192 SetVector<Value *> &Values,
193 SetVector<const SCEV *> &SCEVs) {
199 if (isa<GlobalValue>(SrcVal))
200 Values.insert(SrcVal);
215 if (
Value *NewVal = GlobalMap.lookup(SrcVal))
216 Values.insert(NewVal);
220 Loop *UserScope,
const ValueMapT &GlobalMap,
221 SetVector<Value *> &Values,
222 SetVector<const SCEV *> &SCEVs) {
223 for (Use &U : Inst->operands())
229 SetVector<const SCEV *> &SCEVs) {
233 Loop *Scope = LI->getLoopFor(BB);
238 for (BasicBlock *BB : Stmt->
getRegion()->blocks()) {
239 Loop *Scope = LI->getLoopFor(BB);
240 for (Instruction &Inst : *BB)
247 bool CreateScalarRefs) {
253 for (
auto &Access : *Stmt) {
254 if (References.ParamSpace) {
255 isl::space ParamSpace = Access->getLatestAccessRelation().get_space();
256 (*References.ParamSpace) =
260 if (Access->isLatestArrayKind()) {
261 auto *BasePtr = Access->getLatestScopArrayInfo()->getBasePtr();
262 if (Instruction *OpInst = dyn_cast<Instruction>(BasePtr))
266 References.Values.insert(BasePtr);
270 if (CreateScalarRefs)
271 References.Values.insert(References.BlockGen.getOrCreateAlloca(*Access));
318 SetVector<Value *> &Values,
319 SetVector<const Loop *> &Loops) {
320 SetVector<const SCEV *> SCEVs;
325 Values.insert(I.second);
329 Values.insert(cast<SCEVUnknown>(I.second)->getValue());
334 for (
const SCEV *Expr : SCEVs) {
339 Values.remove_if([](
const Value *V) {
return isa<GlobalValue>(V); });
352 Loops.remove_if([
this](
const Loop *L) {
353 return S.contains(L) || L->contains(
S.getEntry());
362 SetVector<Value *> ReplacedValues;
363 for (
Value *V : Values) {
366 Values = ReplacedValues;
370 SmallPtrSet<Value *, 5> Inserted;
373 IDToValue[I.first] = NewValues[I.second];
374 Inserted.insert(I.second);
377 for (
const auto &I : NewValues) {
378 if (Inserted.count(I.first))
421 "Nest must not overwrite loop attr environment");
443 auto Id = BodyMark.
id();
444 if (strcmp(Id.get_name().c_str(),
"Loop Vectorizer Disabled") == 0)
451 Value *ValueLB, *ValueUB, *ValueInc;
453 BasicBlock *ExitBlock;
455 CmpInst::Predicate Predicate;
482 if (MaxType != ValueLB->getType())
483 ValueLB =
Builder.CreateSExt(ValueLB, MaxType);
484 if (MaxType != ValueUB->getType())
485 ValueUB =
Builder.CreateSExt(ValueUB, MaxType);
486 if (MaxType != ValueInc->getType())
487 ValueInc =
Builder.CreateSExt(ValueInc, MaxType);
492 !
SE.isKnownPredicate(Predicate,
SE.getSCEV(ValueLB),
SE.getSCEV(ValueUB));
494 Predicate, &
Annotator, MarkParallel, UseGuardBB,
495 LoopVectorizerDisabled);
504 Builder.SetInsertPoint(&ExitBlock->front());
540 DomTreeNode *
N = DT.getNode(&F->getEntryBlock());
541 std::vector<BasicBlock *> Nodes;
546 for (po_iterator<DomTreeNode *> I = po_begin(
N), E = po_end(
N); I != E; ++I)
547 Nodes.push_back(I->getBlock());
549 for (BasicBlock *BB : Nodes)
557 Value *ValueLB, *ValueUB, *ValueInc;
560 CmpInst::Predicate Predicate;
565 BasicBlock *ParBB = SplitBlock(
Builder.GetInsertBlock(),
567 ParBB->setName(
"polly.parallel.for");
568 Builder.SetInsertPoint(&ParBB->front());
584 if (Predicate == CmpInst::ICMP_SLT)
586 ValueUB,
Builder.CreateSExt(
Builder.getTrue(), ValueUB->getType()));
593 if (MaxType != ValueLB->getType())
594 ValueLB =
Builder.CreateSExt(ValueLB, MaxType);
595 if (MaxType != ValueUB->getType())
596 ValueUB =
Builder.CreateSExt(ValueUB, MaxType);
597 if (MaxType != ValueInc->getType())
598 ValueInc =
Builder.CreateSExt(ValueInc, MaxType);
600 BasicBlock::iterator LoopBody;
602 SetVector<Value *> SubtreeValues;
603 SetVector<const Loop *> Loops;
611 for (
const Loop *L : Loops) {
613 SubtreeValues.insert(LoopInductionVar);
618 std::unique_ptr<ParallelLoopGenerator> ParallelLoopGenPtr;
621 case OpenMPBackend::GNU:
622 ParallelLoopGenPtr.reset(
625 case OpenMPBackend::LLVM:
630 IV = ParallelLoopGenPtr->createParallelLoop(
631 ValueLB, ValueUB, ValueInc, SubtreeValues, NewValues, &LoopBody);
632 BasicBlock::iterator AfterLoop =
Builder.GetInsertPoint();
633 Builder.SetInsertPoint(&*LoopBody);
647 for (
auto P : NewValues)
648 NewValuesReverse[P.second] = P.first;
659 Builder.SetInsertPoint(&*AfterLoop);
662 for (
const Loop *L : Loops)
686 LLVMContext &Context = F->getContext();
688 BasicBlock *CondBB = SplitBlock(
Builder.GetInsertBlock(),
690 CondBB->setName(
"polly.cond");
691 BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), &
DT, &
LI);
692 MergeBB->setName(
"polly.merge");
693 BasicBlock *ThenBB = BasicBlock::Create(Context,
"polly.then", F);
694 BasicBlock *ElseBB = BasicBlock::Create(Context,
"polly.else", F);
696 DT.addNewBlock(ThenBB, CondBB);
697 DT.addNewBlock(ElseBB, CondBB);
698 DT.changeImmediateDominator(MergeBB, CondBB);
700 Loop *L =
LI.getLoopFor(CondBB);
702 L->addBasicBlockToLoop(ThenBB,
LI);
703 L->addBasicBlockToLoop(ElseBB,
LI);
706 CondBB->getTerminator()->eraseFromParent();
708 Builder.SetInsertPoint(CondBB);
710 Builder.CreateCondBr(Predicate, ThenBB, ElseBB);
711 Builder.SetInsertPoint(ThenBB);
713 Builder.SetInsertPoint(ElseBB);
715 Builder.SetInsertPoint(&ThenBB->front());
719 Builder.SetInsertPoint(&ElseBB->front());
724 Builder.SetInsertPoint(&MergeBB->front());
738 assert(!Build.
is_null() &&
"Could not obtain isl_ast_build from user node");
741 for (
auto *MA : *Stmt) {
742 if (!MA->hasNewAccessRelation()) {
746 if (MA->getLatestScopArrayInfo()->getBasePtrOriginSAI())
750 dyn_cast<Instruction>(MA->getLatestScopArrayInfo()->getBasePtr());
758 "Only affine memory accesses can be code generated");
772 "Access relation not defined on full schedule domain");
774 "Access relation not defined on full domain");
791 NewAccesses = NewAccesses.
set(MA->getId(), AccessExpr);
798 ScopStmt *Stmt, LoopToScevMapT <S) {
800 "Expression of type 'op' expected");
802 "Operation of type 'call' expected");
818 std::vector<LoopToScevMapT> &VLTS, std::vector<Value *> &IVS,
823 for (
Value *IV : IVS) {
837 auto ReadAccess = Stmt->
begin();
838 auto WriteAccess = ReadAccess++;
839 assert((*ReadAccess)->isRead() && (*WriteAccess)->isMustWrite());
840 assert((*ReadAccess)->getElementType() == (*WriteAccess)->getElementType() &&
841 "Accesses use the same data type");
842 assert((*ReadAccess)->isArrayKind() && (*WriteAccess)->isArrayKind());
844 isl_id_to_ast_expr_get(NewAccesses, (*ReadAccess)->getId().release());
847 isl_id_to_ast_expr_get(NewAccesses, (*WriteAccess)->getId().release());
849 Builder.CreateStore(LoadValue, StoreAddr);
854 "trying to materialize loop induction variable twice");
855 const SCEV *OuterLIV =
SE.getAddRecExpr(
SE.getUnknown(
Builder.getInt64(0)),
889 isl_id_to_ast_expr_free(NewAccesses);
897 for (
int i = 0; i < isl_ast_node_list_n_ast_node(List); ++i)
898 create(isl_ast_node_list_get_ast_node(List, i));
901 isl_ast_node_list_free(List);
907 llvm_unreachable(
"code generation error");
925 llvm_unreachable(
"Unknown isl_ast_node type");
938 SetVector<Value *> Values;
940 for (
auto *Val : Values) {
943 if (
auto *Inst = dyn_cast<Instruction>(Val)) {
944 if (
S.contains(Inst)) {
952 auto Address = MemInst ? MemInst.getPointerOperand() :
nullptr;
953 if (Address &&
SE.getUnknown(UndefValue::get(Address->getType())) ==
954 SE.getPointerBase(
SE.getSCEV(Address))) {
955 }
else if (
S.getStmtFor(Inst)) {
958 auto *
Domain =
S.getDomainConditions(Inst->getParent()).release();
964 V = UndefValue::get(ParamSCEV->getType());
970 if (
auto *IAClass =
S.lookupInvariantEquivClass(Val)) {
974 if (IAClass->InvariantAccesses.empty())
975 V = UndefValue::get(ParamSCEV->getType());
1004 for (
const SCEV *Param :
S.parameters()) {
1005 isl_id *Id =
S.getIdForParam(Param).release();
1014 Instruction *AccInst) {
1024 Type *Ty = AccInst->getType();
1026 auto *Ptr = AddressValue;
1027 auto Name = Ptr->getName();
1028 auto AS = Ptr->getType()->getPointerAddressSpace();
1029 Ptr =
Builder.CreatePointerCast(Ptr, Ty->getPointerTo(AS), Name +
".cast");
1030 PreloadVal =
Builder.CreateLoad(Ty, Ptr, Name +
".load");
1031 if (LoadInst *PreloadInst = dyn_cast<LoadInst>(PreloadVal))
1032 PreloadInst->setAlignment(cast<LoadInst>(AccInst)->getAlign());
1036 if (
SE.isSCEVable(Ty))
1037 SE.forgetValue(AccInst);
1060 Type *AccInstTy = AccInst->getType();
1062 Value *PreloadVal =
nullptr;
1063 if (AlwaysExecuted) {
1083 "polly.preload.cond.overflown");
1084 Cond =
Builder.CreateAnd(Cond, OverflowHappened,
"polly.preload.cond.result");
1087 if (!Cond->getType()->isIntegerTy(1))
1088 Cond =
Builder.CreateIsNotNull(Cond);
1090 BasicBlock *CondBB = SplitBlock(
Builder.GetInsertBlock(),
1092 CondBB->setName(
"polly.preload.cond");
1094 BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), &
DT, &
LI);
1095 MergeBB->setName(
"polly.preload.merge");
1098 LLVMContext &Context = F->getContext();
1099 BasicBlock *ExecBB = BasicBlock::Create(Context,
"polly.preload.exec", F);
1101 DT.addNewBlock(ExecBB, CondBB);
1102 if (Loop *L =
LI.getLoopFor(CondBB))
1103 L->addBasicBlockToLoop(ExecBB,
LI);
1105 auto *CondBBTerminator = CondBB->getTerminator();
1106 Builder.SetInsertPoint(CondBBTerminator);
1107 Builder.CreateCondBr(Cond, ExecBB, MergeBB);
1108 CondBBTerminator->eraseFromParent();
1110 Builder.SetInsertPoint(ExecBB);
1113 Builder.SetInsertPoint(ExecBB->getTerminator());
1115 Builder.SetInsertPoint(MergeBB->getTerminator());
1116 auto *MergePHI =
Builder.CreatePHI(
1117 AccInstTy, 2,
"polly.preload." + AccInst->getName() +
".merge");
1118 PreloadVal = MergePHI;
1121 PreloadVal =
nullptr;
1122 PreAccInst = UndefValue::get(AccInstTy);
1125 MergePHI->addIncoming(PreAccInst, ExecBB);
1126 MergePHI->addIncoming(Constant::getNullValue(AccInstTy), CondBB);
1163 if (
auto *BaseIAClass =
S.lookupInvariantEquivClass(SAI->getBasePtr())) {
1169 isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext;
1170 ExecutionCtx = ExecutionCtx.
intersect(BaseExecutionCtx);
1175 for (
unsigned i = 1, e = SAI->getNumberOfDimensions(); i < e; ++i) {
1176 const SCEV *Dim = SAI->getDimensionSize(i);
1177 SetVector<Value *> Values;
1179 for (
auto *Val : Values) {
1180 if (
auto *BaseIAClass =
S.lookupInvariantEquivClass(Val)) {
1186 isl::set BaseExecutionCtx = BaseIAClass->ExecutionContext;
1187 ExecutionCtx = ExecutionCtx.
intersect(BaseExecutionCtx);
1193 Type *AccInstTy = AccInst->getType();
1201 assert(PreloadVal->getType() == MAAccInst->getType());
1205 if (
SE.isSCEVable(AccInstTy)) {
1206 isl_id *ParamId =
S.getIdForParam(
SE.getSCEV(AccInst)).release();
1212 BasicBlock *EntryBB = &
Builder.GetInsertBlock()->getParent()->getEntryBlock();
1213 auto *
Alloca =
new AllocaInst(AccInstTy,
DL.getAllocaAddrSpace(),
1214 AccInst->getName() +
".preload.s2a",
1215 EntryBB->getFirstInsertionPt());
1218 PreloadedPointer[PreloadVal] = AccInst;
1221 for (
auto *DerivedSAI : SAI->getDerivedSAIs()) {
1222 Value *BasePtr = DerivedSAI->getBasePtr();
1230 assert(BasePtr->getType() == PreloadVal->getType());
1231 DerivedSAI->setBasePtr(PreloadVal);
1244 for (
auto *U : MAAccInst->users())
1245 if (Instruction *UI = dyn_cast<Instruction>(U))
1246 if (!
S.contains(UI))
1247 EscapeUsers.push_back(UI);
1249 if (EscapeUsers.empty())
1253 std::make_pair(
Alloca, std::move(EscapeUsers));
1260 for (
auto &SAI :
S.arrays()) {
1261 if (SAI->getBasePtr())
1264 assert(SAI->getNumberOfDimensions() > 0 && SAI->getDimensionSize(0) &&
1265 "The size of the outermost dimension is used to declare newly "
1266 "created arrays that require memory allocation.");
1268 Type *NewArrayType =
nullptr;
1271 uint64_t ArraySizeInt = 1;
1272 for (
int i = SAI->getNumberOfDimensions() - 1; i >= 0; i--) {
1273 auto *DimSize = SAI->getDimensionSize(i);
1274 unsigned UnsignedDimSize =
static_cast<const SCEVConstant *
>(DimSize)
1279 NewArrayType = SAI->getElementType();
1281 NewArrayType = ArrayType::get(NewArrayType, UnsignedDimSize);
1282 ArraySizeInt *= UnsignedDimSize;
1285 if (SAI->isOnHeap()) {
1286 LLVMContext &
Ctx = NewArrayType->getContext();
1289 auto IntPtrTy =
DL.getIntPtrType(
Ctx);
1292 unsigned Size = SAI->getElemSizeInBytes();
1295 Builder.SetInsertPoint(std::get<0>(StartExitBlocks)->getTerminator());
1296 auto *CreatedArray =
Builder.CreateMalloc(
1297 IntPtrTy, SAI->getElementType(),
1298 ConstantInt::get(Type::getInt64Ty(
Ctx), Size),
1299 ConstantInt::get(Type::getInt64Ty(
Ctx), ArraySizeInt),
nullptr,
1302 SAI->setBasePtr(CreatedArray);
1305 Builder.SetInsertPoint(std::get<1>(StartExitBlocks)->getTerminator());
1306 Builder.CreateFree(CreatedArray);
1308 auto InstIt =
Builder.GetInsertBlock()
1314 auto *CreatedArray =
new AllocaInst(NewArrayType,
DL.getAllocaAddrSpace(),
1315 SAI->getName(), InstIt);
1318 SAI->setBasePtr(CreatedArray);
1324 auto &InvariantEquivClasses =
S.getInvariantAccesses();
1325 if (InvariantEquivClasses.empty())
1328 BasicBlock *PreLoadBB = SplitBlock(
Builder.GetInsertBlock(),
1330 PreLoadBB->setName(
"polly.preload.begin");
1331 Builder.SetInsertPoint(&PreLoadBB->front());
1333 for (
auto &IAClass : InvariantEquivClasses)
1350 Loop *L =
LI.getLoopFor(
S.getEntry());
1352 while (L !=
nullptr &&
S.contains(L))
1353 L = L->getParentLoop();
1355 while (L !=
nullptr) {
1357 L = L->getParentLoop();
1376 "Insert location points after last valid instruction");
1377 Instruction *InsertLocation = &*
Builder.GetInsertPoint();
1402 if (!RTC->getType()->isIntegerTy(1))
1403 RTC =
Builder.CreateIsNotNull(RTC);
1404 Value *OverflowHappened =
1408 auto *F =
Builder.GetInsertBlock()->getParent();
1411 "F: " + F->getName().str() +
" R: " +
S.getRegion().getNameStr() +
1413 RTC,
" Overflow: ", OverflowHappened,
1415 " (0 failed, -1 succeeded)\n"
1416 " (if one or both are 0 falling back to original code, if both are -1 "
1417 "executing Polly code)\n");
1420 RTC =
Builder.CreateAnd(RTC, OverflowHappened,
"polly.rtc.result");
1423 if (!isa<ConstantInt>(RTC))
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.
static void removeSubFuncFromDomTree(Function *F, DominatorTree &DT)
Remove the BBs contained in a (sub)function from the dominator tree.
llvm::cl::OptionCategory PollyCategory
static RegisterPass< ScopOnlyPrinterWrapperPass > N("dot-scops-only", "Polly - Print Scops of function (with no function bodies)")
__isl_give isl_pw_multi_aff * isl_pw_multi_aff_from_set(__isl_take isl_set *set)
__isl_export __isl_give isl_ast_expr * isl_ast_node_for_get_init(__isl_keep isl_ast_node *node)
__isl_export __isl_give isl_ast_node_list * isl_ast_node_block_get_children(__isl_keep isl_ast_node *node)
__isl_null isl_ast_expr * isl_ast_expr_free(__isl_take isl_ast_expr *expr)
__isl_give isl_ast_expr * isl_ast_expr_address_of(__isl_take isl_ast_expr *expr)
isl_size isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr)
enum isl_ast_expr_op_type isl_ast_expr_get_op_type(__isl_keep isl_ast_expr *expr)
__isl_give isl_ast_expr * isl_ast_expr_get_op_arg(__isl_keep isl_ast_expr *expr, int pos)
__isl_export __isl_give isl_ast_node * isl_ast_node_mark_get_node(__isl_keep isl_ast_node *node)
__isl_export __isl_give isl_ast_expr * isl_ast_node_for_get_inc(__isl_keep isl_ast_node *node)
__isl_give isl_ast_node * isl_ast_node_if_get_else(__isl_keep isl_ast_node *node)
__isl_export __isl_give isl_ast_node * isl_ast_node_for_get_body(__isl_keep isl_ast_node *node)
__isl_give isl_id * isl_ast_expr_get_id(__isl_keep isl_ast_expr *expr)
__isl_export __isl_give isl_ast_expr * isl_ast_node_user_get_expr(__isl_keep isl_ast_node *node)
__isl_export __isl_give isl_ast_expr * isl_ast_node_if_get_cond(__isl_keep isl_ast_node *node)
__isl_export __isl_give isl_id * isl_ast_node_mark_get_id(__isl_keep isl_ast_node *node)
__isl_export __isl_give isl_ast_expr * isl_ast_node_for_get_iterator(__isl_keep isl_ast_node *node)
__isl_null isl_ast_node * isl_ast_node_free(__isl_take isl_ast_node *node)
__isl_give isl_ast_node * isl_ast_node_if_get_then(__isl_keep isl_ast_node *node)
isl_bool isl_ast_node_if_has_else(__isl_keep isl_ast_node *node)
__isl_give isl_ast_expr * isl_ast_expr_copy(__isl_keep isl_ast_expr *expr)
__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::union_map get_schedule() const
isl::ast_expr access_from(isl::multi_pw_aff mpa) const
isl::ast_expr get_op_arg(int pos) const
__isl_give isl_ast_expr * release()
__isl_keep isl_ast_expr * get() 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()
__isl_keep isl_id * get() const
__isl_give isl_map * release()
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
__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
SmallVector< Instruction *, 4 > EscapeUserVectorTy
Simple vector of instructions to store escape users.
void copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses)
Copy the basic block.
static bool isParallel(const isl::ast_node &Node)
Is this loop a parallel loop?
static bool isExecutedInParallel(const isl::ast_node &Node)
Will the loop be run as thread parallel?
static isl::union_map getSchedule(const isl::ast_node &Node)
Get the nodes schedule or a nullptr if not available.
static isl::ast_build getBuild(const isl::ast_node &Node)
Get the nodes build context or a nullptr if not available.
static bool isReductionParallel(const isl::ast_node &Node)
Is this loop a reduction parallel loop?
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.
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
void updateValues(ValueMapT &NewValues)
Change the llvm::Value(s) used for code generation.
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.
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)
void createSubstitutionsVector(__isl_take isl_ast_expr *Expr, ScopStmt *Stmt, std::vector< LoopToScevMapT > &VLTS, std::vector< Value * > &IVS, __isl_take isl_id *IteratorID)
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.
void getReferencesInSubtree(const isl::ast_node &For, SetVector< Value * > &Values, SetVector< const Loop * > &Loops)
Compute the values and loops referenced in this subtree.
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 <S)
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)
Represent memory accesses in statements.
Instruction * getAccessInstruction() const
Return the access instruction of this memory access.
bool isRead() const
Is this a read memory access?
isl::map getAddressFunction() const
Get an isl map describing the memory address accessed.
const ScopArrayInfo * getScopArrayInfo() const
Legacy name of getOriginalScopArrayInfo().
Value * getOriginalBaseAddr() const
Get the original base address of this access (e.g.
bool isArrayKind() const
Old name of isOriginalArrayKind.
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 <S, __isl_keep isl_id_to_ast_expr *IdToAstExp)
Copy the region statement Stmt.
void resetAlternativeAliasBases()
Delete the set of alternative alias bases.
BandAttr *& getStagingAttrEnv()
void addAlternativeAliasBases(llvm::DenseMap< llvm::AssertingVH< llvm::Value >, llvm::AssertingVH< llvm::Value > > &NewMap)
Add alternative alias based pointers.
void popLoop(bool isParallel)
Remove the last added loop.
const std::vector< Instruction * > & getInstructions() const
bool isBlockStmt() const
Return true if this statement represents a single basic block.
Region * getRegion() const
Get the region represented by this ScopStmt (if any).
BasicBlock * getBasicBlock() const
Get the BasicBlock represented by this ScopStmt (if any).
bool isCopyStmt() const
Return true if this is a copy statement.
bool isRegionStmt() const
Return true if this statement represents a whole region.
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.
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.
bool contains(const Loop *L) const
Check if L is contained in the SCoP.
const Region & getRegion() const
Get the maximum region of this static control part.
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.
__isl_export __isl_keep const char * isl_id_get_name(__isl_keep isl_id *id)
__isl_null isl_id * isl_id_free(__isl_take isl_id *id)
void * isl_id_get_user(__isl_keep isl_id *id)
enum isl_ast_expr_type isl_ast_expr_get_type(__isl_keep isl_ast_expr *expr)
enum isl_ast_node_type isl_ast_node_get_type(__isl_keep isl_ast_node *node)
__isl_export __isl_give isl_set * isl_map_domain(__isl_take isl_map *bmap)
__isl_export __isl_give isl_set * isl_map_range(__isl_take isl_map *map)
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).
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, const llvm::DataLayout &DL, const char *Name, const llvm::SCEV *E, llvm::Type *Ty, llvm::Instruction *IP, ValueMapT *VMap, 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.
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.
std::forward_list< MemoryAccess * > MemoryAccessList
Ordered list type to hold accesses.
__isl_export __isl_give isl_set * isl_set_universe(__isl_take isl_space *space)
__isl_export __isl_give isl_space * isl_set_get_space(__isl_keep isl_set *set)
__isl_export isl_bool isl_set_is_equal(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
__isl_export __isl_give isl_set * isl_set_intersect_params(__isl_take isl_set *set, __isl_take isl_set *params)
__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)
__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)
isl_size isl_set_dim(__isl_keep isl_set *set, enum isl_dim_type type)
__isl_give isl_id * isl_set_get_dim_id(__isl_keep isl_set *set, enum isl_dim_type type, unsigned pos)
__isl_export isl_bool isl_set_is_empty(__isl_keep isl_set *set)
Represent the attributes of a loop.
Type for equivalent invariant accesses and their domain context.
MemoryAccessList InvariantAccesses
Memory accesses now treated invariant.
Type * AccessType
The type of the invariant access.
isl::set ExecutionContext
The execution context under which the memory location is accessed.
const SCEV * IdentifyingPointer
The pointer that identifies this equivalence class.
static void createCPUPrinter(PollyIRBuilder &Builder, Args... args)
Print a set of LLVM-IR Values or StringRefs via printf.
static TupleKindPtr Domain("Domain")
__isl_give isl_set * isl_set_from_union_set(__isl_take isl_union_set *uset)