Rewrite part of how loop ID is obtained.

[trentxintong]

Summary

If a loop has multiple backedges and all of them have the same metadata.
we return that metadata. Otherwise we return nullptr.

Without the patch, we search through all blocks in the loop, this is an
overkill and more importantly we bail on the first block that is either a latch
without metadata or *not* a latch at all. we should not bail on non-latch block.

[sanjoy]

Code-wise this looks fine, but the "If a loop has multiple backedges and all of them have the same metadata we return that metadata. Otherwise we return nullptr." bit should be documented in the LangRef. I'll also ask you to please wait for someone familiar with how LLVM uses !llvm.loop to give a final go head before checking this in.

lib/Analysis/LoopInfo.cpp

223

s/I/BB/

unittests/Analysis/LoopInfoTest.cpp

103

You can reduce some of this boilerplate by a runWithLoopInfo helper, as in: https://github.com/llvm-mirror/llvm/blob/master/unittests/Analysis/ScalarEvolutionTest.cpp#L54

[trentxintong]

In D28756#647368, @sanjoy wrote:

Code-wise this looks fine, but the "If a loop has multiple backedges and all of them have the same metadata we return that metadata. Otherwise we return nullptr." bit should be documented in the LangRef. I'll also ask you to please wait for someone familiar with how LLVM uses !llvm.loop to give a final go head before checking this in.

Thanks for the review. I will wait for @hfinkel to give the final approval.

[hfinkel]

In D28756#647380, @trentxintong wrote:

In D28756#647368, @sanjoy wrote:

Code-wise this looks fine, but the "If a loop has multiple backedges and all of them have the same metadata we return that metadata. Otherwise we return nullptr." bit should be documented in the LangRef. I'll also ask you to please wait for someone familiar with how LLVM uses !llvm.loop to give a final go head before checking this in.

Thanks for the review. I will wait for @hfinkel to give the final approval.

I think that this makes sense. I agree with Sanjoy that we should make sure that the LangRef reflects what we actually do here.

lib/Analysis/LoopInfo.cpp

223

You should be able to use a range-based for here, something like:

