tobin.cpp

一个用C++实现的C的Compiler。 代码风格良好。 原作者自己写了这个编译器

#include <cstdio>
#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include "IDHash.cpp"

#define InFile "IR.tac"

using namespace std;

const			int				LimitVars				=		100000;
const			int				LimitLabel				=		100000;
const			int				MaxColor				=		500;
const			int				global_func_name		=		-1;

const			int				var_class_global_dat	=		0;
const			int				var_class_global_var	=		1;
const			int				var_class_func_var		=		2;
const			int				var_class_temp_var		=		3;

const			int				var_type_uint16			=		-1;

const			int				LimitFunction			=		10000;

const			int				RegCount				=		6;

const			int				bincode_type_begin		=		0;
const			int				bincode_type_empty		=		1;
const			int				bincode_type_normal		=		2;
const			int				bincode_type_B			=		3;
const			int				bincode_type_BTEQZ		=		4;
const			int				bincode_type_BTNEZ		=		5;
const			int				bincode_type_BEQZ		=		6;
const			int				bincode_type_BNEZ		=		7;
const			int				bincode_type_load_const_front
														=		8;
const			int				bincode_type_load_const_back
														=		9;
const			int				bincode_type_load_func	=		10;
const			int				bincode_type_load_global_var
														=		11;
const			int				bincode_type_load_global_const
														=		12;

const			int				bincode_type_B_L		=		23;
const			int				bincode_type_BTEQZ_L	=		24;
const			int				bincode_type_BTNEZ_L	=		25;
const			int				bincode_type_BEQZ_L		=		26;
const			int				bincode_type_BNEZ_L		=		27;

const			int				maxword					=		65535;
const			int				maxint					=		32767;
const			int				TOTAL_MEM				=		0xE000;

const			int				GlobalBaseColor			=		1000;

struct TVarEntry {
	int offset;
	int func_name;
	int var_class;
	int var_type;					/* >= 0 for sized block */
	list <int> conflict;
	int color, PEOcount;
	int lea_marked;
	TVarEntry () 
	{
		offset = func_name = var_class = var_type = color = PEOcount = -1;
		lea_marked = 0; 
	}
};

struct TBinEntry {
	int bincode_type;
	unsigned short code;
	int label_name, func_name;
	int reg_name;
	int jmpreg1, jmpreg2;
	int short_num;
	int visited;
	list <TBinEntry> :: iterator bin_label;
};

struct TTACEntry {
	int offset;
	string op, var1, var2, var3;
	list <int> setA1, setA2, setA3, setB1, setB2, setB3, live1, live2, live3;
	list <int> use, def;
	list <int> usereg, defreg;
	list <TBinEntry> :: iterator bin_start;
	int phi1[RegCount], phi2[RegCount], phi3[RegCount];
	int work_space[RegCount];
	int func_name;
	int sp_bias;
	TTACEntry ()
	{
		memset(phi1, 0xff, sizeof(phi1));
		memset(phi2, 0xff, sizeof(phi2));
		memset(phi3, 0xff, sizeof(phi3));
	}
	void print()
	{
		printf("  %s %s %s %s\t", op.c_str(), var1.c_str(), var2.c_str(), var3.c_str());
	}
};

struct TFuncEntry {
	int ret_type;
	int parameter_size;
	int determined_size;
	int max_color;
	list <TTACEntry> ins;
	list <TBinEntry> :: iterator bin_start;
	TFuncEntry() { parameter_size = -1; }
};

vector <int> globaldata;
TVarEntry VarEntry[LimitVars];
TFuncEntry FuncEntry[LimitFunction];
list <TTACEntry> :: iterator LabelEntry[LimitLabel];
list <TBinEntry> bincode;
list <TBinEntry> :: iterator BinLabelEntry[LimitLabel];
int max_var_name = -1;
int max_func_name = -1;
int max_label_name = -1;
int globaldata_size, globaldata_start;
int global_size, global_start;
int code_size, code_start = 10;
int stack_top, stack_size = 0x100;
int kernel_mode = 1;
int func_count;
char* OutFile = "code.cod";
int sp_add;

