pangen5.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

{
	if (!t) return;
	rel_trans(t->nxt);
	rel_use(t->Val[0]);
	rel_use(t->Val[1]);
	t->Val[0] = t->Val[1] = (FSM_use *) 0;
	t->nxt = trans_free;
	trans_free = t;
}

static void
rel_state(FSM_state *f)
{
	if (!f) return;
	rel_state(f->nxt);
	rel_trans(f->t);
	f->t = (FSM_trans *) 0;
	f->nxt = fsm_free;
	fsm_free = f;
}

static void
FSM_DEL(void)
{
	rel_state(fsm);
	fsm = (FSM_state *) 0;
}

static FSM_state *
mkstate(int s)
{	FSM_state *f;

	/* fsm_tbl isn't allocated yet */
	for (f = fsm; f; f = f->nxt)
		if (f->from == s)
			break;
	if (!f)
	{	if (fsm_free)
		{	f = fsm_free;
			memset(f, 0, sizeof(FSM_state));
			fsm_free = fsm_free->nxt;
		} else
			f = (FSM_state *) emalloc(sizeof(FSM_state));
		f->from = s;
		f->t = (FSM_trans *) 0;
		f->nxt = fsm;
		fsm = f;
		if (s > max_st_id)
			max_st_id = s;
	}
	return f;
}

static FSM_trans *
get_trans(int to)
{	FSM_trans *t;

	if (trans_free)
	{	t = trans_free;
		memset(t, 0, sizeof(FSM_trans));
		trans_free = trans_free->nxt;
	} else
		t = (FSM_trans *) emalloc(sizeof(FSM_trans));

	t->to = to;
	return t;
}

static void
FSM_EDGE(int from, int to, Element *e)
{	FSM_state *f;
	FSM_trans *t;

	f = mkstate(from);	/* find it or else make it */
	t = get_trans(to);

	t->step = e;
	t->nxt = f->t;
	f->t = t;

	f = mkstate(to);
	f->in++;

	if (export_ast)
	{	t = get_trans(from);
		t->step = e;
		t->nxt = f->p;	/* from is a predecessor of to */
		f->p = t;
	}

	if (t->step)
		ana_stmnt(t, t->step->n, 0);
}

#define LVAL	1
#define RVAL	0

static void
ana_var(FSM_trans *t, Lextok *now, int usage)
{	FSM_use *u, *v;

	if (!t || !now || !now->sym)
		return;

	if (now->sym->name[0] == '_'
	&&  (strcmp(now->sym->name, "_") == 0
	||   strcmp(now->sym->name, "_pid") == 0
	||   strcmp(now->sym->name, "_last") == 0))
		return;

	v = t->Val[usage];
	for (u = v; u; u = u->nxt)
		if (u->var == now->sym)
			return;	/* it's already there */

	if (!now->lft)
	{	/* not for array vars -- it's hard to tell statically
		   if the index would, at runtime, evaluate to the
		   same values at lval and rval references
		*/
		if (use_free)
		{	u = use_free;
			use_free = use_free->nxt;
		} else
			u = (FSM_use *) emalloc(sizeof(FSM_use));
	
		u->var = now->sym;
		u->nxt = t->Val[usage];
		t->Val[usage] = u;
	} else
		 ana_stmnt(t, now->lft, RVAL);	/* index */

	if (now->sym->type == STRUCT
	&&  now->rgt
	&&  now->rgt->lft)
		ana_var(t, now->rgt->lft, usage);
}

