Multiple specialization using minimal-function graph semantics

AbstractMany optimizing compilers use interprocedural analysis to determine how the source program uses each of its procedures. Customarily, the compiler gives each procedure a single implementation, which is specialized according to restrictions met by all uses of the procedure. We propose a general method whereby the compiler can make the uses of each procedure implementation more uniform, enabling a greater degree of specialization. The method creates several implementations of each procedure, each specialized for a different class of use; it avoids run-time overhead by determining at compile time the appropriate procedure implementation for each call in the expanded program. The implementation suited to each call is determined by embedding in the program a deterministic finite automaton that, during execution, scans the current call path, i.e., the sequence of calls entered but not yet exited. Each automaton state has an associated class of procedure uses that includes the use made by the last call in each call path, on input, leaves the automaton in the given state. The compiler creates one implementation for each state, using the associated class of use to specialize the implementation and the transition function to determine which implementation to invoke for each call in the expanded program. With standard automata-theory techniques, it is straightforward to merge several automaton states, in case several classes of use lead to specializations that are the same or whose differences are not substantial enough to warrant separate implementations. Thus, our method allows the compiler to perform multiple specialization where it is useful, while avoiding excessive enlargement of the generated code. We formalize the foundation of our method by constructing a general-purpose minimal-function graph semantics that extends and improves prior constructions of this sort