void read_globaldata(ifstream& fin)
{
	string s = "#";
	while (s != "GlobalData") 
	{
		fin >> s;
	}
	fin >> s;
	globaldata_size = 0;
	while (s != "EndGlobalData")
	{
		int var_name;
		sscanf(s.c_str(), "v%d", &var_name);
		if (var_name > max_var_name) max_var_name = var_name;
		VarEntry[var_name].offset = globaldata.size();
		VarEntry[var_name].func_name = global_func_name;
		VarEntry[var_name].var_class = var_class_global_dat;
		VarEntry[var_name].var_type = var_type_uint16;

		fin >> s;
		while (s != "#")
		{
			int num;
			sscanf(s.c_str(), "%d", &num);
			globaldata.push_back(num);
			globaldata_size ++;
			fin >> s;
		}

		fin >> s;
	}
}

int __get_sizeof(int var_type)
{
	if (var_type == var_type_uint16)
	{
		return 1;
	}
	else
	{
		return var_type;
	}
}

int str2vartype(string& s)
{
	if (s == "u16")
	{
		return var_type_uint16;
	}
	else if (s[0] == 'w')
	{
		int var_type;
		sscanf(s.c_str(), "w%d", &var_type);
		return var_type;
	}
	else 
	{
		printf("unknown type : %s", s.c_str());
		exit(1);
	}
}

void read_globalvar(ifstream& fin)
{
	string s = "#";
	while (s != "Global") fin >> s;
	int offset = 0;
	fin >> s;
	while (s != "EndGlobal")
	{
		int var_type;
		var_type = str2vartype(s);

		fin >> s;
		int var_name;
		sscanf(s.c_str(), "v%d", &var_name);
		VarEntry[var_name].offset = offset;
		VarEntry[var_name].func_name = global_func_name;
		VarEntry[var_name].var_class = var_class_global_var;
		VarEntry[var_name].var_type = var_type;
		offset += __get_sizeof(var_type);

		if (var_name > max_var_name) max_var_name = var_name;
		fin >> s;
	}
	global_size = offset;
}

int ListAdd(list <int>& A, int num)
{
	list <int> :: iterator p = A.begin();
	for ( ; p != A.end() && *p < num; p ++);
	if (p != A.end() && *p == num) return 0;
	A.insert(p, num);
	return 1;
}

int ListDel(list <int>& A, int num)
{
	for (list <int> :: iterator p = A.begin(); p != A.end(); p ++)
	{
		if (*p == num)
		{
			A.erase(p);
			return 1;
		}
	}
	return 0;
}

void printintlist(list <int>& A)
{
	for (list <int> :: iterator p = A.begin(); p != A.end(); p ++)
	{
		printf (" %d", *p);
	}
}

