📄 公共表达式优化.txt

📁 中间代码的公共表达式优化算法,是编译原理学习的一个好例子
💻 TXT
📖 第 1 页 / 共 2 页
字号:
12 下一页
// eccOpti.cpp: implementation of the CeccOpti class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "face.h"
#include "eccOpti.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CeccOpti::CeccOpti()
{

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

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

CeccOpti::~CeccOpti()
{

}

/**********实用函数***************/

/********************************************************/
/* 函数名  DivBaseBlock									*/
/* 功  能  为中间代码划分基本块							*/
/* 说  明  基本块从0开始编号，若有变参传递，则相应过程  */
/*	       调用做为当前基本块的结束						*/
/********************************************************/
int  CeccOpti::DivBaseBlock(CodeFile *firstCode)
{   
	/*初始化基本块数目*/
	int blocknum = 0;
	
	CodeFile  *code = firstCode ;
    /*初始化基本块指针*/
	for (int i=0;i<100;i++)
		baseBlock[i]=NULL;

    baseBlock[blocknum++] =code;
	if (code->next != NULL)
	   code = code->next;

	while (code != NULL)
	{
	   switch(code->codeR.codekind)
	   {/*声明类的代码*/ 
	    case LABEL:
		case WHILESTART:
        case PENTRY:
		case MENTRY:
			 /*进入一个新的基本块*/
			 baseBlock[blocknum++] =code;  
			 break;
        /*跳转类的代码*/
		case JUMP:
		case JUMP0:
		case RETURNC:
		case ENDPROC:
		case ENDWHILE:

			/*从下一条语句开始，进入一个新的基本块*/
			 if (code->next!= NULL)
			 { code = code->next;
			   baseBlock[blocknum++] =code;
			 }
			 break;
		/*变参传递*/
		case VARACT: 
			 /*找到对应的过程调用语句，作为本基本块的结束*/
			 code = code->next;
			 while (code->codeR.codekind != CALL)
				 code = code->next;
			 /*从下一条语句开始，进入一个新的基本块*/
			 if (code->next!= NULL)
			 { code = code->next;
			   baseBlock[blocknum++] =code;
			 }
			 
        default : break;
	   }
       code = code->next;
	}
	return(blocknum);
}
 
/********************************************************/
/* 函数名  PrintBaseBlock								*/
/* 功  能  打印基本块第一条代码,以显示基本块的划分		*/
/* 说  明												*/
/********************************************************/  
void CeccOpti::PrintBaseBlock(int  blocknum)
{
	for (int i=0;i<blocknum ;i++)
	{ 
		PrintOneCode(baseBlock[i]);
      fprintf(listing,"\n");
	}
}


/**************用于公共表达式优化*****************/
/********************************************************/
/* 函数名  printValuNum									*/
/* 功  能  输出值编码表									*/
/* 说  明												*/
/********************************************************/  
void   CeccOpti::printValuNum()
{ 

	ValuNum  *Item = valuNumT;
	while (Item!=NULL)
	{   
		PrintContent(Item->arg);
		fprintf(listing,"  ");
		if (Item->access == indir )
		{   fprintf(listing ,"(");
			fprintf(listing,"%d",Item->codeInfo.twoCode.valuecode);
			fprintf(listing," , ");
			fprintf(listing,"%d",Item->codeInfo.twoCode.addrcode);
		    fprintf(listing,")");
		}
       else  fprintf(listing,"%d",Item->codeInfo.valueCode);
       
	   fprintf(listing,"\n");
	   Item = Item->next;
	}
}

/********************************************************/
/* 函数名  printUsableExpr								*/
/* 功  能  输出可用表达式编码表							*/
/* 说  明												*/
/********************************************************/  
void   CeccOpti::printUsbleExpr()
{
	UsableExpr  *Item = usableExprT;
	while (Item!=NULL)
	{ PrintOneCode(Item->code);
	  fprintf(listing, "  :  ");
	  fprintf(listing,"(");
	  fprintf(listing,"%d  ",Item->mirrorC->op1);
	  fprintf(listing,"%d  ",Item->mirrorC->op2);
	  fprintf(listing,"%d  ",Item->mirrorC->result);
	  fprintf(listing,")");
	  
	  fprintf(listing,"\n");
	  Item = Item->next;
	}

}


/********************************************************/
/* 函数名  printTempEqua								*/
/* 功  能  输出临时变量等价表							*/
/* 说  明												*/
/********************************************************/  
void   CeccOpti::printTempEqua()
{


	TempEqua  * Item = tempEquaT;
	while (Item!=NULL)
	{ PrintContent(Item->arg1);
		fprintf(listing,"   ");
		PrintContent(Item->arg2);

		fprintf(listing,"\n");
		Item = Item->next;
  }
}


/********************************************************/
/* 函数名  PrintMidCode 								*/
/* 功  能  打印中间代码序列								*/
/* 说  明												*/
/********************************************************/
void  CeccOpti::PrintMidCode(CodeFile  *firstCode)
{   int i = 0;
	CodeFile  *code = firstCode ;
	while (code!=NULL)
	{ fprintf(listing ,"           ");
    	fprintf(listing ,"%d%s",  i, ":  ");
	  PrintOneCode(code);
	  fprintf(listing,"\n");
	  code = code ->next;
	  i++;
	}
}
/********************************************************/
/* 函数名  PrintOneCode 								*/
/* 功  能  打印一条中间代码								*/
/* 说  明  由函数PrintMidCode调用						*/
/********************************************************/
void CeccOpti::PrintOneCode(CodeFile  *code)
{ 
    PrintCodeName(code->codeR.codekind);
	fprintf(listing ,"    ");
	if (code->codeR.arg1!=NULL)
		PrintContent(code->codeR.arg1);
	else  fprintf(listing, "  ");
	fprintf(listing ,"    ");
	if (code->codeR.arg2!=NULL)
		PrintContent(code->codeR.arg2);
	else  fprintf(listing ,"  ");
	fprintf(listing ,"    ");
	if (code->codeR.arg3!=NULL)
		PrintContent(code->codeR.arg3);
	else  fprintf(listing, "  ");
}
 
/********************************************************/
/* 函数名  PrintCodeName  								*/
/* 功  能  打印代码的类别								*/
/* 说  明  由函数PrintOneCode调用						*/
/********************************************************/
void  CeccOpti::PrintCodeName(CodeKind kind)
{
  switch(kind)
  {	case	ADD:		fprintf(listing ,"ADD");     break;
    case    SUB:		fprintf(listing ,"SUB");	 break;
	case	MULT:       fprintf(listing ,"MULT");    break;
	case	DIV:		fprintf(listing ,"DIV");     break;
	case	EQC:		fprintf(listing ,"EQ");      break;
	case	LTC:		fprintf(listing ,"LT");      break;
	case	READC:		fprintf(listing ,"READ");    break;
	case	WRITEC:		fprintf(listing ,"WRITE");	 break;
	case	RETURNC:	fprintf(listing ,"RETURN");  break;
	case	ASSIG:		fprintf(listing ,"ASSIG");   break;
	case    AADD:		fprintf(listing ,"AADD");    break;
	case    LABEL:		fprintf(listing ,"LABEL");   break;
	case    JUMP0:		fprintf(listing ,"JUMP0");   break;
	case    JUMP:		fprintf(listing ,"JUMP");    break;
	case    CALL:		fprintf(listing ,"CALL");    break;
	case    VARACT:		fprintf(listing ,"VARACT");  break;
	case    VALACT:		fprintf(listing ,"VALACT");  break;
	case    PENTRY:		fprintf(listing ,"PENTRY");  break;
	case    ENDPROC:	fprintf(listing ,"ENDPROC"); break;
	case    MENTRY:		fprintf(listing ,"MENTRY");  break;
	case    WHILESTART: fprintf(listing ,"WHILESTART");break;
	case    ENDWHILE:   fprintf(listing ,"ENDWHILE");  break;
	default:  break;
  }
}

/********************************************************/
/* 函数名  PrintCotent  								*/
/* 功  能  打印ARG结构的内容							*/
/* 说  明  由函数PrintOneCode调用						*/
/********************************************************/
void CeccOpti::PrintContent(ArgRecord  *arg)
{
	switch(arg->form)
	{case  LabelForm : fprintf(listing ,"%d",arg->Attr.label); break;
	 case  ValueForm : fprintf(listing ,"%d",arg->Attr.value); break;
	 case  AddrForm: 
		 //d:fprintf(listing ,"(");
		 if (arg->Attr.addr.dataLevel!=-1)
		      fprintf(listing ,arg->Attr.addr.name);
		 else 
		 { fprintf(listing ,"temp");
		        fprintf(listing ,"%d",arg->Attr.addr.dataOff);
		 }
		 /*
		 fprintf(listing ," , ");
		 fprintf(listing ,"%d",arg->Attr.addr.dataLevel);
		 fprintf(listing ," , ");
		 fprintf(listing ,"%d",arg->Attr.addr.dataOff);
		 fprintf(listing ," , ");
		 switch( arg->Attr.addr.access)
		 { case dir :  fprintf(listing ,"dir");   break;
		   case indir: fprintf(listing ,"indir"); break;
		   default  : break;
		  }
		 fprintf(listing ,")");
	     */
		 break;
	 default:  break;
	}
}


/***************公共表达式优化的各函数实现***************/


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

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

Cglobal::CodeFile  *CeccOpti::ECCsave(CodeFile *firstCode)
{ 

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

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

/***********************************/

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

	fprintf(listing, ">>基本块划分：（显示每个基本块的第一条语句以表示划分）\n");
    PrintBaseBlock(blocknum);

    /*循环对每个基本块进行公共表达式优化*/
	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   CeccOpti::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))
	{
		/*进行等价替换*/
12 下一页
💿 文件大小 7 K
👤 上传用户 sinba
📂 所属分类编译器/解释器
🏷️ 相关标签

#代码 #表达式 #优化算法 #编译原理
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -