基于DAG的基本块优化.docx
《基于DAG的基本块优化.docx》由会员分享，可在线阅读，更多相关《基于DAG的基本块优化.docx（15页珍藏版）》请在冰点文库上搜索。
基于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）
B
C
rop
3
1
2
B
C
=[]
3
1
2
B
C
op
3
1
2
（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如下：
*
*
-
③T1,T4
⑤T3,X
⑨T6,Y
①
A
B
1.5
20
5
2
④T2
②
⑧T5
⑥
⑦C
按生成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;
#defineMAXNN 20 /*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;j if（!
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;j if（!
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;i strcpy（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结点
升级会员 