This paper presents a novel set of algorithms for heap abstraction, identifying logically related regions of the heap. The targeted regions include objects that are part of the same component
structure (recursive data structure). The result of the technique outlined in this paper has the
form of a compact normal form (an abstract model) that boosts the efficiency of the static analysis via speeding its convergence. The result of heap abstraction, together with some properties of data structures, can be used to enable program optimizations like static deallocation, pool allocation, region-based garbage collection, and object co-location.
More precisely, this paper proposes algorithms for abstracting heap components with the layout
of a singly linked list, a binary tree, a cycle, and a directed acyclic graph. The termination and correctness
of these algorithms are studied in the paper. Towards presenting the algorithms the paper
also presents concrete and abstract models for heap representations.