xref: /illumos-gate/usr/src/tools/smatch/src/simplify.c (revision 1f5207b7)
1*1f5207b7SJohn Levon /*
2*1f5207b7SJohn Levon  * Simplify - do instruction simplification before CSE
3*1f5207b7SJohn Levon  *
4*1f5207b7SJohn Levon  * Copyright (C) 2004 Linus Torvalds
5*1f5207b7SJohn Levon  */
6*1f5207b7SJohn Levon 
7*1f5207b7SJohn Levon #include <assert.h>
8*1f5207b7SJohn Levon 
9*1f5207b7SJohn Levon #include "parse.h"
10*1f5207b7SJohn Levon #include "expression.h"
11*1f5207b7SJohn Levon #include "linearize.h"
12*1f5207b7SJohn Levon #include "flow.h"
13*1f5207b7SJohn Levon #include "symbol.h"
14*1f5207b7SJohn Levon 
15*1f5207b7SJohn Levon /* Find the trivial parent for a phi-source */
16*1f5207b7SJohn Levon static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
17*1f5207b7SJohn Levon {
18*1f5207b7SJohn Levon 	/* Can't go upwards if the pseudo is defined in the bb it came from.. */
19*1f5207b7SJohn Levon 	if (pseudo->type == PSEUDO_REG) {
20*1f5207b7SJohn Levon 		struct instruction *def = pseudo->def;
21*1f5207b7SJohn Levon 		if (def->bb == source)
22*1f5207b7SJohn Levon 			return source;
23*1f5207b7SJohn Levon 	}
24*1f5207b7SJohn Levon 	if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
25*1f5207b7SJohn Levon 		return source;
26*1f5207b7SJohn Levon 	return first_basic_block(source->parents);
27*1f5207b7SJohn Levon }
28*1f5207b7SJohn Levon 
29*1f5207b7SJohn Levon /*
30*1f5207b7SJohn Levon  * Copy the phi-node's phisrcs into to given array.
31*1f5207b7SJohn Levon  * Returns 0 if the the list contained the expected
32*1f5207b7SJohn Levon  * number of element, a positive number if there was
33*1f5207b7SJohn Levon  * more than expected and a negative one if less.
34*1f5207b7SJohn Levon  *
35*1f5207b7SJohn Levon  * Note: we can't reuse a function like linearize_ptr_list()
36*1f5207b7SJohn Levon  * because any VOIDs in the phi-list must be ignored here
37*1f5207b7SJohn Levon  * as in this context they mean 'entry has been removed'.
38*1f5207b7SJohn Levon  */
39*1f5207b7SJohn Levon static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
40*1f5207b7SJohn Levon {
41*1f5207b7SJohn Levon 	pseudo_t phi;
42*1f5207b7SJohn Levon 	int i = 0;
43*1f5207b7SJohn Levon 
44*1f5207b7SJohn Levon 	assert(insn->opcode == OP_PHI);
45*1f5207b7SJohn Levon 	FOR_EACH_PTR(insn->phi_list, phi) {
46*1f5207b7SJohn Levon 		struct instruction *def;
47*1f5207b7SJohn Levon 		if (phi == VOID)
48*1f5207b7SJohn Levon 			continue;
49*1f5207b7SJohn Levon 		if (i >= nbr)
50*1f5207b7SJohn Levon 			return 1;
51*1f5207b7SJohn Levon 		def = phi->def;
52*1f5207b7SJohn Levon 		assert(def->opcode == OP_PHISOURCE);
53*1f5207b7SJohn Levon 		sources[i++] = def;
54*1f5207b7SJohn Levon 	} END_FOR_EACH_PTR(phi);
55*1f5207b7SJohn Levon 	return i - nbr;
56*1f5207b7SJohn Levon }
57*1f5207b7SJohn Levon 
58*1f5207b7SJohn Levon static int if_convert_phi(struct instruction *insn)
59*1f5207b7SJohn Levon {
60*1f5207b7SJohn Levon 	struct instruction *array[2];
61*1f5207b7SJohn Levon 	struct basic_block *parents[3];
62*1f5207b7SJohn Levon 	struct basic_block *bb, *bb1, *bb2, *source;
63*1f5207b7SJohn Levon 	struct instruction *br;
64*1f5207b7SJohn Levon 	pseudo_t p1, p2;
65*1f5207b7SJohn Levon 
66*1f5207b7SJohn Levon 	bb = insn->bb;
67*1f5207b7SJohn Levon 	if (get_phisources(array, 2, insn))
68*1f5207b7SJohn Levon 		return 0;
69*1f5207b7SJohn Levon 	if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
70*1f5207b7SJohn Levon 		return 0;
71*1f5207b7SJohn Levon 	p1 = array[0]->src1;
72*1f5207b7SJohn Levon 	bb1 = array[0]->bb;
73*1f5207b7SJohn Levon 	p2 = array[1]->src1;
74*1f5207b7SJohn Levon 	bb2 = array[1]->bb;
75*1f5207b7SJohn Levon 
76*1f5207b7SJohn Levon 	/* Only try the simple "direct parents" case */
77*1f5207b7SJohn Levon 	if ((bb1 != parents[0] || bb2 != parents[1]) &&
78*1f5207b7SJohn Levon 	    (bb1 != parents[1] || bb2 != parents[0]))
79*1f5207b7SJohn Levon 		return 0;
80*1f5207b7SJohn Levon 
81*1f5207b7SJohn Levon 	/*
82*1f5207b7SJohn Levon 	 * See if we can find a common source for this..
83*1f5207b7SJohn Levon 	 */
84*1f5207b7SJohn Levon 	source = phi_parent(bb1, p1);
85*1f5207b7SJohn Levon 	if (source != phi_parent(bb2, p2))
86*1f5207b7SJohn Levon 		return 0;
87*1f5207b7SJohn Levon 
88*1f5207b7SJohn Levon 	/*
89*1f5207b7SJohn Levon 	 * Cool. We now know that 'source' is the exclusive
90*1f5207b7SJohn Levon 	 * parent of both phi-nodes, so the exit at the
91*1f5207b7SJohn Levon 	 * end of it fully determines which one it is, and
92*1f5207b7SJohn Levon 	 * we can turn it into a select.
93*1f5207b7SJohn Levon 	 *
94*1f5207b7SJohn Levon 	 * HOWEVER, right now we only handle regular
95*1f5207b7SJohn Levon 	 * conditional branches. No multijumps or computed
96*1f5207b7SJohn Levon 	 * stuff. Verify that here.
97*1f5207b7SJohn Levon 	 */
98*1f5207b7SJohn Levon 	br = last_instruction(source->insns);
99*1f5207b7SJohn Levon 	if (!br || br->opcode != OP_CBR)
100*1f5207b7SJohn Levon 		return 0;
101*1f5207b7SJohn Levon 
102*1f5207b7SJohn Levon 	assert(br->cond);
103*1f5207b7SJohn Levon 	assert(br->bb_false);
104*1f5207b7SJohn Levon 
105*1f5207b7SJohn Levon 	/*
106*1f5207b7SJohn Levon 	 * We're in business. Match up true/false with p1/p2.
107*1f5207b7SJohn Levon 	 */
108*1f5207b7SJohn Levon 	if (br->bb_true == bb2 || br->bb_false == bb1) {
109*1f5207b7SJohn Levon 		pseudo_t p = p1;
110*1f5207b7SJohn Levon 		p1 = p2;
111*1f5207b7SJohn Levon 		p2 = p;
112*1f5207b7SJohn Levon 	}
113*1f5207b7SJohn Levon 
114*1f5207b7SJohn Levon 	/*
115*1f5207b7SJohn Levon 	 * OK, we can now replace that last
116*1f5207b7SJohn Levon 	 *
117*1f5207b7SJohn Levon 	 *	br cond, a, b
118*1f5207b7SJohn Levon 	 *
119*1f5207b7SJohn Levon 	 * with the sequence
120*1f5207b7SJohn Levon 	 *
121*1f5207b7SJohn Levon 	 *	setcc cond
122*1f5207b7SJohn Levon 	 *	select pseudo, p1, p2
123*1f5207b7SJohn Levon 	 *	br cond, a, b
124*1f5207b7SJohn Levon 	 *
125*1f5207b7SJohn Levon 	 * and remove the phi-node. If it then
126*1f5207b7SJohn Levon 	 * turns out that 'a' or 'b' is entirely
127*1f5207b7SJohn Levon 	 * empty (common case), and now no longer
128*1f5207b7SJohn Levon 	 * a phi-source, we'll be able to simplify
129*1f5207b7SJohn Levon 	 * the conditional branch too.
130*1f5207b7SJohn Levon 	 */
131*1f5207b7SJohn Levon 	insert_select(source, br, insn, p1, p2);
132*1f5207b7SJohn Levon 	kill_instruction(insn);
133*1f5207b7SJohn Levon 	return REPEAT_CSE;
134*1f5207b7SJohn Levon }
135*1f5207b7SJohn Levon 
136*1f5207b7SJohn Levon static int clean_up_phi(struct instruction *insn)
137*1f5207b7SJohn Levon {
138*1f5207b7SJohn Levon 	pseudo_t phi;
139*1f5207b7SJohn Levon 	struct instruction *last;
140*1f5207b7SJohn Levon 	int same;
141*1f5207b7SJohn Levon 
142*1f5207b7SJohn Levon 	last = NULL;
143*1f5207b7SJohn Levon 	same = 1;
144*1f5207b7SJohn Levon 	FOR_EACH_PTR(insn->phi_list, phi) {
145*1f5207b7SJohn Levon 		struct instruction *def;
146*1f5207b7SJohn Levon 		if (phi == VOID)
147*1f5207b7SJohn Levon 			continue;
148*1f5207b7SJohn Levon 		def = phi->def;
149*1f5207b7SJohn Levon 		if (def->src1 == VOID || !def->bb)
150*1f5207b7SJohn Levon 			continue;
151*1f5207b7SJohn Levon 		if (last) {
152*1f5207b7SJohn Levon 			if (last->src1 != def->src1)
153*1f5207b7SJohn Levon 				same = 0;
154*1f5207b7SJohn Levon 			continue;
155*1f5207b7SJohn Levon 		}
156*1f5207b7SJohn Levon 		last = def;
157*1f5207b7SJohn Levon 	} END_FOR_EACH_PTR(phi);
158*1f5207b7SJohn Levon 
159*1f5207b7SJohn Levon 	if (same) {
160*1f5207b7SJohn Levon 		pseudo_t pseudo = last ? last->src1 : VOID;
161*1f5207b7SJohn Levon 		convert_instruction_target(insn, pseudo);
162*1f5207b7SJohn Levon 		kill_instruction(insn);
163*1f5207b7SJohn Levon 		return REPEAT_CSE;
164*1f5207b7SJohn Levon 	}
165*1f5207b7SJohn Levon 
166*1f5207b7SJohn Levon 	return if_convert_phi(insn);
167*1f5207b7SJohn Levon }
168*1f5207b7SJohn Levon 
169*1f5207b7SJohn Levon static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
170*1f5207b7SJohn Levon {
171*1f5207b7SJohn Levon 	struct pseudo_user *pu;
172*1f5207b7SJohn Levon 
173*1f5207b7SJohn Levon 	FOR_EACH_PTR(*list, pu) {
174*1f5207b7SJohn Levon 		if (pu->userp == entry) {
175*1f5207b7SJohn Levon 			MARK_CURRENT_DELETED(pu);
176*1f5207b7SJohn Levon 			if (!--count)
177*1f5207b7SJohn Levon 				goto out;
178*1f5207b7SJohn Levon 		}
179*1f5207b7SJohn Levon 	} END_FOR_EACH_PTR(pu);
180*1f5207b7SJohn Levon 	assert(count <= 0);
181*1f5207b7SJohn Levon out:
182*1f5207b7SJohn Levon 	if (ptr_list_size((struct ptr_list *) *list) == 0)
183*1f5207b7SJohn Levon 		*list = NULL;
184*1f5207b7SJohn Levon 	return count;
185*1f5207b7SJohn Levon }
186*1f5207b7SJohn Levon 
187*1f5207b7SJohn Levon static inline void remove_usage(pseudo_t p, pseudo_t *usep)
188*1f5207b7SJohn Levon {
189*1f5207b7SJohn Levon 	if (has_use_list(p)) {
190*1f5207b7SJohn Levon 		delete_pseudo_user_list_entry(&p->users, usep, 1);
191*1f5207b7SJohn Levon 		if (!p->users)
192*1f5207b7SJohn Levon 			kill_instruction(p->def);
193*1f5207b7SJohn Levon 	}
194*1f5207b7SJohn Levon }
195*1f5207b7SJohn Levon 
196*1f5207b7SJohn Levon void kill_use(pseudo_t *usep)
197*1f5207b7SJohn Levon {
198*1f5207b7SJohn Levon 	if (usep) {
199*1f5207b7SJohn Levon 		pseudo_t p = *usep;
200*1f5207b7SJohn Levon 		*usep = VOID;
201*1f5207b7SJohn Levon 		remove_usage(p, usep);
202*1f5207b7SJohn Levon 	}
203*1f5207b7SJohn Levon }
204*1f5207b7SJohn Levon 
205*1f5207b7SJohn Levon static void kill_use_list(struct pseudo_list *list)
206*1f5207b7SJohn Levon {
207*1f5207b7SJohn Levon 	pseudo_t p;
208*1f5207b7SJohn Levon 	FOR_EACH_PTR(list, p) {
209*1f5207b7SJohn Levon 		if (p == VOID)
210*1f5207b7SJohn Levon 			continue;
211*1f5207b7SJohn Levon 		kill_use(THIS_ADDRESS(p));
212*1f5207b7SJohn Levon 	} END_FOR_EACH_PTR(p);
213*1f5207b7SJohn Levon }
214*1f5207b7SJohn Levon 
215*1f5207b7SJohn Levon /*
216*1f5207b7SJohn Levon  * kill an instruction:
217*1f5207b7SJohn Levon  * - remove it from its bb
218*1f5207b7SJohn Levon  * - remove the usage of all its operands
219*1f5207b7SJohn Levon  * If forse is zero, the normal case, the function only for
220*1f5207b7SJohn Levon  * instructions free of (possible) side-effects. Otherwise
221*1f5207b7SJohn Levon  * the function does that unconditionally (must only be used
222*1f5207b7SJohn Levon  * for unreachable instructions.
223*1f5207b7SJohn Levon  */
224*1f5207b7SJohn Levon void kill_insn(struct instruction *insn, int force)
225*1f5207b7SJohn Levon {
226*1f5207b7SJohn Levon 	if (!insn || !insn->bb)
227*1f5207b7SJohn Levon 		return;
228*1f5207b7SJohn Levon 
229*1f5207b7SJohn Levon 	switch (insn->opcode) {
230*1f5207b7SJohn Levon 	case OP_SEL:
231*1f5207b7SJohn Levon 	case OP_RANGE:
232*1f5207b7SJohn Levon 		kill_use(&insn->src3);
233*1f5207b7SJohn Levon 		/* fall through */
234*1f5207b7SJohn Levon 
235*1f5207b7SJohn Levon 	case OP_BINARY ... OP_BINCMP_END:
236*1f5207b7SJohn Levon 		kill_use(&insn->src2);
237*1f5207b7SJohn Levon 		/* fall through */
238*1f5207b7SJohn Levon 
239*1f5207b7SJohn Levon 	case OP_CAST:
240*1f5207b7SJohn Levon 	case OP_SCAST:
241*1f5207b7SJohn Levon 	case OP_FPCAST:
242*1f5207b7SJohn Levon 	case OP_PTRCAST:
243*1f5207b7SJohn Levon 	case OP_SETVAL:
244*1f5207b7SJohn Levon 	case OP_NOT: case OP_NEG:
245*1f5207b7SJohn Levon 	case OP_SLICE:
246*1f5207b7SJohn Levon 		kill_use(&insn->src1);
247*1f5207b7SJohn Levon 		break;
248*1f5207b7SJohn Levon 
249*1f5207b7SJohn Levon 	case OP_PHI:
250*1f5207b7SJohn Levon 		kill_use_list(insn->phi_list);
251*1f5207b7SJohn Levon 		break;
252*1f5207b7SJohn Levon 	case OP_PHISOURCE:
253*1f5207b7SJohn Levon 		kill_use(&insn->phi_src);
254*1f5207b7SJohn Levon 		break;
255*1f5207b7SJohn Levon 
256*1f5207b7SJohn Levon 	case OP_SYMADDR:
257*1f5207b7SJohn Levon 		repeat_phase |= REPEAT_SYMBOL_CLEANUP;
258*1f5207b7SJohn Levon 		break;
259*1f5207b7SJohn Levon 
260*1f5207b7SJohn Levon 	case OP_CBR:
261*1f5207b7SJohn Levon 	case OP_COMPUTEDGOTO:
262*1f5207b7SJohn Levon 		kill_use(&insn->cond);
263*1f5207b7SJohn Levon 		break;
264*1f5207b7SJohn Levon 
265*1f5207b7SJohn Levon 	case OP_CALL:
266*1f5207b7SJohn Levon 		if (!force) {
267*1f5207b7SJohn Levon 			/* a "pure" function can be killed too */
268*1f5207b7SJohn Levon 			if (!(insn->func->type == PSEUDO_SYM))
269*1f5207b7SJohn Levon 				return;
270*1f5207b7SJohn Levon 			if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
271*1f5207b7SJohn Levon 				return;
272*1f5207b7SJohn Levon 		}
273*1f5207b7SJohn Levon 		kill_use_list(insn->arguments);
274*1f5207b7SJohn Levon 		if (insn->func->type == PSEUDO_REG)
275*1f5207b7SJohn Levon 			kill_use(&insn->func);
276*1f5207b7SJohn Levon 		break;
277*1f5207b7SJohn Levon 
278*1f5207b7SJohn Levon 	case OP_LOAD:
279*1f5207b7SJohn Levon 		if (!force && insn->type->ctype.modifiers & MOD_VOLATILE)
280*1f5207b7SJohn Levon 			return;
281*1f5207b7SJohn Levon 		kill_use(&insn->src);
282*1f5207b7SJohn Levon 		break;
283*1f5207b7SJohn Levon 
284*1f5207b7SJohn Levon 	case OP_STORE:
285*1f5207b7SJohn Levon 		if (!force)
286*1f5207b7SJohn Levon 			return;
287*1f5207b7SJohn Levon 		kill_use(&insn->src);
288*1f5207b7SJohn Levon 		kill_use(&insn->target);
289*1f5207b7SJohn Levon 		break;
290*1f5207b7SJohn Levon 
291*1f5207b7SJohn Levon 	case OP_ENTRY:
292*1f5207b7SJohn Levon 		/* ignore */
293*1f5207b7SJohn Levon 		return;
294*1f5207b7SJohn Levon 
295*1f5207b7SJohn Levon 	case OP_BR:
296*1f5207b7SJohn Levon 	default:
297*1f5207b7SJohn Levon 		break;
298*1f5207b7SJohn Levon 	}
299*1f5207b7SJohn Levon 
300*1f5207b7SJohn Levon 	insn->bb = NULL;
301*1f5207b7SJohn Levon 	repeat_phase |= REPEAT_CSE;
302*1f5207b7SJohn Levon 	return;
303*1f5207b7SJohn Levon }
304*1f5207b7SJohn Levon 
305*1f5207b7SJohn Levon /*
306*1f5207b7SJohn Levon  * Kill trivially dead instructions
307*1f5207b7SJohn Levon  */
308*1f5207b7SJohn Levon static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
309*1f5207b7SJohn Levon {
310*1f5207b7SJohn Levon 	struct pseudo_user *pu;
311*1f5207b7SJohn Levon 	FOR_EACH_PTR(insn->target->users, pu) {
312*1f5207b7SJohn Levon 		if (*pu->userp != VOID)
313*1f5207b7SJohn Levon 			return 0;
314*1f5207b7SJohn Levon 	} END_FOR_EACH_PTR(pu);
315*1f5207b7SJohn Levon 
316*1f5207b7SJohn Levon 	insn->bb = NULL;
317*1f5207b7SJohn Levon 	kill_use(src1);
318*1f5207b7SJohn Levon 	kill_use(src2);
319*1f5207b7SJohn Levon 	kill_use(src3);
320*1f5207b7SJohn Levon 	return REPEAT_CSE;
321*1f5207b7SJohn Levon }
322*1f5207b7SJohn Levon 
323*1f5207b7SJohn Levon static inline int constant(pseudo_t pseudo)
324*1f5207b7SJohn Levon {
325*1f5207b7SJohn Levon 	return pseudo->type == PSEUDO_VAL;
326*1f5207b7SJohn Levon }
327*1f5207b7SJohn Levon 
328*1f5207b7SJohn Levon static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
329*1f5207b7SJohn Levon {
330*1f5207b7SJohn Levon 	convert_instruction_target(insn, pseudo);
331*1f5207b7SJohn Levon 
332*1f5207b7SJohn Levon 	switch (insn->opcode) {
333*1f5207b7SJohn Levon 	case OP_SEL:
334*1f5207b7SJohn Levon 	case OP_RANGE:
335*1f5207b7SJohn Levon 		kill_use(&insn->src3);
336*1f5207b7SJohn Levon 	case OP_BINARY ... OP_BINCMP_END:
337*1f5207b7SJohn Levon 		kill_use(&insn->src2);
338*1f5207b7SJohn Levon 	case OP_NOT:
339*1f5207b7SJohn Levon 	case OP_NEG:
340*1f5207b7SJohn Levon 	case OP_SYMADDR:
341*1f5207b7SJohn Levon 	case OP_CAST:
342*1f5207b7SJohn Levon 	case OP_SCAST:
343*1f5207b7SJohn Levon 	case OP_FPCAST:
344*1f5207b7SJohn Levon 	case OP_PTRCAST:
345*1f5207b7SJohn Levon 		kill_use(&insn->src1);
346*1f5207b7SJohn Levon 		break;
347*1f5207b7SJohn Levon 
348*1f5207b7SJohn Levon 	default:
349*1f5207b7SJohn Levon 		assert(0);
350*1f5207b7SJohn Levon 	}
351*1f5207b7SJohn Levon 	insn->bb = NULL;
352*1f5207b7SJohn Levon 	return REPEAT_CSE;
353*1f5207b7SJohn Levon }
354*1f5207b7SJohn Levon 
355*1f5207b7SJohn Levon unsigned int value_size(long long value)
356*1f5207b7SJohn Levon {
357*1f5207b7SJohn Levon 	value >>= 8;
358*1f5207b7SJohn Levon 	if (!value)
359*1f5207b7SJohn Levon 		return 8;
360*1f5207b7SJohn Levon 	value >>= 8;
361*1f5207b7SJohn Levon 	if (!value)
362*1f5207b7SJohn Levon 		return 16;
363*1f5207b7SJohn Levon 	value >>= 16;
364*1f5207b7SJohn Levon 	if (!value)
365*1f5207b7SJohn Levon 		return 32;
366*1f5207b7SJohn Levon 	return 64;
367*1f5207b7SJohn Levon }
368*1f5207b7SJohn Levon 
369*1f5207b7SJohn Levon /*
370*1f5207b7SJohn Levon  * Try to determine the maximum size of bits in a pseudo.
371*1f5207b7SJohn Levon  *
372*1f5207b7SJohn Levon  * Right now this only follow casts and constant values, but we
373*1f5207b7SJohn Levon  * could look at things like logical 'and' instructions etc.
374*1f5207b7SJohn Levon  */
375*1f5207b7SJohn Levon static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
376*1f5207b7SJohn Levon {
377*1f5207b7SJohn Levon 	unsigned int size = insn->size;
378*1f5207b7SJohn Levon 
379*1f5207b7SJohn Levon 	if (pseudo->type == PSEUDO_REG) {
380*1f5207b7SJohn Levon 		struct instruction *src = pseudo->def;
381*1f5207b7SJohn Levon 		if (src && src->opcode == OP_CAST && src->orig_type) {
382*1f5207b7SJohn Levon 			unsigned int orig_size = src->orig_type->bit_size;
383*1f5207b7SJohn Levon 			if (orig_size < size)
384*1f5207b7SJohn Levon 				size = orig_size;
385*1f5207b7SJohn Levon 		}
386*1f5207b7SJohn Levon 	}
387*1f5207b7SJohn Levon 	if (pseudo->type == PSEUDO_VAL) {
388*1f5207b7SJohn Levon 		unsigned int orig_size = value_size(pseudo->value);
389*1f5207b7SJohn Levon 		if (orig_size < size)
390*1f5207b7SJohn Levon 			size = orig_size;
391*1f5207b7SJohn Levon 	}
392*1f5207b7SJohn Levon 	return size;
393*1f5207b7SJohn Levon }
394*1f5207b7SJohn Levon 
395*1f5207b7SJohn Levon static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long value)
396*1f5207b7SJohn Levon {
397*1f5207b7SJohn Levon 	unsigned int size = operand_size(insn, pseudo);
398*1f5207b7SJohn Levon 
399*1f5207b7SJohn Levon 	if (value >= size) {
400*1f5207b7SJohn Levon 		warning(insn->pos, "right shift by bigger than source value");
401*1f5207b7SJohn Levon 		return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
402*1f5207b7SJohn Levon 	}
403*1f5207b7SJohn Levon 	if (!value)
404*1f5207b7SJohn Levon 		return replace_with_pseudo(insn, pseudo);
405*1f5207b7SJohn Levon 	return 0;
406*1f5207b7SJohn Levon }
407*1f5207b7SJohn Levon 
408*1f5207b7SJohn Levon static int simplify_mul_div(struct instruction *insn, long long value)
409*1f5207b7SJohn Levon {
410*1f5207b7SJohn Levon 	unsigned long long sbit = 1ULL << (insn->size - 1);
411*1f5207b7SJohn Levon 	unsigned long long bits = sbit | (sbit - 1);
412*1f5207b7SJohn Levon 
413*1f5207b7SJohn Levon 	if (value == 1)
414*1f5207b7SJohn Levon 		return replace_with_pseudo(insn, insn->src1);
415*1f5207b7SJohn Levon 
416*1f5207b7SJohn Levon 	switch (insn->opcode) {
417*1f5207b7SJohn Levon 	case OP_MULS:
418*1f5207b7SJohn Levon 	case OP_MULU:
419*1f5207b7SJohn Levon 		if (value == 0)
420*1f5207b7SJohn Levon 			return replace_with_pseudo(insn, insn->src2);
421*1f5207b7SJohn Levon 	/* Fall through */
422*1f5207b7SJohn Levon 	case OP_DIVS:
423*1f5207b7SJohn Levon 		if (!(value & sbit))	// positive
424*1f5207b7SJohn Levon 			break;
425*1f5207b7SJohn Levon 
426*1f5207b7SJohn Levon 		value |= ~bits;
427*1f5207b7SJohn Levon 		if (value == -1) {
428*1f5207b7SJohn Levon 			insn->opcode = OP_NEG;
429*1f5207b7SJohn Levon 			return REPEAT_CSE;
430*1f5207b7SJohn Levon 		}
431*1f5207b7SJohn Levon 	}
432*1f5207b7SJohn Levon 
433*1f5207b7SJohn Levon 	return 0;
434*1f5207b7SJohn Levon }
435*1f5207b7SJohn Levon 
436*1f5207b7SJohn Levon static int compare_opcode(int opcode, int inverse)
437*1f5207b7SJohn Levon {
438*1f5207b7SJohn Levon 	if (!inverse)
439*1f5207b7SJohn Levon 		return opcode;
440*1f5207b7SJohn Levon 
441*1f5207b7SJohn Levon 	switch (opcode) {
442*1f5207b7SJohn Levon 	case OP_SET_EQ:	return OP_SET_NE;
443*1f5207b7SJohn Levon 	case OP_SET_NE:	return OP_SET_EQ;
444*1f5207b7SJohn Levon 
445*1f5207b7SJohn Levon 	case OP_SET_LT:	return OP_SET_GE;
446*1f5207b7SJohn Levon 	case OP_SET_LE:	return OP_SET_GT;
447*1f5207b7SJohn Levon 	case OP_SET_GT:	return OP_SET_LE;
448*1f5207b7SJohn Levon 	case OP_SET_GE:	return OP_SET_LT;
449*1f5207b7SJohn Levon 
450*1f5207b7SJohn Levon 	case OP_SET_A:	return OP_SET_BE;
451*1f5207b7SJohn Levon 	case OP_SET_AE:	return OP_SET_B;
452*1f5207b7SJohn Levon 	case OP_SET_B:	return OP_SET_AE;
453*1f5207b7SJohn Levon 	case OP_SET_BE:	return OP_SET_A;
454*1f5207b7SJohn Levon 
455*1f5207b7SJohn Levon 	default:
456*1f5207b7SJohn Levon 		return opcode;
457*1f5207b7SJohn Levon 	}
458*1f5207b7SJohn Levon }
459*1f5207b7SJohn Levon 
460*1f5207b7SJohn Levon static int simplify_seteq_setne(struct instruction *insn, long long value)
461*1f5207b7SJohn Levon {
462*1f5207b7SJohn Levon 	pseudo_t old = insn->src1;
463*1f5207b7SJohn Levon 	struct instruction *def = old->def;
464*1f5207b7SJohn Levon 	pseudo_t src1, src2;
465*1f5207b7SJohn Levon 	int inverse;
466*1f5207b7SJohn Levon 	int opcode;
467*1f5207b7SJohn Levon 
468*1f5207b7SJohn Levon 	if (value != 0 && value != 1)
469*1f5207b7SJohn Levon 		return 0;
470*1f5207b7SJohn Levon 
471*1f5207b7SJohn Levon 	if (!def)
472*1f5207b7SJohn Levon 		return 0;
473*1f5207b7SJohn Levon 
474*1f5207b7SJohn Levon 	inverse = (insn->opcode == OP_SET_NE) == value;
475*1f5207b7SJohn Levon 	opcode = def->opcode;
476*1f5207b7SJohn Levon 	switch (opcode) {
477*1f5207b7SJohn Levon 	case OP_BINCMP ... OP_BINCMP_END:
478*1f5207b7SJohn Levon 		// Convert:
479*1f5207b7SJohn Levon 		//	setcc.n	%t <- %a, %b
480*1f5207b7SJohn Levon 		//	setne.m %r <- %t, $0
481*1f5207b7SJohn Levon 		// into:
482*1f5207b7SJohn Levon 		//	setcc.n	%t <- %a, %b
483*1f5207b7SJohn Levon 		//	setcc.m %r <- %a, $b
484*1f5207b7SJohn Levon 		// and similar for setne/eq ... 0/1
485*1f5207b7SJohn Levon 		src1 = def->src1;
486*1f5207b7SJohn Levon 		src2 = def->src2;
487*1f5207b7SJohn Levon 		insn->opcode = compare_opcode(opcode, inverse);
488*1f5207b7SJohn Levon 		use_pseudo(insn, src1, &insn->src1);
489*1f5207b7SJohn Levon 		use_pseudo(insn, src2, &insn->src2);
490*1f5207b7SJohn Levon 		remove_usage(old, &insn->src1);
491*1f5207b7SJohn Levon 		return REPEAT_CSE;
492*1f5207b7SJohn Levon 
493*1f5207b7SJohn Levon 	default:
494*1f5207b7SJohn Levon 		return 0;
495*1f5207b7SJohn Levon 	}
496*1f5207b7SJohn Levon }
497*1f5207b7SJohn Levon 
498*1f5207b7SJohn Levon static int simplify_constant_rightside(struct instruction *insn)
499*1f5207b7SJohn Levon {
500*1f5207b7SJohn Levon 	long long value = insn->src2->value;
501*1f5207b7SJohn Levon 
502*1f5207b7SJohn Levon 	switch (insn->opcode) {
503*1f5207b7SJohn Levon 	case OP_OR_BOOL:
504*1f5207b7SJohn Levon 		if (value == 1)
505*1f5207b7SJohn Levon 			return replace_with_pseudo(insn, insn->src2);
506*1f5207b7SJohn Levon 		goto case_neutral_zero;
507*1f5207b7SJohn Levon 
508*1f5207b7SJohn Levon 	case OP_SUB:
509*1f5207b7SJohn Levon 		if (value) {
510*1f5207b7SJohn Levon 			insn->opcode = OP_ADD;
511*1f5207b7SJohn Levon 			insn->src2 = value_pseudo(insn->type, -value);
512*1f5207b7SJohn Levon 			return REPEAT_CSE;
513*1f5207b7SJohn Levon 		}
514*1f5207b7SJohn Levon 	/* Fall through */
515*1f5207b7SJohn Levon 	case OP_ADD:
516*1f5207b7SJohn Levon 	case OP_OR: case OP_XOR:
517*1f5207b7SJohn Levon 	case OP_SHL:
518*1f5207b7SJohn Levon 	case OP_LSR:
519*1f5207b7SJohn Levon 	case_neutral_zero:
520*1f5207b7SJohn Levon 		if (!value)
521*1f5207b7SJohn Levon 			return replace_with_pseudo(insn, insn->src1);
522*1f5207b7SJohn Levon 		return 0;
523*1f5207b7SJohn Levon 	case OP_ASR:
524*1f5207b7SJohn Levon 		return simplify_asr(insn, insn->src1, value);
525*1f5207b7SJohn Levon 
526*1f5207b7SJohn Levon 	case OP_MODU: case OP_MODS:
527*1f5207b7SJohn Levon 		if (value == 1)
528*1f5207b7SJohn Levon 			return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
529*1f5207b7SJohn Levon 		return 0;
530*1f5207b7SJohn Levon 
531*1f5207b7SJohn Levon 	case OP_DIVU: case OP_DIVS:
532*1f5207b7SJohn Levon 	case OP_MULU: case OP_MULS:
533*1f5207b7SJohn Levon 		return simplify_mul_div(insn, value);
534*1f5207b7SJohn Levon 
535*1f5207b7SJohn Levon 	case OP_AND_BOOL:
536*1f5207b7SJohn Levon 		if (value == 1)
537*1f5207b7SJohn Levon 			return replace_with_pseudo(insn, insn->src1);
538*1f5207b7SJohn Levon 	/* Fall through */
539*1f5207b7SJohn Levon 	case OP_AND:
540*1f5207b7SJohn Levon 		if (!value)
541*1f5207b7SJohn Levon 			return replace_with_pseudo(insn, insn->src2);
542*1f5207b7SJohn Levon 		return 0;
543*1f5207b7SJohn Levon 
544*1f5207b7SJohn Levon 	case OP_SET_NE:
545*1f5207b7SJohn Levon 	case OP_SET_EQ:
546*1f5207b7SJohn Levon 		return simplify_seteq_setne(insn, value);
547*1f5207b7SJohn Levon 	}
548*1f5207b7SJohn Levon 	return 0;
549*1f5207b7SJohn Levon }
550*1f5207b7SJohn Levon 
551*1f5207b7SJohn Levon static int simplify_constant_leftside(struct instruction *insn)
552*1f5207b7SJohn Levon {
553*1f5207b7SJohn Levon 	long long value = insn->src1->value;
554*1f5207b7SJohn Levon 
555*1f5207b7SJohn Levon 	switch (insn->opcode) {
556*1f5207b7SJohn Levon 	case OP_ADD: case OP_OR: case OP_XOR:
557*1f5207b7SJohn Levon 		if (!value)
558*1f5207b7SJohn Levon 			return replace_with_pseudo(insn, insn->src2);
559*1f5207b7SJohn Levon 		return 0;
560*1f5207b7SJohn Levon 
561*1f5207b7SJohn Levon 	case OP_SHL:
562*1f5207b7SJohn Levon 	case OP_LSR: case OP_ASR:
563*1f5207b7SJohn Levon 	case OP_AND:
564*1f5207b7SJohn Levon 	case OP_MULU: case OP_MULS:
565*1f5207b7SJohn Levon 		if (!value)
566*1f5207b7SJohn Levon 			return replace_with_pseudo(insn, insn->src1);
567*1f5207b7SJohn Levon 		return 0;
568*1f5207b7SJohn Levon 	}
569*1f5207b7SJohn Levon 	return 0;
570*1f5207b7SJohn Levon }
571*1f5207b7SJohn Levon 
572*1f5207b7SJohn Levon static int simplify_constant_binop(struct instruction *insn)
573*1f5207b7SJohn Levon {
574*1f5207b7SJohn Levon 	/* FIXME! Verify signs and sizes!! */
575*1f5207b7SJohn Levon 	long long left = insn->src1->value;
576*1f5207b7SJohn Levon 	long long right = insn->src2->value;
577*1f5207b7SJohn Levon 	unsigned long long ul, ur;
578*1f5207b7SJohn Levon 	long long res, mask, bits;
579*1f5207b7SJohn Levon 
580*1f5207b7SJohn Levon 	mask = 1ULL << (insn->size-1);
581*1f5207b7SJohn Levon 	bits = mask | (mask-1);
582*1f5207b7SJohn Levon 
583*1f5207b7SJohn Levon 	if (left & mask)
584*1f5207b7SJohn Levon 		left |= ~bits;
585*1f5207b7SJohn Levon 	if (right & mask)
586*1f5207b7SJohn Levon 		right |= ~bits;
587*1f5207b7SJohn Levon 	ul = left & bits;
588*1f5207b7SJohn Levon 	ur = right & bits;
589*1f5207b7SJohn Levon 
590*1f5207b7SJohn Levon 	switch (insn->opcode) {
591*1f5207b7SJohn Levon 	case OP_ADD:
592*1f5207b7SJohn Levon 		res = left + right;
593*1f5207b7SJohn Levon 		break;
594*1f5207b7SJohn Levon 	case OP_SUB:
595*1f5207b7SJohn Levon 		res = left - right;
596*1f5207b7SJohn Levon 		break;
597*1f5207b7SJohn Levon 	case OP_MULU:
598*1f5207b7SJohn Levon 		res = ul * ur;
599*1f5207b7SJohn Levon 		break;
600*1f5207b7SJohn Levon 	case OP_MULS:
601*1f5207b7SJohn Levon 		res = left * right;
602*1f5207b7SJohn Levon 		break;
603*1f5207b7SJohn Levon 	case OP_DIVU:
604*1f5207b7SJohn Levon 		if (!ur)
605*1f5207b7SJohn Levon 			return 0;
606*1f5207b7SJohn Levon 		res = ul / ur;
607*1f5207b7SJohn Levon 		break;
608*1f5207b7SJohn Levon 	case OP_DIVS:
609*1f5207b7SJohn Levon 		if (!right)
610*1f5207b7SJohn Levon 			return 0;
611*1f5207b7SJohn Levon 		if (left == mask && right == -1)
612*1f5207b7SJohn Levon 			return 0;
613*1f5207b7SJohn Levon 		res = left / right;
614*1f5207b7SJohn Levon 		break;
615*1f5207b7SJohn Levon 	case OP_MODU:
616*1f5207b7SJohn Levon 		if (!ur)
617*1f5207b7SJohn Levon 			return 0;
618*1f5207b7SJohn Levon 		res = ul % ur;
619*1f5207b7SJohn Levon 		break;
620*1f5207b7SJohn Levon 	case OP_MODS:
621*1f5207b7SJohn Levon 		if (!right)
622*1f5207b7SJohn Levon 			return 0;
623*1f5207b7SJohn Levon 		if (left == mask && right == -1)
624*1f5207b7SJohn Levon 			return 0;
625*1f5207b7SJohn Levon 		res = left % right;
626*1f5207b7SJohn Levon 		break;
627*1f5207b7SJohn Levon 	case OP_SHL:
628*1f5207b7SJohn Levon 		res = left << right;
629*1f5207b7SJohn Levon 		break;
630*1f5207b7SJohn Levon 	case OP_LSR:
631*1f5207b7SJohn Levon 		res = ul >> ur;
632*1f5207b7SJohn Levon 		break;
633*1f5207b7SJohn Levon 	case OP_ASR:
634*1f5207b7SJohn Levon 		res = left >> right;
635*1f5207b7SJohn Levon 		break;
636*1f5207b7SJohn Levon        /* Logical */
637*1f5207b7SJohn Levon 	case OP_AND:
638*1f5207b7SJohn Levon 		res = left & right;
639*1f5207b7SJohn Levon 		break;
640*1f5207b7SJohn Levon 	case OP_OR:
641*1f5207b7SJohn Levon 		res = left | right;
642*1f5207b7SJohn Levon 		break;
643*1f5207b7SJohn Levon 	case OP_XOR:
644*1f5207b7SJohn Levon 		res = left ^ right;
645*1f5207b7SJohn Levon 		break;
646*1f5207b7SJohn Levon 	case OP_AND_BOOL:
647*1f5207b7SJohn Levon 		res = left && right;
648*1f5207b7SJohn Levon 		break;
649*1f5207b7SJohn Levon 	case OP_OR_BOOL:
650*1f5207b7SJohn Levon 		res = left || right;
651*1f5207b7SJohn Levon 		break;
652*1f5207b7SJohn Levon 
653*1f5207b7SJohn Levon 	/* Binary comparison */
654*1f5207b7SJohn Levon 	case OP_SET_EQ:
655*1f5207b7SJohn Levon 		res = left == right;
656*1f5207b7SJohn Levon 		break;
657*1f5207b7SJohn Levon 	case OP_SET_NE:
658*1f5207b7SJohn Levon 		res = left != right;
659*1f5207b7SJohn Levon 		break;
660*1f5207b7SJohn Levon 	case OP_SET_LE:
661*1f5207b7SJohn Levon 		res = left <= right;
662*1f5207b7SJohn Levon 		break;
663*1f5207b7SJohn Levon 	case OP_SET_GE:
664*1f5207b7SJohn Levon 		res = left >= right;
665*1f5207b7SJohn Levon 		break;
666*1f5207b7SJohn Levon 	case OP_SET_LT:
667*1f5207b7SJohn Levon 		res = left < right;
668*1f5207b7SJohn Levon 		break;
669*1f5207b7SJohn Levon 	case OP_SET_GT:
670*1f5207b7SJohn Levon 		res = left > right;
671*1f5207b7SJohn Levon 		break;
672*1f5207b7SJohn Levon 	case OP_SET_B:
673*1f5207b7SJohn Levon 		res = ul < ur;
674*1f5207b7SJohn Levon 		break;
675*1f5207b7SJohn Levon 	case OP_SET_A:
676*1f5207b7SJohn Levon 		res = ul > ur;
677*1f5207b7SJohn Levon 		break;
678*1f5207b7SJohn Levon 	case OP_SET_BE:
679*1f5207b7SJohn Levon 		res = ul <= ur;
680*1f5207b7SJohn Levon 		break;
681*1f5207b7SJohn Levon 	case OP_SET_AE:
682*1f5207b7SJohn Levon 		res = ul >= ur;
683*1f5207b7SJohn Levon 		break;
684*1f5207b7SJohn Levon 	default:
685*1f5207b7SJohn Levon 		return 0;
686*1f5207b7SJohn Levon 	}
687*1f5207b7SJohn Levon 	res &= bits;
688*1f5207b7SJohn Levon 
689*1f5207b7SJohn Levon 	replace_with_pseudo(insn, value_pseudo(insn->type, res));
690*1f5207b7SJohn Levon 	return REPEAT_CSE;
691*1f5207b7SJohn Levon }
692*1f5207b7SJohn Levon 
693*1f5207b7SJohn Levon static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
694*1f5207b7SJohn Levon {
695*1f5207b7SJohn Levon 	switch (insn->opcode) {
696*1f5207b7SJohn Levon 	case OP_SET_NE:
697*1f5207b7SJohn Levon 	case OP_SET_LT: case OP_SET_GT:
698*1f5207b7SJohn Levon 	case OP_SET_B:  case OP_SET_A:
699*1f5207b7SJohn Levon 		if (Wtautological_compare)
700*1f5207b7SJohn Levon 			warning(insn->pos, "self-comparison always evaluates to false");
701*1f5207b7SJohn Levon 	case OP_SUB:
702*1f5207b7SJohn Levon 	case OP_XOR:
703*1f5207b7SJohn Levon 		return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
704*1f5207b7SJohn Levon 
705*1f5207b7SJohn Levon 	case OP_SET_EQ:
706*1f5207b7SJohn Levon 	case OP_SET_LE: case OP_SET_GE:
707*1f5207b7SJohn Levon 	case OP_SET_BE: case OP_SET_AE:
708*1f5207b7SJohn Levon 		if (Wtautological_compare)
709*1f5207b7SJohn Levon 			warning(insn->pos, "self-comparison always evaluates to true");
710*1f5207b7SJohn Levon 		return replace_with_pseudo(insn, value_pseudo(insn->type, 1));
711*1f5207b7SJohn Levon 
712*1f5207b7SJohn Levon 	case OP_AND:
713*1f5207b7SJohn Levon 	case OP_OR:
714*1f5207b7SJohn Levon 		return replace_with_pseudo(insn, arg);
715*1f5207b7SJohn Levon 
716*1f5207b7SJohn Levon 	case OP_AND_BOOL:
717*1f5207b7SJohn Levon 	case OP_OR_BOOL:
718*1f5207b7SJohn Levon 		remove_usage(arg, &insn->src2);
719*1f5207b7SJohn Levon 		insn->src2 = value_pseudo(insn->type, 0);
720*1f5207b7SJohn Levon 		insn->opcode = OP_SET_NE;
721*1f5207b7SJohn Levon 		return REPEAT_CSE;
722*1f5207b7SJohn Levon 
723*1f5207b7SJohn Levon 	default:
724*1f5207b7SJohn Levon 		break;
725*1f5207b7SJohn Levon 	}
726*1f5207b7SJohn Levon 
727*1f5207b7SJohn Levon 	return 0;
728*1f5207b7SJohn Levon }
729*1f5207b7SJohn Levon 
730*1f5207b7SJohn Levon static int simplify_binop(struct instruction *insn)
731*1f5207b7SJohn Levon {
732*1f5207b7SJohn Levon 	if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
733*1f5207b7SJohn Levon 		return REPEAT_CSE;
734*1f5207b7SJohn Levon 	if (constant(insn->src1)) {
735*1f5207b7SJohn Levon 		if (constant(insn->src2))
736*1f5207b7SJohn Levon 			return simplify_constant_binop(insn);
737*1f5207b7SJohn Levon 		return simplify_constant_leftside(insn);
738*1f5207b7SJohn Levon 	}
739*1f5207b7SJohn Levon 	if (constant(insn->src2))
740*1f5207b7SJohn Levon 		return simplify_constant_rightside(insn);
741*1f5207b7SJohn Levon 	if (insn->src1 == insn->src2)
742*1f5207b7SJohn Levon 		return simplify_binop_same_args(insn, insn->src1);
743*1f5207b7SJohn Levon 	return 0;
744*1f5207b7SJohn Levon }
745*1f5207b7SJohn Levon 
746*1f5207b7SJohn Levon static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
747*1f5207b7SJohn Levon {
748*1f5207b7SJohn Levon 	pseudo_t p1 = *pp1, p2 = *pp2;
749*1f5207b7SJohn Levon 
750*1f5207b7SJohn Levon 	use_pseudo(insn1, p2, pp1);
751*1f5207b7SJohn Levon 	use_pseudo(insn2, p1, pp2);
752*1f5207b7SJohn Levon 	remove_usage(p1, pp1);
753*1f5207b7SJohn Levon 	remove_usage(p2, pp2);
754*1f5207b7SJohn Levon }
755*1f5207b7SJohn Levon 
756*1f5207b7SJohn Levon static int canonical_order(pseudo_t p1, pseudo_t p2)
757*1f5207b7SJohn Levon {
758*1f5207b7SJohn Levon 	/* symbol/constants on the right */
759*1f5207b7SJohn Levon 	if (p1->type == PSEUDO_VAL)
760*1f5207b7SJohn Levon 		return p2->type == PSEUDO_VAL;
761*1f5207b7SJohn Levon 
762*1f5207b7SJohn Levon 	if (p1->type == PSEUDO_SYM)
763*1f5207b7SJohn Levon 		return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
764*1f5207b7SJohn Levon 
765*1f5207b7SJohn Levon 	return 1;
766*1f5207b7SJohn Levon }
767*1f5207b7SJohn Levon 
768*1f5207b7SJohn Levon static int simplify_commutative_binop(struct instruction *insn)
769*1f5207b7SJohn Levon {
770*1f5207b7SJohn Levon 	if (!canonical_order(insn->src1, insn->src2)) {
771*1f5207b7SJohn Levon 		switch_pseudo(insn, &insn->src1, insn, &insn->src2);
772*1f5207b7SJohn Levon 		return REPEAT_CSE;
773*1f5207b7SJohn Levon 	}
774*1f5207b7SJohn Levon 	return 0;
775*1f5207b7SJohn Levon }
776*1f5207b7SJohn Levon 
777*1f5207b7SJohn Levon static inline int simple_pseudo(pseudo_t pseudo)
778*1f5207b7SJohn Levon {
779*1f5207b7SJohn Levon 	return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
780*1f5207b7SJohn Levon }
781*1f5207b7SJohn Levon 
782*1f5207b7SJohn Levon static int simplify_associative_binop(struct instruction *insn)
783*1f5207b7SJohn Levon {
784*1f5207b7SJohn Levon 	struct instruction *def;
785*1f5207b7SJohn Levon 	pseudo_t pseudo = insn->src1;
786*1f5207b7SJohn Levon 
787*1f5207b7SJohn Levon 	if (!simple_pseudo(insn->src2))
788*1f5207b7SJohn Levon 		return 0;
789*1f5207b7SJohn Levon 	if (pseudo->type != PSEUDO_REG)
790*1f5207b7SJohn Levon 		return 0;
791*1f5207b7SJohn Levon 	def = pseudo->def;
792*1f5207b7SJohn Levon 	if (def == insn)
793*1f5207b7SJohn Levon 		return 0;
794*1f5207b7SJohn Levon 	if (def->opcode != insn->opcode)
795*1f5207b7SJohn Levon 		return 0;
796*1f5207b7SJohn Levon 	if (!simple_pseudo(def->src2))
797*1f5207b7SJohn Levon 		return 0;
798*1f5207b7SJohn Levon 	if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
799*1f5207b7SJohn Levon 		return 0;
800*1f5207b7SJohn Levon 	switch_pseudo(def, &def->src1, insn, &insn->src2);
801*1f5207b7SJohn Levon 	return REPEAT_CSE;
802*1f5207b7SJohn Levon }
803*1f5207b7SJohn Levon 
804*1f5207b7SJohn Levon static int simplify_constant_unop(struct instruction *insn)
805*1f5207b7SJohn Levon {
806*1f5207b7SJohn Levon 	long long val = insn->src1->value;
807*1f5207b7SJohn Levon 	long long res, mask;
808*1f5207b7SJohn Levon 
809*1f5207b7SJohn Levon 	switch (insn->opcode) {
810*1f5207b7SJohn Levon 	case OP_NOT:
811*1f5207b7SJohn Levon 		res = ~val;
812*1f5207b7SJohn Levon 		break;
813*1f5207b7SJohn Levon 	case OP_NEG:
814*1f5207b7SJohn Levon 		res = -val;
815*1f5207b7SJohn Levon 		break;
816*1f5207b7SJohn Levon 	default:
817*1f5207b7SJohn Levon 		return 0;
818*1f5207b7SJohn Levon 	}
819*1f5207b7SJohn Levon 	mask = 1ULL << (insn->size-1);
820*1f5207b7SJohn Levon 	res &= mask | (mask-1);
821*1f5207b7SJohn Levon 
822*1f5207b7SJohn Levon 	replace_with_pseudo(insn, value_pseudo(insn->type, res));
823*1f5207b7SJohn Levon 	return REPEAT_CSE;
824*1f5207b7SJohn Levon }
825*1f5207b7SJohn Levon 
826*1f5207b7SJohn Levon static int simplify_unop(struct instruction *insn)
827*1f5207b7SJohn Levon {
828*1f5207b7SJohn Levon 	if (dead_insn(insn, &insn->src1, NULL, NULL))
829*1f5207b7SJohn Levon 		return REPEAT_CSE;
830*1f5207b7SJohn Levon 	if (constant(insn->src1))
831*1f5207b7SJohn Levon 		return simplify_constant_unop(insn);
832*1f5207b7SJohn Levon 
833*1f5207b7SJohn Levon 	switch (insn->opcode) {
834*1f5207b7SJohn Levon 		struct instruction *def;
835*1f5207b7SJohn Levon 
836*1f5207b7SJohn Levon 	case OP_NOT:
837*1f5207b7SJohn Levon 		def = insn->src->def;
838*1f5207b7SJohn Levon 		if (def && def->opcode == OP_NOT)
839*1f5207b7SJohn Levon 			return replace_with_pseudo(insn, def->src);
840*1f5207b7SJohn Levon 		break;
841*1f5207b7SJohn Levon 	case OP_NEG:
842*1f5207b7SJohn Levon 		def = insn->src->def;
843*1f5207b7SJohn Levon 		if (def && def->opcode == OP_NEG)
844*1f5207b7SJohn Levon 			return replace_with_pseudo(insn, def->src);
845*1f5207b7SJohn Levon 		break;
846*1f5207b7SJohn Levon 	default:
847*1f5207b7SJohn Levon 		return 0;
848*1f5207b7SJohn Levon 	}
849*1f5207b7SJohn Levon 	return 0;
850*1f5207b7SJohn Levon }
851*1f5207b7SJohn Levon 
852*1f5207b7SJohn Levon static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
853*1f5207b7SJohn Levon {
854*1f5207b7SJohn Levon 	pseudo_t addr = insn->src;
855*1f5207b7SJohn Levon 	pseudo_t new, off;
856*1f5207b7SJohn Levon 
857*1f5207b7SJohn Levon 	if (addr->type == PSEUDO_REG) {
858*1f5207b7SJohn Levon 		struct instruction *def = addr->def;
859*1f5207b7SJohn Levon 		if (def->opcode == OP_SYMADDR && def->src) {
860*1f5207b7SJohn Levon 			kill_use(&insn->src);
861*1f5207b7SJohn Levon 			use_pseudo(insn, def->src, &insn->src);
862*1f5207b7SJohn Levon 			return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
863*1f5207b7SJohn Levon 		}
864*1f5207b7SJohn Levon 		if (def->opcode == OP_ADD) {
865*1f5207b7SJohn Levon 			new = def->src1;
866*1f5207b7SJohn Levon 			off = def->src2;
867*1f5207b7SJohn Levon 			if (constant(off))
868*1f5207b7SJohn Levon 				goto offset;
869*1f5207b7SJohn Levon 			new = off;
870*1f5207b7SJohn Levon 			off = def->src1;
871*1f5207b7SJohn Levon 			if (constant(off))
872*1f5207b7SJohn Levon 				goto offset;
873*1f5207b7SJohn Levon 			return 0;
874*1f5207b7SJohn Levon 		}
875*1f5207b7SJohn Levon 	}
876*1f5207b7SJohn Levon 	return 0;
877*1f5207b7SJohn Levon 
878*1f5207b7SJohn Levon offset:
879*1f5207b7SJohn Levon 	/* Invalid code */
880*1f5207b7SJohn Levon 	if (new == orig) {
881*1f5207b7SJohn Levon 		if (new == VOID)
882*1f5207b7SJohn Levon 			return 0;
883*1f5207b7SJohn Levon 		/*
884*1f5207b7SJohn Levon 		 * If some BB have been removed it is possible that this
885*1f5207b7SJohn Levon 		 * memop is in fact part of a dead BB. In this case
886*1f5207b7SJohn Levon 		 * we must not warn since nothing is wrong.
887*1f5207b7SJohn Levon 		 * If not part of a dead BB this will be redone after
888*1f5207b7SJohn Levon 		 * the BBs have been cleaned up.
889*1f5207b7SJohn Levon 		 */
890*1f5207b7SJohn Levon 		if (repeat_phase & REPEAT_CFG_CLEANUP)
891*1f5207b7SJohn Levon 			return 0;
892*1f5207b7SJohn Levon 		new = VOID;
893*1f5207b7SJohn Levon 		warning(insn->pos, "crazy programmer");
894*1f5207b7SJohn Levon 	}
895*1f5207b7SJohn Levon 	insn->offset += off->value;
896*1f5207b7SJohn Levon 	use_pseudo(insn, new, &insn->src);
897*1f5207b7SJohn Levon 	remove_usage(addr, &insn->src);
898*1f5207b7SJohn Levon 	return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
899*1f5207b7SJohn Levon }
900*1f5207b7SJohn Levon 
901*1f5207b7SJohn Levon /*
902*1f5207b7SJohn Levon  * We walk the whole chain of adds/subs backwards. That's not
903*1f5207b7SJohn Levon  * only more efficient, but it allows us to find loops.
904*1f5207b7SJohn Levon  */
905*1f5207b7SJohn Levon static int simplify_memop(struct instruction *insn)
906*1f5207b7SJohn Levon {
907*1f5207b7SJohn Levon 	int one, ret = 0;
908*1f5207b7SJohn Levon 	pseudo_t orig = insn->src;
909*1f5207b7SJohn Levon 
910*1f5207b7SJohn Levon 	do {
911*1f5207b7SJohn Levon 		one = simplify_one_memop(insn, orig);
912*1f5207b7SJohn Levon 		ret |= one;
913*1f5207b7SJohn Levon 	} while (one);
914*1f5207b7SJohn Levon 	return ret;
915*1f5207b7SJohn Levon }
916*1f5207b7SJohn Levon 
917*1f5207b7SJohn Levon static long long get_cast_value(long long val, int old_size, int new_size, int sign)
918*1f5207b7SJohn Levon {
919*1f5207b7SJohn Levon 	long long mask;
920*1f5207b7SJohn Levon 
921*1f5207b7SJohn Levon 	if (sign && new_size > old_size) {
922*1f5207b7SJohn Levon 		mask = 1 << (old_size-1);
923*1f5207b7SJohn Levon 		if (val & mask)
924*1f5207b7SJohn Levon 			val |= ~(mask | (mask-1));
925*1f5207b7SJohn Levon 	}
926*1f5207b7SJohn Levon 	mask = 1 << (new_size-1);
927*1f5207b7SJohn Levon 	return val & (mask | (mask-1));
928*1f5207b7SJohn Levon }
929*1f5207b7SJohn Levon 
930*1f5207b7SJohn Levon static int simplify_cast(struct instruction *insn)
931*1f5207b7SJohn Levon {
932*1f5207b7SJohn Levon 	struct symbol *orig_type;
933*1f5207b7SJohn Levon 	int orig_size, size;
934*1f5207b7SJohn Levon 	pseudo_t src;
935*1f5207b7SJohn Levon 
936*1f5207b7SJohn Levon 	if (dead_insn(insn, &insn->src, NULL, NULL))
937*1f5207b7SJohn Levon 		return REPEAT_CSE;
938*1f5207b7SJohn Levon 
939*1f5207b7SJohn Levon 	orig_type = insn->orig_type;
940*1f5207b7SJohn Levon 	if (!orig_type)
941*1f5207b7SJohn Levon 		return 0;
942*1f5207b7SJohn Levon 
943*1f5207b7SJohn Levon 	/* Keep casts with pointer on either side (not only case of OP_PTRCAST) */
944*1f5207b7SJohn Levon 	if (is_ptr_type(orig_type) || is_ptr_type(insn->type))
945*1f5207b7SJohn Levon 		return 0;
946*1f5207b7SJohn Levon 
947*1f5207b7SJohn Levon 	orig_size = orig_type->bit_size;
948*1f5207b7SJohn Levon 	size = insn->size;
949*1f5207b7SJohn Levon 	src = insn->src;
950*1f5207b7SJohn Levon 
951*1f5207b7SJohn Levon 	/* A cast of a constant? */
952*1f5207b7SJohn Levon 	if (constant(src)) {
953*1f5207b7SJohn Levon 		int sign = orig_type->ctype.modifiers & MOD_SIGNED;
954*1f5207b7SJohn Levon 		long long val = get_cast_value(src->value, orig_size, size, sign);
955*1f5207b7SJohn Levon 		src = value_pseudo(orig_type, val);
956*1f5207b7SJohn Levon 		goto simplify;
957*1f5207b7SJohn Levon 	}
958*1f5207b7SJohn Levon 
959*1f5207b7SJohn Levon 	/* A cast of a "and" might be a no-op.. */
960*1f5207b7SJohn Levon 	if (src->type == PSEUDO_REG) {
961*1f5207b7SJohn Levon 		struct instruction *def = src->def;
962*1f5207b7SJohn Levon 		if (def->opcode == OP_AND && def->size >= size) {
963*1f5207b7SJohn Levon 			pseudo_t val = def->src2;
964*1f5207b7SJohn Levon 			if (val->type == PSEUDO_VAL) {
965*1f5207b7SJohn Levon 				unsigned long long value = val->value;
966*1f5207b7SJohn Levon 				if (!(value >> (size-1)))
967*1f5207b7SJohn Levon 					goto simplify;
968*1f5207b7SJohn Levon 			}
969*1f5207b7SJohn Levon 		}
970*1f5207b7SJohn Levon 	}
971*1f5207b7SJohn Levon 
972*1f5207b7SJohn Levon 	if (size == orig_size) {
973*1f5207b7SJohn Levon 		int op = (orig_type->ctype.modifiers & MOD_SIGNED) ? OP_SCAST : OP_CAST;
974*1f5207b7SJohn Levon 		if (insn->opcode == op)
975*1f5207b7SJohn Levon 			goto simplify;
976*1f5207b7SJohn Levon 		if (insn->opcode == OP_FPCAST && is_float_type(orig_type))
977*1f5207b7SJohn Levon 			goto simplify;
978*1f5207b7SJohn Levon 	}
979*1f5207b7SJohn Levon 
980*1f5207b7SJohn Levon 	return 0;
981*1f5207b7SJohn Levon 
982*1f5207b7SJohn Levon simplify:
983*1f5207b7SJohn Levon 	return replace_with_pseudo(insn, src);
984*1f5207b7SJohn Levon }
985*1f5207b7SJohn Levon 
986*1f5207b7SJohn Levon static int simplify_select(struct instruction *insn)
987*1f5207b7SJohn Levon {
988*1f5207b7SJohn Levon 	pseudo_t cond, src1, src2;
989*1f5207b7SJohn Levon 
990*1f5207b7SJohn Levon 	if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
991*1f5207b7SJohn Levon 		return REPEAT_CSE;
992*1f5207b7SJohn Levon 
993*1f5207b7SJohn Levon 	cond = insn->src1;
994*1f5207b7SJohn Levon 	src1 = insn->src2;
995*1f5207b7SJohn Levon 	src2 = insn->src3;
996*1f5207b7SJohn Levon 	if (constant(cond) || src1 == src2) {
997*1f5207b7SJohn Levon 		pseudo_t *kill, take;
998*1f5207b7SJohn Levon 		kill_use(&insn->src1);
999*1f5207b7SJohn Levon 		take = cond->value ? src1 : src2;
1000*1f5207b7SJohn Levon 		kill = cond->value ? &insn->src3 : &insn->src2;
1001*1f5207b7SJohn Levon 		kill_use(kill);
1002*1f5207b7SJohn Levon 		replace_with_pseudo(insn, take);
1003*1f5207b7SJohn Levon 		return REPEAT_CSE;
1004*1f5207b7SJohn Levon 	}
1005*1f5207b7SJohn Levon 	if (constant(src1) && constant(src2)) {
1006*1f5207b7SJohn Levon 		long long val1 = src1->value;
1007*1f5207b7SJohn Levon 		long long val2 = src2->value;
1008*1f5207b7SJohn Levon 
1009*1f5207b7SJohn Levon 		/* The pair 0/1 is special - replace with SETNE/SETEQ */
1010*1f5207b7SJohn Levon 		if ((val1 | val2) == 1) {
1011*1f5207b7SJohn Levon 			int opcode = OP_SET_EQ;
1012*1f5207b7SJohn Levon 			if (val1) {
1013*1f5207b7SJohn Levon 				src1 = src2;
1014*1f5207b7SJohn Levon 				opcode = OP_SET_NE;
1015*1f5207b7SJohn Levon 			}
1016*1f5207b7SJohn Levon 			insn->opcode = opcode;
1017*1f5207b7SJohn Levon 			/* insn->src1 is already cond */
1018*1f5207b7SJohn Levon 			insn->src2 = src1; /* Zero */
1019*1f5207b7SJohn Levon 			return REPEAT_CSE;
1020*1f5207b7SJohn Levon 		}
1021*1f5207b7SJohn Levon 	}
1022*1f5207b7SJohn Levon 	return 0;
1023*1f5207b7SJohn Levon }
1024*1f5207b7SJohn Levon 
1025*1f5207b7SJohn Levon static int is_in_range(pseudo_t src, long long low, long long high)
1026*1f5207b7SJohn Levon {
1027*1f5207b7SJohn Levon 	long long value;
1028*1f5207b7SJohn Levon 
1029*1f5207b7SJohn Levon 	switch (src->type) {
1030*1f5207b7SJohn Levon 	case PSEUDO_VAL:
1031*1f5207b7SJohn Levon 		value = src->value;
1032*1f5207b7SJohn Levon 		return value >= low && value <= high;
1033*1f5207b7SJohn Levon 	default:
1034*1f5207b7SJohn Levon 		return 0;
1035*1f5207b7SJohn Levon 	}
1036*1f5207b7SJohn Levon }
1037*1f5207b7SJohn Levon 
1038*1f5207b7SJohn Levon static int simplify_range(struct instruction *insn)
1039*1f5207b7SJohn Levon {
1040*1f5207b7SJohn Levon 	pseudo_t src1, src2, src3;
1041*1f5207b7SJohn Levon 
1042*1f5207b7SJohn Levon 	src1 = insn->src1;
1043*1f5207b7SJohn Levon 	src2 = insn->src2;
1044*1f5207b7SJohn Levon 	src3 = insn->src3;
1045*1f5207b7SJohn Levon 	if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
1046*1f5207b7SJohn Levon 		return 0;
1047*1f5207b7SJohn Levon 	if (is_in_range(src1, src2->value, src3->value)) {
1048*1f5207b7SJohn Levon 		kill_instruction(insn);
1049*1f5207b7SJohn Levon 		return REPEAT_CSE;
1050*1f5207b7SJohn Levon 	}
1051*1f5207b7SJohn Levon 	return 0;
1052*1f5207b7SJohn Levon }
1053*1f5207b7SJohn Levon 
1054*1f5207b7SJohn Levon /*
1055*1f5207b7SJohn Levon  * Simplify "set_ne/eq $0 + br"
1056*1f5207b7SJohn Levon  */
1057*1f5207b7SJohn Levon static int simplify_cond_branch(struct instruction *br, pseudo_t cond, struct instruction *def, pseudo_t *pp)
1058*1f5207b7SJohn Levon {
1059*1f5207b7SJohn Levon 	use_pseudo(br, *pp, &br->cond);
1060*1f5207b7SJohn Levon 	remove_usage(cond, &br->cond);
1061*1f5207b7SJohn Levon 	if (def->opcode == OP_SET_EQ) {
1062*1f5207b7SJohn Levon 		struct basic_block *true = br->bb_true;
1063*1f5207b7SJohn Levon 		struct basic_block *false = br->bb_false;
1064*1f5207b7SJohn Levon 		br->bb_false = true;
1065*1f5207b7SJohn Levon 		br->bb_true = false;
1066*1f5207b7SJohn Levon 	}
1067*1f5207b7SJohn Levon 	return REPEAT_CSE;
1068*1f5207b7SJohn Levon }
1069*1f5207b7SJohn Levon 
1070*1f5207b7SJohn Levon static int simplify_branch(struct instruction *insn)
1071*1f5207b7SJohn Levon {
1072*1f5207b7SJohn Levon 	pseudo_t cond = insn->cond;
1073*1f5207b7SJohn Levon 
1074*1f5207b7SJohn Levon 	/* Constant conditional */
1075*1f5207b7SJohn Levon 	if (constant(cond)) {
1076*1f5207b7SJohn Levon 		insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
1077*1f5207b7SJohn Levon 		return REPEAT_CSE;
1078*1f5207b7SJohn Levon 	}
1079*1f5207b7SJohn Levon 
1080*1f5207b7SJohn Levon 	/* Same target? */
1081*1f5207b7SJohn Levon 	if (insn->bb_true == insn->bb_false) {
1082*1f5207b7SJohn Levon 		struct basic_block *bb = insn->bb;
1083*1f5207b7SJohn Levon 		struct basic_block *target = insn->bb_false;
1084*1f5207b7SJohn Levon 		remove_bb_from_list(&target->parents, bb, 1);
1085*1f5207b7SJohn Levon 		remove_bb_from_list(&bb->children, target, 1);
1086*1f5207b7SJohn Levon 		insn->bb_false = NULL;
1087*1f5207b7SJohn Levon 		kill_use(&insn->cond);
1088*1f5207b7SJohn Levon 		insn->cond = NULL;
1089*1f5207b7SJohn Levon 		insn->opcode = OP_BR;
1090*1f5207b7SJohn Levon 		return REPEAT_CSE;
1091*1f5207b7SJohn Levon 	}
1092*1f5207b7SJohn Levon 
1093*1f5207b7SJohn Levon 	/* Conditional on a SETNE $0 or SETEQ $0 */
1094*1f5207b7SJohn Levon 	if (cond->type == PSEUDO_REG) {
1095*1f5207b7SJohn Levon 		struct instruction *def = cond->def;
1096*1f5207b7SJohn Levon 
1097*1f5207b7SJohn Levon 		if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
1098*1f5207b7SJohn Levon 			if (constant(def->src1) && !def->src1->value)
1099*1f5207b7SJohn Levon 				return simplify_cond_branch(insn, cond, def, &def->src2);
1100*1f5207b7SJohn Levon 			if (constant(def->src2) && !def->src2->value)
1101*1f5207b7SJohn Levon 				return simplify_cond_branch(insn, cond, def, &def->src1);
1102*1f5207b7SJohn Levon 		}
1103*1f5207b7SJohn Levon 		if (def->opcode == OP_SEL) {
1104*1f5207b7SJohn Levon 			if (constant(def->src2) && constant(def->src3)) {
1105*1f5207b7SJohn Levon 				long long val1 = def->src2->value;
1106*1f5207b7SJohn Levon 				long long val2 = def->src3->value;
1107*1f5207b7SJohn Levon 				if (!val1 && !val2) {
1108*1f5207b7SJohn Levon 					insert_branch(insn->bb, insn, insn->bb_false);
1109*1f5207b7SJohn Levon 					return REPEAT_CSE;
1110*1f5207b7SJohn Levon 				}
1111*1f5207b7SJohn Levon 				if (val1 && val2) {
1112*1f5207b7SJohn Levon 					insert_branch(insn->bb, insn, insn->bb_true);
1113*1f5207b7SJohn Levon 					return REPEAT_CSE;
1114*1f5207b7SJohn Levon 				}
1115*1f5207b7SJohn Levon 				if (val2) {
1116*1f5207b7SJohn Levon 					struct basic_block *true = insn->bb_true;
1117*1f5207b7SJohn Levon 					struct basic_block *false = insn->bb_false;
1118*1f5207b7SJohn Levon 					insn->bb_false = true;
1119*1f5207b7SJohn Levon 					insn->bb_true = false;
1120*1f5207b7SJohn Levon 				}
1121*1f5207b7SJohn Levon 				use_pseudo(insn, def->src1, &insn->cond);
1122*1f5207b7SJohn Levon 				remove_usage(cond, &insn->cond);
1123*1f5207b7SJohn Levon 				return REPEAT_CSE;
1124*1f5207b7SJohn Levon 			}
1125*1f5207b7SJohn Levon 		}
1126*1f5207b7SJohn Levon 		if (def->opcode == OP_CAST || def->opcode == OP_SCAST) {
1127*1f5207b7SJohn Levon 			int orig_size = def->orig_type ? def->orig_type->bit_size : 0;
1128*1f5207b7SJohn Levon 			if (def->size > orig_size) {
1129*1f5207b7SJohn Levon 				use_pseudo(insn, def->src, &insn->cond);
1130*1f5207b7SJohn Levon 				remove_usage(cond, &insn->cond);
1131*1f5207b7SJohn Levon 				return REPEAT_CSE;
1132*1f5207b7SJohn Levon 			}
1133*1f5207b7SJohn Levon 		}
1134*1f5207b7SJohn Levon 	}
1135*1f5207b7SJohn Levon 	return 0;
1136*1f5207b7SJohn Levon }
1137*1f5207b7SJohn Levon 
1138*1f5207b7SJohn Levon static int simplify_switch(struct instruction *insn)
1139*1f5207b7SJohn Levon {
1140*1f5207b7SJohn Levon 	pseudo_t cond = insn->cond;
1141*1f5207b7SJohn Levon 	long long val;
1142*1f5207b7SJohn Levon 	struct multijmp *jmp;
1143*1f5207b7SJohn Levon 
1144*1f5207b7SJohn Levon 	if (!constant(cond))
1145*1f5207b7SJohn Levon 		return 0;
1146*1f5207b7SJohn Levon 	val = insn->cond->value;
1147*1f5207b7SJohn Levon 
1148*1f5207b7SJohn Levon 	FOR_EACH_PTR(insn->multijmp_list, jmp) {
1149*1f5207b7SJohn Levon 		/* Default case */
1150*1f5207b7SJohn Levon 		if (jmp->begin > jmp->end)
1151*1f5207b7SJohn Levon 			goto found;
1152*1f5207b7SJohn Levon 		if (val >= jmp->begin && val <= jmp->end)
1153*1f5207b7SJohn Levon 			goto found;
1154*1f5207b7SJohn Levon 	} END_FOR_EACH_PTR(jmp);
1155*1f5207b7SJohn Levon 	warning(insn->pos, "Impossible case statement");
1156*1f5207b7SJohn Levon 	return 0;
1157*1f5207b7SJohn Levon 
1158*1f5207b7SJohn Levon found:
1159*1f5207b7SJohn Levon 	insert_branch(insn->bb, insn, jmp->target);
1160*1f5207b7SJohn Levon 	return REPEAT_CSE;
1161*1f5207b7SJohn Levon }
1162*1f5207b7SJohn Levon 
1163*1f5207b7SJohn Levon int simplify_instruction(struct instruction *insn)
1164*1f5207b7SJohn Levon {
1165*1f5207b7SJohn Levon 	if (!insn->bb)
1166*1f5207b7SJohn Levon 		return 0;
1167*1f5207b7SJohn Levon 	switch (insn->opcode) {
1168*1f5207b7SJohn Levon 	case OP_ADD: case OP_MULS:
1169*1f5207b7SJohn Levon 	case OP_AND: case OP_OR: case OP_XOR:
1170*1f5207b7SJohn Levon 	case OP_AND_BOOL: case OP_OR_BOOL:
1171*1f5207b7SJohn Levon 		if (simplify_binop(insn))
1172*1f5207b7SJohn Levon 			return REPEAT_CSE;
1173*1f5207b7SJohn Levon 		if (simplify_commutative_binop(insn))
1174*1f5207b7SJohn Levon 			return REPEAT_CSE;
1175*1f5207b7SJohn Levon 		return simplify_associative_binop(insn);
1176*1f5207b7SJohn Levon 
1177*1f5207b7SJohn Levon 	case OP_MULU:
1178*1f5207b7SJohn Levon 	case OP_SET_EQ: case OP_SET_NE:
1179*1f5207b7SJohn Levon 		if (simplify_binop(insn))
1180*1f5207b7SJohn Levon 			return REPEAT_CSE;
1181*1f5207b7SJohn Levon 		return simplify_commutative_binop(insn);
1182*1f5207b7SJohn Levon 
1183*1f5207b7SJohn Levon 	case OP_SUB:
1184*1f5207b7SJohn Levon 	case OP_DIVU: case OP_DIVS:
1185*1f5207b7SJohn Levon 	case OP_MODU: case OP_MODS:
1186*1f5207b7SJohn Levon 	case OP_SHL:
1187*1f5207b7SJohn Levon 	case OP_LSR: case OP_ASR:
1188*1f5207b7SJohn Levon 	case OP_SET_LE: case OP_SET_GE:
1189*1f5207b7SJohn Levon 	case OP_SET_LT: case OP_SET_GT:
1190*1f5207b7SJohn Levon 	case OP_SET_B:  case OP_SET_A:
1191*1f5207b7SJohn Levon 	case OP_SET_BE: case OP_SET_AE:
1192*1f5207b7SJohn Levon 		return simplify_binop(insn);
1193*1f5207b7SJohn Levon 
1194*1f5207b7SJohn Levon 	case OP_NOT: case OP_NEG:
1195*1f5207b7SJohn Levon 		return simplify_unop(insn);
1196*1f5207b7SJohn Levon 	case OP_LOAD: case OP_STORE:
1197*1f5207b7SJohn Levon 		return simplify_memop(insn);
1198*1f5207b7SJohn Levon 	case OP_SYMADDR:
1199*1f5207b7SJohn Levon 		if (dead_insn(insn, NULL, NULL, NULL))
1200*1f5207b7SJohn Levon 			return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1201*1f5207b7SJohn Levon 		return replace_with_pseudo(insn, insn->symbol);
1202*1f5207b7SJohn Levon 	case OP_CAST:
1203*1f5207b7SJohn Levon 	case OP_SCAST:
1204*1f5207b7SJohn Levon 	case OP_FPCAST:
1205*1f5207b7SJohn Levon 	case OP_PTRCAST:
1206*1f5207b7SJohn Levon 		return simplify_cast(insn);
1207*1f5207b7SJohn Levon 	case OP_PHI:
1208*1f5207b7SJohn Levon 		if (dead_insn(insn, NULL, NULL, NULL)) {
1209*1f5207b7SJohn Levon 			kill_use_list(insn->phi_list);
1210*1f5207b7SJohn Levon 			return REPEAT_CSE;
1211*1f5207b7SJohn Levon 		}
1212*1f5207b7SJohn Levon 		return clean_up_phi(insn);
1213*1f5207b7SJohn Levon 	case OP_PHISOURCE:
1214*1f5207b7SJohn Levon 		if (dead_insn(insn, &insn->phi_src, NULL, NULL))
1215*1f5207b7SJohn Levon 			return REPEAT_CSE;
1216*1f5207b7SJohn Levon 		break;
1217*1f5207b7SJohn Levon 	case OP_SEL:
1218*1f5207b7SJohn Levon 		return simplify_select(insn);
1219*1f5207b7SJohn Levon 	case OP_CBR:
1220*1f5207b7SJohn Levon 		return simplify_branch(insn);
1221*1f5207b7SJohn Levon 	case OP_SWITCH:
1222*1f5207b7SJohn Levon 		return simplify_switch(insn);
1223*1f5207b7SJohn Levon 	case OP_RANGE:
1224*1f5207b7SJohn Levon 		return simplify_range(insn);
1225*1f5207b7SJohn Levon 	}
1226*1f5207b7SJohn Levon 	return 0;
1227*1f5207b7SJohn Levon }
1228