-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Linear scan register allocator, formally verified in Coq
--   
@package linearscan
@version 0.2.0.0

module LinearScan

-- | 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 <a>Left</a> value is returned, with a
--   string describing the error.
allocate :: BlockInfo blk o a b -> OpInfo accType o v a b -> VarInfo v -> [blk a] -> accType -> Either String ([blk b], accType)

-- | From the point of view of this library, a basic block is nothing more
--   than an ordered sequence of operations.
data BlockInfo blk o a b
BlockInfo :: (blk a -> Int) -> (blk a -> [Int]) -> (blk a -> [o a]) -> (blk a -> [o b] -> blk b) -> BlockInfo blk o a b
blockId :: BlockInfo blk o a b -> blk a -> Int
blockSuccessors :: BlockInfo blk o a b -> blk a -> [Int]
blockOps :: BlockInfo blk o a b -> blk a -> [o a]
setBlockOps :: BlockInfo blk o a b -> blk a -> [o b] -> blk b

-- | 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 <a>OpKind</a> 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.
data OpInfo accType o v a b
OpInfo :: (o a -> OpKind) -> (o a -> ([v], [PhysReg])) -> (Int -> PhysReg -> accType -> (o b, accType)) -> (Int -> PhysReg -> accType -> (o b, accType)) -> (o a -> [(Int, PhysReg)] -> o b) -> OpInfo accType o v a b
opKind :: OpInfo accType o v a b -> o a -> OpKind
opRefs :: OpInfo accType o v a b -> o a -> ([v], [PhysReg])
saveOp :: OpInfo accType o v a b -> Int -> PhysReg -> accType -> (o b, accType)
restoreOp :: OpInfo accType o v a b -> Int -> PhysReg -> accType -> (o b, accType)
applyAllocs :: OpInfo accType o v a b -> o a -> [(Int, PhysReg)] -> o b
data OpKind
IsNormal :: OpKind
IsCall :: OpKind
IsBranch :: OpKind
IsLoopBegin :: OpKind
IsLoopEnd :: OpKind

-- | 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.
data VarInfo v
VarInfo :: (v -> Int) -> (v -> VarKind) -> (v -> Bool) -> VarInfo v
varId :: VarInfo v -> v -> Int
varKind :: VarInfo v -> v -> VarKind
regRequired :: VarInfo v -> v -> Bool
data VarKind
Input :: VarKind
Temp :: VarKind
Output :: VarKind
type PhysReg = Int
instance Show OpKind
instance Eq OpKind
instance Show VarKind
instance Eq VarKind