Shape analysis concerns the problem of determining "shape invariants" for programs that perform destructive updating on dynamically allocated storage. This paper presents a new algorithm that takes as input a shape descriptor (describing some set of concrete stores X) and a precondition p, and computes the most-precise shape descriptor for the stores in X that satisfy p .

This algorithm solves several open problems in shape analysis:

• computing the most-precise descriptor of a set of concrete stores represented by a logical formula;
• computing best transformers for atomic program statements and conditions;
• computing best transformers for loop-free code fragments (i.e., blocks of atomic program statements and conditions)
• performing interprocedural shape analysis using procedure specifications and assume-guarantee reasoning;
• computing the most-precise overapproximation of the meet of two shape descriptors.

The algorithm employs a theorem prover; termination can be assured by using standard techniques (e.g., having the theorem prover return a safe answer if a time-out threshold is exceeded) at the cost of losing the ability to guarantee that a most-precise result is obtained.

A prototype has been implemented in TVLA, using the SPASS theorem prover.