static void
ana_stmnt(FSM_trans *t, Lextok *now, int usage)
{	Lextok *v;

	if (!t || !now) return;

	switch (now->ntyp) {
	case '.':
	case BREAK:
	case GOTO:
	case CONST:
	case TIMEOUT:
	case NONPROGRESS:
	case  ELSE:
	case '@':
	case 'q':
	case IF:
	case DO:
	case ATOMIC:
	case NON_ATOMIC:
	case D_STEP:
	case C_CODE:
	case C_EXPR:
		break;

	case '!':	
	case UMIN:
	case '~':
	case ENABLED:
	case PC_VAL:
	case LEN:
	case FULL:
	case EMPTY:
	case NFULL:
	case NEMPTY:
	case ASSERT:
	case 'c':
		ana_stmnt(t, now->lft, RVAL);
		break;

	case '/':
	case '*':
	case '-':
	case '+':
	case '%':
	case '&':
	case '^':
	case '|':
	case LT:
	case GT:
	case LE:
	case GE:
	case NE:
	case EQ:
	case OR:
	case AND:
	case LSHIFT:
	case RSHIFT:
		ana_stmnt(t, now->lft, RVAL);
		ana_stmnt(t, now->rgt, RVAL);
		break;

	case ASGN:
		ana_stmnt(t, now->lft, LVAL);
		ana_stmnt(t, now->rgt, RVAL);
		break;

	case PRINT:
	case RUN:
		for (v = now->lft; v; v = v->rgt)
			ana_stmnt(t, v->lft, RVAL);
		break;

	case PRINTM:
		if (now->lft && !now->lft->ismtyp)
			ana_stmnt(t, now->lft, RVAL);
		break;

	case 's':
		ana_stmnt(t, now->lft, RVAL);
		for (v = now->rgt; v; v = v->rgt)
			ana_stmnt(t, v->lft, RVAL);
		break;

	case 'R':
	case 'r':
		ana_stmnt(t, now->lft, RVAL);
		for (v = now->rgt; v; v = v->rgt)
		{	if (v->lft->ntyp == EVAL)
				ana_stmnt(t, v->lft->lft, RVAL);
			else
			if (v->lft->ntyp != CONST
			&&  now->ntyp != 'R')		/* was v->lft->ntyp */
				ana_stmnt(t, v->lft, LVAL);
		}
		break;

	case '?':
		ana_stmnt(t, now->lft, RVAL);
		if (now->rgt)
		{	ana_stmnt(t, now->rgt->lft, RVAL);
			ana_stmnt(t, now->rgt->rgt, RVAL);
		}
		break;

	case NAME:
		ana_var(t, now, usage);
		break;

	case   'p':	/* remote ref */
		ana_stmnt(t, now->lft->lft, RVAL);	/* process id */
		ana_var(t, now, RVAL);
		ana_var(t, now->rgt, RVAL);
		break;

	default:
		printf("spin: bad node type %d line %d (ana_stmnt)\n", now->ntyp, now->ln);
		fatal("aborting", (char *) 0);
	}
}

void
ana_src(int dataflow, int merger)	/* called from main.c and guided.c */
{	ProcList *p;
	Element *e;
#if 0
	int counter = 1;
#endif
	for (p = rdy; p; p = p->nxt)
	{	if (p->tn == eventmapnr
		||  p->tn == claimnr)
			continue;

		ana_seq(p->s);
		fsm_table();

		e = p->s->frst;
#if 0
		if (dataflow || merger)
		{	printf("spin: %d, optimizing '%s'",
				counter++, p->n->name);
			fflush(stdout);
		}
#endif
		if (dataflow)
		{	FSM_ANA();
		}
		if (merger)
		{	FSM_MERGER(p->n->name);
			huntele(e, e->status, -1)->merge_in = 1; /* start-state */
#if 0
			printf("\n");
#endif
		}
		if (export_ast)
			AST_store(p, huntele(e, e->status, -1)->seqno);

		FSM_DEL();
	}
	for (e = Al_El; e; e = e->Nxt)
	{
		if (!(e->status&DONE) && (verbose&32))
		{	printf("unreachable code: ");
			printf("%s, line %3d:  ",
				e->n->fn->name, e->n->ln);
			comment(stdout, e->n, 0);
			printf("\n");
		}
		e->status &= ~DONE;
	}
	if (export_ast)
	{	AST_slice();
		exit(0);
	}
}

