This is an archive of the discontinued LLVM Phabricator instance.

[LCSSA] Forget values we create LCSSA phis for
ClosedPublic

Authored by fhahn on Sep 29 2019, 8:18 AM.

Details

Summary

Currently we only forget the loop we added LCSSA phis for. But SCEV
expressions in other loops could also depend on the instruction we added
a PHI for and currently we do not invalidate those expressions. This can
happen when we use ScalarEvolution before converting a function to LCSSA
form. The SCEV expressions will refer to the non-LCSSA value. If this
SCEV expression is then used with the expander, we do not preserve LCSSA
form.

This patch properly forgets the values we created PHIs for. Those need
to be recomputed again. This patch fixes PR43458.

Currently SCEV::verify does not catch this mismatch and any test would
need to run multiple passes to trigger the error (e.g. -loop-reduce
-loop-unroll). I will also look into catching this kind of mismatch in
the verifier. Also, we currently forget the whole loop in LCSSA and I'll
check if we can be more surgical.

Event Timeline

fhahn created this revision.Sep 29 2019, 8:18 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 29 2019, 8:18 AM
fhahn updated this revision to Diff 223651.Oct 7 2019, 2:10 PM

Add test.

If the SCEV expression is mathematically correct I think this is a problem with SCEV expander. If it is expected to preserve LCSSA it should add the necessary PHIs.

I know this contradicts existing code in SCEV that tries not to break LCSSA, I'm wondering if we should just remove those in favor of teaching SCEV expander about preserving LCSSA.

llvm/test/Transforms/LoopUnroll/unroll-preserve-scev-lcssa.ll
76 ↗(On Diff #223651)

Minor thing: I'd avoid adding branches on undef (unless you need them to reproduce the test) because there is no guarantee on how the optimizers will optimize these.

(It is also unclear whether this is UB.)

I know this contradicts existing code in SCEV that tries not to break LCSSA, I'm wondering if we should just remove those in favor of teaching SCEV expander about preserving LCSSA.

Currently, SCEV deliberately doesn't look through LCSSA PHI nodes (there's code in ScalarEvolution::createNodeForPHI etc.). You're saying we should change that? It might be a good idea. I recently ran into an performance issue involving a nested loop where SCEV for the outer loop was getting confused by an LCSSA PHI for the inner loop. I'd be worried about loop passes getting confused, though; for example, if they assume all AddRecs are part of the current loop nest.

That said, this patch probably isn't the right place to have that discussion.

fhahn added a comment.Oct 8 2019, 9:44 AM

I know this contradicts existing code in SCEV that tries not to break LCSSA, I'm wondering if we should just remove those in favor of teaching SCEV expander about preserving LCSSA.

Currently, SCEV deliberately doesn't look through LCSSA PHI nodes (there's code in ScalarEvolution::createNodeForPHI etc.). You're saying we should change that? It might be a good idea. I recently ran into an performance issue involving a nested loop where SCEV for the outer loop was getting confused by an LCSSA PHI for the inner loop. I'd be worried about loop passes getting confused, though; for example, if they assume all AddRecs are part of the current loop nest.

That said, this patch probably isn't the right place to have that discussion.

AFAICT, there are at least 2 issues that need addressing if we want to handle LCSSA PHIs differently: 1) teach SCEV to look through LCSSA phis and 2) updating SCEV expander to insert LCSSA Phi nodes, if required. Incidentally, I started out with a patch to fix the issue in the expander. But addressing both 1) and 2) seems like a more fundamental change.

As a first step I guess we could try to find some cases where we would get more precise results by looking through LCSSA PHIs. IMO that would be a better motivation than just the expander issue.

fhahn updated this revision to Diff 224488.Oct 10 2019, 2:55 PM
fhahn marked an inline comment as done.

remove undef branch conditions from tests.

fhahn marked an inline comment as done.Oct 10 2019, 2:56 PM
fhahn added inline comments.
llvm/test/Transforms/LoopUnroll/unroll-preserve-scev-lcssa.ll
76 ↗(On Diff #223651)

Excellent point, thanks! This was originally reduced by bug point which likes undef, but I've added proper conditions now.

ping. I did not have time to look into looking through LCSSA phis in SCEV, but I think it will be quite a complex change. I think it would be great if we could get in this fix regardless of addressing the bigger issue.

This revision is now accepted and ready to land.Oct 21 2019, 5:47 PM
This revision was automatically updated to reflect the committed changes.
fhahn added a comment.Dec 16 2019, 4:09 AM

I know this contradicts existing code in SCEV that tries not to break LCSSA, I'm wondering if we should just remove those in favor of teaching SCEV expander about preserving LCSSA.

Currently, SCEV deliberately doesn't look through LCSSA PHI nodes (there's code in ScalarEvolution::createNodeForPHI etc.). You're saying we should change that? It might be a good idea. I recently ran into an performance issue involving a nested loop where SCEV for the outer loop was getting confused by an LCSSA PHI for the inner loop. I'd be worried about loop passes getting confused, though; for example, if they assume all AddRecs are part of the current loop nest.

That said, this patch probably isn't the right place to have that discussion.

I've put up a WIP patch that teaches SCEVExpander to preserve LCSSA while expanding: D71538 it still needs a bit of refactoring and cleanup. And D71539 to look through trivial PHIs which also needs a bit of work.