sys/src/cmd/spin/pangen5.c

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