Page MenuHomePhabricator

[LoopSimplifyCFG] Do not deal with loops with irreducible CFG inside
ClosedPublic

Authored by mkazantsev on Dec 6 2018, 1:51 AM.

Details

Summary

The current algorithm that collects live/dead/inloop blocks relies on some invariants
related to RPO and PO traversals. In particular, the important fact it requires is that
the only loop's latch is the first block in PO traversal. It also relies on fact that during
RPO we visit all prececessors of a block before we visit this block (backedges ignored).

If a loop has irreducible non-loop cycle inside, both these assumptions may break.
This patch adds detection for this situation and prohibits the terminator folding
for loops with irreducible CFG.

We can in theory support this later, for this some algorithmic changes are needed.
Besides, irreducible CFG is not a frequent situation and we can just don't bother.

Thanks @uabelho for finding this!

Diff Detail

Repository
rL LLVM

Event Timeline

mkazantsev created this revision.Dec 6 2018, 1:51 AM

I don't know this code but at least it makes the reproducer I had compile succesfully now. Thanks!

mkazantsev marked an inline comment as done.
mkazantsev added inline comments.
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
161 ↗(On Diff #176939)

typo: irreducle --> irreducible, will fix before commit.

mkazantsev updated this revision to Diff 177112.Dec 6 2018, 8:49 PM

Typo/comment fix.

skatkov accepted this revision.Dec 6 2018, 9:04 PM
skatkov added inline comments.
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
152 ↗(On Diff #177112)

I think it makes sense to add an assert
assert(DFS.isComplete() && "DFS is expected to be finished");
here.

This revision is now accepted and ready to land.Dec 6 2018, 9:04 PM
mkazantsev marked an inline comment as done.Dec 6 2018, 9:10 PM
This revision was automatically updated to reflect the committed changes.