Documentation

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.

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.

DomMap : node -> dominators of node

IDomMap : node -> immediate dominator of node

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

Reversed postordering.

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

Reversed preordering.

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

Apply the iterative dataflow analysis method.

Show some information about dataflow analyses.

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

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

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

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

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.

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.

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

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

Invert the DUMap into a UDMap

UDMap : use -> { definition }

DUMap : definition -> { use }

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

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

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

Represent "flows" between variables

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.

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

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.

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

Create a call map showing the structure of the program.

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

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.

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'

The strongly connected component containing a given node.

BackEdgeMap : node -> node

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

LoopNodeMap : node -> { node }

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.

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

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

InductionVarMapByASTBlock : AST-block label -> { name }

Compute the set of nodes with no predecessors.

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