Re: static analysis of variable value ranges

spuler@coral.cs.jcu.edu.au writes:
>I was wondering whether anyone knows of further research into the
>technique developed by Harrison to trace the values of variables
>throughout program execution. [...]


A particular application of abstract interpretation (i.e: data flow
analysis + semantics) called interval analysis was described in the paper:


@InProceedings{Cousots77,
    author = "Cousot,P. and Cousot, R.",
    title = "Abstract Interpretation~: a unified lattice model for
static analysis of programs by construction of
approximation of fixpoints",
    booktitle = "Fourth Annual ACM Symp. on Principles of Programming
Languages",
    year = "1977",
    pages = "238--252",
    address = "Los Angeles",
    month = jan
}


This is a program analysis based on the so-called lattice of intervals.
This analysis is both:


- more accurate than the analysis of Harrison 77 ;
- more accurate than the analysis of Gupta 90:


@InProceedings{Gupta90,
    author = "Gupta,R.",
    title = "A Fresh Look at Optimizing Array Bound Checking",
    volume = "25(6)",
    series = "Sigplan Notices",
    pages = "272--282",
    booktitle = "Sigplan'90 Conf. on Programming Language Design and
Implementation",
    year = 1990,
    publisher = "ACM Press",
    address = "White Plains, NY",
    month = jun
}
- usable in practice, see Morel 84 (I do not have the reference at
hand) for a description of a real ADA compiler using this
technique for removing statically array bound checks.


The interval analysis Cousots 77 can be applied both intraprocedurally,
and also interprocedurally, as described in the paper:


@InProceedings{Cousots77b,
    author = "Cousot,P. and Cousot,R.",
    title = "Static determination of dynamic properties of recursive
procedures",
    booktitle = "Working Conf. on Formal Description of Programming Concepts",
    year = "1977",
    organization= "IFIP WG 2.2",
    publisher = "North-Holland",
    address = "St-Andrews,Canada",
    month = aug
}


Sincerely,


Alain Deutsch.


----
Alain Deutsch -- School of Computer Science
Carnegie Mellon University, Pittsburgh, PA 15213-3890, USA.
Email: deutsch@cs.cmu.edu, Phone: (412) 268 2697, Fax: (412) 681 5739.
--

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