Partial Data Traces: EÆcient Generation and Representation

Binary manipulation techniques are increasing in popularity. They support program transformations tai-lored toward certain program inputs, and these trans-formations have been shown to yield performance gains beyond the scope of static code optimizations without pro le-directed feedback. They even deliver moderate gains in the presence of prole-guided optimizations. In addition, transformations can be performed on the entire executable, including library routines. This work focuses on program instrumentation, yet another appli-cation of binary manipulation. This paper reports preliminary results on generat-ing partial data traces through dynamic binary rewrit-ing. The contributions are threefold. First, a portable method for extracting precise data traces for partial executions of arbitrary applications is developed. Sec-ond, a set of hierarchical structures for compactly rep-resenting these accesses is developed. Third, an eÆ-cient online algorithm to detect regular accesses is in-troduced. These eorts are part of a larger project to counter the increasing gap between processor and main memory speeds by means of software optimization and hardware enhancements. 1