Module Fang_alloc

Register allocation.

This implementation both coalesces boxes to minimize unnecessary move instructions and also handles spilling so that there's no limit to the number of local variables in a Tiger program.

It's based on the "iterated register coallescing" algorithm [1].

References

[1] L. George and A. Appel, "Iterated register coalescing", ACM Transactions on Programming Languages and Systems, vol. 18, no. 3, pp. 300-324, 1996. Available: 10.1145/229542.229546.

module type SPILLING = sig ... end

Necessary information for handling spills (i.e., boxes that cannot be assigned a register).

module type ALLOC = sig ... end

Allocating processor registers to temporary boxes.

module Alloc : functor (R : sig ... end) -> functor (P : SPILLING) -> ALLOC with type spilling_handler = P.handler