tobin.cpp

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

	{
		if (q == B.end() || p != A.end() && *p <= *q)
		{
			if (q != B.end() && *p == *q)
			{
				if (t == C.end())
				{
					C.push_back(*p);
					different = 1;
				}
				else
				{
					*t = *p;
					t ++;
				}
				q ++;
			}
			p ++;
		}
		else
		{
			q ++;
		}
	}
	while (t != C.end())
	{
		different = 1;
		C.erase(t);
		t --;
		t ++;
	}
/*	if (different)
	{
		printintlist(A); printf("\n");
		printintlist(B); printf("\n");
		printintlist(C); printf("\n");
		printf("different : %d\n", different);
	}*/
	return different;
}

void calc_setA(int func_name)
{
	list <TTACEntry> :: iterator p = FuncEntry[func_name].ins.begin();
	for (int i = 0; i <= max_var_name; i ++)
	{
		if (VarEntry[i].var_class == var_class_func_var && VarEntry[i].offset < FuncEntry[func_name].parameter_size 
			&& VarEntry[i].func_name == func_name)
		{
			p->setA3.push_back(i);
		}
		p->setA3.sort();
	}

	int changed = 1;
	while (changed)
	{
		changed = 0;
		for (list <TTACEntry> :: iterator p = FuncEntry[func_name].ins.begin(); p != FuncEntry[func_name].ins.end(); p ++)
		{
			p->setA2 = p->setA1;
			p->setA3 = p->setA2;
			ListJoin(p->setA3, p->def);
			list <TTACEntry> :: iterator q = p;

			q ++;
			if (p->op == "JMP")
			{
				int label_name;
				sscanf(p->var1.c_str(), "L%d", &label_name);
				q = LabelEntry[label_name];
				q ++;
			}
			if (q != FuncEntry[func_name].ins.end())
			{
				changed |= ListJoin(q->setA1, p->setA3);
			}
			if (p->op == "JE" || p->op == "JNE" || p->op == "JL" || p->op == "JLE" || p->op == "JG" || p->op == "JGE")
			{
				int label_name;
				sscanf(p->var3.c_str(), "L%d", &label_name);
				q = LabelEntry[label_name];
				q ++;
				if (q != FuncEntry[func_name].ins.end())
				{
					changed |= ListJoin(q->setA1, p->setA3);
				}
			}
		}
	}
}

void calc_setB(int func_name)
{
	int changed = 1;
	while (changed)
	{
		changed = 0;
		for (list <TTACEntry> :: iterator p = FuncEntry[func_name].ins.end(); ; )
		{
			p --;

			list <TTACEntry> :: iterator q = p;
			q ++;
			if (p->op == "JMP")
			{
				int label_name;
				sscanf(p->var1.c_str(), "L%d", &label_name);
				q = LabelEntry[label_name];
				q ++;
			}
			if (q != FuncEntry[func_name].ins.end())
			{
				changed |= ListJoin(p->setB3, q->setB1);
			}
			if (p->op == "JE" || p->op == "JNE" || p->op == "JL" || p->op == "JLE" || p->op == "JG" || p->op == "JGE")
			{
				int label_name;
				sscanf(p->var3.c_str(), "L%d", &label_name);
				q = LabelEntry[label_name];
				q ++;
				if (q != FuncEntry[func_name].ins.end())
				{
					changed |= ListJoin(p->setB3, q->setB1);
				}
			}

			p->setB2 = p->setB3;
			ListMinus(p->setB2, p->def);
			p->setB1 = p->setB2;
			ListJoin(p->setB1, p->use);

			if (p == FuncEntry[func_name].ins.begin())
			{
				break;
			}
		}
	}
}

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

