Whole Program Paths James R. Larus Microsoft Research One Microsoft Way Redmond, WA 98052 [email protected] www.research.microsoft.com/-tat-us Abstract Whole program paths (WPP) are a new approach to capturing and representing a program’s dynamic -actually executed--control flow. Unlike other path profiling techniques, which record intraprocedural or acyclic paths, WPPs produce a single, compact description of a program’s entire control flow, including loop iteration and interprocedural paths. This paper explains how to collect and represent WPPs. It also shows how to use WPPs to find hot subpaths, which are the heavily executed sequences of code that should be the focus of performance tuning and compiler optimization. Keywords dynamic program measurement, program tracing, path profiling, program control flow, data compression 1. Introduction A central challenge facing computer architects, compiler writers, and mere mortal programmers is to understand a program’s dynamic behavior. Events that occur while a program runs are often elusive, but they provide a basis for understanding the program’s behavior and improving its performance. Program paths or traces-sequences of consecutively executed basic blocks-offer one of the few clear windows into a program’s dynamic behavior. Paths, unlike other techniques, such as block or edge profiles, capture aspects of a program5 dynamic control flow, not just its aggregate behavior. Paths have long provided a unifying context for performance tuning. Programmers have improved the performance of large, complex systems, such as operating systems and databases, by identifying heavily executed paths and streamlining them into “fast paths” [20,24]. In compilers as well, trace scheduling and, more recently, path-based compilation demonstrate that program optimization can benefit from a focus on a program’s dynamic control flow [2, 8, 11, 12, 141. Recently designed computer architectures have also directly exploited traces to enhance instruction caching and execution [I 5,25,26]. Paths are often identified by ad-hoc approaches; although recently developed path profiling techniques can inexpensively identify Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advan- tage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SIGPLAN ‘99 (PLDI) 5/99 Atlanta, GA, USA 0 1999 ACM 1.58113.083.X/99/0004...$5.00 executed path segments and quantify their cost [2,6,7]. Previous path profiling algorithms, however, captured acyclic paths, which are short, disjoint snippets of execution that unfortunately end at loop and procedure boundaries-two of the most interesting points in a program’s execution [6] (this technique has been extended to handle paths that cross procedure boundaries [ 191). This paper describes a new approach to measuring a program’s control flow that captures a complete picture of the program’s dynamic behavior. The technique introduces whole program paths (WPP), which are a complete, compact record of a program’s entire control flow. A whole program path crosses both loop and procedure boundaries, and so provides a practical basis for interprocedural path profiling. This paper explains how to record a WPP, describes its representation, shows that this representation can be used to analyze program behavior, and demonstrates the technique’s practicality on SPEC benchmarks and commercial application programs. 1.1 Overview Whole program paths are collected in two phases. The first produces a trace of the acyclic paths executed by a program. The second phase transforms the trace into a more compact and usable form by finding its inherent regularity (i.e., repeated code). In practice, compression can run concurrently with the instrumented program, so only the compressed form need be stored. The product of compression is a directed acyclic graph (DAG), which is not only a compact and lossless representation of the programs dynamic control flow, but is also a convenient representation for analysis. This paper describes one such analysis, which identifies heavily executed (hot) subpaths. Figure 1 illustrates the process of recording a whole program path. . Section 2 briefly describes the trace instrumentation and resulting sequence of acyclic paths. One novel contribution of this work is the next phase (compression), which turns a stream of acyclic paths into a context-free grammar. The compression technique is based on Nevill-Manning and WittenS SEQUITUR hierarchical compression algorithm [21, 221. This linear, on-line algorithm builds a context-free grammar for a string. The resulting grammar reflects its input’s hierarchical structure and is typically far more compact than the original sequence. Section 3 describes Nevill- Manning and Witten’s algorithm and a modification that enhances its performance. The product of this algorithm is a grammar. The DAG representation of this grammar, called a Whole-Program Path (WPP), compactly and effectively records a program’s entire control flow. Section 4 presents another contribution of this work, which is an analysis technique for WPPs. Section 5 contains measurements of the technique on SPEC benchmarks and Microsoft’s SQL database and WinWord document processor. As an example, consider the code in Figure 2. The loop executes nineteen acyclic paths (labeled 1-5). The SEQUITUR algorithm 259PP (Path Profiling Tool) Whole Program Figure 1. Collecting a Whole Program Path. A path-profiling tool (PP) instruments a program to produce a trace of executed wyclic paths. These paths are processed by another tool (PPCompress) into a Whole Program Path (WPP). Further tools analyze WPPs to find performance bottlenecks or program errors. processes the path trace and produces the grammar in the figure. mechanism originally used to terminate paths at loop backedges The grammar’s DAG representation is the
View Full Document
Unlocking...