Linear scan register allocation algorithm

linear-scan-algo.py

LinearScanRegisterAllocation
  active <- {}
  foreach live interval i, in order of increasing start point
    ExpireOldIntervals(i)
    if length(active) == R then
      SpillAtInterval(i)
    else
      register[i] <- a register removed from pool of free registers
      add i to active, sorted by increasing end point

ExpireOldIntervals(i)
  foreach interval j in active, in order of increasing end point
    if endpoint[j] >= startpoint[i] then  # > が正しい気がする。
      return
    remove j from active
    add register[j] to pool of free registers

SpillAtInterval(i)
  spill <- last interval in active
  if endpoint[spill] > endpoint[i] then
    register[i] <- register[spill]
    location[spill] <- new stack location
    remove spill from active
    add i to active, sorted by increasing end point
  else
    location[i] <- new stack location