This is an archive of the discontinued LLVM Phabricator instance.

[LoopExtractor] Convert LoopExtractor from LoopPass to ModulePass
ClosedPublic

Authored by ekatz on Oct 16 2019, 1:29 PM.

Details

Summary

The LoopExtractor created new functions (by definition), which violates the restrictions of a LoopPass.
The correct implementation of this pass should be as a ModulePass.
Also revert r82990 implications on the LoopExtractor.

Fixes PR3082 and PR8929.

Diff Detail

Event Timeline

ekatz created this revision.Oct 16 2019, 1:29 PM
vsk added a comment.Oct 18 2019, 9:44 AM

Thanks, this looks reasonable to me. Please wait for another +1, as I'm not terribly familiar with the loop pass machinery.

ekatz updated this revision to Diff 225760.Oct 19 2019, 11:00 AM
ekatz edited the summary of this revision. (Show Details)

Found the revision that changed the pass from FunctionPass to LoopPass - r82990.
This change actually removed (for no apparent reason) the handling of sub-loops, in case the function is a minimal wrapper around a singular top-level loop, added in r12403.
I re-added this code.

In addition, I extracted some of the logics into separate functions, for better readability.

Some comments, but it looks reasonable overall.

llvm/lib/Transforms/IPO/LoopExtractor.cpp
43

Could you add a comment on how NumLoops is used?

106

Unused after the latest change?

131

Nit: rename to runOnFunction for consistency? I don't mean having an override method.
To give a similar example, function passes may have a static or class specific runOnBasicBlock without being a basic block pass.

142–143

for (auto *ExitBlock : ExitBlocks)

230

for (auto *ExitBlock : ExitBlocks)

ekatz updated this revision to Diff 225945.Oct 21 2019, 1:01 PM
ekatz marked 5 inline comments as done.

Applied requested changes.

ekatz updated this revision to Diff 226020.Oct 22 2019, 4:11 AM
ekatz edited the summary of this revision. (Show Details)

Removed redundant handling of EH pads at exit blocks, as it is already handled in CodeExtractor.

asbirlea accepted this revision.Oct 23 2019, 10:52 AM

Since I don't really understand the CodeExtractor, I'm relying on the author or another reviewer to confirm the correctness here.
This patch by itself looks good, but please wait to see if there are additional comments for the other reviewers before checking in.

llvm/lib/Transforms/IPO/LoopExtractor.cpp
61–62

Does this preserve LoopInfo? If yes, addPreserved, if unsure best to leave as is.

Similar question on the DomTree.
This is an item where I don't honestly understand if there are potential correctness implications in extractLoops if the DT is not preserved while iterating.

This revision is now accepted and ready to land.Oct 23 2019, 10:52 AM
ekatz marked an inline comment as done.Oct 23 2019, 11:35 AM
ekatz added inline comments.
llvm/lib/Transforms/IPO/LoopExtractor.cpp
61–62

You are correct. I will add the preservation of LoopInfo, as it is.
The DomTree is not.

ekatz updated this revision to Diff 226165.Oct 23 2019, 11:37 AM

Notify that the LoopInfo is preserved.

ekatz added a comment.Oct 28 2019, 3:07 PM
This comment was removed by ekatz.
ekatz added a comment.Nov 4 2019, 11:49 PM
This comment was removed by ekatz.
This comment was removed by ekatz.
ekatz retitled this revision from [IPO] Convert LoopExtractor pass from LoopPass to ModulePass to [LoopExtractor] Convert LoopExtractor from LoopPass to ModulePass.Nov 24 2019, 11:38 AM
ekatz updated this revision to Diff 231727.Dec 2 2019, 9:36 AM

Fix test.

fhahn added a subscriber: fhahn.Dec 4 2019, 3:20 AM

Would it be possible to also add some of the test cases for the linked bugs?

llvm/lib/Transforms/IPO/LoopExtractor.cpp
144

It might be slightly better to use size (from STLExtra.h), as it will fail to compile, if the iterators are not random access iterators. Or just check std::next(LI.begin()) != std::end()

149

Do we actually need this special case when it's a module pass? IIUC, it was only needed with the LoopPass to avoid extracting loops we already extracted into new functions earlier right?

181

I am not sure I see why we would try to extract the sub loops here? The original loopPass only tried to extract top-level loops, unless I missed something.

