[cfe-dev] Refactoring the dominators patch for Clang

[Guoping Long]

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/20111112/e551dfdb/attachment.html>