[cfe-dev] Constructing use-def chains

[Simone Pellegrini]

Hi again,
Here it is my current implementation of DefUse chain analysis. I adjust 
the code to be compliant with some of the clang rules (I had some 
problem in switching from std::map to llvm::DenseMap and I will try to 
better investigate this issue in the future).

So as this is not a patch, but a complete new feature I don't know where 
it should be placed in the source tree (clang/Analysis seems fine), so I 
will let u decide. The analysis is composed by 2 files DefUse.h and 
DefUse.cpp which represent respectively the interface and the 
implementation of the DefUse analysis. The usage of DefUse is very 
similar to CFG. You build the all DefUse chains for a specific piece of 
code (usually a function body) and then u start querying the object.

#include "DefUse.h"
using namespace defuse;

clang::FunctionDecl* fd = ...
DefUse* DU = DefUse::BuildDefUseChains(fd->getBody(), astCtx);

now if we have a reference to a variable inside the function body 
(usually a DeclRefExpr) we can query the DefUse object to know if the 
VarRef is a "definition" or an "use":

DeclRefExpr* DR = ...
DU->isDef(DR);
DU->isUse(DR);

Now if our variable is a "definition" for example we can iterate among 
all the uses referred to the definition in the following way:
for(DefUse::uses_iterator I = DU->uses_begin(DR), E = DU->uses_end(); I 
!= E, I++){
    DeclRefExpr* U = *I;
    ...
}

If the variable is a use, we can iterate among all the definitions:
for(DefUse::defs_iterator I = DU->defs_begin(DR), E = DU->defs_end(); I 
!= E, I++){
   ...
}
here the problem is that a definition can be either a DeclRefExpr in 
situations like:
-> a = s; // this is a definition for var. a

or a VarDecl in situations like:
-> int a; // this is a definition for variable a

For these reasons I have introduced a wrapper class called DefUseNode 
(the name can be changed) that can contains VarDecls or DeclRefExprs.

And that's the basic usage of DefUse.

A more advanced use is also possible, I don't want to go into the 
details of the algorithm used to compute the defuse chains, but you can 
imagine it divided into 2 steps. In the first steps all the variable 
references are collected and marked as definitions or uses depending on 
the semantic of the instruction and then, in the second step, this 
informations are elaborated in order to build the graph.
We can discuss about it but It comes out that marking the use of a 
variable can depends from the context, and the semantics can be 
different. For example if we are calling a function and the variable is 
passed as a reference or pointer we have to assume that this is a 
definition for the variable, but if we know the semantics of the 
function and we are sure the variable is not modified in the function 
body we can "risk" a little and mark the variable as an use. For this 
reason different semantics can be defined by the user in order to cover 
specific cases.

This is possible by extending the DefUseBasicHelper. The basic helper 
already implements the default semantics (a very conservative one) but 
it exposes some virtual methods that can be extended by the user who 
wants to implement a different behavior. The helper should be passed to 
the BuildDefUseChain method in this way:

DefUseCustomHelper helper;
DefUse* DU = DefUse::BuildDefUseChains(fd->getBody(), astCtx, &helper);
...

At last, I added a class to test the algorithm DefUseChainTest. I 
produces a lot of output (badly formatted) but you can easily see how ( 
and if :) ) the whole analysis works just by:
defuse::DefUseChainTest Consumer(llvm::outs());
...
ParseAST(PP, Consumer, *ContextOwner, false);

The test class is also meant to be an example of how to use the DefUse.

N.B.: As I already stated in my previous emails it is important (when 
and if the patch will be committed in the CLANG source tree) the 
institution where I am working, the "University of Innsbruck", and if 
possible my name (Simone Pellegrini) appear in the CREDITS.TXT file as 
contributors for this type of analysis.

have fun with DefUses, cheers Simone

P.S.: Unfortunately next week I will be on a business trip so not 
reachable. I will reply and address your comments/feedbacks as soon as I 
am back in the office.

Ted Kremenek wrote:
>
> On Sep 3, 2009, at 9:44 AM, John McCall wrote:
>
>> Simone Pellegrini wrote:
>>> Hello again,
>>> I guess I solved the issue with my university, everything is fine if 
>>> our
>>> contributions will be listed in the CREDITS.txt file.
>>>
>>
>> Excellent.
>>
>>> So, once I modified the code to be compliant with the LLVM coding 
>>> rules,
>>> where or to who should I send the code for the reviewing process?
>>>
>>
>> To this list, preferably.
>>
>> John.
>
> We actually prefer patches to be sent to cfe-commits, but cfe-dev is 
> fine too:
>
>   http://clang.llvm.org/hacking.html#patches

-------------- next part --------------
A non-text attachment was scrubbed...
Name: DefUse.h
Type: text/x-chdr
Size: 7893 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20090904/4608add1/attachment.h>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DefUse.cpp
Type: text/x-c++src
Size: 31839 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20090904/4608add1/attachment.cpp>