Trace Execution Automata In Dynamic Binary Translation

Program performance can be dynamically improved by optimizing its frequent execution traces. Once traces are collected, they can be analyzed and optimized based on the dynamic information derived from the program's previous runs. The ability to record traces is thus central to any dynamic binary translation system. Recording traces, as well as loading them for use in different runs, requires code replication to represent the trace. This paper presents a novel technique which records execution traces by using an automaton called TEA (Trace Execution Automata). Contrary to other approaches, TEA stores traces implicitly, without the need to replicate execution code. TEA can also be used to simulate the trace execution in a separate environment, to store profile information about the generated traces, as well to instrument optimized versions of the traces. In our experiments, we showed that TEA decreases memory needs to represent the traces (nearly 80% savings). © 2011 Springer-Verlag.6161 LNCS99116Bala, V., Duesterwald, E., Banerjia, S., Dynamo: A transparent dynamic optimization system (2000) SIGPLAN Not., 35 (5), pp. 1-12Baraz, L., Devor, T., Etzion, O., Goldenberg, S., Skaletsky, A., Wang, Y., Zemach, Y., Ia-32 execution layer: A two-phase dynamic translator designed to support ia-32 applications on itanium®-based systems (2003) MICRO 36: Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture, p. 191Cifuentes, C., Emmerik, M.V., Uqbt: Adaptable binary translation at low cost (2000) Computer, 33 (3), pp. 60-66Dehnert, J.C., Grant, B.K., Banning, J.P., Johnson, R., Kistler, T., Klaiber, A., Mattson, J., The transmeta code morphing™software: Using speculation, recovery, and adaptive retranslation to address real-life challenges (2003) CGO 2003: Proceedings of the International Symposium on Code Generation and Optimization, pp. 15-24Duesterwald, E., Bala, V., Software profiling for hot path prediction: Less is more (2000) ASPLOS-IX:Proceedings of TheNinth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 202-211Ebcioǧlu, K., Altman, E.R., Daisy: Dynamic compilation for 100% architectural compatibility (1997) ISCA 1997: Proceedings of the 24th Annual International Symposium on Computer Architecture, pp. 26-37Ebcioǧlu, K., Altman, E.R., Gschwind, M., Sathaye, S., Optimizations and oracle parallelism with dynamic translation (1999) MICRO 32: Proceedings of the 32nd Annual ACM/IEEE International Symposium on Microarchitecture, pp. 284-295Friendly, D.H., Patel, S.J., Patt, Y.N., Putting the fill unit to work: Dynamic optimizations for trace cache microprocessors (1998) MICRO 31: Proceedings of the 31st Annual ACM/IEEE International Symposium on Microarchitecture, pp. 173-181Gal, A., Franz, M., (2006) Incremental Dynamic Code Generation with Trace Trees, , Tech. Rep. 06-16, Donald Bren School of Information and Computer Science, University of California, Irvine NovemberGal, A., Eich, B., Shaver, M., Anderson, D., Mandelin, D., Haghighat, M.R., Kaplan, B., Franz, M., Trace-based just-in-time type specialization for dynamic languages (2009) PLDI 2009: Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 465-478Gschwind, M., Ebcioǧlu, K., Altman, E., Sathaye, S., Binary translation and architecture convergence issues for ibm system/390 (2000) ICS 2000: Proceedings of the 14th International Conference on Supercomputing, pp. 336-347Hookway, R., Digital fx!32: Running 32-bit x86 applications on alpha nt (1997) COMPCON 1997: Proceedings of the 42nd IEEE International Computer Conference, p. 37Klaiber, A., (2000) The Technology behind Crusoe™ Processors, , Tansmeta Corporation JanuaryLuk, C.K., Cohn, R., Muth, R., Patil, H., Klauser, A., Lowney, G., Wallace, S., Hazelwood, K., Pin: Building customized program analysis tools with dynamic instrumentation (2005) PLDI 2005: Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 190-200Porto, J.P., Araujo, G., Wu, Y., Borin, E., Wang, C., Compact trace trees in dynamic binary translators (2009) 2nd Workshop on Architectural and Micro- Architectural Support for Binary Translation, AMAS-BT 2009Rotenberg, E., Bennett, S., Smith, J.E., Trace cache: A low latency approach to high bandwidth instruction fetching (1996) MICRO 29: Proceedings of the 29th Annual ACM/IEEE International Symposium on Microarchitecture, pp. 24-35Sprangle, E., Carmean, D., Increasing processor performance by implementing deeper pipelines (2002) SIGARCH Comput. Archit. News, 30 (2), pp. 25-34Suganuma, T., Yasue, T., Nakatani, T., A region-based compilation technique for dynamic compilers (2006) ACM Trans. Program. Lang. Syst., 28 (1), pp. 134-174Wang, C., Hu, S., Kim, H., Nair, S.R., Breternitz, M., Ying, Z., Wu, Y., Stardbt: An efficient multi-platform dynamic binary translation system (2007) Asia-Pacific Computer Systems Architecture Conference, pp. 4-15Wimmer, C., Cintra, M.S., Bebenita, M., Chang, M., Gal, A., Franz, M., Phase detection using trace compilation (2009) PPPJ 2009: Proceedings of the 7th International Conference on Principles and Practice of Programming in Java, pp. 172-181Zaleski, M., Brown, A.D., Stoodley, K., Yeti: A gradually extensible trace interpreter (2007) VEE 2007: Proceedings of the 3rd International Conference on Virtual Execution Environments, pp. 83-9