Re: And speaking of fast compilers...

sasdrf@unx.sas.com (Dave Frederick) writes:
>Most of the optimizations an Ada compiler performs are compile-time range
>and bounds checking. [other comments deleted]
>When performing such tests for all ranges, subranges, and array
>indices, one can see how an explosion in compile time can occur.


Range and bounds checking are variations on the constant propagation
problem. If memory serves, this is doable in time linear to the number of
variables. See [1] for how global constant propagation can be done
efficiently.


>One of the hot topics when I last worked on an Ada compiler was doing the
>above range and bounds checking optimization across procedures in a
>package. Interprocedural analysis is quite helpful for determining the
>possibility of these errors on var parameters.


So presumably, you were also doing interprocedural alias analysis. I'm
curious about the algorithms used for this. Did you implement those of [2]
(for alias analysis)?


The same algorithms for value propagation mentioned above. In the inter-
procedural case, you may have a paritally constructed lattice with some
known values or ranges for some of the variables.


References
[1]
@inproceedings{cooper:89a,
author = "Keith D. Cooper and Ken Kennedy",
title = "Fast interprocedural alias analysis",
booktitle = popl89,
pages = "49--59",
address = "Austin, TX",
month = jan,
year = 1989}


[2]
@article{wegman:91,
author = "Mark N. Wegman and F. Kenneth Zadeck",
title = "Constant propagation with conditional branches",
journal = toplas,
volume = 13,
number = 2,
pages = "181--210",
month = apr,
year = 1991}




--
Cheryl Lins Oberon Paladin lins@apple.com
--

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