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

[Guoping Long]

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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111004/a5f0fec5/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: CFG.cpp.patch
Type: application/octet-stream
Size: 5754 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111004/a5f0fec5/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: CFG.h.patch
Type: application/octet-stream
Size: 2955 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20111004/a5f0fec5/attachment-0001.obj>