[cfe-dev] Refactoring the dominators patch for Clang

[Guoping Long]

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
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111105/7d6488ed/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dominators-clang.patch
Type: application/octet-stream
Size: 21740 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111105/7d6488ed/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dominators-llvm.patch
Type: application/octet-stream
Size: 3040 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111105/7d6488ed/attachment-0001.obj>