Compiler.Hoopl

Documentation

data DataflowLattice a

Constructors

DataflowLattice

Fields

fact_name :: String

fact_bot :: a

fact_extend :: JoinFun a

fact_do_logging :: Bool

type JoinFun a = OldFact a -> NewFact a -> (ChangeFlag, a)

newtype OldFact a

Constructors

OldFact a

newtype NewFact a

Constructors

NewFact a

data ChangeFlag

Constructors

NoChange

SomeChange

changeIf :: Bool -> ChangeFlag

data FwdPass n f

Constructors

FwdPass

Fields

fp_lattice :: DataflowLattice f

fp_transfer :: FwdTransfer n f

fp_rewrite :: FwdRewrite n f

type FwdTransfer n f = forall e x. n e x -> Fact e f -> Fact x f

type FwdRewrite n f = forall e x. n e x -> Fact e f -> Maybe (FwdRes n f e x)

type SimpleFwdRewrite n f = forall e x. n e x -> Fact e f -> Maybe (AGraph n e x)

data FwdRes n f e x

Constructors

FwdRes (AGraph n e x) (FwdRewrite n f)

noFwdRewrite :: FwdRewrite n f

thenFwdRw :: FwdRewrite n f -> FwdRewrite n f -> FwdRewrite n f

shallowFwdRw :: SimpleFwdRewrite n f -> FwdRewrite n f

deepFwdRw :: SimpleFwdRewrite n f -> FwdRewrite n f

iterFwdRw :: FwdRewrite n f -> FwdRewrite n f

data BwdPass n f

Constructors

BwdPass

Fields

bp_lattice :: DataflowLattice f

bp_transfer :: BwdTransfer n f

bp_rewrite :: BwdRewrite n f

type BwdTransfer n f = forall e x. n e x -> Fact x f -> Fact e f

type BwdRewrite n f = forall e x. n e x -> Fact x f -> Maybe (BwdRes n f e x)

type SimpleBwdRewrite n f = forall e x. n e x -> Fact x f -> Maybe (AGraph n e x)

data BwdRes n f e x

Constructors

BwdRes (AGraph n e x) (BwdRewrite n f)

noBwdRewrite :: BwdRewrite n f

thenBwdRw :: BwdRewrite n f -> BwdRewrite n f -> BwdRewrite n f

shallowBwdRw :: SimpleBwdRewrite n f -> BwdRewrite n f

deepBwdRw :: SimpleBwdRewrite n f -> BwdRewrite n f

iterBwdRw :: BwdRewrite n f -> BwdRewrite n f

type family Fact x f :: *

analyzeAndRewriteFwd :: forall n f. Edges n => FwdPass n f -> Body n -> FactBase f -> FuelMonad (Body n, FactBase f)

analyzeAndRewriteBwd :: forall n f. Edges n => BwdPass n f -> Body n -> FactBase f -> FuelMonad (Body n, FactBase f)

type Fuel = Int

data FuelMonad a

Instances

Monad FuelMonad

withFuel :: Maybe a -> FuelMonad (Maybe a)

getFuel :: FuelMonad Fuel

setFuel :: Fuel -> FuelMonad ()

freshLabel :: FuelMonad Label

runWithFuel :: Fuel -> FuelMonad a -> a

data O

Instances

IfThenElseable O

data C

Instances

IfThenElseable C

data Block n e x where

Constructors

BUnit :: n e x -> Block n e x

BCat :: Block n e O -> Block n O x -> Block n e x

Instances

Edges n => Edges (Block n)

data Body n where

Constructors

BodyEmpty :: Body n

BodyUnit :: Block n C C -> Body n

BodyCat :: Body n -> Body n -> Body n

bodyMap :: Edges n => Body n -> LabelMap (Block n C C)

data Graph n e x where

Constructors

GNil :: Graph n O O

GUnit :: Block n O O -> Graph n O O

GMany :: MaybeO e (Block n O C) -> Body n -> MaybeO x (Block n C O) -> Graph n e x

data MaybeO ex t where

Constructors

JustO :: t -> MaybeO O t

NothingO :: MaybeO C t

class Edges thing where

Methods

entryLabel :: thing C x -> Label

successors :: thing e C -> [Label]

Instances

Edges n => Edges (Block n)

addBlock :: Block n C C -> Body n -> Body n

bodyList :: Edges n => Body n -> [(Label, Block n C C)]

