[StaticAnalyzer] Question about IPA function call inlining

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[StaticAnalyzer] Question about IPA function call inlining

Xin Wang via cfe-dev
Hi,

I noticed a strange behavior of function call inlining when I was debugging my checker. 
For a very simple code example:

void func_with_loop(int loop_times) {
  for (int i = 0; i < loop_times; i++) {
    //Do nothing
  }
}

void call_loop(int tag) {
  func_with_loop(tag);
}

When I run clang static analyzer on this piece of code with scan-build, the function "func_with_loop()" will not be inlined by ExprEngine.

To demo this behavior, here is my patch to the clang to print if the function call is inlined: https://gist.github.com/zeroomega/bbe2cfa298a912a1b5b37fa4b9cd76b5 . The output of clang after this patch is:

testmxchannel.c:204:3func_with_loop  Should inline: Direct inlined
Block Count exceeded maxBlockVisitOnPath 4Dump SRC

 [B1]
   1: i
   2: [B1.1]++
   Preds (1): B2
   Succs (1): B2


 Dump Dst:

 [B2]
   1: i
   2: [B2.1] (ImplicitCastExpr, LValueToRValue, int)
   3: loop_times
   4: [B2.3] (ImplicitCastExpr, LValueToRValue, int)
   5: [B2.2] < [B2.4]
   T: for (...; [B2.5]; ...)
   Preds (2): B1 B3
   Succs (2): B1 B0


testmxchannel.c:204:3func_with_loop  InlinedFailedState is not null  Should not inline 

It seems that the ExprEngine did try to inline the function "func_with_loop", but the total block count of this function exceeded "maxBlockVisitOnPath", which by default is 4. The inline process was rolled back and this function is evaluated by "conservativeEvalCall". I manually increased the value of "maxBlockVisitOnPath" but "func_with_loop" was still not inlined.

Is it an intended behavior of clang static analyzer or is it a bug? In my understanding, by default, when clang static analyzer evaluate a loop that the total times of the loop cannot determined, the loop will be evaluated for 4 times and an additional ExplodedNode will be created with the loop condition evaluated to false. But why in this code example it causes the function inline to be rolled back instead of creating an additional node that evaluate the loop conditions to false?

Another question I have is that is it possible in checkPreCall() callback of a checker to determine if the function call will not be inlined by ExprEngine? 

Thanks for any help,

Haowei

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [StaticAnalyzer] Question about IPA function call inlining

Xin Wang via cfe-dev
Hello Haowei,

You described most of the behaviors right but not exactly.


When I run clang static analyzer on this piece of code with scan-build, the function "func_with_loop()" will not be inlined by ExprEngine.

The func_with_loop() function will be inlined for sure. That is what your example has just proven by producing the line:
 
testmxchannel.c:204:3func_with_loop  Should inline: Direct inlined

So it will be inlined. Lets considering the next important line in the output:
 
Block Count exceeded maxBlockVisitOnPath 4Dump SRC
...
testmxchannel.c:204:3func_with_loop  InlinedFailedState is not null  Should not inline 
 
It seems that the ExprEngine did try to inline the function "func_with_loop", but the total block count of this function exceeded "maxBlockVisitOnPath", which by default is 4. The inline process was rolled back and this function is evaluated by "conservativeEvalCall".
 
Yeah. that is what happens BUT! only on the PATH where the maxBlockVisitOnPath exceeded. So the other paths will be simulated but this path will be rolled back before the point where the analyzer inline the function and mark the function not to be inlined again (NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE)). So simulating again that path will trigger the defaultEvalCall on the same function call which was just rolled back and marked so the analyzer won't inline it. That is what is checked by the getInlineFailedState() and that is the reason why the 2. output says it should not be inlined.

In my understanding, by default, when clang static analyzer evaluate a loop that the total times of the loop cannot determined, the loop will be evaluated for 4 times and an additional ExplodedNode will be created with the loop condition evaluated to false. But why in this code example it causes the function inline to be rolled back instead of creating an additional node that evaluate the loop conditions to false?

Not exactly. The ExplodedGraph will be forked every time when the loop condition is evaluated. So there will be 5 different paths int ExplodedGraph while simulating a loop like this:
- when the condition is false
- when the condition is false after the 1. step
- when the condition is false after the 2. step
- when the condition is false after the 3. step
- when the condition is true every time - but this will be the path where the maxBlockVisitOnPath exceeds and then the above mentioned things happen.

Why is it important to replay the analysis without inlining this function which contains a loop?
The most problematic case is when the bound is known so the analyzer won't create new branches for paths where the condition can be false if it knows it can't be. For example if you try out a code like this:

void func_with_loop(int loop_times) {
  for (int i = 0; i < loop_times; i++) {
    //Do nothing
  }
}

