distrib/sources/yagle/fcl/fcl_phase2.c

   1 /****************************************************************************/
   2 /*                                                                          */
   3 /*                      Chaine de CAO & VLSI   Alliance                     */
   4 /*                                                                          */
   5 /*    Produit : FCL  v1.02                                                  */
   6 /*    Fichier : fcl_phase2.c                                                */
   7 /*                                                                          */
   8 /*    (c) copyright 1996 Laboratoire MASI equipe CAO & VLSI                 */
   9 /*    Tous droits reserves                                                  */
  10 /*    Support : e-mail alliance-support@asim.lip6.fr                        */
  11 /*                                                                          */
  12 /*                                                                          */
  13 /****************************************************************************/
  14
  15 #include "fcl_headers.h"
  16
  17 /*
  18    ####====================================================================####
  19    ##                                                                        ##
  20    ##                         EN TETE DES FONCTIONS                          ##
  21    ##                                                                        ##
  22    ####====================================================================####
  23  */
  24 static void            init_phase2();       /* init                           */
  25 static void            clean_phase2();      /* netoie                           */
  26 static int             parcours_sig();      /* parcours les S connectes a un T  */
  27 static int             parcours_trs_ins();  /* parcours les T connectes a un S  */
  28 static int             test_non_match();    /* cherche les branches perdues     */
  29 static void            clear();             /* supprime les match de la phase 2 */
  30 //static int             rebouclage();        /* supprime les solutions bouclees  */
  31 static int             check_couplings();   /* remove broken couplings          */
  32 static num_list       *get_numlist_intersect();
  33 /*
  34    ####====================================================================####
  35    ##                                                                        ##
  36    ##                             VARIABLES GLOBALES                         ##
  37    ##                                                                        ##
  38    ####====================================================================####
  39  */
  40
  41 matrice_list   *ptmatrice = (matrice_list *) NULL; /* matrice des solutions   */
  42
  43 int             niveau_last = 0;        /* numero de la derniere colonne dans */
  44                                         /* la matrice                         */
  45
  46 cell_list      *FCL_CELL_LIST = NULL;
  47 chain_list     *FCL_INSTANCE_LIST = NULL;
  48 locon_list     *FCL_LOCON_LIST = NULL;
  49
  50 int             FCL_BUILD_CELLS = FALSE;
  51 int             FCL_BUILD_INSTANCES = FALSE;
  52 int             FCL_BUILD_CORRESP = FALSE;
  53
  54 int             FCL_NEED_ZERO = FALSE;
  55 int             FCL_NEED_ONE = FALSE;
  56
  57 /*
  58    ####====================================================================####
  59    ##                                                                        ##
  60    ##                               phase2()                                 ##
  61    ##                                                                        ##
  62    ## Tante de faire un parcours identique dans le model et dans le circuit  ##
  63    ##                                                                        ##
  64    ####====================================================================####
  65    ##  entree : pointeur sur la lofig du circuit                             ##
  66    ##         : pointeur sur la lofig du model                               ##
  67    ##         : pointeur sur la liste des vecteurs candidats                 ##
  68    ##         : pointeur sur le vecteur cle du model                         ##
  69    ##  sortie :                                                              ##
  70    ####====================================================================####
  71  */
  72
  73 void
  74 fclPhase2(ptlofig_c, ptlofig_m, ptbefig_m, ptsolution, ptcle, findall)
  75     lofig_list     *ptlofig_c;
  76     lofig_list     *ptlofig_m;
  77     befig_list     *ptbefig_m;
  78     partition_list *ptsolution;
  79     void           *ptcle;
  80     int             findall;
  81 {
  82     chain_list     *ptchain;        /* parcours de tous les vecteurs camdidats  */
  83     lotrs_list     *ptlotrs;        /* vecteur cle type                         */
  84     losig_list     *ptlosig;        /* vecteur cle type                         */
  85     loins_list     *ptloins;        /* vecteur cle type                         */
  86     matrice_list   *ptm;
  87     int             instance = 1;
  88
  89
  90     /* Effectue les netoyages pour la phase 1 et intialise les labels */
  91     init_phase2(ptlofig_c);
  92     init_phase2(ptlofig_m);
  93
  94     if (findall) {
  95         /* le vecteur cle est marque MATCH avec le niveau 0 */
  96         niveau_last = 0;
  97         if (ptsolution->TYPE == TYPE_T) {
  98             ptlotrs = (lotrs_list *) ptcle;
  99             ptlotrs->USER = addptype(ptlotrs->USER, FCL_MATCH_PTYPE, (void *)(long) niveau_last);
 100         }
 101         else if (ptsolution->TYPE == TYPE_S) {
 102             ptlosig = (losig_list *) (ptcle);
 103             ptlosig->USER = addptype(ptlosig->USER, FCL_MATCH_PTYPE, (void *)(long) niveau_last);
 104         }
 105         else if (ptsolution->TYPE == TYPE_I) {
 106             ptloins = (loins_list *) (ptcle);
 107             ptloins->USER = addptype(ptloins->USER, FCL_MATCH_PTYPE, (void *)(long) niveau_last);
 108         }
 109
 110         /* la matrice est preparee */
 111         ptmatrice = tab_init();
 112         (ptmatrice->tab)[0] = ptcle;
 113         (ptmatrice->NEXT->tab)[0] = (void *) (long)ptsolution->TYPE;
 114
 115         ptm = ptmatrice;
 116         for (ptchain = ptsolution->DATA; ptchain; ptchain = ptchain->NEXT) {
 117             ptm->NEXT = (matrice_list *) mbkalloc(sizeof(matrice_list));
 118             ptm = ptm->NEXT;
 119             ptm->tab = mbkalloc(BUFFER * sizeof(void *)) ;
 120             (ptm->tab)[0] = ptchain->DATA;
 121         }
 122
 123         /* le parcours peut commencer */
 124         if (ptsolution->TYPE == TYPE_T) {
 125             if (parcours_sig((locon_list *) NULL, TYPE_T, (int) - 1) && test_non_match(ptlofig_m)) {
 126                 fclTestSolutions(ptmatrice, ptlofig_c, ptlofig_m, ptbefig_m, &instance);
 127             }
 128             else if (FCL_TRACE_LEVEL > 1) printf("NOT\n");
 129         }
 130         else if (ptsolution->TYPE == TYPE_S) {
 131             if (parcours_trs_ins((locon_list *) NULL) && test_non_match(ptlofig_m)) {
 132                 fclTestSolutions(ptmatrice, ptlofig_c, ptlofig_m, ptbefig_m, &instance);
 133             }
 134             else if (FCL_TRACE_LEVEL > 1) printf("NOT\n");
 135         }
 136         else if (ptsolution->TYPE == TYPE_I) {
 137             if (parcours_sig((locon_list *) NULL, TYPE_I, (int) - 1) && test_non_match(ptlofig_m)) {
 138                 fclTestSolutions(ptmatrice, ptlofig_c, ptlofig_m, ptbefig_m, &instance);
 139             }
 140             else if (FCL_TRACE_LEVEL > 1) printf("NOT\n");
 141         }
 142         tab_free(ptmatrice);
 143         clear(ptlofig_m);
 144     }
 145     else {
 146         for (ptchain = ptsolution->DATA; ptchain; ptchain = ptchain->NEXT) {
 147             /* le vecteur cle est marque MATCH avec le niveau 0 */
 148             niveau_last = 0;
 149             if (ptsolution->TYPE == TYPE_T) {
 150                 ptlotrs = (lotrs_list *) ptcle;
 151                 ptlotrs->USER = addptype(ptlotrs->USER, FCL_MATCH_PTYPE, (void *)(long) niveau_last);
 152             }
 153             else if (ptsolution->TYPE == TYPE_S) {
 154                 ptlosig = (losig_list *) (ptcle);
 155                 ptlosig->USER = addptype(ptlosig->USER, FCL_MATCH_PTYPE, (void *)(long) niveau_last);
 156             }
 157             else if (ptsolution->TYPE == TYPE_I) {
 158                 ptloins = (loins_list *) (ptcle);
 159                 ptloins->USER = addptype(ptloins->USER, FCL_MATCH_PTYPE, (void *)(long) niveau_last);
 160             }
 161
 162             /* la matrice est preparee */
 163             ptmatrice = tab_init();
 164             (ptmatrice->tab)[0] = ptcle;
 165             (ptmatrice->NEXT->tab)[0] = (void *) (long)ptsolution->TYPE;
 166             (ptmatrice->NEXT->NEXT->tab)[0] = ptchain->DATA;
 167
 168             /* le parcours peut commencer */
 169             if (ptsolution->TYPE == TYPE_T) {
 170                 if (parcours_sig((locon_list *) NULL, TYPE_T, (int) - 1) && test_non_match(ptlofig_m)) {
 171                     fclTestSolutions(ptmatrice, ptlofig_c, ptlofig_m, ptbefig_m, &instance);
 172                 }
 173                 else if (FCL_TRACE_LEVEL > 1) printf("NOT\n");
 174             }
 175             else if (ptsolution->TYPE == TYPE_S) {
 176                 if (parcours_trs_ins((locon_list *) NULL) && test_non_match(ptlofig_m)) {
 177                     fclTestSolutions(ptmatrice, ptlofig_c, ptlofig_m, ptbefig_m, &instance);
 178                 }
 179                 else if (FCL_TRACE_LEVEL > 1) printf("NOT\n");
 180             }
 181             else if (ptsolution->TYPE == TYPE_I) {
 182                 if (parcours_sig((locon_list *) NULL, TYPE_I, (int) - 1) && test_non_match(ptlofig_m)) {
 183                     fclTestSolutions(ptmatrice, ptlofig_c, ptlofig_m, ptbefig_m, &instance);
 184                 }
 185                 else if (FCL_TRACE_LEVEL > 1) printf("NOT\n");
 186             }
 187             tab_free(ptmatrice);
 188             clear(ptlofig_m);
 189         }
 190     }
 191     if (FCL_FILE && instance > 1) {
 192         if (FCL_CELL_LIST != NULL) {
 193             fprintf(FCL_OUTPUT, "Instances of '%s' = %d (Model = %ld)\n\n", ptlofig_m->NAME, instance - 1, FCL_CELL_LIST->TYPE & ~CNS_UNKNOWN);
 194         }
 195         else {
 196             fprintf(FCL_OUTPUT, "Instances of '%s' = %d\n\n", ptlofig_m->NAME, instance - 1);
 197         }
 198     }
 199     clean_phase2(ptlofig_c);
 200     clean_phase2(ptlofig_m);
 201 }
 202
 203
 204 /*
 205    ####====================================================================####
 206    ##                                                                        ##
 207    ##                             PARCOURS_SIG                               ##
 208    ##                                                                        ##
 209    ## Parcours les signaux connectes a un transistor ou instance donne       ##
 210    ####====================================================================####
 211    ## A partir d'un transistor d'un sous-graphe, parcours l'ensemble des     ##
 212    ## signaux qui y sont conectes. Ce parcours doit etre identique dans      ##
 213    ## le circuit. Si on cherche a passer par un signal qui a deja ete        ##
 214    ## parcouru, ce rebouclage doit egalement exister dans le circuit         ##
 215    ## Plusieurs Solutions peuvent exister dans le circuit. Elles sont alors  ##
 216    ## memoriser dans une matrice.                                            ##
 217    ##                                                                        ##
 218    ####====================================================================####
 219  */
 220 static int
 221 parcours_sig(ptlocon, sourcetype, precniveau)
 222     locon_list     *ptlocon;        /* Ptr sur LOCON par lequel on arrive   */
 223     char            sourcetype;
 224     int             precniveau;
 225 {
 226     fcl_label       prevcon;        /* label du connecteur precedent        */
 227     ptype_list     *ptuser;        /* pointeur sur le ptype MATCH du TRS   */
 228     lotrs_list     *ptlotrs = NULL;        /* TRS du parcours precedent            */
 229     loins_list     *ptloins = NULL;        /* INS du parcours precedent            */
 230     int             niveau = niveau_last;        /* niveau du transistor      */
 231     int             niveau_donesourcedrain = -1;
 232     losig_list     *ptlosig;        /* ptr sur signal a parcourir           */
 233     matrice_list   *ptm;        /* pointeur sur une solution            */
 234     locon_list     *ptnextlocon;
 235     int             loop;
 236
 237     if (FCL_TRACE_LEVEL > 5) {
 238         int             i;
 239
 240         printf("parcours sig\n");
 241         displaymatrice(ptmatrice,niveau_last, FALSE);
 242         for (i = 0, ptm = ptmatrice; ptm; i++, ptm = ptm->NEXT);
 243         printf("n=%d     nb=%d\n", niveau_last, i);
 244     }
 245
 246     prevcon = getlabellocon(ptlocon);
 247
 248     /* On verifie si le vecteur cle courrant n'est pas deja MATCH */
 249     /* a un niveau inferieur, si c'est le cas les vecteurs des    */
 250     /* solutions doivent etre MATCH egalement et sur le meme      */
 251     /* niveau                                                     */
 252
 253     if (sourcetype == TYPE_T) {
 254         ptlotrs = (lotrs_list *) ((ptmatrice->tab)[niveau]);
 255     }
 256     else if (sourcetype == TYPE_I) {
 257         ptloins = (loins_list *) ((ptmatrice->tab)[niveau]);
 258     }
 259
 260     /* Il faut tester les rebouclages du graphe             */
 261     /* seules les solutions sans rebouclage doivent exister */
 262 /*    if (!rebouclage()) {
 263         if (FCL_TRACE_LEVEL > 5) {
 264             printf("phase 2 match failed: no loop to transistor in model but all solutions have loop\n");
 265         }
 266         return 0;
 267     }*/
 268
 269     if (sourcetype == TYPE_T) {
 270         /* *************************** */
 271         /* Pour le signal sur le DRAIN */
 272         /* *************************** */
 273         ptlosig = ptlotrs->DRAIN->SIG;
 274         if (ptlotrs->DRAIN != ptlocon) {
 275             niveau_last++;
 276
 277             /* Le signal est marque MATCH, s'il ne l'est pas deja */
 278             if ((ptuser = getptype(ptlosig->USER, FCL_MATCH_PTYPE)) == NULL) {
 279                 ptlosig->USER = addptype(ptlosig->USER, FCL_MATCH_PTYPE, (void *)(long)niveau_last);
 280                 loop = -1;
 281             }
 282             else loop = (int)(long)ptuser->DATA;
 283
 284             /* Le signal est ajoute sur le premier tableau */
 285             tab_ajoute(ptmatrice, niveau_last, (void *)ptlosig);
 286             tab_ajoute(ptmatrice->NEXT, niveau_last, (void *)(long)TYPE_S);
 287
 288             /* On cherche les signaux identiques dans le graphe */
 289             if (!fclFindCorrespondingLosig(ptmatrice, niveau, POID_DRAIN, prevcon, precniveau, loop, -1)) return 0;
 290             /* on part sur le signal trouve */
 291             niveau_donesourcedrain = niveau_last;
 292             if (loop >= 0) niveau_last--;
 293             else if (!parcours_trs_ins(ptlotrs->DRAIN)) return 0;
 294         }
 295
 296         /* **************************** */
 297         /* Pour le signal sur le SOURCE */
 298         /* **************************** */
 299         ptlosig = ptlotrs->SOURCE->SIG;
 300         if (ptlotrs->SOURCE != ptlocon) {
 301             niveau_last++;
 302
 303             /* Le signal est marque MATCH, s'il ne l'est pas deja */
 304             if ((ptuser = getptype(ptlosig->USER, FCL_MATCH_PTYPE)) == NULL) {
 305                 ptlosig->USER = addptype(ptlosig->USER, FCL_MATCH_PTYPE, (void *)(long)niveau_last);
 306                 loop = -1;
 307             }
 308             else loop = (int)(long)ptuser->DATA;
 309
 310             /* Le signal est ajoute sur le premier tableau */
 311             tab_ajoute(ptmatrice, niveau_last, (void *)ptlosig);
 312             tab_ajoute(ptmatrice->NEXT, niveau_last, (void *)(long)TYPE_S);
 313
 314             /* On cherche les signaux identiques */
 315             if (!fclFindCorrespondingLosig(ptmatrice, niveau, POID_SOURCE, prevcon, precniveau, loop, niveau_donesourcedrain)) return 0;
 316             /* on part sur le signal trouve */
 317             if (loop >= 0) niveau_last--;
 318             else if (!parcours_trs_ins(ptlotrs->SOURCE)) return 0;
 319         }
 320
 321         /* ************************** */
 322         /* Pour le signal sur le GRID */
 323         /* ************************** */
 324         ptlosig = ptlotrs->GRID->SIG;
 325         if (ptlotrs->GRID != ptlocon) {
 326             niveau_last++;
 327
 328             /* Le signal est marque MATCH, s'il ne l'est pas deja */
 329             if ((ptuser = getptype(ptlosig->USER, FCL_MATCH_PTYPE)) == NULL) {
 330                 ptlosig->USER = addptype(ptlosig->USER, FCL_MATCH_PTYPE, (void *)(long)niveau_last);
 331                 loop = -1;
 332             }
 333             else loop = (int)(long)ptuser->DATA;
 334
 335             /* Le signal est ajoute sur le premier tableau */
 336             tab_ajoute(ptmatrice, niveau_last, (void *)ptlosig);
 337             tab_ajoute(ptmatrice->NEXT, niveau_last, (void *)(long) TYPE_S);
 338
 339             /* On cherche les signaux identiques */
 340             if (!fclFindCorrespondingLosig(ptmatrice, niveau, POID_GRID, prevcon, precniveau, loop, -1)) return 0;
 341             /* on part sur le signal trouve */
 342             if (loop >= 0) niveau_last--;
 343             else if (!parcours_trs_ins(ptlotrs->GRID)) return 0;
 344         }
 345
 346         /* ************************** */
 347         /* Pour le signal sur le BULK */
 348         /* ************************** */
 349         if (ptlotrs->BULK) ptlosig = ptlotrs->BULK->SIG;
 350         if (ptlotrs->BULK != ptlocon && ptlotrs->BULK && ptlosig && SPI_IGNORE_BULK == 'N') {
 351             niveau_last++;
 352
 353             /* Le signal est marque MATCH, s'il ne l'est pas deja */
 354             if ((ptuser = getptype(ptlosig->USER, FCL_MATCH_PTYPE)) == NULL) {
 355                 ptlosig->USER = addptype(ptlosig->USER, FCL_MATCH_PTYPE, (void *)(long)niveau_last);
 356                 loop = -1;
 357             }
 358             else loop = (int)(long)ptuser->DATA;
 359
 360             /* Le signal est ajoute sur le premier tableau */
 361             tab_ajoute(ptmatrice, niveau_last, (void *) ptlosig);
 362             tab_ajoute(ptmatrice->NEXT, niveau_last, (void *)(long)TYPE_S);
 363
 364             /* On cherche les signaux identiques */
 365             if (!fclFindCorrespondingLosig(ptmatrice, niveau, POID_BULK, prevcon, precniveau, loop, -1)) return 0;
 366             /* on part sur le signal trouve */
 367             if (loop >= 0) niveau_last--;
 368             else if (!parcours_trs_ins(ptlotrs->BULK)) return 0;
 369         }
 370     }
 371     else if (sourcetype == TYPE_I) {
 372         for (ptnextlocon = ptloins->LOCON; ptnextlocon; ptnextlocon = ptnextlocon->NEXT) {
 373             if (ptnextlocon != ptlocon) {
 374                 ptlosig = ptnextlocon->SIG;
 375                 niveau_last++;
 376
 377                 /* Le signal est marque MATCH, s'il ne l'est pas deja */
 378                 if ((ptuser = getptype(ptlosig->USER, FCL_MATCH_PTYPE)) == NULL) {
 379                     ptlosig->USER = addptype(ptlosig->USER, FCL_MATCH_PTYPE, (void *)(long)niveau_last);
 380                     loop = -1;
 381                 }
 382                 else loop = (int)(long)ptuser->DATA;
 383
 384                 /* Le signal est ajoute sur le premier tableau */
 385                 tab_ajoute(ptmatrice, niveau_last, (void *) ptlosig);
 386                 tab_ajoute(ptmatrice->NEXT, niveau_last, (void *)(long)TYPE_S);
 387
 388                 /* On cherche les signaux identiques */
 389                 if (!fclFindCorrespondingLosig(ptmatrice, niveau, getlabellocon(ptnextlocon), prevcon, precniveau, loop, -1)) return 0;
 390                 /* on part sur le signal trouve */
 391                 if (loop >= 0) niveau_last--;
 392                 else if (!parcours_trs_ins(ptnextlocon)) return 0;
 393             }
 394         }
 395     }
 396
 397     return 1;
 398 }
 399
 400 /*
 401    ####====================================================================####
 402    ##                                                                        ##
 403    ##                             PARCOURS_TRS_INS                           ##
 404    ##                                                                        ##
 405    ## Parcours les transistors ou instances connectes a un signal donne      ##
 406    ####====================================================================####
 407    ## A partir d'un signal d'un sous-graphe, parcours l'ensemble des         ##
 408    ## transistors qui y sont conectes. Ce parcours doit etre identique dans  ##
 409    ## le circuit. Si on cherche a passer par un transistor qui a deja ete    ##
 410    ## parcouru, ce rebouclage doit egalement exister dans le circuit         ##
 411    ## Plusieurs Solutions peuvent exister dans le circuit. Elles sont alors  ##
 412    ## memoriser dans une matrice.                                            ##
 413    ##                                                                        ##
 414    ####====================================================================####
 415  */
 416 static int
 417 parcours_trs_ins(ptlocon)
 418     locon_list     *ptlocon;
 419 {
 420     fcl_label       label;        /* label du connecteur             */
 421     chain_list     *ptfils;        /* Liste des fils du Vect courrant */
 422     chain_list     *ptfils_courrant;        /* Pointeur sur le fils courrant   */
 423     ptype_list     *ptuser;        /* ptype MATCH du vecteur courrant */
 424     losig_list     *ptlosig;        /* ptr sur signal precedent        */
 425     lotrs_list     *ptlotrs;        /* ptr sur trs a parcourir         */
 426     loins_list     *ptloins;        /* ptr sur instance a parcourir         */
 427     int             niveau = niveau_last;        /* niveau courrant               */
 428     matrice_list   *ptm;        /* pointeur sur une solution     */
 429     locon_list     *ptnextlocon;
 430     int             loop;
 431
 432     if (FCL_TRACE_LEVEL > 5) {
 433         int             i;
 434
 435         printf("parcours trs\n");
 436         displaymatrice(ptmatrice,niveau_last, FALSE);
 437         for (i = 0, ptm = ptmatrice; ptm; i++, ptm = ptm->NEXT);
 438         printf("n=%d     nb=%d\n", niveau_last, i);
 439     }
 440
 441     ptlosig = (losig_list *) ((ptmatrice->tab)[niveau]);
 442
 443     /* si le signal cle correspond a une alim il faut que le */
 444     /* signal de la solution correspond a la meme alim       */
 445
 446     if (ptlosig->TYPE == CNS_SIGVDD || ptlosig->TYPE == CNS_SIGVSS) {
 447         for (ptm = ptmatrice->NEXT->NEXT; ptm; ptm = ptm->NEXT) {
 448             if (((losig_list *) ((ptm->tab)[niveau]))->TYPE != ptlosig->TYPE) {
 449                 /* La solution courrante n'est pas bonne */
 450                 ptm = tab_del(ptmatrice, ptm);
 451             }
 452         }
 453         if (ptmatrice->NEXT->NEXT == NULL) {
 454             if (FCL_TRACE_LEVEL > 5) {
 455                 printf("phase 2 match failed: power supply in model has no correspondance\n");
 456             }
 457             return 0;
 458         }
 459         else return 1;
 460     }
 461
 462     /* Test that instance connector couplings have not been broken */
 463     if (!check_couplings()) return 0;
 464
 465     /* On ne parcours que les signaux INTERNES */
 466     if (ptlosig->TYPE != INTERNAL) return 1;
 467
 468     /* Il faut tester les rebouclages du graphe */
 469 /*    if (!rebouclage()) {
 470         if (FCL_TRACE_LEVEL > 5) {
 471             printf("phase 2 match failed: no loop to signal in model but all solutions have loop\n");
 472         }
 473         return 0;
 474     }*/
 475
 476     /* On construit la liste des successeurs du vecteur du */
 477     /* sous-graphe courrant. Cette liste contient en       */
 478     /* premier les vecteurs deja MATCH (s'ils existent)    */
 479
 480     ptfils = fils_sig(ptlosig, ptlocon);
 481
 482     /* On parcourt la liste en essayant de faire un parcourt */
 483     /* identique dans le circuit                             */
 484     for (ptfils_courrant = ptfils; ptfils_courrant; ptfils_courrant = ptfils_courrant->NEXT) {
 485         niveau_last++;
 486         ptnextlocon = (locon_list *)ptfils_courrant->DATA;
 487
 488         if (ptnextlocon->TYPE == 'T') {
 489             ptlotrs = (lotrs_list *)ptnextlocon->ROOT;
 490
 491             /* Le transistor est marque MATCH, s'il ne l'est pas deja */
 492             if ((ptuser = getptype(ptlotrs->USER, FCL_MATCH_PTYPE)) == NULL) {
 493                 ptlotrs->USER = addptype(ptlotrs->USER, FCL_MATCH_PTYPE, (void *)(long)niveau_last);
 494                 loop = -1;
 495             }
 496             else loop = (int)(long)ptuser->DATA;
 497
 498             /* Le trs est ajoute sur le premier tableau */
 499             tab_ajoute(ptmatrice, niveau_last, (void *)ptlotrs);
 500             tab_ajoute(ptmatrice->NEXT, niveau_last, (void *)(long)TYPE_T);
 501
 502             label = getlabellocon(ptnextlocon);
 503
 504             /* On cherche les transistors identiques */
 505             if (!fclFindCorrespondingLotrs(ptmatrice, niveau, label, loop)) {
 506                 freechain(ptfils);
 507                 return 0;
 508             }
 509             if (loop >= 0) niveau_last--;
 510             else if (!parcours_sig(ptnextlocon, TYPE_T, niveau)) {
 511                 freechain(ptfils);
 512                 return 0;
 513             }
 514         }
 515         else if (ptnextlocon->TYPE == 'I') {
 516             ptloins = (loins_list *)ptnextlocon->ROOT;
 517
 518             /* Instance est marque MATCH, s'il ne l'est pas deja */
 519             if ((ptuser = getptype(ptloins->USER, FCL_MATCH_PTYPE)) == NULL) {
 520                 ptloins->USER = addptype(ptloins->USER, FCL_MATCH_PTYPE, (void *)(long)niveau_last);
 521                 loop = -1;
 522             }
 523             else loop = (int)(long)ptuser->DATA;
 524
 525             /* Instance est ajoute sur le premier tableau */
 526             tab_ajoute(ptmatrice, niveau_last, (void *)ptloins);
 527             tab_ajoute(ptmatrice->NEXT, niveau_last, (void *)(long)TYPE_I);
 528
 529             label = getlabellocon(ptnextlocon);
 530
 531             /* On cherche les instances identiques */
 532             if (!fclFindCorrespondingLoins(ptmatrice, niveau, label, loop)) {
 533                 freechain(ptfils);
 534                 return 0;
 535             }
 536             if (loop >= 0) niveau_last--;
 537             else if (!parcours_sig(ptnextlocon, TYPE_I, niveau)) {
 538                 freechain(ptfils);
 539                 return 0;
 540             }
 541         }
 542     }
 543
 544     freechain(ptfils);
 545     return 1;
 546 }
 547
 548 /*
 549    ####====================================================================####
 550    ##                                                                        ##
 551    ##                            clear()                                     ##
 552    ##                                                                        ##
 553    ## Supprime les ptypes MATCH du sous-graphe apres une premiere recherche  ##
 554    ####====================================================================####
 555    ##  entree : pointeur sur la LOFIG                                        ##
 556    ##  sortie : rien                                                         ##
 557    ####====================================================================####
 558  */
 559 static void
 560 clear(ptlofig)
 561     lofig_list     *ptlofig;
 562 {
 563     losig_list     *ptlosig;
 564     lotrs_list     *ptlotrs;
 565     loins_list     *ptloins;
 566     ptype_list     *ptype;
 567
 568     /*  scan signal list  */
 569     for (ptlosig = ptlofig->LOSIG; ptlosig; ptlosig = ptlosig->NEXT) {
 570         ptype = getptype(ptlosig->USER, FCL_MATCH_PTYPE);
 571         if (ptype != NULL) ptlosig->USER = delptype(ptlosig->USER, FCL_MATCH_PTYPE);
 572     }
 573
 574     /*  scan lotrs list  */
 575     for (ptlotrs = ptlofig->LOTRS; ptlotrs; ptlotrs = ptlotrs->NEXT) {
 576         ptype = getptype(ptlotrs->USER, FCL_MATCH_PTYPE);
 577         if (ptype != NULL) ptlotrs->USER = delptype(ptlotrs->USER, FCL_MATCH_PTYPE);
 578     }
 579
 580     /*  scan loins list  */
 581     for (ptloins = ptlofig->LOINS; ptloins; ptloins = ptloins->NEXT) {
 582         ptype = getptype(ptloins->USER, FCL_MATCH_PTYPE);
 583         if (ptype != NULL) ptloins->USER = delptype(ptloins->USER, FCL_MATCH_PTYPE);
 584     }
 585 }
 586
 587
 588 /*
 589    ####====================================================================####
 590    ##                                                                        ##
 591    ##                            init_phase2()                               ##
 592    ##                                                                        ##
 593    ## Supprime tous les ptypes du traitement de la phase 1                   ##
 594    ## et initialise les labels                                               ##
 595    ####====================================================================####
 596    ##  entree : pointeur sur la LOFIG                                        ##
 597    ##  sortie : rien                                                         ##
 598    ####====================================================================####
 599  */
 600 static void
 601 init_phase2(ptlofig)
 602     lofig_list     *ptlofig;
 603 {
 604     losig_list     *ptlosig = (losig_list *) NULL;
 605     ptype_list     *ptype;
 606     int             i;
 607
 608     /*  scan signal list  */
 609     for (ptlosig = ptlofig->LOSIG; ptlosig; ptlosig = ptlosig->NEXT) {
 610
 611         /* for each signal count the number of connection */
 612         ptype = getptype(ptlosig->USER, LOFIGCHAIN);
 613         i = CountChain((chain_list *)ptype->DATA);
 614
 615         /* compensate for external connector */
 616         if (ptlosig->TYPE != 'I') i--;
 617
 618         /* and save this value */
 619         ptype = getptype(ptlosig->USER, FCL_LABEL_PTYPE);
 620         if (ptype == NULL) {
 621             ptlosig->USER = addptype(ptlosig->USER, FCL_LABEL_PTYPE, (void *)(long)i);
 622         }
 623         else {
 624             ptype->DATA = (void *)(long)i;
 625         }
 626     }
 627 }
 628
 629 static void
 630 clean_phase2(ptlofig)
 631     lofig_list     *ptlofig;
 632 {
 633     losig_list     *ptlosig = (losig_list *) NULL;
 634     ptype_list     *ptype;
 635
 636     /*  scan signal list  */
 637     for (ptlosig = ptlofig->LOSIG; ptlosig; ptlosig = ptlosig->NEXT) {
 638         ptype = getptype(ptlosig->USER, FCL_LABEL_PTYPE);
 639         if (ptype != NULL) {
 640             ptlosig->USER = delptype(ptlosig->USER, FCL_LABEL_PTYPE);
 641         }
 642     }
 643 }
 644
 645 /*
 646    ####====================================================================####
 647    ##                                                                        ##
 648    ##                            rebouclage()                                ##
 649    ##                                                                        ##
 650    ## Test si un rebouclage existe dans chaques solutions,                   ##
 651    ## si c'est le cas ces solutions sont supprimees                          ##
 652    ####====================================================================####
 653    ##  entree :                                                              ##
 654    ##  sortie : une valeur d'etat                                            ##
 655    ####====================================================================####
 656  */
 657 /*
 658 static int
 659 rebouclage()
 660 {
 661     void           *pt_element;
 662     matrice_list   *ptm;
 663     int             niveau;
 664
 665     for (ptm = ptmatrice->NEXT->NEXT; ptm; ptm = ptm->NEXT) {
 666         pt_element = ((ptm->tab)[niveau_last]);
 667
 668         for (niveau = niveau_last - 1; niveau >= 0; niveau--) {
 669             if (((ptm->tab)[niveau]) == pt_element) {
 670                 ptm = tab_del(ptmatrice, ptm);
 671                 break;
 672             }
 673         }
 674     }
 675
 676     if (ptmatrice->NEXT->NEXT == NULL) return 0;
 677
 678     return 1;
 679 }
 680 */
 681 /*
 682    ####====================================================================####
 683    ##                                                                        ##
 684    ##                            check_couplings()                           ##
 685    ##                                                                        ##
 686    ## Remove solutions violating instance connector couplings                ##
 687    ####====================================================================####
 688  */
 689 static int
 690 check_couplings()
 691 {
 692     matrice_list   *ptm;
 693     losig_list     *ptnewmodelsig;
 694     losig_list     *ptmodelsig;
 695     losig_list     *ptlosig;
 696     num_list       *ptcouplinglist;
 697     num_list       *ptlevellist, *ptlevel;
 698     num_list       *ptnum, *ptnumintersection;
 699     chain_list     *ptnumlistchain;
 700     ptype_list     *ptuser;
 701     long            coupling_index;
 702     long            level;
 703
 704     if ((ptmatrice->NEXT->tab)[niveau_last] != (void *)(long)TYPE_S) return 1;
 705     ptnewmodelsig = (losig_list *)(ptmatrice->tab)[niveau_last];
 706     if ((ptuser = getptype(ptnewmodelsig->USER, FCL_COUP_LIST_PTYPE)) == NULL) return 1;
 707     ptcouplinglist = (num_list *)ptuser->DATA;
 708     /* For each coupling index on the most recent signal */
 709     for (ptnum = ptcouplinglist; ptnum; ptnum = ptnum->NEXT) {
 710         coupling_index = ptnum->DATA;
 711         ptlevellist = addnum(NULL, (long)niveau_last);
 712         /* obtain list of levels of signals with identical coupling index */
 713         for (level = 0; level < niveau_last; level++) {
 714             if ((ptmatrice->NEXT->tab)[level] != (void *)(long)TYPE_S) continue;
 715             ptmodelsig = (losig_list *)(ptmatrice->tab)[level];
 716             if ((ptuser = getptype(ptmodelsig->USER, FCL_COUP_LIST_PTYPE)) == NULL) continue;
 717             if (getnum((num_list *)ptuser->DATA, coupling_index) != NULL) {
 718                 ptlevellist = addnum(ptlevellist, level);
 719             }
 720         }
 721         if (ptlevellist->NEXT != NULL) { /* signal(s) with matching index exist */
 722             for (ptm = ptmatrice->NEXT->NEXT; ptm; ptm = ptm->NEXT) {
 723                 ptnumlistchain = NULL;
 724                 /* obtain list of coupling index lists for each of the identified levels */
 725                 for (ptlevel = ptlevellist; ptlevel; ptlevel = ptlevel->NEXT) {
 726                     ptlosig = (losig_list *)(ptm->tab)[ptlevel->DATA];
 727                     if ((ptuser = getptype(ptlosig->USER, FCL_COUP_LIST_PTYPE)) == NULL) {
 728                         ptm = tab_del(ptmatrice, ptm);
 729                         break;
 730                     }
 731                     ptnumlistchain = addchain(ptnumlistchain, ptuser->DATA);
 732                 }
 733                 if (ptlevel != NULL) {
 734                     freechain(ptnumlistchain);
 735                     continue;
 736                 }
 737                 /* bad solution if the coupling list intersection is empty */
 738                 if ((ptnumintersection = get_numlist_intersect(ptnumlistchain)) == NULL) {
 739                     ptm = tab_del(ptmatrice, ptm);
 740                 }
 741                 freenum(ptnumintersection);
 742             }
 743         }
 744         freenum(ptlevellist);
 745     }
 746
 747     if (ptmatrice->NEXT->NEXT == NULL) return 0;
 748
 749     return 1;
 750 }
 751
 752 static num_list *
 753 get_numlist_intersect(ptnumlistchain)
 754     chain_list *ptnumlistchain;
 755 {
 756     num_list   *ptfirstnumlist;
 757     num_list   *ptcurnumlist;
 758     num_list   *ptnum;
 759     num_list   *ptnumintersection = NULL;
 760     chain_list *ptchain;
 761     long        curindex;
 762     int         intersect;
 763
 764     if (ptnumlistchain->NEXT == NULL) return NULL;
 765     ptfirstnumlist = (num_list *)ptnumlistchain->DATA;
 766     for (ptnum = ptfirstnumlist; ptnum; ptnum = ptnum->NEXT) {
 767         curindex = ptnum->DATA;
 768         intersect = TRUE;
 769         for (ptchain = ptnumlistchain->NEXT; ptchain; ptchain = ptchain->NEXT) {
 770             ptcurnumlist = (num_list *)ptchain->DATA;
 771             if (getnum(ptcurnumlist, curindex) == NULL) {
 772                 intersect = FALSE;
 773                 break;
 774             }
 775         }
 776         if (intersect) ptnumintersection = addnum(ptnumintersection, curindex);
 777     }
 778     return ptnumintersection;
 779 }
 780
 781 /*
 782    ####====================================================================####
 783    ##                                                                        ##
 784    ##                        test_non_match                                  ##
 785    ##                                                                        ##
 786    ##  Parcours les branches non parcourues                                  ##
 787    ####====================================================================####
 788    ## Cherche si des transistors n'ont pas ete parcourus, s'il en existe     ##
 789    ## ces branches sont connectees au signaux externes. Il faut donc a partir##
 790    ## du transistor non MATCH chercher un signal externe, puis continuer     ##
 791    ## le parcours dans les deux graphes a partir de ce signal                ##
 792    ##                                                                        ##
 793    ####====================================================================####
 794  */
 795 static int
 796 test_non_match(ptlofig_m)
 797     lofig_list     *ptlofig_m;
 798 {
 799     lotrs_list     *ptlotrs;
 800     loins_list     *ptloins;
 801     losig_list     *ptlosig;
 802     locon_list     *ptnextlocon;
 803     ptype_list     *ptype;
 804     fcl_label       label;
 805     int             all_matched;
 806     int             matching;
 807     int             i;
 808
 809     do {
 810         all_matched = TRUE;
 811         matching = FALSE;
 812         /* parcours tous les transistors du sous-graphe */
 813         for (ptlotrs = ptlofig_m->LOTRS; ptlotrs; ptlotrs = ptlotrs->NEXT) {
 814             if ((ptype = getptype(ptlotrs->USER, FCL_MATCH_PTYPE)) == NULL) {
 815                 /* Une branche non parcourue existe */
 816                 all_matched = FALSE;
 817
 818                 /* On cherche un signal externe deja MATCH */
 819                 if ((ptlosig = ptlotrs->DRAIN->SIG)->TYPE == EXTERNAL &&
 820                     (ptype = getptype(ptlosig->USER, FCL_MATCH_PTYPE)) != NULL) {
 821
 822                     niveau_last++;
 823                     matching = TRUE;
 824
 825                     /* Le transistor est marque MATCH */
 826                     ptlotrs->USER = addptype(ptlotrs->USER, FCL_MATCH_PTYPE, (void *)(long) niveau_last);
 827
 828                     /* Le trs est ajoute sur le premier tableau */
 829                     tab_ajoute(ptmatrice, niveau_last, ptlotrs);
 830                     tab_ajoute(ptmatrice->NEXT, niveau_last, (void *)(long)TYPE_T);
 831
 832                     label = getlabelsigtrs(ptlotrs, ptlosig);
 833
 834                     for (i = 0; i <= niveau_last; i++) {
 835                         if ((ptmatrice->tab)[i] == ptlosig) break;
 836                     }
 837
 838                     /* On cherche les transistors identiques */
 839                     if (!fclFindCorrespondingLotrs(ptmatrice, i, label, -1)) return 0;
 840                     if (!parcours_sig(ptlotrs->DRAIN, TYPE_T, (int)(long)ptype->DATA)) return 0;
 841                     break;
 842                 }
 843
 844                 if ((ptlosig = ptlotrs->SOURCE->SIG)->TYPE == EXTERNAL &&
 845                     (ptype = getptype(ptlosig->USER, FCL_MATCH_PTYPE)) != NULL) {
 846
 847                     niveau_last++;
 848                     matching = TRUE;
 849
 850                     /* Le transistor est marque MATCH */
 851                     ptlotrs->USER = addptype(ptlotrs->USER, FCL_MATCH_PTYPE, (void *)(long) niveau_last);
 852
 853                     /* Le trs est ajoute sur le premier tableau */
 854                     tab_ajoute(ptmatrice, niveau_last, ptlotrs);
 855                     tab_ajoute(ptmatrice->NEXT, niveau_last, (void *)(long) TYPE_T);
 856
 857                     label = getlabelsigtrs(ptlotrs, ptlosig);
 858
 859
 860                     for (i = 0; i <= niveau_last; i++) {
 861                         if ((ptmatrice->tab)[i] == ptlosig) break;
 862                     }
 863
 864                     /* On cherche les transistors identiques */
 865                     if (!fclFindCorrespondingLotrs(ptmatrice, i, label, -1)) return 0;
 866                     if (!parcours_sig(ptlotrs->SOURCE, TYPE_T, (int)(long) ptype->DATA)) return 0;
 867                     break;
 868                 }
 869
 870                 if ((ptlosig = ptlotrs->GRID->SIG)->TYPE == EXTERNAL &&
 871                     (ptype = getptype(ptlosig->USER, FCL_MATCH_PTYPE)) != NULL) {
 872
 873                     niveau_last++;
 874                     matching = TRUE;
 875
 876                     /* Le transistor est marque MATCH */
 877                     ptlotrs->USER = addptype(ptlotrs->USER, FCL_MATCH_PTYPE, (void *)(long) niveau_last);
 878
 879                     /* Le trs est ajoute sur le premier tableau */
 880                     tab_ajoute(ptmatrice, niveau_last, ptlotrs);
 881                     tab_ajoute(ptmatrice->NEXT, niveau_last, (void *)(long) TYPE_T);
 882
 883                     label = getlabelsigtrs(ptlotrs, ptlosig);
 884
 885                     for (i = 0; i <= niveau_last; i++) {
 886                         if ((ptmatrice->tab)[i] == (void *) ptlosig) break;
 887                     }
 888
 889                     /* On cherche les transistors identiques */
 890                     if (!fclFindCorrespondingLotrs(ptmatrice, i, label, -1)) return 0;
 891                     if (!parcours_sig(ptlotrs->GRID, TYPE_T, (int)(long) ptype->DATA)) return 0;
 892                     break;
 893                 }
 894             }
 895         }
 896         /* parcours tous les instances du sous-graphe */
 897         for (ptloins = ptlofig_m->LOINS; ptloins; ptloins = ptloins->NEXT) {
 898             if ((ptype = getptype(ptloins->USER, FCL_MATCH_PTYPE)) == NULL) {
 899                 /* Une branche non parcourue existe */
 900                 all_matched = FALSE;
 901
 902                 /* On cherche un signal externe deja MATCH */
 903                 for (ptnextlocon = ptloins->LOCON; ptnextlocon; ptnextlocon = ptnextlocon->NEXT) {
 904                     if ((ptlosig = ptnextlocon->SIG)->TYPE == EXTERNAL &&
 905                         (ptype = getptype(ptlosig->USER, FCL_MATCH_PTYPE)) != NULL) {
 906
 907                         niveau_last++;
 908                         matching = TRUE;
 909
 910                         /* Instance est marque MATCH */
 911                         ptloins->USER = addptype(ptloins->USER, FCL_MATCH_PTYPE, (void *)(long)niveau_last);
 912
 913                         /* Instance est ajoute sur le premier tableau */
 914                         tab_ajoute(ptmatrice, niveau_last, ptloins);
 915                         tab_ajoute(ptmatrice->NEXT, niveau_last, (void *)(long)TYPE_I);
 916
 917                         label = getlabellocon(ptnextlocon);
 918
 919                         for (i = 0; i <= niveau_last; i++) {
 920                             if ((ptmatrice->tab)[i] == ptlosig) break;
 921                         }
 922
 923                         /* On cherche les instances identiques */
 924                         if (!fclFindCorrespondingLoins(ptmatrice, i, label, -1)) return 0;
 925                         if (!parcours_sig(ptnextlocon, TYPE_I, (int)(long)ptype->DATA)) return 0;
 926                         break;
 927                     }
 928                 }
 929             }
 930         }
 931         /* nothing possible */
 932         if (all_matched == FALSE && matching == FALSE && niveau_last > 2) {
 933            fprintf(stderr, "[FCL WAR] model '%s' is disjoint - there are unmatched transistors\n", ptlofig_m->NAME);
 934            break;
 935         }
 936     } while (all_matched == FALSE && matching == TRUE);
 937
 938     return 1;
 939 }
 940