[cfe-dev] Constructing use-def chains

[Simone Pellegrini]

Ted Kremenek wrote:
> Hi Simone,
>
> Sorry for reviewing this second set of changes so late.  Comments inline.
Hello,
as you see I am also late :), sorry but currently I am working on other 
aspects of program analysis and I have very little time to work in DefUse.

Anyway I am doing the changes you proposed:
>
> Where this is going to bite you is here:
>
>   typedef std::map<VarDecl const*, DefUseVect> DefUseChain;
>
> If you replace this with:
>
>   typedef llvm::DenseMap<VarDecl const*, DefUseVect> DefUseChain;
>
> then fundamentally things are going to break.  This because the 
> DefUseVect values, which is a typedef for std::vector<DefUseNode>, 
> will get copied and deallocated when the table resizes.  All 
> references to the DefUseVect, or the objects they contain, will 
> incorrect at this point.
>
> The solution is to use DefUseVect* instead of DefUseVect as the value 
> for DefUseChain.
I managed to get rid of the std::map in my implementation, I defined 
DefUseChain as:

typedef llvm::DenseMap<VarDecl const*, DefUseVect*> DefUseChain;

the only problem is that now in the destructor for the DefUse class I 
have to manually free the memory allocated in the heap, and that's ugly :)

I am looking forward to do something like: typedef 
llvm::DenseMap<VarDecl const*, llvm::OwningPtr<DefUseVect> > DefUseChain;
but OwiningPrt has no copy constructor and I need to do some major 
changes in the code.

Is there in LLVM something like the boost::shared_ptr?
>
> I think the approach should be to focus on a clean API.  Using 
> templates should be avoided unless there is a huge performance need; 
> the cost of virtual functions is low if the amount of work done in the 
> virtual function call outweighs the dynamic dispatch.
I still have to look into this issue!
>
>>
>> For the rest I properly formatted the code, for the test cases I have 
>> to learn how to write test cases for LLVM :)
>
> Take a look at the Clang tests in 'test/Analysis' and friends.  
> Basically we'll need to wire up a driver option to clang-cc, and 
> you'll want to run clang-cc on some code that outputs some diagnostics 
> relevant to def-use analysis.
>
I will
> More specific comments inline.
>
>> //===------------------------- Typedefs -------------------------===//
>> class DefUseBlock;
>> class VarDeclMap;
>> typedef std::vector<DefUseBlock> DefUseData;
>> typedef llvm::DenseMap<Stmt const*, unsigned> VarRefBlockMap;
>> typedef std::vector<DefUseNode> DefUseVect;
>> typedef std::vector<DefUseNode const*> VarRefsVect;
>
> Something looks potentially wrong here.  DefUseVect is a vector of 
> DefUseNode objects, not DefUseNode*.  If the vector ever needs to be 
> resized, then the DefUseNode objects will be obliterated, and any 
> references to them (which may be in VarRefVect) will suddenly become 
> invalid.  DefUseNode is a lightweight object that you can certainly 
> keep in a vector, but if you need these objects to have stable pointer 
> addresses you will need to manually allocate them and store 
> DefUseNode* instead DefUseVect instead.  If you are concerned with 
> 'malloc()' being too slow, you can use the BumpPtrAllocator in llvm to 
> quickly allocate objects.
You are completely write, that's a potential huge problem.

I get rid of the DefUseVect so not I keep only vector to pointers. This 
also allow me to do some simplifications inside the defs_iterator and 
uses_iterator
of course there is always the issue that I need to clean the memory when 
the DefUse object is deleted.

> Again, this is really great you're interested in contributing this 
> back, and I look forward to hearing your reply.
>
> Best,
> Ted
I will continue this work this week and probably at the beginning of the 
next week I will send you the code for another iteration.

There are several things I want to improve simplifying the overall 
implementation.

Thanks again for you style lessons, and see you in few days!
bye