[PRL] Subcubic Control Flow Analysis Algorithms

[David Van Horn]

Jan and I would greatly appreciate feedback.  -- David

Subcubic Control Flow Analysis Algorithms
	
Jan Midtgaard
David Van Horn
http://www.ruc.dk/dat_en/research/reports/125/

We give the first direct subcubic algorithm for performing control flow 
analysis of higher-order functional programs. Despite the long held 
belief that inclusion-based flow analysis could not surpass the ``cubic 
bottleneck,'' we apply known set compression techniques to obtain an 
algorithm that runs in time O(n^3/log n) on a unit cost random-access 
memory model machine. Moreover, we refine the initial flow analysis into 
two more precise analyses incorporating notions of reachability. We give 
subcubic algorithms for these more precise analyses and relate them to 
an existing analysis from the literature.