18cf6c252SPaul Traina /* 28cf6c252SPaul Traina * Copyright (c) 1988, 1989, 1990, 1991, 1993, 1994, 1995, 1996 38cf6c252SPaul Traina * The Regents of the University of California. All rights reserved. 48cf6c252SPaul Traina * 58cf6c252SPaul Traina * Redistribution and use in source and binary forms, with or without 68cf6c252SPaul Traina * modification, are permitted provided that: (1) source code distributions 78cf6c252SPaul Traina * retain the above copyright notice and this paragraph in its entirety, (2) 88cf6c252SPaul Traina * distributions including binary code include the above copyright notice and 98cf6c252SPaul Traina * this paragraph in its entirety in the documentation or other materials 108cf6c252SPaul Traina * provided with the distribution, and (3) all advertising materials mentioning 118cf6c252SPaul Traina * features or use of this software display the following acknowledgement: 128cf6c252SPaul Traina * ``This product includes software developed by the University of California, 138cf6c252SPaul Traina * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of 148cf6c252SPaul Traina * the University nor the names of its contributors may be used to endorse 158cf6c252SPaul Traina * or promote products derived from this software without specific prior 168cf6c252SPaul Traina * written permission. 178cf6c252SPaul Traina * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 188cf6c252SPaul Traina * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 198cf6c252SPaul Traina * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 208cf6c252SPaul Traina * 218cf6c252SPaul Traina * Optimization module for tcpdump intermediate representation. 228cf6c252SPaul Traina */ 238cf6c252SPaul Traina #ifndef lint 243052b236SBill Fenner static const char rcsid[] = 250a94d38fSBill Fenner "@(#) $Header: /tcpdump/master/libpcap/optimize.c,v 1.69 2001/11/12 21:57:06 fenner Exp $ (LBL)"; 26dc2c7305SBill Fenner #endif 27dc2c7305SBill Fenner 28dc2c7305SBill Fenner #ifdef HAVE_CONFIG_H 29dc2c7305SBill Fenner #include "config.h" 308cf6c252SPaul Traina #endif 318cf6c252SPaul Traina 328cf6c252SPaul Traina #include <sys/types.h> 338cf6c252SPaul Traina #include <sys/time.h> 348cf6c252SPaul Traina 358cf6c252SPaul Traina #include <stdio.h> 368cf6c252SPaul Traina #include <stdlib.h> 378cf6c252SPaul Traina #include <memory.h> 388cf6c252SPaul Traina 39dc2c7305SBill Fenner #include <errno.h> 40dc2c7305SBill Fenner 418cf6c252SPaul Traina #include "pcap-int.h" 428cf6c252SPaul Traina 438cf6c252SPaul Traina #include "gencode.h" 448cf6c252SPaul Traina 458cf6c252SPaul Traina #ifdef HAVE_OS_PROTO_H 468cf6c252SPaul Traina #include "os-proto.h" 478cf6c252SPaul Traina #endif 488cf6c252SPaul Traina 498cf6c252SPaul Traina #ifdef BDEBUG 508cf6c252SPaul Traina extern int dflag; 518cf6c252SPaul Traina #endif 528cf6c252SPaul Traina 538cf6c252SPaul Traina #define A_ATOM BPF_MEMWORDS 548cf6c252SPaul Traina #define X_ATOM (BPF_MEMWORDS+1) 558cf6c252SPaul Traina 568cf6c252SPaul Traina #define NOP -1 578cf6c252SPaul Traina 588cf6c252SPaul Traina /* 598cf6c252SPaul Traina * This define is used to represent *both* the accumulator and 608cf6c252SPaul Traina * x register in use-def computations. 618cf6c252SPaul Traina * Currently, the use-def code assumes only one definition per instruction. 628cf6c252SPaul Traina */ 638cf6c252SPaul Traina #define AX_ATOM N_ATOMS 648cf6c252SPaul Traina 658cf6c252SPaul Traina /* 668cf6c252SPaul Traina * A flag to indicate that further optimization is needed. 678cf6c252SPaul Traina * Iterative passes are continued until a given pass yields no 688cf6c252SPaul Traina * branch movement. 698cf6c252SPaul Traina */ 708cf6c252SPaul Traina static int done; 718cf6c252SPaul Traina 728cf6c252SPaul Traina /* 738cf6c252SPaul Traina * A block is marked if only if its mark equals the current mark. 748cf6c252SPaul Traina * Rather than traverse the code array, marking each item, 'cur_mark' is 758cf6c252SPaul Traina * incremented. This automatically makes each element unmarked. 768cf6c252SPaul Traina */ 778cf6c252SPaul Traina static int cur_mark; 788cf6c252SPaul Traina #define isMarked(p) ((p)->mark == cur_mark) 798cf6c252SPaul Traina #define unMarkAll() cur_mark += 1 808cf6c252SPaul Traina #define Mark(p) ((p)->mark = cur_mark) 818cf6c252SPaul Traina 828cf6c252SPaul Traina static void opt_init(struct block *); 838cf6c252SPaul Traina static void opt_cleanup(void); 848cf6c252SPaul Traina 858cf6c252SPaul Traina static void make_marks(struct block *); 868cf6c252SPaul Traina static void mark_code(struct block *); 878cf6c252SPaul Traina 888cf6c252SPaul Traina static void intern_blocks(struct block *); 898cf6c252SPaul Traina 908cf6c252SPaul Traina static int eq_slist(struct slist *, struct slist *); 918cf6c252SPaul Traina 928cf6c252SPaul Traina static void find_levels_r(struct block *); 938cf6c252SPaul Traina 948cf6c252SPaul Traina static void find_levels(struct block *); 958cf6c252SPaul Traina static void find_dom(struct block *); 968cf6c252SPaul Traina static void propedom(struct edge *); 978cf6c252SPaul Traina static void find_edom(struct block *); 988cf6c252SPaul Traina static void find_closure(struct block *); 998cf6c252SPaul Traina static int atomuse(struct stmt *); 1008cf6c252SPaul Traina static int atomdef(struct stmt *); 1018cf6c252SPaul Traina static void compute_local_ud(struct block *); 1028cf6c252SPaul Traina static void find_ud(struct block *); 1038cf6c252SPaul Traina static void init_val(void); 1048cf6c252SPaul Traina static int F(int, int, int); 1058cf6c252SPaul Traina static inline void vstore(struct stmt *, int *, int, int); 1068cf6c252SPaul Traina static void opt_blk(struct block *, int); 1078cf6c252SPaul Traina static int use_conflict(struct block *, struct block *); 1088cf6c252SPaul Traina static void opt_j(struct edge *); 1098cf6c252SPaul Traina static void or_pullup(struct block *); 1108cf6c252SPaul Traina static void and_pullup(struct block *); 1118cf6c252SPaul Traina static void opt_blks(struct block *, int); 1128cf6c252SPaul Traina static inline void link_inedge(struct edge *, struct block *); 1138cf6c252SPaul Traina static void find_inedges(struct block *); 1148cf6c252SPaul Traina static void opt_root(struct block **); 1158cf6c252SPaul Traina static void opt_loop(struct block *, int); 1168cf6c252SPaul Traina static void fold_op(struct stmt *, int, int); 1178cf6c252SPaul Traina static inline struct slist *this_op(struct slist *); 1188cf6c252SPaul Traina static void opt_not(struct block *); 1198cf6c252SPaul Traina static void opt_peep(struct block *); 1208cf6c252SPaul Traina static void opt_stmt(struct stmt *, int[], int); 1218cf6c252SPaul Traina static void deadstmt(struct stmt *, struct stmt *[]); 1228cf6c252SPaul Traina static void opt_deadstores(struct block *); 1238cf6c252SPaul Traina static void opt_blk(struct block *, int); 1248cf6c252SPaul Traina static int use_conflict(struct block *, struct block *); 1258cf6c252SPaul Traina static void opt_j(struct edge *); 1268cf6c252SPaul Traina static struct block *fold_edge(struct block *, struct edge *); 1278cf6c252SPaul Traina static inline int eq_blk(struct block *, struct block *); 1288cf6c252SPaul Traina static int slength(struct slist *); 1298cf6c252SPaul Traina static int count_blocks(struct block *); 1308cf6c252SPaul Traina static void number_blks_r(struct block *); 1318cf6c252SPaul Traina static int count_stmts(struct block *); 1328cf6c252SPaul Traina static int convert_code_r(struct block *); 1338cf6c252SPaul Traina #ifdef BDEBUG 1348cf6c252SPaul Traina static void opt_dump(struct block *); 1358cf6c252SPaul Traina #endif 1368cf6c252SPaul Traina 1378cf6c252SPaul Traina static int n_blocks; 1388cf6c252SPaul Traina struct block **blocks; 1398cf6c252SPaul Traina static int n_edges; 1408cf6c252SPaul Traina struct edge **edges; 1418cf6c252SPaul Traina 1428cf6c252SPaul Traina /* 1438cf6c252SPaul Traina * A bit vector set representation of the dominators. 1448cf6c252SPaul Traina * We round up the set size to the next power of two. 1458cf6c252SPaul Traina */ 1468cf6c252SPaul Traina static int nodewords; 1478cf6c252SPaul Traina static int edgewords; 1488cf6c252SPaul Traina struct block **levels; 1498cf6c252SPaul Traina bpf_u_int32 *space; 1508cf6c252SPaul Traina #define BITS_PER_WORD (8*sizeof(bpf_u_int32)) 1518cf6c252SPaul Traina /* 1528cf6c252SPaul Traina * True if a is in uset {p} 1538cf6c252SPaul Traina */ 1548cf6c252SPaul Traina #define SET_MEMBER(p, a) \ 1558cf6c252SPaul Traina ((p)[(unsigned)(a) / BITS_PER_WORD] & (1 << ((unsigned)(a) % BITS_PER_WORD))) 1568cf6c252SPaul Traina 1578cf6c252SPaul Traina /* 1588cf6c252SPaul Traina * Add 'a' to uset p. 1598cf6c252SPaul Traina */ 1608cf6c252SPaul Traina #define SET_INSERT(p, a) \ 1618cf6c252SPaul Traina (p)[(unsigned)(a) / BITS_PER_WORD] |= (1 << ((unsigned)(a) % BITS_PER_WORD)) 1628cf6c252SPaul Traina 1638cf6c252SPaul Traina /* 1648cf6c252SPaul Traina * Delete 'a' from uset p. 1658cf6c252SPaul Traina */ 1668cf6c252SPaul Traina #define SET_DELETE(p, a) \ 1678cf6c252SPaul Traina (p)[(unsigned)(a) / BITS_PER_WORD] &= ~(1 << ((unsigned)(a) % BITS_PER_WORD)) 1688cf6c252SPaul Traina 1698cf6c252SPaul Traina /* 1708cf6c252SPaul Traina * a := a intersect b 1718cf6c252SPaul Traina */ 1728cf6c252SPaul Traina #define SET_INTERSECT(a, b, n)\ 1738cf6c252SPaul Traina {\ 1748cf6c252SPaul Traina register bpf_u_int32 *_x = a, *_y = b;\ 1758cf6c252SPaul Traina register int _n = n;\ 1768cf6c252SPaul Traina while (--_n >= 0) *_x++ &= *_y++;\ 1778cf6c252SPaul Traina } 1788cf6c252SPaul Traina 1798cf6c252SPaul Traina /* 1808cf6c252SPaul Traina * a := a - b 1818cf6c252SPaul Traina */ 1828cf6c252SPaul Traina #define SET_SUBTRACT(a, b, n)\ 1838cf6c252SPaul Traina {\ 1848cf6c252SPaul Traina register bpf_u_int32 *_x = a, *_y = b;\ 1858cf6c252SPaul Traina register int _n = n;\ 1868cf6c252SPaul Traina while (--_n >= 0) *_x++ &=~ *_y++;\ 1878cf6c252SPaul Traina } 1888cf6c252SPaul Traina 1898cf6c252SPaul Traina /* 1908cf6c252SPaul Traina * a := a union b 1918cf6c252SPaul Traina */ 1928cf6c252SPaul Traina #define SET_UNION(a, b, n)\ 1938cf6c252SPaul Traina {\ 1948cf6c252SPaul Traina register bpf_u_int32 *_x = a, *_y = b;\ 1958cf6c252SPaul Traina register int _n = n;\ 1968cf6c252SPaul Traina while (--_n >= 0) *_x++ |= *_y++;\ 1978cf6c252SPaul Traina } 1988cf6c252SPaul Traina 1998cf6c252SPaul Traina static uset all_dom_sets; 2008cf6c252SPaul Traina static uset all_closure_sets; 2018cf6c252SPaul Traina static uset all_edge_sets; 2028cf6c252SPaul Traina 2038cf6c252SPaul Traina #ifndef MAX 2048cf6c252SPaul Traina #define MAX(a,b) ((a)>(b)?(a):(b)) 2058cf6c252SPaul Traina #endif 2068cf6c252SPaul Traina 2078cf6c252SPaul Traina static void 2088cf6c252SPaul Traina find_levels_r(b) 2098cf6c252SPaul Traina struct block *b; 2108cf6c252SPaul Traina { 2118cf6c252SPaul Traina int level; 2128cf6c252SPaul Traina 2138cf6c252SPaul Traina if (isMarked(b)) 2148cf6c252SPaul Traina return; 2158cf6c252SPaul Traina 2168cf6c252SPaul Traina Mark(b); 2178cf6c252SPaul Traina b->link = 0; 2188cf6c252SPaul Traina 2198cf6c252SPaul Traina if (JT(b)) { 2208cf6c252SPaul Traina find_levels_r(JT(b)); 2218cf6c252SPaul Traina find_levels_r(JF(b)); 2228cf6c252SPaul Traina level = MAX(JT(b)->level, JF(b)->level) + 1; 2238cf6c252SPaul Traina } else 2248cf6c252SPaul Traina level = 0; 2258cf6c252SPaul Traina b->level = level; 2268cf6c252SPaul Traina b->link = levels[level]; 2278cf6c252SPaul Traina levels[level] = b; 2288cf6c252SPaul Traina } 2298cf6c252SPaul Traina 2308cf6c252SPaul Traina /* 2318cf6c252SPaul Traina * Level graph. The levels go from 0 at the leaves to 2328cf6c252SPaul Traina * N_LEVELS at the root. The levels[] array points to the 2338cf6c252SPaul Traina * first node of the level list, whose elements are linked 2348cf6c252SPaul Traina * with the 'link' field of the struct block. 2358cf6c252SPaul Traina */ 2368cf6c252SPaul Traina static void 2378cf6c252SPaul Traina find_levels(root) 2388cf6c252SPaul Traina struct block *root; 2398cf6c252SPaul Traina { 2408cf6c252SPaul Traina memset((char *)levels, 0, n_blocks * sizeof(*levels)); 2418cf6c252SPaul Traina unMarkAll(); 2428cf6c252SPaul Traina find_levels_r(root); 2438cf6c252SPaul Traina } 2448cf6c252SPaul Traina 2458cf6c252SPaul Traina /* 2468cf6c252SPaul Traina * Find dominator relationships. 2478cf6c252SPaul Traina * Assumes graph has been leveled. 2488cf6c252SPaul Traina */ 2498cf6c252SPaul Traina static void 2508cf6c252SPaul Traina find_dom(root) 2518cf6c252SPaul Traina struct block *root; 2528cf6c252SPaul Traina { 2538cf6c252SPaul Traina int i; 2548cf6c252SPaul Traina struct block *b; 2558cf6c252SPaul Traina bpf_u_int32 *x; 2568cf6c252SPaul Traina 2578cf6c252SPaul Traina /* 2588cf6c252SPaul Traina * Initialize sets to contain all nodes. 2598cf6c252SPaul Traina */ 2608cf6c252SPaul Traina x = all_dom_sets; 2618cf6c252SPaul Traina i = n_blocks * nodewords; 2628cf6c252SPaul Traina while (--i >= 0) 2638cf6c252SPaul Traina *x++ = ~0; 2648cf6c252SPaul Traina /* Root starts off empty. */ 2658cf6c252SPaul Traina for (i = nodewords; --i >= 0;) 2668cf6c252SPaul Traina root->dom[i] = 0; 2678cf6c252SPaul Traina 2688cf6c252SPaul Traina /* root->level is the highest level no found. */ 2698cf6c252SPaul Traina for (i = root->level; i >= 0; --i) { 2708cf6c252SPaul Traina for (b = levels[i]; b; b = b->link) { 2718cf6c252SPaul Traina SET_INSERT(b->dom, b->id); 2728cf6c252SPaul Traina if (JT(b) == 0) 2738cf6c252SPaul Traina continue; 2748cf6c252SPaul Traina SET_INTERSECT(JT(b)->dom, b->dom, nodewords); 2758cf6c252SPaul Traina SET_INTERSECT(JF(b)->dom, b->dom, nodewords); 2768cf6c252SPaul Traina } 2778cf6c252SPaul Traina } 2788cf6c252SPaul Traina } 2798cf6c252SPaul Traina 2808cf6c252SPaul Traina static void 2818cf6c252SPaul Traina propedom(ep) 2828cf6c252SPaul Traina struct edge *ep; 2838cf6c252SPaul Traina { 2848cf6c252SPaul Traina SET_INSERT(ep->edom, ep->id); 2858cf6c252SPaul Traina if (ep->succ) { 2868cf6c252SPaul Traina SET_INTERSECT(ep->succ->et.edom, ep->edom, edgewords); 2878cf6c252SPaul Traina SET_INTERSECT(ep->succ->ef.edom, ep->edom, edgewords); 2888cf6c252SPaul Traina } 2898cf6c252SPaul Traina } 2908cf6c252SPaul Traina 2918cf6c252SPaul Traina /* 2928cf6c252SPaul Traina * Compute edge dominators. 2938cf6c252SPaul Traina * Assumes graph has been leveled and predecessors established. 2948cf6c252SPaul Traina */ 2958cf6c252SPaul Traina static void 2968cf6c252SPaul Traina find_edom(root) 2978cf6c252SPaul Traina struct block *root; 2988cf6c252SPaul Traina { 2998cf6c252SPaul Traina int i; 3008cf6c252SPaul Traina uset x; 3018cf6c252SPaul Traina struct block *b; 3028cf6c252SPaul Traina 3038cf6c252SPaul Traina x = all_edge_sets; 3048cf6c252SPaul Traina for (i = n_edges * edgewords; --i >= 0; ) 3058cf6c252SPaul Traina x[i] = ~0; 3068cf6c252SPaul Traina 3078cf6c252SPaul Traina /* root->level is the highest level no found. */ 3088cf6c252SPaul Traina memset(root->et.edom, 0, edgewords * sizeof(*(uset)0)); 3098cf6c252SPaul Traina memset(root->ef.edom, 0, edgewords * sizeof(*(uset)0)); 3108cf6c252SPaul Traina for (i = root->level; i >= 0; --i) { 3118cf6c252SPaul Traina for (b = levels[i]; b != 0; b = b->link) { 3128cf6c252SPaul Traina propedom(&b->et); 3138cf6c252SPaul Traina propedom(&b->ef); 3148cf6c252SPaul Traina } 3158cf6c252SPaul Traina } 3168cf6c252SPaul Traina } 3178cf6c252SPaul Traina 3188cf6c252SPaul Traina /* 3198cf6c252SPaul Traina * Find the backwards transitive closure of the flow graph. These sets 3208cf6c252SPaul Traina * are backwards in the sense that we find the set of nodes that reach 3218cf6c252SPaul Traina * a given node, not the set of nodes that can be reached by a node. 3228cf6c252SPaul Traina * 3238cf6c252SPaul Traina * Assumes graph has been leveled. 3248cf6c252SPaul Traina */ 3258cf6c252SPaul Traina static void 3268cf6c252SPaul Traina find_closure(root) 3278cf6c252SPaul Traina struct block *root; 3288cf6c252SPaul Traina { 3298cf6c252SPaul Traina int i; 3308cf6c252SPaul Traina struct block *b; 3318cf6c252SPaul Traina 3328cf6c252SPaul Traina /* 3338cf6c252SPaul Traina * Initialize sets to contain no nodes. 3348cf6c252SPaul Traina */ 3358cf6c252SPaul Traina memset((char *)all_closure_sets, 0, 3368cf6c252SPaul Traina n_blocks * nodewords * sizeof(*all_closure_sets)); 3378cf6c252SPaul Traina 3388cf6c252SPaul Traina /* root->level is the highest level no found. */ 3398cf6c252SPaul Traina for (i = root->level; i >= 0; --i) { 3408cf6c252SPaul Traina for (b = levels[i]; b; b = b->link) { 3418cf6c252SPaul Traina SET_INSERT(b->closure, b->id); 3428cf6c252SPaul Traina if (JT(b) == 0) 3438cf6c252SPaul Traina continue; 3448cf6c252SPaul Traina SET_UNION(JT(b)->closure, b->closure, nodewords); 3458cf6c252SPaul Traina SET_UNION(JF(b)->closure, b->closure, nodewords); 3468cf6c252SPaul Traina } 3478cf6c252SPaul Traina } 3488cf6c252SPaul Traina } 3498cf6c252SPaul Traina 3508cf6c252SPaul Traina /* 3518cf6c252SPaul Traina * Return the register number that is used by s. If A and X are both 3528cf6c252SPaul Traina * used, return AX_ATOM. If no register is used, return -1. 3538cf6c252SPaul Traina * 3548cf6c252SPaul Traina * The implementation should probably change to an array access. 3558cf6c252SPaul Traina */ 3568cf6c252SPaul Traina static int 3578cf6c252SPaul Traina atomuse(s) 3588cf6c252SPaul Traina struct stmt *s; 3598cf6c252SPaul Traina { 3608cf6c252SPaul Traina register int c = s->code; 3618cf6c252SPaul Traina 3628cf6c252SPaul Traina if (c == NOP) 3638cf6c252SPaul Traina return -1; 3648cf6c252SPaul Traina 3658cf6c252SPaul Traina switch (BPF_CLASS(c)) { 3668cf6c252SPaul Traina 3678cf6c252SPaul Traina case BPF_RET: 3688cf6c252SPaul Traina return (BPF_RVAL(c) == BPF_A) ? A_ATOM : 3698cf6c252SPaul Traina (BPF_RVAL(c) == BPF_X) ? X_ATOM : -1; 3708cf6c252SPaul Traina 3718cf6c252SPaul Traina case BPF_LD: 3728cf6c252SPaul Traina case BPF_LDX: 3738cf6c252SPaul Traina return (BPF_MODE(c) == BPF_IND) ? X_ATOM : 3748cf6c252SPaul Traina (BPF_MODE(c) == BPF_MEM) ? s->k : -1; 3758cf6c252SPaul Traina 3768cf6c252SPaul Traina case BPF_ST: 3778cf6c252SPaul Traina return A_ATOM; 3788cf6c252SPaul Traina 3798cf6c252SPaul Traina case BPF_STX: 3808cf6c252SPaul Traina return X_ATOM; 3818cf6c252SPaul Traina 3828cf6c252SPaul Traina case BPF_JMP: 3838cf6c252SPaul Traina case BPF_ALU: 3848cf6c252SPaul Traina if (BPF_SRC(c) == BPF_X) 3858cf6c252SPaul Traina return AX_ATOM; 3868cf6c252SPaul Traina return A_ATOM; 3878cf6c252SPaul Traina 3888cf6c252SPaul Traina case BPF_MISC: 3898cf6c252SPaul Traina return BPF_MISCOP(c) == BPF_TXA ? X_ATOM : A_ATOM; 3908cf6c252SPaul Traina } 3918cf6c252SPaul Traina abort(); 3928cf6c252SPaul Traina /* NOTREACHED */ 3938cf6c252SPaul Traina } 3948cf6c252SPaul Traina 3958cf6c252SPaul Traina /* 3968cf6c252SPaul Traina * Return the register number that is defined by 's'. We assume that 3978cf6c252SPaul Traina * a single stmt cannot define more than one register. If no register 3988cf6c252SPaul Traina * is defined, return -1. 3998cf6c252SPaul Traina * 4008cf6c252SPaul Traina * The implementation should probably change to an array access. 4018cf6c252SPaul Traina */ 4028cf6c252SPaul Traina static int 4038cf6c252SPaul Traina atomdef(s) 4048cf6c252SPaul Traina struct stmt *s; 4058cf6c252SPaul Traina { 4068cf6c252SPaul Traina if (s->code == NOP) 4078cf6c252SPaul Traina return -1; 4088cf6c252SPaul Traina 4098cf6c252SPaul Traina switch (BPF_CLASS(s->code)) { 4108cf6c252SPaul Traina 4118cf6c252SPaul Traina case BPF_LD: 4128cf6c252SPaul Traina case BPF_ALU: 4138cf6c252SPaul Traina return A_ATOM; 4148cf6c252SPaul Traina 4158cf6c252SPaul Traina case BPF_LDX: 4168cf6c252SPaul Traina return X_ATOM; 4178cf6c252SPaul Traina 4188cf6c252SPaul Traina case BPF_ST: 4198cf6c252SPaul Traina case BPF_STX: 4208cf6c252SPaul Traina return s->k; 4218cf6c252SPaul Traina 4228cf6c252SPaul Traina case BPF_MISC: 4238cf6c252SPaul Traina return BPF_MISCOP(s->code) == BPF_TAX ? X_ATOM : A_ATOM; 4248cf6c252SPaul Traina } 4258cf6c252SPaul Traina return -1; 4268cf6c252SPaul Traina } 4278cf6c252SPaul Traina 4288cf6c252SPaul Traina static void 4298cf6c252SPaul Traina compute_local_ud(b) 4308cf6c252SPaul Traina struct block *b; 4318cf6c252SPaul Traina { 4328cf6c252SPaul Traina struct slist *s; 4338cf6c252SPaul Traina atomset def = 0, use = 0, kill = 0; 4348cf6c252SPaul Traina int atom; 4358cf6c252SPaul Traina 4368cf6c252SPaul Traina for (s = b->stmts; s; s = s->next) { 4378cf6c252SPaul Traina if (s->s.code == NOP) 4388cf6c252SPaul Traina continue; 4398cf6c252SPaul Traina atom = atomuse(&s->s); 4408cf6c252SPaul Traina if (atom >= 0) { 4418cf6c252SPaul Traina if (atom == AX_ATOM) { 4428cf6c252SPaul Traina if (!ATOMELEM(def, X_ATOM)) 4438cf6c252SPaul Traina use |= ATOMMASK(X_ATOM); 4448cf6c252SPaul Traina if (!ATOMELEM(def, A_ATOM)) 4458cf6c252SPaul Traina use |= ATOMMASK(A_ATOM); 4468cf6c252SPaul Traina } 4478cf6c252SPaul Traina else if (atom < N_ATOMS) { 4488cf6c252SPaul Traina if (!ATOMELEM(def, atom)) 4498cf6c252SPaul Traina use |= ATOMMASK(atom); 4508cf6c252SPaul Traina } 4518cf6c252SPaul Traina else 4528cf6c252SPaul Traina abort(); 4538cf6c252SPaul Traina } 4548cf6c252SPaul Traina atom = atomdef(&s->s); 4558cf6c252SPaul Traina if (atom >= 0) { 4568cf6c252SPaul Traina if (!ATOMELEM(use, atom)) 4578cf6c252SPaul Traina kill |= ATOMMASK(atom); 4588cf6c252SPaul Traina def |= ATOMMASK(atom); 4598cf6c252SPaul Traina } 4608cf6c252SPaul Traina } 4618cf6c252SPaul Traina if (!ATOMELEM(def, A_ATOM) && BPF_CLASS(b->s.code) == BPF_JMP) 4628cf6c252SPaul Traina use |= ATOMMASK(A_ATOM); 4638cf6c252SPaul Traina 4648cf6c252SPaul Traina b->def = def; 4658cf6c252SPaul Traina b->kill = kill; 4668cf6c252SPaul Traina b->in_use = use; 4678cf6c252SPaul Traina } 4688cf6c252SPaul Traina 4698cf6c252SPaul Traina /* 4708cf6c252SPaul Traina * Assume graph is already leveled. 4718cf6c252SPaul Traina */ 4728cf6c252SPaul Traina static void 4738cf6c252SPaul Traina find_ud(root) 4748cf6c252SPaul Traina struct block *root; 4758cf6c252SPaul Traina { 4768cf6c252SPaul Traina int i, maxlevel; 4778cf6c252SPaul Traina struct block *p; 4788cf6c252SPaul Traina 4798cf6c252SPaul Traina /* 4808cf6c252SPaul Traina * root->level is the highest level no found; 4818cf6c252SPaul Traina * count down from there. 4828cf6c252SPaul Traina */ 4838cf6c252SPaul Traina maxlevel = root->level; 4848cf6c252SPaul Traina for (i = maxlevel; i >= 0; --i) 4858cf6c252SPaul Traina for (p = levels[i]; p; p = p->link) { 4868cf6c252SPaul Traina compute_local_ud(p); 4878cf6c252SPaul Traina p->out_use = 0; 4888cf6c252SPaul Traina } 4898cf6c252SPaul Traina 4908cf6c252SPaul Traina for (i = 1; i <= maxlevel; ++i) { 4918cf6c252SPaul Traina for (p = levels[i]; p; p = p->link) { 4928cf6c252SPaul Traina p->out_use |= JT(p)->in_use | JF(p)->in_use; 4938cf6c252SPaul Traina p->in_use |= p->out_use &~ p->kill; 4948cf6c252SPaul Traina } 4958cf6c252SPaul Traina } 4968cf6c252SPaul Traina } 4978cf6c252SPaul Traina 4988cf6c252SPaul Traina /* 4998cf6c252SPaul Traina * These data structures are used in a Cocke and Shwarz style 5008cf6c252SPaul Traina * value numbering scheme. Since the flowgraph is acyclic, 5018cf6c252SPaul Traina * exit values can be propagated from a node's predecessors 5028cf6c252SPaul Traina * provided it is uniquely defined. 5038cf6c252SPaul Traina */ 5048cf6c252SPaul Traina struct valnode { 5058cf6c252SPaul Traina int code; 5068cf6c252SPaul Traina int v0, v1; 5078cf6c252SPaul Traina int val; 5088cf6c252SPaul Traina struct valnode *next; 5098cf6c252SPaul Traina }; 5108cf6c252SPaul Traina 5118cf6c252SPaul Traina #define MODULUS 213 5128cf6c252SPaul Traina static struct valnode *hashtbl[MODULUS]; 5138cf6c252SPaul Traina static int curval; 5148cf6c252SPaul Traina static int maxval; 5158cf6c252SPaul Traina 5168cf6c252SPaul Traina /* Integer constants mapped with the load immediate opcode. */ 5178cf6c252SPaul Traina #define K(i) F(BPF_LD|BPF_IMM|BPF_W, i, 0L) 5188cf6c252SPaul Traina 5198cf6c252SPaul Traina struct vmapinfo { 5208cf6c252SPaul Traina int is_const; 5218cf6c252SPaul Traina bpf_int32 const_val; 5228cf6c252SPaul Traina }; 5238cf6c252SPaul Traina 5248cf6c252SPaul Traina struct vmapinfo *vmap; 5258cf6c252SPaul Traina struct valnode *vnode_base; 5268cf6c252SPaul Traina struct valnode *next_vnode; 5278cf6c252SPaul Traina 5288cf6c252SPaul Traina static void 5298cf6c252SPaul Traina init_val() 5308cf6c252SPaul Traina { 5318cf6c252SPaul Traina curval = 0; 5328cf6c252SPaul Traina next_vnode = vnode_base; 5338cf6c252SPaul Traina memset((char *)vmap, 0, maxval * sizeof(*vmap)); 5348cf6c252SPaul Traina memset((char *)hashtbl, 0, sizeof hashtbl); 5358cf6c252SPaul Traina } 5368cf6c252SPaul Traina 5378cf6c252SPaul Traina /* Because we really don't have an IR, this stuff is a little messy. */ 5388cf6c252SPaul Traina static int 5398cf6c252SPaul Traina F(code, v0, v1) 5408cf6c252SPaul Traina int code; 5418cf6c252SPaul Traina int v0, v1; 5428cf6c252SPaul Traina { 5438cf6c252SPaul Traina u_int hash; 5448cf6c252SPaul Traina int val; 5458cf6c252SPaul Traina struct valnode *p; 5468cf6c252SPaul Traina 5478cf6c252SPaul Traina hash = (u_int)code ^ (v0 << 4) ^ (v1 << 8); 5488cf6c252SPaul Traina hash %= MODULUS; 5498cf6c252SPaul Traina 5508cf6c252SPaul Traina for (p = hashtbl[hash]; p; p = p->next) 5518cf6c252SPaul Traina if (p->code == code && p->v0 == v0 && p->v1 == v1) 5528cf6c252SPaul Traina return p->val; 5538cf6c252SPaul Traina 5548cf6c252SPaul Traina val = ++curval; 5558cf6c252SPaul Traina if (BPF_MODE(code) == BPF_IMM && 5568cf6c252SPaul Traina (BPF_CLASS(code) == BPF_LD || BPF_CLASS(code) == BPF_LDX)) { 5578cf6c252SPaul Traina vmap[val].const_val = v0; 5588cf6c252SPaul Traina vmap[val].is_const = 1; 5598cf6c252SPaul Traina } 5608cf6c252SPaul Traina p = next_vnode++; 5618cf6c252SPaul Traina p->val = val; 5628cf6c252SPaul Traina p->code = code; 5638cf6c252SPaul Traina p->v0 = v0; 5648cf6c252SPaul Traina p->v1 = v1; 5658cf6c252SPaul Traina p->next = hashtbl[hash]; 5668cf6c252SPaul Traina hashtbl[hash] = p; 5678cf6c252SPaul Traina 5688cf6c252SPaul Traina return val; 5698cf6c252SPaul Traina } 5708cf6c252SPaul Traina 5718cf6c252SPaul Traina static inline void 5728cf6c252SPaul Traina vstore(s, valp, newval, alter) 5738cf6c252SPaul Traina struct stmt *s; 5748cf6c252SPaul Traina int *valp; 5758cf6c252SPaul Traina int newval; 5768cf6c252SPaul Traina int alter; 5778cf6c252SPaul Traina { 5788cf6c252SPaul Traina if (alter && *valp == newval) 5798cf6c252SPaul Traina s->code = NOP; 5808cf6c252SPaul Traina else 5818cf6c252SPaul Traina *valp = newval; 5828cf6c252SPaul Traina } 5838cf6c252SPaul Traina 5848cf6c252SPaul Traina static void 5858cf6c252SPaul Traina fold_op(s, v0, v1) 5868cf6c252SPaul Traina struct stmt *s; 5878cf6c252SPaul Traina int v0, v1; 5888cf6c252SPaul Traina { 5898cf6c252SPaul Traina bpf_int32 a, b; 5908cf6c252SPaul Traina 5918cf6c252SPaul Traina a = vmap[v0].const_val; 5928cf6c252SPaul Traina b = vmap[v1].const_val; 5938cf6c252SPaul Traina 5948cf6c252SPaul Traina switch (BPF_OP(s->code)) { 5958cf6c252SPaul Traina case BPF_ADD: 5968cf6c252SPaul Traina a += b; 5978cf6c252SPaul Traina break; 5988cf6c252SPaul Traina 5998cf6c252SPaul Traina case BPF_SUB: 6008cf6c252SPaul Traina a -= b; 6018cf6c252SPaul Traina break; 6028cf6c252SPaul Traina 6038cf6c252SPaul Traina case BPF_MUL: 6048cf6c252SPaul Traina a *= b; 6058cf6c252SPaul Traina break; 6068cf6c252SPaul Traina 6078cf6c252SPaul Traina case BPF_DIV: 6088cf6c252SPaul Traina if (b == 0) 6098cf6c252SPaul Traina bpf_error("division by zero"); 6108cf6c252SPaul Traina a /= b; 6118cf6c252SPaul Traina break; 6128cf6c252SPaul Traina 6138cf6c252SPaul Traina case BPF_AND: 6148cf6c252SPaul Traina a &= b; 6158cf6c252SPaul Traina break; 6168cf6c252SPaul Traina 6178cf6c252SPaul Traina case BPF_OR: 6188cf6c252SPaul Traina a |= b; 6198cf6c252SPaul Traina break; 6208cf6c252SPaul Traina 6218cf6c252SPaul Traina case BPF_LSH: 6228cf6c252SPaul Traina a <<= b; 6238cf6c252SPaul Traina break; 6248cf6c252SPaul Traina 6258cf6c252SPaul Traina case BPF_RSH: 6268cf6c252SPaul Traina a >>= b; 6278cf6c252SPaul Traina break; 6288cf6c252SPaul Traina 6298cf6c252SPaul Traina case BPF_NEG: 6308cf6c252SPaul Traina a = -a; 6318cf6c252SPaul Traina break; 6328cf6c252SPaul Traina 6338cf6c252SPaul Traina default: 6348cf6c252SPaul Traina abort(); 6358cf6c252SPaul Traina } 6368cf6c252SPaul Traina s->k = a; 6378cf6c252SPaul Traina s->code = BPF_LD|BPF_IMM; 6388cf6c252SPaul Traina done = 0; 6398cf6c252SPaul Traina } 6408cf6c252SPaul Traina 6418cf6c252SPaul Traina static inline struct slist * 6428cf6c252SPaul Traina this_op(s) 6438cf6c252SPaul Traina struct slist *s; 6448cf6c252SPaul Traina { 6458cf6c252SPaul Traina while (s != 0 && s->s.code == NOP) 6468cf6c252SPaul Traina s = s->next; 6478cf6c252SPaul Traina return s; 6488cf6c252SPaul Traina } 6498cf6c252SPaul Traina 6508cf6c252SPaul Traina static void 6518cf6c252SPaul Traina opt_not(b) 6528cf6c252SPaul Traina struct block *b; 6538cf6c252SPaul Traina { 6548cf6c252SPaul Traina struct block *tmp = JT(b); 6558cf6c252SPaul Traina 6568cf6c252SPaul Traina JT(b) = JF(b); 6578cf6c252SPaul Traina JF(b) = tmp; 6588cf6c252SPaul Traina } 6598cf6c252SPaul Traina 6608cf6c252SPaul Traina static void 6618cf6c252SPaul Traina opt_peep(b) 6628cf6c252SPaul Traina struct block *b; 6638cf6c252SPaul Traina { 6648cf6c252SPaul Traina struct slist *s; 6658cf6c252SPaul Traina struct slist *next, *last; 6668cf6c252SPaul Traina int val; 6678cf6c252SPaul Traina 6688cf6c252SPaul Traina s = b->stmts; 6698cf6c252SPaul Traina if (s == 0) 6708cf6c252SPaul Traina return; 6718cf6c252SPaul Traina 6728cf6c252SPaul Traina last = s; 6738cf6c252SPaul Traina while (1) { 6748cf6c252SPaul Traina s = this_op(s); 6758cf6c252SPaul Traina if (s == 0) 6768cf6c252SPaul Traina break; 6778cf6c252SPaul Traina next = this_op(s->next); 6788cf6c252SPaul Traina if (next == 0) 6798cf6c252SPaul Traina break; 6808cf6c252SPaul Traina last = next; 6818cf6c252SPaul Traina 6828cf6c252SPaul Traina /* 6838cf6c252SPaul Traina * st M[k] --> st M[k] 6848cf6c252SPaul Traina * ldx M[k] tax 6858cf6c252SPaul Traina */ 6868cf6c252SPaul Traina if (s->s.code == BPF_ST && 6878cf6c252SPaul Traina next->s.code == (BPF_LDX|BPF_MEM) && 6888cf6c252SPaul Traina s->s.k == next->s.k) { 6898cf6c252SPaul Traina done = 0; 6908cf6c252SPaul Traina next->s.code = BPF_MISC|BPF_TAX; 6918cf6c252SPaul Traina } 6928cf6c252SPaul Traina /* 6938cf6c252SPaul Traina * ld #k --> ldx #k 6948cf6c252SPaul Traina * tax txa 6958cf6c252SPaul Traina */ 6968cf6c252SPaul Traina if (s->s.code == (BPF_LD|BPF_IMM) && 6978cf6c252SPaul Traina next->s.code == (BPF_MISC|BPF_TAX)) { 6988cf6c252SPaul Traina s->s.code = BPF_LDX|BPF_IMM; 6998cf6c252SPaul Traina next->s.code = BPF_MISC|BPF_TXA; 7008cf6c252SPaul Traina done = 0; 7018cf6c252SPaul Traina } 7028cf6c252SPaul Traina /* 7038cf6c252SPaul Traina * This is an ugly special case, but it happens 7048cf6c252SPaul Traina * when you say tcp[k] or udp[k] where k is a constant. 7058cf6c252SPaul Traina */ 7068cf6c252SPaul Traina if (s->s.code == (BPF_LD|BPF_IMM)) { 7078cf6c252SPaul Traina struct slist *add, *tax, *ild; 7088cf6c252SPaul Traina 7098cf6c252SPaul Traina /* 7108cf6c252SPaul Traina * Check that X isn't used on exit from this 7118cf6c252SPaul Traina * block (which the optimizer might cause). 7128cf6c252SPaul Traina * We know the code generator won't generate 7138cf6c252SPaul Traina * any local dependencies. 7148cf6c252SPaul Traina */ 7158cf6c252SPaul Traina if (ATOMELEM(b->out_use, X_ATOM)) 7168cf6c252SPaul Traina break; 7178cf6c252SPaul Traina 7188cf6c252SPaul Traina if (next->s.code != (BPF_LDX|BPF_MSH|BPF_B)) 7198cf6c252SPaul Traina add = next; 7208cf6c252SPaul Traina else 7218cf6c252SPaul Traina add = this_op(next->next); 7228cf6c252SPaul Traina if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X)) 7238cf6c252SPaul Traina break; 7248cf6c252SPaul Traina 7258cf6c252SPaul Traina tax = this_op(add->next); 7268cf6c252SPaul Traina if (tax == 0 || tax->s.code != (BPF_MISC|BPF_TAX)) 7278cf6c252SPaul Traina break; 7288cf6c252SPaul Traina 7298cf6c252SPaul Traina ild = this_op(tax->next); 7308cf6c252SPaul Traina if (ild == 0 || BPF_CLASS(ild->s.code) != BPF_LD || 7318cf6c252SPaul Traina BPF_MODE(ild->s.code) != BPF_IND) 7328cf6c252SPaul Traina break; 7338cf6c252SPaul Traina /* 7348cf6c252SPaul Traina * XXX We need to check that X is not 7358cf6c252SPaul Traina * subsequently used. We know we can eliminate the 7368cf6c252SPaul Traina * accumulator modifications since it is defined 7378cf6c252SPaul Traina * by the last stmt of this sequence. 7388cf6c252SPaul Traina * 7398cf6c252SPaul Traina * We want to turn this sequence: 7408cf6c252SPaul Traina * 7418cf6c252SPaul Traina * (004) ldi #0x2 {s} 7428cf6c252SPaul Traina * (005) ldxms [14] {next} -- optional 7438cf6c252SPaul Traina * (006) addx {add} 7448cf6c252SPaul Traina * (007) tax {tax} 7458cf6c252SPaul Traina * (008) ild [x+0] {ild} 7468cf6c252SPaul Traina * 7478cf6c252SPaul Traina * into this sequence: 7488cf6c252SPaul Traina * 7498cf6c252SPaul Traina * (004) nop 7508cf6c252SPaul Traina * (005) ldxms [14] 7518cf6c252SPaul Traina * (006) nop 7528cf6c252SPaul Traina * (007) nop 7538cf6c252SPaul Traina * (008) ild [x+2] 7548cf6c252SPaul Traina * 7558cf6c252SPaul Traina */ 7568cf6c252SPaul Traina ild->s.k += s->s.k; 7578cf6c252SPaul Traina s->s.code = NOP; 7588cf6c252SPaul Traina add->s.code = NOP; 7598cf6c252SPaul Traina tax->s.code = NOP; 7608cf6c252SPaul Traina done = 0; 7618cf6c252SPaul Traina } 7628cf6c252SPaul Traina s = next; 7638cf6c252SPaul Traina } 7648cf6c252SPaul Traina /* 7658cf6c252SPaul Traina * If we have a subtract to do a comparison, and the X register 7668cf6c252SPaul Traina * is a known constant, we can merge this value into the 7678cf6c252SPaul Traina * comparison. 7688cf6c252SPaul Traina */ 7698cf6c252SPaul Traina if (last->s.code == (BPF_ALU|BPF_SUB|BPF_X) && 7708cf6c252SPaul Traina !ATOMELEM(b->out_use, A_ATOM)) { 7718cf6c252SPaul Traina val = b->val[X_ATOM]; 7728cf6c252SPaul Traina if (vmap[val].is_const) { 7738cf6c252SPaul Traina int op; 7748cf6c252SPaul Traina 7758cf6c252SPaul Traina b->s.k += vmap[val].const_val; 7768cf6c252SPaul Traina op = BPF_OP(b->s.code); 7778cf6c252SPaul Traina if (op == BPF_JGT || op == BPF_JGE) { 7788cf6c252SPaul Traina struct block *t = JT(b); 7798cf6c252SPaul Traina JT(b) = JF(b); 7808cf6c252SPaul Traina JF(b) = t; 7818cf6c252SPaul Traina b->s.k += 0x80000000; 7828cf6c252SPaul Traina } 7838cf6c252SPaul Traina last->s.code = NOP; 7848cf6c252SPaul Traina done = 0; 7858cf6c252SPaul Traina } else if (b->s.k == 0) { 7868cf6c252SPaul Traina /* 7878cf6c252SPaul Traina * sub x -> nop 7888cf6c252SPaul Traina * j #0 j x 7898cf6c252SPaul Traina */ 7908cf6c252SPaul Traina last->s.code = NOP; 7918cf6c252SPaul Traina b->s.code = BPF_CLASS(b->s.code) | BPF_OP(b->s.code) | 7928cf6c252SPaul Traina BPF_X; 7938cf6c252SPaul Traina done = 0; 7948cf6c252SPaul Traina } 7958cf6c252SPaul Traina } 7968cf6c252SPaul Traina /* 7978cf6c252SPaul Traina * Likewise, a constant subtract can be simplified. 7988cf6c252SPaul Traina */ 7998cf6c252SPaul Traina else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K) && 8008cf6c252SPaul Traina !ATOMELEM(b->out_use, A_ATOM)) { 8018cf6c252SPaul Traina int op; 8028cf6c252SPaul Traina 8038cf6c252SPaul Traina b->s.k += last->s.k; 8048cf6c252SPaul Traina last->s.code = NOP; 8058cf6c252SPaul Traina op = BPF_OP(b->s.code); 8068cf6c252SPaul Traina if (op == BPF_JGT || op == BPF_JGE) { 8078cf6c252SPaul Traina struct block *t = JT(b); 8088cf6c252SPaul Traina JT(b) = JF(b); 8098cf6c252SPaul Traina JF(b) = t; 8108cf6c252SPaul Traina b->s.k += 0x80000000; 8118cf6c252SPaul Traina } 8128cf6c252SPaul Traina done = 0; 8138cf6c252SPaul Traina } 8148cf6c252SPaul Traina /* 8158cf6c252SPaul Traina * and #k nop 8168cf6c252SPaul Traina * jeq #0 -> jset #k 8178cf6c252SPaul Traina */ 8188cf6c252SPaul Traina if (last->s.code == (BPF_ALU|BPF_AND|BPF_K) && 8198cf6c252SPaul Traina !ATOMELEM(b->out_use, A_ATOM) && b->s.k == 0) { 8208cf6c252SPaul Traina b->s.k = last->s.k; 8218cf6c252SPaul Traina b->s.code = BPF_JMP|BPF_K|BPF_JSET; 8228cf6c252SPaul Traina last->s.code = NOP; 8238cf6c252SPaul Traina done = 0; 8248cf6c252SPaul Traina opt_not(b); 8258cf6c252SPaul Traina } 8268cf6c252SPaul Traina /* 8278cf6c252SPaul Traina * If the accumulator is a known constant, we can compute the 8288cf6c252SPaul Traina * comparison result. 8298cf6c252SPaul Traina */ 8308cf6c252SPaul Traina val = b->val[A_ATOM]; 8318cf6c252SPaul Traina if (vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) { 8328cf6c252SPaul Traina bpf_int32 v = vmap[val].const_val; 8338cf6c252SPaul Traina switch (BPF_OP(b->s.code)) { 8348cf6c252SPaul Traina 8358cf6c252SPaul Traina case BPF_JEQ: 8368cf6c252SPaul Traina v = v == b->s.k; 8378cf6c252SPaul Traina break; 8388cf6c252SPaul Traina 8398cf6c252SPaul Traina case BPF_JGT: 8408cf6c252SPaul Traina v = (unsigned)v > b->s.k; 8418cf6c252SPaul Traina break; 8428cf6c252SPaul Traina 8438cf6c252SPaul Traina case BPF_JGE: 8448cf6c252SPaul Traina v = (unsigned)v >= b->s.k; 8458cf6c252SPaul Traina break; 8468cf6c252SPaul Traina 8478cf6c252SPaul Traina case BPF_JSET: 8488cf6c252SPaul Traina v &= b->s.k; 8498cf6c252SPaul Traina break; 8508cf6c252SPaul Traina 8518cf6c252SPaul Traina default: 8528cf6c252SPaul Traina abort(); 8538cf6c252SPaul Traina } 8548cf6c252SPaul Traina if (JF(b) != JT(b)) 8558cf6c252SPaul Traina done = 0; 8568cf6c252SPaul Traina if (v) 8578cf6c252SPaul Traina JF(b) = JT(b); 8588cf6c252SPaul Traina else 8598cf6c252SPaul Traina JT(b) = JF(b); 8608cf6c252SPaul Traina } 8618cf6c252SPaul Traina } 8628cf6c252SPaul Traina 8638cf6c252SPaul Traina /* 8648cf6c252SPaul Traina * Compute the symbolic value of expression of 's', and update 8658cf6c252SPaul Traina * anything it defines in the value table 'val'. If 'alter' is true, 8668cf6c252SPaul Traina * do various optimizations. This code would be cleaner if symbolic 8678cf6c252SPaul Traina * evaluation and code transformations weren't folded together. 8688cf6c252SPaul Traina */ 8698cf6c252SPaul Traina static void 8708cf6c252SPaul Traina opt_stmt(s, val, alter) 8718cf6c252SPaul Traina struct stmt *s; 8728cf6c252SPaul Traina int val[]; 8738cf6c252SPaul Traina int alter; 8748cf6c252SPaul Traina { 8758cf6c252SPaul Traina int op; 8768cf6c252SPaul Traina int v; 8778cf6c252SPaul Traina 8788cf6c252SPaul Traina switch (s->code) { 8798cf6c252SPaul Traina 8808cf6c252SPaul Traina case BPF_LD|BPF_ABS|BPF_W: 8818cf6c252SPaul Traina case BPF_LD|BPF_ABS|BPF_H: 8828cf6c252SPaul Traina case BPF_LD|BPF_ABS|BPF_B: 8838cf6c252SPaul Traina v = F(s->code, s->k, 0L); 8848cf6c252SPaul Traina vstore(s, &val[A_ATOM], v, alter); 8858cf6c252SPaul Traina break; 8868cf6c252SPaul Traina 8878cf6c252SPaul Traina case BPF_LD|BPF_IND|BPF_W: 8888cf6c252SPaul Traina case BPF_LD|BPF_IND|BPF_H: 8898cf6c252SPaul Traina case BPF_LD|BPF_IND|BPF_B: 8908cf6c252SPaul Traina v = val[X_ATOM]; 8918cf6c252SPaul Traina if (alter && vmap[v].is_const) { 8928cf6c252SPaul Traina s->code = BPF_LD|BPF_ABS|BPF_SIZE(s->code); 8938cf6c252SPaul Traina s->k += vmap[v].const_val; 8948cf6c252SPaul Traina v = F(s->code, s->k, 0L); 8958cf6c252SPaul Traina done = 0; 8968cf6c252SPaul Traina } 8978cf6c252SPaul Traina else 8988cf6c252SPaul Traina v = F(s->code, s->k, v); 8998cf6c252SPaul Traina vstore(s, &val[A_ATOM], v, alter); 9008cf6c252SPaul Traina break; 9018cf6c252SPaul Traina 9028cf6c252SPaul Traina case BPF_LD|BPF_LEN: 9038cf6c252SPaul Traina v = F(s->code, 0L, 0L); 9048cf6c252SPaul Traina vstore(s, &val[A_ATOM], v, alter); 9058cf6c252SPaul Traina break; 9068cf6c252SPaul Traina 9078cf6c252SPaul Traina case BPF_LD|BPF_IMM: 9088cf6c252SPaul Traina v = K(s->k); 9098cf6c252SPaul Traina vstore(s, &val[A_ATOM], v, alter); 9108cf6c252SPaul Traina break; 9118cf6c252SPaul Traina 9128cf6c252SPaul Traina case BPF_LDX|BPF_IMM: 9138cf6c252SPaul Traina v = K(s->k); 9148cf6c252SPaul Traina vstore(s, &val[X_ATOM], v, alter); 9158cf6c252SPaul Traina break; 9168cf6c252SPaul Traina 9178cf6c252SPaul Traina case BPF_LDX|BPF_MSH|BPF_B: 9188cf6c252SPaul Traina v = F(s->code, s->k, 0L); 9198cf6c252SPaul Traina vstore(s, &val[X_ATOM], v, alter); 9208cf6c252SPaul Traina break; 9218cf6c252SPaul Traina 9228cf6c252SPaul Traina case BPF_ALU|BPF_NEG: 9238cf6c252SPaul Traina if (alter && vmap[val[A_ATOM]].is_const) { 9248cf6c252SPaul Traina s->code = BPF_LD|BPF_IMM; 9258cf6c252SPaul Traina s->k = -vmap[val[A_ATOM]].const_val; 9268cf6c252SPaul Traina val[A_ATOM] = K(s->k); 9278cf6c252SPaul Traina } 9288cf6c252SPaul Traina else 9298cf6c252SPaul Traina val[A_ATOM] = F(s->code, val[A_ATOM], 0L); 9308cf6c252SPaul Traina break; 9318cf6c252SPaul Traina 9328cf6c252SPaul Traina case BPF_ALU|BPF_ADD|BPF_K: 9338cf6c252SPaul Traina case BPF_ALU|BPF_SUB|BPF_K: 9348cf6c252SPaul Traina case BPF_ALU|BPF_MUL|BPF_K: 9358cf6c252SPaul Traina case BPF_ALU|BPF_DIV|BPF_K: 9368cf6c252SPaul Traina case BPF_ALU|BPF_AND|BPF_K: 9378cf6c252SPaul Traina case BPF_ALU|BPF_OR|BPF_K: 9388cf6c252SPaul Traina case BPF_ALU|BPF_LSH|BPF_K: 9398cf6c252SPaul Traina case BPF_ALU|BPF_RSH|BPF_K: 9408cf6c252SPaul Traina op = BPF_OP(s->code); 9418cf6c252SPaul Traina if (alter) { 9428cf6c252SPaul Traina if (s->k == 0) { 9430a94d38fSBill Fenner /* don't optimize away "sub #0" 9440a94d38fSBill Fenner * as it may be needed later to 9450a94d38fSBill Fenner * fixup the generated math code */ 9460a94d38fSBill Fenner if (op == BPF_ADD || 9478cf6c252SPaul Traina op == BPF_LSH || op == BPF_RSH || 9488cf6c252SPaul Traina op == BPF_OR) { 9498cf6c252SPaul Traina s->code = NOP; 9508cf6c252SPaul Traina break; 9518cf6c252SPaul Traina } 9528cf6c252SPaul Traina if (op == BPF_MUL || op == BPF_AND) { 9538cf6c252SPaul Traina s->code = BPF_LD|BPF_IMM; 9548cf6c252SPaul Traina val[A_ATOM] = K(s->k); 9558cf6c252SPaul Traina break; 9568cf6c252SPaul Traina } 9578cf6c252SPaul Traina } 9588cf6c252SPaul Traina if (vmap[val[A_ATOM]].is_const) { 9598cf6c252SPaul Traina fold_op(s, val[A_ATOM], K(s->k)); 9608cf6c252SPaul Traina val[A_ATOM] = K(s->k); 9618cf6c252SPaul Traina break; 9628cf6c252SPaul Traina } 9638cf6c252SPaul Traina } 9648cf6c252SPaul Traina val[A_ATOM] = F(s->code, val[A_ATOM], K(s->k)); 9658cf6c252SPaul Traina break; 9668cf6c252SPaul Traina 9678cf6c252SPaul Traina case BPF_ALU|BPF_ADD|BPF_X: 9688cf6c252SPaul Traina case BPF_ALU|BPF_SUB|BPF_X: 9698cf6c252SPaul Traina case BPF_ALU|BPF_MUL|BPF_X: 9708cf6c252SPaul Traina case BPF_ALU|BPF_DIV|BPF_X: 9718cf6c252SPaul Traina case BPF_ALU|BPF_AND|BPF_X: 9728cf6c252SPaul Traina case BPF_ALU|BPF_OR|BPF_X: 9738cf6c252SPaul Traina case BPF_ALU|BPF_LSH|BPF_X: 9748cf6c252SPaul Traina case BPF_ALU|BPF_RSH|BPF_X: 9758cf6c252SPaul Traina op = BPF_OP(s->code); 9768cf6c252SPaul Traina if (alter && vmap[val[X_ATOM]].is_const) { 9778cf6c252SPaul Traina if (vmap[val[A_ATOM]].is_const) { 9788cf6c252SPaul Traina fold_op(s, val[A_ATOM], val[X_ATOM]); 9798cf6c252SPaul Traina val[A_ATOM] = K(s->k); 9808cf6c252SPaul Traina } 9818cf6c252SPaul Traina else { 9828cf6c252SPaul Traina s->code = BPF_ALU|BPF_K|op; 9838cf6c252SPaul Traina s->k = vmap[val[X_ATOM]].const_val; 9848cf6c252SPaul Traina done = 0; 9858cf6c252SPaul Traina val[A_ATOM] = 9868cf6c252SPaul Traina F(s->code, val[A_ATOM], K(s->k)); 9878cf6c252SPaul Traina } 9888cf6c252SPaul Traina break; 9898cf6c252SPaul Traina } 9908cf6c252SPaul Traina /* 9918cf6c252SPaul Traina * Check if we're doing something to an accumulator 9928cf6c252SPaul Traina * that is 0, and simplify. This may not seem like 9938cf6c252SPaul Traina * much of a simplification but it could open up further 9948cf6c252SPaul Traina * optimizations. 9958cf6c252SPaul Traina * XXX We could also check for mul by 1, and -1, etc. 9968cf6c252SPaul Traina */ 9978cf6c252SPaul Traina if (alter && vmap[val[A_ATOM]].is_const 9988cf6c252SPaul Traina && vmap[val[A_ATOM]].const_val == 0) { 9998cf6c252SPaul Traina if (op == BPF_ADD || op == BPF_OR || 10008cf6c252SPaul Traina op == BPF_LSH || op == BPF_RSH || op == BPF_SUB) { 10018cf6c252SPaul Traina s->code = BPF_MISC|BPF_TXA; 10028cf6c252SPaul Traina vstore(s, &val[A_ATOM], val[X_ATOM], alter); 10038cf6c252SPaul Traina break; 10048cf6c252SPaul Traina } 10058cf6c252SPaul Traina else if (op == BPF_MUL || op == BPF_DIV || 10068cf6c252SPaul Traina op == BPF_AND) { 10078cf6c252SPaul Traina s->code = BPF_LD|BPF_IMM; 10088cf6c252SPaul Traina s->k = 0; 10098cf6c252SPaul Traina vstore(s, &val[A_ATOM], K(s->k), alter); 10108cf6c252SPaul Traina break; 10118cf6c252SPaul Traina } 10128cf6c252SPaul Traina else if (op == BPF_NEG) { 10138cf6c252SPaul Traina s->code = NOP; 10148cf6c252SPaul Traina break; 10158cf6c252SPaul Traina } 10168cf6c252SPaul Traina } 10178cf6c252SPaul Traina val[A_ATOM] = F(s->code, val[A_ATOM], val[X_ATOM]); 10188cf6c252SPaul Traina break; 10198cf6c252SPaul Traina 10208cf6c252SPaul Traina case BPF_MISC|BPF_TXA: 10218cf6c252SPaul Traina vstore(s, &val[A_ATOM], val[X_ATOM], alter); 10228cf6c252SPaul Traina break; 10238cf6c252SPaul Traina 10248cf6c252SPaul Traina case BPF_LD|BPF_MEM: 10258cf6c252SPaul Traina v = val[s->k]; 10268cf6c252SPaul Traina if (alter && vmap[v].is_const) { 10278cf6c252SPaul Traina s->code = BPF_LD|BPF_IMM; 10288cf6c252SPaul Traina s->k = vmap[v].const_val; 10298cf6c252SPaul Traina done = 0; 10308cf6c252SPaul Traina } 10318cf6c252SPaul Traina vstore(s, &val[A_ATOM], v, alter); 10328cf6c252SPaul Traina break; 10338cf6c252SPaul Traina 10348cf6c252SPaul Traina case BPF_MISC|BPF_TAX: 10358cf6c252SPaul Traina vstore(s, &val[X_ATOM], val[A_ATOM], alter); 10368cf6c252SPaul Traina break; 10378cf6c252SPaul Traina 10388cf6c252SPaul Traina case BPF_LDX|BPF_MEM: 10398cf6c252SPaul Traina v = val[s->k]; 10408cf6c252SPaul Traina if (alter && vmap[v].is_const) { 10418cf6c252SPaul Traina s->code = BPF_LDX|BPF_IMM; 10428cf6c252SPaul Traina s->k = vmap[v].const_val; 10438cf6c252SPaul Traina done = 0; 10448cf6c252SPaul Traina } 10458cf6c252SPaul Traina vstore(s, &val[X_ATOM], v, alter); 10468cf6c252SPaul Traina break; 10478cf6c252SPaul Traina 10488cf6c252SPaul Traina case BPF_ST: 10498cf6c252SPaul Traina vstore(s, &val[s->k], val[A_ATOM], alter); 10508cf6c252SPaul Traina break; 10518cf6c252SPaul Traina 10528cf6c252SPaul Traina case BPF_STX: 10538cf6c252SPaul Traina vstore(s, &val[s->k], val[X_ATOM], alter); 10548cf6c252SPaul Traina break; 10558cf6c252SPaul Traina } 10568cf6c252SPaul Traina } 10578cf6c252SPaul Traina 10588cf6c252SPaul Traina static void 10598cf6c252SPaul Traina deadstmt(s, last) 10608cf6c252SPaul Traina register struct stmt *s; 10618cf6c252SPaul Traina register struct stmt *last[]; 10628cf6c252SPaul Traina { 10638cf6c252SPaul Traina register int atom; 10648cf6c252SPaul Traina 10658cf6c252SPaul Traina atom = atomuse(s); 10668cf6c252SPaul Traina if (atom >= 0) { 10678cf6c252SPaul Traina if (atom == AX_ATOM) { 10688cf6c252SPaul Traina last[X_ATOM] = 0; 10698cf6c252SPaul Traina last[A_ATOM] = 0; 10708cf6c252SPaul Traina } 10718cf6c252SPaul Traina else 10728cf6c252SPaul Traina last[atom] = 0; 10738cf6c252SPaul Traina } 10748cf6c252SPaul Traina atom = atomdef(s); 10758cf6c252SPaul Traina if (atom >= 0) { 10768cf6c252SPaul Traina if (last[atom]) { 10778cf6c252SPaul Traina done = 0; 10788cf6c252SPaul Traina last[atom]->code = NOP; 10798cf6c252SPaul Traina } 10808cf6c252SPaul Traina last[atom] = s; 10818cf6c252SPaul Traina } 10828cf6c252SPaul Traina } 10838cf6c252SPaul Traina 10848cf6c252SPaul Traina static void 10858cf6c252SPaul Traina opt_deadstores(b) 10868cf6c252SPaul Traina register struct block *b; 10878cf6c252SPaul Traina { 10888cf6c252SPaul Traina register struct slist *s; 10898cf6c252SPaul Traina register int atom; 10908cf6c252SPaul Traina struct stmt *last[N_ATOMS]; 10918cf6c252SPaul Traina 10928cf6c252SPaul Traina memset((char *)last, 0, sizeof last); 10938cf6c252SPaul Traina 10948cf6c252SPaul Traina for (s = b->stmts; s != 0; s = s->next) 10958cf6c252SPaul Traina deadstmt(&s->s, last); 10968cf6c252SPaul Traina deadstmt(&b->s, last); 10978cf6c252SPaul Traina 10988cf6c252SPaul Traina for (atom = 0; atom < N_ATOMS; ++atom) 10998cf6c252SPaul Traina if (last[atom] && !ATOMELEM(b->out_use, atom)) { 11008cf6c252SPaul Traina last[atom]->code = NOP; 11018cf6c252SPaul Traina done = 0; 11028cf6c252SPaul Traina } 11038cf6c252SPaul Traina } 11048cf6c252SPaul Traina 11058cf6c252SPaul Traina static void 11068cf6c252SPaul Traina opt_blk(b, do_stmts) 11078cf6c252SPaul Traina struct block *b; 11088cf6c252SPaul Traina int do_stmts; 11098cf6c252SPaul Traina { 11108cf6c252SPaul Traina struct slist *s; 11118cf6c252SPaul Traina struct edge *p; 11128cf6c252SPaul Traina int i; 11138cf6c252SPaul Traina bpf_int32 aval; 11148cf6c252SPaul Traina 11158751327cSBill Fenner #if 0 11168751327cSBill Fenner for (s = b->stmts; s && s->next; s = s->next) 11178751327cSBill Fenner if (BPF_CLASS(s->s.code) == BPF_JMP) { 11188751327cSBill Fenner do_stmts = 0; 11198751327cSBill Fenner break; 11208751327cSBill Fenner } 11218751327cSBill Fenner #endif 11228751327cSBill Fenner 11238cf6c252SPaul Traina /* 11248cf6c252SPaul Traina * Initialize the atom values. 11258cf6c252SPaul Traina * If we have no predecessors, everything is undefined. 11268cf6c252SPaul Traina * Otherwise, we inherent our values from our predecessors. 11278cf6c252SPaul Traina * If any register has an ambiguous value (i.e. control paths are 11288cf6c252SPaul Traina * merging) give it the undefined value of 0. 11298cf6c252SPaul Traina */ 11308cf6c252SPaul Traina p = b->in_edges; 11318cf6c252SPaul Traina if (p == 0) 11328cf6c252SPaul Traina memset((char *)b->val, 0, sizeof(b->val)); 11338cf6c252SPaul Traina else { 11348cf6c252SPaul Traina memcpy((char *)b->val, (char *)p->pred->val, sizeof(b->val)); 11358cf6c252SPaul Traina while ((p = p->next) != NULL) { 11368cf6c252SPaul Traina for (i = 0; i < N_ATOMS; ++i) 11378cf6c252SPaul Traina if (b->val[i] != p->pred->val[i]) 11388cf6c252SPaul Traina b->val[i] = 0; 11398cf6c252SPaul Traina } 11408cf6c252SPaul Traina } 11418cf6c252SPaul Traina aval = b->val[A_ATOM]; 11428cf6c252SPaul Traina for (s = b->stmts; s; s = s->next) 11438cf6c252SPaul Traina opt_stmt(&s->s, b->val, do_stmts); 11448cf6c252SPaul Traina 11458cf6c252SPaul Traina /* 11468cf6c252SPaul Traina * This is a special case: if we don't use anything from this 11478cf6c252SPaul Traina * block, and we load the accumulator with value that is 11488cf6c252SPaul Traina * already there, or if this block is a return, 11498cf6c252SPaul Traina * eliminate all the statements. 11508cf6c252SPaul Traina */ 11518cf6c252SPaul Traina if (do_stmts && 11528cf6c252SPaul Traina ((b->out_use == 0 && aval != 0 &&b->val[A_ATOM] == aval) || 11538cf6c252SPaul Traina BPF_CLASS(b->s.code) == BPF_RET)) { 11548cf6c252SPaul Traina if (b->stmts != 0) { 11558cf6c252SPaul Traina b->stmts = 0; 11568cf6c252SPaul Traina done = 0; 11578cf6c252SPaul Traina } 11588cf6c252SPaul Traina } else { 11598cf6c252SPaul Traina opt_peep(b); 11608cf6c252SPaul Traina opt_deadstores(b); 11618cf6c252SPaul Traina } 11628cf6c252SPaul Traina /* 11638cf6c252SPaul Traina * Set up values for branch optimizer. 11648cf6c252SPaul Traina */ 11658cf6c252SPaul Traina if (BPF_SRC(b->s.code) == BPF_K) 11668cf6c252SPaul Traina b->oval = K(b->s.k); 11678cf6c252SPaul Traina else 11688cf6c252SPaul Traina b->oval = b->val[X_ATOM]; 11698cf6c252SPaul Traina b->et.code = b->s.code; 11708cf6c252SPaul Traina b->ef.code = -b->s.code; 11718cf6c252SPaul Traina } 11728cf6c252SPaul Traina 11738cf6c252SPaul Traina /* 11748cf6c252SPaul Traina * Return true if any register that is used on exit from 'succ', has 11758cf6c252SPaul Traina * an exit value that is different from the corresponding exit value 11768cf6c252SPaul Traina * from 'b'. 11778cf6c252SPaul Traina */ 11788cf6c252SPaul Traina static int 11798cf6c252SPaul Traina use_conflict(b, succ) 11808cf6c252SPaul Traina struct block *b, *succ; 11818cf6c252SPaul Traina { 11828cf6c252SPaul Traina int atom; 11838cf6c252SPaul Traina atomset use = succ->out_use; 11848cf6c252SPaul Traina 11858cf6c252SPaul Traina if (use == 0) 11868cf6c252SPaul Traina return 0; 11878cf6c252SPaul Traina 11888cf6c252SPaul Traina for (atom = 0; atom < N_ATOMS; ++atom) 11898cf6c252SPaul Traina if (ATOMELEM(use, atom)) 11908cf6c252SPaul Traina if (b->val[atom] != succ->val[atom]) 11918cf6c252SPaul Traina return 1; 11928cf6c252SPaul Traina return 0; 11938cf6c252SPaul Traina } 11948cf6c252SPaul Traina 11958cf6c252SPaul Traina static struct block * 11968cf6c252SPaul Traina fold_edge(child, ep) 11978cf6c252SPaul Traina struct block *child; 11988cf6c252SPaul Traina struct edge *ep; 11998cf6c252SPaul Traina { 12008cf6c252SPaul Traina int sense; 12018cf6c252SPaul Traina int aval0, aval1, oval0, oval1; 12028cf6c252SPaul Traina int code = ep->code; 12038cf6c252SPaul Traina 12048cf6c252SPaul Traina if (code < 0) { 12058cf6c252SPaul Traina code = -code; 12068cf6c252SPaul Traina sense = 0; 12078cf6c252SPaul Traina } else 12088cf6c252SPaul Traina sense = 1; 12098cf6c252SPaul Traina 12108cf6c252SPaul Traina if (child->s.code != code) 12118cf6c252SPaul Traina return 0; 12128cf6c252SPaul Traina 12138cf6c252SPaul Traina aval0 = child->val[A_ATOM]; 12148cf6c252SPaul Traina oval0 = child->oval; 12158cf6c252SPaul Traina aval1 = ep->pred->val[A_ATOM]; 12168cf6c252SPaul Traina oval1 = ep->pred->oval; 12178cf6c252SPaul Traina 12188cf6c252SPaul Traina if (aval0 != aval1) 12198cf6c252SPaul Traina return 0; 12208cf6c252SPaul Traina 12218cf6c252SPaul Traina if (oval0 == oval1) 12228cf6c252SPaul Traina /* 12238cf6c252SPaul Traina * The operands are identical, so the 12248cf6c252SPaul Traina * result is true if a true branch was 12258cf6c252SPaul Traina * taken to get here, otherwise false. 12268cf6c252SPaul Traina */ 12278cf6c252SPaul Traina return sense ? JT(child) : JF(child); 12288cf6c252SPaul Traina 12298cf6c252SPaul Traina if (sense && code == (BPF_JMP|BPF_JEQ|BPF_K)) 12308cf6c252SPaul Traina /* 12318cf6c252SPaul Traina * At this point, we only know the comparison if we 12328cf6c252SPaul Traina * came down the true branch, and it was an equality 12338cf6c252SPaul Traina * comparison with a constant. We rely on the fact that 12348cf6c252SPaul Traina * distinct constants have distinct value numbers. 12358cf6c252SPaul Traina */ 12368cf6c252SPaul Traina return JF(child); 12378cf6c252SPaul Traina 12388cf6c252SPaul Traina return 0; 12398cf6c252SPaul Traina } 12408cf6c252SPaul Traina 12418cf6c252SPaul Traina static void 12428cf6c252SPaul Traina opt_j(ep) 12438cf6c252SPaul Traina struct edge *ep; 12448cf6c252SPaul Traina { 12458cf6c252SPaul Traina register int i, k; 12468cf6c252SPaul Traina register struct block *target; 12478cf6c252SPaul Traina 12488cf6c252SPaul Traina if (JT(ep->succ) == 0) 12498cf6c252SPaul Traina return; 12508cf6c252SPaul Traina 12518cf6c252SPaul Traina if (JT(ep->succ) == JF(ep->succ)) { 12528cf6c252SPaul Traina /* 12538cf6c252SPaul Traina * Common branch targets can be eliminated, provided 12548cf6c252SPaul Traina * there is no data dependency. 12558cf6c252SPaul Traina */ 12568cf6c252SPaul Traina if (!use_conflict(ep->pred, ep->succ->et.succ)) { 12578cf6c252SPaul Traina done = 0; 12588cf6c252SPaul Traina ep->succ = JT(ep->succ); 12598cf6c252SPaul Traina } 12608cf6c252SPaul Traina } 12618cf6c252SPaul Traina /* 12628cf6c252SPaul Traina * For each edge dominator that matches the successor of this 12638cf6c252SPaul Traina * edge, promote the edge successor to the its grandchild. 12648cf6c252SPaul Traina * 12658cf6c252SPaul Traina * XXX We violate the set abstraction here in favor a reasonably 12668cf6c252SPaul Traina * efficient loop. 12678cf6c252SPaul Traina */ 12688cf6c252SPaul Traina top: 12698cf6c252SPaul Traina for (i = 0; i < edgewords; ++i) { 12708cf6c252SPaul Traina register bpf_u_int32 x = ep->edom[i]; 12718cf6c252SPaul Traina 12728cf6c252SPaul Traina while (x != 0) { 12738cf6c252SPaul Traina k = ffs(x) - 1; 12748cf6c252SPaul Traina x &=~ (1 << k); 12758cf6c252SPaul Traina k += i * BITS_PER_WORD; 12768cf6c252SPaul Traina 12778cf6c252SPaul Traina target = fold_edge(ep->succ, edges[k]); 12788cf6c252SPaul Traina /* 12798cf6c252SPaul Traina * Check that there is no data dependency between 12808cf6c252SPaul Traina * nodes that will be violated if we move the edge. 12818cf6c252SPaul Traina */ 12828cf6c252SPaul Traina if (target != 0 && !use_conflict(ep->pred, target)) { 12838cf6c252SPaul Traina done = 0; 12848cf6c252SPaul Traina ep->succ = target; 12858cf6c252SPaul Traina if (JT(target) != 0) 12868cf6c252SPaul Traina /* 12878cf6c252SPaul Traina * Start over unless we hit a leaf. 12888cf6c252SPaul Traina */ 12898cf6c252SPaul Traina goto top; 12908cf6c252SPaul Traina return; 12918cf6c252SPaul Traina } 12928cf6c252SPaul Traina } 12938cf6c252SPaul Traina } 12948cf6c252SPaul Traina } 12958cf6c252SPaul Traina 12968cf6c252SPaul Traina 12978cf6c252SPaul Traina static void 12988cf6c252SPaul Traina or_pullup(b) 12998cf6c252SPaul Traina struct block *b; 13008cf6c252SPaul Traina { 13018cf6c252SPaul Traina int val, at_top; 13028cf6c252SPaul Traina struct block *pull; 13038cf6c252SPaul Traina struct block **diffp, **samep; 13048cf6c252SPaul Traina struct edge *ep; 13058cf6c252SPaul Traina 13068cf6c252SPaul Traina ep = b->in_edges; 13078cf6c252SPaul Traina if (ep == 0) 13088cf6c252SPaul Traina return; 13098cf6c252SPaul Traina 13108cf6c252SPaul Traina /* 13118cf6c252SPaul Traina * Make sure each predecessor loads the same value. 13128cf6c252SPaul Traina * XXX why? 13138cf6c252SPaul Traina */ 13148cf6c252SPaul Traina val = ep->pred->val[A_ATOM]; 13158cf6c252SPaul Traina for (ep = ep->next; ep != 0; ep = ep->next) 13168cf6c252SPaul Traina if (val != ep->pred->val[A_ATOM]) 13178cf6c252SPaul Traina return; 13188cf6c252SPaul Traina 13198cf6c252SPaul Traina if (JT(b->in_edges->pred) == b) 13208cf6c252SPaul Traina diffp = &JT(b->in_edges->pred); 13218cf6c252SPaul Traina else 13228cf6c252SPaul Traina diffp = &JF(b->in_edges->pred); 13238cf6c252SPaul Traina 13248cf6c252SPaul Traina at_top = 1; 13258cf6c252SPaul Traina while (1) { 13268cf6c252SPaul Traina if (*diffp == 0) 13278cf6c252SPaul Traina return; 13288cf6c252SPaul Traina 13298cf6c252SPaul Traina if (JT(*diffp) != JT(b)) 13308cf6c252SPaul Traina return; 13318cf6c252SPaul Traina 13328cf6c252SPaul Traina if (!SET_MEMBER((*diffp)->dom, b->id)) 13338cf6c252SPaul Traina return; 13348cf6c252SPaul Traina 13358cf6c252SPaul Traina if ((*diffp)->val[A_ATOM] != val) 13368cf6c252SPaul Traina break; 13378cf6c252SPaul Traina 13388cf6c252SPaul Traina diffp = &JF(*diffp); 13398cf6c252SPaul Traina at_top = 0; 13408cf6c252SPaul Traina } 13418cf6c252SPaul Traina samep = &JF(*diffp); 13428cf6c252SPaul Traina while (1) { 13438cf6c252SPaul Traina if (*samep == 0) 13448cf6c252SPaul Traina return; 13458cf6c252SPaul Traina 13468cf6c252SPaul Traina if (JT(*samep) != JT(b)) 13478cf6c252SPaul Traina return; 13488cf6c252SPaul Traina 13498cf6c252SPaul Traina if (!SET_MEMBER((*samep)->dom, b->id)) 13508cf6c252SPaul Traina return; 13518cf6c252SPaul Traina 13528cf6c252SPaul Traina if ((*samep)->val[A_ATOM] == val) 13538cf6c252SPaul Traina break; 13548cf6c252SPaul Traina 13558cf6c252SPaul Traina /* XXX Need to check that there are no data dependencies 13568cf6c252SPaul Traina between dp0 and dp1. Currently, the code generator 13578cf6c252SPaul Traina will not produce such dependencies. */ 13588cf6c252SPaul Traina samep = &JF(*samep); 13598cf6c252SPaul Traina } 13608cf6c252SPaul Traina #ifdef notdef 13618cf6c252SPaul Traina /* XXX This doesn't cover everything. */ 13628cf6c252SPaul Traina for (i = 0; i < N_ATOMS; ++i) 13638cf6c252SPaul Traina if ((*samep)->val[i] != pred->val[i]) 13648cf6c252SPaul Traina return; 13658cf6c252SPaul Traina #endif 13668cf6c252SPaul Traina /* Pull up the node. */ 13678cf6c252SPaul Traina pull = *samep; 13688cf6c252SPaul Traina *samep = JF(pull); 13698cf6c252SPaul Traina JF(pull) = *diffp; 13708cf6c252SPaul Traina 13718cf6c252SPaul Traina /* 13728cf6c252SPaul Traina * At the top of the chain, each predecessor needs to point at the 13738cf6c252SPaul Traina * pulled up node. Inside the chain, there is only one predecessor 13748cf6c252SPaul Traina * to worry about. 13758cf6c252SPaul Traina */ 13768cf6c252SPaul Traina if (at_top) { 13778cf6c252SPaul Traina for (ep = b->in_edges; ep != 0; ep = ep->next) { 13788cf6c252SPaul Traina if (JT(ep->pred) == b) 13798cf6c252SPaul Traina JT(ep->pred) = pull; 13808cf6c252SPaul Traina else 13818cf6c252SPaul Traina JF(ep->pred) = pull; 13828cf6c252SPaul Traina } 13838cf6c252SPaul Traina } 13848cf6c252SPaul Traina else 13858cf6c252SPaul Traina *diffp = pull; 13868cf6c252SPaul Traina 13878cf6c252SPaul Traina done = 0; 13888cf6c252SPaul Traina } 13898cf6c252SPaul Traina 13908cf6c252SPaul Traina static void 13918cf6c252SPaul Traina and_pullup(b) 13928cf6c252SPaul Traina struct block *b; 13938cf6c252SPaul Traina { 13948cf6c252SPaul Traina int val, at_top; 13958cf6c252SPaul Traina struct block *pull; 13968cf6c252SPaul Traina struct block **diffp, **samep; 13978cf6c252SPaul Traina struct edge *ep; 13988cf6c252SPaul Traina 13998cf6c252SPaul Traina ep = b->in_edges; 14008cf6c252SPaul Traina if (ep == 0) 14018cf6c252SPaul Traina return; 14028cf6c252SPaul Traina 14038cf6c252SPaul Traina /* 14048cf6c252SPaul Traina * Make sure each predecessor loads the same value. 14058cf6c252SPaul Traina */ 14068cf6c252SPaul Traina val = ep->pred->val[A_ATOM]; 14078cf6c252SPaul Traina for (ep = ep->next; ep != 0; ep = ep->next) 14088cf6c252SPaul Traina if (val != ep->pred->val[A_ATOM]) 14098cf6c252SPaul Traina return; 14108cf6c252SPaul Traina 14118cf6c252SPaul Traina if (JT(b->in_edges->pred) == b) 14128cf6c252SPaul Traina diffp = &JT(b->in_edges->pred); 14138cf6c252SPaul Traina else 14148cf6c252SPaul Traina diffp = &JF(b->in_edges->pred); 14158cf6c252SPaul Traina 14168cf6c252SPaul Traina at_top = 1; 14178cf6c252SPaul Traina while (1) { 14188cf6c252SPaul Traina if (*diffp == 0) 14198cf6c252SPaul Traina return; 14208cf6c252SPaul Traina 14218cf6c252SPaul Traina if (JF(*diffp) != JF(b)) 14228cf6c252SPaul Traina return; 14238cf6c252SPaul Traina 14248cf6c252SPaul Traina if (!SET_MEMBER((*diffp)->dom, b->id)) 14258cf6c252SPaul Traina return; 14268cf6c252SPaul Traina 14278cf6c252SPaul Traina if ((*diffp)->val[A_ATOM] != val) 14288cf6c252SPaul Traina break; 14298cf6c252SPaul Traina 14308cf6c252SPaul Traina diffp = &JT(*diffp); 14318cf6c252SPaul Traina at_top = 0; 14328cf6c252SPaul Traina } 14338cf6c252SPaul Traina samep = &JT(*diffp); 14348cf6c252SPaul Traina while (1) { 14358cf6c252SPaul Traina if (*samep == 0) 14368cf6c252SPaul Traina return; 14378cf6c252SPaul Traina 14388cf6c252SPaul Traina if (JF(*samep) != JF(b)) 14398cf6c252SPaul Traina return; 14408cf6c252SPaul Traina 14418cf6c252SPaul Traina if (!SET_MEMBER((*samep)->dom, b->id)) 14428cf6c252SPaul Traina return; 14438cf6c252SPaul Traina 14448cf6c252SPaul Traina if ((*samep)->val[A_ATOM] == val) 14458cf6c252SPaul Traina break; 14468cf6c252SPaul Traina 14478cf6c252SPaul Traina /* XXX Need to check that there are no data dependencies 14488cf6c252SPaul Traina between diffp and samep. Currently, the code generator 14498cf6c252SPaul Traina will not produce such dependencies. */ 14508cf6c252SPaul Traina samep = &JT(*samep); 14518cf6c252SPaul Traina } 14528cf6c252SPaul Traina #ifdef notdef 14538cf6c252SPaul Traina /* XXX This doesn't cover everything. */ 14548cf6c252SPaul Traina for (i = 0; i < N_ATOMS; ++i) 14558cf6c252SPaul Traina if ((*samep)->val[i] != pred->val[i]) 14568cf6c252SPaul Traina return; 14578cf6c252SPaul Traina #endif 14588cf6c252SPaul Traina /* Pull up the node. */ 14598cf6c252SPaul Traina pull = *samep; 14608cf6c252SPaul Traina *samep = JT(pull); 14618cf6c252SPaul Traina JT(pull) = *diffp; 14628cf6c252SPaul Traina 14638cf6c252SPaul Traina /* 14648cf6c252SPaul Traina * At the top of the chain, each predecessor needs to point at the 14658cf6c252SPaul Traina * pulled up node. Inside the chain, there is only one predecessor 14668cf6c252SPaul Traina * to worry about. 14678cf6c252SPaul Traina */ 14688cf6c252SPaul Traina if (at_top) { 14698cf6c252SPaul Traina for (ep = b->in_edges; ep != 0; ep = ep->next) { 14708cf6c252SPaul Traina if (JT(ep->pred) == b) 14718cf6c252SPaul Traina JT(ep->pred) = pull; 14728cf6c252SPaul Traina else 14738cf6c252SPaul Traina JF(ep->pred) = pull; 14748cf6c252SPaul Traina } 14758cf6c252SPaul Traina } 14768cf6c252SPaul Traina else 14778cf6c252SPaul Traina *diffp = pull; 14788cf6c252SPaul Traina 14798cf6c252SPaul Traina done = 0; 14808cf6c252SPaul Traina } 14818cf6c252SPaul Traina 14828cf6c252SPaul Traina static void 14838cf6c252SPaul Traina opt_blks(root, do_stmts) 14848cf6c252SPaul Traina struct block *root; 14858cf6c252SPaul Traina int do_stmts; 14868cf6c252SPaul Traina { 14878cf6c252SPaul Traina int i, maxlevel; 14888cf6c252SPaul Traina struct block *p; 14898cf6c252SPaul Traina 14908cf6c252SPaul Traina init_val(); 14918cf6c252SPaul Traina maxlevel = root->level; 1492dc2c7305SBill Fenner 1493dc2c7305SBill Fenner find_inedges(root); 14948cf6c252SPaul Traina for (i = maxlevel; i >= 0; --i) 14958cf6c252SPaul Traina for (p = levels[i]; p; p = p->link) 14968cf6c252SPaul Traina opt_blk(p, do_stmts); 14978cf6c252SPaul Traina 14988cf6c252SPaul Traina if (do_stmts) 14998cf6c252SPaul Traina /* 15008cf6c252SPaul Traina * No point trying to move branches; it can't possibly 15018cf6c252SPaul Traina * make a difference at this point. 15028cf6c252SPaul Traina */ 15038cf6c252SPaul Traina return; 15048cf6c252SPaul Traina 15058cf6c252SPaul Traina for (i = 1; i <= maxlevel; ++i) { 15068cf6c252SPaul Traina for (p = levels[i]; p; p = p->link) { 15078cf6c252SPaul Traina opt_j(&p->et); 15088cf6c252SPaul Traina opt_j(&p->ef); 15098cf6c252SPaul Traina } 15108cf6c252SPaul Traina } 1511dc2c7305SBill Fenner 1512dc2c7305SBill Fenner find_inedges(root); 15138cf6c252SPaul Traina for (i = 1; i <= maxlevel; ++i) { 15148cf6c252SPaul Traina for (p = levels[i]; p; p = p->link) { 15158cf6c252SPaul Traina or_pullup(p); 15168cf6c252SPaul Traina and_pullup(p); 15178cf6c252SPaul Traina } 15188cf6c252SPaul Traina } 15198cf6c252SPaul Traina } 15208cf6c252SPaul Traina 15218cf6c252SPaul Traina static inline void 15228cf6c252SPaul Traina link_inedge(parent, child) 15238cf6c252SPaul Traina struct edge *parent; 15248cf6c252SPaul Traina struct block *child; 15258cf6c252SPaul Traina { 15268cf6c252SPaul Traina parent->next = child->in_edges; 15278cf6c252SPaul Traina child->in_edges = parent; 15288cf6c252SPaul Traina } 15298cf6c252SPaul Traina 15308cf6c252SPaul Traina static void 15318cf6c252SPaul Traina find_inedges(root) 15328cf6c252SPaul Traina struct block *root; 15338cf6c252SPaul Traina { 15348cf6c252SPaul Traina int i; 15358cf6c252SPaul Traina struct block *b; 15368cf6c252SPaul Traina 15378cf6c252SPaul Traina for (i = 0; i < n_blocks; ++i) 15388cf6c252SPaul Traina blocks[i]->in_edges = 0; 15398cf6c252SPaul Traina 15408cf6c252SPaul Traina /* 15418cf6c252SPaul Traina * Traverse the graph, adding each edge to the predecessor 15428cf6c252SPaul Traina * list of its successors. Skip the leaves (i.e. level 0). 15438cf6c252SPaul Traina */ 15448cf6c252SPaul Traina for (i = root->level; i > 0; --i) { 15458cf6c252SPaul Traina for (b = levels[i]; b != 0; b = b->link) { 15468cf6c252SPaul Traina link_inedge(&b->et, JT(b)); 15478cf6c252SPaul Traina link_inedge(&b->ef, JF(b)); 15488cf6c252SPaul Traina } 15498cf6c252SPaul Traina } 15508cf6c252SPaul Traina } 15518cf6c252SPaul Traina 15528cf6c252SPaul Traina static void 15538cf6c252SPaul Traina opt_root(b) 15548cf6c252SPaul Traina struct block **b; 15558cf6c252SPaul Traina { 15568cf6c252SPaul Traina struct slist *tmp, *s; 15578cf6c252SPaul Traina 15588cf6c252SPaul Traina s = (*b)->stmts; 15598cf6c252SPaul Traina (*b)->stmts = 0; 15608cf6c252SPaul Traina while (BPF_CLASS((*b)->s.code) == BPF_JMP && JT(*b) == JF(*b)) 15618cf6c252SPaul Traina *b = JT(*b); 15628cf6c252SPaul Traina 15638cf6c252SPaul Traina tmp = (*b)->stmts; 15648cf6c252SPaul Traina if (tmp != 0) 15658cf6c252SPaul Traina sappend(s, tmp); 15668cf6c252SPaul Traina (*b)->stmts = s; 15678cf6c252SPaul Traina 15688cf6c252SPaul Traina /* 15698cf6c252SPaul Traina * If the root node is a return, then there is no 15708cf6c252SPaul Traina * point executing any statements (since the bpf machine 15718cf6c252SPaul Traina * has no side effects). 15728cf6c252SPaul Traina */ 15738cf6c252SPaul Traina if (BPF_CLASS((*b)->s.code) == BPF_RET) 15748cf6c252SPaul Traina (*b)->stmts = 0; 15758cf6c252SPaul Traina } 15768cf6c252SPaul Traina 15778cf6c252SPaul Traina static void 15788cf6c252SPaul Traina opt_loop(root, do_stmts) 15798cf6c252SPaul Traina struct block *root; 15808cf6c252SPaul Traina int do_stmts; 15818cf6c252SPaul Traina { 15828cf6c252SPaul Traina 15838cf6c252SPaul Traina #ifdef BDEBUG 15840a94d38fSBill Fenner if (dflag > 1) { 15850a94d38fSBill Fenner printf("opt_loop(root, %d) begin\n", do_stmts); 15868cf6c252SPaul Traina opt_dump(root); 15870a94d38fSBill Fenner } 15888cf6c252SPaul Traina #endif 15898cf6c252SPaul Traina do { 15908cf6c252SPaul Traina done = 1; 15918cf6c252SPaul Traina find_levels(root); 15928cf6c252SPaul Traina find_dom(root); 15938cf6c252SPaul Traina find_closure(root); 15948cf6c252SPaul Traina find_ud(root); 15958cf6c252SPaul Traina find_edom(root); 15968cf6c252SPaul Traina opt_blks(root, do_stmts); 15978cf6c252SPaul Traina #ifdef BDEBUG 15980a94d38fSBill Fenner if (dflag > 1) { 15990a94d38fSBill Fenner printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, done); 16008cf6c252SPaul Traina opt_dump(root); 16010a94d38fSBill Fenner } 16028cf6c252SPaul Traina #endif 16038cf6c252SPaul Traina } while (!done); 16048cf6c252SPaul Traina } 16058cf6c252SPaul Traina 16068cf6c252SPaul Traina /* 16078cf6c252SPaul Traina * Optimize the filter code in its dag representation. 16088cf6c252SPaul Traina */ 16098cf6c252SPaul Traina void 16108cf6c252SPaul Traina bpf_optimize(rootp) 16118cf6c252SPaul Traina struct block **rootp; 16128cf6c252SPaul Traina { 16138cf6c252SPaul Traina struct block *root; 16148cf6c252SPaul Traina 16158cf6c252SPaul Traina root = *rootp; 16168cf6c252SPaul Traina 16178cf6c252SPaul Traina opt_init(root); 16188cf6c252SPaul Traina opt_loop(root, 0); 16198cf6c252SPaul Traina opt_loop(root, 1); 16208cf6c252SPaul Traina intern_blocks(root); 16210a94d38fSBill Fenner #ifdef BDEBUG 16220a94d38fSBill Fenner if (dflag > 1) { 16230a94d38fSBill Fenner printf("after intern_blocks()\n"); 16240a94d38fSBill Fenner opt_dump(root); 16250a94d38fSBill Fenner } 16260a94d38fSBill Fenner #endif 16278cf6c252SPaul Traina opt_root(rootp); 16280a94d38fSBill Fenner #ifdef BDEBUG 16290a94d38fSBill Fenner if (dflag > 1) { 16300a94d38fSBill Fenner printf("after opt_root()\n"); 16310a94d38fSBill Fenner opt_dump(root); 16320a94d38fSBill Fenner } 16330a94d38fSBill Fenner #endif 16348cf6c252SPaul Traina opt_cleanup(); 16358cf6c252SPaul Traina } 16368cf6c252SPaul Traina 16378cf6c252SPaul Traina static void 16388cf6c252SPaul Traina make_marks(p) 16398cf6c252SPaul Traina struct block *p; 16408cf6c252SPaul Traina { 16418cf6c252SPaul Traina if (!isMarked(p)) { 16428cf6c252SPaul Traina Mark(p); 16438cf6c252SPaul Traina if (BPF_CLASS(p->s.code) != BPF_RET) { 16448cf6c252SPaul Traina make_marks(JT(p)); 16458cf6c252SPaul Traina make_marks(JF(p)); 16468cf6c252SPaul Traina } 16478cf6c252SPaul Traina } 16488cf6c252SPaul Traina } 16498cf6c252SPaul Traina 16508cf6c252SPaul Traina /* 16518cf6c252SPaul Traina * Mark code array such that isMarked(i) is true 16528cf6c252SPaul Traina * only for nodes that are alive. 16538cf6c252SPaul Traina */ 16548cf6c252SPaul Traina static void 16558cf6c252SPaul Traina mark_code(p) 16568cf6c252SPaul Traina struct block *p; 16578cf6c252SPaul Traina { 16588cf6c252SPaul Traina cur_mark += 1; 16598cf6c252SPaul Traina make_marks(p); 16608cf6c252SPaul Traina } 16618cf6c252SPaul Traina 16628cf6c252SPaul Traina /* 16638cf6c252SPaul Traina * True iff the two stmt lists load the same value from the packet into 16648cf6c252SPaul Traina * the accumulator. 16658cf6c252SPaul Traina */ 16668cf6c252SPaul Traina static int 16678cf6c252SPaul Traina eq_slist(x, y) 16688cf6c252SPaul Traina struct slist *x, *y; 16698cf6c252SPaul Traina { 16708cf6c252SPaul Traina while (1) { 16718cf6c252SPaul Traina while (x && x->s.code == NOP) 16728cf6c252SPaul Traina x = x->next; 16738cf6c252SPaul Traina while (y && y->s.code == NOP) 16748cf6c252SPaul Traina y = y->next; 16758cf6c252SPaul Traina if (x == 0) 16768cf6c252SPaul Traina return y == 0; 16778cf6c252SPaul Traina if (y == 0) 16788cf6c252SPaul Traina return x == 0; 16798cf6c252SPaul Traina if (x->s.code != y->s.code || x->s.k != y->s.k) 16808cf6c252SPaul Traina return 0; 16818cf6c252SPaul Traina x = x->next; 16828cf6c252SPaul Traina y = y->next; 16838cf6c252SPaul Traina } 16848cf6c252SPaul Traina } 16858cf6c252SPaul Traina 16868cf6c252SPaul Traina static inline int 16878cf6c252SPaul Traina eq_blk(b0, b1) 16888cf6c252SPaul Traina struct block *b0, *b1; 16898cf6c252SPaul Traina { 16908cf6c252SPaul Traina if (b0->s.code == b1->s.code && 16918cf6c252SPaul Traina b0->s.k == b1->s.k && 16928cf6c252SPaul Traina b0->et.succ == b1->et.succ && 16938cf6c252SPaul Traina b0->ef.succ == b1->ef.succ) 16948cf6c252SPaul Traina return eq_slist(b0->stmts, b1->stmts); 16958cf6c252SPaul Traina return 0; 16968cf6c252SPaul Traina } 16978cf6c252SPaul Traina 16988cf6c252SPaul Traina static void 16998cf6c252SPaul Traina intern_blocks(root) 17008cf6c252SPaul Traina struct block *root; 17018cf6c252SPaul Traina { 17028cf6c252SPaul Traina struct block *p; 17038cf6c252SPaul Traina int i, j; 17048cf6c252SPaul Traina int done; 17058cf6c252SPaul Traina top: 17068cf6c252SPaul Traina done = 1; 17078cf6c252SPaul Traina for (i = 0; i < n_blocks; ++i) 17088cf6c252SPaul Traina blocks[i]->link = 0; 17098cf6c252SPaul Traina 17108cf6c252SPaul Traina mark_code(root); 17118cf6c252SPaul Traina 17128cf6c252SPaul Traina for (i = n_blocks - 1; --i >= 0; ) { 17138cf6c252SPaul Traina if (!isMarked(blocks[i])) 17148cf6c252SPaul Traina continue; 17158cf6c252SPaul Traina for (j = i + 1; j < n_blocks; ++j) { 17168cf6c252SPaul Traina if (!isMarked(blocks[j])) 17178cf6c252SPaul Traina continue; 17188cf6c252SPaul Traina if (eq_blk(blocks[i], blocks[j])) { 17198cf6c252SPaul Traina blocks[i]->link = blocks[j]->link ? 17208cf6c252SPaul Traina blocks[j]->link : blocks[j]; 17218cf6c252SPaul Traina break; 17228cf6c252SPaul Traina } 17238cf6c252SPaul Traina } 17248cf6c252SPaul Traina } 17258cf6c252SPaul Traina for (i = 0; i < n_blocks; ++i) { 17268cf6c252SPaul Traina p = blocks[i]; 17278cf6c252SPaul Traina if (JT(p) == 0) 17288cf6c252SPaul Traina continue; 17298cf6c252SPaul Traina if (JT(p)->link) { 17308cf6c252SPaul Traina done = 0; 17318cf6c252SPaul Traina JT(p) = JT(p)->link; 17328cf6c252SPaul Traina } 17338cf6c252SPaul Traina if (JF(p)->link) { 17348cf6c252SPaul Traina done = 0; 17358cf6c252SPaul Traina JF(p) = JF(p)->link; 17368cf6c252SPaul Traina } 17378cf6c252SPaul Traina } 17388cf6c252SPaul Traina if (!done) 17398cf6c252SPaul Traina goto top; 17408cf6c252SPaul Traina } 17418cf6c252SPaul Traina 17428cf6c252SPaul Traina static void 17438cf6c252SPaul Traina opt_cleanup() 17448cf6c252SPaul Traina { 17458cf6c252SPaul Traina free((void *)vnode_base); 17468cf6c252SPaul Traina free((void *)vmap); 17478cf6c252SPaul Traina free((void *)edges); 17488cf6c252SPaul Traina free((void *)space); 17498cf6c252SPaul Traina free((void *)levels); 17508cf6c252SPaul Traina free((void *)blocks); 17518cf6c252SPaul Traina } 17528cf6c252SPaul Traina 17538cf6c252SPaul Traina /* 17548cf6c252SPaul Traina * Return the number of stmts in 's'. 17558cf6c252SPaul Traina */ 17568cf6c252SPaul Traina static int 17578cf6c252SPaul Traina slength(s) 17588cf6c252SPaul Traina struct slist *s; 17598cf6c252SPaul Traina { 17608cf6c252SPaul Traina int n = 0; 17618cf6c252SPaul Traina 17628cf6c252SPaul Traina for (; s; s = s->next) 17638cf6c252SPaul Traina if (s->s.code != NOP) 17648cf6c252SPaul Traina ++n; 17658cf6c252SPaul Traina return n; 17668cf6c252SPaul Traina } 17678cf6c252SPaul Traina 17688cf6c252SPaul Traina /* 17698cf6c252SPaul Traina * Return the number of nodes reachable by 'p'. 17708cf6c252SPaul Traina * All nodes should be initially unmarked. 17718cf6c252SPaul Traina */ 17728cf6c252SPaul Traina static int 17738cf6c252SPaul Traina count_blocks(p) 17748cf6c252SPaul Traina struct block *p; 17758cf6c252SPaul Traina { 17768cf6c252SPaul Traina if (p == 0 || isMarked(p)) 17778cf6c252SPaul Traina return 0; 17788cf6c252SPaul Traina Mark(p); 17798cf6c252SPaul Traina return count_blocks(JT(p)) + count_blocks(JF(p)) + 1; 17808cf6c252SPaul Traina } 17818cf6c252SPaul Traina 17828cf6c252SPaul Traina /* 17838cf6c252SPaul Traina * Do a depth first search on the flow graph, numbering the 17848cf6c252SPaul Traina * the basic blocks, and entering them into the 'blocks' array.` 17858cf6c252SPaul Traina */ 17868cf6c252SPaul Traina static void 17878cf6c252SPaul Traina number_blks_r(p) 17888cf6c252SPaul Traina struct block *p; 17898cf6c252SPaul Traina { 17908cf6c252SPaul Traina int n; 17918cf6c252SPaul Traina 17928cf6c252SPaul Traina if (p == 0 || isMarked(p)) 17938cf6c252SPaul Traina return; 17948cf6c252SPaul Traina 17958cf6c252SPaul Traina Mark(p); 17968cf6c252SPaul Traina n = n_blocks++; 17978cf6c252SPaul Traina p->id = n; 17988cf6c252SPaul Traina blocks[n] = p; 17998cf6c252SPaul Traina 18008cf6c252SPaul Traina number_blks_r(JT(p)); 18018cf6c252SPaul Traina number_blks_r(JF(p)); 18028cf6c252SPaul Traina } 18038cf6c252SPaul Traina 18048cf6c252SPaul Traina /* 18058cf6c252SPaul Traina * Return the number of stmts in the flowgraph reachable by 'p'. 18068cf6c252SPaul Traina * The nodes should be unmarked before calling. 1807dc2c7305SBill Fenner * 1808dc2c7305SBill Fenner * Note that "stmts" means "instructions", and that this includes 1809dc2c7305SBill Fenner * 1810dc2c7305SBill Fenner * side-effect statements in 'p' (slength(p->stmts)); 1811dc2c7305SBill Fenner * 1812dc2c7305SBill Fenner * statements in the true branch from 'p' (count_stmts(JT(p))); 1813dc2c7305SBill Fenner * 1814dc2c7305SBill Fenner * statements in the false branch from 'p' (count_stmts(JF(p))); 1815dc2c7305SBill Fenner * 1816dc2c7305SBill Fenner * the conditional jump itself (1); 1817dc2c7305SBill Fenner * 1818dc2c7305SBill Fenner * an extra long jump if the true branch requires it (p->longjt); 1819dc2c7305SBill Fenner * 1820dc2c7305SBill Fenner * an extra long jump if the false branch requires it (p->longjf). 18218cf6c252SPaul Traina */ 18228cf6c252SPaul Traina static int 18238cf6c252SPaul Traina count_stmts(p) 18248cf6c252SPaul Traina struct block *p; 18258cf6c252SPaul Traina { 18268cf6c252SPaul Traina int n; 18278cf6c252SPaul Traina 18288cf6c252SPaul Traina if (p == 0 || isMarked(p)) 18298cf6c252SPaul Traina return 0; 18308cf6c252SPaul Traina Mark(p); 18318cf6c252SPaul Traina n = count_stmts(JT(p)) + count_stmts(JF(p)); 1832dc2c7305SBill Fenner return slength(p->stmts) + n + 1 + p->longjt + p->longjf; 18338cf6c252SPaul Traina } 18348cf6c252SPaul Traina 18358cf6c252SPaul Traina /* 18368cf6c252SPaul Traina * Allocate memory. All allocation is done before optimization 18378cf6c252SPaul Traina * is begun. A linear bound on the size of all data structures is computed 18388cf6c252SPaul Traina * from the total number of blocks and/or statements. 18398cf6c252SPaul Traina */ 18408cf6c252SPaul Traina static void 18418cf6c252SPaul Traina opt_init(root) 18428cf6c252SPaul Traina struct block *root; 18438cf6c252SPaul Traina { 18448cf6c252SPaul Traina bpf_u_int32 *p; 18458cf6c252SPaul Traina int i, n, max_stmts; 18468cf6c252SPaul Traina 18478cf6c252SPaul Traina /* 18488cf6c252SPaul Traina * First, count the blocks, so we can malloc an array to map 18498cf6c252SPaul Traina * block number to block. Then, put the blocks into the array. 18508cf6c252SPaul Traina */ 18518cf6c252SPaul Traina unMarkAll(); 18528cf6c252SPaul Traina n = count_blocks(root); 18538cf6c252SPaul Traina blocks = (struct block **)malloc(n * sizeof(*blocks)); 18548cf6c252SPaul Traina unMarkAll(); 18558cf6c252SPaul Traina n_blocks = 0; 18568cf6c252SPaul Traina number_blks_r(root); 18578cf6c252SPaul Traina 18588cf6c252SPaul Traina n_edges = 2 * n_blocks; 18598cf6c252SPaul Traina edges = (struct edge **)malloc(n_edges * sizeof(*edges)); 18608cf6c252SPaul Traina 18618cf6c252SPaul Traina /* 18628cf6c252SPaul Traina * The number of levels is bounded by the number of nodes. 18638cf6c252SPaul Traina */ 18648cf6c252SPaul Traina levels = (struct block **)malloc(n_blocks * sizeof(*levels)); 18658cf6c252SPaul Traina 18668cf6c252SPaul Traina edgewords = n_edges / (8 * sizeof(bpf_u_int32)) + 1; 18678cf6c252SPaul Traina nodewords = n_blocks / (8 * sizeof(bpf_u_int32)) + 1; 18688cf6c252SPaul Traina 18698cf6c252SPaul Traina /* XXX */ 18708cf6c252SPaul Traina space = (bpf_u_int32 *)malloc(2 * n_blocks * nodewords * sizeof(*space) 18718cf6c252SPaul Traina + n_edges * edgewords * sizeof(*space)); 18728cf6c252SPaul Traina p = space; 18738cf6c252SPaul Traina all_dom_sets = p; 18748cf6c252SPaul Traina for (i = 0; i < n; ++i) { 18758cf6c252SPaul Traina blocks[i]->dom = p; 18768cf6c252SPaul Traina p += nodewords; 18778cf6c252SPaul Traina } 18788cf6c252SPaul Traina all_closure_sets = p; 18798cf6c252SPaul Traina for (i = 0; i < n; ++i) { 18808cf6c252SPaul Traina blocks[i]->closure = p; 18818cf6c252SPaul Traina p += nodewords; 18828cf6c252SPaul Traina } 18838cf6c252SPaul Traina all_edge_sets = p; 18848cf6c252SPaul Traina for (i = 0; i < n; ++i) { 18858cf6c252SPaul Traina register struct block *b = blocks[i]; 18868cf6c252SPaul Traina 18878cf6c252SPaul Traina b->et.edom = p; 18888cf6c252SPaul Traina p += edgewords; 18898cf6c252SPaul Traina b->ef.edom = p; 18908cf6c252SPaul Traina p += edgewords; 18918cf6c252SPaul Traina b->et.id = i; 18928cf6c252SPaul Traina edges[i] = &b->et; 18938cf6c252SPaul Traina b->ef.id = n_blocks + i; 18948cf6c252SPaul Traina edges[n_blocks + i] = &b->ef; 18958cf6c252SPaul Traina b->et.pred = b; 18968cf6c252SPaul Traina b->ef.pred = b; 18978cf6c252SPaul Traina } 18988cf6c252SPaul Traina max_stmts = 0; 18998cf6c252SPaul Traina for (i = 0; i < n; ++i) 19008cf6c252SPaul Traina max_stmts += slength(blocks[i]->stmts) + 1; 19018cf6c252SPaul Traina /* 19028cf6c252SPaul Traina * We allocate at most 3 value numbers per statement, 19038cf6c252SPaul Traina * so this is an upper bound on the number of valnodes 19048cf6c252SPaul Traina * we'll need. 19058cf6c252SPaul Traina */ 19068cf6c252SPaul Traina maxval = 3 * max_stmts; 19078cf6c252SPaul Traina vmap = (struct vmapinfo *)malloc(maxval * sizeof(*vmap)); 1908dc2c7305SBill Fenner vnode_base = (struct valnode *)malloc(maxval * sizeof(*vnode_base)); 19098cf6c252SPaul Traina } 19108cf6c252SPaul Traina 19118cf6c252SPaul Traina /* 19128cf6c252SPaul Traina * Some pointers used to convert the basic block form of the code, 19138cf6c252SPaul Traina * into the array form that BPF requires. 'fstart' will point to 19148cf6c252SPaul Traina * the malloc'd array while 'ftail' is used during the recursive traversal. 19158cf6c252SPaul Traina */ 19168cf6c252SPaul Traina static struct bpf_insn *fstart; 19178cf6c252SPaul Traina static struct bpf_insn *ftail; 19188cf6c252SPaul Traina 19198cf6c252SPaul Traina #ifdef BDEBUG 19208cf6c252SPaul Traina int bids[1000]; 19218cf6c252SPaul Traina #endif 19228cf6c252SPaul Traina 19238cf6c252SPaul Traina /* 19248cf6c252SPaul Traina * Returns true if successful. Returns false if a branch has 19258cf6c252SPaul Traina * an offset that is too large. If so, we have marked that 19268cf6c252SPaul Traina * branch so that on a subsequent iteration, it will be treated 19278cf6c252SPaul Traina * properly. 19288cf6c252SPaul Traina */ 19298cf6c252SPaul Traina static int 19308cf6c252SPaul Traina convert_code_r(p) 19318cf6c252SPaul Traina struct block *p; 19328cf6c252SPaul Traina { 19338cf6c252SPaul Traina struct bpf_insn *dst; 19348cf6c252SPaul Traina struct slist *src; 19358cf6c252SPaul Traina int slen; 19368cf6c252SPaul Traina u_int off; 19378cf6c252SPaul Traina int extrajmps; /* number of extra jumps inserted */ 19388751327cSBill Fenner struct slist **offset = NULL; 19398cf6c252SPaul Traina 19408cf6c252SPaul Traina if (p == 0 || isMarked(p)) 19418cf6c252SPaul Traina return (1); 19428cf6c252SPaul Traina Mark(p); 19438cf6c252SPaul Traina 19448cf6c252SPaul Traina if (convert_code_r(JF(p)) == 0) 19458cf6c252SPaul Traina return (0); 19468cf6c252SPaul Traina if (convert_code_r(JT(p)) == 0) 19478cf6c252SPaul Traina return (0); 19488cf6c252SPaul Traina 19498cf6c252SPaul Traina slen = slength(p->stmts); 19508cf6c252SPaul Traina dst = ftail -= (slen + 1 + p->longjt + p->longjf); 19518cf6c252SPaul Traina /* inflate length by any extra jumps */ 19528cf6c252SPaul Traina 19538cf6c252SPaul Traina p->offset = dst - fstart; 19548cf6c252SPaul Traina 19558751327cSBill Fenner /* generate offset[] for convenience */ 19568751327cSBill Fenner if (slen) { 19578751327cSBill Fenner offset = (struct slist **)calloc(sizeof(struct slist *), slen); 19588751327cSBill Fenner if (!offset) { 19598751327cSBill Fenner bpf_error("not enough core"); 19608751327cSBill Fenner /*NOTREACHED*/ 19618751327cSBill Fenner } 19628751327cSBill Fenner } 19638751327cSBill Fenner src = p->stmts; 19648751327cSBill Fenner for (off = 0; off < slen && src; off++) { 19658751327cSBill Fenner #if 0 19668751327cSBill Fenner printf("off=%d src=%x\n", off, src); 19678751327cSBill Fenner #endif 19688751327cSBill Fenner offset[off] = src; 19698751327cSBill Fenner src = src->next; 19708751327cSBill Fenner } 19718751327cSBill Fenner 19728751327cSBill Fenner off = 0; 19738cf6c252SPaul Traina for (src = p->stmts; src; src = src->next) { 19748cf6c252SPaul Traina if (src->s.code == NOP) 19758cf6c252SPaul Traina continue; 19768cf6c252SPaul Traina dst->code = (u_short)src->s.code; 19778cf6c252SPaul Traina dst->k = src->s.k; 19788751327cSBill Fenner 19798751327cSBill Fenner /* fill block-local relative jump */ 1980dc2c7305SBill Fenner if (BPF_CLASS(src->s.code) != BPF_JMP || src->s.code == (BPF_JMP|BPF_JA)) { 19818751327cSBill Fenner #if 0 19828751327cSBill Fenner if (src->s.jt || src->s.jf) { 19838751327cSBill Fenner bpf_error("illegal jmp destination"); 19848751327cSBill Fenner /*NOTREACHED*/ 19858cf6c252SPaul Traina } 19868751327cSBill Fenner #endif 19878751327cSBill Fenner goto filled; 19888751327cSBill Fenner } 19898751327cSBill Fenner if (off == slen - 2) /*???*/ 19908751327cSBill Fenner goto filled; 19918751327cSBill Fenner 19928751327cSBill Fenner { 19938751327cSBill Fenner int i; 19948751327cSBill Fenner int jt, jf; 19958751327cSBill Fenner char *ljerr = "%s for block-local relative jump: off=%d"; 19968751327cSBill Fenner 19978751327cSBill Fenner #if 0 19988751327cSBill Fenner printf("code=%x off=%d %x %x\n", src->s.code, 19998751327cSBill Fenner off, src->s.jt, src->s.jf); 20008751327cSBill Fenner #endif 20018751327cSBill Fenner 20028751327cSBill Fenner if (!src->s.jt || !src->s.jf) { 20038751327cSBill Fenner bpf_error(ljerr, "no jmp destination", off); 20048751327cSBill Fenner /*NOTREACHED*/ 20058751327cSBill Fenner } 20068751327cSBill Fenner 20078751327cSBill Fenner jt = jf = 0; 20088751327cSBill Fenner for (i = 0; i < slen; i++) { 20098751327cSBill Fenner if (offset[i] == src->s.jt) { 20108751327cSBill Fenner if (jt) { 20118751327cSBill Fenner bpf_error(ljerr, "multiple matches", off); 20128751327cSBill Fenner /*NOTREACHED*/ 20138751327cSBill Fenner } 20148751327cSBill Fenner 20158751327cSBill Fenner dst->jt = i - off - 1; 20168751327cSBill Fenner jt++; 20178751327cSBill Fenner } 20188751327cSBill Fenner if (offset[i] == src->s.jf) { 20198751327cSBill Fenner if (jf) { 20208751327cSBill Fenner bpf_error(ljerr, "multiple matches", off); 20218751327cSBill Fenner /*NOTREACHED*/ 20228751327cSBill Fenner } 20238751327cSBill Fenner dst->jf = i - off - 1; 20248751327cSBill Fenner jf++; 20258751327cSBill Fenner } 20268751327cSBill Fenner } 20278751327cSBill Fenner if (!jt || !jf) { 20288751327cSBill Fenner bpf_error(ljerr, "no destination found", off); 20298751327cSBill Fenner /*NOTREACHED*/ 20308751327cSBill Fenner } 20318751327cSBill Fenner } 20328751327cSBill Fenner filled: 20338751327cSBill Fenner ++dst; 20348751327cSBill Fenner ++off; 20358751327cSBill Fenner } 20368751327cSBill Fenner if (offset) 20378751327cSBill Fenner free(offset); 20388751327cSBill Fenner 20398cf6c252SPaul Traina #ifdef BDEBUG 20408cf6c252SPaul Traina bids[dst - fstart] = p->id + 1; 20418cf6c252SPaul Traina #endif 20428cf6c252SPaul Traina dst->code = (u_short)p->s.code; 20438cf6c252SPaul Traina dst->k = p->s.k; 20448cf6c252SPaul Traina if (JT(p)) { 20458cf6c252SPaul Traina extrajmps = 0; 20468cf6c252SPaul Traina off = JT(p)->offset - (p->offset + slen) - 1; 20478cf6c252SPaul Traina if (off >= 256) { 20488cf6c252SPaul Traina /* offset too large for branch, must add a jump */ 20498cf6c252SPaul Traina if (p->longjt == 0) { 20508cf6c252SPaul Traina /* mark this instruction and retry */ 20518cf6c252SPaul Traina p->longjt++; 20528cf6c252SPaul Traina return(0); 20538cf6c252SPaul Traina } 20548cf6c252SPaul Traina /* branch if T to following jump */ 20558cf6c252SPaul Traina dst->jt = extrajmps; 20568cf6c252SPaul Traina extrajmps++; 20578cf6c252SPaul Traina dst[extrajmps].code = BPF_JMP|BPF_JA; 20588cf6c252SPaul Traina dst[extrajmps].k = off - extrajmps; 20598cf6c252SPaul Traina } 20608cf6c252SPaul Traina else 20618cf6c252SPaul Traina dst->jt = off; 20628cf6c252SPaul Traina off = JF(p)->offset - (p->offset + slen) - 1; 20638cf6c252SPaul Traina if (off >= 256) { 20648cf6c252SPaul Traina /* offset too large for branch, must add a jump */ 20658cf6c252SPaul Traina if (p->longjf == 0) { 20668cf6c252SPaul Traina /* mark this instruction and retry */ 20678cf6c252SPaul Traina p->longjf++; 20688cf6c252SPaul Traina return(0); 20698cf6c252SPaul Traina } 20708cf6c252SPaul Traina /* branch if F to following jump */ 20718cf6c252SPaul Traina /* if two jumps are inserted, F goes to second one */ 20728cf6c252SPaul Traina dst->jf = extrajmps; 20738cf6c252SPaul Traina extrajmps++; 20748cf6c252SPaul Traina dst[extrajmps].code = BPF_JMP|BPF_JA; 20758cf6c252SPaul Traina dst[extrajmps].k = off - extrajmps; 20768cf6c252SPaul Traina } 20778cf6c252SPaul Traina else 20788cf6c252SPaul Traina dst->jf = off; 20798cf6c252SPaul Traina } 20808cf6c252SPaul Traina return (1); 20818cf6c252SPaul Traina } 20828cf6c252SPaul Traina 20838cf6c252SPaul Traina 20848cf6c252SPaul Traina /* 20858cf6c252SPaul Traina * Convert flowgraph intermediate representation to the 20868cf6c252SPaul Traina * BPF array representation. Set *lenp to the number of instructions. 20878cf6c252SPaul Traina */ 20888cf6c252SPaul Traina struct bpf_insn * 20898cf6c252SPaul Traina icode_to_fcode(root, lenp) 20908cf6c252SPaul Traina struct block *root; 20918cf6c252SPaul Traina int *lenp; 20928cf6c252SPaul Traina { 20938cf6c252SPaul Traina int n; 20948cf6c252SPaul Traina struct bpf_insn *fp; 20958cf6c252SPaul Traina 20968cf6c252SPaul Traina /* 20970a94d38fSBill Fenner * Loop doing convert_code_r() until no branches remain 20988cf6c252SPaul Traina * with too-large offsets. 20998cf6c252SPaul Traina */ 21008cf6c252SPaul Traina while (1) { 21018cf6c252SPaul Traina unMarkAll(); 21028cf6c252SPaul Traina n = *lenp = count_stmts(root); 21038cf6c252SPaul Traina 21048cf6c252SPaul Traina fp = (struct bpf_insn *)malloc(sizeof(*fp) * n); 21058cf6c252SPaul Traina memset((char *)fp, 0, sizeof(*fp) * n); 21068cf6c252SPaul Traina fstart = fp; 21078cf6c252SPaul Traina ftail = fp + n; 21088cf6c252SPaul Traina 21098cf6c252SPaul Traina unMarkAll(); 21108cf6c252SPaul Traina if (convert_code_r(root)) 21118cf6c252SPaul Traina break; 21128cf6c252SPaul Traina free(fp); 21138cf6c252SPaul Traina } 21148cf6c252SPaul Traina 21158cf6c252SPaul Traina return fp; 21168cf6c252SPaul Traina } 21178cf6c252SPaul Traina 2118dc2c7305SBill Fenner /* 2119dc2c7305SBill Fenner * Make a copy of a BPF program and put it in the "fcode" member of 2120dc2c7305SBill Fenner * a "pcap_t". 2121dc2c7305SBill Fenner * 2122dc2c7305SBill Fenner * If we fail to allocate memory for the copy, fill in the "errbuf" 2123dc2c7305SBill Fenner * member of the "pcap_t" with an error message, and return -1; 2124dc2c7305SBill Fenner * otherwise, return 0. 2125dc2c7305SBill Fenner */ 2126dc2c7305SBill Fenner int 2127dc2c7305SBill Fenner install_bpf_program(pcap_t *p, struct bpf_program *fp) 2128dc2c7305SBill Fenner { 2129dc2c7305SBill Fenner size_t prog_size; 2130dc2c7305SBill Fenner 2131dc2c7305SBill Fenner /* 2132dc2c7305SBill Fenner * Free up any already installed program. 2133dc2c7305SBill Fenner */ 2134dc2c7305SBill Fenner pcap_freecode(&p->fcode); 2135dc2c7305SBill Fenner 2136dc2c7305SBill Fenner prog_size = sizeof(*fp->bf_insns) * fp->bf_len; 2137dc2c7305SBill Fenner p->fcode.bf_len = fp->bf_len; 2138dc2c7305SBill Fenner p->fcode.bf_insns = (struct bpf_insn *)malloc(prog_size); 2139dc2c7305SBill Fenner if (p->fcode.bf_insns == NULL) { 2140dc2c7305SBill Fenner snprintf(p->errbuf, sizeof(p->errbuf), 2141dc2c7305SBill Fenner "malloc: %s", pcap_strerror(errno)); 2142dc2c7305SBill Fenner return (-1); 2143dc2c7305SBill Fenner } 2144dc2c7305SBill Fenner memcpy(p->fcode.bf_insns, fp->bf_insns, prog_size); 2145dc2c7305SBill Fenner return (0); 2146dc2c7305SBill Fenner } 2147dc2c7305SBill Fenner 21488cf6c252SPaul Traina #ifdef BDEBUG 21498cf6c252SPaul Traina static void 21508cf6c252SPaul Traina opt_dump(root) 21518cf6c252SPaul Traina struct block *root; 21528cf6c252SPaul Traina { 21538cf6c252SPaul Traina struct bpf_program f; 21548cf6c252SPaul Traina 21558cf6c252SPaul Traina memset(bids, 0, sizeof bids); 21568cf6c252SPaul Traina f.bf_insns = icode_to_fcode(root, &f.bf_len); 21578cf6c252SPaul Traina bpf_dump(&f, 1); 21588cf6c252SPaul Traina putchar('\n'); 21598cf6c252SPaul Traina free((char *)f.bf_insns); 21608cf6c252SPaul Traina } 21618cf6c252SPaul Traina #endif 2162