This is an archive of the discontinued LLVM Phabricator instance.

[GISel] Add new combines for G_ADD
ClosedPublic

Authored by mkitzan on Sep 18 2020, 1:14 PM.

Details

Summary

Patch adds new GICombineRules for G_ADD:

  • G_ADD(x, G_SUB(y, x)) -> y
  • G_ADD(G_SUB(y, x), x) -> y

Patch additionally adds new combine tests for AArch64 target for these new rules.

Diff Detail

Event Timeline

mkitzan created this revision.Sep 18 2020, 1:14 PM
mkitzan requested review of this revision.Sep 18 2020, 1:14 PM

Out of curiosity, is the first rule a win or canonicalisation?

arsenm added inline comments.Sep 18 2020, 1:46 PM
llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h
415

APInt to allow it to work for wide integers?

llvm/test/CodeGen/AArch64/GlobalISel/combine-add.mir
86

Add an s128 case? This currently won't work for vectors, but it would be nice to handle a few vector tests too

llvm/test/CodeGen/AMDGPU/GlobalISel/extractelement.i128.ll
23–24 ↗(On Diff #292884)

I don't understand where this regression came from (but isn't particularly important)

54–62 ↗(On Diff #292884)

This is a much more interesting regression

mkitzan added a comment.EditedSep 18 2020, 2:57 PM

Out of curiosity, is the first rule a win or canonicalisation?

Primarily canonicalization, however depending on the target there can be perf wins. By eliminating the signed constant, there's a better chance the constant can be folded into the opcode as an immediate operand rather than being loaded into a register before being used (if the target supports immediate operands, otherwise nothing lost, eh?).

Assume hypothetical target only supports 2b immediate operands to arithmetic ops and registers are 8b. Here's an example where the combine is a perf win.

mov r1, -1
add r0, r1
---
sub r0, 1
llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h
415

Make sense, will add

llvm/test/CodeGen/AArch64/GlobalISel/combine-add.mir
86

Will add an s128 and a vector test case for each of these

llvm/test/CodeGen/AMDGPU/GlobalISel/extractelement.i128.ll
54–62 ↗(On Diff #292884)

I noticed regressions in this test file too. The combine causing them is the: G_ADD(x, y) -> G_OR(x, y) (iff x and y share no common bits). That combine rule is the cause of nearly all the AMDGPU test changes (with the exception of three or four tests).

arsenm added inline comments.Sep 18 2020, 4:10 PM
llvm/test/CodeGen/AMDGPU/GlobalISel/extractelement.i128.ll
54–62 ↗(On Diff #292884)

So we need the equivalent utility for SelectionDAG::isBaseWithConstantOffset(

mkitzan added inline comments.Sep 18 2020, 5:50 PM
llvm/test/CodeGen/AMDGPU/GlobalISel/extractelement.i128.ll
54–62 ↗(On Diff #292884)

Not quite sure where that fits into the implementation of the combine. The added GlobalISel/Utils.cpp:haveNoCommonBitsSet acts the same as SelectionDAG.pp:haveNoCommonBitsSet which is used to gate the DAG combine version (x + y) -> (x | y) iff x and y share no bits.

mkitzan updated this revision to Diff 292930.Sep 18 2020, 6:24 PM
  • Changed G_ADD(x, -cst) -> G_SUB(x, cst) to use APInt
  • Added vector and s128 test cases (though some combines don't fire with these input types)
arsenm added inline comments.Sep 25 2020, 1:29 PM
llvm/test/CodeGen/AMDGPU/GlobalISel/extractelement.i128.ll
54–62 ↗(On Diff #292884)

It's not for the combine itself, it's for all of the other code to deal with the side effect of it. In general this is a terrible combine because nobody expects adds to turn into ors. Without a utility function you can easily use to match adds that were turned into ors, I think it's generally worse to do this combine. I think having this utility function is a prerequisite for this

I can remove the G_ADD(x, y)->G_OR(x, y) combine if that's a blocker. Let me know if there's anything else specifically blocking the approval of this patch.

mkitzan updated this revision to Diff 430513.May 18 2022, 3:09 PM
mkitzan edited the summary of this revision. (Show Details)
mkitzan added reviewers: aemerson, foad.
mkitzan added subscribers: foad, aemerson.

Updates:

  • Rebased patch
  • Removed G_ADD(x, y) -> G_OR(x, y) combine
  • Exchanged my custom applyAddSubSameReg function for replaceSingleDefInstWithReg
  • Add @aemerson and @foad to reviewers list
Herald added a project: Restricted Project. · View Herald TranscriptMay 18 2022, 3:09 PM
Herald added a subscriber: kosarev. · View Herald Transcript

I do think the add -> or has some value, but it should be separate with the helper function

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
5638–5643

Probably should use m_match here (maybe even have a negative constant matcher)

mkitzan updated this revision to Diff 430529.May 18 2022, 4:23 PM

Good point about using mi_match, updated the diff.

Can work on the add -> or combine + helper function in a future patch. Better to not block committing the simpler combines.

foad added inline comments.May 19 2022, 1:01 AM
llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h
739

Does SelectionDAG do this? I suppose it can be useful to canonicalize, but my gut feeling is that it would be better to do the converse, i.e. canonicalize G_SUB(x, cst) -> G_ADD(x, -cst). That way you are canonicalizing on using G_ADD instead of G_SUB wherever possible, which feels more useful than using positive constants instead of negative constants wherever possible. E.g. if you're writing a pattern to match a "reg + simm" addressing mode you would only need to match G_ADD.

mkitzan added inline comments.May 19 2022, 10:50 AM
llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h
739

No, I can't seem to find it in DAGCombiner. Would you rather it be removed from the patch?

I think addressing modes are less of a factor given that g_ptr_add is separate

I think addressing modes are less of a factor given that g_ptr_add is separate

I guess this breaks down as soon as you have a 2 component mode

I'll remove that combine as well. If there's more discussion and it's found to be beneficial then I can open another revision for it.

mkitzan updated this revision to Diff 430764.May 19 2022, 11:49 AM
mkitzan edited the summary of this revision. (Show Details)

Updates:

paquette accepted this revision.Jun 6 2022, 9:25 AM

I think this looks reasonable now? I basically only have one nit.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
5644

FYI, in Register.h:

/// Wrapper class representing virtual and physical registers. Should be passed
/// by value.
class Register {
  unsigned Reg;

Since neither MaybeSub nor MaybeSameReg is being mutated, they might as well be passed by value.

This revision is now accepted and ready to land.Jun 6 2022, 9:25 AM

Thanks for the review @paquette. I'll update the diff addressing your nit when I push the patch

This revision was landed with ongoing or failed builds.Jun 6 2022, 11:19 AM
This revision was automatically updated to reflect the committed changes.