sys/src/cmd/spin/pangen5.c

   1 /***** spin: pangen5.c *****/
   2
   3 /*
   4  * This file is part of the public release of Spin. It is subject to the
   5  * terms in the LICENSE file that is included in this source directory.
   6  * Tool documentation is available at http://spinroot.com
   7  */
   8
   9 #include "spin.h"
  10 #include "y.tab.h"
  11
  12 typedef struct BuildStack {
  13         FSM_trans *t;
  14         struct BuildStack *nxt;
  15 } BuildStack;
  16
  17 extern ProcList *rdy;
  18 extern int verbose, eventmapnr, claimnr, rvopt, export_ast, u_sync;
  19 extern Element *Al_El;
  20
  21 static FSM_state *fsm_free;
  22 static FSM_trans *trans_free;
  23 static BuildStack *bs, *bf;
  24 static int max_st_id;
  25 static int cur_st_id;
  26 int o_max;
  27 FSM_state *fsm;
  28 FSM_state **fsm_tbl;
  29 FSM_use   *use_free;
  30
  31 static void ana_seq(Sequence *);
  32 static void ana_stmnt(FSM_trans *, Lextok *, int);
  33
  34 extern void AST_slice(void);
  35 extern void AST_store(ProcList *, int);
  36 extern int  has_global(Lextok *);
  37 extern void exit(int);
  38
  39 static void
  40 fsm_table(void)
  41 {       FSM_state *f;
  42         max_st_id += 2;
  43         /* fprintf(stderr, "omax %d, max=%d\n", o_max, max_st_id); */
  44         if (o_max < max_st_id)
  45         {       o_max = max_st_id;
  46                 fsm_tbl = (FSM_state **) emalloc(max_st_id * sizeof(FSM_state *));
  47         } else
  48                 memset((char *)fsm_tbl, 0, max_st_id * sizeof(FSM_state *));
  49         cur_st_id = max_st_id;
  50         max_st_id = 0;
  51
  52         for (f = fsm; f; f = f->nxt)
  53                 fsm_tbl[f->from] = f;
  54 }
  55
  56 static int
  57 FSM_DFS(int from, FSM_use *u)
  58 {       FSM_state *f;
  59         FSM_trans *t;
  60         FSM_use *v;
  61         int n;
  62
  63         if (from == 0)
  64                 return 1;
  65
  66         f = fsm_tbl[from];
  67
  68         if (!f)
  69         {       printf("cannot find state %d\n", from);
  70                 fatal("fsm_dfs: cannot happen\n", (char *) 0);
  71         }
  72
  73         if (f->seen)
  74                 return 1;
  75         f->seen = 1;
  76
  77         for (t = f->t; t; t = t->nxt)
  78         {
  79                 for (n = 0; n < 2; n++)
  80                 for (v = t->Val[n]; v; v = v->nxt)
  81                         if (u->var == v->var)
  82                                 return n;       /* a read or write */
  83
  84                 if (!FSM_DFS(t->to, u))
  85                         return 0;
  86         }
  87         return 1;
  88 }
  89
  90 static void
  91 new_dfs(void)
  92 {       int i;
  93
  94         for (i = 0; i < cur_st_id; i++)
  95                 if (fsm_tbl[i])
  96                         fsm_tbl[i]->seen = 0;
  97 }
  98
  99 static int
 100 good_dead(Element *e, FSM_use *u)
 101 {
 102         switch (u->special) {
 103         case 2: /* ok if it's a receive */
 104                 if (e->n->ntyp == ASGN
 105                 &&  e->n->rgt->ntyp == CONST
 106                 &&  e->n->rgt->val == 0)
 107                         return 0;
 108                 break;
 109         case 1: /* must be able to use oval */
 110                 if (e->n->ntyp != 'c'
 111                 &&  e->n->ntyp != 'r')
 112                         return 0;       /* can't really happen */
 113                 break;
 114         }
 115         return 1;
 116 }
 117
 118 #if 0
 119 static int howdeep = 0;
 120 #endif
 121
 122 static int
 123 eligible(FSM_trans *v)
 124 {       Element *el = ZE;
 125         Lextok  *lt = ZN;
 126
 127         if (v) el = v->step;
 128         if (el) lt = v->step->n;
 129
 130         if (!lt                         /* dead end */
 131         ||  v->nxt                      /* has alternatives */
 132         ||  el->esc                     /* has an escape */
 133         ||  (el->status&CHECK2)         /* remotely referenced */
 134         ||  lt->ntyp == ATOMIC
 135         ||  lt->ntyp == NON_ATOMIC      /* used for inlines -- should be able to handle this */
 136         ||  lt->ntyp == IF
 137         ||  lt->ntyp == C_CODE
 138         ||  lt->ntyp == C_EXPR
 139         ||  has_lab(el, 0)              /* any label at all */
 140         ||  lt->ntyp == SET_P           /* to prevent multiple set_p merges */
 141
 142         ||  lt->ntyp == DO
 143         ||  lt->ntyp == UNLESS
 144         ||  lt->ntyp == D_STEP
 145         ||  lt->ntyp == ELSE
 146         ||  lt->ntyp == '@'
 147         ||  lt->ntyp == 'c'
 148         ||  lt->ntyp == 'r'
 149         ||  lt->ntyp == 's')
 150                 return 0;
 151
 152         if (!(el->status&(2|4)))        /* not atomic */
 153         {       int unsafe = (el->status&I_GLOB)?1:has_global(el->n);
 154                 if (unsafe)
 155                         return 0;
 156         }
 157
 158         return 1;
 159 }
 160
 161 static int
 162 canfill_in(FSM_trans *v)
 163 {       Element *el = v->step;
 164         Lextok  *lt = v->step->n;
 165
 166         if (!lt                         /* dead end */
 167         ||  v->nxt                      /* has alternatives */
 168         ||  el->esc                     /* has an escape */
 169         ||  (el->status&CHECK2))        /* remotely referenced */
 170                 return 0;
 171
 172         if (!(el->status&(2|4))         /* not atomic */
 173         &&  ((el->status&I_GLOB)
 174         ||   has_global(el->n)))        /* and not safe */
 175                 return 0;
 176
 177         return 1;
 178 }
 179
 180 static int
 181 pushbuild(FSM_trans *v)
 182 {       BuildStack *b;
 183
 184         for (b = bs; b; b = b->nxt)
 185                 if (b->t == v)
 186                         return 0;
 187         if (bf)
 188         {       b = bf;
 189                 bf = bf->nxt;
 190         } else
 191                 b = (BuildStack *) emalloc(sizeof(BuildStack));
 192         b->t = v;
 193         b->nxt = bs;
 194         bs = b;
 195         return 1;
 196 }
 197
 198 static void
 199 popbuild(void)
 200 {       BuildStack *f;
 201         if (!bs)
 202                 fatal("cannot happen, popbuild", (char *) 0);
 203         f = bs;
 204         bs = bs->nxt;
 205         f->nxt = bf;
 206         bf = f;                         /* freelist */
 207 }
 208
 209 static int
 210 build_step(FSM_trans *v)
 211 {       FSM_state *f;
 212         Element *el;
 213 #if 0
 214         Lextok  *lt = ZN;
 215 #endif
 216         int     st;
 217         int     r;
 218
 219         if (!v) return -1;
 220
 221         el = v->step;
 222         st = v->to;
 223
 224         if (!el) return -1;
 225
 226         if (v->step->merge)
 227                 return v->step->merge;  /* already done */
 228
 229         if (!eligible(v))               /* non-blocking */
 230                 return -1;
 231
 232         if (!pushbuild(v))              /* cycle detected */
 233                 return -1;              /* break cycle */
 234
 235         f = fsm_tbl[st];
 236 #if 0
 237         lt = v->step->n;
 238         if (verbose&32)
 239         {       if (++howdeep == 1)
 240                         printf("spin: %s:%d, merge:\n", lt->fn->name, lt->ln);
 241                 printf("\t[%d] <seqno %d>\t", howdeep, el->seqno);
 242                 comment(stdout, lt, 0);
 243                 printf(";\n");
 244         }
 245 #endif
 246         r = build_step(f->t);
 247         v->step->merge = (r == -1) ? st : r;
 248 #if 0
 249         if (verbose&32)
 250         {       printf("        merge value: %d (st=%d,r=%d, line %d)\n",
 251                         v->step->merge, st, r, el->n->ln);
 252                 howdeep--;
 253         }
 254 #endif
 255         popbuild();
 256
 257         return v->step->merge;
 258 }
 259
 260 static void
 261 FSM_MERGER(/* char *pname */ void)      /* find candidates for safely merging steps */
 262 {       FSM_state *f, *g;
 263         FSM_trans *t;
 264         Lextok  *lt;
 265
 266         for (f = fsm; f; f = f->nxt)            /* all states */
 267         for (t = f->t; t; t = t->nxt)           /* all edges */
 268         {       if (!t->step) continue;         /* happens with 'unless' */
 269
 270                 t->step->merge_in = f->in;      /* ?? */
 271
 272                 if (t->step->merge)
 273                         continue;
 274                 lt = t->step->n;
 275
 276                 if (lt->ntyp == 'c'
 277                 ||  lt->ntyp == 'r'
 278                 ||  lt->ntyp == 's')    /* blocking stmnts */
 279                         continue;       /* handled in 2nd scan */
 280
 281                 if (!eligible(t))
 282                         continue;
 283
 284                 g = fsm_tbl[t->to];
 285                 if (!g || !eligible(g->t))
 286                 {
 287 #define SINGLES
 288 #ifdef SINGLES
 289                         t->step->merge_single = t->to;
 290 #if 0
 291                         if ((verbose&32))
 292                         {       printf("spin: %s:%d, merge_single:\n\t<seqno %d>\t",
 293                                         t->step->n->fn->name,
 294                                         t->step->n->ln,
 295                                         t->step->seqno);
 296                                 comment(stdout, t->step->n, 0);
 297                                 printf(";\n");
 298                         }
 299 #endif
 300 #endif
 301                         /* t is an isolated eligible step:
 302                          *
 303                          * a merge_start can connect to a proper
 304                          * merge chain or to a merge_single
 305                          * a merge chain can be preceded by
 306                          * a merge_start, but not by a merge_single
 307                          */
 308
 309                         continue;
 310                 }
 311
 312                 (void) build_step(t);
 313         }
 314
 315         /* 2nd scan -- find possible merge_starts */
 316
 317         for (f = fsm; f; f = f->nxt)            /* all states */
 318         for (t = f->t; t; t = t->nxt)           /* all edges */
 319         {       if (!t->step || t->step->merge)
 320                         continue;
 321
 322                 lt = t->step->n;
 323 #if 0
 324         4.1.3:
 325         an rv send operation ('s') inside an atomic, *loses* atomicity
 326         when executed, and should therefore never be merged with a subsequent
 327         statement within the atomic sequence
 328         the same is not true for non-rv send operations;
 329         6.2.2:
 330         RUN statements can start a new process at a higher priority level
 331         which interferes with statement merging, so it too is not a suitable
 332         merge target
 333 #endif
 334
 335                 if ((lt->ntyp == 'c' && !any_oper(lt->lft, RUN)) /* 2nd clause 6.2.2 */
 336                 ||  lt->ntyp == 'r'
 337                 ||  (lt->ntyp == 's' && u_sync == 0))   /* added !u_sync in 4.1.3 */
 338                 {       if (!canfill_in(t))             /* atomic, non-global, etc. */
 339                                 continue;
 340
 341                         g = fsm_tbl[t->to];
 342                         if (!g || !g->t || !g->t->step)
 343                                 continue;
 344                         if (g->t->step->merge)
 345                                 t->step->merge_start = g->t->step->merge;
 346 #ifdef SINGLES
 347                         else if (g->t->step->merge_single)
 348                                 t->step->merge_start = g->t->step->merge_single;
 349 #endif
 350 #if 0
 351                         if ((verbose&32)
 352                         && t->step->merge_start)
 353                         {       printf("spin: %s:%d, merge_START:\n\t<seqno %d>\t",
 354                                                 lt->fn->name, lt->ln,
 355                                                 t->step->seqno);
 356                                 comment(stdout, lt, 0);
 357                                 printf(";\n");
 358                         }
 359 #endif
 360                 }
 361         }
 362 }
 363
 364 static void
 365 FSM_ANA(void)
 366 {       FSM_state *f;
 367         FSM_trans *t;
 368         FSM_use *u, *v, *w;
 369         int n;
 370
 371         for (f = fsm; f; f = f->nxt)            /* all states */
 372         for (t = f->t; t; t = t->nxt)           /* all edges */
 373         for (n = 0; n < 2; n++)                 /* reads and writes */
 374         for (u = t->Val[n]; u; u = u->nxt)
 375         {       if (!u->var->context    /* global */
 376                 ||   u->var->type == CHAN
 377                 ||   u->var->type == STRUCT)
 378                         continue;
 379                 new_dfs();
 380                 if (FSM_DFS(t->to, u))  /* cannot hit read before hitting write */
 381                         u->special = n+1;       /* means, reset to 0 after use */
 382         }
 383
 384         if (!export_ast)
 385         for (f = fsm; f; f = f->nxt)
 386         for (t = f->t; t; t = t->nxt)
 387         for (n = 0; n < 2; n++)
 388         for (u = t->Val[n], w = (FSM_use *) 0; u; )
 389         {       if (u->special)
 390                 {       v = u->nxt;
 391                         if (!w)                 /* remove from list */
 392                                 t->Val[n] = v;
 393                         else
 394                                 w->nxt = v;
 395 #if q
 396                         if (verbose&32)
 397                         {       printf("%s : %3d:  %d -> %d \t",
 398                                         t->step->n->fn->name,
 399                                         t->step->n->ln,
 400                                         f->from,
 401                                         t->to);
 402                                 comment(stdout, t->step->n, 0);
 403                                 printf("\t%c%d: %s\n", n==0?'R':'L',
 404                                         u->special, u->var->name);
 405                         }
 406 #endif
 407                         if (good_dead(t->step, u))
 408                         {       u->nxt = t->step->dead; /* insert into dead */
 409                                 t->step->dead = u;
 410                         }
 411                         u = v;
 412                 } else
 413                 {       w = u;
 414                         u = u->nxt;
 415         }       }
 416 }
 417
 418 void
 419 rel_use(FSM_use *u)
 420 {
 421         if (!u) return;
 422         rel_use(u->nxt);
 423         u->var = (Symbol *) 0;
 424         u->special = 0;
 425         u->nxt = use_free;
 426         use_free = u;
 427 }
 428
 429 static void
 430 rel_trans(FSM_trans *t)
 431 {
 432         if (!t) return;
 433         rel_trans(t->nxt);
 434         rel_use(t->Val[0]);
 435         rel_use(t->Val[1]);
 436         t->Val[0] = t->Val[1] = (FSM_use *) 0;
 437         t->nxt = trans_free;
 438         trans_free = t;
 439 }
 440
 441 static void
 442 rel_state(FSM_state *f)
 443 {
 444         if (!f) return;
 445         rel_state(f->nxt);
 446         rel_trans(f->t);
 447         f->t = (FSM_trans *) 0;
 448         f->nxt = fsm_free;
 449         fsm_free = f;
 450 }
 451
 452 static void
 453 FSM_DEL(void)
 454 {
 455         rel_state(fsm);
 456         fsm = (FSM_state *) 0;
 457 }
 458
 459 static FSM_state *
 460 mkstate(int s)
 461 {       FSM_state *f;
 462
 463         /* fsm_tbl isn't allocated yet */
 464         for (f = fsm; f; f = f->nxt)
 465                 if (f->from == s)
 466                         break;
 467         if (!f)
 468         {       if (fsm_free)
 469                 {       f = fsm_free;
 470                         memset(f, 0, sizeof(FSM_state));
 471                         fsm_free = fsm_free->nxt;
 472                 } else
 473                         f = (FSM_state *) emalloc(sizeof(FSM_state));
 474                 f->from = s;
 475                 f->t = (FSM_trans *) 0;
 476                 f->nxt = fsm;
 477                 fsm = f;
 478                 if (s > max_st_id)
 479                         max_st_id = s;
 480         }
 481         return f;
 482 }
 483
 484 static FSM_trans *
 485 get_trans(int to)
 486 {       FSM_trans *t;
 487
 488         if (trans_free)
 489         {       t = trans_free;
 490                 memset(t, 0, sizeof(FSM_trans));
 491                 trans_free = trans_free->nxt;
 492         } else
 493                 t = (FSM_trans *) emalloc(sizeof(FSM_trans));
 494
 495         t->to = to;
 496         return t;
 497 }
 498
 499 static void
 500 FSM_EDGE(int from, int to, Element *e)
 501 {       FSM_state *f;
 502         FSM_trans *t;
 503
 504         f = mkstate(from);      /* find it or else make it */
 505         t = get_trans(to);
 506
 507         t->step = e;
 508         t->nxt = f->t;
 509         f->t = t;
 510
 511         f = mkstate(to);
 512         f->in++;
 513
 514         if (export_ast)
 515         {       t = get_trans(from);
 516                 t->step = e;
 517                 t->nxt = f->p;  /* from is a predecessor of to */
 518                 f->p = t;
 519         }
 520
 521         if (t->step)
 522                 ana_stmnt(t, t->step->n, 0);
 523 }
 524
 525 #define LVAL    1
 526 #define RVAL    0
 527
 528 static void
 529 ana_var(FSM_trans *t, Lextok *now, int usage)
 530 {       FSM_use *u, *v;
 531
 532         if (!t || !now || !now->sym)
 533                 return;
 534
 535         if (now->sym->name[0] == '_'
 536         &&  (strcmp(now->sym->name, "_") == 0
 537         ||   strcmp(now->sym->name, "_pid") == 0
 538         ||   strcmp(now->sym->name, "_priority") == 0
 539         ||   strcmp(now->sym->name, "_last") == 0))
 540                 return;
 541
 542         v = t->Val[usage];
 543         for (u = v; u; u = u->nxt)
 544                 if (u->var == now->sym)
 545                         return; /* it's already there */
 546
 547         if (!now->lft)
 548         {       /* not for array vars -- it's hard to tell statically
 549                    if the index would, at runtime, evaluate to the
 550                    same values at lval and rval references
 551                 */
 552                 if (use_free)
 553                 {       u = use_free;
 554                         use_free = use_free->nxt;
 555                 } else
 556                         u = (FSM_use *) emalloc(sizeof(FSM_use));
 557
 558                 u->var = now->sym;
 559                 u->nxt = t->Val[usage];
 560                 t->Val[usage] = u;
 561         } else
 562                  ana_stmnt(t, now->lft, RVAL);  /* index */
 563
 564         if (now->sym->type == STRUCT
 565         &&  now->rgt
 566         &&  now->rgt->lft)
 567                 ana_var(t, now->rgt->lft, usage);
 568 }
 569
 570 static void
 571 ana_stmnt(FSM_trans *t, Lextok *now, int usage)
 572 {       Lextok *v;
 573
 574         if (!t || !now) return;
 575
 576         switch (now->ntyp) {
 577         case '.':
 578         case BREAK:
 579         case GOTO:
 580         case CONST:
 581         case TIMEOUT:
 582         case NONPROGRESS:
 583         case  ELSE:
 584         case '@':
 585         case 'q':
 586         case IF:
 587         case DO:
 588         case ATOMIC:
 589         case NON_ATOMIC:
 590         case D_STEP:
 591         case C_CODE:
 592         case C_EXPR:
 593                 break;
 594
 595         case ',': /* reached with SET_P and array initializers */
 596                 if (now->lft && now->lft->rgt)
 597                 {       ana_stmnt(t, now->lft->rgt, RVAL);
 598                 }
 599                 break;
 600
 601         case '!':
 602         case UMIN:
 603         case '~':
 604         case ENABLED:
 605         case GET_P:
 606         case PC_VAL:
 607         case LEN:
 608         case FULL:
 609         case EMPTY:
 610         case NFULL:
 611         case NEMPTY:
 612         case ASSERT:
 613         case 'c':
 614                 ana_stmnt(t, now->lft, RVAL);
 615                 break;
 616
 617         case SET_P:
 618                 ana_stmnt(t, now->lft, RVAL); /* ',' */
 619                 ana_stmnt(t, now->lft->rgt, RVAL);
 620                 break;
 621
 622         case '/':
 623         case '*':
 624         case '-':
 625         case '+':
 626         case '%':
 627         case '&':
 628         case '^':
 629         case '|':
 630         case LT:
 631         case GT:
 632         case LE:
 633         case GE:
 634         case NE:
 635         case EQ:
 636         case OR:
 637         case AND:
 638         case LSHIFT:
 639         case RSHIFT:
 640                 ana_stmnt(t, now->lft, RVAL);
 641                 ana_stmnt(t, now->rgt, RVAL);
 642                 break;
 643
 644         case ASGN:
 645                 if (check_track(now) == STRUCT) { break; }
 646
 647                 ana_stmnt(t, now->lft, LVAL);
 648                 if (now->rgt->ntyp)
 649                         ana_stmnt(t, now->rgt, RVAL);
 650                 break;
 651
 652         case PRINT:
 653         case RUN:
 654                 for (v = now->lft; v; v = v->rgt)
 655                         ana_stmnt(t, v->lft, RVAL);
 656                 break;
 657
 658         case PRINTM:
 659                 if (now->lft && !now->lft->ismtyp)
 660                         ana_stmnt(t, now->lft, RVAL);
 661                 break;
 662
 663         case 's':
 664                 ana_stmnt(t, now->lft, RVAL);
 665                 for (v = now->rgt; v; v = v->rgt)
 666                         ana_stmnt(t, v->lft, RVAL);
 667                 break;
 668
 669         case 'R':
 670         case 'r':
 671                 ana_stmnt(t, now->lft, RVAL);
 672                 for (v = now->rgt; v; v = v->rgt)
 673                 {       if (v->lft->ntyp == EVAL)
 674                                 ana_stmnt(t, v->lft->lft, RVAL);
 675                         else
 676                         if (v->lft->ntyp != CONST
 677                         &&  now->ntyp != 'R')           /* was v->lft->ntyp */
 678                                 ana_stmnt(t, v->lft, LVAL);
 679                 }
 680                 break;
 681
 682         case '?':
 683                 ana_stmnt(t, now->lft, RVAL);
 684                 if (now->rgt)
 685                 {       ana_stmnt(t, now->rgt->lft, RVAL);
 686                         ana_stmnt(t, now->rgt->rgt, RVAL);
 687                 }
 688                 break;
 689
 690         case NAME:
 691                 ana_var(t, now, usage);
 692                 break;
 693
 694         case   'p':     /* remote ref */
 695                 ana_stmnt(t, now->lft->lft, RVAL);      /* process id */
 696                 ana_var(t, now, RVAL);
 697                 ana_var(t, now->rgt, RVAL);
 698                 break;
 699
 700         default:
 701                 printf("spin: %s:%d, bad node type %d (ana_stmnt)\n",
 702                         now->fn->name, now->ln, now->ntyp);
 703                 fatal("aborting", (char *) 0);
 704         }
 705 }
 706
 707 void
 708 ana_src(int dataflow, int merger)       /* called from main.c and guided.c */
 709 {       ProcList *p;
 710         Element *e;
 711 #if 0
 712         int counter = 1;
 713 #endif
 714         for (p = rdy; p; p = p->nxt)
 715         {
 716                 ana_seq(p->s);
 717                 fsm_table();
 718
 719                 e = p->s->frst;
 720 #if 0
 721                 if (dataflow || merger)
 722                 {       printf("spin: %d, optimizing '%s'",
 723                                 counter++, p->n->name);
 724                         fflush(stdout);
 725                 }
 726 #endif
 727                 if (dataflow)
 728                 {       FSM_ANA();
 729                 }
 730                 if (merger)
 731                 {       FSM_MERGER(/* p->n->name */);
 732                         huntele(e, e->status, -1)->merge_in = 1; /* start-state */
 733 #if 0
 734                         printf("\n");
 735 #endif
 736                 }
 737                 if (export_ast)
 738                         AST_store(p, huntele(e, e->status, -1)->seqno);
 739
 740                 FSM_DEL();
 741         }
 742         for (e = Al_El; e; e = e->Nxt)
 743         {
 744                 if (!(e->status&DONE) && (verbose&32))
 745                 {       printf("unreachable code: ");
 746                         printf("%s:%3d  ", e->n->fn->name, e->n->ln);
 747                         comment(stdout, e->n, 0);
 748                         printf("\n");
 749                 }
 750                 e->status &= ~DONE;
 751         }
 752         if (export_ast)
 753         {       AST_slice();
 754                 alldone(0);     /* changed in 5.3.0: was exit(0) */
 755         }
 756 }
 757
 758 void
 759 spit_recvs(FILE *f1, FILE *f2)  /* called from pangen2.c */
 760 {       Element *e;
 761         Sequence *s;
 762         extern int Unique;
 763
 764         fprintf(f1, "unsigned char Is_Recv[%d];\n", Unique);
 765
 766         fprintf(f2, "void\nset_recvs(void)\n{\n");
 767         for (e = Al_El; e; e = e->Nxt)
 768         {       if (!e->n) continue;
 769
 770                 switch (e->n->ntyp) {
 771                 case 'r':
 772 markit:                 fprintf(f2, "\tIs_Recv[%d] = 1;\n", e->Seqno);
 773                         break;
 774                 case D_STEP:
 775                         s = e->n->sl->this;
 776                         switch (s->frst->n->ntyp) {
 777                         case DO:
 778                                 fatal("unexpected: do at start of d_step", (char *) 0);
 779                         case IF: /* conservative: fall through */
 780                         case 'r': goto markit;
 781                         }
 782                         break;
 783                 }
 784         }
 785         fprintf(f2, "}\n");
 786
 787         if (rvopt)
 788         {
 789         fprintf(f2, "int\nno_recvs(int me)\n{\n");
 790         fprintf(f2, "   int h; uchar ot; short tt;\n");
 791         fprintf(f2, "   Trans *t;\n");
 792         fprintf(f2, "   for (h = BASE; h < (int) now._nr_pr; h++)\n");
 793         fprintf(f2, "   {       if (h == me) continue;\n");
 794         fprintf(f2, "           tt = (short) ((P0 *)pptr(h))->_p;\n");
 795         fprintf(f2, "           ot = (uchar) ((P0 *)pptr(h))->_t;\n");
 796         fprintf(f2, "           for (t = trans[ot][tt]; t; t = t->nxt)\n");
 797         fprintf(f2, "                   if (Is_Recv[t->t_id]) return 0;\n");
 798         fprintf(f2, "   }\n");
 799         fprintf(f2, "   return 1;\n");
 800         fprintf(f2, "}\n");
 801         }
 802 }
 803
 804 static void
 805 ana_seq(Sequence *s)
 806 {       SeqList *h;
 807         Sequence *t;
 808         Element *e, *g;
 809         int From, To;
 810
 811         for (e = s->frst; e; e = e->nxt)
 812         {       if (e->status & DONE)
 813                         goto checklast;
 814
 815                 e->status |= DONE;
 816
 817                 From = e->seqno;
 818
 819                 if (e->n->ntyp == UNLESS)
 820                         ana_seq(e->sub->this);
 821                 else if (e->sub)
 822                 {       for (h = e->sub; h; h = h->nxt)
 823                         {       g = huntstart(h->this->frst);
 824                                 To = g->seqno;
 825
 826                                 if (g->n->ntyp != 'c'
 827                                 ||  g->n->lft->ntyp != CONST
 828                                 ||  g->n->lft->val != 0
 829                                 ||  g->esc)
 830                                         FSM_EDGE(From, To, e);
 831                                 /* else it's a dead link */
 832                         }
 833                         for (h = e->sub; h; h = h->nxt)
 834                                 ana_seq(h->this);
 835                 } else if (e->n->ntyp == ATOMIC
 836                         ||  e->n->ntyp == D_STEP
 837                         ||  e->n->ntyp == NON_ATOMIC)
 838                 {
 839                         t = e->n->sl->this;
 840                         g = huntstart(t->frst);
 841                         t->last->nxt = e->nxt;
 842                         To = g->seqno;
 843                         FSM_EDGE(From, To, e);
 844
 845                         ana_seq(t);
 846                 } else
 847                 {       if (e->n->ntyp == GOTO)
 848                         {       g = get_lab(e->n, 1);
 849                                 g = huntele(g, e->status, -1);
 850                                 if (!g)
 851                                 {       fatal("unexpected error 2", (char *) 0);
 852                                 }
 853                                 To = g->seqno;
 854                         } else if (e->nxt)
 855                         {       g = huntele(e->nxt, e->status, -1);
 856                                 if (!g)
 857                                 {       fatal("unexpected error 3", (char *) 0);
 858                                 }
 859                                 To = g->seqno;
 860                         } else
 861                                 To = 0;
 862
 863                         FSM_EDGE(From, To, e);
 864
 865                         if (e->esc
 866                         &&  e->n->ntyp != GOTO
 867                         &&  e->n->ntyp != '.')
 868                         for (h = e->esc; h; h = h->nxt)
 869                         {       g = huntstart(h->this->frst);
 870                                 To = g->seqno;
 871                                 FSM_EDGE(From, To, ZE);
 872                                 ana_seq(h->this);
 873                         }
 874                 }
 875
 876 checklast:      if (e == s->last)
 877                         break;
 878         }
 879 }