Lines Matching refs:opt_state
221 #define K(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)
377 find_levels_r(opt_state_t *opt_state, struct icode *ic, struct block *b) in find_levels_r() argument
388 find_levels_r(opt_state, ic, JT(b)); in find_levels_r()
389 find_levels_r(opt_state, ic, JF(b)); in find_levels_r()
394 b->link = opt_state->levels[level]; in find_levels_r()
395 opt_state->levels[level] = b; in find_levels_r()
405 find_levels(opt_state_t *opt_state, struct icode *ic) in find_levels() argument
407 memset((char *)opt_state->levels, 0, opt_state->n_blocks * sizeof(*opt_state->levels)); in find_levels()
409 find_levels_r(opt_state, ic, ic->root); in find_levels()
417 find_dom(opt_state_t *opt_state, struct block *root) in find_dom() argument
427 x = opt_state->all_dom_sets; in find_dom()
431 i = opt_state->n_blocks * opt_state->nodewords; in find_dom()
437 for (i = opt_state->nodewords; i != 0;) { in find_dom()
444 for (b = opt_state->levels[level]; b; b = b->link) { in find_dom()
448 SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords); in find_dom()
449 SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords); in find_dom()
455 propedom(opt_state_t *opt_state, struct edge *ep) in propedom() argument
459 SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords); in propedom()
460 SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords); in propedom()
469 find_edom(opt_state_t *opt_state, struct block *root) in find_edom() argument
476 x = opt_state->all_edge_sets; in find_edom()
480 for (i = opt_state->n_edges * opt_state->edgewords; i != 0; ) { in find_edom()
486 memset(root->et.edom, 0, opt_state->edgewords * sizeof(*(uset)0)); in find_edom()
487 memset(root->ef.edom, 0, opt_state->edgewords * sizeof(*(uset)0)); in find_edom()
489 for (b = opt_state->levels[level]; b != 0; b = b->link) { in find_edom()
490 propedom(opt_state, &b->et); in find_edom()
491 propedom(opt_state, &b->ef); in find_edom()
504 find_closure(opt_state_t *opt_state, struct block *root) in find_closure() argument
512 memset((char *)opt_state->all_closure_sets, 0, in find_closure()
513 opt_state->n_blocks * opt_state->nodewords * sizeof(*opt_state->all_closure_sets)); in find_closure()
517 for (b = opt_state->levels[level]; b; b = b->link) { in find_closure()
521 SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords); in find_closure()
522 SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords); in find_closure()
683 find_ud(opt_state_t *opt_state, struct block *root) in find_ud() argument
694 for (p = opt_state->levels[i]; p; p = p->link) { in find_ud()
700 for (p = opt_state->levels[i]; p; p = p->link) { in find_ud()
707 init_val(opt_state_t *opt_state) in init_val() argument
709 opt_state->curval = 0; in init_val()
710 opt_state->next_vnode = opt_state->vnode_base; in init_val()
711 memset((char *)opt_state->vmap, 0, opt_state->maxval * sizeof(*opt_state->vmap)); in init_val()
712 memset((char *)opt_state->hashtbl, 0, sizeof opt_state->hashtbl); in init_val()
725 F(opt_state_t *opt_state, int code, bpf_u_int32 v0, bpf_u_int32 v1) in F() argument
734 for (p = opt_state->hashtbl[hash]; p; p = p->next) in F()
749 val = ++opt_state->curval; in F()
752 opt_state->vmap[val].const_val = v0; in F()
753 opt_state->vmap[val].is_const = 1; in F()
755 p = opt_state->next_vnode++; in F()
760 p->next = opt_state->hashtbl[hash]; in F()
761 opt_state->hashtbl[hash] = p; in F()
780 fold_op(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 v0, bpf_u_int32 v1) in fold_op() argument
784 a = opt_state->vmap[v0].const_val; in fold_op()
785 b = opt_state->vmap[v1].const_val; in fold_op()
802 opt_error(opt_state, "division by zero"); in fold_op()
808 opt_error(opt_state, "modulus by zero"); in fold_op()
868 opt_state->non_branch_movement_performed = 1; in fold_op()
869 opt_state->done = 0; in fold_op()
890 opt_peep(opt_state_t *opt_state, struct block *b) in opt_peep() argument
928 opt_state->non_branch_movement_performed = 1; in opt_peep()
929 opt_state->done = 0; in opt_peep()
943 opt_state->non_branch_movement_performed = 1; in opt_peep()
944 opt_state->done = 0; in opt_peep()
1026 opt_state->non_branch_movement_performed = 1; in opt_peep()
1027 opt_state->done = 0; in opt_peep()
1045 if (opt_state->vmap[val].is_const) { in opt_peep()
1055 b->s.k += opt_state->vmap[val].const_val; in opt_peep()
1060 opt_state->non_branch_movement_performed = 1; in opt_peep()
1061 opt_state->done = 0; in opt_peep()
1077 opt_state->non_branch_movement_performed = 1; in opt_peep()
1078 opt_state->done = 0; in opt_peep()
1093 opt_state->non_branch_movement_performed = 1; in opt_peep()
1094 opt_state->done = 0; in opt_peep()
1111 opt_state->non_branch_movement_performed = 1; in opt_peep()
1112 opt_state->done = 0; in opt_peep()
1132 if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_X) { in opt_peep()
1133 bpf_u_int32 v = opt_state->vmap[val].const_val; in opt_peep()
1142 if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) { in opt_peep()
1143 bpf_u_int32 v = opt_state->vmap[val].const_val; in opt_peep()
1169 opt_state->non_branch_movement_performed = 1; in opt_peep()
1170 opt_state->done = 0; in opt_peep()
1186 opt_stmt(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 val[], int alter) in opt_stmt() argument
1196 v = F(opt_state, s->code, s->k, 0L); in opt_stmt()
1204 if (alter && opt_state->vmap[v].is_const) { in opt_stmt()
1206 s->k += opt_state->vmap[v].const_val; in opt_stmt()
1207 v = F(opt_state, s->code, s->k, 0L); in opt_stmt()
1211 opt_state->non_branch_movement_performed = 1; in opt_stmt()
1212 opt_state->done = 0; in opt_stmt()
1215 v = F(opt_state, s->code, s->k, v); in opt_stmt()
1220 v = F(opt_state, s->code, 0L, 0L); in opt_stmt()
1235 v = F(opt_state, s->code, s->k, 0L); in opt_stmt()
1240 if (alter && opt_state->vmap[val[A_ATOM]].is_const) { in opt_stmt()
1258 s->k = 0U - opt_state->vmap[val[A_ATOM]].const_val; in opt_stmt()
1262 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], 0L); in opt_stmt()
1301 opt_error(opt_state, in opt_stmt()
1304 opt_error(opt_state, in opt_stmt()
1307 if (opt_state->vmap[val[A_ATOM]].is_const) { in opt_stmt()
1308 fold_op(opt_state, s, val[A_ATOM], K(s->k)); in opt_stmt()
1313 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], K(s->k)); in opt_stmt()
1327 if (alter && opt_state->vmap[val[X_ATOM]].is_const) { in opt_stmt()
1328 if (opt_state->vmap[val[A_ATOM]].is_const) { in opt_stmt()
1329 fold_op(opt_state, s, val[A_ATOM], val[X_ATOM]); in opt_stmt()
1334 s->k = opt_state->vmap[val[X_ATOM]].const_val; in opt_stmt()
1337 opt_error(opt_state, in opt_stmt()
1342 opt_state->non_branch_movement_performed = 1; in opt_stmt()
1343 opt_state->done = 0; in opt_stmt()
1345 F(opt_state, s->code, val[A_ATOM], K(s->k)); in opt_stmt()
1356 if (alter && opt_state->vmap[val[A_ATOM]].is_const in opt_stmt()
1357 && opt_state->vmap[val[A_ATOM]].const_val == 0) { in opt_stmt()
1375 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], val[X_ATOM]); in opt_stmt()
1384 if (alter && opt_state->vmap[v].is_const) { in opt_stmt()
1386 s->k = opt_state->vmap[v].const_val; in opt_stmt()
1390 opt_state->non_branch_movement_performed = 1; in opt_stmt()
1391 opt_state->done = 0; in opt_stmt()
1402 if (alter && opt_state->vmap[v].is_const) { in opt_stmt()
1404 s->k = opt_state->vmap[v].const_val; in opt_stmt()
1408 opt_state->non_branch_movement_performed = 1; in opt_stmt()
1409 opt_state->done = 0; in opt_stmt()
1425 deadstmt(opt_state_t *opt_state, register struct stmt *s, register struct stmt *last[]) in deadstmt() argument
1444 opt_state->non_branch_movement_performed = 1; in deadstmt()
1445 opt_state->done = 0; in deadstmt()
1453 opt_deadstores(opt_state_t *opt_state, register struct block *b) in opt_deadstores() argument
1462 deadstmt(opt_state, &s->s, last); in opt_deadstores()
1463 deadstmt(opt_state, &b->s, last); in opt_deadstores()
1477 opt_state->non_branch_movement_performed = 1; in opt_deadstores()
1478 opt_state->done = 0; in opt_deadstores()
1483 opt_blk(opt_state_t *opt_state, struct block *b, int do_stmts) in opt_blk() argument
1533 opt_stmt(opt_state, &s->s, b->val, do_stmts); in opt_blk()
1571 opt_state->non_branch_movement_performed = 1; in opt_blk()
1572 opt_state->done = 0; in opt_blk()
1575 opt_peep(opt_state, b); in opt_blk()
1576 opt_deadstores(opt_state, b); in opt_blk()
1697 opt_j(opt_state_t *opt_state, struct edge *ep) in opt_j() argument
1743 opt_state->non_branch_movement_performed = 1; in opt_j()
1744 opt_state->done = 0; in opt_j()
1756 for (i = 0; i < opt_state->edgewords; ++i) { in opt_j()
1766 target = fold_edge(ep->succ, opt_state->edges[k]); in opt_j()
1789 opt_state->done = 0; in opt_j()
1822 or_pullup(opt_state_t *opt_state, struct block *b, struct block *root) in or_pullup() argument
1982 opt_state->done = 0; in or_pullup()
1987 find_dom(opt_state, root); in or_pullup()
1991 and_pullup(opt_state_t *opt_state, struct block *b, struct block *root) in and_pullup() argument
2083 opt_state->done = 0; in and_pullup()
2088 find_dom(opt_state, root); in and_pullup()
2092 opt_blks(opt_state_t *opt_state, struct icode *ic, int do_stmts) in opt_blks() argument
2097 init_val(opt_state); in opt_blks()
2100 find_inedges(opt_state, ic->root); in opt_blks()
2102 for (p = opt_state->levels[i]; p; p = p->link) in opt_blks()
2103 opt_blk(opt_state, p, do_stmts); in opt_blks()
2126 for (p = opt_state->levels[i]; p; p = p->link) { in opt_blks()
2127 opt_j(opt_state, &p->et); in opt_blks()
2128 opt_j(opt_state, &p->ef); in opt_blks()
2132 find_inedges(opt_state, ic->root); in opt_blks()
2134 for (p = opt_state->levels[i]; p; p = p->link) { in opt_blks()
2135 or_pullup(opt_state, p, ic->root); in opt_blks()
2136 and_pullup(opt_state, p, ic->root); in opt_blks()
2149 find_inedges(opt_state_t *opt_state, struct block *root) in find_inedges() argument
2155 for (i = 0; i < opt_state->n_blocks; ++i) in find_inedges()
2156 opt_state->blocks[i]->in_edges = 0; in find_inedges()
2163 for (b = opt_state->levels[level]; b != 0; b = b->link) { in find_inedges()
2195 opt_loop(opt_state_t *opt_state, struct icode *ic, int do_stmts) in opt_loop() argument
2201 opt_dump(opt_state, ic); in opt_loop()
2210 opt_state->done = 1; in opt_loop()
2214 opt_state->non_branch_movement_performed = 0; in opt_loop()
2215 find_levels(opt_state, ic); in opt_loop()
2216 find_dom(opt_state, ic->root); in opt_loop()
2217 find_closure(opt_state, ic->root); in opt_loop()
2218 find_ud(opt_state, ic->root); in opt_loop()
2219 find_edom(opt_state, ic->root); in opt_loop()
2220 opt_blks(opt_state, ic, do_stmts); in opt_loop()
2223 printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, opt_state->done); in opt_loop()
2224 opt_dump(opt_state, ic); in opt_loop()
2231 if (opt_state->done) { in opt_loop()
2243 if (opt_state->non_branch_movement_performed) { in opt_loop()
2267 opt_state->done = 1; in opt_loop()
2281 opt_state_t opt_state; in bpf_optimize() local
2283 memset(&opt_state, 0, sizeof(opt_state)); in bpf_optimize()
2284 opt_state.errbuf = errbuf; in bpf_optimize()
2285 opt_state.non_branch_movement_performed = 0; in bpf_optimize()
2286 if (setjmp(opt_state.top_ctx)) { in bpf_optimize()
2287 opt_cleanup(&opt_state); in bpf_optimize()
2290 opt_init(&opt_state, ic); in bpf_optimize()
2291 opt_loop(&opt_state, ic, 0); in bpf_optimize()
2292 opt_loop(&opt_state, ic, 1); in bpf_optimize()
2293 intern_blocks(&opt_state, ic); in bpf_optimize()
2297 opt_dump(&opt_state, ic); in bpf_optimize()
2304 opt_dump(&opt_state, ic); in bpf_optimize()
2307 opt_cleanup(&opt_state); in bpf_optimize()
2369 intern_blocks(opt_state_t *opt_state, struct icode *ic) in intern_blocks() argument
2376 for (i = 0; i < opt_state->n_blocks; ++i) in intern_blocks()
2377 opt_state->blocks[i]->link = 0; in intern_blocks()
2381 for (i = opt_state->n_blocks - 1; i != 0; ) { in intern_blocks()
2383 if (!isMarked(ic, opt_state->blocks[i])) in intern_blocks()
2385 for (j = i + 1; j < opt_state->n_blocks; ++j) { in intern_blocks()
2386 if (!isMarked(ic, opt_state->blocks[j])) in intern_blocks()
2388 if (eq_blk(opt_state->blocks[i], opt_state->blocks[j])) { in intern_blocks()
2389 opt_state->blocks[i]->link = opt_state->blocks[j]->link ? in intern_blocks()
2390 opt_state->blocks[j]->link : opt_state->blocks[j]; in intern_blocks()
2395 for (i = 0; i < opt_state->n_blocks; ++i) { in intern_blocks()
2396 p = opt_state->blocks[i]; in intern_blocks()
2413 opt_cleanup(opt_state_t *opt_state) in opt_cleanup() argument
2415 free((void *)opt_state->vnode_base); in opt_cleanup()
2416 free((void *)opt_state->vmap); in opt_cleanup()
2417 free((void *)opt_state->edges); in opt_cleanup()
2418 free((void *)opt_state->space); in opt_cleanup()
2419 free((void *)opt_state->levels); in opt_cleanup()
2420 free((void *)opt_state->blocks); in opt_cleanup()
2427 opt_error(opt_state_t *opt_state, const char *fmt, ...) in opt_error() argument
2431 if (opt_state->errbuf != NULL) { in opt_error()
2433 (void)vsnprintf(opt_state->errbuf, in opt_error()
2437 longjmp(opt_state->top_ctx, 1); in opt_error()
2476 number_blks_r(opt_state_t *opt_state, struct icode *ic, struct block *p) in number_blks_r() argument
2484 n = opt_state->n_blocks++; in number_blks_r()
2485 if (opt_state->n_blocks == 0) { in number_blks_r()
2489 opt_error(opt_state, "filter is too complex to optimize"); in number_blks_r()
2492 opt_state->blocks[n] = p; in number_blks_r()
2494 number_blks_r(opt_state, ic, JT(p)); in number_blks_r()
2495 number_blks_r(opt_state, ic, JF(p)); in number_blks_r()
2534 opt_init(opt_state_t *opt_state, struct icode *ic) in opt_init() argument
2547 opt_state->blocks = (struct block **)calloc(n, sizeof(*opt_state->blocks)); in opt_init()
2548 if (opt_state->blocks == NULL) in opt_init()
2549 opt_error(opt_state, "malloc"); in opt_init()
2551 opt_state->n_blocks = 0; in opt_init()
2552 number_blks_r(opt_state, ic, ic->root); in opt_init()
2557 if (opt_state->n_blocks == 0) in opt_init()
2558 opt_error(opt_state, "filter has no instructions; please report this as a libpcap issue"); in opt_init()
2560 opt_state->n_edges = 2 * opt_state->n_blocks; in opt_init()
2561 if ((opt_state->n_edges / 2) != opt_state->n_blocks) { in opt_init()
2565 opt_error(opt_state, "filter is too complex to optimize"); in opt_init()
2567 opt_state->edges = (struct edge **)calloc(opt_state->n_edges, sizeof(*opt_state->edges)); in opt_init()
2568 if (opt_state->edges == NULL) { in opt_init()
2569 opt_error(opt_state, "malloc"); in opt_init()
2575 opt_state->levels = (struct block **)calloc(opt_state->n_blocks, sizeof(*opt_state->levels)); in opt_init()
2576 if (opt_state->levels == NULL) { in opt_init()
2577 opt_error(opt_state, "malloc"); in opt_init()
2580 opt_state->edgewords = opt_state->n_edges / BITS_PER_WORD + 1; in opt_init()
2581 opt_state->nodewords = opt_state->n_blocks / BITS_PER_WORD + 1; in opt_init()
2588 product = opt_state->n_blocks * opt_state->nodewords; in opt_init()
2589 if ((product / opt_state->n_blocks) != opt_state->nodewords) { in opt_init()
2595 opt_error(opt_state, "filter is too complex to optimize"); in opt_init()
2602 block_memsize = (size_t)2 * product * sizeof(*opt_state->space); in opt_init()
2603 if ((block_memsize / product) != 2 * sizeof(*opt_state->space)) { in opt_init()
2604 opt_error(opt_state, "filter is too complex to optimize"); in opt_init()
2612 product = opt_state->n_edges * opt_state->edgewords; in opt_init()
2613 if ((product / opt_state->n_edges) != opt_state->edgewords) { in opt_init()
2614 opt_error(opt_state, "filter is too complex to optimize"); in opt_init()
2621 edge_memsize = (size_t)product * sizeof(*opt_state->space); in opt_init()
2622 if (edge_memsize / product != sizeof(*opt_state->space)) { in opt_init()
2623 opt_error(opt_state, "filter is too complex to optimize"); in opt_init()
2631 opt_error(opt_state, "filter is too complex to optimize"); in opt_init()
2635 opt_state->space = (bpf_u_int32 *)malloc(block_memsize + edge_memsize); in opt_init()
2636 if (opt_state->space == NULL) { in opt_init()
2637 opt_error(opt_state, "malloc"); in opt_init()
2639 p = opt_state->space; in opt_init()
2640 opt_state->all_dom_sets = p; in opt_init()
2642 opt_state->blocks[i]->dom = p; in opt_init()
2643 p += opt_state->nodewords; in opt_init()
2645 opt_state->all_closure_sets = p; in opt_init()
2647 opt_state->blocks[i]->closure = p; in opt_init()
2648 p += opt_state->nodewords; in opt_init()
2650 opt_state->all_edge_sets = p; in opt_init()
2652 register struct block *b = opt_state->blocks[i]; in opt_init()
2655 p += opt_state->edgewords; in opt_init()
2657 p += opt_state->edgewords; in opt_init()
2659 opt_state->edges[i] = &b->et; in opt_init()
2660 b->ef.id = opt_state->n_blocks + i; in opt_init()
2661 opt_state->edges[opt_state->n_blocks + i] = &b->ef; in opt_init()
2667 max_stmts += slength(opt_state->blocks[i]->stmts) + 1; in opt_init()
2673 opt_state->maxval = 3 * max_stmts; in opt_init()
2674 opt_state->vmap = (struct vmapinfo *)calloc(opt_state->maxval, sizeof(*opt_state->vmap)); in opt_init()
2675 if (opt_state->vmap == NULL) { in opt_init()
2676 opt_error(opt_state, "malloc"); in opt_init()
2678 …opt_state->vnode_base = (struct valnode *)calloc(opt_state->maxval, sizeof(*opt_state->vnode_base)… in opt_init()
2679 if (opt_state->vnode_base == NULL) { in opt_init()
2680 opt_error(opt_state, "malloc"); in opt_init()
3097 opt_dump(opt_state_t *opt_state, struct icode *ic) in opt_dump() argument
3111 opt_error(opt_state, "opt_dump: icode_to_fcode failed: %s", errbuf); in opt_dump()