/****************************************************************************/
/*                                                                          */
/*                      Chaine de CAO & VLSI   Alliance                     */
/*                                                                          */
/*    Produit : Synthetiseur logique                                        */
/*    Fichier : arbres.c                                                    */
/*                                                                          */
/*    (c) copyright 1991 Laboratoire MASI equipe CAO & VLSI                 */
/*    Tous droits reserves                                                  */
/*    Support : e-mail cao-vlsi@masi.ibp.fr                                 */
/*                                                                          */
/*    Auteur(s) :   DICTUS N.                           le : 29/08/1991     */
/*                                                                          */
/*    Modifie par :                                     le : 16/01/1992     */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*                                                                          */
/****************************************************************************/

#include <stdio.h>
#include MUT_H
#include LOG_H
#include BEH_H
#include "../compil/lax_param.h"
#include "../synthe/sl_type.h"
#include "../menu/sl_corps.h"
#include "../compil/sl_util.h"
#include "types.h"
#include "oper.h"
#include "compile.h"
#include "util.h"
#include "mapper.h"
#include "regles.h"
#include "arbres.h"
#define REDUC 1
/* 0 : pas de reduc, 1 : reduction, 2 : reduction uniquement des inverseurs */

chain_list *genArbo(expr,signal,niv,init)
chain_list *expr;
sig *signal;
short niv,init;
{
chain_list *args,*auxExpr;
virtuelList *virt = NULL;
char *nameVirt = NULL;

   if (ATOM(expr)) return copyExpr(expr);
   createRef(niv);
   auxExpr = createExpr(OPER(expr));
   for(args = CDR(expr);args;args = CDR(args))
      addQExpr(auxExpr,genArbo(CAR(args),signal,niv+1,init));
   addArite(auxExpr);
   if (REDUC && init)
   {	
      nameVirt = cherchePorte(auxExpr,niv);
      if (nameVirt)
      {
	if (SL_TRACE)
           printf("genArbo : gate found = %s\n",nameVirt);

      	virt = (virtuelList *)testObj(nameVirt,'v');
	if (!virt) 
	   nameVirt = (char *)NULL;
      }
   }
   if (!nameVirt)
   {
      	virt = (virtuelList *)mbkalloc(sizeof(virtuelList));

	virt->capa = 0;
	virt->del_rc = -1;
	virt->fanout = (chain_list *)NULL;
	virt->op_log = NULL;
	virt->cellule = NULL;
	if ((niv != 1) || (signal && (signal->type == 3)))
	    nameVirt = gensym("auxsc",cptVirtuel++);
	else
	    nameVirt = signal->name;
	addTH(mappSys->virt_hash,nameVirt,(int)virt);
        virt->solutions = createATOM(auxExpr);
   }
   if (init)
   {
	virt->delais = delais(auxExpr);
	virt->surface_cone = surface_cone(virt);
   }
   else
   {
	virt->delais = -1;
	virt->surface_cone = -1;
   }
   addRef(nameVirt,niv);
   for(args = CDR(auxExpr);args;args = CDR(args))
   {
   virtuelList *filsVirt = (virtuelList *)testObj(VALUE_ATOM(CAR(args)),'v');

      if (filsVirt && (!memberChain_list((void *)nameVirt,filsVirt->fanout)))
	filsVirt->fanout = addchain(filsVirt->fanout,(void *)nameVirt);
   }
   return createATOM(nameVirt);
}

