optimize.c

该软件根据网络数据生成NetFlow记录。NetFlow可用于网络规划、负载均衡、安全监控等

/*
 * Copyright (c) 1988, 1989, 1990, 1991, 1993, 1994, 1995, 1996
 *	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 intermediate representation.
 */
#ifndef lint
static const char rcsid[] =
    "@(#) $Header: optimize.c,v 1.60 96/09/26 23:28:14 leres Exp $ (LBL)";
#endif

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

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#include "pcap-int.h"

#include "gencode.h"

#include "gnuc.h"
#ifdef HAVE_OS_PROTO_H
#include "os-proto.h"
#endif

#ifdef BDEBUG
extern int dflag;
#endif

#define A_ATOM BPF_MEMWORDS
#define X_ATOM (BPF_MEMWORDS+1)

#define NOP -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_ATOM N_ATOMS

/*
 * 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(struct block *);
static void opt_cleanup(void);

static void make_marks(struct block *);
static void mark_code(struct block *);

static void intern_blocks(struct block *);

static int eq_slist(struct slist *, struct slist *);

static void find_levels_r(struct block *);

static void find_levels(struct block *);
static void find_dom(struct block *);
static void propedom(struct edge *);
static void find_edom(struct block *);
static void find_closure(struct block *);
static int atomuse(struct stmt *);
static int atomdef(struct stmt *);
static void compute_local_ud(struct block *);
static void find_ud(struct block *);
static void init_val(void);
static int F(int, int, int);
static inline void vstore(struct stmt *, int *, int, int);
static void opt_blk(struct block *, int);
static int use_conflict(struct block *, struct block *);
static void opt_j(struct edge *);
static void or_pullup(struct block *);
static void and_pullup(struct block *);
static void opt_blks(struct block *, int);
static inline void link_inedge(struct edge *, struct block *);
static void find_inedges(struct block *);
static void opt_root(struct block **);
static void opt_loop(struct block *, int);
static void fold_op(struct stmt *, int, int);
static inline struct slist *this_op(struct slist *);
static void opt_not(struct block *);
static void opt_peep(struct block *);
static void opt_stmt(struct stmt *, int[], int);
static void deadstmt(struct stmt *, struct stmt *[]);
static void opt_deadstores(struct block *);
static void opt_blk(struct block *, int);
static int use_conflict(struct block *, struct block *);
static void opt_j(struct edge *);
static struct block *fold_edge(struct block *, struct edge *);
static inline int eq_blk(struct block *, struct block *);
static int slength(struct slist *);
static int count_blocks(struct block *);
static void number_blks_r(struct block *);
static int count_stmts(struct block *);
static int convert_code_r(struct block *);
#ifdef BDEBUG
static void opt_dump(struct block *);
#endif

static int n_blocks;
struct block **blocks;
static int n_edges;
struct edge **edges;

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

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

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

/*
 * a := a intersect b
 */
#define SET_INTERSECT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register int _n = n;\
	while (--_n >= 0) *_x++ &= *_y++;\
}

/*
 * a := a - b
 */
#define SET_SUBTRACT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register int _n = n;\
	while (--_n >= 0) *_x++ &=~ *_y++;\
}

/*
 * a := a union b
 */
#define SET_UNION(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register int _n = n;\
	while (--_n >= 0) *_x++ |= *_y++;\
}

static uset all_dom_sets;
static uset all_closure_sets;
static uset all_edge_sets;

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

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

	if (isMarked(b))
		return;

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

	if (JT(b)) {
		find_levels_r(JT(b));
		find_levels_r(JF(b));
		level = MAX(JT(b)->level, JF(b)->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;
{
	memset((char *)levels, 0, 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;
	bpf_u_int32 *x;

	/*
	 * Initialize sets to contain all nodes.
	 */
	x = all_dom_sets;
	i = n_blocks * nodewords;
	while (--i >= 0)
		*x++ = ~0;
	/* Root starts off empty. */
	for (i = nodewords; --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) {
			SET_INSERT(b->dom, b->id);
			if (JT(b) == 0)
				continue;
			SET_INTERSECT(JT(b)->dom, b->dom, nodewords);
			SET_INTERSECT(JF(b)->dom, b->dom, nodewords);
		}
	}
}

static void
propedom(ep)
	struct edge *ep;
{
	SET_INSERT(ep->edom, ep->id);
	if (ep->succ) {
		SET_INTERSECT(ep->succ->et.edom, ep->edom, edgewords);
		SET_INTERSECT(ep->succ->ef.edom, ep->edom, edgewords);
	}
}

/*
 * Compute edge dominators.
 * Assumes graph has been leveled and predecessors established.
 */
static void
find_edom(root)
	struct block *root;
{
	int i;
	uset x;
	struct block *b;

	x = all_edge_sets;
	for (i = n_edges * edgewords; --i >= 0; )
		x[i] = ~0;

	/* root->level is the highest level no found. */
	memset(root->et.edom, 0, edgewords * sizeof(*(uset)0));
	memset(root->ef.edom, 0, edgewords * sizeof(*(uset)0));
	for (i = root->level; i >= 0; --i) {
		for (b = levels[i]; b != 0; b = b->link) {
			propedom(&b->et);
			propedom(&b->ef);
		}
	}
}

/*
 * 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.
	 */
	memset((char *)all_closure_sets, 0,
	      n_blocks * nodewords * 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) {
			SET_INSERT(b->closure, b->id);
			if (JT(b) == 0)
				continue;
			SET_UNION(JT(b)->closure, b->closure, nodewords);
			SET_UNION(JF(b)->closure, b->closure, nodewords);
		}
	}
}

