1/* 2 * Copyright (c) 1988, 1989, 1990, 1991, 1993, 1994, 1995, 1996 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that: (1) source code distributions 7 * retain the above copyright notice and this paragraph in its entirety, (2) 8 * distributions including binary code include the above copyright notice and 9 * this paragraph in its entirety in the documentation or other materials 10 * provided with the distribution, and (3) all advertising materials mentioning 11 * features or use of this software display the following acknowledgement: 12 * ``This product includes software developed by the University of California, 13 * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of 14 * the University nor the names of its contributors may be used to endorse 15 * or promote products derived from this software without specific prior 16 * written permission. 17 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 18 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 19 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 20 * 21 * Optimization module for tcpdump intermediate representation. 22 */ 23 24#ifdef HAVE_CONFIG_H 25#include "config.h" 26#endif 27 28#ifdef WIN32 29#include <pcap-stdinc.h> 30#else /* WIN32 */ 31#if HAVE_INTTYPES_H 32#include <inttypes.h> 33#elif HAVE_STDINT_H 34#include <stdint.h> 35#endif 36#ifdef HAVE_SYS_BITYPES_H 37#include <sys/bitypes.h> 38#endif 39#include <sys/types.h> 40#endif /* WIN32 */ 41 42#include <stdio.h> 43#include <stdlib.h> 44#include <memory.h> 45#include <string.h> 46 47#include <errno.h> 48 49#include "pcap-int.h" 50 51#include "gencode.h" 52 53#ifdef HAVE_OS_PROTO_H 54#include "os-proto.h" 55#endif 56 57#ifdef BDEBUG 58extern int dflag; 59#endif 60 61#if defined(MSDOS) && !defined(__DJGPP__) 62extern int _w32_ffs (int mask); 63#define ffs _w32_ffs 64#endif 65 66#if defined(WIN32) && defined (_MSC_VER) 67int ffs(int mask); 68#endif 69 70/* 71 * Represents a deleted instruction. 72 */ 73#define NOP -1 74 75/* 76 * Register numbers for use-def values. 77 * 0 through BPF_MEMWORDS-1 represent the corresponding scratch memory 78 * location. A_ATOM is the accumulator and X_ATOM is the index 79 * register. 80 */ 81#define A_ATOM BPF_MEMWORDS 82#define X_ATOM (BPF_MEMWORDS+1) 83 84/* 85 * This define is used to represent *both* the accumulator and 86 * x register in use-def computations. 87 * Currently, the use-def code assumes only one definition per instruction. 88 */ 89#define AX_ATOM N_ATOMS 90 91/* 92 * A flag to indicate that further optimization is needed. 93 * Iterative passes are continued until a given pass yields no 94 * branch movement. 95 */ 96static int done; 97 98/* 99 * A block is marked if only if its mark equals the current mark. 100 * Rather than traverse the code array, marking each item, 'cur_mark' is 101 * incremented. This automatically makes each element unmarked. 102 */ 103static int cur_mark; 104#define isMarked(p) ((p)->mark == cur_mark) 105#define unMarkAll() cur_mark += 1 106#define Mark(p) ((p)->mark = cur_mark) 107 108static void opt_init(struct block *); 109static void opt_cleanup(void); 110 111static void intern_blocks(struct block *); 112 113static void find_inedges(struct block *); 114#ifdef BDEBUG 115static void opt_dump(struct block *); 116#endif 117 118static int n_blocks; 119struct block **blocks; 120static int n_edges; 121struct edge **edges; 122 123/* 124 * A bit vector set representation of the dominators. 125 * We round up the set size to the next power of two. 126 */ 127static int nodewords; 128static int edgewords; 129struct block **levels; 130bpf_u_int32 *space; 131#define BITS_PER_WORD (8*sizeof(bpf_u_int32)) 132/* 133 * True if a is in uset {p} 134 */ 135#define SET_MEMBER(p, a) \ 136((p)[(unsigned)(a) / BITS_PER_WORD] & (1 << ((unsigned)(a) % BITS_PER_WORD))) 137 138/* 139 * Add 'a' to uset p. 140 */ 141#define SET_INSERT(p, a) \ 142(p)[(unsigned)(a) / BITS_PER_WORD] |= (1 << ((unsigned)(a) % BITS_PER_WORD)) 143 144/* 145 * Delete 'a' from uset p. 146 */ 147#define SET_DELETE(p, a) \ 148(p)[(unsigned)(a) / BITS_PER_WORD] &= ~(1 << ((unsigned)(a) % BITS_PER_WORD)) 149 150/* 151 * a := a intersect b 152 */ 153#define SET_INTERSECT(a, b, n)\ 154{\ 155 register bpf_u_int32 *_x = a, *_y = b;\ 156 register int _n = n;\ 157 while (--_n >= 0) *_x++ &= *_y++;\ 158} 159 160/* 161 * a := a - b 162 */ 163#define SET_SUBTRACT(a, b, n)\ 164{\ 165 register bpf_u_int32 *_x = a, *_y = b;\ 166 register int _n = n;\ 167 while (--_n >= 0) *_x++ &=~ *_y++;\ 168} 169 170/* 171 * a := a union b 172 */ 173#define SET_UNION(a, b, n)\ 174{\ 175 register bpf_u_int32 *_x = a, *_y = b;\ 176 register int _n = n;\ 177 while (--_n >= 0) *_x++ |= *_y++;\ 178} 179 180static uset all_dom_sets; 181static uset all_closure_sets; 182static uset all_edge_sets; 183 184#ifndef MAX 185#define MAX(a,b) ((a)>(b)?(a):(b)) 186#endif 187 188static void 189find_levels_r(struct block *b) 190{ 191 int level; 192 193 if (isMarked(b)) 194 return; 195 196 Mark(b); 197 b->link = 0; 198 199 if (JT(b)) { 200 find_levels_r(JT(b)); 201 find_levels_r(JF(b)); 202 level = MAX(JT(b)->level, JF(b)->level) + 1; 203 } else 204 level = 0; 205 b->level = level; 206 b->link = levels[level]; 207 levels[level] = b; 208} 209 210/* 211 * Level graph. The levels go from 0 at the leaves to 212 * N_LEVELS at the root. The levels[] array points to the 213 * first node of the level list, whose elements are linked 214 * with the 'link' field of the struct block. 215 */ 216static void 217find_levels(struct block *root) 218{ 219 memset((char *)levels, 0, n_blocks * sizeof(*levels)); 220 unMarkAll(); 221 find_levels_r(root); 222} 223 224/* 225 * Find dominator relationships. 226 * Assumes graph has been leveled. 227 */ 228static void 229find_dom(struct block *root) 230{ 231 int i; 232 struct block *b; 233 bpf_u_int32 *x; 234 235 /* 236 * Initialize sets to contain all nodes. 237 */ 238 x = all_dom_sets; 239 i = n_blocks * nodewords; 240 while (--i >= 0) 241 *x++ = ~0; 242 /* Root starts off empty. */ 243 for (i = nodewords; --i >= 0;) 244 root->dom[i] = 0; 245 246 /* root->level is the highest level no found. */ 247 for (i = root->level; i >= 0; --i) { 248 for (b = levels[i]; b; b = b->link) { 249 SET_INSERT(b->dom, b->id); 250 if (JT(b) == 0) 251 continue; 252 SET_INTERSECT(JT(b)->dom, b->dom, nodewords); 253 SET_INTERSECT(JF(b)->dom, b->dom, nodewords); 254 } 255 } 256} 257 258static void 259propedom(struct edge *ep) 260{ 261 SET_INSERT(ep->edom, ep->id); 262 if (ep->succ) { 263 SET_INTERSECT(ep->succ->et.edom, ep->edom, edgewords); 264 SET_INTERSECT(ep->succ->ef.edom, ep->edom, edgewords); 265 } 266} 267 268/* 269 * Compute edge dominators. 270 * Assumes graph has been leveled and predecessors established. 271 */ 272static void 273find_edom(struct block *root) 274{ 275 int i; 276 uset x; 277 struct block *b; 278 279 x = all_edge_sets; 280 for (i = n_edges * edgewords; --i >= 0; ) 281 x[i] = ~0; 282 283 /* root->level is the highest level no found. */ 284 memset(root->et.edom, 0, edgewords * sizeof(*(uset)0)); 285 memset(root->ef.edom, 0, edgewords * sizeof(*(uset)0)); 286 for (i = root->level; i >= 0; --i) { 287 for (b = levels[i]; b != 0; b = b->link) { 288 propedom(&b->et); 289 propedom(&b->ef); 290 } 291 } 292} 293 294/* 295 * Find the backwards transitive closure of the flow graph. These sets 296 * are backwards in the sense that we find the set of nodes that reach 297 * a given node, not the set of nodes that can be reached by a node. 298 * 299 * Assumes graph has been leveled. 300 */ 301static void 302find_closure(struct block *root) 303{ 304 int i; 305 struct block *b; 306 307 /* 308 * Initialize sets to contain no nodes. 309 */ 310 memset((char *)all_closure_sets, 0, 311 n_blocks * nodewords * sizeof(*all_closure_sets)); 312 313 /* root->level is the highest level no found. */ 314 for (i = root->level; i >= 0; --i) { 315 for (b = levels[i]; b; b = b->link) { 316 SET_INSERT(b->closure, b->id); 317 if (JT(b) == 0) 318 continue; 319 SET_UNION(JT(b)->closure, b->closure, nodewords); 320 SET_UNION(JF(b)->closure, b->closure, nodewords); 321 } 322 } 323} 324 325/* 326 * Return the register number that is used by s. If A and X are both 327 * used, return AX_ATOM. If no register is used, return -1. 328 * 329 * The implementation should probably change to an array access. 330 */ 331static int 332atomuse(struct stmt *s) 333{ 334 register int c = s->code; 335 336 if (c == NOP) 337 return -1; 338 339 switch (BPF_CLASS(c)) { 340 341 case BPF_RET: 342 return (BPF_RVAL(c) == BPF_A) ? A_ATOM : 343 (BPF_RVAL(c) == BPF_X) ? X_ATOM : -1; 344 345 case BPF_LD: 346 case BPF_LDX: 347 return (BPF_MODE(c) == BPF_IND) ? X_ATOM : 348 (BPF_MODE(c) == BPF_MEM) ? s->k : -1; 349 350 case BPF_ST: 351 return A_ATOM; 352 353 case BPF_STX: 354 return X_ATOM; 355 356 case BPF_JMP: 357 case BPF_ALU: 358 if (BPF_SRC(c) == BPF_X) 359 return AX_ATOM; 360 return A_ATOM; 361 362 case BPF_MISC: 363 return BPF_MISCOP(c) == BPF_TXA ? X_ATOM : A_ATOM; 364 } 365 abort(); 366 /* NOTREACHED */ 367} 368 369/* 370 * Return the register number that is defined by 's'. We assume that 371 * a single stmt cannot define more than one register. If no register 372 * is defined, return -1. 373 * 374 * The implementation should probably change to an array access. 375 */ 376static int 377atomdef(struct stmt *s) 378{ 379 if (s->code == NOP) 380 return -1; 381 382 switch (BPF_CLASS(s->code)) { 383 384 case BPF_LD: 385 case BPF_ALU: 386 return A_ATOM; 387 388 case BPF_LDX: 389 return X_ATOM; 390 391 case BPF_ST: 392 case BPF_STX: 393 return s->k; 394 395 case BPF_MISC: 396 return BPF_MISCOP(s->code) == BPF_TAX ? X_ATOM : A_ATOM; 397 } 398 return -1; 399} 400 401/* 402 * Compute the sets of registers used, defined, and killed by 'b'. 403 * 404 * "Used" means that a statement in 'b' uses the register before any 405 * statement in 'b' defines it, i.e. it uses the value left in 406 * that register by a predecessor block of this block. 407 * "Defined" means that a statement in 'b' defines it. 408 * "Killed" means that a statement in 'b' defines it before any 409 * statement in 'b' uses it, i.e. it kills the value left in that 410 * register by a predecessor block of this block. 411 */ 412static void 413compute_local_ud(struct block *b) 414{ 415 struct slist *s; 416 atomset def = 0, use = 0, kill = 0; 417 int atom; 418 419 for (s = b->stmts; s; s = s->next) { 420 if (s->s.code == NOP) 421 continue; 422 atom = atomuse(&s->s); 423 if (atom >= 0) { 424 if (atom == AX_ATOM) { 425 if (!ATOMELEM(def, X_ATOM)) 426 use |= ATOMMASK(X_ATOM); 427 if (!ATOMELEM(def, A_ATOM)) 428 use |= ATOMMASK(A_ATOM); 429 } 430 else if (atom < N_ATOMS) { 431 if (!ATOMELEM(def, atom)) 432 use |= ATOMMASK(atom); 433 } 434 else 435 abort(); 436 } 437 atom = atomdef(&s->s); 438 if (atom >= 0) { 439 if (!ATOMELEM(use, atom)) 440 kill |= ATOMMASK(atom); 441 def |= ATOMMASK(atom); 442 } 443 } 444 if (BPF_CLASS(b->s.code) == BPF_JMP) { 445 /* 446 * XXX - what about RET? 447 */ 448 atom = atomuse(&b->s); 449 if (atom >= 0) { 450 if (atom == AX_ATOM) { 451 if (!ATOMELEM(def, X_ATOM)) 452 use |= ATOMMASK(X_ATOM); 453 if (!ATOMELEM(def, A_ATOM)) 454 use |= ATOMMASK(A_ATOM); 455 } 456 else if (atom < N_ATOMS) { 457 if (!ATOMELEM(def, atom)) 458 use |= ATOMMASK(atom); 459 } 460 else 461 abort(); 462 } 463 } 464 465 b->def = def; 466 b->kill = kill; 467 b->in_use = use; 468} 469 470/* 471 * Assume graph is already leveled. 472 */ 473static void 474find_ud(struct block *root) 475{ 476 int i, maxlevel; 477 struct block *p; 478 479 /* 480 * root->level is the highest level no found; 481 * count down from there. 482 */ 483 maxlevel = root->level; 484 for (i = maxlevel; i >= 0; --i) 485 for (p = levels[i]; p; p = p->link) { 486 compute_local_ud(p); 487 p->out_use = 0; 488 } 489 490 for (i = 1; i <= maxlevel; ++i) { 491 for (p = levels[i]; p; p = p->link) { 492 p->out_use |= JT(p)->in_use | JF(p)->in_use; 493 p->in_use |= p->out_use &~ p->kill; 494 } 495 } 496} 497 498/* 499 * These data structures are used in a Cocke and Shwarz style 500 * value numbering scheme. Since the flowgraph is acyclic, 501 * exit values can be propagated from a node's predecessors 502 * provided it is uniquely defined. 503 */ 504struct valnode { 505 int code; 506 int v0, v1; 507 int val; 508 struct valnode *next; 509}; 510 511#define MODULUS 213 512static struct valnode *hashtbl[MODULUS]; 513static int curval; 514static int maxval; 515 516/* Integer constants mapped with the load immediate opcode. */ 517#define K(i) F(BPF_LD|BPF_IMM|BPF_W, i, 0L) 518 519struct vmapinfo { 520 int is_const; 521 bpf_int32 const_val; 522}; 523 524struct vmapinfo *vmap; 525struct valnode *vnode_base; 526struct valnode *next_vnode; 527 528static void 529init_val(void) 530{ 531 curval = 0; 532 next_vnode = vnode_base; 533 memset((char *)vmap, 0, maxval * sizeof(*vmap)); 534 memset((char *)hashtbl, 0, sizeof hashtbl); 535} 536 537/* Because we really don't have an IR, this stuff is a little messy. */ 538static int 539F(int code, int v0, int v1) 540{ 541 u_int hash; 542 int val; 543 struct valnode *p; 544 545 hash = (u_int)code ^ (v0 << 4) ^ (v1 << 8); 546 hash %= MODULUS; 547 548 for (p = hashtbl[hash]; p; p = p->next) 549 if (p->code == code && p->v0 == v0 && p->v1 == v1) 550 return p->val; 551 552 val = ++curval; 553 if (BPF_MODE(code) == BPF_IMM && 554 (BPF_CLASS(code) == BPF_LD || BPF_CLASS(code) == BPF_LDX)) { 555 vmap[val].const_val = v0; 556 vmap[val].is_const = 1; 557 } 558 p = next_vnode++; 559 p->val = val; 560 p->code = code; 561 p->v0 = v0; 562 p->v1 = v1; 563 p->next = hashtbl[hash]; 564 hashtbl[hash] = p; 565 566 return val; 567} 568 569static inline void 570vstore(struct stmt *s, int *valp, int newval, int alter) 571{ 572 if (alter && *valp == newval) 573 s->code = NOP; 574 else 575 *valp = newval; 576} 577 578/* 579 * Do constant-folding on binary operators. 580 * (Unary operators are handled elsewhere.) 581 */ 582static void 583fold_op(struct stmt *s, int v0, int v1) 584{ 585 bpf_u_int32 a, b; 586 587 a = vmap[v0].const_val; 588 b = vmap[v1].const_val; 589 590 switch (BPF_OP(s->code)) { 591 case BPF_ADD: 592 a += b; 593 break; 594 595 case BPF_SUB: 596 a -= b; 597 break; 598 599 case BPF_MUL: 600 a *= b; 601 break; 602 603 case BPF_DIV: 604 if (b == 0) 605 bpf_error("division by zero"); 606 a /= b; 607 break; 608 609 case BPF_MOD: 610 if (b == 0) 611 bpf_error("modulus by zero"); 612 a %= b; 613 break; 614 615 case BPF_AND: 616 a &= b; 617 break; 618 619 case BPF_OR: 620 a |= b; 621 break; 622 623 case BPF_XOR: 624 a ^= b; 625 break; 626 627 case BPF_LSH: 628 a <<= b; 629 break; 630 631 case BPF_RSH: 632 a >>= b; 633 break; 634 635 default: 636 abort(); 637 } 638 s->k = a; 639 s->code = BPF_LD|BPF_IMM; 640 done = 0; 641} 642 643static inline struct slist * 644this_op(struct slist *s) 645{ 646 while (s != 0 && s->s.code == NOP) 647 s = s->next; 648 return s; 649} 650 651static void 652opt_not(struct block *b) 653{ 654 struct block *tmp = JT(b); 655 656 JT(b) = JF(b); 657 JF(b) = tmp; 658} 659 660static void 661opt_peep(struct block *b) 662{ 663 struct slist *s; 664 struct slist *next, *last; 665 int val; 666 667 s = b->stmts; 668 if (s == 0) 669 return; 670 671 last = s; 672 for (/*empty*/; /*empty*/; s = next) { 673 /* 674 * Skip over nops. 675 */ 676 s = this_op(s); 677 if (s == 0) 678 break; /* nothing left in the block */ 679 680 /* 681 * Find the next real instruction after that one 682 * (skipping nops). 683 */ 684 next = this_op(s->next); 685 if (next == 0) 686 break; /* no next instruction */ 687 last = next; 688 689 /* 690 * st M[k] --> st M[k] 691 * ldx M[k] tax 692 */ 693 if (s->s.code == BPF_ST && 694 next->s.code == (BPF_LDX|BPF_MEM) && 695 s->s.k == next->s.k) { 696 done = 0; 697 next->s.code = BPF_MISC|BPF_TAX; 698 } 699 /* 700 * ld #k --> ldx #k 701 * tax txa 702 */ 703 if (s->s.code == (BPF_LD|BPF_IMM) && 704 next->s.code == (BPF_MISC|BPF_TAX)) { 705 s->s.code = BPF_LDX|BPF_IMM; 706 next->s.code = BPF_MISC|BPF_TXA; 707 done = 0; 708 } 709 /* 710 * This is an ugly special case, but it happens 711 * when you say tcp[k] or udp[k] where k is a constant. 712 */ 713 if (s->s.code == (BPF_LD|BPF_IMM)) { 714 struct slist *add, *tax, *ild; 715 716 /* 717 * Check that X isn't used on exit from this 718 * block (which the optimizer might cause). 719 * We know the code generator won't generate 720 * any local dependencies. 721 */ 722 if (ATOMELEM(b->out_use, X_ATOM)) 723 continue; 724 725 /* 726 * Check that the instruction following the ldi 727 * is an addx, or it's an ldxms with an addx 728 * following it (with 0 or more nops between the 729 * ldxms and addx). 730 */ 731 if (next->s.code != (BPF_LDX|BPF_MSH|BPF_B)) 732 add = next; 733 else 734 add = this_op(next->next); 735 if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X)) 736 continue; 737 738 /* 739 * Check that a tax follows that (with 0 or more 740 * nops between them). 741 */ 742 tax = this_op(add->next); 743 if (tax == 0 || tax->s.code != (BPF_MISC|BPF_TAX)) 744 continue; 745 746 /* 747 * Check that an ild follows that (with 0 or more 748 * nops between them). 749 */ 750 ild = this_op(tax->next); 751 if (ild == 0 || BPF_CLASS(ild->s.code) != BPF_LD || 752 BPF_MODE(ild->s.code) != BPF_IND) 753 continue; 754 /* 755 * We want to turn this sequence: 756 * 757 * (004) ldi #0x2 {s} 758 * (005) ldxms [14] {next} -- optional 759 * (006) addx {add} 760 * (007) tax {tax} 761 * (008) ild [x+0] {ild} 762 * 763 * into this sequence: 764 * 765 * (004) nop 766 * (005) ldxms [14] 767 * (006) nop 768 * (007) nop 769 * (008) ild [x+2] 770 * 771 * XXX We need to check that X is not 772 * subsequently used, because we want to change 773 * what'll be in it after this sequence. 774 * 775 * We know we can eliminate the accumulator 776 * modifications earlier in the sequence since 777 * it is defined by the last stmt of this sequence 778 * (i.e., the last statement of the sequence loads 779 * a value into the accumulator, so we can eliminate 780 * earlier operations on the accumulator). 781 */ 782 ild->s.k += s->s.k; 783 s->s.code = NOP; 784 add->s.code = NOP; 785 tax->s.code = NOP; 786 done = 0; 787 } 788 } 789 /* 790 * If the comparison at the end of a block is an equality 791 * comparison against a constant, and nobody uses the value 792 * we leave in the A register at the end of a block, and 793 * the operation preceding the comparison is an arithmetic 794 * operation, we can sometime optimize it away. 795 */ 796 if (b->s.code == (BPF_JMP|BPF_JEQ|BPF_K) && 797 !ATOMELEM(b->out_use, A_ATOM)) { 798 /* 799 * We can optimize away certain subtractions of the 800 * X register. 801 */ 802 if (last->s.code == (BPF_ALU|BPF_SUB|BPF_X)) { 803 val = b->val[X_ATOM]; 804 if (vmap[val].is_const) { 805 /* 806 * If we have a subtract to do a comparison, 807 * and the X register is a known constant, 808 * we can merge this value into the 809 * comparison: 810 * 811 * sub x -> nop 812 * jeq #y jeq #(x+y) 813 */ 814 b->s.k += vmap[val].const_val; 815 last->s.code = NOP; 816 done = 0; 817 } else if (b->s.k == 0) { 818 /* 819 * If the X register isn't a constant, 820 * and the comparison in the test is 821 * against 0, we can compare with the 822 * X register, instead: 823 * 824 * sub x -> nop 825 * jeq #0 jeq x 826 */ 827 last->s.code = NOP; 828 b->s.code = BPF_JMP|BPF_JEQ|BPF_X; 829 done = 0; 830 } 831 } 832 /* 833 * Likewise, a constant subtract can be simplified: 834 * 835 * sub #x -> nop 836 * jeq #y -> jeq #(x+y) 837 */ 838 else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K)) { 839 last->s.code = NOP; 840 b->s.k += last->s.k; 841 done = 0; 842 } 843 /* 844 * And, similarly, a constant AND can be simplified 845 * if we're testing against 0, i.e.: 846 * 847 * and #k nop 848 * jeq #0 -> jset #k 849 */ 850 else if (last->s.code == (BPF_ALU|BPF_AND|BPF_K) && 851 b->s.k == 0) { 852 b->s.k = last->s.k; 853 b->s.code = BPF_JMP|BPF_K|BPF_JSET; 854 last->s.code = NOP; 855 done = 0; 856 opt_not(b); 857 } 858 } 859 /* 860 * jset #0 -> never 861 * jset #ffffffff -> always 862 */ 863 if (b->s.code == (BPF_JMP|BPF_K|BPF_JSET)) { 864 if (b->s.k == 0) 865 JT(b) = JF(b); 866 if (b->s.k == 0xffffffff) 867 JF(b) = JT(b); 868 } 869 /* 870 * If we're comparing against the index register, and the index 871 * register is a known constant, we can just compare against that 872 * constant. 873 */ 874 val = b->val[X_ATOM]; 875 if (vmap[val].is_const && BPF_SRC(b->s.code) == BPF_X) { 876 bpf_int32 v = vmap[val].const_val; 877 b->s.code &= ~BPF_X; 878 b->s.k = v; 879 } 880 /* 881 * If the accumulator is a known constant, we can compute the 882 * comparison result. 883 */ 884 val = b->val[A_ATOM]; 885 if (vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) { 886 bpf_int32 v = vmap[val].const_val; 887 switch (BPF_OP(b->s.code)) { 888 889 case BPF_JEQ: 890 v = v == b->s.k; 891 break; 892 893 case BPF_JGT: 894 v = (unsigned)v > b->s.k; 895 break; 896 897 case BPF_JGE: 898 v = (unsigned)v >= b->s.k; 899 break; 900 901 case BPF_JSET: 902 v &= b->s.k; 903 break; 904 905 default: 906 abort(); 907 } 908 if (JF(b) != JT(b)) 909 done = 0; 910 if (v) 911 JF(b) = JT(b); 912 else 913 JT(b) = JF(b); 914 } 915} 916 917/* 918 * Compute the symbolic value of expression of 's', and update 919 * anything it defines in the value table 'val'. If 'alter' is true, 920 * do various optimizations. This code would be cleaner if symbolic 921 * evaluation and code transformations weren't folded together. 922 */ 923static void 924opt_stmt(struct stmt *s, int val[], int alter) 925{ 926 int op; 927 int v; 928 929 switch (s->code) { 930 931 case BPF_LD|BPF_ABS|BPF_W: 932 case BPF_LD|BPF_ABS|BPF_H: 933 case BPF_LD|BPF_ABS|BPF_B: 934 v = F(s->code, s->k, 0L); 935 vstore(s, &val[A_ATOM], v, alter); 936 break; 937 938 case BPF_LD|BPF_IND|BPF_W: 939 case BPF_LD|BPF_IND|BPF_H: 940 case BPF_LD|BPF_IND|BPF_B: 941 v = val[X_ATOM]; 942 if (alter && vmap[v].is_const) { 943 s->code = BPF_LD|BPF_ABS|BPF_SIZE(s->code); 944 s->k += vmap[v].const_val; 945 v = F(s->code, s->k, 0L); 946 done = 0; 947 } 948 else 949 v = F(s->code, s->k, v); 950 vstore(s, &val[A_ATOM], v, alter); 951 break; 952 953 case BPF_LD|BPF_LEN: 954 v = F(s->code, 0L, 0L); 955 vstore(s, &val[A_ATOM], v, alter); 956 break; 957 958 case BPF_LD|BPF_IMM: 959 v = K(s->k); 960 vstore(s, &val[A_ATOM], v, alter); 961 break; 962 963 case BPF_LDX|BPF_IMM: 964 v = K(s->k); 965 vstore(s, &val[X_ATOM], v, alter); 966 break; 967 968 case BPF_LDX|BPF_MSH|BPF_B: 969 v = F(s->code, s->k, 0L); 970 vstore(s, &val[X_ATOM], v, alter); 971 break; 972 973 case BPF_ALU|BPF_NEG: 974 if (alter && vmap[val[A_ATOM]].is_const) { 975 s->code = BPF_LD|BPF_IMM; 976 s->k = -vmap[val[A_ATOM]].const_val; 977 val[A_ATOM] = K(s->k); 978 } 979 else 980 val[A_ATOM] = F(s->code, val[A_ATOM], 0L); 981 break; 982 983 case BPF_ALU|BPF_ADD|BPF_K: 984 case BPF_ALU|BPF_SUB|BPF_K: 985 case BPF_ALU|BPF_MUL|BPF_K: 986 case BPF_ALU|BPF_DIV|BPF_K: 987 case BPF_ALU|BPF_MOD|BPF_K: 988 case BPF_ALU|BPF_AND|BPF_K: 989 case BPF_ALU|BPF_OR|BPF_K: 990 case BPF_ALU|BPF_XOR|BPF_K: 991 case BPF_ALU|BPF_LSH|BPF_K: 992 case BPF_ALU|BPF_RSH|BPF_K: 993 op = BPF_OP(s->code); 994 if (alter) { 995 if (s->k == 0) { 996 /* don't optimize away "sub #0" 997 * as it may be needed later to 998 * fixup the generated math code */ 999 if (op == BPF_ADD || 1000 op == BPF_LSH || op == BPF_RSH || 1001 op == BPF_OR || op == BPF_XOR) { 1002 s->code = NOP; 1003 break; 1004 } 1005 if (op == BPF_MUL || op == BPF_AND) { 1006 s->code = BPF_LD|BPF_IMM; 1007 val[A_ATOM] = K(s->k); 1008 break; 1009 } 1010 } 1011 if (vmap[val[A_ATOM]].is_const) { 1012 fold_op(s, val[A_ATOM], K(s->k)); 1013 val[A_ATOM] = K(s->k); 1014 break; 1015 } 1016 } 1017 val[A_ATOM] = F(s->code, val[A_ATOM], K(s->k)); 1018 break; 1019 1020 case BPF_ALU|BPF_ADD|BPF_X: 1021 case BPF_ALU|BPF_SUB|BPF_X: 1022 case BPF_ALU|BPF_MUL|BPF_X: 1023 case BPF_ALU|BPF_DIV|BPF_X: 1024 case BPF_ALU|BPF_MOD|BPF_X: 1025 case BPF_ALU|BPF_AND|BPF_X: 1026 case BPF_ALU|BPF_OR|BPF_X: 1027 case BPF_ALU|BPF_XOR|BPF_X: 1028 case BPF_ALU|BPF_LSH|BPF_X: 1029 case BPF_ALU|BPF_RSH|BPF_X: 1030 op = BPF_OP(s->code); 1031 if (alter && vmap[val[X_ATOM]].is_const) { 1032 if (vmap[val[A_ATOM]].is_const) { 1033 fold_op(s, val[A_ATOM], val[X_ATOM]); 1034 val[A_ATOM] = K(s->k); 1035 } 1036 else { 1037 s->code = BPF_ALU|BPF_K|op; 1038 s->k = vmap[val[X_ATOM]].const_val; 1039 done = 0; 1040 val[A_ATOM] = 1041 F(s->code, val[A_ATOM], K(s->k)); 1042 } 1043 break; 1044 } 1045 /* 1046 * Check if we're doing something to an accumulator 1047 * that is 0, and simplify. This may not seem like 1048 * much of a simplification but it could open up further 1049 * optimizations. 1050 * XXX We could also check for mul by 1, etc. 1051 */ 1052 if (alter && vmap[val[A_ATOM]].is_const 1053 && vmap[val[A_ATOM]].const_val == 0) { 1054 if (op == BPF_ADD || op == BPF_OR || op == BPF_XOR) { 1055 s->code = BPF_MISC|BPF_TXA; 1056 vstore(s, &val[A_ATOM], val[X_ATOM], alter); 1057 break; 1058 } 1059 else if (op == BPF_MUL || op == BPF_DIV || op == BPF_MOD || 1060 op == BPF_AND || op == BPF_LSH || op == BPF_RSH) { 1061 s->code = BPF_LD|BPF_IMM; 1062 s->k = 0; 1063 vstore(s, &val[A_ATOM], K(s->k), alter); 1064 break; 1065 } 1066 else if (op == BPF_NEG) { 1067 s->code = NOP; 1068 break; 1069 } 1070 } 1071 val[A_ATOM] = F(s->code, val[A_ATOM], val[X_ATOM]); 1072 break; 1073 1074 case BPF_MISC|BPF_TXA: 1075 vstore(s, &val[A_ATOM], val[X_ATOM], alter); 1076 break; 1077 1078 case BPF_LD|BPF_MEM: 1079 v = val[s->k]; 1080 if (alter && vmap[v].is_const) { 1081 s->code = BPF_LD|BPF_IMM; 1082 s->k = vmap[v].const_val; 1083 done = 0; 1084 } 1085 vstore(s, &val[A_ATOM], v, alter); 1086 break; 1087 1088 case BPF_MISC|BPF_TAX: 1089 vstore(s, &val[X_ATOM], val[A_ATOM], alter); 1090 break; 1091 1092 case BPF_LDX|BPF_MEM: 1093 v = val[s->k]; 1094 if (alter && vmap[v].is_const) { 1095 s->code = BPF_LDX|BPF_IMM; 1096 s->k = vmap[v].const_val; 1097 done = 0; 1098 } 1099 vstore(s, &val[X_ATOM], v, alter); 1100 break; 1101 1102 case BPF_ST: 1103 vstore(s, &val[s->k], val[A_ATOM], alter); 1104 break; 1105 1106 case BPF_STX: 1107 vstore(s, &val[s->k], val[X_ATOM], alter); 1108 break; 1109 } 1110} 1111 1112static void 1113deadstmt(register struct stmt *s, register struct stmt *last[]) 1114{ 1115 register int atom; 1116 1117 atom = atomuse(s); 1118 if (atom >= 0) { 1119 if (atom == AX_ATOM) { 1120 last[X_ATOM] = 0; 1121 last[A_ATOM] = 0; 1122 } 1123 else 1124 last[atom] = 0; 1125 } 1126 atom = atomdef(s); 1127 if (atom >= 0) { 1128 if (last[atom]) { 1129 done = 0; 1130 last[atom]->code = NOP; 1131 } 1132 last[atom] = s; 1133 } 1134} 1135 1136static void 1137opt_deadstores(register struct block *b) 1138{ 1139 register struct slist *s; 1140 register int atom; 1141 struct stmt *last[N_ATOMS]; 1142 1143 memset((char *)last, 0, sizeof last); 1144 1145 for (s = b->stmts; s != 0; s = s->next) 1146 deadstmt(&s->s, last); 1147 deadstmt(&b->s, last); 1148 1149 for (atom = 0; atom < N_ATOMS; ++atom) 1150 if (last[atom] && !ATOMELEM(b->out_use, atom)) { 1151 last[atom]->code = NOP; 1152 done = 0; 1153 } 1154} 1155 1156static void 1157opt_blk(struct block *b, int do_stmts) 1158{ 1159 struct slist *s; 1160 struct edge *p; 1161 int i; 1162 bpf_int32 aval, xval; 1163 1164#if 0 1165 for (s = b->stmts; s && s->next; s = s->next) 1166 if (BPF_CLASS(s->s.code) == BPF_JMP) { 1167 do_stmts = 0; 1168 break; 1169 } 1170#endif 1171 1172 /* 1173 * Initialize the atom values. 1174 */ 1175 p = b->in_edges; 1176 if (p == 0) { 1177 /* 1178 * We have no predecessors, so everything is undefined 1179 * upon entry to this block. 1180 */ 1181 memset((char *)b->val, 0, sizeof(b->val)); 1182 } else { 1183 /* 1184 * Inherit values from our predecessors. 1185 * 1186 * First, get the values from the predecessor along the 1187 * first edge leading to this node. 1188 */ 1189 memcpy((char *)b->val, (char *)p->pred->val, sizeof(b->val)); 1190 /* 1191 * Now look at all the other nodes leading to this node. 1192 * If, for the predecessor along that edge, a register 1193 * has a different value from the one we have (i.e., 1194 * control paths are merging, and the merging paths 1195 * assign different values to that register), give the 1196 * register the undefined value of 0. 1197 */ 1198 while ((p = p->next) != NULL) { 1199 for (i = 0; i < N_ATOMS; ++i) 1200 if (b->val[i] != p->pred->val[i]) 1201 b->val[i] = 0; 1202 } 1203 } 1204 aval = b->val[A_ATOM]; 1205 xval = b->val[X_ATOM]; 1206 for (s = b->stmts; s; s = s->next) 1207 opt_stmt(&s->s, b->val, do_stmts); 1208 1209 /* 1210 * This is a special case: if we don't use anything from this 1211 * block, and we load the accumulator or index register with a 1212 * value that is already there, or if this block is a return, 1213 * eliminate all the statements. 1214 * 1215 * XXX - what if it does a store? 1216 * 1217 * XXX - why does it matter whether we use anything from this 1218 * block? If the accumulator or index register doesn't change 1219 * its value, isn't that OK even if we use that value? 1220 * 1221 * XXX - if we load the accumulator with a different value, 1222 * and the block ends with a conditional branch, we obviously 1223 * can't eliminate it, as the branch depends on that value. 1224 * For the index register, the conditional branch only depends 1225 * on the index register value if the test is against the index 1226 * register value rather than a constant; if nothing uses the 1227 * value we put into the index register, and we're not testing 1228 * against the index register's value, and there aren't any 1229 * other problems that would keep us from eliminating this 1230 * block, can we eliminate it? 1231 */ 1232 if (do_stmts && 1233 ((b->out_use == 0 && aval != 0 && b->val[A_ATOM] == aval && 1234 xval != 0 && b->val[X_ATOM] == xval) || 1235 BPF_CLASS(b->s.code) == BPF_RET)) { 1236 if (b->stmts != 0) { 1237 b->stmts = 0; 1238 done = 0; 1239 } 1240 } else { 1241 opt_peep(b); 1242 opt_deadstores(b); 1243 } 1244 /* 1245 * Set up values for branch optimizer. 1246 */ 1247 if (BPF_SRC(b->s.code) == BPF_K) 1248 b->oval = K(b->s.k); 1249 else 1250 b->oval = b->val[X_ATOM]; 1251 b->et.code = b->s.code; 1252 b->ef.code = -b->s.code; 1253} 1254 1255/* 1256 * Return true if any register that is used on exit from 'succ', has 1257 * an exit value that is different from the corresponding exit value 1258 * from 'b'. 1259 */ 1260static int 1261use_conflict(struct block *b, struct block *succ) 1262{ 1263 int atom; 1264 atomset use = succ->out_use; 1265 1266 if (use == 0) 1267 return 0; 1268 1269 for (atom = 0; atom < N_ATOMS; ++atom) 1270 if (ATOMELEM(use, atom)) 1271 if (b->val[atom] != succ->val[atom]) 1272 return 1; 1273 return 0; 1274} 1275 1276static struct block * 1277fold_edge(struct block *child, struct edge *ep) 1278{ 1279 int sense; 1280 int aval0, aval1, oval0, oval1; 1281 int code = ep->code; 1282 1283 if (code < 0) { 1284 code = -code; 1285 sense = 0; 1286 } else 1287 sense = 1; 1288 1289 if (child->s.code != code) 1290 return 0; 1291 1292 aval0 = child->val[A_ATOM]; 1293 oval0 = child->oval; 1294 aval1 = ep->pred->val[A_ATOM]; 1295 oval1 = ep->pred->oval; 1296 1297 if (aval0 != aval1) 1298 return 0; 1299 1300 if (oval0 == oval1) 1301 /* 1302 * The operands of the branch instructions are 1303 * identical, so the result is true if a true 1304 * branch was taken to get here, otherwise false. 1305 */ 1306 return sense ? JT(child) : JF(child); 1307 1308 if (sense && code == (BPF_JMP|BPF_JEQ|BPF_K)) 1309 /* 1310 * At this point, we only know the comparison if we 1311 * came down the true branch, and it was an equality 1312 * comparison with a constant. 1313 * 1314 * I.e., if we came down the true branch, and the branch 1315 * was an equality comparison with a constant, we know the 1316 * accumulator contains that constant. If we came down 1317 * the false branch, or the comparison wasn't with a 1318 * constant, we don't know what was in the accumulator. 1319 * 1320 * We rely on the fact that distinct constants have distinct 1321 * value numbers. 1322 */ 1323 return JF(child); 1324 1325 return 0; 1326} 1327 1328static void 1329opt_j(struct edge *ep) 1330{ 1331 register int i, k; 1332 register struct block *target; 1333 1334 if (JT(ep->succ) == 0) 1335 return; 1336 1337 if (JT(ep->succ) == JF(ep->succ)) { 1338 /* 1339 * Common branch targets can be eliminated, provided 1340 * there is no data dependency. 1341 */ 1342 if (!use_conflict(ep->pred, ep->succ->et.succ)) { 1343 done = 0; 1344 ep->succ = JT(ep->succ); 1345 } 1346 } 1347 /* 1348 * For each edge dominator that matches the successor of this 1349 * edge, promote the edge successor to the its grandchild. 1350 * 1351 * XXX We violate the set abstraction here in favor a reasonably 1352 * efficient loop. 1353 */ 1354 top: 1355 for (i = 0; i < edgewords; ++i) { 1356 register bpf_u_int32 x = ep->edom[i]; 1357 1358 while (x != 0) { 1359 k = ffs(x) - 1; 1360 x &=~ (1 << k); 1361 k += i * BITS_PER_WORD; 1362 1363 target = fold_edge(ep->succ, edges[k]); 1364 /* 1365 * Check that there is no data dependency between 1366 * nodes that will be violated if we move the edge. 1367 */ 1368 if (target != 0 && !use_conflict(ep->pred, target)) { 1369 done = 0; 1370 ep->succ = target; 1371 if (JT(target) != 0) 1372 /* 1373 * Start over unless we hit a leaf. 1374 */ 1375 goto top; 1376 return; 1377 } 1378 } 1379 } 1380} 1381 1382 1383static void 1384or_pullup(struct block *b) 1385{ 1386 int val, at_top; 1387 struct block *pull; 1388 struct block **diffp, **samep; 1389 struct edge *ep; 1390 1391 ep = b->in_edges; 1392 if (ep == 0) 1393 return; 1394 1395 /* 1396 * Make sure each predecessor loads the same value. 1397 * XXX why? 1398 */ 1399 val = ep->pred->val[A_ATOM]; 1400 for (ep = ep->next; ep != 0; ep = ep->next) 1401 if (val != ep->pred->val[A_ATOM]) 1402 return; 1403 1404 if (JT(b->in_edges->pred) == b) 1405 diffp = &JT(b->in_edges->pred); 1406 else 1407 diffp = &JF(b->in_edges->pred); 1408 1409 at_top = 1; 1410 while (1) { 1411 if (*diffp == 0) 1412 return; 1413 1414 if (JT(*diffp) != JT(b)) 1415 return; 1416 1417 if (!SET_MEMBER((*diffp)->dom, b->id)) 1418 return; 1419 1420 if ((*diffp)->val[A_ATOM] != val) 1421 break; 1422 1423 diffp = &JF(*diffp); 1424 at_top = 0; 1425 } 1426 samep = &JF(*diffp); 1427 while (1) { 1428 if (*samep == 0) 1429 return; 1430 1431 if (JT(*samep) != JT(b)) 1432 return; 1433 1434 if (!SET_MEMBER((*samep)->dom, b->id)) 1435 return; 1436 1437 if ((*samep)->val[A_ATOM] == val) 1438 break; 1439 1440 /* XXX Need to check that there are no data dependencies 1441 between dp0 and dp1. Currently, the code generator 1442 will not produce such dependencies. */ 1443 samep = &JF(*samep); 1444 } 1445#ifdef notdef 1446 /* XXX This doesn't cover everything. */ 1447 for (i = 0; i < N_ATOMS; ++i) 1448 if ((*samep)->val[i] != pred->val[i]) 1449 return; 1450#endif 1451 /* Pull up the node. */ 1452 pull = *samep; 1453 *samep = JF(pull); 1454 JF(pull) = *diffp; 1455 1456 /* 1457 * At the top of the chain, each predecessor needs to point at the 1458 * pulled up node. Inside the chain, there is only one predecessor 1459 * to worry about. 1460 */ 1461 if (at_top) { 1462 for (ep = b->in_edges; ep != 0; ep = ep->next) { 1463 if (JT(ep->pred) == b) 1464 JT(ep->pred) = pull; 1465 else 1466 JF(ep->pred) = pull; 1467 } 1468 } 1469 else 1470 *diffp = pull; 1471 1472 done = 0; 1473} 1474 1475static void 1476and_pullup(struct block *b) 1477{ 1478 int val, at_top; 1479 struct block *pull; 1480 struct block **diffp, **samep; 1481 struct edge *ep; 1482 1483 ep = b->in_edges; 1484 if (ep == 0) 1485 return; 1486 1487 /* 1488 * Make sure each predecessor loads the same value. 1489 */ 1490 val = ep->pred->val[A_ATOM]; 1491 for (ep = ep->next; ep != 0; ep = ep->next) 1492 if (val != ep->pred->val[A_ATOM]) 1493 return; 1494 1495 if (JT(b->in_edges->pred) == b) 1496 diffp = &JT(b->in_edges->pred); 1497 else 1498 diffp = &JF(b->in_edges->pred); 1499 1500 at_top = 1; 1501 while (1) { 1502 if (*diffp == 0) 1503 return; 1504 1505 if (JF(*diffp) != JF(b)) 1506 return; 1507 1508 if (!SET_MEMBER((*diffp)->dom, b->id)) 1509 return; 1510 1511 if ((*diffp)->val[A_ATOM] != val) 1512 break; 1513 1514 diffp = &JT(*diffp); 1515 at_top = 0; 1516 } 1517 samep = &JT(*diffp); 1518 while (1) { 1519 if (*samep == 0) 1520 return; 1521 1522 if (JF(*samep) != JF(b)) 1523 return; 1524 1525 if (!SET_MEMBER((*samep)->dom, b->id)) 1526 return; 1527 1528 if ((*samep)->val[A_ATOM] == val) 1529 break; 1530 1531 /* XXX Need to check that there are no data dependencies 1532 between diffp and samep. Currently, the code generator 1533 will not produce such dependencies. */ 1534 samep = &JT(*samep); 1535 } 1536#ifdef notdef 1537 /* XXX This doesn't cover everything. */ 1538 for (i = 0; i < N_ATOMS; ++i) 1539 if ((*samep)->val[i] != pred->val[i]) 1540 return; 1541#endif 1542 /* Pull up the node. */ 1543 pull = *samep; 1544 *samep = JT(pull); 1545 JT(pull) = *diffp; 1546 1547 /* 1548 * At the top of the chain, each predecessor needs to point at the 1549 * pulled up node. Inside the chain, there is only one predecessor 1550 * to worry about. 1551 */ 1552 if (at_top) { 1553 for (ep = b->in_edges; ep != 0; ep = ep->next) { 1554 if (JT(ep->pred) == b) 1555 JT(ep->pred) = pull; 1556 else 1557 JF(ep->pred) = pull; 1558 } 1559 } 1560 else 1561 *diffp = pull; 1562 1563 done = 0; 1564} 1565 1566static void 1567opt_blks(struct block *root, int do_stmts) 1568{ 1569 int i, maxlevel; 1570 struct block *p; 1571 1572 init_val(); 1573 maxlevel = root->level; 1574 1575 find_inedges(root); 1576 for (i = maxlevel; i >= 0; --i) 1577 for (p = levels[i]; p; p = p->link) 1578 opt_blk(p, do_stmts); 1579 1580 if (do_stmts) 1581 /* 1582 * No point trying to move branches; it can't possibly 1583 * make a difference at this point. 1584 */ 1585 return; 1586 1587 for (i = 1; i <= maxlevel; ++i) { 1588 for (p = levels[i]; p; p = p->link) { 1589 opt_j(&p->et); 1590 opt_j(&p->ef); 1591 } 1592 } 1593 1594 find_inedges(root); 1595 for (i = 1; i <= maxlevel; ++i) { 1596 for (p = levels[i]; p; p = p->link) { 1597 or_pullup(p); 1598 and_pullup(p); 1599 } 1600 } 1601} 1602 1603static inline void 1604link_inedge(struct edge *parent, struct block *child) 1605{ 1606 parent->next = child->in_edges; 1607 child->in_edges = parent; 1608} 1609 1610static void 1611find_inedges(struct block *root) 1612{ 1613 int i; 1614 struct block *b; 1615 1616 for (i = 0; i < n_blocks; ++i) 1617 blocks[i]->in_edges = 0; 1618 1619 /* 1620 * Traverse the graph, adding each edge to the predecessor 1621 * list of its successors. Skip the leaves (i.e. level 0). 1622 */ 1623 for (i = root->level; i > 0; --i) { 1624 for (b = levels[i]; b != 0; b = b->link) { 1625 link_inedge(&b->et, JT(b)); 1626 link_inedge(&b->ef, JF(b)); 1627 } 1628 } 1629} 1630 1631static void 1632opt_root(struct block **b) 1633{ 1634 struct slist *tmp, *s; 1635 1636 s = (*b)->stmts; 1637 (*b)->stmts = 0; 1638 while (BPF_CLASS((*b)->s.code) == BPF_JMP && JT(*b) == JF(*b)) 1639 *b = JT(*b); 1640 1641 tmp = (*b)->stmts; 1642 if (tmp != 0) 1643 sappend(s, tmp); 1644 (*b)->stmts = s; 1645 1646 /* 1647 * If the root node is a return, then there is no 1648 * point executing any statements (since the bpf machine 1649 * has no side effects). 1650 */ 1651 if (BPF_CLASS((*b)->s.code) == BPF_RET) 1652 (*b)->stmts = 0; 1653} 1654 1655static void 1656opt_loop(struct block *root, int do_stmts) 1657{ 1658 1659#ifdef BDEBUG 1660 if (dflag > 1) { 1661 printf("opt_loop(root, %d) begin\n", do_stmts); 1662 opt_dump(root); 1663 } 1664#endif 1665 do { 1666 done = 1; 1667 find_levels(root); 1668 find_dom(root); 1669 find_closure(root); 1670 find_ud(root); 1671 find_edom(root); 1672 opt_blks(root, do_stmts); 1673#ifdef BDEBUG 1674 if (dflag > 1) { 1675 printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, done); 1676 opt_dump(root); 1677 } 1678#endif 1679 } while (!done); 1680} 1681 1682/* 1683 * Optimize the filter code in its dag representation. 1684 */ 1685void 1686bpf_optimize(struct block **rootp) 1687{ 1688 struct block *root; 1689 1690 root = *rootp; 1691 1692 opt_init(root); 1693 opt_loop(root, 0); 1694 opt_loop(root, 1); 1695 intern_blocks(root); 1696#ifdef BDEBUG 1697 if (dflag > 1) { 1698 printf("after intern_blocks()\n"); 1699 opt_dump(root); 1700 } 1701#endif 1702 opt_root(rootp); 1703#ifdef BDEBUG 1704 if (dflag > 1) { 1705 printf("after opt_root()\n"); 1706 opt_dump(root); 1707 } 1708#endif 1709 opt_cleanup(); 1710} 1711 1712static void 1713make_marks(struct block *p) 1714{ 1715 if (!isMarked(p)) { 1716 Mark(p); 1717 if (BPF_CLASS(p->s.code) != BPF_RET) { 1718 make_marks(JT(p)); 1719 make_marks(JF(p)); 1720 } 1721 } 1722} 1723 1724/* 1725 * Mark code array such that isMarked(i) is true 1726 * only for nodes that are alive. 1727 */ 1728static void 1729mark_code(struct block *p) 1730{ 1731 cur_mark += 1; 1732 make_marks(p); 1733} 1734 1735/* 1736 * True iff the two stmt lists load the same value from the packet into 1737 * the accumulator. 1738 */ 1739static int 1740eq_slist(struct slist *x, struct slist *y) 1741{ 1742 while (1) { 1743 while (x && x->s.code == NOP) 1744 x = x->next; 1745 while (y && y->s.code == NOP) 1746 y = y->next; 1747 if (x == 0) 1748 return y == 0; 1749 if (y == 0) 1750 return x == 0; 1751 if (x->s.code != y->s.code || x->s.k != y->s.k) 1752 return 0; 1753 x = x->next; 1754 y = y->next; 1755 } 1756} 1757 1758static inline int 1759eq_blk(struct block *b0, struct block *b1) 1760{ 1761 if (b0->s.code == b1->s.code && 1762 b0->s.k == b1->s.k && 1763 b0->et.succ == b1->et.succ && 1764 b0->ef.succ == b1->ef.succ) 1765 return eq_slist(b0->stmts, b1->stmts); 1766 return 0; 1767} 1768 1769static void 1770intern_blocks(struct block *root) 1771{ 1772 struct block *p; 1773 int i, j; 1774 int done1; /* don't shadow global */ 1775 top: 1776 done1 = 1; 1777 for (i = 0; i < n_blocks; ++i) 1778 blocks[i]->link = 0; 1779 1780 mark_code(root); 1781 1782 for (i = n_blocks - 1; --i >= 0; ) { 1783 if (!isMarked(blocks[i])) 1784 continue; 1785 for (j = i + 1; j < n_blocks; ++j) { 1786 if (!isMarked(blocks[j])) 1787 continue; 1788 if (eq_blk(blocks[i], blocks[j])) { 1789 blocks[i]->link = blocks[j]->link ? 1790 blocks[j]->link : blocks[j]; 1791 break; 1792 } 1793 } 1794 } 1795 for (i = 0; i < n_blocks; ++i) { 1796 p = blocks[i]; 1797 if (JT(p) == 0) 1798 continue; 1799 if (JT(p)->link) { 1800 done1 = 0; 1801 JT(p) = JT(p)->link; 1802 } 1803 if (JF(p)->link) { 1804 done1 = 0; 1805 JF(p) = JF(p)->link; 1806 } 1807 } 1808 if (!done1) 1809 goto top; 1810} 1811 1812static void 1813opt_cleanup(void) 1814{ 1815 free((void *)vnode_base); 1816 free((void *)vmap); 1817 free((void *)edges); 1818 free((void *)space); 1819 free((void *)levels); 1820 free((void *)blocks); 1821} 1822 1823/* 1824 * Return the number of stmts in 's'. 1825 */ 1826static u_int 1827slength(struct slist *s) 1828{ 1829 u_int n = 0; 1830 1831 for (; s; s = s->next) 1832 if (s->s.code != NOP) 1833 ++n; 1834 return n; 1835} 1836 1837/* 1838 * Return the number of nodes reachable by 'p'. 1839 * All nodes should be initially unmarked. 1840 */ 1841static int 1842count_blocks(struct block *p) 1843{ 1844 if (p == 0 || isMarked(p)) 1845 return 0; 1846 Mark(p); 1847 return count_blocks(JT(p)) + count_blocks(JF(p)) + 1; 1848} 1849 1850/* 1851 * Do a depth first search on the flow graph, numbering the 1852 * the basic blocks, and entering them into the 'blocks' array.` 1853 */ 1854static void 1855number_blks_r(struct block *p) 1856{ 1857 int n; 1858 1859 if (p == 0 || isMarked(p)) 1860 return; 1861 1862 Mark(p); 1863 n = n_blocks++; 1864 p->id = n; 1865 blocks[n] = p; 1866 1867 number_blks_r(JT(p)); 1868 number_blks_r(JF(p)); 1869} 1870 1871/* 1872 * Return the number of stmts in the flowgraph reachable by 'p'. 1873 * The nodes should be unmarked before calling. 1874 * 1875 * Note that "stmts" means "instructions", and that this includes 1876 * 1877 * side-effect statements in 'p' (slength(p->stmts)); 1878 * 1879 * statements in the true branch from 'p' (count_stmts(JT(p))); 1880 * 1881 * statements in the false branch from 'p' (count_stmts(JF(p))); 1882 * 1883 * the conditional jump itself (1); 1884 * 1885 * an extra long jump if the true branch requires it (p->longjt); 1886 * 1887 * an extra long jump if the false branch requires it (p->longjf). 1888 */ 1889static u_int 1890count_stmts(struct block *p) 1891{ 1892 u_int n; 1893 1894 if (p == 0 || isMarked(p)) 1895 return 0; 1896 Mark(p); 1897 n = count_stmts(JT(p)) + count_stmts(JF(p)); 1898 return slength(p->stmts) + n + 1 + p->longjt + p->longjf; 1899} 1900 1901/* 1902 * Allocate memory. All allocation is done before optimization 1903 * is begun. A linear bound on the size of all data structures is computed 1904 * from the total number of blocks and/or statements. 1905 */ 1906static void 1907opt_init(struct block *root) 1908{ 1909 bpf_u_int32 *p; 1910 int i, n, max_stmts; 1911 1912 /* 1913 * First, count the blocks, so we can malloc an array to map 1914 * block number to block. Then, put the blocks into the array. 1915 */ 1916 unMarkAll(); 1917 n = count_blocks(root); 1918 blocks = (struct block **)calloc(n, sizeof(*blocks)); 1919 if (blocks == NULL) 1920 bpf_error("malloc"); 1921 unMarkAll(); 1922 n_blocks = 0; 1923 number_blks_r(root); 1924 1925 n_edges = 2 * n_blocks; 1926 edges = (struct edge **)calloc(n_edges, sizeof(*edges)); 1927 if (edges == NULL) 1928 bpf_error("malloc"); 1929 1930 /* 1931 * The number of levels is bounded by the number of nodes. 1932 */ 1933 levels = (struct block **)calloc(n_blocks, sizeof(*levels)); 1934 if (levels == NULL) 1935 bpf_error("malloc"); 1936 1937 edgewords = n_edges / (8 * sizeof(bpf_u_int32)) + 1; 1938 nodewords = n_blocks / (8 * sizeof(bpf_u_int32)) + 1; 1939 1940 /* XXX */ 1941 space = (bpf_u_int32 *)malloc(2 * n_blocks * nodewords * sizeof(*space) 1942 + n_edges * edgewords * sizeof(*space)); 1943 if (space == NULL) 1944 bpf_error("malloc"); 1945 p = space; 1946 all_dom_sets = p; 1947 for (i = 0; i < n; ++i) { 1948 blocks[i]->dom = p; 1949 p += nodewords; 1950 } 1951 all_closure_sets = p; 1952 for (i = 0; i < n; ++i) { 1953 blocks[i]->closure = p; 1954 p += nodewords; 1955 } 1956 all_edge_sets = p; 1957 for (i = 0; i < n; ++i) { 1958 register struct block *b = blocks[i]; 1959 1960 b->et.edom = p; 1961 p += edgewords; 1962 b->ef.edom = p; 1963 p += edgewords; 1964 b->et.id = i; 1965 edges[i] = &b->et; 1966 b->ef.id = n_blocks + i; 1967 edges[n_blocks + i] = &b->ef; 1968 b->et.pred = b; 1969 b->ef.pred = b; 1970 } 1971 max_stmts = 0; 1972 for (i = 0; i < n; ++i) 1973 max_stmts += slength(blocks[i]->stmts) + 1; 1974 /* 1975 * We allocate at most 3 value numbers per statement, 1976 * so this is an upper bound on the number of valnodes 1977 * we'll need. 1978 */ 1979 maxval = 3 * max_stmts; 1980 vmap = (struct vmapinfo *)calloc(maxval, sizeof(*vmap)); 1981 vnode_base = (struct valnode *)calloc(maxval, sizeof(*vnode_base)); 1982 if (vmap == NULL || vnode_base == NULL) 1983 bpf_error("malloc"); 1984} 1985 1986/* 1987 * Some pointers used to convert the basic block form of the code, 1988 * into the array form that BPF requires. 'fstart' will point to 1989 * the malloc'd array while 'ftail' is used during the recursive traversal. 1990 */ 1991static struct bpf_insn *fstart; 1992static struct bpf_insn *ftail; 1993 1994#ifdef BDEBUG 1995int bids[1000]; 1996#endif 1997 1998/* 1999 * Returns true if successful. Returns false if a branch has 2000 * an offset that is too large. If so, we have marked that 2001 * branch so that on a subsequent iteration, it will be treated 2002 * properly. 2003 */ 2004static int 2005convert_code_r(struct block *p) 2006{ 2007 struct bpf_insn *dst; 2008 struct slist *src; 2009 int slen; 2010 u_int off; 2011 int extrajmps; /* number of extra jumps inserted */ 2012 struct slist **offset = NULL; 2013 2014 if (p == 0 || isMarked(p)) 2015 return (1); 2016 Mark(p); 2017 2018 if (convert_code_r(JF(p)) == 0) 2019 return (0); 2020 if (convert_code_r(JT(p)) == 0) 2021 return (0); 2022 2023 slen = slength(p->stmts); 2024 dst = ftail -= (slen + 1 + p->longjt + p->longjf); 2025 /* inflate length by any extra jumps */ 2026 2027 p->offset = dst - fstart; 2028 2029 /* generate offset[] for convenience */ 2030 if (slen) { 2031 offset = (struct slist **)calloc(slen, sizeof(struct slist *)); 2032 if (!offset) { 2033 bpf_error("not enough core"); 2034 /*NOTREACHED*/ 2035 } 2036 } 2037 src = p->stmts; 2038 for (off = 0; off < slen && src; off++) { 2039#if 0 2040 printf("off=%d src=%x\n", off, src); 2041#endif 2042 offset[off] = src; 2043 src = src->next; 2044 } 2045 2046 off = 0; 2047 for (src = p->stmts; src; src = src->next) { 2048 if (src->s.code == NOP) 2049 continue; 2050 dst->code = (u_short)src->s.code; 2051 dst->k = src->s.k; 2052 2053 /* fill block-local relative jump */ 2054 if (BPF_CLASS(src->s.code) != BPF_JMP || src->s.code == (BPF_JMP|BPF_JA)) { 2055#if 0 2056 if (src->s.jt || src->s.jf) { 2057 bpf_error("illegal jmp destination"); 2058 /*NOTREACHED*/ 2059 } 2060#endif 2061 goto filled; 2062 } 2063 if (off == slen - 2) /*???*/ 2064 goto filled; 2065 2066 { 2067 int i; 2068 int jt, jf; 2069 const char *ljerr = "%s for block-local relative jump: off=%d"; 2070 2071#if 0 2072 printf("code=%x off=%d %x %x\n", src->s.code, 2073 off, src->s.jt, src->s.jf); 2074#endif 2075 2076 if (!src->s.jt || !src->s.jf) { 2077 bpf_error(ljerr, "no jmp destination", off); 2078 /*NOTREACHED*/ 2079 } 2080 2081 jt = jf = 0; 2082 for (i = 0; i < slen; i++) { 2083 if (offset[i] == src->s.jt) { 2084 if (jt) { 2085 bpf_error(ljerr, "multiple matches", off); 2086 /*NOTREACHED*/ 2087 } 2088 2089 dst->jt = i - off - 1; 2090 jt++; 2091 } 2092 if (offset[i] == src->s.jf) { 2093 if (jf) { 2094 bpf_error(ljerr, "multiple matches", off); 2095 /*NOTREACHED*/ 2096 } 2097 dst->jf = i - off - 1; 2098 jf++; 2099 } 2100 } 2101 if (!jt || !jf) { 2102 bpf_error(ljerr, "no destination found", off); 2103 /*NOTREACHED*/ 2104 } 2105 } 2106filled: 2107 ++dst; 2108 ++off; 2109 } 2110 if (offset) 2111 free(offset); 2112 2113#ifdef BDEBUG 2114 bids[dst - fstart] = p->id + 1; 2115#endif 2116 dst->code = (u_short)p->s.code; 2117 dst->k = p->s.k; 2118 if (JT(p)) { 2119 extrajmps = 0; 2120 off = JT(p)->offset - (p->offset + slen) - 1; 2121 if (off >= 256) { 2122 /* offset too large for branch, must add a jump */ 2123 if (p->longjt == 0) { 2124 /* mark this instruction and retry */ 2125 p->longjt++; 2126 return(0); 2127 } 2128 /* branch if T to following jump */ 2129 dst->jt = extrajmps; 2130 extrajmps++; 2131 dst[extrajmps].code = BPF_JMP|BPF_JA; 2132 dst[extrajmps].k = off - extrajmps; 2133 } 2134 else 2135 dst->jt = off; 2136 off = JF(p)->offset - (p->offset + slen) - 1; 2137 if (off >= 256) { 2138 /* offset too large for branch, must add a jump */ 2139 if (p->longjf == 0) { 2140 /* mark this instruction and retry */ 2141 p->longjf++; 2142 return(0); 2143 } 2144 /* branch if F to following jump */ 2145 /* if two jumps are inserted, F goes to second one */ 2146 dst->jf = extrajmps; 2147 extrajmps++; 2148 dst[extrajmps].code = BPF_JMP|BPF_JA; 2149 dst[extrajmps].k = off - extrajmps; 2150 } 2151 else 2152 dst->jf = off; 2153 } 2154 return (1); 2155} 2156 2157 2158/* 2159 * Convert flowgraph intermediate representation to the 2160 * BPF array representation. Set *lenp to the number of instructions. 2161 * 2162 * This routine does *NOT* leak the memory pointed to by fp. It *must 2163 * not* do free(fp) before returning fp; doing so would make no sense, 2164 * as the BPF array pointed to by the return value of icode_to_fcode() 2165 * must be valid - it's being returned for use in a bpf_program structure. 2166 * 2167 * If it appears that icode_to_fcode() is leaking, the problem is that 2168 * the program using pcap_compile() is failing to free the memory in 2169 * the BPF program when it's done - the leak is in the program, not in 2170 * the routine that happens to be allocating the memory. (By analogy, if 2171 * a program calls fopen() without ever calling fclose() on the FILE *, 2172 * it will leak the FILE structure; the leak is not in fopen(), it's in 2173 * the program.) Change the program to use pcap_freecode() when it's 2174 * done with the filter program. See the pcap man page. 2175 */ 2176struct bpf_insn * 2177icode_to_fcode(struct block *root, u_int *lenp) 2178{ 2179 u_int n; 2180 struct bpf_insn *fp; 2181 2182 /* 2183 * Loop doing convert_code_r() until no branches remain 2184 * with too-large offsets. 2185 */ 2186 while (1) { 2187 unMarkAll(); 2188 n = *lenp = count_stmts(root); 2189 2190 fp = (struct bpf_insn *)malloc(sizeof(*fp) * n); 2191 if (fp == NULL) 2192 bpf_error("malloc"); 2193 memset((char *)fp, 0, sizeof(*fp) * n); 2194 fstart = fp; 2195 ftail = fp + n; 2196 2197 unMarkAll(); 2198 if (convert_code_r(root)) 2199 break; 2200 free(fp); 2201 } 2202 2203 return fp; 2204} 2205 2206/* 2207 * Make a copy of a BPF program and put it in the "fcode" member of 2208 * a "pcap_t". 2209 * 2210 * If we fail to allocate memory for the copy, fill in the "errbuf" 2211 * member of the "pcap_t" with an error message, and return -1; 2212 * otherwise, return 0. 2213 */ 2214int 2215install_bpf_program(pcap_t *p, struct bpf_program *fp) 2216{ 2217 size_t prog_size; 2218 2219 /* 2220 * Validate the program. 2221 */ 2222 if (!bpf_validate(fp->bf_insns, fp->bf_len)) { 2223 snprintf(p->errbuf, sizeof(p->errbuf), 2224 "BPF program is not valid"); 2225 return (-1); 2226 } 2227 2228 /* 2229 * Free up any already installed program. 2230 */ 2231 pcap_freecode(&p->fcode); 2232 2233 prog_size = sizeof(*fp->bf_insns) * fp->bf_len; 2234 p->fcode.bf_len = fp->bf_len; 2235 p->fcode.bf_insns = (struct bpf_insn *)malloc(prog_size); 2236 if (p->fcode.bf_insns == NULL) { 2237 snprintf(p->errbuf, sizeof(p->errbuf), 2238 "malloc: %s", pcap_strerror(errno)); 2239 return (-1); 2240 } 2241 memcpy(p->fcode.bf_insns, fp->bf_insns, prog_size); 2242 return (0); 2243} 2244 2245#ifdef BDEBUG 2246static void 2247dot_dump_node(struct block *block, struct bpf_program *prog, FILE *out) 2248{ 2249 int icount, noffset; 2250 int i; 2251 2252 if (block == NULL || isMarked(block)) 2253 return; 2254 Mark(block); 2255 2256 icount = slength(block->stmts) + 1 + block->longjt + block->longjf; 2257 noffset = min(block->offset + icount, (int)prog->bf_len); 2258 2259 fprintf(out, "\tblock%d [shape=ellipse, id=\"block-%d\" label=\"BLOCK%d\\n", block->id, block->id, block->id); 2260 for (i = block->offset; i < noffset; i++) { 2261 fprintf(out, "\\n%s", bpf_image(prog->bf_insns + i, i)); 2262 } 2263 fprintf(out, "\" tooltip=\""); 2264 for (i = 0; i < BPF_MEMWORDS; i++) 2265 if (block->val[i] != 0) 2266 fprintf(out, "val[%d]=%d ", i, block->val[i]); 2267 fprintf(out, "val[A]=%d ", block->val[A_ATOM]); 2268 fprintf(out, "val[X]=%d", block->val[X_ATOM]); 2269 fprintf(out, "\""); 2270 if (JT(block) == NULL) 2271 fprintf(out, ", peripheries=2"); 2272 fprintf(out, "];\n"); 2273 2274 dot_dump_node(JT(block), prog, out); 2275 dot_dump_node(JF(block), prog, out); 2276} 2277static void 2278dot_dump_edge(struct block *block, FILE *out) 2279{ 2280 if (block == NULL || isMarked(block)) 2281 return; 2282 Mark(block); 2283 2284 if (JT(block)) { 2285 fprintf(out, "\t\"block%d\":se -> \"block%d\":n [label=\"T\"]; \n", 2286 block->id, JT(block)->id); 2287 fprintf(out, "\t\"block%d\":sw -> \"block%d\":n [label=\"F\"]; \n", 2288 block->id, JF(block)->id); 2289 } 2290 dot_dump_edge(JT(block), out); 2291 dot_dump_edge(JF(block), out); 2292} 2293/* Output the block CFG using graphviz/DOT language 2294 * In the CFG, block's code, value index for each registers at EXIT, 2295 * and the jump relationship is show. 2296 * 2297 * example DOT for BPF `ip src host 1.1.1.1' is: 2298 digraph BPF { 2299 block0 [shape=ellipse, id="block-0" label="BLOCK0\n\n(000) ldh [12]\n(001) jeq #0x800 jt 2 jf 5" tooltip="val[A]=0 val[X]=0"]; 2300 block1 [shape=ellipse, id="block-1" label="BLOCK1\n\n(002) ld [26]\n(003) jeq #0x1010101 jt 4 jf 5" tooltip="val[A]=0 val[X]=0"]; 2301 block2 [shape=ellipse, id="block-2" label="BLOCK2\n\n(004) ret #68" tooltip="val[A]=0 val[X]=0", peripheries=2]; 2302 block3 [shape=ellipse, id="block-3" label="BLOCK3\n\n(005) ret #0" tooltip="val[A]=0 val[X]=0", peripheries=2]; 2303 "block0":se -> "block1":n [label="T"]; 2304 "block0":sw -> "block3":n [label="F"]; 2305 "block1":se -> "block2":n [label="T"]; 2306 "block1":sw -> "block3":n [label="F"]; 2307 } 2308 * 2309 * After install graphviz on http://www.graphviz.org/, save it as bpf.dot 2310 * and run `dot -Tpng -O bpf.dot' to draw the graph. 2311 */ 2312static void 2313dot_dump(struct block *root) 2314{ 2315 struct bpf_program f; 2316 FILE *out = stdout; 2317 2318 memset(bids, 0, sizeof bids); 2319 f.bf_insns = icode_to_fcode(root, &f.bf_len); 2320 2321 fprintf(out, "digraph BPF {\n"); 2322 unMarkAll(); 2323 dot_dump_node(root, &f, out); 2324 unMarkAll(); 2325 dot_dump_edge(root, out); 2326 fprintf(out, "}\n"); 2327 2328 free((char *)f.bf_insns); 2329} 2330 2331static void 2332plain_dump(struct block *root) 2333{ 2334 struct bpf_program f; 2335 2336 memset(bids, 0, sizeof bids); 2337 f.bf_insns = icode_to_fcode(root, &f.bf_len); 2338 bpf_dump(&f, 1); 2339 putchar('\n'); 2340 free((char *)f.bf_insns); 2341} 2342static void 2343opt_dump(struct block *root) 2344{ 2345 /* if optimizer debugging is enabled, output DOT graph 2346 * `dflag=4' is equivalent to -dddd to follow -d/-dd/-ddd 2347 * convention in tcpdump command line 2348 */ 2349 if (dflag > 3) 2350 dot_dump(root); 2351 else 2352 plain_dump(root); 2353} 2354 2355#endif 2356