void calc_live(int func_name)
{
	for (int i = 0; i <= max_var_name; i ++)
	{
		if (VarEntry[i].func_name == func_name && VarEntry[i].var_class == var_class_func_var)
		{
			ListAdd(FuncEntry[func_name].ins.begin()->def, i);
		}
	}
	for (list <TTACEntry> :: iterator p = FuncEntry[func_name].ins.begin(); p != FuncEntry[func_name].ins.end(); p ++)
	{
		p->live1.clear();
		p->live2.clear();
		p->live3.clear();
	}

	int changed = 1;
	while (changed)
	{
		changed = 0;
	/*	for (list <TTACEntry> :: iterator p = FuncEntry[func_name].ins.begin(); p != FuncEntry[func_name].ins.end(); p ++)
		{
			p->print();
			printf("\n");
			printf("\t\t\tuse :");	printintlist(p->use);		printf("\n");
			printf("\t\t\tdef :");	printintlist(p->def);		printf("\n");
		}*/
		for (list <TTACEntry> :: iterator p = FuncEntry[func_name].ins.begin(); p != FuncEntry[func_name].ins.end(); p ++)
		{
			 p->setA1.clear(); p->setA2.clear(); p->setA3.clear();
			 p->setB1.clear(); p->setB2.clear(); p->setB3.clear();
		}
		calc_setA(func_name);
		calc_setB(func_name);
	//	printf ("Live status for %s: \n", IDHash_int2ID(func_name).c_str());
		for (list <TTACEntry> :: iterator p = FuncEntry[func_name].ins.begin(); p != FuncEntry[func_name].ins.end(); p ++)
		{
			changed |= ListIntersection(p->live1, p->setA1, p->setB1);
			changed |= ListIntersection(p->live2, p->setA2, p->setB2);
			changed |= ListIntersection(p->live3, p->setA3, p->setB3);
	/*		p->print();
			printf("\n");
			printf("\t\t\tSet live1:");	printintlist(p->live1);		printf("\n");
			printf("\t\t\tSet live2:");	printintlist(p->live2);		printf("\n");
			printf("\t\t\tSet live3:");	printintlist(p->live3);		printf("\n");*/
		}

		for (list <TTACEntry> :: iterator p = FuncEntry[func_name].ins.begin(); p != FuncEntry[func_name].ins.end(); p ++)
		{
			if (p->op == "ADD" || p->op == "SUB" || p->op == "MUL" || p->op == "DIV" || p->op == "MOD" || p->op == "LET" ||
				p->op == "AND" || p->op == "OR" || p->op == "NOT" || p->op == "LEA" || p->op == "LOAD" || p->op == "LEAFUNC" ||
				p->op == "SHL" || p->op == "SHR")
			{
				int okdel = 1;
				for (list <int> :: iterator t = p->def.begin(); t != p->def.end(); t ++)
				{
					if (ListCheckIn(p->live3, *t) || VarEntry[*t].var_class == var_class_global_var || 
						(VarEntry[*t].var_class == var_class_func_var || VarEntry[*t].var_class == var_class_temp_var) && VarEntry[*t].lea_marked)
					{
						okdel = 0;
						break;
					}
				}
				if (okdel)
				{
//					p->print(); printf(" DELETE\n");
					p->op = "NOP";
					p->use.clear(); p->def.clear();
					p->usereg.clear(); p->defreg.clear();
				}
			}
			if (p->op == "POP" && p->var1 == "0")
			{
//				p->print(); printf(" DELETE\n");
				p->op = "NOP";
				p->use.clear(); p->def.clear();
			}
		}
	}
}

void AddConflict(list <int>& A, int func_name)
{
	for (list <int> :: iterator p = A.begin(); p != A.end(); p ++) if (!VarEntry[*p].lea_marked && VarEntry[*p].func_name == func_name)
	{
		for (list <int> :: iterator q = A.begin(); q != A.end(); q++) if (!VarEntry[*q].lea_marked && VarEntry[*q].func_name == func_name)
		{
			ListAdd(VarEntry[*p].conflict, *q);
		}
	}
}

