Program analysis with partial transfer functions

Program analyses used in compilers commonly use a transfer function (TF) to summarize the input/output behavior of a procedure or region, speeding con vergence of analysis of the surrounding region or program. A partial transf er function (PTF) summarizes input/output behavior for only a subset of the possible inputs. Tn many cases, an exact characterization of input/output behavior is possible for the contexts occurring in a given program, even wh en a concise and exact total summary would not be feasible. In other cases, an approximate PTF can be used which, while not exact, is more precise tha n would be possible with a total approximation. As demonstrated by prior work in a flow- and context-sensitive pointer alia s analysis, PTFs are effective in speeding the convergence of program analy sis involving higher-order functions and complex transfer functions that ca nnot easily be summarized. This paper presents a formal definition of partial transfer functions and i ntroduces a general framework that enables data flow systems with complex t ransfer functions to be decomposed into simpler partial transfer functions. This paper provides a foundation that will allow the further development o f the PTF concept, as well as enabling application to many more program ana lyses.