/****************************************************************************/
/*                                                                          */
/*                      Chaine de CAO & VLSI   Alliance                     */
/*                                                                          */
/*    Produit :   synthetiseur logique                                      */
/*    Fichier :   sl_order.c                                                */
/*                                                                          */
/*    (c) copyright 1991 Laboratoire MASI equipe CAO & VLSI                 */
/*    Tous droits reserves                                                  */
/*    Support : e-mail cao-vlsi@masi.ibp.fr                                 */
/*                                                                          */
/*    Auteur(s) : DESTOMBES C.                          le : 12/06/91       */
/*                                                                          */
/*    Modifie par :  BURGUN L.                          le : 15/11/91       */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*                                                                          */
/****************************************************************************/

#include"head.h"

/*---------------------------------------------------------------------------
traitementAux	: traitement d'un Abl aux  pour le remplissage de la struct de
-----------------------------------------------------------------------------
retour		: int
---------------------------------------------------------------------------*/
int	 traitementAux(beh,name,ptOrder,ptHOrder,depth,oper,ptHAux)
befig_list 	*beh;
char		*name;
sl_tableOrder	*ptOrder;
pTH	  	ptHOrder;
int		 depth;
int		 oper;
pTH	  	ptHAux;

{
chain_list *expr;

expr = (chain_list *) searchTH(ptHAux,name);

if (expr != (chain_list *) VIDETH)
   {
   if (OPER( expr ) == oper)
      {
      return( traitementABL( beh, expr, ptOrder, 
                          ptHOrder, depth, oper,ptHAux ));
      }
   else 
      if (OPER(expr) == NOT)
         {
         return( traitementABL( beh, expr, 
                             ptOrder,ptHOrder, depth, oper,ptHAux )); 
         }
      else
         {
          return( traitementABL( beh, expr, ptOrder, 
	   		ptHOrder, depth +1, oper,ptHAux));
          }
      }
else
   {
   printf("traitementAux : variable '%s' does'nt exist\n,name");
   return( depth );
   }
}

/*---------------------------------------------------------------------------
supportAuxExpr	: compile un cone au premier niveau en calculant pour
                  chaque variable auxiliaire sa profondeur min et son 
                  nombre d'apparition a ce niveau.
-----------------------------------------------------------------------------
retour		: void
---------------------------------------------------------------------------*/
void supportAuxExpr(beh,abl,ppAux,prof,ptHOrder)
befig_list *beh;
chain_list *abl;
ptype_list **ppAux;
int prof;
pTH ptHOrder;
{
if (ATOM(abl))
   {
   ptype_list *pTL = *ppAux;

			/* est-ce une entree, 0 ou 1 ? */

   if ((searchTH(ptHOrder,VALUE_ATOM(abl)) != VIDETH) || 
       VALUE_ATOM(abl) == namealloc("'0'") ||
       VALUE_ATOM(abl) == namealloc("'1'"))
      {
      return;   
      }

   while (pTL)
      {
      if ((char*)pTL->DATA == VALUE_ATOM(abl))		/* nouvelle occurence de AUX */
         {
         
/*
   printf("*** %s occ = %d prof = %d\n",pTL->DATA,
                                    occAuxPTCL(pTL),profAuxPTCL(pTL));
*/
         if (prof == profAuxPTCL(pTL))		/* m profondeur d'apparition */
            {
            pTL->TYPE = pTL->TYPE + 1; 
            }
         else
            if (prof < profAuxPTCL(pTL))
               {
               pTL->TYPE = (prof << 8) + 1;
               }
         return;
         }
      pTL = pTL->NEXT;
      }
		/* nouvelle variable auxiliaire */

   *ppAux = addptype(*ppAux,(prof << 8)+1,VALUE_ATOM(abl));
   }
else
   {
   while (abl = CDR(abl))
         supportAuxExpr(beh,CAR(abl),ppAux,prof+1,ptHOrder);
   }
}

