loopopti.cpp

学习编译原理

/****************************************************/
/* 文件 loopOpti.cpp								*/
/*													*/
/* 说明 TINY编译器中间代码的循环不变式外提优化  	*/
/****************************************************/

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

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

#include "loopOpti.h"		/* 该头文件声明了循环不变式优化界面函数*/


/*变量定值表,用变量的arg结构表示变量*/
 ArgRecord  *varTable[100];
 int  TotalNum = 0;

/*循环信息栈*/
LoopStack  *loopTop = NULL;
bool  loopStackEmpty;


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

CodeFile * LoopOpti();

void      whileEntry(CodeFile *code);

void      whileEnd(CodeFile *code);

void      call(CodeFile  *code);

void	  LoopOutside(CodeFile  *entry);

int  	  SearchTable(ArgRecord  *arg , int  head);

void      DelItem(ArgRecord  *arg, int head);

void      AddTable(ArgRecord *arg);

void      printVarTable();


/****************************************************/
/* 函数名  LoopOpti									*/
/* 功  能  循环不变式优化主函数						*/
/* 说  明										    */
/****************************************************/
CodeFile  *LoopOpti()
{   
   /*初始化变量定值表*/
	for (int i=0;i<100;i++)
		varTable[i] = NULL;

	/*从第一条代码开始优化过程*/
    CodeFile  *currentCode = firstCode;
	
    fprintf(listing,"\n>>Var  def  Table  after  each  code:\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 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  call(CodeFile  *code)
{ 
  /*所有打开着的循环均为不可外提状态，是这些循环信息中的
    State取0*/
   LoopStack  *Item = loopTop;
  
   while (Item!=NULL)
   { Item->loopInfo->state = 0;
     Item = Item->under;
   }

}

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

void 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   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	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  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  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  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");
}