Abstract
We present several new static analysis frameworks applying to rational numbers, and more precisely, designed for discovering congruence properties satisfied by rational (or real) variables of programs. Two of them deal with additive congruence properties and generalize linear equation analysis [12] and congruence analyses on integer numbers [8, 9]. The others are based on multiplicative congruence properties in the set of positive rational numbers. Among other potential applications, we exemplify the interest of all these analyses for optimizing the representation of rational or real valued variables.
Preview
Unable to display preview. Download preview PDF.
References
R. Allen, K. Kennedy, Automatic Translation of FORTRAN Programs to Vector Form, ACM Transactions on Programming Languages and Systems, Vol. 9, No. 4, pp. 491–542, 1987.
P. Cousot, R. Cousot, Static Determination of Dynamic Properties of Programs, Proceedings of the 2nd International Symposium on Programming, Dunod, Paris, pp. 106–130, 1976.
P. Cousot, R. Cousot, Abstract Interpretation: a Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints, Conf. Rec. of the 4th ACM Symposium on Principles of Programming Languages, pp. 238–252, 1977.
P. Cousot, R. Cousot, Systematic Design of Program Analysis Frameworks, Conf. Rec. of the 6th ACM Symposium on Principles of Programming Languages, pp. 269–282, 1979.
P. Cousot, N. Halbwachs, Automatic Discovery of Linear Restraints among Variables of a Program, Conf. Rec. of the 5th ACM Symposium on Principles of Programming Languages, pp. 84–97, 1978.
A. Deutsch, A Storeless Model of Aliasing and its Abstractions using Finite Representations of Right-Regular Equivalence Relations, Proceedings of the IEEE 1992 International Conference on Computer Languages, Oakland, CA, pp. 2–13, 1992.
N. Jacobson, Basic Algebra, W. H. Freeman and Company, 1985.
P. Granger, Static Analysis of Arithmetical Congruences, International Journal of Computer Mathematics, Vol. 30, pp. 165–190, 1989.
P. Granger, Static Analysis of Linear Congruence Equalities among Variables of a Program, TAPSOFT'91, Proceedings of the International Joint conference on Theory and Practice of Software Development, Brighton, U.K., Vol. 1 (CAAP'91), Springer-Verlag Lecture Notes in Computer Science, Vol. 493, pp. 169–192, 1991.
P. Granger, Analyses Sémantiques de Congruence, Thèse de Doctorat, École Polytechnique, 1991.
P. Granger, Improving the Results of Static Analyses of Programs by Local Decreasing Iterations (Extended Abstract), Proc. of Foundations of Software Technology and Theoretical Computer Science, 12th Conference, Springer-Verlag Lecture Notes in Computer Science 652, pp. 68–79, 1992.
M. Karr, Affine Relationships among Variables of a Program, Acta Informatica, Vol. 6, pp. 133–151, 1976.
G. A. Kildall, A Unified Approach to Global Program Optimization, Conf. Rec. of the ACM Symposium on Principles of Programming Languages, pp. 194–206, 1973.
A. Lichnewsky, F. Thomasset, Introducing Symbolic Problems Solving Techniques in the Dependence Phases of a Vectorizer, Proceedings of the 2nd ACM International Conference on Supercomputing, Saint-Malo, France, pp. 396—406, 1988.
F. Masdupuy, Using Abstract Interpretation to Detect Array Data Dependencies, Proceedings of the International Symposium on Supercomputing, Fukuoka, Japan, pp. 19–27, 1991.
F. Masdupuy, Semantic Analysis of Interval Congruences, Proc. of Formal Methods in Programming and Their Applications, Springer-Verlag Lecture Notes in Computer Science 735, pp.142–155, 1993.
N. Mercouroff, An Algorithm for Analyzing Communicating Processes, Proceedings of Mathematical Foundations of Programming Semantics, Pittsburgh, PA, Springer-Verlag Lecture Notes in Computer Science, Vol. 598, pp. 312–325, 1991.
A. Mycroft, The Theory and Practice of Transforming Call-by-need into Call-by-value, Proceedings of the 4th International Symposium on Programming, Springer-Verlag Lecture Notes in Computer Science, Vol. 83, pp. 269–281, 1980. *** DIRECT SUPPORT *** A0008C44 00007
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Granger, P. (1997). Static analyses of congruence properties on rational numbers (extended abstract). In: Van Hentenryck, P. (eds) Static Analysis. SAS 1997. Lecture Notes in Computer Science, vol 1302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0032748
Download citation
DOI: https://doi.org/10.1007/BFb0032748
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63468-3
Online ISBN: 978-3-540-69576-9
eBook Packages: Springer Book Archive