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


-- | Linear scan register allocator, formally verified in Coq
--   
@package linearscan
@version 0.3.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 :: Int -> BlockInfo blk1 blk2 op1 op2 -> OpInfo accType op1 op2 -> [blk1] -> State accType (Either String [blk2])

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

-- | 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 op1 op2
OpInfo :: (op1 -> OpKind) -> (op1 -> [VarInfo]) -> (PhysReg -> PhysReg -> State accType [op2]) -> (PhysReg -> PhysReg -> State accType [op2]) -> (PhysReg -> Maybe Int -> State accType [op2]) -> (Maybe Int -> PhysReg -> State accType [op2]) -> (op1 -> [(Int, PhysReg)] -> [op2]) -> OpInfo accType op1 op2
opKind :: OpInfo accType op1 op2 -> op1 -> OpKind
opRefs :: OpInfo accType op1 op2 -> op1 -> [VarInfo]
moveOp :: OpInfo accType op1 op2 -> PhysReg -> PhysReg -> State accType [op2]
swapOp :: OpInfo accType op1 op2 -> PhysReg -> PhysReg -> State accType [op2]
saveOp :: OpInfo accType op1 op2 -> PhysReg -> Maybe Int -> State accType [op2]
restoreOp :: OpInfo accType op1 op2 -> Maybe Int -> PhysReg -> State accType [op2]
applyAllocs :: OpInfo accType op1 op2 -> op1 -> [(Int, PhysReg)] -> [op2]
data OpKind
IsNormal :: OpKind
IsCall :: OpKind
IsBranch :: OpKind
IsLoopBegin :: OpKind
IsLoopEnd :: OpKind
type VarId = Int

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