Lines Matching defs:opt_state
226 #define K(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)
382 find_levels_r(opt_state_t *opt_state, struct icode *ic, struct block *b)
393 find_levels_r(opt_state, ic, JT(b));
394 find_levels_r(opt_state, ic, JF(b));
399 b->link = opt_state->levels[level];
400 opt_state->levels[level] = b;
405 * N_LEVELS at the root. The opt_state->levels[] array points to the
410 find_levels(opt_state_t *opt_state, struct icode *ic)
412 memset((char *)opt_state->levels, 0, opt_state->n_blocks * sizeof(*opt_state->levels));
414 find_levels_r(opt_state, ic, ic->root);
422 find_dom(opt_state_t *opt_state, struct block *root)
432 x = opt_state->all_dom_sets;
436 i = opt_state->n_blocks * opt_state->nodewords;
442 for (i = opt_state->nodewords; i != 0;) {
449 for (b = opt_state->levels[level]; b; b = b->link) {
453 SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);
454 SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);
460 propedom(opt_state_t *opt_state, struct edge *ep)
464 SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);
465 SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);
474 find_edom(opt_state_t *opt_state, struct block *root)
481 x = opt_state->all_edge_sets;
485 for (i = opt_state->n_edges * opt_state->edgewords; i != 0; ) {
491 memset(root->et.edom, 0, opt_state->edgewords * sizeof(*(uset)0));
492 memset(root->ef.edom, 0, opt_state->edgewords * sizeof(*(uset)0));
494 for (b = opt_state->levels[level]; b != 0; b = b->link) {
495 propedom(opt_state, &b->et);
496 propedom(opt_state, &b->ef);
509 find_closure(opt_state_t *opt_state, struct block *root)
517 memset((char *)opt_state->all_closure_sets, 0,
518 opt_state->n_blocks * opt_state->nodewords * sizeof(*opt_state->all_closure_sets));
522 for (b = opt_state->levels[level]; b; b = b->link) {
526 SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);
527 SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);
688 find_ud(opt_state_t *opt_state, struct block *root)
699 for (p = opt_state->levels[i]; p; p = p->link) {
705 for (p = opt_state->levels[i]; p; p = p->link) {
712 init_val(opt_state_t *opt_state)
714 opt_state->curval = 0;
715 opt_state->next_vnode = opt_state->vnode_base;
716 memset((char *)opt_state->vmap, 0, opt_state->maxval * sizeof(*opt_state->vmap));
717 memset((char *)opt_state->hashtbl, 0, sizeof opt_state->hashtbl);
730 F(opt_state_t *opt_state, int code, bpf_u_int32 v0, bpf_u_int32 v1)
739 for (p = opt_state->hashtbl[hash]; p; p = p->next)
747 * opt_state->curval starts out as 0, which means VAL_UNKNOWN; we
754 val = ++opt_state->curval;
757 opt_state->vmap[val].const_val = v0;
758 opt_state->vmap[val].is_const = 1;
760 p = opt_state->next_vnode++;
765 p->next = opt_state->hashtbl[hash];
766 opt_state->hashtbl[hash] = p;
785 fold_op(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 v0, bpf_u_int32 v1)
789 a = opt_state->vmap[v0].const_val;
790 b = opt_state->vmap[v1].const_val;
807 opt_error(opt_state, "division by zero");
813 opt_error(opt_state, "modulus by zero");
873 opt_state->non_branch_movement_performed = 1;
874 opt_state->done = 0;
895 opt_peep(opt_state_t *opt_state, struct block *b)
933 opt_state->non_branch_movement_performed = 1;
934 opt_state->done = 0;
948 opt_state->non_branch_movement_performed = 1;
949 opt_state->done = 0;
1031 opt_state->non_branch_movement_performed = 1;
1032 opt_state->done = 0;
1050 if (opt_state->vmap[val].is_const) {
1060 b->s.k += opt_state->vmap[val].const_val;
1065 opt_state->non_branch_movement_performed = 1;
1066 opt_state->done = 0;
1082 opt_state->non_branch_movement_performed = 1;
1083 opt_state->done = 0;
1098 opt_state->non_branch_movement_performed = 1;
1099 opt_state->done = 0;
1116 opt_state->non_branch_movement_performed = 1;
1117 opt_state->done = 0;
1137 if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_X) {
1138 bpf_u_int32 v = opt_state->vmap[val].const_val;
1147 if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) {
1148 bpf_u_int32 v = opt_state->vmap[val].const_val;
1174 opt_state->non_branch_movement_performed = 1;
1175 opt_state->done = 0;
1191 opt_stmt(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 val[], int alter)
1201 v = F(opt_state, s->code, s->k, 0L);
1209 if (alter && opt_state->vmap[v].is_const) {
1211 s->k += opt_state->vmap[v].const_val;
1212 v = F(opt_state, s->code, s->k, 0L);
1216 opt_state->non_branch_movement_performed = 1;
1217 opt_state->done = 0;
1220 v = F(opt_state, s->code, s->k, v);
1225 v = F(opt_state, s->code, 0L, 0L);
1240 v = F(opt_state, s->code, s->k, 0L);
1245 if (alter && opt_state->vmap[val[A_ATOM]].is_const) {
1263 s->k = 0U - opt_state->vmap[val[A_ATOM]].const_val;
1267 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], 0L);
1306 opt_error(opt_state,
1309 opt_error(opt_state,
1312 if (opt_state->vmap[val[A_ATOM]].is_const) {
1313 fold_op(opt_state, s, val[A_ATOM], K(s->k));
1318 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], K(s->k));
1332 if (alter && opt_state->vmap[val[X_ATOM]].is_const) {
1333 if (opt_state->vmap[val[A_ATOM]].is_const) {
1334 fold_op(opt_state, s, val[A_ATOM], val[X_ATOM]);
1339 s->k = opt_state->vmap[val[X_ATOM]].const_val;
1342 opt_error(opt_state,
1347 opt_state->non_branch_movement_performed = 1;
1348 opt_state->done = 0;
1350 F(opt_state, s->code, val[A_ATOM], K(s->k));
1361 if (alter && opt_state->vmap[val[A_ATOM]].is_const
1362 && opt_state->vmap[val[A_ATOM]].const_val == 0) {
1380 val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], val[X_ATOM]);
1389 if (alter && opt_state->vmap[v].is_const) {
1391 s->k = opt_state->vmap[v].const_val;
1395 opt_state->non_branch_movement_performed = 1;
1396 opt_state->done = 0;
1407 if (alter && opt_state->vmap[v].is_const) {
1409 s->k = opt_state->vmap[v].const_val;
1413 opt_state->non_branch_movement_performed = 1;
1414 opt_state->done = 0;
1430 deadstmt(opt_state_t *opt_state, register struct stmt *s, register struct stmt *last[])
1449 opt_state->non_branch_movement_performed = 1;
1450 opt_state->done = 0;
1458 opt_deadstores(opt_state_t *opt_state, register struct block *b)
1467 deadstmt(opt_state, &s->s, last);
1468 deadstmt(opt_state, &b->s, last);
1482 opt_state->non_branch_movement_performed = 1;
1483 opt_state->done = 0;
1488 opt_blk(opt_state_t *opt_state, struct block *b, int do_stmts)
1538 opt_stmt(opt_state, &s->s, b->val, do_stmts);
1576 opt_state->non_branch_movement_performed = 1;
1577 opt_state->done = 0;
1580 opt_peep(opt_state, b);
1581 opt_deadstores(opt_state, b);
1702 opt_j(opt_state_t *opt_state, struct edge *ep)
1748 opt_state->non_branch_movement_performed = 1;
1749 opt_state->done = 0;
1761 for (i = 0; i < opt_state->edgewords; ++i) {
1771 target = fold_edge(ep->succ, opt_state->edges[k]);
1794 opt_state->done = 0;
1827 or_pullup(opt_state_t *opt_state, struct block *b, struct block *root)
1987 opt_state->done = 0;
1992 find_dom(opt_state, root);
1996 and_pullup(opt_state_t *opt_state, struct block *b, struct block *root)
2088 opt_state->done = 0;
2093 find_dom(opt_state, root);
2097 opt_blks(opt_state_t *opt_state, struct icode *ic, int do_stmts)
2102 init_val(opt_state);
2105 find_inedges(opt_state, ic->root);
2107 for (p = opt_state->levels[i]; p; p = p->link)
2108 opt_blk(opt_state, p, do_stmts);
2131 for (p = opt_state->levels[i]; p; p = p->link) {
2132 opt_j(opt_state, &p->et);
2133 opt_j(opt_state, &p->ef);
2137 find_inedges(opt_state, ic->root);
2139 for (p = opt_state->levels[i]; p; p = p->link) {
2140 or_pullup(opt_state, p, ic->root);
2141 and_pullup(opt_state, p, ic->root);
2154 find_inedges(opt_state_t *opt_state, struct block *root)
2160 for (i = 0; i < opt_state->n_blocks; ++i)
2161 opt_state->blocks[i]->in_edges = 0;
2168 for (b = opt_state->levels[level]; b != 0; b = b->link) {
2200 opt_loop(opt_state_t *opt_state, struct icode *ic, int do_stmts)
2206 opt_dump(opt_state, ic);
2215 opt_state->done = 1;
2219 opt_state->non_branch_movement_performed = 0;
2220 find_levels(opt_state, ic);
2221 find_dom(opt_state, ic->root);
2222 find_closure(opt_state, ic->root);
2223 find_ud(opt_state, ic->root);
2224 find_edom(opt_state, ic->root);
2225 opt_blks(opt_state, ic, do_stmts);
2228 printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, opt_state->done);
2229 opt_dump(opt_state, ic);
2236 if (opt_state->done) {
2248 if (opt_state->non_branch_movement_performed) {
2272 opt_state->done = 1;
2286 opt_state_t opt_state;
2288 memset(&opt_state, 0, sizeof(opt_state));
2289 opt_state.errbuf = errbuf;
2290 opt_state.non_branch_movement_performed = 0;
2291 if (setjmp(opt_state.top_ctx)) {
2292 opt_cleanup(&opt_state);
2295 opt_init(&opt_state, ic);
2296 opt_loop(&opt_state, ic, 0);
2297 opt_loop(&opt_state, ic, 1);
2298 intern_blocks(&opt_state, ic);
2302 opt_dump(&opt_state, ic);
2309 opt_dump(&opt_state, ic);
2312 opt_cleanup(&opt_state);
2374 intern_blocks(opt_state_t *opt_state, struct icode *ic)
2381 for (i = 0; i < opt_state->n_blocks; ++i)
2382 opt_state->blocks[i]->link = 0;
2386 for (i = opt_state->n_blocks - 1; i != 0; ) {
2388 if (!isMarked(ic, opt_state->blocks[i]))
2390 for (j = i + 1; j < opt_state->n_blocks; ++j) {
2391 if (!isMarked(ic, opt_state->blocks[j]))
2393 if (eq_blk(opt_state->blocks[i], opt_state->blocks[j])) {
2394 opt_state->blocks[i]->link = opt_state->blocks[j]->link ?
2395 opt_state->blocks[j]->link : opt_state->blocks[j];
2400 for (i = 0; i < opt_state->n_blocks; ++i) {
2401 p = opt_state->blocks[i];
2418 opt_cleanup(opt_state_t *opt_state)
2420 free((void *)opt_state->vnode_base);
2421 free((void *)opt_state->vmap);
2422 free((void *)opt_state->edges);
2423 free((void *)opt_state->space);
2424 free((void *)opt_state->levels);
2425 free((void *)opt_state->blocks);
2432 opt_error(opt_state_t *opt_state, const char *fmt, ...)
2436 if (opt_state->errbuf != NULL) {
2438 (void)vsnprintf(opt_state->errbuf,
2442 longjmp(opt_state->top_ctx, 1);
2481 number_blks_r(opt_state_t *opt_state, struct icode *ic, struct block *p)
2489 n = opt_state->n_blocks++;
2490 if (opt_state->n_blocks == 0) {
2494 opt_error(opt_state, "filter is too complex to optimize");
2497 opt_state->blocks[n] = p;
2499 number_blks_r(opt_state, ic, JT(p));
2500 number_blks_r(opt_state, ic, JF(p));
2539 opt_init(opt_state_t *opt_state, struct icode *ic)
2552 opt_state->blocks = (struct block **)calloc(n, sizeof(*opt_state->blocks));
2553 if (opt_state->blocks == NULL)
2554 opt_error(opt_state, "malloc");
2556 opt_state->n_blocks = 0;
2557 number_blks_r(opt_state, ic, ic->root);
2562 if (opt_state->n_blocks == 0)
2563 opt_error(opt_state, "filter has no instructions; please report this as a libpcap issue");
2565 opt_state->n_edges = 2 * opt_state->n_blocks;
2566 if ((opt_state->n_edges / 2) != opt_state->n_blocks) {
2570 opt_error(opt_state, "filter is too complex to optimize");
2572 opt_state->edges = (struct edge **)calloc(opt_state->n_edges, sizeof(*opt_state->edges));
2573 if (opt_state->edges == NULL) {
2574 opt_error(opt_state, "malloc");
2580 opt_state->levels = (struct block **)calloc(opt_state->n_blocks, sizeof(*opt_state->levels));
2581 if (opt_state->levels == NULL) {
2582 opt_error(opt_state, "malloc");
2585 opt_state->edgewords = opt_state->n_edges / BITS_PER_WORD + 1;
2586 opt_state->nodewords = opt_state->n_blocks / BITS_PER_WORD + 1;
2589 * Make sure opt_state->n_blocks * opt_state->nodewords fits
2593 product = opt_state->n_blocks * opt_state->nodewords;
2594 if ((product / opt_state->n_blocks) != opt_state->nodewords) {
2600 opt_error(opt_state, "filter is too complex to optimize");
2607 block_memsize = (size_t)2 * product * sizeof(*opt_state->space);
2608 if ((block_memsize / product) != 2 * sizeof(*opt_state->space)) {
2609 opt_error(opt_state, "filter is too complex to optimize");
2613 * Make sure opt_state->n_edges * opt_state->edgewords fits
2617 product = opt_state->n_edges * opt_state->edgewords;
2618 if ((product / opt_state->n_edges) != opt_state->edgewords) {
2619 opt_error(opt_state, "filter is too complex to optimize");
2626 edge_memsize = (size_t)product * sizeof(*opt_state->space);
2627 if (edge_memsize / product != sizeof(*opt_state->space)) {
2628 opt_error(opt_state, "filter is too complex to optimize");
2636 opt_error(opt_state, "filter is too complex to optimize");
2640 opt_state->space = (bpf_u_int32 *)malloc(block_memsize + edge_memsize);
2641 if (opt_state->space == NULL) {
2642 opt_error(opt_state, "malloc");
2644 p = opt_state->space;
2645 opt_state->all_dom_sets = p;
2647 opt_state->blocks[i]->dom = p;
2648 p += opt_state->nodewords;
2650 opt_state->all_closure_sets = p;
2652 opt_state->blocks[i]->closure = p;
2653 p += opt_state->nodewords;
2655 opt_state->all_edge_sets = p;
2657 register struct block *b = opt_state->blocks[i];
2660 p += opt_state->edgewords;
2662 p += opt_state->edgewords;
2664 opt_state->edges[i] = &b->et;
2665 b->ef.id = opt_state->n_blocks + i;
2666 opt_state->edges[opt_state->n_blocks + i] = &b->ef;
2672 max_stmts += slength(opt_state->blocks[i]->stmts) + 1;
2678 opt_state->maxval = 3 * max_stmts;
2679 opt_state->vmap = (struct vmapinfo *)calloc(opt_state->maxval, sizeof(*opt_state->vmap));
2680 if (opt_state->vmap == NULL) {
2681 opt_error(opt_state, "malloc");
2683 opt_state->vnode_base = (struct valnode *)calloc(opt_state->maxval, sizeof(*opt_state->vnode_base));
2684 if (opt_state->vnode_base == NULL) {
2685 opt_error(opt_state, "malloc");
3102 opt_dump(opt_state_t *opt_state, struct icode *ic)
3116 opt_error(opt_state, "opt_dump: icode_to_fcode failed: %s", errbuf);
Indexes created Mon Mar 02 05:31:46 UTC 2026