开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Internet/网络编程 > Telnet服务器 > 查看源码
optimize.c
资源名称：nessus-libraries_2.2.10.orig.tar.gz　[点击查看]
上传用户：tjescc
上传日期：2021-02-23
资源大小：419k
文件大小：40k
源码类别：

Telnet服务器

开发平台：

Unix_Linux

optimize.c：源码内容
  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. #ifndef lint
  24. static const char rcsid[] =
  25.     "@(#) $Header: /usr/local/cvs/nessus-libraries/libpcap-nessus/optimize.c,v 1.3 2003/02/06 20:28:08 renaud Exp $ (LBL)";
  26. #endif
  28. #include <sys/types.h>
  29. #include <sys/time.h>
  31. #include <stdio.h>
  32. #include <stdlib.h>
  33. #include <memory.h>
  35. #include "pcap-int.h"
  37. #include "gencode.h"
  39. #include "gnuc.h"
  40. #ifdef HAVE_OS_PROTO_H
  41. #include "os-proto.h"
  42. #endif
  44. #ifdef BDEBUG
  45. extern int dflag;
  46. #endif
  48. #define A_ATOM BPF_MEMWORDS
  49. #define X_ATOM (BPF_MEMWORDS+1)
  51. #define NOP -1
  53. /*
  54.  * This define is used to represent *both* the accumulator and
  55.  * x register in use-def computations.
  56.  * Currently, the use-def code assumes only one definition per instruction.
  57.  */
  58. #define AX_ATOM N_ATOMS
  60. /*
  61.  * A flag to indicate that further optimization is needed.
  62.  * Iterative passes are continued until a given pass yields no
  63.  * branch movement.
  64.  */
  65. static int done;
  67. /*
  68.  * A block is marked if only if its mark equals the current mark.
  69.  * Rather than traverse the code array, marking each item, 'cur_mark' is
  70.  * incremented.  This automatically makes each element unmarked.
  71.  */
  72. static int cur_mark;
  73. #define isMarked(p) ((p)->mark == cur_mark)
  74. #define unMarkAll() cur_mark += 1
  75. #define Mark(p) ((p)->mark = cur_mark)
  77. static void opt_init(struct block *);
  78. static void opt_cleanup(void);
  80. static void make_marks(struct block *);
  81. static void mark_code(struct block *);
  83. static void intern_blocks(struct block *);
  85. static int eq_slist(struct slist *, struct slist *);
  87. static void find_levels_r(struct block *);
  89. static void find_levels(struct block *);
  90. static void find_dom(struct block *);
  91. static void propedom(struct edge *);
  92. static void find_edom(struct block *);
  93. static void find_closure(struct block *);
  94. static int atomuse(struct stmt *);
  95. static int atomdef(struct stmt *);
  96. static void compute_local_ud(struct block *);
  97. static void find_ud(struct block *);
  98. static void init_val(void);
  99. static int F(int, int, int);
  100. static inline void vstore(struct stmt *, int *, int, int);
  101. static void opt_blk(struct block *, int);
  102. static int use_conflict(struct block *, struct block *);
  103. static void opt_j(struct edge *);
  104. static void or_pullup(struct block *);
  105. static void and_pullup(struct block *);
  106. static void opt_blks(struct block *, int);
  107. static inline void link_inedge(struct edge *, struct block *);
  108. static void find_inedges(struct block *);
  109. static void opt_root(struct block **);
  110. static void opt_loop(struct block *, int);
  111. static void fold_op(struct stmt *, int, int);
  112. static inline struct slist *this_op(struct slist *);
  113. static void opt_not(struct block *);
  114. static void opt_peep(struct block *);
  115. static void opt_stmt(struct stmt *, int[], int);
  116. static void deadstmt(struct stmt *, struct stmt *[]);
  117. static void opt_deadstores(struct block *);
  118. static void opt_blk(struct block *, int);
  119. static int use_conflict(struct block *, struct block *);
  120. static void opt_j(struct edge *);
  121. static struct block *fold_edge(struct block *, struct edge *);
  122. static inline int eq_blk(struct block *, struct block *);
  123. static int slength(struct slist *);
  124. static int count_blocks(struct block *);
  125. static void number_blks_r(struct block *);
  126. static int count_stmts(struct block *);
  127. static int convert_code_r(struct block *);
  128. #ifdef BDEBUG
  129. static void opt_dump(struct block *);
  130. #endif
  132. static int n_blocks;
  133. struct block **blocks;
  134. static int n_edges;
  135. struct edge **edges;
  137. /*
  138.  * A bit vector set representation of the dominators.
  139.  * We round up the set size to the next power of two.
  140.  */
  141. static int nodewords;
  142. static int edgewords;
  143. struct block **levels;
  144. bpf_u_int32 *space;
  145. #define BITS_PER_WORD (8*sizeof(bpf_u_int32))
  146. /*
  147.  * True if a is in uset {p}
  148.  */
  149. #define SET_MEMBER(p, a) 
  150. ((p)[(unsigned)(a) / BITS_PER_WORD] & (1 << ((unsigned)(a) % BITS_PER_WORD)))
  152. /*
  153.  * Add 'a' to uset p.
  154.  */
  155. #define SET_INSERT(p, a) 
  156. (p)[(unsigned)(a) / BITS_PER_WORD] |= (1 << ((unsigned)(a) % BITS_PER_WORD))
  158. /*
  159.  * Delete 'a' from uset p.
  160.  */
  161. #define SET_DELETE(p, a) 
  162. (p)[(unsigned)(a) / BITS_PER_WORD] &= ~(1 << ((unsigned)(a) % BITS_PER_WORD))
  164. /*
  165.  * a := a intersect b
  166.  */
  167. #define SET_INTERSECT(a, b, n)
  168. {
  169. register bpf_u_int32 *_x = a, *_y = b;
  170. register int _n = n;
  171. while (--_n >= 0) *_x++ &= *_y++;
  172. }
  174. /*
  175.  * a := a - b
  176.  */
  177. #define SET_SUBTRACT(a, b, n)
  178. {
  179. register bpf_u_int32 *_x = a, *_y = b;
  180. register int _n = n;
  181. while (--_n >= 0) *_x++ &=~ *_y++;
  182. }
  184. /*
  185.  * a := a union b
  186.  */
  187. #define SET_UNION(a, b, n)
  188. {
  189. register bpf_u_int32 *_x = a, *_y = b;
  190. register int _n = n;
  191. while (--_n >= 0) *_x++ |= *_y++;
  192. }
  194. static uset all_dom_sets;
  195. static uset all_closure_sets;
  196. static uset all_edge_sets;
  198. #ifndef MAX
  199. #define MAX(a,b) ((a)>(b)?(a):(b))
  200. #endif
  202. static void
  203. find_levels_r(b)
  204. struct block *b;
  205. {
  206. int level;
  208. if (isMarked(b))
  209. return;
  211. Mark(b);
  212. b->link = 0;
  214. if (JT(b)) {
  215. find_levels_r(JT(b));
  216. find_levels_r(JF(b));
  217. level = MAX(JT(b)->level, JF(b)->level) + 1;
  218. } else
  219. level = 0;
  220. b->level = level;
  221. b->link = levels[level];
  222. levels[level] = b;
  223. }
  225. /*
  226.  * Level graph.  The levels go from 0 at the leaves to
  227.  * N_LEVELS at the root.  The levels[] array points to the
  228.  * first node of the level list, whose elements are linked
  229.  * with the 'link' field of the struct block.
  230.  */
  231. static void
  232. find_levels(root)
  233. struct block *root;
  234. {
  235. memset((char *)levels, 0, n_blocks * sizeof(*levels));
  236. unMarkAll();
  237. find_levels_r(root);
  238. }
  240. /*
  241.  * Find dominator relationships.
  242.  * Assumes graph has been leveled.
  243.  */
  244. static void
  245. find_dom(root)
  246. struct block *root;
  247. {
  248. int i;
  249. struct block *b;
  250. bpf_u_int32 *x;
  252. /*
  253.  * Initialize sets to contain all nodes.
  254.  */
  255. x = all_dom_sets;
  256. i = n_blocks * nodewords;
  257. while (--i >= 0)
  258. *x++ = ~0;
  259. /* Root starts off empty. */
  260. for (i = nodewords; --i >= 0;)
  261. root->dom[i] = 0;
  263. /* root->level is the highest level no found. */
  264. for (i = root->level; i >= 0; --i) {
  265. for (b = levels[i]; b; b = b->link) {
  266. SET_INSERT(b->dom, b->id);
  267. if (JT(b) == 0)
  268. continue;
  269. SET_INTERSECT(JT(b)->dom, b->dom, nodewords);
  270. SET_INTERSECT(JF(b)->dom, b->dom, nodewords);
  271. }
  272. }
  273. }
  275. static void
  276. propedom(ep)
  277. struct edge *ep;
  278. {
  279. SET_INSERT(ep->edom, ep->id);
  280. if (ep->succ) {
  281. SET_INTERSECT(ep->succ->et.edom, ep->edom, edgewords);
  282. SET_INTERSECT(ep->succ->ef.edom, ep->edom, edgewords);
  283. }
  284. }
  286. /*
  287.  * Compute edge dominators.
  288.  * Assumes graph has been leveled and predecessors established.
  289.  */
  290. static void
  291. find_edom(root)
  292. struct block *root;
  293. {
  294. int i;
  295. uset x;
  296. struct block *b;
  298. x = all_edge_sets;
  299. for (i = n_edges * edgewords; --i >= 0; )
  300. x[i] = ~0;
  302. /* root->level is the highest level no found. */
  303. memset(root->et.edom, 0, edgewords * sizeof(*(uset)0));
  304. memset(root->ef.edom, 0, edgewords * sizeof(*(uset)0));
  305. for (i = root->level; i >= 0; --i) {
  306. for (b = levels[i]; b != 0; b = b->link) {
  307. propedom(&b->et);
  308. propedom(&b->ef);
  309. }
  310. }
  311. }
  313. /*
  314.  * Find the backwards transitive closure of the flow graph.  These sets
  315.  * are backwards in the sense that we find the set of nodes that reach
  316.  * a given node, not the set of nodes that can be reached by a node.
  317.  *
  318.  * Assumes graph has been leveled.
  319.  */
  320. static void
  321. find_closure(root)
  322. struct block *root;
  323. {
  324. int i;
  325. struct block *b;
  327. /*
  328.  * Initialize sets to contain no nodes.
  329.  */
  330. memset((char *)all_closure_sets, 0,
  331.       n_blocks * nodewords * sizeof(*all_closure_sets));
  333. /* root->level is the highest level no found. */
  334. for (i = root->level; i >= 0; --i) {
  335. for (b = levels[i]; b; b = b->link) {
  336. SET_INSERT(b->closure, b->id);
  337. if (JT(b) == 0)
  338. continue;
  339. SET_UNION(JT(b)->closure, b->closure, nodewords);
  340. SET_UNION(JF(b)->closure, b->closure, nodewords);
  341. }
  342. }
  343. }
  345. /*
  346.  * Return the register number that is used by s.  If A and X are both
  347.  * used, return AX_ATOM.  If no register is used, return -1.
  348.  *
  349.  * The implementation should probably change to an array access.
  350.  */
  351. static int
  352. atomuse(s)
  353. struct stmt *s;
  354. {
  355. register int c = s->code;
  357. if (c == NOP)
  358. return -1;
  360. switch (BPF_CLASS(c)) {
  362. case BPF_RET:
  363. return (BPF_RVAL(c) == BPF_A) ? A_ATOM :
  364. (BPF_RVAL(c) == BPF_X) ? X_ATOM : -1;
  366. case BPF_LD:
  367. case BPF_LDX:
  368. return (BPF_MODE(c) == BPF_IND) ? X_ATOM :
  369. (BPF_MODE(c) == BPF_MEM) ? s->k : -1;
  371. case BPF_ST:
  372. return A_ATOM;
  374. case BPF_STX:
  375. return X_ATOM;
  377. case BPF_JMP:
  378. case BPF_ALU:
  379. if (BPF_SRC(c) == BPF_X)
  380. return AX_ATOM;
  381. return A_ATOM;
  383. case BPF_MISC:
  384. return BPF_MISCOP(c) == BPF_TXA ? X_ATOM : A_ATOM;
  385. }
  386. abort();
  387. /* NOTREACHED */
  388. }
  390. /*
  391.  * Return the register number that is defined by 's'.  We assume that
  392.  * a single stmt cannot define more than one register.  If no register
  393.  * is defined, return -1.
  394.  *
  395.  * The implementation should probably change to an array access.
  396.  */
  397. static int
  398. atomdef(s)
  399. struct stmt *s;
  400. {
  401. if (s->code == NOP)
  402. return -1;
  404. switch (BPF_CLASS(s->code)) {
  406. case BPF_LD:
  407. case BPF_ALU:
  408. return A_ATOM;
  410. case BPF_LDX:
  411. return X_ATOM;
  413. case BPF_ST:
  414. case BPF_STX:
  415. return s->k;
  417. case BPF_MISC:
  418. return BPF_MISCOP(s->code) == BPF_TAX ? X_ATOM : A_ATOM;
  419. }
  420. return -1;
  421. }
  423. static void
  424. compute_local_ud(b)
  425. struct block *b;
  426. {
  427. struct slist *s;
  428. atomset def = 0, use = 0, kill = 0;
  429. int atom;
  431. for (s = b->stmts; s; s = s->next) {
  432. if (s->s.code == NOP)
  433. continue;
  434. atom = atomuse(&s->s);
  435. if (atom >= 0) {
  436. if (atom == AX_ATOM) {
  437. if (!ATOMELEM(def, X_ATOM))
  438. use |= ATOMMASK(X_ATOM);
  439. if (!ATOMELEM(def, A_ATOM))
  440. use |= ATOMMASK(A_ATOM);
  441. }
  442. else if (atom < N_ATOMS) {
  443. if (!ATOMELEM(def, atom))
  444. use |= ATOMMASK(atom);
  445. }
  446. else
  447. abort();
  448. }
  449. atom = atomdef(&s->s);
  450. if (atom >= 0) {
  451. if (!ATOMELEM(use, atom))
  452. kill |= ATOMMASK(atom);
  453. def |= ATOMMASK(atom);
  454. }
  455. }
  456. if (!ATOMELEM(def, A_ATOM) && BPF_CLASS(b->s.code) == BPF_JMP)
  457. use |= ATOMMASK(A_ATOM);
  459. b->def = def;
  460. b->kill = kill;
  461. b->in_use = use;
  462. }
  464. /*
  465.  * Assume graph is already leveled.
  466.  */
  467. static void
  468. find_ud(root)
  469. struct block *root;
  470. {
  471. int i, maxlevel;
  472. struct block *p;
  474. /*
  475.  * root->level is the highest level no found;
  476.  * count down from there.
  477.  */
  478. maxlevel = root->level;
  479. for (i = maxlevel; i >= 0; --i)
  480. for (p = levels[i]; p; p = p->link) {
  481. compute_local_ud(p);
  482. p->out_use = 0;
  483. }
  485. for (i = 1; i <= maxlevel; ++i) {
  486. for (p = levels[i]; p; p = p->link) {
  487. p->out_use |= JT(p)->in_use | JF(p)->in_use;
  488. p->in_use |= p->out_use &~ p->kill;
  489. }
  490. }
  491. }
  493. /*
  494.  * These data structures are used in a Cocke and Shwarz style
  495.  * value numbering scheme.  Since the flowgraph is acyclic,
  496.  * exit values can be propagated from a node's predecessors
  497.  * provided it is uniquely defined.
  498.  */
  499. struct valnode {
  500. int code;
  501. int v0, v1;
  502. int val;
  503. struct valnode *next;
  504. };
  506. #define MODULUS 213
  507. static struct valnode *hashtbl[MODULUS];
  508. static int curval;
  509. static int maxval;
  511. /* Integer constants mapped with the load immediate opcode. */
  512. #define K(i) F(BPF_LD|BPF_IMM|BPF_W, i, 0L)
  514. struct vmapinfo {
  515. int is_const;
  516. bpf_int32 const_val;
  517. };
  519. struct vmapinfo *vmap;
  520. struct valnode *vnode_base;
  521. struct valnode *next_vnode;
  523. static void
  524. init_val()
  525. {
  526. curval = 0;
  527. next_vnode = vnode_base;
  528. memset((char *)vmap, 0, maxval * sizeof(*vmap));
  529. memset((char *)hashtbl, 0, sizeof hashtbl);
  530. }
  532. /* Because we really don't have an IR, this stuff is a little messy. */
  533. static int
  534. F(code, v0, v1)
  535. int code;
  536. int v0, v1;
  537. {
  538. u_int hash;
  539. int val;
  540. struct valnode *p;
  542. hash = (u_int)code ^ (v0 << 4) ^ (v1 << 8);
  543. hash %= MODULUS;
  545. for (p = hashtbl[hash]; p; p = p->next)
  546. if (p->code == code && p->v0 == v0 && p->v1 == v1)
  547. return p->val;
  549. val = ++curval;
  550. if (BPF_MODE(code) == BPF_IMM &&
  551.     (BPF_CLASS(code) == BPF_LD || BPF_CLASS(code) == BPF_LDX)) {
  552. vmap[val].const_val = v0;
  553. vmap[val].is_const = 1;
  554. }
  555. p = next_vnode++;
  556. p->val = val;
  557. p->code = code;
  558. p->v0 = v0;
  559. p->v1 = v1;
  560. p->next = hashtbl[hash];
  561. hashtbl[hash] = p;
  563. return val;
  564. }
  566. static inline void
  567. vstore(s, valp, newval, alter)
  568. struct stmt *s;
  569. int *valp;
  570. int newval;
  571. int alter;
  572. {
  573. if (alter && *valp == newval)
  574. s->code = NOP;
  575. else
  576. *valp = newval;
  577. }
  579. static void
  580. fold_op(s, v0, v1)
  581. struct stmt *s;
  582. int v0, v1;
  583. {
  584. bpf_int32 a, b;
  586. a = vmap[v0].const_val;
  587. b = vmap[v1].const_val;
  589. switch (BPF_OP(s->code)) {
  590. case BPF_ADD:
  591. a += b;
  592. break;
  594. case BPF_SUB:
  595. a -= b;
  596. break;
  598. case BPF_MUL:
  599. a *= b;
  600. break;
  602. case BPF_DIV:
  603. if (b == 0)
  604. bpf_error("division by zero");
  605. a /= b;
  606. break;
  608. case BPF_AND:
  609. a &= b;
  610. break;
  612. case BPF_OR:
  613. a |= b;
  614. break;
  616. case BPF_LSH:
  617. a <<= b;
  618. break;
  620. case BPF_RSH:
  621. a >>= b;
  622. break;
  624. case BPF_NEG:
  625. a = -a;
  626. break;
  628. default:
  629. abort();
  630. }
  631. s->k = a;
  632. s->code = BPF_LD|BPF_IMM;
  633. done = 0;
  634. }
  636. static inline struct slist *
  637. this_op(s)
  638. struct slist *s;
  639. {
  640. while (s != 0 && s->s.code == NOP)
  641. s = s->next;
  642. return s;
  643. }
  645. static void
  646. opt_not(b)
  647. struct block *b;
  648. {
  649. struct block *tmp = JT(b);
  651. JT(b) = JF(b);
  652. JF(b) = tmp;
  653. }
  655. static void
  656. opt_peep(b)
  657. struct block *b;
  658. {
  659. struct slist *s;
  660. struct slist *next, *last;
  661. int val;
  663. s = b->stmts;
  664. if (s == 0)
  665. return;
  667. last = s;
  668. while (1) {
  669. s = this_op(s);
  670. if (s == 0)
  671. break;
  672. next = this_op(s->next);
  673. if (next == 0)
  674. break;
  675. last = next;
  677. /*
  678.  * st  M[k] --> st  M[k]
  679.  * ldx M[k] tax
  680.  */
  681. if (s->s.code == BPF_ST &&
  682.     next->s.code == (BPF_LDX|BPF_MEM) &&
  683.     s->s.k == next->s.k) {
  684. done = 0;
  685. next->s.code = BPF_MISC|BPF_TAX;
  686. }
  687. /*
  688.  * ld  #k --> ldx  #k
  689.  * tax txa
  690.  */
  691. if (s->s.code == (BPF_LD|BPF_IMM) &&
  692.     next->s.code == (BPF_MISC|BPF_TAX)) {
  693. s->s.code = BPF_LDX|BPF_IMM;
  694. next->s.code = BPF_MISC|BPF_TXA;
  695. done = 0;
  696. }
  697. /*
  698.  * This is an ugly special case, but it happens
  699.  * when you say tcp[k] or udp[k] where k is a constant.
  700.  */
  701. if (s->s.code == (BPF_LD|BPF_IMM)) {
  702. struct slist *add, *tax, *ild;
  704. /*
  705.  * Check that X isn't used on exit from this
  706.  * block (which the optimizer might cause).
  707.  * We know the code generator won't generate
  708.  * any local dependencies.
  709.  */
  710. if (ATOMELEM(b->out_use, X_ATOM))
  711. break;
  713. if (next->s.code != (BPF_LDX|BPF_MSH|BPF_B))
  714. add = next;
  715. else
  716. add = this_op(next->next);
  717. if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X))
  718. break;
  720. tax = this_op(add->next);
  721. if (tax == 0 || tax->s.code != (BPF_MISC|BPF_TAX))
  722. break;
  724. ild = this_op(tax->next);
  725. if (ild == 0 || BPF_CLASS(ild->s.code) != BPF_LD ||
  726.     BPF_MODE(ild->s.code) != BPF_IND)
  727. break;
  728. /*
  729.  * XXX We need to check that X is not
  730.  * subsequently used.  We know we can eliminate the
  731.  * accumulator modifications since it is defined
  732.  * by the last stmt of this sequence.
  733.  *
  734.  * We want to turn this sequence:
  735.  *
  736.  * (004) ldi     #0x2 {s}
  737.  * (005) ldxms   [14] {next}  -- optional
  738.  * (006) addx {add}
  739.  * (007) tax {tax}
  740.  * (008) ild     [x+0] {ild}
  741.  *
  742.  * into this sequence:
  743.  *
  744.  * (004) nop
  745.  * (005) ldxms   [14]
  746.  * (006) nop
  747.  * (007) nop
  748.  * (008) ild     [x+2]
  749.  *
  750.  */
  751. ild->s.k += s->s.k;
  752. s->s.code = NOP;
  753. add->s.code = NOP;
  754. tax->s.code = NOP;
  755. done = 0;
  756. }
  757. s = next;
  758. }
  759. /*
  760.  * If we have a subtract to do a comparison, and the X register
  761.  * is a known constant, we can merge this value into the
  762.  * comparison.
  763.  */
  764. if (last->s.code == (BPF_ALU|BPF_SUB|BPF_X) &&
  765.     !ATOMELEM(b->out_use, A_ATOM)) {
  766. val = b->val[X_ATOM];
  767. if (vmap[val].is_const) {
  768. int op;
  770. b->s.k += vmap[val].const_val;
  771. op = BPF_OP(b->s.code);
  772. if (op == BPF_JGT || op == BPF_JGE) {
  773. struct block *t = JT(b);
  774. JT(b) = JF(b);
  775. JF(b) = t;
  776. b->s.k += 0x80000000;
  777. }
  778. last->s.code = NOP;
  779. done = 0;
  780. } else if (b->s.k == 0) {
  781. /*
  782.  * sub x  -> nop
  783.  * j  #0 j  x
  784.  */
  785. last->s.code = NOP;
  786. b->s.code = BPF_CLASS(b->s.code) | BPF_OP(b->s.code) |
  787. BPF_X;
  788. done = 0;
  789. }
  790. }
  791. /*
  792.  * Likewise, a constant subtract can be simplified.
  793.  */
  794. else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K) &&
  795.  !ATOMELEM(b->out_use, A_ATOM)) {
  796. int op;
  798. b->s.k += last->s.k;
  799. last->s.code = NOP;
  800. op = BPF_OP(b->s.code);
  801. if (op == BPF_JGT || op == BPF_JGE) {
  802. struct block *t = JT(b);
  803. JT(b) = JF(b);
  804. JF(b) = t;
  805. b->s.k += 0x80000000;
  806. }
  807. done = 0;
  808. }
  809. /*
  810.  * and #k nop
  811.  * jeq #0  -> jset #k
  812.  */
  813. if (last->s.code == (BPF_ALU|BPF_AND|BPF_K) &&
  814.     !ATOMELEM(b->out_use, A_ATOM) && b->s.k == 0) {
  815. b->s.k = last->s.k;
  816. b->s.code = BPF_JMP|BPF_K|BPF_JSET;
  817. last->s.code = NOP;
  818. done = 0;
  819. opt_not(b);
  820. }
  821. /*
  822.  * If the accumulator is a known constant, we can compute the
  823.  * comparison result.
  824.  */
  825. val = b->val[A_ATOM];
  826. if (vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) {
  827. bpf_int32 v = vmap[val].const_val;
  828. switch (BPF_OP(b->s.code)) {
  830. case BPF_JEQ:
  831. v = v == b->s.k;
  832. break;
  834. case BPF_JGT:
  835. v = (unsigned)v > b->s.k;
  836. break;
  838. case BPF_JGE:
  839. v = (unsigned)v >= b->s.k;
  840. break;
  842. case BPF_JSET:
  843. v &= b->s.k;
  844. break;
  846. default:
  847. abort();
  848. }
  849. if (JF(b) != JT(b))
  850. done = 0;
  851. if (v)
  852. JF(b) = JT(b);
  853. else
  854. JT(b) = JF(b);
  855. }
  856. }
  858. /*
  859.  * Compute the symbolic value of expression of 's', and update
  860.  * anything it defines in the value table 'val'.  If 'alter' is true,
  861.  * do various optimizations.  This code would be cleaner if symbolic
  862.  * evaluation and code transformations weren't folded together.
  863.  */
  864. static void
  865. opt_stmt(s, val, alter)
  866. struct stmt *s;
  867. int val[];
  868. int alter;
  869. {
  870. int op;
  871. int v;
  873. switch (s->code) {
  875. case BPF_LD|BPF_ABS|BPF_W:
  876. case BPF_LD|BPF_ABS|BPF_H:
  877. case BPF_LD|BPF_ABS|BPF_B:
  878. v = F(s->code, s->k, 0L);
  879. vstore(s, &val[A_ATOM], v, alter);
  880. break;
  882. case BPF_LD|BPF_IND|BPF_W:
  883. case BPF_LD|BPF_IND|BPF_H:
  884. case BPF_LD|BPF_IND|BPF_B:
  885. v = val[X_ATOM];
  886. if (alter && vmap[v].is_const) {
  887. s->code = BPF_LD|BPF_ABS|BPF_SIZE(s->code);
  888. s->k += vmap[v].const_val;
  889. v = F(s->code, s->k, 0L);
  890. done = 0;
  891. }
  892. else
  893. v = F(s->code, s->k, v);
  894. vstore(s, &val[A_ATOM], v, alter);
  895. break;
  897. case BPF_LD|BPF_LEN:
  898. v = F(s->code, 0L, 0L);
  899. vstore(s, &val[A_ATOM], v, alter);
  900. break;
  902. case BPF_LD|BPF_IMM:
  903. v = K(s->k);
  904. vstore(s, &val[A_ATOM], v, alter);
  905. break;
  907. case BPF_LDX|BPF_IMM:
  908. v = K(s->k);
  909. vstore(s, &val[X_ATOM], v, alter);
  910. break;
  912. case BPF_LDX|BPF_MSH|BPF_B:
  913. v = F(s->code, s->k, 0L);
  914. vstore(s, &val[X_ATOM], v, alter);
  915. break;
  917. case BPF_ALU|BPF_NEG:
  918. if (alter && vmap[val[A_ATOM]].is_const) {
  919. s->code = BPF_LD|BPF_IMM;
  920. s->k = -vmap[val[A_ATOM]].const_val;
  921. val[A_ATOM] = K(s->k);
  922. }
  923. else
  924. val[A_ATOM] = F(s->code, val[A_ATOM], 0L);
  925. break;
  927. case BPF_ALU|BPF_ADD|BPF_K:
  928. case BPF_ALU|BPF_SUB|BPF_K:
  929. case BPF_ALU|BPF_MUL|BPF_K:
  930. case BPF_ALU|BPF_DIV|BPF_K:
  931. case BPF_ALU|BPF_AND|BPF_K:
  932. case BPF_ALU|BPF_OR|BPF_K:
  933. case BPF_ALU|BPF_LSH|BPF_K:
  934. case BPF_ALU|BPF_RSH|BPF_K:
  935. op = BPF_OP(s->code);
  936. if (alter) {
  937. if (s->k == 0) {
  938. if (op == BPF_ADD || op == BPF_SUB ||
  939.     op == BPF_LSH || op == BPF_RSH ||
  940.     op == BPF_OR) {
  941. s->code = NOP;
  942. break;
  943. }
  944. if (op == BPF_MUL || op == BPF_AND) {
  945. s->code = BPF_LD|BPF_IMM;
  946. val[A_ATOM] = K(s->k);
  947. break;
  948. }
  949. }
  950. if (vmap[val[A_ATOM]].is_const) {
  951. fold_op(s, val[A_ATOM], K(s->k));
  952. val[A_ATOM] = K(s->k);
  953. break;
  954. }
  955. }
  956. val[A_ATOM] = F(s->code, val[A_ATOM], K(s->k));
  957. break;
  959. case BPF_ALU|BPF_ADD|BPF_X:
  960. case BPF_ALU|BPF_SUB|BPF_X:
  961. case BPF_ALU|BPF_MUL|BPF_X:
  962. case BPF_ALU|BPF_DIV|BPF_X:
  963. case BPF_ALU|BPF_AND|BPF_X:
  964. case BPF_ALU|BPF_OR|BPF_X:
  965. case BPF_ALU|BPF_LSH|BPF_X:
  966. case BPF_ALU|BPF_RSH|BPF_X:
  967. op = BPF_OP(s->code);
  968. if (alter && vmap[val[X_ATOM]].is_const) {
  969. if (vmap[val[A_ATOM]].is_const) {
  970. fold_op(s, val[A_ATOM], val[X_ATOM]);
  971. val[A_ATOM] = K(s->k);
  972. }
  973. else {
  974. s->code = BPF_ALU|BPF_K|op;
  975. s->k = vmap[val[X_ATOM]].const_val;
  976. done = 0;
  977. val[A_ATOM] =
  978. F(s->code, val[A_ATOM], K(s->k));
  979. }
  980. break;
  981. }
  982. /*
  983.  * Check if we're doing something to an accumulator
  984.  * that is 0, and simplify.  This may not seem like
  985.  * much of a simplification but it could open up further
  986.  * optimizations.
  987.  * XXX We could also check for mul by 1, and -1, etc.
  988.  */
  989. if (alter && vmap[val[A_ATOM]].is_const
  990.     && vmap[val[A_ATOM]].const_val == 0) {
  991. if (op == BPF_ADD || op == BPF_OR ||
  992.     op == BPF_LSH || op == BPF_RSH || op == BPF_SUB) {
  993. s->code = BPF_MISC|BPF_TXA;
  994. vstore(s, &val[A_ATOM], val[X_ATOM], alter);
  995. break;
  996. }
  997. else if (op == BPF_MUL || op == BPF_DIV ||
  998.  op == BPF_AND) {
  999. s->code = BPF_LD|BPF_IMM;
  1000. s->k = 0;
  1001. vstore(s, &val[A_ATOM], K(s->k), alter);
  1002. break;
  1003. }
  1004. else if (op == BPF_NEG) {
  1005. s->code = NOP;
  1006. break;
  1007. }
  1008. }
  1009. val[A_ATOM] = F(s->code, val[A_ATOM], val[X_ATOM]);
  1010. break;
  1012. case BPF_MISC|BPF_TXA:
  1013. vstore(s, &val[A_ATOM], val[X_ATOM], alter);
  1014. break;
  1016. case BPF_LD|BPF_MEM:
  1017. v = val[s->k];
  1018. if (alter && vmap[v].is_const) {
  1019. s->code = BPF_LD|BPF_IMM;
  1020. s->k = vmap[v].const_val;
  1021. done = 0;
  1022. }
  1023. vstore(s, &val[A_ATOM], v, alter);
  1024. break;
  1026. case BPF_MISC|BPF_TAX:
  1027. vstore(s, &val[X_ATOM], val[A_ATOM], alter);
  1028. break;
  1030. case BPF_LDX|BPF_MEM:
  1031. v = val[s->k];
  1032. if (alter && vmap[v].is_const) {
  1033. s->code = BPF_LDX|BPF_IMM;
  1034. s->k = vmap[v].const_val;
  1035. done = 0;
  1036. }
  1037. vstore(s, &val[X_ATOM], v, alter);
  1038. break;
  1040. case BPF_ST:
  1041. vstore(s, &val[s->k], val[A_ATOM], alter);
  1042. break;
  1044. case BPF_STX:
  1045. vstore(s, &val[s->k], val[X_ATOM], alter);
  1046. break;
  1047. }
  1048. }
  1050. static void
  1051. deadstmt(s, last)
  1052. register struct stmt *s;
  1053. register struct stmt *last[];
  1054. {
  1055. register int atom;
  1057. atom = atomuse(s);
  1058. if (atom >= 0) {
  1059. if (atom == AX_ATOM) {
  1060. last[X_ATOM] = 0;
  1061. last[A_ATOM] = 0;
  1062. }
  1063. else
  1064. last[atom] = 0;
  1065. }
  1066. atom = atomdef(s);
  1067. if (atom >= 0) {
  1068. if (last[atom]) {
  1069. done = 0;
  1070. last[atom]->code = NOP;
  1071. }
  1072. last[atom] = s;
  1073. }
  1074. }
  1076. static void
  1077. opt_deadstores(b)
  1078. register struct block *b;
  1079. {
  1080. register struct slist *s;
  1081. register int atom;
  1082. struct stmt *last[N_ATOMS];
  1084. memset((char *)last, 0, sizeof last);
  1086. for (s = b->stmts; s != 0; s = s->next)
  1087. deadstmt(&s->s, last);
  1088. deadstmt(&b->s, last);
  1090. for (atom = 0; atom < N_ATOMS; ++atom)
  1091. if (last[atom] && !ATOMELEM(b->out_use, atom)) {
  1092. last[atom]->code = NOP;
  1093. done = 0;
  1094. }
  1095. }
  1097. static void
  1098. opt_blk(b, do_stmts)
  1099. struct block *b;
  1100. int do_stmts;
  1101. {
  1102. struct slist *s;
  1103. struct edge *p;
  1104. int i;
  1105. bpf_int32 aval;
  1107. /*
  1108.  * Initialize the atom values.
  1109.  * If we have no predecessors, everything is undefined.
  1110.  * Otherwise, we inherent our values from our predecessors.
  1111.  * If any register has an ambiguous value (i.e. control paths are
  1112.  * merging) give it the undefined value of 0.
  1113.  */
  1114. p = b->in_edges;
  1115. if (p == 0)
  1116. memset((char *)b->val, 0, sizeof(b->val));
  1117. else {
  1118. memcpy((char *)b->val, (char *)p->pred->val, sizeof(b->val));
  1119. while ((p = p->next) != NULL) {
  1120. for (i = 0; i < N_ATOMS; ++i)
  1121. if (b->val[i] != p->pred->val[i])
  1122. b->val[i] = 0;
  1123. }
  1124. }
  1125. aval = b->val[A_ATOM];
  1126. for (s = b->stmts; s; s = s->next)
  1127. opt_stmt(&s->s, b->val, do_stmts);
  1129. /*
  1130.  * This is a special case: if we don't use anything from this
  1131.  * block, and we load the accumulator with value that is
  1132.  * already there, or if this block is a return,
  1133.  * eliminate all the statements.
  1134.  */
  1135. if (do_stmts && 
  1136.     ((b->out_use == 0 && aval != 0 &&b->val[A_ATOM] == aval) ||
  1137.      BPF_CLASS(b->s.code) == BPF_RET)) {
  1138. if (b->stmts != 0) {
  1139. b->stmts = 0;
  1140. done = 0;
  1141. }
  1142. } else {
  1143. opt_peep(b);
  1144. opt_deadstores(b);
  1145. }
  1146. /*
  1147.  * Set up values for branch optimizer.
  1148.  */
  1149. if (BPF_SRC(b->s.code) == BPF_K)
  1150. b->oval = K(b->s.k);
  1151. else
  1152. b->oval = b->val[X_ATOM];
  1153. b->et.code = b->s.code;
  1154. b->ef.code = -b->s.code;
  1155. }
  1157. /*
  1158.  * Return true if any register that is used on exit from 'succ', has
  1159.  * an exit value that is different from the corresponding exit value
  1160.  * from 'b'.
  1161.  */
  1162. static int
  1163. use_conflict(b, succ)
  1164. struct block *b, *succ;
  1165. {
  1166. int atom;
  1167. atomset use = succ->out_use;
  1169. if (use == 0)
  1170. return 0;
  1172. for (atom = 0; atom < N_ATOMS; ++atom)
  1173. if (ATOMELEM(use, atom))
  1174. if (b->val[atom] != succ->val[atom])
  1175. return 1;
  1176. return 0;
  1177. }
  1179. static struct block *
  1180. fold_edge(child, ep)
  1181. struct block *child;
  1182. struct edge *ep;
  1183. {
  1184. int sense;
  1185. int aval0, aval1, oval0, oval1;
  1186. int code = ep->code;
  1188. if (code < 0) {
  1189. code = -code;
  1190. sense = 0;
  1191. } else
  1192. sense = 1;
  1194. if (child->s.code != code)
  1195. return 0;
  1197. aval0 = child->val[A_ATOM];
  1198. oval0 = child->oval;
  1199. aval1 = ep->pred->val[A_ATOM];
  1200. oval1 = ep->pred->oval;
  1202. if (aval0 != aval1)
  1203. return 0;
  1205. if (oval0 == oval1)
  1206. /*
  1207.  * The operands are identical, so the
  1208.  * result is true if a true branch was
  1209.  * taken to get here, otherwise false.
  1210.  */
  1211. return sense ? JT(child) : JF(child);
  1213. if (sense && code == (BPF_JMP|BPF_JEQ|BPF_K))
  1214. /*
  1215.  * At this point, we only know the comparison if we
  1216.  * came down the true branch, and it was an equality
  1217.  * comparison with a constant.  We rely on the fact that
  1218.  * distinct constants have distinct value numbers.
  1219.  */
  1220. return JF(child);
  1222. return 0;
  1223. }
  1225. static void
  1226. opt_j(ep)
  1227. struct edge *ep;
  1228. {
  1229. register int i, k;
  1230. register struct block *target;
  1232. if (JT(ep->succ) == 0)
  1233. return;
  1235. if (JT(ep->succ) == JF(ep->succ)) {
  1236. /*
  1237.  * Common branch targets can be eliminated, provided
  1238.  * there is no data dependency.
  1239.  */
  1240. if (!use_conflict(ep->pred, ep->succ->et.succ)) {
  1241. done = 0;
  1242. ep->succ = JT(ep->succ);
  1243. }
  1244. }
  1245. /*
  1246.  * For each edge dominator that matches the successor of this
  1247.  * edge, promote the edge successor to the its grandchild.
  1248.  *
  1249.  * XXX We violate the set abstraction here in favor a reasonably
  1250.  * efficient loop.
  1251.  */
  1252.  top:
  1253. for (i = 0; i < edgewords; ++i) {
  1254. register bpf_u_int32 x = ep->edom[i];
  1256. while (x != 0) {
  1257. k = ffs(x) - 1;
  1258. x &=~ (1 << k);
  1259. k += i * BITS_PER_WORD;
  1261. target = fold_edge(ep->succ, edges[k]);
  1262. /*
  1263.  * Check that there is no data dependency between
  1264.  * nodes that will be violated if we move the edge.
  1265.  */
  1266. if (target != 0 && !use_conflict(ep->pred, target)) {
  1267. done = 0;
  1268. ep->succ = target;
  1269. if (JT(target) != 0)
  1270. /*
  1271.  * Start over unless we hit a leaf.
  1272.  */
  1273. goto top;
  1274. return;
  1275. }
  1276. }
  1277. }
  1278. }
  1281. static void
  1282. or_pullup(b)
  1283. struct block *b;
  1284. {
  1285. int val, at_top;
  1286. struct block *pull;
  1287. struct block **diffp, **samep;
  1288. struct edge *ep;
  1290. ep = b->in_edges;
  1291. if (ep == 0)
  1292. return;
  1294. /*
  1295.  * Make sure each predecessor loads the same value.
  1296.  * XXX why?
  1297.  */
  1298. val = ep->pred->val[A_ATOM];
  1299. for (ep = ep->next; ep != 0; ep = ep->next)
  1300. if (val != ep->pred->val[A_ATOM])
  1301. return;
  1303. if (JT(b->in_edges->pred) == b)
  1304. diffp = &JT(b->in_edges->pred);
  1305. else
  1306. diffp = &JF(b->in_edges->pred);
  1308. at_top = 1;
  1309. while (1) {
  1310. if (*diffp == 0)
  1311. return;
  1313. if (JT(*diffp) != JT(b))
  1314. return;
  1316. if (!SET_MEMBER((*diffp)->dom, b->id))
  1317. return;
  1319. if ((*diffp)->val[A_ATOM] != val)
  1320. break;
  1322. diffp = &JF(*diffp);
  1323. at_top = 0;
  1324. }
  1325. samep = &JF(*diffp);
  1326. while (1) {
  1327. if (*samep == 0)
  1328. return;
  1330. if (JT(*samep) != JT(b))
  1331. return;
  1333. if (!SET_MEMBER((*samep)->dom, b->id))
  1334. return;
  1336. if ((*samep)->val[A_ATOM] == val)
  1337. break;
  1339. /* XXX Need to check that there are no data dependencies
  1340.    between dp0 and dp1.  Currently, the code generator
  1341.    will not produce such dependencies. */
  1342. samep = &JF(*samep);
  1343. }
  1344. #ifdef notdef
  1345. /* XXX This doesn't cover everything. */
  1346. for (i = 0; i < N_ATOMS; ++i)
  1347. if ((*samep)->val[i] != pred->val[i])
  1348. return;
  1349. #endif
  1350. /* Pull up the node. */
  1351. pull = *samep;
  1352. *samep = JF(pull);
  1353. JF(pull) = *diffp;
  1355. /*
  1356.  * At the top of the chain, each predecessor needs to point at the
  1357.  * pulled up node.  Inside the chain, there is only one predecessor
  1358.  * to worry about.
  1359.  */
  1360. if (at_top) {
  1361. for (ep = b->in_edges; ep != 0; ep = ep->next) {
  1362. if (JT(ep->pred) == b)
  1363. JT(ep->pred) = pull;
  1364. else
  1365. JF(ep->pred) = pull;
  1366. }
  1367. }
  1368. else
  1369. *diffp = pull;
  1371. done = 0;
  1372. }
  1374. static void
  1375. and_pullup(b)
  1376. struct block *b;
  1377. {
  1378. int val, at_top;
  1379. struct block *pull;
  1380. struct block **diffp, **samep;
  1381. struct edge *ep;
  1383. ep = b->in_edges;
  1384. if (ep == 0)
  1385. return;
  1387. /*
  1388.  * Make sure each predecessor loads the same value.
  1389.  */
  1390. val = ep->pred->val[A_ATOM];
  1391. for (ep = ep->next; ep != 0; ep = ep->next)
  1392. if (val != ep->pred->val[A_ATOM])
  1393. return;
  1395. if (JT(b->in_edges->pred) == b)
  1396. diffp = &JT(b->in_edges->pred);
  1397. else
  1398. diffp = &JF(b->in_edges->pred);
  1400. at_top = 1;
  1401. while (1) {
  1402. if (*diffp == 0)
  1403. return;
  1405. if (JF(*diffp) != JF(b))
  1406. return;
  1408. if (!SET_MEMBER((*diffp)->dom, b->id))
  1409. return;
  1411. if ((*diffp)->val[A_ATOM] != val)
  1412. break;
  1414. diffp = &JT(*diffp);
  1415. at_top = 0;
  1416. }
  1417. samep = &JT(*diffp);
  1418. while (1) {
  1419. if (*samep == 0)
  1420. return;
  1422. if (JF(*samep) != JF(b))
  1423. return;
  1425. if (!SET_MEMBER((*samep)->dom, b->id))
  1426. return;
  1428. if ((*samep)->val[A_ATOM] == val)
  1429. break;
  1431. /* XXX Need to check that there are no data dependencies
  1432.    between diffp and samep.  Currently, the code generator
  1433.    will not produce such dependencies. */
  1434. samep = &JT(*samep);
  1435. }
  1436. #ifdef notdef
  1437. /* XXX This doesn't cover everything. */
  1438. for (i = 0; i < N_ATOMS; ++i)
  1439. if ((*samep)->val[i] != pred->val[i])
  1440. return;
  1441. #endif
  1442. /* Pull up the node. */
  1443. pull = *samep;
  1444. *samep = JT(pull);
  1445. JT(pull) = *diffp;
  1447. /*
  1448.  * At the top of the chain, each predecessor needs to point at the
  1449.  * pulled up node.  Inside the chain, there is only one predecessor
  1450.  * to worry about.
  1451.  */
  1452. if (at_top) {
  1453. for (ep = b->in_edges; ep != 0; ep = ep->next) {
  1454. if (JT(ep->pred) == b)
  1455. JT(ep->pred) = pull;
  1456. else
  1457. JF(ep->pred) = pull;
  1458. }
  1459. }
  1460. else
  1461. *diffp = pull;
  1463. done = 0;
  1464. }
  1466. static void
  1467. opt_blks(root, do_stmts)
  1468. struct block *root;
  1469. int do_stmts;
  1470. {
  1471. int i, maxlevel;
  1472. struct block *p;
  1474. init_val();
  1475. maxlevel = root->level;
  1476. for (i = maxlevel; i >= 0; --i)
  1477. for (p = levels[i]; p; p = p->link)
  1478. opt_blk(p, do_stmts);
  1480. if (do_stmts)
  1481. /*
  1482.  * No point trying to move branches; it can't possibly
  1483.  * make a difference at this point.
  1484.  */
  1485. return;
  1487. for (i = 1; i <= maxlevel; ++i) {
  1488. for (p = levels[i]; p; p = p->link) {
  1489. opt_j(&p->et);
  1490. opt_j(&p->ef);
  1491. }
  1492. }
  1493. for (i = 1; i <= maxlevel; ++i) {
  1494. for (p = levels[i]; p; p = p->link) {
  1495. or_pullup(p);
  1496. and_pullup(p);
  1497. }
  1498. }
  1499. }
  1501. static inline void
  1502. link_inedge(parent, child)
  1503. struct edge *parent;
  1504. struct block *child;
  1505. {
  1506. parent->next = child->in_edges;
  1507. child->in_edges = parent;
  1508. }
  1510. static void
  1511. find_inedges(root)
  1512. struct block *root;
  1513. {
  1514. int i;
  1515. struct block *b;
  1517. for (i = 0; i < n_blocks; ++i)
  1518. blocks[i]->in_edges = 0;
  1520. /*
  1521.  * Traverse the graph, adding each edge to the predecessor
  1522.  * list of its successors.  Skip the leaves (i.e. level 0).
  1523.  */
  1524. for (i = root->level; i > 0; --i) {
  1525. for (b = levels[i]; b != 0; b = b->link) {
  1526. link_inedge(&b->et, JT(b));
  1527. link_inedge(&b->ef, JF(b));
  1528. }
  1529. }
  1530. }
  1532. static void
  1533. opt_root(b)
  1534. struct block **b;
  1535. {
  1536. struct slist *tmp, *s;
  1538. s = (*b)->stmts;
  1539. (*b)->stmts = 0;
  1540. while (BPF_CLASS((*b)->s.code) == BPF_JMP && JT(*b) == JF(*b))
  1541. *b = JT(*b);
  1543. tmp = (*b)->stmts;
  1544. if (tmp != 0)
  1545. sappend(s, tmp);
  1546. (*b)->stmts = s;
  1548. /*
  1549.  * If the root node is a return, then there is no
  1550.  * point executing any statements (since the bpf machine
  1551.  * has no side effects).
  1552.  */
  1553. if (BPF_CLASS((*b)->s.code) == BPF_RET)
  1554. (*b)->stmts = 0;
  1555. }
  1557. static void
  1558. opt_loop(root, do_stmts)
  1559. struct block *root;
  1560. int do_stmts;
  1561. {
  1563. #ifdef BDEBUG
  1564. if (dflag > 1)
  1565. opt_dump(root);
  1566. #endif
  1567. do {
  1568. done = 1;
  1569. find_levels(root);
  1570. find_dom(root);
  1571. find_closure(root);
  1572. find_inedges(root);
  1573. find_ud(root);
  1574. find_edom(root);
  1575. opt_blks(root, do_stmts);
  1576. #ifdef BDEBUG
  1577. if (dflag > 1)
  1578. opt_dump(root);
  1579. #endif
  1580. } while (!done);
  1581. }
  1583. /*
  1584.  * Optimize the filter code in its dag representation.
  1585.  */
  1586. void
  1587. bpf_optimize(rootp)
  1588. struct block **rootp;
  1589. {
  1590. struct block *root;
  1592. root = *rootp;
  1594. opt_init(root);
  1595. opt_loop(root, 0);
  1596. opt_loop(root, 1);
  1597. intern_blocks(root);
  1598. opt_root(rootp);
  1599. opt_cleanup();
  1600. }
  1602. static void
  1603. make_marks(p)
  1604. struct block *p;
  1605. {
  1606. if (!isMarked(p)) {
  1607. Mark(p);
  1608. if (BPF_CLASS(p->s.code) != BPF_RET) {
  1609. make_marks(JT(p));
  1610. make_marks(JF(p));
  1611. }
  1612. }
  1613. }
  1615. /*
  1616.  * Mark code array such that isMarked(i) is true
  1617.  * only for nodes that are alive.
  1618.  */
  1619. static void
  1620. mark_code(p)
  1621. struct block *p;
  1622. {
  1623. cur_mark += 1;
  1624. make_marks(p);
  1625. }
  1627. /*
  1628.  * True iff the two stmt lists load the same value from the packet into
  1629.  * the accumulator.
  1630.  */
  1631. static int
  1632. eq_slist(x, y)
  1633. struct slist *x, *y;
  1634. {
  1635. while (1) {
  1636. while (x && x->s.code == NOP)
  1637. x = x->next;
  1638. while (y && y->s.code == NOP)
  1639. y = y->next;
  1640. if (x == 0)
  1641. return y == 0;
  1642. if (y == 0)
  1643. return x == 0;
  1644. if (x->s.code != y->s.code || x->s.k != y->s.k)
  1645. return 0;
  1646. x = x->next;
  1647. y = y->next;
  1648. }
  1649. }
  1651. static inline int
  1652. eq_blk(b0, b1)
  1653. struct block *b0, *b1;
  1654. {
  1655. if (b0->s.code == b1->s.code &&
  1656.     b0->s.k == b1->s.k &&
  1657.     b0->et.succ == b1->et.succ &&
  1658.     b0->ef.succ == b1->ef.succ)
  1659. return eq_slist(b0->stmts, b1->stmts);
  1660. return 0;
  1661. }
  1663. static void
  1664. intern_blocks(root)
  1665. struct block *root;
  1666. {
  1667. struct block *p;
  1668. int i, j;
  1669. int done;
  1670.  top:
  1671. done = 1;
  1672. for (i = 0; i < n_blocks; ++i)
  1673. blocks[i]->link = 0;
  1675. mark_code(root);
  1677. for (i = n_blocks - 1; --i >= 0; ) {
  1678. if (!isMarked(blocks[i]))
  1679. continue;
  1680. for (j = i + 1; j < n_blocks; ++j) {
  1681. if (!isMarked(blocks[j]))
  1682. continue;
  1683. if (eq_blk(blocks[i], blocks[j])) {
  1684. blocks[i]->link = blocks[j]->link ?
  1685. blocks[j]->link : blocks[j];
  1686. break;
  1687. }
  1688. }
  1689. }
  1690. for (i = 0; i < n_blocks; ++i) {
  1691. p = blocks[i];
  1692. if (JT(p) == 0)
  1693. continue;
  1694. if (JT(p)->link) {
  1695. done = 0;
  1696. JT(p) = JT(p)->link;
  1697. }
  1698. if (JF(p)->link) {
  1699. done = 0;
  1700. JF(p) = JF(p)->link;
  1701. }
  1702. }
  1703. if (!done)
  1704. goto top;
  1705. }
  1707. static void
  1708. opt_cleanup()
  1709. {
  1710. free((void *)vnode_base);
  1711. free((void *)vmap);
  1712. free((void *)edges);
  1713. free((void *)space);
  1714. free((void *)levels);
  1715. free((void *)blocks);
  1716. }
  1718. /*
  1719.  * Return the number of stmts in 's'.
  1720.  */
  1721. static int
  1722. slength(s)
  1723. struct slist *s;
  1724. {
  1725. int n = 0;
  1727. for (; s; s = s->next)
  1728. if (s->s.code != NOP)
  1729. ++n;
  1730. return n;
  1731. }
  1733. /*
  1734.  * Return the number of nodes reachable by 'p'.
  1735.  * All nodes should be initially unmarked.
  1736.  */
  1737. static int
  1738. count_blocks(p)
  1739. struct block *p;
  1740. {
  1741. if (p == 0 || isMarked(p))
  1742. return 0;
  1743. Mark(p);
  1744. return count_blocks(JT(p)) + count_blocks(JF(p)) + 1;
  1745. }
  1747. /*
  1748.  * Do a depth first search on the flow graph, numbering the
  1749.  * the basic blocks, and entering them into the 'blocks' array.`
  1750.  */
  1751. static void
  1752. number_blks_r(p)
  1753. struct block *p;
  1754. {
  1755. int n;
  1757. if (p == 0 || isMarked(p))
  1758. return;
  1760. Mark(p);
  1761. n = n_blocks++;
  1762. p->id = n;
  1763. blocks[n] = p;
  1765. number_blks_r(JT(p));
  1766. number_blks_r(JF(p));
  1767. }
  1769. /*
  1770.  * Return the number of stmts in the flowgraph reachable by 'p'.
  1771.  * The nodes should be unmarked before calling.
  1772.  */
  1773. static int
  1774. count_stmts(p)
  1775. struct block *p;
  1776. {
  1777. int n;
  1779. if (p == 0 || isMarked(p))
  1780. return 0;
  1781. Mark(p);
  1782. n = count_stmts(JT(p)) + count_stmts(JF(p));
  1783. return slength(p->stmts) + n + 1;
  1784. }
  1786. /*
  1787.  * Allocate memory.  All allocation is done before optimization
  1788.  * is begun.  A linear bound on the size of all data structures is computed
  1789.  * from the total number of blocks and/or statements.
  1790.  */
  1791. static void
  1792. opt_init(root)
  1793. struct block *root;
  1794. {
  1795. bpf_u_int32 *p;
  1796. int i, n, max_stmts;
  1798. /*
  1799.  * First, count the blocks, so we can malloc an array to map
  1800.  * block number to block.  Then, put the blocks into the array.
  1801.  */
  1802. unMarkAll();
  1803. n = count_blocks(root);
  1804. blocks = (struct block **)malloc(n * sizeof(*blocks));
  1805. unMarkAll();
  1806. n_blocks = 0;
  1807. number_blks_r(root);
  1809. n_edges = 2 * n_blocks;
  1810. edges = (struct edge **)malloc(n_edges * sizeof(*edges));
  1812. /*
  1813.  * The number of levels is bounded by the number of nodes.
  1814.  */
  1815. levels = (struct block **)malloc(n_blocks * sizeof(*levels));
  1817. edgewords = n_edges / (8 * sizeof(bpf_u_int32)) + 1;
  1818. nodewords = n_blocks / (8 * sizeof(bpf_u_int32)) + 1;
  1820. /* XXX */
  1821. space = (bpf_u_int32 *)malloc(2 * n_blocks * nodewords * sizeof(*space)
  1822.  + n_edges * edgewords * sizeof(*space));
  1823. p = space;
  1824. all_dom_sets = p;
  1825. for (i = 0; i < n; ++i) {
  1826. blocks[i]->dom = p;
  1827. p += nodewords;
  1828. }
  1829. all_closure_sets = p;
  1830. for (i = 0; i < n; ++i) {
  1831. blocks[i]->closure = p;
  1832. p += nodewords;
  1833. }
  1834. all_edge_sets = p;
  1835. for (i = 0; i < n; ++i) {
  1836. register struct block *b = blocks[i];
  1838. b->et.edom = p;
  1839. p += edgewords;
  1840. b->ef.edom = p;
  1841. p += edgewords;
  1842. b->et.id = i;
  1843. edges[i] = &b->et;
  1844. b->ef.id = n_blocks + i;
  1845. edges[n_blocks + i] = &b->ef;
  1846. b->et.pred = b;
  1847. b->ef.pred = b;
  1848. }
  1849. max_stmts = 0;
  1850. for (i = 0; i < n; ++i)
  1851. max_stmts += slength(blocks[i]->stmts) + 1;
  1852. /*
  1853.  * We allocate at most 3 value numbers per statement,
  1854.  * so this is an upper bound on the number of valnodes
  1855.  * we'll need.
  1856.  */
  1857. maxval = 3 * max_stmts;
  1858. vmap = (struct vmapinfo *)malloc(maxval * sizeof(*vmap));
  1859. vnode_base = (struct valnode *)malloc(maxval * sizeof(*vmap));
  1860. }
  1862. /*
  1863.  * Some pointers used to convert the basic block form of the code,
  1864.  * into the array form that BPF requires.  'fstart' will point to
  1865.  * the malloc'd array while 'ftail' is used during the recursive traversal.
  1866.  */
  1867. static struct bpf_insn *fstart;
  1868. static struct bpf_insn *ftail;
  1870. #ifdef BDEBUG
  1871. int bids[1000];
  1872. #endif
  1874. /*
  1875.  * Returns true if successful.  Returns false if a branch has
  1876.  * an offset that is too large.  If so, we have marked that
  1877.  * branch so that on a subsequent iteration, it will be treated
  1878.  * properly.
  1879.  */
  1880. static int
  1881. convert_code_r(p)
  1882. struct block *p;
  1883. {
  1884. struct bpf_insn *dst;
  1885. struct slist *src;
  1886. int slen;
  1887. u_int off;
  1888. int extrajmps; /* number of extra jumps inserted */
  1890. if (p == 0 || isMarked(p))
  1891. return (1);
  1892. Mark(p);
  1894. if (convert_code_r(JF(p)) == 0)
  1895. return (0);
  1896. if (convert_code_r(JT(p)) == 0)
  1897. return (0);
  1899. slen = slength(p->stmts);
  1900. dst = ftail -= (slen + 1 + p->longjt + p->longjf);
  1901. /* inflate length by any extra jumps */
  1903. p->offset = dst - fstart;
  1905. for (src = p->stmts; src; src = src->next) {
  1906. if (src->s.code == NOP)
  1907. continue;
  1908. dst->code = (u_short)src->s.code;
  1909. dst->k = src->s.k;
  1910. ++dst;
  1911. }
  1912. #ifdef BDEBUG
  1913. bids[dst - fstart] = p->id + 1;
  1914. #endif
  1915. dst->code = (u_short)p->s.code;
  1916. dst->k = p->s.k;
  1917. if (JT(p)) {
  1918. extrajmps = 0;
  1919. off = JT(p)->offset - (p->offset + slen) - 1;
  1920. if (off >= 256) {
  1921.     /* offset too large for branch, must add a jump */
  1922.     if (p->longjt == 0) {
  1923.      /* mark this instruction and retry */
  1924. p->longjt++;
  1925. return(0);
  1926.     }
  1927.     /* branch if T to following jump */
  1928.     dst->jt = extrajmps;
  1929.     extrajmps++;
  1930.     dst[extrajmps].code = BPF_JMP|BPF_JA;
  1931.     dst[extrajmps].k = off - extrajmps;
  1932. }
  1933. else
  1934.     dst->jt = off;
  1935. off = JF(p)->offset - (p->offset + slen) - 1;
  1936. if (off >= 256) {
  1937.     /* offset too large for branch, must add a jump */
  1938.     if (p->longjf == 0) {
  1939.      /* mark this instruction and retry */
  1940. p->longjf++;
  1941. return(0);
  1942.     }
  1943.     /* branch if F to following jump */
  1944.     /* if two jumps are inserted, F goes to second one */
  1945.     dst->jf = extrajmps;
  1946.     extrajmps++;
  1947.     dst[extrajmps].code = BPF_JMP|BPF_JA;
  1948.     dst[extrajmps].k = off - extrajmps;
  1949. }
  1950. else
  1951.     dst->jf = off;
  1952. }
  1953. return (1);
  1954. }
  1957. /*
  1958.  * Convert flowgraph intermediate representation to the
  1959.  * BPF array representation.  Set *lenp to the number of instructions.
  1960.  */
  1961. struct bpf_insn *
  1962. icode_to_fcode(root, lenp)
  1963. struct block *root;
  1964. int *lenp;
  1965. {
  1966. int n;
  1967. struct bpf_insn *fp;
  1969. /*
  1970.  * Loop doing convert_codr_r() until no branches remain
  1971.  * with too-large offsets.
  1972.  */
  1973. while (1) {
  1974.     unMarkAll();
  1975.     n = *lenp = count_stmts(root);
  1976.     
  1977.     fp = (struct bpf_insn *)malloc(sizeof(*fp) * n);
  1978.     memset((char *)fp, 0, sizeof(*fp) * n);
  1979.     fstart = fp;
  1980.     ftail = fp + n;
  1981.     
  1982.     unMarkAll();
  1983.     if (convert_code_r(root))
  1984. break;
  1985.     free(fp);
  1986. }
  1988. return fp;
  1989. }
  1991. #ifdef BDEBUG
  1992. static void
  1993. opt_dump(root)
  1994. struct block *root;
  1995. {
  1996. struct bpf_program f;
  1998. memset(bids, 0, sizeof bids);
  1999. f.bf_insns = icode_to_fcode(root, &f.bf_len);
  2000. bpf_dump(&f, 1);
  2001. putchar('n');
  2002. free((char *)f.bf_insns);
  2003. }
  2004. #endif