int read_function(ifstream& fin)
{
	string s;
	fin >> s;
	if (fin.eof()) return 0;
	int func_name = IDHash_ID2int(s);
	if (func_name > max_func_name) max_func_name = func_name;

	fin >> s; fin >> s;
	FuncEntry[func_name].ret_type = str2vartype(s);
	
	fin >> s;
	while (s != "BeginFunction") fin >> s;
	fin >> s;
	while (s != "Parameter") fin >> s;

	int offset = 0;
	fin >> s;
	while (s != "Var")
	{
		int var_type;
		var_type = str2vartype(s);

		fin >> s;
		int var_name;
		sscanf(s.c_str(), "v%d", &var_name);
		VarEntry[var_name].offset = offset;
		VarEntry[var_name].func_name = func_name;
		VarEntry[var_name].var_class = var_class_func_var;
		VarEntry[var_name].var_type = var_type;
		offset += __get_sizeof(var_type);

		if (var_name > max_var_name) max_var_name = var_name;

		fin >> s;
	}
	FuncEntry[func_name].parameter_size = offset;
	FuncEntry[func_name].determined_size = 0;
	fin >> s;

	while (s != "Stmt")
	{
		int var_type;
		var_type = str2vartype(s);

		fin >> s;
		int var_name;
		sscanf(s.c_str(), "v%d", &var_name);
		VarEntry[var_name].offset = -1;
		VarEntry[var_name].func_name = func_name;
		VarEntry[var_name].var_class = var_class_temp_var;
		VarEntry[var_name].var_type = var_type;

		if (var_name > max_var_name) max_var_name = var_name;

		fin >> s;
	}
	fin >> s;

	TTACEntry TAC;
	TAC.op = "BEGIN"; TAC.var1 = TAC.var2 = TAC.var3 = "(null)"; TAC.func_name = func_name;
	FuncEntry[func_name].ins.push_back(TAC);
	while (s != "EndFunction")
	{
		TAC.op = s;
		TAC.use.clear();
		TAC.def.clear();
		TAC.usereg.clear();
		TAC.defreg.clear();
		fin >> TAC.var1 >> TAC.var2 >> TAC.var3;
		TAC.func_name = func_name;
		if (TAC.op == "LABEL")
		{
			int label_name;
			sscanf(TAC.var1.c_str(), "L%d", &label_name);
			LabelEntry[label_name] = FuncEntry[func_name].ins.end();
			LabelEntry[label_name] --;
			if (label_name > max_label_name) max_label_name = label_name;
		}
		if (TAC.op == "LEA")
		{
			if (TAC.var2[0] == 'v')
			{
				int var_name;
				sscanf(TAC.var2.c_str(), "v%d", &var_name);
				if (!VarEntry[var_name].lea_marked)
				{
//					printf("LEA %s\n", TAC.var2.c_str());
					VarEntry[var_name].lea_marked = 1;
					if (VarEntry[var_name].var_class == var_class_temp_var)
					{
						VarEntry[var_name].offset = offset;
						offset += __get_sizeof(VarEntry[var_name].var_type);
						FuncEntry[func_name].determined_size += __get_sizeof(VarEntry[var_name].var_type);
					}
				}
			}
		}
		if (TAC.op == "ADD" || TAC.op == "SUB" || TAC.op == "MUL" || TAC.op == "DIV" || TAC.op == "MOD" || 
			TAC.op == "LET" || TAC.op == "AND" || TAC.op == "OR" || TAC.op == "NOT" || TAC.op == "LEA" || 
			TAC.op == "LOAD" || TAC.op == "RCALL" || TAC.op == "RICALL" || TAC.op == "LEAFUNC" || TAC.op == "XOR" ||
			TAC.op == "SHL" || TAC.op == "SHR")
		{
			if (TAC.var1[0] == 'v')
			{
				int var_name;
				sscanf(TAC.var1.c_str(), "v%d", &var_name);
				if (ListAdd(TAC.def, var_name))
					TAC.defreg.push_back(-1);
			}
		}
		if (TAC.op == "RREAD")
		{
			if (TAC.var2[0] == 'v')
			{
				int var_name;
				sscanf(TAC.var2.c_str(), "v%d", &var_name);
				if (ListAdd(TAC.def, var_name))
					TAC.defreg.push_back(-1);
			}
		}
		if (TAC.op == "JE" || TAC.op == "JNE" || TAC.op == "JL" || TAC.op == "JLE" || TAC.op == "JG" || 
			TAC.op == "JGE" || TAC.op == "POP" || TAC.op == "STORE" || TAC.op == "MEMCPY" || TAC.op == "PUSH" ||
			TAC.op == "RET")
		{
			if (TAC.var1[0] == 'v')
			{
				int var_name;
				sscanf(TAC.var1.c_str(), "v%d", &var_name);
				if (ListAdd(TAC.use, var_name))
					TAC.usereg.push_back(-1);
			}
		}
		if (TAC.op == "ADD" || TAC.op == "SUB" || TAC.op == "MUL" || TAC.op == "DIV" || TAC.op == "MOD" || 
			TAC.op == "LET" || TAC.op == "JE" || TAC.op == "JNE" || TAC.op == "JL" || TAC.op == "JLE" || 
			TAC.op == "JG" || TAC.op == "JGE" || TAC.op == "AND" || TAC.op == "OR" || TAC.op == "NOT" || 
			TAC.op == "LOAD" || TAC.op == "STORE" || TAC.op == "RICALL" || TAC.op == "MEMCPY" || TAC.op == "XOR" ||
			TAC.op == "SHL" || TAC.op == "SHR" || TAC.op == "RWRITE")
		{
			if (TAC.var2[0] == 'v')
			{
				int var_name;
				sscanf(TAC.var2.c_str(), "v%d", &var_name);
				if (ListAdd(TAC.use, var_name))
					TAC.usereg.push_back(-1);
			}
		}
		if (TAC.op == "ADD" || TAC.op == "SUB" || TAC.op == "MUL" || TAC.op == "DIV" || TAC.op == "MOD" || 
			TAC.op == "AND" || TAC.op == "OR" || TAC.op == "MEMCPY" || TAC.op == "XOR" || TAC.op == "SHL" || 
			TAC.op == "SHR")
		{
			if (TAC.var3[0] == 'v')
			{
				int var_name;
				sscanf(TAC.var3.c_str(), "v%d", &var_name);
				if (ListAdd(TAC.use, var_name))
					TAC.usereg.push_back(-1);
			}
		}
		if (TAC.op != "LABEL")
		{
			FuncEntry[func_name].ins.push_back(TAC);
		}
		fin >> s;
	}
	TAC.op = "NOP"; TAC.var1 = TAC.var2 = TAC.var3 = "(null)"; TAC.func_name = func_name;
	TAC.use.clear(); TAC.def.clear(); TAC.usereg.clear(); TAC.defreg.clear();
	FuncEntry[func_name].ins.push_back(TAC);
	return 1;
}

