| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
LinearScan
- allocate :: Int -> BlockInfo blk1 blk2 op1 op2 -> OpInfo accType op1 op2 -> [blk1] -> State accType (Either String [blk2])
- data BlockInfo blk1 blk2 op1 op2 = BlockInfo {
- blockId :: blk1 -> Int
- blockSuccessors :: blk1 -> [Int]
- blockOps :: blk1 -> ([op1], [op1], [op1])
- setBlockOps :: blk1 -> [op2] -> [op2] -> [op2] -> blk2
- data OpInfo accType op1 op2 = OpInfo {
- opKind :: op1 -> OpKind
- opRefs :: op1 -> [VarInfo]
- moveOp :: PhysReg -> PhysReg -> State accType [op2]
- swapOp :: PhysReg -> PhysReg -> State accType [op2]
- saveOp :: PhysReg -> Maybe Int -> State accType [op2]
- restoreOp :: Maybe Int -> PhysReg -> State accType [op2]
- applyAllocs :: op1 -> [(Int, PhysReg)] -> [op2]
- data OpKind
- type VarId = Int
- data VarInfo = VarInfo {}
- data VarKind
- type PhysReg = Int
Main entry point
Arguments
| :: Int | Maximum number of registers to use |
| -> BlockInfo blk1 blk2 op1 op2 | |
| -> OpInfo accType op1 op2 | |
| -> [blk1] | |
| -> State accType (Either String [blk2]) |
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 provide records that allow viewing and mutating of the original program graph.
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
data BlockInfo blk1 blk2 op1 op2 Source
From the point of view of this library, a basic block is nothing more than an ordered sequence of operations.
Constructors
| BlockInfo | |
Fields
| |
Operations
data OpInfo accType op1 op2 Source
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.
Constructors
| OpInfo | |
Fields
| |
Constructors
| IsNormal | |
| IsCall | |
| IsBranch | |
| IsLoopBegin | |
| IsLoopEnd |
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.