optimize.c

/*
 * 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 BPF code intermediate representation.
 */

#ifdefHAVE_CONFIG_H
#include<config.h>
#endif

#include<pcap-types.h>

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<setjmp.h>
#include<string.h>
#include<limits.h>/* for SIZE_MAX */
#include<errno.h>

#include"pcap-int.h"

#include"gencode.h"
#include"optimize.h"
#include"diag-control.h"

#ifdefHAVE_OS_PROTO_H
#include"os-proto.h"
#endif

#ifdefBDEBUG
/*
 * The internal "debug printout" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_optimizer_debug;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_optimizer_debug(intvalue);

PCAP_API_DEFvoid
pcap_set_optimizer_debug(intvalue)
{
pcap_optimizer_debug=value;
}

/*
 * The internal "print dot graph" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_print_dot_graph;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_print_dot_graph(intvalue);

PCAP_API_DEFvoid
pcap_set_print_dot_graph(intvalue)
{
pcap_print_dot_graph=value;
}

#endif

/*
 * lowest_set_bit().
 *
 * Takes a 32-bit integer as an argument.
 *
 * If handed a non-zero value, returns the index of the lowest set bit,
 * counting upwards from zero.
 *
 * If handed zero, the results are platform- and compiler-dependent.
 * Keep it out of the light, don't give it any water, don't feed it
 * after midnight, and don't pass zero to it.
 *
 * This is the same as the count of trailing zeroes in the word.
 */
#ifPCAP_IS_AT_LEAST_GNUC_VERSION(3,4)
/*
 * GCC 3.4 and later; we have __builtin_ctz().
 */
#definelowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
#elif defined(_MSC_VER)
/*
 * Visual Studio; we support only 2005 and later, so use
 * _BitScanForward().
 */
#include<intrin.h>

#ifndef__clang__
#pragma intrinsic(_BitScanForward)
#endif

static __forceinline u_int
lowest_set_bit(intmask)
{
unsigned longbit;

/*
 * Don't sign-extend mask if long is longer than int.
 * (It's currently not, in MSVC, even on 64-bit platforms, but....)
 */
if (_BitScanForward(&bit, (unsigned int)mask) ==0)
abort();	/* mask is zero */
return (u_int)bit;
}
#elif defined(MSDOS) && defined(__DJGPP__)
/*
 * MS-DOS with DJGPP, which declares ffs() in <string.h>, which
 * we've already included.
 */
#definelowest_set_bit(mask)	((u_int)(ffs((mask)) - 1))
#elif (defined(MSDOS) && defined(__WATCOMC__)) || defined(STRINGS_H_DECLARES_FFS)
/*
 * MS-DOS with Watcom C, which has <strings.h> and declares ffs() there,
 * or some other platform (UN*X conforming to a sufficient recent version
 * of the Single UNIX Specification).
 */
#include<strings.h>
#definelowest_set_bit(mask)	(u_int)((ffs((mask)) - 1))
#else
/*
 * None of the above.
 * Use a perfect-hash-function-based function.
 */
staticu_int
lowest_set_bit(intmask)
{
unsigned intv= (unsigned int)mask;

staticconstu_intMultiplyDeBruijnBitPosition[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]);
}
#endif

/*
 * Represents a deleted instruction.
 */
#defineNOP -1

/*
 * Register numbers for use-def values.
 * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory
 * location. A_ATOM is the accumulator and X_ATOM is the index
 * register.
 */
#defineA_ATOM BPF_MEMWORDS
#defineX_ATOM (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.
 */
#defineAX_ATOM N_ATOMS

/*
 * 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.
 */
structvalnode {
intcode;
bpf_u_int32v0, v1;
intval; /* the value number */
structvalnode*next;
};

/* Integer constants mapped with the load immediate opcode. */
#defineK(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)

structvmapinfo {
intis_const;
bpf_u_int32const_val;
};

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * A flag to indicate that further optimization is needed.
 * Iterative passes are continued until a given pass yields no
 * code simplification or branch movement.
 */
intdone;

/*
 * XXX - detect loops that do nothing but repeated AND/OR pullups
 * and edge moves.
 * If 100 passes in a row do nothing but that, treat that as a
 * sign that we're in a loop that just shuffles in a cycle in
 * which each pass just shuffles the code and we eventually
 * get back to the original configuration.
 *
 * XXX - we need a non-heuristic way of detecting, or preventing,
 * such a cycle.
 */
intnon_branch_movement_performed;

u_intn_blocks; /* number of blocks in the CFG; guaranteed to be > 0, as it's a RET instruction at a minimum */
structblock**blocks;
u_intn_edges; /* twice n_blocks, so guaranteed to be > 0 */
structedge**edges;

/*
 * A bit vector set representation of the dominators.
 * We round up the set size to the next power of two.
 */
u_intnodewords;	/* number of 32-bit words for a bit vector of "number of nodes" bits; guaranteed to be > 0 */
u_intedgewords;	/* number of 32-bit words for a bit vector of "number of edges" bits; guaranteed to be > 0 */
structblock**levels;
bpf_u_int32*space;

#defineBITS_PER_WORD (8*sizeof(bpf_u_int32))
/*
 * True if a is in uset {p}
 */
#defineSET_MEMBER(p, a) \
((p)[(unsigned)(a) / BITS_PER_WORD] & ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD)))

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

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

/*
 * a := a intersect b
 * n must be guaranteed to be > 0
 */
#defineSET_INTERSECT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &= *_y++; while (--_n != 0);\
}

/*
 * a := a - b
 * n must be guaranteed to be > 0
 */
#defineSET_SUBTRACT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &=~ *_y++; while (--_n != 0);\
}

/*
 * a := a union b
 * n must be guaranteed to be > 0
 */
#defineSET_UNION(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ |= *_y++; while (--_n != 0);\
}

usetall_dom_sets;
usetall_closure_sets;
usetall_edge_sets;

#defineMODULUS 213
structvalnode*hashtbl[MODULUS];
bpf_u_int32curval;
bpf_u_int32maxval;

structvmapinfo*vmap;
structvalnode*vnode_base;
structvalnode*next_vnode;
} opt_state_t;

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * 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.
 */
structbpf_insn*fstart;
structbpf_insn*ftail;
} conv_state_t;

staticvoidopt_init(opt_state_t*, structicode*);
staticvoidopt_cleanup(opt_state_t*);
staticvoidPCAP_NORETURNopt_error(opt_state_t*, constchar*, ...)
PCAP_PRINTFLIKE(2, 3);

staticvoidintern_blocks(opt_state_t*, structicode*);

staticvoidfind_inedges(opt_state_t*, structblock*);
#ifdefBDEBUG
staticvoidopt_dump(opt_state_t*, structicode*);
#endif

#ifndefMAX
#defineMAX(a,b) ((a)>(b)?(a):(b))
#endif

staticvoid
find_levels_r(opt_state_t*opt_state, structicode*ic, structblock*b)
{
intlevel;

if (isMarked(ic, b))
return;

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

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;
	} else
level=0;
b->level=level;
b->link=opt_state->levels[level];
opt_state->levels[level] =b;
}

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

/*
 * Find dominator relationships.
 * Assumes graph has been leveled.
 */
staticvoid
find_dom(opt_state_t*opt_state, structblock*root)
{
u_inti;
intlevel;
structblock*b;
bpf_u_int32*x;

/*
 * Initialize sets to contain all nodes.
 */
x=opt_state->all_dom_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
i=opt_state->n_blocks*opt_state->nodewords;
while (i!=0) {
--i;
*x++=0xFFFFFFFFU;
	}
/* Root starts off empty. */
for (i=opt_state->nodewords; i!=0;) {
--i;
root->dom[i] =0;
	}

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->dom, b->id);
if (JT(b) ==0)
continue;
SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
 }
	}
}

staticvoid
propedom(opt_state_t*opt_state, structedge*ep)
{
SET_INSERT(ep->edom, ep->id);
if (ep->succ) {
SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
	}
}

/*
 * Compute edge dominators.
 * Assumes graph has been leveled and predecessors established.
 */
staticvoid
find_edom(opt_state_t*opt_state, structblock*root)
{
u_inti;
usetx;
intlevel;
structblock*b;

x=opt_state->all_edge_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
for (i=opt_state->n_edges*opt_state->edgewords; i!=0; ) {
--i;
x[i] =0xFFFFFFFFU;
	}

/* root->level is the highest level no found. */
memset(root->et.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
memset(root->ef.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b!=0; b=b->link) {
propedom(opt_state, &b->et);
propedom(opt_state, &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.
 */
staticvoid
find_closure(opt_state_t*opt_state, structblock*root)
{
intlevel;
structblock*b;

/*
 * Initialize sets to contain no nodes.
 */
memset((char*)opt_state->all_closure_sets, 0,
opt_state->n_blocks*opt_state->nodewords*sizeof(*opt_state->all_closure_sets));

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->closure, b->id);
if (JT(b) ==0)
continue;
SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
 }
	}
}

/*
 * Return the register number that is used by s.
 *
 * Returns ATOM_A if A is used, ATOM_X if X is used, AX_ATOM if both A and X
 * are used, the scratch memory location's number if a scratch memory
 * location is used (e.g., 0 for M[0]), or -1 if none of those are used.
 *
 * The implementation should probably change to an array access.
 */
staticint
atomuse(structstmt*s)
{
	register intc=s->code;

if (c==NOP)
return-1;

switch (BPF_CLASS(c)) {

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

caseBPF_LD:
caseBPF_LDX:
/*
 * As there are fewer than 2^31 memory locations,
 * s->k should be convertible to int without problems.
 */
return (BPF_MODE(c) ==BPF_IND) ? X_ATOM :
 (BPF_MODE(c) ==BPF_MEM) ? (int)s->k : -1;

caseBPF_ST:
returnA_ATOM;

caseBPF_STX:
returnX_ATOM;

caseBPF_JMP:
caseBPF_ALU:
if (BPF_SRC(c) ==BPF_X)
returnAX_ATOM;
returnA_ATOM;

caseBPF_MISC:
returnBPF_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.
 */
staticint
atomdef(structstmt*s)
{
if (s->code==NOP)
return-1;

switch (BPF_CLASS(s->code)) {

caseBPF_LD:
caseBPF_ALU:
returnA_ATOM;

caseBPF_LDX:
returnX_ATOM;

caseBPF_ST:
caseBPF_STX:
returns->k;

caseBPF_MISC:
returnBPF_MISCOP(s->code) ==BPF_TAX ? X_ATOM : A_ATOM;
	}
return-1;
}

/*
 * Compute the sets of registers used, defined, and killed by 'b'.
 *
 * "Used" means that a statement in 'b' uses the register before any
 * statement in 'b' defines it, i.e. it uses the value left in
 * that register by a predecessor block of this block.
 * "Defined" means that a statement in 'b' defines it.
 * "Killed" means that a statement in 'b' defines it before any
 * statement in 'b' uses it, i.e. it kills the value left in that
 * register by a predecessor block of this block.
 */
staticvoid
compute_local_ud(structblock*b)
{
structslist*s;
atomsetdef=0, use=0, killed=0;
intatom;

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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
atom=atomdef(&s->s);
if (atom >= 0) {
if (!ATOMELEM(use, atom))
killed |= ATOMMASK(atom);
def |= ATOMMASK(atom);
 }
	}
if (BPF_CLASS(b->s.code) ==BPF_JMP) {
/*
 * XXX - what about RET?
 */
atom=atomuse(&b->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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
	}

b->def=def;
b->kill=killed;
b->in_use=use;
}

/*
 * Assume graph is already leveled.
 */
staticvoid
find_ud(opt_state_t*opt_state, structblock*root)
{
inti, maxlevel;
structblock*p;

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

for (i=1; i <= maxlevel; ++i) {
for (p=opt_state->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;
 }
	}
}
staticvoid
init_val(opt_state_t*opt_state)
{
opt_state->curval=0;
opt_state->next_vnode=opt_state->vnode_base;
memset((char*)opt_state->vmap, 0, opt_state->maxval*sizeof(*opt_state->vmap));
memset((char*)opt_state->hashtbl, 0, sizeofopt_state->hashtbl);
}

/*
 * Because we really don't have an IR, this stuff is a little messy.
 *
 * This routine looks in the table of existing value number for a value
 * with generated from an operation with the specified opcode and
 * the specified values. If it finds it, it returns its value number,
 * otherwise it makes a new entry in the table and returns the
 * value number of that entry.
 */
staticbpf_u_int32
F(opt_state_t*opt_state, intcode, bpf_u_int32v0, bpf_u_int32v1)
{
u_inthash;
bpf_u_int32val;
structvalnode*p;

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

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

/*
 * Not found. Allocate a new value, and assign it a new
 * value number.
 *
 * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we
 * increment it before using it as the new value number, which
 * means we never assign VAL_UNKNOWN.
 *
 * XXX - unless we overflow, but we probably won't have 2^32-1
 * values; we treat 32 bits as effectively infinite.
 */
val=++opt_state->curval;
if (BPF_MODE(code) ==BPF_IMM&&
 (BPF_CLASS(code) ==BPF_LD||BPF_CLASS(code) ==BPF_LDX)) {
opt_state->vmap[val].const_val=v0;
opt_state->vmap[val].is_const=1;
	}
p=opt_state->next_vnode++;
p->val=val;
p->code=code;
p->v0=v0;
p->v1=v1;
p->next=opt_state->hashtbl[hash];
opt_state->hashtbl[hash] =p;

returnval;
}

staticinlinevoid
vstore(structstmt*s, bpf_u_int32*valp, bpf_u_int32newval, intalter)
{
if (alter&&newval!=VAL_UNKNOWN&&*valp==newval)
s->code=NOP;
else
*valp=newval;
}

/*
 * Do constant-folding on binary operators.
 * (Unary operators are handled elsewhere.)
 */
staticvoid
fold_op(opt_state_t*opt_state, structstmt*s, bpf_u_int32v0, bpf_u_int32v1)
{
bpf_u_int32a, b;

a=opt_state->vmap[v0].const_val;
b=opt_state->vmap[v1].const_val;

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

caseBPF_SUB:
a-=b;
break;

caseBPF_MUL:
a *= b;
break;

caseBPF_DIV:
if (b==0)
opt_error(opt_state, "division by zero");
a /= b;
break;

caseBPF_MOD:
if (b==0)
opt_error(opt_state, "modulus by zero");
a %= b;
break;

caseBPF_AND:
a &= b;
break;

caseBPF_OR:
a |= b;
break;

caseBPF_XOR:
a ^= b;
break;

caseBPF_LSH:
/*
 * A left shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a <<= b;
else
a=0;
break;

caseBPF_RSH:
/*
 * A right shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a >>= b;
else
a=0;
break;

default:
abort();
	}
s->k=a;
s->code=BPF_LD|BPF_IMM;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
}

staticinlinestructslist*
this_op(structslist*s)
{
while (s!=0&&s->s.code==NOP)
s=s->next;
returns;
}

staticvoid
opt_not(structblock*b)
{
structblock*tmp=JT(b);

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

staticvoid
opt_peep(opt_state_t*opt_state, structblock*b)
{
structslist*s;
structslist*next, *last;
bpf_u_int32val;

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

last=s;
for (/*empty*/; /*empty*/; s=next) {
/*
 * Skip over nops.
 */
s=this_op(s);
if (s==0)
break;	/* nothing left in the block */

/*
 * Find the next real instruction after that one
 * (skipping nops).
 */
next=this_op(s->next);
if (next==0)
break;	/* no next instruction */
last=next;

/*
 * st M[k]	-->	st M[k]
 * ldx M[k] tax
 */
if (s->s.code==BPF_ST&&
next->s.code== (BPF_LDX|BPF_MEM) &&
s->s.k==next->s.k) {
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
next->s.code=BPF_MISC|BPF_TAX;
 }
/*
 * ld #k	-->	ldx #k
 * tax txa
 */
if (s->s.code== (BPF_LD|BPF_IMM) &&
next->s.code== (BPF_MISC|BPF_TAX)) {
s->s.code=BPF_LDX|BPF_IMM;
next->s.code=BPF_MISC|BPF_TXA;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
 }
/*
 * This is an ugly special case, but it happens
 * when you say tcp[k] or udp[k] where k is a constant.
 */
if (s->s.code== (BPF_LD|BPF_IMM)) {
structslist*add, *tax, *ild;

/*
 * Check that X isn't used on exit from this
 * block (which the optimizer might cause).
 * We know the code generator won't generate
 * any local dependencies.
 */
if (ATOMELEM(b->out_use, X_ATOM))
continue;

/*
 * Check that the instruction following the ldi
 * is an addx, or it's an ldxms with an addx
 * following it (with 0 or more nops between the
 * ldxms and addx).
 */
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))
continue;

/*
 * Check that a tax follows that (with 0 or more
 * nops between them).
 */
tax=this_op(add->next);
if (tax==0||tax->s.code!= (BPF_MISC|BPF_TAX))
continue;

/*
 * Check that an ild follows that (with 0 or more
 * nops between them).
 */
ild=this_op(tax->next);
if (ild==0||BPF_CLASS(ild->s.code) !=BPF_LD||
BPF_MODE(ild->s.code) !=BPF_IND)
continue;
/*
 * We want to turn this sequence:
 *
 * (004) ldi #0x2 {s}
 * (005) ldxms [14] {next} -- optional
 * (006) addx {add}
 * (007) tax {tax}
 * (008) ild [x+0] {ild}
/*
 * 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 BPF code intermediate representation.
 */

#ifdefHAVE_CONFIG_H
#include<config.h>
#endif

#include<pcap-types.h>

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<setjmp.h>
#include<string.h>
#include<limits.h>/* for SIZE_MAX */
#include<errno.h>

#include"pcap-int.h"

#include"gencode.h"
#include"optimize.h"
#include"diag-control.h"

#ifdefHAVE_OS_PROTO_H
#include"os-proto.h"
#endif

#ifdefBDEBUG
/*
 * The internal "debug printout" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_optimizer_debug;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_optimizer_debug(intvalue);

PCAP_API_DEFvoid
pcap_set_optimizer_debug(intvalue)
{
pcap_optimizer_debug=value;
}

/*
 * The internal "print dot graph" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_print_dot_graph;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_print_dot_graph(intvalue);

PCAP_API_DEFvoid
pcap_set_print_dot_graph(intvalue)
{
pcap_print_dot_graph=value;
}

#endif

/*
 * lowest_set_bit().
 *
 * Takes a 32-bit integer as an argument.
 *
 * If handed a non-zero value, returns the index of the lowest set bit,
 * counting upwards from zero.
 *
 * If handed zero, the results are platform- and compiler-dependent.
 * Keep it out of the light, don't give it any water, don't feed it
 * after midnight, and don't pass zero to it.
 *
 * This is the same as the count of trailing zeroes in the word.
 */
#ifPCAP_IS_AT_LEAST_GNUC_VERSION(3,4)
/*
 * GCC 3.4 and later; we have __builtin_ctz().
 */
#definelowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
#elif defined(_MSC_VER)
/*
 * Visual Studio; we support only 2005 and later, so use
 * _BitScanForward().
 */
#include<intrin.h>

#ifndef__clang__
#pragma intrinsic(_BitScanForward)
#endif

static __forceinline u_int
lowest_set_bit(intmask)
{
unsigned longbit;

/*
 * Don't sign-extend mask if long is longer than int.
 * (It's currently not, in MSVC, even on 64-bit platforms, but....)
 */
if (_BitScanForward(&bit, (unsigned int)mask) ==0)
abort();	/* mask is zero */
return (u_int)bit;
}
#elif defined(MSDOS) && defined(__DJGPP__)
/*
 * MS-DOS with DJGPP, which declares ffs() in <string.h>, which
 * we've already included.
 */
#definelowest_set_bit(mask)	((u_int)(ffs((mask)) - 1))
#elif (defined(MSDOS) && defined(__WATCOMC__)) || defined(STRINGS_H_DECLARES_FFS)
/*
 * MS-DOS with Watcom C, which has <strings.h> and declares ffs() there,
 * or some other platform (UN*X conforming to a sufficient recent version
 * of the Single UNIX Specification).
 */
#include<strings.h>
#definelowest_set_bit(mask)	(u_int)((ffs((mask)) - 1))
#else
/*
 * None of the above.
 * Use a perfect-hash-function-based function.
 */
staticu_int
lowest_set_bit(intmask)
{
unsigned intv= (unsigned int)mask;

staticconstu_intMultiplyDeBruijnBitPosition[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]);
}
#endif

/*
 * Represents a deleted instruction.
 */
#defineNOP -1

/*
 * Register numbers for use-def values.
 * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory
 * location. A_ATOM is the accumulator and X_ATOM is the index
 * register.
 */
#defineA_ATOM BPF_MEMWORDS
#defineX_ATOM (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.
 */
#defineAX_ATOM N_ATOMS

/*
 * 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.
 */
structvalnode {
intcode;
bpf_u_int32v0, v1;
intval; /* the value number */
structvalnode*next;
};

/* Integer constants mapped with the load immediate opcode. */
#defineK(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)

structvmapinfo {
intis_const;
bpf_u_int32const_val;
};

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * A flag to indicate that further optimization is needed.
 * Iterative passes are continued until a given pass yields no
 * code simplification or branch movement.
 */
intdone;

/*
 * XXX - detect loops that do nothing but repeated AND/OR pullups
 * and edge moves.
 * If 100 passes in a row do nothing but that, treat that as a
 * sign that we're in a loop that just shuffles in a cycle in
 * which each pass just shuffles the code and we eventually
 * get back to the original configuration.
 *
 * XXX - we need a non-heuristic way of detecting, or preventing,
 * such a cycle.
 */
intnon_branch_movement_performed;

u_intn_blocks; /* number of blocks in the CFG; guaranteed to be > 0, as it's a RET instruction at a minimum */
structblock**blocks;
u_intn_edges; /* twice n_blocks, so guaranteed to be > 0 */
structedge**edges;

/*
 * A bit vector set representation of the dominators.
 * We round up the set size to the next power of two.
 */
u_intnodewords;	/* number of 32-bit words for a bit vector of "number of nodes" bits; guaranteed to be > 0 */
u_intedgewords;	/* number of 32-bit words for a bit vector of "number of edges" bits; guaranteed to be > 0 */
structblock**levels;
bpf_u_int32*space;

#defineBITS_PER_WORD (8*sizeof(bpf_u_int32))
/*
 * True if a is in uset {p}
 */
#defineSET_MEMBER(p, a) \
((p)[(unsigned)(a) / BITS_PER_WORD] & ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD)))

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

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

