/****************************************************************************/
/*                                                                          */
/*                      Chaine de CAO & VLSI   Alliance                     */
/*                                                                          */
/*    Produit : synthetiseur logique                                        */
/*    Fichier : map.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 : 03/04/1992     */
/*                                                                          */
/*    Modifie par :                                     le : 22/07/1993     */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*                                                                          */
/****************************************************************************/

#include MUT_H
#include LOG_H
#include BEH_H
#include "bib.h"
#include "../compil/lax_param.h"
#include "../synthe/sl_type.h"
#include "../compil/sl_util.h"

#define FANOUT_MAX 4

/*-------------------------------------------------------------------------
createVIExpr: cree une VI. 
---------------------------------------------------------------------------
retour		: un litteral (a ou not a)
---------------------------------------------------------------------------*/
chain_list *createVIExpr(beh,expr,notTH,polarity,occTH)
befig_list *beh;
chain_list *expr;
pTH notTH;
int polarity;
pTH occTH;
{
static int co = 0;
char *newVI;
int val;

if (ATOM(expr))
   {
   printf("createVIExpr : Warning - atomic expression\n");
   displayExpr(expr);
   }

if (OPER(expr) == NOT && 
    (val = searchTH(notTH,VALUE_ATOM(CADR(expr)))) != EMPTYTH)
   {
   newVI = (char *) val;

			/* si le fanout est sup a 30 , on duplique */

/*
   if (searchTH(occTH,newVI) > 30)
      {
      newVI = gensym("auxc4",++co);
      beh->BEAUX = beh_addbeaux(beh->BEAUX,newVI,expr,NULL);
      addTH(occTH,newVI,1);
      addTH(notTH,VALUE_ATOM(CADR(expr)),newVI);
      }
   else
      addTH(occTH,newVI,1+ searchTH(occTH,newVI));
*/
   }
else
   {
   newVI = gensym("auxc4",++co);
   beh->BEAUX = beh_addbeaux(beh->BEAUX,newVI,expr,NULL);
   addTH(occTH,newVI,1);
   if (OPER(expr) == NOT)
      addTH(notTH,VALUE_ATOM(CADR(expr)),newVI);
   }

if (polarity == 0)
   return (notExpr(createAtom(newVI)));
else
   return (createAtom(newVI));
}

/*-------------------------------------------------------------------------
numberNot: nombre de not dans une expression. 
---------------------------------------------------------------------------
retour		: un int. 
---------------------------------------------------------------------------*/
int numberNot(expr,occTH,notTH)
chain_list *expr;
pTH occTH;
pTH notTH;
{
if (ATOM(expr))
   return 0;
else
   {
   int ret = 0;
   if (OPER(expr) == NOT)
      {
		/* le not n'existe pas deja et la variable
		   n'apparait au plus 2 fois */
      if ((searchTH(notTH,VALUE_ATOM(CADR(expr))) == EMPTYTH) &&
          (searchTH(occTH,VALUE_ATOM(CADR(expr))) <= 2))
         return 1;
      else
         return 0;
      }

   while (expr = CDR(expr))
       ret = ret + numberNot(CAR(expr),occTH,notTH);
   return ret;
   }
}

/*-------------------------------------------------------------------------
mapInvExpr:  transforme une expression de polarite autre en
             une expression negative en creant au besoin des
             variables auxiliaires. 
---------------------------------------------------------------------------
retour		: une expression
---------------------------------------------------------------------------*/
chain_list *mapInvExpr(expr,notTH,beh,occTH)
chain_list *expr;
pTH notTH;
befig_list *beh;
pTH occTH;
{
chain_list *ret;
         
ret = createExpr(OPER(expr));
while (expr = CDR(expr))
   {
   if (ATOM(CAR(expr)))		/* creation ou recup. de VI */
      {
      addQExpr(ret,createVIExpr(beh,notExpr(copyExpr(CAR(expr))),notTH,0,occTH));
      }
   else
      {
      if (OPER(CAR(expr)) == NOT)
         addQExpr(ret,copyExpr(CAR(expr)));
      else
         addQExpr(ret,mapInvExpr(CAR(expr),notTH,beh,occTH));
      }
   }
return ret;
}
/*-------------------------------------------------------------------------
void deleteFilsExpr: detruit filsSelect se situant au niveau level.
---------------------------------------------------------------------------
retour		: rien. (modification physique + 
                         desallocation de filsSelect)
---------------------------------------------------------------------------*/
void deleteFilsExpr(expr,filsSelect,level)
chain_list *expr;
chain_list *filsSelect;
int level;
{
if (level == 1)
   {
   chain_list *expr1 = expr;
   
   while (CDR(expr1) && CADR(expr1) != filsSelect)
      expr1 = CDR(expr1);

     /* element trouve*/
   if (CDR(expr1))
      {
      expr1->NEXT = CDR(CDR(expr1));      
      freeExpr(filsSelect);
      }
   }
else
   while (expr = CDR(expr))
      deleteFilsExpr(CAR(expr),filsSelect,--level);
}

