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