Page MenuHomePhabricator

[SCEV] Fix false-positive recognition of simple recurrences. PR49856
ClosedPublic

Authored by mkazantsev on Tue, Apr 6, 1:06 AM.

Details

Summary

A value from reachable block may come to a Phi node as its input from
unreachable block. This may confuse matchSimpleRecurrence which
has no access to DomTree and can falsely recognize something as a recurrency
because of this effect, as the attached test shows.

Patch ae7b1e deals with half of this problem, but it only accounts from
the case when an unreachable instruction comes to Phi as an input.

This patch provides a generalization by checking that no Phi block's
predecessor is unreachable (no matter what the input is).

Diff Detail

Event Timeline

mkazantsev created this revision.Tue, Apr 6, 1:06 AM
mkazantsev requested review of this revision.Tue, Apr 6, 1:06 AM
Herald added a project: Restricted Project. · View Herald TranscriptTue, Apr 6, 1:06 AM
mkazantsev edited the summary of this revision. (Show Details)Tue, Apr 6, 1:07 AM
mkazantsev updated this revision to Diff 335427.Tue, Apr 6, 1:29 AM

Trivialized test.

uabelho added a subscriber: uabelho.Tue, Apr 6, 5:38 AM
reames accepted this revision.Tue, Apr 6, 7:30 PM

I posted an alternate fix here: https://reviews.llvm.org/D100004. Let me know what you think. Stylistically, I prefer that one, but yours appears to be correct as well.

Given that, I'm LGTMing this, but asking you not to land unless you spot a problem with the one I linked to. If you do, feel free to land this, and I can work on top of it. I don't want to delay the correctness fix over a debatable style issue.

This revision is now accepted and ready to land.Tue, Apr 6, 7:30 PM
mkazantsev added a comment.EditedTue, Apr 6, 9:34 PM

I can't say if the alternative a correct solution because I don't know if we guarantee to destroy all loops immediately after some block contained in them has become urneachable. If not, then the alternative solution also contains this bug. If yes, this is not obvious and I'm not sure where it is asserted. We can go with it if we have the answers to these questions. I don't see any problems with having a loop in fully unreachable code, or having extra unreachable predecessors to loop blocks.