ROSE 编译器框架/活跃性分析
ROSE 中有几种活跃性分析的实现。
编译器执行的经典数据流分析，用于计算每个程序点可能在下次写入之前读取的变量，即每个程序点出口处的活动变量。
- 后向数据流分析
- 可能分析
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
另一个
L1: b := 3; // live_out={b}
L2: c := 5; // live_out ={b,c}
L3: a := b + c;
END
第 L2 行的活动变量集为 {b, c}，但第 L1 行的活动变量集仅为 {b}，因为变量 c 在第 2 行更新。变量 a 的值从未使用过，因此该变量从未处于活动状态。
- x 在循环之前不是活动变量（活动变量输入）：x=a[i] 在 x 被使用之前重新定义了 x，x 在循环之后不是活动变量（活动变量输出）：x=10 在 x 被使用之前重新定义了 x。
int x;
for (i=0;i<100;i++)
{
x= a[i];
b[i]=x+1;
}
x = 10;
- a 是活动变量输入和活动变量输出
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 是活动变量输入，但不是活动变量输出
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 = ...
您必须使用 https://github.com/rose-compiler/rose-develop 中的最新版本的 ROSE
cd rosebuildtree/projects/CodeThorn/src // 注意：必须进入 src 目录，而不是 CodeThorn 的顶部！
make analyterix
./analyterix --lv-analysis myprog.C
在 rose_myprog.C 中，lv-analysis 结果被注释为注释。
注意
- 直接在 projects/CodeThorn 下输入 make 将失败，因为它构建了所有内容，需要一个名为 SPOT 的第三方库
输入
...
#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);
}
}
输出
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
}
src/midend/abstractLayer/Labeler.h /.C // 带标签的 AST 节点
projects/CodeThorn/src/LVLattice.h // 活跃性分析格
这将被逐步淘汰，以支持更新的版本
提供两个函数来调用分析并获取循环的活动变量。
// 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)
如果您想将其扩展到支持任何范围语句，则需要了解一些内部机制
//!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)
}
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)
*****************************************/
buildtree/tests/roseTests/programAnalysisTests/variableLivenessTests/
runTest inputcode.c
将生成一些点文件
- cfg.dot
- dfa.dot
- var.dot // 这是变量显示的那个
用于生成点图的编程 API
#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;
sourcetree/src/midend/programAnalysis/defUseAnalysis
dfaToDot.h dfaToDot.cpp
两个步骤
- 将所有 CFG 节点收集到一个多重映射中：template <typename NodeT, typename EdgeT> void DfaToDotImpl<NodeT, EdgeT>::explore(NodeT n)
- 打印节点和边：template <typename NodeT, typename EdgeT> void DfaToDotImpl<NodeT, EdgeT>::processNodes(SgNode*)
待办事项
- 写入点图在中间不起作用