
/****************************************************************************/
/*                                                                          */
/*                      Chaine de CAO & VLSI   Alliance                     */
/*                                                                          */
/*    Produit : synthetiseur logique                                        */
/*    Fichier : devxor.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 : 31/01/1992     */
/*                                                                          */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*                                                                          */
/****************************************************************************/

#include MUT_H
#include LOG_H
#include "bib.h"
#include BEH_H

/*-------------------------------------------------------------------------
devXorOptimExpr: elimination des XOR 
---------------------------------------------------------------------------
retour		: une expression sans XOR.
---------------------------------------------------------------------------*/
chain_list *devXorOptimExpr(beh,caracTH,occTH,expr,optim,dejaTraite)
befig_list *beh;
pTH caracTH;
pTH occTH;
chain_list *expr;
int optim;
pTH dejaTraite;
{
static int co = 0;
chain_list *charToExpr();

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)
      return copyExpr(expr);
   else
      {
      addTH(dejaTraite,VALUE_ATOM(expr),1);
      aux->ABL = devXorOptimExpr(beh,caracTH,occTH,aux->ABL,optim,dejaTraite);
      return(copyExpr(expr));
      }
   }

		/* traitement des XOR - NXOR */

if ((OPER(expr) == XOR) || (OPER(expr) == NXOR))
  {
  char *a,*b;
  short polarite = 0;
  char *newVi ;
  char *gensym();
  short cptNot = 0;
  chain_list *oldExpr = expr;
  int arity;

	/* calcul de la polarite et elimination des inverseurs */

  while(oldExpr = CDR(oldExpr))
     if (!ATOM(CAR(oldExpr)) && OPER(CAR(oldExpr)) == NOT)
	{
	chain_list *aux = CAR(oldExpr);
	oldExpr->DATA = (void *)copyExpr(CADR(CAR(oldExpr)));
	freeExpr(aux);
	cptNot++;
	}

  if ((OPER(expr) == XOR && (cptNot % 2) == 1) ||
      (OPER(expr) == NXOR && (cptNot % 2 == 0)))
	polarite = 1;

	/* creation de VI pour les ss-expressions d'operateurs */

  if (anyExpr(profExpr,expr))
     {
     oldExpr = expr;
     while(oldExpr = CDR(oldExpr))
        if (!ATOM(CAR(oldExpr))) 
	   {
	   newVi = gensym("auxxor",++co);
	   beh->BEAUX = beh_addbeaux(beh->BEAUX,newVi,copyExpr(CAR(oldExpr)),NULL);
	   oldExpr->DATA = (void *) createAtom(newVi);
	   }
     }

	/* cas general */

  a = VALUE_ATOM(CAR(CDR(expr)));
  b = VALUE_ATOM(CAR(CDR(CDR(expr))));

	/*--------- cas du XOR a 2 entrees ---------*/

  if ((arity = lengthExpr(expr)) == 2)
     {
     chain_list *ret, *aux1, *aux2;



		/* a xor b = (a + b) . ('a + 'b) */
     aux1 = OR2(createAtom(a),createAtom(b));
     aux2 = OR2(notExpr(createAtom(a)),notExpr(createAtom(b)));
     ret  = AND2(aux1,aux2);

		/* appel recursif sur les fils */

     devXorOptimExpr(beh,caracTH,occTH,createAtom(a),optim,dejaTraite);
     devXorOptimExpr(beh,caracTH,occTH,createAtom(b),optim,dejaTraite);

     if (polarite) 
        return notExpr(ret);
     else
        return ret;
     }

		/*--------- cas du xor 3 ---------*/

  if (arity == 3)
     {
     char *c = VALUE_ATOM(searchNumExpr(expr,2));
     chain_list *ret, *aux1, *aux2, *aux3, *aux4;

     if (optim == 0)

		/* Optimisation en surface */
	{
        int numa, numb, numc;

        numa = searchTH(occTH,a);
        numb = searchTH(occTH,b);
        numc = searchTH(occTH,c);
    
		/* les variables ne sont pas trop utilises ailleurs */

        if ((numa < 3 && numb < 3) || (numa < 3 && numc < 3) || 
   	    (numb < 3 && numc < 3))
	   {

		/* on cree une variable auxilaire = a xor b */
		/* la variable c doit etre la + retardee    */ 

           aux1 = OR2(createAtom(a),createAtom(b));
           aux2 = OR2(notExpr(createAtom(a)),notExpr(createAtom(b)));
           aux3 = AND2(aux1,aux2);

		/* on inverse sur a xor b */

           if (polarite) 
              aux3 = notExpr(aux3);

           newVi = gensym("auxxor",++co);
           beh->BEAUX = beh_addbeaux(beh->BEAUX,newVi,aux3,NULL);

           aux1 = OR2(createAtom(newVi),createAtom(c));
           aux2 = OR2(notExpr(createAtom(newVi)),notExpr(createAtom(c)));
           ret  = AND2(aux1,aux2);

		/* appel recursif sur les fils */

	   devXorOptimExpr(beh,caracTH,occTH,createAtom(a),optim,dejaTraite);
	   devXorOptimExpr(beh,caracTH,occTH,createAtom(b),optim,dejaTraite);
	   devXorOptimExpr(beh,caracTH,occTH,createAtom(c),optim,dejaTraite);

           return ret;
	   }
        }

	/* a xor b xor c = c.('a.'b + a.b) + 'c.('a + 'b).(a + b) */

      ret = charToExpr(
               "(or (and c (or (and (not a) (not b)) (and a b))) (and (not c) (and (or (not a) (not b)) (or a b))))");

     substPhyExpr(ret,"a",createAtom(a));
     substPhyExpr(ret,"b",createAtom(b));
     substPhyExpr(ret,"c",createAtom(c));


		/* appel recursif sur les fils */

     devXorOptimExpr(beh,caracTH,occTH,createAtom(a),optim,dejaTraite);
     devXorOptimExpr(beh,caracTH,occTH,createAtom(b),optim,dejaTraite);
     devXorOptimExpr(beh,caracTH,occTH,createAtom(c),optim,dejaTraite);

     if (polarite) 
	return notExpr(ret);
     else
	return ret;
     }

  if (arity >= 4)
	{
        int div = arity / 3;
        int mod = arity % 3;
        int nbSsexpr, nbElts;
        chain_list *ret = createExpr(OPER(expr));

        expr = CDR(expr);

		/* creation de div ss-expressions */
        for(nbSsexpr = 0; nbSsexpr < div; nbSsexpr++)
           {
           chain_list *ssExpr = createExpr(XOR);

                /* dans chaque ss-expr, ajout de 3 elts */
           for(nbElts = 0; nbElts < 3; nbElts++)
              {
              addQExpr(ssExpr,copyExpr(CAR(expr)));
              expr = CDR(expr);
              }
           addQExpr(ret,ssExpr);
           }
         if (mod == 1)
            addQExpr(ret,copyExpr(CAR(expr)));
         else if (mod == 2)
                 {
                 chain_list *ssExpr = createExpr(XOR);

                 addQExpr(ssExpr,copyExpr(CAR(expr)));
                 addQExpr(ssExpr,copyExpr(CAR(CDR(expr))));
                 addQExpr(ret,ssExpr);
                 } 

        return devXorOptimExpr(beh,caracTH,occTH,ret,optim,dejaTraite);
	}
  }
