Compiler.Hoopl

Documentation

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

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

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

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

data DataflowLattice a

Constructors

DataflowLattice

Fields

fact_name :: String

fact_bot :: a

fact_extend :: JoinFun a

fact_do_logging :: Bool

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

newtype OldFact a

Constructors

OldFact a

newtype NewFact a

Constructors

NewFact a

data ChangeFlag

Constructors

NoChange

SomeChange

Instances

Eq ChangeFlag

Ord ChangeFlag

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)

data FwdRes n f e x

Constructors

FwdRes (AGraph n e x) (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)

data BwdRes n f e x

Constructors

BwdRes (AGraph n e x) (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)

analyzeAndRewriteFwd' :: forall n f e x. Edges n => FwdPass n f -> Graph n e x -> Fact e f -> FuelMonad (Graph n e x, FactBase f, MaybeO x f)

if the graph being analyzed is open at the entry, there must be no other entry point, or all goes horribly wrong...

analyzeAndRewriteBwd' :: forall n f e x. Edges n => BwdPass n f -> Graph n e x -> Fact x f -> FuelMonad (Graph n e x, FactBase f, MaybeO e f)

if the graph being analyzed is open at the exit, I don't quite understand the implications of possible other exits

type TraceFn = forall a. String -> a -> a

debugFwdJoins :: forall n f. Show f => TraceFn -> ChangePred -> FwdPass n f -> FwdPass n f

Debugging combinators: Each combinator takes a dataflow pass and produces a dataflow pass that can output debugging messages. You provide the function, we call it with the applicable message.

The most common use case is probably to:

1. import Debug.Trace
2. pass trace as the 1st argument to the debug combinator
3. pass 'const true' as the 2nd argument to the debug combinator

debugBwdJoins :: forall n f. Show f => TraceFn -> ChangePred -> BwdPass n f -> BwdPass n 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

Edges n => LabelsPtr (n e 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)

type Body = Body' Block

data Body' block n where

Constructors

BodyEmpty :: Body' block n

BodyUnit :: block n C C -> Body' block n

BodyCat :: Body' block n -> Body' block n -> Body' block n

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

type Graph = Graph' Block

data Graph' block n e x where

Constructors

GNil :: Graph' block n O O

GUnit :: block n O O -> Graph' block n O O

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

data MaybeO ex t where

Constructors

JustO :: t -> MaybeO O t

NothingO :: MaybeO C t

Instances

Functor (MaybeO ex)

class Edges thing where

Methods

entryLabel :: thing C x -> Label

successors :: thing e C -> [Label]

Instances

Edges n => Edges (Block n)

Edges n => Edges (ZBlock n)

addBlock :: block n C C -> Body' block n -> Body' block n

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

data Label

Instances

Eq Label

Ord Label

Show Label

LabelsPtr 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)]

data LabelSet

Instances

LabelsPtr LabelSet

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

data AGraph n e x

graphOfAGraph :: 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.
• The operator |*><*| splices two graphs at a closed point. The vertical bar stands for closed point just as the angle brackets above stand for open point. Unlike the * operator, the |*><*| can create a control-flow graph with dangling outedges or unreachable blocks. The operator must be used carefully, so we have chosen a long name on purpose, to help call people's attention to what they're doing.
• We have discussed a dynamic assertion about dangling outedges and unreachable blocks, but nothing is implemented yet.

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.

(|*><*|) :: AGraph n e C -> AGraph n C x -> AGraph n e x

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

showGraph :: forall n e x. Edges n => Showing n -> Graph n e x -> String