[cfe-dev] Refactoring the dominators patch for Clang
Guoping Long
longguoping at gmail.com
Wed Nov 30 14:55:22 PST 2011
Hi, Anna
These comments are very helpful. Attached is the revised patch based on
your comments.
Please let me know if you have additional comments.
--
Guoping
2011/11/28 Anna Zaks <ganna at apple.com>
> Hi Guoping,
>
> Thanks for the new patch! Looks good overall. Below are some minor
> comments.
>
> Comments for the LLVM patch:
> 1) In include/llvm/Analysis/Dominators.h, use typedef instead of spelling
> out GraphTraits<FT*> each time it's used.
>
> 2) In include/llvm/Support/CFG.h, use unsigned instead of size_t to be
> consistent with Function::size().
>
> 3) The size function should probably be mentioned in the interface itself
> llvm/ADT/GraphTraits.h (not only in the template instantiations).
>
> 4) Please, send the llvm patch to llvm-commits <llvm-commits at cs.uiuc.edu>
> list for review.
>
> Comments on the clang patch:
> 1) I'd rather keep the old high level comments. For example, in
> Dominators.h we should specify what functionality the class/file provides,
> not how it's implemented (Specifically, this is an implementation detail:
> "A wrapper to LLVM dominators implementation"). You can provide
> implementation details as well, but avoid putting those in headlines. It's
> also better to use doxygen style comments:
> - /// changeImmediateDominator - This method is used to update the
> dominator
> - /// tree information when a node's immediate dominator changes.
> + /// \brief This method is used to update the dominator
> + /// tree information when a node's immediate dominator changes.
>
> 2) iterator2 is not a very descriptive name :)
>
> 3) size_t -> unsigned.
>
> 4) There are a few unused APIs in DominatorTree (Ex: splitBlock()).
> Ideally, we'd want to keep as many of them as possible and just add test
> cases exercising them. However, you can completely remove some if they
> don't seem very important; we can always add them in later on.
>
> Thanks!
> Anna.
>
> On Nov 18, 2011, at 7:32 PM, Guoping Long wrote:
>
> 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
>>>>>
>>>>>
>>>>
>>>
>>>
>>
>>
> <dominators-clang.patch><dominators-llvm.patch>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111130/952da313/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dominators-clang.patch
Type: application/octet-stream
Size: 17572 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111130/952da313/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dominators-llvm.patch
Type: application/octet-stream
Size: 4772 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111130/952da313/attachment-0001.obj>
More information about the cfe-dev
mailing list