This is an archive of the discontinued LLVM Phabricator instance.

[StatepointsForGC] Identify values for rematerialization in presence of PHI
ClosedPublic

Authored by anna on Aug 26 2016, 5:32 AM.

Details

Summary

While walking the use chain for identifying rematerializable values in RS4GC,
add the case where the current value and base value are the same PHI nodes.

This will aid rematerialization of geps and casts instead of adding gc.relocate.

Diff Detail

Repository
rL LLVM

Event Timeline

anna updated this revision to Diff 69357.Aug 26 2016, 5:32 AM
anna retitled this revision from to [StatepointsForGC] Identify PHI values for rematerialization.
anna updated this object.
anna added reviewers: sanjoy, reames.
anna added a subscriber: llvm-commits.
igor-laevsky requested changes to this revision.Aug 26 2016, 7:48 AM
igor-laevsky edited edge metadata.

Could you please add a couple of tests? Also you should update comment in the header of the "findRematerializableChainToBasePointer".

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
1816–1817 ↗(On Diff #69357)

I would emphasise in the comment that it's a termination condition, not a continuation of recursion. Also would be nice to move it closer to the "CurrentValue == BaseValue" case.

1820 ↗(On Diff #69357)

This should be named PhiNum according to the llvm convensions

1824–1826 ↗(On Diff #69357)

I think you should check that incoming blocks are equivalent. In theory we can have two phi nodes with similar incoming values which are assigned to the different basic blocks, i.e:

base_value    = phi (%a, BB1), (%b, BB2)
current_value = phi (%a, BB2), (%b, BB1)

Also we can have two equivalent phi nodes with values recorder in a different order, i.e:

base_value    = phi (%a, BB1), (%b, BB2)
current_value = phi (%b, BB2), (%a, BB1)
This revision now requires changes to proceed.Aug 26 2016, 7:48 AM
anna marked 2 inline comments as done.Aug 26 2016, 8:34 AM
anna added inline comments.
lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
1824–1826 ↗(On Diff #69357)

IIUC, base_value != current_value for the first example?

base_value    = phi (%a, BB1), (%b, BB2)
current_value = phi (%a, BB2), (%b, BB1)

Although the value is coming from different basic blocks, since the incoming value is an SSA value, (%a, BB1) is same as (%a, BB2). There is only one definition for %a, and all uses are dominated by the def. So, base_value == current_value in the example.
Another concern that came to mind as I saw the example was, if we needed a recursive check if %a was also a phi node. Again, we do not need this check, for the same reason that %a is an SSA value.

Regarding the second example, I initially had this in mind while writing the patch, but the check complexity is O(n log n) for n = PhiNum. Didnt think it warranted the expense :) I'll add this case.

igor-laevsky added inline comments.Aug 26 2016, 9:39 AM
lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
1824–1826 ↗(On Diff #69357)

I still think that base_value != current_value at runtime. See extended example:

BB1:
  br %merge

BB2:
  br %merge

merge:
  base_value    = phi (%a, BB1), (%b, BB2)
  current_value = phi (%b, BB1), (%a, BB2)

Say at runtime control flow will go through BB1. This would mean that "base_value == %a" and "current_value == %b". In case if we go through BB2, situation will reverse: "base_value == %b" and "current_value == %a". This means that at runtime base_value will never be equal to the current_value.

I suspect this situation is hardly possible on practice, since we know that base_value is a base pointer for the current_value. Yet I'm not convinced that we can simply ignore this problem.

anna added a comment.Aug 26 2016, 10:30 AM

Upcoming change to handle review comments and with test cases from these examples discussed in review.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
1824–1826 ↗(On Diff #69357)

I see your point. I was looking at the incoming data values statically, rather than the control flow at runtime. It would take exactly one path :)

anna updated this revision to Diff 69438.Aug 26 2016, 2:58 PM
anna edited edge metadata.

Added a test case to show what we are trying to solve.
Also, consider reordering of arguments in phi, and consider incoming basic blocks as well.

Frankly, the best solution would be to remove the extra base.phi that is getting created, but need to see how to go about it.
I think in the current form, where base pointers that are phi nodes have an extra 'phi.base' getting generated,
we would not need the extra checks to make sure that the incoming basic blocks are the same, and also, the arguments won't be reordered.
These would be beneficial once we can remove the extra base.phi that get created.

anna retitled this revision from [StatepointsForGC] Identify PHI values for rematerialization to [StatepointsForGC] Identify values for rematerialization in presence of PHI.Aug 29 2016, 5:04 AM
anna updated this object.
anna edited edge metadata.
igor-laevsky accepted this revision.Aug 29 2016, 7:23 AM
igor-laevsky edited edge metadata.

looks good.

This revision is now accepted and ready to land.Aug 29 2016, 7:23 AM
reames accepted this revision.Aug 29 2016, 8:36 AM
reames edited edge metadata.

LGTM w/minor comment

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
1802 ↗(On Diff #69438)

I think it's important to call out in the comment that this is a workaround for deficiency in the base pointer rewriting code. That's not immediately obvious to everyone reading. :)

We really need to rewrite that code at some point. My initial prototype version has lived far longer than it should have.

This revision was automatically updated to reflect the committed changes.
anna added a comment.Aug 29 2016, 8:54 AM

LGTM w/minor comment

Ah, didnt see the update before my commit. However, I had added comments saying how such PHIs are generated and from which part of the algorithm. I'll explicitly mention this is a workaround for the deficiency. Thanks!