void
spit_recvs(FILE *f1, FILE *f2)	/* called from pangen2.c */
{	Element *e;
	Sequence *s;
	extern int Unique;

	fprintf(f1, "unsigned char Is_Recv[%d];\n", Unique);

	fprintf(f2, "void\nset_recvs(void)\n{\n");
	for (e = Al_El; e; e = e->Nxt)
	{	if (!e->n) continue;

		switch (e->n->ntyp) {
		case 'r':
markit:			fprintf(f2, "\tIs_Recv[%d] = 1;\n", e->Seqno);
			break;
		case D_STEP:
			s = e->n->sl->this;
			switch (s->frst->n->ntyp) {
			case DO:
				fatal("unexpected: do at start of d_step", (char *) 0);
			case IF: /* conservative: fall through */
			case 'r': goto markit;
			}
			break;
		}
	}
	fprintf(f2, "}\n");

	if (rvopt)
	{
	fprintf(f2, "int\nno_recvs(int me)\n{\n");
	fprintf(f2, "	int h; uchar ot; short tt;\n");
	fprintf(f2, "	Trans *t;\n");
	fprintf(f2, "	for (h = BASE; h < (int) now._nr_pr; h++)\n");
	fprintf(f2, "	{	if (h == me) continue;\n");
	fprintf(f2, "		tt = (short) ((P0 *)pptr(h))->_p;\n");
	fprintf(f2, "		ot = (uchar) ((P0 *)pptr(h))->_t;\n");
	fprintf(f2, "		for (t = trans[ot][tt]; t; t = t->nxt)\n");
	fprintf(f2, "			if (Is_Recv[t->t_id]) return 0;\n");
	fprintf(f2, "	}\n");
	fprintf(f2, "	return 1;\n");
	fprintf(f2, "}\n");
	}
}

static void
ana_seq(Sequence *s)
{	SeqList *h;
	Sequence *t;
	Element *e, *g;
	int From, To;

	for (e = s->frst; e; e = e->nxt)
	{	if (e->status & DONE)
			goto checklast;

		e->status |= DONE;

		From = e->seqno;

		if (e->n->ntyp == UNLESS)
			ana_seq(e->sub->this);
		else if (e->sub)
		{	for (h = e->sub; h; h = h->nxt)
			{	g = huntstart(h->this->frst);
				To = g->seqno;

				if (g->n->ntyp != 'c'
				||  g->n->lft->ntyp != CONST
				||  g->n->lft->val != 0
				||  g->esc)
					FSM_EDGE(From, To, e);
				/* else it's a dead link */
			}
			for (h = e->sub; h; h = h->nxt)
				ana_seq(h->this);
		} else if (e->n->ntyp == ATOMIC
			||  e->n->ntyp == D_STEP
			||  e->n->ntyp == NON_ATOMIC)
		{
			t = e->n->sl->this;
			g = huntstart(t->frst);
			t->last->nxt = e->nxt;
			To = g->seqno;
			FSM_EDGE(From, To, e);

			ana_seq(t);
		} else 
		{	if (e->n->ntyp == GOTO)
			{	g = get_lab(e->n, 1);
				g = huntele(g, e->status, -1);
				To = g->seqno;
			} else if (e->nxt)
			{	g = huntele(e->nxt, e->status, -1);
				To = g->seqno;
			} else
				To = 0;

			FSM_EDGE(From, To, e);

			if (e->esc
			&&  e->n->ntyp != GOTO
			&&  e->n->ntyp != '.')
			for (h = e->esc; h; h = h->nxt)
			{	g = huntstart(h->this->frst);
				To = g->seqno;
				FSM_EDGE(From, To, ZE);
				ana_seq(h->this);
			}
		}

checklast:	if (e == s->last)
			break;
	}
}