Dataflow analysis with Libtooling and LiveVariables

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

Dataflow analysis with Libtooling and LiveVariables

Saheel Godhane
Hello everyone!

I am a PhD student and have been working with Clang with the aim to do an intra-procedural dataflow analysis. I am aware of a recent discussion on this mailing list regarding the same but my questions are slightly more specific. Pardon me if this is the wrong forum to ask them, but anyway, here they are:

1. Implementation question

I have been trying to use the Libtooling clang interface (based on this tutorial) and the existing LiveVariables analysis. My goal is to answer the question: given a VarDecl, is it live at a particular SourceLocation? (is this even possible with LiveVariables, which somehow looks like block-level liveness analysis?)

So far, although I have been able to get some code on a LiveVariables analysis working, it is not displaying the expected result. Specifically, I have overridden VisitFunctionDecl() so as to calculate a LiveVariables analysis on every function. When I dump the live values, it shows correctly all the blocks in my function but it doesn't show any of the live variables. I tried using "clang -cc1 -analyze -analyzer-checker=debug.DumpLiveVars test.c" which works as expected, displaying all the variables live in different blocks.

Here is my code for VisitFunctionDecl. Pastebin version here. Full cpp file for my clang tool here.

virtual bool VisitFunctionDecl(FunctionDecl *func) {
    errs() << "Inside " << ++numFunctions << " " << func->getNameInfo().getName().getAsString() << "\n";

    clang::AnalysisDeclContextManager *ADCM = new clang::AnalysisDeclContextManager(false, true, true, true, true, true);
    clang::AnalysisDeclContext *func_ADC = ADCM->getContext(func);
    clang::LiveVariables *func_LV = clang::LiveVariables::computeLiveness(*func_ADC, false);
    clang::LiveVariables::Observer *obs = new clang::LiveVariables::Observer();

    func_LV->runOnAllBlocks(*obs);
    func_LV->dumpBlockLiveness((func_ADC->getASTContext()).getSourceManager());

    return true;
}

Surely I am missing something here but I am not able to figure out. Perhaps my instantiation of AnalysisDeclContextManager is incorrect?
I started out with overriding VisitVarDecl() in the RecursiveASTVisitor but then realized that to call LiveVariables::computeLiveness() I need an AnalysisDeclContext object which works only with block-level declarations (am I correct?), so switched to VisitFunctionDecl().

Any help on how to get this working, or whether I should just switch over to writing a Checker, will be greatly appreciated! :)

Sincerely,
Saheel.


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Dataflow analysis with Libtooling and LiveVariables

Manuel Klimek
On Fri Dec 05 2014 at 1:44:04 AM Saheel Godhane <[hidden email]> wrote:
Hello everyone!

I am a PhD student and have been working with Clang with the aim to do an intra-procedural dataflow analysis. I am aware of a recent discussion on this mailing list regarding the same but my questions are slightly more specific. Pardon me if this is the wrong forum to ask them, but anyway, here they are:

1. Implementation question

I have been trying to use the Libtooling clang interface (based on this tutorial) and the existing LiveVariables analysis. My goal is to answer the question: given a VarDecl, is it live at a particular SourceLocation? (is this even possible with LiveVariables, which somehow looks like block-level liveness analysis?)

+Anna for the LiveVariables question.
 
So far, although I have been able to get some code on a LiveVariables analysis working, it is not displaying the expected result. Specifically, I have overridden VisitFunctionDecl() so as to calculate a LiveVariables analysis on every function. When I dump the live values, it shows correctly all the blocks in my function but it doesn't show any of the live variables. I tried using "clang -cc1 -analyze -analyzer-checker=debug.DumpLiveVars test.c" which works as expected, displaying all the variables live in different blocks.

Here is my code for VisitFunctionDecl. Pastebin version here. Full cpp file for my clang tool here.

virtual bool VisitFunctionDecl(FunctionDecl *func) {
    errs() << "Inside " << ++numFunctions << " " << func->getNameInfo().getName().getAsString() << "\n";

    clang::AnalysisDeclContextManager *ADCM = new clang::AnalysisDeclContextManager(false, true, true, true, true, true);
    clang::AnalysisDeclContext *func_ADC = ADCM->getContext(func);
    clang::LiveVariables *func_LV = clang::LiveVariables::computeLiveness(*func_ADC, false);
    clang::LiveVariables::Observer *obs = new clang::LiveVariables::Observer();

    func_LV->runOnAllBlocks(*obs);
    func_LV->dumpBlockLiveness((func_ADC->getASTContext()).getSourceManager());

    return true;
}

Surely I am missing something here but I am not able to figure out. Perhaps my instantiation of AnalysisDeclContextManager is incorrect?
I started out with overriding VisitVarDecl() in the RecursiveASTVisitor but then realized that to call LiveVariables::computeLiveness() I need an AnalysisDeclContext object which works only with block-level declarations (am I correct?), so switched to VisitFunctionDecl().

Any help on how to get this working, or whether I should just switch over to writing a Checker, will be greatly appreciated! :)

That depends:
If what you want in the end is a static analysis check, then yes, write a checker. If you want  to drive refactorings from the results, then the right approach is libTooling; but as you discovered libTooling is not integrated well with the CFG yet (that needs some work)

 

Sincerely,
Saheel.

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Dataflow analysis with Libtooling and LiveVariables

Anna Zaks

On Dec 15, 2014, at 5:01 AM, Manuel Klimek <[hidden email]> wrote:

