distrib/sources/yagle/yagle/yag_resolve.c

   1 /****************************************************************************/
   2 /*                                                                          */
   3 /*                      Chaine de CAO & VLSI   Alliance                     */
   4 /*                                                                          */
   5 /*    Produit : YAGLE  v3.0                                                 */
   6 /*    Fichier : yag_resolve.c                                               */
   7 /*                                                                          */
   8 /*    (c) copyright 1997 Laboratoire MASI equipe CAO & VLSI                 */
   9 /*    Tous droits reserves                                                  */
  10 /*    Support : e-mail cao-vlsi@masi.ibp.fr                                 */
  11 /*                                                                          */
  12 /*    Auteur(s) : Anthony LESTER                        le : 04/09/1997     */
  13 /*                                                                          */
  14 /*    Modifie par :                                     le : ../../....     */
  15 /*    Modifie par :                                     le : ../../....     */
  16 /*    Modifie par :                                     le : ../../....     */
  17 /*                                                                          */
  18 /****************************************************************************/
  19
  20 #include "yag_headers.h"
  21
  22 static pNode mintermResolveBdd __P((pNode bdd));
  23 static pNode mintermTraverse __P((pNode bdd, pNode resbdd));
  24 static pNode enumResolveBdd __P((pNode bdd, pNode resbdd));
  25 static pNode enumerateTraverse __P((chain_list *varlist, pNode enumbdd, pNode resbdd));
  26 static pNode electricResolve __P((pNode inbdd, pNode sumbdd));
  27 static int calcLevel __P((pNode inbdd));
  28
  29 //static pNode unexpand __P((pNode ptbdd, int curindex));
  30
  31 static pCircuit PRIMARY_CCT;
  32 static pCircuit DIRECT_CCT;
  33
  34 static cone_list *RESCONE;
  35
  36 static pNode CONFLICT;
  37 static int TEST;
  38
  39 /*************************************************************************
  40  *                    function yagResolveConflicts()                     *
  41  *************************************************************************/
  42
  43 /* takes a bdd of the conditions for electrical conflict  */
  44 /* for a cone and returns bdd representing the conditions */
  45 /* for which the conflict resolves to one                 */
  46
  47 pNode
  48 yagResolveConflicts(directCct, primaryCct, pConflictBdd, ptcone)
  49     pCircuit    directCct;
  50     pCircuit    primaryCct;
  51     pNode      *pConflictBdd;
  52     cone_list  *ptcone;
  53 {
  54     pNode       res;
  55
  56     TEST = 0;
  57     PRIMARY_CCT = primaryCct;
  58     DIRECT_CCT = directCct;
  59
  60     RESCONE = ptcone;
  61
  62     CONFLICT = BDD_zero;
  63
  64     res = mintermResolveBdd(*pConflictBdd);
  65
  66     *pConflictBdd = CONFLICT;
  67     return res;
  68 }
  69
  70 static chain_list *ABL;
  71
  72 /*************************************************************************
  73  *                    function mintermResolveBdd()                       *
  74  *************************************************************************/
  75
  76 /* minterm traversal of a given Bdd for conflict resolution */
  77
  78 static pNode
  79 mintermResolveBdd(bdd)
  80     pNode   bdd;
  81 {
  82     pNode   resbdd;
  83
  84     resbdd = BDD_zero;
  85     ABL = NULL;
  86     if (bdd == BDD_one) resbdd = enumResolveBdd(BDD_one, resbdd);
  87     else if (bdd != BDD_zero) {
  88         ABL = createExpr(AND);
  89         addQExpr(ABL, createAtom("'1'"));
  90         resbdd = mintermTraverse(bdd, resbdd);
  91         if (!ABL->NEXT) { freechain(ABL->DATA); freechain(ABL); }
  92         else { freeExpr(ABL); }
  93     }
  94     return resbdd;
  95 }
  96
  97 static pNode
  98 mintermTraverse(bdd, resbdd)
  99     pNode   bdd;
 100     pNode   resbdd;
 101 {
 102     chain_list *toDel;
 103
 104     if (bdd == BDD_one) resbdd = enumResolveBdd(ablToBddCct(DIRECT_CCT, ABL), resbdd);
 105     else if (bdd != BDD_zero) {
 106         addHExpr(ABL, notExpr(createAtom(searchIndexCct(DIRECT_CCT, bdd->index))));
 107         resbdd = mintermTraverse(bdd->low, resbdd);
 108         addHExpr(ABL, createAtom(searchIndexCct(DIRECT_CCT, bdd->index)));
 109         resbdd = mintermTraverse(bdd->high, resbdd);
 110     }
 111     toDel = ABL->NEXT;
 112     ABL->NEXT = ABL->NEXT->NEXT;
 113     toDel->NEXT = NULL;
 114     freeExpr(toDel->DATA);
 115     freechain(toDel);
 116
 117     return resbdd;
 118 }
 119
 120 /*************************************************************************
 121  *                    function enumResolveBdd()                          *
 122  *************************************************************************/
 123
 124 /* Dont Care enumeration of a given BDD for conflict resolution */
 125
 126 static pNode
 127 enumResolveBdd(bdd, resbdd)
 128     pNode   bdd;
 129     pNode   resbdd;
 130 {
 131     chain_list *support;
 132     chain_list *dontcare = NULL;
 133     ptype_list *ptroot;
 134     gnode_list *ptnode;
 135     short       index;
 136     char       *name;
 137
 138     support = supportChain_listBdd(bdd);
 139     for (ptroot = YAG_CONTEXT->YAG_CONE_GRAPH->ROOTNODES; ptroot; ptroot = ptroot->NEXT) {
 140         ptnode = (gnode_list *)ptroot->DATA;
 141         if ((ptnode->TYPE & CONE_TYPE) != 0) {
 142             name = ptnode->OBJECT.CONE->NAME;
 143         }
 144         else {
 145             /* node is an external connector */
 146             name = ptnode->OBJECT.LOCON->NAME;
 147         }
 148         index = searchInputCct_no_NA(DIRECT_CCT, name);
 149         if (index <= 1) continue;
 150         if (yagSearchBddList(support, index) == NULL) {
 151             dontcare = addchain(dontcare, createNodeTermBdd(index));
 152         }
 153     }
 154
 155     if (dontcare != NULL) {
 156         resbdd = enumerateTraverse(dontcare, bdd, resbdd);
 157         freechain(dontcare);
 158     }
 159     else {
 160         resbdd = electricResolve(bdd, resbdd);
 161     }
 162
 163     freechain(support);
 164     return resbdd;
 165 }
 166
 167 pNode
 168 yagSearchBddList(ptlist, index)
 169     chain_list *ptlist;
 170     short       index;
 171 {
 172     chain_list *ptchain;
 173     pNode       ptbdd;
 174
 175     for (ptchain = ptlist; ptchain; ptchain = ptchain->NEXT) {
 176         ptbdd = (pNode)ptchain->DATA;
 177         if (ptbdd->index == index) break;
 178     }
 179     if (ptchain != NULL) return ptbdd;
 180     else return NULL;
 181 }
 182
 183 static pNode
 184 enumerateTraverse(varlist, enumbdd, resbdd)
 185     chain_list *varlist;
 186     pNode       enumbdd;
 187     pNode       resbdd;
 188 {
 189     pNode       nextenum;
 190
 191     nextenum = applyBinBdd(AND, enumbdd, notBdd((pNode)varlist->DATA));
 192
 193     if (varlist->NEXT != NULL) {
 194         resbdd = enumerateTraverse(varlist->NEXT, nextenum, resbdd);
 195     }
 196     else {
 197         resbdd = electricResolve(nextenum, resbdd);
 198     }
 199
 200     nextenum = applyBinBdd(AND, enumbdd, (pNode)varlist->DATA);
 201
 202     if (varlist->NEXT != NULL) {
 203         resbdd = enumerateTraverse(varlist->NEXT, nextenum, resbdd);
 204     }
 205     else {
 206         resbdd = electricResolve(nextenum, resbdd);
 207     }
 208
 209     return resbdd;
 210 }
 211
 212 static pNode
 213 electricResolve(inbdd, sumbdd)
 214     pNode   inbdd;
 215     pNode   sumbdd;
 216 {
 217     chain_list *inabl;
 218     pNode       primbdd;
 219
 220     /* check that condition is functionally possible */
 221     inabl = bddToAblCct(DIRECT_CCT, inbdd);
 222     primbdd = ablToBddCct(PRIMARY_CCT, inabl);
 223     /* apply the contraints */
 224     primbdd = yagApplyConstraints(primbdd, NULL);
 225     freeExpr(inabl);
 226     if (primbdd != BDD_zero) {
 227         if (calcLevel(inbdd) == TRUE) {
 228             return applyBinBdd(OR, inbdd, sumbdd);
 229         }
 230         else return sumbdd;
 231     }
 232     else return sumbdd;
 233 }
 234
 235 static int
 236 calcLevel(inbdd)
 237     pNode   inbdd;
 238 {
 239     branch_list    *ptbranch;
 240     chain_list     *abl;
 241     chain_list     *upList = NULL;
 242     chain_list     *downList = NULL;
 243     abl_pair        extabl;
 244     pNode           branchbdd;
 245     pNode           extupbdd, extdnbdd;
 246     float           upresistance;
 247     float           downresistance;
 248     int             stmresult = FALSE;
 249
 250     for (ptbranch = RESCONE->BRVDD; ptbranch; ptbranch = ptbranch->NEXT) {
 251         if ((ptbranch->TYPE & (CNS_NOT_FUNCTIONAL|CNS_IGNORE)) != 0) continue;
 252         abl = cnsMakeBranchExpr(ptbranch, 0, FALSE);
 253         branchbdd = ablToBddCct(DIRECT_CCT, abl);
 254         if (applyBinBdd(AND, branchbdd, inbdd) != BDD_zero) {
 255             upList = addchain(upList, ptbranch);
 256         }
 257         freeExpr(abl);
 258     }
 259
 260     for (ptbranch = RESCONE->BRVSS; ptbranch; ptbranch = ptbranch->NEXT) {
 261         if ((ptbranch->TYPE & (CNS_NOT_FUNCTIONAL|CNS_IGNORE)) != 0) continue;
 262         abl = cnsMakeBranchExpr(ptbranch, 0, FALSE);
 263         branchbdd = ablToBddCct(DIRECT_CCT, abl);
 264         if (applyBinBdd(AND, branchbdd, inbdd) != BDD_zero) {
 265             downList = addchain(downList, ptbranch);
 266         }
 267         freeExpr(abl);
 268     }
 269
 270     for (ptbranch = RESCONE->BREXT; ptbranch; ptbranch = ptbranch->NEXT) {
 271         if ((ptbranch->TYPE & (CNS_NOT_FUNCTIONAL|CNS_IGNORE)) != 0) continue;
 272         cnsMakeExtBranchExpr(ptbranch, &extabl, 0, FALSE);
 273         extupbdd = ablToBddCct(DIRECT_CCT, extabl.UP);
 274         extdnbdd = ablToBddCct(DIRECT_CCT, extabl.DN);
 275         if (applyBinBdd(AND, extupbdd, inbdd) != BDD_zero) {
 276             upList = addchain(upList, ptbranch);
 277         }
 278         else if (applyBinBdd(AND, extdnbdd, inbdd) != BDD_zero) {
 279             downList = addchain(downList, ptbranch);
 280         }
 281         freeExpr(extabl.UP);
 282         freeExpr(extabl.DN);
 283     }
 284
 285 #ifndef WITHOUT_TAS
 286     if (YAG_CONTEXT->YAG_USESTMSOLVER) {
 287         stmresult = yagCalcStmResPair(upList, downList, RESCONE, &upresistance, &downresistance);
 288     }
 289 #endif
 290
 291     if (!stmresult) {
 292         upresistance = yagCalcParallelResistance(upList);
 293         downresistance = yagCalcParallelResistance(downList);
 294     }
 295     freechain(upList);
 296     freechain(downList);
 297
 298     if ( avt_islog(3,LOGYAG) || YAG_CONTEXT->YAG_DEBUG_CONE == YAG_CONTEXT->YAG_CURCIRCUIT->name) {
 299         avt_log(LOGYAG,1,"Input '");
 300         abl = bddToAblCct(DIRECT_CCT, inbdd);
 301         displayInfExprLog(LOGYAG, 1, abl);
 302         freeExpr(abl);
 303         avt_log(LOGYAG,1,"' resolves to %.2f", downresistance/(downresistance+upresistance));
 304     }
 305     if (downresistance >= YAG_CONTEXT->YAG_THRESHOLD*upresistance) {
 306         if ( avt_islog(3,LOGYAG) || YAG_CONTEXT->YAG_DEBUG_CONE == YAG_CONTEXT->YAG_CURCIRCUIT->name) {
 307             avt_log(LOGYAG,1, " (\"1\")\n");
 308         }
 309         return TRUE;
 310     }
 311     if (upresistance >= YAG_CONTEXT->YAG_THRESHOLD*downresistance) {
 312         if ( avt_islog(3,LOGYAG) || YAG_CONTEXT->YAG_DEBUG_CONE == YAG_CONTEXT->YAG_CURCIRCUIT->name) {
 313             avt_log(LOGYAG,1, " (\"0\")\n");
 314         }
 315         return FALSE;
 316     }
 317     CONFLICT = applyBinBdd(OR, CONFLICT, inbdd);
 318     if ( avt_islog(3,LOGYAG) || YAG_CONTEXT->YAG_DEBUG_CONE == YAG_CONTEXT->YAG_CURCIRCUIT->name) {
 319         avt_log(LOGYAG,1, "\n");
 320     }
 321     if (downresistance > upresistance) return TRUE;
 322     else return FALSE;
 323 }