[<< wikibooks] ROSE Compiler Framework/liveness analysis
There are several implementations of liveness analysis in ROSE. 


== Basics ==
A classic data flow analysis performed by compilers to calculate for each program point the variables that may be potentially read before their next write, that is, the variables that are live at the exit from each program point. 

backward data flow analysis
may analysis


== Examples ==

Instructions	Live_in vars
                a
b = a + 2
		b,a // step 3: b is used (live),  a is used (live), c is killed
c = b * b
		a,c  // step 2: a,b,c , b is killed (defined), live_in ={a,c}
b = c + 1
		b,a  // step 1: start from the end of CFG here, a, b are used (live_in)
return b * a

Another one

L1: b := 3;   // live_out={b}
L2: c := 5;   // live_out ={b,c}
L3: a := b + c;
END

The set of live variables at line L2 is {b, c}, but the set of live variables at line L1 is only {b} since variable c is updated in line 2. The value of variable a is never used, so the variable is never live.

x is not live before the loop (live-in): x=a[i] redefines x before x is used, x is not live after the loop(live-out): x=10 redefines x before x is used.  int x;

  for (i=0;i<100;i++) 
  { 
    x= a[i];
    b[i]=x+1;
  }  
  x = 10;

a is live-in, and live-outint a[100];

void foo ()
{
  // a is live-in: =a[i]+1 uses a.
  for (i=0;i<100;i++) 
  { 
    a[i]=a[i]+1; 
  }  
  // A[] is be live-out, used after the loop
  .. = a[i]
  // A[] may be live-out, global variable, could be modified by other functions
}

x is live-in, but not live-out  int x=1

 for (i=0;i<100;i++) 
  { 
    // x is live-in, used before any redefinition. 
    b[i]=x+1;
     x=...
     ... =x
  }  
  // x is not live-out: redefined before any use
 x = ...  


== Implementation 2 ==
You must use the latest version of ROSE from  https://github.com/rose-compiler/rose-develop 
cd rosebuildtree/projects/CodeThorn/src   // note: must go into src directory, not to top of CodeThorn!
make analyterix
./analyterix --lv-analysis myprog.C
in rose_myprog.C the lv-analysis results are annotated as comments. 
Note:

Typing make directly under projects/CodeThorn will fail since it builds all stuff, requiring a third party library called SPOT


=== sample input and output ===
Input:

...
#define MSIZE 200
int n, m, mits;
double tol, relax = 1.0, alpha = 0.0543;
double u[MSIZE][MSIZE], f[MSIZE][MSIZE], uold[MSIZE][MSIZE];
double dx, dy;
....
void
initialize ()
{

  int i, j, xx, yy;
//  double PI = 3.1415926;

  dx = 2.0 / (n - 1); // -->dx@112:2
  dy = 2.0 / (m - 1);  //-->dy@113:2

/* Initialize initial condition and RHS */

//#pragma omp parallel for private(i,j,xx,yy)
  for (i = 0; i < n; i++)
    for (j = 0; j < m; j++)
      {
	xx = (int) (-1.0 + dx * (i - 1));	/* -1 < x < 1 */
	yy = (int) (-1.0 + dy * (j - 1));	/* -1 < y < 1 */
	u[i][j] = 0.0;
	f[i][j] = -1.0 * alpha * (1.0 - xx * xx) * (1.0 - yy * yy)
	  - 2.0 * (1.0 - xx * xx) - 2.0 * (1.0 - yy * yy);

      }

}

Output:

void initialize()
// 84 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64}
{
// 87 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64}
  int i;
// 87 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64}
// 88 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64}
  int j;
// 88 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64}
// 89 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64}
  int xx;
// 89 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64}
// 90 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64}
  int yy;
// 90 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64}
//  double PI = 3.1415926;
// -->dx@112:2
// 91 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64}
  dx = 2.0 / (n - 1);
// 91 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65}
//-->dy@113:2
// 92 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65}
  dy = 2.0 / (m - 1);
// 92 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65,dy_66}
/* Initialize initial condition and RHS */
//#pragma omp parallel for private(i,j,xx,yy)
// 93 lv-analysis-out: bot
  for (
// 94 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65,dy_66}
i = 0
// 94 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65,dy_66,i_67}
;
// 95 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65,dy_66,i_67}
i < n;
// 95 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65,dy_66,i_67}
 i++)
// 97 lv-analysis-out: bot
    for (
// 98 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65,dy_66,i_67}
j = 0
// 98 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65,dy_66,i_67,j_68}
;
// 99 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65,dy_66,i_67,j_68}
j < m;
// 99 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65,dy_66,i_67,j_68}
 j++) {
/* -1 < x < 1 */
// 102 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,uold_64,dx_65,dy_66,i_67,j_68}
      xx = ((int )(- 1.0 + dx * (i - 1)));
// 102 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,uold_64,dx_65,dy_66,i_67,j_68,xx_69}
/* -1 < y < 1 */
// 103 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,uold_64,dx_65,dy_66,i_67,j_68,xx_69}
      yy = ((int )(- 1.0 + dy * (j - 1)));
// 103 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,uold_64,dx_65,dy_66,i_67,j_68,xx_69,yy_70}
// 104 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,uold_64,dx_65,dy_66,i_67,j_68,xx_69,yy_70}
      u[i][j] = 0.0;
// 104 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,uold_64,dx_65,dy_66,i_67,j_68,xx_69,yy_70}
// 105 lv-analysis-out: {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,uold_64,dx_65,dy_66,i_67,j_68,xx_69,yy_70}
      f[i][j] = - 1.0 * alpha * (1.0 - (xx * xx)) * (1.0 - (yy * yy)) - 2.0 * (1.0 - (xx * xx)) - 2.0 * (1.0 - (yy * yy));
// 105 lv-analysis-in : {n_56,m_57,mits_58,tol_59,relax_60,alpha_61,u_62,f_63,uold_64,dx_65,dy_66,i_67,j_68}
    }                                                                                                                                      
// 97 lv-analysis-in : bot                                                                                                                 
// 93 lv-analysis-in : bot                                                                                                                 
}                                                                                        