On Fri Dec 05 2014 at 1:44:04 AM Saheel Godhane <[hidden email]> wrote:
Hello everyone!

I am a PhD student and have been working with Clang with the aim to do an intra-procedural dataflow analysis. I am aware of a recent discussion on this mailing list regarding the same but my questions are slightly more specific. Pardon me if this is the wrong forum to ask them, but anyway, here they are:

1. Implementation question

I have been trying to use the Libtooling clang interface (based on this tutorial) and the existing LiveVariables analysis. My goal is to answer the question: given a VarDecl, is it live at a particular SourceLocation? (is this even possible with LiveVariables, which somehow looks like block-level liveness analysis?)

+Anna for the LiveVariables question.

LiveVariables operates on the front-end CFG, which contains the references to the AST nodes in its basic blocks.  You should be getting precise liveness information for every statement. 

LiveVariables is currently used by the DeadStoresChecker, so that would be a good point of reference. DeadStoresChecker talks to the LiveVariables through the Observer.

 
So far, although I have been able to get some code on a LiveVariables analysis working, it is not displaying the expected result. Specifically, I have overridden VisitFunctionDecl() so as to calculate a LiveVariables analysis on every function. When I dump the live values, it shows correctly all the blocks in my function but it doesn't show any of the live variables. I tried using "clang -cc1 -analyze -analyzer-checker=debug.DumpLiveVars test.c" which works as expected, displaying all the variables live in different blocks.

Here is my code for VisitFunctionDecl. Pastebin version here. Full cpp file for my clang tool here.

virtual bool VisitFunctionDecl(FunctionDecl *func) {
    errs() << "Inside " << ++numFunctions << " " << func->getNameInfo().getName().getAsString() << "\n";

    clang::AnalysisDeclContextManager *ADCM = new clang::AnalysisDeclContextManager(false, true, true, true, true, true);
    clang::AnalysisDeclContext *func_ADC = ADCM->getContext(func);
    clang::LiveVariables *func_LV = clang::LiveVariables::computeLiveness(*func_ADC, false);
    clang::LiveVariables::Observer *obs = new clang::LiveVariables::Observer();

In order to use the observer, you need to implement your own observer here which will get notified on observeStmt. 


    func_LV->runOnAllBlocks(*obs);
    func_LV->dumpBlockLiveness((func_ADC->getASTContext()).getSourceManager());

I am not sure why liveness information is not dumped... I would try to debug this as well as the analyzer's version to see what's missing.


    return true;
}

Surely I am missing something here but I am not able to figure out. Perhaps my instantiation of AnalysisDeclContextManager is incorrect?
I started out with overriding VisitVarDecl() in the RecursiveASTVisitor but then realized that to call LiveVariables::computeLiveness() I need an AnalysisDeclContext object which works only with block-level declarations (am I correct?), so switched to VisitFunctionDecl().

Any help on how to get this working, or whether I should just switch over to writing a Checker, will be greatly appreciated! :)

That depends:
If what you want in the end is a static analysis check, then yes, write a checker. If you want  to drive refactorings from the results, then the right approach is libTooling; but as you discovered libTooling is not integrated well with the CFG yet (that needs some work)

+1


 

Sincerely,
Saheel.

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Dataflow analysis with Libtooling and LiveVariables

Saheel Godhane
Thank you so much for your replies! Please find my comments below.

On Mon, Dec 15, 2014 at 2:10 PM, Anna Zaks <[hidden email]> wrote:

On Dec 15, 2014, at 5:01 AM, Manuel Klimek <[hidden email]> wrote:

LiveVariables operates on the front-end CFG, which contains the references to the AST nodes in its basic blocks.  You should be getting precise liveness information for every statement.

LiveVariables is currently used by the DeadStoresChecker, so that would be a good point of reference. DeadStoresChecker talks to the LiveVariables through the Observer.

Hmm... I noticed that DebugChecker also uses LiveVariables (though very slightly), so taking that as a reference I wrote a checker and have been able to get statement level liveness information.

By the way, is there def-use and use-def chains also implemented (used?) in Clang? At least, I couldn't find it anywhere.
 

I am not sure why liveness information is not dumped... I would try to debug this as well as the analyzer's version to see what's missing.

Debug using GDB? Or is there is an easier way? I tried GDB but as usual it was a bit messy, so I gave up and started writing a checker.
 
Surely I am missing something here but I am not able to figure out. Perhaps my instantiation of AnalysisDeclContextManager is incorrect?
I started out with overriding VisitVarDecl() in the RecursiveASTVisitor but then realized that to call LiveVariables::computeLiveness() I need an AnalysisDeclContext object which works only with block-level declarations (am I correct?), so switched to VisitFunctionDecl().

Any help on how to get this working, or whether I should just switch over to writing a Checker, will be greatly appreciated! :)

That depends:
If what you want in the end is a static analysis check, then yes, write a checker. If you want  to drive refactorings from the results, then the right approach is libTooling; but as you discovered libTooling is not integrated well with the CFG yet (that needs some work)

Thanks for the hint! Indeed, all I want to do is some static analysis. And I am finding writing a checker quite easy and useful for that purpose.

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Dataflow analysis with Libtooling and LiveVariables

Ted Kremenek

On Dec 15, 2014, at 3:34 PM, Saheel Godhane <[hidden email]> wrote:

By the way, is there def-use and use-def chains also implemented (used?) in Clang? At least, I couldn't find it anywhere.
 

Sorry for the late response, but to answer this specific question there is no def-use or use-def chains implemented in Clang.

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev