This is an archive of the discontinued LLVM Phabricator instance.

[LCSSA] Handle PHI insertion in disjoint loops
ClosedPublic

Authored by bruno on Dec 11 2014, 11:52 AM.

Details

Summary

Take two disjoint Loops L1 and L2.

LoopSimplify skips to simplify some loops (e.g. when indirect branches are involved). In such situations, it can happen that an exit for L1 is the header of L2. Thus, when we create PHIs in one of such exits we are also inserting PHIs in L2 header.

This could break LCSSA form for L2 because these inserted PHIs can also have uses in L2 exits, which are never handled in the current implementation. Provide a fix for this corner case and test that we don't assert/crash on that.

Diff Detail

Repository
rL LLVM

Event Timeline

bruno updated this revision to Diff 17179.Dec 11 2014, 11:52 AM
bruno retitled this revision from to [LCSSA] Handle PHI insertion in disjoint loops.
bruno updated this object.
bruno edited the test plan for this revision. (Show Details)
bruno added reviewers: chandlerc, hfinkel.
bruno set the repository for this revision to rL LLVM.
bruno added a subscriber: Unknown Object (MLST).
chandlerc added inline comments.Dec 15 2014, 11:19 AM
lib/Transforms/Utils/LCSSA.cpp
97

Rather than a set pointing into AddedPHIs, just keep a list? We don't put PHI nodes into AddedPHIs more than once, so there is no need for set logic, just a separate list for the ones needing post-processing?

136–137

I would say "LoopSimplify might fail to simplify some loops (...)."

139

"PHIs in such an exit block, we are also inserting PHIs into L2's header." reads a bit better to me.

141

"can also have uses outside of L2."? It doesn't matter where the uses are, the key is that we're inserting a loop value in the form of a PHI node in the header.

182–192

Add a comment that we specifically recurse here?

Note that I can probably blow out the stack here with a suitably horrible crafted IR: simply set up a chain of loops such as this that is arbitrarily long. It's pretty contrived, but at least leave a FIXME that we should really convert this entire thing to a worklist approach where we process a vector of instructions...

bruno updated this revision to Diff 17332.Dec 16 2014, 5:21 AM
bruno removed rL LLVM as the repository for this revision.

Thanks for the review Chandler, patch updated with your suggestions.

chandlerc accepted this revision.Dec 22 2014, 11:28 AM
chandlerc edited edge metadata.

One totally nit-picky comment, and one substantial comment. Feel free to commit once addressed.

lib/Transforms/Utils/LCSSA.cpp
144–146

I would write this as:

if (auto OtherLoop = LI->getLoopFor(ExitBB))
  if (!L.contains(OtherLoop))
    PostProcessPHIs.push_back(PN)
177–181

Ow. This is quadratic in all cases AFAICT. Either we move all remaining elements in PostProcessPHIs down a slot, or we skip over an element in every trip throuh AddedPHIs (AddedPHIs is a superset and ordered the same).

Instead of all this, how about we do the post processing first, and then this loop? You can add a similar guard to skip post processing of phis with empty use lists. That avoids all the complexity here.

This revision is now accepted and ready to land.Dec 22 2014, 11:28 AM
bruno added inline comments.Dec 22 2014, 11:56 AM
lib/Transforms/Utils/LCSSA.cpp
144–146

Neat!

177–181

Yep, I was trying to avoid it by using SmallPtrSet in the first patch, thought you had noticed the tradeoff, should have made that explicit. But this solution looks better anyway. Thanks again. :-)

bruno closed this revision.Dec 22 2014, 2:39 PM