/*
*
*
* 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
