This is an archive of the discontinued LLVM Phabricator instance.

GVN-hoist: fix hoistingFromAllPaths for loops (PR29034)
ClosedPublic

Authored by sebpop on Aug 24 2016, 11:08 AM.

Details

Summary

It is invalid to hoist stores or loads if they are not executed on all paths
from the hoisting point to the exit of the function. In the testcase, there are
paths in the loop that do not execute the stores or the loads, and so hoisting
them within the loop is unsafe.

The problem is that the current implementation of hoistingFromAllPaths is
incomplete: it walks all blocks dominated by the hoisting point, and does not
return false when the loop contains a path on which the hoisted ld/st is
not executed.

Diff Detail

Event Timeline

sebpop updated this revision to Diff 69141.Aug 24 2016, 11:08 AM
sebpop retitled this revision from to GVN-hoist: fix hoistingFromAllPaths for loops (PR29034).
sebpop updated this object.
sebpop added a reviewer: dberlin.
sebpop added subscribers: llvm-commits, hiraditya.
sebpop updated this revision to Diff 69156.Aug 24 2016, 12:50 PM

Added testcase for https://llvm.org/bugs/show_bug.cgi?id=29031 that is also fixed by this patch.

dberlin added inline comments.Aug 24 2016, 3:01 PM
llvm/lib/Transforms/Scalar/GVNHoist.cpp
315

How is this different than just checking whether one of the successors is a loop backedge?
(and if so, why not just compute and store that set once :P)

If it's different, how is this not basically a dominance frontier check?

dominance frontier of BB = blocks where BB's dominance ends.

So this is a check if any of the blocks are in the dominance frontier of BB, no?

sebpop added inline comments.Aug 24 2016, 8:17 PM
llvm/lib/Transforms/Scalar/GVNHoist.cpp
315

I think checking for loop latch is in part correct: there may be irreducible loops that would not be in LoopInfo and there may still exit backedges that would violate the property of execution on all paths.

Yes, the check can be rewritten as whether a successor of a block in the dominance frontier of BB dominates BB. So we would not have to compute this property for all blocks dominated by BB, only for the blocks on the dominance frontier.

I will update the patch. Thanks for the suggestion.

See if it's worth it. Storing the DF is N^2, even though it's linear time to compute, so if doing it your current way is faster, let's go with that.

I think I will commit the patch as is for this reason.

This revision was automatically updated to reflect the committed changes.