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

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 = BBNodeMap BBNodeSet

DomMap : node -> dominators of node

type IDomMap = BBNodeMap BBNode

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

:: (NFData t, 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. Forces evaluation of intermediate data structures at each step.

type InOut t = (t, t)

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

type InOutMap t = BBNodeMap (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 ASTBlockNodeSet

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 ASTBlockNodeSet -> 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 ASTBlockNodeSet -> 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 = ASTBlockNodeMap ASTBlockNodeSet

UDMap : use -> { definition }

type DUMap = ASTBlockNodeMap ASTBlockNodeSet

DUMap : definition -> { use }

genFlowsToGraph

Arguments

:: Data a

=> BlockMap a

-> DefMap

-> BBGr (Analysis a)

-> InOutMap ASTBlockNodeSet

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

data Constant

Information about potential / actual constant expressions.

Constructors

ConstInt Integer

interpreted integer

ConstUninterpInt String

uninterpreted integer

ConstUninterpReal String

uninterpreted real

ConstBinary BinaryOp Constant Constant

binary operation on potential constants

ConstUnary UnaryOp Constant

unary operation on potential constants

Instances

Eq Constant

Defined in Language.Fortran.Analysis

Methods

(==) :: Constant -> Constant -> Bool

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

Data Constant

Defined in Language.Fortran.Analysis

Methods

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

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

toConstr :: Constant -> Constr

dataTypeOf :: Constant -> DataType

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

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

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

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

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

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

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

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

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

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

Ord Constant

Defined in Language.Fortran.Analysis

Methods

compare :: Constant -> Constant -> Ordering

(<) :: Constant -> Constant -> Bool

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

(>) :: Constant -> Constant -> Bool

(>=) :: Constant -> Constant -> Bool

max :: Constant -> Constant -> Constant

min :: Constant -> Constant -> Constant

Show Constant

Defined in Language.Fortran.Analysis

Methods

showsPrec :: Int -> Constant -> ShowS

show :: Constant -> String

showList :: [Constant] -> ShowS

Generic Constant

Defined in Language.Fortran.Analysis

Associated Types

type Rep Constant :: Type -> Type

Methods

from :: Constant -> Rep Constant x

to :: Rep Constant x -> Constant

Binary Constant

Defined in Language.Fortran.Analysis

Methods

put :: Constant -> Put

get :: Get Constant

putList :: [Constant] -> Put

Out Constant

Defined in Language.Fortran.Analysis

Methods

docPrec :: Int -> Constant -> Doc

doc :: Constant -> Doc

docList :: [Constant] -> Doc

type Rep Constant

Defined in Language.Fortran.Analysis

type Rep Constant = D1 ('MetaData "Constant" "Language.Fortran.Analysis" "fortran-src-0.4.2-inplace" 'False) ((C1 ('MetaCons "ConstInt" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Integer)) :+: C1 ('MetaCons "ConstUninterpInt" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 String))) :+: (C1 ('MetaCons "ConstUninterpReal" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 String)) :+: (C1 ('MetaCons "ConstBinary" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 BinaryOp) :*: (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Constant) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Constant))) :+: C1 ('MetaCons "ConstUnary" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 UnaryOp) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Constant)))))

type ParameterVarMap = Map Name Constant

The map of all parameter variables and their corresponding values

type ConstExpMap = ASTExprNodeMap (Maybe Constant)

The map of all expressions and whether they are undecided (not present in map), a constant value (Just Constant), or probably not constant (Nothing).

genConstExpMap :: forall a. Data a => ProgramFile (Analysis a) -> ConstExpMap

Generate a constant-expression map with information about the expressions (identified by insLabel numbering) in the ProgramFile pf (must have analysis initiated & basic blocks generated) .

analyseConstExps :: forall a. Data a => ProgramFile (Analysis a) -> ProgramFile (Analysis a)

Get constant-expression information and put it into the AST analysis annotation. Must occur after analyseBBlocks.

analyseParameterVars :: forall a. Data a => ParameterVarMap -> ProgramFile (Analysis a) -> ProgramFile (Analysis a)

Annotate AST with constant-expression information based on given ParameterVarMap.

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 = ASTBlockNodeMap (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 ASTBlockNodeSet

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 -> [BBNodeSet]

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 = BBNodeMap BBNode

BackEdgeMap : bblock node -> bblock 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 = BBNodeMap BBNodeSet

LoopNodeMap : bblock node -> { bblock 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 = BBNodeMap (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 = ASTBlockNodeMap (Set Name)

InductionVarMapByASTBlock : AST-block label -> { name }

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 = ASTExprNodeMap InductionExpr

data InductionExpr

Constructors

IETop

IELinear !Name !Int !Int

IEBottom

Instances

Eq InductionExpr

Defined in Language.Fortran.Analysis.DataFlow

Methods

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

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

Data InductionExpr

Defined in Language.Fortran.Analysis.DataFlow

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 :: forall r r'. (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

Defined in Language.Fortran.Analysis.DataFlow

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

Defined in Language.Fortran.Analysis.DataFlow

Methods

showsPrec :: Int -> InductionExpr -> ShowS

show :: InductionExpr -> String

showList :: [InductionExpr] -> ShowS

Generic InductionExpr

Defined in Language.Fortran.Analysis.DataFlow

Associated Types

type Rep InductionExpr :: Type -> Type

Methods

from :: InductionExpr -> Rep InductionExpr x

to :: Rep InductionExpr x -> InductionExpr

NFData InductionExpr

Defined in Language.Fortran.Analysis.DataFlow

Methods

rnf :: InductionExpr -> ()

type Rep InductionExpr

Defined in Language.Fortran.Analysis.DataFlow

type Rep InductionExpr = D1 ('MetaData "InductionExpr" "Language.Fortran.Analysis.DataFlow" "fortran-src-0.4.2-inplace" 'False) (C1 ('MetaCons "IETop" 'PrefixI 'False) (U1 :: Type -> Type) :+: (C1 ('MetaCons "IELinear" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Name) :*: (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Int) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 Int))) :+: C1 ('MetaCons "IEBottom" 'PrefixI 'False) (U1 :: Type -> Type)))

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

Show some information about dataflow analyses.

showFlowsDOT :: (Data a, Out a, Show a) => ProgramFile (Analysis a) -> BBGr (Analysis a) -> ASTBlockNode -> Bool -> String

Outputs a DOT-formatted graph showing flow-to data starting at the given AST-Block node in the given Basic Block graph.

type BBNodeMap = IntMap

type BBNodeSet = IntSet

type ASTBlockNodeMap = IntMap

type ASTBlockNodeSet = IntSet

type ASTExprNodeMap = IntMap

type ASTExprNodeSet = IntSet