This is an archive of the discontinued LLVM Phabricator instance.

[AArch64][GlobalISel] Select G_UADDE/G_SADDE/G_USUBE/G_SSUBE
ClosedPublic

Authored by tobias-stadler on Jun 16 2023, 12:54 PM.

Details

Summary

This implements the remaining overflow generating instructions in the AArch64 GlobalISel selector.
Now wide add/sub operations do not fallback to SelectionDAG anymore.
We make use of PostSelectOptimize to cleanup the hereby generated flag-setting operations when the carry-out is unused.
Since we do not fallback anymore when selecting add/sub atomics on O0 some test changes were required there.

Fixes: https://github.com/llvm/llvm-project/issues/59407

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptJun 16 2023, 12:54 PM
tobias-stadler requested review of this revision.Jun 16 2023, 12:54 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 16 2023, 12:54 PM
arsenm added inline comments.Jun 16 2023, 3:19 PM
llvm/lib/Target/AArch64/GISel/AArch64InstructionSelector.cpp
4820

Don't need null check

4876

I didn't even know hasAtMostUserInstrs existed, just use use_nodbg_empty

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

Address comments. Thanks.

tobias-stadler edited the summary of this revision. (Show Details)

Update commit summary to include fixed issue. Thanks.

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

We noticed this, because our application (database query compilation) makes frequent use of 128bit add/sub overflow intrinsics, which produced a significant amount of fallbacks when using GlobalISel. With this patch, we don't fallback anymore (at least from what we have tested so far).
The G_*E operations were marked as legal by https://reviews.llvm.org/D95325, but there was no selector implementation provided at that time.

aemerson added inline comments.Jun 20 2023, 10:53 AM
llvm/lib/Target/AArch64/GISel/AArch64InstructionSelector.cpp
4566

MachineIRBuilder has getMRI().

4798–4799

Since we only have 2 mutually exclusive choices, I'd just use something like bool IsSub = false. Then simplify below to:

if (Opcode == TargetOpcode::G_SSUBE || Opcode == TargetOpcode::G_USUBE)
  IsSub = true;

NegateCarry then is also redundant since it's only set when IsSub = true

4848–4867

This code looks pretty verbose. How about we add some new helper classes to GenericMachineInstrs.h so we have something like GBinOpCarryOut, GBinOpCarryIn. We could then eliminate this switch and replace with something like:

assert(isa<GBinOpCarryOut>(I) || isa<GBinOpCarryIn>(I));

if (auto *InMI = dyn_cast<GBinOpCarryIn>(&I)) {
  // Set NZCV carry according to carry-in VReg
  emitCarryIn(I, InMI->getCarryReg());
}

this way we also avoid hard coding an operand index.

tobias-stadler updated this revision to Diff 533289.EditedJun 21 2023, 9:03 AM

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.

Minor cleanup in PostSelectOptimize and added missed *Wrs variants of instructions.

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.

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.

As far as my patch is concerned: CarryIn/CarryOut is consistent with the terminology used in MachineIRBuilder, the docs and other places I have seen, so I'd prefer to keep it this way.

As far as my patch is concerned: CarryIn/CarryOut is consistent with the terminology used in MachineIRBuilder, the docs and other places I have seen, so I'd prefer to keep it this way.

Sure, I just wanted to identify the (bigger) issue.

aemerson accepted this revision.Jun 23 2023, 1:33 PM

LGTM. Thanks for the nice improvements.

This revision is now accepted and ready to land.Jun 23 2023, 1:33 PM
tobias-stadler added a comment.EditedJun 23 2023, 2:19 PM

LGTM. Thanks for the nice improvements.

Thanks for the review. This is my first patch, so I don't have commit access. Could you land this for me, please?
Looks like I accidentally created the commit using the github no-reply mail. Please use this author information:

Tobias Stadler <mail@stadler-tobias.de>
This revision was automatically updated to reflect the committed changes.