/*
 * a := a intersect b
 * n must be guaranteed to be > 0
 */
#defineSET_INTERSECT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &= *_y++; while (--_n != 0);\
}

/*
 * a := a - b
 * n must be guaranteed to be > 0
 */
#defineSET_SUBTRACT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &=~ *_y++; while (--_n != 0);\
}

/*
 * a := a union b
 * n must be guaranteed to be > 0
 */
#defineSET_UNION(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ |= *_y++; while (--_n != 0);\
}

usetall_dom_sets;
usetall_closure_sets;
usetall_edge_sets;

#defineMODULUS 213
structvalnode*hashtbl[MODULUS];
bpf_u_int32curval;
bpf_u_int32maxval;

structvmapinfo*vmap;
structvalnode*vnode_base;
structvalnode*next_vnode;
} opt_state_t;

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * 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.
 */
structbpf_insn*fstart;
structbpf_insn*ftail;
} conv_state_t;

staticvoidopt_init(opt_state_t*, structicode*);
staticvoidopt_cleanup(opt_state_t*);
staticvoidPCAP_NORETURNopt_error(opt_state_t*, constchar*, ...)
PCAP_PRINTFLIKE(2, 3);

staticvoidintern_blocks(opt_state_t*, structicode*);

staticvoidfind_inedges(opt_state_t*, structblock*);
#ifdefBDEBUG
staticvoidopt_dump(opt_state_t*, structicode*);
#endif

#ifndefMAX
#defineMAX(a,b) ((a)>(b)?(a):(b))
#endif

staticvoid
find_levels_r(opt_state_t*opt_state, structicode*ic, structblock*b)
{
intlevel;

if (isMarked(ic, b))
return;

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

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;
	} else
level=0;
b->level=level;
b->link=opt_state->levels[level];
opt_state->levels[level] =b;
}

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

/*
 * Find dominator relationships.
 * Assumes graph has been leveled.
 */
staticvoid
find_dom(opt_state_t*opt_state, structblock*root)
{
u_inti;
intlevel;
structblock*b;
bpf_u_int32*x;

/*
 * Initialize sets to contain all nodes.
 */
x=opt_state->all_dom_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
i=opt_state->n_blocks*opt_state->nodewords;
while (i!=0) {
--i;
*x++=0xFFFFFFFFU;
	}
/* Root starts off empty. */
for (i=opt_state->nodewords; i!=0;) {
--i;
root->dom[i] =0;
	}

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->dom, b->id);
if (JT(b) ==0)
continue;
SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
 }
	}
}

staticvoid
propedom(opt_state_t*opt_state, structedge*ep)
{
SET_INSERT(ep->edom, ep->id);
if (ep->succ) {
SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
	}
}

/*
 * Compute edge dominators.
 * Assumes graph has been leveled and predecessors established.
 */
staticvoid
find_edom(opt_state_t*opt_state, structblock*root)
{
u_inti;
usetx;
intlevel;
structblock*b;

x=opt_state->all_edge_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
for (i=opt_state->n_edges*opt_state->edgewords; i!=0; ) {
--i;
x[i] =0xFFFFFFFFU;
	}

/* root->level is the highest level no found. */
memset(root->et.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
memset(root->ef.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b!=0; b=b->link) {
propedom(opt_state, &b->et);
propedom(opt_state, &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.
 */
staticvoid
find_closure(opt_state_t*opt_state, structblock*root)
{
intlevel;
structblock*b;

/*
 * Initialize sets to contain no nodes.
 */
memset((char*)opt_state->all_closure_sets, 0,
opt_state->n_blocks*opt_state->nodewords*sizeof(*opt_state->all_closure_sets));

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->closure, b->id);
if (JT(b) ==0)
continue;
SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
 }
	}
}

/*
 * Return the register number that is used by s.
 *
 * Returns ATOM_A if A is used, ATOM_X if X is used, AX_ATOM if both A and X
 * are used, the scratch memory location's number if a scratch memory
 * location is used (e.g., 0 for M[0]), or -1 if none of those are used.
 *
 * The implementation should probably change to an array access.
 */
staticint
atomuse(structstmt*s)
{
	register intc=s->code;

if (c==NOP)
return-1;

switch (BPF_CLASS(c)) {

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

caseBPF_LD:
caseBPF_LDX:
/*
 * As there are fewer than 2^31 memory locations,
 * s->k should be convertible to int without problems.
 */
return (BPF_MODE(c) ==BPF_IND) ? X_ATOM :
 (BPF_MODE(c) ==BPF_MEM) ? (int)s->k : -1;

caseBPF_ST:
returnA_ATOM;

caseBPF_STX:
returnX_ATOM;

caseBPF_JMP:
caseBPF_ALU:
if (BPF_SRC(c) ==BPF_X)
returnAX_ATOM;
returnA_ATOM;

caseBPF_MISC:
returnBPF_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.
 */
staticint
atomdef(structstmt*s)
{
if (s->code==NOP)
return-1;

switch (BPF_CLASS(s->code)) {

caseBPF_LD:
caseBPF_ALU:
returnA_ATOM;

caseBPF_LDX:
returnX_ATOM;

caseBPF_ST:
caseBPF_STX:
returns->k;

caseBPF_MISC:
returnBPF_MISCOP(s->code) ==BPF_TAX ? X_ATOM : A_ATOM;
	}
return-1;
}

/*
 * Compute the sets of registers used, defined, and killed by 'b'.
 *
 * "Used" means that a statement in 'b' uses the register before any
 * statement in 'b' defines it, i.e. it uses the value left in
 * that register by a predecessor block of this block.
 * "Defined" means that a statement in 'b' defines it.
 * "Killed" means that a statement in 'b' defines it before any
 * statement in 'b' uses it, i.e. it kills the value left in that
 * register by a predecessor block of this block.
 */
staticvoid
compute_local_ud(structblock*b)
{
structslist*s;
atomsetdef=0, use=0, killed=0;
intatom;

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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
atom=atomdef(&s->s);
if (atom >= 0) {
if (!ATOMELEM(use, atom))
killed |= ATOMMASK(atom);
def |= ATOMMASK(atom);
 }
	}
if (BPF_CLASS(b->s.code) ==BPF_JMP) {
/*
 * XXX - what about RET?
 */
atom=atomuse(&b->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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
	}

b->def=def;
b->kill=killed;
b->in_use=use;
}

/*
 * Assume graph is already leveled.
 */
staticvoid
find_ud(opt_state_t*opt_state, structblock*root)
{
inti, maxlevel;
structblock*p;

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

for (i=1; i <= maxlevel; ++i) {
for (p=opt_state->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;
 }
	}
}
staticvoid
init_val(opt_state_t*opt_state)
{
opt_state->curval=0;
opt_state->next_vnode=opt_state->vnode_base;
memset((char*)opt_state->vmap, 0, opt_state->maxval*sizeof(*opt_state->vmap));
memset((char*)opt_state->hashtbl, 0, sizeofopt_state->hashtbl);
}

/*
 * Because we really don't have an IR, this stuff is a little messy.
 *
 * This routine looks in the table of existing value number for a value
 * with generated from an operation with the specified opcode and
 * the specified values. If it finds it, it returns its value number,
 * otherwise it makes a new entry in the table and returns the
 * value number of that entry.
 */
staticbpf_u_int32
F(opt_state_t*opt_state, intcode, bpf_u_int32v0, bpf_u_int32v1)
{
u_inthash;
bpf_u_int32val;
structvalnode*p;

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

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

/*
 * Not found. Allocate a new value, and assign it a new
 * value number.
 *
 * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we
 * increment it before using it as the new value number, which
 * means we never assign VAL_UNKNOWN.
 *
 * XXX - unless we overflow, but we probably won't have 2^32-1
 * values; we treat 32 bits as effectively infinite.
 */
val=++opt_state->curval;
if (BPF_MODE(code) ==BPF_IMM&&
 (BPF_CLASS(code) ==BPF_LD||BPF_CLASS(code) ==BPF_LDX)) {
opt_state->vmap[val].const_val=v0;
opt_state->vmap[val].is_const=1;
	}
p=opt_state->next_vnode++;
p->val=val;
p->code=code;
p->v0=v0;
p->v1=v1;
p->next=opt_state->hashtbl[hash];
opt_state->hashtbl[hash] =p;

returnval;
}

staticinlinevoid
vstore(structstmt*s, bpf_u_int32*valp, bpf_u_int32newval, intalter)
{
if (alter&&newval!=VAL_UNKNOWN&&*valp==newval)
s->code=NOP;
else
*valp=newval;
}

/*
 * Do constant-folding on binary operators.
 * (Unary operators are handled elsewhere.)
 */
staticvoid
fold_op(opt_state_t*opt_state, structstmt*s, bpf_u_int32v0, bpf_u_int32v1)
{
bpf_u_int32a, b;

a=opt_state->vmap[v0].const_val;
b=opt_state->vmap[v1].const_val;

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

caseBPF_SUB:
a-=b;
break;

caseBPF_MUL:
a *= b;
break;

caseBPF_DIV:
if (b==0)
opt_error(opt_state, "division by zero");
a /= b;
break;

caseBPF_MOD:
if (b==0)
opt_error(opt_state, "modulus by zero");
a %= b;
break;

caseBPF_AND:
a &= b;
break;

caseBPF_OR:
a |= b;
break;

caseBPF_XOR:
a ^= b;
break;

caseBPF_LSH:
/*
 * A left shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a <<= b;
else
a=0;
break;

caseBPF_RSH:
/*
 * A right shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a >>= b;
else
a=0;
break;

default:
abort();
	}
s->k=a;
s->code=BPF_LD|BPF_IMM;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
}

staticinlinestructslist*
this_op(structslist*s)
{
while (s!=0&&s->s.code==NOP)
s=s->next;
returns;
}

staticvoid
opt_not(structblock*b)
{
structblock*tmp=JT(b);

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

staticvoid
opt_peep(opt_state_t*opt_state, structblock*b)
{
structslist*s;
structslist*next, *last;
bpf_u_int32val;

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

last=s;
for (/*empty*/; /*empty*/; s=next) {
/*
 * Skip over nops.
 */
s=this_op(s);
if (s==0)
break;	/* nothing left in the block */

/*
 * Find the next real instruction after that one
 * (skipping nops).
 */
next=this_op(s->next);
if (next==0)
break;	/* no next instruction */
last=next;

/*
 * st M[k]	-->	st M[k]
 * ldx M[k] tax
 */
if (s->s.code==BPF_ST&&
next->s.code== (BPF_LDX|BPF_MEM) &&
s->s.k==next->s.k) {
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
next->s.code=BPF_MISC|BPF_TAX;
 }
/*
 * ld #k	-->	ldx #k
 * tax txa
 */
if (s->s.code== (BPF_LD|BPF_IMM) &&
next->s.code== (BPF_MISC|BPF_TAX)) {
s->s.code=BPF_LDX|BPF_IMM;
next->s.code=BPF_MISC|BPF_TXA;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
 }
/*
 * This is an ugly special case, but it happens
 * when you say tcp[k] or udp[k] where k is a constant.
 */
if (s->s.code== (BPF_LD|BPF_IMM)) {
structslist*add, *tax, *ild;

/*
 * Check that X isn't used on exit from this
 * block (which the optimizer might cause).
 * We know the code generator won't generate
 * any local dependencies.
 */
if (ATOMELEM(b->out_use, X_ATOM))
continue;

/*
 * Check that the instruction following the ldi
 * is an addx, or it's an ldxms with an addx
 * following it (with 0 or more nops between the
 * ldxms and addx).
 */
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))
continue;

/*
 * Check that a tax follows that (with 0 or more
 * nops between them).
 */
tax=this_op(add->next);
if (tax==0||tax->s.code!= (BPF_MISC|BPF_TAX))
continue;

/*
 * Check that an ild follows that (with 0 or more
 * nops between them).
 */
ild=this_op(tax->next);
if (ild==0||BPF_CLASS(ild->s.code) !=BPF_LD||
BPF_MODE(ild->s.code) !=BPF_IND)
continue;
/*
 * We want to turn this sequence:
 *
 * (004) ldi #0x2 {s}
 * (005) ldxms [14] {next} -- optional
 * (006) addx {add}
 * (007) tax {tax}
 * (008) ild [x+0] {ild}
/*
 * 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 BPF code intermediate representation.
 */

#ifdefHAVE_CONFIG_H
#include<config.h>
#endif

#include<pcap-types.h>

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<setjmp.h>
#include<string.h>
#include<limits.h>/* for SIZE_MAX */
#include<errno.h>

#include"pcap-int.h"

#include"gencode.h"
#include"optimize.h"
#include"diag-control.h"

#ifdefHAVE_OS_PROTO_H
#include"os-proto.h"
#endif

#ifdefBDEBUG
/*
 * The internal "debug printout" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_optimizer_debug;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_optimizer_debug(intvalue);

PCAP_API_DEFvoid
pcap_set_optimizer_debug(intvalue)
{
pcap_optimizer_debug=value;
}

/*
 * The internal "print dot graph" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_print_dot_graph;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_print_dot_graph(intvalue);

PCAP_API_DEFvoid
pcap_set_print_dot_graph(intvalue)
{
pcap_print_dot_graph=value;
}

#endif

/*
 * lowest_set_bit().
 *
 * Takes a 32-bit integer as an argument.
 *
 * If handed a non-zero value, returns the index of the lowest set bit,
 * counting upwards from zero.
 *
 * If handed zero, the results are platform- and compiler-dependent.
 * Keep it out of the light, don't give it any water, don't feed it
 * after midnight, and don't pass zero to it.
 *
 * This is the same as the count of trailing zeroes in the word.
 */
#ifPCAP_IS_AT_LEAST_GNUC_VERSION(3,4)
/*
 * GCC 3.4 and later; we have __builtin_ctz().
 */
#definelowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
#elif defined(_MSC_VER)
/*
 * Visual Studio; we support only 2005 and later, so use
 * _BitScanForward().
 */
#include<intrin.h>

#ifndef__clang__
#pragma intrinsic(_BitScanForward)
#endif

static __forceinline u_int
lowest_set_bit(intmask)
{
unsigned longbit;

/*
 * Don't sign-extend mask if long is longer than int.
 * (It's currently not, in MSVC, even on 64-bit platforms, but....)
 */
if (_BitScanForward(&bit, (unsigned int)mask) ==0)
abort();	/* mask is zero */
return (u_int)bit;
}
#elif defined(MSDOS) && defined(__DJGPP__)
/*
 * MS-DOS with DJGPP, which declares ffs() in <string.h>, which
 * we've already included.
 */
#definelowest_set_bit(mask)	((u_int)(ffs((mask)) - 1))
#elif (defined(MSDOS) && defined(__WATCOMC__)) || defined(STRINGS_H_DECLARES_FFS)
/*
 * MS-DOS with Watcom C, which has <strings.h> and declares ffs() there,
 * or some other platform (UN*X conforming to a sufficient recent version
 * of the Single UNIX Specification).
 */
#include<strings.h>
#definelowest_set_bit(mask)	(u_int)((ffs((mask)) - 1))
#else
/*
 * None of the above.
 * Use a perfect-hash-function-based function.
 */
staticu_int
lowest_set_bit(intmask)
{
unsigned intv= (unsigned int)mask;

staticconstu_intMultiplyDeBruijnBitPosition[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]);
}
#endif

/*
 * Represents a deleted instruction.
 */
#defineNOP -1

/*
 * Register numbers for use-def values.
 * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory
 * location. A_ATOM is the accumulator and X_ATOM is the index
 * register.
 */
#defineA_ATOM BPF_MEMWORDS
#defineX_ATOM (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.
 */
#defineAX_ATOM N_ATOMS

/*
 * 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.
 */
structvalnode {
intcode;
bpf_u_int32v0, v1;
intval; /* the value number */
structvalnode*next;
};

/* Integer constants mapped with the load immediate opcode. */
#defineK(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)

structvmapinfo {
intis_const;
bpf_u_int32const_val;
};

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * A flag to indicate that further optimization is needed.
 * Iterative passes are continued until a given pass yields no
 * code simplification or branch movement.
 */
intdone;

/*
 * XXX - detect loops that do nothing but repeated AND/OR pullups
 * and edge moves.
 * If 100 passes in a row do nothing but that, treat that as a
 * sign that we're in a loop that just shuffles in a cycle in
 * which each pass just shuffles the code and we eventually
 * get back to the original configuration.
 *
 * XXX - we need a non-heuristic way of detecting, or preventing,
 * such a cycle.
 */
intnon_branch_movement_performed;

u_intn_blocks; /* number of blocks in the CFG; guaranteed to be > 0, as it's a RET instruction at a minimum */
structblock**blocks;
u_intn_edges; /* twice n_blocks, so guaranteed to be > 0 */
structedge**edges;

/*
 * A bit vector set representation of the dominators.
 * We round up the set size to the next power of two.
 */
u_intnodewords;	/* number of 32-bit words for a bit vector of "number of nodes" bits; guaranteed to be > 0 */
u_intedgewords;	/* number of 32-bit words for a bit vector of "number of edges" bits; guaranteed to be > 0 */
structblock**levels;
bpf_u_int32*space;

#defineBITS_PER_WORD (8*sizeof(bpf_u_int32))
/*
 * True if a is in uset {p}
 */
#defineSET_MEMBER(p, a) \
((p)[(unsigned)(a) / BITS_PER_WORD] & ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD)))

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

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