/*
 * Return the register number that is used by s.  If A and X are both
 * used, return AX_ATOM.  If no register is used, return -1.
 *
 * The implementation should probably change to an array access.
 */
static int
atomuse(s)
	struct stmt *s;
{
	register int c = s->code;

	if (c == NOP)
		return -1;

	switch (BPF_CLASS(c)) {

	case BPF_RET:
		return (BPF_RVAL(c) == BPF_A) ? A_ATOM :
			(BPF_RVAL(c) == BPF_X) ? X_ATOM : -1;

	case BPF_LD:
	case BPF_LDX:
		return (BPF_MODE(c) == BPF_IND) ? X_ATOM :
			(BPF_MODE(c) == BPF_MEM) ? s->k : -1;

	case BPF_ST:
		return A_ATOM;

	case BPF_STX:
		return X_ATOM;

	case BPF_JMP:
	case BPF_ALU:
		if (BPF_SRC(c) == BPF_X)
			return AX_ATOM;
		return A_ATOM;

	case BPF_MISC:
		return BPF_MISCOP(c) == BPF_TXA ? X_ATOM : A_ATOM;
	}
	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.
 */
static int
atomdef(s)
	struct stmt *s;
{
	if (s->code == NOP)
		return -1;

	switch (BPF_CLASS(s->code)) {

	case BPF_LD:
	case BPF_ALU:
		return A_ATOM;

	case BPF_LDX:
		return X_ATOM;

	case BPF_ST:
	case BPF_STX:
		return s->k;

	case BPF_MISC:
		return BPF_MISCOP(s->code) == BPF_TAX ? X_ATOM : A_ATOM;
	}
	return -1;
}

static void
compute_local_ud(b)
	struct block *b;
{
	struct slist *s;
	atomset def = 0, use = 0, kill = 0;
	int atom;

	for (s = b->stmts; s; s = s->next) {
		if (s->s.code == NOP)
			continue;
		atom = atomuse(&s->s);
		if (atom >= 0) {
			if (atom == AX_ATOM) {
				if (!ATOMELEM(def, X_ATOM))
					use |= ATOMMASK(X_ATOM);
				if (!ATOMELEM(def, A_ATOM))
					use |= ATOMMASK(A_ATOM);
			}
			else if (atom < N_ATOMS) {
				if (!ATOMELEM(def, atom))
					use |= ATOMMASK(atom);
			}
			else
				abort();
		}
		atom = atomdef(&s->s);
		if (atom >= 0) {
			if (!ATOMELEM(use, atom))
				kill |= ATOMMASK(atom);
			def |= ATOMMASK(atom);
		}
	}
	if (!ATOMELEM(def, A_ATOM) && BPF_CLASS(b->s.code) == BPF_JMP)
		use |= ATOMMASK(A_ATOM);

	b->def = def;
	b->kill = kill;
	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 |= JT(p)->in_use | JF(p)->in_use;
			p->in_use |= p->out_use &~ p->kill;
		}
	}
}

/*
 * These data structures are 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 {
	int code;
	int v0, v1;
	int val;
	struct valnode *next;
};

#define MODULUS 213
static struct valnode *hashtbl[MODULUS];
static int curval;
static int maxval;

/* Integer constants mapped with the load immediate opcode. */
#define K(i) F(BPF_LD|BPF_IMM|BPF_W, i, 0L)

struct vmapinfo {
	int is_const;
	bpf_int32 const_val;
};

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

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

/* Because we really don't have an IR, this stuff is a little messy. */
static int
F(code, v0, v1)
	int code;
	int 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 (BPF_MODE(code) == BPF_IMM &&
	    (BPF_CLASS(code) == BPF_LD || BPF_CLASS(code) == BPF_LDX)) {
		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;
	int *valp;
	int newval;
	int alter;
{
	if (alter && *valp == newval)
		s->code = NOP;
	else
		*valp = newval;
}

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

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

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

	case BPF_SUB:
		a -= b;
		break;

	case BPF_MUL:
		a *= b;
		break;

	case BPF_DIV:
		if (b == 0)
			bpf_error("division by zero");
		a /= b;
		break;

	case BPF_AND:
		a &= b;
		break;

	case BPF_OR:
		a |= b;
		break;

	case BPF_LSH:
		a <<= b;
		break;

	case BPF_RSH:
		a >>= b;
		break;

	case BPF_NEG:
		a = -a;
		break;

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

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

static void
opt_not(b)
	struct block *b;
{
	struct block *tmp = JT(b);

	JT(b) = JF(b);
	JF(b) = tmp;
}

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

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

	last = s;
	while (1) {
		s = this_op(s);