This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombine] Refactor common addcarry pattern.
ClosedPublic

Authored by deadalnix on May 2 2017, 10:14 AM.

Details

Summary

This pattern is no very useful per se, but it exposes optimization for toehr patterns that wouldn't kick in otherwize. It's very common and worth optimizing for.

Event Timeline

deadalnix created this revision.May 2 2017, 10:14 AM
deadalnix retitled this revision from [DAGCombine] Refacotr common addcarry pattern. to [DAGCombine] Refactor common addcarry pattern..May 2 2017, 1:06 PM
RKSimon added inline comments.May 4 2017, 2:21 PM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2224

This comment really isn't any use to explain what is happening here - it needs a much better explanation.

AFAICT you are saying that if (A+B) overflows then the carry can only occur in the second operand, else if (A+B) doesn't overflow it might occur in the third (carry) operand after the additional add? Can carries ever occur in both? e.g. Is addcarry/uaddo supposed to accept for i1/i2 types?

deadalnix added inline comments.May 5 2017, 6:38 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2224

That is the idea. If A + B overflows, then Y + [0 or 1] cannot overflow. As a result, you can combine the two carries into one by doing A + B + [0 or 1]. This holds true even for types like i1, however, addcarry are generated by the legalization code, so you shouldn't get i1 in there anyway.

This transform a diamond pattern into the carry chain into a linear carry chain, and then other existing optimizations can kick in.

deadalnix updated this revision to Diff 97951.May 5 2017, 7:00 AM

Change the comment to explain the transform with some ASCII art.

spatel added inline comments.May 5 2017, 7:38 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2230

I like the ascii art!

I'm still not very familiar with the carry ops, so I would've kept the formulas from the previous rev in here too. This is complicated enough that I think it's justified to have both.

But I have a question about this node: (addcarry 0, 0, *)
Can that be simplified to a cast instruction from bool to the VT of the addcarry?
If yes, if we add that simplification, will it break this pattern matching?

filcab added a subscriber: filcab.May 5 2017, 8:32 AM

You should probably also mention the PR number on the commit message.
Does this trigger often, btw?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2243

Shouldn't we allow both (addcarry *, 0, Z) and (addcarry 0, *, Z)?
Same for the final one, we could have X+0(+C) or 0+X(+C), no?

deadalnix added inline comments.May 5 2017, 9:37 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2230

I think you are correct. Let me do a patch with (addcarry 0, 0, X) to (extend/trunc X) and see where this goes.

2243

The method is called with argument in both order already. See line 2146 onward.

filcab added inline comments.May 5 2017, 10:00 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2243

Should take care of the final addcarry, yes. But it's still missing the one above (*+0+Z), no?

deadalnix added inline comments.May 5 2017, 10:11 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2230

So i played a bit with it, and as it turns out, it makes some things worse, other better. I still think this is useful, we just need to add a few patterns to get things back to normal after the fact, like promoting uaddo into addcarry when one of the parameter actually comes from a carry.

deadalnix added inline comments.May 5 2017, 10:17 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2243

Constants are canonicalized on the RHS so it's fine.

deadalnix updated this revision to Diff 98036.May 5 2017, 4:18 PM

Rebase on top of D32925

deadalnix updated this revision to Diff 98053.May 6 2017, 3:44 AM

Doing some refactoring to help the introduction of further diamond pattern simplification.

deadalnix updated this revision to Diff 100284.May 25 2017, 1:06 PM
deadalnix marked 2 inline comments as done.

Ping !

RKSimon accepted this revision.May 25 2017, 2:32 PM

@filcab suggested adding the PR number on the commit message title as well.

LGTM - couple of minors.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2240

Worth checking/asserting that CarryIn.getResNo() == 1 ?

This revision is now accepted and ready to land.May 25 2017, 2:32 PM
deadalnix added inline comments.May 28 2017, 8:11 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2240

Sounds like a good idea. i don't think we generate such a code ever, but better safe than sorry.

Check result count.

RKSimon accepted this revision.May 30 2017, 3:30 AM

Thanks, LGTM

This revision was automatically updated to reflect the committed changes.