This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by wuzish on Apr 17 2019, 11:51 PM.

Details

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

Diff Detail

Event Timeline

wuzish created this revision.Apr 17 2019, 11:51 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 17 2019, 11:51 PM

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?

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

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.

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.

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.

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 ||.

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.

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

efriedma added inline comments.Apr 24 2019, 11:18 AM
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 marked 2 inline comments as done.Apr 24 2019, 7:55 PM
wuzish added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
10225 ↗(On Diff #196388)

OK, I see.

wuzish marked an inline comment as done.
This revision is now accepted and ready to land.Apr 25 2019, 12:36 PM
efriedma requested changes to this revision.Apr 25 2019, 12:37 PM
efriedma added inline comments.
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.

This revision now requires changes to proceed.Apr 25 2019, 12:37 PM
wuzish marked an inline comment as done.

complete testcase

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

This revision is now accepted and ready to land.Apr 29 2019, 12:29 PM

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

wuzish retitled this revision from [DAGLegalize][PowerPC] Add promote legalization of addc/adde and subc/sube to [DAGCombiner] Do not do transforming of (trunc adde(X, Y, Carry)) -> (adde trunc(X), trunc(Y), Carry) when adde is not legal for the target.Apr 29 2019, 7:53 PM
wuzish edited the summary of this revision. (Show Details)
wuzish retitled this revision from [DAGCombiner] Do not do transforming of (trunc adde(X, Y, Carry)) -> (adde trunc(X), trunc(Y), Carry) when adde is not legal for the target to [DAGCombiner] Do not generate ISD::ADDE node if adde is not legal for the target when combine ISD::TRUNC node.Apr 29 2019, 7:58 PM
wuzish edited the summary of this revision. (Show Details)