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


-- | Linear scan register allocator, formally verified in Coq
--   
@package linearscan
@version 0.5.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 :: (Functor m, Applicative m, Monad m) => Int -> BlockInfo m blk1 blk2 op1 op2 -> OpInfo m op1 op2 -> [blk1] -> m (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 m blk1 blk2 op1 op2
BlockInfo :: (blk1 -> m Int) -> (blk1 -> m [Int]) -> (blk1 -> blk1 -> m (blk1, blk1)) -> (blk1 -> ([op1], [op1], [op1])) -> (blk1 -> [op2] -> [op2] -> [op2] -> blk2) -> BlockInfo m blk1 blk2 op1 op2
blockId :: BlockInfo m blk1 blk2 op1 op2 -> blk1 -> m Int
blockSuccessors :: BlockInfo m blk1 blk2 op1 op2 -> blk1 -> m [Int]
splitCriticalEdge :: BlockInfo m blk1 blk2 op1 op2 -> blk1 -> blk1 -> m (blk1, blk1)
blockOps :: BlockInfo m blk1 blk2 op1 op2 -> blk1 -> ([op1], [op1], [op1])
setBlockOps :: BlockInfo m 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 m op1 op2
OpInfo :: (op1 -> OpKind) -> (op1 -> [VarInfo]) -> (PhysReg -> PhysReg -> m [op2]) -> (PhysReg -> PhysReg -> m [op2]) -> (PhysReg -> Maybe Int -> m [op2]) -> (Maybe Int -> PhysReg -> m [op2]) -> (op1 -> [(Int, PhysReg)] -> m [op2]) -> (op1 -> String) -> OpInfo m op1 op2
opKind :: OpInfo m op1 op2 -> op1 -> OpKind
opRefs :: OpInfo m op1 op2 -> op1 -> [VarInfo]
moveOp :: OpInfo m op1 op2 -> PhysReg -> PhysReg -> m [op2]
swapOp :: OpInfo m op1 op2 -> PhysReg -> PhysReg -> m [op2]
saveOp :: OpInfo m op1 op2 -> PhysReg -> Maybe Int -> m [op2]
restoreOp :: OpInfo m op1 op2 -> Maybe Int -> PhysReg -> m [op2]
applyAllocs :: OpInfo m op1 op2 -> op1 -> [(Int, PhysReg)] -> m [op2]
showOp1 :: OpInfo m op1 op2 -> op1 -> String
data OpKind
IsNormal :: OpKind
IsCall :: OpKind
IsBranch :: 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 BlockLiveSets
instance Show FinalStage
instance Show SSError
instance Show SplitPosition
instance Show SpillDetails
instance Show SplitReason
instance Show UsePos
instance Show RangeDesc
instance Show IntervalDesc
instance Show OpKind
instance Eq OpKind
instance Show VarKind
instance Eq VarKind
instance Show LoopState
instance Show ScanStateDesc