[JumpThreading] ComputeValueKnownInPredecessors only handles the case when phi is on lhs of a comparison op

[wmi]

Summary

For the following testcase,
L1:

%t0 = add i32 %m, 7
%t3 = icmp eq i32* %t2, null
br i1 %t3, label %L3, label %L2

L2:

%t4 = load i32, i32* %t2, align 4
br label %L3

L3:

%t5 = phi i32 [ %t0, %L1 ], [ %t4, %L2 ]
%t6 = icmp eq i32 %t0, %t5
br i1 %t6, label %L4, label %L5

We know if we go through the path L1 --> L3, %t6 should always be true. However, currently, if the rhs of the eq comparison is phi, JumpThreading fails to evaluate %t6 to true. And we know that Instcombine cannot guarantee always canonicalizing phi to the left hand side of the comparison operation according to the operand priority comparison mechanism in instcombine.

The patch handles the case when rhs of the comparison op is a phi.

[davidxl]

lgtm

[wmi]

update the patch to fix a bug found in llvm bootstrap.

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::ComputeValueKnownInPredecessors(
   if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) {
     assert(Preference == WantInteger && "Compares only produce integers");
     Type *CmpType = Cmp->getType();
     Value *CmpLHS = Cmp->getOperand(0);
     Value *CmpRHS = Cmp->getOperand(1);
     CmpInst::Predicate Pred = Cmp->getPredicate();
 
     PHINode *PN = dyn_cast<PHINode>(CmpLHS);
+    if (!PN)
+      PN = dyn_cast<PHINode>(CmpRHS);
     if (PN && PN->getParent() == BB) {
       const DataLayout &DL = PN->getModule()->getDataLayout();
       // We can do this simplification if any comparisons fold to true or false.
       // See if any do.
       if (DDT->pending())
         LVI->disableDT();
       else
         LVI->enableDT();
       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
         BasicBlock *PredBB = PN->getIncomingBlock(i);
-        Value *LHS = PN->getIncomingValue(i);
-        Value *RHS = CmpRHS->DoPHITranslation(BB, PredBB);
-
+        Value *LHS, *RHS;
+        if (PN == CmpLHS) {
+          LHS = PN->getIncomingValue(i);
+          RHS = CmpRHS->DoPHITranslation(BB, PredBB);
+        } else {
+          LHS = CmpLHS->DoPHITranslation(BB, PredBB);
+          RHS = PN->getIncomingValue(i);
+        }
         Value *Res = SimplifyCmpInst(Pred, LHS, RHS, {DL});
         if (!Res) {
           if (!isa<Constant>(RHS))
             continue;
 
+          // getPredicateOnEdge call will make no sense if LHS is defined in BB.
+          auto LHSInst = dyn_cast<Instruction>(LHS);
+          if (LHSInst && LHSInst->getParent() == BB)
+            continue;
+
           LazyValueInfo::Tristate
             ResT = LVI->getPredicateOnEdge(Pred, LHS,
                                            cast<Constant>(RHS), PredBB, BB,
                                            CxtI ? CxtI : Cmp);
           if (ResT == LazyValueInfo::Unknown)
             continue;
           Res = ConstantInt::get(Type::getInt1Ty(LHS->getContext()), ResT);
         }

llvm/trunk/test/Other/pr32085.ll

 ; RUN: opt -S -O1 < %s -o %t1.ll
 ;; Show that there's no difference after running another simplify CFG
-; RUN: opt -S -simplifycfg < %t1.ll -o %t2.ll
+; RUN: opt -S -simplifycfg < %t1.ll -o %t2.ll 
+; RUN: sed -i 's/; preds = .*//g' %t1.ll %t2.ll
 ; RUN: diff %t1.ll %t2.ll
 
 ; Test from LoopSink pass, leaves some single-entry single-exit basic blocks.
 ; After LoopSink, we get a basic block .exit.loopexit which has one entry and
 ; one exit, the only instruction is a branch. Make sure it doesn't show up.
 ; Make sure they disappear at -O1.
 
 @g = global i32 0, align 4

llvm/trunk/test/Transforms/JumpThreading/phi-known.ll

 ; CHECK-NEXT: br i1 %cmp1
   %p1 = phi i8* [%p, %entry], [%p1, %loop]
   %cmp1 = icmp ne i8* %p1, null
   br i1 %cmp1, label %exit, label %loop
 exit:
   ret void
 }
 
+; The eq predicate is always true if we go through the path from
+; L1 to L3, no matter the phi result %t5 is on the lhs or rhs of
+; the predicate.
+declare void @goo()
+declare void @hoo()
+
+define void @test3(i32 %m, i32** %t1) {
+L1:
+  %t0 = add i32 %m, 7
+  %t2 = load i32*, i32** %t1, align 8
+; CHECK-LABEL: @test3
+; CHECK: %t3 = icmp eq i32* %t2, null
+; CHECK: br i1 %t3, label %[[LABEL2:.*]], label %[[LABEL1:.*]]
+
+  %t3 = icmp eq i32* %t2, null
+  br i1 %t3, label %L3, label %L2
+
+; CHECK: [[LABEL1]]:
+; CHECK-NEXT: %t4 = load i32, i32* %t2, align 4
+L2:
+  %t4 = load i32, i32* %t2, align 4
+  br label %L3
+
+L3:
+  %t5 = phi i32 [ %t0, %L1 ], [ %t4, %L2 ]
+  %t6 = icmp eq i32 %t0, %t5
+  br i1 %t6, label %L4, label %L5
+
+; CHECK: [[LABEL2]]:
+; CHECK-NEXT: call void @goo()
+L4:
+  call void @goo()
+  ret void
+
+L5:
+  call void @hoo()
+  ret void
+}