We present a tool kit for the construction of optimal interprocedural data flow analyses for programs with mutually recursive procedures, global and local variables, formal value and reference parameters. The tool kit contains specification tools, which allow concise specifications, and computation tools that can directly be fed with these specifications. Moreover, proving an analysis to be optimal only requires knowledge about the specification. The benefits of the tool kit are demonstrated by presenting a collection of practically relevant optimal interprocedural data flow analyses ranging from classical bit-vector problems as e.g. reaching definitions and busy expressions to more sophisticated application as the optimal elimination of interprocedural partial redundancies.
Keyword: Interprcedural data flow analysis, program optimization, bit-vector data flow analysises, available expressions, reaching definitions, live variables, very busy expressions, use-definition-chains, code motion, partial redundancy elimination, partial dead code elimination, strength reduction.
Ulrike Peiker, Martin Griebl