Accurate critical path analysis via random trace construction

Pierre Salverda, Charles Tucker, Craig Zilles

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a new approach to performing program analysis through, profile-guided random generation of instruction traces. Using hardware support available in commercial processors, we profile the behavior of individual instructions. Then, in conjunction with the program binary, we use that information to fabricate short (1,000-instruction) traces by randomly evaluating branches in proportion to their profiled behavior. We demonstrate our technique in the context of critical path analysis, showing it can achieve the same accuracy as a hardware critical path predictor, but with lower hardware requirements. Key to achieving this accuracy is correctly identifying memory dependences in the fabricated trace, for which purpose we use a form of abstract interpretation to identify aliasing store-load pairs without explicitly profiling them. We also demonstrate that our approach is very tolerant of the quality of profile information available.

Original languageEnglish (US)
Title of host publicationProceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization
Pages64-73
Number of pages10
DOIs
StatePublished - May 19 2008

Publication series

NameProceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization

Keywords

  • Instruction criticality
  • Profiling
  • Trace fabrication

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Accurate critical path analysis via random trace construction'. Together they form a unique fingerprint.

  • Cite this

    Salverda, P., Tucker, C., & Zilles, C. (2008). Accurate critical path analysis via random trace construction. In Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization (pp. 64-73). (Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization). https://doi.org/10.1145/1356058.1356068