[SelectionDAG] computeKnownBits / ComputeNumSignBits for the remaining overflow-aware nodes

[barannikov88]

Summary

Some overflow-aware nodes were missing from the switches in
computeKnownBits and ComputeNumSignBits.

[barannikov88]

Rebase

[bjope]

LGTM!

[barannikov88]

Rebase

[barannikov88]

This is my first patch. I would really appreciate it if someone could guide me through the process of contribution.
What do I do next once the patch is approved by the reviewers (e.g. is there a way I can merge it myself or will it be merged automatically / by some other person)? How many approvals do I need? Is there some kind of CODEOWNERS whose approve is mandatory?
I have read https://llvm.org/docs/Contributing.html but it does not answer all questions, so any additional information would be helpful.

[barannikov88]

It seems I don't have permission to land the patch. Could someone do this please?

I also see a build bot failure, but the error seems unrelated:
https://buildkite.com/llvm-project/premerge-checks/builds/101001#0181cec4-b429-490e-8703-f179f25541b2/6-12053

Failed Tests (1):
  BOLT :: runtime/X86/user-func-reorder.c

Is it OK or should I look into it?

[barannikov88]

Kindly ping

[foad]

In D129028#3630395, @barannikov88 wrote:

This is my first patch. I would really appreciate it if someone could guide me through the process of contribution.
What do I do next once the patch is approved by the reviewers (e.g. is there a way I can merge it myself or will it be merged automatically / by some other person)?

For your first few patches you can ask someone else to do it. Then you should apply for commit access.

How many approvals do I need?

Usually one approval is enough, unless some other reviewer is still unhappy with the patch.

Is there some kind of CODEOWNERS whose approve is mandatory?

No. There is an llvm CODE_OWNERS.TXT but the people listed there are supposed to be responsible for ensuring that patches to a particular part of the compiler get reviewed. They are not mandatory reviewers for every single patch themselves.

I have read https://llvm.org/docs/Contributing.html but it does not answer all questions, so any additional information would be helpful.

There are also other docs linked from https://llvm.org/docs/GettingInvolved.html like the Developer Policy and the Code-Review Policy.

In D129028#3630627, @barannikov88 wrote:

It seems I don't have permission to land the patch. Could someone do this please?

Yes I can do it. What is your preferred name and email address for the Author: header? (Or do you have an existing github account with some commits I can copy it from?)

I also see a build bot failure, but the error seems unrelated:
https://buildkite.com/llvm-project/premerge-checks/builds/101001#0181cec4-b429-490e-8703-f179f25541b2/6-12053

Failed Tests (1):
  BOLT :: runtime/X86/user-func-reorder.c

Is it OK or should I look into it?

If you're reasonably sure it's unrelated then I guess it's OK to ignore it. I'm not even sure how to run the BOLT tests. I don't think they are part of check-llvm.

[barannikov88]

There are also other docs linked from https://llvm.org/docs/GettingInvolved.html like the Developer Policy and the Code-Review Policy.

Thanks, that is a lot of information to get acquainted with

Yes I can do it. What is your preferred name and email address for the Author: header? (Or do you have an existing github account with some commits I can copy it from?)

Sergei Barannikov <[e-mail]>

For your first few patches you can ask someone else to do it. Then you should apply for commit access.

How can I apply for the access?

[foad]

In D129028#3636467, @barannikov88 wrote:

There are also other docs linked from https://llvm.org/docs/GettingInvolved.html like the Developer Policy and the Code-Review Policy.

Thanks, that is a lot of information to get acquainted with

Yes :-/

For your first few patches you can ask someone else to do it. Then you should apply for commit access.

How can I apply for the access?

https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access

[barannikov88]

In D129028#3638097, @foad wrote:

https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access

OK, I'll do it after submitting a few patches. Thank you for your time

[foad]

2247fdc84d74d267b7d82a4103aa60b28065f62a

I forgot to manually add the Differential Revision: header to the log message, sigh.

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

