optimize.c

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

/*
 * Copyright (c) 1988-1990 The Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that: (1) source code distributions
 * retain the above copyright notice and this paragraph in its entirety, (2)
 * distributions including binary code include the above copyright notice and
 * this paragraph in its entirety in the documentation or other materials
 * provided with the distribution, and (3) all advertising materials mentioning
 * features or use of this software display the following acknowledgement:
 * ``This product includes software developed by the University of California,
 * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
 * the University nor the names of its contributors may be used to endorse
 * or promote products derived from this software without specific prior
 * written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 *  Optimization module for tcpdump intermeddiate representation.
 *
 * SCCSID: @(#)optimize.c	4.2	ULTRIX	1/25/91
 * Based on:
 * rcsid[] = "@(#) $Header: optimize.c,v 1.25 91/01/07 16:03:21 mccanne Exp $ (LBL)"
 */

#include <stdio.h>
#include <sys/types.h>

#include <sys/time.h>
#include <net/bpf.h>

#include "interface.h"
#include "gencode.h"

#define A_REGNO BPF_MEMWORDS
#define X_REGNO (BPF_MEMWORDS+1)

/*
 * This define is used to represent *both* the accumulator and
 * x register in use-def computations.
 * Currently, the use-def code assumes only one definition per instruction.
 */
#define AX_REGNO N_MEMWORDS

/*
 * A flag to indicate that further optimization is needed.
 * Iterative passes are continued until a given pass yields no 
 * branch movement.
 */
static int done;

/*
 * A block is marked if only if its mark equals the current mark.
 * Rather than traverse the code array, marking each item, 'cur_mark' is
 * incremented.  This automatically makes each element unmarked.
 */
static int cur_mark;
#define isMarked(p) ((p)->mark == cur_mark)
#define unMarkAll() cur_mark += 1
#define Mark(p) ((p)->mark = cur_mark)

static void opt_init();
static void opt_cleanup();

static void make_marks();
static void mark_code();

static void intern_blocks();

static int eq_slist();

static int n_blocks;
struct block **blocks;

/*
 * A bit vector set representation of the dominators.  
 * We round up the set size to the next power of two.  
 */
static int ns_nwords;
struct block **levels;
u_long *space;
#define BITS_PER_WORD (8*sizeof(u_long))
/*
 * True if a is in nodeset {p}
 */
#define NS_MEMBER(p, a) \
((p)[(unsigned)(a) / BITS_PER_WORD] & (1 << ((unsigned)(a) % BITS_PER_WORD)))

/*
 * Add 'a' to nodeset p.
 */
#define NS_INSERT(p, a) \
(p)[(unsigned)(a) / BITS_PER_WORD] |= (1 << ((unsigned)(a) % BITS_PER_WORD))

/*
 * Delete 'a' from nodeset p.
 */
#define NS_DELETE(p, a) \
(p)[(unsigned)(a) / BITS_PER_WORD] &= ~(1 << ((unsigned)(a) % BITS_PER_WORD))

/*
 * a := a intersect b
 */
#define NS_INTERSECT(a, b)\
{\
	u_long *_x = a, *_y = b;\
	int _n = ns_nwords;\
	while (--_n >= 0) *_x++ &= *_y++;\
}

/*
 * a := a union b
 */
#define NS_UNION(a, b)\
{\
	u_long *_x = a, *_y = b;\
	int _n = ns_nwords;\
	while (--_n >= 0) *_x++ |= *_y++;\
}

static nodeset all_dom_sets;
static nodeset all_closure_sets;

#define MAX(a,b) ((a)>(b)?(a):(b))

static void
find_levels_r(b)
	struct block *b;
{
	int level;

	if (isMarked(b))
		return;

	Mark(b);
	b->link = 0;

	if (b->jt) {
		find_levels_r(b->jt);
		find_levels_r(b->jf);
		level = MAX(b->jt->level, b->jf->level) + 1;
	} else
		level = 0;
	b->level = level;
	b->link = levels[level];
	levels[level] = b;
}

/*
 * Level graph.  The levels go from 0 at the leaves to 
 * N_LEVELS at the root.  The levels[] array points to the
 * first node of the level list, whose elements are linked
 * with the 'link' field of the struct block.
 */
static void
find_levels(root)
	struct block *root;
{
	bzero((char *)levels, n_blocks * sizeof(*levels));
	unMarkAll();
	find_levels_r(root);
}

/* 
 * Find dominator relationships.
 * Assumes graph has been leveled.
 */
static void
find_dom(root)
	struct block *root;
{
	int i;
	struct block *b;
	u_long *x;

