eccsaving.cpp

snl语言是一个简单的具有嵌套过程定义的过程式语言

/****************************************************/
/* 文件 ECCsaving.cpp								*/
/*													*/
/* 说明 TINY编译器中间代码的公共表达式优化实现		*/
/****************************************************/

#include "globals.h"		/* 该头文件定义全局类型和变量 */

#include "util.h"			/*该头文件定义了一些实用函数*/

#include "Eccsaving.h"		/* 该头文件声明了公共表达式优化界面函数*/

/* 值编码表 */
ValuNum     *valuNumT = NULL;
/* 可用表达式代码表 */
UsableExpr  *usableExprT = NULL;
/* 临时变量的等价表 */
TempEqua    *tempEquaT = NULL;

/*记录值编码*/
int  Vnumber= 0;


/**********函数声明***************/

int		     NewVN();

CodeFile    *ECCsave();

void	     SaveInBlock(int i);

void	     EquaSubsti(CodeFile *code);

TempEqua    *FindTempEqua(ArgRecord *arg);

int		     Process(CodeFile  *code , int  i);

ValuNum     *SearchValuNum(ArgRecord  *arg);

bool         IsEqual(ArgRecord *arg1,ArgRecord  *arg2);

void	     AppendValuNum(ArgRecord *arg , int  Vcode);

CodeFile    *FindECC(CodeKind  codekind,int  op1Code, int  op2Code);

void	     AppendTempEqua(ArgRecord  *arg1,ArgRecord  *arg2);

MirrorCode  *GenMirror(int op1,int op2,int result);

void		 AppendUsExpr(CodeFile  *code,MirrorCode  *mirror);

void		 SubstiVcode(ArgRecord  *arg,int Vcode);

void		 DelUsExpr(ArgRecord  *arg);

/********************************************************/
/* 函数名  NewVN		  								*/
/* 功  能  产生一个新的值编码							*/
/* 说  明  通过全局变量Vnumber加1，产生新的值编码		*/
/********************************************************/
int  NewVN()
{  Vnumber++;  
   return (Vnumber);
}

/****************************************************/
/* 函数名  ECCsave									*/
/* 功  能  公共表达式优化主函数    					*/
/* 说  明  循环对各个基本块进行公共表达式优化	    */
/****************************************************/
/*注：考虑将blocknum用作局部变量，全局变量封装不好*/

CodeFile  *ECCsave()
{ 
	ValuNum  *freeVN = NULL;
	UsableExpr  *freeUE = NULL;
	TempEqua  *freeTE = NULL;
	/*调用划分基本块函数*/
	int  blocknum = DivBaseBlock() ;

    //PrintBaseBlock(blocknum);
	//getchar( );

    /*循环对每个基本块进行公共表达式优化*/
	for (int i=0 ; i<blocknum ;i++)
	{  /*基本块入口处置值编码表，
		 可用表达式表，临时变量等价表为空*/
	   valuNumT = NULL;
	   usableExprT = NULL;
	   tempEquaT = NULL;

	   /*基本块的ECC节省*/
       SaveInBlock(i);

	   /*打印三个表*/
	   //printValuNum();
	   //printUsbleExpr();
	   //printTempEqua();

	   /*释放此基本块占用的表空间*/
		while (valuNumT!=NULL)
		{ freeVN = valuNumT ;
          valuNumT = valuNumT->next;
		  free(freeVN);
		}
		while (usableExprT!=NULL)
		{ freeUE = usableExprT;
		  usableExprT = usableExprT->next;
		  free(freeUE);
		}
        while(tempEquaT!=NULL)
		{ freeTE = tempEquaT;
		  tempEquaT = tempEquaT->next;
		  free(freeTE);
		}

	}
	/*返回优化后的中间代码*/
	return(firstCode);

}

