* Optimization module for tcpdump intermediate representation.
*/
#ifndef lint
-static const char rcsid[] =
- "@(#) $Header: /tcpdump/master/libpcap/optimize.c,v 1.69 2001-11-12 21:57:06 fenner Exp $ (LBL)";
+static const char rcsid[] _U_ =
+ "@(#) $Header: /tcpdump/master/libpcap/optimize.c,v 1.77 2003-11-15 23:24:00 guy Exp $ (LBL)";
#endif
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
-#include <sys/types.h>
-#include <sys/time.h>
-
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
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 *);
return;
last = s;
- while (1) {
+ for (/*empty*/; /*empty*/; s = next) {
s = this_op(s);
if (s == 0)
break;
* any local dependencies.
*/
if (ATOMELEM(b->out_use, X_ATOM))
- break;
+ continue;
if (next->s.code != (BPF_LDX|BPF_MSH|BPF_B))
add = next;
else
add = this_op(next->next);
if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X))
- break;
+ continue;
tax = this_op(add->next);
if (tax == 0 || tax->s.code != (BPF_MISC|BPF_TAX))
- break;
+ continue;
ild = this_op(tax->next);
if (ild == 0 || BPF_CLASS(ild->s.code) != BPF_LD ||
BPF_MODE(ild->s.code) != BPF_IND)
- break;
+ continue;
/*
* XXX We need to check that X is not
* subsequently used. We know we can eliminate the
tax->s.code = NOP;
done = 0;
}
- s = next;
}
/*
* If we have a subtract to do a comparison, and the X register
* is a known constant, we can merge this value into the
* comparison.
*/
- if (last->s.code == (BPF_ALU|BPF_SUB|BPF_X) &&
- !ATOMELEM(b->out_use, A_ATOM)) {
- val = b->val[X_ATOM];
- if (vmap[val].is_const) {
- int op;
-
- b->s.k += vmap[val].const_val;
- op = BPF_OP(b->s.code);
- if (op == BPF_JGT || op == BPF_JGE) {
- struct block *t = JT(b);
- JT(b) = JF(b);
- JF(b) = t;
- b->s.k += 0x80000000;
+ if (BPF_OP(b->s.code) == BPF_JEQ) {
+ if (last->s.code == (BPF_ALU|BPF_SUB|BPF_X) &&
+ !ATOMELEM(b->out_use, A_ATOM)) {
+ val = b->val[X_ATOM];
+ if (vmap[val].is_const) {
+ /*
+ * sub x -> nop
+ * jeq #y jeq #(x+y)
+ */
+ b->s.k += vmap[val].const_val;
+ last->s.code = NOP;
+ done = 0;
+ } else if (b->s.k == 0) {
+ /*
+ * sub #x -> nop
+ * jeq #0 jeq #x
+ */
+ last->s.code = NOP;
+ b->s.code = BPF_CLASS(b->s.code) |
+ BPF_OP(b->s.code) | BPF_X;
+ done = 0;
}
- last->s.code = NOP;
- done = 0;
- } else if (b->s.k == 0) {
- /*
- * sub x -> nop
- * j #0 j x
- */
- last->s.code = NOP;
- b->s.code = BPF_CLASS(b->s.code) | BPF_OP(b->s.code) |
- BPF_X;
- done = 0;
}
- }
- /*
- * Likewise, a constant subtract can be simplified.
- */
- else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K) &&
- !ATOMELEM(b->out_use, A_ATOM)) {
- int op;
+ /*
+ * Likewise, a constant subtract can be simplified.
+ */
+ else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K) &&
+ !ATOMELEM(b->out_use, A_ATOM)) {
- b->s.k += last->s.k;
- last->s.code = NOP;
- op = BPF_OP(b->s.code);
- if (op == BPF_JGT || op == BPF_JGE) {
- struct block *t = JT(b);
- JT(b) = JF(b);
- JF(b) = t;
- b->s.k += 0x80000000;
+ last->s.code = NOP;
+ b->s.k += last->s.k;
+ done = 0;
}
- done = 0;
}
/*
* and #k nop
done = 0;
opt_not(b);
}
+ /*
+ * jset #0 -> never
+ * jset #ffffffff -> always
+ */
+ if (b->s.code == (BPF_JMP|BPF_K|BPF_JSET)) {
+ if (b->s.k == 0)
+ JT(b) = JF(b);
+ if (b->s.k == 0xffffffff)
+ JF(b) = JT(b);
+ }
/*
* If the accumulator is a known constant, we can compute the
* comparison result.
* that is 0, and simplify. This may not seem like
* much of a simplification but it could open up further
* optimizations.
- * XXX We could also check for mul by 1, and -1, etc.
+ * XXX We could also check for mul by 1, etc.
*/
if (alter && vmap[val[A_ATOM]].is_const
&& vmap[val[A_ATOM]].const_val == 0) {
- if (op == BPF_ADD || op == BPF_OR ||
- op == BPF_LSH || op == BPF_RSH || op == BPF_SUB) {
+ if (op == BPF_ADD || op == BPF_OR) {
s->code = BPF_MISC|BPF_TXA;
vstore(s, &val[A_ATOM], val[X_ATOM], alter);
break;
}
else if (op == BPF_MUL || op == BPF_DIV ||
- op == BPF_AND) {
+ op == BPF_AND || op == BPF_LSH || op == BPF_RSH) {
s->code = BPF_LD|BPF_IMM;
s->k = 0;
vstore(s, &val[A_ATOM], K(s->k), alter);
* already there, or if this block is a return,
* eliminate all the statements.
*/
- if (do_stmts &&
+ if (do_stmts &&
((b->out_use == 0 && aval != 0 &&b->val[A_ATOM] == aval) ||
BPF_CLASS(b->s.code) == BPF_RET)) {
if (b->stmts != 0) {
unMarkAll();
n = count_blocks(root);
blocks = (struct block **)malloc(n * sizeof(*blocks));
+ if (blocks == NULL)
+ bpf_error("malloc");
unMarkAll();
n_blocks = 0;
number_blks_r(root);
n_edges = 2 * n_blocks;
edges = (struct edge **)malloc(n_edges * sizeof(*edges));
+ if (edges == NULL)
+ bpf_error("malloc");
/*
* The number of levels is bounded by the number of nodes.
*/
levels = (struct block **)malloc(n_blocks * sizeof(*levels));
+ if (levels == NULL)
+ bpf_error("malloc");
edgewords = n_edges / (8 * sizeof(bpf_u_int32)) + 1;
nodewords = n_blocks / (8 * sizeof(bpf_u_int32)) + 1;
/* XXX */
space = (bpf_u_int32 *)malloc(2 * n_blocks * nodewords * sizeof(*space)
+ n_edges * edgewords * sizeof(*space));
+ if (space == NULL)
+ bpf_error("malloc");
p = space;
all_dom_sets = p;
for (i = 0; i < n; ++i) {
maxval = 3 * max_stmts;
vmap = (struct vmapinfo *)malloc(maxval * sizeof(*vmap));
vnode_base = (struct valnode *)malloc(maxval * sizeof(*vnode_base));
+ if (vmap == NULL || vnode_base == NULL)
+ bpf_error("malloc");
}
/*
/* generate offset[] for convenience */
if (slen) {
- offset = (struct slist **)calloc(sizeof(struct slist *), slen);
+ offset = (struct slist **)calloc(slen, sizeof(struct slist *));
if (!offset) {
bpf_error("not enough core");
/*NOTREACHED*/
while (1) {
unMarkAll();
n = *lenp = count_stmts(root);
-
+
fp = (struct bpf_insn *)malloc(sizeof(*fp) * n);
+ if (fp == NULL)
+ bpf_error("malloc");
memset((char *)fp, 0, sizeof(*fp) * n);
fstart = fp;
ftail = fp + n;
-
+
unMarkAll();
if (convert_code_r(root))
break;
projects / libpcap / blobdiff