[LoopInfo] Fix a bug in the function getInductionVariable

[duan.db]

Summary

There is a bug in getInductionVariable. From code, the way this function gets the induction variable is by judging whether StepInst or IndVar in the phi statement is one of the operands of CMP. It will perform dyn_cast operations. But if the LatchCmpOp0/LatchCmpOp1 is a constant, it will be cast to null. The same situation exists when getting the Stepinst, the subsequent comparison may result in null == null, which is meaningless. The induction variable will be the first phi of the loop, and this does not match the logic of this function.

[Whitney]

Thanks for fixing this. Can you please provide a test case?

[duan.db]

Hi, This is the test case, any other suggestions?

[fhahn]

The induction variable will be the first phi of the loop, and this does not match the logic of this function.

Is the code relying on the IV being the first phi in the loop? That is not a guarantee that can be relied on I think.

llvm/lib/Analysis/LoopInfo.cpp

312–313

nit: no need for this->?

llvm/unittests/Analysis/LoopInfoTest.cpp

1551

Can you clean up the IR? There are multiple things that should not be needed, like

"; Function Attrs:

dso_local sigext

the metadata and more.

llvm/lib/Analysis/LoopInfo.cpp

if (!isLoopSimplifyForm())
     return nullptr;
 
   BasicBlock *Header = getHeader();
   assert(Header && "Expected a valid loop header");
   ICmpInst *CmpInst = getLatchCmpInst();
   if (!CmpInst)
     return nullptr;
 
-  Instruction *LatchCmpOp0 = dyn_cast<Instruction>(CmpInst->getOperand(0));
-  Instruction *LatchCmpOp1 = dyn_cast<Instruction>(CmpInst->getOperand(1));
+  Value *LatchCmpOp0 = CmpInst->getOperand(0);
+  Value *LatchCmpOp1 = CmpInst->getOperand(1);
 
   for (PHINode &IndVar : Header->phis()) {
     InductionDescriptor IndDesc;
     if (!InductionDescriptor::isInductionPHI(&IndVar, this, &SE, IndDesc))
       continue;
 
-    Instruction *StepInst = IndDesc.getInductionBinOp();
+    BasicBlock *Latch = getLoopLatch();
+    Value *StepInst = IndVar.getIncomingValueForBlock(Latch);
 
     // case 1:
     // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
     // StepInst = IndVar + step
     // cmp = StepInst < FinalValue
     if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1)
       return &IndVar;
 

llvm/unittests/Analysis/LoopInfoTest.cpp

runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
 
     Loop *L = LI.getLoopFor(Header);
     EXPECT_NE(L, nullptr);
 
     // L should not have a guard branch
     EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
   });
 }
+
+TEST(LoopInfoTest, LoopInductionVariable) {
+  const char *ModuleStr =
+      "define i32 @foo(i32* %addr) {\n"
+      "entry:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %sum.08 = phi i32 [ 0, %entry ], [ %add, %for.body ]\n"
+      "  %addr.addr.06 = phi i32* [ %addr, %entry ], [ %incdec.ptr, %for.body "
+      "]\n"
+      "  %count.07 = phi i32 [ 6000, %entry ], [ %dec, %for.body ]\n"
+      "  %0 = load i32, i32* %addr.addr.06, align 4\n"
+      "  %add = add nsw i32 %0, %sum.08\n"
+      "  %dec = add nsw i32 %count.07, -1\n"
+      "  %incdec.ptr = getelementptr inbounds i32, i32* %addr.addr.06, i64 1\n"
+      "  %cmp = icmp ugt i32 %count.07, 1\n"
+      "  br i1 %cmp, label %for.body, label %for.end\n"
+      "for.end:\n"
+      "  %cmp1 = icmp eq i32 %add, -1\n"
+      "  %conv = zext i1 %cmp1 to i32\n"
+      "  ret i32 %conv\n"
+      "}\n";
+
+  // Parse the module.
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
+
+  runWithLoopInfoPlus(
+      *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        Function::iterator FI = F.begin();
+        BasicBlock *Header = &*(++FI);
+        Loop *L = LI.getLoopFor(Header);
+        EXPECT_NE(L, nullptr);
+        EXPECT_EQ(L->getInductionVariable(SE)->getName(), "count.07");
+      });
+}