optimize.c

来自「<B>Digital的Unix操作系统VAX 4.2源码</B>」· C语言 代码 · 共 1,806 行 · 第 1/3 页

			return;

		if ((*diffp)->val[A_REGNO] != val)
			break;

		diffp = &(*diffp)->jf;
		at_top = 0;
	}
	samep = &(*diffp)->jf;
	while (1) {
		if (*samep == 0)
			return;

		if ((*samep)->jt != b->jt)
			return;

		if (!NS_MEMBER((*samep)->dom, b->id))
			return;

		if ((*samep)->val[A_REGNO] == val)
			break;

		/* XXX Need to check that there are no data dependencies
		   between dp0 and dp1.  Currently, the code generator
		   will not produce such dependencies. */
		samep = &(*samep)->jf;
	}
#ifdef notdef
	/* XXX This doesn't cover everything. */
	for (i = 0; i < N_MEMWORDS; ++i)
		if ((*samep)->val[i] != pred->val[i])
			return;
#endif
	/* Pull up the node. */
	pull = *samep;
	*samep = pull->jf;
	pull->jf = *diffp;
	
	/*
	 * At the top of the chain, each predecessor needs to point at the
	 * pulled up node.  Inside the chain, there is only one predecessor
	 * to worry about.
	 */
	if (at_top) {
		for (plist = b->pred; plist; plist = plist->next) {
			if (plist->blk->jt == b)
				plist->blk->jt = pull;
			else
				plist->blk->jf = pull;
		}
	}
	else
		*diffp = pull;

	done = 0;
}
	
static void
and_pullup(b)
	struct block *b;
{
	int val, at_top;
	struct block *pull;
	struct block **diffp, **samep;
	struct blist *plist;

	plist = b->pred;
	if (plist == 0)
		return;

	/*
	 * Make sure each predecessor loads the same value.
	 */
	val = plist->blk->val[A_REGNO];
	for (plist = plist->next; plist; plist = plist->next)
		if (val != plist->blk->val[A_REGNO])
			return;

	if (b->pred->blk->jt == b)
		diffp = &b->pred->blk->jt;
	else
		diffp = &b->pred->blk->jf;

	at_top = 1;
	while (1) {
		if (*diffp == 0)
			return;

		if ((*diffp)->jf != b->jf)
			return;

		if (!NS_MEMBER((*diffp)->dom, b->id))
			return;

		if ((*diffp)->val[A_REGNO] != val)
			break;

		diffp = &(*diffp)->jt;
		at_top = 0;
	}
	samep = &(*diffp)->jt;
	while (1) {
		if (*samep == 0)
			return;

		if ((*samep)->jf != b->jf)
			return;

		if (!NS_MEMBER((*samep)->dom, b->id))
			return;

		if ((*samep)->val[A_REGNO] == val)
			break;

		/* XXX Need to check that there are no data dependencies
		   between dp0 and dp1.  Currently, the code generator
		   will not produce such dependencies. */
		samep = &(*samep)->jt;
	}
#ifdef notdef
	/* XXX This doesn't cover everything. */
	for (i = 0; i < N_MEMWORDS; ++i)
		if ((*samep)->val[i] != pred->val[i])
			return;
#endif
	/* Pull up the node. */
	pull = *samep;
	*samep = pull->jt;
	pull->jt = *diffp;
	
	/*
	 * At the top of the chain, each predecessor needs to point at the
	 * pulled up node.  Inside the chain, there is only one predecessor
	 * to worry about.
	 */
	if (at_top) {
		for (plist = b->pred; plist; plist = plist->next) {
			if (plist->blk->jt == b)
				plist->blk->jt = pull;
			else
				plist->blk->jf = pull;
		}
	}
	else
		*diffp = pull;

	done = 0;
}

static void
opt_blks(root, do_stmts)
	struct block *root;
{
	int i, maxlevel;
	struct block *p;

	init_val();
	maxlevel = root->level;
	for (i = maxlevel; i >= 0; --i)
		for (p = levels[i]; p; p = p->link)
			opt_blk(p, do_stmts);

	if (do_stmts)
		/* 
		 * No point trying to move branches; it can't possibly
		 * make a difference at this point.
		 */
		return;

	for (i = 1; i <= maxlevel; ++i) {
		for (p = levels[i]; p; p = p->link) {
			opt_j(p, 1);
			opt_j(p, 0);
		}
	}
	for (i = 1; i <= maxlevel; ++i)
		for (p = levels[i]; p; p = p->link) {
			or_pullup(p);
			and_pullup(p);
		}
}

static void
find_pred(root)
	struct block *root;
{
	int i;
	struct block *b;
	struct blist *list;

	next_blist = blist_base;

	for (i = 0; i < n_blocks; ++i)
		blocks[i]->pred = 0;

