Page MenuHomePhabricator

[DAGCombine] More diamond carry pattern optimization.

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



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
2522 ↗(On Diff #183760)


2523 ↗(On Diff #183760)


2567 ↗(On Diff #183760)


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
2590 ↗(On Diff #190035)

ddamoni ? paternq?

2670 ↗(On Diff #190035)

Don't use auto

2675 ↗(On Diff #190035)

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

107 ↗(On Diff #190035)

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
107 ↗(On Diff #190035)

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


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.Jun 2 2019, 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?

2779 ↗(On Diff #202606)

nit: make the failing case here an else clause.

2812 ↗(On Diff #202606)

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.Jun 12 2019, 4:49 PM

Update logic as requested

deadalnix updated this revision to Diff 206757.Jun 26 2019, 3:33 PM

rebase and ping!

niravd accepted this revision.Jul 1 2019, 6:53 AM


This revision is now accepted and ready to land.Jul 1 2019, 6:53 AM
This revision was automatically updated to reflect the committed changes.