[cfe-dev] Adding more analysis algorithms to Clang?

[Guoping Long]

Hi, Anna

   You are right. Since LLVM already has dominatorTree implementation, it's
not very interesting to build the wheel again.

------
Guoping

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

> Hi Guoping,
>
> Here are some comments mostly based on review of buildDominanceTree().
>
> This should be extensively tested. I think unit tests(clang/test/unittests)
> could be a good fit in this case. Please, make tests a part of your next
> patch.
>
> It would be nice if you could provide more expressive API for users of the
> algorithms. For example, provide reverse post order iterator which can be
> used by multiple clients instead of using the RPOQueue local variable to
> store the results.  Similarly for the dominator info, it would be nice to
> add some API which allows querying if one block dominates another one.. LLVM
> already has these algorithms implemented. I am not sure if some reuse is
> possible or not:
> http://llvm.org/docs/doxygen/html/PostOrderIterator_8h_source.html
> http://llvm.org/docs/doxygen/html/classllvm_1_1DominatorTree.html
>
> Other comments:
> - A single patch file would be easier to review.
>
>  - If the following if statement needed? (Can a block have null
> successors?)
> +      if(CFGBlock *B = *I) {
>
>  - Is VisitVector needed? Maybe you could use the BlockRPO of the
> successors instead.
>
>  - Shouldn't Dominator fields be initialized to 0?
>
>  - 2 components/functions should be pulled out of buildDominanceTree():
> buildReversePostorder(), intersect().
>
>  - I think it would be cleaner to include the paper references as part of
> method comments/not fields comments.
>
>  - "That is, dead code CFG blocks are ignored by this algorithm" - I'd
> remove this comment. The first sentence is clear enough. (I think you are
> talking about unreachable code here, and dominance analysis are not powerful
> enough to find all unreachable code.)
>
> Microscopic style issues:
>    - Comments should use proper punctuation.
>
>    - You need to insert a space after a comma and before {. For example:
>         RPOQueue.push_back(item,BlkBVC); ->  RPOQueue.push_back(item,
> BlkBVC);
>         if(!VisitVector[BlockID]){ -> if (!VisitVector[BlockID]) {
>
>    - CFGBlock * getSCCRoot() -> CFGBlock *getSCCRoot()
>
> Cheers,
> Anna.
>
> On Oct 5, 2011, at 3:44 PM, Guoping Long wrote:
>
> Thanks Arjun for your feedback. I updated these files (attached).
> Ted, I am looking forward to your comments.
>
> ------
> Guoping
>
> 2011/10/5 Arjun Singri <arjunsingri at gmail.com>
>
>> 1. Use "unsigned int" instead of just "unsigned"
>> 2. Shouldnt       "CFGStack.pop_back_val(); " on line 45 be outside the
>> "if (AllVisited)" statement?
>> 3. The check on line 76 is unnecessary. If you are at line 76 then the
>> check at line 71 was false which means that the check at 76 is true. So I
>> guess replace "else if" with "else".
>> 4. typo on line 52
>>
>> Arjun
>>
>> On Tue, Oct 4, 2011 at 8:34 PM, Guoping Long <longguoping at gmail.com>wrote:
>>
>>> Dear Ted
>>>
>>>    I added two control flow analysis algorithms: One builds the dominance
>>> tree for CFG. The other one finds all SCC components within the CFG.
>>> Attached is the patch. I integrated these algorithms within the CFG and
>>> CFGBlock classes. This is the first time I submit something, so I have some
>>> questions:
>>>
>>> 1 While I would really love to contribute, I am not sure if the code
>>> quality is enough. Please let me know any problems with the code so I shall
>>> fix them.
>>> 2 These algorithms shall work on any CFG. I am not sure what kind of
>>> special test cases should be added. I do wrote an example (in
>>> tools/clang/examples) to illustrate how to use these two algorithms. Is it
>>> necessary to submit the example into the examples/ directory?
>>> 3 I tried my best to follow the code standards and comments. Also, in the
>>> comments, I listed the key reference papers which described thorough details
>>> of these algorithms. They are the state of the art algorithms as far as I
>>> know, and very efficient, although I am not sure my implementation is good
>>> or not.
>>>
>>> I am looking forward to feedback. I shall fix problems until it meets the
>>> quality for actual commit.
>>> Thanks.
>>>
>>> ------------
>>> Guoping
>>>
>>>
>>> 2011/10/3 Ted Kremenek <kremenek at apple.com>
>>>
>>>> Hi Guoping,
>>>>
>>>> Additions to libAnalysis have largely been demand-driven.  I think we
>>>> are fine with general contributions to this library that meeting the
>>>> following criteria:
>>>>
>>>> (1) Meet the Clang coding conventions and quality expectations.
>>>>
>>>> (2) Are testable ("make test"), and tests are included in clang/test.
>>>>
>>>> (3) Performance is acceptable and measurable, or at least documented
>>>> when algorithms are known to be expensive.
>>>>
>>>> (4) APIs are well-documented, which can come in the form of good doxygen
>>>> comments.
>>>>
>>>> Source-to-source transformations are welcome, and the Clang codebase
>>>> does contains tools that are source-to-source rewriters.  For example,
>>>> libRewrite provides low-level functionality for doing textual rewrites of
>>>> source files using Clang SourceLocations.  Other analysis algorithms are
>>>> useful as well; we just prefer that they can be regression tested, and the
>>>> APIs are well-documented (especially if they don't have any real clients in
>>>> the codebase at present).
>>>>
>>>> Cheers,
>>>> Ted
>>>>
>>>> On Oct 3, 2011, at 2:40 PM, Guoping Long wrote:
>>>>
>>>> > Hi,
>>>> >
>>>> >    There are some program analysis algorithms in clang/lib/Analysis
>>>> directory. I am wandering if there are more algorithms to come or not. Are
>>>> there some people working on this? What kind of algorithms are welcome to be
>>>> part of Clang?
>>>> >
>>>> >    I am asking this because I want to help on this part. But I am not
>>>> sure if source-to-source transformation algorithms are welcome in this
>>>> community, since many optimization work is done in the LLVM backend.
>>>> Currently I have implemented to CFG analysis algorithms (building the
>>>> dominance tree and finding the strong connected components in CFG). I plan
>>>> to implement more data flow analysis or even pointer analysis algorithms. If
>>>> these algorithms are useful to people in this community, I would love to
>>>> submit a patch.
>>>> >
>>>> >   I am new to Clang and this community. Hopefully these questions are
>>>> not naive to you.
>>>> >
>>>> >   Thanks.
>>>> > --------
>>>> > Guoping
>>>> > _______________________________________________
>>>> > cfe-dev mailing list
>>>> > cfe-dev at cs.uiuc.edu
>>>> > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>>>>
>>>>
>>>
>>> _______________________________________________
>>> cfe-dev mailing list
>>> cfe-dev at cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>>>
>>>
>>
> <CFG.cpp.patch><CFG.h.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/20111012/b95a9455/attachment.html>