Subcubic Control Flow Analysis Algorithms

Jan Midtgaard, David Van Horn

    Publikation: Bog/antologi/afhandling/rapportRapportForskning

    Resumé

    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.
    OriginalsprogEngelsk
    Udgivelses stedRoskilde
    ForlagRoskilde Universitet
    Antal sider32
    StatusUdgivet - 2009
    NavnRoskilde Universitet. Computer Science. Computer Science Research Report
    Nummer125
    ISSN0109-9779

    Emneord

      Citer dette

      Midtgaard, J., & Van Horn, D. (2009). Subcubic Control Flow Analysis Algorithms. Roskilde: Roskilde Universitet. Roskilde Universitet. Computer Science. Computer Science Research Report, Nr. 125
      Midtgaard, Jan ; Van Horn, David. / Subcubic Control Flow Analysis Algorithms. Roskilde : Roskilde Universitet, 2009. 32 s. (Roskilde Universitet. Computer Science. Computer Science Research Report; Nr. 125).
      @book{fccd6e107c4611debfff000ea68e967b,
      title = "Subcubic Control Flow Analysis Algorithms",
      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.",
      keywords = "Control flow analysis, Algorithms, Cubic bottleneck",
      author = "Jan Midtgaard and {Van Horn}, David",
      year = "2009",
      language = "English",
      publisher = "Roskilde Universitet",

      }

      Midtgaard, J & Van Horn, D 2009, Subcubic Control Flow Analysis Algorithms. Roskilde Universitet. Computer Science. Computer Science Research Report, nr. 125, Roskilde Universitet, Roskilde.

      Subcubic Control Flow Analysis Algorithms. / Midtgaard, Jan; Van Horn, David.

      Roskilde : Roskilde Universitet, 2009. 32 s.

      Publikation: Bog/antologi/afhandling/rapportRapportForskning

      TY - RPRT

      T1 - Subcubic Control Flow Analysis Algorithms

      AU - Midtgaard, Jan

      AU - Van Horn, David

      PY - 2009

      Y1 - 2009

      N2 - 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.

      AB - 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.

      KW - Control flow analysis

      KW - Algorithms

      KW - Cubic bottleneck

      M3 - Report

      BT - Subcubic Control Flow Analysis Algorithms

      PB - Roskilde Universitet

      CY - Roskilde

      ER -

      Midtgaard J, Van Horn D. Subcubic Control Flow Analysis Algorithms. Roskilde: Roskilde Universitet, 2009. 32 s. (Roskilde Universitet. Computer Science. Computer Science Research Report; Nr. 125).