distrib/sources/yagle/yagle/yag_duals.c

   1 /****************************************************************************/
   2 /*                                                                          */
   3 /*                      Chaine de CAO & VLSI   Alliance                     */
   4 /*                                                                          */
   5 /*    Produit : YAGLE  v3.50                                                */
   6 /*    Fichier : yag_duals.c                                                 */
   7 /*                                                                          */
   8 /*    (c) copyright 1994 Laboratoire MASI equipe CAO & VLSI                 */
   9 /*    Tous droits reserves                                                  */
  10 /*    Support : e-mail alliance-support@asim.lip6.fr                        */
  11 /*                                                                          */
  12 /*    Auteur(s) : Anthony LESTER                        le : 18/03/1994     */
  13 /*                                                                          */
  14 /*    Modifie par :                                     le : ../../....     */
  15 /*    Modifie par :                                     le : ../../....     */
  16 /*    Modifie par :                                     le : ../../....     */
  17 /*                                                                          */
  18 /****************************************************************************/
  19
  20 #include "yag_headers.h"
  21
  22 static chain_list *VISIT_LIST;
  23
  24 static int  UNRAVEL;
  25
  26 static branch_list *dual_branches __P((losig_list *ptsig, losig_list *ptlastsig, long *ptbranchtype));
  27 static chain_list *verif_dual __P((branch_group *ptbranches));
  28 static ht *order __P((branch_list *ptbranchlist, table *ptnames));
  29
  30 cone_list *yagMakeConeList(ifl, pt_mbkfig, pt_cnsfig)
  31     inffig_list *ifl;
  32     lofig_list  *pt_mbkfig;
  33     cnsfig_list *pt_cnsfig;
  34 {
  35     cone_list       *ptcone = NULL;
  36     cone_list       *tempcone = NULL;
  37     cone_list       *gluecone = NULL;
  38     losig_list      *ptsig = NULL;
  39     locon_list      *ptcon = NULL;
  40     chain_list      *ptchain = NULL;
  41     chain_list      *expr = NULL;
  42     chain_list      *ptchain1, *ptconlist;
  43     lotrs_list      *pttrans;
  44     ptype_list      *ptuser;
  45     branch_group    theBranches;
  46     int             numCon, numGates;
  47     int             isPartial;
  48     int             isTemp, isGlue;
  49     int             isDual;
  50     long            coneType;
  51     char            nodeType;
  52
  53 /* signal list traversal */
  54     for (ptsig = pt_mbkfig->LOSIG; ptsig != NULL; ptsig = ptsig->NEXT) {
  55         nodeType = 0;
  56         coneType = 0;
  57         theBranches.BRVDD = NULL;
  58         theBranches.BRVSS = NULL;
  59         theBranches.BRGND = NULL;
  60         theBranches.BREXT = NULL;
  61
  62         /* transparences */
  63         if (ptsig->TYPE == 'T') continue;
  64
  65         /* FCL_NEVER directive */
  66         if ((ptuser = getptype(ptsig->USER, FCL_TRANSFER_PTYPE)) != NULL) {
  67             if (((long)ptuser->DATA & FCL_NEVER) != 0) continue;
  68         }
  69
  70         /* check for gates and N-P intersection */
  71
  72         numCon = 0;
  73         numGates = 0;
  74         for (ptchain = (chain_list *)getptype(ptsig->USER, LOFIGCHAIN)->DATA;
  75                 ptchain != NULL;
  76                 ptchain = ptchain->NEXT) {
  77
  78             ptcon = ptchain->DATA;
  79             numCon++;
  80             if (ptcon->TYPE != 'T') continue;
  81             pttrans = (lotrs_list *)ptcon->ROOT;
  82
  83             /* check for NEVER directive on transistor */
  84             if ((ptuser = getptype(pttrans->USER, FCL_TRANSFER_PTYPE)) != NULL) {
  85                 if (((long)ptuser->DATA & FCL_NEVER) != 0) {
  86                     numCon--;
  87                     continue;
  88                 }
  89             }
  90
  91             /* Don't count if transistor is a capacitance */
  92             if (!(V_BOOL_TAB[__YAGLE_CAPACITANCE_CONES].VALUE)) {
  93                 if ((pttrans->TYPE & CAPACITE) == CAPACITE) {
  94                     numCon--;
  95                     continue;
  96                 }
  97             }
  98
  99             if (ptcon->NAME == CNS_GRIDNAME) numGates++;
 100
 101             if (ptcon->NAME != CNS_GRIDNAME && ptcon->NAME != CNS_BULKNAME) nodeType |= pttrans->TYPE;
 102         }
 103
 104         /* Handle Inputs from INF */
 105         if ((YAG_CONTEXT->YAG_FLAGS & YAG_HAS_INF_INPUTS)!=0 && ptsig->TYPE == CNS_SIGEXT) {
 106             ptconlist = yagGetExtLoconList(ptsig);
 107             for (ptchain1 = ptconlist; ptchain1; ptchain1 = ptchain1->NEXT) {
 108                 ptcon = (locon_list *)ptchain1->DATA;
 109                 if (getptype(ptcon->USER, YAG_INPUT_PTYPE) != NULL) {
 110                     nodeType = 0; /* Force input cone if gate present */
 111                 }
 112             }
 113             freechain(ptconlist);
 114         }
 115
 116         if ((ptsig->TYPE != CNS_SIGVDD) && (ptsig->TYPE != CNS_SIGVSS)) {
 117
 118             /* extract a CMOS DUAL cone */
 119             isDual = FALSE;
 120             isTemp = FALSE;
 121             isGlue = FALSE;
 122             if ((nodeType & (CNS_TN|CNS_TP)) == (CNS_TN|CNS_TP) && numCon > 2) {
 123                 isPartial = FALSE;
 124                 if ((expr = yagTryDual(ptsig, &theBranches, &isPartial)) != NULL) {
 125                     isDual = TRUE;
 126                     coneType |= YAG_HASDUAL;
 127                     if (isPartial) coneType |= YAG_PARTIAL;
 128                     if (ptsig->TYPE == CNS_SIGEXT) {
 129                         if (numGates == 0) {
 130                             ptcone = yagMakeOutCone(ptcone, ptsig, &theBranches, coneType, CNS_DUAL_CMOS);
 131                         }
 132                         else {
 133                             ptcone = yagMakeInoutCone(ptcone, ptsig, &theBranches, coneType, CNS_DUAL_CMOS);
 134                         }
 135                         ptcone->USER = addptype(ptcone->USER, CNS_UPEXPR, expr);
 136                         ptcone->USER = addptype(ptcone->USER, YAG_DUALEXPR_PTYPE, copyExpr(expr));
 137                     }
 138                     else {
 139                         if (numGates == 0) {
 140                         /* not a real cone */
 141                             if (getptype(ptsig->USER, FCL_FORCECONE_PTYPE) != NULL) {
 142                                 isGlue = TRUE;
 143                                 coneType |= YAG_GLUECONE;
 144                                 gluecone = yagMakeCone(gluecone, ptsig, NULL, coneType, 0);
 145                             }
 146                             else {
 147                                 isTemp = TRUE;
 148                                 coneType |= YAG_TEMPCONE;
 149                                 tempcone = yagMakeCone(tempcone, ptsig, &theBranches, coneType, CNS_DUAL_CMOS);
 150                             }
 151                             freeExpr(expr);
 152                         }
 153                         else {
 154                             ptcone = yagMakeCone(ptcone, ptsig, &theBranches, coneType, CNS_DUAL_CMOS);
 155                             ptcone->USER = addptype(ptcone->USER, CNS_UPEXPR, expr);
 156                             ptcone->USER = addptype(ptcone->USER, YAG_DUALEXPR_PTYPE, copyExpr(expr));
 157                         }
 158                     }
 159                     if (isGlue) yagMarkUsedTrans(gluecone);
 160                     else if (isTemp) yagMarkUsedTrans(tempcone);
 161                     else yagMarkUsedTrans(ptcone);
 162                     if (YAG_CONTEXT->YAG_ORIENT) yagOrientTransistors(ptsig);
 163                 }
 164                 else {
 165                     yagDelBranchList(theBranches.BRVDD);
 166                     yagDelBranchList(theBranches.BRVSS);
 167                 }
 168             }
 169
 170             /* add empty cones if no DUAL but signal attacks gate or connector or marked FORCECONE */
 171             if (isDual == FALSE) {
 172                 if (ptsig->TYPE == CNS_SIGEXT) {
 173                     /* add connector cones */
 174                     if (nodeType == 0 && numGates > 0) {
 175                         ptcone = yagMakeInCone(ptcone, ptsig, 0, 0);
 176                     }
 177                     else if (nodeType != 0 && numGates == 0) {
 178                         ptcone = yagMakeOutCone(ptcone, ptsig, NULL, YAG_PARTIAL, 0);
 179                     }
 180                     else if (nodeType != 0 && numGates > 0) {
 181                         ptcone = yagMakeInoutCone(ptcone, ptsig, NULL, YAG_PARTIAL, 0);
 182                     }
 183                 }
 184                 else if (numGates > 0) { /* normal empty cone */
 185                         ptcone = yagMakeCone(ptcone, ptsig, NULL, YAG_PARTIAL, 0);
 186                 }
 187                 else if (getptype(ptsig->USER, FCL_FORCECONE_PTYPE) != NULL) {
 188                     gluecone = yagMakeCone(gluecone, ptsig, NULL, YAG_PARTIAL|YAG_GLUECONE, 0);
 189                 }
 190             }
 191         }
 192         else if (numGates > 0) {
 193             /* power supply cones */
 194             ptcone = yagMakeSupplyCone(ptcone, ptsig);
 195         }
 196     }
 197
 198     if (tempcone != NULL) {
 199         pt_cnsfig->USER = addptype(pt_cnsfig->USER, YAG_TEMPCONE_PTYPE, tempcone);
 200     }
 201     if (gluecone != NULL) {
 202         pt_cnsfig->USER = addptype(pt_cnsfig->USER, YAG_GLUECONE_PTYPE, gluecone);
 203     }
 204     return ptcone;
 205 }
 206
 207 chain_list *yagTryDual(ptsig, ptbranches, ptpartial)
 208     losig_list      *ptsig;
 209     branch_group    *ptbranches;
 210     int             *ptpartial;
 211 {
 212     branch_list *newbranches;
 213     branch_list *ptbranch;
 214     chain_list  *ptchain;
 215     locon_list  *ptcon;
 216     lotrs_list  *pttrans;
 217     losig_list  *ptnextsig;
 218     long        branch_type;
 219
 220     VISIT_LIST = addchain(NULL, ptsig);
 221
 222     for (ptchain = (chain_list *)getptype(ptsig->USER, LOFIGCHAIN)->DATA; ptchain != NULL; ptchain = ptchain->NEXT) {
 223         ptcon = (locon_list *)ptchain->DATA;
 224         if (ptcon->TYPE == 'T') {
 225             pttrans = (lotrs_list *)ptcon->ROOT;
 226
 227             /* Skip parallel transistor instances */
 228             if (getptype(pttrans->USER, MBK_TRANS_MARK) != NULL) continue;
 229
 230             UNRAVEL = FALSE;
 231             if (ptcon == pttrans->SOURCE) {
 232                 ptnextsig = pttrans->DRAIN->SIG;
 233             }
 234             else if (ptcon == pttrans->DRAIN) {
 235                 ptnextsig = pttrans->SOURCE->SIG;
 236             }
 237             else if (ptcon == pttrans->GRID) continue;
 238             else if (ptcon == pttrans->BULK) continue;
 239
 240             if (ptnextsig == ptsig) continue;
 241
 242             branch_type = (pttrans->TYPE & CNS_TN) == CNS_TN ? CNS_VSS : CNS_VDD;
 243
 244             if (ptnextsig->TYPE == CNS_SIGVDD) {
 245                 newbranches = addbranch(NULL, CNS_VDD|YAG_DUALBRANCH, NULL);
 246                 branch_type |= CNS_VDD;
 247             }
 248             else if (ptnextsig->TYPE == CNS_SIGVSS) {
 249                 newbranches = addbranch(NULL, CNS_VSS|YAG_DUALBRANCH, NULL);
 250                 branch_type |= CNS_VSS;
 251             }
 252             else newbranches = dual_branches(ptnextsig, ptsig, &branch_type);
 253
 254             if (UNRAVEL) {
 255                 yagDelBranchList(newbranches);
 256                 *ptpartial = TRUE;
 257             }
 258             else {
 259                 if (branch_type == CNS_VDD) {
 260                     for (ptbranch = newbranches; ptbranch != NULL; ptbranch = ptbranch->NEXT) {
 261                         ptbranch->LINK = yagAddTransLink(ptbranch->LINK, pttrans, ptsig);
 262                     }
 263                     ptbranches->BRVDD = yagAppendBranch(ptbranches->BRVDD, newbranches);
 264                 }
 265                 else if (branch_type == CNS_VSS) {
 266                     for (ptbranch = newbranches; ptbranch != NULL; ptbranch = ptbranch->NEXT) {
 267                         ptbranch->LINK = yagAddTransLink(ptbranch->LINK, pttrans, ptsig);
 268                     }
 269                     ptbranches->BRVSS = yagAppendBranch(ptbranches->BRVSS, newbranches);
 270                 }
 271                 else {
 272                     yagDelBranchList(newbranches);
 273                     *ptpartial = TRUE;
 274                 }
 275             }
 276         }
 277     }
 278     freechain(VISIT_LIST);
 279     return verif_dual(ptbranches);
 280 }
 281
 282 static
 283 branch_list *dual_branches(ptsig, ptlastsig, ptbranchtype)
 284     losig_list  *ptsig;
 285     losig_list  *ptlastsig;
 286     long        *ptbranchtype;
 287 {
 288     branch_list *newbranches = NULL;
 289     branch_list *result_branch = NULL;
 290     branch_list *ptbranch;
 291     losig_list  *ptnextsig;
 292     chain_list  *ptchain, *headchain;
 293     locon_list  *ptcon;
 294     lotrs_list  *pttrans;
 295
 296     headchain = (chain_list *)getptype(ptsig->USER, LOFIGCHAIN)->DATA;
 297
 298     for (ptchain = headchain; ptchain != NULL; ptchain = ptchain->NEXT) {
 299         if (((locon_list *)ptchain->DATA)->NAME == CNS_GRIDNAME
 300         || ((locon_list *)ptchain->DATA)->NAME == CNS_BULKNAME) {
 301             UNRAVEL = TRUE;
 302             return NULL;
 303         }
 304     }
 305
 306     VISIT_LIST = addchain(VISIT_LIST, ptsig);
 307     for (ptchain = headchain; ptchain != NULL; ptchain = ptchain->NEXT) {
 308         ptcon = (locon_list *)ptchain->DATA;
 309
 310         if (ptcon->TYPE == 'T') {
 311             pttrans = (lotrs_list *)ptcon->ROOT;
 312
 313             /* Skip parallel transistor instances */
 314             if (getptype(pttrans->USER, MBK_TRANS_MARK) != NULL) continue;
 315
 316             if (ptcon == pttrans->SOURCE) {
 317                 ptnextsig = pttrans->DRAIN->SIG;
 318             }
 319             else if (ptcon == pttrans->DRAIN) {
 320                 ptnextsig = pttrans->SOURCE->SIG;
 321             }
 322             if (ptnextsig == ptlastsig) continue;
 323
 324             if (yagGetChain(VISIT_LIST, ptnextsig) != NULL) continue;
 325
 326             *ptbranchtype |= (pttrans->TYPE & CNS_TN) == CNS_TN ? CNS_VSS : CNS_VDD;
 327
 328             if (ptnextsig->TYPE == CNS_SIGVDD) {
 329                 newbranches = addbranch(NULL, CNS_VDD|YAG_DUALBRANCH, NULL);
 330                 *ptbranchtype |= CNS_VDD;
 331             }
 332             else if (ptnextsig->TYPE == CNS_SIGVSS) {
 333                 newbranches = addbranch(NULL, CNS_VSS|YAG_DUALBRANCH, NULL);
 334                 *ptbranchtype |= CNS_VSS;
 335             }
 336             else newbranches = dual_branches(ptnextsig, ptsig, ptbranchtype);
 337
 338             if (UNRAVEL) yagDelBranchList(newbranches);
 339             else {
 340                 if (*ptbranchtype == CNS_VSS || *ptbranchtype == CNS_VDD) {
 341                     for (ptbranch = newbranches; ptbranch != NULL; ptbranch = ptbranch->NEXT) {
 342                         ptbranch->LINK = yagAddTransLink(ptbranch->LINK, pttrans, ptsig);
 343                     }
 344                     result_branch = yagAppendBranch(result_branch, newbranches);
 345                 }
 346                 else {
 347                     yagDelBranchList(newbranches);
 348                     UNRAVEL = TRUE;
 349                 }
 350             }
 351         }
 352         else if (ptcon->TYPE == 'E' || ptcon->TYPE == 'I' || ptcon->TYPE == 'C') {
 353             UNRAVEL = TRUE;
 354         }
 355         else yagBug(DBG_ILL_CONTYPE,"dual_branches",NULL,NULL,0);
 356         if (UNRAVEL) {
 357             VISIT_LIST = delchain(VISIT_LIST, VISIT_LIST);
 358             return result_branch;
 359         }
 360     }
 361     VISIT_LIST = delchain(VISIT_LIST, VISIT_LIST);
 362     return result_branch;
 363 }
 364
 365 static
 366 chain_list *verif_dual(ptbranches)
 367     branch_group *ptbranches;
 368 {
 369     ht          *ptorder;
 370     table       *ptnames;
 371     branch_list *ptbranch;
 372     losig_list  *ptsig;
 373     link_list   *ptlink;
 374     pNode       sup = BDD_zero;
 375     pNode       sdown = BDD_zero;
 376     pNode       stot = BDD_zero;
 377     pNode       term, symbol;
 378     long        index;
 379     chain_list  *expr;
 380
 381     ptnames = newtable();
 382     ptorder = order(ptbranches->BRVSS, ptnames);
 383
 384 /* To calculate Sup */
 385
 386     for (ptbranch = ptbranches->BRVDD; ptbranch != NULL; ptbranch = ptbranch->NEXT) {
 387         term = BDD_one;
 388         for (ptlink = ptbranch->LINK; ptlink != NULL; ptlink = ptlink->NEXT) {
 389             ptsig = ((ptlink->ULINK).LOTRS)->GRID->SIG;
 390             if (ptsig->TYPE == CNS_SIGVDD) symbol = BDD_zero;
 391             else if (ptsig->TYPE == CNS_SIGVSS) symbol = BDD_one;
 392             else {
 393                 if ((index = gethtitem(ptorder, ptsig)) == EMPTYHT) {
 394                     delht(ptorder);
 395                     deltable(ptnames);
 396                     return FALSE;
 397                 }
 398                 symbol = notBdd(createNodeTermBdd(index));
 399             }
 400             term = applyBinBdd(AND, term, symbol);
 401         }
 402         if (term == BDD_zero) ptbranch->TYPE |= CNS_NOT_FUNCTIONAL;
 403         sup = applyBinBdd(OR, sup, term);
 404     }
 405
 406 /* To calculate Sdown */
 407
 408     for (ptbranch = ptbranches->BRVSS; ptbranch != NULL; ptbranch = ptbranch->NEXT) {
 409         term = BDD_one;
 410         for (ptlink = ptbranch->LINK; ptlink != NULL; ptlink = ptlink->NEXT) {
 411             ptsig = ((ptlink->ULINK).LOTRS)->GRID->SIG;
 412             if (ptsig->TYPE == CNS_SIGVDD) symbol = BDD_one;
 413             else if (ptsig->TYPE == CNS_SIGVSS) symbol = BDD_zero;
 414             else {
 415                 index = gethtitem(ptorder, ptsig);
 416                 symbol = createNodeTermBdd(index);
 417             }
 418             term = applyBinBdd(AND, term, symbol);
 419         }
 420         if (term == BDD_zero) ptbranch->TYPE |= CNS_NOT_FUNCTIONAL;
 421         sdown = applyBinBdd(OR, sdown, term);
 422     }
 423
 424     delht(ptorder);
 425     stot = applyBinBdd(AND, sup, sdown);
 426     if (stot == BDD_zero) {
 427         stot = applyBinBdd(OR, sup, sdown);
 428         if (stot == BDD_one) {
 429             expr = bddToAbl(sup, (char **)ptnames->DATA);
 430             deltable(ptnames);
 431             yagControlBdd(0);
 432             return expr;
 433         }
 434     }
 435     deltable(ptnames);
 436     yagControlBdd(0);
 437     return NULL;
 438 }
 439
 440 static
 441 ht *order(ptbranchlist, ptnames)
 442     branch_list *ptbranchlist;
 443     table       *ptnames;
 444 {
 445     ht          *ptorder;
 446     branch_list *ptbranch;
 447     link_list   *ptlink;
 448     losig_list  *ptsig;
 449     char        *name;
 450     long        index = 2;
 451
 452     ptorder = addht(20);
 453
 454     for (ptbranch = ptbranchlist; ptbranch != NULL; ptbranch = ptbranch->NEXT) {
 455         for (ptlink = ptbranch->LINK; ptlink != NULL; ptlink = ptlink->NEXT) {
 456             ptsig = ((ptlink->ULINK).LOTRS)->GRID->SIG;
 457             if (ptsig->TYPE == CNS_SIGVDD) continue;
 458             if (ptsig->TYPE == CNS_SIGVSS) continue;
 459             if (gethtitem(ptorder, ptsig) == EMPTYHT) {
 460                 addhtitem(ptorder, ptsig, index++);
 461                 switch(ptsig->TYPE) {
 462                     case CNS_SIGEXT: name = (yagGetExtLocon(ptsig))->NAME; break;
 463                     default: name = (char *)(ptsig->NAMECHAIN->DATA);
 464                 }
 465                 addtableitem(ptnames, name);
 466             }
 467         }
 468     }
 469     return ptorder;
 470 }