void color_graph(int func_name)
{
	vector <int> infunc_var;
	for (int i = 0; i <= max_var_name; i ++)
	{
		if (!VarEntry[i].lea_marked && VarEntry[i].func_name == func_name)
		{
			infunc_var.push_back(i);
			VarEntry[i].PEOcount = 0;
		}
	}

	for (list <TTACEntry> :: iterator p = FuncEntry[func_name].ins.begin(); p != FuncEntry[func_name].ins.end(); p ++)
	{
		AddConflict(p->live1, func_name);
		AddConflict(p->live2, func_name);
		AddConflict(p->live3, func_name);
	}

/*	printf("Conflicts : \n");
	for (int i = 0; i <= max_var_name; i ++)
	{
		if (VarEntry[i].func_name == func_name)
		{
			printf("Var %d : ", i);
			printintlist(VarEntry[i].conflict);
			printf("\n");
		}
	}*/

	for (unsigned int i = 0; i < infunc_var.size(); i ++)
	{
		VarEntry[infunc_var[i]].color = -1;
	}
	int used[MaxColor];
	vector <int> order;
	for (int i = 0; i < (int)infunc_var.size(); i ++)
	{
		int min = -1;
		for (int j = 0; j < (int)infunc_var.size(); j ++)
		{
			if (VarEntry[infunc_var[j]].color == -1 && 
					(min == -1 || VarEntry[min].PEOcount > VarEntry[infunc_var[j]].PEOcount))
			{
				min = infunc_var[j];
			}
		}
//		printf("checked, %d\n", min);
		order.push_back(min);
		VarEntry[min].color = -2;
		for (list <int> :: iterator p = VarEntry[min].conflict.begin(); p != VarEntry[min].conflict.end(); p ++)
		{
			VarEntry[*p].PEOcount ++;
		}
	}

/*	printf("Order : ");
	for (int i = 0; i < (int)infunc_var.size(); i ++)
	{
		printf(" %d", order[i]);
	}
	printf("\n");*/

	memset(used, 0xff, sizeof(used));
	for (int i = 0; i < (int)infunc_var.size(); i ++)
	{
		int min = order[infunc_var.size() - 1 - i];
		for (list <int> :: iterator p = VarEntry[min].conflict.begin(); p != VarEntry[min].conflict.end(); p ++)
		{
			if (VarEntry[*p].color != -2)
			{
				used[VarEntry[*p].color] = i;
			}
		}
		VarEntry[min].color = 0;
		while (used[VarEntry[min].color] == i) VarEntry[min].color ++;
		if (VarEntry[min].color > FuncEntry[func_name].max_color)
		{
			FuncEntry[func_name].max_color = VarEntry[min].color;
		}
	}

//	printf("Color : \n");
	for (int i = 0; i <= max_var_name; i ++)
	{
		if (!VarEntry[i].lea_marked && VarEntry[i].func_name == func_name)
		{
//			printf("Var %d : %d\n", i, VarEntry[i].color);
		}
		else if (VarEntry[i].func_name == func_name || VarEntry[i].var_class == var_class_global_var || VarEntry[i].var_class == var_class_global_dat)
		{
			VarEntry[i].color = GlobalBaseColor + i;
//			printf("Var %d : %d\n", i, VarEntry[i].color);
		}
	}
}

