| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
GHC.Cmm.Dataflow.Graph
Synopsis
- type Body (s :: Type -> k) (n :: Extensibility -> Extensibility -> Type) = Body' s Block n
- type Graph = Graph' LabelMap Block
- data Graph' (s :: Type -> Type) (block :: (Extensibility -> Extensibility -> Type) -> Extensibility -> Extensibility -> Type) (n :: Extensibility -> Extensibility -> Type) (e :: Extensibility) (x :: Extensibility) where
- GNil :: forall (s :: Type -> Type) (block :: (Extensibility -> Extensibility -> Type) -> Extensibility -> Extensibility -> Type) (n :: Extensibility -> Extensibility -> Type). Graph' s block n 'Open 'Open
- GUnit :: forall (block :: (Extensibility -> Extensibility -> Type) -> Extensibility -> Extensibility -> Type) (n :: Extensibility -> Extensibility -> Type) (s :: Type -> Type). block n O O -> Graph' s block n 'Open 'Open
- GMany :: forall (e :: Extensibility) (block :: (Extensibility -> Extensibility -> Type) -> Extensibility -> Extensibility -> Type) (n :: Extensibility -> Extensibility -> Type) (s :: Type -> Type) (x :: Extensibility). MaybeO e (block n O C) -> Body' s block n -> MaybeO x (block n C O) -> Graph' s block n e x
- class NonLocal (thing :: Extensibility -> Extensibility -> Type) where
- entryLabel :: forall (x :: Extensibility). thing C x -> Label
- successors :: forall (e :: Extensibility). thing e C -> [Label]
- addBlock :: (NonLocal block, HasDebugCallStack) => block C C -> LabelMap (block C C) -> LabelMap (block C C)
- bodyList :: forall block (n :: Extensibility -> Extensibility -> Type). Body' LabelMap block n -> [(Label, block n C C)]
- bodyToBlockList :: forall (n :: Extensibility -> Extensibility -> Type). Body LabelMap n -> [Block n C C]
- emptyBody :: forall block (n :: Extensibility -> Extensibility -> Type). Body' LabelMap block n
- labelsDefined :: forall (block :: (Extensibility -> Extensibility -> Type) -> Extensibility -> Extensibility -> Type) (n :: Extensibility -> Extensibility -> Type) (e :: Extensibility) (x :: Extensibility). NonLocal (block n) => Graph' LabelMap block n e x -> LabelSet
- mapGraph :: forall n n' (e :: Extensibility) (x :: Extensibility). (forall (e1 :: Extensibility) (x1 :: Extensibility). n e1 x1 -> n' e1 x1) -> Graph n e x -> Graph n' e x
- mapGraphBlocks :: forall s block (n :: Extensibility -> Extensibility -> Type) block' (n' :: Extensibility -> Extensibility -> Type) (e :: Extensibility) (x :: Extensibility). (forall a b. (a -> b) -> s a -> s b) -> (forall (e1 :: Extensibility) (x1 :: Extensibility). block n e1 x1 -> block' n' e1 x1) -> Graph' s block n e x -> Graph' s block' n' e x
- revPostorderFrom :: NonLocal block => LabelMap (block C C) -> Label -> [block C C]
Documentation
type Body (s :: Type -> k) (n :: Extensibility -> Extensibility -> Type) = Body' s Block n Source #
A (possibly empty) collection of closed/closed blocks
type Graph = Graph' LabelMap Block Source #
A control-flow 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' (s :: Type -> Type) (block :: (Extensibility -> Extensibility -> Type) -> Extensibility -> Extensibility -> Type) (n :: Extensibility -> Extensibility -> Type) (e :: Extensibility) (x :: Extensibility) where Source #
Graph' is abstracted over the block type, so that we can build
graphs of annotated blocks for example (Compiler.Hoopl.Dataflow
needs this).
Constructors
| GNil :: forall (s :: Type -> Type) (block :: (Extensibility -> Extensibility -> Type) -> Extensibility -> Extensibility -> Type) (n :: Extensibility -> Extensibility -> Type). Graph' s block n 'Open 'Open | |
| GUnit :: forall (block :: (Extensibility -> Extensibility -> Type) -> Extensibility -> Extensibility -> Type) (n :: Extensibility -> Extensibility -> Type) (s :: Type -> Type). block n O O -> Graph' s block n 'Open 'Open | |
| GMany :: forall (e :: Extensibility) (block :: (Extensibility -> Extensibility -> Type) -> Extensibility -> Extensibility -> Type) (n :: Extensibility -> Extensibility -> Type) (s :: Type -> Type) (x :: Extensibility). MaybeO e (block n O C) -> Body' s block n -> MaybeO x (block n C O) -> Graph' s block n e x |
class NonLocal (thing :: Extensibility -> Extensibility -> Type) where Source #
Gives access to the anchor points for nonlocal edges as well as the edges themselves
Methods
Arguments
| :: forall (x :: Extensibility). thing C x | |
| -> Label | The label of a first node or block |
Arguments
| :: forall (e :: Extensibility). thing e C | |
| -> [Label] | Gives control-flow successors |
Instances
| NonLocal CmmNode Source # | |
Defined in GHC.Cmm.Node Methods entryLabel :: forall (x :: Extensibility). CmmNode C x -> Label Source # successors :: forall (e :: Extensibility). CmmNode e C -> [Label] Source # | |
| NonLocal n => NonLocal (Block n) Source # | |
Defined in GHC.Cmm.Dataflow.Graph Methods entryLabel :: forall (x :: Extensibility). Block n C x -> Label Source # successors :: forall (e :: Extensibility). Block n e C -> [Label] Source # | |
addBlock :: (NonLocal block, HasDebugCallStack) => block C C -> LabelMap (block C C) -> LabelMap (block C C) Source #
bodyList :: forall block (n :: Extensibility -> Extensibility -> Type). Body' LabelMap block n -> [(Label, block n C C)] Source #
bodyToBlockList :: forall (n :: Extensibility -> Extensibility -> Type). Body LabelMap n -> [Block n C C] Source #
emptyBody :: forall block (n :: Extensibility -> Extensibility -> Type). Body' LabelMap block n Source #
labelsDefined :: forall (block :: (Extensibility -> Extensibility -> Type) -> Extensibility -> Extensibility -> Type) (n :: Extensibility -> Extensibility -> Type) (e :: Extensibility) (x :: Extensibility). NonLocal (block n) => Graph' LabelMap block n e x -> LabelSet Source #
mapGraph :: forall n n' (e :: Extensibility) (x :: Extensibility). (forall (e1 :: Extensibility) (x1 :: Extensibility). n e1 x1 -> n' e1 x1) -> Graph n e x -> Graph n' e x Source #
Maps over all nodes in a graph.
mapGraphBlocks :: forall s block (n :: Extensibility -> Extensibility -> Type) block' (n' :: Extensibility -> Extensibility -> Type) (e :: Extensibility) (x :: Extensibility). (forall a b. (a -> b) -> s a -> s b) -> (forall (e1 :: Extensibility) (x1 :: Extensibility). block n e1 x1 -> block' n' e1 x1) -> Graph' s block n e x -> Graph' s block' n' e x Source #
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.
revPostorderFrom :: NonLocal block => LabelMap (block C C) -> Label -> [block C C] Source #
Returns a list of blocks reachable from the provided Labels in the reverse postorder.
This is the most important traversal over this data structure. It drops unreachable code and puts blocks in an order that is good for solving forward dataflow problems quickly. The reverse order is good for solving backward dataflow problems quickly. The forward order is also reasonably good for emitting instructions, except that it will not usually exploit Forrest Baskett's trick of eliminating the unconditional branch from a loop. For that you would need a more serious analysis, probably based on dominators, to identify loop headers.
For forward analyses we want reverse postorder visitation, consider:
A -> [B,C]
B -> D
C -> D
Postorder: [D, C, B, A] (or [D, B, C, A])
Reverse postorder: [A, B, C, D] (or [A, C, B, D])
This matters for, e.g., forward analysis, because we want to analyze *both*
B and C before we analyze D.