[cfe-dev] Refactoring the dominators patch for Clang

[Anna Zaks]

Hi Guoping,

Even though adding another method (getBlock()) to resolve the inconsistency is the least intrusive solution, it's not the cleanest one in my opinion. Ex: There is no interface that defines the API a graph class should implement to support the dominator computation. It's not a problem with your extension, but with the current dominator's implementation. The cleanest approach would be to change the dominators to only rely on GraphTraits. Though that would involve more work and I am not sure if you have the time to do it.

Cheers,
Anna.
On Nov 5, 2011, at 8:10 PM, Guoping Long wrote:

> Hi, Anna, Ted
> 
>   Here is the approach I finally take, which I believe shall be least intrusive to both clang and LLVM:
> The EntryBlock issue is easy to resolve, as you pointed out, I just changed the Clang's counterpart method into this name. Up to now, three classes involve dominators: the Function class, the Clang::CFG class, and the MachineFunction class. The MachineFunction class also does not have the getEntryBlock() method. It's trivial to just add this method into the class.
> 
> To deal with the iterator issue, either changing Clang or LLVM to use the other's iterator is too intrusive.  The approach I am using is simply an interface method. On the Clang side, add this method to the CFG class:
> CFGBlock *                getBlock(iterator I)   { return *I; }
> While on the LLVM side, adding this method to both Function and MachineFunction classes:
> BasicBlock *               getBlock(iterator I)   { return I; }
> This fixes the issue.
> 
> Attached is the final patch to both LLVM and Clang. Hopefully this could conclude the addition of the dominator tree support for Clang. Please let me know your comments.
> 
> Thanks!
> 
> ----
> Guoping
> 
> 2011/11/4 Anna Zaks <ganna at apple.com>
> Hi Guoping,
> 
> There are two possible solutions here. 
> 
> First solution is to rewrite the recompute() routine to use the following GraphTraits instead of passing in the Function/clang::CFG object:
> // From include/llvm/Support/CFG.h
> template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*>
> GraphTraits already has most of the APIs used by the dominator computation. However, it does not have the size() method, which is used in the Calculate() function called from recalculate(). That would mean that we would possibly need to extend the traits.. Then, we could change the clang::CFG GraphTraits to have the nodes_iterator type consistent with that of Function's GraphTraits. This change is much more intrusive on LLVM side.
> 
> Another solution is to change the iterator type in clang::CFG to match the Function iterator. 
> 
> As a side note,  it's a bit strange that the nodes_iterator types are inconsistent between clang::CFG and Function GraphTraits. They are defined as iterators of clang::CFG and Function respectively. Everything still works because the GraphWriter, which relies on the traits, has an overloaded writeNode() function which allows it to work with NodeType and NodeType*. But either solution would fix the inconsistency.
> 
> Ted, do you have any preferences?
> 
> Cheers,
> Anna.
> 
> 
> 
> On Nov 4, 2011, at 9:23 AM, Guoping Long wrote:
> 
>> Hi, Anna
>> 
>>   First, thank your for your time for commenting this code!
>>   There is one more subtle difference. This is the major one that ended up the code this way. It is the difference between CFGBlock::iterator and Function::iterator, as shown in the code excerpt below.
>> 
>> Function::iterator. Each iterator I is used directly as BasicBlock * here.
>>       // Initialize the roots list
>>       for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) {
>>         if (std::distance(GraphTraits<FT*>::child_begin(I),
>>                           GraphTraits<FT*>::child_end(I)) == 0)
>>           addRoot(I);
>> 
>> CFG::iterator. Each iterator has the CFGBlock ** type. In this case we need a pointer indirection here.
>>       // Initialize the roots list
>>       for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) {
>>         if (std::distance(GraphTraits<FT*>::child_begin(*I),
>>                           GraphTraits<FT*>::child_end(*I)) == 0)
>>           addRoot(*I);
>> 
>> One approach is to change CFG or Function implementation to make them have the same interface. But I am afraid this may cause two many changes to the code base. I would love to hear your comments. Is there a decent solution that does not require too many changes to the code?
>> 
>> --
>> Guoping
>> 
>> 
>> 2011/11/2 Anna Zaks <ganna at apple.com>
>> Hi Guoping,
>> 
>> It seems that the only reason why you need to copy the recalculate function is that the names for the entry block in the clang CFG and LLVM function are different. Is that correct? (The bool parameter does not seem to be used..)
>> 
>> A simple solution to that would be to make sure that we have the same name in both. I suggest using getEntryBlock().
>> 
>> 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().
>> 
>> Thanks!
>> Anna.
>> On Oct 29, 2011, at 3:58 PM, Guoping Long wrote:
>> 
>> > Hi, Ted
>> >
>> >    The preliminary refactoring of the dominators patch for clang based on the more efficient LLVM core implementation is done. Attached is the patch. I am not very satisfied with this version because it relies a ugly hack to deal with the subtle differences between LLVM Function and Clang CFG. Since this version requires some modifications to include/llvm/Analysis/Dominators.h, so there is also a patch for llvm.
>> >
>> >     While I believe there should be a cleaner way to do this, I do not know how to achieve that.  Please let me know your comments. I shall continue to improve until it become satisfactory.
>> >     Regards.
>> >
>> > ----
>> > Guoping
>> > <dominators-clang.patch><dominators-llvm.patch>_______________________________________________
>> > 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/20111106/a88845ec/attachment.html>