# ROSE Compiler Framework/Generic Dataflow Framework
## Introduction

As the ROSE project goes on, we have collected quite some versions of dataflow analysis. It is painful to maintain and use them as they
* duplicate the iterative fixed-point algorithm,
* scatter in different directories,
* use different representations for results, and
* has different level of maturity and robustness.
An ongoing effort is to consolidate all dataflow analysis work within a single framework.
Quick facts
* original author: Greg Bronevetsky
* code gatekeeper: Chunhua Liao
* Documentation:
** Chapter 18 Generic Dataflow Analysis Framework, of the ROSE tutorial pdf, git commit
** This wikibook page
* source codes: files under ./src/midend/programAnalysis/genericDataflow
* tests: tests/roseTests/programAnalysisTests/generalDataFlowAnalysisTests

## Implemented analysis

List
* Constant Propagation
* dominator analysis: dominatorAnalysis.h dominatorAnalysis.C
* livedead variable analysis, or liveness analysis: liveDeadVarAnalysis.h liveDeadVarAnalysis.C
* Pointer Analysis

## Function, nodeState and FunctionState

Function and nodeState are two required parameters to run data flow analysis:
They are stored together inside FunctionState //functionState.h
functionState.h
genericDataflow/cfgUtils/CallGraphTraverse.h

### function

An abstraction of functions, internally connected to SgFunctionDeclaration *decl
declared in ./src/midend/programAnalysis/genericDataflow/cfgUtils/CallGraphTraverse.h
constructors:
* Function::Function(string name) based on function name
* Function::Function(SgFunctionDeclaration* sample) // core constructor
* Function::Function(SgFunctionDefinition* sample)
CGFunction* cgFunc; // call graph function
Function func(cgFunc);

### NodeFact

any information related to a CFG node.
* It has no dataflow 's IN/OUT concept
* not meant to evolve during the dataflow analysis

### NodeState

Store information about multiple analyses and their corresponding lattices, for a given node (CFG node ??)
./src/midend/programAnalysis/genericDataflow/state/nodeState.h
It also provide static functions to
* initialize NodeState for all DataflowNode
* to retrieve NodeState for a given DataflowNode

### FunctionState

./src/midend/programAnalysis/genericDataflow/state/functionState.h
A pair of Function and NodeState.
* it provides static functions to initialize all FunctionState And retrieve FunctionState
FunctionState* fs = new FunctionState(func); // empty From FuntionState to NodeState
example: retrieve the liveness analysis's IN lattice
void getAllLiveVarsAt(LiveDeadVarsAnalysis* ldva, const NodeState& state, set<varID>& vars, string indent)
* LiveVarsLattice* liveLAbove = dynamic_cast<LiveVarsLattice*>(*(state.getLatticeAbove(ldva).begin));

## Lattices

Caveat: lattice vs. lattice value
* A lattice by definition is a set of values. However, an instance of lattice type in Generic dataflow framework is used to represent an individual value within a lattice also. Sorry for this confusing. We welcome suggestions to fix this.

### Basics

See more at ROSE Compiler Framework/Lattice
Store the data flow analysis information attached to CFG nodes.
Fundamental operations:
* what to store: lattice value set, bottom, up , and anything in between
* initialization: LiveDeadVarsAnalysis::genInitState
* creation: transfer function
* meet operation: a member function of the lattice
Example
* liveness analysis: the live variable set at the entry point of a CFG node:
* constant propagation: lattice values from no information (bottom) -> unknown --> constant --> too much information (conflicting constant values, top),

### below/above vs IN/OUT

The concept is based on the original CFG flow direction
* above: the incoming edge direction
* below: the outcoming edge direction
IN and OUT depends on the direction of the problem, forward vs. backward
* forward direction: IN == above lattice, OUT = below lattice
* backward direction: IN == below lattice, OUT = above lattice

### Common Utility Lattices

the framework provides some pre-defined lattices ready for use.
lattice.h/latticeFull.h
* BoolAndLattice

### LiveVarsLattice
## Transfer Function

basics: Data_flow_analysis#flow.2Ftransfer_function
* IN = sum of OUT (predecessors)
* OUT = GEN + (IN - KILL)
The impact of program constructs on the current lattices (how to change the current lattices).
* lattices: stores IN and OUT information
* additional data members are necessary to store GEN and KILL set inside the transfer function.
class hierarchy:

### LiveDead Variable

Functions to convert program point to Generator and KILL set. For liveness analysis
* Kill (s) = {variables being defined in s}: //
* Gen (s) = {variables being used in s}
OUT = IN -KILL + GEN
* OUT is initialized to be IN set,
* transfer function will apply -KILL + GEN

### Call Stack
## Control flow graph and call graph

The generic dataflow framework works on virtual control flow graph in ROSE

