copyprop.java

用Java实现的编译器。把源代码编译成SPARC汇编程序

/**
*This class is used for expressions using the AND operation.
*This class extends the Exp abstract class
**/
package CatDecaf.Optimizer;
import CatDecaf.IR.*;
import CatDecaf.Utilities.*;
import java6035.tools.ASM.*;
import java.io.*;
import java.util.*;
import CatDecaf.SymTable.*;
import parser.*;
public class CopyProp implements Visitor{

//public static boolean optFlag;
//public static HashSet loopKillSet;==========big mistake!!!!!!
public static CopyTable curCopyTable;
public static int count;
public static boolean newOptDone;

	/*public CopyProp(){
		curCopyTable = new LinkedHashMap();
	}*/
	

	
	public void visit(Ir n){        } //abstract class
	public void visit(IrProg n){
		
		newOptDone = false;
		if(n.fdDeclList_!=null)
			n.fdDeclList_.accept(this);
		if(n.mdDeclList_ == null) System.out.println("ERROR!!!!!!!!!!!!!!!!!!!!!!!!!!");
			n.mdDeclList_.accept(this);  //this should never be empty

	}
	public void visit(FdDeclList n){ //not printing List classes
		while(n!= null)
		{	
			n.fdDecl_.accept(this);
			n = n.fdDeclList_;
		}
	}
	public void visit(FdDecl n){
		if(n.glbVarList_==null) System.out.println("ERROR!!!!!!!!!!!!!!!");
		n.typ_.accept(this);
		n.glbVarList_.accept(this);
	}
	public void visit(GlbVar n){ } //abstract class
	public void visit(GlbVarArray n){
		n.identifier_.accept(this);
		n.ltrInt_.accept(this);
	}	
	public void visit(GlbVarId n){
		n.identifier_.accept(this);
	}	
	public void visit(GlbVarList n){ //not printing List classes
		while(n!= null)
		{	
			n.glbVar_.accept(this);
			n = n.glbVarList_;
		}
	}	
	public void visit(Typ n){	}	//abstract class
	public void visit(TypInt n){
	}
	public void visit(TypBool n){
	}
	public void visit(TypVoid n){
	}
	public void visit(MdDeclList n){ //not printing List classes
		while(n!= null)
		{	
			n.mdDecl_.accept(this);
			n = n.mdDeclList_;
		}
	}	
	public void visit(MdDecl n){
		curCopyTable = new CopyTable();curCopyTable.optFlag = true;
		n.typ_.accept(this);
		n.identifier_.accept(this);
		if(n.mdParaList_ !=null){ //method parameter list could be NULL
			n.mdParaList_.accept(this);
		}
		n.block_.accept(this);
	}	
	public void visit(MdParaList n){ //not printing List classes
		while(n!= null)
		{	
			n.mdPara_.accept(this);
			n = n.mdParaList_;
		}
	}	
	public void visit(MdPara n){
		n.typ_.accept(this);
		n.identifier_.accept(this);
	}	
	public void visit(Block n){
		if(n.varDeclList_!=null) //var declaration list could be empty
			n.varDeclList_.accept(this);
		if(n.stmtList_!=null)//list can be empty
			n.stmtList_.accept(this);
	}
	public void visit(VarDecl n){
		n.typ_.accept(this);
		if(n.locVarList_==null) System.out.println("ERROR!!!!!!!!!!!!!!!");
		n.locVarList_.accept(this);
	}	
	public void visit(VarDeclList n){ //not printing List classes
		while(n!= null)
		{	
			n.varDecl_.accept(this);
			n = n.varDeclList_;
		}
	}
	public void visit(LocVar n){
		n.identifier_.accept(this);
	}	
	public void visit(LocVarList n){ //not printing List classes
		while(n!= null)
		{	
			n.locVar_.accept(this);
			n = n.locVarList_;
		}
	}
	public void visit(StmtList n){ //not printing List classes
		while(n!= null)
		{	
			n.stmt_.accept(this);
			n = n.stmtList_;
		}
	}
	public void visit(Stmt n){	}	 //abstract class

	
/************************************************************************************************/
// You may take the above code as a reference
/***********************************************************************************************/
/*
	public void visit(StmtLocation n){
		if(n.location_ instanceof LocationId && (n.exp_ instanceof LtrInt || n.exp_ instanceof LtrBoolTrue || n.exp_ instanceof LtrBoolFalse )){
			LocationId lid = (LocationId)n.location_;
			Exp e = n.exp_;
			//check whether idd already there and whther value changed
			Object o=null;
			boolean valueUnchanged = true;
			if ((o = curCopyTable.lookupValue(lid.idd)) != null){
				if(loopKillSet == null || !loopKillSet.contains(lid.idd)){
					//n.copyResult = (Exp) o;
					//clone a new object here is always safe so that no conflict in register allocation
					if(o instanceof LtrInt) valueUnchanged = ((LtrInt)o).ltrInt_ == ((LtrInt)e).ltrInt_ ;
					else if(o instanceof LtrBoolFalse) valueUnchanged = e instanceof LtrBoolFalse;
					else if(o instanceof LtrBoolTrue) valueUnchanged = e instanceof LtrBoolTrue;
				}
			}
			if (o!=null && valueUnchanged ) {//idd already there, check whether new assignment gives a different value
				//idd there and same, keep it
				return;
			}else{//idd not there or different then kill
				curCopyTable.table.put(lid.idd, n.exp_);
				if(curCopyTable.checkIDDInParents(lid.idd)) curCopyTable.killSet.add(lid.idd);	// to be killed by this block's parent
			}
		}else{			
			n.exp_.accept(this);
			if(n.exp_.copyResult != null) n.exp_ = n.exp_.copyResult;
			if(n.location_ instanceof LocationId){
				LocationId lid = (LocationId)n.location_;
				if(n.exp_ instanceof LtrInt || n.exp_ instanceof LtrBoolTrue || n.exp_ instanceof LtrBoolFalse )	{				
					Exp e = n.exp_;
					//check whether idd already there and whther value changed
					Object o=null;
					boolean valueUnchanged = true;
					if ((o = curCopyTable.lookupValue(lid.idd)) != null){
						if(loopKillSet == null || !loopKillSet.contains(lid.idd)){
							//n.copyResult = (Exp) o;
							//clone a new object here is always safe so that no conflict in register allocation
							if(o instanceof LtrInt) valueUnchanged = ((LtrInt)o).ltrInt_ == ((LtrInt)e).ltrInt_ ;
							else if(o instanceof LtrBoolFalse) valueUnchanged = e instanceof LtrBoolFalse;
							else if(o instanceof LtrBoolTrue) valueUnchanged = e instanceof LtrBoolTrue;
						}
					}
					if (o!=null && valueUnchanged ) {//idd already there, check whether new assignment gives a different value
						//idd there and same, keep it
						return;
					}else{//idd not there or different then kill
						curCopyTable.table.put(lid.idd, n.exp_);
						if(curCopyTable.checkIDDInParents(lid.idd)) curCopyTable.killSet.add(lid.idd);	// to be killed by this block's parent
					}
				}
				else{	//remove from constant table				
					curCopyTable.table.remove(lid.idd); //no more a constant
					if(curCopyTable.checkIDDInParents(lid.idd)) curCopyTable.killSet.add(lid.idd);  //to be kicked out in parent's constant table
				}
			}	
		}
		
		
	}
	
/************************************************************************************************/
// You may take the above code as a reference
/***********************************************************************************************/
	
	
	public void visit(StmtLocation n){
		/*if(n.location_ instanceof LocationId && (n.exp_ instanceof LtrInt || n.exp_ instanceof LtrBoolTrue || n.exp_ instanceof LtrBoolFalse )){
			LocationId lid = (LocationId)n.location_;
			
			if(curCopyTable.table.containsKey(lid.idd)) curCopyTable.table.put(lid.idd, n.exp_);//must overwrite
			if(!curCopyTable.checkIDDInParents(lid.idd, n.exp_)){
				curCopyTable.table.put(lid.idd, n.exp_);				
				if(curCopyTable.loopKillSet != null && curCopyTable.loopKillSet.contains(lid.idd))
					curCopyTable.loopKillSet.remove(lid.idd);
					
				if(curCopyTable.checkIDDInParents(lid.idd)) curCopyTable.killSet.add(lid.idd);	// to be killed by this block's parent
			}
		}else{*/
			n.exp_.accept(this);
			if(n.exp_.copyResult != null) n.exp_ = n.exp_.copyResult;

			//special case, x=x, completely ignored, nothing to optimize or to change
			if(n.location_ instanceof LocationId && n.exp_ instanceof LocationId ){
				if (((LocationId)n.location_).idd == ((LocationId)n.exp_).idd) return;
			}
			
			if(n.location_ instanceof LocationId){
				LocationId lid = (LocationId)n.location_;
				if(n.exp_ instanceof LocationId){				
					if(curCopyTable.table.containsKey(lid.idd)) curCopyTable.table.put(lid.idd, ((LocationId)n.exp_).idd);//must overwrite
					if(!curCopyTable.checkIDDInParents(lid.idd, ((LocationId)n.exp_).idd)){
						curCopyTable.table.put(lid.idd, ((LocationId)n.exp_).idd);
						
						if(curCopyTable.loopKillSet != null && curCopyTable.loopKillSet.contains(lid.idd))
							curCopyTable.loopKillSet.remove(lid.idd);
							
						if(curCopyTable.checkIDDInParents(lid.idd)) curCopyTable.killSet.add(lid.idd);  //to be kicked out in parent's constant table
					}
				}
				else{	//remove from constant table				
					curCopyTable.table.remove(lid.idd); //no more a constant
					if(curCopyTable.checkIDDInParents(lid.idd)) curCopyTable.killSet.add(lid.idd);  //to be kicked out in parent's constant table
				}

				//handle it's an assignment to the right, ie, the value is modifified
				//if lid is a value, then find all keys and remove them all;
				//curCopyTable.removeAllKeysFromAllTablesContainingValue(lid.idd);
				//instead of doing the above, we remove from current table, and add to killset
				//get a list of the keys that contains those values.
				
				Set keys = new HashSet();
				curCopyTable.getAllKeysFromAllTablesContainingValue(lid.idd, keys);
				for(Iterator i = keys.iterator(); i.hasNext();){
					IDDescriptor idd = (IDDescriptor)i.next();
					curCopyTable.table.remove(idd);
					if(curCopyTable.checkIDDInParents(idd)) curCopyTable.killSet.add(idd);

				}
				
			}	
		//}
		
		
	}