/*---------------------------------------------------------------------------
traitementABL	: traitement d'un ABL pour le remplissage de la struct de don
-----------------------------------------------------------------------------
retour		: int correspondant a la profondeur maximale de l'expression.
---------------------------------------------------------------------------*/
int	traitementABL(beh, abl, ptOrder, ptHOrder,depth, oper,ptHAux )
befig_list 	*beh;
chain_list	*abl;
sl_tableOrder	*ptOrder;
pTH		ptHOrder;
int		depth;
int		oper;
pTH		ptHAux;
{
int resul;
ptype_list *pAux;
ptype_list **ppAux = (ptype_list **) malloc (sizeof(ptype_list *));
*ppAux = NULL;

/*
displayExpr(abl);
*/

supportAuxExpr(beh,abl,ppAux,0,ptHOrder);
pAux = *ppAux;
/*
while (pAux)
   {
   printf("name = %s occ = %d prof = %d\n",pAux->DATA,
                                    occAuxPTCL(pAux),profAuxPTCL(pAux));
   pAux = CDR(pAux);
   }
*/
resul = traitementABLInt(beh,abl,ptOrder,ptHOrder,
                         depth,oper,*ppAux,ptHAux);
freeptype(*ppAux);
return(resul);
}

/*---------------------------------------------------------------------------
traitementABLInt: la meme en interne. 
-----------------------------------------------------------------------------
retour		: int correspondant a la profondeur maximale de l'expression.
---------------------------------------------------------------------------*/
int traitementABLInt(beh,abl,ptOrder,ptHOrder,depth,oper,pAux,ptHAux)
befig_list 	*beh;
chain_list	*abl;
sl_tableOrder	*ptOrder;
pTH		ptHOrder;
int		 depth;
int		 oper;
ptype_list      *pAux;
pTH		ptHAux;
{
int		 oper_;


if (ATOM(abl))
   {
   int		 indice;
   char *name = VALUE_ATOM(abl);

   if (name == namealloc("'0'") || name == namealloc("'1'"))
      return(depth);

			/* est-ce une entree ? */

   indice = searchTH( ptHOrder, name);
   if (indice != VIDETH)
      {

	/* premier occurence ou nouvelle occurence au meme niveau */

      if (ptOrder[indice].depthMin == 0 || depth == ptOrder[indice].depthMin)
         {
         ptOrder[indice].numOccMin = ptOrder[indice].numOccMin + 1;
         ptOrder[indice].depthMin = depth;
         }

		/* profondeur inferieure */

      if (depth < ptOrder[indice].depthMin )
         {
         ptOrder[indice].depthMin = depth;
         ptOrder[indice].numOccMin = 1;
         }
	
/*   

printf("nom de l'atome: %s \n",name);
printf("   son ind: %d \n",indice);
printf("   son nb d'cc au niveau min: %d \n",ptOrder[indice].numOccMin);
printf("   sa prof: %d ",depth );
printf("   sa profmin: %d \n",ptOrder[indice].depthMin);

*/

      return( depth );
      }
   else
      {

      while (pAux)		/* recherche dans les Aux */
         {
         if ((char*)pAux->DATA == name)		/* trouve */
            {
            if (pAux->TYPE == 0)		/* deja traite */
               return(depth);

/* anciennement
               return(depth + profExprBeh(beh,searchTH(ptHAux,name)));
*/

            else
               {
               int result;

		/* la profondeur diminue avec le nombre d'occurence */

               result = traitementAux(beh, name, ptOrder, ptHOrder, 
                                      depth-logint(occAuxPTCL(pAux)+1), 
                                      oper, ptHAux);
               pAux->TYPE = 0; 
               return(result);
               }
            }     
         pAux = pAux->NEXT;
         }

      printf("traitementABL : Auxilliary variable doesn't exist\n");
      exit(-1); 
      }
   }			/* fin traitement atomique */
else
   {
   int depth_inter,depthm_retour = 0;

   oper_ = OPER( abl);
   while (abl = CDR(abl))
      {
      if (oper_ == oper)
        depth_inter = traitementABLInt( beh, CAR(abl), ptOrder,
                        ptHOrder, depth, oper_ ,pAux, ptHAux ) ;
      else
         {
         if (oper_ == NOT)
            {
            if (oper == AND)
               oper_ = OR;
            if (oper == OR)
               oper_ = AND;
            depth_inter = traitementABLInt( beh, CAR(abl), ptOrder,
                            ptHOrder, depth, oper_ ,pAux, ptHAux ) ;
            }
         else
           depth_inter = traitementABLInt( beh, CAR(abl), ptOrder, ptHOrder,
                                 depth+1, oper_ ,pAux, ptHAux) ;
         }
      if (depth_inter > depthm_retour)
         depthm_retour = depth_inter;
      }
   return( depthm_retour );
   }
}