/*
 * a := a intersect b
 * n must be guaranteed to be > 0
 */
#defineSET_INTERSECT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &= *_y++; while (--_n != 0);\
}

/*
 * a := a - b
 * n must be guaranteed to be > 0
 */
#defineSET_SUBTRACT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &=~ *_y++; while (--_n != 0);\
}

/*
 * a := a union b
 * n must be guaranteed to be > 0
 */
#defineSET_UNION(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ |= *_y++; while (--_n != 0);\
}

usetall_dom_sets;
usetall_closure_sets;
usetall_edge_sets;

#defineMODULUS 213
structvalnode*hashtbl[MODULUS];
bpf_u_int32curval;
bpf_u_int32maxval;

structvmapinfo*vmap;
structvalnode*vnode_base;
structvalnode*next_vnode;
} opt_state_t;

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * 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.
 */
structbpf_insn*fstart;
structbpf_insn*ftail;
} conv_state_t;

staticvoidopt_init(opt_state_t*, structicode*);
staticvoidopt_cleanup(opt_state_t*);
staticvoidPCAP_NORETURNopt_error(opt_state_t*, constchar*, ...)
PCAP_PRINTFLIKE(2, 3);

staticvoidintern_blocks(opt_state_t*, structicode*);

staticvoidfind_inedges(opt_state_t*, structblock*);
#ifdefBDEBUG
staticvoidopt_dump(opt_state_t*, structicode*);
#endif

#ifndefMAX
#defineMAX(a,b) ((a)>(b)?(a):(b))
#endif

staticvoid
find_levels_r(opt_state_t*opt_state, structicode*ic, structblock*b)
{
intlevel;

if (isMarked(ic, b))
return;

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

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;
	} else
level=0;
b->level=level;
b->link=opt_state->levels[level];
opt_state->levels[level] =b;
}

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

/*
 * Find dominator relationships.
 * Assumes graph has been leveled.
 */
staticvoid
find_dom(opt_state_t*opt_state, structblock*root)
{
u_inti;
intlevel;
structblock*b;
bpf_u_int32*x;

/*
 * Initialize sets to contain all nodes.
 */
x=opt_state->all_dom_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
i=opt_state->n_blocks*opt_state->nodewords;
while (i!=0) {
--i;
*x++=0xFFFFFFFFU;
	}
/* Root starts off empty. */
for (i=opt_state->nodewords; i!=0;) {
--i;
root->dom[i] =0;
	}

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->dom, b->id);
if (JT(b) ==0)
continue;
SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
 }
	}
}

staticvoid
propedom(opt_state_t*opt_state, structedge*ep)
{
SET_INSERT(ep->edom, ep->id);
if (ep->succ) {
SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
	}
}

/*
 * Compute edge dominators.
 * Assumes graph has been leveled and predecessors established.
 */
staticvoid
find_edom(opt_state_t*opt_state, structblock*root)
{
u_inti;
usetx;
intlevel;
structblock*b;

x=opt_state->all_edge_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
for (i=opt_state->n_edges*opt_state->edgewords; i!=0; ) {
--i;
x[i] =0xFFFFFFFFU;
	}

/* root->level is the highest level no found. */
memset(root->et.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
memset(root->ef.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b!=0; b=b->link) {
propedom(opt_state, &b->et);
propedom(opt_state, &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.
 */
staticvoid
find_closure(opt_state_t*opt_state, structblock*root)
{
intlevel;
structblock*b;

/*
 * Initialize sets to contain no nodes.
 */
memset((char*)opt_state->all_closure_sets, 0,
opt_state->n_blocks*opt_state->nodewords*sizeof(*opt_state->all_closure_sets));

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->closure, b->id);
if (JT(b) ==0)
continue;
SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
 }
	}
}

/*
 * Return the register number that is used by s.
 *
 * Returns ATOM_A if A is used, ATOM_X if X is used, AX_ATOM if both A and X
 * are used, the scratch memory location's number if a scratch memory
 * location is used (e.g., 0 for M[0]), or -1 if none of those are used.
 *
 * The implementation should probably change to an array access.
 */
staticint
atomuse(structstmt*s)
{
	register intc=s->code;

if (c==NOP)
return-1;

switch (BPF_CLASS(c)) {

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

caseBPF_LD:
caseBPF_LDX:
/*
 * As there are fewer than 2^31 memory locations,
 * s->k should be convertible to int without problems.
 */
return (BPF_MODE(c) ==BPF_IND) ? X_ATOM :
 (BPF_MODE(c) ==BPF_MEM) ? (int)s->k : -1;

caseBPF_ST:
returnA_ATOM;

caseBPF_STX:
returnX_ATOM;

caseBPF_JMP:
caseBPF_ALU:
if (BPF_SRC(c) ==BPF_X)
returnAX_ATOM;
returnA_ATOM;

caseBPF_MISC:
returnBPF_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.
 */
staticint
atomdef(structstmt*s)
{
if (s->code==NOP)
return-1;

switch (BPF_CLASS(s->code)) {

caseBPF_LD:
caseBPF_ALU:
returnA_ATOM;

caseBPF_LDX:
returnX_ATOM;

caseBPF_ST:
caseBPF_STX:
returns->k;

caseBPF_MISC:
returnBPF_MISCOP(s->code) ==BPF_TAX ? X_ATOM : A_ATOM;
	}
return-1;
}

/*
 * Compute the sets of registers used, defined, and killed by 'b'.
 *
 * "Used" means that a statement in 'b' uses the register before any
 * statement in 'b' defines it, i.e. it uses the value left in
 * that register by a predecessor block of this block.
 * "Defined" means that a statement in 'b' defines it.
 * "Killed" means that a statement in 'b' defines it before any
 * statement in 'b' uses it, i.e. it kills the value left in that
 * register by a predecessor block of this block.
 */
staticvoid
compute_local_ud(structblock*b)
{
structslist*s;
atomsetdef=0, use=0, killed=0;
intatom;

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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
atom=atomdef(&s->s);
if (atom >= 0) {
if (!ATOMELEM(use, atom))
killed |= ATOMMASK(atom);
def |= ATOMMASK(atom);
 }
	}
if (BPF_CLASS(b->s.code) ==BPF_JMP) {
/*
 * XXX - what about RET?
 */
atom=atomuse(&b->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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
	}

b->def=def;
b->kill=killed;
b->in_use=use;
}

/*
 * Assume graph is already leveled.
 */
staticvoid
find_ud(opt_state_t*opt_state, structblock*root)
{
inti, maxlevel;
structblock*p;

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

for (i=1; i <= maxlevel; ++i) {
for (p=opt_state->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;
 }
	}
}
staticvoid
init_val(opt_state_t*opt_state)
{
opt_state->curval=0;
opt_state->next_vnode=opt_state->vnode_base;
memset((char*)opt_state->vmap, 0, opt_state->maxval*sizeof(*opt_state->vmap));
memset((char*)opt_state->hashtbl, 0, sizeofopt_state->hashtbl);
}

/*
 * Because we really don't have an IR, this stuff is a little messy.
 *
 * This routine looks in the table of existing value number for a value
 * with generated from an operation with the specified opcode and
 * the specified values. If it finds it, it returns its value number,
 * otherwise it makes a new entry in the table and returns the
 * value number of that entry.
 */
staticbpf_u_int32
F(opt_state_t*opt_state, intcode, bpf_u_int32v0, bpf_u_int32v1)
{
u_inthash;
bpf_u_int32val;
structvalnode*p;

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

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

/*
 * Not found. Allocate a new value, and assign it a new
 * value number.
 *
 * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we
 * increment it before using it as the new value number, which
 * means we never assign VAL_UNKNOWN.
 *
 * XXX - unless we overflow, but we probably won't have 2^32-1
 * values; we treat 32 bits as effectively infinite.
 */
val=++opt_state->curval;
if (BPF_MODE(code) ==BPF_IMM&&
 (BPF_CLASS(code) ==BPF_LD||BPF_CLASS(code) ==BPF_LDX)) {
opt_state->vmap[val].const_val=v0;
opt_state->vmap[val].is_const=1;
	}
p=opt_state->next_vnode++;
p->val=val;
p->code=code;
p->v0=v0;
p->v1=v1;
p->next=opt_state->hashtbl[hash];
opt_state->hashtbl[hash] =p;

returnval;
}

staticinlinevoid
vstore(structstmt*s, bpf_u_int32*valp, bpf_u_int32newval, intalter)
{
if (alter&&newval!=VAL_UNKNOWN&&*valp==newval)
s->code=NOP;
else
*valp=newval;
}

/*
 * Do constant-folding on binary operators.
 * (Unary operators are handled elsewhere.)
 */
staticvoid
fold_op(opt_state_t*opt_state, structstmt*s, bpf_u_int32v0, bpf_u_int32v1)
{
bpf_u_int32a, b;

a=opt_state->vmap[v0].const_val;
b=opt_state->vmap[v1].const_val;

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

caseBPF_SUB:
a-=b;
break;

caseBPF_MUL:
a *= b;
break;

caseBPF_DIV:
if (b==0)
opt_error(opt_state, "division by zero");
a /= b;
break;

caseBPF_MOD:
if (b==0)
opt_error(opt_state, "modulus by zero");
a %= b;
break;

caseBPF_AND:
a &= b;
break;

caseBPF_OR:
a |= b;
break;

caseBPF_XOR:
a ^= b;
break;

caseBPF_LSH:
/*
 * A left shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a <<= b;
else
a=0;
break;

caseBPF_RSH:
/*
 * A right shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a >>= b;
else
a=0;
break;

default:
abort();
	}
s->k=a;
s->code=BPF_LD|BPF_IMM;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
}

staticinlinestructslist*
this_op(structslist*s)
{
while (s!=0&&s->s.code==NOP)
s=s->next;
returns;
}

staticvoid
opt_not(structblock*b)
{
structblock*tmp=JT(b);

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

staticvoid
opt_peep(opt_state_t*opt_state, structblock*b)
{
structslist*s;
structslist*next, *last;
bpf_u_int32val;

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

last=s;
for (/*empty*/; /*empty*/; s=next) {
/*
 * Skip over nops.
 */
s=this_op(s);
if (s==0)
break;	/* nothing left in the block */

/*
 * Find the next real instruction after that one
 * (skipping nops).
 */
next=this_op(s->next);
if (next==0)
break;	/* no next instruction */
last=next;

/*
 * st M[k]	-->	st M[k]
 * ldx M[k] tax
 */
if (s->s.code==BPF_ST&&
next->s.code== (BPF_LDX|BPF_MEM) &&
s->s.k==next->s.k) {
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
next->s.code=BPF_MISC|BPF_TAX;
 }
/*
 * ld #k	-->	ldx #k
 * tax txa
 */
if (s->s.code== (BPF_LD|BPF_IMM) &&
next->s.code== (BPF_MISC|BPF_TAX)) {
s->s.code=BPF_LDX|BPF_IMM;
next->s.code=BPF_MISC|BPF_TXA;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
 }
/*
 * This is an ugly special case, but it happens
 * when you say tcp[k] or udp[k] where k is a constant.
 */
if (s->s.code== (BPF_LD|BPF_IMM)) {
structslist*add, *tax, *ild;

/*
 * Check that X isn't used on exit from this
 * block (which the optimizer might cause).
 * We know the code generator won't generate
 * any local dependencies.
 */
if (ATOMELEM(b->out_use, X_ATOM))
continue;

/*
 * Check that the instruction following the ldi
 * is an addx, or it's an ldxms with an addx
 * following it (with 0 or more nops between the
 * ldxms and addx).
 */
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))
continue;

/*
 * Check that a tax follows that (with 0 or more
 * nops between them).
 */
tax=this_op(add->next);
if (tax==0||tax->s.code!= (BPF_MISC|BPF_TAX))
continue;

/*
 * Check that an ild follows that (with 0 or more
 * nops between them).
 */
ild=this_op(tax->next);
if (ild==0||BPF_CLASS(ild->s.code) !=BPF_LD||
BPF_MODE(ild->s.code) !=BPF_IND)
continue;
/*
 * We want to turn this sequence:
 *
 * (004) ldi #0x2 {s}
 * (005) ldxms [14] {next} -- optional
 * (006) addx {add}
 * (007) tax {tax}
 * (008) ild [x+0] {ild}
/*
 * 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 BPF code intermediate representation.
 */

#ifdefHAVE_CONFIG_H
#include<config.h>
#endif

#include<pcap-types.h>

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<setjmp.h>
#include<string.h>
#include<limits.h>/* for SIZE_MAX */
#include<errno.h>

#include"pcap-int.h"

#include"gencode.h"
#include"optimize.h"
#include"diag-control.h"

#ifdefHAVE_OS_PROTO_H
#include"os-proto.h"
#endif

#ifdefBDEBUG
/*
 * The internal "debug printout" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_optimizer_debug;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_optimizer_debug(intvalue);

PCAP_API_DEFvoid
pcap_set_optimizer_debug(intvalue)
{
pcap_optimizer_debug=value;
}

/*
 * The internal "print dot graph" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_print_dot_graph;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_print_dot_graph(intvalue);

PCAP_API_DEFvoid
pcap_set_print_dot_graph(intvalue)
{
pcap_print_dot_graph=value;
}

#endif

/*
 * lowest_set_bit().
 *
 * Takes a 32-bit integer as an argument.
 *
 * If handed a non-zero value, returns the index of the lowest set bit,
 * counting upwards from zero.
 *
 * If handed zero, the results are platform- and compiler-dependent.
 * Keep it out of the light, don't give it any water, don't feed it
 * after midnight, and don't pass zero to it.
 *
 * This is the same as the count of trailing zeroes in the word.
 */
#ifPCAP_IS_AT_LEAST_GNUC_VERSION(3,4)
/*
 * GCC 3.4 and later; we have __builtin_ctz().
 */
#definelowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
#elif defined(_MSC_VER)
/*
 * Visual Studio; we support only 2005 and later, so use
 * _BitScanForward().
 */
#include<intrin.h>

#ifndef__clang__
#pragma intrinsic(_BitScanForward)
#endif

static __forceinline u_int
lowest_set_bit(intmask)
{
unsigned longbit;

/*
 * Don't sign-extend mask if long is longer than int.
 * (It's currently not, in MSVC, even on 64-bit platforms, but....)
 */
if (_BitScanForward(&bit, (unsigned int)mask) ==0)
abort();	/* mask is zero */
return (u_int)bit;
}
#elif defined(MSDOS) && defined(__DJGPP__)
/*
 * MS-DOS with DJGPP, which declares ffs() in <string.h>, which
 * we've already included.
 */
#definelowest_set_bit(mask)	((u_int)(ffs((mask)) - 1))
#elif (defined(MSDOS) && defined(__WATCOMC__)) || defined(STRINGS_H_DECLARES_FFS)
/*
 * MS-DOS with Watcom C, which has <strings.h> and declares ffs() there,
 * or some other platform (UN*X conforming to a sufficient recent version
 * of the Single UNIX Specification).
 */
#include<strings.h>
#definelowest_set_bit(mask)	(u_int)((ffs((mask)) - 1))
#else
/*
 * None of the above.
 * Use a perfect-hash-function-based function.
 */
staticu_int
lowest_set_bit(intmask)
{
unsigned intv= (unsigned int)mask;

staticconstu_intMultiplyDeBruijnBitPosition[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]);
}
#endif

/*
 * Represents a deleted instruction.
 */
#defineNOP -1

/*
 * Register numbers for use-def values.
 * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory
 * location. A_ATOM is the accumulator and X_ATOM is the index
 * register.
 */
#defineA_ATOM BPF_MEMWORDS
#defineX_ATOM (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.
 */
#defineAX_ATOM N_ATOMS

/*
 * 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.
 */
structvalnode {
intcode;
bpf_u_int32v0, v1;
intval; /* the value number */
structvalnode*next;
};

/* Integer constants mapped with the load immediate opcode. */
#defineK(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)

structvmapinfo {
intis_const;
bpf_u_int32const_val;
};

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * A flag to indicate that further optimization is needed.
 * Iterative passes are continued until a given pass yields no
 * code simplification or branch movement.
 */
intdone;

/*
 * XXX - detect loops that do nothing but repeated AND/OR pullups
 * and edge moves.
 * If 100 passes in a row do nothing but that, treat that as a
 * sign that we're in a loop that just shuffles in a cycle in
 * which each pass just shuffles the code and we eventually
 * get back to the original configuration.
 *
 * XXX - we need a non-heuristic way of detecting, or preventing,
 * such a cycle.
 */
intnon_branch_movement_performed;

u_intn_blocks; /* number of blocks in the CFG; guaranteed to be > 0, as it's a RET instruction at a minimum */
structblock**blocks;
u_intn_edges; /* twice n_blocks, so guaranteed to be > 0 */
structedge**edges;

/*
 * A bit vector set representation of the dominators.
 * We round up the set size to the next power of two.
 */
u_intnodewords;	/* number of 32-bit words for a bit vector of "number of nodes" bits; guaranteed to be > 0 */
u_intedgewords;	/* number of 32-bit words for a bit vector of "number of edges" bits; guaranteed to be > 0 */
structblock**levels;
bpf_u_int32*space;

#defineBITS_PER_WORD (8*sizeof(bpf_u_int32))
/*
 * True if a is in uset {p}
 */
#defineSET_MEMBER(p, a) \
((p)[(unsigned)(a) / BITS_PER_WORD] & ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD)))

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

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

/*
 * a := a intersect b
 * n must be guaranteed to be > 0
 */
#defineSET_INTERSECT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &= *_y++; while (--_n != 0);\
}

/*
 * a := a - b
 * n must be guaranteed to be > 0
 */
#defineSET_SUBTRACT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &=~ *_y++; while (--_n != 0);\
}

/*
 * a := a union b
 * n must be guaranteed to be > 0
 */
#defineSET_UNION(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ |= *_y++; while (--_n != 0);\
}

usetall_dom_sets;
usetall_closure_sets;
usetall_edge_sets;

#defineMODULUS 213
structvalnode*hashtbl[MODULUS];
bpf_u_int32curval;
bpf_u_int32maxval;

structvmapinfo*vmap;
structvalnode*vnode_base;
structvalnode*next_vnode;
} opt_state_t;

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * 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.
 */
structbpf_insn*fstart;
structbpf_insn*ftail;
} conv_state_t;

staticvoidopt_init(opt_state_t*, structicode*);
staticvoidopt_cleanup(opt_state_t*);
staticvoidPCAP_NORETURNopt_error(opt_state_t*, constchar*, ...)
PCAP_PRINTFLIKE(2, 3);

staticvoidintern_blocks(opt_state_t*, structicode*);

staticvoidfind_inedges(opt_state_t*, structblock*);
#ifdefBDEBUG
staticvoidopt_dump(opt_state_t*, structicode*);
#endif

#ifndefMAX
#defineMAX(a,b) ((a)>(b)?(a):(b))
#endif

staticvoid
find_levels_r(opt_state_t*opt_state, structicode*ic, structblock*b)
{
intlevel;

if (isMarked(ic, b))
return;

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

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;
	} else
level=0;
b->level=level;
b->link=opt_state->levels[level];
opt_state->levels[level] =b;
}

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

/*
 * Find dominator relationships.
 * Assumes graph has been leveled.
 */
staticvoid
find_dom(opt_state_t*opt_state, structblock*root)
{
u_inti;
intlevel;
structblock*b;
bpf_u_int32*x;

/*
 * Initialize sets to contain all nodes.
 */
x=opt_state->all_dom_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
i=opt_state->n_blocks*opt_state->nodewords;
while (i!=0) {
--i;
*x++=0xFFFFFFFFU;
	}
/* Root starts off empty. */
for (i=opt_state->nodewords; i!=0;) {
--i;
root->dom[i] =0;
	}

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->dom, b->id);
if (JT(b) ==0)
continue;
SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
 }
	}
}

staticvoid
propedom(opt_state_t*opt_state, structedge*ep)
{
SET_INSERT(ep->edom, ep->id);
if (ep->succ) {
SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
	}
}

/*
 * Compute edge dominators.
 * Assumes graph has been leveled and predecessors established.
 */
staticvoid
find_edom(opt_state_t*opt_state, structblock*root)
{
u_inti;
usetx;
intlevel;
structblock*b;

x=opt_state->all_edge_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
for (i=opt_state->n_edges*opt_state->edgewords; i!=0; ) {
--i;
x[i] =0xFFFFFFFFU;
	}

/* root->level is the highest level no found. */
memset(root->et.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
memset(root->ef.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b!=0; b=b->link) {
propedom(opt_state, &b->et);
propedom(opt_state, &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.
 */
staticvoid
find_closure(opt_state_t*opt_state, structblock*root)
{
intlevel;
structblock*b;

/*
 * Initialize sets to contain no nodes.
 */
memset((char*)opt_state->all_closure_sets, 0,
opt_state->n_blocks*opt_state->nodewords*sizeof(*opt_state->all_closure_sets));

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->closure, b->id);
if (JT(b) ==0)
continue;
SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
 }
	}
}

/*
 * Return the register number that is used by s.
 *
 * Returns ATOM_A if A is used, ATOM_X if X is used, AX_ATOM if both A and X
 * are used, the scratch memory location's number if a scratch memory
 * location is used (e.g., 0 for M[0]), or -1 if none of those are used.
 *
 * The implementation should probably change to an array access.
 */
staticint
atomuse(structstmt*s)
{
	register intc=s->code;

if (c==NOP)
return-1;

switch (BPF_CLASS(c)) {

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

caseBPF_LD:
caseBPF_LDX:
/*
 * As there are fewer than 2^31 memory locations,
 * s->k should be convertible to int without problems.
 */
return (BPF_MODE(c) ==BPF_IND) ? X_ATOM :
 (BPF_MODE(c) ==BPF_MEM) ? (int)s->k : -1;

caseBPF_ST:
returnA_ATOM;

caseBPF_STX:
returnX_ATOM;

caseBPF_JMP:
caseBPF_ALU:
if (BPF_SRC(c) ==BPF_X)
returnAX_ATOM;
returnA_ATOM;

caseBPF_MISC:
returnBPF_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.
 */
staticint
atomdef(structstmt*s)
{
if (s->code==NOP)
return-1;

switch (BPF_CLASS(s->code)) {

caseBPF_LD:
caseBPF_ALU:
returnA_ATOM;

caseBPF_LDX:
returnX_ATOM;

caseBPF_ST:
caseBPF_STX:
returns->k;

caseBPF_MISC:
returnBPF_MISCOP(s->code) ==BPF_TAX ? X_ATOM : A_ATOM;
	}
return-1;
}

/*
 * Compute the sets of registers used, defined, and killed by 'b'.
 *
 * "Used" means that a statement in 'b' uses the register before any
 * statement in 'b' defines it, i.e. it uses the value left in
 * that register by a predecessor block of this block.
 * "Defined" means that a statement in 'b' defines it.
 * "Killed" means that a statement in 'b' defines it before any
 * statement in 'b' uses it, i.e. it kills the value left in that
 * register by a predecessor block of this block.
 */
staticvoid
compute_local_ud(structblock*b)
{
structslist*s;
atomsetdef=0, use=0, killed=0;
intatom;

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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
atom=atomdef(&s->s);
if (atom >= 0) {
if (!ATOMELEM(use, atom))
killed |= ATOMMASK(atom);
def |= ATOMMASK(atom);
 }
	}
if (BPF_CLASS(b->s.code) ==BPF_JMP) {
/*
 * XXX - what about RET?
 */
atom=atomuse(&b->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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
	}

b->def=def;
b->kill=killed;
b->in_use=use;
}

/*
 * Assume graph is already leveled.
 */
staticvoid
find_ud(opt_state_t*opt_state, structblock*root)
{
inti, maxlevel;
structblock*p;

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

for (i=1; i <= maxlevel; ++i) {
for (p=opt_state->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;
 }
	}
}
staticvoid
init_val(opt_state_t*opt_state)
{
opt_state->curval=0;
opt_state->next_vnode=opt_state->vnode_base;
memset((char*)opt_state->vmap, 0, opt_state->maxval*sizeof(*opt_state->vmap));
memset((char*)opt_state->hashtbl, 0, sizeofopt_state->hashtbl);
}

/*
 * Because we really don't have an IR, this stuff is a little messy.
 *
 * This routine looks in the table of existing value number for a value
 * with generated from an operation with the specified opcode and
 * the specified values. If it finds it, it returns its value number,
 * otherwise it makes a new entry in the table and returns the
 * value number of that entry.
 */
staticbpf_u_int32
F(opt_state_t*opt_state, intcode, bpf_u_int32v0, bpf_u_int32v1)
{
u_inthash;
bpf_u_int32val;
structvalnode*p;

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

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

/*
 * Not found. Allocate a new value, and assign it a new
 * value number.
 *
 * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we
 * increment it before using it as the new value number, which
 * means we never assign VAL_UNKNOWN.
 *
 * XXX - unless we overflow, but we probably won't have 2^32-1
 * values; we treat 32 bits as effectively infinite.
 */
val=++opt_state->curval;
if (BPF_MODE(code) ==BPF_IMM&&
 (BPF_CLASS(code) ==BPF_LD||BPF_CLASS(code) ==BPF_LDX)) {
opt_state->vmap[val].const_val=v0;
opt_state->vmap[val].is_const=1;
	}
p=opt_state->next_vnode++;
p->val=val;
p->code=code;
p->v0=v0;
p->v1=v1;
p->next=opt_state->hashtbl[hash];
opt_state->hashtbl[hash] =p;

returnval;
}

staticinlinevoid
vstore(structstmt*s, bpf_u_int32*valp, bpf_u_int32newval, intalter)
{
if (alter&&newval!=VAL_UNKNOWN&&*valp==newval)
s->code=NOP;
else
*valp=newval;
}

/*
 * Do constant-folding on binary operators.
 * (Unary operators are handled elsewhere.)
 */
staticvoid
fold_op(opt_state_t*opt_state, structstmt*s, bpf_u_int32v0, bpf_u_int32v1)
{
bpf_u_int32a, b;

a=opt_state->vmap[v0].const_val;
b=opt_state->vmap[v1].const_val;

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

caseBPF_SUB:
a-=b;
break;

caseBPF_MUL:
a *= b;
break;

caseBPF_DIV:
if (b==0)
opt_error(opt_state, "division by zero");
a /= b;
break;

caseBPF_MOD:
if (b==0)
opt_error(opt_state, "modulus by zero");
a %= b;
break;

caseBPF_AND:
a &= b;
break;

caseBPF_OR:
a |= b;
break;

caseBPF_XOR:
a ^= b;
break;

caseBPF_LSH:
/*
 * A left shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a <<= b;
else
a=0;
break;

caseBPF_RSH:
/*
 * A right shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a >>= b;
else
a=0;
break;

default:
abort();
	}
s->k=a;
s->code=BPF_LD|BPF_IMM;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
}

staticinlinestructslist*
this_op(structslist*s)
{
while (s!=0&&s->s.code==NOP)
s=s->next;
returns;
}

staticvoid
opt_not(structblock*b)
{
structblock*tmp=JT(b);

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

staticvoid
opt_peep(opt_state_t*opt_state, structblock*b)
{
structslist*s;
structslist*next, *last;
bpf_u_int32val;

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

last=s;
for (/*empty*/; /*empty*/; s=next) {
/*
 * Skip over nops.
 */
s=this_op(s);
if (s==0)
break;	/* nothing left in the block */

/*
 * Find the next real instruction after that one
 * (skipping nops).
 */
next=this_op(s->next);
if (next==0)
break;	/* no next instruction */
last=next;

/*
 * st M[k]	-->	st M[k]
 * ldx M[k] tax
 */
if (s->s.code==BPF_ST&&
next->s.code== (BPF_LDX|BPF_MEM) &&
s->s.k==next->s.k) {
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
next->s.code=BPF_MISC|BPF_TAX;
 }
/*
 * ld #k	-->	ldx #k
 * tax txa
 */
if (s->s.code== (BPF_LD|BPF_IMM) &&
next->s.code== (BPF_MISC|BPF_TAX)) {
s->s.code=BPF_LDX|BPF_IMM;
next->s.code=BPF_MISC|BPF_TXA;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
 }
/*
 * This is an ugly special case, but it happens
 * when you say tcp[k] or udp[k] where k is a constant.
 */
if (s->s.code== (BPF_LD|BPF_IMM)) {
structslist*add, *tax, *ild;

/*
 * Check that X isn't used on exit from this
 * block (which the optimizer might cause).
 * We know the code generator won't generate
 * any local dependencies.
 */
if (ATOMELEM(b->out_use, X_ATOM))
continue;

/*
 * Check that the instruction following the ldi
 * is an addx, or it's an ldxms with an addx
 * following it (with 0 or more nops between the
 * ldxms and addx).
 */
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))
continue;

/*
 * Check that a tax follows that (with 0 or more
 * nops between them).
 */
tax=this_op(add->next);
if (tax==0||tax->s.code!= (BPF_MISC|BPF_TAX))
continue;

/*
 * Check that an ild follows that (with 0 or more
 * nops between them).
 */
ild=this_op(tax->next);
if (ild==0||BPF_CLASS(ild->s.code) !=BPF_LD||
BPF_MODE(ild->s.code) !=BPF_IND)
continue;
/*
 * We want to turn this sequence:
 *
 * (004) ldi #0x2 {s}
 * (005) ldxms [14] {next} -- optional
 * (006) addx {add}
 * (007) tax {tax}
 * (008) ild [x+0] {ild}
/*
 * 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 BPF code intermediate representation.
 */

#ifdefHAVE_CONFIG_H
#include<config.h>
#endif

#include<pcap-types.h>

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<setjmp.h>
#include<string.h>
#include<limits.h>/* for SIZE_MAX */
#include<errno.h>

#include"pcap-int.h"

#include"gencode.h"
#include"optimize.h"
#include"diag-control.h"

#ifdefHAVE_OS_PROTO_H
#include"os-proto.h"
#endif

#ifdefBDEBUG
/*
 * The internal "debug printout" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_optimizer_debug;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_optimizer_debug(intvalue);

PCAP_API_DEFvoid
pcap_set_optimizer_debug(intvalue)
{
pcap_optimizer_debug=value;
}

/*
 * The internal "print dot graph" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_print_dot_graph;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_print_dot_graph(intvalue);

PCAP_API_DEFvoid
pcap_set_print_dot_graph(intvalue)
{
pcap_print_dot_graph=value;
}

#endif

/*
 * lowest_set_bit().
 *
 * Takes a 32-bit integer as an argument.
 *
 * If handed a non-zero value, returns the index of the lowest set bit,
 * counting upwards from zero.
 *
 * If handed zero, the results are platform- and compiler-dependent.
 * Keep it out of the light, don't give it any water, don't feed it
 * after midnight, and don't pass zero to it.
 *
 * This is the same as the count of trailing zeroes in the word.
 */
#ifPCAP_IS_AT_LEAST_GNUC_VERSION(3,4)
/*
 * GCC 3.4 and later; we have __builtin_ctz().
 */
#definelowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
#elif defined(_MSC_VER)
/*
 * Visual Studio; we support only 2005 and later, so use
 * _BitScanForward().
 */
#include<intrin.h>

#ifndef__clang__
#pragma intrinsic(_BitScanForward)
#endif

static __forceinline u_int
lowest_set_bit(intmask)
{
unsigned longbit;

/*
 * Don't sign-extend mask if long is longer than int.
 * (It's currently not, in MSVC, even on 64-bit platforms, but....)
 */
if (_BitScanForward(&bit, (unsigned int)mask) ==0)
abort();	/* mask is zero */
return (u_int)bit;
}
#elif defined(MSDOS) && defined(__DJGPP__)
/*
 * MS-DOS with DJGPP, which declares ffs() in <string.h>, which
 * we've already included.
 */
#definelowest_set_bit(mask)	((u_int)(ffs((mask)) - 1))
#elif (defined(MSDOS) && defined(__WATCOMC__)) || defined(STRINGS_H_DECLARES_FFS)
/*
 * MS-DOS with Watcom C, which has <strings.h> and declares ffs() there,
 * or some other platform (UN*X conforming to a sufficient recent version
 * of the Single UNIX Specification).
 */
#include<strings.h>
#definelowest_set_bit(mask)	(u_int)((ffs((mask)) - 1))
#else
/*
 * None of the above.
 * Use a perfect-hash-function-based function.
 */
staticu_int
lowest_set_bit(intmask)
{
unsigned intv= (unsigned int)mask;

staticconstu_intMultiplyDeBruijnBitPosition[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]);
}
#endif

/*
 * Represents a deleted instruction.
 */
#defineNOP -1

/*
 * Register numbers for use-def values.
 * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory
 * location. A_ATOM is the accumulator and X_ATOM is the index
 * register.
 */
#defineA_ATOM BPF_MEMWORDS
#defineX_ATOM (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.
 */
#defineAX_ATOM N_ATOMS

/*
 * 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.
 */
structvalnode {
intcode;
bpf_u_int32v0, v1;
intval; /* the value number */
structvalnode*next;
};

/* Integer constants mapped with the load immediate opcode. */
#defineK(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)

structvmapinfo {
intis_const;
bpf_u_int32const_val;
};

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * A flag to indicate that further optimization is needed.
 * Iterative passes are continued until a given pass yields no
 * code simplification or branch movement.
 */
intdone;

/*
 * XXX - detect loops that do nothing but repeated AND/OR pullups
 * and edge moves.
 * If 100 passes in a row do nothing but that, treat that as a
 * sign that we're in a loop that just shuffles in a cycle in
 * which each pass just shuffles the code and we eventually
 * get back to the original configuration.
 *
 * XXX - we need a non-heuristic way of detecting, or preventing,
 * such a cycle.
 */
intnon_branch_movement_performed;

u_intn_blocks; /* number of blocks in the CFG; guaranteed to be > 0, as it's a RET instruction at a minimum */
structblock**blocks;
u_intn_edges; /* twice n_blocks, so guaranteed to be > 0 */
structedge**edges;

/*
 * A bit vector set representation of the dominators.
 * We round up the set size to the next power of two.
 */
u_intnodewords;	/* number of 32-bit words for a bit vector of "number of nodes" bits; guaranteed to be > 0 */
u_intedgewords;	/* number of 32-bit words for a bit vector of "number of edges" bits; guaranteed to be > 0 */
structblock**levels;
bpf_u_int32*space;

#defineBITS_PER_WORD (8*sizeof(bpf_u_int32))
/*
 * True if a is in uset {p}
 */
#defineSET_MEMBER(p, a) \
((p)[(unsigned)(a) / BITS_PER_WORD] & ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD)))

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

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

