/****************************************************************************/
/*                                                                          */
/*                      Chaine de CAO & VLSI   Alliance                     */
/*                                                                          */
/*    Produit :  Synthetiseur Logique                                       */
/*    Fichier :  optimexpr.c                                                */
/*                                                                          */
/*    (c) copyright 1991 Laboratoire MASI equipe CAO & VLSI                 */
/*    Tous droits reserves                                                  */
/*    Support : e-mail cao-vlsi@masi.ibp.fr                                 */
/*                                                                          */
/*    Auteur(s) :  L. Burgun                            le : 16/04/1992     */
/*                                                                          */
/*    Modifie par :                                     le : ../../..       */
/*    Modifie par :                                     le : ../../..       */
/*    Modifie par :                                     le : ../../....     */
/*                                                                          */
/****************************************************************************/

#include MUT_H
#include LOG_H
#include BEH_H
#include "sl_facto.h"
#include "../compil/lax_param.h"
#include "../synthe/sl_type.h"
#include "../prepar/carac.h"
#include "optim.h"
#include "optimexpr.h"
      
/*------------------------------------------------------------------------------
timeExpr        : calcul du temps pour une expression 
-------------------------------------------------------
parametres 	 : une expression et une table de hachage (atom,delais) 
-------------------------------------------------------
return 		 : un int
------------------------------------------------------------------------------*/
int timeExpr(expr,timeTH)
chain_list *expr;
pTH timeTH;
{
if (ATOM(expr))
   {
   return(searchTH(timeTH,VALUE_ATOM(expr)));
   }
else
   {
   chain_list *oldExpr = expr; 
   int max = 0;
   int delais;
   int moyenne;
   int somme = 0;
   int delaisEstime;
   int length = lengthExpr(expr);
 

 
                        /* calcul du max */
 
   while (expr = CDR(expr))
      {
      delais = timeExpr(CAR(expr),timeTH);
      somme = somme + delais; 
      if (max < delais)
         max = delais;
      }
   if (OPER(oldExpr) == NOT)
      return(max);

			/* calcul avec ponderation */

   moyenne = somme/length;
 
   if (OPER(oldExpr) == XOR || OPER(oldExpr) == NXOR)
      {
      delaisEstime = 1000*logsup2(length) - max + moyenne;
      if (1000 > delaisEstime)
         delais = 1000+max;
      else
         delais = delaisEstime+max;
      }
   else
      {
      delaisEstime = 500*logsup2(length) - max + moyenne;
      if (500 > delaisEstime)
         delais = 500+max;
      else
         delais = delaisEstime+max;
      }

   return (delais);
   }
}

/*------------------------------------------------------------------------------
coutExpr        : fonction de cout pour une expression 
-------------------------------------------------------
parametres 	 : nombre de litteraux, temps et mode d'optimisation 
-------------------------------------------------------
return 		 : un int
------------------------------------------------------------------------------*/
int coutExpr(litt,time,optim)
int litt,time,optim;
{
if (time == 0)
   return(litt);

if (optim == 0)
   return (10*litt + time/100);		/* 1 nano pour 1 litteraux  */
else
   return (10*litt + time/10);		/* 1 nano pour 10 litteraux */
}