for (auto &BB : predecessors(H)) {

[trentxintong]

In D28756#647388, @hfinkel wrote:

In D28756#647380, @trentxintong wrote:

In D28756#647368, @sanjoy wrote:

Code-wise this looks fine, but the "If a loop has multiple backedges and all of them have the same metadata we return that metadata. Otherwise we return nullptr." bit should be documented in the LangRef. I'll also ask you to please wait for someone familiar with how LLVM uses !llvm.loop to give a final go head before checking this in.

Thanks for the review. I will wait for @hfinkel to give the final approval.

I think that this makes sense. I agree with Sanjoy that we should make sure that the LangRef reflects what we actually do here.

To be honest, I am a little bit confused now. Originally, I created this patch because according to getLoopID()'s comment, we should return the null if there are multiple latches and their loop IDs do not match (in case some are null, we return null). I am looking through how llvm.loop is used in the optimizer and came across this https://reviews.llvm.org/D26495 . we set the loop id to the newly created backedge in loopsimplify even some latches do not or have distinct loop ID's. These 2 things seem conflicting to me, i.e. on one side, we find and use the loop ID only if all the latches have them and they are identical, on the other side, we set loop ID (potentially use later) to the newly created backedge even though some latches do not have a loop id or have different loop IDs.

So which one is right ? Given a loop with multiple latches, and they have different loop IDs, can we use the loop ID and which one we use ?

lib/Analysis/LoopInfo.cpp

MDNode *Loop::getLoopID() const {
   if (BasicBlock *Latch = getLoopLatch()) {
     LoopID = Latch->getTerminator()->getMetadata(LLVMContext::MD_loop);
   } else {
     assert(!getLoopLatch() &&
            "The loop should have no single latch at this point");
     // Go through each predecessor of the loop header and check the
     // terminator for the metadata.
     BasicBlock *H = getHeader();
-    for (BasicBlock *BB : this->blocks()) {
-      TerminatorInst *TI = BB->getTerminator();
-      MDNode *MD = nullptr;
-
-      // Check if this terminator branches to the loop header.
-      for (BasicBlock *Successor : TI->successors()) {
-        if (Successor == H) {
-          MD = TI->getMetadata(LLVMContext::MD_loop);
-          break;
-        }
-      }
-      if (!MD)
+    assert(H && "Loop must have a header");
+    for (auto I = pred_begin(H), E = pred_end(H); I != E; ++I) {
+      // Ignore header's predecessor outside the loop.
+      if (!contains(*I))
+        continue;
+      MDNode *MD = (*I)->getTerminator()->getMetadata(LLVMContext::MD_loop);
+      // Unable to find a metadata in the latch block.
+      if (!MD) 
         return nullptr;
 
+      // Found a metadata.
       if (!LoopID)
         LoopID = MD;
+      // Found a non-null, but different metadata from the one seen before.
       else if (MD != LoopID)
         return nullptr;
     }
   }
   if (!LoopID || LoopID->getNumOperands() == 0 ||
       LoopID->getOperand(0) != LoopID)
     return nullptr;
   return LoopID;

unittests/Analysis/LoopInfoTest.cpp

if (MDNode *D = L->getLoopID()) {
     L->setLoopID(D);
     loopIDFoundAndSet = true;
   }
 
   // We must have successfully found and set the loop id in the
   // only latch the loop has.
   EXPECT_TRUE(loopIDFoundAndSet);
 }
+
+// This test has 2 latches and both carry the same llvm.loop metadata.
+TEST(LoopInfoTest, LoopWithMultiLatchesWithSameMD) {
+  const char *ModuleStr =
+         "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
+         "define void @foo(i32 %n) {\n"
+         "entry:\n"
+         "  br i1 undef, label %for.cond, label %for.end\n"
+         "for.cond:\n"
+         "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.first.latch ], [ %inc2, %for.second.latch]\n"
+         "  %cmp = icmp slt i32 %i.0, %n\n"
+         "  br i1 %cmp, label %for.first.latch, label %for.end\n"
+         "for.first.latch:\n"
+         "  %inc = add nsw i32 %i.0, 1\n"
+         "  br i1 undef, label %for.second.latch, label %for.cond, !llvm.loop !0\n"
+         "for.second.latch:\n"
+         "  %inc2 = add nsw i32 %inc, 1\n"
+         "  br label %for.cond, !llvm.loop !0\n"
+         "for.end:\n"
+         "  ret void\n"
+         "}\n"
+         "!0 = distinct !{!0, !1}\n"
+         "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
+  
+  // Parse the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
+
+  // Build the dominator tree and loop info.
+  DominatorTree DT;
+  DT.recalculate(*M->begin());
+  LoopInfo LI;
+  LI.analyze(DT);
+
+  Function &F = *M->begin();
+  Function::iterator FI = F.begin();
+  FI++; // First basic block is entry - skip it.
+  BasicBlock *Header = &*FI++;
+  assert(Header->getName() == "for.cond");
+  Loop *L = LI.getLoopFor(Header);
+
+  // We must be able to get the metadata.
+  EXPECT_TRUE(L->getLoopID());
+}
+
+// This test has 2 latches, but only 1 carry the llvm.loop metadata.
+TEST(LoopInfoTest, LoopWithMultiLatchesSomeWithMD) {
+  const char *ModuleStr =
+         "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
+         "define void @foo(i32 %n) {\n"
+         "entry:\n"
+         "  br i1 undef, label %for.cond, label %for.end\n"
+         "for.cond:\n"
+         "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.first.latch ], [ %inc2, %for.second.latch]\n"
+         "  %cmp = icmp slt i32 %i.0, %n\n"
+         "  br i1 %cmp, label %for.first.latch, label %for.end\n"
+         "for.first.latch:\n"
+         "  %inc = add nsw i32 %i.0, 1\n"
+         "  br i1 undef, label %for.second.latch, label %for.cond, !llvm.loop !0\n"
+         "for.second.latch:\n"
+         "  %inc2 = add nsw i32 %inc, 1\n"
+         "  br label %for.cond\n"
+         "for.end:\n"
+         "  ret void\n"
+         "}\n"
+         "!0 = distinct !{!0, !1}\n"
+         "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
+  
+  // Parse the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
+
+  // Build the dominator tree and loop info.
+  DominatorTree DT;
+  DT.recalculate(*M->begin());
+  LoopInfo LI;
+  LI.analyze(DT);
+
+  Function &F = *M->begin();
+  Function::iterator FI = F.begin();
+  FI++; // First basic block is entry - skip it.
+  BasicBlock *Header = &*FI++;
+  assert(Header->getName() == "for.cond");
+  Loop *L = LI.getLoopFor(Header);
+
+  // We must not be able to get the metadata from the loop as one of the
+  // latch does not have it.
+  EXPECT_FALSE(L->getLoopID());
+}
+
+