xref: /illumos-gate/usr/src/tools/smatch/src/dominate.c (revision c85f09cc92abd00c84e58ec9f0f5d942906cb713)
1 // SPDX-License-Identifier: MIT
2 //
3 // dominate.c - compute the (iterated) dominance frontier of (a set of) nodes.
4 //
5 // Copyright (C) 2017 - Luc Van Oostenryck
6 //
7 // The algorithm used is the one described in:
8 //	"A Linear Time Algorithm for Placing phi-nodes"
9 //	by Vugranam C. Sreedhar and Guang R. Gao
10 //
11 
12 #include "dominate.h"
13 #include "flowgraph.h"
14 #include "linearize.h"
15 #include "flow.h"
16 #include <assert.h>
17 #include <stdlib.h>
18 #include <stdio.h>
19 
20 
21 struct piggy {
22 	unsigned int max;
23 	struct basic_block_list *lists[0];
24 };
25 
bank_init(unsigned levels)26 static struct piggy *bank_init(unsigned levels)
27 {
28 	struct piggy *bank;
29 	bank = calloc(1, sizeof(*bank) + levels * sizeof(bank->lists[0]));
30 	bank->max = levels - 1;
31 	return bank;
32 }
33 
bank_free(struct piggy * bank,unsigned int levels)34 static void bank_free(struct piggy *bank, unsigned int levels)
35 {
36 	for (; levels-- ;)
37 		free_ptr_list(&bank->lists[levels]);
38 	free(bank);
39 }
40 
bank_put(struct piggy * bank,struct basic_block * bb)41 static void bank_put(struct piggy *bank, struct basic_block *bb)
42 {
43 	unsigned int level = bb->dom_level;
44 	assert(level <= bank->max);
45 	add_bb(&bank->lists[level], bb);
46 }
47 
pop_bb(struct basic_block_list ** list)48 static inline struct basic_block *pop_bb(struct basic_block_list **list)
49 {
50 	return delete_ptr_list_last((struct ptr_list **)list);
51 }
52 
bank_get(struct piggy * bank)53 static struct basic_block *bank_get(struct piggy *bank)
54 {
55 	int level = bank->max;
56 	do {
57 		struct basic_block *bb = pop_bb(&bank->lists[level]);
58 		if (bb)
59 			return bb;
60 		if (!level)
61 			return NULL;
62 		bank->max = --level;
63 	} while (1);
64 }
65 
66 
67 #define	VISITED	0x1
68 #define	INPHI	0x2
69 #define	ALPHA	0x4
70 #define	FLAGS	0x7
71 
visit(struct piggy * bank,struct basic_block_list ** idf,struct basic_block * x,int curr_level)72 static void visit(struct piggy *bank, struct basic_block_list **idf, struct basic_block *x, int curr_level)
73 {
74 	struct basic_block *y;
75 
76 	x->generation |= 1;
77 	FOR_EACH_PTR(x->children, y) {
78 		unsigned flags = y->generation & FLAGS;
79 		if (y->idom == x)	// J-edges will be processed later
80 			continue;
81 		if (y->dom_level > curr_level)
82 			continue;
83 		if (flags & INPHI)
84 			continue;
85 		y->generation |= INPHI;
86 		add_bb(idf, y);
87 		if (flags & ALPHA)
88 			continue;
89 		bank_put(bank, y);
90 	} END_FOR_EACH_PTR(y);
91 
92 	FOR_EACH_PTR(x->doms, y) {
93 		if (y->generation & VISITED)
94 			continue;
95 		visit(bank, idf, y, curr_level);
96 	} END_FOR_EACH_PTR(y);
97 }
98 
idf_compute(struct entrypoint * ep,struct basic_block_list ** idf,struct basic_block_list * alpha)99 void idf_compute(struct entrypoint *ep, struct basic_block_list **idf, struct basic_block_list *alpha)
100 {
101 	int levels = ep->dom_levels;
102 	struct piggy *bank = bank_init(levels);
103 	struct basic_block *bb;
104 	unsigned long generation = bb_generation;
105 
106 	generation = bb_generation;
107 	generation += -generation & FLAGS;
108 	bb_generation = generation + (FLAGS + 1);
109 
110 	// init all the nodes
111 	FOR_EACH_PTR(ep->bbs, bb) {
112 		// FIXME: this should be removed and the tests for
113 		//	  visited/in_phi/alpha should use a sparse set
114 		bb->generation = generation;
115 	} END_FOR_EACH_PTR(bb);
116 
117 	FOR_EACH_PTR(alpha, bb) {
118 		bb->generation = generation | ALPHA;
119 		bank_put(bank, bb);
120 	} END_FOR_EACH_PTR(bb);
121 
122 	while ((bb = bank_get(bank))) {
123 		visit(bank, idf, bb, bb->dom_level);
124 	}
125 
126 	bank_free(bank, levels);
127 }
128 
idf_dump(struct entrypoint * ep)129 void idf_dump(struct entrypoint *ep)
130 {
131 	struct basic_block *bb;
132 
133 	domtree_build(ep);
134 
135 	printf("%s's IDF:\n", show_ident(ep->name->ident));
136 	FOR_EACH_PTR(ep->bbs, bb) {
137 		struct basic_block_list *alpha = NULL;
138 		struct basic_block_list *idf = NULL;
139 		struct basic_block *df;
140 
141 		add_bb(&alpha, bb);
142 		idf_compute(ep, &idf, alpha);
143 
144 		printf("\t%s\t<-", show_label(bb));
145 		FOR_EACH_PTR(idf, df) {
146 			printf(" %s", show_label(df));
147 		} END_FOR_EACH_PTR(df);
148 		printf("\n");
149 
150 		free_ptr_list(&idf);
151 		free_ptr_list(&alpha);
152 	} END_FOR_EACH_PTR(bb);
153 }
154