[Polly] Allow to annotate alias scopes in the new SCoP.

[jdoerfert]

Summary

The command line flag -polly-annotate-alias-scopes controls
whether or not Polly annotates alias scopes in the new SCoP.
This can improve later optimizations as the new SCoP is basically
an alias free environment for them.

[grosser]

Nice!

Some minor comments inlined.

include/polly/CodeGen/CodeGeneration.h

41

I don't think we need a command line option for this. That seems pure goodness, so why don't we enable it by default?

include/polly/CodeGen/IRBuilder.h

32

The first sentence talks more about the way the LoopAnnotator works and also seems somehow incomplete.

lib/CodeGen/IRBuilder.cpp

34

What are arg0 and arg0? Are you saying this metadata node can (optionally) reference two other metadata nodes? Maybe add this to the example in the documentation.

47

What about writing this like:

std::vector<Value *> Args = {0}

if (arg0)
  Args.push_back(arg0);

if (arg1)
  Args.push_back(arg1);

ID = MDNode::get(Ctx, Args);

63

Please use a data structure which guarantees the order in which we iterate over (SetVector?)

135

Would it be better to use the new to (later) use the newly introduced ScopArrayInfo class to get the base pointer?

lib/CodeGen/IslCodeGeneration.cpp

610

I would enable this by default.

[jdoerfert]

Dup of http://reviews.llvm.org/D5575

include/polly/CodeGen/CodeGeneration.h

41

This is for example useful for ppl using Polly as an analyzer/annotator with the ignore-aliasing option and without scheduling. In such a case you might don't want the alias scopes.

[jdoerfert]

Could you take a quick look at http://reviews.llvm.org/D5575
I changed it according to your comments and added a second refactoring
patch to rename the LoopAnnotator to ScopAnnotator.

• msg-8727-369.dat219 BDownload

include/polly/CodeGen/CodeGeneration.h

 #ifdef CLOOG_FOUND
   CODEGEN_CLOOG,
 #endif
   CODEGEN_ISL,
   CODEGEN_NONE
 };
 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);
 
   // Calculate a map similar to the identity map, but with the last input
   // and output dimension not related.
   //  [i0, i1, i2, i3] -> [i0, i1, i2, o0]
   isl_space *Space = isl_set_get_space(Domain);
   Space = isl_space_drop_dims(Space, isl_dim_out, Dim - 1, 1);

include/polly/CodeGen/IRBuilder.h

 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_CODEGEN_IRBUILDER_H
 #define POLLY_CODEGEN_IRBUILDER_H
 
 #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);
 
   /// @brief Remove the last added loop.
   void popLoop(bool isParallel);
 
   /// @brief Annotate the new instruction @p I for all parallel loops.
   void annotate(llvm::Instruction *I);
 
   /// @brief Annotate the loop latch @p B wrt. @p L.
   void annotateLoopLatch(llvm::BranchInst *B, llvm::Loop *L,
                          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<llvm::Loop *, 8> ActiveLoops;
 
   /// @brief Metadata pointing to parallel loops currently under construction.
   llvm::SmallVector<llvm::MDNode *, 8> 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<llvm::Value *, llvm::MDNode *> AliasScopeMap;
+
+  /// @brief A map from base pointers to an alias scope list of other pointers.
+  llvm::DenseMap<llvm::Value *, llvm::MDNode *> OtherAliasScopeListMap;
 };
 
 /// @brief Add Polly specifics when running IRBuilder.
 ///
 /// This is used to add additional items such as e.g. the llvm.loop.parallel
 /// metadata.
 template <bool PreserveNames>
 class PollyBuilderInserter

lib/CodeGen/IRBuilder.cpp

 //===------ PollyIRBuilder.cpp --------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // The Polly IRBuilder file contains Polly specific extensions for the IRBuilder
 // that are used e.g. to emit the llvm.loop.parallel metadata.
 //
 //===----------------------------------------------------------------------===//
 
 #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) {
+/// @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};
-  MDNode *LoopID = MDNode::get(L->getHeader()->getContext(), Args);
-  LoopID->replaceOperandWith(0, LoopID);
-  return LoopID;
+    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<Value *, 8> 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)
                     : MDNode::concatenate(ParallelLoops.back(), Id);
   ParallelLoops.push_back(Ids);
 }
 
 void polly::LoopAnnotator::popLoop(bool IsParallel) {
void polly::LoopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L,
 
   assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
   MDNode *Ids = ParallelLoops.back();
   MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
   B->setMetadata("llvm.loop", Id);
 }
 
 void polly::LoopAnnotator::annotate(Instruction *Inst) {
-  if (!Inst->mayReadOrWriteMemory() || ParallelLoops.empty())
+  if (!Inst->mayReadOrWriteMemory())
+    return;
+
+  if (AliasScopeDomain) {
+    Value *BasePtr = nullptr;
+    if (isa<StoreInst>(Inst) || isa<LoadInst>(Inst)) {
+      const SCEV *PtrSCEV = SE->getSCEV(getPointerOperand(*Inst));
+      const SCEV *BaseSCEV = SE->getPointerBase(PtrSCEV);
+      if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(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());
 }

lib/CodeGen/IslCodeGeneration.cpp

bool runOnScop(Scop &S) {
     LI = &getAnalysis<LoopInfo>();
     AI = &getAnalysis<IslAstInfo>();
     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     SE = &getAnalysis<ScalarEvolution>();
 
     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);
 
     IslNodeBuilder NodeBuilder(Builder, Annotator, this, *LI, *SE, *DT);
     NodeBuilder.addMemoryAccesses(S);
     NodeBuilder.addParameters(S.getContext());
 
     Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());

lib/Support/RegisterPasses.cpp

static cl::opt<bool> PollyOnlyPrinter(
     cl::value_desc("Run the Polly DOT printer at -O3 (no BB content"),
     cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<bool>
     CFGPrinter("polly-view-cfg",
                cl::desc("Show the Polly CFG right after code generation"),
                cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
+bool polly::PollyAnnotateAliasScopes;
+static cl::opt<bool, true> 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
   initializeCloogInfoPass(Registry);
   initializeCodeGenerationPass(Registry);
 #endif
   initializeIslCodeGenerationPass(Registry);
   initializeCodePreparationPass(Registry);

test/Isl/CodeGen/annotated_alias_scopes.ll

+; 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
+}