chain_list *remp(inst,abl,indSol)
char *inst;
chain_list *abl;
short indSol;
{
chain_list *a,*aux;

   if (ATOM(abl)) 
	{
	virtuelList *argVirt = (virtuelList *)testObj(VALUE_ATOM(abl),'v');
	sig *signal = (sig *)testObj(VALUE_ATOM(abl),'s');
	
	if ((signal && !SL_AUX && !inPtype_list(SL_DELAYPI,VALUE_ATOM(abl)) &&
            (signal->type == 2)) || (!signal && argVirt))
		return copyExpr(CAR(argVirt->solutions));

        return copyExpr(abl);
        }
   aux = copyExpr(abl);
   for(a = CDR(aux);a;a = CDR(a))
	{
	virtuelList *argVirt = (virtuelList *)testObj(VALUE_ATOM(CAR(a)),'v');
	sig *signal = (sig *)testObj(VALUE_ATOM(CAR(a)),'s');

	/* test expansion :
		c'est un signal que l'on peut expanser ou
		c'est un virtuel				*/

	if ((signal && !SL_AUX && (signal->type == 2)  &&
            !inPtype_list(SL_DELAYPI,VALUE_ATOM(CAR(a)))) ||
	    (argVirt && !signal))
	 {
	 chain_list *s;
	 short n;

	   for(s = argVirt->solutions,n = 1;s && n < indSol;s = CDR(s),n++) ;
	   if (s)
	      a->DATA = (void *)copyExpr(CAR(s));
	   else
	   {
	      freeExpr(aux);
	      return remp(inst,abl,--indSol);
	   }
	   if (inst)
	   {
	   virtuelList *virt = (virtuelList *)testObj(inst,'v');

	      if (!virt->op_log)
		 argVirt->fanout = delFanout(argVirt->fanout,inst);
	   }
         }
	}
   return aux;
}

chain_list *delFanout(fanout,nom)
chain_list *fanout;
char *nom;
{
chain_list *f,*sauv = fanout;

   while (f = sauv)
   {
	sauv = CDR(f);
	if ((char *)f->DATA == nom) fanout = delchain(fanout,f);
   }
   return fanout;
}

char *cherchePorte(abl,niv)
chain_list *abl;
int niv;
{
char *res = NULL;
ptype_list *m;
chain_list *i;

   if (profExpr(abl) == 1) res = (char *)testObj(exprToCharRed(abl),'a');
   if (res) return res;
/* modif 4/3/93 recherche jusqu'au niveau courant */
   for(m = mappSys->ref;m && (m->TYPE >= niv);m = CDR(m))
	for(i = CAR(m);i;i = CDR(i))
	{
	virtuelList *virt = (virtuelList *)testObj((char *)i->DATA,'v');

/* modif du 27/07/93 : normaliser la solution consultee */
	if (equalExpr(abl,CAR(virt->solutions)))
		return (char *)i->DATA;
	}
   return NULL;
}

void geleVirtuel(signal,abl)
sig *signal;
chain_list *abl;
{
ptype_list *r;
chain_list *n,*aux;

   freeExpr(CAR(abl));
   for(r = mappSys->ref;r;r = CDR(r))
      for(n = CAR(r);n;n = CDR(n))
      {
	virtuelList *virt = (virtuelList *)testObj((char *)n->DATA,'v');
	cellList *cellLog;

        if (!ATOM(CAR(virt->solutions)))
  	{
	   cellLog = operToCell(CAR(virt->solutions));
	   if (!cellLog)
	   {
	      fprintf(stderr,"cell doesn't exist %s%d\n",
			     searchCharOper(OPER(CAR(virt->solutions))),
			     ARITE(CAR(virt->solutions)));
	      exit(-1);
	   }
/* ne pas traiter les auxilliaires 4/3/93 */
	   if (!virt->op_log) 
	  {
      	   cellLog->util++;
	   virt->op_log = cellLog;
	   virt->cellule = virt->op_log->nom;

	/* on ne met que les auxilliaires et tous les sous cones */

if(REDUC == 1 || (REDUC == 2 && OPER(CAR(virt->solutions)) == NOT))
	   if ((r->TYPE > 1) || signal->type == 2)
	      addTH(mappSys->abl_hash,exprToCharRed(CAR(virt->solutions)),
		    (int)n->DATA);

	/* on ne garde que les differentes solutions des auxilliaires */

	   if ((r->TYPE > 1) || (signal->type == 3) || (signal->type == 4) ||
	       SL_AUX)
	   {
	 	aux = virt->solutions;
		while (aux = CDR(aux))
		   freeExpr(CAR(aux));
		freechain(CDR(virt->solutions));
		virt->solutions->NEXT = NULL;
	   }
	  }
	   /* mise a jour du champ util des signaux */
	   aux = CAR(virt->solutions);
	   while (aux = CDR(aux))
	   {
	   sig *sigAux = (sig *)testObj(VALUE_ATOM(CAR(aux)),'s');

	      if (sigAux && !memberChain_list(n->DATA,sigAux->util))
		 sigAux->util = addchain(sigAux->util,n->DATA);
           }
	}
   	else
	{
	   if (SL_TRACE) 
              printf("New Atom : %s\n",VALUE_ATOM(CAR(virt->solutions)));
	   abl->DATA = (void *)CAR(virt->solutions);
	}
	   if (r->TYPE == 1)
	   {
	      virt->fanout = addchain(virt->fanout,(void *)signal->name);
	      abl->DATA = (void *)createATOM((char *)n->DATA);
	   }
      }
   /* destruction de la reference */
   for(r = mappSys->ref;r;r = CDR(r))
   {
      freechain(CAR(r));
      r->DATA = NULL;
   }
   freeptype(mappSys->ref);
   mappSys->ref = NULL;
}