void call_loop() {
  func_with_loop(12);
  ... //the most complex body you can just imagine
}

In this case (without the replaying-without-inlining feature) the analysis of this call_loop function would be ended while analyzing the inlined func_with_loop() function and exceeding the maxBlockVisitOnPath. Which is not something you would like to see so the state is going to be rolled back and the other parts of the function will be analyzed but without knowing what the func_with_loop() function did (so yes, with more unknown value).
 
Another question I have is that is it possible in checkPreCall() callback of a checker to determine if the function call will not be inlined by ExprEngine? 

I would be surprised if you can check that in checkPreCall() but maybe somebody else (probably NoQ) knows a way to check this.  (in checkPostCall() you can do this for sure by checking the wasInlined flag of the CheckerContext.)

I hope I could help at least a little bit.

Cheers,
Peter

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [StaticAnalyzer] Question about IPA function call inlining

Xin Wang via cfe-dev
Hi Peter,

Thanks for you clarification, it helps a lot. If I understood correctly, for following code:

void func_with_loop(int tag) {
  for (int i = 0; i < 12; i++) {
    // Do nothing
  }
  // Some complex body
}

If the func_with_loop() is a top level function, the code after the for loop will not be evaluated at all because maxBlockVisitOnPath will be exceeded. Is it correct?

I am currently working on a checker but have some false positive cases due to the behaviors of the loops you mentioned earlier. A simple example (simplified from a real FP) would be like:

typedef int mx_status_t;
typedef __typeof__(sizeof(int)) mx_handle_t;

mx_status_t mx_channel_create(
   uint32_t options,
   mx_handle_t* out0,
   mx_handle_t* out1);

mx_status_t mx_handle_close(mx_handle_t handle);

void func_with_loop(mx_handle_t h, int loop_times) {
  mx_handle_close(h);
  for (int i = 0; i < loop_times; ++i) {
    // Some unrelated body
  }
}

void func_call_loop(int loop_times) {
  mx_handle_t sa, sb;
  mx_channel_create(0, &sa, &sb);
  // Some unrelated body
  func_with_loop(sa, loop_times);
  mx_handle_close(sb);
}

The function mx_channel_create() will allocate two handles (you can think it is like a file descriptor) and save them to the pointers pointed by out1 and out2. Function mx_handle_close() will release the handle passed in. My checker is basically looking for paths that a handle is allocated but not released, which is very similar to the SimpleStreamChecker in the clang.

In the code example above, the handle is properly released in every path. However, as the loop condition of the for loop in function func_with_loop cannot be determined, the maxBlockVisitOnPath will be exceeded and the "replaying-without-inlining" feature will kick in. So there exists paths that func_with_loop is not inlined, which in this case, the handle in sa is not considered as released at the end of analysis and the checker will report a leak.

Is it possible to detect this type of false positives and not to report them within a checker? Is so, what callbacks and APIs should I use? Or for this special case, there is nothing I can do in a checker to fix this issue unless I modified the way ExprEngine evaluates a loop?

The source code of the checker I am working on can be found here: https://gist.github.com/zeroomega/0a2abb371d85ff0444a8a9562d119b80 . It is still under development so contains a lot of debug code. 

Thanks,
Haowei


On Sun, Jun 25, 2017 at 5:51 AM, Péter Szécsi <[hidden email]> wrote:
Hello Haowei,

You described most of the behaviors right but not exactly.


When I run clang static analyzer on this piece of code with scan-build, the function "func_with_loop()" will not be inlined by ExprEngine.

The func_with_loop() function will be inlined for sure. That is what your example has just proven by producing the line:
 
testmxchannel.c:204:3func_with_loop  Should inline: Direct inlined

So it will be inlined. Lets considering the next important line in the output:
 
Block Count exceeded maxBlockVisitOnPath 4Dump SRC
...
testmxchannel.c:204:3func_with_loop  InlinedFailedState is not null  Should not inline 
 
It seems that the ExprEngine did try to inline the function "func_with_loop", but the total block count of this function exceeded "maxBlockVisitOnPath", which by default is 4. The inline process was rolled back and this function is evaluated by "conservativeEvalCall".
 
Yeah. that is what happens BUT! only on the PATH where the maxBlockVisitOnPath exceeded. So the other paths will be simulated but this path will be rolled back before the point where the analyzer inline the function and mark the function not to be inlined again (NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE)). So simulating again that path will trigger the defaultEvalCall on the same function call which was just rolled back and marked so the analyzer won't inline it. That is what is checked by the getInlineFailedState() and that is the reason why the 2. output says it should not be inlined.

