Safe Haskell	None
Language	GHC2021

Language.QBE.Simulator.State

Contents

Abstract Monad
Name Resolution
Helper
Stack

Description

This module defines the abstract Simulator monad and thus provides the primitives used by Language.QBE.Simulator to describe the semantics of the QBE intermediate representation.

Synopsis

class (ValueRepr v, MonadError EvalError m) => Simulator (m :: Type -> Type) v | m -> v where
- isTrue :: v -> m Bool
- toAddress :: v -> m Address
- lookupSymbol :: GlobalIdent -> m (Maybe Address)
- findFunc :: GlobalIdent -> m (Maybe (SomeFunc m v))
- findFuncByAddr :: Address -> m (Maybe (SomeFunc m v))
- activeFrame :: m (StackFrame v)
- pushStackFrame :: StackFrame v -> m ()
- popStackFrame :: m (StackFrame v)
- getSP :: m v
- setSP :: v -> m ()
- writeMemory :: Address -> ExtType -> v -> m ()
- readMemory :: LoadType -> Address -> m v
data SomeFunc (m :: Type -> Type) v
- = SSimFunc ([v] -> m (Maybe v))
- | SFuncDef FuncDef
lookupFunc :: Simulator m v => Value -> m (SomeFunc m v)
lookupArgs :: Simulator m v => [FuncArg] -> m [v]
lookupGlobal :: Simulator m v => BaseType -> GlobalIdent -> m v
lookupLocal :: StackFrame v -> LocalIdent -> Maybe v
lookupValue :: Simulator m v => BaseType -> Value -> m v
liftMaybe :: MonadError EvalError m => EvalError -> Maybe a -> m a
subType :: Simulator m v => BaseType -> v -> m v
runBinary :: Simulator m v => BaseType -> (v -> v -> Maybe v) -> v -> v -> m v
returnFromFunc :: Simulator m v => m ()
readNullArray :: Simulator m v => Address -> m [v]
data StackFrame v = StackFrame {
- stkFunc :: FuncDef
- stkVars :: Map LocalIdent v
- stkVarArgs :: [v]
- stkFp :: v
}
newStackFrame :: Simulator m v => FuncDef -> Map LocalIdent v -> [v] -> m (StackFrame v)
storeLocal :: LocalIdent -> v -> StackFrame v -> StackFrame v
modifyFrame :: Simulator m v => (StackFrame v -> StackFrame v) -> m ()
stackAlign :: ValueRepr v => v -> v -> Maybe v
stackAlloc :: Simulator m v => v -> Word64 -> m v
stackSpill :: Simulator m v => v -> m Address

Abstract Monad

class (ValueRepr v, MonadError EvalError m) => Simulator (m :: Type -> Type) v | m -> v where Source #

This is an “abstract monad” representing the Simulator and allowing interaction with an encapsulated Simulator state m. Conceptually, this monads describes the primitives based on which the semantics of the QBE intermediate representation are abstractly described in Simulator.

An instance of this monad then provides concrete semantics for these primitives. For example, the module Language.QBE.Simulator.Default.State provides an implementation of a polymorphic Simulator state implement over a Control.Monad.State monad.

The idea is inspired by Bourgeat et al. https://doi.org/10.1145/3607833.

Methods

isTrue :: v -> m Bool Source #

Check if a value of type ValueRepr evaluates to true. This is used within Language.QBE.Simulator to implement conditional jumps.

toAddress :: v -> m Address Source #

Convert a value of type ValueRepr to a Address that can be used to index a Language.QBE.Simulator.Memory.

lookupSymbol :: GlobalIdent -> m (Maybe Address) Source #

Lookup the address of a data symbol.

findFunc :: GlobalIdent -> m (Maybe (SomeFunc m v)) Source #

Find a function by name, required to implement call instructions.

findFuncByAddr :: Address -> m (Maybe (SomeFunc m v)) Source #

Find a function by "text segment" address, used for the implementation of function pointers.

activeFrame :: m (StackFrame v) Source #

Return the StackFrame of the currently executed function.

pushStackFrame :: StackFrame v -> m () Source #

Push a new StackFrame onto the function call stack.

popStackFrame :: m (StackFrame v) Source #

Pop the current stack frame from the function call stack. Should throw EmptyStack when invoked on an empty function call stack.

getSP :: m v Source #

Get the current value of the stack pointer.

setSP :: v -> m () Source #

Set the value of the stack pointer.

writeMemory :: Address -> ExtType -> v -> m () Source #

Write a value to memory.

readMemory :: LoadType -> Address -> m v Source #

Read a value from memory.

Instances

