pangen6.c

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

static void
AST_fp1(char *s, Lextok *t, Lextok *f, int parno)
{	Lextok *v;
	int cnt;

	if (!t) return;

	if (t->ntyp == RUN)
	{	if (strcmp(t->sym->name, s) == 0)
		for (v = t->lft, cnt = 1; v; v = v->rgt, cnt++)
			if (cnt == parno)
			{	AST_add_explicit(f, v->lft);
				break;
			}
	} else
	{	AST_fp1(s, t->lft, f, parno);
		AST_fp1(s, t->rgt, f, parno);
	}
}

static void
AST_mk1(char *s, Lextok *c, int parno)
{	AST *a;
	FSM_state *f;
	FSM_trans *t;

	/* concoct an extra FSM_trans *t with the asgn of
	 * formal par c to matching actual pars made explicit
	 */

	for (a = ast; a; a = a->nxt)		/* automata       */
	for (f = a->fsm; f; f = f->nxt)		/* control states */
	for (t = f->t; t; t = t->nxt)		/* transitions    */
	{	if (t->step)
		AST_fp1(s, t->step->n, c, parno);
	}
}

static void
AST_par_init(void)	/* parameter passing -- hidden assignments */
{	AST *a;
	Lextok *f, *t, *c;
	int cnt;

	for (a = ast; a; a = a->nxt)
	{	if (strcmp(a->p->n->name, ":never:") == 0
		||  strcmp(a->p->n->name, ":trace:") == 0
		||  strcmp(a->p->n->name, ":notrace:") == 0
		||  strcmp(a->p->n->name, ":init:") == 0)
			continue;			/* have no params */

		cnt = 0;
		for (f = a->p->p; f; f = f->rgt)	/* types */
		for (t = f->lft; t; t = t->rgt)		/* formals */
		{	cnt++;				/* formal par count */
			c = (t->ntyp != ',')? t : t->lft;	/* the formal parameter */
			AST_mk1(a->p->n->name, c, cnt);		/* all matching run statements */
	}	}
}

static void
AST_var_init(void)		/* initialized vars (not chans) - hidden assignments */
{	Ordered	*walk;
	Lextok *x;
	Symbol	*sp;
	AST *a;

	for (walk = all_names; walk; walk = walk->next)	
	{	sp = walk->entry;
		if (sp
		&&  !sp->context		/* globals */
		&&  sp->type != PROCTYPE
		&&  sp->ini
		&& (sp->type != MTYPE || sp->ini->ntyp != CONST) /* not mtype defs */
		&&  sp->ini->ntyp != CHAN)
		{	x = nn(ZN, TYPE, ZN, ZN);
			x->sym = sp;
			AST_add_explicit(x, sp->ini);
	}	}

	for (a = ast; a; a = a->nxt)
	{	if (strcmp(a->p->n->name, ":never:") != 0
		&&  strcmp(a->p->n->name, ":trace:") != 0
		&&  strcmp(a->p->n->name, ":notrace:") != 0)	/* claim has no locals */
		for (walk = all_names; walk; walk = walk->next)	
		{	sp = walk->entry;
			if (sp
			&&  sp->context
			&&  strcmp(sp->context->name, a->p->n->name) == 0
			&&  sp->Nid >= 0	/* not a param */
			&&  sp->type != LABEL
			&&  sp->ini
			&&  sp->ini->ntyp != CHAN)
			{	x = nn(ZN, TYPE, ZN, ZN);
				x->sym = sp;
				AST_add_explicit(x, sp->ini);
	}	}	}
}

static void
show_expl(void)
{	FSM_trans *t, *T;
	FSM_use *u;

	printf("\nExplicit List:\n");
	for (T = expl_par; T; T = (T == expl_par)?expl_var: (FSM_trans *) 0)
	{	for (t = T; t; t = t->nxt)
		{	if (!t->Val[0]) continue;
			printf("%s", t->relevant?"*":" ");
			printf("%3d", t->round);
			for (u = t->Val[0]; u; u = u->nxt)
			{	printf("\t<");
				AST_var(u->n, u->n->sym, 1);
				printf(":%d>, ", u->special);
			}
			printf("\n");
		}
		printf("==\n");
	}
	printf("End\n");
}

static void
AST_hidden(void)			/* reveal all hidden assignments */
{
	AST_par_init();
	expl_par = explicit;
	explicit = (FSM_trans *) 0;

	AST_var_init();
	expl_var = explicit;
	explicit = (FSM_trans *) 0;
}

