2 * Copyright (c) 1988, 1989, 1990, 1991, 1993, 1994, 1995, 1996
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that: (1) source code distributions
7 * retain the above copyright notice and this paragraph in its entirety, (2)
8 * distributions including binary code include the above copyright notice and
9 * this paragraph in its entirety in the documentation or other materials
10 * provided with the distribution, and (3) all advertising materials mentioning
11 * features or use of this software display the following acknowledgement:
12 * ``This product includes software developed by the University of California,
13 * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
14 * the University nor the names of its contributors may be used to endorse
15 * or promote products derived from this software without specific prior
17 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
18 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
19 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
21 * Optimization module for BPF code intermediate representation.
28 #include <pcap-types.h>
43 #ifdef HAVE_OS_PROTO_H
49 * The internal "debug printout" flag for the filter expression optimizer.
50 * The code to print that stuff is present only if BDEBUG is defined, so
51 * the flag, and the routine to set it, are defined only if BDEBUG is
54 static int pcap_optimizer_debug;
57 * Routine to set that flag.
59 * This is intended for libpcap developers, not for general use.
60 * If you want to set these in a program, you'll have to declare this
61 * routine yourself, with the appropriate DLL import attribute on Windows;
62 * it's not declared in any header file, and won't be declared in any
63 * header file provided by libpcap.
65 PCAP_API void pcap_set_optimizer_debug(int value);
68 pcap_set_optimizer_debug(int value)
70 pcap_optimizer_debug = value;
74 * The internal "print dot graph" flag for the filter expression optimizer.
75 * The code to print that stuff is present only if BDEBUG is defined, so
76 * the flag, and the routine to set it, are defined only if BDEBUG is
79 static int pcap_print_dot_graph;
82 * Routine to set that flag.
84 * This is intended for libpcap developers, not for general use.
85 * If you want to set these in a program, you'll have to declare this
86 * routine yourself, with the appropriate DLL import attribute on Windows;
87 * it's not declared in any header file, and won't be declared in any
88 * header file provided by libpcap.
90 PCAP_API void pcap_set_print_dot_graph(int value);
93 pcap_set_print_dot_graph(int value)
95 pcap_print_dot_graph = value;
103 * Takes a 32-bit integer as an argument.
105 * If handed a non-zero value, returns the index of the lowest set bit,
106 * counting upwards fro zero.
108 * If handed zero, the results are platform- and compiler-dependent.
109 * Keep it out of the light, don't give it any water, don't feed it
110 * after midnight, and don't pass zero to it.
112 * This is the same as the count of trailing zeroes in the word.
114 #if PCAP_IS_AT_LEAST_GNUC_VERSION(3,4)
116 * GCC 3.4 and later; we have __builtin_ctz().
118 #define lowest_set_bit(mask) __builtin_ctz(mask)
119 #elif defined(_MSC_VER)
121 * Visual Studio; we support only 2005 and later, so use
127 #pragma intrinsic(_BitScanForward)
130 static __forceinline int
131 lowest_set_bit(int mask)
136 * Don't sign-extend mask if long is longer than int.
137 * (It's currently not, in MSVC, even on 64-bit platforms, but....)
139 if (_BitScanForward(&bit, (unsigned int)mask) == 0)
140 return -1; /* mask is zero */
143 #elif defined(MSDOS) && defined(__DJGPP__)
145 * MS-DOS with DJGPP, which declares ffs() in <string.h>, which
146 * we've already included.
148 #define lowest_set_bit(mask) (ffs((mask)) - 1)
149 #elif (defined(MSDOS) && defined(__WATCOMC__)) || defined(STRINGS_H_DECLARES_FFS)
151 * MS-DOS with Watcom C, which has <strings.h> and declares ffs() there,
152 * or some other platform (UN*X conforming to a sufficient recent version
153 * of the Single UNIX Specification).
156 #define lowest_set_bit(mask) (ffs((mask)) - 1)
160 * Use a perfect-hash-function-based function.
163 lowest_set_bit(int mask)
165 unsigned int v = (unsigned int)mask;
167 static const int MultiplyDeBruijnBitPosition[32] = {
168 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
169 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
173 * We strip off all but the lowermost set bit (v & ~v),
174 * and perform a minimal perfect hash on it to look up the
175 * number of low-order zero bits in a table.
179 * http://7ooo.mooo.com/text/ComputingTrailingZerosHOWTO.pdf
181 * http://supertech.csail.mit.edu/papers/debruijn.pdf
183 return (MultiplyDeBruijnBitPosition[((v & -v) * 0x077CB531U) >> 27]);
188 * Represents a deleted instruction.
193 * Register numbers for use-def values.
194 * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory
195 * location. A_ATOM is the accumulator and X_ATOM is the index
198 #define A_ATOM BPF_MEMWORDS
199 #define X_ATOM (BPF_MEMWORDS+1)
202 * This define is used to represent *both* the accumulator and
203 * x register in use-def computations.
204 * Currently, the use-def code assumes only one definition per instruction.
206 #define AX_ATOM N_ATOMS
209 * These data structures are used in a Cocke and Shwarz style
210 * value numbering scheme. Since the flowgraph is acyclic,
211 * exit values can be propagated from a node's predecessors
212 * provided it is uniquely defined.
218 struct valnode *next;
221 /* Integer constants mapped with the load immediate opcode. */
222 #define K(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0L)
231 * Place to longjmp to on an error.
236 * The buffer into which to put error message.
241 * A flag to indicate that further optimization is needed.
242 * Iterative passes are continued until a given pass yields no
248 struct block **blocks;
253 * A bit vector set representation of the dominators.
254 * We round up the set size to the next power of two.
258 struct block **levels;
261 #define BITS_PER_WORD (8*sizeof(bpf_u_int32))
263 * True if a is in uset {p}
265 #define SET_MEMBER(p, a) \
266 ((p)[(unsigned)(a) / BITS_PER_WORD] & ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD)))
271 #define SET_INSERT(p, a) \
272 (p)[(unsigned)(a) / BITS_PER_WORD] |= ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD))
275 * Delete 'a' from uset p.
277 #define SET_DELETE(p, a) \
278 (p)[(unsigned)(a) / BITS_PER_WORD] &= ~((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD))
283 #define SET_INTERSECT(a, b, n)\
285 register bpf_u_int32 *_x = a, *_y = b;\
286 register int _n = n;\
287 while (--_n >= 0) *_x++ &= *_y++;\
293 #define SET_SUBTRACT(a, b, n)\
295 register bpf_u_int32 *_x = a, *_y = b;\
296 register int _n = n;\
297 while (--_n >= 0) *_x++ &=~ *_y++;\
303 #define SET_UNION(a, b, n)\
305 register bpf_u_int32 *_x = a, *_y = b;\
306 register int _n = n;\
307 while (--_n >= 0) *_x++ |= *_y++;\
311 uset all_closure_sets;
315 struct valnode *hashtbl[MODULUS];
319 struct vmapinfo *vmap;
320 struct valnode *vnode_base;
321 struct valnode *next_vnode;
326 * Place to longjmp to on an error.
331 * The buffer into which to put error message.
336 * Some pointers used to convert the basic block form of the code,
337 * into the array form that BPF requires. 'fstart' will point to
338 * the malloc'd array while 'ftail' is used during the recursive
341 struct bpf_insn *fstart;
342 struct bpf_insn *ftail;
345 static void opt_init(opt_state_t *, struct icode *);
346 static void opt_cleanup(opt_state_t *);
347 static void PCAP_NORETURN opt_error(opt_state_t *, const char *, ...)
348 PCAP_PRINTFLIKE(2, 3);
350 static void intern_blocks(opt_state_t *, struct icode *);
352 static void find_inedges(opt_state_t *, struct block *);
354 static void opt_dump(opt_state_t *, struct icode *);
358 #define MAX(a,b) ((a)>(b)?(a):(b))
362 find_levels_r(opt_state_t *opt_state, struct icode *ic, struct block *b)
373 find_levels_r(opt_state, ic, JT(b));
374 find_levels_r(opt_state, ic, JF(b));
375 level = MAX(JT(b)->level, JF(b)->level) + 1;
379 b->link = opt_state->levels[level];
380 opt_state->levels[level] = b;
384 * Level graph. The levels go from 0 at the leaves to
385 * N_LEVELS at the root. The opt_state->levels[] array points to the
386 * first node of the level list, whose elements are linked
387 * with the 'link' field of the struct block.
390 find_levels(opt_state_t *opt_state, struct icode *ic)
392 memset((char *)opt_state->levels, 0, opt_state->n_blocks * sizeof(*opt_state->levels));
394 find_levels_r(opt_state, ic, ic->root);
398 * Find dominator relationships.
399 * Assumes graph has been leveled.
402 find_dom(opt_state_t *opt_state, struct block *root)
409 * Initialize sets to contain all nodes.
411 x = opt_state->all_dom_sets;
412 i = opt_state->n_blocks * opt_state->nodewords;
415 /* Root starts off empty. */
416 for (i = opt_state->nodewords; --i >= 0;)
419 /* root->level is the highest level no found. */
420 for (i = root->level; i >= 0; --i) {
421 for (b = opt_state->levels[i]; b; b = b->link) {
422 SET_INSERT(b->dom, b->id);
425 SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
426 SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
432 propedom(opt_state_t *opt_state, struct edge *ep)
434 SET_INSERT(ep->edom, ep->id);
436 SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
437 SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
442 * Compute edge dominators.
443 * Assumes graph has been leveled and predecessors established.
446 find_edom(opt_state_t *opt_state, struct block *root)
452 x = opt_state->all_edge_sets;
453 for (i = opt_state->n_edges * opt_state->edgewords; --i >= 0; )
456 /* root->level is the highest level no found. */
457 memset(root->et.edom, 0, opt_state->edgewords * sizeof(*(uset)0));
458 memset(root->ef.edom, 0, opt_state->edgewords * sizeof(*(uset)0));
459 for (i = root->level; i >= 0; --i) {
460 for (b = opt_state->levels[i]; b != 0; b = b->link) {
461 propedom(opt_state, &b->et);
462 propedom(opt_state, &b->ef);
468 * Find the backwards transitive closure of the flow graph. These sets
469 * are backwards in the sense that we find the set of nodes that reach
470 * a given node, not the set of nodes that can be reached by a node.
472 * Assumes graph has been leveled.
475 find_closure(opt_state_t *opt_state, struct block *root)
481 * Initialize sets to contain no nodes.
483 memset((char *)opt_state->all_closure_sets, 0,
484 opt_state->n_blocks * opt_state->nodewords * sizeof(*opt_state->all_closure_sets));
486 /* root->level is the highest level no found. */
487 for (i = root->level; i >= 0; --i) {
488 for (b = opt_state->levels[i]; b; b = b->link) {
489 SET_INSERT(b->closure, b->id);
492 SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
493 SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
499 * Return the register number that is used by s. If A and X are both
500 * used, return AX_ATOM. If no register is used, return -1.
502 * The implementation should probably change to an array access.
505 atomuse(struct stmt *s)
507 register int c = s->code;
512 switch (BPF_CLASS(c)) {
515 return (BPF_RVAL(c) == BPF_A) ? A_ATOM :
516 (BPF_RVAL(c) == BPF_X) ? X_ATOM : -1;
520 return (BPF_MODE(c) == BPF_IND) ? X_ATOM :
521 (BPF_MODE(c) == BPF_MEM) ? s->k : -1;
531 if (BPF_SRC(c) == BPF_X)
536 return BPF_MISCOP(c) == BPF_TXA ? X_ATOM : A_ATOM;
543 * Return the register number that is defined by 's'. We assume that
544 * a single stmt cannot define more than one register. If no register
545 * is defined, return -1.
547 * The implementation should probably change to an array access.
550 atomdef(struct stmt *s)
555 switch (BPF_CLASS(s->code)) {
569 return BPF_MISCOP(s->code) == BPF_TAX ? X_ATOM : A_ATOM;
575 * Compute the sets of registers used, defined, and killed by 'b'.
577 * "Used" means that a statement in 'b' uses the register before any
578 * statement in 'b' defines it, i.e. it uses the value left in
579 * that register by a predecessor block of this block.
580 * "Defined" means that a statement in 'b' defines it.
581 * "Killed" means that a statement in 'b' defines it before any
582 * statement in 'b' uses it, i.e. it kills the value left in that
583 * register by a predecessor block of this block.
586 compute_local_ud(struct block *b)
589 atomset def = 0, use = 0, killed = 0;
592 for (s = b->stmts; s; s = s->next) {
593 if (s->s.code == NOP)
595 atom = atomuse(&s->s);
597 if (atom == AX_ATOM) {
598 if (!ATOMELEM(def, X_ATOM))
599 use |= ATOMMASK(X_ATOM);
600 if (!ATOMELEM(def, A_ATOM))
601 use |= ATOMMASK(A_ATOM);
603 else if (atom < N_ATOMS) {
604 if (!ATOMELEM(def, atom))
605 use |= ATOMMASK(atom);
610 atom = atomdef(&s->s);
612 if (!ATOMELEM(use, atom))
613 killed |= ATOMMASK(atom);
614 def |= ATOMMASK(atom);
617 if (BPF_CLASS(b->s.code) == BPF_JMP) {
619 * XXX - what about RET?
621 atom = atomuse(&b->s);
623 if (atom == AX_ATOM) {
624 if (!ATOMELEM(def, X_ATOM))
625 use |= ATOMMASK(X_ATOM);
626 if (!ATOMELEM(def, A_ATOM))
627 use |= ATOMMASK(A_ATOM);
629 else if (atom < N_ATOMS) {
630 if (!ATOMELEM(def, atom))
631 use |= ATOMMASK(atom);
644 * Assume graph is already leveled.
647 find_ud(opt_state_t *opt_state, struct block *root)
653 * root->level is the highest level no found;
654 * count down from there.
656 maxlevel = root->level;
657 for (i = maxlevel; i >= 0; --i)
658 for (p = opt_state->levels[i]; p; p = p->link) {
663 for (i = 1; i <= maxlevel; ++i) {
664 for (p = opt_state->levels[i]; p; p = p->link) {
665 p->out_use |= JT(p)->in_use | JF(p)->in_use;
666 p->in_use |= p->out_use &~ p->kill;
671 init_val(opt_state_t *opt_state)
673 opt_state->curval = 0;
674 opt_state->next_vnode = opt_state->vnode_base;
675 memset((char *)opt_state->vmap, 0, opt_state->maxval * sizeof(*opt_state->vmap));
676 memset((char *)opt_state->hashtbl, 0, sizeof opt_state->hashtbl);
679 /* Because we really don't have an IR, this stuff is a little messy. */
681 F(opt_state_t *opt_state, int code, int v0, int v1)
687 hash = (u_int)code ^ ((u_int)v0 << 4) ^ ((u_int)v1 << 8);
690 for (p = opt_state->hashtbl[hash]; p; p = p->next)
691 if (p->code == code && p->v0 == v0 && p->v1 == v1)
694 val = ++opt_state->curval;
695 if (BPF_MODE(code) == BPF_IMM &&
696 (BPF_CLASS(code) == BPF_LD || BPF_CLASS(code) == BPF_LDX)) {
697 opt_state->vmap[val].const_val = v0;
698 opt_state->vmap[val].is_const = 1;
700 p = opt_state->next_vnode++;
705 p->next = opt_state->hashtbl[hash];
706 opt_state->hashtbl[hash] = p;
712 vstore(struct stmt *s, int *valp, int newval, int alter)
714 if (alter && newval != VAL_UNKNOWN && *valp == newval)
721 * Do constant-folding on binary operators.
722 * (Unary operators are handled elsewhere.)
725 fold_op(opt_state_t *opt_state, struct stmt *s, int v0, int v1)
729 a = opt_state->vmap[v0].const_val;
730 b = opt_state->vmap[v1].const_val;
732 switch (BPF_OP(s->code)) {
747 opt_error(opt_state, "division by zero");
753 opt_error(opt_state, "modulus by zero");
771 * A left shift of more than the width of the type
772 * is undefined in C; we'll just treat it as shifting
775 * XXX - the BPF interpreter doesn't check for this,
776 * so its behavior is dependent on the behavior of
777 * the processor on which it's running. There are
778 * processors on which it shifts all the bits out
779 * and processors on which it does no shift.
789 * A right shift of more than the width of the type
790 * is undefined in C; we'll just treat it as shifting
793 * XXX - the BPF interpreter doesn't check for this,
794 * so its behavior is dependent on the behavior of
795 * the processor on which it's running. There are
796 * processors on which it shifts all the bits out
797 * and processors on which it does no shift.
809 s->code = BPF_LD|BPF_IMM;
813 static inline struct slist *
814 this_op(struct slist *s)
816 while (s != 0 && s->s.code == NOP)
822 opt_not(struct block *b)
824 struct block *tmp = JT(b);
831 opt_peep(opt_state_t *opt_state, struct block *b)
834 struct slist *next, *last;
842 for (/*empty*/; /*empty*/; s = next) {
848 break; /* nothing left in the block */
851 * Find the next real instruction after that one
854 next = this_op(s->next);
856 break; /* no next instruction */
860 * st M[k] --> st M[k]
863 if (s->s.code == BPF_ST &&
864 next->s.code == (BPF_LDX|BPF_MEM) &&
865 s->s.k == next->s.k) {
867 next->s.code = BPF_MISC|BPF_TAX;
873 if (s->s.code == (BPF_LD|BPF_IMM) &&
874 next->s.code == (BPF_MISC|BPF_TAX)) {
875 s->s.code = BPF_LDX|BPF_IMM;
876 next->s.code = BPF_MISC|BPF_TXA;
880 * This is an ugly special case, but it happens
881 * when you say tcp[k] or udp[k] where k is a constant.
883 if (s->s.code == (BPF_LD|BPF_IMM)) {
884 struct slist *add, *tax, *ild;
887 * Check that X isn't used on exit from this
888 * block (which the optimizer might cause).
889 * We know the code generator won't generate
890 * any local dependencies.
892 if (ATOMELEM(b->out_use, X_ATOM))
896 * Check that the instruction following the ldi
897 * is an addx, or it's an ldxms with an addx
898 * following it (with 0 or more nops between the
901 if (next->s.code != (BPF_LDX|BPF_MSH|BPF_B))
904 add = this_op(next->next);
905 if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X))
909 * Check that a tax follows that (with 0 or more
910 * nops between them).
912 tax = this_op(add->next);
913 if (tax == 0 || tax->s.code != (BPF_MISC|BPF_TAX))
917 * Check that an ild follows that (with 0 or more
918 * nops between them).
920 ild = this_op(tax->next);
921 if (ild == 0 || BPF_CLASS(ild->s.code) != BPF_LD ||
922 BPF_MODE(ild->s.code) != BPF_IND)
925 * We want to turn this sequence:
928 * (005) ldxms [14] {next} -- optional
931 * (008) ild [x+0] {ild}
933 * into this sequence:
941 * XXX We need to check that X is not
942 * subsequently used, because we want to change
943 * what'll be in it after this sequence.
945 * We know we can eliminate the accumulator
946 * modifications earlier in the sequence since
947 * it is defined by the last stmt of this sequence
948 * (i.e., the last statement of the sequence loads
949 * a value into the accumulator, so we can eliminate
950 * earlier operations on the accumulator).
960 * If the comparison at the end of a block is an equality
961 * comparison against a constant, and nobody uses the value
962 * we leave in the A register at the end of a block, and
963 * the operation preceding the comparison is an arithmetic
964 * operation, we can sometime optimize it away.
966 if (b->s.code == (BPF_JMP|BPF_JEQ|BPF_K) &&
967 !ATOMELEM(b->out_use, A_ATOM)) {
969 * We can optimize away certain subtractions of the
972 if (last->s.code == (BPF_ALU|BPF_SUB|BPF_X)) {
973 val = b->val[X_ATOM];
974 if (opt_state->vmap[val].is_const) {
976 * If we have a subtract to do a comparison,
977 * and the X register is a known constant,
978 * we can merge this value into the
984 b->s.k += opt_state->vmap[val].const_val;
987 } else if (b->s.k == 0) {
989 * If the X register isn't a constant,
990 * and the comparison in the test is
991 * against 0, we can compare with the
992 * X register, instead:
998 b->s.code = BPF_JMP|BPF_JEQ|BPF_X;
1003 * Likewise, a constant subtract can be simplified:
1006 * jeq #y -> jeq #(x+y)
1008 else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K)) {
1010 b->s.k += last->s.k;
1011 opt_state->done = 0;
1014 * And, similarly, a constant AND can be simplified
1015 * if we're testing against 0, i.e.:
1020 else if (last->s.code == (BPF_ALU|BPF_AND|BPF_K) &&
1023 b->s.code = BPF_JMP|BPF_K|BPF_JSET;
1025 opt_state->done = 0;
1031 * jset #ffffffff -> always
1033 if (b->s.code == (BPF_JMP|BPF_K|BPF_JSET)) {
1036 if ((u_int)b->s.k == 0xffffffffU)
1040 * If we're comparing against the index register, and the index
1041 * register is a known constant, we can just compare against that
1044 val = b->val[X_ATOM];
1045 if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_X) {
1046 bpf_int32 v = opt_state->vmap[val].const_val;
1047 b->s.code &= ~BPF_X;
1051 * If the accumulator is a known constant, we can compute the
1052 * comparison result.
1054 val = b->val[A_ATOM];
1055 if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) {
1056 bpf_int32 v = opt_state->vmap[val].const_val;
1057 switch (BPF_OP(b->s.code)) {
1064 v = (unsigned)v > (unsigned)b->s.k;
1068 v = (unsigned)v >= (unsigned)b->s.k;
1079 opt_state->done = 0;
1088 * Compute the symbolic value of expression of 's', and update
1089 * anything it defines in the value table 'val'. If 'alter' is true,
1090 * do various optimizations. This code would be cleaner if symbolic
1091 * evaluation and code transformations weren't folded together.
1094 opt_stmt(opt_state_t *opt_state, struct stmt *s, int val[], int alter)
1101 case BPF_LD|BPF_ABS|BPF_W:
1102 case BPF_LD|BPF_ABS|BPF_H:
1103 case BPF_LD|BPF_ABS|BPF_B:
1104 v = F(opt_state, s->code, s->k, 0L);
1105 vstore(s, &val[A_ATOM], v, alter);
1108 case BPF_LD|BPF_IND|BPF_W:
1109 case BPF_LD|BPF_IND|BPF_H:
1110 case BPF_LD|BPF_IND|BPF_B:
1112 if (alter && opt_state->vmap[v].is_const) {
1113 s->code = BPF_LD|BPF_ABS|BPF_SIZE(s->code);
1114 s->k += opt_state->vmap[v].const_val;
1115 v = F(opt_state, s->code, s->k, 0L);
1116 opt_state->done = 0;
1119 v = F(opt_state, s->code, s->k, v);
1120 vstore(s, &val[A_ATOM], v, alter);
1123 case BPF_LD|BPF_LEN:
1124 v = F(opt_state, s->code, 0L, 0L);
1125 vstore(s, &val[A_ATOM], v, alter);
1128 case BPF_LD|BPF_IMM:
1130 vstore(s, &val[A_ATOM], v, alter);
1133 case BPF_LDX|BPF_IMM:
1135 vstore(s, &val[X_ATOM], v, alter);
1138 case BPF_LDX|BPF_MSH|BPF_B:
1139 v = F(opt_state, s->code, s->k, 0L);
1140 vstore(s, &val[X_ATOM], v, alter);
1143 case BPF_ALU|BPF_NEG:
1144 if (alter && opt_state->vmap[val[A_ATOM]].is_const) {
1145 s->code = BPF_LD|BPF_IMM;
1147 * Do this negation as unsigned arithmetic; that's
1148 * what modern BPF engines do, and it guarantees
1149 * that all possible values can be negated. (Yeah,
1150 * negating 0x80000000, the minimum signed 32-bit
1151 * two's-complement value, results in 0x80000000,
1152 * so it's still negative, but we *should* be doing
1153 * all unsigned arithmetic here, to match what
1154 * modern BPF engines do.)
1156 * Express it as 0U - (unsigned value) so that we
1157 * don't get compiler warnings about negating an
1158 * unsigned value and don't get UBSan warnings
1159 * about the result of negating 0x80000000 being
1162 s->k = 0U - (bpf_u_int32)(opt_state->vmap[val[A_ATOM]].const_val);
1163 val[A_ATOM] = K(s->k);
1166 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], 0L);
1169 case BPF_ALU|BPF_ADD|BPF_K:
1170 case BPF_ALU|BPF_SUB|BPF_K:
1171 case BPF_ALU|BPF_MUL|BPF_K:
1172 case BPF_ALU|BPF_DIV|BPF_K:
1173 case BPF_ALU|BPF_MOD|BPF_K:
1174 case BPF_ALU|BPF_AND|BPF_K:
1175 case BPF_ALU|BPF_OR|BPF_K:
1176 case BPF_ALU|BPF_XOR|BPF_K:
1177 case BPF_ALU|BPF_LSH|BPF_K:
1178 case BPF_ALU|BPF_RSH|BPF_K:
1179 op = BPF_OP(s->code);
1183 * Optimize operations where the constant
1186 * Don't optimize away "sub #0"
1187 * as it may be needed later to
1188 * fixup the generated math code.
1190 * Fail if we're dividing by zero or taking
1191 * a modulus by zero.
1193 if (op == BPF_ADD ||
1194 op == BPF_LSH || op == BPF_RSH ||
1195 op == BPF_OR || op == BPF_XOR) {
1199 if (op == BPF_MUL || op == BPF_AND) {
1200 s->code = BPF_LD|BPF_IMM;
1201 val[A_ATOM] = K(s->k);
1205 opt_error(opt_state,
1206 "division by zero");
1208 opt_error(opt_state,
1211 if (opt_state->vmap[val[A_ATOM]].is_const) {
1212 fold_op(opt_state, s, val[A_ATOM], K(s->k));
1213 val[A_ATOM] = K(s->k);
1217 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], K(s->k));
1220 case BPF_ALU|BPF_ADD|BPF_X:
1221 case BPF_ALU|BPF_SUB|BPF_X:
1222 case BPF_ALU|BPF_MUL|BPF_X:
1223 case BPF_ALU|BPF_DIV|BPF_X:
1224 case BPF_ALU|BPF_MOD|BPF_X:
1225 case BPF_ALU|BPF_AND|BPF_X:
1226 case BPF_ALU|BPF_OR|BPF_X:
1227 case BPF_ALU|BPF_XOR|BPF_X:
1228 case BPF_ALU|BPF_LSH|BPF_X:
1229 case BPF_ALU|BPF_RSH|BPF_X:
1230 op = BPF_OP(s->code);
1231 if (alter && opt_state->vmap[val[X_ATOM]].is_const) {
1232 if (opt_state->vmap[val[A_ATOM]].is_const) {
1233 fold_op(opt_state, s, val[A_ATOM], val[X_ATOM]);
1234 val[A_ATOM] = K(s->k);
1237 s->code = BPF_ALU|BPF_K|op;
1238 s->k = opt_state->vmap[val[X_ATOM]].const_val;
1240 * XXX - we need to make up our minds
1241 * as to what integers are signed and
1242 * what integers are unsigned in BPF
1243 * programs and in our IR.
1245 if ((op == BPF_LSH || op == BPF_RSH) &&
1246 (s->k < 0 || s->k > 31))
1247 opt_error(opt_state,
1248 "shift by more than 31 bits");
1249 opt_state->done = 0;
1251 F(opt_state, s->code, val[A_ATOM], K(s->k));
1256 * Check if we're doing something to an accumulator
1257 * that is 0, and simplify. This may not seem like
1258 * much of a simplification but it could open up further
1260 * XXX We could also check for mul by 1, etc.
1262 if (alter && opt_state->vmap[val[A_ATOM]].is_const
1263 && opt_state->vmap[val[A_ATOM]].const_val == 0) {
1264 if (op == BPF_ADD || op == BPF_OR || op == BPF_XOR) {
1265 s->code = BPF_MISC|BPF_TXA;
1266 vstore(s, &val[A_ATOM], val[X_ATOM], alter);
1269 else if (op == BPF_MUL || op == BPF_DIV || op == BPF_MOD ||
1270 op == BPF_AND || op == BPF_LSH || op == BPF_RSH) {
1271 s->code = BPF_LD|BPF_IMM;
1273 vstore(s, &val[A_ATOM], K(s->k), alter);
1276 else if (op == BPF_NEG) {
1281 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], val[X_ATOM]);
1284 case BPF_MISC|BPF_TXA:
1285 vstore(s, &val[A_ATOM], val[X_ATOM], alter);
1288 case BPF_LD|BPF_MEM:
1290 if (alter && opt_state->vmap[v].is_const) {
1291 s->code = BPF_LD|BPF_IMM;
1292 s->k = opt_state->vmap[v].const_val;
1293 opt_state->done = 0;
1295 vstore(s, &val[A_ATOM], v, alter);
1298 case BPF_MISC|BPF_TAX:
1299 vstore(s, &val[X_ATOM], val[A_ATOM], alter);
1302 case BPF_LDX|BPF_MEM:
1304 if (alter && opt_state->vmap[v].is_const) {
1305 s->code = BPF_LDX|BPF_IMM;
1306 s->k = opt_state->vmap[v].const_val;
1307 opt_state->done = 0;
1309 vstore(s, &val[X_ATOM], v, alter);
1313 vstore(s, &val[s->k], val[A_ATOM], alter);
1317 vstore(s, &val[s->k], val[X_ATOM], alter);
1323 deadstmt(opt_state_t *opt_state, register struct stmt *s, register struct stmt *last[])
1329 if (atom == AX_ATOM) {
1339 opt_state->done = 0;
1340 last[atom]->code = NOP;
1347 opt_deadstores(opt_state_t *opt_state, register struct block *b)
1349 register struct slist *s;
1351 struct stmt *last[N_ATOMS];
1353 memset((char *)last, 0, sizeof last);
1355 for (s = b->stmts; s != 0; s = s->next)
1356 deadstmt(opt_state, &s->s, last);
1357 deadstmt(opt_state, &b->s, last);
1359 for (atom = 0; atom < N_ATOMS; ++atom)
1360 if (last[atom] && !ATOMELEM(b->out_use, atom)) {
1361 last[atom]->code = NOP;
1362 opt_state->done = 0;
1367 opt_blk(opt_state_t *opt_state, struct block *b, int do_stmts)
1372 bpf_int32 aval, xval;
1375 for (s = b->stmts; s && s->next; s = s->next)
1376 if (BPF_CLASS(s->s.code) == BPF_JMP) {
1383 * Initialize the atom values.
1388 * We have no predecessors, so everything is undefined
1389 * upon entry to this block.
1391 memset((char *)b->val, 0, sizeof(b->val));
1394 * Inherit values from our predecessors.
1396 * First, get the values from the predecessor along the
1397 * first edge leading to this node.
1399 memcpy((char *)b->val, (char *)p->pred->val, sizeof(b->val));
1401 * Now look at all the other nodes leading to this node.
1402 * If, for the predecessor along that edge, a register
1403 * has a different value from the one we have (i.e.,
1404 * control paths are merging, and the merging paths
1405 * assign different values to that register), give the
1406 * register the undefined value of 0.
1408 while ((p = p->next) != NULL) {
1409 for (i = 0; i < N_ATOMS; ++i)
1410 if (b->val[i] != p->pred->val[i])
1414 aval = b->val[A_ATOM];
1415 xval = b->val[X_ATOM];
1416 for (s = b->stmts; s; s = s->next)
1417 opt_stmt(opt_state, &s->s, b->val, do_stmts);
1420 * This is a special case: if we don't use anything from this
1421 * block, and we load the accumulator or index register with a
1422 * value that is already there, or if this block is a return,
1423 * eliminate all the statements.
1425 * XXX - what if it does a store?
1427 * XXX - why does it matter whether we use anything from this
1428 * block? If the accumulator or index register doesn't change
1429 * its value, isn't that OK even if we use that value?
1431 * XXX - if we load the accumulator with a different value,
1432 * and the block ends with a conditional branch, we obviously
1433 * can't eliminate it, as the branch depends on that value.
1434 * For the index register, the conditional branch only depends
1435 * on the index register value if the test is against the index
1436 * register value rather than a constant; if nothing uses the
1437 * value we put into the index register, and we're not testing
1438 * against the index register's value, and there aren't any
1439 * other problems that would keep us from eliminating this
1440 * block, can we eliminate it?
1443 ((b->out_use == 0 &&
1444 aval != VAL_UNKNOWN && b->val[A_ATOM] == aval &&
1445 xval != VAL_UNKNOWN && b->val[X_ATOM] == xval) ||
1446 BPF_CLASS(b->s.code) == BPF_RET)) {
1447 if (b->stmts != 0) {
1449 opt_state->done = 0;
1452 opt_peep(opt_state, b);
1453 opt_deadstores(opt_state, b);
1456 * Set up values for branch optimizer.
1458 if (BPF_SRC(b->s.code) == BPF_K)
1459 b->oval = K(b->s.k);
1461 b->oval = b->val[X_ATOM];
1462 b->et.code = b->s.code;
1463 b->ef.code = -b->s.code;
1467 * Return true if any register that is used on exit from 'succ', has
1468 * an exit value that is different from the corresponding exit value
1472 use_conflict(struct block *b, struct block *succ)
1475 atomset use = succ->out_use;
1480 for (atom = 0; atom < N_ATOMS; ++atom)
1481 if (ATOMELEM(use, atom))
1482 if (b->val[atom] != succ->val[atom])
1487 static struct block *
1488 fold_edge(struct block *child, struct edge *ep)
1491 int aval0, aval1, oval0, oval1;
1492 int code = ep->code;
1500 if (child->s.code != code)
1503 aval0 = child->val[A_ATOM];
1504 oval0 = child->oval;
1505 aval1 = ep->pred->val[A_ATOM];
1506 oval1 = ep->pred->oval;
1513 * The operands of the branch instructions are
1514 * identical, so the result is true if a true
1515 * branch was taken to get here, otherwise false.
1517 return sense ? JT(child) : JF(child);
1519 if (sense && code == (BPF_JMP|BPF_JEQ|BPF_K))
1521 * At this point, we only know the comparison if we
1522 * came down the true branch, and it was an equality
1523 * comparison with a constant.
1525 * I.e., if we came down the true branch, and the branch
1526 * was an equality comparison with a constant, we know the
1527 * accumulator contains that constant. If we came down
1528 * the false branch, or the comparison wasn't with a
1529 * constant, we don't know what was in the accumulator.
1531 * We rely on the fact that distinct constants have distinct
1540 opt_j(opt_state_t *opt_state, struct edge *ep)
1543 register struct block *target;
1545 if (JT(ep->succ) == 0)
1548 if (JT(ep->succ) == JF(ep->succ)) {
1550 * Common branch targets can be eliminated, provided
1551 * there is no data dependency.
1553 if (!use_conflict(ep->pred, ep->succ->et.succ)) {
1554 opt_state->done = 0;
1555 ep->succ = JT(ep->succ);
1559 * For each edge dominator that matches the successor of this
1560 * edge, promote the edge successor to the its grandchild.
1562 * XXX We violate the set abstraction here in favor a reasonably
1566 for (i = 0; i < opt_state->edgewords; ++i) {
1567 register bpf_u_int32 x = ep->edom[i];
1570 k = lowest_set_bit(x);
1571 x &=~ ((bpf_u_int32)1 << k);
1572 k += i * BITS_PER_WORD;
1574 target = fold_edge(ep->succ, opt_state->edges[k]);
1576 * Check that there is no data dependency between
1577 * nodes that will be violated if we move the edge.
1579 if (target != 0 && !use_conflict(ep->pred, target)) {
1580 opt_state->done = 0;
1582 if (JT(target) != 0)
1584 * Start over unless we hit a leaf.
1595 or_pullup(opt_state_t *opt_state, struct block *b)
1599 struct block **diffp, **samep;
1607 * Make sure each predecessor loads the same value.
1610 val = ep->pred->val[A_ATOM];
1611 for (ep = ep->next; ep != 0; ep = ep->next)
1612 if (val != ep->pred->val[A_ATOM])
1615 if (JT(b->in_edges->pred) == b)
1616 diffp = &JT(b->in_edges->pred);
1618 diffp = &JF(b->in_edges->pred);
1625 if (JT(*diffp) != JT(b))
1628 if (!SET_MEMBER((*diffp)->dom, b->id))
1631 if ((*diffp)->val[A_ATOM] != val)
1634 diffp = &JF(*diffp);
1637 samep = &JF(*diffp);
1642 if (JT(*samep) != JT(b))
1645 if (!SET_MEMBER((*samep)->dom, b->id))
1648 if ((*samep)->val[A_ATOM] == val)
1651 /* XXX Need to check that there are no data dependencies
1652 between dp0 and dp1. Currently, the code generator
1653 will not produce such dependencies. */
1654 samep = &JF(*samep);
1657 /* XXX This doesn't cover everything. */
1658 for (i = 0; i < N_ATOMS; ++i)
1659 if ((*samep)->val[i] != pred->val[i])
1662 /* Pull up the node. */
1668 * At the top of the chain, each predecessor needs to point at the
1669 * pulled up node. Inside the chain, there is only one predecessor
1673 for (ep = b->in_edges; ep != 0; ep = ep->next) {
1674 if (JT(ep->pred) == b)
1675 JT(ep->pred) = pull;
1677 JF(ep->pred) = pull;
1683 opt_state->done = 0;
1687 and_pullup(opt_state_t *opt_state, struct block *b)
1691 struct block **diffp, **samep;
1699 * Make sure each predecessor loads the same value.
1701 val = ep->pred->val[A_ATOM];
1702 for (ep = ep->next; ep != 0; ep = ep->next)
1703 if (val != ep->pred->val[A_ATOM])
1706 if (JT(b->in_edges->pred) == b)
1707 diffp = &JT(b->in_edges->pred);
1709 diffp = &JF(b->in_edges->pred);
1716 if (JF(*diffp) != JF(b))
1719 if (!SET_MEMBER((*diffp)->dom, b->id))
1722 if ((*diffp)->val[A_ATOM] != val)
1725 diffp = &JT(*diffp);
1728 samep = &JT(*diffp);
1733 if (JF(*samep) != JF(b))
1736 if (!SET_MEMBER((*samep)->dom, b->id))
1739 if ((*samep)->val[A_ATOM] == val)
1742 /* XXX Need to check that there are no data dependencies
1743 between diffp and samep. Currently, the code generator
1744 will not produce such dependencies. */
1745 samep = &JT(*samep);
1748 /* XXX This doesn't cover everything. */
1749 for (i = 0; i < N_ATOMS; ++i)
1750 if ((*samep)->val[i] != pred->val[i])
1753 /* Pull up the node. */
1759 * At the top of the chain, each predecessor needs to point at the
1760 * pulled up node. Inside the chain, there is only one predecessor
1764 for (ep = b->in_edges; ep != 0; ep = ep->next) {
1765 if (JT(ep->pred) == b)
1766 JT(ep->pred) = pull;
1768 JF(ep->pred) = pull;
1774 opt_state->done = 0;
1778 opt_blks(opt_state_t *opt_state, struct icode *ic, int do_stmts)
1783 init_val(opt_state);
1784 maxlevel = ic->root->level;
1786 find_inedges(opt_state, ic->root);
1787 for (i = maxlevel; i >= 0; --i)
1788 for (p = opt_state->levels[i]; p; p = p->link)
1789 opt_blk(opt_state, p, do_stmts);
1793 * No point trying to move branches; it can't possibly
1794 * make a difference at this point.
1798 for (i = 1; i <= maxlevel; ++i) {
1799 for (p = opt_state->levels[i]; p; p = p->link) {
1800 opt_j(opt_state, &p->et);
1801 opt_j(opt_state, &p->ef);
1805 find_inedges(opt_state, ic->root);
1806 for (i = 1; i <= maxlevel; ++i) {
1807 for (p = opt_state->levels[i]; p; p = p->link) {
1808 or_pullup(opt_state, p);
1809 and_pullup(opt_state, p);
1815 link_inedge(struct edge *parent, struct block *child)
1817 parent->next = child->in_edges;
1818 child->in_edges = parent;
1822 find_inedges(opt_state_t *opt_state, struct block *root)
1827 for (i = 0; i < opt_state->n_blocks; ++i)
1828 opt_state->blocks[i]->in_edges = 0;
1831 * Traverse the graph, adding each edge to the predecessor
1832 * list of its successors. Skip the leaves (i.e. level 0).
1834 for (i = root->level; i > 0; --i) {
1835 for (b = opt_state->levels[i]; b != 0; b = b->link) {
1836 link_inedge(&b->et, JT(b));
1837 link_inedge(&b->ef, JF(b));
1843 opt_root(struct block **b)
1845 struct slist *tmp, *s;
1849 while (BPF_CLASS((*b)->s.code) == BPF_JMP && JT(*b) == JF(*b))
1858 * If the root node is a return, then there is no
1859 * point executing any statements (since the bpf machine
1860 * has no side effects).
1862 if (BPF_CLASS((*b)->s.code) == BPF_RET)
1867 opt_loop(opt_state_t *opt_state, struct icode *ic, int do_stmts)
1871 if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) {
1872 printf("opt_loop(root, %d) begin\n", do_stmts);
1873 opt_dump(opt_state, ic);
1877 opt_state->done = 1;
1878 find_levels(opt_state, ic);
1879 find_dom(opt_state, ic->root);
1880 find_closure(opt_state, ic->root);
1881 find_ud(opt_state, ic->root);
1882 find_edom(opt_state, ic->root);
1883 opt_blks(opt_state, ic, do_stmts);
1885 if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) {
1886 printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, opt_state->done);
1887 opt_dump(opt_state, ic);
1890 } while (!opt_state->done);
1894 * Optimize the filter code in its dag representation.
1895 * Return 0 on success, -1 on error.
1898 bpf_optimize(struct icode *ic, char *errbuf)
1900 opt_state_t opt_state;
1902 memset(&opt_state, 0, sizeof(opt_state));
1903 opt_state.errbuf = errbuf;
1904 if (setjmp(opt_state.top_ctx)) {
1905 opt_cleanup(&opt_state);
1908 opt_init(&opt_state, ic);
1909 opt_loop(&opt_state, ic, 0);
1910 opt_loop(&opt_state, ic, 1);
1911 intern_blocks(&opt_state, ic);
1913 if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) {
1914 printf("after intern_blocks()\n");
1915 opt_dump(&opt_state, ic);
1918 opt_root(&ic->root);
1920 if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) {
1921 printf("after opt_root()\n");
1922 opt_dump(&opt_state, ic);
1925 opt_cleanup(&opt_state);
1930 make_marks(struct icode *ic, struct block *p)
1932 if (!isMarked(ic, p)) {
1934 if (BPF_CLASS(p->s.code) != BPF_RET) {
1935 make_marks(ic, JT(p));
1936 make_marks(ic, JF(p));
1942 * Mark code array such that isMarked(ic->cur_mark, i) is true
1943 * only for nodes that are alive.
1946 mark_code(struct icode *ic)
1949 make_marks(ic, ic->root);
1953 * True iff the two stmt lists load the same value from the packet into
1957 eq_slist(struct slist *x, struct slist *y)
1960 while (x && x->s.code == NOP)
1962 while (y && y->s.code == NOP)
1968 if (x->s.code != y->s.code || x->s.k != y->s.k)
1976 eq_blk(struct block *b0, struct block *b1)
1978 if (b0->s.code == b1->s.code &&
1979 b0->s.k == b1->s.k &&
1980 b0->et.succ == b1->et.succ &&
1981 b0->ef.succ == b1->ef.succ)
1982 return eq_slist(b0->stmts, b1->stmts);
1987 intern_blocks(opt_state_t *opt_state, struct icode *ic)
1991 int done1; /* don't shadow global */
1994 for (i = 0; i < opt_state->n_blocks; ++i)
1995 opt_state->blocks[i]->link = 0;
1999 for (i = opt_state->n_blocks - 1; --i >= 0; ) {
2000 if (!isMarked(ic, opt_state->blocks[i]))
2002 for (j = i + 1; j < opt_state->n_blocks; ++j) {
2003 if (!isMarked(ic, opt_state->blocks[j]))
2005 if (eq_blk(opt_state->blocks[i], opt_state->blocks[j])) {
2006 opt_state->blocks[i]->link = opt_state->blocks[j]->link ?
2007 opt_state->blocks[j]->link : opt_state->blocks[j];
2012 for (i = 0; i < opt_state->n_blocks; ++i) {
2013 p = opt_state->blocks[i];
2018 JT(p) = JT(p)->link;
2022 JF(p) = JF(p)->link;
2030 opt_cleanup(opt_state_t *opt_state)
2032 free((void *)opt_state->vnode_base);
2033 free((void *)opt_state->vmap);
2034 free((void *)opt_state->edges);
2035 free((void *)opt_state->space);
2036 free((void *)opt_state->levels);
2037 free((void *)opt_state->blocks);
2041 * For optimizer errors.
2043 static void PCAP_NORETURN
2044 opt_error(opt_state_t *opt_state, const char *fmt, ...)
2048 if (opt_state->errbuf != NULL) {
2050 (void)pcap_vsnprintf(opt_state->errbuf,
2051 PCAP_ERRBUF_SIZE, fmt, ap);
2054 longjmp(opt_state->top_ctx, 1);
2059 * Return the number of stmts in 's'.
2062 slength(struct slist *s)
2066 for (; s; s = s->next)
2067 if (s->s.code != NOP)
2073 * Return the number of nodes reachable by 'p'.
2074 * All nodes should be initially unmarked.
2077 count_blocks(struct icode *ic, struct block *p)
2079 if (p == 0 || isMarked(ic, p))
2082 return count_blocks(ic, JT(p)) + count_blocks(ic, JF(p)) + 1;
2086 * Do a depth first search on the flow graph, numbering the
2087 * the basic blocks, and entering them into the 'blocks' array.`
2090 number_blks_r(opt_state_t *opt_state, struct icode *ic, struct block *p)
2094 if (p == 0 || isMarked(ic, p))
2098 n = opt_state->n_blocks++;
2100 opt_state->blocks[n] = p;
2102 number_blks_r(opt_state, ic, JT(p));
2103 number_blks_r(opt_state, ic, JF(p));
2107 * Return the number of stmts in the flowgraph reachable by 'p'.
2108 * The nodes should be unmarked before calling.
2110 * Note that "stmts" means "instructions", and that this includes
2112 * side-effect statements in 'p' (slength(p->stmts));
2114 * statements in the true branch from 'p' (count_stmts(JT(p)));
2116 * statements in the false branch from 'p' (count_stmts(JF(p)));
2118 * the conditional jump itself (1);
2120 * an extra long jump if the true branch requires it (p->longjt);
2122 * an extra long jump if the false branch requires it (p->longjf).
2125 count_stmts(struct icode *ic, struct block *p)
2129 if (p == 0 || isMarked(ic, p))
2132 n = count_stmts(ic, JT(p)) + count_stmts(ic, JF(p));
2133 return slength(p->stmts) + n + 1 + p->longjt + p->longjf;
2137 * Allocate memory. All allocation is done before optimization
2138 * is begun. A linear bound on the size of all data structures is computed
2139 * from the total number of blocks and/or statements.
2142 opt_init(opt_state_t *opt_state, struct icode *ic)
2145 int i, n, max_stmts;
2148 * First, count the blocks, so we can malloc an array to map
2149 * block number to block. Then, put the blocks into the array.
2152 n = count_blocks(ic, ic->root);
2153 opt_state->blocks = (struct block **)calloc(n, sizeof(*opt_state->blocks));
2154 if (opt_state->blocks == NULL)
2155 opt_error(opt_state, "malloc");
2157 opt_state->n_blocks = 0;
2158 number_blks_r(opt_state, ic, ic->root);
2160 opt_state->n_edges = 2 * opt_state->n_blocks;
2161 opt_state->edges = (struct edge **)calloc(opt_state->n_edges, sizeof(*opt_state->edges));
2162 if (opt_state->edges == NULL) {
2163 opt_error(opt_state, "malloc");
2167 * The number of levels is bounded by the number of nodes.
2169 opt_state->levels = (struct block **)calloc(opt_state->n_blocks, sizeof(*opt_state->levels));
2170 if (opt_state->levels == NULL) {
2171 opt_error(opt_state, "malloc");
2174 opt_state->edgewords = opt_state->n_edges / (8 * sizeof(bpf_u_int32)) + 1;
2175 opt_state->nodewords = opt_state->n_blocks / (8 * sizeof(bpf_u_int32)) + 1;
2178 opt_state->space = (bpf_u_int32 *)malloc(2 * opt_state->n_blocks * opt_state->nodewords * sizeof(*opt_state->space)
2179 + opt_state->n_edges * opt_state->edgewords * sizeof(*opt_state->space));
2180 if (opt_state->space == NULL) {
2181 opt_error(opt_state, "malloc");
2183 p = opt_state->space;
2184 opt_state->all_dom_sets = p;
2185 for (i = 0; i < n; ++i) {
2186 opt_state->blocks[i]->dom = p;
2187 p += opt_state->nodewords;
2189 opt_state->all_closure_sets = p;
2190 for (i = 0; i < n; ++i) {
2191 opt_state->blocks[i]->closure = p;
2192 p += opt_state->nodewords;
2194 opt_state->all_edge_sets = p;
2195 for (i = 0; i < n; ++i) {
2196 register struct block *b = opt_state->blocks[i];
2199 p += opt_state->edgewords;
2201 p += opt_state->edgewords;
2203 opt_state->edges[i] = &b->et;
2204 b->ef.id = opt_state->n_blocks + i;
2205 opt_state->edges[opt_state->n_blocks + i] = &b->ef;
2210 for (i = 0; i < n; ++i)
2211 max_stmts += slength(opt_state->blocks[i]->stmts) + 1;
2213 * We allocate at most 3 value numbers per statement,
2214 * so this is an upper bound on the number of valnodes
2217 opt_state->maxval = 3 * max_stmts;
2218 opt_state->vmap = (struct vmapinfo *)calloc(opt_state->maxval, sizeof(*opt_state->vmap));
2219 if (opt_state->vmap == NULL) {
2220 opt_error(opt_state, "malloc");
2222 opt_state->vnode_base = (struct valnode *)calloc(opt_state->maxval, sizeof(*opt_state->vnode_base));
2223 if (opt_state->vnode_base == NULL) {
2224 opt_error(opt_state, "malloc");
2229 * This is only used when supporting optimizer debugging. It is
2230 * global state, so do *not* do more than one compile in parallel
2231 * and expect it to provide meaningful information.
2237 static void PCAP_NORETURN conv_error(conv_state_t *, const char *, ...)
2238 PCAP_PRINTFLIKE(2, 3);
2241 * Returns true if successful. Returns false if a branch has
2242 * an offset that is too large. If so, we have marked that
2243 * branch so that on a subsequent iteration, it will be treated
2247 convert_code_r(conv_state_t *conv_state, struct icode *ic, struct block *p)
2249 struct bpf_insn *dst;
2253 u_int extrajmps; /* number of extra jumps inserted */
2254 struct slist **offset = NULL;
2256 if (p == 0 || isMarked(ic, p))
2260 if (convert_code_r(conv_state, ic, JF(p)) == 0)
2262 if (convert_code_r(conv_state, ic, JT(p)) == 0)
2265 slen = slength(p->stmts);
2266 dst = conv_state->ftail -= (slen + 1 + p->longjt + p->longjf);
2267 /* inflate length by any extra jumps */
2269 p->offset = (int)(dst - conv_state->fstart);
2271 /* generate offset[] for convenience */
2273 offset = (struct slist **)calloc(slen, sizeof(struct slist *));
2275 conv_error(conv_state, "not enough core");
2280 for (off = 0; off < slen && src; off++) {
2282 printf("off=%d src=%x\n", off, src);
2289 for (src = p->stmts; src; src = src->next) {
2290 if (src->s.code == NOP)
2292 dst->code = (u_short)src->s.code;
2295 /* fill block-local relative jump */
2296 if (BPF_CLASS(src->s.code) != BPF_JMP || src->s.code == (BPF_JMP|BPF_JA)) {
2298 if (src->s.jt || src->s.jf) {
2300 conv_error(conv_state, "illegal jmp destination");
2306 if (off == slen - 2) /*???*/
2312 const char ljerr[] = "%s for block-local relative jump: off=%d";
2315 printf("code=%x off=%d %x %x\n", src->s.code,
2316 off, src->s.jt, src->s.jf);
2319 if (!src->s.jt || !src->s.jf) {
2321 conv_error(conv_state, ljerr, "no jmp destination", off);
2326 for (i = 0; i < slen; i++) {
2327 if (offset[i] == src->s.jt) {
2330 conv_error(conv_state, ljerr, "multiple matches", off);
2334 if (i - off - 1 >= 256) {
2336 conv_error(conv_state, ljerr, "out-of-range jump", off);
2339 dst->jt = (u_char)(i - off - 1);
2342 if (offset[i] == src->s.jf) {
2345 conv_error(conv_state, ljerr, "multiple matches", off);
2348 if (i - off - 1 >= 256) {
2350 conv_error(conv_state, ljerr, "out-of-range jump", off);
2353 dst->jf = (u_char)(i - off - 1);
2359 conv_error(conv_state, ljerr, "no destination found", off);
2371 if (dst - conv_state->fstart < NBIDS)
2372 bids[dst - conv_state->fstart] = p->id + 1;
2374 dst->code = (u_short)p->s.code;
2378 off = JT(p)->offset - (p->offset + slen) - 1;
2380 /* offset too large for branch, must add a jump */
2381 if (p->longjt == 0) {
2382 /* mark this instruction and retry */
2386 /* branch if T to following jump */
2387 if (extrajmps >= 256) {
2388 conv_error(conv_state, "too many extra jumps");
2391 dst->jt = (u_char)extrajmps;
2393 dst[extrajmps].code = BPF_JMP|BPF_JA;
2394 dst[extrajmps].k = off - extrajmps;
2397 dst->jt = (u_char)off;
2398 off = JF(p)->offset - (p->offset + slen) - 1;
2400 /* offset too large for branch, must add a jump */
2401 if (p->longjf == 0) {
2402 /* mark this instruction and retry */
2406 /* branch if F to following jump */
2407 /* if two jumps are inserted, F goes to second one */
2408 if (extrajmps >= 256) {
2409 conv_error(conv_state, "too many extra jumps");
2412 dst->jf = (u_char)extrajmps;
2414 dst[extrajmps].code = BPF_JMP|BPF_JA;
2415 dst[extrajmps].k = off - extrajmps;
2418 dst->jf = (u_char)off;
2425 * Convert flowgraph intermediate representation to the
2426 * BPF array representation. Set *lenp to the number of instructions.
2428 * This routine does *NOT* leak the memory pointed to by fp. It *must
2429 * not* do free(fp) before returning fp; doing so would make no sense,
2430 * as the BPF array pointed to by the return value of icode_to_fcode()
2431 * must be valid - it's being returned for use in a bpf_program structure.
2433 * If it appears that icode_to_fcode() is leaking, the problem is that
2434 * the program using pcap_compile() is failing to free the memory in
2435 * the BPF program when it's done - the leak is in the program, not in
2436 * the routine that happens to be allocating the memory. (By analogy, if
2437 * a program calls fopen() without ever calling fclose() on the FILE *,
2438 * it will leak the FILE structure; the leak is not in fopen(), it's in
2439 * the program.) Change the program to use pcap_freecode() when it's
2440 * done with the filter program. See the pcap man page.
2443 icode_to_fcode(struct icode *ic, struct block *root, u_int *lenp,
2447 struct bpf_insn *fp;
2448 conv_state_t conv_state;
2450 conv_state.fstart = NULL;
2451 conv_state.errbuf = errbuf;
2452 if (setjmp(conv_state.top_ctx) != 0) {
2453 free(conv_state.fstart);
2458 * Loop doing convert_code_r() until no branches remain
2459 * with too-large offsets.
2463 n = *lenp = count_stmts(ic, root);
2465 fp = (struct bpf_insn *)malloc(sizeof(*fp) * n);
2467 (void)pcap_snprintf(errbuf, PCAP_ERRBUF_SIZE,
2472 memset((char *)fp, 0, sizeof(*fp) * n);
2473 conv_state.fstart = fp;
2474 conv_state.ftail = fp + n;
2477 if (convert_code_r(&conv_state, ic, root))
2486 * For iconv_to_fconv() errors.
2488 static void PCAP_NORETURN
2489 conv_error(conv_state_t *conv_state, const char *fmt, ...)
2494 (void)pcap_vsnprintf(conv_state->errbuf,
2495 PCAP_ERRBUF_SIZE, fmt, ap);
2497 longjmp(conv_state->top_ctx, 1);
2502 * Make a copy of a BPF program and put it in the "fcode" member of
2505 * If we fail to allocate memory for the copy, fill in the "errbuf"
2506 * member of the "pcap_t" with an error message, and return -1;
2507 * otherwise, return 0.
2510 install_bpf_program(pcap_t *p, struct bpf_program *fp)
2515 * Validate the program.
2517 if (!bpf_validate(fp->bf_insns, fp->bf_len)) {
2518 pcap_snprintf(p->errbuf, sizeof(p->errbuf),
2519 "BPF program is not valid");
2524 * Free up any already installed program.
2526 pcap_freecode(&p->fcode);
2528 prog_size = sizeof(*fp->bf_insns) * fp->bf_len;
2529 p->fcode.bf_len = fp->bf_len;
2530 p->fcode.bf_insns = (struct bpf_insn *)malloc(prog_size);
2531 if (p->fcode.bf_insns == NULL) {
2532 pcap_fmt_errmsg_for_errno(p->errbuf, sizeof(p->errbuf),
2536 memcpy(p->fcode.bf_insns, fp->bf_insns, prog_size);
2542 dot_dump_node(struct icode *ic, struct block *block, struct bpf_program *prog,
2545 int icount, noffset;
2548 if (block == NULL || isMarked(ic, block))
2552 icount = slength(block->stmts) + 1 + block->longjt + block->longjf;
2553 noffset = min(block->offset + icount, (int)prog->bf_len);
2555 fprintf(out, "\tblock%d [shape=ellipse, id=\"block-%d\" label=\"BLOCK%d\\n", block->id, block->id, block->id);
2556 for (i = block->offset; i < noffset; i++) {
2557 fprintf(out, "\\n%s", bpf_image(prog->bf_insns + i, i));
2559 fprintf(out, "\" tooltip=\"");
2560 for (i = 0; i < BPF_MEMWORDS; i++)
2561 if (block->val[i] != VAL_UNKNOWN)
2562 fprintf(out, "val[%d]=%d ", i, block->val[i]);
2563 fprintf(out, "val[A]=%d ", block->val[A_ATOM]);
2564 fprintf(out, "val[X]=%d", block->val[X_ATOM]);
2566 if (JT(block) == NULL)
2567 fprintf(out, ", peripheries=2");
2568 fprintf(out, "];\n");
2570 dot_dump_node(ic, JT(block), prog, out);
2571 dot_dump_node(ic, JF(block), prog, out);
2575 dot_dump_edge(struct icode *ic, struct block *block, FILE *out)
2577 if (block == NULL || isMarked(ic, block))
2582 fprintf(out, "\t\"block%d\":se -> \"block%d\":n [label=\"T\"]; \n",
2583 block->id, JT(block)->id);
2584 fprintf(out, "\t\"block%d\":sw -> \"block%d\":n [label=\"F\"]; \n",
2585 block->id, JF(block)->id);
2587 dot_dump_edge(ic, JT(block), out);
2588 dot_dump_edge(ic, JF(block), out);
2591 /* Output the block CFG using graphviz/DOT language
2592 * In the CFG, block's code, value index for each registers at EXIT,
2593 * and the jump relationship is show.
2595 * example DOT for BPF `ip src host 1.1.1.1' is:
2597 block0 [shape=ellipse, id="block-0" label="BLOCK0\n\n(000) ldh [12]\n(001) jeq #0x800 jt 2 jf 5" tooltip="val[A]=0 val[X]=0"];
2598 block1 [shape=ellipse, id="block-1" label="BLOCK1\n\n(002) ld [26]\n(003) jeq #0x1010101 jt 4 jf 5" tooltip="val[A]=0 val[X]=0"];
2599 block2 [shape=ellipse, id="block-2" label="BLOCK2\n\n(004) ret #68" tooltip="val[A]=0 val[X]=0", peripheries=2];
2600 block3 [shape=ellipse, id="block-3" label="BLOCK3\n\n(005) ret #0" tooltip="val[A]=0 val[X]=0", peripheries=2];
2601 "block0":se -> "block1":n [label="T"];
2602 "block0":sw -> "block3":n [label="F"];
2603 "block1":se -> "block2":n [label="T"];
2604 "block1":sw -> "block3":n [label="F"];
2607 * After install graphviz on http://www.graphviz.org/, save it as bpf.dot
2608 * and run `dot -Tpng -O bpf.dot' to draw the graph.
2611 dot_dump(struct icode *ic, char *errbuf)
2613 struct bpf_program f;
2616 memset(bids, 0, sizeof bids);
2617 f.bf_insns = icode_to_fcode(ic, ic->root, &f.bf_len, errbuf);
2618 if (f.bf_insns == NULL)
2621 fprintf(out, "digraph BPF {\n");
2623 dot_dump_node(ic, ic->root, &f, out);
2625 dot_dump_edge(ic, ic->root, out);
2626 fprintf(out, "}\n");
2628 free((char *)f.bf_insns);
2633 plain_dump(struct icode *ic, char *errbuf)
2635 struct bpf_program f;
2637 memset(bids, 0, sizeof bids);
2638 f.bf_insns = icode_to_fcode(ic, ic->root, &f.bf_len, errbuf);
2639 if (f.bf_insns == NULL)
2643 free((char *)f.bf_insns);
2648 opt_dump(opt_state_t *opt_state, struct icode *ic)
2651 char errbuf[PCAP_ERRBUF_SIZE];
2654 * If the CFG, in DOT format, is requested, output it rather than
2655 * the code that would be generated from that graph.
2657 if (pcap_print_dot_graph)
2658 status = dot_dump(ic, errbuf);
2660 status = plain_dump(ic, errbuf);
2662 opt_error(opt_state, "opt_dump: icode_to_fcode failed: %s", errbuf);