Entry Briggs:1992:R 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{Briggs:1992:R,
  author =       "Preston Briggs and Keith D. Cooper and Linda Torczon",
  title =        "Rematerialization",
  journal =      j-SIGPLAN,
  volume =       "27",
  number =       "7",
  pages =        "311--321",
  month =        jul,
  year =         "1992",
  CODEN =        "SINODQ",
  ISBN =         "0-89791-475-9",
  ISBN-13 =      "978-0-89791-475-8",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  LCCN =         "QA76.7.S53 1992",
  bibdate =      "Sun Dec 14 09:16:22 MST 2003",
  bibsource =    "Compendex database; http://portal.acm.org/;
                 http://www.acm.org/pubs/contents/proceedings/pldi/143095/index.html",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/143095/p311-briggs/",
  abstract =     "This paper examines a problem that arises during
                 global register allocation --- {\em
                 rematerialization\/}. If a value cannot be kept in a
                 register, the allocator should recognize when it is
                 cheaper to recompute the value (rematerialize it) than
                 to store and reload it. Chaitin's original
                 graph-coloring allocator handled simple instance of
                 this problem correctly. This paper details a general
                 solution to the problem and presents experimental
                 evidence that shows its importance. Our approach is to
                 tag individual values in the procedure's SSA graph with
                 information specifying how it should be spilled. We use
                 a variant of Wegman and Zadeck's {\em sparse simple
                 constant\/} algorithm to propagate tags throughout the
                 graph. The allocator then splits live ranges into
                 values with different tags. This isolates those values
                 that can be easily rematerialized from values that
                 require general spilling. We modify the base allocator
                 to use this information when estimating spill costs and
                 introducing spill code. Our presentation focuses on
                 rematerialization in the context of Chaitin's
                 allocator; however, the problem arises in any global
                 allocator. We believe that our approach will work in
                 other allocators-while the details of implementation
                 will vary, the key insights should carry over
                 directly.",
  acknowledgement = ack-nhfb,
  affiliation =  "Rice Univ",
  affiliationaddress = "Houston, TX, USA",
  annote =       "Published as part of the Proceedings of PLDI'92.",
  classification = "723.1",
  conference =   "Proceedings of the ACM SIGPLAN '92 Conference on
                 Programming Language Design and Implementation",
  conferenceyear = "1992",
  journalabr =   "SIGPLAN Not",
  keywords =     "algorithms; Chaitin-style allocators; Computer
                 programming; experimentation; Global register
                 allocation; Program compilers; Rematerialization",
  meetingaddress = "San Francisco, CA, USA",
  meetingdate =  "Jun 17--19 1992",
  meetingdate2 = "06/17--19/92",
  sponsor =      "ACM",
  subject =      "{\bf G.2.2} Mathematics of Computing, DISCRETE
                 MATHEMATICS, Graph Theory, Graph algorithms. {\bf
                 D.3.4} Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization. {\bf D.3.4} Software, PROGRAMMING
                 LANGUAGES, Processors, Compilers. {\bf F.3.3} Theory of
                 Computation, LOGICS AND MEANINGS OF PROGRAMS, Studies
                 of Program Constructs.",
}

Related entries