xref: /illumos-gate/usr/src/tools/smatch/src/cse.c (revision c85f09cc92abd00c84e58ec9f0f5d942906cb713)
1 /*
2  * CSE - walk the linearized instruction flow, and
3  * see if we can simplify it and apply CSE on it.
4  *
5  * Copyright (C) 2004 Linus Torvalds
6  */
7 
8 #include <string.h>
9 #include <stdarg.h>
10 #include <stdlib.h>
11 #include <stdio.h>
12 #include <stddef.h>
13 #include <assert.h>
14 
15 #include "parse.h"
16 #include "expression.h"
17 #include "flowgraph.h"
18 #include "linearize.h"
19 #include "flow.h"
20 #include "cse.h"
21 
22 #define INSN_HASH_SIZE 256
23 static struct instruction_list *insn_hash_table[INSN_HASH_SIZE];
24 
phi_compare(pseudo_t phi1,pseudo_t phi2)25 static int phi_compare(pseudo_t phi1, pseudo_t phi2)
26 {
27 	const struct instruction *def1 = phi1->def;
28 	const struct instruction *def2 = phi2->def;
29 
30 	if (def1->src1 != def2->src1)
31 		return def1->src1 < def2->src1 ? -1 : 1;
32 	if (def1->bb != def2->bb)
33 		return def1->bb < def2->bb ? -1 : 1;
34 	return 0;
35 }
36 
37 
cse_collect(struct instruction * insn)38 void cse_collect(struct instruction *insn)
39 {
40 	unsigned long hash;
41 
42 	hash = (insn->opcode << 3) + (insn->size >> 3);
43 	switch (insn->opcode) {
44 	case OP_SEL:
45 		hash += hashval(insn->src3);
46 		/* Fall through */
47 
48 	/* Binary arithmetic */
49 	case OP_ADD: case OP_SUB:
50 	case OP_MUL:
51 	case OP_DIVU: case OP_DIVS:
52 	case OP_MODU: case OP_MODS:
53 	case OP_SHL:
54 	case OP_LSR: case OP_ASR:
55 	case OP_AND: case OP_OR:
56 
57 	/* Binary logical */
58 	case OP_XOR:
59 
60 	/* Binary comparison */
61 	case OP_SET_EQ: case OP_SET_NE:
62 	case OP_SET_LE: case OP_SET_GE:
63 	case OP_SET_LT: case OP_SET_GT:
64 	case OP_SET_B:  case OP_SET_A:
65 	case OP_SET_BE: case OP_SET_AE:
66 
67 	/* floating-point arithmetic & comparison */
68 	case OP_FPCMP ... OP_FPCMP_END:
69 	case OP_FADD:
70 	case OP_FSUB:
71 	case OP_FMUL:
72 	case OP_FDIV:
73 		hash += hashval(insn->src2);
74 		/* Fall through */
75 
76 	/* Unary */
77 	case OP_NOT: case OP_NEG:
78 	case OP_FNEG:
79 	case OP_SYMADDR:
80 		hash += hashval(insn->src1);
81 		break;
82 
83 	case OP_SETVAL:
84 		hash += hashval(insn->val);
85 		break;
86 
87 	case OP_SETFVAL:
88 		hash += hashval(insn->fvalue);
89 		break;
90 
91 	case OP_SEXT: case OP_ZEXT:
92 	case OP_TRUNC:
93 	case OP_PTRCAST:
94 	case OP_UTPTR: case OP_PTRTU:
95 		if (!insn->orig_type || insn->orig_type->bit_size < 0)
96 			return;
97 		hash += hashval(insn->src);
98 
99 		// Note: see corresponding line in insn_compare()
100 		hash += hashval(insn->orig_type->bit_size);
101 		break;
102 
103 	/* Other */
104 	case OP_PHI: {
105 		pseudo_t phi;
106 		FOR_EACH_PTR(insn->phi_list, phi) {
107 			struct instruction *def;
108 			if (phi == VOID || !phi->def)
109 				continue;
110 			def = phi->def;
111 			hash += hashval(def->src1);
112 			hash += hashval(def->bb);
113 		} END_FOR_EACH_PTR(phi);
114 		break;
115 	}
116 
117 	default:
118 		/*
119 		 * Nothing to do, don't even bother hashing them,
120 		 * we're not going to try to CSE them
121 		 */
122 		return;
123 	}
124 	hash += hash >> 16;
125 	hash &= INSN_HASH_SIZE-1;
126 	add_instruction(insn_hash_table + hash, insn);
127 }
128 
129 /* Compare two (sorted) phi-lists */
phi_list_compare(struct pseudo_list * l1,struct pseudo_list * l2)130 static int phi_list_compare(struct pseudo_list *l1, struct pseudo_list *l2)
131 {
132 	pseudo_t phi1, phi2;
133 
134 	PREPARE_PTR_LIST(l1, phi1);
135 	PREPARE_PTR_LIST(l2, phi2);
136 	for (;;) {
137 		int cmp;
138 
139 		while (phi1 && (phi1 == VOID || !phi1->def))
140 			NEXT_PTR_LIST(phi1);
141 		while (phi2 && (phi2 == VOID || !phi2->def))
142 			NEXT_PTR_LIST(phi2);
143 
144 		if (!phi1)
145 			return phi2 ? -1 : 0;
146 		if (!phi2)
147 			return phi1 ? 1 : 0;
148 		cmp = phi_compare(phi1, phi2);
149 		if (cmp)
150 			return cmp;
151 		NEXT_PTR_LIST(phi1);
152 		NEXT_PTR_LIST(phi2);
153 	}
154 	/* Not reached, but we need to make the nesting come out right */
155 	FINISH_PTR_LIST(phi2);
156 	FINISH_PTR_LIST(phi1);
157 }
158 
insn_compare(const void * _i1,const void * _i2)159 static int insn_compare(const void *_i1, const void *_i2)
160 {
161 	const struct instruction *i1 = _i1;
162 	const struct instruction *i2 = _i2;
163 	int size1, size2;
164 	int diff;
165 
166 	if (i1->opcode != i2->opcode)
167 		return i1->opcode < i2->opcode ? -1 : 1;
168 
169 	switch (i1->opcode) {
170 
171 	/* commutative binop */
172 	case OP_ADD:
173 	case OP_MUL:
174 	case OP_AND: case OP_OR:
175 	case OP_XOR:
176 	case OP_SET_EQ: case OP_SET_NE:
177 		if (i1->src1 == i2->src2 && i1->src2 == i2->src1)
178 			return 0;
179 		goto case_binops;
180 
181 	case OP_SEL:
182 		if (i1->src3 != i2->src3)
183 			return i1->src3 < i2->src3 ? -1 : 1;
184 		/* Fall-through to binops */
185 
186 	/* Binary arithmetic */
187 	case OP_SUB:
188 	case OP_DIVU: case OP_DIVS:
189 	case OP_MODU: case OP_MODS:
190 	case OP_SHL:
191 	case OP_LSR: case OP_ASR:
192 
193 	/* Binary comparison */
194 	case OP_SET_LE: case OP_SET_GE:
195 	case OP_SET_LT: case OP_SET_GT:
196 	case OP_SET_B:  case OP_SET_A:
197 	case OP_SET_BE: case OP_SET_AE:
198 
199 	/* floating-point arithmetic */
200 	case OP_FPCMP ... OP_FPCMP_END:
201 	case OP_FADD:
202 	case OP_FSUB:
203 	case OP_FMUL:
204 	case OP_FDIV:
205 	case_binops:
206 		if (i1->src2 != i2->src2)
207 			return i1->src2 < i2->src2 ? -1 : 1;
208 		/* Fall through to unops */
209 
210 	/* Unary */
211 	case OP_NOT: case OP_NEG:
212 	case OP_FNEG:
213 	case OP_SYMADDR:
214 		if (i1->src1 != i2->src1)
215 			return i1->src1 < i2->src1 ? -1 : 1;
216 		break;
217 
218 	case OP_SETVAL:
219 		if (i1->val != i2->val)
220 			return i1->val < i2->val ? -1 : 1;
221 		break;
222 
223 	case OP_SETFVAL:
224 		diff = memcmp(&i1->fvalue, &i2->fvalue, sizeof(i1->fvalue));
225 		if (diff)
226 			return diff;
227 		break;
228 
229 	/* Other */
230 	case OP_PHI:
231 		return phi_list_compare(i1->phi_list, i2->phi_list);
232 
233 	case OP_SEXT: case OP_ZEXT:
234 	case OP_TRUNC:
235 	case OP_PTRCAST:
236 	case OP_UTPTR: case OP_PTRTU:
237 		if (i1->src != i2->src)
238 			return i1->src < i2->src ? -1 : 1;
239 
240 		// Note: if it can be guaranted that identical ->src
241 		// implies identical orig_type->bit_size, then this
242 		// test and the hashing of the original size in
243 		// cse_collect() are not needed.
244 		// It must be generaly true but it isn't guaranted (yet).
245 		size1 = i1->orig_type->bit_size;
246 		size2 = i2->orig_type->bit_size;
247 		if (size1 != size2)
248 			return size1 < size2 ? -1 : 1;
249 		break;
250 
251 	default:
252 		warning(i1->pos, "bad instruction on hash chain");
253 	}
254 	if (i1->size != i2->size)
255 		return i1->size < i2->size ? -1 : 1;
256 	return 0;
257 }
258 
sort_instruction_list(struct instruction_list ** list)259 static void sort_instruction_list(struct instruction_list **list)
260 {
261 	sort_list((struct ptr_list **)list , insn_compare);
262 }
263 
cse_one_instruction(struct instruction * insn,struct instruction * def)264 static struct instruction * cse_one_instruction(struct instruction *insn, struct instruction *def)
265 {
266 	convert_instruction_target(insn, def->target);
267 
268 	kill_instruction(insn);
269 	repeat_phase |= REPEAT_CSE;
270 	return def;
271 }
272 
trivial_common_parent(struct basic_block * bb1,struct basic_block * bb2)273 static struct basic_block *trivial_common_parent(struct basic_block *bb1, struct basic_block *bb2)
274 {
275 	struct basic_block *parent;
276 
277 	if (bb_list_size(bb1->parents) != 1)
278 		return NULL;
279 	parent = first_basic_block(bb1->parents);
280 	if (bb_list_size(bb2->parents) != 1)
281 		return NULL;
282 	if (first_basic_block(bb2->parents) != parent)
283 		return NULL;
284 	return parent;
285 }
286 
remove_instruction(struct instruction_list ** list,struct instruction * insn,int count)287 static inline void remove_instruction(struct instruction_list **list, struct instruction *insn, int count)
288 {
289 	delete_ptr_list_entry((struct ptr_list **)list, insn, count);
290 }
291 
add_instruction_to_end(struct instruction * insn,struct basic_block * bb)292 static void add_instruction_to_end(struct instruction *insn, struct basic_block *bb)
293 {
294 	struct instruction *br = delete_last_instruction(&bb->insns);
295 	insn->bb = bb;
296 	add_instruction(&bb->insns, insn);
297 	add_instruction(&bb->insns, br);
298 }
299 
try_to_cse(struct entrypoint * ep,struct instruction * i1,struct instruction * i2)300 static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction *i1, struct instruction *i2)
301 {
302 	struct basic_block *b1, *b2, *common;
303 
304 	/*
305 	 * OK, i1 and i2 are the same instruction, modulo "target".
306 	 * We should now see if we can combine them.
307 	 */
308 	b1 = i1->bb;
309 	b2 = i2->bb;
310 
311 	/*
312 	 * Currently we only handle the uninteresting degenerate case where
313 	 * the CSE is inside one basic-block.
314 	 */
315 	if (b1 == b2) {
316 		struct instruction *insn;
317 		FOR_EACH_PTR(b1->insns, insn) {
318 			if (insn == i1)
319 				return cse_one_instruction(i2, i1);
320 			if (insn == i2)
321 				return cse_one_instruction(i1, i2);
322 		} END_FOR_EACH_PTR(insn);
323 		warning(b1->pos, "Whaa? unable to find CSE instructions");
324 		return i1;
325 	}
326 	if (domtree_dominates(b1, b2))
327 		return cse_one_instruction(i2, i1);
328 
329 	if (domtree_dominates(b2, b1))
330 		return cse_one_instruction(i1, i2);
331 
332 	/* No direct dominance - but we could try to find a common ancestor.. */
333 	common = trivial_common_parent(b1, b2);
334 	if (common) {
335 		i1 = cse_one_instruction(i2, i1);
336 		remove_instruction(&b1->insns, i1, 1);
337 		add_instruction_to_end(i1, common);
338 	} else {
339 		i1 = i2;
340 	}
341 
342 	return i1;
343 }
344 
cse_eliminate(struct entrypoint * ep)345 void cse_eliminate(struct entrypoint *ep)
346 {
347 	int i;
348 
349 	for (i = 0; i < INSN_HASH_SIZE; i++) {
350 		struct instruction_list **list = insn_hash_table + i;
351 		if (*list) {
352 			if (instruction_list_size(*list) > 1) {
353 				struct instruction *insn, *last;
354 
355 				sort_instruction_list(list);
356 
357 				last = NULL;
358 				FOR_EACH_PTR(*list, insn) {
359 					if (!insn->bb)
360 						continue;
361 					if (last) {
362 						if (!insn_compare(last, insn))
363 							insn = try_to_cse(ep, last, insn);
364 					}
365 					last = insn;
366 				} END_FOR_EACH_PTR(insn);
367 			}
368 			free_ptr_list(list);
369 		}
370 	}
371 }
372