[Tinycc-devel] Static Analysis

[Basile STARYNKEVITCH]

>>>>> "Paul" == Paul Miseiko <address@hidden> writes:

    Paul> I am currently looking to do a static analysis of a decent
    Paul> size code base to determining the peak stack utilization.

If you want good results, don't start from any compiler. Making a
syntax tree is easy. What is hard is the semantical static
analysis. Several advanced techniques (model checking, abstract
interpretation) exist to make it, but they are hard to implement, and
might even not give good enough results.

The question "does a given program need a bounded stack" is equivalent
to "does a given program halt in finite time" so is not
algorithmically solvable in the general case.

A tool such as CIL - see http://manju.cs.berkeley.edu/cil/ for more -
is probably better to start with.

On abstract interpretation you may start with
http://www.di.ens.fr/~cousot/aiintro.shtml

On model checking you might look at
http://wwwbrauer.in.tum.de/gruppen/theorie/KIT/ and
http://vlsi.colorado.edu/~rbloem/mc.html

You might need several man years of hard work to achieve any decent
result. Good luck! It would be great if you could publish your
resulting static analyser as an opensource software. I also suggest
contacting researchers on abstract interpretation or model checking
(which are often two rival communities), and publishing your
scientifical results.

Some companies sell static analysers. They are usually very expensive!


PS: I did work on a proprietary abstract interpretation based C
static analyser and can witness that it is a hard work, with sometimes
disappointing results.
-- 

Basile STARYNKEVITCH         http://starynkevitch.net/Basile/ 
email: basile<at>starynkevitch<dot>net 
aliases: basile<at>tunes<dot>org = bstarynk<at>nerim<dot>net
8, rue de la Faïencerie, 92340 Bourg La Reine, France