Page MenuHomePhabricator

[LCSSA] Re-use suitable PHI if available instead creating new ones.
AbandonedPublic

Authored by fhahn on Aug 25 2022, 2:19 PM.

Details

Summary

If ExitBB already contains a phi with a constant incoming value, re-use
it instead of creating a new phi. If the incoming value of the re-used
phi node is not yet in LCSSA form it will get formed in subsequent
iterations, like for newly created ones.

This means we won't end up with multiple LCSSA phi nodes when an
existing PHI can already be re-used. This is in particular relevant for
code that needs to re-build LCSSA for some values on demand, like
SCEVExpander.

This patch ensures that only be a single LCSSA phi will be created and
re-used when expanding the same expressions multiple times.

Fixes #57000.

Diff Detail

Event Timeline

fhahn created this revision.Aug 25 2022, 2:19 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 25 2022, 2:19 PM
fhahn requested review of this revision.Aug 25 2022, 2:19 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 25 2022, 2:19 PM
efriedma added inline comments.Aug 25 2022, 2:32 PM
llvm/lib/Transforms/Utils/LCSSA.cpp
176

Is the new code to prevent creating identical PHI nodes part of the fix, or just an optimization? It isn't obviously related.

fhahn added inline comments.Aug 25 2022, 3:05 PM
llvm/lib/Transforms/Utils/LCSSA.cpp
176

Preventing identical phis is the main part of the fix. The issue is that currently scev expansion can create different LCSSA phis when expanding the same expression (since we changed scev to look through trivial phis)

If those are then used as incoming values for phis with multiple matching predecessors we create invalid ir .

efriedma added inline comments.Aug 26 2022, 11:19 AM
llvm/lib/Transforms/Utils/LCSSA.cpp
176

I'm sorry, I really don't follow how having multiple PHI nodes that use the value messes up the algorithm. (If someone else does, feel free to take over reviewing...)

fhahn added inline comments.Aug 26 2022, 12:26 PM
llvm/lib/Transforms/Utils/LCSSA.cpp
176

Sorry for the confusion. Having multiple multiple phi nodes for the same values isn't a problem for the LCSSA construction algorithm itself. For the LCSSA construction algorithm the change is purely an optimization.

The bug fix is that is also addresses a problem for a user of the construction algorithm (SCEVExpander). Creating duplicated phis when expanding the same expression multiple times can cause issues with uses of the expanded expressions.

In the added test case pr57000, IndVars updates the incoming values of an LCSSA phi node with multiple incoming edges from the same block. It expands the same SCEV expression once for each edge and expanding it requires creating new LCSSA phi nodes (using the construction algorithm,). With the patch, LCSSA expansion will return a single PHI, whereas before it would create duplicated phis for each expansion, resulting in a phi node with different incoming values for edges from the same block.

I hope this helps to clarify things a bit.

efriedma added inline comments.Sep 13 2022, 2:39 PM
llvm/lib/Transforms/Utils/LCSSA.cpp
176

Dug a bit. I think I understand: rewriteLoopExitValues calls expandCodeFor in a loop. The way that loop is written, it implicitly assumes that if it calls expandCodeFor multiple times with the same operands, it will receive the same result. (Otherwise, it ends up setting the operands of the PHI it's rewriting to invalid values.)

There are other ways you could fix that particular issue. For example, we could just avoid repeated calls to expandCodeFor in rewriteLoopExitValues, which would be both faster, and more obviously correct.


I'm a little concerned that the current patch could end up iterating over ExitBB->phis() repeatedly, which would be effectively O(N^2).

Allen added a subscriber: Allen.Sep 21 2022, 7:53 AM
fhahn added inline comments.Sep 27 2022, 7:14 AM
llvm/lib/Transforms/Utils/LCSSA.cpp
176

There are other ways you could fix that particular issue. For example, we could just avoid repeated calls to expandCodeFor in rewriteLoopExitValues, which would be both faster, and more obviously correct.

Solving this closer to SCEV expansion sounds good to me! I initially thought solving this more generally in LCSSA construction may be desirable, but the potential compile-time cost doesn't make it seem worth it and I cannot think of a way to avoid a scan of all phi nodes.

I put up D134739 as an alternative which extends SCEVExpander's logic to use the previous expansion result for LCSSA phis.

Should this patch be abandoned since D134739 was committed?

fhahn abandoned this revision.Oct 12 2022, 8:42 AM

Yep, this is no longer needed.