/*-------------------------------------------------------------------------
traitementCone 	: traite un cone (registre, bus ou sortie) 
---------------------------------------------------------------------------
retour		: un void.
---------------------------------------------------------------------------*/

void traitementCone(beh,expr,ptOrder,ptHOrder,ptHAux)
befig_list *beh;
chain_list *expr;
sl_tableOrder *ptOrder;
pTH 	ptHOrder;
pTH 	ptHAux;
{
int depthMax;
sl_tableOrder *ptOrderAux = ptOrder;
berin_list *in;

if (expr == NULL)
   {
   printf("traitement cone : attention abl vide\n");
   }
else
   {

   depthMax = traitementABL(beh,expr,ptOrder,ptHOrder,0,1000,ptHAux );

   ptOrderAux = ptOrder;
   in = beh->BERIN;

   while (in)
      {

      if (ptOrderAux->numOccMin != 0) 
         {
         ptOrderAux->numberOut++;
/*
         printf("logint(%d) = %d\n",ptOrderAux->numOccMin,logint(ptOrderAux->numOccMin));
         printf("maxdepth = %d depthMin = %d\n",depthMax, ptOrderAux->depthMin);
*/
         ptOrderAux->sigmaDeltaDepth += 
              (logint(ptOrderAux->numOccMin)  + 1 
              + (depthMax - ptOrderAux->depthMin));

         }

      ptOrderAux->depthMin = 0;
      ptOrderAux->numOccMin = 0;
      in = in->NEXT;
      ptOrderAux++;
      }
   }
}

/*-------------------------------------------------------------------------
loadOrdInput 	: met les entrees d'un circuit (berin) dans les tables
                  d'ordonnancement
---------------------------------------------------------------------------
retour		: un void.
---------------------------------------------------------------------------*/

void loadOrdInput(beh,ptOrder,ptHOrder,ptHAux)
befig_list *beh;
sl_tableOrder *ptOrder;
pTH ptHOrder;
pTH ptHAux;
{
sl_tableOrder *ptOrderAux = ptOrder;
beout_list *out;
beaux_list *aux;
bebus_list *bus;
bereg_list *reg;
biabl_list *biabl;
int depthMax;
int count =0;
berin_list *in;
int c;

	/* insertion des auxiliares dans la table de hachage ptHAux*/

aux = beh->BEAUX;
while (aux)
   {
   addTH(ptHAux,aux->NAME,aux->ABL);
   aux = aux->NEXT;
   }

	/* insertion des entrees primaires dans la table de hachage */

in = beh->BERIN;
while (in)
   {
   ptOrderAux->name = in->NAME ;
   ptOrderAux->sigmaDeltaDepth = 0;
   ptOrderAux->depthMin = 0;
   ptOrderAux->vue = 0;
   ptOrderAux->numOccMin = 0;
   ptOrderAux->numberOut = 0;
   ptOrderAux->total= 0;
   addTH(ptHOrder,in->NAME,count);
   in = in->NEXT;
   count++;
   ptOrderAux++;
   };


	/* remplissage de la struct de donnees sl_tableOrder */
	/*   ( informations pour l'ordonnancement )	     */

out = beh->BEOUT;
while (out)
   {

/*
   printf("\n output: %s\n", out->NAME );
   displayExpr(out->ABL);
*/
   traitementCone(beh,out->ABL,ptOrder,ptHOrder,ptHAux);
   out = out->NEXT;
   }
bus = beh->BEBUS;
while (bus)
   {
/*
   printf("\n bus: %s\n", bus->NAME );
 */  
   biabl = bus->BIABL;
   while (biabl)
      {
      traitementCone(beh,biabl->VALABL,ptOrder,ptHOrder,ptHAux);
      traitementCone(beh,biabl->CNDABL,ptOrder,ptHOrder,ptHAux);
      biabl = biabl->NEXT;
      }
   bus = bus->NEXT;
   }

reg = beh->BEREG;
while (reg)
   {

/*
   printf("\n reg: %s\n", reg->NAME );
*/
   
   biabl = reg->BIABL;
   while (biabl)
      {
      traitementCone(beh,biabl->VALABL,ptOrder,ptHOrder,ptHAux);
      traitementCone(beh,biabl->CNDABL,ptOrder,ptHOrder,ptHAux);
      biabl = biabl->NEXT;
      }
   reg = reg->NEXT;
   }
}

