Subcubic Control Flow Analysis Algorithms

Jan Midtgaard, David Van Horn

    Research output: Book/ReportReportResearch

    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.
    Original languageEnglish
    Place of PublicationRoskilde
    PublisherRoskilde Universitet
    Number of pages32
    Publication statusPublished - 2009
    SeriesRoskilde Universitet. Computer Science. Computer Science Research Report
    Number125
    ISSN0109-9779

    Keywords

    • Control flow analysis
    • Algorithms
    • Cubic bottleneck

    Cite this

    Midtgaard, J., & Van Horn, D. (2009). Subcubic Control Flow Analysis Algorithms. Roskilde Universitet. Roskilde Universitet. Computer Science. Computer Science Research Report, No. 125 http://www.ruc.dk/dat_en/research/reports/125/