通过词法分析,语法分析,语义分析,最后产生了四元式。而代码生成则是通过四元式来完成。我们先从简单开始做起。
编译实验项目下载链接:http://download.csdn.net/download/supersmart_dong/10224159
例如四元式(j,0,0,7)这样的,代码生成只需要一个goto语句;(j=,A,B,7)代码生成为:
CMP A,B
JE .....
目标代码如果是汇编语言的话,则代码生成对汇编要有一定了解。
指令码
意义
条件
JZ, JE
结果为0或相等则转
Z=1,(A) = (B)
JNZ, JNE
结果不为0或不相等则转
Z=0,(A)≠(B)
JNL, JGE
大于等于转
(S∨O)=0,(A)≥(B)
JL, JNGE
小于转
(S∨O)=1,(A)<(B)
JG, JNLE
大于转
(S∨O∨Z)=0,(A)>(B)
JMP
无条件转移
CMP 为比较,实际上是两个变量相减只影响标志位。
所以当(J<,A,B,7)这样的只需要一个比较语句和一个跳转语句就行。跳转到哪?当然是跳转到对应四元式所对应的代码了,我们需要引进基本块的概念,块也就是一堆顺序执行的语句序列。首先要就四元式进行划分基本块。
(1)程序第一个四元式为基本块入口
(2)跳转四元式的下一个四元式为基本块入口
(3)跳转语句要跳转到的四元式,该四元式为基本块入口
最后,相邻两个基本块入口之间的四元式构成一个基本块(其中包含前者入口,不包含后者入口)。跳转语句的跳转位置也就是基本块的名字。
首先第一步,设置基本块路口,我们四元式需要一个属性来标记是否为某基本块入口(0为否,1为是),按照上面的三步骤,遍历四元式判断是不是第一个四元式,是不是跳转语句的四元式,是的话相应四元式属性置为1就可以。
第二步就是初始化基本块集合。遍历四元式将四元式加入基本块,直到下一个入口四元式为止,再把基本块加到集合中。
做完这些,所有跳转语句就可以完成了,跳转目的地也就是四元式对应的基本块名称。
接下来完成加减乘除的四元式代码生成。假如有ax,bx,dx寄存器可用
像(+,A,B,T1) (:=,T1,0,A)对应汇编代码应该是:
MOV AX,A
ADD AX,B
MOV C,AX
假如B的值存在了bx寄存器中:
MOV AX,A
ADD AX,BX
MOV C,AX
首先定义寄存器的数据结构,起码要有name(寄存器名称),Rvalue(寄存器存放的值),例如上面的代码,AX寄存器最后存放了T1和C的值。struct registers { string name; vector<string> Rvalue; registers(string n){ name = n; } registers(){}; void clearPush(string n) { Rvalue.clear(); Rvalue.push_back(n); } bool isinReg(string n) { bool flag = false; for (int i = 0; i < Rvalue.size(); i++) { if (Rvalue[i] == n) flag = true; } return flag; } }; vector<registers> regs = { registers("AX"), registers("BX"), registers("DX") }; registers M("M"); registers findreg(string arg,int &index) { //如果找到原本有的 for (int i = 0; i < regs.size(); i++) { if (regs[i].isinReg(arg)) { index = i; return regs[i]; } } //没有则返回空寄存器 for (int i = 0; i < regs.size(); i++) { if (regs[i].Rvalue.size()==0) { index = i; return regs[i]; } } return NULL; } bool isExistRvalue(string arg) { for (int i = 0; i < regs.size(); i++) { if (regs[i].isinReg(arg)) return true; } return false; }
在进行加减乘除的代码生成的时候,首先遍历所有寄存器的Rvalue查询是否存在Rvalue中,是的话返回对应寄存器。
例如进行计算A+B时,对应四元式 (+,A,B,T),如果A和B分别在ax,bx寄存器中,对应代码:
ADD ax,bx
如果A在寄存器ax中b不在寄存器,则:
ADD ax,B
如果A在不在寄存器b在寄存器bx,则:
ADD bx,A
A和B都不在寄存器中时,返回空寄存器(假如是AX):
mov ax,A
add ax ,B
目标代码生成参考代码:
#include <string> #include <vector> #include "register.h" //定义基本块的数据结构,定义代码表的基本结构,找到四元式的入口,划分基本块,遍历基本块进行代码生成(首先完成根据四元式地址找到基本块,完成操作符代码表),精化代码表用到寄存器分配 static int nameNum; struct basicBlock { string name; vector<GenStruct> gens; vector <string> codes; basicBlock() { string str; int2str(nameNum,str); name = "L" + str; nameNum++; } void add(GenStruct g) { gens.push_back(g); } }; class codeTable { private: vector<basicBlock> block; //基本块 void initblock(); //初始化基本块 int findblocknameByGen(int index); //根据四元式地址找到基本块 string findblocknameByGen(string index){ int i = stoi(index); i=findblocknameByGen(i); if (i >= block.size()) return "End"; return block[i].name; } vector<string> createcode(GenStruct); void initblockcodes(); bool stringisinGen(string,int); //判断string 是否在index后四元式中存在 public: vector<basicBlock> getBasicBlock(){ return block; } codeTable(){ initblock(); initblockcodes(); } void clearNotUse(GenStruct); void printcodes(); }; void codeTable::initblock() { for (int i = 0; i < genStructs.size()-1; i++) { if (i == 0) { //程序第一条为入口 changeOut_port(0); } if (genStructs[i].code <= 58 && genStructs[i].code >= 52) //跳转语句 { changeOut_port(genStructs[i].result);//跳转到的语句为入口语句 changeOut_port(i+1); //跳转语句的下一行,为入口语句 } } for (int i = 0; i < genStructs.size() ; ) //把入口语句加入到基本块 { basicBlock bl; bl.add(genStructs[i]); i++; for (; i < genStructs.size(); i++) { if (genStructs[i].out_port == 1) { block.push_back(bl); break; } else bl.add(genStructs[i]); } if (i==genStructs.size()) block.push_back(bl); } } int codeTable::findblocknameByGen(int index) { for (int i = 0; i < block.size(); i++) //i为block索引 { for (int j = 0; j < block[i].gens.size(); j++) { if (block[i].gens[j].label == index) { return i; } } } return -1; } void codeTable::initblockcodes() { for (int blockindex = 0; blockindex < block.size(); blockindex++) { for (int i = 0; i < block[blockindex].gens.size(); i++) { block[blockindex].codes = merge(block[blockindex].codes, createcode(block[blockindex].gens[i])); } } } void codeTable::printcodes() { for (int blockindex = 0; blockindex < block.size(); blockindex++) { cout << block[blockindex].name << ":\n"; for (int i = 0; i < block[blockindex].codes.size(); i++) { cout << " "<<block[blockindex].codes[i] << endl; } } } vector<string> codeTable::createcode(GenStruct gen) { vector<string> codes; int code = gen.code; clearNotUse(gen); registers reg; int regindex,temp; switch (code) { case 41://op = "*"; if (isExistRvalue(gen.addr1) && isExistRvalue(gen.addr2)) { codes.push_back("MUL " + findreg(gen.addr1, regindex).name + "," + findreg(gen.addr2, temp).name); regs[regindex].clearPush(gen.result); } else if (isExistRvalue(gen.addr1) && !isExistRvalue(gen.addr2)) { codes.push_back("MUL " + findreg(gen.addr1, regindex).name + "," + gen.addr2); regs[regindex].clearPush(gen.result); } else if (!isExistRvalue(gen.addr1) && isExistRvalue(gen.addr2)) { codes.push_back("MUL " + findreg(gen.addr2, regindex).name + "," + gen.addr1); regs[regindex].clearPush(gen.result); } else{ reg = findreg(gen.addr1, regindex); codes.push_back("MOV " + reg.name + "," + gen.addr1); codes.push_back("MUL " + reg.name + "," + gen.addr2); regs[regindex].clearPush(gen.result); } break; case 43://op = "+"; if (isExistRvalue(gen.addr1) && isExistRvalue(gen.addr2)) { codes.push_back("ADD " + findreg(gen.addr1, regindex).name + "," + findreg(gen.addr2, temp).name); regs[regindex].clearPush(gen.result); } else if (isExistRvalue(gen.addr1) && !isExistRvalue(gen.addr2)) { codes.push_back("ADD " + findreg(gen.addr1, regindex).name + "," + gen.addr2); regs[regindex].clearPush(gen.result); } else if (!isExistRvalue(gen.addr1) && isExistRvalue(gen.addr2)) { codes.push_back("ADD " + findreg(gen.addr2, regindex).name + "," + gen.addr1); regs[regindex].clearPush(gen.result); } else{ reg = findreg(gen.addr1, regindex); codes.push_back("MOV " + reg.name + "," + gen.addr1); codes.push_back("Add " + reg.name + "," + gen.addr2); regs[regindex].clearPush(gen.result); } break; case 45://op = "-"; codes.push_back("MOV " + findreg(gen.addr1, regindex).name + ",-" + gen.addr2); regs[regindex].clearPush(gen.result); break; case 48://op = "/"; 没有这个文法 codes.push_back("DIV " + gen.addr1 + "," + gen.addr2); break; case 51://op = ":="; reg = findreg(gen.addr1, regindex); codes.push_back("MOV " + gen.result + "," + reg.name); regs[regindex].Rvalue.push_back(gen.result); break; case 52://op = "j"; codes.push_back("GOTO " + findblocknameByGen(gen.result)); break; case 53://op = "j<"; codes.push_back("CMP " + gen.addr1 + "," + gen.addr2); codes.push_back("JL " + findblocknameByGen(gen.result)); break; case 54://op = "j<="; codes.push_back("CMP " + gen.addr1 + "," + gen.addr2); codes.push_back("JLE " + findblocknameByGen(gen.result)); break; case 55://op = "j<>"; codes.push_back("CMP " + gen.addr1 + "," + gen.addr2); codes.push_back("JNE " + findblocknameByGen(gen.result)); break; case 56://op = "j="; codes.push_back("CMP " + gen.addr1 + "," + gen.addr2); codes.push_back("JE " + findblocknameByGen(gen.result)); break; case 57://op = "j>"; codes.push_back("CMP " + gen.addr1 + "," + gen.addr2); codes.push_back("JG " + findblocknameByGen(gen.result)); break; case 58://op = "j>="; codes.push_back("CMP " + gen.addr1 + "," + gen.addr2); codes.push_back("JGE " + findblocknameByGen(gen.result)); break; default: break; } return codes; } bool codeTable::stringisinGen(string str,int index) { for (int i = genStructs.size() - 1; i >= index; i--) //因为先删除后操作,所以要把iindex是加进去 { if (genStructs[i].addr1 == str || genStructs[i].addr2 == str) return true; } return false; } //遍历所有基本块,把非待用的寄存器里值给删了,把基本块里的Rvalue void codeTable::clearNotUse(GenStruct gen)//运行到四元式的值 { int index = gen.label; //遍历所有寄存器的Rvalue 看看后没有在index之后的四元式出现 for (int i = 0; i < regs.size(); i++) { for (int j = 0; j < regs[i].Rvalue.size(); j++) { if (!stringisinGen(regs[i].Rvalue[j], index)) { //删除 regs[i].Rvalue.erase(regs[i].Rvalue.begin() + j); } } } }
到此为止,差不多就结束了。不过有个缺陷,就是计算一旦多起来寄存器可能就不够用了,所以在每次生成代码前还要把寄存器里非待用的给删了。何为非待用?例如:
1: T1 :=A+B
2: C :=T1+A
当执行完第一句时此时T1 和A是待用的因为之后的运算用到了他们,B是非待用的因为之后的运算没用到B。
实现非待用判断不难,首先从尾至当前,遍历四元式看看第二元素,第三元素是否与之相等。
实现非待用的删除,遍历每个寄存的RValue中的值,判断该值是否非待用,是则删除。