Transform a list of basic blocks containing variable references, into an equivalent list where each reference is associated with a register allocation. Artificial save and restore instructions may also be inserted into blocks to indicate spilling and reloading of variables.

In order to call this function, the caller must transform their own basic block representation into a linear series of BlockInfo structures. Each of these structures may be associated with a unique identifier, to assist with processing allocation info afterward.

If allocation is found to be impossible -- for example if there are simply not enough registers -- a Left value is returned, with a string describing the error.

From the point of view of this library, a basic block is nothing more than an ordered sequence of operations.

Every operation may reference multiple variables and/or specific physical registers. If a physical register is referenced, then that register is considered unavailable for allocation over the range of such references.

Certain operations have special significance as to how basic blocks are organized, and the lifetime of allocations. Thus, if an operation begins or ends a loop, or represents a method call, it should be indicated using the OpKind field. Indication of calls is necessary in order to save and restore all registers around a call, but indication of loops is optional, as it's merely avoids reloading of spilled variables inside loop bodies.

Each variable has associated allocation details, and a flag to indicate whether it must be loaded into a register at its point of use. Variables are also distinguished by their kind, which allows for restricting the scope of their lifetime. For example, output variables are not needed in a basic block until the first point of use, while the lifetime of input variables extends until their final use.