feat: apply register allocation in `zkasm`

[letypequividelespoubelles]

Actual not optimized

pub fn useless(INST, INPUT u128,) -> (OUTPUT u1){
   if INST = 0      goto doNothing
   if INST==5      goto instGt5
   if INST==13    goto instLt13
fail

doNothing
OUTPUT = 0
return

instGt5:
 var tmpInputMinus5 u128
OUTPUT, tmpInputMinus5 = INPUT - 5
return

instGt5:
var tmp13MinustInput u128
OUTPUT, tmp13MinustInput = 13 -INPUT
return
}

=> we create two columns for the two tmps, they can't have same name etc ... when we have lots of b/c u1 columns we end up with var b6 u1 ...

Actual "hand optimized":

pub fn useless(INST = 5, INPUT u128,) -> (OUTPUT u1){
    var tmp u128

   if INST==5      goto instGt5
   if INST==13    goto instLt13
fail

doNothing
tmp = 0 ;; useless constraint
OUTPUT = 0
return

instGt5:
OUTPUT, tmp = INPUT - 5
return

instGt5:
OUTPUT, tmp = 13 -INPUT
return
}

hand made :(

Improved:

pub fn useless(INST = 5, INPUT u128,) -> (OUTPUT u1){
   if INST==5      goto instGt5
   if INST==13    goto instLt13
fail


doNothing
OUTPUT = 0
return

instGt5:
 var loc tmp u128
OUTPUT, tmp = INPUT - 5
return

instGt5:
var loc tmp u128
OUTPUT, tmp = 13 -INPUT
return
}

=> we can create "loc variables" that could share the same name, can be put in same register, we don't have to declare shared tmp columns where a sub inst doesn't require it etc ...

[DavePearce]

You don't need special syntax like var loc tmp. Just var tmp is enough. have loc doesn't help because it doesn't give any information about the grouping. In general, this is comparable to what is called "register allocation" in a compiler. Specifically, you have a number of variables and a smaller number of columns, and you want to map the variables onto the columns in a way which ensure they don't interfere.

The starting point for the algorithm is to approximate the set of instructions over which a given variable is "live". Then, variables with disjoint live ranges can be allocated to the same underlying column, etc.