[cfe-dev] Refactoring the dominators patch for Clang

[Guoping Long]

Hi, Anna

  I may not fully understand your point. Here are my thoughts:
First, In think changing the CFG::iterator to be in line with
Function::iterator is too intrusive to clang, and not very necessary. I
actually tried to do this. It involved so many changes that I finally gave
up.

Second, on your comment on the approach I took. Even the current
implementation of the recalculate function does not solely depend on
GraphTraits. It also depends on Function::getEntryBlock or
Function::front(), Function.size(), etc. Why do you think a clean
implementation should only depend on GraphTraits? In addition, I actually
have such a concern: is it reasonable enough to fill in GraphTraits more
stuff only because dominators implementation needs this?

I believe it should be possible to change the recalculate function to only
depend on GraphTraits. But I am not sure if this will be viewed as too
intrusive to LLVM. In thinking of these I finally made that compromise.

Regarding the time, I am willing to do further refactoring until this code
will finally become good enough, although I can only work on weekend on
this. I just want to understand clearly the reasonable motivation behind
each refactoring step.

--
Guoping

2011/11/6 Anna Zaks <ganna at apple.com>

> 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/20111107/ffefdddb/attachment.html>