Dynamic profiling and trace creation

Effective dynamic virtual-machine optimization depends on quickly finding and optimizing frequently-executed code regions. Such regions are naturally represented with a trace-cache, a collection of long, frequently-executed sequences of instructions. An ideal trace-cache is small and captures the majority of the program's execution stream, yet consists of traces large enough to allow for useful inter-bytecode optimizations and improve instruction-fetch performance. This thesis describes an efficient dynamic technique for finding and constructing such traces.Our trace caching algorithm relies on three innovative techniques: profiling data is managed with the Branch Implication Graph(BI-Graph) data structure, decomposing the program into small, independent, tree-like components using our hot subgraph filters the BI-Graph for relevant data, and traces are constructed from components using a minimum-bounded expected completion rate.We evaluated the runtime performance of our generated traces using a trace cache simulator implemented on top of the Java Virtual Machine, SableVM. Tested against Java benchmarks, our primary data structure, the BI-Graph, scales linearly with the loaded program size and is no larger than a control flow graph. On our benchmarks set, our traces capture 98.5% of the executed instructions, average 34 bytecodes instructions in length, and execute to completion 98.5% of the time. Further, the total size of all traces created scales linearly at 83% of the program's size, averaging only 50000 bytecodes. The entire algorithm, including context-sensitive, branch bias profiling and trace creation, has a projected overhead of only 4.5%. Thus, our algorithm efficiently constructs a small trace cache consisting of long traces that both tend to execute to completion and capture the majority of the execution stream