- data DataflowLattice a = DataflowLattice {
- 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 = OldFact a
- newtype NewFact a = NewFact a
- data ChangeFlag
- = NoChange
- | SomeChange
- changeIf :: Bool -> ChangeFlag
- data FwdPass n f = FwdPass {
- 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 = 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 = BwdPass {
- 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 = 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
- withFuel :: Maybe a -> FuelMonad (Maybe a)
- getFuel :: FuelMonad Fuel
- setFuel :: Fuel -> FuelMonad ()
- freshLabel :: FuelMonad Label
- runWithFuel :: Fuel -> FuelMonad a -> a
- data O
- data C
- data Block n e x where
- data Body n where
- bodyMap :: Edges n => Body n -> LabelMap (Block n C C)
- data Graph n e x where
- data MaybeO ex t where
- class Edges thing where
- entryLabel :: thing C x -> Label
- successors :: thing e C -> [Label]
- addBlock :: Block n C C -> Body n -> Body n
- bodyList :: Edges n => Body n -> [(Label, Block n C C)]
- data 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
- 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
- mkEntry :: Block n O C -> AGraph n O C
- mkExit :: Block n C O -> AGraph n C O
- class Edges n => HooplNode n where
- mkBranchNode :: Label -> n O C
- mkLabelNode :: Label -> n C O
Documentation
data DataflowLattice a Source
DataflowLattice | |
|
type JoinFun a = OldFact a -> NewFact a -> (ChangeFlag, a)Source
changeIf :: Bool -> ChangeFlagSource
FwdPass | |
|
type FwdTransfer n f = forall e x. n e x -> Fact e f -> Fact x fSource
type FwdRewrite n f = forall e x. n e x -> Fact e f -> Maybe (FwdRes n f e x)Source
type SimpleFwdRewrite n f = forall e x. n e x -> Fact e f -> Maybe (AGraph n e x)Source
FwdRes (AGraph n e x) (FwdRewrite n f) |
noFwdRewrite :: FwdRewrite n fSource
thenFwdRw :: FwdRewrite n f -> FwdRewrite n f -> FwdRewrite n fSource
shallowFwdRw :: SimpleFwdRewrite n f -> FwdRewrite n fSource
deepFwdRw :: SimpleFwdRewrite n f -> FwdRewrite n fSource
iterFwdRw :: FwdRewrite n f -> FwdRewrite n fSource
BwdPass | |
|
type BwdTransfer n f = forall e x. n e x -> Fact x f -> Fact e fSource
type BwdRewrite n f = forall e x. n e x -> Fact x f -> Maybe (BwdRes n f e x)Source
type SimpleBwdRewrite n f = forall e x. n e x -> Fact x f -> Maybe (AGraph n e x)Source
BwdRes (AGraph n e x) (BwdRewrite n f) |
noBwdRewrite :: BwdRewrite n fSource
thenBwdRw :: BwdRewrite n f -> BwdRewrite n f -> BwdRewrite n fSource
shallowBwdRw :: SimpleBwdRewrite n f -> BwdRewrite n fSource
deepBwdRw :: SimpleBwdRewrite n f -> BwdRewrite n fSource
iterBwdRw :: BwdRewrite n f -> BwdRewrite n fSource
analyzeAndRewriteFwd :: forall n f. Edges n => FwdPass n f -> Body n -> FactBase f -> FuelMonad (Body n, FactBase f)Source
analyzeAndRewriteBwd :: forall n f. Edges n => BwdPass n f -> Body n -> FactBase f -> FuelMonad (Body n, FactBase f)Source
runWithFuel :: Fuel -> FuelMonad a -> aSource
entryLabel :: thing C x -> LabelSource
successors :: thing e C -> [Label]Source
mkFactBase :: [(Label, f)] -> FactBase fSource
lookupFact :: FactBase f -> Label -> Maybe fSource
extendFactBase :: FactBase f -> Label -> f -> FactBase fSource
delFromFactBase :: FactBase f -> [(Label, a)] -> FactBase fSource
unionFactBase :: FactBase f -> FactBase f -> FactBase fSource
elemFactBase :: Label -> FactBase f -> BoolSource
factBaseLabels :: FactBase f -> [Label]Source
factBaseList :: FactBase f -> [(Label, f)]Source
extendLabelSet :: LabelSet -> Label -> LabelSetSource
reduceLabelSet :: LabelSet -> Label -> LabelSetSource
mkLabelSet :: [Label] -> LabelSetSource
elemLabelSet :: Label -> LabelSet -> BoolSource
labelSetElems :: LabelSet -> [Label]Source
minusLabelSet :: LabelSet -> LabelSet -> LabelSetSource
unionLabelSet :: LabelSet -> LabelSet -> LabelSetSource
interLabelSet :: LabelSet -> LabelSet -> LabelSetSource
sizeLabelSet :: LabelSet -> IntSource
(<*>) :: AGraph n e O -> AGraph n O x -> AGraph n e xSource
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
oraddExitSeq
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/closedAGraph
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 aHooplNode
type-class constraint. (In GHC 6.12 this operator was calledoutOfLine
.) - The operator
unionBlocks
takes the union of two sets of basic blocks, each of which is represented as a closed/closedAGraph
. It is not redundant withaddBlocks
, becauseaddBlocks
requires aHooplNode
constraint butunionBlocks
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.
emptyAGraph :: AGraph n O OSource
emptyClosedAGraph :: AGraph n C CSource
withFreshLabels :: Labels l => (l -> AGraph n e x) -> AGraph n e xSource