=== relevant source files ===
src/midend/abstractLayer/Labeler.h /.C // AST Node with labels
projects/CodeThorn/src/LVLattice.h // liveness analysis lattice


== Implementation 1 ==
This is being phased out in favour of newer version


=== SageInterface functions ===
Two functions are provided to call the analysis and obtain live variables for loops.

// 	Call liveness analysis on an entire project. 
LivenessAnalysis * 	SageInterface::call_liveness_analysis (SgProject *project, bool debug=false)

//	get liveIn and liveOut variables for a for loop from liveness analysis result liv. 
void 	getLiveVariables (LivenessAnalysis *liv, SgForStatement *loop, std::set< SgInitializedName * > &liveIns, std::set< SgInitializedName * > &liveOuts)

Some internals if you want to expand it to support any scope statements

//!Get liveIn and liveOut variables for a for loop
void SageInterface::getLiveVariables(LivenessAnalysis * liv, SgForStatement* loop, std::set& liveIns, std::set & liveOuts)
{
  ROSE_ASSERT(liv != NULL);
  ROSE_ASSERT(loop != NULL);
  SgForStatement *forstmt = loop;
  std::vector liveIns0, liveOuts0; // store the original one

  // Jeremiah's hidden constructor parameter value '2' to grab the node for forStmt's 
  // Several CFG nodes are used for the same SgForStatement, only one of the is needed.
  // We have to check the full control flow graph to find all SgForStatement's nodes,
  // check the index numbers from 0 , find the one with two out edges (true, false)
  // The CFG node should have a caption like"  @ 8: 1",
  // which means this is a CFG node for a for statement at source line 8, with an index 1.
  // For SgForStatement, there are 5 cfg nodes, 0 and 4 are for begin and end CFG nodes
  // 1: after init statement, 2: after test expression (the remaining one after filtering), 3: before increment  
  CFGNode cfgnode(forstmt,2);
  FilteredCFGNode filternode= FilteredCFGNode (cfgnode);
  // This one does not return the one we want even its getNode returns the
  // right for statement
  //FilteredCFGNode filternode= FilteredCFGNode (forstmt->cfgForBeginning());
  ROSE_ASSERT(filternode.getNode()==forstmt);

  // Check out edges
  vector > out_edges = filternode.outEdges();
  ROSE_ASSERT(out_edges.size()==2);
  vector >::iterator iter= out_edges.begin();

  for (; iter!=out_edges.end();iter++)
  {
    FilteredCFGEdge < IsDFAFilter > edge= *iter;
    //SgForStatement should have two outgoing edges based on the loop condition
    // one true(going into the loop body) and one false (going out the loop)
    //x. Live-in (loop) = live-in (first-stmt-in-loop)
    if (edge.condition()==eckTrue)
    {
      SgNode* firstnode= edge.target().getNode();
      liveIns0 = liv->getIn(firstnode);
      // cout<<"Live-in variables for loop:"<::iterator iter = liveIns0.begin();
          iter!=liveIns0.end(); iter++)
      {
        // SgInitializedName* name = *iter;
        liveIns.insert(*iter);
        //           cout<< name->get_qualified_name().getString()<getIn(firstnode);
      //  cout<<"Live-out variables for loop:"<::iterator iter = liveOuts0.begin();
          iter!=liveOuts0.end(); iter++)
      {
        // SgInitializedName* name = *iter;
        //  cout<< name->get_qualified_name().getString()<run(debug);

 LivenessAnalysis* liv = new LivenessAnalysis(debug,(DefUseAnalysis*)defuse);

  std::vector  > dfaFunctions;

  NodeQuerySynthesizedAttributeType vars = NodeQuery::querySubTree(project, V_SgFunctionDefinition);
  NodeQuerySynthesizedAttributeType::const_iterator i = vars.begin();
  bool abortme=false;
  for (; i!=vars.end();++i) {
    SgFunctionDefinition* func = isSgFunctionDefinition(*i);
    std::string name = func->class_name();
    string funcName = func->get_declaration()->get_qualified_name().str();

    // run liveness analysis on all function bodies. 
    FilteredCFGNode  rem_source = liv->run(func,abortme);
    if (abortme)
      break;
    if (funcName!=funcParamName) {
      if (debug)
        cerr << "    .. skipping live analysis check for func : " << funcName << endl;
      continue;
    }
    if (rem_source.getNode()!=NULL)
      dfaFunctions.push_back(rem_source);

  std::ofstream f2("var.dot");
  dfaToDot(f2, string("var"), dfaFunctions, (DefUseAnalysis*)defuse, liv);
  f2.close();

// internals of returned CFG node after run()

       // add this node to worklist and work through the outgoing edges
        FilteredCFGNode source = FilteredCFGNode (
                        funcDecl->cfgForEnd());
        if (forwardAlgo)
                source = FilteredCFGNode (funcDecl->cfgForBeginning());

        //CFGNode cmpSrc = CFGNode(funcDecl->cfgForEnd());
        FilteredCFGNode rem_source = source;


=== dot graph output ===
sourcetree/src/midend/programAnalysis/defUseAnalysis
dfaToDot.h dfaToDot.cpp
Two steps: 

collect all CFG nodes into a multimap:  template    void DfaToDotImpl::explore(NodeT n)
print out nodes and edges:  template  void DfaToDotImpl::processNodes(SgNode*)
TODO: 

write to dot graph does not work properly in the middle