distrib/sources/yagle/yagle/yag_graph.c

   1 /****************************************************************************/
   2 /*                                                                          */
   3 /*                      Chaine de CAO & VLSI   Alliance                     */
   4 /*                                                                          */
   5 /*    Produit : YAGLE  v3.50                                                */
   6 /*    Fichier : yag_graph.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 : 20/06/1994     */
  13 /*                                                                          */
  14 /*    Modifie par :                                     le : ../../....     */
  15 /*    Modifie par :                                     le : ../../....     */
  16 /*    Modifie par :                                     le : ../../....     */
  17 /*                                                                          */
  18 /****************************************************************************/
  19
  20 #include "yag_headers.h"
  21
  22 #define GR_NOERR 0
  23 #define GR_LOOP 1
  24 #define GR_HOLE 2
  25 #define GR_STOP 4
  26
  27 #define GR_PRIMVAR 0
  28 #define GR_NOPRIMVAR 1
  29
  30 #define GRAPH_PACKET 4
  31 #define NODE_PACKET 20
  32
  33 static graph        *EMPTY_GRAPH = NULL;
  34 static graph        *ALLOC_GRAPH = NULL;
  35
  36 static gnode_list   *EMPTY_NODE = NULL;
  37
  38 static graph    *CUR_GRAPH;
  39 static short    CUR_TREE;
  40 static cone_list *CUR_ROOT;
  41
  42 static chain_list   *VAR_LIST;
  43
  44 static int      local;
  45 //static int      incomplete;
  46 static int      numholes;
  47
  48 static int      total_son_arcs;
  49 static int      visited_son_arcs;
  50
  51 static int      add_constraints;
  52
  53 #define convergence(node) (node->NUMSONS >= 2 || (node->NUMSONS == 1 && node->DEPTH == 0))
  54 #define mark_treebit(node) (node->TREEBIT |= (1 << CUR_TREE))
  55 #define unmark_treebit(node) (node->TREEBIT ^= (1 << CUR_TREE))
  56 #define in_other_tree(node) (((node->TREEBIT & ~(1 << CUR_TREE)) != 0) ? TRUE : FALSE)
  57 #define check_complete(ptgraph) (ptgraph->ROOTNODES == NULL ? TRUE : (ptgraph->ROOTNODES->TYPE & HOLENODE) == 0)
  58
  59 static gnode_list *build(edge_list *ptedge, int depth, int *ptrescode, int invonly, int force);
  60 static void update_depth(gnode_list *ptnode, int depth);
  61 static void check_memsym_constraint(cone_list *ptcone, graph *ptgraph);
  62 static gnode_list *add_node(void *object, long type, short deep);
  63 static void extra_constraints(gnode_list *ptnode, graph *ptgraph);
  64 static void number_sons(gnode_list *ptnode);
  65 static void traverse(gnode_list *ptnode);
  66 static void unmark(gnode_list *ptnode);
  67 static void count_sons(gnode_list *ptnode);
  68 static void pick_prims(gnode_list *ptnode);
  69 static chain_list *add_primvar(chain_list *list, gnode_list *ptnode);
  70 static void reduce(graph *ptgraph, gnode_list *ptnode);
  71 static void prop_search(gnode_list *ptnode);
  72
  73 /****************************************************************************
  74  *                         function yagBuildGraph();                        *
  75  ****************************************************************************/
  76
  77 graph *
  78 yagBuildGraph(edge_list *ptedgelist, cone_list *rootcone, int force)
  79 {
  80     edge_list   *ptedge;
  81     gnode_list  *ptnode;
  82     locon_list  *ptcon;
  83     cone_list   *ptcone;
  84     int         rescode;
  85     int         stopcone;
  86     int         save_hasdual;
  87
  88     if ((rootcone && rootcone->TYPE & YAG_HASDUAL) != 0) save_hasdual = TRUE;
  89     else save_hasdual = FALSE;
  90     if (rootcone) rootcone->TYPE &= ~YAG_HASDUAL;
  91
  92     CUR_GRAPH = yagNewGraph();
  93     CUR_ROOT = rootcone;
  94
  95     local = FALSE;
  96     if (rootcone && (rootcone->TYPE & YAG_STOP) == YAG_STOP) stopcone = TRUE;
  97     else stopcone = FALSE;
  98
  99     /* create root nodes separately in order to */
 100     /* detect reconvergence onto a root         */
 101
 102     for (ptedge = ptedgelist; ptedge != NULL; ptedge = ptedge->NEXT) {
 103         if ((ptedge->TYPE & CNS_BLEEDER) == CNS_BLEEDER) continue;
 104         CUR_TREE = CUR_GRAPH->WIDTH;
 105         if ((ptedge->TYPE & CNS_EXT) == CNS_EXT) {
 106             ptcon = ptedge->UEDGE.LOCON;
 107             ptnode = add_node(ptcon, ROOT_NODE|EXT, 0);
 108             if (getptype(ptcon->USER, YAG_CONSTRAINT_PTYPE) != NULL) {
 109                 ptnode->TYPE |= CONSTRAINT_NODE;
 110             }
 111         }
 112         else {
 113             ptcone = ptedge->UEDGE.CONE;
 114             ptnode = add_node(ptcone, ROOT_NODE|CONE_TYPE, 0);
 115             if ((ptcone->TYPE & YAG_CONSTRAINT) == YAG_CONSTRAINT) {
 116                 ptnode->TYPE |= CONSTRAINT_NODE;
 117             }
 118             if ((ptcone->TYPE & CNS_MEMSYM) != 0) check_memsym_constraint(ptcone, CUR_GRAPH);
 119         }
 120         CUR_GRAPH->ROOTNODES = addptype(CUR_GRAPH->ROOTNODES, 0, ptnode);
 121         CUR_GRAPH->WIDTH++;
 122     }
 123
 124     for (ptedge = ptedgelist; ptedge != NULL; ptedge = ptedge->NEXT) {
 125         if ((ptedge->TYPE & CNS_BLEEDER) == CNS_BLEEDER) continue;
 126         CUR_TREE = CUR_GRAPH->WIDTH;
 127         ptnode = build(ptedge, 0, &rescode, TRUE, force);
 128     }
 129     if (rootcone && save_hasdual) rootcone->TYPE |= YAG_HASDUAL;
 130     return CUR_GRAPH;
 131 }
 132
 133 /****************************************************************************
 134  *                         function yagRootGraph();                           *
 135  ****************************************************************************/
 136
 137 gnode_list *
 138 yagRootGraph(graph *ptgraph, cone_list *ptcone)
 139 {
 140     gnode_list *ptnode;
 141     ptype_list *ptlist;
 142
 143     CUR_GRAPH = ptgraph;
 144     ptnode = add_node(ptcone, CONE_TYPE|ROOT_NODE, 0);
 145
 146     for (ptlist = ptgraph->ROOTNODES; ptlist; ptlist = ptlist->NEXT) {
 147         ptnode->FATHERS = addchain(ptnode->FATHERS, ptlist->DATA);
 148         ((gnode_list *)ptlist->DATA)->TYPE &= ~ROOT_NODE;
 149     }
 150     freeptype(ptgraph->ROOTNODES);
 151     ptgraph->ROOTNODES = addptype(NULL, 0, ptnode);
 152
 153     return ptnode;
 154 }
 155
 156 /****************************************************************************
 157  *                         function build();                                *
 158  ****************************************************************************/
 159
 160 static gnode_list *
 161 build(edge_list  *ptedge, int depth, int *ptrescode, int invonly, int force)
 162 {
 163     cone_list  *ptcone;
 164     locon_list *ptcon;
 165     gnode_list *ptnode;
 166     gnode_list *ptinnode;
 167     edge_list  *input;
 168     edge_list  *inputlist;
 169     long        nodetype;
 170     int         tostop;
 171     int         stop = FALSE;
 172     int         hole = FALSE;
 173     int         addfathers;
 174
 175     *ptrescode = GR_NOERR;
 176
 177     /* connector node */
 178     if ((ptedge->TYPE & CNS_EXT) == CNS_EXT) {
 179         ptcon = ptedge->UEDGE.LOCON;
 180         ptnode = (gnode_list *)gethtitem(CUR_GRAPH->HASHTAB, ptcon);
 181         if (ptnode != (gnode_list *)EMPTYHT) {
 182             if (depth > ptnode->DEPTH) ptnode->DEPTH = depth;
 183         }
 184         else {
 185             ptnode = add_node(ptcon, EXT, depth);
 186             /* check for a constraint */
 187             if (getptype(ptcon->USER, YAG_CONSTRAINT_PTYPE) != NULL) {
 188                 ptnode->TYPE |= CONSTRAINT_NODE;
 189             }
 190         }
 191         stop = TRUE;
 192     }
 193     else {
 194     /* cone node */
 195
 196         ptcone = ptedge->UEDGE.CONE;
 197
 198         /* loop handling */
 199
 200         if ((ptcone->TYPE & YAG_VISITED) != 0) {
 201             *ptrescode = GR_LOOP;
 202             return NULL;
 203         }
 204         ptcone->TYPE |= YAG_VISITED;
 205
 206         nodetype = CONE_TYPE;
 207         if ((ptcone->TYPE & CNS_POWER) == CNS_POWER) nodetype |= CONSTBIT;
 208         if ((ptcone->TYPE & YAG_FORCEPRIM) == YAG_FORCEPRIM) nodetype |= FORCEPRIM_NODE;
 209
 210         /* check depth limit */
 211         tostop = FALSE;
 212         if (!invonly) {
 213             if (depth >= YAG_CONTEXT->YAG_DEPTH * 2) tostop = TRUE;
 214         }
 215         else {
 216             if (depth >= (YAG_CONTEXT->YAG_DEPTH<9?9:YAG_CONTEXT->YAG_DEPTH) * 2) tostop = TRUE;
 217         }
 218
 219         /* set depth to zero if reconverging */
 220         /* onto a rootnode                   */
 221         ptnode = (gnode_list *)gethtitem(CUR_GRAPH->HASHTAB, ptcone);
 222         if (ptnode != (gnode_list *)EMPTYHT) {
 223             if (ptnode->DEPTH == 0) depth = 0;
 224         }
 225
 226         /* check stop conditions */
 227         if (!force || depth != 0) {
 228             tostop = ((ptcone->TYPE & (CNS_POWER|CNS_LATCH|CNS_MEMSYM|CNS_RS|YAG_CONSTRAINT|YAG_STOP)) != 0);
 229             tostop = (tostop || ((ptcone->TYPE & CNS_CONFLICT) != 0 && (ptcone->TYPE & YAG_HASDUAL) == 0 && (ptcone->TECTYPE & YAG_RESCONF) == 0));
 230             if ((ptcone->TYPE & CNS_EXT) != 0) tostop = (tostop || !yagIsOutput(ptcone));
 231             if (!YAG_CONTEXT->YAG_PROP_HZ) tostop = (tostop || ((ptcone->TYPE & CNS_TRI) != 0));
 232
 233         }
 234
 235         /* check for hole for graph completeness */
 236         hole = !tostop && ((ptcone->TYPE & YAG_PARTIAL) != 0 && (ptcone->TECTYPE & CNS_DUAL_CMOS) == 0);
 237
 238         if ((!tostop && !hole) || (force && depth == 0)) {
 239
 240             if (ptnode != (gnode_list *)EMPTYHT) {
 241
 242                 /* return if reconverging onto a loop cut */
 243                 if ((ptnode->TYPE & LOOP_NODE) != 0) {
 244                     ptcone->TYPE &= ~YAG_VISITED;
 245                     return ptnode;
 246                 }
 247
 248                 /* return if reconverging onto */
 249                 /* a node of greater depth     */
 250                 if (depth > 0) {
 251                     if (ptnode->DEPTH >= depth) {
 252                         ptcone->TYPE &= ~YAG_VISITED;
 253                         return ptnode;
 254                     }
 255                     else update_depth(ptnode, depth);
 256                 }
 257             }
 258             else ptnode = add_node(ptcone, nodetype, depth);
 259
 260             addfathers = (ptnode->FATHERS == NULL);
 261
 262             stop = TRUE;
 263
 264             //if ((ptcone->TYPE & CNS_CONFLICT) != 0 && (ptcone->TYPE & YAG_HASDUAL) != 0) {
 265             if ((ptcone->TYPE & YAG_HASDUAL) != 0 && (!force || depth != 0)) {
 266                 inputlist = (edge_list *)getptype(ptcone->USER, YAG_DUALINPUTS_PTYPE)->DATA;
 267             }
 268             else inputlist = ptcone->INCONE;
 269
 270             if (!(inputlist && (inputlist->NEXT == NULL))) invonly=0;
 271
 272             for (input = inputlist; input != NULL; input = input->NEXT) {
 273
 274                 if ((input->TYPE & CNS_BLEEDER) == CNS_BLEEDER) continue;
 275                 ptinnode = build(input, depth+1, ptrescode, invonly, force);
 276                 if (ptinnode != NULL) {
 277                     if (addfathers) {
 278                         ptnode->FATHERS = addchain(ptnode->FATHERS, ptinnode);
 279                     }
 280                 }
 281                 else if  (*ptrescode == GR_LOOP) {
 282                     if (!force || depth != 0) {
 283                         if (ptnode->FATHERS != NULL) {
 284                             freechain(ptnode->FATHERS);
 285                             ptnode->FATHERS = NULL;
 286                         }
 287                         ptnode->TYPE |= LOOP_NODE;
 288                         stop = TRUE;
 289                         break;
 290                     }
 291                 }
 292                 if (((*ptrescode) & GR_STOP) == 0) stop = FALSE;
 293             }
 294         }
 295         else {
 296             ptnode = (gnode_list *)gethtitem(CUR_GRAPH->HASHTAB, ptcone);
 297             if (ptnode != (gnode_list *)EMPTYHT) {
 298                 if (ptnode->DEPTH != 0) {
 299                     if (depth > ptnode->DEPTH) ptnode->DEPTH = depth;
 300                 }
 301             }
 302             else {
 303                 ptnode = add_node((void *)ptcone, nodetype, depth);
 304             }
 305             if (tostop || hole) stop = TRUE;
 306
 307             /* check for a contraint */
 308             if ((ptcone->TYPE & YAG_CONSTRAINT) == YAG_CONSTRAINT) {
 309                 ptnode->TYPE |= CONSTRAINT_NODE;
 310             }
 311             if ((ptcone->TYPE & CNS_MEMSYM) != 0) check_memsym_constraint(ptcone, CUR_GRAPH);
 312         }
 313         ptcone->TYPE &= ~YAG_VISITED;
 314         if (ptcone == CUR_ROOT) hole = FALSE;
 315     }
 316
 317     if (hole && !tostop) {
 318         ptnode->TYPE |= HOLENODE;
 319     }
 320     if (stop) {
 321         ptnode->TYPE |= STOPNODE;
 322         *ptrescode |= GR_STOP;
 323     }
 324
 325     return ptnode;
 326 }
 327
 328 static void
 329 update_depth(gnode_list *ptnode, int depth)
 330 {
 331     chain_list  *ptchain;
 332
 333     /* reconverging onto a root */
 334     if (ptnode->DEPTH == 0) return;
 335
 336     if (depth > ptnode->DEPTH) {
 337         ptnode->DEPTH = depth;
 338
 339         for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 340             update_depth((gnode_list *)ptchain->DATA, depth+1);
 341         }
 342     }
 343 }
 344
 345 static void
 346 check_memsym_constraint(cone_list *ptcone, graph *ptgraph)
 347 {
 348     cone_list *ptloopcone;
 349     gnode_list *ptnode, *ptloopnode;
 350     ptype_list *ptuser;
 351
 352     if ((ptcone->TYPE & CNS_MEMSYM) != CNS_MEMSYM) return;
 353     if ((ptnode = (gnode_list *)gethtitem(CUR_GRAPH->HASHTAB, ptcone)) == (gnode_list *)EMPTYHT) return;
 354     if ((ptuser = getptype(ptcone->USER, YAG_MEMORY_PTYPE)) != NULL) {
 355         ptloopcone = (cone_list *)ptuser->DATA;
 356         if ((ptloopnode = (gnode_list *)gethtitem(CUR_GRAPH->HASHTAB, ptloopcone)) != (gnode_list *)EMPTYHT) {
 357             ptnode->TYPE |= MEMSYM_NODE;
 358             ptloopnode->TYPE |= MEMSYM_NODE;
 359         }
 360     }
 361 }
 362
 363 /****************************************************************************
 364  *                         function add_node();                             *
 365  ****************************************************************************/
 366
 367 static gnode_list *
 368 add_node(void *object, long type, short deep)
 369 {
 370     gnode_list *ptnode;
 371     int         i;
 372     char       *name;
 373
 374     if (EMPTY_NODE == NULL) {
 375         ptnode = (gnode_list *)mbkalloc(NODE_PACKET * sizeof(gnode_list));
 376         EMPTY_NODE = ptnode;
 377         for (i=1; i<NODE_PACKET; i++) {
 378             ptnode->NEXT = ptnode + 1;
 379             ptnode += 1;
 380         }
 381         ptnode->NEXT = NULL;
 382     }
 383     ptnode = EMPTY_NODE;
 384     EMPTY_NODE = EMPTY_NODE->NEXT;
 385     ptnode->NEXT = CUR_GRAPH->HEADNODE;
 386     CUR_GRAPH->HEADNODE = ptnode;
 387
 388     ptnode->OBJECT.PTR = object;
 389     ptnode->VISITED = FALSE;
 390     ptnode->TYPE = type;
 391     ptnode->DEPTH = deep;
 392     if (local) ptnode->TREEBIT = 1 << CUR_TREE;
 393     else ptnode->TREEBIT = 0;
 394     ptnode->NUMSONS = 0;
 395     ptnode->SONS = NULL;
 396     ptnode->FATHERS = NULL;
 397
 398     addhtitem(CUR_GRAPH->HASHTAB, object, (long)ptnode);
 399
 400     if ((type & CONE_TYPE) == CONE_TYPE) name = ((cone_list *)object)->NAME;
 401     else name = ((locon_list *)object)->NAME;
 402     addhtitem(CUR_GRAPH->NAMEHASHTAB, name, (long)ptnode);
 403
 404     return ptnode;
 405 }
 406
 407 /****************************************************************************
 408  *                         function yagNewGraph();                            *
 409  ****************************************************************************/
 410
 411 graph *
 412 yagNewGraph()
 413 {
 414     graph  *ptgraph;
 415     int     i;
 416
 417     if (EMPTY_GRAPH == NULL) {
 418         ptgraph = (graph *)mbkalloc(GRAPH_PACKET * sizeof(graph));
 419         EMPTY_GRAPH = ptgraph;
 420         for (i=1; i<GRAPH_PACKET; i++) {
 421             ptgraph->NEXT = ptgraph + 1;
 422             ptgraph += 1;
 423         }
 424         ptgraph->NEXT = NULL;
 425     }
 426     ptgraph = EMPTY_GRAPH;
 427     EMPTY_GRAPH = EMPTY_GRAPH->NEXT;
 428     ptgraph->NEXT = ALLOC_GRAPH;
 429     ALLOC_GRAPH = ptgraph;
 430
 431     ptgraph->ROOTNODES = NULL;
 432     ptgraph->PRIMVARS = NULL;
 433     ptgraph->HEADNODE = NULL;
 434     ptgraph->HASHTAB = addht(40);
 435     ptgraph->NAMEHASHTAB = addht(40);
 436     ptgraph->CONSTRAINTS = NULL;
 437     ptgraph->EXTRA_CONSTRAINTS = NULL;
 438     ptgraph->COMPLETE = FALSE;
 439     ptgraph->WIDTH = 0;
 440
 441     return ptgraph;
 442 }
 443
 444 /****************************************************************************
 445  *                         function yagFreeGraph();                           *
 446  ****************************************************************************/
 447
 448 void
 449 yagFreeGraph(graph *ptgraph)
 450 {
 451     gnode_list  *ptnode, *ptlastnode = NULL;
 452     ptype_list  *ptptype;
 453
 454     if (ptgraph == NULL) yagBug(DBG_NULL_PTR, "yagFreeGraph", NULL, NULL, 0);
 455
 456     delht(ptgraph->HASHTAB);
 457     delht(ptgraph->NAMEHASHTAB);
 458
 459     for (ptnode = ptgraph->HEADNODE; ptnode != NULL; ptnode = ptnode->NEXT) {
 460         freechain(ptnode->FATHERS);
 461         freechain(ptnode->SONS);
 462         ptlastnode = ptnode;
 463     }
 464     if (ptlastnode != NULL) {
 465         ptlastnode->NEXT = EMPTY_NODE;
 466         EMPTY_NODE = ptgraph->HEADNODE;
 467         freeptype(ptgraph->ROOTNODES);
 468         freechain(ptgraph->PRIMVARS);
 469         freeptype(ptgraph->CONSTRAINTS);
 470         for (ptptype = ptgraph->EXTRA_CONSTRAINTS; ptptype; ptptype = ptptype->NEXT) {
 471             freechain((chain_list *)ptptype->TYPE);
 472             freeExpr((chain_list *)ptptype->DATA);
 473         }
 474         freeptype(ptgraph->EXTRA_CONSTRAINTS);
 475     }
 476
 477     ALLOC_GRAPH = ptgraph->NEXT;
 478     ptgraph->NEXT = EMPTY_GRAPH;
 479     EMPTY_GRAPH = ptgraph;
 480 }
 481
 482 /****************************************************************************
 483  *                         function yagTraverseGraph();                       *
 484  ****************************************************************************/
 485
 486 void
 487 yagAddExtraConstraints(graph *ptgraph)
 488 {
 489     ptype_list  *ptlist;
 490
 491     for (ptlist = ptgraph->ROOTNODES; ptlist; ptlist = ptlist->NEXT) {
 492         extra_constraints((gnode_list *)ptlist->DATA, ptgraph);
 493     }
 494     for (ptlist = ptgraph->ROOTNODES; ptlist; ptlist = ptlist->NEXT) {
 495         unmark((gnode_list *)ptlist->DATA);
 496     }
 497 }
 498
 499 static void
 500 extra_constraints(gnode_list *ptnode, graph *ptgraph)
 501 {
 502     chain_list  *ptchain;
 503     ptype_list  *ptuser;
 504     cone_list   *ptcone, *ptinvcone;
 505     gnode_list  *ptinvnode;
 506     chain_list  *support;
 507     chain_list  *tempexpr;
 508
 509     if (ptnode->VISITED) return;
 510     ptnode->VISITED = TRUE;
 511
 512     if ((ptnode->TYPE & EXT) == 0) {
 513         ptcone = ptnode->OBJECT.CONE;
 514         if ((ptuser = getptype(ptcone->USER, CNS_INVCONE)) != NULL) {
 515             for (ptchain = (chain_list *)ptuser->DATA; ptchain; ptchain = ptchain->NEXT) {
 516                 ptinvcone = (cone_list *)ptchain->DATA;
 517                 support = addchain(NULL, ptcone->NAME);
 518                 support = addchain(support, ptinvcone->NAME);
 519                 tempexpr = createExpr(OR);
 520                 addQExpr(tempexpr, createAtom(ptcone->NAME));
 521                 addQExpr(tempexpr, createAtom(ptinvcone->NAME));
 522                 ptgraph->CONSTRAINTS = addptype(ptgraph->CONSTRAINTS, (long)support, (void *)tempexpr);
 523                 ptgraph->EXTRA_CONSTRAINTS = addptype(ptgraph->EXTRA_CONSTRAINTS, (long)support, (void *)tempexpr);
 524                 tempexpr = createExpr(AND);
 525                 addQExpr(tempexpr, createAtom(ptcone->NAME));
 526                 addQExpr(tempexpr, createAtom(ptinvcone->NAME));
 527                 tempexpr = notExpr(tempexpr);
 528                 ptgraph->CONSTRAINTS = addptype(ptgraph->CONSTRAINTS, (long)support, (void *)tempexpr);
 529                 ptgraph->EXTRA_CONSTRAINTS = addptype(ptgraph->EXTRA_CONSTRAINTS, (long)yagCopyChainList(support), (void *)tempexpr);
 530             }
 531         }
 532         if (((ptnode->TYPE & MEMSYM_NODE) == MEMSYM_NODE) && (ptuser = getptype(ptcone->USER, YAG_MEMORY_PTYPE)) != NULL) {
 533             ptinvcone = (cone_list *)ptuser->DATA;
 534             ptinvnode = (gnode_list *)gethtitem(CUR_GRAPH->HASHTAB, ptinvcone);
 535             if (ptinvnode != (gnode_list *)EMPTYHT) {
 536                 ptinvnode->VISITED = TRUE;
 537                 support = addchain(NULL, ptcone->NAME);
 538                 support = addchain(support, ptinvcone->NAME);
 539                 tempexpr = createExpr(OR);
 540                 addQExpr(tempexpr, createAtom(ptcone->NAME));
 541                 addQExpr(tempexpr, createAtom(ptinvcone->NAME));
 542                 ptgraph->CONSTRAINTS = addptype(ptgraph->CONSTRAINTS, (long)support, (void *)tempexpr);
 543                 ptgraph->EXTRA_CONSTRAINTS = addptype(ptgraph->EXTRA_CONSTRAINTS, (long)support, (void *)tempexpr);
 544                 tempexpr = createExpr(AND);
 545                 addQExpr(tempexpr, createAtom(ptcone->NAME));
 546                 addQExpr(tempexpr, createAtom(ptinvcone->NAME));
 547                 tempexpr = notExpr(tempexpr);
 548                 ptgraph->CONSTRAINTS = addptype(ptgraph->CONSTRAINTS, (long)support, (void *)tempexpr);
 549                 ptgraph->EXTRA_CONSTRAINTS = addptype(ptgraph->EXTRA_CONSTRAINTS, (long)yagCopyChainList(support), (void *)tempexpr);
 550             }
 551         }
 552     }
 553     if ((ptnode->TYPE & PRIMNODE) == 0) {
 554         for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 555             extra_constraints((gnode_list *)ptchain->DATA, ptgraph);
 556         }
 557     }
 558 }
 559
 560 /****************************************************************************
 561  *                         function yagTraverseGraph();                       *
 562  ****************************************************************************/
 563
 564 void
 565 yagTraverseGraph(graph *ptgraph)
 566 {
 567     ptype_list  *ptlist;
 568
 569     numholes = 0;
 570     for (ptlist = ptgraph->ROOTNODES; ptlist; ptlist = ptlist->NEXT) {
 571         number_sons((gnode_list *)ptlist->DATA);
 572     }
 573     for (ptlist = ptgraph->ROOTNODES; ptlist; ptlist = ptlist->NEXT) {
 574         unmark((gnode_list *)ptlist->DATA);
 575     }
 576
 577     for (ptlist = ptgraph->ROOTNODES; ptlist; ptlist = ptlist->NEXT) {
 578         traverse((gnode_list *)ptlist->DATA);
 579     }
 580
 581     VAR_LIST = NULL;
 582     for (ptlist = ptgraph->ROOTNODES; ptlist; ptlist = ptlist->NEXT) {
 583         pick_prims((gnode_list *)ptlist->DATA);
 584     }
 585     for (ptlist = ptgraph->ROOTNODES; ptlist; ptlist = ptlist->NEXT) {
 586         unmark((gnode_list *)ptlist->DATA);
 587     }
 588     ptgraph->COMPLETE = (numholes < 1);
 589     ptgraph->PRIMVARS = VAR_LIST;
 590 }
 591
 592 static void
 593 number_sons(gnode_list *ptnode)
 594 {
 595     chain_list  *ptchain;
 596     gnode_list  *ptfather;
 597     int          outdepth = FALSE;
 598     int          forceprim = FALSE;
 599
 600     ptnode->NUMSONS++;
 601     if (ptnode->VISITED) return;
 602     ptnode->VISITED = TRUE;
 603
 604     if (ptnode->DEPTH >= YAG_CONTEXT->YAG_DEPTH) {
 605         if (ptnode->FATHERS != NULL) {
 606             freechain(ptnode->FATHERS);
 607             ptnode->FATHERS = NULL;
 608         }
 609         return;
 610     }
 611
 612     if ((ptnode->TYPE & HOLENODE) != 0) {
 613         numholes++;
 614     }
 615
 616     for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 617         ptfather = (gnode_list *)ptchain->DATA;
 618         if (ptfather->DEPTH > YAG_CONTEXT->YAG_DEPTH) outdepth = TRUE;
 619         if ((ptfather->TYPE & FORCEPRIM_NODE) != 0) forceprim = TRUE;
 620     }
 621     if (outdepth && !forceprim) {
 622         freechain(ptnode->FATHERS);
 623         ptnode->FATHERS = NULL;
 624         return;
 625     }
 626
 627     for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 628         number_sons((gnode_list *)ptchain->DATA);
 629     }
 630 }
 631
 632 static void
 633 traverse(gnode_list *ptnode)
 634 {
 635     chain_list  *ptchain;
 636
 637     if ((ptnode->TYPE & TRAVERSED) != 0) return;
 638     ptnode->TYPE |= TRAVERSED;
 639
 640     for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 641         traverse((gnode_list *)ptchain->DATA);
 642     }
 643
 644     total_son_arcs = 0;
 645     visited_son_arcs = 0;
 646
 647     for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 648         count_sons((gnode_list *)ptchain->DATA);
 649     }
 650     for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 651         unmark((gnode_list *)ptchain->DATA);
 652     }
 653
 654     if (total_son_arcs == visited_son_arcs) ptnode->TYPE |= PRIMNODE;
 655 }
 656
 657 static void
 658 unmark(gnode_list *ptnode)
 659 {
 660     chain_list  *ptchain;
 661
 662     if (ptnode->VISITED == FALSE) return;
 663     ptnode->VISITED = FALSE;
 664
 665     if ((ptnode->TYPE & PRIMNODE) != 0) return;
 666
 667     for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 668         unmark((gnode_list *)ptchain->DATA);
 669     }
 670 }
 671
 672 static void
 673 count_sons(gnode_list *ptnode)
 674 {
 675     chain_list  *ptchain;
 676
 677     visited_son_arcs++;
 678
 679     if (ptnode->VISITED) return;
 680     ptnode->VISITED = TRUE;
 681
 682     total_son_arcs += ptnode->NUMSONS;
 683
 684     /* add additional dependancy to constrained node to force it PRIM */
 685     if ((ptnode->TYPE & (CONSTBIT|CONSTRAINT_NODE|FORCEPRIM_NODE|MEMSYM_NODE)) != 0) total_son_arcs++;
 686
 687     if ((ptnode->TYPE & PRIMNODE) == 0) {
 688         for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 689             count_sons((gnode_list *)ptchain->DATA);
 690         }
 691     }
 692 }
 693
 694 static void
 695 pick_prims(gnode_list *ptnode)
 696 {
 697     chain_list  *ptchain;
 698
 699     if (ptnode->VISITED) return;
 700     ptnode->VISITED = TRUE;
 701
 702     if ((ptnode->TYPE & CONSTRAINT_NODE) != 0) {
 703         if ((ptnode->TYPE & EXT) != 0) yagTagConstraint(ptnode->OBJECT.LOCON->NAME);
 704         else yagTagConstraint(ptnode->OBJECT.CONE->NAME);
 705     }
 706
 707     if ((ptnode->TYPE & PRIMNODE) != 0) {
 708         VAR_LIST = add_primvar(VAR_LIST, ptnode);
 709     }
 710     else {
 711         for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 712             pick_prims((gnode_list *)ptchain->DATA);
 713         }
 714     }
 715 }
 716
 717 /****************************************************************************
 718  *                         miscellaneous utility functions                  *
 719  ****************************************************************************/
 720
 721  /*--------------------------------------------------*
 722  | Add a node to the main list of primary variables  |
 723  *--------------------------------------------------*/
 724
 725 static chain_list *
 726 add_primvar(chain_list *list, gnode_list *ptnode)
 727 {
 728     return addchain(list, ptnode);
 729 }
 730
 731  /*----------------------------------------------*
 732  | Return the node pointer to the named father   |
 733  | of the given node                             |
 734  *-----------------------------------------------*/
 735
 736 gnode_list *
 737 yagGetNodeFather(gnode_list *ptnode, char *name)
 738 {
 739     chain_list  *ptchain;
 740     gnode_list  *ptfather;
 741     char        *nodename;
 742
 743     for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 744         ptfather = (gnode_list *)ptchain->DATA;
 745         if ((ptfather->TYPE & EXT) != 0) {
 746             nodename = ptfather->OBJECT.LOCON->NAME;
 747         }
 748         else {
 749             nodename = ptfather->OBJECT.CONE->NAME;
 750         }
 751         if (nodename == name) break;
 752     }
 753     if (ptchain == NULL) {
 754         yagBug(DBG_NO_FATHER, "yagGetNodeFather", name, ptnode->OBJECT.CONE->NAME, 0);
 755         return NULL;
 756     }
 757     else return ptfather;
 758 }
 759
 760 /****************************************************************************
 761  *                         function yagExtendSupportRoot();                   *
 762  ****************************************************************************/
 763  /*------------------------------------------*
 764  | Extend the support graph root of a given  |
 765  | graph by the given object                 |
 766  *-------------------------------------------*/
 767
 768 int
 769 yagExtendSupportRoot(graph *ptgraph, cone_list *ptcone, long roottype)
 770 {
 771     gnode_list *ptnode;
 772     ptype_list *ptroot;
 773     int         result;
 774
 775     local = TRUE;
 776     CUR_TREE = ptgraph->WIDTH;
 777     CUR_GRAPH = ptgraph;
 778
 779     result = TRUE;
 780     ptnode = (gnode_list *)gethtitem(ptgraph->HASHTAB, ptcone);
 781     if (ptnode == (gnode_list *)EMPTYHT) {
 782         ptnode = add_node(ptcone, CONE_TYPE, 0);
 783         result = FALSE;
 784     }
 785     else mark_treebit(ptnode);
 786
 787     ptgraph->ROOTNODES = addptype(ptgraph->ROOTNODES, roottype, ptnode);
 788
 789     for (ptroot = ptgraph->ROOTNODES; ptroot; ptroot = ptroot->NEXT) {
 790         ((gnode_list *)ptroot->DATA)->TYPE |= ptroot->TYPE;
 791     }
 792
 793     ptgraph->WIDTH++;
 794     local = FALSE;
 795     return result;
 796 }
 797
 798 /****************************************************************************
 799  *                         function yagExtendSupportGraph();                       *
 800  ****************************************************************************/
 801  /*------------------------------------------*
 802  | Update the given graph given a node and   |
 803  | its newly obtained father list            |
 804  *-------------------------------------------*/
 805
 806 void
 807 yagExtendSupportGraph(graph *ptgraph, gnode_list *ptnode, chain_list *ptfatherlist)
 808 {
 809     chain_list *ptchain;
 810     cone_list  *ptcone;
 811     gnode_list *ptfather;
 812
 813     CUR_TREE = ptgraph->WIDTH - 1;
 814     CUR_GRAPH = ptgraph;
 815
 816     for (ptchain = ptfatherlist; ptchain; ptchain = ptchain->NEXT) {
 817         ptcone = ((gnode_list *)ptchain->DATA)->OBJECT.CONE;
 818
 819         ptfather = (gnode_list *)gethtitem(ptgraph->HASHTAB, ptcone);
 820         if (ptfather == (gnode_list *)EMPTYHT) {
 821             ptfather = add_node(ptcone, CONE_TYPE, 0);
 822         }
 823         ptfather->NUMSONS++;
 824         ptfather->SONS = addchain(ptfather->SONS, ptnode);
 825         ptnode->FATHERS = addchain(ptnode->FATHERS, ptfather);
 826     }
 827 }
 828
 829 /****************************************************************************
 830  *                         function yagReduceSupportGraph();                       *
 831  ****************************************************************************/
 832  /*------------------------------------------*
 833  | Reduce the given graph by removing the    |
 834  | most recently added root node             |
 835  *-------------------------------------------*/
 836
 837 void
 838 yagReduceSupportGraph(graph *ptgraph)
 839 {
 840     gnode_list *ptnode;
 841     ptype_list *ptroot;
 842
 843     CUR_TREE = ptgraph->WIDTH - 1;
 844
 845     if (ptgraph == NULL) yagBug(DBG_NULL_PTR, "yagReduceSupportGraph", NULL, NULL, 0);
 846
 847     for (ptroot = ptgraph->ROOTNODES; ptroot; ptroot = ptroot->NEXT) {
 848         ((gnode_list *)ptroot->DATA)->TYPE &= ~(TN_NODE|TP_NODE);
 849     }
 850
 851     ptnode = (gnode_list *)ptgraph->ROOTNODES->DATA;
 852     reduce(ptgraph, ptnode);
 853     ptroot = ptgraph->ROOTNODES;
 854     ptgraph->ROOTNODES = ptgraph->ROOTNODES->NEXT;
 855     ptroot->NEXT = NULL;
 856     freeptype(ptroot);
 857     ptgraph->WIDTH--;
 858     ptgraph->COMPLETE = check_complete(ptgraph);
 859 }
 860
 861 static void
 862 reduce(graph *ptgraph, gnode_list *ptnode)
 863 {
 864     chain_list *ptchain;
 865     gnode_list *ptfather;
 866
 867     unmark_treebit(ptnode);
 868     if (in_other_tree(ptnode)) return;
 869
 870     for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 871         ptfather = (gnode_list *)ptchain->DATA;
 872         ptfather->SONS = yagRmvChain(ptfather->SONS, ptnode);
 873         ptfather->NUMSONS--;
 874         if (ptfather->NUMSONS == 0) {
 875             ptfather->TYPE |= DELETED_NODE;
 876             delhtitem(ptgraph->HASHTAB, ptfather->OBJECT.PTR);
 877         }
 878     }
 879
 880     freechain(ptnode->FATHERS);
 881     ptnode->FATHERS = NULL;
 882
 883     /* beware : node may be its own father hence already treated */
 884     if ((ptnode->TYPE & DELETED_NODE) == 0 && ptnode->NUMSONS == 0) {
 885         ptnode->TYPE |= DELETED_NODE;
 886         delhtitem(ptgraph->HASHTAB, ptnode->OBJECT.PTR);
 887     }
 888 }
 889
 890 /****************************************************************************
 891  *                         function yagGetPrimVars();                         *
 892  ****************************************************************************/
 893  /*---------------------------------------------*
 894  | Return list of primary variables which       |
 895  | influence a given node                       |
 896  *---------------------------------------------*/
 897
 898 chain_list *
 899 yagGetPrimVars(graph *ptgraph, gnode_list *ptnode)
 900 {
 901     chain_list *ptchain;
 902     gnode_list *ptprimnode;
 903
 904     unmark(ptnode);
 905     VAR_LIST = NULL;
 906     CUR_GRAPH = ptgraph;
 907     add_constraints = FALSE;
 908     prop_search(ptnode);
 909
 910     if (add_constraints) {
 911         for (ptchain = ptgraph->PRIMVARS; ptchain; ptchain = ptchain->NEXT) {
 912             ptprimnode = (gnode_list *)ptchain->DATA;
 913             if ((ptprimnode->TYPE & CONSTRAINT_NODE) != 0 && !ptprimnode->VISITED) {
 914                 VAR_LIST = addchain(VAR_LIST, ptprimnode);
 915             }
 916         }
 917     }
 918
 919     unmark(ptnode);
 920     return VAR_LIST;
 921 }
 922
 923 chain_list *
 924 yagGetJustPrimVars(graph *ptgraph, gnode_list *ptnode)
 925 {
 926     unmark(ptnode);
 927     VAR_LIST = NULL;
 928     CUR_GRAPH = ptgraph;
 929     prop_search(ptnode);
 930     unmark(ptnode);
 931     return VAR_LIST;
 932 }
 933
 934 static void
 935 prop_search(gnode_list *ptnode)
 936 {
 937     chain_list *ptchain;
 938
 939     if (ptnode->VISITED) return;
 940     ptnode->VISITED = TRUE;
 941     if ((ptnode->TYPE & PRIMNODE) != 0) {
 942         if ((ptnode->TYPE & CONSTRAINT_NODE) != 0) add_constraints = TRUE;
 943         VAR_LIST = addchain(VAR_LIST, ptnode);
 944         return;
 945     }
 946     else {
 947         for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 948             prop_search((gnode_list *)ptchain->DATA);
 949         }
 950     }
 951 }
 952
 953 static chain_list *RESCHAIN;
 954
 955 static void
 956 isNonPrimaryUsed(gnode_list *ptnode)
 957 {
 958     chain_list     *ptchain;
 959     gnode_list     *ptinnode;
 960
 961     if (ptnode->VISITED)
 962         return;
 963     ptnode->VISITED = TRUE;
 964     if ((ptnode->TYPE & PRIMNODE) != 0) return;
 965
 966     RESCHAIN = addchain(RESCHAIN, ptnode);
 967
 968     for (ptchain = ptnode->FATHERS; ptchain; ptchain = ptchain->NEXT) {
 969         ptinnode = (gnode_list *) ptchain->DATA;
 970         isNonPrimaryUsed(ptinnode);
 971     }
 972 }
 973
 974 chain_list *
 975 yagGetNonPrimaryUsedNodes(graph *ptgraph)
 976 {
 977     ptype_list     *ptroots;
 978     gnode_list     *ptnode;
 979
 980     RESCHAIN = NULL;
 981
 982     for (ptroots = ptgraph->ROOTNODES; ptroots; ptroots = ptroots->NEXT) {
 983         ptnode = (gnode_list *) ptroots->DATA;
 984         isNonPrimaryUsed(ptnode);
 985     }
 986     for (ptroots = ptgraph->ROOTNODES; ptroots; ptroots = ptroots->NEXT) {
 987         ptnode = (gnode_list *) ptroots->DATA;
 988         unmark(ptnode);
 989     }
 990     return RESCHAIN;
 991 }
 992