	/*
	 * Initialize sets to contain all nodes.
	 */
	x = all_dom_sets;
	i = n_blocks * ns_nwords;
	while (--i >= 0)
		*x++ = ~0;
	/* Root starts off empty. */
	for (i = ns_nwords; --i >= 0;)
		root->dom[i] = 0;
	
	/* root->level is the highest level no found. */
	for (i = root->level; i >= 0; --i) {
		for (b = levels[i]; b; b = b->link) {
			NS_INSERT(b->dom, b->id);
			if (b->jt == 0)
				continue;
			NS_INTERSECT(b->jt->dom, b->dom);
			NS_INTERSECT(b->jf->dom, b->dom);
		}
	}
}

/* 
 * Find the backwards transitive closure of the flow graph.  These sets
 * are backwards in the sense that we find the set of nodes that reach
 * a given node, not the set of nodes that can be reached by a node.
 *
 * Assumes graph has been leveled.
 */
static void
find_closure(root)
	struct block *root;
{
	int i;
	struct block *b;

	/*
	 * Initialize sets to contain no nodes.
	 */
	bzero((char *)all_closure_sets, 
	      n_blocks * ns_nwords * sizeof(*all_closure_sets));
	
	/* root->level is the highest level no found. */
	for (i = root->level; i >= 0; --i) {
		for (b = levels[i]; b; b = b->link) {
			NS_INSERT(b->closure, b->id);
			if (b->jt == 0)
				continue;
			NS_UNION(b->jt->closure, b->closure);
			NS_UNION(b->jf->closure, b->closure);
		}
	}
}

/* 
 * Return the register number that is used by s.  If A and X are both
 * used, return AX_REGNO.  If no register is used, return -1.
 * 
 * The implementation should probably change to an array access, and
 * and a special case for trx and tra.
 */
static int
reguse(s)
	struct stmt *s;
{
	switch (s->code) {
	case GEOp:
	case GTOp:
	case EQOp:
	case AddIOp:
	case SubIOp:
	case MulIOp:
	case DivIOp:
	case AndIOp:
	case OrIOp:
	case LshIOp:
	case RshIOp:
	case NegOp:
	case TaxOp:
	case StmOp:
	case RetAOp:
		return A_REGNO;

	case LdOp:
	case LdHOp:
	case LdBOp:
	case LdLenOp:
	case LdIOp:
	case LdXIOp:
	case LdxmsOp:
	case NopOp:
	case RetOp:
		return -1;

	case ILdOp:
	case ILdHOp:
	case ILdBOp:
	case TxaOp:
	case StmXOp:
		return X_REGNO;

	case AddXOp:
	case SubXOp:
	case MulXOp:
	case DivXOp:
	case AndXOp:
	case OrXOp:
	case LshXOp:
	case RshXOp:
		return AX_REGNO;

	case LdmOp:
	case LdmXOp:
		return s->k;
	}
	abort();
	/* NOTREACHED */
}

/* 
 * Return the register number that is defined by 's'.  We assume that
 * a single stmt cannot define more than one register.  If no register
 * is defined, return -1.
 *
 * The implementation should probably change to an array access, and
 * and a special case for txr and tar.
 */
static int
regdef(s)
	struct stmt *s;
{
	switch (s->code) {
	case GEOp:
	case GTOp:
	case EQOp:
	case NopOp:
	case RetOp:
	case RetAOp:
		return -1;

	case LdOp:
	case LdHOp:
	case LdBOp:
	case LdLenOp:
	case LdIOp:
	case ILdOp:
	case ILdHOp:
	case ILdBOp:
	case AddIOp:
	case SubIOp:
	case MulIOp:
	case DivIOp:
	case AndIOp:
	case OrIOp:
	case LshIOp:
	case RshIOp:
	case NegOp:
	case AddXOp:
	case SubXOp:
	case MulXOp:
	case DivXOp:
	case AndXOp:
	case OrXOp:
	case LshXOp:
	case RshXOp:
	case TxaOp:
	case LdmOp:
		return A_REGNO;

	case LdXIOp:
	case LdxmsOp:
	case TaxOp:
	case LdmXOp:
		return X_REGNO;

	case StmOp:
	case StmXOp:
		return s->k;
	}
	abort();
	/* NOTREACHED */
}

static void
compute_local_ud(b)
	struct block *b;
{
	struct slist *s;
	regset def = 0, use = 0;
	int regno;

