This is an archive of the discontinued LLVM Phabricator instance.

[Machine Combiner] Refactor machine reassociation into a target-independent pass
ClosedPublic

Authored by haicheng on Sep 15 2015, 12:11 PM.

Details

Summary

This patch refactors the machine reassociation pass into a target-independent pass. The only pass used by x86 now is this reassociation pass, not the machine combiner pass. There is no functional change in this patch. No change is found in the x86 assembly when complied with llvm-test-suite and spec2006.

This change address PR24522.

Diff Detail

Repository
rL LLVM

Event Timeline

haicheng updated this revision to Diff 34820.Sep 15 2015, 12:11 PM
haicheng retitled this revision from to [Machine Combiner] Refactor machine reassociation into a target-independent pass.
haicheng updated this object.
haicheng added reviewers: spatel, jmolloy.
haicheng set the repository for this revision to rL LLVM.

The intent of this patch is to remove the redundant code from the PPC backend and to expose the generic parts so that other backends (e.g., AArch64) can use this machinery. I've added Hal to assist/comment on the PPC changes, if he's interested.

I support refactoring the reassociation code to be target-independent, but I'm wondering: what is the benefit from making this a separate pass from MachineCombiner?

If I'm seeing it correctly, this patch has exactly duplicated a few hundred lines of code for MachineReassociation::reassociateInstructions() and its helpers from the existing pass.

Thank you for your quick response, Sanjay.

This patch is trivial. As the next step, we will add the reassociation pass to other targets such as aarch64. In that case, aarch64 needs to run both reassociation and machine-combiner pass. We separate these two passes because of two reasons.

  1. The machine-combiner pass searches and combines a pair of instructions (mul & add/sub), but the reassociation pass may optimize on a long chain of instructions. They may need different optimizations in the future (e.g. compilation time optimization).
  1. If a target needs to run both passes, it may need different pattern enums. It might be ugly to put them in the same pass.

Please let us know your opinion.

  1. The machine-combiner pass searches and combines a pair of instructions (mul & add/sub), but the reassociation pass may optimize on a long chain of instructions. They may need different optimizations in the future (e.g. compilation time optimization).
  1. If a target needs to run both passes, it may need different pattern enums. It might be ugly to put them in the same pass.

Both of these are hypothetical problems that don't exist today. If these problems arise in practice, then certainly we could create a new pass to deal with them, but that should be a separate step IMO.

For this patch, I think we should just be refactoring the reassociation functions to live in MachineCombiner. That way, we eliminate the duplicated code from the x86 + PPC backends without duplicating all of the code that's already in MachineCombiner.

Gerolf edited edge metadata.Sep 16 2015, 10:19 AM
Gerolf added a subscriber: Gerolf.

+1

haicheng updated this revision to Diff 35009.Sep 17 2015, 9:28 AM
haicheng edited edge metadata.

Thank you, Sanjay and Gerolf.

This time I refactor into the machine combiner pass. Verified again with llvm-test-suite and spec2006 that there is no functional change.

Thank you, Sanjay and Gerolf.

This time I refactor into the machine combiner pass. Verified again with llvm-test-suite and spec2006 that there is no functional change.

Thanks, Haicheng! This is much closer to what I imagined the refactoring would look like. :)

  1. I don't think we need to distinguish between useMachineCombiner and useMachineReassociation. The reassociation patterns are just a subset of the combiner patterns. You can move what you are currently calling getMachineReassociationPatterns and genAlterReassocCodeSequence into the TargetInstrInfo base class implementations of getMachineCombinerPatterns and genAlternativeCodeSequence. Then the target overrides for those functions can choose to call the base implementation or not. When it's time to turn on the reassociation optimization for AArch, you just add a call to the base implementation ahead of the target-specific code that's already there. This will allow you to remove the isReassociation variable and associated if-checks in combineInstructions.
  1. reassociateOps is still a bunch of target-independent duplicated code for PPC and x86. Can you pull that into MachineCombiner and make setSpecialOperandAttr a virtual function? It would only be overridden by x86 for now, but AArch might want to override that too.
haicheng updated this revision to Diff 35125.Sep 18 2015, 12:48 PM

Thank you for your detailed comments, Sanjay. I did as what you suggested. Please check.

LGTM.

lib/CodeGen/TargetInstrInfo.cpp
550 ↗(On Diff #35125)

There is a lot of duplication in the comments. You could define the rules for reassociation once and simply refer to it. You could think of formalizing them and use them as verifier when the actual transformation happens.

563 ↗(On Diff #35125)

It would be consistent with other functions if you pulled them out before the prototype.

spatel accepted this revision.Sep 18 2015, 2:32 PM
spatel edited edge metadata.

LGTM too. Just a few inline nits.

include/llvm/CodeGen/MachineCombinerPattern.h
35 ↗(On Diff #35125)

The comment should say that these are AArch64 patterns. It might even be worth making that explicit in the names like:
MC_AARCH64_MULADDW_OP1
but that can be a follow-on change since it will mean changing the AArch code.

include/llvm/Target/TargetInstrInfo.h
737

Extra line.

lib/CodeGen/TargetInstrInfo.cpp
630 ↗(On Diff #35125)

I'm biased of course, but I think it's easier to understand the logic when the rows of the array are actually on different rows in the source.

This revision is now accepted and ready to land.Sep 18 2015, 2:32 PM
spatel added inline comments.Sep 18 2015, 2:42 PM
include/llvm/CodeGen/MachineCombinerPattern.h
36–48 ↗(On Diff #35125)

Forgot to mention: the AArch patterns should not specify an enum value directly. The reassociation patterns must specify a value from 0-3 because we use those values as indexes into an array (that's rather hacky, but changing it would be another follow-on commit).

haicheng updated this revision to Diff 35249.Sep 21 2015, 6:34 AM
haicheng edited edge metadata.

Fix the comments and other minor things. Thank you, everyone.

spatel closed this revision.Sep 22 2015, 9:56 AM

Marking review as closed; Chad committed this for Haicheng at r248164.

Marking review as closed; Chad committed this for Haicheng at r248164.

Thanks, Sanjay. I meant to ask Haicheng to do the same, but it slipped my mind.