	/*
	 * Traverse the graph, adding each node to the predecessor
	 * list of its sucessors.  Skip the leaves (i.e. level 0).
	 */
	for (i = root->level; i > 0; --i) {
		for (b = levels[i]; b; b = b->link) {
			list = next_blist++;
			list->blk = b;
			list->next = b->jt->pred;
			b->jt->pred = list;
			list = next_blist++;
			list->blk = b;
			list->next = b->jf->pred;
			b->jf->pred = list;
		}
	}
}

static void
opt_root(b)
	struct block **b;
{
	while (BPF_ISJUMP((*b)->s.code) &&
	       (*b)->jt == (*b)->jf) {
		*b = (*b)->jt;
	}
}

static void
opt_loop(root, do_stmts)
	struct block *root;
	int do_stmts;
{
	do {
		done = 1;

		find_levels(root);
		find_dom(root);
		find_closure(root);
		find_pred(root);
		find_ud(root);

		opt_blks(root, do_stmts);

	} while (!done);
}

/*
 * Optimize the filter code in its dag representation.
 */
void
optimize(rootp)
	struct block **rootp;
{
	struct block *root;

	root = *rootp;

	opt_init(root);
	opt_loop(root, 0);
	opt_loop(root, 1);
	intern_blocks(root);
	opt_root(rootp);
	opt_cleanup();
}

static void
make_marks(p)
	struct block *p;
{
	if (!isMarked(p)) {
		Mark(p);
		if (!BPF_ISLEAF(p->s.code)) {
			make_marks(p->jt);
			make_marks(p->jf);
		}
	}
}

/*
 * Mark code array such that isMarked(i) is true
 * only for nodes that are alive.
 */
static void
mark_code(p)
	struct block *p;
{
	cur_mark += 1;
	make_marks(p);
}

/*
 * True iff the two stmt lists load the same value from the packet into
 * the accumulator.
 */
static int
eq_slist(x, y)
	struct slist *x, *y;
{
	while (1) {
		while (x && x->s.code == NopOp)
			x = x->next;
		while (y && y->s.code == NopOp)
			y = y->next;
		if (x == 0)
			return y == 0;
		if (y == 0)
			return x == 0;
		if (x->s.code != y->s.code ||
		    x->s.k != y->s.k)
			return 0;
		x = x->next;
		y = y->next;
	}
}

static inline int
eq_blk(b0, b1)
	struct block *b0, *b1;
{
	if (b0->s.code == b1->s.code &&
	    b0->s.k == b1->s.k &&
	    b0->jt == b1->jt && b0->jf == b1->jf)
		return eq_slist(b0->stmts, b1->stmts);
	return 0;
}

static void
intern_blocks(root)
	struct block *root;
{
	struct block *p;
	int i, j;
	int done;
 top:
	done = 1;
	for (i = 0; i < n_blocks; ++i)
		blocks[i]->link = 0;

	mark_code(root);

	for (i = n_blocks - 1; --i >= 0; ) {
		if (!isMarked(blocks[i]))
			continue;
		for (j = i + 1; j < n_blocks; ++j) {
			if (!isMarked(blocks[j]))
				continue;
			if (eq_blk(blocks[i], blocks[j])) {
				blocks[i]->link = blocks[j]->link ?
					blocks[j]->link : blocks[j];
				break;
			}
		}
	}
	for (i = 0; i < n_blocks; ++i) {
		p = blocks[i];
		if (p->jt == 0)
			continue;
		if (p->jt->link) {
			done = 0;
			p->jt = p->jt->link;
		}
		if (p->jf->link) {
			done = 0;
			p->jf = p->jf->link;
		}
	}
	if (!done)
		goto top;
}

static void
opt_cleanup()
{
	free((void *)vnode_base);
	free((void *)vmap);
	free((void *)blist_base);
	free((void *)space);
	free((void *)levels);
	free((void *)blocks);
}

/*
 * Return the number of stmts in 's'.
 */
static int
slength(s)
	struct slist *s;
{
	int n = 0;

	for (; s; s = s->next)
		if (s->s.code != NopOp)
			++n;
	return n;
}

/*
 * Return the number of nodes reachable by 'p'.
 * All nodes should be initially unmarked.
 */
static int
count_blocks(p)
	struct block *p;
{
	if (p == 0 || isMarked(p))
		return 0;
	Mark(p);
	return count_blocks(p->jt) + count_blocks(p->jf) + 1;
}	

/*
 * Do a depth first search on the flow graph, numbering the
 * the basic blocks, and entering them into the 'blocks' array.`
 */
static void
number_blks_r(p)
	struct block *p;
{
	int n;

	if (p == 0 || isMarked(p))
		return;

	Mark(p);
	n = n_blocks++;
	p->id = n;
	blocks[n] = p;

