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
23static struct instruction_list *insn_hash_table[INSN_HASH_SIZE];
24
25static 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
38void 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 */
130static 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
159static 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
259static void sort_instruction_list(struct instruction_list **list)
260{
261	sort_list((struct ptr_list **)list , insn_compare);
262}
263
264static 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
273static 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
287static 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
292static 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
300static 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
345void 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