	for (s = b->stmts; s; s = s->next) {
		regno = reguse(&s->s);
		if (regno >= 0) {
			if (regno == AX_REGNO) {
				if (!REGELEM(def, X_REGNO))
					use |= REGMASK(X_REGNO);
				if (!REGELEM(def, A_REGNO))
					use |= REGMASK(A_REGNO);
			}
			else if (regno < N_MEMWORDS) {
				if (!REGELEM(def, regno))
					use |= REGMASK(regno);
			}
			else
				abort();
		}
		regno = regdef(&s->s);
		if (regno >= 0)
			def |= REGMASK(regno);
	}
	if (!REGELEM(def, A_REGNO) && BPF_ISJUMP(b->s.code))
		use |= REGMASK(A_REGNO);
		
	b->def = def;
	b->in_use = use;
}

/*
 * Assume graph is already leveled.
 */
static void
find_ud(root)
	struct block *root;
{
	int i, maxlevel;
	struct block *p;

	/*
	 * root->level is the highest level no found;
	 * count down from there.
	 */
	maxlevel = root->level;
	for (i = maxlevel; i >= 0; --i)
		for (p = levels[i]; p; p = p->link) {
			compute_local_ud(p);
			p->out_use = 0;
		}

	for (i = 1; i <= maxlevel; ++i) {
		for (p = levels[i]; p; p = p->link) {
			p->out_use |= p->jt->in_use | p->jf->in_use;
			p->in_use |= p->out_use;
		}
	}
}

/* 
 * These data structures used in a Cocke and Shwarz style
 * value numbering scheme.  Since the flowgraph is acyclic,
 * exit values can be propagated from a node's predecessors
 * provided it is uniquely defined.
 */
struct valnode {
	enum bpf_code code;
	long v0, v1;
	long val;
	struct valnode *next;
};
	
#define MODULUS 213
static struct valnode *hashtbl[MODULUS];
static int curval;
static int maxval;

/* Integer constants mapped with the LdIOp opcode. */
#define K(i) F(LdIOp, i, 0L)

struct vmapinfo {
	int is_const;
	long const_val;
};

struct vmapinfo *vmap;
struct valnode *vnode_base;
struct valnode *next_vnode;

static void
init_val()
{
	curval = 0;
	next_vnode = vnode_base;
	bzero((char *)vmap, maxval * sizeof(*vmap));
	bzero((char *)hashtbl, sizeof hashtbl);
}

/* Because we really don't have an IR, this stuff is a little messy. */
static long
F(code, v0, v1)
	enum bpf_code code;
	long v0, v1;
{
	u_int hash;
	int val;
	struct valnode *p;

	hash = (u_int)code ^ (v0 << 4) ^ (v1 << 8);
	hash %= MODULUS;

	for (p = hashtbl[hash]; p; p = p->next)
		if (p->code == code && p->v0 == v0 && p->v1 == v1)
			return p->val;

	val = ++curval;
	if (code == LdIOp || code == LdXIOp) {
		vmap[val].const_val = v0;
		vmap[val].is_const = 1;
	}
	p = next_vnode++;
	p->val = val;
	p->code = code;
	p->v0 = v0;
	p->v1 = v1;
	p->next = hashtbl[hash];
	hashtbl[hash] = p;

	return val;
}

static inline void
vstore(s, valp, newval, alter)
	struct stmt *s;
	long *valp;
	long newval;
	int alter;
{
	if (alter && *valp == newval)
		s->code = NopOp;
	else
		*valp = newval;
}

static void
fold_op(s, v0, v1)
	struct stmt *s;
	long v0, v1;
{
	long a, b;

	a = vmap[v0].const_val;
	b = vmap[v1].const_val;

	switch (s->code) {
	case AddIOp:
	case AddXOp:
		a += b;
		break;

	case SubIOp:
	case SubXOp:
		a -= b;
		break;

	case MulIOp:
	case MulXOp:
		a *= b;
		break;

	case DivIOp:
	case DivXOp:
		if (b == 0)
			error("division by zero");
		a /= b;
		break;

	case AndIOp:
	case AndXOp:
		a &= b;
		break;

	case OrIOp:
	case OrXOp:
		a |= b;
		break;

	case LshIOp:
	case LshXOp:
		a <<= b;
		break;

	case RshIOp:
	case RshXOp:
		a >>= b;
		break;

	case NegOp:
		a = -a;
		break;

	default:
		abort();
	}
	s->k = a;
	s->code = LdIOp;
	done = 0;
}

static inline struct slist *
this_op(s)
	struct slist *s;
{
	while (s != 0 && s->s.code == NopOp)
		s = s->next;
	return s;
}

static void
opt_peep(b)
	struct block *b;
{
	struct slist *s;
	struct slist *next, *last;
	int val;
	long v;

	s = b->stmts;
	if (s == 0)
		return;

	last = s;
	while (1) {
		s = this_op(s);
		if (s == 0)
			break;