### Filtered Virtual CFG

The raw virtual CFG may not be desirable for all kinds of analyses since it can have too many administrative nodes which are not relevant to a problem.
So the framework provides a filter parameter to the Analysis class. A default filter will be used unless you specify your own filter.

## Analysis Driver

Key function:
Basic tasks: run the analysis by
* initialize data flow state: lattices and other information
* walk the CFG : find descendants from a current node
* call transfer function

### Class Hierarchy

* Analysis -> IntraProceduralAnalysis -> IntraProceduralDataflow -> IntraUnitDataflow --> IntraUniDirectionalDataflow (INTERESTING level)-> IntraBWDataflow -> LiveDeadVarsAnalysis
foward intra-procedural data flow analysis: e.g. reaching definition
* class IntraFWDataflow : public IntraUniDirectionalDataflow

### Initialization: InitDataflowState

Used to initialized the lattices/facts for CFG nodes. It is an analysis by itself. unstructured pass

### worklist

list of CFG nodes, accessed through an iterator interface
auto_ptr<VirtualCFG::dataflow> workList(getInitialWorklist(func, firstVisit, analyzeDueToCallers, calleesUpdated, fState));
Implemented in derived classes:
* VirtualCFG::dataflow* IntraFWDataflow::getInitialWorklist
* VirtualCFG::dataflow* IntraBWDataflow::getInitialWorklist

### apply transfer function

b is a basic block in CFG
* ${\rm {IN}}[b]=\bigcup _{p\in pred[b]}{\rm {OUT}}[p]$ // information goes into b is the union/join of information comes out of all predecessor nodes of b
* ${OUT}[b]={\rm {GEN}}[b]\cup ({\rm {IN}}[b]-{\rm {KILL}}[b])$ // information goes out out S is the information generated by b minus information killed by b. This is the transfer function operating on b!!

### propagate state to next (meetUpdate)

This is prove to be essential to propagate information along the path. Cannot commenting it out!!
??? not sure about the difference between this step and the step before (Meet Before / Meet After)
meetUpdate is called here also

### live dead variable

Backward Intra-Procedural Dataflow Analysis: e.g. liveness analysis ( use --> backward --> defined)
* class IntraBWDataflow : public IntraUniDirectionalDataflow

## Inter-procedural analysis

Key: transfer function that is applied to call sites to perform the appropriate state transfers across function boundaries.

### InterProceduralDataflow

TODO: begin and end func definition issue is mentioned inside of this

### simplest form:unstructured

Simplest form: No transfer action at call sites at all

### ContextInsensitiveInterProceduralDataflow

TODO

## How to use one analysis
### Call directly

Direct call: Runs the intra-procedural analysis on the given function and returns true if the function's NodeState gets modified as a result and false otherwise state - the function's NodeState
* bool IntraUniDirectionalDataflow::runAnalysis(const Function& func, NodeState* state, bool analyzeDueToCallers, std::set<Function> calleesUpdated);
* direct call with a simpler parameter list : not feasible, all intra procedural analysis has to have an inter procedural analysis set interally!

### Through inter-procedural analysis

Invoke a simple intra-procedural analysis through the unstructured pass inter-procedural data flow class

### Retrieve lattices

Sample code:

## Testing

It is essential to have a way to test the analysis results are correct.
We currently use a primitive way to test the correctness of analysis: comparing pragma and lattice string output
Two examples translators testing analysis correctness(comparing pragma and lattice string output):
* https://github.com/rose-compiler/rose/blob/master/tests/roseTests/programAnalysisTests/generalDataFlowAnalysisTests/liveDeadVarAnalysisTest.C
* https://github.com/rose-compiler/rose/blob/master/tests/roseTests/programAnalysisTests/generalDataFlowAnalysisTests/constantPropagationTest.C
An example test input file for liveness analysis's correctness
* https://github.com/rose-compiler/rose/blob/master/tests/roseTests/programAnalysisTests/generalDataFlowAnalysisTests/test5.C

## How to debug
### Trace the analysis

Turn it on
check the web page dump using a browser
How to read the trace file: start from the beginning: information is ordered based on the CFG nodes visited. The order could be forward or backward order. Check if the order is correct first, then for each node visited

### Dump cfg dot graph with lattices

A class analysisStatesToDot is provided generate a CFG dot graph with lattices information.

### Example use
## TODO

* Hard to use the generated lattices since many temporary expression objects are generated in lattices. But often users do not care about them (constant propagation, pointer analysis)
** to see the problem: go to [build64/tests/roseTests/programAnalysisTests/generalDataFlowAnalysisTests]
** run make check
** see the dot graph dump of an analysis : run.sh test_ptr4.C_main_0x2b41e651c038_cfg.dot