Melvin's digital garden

Register Allocation by Puzzle Solving

CREATED: 200809030303 Speaker: Jens Palsberg, Fernando M Q Pereira ** Register Allocation

  • Liveness analysis $\rightarrow$ interference graph $\rightarrow$ graph coloring (#colors = #registers)
  • Other approaches: Linear scan, ILP, Partitioned Boolean QP, Multi-commodity network flow
  • Challenges ** spill: not enough registers, need to use memory ** coalesce: for assignment x=y, map x and y to same register ** live-range splitting: enable a register to some times be in a register and some times in memory ** pre-coloring: arguments must be in registers when calling functions ** register aliasing: a single 16bit register can be used as two 8 bit registers ** rematerialization: don’t store, recompute ** Puzzles Approach
  • original program $\rightarrow$ elementary program $\rightarrow$ assembly code
  • register allocation for elementary programs equivalent to puzzle solving
  • elemenatary programs obtained by live range splitting, immediately renaming a variable after each statement
  • Pieces: elementary programs results in very short live ranges of length 1 or 2
  • Puzzle board: different types of archetecture gives rise to different types of registers
  • Algorithm: fill each register one at a time using a set of 15 rules (order of applying the rules matter!) ** Results
  • With pre coloring, without spilling is $O(|P| #reg)$
  • With pre coloring and spilling is NP-complete
  • Coalescing is important to reduce renaming, use solution of previous puzzle board to guide the solution of the current board
  • Without pre coloring, coalescing can be solved optimally using fewest number of moves ** Comparison with Graph Coloring
  • Graph coloring model variables as vertices and assign registers to variables
  • Puzzle solving models registers as puzzle boards and variables as puzzle pieces filling the boards

Links to this note