Shape-Analysis for Languages with Destructive Updating

点击翻译按钮获取中文摘要

9619219 The goal of the project is to advance the state of the art in static analysis of programs that perform destructive updating on heap-allocated storage. The work will address problems that can be looked at --- depending on one's point of view --- as pointer- analysis problems, alias-analysis problems, sharing-analysis problems, storage-analysis problems (also known as shape-analysis problems), or type-checking problems. The information obtained is useful for generating efficient sequential and parallel code. It is also useful in certain kinds of software-engineering tools. The project aims to make contributions in the following areas: (1) Develop further the theoretical foundations of shape abstractions and their use in abstract interpretation. (2) Develop a tool for creating a shape-analysis algorithm from a specification of a shape abstraction. (3) Extend the range of applications for shape-analysis techniques, for example, by (i) generalizing them so that questions can be answered of the form "Can accesses through the structure that x points to at program point p ever reach any of the elements of the structure that y points to at program point q?", and (ii) combining shape-analysis with array-subscript analysis. (4) Create, experiment with, and evaluate shape-analysis implementations. ***