Use getLoopLatch in place of isLoopSimplifyForm

[trentxintong]

Summary

Use getLoopLatch in place of isLoopSimplifyForm. we do not need
to know whether the loop has a preheader nor dedicated exits.

[trentxintong]

Remove a redundant getLoopLatch().

[sanjoy]

Can you please add a test case to unittests/?

[trentxintong]

In D28724#646306, @sanjoy wrote:

Can you please add a test case to unittests/?

will do.

[hfinkel]

This looks good to me (aside from the fact that, as Sanjoy pointed out, it needs a test case).

[trentxintong]

Add an assertion to check that in case we have a single latch, we actually use that
latch to get the loop id. This is the fast case !.

Add a test case to make sure fast case is exercised and works correctly.

[sanjoy]

Some comments on the test case.

unittests/Analysis/LoopInfoTest.cpp

21

I'd rather put this inside the LoopInfoTest struct as a public instance variable.

31

Can you ASSERT or assert (up to you which one) that the name of Header is for.cond, just to make sure we're doing what we think we're doing?

53

Make this a static function.

67

This is totally up to you, but I tend to prefer not using explicit "\n" s but instead end lines with a space. That makes the string more readable and it works fine since LLVM is (mostly?) whitespace insensitive.

82

Creating a pass for this seems unnecessary -- why can't you directly call LoopInfo::analyze on the relevant function?

[sanjoy]

unittests/Analysis/LoopInfoTest.cpp

86

Also, I'd add a check that the loop is not in loop simplify form, to make sure we're testing the right thing.

[trentxintong]

Address comments.

[sanjoy]

lgtm

[MatzeB]

Why was this implemented as a unittest? Wouldn't this work just as good by inserting some debug prints and then using lit+opt+FileCheck to test?

[MatzeB]

In D28724#648397, @MatzeB wrote:

Why was this implemented as a unittest? Wouldn't this work just as good by inserting some debug prints and then using lit+opt+FileCheck to test?

Admittedly the same is true for many of the other tests in unittests/Analysis. Most of the times I just don't see the benefits of using unittests over lit+FileCheck, they are usually a lot harder to understand and debug.

[trentxintong]

In D28724#648400, @MatzeB wrote:

In D28724#648397, @MatzeB wrote:

Why was this implemented as a unittest? Wouldn't this work just as good by inserting some debug prints and then using lit+opt+FileCheck to test?

Admittedly the same is true for many of the other tests in unittests/Analysis. Most of the times I just don't see the benefits of using unittests over lit+FileCheck, they are usually a lot harder to understand and debug.

One problem I can see with LIT test here is that getLoopID() is not a transformation by itself, it depends on other transformations to call/use it. Would not using a LIT test for that tranformation making the testing a little bit more fragile/unpredictable, i.e. what if the transformation later is changed not to call this API or call it in a different way. Testing this way is a bit more specific I feel.

[MatzeB]

In D28724#648407, @trentxintong wrote:

In D28724#648400, @MatzeB wrote:

In D28724#648397, @MatzeB wrote:

Why was this implemented as a unittest? Wouldn't this work just as good by inserting some debug prints and then using lit+opt+FileCheck to test?

Admittedly the same is true for many of the other tests in unittests/Analysis. Most of the times I just don't see the benefits of using unittests over lit+FileCheck, they are usually a lot harder to understand and debug.

One problem I can see with LIT test here is that getLoopID() is not a transformation by itself, it depends on other transformations to call/use it. Would not using a LIT test for that tranformation making the testing a little bit more fragile/unpredictable, i.e. what if the transformation later is changed not to call this API or call it in a different way. Testing this way is a bit more specific I feel.

You can just request a single analysis from opt without running any transformation. It should work similar to this opt -mypass -debug-only=mypass input.ll if you use DEBUG(dbgs() << ) statements, alternatively there is the -analyze flag to opt, which ends up calling MyAnalysisPass::print().

There are number of tests in test/Analysis that work this way.

[sanjoy]

In D28724#648408, @MatzeB wrote:

