[ConstantRange] Use APInt::or/APInt::and for single elements.

[fhahn]

Summary

Currently ConstantRange::binaryAnd/binaryOr results are too pessimistic
for single element constant ranges.

If both operands are single element ranges, we can use APInt's AND and
OR implementations directly.

Note that some other binary operations on constant ranges can cover the
single element cases naturally, but for OR and AND this unfortunately is
not the case.

[lebedev.ri]

SGTM

[spatel]

LGTM as well.

[nikic]

I'd like to see a unit test that exhaustively tests this for all binary operators (or the ones where it holds). I don't think single element ranges are handled accurately for all the ops (e.g. probably not for urem/srem?)

[fhahn]

In D76446#1932013, @nikic wrote:

I'd like to see a unit test that exhaustively tests this for all binary operators (or the ones where it holds). I don't think single element ranges are handled accurately for all the ops (e.g. probably not for urem/srem?)

Yes, ideally we would handle all single element ranges in ConstantRange::binaryOp directly, by delegating to APInt, rather than doing it separately for each one I think. Maybe we should add an APInt::binaryOp? Or just dispatch in ConstantRange::binaryOp?

[nikic]

In D76446#1932076, @fhahn wrote:

In D76446#1932013, @nikic wrote:

I'd like to see a unit test that exhaustively tests this for all binary operators (or the ones where it holds). I don't think single element ranges are handled accurately for all the ops (e.g. probably not for urem/srem?)

Yes, ideally we would handle all single element ranges in ConstantRange::binaryOp directly, by delegating to APInt, rather than doing it separately for each one I think. Maybe we should add an APInt::binaryOp?

I don't think that's possible due to layering. APInt is in Support, so it can't depend on IR.

Or just dispatch in ConstantRange::binaryOp?

We probably don't want to make binaryOp() more powerful than the individual methods, so I think your current approach is already fine.

[fhahn]

In D76446#1932412, @nikic wrote:

In D76446#1932076, @fhahn wrote:

In D76446#1932013, @nikic wrote:

I'd like to see a unit test that exhaustively tests this for all binary operators (or the ones where it holds). I don't think single element ranges are handled accurately for all the ops (e.g. probably not for urem/srem?)

Yes, ideally we would handle all single element ranges in ConstantRange::binaryOp directly, by delegating to APInt, rather than doing it separately for each one I think. Maybe we should add an APInt::binaryOp?

I don't think that's possible due to layering. APInt is in Support, so it can't depend on IR.

Or just dispatch in ConstantRange::binaryOp?

We probably don't want to make binaryOp() more powerful than the individual methods, so I think your current approach is already fine.

Agreed! I'll go ahead and commit this as is for now. Happy to iterate on this post-commit as well

llvm/lib/IR/ConstantRange.cpp

ConstantRange ConstantRange::srem(const ConstantRange &RHS) const {
   return ConstantRange(std::move(Lower), std::move(Upper));
 }
 
 ConstantRange
 ConstantRange::binaryAnd(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();
 
+  // Use APInt's implementation of AND for single element ranges.
+  if (isSingleElement() && Other.isSingleElement())
+    return {*getSingleElement() & *Other.getSingleElement()};
+
   // TODO: replace this with something less conservative
 
   APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
   return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
 }
 
 ConstantRange
 ConstantRange::binaryOr(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();
 
+  // Use APInt's implementation of OR for single element ranges.
+  if (isSingleElement() && Other.isSingleElement())
+    return {*getSingleElement() | *Other.getSingleElement()};
+
   // TODO: replace this with something less conservative
 
   APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
   return getNonEmpty(std::move(umax), APInt::getNullValue(getBitWidth()));
 }
 
 ConstantRange ConstantRange::binaryXor(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())

