Selective runtime memory disambiguation in a dynamic binary translator

Bolei Guo, Youfeng Wu, Cheng Wang, Matthew J. Bridges, Guilherme Ottoni, Neil Vachharajani, Jonathan Chang, David I. August

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

4 Scopus citations

Abstract

Alias analysis, traditionally performed statically, is unsuited for a dynamic binary translator (DBT) due to incomplete control-flow information and the high complexity of an accurate analysis. Whole- program profiling, however, shows lhat most 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 achieve effective memory disambiguation while keeping a tight bound on 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, We demonstrate thai a small number of checks, inserted with a low-overhead analysis, can approach optimal scheduling, where all false memory dependences are removed. Simulation shows that better scheduling alone improves overall performance by 5%.

Original languageEnglish (US)
Title of host publicationCompiler Construction - 15th International Conference, CC 2006, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2006, Proceedings
PublisherSpringer Verlag
Pages65-79
Number of pages15
ISBN (Print)354033050X, 9783540330509
DOIs
StatePublished - 2006
Event15th International Conference on Compiler Construction, CC 2006. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2006 - Vienna, Austria
Duration: Mar 30 2006Mar 31 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3923 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th International Conference on Compiler Construction, CC 2006. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2006
CountryAustria
CityVienna
Period3/30/063/31/06

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Selective runtime memory disambiguation in a dynamic binary translator'. Together they form a unique fingerprint.

Cite this