213–214

The original NumLoops was on a per-function basis I guess, but now it's per-module, right? I think it would be better to keep it on a per-function basis, i.e. NumLoops == the max number of loops to extract per function.

llvm/test/Feature/optnone-opt.ll
57

The pass is still run right, just somewhere else? Could you check this in the right place?

ekatz marked 5 inline comments as done.Jan 6 2020, 12:11 PM
ekatz added inline comments.
llvm/lib/Transforms/IPO/LoopExtractor.cpp
144

I agree. size (from STLExtras.h) is better.
Regarding the std::next solution, I thought it is a bit less clear, but it is actually even a better solution for the general case. So, I'll change it to that.

149

This particular line was added in SVN commit r86175 (Git commit rGa83ac2d9e7b990df6978598d9dec860b5ef13a9a). Personally, I do not see a good reason not to extract loops in a non simplify-form, but the change (that added it) does not explain much, so I decided to keep it (maybe there was a related bug?).
If you are positive that it is not needed, then I'll remove it.

181

As described in the "review summary", this is a kind of revert of SVN commit r82990 (Git commit rG9a7320c7110ee7f5450f8c46abe361de769886c0). I don't know why the extraction of the sub-loops was removed in that change, other than, probably, the change to LoopPass. Seems like an unintentional change/bug.

213–214

It used to be per program, as it is now; as the previous LoopPass was created only once per program (as well as the new ModulePass). The result remains the same.

llvm/test/Feature/optnone-opt.ll
57

It is still run, but it does not have an indication that the pass is skipped. Not sure why it was designed that way (probably wasn't), but skipped ModulePasses (via a call to skipModule) do not print any indication, while Function/Loop/Region-passes do.

ekatz updated this revision to Diff 237063.Jan 9 2020, 6:42 AM
ekatz added a comment.EditedJan 9 2020, 1:14 PM

Would it be possible to also add some of the test cases for the linked bugs?

This patch fixes a crash. Maybe just add a .ll file that shouldn't crash (with the fix)?!

@fhahn, what do you say?

Would it be possible to also add some of the test cases for the linked bugs?

This patch fixes a crash. Maybe just add a .ll file that shouldn't crash (with the fix)?!

that would be ideal.

llvm/lib/Transforms/IPO/LoopExtractor.cpp
149

I think the position of my original comment got messed up. I was referring to the distinction between functions with a single loop and functions with multiple loops. I *think* this was only needed with the LoopPass to avoid extracting loops we already extracted into new functions earlier which might result in an infinite loop.

I.e. just have the following starting at line 140.

DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
return extractLoops(LI.begin(), LI.end(), LI, DT);

The test coverage isn't great, but it seems to pass all tests ;)

213–214

Right.

ekatz marked an inline comment as done.Jan 15 2020, 8:31 PM
ekatz added inline comments.
llvm/lib/Transforms/IPO/LoopExtractor.cpp
149

Not sure the position got messed up - it is probably my fault. I do not sleep much these days, with my 1 year old teething or whatever he decides the reason to wake up every hour at night...

Anyway, this code is from SVN commit rL12403 (Git commit rG2f155d87). It is from the time that the pass was a FunctionPass. It tries to distinguish between a function that has more than a single loop with a simple function wrapper around a loop (which can be created by other means than the extractor).

ekatz marked an inline comment as done.Jan 15 2020, 8:33 PM
ekatz added inline comments.
llvm/lib/Transforms/IPO/LoopExtractor.cpp
149

I'll add a test for that particular case.

This LGTM, pending the test cases.

llvm/lib/Transforms/IPO/LoopExtractor.cpp
149

Anyway, this code is from SVN commit rL12403 (Git commit rG2f155d87). It is from the time that the pass was a FunctionPass. It tries to distinguish between a function that has more than a single loop with a simple function wrapper around a loop (which can be created by other means than the extractor).

Right, but it cannot happen while the LoopExtractor is running, with it being a module pass now, so we cannot get stuck in a loop where we extract a loop into a wrapper function and then try to extract the loop from the newly created function and get stuck.

Of course it still might be slightly more preferable to avoid extracting loops from trivial wrapper functions, but IMO the extra complexity does not really warrant the smallish benefit on a few probably not very common cases (also the checks are quite brittle and I guess not hit very often in practice (unless running loop-extract multiple times...))

But I am not feeling very strongly about that point :)

