[CVP] Simplify cmp of local phi node

[nikic]

Summary

CVP currently does not simplify cmps with instructions in the same block, because LVI getPredicateAt() currently does not really provide much useful information for that case (D69686 would change that, but is stuck.) However, if the instruction is a Phi node, then LVI can compute the result of the predicate by threading it into the predecessor blocks, which allows it simplify some conditions that nothing else can handle. Relevant code: https://github.com/llvm/llvm-project/blob/6d6a4590c5d4c7fc7445d72fe685f966b0a8cafb/llvm/lib/Analysis/LazyValueInfo.cpp#L1904-L1927

The example in the test case is reduced from a Rust test case that sees a major perf regression in LLVM 10 (https://bugs.llvm.org/show_bug.cgi?id=44461). This patch addresses part of the regression (though not all of it).

[nikic]

Ping

[nikic]

Ping

[reames]

LGTM.

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
   auto *C = dyn_cast<Constant>(Cmp->getOperand(1));
   if (!C)
     return false;
 
   // As a policy choice, we choose not to waste compile time on anything where
   // the comparison is testing local values.  While LVI can sometimes reason
   // about such cases, it's not its primary purpose.  We do make sure to do
   // the block local query for uses from terminator instructions, but that's
-  // handled in the code for each terminator.
+  // handled in the code for each terminator. As an exception, we allow phi
+  // nodes, for which LVI can thread the condition into predecessors.
   auto *I = dyn_cast<Instruction>(Op0);
-  if (I && I->getParent() == Cmp->getParent())
+  if (I && I->getParent() == Cmp->getParent() && !isa<PHINode>(I))
     return false;
 
   LazyValueInfo::Tristate Result =
       LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp);
   if (Result == LazyValueInfo::Unknown)
     return false;
 
   ++NumCmps;

llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll

 define void @test_cmp_phi(i8 %a) {
 ; CHECK-LABEL: @test_cmp_phi(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C0:%.*]] = icmp ult i8 [[A:%.*]], 2
 ; CHECK-NEXT:    br i1 [[C0]], label [[LOOP:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[P:%.*]] = phi i8 [ [[A]], [[ENTRY:%.*]] ], [ [[B:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ne i8 [[P]], 0
-; CHECK-NEXT:    [[C2:%.*]] = icmp ne i8 [[P]], 2
-; CHECK-NEXT:    [[C3:%.*]] = and i1 [[C1]], [[C2]]
 ; CHECK-NEXT:    [[C4:%.*]] = call i1 @get_bool()
 ; CHECK-NEXT:    [[B]] = zext i1 [[C4]] to i8
-; CHECK-NEXT:    br i1 [[C3]], label [[LOOP]], label [[EXIT]]
+; CHECK-NEXT:    br i1 [[C1]], label [[LOOP]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %c0 = icmp ult i8 %a, 2
   br i1 %c0, label %loop, label %exit
 
 loop: