[cfe-dev] Refactoring the dominators patch for Clang

Mon Nov 28 11:35:07 PST 2011

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/20111128/3f2dee3c/attachment.html>