Dynamic memory allocation techniques based on the lifetime of objects

The binding of a program to a particular property or attribute is the choice of such property from a set of possible ones. In general, postponement of binding times gives greater flexibility to a language user, but can adversely affect run-time efficiency. An ideal processor for a language should have as one of its functions the task of determining the earliest binding times for a program which are consistent with its being correctly executed. This task is what we call binding time optimization. This thesis deals with the storage management aspect of binding time optimization in strongly typed languages with dynamically allocated objects. Our optimization technique is based on the observation that while global heap allocation has generally been the only technique used to implement reference variables, most of the features necessary for the implementation of high-level data structures do not require that the heap be a global one. The only characteristic which demands a global heap is that object lifetimes are not tied to a particular procedure, and are therefore unknown at compile-time. We present several memory allocation techniques that can be used in place of global heap allocation when the information about the lifetime of objects is available. We consider a broad class of structured objects, including recursive types. Our techniques are based on the concept of local heaps associated to procedure activation records on the stack. To determine upper bounds on the lifetime of objects we first introduce a compile-time approximation of run-time objects, called sources. We then develop a flow analysis algorithm for the inter-procedural problem of determining how far in the call-graph of the program a source can propagate. This problem requires collecting information at two levels. At the inter-procedural level we provide an algorithm to propagate the names of the sources returned to a calling procedure. At the intra-procedural level we examine the flow of the sources within each procedure to determine which ones reach the exits. We present both algorithms using a formal data flow analysis framework model. Because the two levels are independent our algorithm handles recursive procedures without recomputing intra-procedural information