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

int 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<SgInitializedName*>& liveIns, std::set<SgIn
itializedName*> & liveOuts)
{
  ROSE_ASSERT(liv != NULL);
  ROSE_ASSERT(loop != NULL);
  SgForStatement *forstmt = loop;
  std::vector<SgInitializedName*> 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" <SgForStatement> @ 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<IsDFAFilter> filternode= FilteredCFGNode<IsDFAFilter> (cfgnode);
  // This one does not return the one we want even its getNode returns the
  // right for statement
  //FilteredCFGNode<IsDFAFilter> filternode= FilteredCFGNode<IsDFAFilter> (forstmt->cfgForBeginning());
  ROSE_ASSERT(filternode.getNode()==forstmt);

  // Check out edges
  vector<FilteredCFGEdge < IsDFAFilter > > out_edges = filternode.outEdges();
  ROSE_ASSERT(out_edges.size()==2);
  vector<FilteredCFGEdge < IsDFAFilter > >::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:"<<endl;
      for (std::vector<SgInitializedName*>::iterator iter = liveIns0.begin();
          iter!=liveIns0.end(); iter++)
      {
        // SgInitializedName* name = *iter;
        liveIns.insert(*iter);
        //           cout<< name->get_qualified_name().getString()<<endl;
      }
    }
    //x. live-out(loop) = live-in (first-stmt-after-loop)
    else if (edge.condition()==eckFalse)
    {
      SgNode* firstnode= edge.target().getNode();
      liveOuts0 = liv->getIn(firstnode);
      //  cout<<"Live-out variables for loop:"<<endl;
      for (std::vector<SgInitializedName*>::iterator iter = liveOuts0.begin();
          iter!=liveOuts0.end(); iter++)
      {
        // SgInitializedName* name = *iter;
        //  cout<< name->get_qualified_name().getString()<<endl;
        liveOuts.insert(*iter);
      }
    }
    else
    {
      cerr<<"Unexpected CFG out edge type for SgForStmt!"<<endl;
      ROSE_ASSERT(false);
    }
  } // end for (edges)

}

source files

src/midend/programAnalysis/defUseAnaysis/LivenessAnalysis.cpp

/******************************************
 * Algorithm used:
 * for all n, in[n] = out[n] = 0
 * w = { set of all nodes }
 * repeat until w empty
 *    n = w.pop()
 *    out[n] = OR (n' ELEM SUCC[n]) in[n']
 *    in[n] = use[n] OR (out[n] - def[n])
 *    if change to in[n]
 *       for all predecessors m of n, w.push(m)
 *****************************************/

debug

buildtree/tests/roseTests/programAnalysisTests/variableLivenessTests/

runTest inputcode.c

a few dot files will be generated

• cfg.dot
• dfa.dot
• var.dot // this is the one with variables showing up

Programming API to generate a dot graph

#include "rose.h"
#include "DefUseAnalysis.h"
#include "LivenessAnalysis.h"

.....
  SgProject* project = frontend(argvList);
  // Call the Def-Use Analysis
  DFAnalysis* defuse = new DefUseAnalysis(project);
  int val = defuse->run(debug);

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

  std::vector <FilteredCFGNode < IsDFAFilter > > 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 <IsDFAFilter> 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<IsDFAFilter> source = FilteredCFGNode<IsDFAFilter> (
                        funcDecl->cfgForEnd());
        if (forwardAlgo)
                source = FilteredCFGNode<IsDFAFilter> (funcDecl->cfgForBeginning());

        //CFGNode cmpSrc = CFGNode(funcDecl->cfgForEnd());
        FilteredCFGNode<IsDFAFilter> 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 <typename NodeT, typename EdgeT> void DfaToDotImpl<NodeT, EdgeT>::explore(NodeT n)
• print out nodes and edges: template <typename NodeT, typename EdgeT> void DfaToDotImpl<NodeT, EdgeT>::processNodes(SgNode*)

TODO:

• write to dot graph does not work properly in the middle