[cfe-dev] Refactoring the dominators patch for Clang

[Guoping Long]

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
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111112/47c929d1/attachment.html>