Safe Haskell | None |
---|---|
Language | Haskell2010 |
- allocate :: [BlockInfo] -> Either String [BlockInfo]
- data BlockInfo = BlockInfo {}
- defaultBlockInfo :: BlockInfo
- data OpInfo = OpInfo {}
- data OpKind
- defaultOpInfo :: OpInfo
- data VarInfo = VarInfo {
- varId :: Int
- varKind :: VarKind
- varAlloc :: Allocation
- regRequired :: Bool
- data VarKind
- data Allocation
- type PhysReg = Int
- defaultVarInfo :: VarInfo
Main entry point
allocate :: [BlockInfo] -> Either String [BlockInfo] Source
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.
Blocks
From the point of view of this library, a basic block is nothing more than an ordered sequence of operations.
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.
Variables
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.
VarInfo | |
|