Instances details

(Storable v b, ValueRepr v, NFData b) => Simulator (SimState v b) v Source #

Instance details

Defined in Language.QBE.Simulator.Default.State

Methods

isTrue :: v -> SimState v b Bool Source #

toAddress :: v -> SimState v b Address Source #

lookupSymbol :: GlobalIdent -> SimState v b (Maybe Address) Source #

findFunc :: GlobalIdent -> SimState v b (Maybe (SomeFunc (SimState v b) v)) Source #

findFuncByAddr :: Address -> SimState v b (Maybe (SomeFunc (SimState v b) v)) Source #

activeFrame :: SimState v b (StackFrame v) Source #

pushStackFrame :: StackFrame v -> SimState v b () Source #

popStackFrame :: SimState v b (StackFrame v) Source #

getSP :: SimState v b v Source #

setSP :: v -> SimState v b () Source #

writeMemory :: Address -> ExtType -> v -> SimState v b () Source #

readMemory :: LoadType -> Address -> SimState v b v Source #

Name Resolution

data SomeFunc (m :: Type -> Type) v Source #

Representation of a function.

Constructors

SSimFunc ([v] -> m (Maybe v))	A simulated function whose execution is intercepted by the Simulator.
SFuncDef FuncDef	A QBE function defined in the input program.

lookupFunc :: Simulator m v => Value -> m (SomeFunc m v) Source #

Interpret the given Value as a function reference, either looking it up by name or by address. If the function could not be found by address an UnknownFunctionAddr is thrown, otherwise an UnknownFunction error is thrown.

lookupArgs :: Simulator m v => [FuncArg] -> m [v] Source #

Lookup the arguments to a function.

lookupGlobal :: Simulator m v => BaseType -> GlobalIdent -> m v Source #

Lookup a global variable, might throw an UnknownVariable error.

lookupLocal :: StackFrame v -> LocalIdent -> Maybe v Source #

Lookup a local variable in the current StackFrame.

lookupValue :: Simulator m v => BaseType -> Value -> m v Source #

Lookup a Value, invoking the correct lookup function. For example, lookupGlobal for globals or lookupLocal for local variables.

Helper

liftMaybe :: MonadError EvalError m => EvalError -> Maybe a -> m a Source #

Extracts the element out of a Just or throw the given EvalError if if its argument is Nothing.

subType :: Simulator m v => BaseType -> v -> m v Source #

Implements the subtyping rules of the QBE intermediate representation.

See https://c9x.me/compile/doc/il-v1.2.html#Subtyping.

runBinary :: Simulator m v => BaseType -> (v -> v -> Maybe v) -> v -> v -> m v Source #

Invoke a binary operation and perform subtyping (see subType) on its results for the provided BaseType. If the operation returns a Nothing value a TypingError is raised.

returnFromFunc :: Simulator m v => m () Source #

Trigger a function return, popping its StackFrame from the call stack and updating both the stack and frame pointer.

readNullArray :: Simulator m v => Address -> m [v] Source #

Read a null-terminated C string from memory at the given Address. The return value is a list of 8-bit values.

Stack

data StackFrame v Source #

Representation of a stack frame on the function call stack.

Constructors

StackFrame
Fields stkFunc :: FuncDef stkVars :: Map LocalIdent v stkVarArgs :: [v] stkFp :: v

newStackFrame Source #

Arguments

:: Simulator m v
=> FuncDef	Definition of the functions to which this frame belongs.
-> Map LocalIdent v	Named arguments passed to this function.
-> [v]	Optional, unnamed variadic arguments.
-> m (StackFrame v)

Create a new StackFrame and push it onto the call stack.

storeLocal :: LocalIdent -> v -> StackFrame v -> StackFrame v Source #

Store a local variable with a given name and value in the given StackFrame.

modifyFrame :: Simulator m v => (StackFrame v -> StackFrame v) -> m () Source #

Modify the current StackFrame, e.g. to add a new local variable to it. If the function call stack is currently empty an EmptyStack error is thrown.

stackAlign :: ValueRepr v => v -> v -> Maybe v Source #

Align a stack address. Contrary to alignAddr, this rounds down to the nearest aligned addressed (not up) as the stack grows downward. Further, since the SP representation is presently not fixed, it operates on ValueRepr.

stackAlloc :: Simulator m v => v -> Word64 -> m v Source #

Allocate a given amount of bytes on the stack with the given alignment. Advances the stack pointer accordingly.

stackSpill :: Simulator m v => v -> m Address Source #

Allocate space for the given value on the stack and store it there. Returns a reference (i.e., a memory address) fore the allocated memory.