循环不变式优化.txt

这是编译原理的源代码

// loopOpti.cpp: implementation of the CloopOpti class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "face.h"
#include "loopOpti.h"

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

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

CloopOpti::CloopOpti()
{

	TotalNum = 0;
	
	/*循环信息栈*/
	loopTop = NULL;

}

CloopOpti::~CloopOpti()
{

}


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


/*循环信息栈的压栈实现过程*/
void  CloopOpti::PushLoop(LoopInfo  *t)
{
	LoopStack *p = (LoopStack *)malloc (sizeof(LoopStack));
	p->loopInfo = t ;
	p->under=loopTop;
    loopTop = p;
	loopStackEmpty = false;
}

/*循环信息栈的弹栈实现过程*/
Cglobal::LoopInfo *CloopOpti::PopLoop()
{     
  LoopStack  *p=NULL;
  LoopInfo   *backpointer = NULL;
  p =loopTop;
  backpointer=p->loopInfo;
  loopTop=loopTop->under;
  free(p);
  if (loopTop==NULL)
	  loopStackEmpty = true;

  return backpointer;
}
 

/********************************************************/
/* 函数名  PrintMidCode 								*/
/* 功  能  打印中间代码序列								*/
/* 说  明												*/
/********************************************************/
void  CloopOpti::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 CloopOpti::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  CloopOpti::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 CloopOpti::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;
	}
}

/****************循环不变式优化的实现函数********************/

/****************************************************/
/* 函数名  LoopOpti									*/
/* 功  能  循环不变式优化主函数						*/
/* 说  明										    */
/****************************************************/
Cglobal::CodeFile  *CloopOpti::LoopOpti(CodeFile *firstCode)
{   

/*********初始化*************/
	TotalNum = 0;
	
	/*循环信息栈*/
	loopTop = NULL;
/****************************/
   
	/*初始化变量定值表*/
	for (int i=0;i<100;i++)
		varTable[i] = NULL;

	/*从第一条代码开始优化过程*/
    CodeFile  *currentCode = firstCode;
	
    fprintf(listing,"\n*******优化过程：变量定值表的变化：\n");

	/*循环处理每条代码，直到中间代码结束*/
	while (currentCode!=NULL)
	{   
		switch(currentCode->codeR.codekind)
		{ /*算术和关系操作*/
		  case  AADD:
		  case  ADD:
		  case  SUB:
          case  MULT:
   	      case  DIV:
		  case  LTC:
		  case  EQC:	
			        /*将被定值的变量名填入变量定值表中*/
			  	    AddTable(currentCode->codeR.arg3);
					break;
		  /*赋值语句*/
	      case ASSIG:
			        /*将被定值的变量填入变量定值表中*/
			  	    AddTable(currentCode->codeR.arg2);
					break;
		  /*循环入口*/
		  case WHILESTART:
					whileEntry(currentCode);
					break;
		  /*循环出口*/
		  case ENDWHILE:  
					whileEnd(currentCode);
					break;
		  /*过程调用语句*/
		  case CALL:
			        call(currentCode);
			        break;

		  default : break;
        }
      /*调用函数输出变量定值表，以现在处理完每条代码后，
	    表的变化*/
      //printVarTable();
	  /*令指针指向下一条代码*/
	  currentCode = currentCode->next;

	 
	}
   return (firstCode);
}

/****************************************************/
/* 函数名  whileEntry								*/
/* 功  能  循环入口部分的处理函数					*/
/* 说  明										    */
/****************************************************/
void CloopOpti::whileEntry(CodeFile *code)
{
	LoopInfo  *infoItem = (LoopInfo*)malloc(sizeof(LoopInfo));

	/*外提标志初始化为可以外提标志1*/
	infoItem->state = 1;
	/*此循环在变量定值表的入口*/
	infoItem->varDef = TotalNum;
	/*循环入口指针*/
	infoItem->whileEntry = code;
	/*循环出口此处不能确定*/
	//infoItem.whileEnd = NULL;
    /*循环信息表压栈*/
    PushLoop(infoItem);

}

/****************************************************/
/* 函数名  call										*/
/* 功  能  遇到过程调用语句的特别处理				*/
/* 说  明  所有包含此调用语句的循环都不能做不变式   */
/*		   外提									    */
/****************************************************/
void  CloopOpti::call(CodeFile  *code)
{ 
  /*所有打开着的循环均为不可外提状态，是这些循环信息中的
    State取0*/
   LoopStack  *Item = loopTop;
  
   while (Item!=NULL)
   { Item->loopInfo->state = 0;
     Item = Item->under;
   }

}

/****************************************************/
/* 函数名  whileEnd									*/
/* 功  能  循环出口部分的处理函数					*/
/* 说  明										    */
/****************************************************/

void CloopOpti::whileEnd(CodeFile *code)
{
  /*循环信息栈的栈顶*/
  LoopStack  *Item = loopTop;

  /*可以外提*/
  if (Item->loopInfo->state == 1)
  {   
	  /*填写循环出口位置指针*/
	  loopTop->loopInfo->whileEnd = code;
	  /*找到循环入口*/
      CodeFile  *entry  = loopTop->loopInfo->whileEntry;
      /*循环外提处理部分*/
      LoopOutside(entry );
  }

  /*弹循环信息栈，此层循环处理结束*/
  PopLoop();

}


