[cfe-dev] Refactoring the dominators patch for Clang

[Guoping Long]

Hi, Anna, Ted

  Thanks for your link. Attached is another refactoring, using only
GraphTraits to implement all this functionality. Please let me know your
comments.
--
Guoping

2011/11/12 Anna Zaks <ganna at apple.com>

> I was thinking of something similar to PathDiagnostic.h:523 (
> http://clang.llvm.org/doxygen/PathDiagnostic_8h_source.html)
>
> Anna.
>
> On Nov 12, 2011, at 6:23 PM, Guoping Long wrote:
>
> Anna,
>
> Sounds like a good idea to provide a custom iterator for CFG. But how to
> achieve that?
> CFG iterator is defined as BumpVector<CFGBlock*>::iterator, do you mean
> makes a custom iterator as BumpVector<CFGBlock>::iterator? It's easy to
> implement begin()/end(), but how to implement ++ operator? All CFGBlocks
> are stored as CFGBlock* in BumpVector, do you mean also maintaining another
> vector of CFGBlocks, ex: BumpVector<CFGBlock>? That will also be very messy.
>
> --
> Guoping
>
> 2011/11/12 Anna Zaks <ganna at apple.com>
>
>> Hi Guoping,
>>
>> I propose to use a 3d solution.
>>
>> What we need is to change the clang::CFG GraphTraits to have
>> the nodes_iterator type consistent with that of Function's GraphTraits. As
>> I pointed out in one of the previous emails, they are currently not
>> consistent even in terms of NodeType (which is a type internal to traits) -
>> one iterates over NodeType and another over NodeType*. This can be
>> implemented by adding a a custom iterator for CFG which returns CFGBlock*
>> (instead of CFGBlock**). Then, you define nodes_iterator as your new
>> iterator.
>>
>> Cheers,
>> Anna.
>> On Nov 12, 2011, at 1:35 PM, Guoping Long wrote:
>>
>> Hi, Anna
>>
>>    I am doing the refactoring only using GraphTraits.  Here is the
>> problem: We still need to deal with the difference between the iterator
>> implementation of CFG and Function. The fundamental reason for this
>> difference is that CFG used BumpVector, while the Function class used
>> iplist.  There are two possible solutions to this problem:
>>
>>   1. As you pointed out, let's change the CFG design to use iplist
>> instead of BumpVector. But for me, this may seem unnecessarily intrusive to
>> Clang.
>>   2. In the GraphTraits class, let's provide a convert routine to do the
>> iterator to Block conversion. For example, in GraphTraits<CFG*>, let's add
>> this:
>>       static NodeType *I2B(node_iterator I) {
>>         return *I;
>>       }
>>   In this way, we can still conceal all implementation details in
>> GraphTraits. But this may make the GraphTraits a little messy. Please let
>> me know your comments. Which approach should be better?
>>
>> ----
>> Guoping
>>
>> 2011/11/8 Guoping Long <longguoping at gmail.com>
>>
>>> Hi, Ted, Anna
>>>
>>>    Thanks. Now I think I understand the design rationale behind
>>> GraphTraits. I will do another refactoring later this week.
>>>
>>> --
>>> Guoping
>>>
>>> 2011/11/7 Ted Kremenek <kremenek at apple.com>
>>>
>>>>  On Nov 7, 2011, at 9:10 PM, Anna Zaks wrote:
>>>>
>>>>
>>>> On Nov 7, 2011, at 7:08 PM, Ted Kremenek wrote:
>>>>
>>>> On Nov 3, 2011, at 10:50 AM, Ted Kremenek wrote:
>>>>
>>>> On Nov 2, 2011, at 4:23 PM, Anna Zaks wrote:
>>>>
>>>> On llvm's side, it would involve changing the recalculate function to
>>>> use getEntryBlock instead of front(). Looks like they are the same thing.
>>>>
>>>> On Clang's side, we could just rename CFG::getEntry()  ->
>>>> CFG::getEntryBlock().
>>>>
>>>>
>>>> Both of these seem reasonable to me.
>>>>
>>>>
>>>> Looking back at this comment, I think the Dominators algorithm should
>>>> not rely on the existence of a 'getEntryBlock()' and really just being
>>>> using GraphTraits that can get the entrance of the graph.  We shouldn't
>>>> have to rename anything in the CFG just to get the dominators analysis to
>>>> work.  If we are missing a concept, that is one thing, but renaming
>>>> something means that the dominators analysis is relying on particular
>>>> methods being present.  That just feels really wrong to me.  As I mentioned
>>>> in another email I just sent, there is also no reason for the dominators
>>>> analysis to have any notion of "basic blocks" either since it is a generic
>>>> graph algorithm.
>>>>
>>>>
>>>> Ted, this comment is from before Guoping pointed out that this function
>>>> name is not the only inconsistency between Function and CFG (at that point
>>>> it seemed fine to just make a simple change to get the patch through). With
>>>> the new approach, where we change the dominators to use GraphTraits, it
>>>> will handle this case as well. There is getEntryBlock() method in the
>>>> GraphTraits.
>>>>
>>>>
>>>> Indeed.  I figured this would be handled by using GraphTraits for
>>>> everything, but I wanted to amend my previous comment for posterity.  :)
>>>>
>>>> _______________________________________________
>>>> cfe-dev mailing list
>>>> cfe-dev at cs.uiuc.edu
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>>>>
>>>>
>>>
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111118/64e4ea5d/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dominators-clang.patch
Type: application/octet-stream
Size: 18397 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111118/64e4ea5d/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dominators-llvm.patch
Type: application/octet-stream
Size: 3583 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111118/64e4ea5d/attachment-0001.obj>