This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombine] Combine composition of ADDC(ADDE)
AbandonedPublic

Authored by zvi on Jan 29 2017, 10:17 PM.

Details

Summary

fold (addc X, (adde Y, 0, Carry)) -> (adde X, Y, Carry)

One step towards improving pr31719

Diff Detail

Repository
rL LLVM

Event Timeline

zvi created this revision.Jan 29 2017, 10:17 PM
zvi added inline comments.Jan 29 2017, 10:23 PM
test/CodeGen/X86/mul-i1024.ll
4383 ↗(On Diff #86241)

FWIW, this file is 11 lines shorter

test/CodeGen/X86/mul-i512.ll
5 ↗(On Diff #86241)

FWIW, this file is 8 lines shorter

deadalnix added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1872

Is that important to check this has only one use ? I'd assume that having (adde Y, 0, Carry) + (adde X, Y, Carry) is still preferable to (addc X, (adde Y, 0, Carry)) as it break dependencies between instructions.

zvi added inline comments.Jan 30 2017, 1:18 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1872

That's a fair point, but here I am following the practice that is common in the DAG Combiner. If you search for "hasOneUse" or "isOnlyUserOf" you can see the conservative approach of avoiding increase in instruction count.
If you can provide a benchmark that can show this case is an exception, we can discuss the trade-off with data to guide us - and better do it in a follow-up patch.

RKSimon added inline comments.Jan 30 2017, 4:06 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1872

Are there any situations where the inner ADDE's carry flag will be used by something else?

zvi added inline comments.Jan 30 2017, 5:27 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1872

The carry's type is glue, so by definition it can have a single user, right?

deadalnix added inline comments.Feb 1 2017, 5:37 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1872

If you search for "hasOneUse" or "isOnlyUserOf" you can see the conservative approach of avoiding increase in instruction count.

I don't think this is a valid concern in that case. If the instruction has more than one use, you get 2 instructions before and 2 after. So I don't think this apply in that case.

However, I'm not sure about the glue. It may indeed be the case that it is expected that a glue is used only once (that would make sense). In which case maybe a adding comment is a good thing because if it is not obvious to us now, it won't be to some dude reading this in a few month without context.

zvi added inline comments.Feb 1 2017, 11:09 PM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1872

You can see for yourself the results of your suggestion by applying this patch and running 'make check-llvm'.
At least the tests 'mul-i1024.ll' and 'mul-i512.ll' will be affected by this change. You will see the instruction count will increase. Not saying this is necessarily undesirable, but it requires additional work of convincing ourselves that the larger code is faster.

deadalnix added inline comments.Feb 1 2017, 11:51 PM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1872

Alright, I think this is moot anyway. I'm not sure this transformation is valid if Y may be all ones. adde would generate a carry, but the addc would not, after the transformation, it would generate a carry.

deadalnix added inline comments.Feb 2 2017, 1:02 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1872

I suggest something like:

// (addc X, (adde Y, 0, Carry)) -> (adde X, Y, Carry) if Y + 1 cannot overflow.
if (N1.getOpcode() == ISD::ADDE &&
    N->isOnlyUserOf(N1.getValue(0).getNode()) &&
    isNullConstant(N1.getOperand(1))) {
  APInt YZero, YOne;
  DAG.computeKnownBits(N1.getOperand(0), YZero, YOne);
  if (YZero)
    return DAG.getNode(ISD::ADDE, SDLoc(N), N->getVTList(), N0,
                       N1->getOperand(0), N1->getOperand(2));
}
zvi added inline comments.Feb 2 2017, 6:15 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1872

Sorry, it would have been clearer if i wrote: ".. by applying this patch only without the condtion of '&&

N->isOnlyUserOf(N1.getValue(0).getNode())'
1872

Good catch. Thanks

deadalnix added inline comments.Feb 2 2017, 9:42 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
1872

For what it's worth, in the meantime, I did https://reviews.llvm.org/D29443 which solve the whole thing. This pattern is part of the solution.

Shall we close this one in favor of D29443 ?

zvi updated this revision to Diff 87147.Feb 5 2017, 7:33 AM

Following @deadalnix's suggestion for special case where Y is all ones. Thanks!

zvi added a comment.Feb 5 2017, 7:45 AM

Shall we close this one in favor of D29443 ?

I don't mind abandoning this patch in favor of D29443, but if possible, i think you should break D29443 into several patches. I'm saying this because D29443 adds several new combines and it would be easier to review each combine in a separate patch with tests that show its goodness.
So it may turn out that after breaking D29443, this patch will end-up as the initial patch in a sequence. Does this make sense?

I actually posted in that diff asking if I should do this, so yes, it does make sense.

zvi abandoned this revision.Feb 7 2017, 12:49 PM