Language.Fortran.Analysis.DataFlow

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

Documentation

dominators :: BBGr a -> DomMap

Compute dominators of each bblock in the graph. Node A dominates node B when all paths from the start node (0) 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

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.

type DomMap = IntMap IntSet

DomMap : node -> dominators of node

type IDomMap = IntMap Int

IDomMap : node -> immediate dominator of node

postOrder :: OrderF a

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

revPostOrder :: OrderF a

Reversed postordering.

preOrder :: OrderF a

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

revPreOrder :: OrderF a

Reversed preordering.

type OrderF a = BBGr a -> [Node]

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

dataFlowSolver

Arguments

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

Show some information about dataflow analyses.

type InOut t = (t, t)

InOut : (dataflow into the bblock, dataflow out of the bblock)

type InOutMap t = IntMap (InOut t)

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

type InF t = Node -> t

InF, a function that returns the in-dataflow for a given node

type OutF t = Node -> t

OutF, a function that returns the out-dataflow for a given node

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

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

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

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

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

duMapToUdMap :: DUMap -> UDMap

Invert the DUMap into a UDMap

type UDMap = IntMap IntSet

UDMap : use -> { definition }

type DUMap = IntMap IntSet

DUMap : definition -> { use }

genFlowsToGraph

Arguments

:: 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)) ()

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

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

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

type VarFlowsMap = Map Name (Set Name)

Represent "flows" between variables

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

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

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

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.

type DefMap = Map Name IntSet

DefMap : variable name -> { AST-block label }

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

Create a call map showing the structure of the program.

type CallMap = Map ProgramUnitName (Set Name)

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

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

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

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]

The strongly connected component containing a given node.

type BackEdgeMap = IntMap Node

BackEdgeMap : node -> node

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

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

LoopNodeMap : node -> { node }

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

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)

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

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

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

type InductionVarMapByASTBlock = IntMap (Set Name)

InductionVarMapByASTBlock : AST-block label -> { name }

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

Compute the set of nodes with no predecessors.

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

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

type DerivedInductionMap = IntMap InductionExpr

data InductionExpr

Constructors

IETop

IELinear Name Int Int

IEBottom

Instances

Eq InductionExpr

Methods

(==) :: InductionExpr -> InductionExpr -> Bool

(/=) :: InductionExpr -> InductionExpr -> Bool

Data InductionExpr

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> InductionExpr -> c InductionExpr

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c InductionExpr

toConstr :: InductionExpr -> Constr

dataTypeOf :: InductionExpr -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c InductionExpr)

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c InductionExpr)

gmapT :: (forall b. Data b => b -> b) -> InductionExpr -> InductionExpr

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> InductionExpr -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> InductionExpr -> r

gmapQ :: (forall d. Data d => d -> u) -> InductionExpr -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> InductionExpr -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> InductionExpr -> m InductionExpr

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> InductionExpr -> m InductionExpr

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> InductionExpr -> m InductionExpr

Ord InductionExpr

Methods

compare :: InductionExpr -> InductionExpr -> Ordering

(<) :: InductionExpr -> InductionExpr -> Bool

(<=) :: InductionExpr -> InductionExpr -> Bool

(>) :: InductionExpr -> InductionExpr -> Bool

(>=) :: InductionExpr -> InductionExpr -> Bool

max :: InductionExpr -> InductionExpr -> InductionExpr

min :: InductionExpr -> InductionExpr -> InductionExpr

Show InductionExpr

Methods

showsPrec :: Int -> InductionExpr -> ShowS

show :: InductionExpr -> String

showList :: [InductionExpr] -> ShowS

Generic InductionExpr

Associated Types

type Rep InductionExpr :: * -> *

Methods

from :: InductionExpr -> Rep InductionExpr x

to :: Rep InductionExpr x -> InductionExpr

type Rep InductionExpr

type Rep InductionExpr = D1 (MetaData "InductionExpr" "Language.Fortran.Analysis.DataFlow" "fortran-src-0.1.0.4-9s32whVEBRK7KGD1RBNMcM" False) ((:+:) (C1 (MetaCons "IETop" PrefixI False) U1) ((:+:) (C1 (MetaCons "IELinear" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Name)) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Int)) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Int))))) (C1 (MetaCons "IEBottom" PrefixI False) U1)))