	number_blks_r(p->jt);
	number_blks_r(p->jf);
}

/*
 * Return the number of stmts in the flowgraph reachable by 'p'.
 * The nodes should be unmarked before calling.
 */
static int
count_stmts(p)
	struct block *p;
{
	int n;

	if (p == 0 || isMarked(p))
		return 0;
	Mark(p);
	n = count_stmts(p->jt) + count_stmts(p->jf);
	return slength(p->stmts) + n + 1;
}

/*
 * Allocate memory.  All allocation is done before optimization
 * is begun.  A linear bound on the size of all data structures is computed
 * from the total number of blocks and/or statements.
 */
static void
opt_init(root)
	struct block *root;
{
	u_long *p;
	int i, n, max_stmts;

	/*
	 * First, count the blocks, so we can malloc an array to map
	 * block number to block.  Then, put the blocks into the array.
	 */
	unMarkAll();
	n = count_blocks(root);
	blocks = (struct block **)malloc(n * sizeof(*blocks));
	unMarkAll();
	n_blocks = 0;
	number_blks_r(root);

	/*
	 * The number of levels is bounded by the number of nodes.
	 */
	levels = (struct block **)malloc(n * sizeof(*levels));

	ns_nwords = n / (8 * sizeof(u_long)) + 1;
	space = (u_long *)malloc(2 * n * ns_nwords * sizeof(*space));
	p = space;
	all_dom_sets = p;
	for (i = 0; i < n; ++i) {
		blocks[i]->dom = p;
		p += ns_nwords;
	}
	all_closure_sets = p;
	for (i = 0; i < n; ++i) {
		blocks[i]->closure = p;
		p += ns_nwords;
	}
	/*
	 * At most, we can have E = 2N predecessors. 
	 * (E = num edges, N = num blocks)
	 */
	blist_base = (struct blist *)malloc(2 * n * sizeof(*blist_base));

	max_stmts = 0;
	for (i = 0; i < n; ++i)
		max_stmts += slength(blocks[i]->stmts) + 1;
	/*
	 * We allocate at most 3 value numbers per statement,
	 * so this is an upper bound on the number of valnodes
	 * we'll need.
	 */
	maxval = 3 * max_stmts;
	vmap = (struct vmapinfo *)malloc(maxval * sizeof(*vmap));
	vnode_base = (struct valnode *)malloc(maxval * sizeof(*vmap));
}

/*
 * Some pointers used to convert the basic block form of the code,
 * into the array form that BPF requires.  'fstart' will point to
 * the malloc'd array while 'ftail' is used during the recursive traversal.
 */
static struct bpf_insn *fstart;
static struct bpf_insn *ftail;

#ifdef BDEBUG
int bids[1000];
#endif

static void
convert_code_r(p)
	struct block *p;
{
	struct bpf_insn *dst;
	struct slist *src;
	int slen;
	u_int off;

	if (p == 0 || isMarked(p))
		return;
	Mark(p);

	convert_code_r(p->jf);
	convert_code_r(p->jt);

	slen = slength(p->stmts);
	dst = ftail -= slen + 1;

	p->offset = dst - fstart;

	for (src = p->stmts; src; src = src->next) {
		if (src->s.code == NopOp)
			continue;
		dst->code = (u_short)src->s.code;
		dst->k = src->s.k;
		++dst;
	}
#ifdef BDEBUG
	bids[dst - fstart] = p->id + 1;
#endif
	dst->code = (u_short)p->s.code;
	dst->k = p->s.k;
	if (p->jt) {
		off = p->jt->offset - (p->offset + slen);
		if (off >= 256) 
			error("long jumps not supported");
		dst->jt = off;
		off = p->jf->offset - (p->offset + slen);
		if (off >= 256) 
			error("long jumps not supported");
		dst->jf = off;
	}
}
	

/*
 * Convert flowgraph intermediate representation to the
 * BPF array representation.  Set *lenp to the number of instructions.
 */
struct bpf_insn *
icode_to_fcode(root, lenp)
	struct block *root;
	int *lenp;
{
	int n;
	struct bpf_insn *fp;
	
	unMarkAll();
	n = *lenp = count_stmts(root);

	fp = (struct bpf_insn *)malloc(sizeof(*fp) * n);
	bzero((char *)fp, sizeof(*fp) * n);
	fstart = fp;
	ftail = fp + n;

	unMarkAll();
	convert_code_r(root);

	return fp;
}

#ifdef BDEBUG
opt_dump(root)
	struct block *root;
{
	struct bpf_program f;
	
	f.bf_insns = icode_to_fcode(root, &f.bf_len);
	bpf_dump(&f, 1);
	putchar('\n');
	free((char *)f.bf_insns);
}
#endif