/*-------------------------------------------------------------------------
makeOrderAbl 	: calcule (si mode = 1) un bon ordonnancement pour une BEFIG, 
                  sinon prend l'odre d'apparition.
---------------------------------------------------------------------------
retour		: un void.
---------------------------------------------------------------------------*/

chain_list *makeOrderAbl(beh,mode,trace)
befig_list *beh;
int mode;
int trace;
{
sl_tableOrder *ptOrder;
pTH ptHOrder,ptHAux;
int count;
chain_list *resul;

if (trace)
   {
   printf("\n");
   printf("Running abl ordonnancer on `%s` ...\n",beh->NAME);
   printf("\n");
   }

count = countInputBeh(beh);

if (mode == 1)		/* mode automatique */
   {
   beaux_list *aux;

   ptOrder = (sl_tableOrder *) malloc (count * sizeof(sl_tableOrder));
   ptHOrder = createTH(2*count);
   count = 0;
   aux = beh->BEAUX;
   while (aux)
     {
     aux = aux->NEXT;
     count++;
     }
   ptHAux = createTH(2*count+1);
   loadOrdInput(beh,ptOrder,ptHOrder,ptHAux);
   resul =  optimSurface ( beh, ptOrder, ptHOrder,ptHAux );
   destroyTH(ptHOrder); 
   destroyTH(ptHAux); 
   free(ptOrder);
   return resul;
   }
else			/* par ordre d'apparition */
   {
   return(berinToChain_list(beh));
   }
}

/*--------------------------------------------------------------------------
coutPI		: remplit le champ total de la Torder.
		  (pour l'instant ne prend en compte que )
----------------------------------------------------------------------------
retour		: ce cout (int) servant pour l'ordonnancement
--------------------------------------------------------------------------*/
void 		 coutPI( beh, ptOrder, ptHOrder )
befig_list	*beh;
sl_tableOrder	*ptOrder;
pTH		ptHOrder;
{
int		i;
int		finTable;

finTable = countInputBeh( beh );

/*
printf( "Nombre d'entrees : %d\n", finTable );
*/

for( i = 0; i < finTable; i ++ )
   {
   if (ptOrder[i].numberOut == 0) 
      {
      /* printf("erreur : %s n'apparait pas dans les equations\n",ptOrder[i].name);*/
      ptOrder[i].total = 0;
      }
  else 
      {
      ptOrder[i].total = (100*ptOrder[i].sigmaDeltaDepth)/ptOrder[i].numberOut;

/*
   printf("TOTAL de %s : %d", ptOrder[i].name, ptOrder[i].total );
   printf(" = %d sur %d\n", ptOrder[i].sigmaDeltaDepth, ptOrder[i].numberOut);
*/
      }
   }
}

	
/*--------------------------------------------------------------------------
optimSurface	: fournit un ordonnancement selon les param de sl_tableOrder
----------------------------------------------------------------------------
retour		: une LC (qu'il faudra recoller a l'ensemble)
--------------------------------------------------------------------------*/
chain_list	*optimSurface( beh, ptOrder, ptHOrder)
befig_list 	*beh;
sl_tableOrder 	*ptOrder;
pTH 	 	ptHOrder;
{
chain_list	*LC_retour = NULL;
long		 coutMax;
int		 j, indice, finTable;


coutPI( beh, ptOrder, ptHOrder );


finTable = countInputBeh( beh );

for( j = 0; j < finTable; j ++ ) 
   {
   coutMax = -1;

		/* calcul du cout max */

   for( indice = 0; indice < finTable; indice ++ ) 
      {
      if ((ptOrder[indice].vue == 0)&&(ptOrder[indice].total  >coutMax))
         {
  	 coutMax = ptOrder[indice].total;
         }
      }

   if (coutMax == -1)
      return(LC_retour);

		/* ajout de toutes les entrees de cout coutMax */

   for( indice = 0; indice < finTable; indice ++ ) 
      {
      if ((ptOrder[indice].vue == 0)&&(ptOrder[indice].total  == coutMax))
         {
         ptOrder[indice].vue = 1;
         LC_retour = addchain( LC_retour, ptOrder[indice].name);
         }
      }


   }

return( LC_retour );
}