#define BPW	(8*sizeof(ulong))			/* bits per word */

static int
bad_scratch(FSM_state *f, int upto)
{	FSM_trans *t;
#if 0
	1. all internal branch-points have else-s
	2. all non-branchpoints have non-blocking out-edge
	3. all internal edges are non-relevant
	subgraphs like this need NOT contribute control-dependencies
#endif

	if (!f->seen
	||  (f->scratch&4))
		return 0;

	if (f->scratch&8)
		return 1;

	f->scratch |= 4;

	if (verbose&32) printf("X[%d:%d:%d] ", f->from, upto, f->scratch);

	if (f->scratch&1)
	{	if (verbose&32)
			printf("\tbad scratch: %d\n", f->from);
bad:		f->scratch &= ~4;
	/*	f->scratch |=  8;	 wrong */
		return 1;
	}

	if (f->from != upto)
	for (t = f->t; t; t = t->nxt)
		if (bad_scratch(fsm_tbl[t->to], upto))
			goto bad;

	return 0;
}

static void
mark_subgraph(FSM_state *f, int upto)
{	FSM_trans *t;

	if (f->from == upto
	||  !f->seen
	||  (f->scratch&2))
		return;

	f->scratch |= 2;

	for (t = f->t; t; t = t->nxt)
		mark_subgraph(fsm_tbl[t->to], upto);
}

static void
AST_pair(AST *a, FSM_state *h, int y)
{	Pair *p;

	for (p = a->pairs; p; p = p->nxt)
		if (p->h == h
		&&  p->b == y)
			return;

	p = (Pair *) emalloc(sizeof(Pair));
	p->h = h;
	p->b = y;
	p->nxt = a->pairs;
	a->pairs = p;
}

static void
AST_checkpairs(AST *a)
{	Pair *p;

	for (p = a->pairs; p; p = p->nxt)
	{	if (verbose&32)
			printf("	inspect pair %d %d\n", p->b, p->h->from);
		if (!bad_scratch(p->h, p->b))	/* subgraph is clean */
		{	if (verbose&32)
				printf("subgraph: %d .. %d\n", p->b, p->h->from);
			mark_subgraph(p->h, p->b);
		}
	}
}

static void
subgraph(AST *a, FSM_state *f, int out)
{	FSM_state *h;
	int i, j;
	ulong *g;
#if 0
	reverse dominance suggests that this is a possible
	entry and exit node for a proper subgraph
#endif
	h = fsm_tbl[out];

	i = f->from / BPW;
	j = f->from % BPW;
	g = h->mod;

	if (verbose&32)
		printf("possible pair %d %d -- %d\n",
			f->from, h->from, (g[i]&(1<<j))?1:0);
	
	if (g[i]&(1<<j))		/* also a forward dominance pair */
		AST_pair(a, h, f->from);	/* record this pair */
}

static void
act_dom(AST *a)
{	FSM_state *f;
	FSM_trans *t;
	int i, j, cnt;

	for (f = a->fsm; f; f = f->nxt)
	{	if (!f->seen) continue;
#if 0
		f->from is the exit-node of a proper subgraph, with
		the dominator its entry-node, if:
		a. this node has more than 1 reachable predecessor
		b. the dominator has more than 1 reachable successor
		   (need reachability - in case of reverse dominance)
		d. the dominator is reachable, and not equal to this node
#endif
		for (t = f->p, i = 0; t; t = t->nxt)
			i += fsm_tbl[t->to]->seen;
		if (i <= 1) continue;					/* a. */

		for (cnt = 1; cnt < a->nstates; cnt++)	/* 0 is endstate */
		{	if (cnt == f->from
			||  !fsm_tbl[cnt]->seen)
				continue;				/* c. */

			i = cnt / BPW;
			j = cnt % BPW;
			if (!(f->dom[i]&(1<<j)))
				continue;

			for (t = fsm_tbl[cnt]->t, i = 0; t; t = t->nxt)
				i += fsm_tbl[t->to]->seen;
			if (i <= 1)
				continue;				/* b. */

			if (f->mod)			/* final check in 2nd phase */
				subgraph(a, f, cnt);	/* possible entry-exit pair */
		}
	}
}

