SubTransitive CFA Using TypesLast modified: Tue Mar 14 19:28:19 2000 GMT. AuthorsBratin SahaNevin Heintze Dino Oliva AbstractWe present an experimental evaluation of Heintze and McAllester's lineartime subtransitive CFA algorithm, in the context of SML/NJ v110.7. As described in the paper "LinearTime Subtransitive Control Flow Analysis" by Nevin Heintze and David McAllester, lineartime 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 typedirected version of the algorithm (which explores a program's entire type structure) is only practical on small programs. We also show that the demanddriven 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/TR1166, Department of Computer Science, Yale University, October 1998.

Copyright © 19962021 The FLINT Group
<flint at cs dot yale dot edu>
Yale University Department of Computer Science 
colophon 