ekatz updated this revision to Diff 239663.Jan 22 2020, 11:43 AM
ekatz edited the summary of this revision. (Show Details)

Added test cases for the bugs, as well as for testing a simple extraction and a no extraction in the edge case where the function is just a minimal wrapper around a loop.

ekatz marked an inline comment as done.Jan 29 2020, 1:38 PM
ekatz added inline comments.
llvm/lib/Transforms/IPO/LoopExtractor.cpp
149

The new test LoopExtractor_min_wrapper.ll demonstrates the use case.

ekatz added a comment.Feb 6 2020, 2:54 AM

@fhahn , do I have a green light?

fhahn accepted this revision.Feb 6 2020, 4:08 AM

LGTM, with comments addressed before committing. Thanks!

llvm/lib/Transforms/IPO/LoopExtractor.cpp
151

nit: the comment is a bit confusing, as it checks if the loop is in simplify-form. Maybe say something like: If the loop is in LoopSimplify form, check if the function is a minimal container around the loop.

llvm/test/Transforms/CodeExtractor/LoopExtractor.ll
3 ↗(On Diff #239663)

I think it would be good to check the full IR after extraction.

llvm/test/Transforms/CodeExtractor/LoopExtractor_crash.ll
4 ↗(On Diff #239663)

There are no arguments to promote and no functions to inline? Is -inline/-argpromotion needed? Also, please add some rudimentary checks. (you could use llvm/tools/update_test_checks.py)

llvm/test/Transforms/CodeExtractor/LoopExtractor_infinite.ll
3 ↗(On Diff #239663)

Is running -mergereturn required? Or is it enough to have the output of merge return as test case? Also it would be good to have some rudimentary checks.

ekatz marked 2 inline comments as done.Feb 6 2020, 9:42 AM
ekatz added inline comments.
llvm/test/Transforms/CodeExtractor/LoopExtractor_crash.ll
4 ↗(On Diff #239663)

inline and argpromotion shouldn't do anything but certainly not crash. This crash is observed in those cases.

llvm/test/Transforms/CodeExtractor/LoopExtractor_infinite.ll
3 ↗(On Diff #239663)

opt must be run with mergereturn and loop-extract to observe the infinite loop.

ekatz updated this revision to Diff 242953.Feb 6 2020, 10:58 AM
ekatz marked 3 inline comments as done.Feb 6 2020, 11:00 AM
ekatz added inline comments.
llvm/lib/Transforms/IPO/LoopExtractor.cpp
151

Done.

llvm/test/Transforms/CodeExtractor/LoopExtractor.ll
3 ↗(On Diff #239663)

Added full IR check.

llvm/test/Transforms/CodeExtractor/LoopExtractor_crash.ll
4 ↗(On Diff #239663)

I don't think there is any reason to test the resulting IR. This test is only testing that there is no crash.

fhahn added inline comments.Feb 6 2020, 11:13 AM
llvm/test/Transforms/CodeExtractor/LoopExtractor_crash.ll
4 ↗(On Diff #239663)

Sure, but it would still be good to check that the pass does what we expect (not crashing is a relatively low bar). I guess this is a case where the function is just a minimal container? If that's the case, that's worth explicitly checking (and probably best to also add a short comment & a reference to the bug).

also without check, the pass could also delete the whole function in order not to crash ;)

ekatz updated this revision to Diff 242975.Feb 6 2020, 12:05 PM

Added IR checks of all the tests.

ekatz marked an inline comment as done.Feb 6 2020, 12:05 PM
ekatz added inline comments.
llvm/test/Transforms/CodeExtractor/LoopExtractor_crash.ll
4 ↗(On Diff #239663)

I agree. Done.

ekatz added a comment.Feb 7 2020, 12:41 PM

@fhahn does it look right?

fhahn added a comment.Feb 8 2020, 6:29 AM

Looks good, thanks!

This revision was automatically updated to reflect the committed changes.

Seems like it... :/
I wonder if it is because of the duplication of the dependencies in:

INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)

as LoopSimplify already depends on LoopInfoWrapperPass which depends on DominatorTreeWrapperPass.

I'll try to remove the last 2.

fhahn added a comment.Feb 13 2020, 2:12 AM

Should be fixed in rGd8a2ea9fd5c7

looks like it, thanks!