static void
reachability(AST *a)
{	FSM_state *f;

	for (f = a->fsm; f; f = f->nxt)
		f->seen = 0;		/* clear */
	AST_dfs(a, a->i_st, 0);		/* mark 'seen' */
}

static int
see_else(FSM_state *f)
{	FSM_trans *t;

	for (t = f->t; t; t = t->nxt)
	{	if (t->step
		&&  t->step->n)
		switch (t->step->n->ntyp) {
		case ELSE:
			return 1;
		case IF:
		case DO:
		case ATOMIC:
		case NON_ATOMIC:
		case D_STEP:
			if (see_else(fsm_tbl[t->to]))
				return 1;
		default:
			break;
		}
	}
	return 0;
}

static int
is_guard(FSM_state *f)
{	FSM_state *g;
	FSM_trans *t;

	for (t = f->p; t; t = t->nxt)
	{	g = fsm_tbl[t->to];
		if (!g->seen)
			continue;

		if (t->step
		&&  t->step->n)
		switch(t->step->n->ntyp) {
		case IF:
		case DO:
			return 1;
		case ATOMIC:
		case NON_ATOMIC:
		case D_STEP:
			if (is_guard(g))
				return 1;
		default:
			break;
		}
	}
	return 0;
}

static void
curtail(AST *a)
{	FSM_state *f, *g;
	FSM_trans *t;
	int i, haselse, isrel, blocking;
#if 0
	mark nodes that do not satisfy these requirements:
	1. all internal branch-points have else-s
	2. all non-branchpoints have non-blocking out-edge
	3. all internal edges are non-data-relevant
#endif
	if (verbose&32)
		printf("Curtail %s:\n", a->p->n->name);

	for (f = a->fsm; f; f = f->nxt)
	{	if (!f->seen
		||  (f->scratch&(1|2)))
			continue;

		isrel = haselse = i = blocking = 0;

		for (t = f->t; t; t = t->nxt)
		{	g = fsm_tbl[t->to];

			isrel |= (t->relevant&1);	/* data relevant */
			i += g->seen;

			if (t->step
			&&  t->step->n)
			{	switch (t->step->n->ntyp) {
				case IF:
				case DO:
					haselse |= see_else(g);
					break;
				case 'c':
				case 's':
				case 'r':
					blocking = 1;
					break;
		}	}	}
#if 0
		if (verbose&32)
			printf("prescratch %d -- %d %d %d %d -- %d\n",
				f->from, i, isrel, blocking, haselse, is_guard(f));
#endif
		if (isrel			/* 3. */		
		||  (i == 1 && blocking)	/* 2. */
		||  (i >  1 && !haselse))	/* 1. */
		{	if (!is_guard(f))
			{	f->scratch |= 1;
				if (verbose&32)
				printf("scratch %d -- %d %d %d %d\n",
					f->from, i, isrel, blocking, haselse);
			}
		}
	}
}

static void
init_dom(AST *a)
{	FSM_state *f;
	int i, j, cnt;
#if 0
	(1)  D(s0) = {s0}
	(2)  for s in S - {s0} do D(s) = S
#endif

	for (f = a->fsm; f; f = f->nxt)
	{	if (!f->seen) continue;

		f->dom = (ulong *)
			emalloc(a->nwords * sizeof(ulong));

		if (f->from == a->i_st)
		{	i = a->i_st / BPW;
			j = a->i_st % BPW;
			f->dom[i] = (1<<j);			/* (1) */
		} else						/* (2) */
		{	for (i = 0; i < a->nwords; i++)
				f->dom[i] = (ulong) ~0;			/* all 1's */

			if (a->nstates % BPW)
			for (i = a->nstates % BPW; i < BPW; i++)
				f->dom[a->nwords-1] &= ~(1<<i);	/* clear tail */

			for (cnt = 0; cnt < a->nstates; cnt++)
				if (!fsm_tbl[cnt]->seen)
				{	i = cnt / BPW;
					j = cnt % BPW;
					f->dom[i] &= ~(1<<j);
	}	}		}
}

