Page MenuHomePhabricator

[CVP] Replace incoming values from unreachable blocks with undef
ClosedPublic

Authored by davide on Jan 7 2018, 2:03 PM.

Details

Summary

This is an attempt of fixing PR35807.
Due to the non-standard definition of dominance in LLVM, where uses in unreachable blocks are dominated by anything, you can have, in an unreachable block

%patatino = OP1 %patatino, CONSTANT

When SimplifyInstruction receives a PHI where an incoming value is of the aforementioned form, in some cases, loops indefinitely (see the stack trace in the PR). I, pretty honestly, tried to figure out what was wrong in ValueTracking and it seems cause a loop, but I wasn't really able to get to the bottom of it as SimplifyInstruction/ValueTracking recently became a big mess.

What I propose here instead is keeping track of the incoming values from unreachable blocks, and replacing them with undef. This fixes this case, and it seems to be good regardless (even if we can't prove that the value is constant, as it's coming from an unreachable block, we can ignore it).

OTOH, I don't want to paper over the issue, so if somebody feels brave enough to take a look, I'll abandon this (although it might go in for the reasons explained above).

I experimented using a domtree to query reachability rather than RPOT, but it doesn't seem to make a difference for compile time even for large test cases(where we spend a decent fraction of time in CVP).

Diff Detail

Repository
rL LLVM

Event Timeline

davide created this revision.Jan 7 2018, 2:03 PM
spatel added a subscriber: spatel.Jan 8 2018, 6:31 AM
anna added a comment.Jan 8 2018, 6:46 AM

What I propose here instead is keeping track of the incoming values from unreachable blocks, and replacing them with undef. This fixes this case, and it seems to be good regardless (even if we can't prove that the value is constant, as it's coming from an unreachable block, we can ignore it).

LGTM - this was also the design I went with (change incoming values from unreachable blocks to undef) when we didn't want to break the structure of the loop in loop deletion.

anna accepted this revision.Jan 8 2018, 7:10 AM

LGTM w/ comments.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
134 ↗(On Diff #128886)

The reasons for this code here is 2 fold right:

  1. avoid querying LVI for unreachable block BB
  2. transforming the incoming value so that transformation further below don't mess around with such IR in unreachable blocks.

It's really #2 that fixes this issue. #1 just avoids unnecessary work.

I agree that this change by itself is a good one to have (it also has the side effect of avoiding IR pattern in *this single* instance of SimplifyInstruction).

test/Transforms/CorrelatedValuePropagation/pr35807.ll
41 ↗(On Diff #128886)

All of these are unreachable blocks, could you pls rename them or perhaps add a comment on bb14 stating its unreachable block.

This revision is now accepted and ready to land.Jan 8 2018, 7:10 AM
This revision was automatically updated to reflect the committed changes.
efriedma added inline comments.Jan 23 2018, 12:33 PM
llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
336

This call invalidates the set of reachable blocks.

davide added inline comments.Jan 23 2018, 12:39 PM
llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
336

hmmm, this is annoying.
I can't think of an easy way of handling this case easily. Do you have something in your mind?
If not, I'll revert the patch for now until I come up with a better idea.
cc: @anna

efriedma added inline comments.Jan 23 2018, 1:02 PM
llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
336

Maybe you could use an incrementally updated domtree to keep ReachableBlocks up-to-date? Not sure how expensive that would be, though.

Alternatively, you could record dead edges, and postpone actually modifying the CFG until the end of the pass. You lose a little optimization power that way, I guess, but it avoids any complicated incremental updates.

thanks, I'll give this a shot when I have a minute to dedicate to llvm.