/*------------------------------------------------------------------------------
optimExpr        : optimise une expression localement.
-------------------------------------------------------
parametres 	 : une expression, une liste de delais et un mode d'optimisation.
-------------------------------------------------------
return 		 :une pointeur de CHAIN_LIST.
------------------------------------------------------------------------------*/
chain_list *optimExpr(expr,support,optim)
chain_list *expr;
ptype_list *support;
int optim;
{
pCircuit pC;
ptype_list *lpt;
int numberInput;
chain_list *newExpr0;
int *tabDel;
bdd_table *matOrder;
int i,indexNewPI;
pNode pBddOut;
pElemTH pEl;
int selection;
pTH timeTH;
char **nameI;


		/* calcul du nombre d'entrees */

lpt = support;
numberInput = 0;
while (lpt)
   {
   numberInput++;
   lpt = lpt->NEXT;
   }


if (SL_TRACE)
   {
   printf("\noptimExpr : optim = %d support = %d\n",optim,numberInput);
   displayExpr(expr);
   lpt = support;
   while (lpt)
      {
      printf("%s(%d) ",lpt->DATA,lpt->TYPE); 
      lpt = lpt->NEXT;
      }
   printf("\n");
   }

tabDel = (int *) mbkalloc (numberInput * sizeof(int));
timeTH = createTH(numberInput*2);

pC = initializeCct("optimexpr",numberInput,2);

		/* ajout des entrees dans le circuit et 
                   association des index avec les delais  */

lpt = support;
while (lpt)
   {
   int index = addInputCct(pC,(char *)lpt->DATA);
   
   addTH(timeTH,(char *) lpt->DATA,(int )lpt->TYPE);

   if (index > 1)
      tabDel[index-2] = lpt->TYPE;
   else
      {
      printf("optimExpr : error - index < 2\n");
      exit(-1);
      }
   lpt = lpt->NEXT;
   }
		/* calcul de la sortie */

pBddOut = ablToBddCct(pC,expr);

addOutputCct(pC,"out",pBddOut);


		/* re-ordonnancement du graphe */

matOrder = (bdd_table *) mbkalloc (numberInput*sizeof(bdd_table));

for (i=0;i<numberInput;i++)
      {
      matOrder[i].ptNode = NULL;
      matOrder[i].numberNode = 0;
      matOrder[i].support = 'O';
      }


	/* creation des entrees virtuelles */

for (i=0;i<numberInput;i++)
   {
   addInputCct(pC,gensym("newpi",i+numberInput+2));
   }

pTabExpr = createTH(1000);
nameI = pC->pNameI;

	/* re-ordonnancement */

indexNewPI = 2*numberInput + 1;
while (indexNewPI != numberInput + 1)
   {
   int numberNodeOut;
   int minNumber,minDepth;
   int minIndex,lastIndex;

   for (i=0;i<numberInput;i++)
       {

       switch (matOrder[i].support)
            {
            case 'O' :
               matOrder[i].ptNode = 
                           upVarBdd(pBddOut,createNodeTermBdd(i+2),indexNewPI);
               matOrder[i].numberNode =
                           numberNodeBdd(matOrder[i].ptNode);
               break;
            case 'D' :
               break;
            }
       }

		/* calcul des expressions */

   numberNodeOut = numberNodeBdd(pBddOut);
   if (numberInput < 10)
      selection = 14;
   else
      if (numberInput < 20)
         selection = 12;
      else
         selection = 11;

   for (i=0;i<numberInput;i++)
       {
       if (matOrder[i].support == 'O')   /* entree non traitee */
          {       
			/* entree selectionnable */

          if ((matOrder[i].numberNode * 10) < (numberNodeOut * selection))
             {
             chain_list *exprInt = bdd2Abl(matOrder[i].ptNode,pC->pNameI,0);

             matOrder[i].number = numberAtomExpr(exprInt);
             addTH(timeTH,nameI[indexNewPI-2],tabDel[i]);
             matOrder[i].time  = timeExpr(exprInt,timeTH); 
             freeExpr(exprInt);
             } 
          else
             {
             matOrder[i].number = 0; 
             matOrder[i].time  = 0; 
             }
          }
       }

		/* selection de la meilleur expression */

   minNumber = 100000;
   minDepth = 10000;
   minIndex = -1;
   lastIndex = -1;

   for (i=0;i<numberInput;i++)
       {
   		/* entree non traitee */

       if (matOrder[i].support == 'O')
          {
          if (matOrder[i].number != 0)
             {       
             if (coutExpr(minNumber,minDepth,optim) > 
                 coutExpr(matOrder[i].number,matOrder[i].time,optim))
                {
                minNumber = matOrder[i].number;
                minDepth = matOrder[i].time; 
                minIndex = i;
                }
             }
          lastIndex = i; 
          }
       }

   if (minIndex == -1)
      minIndex = lastIndex;

   if (SL_TRACE)
      printf(" %d",minIndex+2);

   if (numberNodeAllBdd() > 20000)
      gcNodeCct(pC);
   upVarCct(pC,createNodeTermBdd(minIndex+2),indexNewPI);
   matOrder[minIndex].support = 'D';
   pBddOut = searchOutputCct(pC,"out");
   indexNewPI--;
   }

		/* desa de pTabExpr */

pEl = pTabExpr->pElem;
 
for(i = 0;i<pTabExpr->length;i++)
   {
   if (pEl->value != EMPTYTH && pEl->value != DELETETH)
      {
      freeExpr((chain_list *)pEl->value);
      }
   pEl++;
   }  
destroyTH(pTabExpr);

pTabExpr = createTH(100);

		 /* re-generation de l'expression */


mbkfree(tabDel);
mbkfree(matOrder);

newExpr0 = bdd2Abl(pBddOut,pC->pNameI,0);

destroyCct(pC);

pEl = pTabExpr->pElem;
 
for(i = 0;i<pTabExpr->length;i++)
   {
   if (pEl->value != EMPTYTH && pEl->value != DELETETH)
      {
      freeExpr((chain_list *)pEl->value);
      }
   pEl++;
   }  
destroyTH(pTabExpr);

if (SL_TRACE)
   {
   printf("\nResult : \n");
   displayExpr(newExpr0);

   printf("Delay (1)%d (2)%d\n",timeExpr(expr,timeTH),timeExpr(newExpr0,timeTH));
   printf("Litterals (1)%d (2)%d\n",numberAtomExpr(expr),numberAtomExpr(newExpr0));
   }

if (coutExpr(numberAtomExpr(expr),timeExpr(expr,timeTH),optim) <
    coutExpr(numberAtomExpr(newExpr0),timeExpr(newExpr0,timeTH),optim)) 
   {
   freeExpr(newExpr0);
   newExpr0 = copyExpr(expr);
   }

destroyTH(timeTH);
return(newExpr0);
}

