Re: And speaking of fast compilers...

cheryl@gallant.apple.com (Cheryl Lins)
Tue, 17 Nov 1992 17:35:48 GMT

          From comp.compilers

Related articles
And speaking of fast compilers... pardo@cs.washington.edu (1992-11-12)
Re: And speaking of fast compilers... sasdrf@unx.sas.com (1992-11-16)
Re: And speaking of fast compilers... preston@dawn.cs.rice.edu (1992-11-17)
Re: And speaking of fast compilers... cheryl@gallant.apple.com (1992-11-17)
Re: And speaking of fast compilers... pardo@cs.washington.edu (1992-11-17)
Range Checking (was: And speaking of ...) grover@brahmand.Eng.Sun.COM (1992-11-19)
Re: And speaking of fast compilers... pardo@cs.washington.edu (1992-11-23)
Re: And speaking of fast compilers... macrakis@osf.org (1992-11-24)
Re: And speaking of fast compilers... preston@miranda.cs.rice.edu (1992-12-03)
| List of all articles for this month |

Newsgroups: comp.compilers
From: cheryl@gallant.apple.com (Cheryl Lins)
Organization: Apple Computer Inc, Cupertino, CA
Date: Tue, 17 Nov 1992 17:35:48 GMT
Summary: constant prop. and range value prop.
Keywords: performance, Ada, design, bibliography
References: 92-11-057 92-11-084

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
--


Post a followup to this message

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