首页 » C语言 » 编译实验(三)目标代码生成

编译实验(三)目标代码生成

原文 http://blog.csdn.net/superSmart_Dong/article/details/79187150

2018-01-29 02:00:35阅读(467)

通过词法分析,语法分析,语义分析,最后产生了四元式。而代码生成则是通过四元式来完成。我们先从简单开始做起。

编译实验项目下载链接: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中的值,判断该值是否非待用,是则删除。

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