/*
 * a := a intersect b
 * n must be guaranteed to be > 0
 */
#defineSET_INTERSECT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &= *_y++; while (--_n != 0);\
}

/*
 * a := a - b
 * n must be guaranteed to be > 0
 */
#defineSET_SUBTRACT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &=~ *_y++; while (--_n != 0);\
}

/*
 * a := a union b
 * n must be guaranteed to be > 0
 */
#defineSET_UNION(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ |= *_y++; while (--_n != 0);\
}

usetall_dom_sets;
usetall_closure_sets;
usetall_edge_sets;

#defineMODULUS 213
structvalnode*hashtbl[MODULUS];
bpf_u_int32curval;
bpf_u_int32maxval;

structvmapinfo*vmap;
structvalnode*vnode_base;
structvalnode*next_vnode;
} opt_state_t;

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * 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.
 */
structbpf_insn*fstart;
structbpf_insn*ftail;
} conv_state_t;

staticvoidopt_init(opt_state_t*, structicode*);
staticvoidopt_cleanup(opt_state_t*);
staticvoidPCAP_NORETURNopt_error(opt_state_t*, constchar*, ...)
PCAP_PRINTFLIKE(2, 3);

staticvoidintern_blocks(opt_state_t*, structicode*);

staticvoidfind_inedges(opt_state_t*, structblock*);
#ifdefBDEBUG
staticvoidopt_dump(opt_state_t*, structicode*);
#endif

#ifndefMAX
#defineMAX(a,b) ((a)>(b)?(a):(b))
#endif

staticvoid
find_levels_r(opt_state_t*opt_state, structicode*ic, structblock*b)
{
intlevel;

if (isMarked(ic, b))
return;

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

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;
	} else
level=0;
b->level=level;
b->link=opt_state->levels[level];
opt_state->levels[level] =b;
}

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

/*
 * Find dominator relationships.
 * Assumes graph has been leveled.
 */
staticvoid
find_dom(opt_state_t*opt_state, structblock*root)
{
u_inti;
intlevel;
structblock*b;
bpf_u_int32*x;

/*
 * Initialize sets to contain all nodes.
 */
x=opt_state->all_dom_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
i=opt_state->n_blocks*opt_state->nodewords;
while (i!=0) {
--i;
*x++=0xFFFFFFFFU;
	}
/* Root starts off empty. */
for (i=opt_state->nodewords; i!=0;) {
--i;
root->dom[i] =0;
	}

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->dom, b->id);
if (JT(b) ==0)
continue;
SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
 }
	}
}

staticvoid
propedom(opt_state_t*opt_state, structedge*ep)
{
SET_INSERT(ep->edom, ep->id);
if (ep->succ) {
SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
	}
}

/*
 * Compute edge dominators.
 * Assumes graph has been leveled and predecessors established.
 */
staticvoid
find_edom(opt_state_t*opt_state, structblock*root)
{
u_inti;
usetx;
intlevel;
structblock*b;

x=opt_state->all_edge_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
for (i=opt_state->n_edges*opt_state->edgewords; i!=0; ) {
--i;
x[i] =0xFFFFFFFFU;
	}

/* root->level is the highest level no found. */
memset(root->et.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
memset(root->ef.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b!=0; b=b->link) {
propedom(opt_state, &b->et);
propedom(opt_state, &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.
 */
staticvoid
find_closure(opt_state_t*opt_state, structblock*root)
{
intlevel;
structblock*b;

/*
 * Initialize sets to contain no nodes.
 */
memset((char*)opt_state->all_closure_sets, 0,
opt_state->n_blocks*opt_state->nodewords*sizeof(*opt_state->all_closure_sets));

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->closure, b->id);
if (JT(b) ==0)
continue;
SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
 }
	}
}

/*
 * Return the register number that is used by s.
 *
 * Returns ATOM_A if A is used, ATOM_X if X is used, AX_ATOM if both A and X
 * are used, the scratch memory location's number if a scratch memory
 * location is used (e.g., 0 for M[0]), or -1 if none of those are used.
 *
 * The implementation should probably change to an array access.
 */
staticint
atomuse(structstmt*s)
{
	register intc=s->code;

if (c==NOP)
return-1;

switch (BPF_CLASS(c)) {

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

caseBPF_LD:
caseBPF_LDX:
/*
 * As there are fewer than 2^31 memory locations,
 * s->k should be convertible to int without problems.
 */
return (BPF_MODE(c) ==BPF_IND) ? X_ATOM :
 (BPF_MODE(c) ==BPF_MEM) ? (int)s->k : -1;

caseBPF_ST:
returnA_ATOM;

caseBPF_STX:
returnX_ATOM;

caseBPF_JMP:
caseBPF_ALU:
if (BPF_SRC(c) ==BPF_X)
returnAX_ATOM;
returnA_ATOM;

caseBPF_MISC:
returnBPF_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.
 */
staticint
atomdef(structstmt*s)
{
if (s->code==NOP)
return-1;

switch (BPF_CLASS(s->code)) {

caseBPF_LD:
caseBPF_ALU:
returnA_ATOM;

caseBPF_LDX:
returnX_ATOM;

caseBPF_ST:
caseBPF_STX:
returns->k;

caseBPF_MISC:
returnBPF_MISCOP(s->code) ==BPF_TAX ? X_ATOM : A_ATOM;
	}
return-1;
}

/*
 * Compute the sets of registers used, defined, and killed by 'b'.
 *
 * "Used" means that a statement in 'b' uses the register before any
 * statement in 'b' defines it, i.e. it uses the value left in
 * that register by a predecessor block of this block.
 * "Defined" means that a statement in 'b' defines it.
 * "Killed" means that a statement in 'b' defines it before any
 * statement in 'b' uses it, i.e. it kills the value left in that
 * register by a predecessor block of this block.
 */
staticvoid
compute_local_ud(structblock*b)
{
structslist*s;
atomsetdef=0, use=0, killed=0;
intatom;

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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
atom=atomdef(&s->s);
if (atom >= 0) {
if (!ATOMELEM(use, atom))
killed |= ATOMMASK(atom);
def |= ATOMMASK(atom);
 }
	}
if (BPF_CLASS(b->s.code) ==BPF_JMP) {
/*
 * XXX - what about RET?
 */
atom=atomuse(&b->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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
	}

b->def=def;
b->kill=killed;
b->in_use=use;
}

/*
 * Assume graph is already leveled.
 */
staticvoid
find_ud(opt_state_t*opt_state, structblock*root)
{
inti, maxlevel;
structblock*p;

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

for (i=1; i <= maxlevel; ++i) {
for (p=opt_state->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;
 }
	}
}
staticvoid
init_val(opt_state_t*opt_state)
{
opt_state->curval=0;
opt_state->next_vnode=opt_state->vnode_base;
memset((char*)opt_state->vmap, 0, opt_state->maxval*sizeof(*opt_state->vmap));
memset((char*)opt_state->hashtbl, 0, sizeofopt_state->hashtbl);
}

/*
 * Because we really don't have an IR, this stuff is a little messy.
 *
 * This routine looks in the table of existing value number for a value
 * with generated from an operation with the specified opcode and
 * the specified values. If it finds it, it returns its value number,
 * otherwise it makes a new entry in the table and returns the
 * value number of that entry.
 */
staticbpf_u_int32
F(opt_state_t*opt_state, intcode, bpf_u_int32v0, bpf_u_int32v1)
{
u_inthash;
bpf_u_int32val;
structvalnode*p;

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

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

/*
 * Not found. Allocate a new value, and assign it a new
 * value number.
 *
 * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we
 * increment it before using it as the new value number, which
 * means we never assign VAL_UNKNOWN.
 *
 * XXX - unless we overflow, but we probably won't have 2^32-1
 * values; we treat 32 bits as effectively infinite.
 */
val=++opt_state->curval;
if (BPF_MODE(code) ==BPF_IMM&&
 (BPF_CLASS(code) ==BPF_LD||BPF_CLASS(code) ==BPF_LDX)) {
opt_state->vmap[val].const_val=v0;
opt_state->vmap[val].is_const=1;
	}
p=opt_state->next_vnode++;
p->val=val;
p->code=code;
p->v0=v0;
p->v1=v1;
p->next=opt_state->hashtbl[hash];
opt_state->hashtbl[hash] =p;

returnval;
}

staticinlinevoid
vstore(structstmt*s, bpf_u_int32*valp, bpf_u_int32newval, intalter)
{
if (alter&&newval!=VAL_UNKNOWN&&*valp==newval)
s->code=NOP;
else
*valp=newval;
}

/*
 * Do constant-folding on binary operators.
 * (Unary operators are handled elsewhere.)
 */
staticvoid
fold_op(opt_state_t*opt_state, structstmt*s, bpf_u_int32v0, bpf_u_int32v1)
{
bpf_u_int32a, b;

a=opt_state->vmap[v0].const_val;
b=opt_state->vmap[v1].const_val;

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

caseBPF_SUB:
a-=b;
break;

caseBPF_MUL:
a *= b;
break;

caseBPF_DIV:
if (b==0)
opt_error(opt_state, "division by zero");
a /= b;
break;

caseBPF_MOD:
if (b==0)
opt_error(opt_state, "modulus by zero");
a %= b;
break;

caseBPF_AND:
a &= b;
break;

caseBPF_OR:
a |= b;
break;

caseBPF_XOR:
a ^= b;
break;

caseBPF_LSH:
/*
 * A left shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a <<= b;
else
a=0;
break;

caseBPF_RSH:
/*
 * A right shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a >>= b;
else
a=0;
break;

default:
abort();
	}
s->k=a;
s->code=BPF_LD|BPF_IMM;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
}

staticinlinestructslist*
this_op(structslist*s)
{
while (s!=0&&s->s.code==NOP)
s=s->next;
returns;
}

staticvoid
opt_not(structblock*b)
{
structblock*tmp=JT(b);

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

staticvoid
opt_peep(opt_state_t*opt_state, structblock*b)
{
structslist*s;
structslist*next, *last;
bpf_u_int32val;

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

last=s;
for (/*empty*/; /*empty*/; s=next) {
/*
 * Skip over nops.
 */
s=this_op(s);
if (s==0)
break;	/* nothing left in the block */

/*
 * Find the next real instruction after that one
 * (skipping nops).
 */
next=this_op(s->next);
if (next==0)
break;	/* no next instruction */
last=next;

/*
 * st M[k]	-->	st M[k]
 * ldx M[k] tax
 */
if (s->s.code==BPF_ST&&
next->s.code== (BPF_LDX|BPF_MEM) &&
s->s.k==next->s.k) {
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
next->s.code=BPF_MISC|BPF_TAX;
 }
/*
 * ld #k	-->	ldx #k
 * tax txa
 */
if (s->s.code== (BPF_LD|BPF_IMM) &&
next->s.code== (BPF_MISC|BPF_TAX)) {
s->s.code=BPF_LDX|BPF_IMM;
next->s.code=BPF_MISC|BPF_TXA;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
 }
/*
 * This is an ugly special case, but it happens
 * when you say tcp[k] or udp[k] where k is a constant.
 */
if (s->s.code== (BPF_LD|BPF_IMM)) {
structslist*add, *tax, *ild;

/*
 * Check that X isn't used on exit from this
 * block (which the optimizer might cause).
 * We know the code generator won't generate
 * any local dependencies.
 */
if (ATOMELEM(b->out_use, X_ATOM))
continue;

/*
 * Check that the instruction following the ldi
 * is an addx, or it's an ldxms with an addx
 * following it (with 0 or more nops between the
 * ldxms and addx).
 */
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))
continue;

/*
 * Check that a tax follows that (with 0 or more
 * nops between them).
 */
tax=this_op(add->next);
if (tax==0||tax->s.code!= (BPF_MISC|BPF_TAX))
continue;

/*
 * Check that an ild follows that (with 0 or more
 * nops between them).
 */
ild=this_op(tax->next);
if (ild==0||BPF_CLASS(ild->s.code) !=BPF_LD||
BPF_MODE(ild->s.code) !=BPF_IND)
continue;
/*
 * We want to turn this sequence:
 *
 * (004) ldi #0x2 {s}
 * (005) ldxms [14] {next} -- optional
 * (006) addx {add}
 * (007) tax {tax}
 * (008) ild [x+0] {ild}
/*
 * 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 BPF code intermediate representation.
 */

#ifdefHAVE_CONFIG_H
#include<config.h>
#endif

#include<pcap-types.h>

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<setjmp.h>
#include<string.h>
#include<limits.h>/* for SIZE_MAX */
#include<errno.h>

#include"pcap-int.h"

#include"gencode.h"
#include"optimize.h"
#include"diag-control.h"

#ifdefHAVE_OS_PROTO_H
#include"os-proto.h"
#endif

#ifdefBDEBUG
/*
 * The internal "debug printout" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_optimizer_debug;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_optimizer_debug(intvalue);

PCAP_API_DEFvoid
pcap_set_optimizer_debug(intvalue)
{
pcap_optimizer_debug=value;
}

/*
 * The internal "print dot graph" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_print_dot_graph;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_print_dot_graph(intvalue);

PCAP_API_DEFvoid
pcap_set_print_dot_graph(intvalue)
{
pcap_print_dot_graph=value;
}

#endif

/*
 * lowest_set_bit().
 *
 * Takes a 32-bit integer as an argument.
 *
 * If handed a non-zero value, returns the index of the lowest set bit,
 * counting upwards from zero.
 *
 * If handed zero, the results are platform- and compiler-dependent.
 * Keep it out of the light, don't give it any water, don't feed it
 * after midnight, and don't pass zero to it.
 *
 * This is the same as the count of trailing zeroes in the word.
 */
#ifPCAP_IS_AT_LEAST_GNUC_VERSION(3,4)
/*
 * GCC 3.4 and later; we have __builtin_ctz().
 */
#definelowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
#elif defined(_MSC_VER)
/*
 * Visual Studio; we support only 2005 and later, so use
 * _BitScanForward().
 */
#include<intrin.h>

#ifndef__clang__
#pragma intrinsic(_BitScanForward)
#endif

static __forceinline u_int
lowest_set_bit(intmask)
{
unsigned longbit;

/*
 * Don't sign-extend mask if long is longer than int.
 * (It's currently not, in MSVC, even on 64-bit platforms, but....)
 */
if (_BitScanForward(&bit, (unsigned int)mask) ==0)
abort();	/* mask is zero */
return (u_int)bit;
}
#elif defined(MSDOS) && defined(__DJGPP__)
/*
 * MS-DOS with DJGPP, which declares ffs() in <string.h>, which
 * we've already included.
 */
#definelowest_set_bit(mask)	((u_int)(ffs((mask)) - 1))
#elif (defined(MSDOS) && defined(__WATCOMC__)) || defined(STRINGS_H_DECLARES_FFS)
/*
 * MS-DOS with Watcom C, which has <strings.h> and declares ffs() there,
 * or some other platform (UN*X conforming to a sufficient recent version
 * of the Single UNIX Specification).
 */
#include<strings.h>
#definelowest_set_bit(mask)	(u_int)((ffs((mask)) - 1))
#else
/*
 * None of the above.
 * Use a perfect-hash-function-based function.
 */
staticu_int
lowest_set_bit(intmask)
{
unsigned intv= (unsigned int)mask;

staticconstu_intMultiplyDeBruijnBitPosition[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]);
}
#endif

/*
 * Represents a deleted instruction.
 */
#defineNOP -1

/*
 * Register numbers for use-def values.
 * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory
 * location. A_ATOM is the accumulator and X_ATOM is the index
 * register.
 */
#defineA_ATOM BPF_MEMWORDS
#defineX_ATOM (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.
 */
#defineAX_ATOM N_ATOMS

/*
 * 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.
 */
structvalnode {
intcode;
bpf_u_int32v0, v1;
intval; /* the value number */
structvalnode*next;
};

/* Integer constants mapped with the load immediate opcode. */
#defineK(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)

structvmapinfo {
intis_const;
bpf_u_int32const_val;
};

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * A flag to indicate that further optimization is needed.
 * Iterative passes are continued until a given pass yields no
 * code simplification or branch movement.
 */
intdone;

/*
 * XXX - detect loops that do nothing but repeated AND/OR pullups
 * and edge moves.
 * If 100 passes in a row do nothing but that, treat that as a
 * sign that we're in a loop that just shuffles in a cycle in
 * which each pass just shuffles the code and we eventually
 * get back to the original configuration.
 *
 * XXX - we need a non-heuristic way of detecting, or preventing,
 * such a cycle.
 */
intnon_branch_movement_performed;

u_intn_blocks; /* number of blocks in the CFG; guaranteed to be > 0, as it's a RET instruction at a minimum */
structblock**blocks;
u_intn_edges; /* twice n_blocks, so guaranteed to be > 0 */
structedge**edges;

/*
 * A bit vector set representation of the dominators.
 * We round up the set size to the next power of two.
 */
u_intnodewords;	/* number of 32-bit words for a bit vector of "number of nodes" bits; guaranteed to be > 0 */
u_intedgewords;	/* number of 32-bit words for a bit vector of "number of edges" bits; guaranteed to be > 0 */
structblock**levels;
bpf_u_int32*space;

#defineBITS_PER_WORD (8*sizeof(bpf_u_int32))
/*
 * True if a is in uset {p}
 */
#defineSET_MEMBER(p, a) \
((p)[(unsigned)(a) / BITS_PER_WORD] & ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD)))

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

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