void init()
{
	ifstream fin(InFile);

	read_globaldata(fin);
	read_globalvar(fin);

	func_count = 0;
	while (!fin.eof())
	{
		if (read_function(fin))
		{
			func_count ++;
		}
	}
}

int ListJoin(list <int>& A, list <int>& B)
{
	int ret = 0;
	list <int> :: iterator p = A.begin();
	list <int> :: iterator q = B.begin();
	list <int> ret_list;
	while (p != A.end() || q != B.end())
	{
		if (q == B.end() || p != A.end() && *p <= *q)
		{
			ret_list.push_back(*p);
			if (q != B.end() && *p == *q)
			{
				q ++;
			}
			p ++;
		}
		else
		{
			ret = 1;
			ret_list.push_back(*q);
			q ++;
		}
	}
	A = ret_list;
	return ret;
}

int locatepos(int num, int phi[RegCount])
{
	for (int i = 0; i < RegCount; i ++)
	{
		if (num == phi[i])
		{
			return i;
		}
	}
	return -1;
}

int ListMinus(list <int>& A, list <int>& B)
{
	int ret = 0;
	for (list <int> :: iterator p = B.begin(); p != B.end(); p ++)
	{
		ret |= ListDel(A, *p);
	}
	return ret;
}

int ListIntersection(list <int>& C, list <int>& A, list <int>& B)
{
	list <int> :: iterator t = C.begin();
	list <int> :: iterator p = A.begin();
	list <int> :: iterator q = B.begin();
/*	printintlist(A); printf("\n");
	printintlist(B); printf("\n");
	printintlist(C); printf("\n");*/
	int different = 0;
	while (p != A.end() || q != B.end())