/****************************************************/
/* 文件 loopOpti.cpp								*/
/*													*/
/* 說(shuō)明 TINY編譯器中間代碼的循環(huán)不變式外提優(yōu)化  	*/
/****************************************************/

#include "globals.h"		/* 該頭文件定義全局類型和變量 */

#include "util.h"			/*該頭文件定義了一些實(shí)用函數(shù)*/

#include "loopOpti.h"		/* 該頭文件聲明了循環(huán)不變式優(yōu)化界面函數(shù)*/


/*變量定值表,用變量的arg結(jié)構(gòu)表示變量*/
 ArgRecord  *varTable[100];
 int  TotalNum = 0;

/*循環(huán)信息棧*/
LoopStack  *loopTop = NULL;
bool  loopStackEmpty;


/***************函數(shù)聲明********************/

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();


/****************************************************/
/* 函數(shù)名  LoopOpti									*/
/* 功  能  循環(huán)不變式優(yōu)化主函數(shù)						*/
/* 說(shuō)  明										    */
/****************************************************/
CodeFile  *LoopOpti()
{   
   /*初始化變量定值表*/
	for (int i=0;i<100;i++)
		varTable[i] = NULL;

	/*從第一條代碼開始優(yōu)化過程*/
    CodeFile  *currentCode = firstCode;
	
    fprintf(listing,"\n>>Var  def  Table  after  each  code:\n");

	/*循環(huán)處理每條代碼，直到中間代碼結(jié)束*/
	while (currentCode!=NULL)
	{   
		switch(currentCode->codeR.codekind)
		{ /*算術(shù)和關(guān)系操作*/
		  case  AADD:
		  case  ADD:
		  case  SUB:
          case  MULT:
   	      case  DIV:
		  case  LTC:
		  case  EQC:	
			        /*將被定值的變量名填入變量定值表中*/
			  	    AddTable(currentCode->codeR.arg3);
					break;
		  /*賦值語(yǔ)句*/
	      case ASSIG:
			        /*將被定值的變量填入變量定值表中*/
			  	    AddTable(currentCode->codeR.arg2);
					break;
		  /*循環(huán)入口*/
		  case WHILESTART:
					whileEntry(currentCode);
					break;
		  /*循環(huán)出口*/
		  case ENDWHILE:  
					whileEnd(currentCode);
					break;
		  /*過程調(diào)用語(yǔ)句*/
		  case CALL:
			        call(currentCode);
			        break;

		  default : break;
        }
      /*調(diào)用函數(shù)輸出變量定值表，以現(xiàn)在處理完每條代碼后，
	    表的變化*/
      printVarTable();
	  /*令指針指向下一條代碼*/
	  currentCode = currentCode->next;

	 
	}
   return (firstCode);
}

/****************************************************/
/* 函數(shù)名  whileEntry								*/
/* 功  能  循環(huán)入口部分的處理函數(shù)					*/
/* 說(shuō)  明										    */
/****************************************************/
void whileEntry(CodeFile *code)
{
	LoopInfo  *infoItem = (LoopInfo*)malloc(sizeof(LoopInfo));

	/*外提標(biāo)志初始化為可以外提標(biāo)志1*/
	infoItem->state = 1;
	/*此循環(huán)在變量定值表的入口*/
	infoItem->varDef = TotalNum;
	/*循環(huán)入口指針*/
	infoItem->whileEntry = code;
	/*循環(huán)出口此處不能確定*/
	//infoItem.whileEnd = NULL;
    /*循環(huán)信息表壓棧*/
    PushLoop(infoItem);

}

/****************************************************/
/* 函數(shù)名  call										*/
/* 功  能  遇到過程調(diào)用語(yǔ)句的特別處理				*/
/* 說(shuō)  明  所有包含此調(diào)用語(yǔ)句的循環(huán)都不能做不變式   */
/*		   外提									    */
/****************************************************/
void  call(CodeFile  *code)
{ 
  /*所有打開著的循環(huán)均為不可外提狀態(tài)，是這些循環(huán)信息中的
    State取0*/
   LoopStack  *Item = loopTop;
  
   while (Item!=NULL)
   { Item->loopInfo->state = 0;
     Item = Item->under;
   }

}

/****************************************************/
/* 函數(shù)名  whileEnd									*/
/* 功  能  循環(huán)出口部分的處理函數(shù)					*/
/* 說(shuō)  明										    */
/****************************************************/

void whileEnd(CodeFile *code)
{
  /*循環(huán)信息棧的棧頂*/
  LoopStack  *Item = loopTop;

  /*可以外提*/
  if (Item->loopInfo->state == 1)
  {   
	  /*填寫循環(huán)出口位置指針*/
	  loopTop->loopInfo->whileEnd = code;
	  /*找到循環(huán)入口*/
      CodeFile  *entry  = loopTop->loopInfo->whileEntry;
      /*循環(huán)外提處理部分*/
      LoopOutside(entry );
  }

  /*彈循環(huán)信息棧，此層循環(huán)處理結(jié)束*/
  PopLoop();

}


