Page MenuHomePhabricator

[JumpThreading] Fix threading with unusual PHI nodes.
ClosedPublic

Authored by efriedma on Jun 27 2019, 5:51 PM.

Details

Summary

If the block being cloned contains a PHI node, in general, we need to clone that PHI node, even though it's trivial. If the operand of the PHI is an instruction in the block being cloned, the correct value for the operand doesn't exist until SSAUpdater constructs it.

We usually don't hit this issue because we try to avoid threading across loop headers, but it's possible to hit this in some cases involving irreducible CFGs. I added a flag to allow threading across loop headers to make the testcase simpler.

Thanks to Brian Rzycki for reducing the testcase.

Fixes https://bugs.llvm.org/show_bug.cgi?id=42085.

Diff Detail

Repository
rL LLVM

Event Timeline

efriedma created this revision.Jun 27 2019, 5:51 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 27 2019, 5:51 PM
Herald added a subscriber: jfb. · View Herald Transcript

Hi @efriedma , thank you for debugging and identifying the true root cause of PR42085. My comments are inline.

lib/Transforms/Scalar/JumpThreading.cpp
110 ↗(On Diff #206977)

I have concerns about adding this flag in this patch without a bit more testing and general test-cases for loop header threading. I fear this is a proverbial can of worms for any third party user of opt who discovers this flag and starts using it.

1993 ↗(On Diff #206977)

Nit: please consider naming New to something like NewPN.

efriedma marked an inline comment as done.Jul 1 2019, 3:32 PM
efriedma added inline comments.
lib/Transforms/Scalar/JumpThreading.cpp
110 ↗(On Diff #206977)

Thinking about it a bit more, I think it's only possible to reproduce this issue if a PHI node operand is specifically another instruction in the same basic block, since we don't rewrite any other values. That implies the block dominates its predecessor, i.e. it's a loop header. This means either LoopHeaders computation is disabled, or it's falling out of date due to CFG changes.

If we remove this flag, the only way to test this change is to check an IR file where a transform causes the loop headers to fall out of date, then threading happens. Your original testcase works like this, but it's fragile: it could break in unintuitive ways due to other changes.

I'm not really concerned about adding experimental flags; it's something we do routinely, and it doesn't seem to cause any confusion. I can rename the flag if that helps?

Hi @efriedma, comments are inline.

lib/Transforms/Scalar/JumpThreading.cpp
110 ↗(On Diff #206977)

That implies the block dominates its predecessor, i.e. it's a loop header.

This helps me understand why I was down the path of LoopHeader analysis. In D63629 that's exactly what is happening: we calculate all loop headers and then immediately alter the state for trivially constant TIs causing the true loop headers to emerge to FindFunctionBackedges().

I think it's only possible to reproduce this issue if a PHI node operand is specifically another instruction in the same basic block, since we don't rewrite any other values.

I suspect you're right. The failing IR is unusual in several ways and I noticed this. I've never seen clang pass JT a CFG with this property.

I'm not really concerned about adding experimental flags; it's something we do routinely, and it doesn't seem to cause any confusion.

I've thought about it a bit more and agree with you. It'd be better to find the latent bugs in JT if external users enable the flag in their non-standard flows. I'm fine with leaving as-is.

efriedma updated this revision to Diff 207629.Jul 2 2019, 2:25 PM

Fix variable name.

brzycki accepted this revision.Jul 2 2019, 3:56 PM

LGTM.

This revision is now accepted and ready to land.Jul 2 2019, 3:56 PM
This revision was automatically updated to reflect the committed changes.