The FLINT Project








SubTransitive CFA Using Types

Last modified: Tue Mar 14 19:28:19 2000 GMT.


Bratin Saha
Nevin Heintze
Dino Oliva


We present an experimental evaluation of Heintze and McAllester's linear-time subtransitive CFA algorithm, in the context of SML/NJ v110.7. As described in the paper "Linear-Time Subtransitive Control Flow Analysis" by Nevin Heintze and David McAllester, linear-time termination of the algorithm depends on the existence of a simple typing of the program such that the type tree at each node has a bounded size. We show that this condition is violated by many programs, especially heavily functorized ones, and so the type-directed version of the algorithm (which explores a program's entire type structure) is only practical on small programs. We also show that the demand-driven variant of the algorithm does not always terminate for programs with polymorphic type. Our main result is that a hybrid algorithm that combines both approaches avoids both the problems. Whereas Heintze and McAllester's original formulation relied on the existence of types to bound the runtime of the algorithm, our work shows that an effective implementation must actually use the types to control termination.

Technical Report YALEU/DCS/TR-1166, Department of Computer Science, Yale University, October 1998.

Copyright © 1996-2024 The FLINT Group <flint at cs dot yale dot edu>
Yale University Department of Computer Science
Validate this page