In my understanding, by default, when clang static analyzer evaluate a loop that the total times of the loop cannot determined, the loop will be evaluated for 4 times and an additional ExplodedNode will be created with the loop condition evaluated to false. But why in this code example it causes the function inline to be rolled back instead of creating an additional node that evaluate the loop conditions to false?

Not exactly. The ExplodedGraph will be forked every time when the loop condition is evaluated. So there will be 5 different paths int ExplodedGraph while simulating a loop like this:
- when the condition is false
- when the condition is false after the 1. step
- when the condition is false after the 2. step
- when the condition is false after the 3. step
- when the condition is true every time - but this will be the path where the maxBlockVisitOnPath exceeds and then the above mentioned things happen.

Why is it important to replay the analysis without inlining this function which contains a loop?
The most problematic case is when the bound is known so the analyzer won't create new branches for paths where the condition can be false if it knows it can't be. For example if you try out a code like this:

void func_with_loop(int loop_times) {
  for (int i = 0; i < loop_times; i++) {
    //Do nothing
  }
}

void call_loop() {
  func_with_loop(12);
  ... //the most complex body you can just imagine
}

In this case (without the replaying-without-inlining feature) the analysis of this call_loop function would be ended while analyzing the inlined func_with_loop() function and exceeding the maxBlockVisitOnPath. Which is not something you would like to see so the state is going to be rolled back and the other parts of the function will be analyzed but without knowing what the func_with_loop() function did (so yes, with more unknown value).
 
Another question I have is that is it possible in checkPreCall() callback of a checker to determine if the function call will not be inlined by ExprEngine? 

I would be surprised if you can check that in checkPreCall() but maybe somebody else (probably NoQ) knows a way to check this.  (in checkPostCall() you can do this for sure by checking the wasInlined flag of the CheckerContext.)

I hope I could help at least a little bit.

Cheers,
Peter


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [StaticAnalyzer] Question about IPA function call inlining

Xin Wang via cfe-dev
Generally, your checker needs to be able to handle calls like "foo(sa)",
where "foo()" isn't inlined but closes "sa". This has nothing to do with
loops - when "foo()" isn't inlined for whatever reason, on a certain
path, and "sa" *escapes* into "foo()" (which means that "foo()" may
potentially access the value of "sa" within its unavailable body), the
checker should stop tracking "sa", avoiding the false positive.

In SimpleStreamChecker this is accomplished in checkPointerEscape()
callback. Unfortunately, your handles are not pointers, so it may not
work as expected. It's a known issue that checkPointerEscape() doesn't
work for non-pointers; i believe it should be extended to work with
non-pointers; it shouldn't be hard; but currently no checkers use it for
non-pointers, so nobody has fixed this problem so far.

P.S. In case you have any plans for contributing the checker back to the
mainline analyzer, it's a great idea to start early and submit it in
small chunks to phabricator, which we can discuss and help you with
potential issues - it should be significantly easier than contributing a
finished checker.

On 6/27/17 2:35 AM, Haowei Wu via cfe-dev wrote:

> Hi Peter,
>
> Thanks for you clarification, it helps a lot. If I understood
> correctly, for following code:
>
> void func_with_loop(int tag) {
>   for (int i = 0; i < 12; i++) {
>     // Do nothing
>   }
>   // Some complex body
> }
>
> If the func_with_loop() is a top level function, the code after the
> for loop will not be evaluated at all because maxBlockVisitOnPath will
> be exceeded. Is it correct?
>
> I am currently working on a checker but have some false positive cases
> due to the behaviors of the loops you mentioned earlier. A simple
> example (simplified from a real FP) would be like:
>
> typedef int mx_status_t;
> typedef __typeof__(sizeof(int)) mx_handle_t;
>
> mx_status_t mx_channel_create(
>    uint32_t options,
>    mx_handle_t* out0,
>    mx_handle_t* out1);
>
> mx_status_t mx_handle_close(mx_handle_t handle);
>
> void func_with_loop(mx_handle_t h, int loop_times) {
>   mx_handle_close(h);
>   for (int i = 0; i < loop_times; ++i) {
>     // Some unrelated body
>   }
> }
>
> void func_call_loop(int loop_times) {
>   mx_handle_t sa, sb;
>   mx_channel_create(0, &sa, &sb);
>   // Some unrelated body
> *func_with_loop*(sa, loop_times);
>   mx_handle_close(sb);
> }
>
> The function mx_channel_create() will allocate two handles (you can
> think it is like a file descriptor) and save them to the pointers
> pointed by out1 and out2. Function mx_handle_close() will release the
> handle passed in. My checker is basically looking for paths that a
> handle is allocated but not released, which is very similar to the
> SimpleStreamChecker in the clang.
>
> In the code example above, the handle is properly released in every
> path. However, as the loop condition of the for loop in function
> func_with_loop cannot be determined, the maxBlockVisitOnPath will be
> exceeded and the "replaying-without-inlining" feature will kick in. So
> there exists paths that func_with_loop is not inlined, which in this
> case, the handle in sa is not considered as released at the end of
> analysis and the checker will report a leak.
>
> Is it possible to detect this type of false positives and not to
> report them within a checker? Is so, what callbacks and APIs should I
> use? Or for this special case, there is nothing I can do in a checker
> to fix this issue unless I modified the way ExprEngine evaluates a loop?
>
> The source code of the checker I am working on can be found here:
> https://gist.github.com/zeroomega/0a2abb371d85ff0444a8a9562d119b80 .
> It is still under development so contains a lot of debug code.
>
> Thanks,
> Haowei
>
>
> On Sun, Jun 25, 2017 at 5:51 AM, Péter Szécsi <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Hello Haowei,
>
>     You described most of the behaviors right but not exactly.
>
>
>         When I run clang static analyzer on this piece of code with
>         scan-build, the function "func_with_loop()" will not be
>         inlined by ExprEngine.
>
>     The func_with_loop() function will be inlined for sure. That is
>     what your example has just proven by producing the line:
>
>         testmxchannel.c:204:3func_with_loop  Should inline: Direct inlined
>
>
>     So it will be inlined. Lets considering the next important line in
>     the output:
>
>         Block Count exceeded maxBlockVisitOnPath 4Dump SRC
>         ...
>         testmxchannel.c:204:3func_with_loop  InlinedFailedState is not
>         null  Should not inline
>
>         It seems that the ExprEngine did try to inline the function
>         "func_with_loop", but the total block count of this function
>         exceeded "maxBlockVisitOnPath", which by default is 4. The
>         inline process was rolled back and this function is evaluated
>         by "conservativeEvalCall".
>
>
>     Yeah. that is what happens BUT! only on the *PATH* where the
>     maxBlockVisitOnPath exceeded. So the other paths will be simulated
>     but this path will be rolled back before the point where the
>     analyzer inline the function and mark the function not to be
>     inlined again
>     (/NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt
>     *>(CE)/). So simulating again that path will trigger the
>     defaultEvalCall on the same function call which was just rolled
>     back and marked so the analyzer won't inline it. That is what is
>     checked by the /getInlineFailedState() /and that is the reason why
>     the 2. output says it should not be inlined/.
>     /
>
>         In my understanding, by default, when clang static analyzer
>         evaluate a loop that the total times of the loop cannot
>         determined, the loop will be evaluated for 4 times and an
>         additional ExplodedNode will be created with the loop
>         condition evaluated to false. But why in this code example it
>         causes the function inline to be rolled back instead of
>         creating an additional node that evaluate the loop conditions
>         to false?
>
>     Not exactly. The ExplodedGraph will be forked every time when the
>     loop condition is evaluated. So there will be 5 different paths
>     int ExplodedGraph while simulating a loop like this:
>     - when the condition is false
>     - when the condition is false after the 1. step
>     - when the condition is false after the 2. step
>     - when the condition is false after the 3. step
>     - when the condition is true every time - but this will be the
>     path where the maxBlockVisitOnPath exceeds and then the above
>     mentioned things happen.
>
>     Why is it important to replay the analysis without inlining this
>     function which contains a loop?
>     The most problematic case is when the bound is known so the
>     analyzer won't create new branches for paths where the condition
>     can be false if it knows it can't be. For example if you try out a
>     code like this:
>
>     void func_with_loop(int loop_times) {
>       for (int i = 0; i < loop_times; i++) {
>     //Do nothing
>       }
>     }
>
>     void call_loop() {
>     func_with_loop(12);
>       ... //the most complex body you can just imagine
>     }
>
>     In this case (without the replaying-without-inlining feature) the
>     analysis of this call_loop function would be ended while analyzing
>     the inlined func_with_loop() function and exceeding
>     themaxBlockVisitOnPath. Which is not something you would like to
>     see so the state is going to be rolled back and the other parts of
>     the function will be analyzed but without knowing what the
>     func_with_loop() function did (so yes, with more unknown value).
>
>         Another question I have is that is it possible in
>         checkPreCall() callback of a checker to determine if the
>         function call will not be inlined by ExprEngine?
>
>     I would be surprised if you can check that in checkPreCall() but
>     maybe somebody else (probably NoQ) knows a way to check this.  (in
>     checkPostCall() you can do this for sure by checking the
>     wasInlined flag of the CheckerContext.)
>
>     I hope I could help at least a little bit.
>
>     Cheers,
>     Peter
>
>
>
>
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Loading...