/*-------------------------------------------------------------------------
remonteFilsExpr: remonte a la racine filsSelect qui se
                 situe au niveau level.
---------------------------------------------------------------------------
retour		: rien.(modification physique + filsSelect desalloue)
---------------------------------------------------------------------------*/
void remonteFilsExpr(expr,filsSelect,level,caracTH,ssFils)
chain_list *expr;
chain_list *filsSelect;
int level;
pTH caracTH;
chain_list *ssFils;
{
chain_list *expr1 = filsSelect;

	/* ajout des fils de filsSelect dans l'ordre des temps */

while (expr1 = CDR(expr1))
   {
   chain_list *expr2 = expr;
   int tempsExpr1 = searchTH(caracTH,CAR(expr1));

   if (ssFils == CAR(expr1) || !ssFils)
      {
		/* insertion selon le temps */

      while (expr2)
         {
         if (searchTH(caracTH,CADR(expr2)) > tempsExpr1)
            {
            expr2->NEXT = addchain(expr2->NEXT,(void *)CAR(expr1)); 
            expr2 = NULL;
            }
         else
            {
            expr2 = CDR(expr2);
            if (!expr2)
               addQExpr(expr,CAR(expr1));
            }
         }
      if (OPER(filsSelect) == OR)
         expr1->DATA = (void *) createAtom("'0'");
      else
         expr1->DATA = (void *) createAtom("'1'");
      }
   }
	/* elimination de l'argument filsSelect dans expr */

deleteFilsExpr(expr,filsSelect,level);

}

/*-------------------------------------------------------------------------
numberChain_list : calcule le nombre d'arguments d'une liste chainee
---------------------------------------------------------------------------
retour		: int
---------------------------------------------------------------------------*/
int numberChain_list(lc)
chain_list *lc;
{
int cpt = 0;

while(lc)
    {
    cpt++;
    lc = CDR(lc);
    }
return cpt;
}

/*-------------------------------------------------------------------------
maxChain_listExpr : renvoie une liste chainee des ss-expr d'operateur
                    oper possedant le delai max
---------------------------------------------------------------------------
retour		: chain_list
---------------------------------------------------------------------------*/
chain_list *maxChain_listExpr(expr,oper,caracTH)
chain_list *expr;
short oper;
pTH caracTH;
{
chain_list *ret = NULL;
int max = -3;
chain_list *aux;

     /* calcul du max */
aux = expr;
while(aux = CDR(aux))
   if (!ATOM(CAR(aux)) && OPER(CAR(aux)) == oper)
      {
      int delai = searchTH(caracTH,CAR(aux));
      
      if (delai == EMPTYTH)
         {
         printf("maxChain_listExpr : error - bad expression\n");
         displayExpr(CAR(aux));
         exit(-1);
         }
      if (max <  delai)
         max = delai;
      }

    /* chainage des fils egaux au max */
aux = expr;
while(aux = CDR(aux))
   if (!ATOM(CAR(aux)) &&
       OPER(CAR(aux)) == oper && searchTH(caracTH,CAR(aux)) == max)
      ret = addchain(ret,CAR(aux));
return ret;
}
/*-------------------------------------------------------------------------
existFilsOper:  verifie si une ss-expresssion de expr a oper comme
                operateur racine. 
---------------------------------------------------------------------------
retour		: 0 ou 1. 
---------------------------------------------------------------------------*/
int existFilsOper(expr,oper)
chain_list *expr;
short oper;
{
while (expr = CDR(expr))
   if (!ATOM(CAR(expr)) && OPER(CAR(expr)) == oper)
      return 1;
return 0;
}


/*-------------------------------------------------------------------------
saturationExpr: sature une expression en remontant des variables
                du second niveau sur la racine. 
---------------------------------------------------------------------------
retour		: rien. (modification physique)
---------------------------------------------------------------------------*/

void saturationExpr(expr,credit,optim,caracTH)
chain_list *expr;
int credit,optim;
pTH caracTH;
{
chain_list *expr1,*filsSelect;
int arity = lengthExpr(expr);

if (optim == 0)		/* optimisation de surface */
   {
   if (SL_TRACE)
      printf("sat-surface\n");

   expr1 = expr;
   filsSelect = NULL;

	/* peut-on eliminer une ss-expression d'arite = credit + 1 */

   while (expr1 = CDR(expr1))
      {
      if (!ATOM(CAR(expr1)) && OPER(CAR(expr1)) == OPER(expr) &&
          lengthExpr(CAR(expr1)) == credit + 1)
         filsSelect = CAR(expr1);
      }
	/* peut-on eliminer une ss-expression d'arite < credit + 1 */

   if (!filsSelect)
      {
      expr1 = expr;
      while (expr1 = CDR(expr1))
         {
         if (!ATOM(CAR(expr1)) && OPER(CAR(expr1)) == OPER(expr) &&
             lengthExpr(CAR(expr1)) < credit + 1)
            filsSelect = CAR(expr1);
         }
      }
   if (filsSelect)
      {
		/* on remonte filsSelect a la racine */

      remonteFilsExpr(expr,filsSelect,1,caracTH,NULL);

		/* appel recursif si le credit n'est pas epuise */

      if (lengthExpr(expr) < arity + credit &&
           existFilsOper(expr,OPER(expr)))

         saturationExpr(expr,arity + credit - lengthExpr(expr),
                        optim,caracTH);
      }
   else
      {
      expr1 = expr;
 
	/* on se contente de reduire l'arite du dernier fils */

      while (expr1 = CDR(expr1))
         {
         if (!ATOM(CAR(expr1)) && OPER(CAR(expr1)) == OPER(expr))
            filsSelect = CAR(expr1);
         }

      }
   }
else
   {		/* optimisation en delais */

   chain_list *lstFils;
   int numberFils;
   chain_list *auxFils;

   if (SL_TRACE)
      printf("sat-delais\n");

   lstFils = maxChain_listExpr(expr,OPER(expr),caracTH);
   numberFils = numberChain_list(lstFils);

   if (SL_TRACE)
      {
      printf("numberFils = %d\n",numberFils);
      displayExpr(CAR(lstFils));
      }

   while (numberChain_list(lstFils) > credit)
        lstFils = CDR(lstFils);

  if (numberFils == 1)
     {
     if (lengthExpr(CAR(lstFils)) <= credit+1)
        {
                /* on elimine la ss-expr */
        remonteFilsExpr(expr,CAR(lstFils),1,caracTH,NULL);
        credit = 0; lstFils = NULL;
        }
     }

	/* on remonte les ss-expr. 1 seule fois */

   auxFils = lstFils;
   while (auxFils)
         {
         if (lengthExpr(CAR(auxFils)) == 2)
            {
                /* on elimine la ss-expr */
            remonteFilsExpr(expr,CAR(auxFils),1,caracTH,NULL);
            }
         else
            {
		/* On remonte le dernier element de la ss-expr */
            remonteFilsExpr(expr,CAR(auxFils),2,caracTH,
                            searchNumExpr(CAR(auxFils),
                                          lengthExpr(CAR(auxFils))-1));
            }
         auxFils = auxFils->NEXT;
         credit--;
         } 

	/* pas de recursion si le credit n'est pas epuise */
   }
}