	public void visit(StmtBlock n){
		n.block_.accept(this);
	}	
	public void visit(StmtMdCall n){
		n.mdCall_.accept(this);
	}	
	public void visit(Location n){	}	//abstract class
	public void visit(LocationId n){
		if(curCopyTable.optFlag){
			Object o;
			if((o = curCopyTable.lookupValue(n.idd)) != null){
				IDDescriptor idd = (IDDescriptor)o;
				if(curCopyTable.loopKillSet == null || !curCopyTable.loopKillSet.contains(n.idd)){
					//n.copyResult = (Exp) o;
					//clone a new object here is always safe so that no conflict in register allocation					
					n.copyResult = new LocationId(new Identifier(idd.getName(), idd.getType(), idd.getOffset(), idd.isGlobal(), idd.isParam()));
					newOptDone = true;
				}
			}
		}
		
	}
	public void visit(LocationArray n){
		
		n.exp_.accept(this);
		if(n.exp_.copyResult != null) n.exp_ = n.exp_.copyResult;
		
	}
	public void visit(CallOutArgList n){ //not printing List classes
		while(n!= null)
		{	
			n.callOutArg_.accept(this);
			n = n.callOutArgList_;
		}
	}
	public void visit(CallOutArg n){	}	//abstract class
	public void visit(CallOutArgExp n){
		n.exp_.accept(this);
		if(n.exp_.copyResult != null) n.exp_ = n.exp_.copyResult;
	}
	public void visit(CallOutArgStr n){
		n.ltrString_.accept(this);
	}
	public void visit(MdCall n){	}	//abstract class
	public void visit(MdCallOut n){
		n.ltrString_.accept(this);
		if(n.callOutArgList_!=null) //could be empty
			n.callOutArgList_.accept(this);
	}
	public void visit(MdCallIn n){
		n.identifier_.accept(this);
		if(n.expList_!=null) //could be empty
			n.expList_.accept(this);
	}	
	public void visit(ExpList n){ //not printing List classes
		while(n!= null)
		{	
			n.exp_.accept(this);
			if(n.exp_.copyResult != null) n.exp_ = n.exp_.copyResult;
			n = n.expList_;
		}
	}
	public void visit(StmtForLoop n){
		//========id1 = expr1========n.exp1_.accept(this);
		
		n.exp1_.accept(this);
		if(n.exp1_.copyResult != null) n.exp1_ = n.exp1_.copyResult;

		//special case, x=x, completely ignored, nothing to optimize or to change
		if(n.exp1_ instanceof LocationId &&  n.idd1_ == ((LocationId)n.exp1_).idd){
			//do nothing, no optimization
		}else{