Re: Size of graphs in conventional compilers

Pinku Surana <pinkus@comm.mot.com> wrote:
>What is, approximately, the size of the flow graphs created by
>compilers with respect to the parse tree, or to the size of the input
>program? Does the time taken to create the graphs dominate most uses
>of the graph?
>...


In practice, control-flow graphs grow either linearly with or slower than
the parse tree. A CFG consists of nodes (blocks or statements) and edges
(transfers of control). That's all the basic information, which tends to
be much smaller than the parse tree because of the reduced detail. You
still need the parse tree (or another intermediate form) and a map between
it and the CFG. In the worst case -- say, where there are lots of jumps
to computed addresses -- the set of CFG edges may grow quadratically with
the parse tree, but this is exceedingly rare and many other parts of a
compiler will have trouble with such a program.


Data-flow graphs can grow linearly to quadratically with the size of the
parse tree, depending on many things. Over a large sample of procedures,
data-flow graphs built using static single assignment form grow linearly:


@article{CFRWZ:Efficient,
Author={Ron Cytron and Jeanne Ferrante and Barry K. Rosen
and Mark N. Wegman and F. Kenneth Zadeck},
Title={Efficiently computing static single assignment form
and the control dependence graph},
Journal=TOPLAS,
Volume=13,
Number=4,
Pages={451--490},
Month=Oct,
Year={1991}}


--Paul
--
Paul Havlak Dept. of Computer Science, A.V. Williams Bldg
Postdoctoral Research Associate U. of Maryland, College Park, MD 20742-3255
http://www.cs.umd.edu/~havlak (301) 405-2697 (fax: -2744) havlak@cs.umd.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.