phd

Title:
	Reoptimizing meta-tracing
Synopsis:
        Meta-tracing enables virtual machines (VMs) to decide which part
        of a program should be optimized. When a VM gets some code to execute, it
        needs to convert the code to instructions that can be executed on the
        hardware. The VM can either convert the code to assembly or try to
        optimize the code before generating assembly. Optimizing code is an
        expensive operation; that is why most VMs usually identify ahead which
	portion of code could be worth optimizing (in the sense that you would
	gain more time running the optimized code than you lost optimizing it).
        This is what we call the profiling phase; most of the time it indicates
        which function or loop is "hot" by looking only at the number of time
        it was called. Theses points are called hotspots.

        Therefore, some VMs also carry a "tracer". The tracing phase runs
        once a hotspot has been hit. It continues the execution of the hotspot
	but this time it saves every operations in what is called a "trace".
	Given that the tracer ran for the real execution of the hotspot, we now
	have information on the runtime of the program being executed that were
	inaccessible before. This trace should be used to know which part of
	the code ought to be optimized. Since the trace ran only once, it
	probably missed most of the code and branching (conditions) which imply
	that the generated optimizations will not apply in every case. We need
	to detect whether we have to jump from the optimized code to the
	un-optimized code: this check is performed in what we call a "guard".

        Right now it is important to understand that tracing a program is
        extremely slow since it needs to stop the program after every
        instruction to execute some unrelated VM’s internal code.

	Whereas a direct tracing compiler records the execution of a user-
	program directly, meta-tracing refers to a configuration where a tracing
	interpreter executes another language interpreter while this language
	interpreter itself is executing a user-program. The tracing interpreter
	traces the execution of the language interpreter and the recorded
	traces are then optimized.[1]

        This Ph.D will focus especially on this subject: searching ways to
	optimize the meta-tracer in VMs.

	Traditionally, meta-tracing VMs have traced a path through a program
	and stuck with it. Although side-traces are generated when guards fail,
	the original trace is always the best optimized, even if it does not
	represent the most common path through the program.
	To work our way into the optimization of the tracing phase, the first
        step is to get performance data that could help us assess the value of
	our changes. Gladly we should be able to base our work on previous work
	made by the soft-dev team which provided "Krun". Krun is an hypervisor
	that allows you to do more precise, reproductible and easier benchmark.
	We can notice it was used especially to benchmark VMs.[2]
	Once this is done we can start working on way to optimize the tracer.
	The first optimization we thought of is to provide a tracer that
	does hardware tracing instead of software tracing. Indeed, in the most
	common CPUs today (intel, AMD and ARM) there are instructions providing
	this functionnality. This obviously needs to be benchmarked, but if the
	CPU handle the saving of the operations we should expect a huge speedup.
	We also thought of relying on heuristics to decide when and if we should
	really trace a path, of course if we can avoid tracing we will save a
	lot of time, but doing heuristics is also an expensive operation and
	should be taken with great care during benchmarks.

	[1]: The Impact of Meta-Tracing on VM Design and Implementation
	     Carl Friedrich Bolz, Laurence Tratt
	[2]: Virtual Machine Warmup Blows Hot and Cold
	     Edd Barrett, Carl Friedrich Bolz, Rebecca Killick, Sarah Mount,
	     Laurence Tratt