Register allocation

- Register allocation - Register allocation is an important optimization affecting the performance of compiled code. For example, good register allocation can improve the performance of several SPEC benchmarks by an order of magnitude relative to when they are compiled with poor or no register allocation.
  - Background
    - Live ranges - variables, temporaries, virtual/symbolic registers
      - ranges that interfere - in graph, edges connect these - no two nodes with an edge connection can have same color - if not colorable, some edges removed (they will be "spilled", or accessed from memory, or not assigned to registers), until the remaining graph can be colored.
    - Coalescing - eliminating redundant moves - if source and destination of a move do not share an edge, the nodes can be coalesced into one, and the move eliminated - Chaitin's algorithm - however this can cause uncolorable graphs, so more conservative approach (George and Appel 1996) helps avoid spills.
  - Lecture notes on compilers and coloring - http://www.cs.ucla.edu/~palsberg/course/cs132/color-lecturenotes.pdf and http://www.cs.ucla.edu/~palsberg/course/cs132
  - Examples:
    - SSA - Static Single Assignment
      - Transform
      - issues of converting imperative to functional
      - Alpha normal (a-normal form)
      - ssa makes other transforms easier
      - limitation: ssa cant allocate registers
    - Register allocation via graph coloring
    - Linear Scan Register Allocation - link - several times quicker than graph coloring, and quiet efficienct (within 12% for most benchmarks)
      - several times slower: just allocating k registers to k most frequently used variables
        
        fast graph coloring allocator used in tcc dynamic compiler
    - Aggressive coloring algorithm - iterated register coalescing
    - Second-chance binpacking - more work at compile time - more complex linear scan algorithm, refined version of binpacking used in DEC GEM optimizing compiler. includes code rewriting, sometimes variable in register, sometimes not.