Abstract Shape analysis is a form of pointer analysis, although it is more precise than typical pointer analyses. Pointer analyses attempt to determine the set of objects to which a pointer can point (called the points-to set of the pointer). Unfortunately, these analyses are necessarily approximate. Shape analyses can determine smaller (more precise) points-to sets.
In order to determine points-to sets, a pointer analysis must be able to name a program's objects. In general, programs can allocate an unbounded number of objects; but in order to terminate, a pointer analysis can only use a finite set of names. A typical approximation is to give all the objects allocated on a given line of the program the same name.
Shape analysis overcomes the problems of pointer analysis by using a more flexible naming system for objects. Rather than giving an object the same name throughout a program, objects can change names depending on the program's actions. Sometimes, several distinct objects with different names may be summarized, or merged, so that they have the same name. Then, when a summarized object is about to be used by the program, it can be materialized–that is, the summarized object is split into two objects with distinct names, one representing a single object and the other representing the remaining summarized objects. The basic heuristic of shape analysis is that objects that are being used by the program are represented using unique materialized objects, while objects not in use are summarized.
Although shape analyses are very powerful, they usually take a long time to run.
– For a long version of the above, including examples, see Wikipedia.
The first complete version of the presentation will be presented to GK on Thursday, Sept 30, 2010 at 10:30.