1478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 2478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Copyright (c) 1988, 1989, 1990, 1991, 1993, 1994, 1995, 1996 3478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * The Regents of the University of California. All rights reserved. 4478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 5478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Redistribution and use in source and binary forms, with or without 6478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * modification, are permitted provided that: (1) source code distributions 7478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * retain the above copyright notice and this paragraph in its entirety, (2) 8478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * distributions including binary code include the above copyright notice and 9478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * this paragraph in its entirety in the documentation or other materials 10478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * provided with the distribution, and (3) all advertising materials mentioning 11478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * features or use of this software display the following acknowledgement: 12478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * ``This product includes software developed by the University of California, 13478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of 14478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * the University nor the names of its contributors may be used to endorse 15478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * or promote products derived from this software without specific prior 16478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * written permission. 17478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 18478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 19478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 20478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 21478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Optimization module for tcpdump intermediate representation. 22478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 23478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifndef lint 24478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic const char rcsid[] _U_ = 25511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall "@(#) $Header: /tcpdump/master/libpcap/optimize.c,v 1.91 2008-01-02 04:16:46 guy Exp $ (LBL)"; 26478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 27478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 28478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef HAVE_CONFIG_H 29478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#include "config.h" 30478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 31478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 32511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#ifdef WIN32 33511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#include <pcap-stdinc.h> 34511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#else /* WIN32 */ 35511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#if HAVE_INTTYPES_H 36511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#include <inttypes.h> 37511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#elif HAVE_STDINT_H 38511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#include <stdint.h> 39511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#endif 40511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#ifdef HAVE_SYS_BITYPES_H 41511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#include <sys/bitypes.h> 42511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#endif 43511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#include <sys/types.h> 44511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#endif /* WIN32 */ 45511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall 46478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#include <stdio.h> 47478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#include <stdlib.h> 48478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#include <memory.h> 49478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#include <string.h> 50478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 51478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#include <errno.h> 52478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 53478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#include "pcap-int.h" 54478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 55478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#include "gencode.h" 56478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 57478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef HAVE_OS_PROTO_H 58478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#include "os-proto.h" 59478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 60478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 61478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef BDEBUG 62478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectextern int dflag; 63478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 64478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 65478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#if defined(MSDOS) && !defined(__DJGPP__) 66478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectextern int _w32_ffs (int mask); 67478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define ffs _w32_ffs 68478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 69478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 70511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#if defined(WIN32) && defined (_MSC_VER) 71511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallint ffs(int mask); 72511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall#endif 73511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall 74478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 75478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Represents a deleted instruction. 76478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 77478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define NOP -1 78478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 79478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 80478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Register numbers for use-def values. 81478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory 82478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * location. A_ATOM is the accumulator and X_ATOM is the index 83478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * register. 84478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 85478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define A_ATOM BPF_MEMWORDS 86478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define X_ATOM (BPF_MEMWORDS+1) 87478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 88478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 89478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * This define is used to represent *both* the accumulator and 90478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * x register in use-def computations. 91478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Currently, the use-def code assumes only one definition per instruction. 92478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 93478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define AX_ATOM N_ATOMS 94478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 95478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 96478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * A flag to indicate that further optimization is needed. 97478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Iterative passes are continued until a given pass yields no 98478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * branch movement. 99478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 100478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int done; 101478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 102478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 103478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * A block is marked if only if its mark equals the current mark. 104478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Rather than traverse the code array, marking each item, 'cur_mark' is 105478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * incremented. This automatically makes each element unmarked. 106478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 107478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int cur_mark; 108478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define isMarked(p) ((p)->mark == cur_mark) 109478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define unMarkAll() cur_mark += 1 110478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define Mark(p) ((p)->mark = cur_mark) 111478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 112478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void opt_init(struct block *); 113478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void opt_cleanup(void); 114478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 115478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void intern_blocks(struct block *); 116478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 117478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void find_inedges(struct block *); 118478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef BDEBUG 119478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void opt_dump(struct block *); 120478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 121478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 122478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int n_blocks; 123478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstruct block **blocks; 124478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int n_edges; 125478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstruct edge **edges; 126478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 127478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 128478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * A bit vector set representation of the dominators. 129478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * We round up the set size to the next power of two. 130478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 131478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int nodewords; 132478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int edgewords; 133478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstruct block **levels; 134478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectbpf_u_int32 *space; 135478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define BITS_PER_WORD (8*sizeof(bpf_u_int32)) 136478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 137478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * True if a is in uset {p} 138478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 139478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define SET_MEMBER(p, a) \ 140478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project((p)[(unsigned)(a) / BITS_PER_WORD] & (1 << ((unsigned)(a) % BITS_PER_WORD))) 141478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 142478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 143478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Add 'a' to uset p. 144478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 145478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define SET_INSERT(p, a) \ 146478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project(p)[(unsigned)(a) / BITS_PER_WORD] |= (1 << ((unsigned)(a) % BITS_PER_WORD)) 147478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 148478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 149478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Delete 'a' from uset p. 150478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 151478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define SET_DELETE(p, a) \ 152478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project(p)[(unsigned)(a) / BITS_PER_WORD] &= ~(1 << ((unsigned)(a) % BITS_PER_WORD)) 153478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 154478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 155478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * a := a intersect b 156478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 157478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define SET_INTERSECT(a, b, n)\ 158478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{\ 159478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register bpf_u_int32 *_x = a, *_y = b;\ 160478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register int _n = n;\ 161478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (--_n >= 0) *_x++ &= *_y++;\ 162478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 163478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 164478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 165478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * a := a - b 166478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 167478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define SET_SUBTRACT(a, b, n)\ 168478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{\ 169478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register bpf_u_int32 *_x = a, *_y = b;\ 170478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register int _n = n;\ 171478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (--_n >= 0) *_x++ &=~ *_y++;\ 172478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 173478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 174478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 175478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * a := a union b 176478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 177478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define SET_UNION(a, b, n)\ 178478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{\ 179478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register bpf_u_int32 *_x = a, *_y = b;\ 180478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register int _n = n;\ 181478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (--_n >= 0) *_x++ |= *_y++;\ 182478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 183478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 184478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic uset all_dom_sets; 185478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic uset all_closure_sets; 186478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic uset all_edge_sets; 187478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 188478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifndef MAX 189478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define MAX(a,b) ((a)>(b)?(a):(b)) 190478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 191478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 192478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 193511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallfind_levels_r(struct block *b) 194478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 195478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int level; 196478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 197478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (isMarked(b)) 198478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 199478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 200478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project Mark(b); 201478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->link = 0; 202478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 203478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(b)) { 204478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project find_levels_r(JT(b)); 205478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project find_levels_r(JF(b)); 206478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project level = MAX(JT(b)->level, JF(b)->level) + 1; 207478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } else 208478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project level = 0; 209478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->level = level; 210478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->link = levels[level]; 211478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project levels[level] = b; 212478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 213478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 214478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 215478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Level graph. The levels go from 0 at the leaves to 216478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * N_LEVELS at the root. The levels[] array points to the 217478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * first node of the level list, whose elements are linked 218478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * with the 'link' field of the struct block. 219478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 220478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 221511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallfind_levels(struct block *root) 222478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 223478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memset((char *)levels, 0, n_blocks * sizeof(*levels)); 224478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project unMarkAll(); 225478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project find_levels_r(root); 226478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 227478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 228478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 229478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Find dominator relationships. 230478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Assumes graph has been leveled. 231478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 232478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 233511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallfind_dom(struct block *root) 234478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 235478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int i; 236478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block *b; 237478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_u_int32 *x; 238478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 239478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 240478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Initialize sets to contain all nodes. 241478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 242478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project x = all_dom_sets; 243478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project i = n_blocks * nodewords; 244478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (--i >= 0) 245478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project *x++ = ~0; 246478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* Root starts off empty. */ 247478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = nodewords; --i >= 0;) 248478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project root->dom[i] = 0; 249478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 250478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* root->level is the highest level no found. */ 251478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = root->level; i >= 0; --i) { 252478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (b = levels[i]; b; b = b->link) { 253478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project SET_INSERT(b->dom, b->id); 254478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(b) == 0) 255478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project continue; 256478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project SET_INTERSECT(JT(b)->dom, b->dom, nodewords); 257478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project SET_INTERSECT(JF(b)->dom, b->dom, nodewords); 258478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 259478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 260478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 261478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 262478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 263511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallpropedom(struct edge *ep) 264478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 265478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project SET_INSERT(ep->edom, ep->id); 266478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (ep->succ) { 267478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project SET_INTERSECT(ep->succ->et.edom, ep->edom, edgewords); 268478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project SET_INTERSECT(ep->succ->ef.edom, ep->edom, edgewords); 269478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 270478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 271478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 272478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 273478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Compute edge dominators. 274478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Assumes graph has been leveled and predecessors established. 275478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 276478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 277511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallfind_edom(struct block *root) 278478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 279478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int i; 280478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project uset x; 281478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block *b; 282478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 283478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project x = all_edge_sets; 284478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = n_edges * edgewords; --i >= 0; ) 285478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project x[i] = ~0; 286478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 287478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* root->level is the highest level no found. */ 288478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memset(root->et.edom, 0, edgewords * sizeof(*(uset)0)); 289478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memset(root->ef.edom, 0, edgewords * sizeof(*(uset)0)); 290478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = root->level; i >= 0; --i) { 291478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (b = levels[i]; b != 0; b = b->link) { 292478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project propedom(&b->et); 293478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project propedom(&b->ef); 294478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 295478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 296478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 297478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 298478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 299478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Find the backwards transitive closure of the flow graph. These sets 300478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * are backwards in the sense that we find the set of nodes that reach 301478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * a given node, not the set of nodes that can be reached by a node. 302478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 303478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Assumes graph has been leveled. 304478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 305478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 306511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallfind_closure(struct block *root) 307478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 308478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int i; 309478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block *b; 310478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 311478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 312478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Initialize sets to contain no nodes. 313478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 314478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memset((char *)all_closure_sets, 0, 315478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project n_blocks * nodewords * sizeof(*all_closure_sets)); 316478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 317478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* root->level is the highest level no found. */ 318478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = root->level; i >= 0; --i) { 319478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (b = levels[i]; b; b = b->link) { 320478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project SET_INSERT(b->closure, b->id); 321478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(b) == 0) 322478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project continue; 323478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project SET_UNION(JT(b)->closure, b->closure, nodewords); 324478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project SET_UNION(JF(b)->closure, b->closure, nodewords); 325478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 326478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 327478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 328478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 329478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 330478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Return the register number that is used by s. If A and X are both 331478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * used, return AX_ATOM. If no register is used, return -1. 332478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 333478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * The implementation should probably change to an array access. 334478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 335478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int 336511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallatomuse(struct stmt *s) 337478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 338478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register int c = s->code; 339478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 340478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (c == NOP) 341478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return -1; 342478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 343478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project switch (BPF_CLASS(c)) { 344478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 345478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_RET: 346478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return (BPF_RVAL(c) == BPF_A) ? A_ATOM : 347478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project (BPF_RVAL(c) == BPF_X) ? X_ATOM : -1; 348478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 349478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LD: 350478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LDX: 351478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return (BPF_MODE(c) == BPF_IND) ? X_ATOM : 352478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project (BPF_MODE(c) == BPF_MEM) ? s->k : -1; 353478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 354478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ST: 355478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return A_ATOM; 356478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 357478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_STX: 358478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return X_ATOM; 359478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 360478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_JMP: 361478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU: 362478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (BPF_SRC(c) == BPF_X) 363478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return AX_ATOM; 364478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return A_ATOM; 365478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 366478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_MISC: 367478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return BPF_MISCOP(c) == BPF_TXA ? X_ATOM : A_ATOM; 368478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 369478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project abort(); 370478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* NOTREACHED */ 371478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 372478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 373478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 374478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Return the register number that is defined by 's'. We assume that 375478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * a single stmt cannot define more than one register. If no register 376478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * is defined, return -1. 377478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 378478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * The implementation should probably change to an array access. 379478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 380478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int 381511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallatomdef(struct stmt *s) 382478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 383478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (s->code == NOP) 384478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return -1; 385478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 386478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project switch (BPF_CLASS(s->code)) { 387478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 388478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LD: 389478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU: 390478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return A_ATOM; 391478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 392478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LDX: 393478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return X_ATOM; 394478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 395478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ST: 396478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_STX: 397478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return s->k; 398478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 399478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_MISC: 400478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return BPF_MISCOP(s->code) == BPF_TAX ? X_ATOM : A_ATOM; 401478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 402478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return -1; 403478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 404478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 405478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 406478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Compute the sets of registers used, defined, and killed by 'b'. 407478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 408478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * "Used" means that a statement in 'b' uses the register before any 409478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * statement in 'b' defines it, i.e. it uses the value left in 410478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * that register by a predecessor block of this block. 411478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * "Defined" means that a statement in 'b' defines it. 412478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * "Killed" means that a statement in 'b' defines it before any 413478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * statement in 'b' uses it, i.e. it kills the value left in that 414478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * register by a predecessor block of this block. 415478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 416478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 417511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallcompute_local_ud(struct block *b) 418478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 419478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct slist *s; 420478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project atomset def = 0, use = 0, kill = 0; 421478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int atom; 422478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 423478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (s = b->stmts; s; s = s->next) { 424478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (s->s.code == NOP) 425478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project continue; 426478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project atom = atomuse(&s->s); 427478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (atom >= 0) { 428478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (atom == AX_ATOM) { 429478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!ATOMELEM(def, X_ATOM)) 430478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project use |= ATOMMASK(X_ATOM); 431478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!ATOMELEM(def, A_ATOM)) 432478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project use |= ATOMMASK(A_ATOM); 433478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 434478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else if (atom < N_ATOMS) { 435478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!ATOMELEM(def, atom)) 436478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project use |= ATOMMASK(atom); 437478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 438478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 439478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project abort(); 440478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 441478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project atom = atomdef(&s->s); 442478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (atom >= 0) { 443478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!ATOMELEM(use, atom)) 444478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project kill |= ATOMMASK(atom); 445478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project def |= ATOMMASK(atom); 446478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 447478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 448478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (BPF_CLASS(b->s.code) == BPF_JMP) { 449478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 450478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * XXX - what about RET? 451478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 452478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project atom = atomuse(&b->s); 453478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (atom >= 0) { 454478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (atom == AX_ATOM) { 455478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!ATOMELEM(def, X_ATOM)) 456478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project use |= ATOMMASK(X_ATOM); 457478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!ATOMELEM(def, A_ATOM)) 458478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project use |= ATOMMASK(A_ATOM); 459478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 460478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else if (atom < N_ATOMS) { 461478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!ATOMELEM(def, atom)) 462478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project use |= ATOMMASK(atom); 463478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 464478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 465478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project abort(); 466478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 467478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 468478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 469478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->def = def; 470478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->kill = kill; 471478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->in_use = use; 472478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 473478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 474478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 475478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Assume graph is already leveled. 476478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 477478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 478511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallfind_ud(struct block *root) 479478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 480478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int i, maxlevel; 481478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block *p; 482478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 483478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 484478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * root->level is the highest level no found; 485478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * count down from there. 486478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 487478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project maxlevel = root->level; 488478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = maxlevel; i >= 0; --i) 489478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (p = levels[i]; p; p = p->link) { 490478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project compute_local_ud(p); 491478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->out_use = 0; 492478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 493478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 494478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 1; i <= maxlevel; ++i) { 495478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (p = levels[i]; p; p = p->link) { 496478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->out_use |= JT(p)->in_use | JF(p)->in_use; 497478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->in_use |= p->out_use &~ p->kill; 498478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 499478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 500478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 501478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 502478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 503478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * These data structures are used in a Cocke and Shwarz style 504478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * value numbering scheme. Since the flowgraph is acyclic, 505478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * exit values can be propagated from a node's predecessors 506478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * provided it is uniquely defined. 507478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 508478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstruct valnode { 509478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int code; 510478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int v0, v1; 511478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int val; 512478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct valnode *next; 513478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project}; 514478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 515478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define MODULUS 213 516478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic struct valnode *hashtbl[MODULUS]; 517478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int curval; 518478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int maxval; 519478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 520478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* Integer constants mapped with the load immediate opcode. */ 521478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#define K(i) F(BPF_LD|BPF_IMM|BPF_W, i, 0L) 522478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 523478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstruct vmapinfo { 524478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int is_const; 525478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_int32 const_val; 526478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project}; 527478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 528478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstruct vmapinfo *vmap; 529478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstruct valnode *vnode_base; 530478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstruct valnode *next_vnode; 531478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 532478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 533511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallinit_val(void) 534478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 535478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project curval = 0; 536478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project next_vnode = vnode_base; 537478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memset((char *)vmap, 0, maxval * sizeof(*vmap)); 538478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memset((char *)hashtbl, 0, sizeof hashtbl); 539478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 540478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 541478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* Because we really don't have an IR, this stuff is a little messy. */ 542478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int 543511eca30a483e912c274e1d8ba3a0f8f081e2227JP AbgrallF(int code, int v0, int v1) 544478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 545478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project u_int hash; 546478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int val; 547478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct valnode *p; 548478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 549478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project hash = (u_int)code ^ (v0 << 4) ^ (v1 << 8); 550478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project hash %= MODULUS; 551478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 552478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (p = hashtbl[hash]; p; p = p->next) 553478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (p->code == code && p->v0 == v0 && p->v1 == v1) 554478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return p->val; 555478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 556478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val = ++curval; 557478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (BPF_MODE(code) == BPF_IMM && 558478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project (BPF_CLASS(code) == BPF_LD || BPF_CLASS(code) == BPF_LDX)) { 559478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vmap[val].const_val = v0; 560478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vmap[val].is_const = 1; 561478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 562478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p = next_vnode++; 563478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->val = val; 564478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->code = code; 565478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->v0 = v0; 566478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->v1 = v1; 567478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->next = hashtbl[hash]; 568478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project hashtbl[hash] = p; 569478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 570478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return val; 571478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 572478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 573478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic inline void 574511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallvstore(struct stmt *s, int *valp, int newval, int alter) 575478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 576478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (alter && *valp == newval) 577478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = NOP; 578478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 579478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project *valp = newval; 580478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 581478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 582511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall/* 583511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall * Do constant-folding on binary operators. 584511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall * (Unary operators are handled elsewhere.) 585511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall */ 586478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 587511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallfold_op(struct stmt *s, int v0, int v1) 588478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 589478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_u_int32 a, b; 590478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 591478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project a = vmap[v0].const_val; 592478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b = vmap[v1].const_val; 593478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 594478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project switch (BPF_OP(s->code)) { 595478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ADD: 596478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project a += b; 597478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 598478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 599478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_SUB: 600478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project a -= b; 601478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 602478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 603478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_MUL: 604478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project a *= b; 605478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 606478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 607478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_DIV: 608478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (b == 0) 609478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error("division by zero"); 610478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project a /= b; 611478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 612478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 613478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_AND: 614478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project a &= b; 615478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 616478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 617478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_OR: 618478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project a |= b; 619478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 620478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 621478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LSH: 622478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project a <<= b; 623478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 624478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 625478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_RSH: 626478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project a >>= b; 627478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 628478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 629478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project default: 630478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project abort(); 631478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 632478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->k = a; 633478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = BPF_LD|BPF_IMM; 634478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 635478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 636478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 637478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic inline struct slist * 638511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallthis_op(struct slist *s) 639478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 640478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (s != 0 && s->s.code == NOP) 641478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s = s->next; 642478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return s; 643478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 644478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 645478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 646511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_not(struct block *b) 647478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 648478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block *tmp = JT(b); 649478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 650478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JT(b) = JF(b); 651478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JF(b) = tmp; 652478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 653478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 654478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 655511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_peep(struct block *b) 656478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 657478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct slist *s; 658478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct slist *next, *last; 659478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int val; 660478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 661478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s = b->stmts; 662478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (s == 0) 663478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 664478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 665478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last = s; 666478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (/*empty*/; /*empty*/; s = next) { 667478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 668478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Skip over nops. 669478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 670478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s = this_op(s); 671478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (s == 0) 672478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; /* nothing left in the block */ 673478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 674478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 675478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Find the next real instruction after that one 676478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (skipping nops). 677478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 678478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project next = this_op(s->next); 679478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (next == 0) 680478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; /* no next instruction */ 681478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last = next; 682478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 683478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 684478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * st M[k] --> st M[k] 685478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * ldx M[k] tax 686478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 687478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (s->s.code == BPF_ST && 688478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project next->s.code == (BPF_LDX|BPF_MEM) && 689478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->s.k == next->s.k) { 690478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 691478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project next->s.code = BPF_MISC|BPF_TAX; 692478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 693478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 694478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * ld #k --> ldx #k 695478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * tax txa 696478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 697478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (s->s.code == (BPF_LD|BPF_IMM) && 698478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project next->s.code == (BPF_MISC|BPF_TAX)) { 699478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->s.code = BPF_LDX|BPF_IMM; 700478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project next->s.code = BPF_MISC|BPF_TXA; 701478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 702478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 703478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 704478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * This is an ugly special case, but it happens 705478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * when you say tcp[k] or udp[k] where k is a constant. 706478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 707478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (s->s.code == (BPF_LD|BPF_IMM)) { 708478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct slist *add, *tax, *ild; 709478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 710478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 711478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Check that X isn't used on exit from this 712478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * block (which the optimizer might cause). 713478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * We know the code generator won't generate 714478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * any local dependencies. 715478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 716478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (ATOMELEM(b->out_use, X_ATOM)) 717478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project continue; 718478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 719478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 720478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Check that the instruction following the ldi 721478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * is an addx, or it's an ldxms with an addx 722478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * following it (with 0 or more nops between the 723478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * ldxms and addx). 724478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 725478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (next->s.code != (BPF_LDX|BPF_MSH|BPF_B)) 726478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project add = next; 727478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 728478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project add = this_op(next->next); 729478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X)) 730478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project continue; 731478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 732478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 733478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Check that a tax follows that (with 0 or more 734478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * nops between them). 735478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 736478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project tax = this_op(add->next); 737478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (tax == 0 || tax->s.code != (BPF_MISC|BPF_TAX)) 738478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project continue; 739478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 740478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 741478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Check that an ild follows that (with 0 or more 742478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * nops between them). 743478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 744478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project ild = this_op(tax->next); 745478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (ild == 0 || BPF_CLASS(ild->s.code) != BPF_LD || 746478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project BPF_MODE(ild->s.code) != BPF_IND) 747478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project continue; 748478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 749478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * We want to turn this sequence: 750478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 751478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (004) ldi #0x2 {s} 752478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (005) ldxms [14] {next} -- optional 753478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (006) addx {add} 754478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (007) tax {tax} 755478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (008) ild [x+0] {ild} 756478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 757478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * into this sequence: 758478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 759478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (004) nop 760478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (005) ldxms [14] 761478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (006) nop 762478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (007) nop 763478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (008) ild [x+2] 764478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 765478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * XXX We need to check that X is not 766478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * subsequently used, because we want to change 767478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * what'll be in it after this sequence. 768478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 769478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * We know we can eliminate the accumulator 770478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * modifications earlier in the sequence since 771478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * it is defined by the last stmt of this sequence 772478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * (i.e., the last statement of the sequence loads 773478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * a value into the accumulator, so we can eliminate 774478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * earlier operations on the accumulator). 775478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 776478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project ild->s.k += s->s.k; 777478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->s.code = NOP; 778478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project add->s.code = NOP; 779478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project tax->s.code = NOP; 780478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 781478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 782478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 783478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 784478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * If the comparison at the end of a block is an equality 785478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * comparison against a constant, and nobody uses the value 786478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * we leave in the A register at the end of a block, and 787478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * the operation preceding the comparison is an arithmetic 788478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * operation, we can sometime optimize it away. 789478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 790478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (b->s.code == (BPF_JMP|BPF_JEQ|BPF_K) && 791478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project !ATOMELEM(b->out_use, A_ATOM)) { 792478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 793478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * We can optimize away certain subtractions of the 794478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * X register. 795478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 796478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (last->s.code == (BPF_ALU|BPF_SUB|BPF_X)) { 797478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val = b->val[X_ATOM]; 798478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (vmap[val].is_const) { 799478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 800478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * If we have a subtract to do a comparison, 801478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * and the X register is a known constant, 802478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * we can merge this value into the 803478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * comparison: 804478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 805478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * sub x -> nop 806478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * jeq #y jeq #(x+y) 807478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 808478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->s.k += vmap[val].const_val; 809478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last->s.code = NOP; 810478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 811478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } else if (b->s.k == 0) { 812478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 813478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * If the X register isn't a constant, 814478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * and the comparison in the test is 815478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * against 0, we can compare with the 816478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * X register, instead: 817478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 818478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * sub x -> nop 819478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * jeq #0 jeq x 820478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 821478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last->s.code = NOP; 822478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->s.code = BPF_JMP|BPF_JEQ|BPF_X; 823478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 824478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 825478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 826478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 827478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Likewise, a constant subtract can be simplified: 828478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 829478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * sub #x -> nop 830478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * jeq #y -> jeq #(x+y) 831478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 832478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K)) { 833478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last->s.code = NOP; 834478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->s.k += last->s.k; 835478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 836478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 837478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 838478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * And, similarly, a constant AND can be simplified 839478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * if we're testing against 0, i.e.: 840478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 841478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * and #k nop 842478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * jeq #0 -> jset #k 843478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 844478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else if (last->s.code == (BPF_ALU|BPF_AND|BPF_K) && 845478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->s.k == 0) { 846478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->s.k = last->s.k; 847478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->s.code = BPF_JMP|BPF_K|BPF_JSET; 848478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last->s.code = NOP; 849478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 850478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_not(b); 851478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 852478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 853478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 854478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * jset #0 -> never 855478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * jset #ffffffff -> always 856478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 857478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (b->s.code == (BPF_JMP|BPF_K|BPF_JSET)) { 858478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (b->s.k == 0) 859478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JT(b) = JF(b); 860478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (b->s.k == 0xffffffff) 861478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JF(b) = JT(b); 862478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 863478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 864511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall * If we're comparing against the index register, and the index 865511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall * register is a known constant, we can just compare against that 866511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall * constant. 867511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall */ 868511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall val = b->val[X_ATOM]; 869511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall if (vmap[val].is_const && BPF_SRC(b->s.code) == BPF_X) { 870511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall bpf_int32 v = vmap[val].const_val; 871511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall b->s.code &= ~BPF_X; 872511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall b->s.k = v; 873511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall } 874511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall /* 875478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * If the accumulator is a known constant, we can compute the 876478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * comparison result. 877478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 878478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val = b->val[A_ATOM]; 879478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) { 880478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_int32 v = vmap[val].const_val; 881478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project switch (BPF_OP(b->s.code)) { 882478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 883478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_JEQ: 884478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = v == b->s.k; 885478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 886478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 887478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_JGT: 888478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = (unsigned)v > b->s.k; 889478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 890478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 891478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_JGE: 892478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = (unsigned)v >= b->s.k; 893478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 894478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 895478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_JSET: 896478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v &= b->s.k; 897478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 898478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 899478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project default: 900478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project abort(); 901478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 902478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JF(b) != JT(b)) 903478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 904478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (v) 905478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JF(b) = JT(b); 906478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 907478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JT(b) = JF(b); 908478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 909478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 910478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 911478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 912478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Compute the symbolic value of expression of 's', and update 913478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * anything it defines in the value table 'val'. If 'alter' is true, 914478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * do various optimizations. This code would be cleaner if symbolic 915478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * evaluation and code transformations weren't folded together. 916478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 917478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 918511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_stmt(struct stmt *s, int val[], int alter) 919478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 920478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int op; 921478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int v; 922478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 923478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project switch (s->code) { 924478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 925478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LD|BPF_ABS|BPF_W: 926478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LD|BPF_ABS|BPF_H: 927478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LD|BPF_ABS|BPF_B: 928478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = F(s->code, s->k, 0L); 929478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[A_ATOM], v, alter); 930478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 931478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 932478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LD|BPF_IND|BPF_W: 933478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LD|BPF_IND|BPF_H: 934478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LD|BPF_IND|BPF_B: 935478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = val[X_ATOM]; 936478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (alter && vmap[v].is_const) { 937478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = BPF_LD|BPF_ABS|BPF_SIZE(s->code); 938478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->k += vmap[v].const_val; 939478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = F(s->code, s->k, 0L); 940478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 941478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 942478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 943478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = F(s->code, s->k, v); 944478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[A_ATOM], v, alter); 945478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 946478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 947478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LD|BPF_LEN: 948478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = F(s->code, 0L, 0L); 949478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[A_ATOM], v, alter); 950478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 951478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 952478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LD|BPF_IMM: 953478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = K(s->k); 954478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[A_ATOM], v, alter); 955478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 956478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 957478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LDX|BPF_IMM: 958478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = K(s->k); 959478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[X_ATOM], v, alter); 960478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 961478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 962478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LDX|BPF_MSH|BPF_B: 963478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = F(s->code, s->k, 0L); 964478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[X_ATOM], v, alter); 965478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 966478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 967478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_NEG: 968478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (alter && vmap[val[A_ATOM]].is_const) { 969478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = BPF_LD|BPF_IMM; 970478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->k = -vmap[val[A_ATOM]].const_val; 971478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val[A_ATOM] = K(s->k); 972478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 973478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 974478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val[A_ATOM] = F(s->code, val[A_ATOM], 0L); 975478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 976478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 977478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_ADD|BPF_K: 978478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_SUB|BPF_K: 979478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_MUL|BPF_K: 980478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_DIV|BPF_K: 981478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_AND|BPF_K: 982478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_OR|BPF_K: 983478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_LSH|BPF_K: 984478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_RSH|BPF_K: 985478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project op = BPF_OP(s->code); 986478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (alter) { 987478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (s->k == 0) { 988478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* don't optimize away "sub #0" 989478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * as it may be needed later to 990478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * fixup the generated math code */ 991478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (op == BPF_ADD || 992478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project op == BPF_LSH || op == BPF_RSH || 993478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project op == BPF_OR) { 994478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = NOP; 995478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 996478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 997478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (op == BPF_MUL || op == BPF_AND) { 998478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = BPF_LD|BPF_IMM; 999478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val[A_ATOM] = K(s->k); 1000478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1001478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1002478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1003478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (vmap[val[A_ATOM]].is_const) { 1004478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project fold_op(s, val[A_ATOM], K(s->k)); 1005478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val[A_ATOM] = K(s->k); 1006478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1007478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1008478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1009478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val[A_ATOM] = F(s->code, val[A_ATOM], K(s->k)); 1010478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1011478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1012478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_ADD|BPF_X: 1013478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_SUB|BPF_X: 1014478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_MUL|BPF_X: 1015478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_DIV|BPF_X: 1016478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_AND|BPF_X: 1017478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_OR|BPF_X: 1018478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_LSH|BPF_X: 1019478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ALU|BPF_RSH|BPF_X: 1020478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project op = BPF_OP(s->code); 1021478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (alter && vmap[val[X_ATOM]].is_const) { 1022478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (vmap[val[A_ATOM]].is_const) { 1023478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project fold_op(s, val[A_ATOM], val[X_ATOM]); 1024478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val[A_ATOM] = K(s->k); 1025478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1026478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else { 1027478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = BPF_ALU|BPF_K|op; 1028478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->k = vmap[val[X_ATOM]].const_val; 1029478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 1030478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val[A_ATOM] = 1031478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project F(s->code, val[A_ATOM], K(s->k)); 1032478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1033478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1034478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1035478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1036478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Check if we're doing something to an accumulator 1037478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * that is 0, and simplify. This may not seem like 1038478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * much of a simplification but it could open up further 1039478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * optimizations. 1040478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * XXX We could also check for mul by 1, etc. 1041478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1042478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (alter && vmap[val[A_ATOM]].is_const 1043478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project && vmap[val[A_ATOM]].const_val == 0) { 1044478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (op == BPF_ADD || op == BPF_OR) { 1045478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = BPF_MISC|BPF_TXA; 1046478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[A_ATOM], val[X_ATOM], alter); 1047478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1048478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1049478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else if (op == BPF_MUL || op == BPF_DIV || 1050478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project op == BPF_AND || op == BPF_LSH || op == BPF_RSH) { 1051478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = BPF_LD|BPF_IMM; 1052478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->k = 0; 1053478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[A_ATOM], K(s->k), alter); 1054478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1055478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1056478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else if (op == BPF_NEG) { 1057478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = NOP; 1058478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1059478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1060478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1061478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val[A_ATOM] = F(s->code, val[A_ATOM], val[X_ATOM]); 1062478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1063478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1064478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_MISC|BPF_TXA: 1065478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[A_ATOM], val[X_ATOM], alter); 1066478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1067478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1068478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LD|BPF_MEM: 1069478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = val[s->k]; 1070478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (alter && vmap[v].is_const) { 1071478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = BPF_LD|BPF_IMM; 1072478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->k = vmap[v].const_val; 1073478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 1074478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1075478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[A_ATOM], v, alter); 1076478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1077478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1078478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_MISC|BPF_TAX: 1079478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[X_ATOM], val[A_ATOM], alter); 1080478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1081478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1082478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_LDX|BPF_MEM: 1083478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project v = val[s->k]; 1084478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (alter && vmap[v].is_const) { 1085478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->code = BPF_LDX|BPF_IMM; 1086478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s->k = vmap[v].const_val; 1087478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 1088478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1089478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[X_ATOM], v, alter); 1090478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1091478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1092478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_ST: 1093478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[s->k], val[A_ATOM], alter); 1094478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1095478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1096478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project case BPF_STX: 1097478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vstore(s, &val[s->k], val[X_ATOM], alter); 1098478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1099478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1100478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1101478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1102478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1103511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgralldeadstmt(register struct stmt *s, register struct stmt *last[]) 1104478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1105478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register int atom; 1106478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1107478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project atom = atomuse(s); 1108478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (atom >= 0) { 1109478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (atom == AX_ATOM) { 1110478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last[X_ATOM] = 0; 1111478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last[A_ATOM] = 0; 1112478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1113478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 1114478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last[atom] = 0; 1115478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1116478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project atom = atomdef(s); 1117478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (atom >= 0) { 1118478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (last[atom]) { 1119478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 1120478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last[atom]->code = NOP; 1121478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1122478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last[atom] = s; 1123478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1124478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1125478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1126478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1127511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_deadstores(register struct block *b) 1128478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1129478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register struct slist *s; 1130478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register int atom; 1131478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct stmt *last[N_ATOMS]; 1132478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1133478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memset((char *)last, 0, sizeof last); 1134478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1135478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (s = b->stmts; s != 0; s = s->next) 1136478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project deadstmt(&s->s, last); 1137478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project deadstmt(&b->s, last); 1138478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1139478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (atom = 0; atom < N_ATOMS; ++atom) 1140478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (last[atom] && !ATOMELEM(b->out_use, atom)) { 1141478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project last[atom]->code = NOP; 1142478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 1143478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1144478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1145478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1146478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1147511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_blk(struct block *b, int do_stmts) 1148478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1149478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct slist *s; 1150478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct edge *p; 1151478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int i; 1152478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_int32 aval, xval; 1153478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1154478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#if 0 1155478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (s = b->stmts; s && s->next; s = s->next) 1156478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (BPF_CLASS(s->s.code) == BPF_JMP) { 1157478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project do_stmts = 0; 1158478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1159478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1160478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 1161478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1162478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1163478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Initialize the atom values. 1164478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1165478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p = b->in_edges; 1166478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (p == 0) { 1167478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1168478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * We have no predecessors, so everything is undefined 1169478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * upon entry to this block. 1170478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1171478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memset((char *)b->val, 0, sizeof(b->val)); 1172478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } else { 1173478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1174478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Inherit values from our predecessors. 1175478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1176478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * First, get the values from the predecessor along the 1177478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * first edge leading to this node. 1178478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1179478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memcpy((char *)b->val, (char *)p->pred->val, sizeof(b->val)); 1180478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1181478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Now look at all the other nodes leading to this node. 1182478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * If, for the predecessor along that edge, a register 1183478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * has a different value from the one we have (i.e., 1184478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * control paths are merging, and the merging paths 1185478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * assign different values to that register), give the 1186478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * register the undefined value of 0. 1187478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1188478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while ((p = p->next) != NULL) { 1189478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < N_ATOMS; ++i) 1190478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (b->val[i] != p->pred->val[i]) 1191478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->val[i] = 0; 1192478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1193478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1194478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project aval = b->val[A_ATOM]; 1195478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project xval = b->val[X_ATOM]; 1196478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (s = b->stmts; s; s = s->next) 1197478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_stmt(&s->s, b->val, do_stmts); 1198478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1199478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1200478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * This is a special case: if we don't use anything from this 1201478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * block, and we load the accumulator or index register with a 1202478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * value that is already there, or if this block is a return, 1203478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * eliminate all the statements. 1204478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1205478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * XXX - what if it does a store? 1206478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1207478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * XXX - why does it matter whether we use anything from this 1208478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * block? If the accumulator or index register doesn't change 1209478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * its value, isn't that OK even if we use that value? 1210478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1211478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * XXX - if we load the accumulator with a different value, 1212478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * and the block ends with a conditional branch, we obviously 1213478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * can't eliminate it, as the branch depends on that value. 1214478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * For the index register, the conditional branch only depends 1215478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * on the index register value if the test is against the index 1216478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * register value rather than a constant; if nothing uses the 1217478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * value we put into the index register, and we're not testing 1218478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * against the index register's value, and there aren't any 1219478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * other problems that would keep us from eliminating this 1220478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * block, can we eliminate it? 1221478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1222478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (do_stmts && 1223478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project ((b->out_use == 0 && aval != 0 && b->val[A_ATOM] == aval && 1224478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project xval != 0 && b->val[X_ATOM] == xval) || 1225478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project BPF_CLASS(b->s.code) == BPF_RET)) { 1226478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (b->stmts != 0) { 1227478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->stmts = 0; 1228478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 1229478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1230478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } else { 1231478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_peep(b); 1232478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_deadstores(b); 1233478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1234478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1235478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Set up values for branch optimizer. 1236478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1237478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (BPF_SRC(b->s.code) == BPF_K) 1238478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->oval = K(b->s.k); 1239478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 1240478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->oval = b->val[X_ATOM]; 1241478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->et.code = b->s.code; 1242478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->ef.code = -b->s.code; 1243478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1244478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1245478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 1246478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Return true if any register that is used on exit from 'succ', has 1247478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * an exit value that is different from the corresponding exit value 1248478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * from 'b'. 1249478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1250478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int 1251511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgralluse_conflict(struct block *b, struct block *succ) 1252478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1253478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int atom; 1254478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project atomset use = succ->out_use; 1255478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1256478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (use == 0) 1257478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return 0; 1258478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1259478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (atom = 0; atom < N_ATOMS; ++atom) 1260478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (ATOMELEM(use, atom)) 1261478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (b->val[atom] != succ->val[atom]) 1262478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return 1; 1263478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return 0; 1264478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1265478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1266478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic struct block * 1267511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallfold_edge(struct block *child, struct edge *ep) 1268478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1269478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int sense; 1270478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int aval0, aval1, oval0, oval1; 1271478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int code = ep->code; 1272478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1273478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (code < 0) { 1274478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project code = -code; 1275478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project sense = 0; 1276478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } else 1277478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project sense = 1; 1278478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1279478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (child->s.code != code) 1280478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return 0; 1281478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1282478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project aval0 = child->val[A_ATOM]; 1283478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project oval0 = child->oval; 1284478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project aval1 = ep->pred->val[A_ATOM]; 1285478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project oval1 = ep->pred->oval; 1286478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1287478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (aval0 != aval1) 1288478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return 0; 1289478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1290478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (oval0 == oval1) 1291478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1292478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * The operands of the branch instructions are 1293478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * identical, so the result is true if a true 1294478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * branch was taken to get here, otherwise false. 1295478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1296478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return sense ? JT(child) : JF(child); 1297478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1298478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (sense && code == (BPF_JMP|BPF_JEQ|BPF_K)) 1299478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1300478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * At this point, we only know the comparison if we 1301478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * came down the true branch, and it was an equality 1302478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * comparison with a constant. 1303478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1304478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * I.e., if we came down the true branch, and the branch 1305478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * was an equality comparison with a constant, we know the 1306478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * accumulator contains that constant. If we came down 1307478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * the false branch, or the comparison wasn't with a 1308478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * constant, we don't know what was in the accumulator. 1309478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1310478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * We rely on the fact that distinct constants have distinct 1311478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * value numbers. 1312478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1313478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return JF(child); 1314478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1315478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return 0; 1316478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1317478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1318478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1319511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_j(struct edge *ep) 1320478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1321478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register int i, k; 1322478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register struct block *target; 1323478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1324478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(ep->succ) == 0) 1325478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1326478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1327478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(ep->succ) == JF(ep->succ)) { 1328478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1329478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Common branch targets can be eliminated, provided 1330478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * there is no data dependency. 1331478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1332478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!use_conflict(ep->pred, ep->succ->et.succ)) { 1333478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 1334478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project ep->succ = JT(ep->succ); 1335478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1336478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1337478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1338478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * For each edge dominator that matches the successor of this 1339478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * edge, promote the edge successor to the its grandchild. 1340478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1341478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * XXX We violate the set abstraction here in favor a reasonably 1342478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * efficient loop. 1343478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1344478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project top: 1345478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < edgewords; ++i) { 1346478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register bpf_u_int32 x = ep->edom[i]; 1347478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1348478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (x != 0) { 1349478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project k = ffs(x) - 1; 1350478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project x &=~ (1 << k); 1351478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project k += i * BITS_PER_WORD; 1352478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1353478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project target = fold_edge(ep->succ, edges[k]); 1354478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1355478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Check that there is no data dependency between 1356478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * nodes that will be violated if we move the edge. 1357478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1358478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (target != 0 && !use_conflict(ep->pred, target)) { 1359478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 1360478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project ep->succ = target; 1361478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(target) != 0) 1362478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1363478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Start over unless we hit a leaf. 1364478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1365478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project goto top; 1366478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1367478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1368478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1369478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1370478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1371478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1372478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1373478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1374511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallor_pullup(struct block *b) 1375478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1376478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int val, at_top; 1377478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block *pull; 1378478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block **diffp, **samep; 1379478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct edge *ep; 1380478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1381478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project ep = b->in_edges; 1382478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (ep == 0) 1383478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1384478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1385478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1386478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Make sure each predecessor loads the same value. 1387478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * XXX why? 1388478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1389478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val = ep->pred->val[A_ATOM]; 1390478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (ep = ep->next; ep != 0; ep = ep->next) 1391478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (val != ep->pred->val[A_ATOM]) 1392478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1393478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1394478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(b->in_edges->pred) == b) 1395478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project diffp = &JT(b->in_edges->pred); 1396478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 1397478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project diffp = &JF(b->in_edges->pred); 1398478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1399478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project at_top = 1; 1400478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (1) { 1401478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (*diffp == 0) 1402478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1403478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1404478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(*diffp) != JT(b)) 1405478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1406478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1407478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!SET_MEMBER((*diffp)->dom, b->id)) 1408478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1409478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1410478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if ((*diffp)->val[A_ATOM] != val) 1411478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1412478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1413478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project diffp = &JF(*diffp); 1414478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project at_top = 0; 1415478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1416478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project samep = &JF(*diffp); 1417478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (1) { 1418478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (*samep == 0) 1419478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1420478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1421478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(*samep) != JT(b)) 1422478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1423478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1424478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!SET_MEMBER((*samep)->dom, b->id)) 1425478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1426478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1427478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if ((*samep)->val[A_ATOM] == val) 1428478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1429478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1430478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* XXX Need to check that there are no data dependencies 1431478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project between dp0 and dp1. Currently, the code generator 1432478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project will not produce such dependencies. */ 1433478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project samep = &JF(*samep); 1434478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1435478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef notdef 1436478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* XXX This doesn't cover everything. */ 1437478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < N_ATOMS; ++i) 1438478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if ((*samep)->val[i] != pred->val[i]) 1439478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1440478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 1441478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* Pull up the node. */ 1442478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project pull = *samep; 1443478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project *samep = JF(pull); 1444478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JF(pull) = *diffp; 1445478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1446478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1447478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * At the top of the chain, each predecessor needs to point at the 1448478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * pulled up node. Inside the chain, there is only one predecessor 1449478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * to worry about. 1450478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1451478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (at_top) { 1452478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (ep = b->in_edges; ep != 0; ep = ep->next) { 1453478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(ep->pred) == b) 1454478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JT(ep->pred) = pull; 1455478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 1456478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JF(ep->pred) = pull; 1457478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1458478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1459478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 1460478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project *diffp = pull; 1461478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1462478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 1463478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1464478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1465478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1466511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgralland_pullup(struct block *b) 1467478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1468478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int val, at_top; 1469478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block *pull; 1470478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block **diffp, **samep; 1471478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct edge *ep; 1472478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1473478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project ep = b->in_edges; 1474478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (ep == 0) 1475478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1476478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1477478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1478478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Make sure each predecessor loads the same value. 1479478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1480478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project val = ep->pred->val[A_ATOM]; 1481478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (ep = ep->next; ep != 0; ep = ep->next) 1482478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (val != ep->pred->val[A_ATOM]) 1483478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1484478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1485478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(b->in_edges->pred) == b) 1486478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project diffp = &JT(b->in_edges->pred); 1487478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 1488478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project diffp = &JF(b->in_edges->pred); 1489478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1490478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project at_top = 1; 1491478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (1) { 1492478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (*diffp == 0) 1493478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1494478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1495478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JF(*diffp) != JF(b)) 1496478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1497478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1498478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!SET_MEMBER((*diffp)->dom, b->id)) 1499478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1500478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1501478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if ((*diffp)->val[A_ATOM] != val) 1502478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1503478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1504478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project diffp = &JT(*diffp); 1505478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project at_top = 0; 1506478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1507478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project samep = &JT(*diffp); 1508478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (1) { 1509478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (*samep == 0) 1510478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1511478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1512478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JF(*samep) != JF(b)) 1513478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1514478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1515478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!SET_MEMBER((*samep)->dom, b->id)) 1516478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1517478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1518478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if ((*samep)->val[A_ATOM] == val) 1519478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1520478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1521478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* XXX Need to check that there are no data dependencies 1522478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project between diffp and samep. Currently, the code generator 1523478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project will not produce such dependencies. */ 1524478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project samep = &JT(*samep); 1525478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1526478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef notdef 1527478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* XXX This doesn't cover everything. */ 1528478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < N_ATOMS; ++i) 1529478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if ((*samep)->val[i] != pred->val[i]) 1530478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1531478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 1532478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* Pull up the node. */ 1533478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project pull = *samep; 1534478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project *samep = JT(pull); 1535478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JT(pull) = *diffp; 1536478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1537478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1538478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * At the top of the chain, each predecessor needs to point at the 1539478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * pulled up node. Inside the chain, there is only one predecessor 1540478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * to worry about. 1541478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1542478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (at_top) { 1543478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (ep = b->in_edges; ep != 0; ep = ep->next) { 1544478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(ep->pred) == b) 1545478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JT(ep->pred) = pull; 1546478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 1547478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JF(ep->pred) = pull; 1548478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1549478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1550478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 1551478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project *diffp = pull; 1552478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1553478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 0; 1554478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1555478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1556478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1557511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_blks(struct block *root, int do_stmts) 1558478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1559478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int i, maxlevel; 1560478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block *p; 1561478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1562478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project init_val(); 1563478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project maxlevel = root->level; 1564478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1565478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project find_inedges(root); 1566478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = maxlevel; i >= 0; --i) 1567478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (p = levels[i]; p; p = p->link) 1568478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_blk(p, do_stmts); 1569478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1570478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (do_stmts) 1571478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1572478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * No point trying to move branches; it can't possibly 1573478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * make a difference at this point. 1574478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1575478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1576478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1577478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 1; i <= maxlevel; ++i) { 1578478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (p = levels[i]; p; p = p->link) { 1579478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_j(&p->et); 1580478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_j(&p->ef); 1581478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1582478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1583478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1584478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project find_inedges(root); 1585478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 1; i <= maxlevel; ++i) { 1586478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (p = levels[i]; p; p = p->link) { 1587478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project or_pullup(p); 1588478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project and_pullup(p); 1589478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1590478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1591478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1592478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1593478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic inline void 1594511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgralllink_inedge(struct edge *parent, struct block *child) 1595478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1596478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project parent->next = child->in_edges; 1597478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project child->in_edges = parent; 1598478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1599478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1600478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1601511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallfind_inedges(struct block *root) 1602478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1603478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int i; 1604478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block *b; 1605478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1606478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < n_blocks; ++i) 1607478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project blocks[i]->in_edges = 0; 1608478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1609478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1610478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Traverse the graph, adding each edge to the predecessor 1611478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * list of its successors. Skip the leaves (i.e. level 0). 1612478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1613478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = root->level; i > 0; --i) { 1614478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (b = levels[i]; b != 0; b = b->link) { 1615478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project link_inedge(&b->et, JT(b)); 1616478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project link_inedge(&b->ef, JF(b)); 1617478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1618478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1619478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1620478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1621478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1622511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_root(struct block **b) 1623478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1624478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct slist *tmp, *s; 1625478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1626478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project s = (*b)->stmts; 1627478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project (*b)->stmts = 0; 1628478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (BPF_CLASS((*b)->s.code) == BPF_JMP && JT(*b) == JF(*b)) 1629478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project *b = JT(*b); 1630478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1631478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project tmp = (*b)->stmts; 1632478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (tmp != 0) 1633478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project sappend(s, tmp); 1634478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project (*b)->stmts = s; 1635478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1636478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1637478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * If the root node is a return, then there is no 1638478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * point executing any statements (since the bpf machine 1639478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * has no side effects). 1640478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1641478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (BPF_CLASS((*b)->s.code) == BPF_RET) 1642478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project (*b)->stmts = 0; 1643478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1644478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1645478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1646511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_loop(struct block *root, int do_stmts) 1647478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1648478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1649478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef BDEBUG 1650478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (dflag > 1) { 1651478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project printf("opt_loop(root, %d) begin\n", do_stmts); 1652478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_dump(root); 1653478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1654478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 1655478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project do { 1656478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done = 1; 1657478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project find_levels(root); 1658478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project find_dom(root); 1659478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project find_closure(root); 1660478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project find_ud(root); 1661478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project find_edom(root); 1662478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_blks(root, do_stmts); 1663478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef BDEBUG 1664478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (dflag > 1) { 1665478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, done); 1666478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_dump(root); 1667478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1668478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 1669478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } while (!done); 1670478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1671478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1672478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 1673478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Optimize the filter code in its dag representation. 1674478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1675478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectvoid 1676511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallbpf_optimize(struct block **rootp) 1677478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1678478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block *root; 1679478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1680478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project root = *rootp; 1681478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1682478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_init(root); 1683478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_loop(root, 0); 1684478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_loop(root, 1); 1685478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project intern_blocks(root); 1686478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef BDEBUG 1687478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (dflag > 1) { 1688478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project printf("after intern_blocks()\n"); 1689478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_dump(root); 1690478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1691478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 1692478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_root(rootp); 1693478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef BDEBUG 1694478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (dflag > 1) { 1695478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project printf("after opt_root()\n"); 1696478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_dump(root); 1697478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1698478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 1699478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project opt_cleanup(); 1700478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1701478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1702478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1703511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallmake_marks(struct block *p) 1704478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1705478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!isMarked(p)) { 1706478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project Mark(p); 1707478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (BPF_CLASS(p->s.code) != BPF_RET) { 1708478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project make_marks(JT(p)); 1709478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project make_marks(JF(p)); 1710478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1711478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1712478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1713478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1714478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 1715478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Mark code array such that isMarked(i) is true 1716478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * only for nodes that are alive. 1717478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1718478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1719511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallmark_code(struct block *p) 1720478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1721478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project cur_mark += 1; 1722478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project make_marks(p); 1723478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1724478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1725478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 1726478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * True iff the two stmt lists load the same value from the packet into 1727478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * the accumulator. 1728478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1729478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int 1730511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgralleq_slist(struct slist *x, struct slist *y) 1731478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1732478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (1) { 1733478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (x && x->s.code == NOP) 1734478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project x = x->next; 1735478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (y && y->s.code == NOP) 1736478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project y = y->next; 1737478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (x == 0) 1738478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return y == 0; 1739478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (y == 0) 1740478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return x == 0; 1741478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (x->s.code != y->s.code || x->s.k != y->s.k) 1742478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return 0; 1743478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project x = x->next; 1744478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project y = y->next; 1745478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1746478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1747478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1748478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic inline int 1749511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgralleq_blk(struct block *b0, struct block *b1) 1750478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1751478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (b0->s.code == b1->s.code && 1752478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b0->s.k == b1->s.k && 1753478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b0->et.succ == b1->et.succ && 1754478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b0->ef.succ == b1->ef.succ) 1755478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return eq_slist(b0->stmts, b1->stmts); 1756478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return 0; 1757478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1758478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1759478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1760511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallintern_blocks(struct block *root) 1761478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1762478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct block *p; 1763478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int i, j; 1764478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int done1; /* don't shadow global */ 1765478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project top: 1766478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done1 = 1; 1767478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < n_blocks; ++i) 1768478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project blocks[i]->link = 0; 1769478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1770478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project mark_code(root); 1771478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1772478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = n_blocks - 1; --i >= 0; ) { 1773478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!isMarked(blocks[i])) 1774478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project continue; 1775478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (j = i + 1; j < n_blocks; ++j) { 1776478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!isMarked(blocks[j])) 1777478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project continue; 1778478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (eq_blk(blocks[i], blocks[j])) { 1779478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project blocks[i]->link = blocks[j]->link ? 1780478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project blocks[j]->link : blocks[j]; 1781478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 1782478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1783478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1784478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1785478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < n_blocks; ++i) { 1786478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p = blocks[i]; 1787478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(p) == 0) 1788478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project continue; 1789478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(p)->link) { 1790478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done1 = 0; 1791478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JT(p) = JT(p)->link; 1792478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1793478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JF(p)->link) { 1794478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project done1 = 0; 1795478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project JF(p) = JF(p)->link; 1796478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1797478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1798478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!done1) 1799478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project goto top; 1800478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1801478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1802478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1803511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_cleanup(void) 1804478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1805478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project free((void *)vnode_base); 1806478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project free((void *)vmap); 1807478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project free((void *)edges); 1808478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project free((void *)space); 1809478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project free((void *)levels); 1810478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project free((void *)blocks); 1811478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1812478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1813478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 1814478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Return the number of stmts in 's'. 1815478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1816511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallstatic u_int 1817511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallslength(struct slist *s) 1818478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1819511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall u_int n = 0; 1820478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1821478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (; s; s = s->next) 1822478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (s->s.code != NOP) 1823478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project ++n; 1824478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return n; 1825478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1826478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1827478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 1828478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Return the number of nodes reachable by 'p'. 1829478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * All nodes should be initially unmarked. 1830478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1831478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int 1832511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallcount_blocks(struct block *p) 1833478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1834478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (p == 0 || isMarked(p)) 1835478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return 0; 1836478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project Mark(p); 1837478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return count_blocks(JT(p)) + count_blocks(JF(p)) + 1; 1838478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1839478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1840478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 1841478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Do a depth first search on the flow graph, numbering the 1842478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * the basic blocks, and entering them into the 'blocks' array.` 1843478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1844478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1845511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallnumber_blks_r(struct block *p) 1846478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1847478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int n; 1848478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1849478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (p == 0 || isMarked(p)) 1850478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return; 1851478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1852478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project Mark(p); 1853478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project n = n_blocks++; 1854478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->id = n; 1855478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project blocks[n] = p; 1856478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1857478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project number_blks_r(JT(p)); 1858478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project number_blks_r(JF(p)); 1859478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1860478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1861478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 1862478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Return the number of stmts in the flowgraph reachable by 'p'. 1863478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * The nodes should be unmarked before calling. 1864478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1865478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Note that "stmts" means "instructions", and that this includes 1866478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1867478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * side-effect statements in 'p' (slength(p->stmts)); 1868478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1869478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * statements in the true branch from 'p' (count_stmts(JT(p))); 1870478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1871478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * statements in the false branch from 'p' (count_stmts(JF(p))); 1872478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1873478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * the conditional jump itself (1); 1874478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1875478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * an extra long jump if the true branch requires it (p->longjt); 1876478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 1877478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * an extra long jump if the false branch requires it (p->longjf). 1878478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1879511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallstatic u_int 1880511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallcount_stmts(struct block *p) 1881478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1882511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall u_int n; 1883478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1884478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (p == 0 || isMarked(p)) 1885478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return 0; 1886478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project Mark(p); 1887478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project n = count_stmts(JT(p)) + count_stmts(JF(p)); 1888478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return slength(p->stmts) + n + 1 + p->longjt + p->longjf; 1889478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1890478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1891478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 1892478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Allocate memory. All allocation is done before optimization 1893478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * is begun. A linear bound on the size of all data structures is computed 1894478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * from the total number of blocks and/or statements. 1895478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1896478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 1897511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_init(struct block *root) 1898478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1899478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_u_int32 *p; 1900478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int i, n, max_stmts; 1901478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1902478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1903478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * First, count the blocks, so we can malloc an array to map 1904478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * block number to block. Then, put the blocks into the array. 1905478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1906478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project unMarkAll(); 1907478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project n = count_blocks(root); 1908478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project blocks = (struct block **)calloc(n, sizeof(*blocks)); 1909478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (blocks == NULL) 1910478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error("malloc"); 1911478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project unMarkAll(); 1912478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project n_blocks = 0; 1913478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project number_blks_r(root); 1914478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1915478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project n_edges = 2 * n_blocks; 1916478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project edges = (struct edge **)calloc(n_edges, sizeof(*edges)); 1917478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (edges == NULL) 1918478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error("malloc"); 1919478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1920478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1921478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * The number of levels is bounded by the number of nodes. 1922478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1923478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project levels = (struct block **)calloc(n_blocks, sizeof(*levels)); 1924478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (levels == NULL) 1925478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error("malloc"); 1926478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1927478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project edgewords = n_edges / (8 * sizeof(bpf_u_int32)) + 1; 1928478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project nodewords = n_blocks / (8 * sizeof(bpf_u_int32)) + 1; 1929478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1930478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* XXX */ 1931478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project space = (bpf_u_int32 *)malloc(2 * n_blocks * nodewords * sizeof(*space) 1932478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project + n_edges * edgewords * sizeof(*space)); 1933478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (space == NULL) 1934478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error("malloc"); 1935478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p = space; 1936478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project all_dom_sets = p; 1937478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < n; ++i) { 1938478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project blocks[i]->dom = p; 1939478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p += nodewords; 1940478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1941478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project all_closure_sets = p; 1942478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < n; ++i) { 1943478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project blocks[i]->closure = p; 1944478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p += nodewords; 1945478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1946478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project all_edge_sets = p; 1947478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < n; ++i) { 1948478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project register struct block *b = blocks[i]; 1949478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1950478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->et.edom = p; 1951478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p += edgewords; 1952478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->ef.edom = p; 1953478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p += edgewords; 1954478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->et.id = i; 1955478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project edges[i] = &b->et; 1956478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->ef.id = n_blocks + i; 1957478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project edges[n_blocks + i] = &b->ef; 1958478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->et.pred = b; 1959478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project b->ef.pred = b; 1960478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 1961478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project max_stmts = 0; 1962478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < n; ++i) 1963478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project max_stmts += slength(blocks[i]->stmts) + 1; 1964478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 1965478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * We allocate at most 3 value numbers per statement, 1966478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * so this is an upper bound on the number of valnodes 1967478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * we'll need. 1968478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1969478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project maxval = 3 * max_stmts; 1970478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vmap = (struct vmapinfo *)calloc(maxval, sizeof(*vmap)); 1971478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project vnode_base = (struct valnode *)calloc(maxval, sizeof(*vnode_base)); 1972478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (vmap == NULL || vnode_base == NULL) 1973478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error("malloc"); 1974478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 1975478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1976478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 1977478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Some pointers used to convert the basic block form of the code, 1978478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * into the array form that BPF requires. 'fstart' will point to 1979478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * the malloc'd array while 'ftail' is used during the recursive traversal. 1980478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1981478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic struct bpf_insn *fstart; 1982478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic struct bpf_insn *ftail; 1983478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1984478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef BDEBUG 1985478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectint bids[1000]; 1986478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 1987478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 1988478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 1989478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Returns true if successful. Returns false if a branch has 1990478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * an offset that is too large. If so, we have marked that 1991478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * branch so that on a subsequent iteration, it will be treated 1992478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * properly. 1993478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 1994478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic int 1995511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallconvert_code_r(struct block *p) 1996478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 1997478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct bpf_insn *dst; 1998478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct slist *src; 1999478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int slen; 2000478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project u_int off; 2001478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int extrajmps; /* number of extra jumps inserted */ 2002478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct slist **offset = NULL; 2003478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2004478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (p == 0 || isMarked(p)) 2005478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return (1); 2006478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project Mark(p); 2007478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2008478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (convert_code_r(JF(p)) == 0) 2009478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return (0); 2010478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (convert_code_r(JT(p)) == 0) 2011478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return (0); 2012478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2013478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project slen = slength(p->stmts); 2014478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst = ftail -= (slen + 1 + p->longjt + p->longjf); 2015478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* inflate length by any extra jumps */ 2016478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2017478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->offset = dst - fstart; 2018478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2019478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* generate offset[] for convenience */ 2020478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (slen) { 2021478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project offset = (struct slist **)calloc(slen, sizeof(struct slist *)); 2022478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!offset) { 2023478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error("not enough core"); 2024478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /*NOTREACHED*/ 2025478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2026478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2027478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project src = p->stmts; 2028478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (off = 0; off < slen && src; off++) { 2029478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#if 0 2030478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project printf("off=%d src=%x\n", off, src); 2031478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 2032478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project offset[off] = src; 2033478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project src = src->next; 2034478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2035478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2036478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project off = 0; 2037478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (src = p->stmts; src; src = src->next) { 2038478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (src->s.code == NOP) 2039478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project continue; 2040478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst->code = (u_short)src->s.code; 2041478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst->k = src->s.k; 2042478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2043478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* fill block-local relative jump */ 2044478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (BPF_CLASS(src->s.code) != BPF_JMP || src->s.code == (BPF_JMP|BPF_JA)) { 2045478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#if 0 2046478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (src->s.jt || src->s.jf) { 2047478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error("illegal jmp destination"); 2048478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /*NOTREACHED*/ 2049478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2050478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 2051478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project goto filled; 2052478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2053478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (off == slen - 2) /*???*/ 2054478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project goto filled; 2055478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2056478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project { 2057478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int i; 2058478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project int jt, jf; 2059478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project const char *ljerr = "%s for block-local relative jump: off=%d"; 2060478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2061478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#if 0 2062478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project printf("code=%x off=%d %x %x\n", src->s.code, 2063478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project off, src->s.jt, src->s.jf); 2064478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 2065478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2066478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!src->s.jt || !src->s.jf) { 2067478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error(ljerr, "no jmp destination", off); 2068478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /*NOTREACHED*/ 2069478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2070478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2071478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project jt = jf = 0; 2072478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project for (i = 0; i < slen; i++) { 2073478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (offset[i] == src->s.jt) { 2074478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (jt) { 2075478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error(ljerr, "multiple matches", off); 2076478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /*NOTREACHED*/ 2077478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2078478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2079478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst->jt = i - off - 1; 2080478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project jt++; 2081478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2082478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (offset[i] == src->s.jf) { 2083478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (jf) { 2084478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error(ljerr, "multiple matches", off); 2085478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /*NOTREACHED*/ 2086478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2087478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst->jf = i - off - 1; 2088478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project jf++; 2089478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2090478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2091478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (!jt || !jf) { 2092478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error(ljerr, "no destination found", off); 2093478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /*NOTREACHED*/ 2094478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2095478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2096478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectfilled: 2097478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project ++dst; 2098478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project ++off; 2099478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2100478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (offset) 2101478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project free(offset); 2102478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2103478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef BDEBUG 2104478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bids[dst - fstart] = p->id + 1; 2105478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 2106478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst->code = (u_short)p->s.code; 2107478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst->k = p->s.k; 2108478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (JT(p)) { 2109478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project extrajmps = 0; 2110478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project off = JT(p)->offset - (p->offset + slen) - 1; 2111478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (off >= 256) { 2112478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* offset too large for branch, must add a jump */ 2113478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (p->longjt == 0) { 2114478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* mark this instruction and retry */ 2115478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->longjt++; 2116478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return(0); 2117478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2118478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* branch if T to following jump */ 2119478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst->jt = extrajmps; 2120478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project extrajmps++; 2121478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst[extrajmps].code = BPF_JMP|BPF_JA; 2122478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst[extrajmps].k = off - extrajmps; 2123478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2124478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 2125478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst->jt = off; 2126478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project off = JF(p)->offset - (p->offset + slen) - 1; 2127478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (off >= 256) { 2128478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* offset too large for branch, must add a jump */ 2129478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (p->longjf == 0) { 2130478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* mark this instruction and retry */ 2131478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->longjf++; 2132478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return(0); 2133478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2134478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* branch if F to following jump */ 2135478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* if two jumps are inserted, F goes to second one */ 2136478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst->jf = extrajmps; 2137478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project extrajmps++; 2138478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst[extrajmps].code = BPF_JMP|BPF_JA; 2139478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst[extrajmps].k = off - extrajmps; 2140478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2141478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project else 2142478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project dst->jf = off; 2143478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2144478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return (1); 2145478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 2146478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2147478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2148478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 2149478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Convert flowgraph intermediate representation to the 2150478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * BPF array representation. Set *lenp to the number of instructions. 2151478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 2152478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * This routine does *NOT* leak the memory pointed to by fp. It *must 2153478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * not* do free(fp) before returning fp; doing so would make no sense, 2154478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * as the BPF array pointed to by the return value of icode_to_fcode() 2155478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * must be valid - it's being returned for use in a bpf_program structure. 2156478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 2157478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * If it appears that icode_to_fcode() is leaking, the problem is that 2158478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * the program using pcap_compile() is failing to free the memory in 2159478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * the BPF program when it's done - the leak is in the program, not in 2160478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * the routine that happens to be allocating the memory. (By analogy, if 2161478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * a program calls fopen() without ever calling fclose() on the FILE *, 2162478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * it will leak the FILE structure; the leak is not in fopen(), it's in 2163478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * the program.) Change the program to use pcap_freecode() when it's 2164478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * done with the filter program. See the pcap man page. 2165478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 2166478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstruct bpf_insn * 2167511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallicode_to_fcode(struct block *root, u_int *lenp) 2168478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 2169511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall u_int n; 2170478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct bpf_insn *fp; 2171478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2172478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 2173478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Loop doing convert_code_r() until no branches remain 2174478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * with too-large offsets. 2175478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 2176478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project while (1) { 2177478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project unMarkAll(); 2178478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project n = *lenp = count_stmts(root); 2179478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2180478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project fp = (struct bpf_insn *)malloc(sizeof(*fp) * n); 2181478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (fp == NULL) 2182478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_error("malloc"); 2183478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memset((char *)fp, 0, sizeof(*fp) * n); 2184478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project fstart = fp; 2185478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project ftail = fp + n; 2186478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2187478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project unMarkAll(); 2188478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (convert_code_r(root)) 2189478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project break; 2190478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project free(fp); 2191478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2192478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2193478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return fp; 2194478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 2195478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2196478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project/* 2197478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Make a copy of a BPF program and put it in the "fcode" member of 2198478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * a "pcap_t". 2199478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * 2200478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * If we fail to allocate memory for the copy, fill in the "errbuf" 2201478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * member of the "pcap_t" with an error message, and return -1; 2202478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * otherwise, return 0. 2203478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 2204478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectint 2205478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectinstall_bpf_program(pcap_t *p, struct bpf_program *fp) 2206478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 2207478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project size_t prog_size; 2208478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2209478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project /* 2210511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall * Validate the program. 2211511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall */ 2212511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall if (!bpf_validate(fp->bf_insns, fp->bf_len)) { 2213511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall snprintf(p->errbuf, sizeof(p->errbuf), 2214511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall "BPF program is not valid"); 2215511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall return (-1); 2216511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall } 2217511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall 2218511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrall /* 2219478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project * Free up any already installed program. 2220478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project */ 2221478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project pcap_freecode(&p->fcode); 2222478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2223478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project prog_size = sizeof(*fp->bf_insns) * fp->bf_len; 2224478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->fcode.bf_len = fp->bf_len; 2225478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project p->fcode.bf_insns = (struct bpf_insn *)malloc(prog_size); 2226478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project if (p->fcode.bf_insns == NULL) { 2227478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project snprintf(p->errbuf, sizeof(p->errbuf), 2228478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project "malloc: %s", pcap_strerror(errno)); 2229478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return (-1); 2230478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project } 2231478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memcpy(p->fcode.bf_insns, fp->bf_insns, prog_size); 2232478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project return (0); 2233478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 2234478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2235478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#ifdef BDEBUG 2236478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Projectstatic void 2237511eca30a483e912c274e1d8ba3a0f8f081e2227JP Abgrallopt_dump(struct block *root) 2238478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project{ 2239478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project struct bpf_program f; 2240478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project 2241478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project memset(bids, 0, sizeof bids); 2242478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project f.bf_insns = icode_to_fcode(root, &f.bf_len); 2243478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project bpf_dump(&f, 1); 2244478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project putchar('\n'); 2245478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project free((char *)f.bf_insns); 2246478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project} 2247478ab6c8b5bc982589be32eae1e5736efe721b58The Android Open Source Project#endif 2248