optimizer.java

北航编译原理课程设计成果——一个扩充的C0文法编译器

package cn.edu.buaa.scse.liyi.compile.tools;

import java.io.File;
import java.util.LinkedList;
import java.util.TreeMap;

import cn.edu.buaa.scse.liyi.compile.types.DataFlow;
import cn.edu.buaa.scse.liyi.compile.types.Function;
import cn.edu.buaa.scse.liyi.compile.types.Quaternion;

/**
 * 
 * @author liyi
 */
public class Optimizer
{
	private LinkedList<Function> funcList=null;
	
	/**
	 * 中间代码优化器构造方法
	 * @param funcList
	 */
	public Optimizer(LinkedList<Function> funcList)
	{
		this.funcList=new LinkedList<Function>(funcList);
	}

	public void setFuncList(LinkedList<Function> funcList)
	{
		this.funcList=funcList;
	}
	public LinkedList<Function> getFuncList()
	{
		return funcList;
	}
	
	//判断一个字符串的内容是否为一个整数
	private boolean isInteger(String str)
	{
		try
		{
			Integer.parseInt(str);
		}
		catch(Exception e)
		{
			return false;
		}
		return true;
	}
	
	/**
	 * 基本块内部的公共子表达式删除
	 */
	private void deleteCommonSubexpression()
	{
		//常量合并，复制传播，公共子表达式删除
		for(int n=0;n<funcList.size();n++)
		{
			Function curfunc=funcList.get(n);
			LinkedList<Quaternion> quaterList=new LinkedList<Quaternion>();
			
			for(int i=0;i<curfunc.getQuaterList().size();i++)
			{
				Quaternion quater=curfunc.getQuaterList().get(i);
				if(quater==null)
					continue;
				else if((quater.getOperator()>=Yacc.ADD)&&(quater.getOperator()<=Yacc.DIV))
				{
					if(isInteger(quater.getOperend1())&&isInteger(quater.getOperend2()))
					{
						Integer result=0;
						int operend1=Integer.parseInt(quater.getOperend1());
						int operend2=Integer.parseInt(quater.getOperend2());
						
						switch (quater.getOperator())
						{
							case Yacc.ADD:
								result=new Integer(operend1+operend2);
								break;
							case Yacc.SUB:
								result=new Integer(operend1-operend2);
								break;
							case Yacc.MUL:
								result=new Integer(operend1*operend2);
								break;
							case Yacc.DIV:
								result=new Integer(operend1/operend2);
								break;
						}
						curfunc.getQuaterList().set(i,null);
						for(int j=i+1;j<curfunc.getQuaterList().size();j++)
						{
							Quaternion reg0=curfunc.getQuaterList().get(j);
							if(reg0==null)
								continue;
							else if(((reg0.getOperator()>=Yacc.ADD)&&(reg0.getOperator()<=Yacc.DIV)))
							{
								if(reg0.getOperend1().equals(quater.getResult()))
								{
									reg0.setOperend1(result.toString());
									curfunc.getQuaterList().set(j,reg0);
								}
								else if(reg0.getOperend2().equals(quater.getResult()))
								{
									reg0.setOperend2(result.toString());
									curfunc.getQuaterList().set(j,reg0);
								}
							}
							else if((reg0.getOperator()==Yacc.MOV)&&(reg0.getOperend1().equals(quater.getResult())))
							{
								reg0.setOperend1(result.toString());
								curfunc.getQuaterList().set(j,reg0);
							}
							else
								break;
						}
					}
					else
					{
						for(int j=i+1;j<curfunc.getQuaterList().size();j++)
						{
							Quaternion reg1=curfunc.getQuaterList().get(j);
							if(reg1==null)
								continue;
							else if(((reg1.getOperator()>=Yacc.ADD)&&(reg1.getOperator()<=Yacc.DIV)))
							{
								if(quater.equivalents(reg1))
								{
									curfunc.getQuaterList().set(j,null);
									
									for(int k=j+1;k<curfunc.getQuaterList().size();k++)
									{
										Quaternion reg2=curfunc.getQuaterList().get(k);
										if(reg2==null)
											continue;
										else if(((reg2.getOperator()>=Yacc.ADD)&&(reg2.getOperator()<=Yacc.DIV)))
										{
											if(reg2.getOperend1().equals(reg1.getResult()))
											{
												reg2.setOperend1(quater.getResult());
												curfunc.getQuaterList().set(k,reg2);
											}
											else if(reg2.getOperend2().equals(reg1.getResult()))
											{
												reg2.setOperend2(quater.getResult());
												curfunc.getQuaterList().set(k,reg2);
											}
										}
										else if((reg2.getOperator()==Yacc.MOV)&&(reg2.getOperend1().equals(reg1.getResult())))
										{
											reg2.setOperend1(quater.getResult());
											curfunc.getQuaterList().set(k,reg2);
										}
										else
											break;
									}
								}
							}
							else if((reg1.getOperator()==Yacc.MOV)&&(reg1.getResult().equals(quater.getOperend1())||reg1.getResult().equals(quater.getOperend2())))
							{
								break;
							}
							else if((reg1.getOperator()==Yacc.SCANF)&&(reg1.getOperend1().equals(quater.getOperend1())||reg1.getOperend1().equals(quater.getOperend2())))
							{
								break;
							}
						}
					}
				}
			}
			
			for(Quaternion quater:curfunc.getQuaterList())
			{
				if(quater!=null)
				{
					quaterList.add(quater);
				}
			}
			
			curfunc.setQuaterList(quaterList);
			funcList.set(n,curfunc);
		}
		
		//冗余的赋值操作删除
		for(int i=0;i<funcList.size();i++)
		{
			Function func=funcList.get(i);
			LinkedList<Quaternion> quaterList=func.getQuaterList();
			TreeMap<String,Integer> vmap=new TreeMap<String,Integer>();
			
			for(int j=0;j<quaterList.size();j++)
			{
				Quaternion quater=quaterList.get(j);
				if((quater.getOperator()>=Yacc.ADD)&&(quater.getOperator()<=Yacc.DIV)&&quater.getResult().startsWith("@"))
				{
					Quaternion reg1=quaterList.get(j+1);
					if((reg1.getOperator()==Yacc.MOV)&&reg1.getOperend1().equals(quater.getResult()))
					{
						boolean flag=false;
						for(int k=j+2;k<quaterList.size();k++)
						{
							Quaternion reg2=quaterList.get(k);
							if(quater.getResult().equals(reg2.getOperend1())||quater.getResult().equals(reg2.getOperend2()))
							{
								flag=true;
								break;
							}
						}
						if(!flag)
						{
							funcList.get(i).getQuaterList().get(j).setResult(reg1.getResult());
							funcList.get(i).getQuaterList().remove(j+1);
						}
					}
				}
			}
			
			int len=1;
			
			for(String var:funcList.get(i).getVar())
			{
				vmap.put(var,len*4);
				len++;
			}
			
			for(Quaternion quater:quaterList)
			{
				if(quater!=null)
				{
					if(quater.getResult()!=null&&quater.getResult().startsWith("@"))
					{
						vmap.put(quater.getResult(),len*4);
						len++;
					}
				}
			}
			
			funcList.get(i).setVmap(vmap);
		}
	}
	
