ops.rar_ops

/* * * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that: (1) source code distributions * retain the above copyright notice and this paragraph in its entirety, (2) * distributions including binary code include the above copyright notice and * this paragraph in its entirety in the documentation or other materials * provided with the distribution, and (3) all advertising materials mentioning * features or use of this software display the following acknowledgement: * ``This product includes software developed by the University of California, * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of * the University nor the names of its contributors may be used to endorse * or promote products derived from this software without specific prior * written permission. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. * * Optimization module for tcpdump intermediate representation. */ #ifndef lint static const char rcsid[] _U_ = "@(#) $Header: /tcpdump/master/libpcap/optimize.c,v 1.85.2.3 2007/09/12 21:29:45 guy Exp $ (LBL)"; #endif #ifdef HAVE_CONFIG_H #include "config.h" #endif #include <stdio.h> #include <stdlib.h> #include <memory.h> #include <string.h> #include <errno.h> #include "pcap-int.h" #include "gencode.h" #ifdef HAVE_OS_PROTO_H #include "os-proto.h" #endif #ifdef BDEBUG extern int dflag; #endif #if defined(MSDOS) && !defined(__DJGPP__) extern int _w32_ffs (int mask); #define ffs _w32_ffs #endif /* * Represents a deleted instruction. */ #define NOP -1 /* * Register numbers for use-def values. * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory * location. A_ATOM is the accumulator and X_ATOM is the index * register. */ #define A_ATOM BPF_MEMWORDS #define X_ATOM (BPF_MEMWORDS+1) /* * This define is used to represent *both* the accumulator and * x register in use-def computations. * Currently, the use-def code assumes only one definition per instruction. */ #define AX_ATOM N_ATOMS /* * A flag to indicate that further optimization is needed. * Iterative passes are continued until a given pass yields no * branch movement. */ static int done; /* * A block is marked if only if its mark equals the current mark. * Rather than traverse the code array, marking each item, 'cur_mark' is * incremented. This automatically makes each element unmarked. */ static int cur_mark; #define isMarked(p) ((p)->mark == cur_mark) #define unMarkAll() cur_mark += 1 #define Mark(p) ((p)->mark = cur_mark) static void opt_init(struct block *); static void opt_cleanup(void); static void make_marks(struct block *); static void mark_code(struct block *); static void intern_blocks(struct block *); static int eq_slist(struct slist *, struct slist *); static void find_levels_r(struct block *); static void find_levels(struct block *); static void find_dom(struct block *); static void propedom(struct edge *); static void find_edom(struct block *); static void find_closure(struct block *); static int atomuse(struct stmt *); static int atomdef(struct stmt *); static void compute_local_ud(struct block *); static void find_ud(struct block *); static void init_val(void); static int F(int, int, int); static inline void vstore(struct stmt *, int *, int, int); static void opt_blk(struct block *, int); static int use_conflict(struct block *, struct block *); static void opt_j(struct edge *); static void or_pullup(struct block *); static void and_pullup(struct block *); static void opt_blks(struct block *, int); static inline void link_inedge(struct edge *, struct block *); static void find_inedges(struct block *); static void opt_root(struct block **); static void opt_loop(struct block *, int); static void fold_op(struct stmt *, int, int); static inline struct slist *this_op(struct slist *); static void opt_not(struct block *); static void opt_peep(struct block *); static void opt_stmt(struct stmt *, int[], int); static void deadstmt(struct stmt *, struct stmt *[]); static void opt_deadstores(struct block *); static struct block *fold_edge(struct block *, struct edge *); static inline int eq_blk(struct block *, struct block *); static int slength(struct slist *); static int count_blocks(struct block *); static void number_blks_r(struct block *); static int count_stmts(struct block *); static int convert_code_r(struct block *); #ifdef BDEBUG static void opt_dump(struct block *); #endif static int n_blocks; struct block **blocks; static int n_edges; struct edge **edges; /* * A bit vector set representation of the dominators. * We round up the set size to the next power of two. */ static int nodewords; static int edgewords; struct block **levels; bpf_u_int32 *space; #define BITS_PER_WORD (8*sizeof(bpf_u_int32)) /* * True if a is in uset {p} */ #define SET_MEMBER(p, a) \ ((p)[(unsigned)(a) / BITS_PER_WORD] & (1 << ((unsigned)(a) % BITS_PER_WORD))) /* * Add 'a' to uset p. */ #define SET_INSERT(p, a) \ (p)[(unsigned)(a) / BITS_PER_WORD] |= (1 << ((unsigned)(a) % BITS_PER_WORD)) /* * Delete 'a' from uset p. */ #define SET_DELETE(p, a) \ (p)[(unsigned)(a) / BITS_PER_WORD] &= ~(1 << ((unsigned)(a) % BITS_PER_WORD)) /* * a := a intersect b */ #define SET_INTERSECT(a, b, n)\ {\ register bpf_u_int32 *_x = a, *_y = b;\ register int _n = n;\ while (--_n >= 0) *_x++ &= *_y++;\ } /* * a := a - b */ #define SET_SUBTRACT(a, b, n)\ {\ register bpf_u_int32 *_x = a, *_y = b;\ register int _n = n;\ while (--_n >= 0) *_x++ &=~ *_y++;\ } /* * a := a union b */ #define SET_UNION(a, b, n)\ {\ register bpf_u_int32 *_x = a, *_y = b;\ register int _n = n;\ while (--_n >= 0) *_x++ |= *_y++;\ } static uset all_dom_sets; static uset all_closure_sets; static uset all_edge_sets; #ifndef MAX #define MAX(a,b) ((a)>(b)?(a):(b)) #endif static void find_levels_r(b) struct block *b; { int level; if (isMarked(b)) return; Mark(b); b->link = 0; if (JT(b)) { find_levels_r(JT(b)); find_levels_r(JF(b)); level = MAX(JT(b)->level, JF(b)->level) + 1; } else level = 0; b->level = level; b->link = levels[level]; levels[level] = b; } /* * Level graph. The levels go from 0 at the leaves to * N_LEVELS at the root. The levels[] array points to the * first node of the level list, whose elements are linked * with the 'link' field of the struct block. */ static void find_levels(root) struct block *root; { memset((char *)levels, 0, n_blocks * sizeof(*levels)); unMarkAll(); find_levels_r(root); } /* * Find dominator relationships. * Assumes graph has been leveled. */ static void find_dom(root) struct block *root; { int i; struct block *b; bpf_u_int32 *x; /* * Initialize sets to contain all nodes. */ x = all_dom_sets; i = n_blocks * nodewords; while (--i >= 0) *x++ = ~0; /* Root starts off empty. */ for (i = nodewords; --i >= 0;) root->dom[i] = 0; /* root->level is the highest level no found. */ for (i = root->level; i >= 0; --i) { for (b = levels[i]; b; b = b->link) { SET_INSERT(b->dom, b->id); if (JT(b) == 0) continue; SET_INTERSECT(JT(b)->dom, b->dom, nodewords); SET_INTERSECT(JF(b)->dom, b->dom, nodewords); } } } static void propedom(ep) struct edge *ep; { SET_INSERT(ep->edom, ep->id); if (ep->succ) { SET_INTERSECT(ep->succ->et.edom, ep->edom, edgewords); SET_INTERSECT(ep->succ->ef.edom, ep->edom, edgewords); } } /* * Compute edge dominators. * Assumes graph has been leveled and predecessors established. */ static void find_edom(root) struct block *root; { int i; uset x; struct block *b; x = all_edge_sets; for (i = n_edges * edgewords; --i >= 0; ) x[i] = ~0; /* root->level is the highest level no found. */ memset(root->et.edom, 0, edgewords * sizeof(*(uset)0)); memset(root->ef.edom, 0, edgewords * size