/*
 * a := a intersect b
 * n must be guaranteed to be > 0
 */
#defineSET_INTERSECT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &= *_y++; while (--_n != 0);\
}

/*
 * a := a - b
 * n must be guaranteed to be > 0
 */
#defineSET_SUBTRACT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &=~ *_y++; while (--_n != 0);\
}

/*
 * a := a union b
 * n must be guaranteed to be > 0
 */
#defineSET_UNION(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ |= *_y++; while (--_n != 0);\
}

usetall_dom_sets;
usetall_closure_sets;
usetall_edge_sets;

#defineMODULUS 213
structvalnode*hashtbl[MODULUS];
bpf_u_int32curval;
bpf_u_int32maxval;

structvmapinfo*vmap;
structvalnode*vnode_base;
structvalnode*next_vnode;
} opt_state_t;

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * 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.
 */
structbpf_insn*fstart;
structbpf_insn*ftail;
} conv_state_t;

staticvoidopt_init(opt_state_t*, structicode*);
staticvoidopt_cleanup(opt_state_t*);
staticvoidPCAP_NORETURNopt_error(opt_state_t*, constchar*, ...)
PCAP_PRINTFLIKE(2, 3);

staticvoidintern_blocks(opt_state_t*, structicode*);

staticvoidfind_inedges(opt_state_t*, structblock*);
#ifdefBDEBUG
staticvoidopt_dump(opt_state_t*, structicode*);
#endif

#ifndefMAX
#defineMAX(a,b) ((a)>(b)?(a):(b))
#endif

staticvoid
find_levels_r(opt_state_t*opt_state, structicode*ic, structblock*b)
{
intlevel;

if (isMarked(ic, b))
return;

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

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;
	} else
level=0;
b->level=level;
b->link=opt_state->levels[level];
opt_state->levels[level] =b;
}

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

/*
 * Find dominator relationships.
 * Assumes graph has been leveled.
 */
staticvoid
find_dom(opt_state_t*opt_state, structblock*root)
{
u_inti;
intlevel;
structblock*b;
bpf_u_int32*x;

/*
 * Initialize sets to contain all nodes.
 */
x=opt_state->all_dom_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
i=opt_state->n_blocks*opt_state->nodewords;
while (i!=0) {
--i;
*x++=0xFFFFFFFFU;
	}
/* Root starts off empty. */
for (i=opt_state->nodewords; i!=0;) {
--i;
root->dom[i] =0;
	}

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->dom, b->id);
if (JT(b) ==0)
continue;
SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
 }
	}
}

staticvoid
propedom(opt_state_t*opt_state, structedge*ep)
{
SET_INSERT(ep->edom, ep->id);
if (ep->succ) {
SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
	}
}

/*
 * Compute edge dominators.
 * Assumes graph has been leveled and predecessors established.
 */
staticvoid
find_edom(opt_state_t*opt_state, structblock*root)
{
u_inti;
usetx;
intlevel;
structblock*b;

x=opt_state->all_edge_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
for (i=opt_state->n_edges*opt_state->edgewords; i!=0; ) {
--i;
x[i] =0xFFFFFFFFU;
	}

/* root->level is the highest level no found. */
memset(root->et.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
memset(root->ef.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b!=0; b=b->link) {
propedom(opt_state, &b->et);
propedom(opt_state, &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.
 */
staticvoid
find_closure(opt_state_t*opt_state, structblock*root)
{
intlevel;
structblock*b;

/*
 * Initialize sets to contain no nodes.
 */
memset((char*)opt_state->all_closure_sets, 0,
opt_state->n_blocks*opt_state->nodewords*sizeof(*opt_state->all_closure_sets));

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->closure, b->id);
if (JT(b) ==0)
continue;
SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
 }
	}
}

/*
 * Return the register number that is used by s.
 *
 * Returns ATOM_A if A is used, ATOM_X if X is used, AX_ATOM if both A and X
 * are used, the scratch memory location's number if a scratch memory
 * location is used (e.g., 0 for M[0]), or -1 if none of those are used.
 *
 * The implementation should probably change to an array access.
 */
staticint
atomuse(structstmt*s)
{
	register intc=s->code;

if (c==NOP)
return-1;

switch (BPF_CLASS(c)) {

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

caseBPF_LD:
caseBPF_LDX:
/*
 * As there are fewer than 2^31 memory locations,
 * s->k should be convertible to int without problems.
 */
return (BPF_MODE(c) ==BPF_IND) ? X_ATOM :
 (BPF_MODE(c) ==BPF_MEM) ? (int)s->k : -1;

caseBPF_ST:
returnA_ATOM;

caseBPF_STX:
returnX_ATOM;

caseBPF_JMP:
caseBPF_ALU:
if (BPF_SRC(c) ==BPF_X)
returnAX_ATOM;
returnA_ATOM;

caseBPF_MISC:
returnBPF_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.
 */
staticint
atomdef(structstmt*s)
{
if (s->code==NOP)
return-1;

switch (BPF_CLASS(s->code)) {

caseBPF_LD:
caseBPF_ALU:
returnA_ATOM;

caseBPF_LDX:
returnX_ATOM;

caseBPF_ST:
caseBPF_STX:
returns->k;

caseBPF_MISC:
returnBPF_MISCOP(s->code) ==BPF_TAX ? X_ATOM : A_ATOM;
	}
return-1;
}

/*
 * Compute the sets of registers used, defined, and killed by 'b'.
 *
 * "Used" means that a statement in 'b' uses the register before any
 * statement in 'b' defines it, i.e. it uses the value left in
 * that register by a predecessor block of this block.
 * "Defined" means that a statement in 'b' defines it.
 * "Killed" means that a statement in 'b' defines it before any
 * statement in 'b' uses it, i.e. it kills the value left in that
 * register by a predecessor block of this block.
 */
staticvoid
compute_local_ud(structblock*b)
{
structslist*s;
atomsetdef=0, use=0, killed=0;
intatom;

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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
atom=atomdef(&s->s);
if (atom >= 0) {
if (!ATOMELEM(use, atom))
killed |= ATOMMASK(atom);
def |= ATOMMASK(atom);
 }
	}
if (BPF_CLASS(b->s.code) ==BPF_JMP) {
/*
 * XXX - what about RET?
 */
atom=atomuse(&b->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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
	}

b->def=def;
b->kill=killed;
b->in_use=use;
}

/*
 * Assume graph is already leveled.
 */
staticvoid
find_ud(opt_state_t*opt_state, structblock*root)
{
inti, maxlevel;
structblock*p;

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

for (i=1; i <= maxlevel; ++i) {
for (p=opt_state->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;
 }
	}
}
staticvoid
init_val(opt_state_t*opt_state)
{
opt_state->curval=0;
opt_state->next_vnode=opt_state->vnode_base;
memset((char*)opt_state->vmap, 0, opt_state->maxval*sizeof(*opt_state->vmap));
memset((char*)opt_state->hashtbl, 0, sizeofopt_state->hashtbl);
}

/*
 * Because we really don't have an IR, this stuff is a little messy.
 *
 * This routine looks in the table of existing value number for a value
 * with generated from an operation with the specified opcode and
 * the specified values. If it finds it, it returns its value number,
 * otherwise it makes a new entry in the table and returns the
 * value number of that entry.
 */
staticbpf_u_int32
F(opt_state_t*opt_state, intcode, bpf_u_int32v0, bpf_u_int32v1)
{
u_inthash;
bpf_u_int32val;
structvalnode*p;

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

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

/*
 * Not found. Allocate a new value, and assign it a new
 * value number.
 *
 * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we
 * increment it before using it as the new value number, which
 * means we never assign VAL_UNKNOWN.
 *
 * XXX - unless we overflow, but we probably won't have 2^32-1
 * values; we treat 32 bits as effectively infinite.
 */
val=++opt_state->curval;
if (BPF_MODE(code) ==BPF_IMM&&
 (BPF_CLASS(code) ==BPF_LD||BPF_CLASS(code) ==BPF_LDX)) {
opt_state->vmap[val].const_val=v0;
opt_state->vmap[val].is_const=1;
	}
p=opt_state->next_vnode++;
p->val=val;
p->code=code;
p->v0=v0;
p->v1=v1;
p->next=opt_state->hashtbl[hash];
opt_state->hashtbl[hash] =p;

returnval;
}

staticinlinevoid
vstore(structstmt*s, bpf_u_int32*valp, bpf_u_int32newval, intalter)
{
if (alter&&newval!=VAL_UNKNOWN&&*valp==newval)
s->code=NOP;
else
*valp=newval;
}

/*
 * Do constant-folding on binary operators.
 * (Unary operators are handled elsewhere.)
 */
staticvoid
fold_op(opt_state_t*opt_state, structstmt*s, bpf_u_int32v0, bpf_u_int32v1)
{
bpf_u_int32a, b;

a=opt_state->vmap[v0].const_val;
b=opt_state->vmap[v1].const_val;

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

caseBPF_SUB:
a-=b;
break;

caseBPF_MUL:
a *= b;
break;

caseBPF_DIV:
if (b==0)
opt_error(opt_state, "division by zero");
a /= b;
break;

caseBPF_MOD:
if (b==0)
opt_error(opt_state, "modulus by zero");
a %= b;
break;

caseBPF_AND:
a &= b;
break;

caseBPF_OR:
a |= b;
break;

caseBPF_XOR:
a ^= b;
break;

caseBPF_LSH:
/*
 * A left shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a <<= b;
else
a=0;
break;

caseBPF_RSH:
/*
 * A right shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a >>= b;
else
a=0;
break;

default:
abort();
	}
s->k=a;
s->code=BPF_LD|BPF_IMM;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
}

staticinlinestructslist*
this_op(structslist*s)
{
while (s!=0&&s->s.code==NOP)
s=s->next;
returns;
}

staticvoid
opt_not(structblock*b)
{
structblock*tmp=JT(b);

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

staticvoid
opt_peep(opt_state_t*opt_state, structblock*b)
{
structslist*s;
structslist*next, *last;
bpf_u_int32val;

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

last=s;
for (/*empty*/; /*empty*/; s=next) {
/*
 * Skip over nops.
 */
s=this_op(s);
if (s==0)
break;	/* nothing left in the block */

/*
 * Find the next real instruction after that one
 * (skipping nops).
 */
next=this_op(s->next);
if (next==0)
break;	/* no next instruction */
last=next;

/*
 * st M[k]	-->	st M[k]
 * ldx M[k] tax
 */
if (s->s.code==BPF_ST&&
next->s.code== (BPF_LDX|BPF_MEM) &&
s->s.k==next->s.k) {
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
next->s.code=BPF_MISC|BPF_TAX;
 }
/*
 * ld #k	-->	ldx #k
 * tax txa
 */
if (s->s.code== (BPF_LD|BPF_IMM) &&
next->s.code== (BPF_MISC|BPF_TAX)) {
s->s.code=BPF_LDX|BPF_IMM;
next->s.code=BPF_MISC|BPF_TXA;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
 }
/*
 * This is an ugly special case, but it happens
 * when you say tcp[k] or udp[k] where k is a constant.
 */
if (s->s.code== (BPF_LD|BPF_IMM)) {
structslist*add, *tax, *ild;

/*
 * Check that X isn't used on exit from this
 * block (which the optimizer might cause).
 * We know the code generator won't generate
 * any local dependencies.
 */
if (ATOMELEM(b->out_use, X_ATOM))
continue;

/*
 * Check that the instruction following the ldi
 * is an addx, or it's an ldxms with an addx
 * following it (with 0 or more nops between the
 * ldxms and addx).
 */
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))
continue;

/*
 * Check that a tax follows that (with 0 or more
 * nops between them).
 */
tax=this_op(add->next);
if (tax==0||tax->s.code!= (BPF_MISC|BPF_TAX))
continue;

/*
 * Check that an ild follows that (with 0 or more
 * nops between them).
 */
ild=this_op(tax->next);
if (ild==0||BPF_CLASS(ild->s.code) !=BPF_LD||
BPF_MODE(ild->s.code) !=BPF_IND)
continue;
/*
 * We want to turn this sequence:
 *
 * (004) ldi #0x2 {s}
 * (005) ldxms [14] {next} -- optional
 * (006) addx {add}
 * (007) tax {tax}
 * (008) ild [x+0] {ild}
/*
 * 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 BPF code intermediate representation.
 */

#ifdefHAVE_CONFIG_H
#include<config.h>
#endif

#include<pcap-types.h>

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<setjmp.h>
#include<string.h>
#include<limits.h>/* for SIZE_MAX */
#include<errno.h>

#include"pcap-int.h"

#include"gencode.h"
#include"optimize.h"
#include"diag-control.h"

#ifdefHAVE_OS_PROTO_H
#include"os-proto.h"
#endif

#ifdefBDEBUG
/*
 * The internal "debug printout" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_optimizer_debug;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_optimizer_debug(intvalue);

PCAP_API_DEFvoid
pcap_set_optimizer_debug(intvalue)
{
pcap_optimizer_debug=value;
}

/*
 * The internal "print dot graph" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_print_dot_graph;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_print_dot_graph(intvalue);

PCAP_API_DEFvoid
pcap_set_print_dot_graph(intvalue)
{
pcap_print_dot_graph=value;
}

#endif

/*
 * lowest_set_bit().
 *
 * Takes a 32-bit integer as an argument.
 *
 * If handed a non-zero value, returns the index of the lowest set bit,
 * counting upwards from zero.
 *
 * If handed zero, the results are platform- and compiler-dependent.
 * Keep it out of the light, don't give it any water, don't feed it
 * after midnight, and don't pass zero to it.
 *
 * This is the same as the count of trailing zeroes in the word.
 */
#ifPCAP_IS_AT_LEAST_GNUC_VERSION(3,4)
/*
 * GCC 3.4 and later; we have __builtin_ctz().
 */
#definelowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
#elif defined(_MSC_VER)
/*
 * Visual Studio; we support only 2005 and later, so use
 * _BitScanForward().
 */
#include<intrin.h>

#ifndef__clang__
#pragma intrinsic(_BitScanForward)
#endif

static __forceinline u_int
lowest_set_bit(intmask)
{
unsigned longbit;

/*
 * Don't sign-extend mask if long is longer than int.
 * (It's currently not, in MSVC, even on 64-bit platforms, but....)
 */
if (_BitScanForward(&bit, (unsigned int)mask) ==0)
abort();	/* mask is zero */
return (u_int)bit;
}
#elif defined(MSDOS) && defined(__DJGPP__)
/*
 * MS-DOS with DJGPP, which declares ffs() in <string.h>, which
 * we've already included.
 */
#definelowest_set_bit(mask)	((u_int)(ffs((mask)) - 1))
#elif (defined(MSDOS) && defined(__WATCOMC__)) || defined(STRINGS_H_DECLARES_FFS)
/*
 * MS-DOS with Watcom C, which has <strings.h> and declares ffs() there,
 * or some other platform (UN*X conforming to a sufficient recent version
 * of the Single UNIX Specification).
 */
#include<strings.h>
#definelowest_set_bit(mask)	(u_int)((ffs((mask)) - 1))
#else
/*
 * None of the above.
 * Use a perfect-hash-function-based function.
 */
staticu_int
lowest_set_bit(intmask)
{
unsigned intv= (unsigned int)mask;

staticconstu_intMultiplyDeBruijnBitPosition[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]);
}
#endif

/*
 * Represents a deleted instruction.
 */
#defineNOP -1

/*
 * Register numbers for use-def values.
 * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory
 * location. A_ATOM is the accumulator and X_ATOM is the index
 * register.
 */
#defineA_ATOM BPF_MEMWORDS
#defineX_ATOM (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.
 */
#defineAX_ATOM N_ATOMS

/*
 * 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.
 */
structvalnode {
intcode;
bpf_u_int32v0, v1;
intval; /* the value number */
structvalnode*next;
};

/* Integer constants mapped with the load immediate opcode. */
#defineK(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)

structvmapinfo {
intis_const;
bpf_u_int32const_val;
};

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * A flag to indicate that further optimization is needed.
 * Iterative passes are continued until a given pass yields no
 * code simplification or branch movement.
 */
intdone;

/*
 * XXX - detect loops that do nothing but repeated AND/OR pullups
 * and edge moves.
 * If 100 passes in a row do nothing but that, treat that as a
 * sign that we're in a loop that just shuffles in a cycle in
 * which each pass just shuffles the code and we eventually
 * get back to the original configuration.
 *
 * XXX - we need a non-heuristic way of detecting, or preventing,
 * such a cycle.
 */
intnon_branch_movement_performed;

u_intn_blocks; /* number of blocks in the CFG; guaranteed to be > 0, as it's a RET instruction at a minimum */
structblock**blocks;
u_intn_edges; /* twice n_blocks, so guaranteed to be > 0 */
structedge**edges;

/*
 * A bit vector set representation of the dominators.
 * We round up the set size to the next power of two.
 */
u_intnodewords;	/* number of 32-bit words for a bit vector of "number of nodes" bits; guaranteed to be > 0 */
u_intedgewords;	/* number of 32-bit words for a bit vector of "number of edges" bits; guaranteed to be > 0 */
structblock**levels;
bpf_u_int32*space;

#defineBITS_PER_WORD (8*sizeof(bpf_u_int32))
/*
 * True if a is in uset {p}
 */
#defineSET_MEMBER(p, a) \
((p)[(unsigned)(a) / BITS_PER_WORD] & ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD)))

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

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

