[analyzer] "runCheckersForEndFunction()" is not guaranteed to be called at the end of each path?

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[analyzer] "runCheckersForEndFunction()" is not guaranteed to be called at the end of each path?

David Chisnall via cfe-dev
Hi all,
"runCheckersForEndFunction()" is called after "removeDeadOnEndOfFunction()" call, see https://github.com/llvm-mirror/clang/blob/master/lib/StaticAnalyzer/Core/ExprEngine.cpp#L1948. "removeDeadOnEndOfFunction()" calls "getNode()", and "getNode()"supports node deduplication, so the "Dst" is may be empty after "removeDeadOnEndOfFunction(NodeBuilder, Pre, Dst)" has been executed. And "runCheckersForEndFunction()" will not be called if "Dst" set is empty.

=======================================code snippets======================================
int foo(int a, int b)
{
if (a && b)
return a + b;
if(b)
return b;
return 0;
}
========================================================================================

For the above code, "runCheckersForEndFunction()" will only be executed twice. In view of the fact that the comments of "runCheckersForEndFunction()" is "Run Checkers for end of path",  is it reasonable that "runCheckersForEndFunction()" is not called at the end of all paths?

Thanks,
Henry Wong

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

Re: [analyzer] "runCheckersForEndFunction()" is not guaranteed to be called at the end of each path?

David Chisnall via cfe-dev
Yeah, it's called at the end of every complete path, but there are less
paths than you'd expect, because the return value is irrelevant and gets
discarded (since we'd never see the caller during analysis), and then
paths get deduplicated based on that. So it's not the correct way to
enumerate possible function exits - it's merely a notification that the
analysis is exiting a function right now. For the same reason, all other
path event callbacks such as PreStmt would not be called separately for
every path that reaches that event, but only for the particular node on
which the event happens.

You may see how the ExplodedGraph changes when you add a caller, i.e.:

$ cat -n test.c
      1    int foo(int a, int b) {
      2      if (a && b)
      3        return a + b;
      4      if (b)
      5        return b;
      6      return 0;
      7    }
      8
      9    int bar(int a, int b) {
     10      return foo(a, b);
     11    }

$ clang -cc1 -analyze -analyzer-display-progress -analyzer-checker
core,debug.DumpTraversal test.c

ANALYZE (Syntax): test.c foo
ANALYZE (Syntax): test.c bar
ANALYZE (Path,  Inline_Regular): test.c bar
--BEGIN FUNCTION--
--BEGIN FUNCTION--
2 BinaryOperator
4 IfStmt
--END FUNCTION--
--END FUNCTION--
--END FUNCTION--
--END FUNCTION--
2 BinaryOperator
4 IfStmt
--END FUNCTION--
--END FUNCTION--
--END FUNCTION--

(see -analyzer-viz-egraph-graphviz to visualize the actual exploded graph)

There may also be incomplete paths, which were terminated before
reaching the end of the function (eg. maximum exploded graph size
exceeded), and there may also be exits from the function that were never
reached during analysis (because all of their respective paths were
terminated before that happened).

Also your question looks suspicious to me in the sense that you might be
trying to do something that's either not going to work or can be done a
lot easier.

Also you might want to have a look at checkEndAnalysis which is called
only once per analysis and provides the fully constructed ExplodedGraph
to traverse, explore, or gather whatever statistics you want.

On 11/3/17 12:02 PM, Henry Wong via cfe-dev wrote:

> Hi all,
> "runCheckersForEndFunction()" is called after
> "removeDeadOnEndOfFunction()" call, see
> https://github.com/llvm-mirror/clang/blob/master/lib/StaticAnalyzer/Core/ExprEngine.cpp#L1948.
> "removeDeadOnEndOfFunction()" calls "getNode()", and
> "getNode()"supports node deduplication, so the "Dst" is may be empty
> after "removeDeadOnEndOfFunction(NodeBuilder, Pre, Dst)" has been
> executed. And "runCheckersForEndFunction()" will not be called if
> "Dst" set is empty.
>
> =======================================code
> snippets======================================
> int foo(int a, int b)
> {
> if (a && b)
> return a + b;
> if(b)
> return b;
> return 0;
> }
> ========================================================================================
>
> For the above code, "runCheckersForEndFunction()" will only be
> executed twice. In view of the fact that the comments of
> "runCheckersForEndFunction()" is "Run Checkers for end of path", is it
> reasonable that "runCheckersForEndFunction()" is not called at the end
> of all paths?
>
> Thanks,
> Henry Wong
>
>
> _______________________________________________
> 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
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] "runCheckersForEndFunction()" is not guaranteed to be called at the end of each path?

