 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 = DataflowLattice {
 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 = 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)
 data FwdRes n f e x = FwdRes (AGraph n e x) (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)
 data BwdRes n f e x = 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)
 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)
 type TraceFn = forall a. String > a > a
 debugFwdJoins :: forall n f. Show f => TraceFn > ChangePred > FwdPass n f > FwdPass n f
 debugBwdJoins :: forall n f. Show f => TraceFn > ChangePred > BwdPass n f > BwdPass n 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
 type Body = Body' Block
 data Body' block n where
 bodyMap :: Edges (block n) => Body' block n > LabelMap (block n C C)
 type Graph = Graph' Block
 data Graph' block 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' block n > Body' block n
 bodyList :: Edges (block n) => Body' block 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)]
 data 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
 (*><*) :: 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
 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
 showGraph :: forall n e x. Edges n => Showing n > Graph n e x > String
Documentation
type SimpleFwdRewrite n f = forall e x. n e x > Fact e f > Maybe (AGraph n e x)Source
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
type SimpleBwdRewrite n f = forall e x. n e x > Fact x f > Maybe (AGraph n e x)Source
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
data DataflowLattice a Source
DataflowLattice  

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
FwdRes (AGraph n e x) (FwdRewrite n f) 
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
BwdRes (AGraph n e x) (BwdRewrite n f) 
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
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)Source
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)Source
if the graph being analyzed is open at the exit, I don't quite understand the implications of possible other exits
debugFwdJoins :: forall n f. Show f => TraceFn > ChangePred > FwdPass n f > FwdPass n fSource
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:
 import
Debug.Trace
 pass
trace
as the 1st argument to the debug combinator  pass 'const true' as the 2nd argument to the debug combinator
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
graphOfAGraph :: AGraph n e x > FuelMonad (Graph n e x)Source
(<*>) :: 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
typeclass 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.  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 controlflow 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.
emptyAGraph :: AGraph n O OSource
emptyClosedAGraph :: AGraph n C CSource
withFreshLabels :: Labels l => (l > AGraph n e x) > AGraph n e xSource
class IfThenElseable x whereSource