[SCCP] Propagate equality of a not-constant

[StephenFan]

Summary

The equality state of a not-constant can be used to do constant
propagation. For example,

define i32 @equal_not_constant(ptr noundef %p, ptr noundef %q) {
entry:
  %cmp = icmp ne ptr %p, null
  br i1 %cmp, label %if.then, label %if.end

if.then:                                          ; preds = %entry
  %cmp.then = icmp eq ptr %p, %q
  br i1 %cmp.then, label %if.then1, label %if.end

if.then1:                                         ; preds = %if.then
  %cmp.then1 = icmp ne ptr %q, null
  call void @use(i1 %cmp.then1)
  br label %if.end

if.end:
  ret i32 0
}

In this case, we can fold %cmp.then1 as true.

[nikic]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1360

Shouldn't this be getNotConstant()? Probably missing test coverage, I'd expect this to assert.

[nikic]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1360

Actually, isn't this case entirely incorrect? If A != B and B != C, then that does not imply that A == C, right?

[StephenFan]

Don't propagate the inequality of not-constant.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1360

Yes, you are right. Thanks!

[nikic]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1360

Could you please still add a test for this, to make sure the optimization does not happen?

[StephenFan]

Update title.

[StephenFan]

Add not_equal_not_constant test case.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1360

Done.

[nikic]

LGTM

llvm/lib/Transforms/Utils/SCCPSolver.cpp

if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
         // unless we have conditions that are always true/false (e.g. icmp ule
         // i32, %a, i32_max). For the latter overdefined/empty range will be
         // inferred, but the branch will get folded accordingly anyways.
         addAdditionalUser(OtherOp, &CB);
         mergeInValue(
             IV, &CB,
             ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef*/ false));
         return;
-      } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
+      } else if (Pred == CmpInst::ICMP_EQ &&
+                 (CondVal.isConstant() || CondVal.isNotConstant())) {
         // For non-integer values or integer constant expressions, only
-        // propagate equal constants.
+        // propagate equal constants or not-constants.
         addAdditionalUser(OtherOp, &CB);
         mergeInValue(IV, &CB, CondVal);
         return;
       } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant()) {
         // Propagate inequalities.
         addAdditionalUser(OtherOp, &CB);
         mergeInValue(IV, &CB,
                      ValueLatticeElement::getNot(CondVal.getConstant()));
         return;
       }
 
       return (void)mergeInValue(IV, &CB, CopyOfVal);
     }
 
     if (ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
       // Compute result range for intrinsics supported by ConstantRange.
       // Do this even if we don't know a range for all operands, as we may
       // still know something about the result range, e.g. of abs(x).

llvm/test/Transforms/SCCP/conditions-ranges.ll

bb139:                                            ; preds = %bb135
   %tmp140 = icmp eq i32 %tmp136, 0
   call void @use(i1 %tmp140)
   ret void
 
 bb142:                                            ; preds = %bb139
   ret void
 }
 
+define i32 @equal_not_constant(ptr noundef %p, ptr noundef %q) {
+; CHECK-LABEL: @equal_not_constant(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne ptr [[P:%.*]], null
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CMP_THEN:%.*]] = icmp eq ptr [[P]], [[Q:%.*]]
+; CHECK-NEXT:    br i1 [[CMP_THEN]], label [[IF_THEN1:%.*]], label [[IF_END]]
+; CHECK:       if.then1:
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %cmp = icmp ne ptr %p, null
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %cmp.then = icmp eq ptr %p, %q
+  br i1 %cmp.then, label %if.then1, label %if.end
+
+if.then1:                                         ; preds = %if.then
+  %cmp.then1 = icmp ne ptr %q, null
+  call void @use(i1 %cmp.then1)
+  br label %if.end
+
+if.end:
+  ret i32 0
+}
+
+define i32 @not_equal_not_constant(ptr noundef %p, ptr noundef %q) {
+; CHECK-LABEL: @not_equal_not_constant(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne ptr [[P:%.*]], null
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CMP_THEN:%.*]] = icmp ne ptr [[P]], [[Q:%.*]]
+; CHECK-NEXT:    br i1 [[CMP_THEN]], label [[IF_THEN1:%.*]], label [[IF_END]]
+; CHECK:       if.then1:
+; CHECK-NEXT:    [[CMP_THEN1:%.*]] = icmp ne ptr [[Q]], null
+; CHECK-NEXT:    call void @use(i1 [[CMP_THEN1]])
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %cmp = icmp ne ptr %p, null
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %cmp.then = icmp ne ptr %p, %q
+  br i1 %cmp.then, label %if.then1, label %if.end
+
+if.then1:                                         ; preds = %if.then
+  %cmp.then1 = icmp ne ptr %q, null
+  call void @use(i1 %cmp.then1)
+  br label %if.end
+
+if.end:
+  ret i32 0
+}
+
 define i1 @ptr_icmp_data_layout() {
 ; CHECK-LABEL: @ptr_icmp_data_layout(
 ; CHECK-NEXT:    ret i1 false
 ;
   %a.end = getelementptr i32, ptr @A, i64 1
   %cmp = icmp eq ptr %a.end, @A
   ret i1 %cmp
 }