data Label

Instances

Eq Label

Ord Label

Show Label

Labels Label

allLabels :: [Label]

type LabelMap a = IntMap a

type FactBase a = IntMap a

noFacts :: FactBase f

mkFactBase :: [(Label, f)] -> FactBase f

unitFact :: Label -> FactBase f -> FactBase f

lookupFact :: FactBase f -> Label -> Maybe f

extendFactBase :: FactBase f -> Label -> f -> FactBase f

delFromFactBase :: FactBase f -> [(Label, a)] -> FactBase f

unionFactBase :: FactBase f -> FactBase f -> FactBase f

elemFactBase :: Label -> FactBase f -> Bool

factBaseLabels :: FactBase f -> [Label]

factBaseList :: FactBase f -> [(Label, f)]

type LabelSet = IntSet

emptyLabelSet :: LabelSet

extendLabelSet :: LabelSet -> Label -> LabelSet

reduceLabelSet :: LabelSet -> Label -> LabelSet

mkLabelSet :: [Label] -> LabelSet

elemLabelSet :: Label -> LabelSet -> Bool

labelSetElems :: LabelSet -> [Label]

minusLabelSet :: LabelSet -> LabelSet -> LabelSet

unionLabelSet :: LabelSet -> LabelSet -> LabelSet

interLabelSet :: LabelSet -> LabelSet -> LabelSet

sizeLabelSet :: LabelSet -> Int

type AGraph n e x = FuelMonad (Graph n e x)

(<*>) :: AGraph n e O -> AGraph n O x -> AGraph n e x

As noted in the paper, we can define a single, polymorphic type of splicing operation with the very polymorphic type AGraph n e a -> AGraph n a x -> AGraph n e x However, we feel that this operation is a bit too polymorphic, and that it's too easy for clients to use it blindly without thinking. We therfore split it into several operations:

• The <*> operator is true concatenation, for connecting open graphs.
• The operators addEntrySeq or addExitSeq allow a client to add an entry or exit sequence to a graph that is closed at the entry or exit.
• The operator addBlocks adds a set of basic blocks (represented as a closed/closed AGraph to an existing graph, without changing the shape of the existing graph. In some cases, it's necessary to introduce a branch and a label to 'get around' the blocks added, so this operator, and other functions based on it, requires a HooplNode type-class constraint. (In GHC 6.12 this operator was called outOfLine.)
• The operator unionBlocks takes the union of two sets of basic blocks, each of which is represented as a closed/closed AGraph. It is not redundant with addBlocks, because addBlocks requires a HooplNode constraint but unionBlocks does not.

There is some redundancy in this representation (any instance of addEntrySeq is also an instance of either addExitSeq or addBlocks), but because the different operators restrict polymorphism in different ways, we felt some redundancy would be appropriate.

catAGraphs :: [AGraph n O O] -> AGraph n O O

addEntrySeq :: AGraph n O C -> AGraph n C x -> AGraph n O x

addExitSeq :: AGraph n e C -> AGraph n C O -> AGraph n e O

addBlocks :: HooplNode n => AGraph n e x -> AGraph n C C -> AGraph n e x

unionBlocks :: AGraph n C C -> AGraph n C C -> AGraph n C C

emptyAGraph :: AGraph n O O

emptyClosedAGraph :: AGraph n C C

withFreshLabels :: Labels l => (l -> AGraph n e x) -> AGraph n e x

mkFirst :: n C O -> AGraph n C O

mkMiddle :: n O O -> AGraph n O O

mkMiddles :: [n O O] -> AGraph n O O

mkLast :: n O C -> AGraph n O C

mkBranch :: HooplNode n => Label -> AGraph n O C

mkLabel :: HooplNode n => Label -> AGraph n C O

mkWhileDo :: HooplNode n => (Label -> Label -> AGraph n O C) -> AGraph n O O -> AGraph n O O

class IfThenElseable x where

Methods

mkIfThenElse :: HooplNode n => (Label -> Label -> AGraph n O C) -> AGraph n O x -> AGraph n O x -> AGraph n O x

Instances

IfThenElseable C

IfThenElseable O

mkEntry :: Block n O C -> AGraph n O C

mkExit :: Block n C O -> AGraph n C O

class Edges n => HooplNode n where

Methods

mkBranchNode :: Label -> n O C

mkLabelNode :: Label -> n C O