Lines Matching refs:opt_state
222 #define K(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0L)
362 find_levels_r(opt_state_t *opt_state, struct icode *ic, struct block *b) in find_levels_r() argument
373 find_levels_r(opt_state, ic, JT(b)); in find_levels_r()
374 find_levels_r(opt_state, ic, JF(b)); in find_levels_r()
379 b->link = opt_state->levels[level]; in find_levels_r()
380 opt_state->levels[level] = b; in find_levels_r()
390 find_levels(opt_state_t *opt_state, struct icode *ic) in find_levels() argument
392 memset((char *)opt_state->levels, 0, opt_state->n_blocks * sizeof(*opt_state->levels)); in find_levels()
394 find_levels_r(opt_state, ic, ic->root); in find_levels()
402 find_dom(opt_state_t *opt_state, struct block *root) in find_dom() argument
411 x = opt_state->all_dom_sets; in find_dom()
412 i = opt_state->n_blocks * opt_state->nodewords; in find_dom()
416 for (i = opt_state->nodewords; --i >= 0;) in find_dom()
421 for (b = opt_state->levels[i]; b; b = b->link) { in find_dom()
425 SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords); in find_dom()
426 SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords); in find_dom()
432 propedom(opt_state_t *opt_state, struct edge *ep) in propedom() argument
436 SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords); in propedom()
437 SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords); in propedom()
446 find_edom(opt_state_t *opt_state, struct block *root) in find_edom() argument
452 x = opt_state->all_edge_sets; in find_edom()
453 for (i = opt_state->n_edges * opt_state->edgewords; --i >= 0; ) in find_edom()
457 memset(root->et.edom, 0, opt_state->edgewords * sizeof(*(uset)0)); in find_edom()
458 memset(root->ef.edom, 0, opt_state->edgewords * sizeof(*(uset)0)); in find_edom()
460 for (b = opt_state->levels[i]; b != 0; b = b->link) { in find_edom()
461 propedom(opt_state, &b->et); in find_edom()
462 propedom(opt_state, &b->ef); in find_edom()
475 find_closure(opt_state_t *opt_state, struct block *root) in find_closure() argument
483 memset((char *)opt_state->all_closure_sets, 0, in find_closure()
484 opt_state->n_blocks * opt_state->nodewords * sizeof(*opt_state->all_closure_sets)); in find_closure()
488 for (b = opt_state->levels[i]; b; b = b->link) { in find_closure()
492 SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords); in find_closure()
493 SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords); in find_closure()
647 find_ud(opt_state_t *opt_state, struct block *root) in find_ud() argument
658 for (p = opt_state->levels[i]; p; p = p->link) { in find_ud()
664 for (p = opt_state->levels[i]; p; p = p->link) { in find_ud()
671 init_val(opt_state_t *opt_state) in init_val() argument
673 opt_state->curval = 0; in init_val()
674 opt_state->next_vnode = opt_state->vnode_base; in init_val()
675 memset((char *)opt_state->vmap, 0, opt_state->maxval * sizeof(*opt_state->vmap)); in init_val()
676 memset((char *)opt_state->hashtbl, 0, sizeof opt_state->hashtbl); in init_val()
681 F(opt_state_t *opt_state, int code, int v0, int v1) in F() argument
690 for (p = opt_state->hashtbl[hash]; p; p = p->next) in F()
694 val = ++opt_state->curval; in F()
697 opt_state->vmap[val].const_val = v0; in F()
698 opt_state->vmap[val].is_const = 1; in F()
700 p = opt_state->next_vnode++; in F()
705 p->next = opt_state->hashtbl[hash]; in F()
706 opt_state->hashtbl[hash] = p; in F()
725 fold_op(opt_state_t *opt_state, struct stmt *s, int v0, int v1) in fold_op() argument
729 a = opt_state->vmap[v0].const_val; in fold_op()
730 b = opt_state->vmap[v1].const_val; in fold_op()
747 opt_error(opt_state, "division by zero"); in fold_op()
753 opt_error(opt_state, "modulus by zero"); in fold_op()
810 opt_state->done = 0; in fold_op()
831 opt_peep(opt_state_t *opt_state, struct block *b) in opt_peep() argument
866 opt_state->done = 0; in opt_peep()
877 opt_state->done = 0; in opt_peep()
956 opt_state->done = 0; in opt_peep()
974 if (opt_state->vmap[val].is_const) { in opt_peep()
984 b->s.k += opt_state->vmap[val].const_val; in opt_peep()
986 opt_state->done = 0; in opt_peep()
999 opt_state->done = 0; in opt_peep()
1011 opt_state->done = 0; in opt_peep()
1025 opt_state->done = 0; in opt_peep()
1045 if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_X) { in opt_peep()
1046 bpf_int32 v = opt_state->vmap[val].const_val; in opt_peep()
1055 if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) { in opt_peep()
1056 bpf_int32 v = opt_state->vmap[val].const_val; in opt_peep()
1079 opt_state->done = 0; in opt_peep()
1094 opt_stmt(opt_state_t *opt_state, struct stmt *s, int val[], int alter) in opt_stmt() argument
1104 v = F(opt_state, s->code, s->k, 0L); in opt_stmt()
1112 if (alter && opt_state->vmap[v].is_const) { in opt_stmt()
1114 s->k += opt_state->vmap[v].const_val; in opt_stmt()
1115 v = F(opt_state, s->code, s->k, 0L); in opt_stmt()
1116 opt_state->done = 0; in opt_stmt()
1119 v = F(opt_state, s->code, s->k, v); in opt_stmt()
1124 v = F(opt_state, s->code, 0L, 0L); in opt_stmt()
1139 v = F(opt_state, s->code, s->k, 0L); in opt_stmt()
1144 if (alter && opt_state->vmap[val[A_ATOM]].is_const) { in opt_stmt()
1162 s->k = 0U - (bpf_u_int32)(opt_state->vmap[val[A_ATOM]].const_val); in opt_stmt()
1166 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], 0L); in opt_stmt()
1205 opt_error(opt_state, in opt_stmt()
1208 opt_error(opt_state, in opt_stmt()
1211 if (opt_state->vmap[val[A_ATOM]].is_const) { in opt_stmt()
1212 fold_op(opt_state, s, val[A_ATOM], K(s->k)); in opt_stmt()
1217 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], K(s->k)); in opt_stmt()
1231 if (alter && opt_state->vmap[val[X_ATOM]].is_const) { in opt_stmt()
1232 if (opt_state->vmap[val[A_ATOM]].is_const) { in opt_stmt()
1233 fold_op(opt_state, s, val[A_ATOM], val[X_ATOM]); in opt_stmt()
1238 s->k = opt_state->vmap[val[X_ATOM]].const_val; in opt_stmt()
1247 opt_error(opt_state, in opt_stmt()
1249 opt_state->done = 0; in opt_stmt()
1251 F(opt_state, s->code, val[A_ATOM], K(s->k)); in opt_stmt()
1262 if (alter && opt_state->vmap[val[A_ATOM]].is_const in opt_stmt()
1263 && opt_state->vmap[val[A_ATOM]].const_val == 0) { in opt_stmt()
1281 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], val[X_ATOM]); in opt_stmt()
1290 if (alter && opt_state->vmap[v].is_const) { in opt_stmt()
1292 s->k = opt_state->vmap[v].const_val; in opt_stmt()
1293 opt_state->done = 0; in opt_stmt()
1304 if (alter && opt_state->vmap[v].is_const) { in opt_stmt()
1306 s->k = opt_state->vmap[v].const_val; in opt_stmt()
1307 opt_state->done = 0; in opt_stmt()
1323 deadstmt(opt_state_t *opt_state, register struct stmt *s, register struct stmt *last[]) in deadstmt() argument
1339 opt_state->done = 0; in deadstmt()
1347 opt_deadstores(opt_state_t *opt_state, register struct block *b) in opt_deadstores() argument
1356 deadstmt(opt_state, &s->s, last); in opt_deadstores()
1357 deadstmt(opt_state, &b->s, last); in opt_deadstores()
1362 opt_state->done = 0; in opt_deadstores()
1367 opt_blk(opt_state_t *opt_state, struct block *b, int do_stmts) in opt_blk() argument
1417 opt_stmt(opt_state, &s->s, b->val, do_stmts); in opt_blk()
1449 opt_state->done = 0; in opt_blk()
1452 opt_peep(opt_state, b); in opt_blk()
1453 opt_deadstores(opt_state, b); in opt_blk()
1540 opt_j(opt_state_t *opt_state, struct edge *ep) in opt_j() argument
1554 opt_state->done = 0; in opt_j()
1566 for (i = 0; i < opt_state->edgewords; ++i) { in opt_j()
1574 target = fold_edge(ep->succ, opt_state->edges[k]); in opt_j()
1580 opt_state->done = 0; in opt_j()
1595 or_pullup(opt_state_t *opt_state, struct block *b) in or_pullup() argument
1683 opt_state->done = 0; in or_pullup()
1687 and_pullup(opt_state_t *opt_state, struct block *b) in and_pullup() argument
1774 opt_state->done = 0; in and_pullup()
1778 opt_blks(opt_state_t *opt_state, struct icode *ic, int do_stmts) in opt_blks() argument
1783 init_val(opt_state); in opt_blks()
1786 find_inedges(opt_state, ic->root); in opt_blks()
1788 for (p = opt_state->levels[i]; p; p = p->link) in opt_blks()
1789 opt_blk(opt_state, p, do_stmts); in opt_blks()
1799 for (p = opt_state->levels[i]; p; p = p->link) { in opt_blks()
1800 opt_j(opt_state, &p->et); in opt_blks()
1801 opt_j(opt_state, &p->ef); in opt_blks()
1805 find_inedges(opt_state, ic->root); in opt_blks()
1807 for (p = opt_state->levels[i]; p; p = p->link) { in opt_blks()
1808 or_pullup(opt_state, p); in opt_blks()
1809 and_pullup(opt_state, p); in opt_blks()
1822 find_inedges(opt_state_t *opt_state, struct block *root) in find_inedges() argument
1827 for (i = 0; i < opt_state->n_blocks; ++i) in find_inedges()
1828 opt_state->blocks[i]->in_edges = 0; in find_inedges()
1835 for (b = opt_state->levels[i]; b != 0; b = b->link) { in find_inedges()
1867 opt_loop(opt_state_t *opt_state, struct icode *ic, int do_stmts) in opt_loop() argument
1873 opt_dump(opt_state, ic); in opt_loop()
1877 opt_state->done = 1; in opt_loop()
1878 find_levels(opt_state, ic); in opt_loop()
1879 find_dom(opt_state, ic->root); in opt_loop()
1880 find_closure(opt_state, ic->root); in opt_loop()
1881 find_ud(opt_state, ic->root); in opt_loop()
1882 find_edom(opt_state, ic->root); in opt_loop()
1883 opt_blks(opt_state, ic, do_stmts); in opt_loop()
1886 printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, opt_state->done); in opt_loop()
1887 opt_dump(opt_state, ic); in opt_loop()
1890 } while (!opt_state->done); in opt_loop()
1900 opt_state_t opt_state; in bpf_optimize() local
1902 memset(&opt_state, 0, sizeof(opt_state)); in bpf_optimize()
1903 opt_state.errbuf = errbuf; in bpf_optimize()
1904 if (setjmp(opt_state.top_ctx)) { in bpf_optimize()
1905 opt_cleanup(&opt_state); in bpf_optimize()
1908 opt_init(&opt_state, ic); in bpf_optimize()
1909 opt_loop(&opt_state, ic, 0); in bpf_optimize()
1910 opt_loop(&opt_state, ic, 1); in bpf_optimize()
1911 intern_blocks(&opt_state, ic); in bpf_optimize()
1915 opt_dump(&opt_state, ic); in bpf_optimize()
1922 opt_dump(&opt_state, ic); in bpf_optimize()
1925 opt_cleanup(&opt_state); in bpf_optimize()
1987 intern_blocks(opt_state_t *opt_state, struct icode *ic) in intern_blocks() argument
1994 for (i = 0; i < opt_state->n_blocks; ++i) in intern_blocks()
1995 opt_state->blocks[i]->link = 0; in intern_blocks()
1999 for (i = opt_state->n_blocks - 1; --i >= 0; ) { in intern_blocks()
2000 if (!isMarked(ic, opt_state->blocks[i])) in intern_blocks()
2002 for (j = i + 1; j < opt_state->n_blocks; ++j) { in intern_blocks()
2003 if (!isMarked(ic, opt_state->blocks[j])) in intern_blocks()
2005 if (eq_blk(opt_state->blocks[i], opt_state->blocks[j])) { in intern_blocks()
2006 opt_state->blocks[i]->link = opt_state->blocks[j]->link ? in intern_blocks()
2007 opt_state->blocks[j]->link : opt_state->blocks[j]; in intern_blocks()
2012 for (i = 0; i < opt_state->n_blocks; ++i) { in intern_blocks()
2013 p = opt_state->blocks[i]; in intern_blocks()
2030 opt_cleanup(opt_state_t *opt_state) in opt_cleanup() argument
2032 free((void *)opt_state->vnode_base); in opt_cleanup()
2033 free((void *)opt_state->vmap); in opt_cleanup()
2034 free((void *)opt_state->edges); in opt_cleanup()
2035 free((void *)opt_state->space); in opt_cleanup()
2036 free((void *)opt_state->levels); in opt_cleanup()
2037 free((void *)opt_state->blocks); in opt_cleanup()
2044 opt_error(opt_state_t *opt_state, const char *fmt, ...) in opt_error() argument
2048 if (opt_state->errbuf != NULL) { in opt_error()
2050 (void)pcap_vsnprintf(opt_state->errbuf, in opt_error()
2054 longjmp(opt_state->top_ctx, 1); in opt_error()
2090 number_blks_r(opt_state_t *opt_state, struct icode *ic, struct block *p) in number_blks_r() argument
2098 n = opt_state->n_blocks++; in number_blks_r()
2100 opt_state->blocks[n] = p; in number_blks_r()
2102 number_blks_r(opt_state, ic, JT(p)); in number_blks_r()
2103 number_blks_r(opt_state, ic, JF(p)); in number_blks_r()
2142 opt_init(opt_state_t *opt_state, struct icode *ic) in opt_init() argument
2153 opt_state->blocks = (struct block **)calloc(n, sizeof(*opt_state->blocks)); in opt_init()
2154 if (opt_state->blocks == NULL) in opt_init()
2155 opt_error(opt_state, "malloc"); in opt_init()
2157 opt_state->n_blocks = 0; in opt_init()
2158 number_blks_r(opt_state, ic, ic->root); in opt_init()
2160 opt_state->n_edges = 2 * opt_state->n_blocks; in opt_init()
2161 opt_state->edges = (struct edge **)calloc(opt_state->n_edges, sizeof(*opt_state->edges)); in opt_init()
2162 if (opt_state->edges == NULL) { in opt_init()
2163 opt_error(opt_state, "malloc"); in opt_init()
2169 opt_state->levels = (struct block **)calloc(opt_state->n_blocks, sizeof(*opt_state->levels)); in opt_init()
2170 if (opt_state->levels == NULL) { in opt_init()
2171 opt_error(opt_state, "malloc"); in opt_init()
2174 opt_state->edgewords = opt_state->n_edges / (8 * sizeof(bpf_u_int32)) + 1; in opt_init()
2175 opt_state->nodewords = opt_state->n_blocks / (8 * sizeof(bpf_u_int32)) + 1; in opt_init()
2178 …opt_state->space = (bpf_u_int32 *)malloc(2 * opt_state->n_blocks * opt_state->nodewords * sizeof(*… in opt_init()
2179 + opt_state->n_edges * opt_state->edgewords * sizeof(*opt_state->space)); in opt_init()
2180 if (opt_state->space == NULL) { in opt_init()
2181 opt_error(opt_state, "malloc"); in opt_init()
2183 p = opt_state->space; in opt_init()
2184 opt_state->all_dom_sets = p; in opt_init()
2186 opt_state->blocks[i]->dom = p; in opt_init()
2187 p += opt_state->nodewords; in opt_init()
2189 opt_state->all_closure_sets = p; in opt_init()
2191 opt_state->blocks[i]->closure = p; in opt_init()
2192 p += opt_state->nodewords; in opt_init()
2194 opt_state->all_edge_sets = p; in opt_init()
2196 register struct block *b = opt_state->blocks[i]; in opt_init()
2199 p += opt_state->edgewords; in opt_init()
2201 p += opt_state->edgewords; in opt_init()
2203 opt_state->edges[i] = &b->et; in opt_init()
2204 b->ef.id = opt_state->n_blocks + i; in opt_init()
2205 opt_state->edges[opt_state->n_blocks + i] = &b->ef; in opt_init()
2211 max_stmts += slength(opt_state->blocks[i]->stmts) + 1; in opt_init()
2217 opt_state->maxval = 3 * max_stmts; in opt_init()
2218 opt_state->vmap = (struct vmapinfo *)calloc(opt_state->maxval, sizeof(*opt_state->vmap)); in opt_init()
2219 if (opt_state->vmap == NULL) { in opt_init()
2220 opt_error(opt_state, "malloc"); in opt_init()
2222 …opt_state->vnode_base = (struct valnode *)calloc(opt_state->maxval, sizeof(*opt_state->vnode_base)… in opt_init()
2223 if (opt_state->vnode_base == NULL) { in opt_init()
2224 opt_error(opt_state, "malloc"); in opt_init()
2648 opt_dump(opt_state_t *opt_state, struct icode *ic) in opt_dump() argument
2662 opt_error(opt_state, "opt_dump: icode_to_fcode failed: %s", errbuf); in opt_dump()