This is an archive of the discontinued LLVM Phabricator instance.

[CFG] Adding new CFGStmt LoopEntrance for the StaticAnalyzer
Needs ReviewPublic

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

Details

Summary

Adding LoopEntrance as a new CFGElement to the CFG.
This element is added as the last element of the CFGBlock just before the loop condition block.
This can help the Static Analyzer to have a more precise loop modeling.

Diff Detail

Event Timeline

szepet created this revision.Dec 12 2017, 6:24 PM
dkrupp requested changes to this revision.Dec 13 2017, 12:28 AM
This revision now requires changes to proceed.Dec 13 2017, 12:28 AM
dkrupp added inline comments.Dec 15 2017, 5:01 AM
include/clang/Analysis/CFG.h
179

This comment refers to the CFGLoopExit class. Please add a separate explaining comment to the CFGLoopEntrance.

szepet updated this revision to Diff 127894.Dec 21 2017, 8:42 AM
szepet marked an inline comment as done.

Comment added to LoopEntrance CFGElement.

NoQ added a comment.EditedJan 2 2018, 3:59 PM

Because it wasn't immediately obvious to me how to apply both this patch and D39398 (there are a couple of minor conflicts between them), i wanted to post a few pictures for the reference, because debug.ViewCFG graphs are much easier to comprehend than text dumps.

For example, here's the new CFG for check_return() in loopexit-cfg-output.cpp:

833 int check_return() {
834   for (int i = 0; i < 10; i++) {
835     int j = 1;
836     while (j < 12) {
837       if (j % 2)
838         return 0;
839     }
840   }
841   return 1;
842 }


I essentially have one question at a glance - for loop counter variables, don't we want LoopEntrance be before the initialization? I.e. on this picture wouldn't it be better to have

[B10]
1: ForStmt (LoopEntrance)
2: 0
3: int i = 0;

?

Because otherwise our future LoopContext wouldn't correspond to any variable's lifetime scope, so it'd be kind of useless as a ScopeContext. Because, as far as i understand, there are two scopes in every loop:

  1. The scope of the whole loop which includes the counter,
  2. The scope of every iteration, which goes out of scope after the iteration ends.

And currently LoopContext is none of these. Would loop unrolling still work in a sensible manner if we move LoopEntrance to the beginning of the block?

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

(edited my comment: fixed the suggested change to mention the right block)

szepet updated this revision to Diff 130505.Jan 18 2018, 3:51 PM

I essentially have one question at a glance - for loop counter variables, don't we want LoopEntrance be before the initialization?

I guess this would just make too much sense. Done that.

Additionally, handle the cases when we just hop to the body of the loop via goto stmt.
Now the patches can be applied without any conflict (added the loopexit patch as a dependency).

george.karpenkov accepted this revision.May 30 2018, 4:48 PM

I would prefer a more detailed CFG element with more meta-information about nested loop, but this is a good starting point.

Also loops created with gotos should also be supported (e.g. by finding backedges), but that could be done in a different patch.