static int
dom_perculate(AST *a, FSM_state *f)
{	static ulong *ndom = (ulong *) 0;
	static int on = 0;
	int i, j, cnt = 0;
	FSM_state *g;
	FSM_trans *t;

	if (on < a->nwords)
	{	on = a->nwords;
		ndom = (ulong *)
			emalloc(on * sizeof(ulong));
	}

	for (i = 0; i < a->nwords; i++)
		ndom[i] = (ulong) ~0;

	for (t = f->p; t; t = t->nxt)	/* all reachable predecessors */
	{	g = fsm_tbl[t->to];
		if (g->seen)
		for (i = 0; i < a->nwords; i++)
			ndom[i] &= g->dom[i];	/* (5b) */
	}

	i = f->from / BPW;
	j = f->from % BPW;
	ndom[i] |= (1<<j);			/* (5a) */

	for (i = 0; i < a->nwords; i++)
		if (f->dom[i] != ndom[i])
		{	cnt++;
			f->dom[i] = ndom[i];
		}

	return cnt;
}

static void
dom_forward(AST *a)
{	FSM_state *f;
	int cnt;

	init_dom(a);						/* (1,2) */
	do {
		cnt = 0;
		for (f = a->fsm; f; f = f->nxt)
		{	if (f->seen
			&&  f->from != a->i_st)			/* (4) */
				cnt += dom_perculate(a, f);	/* (5) */
		}
	} while (cnt);						/* (3) */
	dom_perculate(a, fsm_tbl[a->i_st]);
}

static void
AST_dominant(void)
{	FSM_state *f;
	FSM_trans *t;
	AST *a;
	int oi;
#if 0
	find dominators
	Aho, Sethi, & Ullman, Compilers - principles, techniques, and tools
	Addison-Wesley, 1986, p.671.

	(1)  D(s0) = {s0}
	(2)  for s in S - {s0} do D(s) = S

	(3)  while any D(s) changes do
	(4)    for s in S - {s0} do
	(5)	D(s) = {s} union  with intersection of all D(p)
		where p are the immediate predecessors of s

	the purpose is to find proper subgraphs
	(one entry node, one exit node)
#endif
	if (AST_Round == 1)	/* computed once, reused in every round */
	for (a = ast; a; a = a->nxt)
	{	a->nstates = 0;
		for (f = a->fsm; f; f = f->nxt)
		{	a->nstates++;				/* count */
			fsm_tbl[f->from] = f;			/* fast lookup */
			f->scratch = 0;				/* clear scratch marks */
		}
		for (oi = 0; oi < a->nstates; oi++)
			if (!fsm_tbl[oi])
				fsm_tbl[oi] = &no_state;

		a->nwords = (a->nstates + BPW - 1) / BPW;	/* round up */

		if (verbose&32)
		{	printf("%s (%d): ", a->p->n->name, a->i_st);
			printf("states=%d (max %d), words = %d, bpw %d, overflow %d\n",
				a->nstates, o_max, a->nwords,
				(int) BPW, (int) (a->nstates % BPW));
		}

		reachability(a);
		dom_forward(a);		/* forward dominance relation */

		curtail(a);		/* mark ineligible edges */
		for (f = a->fsm; f; f = f->nxt)
		{	t = f->p;
			f->p = f->t;
			f->t = t;	/* invert edges */

			f->mod = f->dom;
			f->dom = (ulong *) 0;
		}
		oi = a->i_st;
		if (fsm_tbl[0]->seen)	/* end-state reachable - else leave it */
			a->i_st = 0;	/* becomes initial state */
	
		dom_forward(a);		/* reverse dominance -- don't redo reachability! */
		act_dom(a);		/* mark proper subgraphs, if any */
		AST_checkpairs(a);	/* selectively place 2 scratch-marks */

		for (f = a->fsm; f; f = f->nxt)
		{	t = f->p;
			f->p = f->t;
			f->t = t;	/* restore */
		}
		a->i_st = oi;	/* restore */
	} else
		for (a = ast; a; a = a->nxt)
		{	for (f = a->fsm; f; f = f->nxt)
			{	fsm_tbl[f->from] = f;
				f->scratch &= 1; /* preserve 1-marks */
			}
			for (oi = 0; oi < a->nstates; oi++)
				if (!fsm_tbl[oi])
					fsm_tbl[oi] = &no_state;

			curtail(a);		/* mark ineligible edges */

			for (f = a->fsm; f; f = f->nxt)
			{	t = f->p;
				f->p = f->t;
				f->t = t;	/* invert edges */
			}
	
			AST_checkpairs(a);	/* recompute 2-marks */

			for (f = a->fsm; f; f = f->nxt)
			{	t = f->p;
				f->p = f->t;
				f->t = t;	/* restore */
		}	}
}