/****************************************************/
/* 函数名  LoopOutside								*/
/* 功  能  循环外提处理函数							*/
/* 说  明										    */
/****************************************************/
void   CloopOpti::LoopOutside(CodeFile  *entry)
{
   /*外提的位置，为循环入口位置*/
   CodeFile  *place = entry;
   /*当前处理代码,注：跳过循环开始标号语句*/
   CodeFile  *code =  entry->next;
   
   /*取循环信息栈顶指针*/
   LoopStack *Item = loopTop;
   /*取得本层循环的出口位置*/
   CodeFile  *end = Item->loopInfo->whileEnd;
   /*取得本层循环的变量信息表*/
   int  head = Item->loopInfo->varDef;

   int  present1, present2;

   /*用于跳过内层循环*/
   int  Level = 0;

   /*循环检查每条代码是否可以外提，直到此层循环结束*/
	while (code != end )
	{   
		switch(code->codeR.codekind)
		{ 
		  case  WHILESTART:
				Level++;	break;
		  case  ENDWHILE:
			    Level--;	break;
		  case  ADD:
		  case  SUB:
          case  MULT:
		  case  AADD:
			   /*跳过内层循环*/
			   if (Level==0)
				{
				 present1 = SearchTable(code->codeR.arg1,head);
				 present2 = SearchTable(code->codeR.arg2,head);
				 /*两个分量都不在变量定值标号中，可以外提*/
				 if ((present1<0)&&(present2<0))
				 {  /*操作结果也是不变量，故若在表中，从表中删除*/
					
					DelItem(code->codeR.arg3, head);
					/*外提*/
					/*在当前位置，删除此代码*/
					CodeFile *formerCode = code->former;
					CodeFile *nextCode = code->next;
					formerCode->next = nextCode;
					nextCode->former = formerCode;

					/*将代码加入到应外提的位置*/
					CodeFile *fplace = place->former;
					fplace->next  = code;
					code->former = fplace;
  			    	code->next = place;
					place->former = code;

					/*回到当前位置处，准备处理下一条语句*/
					code = formerCode;					
				 }
				 else
					/*否则，将变量定值加入当前变量定值表中*/ 
					AddTable(code->codeR.arg3);
				}
			   break;
          default :  break;
		}

		/*检查下一条语句*/
		code = code->next;
	}

}


/****************************************************/
/* 函数名  SearchTable								*/
/* 功  能  循环变量定值表查找函数					*/
/* 说  明  参数head指明了本层循环的变量定值在表中的 */
/*		   起始位置，arg表示要查找的变量,返回变量   */
/*		   在表中的位置，若不存在返回值为－1		*/
/****************************************************/
int	CloopOpti::SearchTable(ArgRecord  *arg , int  head)
{
	/*初始化为负数，不再表中*/
	int  present = -1 ;

	if (arg->form ==AddrForm)
	{   
		int  level = arg->Attr.addr.dataLevel;
	    int  off = arg->Attr.addr.dataOff;
		/*注：临时变量和源变量都可以通过比较层数和偏移看是否存在
		      于表中*/
		for (int i = head; i<TotalNum; i++)
			if ((varTable[i]->Attr.addr.dataLevel == level)
				&&(varTable[i]->Attr.addr.dataOff == off))
			{	present = i;
				break;
			}
    }   
	return(present);
}

/****************************************************/
/* 函数名  DelItem									*/
/* 功  能  删除变量定值表中此项						*/
/* 说  明										    */
/****************************************************/
void  CloopOpti::DelItem(ArgRecord  *arg, int head)
{
   /*调用函数查找变量定值表*/
   int present = SearchTable(arg , head);
   /*若在表中，则删除*/
   if (present!=-1)
   {   for (int i=present;i<TotalNum ; i++)
           varTable[i] =varTable[i+1];
       TotalNum--;
   }
}

/****************************************************/
/* 函数名  AddTable									*/
/* 功  能  将被定值的变量填入变量定值表				*/
/* 说  明										    */
/****************************************************/
void  CloopOpti::AddTable(ArgRecord  *arg)
{  
   /*若不在循环中，则从头查表，以免表中重复填入相同的变量*/
   int head = 0;
   /*若在循环中，则只要在当前循环层没有重复定义即可*/
   if (loopTop!=NULL)
	    head = loopTop->loopInfo->varDef;

   int  present = SearchTable(arg , head);
   /*表中没有，则添加*/
   if  (present==-1)
       varTable[TotalNum++] = arg;


}

/****************************************************/
/* 函数名  printVarTable							*/
/* 功  能  输出变量定值表							*/
/* 说  明										    */
/****************************************************/
void  CloopOpti::printVarTable()
{  
	  fprintf(listing,">>");
	  /*输出变量定值表*/
	  for (int i=0;i<TotalNum;i++)
	  {
		if (varTable[i]!=NULL)
		{	  if (varTable[i]->Attr.addr.dataLevel== -1)
				{ fprintf(listing, "temp");
				  fprintf(listing,"%d",varTable[i]->Attr.addr.dataOff);
		          fprintf(listing," ");
				}
			   else 
			      fprintf(listing, "%s  ",varTable[i]->Attr.addr.name);
		}
	  }
	  fprintf(listing,"\n");
}