Array Region Analyses by Abstract Interpretation Approaches

• Ilaria Lari University of Pisa
• Laura Ricci University of Pisa

DOI: https://doi.org/10.5753/sbac-pad.2000.41229

Resumo

This paper presents some static analysis to detect the portion of a data structure accessed in a region of the program, such as a loop nest. Each analysis returns a set of data access descriptors summarizing, through a set of approximations, the data accessed in the region. The analyses have been defined through an abstract interpretation framework. The paper reviews several previously defined abstract domains and shows that some of them are suitable for the analysis of interest. Then, a new domain is proposed and the interpretation is defined through a systematic approach to combine abstract interpretations. Using this approach, an analyzer has been automatically generated from the analysis specification. The application of the analyzer to union cases of interest is shown as well.

Palavras-chave: data access descriptor, abstract interpretation, optimizing compiler, loop transformation, abstract domain

Referências

M. Alt, F. Martin. Generation of efficient interprocedural analyzers with PAG. Static Analysis Symposium, SAS 95, LNCS 983, 1995, pp. 33–50. Springer Verlag.

V. Balasundaram. A Mechanism for Keeping Useful Internal Information in Parallel Programming Tools: The Data Access Descriptor. Journal of Parallel and Distributed Computing, 1990, vol. 9, pp. 154–170.

W. J. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization. PhD thesis, Univ. of Illinois at Urbana-Champaign, Center for Supercomputing, June 1995.

D. Callahan, K. Kennedy. Analysis of Interprocedural Side Effects in a Parallel Programming Environment. Journal of Parallel and Distributed Computing, 1988, vol. 5, pp. 517–550.

P. Cousot, R. Cousot. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoint. Fourth ACM Symposium on Principles of Programming Languages, pp. 238–252, 1977.

P. Cousot, R. Cousot. Systematic Design of Program Analysis Framework. Sixth 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. Fifth ACM Symposium on Principles of Programming Languages, pp. 84–96, 1978.

B. Creusillet, F. Irigoin. Interprocedural Array Region Analyses. Languages and Compilers for Parallel Computing, Lecture Notes in Computer Science, pp. 46–60, August 1995.

T. Gross, P. Steenkiste. Structured Dataflow Analysis for Arrays and its Use in an Optimizing Compiler. Software—Practice and Experience, February 1990, vol. 20(2), pp. 133–155.

M. Haghighat, C. Polychronopoulos. Symbolic Analysis for Parallelizing Compilers. ACM Transactions on Programming Languages and Systems, 1996, Vol. 18, No. 4, July 1996.

M. W. Hall, B. R. Murphy, S. P. Amarasinghe, S. Liao, M. S. Lam. Interprocedural Parallelization Analysis: a case study. Proceedings of 8th International Workshop on Languages and Compilers for Parallel Computing, August 1995.

P. Havlak, K. Kennedy. An Implementation of Interprocedural Bounded Regular Section Analysis. IEEE Transactions on Parallel and Distributed Systems, July 1991, No. 3, Vol. 2.

J. Hoeflinger, Y. Paek, D. Padua. Region-based Parallelization Using the Region Test. Technical Report 1514, Univ. of Illinois at Urbana-Champaign, Center for Supercomputing, December 1996.

I. Lari. Data Access Descriptor Computation: Abstract Interpretation Proposals. Master Thesis, Department of Computer Science, University of Pisa.

R. Triolet, F. Irigoin, P. Feautrier. Direct Parallelization of Call Statement. University of Illinois, Center for Supercomputing R&D, USA, 1986.

M. Vanneschi. Heterogeneous HPC Environments. Euro-Par 98, LNCS 1470, pages 21–34, Southampton, UK, September 1998.