基于DAG的基本块优化.docx
《基于DAG的基本块优化.docx》由会员分享,可在线阅读,更多相关《基于DAG的基本块优化.docx(25页珍藏版)》请在冰点文库上搜索。
基于DAG的基本块优化
基于DAG的基本块优化
1.实验目的与任务
了解基本块的DAG表示及其应用,掌握局部优化的基本方法。
2.实验要求
设计一个转换程序,把由四元式序列表示的基本块转换为DAG,并在构造DAG的过程中,进行合并已知量、删除无用赋值及删除公共子表达式等局部优化处理。
最后再从所得到的DAG出发,按原来生成DAG各个结点的顺序,重建四元式序列形式的基本块。
3.实验内容
(1)DAG的结点类型只考虑0型、1型和2型,如下表所示。
类型
四元式
DAG结点
0型
(=,B,,A)
①A
B
1型
(op,B,,A)
②
op
①
2型
(op,B,C,A)
(=[],B,C,A)
(jrop,B,C,A)
(2)由基本块构造DAG算法如下:
while(基本块中还有未处理过的四元式){
取下一个四元式Q;
newleft=newright=0;
if(getnode(B)==NULL){
makeleaf(B);
newleft=1;
}
switch(Q的类型){
case0:
n=getnode(B);
insertidset(n,A);
break;
case1:
if(isconsnode(B)){
p=calcons(Q.op,B);
if(newleft==1)/*getnode(B)是处理Q时新建结点*/
delnode(B);
if((n=getnode(p))==NULL){
makeleaf(p);
n=getnode(p);
}
}
else{
if((n=findnode(Q.op,B))==NULL)
n=makenode(Q.op,B);
}
insertidset(n,A);
break;
case2:
if(getnode(C)==NULL){
makeleaf(C);
newright=1;
}
if(isconsnode(B)&&isconsnode(C)){
p=calcons(Q.op,B,C);
if(newleft==1)/*getnode(B)是处理Q时新建结点*/
delnode(B);
if(newright==1)/*getnode(C)是处理Q时新建结点*/
delnode(C);
if((n=getnode(p))==NULL){
makeleaf(p);
n=getnode(p);
}
}
else{
if((n=findnode(Q.op,B,C))==NULL)
n=makenode(Q.op,B,C);
}
insertidset(n,A);
break;
}
}
}
上述算法中应设置如下的函数:
getnode(B):
返回B(可以是标记或附加信息)在当前DAG中对应的结点号。
makeleaf(B):
构造标记为B的叶子结点。
isconsnode(B):
检查B对应的结点是否为标记为常数的叶子结点。
calcons(Q.op,B):
计算opB的值(即合并已知量)。
它的另一种调用形式是
calcons(Q.op,B,C):
计算BopC的值。
delnode(B):
删除B(结点的标记)在当前DAG中对应的结点。
findnode(Q.op,B):
在当前DAG中查找并返回这样的结点:
标记为op,后继为getnode(B)(即查找公共子表达式opB)。
它的另一种调用形式是findnode(Q.op,B,C)(即查找公共子表达式BopC)。
makenode(Q.op,B,C):
构造并返回标记为op,左右后继分别为getnode(B)、getnode(C)的内部结点。
insertidset(n,A):
若getnode(A)=NULL,则把A附加到结点n;否则,若A在getnode(A)的附加标识符集中,且getnode(A)无前驱或虽有前驱但getnode(A)附加标识符集中符号数大于1,则把A从getnode(A)的附加标识符集中删除(即删除无用赋值)。
请实现上述基本块的DAG构造算法,并添加从所得DAG按原来生成DAG各个结点的顺序,重建四元式序列的功能。
(3)测试用例
用下面的基本块作为输入:
(1)T1=A*B
(2)T2=3/2
(3)T3=T1―T2
(4)X=T3
(5)C=5
(6)T4=A*B
(7)C=2
(8)T5=18+C
(9)T6=T4*T5
(10)Y=T6
基本块的DAG如下:
按生成DAG各个结点的顺序,重建四元式序列如下:
(1)T1=A*B
(2)T2=1.5
(3)T3=T1―1.5
(4)X=T3
(5)T4=T1
(6)C=2
(7)T5=20
(8)T6=T1*20
(9)Y=T6
Code.txt文件内容
T1=A*B
T2=3/2
T3=T1―T2
X=T3
C=5
T4=A*B
C=2
T5=18+C
T6=T4*T5
Y=T6
#include
#include
#include
#include
/*functionansdatastatement*/
#defineMAXN5/*符号或变量最大长度*/
/*结点类型*/
typedefstructnode
{
intiscons;/*0--无1--整型2--浮点*/
intval_int;/*整型值*/
doubleval_float;/*浮点值*/
intidnum;/*变量的个数*/
charid[MAXN][MAXN];/*变量0~valnum-1*/
charop[MAXN];/*结点操作*/
intleft,right;/*左右节点*/
}DAGNODE;
#defineMAXNN20/*DAG最大结点数目*/
/*DAG*/
typedefstructmnode
{
intnum;/*结点个数*/
DAGNODEnode[MAXNN];/*结点内容1~NUM*/
}DAG;
/*四元式Quaternion*/
typedefstructsnode
{
inttype;/*类型012*/
charop[MAXN];/*操作*/
charop1[MAXN];/*操作数1*/
charop2[MAXN];/*操作数2*/
charans[MAXN];/*结果*/
}QUA;
voidinit();/*初始化函数*/
boolgetqua(QUA*qua);/*获取一个四元式*/
intisnums(char*val);/*检测字符串是否是数字串0标识符1整型数串2浮点数串*/
voidmakeleaf(DAGNODE*n,charval[]);/*构造叶子结点*/
voidmakenode(DAGNODE*n,charop[],intleft,intright);/*构造中间结点*/
intgetnode(DAGdag,charvar[]);/*获取var[]所在结点号*/
intfind1node(DAGdag,charop1[],charop[]);/*查找已有的表达式1*/
intfind2node(DAGdag,charop1[],charop2[],charop[]);/*查找已知表达式2*/
char*isconsnode(DAGdag,charid[]);/*是否是常数结点的id*/
voiddelnode(DAG*dag,intnum);/*删除结点num*/
voiddelid(DAG*dag,intnum);/*删除某节点的Id*/
voidcopynode(DAGNODE*to,DAGNODEfrom);/*复制结点值*/
voidinsertvar(DAG*dag,intnoden,charvar[]);/*将值var附加在noden结点*/
intinsertnode(DAG*dag,DAGNODEdagn);/*将结点插入DAG*/
char*calcons1(charop[],charop1[]);/*计算opop1的运算值*/
char*calcons2(charop[],charop1[],charop2[]);/*op1opop2*/
voidmakeDAG();/*构造DAG*/
voiddispDAG(DAGdag);/*输出DAG*/
char*getv(DAGdag,intdagn);
FILE*fp;/*文件指针,指向代码文件*/
voiddispcode();
intmain()
{
init();
dispcode();
init();
makeDAG();
return0;
}
voiddispcode()
{
staticinti=1;
QUAq;
while(getqua(&q))
{
if(q.type==0)
printf("(%d)%s%s%s\n",i++,q.ans,q.op,q.op1);
elseif(q.type==1)
printf("(%d)%s=%s%s\n",i++,q.ans,q.op,q.op1);
else
printf("(%d)%s=%s%s%s\n",i++,q.ans,q.op1,q.op,q.op2);
}
}
/*初始化函数*/
voidinit()
{
if((fp=fopen("code.txt","r"))==NULL)
{printf("thecodefileisnotexisted.");exit(0);}
}
/*获取一个四元式*/
boolgetqua(QUA*qua)
{
intt;
if(feof(fp)){fclose(fp);returnfalse;}
fscanf(fp,"%d",&t);
fscanf(fp,"%s",qua->ans);
fscanf(fp,"%s",qua->op);
fscanf(fp,"%s",qua->op1);
if(fgetc(fp)=='\n'||feof(fp)){
strcpy(qua->op2,"");
if(!
strcmp(qua->op,"="))
qua->type=0;
if(feof(fp)){fclose(fp);returnfalse;}
returntrue;
}
fscanf(fp,"%s",qua->op);
if(fgetc(fp)=='\n'||feof(fp)){
strcpy(qua->op2,qua->op);
strcpy(qua->op,qua->op1);
strcpy(qua->op1,qua->op2);
strcpy(qua->op2,"");
qua->type=1;
if(feof(fp)){fclose(fp);returnfalse;}
returntrue;
}
fscanf(fp,"%s",qua->op2);
qua->type=2;
returntrue;
}
intisnums(char*val)
{
inti,flag;
for(i=0;val[i];i++){
if(!
isdigit(val[i])){
if(val[i]=='.')/*浮点*/
{flag=2;break;}
flag=0;break;
}
else{
flag=1;/*整型*/
}
}
returnflag;
}
/*构造叶子结点*/
voidmakeleaf(DAGNODE*n,charval[])
{
switch(isnums(val))
{
case0:
n->iscons=0;
n->val_float=0;
n->val_int=0;
n->idnum=1;
strcpy(n->id[0],val);
break;
case1:
n->idnum=0;
n->iscons=1;
n->val_int=atoi(val);
n->val_float=0;
break;
case2:
n->idnum=0;
n->iscons=2;
n->val_int=0;
n->val_float=atof(val);
break;
}
strcpy(n->op,"");
n->left=n->right=0;
}
/*构造中间结点*/
voidmakenode(DAGNODE*n,charop[],intleft,intright)
{
n->idnum=0;
n->iscons=0;
strcpy(n->op,op);
n->left=left;
n->right=right;
}
/*获取var[]所在结点号*/
intgetnode(DAGdag,charvar[])
{
inti,j;
if(dag.num==0)return0;
for(i=1;i<=dag.num;i++)
{
switch(isnums(var))
{
case0:
for(j=0;jif(!
strcmp(dag.node[i].id[j],var))
returni;
break;
case1:
if(dag.node[i].val_int==atoi(var))
returni;
break;
case2:
if(dag.node[i].val_float==atof(var))
returni;
break;
}
}
return0;
}
/*是否是常数节点,常数*/
char*isconsnode(DAGdag,charid[])
{
inti,j;
char*temp;
temp=(char*)malloc(MAXN*sizeof(char));
if(isnums(id)){strcpy(temp,id);returntemp;}
for(i=1;i<=dag.num;i++)
{
if(dag.node[i].iscons>0)/*常数结点*/
{
for(j=0;jif(!
strcmp(dag.node[i].id[j],id)){
switch(dag.node[i].iscons){
case1:
sprintf(temp,"%d",dag.node[i].val_int);
break;
case2:
sprintf(temp,"%g",dag.node[i].val_float);
break;
}
returntemp;
}
}
}
returnNULL;
}
/*查找已定义的表达式1*/
intfind1node(DAGdag,charop1[],charop[])
{
inti;
intop1n;
op1n=getnode(dag,op1);
for(i=1;i<=dag.num;i++)
if((dag.node[i].left==op1n)&&!
strcmp(dag.node[i].op,op))
returni;
return0;
}
/*查找已知表示式2*/
intfind2node(DAGdag,charop1[],charop2[],charop[])
{
inti;
intop1n,op2n;
op1n=getnode(dag,op1);
op2n=getnode(dag,op2);
for(i=1;i<=dag.num;i++)
if((dag.node[i].left==op1n)&&(dag.node[i].right==op2n)&&!
strcmp(dag.node[i].op,op))
returni;
return0;
}
/*删除结点num*/
voiddelnode(DAG*dag,intnum)
{
inti,j;
if(dag->num==0)return;
for(i=1;i<=dag->num;i++)
if(i==num){
for(j=i;j<=dag->num;j++)
copynode(&(dag->node[j]),dag->node[j+1]);
}
--(dag->num);
}
/*删除某结点的id*/
voiddelid(DAG*dag,intnum)
{
inti;
if(dag->num==0)return;
for(i=0;inode[num].idnum;i++)
strcpy(dag->node[num].id[i],"");
dag->node[num].idnum=0;
}
/*赋值结点值*/
voidcopynode(DAGNODE*to,DAGNODEfrom)
{
inti;
to->idnum=from.idnum;
for(i=0;istrcpy(to->id[i],from.id[i]);
to->iscons=from.iscons;
to->val_int=from.val_int;
to->val_float=from.val_float;
strcpy(to->op,from.op);
to->left=from.left;
to->right=from.right;
}
/*将值var附加在noden结点*/
voidinsertvar(DAG*dag,intnoden,charvar[])
{
(dag->node[noden].idnum)++;
strcpy(dag->node[noden].id[dag->node[noden].idnum-1],var);
}
/*将结点插入DAG*/
intinsertnode(DAG*dag,DAGNODEdagn)
{
dag->num=dag->num+1;
copynode(&(dag->node[dag->num]),dagn);
returndag->num;
}
/*计算opop1的运算值*/
char*calcons1(charop[],charop1[])
{
char*temp;
if(!
strcmp(op,"!
")){
temp=(char*)malloc(MAXN*sizeof(char));
switch(isnums(op1)){
case1:
sprintf(temp,"%d",!
atoi(op1));break;
}
}
returntemp;
}
/*计算op1opop2的值*/
char*calcons2(charop[],charop1[],charop2[])
{
intch=isnums(op1)>isnums(op2)?
isnums(op1):
isnums(op2);
char*temp;
temp=(char*)malloc(MAXN*sizeof(char));
if(!
strcmp(op,"+")){
switch(ch){
case1:
sprintf(temp,"%d",atoi(op1)+atoi(op2));
break;
case2:
sprintf(temp,"%g",atof(op1)+atof(op2));
break;
}
}elseif(!
strcmp(op,"-")){
switch(ch){
case1:
sprintf(temp,"%d",atoi(op1)-atoi(op2));
break;
case2:
sprintf(temp,"%g",atof(op1)-atof(op2));
break;
}
}elseif(!
strcmp(op,"*")){
switch(ch){
case1:
sprintf(temp,"%d",atoi(op1)*atoi(op2));
break;
case2:
sprintf(temp,"%g",atof(op1)*atof(op2));
break;
}
}elseif(!
strcmp(op,"/")){
/*!
除法结果为浮点*/
sprintf(temp,"%g",atof(op1)/atof(op2));
}
returntemp;
}
/*构造DAG*/
voidmakeDAG()
{
DAGdag;dag.num=0;/*DAG*/
QUAqua;/*四元式*/
DAGNODEdagn;/*DAG结点*/
intop1n,op2n,opn,oopn;/*操作数1--B2--C所在结点号*/
chartemp[MAXN];
intnewleft,newright;
while(getqua(&qua)){
/*op1--B没有定义*/
newleft=newright=0;
if(getnode(dag,qua.op1)==0){
makeleaf(&dagn,qua.op1);
insertnode(&dag,dagn);/*将结点插入DAG*/