void genVar(inst,name,niv,init)
virtuelList *inst;
char *name;
short niv,init;
{
chain_list *abl = CAR(inst->solutions);
chain_list *auxExpr;
chain_list *args;
sig *signal = NULL;

   if (ATOM(abl))
   {
      signal = (sig *)testObj(VALUE_ATOM(abl),'s');

      if (signal)
      /* virtuel simplifie devenant un signal -> (not (not X)) */
      {

         for(args = inst->fanout;args;args = CDR(args))
         {
         virtuelList *virt = (virtuelList *)testObj((char *)args->DATA,'v');
      
            if (virt)
	       substPhyExpr(CAR(virt->solutions),name,abl);
         }
	 inst->delais = signal->delais;
	 inst->fanout = (chain_list *)NULL;
         return;
      }
      else
         auxExpr = remp((char *)NULL,abl,1);
   }
   else
   {
      auxExpr = createExpr(OPER(abl));
      for(args = CDR(abl);args;args = CDR(args))
   	   if (ATOM(CAR(args))) addQExpr(auxExpr,copyExpr(CAR(args)));
	   else
	   addQExpr(auxExpr,genArbo(CAR(args),signal,niv+1,init));
      addArite(auxExpr);
   }
   freeExpr(abl);
   inst->solutions->DATA = (void *)auxExpr;
   if (REDUC && init) 
   {
   char *nameAux = cherchePorte(auxExpr,niv+1);
   sig *sig1 = (sig *)testObj(name,'s');

      if (nameAux)
      {
      sig *sig2 = (sig *)testObj(nameAux,'s');

        if (SL_TRACE) 
               printf("genVar %s : gate found = %s\n",name,nameAux);

        if (sig1 && sig2 && sig1->type !=5)
        {
           if (sig2->type == 3 || sig2->type == 4)
           {
              freeExpr(CAR(inst->solutions));
              inst->solutions->DATA = (void *)createATOM(nameAux);
           }
        }
        else
        {
        virtuelList *virt = (virtuelList *)testObj(nameAux,'v'),*virtAux;

          if (!sig1)
          {
  	    chain_list *aux = createATOM(nameAux);

            if (virt)
            {
	      args = inst->fanout;
	      do
	      {
	         virtAux = (virtuelList *)testObj((char *)args->DATA,'v');
	         substPhyExpr(CAR(virtAux->solutions),name,aux);
	      }
	      while (args = CDR(args));
	      freeExpr(aux);
	      virt->fanout = appendChain_list(virt->fanout,inst->fanout);
	      inst->fanout = (chain_list *)NULL;
   	      addRef(nameAux,niv);
              name = nameAux;
	    }
          }
          else
/* modifie le 26/07/93 on reduit aussi les sorties */
          if (!sig2 || sig1->type==5)
          {
	    if (sig1->type == 5)
	    {
	     freeExpr(CAR(inst->solutions));
	     inst->solutions->DATA = createATOM(nameAux);
	     virt->fanout = addchain(virt->fanout,(void *)name);
	    }
	    else
            {
            chain_list *aux = createATOM(name);

              args = virt->fanout;
              while (args)
              {
               virtAux = (virtuelList *)testObj((char *)args->DATA,'v');
               if (virtAux)
                  substPhyExpr(CAR(virtAux->solutions),nameAux,aux);
               else
                  virt->fanout = delFanout(virt->fanout,(char *)args->DATA);
               args = CDR(args);
              }
              freeExpr(aux);
              inst->fanout = addchain(inst->fanout,args);
              virt->fanout = NULL;
            }

          }
        }
      }
   }
/* modifie le 8/07/93 : comme ds genArbo, on regarde init pour calculer le delai */
   if (init)
   {
        inst->delais = delais(CAR(inst->solutions));
        inst->surface_cone = surface_cone(inst);
   }
   else
   {
	inst->delais = -1;
	inst->surface_cone = -1;
   }
   /* mise a jour du fanout */
   for(args = CDR(auxExpr);args;args = args->NEXT)
   {
   virtuelList *filsVirt = (virtuelList *)testObj(VALUE_ATOM(CAR(args)),'v');

         if (filsVirt && (!memberChain_list((void *)name,filsVirt->fanout)))
	   filsVirt->fanout = addchain(filsVirt->fanout,(void *)name);
   }
}

