[cfe-dev] Refactoring the dominators patch for Clang
Guoping Long
longguoping at gmail.com
Wed Nov 30 15:06:01 PST 2011
Also, I have submitted the llvm side patch to llvm-commits for review.
--
Guoping
2011/11/30 Guoping Long <longguoping at gmail.com>
> 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/5583eac9/attachment.html>
More information about the cfe-dev
mailing list