/*-------------------------------------------------------------------------
optimExprExt	: optimise localement une expression
---------------------------------------------------------------------------
retour		: un chain_list.
---------------------------------------------------------------------------*/
chain_list *optimExprExt(expr,caracTH,optim,dejaTraite,order,beh)
chain_list *expr;
pTH caracTH;
int optim;
pTH dejaTraite;
chain_list *order;
befig_list *beh;
{
ptype_list *support;
chain_list *lc;
int delais;
chain_list *ret;
chain_list *auxlc;
beaux_list *aux;
int numberInput = 0;

	/* on ne fait rien en dessous de 6 litteraux */

if (numberAtomExpr(expr) < 6)
   {
   ret = copyExpr(expr);

		/* calcul du support pour l'appel recursif (si optim = 1) */

   lc = supportChain_listExpr(expr);
   auxlc = NULL;
   while (lc)
      {
      if (!inChain_list(order,lc->DATA))
         {
         auxlc = addchain(auxlc,(void *) lc->DATA);
         } 
      lc = lc->NEXT;
      }

   }
else
   {
			/* calcul du support */

   support = NULL;

		/* on met les variables primaires en premier */
   lc = order;
   while (lc)
      {
      if (searchExpr(expr,(char *) lc->DATA))
         {
         delais = searchTH(caracTH,(char *) lc->DATA);
         if (delais == EMPTYTH)
            support = addptype(support,0,(void *) lc->DATA);
         else
            support = addptype(support,delais,(void *) lc->DATA);
         numberInput++;
         }
      lc = lc->NEXT;
      }
   
		   /* puis les auxiliaires */
   
   lc = supportChain_listExpr(expr);
   auxlc = NULL;
   
   while (lc)
      {
      if (!inChain_list(order,lc->DATA))
         {
         auxlc = addchain(auxlc,(void *) lc->DATA);
         delais = searchTH(caracTH,(char *) lc->DATA);
         if (delais == EMPTYTH)
            support = addptype(support,0,(void *) lc->DATA);
         else
            support = addptype(support,delais,(void *) lc->DATA);
         numberInput++;
         } 
      lc = lc->NEXT;
      }
   
   if (numberInput < 15)
      ret = optimExpr(expr,support,optim);
   else
      {
      ret = createExpr(OPER(expr));
      while (expr = CDR(expr))
         addQExpr(ret,optimExprExt(CAR(expr),caracTH,optim,
                                   dejaTraite,order,beh));

		/* la recursion sur les fils s'est fait 
                   dans les appels precedents */
      return(ret);
      }
   }

	/* appel recursif uniquement si optimisation de delais */

if (optim == 1)
   {
   chain_list *supOptim;

   supOptim = supportOptimExpr(expr,caracTH,searchTH(caracTH,expr));

   while (auxlc)
      {
      if (searchTH(dejaTraite,(char *) auxlc->DATA) == EMPTYTH &&
          memberChain((char *) auxlc->DATA,supOptim))
         {
         chain_list *auxABL;
      
         aux = beh->BEAUX;
         while (aux && strcmp(aux->NAME,(char *) auxlc->DATA))
            {
            aux = aux->NEXT ; 
            }
         if (!aux)
            {
            printf("optimExprExt : error auxiliary variable does'nt exist\n");
            exit(-1);
            }
         auxABL = optimExprExt(aux->ABL,caracTH,optim,dejaTraite,order,beh);
            freeExpr(aux->ABL);
         aux->ABL = auxABL;
         addTH(dejaTraite,(char *) auxlc->DATA,1);
         }
      auxlc = auxlc->NEXT;
      }
   }
return (ret);
}