int improve_phi(int phi1[RegCount], int phi2[RegCount], int qphi3[RegCount])
{
/*		for (int k = 0; k < RegCount; k ++)
		{
			printf("%d\t", phi1[k]);
		}
		printf("\n");
		for (int k = 0; k < RegCount; k ++)
		{
			printf("%d\t", phi2[k]);
		}
		printf("\n");*/
	int ret = 0;
	for (int i = 0; i < RegCount; i ++)
	{
		if (phi1[i] > -1 && phi1[i] < GlobalBaseColor)
		{
			int p = locatepos(phi1[i], phi2);
			if (phi2[i] == -1)
			{
				phi2[i] = phi1[i];
				if (p != -1) phi2[p] = -1;
				ret = 1;
			}
			else if (phi2[i] != phi1[i])
			{
				if (phi2[i] != -2 && phi2[i] < phi1[i])
				{
					if (p != -1) phi2[p] = phi2[i];
					phi2[i] = phi1[i];
					ret = 1;
				}
				else if (p == -1)
				{
					for (int j = 0; j < RegCount; j ++)
					{
						if (phi2[j] == -1)
						{
							phi2[j] = phi1[i];
							ret = 1;
							break;
						}
					}
				}
			}
		}
	}
/*	if (ret)
	{
		for (int k = 0; k < RegCount; k ++)
		{
			printf("%d\t", phi1[k]);
		}
		printf("\n");
		for (int k = 0; k < RegCount; k ++)
		{
			printf("%d\t", phi2[k]);
		}
		printf("********\n\n");
	}*/
	return ret;
}

int ListCheckPhiInLive(list <int>& A, int num)
{
	if (num >= GlobalBaseColor)
	{
		return 1;
	}
	for (list <int> :: iterator p = A.begin(); p != A.end(); p ++)
	{
		if (VarEntry[*p].color == num)
		{
			return 1;
		}
	}
	return 0;
}

void allocate(int phi[RegCount], list <int>& vars, list <int>& varreg, list <int>& live, int work_space[RegCount])
{
	int fixed[RegCount], order[RegCount];
	memset(fixed, 0, sizeof(fixed));
	for (int i = 0; i < RegCount; i ++) order[i] = i;
/*	for (int i = 0; i < RegCount * 2; i ++)
	{
		int p = rand() % RegCount, q = rand() % RegCount;
		int tmp = order[p]; order[p] = order[q]; order[q] = tmp;
	}*/
	list <int> :: iterator q = varreg.begin();
	for (list <int> :: iterator p = vars.begin(); p != vars.end(); p ++, q ++)
	{
		int find = 0, color = (*p == -1 ? -1 : VarEntry[*p].color);
		for (int i = 0; i < RegCount; i ++)
		{
			if (phi[i] == color)
			{
				fixed[i] = 1;
				find = 1; 
				*q = i;
				break;
			}
		}

		if (find) continue;

		int target = -1;
		for (int j = 0; j < RegCount; j ++)
		{
			int i = order[j];
			if (!fixed[i] && (phi[i] >= -1) && (phi[i] == -1 || !ListCheckPhiInLive(live, phi[i])))
			{
				target = i;
				*q = i;
				break;
			}
		}
		if (target != -1)
		{
			phi[target] = color;
			fixed[target] = 1;
			continue;
		}

		for (int j = 0; j < RegCount; j ++)
		{
			int i = order[j];
			if (!fixed[i] && (target == -1 || phi[target] < phi[i]))
			{
				target = i;
				*q = i;
			}
		}

		phi[target] = color;
		fixed[target] = 1;
	}
	for (int i = 0; i < RegCount; i ++) work_space[i] |= fixed[i];
}

void make_phi(int func_name)
{
	int times = 0;
	for (list <TTACEntry> :: iterator p = FuncEntry[func_name].ins.begin(); p != FuncEntry[func_name].ins.end(); p ++)
	{
		times ++;
	}
	int changed = 1;
	while (changed && times > 0)
	{
		times --;
		changed = 0;
		for (list <TTACEntry> :: iterator p = FuncEntry[func_name].ins.begin(); p != FuncEntry[func_name].ins.end(); p ++)
		{
			if (p->op == "ASM" || p->op == "RREAD" || p->op == "RWRITE")
			{
				for (int i = 0; i < RegCount; i ++) p->phi1[i] = p->phi2[i] = p->phi3[i] = -2;
				continue;
			}

			if (p->op == "RICALL" || p->op == "ASM" || p->op == "RREAD" || p->op == "RWRITE")
			{
				for (int i = 0; i < RegCount; i ++) p->phi1[i] = -2;