公共表达式优化.txt

这是编译原理的源代码

		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  CeccOpti::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  CeccOpti::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);
}


/****************************************************/
/* 函数名  FindTempEqua								*/
/* 功  能  查找临时变量等价表						*/
/* 说  明  										    */
/****************************************************/
Cglobal::TempEqua  *CeccOpti::FindTempEqua(ArgRecord *arg)
{	 
	TempEqua  *Item = tempEquaT ;
	while (Item!=NULL)
	{ /*注：因为是临时变量，故这里可以直接使用指针比较
		    而一般变量则不行，因为同一个变量可能会产生
		    多个内容相同的ARG结构，根据中间代码生成时的
		    处理手段*/
	  if (Item->arg1 == arg)
	     break;
	  Item = Item->next;
	}
   return (Item);
}


	
/****************************************************/
/* 函数名  SearchValuNum							*/
/* 功  能  查找编码表								*/
/* 说  明  若存在于编码表中返回入口地址；否则返回空 */
/****************************************************/
Cglobal::ValuNum *CeccOpti::SearchValuNum(ArgRecord  *arg)
{   
	bool  equal = false;
    /*指向编码表*/
	ValuNum  *Item = valuNumT;
	while (Item != NULL)
	{   /*比较是否有相同的变量*/  
		equal = IsEqual(Item->arg,arg);
        if  (equal)
			  break;

		Item = Item->next;
	}
    return(Item);
}


/****************************************************/
/* 函数名  IsEqual									*/
/* 功  能  判断两个ARG结构是否相同					*/
/* 说  明  这里运算分量没有标号，故只考虑了常量类	*/
/*		   和地址类ARG结构							*/
/****************************************************/
bool  CeccOpti::IsEqual(ArgRecord *arg1,ArgRecord  *arg2)
{
  bool  equal = false ;
  /*注：应比较ARG结构内容，不能比较指针，因为一个相同的变量
        可能会产生多个相同的ARG结构，由不同的指针指向，这是
		由中间代码生成时的处理策略决定的*/
  if (arg1->form == arg2->form)
	switch(arg1->form)
	{/*常数类：值相等则等价*/
     case  ValueForm : 
	     if (arg1->Attr.value == arg2->Attr.value)
				equal = true ;
		 break;
	 /*地址类：层数，偏移，访问方式都相等时等价*/
	 case  AddrForm:
		 if ((arg1->Attr.addr.dataLevel == arg2->Attr.addr.dataLevel)
	        &&(arg1->Attr.addr.dataOff == arg2->Attr.addr.dataOff)
			&&(arg1->Attr.addr.access == arg2->Attr.addr.access))
			   equal  = true ;
		 break;
	 default :break;
	}
	return (equal);
}
				
/****************************************************/
/* 函数名  AppendValuNum							*/
/* 功  能  当前变量及值写入值编码表中				*/
/* 说  明  申请一个新节点，根据变量是否为间接临时变 */
/*		   填写不同的内容，并联入表中				*/
/****************************************************/
void  CeccOpti::AppendValuNum(ArgRecord *arg , int  Vcode)
{   
    /*最后一个节点指针*/
	ValuNum  *last ;
	/*申请一个新的值编码表的节点,并填写内容*/
	ValuNum  *newItem = (ValuNum  *)malloc(sizeof(ValuNum));
	newItem->arg = arg ;
	newItem->next = NULL;
	/*若是间接临时变量*/
    if (arg->form == AddrForm )
		if (arg->Attr.addr.dataLevel == -1)
			if (arg->Attr.addr.access == indir )
			{ 
				newItem->access = indir ;
				newItem->codeInfo.twoCode.valuecode = Vcode;
				newItem->codeInfo.twoCode.addrcode = Vcode;

				goto  L1;
			}
   /*其余情况为：非间接临时变量*/
		
		  newItem->access = dir;
	      newItem->codeInfo.valueCode = Vcode;
	
L1:  /*节点联入值编码表中*/
    if (valuNumT == NULL)
		valuNumT = newItem;
	else 
	{  last = valuNumT ;
		while (last->next!=NULL)
			last = last->next;
	    last->next = newItem;
	}
}

/****************************************************/
/* 函数名  FindECC									*/
/* 功  能  判断可用表达式表中是否有可用的表达式代码 */
/* 说  明  若有，返回用于替换的中间代码指针			*/
/*		   否则，返回为空							*/
/****************************************************/
Cglobal::CodeFile *CeccOpti::FindECC(CodeKind  codekind,int  op1Code, int  op2Code)
{   
	CodeFile  * substiCode =NULL;
	UsableExpr  *currentItem = usableExprT;

	while ((currentItem != NULL)&&(substiCode==NULL))
	{   /*语句类别相同*/
		if (currentItem->code->codeR.codekind == codekind )
			/*对应分量编码都相同,可替换*/
			if ((currentItem->mirrorC->op1== op1Code)&&(currentItem->mirrorC->op2 == op2Code))
					substiCode = currentItem->code;
			else
				/*可交换运算符，分量编码交叉相同，也可替换*/
				if ((codekind ==ADD)||(codekind == MULT))
		 	 		if ((currentItem->mirrorC->op1== op2Code)&&(currentItem->mirrorC->op1 == op2Code))
								substiCode = currentItem->code;

		currentItem = currentItem->next;
	}
	return (substiCode);
}
	

