Entry Patterson:1995:ASB 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{Patterson:1995:ASB,
  author =       "Jason R. C. Patterson",
  title =        "Accurate static branch prediction by value range
                 propagation",
  journal =      j-SIGPLAN,
  volume =       "30",
  number =       "6",
  pages =        "67--78",
  month =        jun,
  year =         "1995",
  CODEN =        "SINODQ",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  bibdate =      "Sun Dec 14 09:17:06 MST 2003",
  bibsource =    "http://portal.acm.org/;
                 http://www.acm.org/pubs/contents/proceedings/pldi/207110/index.html",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/207110/p67-patterson/",
  abstract =     "The ability to predict at compile time the likelihood
                 of a particular branch being taken provides valuable
                 information for several optimizations, including global
                 instruction scheduling, code layout, function inlining,
                 interprocedural register allocation and many high level
                 optimizations. Previous attempts at static branch
                 prediction have either used simple heuristics, which
                 can be quite inaccurate, or put the burden onto the
                 programmer by using execution profiling data or source
                 code hints.\par This paper presents a new approach to
                 static branch prediction called {\em value range
                 propagation\/}. This method tracks the weighted value
                 ranges of variables through a program, much like
                 constant propagation. These value ranges may be either
                 numeric of symbolic in nature. Branch prediction is
                 then performed by simply consulting the value range of
                 the appropriate variable. Heuristics are used as a
                 fallback for cases where the value range of the
                 variable cannot be determined statically. In the
                 process, {\em value range propagation\/}subsumes both
                 constant propagation and copy propagation.\par
                 Experimental results indicate that this approach
                 produces significantly more accurate predictions than
                 the best existing heuristic techniques. The {\em value
                 range propagation\/} method can be implemented over any
                 ``factored'' dataflow representation with a static
                 single assignment property (such as SSA form or a
                 dependence flow graph where the variables have been
                 renamed to achieve single assignment). Experimental
                 results indicate that the technique maintains the
                 linear runtime behavior of constant propagation
                 experienced in practice.",
  acknowledgement = ack-nhfb,
  affiliation =  "Sch. of Comput. Sci., Queensland Univ. of Technol.,
                 Brisbane, Qld., Australia",
  annote =       "Published as part of the Proceedings of PLDI'95.",
  classification = "C1140 (Probability and statistics); C6150C
                 (Compilers, interpreters and other processors); C6150G
                 (Diagnostic, testing, debugging and evaluating
                 systems); C6150N (Distributed systems software)",
  keywords =     "Accurate static branch prediction; algorithms; Branch
                 likelihood; Code layout; Compile time; Constant
                 propagation; Copy propagation; experimentation;
                 Factored dataflow representation; Function inlining;
                 Global instruction scheduling; Heuristics; High level
                 optimizations; Interprocedural register allocation;
                 Linear runtime behavior; Optimizations; performance;
                 Program; Static single assignment property; Value range
                 propagation; Weighted value variable ranges",
  subject =      "{\bf D.3.4} Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf F.3.3} Theory of
                 Computation, LOGICS AND MEANINGS OF PROGRAMS, Studies
                 of Program Constructs. {\bf D.3.4} Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers. {\bf
                 F.3.1} Theory of Computation, LOGICS AND MEANINGS OF
                 PROGRAMS, Specifying and Verifying and Reasoning about
                 Programs.",
  thesaurus =    "Optimising compilers; Probability; Processor
                 scheduling; System monitoring",
}

Related entries