-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A library to support dataflow analysis and optimization
--   
--   Higher-order optimization library
@package hoopl
@version 3.8.7.3

module Compiler.Hoopl.GHC
uniqueToInt :: Unique -> Int
uniqueToLbl :: Unique -> Label
lblToUnique :: Label -> Unique
getFuel :: FuelMonad m => m Fuel
setFuel :: FuelMonad m => Fuel -> m ()
bodyToBlockMap :: Body' block n -> LabelMap (block n C C)
bodyOfBlockMap :: LabelMap (block n C C) -> Body' block n


-- | <i>Deprecated: Use only if you know what you are doing and can
--   preserve the 'respects fuel' invariant</i>
module Compiler.Hoopl.Wrappers
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
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

module Compiler.Hoopl

-- | Used at the type level to indicate an <a>open</a> structure with a
--   unique, unnamed control-flow edge flowing in or out.
--   <a>Fallthrough</a> and concatenation are permitted at an open point.
data O

-- | Used at the type level to indicate a <a>closed</a> structure which
--   supports control transfer only through the use of named labels---no
--   <a>fallthrough</a> is permitted. The number of control-flow edges is
--   unconstrained.
data C

-- | A sequence of nodes. May be any of four shapes (O<i>O, O</i>C, C<i>O,
--   C</i>C). Open at the entry means single entry, mutatis mutandis for
--   exit. A closed<i>closed block is a </i>basic/ block and can't be
--   extended further. Clients should avoid manipulating blocks and should
--   stick to either nodes or graphs.
data Block n e x
BFirst :: n C O -> Block n C O
BMiddle :: n O O -> Block n O O
BLast :: n O C -> Block n O C
BCat :: Block n O O -> Block n O O -> Block n O O
BHead :: Block n C O -> n O O -> Block n C O
BTail :: n O O -> Block n O C -> Block n O C
BClosed :: Block n C O -> Block n O C -> Block n C C

-- | A (possibly empty) collection of closed/closed blocks
type Body n = LabelMap (Block n C C)
newtype Body' block n
Body :: (LabelMap (block n C C)) -> Body' block n

-- | A control-flow graph, which may take any of four shapes (O<i>O,
--   O</i>C, C<i>O, C</i>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.
type Graph = Graph' Block
data Graph' block (n :: * -> * -> *) e x
GNil :: Graph' block n O O
GUnit :: block n O O -> Graph' block n O O
GMany :: MaybeO e (block n O C) -> LabelMap (block n C C) -> MaybeO x (block n C O) -> Graph' block n e x

-- | Maybe type indexed by open/closed
data MaybeO ex t
JustO :: t -> MaybeO O t
NothingO :: MaybeO C t

-- | Maybe type indexed by closed/open
data MaybeC ex t
JustC :: t -> MaybeC C t
NothingC :: MaybeC O t

-- | Dynamic shape value
data Shape ex
Closed :: Shape C
Open :: Shape O

-- | Either type indexed by closed/open using type families

-- | Gives access to the anchor points for nonlocal edges as well as the
--   edges themselves
class NonLocal thing
entryLabel :: NonLocal thing => thing C x -> Label
successors :: NonLocal thing => thing e C -> [Label]
emptyBody :: LabelMap (thing C C)
addBlock :: NonLocal thing => thing C C -> LabelMap (thing C C) -> LabelMap (thing C C)
bodyList :: NonLocal (block n) => Body' block n -> [(Label, block n C C)]

-- | Maps over all nodes in a graph.
mapGraph :: (forall e x. n e x -> n' e x) -> Graph n e x -> Graph n' e x
mapMaybeO :: (forall e x. n e x -> n' e x) -> MaybeO ex (Block n e x) -> MaybeO ex (Block n' e x)
mapMaybeC :: (forall e x. n e x -> n' e x) -> MaybeC ex (Block n e x) -> MaybeC ex (Block n' e x)
mapBlock :: (forall e x. n e x -> n' e x) -> Block n e x -> Block n' e x

-- | The type of abstract graphs. Offers extra <a>smart constructors</a>
--   that may consume fresh labels during construction.
data AGraph n e x

-- | Take an abstract <a>AGraph</a> and make a concrete (if monadic)
--   <a>Graph</a>.
graphOfAGraph :: AGraph n e x -> forall m. UniqueMonad m => m (Graph n e x)

-- | Take a graph and make it abstract.
aGraphOfGraph :: Graph n e x -> AGraph n e x

-- | Concatenate two graphs; control flows from left to right.
(<*>) :: (GraphRep g, NonLocal n) => g n e O -> g n O x -> g n e x

-- | Splice together two graphs at a closed point; nothing is known about
--   control flow.
(|*><*|) :: (GraphRep g, NonLocal n) => g n e C -> g n C x -> g n e x

-- | Conveniently concatenate a sequence of open/open graphs using
--   <a>&lt;*&gt;</a>.
catGraphs :: (GraphRep g, NonLocal n) => [g n O O] -> g n O O

-- | <i>Deprecated: use |*&gt;&lt;*| instead</i>
addEntrySeq :: NonLocal n => AGraph n O C -> AGraph n C x -> AGraph n O x

-- | <i>Deprecated: use |*&gt;&lt;*| instead</i>
addExitSeq :: NonLocal n => AGraph n e C -> AGraph n C O -> AGraph n e O

-- | Extend an existing <a>AGraph</a> with extra basic blocks <a>out of
--   line</a>. No control flow is implied. Simon PJ should give example use
--   case.
addBlocks :: HooplNode n => AGraph n e x -> AGraph n C C -> AGraph n e x

-- | <i>Deprecated: use |*&gt;&lt;*| instead</i>
unionBlocks :: NonLocal n => AGraph n C C -> AGraph n C C -> AGraph n C C

-- | An empty graph that is open at entry and exit. It is the left and
--   right identity of <a>&lt;*&gt;</a>.
emptyGraph :: GraphRep g => g n O O

-- | An empty graph that is closed at entry and exit. It is the left and
--   right identity of <a>|*&gt;&lt;*|</a>.
emptyClosedGraph :: GraphRep g => g n C C
withFresh :: Uniques u => (u -> AGraph n e x) -> AGraph n e x

-- | Create a graph from a first node
mkFirst :: GraphRep g => n C O -> g n C O

-- | Create a graph from a middle node
mkMiddle :: GraphRep g => n O O -> g n O O

-- | Conveniently concatenate a sequence of middle nodes to form an
--   open/open graph.
mkMiddles :: (GraphRep g, NonLocal n) => [n O O] -> g n O O

-- | Create a graph from a last node
mkLast :: GraphRep g => n O C -> g n O C

-- | Create a graph that branches to a label
mkBranch :: (GraphRep g, HooplNode n) => Label -> g n O C

-- | Create a graph that defines a label
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
mkIfThenElse :: (IfThenElseable x, HooplNode n) => (Label -> Label -> AGraph n O C) -> AGraph n O x -> AGraph n O x -> AGraph n O x

-- | Create a graph containing only an entry sequence
mkEntry :: GraphRep g => Block n O C -> g n O C

-- | Create a graph containing only an exit sequence
mkExit :: GraphRep g => Block n C O -> g n C O

-- | For some graph-construction operations and some optimizations, Hoopl
--   must be able to create control-flow edges using a given node type
--   <tt>n</tt>.
class NonLocal n => HooplNode n
mkBranchNode :: HooplNode n => Label -> n O C
mkLabelNode :: HooplNode n => Label -> n C O

-- | 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.
firstXfer :: NonLocal n => (n C O -> f -> f) -> (n C O -> FactBase f -> f)

-- | 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.
distributeXfer :: NonLocal n => DataflowLattice f -> (n O C -> f -> f) -> (n O C -> f -> FactBase f)

-- | 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.
distributeFact :: NonLocal n => n O C -> f -> FactBase f

-- | 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.
distributeFactBwd :: NonLocal n => n C O -> f -> FactBase f

-- | List of (unlabelled) facts from the successors of a last node
successorFacts :: NonLocal n => n O C -> FactBase f -> [f]

-- | Join a list of facts.
joinFacts :: DataflowLattice f -> Label -> [f] -> f

-- | <i>Deprecated: should be replaced by 'joinFacts lat l (successorFacts
--   n f)'; as is, it uses the wrong Label</i>
joinOutFacts :: NonLocal node => DataflowLattice f -> node O C -> FactBase f -> f

-- | 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:
joinMaps :: Ord k => JoinFun v -> JoinFun (Map k v)

-- | Fold a function over every node in a graph. The fold function must be
--   polymorphic in the shape of the nodes.
foldGraphNodes :: (forall e x. n e x -> a -> a) -> (forall e x. Graph n e x -> a -> a)
foldBlockNodesF :: (forall e x. n e x -> a -> a) -> (forall e x. Block n e x -> IndexedCO e a a -> IndexedCO x a a)
foldBlockNodesB :: (forall e x. n e x -> a -> a) -> (forall e x. Block n e x -> IndexedCO x a a -> IndexedCO e a a)

-- | Fold a function over every node in a block, forward or backward. The
--   fold function must be polymorphic in the shape of the nodes.
foldBlockNodesF3 :: (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)
foldBlockNodesB3 :: (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)

-- | A fold function that relies on the IndexedCO type function. Note that
--   the type parameter e is available to the functions that are applied to
--   the middle and last nodes.
tfFoldBlock :: (n C O -> bc, n O O -> IndexedCO e bc bo -> IndexedCO e bc bo, n O C -> IndexedCO e bc bo -> c) -> (Block n e x -> bo -> IndexedCO x c (IndexedCO e bc bo))
data ScottBlock n a
ScottBlock :: (n C O -> a C O) -> (n O O -> a O O) -> (n O C -> a O C) -> (forall e x. a e O -> a O x -> a e x) -> ScottBlock n a
scottFoldBlock :: ScottBlock n a -> Block n e x -> a e x
fbnf3 :: (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)

-- | Convert a block to a list of nodes. The entry and exit node is or is
--   not present depending on the shape of the block.
--   
--   The blockToNodeList function cannot be currently expressed using
--   foldBlockNodesB, because it returns IndexedCO e a b, which means two
--   different types depending on the shape of the block entry. But
--   blockToNodeList returns one of four possible types, depending on the
--   shape of the block entry *and* exit.

-- | <i>Deprecated: What justifies these functions? Can they be eliminated?
--   Replaced with folds?</i>
blockToNodeList :: Block n e x -> (MaybeC e (n C O), [n O O], MaybeC x (n O C))

-- | 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.

-- | <i>Deprecated: What justifies these functions? Can they be eliminated?
--   Replaced with folds?</i>
blockOfNodeList :: (MaybeC e (n C O), [n O O], MaybeC x (n O C)) -> Block n e x
blockToNodeList' :: Block n e x -> (MaybeC e (n C O), [n O O], MaybeC x (n O C))
blockToNodeList'' :: Block n e x -> (MaybeC e (n C O), [n O O], MaybeC x (n O C))
blockToNodeList''' :: (IndexedCO e (NodeList' C O n) (NodeList' O O n) ~ NodeList' e O n, IndexedCO x (NodeList' e C n) (NodeList' e O n) ~ NodeList' e x n) => Block n e x -> NodeList' e x n

-- | 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.
analyzeAndRewriteFwdBody :: (CheckpointMonad m, NonLocal n, LabelsPtr entries) => FwdPass m n f -> entries -> Body n -> FactBase f -> m (Body n, FactBase f)

-- | 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.
analyzeAndRewriteBwdBody :: (CheckpointMonad m, NonLocal n, LabelsPtr entries) => BwdPass m n f -> entries -> Body n -> FactBase f -> m (Body n, FactBase f)

-- | 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 <a>NothingO</a>, which
--   beginners might find confusing and experts might find annoying.
analyzeAndRewriteFwdOx :: (CheckpointMonad m, NonLocal n) => FwdPass m n f -> Graph n O x -> f -> m (Graph n O x, FactBase f, MaybeO x f)

-- | 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 <a>NothingO</a>, which
--   beginners might find confusing and experts might find annoying.
analyzeAndRewriteBwdOx :: (CheckpointMonad m, NonLocal n) => BwdPass m n f -> Graph n O x -> Fact x f -> m (Graph n O x, FactBase f, f)

-- | A value that can be used for the entry point of a graph open at the
--   entry.
noEntries :: MaybeC O Label
data BlockResult n x
NoBlock :: BlockResult n x
BodyBlock :: Block n C C -> BlockResult n x
ExitBlock :: Block n C O -> BlockResult n O
lookupBlock :: NonLocal n => Graph n e x -> Label -> BlockResult n x
class IsSet set where type family ElemOf set
setNull :: IsSet set => set -> Bool
setSize :: IsSet set => set -> Int
setMember :: IsSet set => ElemOf set -> set -> Bool
setEmpty :: IsSet set => set
setSingleton :: IsSet set => ElemOf set -> set
setInsert :: IsSet set => ElemOf set -> set -> set
setDelete :: IsSet set => ElemOf set -> set -> set
setUnion :: IsSet set => set -> set -> set
setDifference :: IsSet set => set -> set -> set
setIntersection :: IsSet set => set -> set -> set
setIsSubsetOf :: IsSet set => set -> set -> Bool
setFold :: IsSet set => (ElemOf set -> b -> b) -> b -> set -> b
setElems :: IsSet set => set -> [ElemOf set]
setFromList :: IsSet set => [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 family KeyOf map
mapNull :: IsMap map => map a -> Bool
mapSize :: IsMap map => map a -> Int
mapMember :: IsMap map => KeyOf map -> map a -> Bool
mapLookup :: IsMap map => KeyOf map -> map a -> Maybe a
mapFindWithDefault :: IsMap map => a -> KeyOf map -> map a -> a
mapEmpty :: IsMap map => map a
mapSingleton :: IsMap map => KeyOf map -> a -> map a
mapInsert :: IsMap map => KeyOf map -> a -> map a -> map a
mapDelete :: IsMap map => KeyOf map -> map a -> map a
mapUnion :: IsMap map => map a -> map a -> map a
mapUnionWithKey :: IsMap map => (KeyOf map -> a -> a -> a) -> map a -> map a -> map a
mapDifference :: IsMap map => map a -> map a -> map a
mapIntersection :: IsMap map => map a -> map a -> map a
mapIsSubmapOf :: (IsMap map, Eq a) => map a -> map a -> Bool
mapMap :: IsMap map => (a -> b) -> map a -> map b
mapMapWithKey :: IsMap map => (KeyOf map -> a -> b) -> map a -> map b
mapFold :: IsMap map => (a -> b -> b) -> b -> map a -> b
mapFoldWithKey :: IsMap map => (KeyOf map -> a -> b -> b) -> b -> map a -> b
mapElems :: IsMap map => map a -> [a]
mapKeys :: IsMap map => map a -> [KeyOf map]
mapToList :: IsMap map => map a -> [(KeyOf map, a)]
mapFromList :: IsMap map => [(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

-- | Obeys the following law: for all <tt>m</tt> <tt> do { s &lt;-
--   checkpoint; m; restart s } == return () </tt>
class Monad m => CheckpointMonad m where type family Checkpoint m
checkpoint :: CheckpointMonad m => m (Checkpoint m)
restart :: CheckpointMonad m => Checkpoint m -> m ()

-- | 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.
data DataflowLattice a
DataflowLattice :: String -> a -> JoinFun a -> DataflowLattice a
fact_name :: DataflowLattice a -> String
fact_bot :: DataflowLattice a -> a
fact_join :: DataflowLattice a -> JoinFun a
type JoinFun a = Label -> OldFact a -> NewFact a -> (ChangeFlag, a)
newtype OldFact a
OldFact :: a -> OldFact a
newtype NewFact a
NewFact :: a -> NewFact a

-- | <a>mkFactBase</a> creates a <a>FactBase</a> from a list of
--   (<a>Label</a>, fact) pairs. If the same label appears more than once,
--   the relevant facts are joined.
mkFactBase :: DataflowLattice f -> [(Label, f)] -> FactBase f
data ChangeFlag
NoChange :: ChangeFlag
SomeChange :: ChangeFlag
changeIf :: Bool -> ChangeFlag
data FwdPass m n f
FwdPass :: DataflowLattice f -> FwdTransfer n f -> FwdRewrite m n f -> FwdPass m n f
fp_lattice :: FwdPass m n f -> DataflowLattice f
fp_transfer :: FwdPass m n f -> FwdTransfer n f
fp_rewrite :: FwdPass m n f -> FwdRewrite m n f
data FwdTransfer n f
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
getFTransfer3 :: FwdTransfer n f -> (n C O -> f -> f, n O O -> f -> f, n O C -> f -> FactBase f)
data FwdRewrite m n f

-- | Functions passed to <a>mkFRewrite</a> should not be aware of the fuel
--   supply. The result returned by <a>mkFRewrite</a> respects fuel.
mkFRewrite :: FuelMonad m => (forall e x. n e x -> f -> m (Maybe (Graph n e x))) -> FwdRewrite m n f

-- | Functions passed to <a>mkFRewrite3</a> should not be aware of the fuel
--   supply. The result returned by <a>mkFRewrite3</a> respects fuel.
mkFRewrite3 :: 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
getFRewrite3 :: FwdRewrite m n f -> (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)))
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 :: DataflowLattice f -> BwdTransfer n f -> BwdRewrite m n f -> BwdPass m n f
bp_lattice :: BwdPass m n f -> DataflowLattice f
bp_transfer :: BwdPass m n f -> BwdTransfer n f
bp_rewrite :: BwdPass m n f -> BwdRewrite m n f
data BwdTransfer n f
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
getBTransfer3 :: BwdTransfer n f -> (n C O -> f -> f, n O O -> f -> f, n O C -> FactBase f -> 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
data BwdRewrite m n f

-- | Functions passed to <a>mkBRewrite</a> should not be aware of the fuel
--   supply. The result returned by <a>mkBRewrite</a> respects fuel.
mkBRewrite :: FuelMonad m => (forall e x. n e x -> Fact x f -> m (Maybe (Graph n e x))) -> BwdRewrite m n f

-- | Functions passed to <a>mkBRewrite3</a> should not be aware of the fuel
--   supply. The result returned by <a>mkBRewrite3</a> respects fuel.
mkBRewrite3 :: 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
getBRewrite3 :: BwdRewrite m n f -> (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)))
noBwdRewrite :: Monad m => BwdRewrite m n f

-- | if the graph being analyzed is open at the entry, there must be no
--   other entry point, or all goes horribly wrong...
analyzeAndRewriteFwd :: (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)

-- | if the graph being analyzed is open at the exit, I don't quite
--   understand the implications of possible other exits
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

-- | Adds top, bottom, or both to help form a lattice
--   
--   The type parameters <tt>t</tt> and <tt>b</tt> are used to say whether
--   top and bottom elements have been added. The analogy with <a>Block</a>
--   is nearly exact:
--   
--   <ul>
--   <li>A <a>Block</a> is closed at the entry if and only if it has a
--   first node; a <a>Pointed</a> is closed at the top if and only if it
--   has a top element.</li>
--   <li>A <a>Block</a> is closed at the exit if and only if it has a last
--   node; a <a>Pointed</a> is closed at the bottom if and only if it has a
--   bottom element.</li>
--   </ul>
--   
--   We thus have four possible types, of which three are interesting:
--   
--   <ul>
--   <li><i><tt>Pointed C C a</tt></i> Type <tt>a</tt> extended with both
--   top and bottom elements.</li>
--   <li><i><tt>Pointed C O a</tt></i> Type <tt>a</tt> extended with a top
--   element only. (Presumably <tt>a</tt> comes equipped with a bottom
--   element of its own.)</li>
--   <li><i><tt>Pointed O C a</tt></i> Type <tt>a</tt> extended with a
--   bottom element only.</li>
--   <li><i><tt>Pointed O O a</tt></i> Isomorphic to <tt>a</tt>, and
--   therefore not interesting.</li>
--   </ul>
--   
--   The advantage of all this GADT-ishness is that the constructors
--   <a>Bot</a>, <a>Top</a>, and <a>PElem</a> can all be used
--   polymorphically.
--   
--   A 'Pointed t b' type is an instance of <a>Functor</a> and <a>Show</a>.
data Pointed t b a
Bot :: Pointed t C a
PElem :: a -> Pointed t b a
Top :: Pointed C b a

-- | 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 <a>addPoints'</a>.
addPoints :: String -> JoinFun a -> DataflowLattice (Pointed t C a)

-- | A more general case for creating a new lattice
addPoints' :: String -> (Label -> OldFact a -> NewFact a -> (ChangeFlag, Pointed t C a)) -> DataflowLattice (Pointed t C a)

-- | 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 :: DataflowLattice a -> DataflowLattice (WithTop a)

-- | A more general case for creating a new lattice
addTop' :: String -> a -> (Label -> OldFact a -> NewFact a -> (ChangeFlag, WithTop a)) -> DataflowLattice (WithTop a)
liftJoinTop :: JoinFun a -> JoinFun (WithTop a)
extendJoinDomain :: (Label -> OldFact a -> NewFact a -> (ChangeFlag, WithTop a)) -> JoinFun (WithTop a)

-- | Type <tt>a</tt> with a top element adjoined
type WithTop a = Pointed C O a

-- | Type <tt>a</tt> with a bottom element adjoined
type WithBot a = Pointed O C a

-- | Type <tt>a</tt> with top and bottom elements adjoined
type WithTopAndBot a = Pointed C C a
thenFwdRw :: 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 :: Monad m => FwdRewrite m n f -> FwdRewrite m n f
thenBwdRw :: 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 :: Monad m => BwdRewrite m n f -> BwdRewrite m n f
pairFwd :: Monad m => FwdPass m n f -> FwdPass m n f' -> FwdPass m n (f, f')
pairBwd :: Monad m => BwdPass m n f -> BwdPass m n f' -> BwdPass m n (f, f')
pairLattice :: DataflowLattice f -> DataflowLattice f' -> DataflowLattice (f, f')
type Fuel = Int
infiniteFuel :: Fuel

-- | Find out how much fuel remains after a computation. Can be subtracted
--   from initial fuel to get total consumption.
fuelRemaining :: FuelMonad m => m Fuel
withFuel :: FuelMonad m => Maybe a -> m (Maybe a)
class Monad m => FuelMonad m
getFuel :: FuelMonad m => m Fuel
setFuel :: FuelMonad m => Fuel -> m ()
class FuelMonadT fm
runWithFuel :: (FuelMonadT fm, Monad m, FuelMonad (fm m)) => Fuel -> fm m a -> m a
liftFuel :: (FuelMonadT fm, Monad m, FuelMonad (fm m)) => m a -> fm m a
data CheckingFuelMonad m a
data InfiniteFuelMonad m a
type SimpleFuelMonad = CheckingFuelMonad SimpleUniqueMonad
data Unique
intToUnique :: Int -> Unique
data UniqueSet
data UniqueMap v
class Monad m => UniqueMonad m
freshUnique :: UniqueMonad m => m Unique
data SimpleUniqueMonad a
runSimpleUniqueMonad :: SimpleUniqueMonad a -> a
data UniqueMonadT m a
runUniqueMonadT :: Monad m => UniqueMonadT m a -> m a
uniqueToInt :: Unique -> Int
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

-- | Function <a>graphMapBlocks</a> 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.
graphMapBlocks :: (forall e x. block n e x -> block' n' e x) -> (Graph' block n e x -> Graph' block' n' e x)
blockMapNodes :: (forall e x. n e x -> n' e x) -> (Block n e x -> Block n' e x)

-- | Function <a>blockMapNodes</a> enables a change of nodes in a block.
blockMapNodes3 :: (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
blockGraph :: NonLocal n => Block n e x -> Graph n e x

-- | Traversal: <a>postorder_dfs</a> 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 <a>back reference</a> exists if one of a block's control-flow
--   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. (<a>postorder_dfs</a> is
--   sufficiently tricky to implement that one doesn't want to try and
--   maintain both forward and backward versions.)
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 :: (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 :: (NonLocal block, LabelsPtr e) => LabelMap (block C C) -> e -> LabelSet -> [block C C]
labelsDefined :: NonLocal (block n) => Graph' block n e x -> LabelSet
labelsUsed :: NonLocal (block n) => Graph' block n e x -> LabelSet
externalEntryLabels :: NonLocal n => LabelMap (Block n C C) -> LabelSet
class LabelsPtr l
targetLabels :: LabelsPtr l => l -> [Label]
type TraceFn = forall a. String -> a -> a

-- | 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:
--   
--   <ol>
--   <li>import <a>Trace</a></li>
--   <li>pass <tt>trace</tt> as the 1st argument to the debug
--   combinator</li>
--   <li>pass 'const true' as the 2nd argument to the debug combinator</li>
--   </ol>
--   
--   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: + Join<tt>L: f1 <tt>join</tt> 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</tt>L: f2 &lt;= 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
debugFwdJoins :: Show f => TraceFn -> ChangePred -> FwdPass m n f -> FwdPass m n f
debugBwdJoins :: Show f => TraceFn -> ChangePred -> BwdPass m n f -> BwdPass m n f
debugFwdTransfers :: Show f => TraceFn -> ShowN n -> FPred n f -> FwdPass m n f -> FwdPass m n f
debugBwdTransfers :: Show f => TraceFn -> ShowN n -> BPred n f -> BwdPass m n f -> BwdPass m n f
showGraph :: NonLocal n => Showing n -> Graph n e x -> String
showFactBase :: Show f => FactBase f -> String

module Compiler.Hoopl.Passes.Dominator

-- | List of labels, extended with a standard bottom element
type Doms = WithBot DPath
newtype DPath

-- | represents part of the domination relation: each label in a list is
--   dominated by all its successors. This is a newtype only so we can give
--   it a fancy Show instance.
DPath :: [Label] -> DPath
domPath :: Doms -> [Label]

-- | The fact that goes into the entry of a dominator analysis: the first
--   node is dominated only by the entry point, which is represented by the
--   empty list of labels.
domEntry :: Doms
domLattice :: DataflowLattice Doms
extendDom :: Label -> DPath -> DPath
data DominatorNode
Entry :: DominatorNode
Labelled :: Label -> DominatorNode

-- | This data structure is a *rose tree* in which each node may have
--   arbitrarily many children. Each node dominates all its descendants.
data DominatorTree
Dominates :: DominatorNode -> [DominatorTree] -> DominatorTree

-- | Map from a FactBase for dominator lists into a dominator tree.
tree :: [(Label, Doms)] -> DominatorTree

-- | Takes FactBase from dominator analysis and returns a map from each
--   label to its immediate dominator, if any
immediateDominators :: FactBase Doms -> LabelMap Label

-- | Dominator pass
domPass :: (NonLocal n, Monad m) => FwdPass m n Doms
instance [safe] Show DominatorNode
instance [safe] Show DominatorTree
instance [safe] Show DPath

module Compiler.Hoopl.Passes.DList

-- | List of labels, extended with a standard bottom element
type Doms = WithBot [Label]

-- | The fact that goes into the entry of a dominator analysis: the first
--   node is dominated only by the entry point, which is represented by the
--   empty list of labels.
domEntry :: Doms
domLattice :: DataflowLattice Doms

-- | Dominator pass
domPass :: (NonLocal n, Monad m) => FwdPass m n Doms