[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 (!V) {
           // for vector type constants that are not all zeroes or all ones.
         }
       }
 
       // 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 (!V) {
         Constant *C = dyn_cast<Constant>(SI->getFalseValue());
-        if (!C) continue;
-
+        if (C) {
           if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
-              P->getIncomingBlock(i), BB, P) !=
-            LazyValueInfo::False)
+                                      P->getIncomingBlock(i), BB,
+                                      P) != LazyValueInfo::False)
             continue;
           V = SI->getTrueValue();
         }
+      }
+
+      // The "true" case,
+      // similar to the select "false" case, but try the select "true" value
+      if (!V) {
+        Constant *C = dyn_cast<Constant>(SI->getTrueValue());
+        if (C) {
+          if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
+                                      P->getIncomingBlock(i), BB,
+                                      P) != LazyValueInfo::False)
+            continue;
+          V = SI->getFalseValue();
+        }
+      }
+
+      if (!V)
+        continue;
 
       LLVM_DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
     }
 
     P->setIncomingValue(i, V);
     Changed = true;
   }
 

llvm/test/Transforms/CorrelatedValuePropagation/select_cond.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=correlated-propagation -S | FileCheck %s
+
+declare i32* @f(i32*)
+
+; "false" case for CorrelatedValuePropagation
+define void @loop1(i32* %x, i32* %y) {
+; CHECK-LABEL: @loop1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:  loop:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32* [ [[F:%.*]], [[LOOP]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[F]] = tail call i32* @f(i32* [[PHI]])
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32* [[F]], [[Y:%.*]]
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32* [[F]], i32* null
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32* [[SEL]], null
+; CHECK-NEXT:    br i1 [[CMP2]], label [[RETURN:%.*]], label [[LOOP]]
+; CHECK:       return:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+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
+
+return:
+  ret void
+}
+
+
+; "true" case for CorrelatedValuePropagation
+define void @loop2(i32* %x, i32* %y) {
+; CHECK-LABEL: @loop2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; 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:
+  br label %loop
+
+loop:
+  %phi = phi i32* [ %sel, %loop ], [ %x, %entry ]
+  %f = tail call i32* @f(i32* %phi)
+  %cmp1 = icmp eq i32* %f, %y
+  %sel = select i1 %cmp1, i32* null, i32* %f
+  %cmp2 = icmp eq i32* %sel, null
+  br i1 %cmp2, label %return, label %loop
+
+return:
+  ret void
+}