David I. August
Professor in the Department of Computer Science, Princeton University
Affiliated with the Department of Electrical Engineering, Princeton University
Ph.D. May 2000, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign

Office: Computer Science Building Room 221
Email: august@princeton.edu
Phone: (609) 258-2085
Fax: (609) 964-1699
Administrative Assistant: Pamela DelOrefice, (609) 258-5551

Front Page Publication List (with stats) Curriculum Vitae (PDF) The Liberty Research Group


Selective Runtime Memory Disambiguation in a Dynamic Binary Translator [abstract] (PDF)
Bolei Guo, Youfeng Wu, Cheng Wang, Matthew J. Bridges, Guilherme Ottoni, Neil Vachharajani, Jonathan Chang, and David I. August
Proceedings of the 15th International Conference on Compiler Construction (CC), March 2006.
Accept Rate: 23% (17/72).

Performing runtime alias analysis in a dynamic binary translator (DBT) is difficult due to incomplete control-flow information and the high complexity of accurate alias analysis. Whole-program profiling, however, shows that the vast majority of memory references do not alias. The current technique used in DBTs to disambiguate memory references, instruction inspection, is too simple and can only disambiguate one-third of potential aliases. To address the problem of effective memory disambiguation while keeping a tight bound on the analysis overhead, we propose an efficient heuristic algorithm that strategically selects key memory dependences to disambiguate with runtime checks. These checks have little runtime overhead and, in the common case where aliasing does not occur, enable aggressive optimizations, particularly scheduling to be performed. We demonstrate that a small number of checks, inserted with a low overhead analysis, can approach optimal scheduling, where all false memory dependences are removed.