/****************************************************/
/* 函数名  SaveInBlock								*/
/* 功  能  基本块优化函数	    					*/
/* 说  明										    */
/****************************************************/
void   SaveInBlock(int i)
{   
	int op1,op2,op3;
	/*可用的表达式代码*/
	CodeFile  *substiCode = NULL;
	ValuNum  *Entry = NULL;
	
	/*指向基本块第一条语句*/
	CodeFile *currentCode = baseBlock[i];
	CodeFile *formerCode = NULL;
	CodeFile *laterCode = NULL;

	/* 循环处理基本块中的各条语句*/
	while ((currentCode!=baseBlock[i+1])&&(currentCode!=NULL))
	{
		/*进行等价替换*/
		EquaSubsti(currentCode);

		switch(currentCode->codeR.codekind)
		{ case  ADD:
		  case  SUB:
          case  MULT:
   	      case  DIV:
		  case  LTC:
		  case  EQC: 
		  case  AADD:
			   /*调用函数Process处理分量1，返回分量1的编码*/
			   op1 = Process(currentCode ,1 );
			   /*调用函数Process处理分量2，返回分量2的编码*/
			   op2 = Process(currentCode ,2 );

				/*查找可用表达式代码表*/
				substiCode = FindECC(currentCode->codeR.codekind,op1,op2);
				/*若找到，当前代码可节省*/
				if (substiCode!=NULL)
				{ 
                  /*向临时变量等价表中添加一项*/
				  AppendTempEqua(currentCode->codeR.arg3,substiCode->codeR.arg3);
				  /*删除当前代码*/
				  formerCode = currentCode->former;
				  laterCode = currentCode->next;
				  if (formerCode!=NULL)
				  	  formerCode->next = laterCode;
				  if (laterCode!=NULL)
					  laterCode->former = formerCode; 
				  free(currentCode);
				  currentCode = formerCode;
				}				 
				else  /*没找到，代码不可节省*/
				{ 
				  /*为结果变量构造一个新的编码，填入值编码表*/
				  Vnumber++;
				  op3 = Vnumber;
				  AppendValuNum(currentCode->codeR.arg3,op3);
				  /*构造对应的映象码*/
				  MirrorCode *mirror = GenMirror(op1,op2,op3);
				  /*当前代码写入可用表达式代码表*/
				  AppendUsExpr(currentCode,mirror);
				}
				break;
		  case  ASSIG:
			    /*Process函数处理赋值右部，返回编码*/
			    op1 = Process(currentCode ,1 );
				
				/*若是间接临时变量，op1是地址码；否则，是值码*/
				op2 = op1;
				
				/*替换编码表中赋值左部的值编码*/
				SubstiVcode(currentCode->codeR.arg2, op2);

				/*删除可用表达式代码表中用到赋值左部值编码的项*/
				DelUsExpr(currentCode->codeR.arg2);
				break;

		  default:  break;
		}
		/*处理下一条代码*/
		currentCode = currentCode->next;
	}
}
/****************************************************/
/* 函数名  EquaSubsti								*/
/* 功  能  利用临时变量等价表对当前代码进行等价替换 */
/* 说  明  										    */
/****************************************************/
void  EquaSubsti(CodeFile *code)
{	
	TempEqua  *Entry = NULL ;
	if (code->codeR.arg1!=NULL)
		/*若操作数1是临时变量,且存在于临时变量等价表中，则替换*/
		if( code->codeR.arg1->form==AddrForm)
			if(code->codeR.arg1->Attr.addr.dataLevel == -1)
			{	Entry = FindTempEqua(code->codeR.arg1);
				if (Entry!=NULL)
					code->codeR.arg1 = Entry->arg2;
			}
    if (code->codeR.arg2!=NULL)
		/*若操作数2是临时变量,且存在于临时变量等价表中，则替换*/
		if( code->codeR.arg2->form==AddrForm)
			if(code->codeR.arg2->Attr.addr.dataLevel == -1)
			{	Entry = FindTempEqua(code->codeR.arg2);
				if (Entry!=NULL)
					code->codeR.arg2 = Entry->arg2;
			}
}

/****************************************************/
/* 函数名  Process									*/
/* 功  能  处理操作分量，并返回对应的编码			*/
/* 说  明  若首次出现，则分配新编码，填入编码表中， */
/*	       返回值取这个新的编码；否则，根据是否间接 */
/*	       变量，返回相应的值编码或地址码			*/	
/****************************************************/
int  Process(CodeFile  *code , int  i)
{
	ArgRecord  *arg;
	ValuNum  *Entry = NULL ;
	CodeKind  codekind = code->codeR.codekind;
	int  opC ;
	if (i==1)
			arg = code->codeR.arg1;
	else    arg = code->codeR.arg2;
	/*若操作数首次出现，则填入编码表*/
	Entry = SearchValuNum(arg);
	if( Entry==NULL)
	{ Vnumber++;
	  opC = Vnumber; /*op1记录操作数1的值编码*/
	  AppendValuNum(arg,opC);
	}
	else 
	{  
		/*间接临时变量*/
	   if (Entry->access == indir)
			/*用间接临时变量的地址码*/
			if((codekind == AADD)||(codekind == ASSIG))
					/*取地址码*/
					opC= Entry->codeInfo.twoCode.addrcode;
			else   /*否则，取值码*/
					opC = Entry->codeInfo.twoCode.valuecode;
		/*非间接临时变量*/
		else    opC = Entry->codeInfo.valueCode;
	}

	return (opC);
}