David Chisnall via cfe-dev
Hi Artem,
Thank you for taking the time to give me a detailed explanation. Your answer 
corrected my misunderstanding of the analyzer engine, especially the engine's 
behavior in the face of duplicate nodes. And I ignored that if the caller is not in 
the top frame, "runCheckersForEndFunction()" will always be executed. If I can 
be aware of this distinction, and continue to think about it, perhaps can 
understand.

Since checkEndAnalysis guarantees that it is always called, I'll consider using it 
instead of checkEndFunction.

Henry Wong
Qihoo 360 Codesafe Team

From: Artem Dergachev <[hidden email]>
Sent: Saturday, November 4, 2017 4:27
To: Henry Wong; [hidden email]
Subject: Re: [cfe-dev] [analyzer] "runCheckersForEndFunction()" is not guaranteed to be called at the end of each path?
 
Yeah, it's called at the end of every complete path, but there are less
paths than you'd expect, because the return value is irrelevant and gets
discarded (since we'd never see the caller during analysis), and then
paths get deduplicated based on that. So it's not the correct way to
enumerate possible function exits - it's merely a notification that the
analysis is exiting a function right now. For the same reason, all other
path event callbacks such as PreStmt would not be called separately for
every path that reaches that event, but only for the particular node on
which the event happens.

You may see how the ExplodedGraph changes when you add a caller, i.e.:

$ cat -n test.c
      1    int foo(int a, int b) {
      2      if (a && b)
      3        return a + b;
      4      if (b)
      5        return b;
      6      return 0;
      7    }
      8
      9    int bar(int a, int b) {
     10      return foo(a, b);
     11    }

$ clang -cc1 -analyze -analyzer-display-progress -analyzer-checker
core,debug.DumpTraversal test.c

ANALYZE (Syntax): test.c foo
ANALYZE (Syntax): test.c bar
ANALYZE (Path,  Inline_Regular): test.c bar
--BEGIN FUNCTION--
--BEGIN FUNCTION--
2 BinaryOperator
4 IfStmt
--END FUNCTION--
--END FUNCTION--
--END FUNCTION--
--END FUNCTION--
2 BinaryOperator
4 IfStmt
--END FUNCTION--
--END FUNCTION--
--END FUNCTION--

(see -analyzer-viz-egraph-graphviz to visualize the actual exploded graph)

There may also be incomplete paths, which were terminated before
reaching the end of the function (eg. maximum exploded graph size
exceeded), and there may also be exits from the function that were never
reached during analysis (because all of their respective paths were
terminated before that happened).

Also your question looks suspicious to me in the sense that you might be
trying to do something that's either not going to work or can be done a
lot easier.

Also you might want to have a look at checkEndAnalysis which is called
only once per analysis and provides the fully constructed ExplodedGraph
to traverse, explore, or gather whatever statistics you want.

On 11/3/17 12:02 PM, Henry Wong via cfe-dev wrote:
> Hi all,
> "runCheckersForEndFunction()" is called after
> "removeDeadOnEndOfFunction()" call, see
> https://github.com/llvm-mirror/clang/blob/master/lib/StaticAnalyzer/Core/ExprEngine.cpp#L1948.
> "removeDeadOnEndOfFunction()" calls "getNode()", and
> "getNode()"supports node deduplication, so the "Dst" is may be empty
> after "removeDeadOnEndOfFunction(NodeBuilder, Pre, Dst)" has been
> executed. And "runCheckersForEndFunction()" will not be called if
> "Dst" set is empty.
>
> =======================================code
> snippets======================================
> int foo(int a, int b)
> {
> if (a && b)
> return a + b;
> if(b)
> return b;
> return 0;
> }
> ========================================================================================
>
> For the above code, "runCheckersForEndFunction()" will only be
> executed twice. In view of the fact that the comments of
> "runCheckersForEndFunction()" is "Run Checkers for end of path", is it
> reasonable that "runCheckersForEndFunction()" is not called at the end
> of all paths?
>
> Thanks,
> Henry Wong
>
>
> _______________________________________________
> 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