Update logic as requested

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.

Rebase, ping?

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.

Rebase and ping.

Ping

Rebase and ping.

Ok, abandoning it as it doesn't seems to be necessary.

Is someone of a different opinion than @spatel ? If not, I'll abandon this patch soon.

@spatel I'm not sure, you tell me :) The history of this patch is that this pattern shows up in practice post legalization, so I submitted a patch for it for DAGCombiner. From there, @ lebedev.ri noticed that InstCombine wasn't doing it and suggested it to be added there as well.

Ping ?

• rebase
• Fix types
• Remove unnecessary use of auto
• Use a lambda

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

Update to reflect change in tests (the vector test had an incorrect constant in it).

Rebase and regenerate tests introduced in rL355400

In D58877#1416363, @RKSimon wrote:

Test for ((A + 1) + ~B) and ((~B + 1) + A) cases?

All the pattern I submit in DAGCombiner are extracted from actual code -in this case libraries doing cryptography). I never encountered the vector version of this but I'm happy to add test cases for them if this is of interest.

Add extra ops to ensure proper ordering.

I made the patch for InstCombine: D58877

It is interesting that instcombine doesn't do this. I would have expected it to be the case. Let me prepare a patch for it.

Rebase and add test cases taht do not depend on D57367

@niravd Any progress ?

rebase on top of rL353626

@RKSimon This can go now, but has no effect in isolation in any of the test cases I have, mainly because DAGCombine is fairly powerless when faced with addcarry as most of the work involve 'deep' patterns. Do you think I should land anyways ?

Ping ?

@RKSimon That sound reasonable. The main motivation for this patch is to fix a regression introduced by D57367 , so would that be possible to get at least a concept ack on it ?

Fix typos.
Rebase on top of D57367

I was thinking about ways to reduce the overhead created by this change. I came up with D57367, which is an alternative that focuses on nodes likely to benefit from the change instead of the whole DAG. It misses several opportunity that exist in that patch, but it seems to be a tradeof worth doing.

In D33587#1374792, @craig.topper wrote:

I don't see changes to addcarry.ll and subborrow.ll in this patch. So do we not have test cases from your workloads that show the benefit of this patch?

First about the kind of code I try to get to have better codegen, it's mostly about large integer manipulations. I already added a fair amount of reduced test cases in addcarry.ll/subcarry.ll . I'm at a stage where the pattern I have to work with are somewhat deep, see D57302 for an example. These patterns do not do anything useful if other transform cannot pick up from whee they left.

Add a comment about existing commutative ops deduplication logic.

Fix NewY's type which was invalid in some circustances

I get it now. We had a mismatched interpretation of which side is up, which side is down. If this is indeed the order in which nodes are processed, then it'd be beneficial to change this.

After thinking more about this, I do not think going bottom up is a good idea. All patterns match a node + its operands, and so benefit from operand to be combined themselves already. I do not think changing all the patterns to match use rather than operands is a good idea. This is a ton of work, and this is unclear there is any benefit at all.

I'm not sure how processing nodes bottom up really helps. Problems arise when you want to use patterns of depth > 2 because then direct parent.child are not processed again, even though such pattern may now be available. It seems to me that both top/down and bottom/up approaches would suffers from the same problem, but maybe there is something I'm missing.

I'd like to ressurect this diff.

@atanasyan The behavior is not supposed to change in any way, so test cases should not change. However, there are doubt about semantic for which there is no test case today.

Ping ?

Absolutely.

Ping ?

Revert changes in LanaiAluCode.h

The change in LanaiAluCode.h are indeed unrelated, let me remove them.