Lambda the Ultimate

Hi Yin, I did not have time to look at your paper in detail, but I look forward to reading it. I skipped to your references section to see the background. I think papers on spill code optimization may be relevant:

"Post Register Allocation Spill Code Optimization" Lupo & Wilken

"Spill Code Minimization by Spill Code Motion" Akira Koseki, Hideaki Komatsu, and
Toshio Nakatani

"Precise register-allocation spill-code costing and placement" [Chris Lupo's dissertation--may require an email to him]

"Spill code minimization via interference region spilling" Bergner et al.

"Progressive spill code placement" Dietmar Ebner, Bernhard Scholz, and Andreas Krall

Your paper seems primarily focused on live range splitting. There is an interesting paper Register Allocation Deconstructed that looks at the relative importance of live range splitting, coalescing, register assignment and spill code optimization. They compare a set of configurations which include optimal register allocation and existing heuristics. They conclude that live range splitting doesn't really matter:

The ability to insert moves (that is, split live ranges or undo coalescing) has surprisingly little impact on code quality. What benefit there is can primarily be obtained by allowing move insertions only at basic block boundaries.

They also conclude that coalescing and register assignment are adequately solved by existing heuristics, as they perform almost as well as the optimal algorithm. They conclude that spill code optimization is most important:

When optimizing for performance on a modern processor, spill code optimization is of paramount importance. Furthermore, the various components of register allocation can be treated separately without significantly impacting performance. Therefore, when targeting processor performance, new register allocator designs should focus on solving the spill code optimization problem as the coalescing, move insertion, and register assignment problems are adequately solved using existing heuristics

Your paper does address this in limited form in section 6. I have not read your paper in detail, but as far as I understand it can still be improved a lot. For example if you have this code:

    x = ...
    while(...){
      y = ...
      // x not used in loop
    }
    // x used here

Then your algorithm will spill x to the stack inside the loop:

    x = ...
    while(...){
      save x
      y = ...
      load x
    }
    // x used here

A much better solution is:

    x = ...
    save x
    while(...){
      y = ...
    }
    load x
    // x used here

Though perhaps (and even likely) I have misunderstood your algorithm. Implementation of your register allocator in e.g. LLVM and comparison with LLVM's existing register allocator is of course required to really evaluate your method.

Register allocation has long been formulated as a graph coloring problem, coloring the dependency graph with physical registers. Such a formulation does not fully capture the goal of the allocation, which is to minimize the traffic between registers and memory.

I don't think that "minimiz[ing] the traffic between registers and memory" fully captures the goal of register allocation either. This goal statement leads, in the limit, to regarding register-register moves and swaps as free... and some work on SSA-style register allocation does just that.

Assigning a nil cost to register moves and swaps does make most register-allocation-related problems easy, if not trivial. We can simply have arbitrary assignments from values to locations (registers or stack slots) at each instruction, and insert spill-free permutation code between each assignment. Since register-register moves are free, so is the permutation code. We've just redefined our problem from NP-complete (for a decision version, i.e. "can this be allocated in k registers?") to trivially polynomial-time (is MAXLIVE ≤ k). This sort of simplification makes me suspicious.

In practice, algorithms based on the assumption that register moves or swaps are free nevertheless include heuristics to forcibly coalesce live ranges, in order to reduce the number of moves and swaps. Otherwise, performance quickly becomes atrocious: even register-register move instructions consume memory bandwidth, I-cache space, and decoding and scheduling resources. So, the goal is *not* strictly to minimise register-memory moves; the statement is a useful approximation, but forgetting that it's an approximation can easily lead us to trivial and useless solutions. In fact, I would argue that it's more harmful to performance than the approximation made by colouring-based allocators (values or variables must be assigned exactly one location for all program points), which merely replaces penalized constraints with hard ones.