This is an archive of the discontinued LLVM Phabricator instance.

[CGP] Make optimizeMemoryInst capable of handling multiple AddrModes
ClosedPublic

Authored by john.brawn on Sep 26 2017, 6:46 AM.

Details

Summary

Currently optimizeMemoryInst requires that all of the AddrModes it sees are identical. This patch makes it capable of tracking multiple AddrModes, so long as they differ in at most one field.

This patch does nothing by itself, but later patches will make use of it to insert or reuse phi or select instructions for the differing fields.

Diff Detail

Event Timeline

skatkov added inline comments.Sep 27 2017, 2:14 AM
lib/CodeGen/CodeGenPrepare.cpp
4518

Can we move this to utility class with operation like diff? It will reduce the size of this method which is already big one.

4561

In reality you do not need iteration over found AddrModes. What you need here is just whether at least two AddrModes has different element.
So if Different* is true you do not need to compare this element more.

It actually means that you can always compare NewAddrMode against the first element of an array AddrMode.

Also I would put this functionality into utility class.

4612

I think it is not good that this bailout goes after debug message (three lines above) is printed.

reames requested changes to this revision.Sep 27 2017, 11:13 AM
reames added inline comments.
lib/CodeGen/CodeGenPrepare.cpp
4559–4560

If I understand your original patch correctly, you only support difference in one input across all AddrModes right?

If so, it might be better to track which fields is known to differ and reject eagerly any that differs in a different field. Using something like an Optional<FieldName> where FieldName is a enum might be a good representation.

Alternatively, this might make more sense as a post processing loop. (i.e. keep track of non-equal address modes in a set, then determine if all elements of the set are compatible.)

4561

We don't have the transform code yet to support this do we? If not, don't we need to remove this?

4563

From the comment, this really sounds like it's covering up a deficiency in the phi/select insertion logic. Would you mind leaving this case out for the moment or showing a test case where this is essential? In particular, Serguei's patch goes to lengths to try to reuse existing phi nodes.

When this is needed, this sounds like a function on AddressMode called isTrivial()

4566

For the moment, you only handle AddrMode.size() == 1. Just make that your exit condition here and remove the bailout below.

From this line, it looks like the trivial case might be a change in behaviour for the existing code. Is that so? If so, where's the test case for that?

4572

use empty()

This revision now requires changes to proceed.Sep 27 2017, 11:13 AM

p.s. Thanks for doing the work to split this out and being so responsive to review comments. Much appreciated!

skatkov added inline comments.Sep 27 2017, 9:15 PM
lib/CodeGen/CodeGenPrepare.cpp
4561

I consider this is as a preparation to implementation. For now we allow processing later but will bail out after that.

Not sure that Addr->hasOneUse is a correct check here...

What if we have two instruction which can fold Addr after our modification?

4563

I think it is about earlier bail out and compile time saving.

TrivialAddrMode actually means that if we found that all AddrModes are of the form only base reg or gv (no scale or offset) then later trying to find a common Phi node for, for example, base reg will end up with exactly the same Phi node we started from (addr). Yes my algorithm will detect it and will not create new Phi nodes but it will return the same Phi node addr. So all complex work in my patch is redundant.

This check just detect it in advance and bail out earlier.

I agree it should be moved to AddrMode class.

john.brawn edited edge metadata.

Updated based on review comments:

  • Move the field comparison into ExtAddrMode and use an enum to represent which field differs
  • Move trivial AddrMode detection into ExtAddrMode
  • Move everything else from optimizeMemoryInst into an AddressingModeCombiner class
skatkov added inline comments.Sep 28 2017, 8:13 PM
lib/CodeGen/CodeGenPrepare.cpp
2680

I cannot understand why you need a AddrModeUser. The only one use of this field I see is for checking that user of AddrMode is Phi or Select.

However according to usage of AddressingModeCombiner AddrModeUser cannot be anything else.

Do I miss anything?

3363

if AllAddrModesTrivial is false, you do not need to compute isTrivial. So you can re-write it as

AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();

Or alternatively:

if (AllAddrModesTrivial)
  AllAddrModesTrivial = NewAddrMode.isTrivial();
4559–4560

Redundant {}

john.brawn added inline comments.Oct 2 2017, 8:10 AM
lib/CodeGen/CodeGenPrepare.cpp
2680

It's there mostly for when we do actually want to do the transform to adjust the select / add a new one - I have an updated version of D38133 that builds on top of this (that I'm not intending to commit), to make sure that this patch actually does something useful, and it's used there. Depending on how D36073 goes it may or may not end up being useful though, so I'll remove it.

john.brawn updated this revision to Diff 117353.Oct 2 2017, 8:15 AM
john.brawn set the repository for this revision to rL LLVM.

Update based on review comments.

reames accepted this revision.Oct 2 2017, 8:08 PM

LGTM subject to the comment below being a clear bugfix addressed before commit.

lib/CodeGen/CodeGenPrepare.cpp
2720

Don't you also need to check that the offset and scale are zero? If not, then I'm still confused by what you mean by "trivial".

This revision is now accepted and ready to land.Oct 2 2017, 8:08 PM
skatkov added inline comments.Oct 2 2017, 9:07 PM
lib/CodeGen/CodeGenPrepare.cpp
2720

OriginalValue = gv + base + scale * Index + offset.

If OriginalValue == base => scale == 0, offset == 0, gv == 0

the same if OriginalValue == gv

skatkov added inline comments.Oct 2 2017, 10:04 PM
lib/CodeGen/CodeGenPrepare.cpp
2696

Don't you want to check type compatibility also here?
Say if type of base regs are different we can return Incompatible types here.

The similar for others...

Or we can do it as a separate patch...

john.brawn added inline comments.Oct 3 2017, 5:57 AM
lib/CodeGen/CodeGenPrepare.cpp
2696

Will do.

2720

Yes, scale and offset are expected to be zero in a trivial addrmode. I'll add a couple of asserts to make sure that's the case.

This revision was automatically updated to reflect the committed changes.