You can just request a single analysis from opt without running any transformation. It should work similar to this opt -mypass -debug-only=mypass input.ll if you use DEBUG(dbgs() << ) statements, alternatively there is the -analyze flag to opt, which ends up calling MyAnalysisPass::print().

There are number of tests in test/Analysis that work this way.

I think that makes sense when you're testing an analysis (e.g. does AA think these two pointers may alias or not?). Here the test is for an API that analyses and transformations uses, so to me it is more understandable to test it this way (since you're directly testing what you changed).

However, we could be better about encoding IR in a way that they're easily auto-upgraded, since IMO that's one of the drawbacks of writing unittests/.

[trentxintong]

In D28724#648408, @MatzeB wrote:

In D28724#648407, @trentxintong wrote:

In D28724#648400, @MatzeB wrote:

In D28724#648397, @MatzeB wrote:

Why was this implemented as a unittest? Wouldn't this work just as good by inserting some debug prints and then using lit+opt+FileCheck to test?

Admittedly the same is true for many of the other tests in unittests/Analysis. Most of the times I just don't see the benefits of using unittests over lit+FileCheck, they are usually a lot harder to understand and debug.

One problem I can see with LIT test here is that getLoopID() is not a transformation by itself, it depends on other transformations to call/use it. Would not using a LIT test for that tranformation making the testing a little bit more fragile/unpredictable, i.e. what if the transformation later is changed not to call this API or call it in a different way. Testing this way is a bit more specific I feel.

You can just request a single analysis from opt without running any transformation. It should work similar to this opt -mypass -debug-only=mypass input.ll if you use DEBUG(dbgs() << ) statements, alternatively there is the -analyze flag to opt, which ends up calling MyAnalysisPass::print().

There are number of tests in test/Analysis that work this way.

I think that would work for LoopInfo, with some additional debug printing. One problem/question I have is whether its a good idea to call getLoopID()/setLoopID() in ::print(), should not print() be primarily used to dump existing information, than testing some APIs in the analysis.

[MatzeB]

In D28724#648438, @trentxintong wrote:

In D28724#648408, @MatzeB wrote:

In D28724#648407, @trentxintong wrote:

In D28724#648400, @MatzeB wrote:

In D28724#648397, @MatzeB wrote:

Why was this implemented as a unittest? Wouldn't this work just as good by inserting some debug prints and then using lit+opt+FileCheck to test?

Admittedly the same is true for many of the other tests in unittests/Analysis. Most of the times I just don't see the benefits of using unittests over lit+FileCheck, they are usually a lot harder to understand and debug.

One problem I can see with LIT test here is that getLoopID() is not a transformation by itself, it depends on other transformations to call/use it. Would not using a LIT test for that tranformation making the testing a little bit more fragile/unpredictable, i.e. what if the transformation later is changed not to call this API or call it in a different way. Testing this way is a bit more specific I feel.

You can just request a single analysis from opt without running any transformation. It should work similar to this opt -mypass -debug-only=mypass input.ll if you use DEBUG(dbgs() << ) statements, alternatively there is the -analyze flag to opt, which ends up calling MyAnalysisPass::print().

There are number of tests in test/Analysis that work this way.

I think that would work for LoopInfo, with some additional debug printing. One problem/question I have is whether its a good idea to call getLoopID()/setLoopID() in ::print(), should not print() be primarily used to dump existing information, than testing some APIs in the analysis.

If course print() should not change any information.
At a first glance this looked to me like you just test the result of an anlysis. But indeed if you need to test actual interaction with an API the unittest is the right tool.

[trentxintong]

In D28724#648451, @MatzeB wrote:

In D28724#648438, @trentxintong wrote:

In D28724#648408, @MatzeB wrote:

In D28724#648407, @trentxintong wrote:

In D28724#648400, @MatzeB wrote:

In D28724#648397, @MatzeB wrote:

Why was this implemented as a unittest? Wouldn't this work just as good by inserting some debug prints and then using lit+opt+FileCheck to test?

Admittedly the same is true for many of the other tests in unittests/Analysis. Most of the times I just don't see the benefits of using unittests over lit+FileCheck, they are usually a lot harder to understand and debug.

