Page MenuHomePhabricator

[CFG][Analyzer] Add LoopExit element to the CFG in more cases
Needs RevisionPublic

Authored by szepet on Oct 27 2017, 6:25 PM.

Details

Summary

This patch adds a LoopExit element to the CFG whenever a loop is exited by a ReturnStmt, GotoStmt or IndirectGotoStmt.
The LoopExit element is consumed by the Static Analyzer in order to simulate the loops more precisely. This patch aims to ensure that the simulation will be always consistent. So, whenever a loop is entered a loop exit element will be encountered after leaving it.

The idea is the following: In cases where a 'jump' is made we check (by walking up on the AST) the containing loops for both (From and To) locations. Then, generate the LoopExit element for the exited loops (which is the difference of the two "containing loop" set.

Note: In case of IndirectGotoStmt, it could happen that we generate LoopExit elements even for loops which is not exited by that jump. However, it does not seem to be a problem. This could result that we can not apply some more precise modeling feature (like unrolling and widening) but not any more - as I can see. (Also, this is a rare case.)

Diff Detail

Event Timeline

szepet created this revision.Oct 27 2017, 6:25 PM
szepet updated this revision to Diff 120726.Oct 27 2017, 6:33 PM

Just removed some accidentally left changes from the patch.

NoQ added a comment.Jan 2 2018, 4:36 PM

These CFGs make perfect sense to me so far, and i guess this is a must-have. Thank you!

Note: In case of IndirectGotoStmt, it could happen that we generate LoopExit elements even for loops which is not exited by that jump. However, it does not seem to be a problem. This could result that we can not apply some more precise modeling feature (like unrolling and widening) but not any more - as I can see. (Also, this is a rare case.)

This seems a bit scary because if there's no obvious one-to-once correspondence between entrances and exits along every path, how would we know when to pop loop contexts from the stack of location contexts? Like, if we attach variable lifetime checks to the loop exit, would we need to write additional code in the analyzer to see if the variable indeed goes out of scope on the current path? Could you demonstrate how it works in a test case over D41151?

include/clang/Analysis/CFG.h
172–179

I'd be glad to see more documentation on where does this CFGElement appear, when, and why:

  • At the end of the block within the loop?
  • At the beginning of the block after the loop?
  • In its own block constructed with the sole purpose of sheltering it?

Same goes for the CFGLoopEntrace, i guess.

test/Analysis/loopexit-cfg-output.cpp
912–914

P.S. This is not a regression introduced by your patch, but i'm really curious what does this block even do.

szepet updated this revision to Diff 130503.EditedJan 18 2018, 3:44 PM
szepet marked 2 inline comments as done.

Added comments and removed indirect goto support from this patch.

This seems a bit scary because if there's no obvious one-to-once correspondence between entrances and exits along every path, how would we know when to pop loop contexts from the stack of location contexts? Like, if we attach variable lifetime checks to the loop exit, would we need to write additional code in the analyzer to see if the variable indeed goes out of scope on the current path.

Yepp, we should check if the current loop (one quick method on the LocationContext) belongs to the LoopExit. This was already necessary in the previous patch since cases like:

if(Cond)
  for(;;){...}
stmt1
stmt2
...

In the above example even if Cond is false the analyzer will encounter the LoopExit since it is the first element of the breakBlock of the loop. (So it is within the same block as stmt1 and stmt2)

I have removed IndirectGoto support since it was not precise enough and rather handle this in the analyzer. (isPrecisableModelableLoop function in the D41151)

test/Analysis/loopexit-cfg-output.cpp
912–914

I believe this is the corresponding TransitionBlock to the WhileStmt (there is always a block which marks the looping back to the head of the loop event) but the optimization phase was good enough to detect that we will never proceed on that (since the first statement of the while loop is a goto jump).

george.karpenkov requested changes to this revision.May 30 2018, 4:56 PM
george.karpenkov added inline comments.
lib/Analysis/CFG.cpp
1298

shouldn't we have a visited list as well, to avoid exponential queue explosion if nodes are repeated?

This revision now requires changes to proceed.May 30 2018, 4:56 PM