Safe Haskell  Safe 

 type Body n = LabelMap (Block n C C)
 type Body' block n = LabelMap (block n C C)
 emptyBody :: Body' block n
 bodyList :: NonLocal (block n) => Body' block n > [(Label, block n C C)]
 addBlock :: NonLocal thing => thing C C > LabelMap (thing C C) > LabelMap (thing C C)
 bodyUnion :: forall a. LabelMap a > LabelMap a > LabelMap a
 type Graph = Graph' Block
 data Graph' block n e x where
 class NonLocal thing where
 entryLabel :: thing C x > Label
 successors :: thing e C > [Label]
 bodyGraph :: Body n > Graph n C C
 blockGraph :: NonLocal n => Block n e x > Graph n e x
 gUnitOO :: block n O O > Graph' block n O O
 gUnitOC :: block n O C > Graph' block n O C
 gUnitCO :: block n C O > Graph' block n C O
 gUnitCC :: NonLocal (block n) => block n C C > Graph' block n C C
 catGraphNodeOC :: NonLocal n => Graph n e O > n O C > Graph n e C
 catGraphNodeOO :: Graph n e O > n O O > Graph n e O
 catNodeCOGraph :: NonLocal n => n C O > Graph n O x > Graph n C x
 catNodeOOGraph :: n O O > Graph n O x > Graph n O x
 splice :: forall block n e a x. NonLocal (block n) => (forall e x. block n e O > block n O x > block n e x) > Graph' block n e a > Graph' block n a x > Graph' block n e x
 gSplice :: NonLocal n => Graph n e a > Graph n a x > Graph n e x
 mapGraph :: (forall e x. n e x > n' e x) > Graph n e x > Graph n' e x
 mapGraphBlocks :: forall block n block' n' e x. (forall e x. block n e x > block' n' e x) > Graph' block n e x > Graph' block' n' e x
 foldGraphNodes :: forall n a. (forall e x. n e x > a > a) > forall e x. Graph n e x > a > a
 labelsDefined :: forall block n e x. NonLocal (block n) => Graph' block n e x > LabelSet
 labelsUsed :: forall block n e x. NonLocal (block n) => Graph' block n e x > LabelSet
 externalEntryLabels :: forall n. NonLocal n => LabelMap (Block n C C) > LabelSet
 postorder_dfs :: NonLocal (block n) => Graph' block n O x > [block n C C]
 postorder_dfs_from :: (NonLocal block, LabelsPtr b) => LabelMap (block C C) > b > [block C C]
 postorder_dfs_from_except :: forall block e. (NonLocal block, LabelsPtr e) => LabelMap (block C C) > e > LabelSet > [block C C]
 preorder_dfs :: NonLocal (block n) => Graph' block n O x > [block n C C]
 preorder_dfs_from_except :: forall block e. (NonLocal block, LabelsPtr e) => LabelMap (block C C) > e > LabelSet > [block C C]
 class LabelsPtr l where
 targetLabels :: l > [Label]
 data O
 data C
 data MaybeO ex t where
 data MaybeC ex t where
 type family IndexedCO ex a b :: *
 data Shape ex where
 data Block n e x where
 BlockCO :: n C O > Block n O O > Block n C O
 BlockCC :: n C O > Block n O O > n O C > Block n C C
 BlockOC :: Block n O O > n O C > Block n O C
 BNil :: Block n O O
 BMiddle :: n O O > Block n O O
 BCat :: Block n O O > Block n O O > Block n O O
 BSnoc :: Block n O O > n O O > Block n O O
 BCons :: n O O > Block n O O > Block n O O
 isEmptyBlock :: Block n e x > Bool
 emptyBlock :: Block n O O
 blockCons :: n O O > Block n O x > Block n O x
 blockSnoc :: Block n e O > n O O > Block n e O
 blockJoinHead :: n C O > Block n O x > Block n C x
 blockJoinTail :: Block n e O > n O C > Block n e C
 blockJoin :: n C O > Block n O O > n O C > Block n C C
 blockJoinAny :: (MaybeC e (n C O), Block n O O, MaybeC x (n O C)) > Block n e x
 blockAppend :: Block n e O > Block n O x > Block n e x
 firstNode :: Block n C x > n C O
 lastNode :: Block n x C > n O C
 endNodes :: Block n C C > (n C O, n O C)
 blockSplitHead :: Block n C x > (n C O, Block n O x)
 blockSplitTail :: Block n e C > (Block n e O, n O C)
 blockSplit :: Block n C C > (n C O, Block n O O, n O C)
 blockSplitAny :: Block n e x > (MaybeC e (n C O), Block n O O, MaybeC x (n O C))
 replaceFirstNode :: Block n C x > n C O > Block n C x
 replaceLastNode :: Block n x C > n O C > Block n x C
 blockToList :: Block n O O > [n O O]
 blockFromList :: [n O O] > Block n O O
 mapBlock :: (forall e x. n e x > n' e x) > Block n e x > Block n' e x
 mapBlock' :: (forall e x. n e x > n' e x) > Block n e x > Block n' e x
 mapBlock3' :: forall n n' e x. (n C O > n' C O, n O O > n' O O, n O C > n' O C) > Block n e x > Block n' e x
 foldBlockNodesF :: forall n a. (forall e x. n e x > a > a) > forall e x. Block n e x > IndexedCO e a a > IndexedCO x a a
 foldBlockNodesF3 :: forall n a b c. (n C O > a > b, n O O > b > b, n O C > b > c) > forall e x. Block n e x > IndexedCO e a b > IndexedCO x c b
 foldBlockNodesB :: forall n a. (forall e x. n e x > a > a) > forall e x. Block n e x > IndexedCO x a a > IndexedCO e a a
 foldBlockNodesB3 :: forall n a b c. (n C O > b > c, n O O > b > b, n O C > a > b) > forall e x. Block n e x > IndexedCO x a b > IndexedCO e c b
 frontBiasBlock :: Block n e x > Block n e x
 backBiasBlock :: Block n e x > Block n e x
 data AGraph n e x
 graphOfAGraph :: AGraph n e x > forall m. UniqueMonad m => m (Graph n e x)
 aGraphOfGraph :: Graph n e x > AGraph n e x
 (<*>) :: (GraphRep g, NonLocal n) => g n e O > g n O x > g n e x
 (*><*) :: (GraphRep g, NonLocal n) => g n e C > g n C x > g n e x
 catGraphs :: (GraphRep g, NonLocal n) => [g n O O] > g n O O
 addEntrySeq :: NonLocal n => AGraph n O C > AGraph n C x > AGraph n O x
 addExitSeq :: NonLocal n => 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 :: NonLocal n => AGraph n C C > AGraph n C C > AGraph n C C
 emptyGraph :: GraphRep g => g n O O
 emptyClosedGraph :: GraphRep g => g n C C
 withFresh :: Uniques u => (u > AGraph n e x) > AGraph n e x
 mkFirst :: GraphRep g => n C O > g n C O
 mkMiddle :: GraphRep g => n O O > g n O O
 mkMiddles :: (GraphRep g, NonLocal n) => [n O O] > g n O O
 mkLast :: GraphRep g => n O C > g n O C
 mkBranch :: (GraphRep g, HooplNode n) => Label > g n O C
 mkLabel :: (GraphRep g, HooplNode n) => Label > g 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 :: GraphRep g => Block n O C > g n O C
 mkExit :: GraphRep g => Block n C O > g n C O
 class NonLocal n => HooplNode n where
 mkBranchNode :: Label > n O C
 mkLabelNode :: Label > n C O
 firstXfer :: NonLocal n => (n C O > f > f) > n C O > FactBase f > f
 distributeXfer :: NonLocal n => DataflowLattice f > (n O C > f > f) > n O C > f > FactBase f
 distributeFact :: NonLocal n => n O C > f > FactBase f
 distributeFactBwd :: NonLocal n => n C O > f > FactBase f
 successorFacts :: NonLocal n => n O C > FactBase f > [f]
 joinFacts :: DataflowLattice f > Label > [f] > f
 joinOutFacts :: NonLocal node => DataflowLattice f > node O C > FactBase f > f
 joinMaps :: Ord k => JoinFun v > JoinFun (Map k v)
 analyzeAndRewriteFwdBody :: forall m n f entries. (CheckpointMonad m, NonLocal n, LabelsPtr entries) => FwdPass m n f > entries > Body n > FactBase f > m (Body n, FactBase f)
 analyzeAndRewriteBwdBody :: forall m n f entries. (CheckpointMonad m, NonLocal n, LabelsPtr entries) => BwdPass m n f > entries > Body n > FactBase f > m (Body n, FactBase f)
 analyzeAndRewriteFwdOx :: forall m n f x. (CheckpointMonad m, NonLocal n) => FwdPass m n f > Graph n O x > f > m (Graph n O x, FactBase f, MaybeO x f)
 analyzeAndRewriteBwdOx :: forall m n f x. (CheckpointMonad m, NonLocal n) => BwdPass m n f > Graph n O x > Fact x f > m (Graph n O x, FactBase f, f)
 class IsSet set where
 type ElemOf set
 setNull :: set > Bool
 setSize :: set > Int
 setMember :: ElemOf set > set > Bool
 setEmpty :: set
 setSingleton :: ElemOf set > set
 setInsert :: ElemOf set > set > set
 setDelete :: ElemOf set > set > set
 setUnion :: set > set > set
 setDifference :: set > set > set
 setIntersection :: set > set > set
 setIsSubsetOf :: set > set > Bool
 setFold :: (ElemOf set > b > b) > b > set > b
 setElems :: set > [ElemOf set]
 setFromList :: [ElemOf set] > set
 setInsertList :: IsSet set => [ElemOf set] > set > set
 setDeleteList :: IsSet set => [ElemOf set] > set > set
 setUnions :: IsSet set => [set] > set
 class IsMap map where
 type KeyOf map
 mapNull :: map a > Bool
 mapSize :: map a > Int
 mapMember :: KeyOf map > map a > Bool
 mapLookup :: KeyOf map > map a > Maybe a
 mapFindWithDefault :: a > KeyOf map > map a > a
 mapEmpty :: map a
 mapSingleton :: KeyOf map > a > map a
 mapInsert :: KeyOf map > a > map a > map a
 mapInsertWith :: (a > a > a) > KeyOf map > a > map a > map a
 mapDelete :: KeyOf map > map a > map a
 mapUnion :: map a > map a > map a
 mapUnionWithKey :: (KeyOf map > a > a > a) > map a > map a > map a
 mapDifference :: map a > map a > map a
 mapIntersection :: map a > map a > map a
 mapIsSubmapOf :: Eq a => map a > map a > Bool
 mapMap :: (a > b) > map a > map b
 mapMapWithKey :: (KeyOf map > a > b) > map a > map b
 mapFold :: (a > b > b) > b > map a > b
 mapFoldWithKey :: (KeyOf map > a > b > b) > b > map a > b
 mapElems :: map a > [a]
 mapKeys :: map a > [KeyOf map]
 mapToList :: map a > [(KeyOf map, a)]
 mapFromList :: [(KeyOf map, a)] > map a
 mapFromListWith :: (a > a > a) > [(KeyOf map, a)] > map a
 mapInsertList :: IsMap map => [(KeyOf map, a)] > map a > map a
 mapDeleteList :: IsMap map => [KeyOf map] > map a > map a
 mapUnions :: IsMap map => [map a] > map a
 class Monad m => CheckpointMonad m where
 type Checkpoint m
 checkpoint :: m (Checkpoint m)
 restart :: Checkpoint m > m ()
 data DataflowLattice a = DataflowLattice {}
 type JoinFun a = Label > OldFact a > NewFact a > (ChangeFlag, a)
 newtype OldFact a = OldFact a
 newtype NewFact a = NewFact a
 type family Fact x f :: *
 mkFactBase :: forall f. DataflowLattice f > [(Label, f)] > FactBase f
 data ChangeFlag
 = NoChange
  SomeChange
 changeIf :: Bool > ChangeFlag
 data FwdPass m n f = FwdPass {
 fp_lattice :: DataflowLattice f
 fp_transfer :: FwdTransfer n f
 fp_rewrite :: FwdRewrite m n f
 newtype FwdTransfer n f = FwdTransfer3 {}
 mkFTransfer :: (forall e x. n e x > f > Fact x f) > FwdTransfer n f
 mkFTransfer3 :: (n C O > f > f) > (n O O > f > f) > (n O C > f > FactBase f) > FwdTransfer n f
 newtype FwdRewrite m n f = FwdRewrite3 {
 getFRewrite3 :: (n C O > f > m (Maybe (Graph n C O, FwdRewrite m n f)), n O O > f > m (Maybe (Graph n O O, FwdRewrite m n f)), n O C > f > m (Maybe (Graph n O C, FwdRewrite m n f)))
 mkFRewrite :: FuelMonad m => (forall e x. n e x > f > m (Maybe (Graph n e x))) > FwdRewrite m n f
 mkFRewrite3 :: forall m n f. FuelMonad m => (n C O > f > m (Maybe (Graph n C O))) > (n O O > f > m (Maybe (Graph n O O))) > (n O C > f > m (Maybe (Graph n O C))) > FwdRewrite m n f
 noFwdRewrite :: Monad m => FwdRewrite m n f
 wrapFR :: (forall e x. (n e x > f > m (Maybe (Graph n e x, FwdRewrite m n f))) > n' e x > f' > m' (Maybe (Graph n' e x, FwdRewrite m' n' f'))) > FwdRewrite m n f > FwdRewrite m' n' f'
 wrapFR2 :: (forall e x. (n1 e x > f1 > m1 (Maybe (Graph n1 e x, FwdRewrite m1 n1 f1))) > (n2 e x > f2 > m2 (Maybe (Graph n2 e x, FwdRewrite m2 n2 f2))) > n3 e x > f3 > m3 (Maybe (Graph n3 e x, FwdRewrite m3 n3 f3))) > FwdRewrite m1 n1 f1 > FwdRewrite m2 n2 f2 > FwdRewrite m3 n3 f3
 data BwdPass m n f = BwdPass {
 bp_lattice :: DataflowLattice f
 bp_transfer :: BwdTransfer n f
 bp_rewrite :: BwdRewrite m n f
 newtype BwdTransfer n f = BwdTransfer3 {}
 mkBTransfer :: (forall e x. n e x > Fact x f > f) > BwdTransfer n f
 mkBTransfer3 :: (n C O > f > f) > (n O O > f > f) > (n O C > FactBase f > f) > BwdTransfer n f
 wrapBR :: (forall e x. Shape x > (n e x > Fact x f > m (Maybe (Graph n e x, BwdRewrite m n f))) > n' e x > Fact x f' > m' (Maybe (Graph n' e x, BwdRewrite m' n' f'))) > BwdRewrite m n f > BwdRewrite m' n' f'
 wrapBR2 :: (forall e x. Shape x > (n1 e x > Fact x f1 > m1 (Maybe (Graph n1 e x, BwdRewrite m1 n1 f1))) > (n2 e x > Fact x f2 > m2 (Maybe (Graph n2 e x, BwdRewrite m2 n2 f2))) > n3 e x > Fact x f3 > m3 (Maybe (Graph n3 e x, BwdRewrite m3 n3 f3))) > BwdRewrite m1 n1 f1 > BwdRewrite m2 n2 f2 > BwdRewrite m3 n3 f3
 newtype BwdRewrite m n f = BwdRewrite3 {
 getBRewrite3 :: (n C O > f > m (Maybe (Graph n C O, BwdRewrite m n f)), n O O > f > m (Maybe (Graph n O O, BwdRewrite m n f)), n O C > FactBase f > m (Maybe (Graph n O C, BwdRewrite m n f)))
 mkBRewrite :: FuelMonad m => (forall e x. n e x > Fact x f > m (Maybe (Graph n e x))) > BwdRewrite m n f
 mkBRewrite3 :: forall m n f. FuelMonad m => (n C O > f > m (Maybe (Graph n C O))) > (n O O > f > m (Maybe (Graph n O O))) > (n O C > FactBase f > m (Maybe (Graph n O C))) > BwdRewrite m n f
 noBwdRewrite :: Monad m => BwdRewrite m n f
 analyzeAndRewriteFwd :: forall m n f e x entries. (CheckpointMonad m, NonLocal n, LabelsPtr entries) => FwdPass m n f > MaybeC e entries > Graph n e x > Fact e f > m (Graph n e x, FactBase f, MaybeO x f)
 analyzeAndRewriteBwd :: (CheckpointMonad m, NonLocal n, LabelsPtr entries) => BwdPass m n f > MaybeC e entries > Graph n e x > Fact x f > m (Graph n e x, FactBase f, MaybeO e f)
 data Label
 freshLabel :: UniqueMonad m => m Label
 data LabelSet
 data LabelMap v
 type FactBase f = LabelMap f
 noFacts :: FactBase f
 lookupFact :: Label > FactBase f > Maybe f
 uniqueToLbl :: Unique > Label
 lblToUnique :: Label > Unique
 data Pointed t b a where
 addPoints :: String > JoinFun a > DataflowLattice (Pointed t C a)
 addPoints' :: forall a t. String > (Label > OldFact a > NewFact a > (ChangeFlag, Pointed t C a)) > DataflowLattice (Pointed t C a)
 addTop :: DataflowLattice a > DataflowLattice (WithTop a)
 addTop' :: forall a. String > a > (Label > OldFact a > NewFact a > (ChangeFlag, WithTop a)) > DataflowLattice (WithTop a)
 liftJoinTop :: JoinFun a > JoinFun (WithTop a)
 extendJoinDomain :: forall a. (Label > OldFact a > NewFact a > (ChangeFlag, WithTop a)) > JoinFun (WithTop a)
 type WithTop a = Pointed C O a
 type WithBot a = Pointed O C a
 type WithTopAndBot a = Pointed C C a
 thenFwdRw :: forall m n f. Monad m => FwdRewrite m n f > FwdRewrite m n f > FwdRewrite m n f
 deepFwdRw3 :: FuelMonad m => (n C O > f > m (Maybe (Graph n C O))) > (n O O > f > m (Maybe (Graph n O O))) > (n O C > f > m (Maybe (Graph n O C))) > FwdRewrite m n f
 deepFwdRw :: FuelMonad m => (forall e x. n e x > f > m (Maybe (Graph n e x))) > FwdRewrite m n f
 iterFwdRw :: forall m n f. Monad m => FwdRewrite m n f > FwdRewrite m n f
 thenBwdRw :: forall m n f. Monad m => BwdRewrite m n f > BwdRewrite m n f > BwdRewrite m n f
 deepBwdRw3 :: FuelMonad m => (n C O > f > m (Maybe (Graph n C O))) > (n O O > f > m (Maybe (Graph n O O))) > (n O C > FactBase f > m (Maybe (Graph n O C))) > BwdRewrite m n f
 deepBwdRw :: FuelMonad m => (forall e x. n e x > Fact x f > m (Maybe (Graph n e x))) > BwdRewrite m n f
 iterBwdRw :: forall m n f. Monad m => BwdRewrite m n f > BwdRewrite m n f
 pairFwd :: forall m n f f'. Monad m => FwdPass m n f > FwdPass m n f' > FwdPass m n (f, f')
 pairBwd :: forall m n f f'. Monad m => BwdPass m n f > BwdPass m n f' > BwdPass m n (f, f')
 pairLattice :: forall f f'. DataflowLattice f > DataflowLattice f' > DataflowLattice (f, f')
 type Fuel = Int
 infiniteFuel :: Fuel
 fuelRemaining :: FuelMonad m => m Fuel
 withFuel :: FuelMonad m => Maybe a > m (Maybe a)
 class Monad m => FuelMonad m where
 class FuelMonadT fm where
 data CheckingFuelMonad m a
 data InfiniteFuelMonad m a
 type SimpleFuelMonad = CheckingFuelMonad SimpleUniqueMonad
 type Unique = Int
 intToUnique :: Int > Unique
 data UniqueSet
 data UniqueMap v
 class Monad m => UniqueMonad m where
 freshUnique :: m Unique
 data SimpleUniqueMonad a
 runSimpleUniqueMonad :: SimpleUniqueMonad a > a
 data UniqueMonadT m a
 runUniqueMonadT :: Monad m => UniqueMonadT m a > m a
 uniqueToInt :: Unique > Int
 type TraceFn = forall a. String > a > a
 debugFwdJoins :: forall m n f. Show f => TraceFn > ChangePred > FwdPass m n f > FwdPass m n f
 debugBwdJoins :: forall m n f. Show f => TraceFn > ChangePred > BwdPass m n f > BwdPass m n f
 debugFwdTransfers :: forall m n f. Show f => TraceFn > ShowN n > FPred n f > FwdPass m n f > FwdPass m n f
 debugBwdTransfers :: forall m n f. Show f => TraceFn > ShowN n > BPred n f > BwdPass m n f > BwdPass m n f
 showGraph :: forall n e x. NonLocal n => Showing n > Graph n e x > String
 showFactBase :: Show f => FactBase f > String
Body
Graph
type Graph = Graph' BlockSource
A controlflow graph, which may take any of four shapes (O/O, OC, CO, C/C). A graph open at the entry has a single, distinguished, anonymous entry point; if a graph is closed at the entry, its entry point(s) are supplied by a context.
data Graph' block n e x whereSource
Graph'
is abstracted over the block type, so that we can build
graphs of annotated blocks for example (Compiler.Hoopl.Dataflow
needs this).
class NonLocal thing whereSource
Gives access to the anchor points for nonlocal edges as well as the edges themselves
Constructing graphs
blockGraph :: NonLocal n => Block n e x > Graph n e xSource
Splicing graphs
splice :: forall block n e a x. NonLocal (block n) => (forall e x. block n e O > block n O x > block n e x) > Graph' block n e a > Graph' block n a x > Graph' block n e xSource
Maps
mapGraph :: (forall e x. n e x > n' e x) > Graph n e x > Graph n' e xSource
Maps over all nodes in a graph.
mapGraphBlocks :: forall block n block' n' e x. (forall e x. block n e x > block' n' e x) > Graph' block n e x > Graph' block' n' e xSource
Function mapGraphBlocks
enables a change of representation of blocks,
nodes, or both. It lifts a polymorphic block transform into a polymorphic
graph transform. When the block representation stabilizes, a similar
function should be provided for blocks.
Folds
foldGraphNodes :: forall n a. (forall e x. n e x > a > a) > forall e x. Graph n e x > a > aSource
Fold a function over every node in a graph. The fold function must be polymorphic in the shape of the nodes.
Extracting Labels
labelsDefined :: forall block n e x. NonLocal (block n) => Graph' block n e x > LabelSetSource
labelsUsed :: forall block n e x. NonLocal (block n) => Graph' block n e x > LabelSetSource
Depthfirst traversals
postorder_dfs :: NonLocal (block n) => Graph' block n O x > [block n C C]Source
Traversal: postorder_dfs
returns a list of blocks reachable
from the entry of enterable graph. The entry and exit are *not* included.
The list has the following property:
Say a back reference exists if one of a block's controlflow successors precedes it in the output list
Then there are as few back references as possible
The output is suitable for use in
a forward dataflow problem. For a backward problem, simply reverse
the list. (postorder_dfs
is sufficiently tricky to implement that
one doesn't want to try and maintain both forward and backward
versions.)
postorder_dfs_from :: (NonLocal block, LabelsPtr b) => LabelMap (block C C) > b > [block C C]Source
postorder_dfs_from_except :: forall block e. (NonLocal block, LabelsPtr e) => LabelMap (block C C) > e > LabelSet > [block C C]Source
preorder_dfs_from_except :: forall block e. (NonLocal block, LabelsPtr e) => LabelMap (block C C) > e > LabelSet > [block C C]Source
targetLabels :: l > [Label]Source
Shapes
Used at the type level to indicate an open structure with a unique, unnamed controlflow edge flowing in or out. Fallthrough and concatenation are permitted at an open point.
Used at the type level to indicate a closed structure which supports control transfer only through the use of named labelsno fallthrough is permitted. The number of controlflow edges is unconstrained.
IfThenElseable C  
NonLocal n => LabelsPtr (n e C) 
Maybe type indexed by open/closed
Maybe type indexed by closed/open
Blocks
A sequence of nodes. May be any of four shapes (OO, OC, CO, CC). Open at the entry means single entry, mutatis mutandis for exit. A closedclosed block is a basic/ block and can't be extended further. Clients should avoid manipulating blocks and should stick to either nodes or graphs.
BlockCO :: n C O > Block n O O > Block n C O  
BlockCC :: n C O > Block n O O > n O C > Block n C C  
BlockOC :: Block n O O > n O C > Block n O C  
BNil :: Block n O O  
BMiddle :: n O O > Block n O O  
BCat :: Block n O O > Block n O O > Block n O O  
BSnoc :: Block n O O > n O O > Block n O O  
BCons :: n O O > Block n O O > Block n O O 
Predicates on Blocks
isEmptyBlock :: Block n e x > BoolSource
Constructing blocks
emptyBlock :: Block n O OSource
blockJoinAny :: (MaybeC e (n C O), Block n O O, MaybeC x (n O C)) > Block n e xSource
Convert a list of nodes to a block. The entry and exit node must or must not be present depending on the shape of the block.
Deconstructing blocks
blockSplit :: Block n C C > (n C O, Block n O O, n O C)Source
Split a closed block into its entry node, open middle block, and exit node.
Modifying blocks
Converting to and from lists
Maps and folds
mapBlock :: (forall e x. n e x > n' e x) > Block n e x > Block n' e xSource
map a function over the nodes of a Block
mapBlock3' :: forall n n' e x. (n C O > n' C O, n O O > n' O O, n O C > n' O C) > Block n e x > Block n' e xSource
map over a block, with different functions to apply to first nodes, middle nodes and last nodes respectively. The map is strict.
foldBlockNodesF :: forall n a. (forall e x. n e x > a > a) > forall e x. Block n e x > IndexedCO e a a > IndexedCO x a aSource
foldBlockNodesF3 :: forall n a b c. (n C O > a > b, n O O > b > b, n O C > b > c) > forall e x. Block n e x > IndexedCO e a b > IndexedCO x c bSource
Fold a function over every node in a block, forward or backward. The fold function must be polymorphic in the shape of the nodes.
foldBlockNodesB :: forall n a. (forall e x. n e x > a > a) > forall e x. Block n e x > IndexedCO x a a > IndexedCO e a aSource
foldBlockNodesB3 :: forall n a b c. (n C O > b > c, n O O > b > b, n O C > a > b) > forall e x. Block n e x > IndexedCO x a b > IndexedCO e c bSource
Biasing
frontBiasBlock :: Block n e x > Block n e xSource
A block is front biased if the left child of every concatenation operation is a node, not a general block; a frontbiased block is analogous to an ordinary list. If a block is frontbiased, then its nodes can be traversed from front to back without general recusion; tail recursion suffices. Not all shapes can be frontbiased; a closed/open block is inherently backbiased.
backBiasBlock :: Block n e x > Block n e xSource
A block is back biased if the right child of every concatenation operation is a node, not a general block; a backbiased block is analogous to a snoclist. If a block is backbiased, then its nodes can be traversed from back to back without general recusion; tail recursion suffices. Not all shapes can be backbiased; an open/closed block is inherently frontbiased.
The type of abstract graphs. Offers extra smart constructors that may consume fresh labels during construction.
graphOfAGraph :: AGraph n e x > forall m. UniqueMonad m => m (Graph n e x)Source
aGraphOfGraph :: Graph n e x > AGraph n e xSource
Take a graph and make it abstract.
(<*>) :: (GraphRep g, NonLocal n) => g n e O > g n O x > g n e xSource
Concatenate two graphs; control flows from left to right.
(*><*) :: (GraphRep g, NonLocal n) => g n e C > g n C x > g n e xSource
Splice together two graphs at a closed point; nothing is known about control flow.
catGraphs :: (GraphRep g, NonLocal n) => [g n O O] > g n O OSource
Conveniently concatenate a sequence of open/open graphs using <*>
.
addEntrySeq :: NonLocal n => AGraph n O C > AGraph n C x > AGraph n O xSource
Deprecated: use *><* instead
addExitSeq :: NonLocal n => AGraph n e C > AGraph n C O > AGraph n e OSource
Deprecated: use *><* instead
addBlocks :: HooplNode n => AGraph n e x > AGraph n C C > AGraph n e xSource
Extend an existing AGraph
with extra basic blocks out of line.
No control flow is implied. Simon PJ should give example use case.
unionBlocks :: NonLocal n => AGraph n C C > AGraph n C C > AGraph n C CSource
Deprecated: use *><* instead
emptyGraph :: GraphRep g => g n O OSource
An empty graph that is open at entry and exit.
It is the left and right identity of <*>
.
emptyClosedGraph :: GraphRep g => g n C CSource
An empty graph that is closed at entry and exit.
It is the left and right identity of *><*
.
mkMiddles :: (GraphRep g, NonLocal n) => [n O O] > g n O OSource
Conveniently concatenate a sequence of middle nodes to form an open/open graph.
mkBranch :: (GraphRep g, HooplNode n) => Label > g n O CSource
Create a graph that branches to a label
class IfThenElseable x whereSource
:: HooplNode n  
=> (Label > Label > AGraph n O C)  branch condition 
> AGraph n O x  code in the then branch 
> AGraph n O x  code in the else branch 
> AGraph n O x  resulting ifthenelse construct 
Translate a highlevel ifthenelse construct into an AGraph
.
The condition takes as arguments labels on the truefalse branch
and returns a singleentry, twoexit graph which exits to
the two labels.
mkEntry :: GraphRep g => Block n O C > g n O CSource
Create a graph containing only an entry sequence
class NonLocal n => HooplNode n whereSource
For some graphconstruction operations and some optimizations,
Hoopl must be able to create controlflow edges using a given node
type n
.
mkBranchNode :: Label > n O CSource
Create a branch node, the source of a controlflow edge.
mkLabelNode :: Label > n C OSource
Create a label node, the target (destination) of a controlflow edge.
Utilities for clients
firstXfer :: NonLocal n => (n C O > f > f) > n C O > FactBase f > fSource
A utility function so that a transfer function for a first node can be given just a fact; we handle the lookup. This function is planned to be made obsolete by changes in the dataflow interface.
distributeXfer :: NonLocal n => DataflowLattice f > (n O C > f > f) > n O C > f > FactBase fSource
This utility function handles a common case in which a transfer function produces a single fact out of a last node, which is then distributed over the outgoing edges.
distributeFact :: NonLocal n => n O C > f > FactBase fSource
This utility function handles a common case in which a transfer function for a last node takes the incoming fact unchanged and simply distributes that fact over the outgoing edges.
distributeFactBwd :: NonLocal n => n C O > f > FactBase fSource
This utility function handles a common case in which a backward transfer function takes the incoming fact unchanged and tags it with the node's label.
successorFacts :: NonLocal n => n O C > FactBase f > [f]Source
List of (unlabelled) facts from the successors of a last node
joinFacts :: DataflowLattice f > Label > [f] > fSource
Join a list of facts.
joinOutFacts :: NonLocal node => DataflowLattice f > node O C > FactBase f > fSource
Deprecated: should be replaced by 'joinFacts lat l (successorFacts n f)'; as is, it uses the wrong Label
joinMaps :: Ord k => JoinFun v > JoinFun (Map k v)Source
It's common to represent dataflow facts as a map from variables to some fact about the locations. For these maps, the join operation on the map can be expressed in terms of the join on each element of the codomain:
analyzeAndRewriteFwdBody :: forall m n f entries. (CheckpointMonad m, NonLocal n, LabelsPtr entries) => FwdPass m n f > entries > Body n > FactBase f > m (Body n, FactBase f)Source
Forward dataflow analysis and rewriting for the special case of a Body. A set of entry points must be supplied; blocks not reachable from the set are thrown away.
analyzeAndRewriteBwdBody :: forall m n f entries. (CheckpointMonad m, NonLocal n, LabelsPtr entries) => BwdPass m n f > entries > Body n > FactBase f > m (Body n, FactBase f)Source
Backward dataflow analysis and rewriting for the special case of a Body. A set of entry points must be supplied; blocks not reachable from the set are thrown away.
analyzeAndRewriteFwdOx :: forall m n f x. (CheckpointMonad m, NonLocal n) => FwdPass m n f > Graph n O x > f > m (Graph n O x, FactBase f, MaybeO x f)Source
Forward dataflow analysis and rewriting for the special case of a
graph open at the entry. This special case relieves the client
from having to specify a type signature for NothingO
, which beginners
might find confusing and experts might find annoying.
analyzeAndRewriteBwdOx :: forall m n f x. (CheckpointMonad m, NonLocal n) => BwdPass m n f > Graph n O x > Fact x f > m (Graph n O x, FactBase f, f)Source
Backward dataflow analysis and rewriting for the special case of a
graph open at the entry. This special case relieves the client
from having to specify a type signature for NothingO
, which beginners
might find confusing and experts might find annoying.
setMember :: ElemOf set > set > BoolSource
setSingleton :: ElemOf set > setSource
setInsert :: ElemOf set > set > setSource
setDelete :: ElemOf set > set > setSource
setUnion :: set > set > setSource
setDifference :: set > set > setSource
setIntersection :: set > set > setSource
setIsSubsetOf :: set > set > BoolSource
setFold :: (ElemOf set > b > b) > b > set > bSource
setElems :: set > [ElemOf set]Source
setFromList :: [ElemOf set] > setSource
setInsertList :: IsSet set => [ElemOf set] > set > setSource
setDeleteList :: IsSet set => [ElemOf set] > set > setSource
mapNull :: map a > BoolSource
mapMember :: KeyOf map > map a > BoolSource
mapLookup :: KeyOf map > map a > Maybe aSource
mapFindWithDefault :: a > KeyOf map > map a > aSource
mapSingleton :: KeyOf map > a > map aSource
mapInsert :: KeyOf map > a > map a > map aSource
mapInsertWith :: (a > a > a) > KeyOf map > a > map a > map aSource
mapDelete :: KeyOf map > map a > map aSource
mapUnion :: map a > map a > map aSource
mapUnionWithKey :: (KeyOf map > a > a > a) > map a > map a > map aSource
mapDifference :: map a > map a > map aSource
mapIntersection :: map a > map a > map aSource
mapIsSubmapOf :: Eq a => map a > map a > BoolSource
mapMap :: (a > b) > map a > map bSource
mapMapWithKey :: (KeyOf map > a > b) > map a > map bSource
mapFold :: (a > b > b) > b > map a > bSource
mapFoldWithKey :: (KeyOf map > a > b > b) > b > map a > bSource
mapElems :: map a > [a]Source
mapKeys :: map a > [KeyOf map]Source
mapToList :: map a > [(KeyOf map, a)]Source
mapFromList :: [(KeyOf map, a)] > map aSource
mapFromListWith :: (a > a > a) > [(KeyOf map, a)] > map aSource
mapInsertList :: IsMap map => [(KeyOf map, a)] > map a > map aSource
mapDeleteList :: IsMap map => [KeyOf map] > map a > map aSource
class Monad m => CheckpointMonad m whereSource
Obeys the following law:
for all m
do { s < checkpoint; m; restart s } == return ()
type Checkpoint m Source
checkpoint :: m (Checkpoint m)Source
restart :: Checkpoint m > m ()Source
data DataflowLattice a Source
A transfer function might want to use the logging flag to control debugging, as in for example, it updates just one element in a big finite map. We don't want Hoopl to show the whole fact, and only the transfer function knows exactly what changed.
mkFactBase :: forall f. DataflowLattice f > [(Label, f)] > FactBase fSource
mkFactBase
creates a FactBase
from a list of (Label
, fact)
pairs. If the same label appears more than once, the relevant facts
are joined.
changeIf :: Bool > ChangeFlagSource
FwdPass  

newtype FwdTransfer n f Source
mkFTransfer :: (forall e x. n e x > f > Fact x f) > FwdTransfer n fSource
mkFTransfer3 :: (n C O > f > f) > (n O O > f > f) > (n O C > f > FactBase f) > FwdTransfer n fSource
newtype FwdRewrite m n f Source
FwdRewrite3  

mkFRewrite :: FuelMonad m => (forall e x. n e x > f > m (Maybe (Graph n e x))) > FwdRewrite m n fSource
Functions passed to mkFRewrite
should not be aware of the fuel supply.
The result returned by mkFRewrite
respects fuel.
mkFRewrite3 :: forall m n f. FuelMonad m => (n C O > f > m (Maybe (Graph n C O))) > (n O O > f > m (Maybe (Graph n O O))) > (n O C > f > m (Maybe (Graph n O C))) > FwdRewrite m n fSource
Functions passed to mkFRewrite3
should not be aware of the fuel supply.
The result returned by mkFRewrite3
respects fuel.
noFwdRewrite :: Monad m => FwdRewrite m n fSource
:: (forall e x. (n e x > f > m (Maybe (Graph n e x, FwdRewrite m n f))) > n' e x > f' > m' (Maybe (Graph n' e x, FwdRewrite m' n' f')))  This argument may assume that any function passed to it respects fuel, and it must return a result that respects fuel. 
> FwdRewrite m n f  
> FwdRewrite m' n' f' 
:: (forall e x. (n1 e x > f1 > m1 (Maybe (Graph n1 e x, FwdRewrite m1 n1 f1))) > (n2 e x > f2 > m2 (Maybe (Graph n2 e x, FwdRewrite m2 n2 f2))) > n3 e x > f3 > m3 (Maybe (Graph n3 e x, FwdRewrite m3 n3 f3)))  This argument may assume that any function passed to it respects fuel, and it must return a result that respects fuel. 
> FwdRewrite m1 n1 f1  
> FwdRewrite m2 n2 f2  
> FwdRewrite m3 n3 f3 
BwdPass  

newtype BwdTransfer n f Source
mkBTransfer :: (forall e x. n e x > Fact x f > f) > BwdTransfer n fSource
mkBTransfer3 :: (n C O > f > f) > (n O O > f > f) > (n O C > FactBase f > f) > BwdTransfer n fSource
:: (forall e x. Shape x > (n e x > Fact x f > m (Maybe (Graph n e x, BwdRewrite m n f))) > n' e x > Fact x f' > m' (Maybe (Graph n' e x, BwdRewrite m' n' f')))  This argument may assume that any function passed to it respects fuel, and it must return a result that respects fuel. 
> BwdRewrite m n f  
> BwdRewrite m' n' f' 
:: (forall e x. Shape x > (n1 e x > Fact x f1 > m1 (Maybe (Graph n1 e x, BwdRewrite m1 n1 f1))) > (n2 e x > Fact x f2 > m2 (Maybe (Graph n2 e x, BwdRewrite m2 n2 f2))) > n3 e x > Fact x f3 > m3 (Maybe (Graph n3 e x, BwdRewrite m3 n3 f3)))  This argument may assume that any function passed to it respects fuel, and it must return a result that respects fuel. 
> BwdRewrite m1 n1 f1  
> BwdRewrite m2 n2 f2  
> BwdRewrite m3 n3 f3 
newtype BwdRewrite m n f Source
BwdRewrite3  

mkBRewrite :: FuelMonad m => (forall e x. n e x > Fact x f > m (Maybe (Graph n e x))) > BwdRewrite m n fSource
Functions passed to mkBRewrite
should not be aware of the fuel supply.
The result returned by mkBRewrite
respects fuel.
mkBRewrite3 :: forall m n f. FuelMonad m => (n C O > f > m (Maybe (Graph n C O))) > (n O O > f > m (Maybe (Graph n O O))) > (n O C > FactBase f > m (Maybe (Graph n O C))) > BwdRewrite m n fSource
Functions passed to mkBRewrite3
should not be aware of the fuel supply.
The result returned by mkBRewrite3
respects fuel.
noBwdRewrite :: Monad m => BwdRewrite m n fSource
analyzeAndRewriteFwd :: forall m n f e x entries. (CheckpointMonad m, NonLocal n, LabelsPtr entries) => FwdPass m n f > MaybeC e entries > Graph n e x > Fact e f > m (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 :: (CheckpointMonad m, NonLocal n, LabelsPtr entries) => BwdPass m n f > MaybeC e entries > Graph n e x > Fact x f > m (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
Respecting Fuel
A value of type FwdRewrite
or BwdRewrite
respects fuel if
any function contained within the value satisfies the following properties:
 When fuel is exhausted, it always returns
Nothing
.  When it returns
Just g rw
, it consumes exactly one unit of fuel, and new rewriterw
also respects fuel.
Provided that functions passed to mkFRewrite
, mkFRewrite3
,
mkBRewrite
, and mkBRewrite3
are not aware of the fuel supply,
the results respect fuel.
It is an unchecked runtime error for the argument passed to wrapFR
,
wrapFR2
, wrapBR
, or warpBR2
to return a function that does not respect fuel.
freshLabel :: UniqueMonad m => m LabelSource
lookupFact :: Label > FactBase f > Maybe fSource
uniqueToLbl :: Unique > LabelSource
lblToUnique :: Label > UniqueSource
data Pointed t b a whereSource
Adds top, bottom, or both to help form a lattice
The type parameters t
and b
are used to say whether top
and bottom elements have been added. The analogy with Block
is nearly exact:
 A
Block
is closed at the entry if and only if it has a first node; aPointed
is closed at the top if and only if it has a top element.  A
Block
is closed at the exit if and only if it has a last node; aPointed
is closed at the bottom if and only if it has a bottom element.
We thus have four possible types, of which three are interesting:
Pointed C C a
 Type
a
extended with both top and bottom elements. Pointed C O a
 Type
a
extended with a top element only. (Presumablya
comes equipped with a bottom element of its own.) Pointed O C a
 Type
a
extended with a bottom element only. Pointed O O a
 Isomorphic to
a
, and therefore not interesting.
The advantage of all this GADTishness is that the constructors
Bot
, Top
, and PElem
can all be used polymorphically.
addPoints :: String > JoinFun a > DataflowLattice (Pointed t C a)Source
Given a join function and a name, creates a semi lattice by
adding a bottom element, and possibly a top element also.
A specialized version of addPoints'
.
addPoints' :: forall a t. String > (Label > OldFact a > NewFact a > (ChangeFlag, Pointed t C a)) > DataflowLattice (Pointed t C a)Source
A more general case for creating a new lattice
addTop :: DataflowLattice a > DataflowLattice (WithTop a)Source
Given a join function and a name, creates a semi lattice by adding a top element but no bottom element. Caller must supply the bottom element.
addTop' :: forall a. String > a > (Label > OldFact a > NewFact a > (ChangeFlag, WithTop a)) > DataflowLattice (WithTop a)Source
A more general case for creating a new lattice
liftJoinTop :: JoinFun a > JoinFun (WithTop a)Source
extendJoinDomain :: forall a. (Label > OldFact a > NewFact a > (ChangeFlag, WithTop a)) > JoinFun (WithTop a)Source
type WithTopAndBot a = Pointed C C aSource
Type a
with top and bottom elements adjoined
thenFwdRw :: forall m n f. Monad m => FwdRewrite m n f > FwdRewrite m n f > FwdRewrite m n fSource
deepFwdRw3 :: FuelMonad m => (n C O > f > m (Maybe (Graph n C O))) > (n O O > f > m (Maybe (Graph n O O))) > (n O C > f > m (Maybe (Graph n O C))) > FwdRewrite m n fSource
deepFwdRw :: FuelMonad m => (forall e x. n e x > f > m (Maybe (Graph n e x))) > FwdRewrite m n fSource
iterFwdRw :: forall m n f. Monad m => FwdRewrite m n f > FwdRewrite m n fSource
thenBwdRw :: forall m n f. Monad m => BwdRewrite m n f > BwdRewrite m n f > BwdRewrite m n fSource
deepBwdRw3 :: FuelMonad m => (n C O > f > m (Maybe (Graph n C O))) > (n O O > f > m (Maybe (Graph n O O))) > (n O C > FactBase f > m (Maybe (Graph n O C))) > BwdRewrite m n fSource
deepBwdRw :: FuelMonad m => (forall e x. n e x > Fact x f > m (Maybe (Graph n e x))) > BwdRewrite m n fSource
iterBwdRw :: forall m n f. Monad m => BwdRewrite m n f > BwdRewrite m n fSource
pairLattice :: forall f f'. DataflowLattice f > DataflowLattice f' > DataflowLattice (f, f')Source
fuelRemaining :: FuelMonad m => m FuelSource
Find out how much fuel remains after a computation. Can be subtracted from initial fuel to get total consumption.
class Monad m => FuelMonad m whereSource
Monad m => FuelMonad (InfiniteFuelMonad m)  
Monad m => FuelMonad (CheckingFuelMonad m) 
class FuelMonadT fm whereSource
data CheckingFuelMonad m a Source
FuelMonadT CheckingFuelMonad  
Monad m => Monad (CheckingFuelMonad m)  
CheckpointMonad m => CheckpointMonad (CheckingFuelMonad m)  
UniqueMonad m => UniqueMonad (CheckingFuelMonad m)  
Monad m => FuelMonad (CheckingFuelMonad m) 
data InfiniteFuelMonad m a Source
FuelMonadT InfiniteFuelMonad  
Monad m => Monad (InfiniteFuelMonad m)  
CheckpointMonad m => CheckpointMonad (InfiniteFuelMonad m)  
UniqueMonad m => UniqueMonad (InfiniteFuelMonad m)  
Monad m => FuelMonad (InfiniteFuelMonad m) 
intToUnique :: Int > UniqueSource
class Monad m => UniqueMonad m whereSource
freshUnique :: m UniqueSource
UniqueMonad SimpleUniqueMonad  
Monad m => UniqueMonad (UniqueMonadT m)  
UniqueMonad m => UniqueMonad (InfiniteFuelMonad m)  
UniqueMonad m => UniqueMonad (CheckingFuelMonad m) 
data SimpleUniqueMonad a Source
runSimpleUniqueMonad :: SimpleUniqueMonad a > aSource
data UniqueMonadT m a Source
Monad m => Monad (UniqueMonadT m)  
Monad m => UniqueMonad (UniqueMonadT m) 
runUniqueMonadT :: Monad m => UniqueMonadT m a > m aSource
uniqueToInt :: Unique > IntSource
debugFwdJoins :: forall m n f. Show f => TraceFn > ChangePred > FwdPass m n f > FwdPass m 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
Trace
 pass
trace
as the 1st argument to the debug combinator  pass 'const true' as the 2nd argument to the debug combinator
There are two kinds of debugging messages for a join,
depending on whether the join is higher in the lattice than the old fact:
1. If the join is higher, we show:
+ JoinL: f1
L: f2 <= f1
where:
_ indicates no change
L is the label where the join takes place
f1 is the old fact at the label (which remains unchanged)
f2 is the new fact we joined with f1
join
f2 = f'
where:
+ indicates a change
L is the label where the join takes place
f1 is the old fact at the label
f2 is the new fact we are joining to f1
f' is the result of the join
2. _ Join
debugBwdJoins :: forall m n f. Show f => TraceFn > ChangePred > BwdPass m n f > BwdPass m n fSource
debugFwdTransfers :: forall m n f. Show f => TraceFn > ShowN n > FPred n f > FwdPass m n f > FwdPass m n fSource
debugBwdTransfers :: forall m n f. Show f => TraceFn > ShowN n > BPred n f > BwdPass m n f > BwdPass m n fSource
showFactBase :: Show f => FactBase f > StringSource