case ISD::UMULO:
     // We know that we have an integer-based boolean since these operations
     // are only available for integer.
     if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
             TargetLowering::ZeroOrOneBooleanContent &&
         BitWidth > 1)
       Known.Zero.setBitsFrom(1);
     break;
   case ISD::SETCC:
+  case ISD::SETCCCARRY:
   case ISD::STRICT_FSETCC:
   case ISD::STRICT_FSETCCS: {
     unsigned OpNo = Op->isStrictFPOpcode() ? 1 : 0;
     // If we know the result of a setcc has the top bits zero, use this info.
     if (TLI->getBooleanContents(Op.getOperand(OpNo).getValueType()) ==
             TargetLowering::ZeroOrOneBooleanContent &&
         BitWidth > 1)
       Known.Zero.setBitsFrom(1);
case ISD::AssertAlign: {
     break;
   }
   case ISD::FGETSIGN:
     // All bits are zero except the low bit.
     Known.Zero.setBitsFrom(1);
     break;
   case ISD::USUBO:
   case ISD::SSUBO:
+  case ISD::SUBCARRY:
+  case ISD::SSUBO_CARRY:
     if (Op.getResNo() == 1) {
       // If we know the result of a setcc has the top bits zero, use this info.
       if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
               TargetLowering::ZeroOrOneBooleanContent &&
           BitWidth > 1)
         Known.Zero.setBitsFrom(1);
       break;
     }
     LLVM_FALLTHROUGH;
   case ISD::SUB:
   case ISD::SUBC: {
     assert(Op.getResNo() == 0 &&
            "We only compute knownbits for the difference here.");
 
+    // TODO: Compute influence of the carry operand.
+    if (Opcode == ISD::SUBCARRY || Opcode == ISD::SSUBO_CARRY)
+      break;
+
     Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
     Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
     Known = KnownBits::computeForAddSub(/* Add */ false, /* NSW */ false,
                                         Known, Known2);
     break;
   }
   case ISD::UADDO:
   case ISD::SADDO:
   case ISD::ADDCARRY:
+  case ISD::SADDO_CARRY:
     if (Op.getResNo() == 1) {
       // If we know the result of a setcc has the top bits zero, use this info.
       if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
               TargetLowering::ZeroOrOneBooleanContent &&
           BitWidth > 1)
         Known.Zero.setBitsFrom(1);
       break;
     }
     LLVM_FALLTHROUGH;
   case ISD::ADD:
   case ISD::ADDC:
   case ISD::ADDE: {
     assert(Op.getResNo() == 0 && "We only compute knownbits for the sum here.");
 
     // With ADDE and ADDCARRY, a carry bit may be added in.
     KnownBits Carry(1);
     if (Opcode == ISD::ADDE)
       // Can't track carry from glue, set carry to unknown.
       Carry.resetAll();
-    else if (Opcode == ISD::ADDCARRY)
+    else if (Opcode == ISD::ADDCARRY || Opcode == ISD::SADDO_CARRY)
       // TODO: Compute known bits for the carry operand. Not sure if it is worth
       // the trouble (how often will we find a known carry bit). And I haven't
       // tested this very much yet, but something like this might work:
       //   Carry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
       //   Carry = Carry.zextOrTrunc(1, false);
       Carry.resetAll();
     else
       Carry.setAllZero();
unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, const APInt &DemandedElts,
   case ISD::UMAX:
     Tmp = ComputeNumSignBits(Op.getOperand(0), DemandedElts, Depth + 1);
     if (Tmp == 1)
       return 1;  // Early out.
     Tmp2 = ComputeNumSignBits(Op.getOperand(1), DemandedElts, Depth + 1);
     return std::min(Tmp, Tmp2);
   case ISD::SADDO:
   case ISD::UADDO:
+  case ISD::SADDO_CARRY:
+  case ISD::ADDCARRY:
   case ISD::SSUBO:
   case ISD::USUBO:
+  case ISD::SSUBO_CARRY:
+  case ISD::SUBCARRY:
   case ISD::SMULO:
   case ISD::UMULO:
     if (Op.getResNo() != 1)
       break;
     // The boolean result conforms to getBooleanContents.  Fall through.
     // If setcc returns 0/-1, all bits are sign bits.
     // We know that we have an integer-based boolean since these operations
     // are only available for integer.
     if (TLI->getBooleanContents(VT.isVector(), false) ==
         TargetLowering::ZeroOrNegativeOneBooleanContent)
       return VTBits;
     break;
   case ISD::SETCC:
+  case ISD::SETCCCARRY:
   case ISD::STRICT_FSETCC:
   case ISD::STRICT_FSETCCS: {
     unsigned OpNo = Op->isStrictFPOpcode() ? 1 : 0;
     // If setcc returns 0/-1, all bits are sign bits.
     if (TLI->getBooleanContents(Op.getOperand(OpNo).getValueType()) ==
         TargetLowering::ZeroOrNegativeOneBooleanContent)
       return VTBits;
     break;

llvm/test/CodeGen/AArch64/i256-math.ll

; CHECK-NEXT:    ret
   ret i256 %1
 }
 
 define { i256, i8 } @u256_checked_sub(i256 %x, i256 %y) {
 ; CHECK-LABEL: u256_checked_sub:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    subs x0, x0, x4
 ; CHECK-NEXT:    sbcs x1, x1, x5
-; CHECK-NEXT:    cset w8, lo
-; CHECK-NEXT:    cmp wzr, w8
 ; CHECK-NEXT:    sbcs x2, x2, x6
-; CHECK-NEXT:    cset w8, lo
-; CHECK-NEXT:    cmp wzr, w8
 ; CHECK-NEXT:    sbcs x3, x3, x7
 ; CHECK-NEXT:    cset w8, lo
 ; CHECK-NEXT:    eor w4, w8, #0x1
 ; CHECK-NEXT:    ret
   %1 = tail call { i256, i1 } @llvm.usub.with.overflow.i256(i256 %x, i256 %y)
   %2 = extractvalue { i256, i1 } %1, 0
   %3 = extractvalue { i256, i1 } %1, 1
   %4 = xor i1 %3, true
   %5 = zext i1 %4 to i8
   %6 = insertvalue { i256, i8 } undef, i256 %2, 0
   %7 = insertvalue { i256, i8 } %6, i8 %5, 1
   ret { i256, i8 } %7
 }
 
 define { i256, i8 } @u256_overflowing_sub(i256 %x, i256 %y) {
 ; CHECK-LABEL: u256_overflowing_sub:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    subs x0, x0, x4
 ; CHECK-NEXT:    sbcs x1, x1, x5
-; CHECK-NEXT:    cset w8, lo
-; CHECK-NEXT:    cmp wzr, w8
 ; CHECK-NEXT:    sbcs x2, x2, x6
-; CHECK-NEXT:    cset w8, lo
-; CHECK-NEXT:    cmp wzr, w8
 ; CHECK-NEXT:    sbcs x3, x3, x7
 ; CHECK-NEXT:    cset w4, lo
 ; CHECK-NEXT:    ret
   %1 = tail call { i256, i1 } @llvm.usub.with.overflow.i256(i256 %x, i256 %y)
   %2 = extractvalue { i256, i1 } %1, 0
   %3 = extractvalue { i256, i1 } %1, 1
   %4 = zext i1 %3 to i8
   %5 = insertvalue { i256, i8 } undef, i256 %2, 0
; CHECK-NEXT:    ret
   ret i256 %1
 }
 
 define { i256, i8 } @i256_checked_sub(i256 %x, i256 %y) {
 ; CHECK-LABEL: i256_checked_sub:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    subs x0, x0, x4
 ; CHECK-NEXT:    sbcs x1, x1, x5
-; CHECK-NEXT:    cset w8, lo
-; CHECK-NEXT:    cmp wzr, w8
 ; CHECK-NEXT:    sbcs x2, x2, x6
-; CHECK-NEXT:    cset w8, lo
-; CHECK-NEXT:    cmp wzr, w8
 ; CHECK-NEXT:    sbcs x3, x3, x7
 ; CHECK-NEXT:    cset w8, vs
 ; CHECK-NEXT:    eor w4, w8, #0x1
 ; CHECK-NEXT:    ret
   %1 = tail call { i256, i1 } @llvm.ssub.with.overflow.i256(i256 %x, i256 %y)
   %2 = extractvalue { i256, i1 } %1, 0
   %3 = extractvalue { i256, i1 } %1, 1
   %4 = xor i1 %3, true
   %5 = zext i1 %4 to i8
   %6 = insertvalue { i256, i8 } undef, i256 %2, 0
   %7 = insertvalue { i256, i8 } %6, i8 %5, 1
   ret { i256, i8 } %7
 }
 
 define { i256, i8 } @i256_overflowing_sub(i256 %x, i256 %y) {
 ; CHECK-LABEL: i256_overflowing_sub:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    subs x0, x0, x4
 ; CHECK-NEXT:    sbcs x1, x1, x5
-; CHECK-NEXT:    cset w8, lo
-; CHECK-NEXT:    cmp wzr, w8
 ; CHECK-NEXT:    sbcs x2, x2, x6
-; CHECK-NEXT:    cset w8, lo
-; CHECK-NEXT:    cmp wzr, w8
 ; CHECK-NEXT:    sbcs x3, x3, x7
 ; CHECK-NEXT:    cset w4, vs
 ; CHECK-NEXT:    ret
   %1 = tail call { i256, i1 } @llvm.ssub.with.overflow.i256(i256 %x, i256 %y)
   %2 = extractvalue { i256, i1 } %1, 0
   %3 = extractvalue { i256, i1 } %1, 1
   %4 = zext i1 %3 to i8
   %5 = insertvalue { i256, i8 } undef, i256 %2, 0

llvm/test/CodeGen/M68k/Control/cmp.ll

 ; CHECK-NEXT:    movem.l %d2, (0,%sp) ; 8-byte Folded Spill
 ; CHECK-NEXT:    move.l (8,%sp), %d1
 ; CHECK-NEXT:    move.l #0, %d0
 ; CHECK-NEXT:    move.l (12,%sp), %d2
 ; CHECK-NEXT:    sub.l #1, %d2
 ; CHECK-NEXT:    subx.l %d0, %d1
 ; CHECK-NEXT:    slt %d1
 ; CHECK-NEXT:    and.l #255, %d1
-; CHECK-NEXT:    and.l #1, %d1
 ; CHECK-NEXT:    movem.l (0,%sp), %d2 ; 8-byte Folded Reload
 ; CHECK-NEXT:    adda.l #4, %sp
 ; CHECK-NEXT:    rts
   %t = icmp slt i64 %x, 1
   %r = zext i1 %t to i64
   ret i64 %r
 }
 

llvm/test/CodeGen/M68k/Control/setcc.ll

 ; CHECK-NEXT:    suba.l #4, %sp
 ; CHECK-NEXT:    movem.l %d2, (0,%sp) ; 8-byte Folded Spill
 ; CHECK-NEXT:    move.l #0, %d2
 ; CHECK-NEXT:    sub.l #18, %d1
 ; CHECK-NEXT:    subx.l %d2, %d0
 ; CHECK-NEXT:    scs %d0
 ; CHECK-NEXT:    move.l %d0, %d1
 ; CHECK-NEXT:    and.l #255, %d1
-; CHECK-NEXT:    and.l #1, %d1
 ; CHECK-NEXT:    lsl.l #6, %d1
 ; CHECK-NEXT:    move.l %d2, %d0
 ; CHECK-NEXT:    movem.l (0,%sp), %d2 ; 8-byte Folded Reload
 ; CHECK-NEXT:    adda.l #4, %sp
 ; CHECK-NEXT:    rts
 entry:
   %0 = icmp ult i64 %x, 18                        ; <i1> [#uses=1]
   %iftmp.2.0 = select i1 %0, i64 64, i64 0        ; <i64> [#uses=1]