/*-------------------------------------------------------------------------
optimBeh	: optimise localement chaque expression d'une befig 
---------------------------------------------------------------------------
retour		: un void.
---------------------------------------------------------------------------*/
void optimBeh(beh,optim,delais,optimPO,order)
befig_list *beh;
int optim;
ptype_list *delais;
chain_list *optimPO;
chain_list *order;
{
beout_list *out;
bereg_list *reg;
bebus_list *bus;
bebux_list *bux;
biabl_list *biabl;
beaux_list *aux;
chain_list *expr;

pTH caracTH,dejaTraite;
int delaisMoyen;
pTH caracBeh();


dejaTraite = createTH(100);

                /* caracterisation */
 
caracTH = caracBeh(beh,delais,0);
 
                /* ----- a correler avec le mode d'optimisation */
 
delaisMoyen = delaisCarac(caracTH,optim);
 

	/* on commence par les cones a optimiser en delais */

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

   if (out->ABL)
      if ((del = searchTH(caracTH,out->ABL)) > delaisMoyen ||
          memberChain(out->NAME,optimPO))
         {
         expr = optimExprExt(out->ABL,caracTH,1,dejaTraite,order,beh);

		/* remise a jour de caracTH avec le nouvel ABL */

         addTH(caracTH,expr,del);
         PRINTF(".");
         fflush(stdout);

         freeExpr(out->ABL);
         out->ABL = expr;
         }
   out = out->NEXT;
   }

reg = beh->BEREG;
while (reg) 
   {
   biabl = reg->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
	 int del;

         if ((del = searchTH(caracTH,biabl->CNDABL)) > delaisMoyen ||
             memberChain(reg->NAME,optimPO))
            {
            expr = optimExprExt(biabl->CNDABL,caracTH,1,dejaTraite,order,beh);

  	    /* remise a jour de caracTH avec le nouvel ABL */

            PRINTF(".");
            fflush(stdout);
            addTH(caracTH,expr,del);

            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }
         if ((del = searchTH(caracTH,biabl->VALABL)) > delaisMoyen ||
             memberChain(reg->NAME,optimPO))
            {
            expr = optimExprExt(biabl->VALABL,caracTH,1,dejaTraite,order,beh);

     	    /* remise a jour de caracTH avec le nouvel ABL */

            PRINTF(".");
            fflush(stdout);
            addTH(caracTH,expr,del);

            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
            }
         }
      biabl = biabl->NEXT;
      }
   reg = reg->NEXT;
   }

bus = beh->BEBUS;
while (bus) 
   {
   biabl = bus->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
	 int del;

         if ((del = searchTH(caracTH,biabl->CNDABL)) > delaisMoyen ||
             memberChain(bus->NAME,optimPO))
            {
            expr = optimExprExt(biabl->CNDABL,caracTH,1,dejaTraite,order,beh);

	    /* remise a jour de caracTH avec le nouvel ABL */
            PRINTF(".");
            fflush(stdout);
            addTH(caracTH,expr,del);

            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }
         if ((del = searchTH(caracTH,biabl->VALABL)) > delaisMoyen ||
             memberChain(bus->NAME,optimPO))
            {
            expr = optimExprExt(biabl->VALABL,caracTH,1,dejaTraite,order,beh);

	    /* remise a jour de caracTH avec le nouvel ABL */
            PRINTF(".");
            fflush(stdout);
            addTH(caracTH,expr,del);

            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
            }
         }
      biabl = biabl->NEXT;
      }
   bus = bus->NEXT;
   }

