Page MenuHomePhabricator

[Analyzer] Unroll for-loops where the upper boundary is a variable with know value
Needs ReviewPublic

Authored by baloghadamsoftware on Jun 13 2019, 9:11 AM.

Details

Summary

For-loops with a variable upper boundary do not differ very much from for-loops with integer literals if the value of the variable is known. Unroll these loops as well, similarly to them. This was a TODO anyway.

Diff Detail

Event Timeline

Szelethus added inline comments.Jul 6 2019, 12:01 PM
lib/StaticAnalyzer/Core/LoopUnrolling.cpp
216–218

Alright, I stood on top of this for longer than I'd like to admit, what's happening here? Like, CondExpr, with the given testfile, should be i < n, right? Then BoundExpr is supposed to be i, and if that is equal to Matches[0].getNodeAs<Expr>("boundVarOperand") (which I guess is supposed to n), which I'm not sure how it could ever happen, we assign the RHS of the assignment to BoundExpr?

What does this do? Why is it needed? Which 2 test cases cover these lines?

223–232

I don't see obvious test case for which BoundNumVal would be unknown, am I wrong?

NoQ added inline comments.Jul 9 2019, 12:34 PM
lib/StaticAnalyzer/Core/LoopUnrolling.cpp
216–218

I think this is about i < n vs. n > i.

223–232

We need an ExprInspection method that reliably produces an UnknownVal, because there's no truly valid reason to produce UnknownVal apart from "something is unimplemented".

Szelethus requested changes to this revision.Jul 15 2019, 1:23 PM
Szelethus added inline comments.
lib/StaticAnalyzer/Core/LoopUnrolling.cpp
216–218

If that is the case, I'd be more comfortable seeing a test for it (there doesn't seem to be any) before landing this.

223–232

For this too.

This revision now requires changes to proceed.Jul 15 2019, 1:23 PM
baloghadamsoftware marked an inline comment as done.Jul 17 2019, 6:01 AM
baloghadamsoftware added inline comments.
lib/StaticAnalyzer/Core/LoopUnrolling.cpp
223–232

Wrong request! :-) The test case is there. Actually we need a test case for which 'BoundNumVal' is not unknown. That I still fail to produce.

Test case added for loop conditions written in reverse order and code fixed to make the test pass.

baloghadamsoftware marked an inline comment as done.Jul 17 2019, 6:08 AM

I am a bit afraid of the performance of the feature because of the extensive use of matchers. Based on my previous experiences matcher creation and disposition are expensive operations. Matchers are meant to be a kind of "static" structures created only once and destroyed at the end. Using them in the core infrastructure may negatively affect the execution time of the whole analysis. Maybe we should get rid of them before turning on this feature as default (which is the ultimate goal).

I think you forgot to remove /* */ and clang formatting before uploading the patch.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp
216–218

I'd appreciate a few lines of comment, given that there's evidence that it might not be obvious what's happening here :^)

NoQ added a comment.EditedJul 17 2019, 5:21 PM

/me has just noticed that this isn't D34812.

In D63279#1590676, @NoQ wrote:

/me has just noticed that this isn't D34812.

Oh great find! Is it worth seizing commandeering @baloghadamsoftware?

In D63279#1590676, @NoQ wrote:

/me has just noticed that this isn't D34812.

Oh, I just noticed that there was already an attempt to fix this :-) However, it seems that the review there died because the author left the work on the analyzer. My fix attempt is an answer to a user request. This patch does not intend to solve other problems, just the symbols with known value. However we are also interested in finalizing this project so it could be enabled as default in future versions of the analyzer. Maybe we should further discuss the open problems regarding it on cfe-dev or maybe in a personal meeting on Skype.

Fix wrong upload.

baloghadamsoftware marked an inline comment as not done.Jul 30 2019, 5:25 AM

For me it is all the same whether to continue this patch or taking over Péter's.

For me it is all the same whether to continue this patch or taking over Péter's.

Well, there are plenty of comments I'm not sure ever got addressed. We could take an inventory of that as a start. @NoQ, do you have any *immediate* suggestion about the direction of this effort? If not, I'd be happy to dive deeper into the archaeology with Ádám and follow up with this later.

NoQ added a comment.Aug 14 2019, 3:30 PM

A quick archaeological dig suggests that i had no concerns with turning on unrolling by default back in 2017: http://lists.llvm.org/pipermail/cfe-dev/2017-August/055221.html - and i don't think i had any new concerns since then. I guess it'll be beneficial to make one more large-codebase run to make sure it still works, but other than that the only reason it's not enabled by default yet is because we forgot to do that :( This patch is good but not a must-have to turn loop unrolling on by default.

Szelethus added a comment.EditedAug 14 2019, 3:41 PM
In D63279#1630491, @NoQ wrote:

the only reason it's not enabled by default yet is because we forgot to do that :(

Damn, thats a bummer. It wouldn't be too much trouble to run an analysis and check out whether everything works correctly, so I might enable this myself.