| Computer science research report #125 | |
Subcubic Control Flow Analysis Algorithms |
|
Jan Midtgaard
|
|
 Download PDF file |
|
| Abstract: |
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. |
| Pages: |
32 |
| Date of submission: | |
|
May 2009 |
|
| Type: |
Technical report |
| BiBTeX entry: |
show » |
| About RU |
 |
Research Profile at Roskilde Univ... |
|
Admission full degree |
|
Research |
|
Departments |
|
Internal pages |
|
Library |
|
På dansk
|
|
|
|
|
|
|
|
Computer Science | |
|||
|
|
|
|||
|
Semesterplan | |
|||
|
|
||||
|
Study Programmes | |
|||
|
|
||||
|
Study advisor | |
|||
|
|
||||
|
Research | |
|||
|
|
|
|||
|
Study administration | |
|||
|
|
||||
|
Staff | |
|||
|
|
||||
|
IT support | |
|||
|
|
||||
|
På dansk | |
|||
|
|
|
|||
|
|||||
|
|
|
|