[DAGCombiner] Do not generate ISD::ADDE node if adde is not legal for the target when combine ISD::TRUNC node

[• wuzish]

Summary

Do not combine (trunc adde(X, Y, Carry)) into (adde trunc(X), trunc(Y), Carry),
if adde is not legal for the target. Even it's at type-legalize phase.
Because adde is special and will not be legalized at operation-legalize phase later.

This fixes: PR40922
https://bugs.llvm.org/show_bug.cgi?id=40922

[efriedma]

ADDC etc. are deprecated in favor of ADDCARRY. Nothing should generate ADDC etc. unless they're marked "Legal" for the type in question... and they should be Expand by default.

Could you look into where the node in question is getting generated?

[• wuzish]

In D60854#1471842, @efriedma wrote:

ADDC etc. are deprecated in favor of ADDCARRY. Nothing should generate ADDC etc. unless they're marked "Legal" for the type in question... and they should be Expand by default.

Could you look into where the node in question is getting generated?

Yes, they are marked "Legal" in Power target.

t43: i32,glue = addc t42, Constant:i32<6>

      t13: ch = CopyToReg t0, Register:i32 %0, t11
    t27: ch = TokenFactor t13, t11:1
          t44: i32,glue = adde Constant:i32<0>, Constant:i32<0>, t43:1
        t46: i32 = and t44, Constant:i32<1>
      t50: i1 = setcc t46, Constant:i32<0>, seteq:ch
        t45: i32 = and t43, Constant:i32<-17>
      t47: i1 = setcc t45, t42, setuge:ch
    t51: i1 = select t50, t47, Constant:i1<-1>
  t34: ch = brcond t27, t51, BasicBlock:ch<if.end 0x1001ba242e8>
t31: ch = br t34, BasicBlock:ch<if.then 0x1001ba24220>

-->

t43: i32,glue = addc t42, Constant:i32<6>
      t13: ch = CopyToReg t0, Register:i32 %0, t11
    t27: ch = TokenFactor t13, t11:1
      t58: i1,glue = adde Constant:i1<0>, Constant:i1<0>, t43:1
        t45: i32 = and t43, Constant:i32<-17>
      t47: i1 = setcc t45, t42, setuge:ch
    t53: i1 = or t58, t47
  t34: ch = brcond t27, t53, BasicBlock:ch<if.end 0x1001ba242e8>
t31: ch = br t34, BasicBlock:ch<if.then 0x1001ba24220>

It was created with sequences of combining.

Combining: t51: i1 = select t50, t47, Constant:i1<-1>
Creating new node: t52: i1 = xor t50, Constant:i1<-1>
Creating new node: t53: i1 = or t52, t47
... into: t53: i1 = or t52, t47

Combining: t53: i1 = or t52, t47

Combining: t52: i1 = xor t50, Constant:i1<-1>
Creating new node: t55: i1 = setcc t46, Constant:i32<0>, setne:ch
... into: t55: i1 = setcc t46, Constant:i32<0>, setne:ch

Combining: t53: i1 = or t55, t47

Combining: t55: i1 = setcc t46, Constant:i32<0>, setne:ch
Creating new node: t56: i1 = truncate t46
... into: t56: i1 = truncate t46

Combining: t53: i1 = or t56, t47

Replacing.2 t46: i32 = and t44, Constant:i32<1>

With: t44: i32,glue = adde Constant:i32<0>, Constant:i32<0>, t43:1

Combining: t53: i1 = or t56, t47

Combining: t56: i1 = truncate t44
Creating constant: t57: i1 = Constant<0>
Creating new node: t58: i1,glue = adde Constant:i1<0>, Constant:i1<0>, t43:1
... into: t58: i1,glue = adde Constant:i1<0>, Constant:i1<0>, t43:1

[efriedma]

Oh, I see, we start with an i32 ADDE, then https://github.com/llvm/llvm-project/blob/e7fe6dd5edb828e702d02c7cdc6565ace4c84f5b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp#L10232 narrows the operation. We probably shouldn't perform that transform if it would produce an illegal ADDE.

[• wuzish]

In D60854#1472624, @efriedma wrote:

Oh, I see, we start with an i32 ADDE, then https://github.com/llvm/llvm-project/blob/e7fe6dd5edb828e702d02c7cdc6565ace4c84f5b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp#L10232 narrows the operation. We probably shouldn't perform that transform if it would produce an illegal ADDE.

if ((N0.getOpcode() == ISD::ADDE || N0.getOpcode() == ISD::ADDCARRY) &&

N0.hasOneUse() && !N0.getNode()->hasAnyUseOfValue(1) &&
(!LegalOperations || TLI.isOperationLegal(N0.getOpcode(), VT))) {

I think there are 2 conditions to combine as above code does. One is before operation legalization phase (!LegalOperations) and the other one is after.
In former condition, such transformation is acceptable even operation ADDE is illegal and it only cares about type legality because illegal operation will be legalized later in DAG legalization phase (as I want to promote it).
So the second condition does consider the legality of ADDE because it's after DAG operation legalization.

[efriedma]

In former condition, such transformation is acceptable even operation ADDE is illegal and it only cares about type legality because illegal operation will be legalized later in DAG legalization phase

Generally, yes, before operation legalization we can create illegal operations.

ADDE is sort of an exception, though; we don't have operation legalization support for it, and we don't want to add it. So the condition for the DAGCombine should be fixed.

[• wuzish]

In D60854#1472817, @efriedma wrote:

In former condition, such transformation is acceptable even operation ADDE is illegal and it only cares about type legality because illegal operation will be legalized later in DAG legalization phase

Generally, yes, before operation legalization we can create illegal operations.

ADDE is sort of an exception, though; we don't have operation legalization support for it, and we don't want to add it. So the condition for the DAGCombine should be fixed.

Yes, I found there is a TODO to support operation legalization as you said for ADDE. https://github.com/llvm/llvm-project/blob/e7fe6dd5edb828e702d02c7cdc6565ace4c84f5b/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp#L2049.

So the principle is that the DAG nodes converted from LLVM IR basically all have related common type and operation legalization (in base class), but the nodes only generated during combining and legalizing phases don't have fully support for common type and operation legalization. Instead, we just don't generate such nodes if targets do not support. Right?

Well, so the easiest way to fix this bug is to remove !LegalOperations before ||.

[efriedma]

so the easiest way to fix this bug is to remove !LegalOperations before ||

Essentially, yes, except we don't want to change the way we handle ADDCARRY.

[• wuzish]

If adde is not legal in target, do not combine to generate adde

[efriedma]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10225 ↗

(On Diff #196388)

Like I said before, we don't want to change the behavior of ADDCARRY. So should be something more like ((!LegalOperations && N0.getOpcode() == ISD::ADDCARRY) || TLI.isOperationLegal(N0.getOpcode(), VT))

[• wuzish]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10225 ↗

(On Diff #196388)

OK, I see.

[efriedma]

LGTM

[efriedma]

llvm/test/CodeGen/PowerPC/pr40922.ll

2

Err, sorry, I didn't read the test carefully enough.

Please use FileCheck to add some CHECK lines; even though the original issue was just a crash, adding a few lines to check for the expected addc or whatever might catch other issues in the future.

[• wuzish]

complete testcase

[• wuzish]

@eli.friedman Could you please have a look again? :) Thanks a lot.

[efriedma]

LGTM

[• wuzish]

update diff since it's out-of-date.

[• wuzish]

https://reviews.llvm.org/rL359532
https://reviews.llvm.org/rG49d60fdc2e8e

llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

if (Node->getOpcode() == ISD::CTLZ ||
         Node->getOpcode() == ISD::CTLZ_ZERO_UNDEF) {
       // Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
       Tmp1 = DAG.getNode(ISD::SUB, dl, NVT, Tmp1,
                           DAG.getConstant(NVT.getSizeInBits() -
                                           OVT.getSizeInBits(), dl, NVT));
     }
     Results.push_back(DAG.getNode(ISD::TRUNCATE, dl, OVT, Tmp1));
     break;
+  case ISD::SUBC:
+  case ISD::SUBE:
+  case ISD::ADDC:
+  case ISD::ADDE: {
+    Tmp1 = DAG.getNode(ISD::SIGN_EXTEND, dl, NVT, Node->getOperand(0));
+    Tmp2 = DAG.getNode(ISD::SIGN_EXTEND, dl, NVT, Node->getOperand(1));
+
+    SmallVector<SDValue, 4> Ops = {Tmp1, Tmp2};
+    if (Node->getOpcode() == ISD::ADDE || Node->getOpcode() == ISD::SUBE)
+      Ops.push_back(Node->getOperand(2));
+
+    Tmp3 = DAG.getNode(Node->getOpcode(), dl, {NVT, MVT::Glue}, Ops);
+    SDValue Res = DAG.getNode(ISD::TRUNCATE, dl, {OVT, MVT::Glue},
+                              {Tmp3, Tmp3.getValue(1)});
+
+    Results.push_back(Res);
+    Results.push_back(Res.getValue(1));
+    break;
+  }
   case ISD::BITREVERSE:
   case ISD::BSWAP: {
     unsigned DiffBits = NVT.getSizeInBits() - OVT.getSizeInBits();
     Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, dl, NVT, Node->getOperand(0));
     Tmp1 = DAG.getNode(Node->getOpcode(), dl, NVT, Tmp1);
     Tmp1 = DAG.getNode(
         ISD::SRL, dl, NVT, Tmp1,
         DAG.getConstant(DiffBits, dl,

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

for (MVT VT : ScalarIntVTs) {
     setOperationAction(ISD::ADDE, VT, Legal);
     setOperationAction(ISD::SUBC, VT, Legal);
     setOperationAction(ISD::SUBE, VT, Legal);
   }
 
   if (Subtarget.useCRBits()) {
     setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i1, Expand);
 
+    setOperationAction(ISD::ADDC, MVT::i1, Promote);
+    AddPromotedToType(ISD::ADDC, MVT::i1, isPPC64 ? MVT::i64 : MVT::i32);
+    setOperationAction(ISD::SUBC, MVT::i1, Promote);
+    AddPromotedToType(ISD::SUBC, MVT::i1, isPPC64 ? MVT::i64 : MVT::i32);
+
+    setOperationAction(ISD::ADDE, MVT::i1, Promote);
+    AddPromotedToType(ISD::ADDE, MVT::i1, isPPC64 ? MVT::i64 : MVT::i32);
+    setOperationAction(ISD::SUBE, MVT::i1, Promote);
+    AddPromotedToType(ISD::SUBE, MVT::i1, isPPC64 ? MVT::i64 : MVT::i32);
+
     if (isPPC64 || Subtarget.hasFPCVT()) {
       setOperationAction(ISD::SINT_TO_FP, MVT::i1, Promote);
       AddPromotedToType (ISD::SINT_TO_FP, MVT::i1,
                          isPPC64 ? MVT::i64 : MVT::i32);
       setOperationAction(ISD::UINT_TO_FP, MVT::i1, Promote);
       AddPromotedToType(ISD::UINT_TO_FP, MVT::i1,
                         isPPC64 ? MVT::i64 : MVT::i32);
     } else {

llvm/test/CodeGen/PowerPC/pr40922.ll

+; RUN: llc -verify-machineinstrs -mtriple=powerpc-unknown-linux-gnu < %s
+
+; Test case adapted from PR40922.
+
+@a.b = internal global i32 0, align 4
+
+define i32 @a() {
+entry:
+  %call = tail call i32 bitcast (i32 (...)* @d to i32 ()*)()
+  %0 = load i32, i32* @a.b, align 4
+  %conv = zext i32 %0 to i64
+  %add = add nuw nsw i64 %conv, 6
+  %and = and i64 %add, 8589934575
+  %cmp = icmp ult i64 %and, %conv
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %call3 = tail call i32 bitcast (i32 (...)* @e to i32 ()*)()
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %entry
+  store i32 %call, i32* @a.b, align 4
+  ret i32 undef
+}
+
+declare i32 @d(...)
+
+declare i32 @e(...)