/*
 * a := a intersect b
 * n must be guaranteed to be > 0
 */
#defineSET_INTERSECT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &= *_y++; while (--_n != 0);\
}

/*
 * a := a - b
 * n must be guaranteed to be > 0
 */
#defineSET_SUBTRACT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &=~ *_y++; while (--_n != 0);\
}

/*
 * a := a union b
 * n must be guaranteed to be > 0
 */
#defineSET_UNION(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ |= *_y++; while (--_n != 0);\
}

usetall_dom_sets;
usetall_closure_sets;
usetall_edge_sets;

#defineMODULUS 213
structvalnode*hashtbl[MODULUS];
bpf_u_int32curval;
bpf_u_int32maxval;

structvmapinfo*vmap;
structvalnode*vnode_base;
structvalnode*next_vnode;
} opt_state_t;

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * 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.
 */
structbpf_insn*fstart;
structbpf_insn*ftail;
} conv_state_t;

staticvoidopt_init(opt_state_t*, structicode*);
staticvoidopt_cleanup(opt_state_t*);
staticvoidPCAP_NORETURNopt_error(opt_state_t*, constchar*, ...)
PCAP_PRINTFLIKE(2, 3);

staticvoidintern_blocks(opt_state_t*, structicode*);

staticvoidfind_inedges(opt_state_t*, structblock*);
#ifdefBDEBUG
staticvoidopt_dump(opt_state_t*, structicode*);
#endif

#ifndefMAX
#defineMAX(a,b) ((a)>(b)?(a):(b))
#endif

staticvoid
find_levels_r(opt_state_t*opt_state, structicode*ic, structblock*b)
{
intlevel;

if (isMarked(ic, b))
return;

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

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;
	} else
level=0;
b->level=level;
b->link=opt_state->levels[level];
opt_state->levels[level] =b;
}

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

/*
 * Find dominator relationships.
 * Assumes graph has been leveled.
 */
staticvoid
find_dom(opt_state_t*opt_state, structblock*root)
{
u_inti;
intlevel;
structblock*b;
bpf_u_int32*x;

/*
 * Initialize sets to contain all nodes.
 */
x=opt_state->all_dom_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
i=opt_state->n_blocks*opt_state->nodewords;
while (i!=0) {
--i;
*x++=0xFFFFFFFFU;
	}
/* Root starts off empty. */
for (i=opt_state->nodewords; i!=0;) {
--i;
root->dom[i] =0;
	}

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->dom, b->id);
if (JT(b) ==0)
continue;
SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
 }
	}
}

staticvoid
propedom(opt_state_t*opt_state, structedge*ep)
{
SET_INSERT(ep->edom, ep->id);
if (ep->succ) {
SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
	}
}

/*
 * Compute edge dominators.
 * Assumes graph has been leveled and predecessors established.
 */
staticvoid
find_edom(opt_state_t*opt_state, structblock*root)
{
u_inti;
usetx;
intlevel;
structblock*b;

x=opt_state->all_edge_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
for (i=opt_state->n_edges*opt_state->edgewords; i!=0; ) {
--i;
x[i] =0xFFFFFFFFU;
	}

/* root->level is the highest level no found. */
memset(root->et.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
memset(root->ef.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b!=0; b=b->link) {
propedom(opt_state, &b->et);
propedom(opt_state, &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.
 */
staticvoid
find_closure(opt_state_t*opt_state, structblock*root)
{
intlevel;
structblock*b;

/*
 * Initialize sets to contain no nodes.
 */
memset((char*)opt_state->all_closure_sets, 0,
opt_state->n_blocks*opt_state->nodewords*sizeof(*opt_state->all_closure_sets));

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->closure, b->id);
if (JT(b) ==0)
continue;
SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
 }
	}
}

/*
 * Return the register number that is used by s.
 *
 * Returns ATOM_A if A is used, ATOM_X if X is used, AX_ATOM if both A and X
 * are used, the scratch memory location's number if a scratch memory
 * location is used (e.g., 0 for M[0]), or -1 if none of those are used.
 *
 * The implementation should probably change to an array access.
 */
staticint
atomuse(structstmt*s)
{
	register intc=s->code;

if (c==NOP)
return-1;

switch (BPF_CLASS(c)) {

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

caseBPF_LD:
caseBPF_LDX:
/*
 * As there are fewer than 2^31 memory locations,
 * s->k should be convertible to int without problems.
 */
return (BPF_MODE(c) ==BPF_IND) ? X_ATOM :
 (BPF_MODE(c) ==BPF_MEM) ? (int)s->k : -1;

caseBPF_ST:
returnA_ATOM;

caseBPF_STX:
returnX_ATOM;

caseBPF_JMP:
caseBPF_ALU:
if (BPF_SRC(c) ==BPF_X)
returnAX_ATOM;
returnA_ATOM;

caseBPF_MISC:
returnBPF_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.
 */
staticint
atomdef(structstmt*s)
{
if (s->code==NOP)
return-1;

switch (BPF_CLASS(s->code)) {

caseBPF_LD:
caseBPF_ALU:
returnA_ATOM;

caseBPF_LDX:
returnX_ATOM;

caseBPF_ST:
caseBPF_STX:
returns->k;

caseBPF_MISC:
returnBPF_MISCOP(s->code) ==BPF_TAX ? X_ATOM : A_ATOM;
	}
return-1;
}

/*
 * Compute the sets of registers used, defined, and killed by 'b'.
 *
 * "Used" means that a statement in 'b' uses the register before any
 * statement in 'b' defines it, i.e. it uses the value left in
 * that register by a predecessor block of this block.
 * "Defined" means that a statement in 'b' defines it.
 * "Killed" means that a statement in 'b' defines it before any
 * statement in 'b' uses it, i.e. it kills the value left in that
 * register by a predecessor block of this block.
 */
staticvoid
compute_local_ud(structblock*b)
{
structslist*s;
atomsetdef=0, use=0, killed=0;
intatom;

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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
atom=atomdef(&s->s);
if (atom >= 0) {
if (!ATOMELEM(use, atom))
killed |= ATOMMASK(atom);
def |= ATOMMASK(atom);
 }
	}
if (BPF_CLASS(b->s.code) ==BPF_JMP) {
/*
 * XXX - what about RET?
 */
atom=atomuse(&b->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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
	}

b->def=def;
b->kill=killed;
b->in_use=use;
}

/*
 * Assume graph is already leveled.
 */
staticvoid
find_ud(opt_state_t*opt_state, structblock*root)
{
inti, maxlevel;
structblock*p;

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

for (i=1; i <= maxlevel; ++i) {
for (p=opt_state->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;
 }
	}
}
staticvoid
init_val(opt_state_t*opt_state)
{
opt_state->curval=0;
opt_state->next_vnode=opt_state->vnode_base;
memset((char*)opt_state->vmap, 0, opt_state->maxval*sizeof(*opt_state->vmap));
memset((char*)opt_state->hashtbl, 0, sizeofopt_state->hashtbl);
}

/*
 * Because we really don't have an IR, this stuff is a little messy.
 *
 * This routine looks in the table of existing value number for a value
 * with generated from an operation with the specified opcode and
 * the specified values. If it finds it, it returns its value number,
 * otherwise it makes a new entry in the table and returns the
 * value number of that entry.
 */
staticbpf_u_int32
F(opt_state_t*opt_state, intcode, bpf_u_int32v0, bpf_u_int32v1)
{
u_inthash;
bpf_u_int32val;
structvalnode*p;

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

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

/*
 * Not found. Allocate a new value, and assign it a new
 * value number.
 *
 * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we
 * increment it before using it as the new value number, which
 * means we never assign VAL_UNKNOWN.
 *
 * XXX - unless we overflow, but we probably won't have 2^32-1
 * values; we treat 32 bits as effectively infinite.
 */
val=++opt_state->curval;
if (BPF_MODE(code) ==BPF_IMM&&
 (BPF_CLASS(code) ==BPF_LD||BPF_CLASS(code) ==BPF_LDX)) {
opt_state->vmap[val].const_val=v0;
opt_state->vmap[val].is_const=1;
	}
p=opt_state->next_vnode++;
p->val=val;
p->code=code;
p->v0=v0;
p->v1=v1;
p->next=opt_state->hashtbl[hash];
opt_state->hashtbl[hash] =p;

returnval;
}

staticinlinevoid
vstore(structstmt*s, bpf_u_int32*valp, bpf_u_int32newval, intalter)
{
if (alter&&newval!=VAL_UNKNOWN&&*valp==newval)
s->code=NOP;
else
*valp=newval;
}

/*
 * Do constant-folding on binary operators.
 * (Unary operators are handled elsewhere.)
 */
staticvoid
fold_op(opt_state_t*opt_state, structstmt*s, bpf_u_int32v0, bpf_u_int32v1)
{
bpf_u_int32a, b;

a=opt_state->vmap[v0].const_val;
b=opt_state->vmap[v1].const_val;

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

caseBPF_SUB:
a-=b;
break;

caseBPF_MUL:
a *= b;
break;

caseBPF_DIV:
if (b==0)
opt_error(opt_state, "division by zero");
a /= b;
break;

caseBPF_MOD:
if (b==0)
opt_error(opt_state, "modulus by zero");
a %= b;
break;

caseBPF_AND:
a &= b;
break;

caseBPF_OR:
a |= b;
break;

caseBPF_XOR:
a ^= b;
break;

caseBPF_LSH:
/*
 * A left shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a <<= b;
else
a=0;
break;

caseBPF_RSH:
/*
 * A right shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a >>= b;
else
a=0;
break;

default:
abort();
	}
s->k=a;
s->code=BPF_LD|BPF_IMM;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
}

staticinlinestructslist*
this_op(structslist*s)
{
while (s!=0&&s->s.code==NOP)
s=s->next;
returns;
}

staticvoid
opt_not(structblock*b)
{
structblock*tmp=JT(b);

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

staticvoid
opt_peep(opt_state_t*opt_state, structblock*b)
{
structslist*s;
structslist*next, *last;
bpf_u_int32val;

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

last=s;
for (/*empty*/; /*empty*/; s=next) {
/*
 * Skip over nops.
 */
s=this_op(s);
if (s==0)
break;	/* nothing left in the block */

/*
 * Find the next real instruction after that one
 * (skipping nops).
 */
next=this_op(s->next);
if (next==0)
break;	/* no next instruction */
last=next;

/*
 * st M[k]	-->	st M[k]
 * ldx M[k] tax
 */
if (s->s.code==BPF_ST&&
next->s.code== (BPF_LDX|BPF_MEM) &&
s->s.k==next->s.k) {
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
next->s.code=BPF_MISC|BPF_TAX;
 }
/*
 * ld #k	-->	ldx #k
 * tax txa
 */
if (s->s.code== (BPF_LD|BPF_IMM) &&
next->s.code== (BPF_MISC|BPF_TAX)) {
s->s.code=BPF_LDX|BPF_IMM;
next->s.code=BPF_MISC|BPF_TXA;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
 }
/*
 * This is an ugly special case, but it happens
 * when you say tcp[k] or udp[k] where k is a constant.
 */
if (s->s.code== (BPF_LD|BPF_IMM)) {
structslist*add, *tax, *ild;

/*
 * Check that X isn't used on exit from this
 * block (which the optimizer might cause).
 * We know the code generator won't generate
 * any local dependencies.
 */
if (ATOMELEM(b->out_use, X_ATOM))
continue;

/*
 * Check that the instruction following the ldi
 * is an addx, or it's an ldxms with an addx
 * following it (with 0 or more nops between the
 * ldxms and addx).
 */
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))
continue;

/*
 * Check that a tax follows that (with 0 or more
 * nops between them).
 */
tax=this_op(add->next);
if (tax==0||tax->s.code!= (BPF_MISC|BPF_TAX))
continue;

/*
 * Check that an ild follows that (with 0 or more
 * nops between them).
 */
ild=this_op(tax->next);
if (ild==0||BPF_CLASS(ild->s.code) !=BPF_LD||
BPF_MODE(ild->s.code) !=BPF_IND)
continue;
/*
 * We want to turn this sequence:
 *
 * (004) ldi #0x2 {s}
 * (005) ldxms [14] {next} -- optional
 * (006) addx {add}
 * (007) tax {tax}
 * (008) ild [x+0] {ild}
/*
 * 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 BPF code intermediate representation.
 */

#ifdefHAVE_CONFIG_H
#include<config.h>
#endif

#include<pcap-types.h>

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<setjmp.h>
#include<string.h>
#include<limits.h>/* for SIZE_MAX */
#include<errno.h>

#include"pcap-int.h"

#include"gencode.h"
#include"optimize.h"
#include"diag-control.h"

#ifdefHAVE_OS_PROTO_H
#include"os-proto.h"
#endif

#ifdefBDEBUG
/*
 * The internal "debug printout" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_optimizer_debug;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_optimizer_debug(intvalue);

PCAP_API_DEFvoid
pcap_set_optimizer_debug(intvalue)
{
pcap_optimizer_debug=value;
}

/*
 * The internal "print dot graph" flag for the filter expression optimizer.
 * The code to print that stuff is present only if BDEBUG is defined, so
 * the flag, and the routine to set it, are defined only if BDEBUG is
 * defined.
 */
staticintpcap_print_dot_graph;

/*
 * Routine to set that flag.
 *
 * This is intended for libpcap developers, not for general use.
 * If you want to set these in a program, you'll have to declare this
 * routine yourself, with the appropriate DLL import attribute on Windows;
 * it's not declared in any header file, and won't be declared in any
 * header file provided by libpcap.
 */
PCAP_APIvoidpcap_set_print_dot_graph(intvalue);

PCAP_API_DEFvoid
pcap_set_print_dot_graph(intvalue)
{
pcap_print_dot_graph=value;
}

#endif

/*
 * lowest_set_bit().
 *
 * Takes a 32-bit integer as an argument.
 *
 * If handed a non-zero value, returns the index of the lowest set bit,
 * counting upwards from zero.
 *
 * If handed zero, the results are platform- and compiler-dependent.
 * Keep it out of the light, don't give it any water, don't feed it
 * after midnight, and don't pass zero to it.
 *
 * This is the same as the count of trailing zeroes in the word.
 */
#ifPCAP_IS_AT_LEAST_GNUC_VERSION(3,4)
/*
 * GCC 3.4 and later; we have __builtin_ctz().
 */
#definelowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
#elif defined(_MSC_VER)
/*
 * Visual Studio; we support only 2005 and later, so use
 * _BitScanForward().
 */
#include<intrin.h>

#ifndef__clang__
#pragma intrinsic(_BitScanForward)
#endif

static __forceinline u_int
lowest_set_bit(intmask)
{
unsigned longbit;

/*
 * Don't sign-extend mask if long is longer than int.
 * (It's currently not, in MSVC, even on 64-bit platforms, but....)
 */
if (_BitScanForward(&bit, (unsigned int)mask) ==0)
abort();	/* mask is zero */
return (u_int)bit;
}
#elif defined(MSDOS) && defined(__DJGPP__)
/*
 * MS-DOS with DJGPP, which declares ffs() in <string.h>, which
 * we've already included.
 */
#definelowest_set_bit(mask)	((u_int)(ffs((mask)) - 1))
#elif (defined(MSDOS) && defined(__WATCOMC__)) || defined(STRINGS_H_DECLARES_FFS)
/*
 * MS-DOS with Watcom C, which has <strings.h> and declares ffs() there,
 * or some other platform (UN*X conforming to a sufficient recent version
 * of the Single UNIX Specification).
 */
#include<strings.h>
#definelowest_set_bit(mask)	(u_int)((ffs((mask)) - 1))
#else
/*
 * None of the above.
 * Use a perfect-hash-function-based function.
 */
staticu_int
lowest_set_bit(intmask)
{
unsigned intv= (unsigned int)mask;

staticconstu_intMultiplyDeBruijnBitPosition[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]);
}
#endif

/*
 * Represents a deleted instruction.
 */
#defineNOP -1

/*
 * Register numbers for use-def values.
 * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory
 * location. A_ATOM is the accumulator and X_ATOM is the index
 * register.
 */
#defineA_ATOM BPF_MEMWORDS
#defineX_ATOM (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.
 */
#defineAX_ATOM N_ATOMS

/*
 * 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.
 */
structvalnode {
intcode;
bpf_u_int32v0, v1;
intval; /* the value number */
structvalnode*next;
};

/* Integer constants mapped with the load immediate opcode. */
#defineK(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)

structvmapinfo {
intis_const;
bpf_u_int32const_val;
};

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * A flag to indicate that further optimization is needed.
 * Iterative passes are continued until a given pass yields no
 * code simplification or branch movement.
 */
intdone;

/*
 * XXX - detect loops that do nothing but repeated AND/OR pullups
 * and edge moves.
 * If 100 passes in a row do nothing but that, treat that as a
 * sign that we're in a loop that just shuffles in a cycle in
 * which each pass just shuffles the code and we eventually
 * get back to the original configuration.
 *
 * XXX - we need a non-heuristic way of detecting, or preventing,
 * such a cycle.
 */
intnon_branch_movement_performed;

u_intn_blocks; /* number of blocks in the CFG; guaranteed to be > 0, as it's a RET instruction at a minimum */
structblock**blocks;
u_intn_edges; /* twice n_blocks, so guaranteed to be > 0 */
structedge**edges;

/*
 * A bit vector set representation of the dominators.
 * We round up the set size to the next power of two.
 */
u_intnodewords;	/* number of 32-bit words for a bit vector of "number of nodes" bits; guaranteed to be > 0 */
u_intedgewords;	/* number of 32-bit words for a bit vector of "number of edges" bits; guaranteed to be > 0 */
structblock**levels;
bpf_u_int32*space;

#defineBITS_PER_WORD (8*sizeof(bpf_u_int32))
/*
 * True if a is in uset {p}
 */
#defineSET_MEMBER(p, a) \
((p)[(unsigned)(a) / BITS_PER_WORD] & ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD)))

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

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

