* Optimization module for BPF code intermediate representation.
*/
-#ifdef HAVE_CONFIG_H
#include <config.h>
-#endif
#include <pcap-types.h>
#define lowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
#elif defined(_MSC_VER)
/*
- * Visual Studio; we support only 2005 and later, so use
+ * Visual Studio; we support only 2015 and later, so use
* _BitScanForward().
*/
#include <intrin.h>
return (u_int)bit;
}
#else
-/*
- * None of the above.
- * Use a perfect-hash-function-based function.
- */
-static u_int
-lowest_set_bit(int mask)
-{
- unsigned int v = (unsigned int)mask;
-
- static const u_int MultiplyDeBruijnBitPosition[32] = {
- 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
- 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
- };
-
- /*
- * We strip off all but the lowermost set bit (v & ~v),
- * and perform a minimal perfect hash on it to look up the
- * number of low-order zero bits in a table.
- *
- * See:
- *
- * http://7ooo.mooo.com/text/ComputingTrailingZerosHOWTO.pdf
- *
- * http://supertech.csail.mit.edu/papers/debruijn.pdf
- */
- return (MultiplyDeBruijnBitPosition[((v & -v) * 0x077CB531U) >> 27]);
-}
+ /*
+ * POSIX.1-2001 says ffs() is in <strings.h>. Every supported non-Windows OS
+ * (including Linux with musl libc and uclibc-ng) has the header and (except
+ * HP-UX) declares the function there. HP-UX declares the function in
+ * <string.h>, which has already been included.
+ */
+ #include <strings.h>
+ #define lowest_set_bit(mask) ((u_int)(ffs((mask)) - 1))
#endif
/*
static void opt_dump(opt_state_t *, struct icode *);
#endif
-#ifndef MAX
-#define MAX(a,b) ((a)>(b)?(a):(b))
-#endif
-
static void
find_levels_r(opt_state_t *opt_state, struct icode *ic, struct block *b)
{
if (JT(b)) {
find_levels_r(opt_state, ic, JT(b));
find_levels_r(opt_state, ic, JF(b));
- level = MAX(JT(b)->level, JF(b)->level) + 1;
+ level = max(JT(b)->level, JF(b)->level) + 1;
} else
level = 0;
b->level = level;
s->code = BPF_LD|BPF_ABS|BPF_SIZE(s->code);
s->k += opt_state->vmap[v].const_val;
v = F(opt_state, s->code, s->k, 0L);
+ opt_state->done = 0;
/*
* XXX - optimizer loop detection.
*/
opt_state->non_branch_movement_performed = 1;
- opt_state->done = 0;
}
else
v = F(opt_state, s->code, s->k, v);
s->k > 31)
opt_error(opt_state,
"shift by more than 31 bits");
+ opt_state->done = 0;
+ val[A_ATOM] =
+ F(opt_state, s->code, val[A_ATOM], K(s->k));
/*
* XXX - optimizer loop detection.
*/
opt_state->non_branch_movement_performed = 1;
- opt_state->done = 0;
- val[A_ATOM] =
- F(opt_state, s->code, val[A_ATOM], K(s->k));
}
break;
}
if (alter && opt_state->vmap[v].is_const) {
s->code = BPF_LD|BPF_IMM;
s->k = opt_state->vmap[v].const_val;
+ opt_state->done = 0;
/*
* XXX - optimizer loop detection.
*/
opt_state->non_branch_movement_performed = 1;
- opt_state->done = 0;
}
vstore(s, &val[A_ATOM], v, alter);
break;
if (alter && opt_state->vmap[v].is_const) {
s->code = BPF_LDX|BPF_IMM;
s->k = opt_state->vmap[v].const_val;
+ opt_state->done = 0;
/*
* XXX - optimizer loop detection.
*/
opt_state->non_branch_movement_performed = 1;
- opt_state->done = 0;
}
vstore(s, &val[X_ATOM], v, alter);
break;
atom = atomdef(s);
if (atom >= 0) {
if (last[atom]) {
+ opt_state->done = 0;
+ last[atom]->code = NOP;
/*
* XXX - optimizer loop detection.
*/
opt_state->non_branch_movement_performed = 1;
- opt_state->done = 0;
- last[atom]->code = NOP;
}
last[atom] = s;
}
* an unknown value.
*/
vstore(0, &b->val[atom], VAL_UNKNOWN, 0);
+ opt_state->done = 0;
/*
* XXX - optimizer loop detection.
*/
opt_state->non_branch_movement_performed = 1;
- opt_state->done = 0;
}
}
BPF_CLASS(b->s.code) == BPF_RET)) {
if (b->stmts != 0) {
b->stmts = 0;
+ opt_state->done = 0;
/*
* XXX - optimizer loop detection.
*/
opt_state->non_branch_movement_performed = 1;
- opt_state->done = 0;
}
} else {
opt_peep(opt_state, b);
* Make this edge go to the block to
* which the successor of that edge
* goes.
- *
- * XXX - optimizer loop detection.
*/
- opt_state->non_branch_movement_performed = 1;
opt_state->done = 0;
ep->succ = JT(ep->succ);
+ /*
+ * XXX - optimizer loop detection.
+ */
+ opt_state->non_branch_movement_performed = 1;
}
}
/*
#ifdef BDEBUG
if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) {
- printf("opt_loop(root, %d) begin\n", do_stmts);
+ printf("%s(root, %d) begin\n", __func__, do_stmts);
opt_dump(opt_state, ic);
}
#endif
*/
int loop_count = 0;
for (;;) {
- opt_state->done = 1;
/*
* XXX - optimizer loop detection.
*/
opt_state->non_branch_movement_performed = 0;
+ opt_state->done = 1;
find_levels(opt_state, ic);
find_dom(opt_state, ic->root);
find_closure(opt_state, ic->root);
opt_blks(opt_state, ic, do_stmts);
#ifdef BDEBUG
if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) {
- printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, opt_state->done);
+ printf("%s(root, %d) bottom, done=%d\n", __func__, do_stmts, opt_state->done);
opt_dump(opt_state, ic);
}
#endif
memset(&opt_state, 0, sizeof(opt_state));
opt_state.errbuf = errbuf;
- opt_state.non_branch_movement_performed = 0;
if (setjmp(opt_state.top_ctx)) {
opt_cleanup(&opt_state);
return -1;
else
status = plain_dump(ic, errbuf);
if (status == -1)
- opt_error(opt_state, "opt_dump: icode_to_fcode failed: %s", errbuf);
+ opt_error(opt_state, "%s: icode_to_fcode failed: %s", __func__, errbuf);
}
#endif
projects / libpcap / blobdiff