Annotate LLVM-IR for all parallel loops

  This change allows to annotate all parallel loops with loop id metadata.
  Furthermore, it will annotate memory instructions with
  llvm.mem.parallel_loop_access metadata for all surrounding parallel loops.
  This is especially usefull if an external paralleliser is used.

  This also removes the PollyLoopInfo class and comments the
  LoopAnnotator.

  A test case for multiple parallel loops is attached.

llvm-svn: 218793

3 files changed, 57 insertions, 35 deletions

diff --git a/polly/lib/CodeGen/IRBuilder.cpp b/polly/lib/CodeGen/IRBuilder.cpp
index 5347ba9f133..2fc84191774 100644
--- a/polly/lib/CodeGen/IRBuilder.cpp
+++ b/polly/lib/CodeGen/IRBuilder.cpp
@@ -13,48 +13,66 @@
 //===----------------------------------------------------------------------===//
 
 #include "polly/CodeGen/IRBuilder.h"
-#include "llvm/Analysis/LoopInfo.h"
+
 #include "llvm/IR/Metadata.h"
 #include "llvm/Support/Debug.h"
 
 using namespace llvm;
 using namespace polly;
 
-llvm::MDNode *polly::PollyLoopInfo::GetLoopID() const {
-  if (LoopID)
-    return LoopID;
-
-  llvm::Value *Args[] = {0};
-  LoopID = llvm::MDNode::get(Header->getContext(), Args);
+/// @brief Get the loop id metadata node.
+///
+/// Each loop is identified by a self referencing metadata node of the form:
+///
+///    '!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;
 }
 
-void polly::LoopAnnotator::Begin(llvm::BasicBlock *Header) {
-  Active.push_back(PollyLoopInfo(Header));
+void polly::LoopAnnotator::pushLoop(Loop *L, bool IsParallel) {
+  ActiveLoops.push_back(L);
+  if (!IsParallel)
+    return;
+
+  BasicBlock *Header = L->getHeader();
+  MDNode *Id = getLoopID(L);
+  Value *Args[] = {Id};
+  MDNode *Ids = ParallelLoops.empty()
+                    ? MDNode::get(Header->getContext(), Args)
+                    : MDNode::concatenate(ParallelLoops.back(), Id);
+  ParallelLoops.push_back(Ids);
 }
 
-void polly::LoopAnnotator::End() { Active.pop_back(); }
+void polly::LoopAnnotator::popLoop(bool IsParallel) {
+  ActiveLoops.pop_back();
+  if (!IsParallel)
+    return;
 
-void polly::LoopAnnotator::SetCurrentParallel() {
-  Active.back().SetParallel(true);
+  assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
+  ParallelLoops.pop_back();
 }
 
-void polly::LoopAnnotator::Annotate(llvm::Instruction *Inst) {
-  if (Active.empty())
+void polly::LoopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L,
+                                             bool IsParallel) const {
+  if (!IsParallel)
     return;
 
-  const PollyLoopInfo &L = Active.back();
-  if (!L.IsParallel())
+  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())
     return;
 
-  if (TerminatorInst *TI = dyn_cast<llvm::TerminatorInst>(Inst)) {
-    for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i)
-      if (TI->getSuccessor(i) == L.GetHeader()) {
-        TI->setMetadata("llvm.loop", L.GetLoopID());
-        break;
-      }
-  } else if (Inst->mayReadOrWriteMemory()) {
-    Inst->setMetadata("llvm.mem.parallel_loop_access", L.GetLoopID());
-  }
+  Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
 }
diff --git a/polly/lib/CodeGen/IslCodeGeneration.cpp b/polly/lib/CodeGen/IslCodeGeneration.cpp
index 22a8fe51abf..f5599ee3a25 100644
--- a/polly/lib/CodeGen/IslCodeGeneration.cpp
+++ b/polly/lib/CodeGen/IslCodeGeneration.cpp
@@ -319,8 +319,8 @@ void IslNodeBuilder::createForSequential(__isl_take isl_ast_node *For) {
   CmpInst::Predicate Predicate;
   bool Parallel;
 
-  Parallel = IslAstInfo::isInnermostParallel(For) &&
-             !IslAstInfo::isReductionParallel(For);
+  Parallel =
+      IslAstInfo::isParallel(For) && !IslAstInfo::isReductionParallel(For);
 
   Body = isl_ast_node_for_get_body(For);
 
@@ -362,7 +362,7 @@ void IslNodeBuilder::createForSequential(__isl_take isl_ast_node *For) {
 
   create(Body);
 
-  Annotator.End();
+  Annotator.popLoop(Parallel);
 
   IDToValue.erase(IteratorID);
 
diff --git a/polly/lib/CodeGen/LoopGenerators.cpp b/polly/lib/CodeGen/LoopGenerators.cpp
index ef9bda58fd5..1ec9fb85026 100644
--- a/polly/lib/CodeGen/LoopGenerators.cpp
+++ b/polly/lib/CodeGen/LoopGenerators.cpp
@@ -64,12 +64,6 @@ Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
   BasicBlock *PreHeaderBB =
       BasicBlock::Create(Context, "polly.loop_preheader", F);
 
-  if (Annotator) {
-    Annotator->Begin(HeaderBB);
-    if (Parallel)
-      Annotator->SetCurrentParallel();
-  }
-
   // Update LoopInfo
   Loop *OuterLoop = LI.getLoopFor(BeforeBB);
   Loop *NewLoop = new Loop();
@@ -86,6 +80,11 @@ Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
 
   NewLoop->addBasicBlockToLoop(HeaderBB, LI.getBase());
 
+  // Notify the annotator (if present) that we have a new loop, but only
+  // after the header block is set.
+  if (Annotator)
+    Annotator->pushLoop(NewLoop, Parallel);
+
   // ExitBB
   ExitBB = SplitBlock(BeforeBB, Builder.GetInsertPoint()++, P);
   ExitBB->setName("polly.loop_exit");
@@ -122,7 +121,12 @@ Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
   UB = Builder.CreateSub(UB, Stride, "polly.adjust_ub");
   LoopCondition = Builder.CreateICmp(Predicate, IV, UB);
   LoopCondition->setName("polly.loop_cond");
-  Builder.CreateCondBr(LoopCondition, HeaderBB, ExitBB);
+
+  // Create the loop latch and annotate it as such.
+  BranchInst *B = Builder.CreateCondBr(LoopCondition, HeaderBB, ExitBB);
+  if (Annotator)
+    Annotator->annotateLoopLatch(B, NewLoop, Parallel);
+
   IV->addIncoming(IncrementedIV, HeaderBB);
   if (GuardBB)
     DT.changeImmediateDominator(ExitBB, GuardBB);