Rebase, fix tests, and rerun CI before relanding.

This was reverted due to an issue fixed by https://github.com/llvm/llvm-project/pull/68840 and should now be ready to reland.

Fix broken test.

Add suggested comment + Rebase.

@arsenm @aemerson Hi, do you have any further comments on this or are you ok with this change?

Rebase.

Gentle Ping.

In D159140#4628523, @aemerson wrote:

I see what you mean now. Is there any code size impact with optimizations (-Os or -O3)? I expect there to be none but just want to check.

In D159140#4627276, @aemerson wrote:

We only emit the mask G_CONSTANT when necessary. Even when the G_AND is combined away later, the constant sometimes ends up being reused by other instructions instead of becoming dead.

I'm a bit confused by how this could happen. Does this happen with optimizations?

The wording suggests that a later transform needs a G_AND, and probably the CSEMIRBuilder returns a reference to dead one? Why would other instructions need a dead instruction?

In D153164#4445206, @aemerson wrote:

LGTM. Thanks for the nice improvements.

In D153164#4440902, @barannikov88 wrote:

Register getCarryOutReg();

For subtraction this is actually a borrow-out. This naming can be confusing.
Has anyone though about deviating from SelectionDAG here and inverting the meaning of the flag for subtractions, so that it is actually a carry for both add/sub?
I understand that we can't just invert the meaning, because many clients (including downstream) rely on the current behavior.
So maybe via deprecation? UADDE/UADDO aren't good names anyway (I still can't figure out what do E and O letters mean).

(not related to this review)
I also had this idea about adding a variant of all ALU operations with status flags output (NZVC), and using this output in G_BRCOND_S/G_SELECT_S along with condition code to test (e.g. "overflow set, zero clear").
Carry-producing instructions could then be replaced by these more general instructions.
This allows eliminating G_ICMP in many cases (and actually make G_ICMP redundant because it could be replaced with G_SUB_S with status flags output).
For example if ((x & y) <= 0) could be translated into G_AND_S + G_BRCOND_S with "not positive" condition code (N == 0 || Z == 0), if the target has one.
I've implemented this as custom nodes in a downstream SelectionDAG as proof of concept. It works, but there are some subtleties, and it is somewhat machine dependent (e.g. RISC-V does not have status flags, as far as I know).

I'm not very familiar with GISel, nor I have time to try to implement this idea upstream, but maybe it will interest someone.

Address comments. Thanks for the suggestions. I think the ifs and switches cleaned up quite nicely using the new helper classes.
My original train of thought behind the switch in emitCarryIn was that if anyone wanted to add support for carry-in setting of other instructions they would have to explicitly add their instruction and think about if they needed a negated carry and could opt-in to the optimizations only if they wanted to. I can't think of any other usecase though, so emitting the carry as-is also seems like a sane default.

In D153164#4430170, @tschuett wrote:

How did you noticed the fallback?
They were marked as legal, but there was no support in instruction selection?

Update commit summary to include fixed issue. Thanks.

Address comments. Thanks.

I fixed these same issues here https://reviews.llvm.org/D153164 2 minutes earlier. I do generate better code though, because I generate less instructions for carry-in setting and optimize these instructions away whenever possible. For >O0 I generate identical code to SelectionDag. I also have higher test coverage.