Page MenuHomePhabricator

[analyzer] Adding LoopContext and improve loop modeling
Needs ReviewPublic

Authored by szepet on Dec 12 2017, 6:32 PM.

Details

Summary

Based on the CFGLoopEntrance element, it is possible to have a CFG driven LocationContext update which contains loop information as well.
Updated the loop unrolling feature as well to use purely the LocationContext stack and not implement its own.
In the current situation the loop unrolling keeps track the currently simulated loop by having a stack of loops. However, the elements of the stack (so the needed information to describe the currently simulated loop) contains not just a Stmt* but a LocationContext* too which is a stack as well. So in order to store this information more efficient and intuitive I have added it to the LocationContext stack.

Diff Detail

Event Timeline

szepet created this revision.Dec 12 2017, 6:32 PM
MTC added a subscriber: MTC.Dec 12 2017, 11:19 PM
MTC added inline comments.
include/clang/Analysis/ProgramPoint.h
619

A minor typo, it should be 'program' :).

Just to be sure, this is just a refactoring to make this cleaner or you expect this to have other effects as well, like better performance?

This thing is very similar to D19979. Do we really need to create a separate LoopContext or we can reuse ScopeContext instead?

szepet edited the summary of this revision. (Show Details)Dec 21 2017, 9:03 AM
NoQ added a comment.Dec 21 2017, 3:31 PM

So, essentially, LoopContext is per-loop, while ScopeContext is per-iteration?

lib/StaticAnalyzer/Core/LoopUnrolling.cpp
28–46

Should the whole LoopState be reduced to a field(s) in LoopContext? It seems to make sense to me, unless we're planning to modify it in the middle of the loop.

NoQ added a comment.Dec 21 2017, 3:35 PM

Or not. Loop counter has its own whole-loop scope.

I guess LoopContext can be treated as a sub-class of ScopeContext. And i don't mind having ScopeContext be split into small distinct sub-classes. Because we're stuck in cornercases for covering all possible scopes, while we're fine with covering only simple scopes (it's better than nothing) and lacking a scope from time to time.

*asked stuff in D39398 regarding how indirect gotos are supported*

szepet updated this revision to Diff 130516.Jan 18 2018, 4:37 PM
szepet marked 2 inline comments as done.

First, sorry for this delayed update, however, I was working on this and running this on real projects. I wanted to make sure that this update will be complete enough that this patch would not cause any harm (yes, these features are hidden behind a flag but anyway) and not crashes on edge cases I haven't thought of. The core used the fact that LocationContext only contains StackFramce and BlockInvocation and I aimed to eliminate all these code snippets (more like rewrite).

This thing is very similar to D19979. Do we really need to create a separate LoopContext or we can reuse ScopeContext instead?

I guess LoopContext can be treated as a sub-class of ScopeContext. And i don't mind having ScopeContext be split into small distinct sub-classes. Because we're stuck in corner cases for covering all possible scopes, while we're fine with covering only simple scopes (it's better than nothing) and lacking a scope from time to time.

In this patch I left it as it was, so a separate context. I agree with Aleksei that yes, it could be implemented as a ScopeContext and checked if it contains a While/Do/For Statement.
On the other hand, I like the idea more, that we split ScopeContext into small distinct subclasses which would result in a more manageable code.
However, this would require refactoring on ScopeContext as well, in order to make it a great base class (like StmtPoint for ProgramPoint). Then, LoopContext would be its only subclass. So, I do not really see the point of doing these changes right now. I think in this state (when ScopeContext not used by the analyzer as I can see) the LoopContext could live as a separate Context and not make any harm. In case when another Context shows up which is similar LoopContext (e.g. ScopeContext) I would happily refactor it but right now, I do not see the point of this.

szepet added inline comments.Jan 18 2018, 4:48 PM
lib/StaticAnalyzer/Core/LoopUnrolling.cpp
28–46

I'm not sure about that. I mean, LoopContext is a general thing for all of the loops. It can easily happen that we modify the bound in the middle of the loop. Another thing what we keep track on if it is unrolled or not which is again something that we can decide to change in the middle of an iteration (e.g. it splits the state).

Yes, in our case MaxStep is not likely to change since we store loops that have a fix bound. (This could change in the future but maybe this is a too bold idea.)