Entry Hailperin:1998:CCM from toplas.bib

Last update: Tue May 1 02:05:46 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | 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{Hailperin:1998:CCM,
  author =       "Max Hailperin",
  title =        "Cost-optimal code motion",
  journal =      j-TOPLAS,
  volume =       "20",
  number =       "6",
  pages =        "1297--1322",
  month =        nov,
  year =         "1998",
  CODEN =        "ATPSDT",
  ISSN =         "0164-0925 (print), 1558-4593 (electronic)",
  ISSN-L =       "0164-0925",
  bibdate =      "Wed Apr 21 14:24:56 MDT 1999",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/toplas.bib",
  URL =          "http://www.acm.org:80/pubs/citations/journals/toplas/1998-20-6/p1297-hailperin/",
  abstract =     "We generalize Knoop et al.'s Lazy Code Motion (LCM)
                 algorithm for partial redundancy elimination so that
                 the generalized version also performs strength
                 reduction. Although Knoop et al. have themselves
                 extended LCM to strength reduction with their Lazy
                 Strength Reduction algorithm, our approach differs
                 substantially from theirs and results in a broader
                 class of candidate expressions, stronger safety
                 guarantees, and the elimination of the potential for
                 performance loss instead of gain. Also, our general
                 framework is not limited to traditional strength
                 reduction, but rather can also handle a wide variety of
                 optimizations in which data-flow information enables
                 the replacement of a computation with a less expensive
                 one. As a simple example, computations can be hoisted
                 to points where they are constant foldable. Another
                 example we sketch is the hoisting of polymorphic
                 operations to points where type analysis provides
                 leverage for optimization. Our general approach
                 consists of placing computations so as to minimize
                 their cost, rather than merely their number. So long as
                 the cost differences between flowgraph nodes obey a
                 certain natural constraint, a cost-optimal code motion
                 transformation that does not unnecessarily prolong the
                 lifetime of temporary variables can be found using
                 techniques completely analogous to LCM. Specifically,
                 the cost differences can be discovered using a wide
                 variety of forward data-flow analyses in a manner which
                 we describe.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Transactions on Programming Languages and
                 Systems",
  keywords =     "algorithms; performance",
  subject =      "{\bf D.3.4} Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization",
}

Related entries