	/**
	 * 无用代码删除
	 */
	private void deleteUselessCode()
	{
		boolean flag=false;
		boolean turn=true;
		
		while(turn)
		{
			int i=0;
			turn=false;
			for(Function fcheck=funcList.get(i);i<funcList.size();fcheck=funcList.get(i))
			{
				flag=false;
				if(fcheck.getName().equals("main"))
					break;
				for(Function func:funcList)
				{
					if(fcheck.getName().equals(func.getName()))
						continue;
					else
					{
						for(Quaternion quater:func.getQuaterList())
						{
							if(quater.getOperator()==Yacc.CALL&&quater.getOperend1().equals(fcheck.getName()))
							{
								flag=true;
								break;
							}	
						}
						if(flag)
							break;
					}
				}
				if(!flag)
				{
					funcList.remove(fcheck);
					turn=true;
				}
				else
					i++;
			}
		}
	}
	
	/**
	 * 多种优化策略综合处理
	 */
	public void process()
	{
		deleteUselessCode();
		deleteCommonSubexpression();
	}
	
	public static void main(String argv [])
	{
		File file=new File("D:/test11.txt");
		Lex lex=new Lex(file);
		lex.analyze();
		Yacc yacc=new Yacc(lex.getList());
		yacc.parseProgram();
		Optimizer opti=new Optimizer(yacc.getFuncList());
		opti.deleteCommonSubexpression();
		for(Function func:opti.getFuncList())
		{
			DataFlow flow=new DataFlow(func.getQuaterList());
			flow.buidDiagram();
			System.out.println("四元式");
			Quaternion quater;
			while((quater=flow.nextTrank())!=null)
				System.out.println(quater);
		}
	}
}