Page MenuHomePhabricator

[DAGCombine] More diamond carry pattern optimization.
Needs ReviewPublic

Authored by deadalnix on Jan 27 2019, 9:48 AM.

Details

Summary

This diff improve the capability of DAGCOmbine to generate linear carries propagation in presence of a diamond pattern. It is now able to match a large variety of different patterns rather than some hardcoded one.

Arguably, the codegen in test cases is not better, but this is to be expected. The goal of this transformation is more about canonicalisation than actual optimisation.

Diff Detail

Event Timeline

deadalnix created this revision.Jan 27 2019, 9:48 AM
deadalnix retitled this revision from [DAGCombine] More diamong carry pattern optimization. to [DAGCombine] More diamond carry pattern optimization..Jan 27 2019, 9:52 AM

Fix NewY's type which was invalid in some circustances

craig.topper added inline comments.Jan 28 2019, 4:56 PM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2798

usualy->usually

2799

linarized->linearized

2843

fnd->find

deadalnix updated this revision to Diff 184009.Jan 28 2019, 7:34 PM

Fix typos.
Rebase on top of D57367

deadalnix updated this revision to Diff 190035.Mar 10 2019, 6:28 PM

Remove dependency on D57367 as now it show improvement on existing test cases.

Herald added a project: Restricted Project. · View Herald TranscriptMar 10 2019, 6:28 PM
RKSimon added inline comments.Mar 11 2019, 3:14 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2794

ddamoni ? paternq?

2874

Don't use auto

2879

Instead of 'DoIt' - would it be better to move this into a lambda and just call it in each of the cases above?

test/CodeGen/X86/subcarry.ll
107

Whats your plan to deal with this regression?

deadalnix updated this revision to Diff 190081.Mar 11 2019, 6:56 AM
deadalnix marked an inline comment as done.
  • rebase
  • Fix types
  • Remove unnecessary use of auto
  • Use a lambda
deadalnix added inline comments.Mar 11 2019, 7:02 AM
test/CodeGen/X86/subcarry.ll
107

It may seems counter intuitive, but this is regression is maybe the main motivation behind that patch. The code previously had 2 carries propagation, and now it has one. This new form is not as good independently, but can be optimized.

See D57317 and D59208 for instance.

deadalnix updated this revision to Diff 193196.Apr 1 2019, 4:19 PM

Rebase and ping.

deadalnix updated this revision to Diff 198135.May 4 2019, 4:27 AM

Rebase and ping.

While I understand one may have doubts about this patch, it is absolutely key to push the quality of the canonicalisation of large interegers further. With a dual track for carry propapagtion, it is not possible to to do any better than we do now.

deadalnix updated this revision to Diff 200018.May 17 2019, 4:22 AM

Rebase.

This is important to be able to make the carry propagation path canonical to be able to optimise large ineteger computation further. I would really appreciate if tis could move forward as this is gating a lot of work.

deadalnix updated this revision to Diff 202606.Sun, Jun 2, 9:12 AM

Rebase, ping?

Should we have the corresponding subcarry case folded in here as well?

Also, do we have a test case where we're adding/subtracting 3 or more multi-register numbers?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2837

nit: make the failing case here an else clause.

2870

Remove the else for consistency.

Do you have a test case where diamond carries are generated for subs ? I'm happy to look into this, but I have no test case.

deadalnix updated this revision to Diff 204388.Wed, Jun 12, 4:49 PM

Update logic as requested