Entry Deutsch:1994:IMA 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{Deutsch:1994:IMA,
  author =       "Alain Deutsch",
  title =        "Interprocedural may-alias analysis for pointers:
                 beyond $k$-limiting",
  journal =      j-SIGPLAN,
  volume =       "29",
  number =       "6",
  pages =        "230--241",
  month =        jun,
  year =         "1994",
  CODEN =        "SINODQ",
  DOI =          "http://doi.acm.org/10.1145/178243.178263",
  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 =      "Wed Jun 18 16:26:55 MDT 2008",
  bibsource =    "http://portal.acm.org/;
                 http://www.acm.org/pubs/contents/proceedings/pldi/178243/index.html",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/178243/p230-deutsch/",
  abstract =     "Existing methods for alias analysis of recursive
                 pointer data structures are based on two approximation
                 techniques: {\em k-limiting\/}, and {\em store-based\/}
                 (or equivalently location or region-based)
                 approximations, which blur distinction between elements
                 of recursive data structures. Although notable progress
                 in inter-procedural alias analysis has been recently
                 accomplished, very little progress in the precision of
                 analysis of recursive pointer data structures has been
                 seen since the inception of these approximation
                 techniques by Jones and Muchnick a decade ago. As a
                 result, optimizing, verifying and parallelizing
                 programs with pointers has remained difficult. We
                 present a new parametric framework for analyzing
                 recursive pointer data structures which can express a
                 new natural class of alias information not accessible
                 to existing methods. The key idea is to represent alias
                 information by pairs of {\em symbolic access paths\/}
                 which are qualified by symbolic descriptions of the
                 positions for which the alias pair holds. Based on this
                 result, we present an algorithm for interprocedural
                 may-alias analysis with pointers which on numerous
                 examples that occur in practice is much more precise
                 than recently published algorithms [CWZ90, He90, LR92,
                 CBC93].",
  acknowledgement = ack-nhfb,
  annote =       "Published as part of the Proceedings of PLDI'94.",
  classification = "C6120 (File organisation)",
  conflocation = "Orlando, FL, USA; 20-24 June 1994",
  conftitle =    "ACM SIGPLAN '94 Conference on Programming Language
                 Design and Implementation (PLDI)",
  corpsource =   "Inst. Nat. de Recherche d'Inf. et d'Autom., Le
                 Chesnay, France",
  keywords =     "algorithms; alias pair; data structures;
                 interprocedural may-alias analysis; k-limiting;
                 location-based approximations; parametric framework;
                 performance; program optimization; program
                 parallelization; program verification; recursive
                 pointer data structures; region-based approximations;
                 store-based approximations; sub-objects; symbolic
                 access parallelization; symbolic access paths; symbolic
                 descriptions",
  sponsororg =   "ACM",
  subject =      "{\bf D.3.3} Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Procedures, functions, and
                 subroutines. {\bf D.3.3} Software, PROGRAMMING
                 LANGUAGES, Language Constructs and Features, Data types
                 and structures.",
  treatment =    "P Practical",
}

Related entries