This is an archive of the discontinued LLVM Phabricator instance.

GVN-hoist: improve code generation for recursive GEPs
ClosedPublic

Authored by sebpop on Jul 20 2016, 2:50 PM.

Details

Summary

When loading or storing in a field of a struct like "a.b.c", GVN is able to detect the equivalent expressions, and GVN-hoist would fail in the code generation.
This is because the GEPs are not hoisted as scalar operations to avoid moving the GEPs too far from their ld/st instruction when the ld/st is not movable.
So we end up having to generate code for the GEP of a ld/st when we move the ld/st.
In the case of a GEP referring to another GEP as in "a.b.c" we need to code generate all the GEPs necessary to make all the operands available at the new location for the ld/st.
With this patch we recursively walk through the GEP operands checking whether all operands are available, and in the case of a GEP operand, it recursively makes all its operands available. Code generation happens from the inner GEPs out until reaching the GEP that appears as an operand of the ld/st.

Tested on x86_64-linux with clang/libc++ bootstrap binary comparing stages 2 and 3, make check-all, test-suite, and cpu2006.
Ok to commit?

Diff Detail

Repository
rL LLVM

Event Timeline

sebpop updated this revision to Diff 64763.Jul 20 2016, 2:50 PM
sebpop retitled this revision from to GVN-hoist: improve code generation for recursive GEPs.
sebpop updated this object.
sebpop added reviewers: majnemer, dberlin.
sebpop set the repository for this revision to rL LLVM.
sebpop added subscribers: hiraditya, llvm-commits.
majnemer added inline comments.Jul 20 2016, 3:10 PM
llvm/lib/Transforms/Scalar/GVNHoist.cpp
578–603 ↗(On Diff #64763)

IIUC, this can mutate the IR while still returning false.

I'd change this to be a worklist algorithm instead of a recursive one. Inside the worklist loop, I'd push GEP candidates onto a vector for later processing (cloning).

sebpop added inline comments.Jul 20 2016, 3:33 PM
llvm/lib/Transforms/Scalar/GVNHoist.cpp
578–603 ↗(On Diff #64763)

You may be right: I'm not sure whether GEP operands are allowed to contain more than one GEP, in which case we may change the IR for one operand and then finally return false because of another GEP for which we fail to make operands available.

As the suggested change is a good cleanup, I will update the patch.

Thanks for your review.

sebpop updated this revision to Diff 65110.Jul 22 2016, 11:28 AM
sebpop removed rL LLVM as the repository for this revision.

Refactored the previous code: put the code generation part cloning the GEPs in a separate function, and call the recursive analysis of GEPs before mutating the IR.
I tried to use vectors, though they are more difficult to use and more compile time intensive, as one has to replace operands of the cloned instructions throughout all the cloned instructions.
With the recursive call we know exactly which operands in which instructions have to be replaced.
Passes make check-all and llvm test-suite on x86_64-linux.

I would like to commit this patch. Any more comments before commit?
Thanks!

sebpop updated this revision to Diff 65518.Jul 26 2016, 7:53 AM

Updated patch for trunk.

dberlin accepted this revision.Jul 26 2016, 11:12 AM
dberlin edited edge metadata.

LGTM for now

llvm/lib/Transforms/Scalar/GVNHoist.cpp
622 ↗(On Diff #65518)

Just a note:
You can cache the result here, since you may try to hoist something deeper and end up trying to make the same gep available again and again :)

(Not sure it happens enough to do it yet, you probably have better data than me)

This revision is now accepted and ready to land.Jul 26 2016, 11:12 AM
This revision was automatically updated to reflect the committed changes.