[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.

[Refactor] Rename LoopAnnotator to ScopAnnotator

The LoopAnnotator doesn't annotate only loops any more, thus it is
called ScopAnnotator from now on.

This also removes unnecessary polly:: namespace tags.

[jdoerfert]

r218877 and r218878.

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 SCoPs with metadata.
 ///
-/// This stack-like structure will keep track of all loops, and annotate
-/// memory instructions and loop headers according to all parallel loops.
-class LoopAnnotator {
+/// The annotations are twofold:
+///   1) Loops are stored in a stack-like structure in the order they are
+///      constructed and the LoopID metadata node is added to the backedge.
+///      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.
+///      These alias scopes live in a new alias domain only used in this SCoP.
+///      Each base pointer has its own alias scope and is annotated to not
+///      alias with any access to different base pointers.
+class ScopAnnotator {
 public:
+  ScopAnnotator();
+
+  /// @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
     : protected llvm::IRBuilderDefaultInserter<PreserveNames> {
 public:
   PollyBuilderInserter() : Annotator(0) {}
-  PollyBuilderInserter(class LoopAnnotator &A) : Annotator(&A) {}
+  PollyBuilderInserter(class ScopAnnotator &A) : Annotator(&A) {}
 
 protected:
   void InsertHelper(llvm::Instruction *I, const llvm::Twine &Name,
                     llvm::BasicBlock *BB,
                     llvm::BasicBlock::iterator InsertPt) const {
     llvm::IRBuilderDefaultInserter<PreserveNames>::InsertHelper(I, Name, BB,
                                                                 InsertPt);
     if (Annotator)
       Annotator->annotate(I);
   }
 
 private:
-  class LoopAnnotator *Annotator;
+  class ScopAnnotator *Annotator;
 };
 
 // TODO: We should not name instructions in NDEBUG builds.
 //
 // We currently always name instructions, as the polly test suite currently
 // matches for certain names.
 typedef PollyBuilderInserter<true> IRInserter;
 typedef llvm::IRBuilder<true, llvm::ConstantFolder, IRInserter> PollyIRBuilder;
 
 /// @brief Return an IR builder pointed before the @p BB terminator.
 static inline PollyIRBuilder createPollyIRBuilder(llvm::BasicBlock *BB,
-                                                  LoopAnnotator &LA) {
+                                                  ScopAnnotator &LA) {
   PollyIRBuilder Builder(BB->getContext(), llvm::ConstantFolder(),
                          polly::IRInserter(LA));
   Builder.SetInsertPoint(BB->getTerminator());
   return Builder;
 }
 }
 #endif

include/polly/CodeGen/LoopGenerators.h

 ///
 /// @param Builder    The builder used to create the loop.
 /// @param P          A pointer to the pass that uses this function. It is used
 ///                   to update analysis information.
 /// @param LI         The loop info for the current function
 /// @param DT         The dominator tree we need to update
 /// @param ExitBlock  The block the loop will exit to.
 /// @param Predicate  The predicate used to generate the upper loop bound.
-/// @param Annotator  This function can (optionally) take a LoopAnnotator which
-///                   tracks the loop structure.
+/// @param Annotator  This function can (optionally) take a ScopAnnotator which
+///                   annotates loops and alias information in the SCoP.
 /// @param Parallel   If this loop should be marked parallel in the Annotator.
 /// @param UseGuard   Create a guard in front of the header to check if the
 ///                   loop is executed at least once, otherwise just assume it.
 ///
 /// @return Value*    The newly created induction variable for this loop.
 Value *createLoop(Value *LowerBound, Value *UpperBound, Value *Stride,
                   PollyIRBuilder &Builder, Pass *P, LoopInfo &LI,
                   DominatorTree &DT, BasicBlock *&ExitBlock,
                   ICmpInst::Predicate Predicate,
-                  LoopAnnotator *Annotator = NULL, bool Parallel = false,
+                  ScopAnnotator *Annotator = NULL, bool Parallel = false,
                   bool UseGuard = true);
 
 class OMPGenerator {
 public:
   typedef std::map<Value *, Value *> ValueToValueMapTy;
 
   OMPGenerator(PollyIRBuilder &Builder, Pass *P) : Builder(Builder), P(P) {}
 

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.
-///
-/// Each loop is identified by a self referencing metadata node of the form:
+/// @brief Get a self referencing id metadata node.
 ///
-///    '!n = metadata !{metadata !n}'
+/// The MDNode looks like this (if arg0/arg1 are not null):
 ///
-/// This functions creates such metadata on demand if not yet available.
+///    '!n = metadata !{metadata !n, arg0, arg1}'
 ///
-/// @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;
+  SmallVector<Value *, 3> Args;
+  Args.push_back(nullptr);
+
+  if (arg0)
+    Args.push_back(arg0);
+  if (arg1)
+    Args.push_back(arg1);
+
+  ID = MDNode::get(Ctx, Args);
+  ID->replaceOperandWith(0, ID);
+  return ID;
+}
+
+ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {}
+
+void ScopAnnotator::buildAliasScopes(Scop &S) {
+  SE = S.getSE();
+
+  LLVMContext &Ctx = SE->getContext();
+  AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
+
+  AliasScopeMap.clear();
+  OtherAliasScopeListMap.clear();
+
+  SetVector<Value *> 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 ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
 
-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 ScopAnnotator::popLoop(bool IsParallel) {
   ActiveLoops.pop_back();
   if (!IsParallel)
     return;
 
   assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
   ParallelLoops.pop_back();
 }
 
-void polly::LoopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L,
-                                             bool IsParallel) const {
+void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L,
   if (!IsParallel)
     return;
 
   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())
+void ScopAnnotator::annotate(Instruction *Inst) {
+  if (!Inst->mayReadOrWriteMemory())
+    return;
+
+  // TODO: Use the ScopArrayInfo once available here.
+  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

 
 using namespace polly;
 using namespace llvm;
 
 #define DEBUG_TYPE "polly-codegen-isl"
 
 class IslNodeBuilder {
 public:
-  IslNodeBuilder(PollyIRBuilder &Builder, LoopAnnotator &Annotator, Pass *P,
+  IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P,
                  LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT)
       : Builder(Builder), Annotator(Annotator), ExprBuilder(Builder, IDToValue),
         P(P), LI(LI), SE(SE), DT(DT) {}
 
   /// @brief Add the mappings from array id's to array llvm::Value's.
   void addMemoryAccesses(Scop &S);
   void addParameters(__isl_take isl_set *Context);
   void create(__isl_take isl_ast_node *Node);
   IslExprBuilder &getExprBuilder() { return ExprBuilder; }
 
 private:
   PollyIRBuilder &Builder;
-  LoopAnnotator &Annotator;
+  ScopAnnotator &Annotator;
   IslExprBuilder ExprBuilder;
   Pass *P;
   LoopInfo &LI;
   ScalarEvolution &SE;
   DominatorTree &DT;
 
   // This maps an isl_id* to the Value* it has in the generated program. For now
   // on, the only isl_ids that are stored here are the newly calculated loop
public:
   ///{
   LoopInfo *LI;
   IslAstInfo *AI;
   DominatorTree *DT;
   ScalarEvolution *SE;
   ///}
 
   /// @brief The loop annotator to generate llvm.loop metadata.
-  LoopAnnotator Annotator;
+  ScopAnnotator Annotator;
 
   /// @brief Build the runtime condition.
   ///
   /// Build the condition that evaluates at run-time to true iff all
   /// assumptions taken for the SCoP hold, and to false otherwise.
   ///
   /// @return A value evaluating to true/false if execution is save/unsafe.
   Value *buildRTC(PollyIRBuilder &Builder, IslExprBuilder &ExprBuilder) {
     Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator());
     Value *RTC = ExprBuilder.create(AI->getRunCondition());
     if (!RTC->getType()->isIntegerTy(1))
       RTC = Builder.CreateIsNotNull(RTC);
     return RTC;
   }
 
   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/CodeGen/LoopGenerators.cpp

 // case we branch to PreHeaderBB and subsequently to the HeaderBB, which
 // contains the loop iv 'polly.indvar', the incremented loop iv
 // 'polly.indvar_next' as well as the condition to check if we execute another
 // iteration of the loop. After the loop has finished, we branch to ExitBB.
 Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
                          PollyIRBuilder &Builder, Pass *P, LoopInfo &LI,
                          DominatorTree &DT, BasicBlock *&ExitBB,
                          ICmpInst::Predicate Predicate,
-                         LoopAnnotator *Annotator, bool Parallel,
+                         ScopAnnotator *Annotator, bool Parallel,
                          bool UseGuard) {
   Function *F = Builder.GetInsertBlock()->getParent();
   LLVMContext &Context = F->getContext();
 
   assert(LB->getType() == UB->getType() && "Types of loop bounds do not match");
   IntegerType *LoopIVType = dyn_cast<IntegerType>(UB->getType());
   assert(LoopIVType && "UB is not integer?");
 

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(true), 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/LoopParallelMD/loop_nest_param_parallel.ll

 ; RUN: opt %loadPolly -polly-codegen-isl -polly-ast-detect-parallel -S < %s | FileCheck %s
 ;
 ; Check that we mark multiple parallel loops correctly including the memory instructions.
 ;
 ; CHECK-DAG:  %polly.loop_cond[[COuter:[0-9]*]] = icmp sle i64 %polly.indvar{{[0-9]*}}, 1022
-; CHECK-DAG:  br i1 %polly.loop_cond[[COuter]], label %polly.loop_header{{[0-9]*}}, label %polly.loop_exit{{[0-9]*}}, !llvm.loop !0
+; CHECK-DAG:  br i1 %polly.loop_cond[[COuter]], label %polly.loop_header{{[0-9]*}}, label %polly.loop_exit{{[0-9]*}}, !llvm.loop ![[IDOuter:[0-9]*]]
 ;
 ; CHECK-DAG:  %polly.loop_cond[[CInner:[0-9]*]] = icmp sle i64 %polly.indvar{{[0-9]*}}, 510
-; CHECK-DAG:  br i1 %polly.loop_cond[[CInner]], label %polly.loop_header{{[0-9]*}}, label %polly.loop_exit{{[0-9]*}}, !llvm.loop !2
+; CHECK-DAG:  br i1 %polly.loop_cond[[CInner]], label %polly.loop_header{{[0-9]*}}, label %polly.loop_exit{{[0-9]*}}, !llvm.loop ![[IDInner:[0-9]*]]
 ;
-; CHECK-DAG: store i32 %p_tmp{{[0-9]*}}, i32* %p_arrayidx{{[0-9]*}}, !llvm.mem.parallel_loop_access !1
+; CHECK-DAG: store i32 %p_tmp{{[0-9]*}}, i32* %p_arrayidx{{[0-9]*}}, {{[ ._!,a-zA-Z0-9]*}}, !llvm.mem.parallel_loop_access !4
 ;
-; CHECK: !0 = metadata !{metadata !0}
-; CHECK: !1 = metadata !{metadata !0, metadata !2}
-; CHECK: !2 = metadata !{metadata !2}
+; CHECK-DAG: ![[IDOuter]] = metadata !{metadata ![[IDOuter]]}
+; CHECK-DAG: ![[IDInner]] = metadata !{metadata ![[IDInner]]}
+; CHECK-DAG: !4 = metadata !{metadata ![[IDOuter]], metadata ![[IDInner]]}
 ;
 ;    void jd(int *A) {
 ;      for (int i = 0; i < 1024; i++)
 ;        for (int j = 0; j < 512; j++)
 ;          A[i * 512 + j] = i + j;
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

test/Isl/CodeGen/LoopParallelMD/single_loop_param_parallel.ll

 
 ret:
   fence seq_cst
   ret void
 }
 
 ; SEQUENTIAL: @test-one
 ; SEQUENTIAL-NOT: !llvm.mem.parallel_loop_access
-; SEQUENTIAL-NOT: !llvm.loop !0
+; SEQUENTIAL-NOT: !llvm.loop
 ; SEQUENTIAL-SCEV: @test-one
 ; SEQUENTIAL-SCEV-NOT: !llvm.mem.parallel_loop_access
 ; SEQUENTIAL-SCEV-NOT: !llvm.loop
 
 ; PARALLEL: @test-one
-; PARALLEL: store i32 1, i32* %p_scevgep, !llvm.mem.parallel_loop_access !0
-; PARALLEL:  br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit, !llvm.loop !0
+; PARALLEL: store i32 1, i32* %p_scevgep, {{[ ._!,a-zA-Z0-9]*}}, !llvm.mem.parallel_loop_access ![[LoopID:[0-9]*]]
+; PARALLEL:  br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit, !llvm.loop ![[LoopID]]
 ; PARALLEL-SCEV: @test-one
-; PARALLEL-SCEV: store i32 1, i32* %scevgep1, !llvm.mem.parallel_loop_access !0
-; PARALLEL-SCEV:  br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit, !llvm.loop !0
+; PARALLEL-SCEV: store i32 1, i32* %scevgep1, {{[ ._!,a-zA-Z0-9]*}}, !llvm.mem.parallel_loop_access ![[LoopID:[0-9]*]]
+; PARALLEL-SCEV:  br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit, !llvm.loop ![[LoopID]]
 
 ; This loop has memory dependences that require at least a simple dependence
 ; analysis to detect the parallelism.
 ;
 ; for (i = 0; i < n; i++)
 ;   A[2 * i] = A[2 * i + 1];
 ;
 define void @test-two(i64 %n) {

 
 ret:
   fence seq_cst
   ret void
 }
 
 ; SEQUENTIAL: @test-two
 ; SEQUENTIAL-NOT: !llvm.mem.parallel_loop_access
-; SEQUENTIAL-NOT: !llvm.loop !0
+; SEQUENTIAL-NOT: !llvm.loop
 ; SEQUENTIAL-SCEV: @test-two
 ; SEQUENTIAL-SCEV-NOT: !llvm.mem.parallel_loop_access
 ; SEQUENTIAL-SCEV-NOT: !llvm.loop
 
 ; PARALLEL: @test-two
-; PARALLEL: %val_p_scalar_ = load i32* %p_scevgepload, !llvm.mem.parallel_loop_access !1
-; PARALLEL: store i32 %val_p_scalar_, i32* %p_scevgepstore, !llvm.mem.parallel_loop_access !1
-; PARALLEL: br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit, !llvm.loop !1
+; PARALLEL: %val_p_scalar_ = load i32* %p_scevgepload, {{[ ._!,a-zA-Z0-9]*}}, !llvm.mem.parallel_loop_access ![[LoopID:[0-9]*]]
+; PARALLEL: store i32 %val_p_scalar_, i32* %p_scevgepstore, {{[ ._!,a-zA-Z0-9]*}}, !llvm.mem.parallel_loop_access ![[LoopID]]
+; PARALLEL: br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit, !llvm.loop ![[LoopID]]
 ; PARALLEL-SCEV: @test-two
-; PARALLEL-SCEV: %val_p_scalar_ = load i32* %scevgep, !llvm.mem.parallel_loop_access !1
-; PARALLEL-SCEV: store i32 %val_p_scalar_, i32* %scevgep1, !llvm.mem.parallel_loop_access !1
-; PARALLEL-SCEV:  br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit, !llvm.loop !1
+; PARALLEL-SCEV: %val_p_scalar_ = load i32* %scevgep, {{[ ._!,a-zA-Z0-9]*}}, !llvm.mem.parallel_loop_access ![[LoopID:[0-9]*]]
+; PARALLEL-SCEV: store i32 %val_p_scalar_, i32* %scevgep1, {{[ ._!,a-zA-Z0-9]*}}, !llvm.mem.parallel_loop_access ![[LoopID]]
+; PARALLEL-SCEV:  br i1 %polly.loop_cond, label %polly.loop_header, label %polly.loop_exit, !llvm.loop ![[LoopID]]

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