Entry Johnson:1993:DPA from sigplan1990.bib

Last update: Thu Apr 12 03:37:15 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Johnson:1993:DPA,
  author =       "Richard Johnson and Keshav Pingali",
  title =        "Dependence-based program analysis",
  journal =      j-SIGPLAN,
  volume =       "28",
  number =       "6",
  pages =        "78--89",
  month =        jun,
  year =         "1993",
  CODEN =        "SINODQ",
  ISBN =         "0-89791-598-4",
  ISBN-13 =      "978-0-89791-598-4",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  bibdate =      "Thu May 13 12:37:27 MDT 1999",
  bibsource =    "http://www.acm.org/pubs/contents/proceedings/pldi/155090/index.html",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/155090/p78-johnson/",
  abstract =     "Program analysis and optimization can be speeded up
                 through the use of the {\em dependence flow graph\/}
                 (DFG), a representation of program dependences which
                 generalizes def-use chains and static single assignment
                 (SSA) form. In this paper, we give a simple
                 graph-theoretic description of the DFG and show how the
                 DFG for a program can be constructed in {\em O(EV)\/}
                 time. We then show how forward and backward dataflow
                 analyses can be performed efficiently on the DFG, using
                 constant propagation and elimination of partial
                 redundancies as examples. These analyses can be framed
                 as solutions of dataflow equations in the DFG. Our
                 construction algorithm is of independent interest
                 because it can be used to construct a program's control
                 dependence graph in {\em O(E)\/} time and its SSA
                 representation in {\em O(EV)\/} time, which are
                 improvements over existing algorithms.",
  acknowledgement = ack-nhfb,
  affiliation =  "Dept. of Comput. Sci., Cornell Univ., Ithaca, NY,
                 USA",
  annote =       "Published as part of the Proceedings of PLDI'93.",
  classification = "C1160 (Combinatorial mathematics); C4240
                 (Programming and algorithm theory); C6110 (Systems
                 analysis and programming); C6150C (Compilers,
                 interpreters and other processors)",
  confdate =     "23-25 June 1993",
  conflocation = "Albuquerque, NM, USA",
  confsponsor =  "ACM",
  keywords =     "algorithms; Backward dataflow analyses; Constant
                 propagation; Control dependence graph; Dataflow
                 equations; Def-use chains; Dependence flow graph;
                 Dependence-based program analysis; DFG; Graph-theoretic
                 description; Optimization; Partial redundancies;
                 performance; Program dependences; SSA representation;
                 Static single assignment; theory",
  subject =      "{\bf D.3.3} Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Control structures. {\bf
                 D.3.4} Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization. {\bf F.2.2} Theory of Computation,
                 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY,
                 Nonnumerical Algorithms and Problems, Computations on
                 discrete structures. {\bf G.2.2} Mathematics of
                 Computing, DISCRETE MATHEMATICS, Graph Theory, Graph
                 algorithms. {\bf F.3.3} Theory of Computation, LOGICS
                 AND MEANINGS OF PROGRAMS, Studies of Program
                 Constructs, Control primitives.",
  thesaurus =    "Graph theory; Program compilers; Programming;
                 Programming theory",
}

Related entries