Shape-Analysis for Languages with Destructive Updating

9619219该项目的目标是提高对在堆分配的存储上执行破坏性更新的程序进行静态分析的技术水平。这项工作将解决可以研究的问题-取决于人们的观点-指针分析问题、别名分析问题、共享分析问题、存储分析问题(也称为形状分析问题)或类型检查问题。所获得的信息对于生成高效的序列和并行代码是有用的。它在某些类型的软件工程工具中也很有用。该项目的目标是在以下方面做出贡献：(1)进一步发展形状抽象及其在抽象解释中的应用的理论基础。(2)开发了一个从形状抽象规格说明创建形状分析算法的工具。(3)扩展形状分析技术的应用范围，例如，通过(I)对它们进行推广，使得可以回答以下形式的问题：“可以通过在程序点p处x指向的结构访问到在程序点q处y指向的结构的任何元素”，以及(Ii)将形状分析与数组下标分析相结合。(4)创建、试验和评估形状分析实现。***

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