Grant Wallace
CS 597d
 
Observation 9:
 
Whole Program Paths [1]
 
Strengths:
1. Captures the entire trace of a program. Useful for optimizing between loop iterations and across function calls.
2. Represents the trace as a directed acyclic graph (DAG). This is an easy representation to work with when identifying hot subpaths.
3. Identifies hot subpaths which cross (or span) acyclic path boundaries based on cost and subpath size.
4. Can compress the trace (Sequitur algorithm) on the fly in O(n) time.
5. Achieves compression ratios of between 15-400 compared to original trace size.
 
Weaknesses:
    The Sequitur algorithm produces very simple grammars (digrams). This will lead to larger DAG size and more time in computing hot subpaths.
 
    Note that in the WPP representation an acyclic path can span multiple iterations of a loop, recursive function calls or consecutive function calls. For instance if a loop took path A on the first iteration, and then path B, and then repeated itself, the path AB would be considered acyclic.
    The algorithm in the paper identifies hot subpaths that span acyclic paths (i.e. joining successor and predecessor symbols from two adjoining acyclic paths). But no mention is made of identifying hot acyclic paths (i.e. AB of two loop iterations as above). These hot acyclic paths would be easy to identify by the weighting factor already assigned in the DAG. Since subpaths are defined as short sequences of acyclic paths, this may be covered in the limiting case where the sequence size is 1.
 
Further research:
    Sequitur only creates digrams. Perhaps a richer grammar can be produced without much added cost. This would reduce the depth of the DAG, and the time complexity of analyzing it.
    It would be interesting to perform some optimizations based on the hot subpaths and see how much speedup is obtained as compared to optimizations using regular profiling information. Is the added cost and complexity worth it?
 
 
[1] James Larus, "Whole Program Paths", Proceedings of the SIGPLAN 1999 Conference on Programming Languages Design and Implementation (PLDI 99), May 1999.