/*-------------------------------------------------------------------------
mapExprC4:  applique la decomposition booleenne sur une expression.
---------------------------------------------------------------------------
retour		: une expression
---------------------------------------------------------------------------*/
chain_list *mapExprC4(beh,caracTH,expr,optim,dejaTraite,tp,tn,notTH,occTH,fanout)
befig_list *beh;
pTH caracTH;
chain_list *expr;
int optim;
pTH dejaTraite;
int tp,tn;
pTH notTH,occTH;
int fanout;
{
chain_list *ret;
int empileOKPos,empileOKNeg;
int polar;
chain_list *exprVi;
chain_list *listeFils;
chain_list *supportOptimExpr();

if (ATOM(expr))
   {
   beaux_list *aux;
 
   if (!strcmp(VALUE_ATOM(expr),"'0'") || !strcmp(VALUE_ATOM(expr),"'1'"))
      return(copyExpr(expr));

   if (searchTH(dejaTraite,VALUE_ATOM(expr)) != EMPTYTH)
      return copyExpr(expr);

                /* descente recursive dans la befig */

   aux = beh->BEAUX;
   while (aux && strcmp(aux->NAME,VALUE_ATOM(expr)))
        aux = aux->NEXT;

   if (!aux)			/* ce n'est pas une var. auxiliaire */
      return copyExpr(expr);
   else
      {
      addTH(dejaTraite,VALUE_ATOM(expr),1);
      ret = aux->ABL;
      aux->ABL = mapExprC4(beh,caracTH,aux->ABL,optim,dejaTraite,tp,tn,
                           notTH,occTH,searchTH(occTH,VALUE_ATOM(expr)));
      freeExpr(ret);
      return(copyExpr(expr));
      }
         
   }

if (SL_TRACE)
   {
   printf("==== mapExprC4 \nexpr = ");
   displayExpr(expr);
   printf("\n");
   }

if (OPER(expr) != AND && OPER(expr) != OR &&
    (OPER(expr) == NOT && !ATOM(CADR(expr))))
   {
   printf("mapExprC4 : error - bad expression \n");
   displayExpr(expr);
   exit(-1);
   }

empileOKPos = empileOKExpr(expr,tp,tn,1);
empileOKNeg = empileOKExpr(expr,tp,tn,0);

if (empileOKPos || empileOKNeg)
   flatArityExpr(expr);

if (empileOKPos && empileOKNeg)
   {
   polar = polarityExpr(expr);

   if (polar == 0)	/* negatif */
      ret = copyExpr(expr);

   if (polar == 1)	/* positif */
      if (optim == 0 || profExpr(expr) == 1 || fanout >= FANOUT_MAX)
         ret = copyExpr(expr);
      else
         {
		/* on decompose niveau par niveau */

         ret = createExpr(OPER(expr));
         while (expr = CDR(expr))
            {
            exprVi = flatPolarityExpr(CAR(expr),0);

            if (ATOM(exprVi))
               addQExpr(ret,notExpr(exprVi));
            else
               {
               
			/* creation de VI */

               addQExpr(ret,createVIExpr(beh,exprVi,notTH,0,occTH));
               }
            }      
         }

   if (polar == 2)	/* autre */
      {
      chain_list *invExpr = flatPolarityExpr(expr,0);

      if (optim == 0)
         {
         int nPos = numberNot(expr,occTH,notTH);
         int nNeg = numberNot(invExpr,occTH,notTH);

	/* reduction en recherchant des ss-expressions de meme polarite */

         if (nPos >= 2 && nNeg >= 2)
            {
            chain_list *oldExpr = expr;
            int polarInt;
            int cptNeg = 0;	/* compteur de ss-expr negatives */
            int cptPos = 0;
            
            while (oldExpr = CDR(oldExpr))
               {
               polarInt = polarityExpr(CAR(oldExpr));
               if (polarInt == 0)
                  cptNeg++;
               if (polarInt == 1)
                  cptPos++;
               }
			/* pas de ss-expression de polarite autre */

            if (cptPos + cptNeg == lengthExpr(expr))
               {
               oldExpr = expr;
               ret = createExpr(OPER(expr));

               if (cptPos > cptNeg)   /* solution positive */
                  {
                  while (oldExpr = CDR(oldExpr))
                     {
                     if (polarityExpr(CAR(oldExpr)) == 0)
                        {
                        addQExpr(ret,createVIExpr(beh,
                                    copyExpr(CAR(oldExpr)),notTH,1,occTH));
                        }
                     else
                        addQExpr(ret,copyExpr(CAR(oldExpr)));  
                     }
                  }
               else		/* solution negative */
                  {
                  while (oldExpr = CDR(oldExpr))
                     {
                     if (polarityExpr(CAR(oldExpr)) == 1)
                        {
                        addQExpr(ret,createVIExpr(beh,
                           flatPolarityExpr(CAR(oldExpr),0),notTH,0,occTH));
                        }
                     else
                        addQExpr(ret,copyExpr(CAR(oldExpr)));  
                     }
                  }

			/* sortie apres appel recursif */

               if (SL_TRACE)
                  {
                  printf("==== fin de mapExprC4 \nexpr = ");
                  displayExpr(ret);
                  printf("\n");
                  }
               return (mapExprC4(beh,caracTH,ret,optim,
                                 dejaTraite,tp,tn,notTH,occTH,fanout));
               }
            }

         	/* on minimise le nombre de not */

         if (nPos + 1 > nNeg)
            {
            
			/* solution negative */
            ret = mapInvExpr(expr,notTH,beh,occTH);
            freeExpr(invExpr);
            }
         else
            {
			/* solution positive */

            ret = notExpr(mapInvExpr(invExpr,notTH,beh,occTH));
            }
         }
      else
         {

		/* fonction negative si fanout faible */

         if (fanout >= FANOUT_MAX)
            ret = notExpr(mapInvExpr(invExpr,notTH,beh,occTH));
         else
            {
            ret = mapInvExpr(expr,notTH,beh,occTH);
            freeExpr(invExpr);
            }
         }
      }
   }
else
   {
   if (empileOKPos)
      {
      polar = polarityExpr(expr);

      if (polar == 0)	/* negatif */
         {

	/* on decompose niveau par niveau  avec un */
  	/* non-respect eventuel de la contrainte d'empilement */

         ret = createExpr(OPER(expr));
         while (expr = CDR(expr))
           {
           exprVi = copyExpr(CAR(expr));

			/* creation de VI */

           addQExpr(ret,createVIExpr(beh,exprVi,notTH,1,occTH));
           }
         }

      if (polar == 1)	/* positif */
         if (optim == 0 || profExpr(expr) == 1 || fanout >=4)
            ret = copyExpr(expr);
         else
            {
		/* on decompose niveau par niveau */

            ret = createExpr(OPER(expr));
            while (expr = CDR(expr))
               {
               exprVi = flatPolarityExpr(CAR(expr),0);

               if (ATOM(exprVi))
                  addQExpr(ret,notExpr(exprVi));
               else
                  {
			/* creation de VI */

                  addQExpr(ret,createVIExpr(beh,exprVi,notTH,0,occTH));
                  }
               }      
            }

      if (polar == 2)	/* autre */
         {
         chain_list *invExpr = flatPolarityExpr(expr,0);
   
         if (optim == 0)
            {
			/* solution positive */

            ret = notExpr(mapInvExpr(invExpr,notTH,beh,occTH));
            }
         else
            {

		/* on decompose niveau par niveau */

            ret = createExpr(OPER(expr));
            while (expr = CDR(expr))
               {
               exprVi = flatPolarityExpr(CAR(expr),0);

               if (ATOM(exprVi))
                  addQExpr(ret,notExpr(exprVi));
               else
                  {
                  addQExpr(ret,createVIExpr(beh,exprVi,notTH,0,occTH));
                  }
               }
            }
         }
      }

   if (empileOKNeg)
      {
      polar = polarityExpr(expr);

      if (polar == 0)	/* negatif */
         ret = copyExpr(expr);


		/* on transgresse les contraintes d'empilements */

      if (polar == 1)	/* positif */
         if (optim == 0 || profExpr(expr) == 1 || fanout >= FANOUT_MAX)
            ret = copyExpr(expr);
         else
            {
		/* on decompose niveau par niveau */

            ret = createExpr(OPER(expr));
            while (expr = CDR(expr))
               {
               exprVi = flatPolarityExpr(CAR(expr),0);
   
               if (ATOM(exprVi))
                  addQExpr(ret,notExpr(exprVi));
               else
                  {
			/* creation de VI */

                  addQExpr(ret,createVIExpr(beh,exprVi,notTH,0,occTH));
                  }
               }      
            }

      if (polar == 2)	/* autre */

		/* fonction negative d'office */
         {

		/* fonction negative si fanout faible */

         if (fanout >= FANOUT_MAX)
            {
            chain_list *invExpr = flatPolarityExpr(expr,0);
            ret = notExpr(mapInvExpr(invExpr,notTH,beh,occTH));
            }
         else
            ret = mapInvExpr(expr,notTH,beh,occTH);
         }

      }
   if (!empileOKPos && !empileOKNeg)

	/* l'expression ne respecte pas la contrainte d'empilement */

      {
      int arity = lengthExpr(expr);

      if (tn < arity || tp < arity)
         {
         printf("cutExprC4 : error - bad decomposition\n");
         displayExpr(expr);
         printf("arity = %d  tp_max = %d tn_max = %d\n",arity,tp,tn);
         exit(-1);
         }


		/* fonction negative si fanout faible */

      if (fanout >= FANOUT_MAX)
         {
         chain_list *invExpr = flatPolarityExpr(expr,0);

         calculDelaisExpr(beh,caracTH,invExpr,0); 
         ret = notExpr(creditExpr(beh,invExpr,tp,tn,tp,tn,optim,caracTH,notTH,occTH,1));
         }
      else
         ret = creditExpr(beh,expr,tp,tn,tp,tn,optim,caracTH,notTH,occTH,1);
      }
   }

if (SL_TRACE)
   {
   printf("==== fin de mapExprC4 \nret = ");
   displayExpr(ret);
   printf("\n");
   }
	/* traitement recursif sur les atomes de ret
           si optim == 1
           on ne selectionne que le support a optimser en delais 
           si optim == 0
           on selectionne tout le support  */

calculDelaisExpr(beh,caracTH,ret,0);

if (optim == 1)
   {
   listeFils = supportOptimExpr(ret,caracTH,searchTH(caracTH,ret));
   while (listeFils)
      {
      if (searchTH(dejaTraite,(char *) listeFils->DATA) == EMPTYTH)
         mapExprC4(beh,caracTH,createAtom((char *)listeFils->DATA),optim,
                   dejaTraite,tp,tn,notTH,occTH,1);
      listeFils = listeFils->NEXT;
      }
   freechain(listeFils);
   }
else
   {
   listeFils = supportChain_listExpr(ret);
   while (listeFils)
      {
      if (searchTH(dejaTraite,(char *) listeFils->DATA) == EMPTYTH)
         mapExprC4(beh,caracTH,createAtom((char *)listeFils->DATA),optim,
                   dejaTraite,tp,tn,notTH,occTH,1);
      listeFils = listeFils->NEXT;
      }
   freechain(listeFils);
   }

return ret;
}