llvm/test/Transforms/Attributor/range.ll

 ; CHECK-NEXT:    ret i32 [[S]]
 ;
   %s = select i1 %c, i32 1, i32 2
   ret i32 %s
 }
 define i1 @callee_range_1(i1 %c1, i1 %c2, i1 %c3) {
 ; OLD_PM-LABEL: define {{[^@]+}}@callee_range_1
 ; OLD_PM-SAME: (i1 [[C1:%.*]], i1 [[C2:%.*]], i1 [[C3:%.*]])
-; OLD_PM-NEXT:    [[F:%.*]] = and i1 true, true
-; OLD_PM-NEXT:    ret i1 [[F]]
+; OLD_PM-NEXT:    ret i1 true
 ;
 ; NEW_PM-LABEL: define {{[^@]+}}@callee_range_1
 ; NEW_PM-SAME: (i1 [[C1:%.*]], i1 [[C2:%.*]], i1 [[C3:%.*]])
-; NEW_PM-NEXT:    [[F:%.*]] = and i1 true, true
-; NEW_PM-NEXT:    ret i1 [[F]]
+; NEW_PM-NEXT:    ret i1 true
 ;
 ; CGSCC_OLD_PM-LABEL: define {{[^@]+}}@callee_range_1
 ; CGSCC_OLD_PM-SAME: (i1 [[C1:%.*]], i1 [[C2:%.*]], i1 [[C3:%.*]])
 ; CGSCC_OLD_PM-NEXT:    [[R1:%.*]] = call i32 @ret1or2(i1 [[C1]])
 ; CGSCC_OLD_PM-NEXT:    [[R2:%.*]] = call i32 @ret1or2(i1 [[C2]])
 ; CGSCC_OLD_PM-NEXT:    [[INDIRECTION:%.*]] = select i1 [[C3]], i32 [[R1]], i32 [[R2]]
 ; CGSCC_OLD_PM-NEXT:    [[A:%.*]] = add i32 [[R1]], [[INDIRECTION]]
 ; CGSCC_OLD_PM-NEXT:    [[I1:%.*]] = icmp sle i32 [[A]], 4

llvm/test/Transforms/CorrelatedValuePropagation/range.ll

 
 define i1 @test14_slt(i32 %a) {
 ; CHECK-LABEL: @test14_slt(
 ; CHECK-NEXT:    [[A_OFF:%.*]] = add i32 [[A:%.*]], -8
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[A_OFF]], 8
 ; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[RESULT:%.*]] = or i1 false, false
-; CHECK-NEXT:    ret i1 [[RESULT]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 false
 ;
   %a.off = add i32 %a, -8
   %cmp = icmp slt i32 %a.off, 8
   br i1 %cmp, label %then, label %else
 
 then:

 
 define i1 @test14_sgt(i32 %a) {
 ; CHECK-LABEL: @test14_sgt(
 ; CHECK-NEXT:    [[A_OFF:%.*]] = add i32 [[A:%.*]], -8
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[A_OFF]], 8
 ; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[RESULT:%.*]] = or i1 false, false
-; CHECK-NEXT:    ret i1 [[RESULT]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 false
 ;
   %a.off = add i32 %a, -8
   %cmp = icmp sgt i32 %a.off, 8
   br i1 %cmp, label %then, label %else
 
 then:

 
 define i1 @test14_ugt(i32 %a) {
 ; CHECK-LABEL: @test14_ugt(
 ; CHECK-NEXT:    [[A_OFF:%.*]] = add i32 [[A:%.*]], -8
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[A_OFF]], 8
 ; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[RESULT:%.*]] = or i1 false, false
-; CHECK-NEXT:    ret i1 [[RESULT]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 false
 ;
   %a.off = add i32 %a, -8
   %cmp = icmp ugt i32 %a.off, 8
   br i1 %cmp, label %then, label %else
 
 then:
then:
   %alive = icmp eq i32 %a, 16
   %result = or i1 %dead, %alive
   ret i1 %result
 
 else:
   ret i1 false
 }
 
+define i1 @test14_ugt_and(i32 %a) {
+; CHECK-LABEL: @test14_ugt_and(
+; CHECK-NEXT:    [[A_OFF:%.*]] = add i32 [[A:%.*]], -8
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[A_OFF]], 8
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[RESULT:%.*]] = and i1 false, false
+; CHECK-NEXT:    ret i1 false
+; CHECK:       else:
+; CHECK-NEXT:    ret i1 false
+;
+  %a.off = add i32 %a, -8
+  %cmp = icmp ugt i32 %a.off, 8
+  br i1 %cmp, label %then, label %else
+
+then:
+  %dead.1 = icmp eq i32 %a, 8
+  %dead.2 = icmp eq i32 %a, 16
+  %result = and i1 %dead.1, %dead.2
+  ret i1 %result
+
+else:
+  ret i1 false
+}
+
 @limit = external global i32
 define i1 @test15(i32 %a) {
 ; CHECK-LABEL: @test15(
 ; CHECK-NEXT:    [[LIMIT:%.*]] = load i32, i32* @limit, !range !4
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], [[LIMIT]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false