[Transforms] Enhance CorrelatedValuePropagation to handle both values of select

[slydiman]

Summary

The "Correlated Value Propagation" pass was missing a case when handling select instructions. It was only handling the "false" constant value, while in NVPTX the select may have the condition (and thus the branches) inverted, for example:

loop:
	%phi = phi i32* [ %sel, %loop ], [ %x, %entry ]
	%f = tail call i32* @f(i32* %phi)
	%cmp1 = icmp ne i32* %f, %y
	%sel = select i1 %cmp1, i32* %f, i32* null
	%cmp2 = icmp eq i32* %sel, null
	br i1 %cmp2, label %return, label %loop

But the select condition can be inverted:

	%cmp1 = icmp eq i32* %f, %y
	%sel = select i1 %cmp1, i32* null, i32* %f

The fix is to enhance "Correlated Value Propagation" to handle both branches of the select instruction.

[nikic]

This looks reasonable, as we do not generally canonicalize constants in select to the RHS. It looks like your new test is based on @test5() from basic.ll, can you please add the new one next to it, precommit and rebase?

[slydiman]

In D119643#3318573, @nikic wrote:

It looks like your new test is based on @test5() from basic.ll, can you please add the new one next to it, precommit and rebase?

Done

[slydiman]

Ping

[lebedev.ri]

Please precommit the tests first.
LGTM

[slydiman]

In D119643#3334208, @lebedev.ri wrote:

Please precommit the tests first.

Thanks for the review. Could you provide some details how to precommit these tests? This patch contains 2 new tests inside the existing file basic.ll. @loop1 will be green anyway, but @loop2 will be red w/o this patch. I don't see a way to apply XFAIL to @loop2.

[slydiman]

In D119643#3335831, @slydiman wrote:

Could you provide some details how to precommit these tests?

Never mind. I have figured that out.

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

if (Constant *C = LVI->getConstantOnEdge(Condition, From, To, CxtI)) {
         return SI->getFalseValue();
     }
   }
 
   // Look if the select has a constant but LVI tells us that the incoming
   // value can never be that constant. In that case replace the incoming
   // value with the other value of the select. This often allows us to
   // remove the select later.
+
+  // The "false" case
   if (auto *C = dyn_cast<Constant>(SI->getFalseValue()))
     if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, From, To, CxtI) ==
         LazyValueInfo::False)
       return SI->getTrueValue();
 
+  // The "true" case,
+  // similar to the select "false" case, but try the select "true" value
+  if (auto *C = dyn_cast<Constant>(SI->getTrueValue()))
+    if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, From, To, CxtI) ==
+        LazyValueInfo::False)
+      return SI->getFalseValue();
+
   return nullptr;
 }
 
 static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT,
                        const SimplifyQuery &SQ) {
   bool Changed = false;
 
   BasicBlock *BB = P->getParent();

llvm/test/Transforms/CorrelatedValuePropagation/basic.ll

 }
 
 ; "true" case for CorrelatedValuePropagation
 define void @loop2(i32* %x, i32* %y) {
 ; CHECK-LABEL: @loop2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-;; CorrelatedValuePropagation should handle inverted select condition, but it does not yet.
-;; CHECK-NEXT:    [[PHI:%.*]] = phi i32* [ [[F:%.*]], [[LOOP]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[F:%.*]] = tail call i32* @f(i32* [[PHI]])
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32* [ [[F:%.*]], [[LOOP]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[F]] = tail call i32* @f(i32* [[PHI]])
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32* [[F]], [[Y:%.*]]
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32* null, i32* [[F]]
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32* [[SEL]], null
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[RETURN:%.*]], label [[LOOP]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret void
 ;
 entry: