Safe Haskell | None |
---|---|

Language | Haskell2010 |

Dataflow analysis to be applied once basic block analysis is complete.

- dominators :: BBGr a -> DomMap
- iDominators :: BBGr a -> IDomMap
- type DomMap = IntMap IntSet
- type IDomMap = IntMap Int
- postOrder :: OrderF a
- revPostOrder :: OrderF a
- preOrder :: OrderF a
- revPreOrder :: OrderF a
- type OrderF a = BBGr a -> [Node]
- dataFlowSolver :: Ord t => BBGr a -> (Node -> InOut t) -> OrderF a -> (OutF t -> InF t) -> (InF t -> OutF t) -> InOutMap t
- showDataFlow :: (Data a, Out a, Show a) => ProgramFile (Analysis a) -> String
- type InOut t = (t, t)
- type InOutMap t = IntMap (InOut t)
- type InF t = Node -> t
- type OutF t = Node -> t
- liveVariableAnalysis :: Data a => BBGr (Analysis a) -> InOutMap (Set Name)
- reachingDefinitions :: Data a => DefMap -> BBGr (Analysis a) -> InOutMap IntSet
- genUDMap :: Data a => BlockMap a -> DefMap -> BBGr (Analysis a) -> InOutMap IntSet -> UDMap
- genDUMap :: Data a => BlockMap a -> DefMap -> BBGr (Analysis a) -> InOutMap IntSet -> DUMap
- duMapToUdMap :: DUMap -> UDMap
- type UDMap = IntMap IntSet
- type DUMap = IntMap IntSet
- genFlowsToGraph :: Data a => BlockMap a -> DefMap -> BBGr (Analysis a) -> InOutMap IntSet -> FlowsGraph a
- type FlowsGraph a = Gr (Block (Analysis a)) ()
- genVarFlowsToMap :: Data a => DefMap -> FlowsGraph a -> VarFlowsMap
- type VarFlowsMap = Map Name (Set Name)
- genBlockMap :: Data a => ProgramFile (Analysis a) -> BlockMap a
- genDefMap :: Data a => BlockMap a -> DefMap
- type BlockMap a = IntMap (Block (Analysis a))
- type DefMap = Map Name IntSet
- genCallMap :: Data a => ProgramFile (Analysis a) -> CallMap
- type CallMap = Map ProgramUnitName (Set Name)
- loopNodes :: Graph gr => BackEdgeMap -> gr a b -> [IntSet]
- genBackEdgeMap :: Graph gr => DomMap -> gr a b -> BackEdgeMap
- sccWith :: Graph gr => Node -> gr a b -> [Node]
- type BackEdgeMap = IntMap Node
- genLoopNodeMap :: Graph gr => BackEdgeMap -> gr a b -> LoopNodeMap
- type LoopNodeMap = IntMap IntSet
- genInductionVarMap :: Data a => BackEdgeMap -> BBGr (Analysis a) -> InductionVarMap
- type InductionVarMap = IntMap (Set Name)
- genInductionVarMapByASTBlock :: forall a. Data a => BackEdgeMap -> BBGr (Analysis a) -> InductionVarMapByASTBlock
- type InductionVarMapByASTBlock = IntMap (Set Name)
- noPredNodes :: Graph g => g a b -> [Node]
- genDerivedInductionMap :: forall a. Data a => BackEdgeMap -> BBGr (Analysis a) -> DerivedInductionMap
- type DerivedInductionMap = IntMap InductionExpr
- data InductionExpr

# Documentation

dominators :: BBGr a -> DomMap Source #

Compute dominators of each bblock in the graph. Node A dominates node B when all paths from the start node of that program unit must pass through node A in order to reach node B. That will be represented as the relation (B, [A, ...]) in the DomMap.

iDominators :: BBGr a -> IDomMap Source #

Compute the immediate dominator of each bblock in the graph. The
immediate dominator is, in a sense, the `closest`

dominator of a
node. Given nodes A and B, you can say that node A is immediately
dominated by node B if there does not exist any node C such that:
node A dominates node C and node C dominates node B.

postOrder :: OrderF a Source #

The postordering of a graph outputs the label after traversal of children.

revPostOrder :: OrderF a Source #

Reversed postordering.

The preordering of a graph outputs the label before traversal of children.

revPreOrder :: OrderF a Source #

Reversed preordering.

type OrderF a = BBGr a -> [Node] Source #

An OrderF is a function from graph to a specific ordering of nodes.

:: Ord t | |

=> BBGr a | basic block graph |

-> (Node -> InOut t) | initialisation for in and out dataflows |

-> OrderF a | ordering function |

-> (OutF t -> InF t) | compute the in-flow given an out-flow function |

-> (InF t -> OutF t) | compute the out-flow given an in-flow function |

-> InOutMap t | final dataflow for each node |

Apply the iterative dataflow analysis method.

showDataFlow :: (Data a, Out a, Show a) => ProgramFile (Analysis a) -> String Source #

Show some information about dataflow analyses.

type InOutMap t = IntMap (InOut t) Source #

InOutMap : node -> (dataflow into node, dataflow out of node)

liveVariableAnalysis :: Data a => BBGr (Analysis a) -> InOutMap (Set Name) Source #

Dataflow analysis for live variables given basic block graph. Muchnick, p. 445: A variable is "live" at a particular program point if there is a path to the exit along which its value may be used before it is redefined. It is "dead" if there is no such path.

reachingDefinitions :: Data a => DefMap -> BBGr (Analysis a) -> InOutMap IntSet Source #

Reaching definitions dataflow analysis. Reaching definitions are the set of variable-defining AST-block labels that may reach a program point. Suppose AST-block with label A defines a variable named v. Label A may reach another program point labeled P if there is at least one program path from label A to label P that does not redefine variable v.

genUDMap :: Data a => BlockMap a -> DefMap -> BBGr (Analysis a) -> InOutMap IntSet -> UDMap Source #

use-def map: map AST-block labels of variable-using AST-blocks to the AST-blocks that define those variables.

genDUMap :: Data a => BlockMap a -> DefMap -> BBGr (Analysis a) -> InOutMap IntSet -> DUMap Source #

def-use map: map AST-block labels of defining AST-blocks to the AST-blocks that may use the definition.

duMapToUdMap :: DUMap -> UDMap Source #

Invert the DUMap into a UDMap

:: Data a | |

=> BlockMap a | |

-> DefMap | |

-> BBGr (Analysis a) | |

-> InOutMap IntSet | result of reaching definitions |

-> FlowsGraph a |

Flows-To analysis. Represent def-use map as a graph.

type FlowsGraph a = Gr (Block (Analysis a)) () Source #

FlowsGraph : nodes as AST-block (numbered by label), edges showing which definitions contribute to which uses.

genVarFlowsToMap :: Data a => DefMap -> FlowsGraph a -> VarFlowsMap Source #

Create a map (A -> Bs) where A "flows" or contributes towards the variables Bs.

genBlockMap :: Data a => ProgramFile (Analysis a) -> BlockMap a Source #

Build a BlockMap from the AST. This can only be performed after analyseBasicBlocks has operated, created basic blocks, and labeled all of the AST-blocks with unique numbers.

genDefMap :: Data a => BlockMap a -> DefMap Source #

Build a DefMap from the BlockMap. This allows us to quickly look up the AST-block labels that wrote into the given variable.

type BlockMap a = IntMap (Block (Analysis a)) Source #

BlockMap : AST-block label -> AST-block Each AST-block has been given a unique number label during analysis of basic blocks. The purpose of this map is to provide the ability to lookup AST-blocks by label.

genCallMap :: Data a => ProgramFile (Analysis a) -> CallMap Source #

Create a call map showing the structure of the program.

type CallMap = Map ProgramUnitName (Set Name) Source #

CallMap : program unit name -> { name of function or subroutine }

loopNodes :: Graph gr => BackEdgeMap -> gr a b -> [IntSet] Source #

For each loop in the program, find out which bblock nodes are
part of the loop by looking through the backedges (m, n) where n is
considered the 'loop-header', delete n from the map, and then do a
reverse-depth-first traversal starting from m to find all the nodes
of interest. Intersect this with the strongly-connected component
containing m, in case of `improper`

graphs with weird control
transfers.

genBackEdgeMap :: Graph gr => DomMap -> gr a b -> BackEdgeMap Source #

Find the edges that 'loop back' in the graph; ones where the target node dominates the source node. If the backedges are viewed as (m -> n) then n is considered the 'loop-header'

sccWith :: Graph gr => Node -> gr a b -> [Node] Source #

The strongly connected component containing a given node.

type BackEdgeMap = IntMap Node Source #

BackEdgeMap : node -> node

genLoopNodeMap :: Graph gr => BackEdgeMap -> gr a b -> LoopNodeMap Source #

Similar to loopNodes except it creates a map from loop-header to the set of loop nodes, for each loop-header.

type LoopNodeMap = IntMap IntSet Source #

LoopNodeMap : node -> { node }

genInductionVarMap :: Data a => BackEdgeMap -> BBGr (Analysis a) -> InductionVarMap Source #

For each loop in the program, figure out the names of the induction variables: the variables that are used to represent the current iteration of the loop.

type InductionVarMap = IntMap (Set Name) Source #

Map of loop header nodes to the induction variables within that loop.

genInductionVarMapByASTBlock :: forall a. Data a => BackEdgeMap -> BBGr (Analysis a) -> InductionVarMapByASTBlock Source #

Generate an induction variable map that is indexed by the labels on AST-blocks within those loops.

type InductionVarMapByASTBlock = IntMap (Set Name) Source #

InductionVarMapByASTBlock : AST-block label -> { name }

noPredNodes :: Graph g => g a b -> [Node] Source #

Compute the set of nodes with no predecessors.

genDerivedInductionMap :: forall a. Data a => BackEdgeMap -> BBGr (Analysis a) -> DerivedInductionMap Source #

For every expression in a loop, try to derive its relationship to a basic induction variable.