/****************************************************/
/* 函数名  AppendTempEqua							*/
/* 功  能  将两个等价的临时变量写入临时变量等价表中	*/
/* 说  明  表示第一项可以被第二项替换				*/
/****************************************************/
void  CeccOpti::AppendTempEqua(ArgRecord  *arg1,ArgRecord  *arg2)
{
   /*最后一个节点指针*/
	TempEqua  *last ;
	/*申请一个新的临时变量等价表的节点,并填写内容*/
	TempEqua  *newItem = (TempEqua  *)malloc(sizeof(TempEqua));
	newItem->arg1 = arg1;
	newItem->arg2 = arg2;
	newItem->next = NULL;

   /*节点联入临时变量等价表中*/
    if (tempEquaT == NULL)
		tempEquaT = newItem;
	else 
	{  last = tempEquaT ;
		while (last->next!=NULL)
			last = last->next;
	    last->next = newItem;
	}
}

/****************************************************/
/* 函数名  GenMirror								*/
/* 功  能  构造映象码								*/
/* 说  明											*/
/****************************************************/
Cglobal::MirrorCode * CeccOpti::GenMirror(int op1,int op2,int result)
{
	MirrorCode  *mirror = (MirrorCode *) malloc (sizeof(MirrorCode));
	mirror->op1 = op1;
	mirror->op2 = op2;
	mirror->result = result ;

	return (mirror);
}

/****************************************************/
/* 函数名  AppendUsExpr								*/
/* 功  能  将中间代码和相应的映象码写可用表达式表中	*/
/* 说  明											*/
/****************************************************/	
void  CeccOpti::AppendUsExpr(CodeFile  *code,MirrorCode  *mirror)
{
	UsableExpr  *last ;
	UsableExpr  *newItem = (UsableExpr  *)malloc(sizeof(UsableExpr));
	newItem->code = code;
    newItem->mirrorC = mirror;
	newItem->next = NULL;

	if (usableExprT==NULL)
		usableExprT = newItem ;
	else 
	{ last = usableExprT ;
	  while (last->next!=NULL)
		  last = last->next ;
	  last->next = newItem;
	}
}

/****************************************************/
/* 函数名  SubstiVcode								*/
/* 功  能  将当前变量，及其值编码写入编码表			*/
/* 说  明  若变量首次出现，则添加一项；否则，将表中	*/
/*		   此变量的值编码替换为新的值编码			*/
/****************************************************/	
void  CeccOpti::SubstiVcode(ArgRecord  *arg,int Vcode)
{
	ValuNum  *Entry = SearchValuNum(arg );
	/*若操作数首次出现，则填入编码表*/
	if( Entry==NULL)
		  AppendValuNum(arg , Vcode);
	else 
	{ 
		/*间接临时变量*/
	   if (Entry->access == indir)
			Entry->codeInfo.twoCode.valuecode = Vcode;				
		/*非间接临时变量*/
	   else    Entry->codeInfo.valueCode = Vcode;
	}
		
}

/****************************************************/
/* 函数名  DelUsExpr								*/
/* 功  能  将可用表达式代码表中用到arg的值编码的项  */
/*		   删除										*/
/* 说  明											*/
/****************************************************/	
void CeccOpti::DelUsExpr(ArgRecord  *arg)
{
	bool  same = false ;
	UsableExpr  *Item = usableExprT;
	UsableExpr  *former = Item ;  
    while (Item!=NULL)
	{   /*因为AADD用的是地址码，所以不考虑*/
		if (Item->code->codeR.codekind!=AADD)
		{ if (Item->code->codeR.arg1==arg)
				same = true;
		  else if (Item->code->codeR.arg2 == arg)
			       same = true;
			   else  if (Item->code->codeR.arg3 == arg)
							same = true;
		  if (same) 
		  { /*删除这个可用表达式项*/ 
			  if (Item == usableExprT)
			  {  usableExprT = Item->next;
			     free(Item);
				 former = Item = usableExprT;
			  }
			  else 
			  {  former->next = Item->next;
			     free(Item);
				 Item = former->next;
			  }
              /*跳到下一次循环开始处*/
		      continue;
		  }
		}
      /*指针后移，比较下一个节点*/
	  former = Item;
	  Item = Item->next;
	}
}