bux = beh->BEBUX;
while (bux) 
   {
   biabl = bux->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
	 int del;

         if ((del = searchTH(caracTH,biabl->CNDABL)) > delaisMoyen ||
             memberChain(bux->NAME,optimPO))
            {
            expr = optimExprExt(biabl->CNDABL,caracTH,1,dejaTraite,order,beh);

	    /* remise a jour de caracTH avec le nouvel ABL */
            PRINTF(".");
            fflush(stdout);
            addTH(caracTH,expr,del);

            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }
         if ((del = searchTH(caracTH,biabl->VALABL)) > delaisMoyen ||
             memberChain(bux->NAME,optimPO))
            {
            expr = optimExprExt(biabl->VALABL,caracTH,1,dejaTraite,order,beh);

	    /* remise a jour de caracTH avec le nouvel ABL */
            PRINTF(".");
            fflush(stdout);
            addTH(caracTH,expr,del);

            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
            }
         }
      biabl = biabl->NEXT;
      }
   bux = bux->NEXT;
   }

if (SL_TRACE)
   printf("area optimizing %d\n",delaisMoyen);

	/* optimisation en surface */

aux = beh->BEAUX;
while (aux) 
   {
   if (aux->ABL)
      if (searchTH(dejaTraite,aux->NAME) == EMPTYTH)
         {
         expr = optimExprExt(aux->ABL,caracTH,0,dejaTraite,order,beh);
         PRINTF(".");
         fflush(stdout);
         freeExpr(aux->ABL);
         aux->ABL = expr;
         }
   aux = aux->NEXT;
   }

out = beh->BEOUT;
while (out) 
   {
   if (out->ABL)
      if (searchTH(caracTH,out->ABL) <= delaisMoyen &&
          !memberChain(out->NAME,optimPO))
         {
         expr = optimExprExt(out->ABL,caracTH,0,dejaTraite,order,beh);
         PRINTF(".");
         fflush(stdout);
         freeExpr(out->ABL);
         out->ABL = expr;
         }
   out = out->NEXT;
   }

reg = beh->BEREG;
while (reg) 
   {
   biabl = reg->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
         if ((searchTH(caracTH,biabl->CNDABL) <= delaisMoyen) &&
             !memberChain(reg->NAME,optimPO))
            {
            expr = optimExprExt(biabl->CNDABL,caracTH,0,dejaTraite,order,beh);
            PRINTF(".");
            fflush(stdout);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }

         if ((searchTH(caracTH,biabl->VALABL) <= delaisMoyen) &&
             (!memberChain(reg->NAME,optimPO)))
            {
            expr = optimExprExt(biabl->VALABL,caracTH,0,dejaTraite,order,beh);
            PRINTF(".");
            fflush(stdout);
            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
            }
         }
      biabl = biabl->NEXT;
      }
   reg = reg->NEXT;
   }

bus = beh->BEBUS;
while (bus) 
   {
   biabl = bus->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
         if ((searchTH(caracTH,biabl->CNDABL) <= delaisMoyen) &&
             !memberChain(bus->NAME,optimPO))
            {
            expr = optimExprExt(biabl->CNDABL,caracTH,0,dejaTraite,order,beh);
            PRINTF(".");
            fflush(stdout);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }
         if ((searchTH(caracTH,biabl->VALABL) <= delaisMoyen) &&
             !memberChain(bus->NAME,optimPO))
            {
            expr = optimExprExt(biabl->VALABL,caracTH,0,dejaTraite,order,beh);
            PRINTF(".");
            fflush(stdout);
            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
            }
         }
      biabl = biabl->NEXT;
      }
   bus = bus->NEXT;
   }

bux = beh->BEBUX;
while (bux) 
   {
   biabl = bux->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
         if ((searchTH(caracTH,biabl->CNDABL) <= delaisMoyen) &&
             !memberChain(bux->NAME,optimPO))
            {
            expr = optimExprExt(biabl->CNDABL,caracTH,0,dejaTraite,order,beh);
            PRINTF(".");
            fflush(stdout);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }
         if ((searchTH(caracTH,biabl->VALABL) <= delaisMoyen) &&
             !memberChain(bux->NAME,optimPO))
            {
            expr = optimExprExt(biabl->VALABL,caracTH,0,dejaTraite,order,beh);
            PRINTF(".");
            fflush(stdout);
            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
            }
         }
      biabl = biabl->NEXT;
      }
   bux = bux->NEXT;
   }


PRINTF("\n");

destroyTH(caracTH);
destroyTH(dejaTraite);
}