void supp()
{
chain_list *virtUtil = (chain_list *)NULL,*virtNotUtil = (chain_list *)NULL,
	   *n,*f;
ptype_list *r;

   for(r = mappSys->ref; r; r = CDR(r))
      for(n = CAR(r);n;n = CDR(n))
      {
      virtuelList *virt = (virtuelList *)testObj((char *)n->DATA,'v');

        for(f = CDR(CAR(virt->solutions));f;f = CDR(f))
	   if (testObj(VALUE_ATOM(CAR(f)),'v'))
	      virtUtil = addchain(virtUtil,(void *)VALUE_ATOM(CAR(f)));

        if (r->TYPE == 1)
	{
	chain_list *aux = virt->solutions,*aux1;

	      while (aux = CDR(aux))
	      {
	        aux1 = expanse(CAR(aux));
	        freeExpr(CAR(aux));
	        aux->DATA = (void *)aux1;
	      }
           virtUtil = addchain(virtUtil,(void *)n->DATA);
	}
      }
   for(r = mappSys->ref; r; r = CDR(r))
      for(n = CAR(r);n;n = CDR(n))
	if (!memberChain_list(n->DATA,virtUtil))
		virtNotUtil = addchain(virtNotUtil,(void *)n->DATA);
   freechain(virtUtil);
   for(n = virtNotUtil;n;n = CDR(n))
	suppVirtuel((char *)n->DATA,virtNotUtil);
   freechain(virtNotUtil);
}

void suppVirtuel(nameInst,liste)
char *nameInst;
chain_list *liste;
{
virtuelList *virt =  (virtuelList *)testObj(nameInst,'v');
sig *signal = (sig *)testObj(nameInst,'s');
chain_list *c,*sauv;

 if (virt)
 {
   sauv = virt->fanout;
   while (c = sauv)
   {
	sauv = CDR(c);
	if (!signal || ((char *)c->DATA != nameInst))
	   if (memberChain_list(c->DATA,liste) && virt->fanout)
	      virt->fanout = delchain(virt->fanout,c);
   }
   if (!virt->fanout)
   {
   chain_list *args;
/*
   chain_list *newListe = addchain(liste,(void *)nameInst);
*/
   chain_list *newListe = createATOM(nameInst);

	for(args = CAR(virt->solutions);args;args = CDR(args))
	    {
	    char *nameArg = VALUE_ATOM(CAR(args));

	    if (testObj(nameArg,'v'))
		  suppVirtuel(nameArg,newListe);
	    }
	delchain(newListe,(void *)nameInst);
/*
   	freechain(newListe);
*/
	delVirt(nameInst);
    }
 }
}

void delVirt(name)
char *name;
{
virtuelList *virt = (virtuelList *)testObj(name,'v');
chain_list *s;

   if (mappSys->ref) delRef(name);
   deleteTH(mappSys->virt_hash,name);
   for (s = virt->solutions;s;s = CDR(s))
 	freeExpr(CAR(s)); 
   freechain(virt->solutions);
   virt->solutions = NULL;
   virt->op_log = NULL;
   virt->cellule = NULL;
   mbkfree(virt);
   if (SL_TRACE) 
      printf("...%s removed\n",name);
}
