sampsyo
commented
4 years ago Sounds good! I like the idea of measuring register pressure in an architecture-independent way. (There are other proposals to do proper register allocation, and they have to invent a "fake" notion of a limited register file to make things work.) Good luck!
What will you do?
I'm going to implement lazy code motion for Bril.
Lazy code motion (LCM) is a compiler optimization which shifts computations around in the control-flow graph in order to avoid redundant computation. It is termed "lazy" because computations are placed as late as possible in the CFG. It subsumes both common subexpression elimination and loop invariant code motion.
How will you do it?
The original lazy code motion paper[2] uses dataflow analysis to decide which expressions to move and where to move them to. They define the analysis with bidirectional systems of dataflow equations, in which changes to the value at a basic block influence the values at blocks preceding and succeeding it. It is computationally harder to solve these systems of dataflow equations and, more importantly, I don't have any code sitting around for solving them over bril programs.
Fortunately, there is a reformulation[1] of lazy code motion in terms of unidirectional systems of equations. I will adapt that presentation for Bril.
How will you empirically measure success?
I want to evaluate three things about my lazy code motion implementation. Qualitatively, I would like to gain some confidence in the correctness of the optimization by comparing the behavior of optimized tests to the behavior of unoptimized ones. Quantitatively, I want to measure changes in (1) number of Bril instructions executed and (2) register pressure over a set of "stress tests."
Counting instructions is an easy change to the Bril interpreter, and a simple metric to compare between an optimized and unoptimized program. Here I would hope that for each stress test, the number of instructions executed is lower for the optimized than for the unoptimized program.
Register pressure is a more complex metric. At a particular point in an execution, the register pressure is the number of live variables. Register pressure's performance impact comes when variables are spilled from registers to the stack. I would measure spills instead, but the interpreter does not have registers or register allocation. I will instead instrument the interpreter to track live ranges of variables, which will result in enough information for a post-processing step to compute register pressure at each point in the execution of a program. I can then compare the distributions of register pressure between optimized and unoptimized program runs. Success here would look like differences in the distributions of register pressure for optimized and unoptimized programs.
Team members: Just me!
References