Trace tree

A trace tree is a data structure that is used in the runtime compilation of programming code. Trace trees are used in tracing just-in-time compilation where tracing is used during code execution to look for hot spots before compilation. When those hot spots are entered again the compiled code is run instead. Each statement executed is traced, including within other function calls, and the entire execution path is compiled. This is different from compiling individual functions. More information can be gained allowing better compiler optimizations, including the removal of some function call overhead. The interpreter is called to continue whenever compiled code makes calls to code outside the compilation contexts.

References

• Bala, Vasanth; Duesterwald, Evelyn; Banerjia, Sanjeev (June 1999), Transparent Dynamic Optimization: The Design and Implementation of Dynamo, https://www.hpl.hp.com/techreports/1999/HPL-1999-78.html, retrieved 2020-12-18 
• Incremental Dynamic Code Generation with Trace Trees, November 2006, https://static.aminer.org/pdf/PDF/000/286/022/profile_driven_generation_of_trace_samples.pdf, retrieved 2020-12-18 
• Making the Compilation "Pipeline" Explicit: Dynamic Compilation Using Trace Tree Serialization, October 2007 
• Double, Chris (February 2008), Quick Introduction to Tamarin Tracing, https://bluishcoder.co.nz/2008/05/20/quick-introduction-to-tamarin-tracing.html, retrieved 2020-12-18 
• Chang, Mason (January 12, 2009), The Difference Between Extended Basic Blocks and Traces, http://www.masonchang.com/blog/2009/1/13/the-difference-between-extended-basic-blocks-and-traces.html 
• Bolz, Carl Friedrich (March 2, 2009), PyPy Blog: Applying a Tracing JIT to an Interpreter, https://morepypy.blogspot.com/2009/03/applying-tracing-jit-to-interpreter.html, retrieved 2020-12-18