Garbage collection and other optimizations

Existing techniques for garbage collection and machine code optimizations can interfere with each other. The inability to fully optimize code in a garbage-collected system is a hidden cost of garbage collection. One solution to this problem is proposed; an inexpensive protocol that permits most optimizations and garbage collection to coexist. A second approach to this problem and a separate problem in its own right is to reduce the need for garbage collection. This requires analysis of storage lifetime. Inferring storage lifetime is difficult in a language with nested and recursive data structures, but it is precisely these languages in which garbage collection is most useful. An improved analysis for "storage containment" is described. Containment information can be represented in a directed graph. The derivation of this graph falls into a monotone data-flow analysis framework; in addition, the derivation has the Church-Rosser property. The graphs produced in the analysis of a value-assignment language have the property that they can be replaced with a single graph without losing any information. These properties also assist in the generation of graphs for side-effect languages. A different approach to avoiding obtaining memory from the garbage collector is also proposed. Existing techniques are either not general or run the risk of consuming all of a bounded memory. A general, low overhead technique that does not consume excessive amounts of memory is described