[SCCP] Use ANDs to limit the range of result with overdef operand.

[fhahn]

Summary

If one of the operands of an AND is overdefined and the other is
a constant range, the range of the result is limited by the range.

Note that without resolving the way undefs are handled, we generate
invalid code for some functions in the test.

[fhahn]

Add a few additional test cases.

[fhahn]

Handled directly by D71936 after the recent changes.

llvm/lib/Transforms/Scalar/SCCP.cpp

void SCCPSolver::visitBinaryOperator(Instruction &I) {
   // Otherwise, one of our operands is overdefined.  Try to produce something
   // better than overdefined with some tricks.
   // If this is 0 / Y, it doesn't matter that the second operand is
   // overdefined, and we can replace it with zero.
   if (I.getOpcode() == Instruction::UDiv || I.getOpcode() == Instruction::SDiv)
     if (isConstant(V1State) && getConstant(V1State)->isNullValue())
       return (void)markConstant(IV, &I, getConstant(V1State));
 
+  // ANDs restricts the range of the result, if either operand is a constant
+  // range.
+  if (I.getOpcode() == Instruction::And &&
+      (V1State.isConstantRange() || V2State.isConstantRange())) {
+    auto A = V1State.isConstantRange()
+                 ? V1State.getConstantRange()
+                 : ConstantRange::getFull(I.getType()->getScalarSizeInBits());
+    auto B = V2State.isConstantRange()
+                 ? V2State.getConstantRange()
+                 : ConstantRange::getFull(I.getType()->getScalarSizeInBits());
+    ConstantRange R = A.binaryOp(cast<BinaryOperator>(&I)->getOpcode(), B);
+    mergeInValue(&I, LatticeVal::getRange(R));
+    return;
+  }
+
   // If this is:
   // -> AND/MUL with 0
   // -> OR with -1
   // it doesn't matter that the other operand is overdefined.
   if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul ||
       I.getOpcode() == Instruction::Or) {
     LatticeVal *NonOverdefVal = nullptr;
     if (!isOverdefined(V1State))

llvm/test/Transforms/SCCP/range-and.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -sccp %s | FileCheck %s
+
+; Test case for PR44949.
+
+; We can remove `%res = and i64 %p, 255`, because %r = 0 and we can eliminate
+; %p as well.
+define i64 @constant_and_undef(i1 %c1, i64 %a) {
+; CHECK-LABEL: @constant_and_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 0
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Check that we go to overdefined when merging a constant range with undef. We
+; cannot remove '%res = and i64 %p, 255'.
+define i64 @constant_range_and_undef(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Same as @constant_range_and_undef, with the undef coming from the other
+; block.
+define i64 @constant_range_and_undef_switched_incoming(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_switched_incoming(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ undef, [[BB2]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb2:
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %r, %bb1 ], [ undef, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+define i1 @constant_range_and_255_100(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_255_100(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R_1:%.*]] = and i64 [[A:%.*]], 100
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[R_2:%.*]] = and i64 [[A]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R_1]], [[BB1]] ], [ [[R_2]], [[BB2]] ]
+; CHECK-NEXT:    [[P_AND:%.*]] = and i64 [[P]], 512
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  %r.1 = and i64 %a, 100
+  br label %bb3
+
+bb2:
+  %r.2 = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %r.1, %bb1 ], [ %r.2, %bb2 ]
+  %p.and = and i64 %p, 512
+  %c = icmp ult i64 %p.and, 256
+  ret i1 %c
+}
+
+
+define i64 @constant_range_and_undef2(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[V1:%.*]] = add i64 undef, undef
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[V2:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[V1]], [[BB1]] ], [ [[V2]], [[BB2]] ]
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB4:%.*]], label [[BB5:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[BB6:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[V3:%.*]] = and i64 [[A]], 255
+; CHECK-NEXT:    br label [[BB6]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[P2:%.*]] = phi i64 [ [[P]], [[BB4]] ], [ [[V3]], [[BB5]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P2]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %v1 = add i64 undef, undef
+  br label %bb3
+
+bb2:
+  %v2 = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %v1, %bb1 ], [ %v2, %bb2 ]
+  br i1 %c2, label %bb4, label %bb5
+
+bb4:
+  br label %bb6
+
+bb5:
+  %v3 = and i64 %a, 255
+  br label %bb6
+
+bb6:
+  %p2 = phi i64 [ %p, %bb4 ], [ %v3, %bb5 ]
+  %res = and i64 %p2, 255
+  ret i64 %res
+}
+
+define i1 @constant_range_and_undef_3(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ]
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %c = icmp ult i64 %p, 256
+  ret i1 %c
+}
+
+define i1 @constant_range_and_undef_3_switched_incoming(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_switched_incoming(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ undef, [[BB2]] ]
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb2:
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %r, %bb1 ], [ undef, %bb2 ]
+  %c = icmp ult i64 %p, 256
+  ret i1 %c
+}