221 #define K(i) F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0L)
339 find_levels_r(opt_state_t *opt_state, struct icode *ic, struct block *b)  in find_levels_r()  argument
350 		find_levels_r(opt_state, ic, JT(b));  in find_levels_r()
351 		find_levels_r(opt_state, ic, JF(b));  in find_levels_r()
356 	b->link = opt_state->levels[level];  in find_levels_r()
357 	opt_state->levels[level] = b;  in find_levels_r()
367 find_levels(opt_state_t *opt_state, struct icode *ic)  in find_levels()  argument
369 	memset((char *)opt_state->levels, 0, opt_state->n_blocks * sizeof(*opt_state->levels));  in find_levels()
371 	find_levels_r(opt_state, ic, ic->root);  in find_levels()
379 find_dom(opt_state_t *opt_state, struct block *root)  in find_dom()  argument
388 	x = opt_state->all_dom_sets;  in find_dom()
389 	i = opt_state->n_blocks * opt_state->nodewords;  in find_dom()
393 	for (i = opt_state->nodewords; --i >= 0;)  in find_dom()
398 		for (b = opt_state->levels[i]; b; b = b->link) {  in find_dom()
402 			SET_INTERSECT(JT(b)->dom, b->dom, opt_state->nodewords);  in find_dom()
403 			SET_INTERSECT(JF(b)->dom, b->dom, opt_state->nodewords);  in find_dom()
409 propedom(opt_state_t *opt_state, struct edge *ep)  in propedom()  argument
413 		SET_INTERSECT(ep->succ->et.edom, ep->edom, opt_state->edgewords);  in propedom()
414 		SET_INTERSECT(ep->succ->ef.edom, ep->edom, opt_state->edgewords);  in propedom()
423 find_edom(opt_state_t *opt_state, struct block *root)  in find_edom()  argument
429 	x = opt_state->all_edge_sets;  in find_edom()
430 	for (i = opt_state->n_edges * opt_state->edgewords; --i >= 0; )  in find_edom()
434 	memset(root->et.edom, 0, opt_state->edgewords * sizeof(*(uset)0));  in find_edom()
435 	memset(root->ef.edom, 0, opt_state->edgewords * sizeof(*(uset)0));  in find_edom()
437 		for (b = opt_state->levels[i]; b != 0; b = b->link) {  in find_edom()
438 			propedom(opt_state, &b->et);  in find_edom()
439 			propedom(opt_state, &b->ef);  in find_edom()
452 find_closure(opt_state_t *opt_state, struct block *root)  in find_closure()  argument
460 	memset((char *)opt_state->all_closure_sets, 0,  in find_closure()
461 	      opt_state->n_blocks * opt_state->nodewords * sizeof(*opt_state->all_closure_sets));  in find_closure()
465 		for (b = opt_state->levels[i]; b; b = b->link) {  in find_closure()
469 			SET_UNION(JT(b)->closure, b->closure, opt_state->nodewords);  in find_closure()
470 			SET_UNION(JF(b)->closure, b->closure, opt_state->nodewords);  in find_closure()
624 find_ud(opt_state_t *opt_state, struct block *root)  in find_ud()  argument
635 		for (p = opt_state->levels[i]; p; p = p->link) {  in find_ud()
641 		for (p = opt_state->levels[i]; p; p = p->link) {  in find_ud()
648 init_val(opt_state_t *opt_state)  in init_val()  argument
650 	opt_state->curval = 0;  in init_val()
651 	opt_state->next_vnode = opt_state->vnode_base;  in init_val()
652 	memset((char *)opt_state->vmap, 0, opt_state->maxval * sizeof(*opt_state->vmap));  in init_val()
653 	memset((char *)opt_state->hashtbl, 0, sizeof opt_state->hashtbl);  in init_val()
658 F(opt_state_t *opt_state, int code, int v0, int v1)  in F()  argument
667 	for (p = opt_state->hashtbl[hash]; p; p = p->next)  in F()
671 	val = ++opt_state->curval;  in F()
674 		opt_state->vmap[val].const_val = v0;  in F()
675 		opt_state->vmap[val].is_const = 1;  in F()
677 	p = opt_state->next_vnode++;  in F()
682 	p->next = opt_state->hashtbl[hash];  in F()
683 	opt_state->hashtbl[hash] = p;  in F()
702 fold_op(compiler_state_t *cstate, opt_state_t *opt_state,  in fold_op()  argument
707 	a = opt_state->vmap[v0].const_val;  in fold_op()
708 	b = opt_state->vmap[v1].const_val;  in fold_op()
760 	opt_state->done = 0;  in fold_op()
781 opt_peep(opt_state_t *opt_state, struct block *b)  in opt_peep()  argument
816 			opt_state->done = 0;  in opt_peep()
827 			opt_state->done = 0;  in opt_peep()
906 			opt_state->done = 0;  in opt_peep()
924 			if (opt_state->vmap[val].is_const) {  in opt_peep()
934 				b->s.k += opt_state->vmap[val].const_val;  in opt_peep()
936 				opt_state->done = 0;  in opt_peep()
949 				opt_state->done = 0;  in opt_peep()
961 			opt_state->done = 0;  in opt_peep()
975 			opt_state->done = 0;  in opt_peep()
995 	if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_X) {  in opt_peep()
996 		bpf_int32 v = opt_state->vmap[val].const_val;  in opt_peep()
1005 	if (opt_state->vmap[val].is_const && BPF_SRC(b->s.code) == BPF_K) {  in opt_peep()
1006 		bpf_int32 v = opt_state->vmap[val].const_val;  in opt_peep()
1029 			opt_state->done = 0;  in opt_peep()
1044 opt_stmt(compiler_state_t *cstate, opt_state_t *opt_state,  in opt_stmt()  argument
1055 		v = F(opt_state, s->code, s->k, 0L);  in opt_stmt()
1063 		if (alter && opt_state->vmap[v].is_const) {  in opt_stmt()
1065 			s->k += opt_state->vmap[v].const_val;  in opt_stmt()
1066 			v = F(opt_state, s->code, s->k, 0L);  in opt_stmt()
1067 			opt_state->done = 0;  in opt_stmt()
1070 			v = F(opt_state, s->code, s->k, v);  in opt_stmt()
1075 		v = F(opt_state, s->code, 0L, 0L);  in opt_stmt()
1090 		v = F(opt_state, s->code, s->k, 0L);  in opt_stmt()
1095 		if (alter && opt_state->vmap[val[A_ATOM]].is_const) {  in opt_stmt()
1097 			s->k = -opt_state->vmap[val[A_ATOM]].const_val;  in opt_stmt()
1101 			val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], 0L);  in opt_stmt()
1132 			if (opt_state->vmap[val[A_ATOM]].is_const) {  in opt_stmt()
1133 				fold_op(cstate, opt_state, s, val[A_ATOM], K(s->k));  in opt_stmt()
1138 		val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], K(s->k));  in opt_stmt()
1152 		if (alter && opt_state->vmap[val[X_ATOM]].is_const) {  in opt_stmt()
1153 			if (opt_state->vmap[val[A_ATOM]].is_const) {  in opt_stmt()
1154 				fold_op(cstate, opt_state, s, val[A_ATOM], val[X_ATOM]);  in opt_stmt()
1159 				s->k = opt_state->vmap[val[X_ATOM]].const_val;  in opt_stmt()
1160 				opt_state->done = 0;  in opt_stmt()
1162 					F(opt_state, s->code, val[A_ATOM], K(s->k));  in opt_stmt()
1173 		if (alter && opt_state->vmap[val[A_ATOM]].is_const  in opt_stmt()
1174 		    && opt_state->vmap[val[A_ATOM]].const_val == 0) {  in opt_stmt()
1192 		val[A_ATOM] = F(opt_state, s->code, val[A_ATOM], val[X_ATOM]);  in opt_stmt()
1201 		if (alter && opt_state->vmap[v].is_const) {  in opt_stmt()
1203 			s->k = opt_state->vmap[v].const_val;  in opt_stmt()
1204 			opt_state->done = 0;  in opt_stmt()
1215 		if (alter && opt_state->vmap[v].is_const) {  in opt_stmt()
1217 			s->k = opt_state->vmap[v].const_val;  in opt_stmt()
1218 			opt_state->done = 0;  in opt_stmt()
1234 deadstmt(opt_state_t *opt_state, register struct stmt *s, register struct stmt *last[])  in deadstmt()  argument
1250 			opt_state->done = 0;  in deadstmt()
1258 opt_deadstores(opt_state_t *opt_state, register struct block *b)  in opt_deadstores()  argument
1267 		deadstmt(opt_state, &s->s, last);  in opt_deadstores()
1268 	deadstmt(opt_state, &b->s, last);  in opt_deadstores()
1273 			opt_state->done = 0;  in opt_deadstores()
1278 opt_blk(compiler_state_t *cstate, opt_state_t *opt_state,  in opt_blk()  argument
1329 		opt_stmt(cstate, opt_state, &s->s, b->val, do_stmts);  in opt_blk()
1361 			opt_state->done = 0;  in opt_blk()
1364 		opt_peep(opt_state, b);  in opt_blk()
1365 		opt_deadstores(opt_state, b);  in opt_blk()
1452 opt_j(opt_state_t *opt_state, struct edge *ep)  in opt_j()  argument
1466 			opt_state->done = 0;  in opt_j()
1478 	for (i = 0; i < opt_state->edgewords; ++i) {  in opt_j()
1486 			target = fold_edge(ep->succ, opt_state->edges[k]);  in opt_j()
1492 				opt_state->done = 0;  in opt_j()
1507 or_pullup(opt_state_t *opt_state, struct block *b)  in or_pullup()  argument
1595 	opt_state->done = 0;  in or_pullup()
1599 and_pullup(opt_state_t *opt_state, struct block *b)  in and_pullup()  argument
1686 	opt_state->done = 0;  in and_pullup()
1690 opt_blks(compiler_state_t *cstate, opt_state_t *opt_state, struct icode *ic,  in opt_blks()  argument
1696 	init_val(opt_state);  in opt_blks()
1699 	find_inedges(opt_state, ic->root);  in opt_blks()
1701 		for (p = opt_state->levels[i]; p; p = p->link)  in opt_blks()
1702 			opt_blk(cstate, opt_state, p, do_stmts);  in opt_blks()
1712 		for (p = opt_state->levels[i]; p; p = p->link) {  in opt_blks()
1713 			opt_j(opt_state, &p->et);  in opt_blks()
1714 			opt_j(opt_state, &p->ef);  in opt_blks()
1718 	find_inedges(opt_state, ic->root);  in opt_blks()
1720 		for (p = opt_state->levels[i]; p; p = p->link) {  in opt_blks()
1721 			or_pullup(opt_state, p);  in opt_blks()
1722 			and_pullup(opt_state, p);  in opt_blks()
1735 find_inedges(opt_state_t *opt_state, struct block *root)  in find_inedges()  argument
1740 	for (i = 0; i < opt_state->n_blocks; ++i)  in find_inedges()
1741 		opt_state->blocks[i]->in_edges = 0;  in find_inedges()
1748 		for (b = opt_state->levels[i]; b != 0; b = b->link) {  in find_inedges()
1780 opt_loop(compiler_state_t *cstate, opt_state_t *opt_state, struct icode *ic,  in opt_loop()  argument
1791 		opt_state->done = 1;  in opt_loop()
1792 		find_levels(opt_state, ic);  in opt_loop()
1793 		find_dom(opt_state, ic->root);  in opt_loop()
1794 		find_closure(opt_state, ic->root);  in opt_loop()
1795 		find_ud(opt_state, ic->root);  in opt_loop()
1796 		find_edom(opt_state, ic->root);  in opt_loop()
1797 		opt_blks(cstate, opt_state, ic, do_stmts);  in opt_loop()
1800 			printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, opt_state->done);  in opt_loop()
1804 	} while (!opt_state->done);  in opt_loop()
1813 	opt_state_t opt_state;  in bpf_optimize()  local
1815 	opt_init(cstate, &opt_state, ic);  in bpf_optimize()
1816 	opt_loop(cstate, &opt_state, ic, 0);  in bpf_optimize()
1817 	opt_loop(cstate, &opt_state, ic, 1);  in bpf_optimize()
1818 	intern_blocks(&opt_state, ic);  in bpf_optimize()
1832 	opt_cleanup(&opt_state);  in bpf_optimize()
1893 intern_blocks(opt_state_t *opt_state, struct icode *ic)  in intern_blocks()  argument
1900 	for (i = 0; i < opt_state->n_blocks; ++i)  in intern_blocks()
1901 		opt_state->blocks[i]->link = 0;  in intern_blocks()
1905 	for (i = opt_state->n_blocks - 1; --i >= 0; ) {  in intern_blocks()
1906 		if (!isMarked(ic, opt_state->blocks[i]))  in intern_blocks()
1908 		for (j = i + 1; j < opt_state->n_blocks; ++j) {  in intern_blocks()
1909 			if (!isMarked(ic, opt_state->blocks[j]))  in intern_blocks()
1911 			if (eq_blk(opt_state->blocks[i], opt_state->blocks[j])) {  in intern_blocks()
1912 				opt_state->blocks[i]->link = opt_state->blocks[j]->link ?  in intern_blocks()
1913 					opt_state->blocks[j]->link : opt_state->blocks[j];  in intern_blocks()
1918 	for (i = 0; i < opt_state->n_blocks; ++i) {  in intern_blocks()
1919 		p = opt_state->blocks[i];  in intern_blocks()
1936 opt_cleanup(opt_state_t *opt_state)  in opt_cleanup()  argument
1938 	free((void *)opt_state->vnode_base);  in opt_cleanup()
1939 	free((void *)opt_state->vmap);  in opt_cleanup()
1940 	free((void *)opt_state->edges);  in opt_cleanup()
1941 	free((void *)opt_state->space);  in opt_cleanup()
1942 	free((void *)opt_state->levels);  in opt_cleanup()
1943 	free((void *)opt_state->blocks);  in opt_cleanup()
1978 number_blks_r(opt_state_t *opt_state, struct icode *ic, struct block *p)  in number_blks_r()  argument
1986 	n = opt_state->n_blocks++;  in number_blks_r()
1988 	opt_state->blocks[n] = p;  in number_blks_r()
1990 	number_blks_r(opt_state, ic, JT(p));  in number_blks_r()
1991 	number_blks_r(opt_state, ic, JF(p));  in number_blks_r()
2030 opt_init(compiler_state_t *cstate, opt_state_t *opt_state, struct icode *ic)  in opt_init()  argument
2041 	opt_state->blocks = (struct block **)calloc(n, sizeof(*opt_state->blocks));  in opt_init()
2042 	if (opt_state->blocks == NULL)  in opt_init()
2045 	opt_state->n_blocks = 0;  in opt_init()
2046 	number_blks_r(opt_state, ic, ic->root);  in opt_init()
2048 	opt_state->n_edges = 2 * opt_state->n_blocks;  in opt_init()
2049 	opt_state->edges = (struct edge **)calloc(opt_state->n_edges, sizeof(*opt_state->edges));  in opt_init()
2050 	if (opt_state->edges == NULL)  in opt_init()
2056 	opt_state->levels = (struct block **)calloc(opt_state->n_blocks, sizeof(*opt_state->levels));  in opt_init()
2057 	if (opt_state->levels == NULL)  in opt_init()
2060 	opt_state->edgewords = opt_state->n_edges / (8 * sizeof(bpf_u_int32)) + 1;  in opt_init()
2061 	opt_state->nodewords = opt_state->n_blocks / (8 * sizeof(bpf_u_int32)) + 1;  in opt_init()
2064 …opt_state->space = (bpf_u_int32 *)malloc(2 * opt_state->n_blocks * opt_state->nodewords * sizeof(*…  in opt_init()
2065 				 + opt_state->n_edges * opt_state->edgewords * sizeof(*opt_state->space));  in opt_init()
2066 	if (opt_state->space == NULL)  in opt_init()
2068 	p = opt_state->space;  in opt_init()
2069 	opt_state->all_dom_sets = p;  in opt_init()
2071 		opt_state->blocks[i]->dom = p;  in opt_init()
2072 		p += opt_state->nodewords;  in opt_init()
2074 	opt_state->all_closure_sets = p;  in opt_init()
2076 		opt_state->blocks[i]->closure = p;  in opt_init()
2077 		p += opt_state->nodewords;  in opt_init()
2079 	opt_state->all_edge_sets = p;  in opt_init()
2081 		register struct block *b = opt_state->blocks[i];  in opt_init()
2084 		p += opt_state->edgewords;  in opt_init()
2086 		p += opt_state->edgewords;  in opt_init()
2088 		opt_state->edges[i] = &b->et;  in opt_init()
2089 		b->ef.id = opt_state->n_blocks + i;  in opt_init()
2090 		opt_state->edges[opt_state->n_blocks + i] = &b->ef;  in opt_init()
2096 		max_stmts += slength(opt_state->blocks[i]->stmts) + 1;  in opt_init()
2102 	opt_state->maxval = 3 * max_stmts;  in opt_init()
2103 	opt_state->vmap = (struct vmapinfo *)calloc(opt_state->maxval, sizeof(*opt_state->vmap));  in opt_init()
2104 …opt_state->vnode_base = (struct valnode *)calloc(opt_state->maxval, sizeof(*opt_state->vnode_base)…  in opt_init()
2105 	if (opt_state->vmap == NULL || opt_state->vnode_base == NULL)  in opt_init()