/****************************************************/
/* 函數(shù)名  LoopOutside								*/
/* 功  能  循環(huán)外提處理函數(shù)							*/
/* 說(shuō)  明										    */
/****************************************************/
void   LoopOutside(CodeFile  *entry)
{
   /*外提的位置，為循環(huán)入口位置*/
   CodeFile  *place = entry;
   /*當(dāng)前處理代碼,注：跳過循環(huán)開始標(biāo)號(hào)語(yǔ)句*/
   CodeFile  *code =  entry->next;
   
   /*取循環(huán)信息棧頂指針*/
   LoopStack *Item = loopTop;
   /*取得本層循環(huán)的出口位置*/
   CodeFile  *end = Item->loopInfo->whileEnd;
   /*取得本層循環(huán)的變量信息表*/
   int  head = Item->loopInfo->varDef;

   int  present1, present2;

   /*用于跳過內(nèi)層循環(huán)*/
   int  Level = 0;

   /*循環(huán)檢查每條代碼是否可以外提，直到此層循環(huán)結(jié)束*/
	while (code != end )
	{   
		switch(code->codeR.codekind)
		{ 
		  case  WHILESTART:
				Level++;	break;
		  case  ENDWHILE:
			    Level--;	break;
		  case  ADD:
		  case  SUB:
          case  MULT:
		  case  AADD:
			   /*跳過內(nèi)層循環(huán)*/
			   if (Level==0)
				{
				 present1 = SearchTable(code->codeR.arg1,head);
				 present2 = SearchTable(code->codeR.arg2,head);
				 /*兩個(gè)分量都不在變量定值標(biāo)號(hào)中，可以外提*/
				 if ((present1<0)&&(present2<0))
				 {  /*操作結(jié)果也是不變量，故若在表中，從表中刪除*/
					
					DelItem(code->codeR.arg3, head);
					/*外提*/
					/*在當(dāng)前位置，刪除此代碼*/
					CodeFile *formerCode = code->former;
					CodeFile *nextCode = code->next;
					formerCode->next = nextCode;
					nextCode->former = formerCode;

					/*將代碼加入到應(yīng)外提的位置*/
					CodeFile *fplace = place->former;
					fplace->next  = code;
					code->former = fplace;
  			    	code->next = place;
					place->former = code;

					/*回到當(dāng)前位置處，準(zhǔn)備處理下一條語(yǔ)句*/
					code = formerCode;					
				 }
				 else
					/*否則，將變量定值加入當(dāng)前變量定值表中*/ 
					AddTable(code->codeR.arg3);
				}
			   break;
          default :  break;
		}

		/*檢查下一條語(yǔ)句*/
		code = code->next;
	}

}


/****************************************************/
/* 函數(shù)名  SearchTable								*/
/* 功  能  循環(huán)變量定值表查找函數(shù)					*/
/* 說(shuō)  明  參數(shù)head指明了本層循環(huán)的變量定值在表中的 */
/*		   起始位置，arg表示要查找的變量,返回變量   */
/*		   在表中的位置，若不存在返回值為－1		*/
/****************************************************/
int	SearchTable(ArgRecord  *arg , int  head)
{
	/*初始化為負(fù)數(shù)，不再表中*/
	int  present = -1 ;

	if (arg->form ==AddrForm)
	{   
		int  level = arg->Attr.addr.dataLevel;
	    int  off = arg->Attr.addr.dataOff;
		/*注：臨時(shí)變量和源變量都可以通過比較層數(shù)和偏移看是否存在
		      于表中*/
		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);
}

/****************************************************/
/* 函數(shù)名  DelItem									*/
/* 功  能  刪除變量定值表中此項(xiàng)						*/
/* 說(shuō)  明										    */
/****************************************************/
void  DelItem(ArgRecord  *arg, int head)
{
   /*調(diào)用函數(shù)查找變量定值表*/
   int present = SearchTable(arg , head);
   /*若在表中，則刪除*/
   if (present!=-1)
   {   for (int i=present;i<TotalNum ; i++)
           varTable[i] =varTable[i+1];
       TotalNum--;
   }
}

/****************************************************/
/* 函數(shù)名  AddTable									*/
/* 功  能  將被定值的變量填入變量定值表				*/
/* 說(shuō)  明										    */
/****************************************************/
void  AddTable(ArgRecord  *arg)
{  
   /*若不在循環(huán)中，則從頭查表，以免表中重復(fù)填入相同的變量*/
   int head = 0;
   /*若在循環(huán)中，則只要在當(dāng)前循環(huán)層沒有重復(fù)定義即可*/
   if (loopTop!=NULL)
	    head = loopTop->loopInfo->varDef;

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


}

/****************************************************/
/* 函數(shù)名  printVarTable							*/
/* 功  能  輸出變量定值表							*/
/* 說(shuō)  明										    */
/****************************************************/
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");
}