else
  {
  chain_list *ret = createExpr(OPER(expr));

  while(expr = CDR(expr))
       addQExpr(ret,devXorOptimExpr(beh,caracTH,occTH,CAR(expr),optim,dejaTraite));
  return ret;
  }
}

/*-------------------------------------------------------------------------
devXorBeh	: elimine les occurences des xor dans une befig.
---------------------------------------------------------------------------
retour		: void 
---------------------------------------------------------------------------*/
void devXorBeh(beh,optim,delais,optimPO)
befig_list *beh;
int optim;
ptype_list *delais;
chain_list *optimPO;
{
berin_list *in;
beout_list *out;
bereg_list *reg;
bebus_list *bus;
bebux_list *bux;
biabl_list *biabl;
beaux_list *aux;
pTH caracTH; 
pTH occTH;
pTH dejaTraite;
int val,delaisMoyen;
pTH caracBeh();
chain_list *expr;

	/* 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;
   }

dejaTraite = createTH(100);
remplTHOccBeh(beh,occTH);

		/* caracterisation */

caracTH = caracBeh(beh,delais,0);

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

delaisMoyen = delaisCarac(caracTH,optim);

		/* parcours des expressions - developpement des xor */

		/* 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))
         {
         expr = devXorOptimExpr(beh,caracTH,occTH,out->ABL,1,dejaTraite);
/*
         printf("optimisation en delais : %s\n",out->NAME);
*/
         /* 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 = devXorOptimExpr(beh,caracTH,occTH,biabl->CNDABL,1,dejaTraite);
            /* 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 = devXorOptimExpr(beh,caracTH,occTH,biabl->VALABL,1,dejaTraite);
            /* 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 = devXorOptimExpr(beh,caracTH,occTH,biabl->CNDABL,1,dejaTraite);
            /* 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))
            {
            expr = devXorOptimExpr(beh,caracTH,occTH,biabl->VALABL,1,dejaTraite);
            /* 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 = devXorOptimExpr(beh,caracTH,occTH,biabl->CNDABL,1,dejaTraite);
            /* 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))
            {
            expr = devXorOptimExpr(beh,caracTH,occTH,biabl->VALABL,1,dejaTraite);
            /* 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;
   }  

		/* cones optimises en surface */

out = beh->BEOUT;
while (out)
   {
   if (out->ABL)
      {
      val = searchTH(caracTH,out->ABL);
      if (val != EMPTYTH && val  <= delaisMoyen
           && !memberChain(out->NAME,optimPO))
	 {
/*
         printf("optimisation en surface : %s\n",out->NAME);
*/
         expr = devXorOptimExpr(beh,caracTH,occTH,out->ABL,0,dejaTraite);
         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
             && !memberChain(reg->NAME,optimPO))
	    {
            expr = devXorOptimExpr(beh,caracTH,occTH,biabl->CNDABL,0,dejaTraite);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
	    }
         val = searchTH(caracTH,biabl->VALABL);
         if (val != EMPTYTH && val  <= delaisMoyen
             && !memberChain(reg->NAME,optimPO))
	    {
            expr = devXorOptimExpr(beh,caracTH,occTH,biabl->VALABL,0,dejaTraite);
            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
             && !memberChain(bus->NAME,optimPO))
	    {
            expr = devXorOptimExpr(beh,caracTH,occTH,biabl->CNDABL,0,dejaTraite);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
	    }
         val = searchTH(caracTH,biabl->VALABL);
         if (val != EMPTYTH && val  <= delaisMoyen
             && !memberChain(bus->NAME,optimPO))
	    {
            expr = devXorOptimExpr(beh,caracTH,occTH,biabl->VALABL,0,dejaTraite);
            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
             && !memberChain(bux->NAME,optimPO))
	    {
            expr = devXorOptimExpr(beh,caracTH,occTH,biabl->CNDABL,0,dejaTraite);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
	    }
         val = searchTH(caracTH,biabl->VALABL);
         if (val != EMPTYTH && val  <= delaisMoyen
             && !memberChain(bux->NAME,optimPO))
	    {
            expr = devXorOptimExpr(beh,caracTH,occTH,biabl->VALABL,0,dejaTraite);
            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
	    }
         }
      biabl = biabl->NEXT;
      }
   bux = bux->NEXT;
   }  


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