/*-------------------------------------------------------------------------
calculSerieMax	: calcule le nombre optimal de transistors en serie.
---------------------------------------------------------------------------
retour		: void 
---------------------------------------------------------------------------*/
void calculSerieMax(optim,tp,tn,max_tp,max_tn)
int optim;
int *tp,*tn;
{
switch (optim)
  {
  case  0 : *tp = 6;
            *tn = 6;
            break;
  case  1 : *tp = 4;
            *tn = 5;
            break;
  case  2 : *tp = 4;
            *tn = 4;
            break;
  case  3 : *tp = 3;
            *tn = 4;
            break;
  case  4 : *tp = 3;
            *tn = 4;
            break;
   }
if (max_tp < *tp)
   *tp = max_tp;
if (max_tn < *tn)
   *tn = max_tn;
}

/*-------------------------------------------------------------------------
creditExpr: decoupe l'expression par un systeme de credit.
---------------------------------------------------------------------------
retour		: rien. (modification physique)
---------------------------------------------------------------------------*/

chain_list *creditExpr(beh,expr,tp,tn,tpLevel,tnLevel,optim,caracTH,notTH,occTH,prof)
befig_list *beh;
chain_list *expr;
int tp, tn, tpLevel, tnLevel, optim;
pTH caracTH;
pTH notTH;
pTH occTH;
int prof;
{
int creditMax;
int creditMaxFils;
int arity = lengthExpr(expr);
chain_list *aux;
chain_list *fils;
chain_list *ret;
int deuxFilsOper;
int creditFrere = 1;


ret = createExpr(OPER(expr));

if (OPER(expr) == OR)
   {
		/* creditMax = min(tn,tnLevel) */
                    
   if (tn > tnLevel)
      creditMax = tnLevel;
   else
      creditMax = tn;


		/* creditMaxFils = min(tp,tlLevel-1) */

   if (tp > tpLevel - 1)
      creditMaxFils = tpLevel - 1;
   else
      creditMaxFils = tp;
   }

if (OPER(expr) == AND)
   {
		/* creditMax = min(tp,tpLevel) */

   if (tp > tpLevel)
      creditMax = tpLevel;
   else
      creditMax = tp;

		/* creditMaxFils = min(tp,tlLevel-1) */

   if (tn > tnLevel - 1)
      creditMaxFils = tnLevel - 1;
   else
      creditMaxFils = tn;
   }

	/* pour eviter les congestions du routage 2 canaux par zone */
        /* deux heuristiques :
               1. limitation pour un operateur du deuxieme niveau
                  a deux fils ayant un operateur different
               2. limitation a quatre niveaux d'operateurs
        */

if (prof >= 2)
   deuxFilsOper = 1;
else
   deuxFilsOper = 0;

	/* a priori cette seconde heuristique est verifiee systematiquement
           si l'on verifie la premiere ... */

if (prof >= MAXLEVEL)
   creditMaxFils = 1;

	/* petite verification */

if (creditMax <= 1)
   {
   printf("creditExpr : error - bad argument \n");
   printf("credit = %d\n",creditMax);
   displayExpr(expr);
   exit(-1);
   }

if (SL_TRACE)
   {
   printf("\n*** Entree creditExpr :\n");
   printf("credit max = %d credit max fils = %d\n",creditMax,creditMaxFils);
   displayExpr(expr);
   }
		/* on repousse certaines ss-expressions
                   quand le credit est insuffisant
                   on effectue une modification physique */

if (creditMax < arity)
   {
	/* on repousse les entrees les moins retardees */ 

   chain_list *aux = expr;
   chain_list *inter = createExpr(OPER(expr));
   int cpt = 0;

   for(cpt =0,aux = CDR(expr);cpt <= arity - creditMax; cpt++,aux = CDR(aux))
      addQExpr(inter,copyExpr(CAR(aux)));

   for(cpt =0;cpt <= arity - creditMax; cpt++)
      {
      deleteNumExpr(expr,0);
      }

   addQExpr(expr,inter);
   calculDelaisExpr(beh,caracTH,inter,0);

   arity = lengthExpr(expr);

   if (SL_TRACE)
      {
      printf("creditExpr : apres selection = \n");
      displayExpr(expr);
      }
   }

		/* a partir de maintenant, le credit >= arite */


	/* on remonte les ss-expr de meme operateur */

if (creditMax > arity)
   {
            		/* saturation sur l'operateur pere */
			/* si fils de meme operateur */
			/* quelquesoit le mode d'optimisation */

   if (existFilsOper(expr,OPER(expr)))
      {
      if (SL_TRACE)
         {
         printf("saturation : credit = %d\n",creditMax-arity);
         displayExpr(expr);
         }
      saturationExpr(expr,creditMax-arity,optim,caracTH);
      }

			/* calcul de la nouvelle arite */

   arity = lengthExpr(expr);


			/* fin de la saturation */
   }

		/* heuristique pour eviter la congestion */

if (deuxFilsOper == 1)
   {
   int coOper = 0;

	/* on calcule le nombre de fils ayant un operateur different de 
           celui de expr et qui ne soit pas unaire */

   fils = expr;
   while (fils = CDR(fils))
      if ((numberAtomExpr(CAR(fils)) > 1) && OPER(CAR(fils)) != OPER(expr))
         coOper++;

   if (coOper > 2)
      {
      fils = expr;
      while ((fils = CDR(fils)) && (coOper > 2))
         {
         if ((numberAtomExpr(fils) > 1) && OPER(CAR(fils)) != OPER(expr))
            {
            coOper--;
            fils->DATA = (void *) createVIExpr(beh,flatPolarityExpr(CAR(fils),0),notTH,0,occTH);
            }
         }
      }
   }

		/* si on optimise en delai,
                   on repousse les entrees peu retardees si il existe
                   un ecart important avec l'entree(s) la + retardees */


if (optim == 1 && arity >= 2)
   {
   chain_list *aux;
   chain_list *inter;
   int cpt = 0;
   int delaisMax;


   expr = simplif10Expr(expr);
   calculDelaisExpr(beh,caracTH,expr,0);

   aux = expr;
   inter = createExpr(OPER(expr));
   delaisMax = searchTH(caracTH,searchNumExpr(expr,lengthExpr(expr)-1));

   if (delaisMax == EMPTYTH)
      {
      printf("creditExpr : error - expr not characterized\n");
      displayExpr(expr);
      exit(-1);
      }

		/* on descend les fils peu retardes */

   while (aux = CDR(aux))
      {
      int delaisInt = searchTH(caracTH,CAR(aux));
     
      if (delaisInt + 1000 <= delaisMax) 
         {
         addQExpr(inter,copyExpr(CAR(aux)));
         cpt++;
         } 
      }

		/* si cpt = 1, on evitera de donner du credit
                   au frere  dans l'appel recursif */

   if (cpt == 1)
      {
      creditFrere = 0;
      }

		/* si au moins deux fils sont descendables ... */

   if (cpt >= 2)
      {
      int i;

      if (SL_TRACE)
         {
         printf("decomposition speciale\n");
         displayExpr(expr);   
         }

      for(i =1;i <= cpt; i++)
         {
         deleteNumExpr(expr,0);
         }


      addQExpr(expr,inter);
      calculDelaisExpr(beh,caracTH,inter,0);
   
      arity = lengthExpr(expr);

      }
   else
      freeExpr(inter);

   ret = expr;
   calculDelaisExpr(beh,caracTH,ret,0);
   }
else
   {
   ret = simplif10Expr(expr);
   calculDelaisExpr(beh,caracTH,ret,0);
   }

		/* creation de VI pour les fils de meme oper 
                   ou si creditFrere est a 0 */

fils = ret;
while(fils = CDR(fils))
   {
   if (!ATOM(CAR(fils)) && OPER(ret) == OPER(CAR(fils)))
      {
      fils->DATA = (void *) createVIExpr(beh,flatPolarityExpr(CAR(fils),0),notTH,0,occTH);
      }
		/* on cree une VI pour la ss-expr retardee comprenant les
                   freres peu retardes */

   else
      if (creditFrere == 0 && CDR(fils))   /* ce n'est pas le dernier fils */
         {
         if (numberAtomExpr(CAR(fils)) > 1)
            {
            fils->DATA = (void *) createVIExpr(beh,flatPolarityExpr(CAR(fils),0),notTH,0,occTH);
            creditFrere = 1;
            }
         }
   }

		/* le credit pour les fils est epuise */

if (creditMaxFils <= 1)
   {
   for(aux = CDR(ret);aux;aux = CDR(aux))
      {
      if (ATOM(CAR(aux)))
         {
         aux->DATA = (void *) createVIExpr(beh,
                          notExpr(copyExpr(CAR(aux))),notTH,0,occTH);
         }
      else
         if (OPER(CAR(aux)) != NOT)
            {
            aux->DATA = (void *) createVIExpr(beh,
                            flatPolarityExpr(CAR(aux),0),notTH,0,occTH);
            }
      }
   }
else		/* le credit n'est pas epuise */
   {
		/* appel recursif */

   if (OPER(ret) == OR)
      {
      for(aux = CDR(ret);aux;aux = CDR(aux))
        if (ATOM(CAR(aux)) || OPER(CAR(aux)) == NOT)
           {
           if (ATOM(CAR(aux)))
              {
              aux->DATA = (void *) createVIExpr(beh,
                               notExpr(copyExpr(CAR(aux))),notTH,0,occTH);
              }
           }
        else
           {
           		/* si le credit n'est pas epuise
                           on en donne au dernier */

           if (creditMax > arity && CDR(aux) == NULL)
              {
              aux->DATA = (void *) creditExpr(beh,CAR(aux),tp,1+creditMax-arity,
                         tpLevel-1,tnLevel-1,optim,caracTH,notTH,occTH,prof+1);
              }
           else
              aux->DATA = (void *) creditExpr(beh,CAR(aux),tp,1,
                         tpLevel-1,tnLevel-1,optim,caracTH,notTH,occTH,prof+1);
           }
      }

   if (OPER(ret) == AND)
      {
      for(aux = CDR(ret);aux;aux = CDR(aux))
        if (ATOM(CAR(aux)) || OPER(CAR(aux)) == NOT)
           {
           if (ATOM(CAR(aux)))
              {
              aux->DATA = (void *) createVIExpr(beh,
                               notExpr(copyExpr(CAR(aux))),notTH,0,occTH);
              }
           }
        else
           {
           		/* si le credit n'est pas epuise
                           on en donne au dernier */

           if (creditMax > arity && CDR(aux) == NULL)
              {
              aux->DATA = (void *) creditExpr(beh,CAR(aux),1+creditMax-arity,tn,
                         tpLevel-1,tnLevel-1,optim,caracTH,notTH,occTH,prof+1);
              }
           else
              aux->DATA = (void *) creditExpr(beh,CAR(aux),1,tn,
                         tpLevel-1,tnLevel-1,optim,caracTH,notTH,occTH,prof+1);
           }
      }
   }

return ret;
}

/*-------------------------------------------------------------------------
mapBeh	: decompose pour C4. 
---------------------------------------------------------------------------
retour		: void 
---------------------------------------------------------------------------*/
void mapBeh(beh,optim,delais,optimPO,tp_max,tn_max)
befig_list *beh;
int optim;
ptype_list *delais;
chain_list *optimPO;
int tp_max,tn_max;
{
berin_list *in;
beaux_list *aux;
beout_list *out;
bereg_list *reg;
bebus_list *bus;
bebux_list *bux;
biabl_list *biabl;
int val,delaisMoyen;
pTH caracBeh();
pTH caracTH; 
pTH dejaTraite;
pTH notTH;
pTH occTH;
chain_list *expr;
int tp,tn;
int tp_optim,tn_optim;

		/* calcul des tp et tn optimaux */

calculSerieMax(optim,&tp,&tn,tp_max,tn_max);

tp_optim = 3;
if (tp < tp_optim)
   tp_optim = tp;

tn_optim = 4;
if (tn < tn_optim)
   tn_optim = tn;

         /* remplissage de la table signal/nombre d'occurence */
 
occTH = createTH(100);
 
in = beh->BERIN;
while (in)
   {
   addTH(occTH,in->NAME,0);
   in = in->NEXT;
   }
 
aux = beh->BEAUX;
while (aux)
   {
   addTH(occTH,aux->NAME,0);
   aux = aux->NEXT;
   }
remplTHOccBeh(beh,occTH);
 
		/* parcours des bus pour inverser les donnees */

bus = beh->BEBUS;
while (bus)
   {  
   biabl = bus->BIABL;
   while (biabl)
      {
      if (biabl->VALABL)
         {
         if (ATOM(biabl->VALABL))
            {
            if (!strcmp(VALUE_ATOM(biabl->VALABL),"'0'"))
               biabl->VALABL = createAtom("'1'");
            else
               if (!strcmp(VALUE_ATOM(biabl->VALABL),"'1'"))
                  biabl->VALABL = createAtom("'0'");
               else
                  biabl->VALABL = notExpr(biabl->VALABL);
            }
         else
            biabl->VALABL = flatPolarityExpr(biabl->VALABL,0);
         }
      biabl = biabl->NEXT;
      }
   bus = bus->NEXT;
   }


bux = beh->BEBUX;
while (bux)
   {  
   biabl = bux->BIABL;
   while (biabl)
      {
      if (biabl->VALABL)
         {
         if (ATOM(biabl->VALABL))
            {
            if (!strcmp(VALUE_ATOM(biabl->VALABL),"'0'"))
               biabl->VALABL = createAtom("'1'");
            else
               if (!strcmp(VALUE_ATOM(biabl->VALABL),"'1'"))
                  biabl->VALABL = createAtom("'0'");
               else
                  biabl->VALABL = notExpr(biabl->VALABL);
            }
         else
            biabl->VALABL = flatPolarityExpr(biabl->VALABL,0);
         }
      biabl = biabl->NEXT;
      }
   bux = bux->NEXT;
   }

		/* caracterisation */

caracTH = caracBeh(beh,delais,0);
dejaTraite = createTH(100);
notTH = createTH(200);

		/* ----- a correler avec le mode d'optimisation */

delaisMoyen = delaisCarac(caracTH,optim);

	/* parcours des expressions - decomposition booleenne */

		/* cones optimises en delais */

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

      if ((del = searchTH(caracTH,out->ABL)) > delaisMoyen ||
          memberChain(out->NAME,optimPO))
         {
         if (SL_TRACE)
            printf("optimisation en delais : %s\n",out->NAME);
         expr = mapExprC4(beh,caracTH,out->ABL,1,dejaTraite,tp_optim,tn_optim,notTH,occTH,1);

         /* remise a jour de caracTH avec le nouvel ABL */
         addTH(caracTH,expr,del);
 
         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 = mapExprC4(beh,caracTH,biabl->CNDABL,1,dejaTraite,tp_optim,tn_optim,notTH,occTH,1);
 
            /* remise a jour de caracTH avec le nouvel ABL */
            addTH(caracTH,expr,del);

            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }
	 if ((del = searchTH(caracTH,biabl->VALABL)) > delaisMoyen
             || memberChain(reg->NAME,optimPO))
            {
            expr = mapExprC4(beh,caracTH,biabl->VALABL,1,dejaTraite,tp_optim,tn_optim,notTH,occTH,1);
 
            /* remise a jour de caracTH avec le nouvel ABL */
            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 = mapExprC4(beh,caracTH,biabl->CNDABL,1,dejaTraite,tp_optim,tn_optim,notTH,occTH,1);
 
            /* remise a jour de caracTH avec le nouvel ABL */
            addTH(caracTH,expr,del);

            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }
	 if ((del = searchTH(caracTH,biabl->VALABL)) > delaisMoyen
             || memberChain(bus->NAME,optimPO))
            {
			/* inversion pour les bus */

            expr = mapExprC4(beh,caracTH,biabl->VALABL,1,dejaTraite,tp_optim,tn_optim,notTH,occTH,1);
 
            /* remise a jour de caracTH avec le nouvel ABL */
            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 = mapExprC4(beh,caracTH,biabl->CNDABL,1,dejaTraite,tp_optim,tn_optim,notTH,occTH,1);
 
            /* remise a jour de caracTH avec le nouvel ABL */
            addTH(caracTH,expr,del);

            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }
	 if ((del = searchTH(caracTH,biabl->VALABL)) > delaisMoyen
             || memberChain(bux->NAME,optimPO))
            {
			/* inversion pour les bux */

            expr = mapExprC4(beh,caracTH,biabl->VALABL,1,dejaTraite,tp_optim,tn_optim,notTH,occTH,1);
 
            /* remise a jour de caracTH avec le nouvel ABL */
            addTH(caracTH,expr,del);

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



if (SL_TRACE)
   displayBeh(beh,1);

		/* cones a optimiser en surface */

aux = beh->BEAUX;
while (aux)
   {
   if (aux->ABL)
      {
      val = searchTH(dejaTraite,aux->NAME);
      if (val == EMPTYTH)
	 {
         expr = mapExprC4(beh,caracTH,aux->ABL,0,dejaTraite,tp,tn,
                notTH,occTH,searchTH(occTH,aux->NAME));
         freeExpr(aux->ABL);
         aux->ABL = expr;
         addTH(dejaTraite,aux->NAME,1);
	 }
      }
   aux = aux->NEXT;
   }

out = beh->BEOUT;
while (out)
   {
   if (out->ABL)
      {
      val = searchTH(caracTH,out->ABL);
      if (val != EMPTYTH && val  <= delaisMoyen)
	 {
         if (SL_TRACE)
            printf("optimisation en surface : %s\n",out->NAME);
         expr = mapExprC4(beh,caracTH,out->ABL,0,dejaTraite,tp,tn,notTH,occTH,1);
         freeExpr(out->ABL);
         out->ABL = expr;
	 }
      }
   out = out->NEXT;
   }

reg = beh->BEREG;
while (reg)
   {  
   biabl = reg->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
         val = searchTH(caracTH,biabl->CNDABL);
         if (val != EMPTYTH && val  <= delaisMoyen)
	    {
            expr = mapExprC4(beh,caracTH,biabl->CNDABL,0,dejaTraite,tp,tn,notTH,occTH,1);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
	    }
         val = searchTH(caracTH,biabl->VALABL);
         if (val != EMPTYTH && val  <= delaisMoyen)
	    {
            expr = mapExprC4(beh,caracTH,biabl->VALABL,0,dejaTraite,tp,tn,notTH,occTH,1);
            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)
         {
         val = searchTH(caracTH,biabl->CNDABL);
         if (val != EMPTYTH && val  <= delaisMoyen)
	    {
            expr = mapExprC4(beh,caracTH,biabl->CNDABL,0,dejaTraite,tp,tn,notTH,occTH,1);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
	    }
         val = searchTH(caracTH,biabl->VALABL);
         if (val != EMPTYTH && val  <= delaisMoyen)
	    {
            expr = mapExprC4(beh,caracTH,biabl->VALABL,0,dejaTraite,tp,tn,notTH,occTH,1);
            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
	    }
         }
      biabl = biabl->NEXT;
      }
   bus = bus->NEXT;
   }  


bus = beh->BEBUS;
while (bus)
   {  
   biabl = bus->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
         val = searchTH(caracTH,biabl->CNDABL);
         if (val != EMPTYTH && val  <= delaisMoyen)
	    {
            expr = mapExprC4(beh,caracTH,biabl->CNDABL,0,dejaTraite,tp,tn,notTH,occTH,1);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
	    }
         val = searchTH(caracTH,biabl->VALABL);
         if (val != EMPTYTH && val  <= delaisMoyen)
	    {
            expr = mapExprC4(beh,caracTH,biabl->VALABL,0,dejaTraite,tp,tn,notTH,occTH,1);
            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)
         {
         val = searchTH(caracTH,biabl->CNDABL);
         if (val != EMPTYTH && val  <= delaisMoyen)
	    {
            expr = mapExprC4(beh,caracTH,biabl->CNDABL,0,dejaTraite,tp,tn,notTH,occTH,1);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
	    }
         val = searchTH(caracTH,biabl->VALABL);
         if (val != EMPTYTH && val  <= delaisMoyen)
	    {
            expr = mapExprC4(beh,caracTH,biabl->VALABL,0,dejaTraite,tp,tn,notTH,occTH,1);
            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
	    }
         }
      biabl = biabl->NEXT;
      }
   bux = bux->NEXT;
   }


destroyTH(caracTH);
destroyTH(dejaTraite);
destroyTH(notTH);
destroyTH(occTH);
}