One problem I can see with LIT test here is that getLoopID() is not a transformation by itself, it depends on other transformations to call/use it. Would not using a LIT test for that tranformation making the testing a little bit more fragile/unpredictable, i.e. what if the transformation later is changed not to call this API or call it in a different way. Testing this way is a bit more specific I feel.

You can just request a single analysis from opt without running any transformation. It should work similar to this opt -mypass -debug-only=mypass input.ll if you use DEBUG(dbgs() << ) statements, alternatively there is the -analyze flag to opt, which ends up calling MyAnalysisPass::print().

There are number of tests in test/Analysis that work this way.

I think that would work for LoopInfo, with some additional debug printing. One problem/question I have is whether its a good idea to call getLoopID()/setLoopID() in ::print(), should not print() be primarily used to dump existing information, than testing some APIs in the analysis.

If course print() should not change any information.
At a first glance this looked to me like you just test the result of an anlysis. But indeed if you need to test actual interaction with an API the unittest is the right tool.

Admittedly, I did not think how this should be tested through completely. (I know what I need to test, but as pointed out there are more than 1 way to test this). I sort of followed what @sanjoy suggested. Thanks for raising the concern though.

lib/Analysis/LoopInfo.cpp

for (Instruction &I : *BB)
         if (CS.cannotDuplicate())
           return false;
   }
   return true;
 }
 
 MDNode *Loop::getLoopID() const {
   MDNode *LoopID = nullptr;
-  if (isLoopSimplifyForm()) {
-    LoopID = getLoopLatch()->getTerminator()->getMetadata(LLVMContext::MD_loop);
+  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.
MDNode *Loop::getLoopID() const {
   return LoopID;
 }
 
 void Loop::setLoopID(MDNode *LoopID) const {
   assert(LoopID && "Loop ID should not be null");
   assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
   assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");
 
-  if (isLoopSimplifyForm()) {
-    getLoopLatch()->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
+  if (BasicBlock *Latch = getLoopLatch()) {
+    Latch->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
     return;
   }
 
+  assert(!getLoopLatch() && "The loop should have no single latch at this point");
   BasicBlock *H = getHeader();
   for (BasicBlock *BB : this->blocks()) {
     TerminatorInst *TI = BB->getTerminator();
     for (BasicBlock *Successor : TI->successors()) {
       if (Successor == H)
         TI->setMetadata(LLVMContext::MD_loop, LoopID);
     }
   }

unittests/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
   )
 
 add_llvm_unittest(AnalysisTests
   AliasAnalysisTest.cpp
   BlockFrequencyInfoTest.cpp
   BranchProbabilityInfoTest.cpp
   CallGraphTest.cpp
   CFGTest.cpp
   CGSCCPassManagerTest.cpp
   LazyCallGraphTest.cpp
+  LoopInfoTest.cpp
   MemoryBuiltinsTest.cpp
   ProfileSummaryInfoTest.cpp
   ScalarEvolutionTest.cpp
   TBAATest.cpp
   ValueTrackingTest.cpp
   UnrollAnalyzer.cpp
   )

unittests/Analysis/LoopInfoTest.cpp

+//===- LoopInfoTest.cpp - LoopInfo unit tests -----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/Support/SourceMgr.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
+                                              const char *ModuleStr) {
+  SMDiagnostic Err;
+  return parseAssemblyString(ModuleStr, Err, Context);
+}
+
+// This tests that for a loop with a single latch, we get the loop id from
+// its only latch, even in case the loop may not be in a simplified form.
+TEST(LoopInfoTest, LoopWithSingleLatch) {
+  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.inc ]\n"
+         "  %cmp = icmp slt i32 %i.0, %n\n"
+         "  br i1 %cmp, label %for.inc, label %for.end\n"
+         "for.inc:\n"
+         "  %inc = add nsw i32 %i.0, 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);
+
+  // This loop is not in simplified form.
+  EXPECT_FALSE(L->isLoopSimplifyForm());
+
+  // Analyze the loop metadata id.
+  bool loopIDFoundAndSet = false;
+  // Try to get and set the metadata id for the loop.
+  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);
+}