/*
 * a := a intersect b
 * n must be guaranteed to be > 0
 */
#defineSET_INTERSECT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &= *_y++; while (--_n != 0);\
}

/*
 * a := a - b
 * n must be guaranteed to be > 0
 */
#defineSET_SUBTRACT(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ &=~ *_y++; while (--_n != 0);\
}

/*
 * a := a union b
 * n must be guaranteed to be > 0
 */
#defineSET_UNION(a, b, n)\
{\
	register bpf_u_int32 *_x = a, *_y = b;\
	register u_int _n = n;\
	do *_x++ |= *_y++; while (--_n != 0);\
}

usetall_dom_sets;
usetall_closure_sets;
usetall_edge_sets;

#defineMODULUS 213
structvalnode*hashtbl[MODULUS];
bpf_u_int32curval;
bpf_u_int32maxval;

structvmapinfo*vmap;
structvalnode*vnode_base;
structvalnode*next_vnode;
} opt_state_t;

typedefstruct {
/*
 * Place to longjmp to on an error.
 */
jmp_buftop_ctx;

/*
 * The buffer into which to put error message.
 */
char*errbuf;

/*
 * 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.
 */
structbpf_insn*fstart;
structbpf_insn*ftail;
} conv_state_t;

staticvoidopt_init(opt_state_t*, structicode*);
staticvoidopt_cleanup(opt_state_t*);
staticvoidPCAP_NORETURNopt_error(opt_state_t*, constchar*, ...)
PCAP_PRINTFLIKE(2, 3);

staticvoidintern_blocks(opt_state_t*, structicode*);

staticvoidfind_inedges(opt_state_t*, structblock*);
#ifdefBDEBUG
staticvoidopt_dump(opt_state_t*, structicode*);
#endif

#ifndefMAX
#defineMAX(a,b) ((a)>(b)?(a):(b))
#endif

staticvoid
find_levels_r(opt_state_t*opt_state, structicode*ic, structblock*b)
{
intlevel;

if (isMarked(ic, b))
return;

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

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;
	} else
level=0;
b->level=level;
b->link=opt_state->levels[level];
opt_state->levels[level] =b;
}

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

/*
 * Find dominator relationships.
 * Assumes graph has been leveled.
 */
staticvoid
find_dom(opt_state_t*opt_state, structblock*root)
{
u_inti;
intlevel;
structblock*b;
bpf_u_int32*x;

/*
 * Initialize sets to contain all nodes.
 */
x=opt_state->all_dom_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
i=opt_state->n_blocks*opt_state->nodewords;
while (i!=0) {
--i;
*x++=0xFFFFFFFFU;
	}
/* Root starts off empty. */
for (i=opt_state->nodewords; i!=0;) {
--i;
root->dom[i] =0;
	}

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->dom, b->id);
if (JT(b) ==0)
continue;
SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
 }
	}
}

staticvoid
propedom(opt_state_t*opt_state, structedge*ep)
{
SET_INSERT(ep->edom, ep->id);
if (ep->succ) {
SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
	}
}

/*
 * Compute edge dominators.
 * Assumes graph has been leveled and predecessors established.
 */
staticvoid
find_edom(opt_state_t*opt_state, structblock*root)
{
u_inti;
usetx;
intlevel;
structblock*b;

x=opt_state->all_edge_sets;
/*
 * In opt_init(), we've made sure the product doesn't overflow.
 */
for (i=opt_state->n_edges*opt_state->edgewords; i!=0; ) {
--i;
x[i] =0xFFFFFFFFU;
	}

/* root->level is the highest level no found. */
memset(root->et.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
memset(root->ef.edom, 0, opt_state->edgewords*sizeof(*(uset)0));
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b!=0; b=b->link) {
propedom(opt_state, &b->et);
propedom(opt_state, &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.
 */
staticvoid
find_closure(opt_state_t*opt_state, structblock*root)
{
intlevel;
structblock*b;

/*
 * Initialize sets to contain no nodes.
 */
memset((char*)opt_state->all_closure_sets, 0,
opt_state->n_blocks*opt_state->nodewords*sizeof(*opt_state->all_closure_sets));

/* root->level is the highest level no found. */
for (level=root->level; level >= 0; --level) {
for (b=opt_state->levels[level]; b; b=b->link) {
SET_INSERT(b->closure, b->id);
if (JT(b) ==0)
continue;
SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
 }
	}
}

/*
 * Return the register number that is used by s.
 *
 * Returns ATOM_A if A is used, ATOM_X if X is used, AX_ATOM if both A and X
 * are used, the scratch memory location's number if a scratch memory
 * location is used (e.g., 0 for M[0]), or -1 if none of those are used.
 *
 * The implementation should probably change to an array access.
 */
staticint
atomuse(structstmt*s)
{
	register intc=s->code;

if (c==NOP)
return-1;

switch (BPF_CLASS(c)) {

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

caseBPF_LD:
caseBPF_LDX:
/*
 * As there are fewer than 2^31 memory locations,
 * s->k should be convertible to int without problems.
 */
return (BPF_MODE(c) ==BPF_IND) ? X_ATOM :
 (BPF_MODE(c) ==BPF_MEM) ? (int)s->k : -1;

caseBPF_ST:
returnA_ATOM;

caseBPF_STX:
returnX_ATOM;

caseBPF_JMP:
caseBPF_ALU:
if (BPF_SRC(c) ==BPF_X)
returnAX_ATOM;
returnA_ATOM;

caseBPF_MISC:
returnBPF_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.
 */
staticint
atomdef(structstmt*s)
{
if (s->code==NOP)
return-1;

switch (BPF_CLASS(s->code)) {

caseBPF_LD:
caseBPF_ALU:
returnA_ATOM;

caseBPF_LDX:
returnX_ATOM;

caseBPF_ST:
caseBPF_STX:
returns->k;

caseBPF_MISC:
returnBPF_MISCOP(s->code) ==BPF_TAX ? X_ATOM : A_ATOM;
	}
return-1;
}

/*
 * Compute the sets of registers used, defined, and killed by 'b'.
 *
 * "Used" means that a statement in 'b' uses the register before any
 * statement in 'b' defines it, i.e. it uses the value left in
 * that register by a predecessor block of this block.
 * "Defined" means that a statement in 'b' defines it.
 * "Killed" means that a statement in 'b' defines it before any
 * statement in 'b' uses it, i.e. it kills the value left in that
 * register by a predecessor block of this block.
 */
staticvoid
compute_local_ud(structblock*b)
{
structslist*s;
atomsetdef=0, use=0, killed=0;
intatom;

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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
atom=atomdef(&s->s);
if (atom >= 0) {
if (!ATOMELEM(use, atom))
killed |= ATOMMASK(atom);
def |= ATOMMASK(atom);
 }
	}
if (BPF_CLASS(b->s.code) ==BPF_JMP) {
/*
 * XXX - what about RET?
 */
atom=atomuse(&b->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);
 }
elseif (atom<N_ATOMS) {
if (!ATOMELEM(def, atom))
use |= ATOMMASK(atom);
 }
else
abort();
 }
	}

b->def=def;
b->kill=killed;
b->in_use=use;
}

/*
 * Assume graph is already leveled.
 */
staticvoid
find_ud(opt_state_t*opt_state, structblock*root)
{
inti, maxlevel;
structblock*p;

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

for (i=1; i <= maxlevel; ++i) {
for (p=opt_state->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;
 }
	}
}
staticvoid
init_val(opt_state_t*opt_state)
{
opt_state->curval=0;
opt_state->next_vnode=opt_state->vnode_base;
memset((char*)opt_state->vmap, 0, opt_state->maxval*sizeof(*opt_state->vmap));
memset((char*)opt_state->hashtbl, 0, sizeofopt_state->hashtbl);
}

/*
 * Because we really don't have an IR, this stuff is a little messy.
 *
 * This routine looks in the table of existing value number for a value
 * with generated from an operation with the specified opcode and
 * the specified values. If it finds it, it returns its value number,
 * otherwise it makes a new entry in the table and returns the
 * value number of that entry.
 */
staticbpf_u_int32
F(opt_state_t*opt_state, intcode, bpf_u_int32v0, bpf_u_int32v1)
{
u_inthash;
bpf_u_int32val;
structvalnode*p;

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

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

/*
 * Not found. Allocate a new value, and assign it a new
 * value number.
 *
 * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we
 * increment it before using it as the new value number, which
 * means we never assign VAL_UNKNOWN.
 *
 * XXX - unless we overflow, but we probably won't have 2^32-1
 * values; we treat 32 bits as effectively infinite.
 */
val=++opt_state->curval;
if (BPF_MODE(code) ==BPF_IMM&&
 (BPF_CLASS(code) ==BPF_LD||BPF_CLASS(code) ==BPF_LDX)) {
opt_state->vmap[val].const_val=v0;
opt_state->vmap[val].is_const=1;
	}
p=opt_state->next_vnode++;
p->val=val;
p->code=code;
p->v0=v0;
p->v1=v1;
p->next=opt_state->hashtbl[hash];
opt_state->hashtbl[hash] =p;

returnval;
}

staticinlinevoid
vstore(structstmt*s, bpf_u_int32*valp, bpf_u_int32newval, intalter)
{
if (alter&&newval!=VAL_UNKNOWN&&*valp==newval)
s->code=NOP;
else
*valp=newval;
}

/*
 * Do constant-folding on binary operators.
 * (Unary operators are handled elsewhere.)
 */
staticvoid
fold_op(opt_state_t*opt_state, structstmt*s, bpf_u_int32v0, bpf_u_int32v1)
{
bpf_u_int32a, b;

a=opt_state->vmap[v0].const_val;
b=opt_state->vmap[v1].const_val;

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

caseBPF_SUB:
a-=b;
break;

caseBPF_MUL:
a *= b;
break;

caseBPF_DIV:
if (b==0)
opt_error(opt_state, "division by zero");
a /= b;
break;

caseBPF_MOD:
if (b==0)
opt_error(opt_state, "modulus by zero");
a %= b;
break;

caseBPF_AND:
a &= b;
break;

caseBPF_OR:
a |= b;
break;

caseBPF_XOR:
a ^= b;
break;

caseBPF_LSH:
/*
 * A left shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a <<= b;
else
a=0;
break;

caseBPF_RSH:
/*
 * A right shift of more than the width of the type
 * is undefined in C; we'll just treat it as shifting
 * all the bits out.
 *
 * XXX - the BPF interpreter doesn't check for this,
 * so its behavior is dependent on the behavior of
 * the processor on which it's running. There are
 * processors on which it shifts all the bits out
 * and processors on which it does no shift.
 */
if (b<32)
a >>= b;
else
a=0;
break;

default:
abort();
	}
s->k=a;
s->code=BPF_LD|BPF_IMM;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
}

staticinlinestructslist*
this_op(structslist*s)
{
while (s!=0&&s->s.code==NOP)
s=s->next;
returns;
}

staticvoid
opt_not(structblock*b)
{
structblock*tmp=JT(b);

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

staticvoid
opt_peep(opt_state_t*opt_state, structblock*b)
{
structslist*s;
structslist*next, *last;
bpf_u_int32val;

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

last=s;
for (/*empty*/; /*empty*/; s=next) {
/*
 * Skip over nops.
 */
s=this_op(s);
if (s==0)
break;	/* nothing left in the block */

/*
 * Find the next real instruction after that one
 * (skipping nops).
 */
next=this_op(s->next);
if (next==0)
break;	/* no next instruction */
last=next;

/*
 * st M[k]	-->	st M[k]
 * ldx M[k] tax
 */
if (s->s.code==BPF_ST&&
next->s.code== (BPF_LDX|BPF_MEM) &&
s->s.k==next->s.k) {
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
next->s.code=BPF_MISC|BPF_TAX;
 }
/*
 * ld #k	-->	ldx #k
 * tax txa
 */
if (s->s.code== (BPF_LD|BPF_IMM) &&
next->s.code== (BPF_MISC|BPF_TAX)) {
s->s.code=BPF_LDX|BPF_IMM;
next->s.code=BPF_MISC|BPF_TXA;
/*
 * XXX - optimizer loop detection.
 */
opt_state->non_branch_movement_performed=1;
opt_state->done=0;
 }
/*
 * This is an ugly special case, but it happens
 * when you say tcp[k] or udp[k] where k is a constant.
 */
if (s->s.code== (BPF_LD|BPF_IMM)) {
structslist*add, *tax, *ild;

/*
 * Check that X isn't used on exit from this
 * block (which the optimizer might cause).
 * We know the code generator won't generate
 * any local dependencies.
 */
if (ATOMELEM(b->out_use, X_ATOM))
continue;

/*
 * Check that the instruction following the ldi
 * is an addx, or it's an ldxms with an addx
 * following it (with 0 or more nops between the
 * ldxms and addx).
 */
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))
continue;

/*
 * Check that a tax follows that (with 0 or more
 * nops between them).
 */
tax=this_op(add->next);
if (tax==0||tax->s.code!= (BPF_MISC|BPF_TAX))
continue;

/*
 * Check that an ild follows that (with 0 or more
 * nops between them).
 */
ild=this_op(tax->next);
if (ild==0||BPF_CLASS(ild->s.code) !=BPF_LD||
BPF_MODE(ild->s.code) !=BPF_IND)
continue;
/*
 * We want to turn this sequence:
 *
 * (004) ldi #0x2 {s}
 * (005) ldxms [14] {next} -- optional
 * (006) addx {add}
 * (007) tax {tax}
 * (008) ild [x+0] {ild}