Whole program path profiling

Details Whole program path profiling Whole program path profiling

1999-04-30

2001-12-04

Powell, Mark R. (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C717S152000

Reexamination Certificate

active

06327699

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to the field of program path profiling and in particular to whole program path profiling.
COPYRIGHT NOTICE/PERMISSION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright © 1999, Microsoft Corporation, All Rights Reserved.
BACKGROUND OF THE INVENTION
A challenge facing computer architects, compiler writers, and programmers is to understand the dynamic behavior of a program. A program's performance is directly related to the events that occur while the program is executing. One way to increase program performance is to understand the dynamic behavior of a program and improve costly or frequently occurring portions of that program.
Program paths or traces are sequences of consecutively executed program blocks of instructions. These program paths or traces have provided programmers a window into a program's dynamic behavior by capturing aspects of a program's dynamic control flow, not just its aggregate behavior. Using these paths, programmers, compiler writers, and computer architects are provided with a way to improve performance. Programmers or compilers are able to identify heavily executed paths and tune them so that they perform faster.
Performance of large, complex systems, such as operating system and databases have been improved by identifying heavily executed paths and streamlining them into fast paths. 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. Recently designed computer architectures have also directly exploited traces or program flow to enhance instruction caching and execution.
Path profiling measures the frequency and cost of a program's executed paths. It is an essential technique to understand a program's control flow. However, current path profiling techniques normally only capture acyclic paths. Acyclic paths are short parts of a program's execution that, unfortunately, end at loop iteration and procedure boundaries, which are two of the most interesting points in a program's execution. Current techniques for path profiling are useful to programmers, but do not easily describe the program's flow through procedure boundaries and loop iterations. Without tools to conveniently identify expensive interprocedural paths, it is difficult to improve the performance of software.
There is a need for a mechanism that can perform path profiling while overcoming the acyclic and intraprocedural path limitations. There is a need for a mechanism to represent the entire flow control of an execution of a program. There is a need for a mechanism to represent the entire flow control of an execution of a program in a manageable format. There is a need for a mechanism to identify the most important parts of that representation so programmers can concentrate their efforts to improve those parts while providing the greatest benefit.
SUMMARY OF THE INVENTION
A program is instrumented to record acyclic paths during execution of the program. As the instrumented program is executed, an executed path trace is created. A whole program path is produced from the executed path trace. The whole program path is a complete compact record of a program's entire control flow. It includes a record of crossing loop boundaries and procedure boundaries to provide a complete picture of the program's dynamic behavior.
A path profiling tool is used to instrument the program with code to produce a trace of executed acyclic paths. An accumulator is incremented by predetermined amounts by such code along a select set of edges in a program's control-flow graph. At the end of an acyclic path, the value in the accumulator uniquely identifies the executed path. The path leading to a call site is recorded in the trace before any paths executed by a callee.
An algorithm is used to compress the path trace and uncover its regular structure. It comprises a string compression algorithm that constructs a context-free grammar for its input. The algorithm is of a type which has been used to find hierarchical structures in a variety of sequences, ranging from DNA sequences to genealogical database. It uses the insight that log N rules can generate N occurrences of a subsequence. The grammar used requires fewer symbols while explicitly capturing repetitions of selected patterns in a context free manner. The grammar is then compressed by representing strings of symbols which are unique identifiers for an acyclic path. The product of the compression is a directed acyclic graph referred to as a whole program path. This whole program path is not only a compact and lossless representation of the program's dynamic flow control, but is also a convenient representation for analysis.
Heavily executed subpaths may be easily identified from the representation. The whole program path is traversed to find the hot subpaths according to input parameters of minimum and maximum path lengths and minimum cost.
Directed acyclic graphs are also used to represent entities such as instructions, statements, basic blocks, memory addresses and acyclic paths as nodes, and the execution of such entities as edges between such nodes.


REFERENCES:
patent: 5067073 (1991-11-01), Andrews
patent: 5161216 (1992-11-01), Reps et al.
patent: 5355487 (1994-10-01), Keller et al.
patent: 5828883 (1998-10-01), Hall
patent: 5896538 (1999-04-01), Blandy et al.
patent: 5950009 (1999-09-01), Bortnikov et al.
patent: 5999736 (1999-12-01), Gupta et al.
patent: 6070009 (2000-05-01), Dean et al.
patent: 6151706 (2000-11-01), Lo et al.
patent: 6170083 (2001-01-01), Tabatabai
Hall, “Call path profiling”, ACM pp 296-306, Jun. 1992.*
Larus, “Whole program paths”, ACM SIGPLAN, pp 259-269, May 1999.*
Ball, “Effiicently counting program events with support for online queries”, ACM TPLS, pp 1399-1410, vol. 16, No. 5, Sep. 1994.*
Ionnidis et al, “Transitive closure algorithms based on graph traversal”, ACM Trans. Database Sys. vo. 18, No. 3, pp 512-576, Sep. 1993.*
Ammons, G., et al., “Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling”,Proceedings of the 1997 ACM SIGPLAN Conference on Programming Laguage Design and Implementation(PLDI),vol. 32, No. 5, pp. 85-96, (May 1997).
Ammons, G., et al., “Improving Data-flow Analysis with Path Profiles”,Proceedings of the 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation(PLDI), pp. 72-84.
Baker, B.S., “Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance”,Society for Industrial and Applied Mathematics Journal on Computing, 26(5), pp. 1343-1362, (1997).
Ball, T., “Efficient Path Profiling”,Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture, pp. 46-57, (Dec. 1996).
Ball, T., et al., “Edge Profiling versus Path Profiling: The Showdown”,Conference Record of POPL '98: The 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 134-148, (Jan. 1998).
Bodik, R., et al., “Refining Data Flow Information Using Infeasible Paths”,6th European Software Engineering Conference, 5th ACM SIGSOFT Symposium on the Foundations of Software Engineering, pp. 361-377, (1997).
Fisher, J.A., “Trace Scheduling: A Technique for Global Microcode Compaction”,IEEE Transactions on Computers, C-30(7), pp. 478-490, (Jul. 1981).
Fisher, J.A., et al., “Parallel Processing: A Smart Compiler and a Dumb Machinep”,Proceedings of the SIGPLAN '84 Symposium on Compiler Consturction, 19(6), pp. 37-47, (Jun. 1984).
Gupta, R., et al., “Path Profile Guid

Affiliated with

Also associated with

Rating

Whole program path profiling does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Whole program path profiling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Whole program path profiling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2564658