Index: include/polly/CodeGen/CodeGeneration.h =================================================================== --- include/polly/CodeGen/CodeGeneration.h +++ include/polly/CodeGen/CodeGeneration.h @@ -36,6 +36,9 @@ }; extern CodeGenChoice PollyCodeGenChoice; +/// @brief Flag to turn on/off annotation of alias scopes. +extern bool PollyAnnotateAliasScopes; + static inline int getNumberOfIterations(__isl_take isl_set *Domain) { int Dim = isl_set_dim(Domain, isl_dim_set); Index: include/polly/CodeGen/IRBuilder.h =================================================================== --- include/polly/CodeGen/IRBuilder.h +++ include/polly/CodeGen/IRBuilder.h @@ -18,14 +18,30 @@ #include "llvm/IR/IRBuilder.h" #include "llvm/Analysis/LoopInfo.h" +namespace llvm { +class ScalarEvolution; +} + namespace polly { +class Scop; -/// @brief Helper class to annotate newly generated loops with metadata. +/// @brief Helper class to annotate newly generated loop nests with metadata. /// -/// This stack-like structure will keep track of all loops, and annotate -/// memory instructions and loop headers according to all parallel loops. +/// The annotations are twofold: +/// 1) Loops are stored in a stack-like structure will keep track of all +/// of them. Contained memory instructions and loop headers are annotated +/// according to all parallel surrounding loops. +/// 2) The new SCoP is assumed alias free (either due to the result of +/// AliasAnalysis queries or runtime alias checks). We annotate therefore +/// all memory instruction with alias scopes to indicate that fact to +/// later optimizations. class LoopAnnotator { public: + LoopAnnotator(); + + /// @brief Build all alias scopes for the given SCoP. + void buildAliasScopes(Scop &S); + /// @brief Add a new loop @p L which is parallel if @p IsParallel is true. void pushLoop(llvm::Loop *L, bool IsParallel); @@ -40,11 +56,23 @@ bool IsParallel) const; private: + /// @brief The ScalarEvolution analysis we use to find base pointers. + llvm::ScalarEvolution *SE; + /// @brief All loops currently under construction. llvm::SmallVector ActiveLoops; /// @brief Metadata pointing to parallel loops currently under construction. llvm::SmallVector ParallelLoops; + + /// @brief The alias scope domain for the current SCoP. + llvm::MDNode *AliasScopeDomain; + + /// @brief A map from base pointers to its alias scope. + llvm::DenseMap AliasScopeMap; + + /// @brief A map from base pointers to an alias scope list of other pointers. + llvm::DenseMap OtherAliasScopeListMap; }; /// @brief Add Polly specifics when running IRBuilder. Index: lib/CodeGen/IRBuilder.cpp =================================================================== --- lib/CodeGen/IRBuilder.cpp +++ lib/CodeGen/IRBuilder.cpp @@ -14,35 +14,86 @@ #include "polly/CodeGen/IRBuilder.h" +#include "polly/ScopInfo.h" +#include "polly/Support/ScopHelper.h" + #include "llvm/IR/Metadata.h" #include "llvm/Support/Debug.h" using namespace llvm; using namespace polly; -/// @brief Get the loop id metadata node. +/// @brief Get a self referencing id metadata node. /// -/// Each loop is identified by a self referencing metadata node of the form: +/// The MDNode looks like this: /// /// '!n = metadata !{metadata !n}' /// -/// This functions creates such metadata on demand if not yet available. -/// -/// @return The loop id metadata node. -static MDNode *getLoopID(Loop *L) { - Value *Args[] = {0}; - MDNode *LoopID = MDNode::get(L->getHeader()->getContext(), Args); - LoopID->replaceOperandWith(0, LoopID); - return LoopID; +/// @return The self referencing id metadata node. +static MDNode *getID(LLVMContext &Ctx, Value *arg0 = nullptr, + Value *arg1 = nullptr) { + MDNode *ID; + if (arg0) { + if (arg1) { + Value *Args[] = {0, arg0, arg1}; + ID = MDNode::get(Ctx, Args); + } else { + Value *Args[] = {0, arg0}; + ID = MDNode::get(Ctx, Args); + } + } else { + Value *Args[] = {0}; + ID = MDNode::get(Ctx, Args); + } + ID->replaceOperandWith(0, ID); + return ID; +} + +LoopAnnotator::LoopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {} + +void LoopAnnotator::buildAliasScopes(Scop &S) { + SE = S.getSE(); + + LLVMContext &Ctx = SE->getContext(); + AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain")); + + AliasScopeMap.clear(); + OtherAliasScopeListMap.clear(); + + SmallPtrSet BasePtrs; + for (ScopStmt *Stmt : S) + for (MemoryAccess *MA : *Stmt) + BasePtrs.insert(MA->getBaseAddr()); + + std::string AliasScopeStr = "polly.alias.scope."; + for (Value *BasePtr : BasePtrs) + AliasScopeMap[BasePtr] = getID( + Ctx, AliasScopeDomain, + MDString::get(Ctx, (AliasScopeStr + BasePtr->getName()).str().c_str())); + + for (Value *BasePtr : BasePtrs) { + MDNode *AliasScopeList = MDNode::get(Ctx, {}); + for (const auto &AliasScopePair : AliasScopeMap) { + if (BasePtr == AliasScopePair.first) + continue; + + Value *Args = {AliasScopePair.second}; + AliasScopeList = + MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args)); + } + + OtherAliasScopeListMap[BasePtr] = AliasScopeList; + } } void polly::LoopAnnotator::pushLoop(Loop *L, bool IsParallel) { + ActiveLoops.push_back(L); if (!IsParallel) return; BasicBlock *Header = L->getHeader(); - MDNode *Id = getLoopID(L); + MDNode *Id = getID(Header->getContext()); Value *Args[] = {Id}; MDNode *Ids = ParallelLoops.empty() ? MDNode::get(Header->getContext(), Args) @@ -71,7 +122,25 @@ } void polly::LoopAnnotator::annotate(Instruction *Inst) { - if (!Inst->mayReadOrWriteMemory() || ParallelLoops.empty()) + if (!Inst->mayReadOrWriteMemory()) + return; + + if (AliasScopeDomain) { + Value *BasePtr = nullptr; + if (isa(Inst) || isa(Inst)) { + const SCEV *PtrSCEV = SE->getSCEV(getPointerOperand(*Inst)); + const SCEV *BaseSCEV = SE->getPointerBase(PtrSCEV); + if (const SCEVUnknown *SU = dyn_cast(BaseSCEV)) + BasePtr = SU->getValue(); + } + + if (BasePtr) { + Inst->setMetadata("alias.scope", AliasScopeMap[BasePtr]); + Inst->setMetadata("noalias", OtherAliasScopeListMap[BasePtr]); + } + } + + if (ParallelLoops.empty()) return; Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back()); Index: lib/CodeGen/IslCodeGeneration.cpp =================================================================== --- lib/CodeGen/IslCodeGeneration.cpp +++ lib/CodeGen/IslCodeGeneration.cpp @@ -605,6 +605,10 @@ assert(!S.getRegion().isTopLevelRegion() && "Top level regions are not supported"); + // Build the alias scopes for annotations first. + if (PollyAnnotateAliasScopes) + Annotator.buildAliasScopes(S); + BasicBlock *EnteringBB = simplifyRegion(&S, this); PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator); Index: lib/Support/RegisterPasses.cpp =================================================================== --- lib/Support/RegisterPasses.cpp +++ lib/Support/RegisterPasses.cpp @@ -141,6 +141,13 @@ cl::desc("Show the Polly CFG right after code generation"), cl::Hidden, cl::init(false), cl::cat(PollyCategory)); +bool polly::PollyAnnotateAliasScopes; +static cl::opt XPollyAnnotateAliasScopes( + "polly-annotate-alias-scopes", + cl::desc("Annotate memory instructions with alias scopes"), + cl::location(PollyAnnotateAliasScopes), cl::init(false), cl::ZeroOrMore, + cl::cat(PollyCategory)); + namespace polly { void initializePollyPasses(PassRegistry &Registry) { #ifdef CLOOG_FOUND Index: test/Isl/CodeGen/annotated_alias_scopes.ll =================================================================== --- /dev/null +++ test/Isl/CodeGen/annotated_alias_scopes.ll @@ -0,0 +1,62 @@ +; RUN: opt %loadPolly -polly-code-generator=isl -polly-codegen-isl -polly-annotate-alias-scopes -S < %s | FileCheck %s +; +; Check that we create alias scopes that indicate the accesses to A, B and C cannot alias in any way. +; +; CHECK: %[[BIdx:[._a-zA-Z0-9]*]] = getelementptr inbounds i32* %B, i64 %polly.indvar +; CHECK: load i32* %[[BIdx]], !alias.scope ![[AliasScopeB:[0-9]*]], !noalias ![[NoAliasB:[0-9]*]] +; CHECK: %[[CIdx:[._a-zA-Z0-9]*]] = getelementptr inbounds float* %C, i64 %polly.indvar +; CHECK: load float* %[[CIdx]], !alias.scope ![[AliasScopeC:[0-9]*]], !noalias ![[NoAliasC:[0-9]*]] +; CHECK: %[[AIdx:[._a-zA-Z0-9]*]] = getelementptr inbounds i32* %A, i64 %polly.indvar +; CHECK: store i32 %{{[._a-zA-Z0-9]*}}, i32* %[[AIdx]], !alias.scope ![[AliasScopeA:[0-9]*]], !noalias ![[NoAliasA:[0-9]*]] +; +; CHECK-DAG: ![[AliasScopeB]] = metadata !{metadata ![[AliasScopeB]], metadata !{{[0-9]*}}, metadata !"polly.alias.scope.B"} +; CHECK: ![[NoAliasB]] = metadata !{ +; CHECK-DAG: metadata ![[AliasScopeA]] +; CHECK-DAG: metadata ![[AliasScopeC]] +; CHECK: } +; CHECK-DAG: ![[AliasScopeA]] = metadata !{metadata ![[AliasScopeA]], metadata !{{[0-9]*}}, metadata !"polly.alias.scope.A"} +; CHECK-DAG: ![[AliasScopeC]] = metadata !{metadata ![[AliasScopeC]], metadata !{{[0-9]*}}, metadata !"polly.alias.scope.C"} +; CHECK: ![[NoAliasC]] = metadata !{ +; CHECK-DAG: metadata ![[AliasScopeA]] +; CHECK-DAG: metadata ![[AliasScopeB]] +; CHECK: } +; CHECK: ![[NoAliasA]] = metadata !{ +; CHECK-DAG: metadata ![[AliasScopeB]] +; CHECK-DAG: metadata ![[AliasScopeC]] +; CHECK: } +; +; void jd(int *A, int *B, float *C) { +; for (int i = 0; i < 1024; i++) +; A[i] = B[i] + C[i]; +; } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @jd(i32* %A, i32* %B, float* %C) { +entry: + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %arrayidx = getelementptr inbounds i32* %B, i64 %indvars.iv + %tmp = load i32* %arrayidx, align 4 + %conv = sitofp i32 %tmp to float + %arrayidx2 = getelementptr inbounds float* %C, i64 %indvars.iv + %tmp1 = load float* %arrayidx2, align 4 + %add = fadd fast float %conv, %tmp1 + %conv3 = fptosi float %add to i32 + %arrayidx5 = getelementptr inbounds i32* %A, i64 %indvars.iv + store i32 %conv3, i32* %arrayidx5, align 4 + br label %for.inc + +for.inc: ; preds = %for.body + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret void +}