1/*
2 * Simplify - do instruction simplification before CSE
3 *
4 * Copyright (C) 2004 Linus Torvalds
5 */
6
7///
8// Instruction simplification
9// --------------------------
10//
11// Notation
12// ^^^^^^^^
13// The following conventions are used to describe the simplications:
14// * Uppercase letters are reserved for constants:
15//   * `M` for a constant mask,
16//   * `S` for a constant shift,
17//   * `N` for a constant number of bits (usually other than a shift),
18//   * `C` or 'K' for others constants.
19// * Lowercase letters `a`, `b`, `x`, `y`, ... are used for non-constants
20//   or when it doesn't matter if the pseudo is a constant or not.
21// * Primes are used if needed to distinguish symbols (`M`, `M'`, ...).
22// * Expressions or sub-expressions involving only constants are
23//   understood to be evaluated.
24// * `$mask(N)` is used for `((1 << N) -1)`
25// * `$trunc(x, N)` is used for `(x & $mask(N))`
26// * Expressions like `(-1 << S)`, `(-1 >> S)` and others formulae are
27//   understood to be truncated to the size of the current instruction
28//   (needed, since in general this size is not the same as the one used
29//   by sparse for the evaluation of arithmetic operations).
30// * `TRUNC(x, N)` is used for a truncation *to* a size of `N` bits
31// * `ZEXT(x, N)` is used for a zero-extension *from* a size of `N` bits
32// * `OP(x, C)` is used to represent some generic operation using a constant,
33//   including when the constant is implicit (e.g. `TRUNC(x, N)`).
34// * `MASK(x, M)` is used to respresent a 'masking' instruction:
35//   - `AND(x, M)`
36//   - `LSR(x, S)`, with `M` = (-1 << S)
37//   - `SHL(x, S)`, with `M` = (-1 >> S)
38//   - `TRUNC(x, N)`, with `M` = $mask(N)
39//   - `ZEXT(x, N)`, with `M` = $mask(N)
40// * `SHIFT(x, S)` is used for `LSR(x, S)` or `SHL(x, S)`.
41
42#include <assert.h>
43
44#include "parse.h"
45#include "expression.h"
46#include "linearize.h"
47#include "flow.h"
48#include "symbol.h"
49
50///
51// Utilities
52// ^^^^^^^^^
53
54///
55// find the trivial parent for a phi-source
56static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
57{
58	/* Can't go upwards if the pseudo is defined in the bb it came from.. */
59	if (pseudo->type == PSEUDO_REG) {
60		struct instruction *def = pseudo->def;
61		if (def->bb == source)
62			return source;
63	}
64	if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
65		return source;
66	return first_basic_block(source->parents);
67}
68
69///
70// copy the phi-node's phisrcs into to given array
71// @return: 0 if the the list contained the expected
72//	number of element, a positive number if there was
73//	more than expected and a negative one if less.
74//
75// :note: we can't reuse a function like linearize_ptr_list()
76//	because any VOIDs in the phi-list must be ignored here
77//	as in this context they mean 'entry has been removed'.
78static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
79{
80	pseudo_t phi;
81	int i = 0;
82
83	assert(insn->opcode == OP_PHI);
84	FOR_EACH_PTR(insn->phi_list, phi) {
85		struct instruction *def;
86		if (phi == VOID)
87			continue;
88		if (i >= nbr)
89			return 1;
90		def = phi->def;
91		assert(def->opcode == OP_PHISOURCE);
92		sources[i++] = def;
93	} END_FOR_EACH_PTR(phi);
94	return i - nbr;
95}
96
97static int if_convert_phi(struct instruction *insn)
98{
99	struct instruction *array[2];
100	struct basic_block *parents[3];
101	struct basic_block *bb, *bb1, *bb2, *source;
102	struct instruction *br;
103	pseudo_t p1, p2;
104
105	bb = insn->bb;
106	if (get_phisources(array, 2, insn))
107		return 0;
108	if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
109		return 0;
110	p1 = array[0]->phi_src;
111	bb1 = array[0]->bb;
112	p2 = array[1]->phi_src;
113	bb2 = array[1]->bb;
114
115	/* Only try the simple "direct parents" case */
116	if ((bb1 != parents[0] || bb2 != parents[1]) &&
117	    (bb1 != parents[1] || bb2 != parents[0]))
118		return 0;
119
120	/*
121	 * See if we can find a common source for this..
122	 */
123	source = phi_parent(bb1, p1);
124	if (source != phi_parent(bb2, p2))
125		return 0;
126
127	/*
128	 * Cool. We now know that 'source' is the exclusive
129	 * parent of both phi-nodes, so the exit at the
130	 * end of it fully determines which one it is, and
131	 * we can turn it into a select.
132	 *
133	 * HOWEVER, right now we only handle regular
134	 * conditional branches. No multijumps or computed
135	 * stuff. Verify that here.
136	 */
137	br = last_instruction(source->insns);
138	if (!br || br->opcode != OP_CBR)
139		return 0;
140
141	assert(br->cond);
142	assert(br->bb_false);
143
144	/*
145	 * We're in business. Match up true/false with p1/p2.
146	 */
147	if (br->bb_true == bb2 || br->bb_false == bb1) {
148		pseudo_t p = p1;
149		p1 = p2;
150		p2 = p;
151	}
152
153	/*
154	 * OK, we can now replace that last
155	 *
156	 *	br cond, a, b
157	 *
158	 * with the sequence
159	 *
160	 *	setcc cond
161	 *	select pseudo, p1, p2
162	 *	br cond, a, b
163	 *
164	 * and remove the phi-node. If it then
165	 * turns out that 'a' or 'b' is entirely
166	 * empty (common case), and now no longer
167	 * a phi-source, we'll be able to simplify
168	 * the conditional branch too.
169	 */
170	insert_select(source, br, insn, p1, p2);
171	kill_instruction(insn);
172	return REPEAT_CSE;
173}
174
175///
176// detect trivial phi-nodes
177// @insn: the phi-node
178// @pseudo: the candidate resulting pseudo (NULL when starting)
179// @return: the unique result if the phi-node is trivial, NULL otherwise
180//
181// A phi-node is trivial if it has a single possible result:
182//	* all operands are the same
183//	* the operands are themselves defined by a chain or cycle of phi-nodes
184//		and the set of all operands involved contains a single value
185//		not defined by these phi-nodes
186//
187// Since the result is unique, these phi-nodes can be removed.
188static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn, struct pseudo_list **list)
189{
190	pseudo_t target = insn->target;
191	pseudo_t phi;
192
193	add_pseudo(list, target);
194
195	FOR_EACH_PTR(insn->phi_list, phi) {
196		struct instruction *def;
197		pseudo_t src;
198
199		if (phi == VOID)
200			continue;
201		def = phi->def;
202		if (!def->bb)
203			continue;
204		src = def->phi_src; // bypass OP_PHISRC & get the real source
205		if (src == VOID)
206			continue;
207		if (!pseudo) {
208			pseudo = src;
209			continue;
210		}
211		if (src == pseudo)
212			continue;
213		if (src == target)
214			continue;
215		if (DEF_OPCODE(def, src) == OP_PHI) {
216			if (pseudo_in_list(*list, src))
217				continue;
218			if ((pseudo = trivial_phi(pseudo, def, list)))
219				continue;
220		}
221		return NULL;
222	} END_FOR_EACH_PTR(phi);
223
224	return pseudo ? pseudo : VOID;
225}
226
227static int clean_up_phi(struct instruction *insn)
228{
229	struct pseudo_list *list = NULL;
230	pseudo_t pseudo;
231
232	if ((pseudo = trivial_phi(NULL, insn, &list))) {
233		convert_instruction_target(insn, pseudo);
234		kill_instruction(insn);
235		return REPEAT_CSE;
236	}
237
238	return if_convert_phi(insn);
239}
240
241static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
242{
243	struct pseudo_user *pu;
244
245	FOR_EACH_PTR(*list, pu) {
246		if (pu->userp == entry) {
247			MARK_CURRENT_DELETED(pu);
248			if (!--count)
249				goto out;
250		}
251	} END_FOR_EACH_PTR(pu);
252	assert(count <= 0);
253out:
254	if (pseudo_user_list_empty(*list))
255		*list = NULL;
256	return count;
257}
258
259static inline void rem_usage(pseudo_t p, pseudo_t *usep, int kill)
260{
261	if (has_use_list(p)) {
262		if (p->type == PSEUDO_SYM)
263			repeat_phase |= REPEAT_SYMBOL_CLEANUP;
264		delete_pseudo_user_list_entry(&p->users, usep, 1);
265		if (kill && !p->users)
266			kill_instruction(p->def);
267	}
268}
269
270static inline void remove_usage(pseudo_t p, pseudo_t *usep)
271{
272	rem_usage(p, usep, 1);
273}
274
275void kill_use(pseudo_t *usep)
276{
277	if (usep) {
278		pseudo_t p = *usep;
279		*usep = VOID;
280		rem_usage(p, usep, 1);
281	}
282}
283
284// Like kill_use() but do not (recursively) kill dead instructions
285void remove_use(pseudo_t *usep)
286{
287	pseudo_t p = *usep;
288	*usep = VOID;
289	rem_usage(p, usep, 0);
290}
291
292static void kill_use_list(struct pseudo_list *list)
293{
294	pseudo_t p;
295	FOR_EACH_PTR(list, p) {
296		if (p == VOID)
297			continue;
298		kill_use(THIS_ADDRESS(p));
299	} END_FOR_EACH_PTR(p);
300}
301
302///
303// kill an instruction
304// @insn: the instruction to be killed
305// @force: if unset, the normal case, the instruction is not killed
306//	if not free of possible side-effect; if set the instruction
307//	is unconditionally killed.
308//
309// The killed instruction is removed from its BB and the usage
310// of all its operands are removed. The instruction is also
311// marked as killed by setting its ->bb to NULL.
312int kill_insn(struct instruction *insn, int force)
313{
314	if (!insn || !insn->bb)
315		return 0;
316
317	switch (insn->opcode) {
318	case OP_SEL:
319	case OP_RANGE:
320		kill_use(&insn->src3);
321		/* fall through */
322
323	case OP_BINARY ... OP_BINCMP_END:
324		kill_use(&insn->src2);
325		/* fall through */
326
327	case OP_UNOP ... OP_UNOP_END:
328	case OP_SETVAL:
329	case OP_SLICE:
330		kill_use(&insn->src1);
331		break;
332
333	case OP_PHI:
334		kill_use_list(insn->phi_list);
335		break;
336	case OP_PHISOURCE:
337		kill_use(&insn->phi_src);
338		break;
339
340	case OP_SYMADDR:
341		kill_use(&insn->src);
342		repeat_phase |= REPEAT_SYMBOL_CLEANUP;
343		break;
344
345	case OP_CBR:
346	case OP_SWITCH:
347	case OP_COMPUTEDGOTO:
348		kill_use(&insn->cond);
349		break;
350
351	case OP_CALL:
352		if (!force) {
353			/* a "pure" function can be killed too */
354			if (!(insn->func->type == PSEUDO_SYM))
355				return 0;
356			if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
357				return 0;
358		}
359		kill_use_list(insn->arguments);
360		if (insn->func->type == PSEUDO_REG)
361			kill_use(&insn->func);
362		break;
363
364	case OP_LOAD:
365		if (!force && insn->is_volatile)
366			return 0;
367		kill_use(&insn->src);
368		break;
369
370	case OP_STORE:
371		if (!force)
372			return 0;
373		kill_use(&insn->src);
374		kill_use(&insn->target);
375		break;
376
377	case OP_ENTRY:
378		/* ignore */
379		return 0;
380
381	case OP_BR:
382	case OP_SETFVAL:
383	default:
384		break;
385	}
386
387	insn->bb = NULL;
388	return repeat_phase |= REPEAT_CSE;
389}
390
391///
392// kill trivially dead instructions
393static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
394{
395	if (has_users(insn->target))
396		return 0;
397
398	insn->bb = NULL;
399	kill_use(src1);
400	kill_use(src2);
401	kill_use(src3);
402	return REPEAT_CSE;
403}
404
405static inline bool has_target(struct instruction *insn)
406{
407	return opcode_table[insn->opcode].flags & OPF_TARGET;
408}
409
410void remove_dead_insns(struct entrypoint *ep)
411{
412	struct basic_block *bb;
413
414	FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
415		struct instruction *insn;
416		FOR_EACH_PTR_REVERSE(bb->insns, insn) {
417			if (!insn->bb)
418				continue;
419			if (!has_target(insn))
420				continue;
421			if (!has_users(insn->target))
422				kill_instruction(insn);
423		} END_FOR_EACH_PTR_REVERSE(insn);
424	} END_FOR_EACH_PTR_REVERSE(bb);
425}
426
427static inline int constant(pseudo_t pseudo)
428{
429	return pseudo->type == PSEUDO_VAL;
430}
431
432///
433// replace the operand of an instruction
434// @insn: the instruction
435// @pp: the address of the instruction's operand
436// @new: the new value for the operand
437// @return: REPEAT_CSE.
438static inline int replace_pseudo(struct instruction *insn, pseudo_t *pp, pseudo_t new)
439{
440	pseudo_t old = *pp;
441	use_pseudo(insn, new, pp);
442	remove_usage(old, pp);
443	return REPEAT_CSE;
444}
445
446static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
447{
448	convert_instruction_target(insn, pseudo);
449
450	switch (insn->opcode) {
451	case OP_SEL:
452	case OP_RANGE:
453		kill_use(&insn->src3);
454	case OP_BINARY ... OP_BINCMP_END:
455		kill_use(&insn->src2);
456	case OP_UNOP ... OP_UNOP_END:
457	case OP_SYMADDR:
458		kill_use(&insn->src1);
459		break;
460
461	default:
462		assert(0);
463	}
464	insn->bb = NULL;
465	return REPEAT_CSE;
466}
467
468static inline int def_opcode(pseudo_t p)
469{
470	if (p->type != PSEUDO_REG)
471		return OP_BADOP;
472	return p->def->opcode;
473}
474
475static unsigned int value_size(long long value)
476{
477	value >>= 8;
478	if (!value)
479		return 8;
480	value >>= 8;
481	if (!value)
482		return 16;
483	value >>= 16;
484	if (!value)
485		return 32;
486	return 64;
487}
488
489///
490// try to determine the maximum size of bits in a pseudo
491//
492// Right now this only follow casts and constant values, but we
493// could look at things like AND instructions, etc.
494static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
495{
496	unsigned int size = insn->size;
497
498	if (pseudo->type == PSEUDO_REG) {
499		struct instruction *src = pseudo->def;
500		if (src && src->opcode == OP_ZEXT && src->orig_type) {
501			unsigned int orig_size = src->orig_type->bit_size;
502			if (orig_size < size)
503				size = orig_size;
504		}
505	}
506	if (pseudo->type == PSEUDO_VAL) {
507		unsigned int orig_size = value_size(pseudo->value);
508		if (orig_size < size)
509			size = orig_size;
510	}
511	return size;
512}
513
514static pseudo_t eval_insn(struct instruction *insn)
515{
516	/* FIXME! Verify signs and sizes!! */
517	unsigned int size = insn->size;
518	long long left = insn->src1->value;
519	long long right = insn->src2->value;
520	unsigned long long ul, ur;
521	long long res, mask, bits;
522
523	mask = 1ULL << (size-1);
524	bits = mask | (mask-1);
525
526	if (left & mask)
527		left |= ~bits;
528	if (right & mask)
529		right |= ~bits;
530	ul = left & bits;
531	ur = right & bits;
532
533	switch (insn->opcode) {
534	case OP_ADD:
535		res = left + right;
536		break;
537	case OP_SUB:
538		res = left - right;
539		break;
540	case OP_MUL:
541		res = ul * ur;
542		break;
543	case OP_DIVU:
544		if (!ur)
545			goto undef;
546		res = ul / ur;
547		break;
548	case OP_DIVS:
549		if (!right)
550			goto undef;
551		if (left == mask && right == -1)
552			goto undef;
553		res = left / right;
554		break;
555	case OP_MODU:
556		if (!ur)
557			goto undef;
558		res = ul % ur;
559		break;
560	case OP_MODS:
561		if (!right)
562			goto undef;
563		if (left == mask && right == -1)
564			goto undef;
565		res = left % right;
566		break;
567	case OP_SHL:
568		if (ur >= size)
569			goto undef;
570		res = left << right;
571		break;
572	case OP_LSR:
573		if (ur >= size)
574			goto undef;
575		res = ul >> ur;
576		break;
577	case OP_ASR:
578		if (ur >= size)
579			goto undef;
580		res = left >> right;
581		break;
582       /* Logical */
583	case OP_AND:
584		res = left & right;
585		break;
586	case OP_OR:
587		res = left | right;
588		break;
589	case OP_XOR:
590		res = left ^ right;
591		break;
592
593	/* Binary comparison */
594	case OP_SET_EQ:
595		res = left == right;
596		break;
597	case OP_SET_NE:
598		res = left != right;
599		break;
600	case OP_SET_LE:
601		res = left <= right;
602		break;
603	case OP_SET_GE:
604		res = left >= right;
605		break;
606	case OP_SET_LT:
607		res = left < right;
608		break;
609	case OP_SET_GT:
610		res = left > right;
611		break;
612	case OP_SET_B:
613		res = ul < ur;
614		break;
615	case OP_SET_A:
616		res = ul > ur;
617		break;
618	case OP_SET_BE:
619		res = ul <= ur;
620		break;
621	case OP_SET_AE:
622		res = ul >= ur;
623		break;
624	default:
625		return NULL;
626	}
627	res &= bits;
628
629	return value_pseudo(res);
630
631undef:
632	return NULL;
633}
634
635///
636// Simplifications
637// ^^^^^^^^^^^^^^^
638
639///
640// try to simplify MASK(OR(AND(x, M'), b), M)
641// @insn: the masking instruction
642// @mask: the associated mask (M)
643// @ora: one of the OR's operands, guaranteed to be PSEUDO_REG
644// @orb: the other OR's operand
645// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
646static int simplify_mask_or_and(struct instruction *insn, unsigned long long mask,
647	pseudo_t ora, pseudo_t orb)
648{
649	unsigned long long omask, nmask;
650	struct instruction *and = ora->def;
651	pseudo_t src2 = and->src2;
652
653	if (and->opcode != OP_AND)
654		return 0;
655	if (!constant(src2))
656		return 0;
657	omask = src2->value;
658	nmask = omask & mask;
659	if (nmask == 0) {
660		// if (M' & M) == 0: ((a & M') | b) -> b
661		return replace_pseudo(insn, &insn->src1, orb);
662	}
663	if (multi_users(insn->src1))
664		return 0;	// can't modify anything inside the OR
665	if (nmask == mask) {
666		struct instruction *or = insn->src1->def;
667		pseudo_t *arg = (ora == or->src1) ? &or->src1 : &or->src2;
668		// if (M' & M) == M: ((a & M') | b) -> (a | b)
669		return replace_pseudo(or, arg, and->src1);
670	}
671	if (nmask != omask && !multi_users(ora)) {
672		// if (M' & M) != M': AND(a, M') -> AND(a, (M' & M))
673		and->src2 = value_pseudo(nmask);
674		return REPEAT_CSE;
675	}
676	return 0;
677}
678
679///
680// try to simplify MASK(OR(a, b), M)
681// @insn: the masking instruction
682// @mask: the associated mask (M)
683// @or: the OR instruction
684// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
685static int simplify_mask_or(struct instruction *insn, unsigned long long mask, struct instruction *or)
686{
687	pseudo_t src1 = or->src1;
688	pseudo_t src2 = or->src2;
689	int rc;
690
691	if (src1->type == PSEUDO_REG) {
692		if ((rc = simplify_mask_or_and(insn, mask, src1, src2)))
693			return rc;
694	}
695	if (src2->type == PSEUDO_REG) {
696		if ((rc = simplify_mask_or_and(insn, mask, src2, src1)))
697			return rc;
698	} else if (src2->type == PSEUDO_VAL) {
699		unsigned long long oval = src2->value;
700		unsigned long long nval = oval & mask;
701		// Try to simplify:
702		//	MASK(OR(x, C), M)
703		if (nval == 0) {
704			// if (C & M) == 0: OR(x, C) -> x
705			return replace_pseudo(insn, &insn->src1, src1);
706		}
707		if (nval == mask) {
708			// if (C & M) == M: OR(x, C) -> M
709			return replace_pseudo(insn, &insn->src1, value_pseudo(mask));
710		}
711		if (nval != oval && !multi_users(or->target)) {
712			// if (C & M) != C: OR(x, C) -> OR(x, (C & M))
713			return replace_pseudo(or, &or->src2, value_pseudo(nval));
714		}
715	}
716	return 0;
717}
718
719///
720// try to simplify MASK(SHIFT(OR(a, b), S), M)
721// @sh: the shift instruction
722// @or: the OR instruction
723// @mask: the mask associated to MASK (M):
724// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
725static int simplify_mask_shift_or(struct instruction *sh, struct instruction *or, unsigned long long mask)
726{
727	unsigned long long smask = bits_mask(sh->size);
728	int shift = sh->src2->value;
729
730	if (sh->opcode == OP_LSR)
731		mask <<= shift;
732	else
733		mask >>= shift;
734	return simplify_mask_or(sh, smask & mask, or);
735}
736
737static int simplify_mask_shift(struct instruction *sh, unsigned long long mask)
738{
739	struct instruction *inner;
740
741	if (!constant(sh->src2) || sh->tainted)
742		return 0;
743	switch (DEF_OPCODE(inner, sh->src1)) {
744	case OP_OR:
745		if (!multi_users(sh->target))
746			return simplify_mask_shift_or(sh, inner, mask);
747		break;
748	}
749	return 0;
750}
751
752static long long check_shift_count(struct instruction *insn, unsigned long long uval)
753{
754	unsigned int size = insn->size;
755	long long sval = uval;
756
757	if (uval < size)
758		return uval;
759
760	sval = sign_extend_safe(sval, size);
761	sval = sign_extend_safe(sval, bits_in_int);
762	if (sval < 0)
763		insn->src2 = value_pseudo(sval);
764	if (insn->tainted)
765		return sval;
766
767	if (sval < 0 && Wshift_count_negative)
768		warning(insn->pos, "shift count is negative (%lld)", sval);
769	if (sval > 0 && Wshift_count_overflow) {
770		struct symbol *ctype = insn->type;
771		const char *tname;
772		if (ctype->type == SYM_NODE)
773			ctype = ctype->ctype.base_type;
774		tname = show_typename(ctype);
775		warning(insn->pos, "shift too big (%llu) for type %s", sval, tname);
776	}
777	insn->tainted = 1;
778	return sval;
779}
780
781static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
782{
783	struct instruction *def;
784	unsigned long long mask, omask, nmask;
785	unsigned long long nval;
786	unsigned int size;
787	pseudo_t src2;
788
789	if (!value)
790		return replace_with_pseudo(insn, pseudo);
791	value = check_shift_count(insn, value);
792	if (value < 0)
793		return 0;
794
795	size = insn->size;
796	switch (insn->opcode) {
797	case OP_ASR:
798		if (value >= size)
799			return 0;
800		if (pseudo->type != PSEUDO_REG)
801			break;
802		def = pseudo->def;
803		switch (def->opcode) {
804		case OP_LSR:
805		case OP_ASR:
806			if (def == insn)	// cyclic DAG!
807				break;
808			src2 = def->src2;
809			if (src2->type != PSEUDO_VAL)
810				break;
811			nval = src2->value;
812			if (nval > insn->size || nval == 0)
813				break;
814			value += nval;
815			if (def->opcode == OP_LSR)
816				insn->opcode = OP_LSR;
817			else if (value >= size)
818				value = size - 1;
819			goto new_value;
820
821		case OP_ZEXT:
822			// transform:
823			//	zext.N	%t <- (O) %a
824			//	asr.N	%r <- %t, C
825			// into
826			//	zext.N	%t <- (O) %a
827			//	lsr.N	%r <- %t, C
828			insn->opcode = OP_LSR;
829			return REPEAT_CSE;
830		}
831		break;
832	case OP_LSR:
833		size = operand_size(insn, pseudo);
834		if (value >= size)
835			goto zero;
836		switch(DEF_OPCODE(def, pseudo)) {
837		case OP_AND:
838			// replace (A & M) >> S
839			// by      (A >> S) & (M >> S)
840			if (!constant(def->src2))
841				break;
842			mask = bits_mask(insn->size - value) << value;
843			omask = def->src2->value;
844			nmask = omask & mask;
845			if (nmask == 0)
846				return replace_with_pseudo(insn, value_pseudo(0));
847			if (nmask == mask)
848				return replace_pseudo(insn, &insn->src1, def->src1);
849			if (nbr_users(pseudo) > 1)
850				break;
851			def->opcode = OP_LSR;
852			def->src2 = insn->src2;
853			insn->opcode = OP_AND;
854			insn->src2 = value_pseudo(omask >> value);
855			return REPEAT_CSE;
856		case OP_LSR:
857			goto case_shift_shift;
858		case OP_OR:
859			mask = bits_mask(size);
860			return simplify_mask_shift_or(insn, def, mask);
861		case OP_SHL:
862			// replace ((x << S) >> S)
863			// by      (x & (-1 >> S))
864			if (def->src2 != insn->src2)
865				break;
866			mask = bits_mask(insn->size - value);
867			goto replace_mask;
868		}
869		break;
870	case OP_SHL:
871		if (value >= size)
872			goto zero;
873		switch(DEF_OPCODE(def, pseudo)) {
874		case OP_AND:
875			// simplify (A & M) << S
876			if (!constant(def->src2))
877				break;
878			mask = bits_mask(insn->size) >> value;
879			omask = def->src2->value;
880			nmask = omask & mask;
881			if (nmask == 0)
882				return replace_with_pseudo(insn, value_pseudo(0));
883			if (nmask == mask)
884				return replace_pseudo(insn, &insn->src1, def->src1);
885			// do not simplify into ((A << S) & (M << S))
886			break;
887		case OP_LSR:
888			// replace ((x >> S) << S)
889			// by      (x & (-1 << S))
890			if (def->src2 != insn->src2)
891				break;
892			mask = bits_mask(insn->size - value) << value;
893			goto replace_mask;
894		case OP_OR:
895			mask = bits_mask(size);
896			return simplify_mask_shift_or(insn, def, mask);
897		case OP_SHL:
898		case_shift_shift:		// also for LSR - LSR
899			if (def == insn)	// cyclic DAG!
900				break;
901			src2 = def->src2;
902			if (src2->type != PSEUDO_VAL)
903				break;
904			nval = src2->value;
905			if (nval > insn->size)
906				break;
907			value += nval;
908			goto new_value;
909		}
910		break;
911	}
912	return 0;
913
914new_value:
915	if (value < size) {
916		insn->src2 = value_pseudo(value);
917		return replace_pseudo(insn, &insn->src1, pseudo->def->src1);
918	}
919zero:
920	return replace_with_pseudo(insn, value_pseudo(0));
921replace_mask:
922	insn->opcode = OP_AND;
923	insn->src2 = value_pseudo(mask);
924	return replace_pseudo(insn, &insn->src1, def->src1);
925}
926
927static int simplify_mul_div(struct instruction *insn, long long value)
928{
929	unsigned long long sbit = 1ULL << (insn->size - 1);
930	unsigned long long bits = sbit | (sbit - 1);
931
932	if (value == 1)
933		return replace_with_pseudo(insn, insn->src1);
934
935	switch (insn->opcode) {
936	case OP_MUL:
937		if (value == 0)
938			return replace_with_pseudo(insn, insn->src2);
939	/* Fall through */
940	case OP_DIVS:
941		if (!(value & sbit))	// positive
942			break;
943
944		value |= ~bits;
945		if (value == -1) {
946			insn->opcode = OP_NEG;
947			return REPEAT_CSE;
948		}
949	}
950
951	return 0;
952}
953
954static int simplify_seteq_setne(struct instruction *insn, long long value)
955{
956	pseudo_t old = insn->src1;
957	struct instruction *def;
958	unsigned osize;
959	int inverse;
960	int opcode;
961
962	if (value != 0 && value != 1)
963		return 0;
964
965	if (old->type != PSEUDO_REG)
966		return 0;
967	def = old->def;
968	if (!def)
969		return 0;
970
971	inverse = (insn->opcode == OP_SET_NE) == value;
972	if (!inverse && def->size == 1 && insn->size == 1) {
973		// Replace:
974		//	setne   %r <- %s, $0
975		// or:
976		//	seteq   %r <- %s, $1
977		// by %s when boolean
978		return replace_with_pseudo(insn, old);
979	}
980	opcode = def->opcode;
981	switch (opcode) {
982	case OP_AND:
983		if (inverse)
984			break;
985		if (def->size != insn->size)
986			break;
987		if (def->src2->type != PSEUDO_VAL)
988			break;
989		if (def->src2->value != 1)
990			break;
991		return replace_with_pseudo(insn, old);
992	case OP_FPCMP ... OP_BINCMP_END:
993		// Convert:
994		//	setcc.n	%t <- %a, %b
995		//	setne.m %r <- %t, $0
996		// into:
997		//	setcc.n	%t <- %a, %b
998		//	setcc.m %r <- %a, $b
999		// and similar for setne/eq ... 0/1
1000		insn->opcode = inverse ? opcode_table[opcode].negate : opcode;
1001		use_pseudo(insn, def->src1, &insn->src1);
1002		use_pseudo(insn, def->src2, &insn->src2);
1003		remove_usage(old, &insn->src1);
1004		return REPEAT_CSE;
1005
1006	case OP_SEXT:
1007		if (value && (def->orig_type->bit_size == 1))
1008			break;
1009		/* Fall through */
1010	case OP_ZEXT:
1011		// Convert:
1012		//	*ext.m	%s <- (1) %a
1013		//	setne.1 %r <- %s, $0
1014		// into:
1015		//	setne.1 %s <- %a, $0
1016		// and same for setne/eq ... 0/1
1017		return replace_pseudo(insn, &insn->src1, def->src);
1018	case OP_TRUNC:
1019		if (multi_users(old))
1020			break;
1021		// convert
1022		//	trunc.n	%s <- (o) %a
1023		//	setne.m %r <- %s, $0
1024		// into:
1025		//	and.o	%s <- %a, $((1 << o) - 1)
1026		//	setne.m %r <- %s, $0
1027		// and same for setne/eq ... 0/1
1028		osize = def->size;
1029		def->opcode = OP_AND;
1030		def->type = def->orig_type;
1031		def->size = def->type->bit_size;
1032		def->src2 = value_pseudo(bits_mask(osize));
1033		return REPEAT_CSE;
1034	}
1035	return 0;
1036}
1037
1038static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
1039{
1040	pseudo_t old = insn->src1;
1041	unsigned long long omask;
1042	unsigned long long nmask;
1043	struct instruction *def;
1044	int osize;
1045
1046	switch (DEF_OPCODE(def, old)) {
1047	case OP_FPCMP ... OP_BINCMP_END:
1048		osize = 1;
1049		goto oldsize;
1050	case OP_OR:
1051		return simplify_mask_or(insn, mask, def);
1052	case OP_LSR:
1053	case OP_SHL:
1054		return simplify_mask_shift(def, mask);
1055	case OP_ZEXT:
1056		osize = def->orig_type->bit_size;
1057		/* fall through */
1058	oldsize:
1059		omask = (1ULL << osize) - 1;
1060		nmask = mask & omask;
1061		if (nmask == omask)
1062			// the AND mask is redundant
1063			return replace_with_pseudo(insn, old);
1064		if (nmask != mask) {
1065			// can use a smaller mask
1066			insn->src2 = value_pseudo(nmask);
1067			return REPEAT_CSE;
1068		}
1069		break;
1070	}
1071	return 0;
1072}
1073
1074static int simplify_constant_rightside(struct instruction *insn)
1075{
1076	long long value = insn->src2->value;
1077	long long sbit = 1ULL << (insn->size - 1);
1078	long long bits = sbit | (sbit - 1);
1079
1080	switch (insn->opcode) {
1081	case OP_OR:
1082		if ((value & bits) == bits)
1083			return replace_with_pseudo(insn, insn->src2);
1084		goto case_neutral_zero;
1085
1086	case OP_XOR:
1087		if ((value & bits) == bits) {
1088			insn->opcode = OP_NOT;
1089			return REPEAT_CSE;
1090		}
1091		goto case_neutral_zero;
1092
1093	case OP_SUB:
1094		if (value) {
1095			insn->opcode = OP_ADD;
1096			insn->src2 = value_pseudo(-value);
1097			return REPEAT_CSE;
1098		}
1099	/* Fall through */
1100	case OP_ADD:
1101	case_neutral_zero:
1102		if (!value)
1103			return replace_with_pseudo(insn, insn->src1);
1104		return 0;
1105	case OP_ASR:
1106	case OP_SHL:
1107	case OP_LSR:
1108		return simplify_shift(insn, insn->src1, value);
1109
1110	case OP_MODU: case OP_MODS:
1111		if (value == 1)
1112			return replace_with_pseudo(insn, value_pseudo(0));
1113		return 0;
1114
1115	case OP_DIVU: case OP_DIVS:
1116	case OP_MUL:
1117		return simplify_mul_div(insn, value);
1118
1119	case OP_AND:
1120		if (!value)
1121			return replace_with_pseudo(insn, insn->src2);
1122		if ((value & bits) == bits)
1123			return replace_with_pseudo(insn, insn->src1);
1124		return simplify_constant_mask(insn, value);
1125
1126	case OP_SET_NE:
1127	case OP_SET_EQ:
1128		return simplify_seteq_setne(insn, value);
1129	}
1130	return 0;
1131}
1132
1133static int simplify_constant_leftside(struct instruction *insn)
1134{
1135	long long value = insn->src1->value;
1136
1137	switch (insn->opcode) {
1138	case OP_ADD: case OP_OR: case OP_XOR:
1139		if (!value)
1140			return replace_with_pseudo(insn, insn->src2);
1141		return 0;
1142
1143	case OP_SHL:
1144	case OP_LSR: case OP_ASR:
1145	case OP_AND:
1146	case OP_MUL:
1147		if (!value)
1148			return replace_with_pseudo(insn, insn->src1);
1149		return 0;
1150	}
1151	return 0;
1152}
1153
1154static int simplify_constant_binop(struct instruction *insn)
1155{
1156	pseudo_t res = eval_insn(insn);
1157
1158	if (!res)
1159		return 0;
1160
1161	replace_with_pseudo(insn, res);
1162	return REPEAT_CSE;
1163}
1164
1165static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
1166{
1167	switch (insn->opcode) {
1168	case OP_SET_NE:
1169	case OP_SET_LT: case OP_SET_GT:
1170	case OP_SET_B:  case OP_SET_A:
1171		if (Wtautological_compare)
1172			warning(insn->pos, "self-comparison always evaluates to false");
1173	case OP_SUB:
1174	case OP_XOR:
1175		return replace_with_pseudo(insn, value_pseudo(0));
1176
1177	case OP_SET_EQ:
1178	case OP_SET_LE: case OP_SET_GE:
1179	case OP_SET_BE: case OP_SET_AE:
1180		if (Wtautological_compare)
1181			warning(insn->pos, "self-comparison always evaluates to true");
1182		return replace_with_pseudo(insn, value_pseudo(1));
1183
1184	case OP_AND:
1185	case OP_OR:
1186		return replace_with_pseudo(insn, arg);
1187
1188	default:
1189		break;
1190	}
1191
1192	return 0;
1193}
1194
1195static int simplify_binop(struct instruction *insn)
1196{
1197	if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
1198		return REPEAT_CSE;
1199	if (constant(insn->src1)) {
1200		if (constant(insn->src2))
1201			return simplify_constant_binop(insn);
1202		return simplify_constant_leftside(insn);
1203	}
1204	if (constant(insn->src2))
1205		return simplify_constant_rightside(insn);
1206	if (insn->src1 == insn->src2)
1207		return simplify_binop_same_args(insn, insn->src1);
1208	return 0;
1209}
1210
1211static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
1212{
1213	pseudo_t p1 = *pp1, p2 = *pp2;
1214
1215	use_pseudo(insn1, p2, pp1);
1216	use_pseudo(insn2, p1, pp2);
1217	remove_usage(p1, pp1);
1218	remove_usage(p2, pp2);
1219}
1220
1221static int canonical_order(pseudo_t p1, pseudo_t p2)
1222{
1223	/* symbol/constants on the right */
1224	if (p1->type == PSEUDO_VAL)
1225		return p2->type == PSEUDO_VAL;
1226
1227	if (p1->type == PSEUDO_SYM)
1228		return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
1229
1230	return 1;
1231}
1232
1233static int canonicalize_commutative(struct instruction *insn)
1234{
1235	if (canonical_order(insn->src1, insn->src2))
1236		return 0;
1237
1238	switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1239	return repeat_phase |= REPEAT_CSE;
1240}
1241
1242static int canonicalize_compare(struct instruction *insn)
1243{
1244	if (canonical_order(insn->src1, insn->src2))
1245		return 0;
1246
1247	switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1248	insn->opcode = opcode_table[insn->opcode].swap;
1249	return repeat_phase |= REPEAT_CSE;
1250}
1251
1252static inline int simple_pseudo(pseudo_t pseudo)
1253{
1254	return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
1255}
1256
1257static int simplify_associative_binop(struct instruction *insn)
1258{
1259	struct instruction *def;
1260	pseudo_t pseudo = insn->src1;
1261
1262	if (!simple_pseudo(insn->src2))
1263		return 0;
1264	if (pseudo->type != PSEUDO_REG)
1265		return 0;
1266	def = pseudo->def;
1267	if (def == insn)
1268		return 0;
1269	if (def->opcode != insn->opcode)
1270		return 0;
1271	if (!simple_pseudo(def->src2))
1272		return 0;
1273	if (multi_users(def->target))
1274		return 0;
1275	switch_pseudo(def, &def->src1, insn, &insn->src2);
1276	return REPEAT_CSE;
1277}
1278
1279static int simplify_constant_unop(struct instruction *insn)
1280{
1281	long long val = insn->src1->value;
1282	long long res, mask;
1283
1284	switch (insn->opcode) {
1285	case OP_NOT:
1286		res = ~val;
1287		break;
1288	case OP_NEG:
1289		res = -val;
1290		break;
1291	case OP_SEXT:
1292		mask = 1ULL << (insn->orig_type->bit_size-1);
1293		if (val & mask)
1294			val |= ~(mask | (mask-1));
1295		/* fall through */
1296	case OP_ZEXT:
1297	case OP_TRUNC:
1298		res = val;
1299		break;
1300	default:
1301		return 0;
1302	}
1303	mask = 1ULL << (insn->size-1);
1304	res &= mask | (mask-1);
1305
1306	replace_with_pseudo(insn, value_pseudo(res));
1307	return REPEAT_CSE;
1308}
1309
1310static int simplify_unop(struct instruction *insn)
1311{
1312	if (dead_insn(insn, &insn->src1, NULL, NULL))
1313		return REPEAT_CSE;
1314	if (constant(insn->src1))
1315		return simplify_constant_unop(insn);
1316
1317	switch (insn->opcode) {
1318		struct instruction *def;
1319
1320	case OP_NOT:
1321		def = insn->src->def;
1322		if (def && def->opcode == OP_NOT)
1323			return replace_with_pseudo(insn, def->src);
1324		break;
1325	case OP_NEG:
1326		def = insn->src->def;
1327		if (def && def->opcode == OP_NEG)
1328			return replace_with_pseudo(insn, def->src);
1329		break;
1330	default:
1331		return 0;
1332	}
1333	return 0;
1334}
1335
1336static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
1337{
1338	pseudo_t addr = insn->src;
1339	pseudo_t new, off;
1340
1341	if (addr->type == PSEUDO_REG) {
1342		struct instruction *def = addr->def;
1343		if (def->opcode == OP_SYMADDR && def->src) {
1344			kill_use(&insn->src);
1345			use_pseudo(insn, def->src, &insn->src);
1346			return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1347		}
1348		if (def->opcode == OP_ADD) {
1349			new = def->src1;
1350			off = def->src2;
1351			if (constant(off))
1352				goto offset;
1353			new = off;
1354			off = def->src1;
1355			if (constant(off))
1356				goto offset;
1357			return 0;
1358		}
1359	}
1360	return 0;
1361
1362offset:
1363	/* Invalid code */
1364	if (new == orig || new == addr) {
1365		if (new == VOID)
1366			return 0;
1367		/*
1368		 * If some BB have been removed it is possible that this
1369		 * memop is in fact part of a dead BB. In this case
1370		 * we must not warn since nothing is wrong.
1371		 * If not part of a dead BB this will be redone after
1372		 * the BBs have been cleaned up.
1373		 */
1374		if (repeat_phase & REPEAT_CFG_CLEANUP)
1375			return 0;
1376		warning(insn->pos, "crazy programmer");
1377		replace_pseudo(insn, &insn->src, VOID);
1378		return 0;
1379	}
1380	insn->offset += off->value;
1381	replace_pseudo(insn, &insn->src, new);
1382	return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1383}
1384
1385///
1386// simplify memops instructions
1387//
1388// :note: We walk the whole chain of adds/subs backwards.
1389//	That's not only more efficient, but it allows us to find loops.
1390static int simplify_memop(struct instruction *insn)
1391{
1392	int one, ret = 0;
1393	pseudo_t orig = insn->src;
1394
1395	do {
1396		one = simplify_one_memop(insn, orig);
1397		ret |= one;
1398	} while (one);
1399	return ret;
1400}
1401
1402static int simplify_cast(struct instruction *insn)
1403{
1404	unsigned long long mask;
1405	struct instruction *def;
1406	pseudo_t src;
1407	pseudo_t val;
1408	int osize;
1409	int size;
1410
1411	if (dead_insn(insn, &insn->src, NULL, NULL))
1412		return REPEAT_CSE;
1413
1414	src = insn->src;
1415
1416	/* A cast of a constant? */
1417	if (constant(src))
1418		return simplify_constant_unop(insn);
1419
1420	// can merge with the previous instruction?
1421	size = insn->size;
1422	def = src->def;
1423	switch (def_opcode(src)) {
1424	case OP_AND:
1425		val = def->src2;
1426		if (val->type != PSEUDO_VAL)
1427			break;
1428		/* A cast of a AND might be a no-op.. */
1429		switch (insn->opcode) {
1430		case OP_TRUNC:
1431			if (multi_users(src))
1432				break;
1433			def->opcode = OP_TRUNC;
1434			def->orig_type = def->type;
1435			def->type = insn->type;
1436			def->size = size;
1437
1438			insn->opcode = OP_AND;
1439			mask = val->value;
1440			mask &= (1ULL << size) - 1;
1441			insn->src2 = value_pseudo(mask);
1442			return REPEAT_CSE;
1443
1444		case OP_SEXT:
1445			if (val->value & (1 << (def->size - 1)))
1446				break;
1447			// OK, sign bit is 0
1448		case OP_ZEXT:
1449			if (multi_users(src))
1450				break;
1451			// transform:
1452			//	and.n	%b <- %a, M
1453			//	*ext.m	%c <- (n) %b
1454			// into:
1455			//	zext.m	%b <- %a
1456			//	and.m	%c <- %b, M
1457			// For ZEXT, the mask will always be small
1458			// enough. For SEXT, it can only be done if
1459			// the mask force the sign bit to 0.
1460			def->opcode = OP_ZEXT;
1461			def->orig_type = insn->orig_type;
1462			def->type = insn->type;
1463			def->size = insn->size;
1464			insn->opcode = OP_AND;
1465			insn->src2 = val;
1466			return REPEAT_CSE;
1467		}
1468		break;
1469	case OP_FPCMP ... OP_BINCMP_END:
1470		switch (insn->opcode) {
1471		case OP_SEXT:
1472			if (insn->size == 1)
1473				break;
1474			/* fall through */
1475		case OP_ZEXT:
1476		case OP_TRUNC:
1477			// simplify:
1478			//	setcc.n	%t <- %a, %b
1479			//	zext.m	%r <- (n) %t
1480			// into:
1481			//	setcc.m	%r <- %a, %b
1482			// and same for s/zext/trunc/
1483			insn->opcode = def->opcode;
1484			use_pseudo(insn, def->src2, &insn->src2);
1485			return replace_pseudo(insn, &insn->src1, def->src1);
1486		}
1487		break;
1488	case OP_OR:
1489		switch (insn->opcode) {
1490		case OP_TRUNC:
1491			mask = bits_mask(insn->size);
1492			return simplify_mask_or(insn, mask, def);
1493		}
1494		break;
1495	case OP_LSR:
1496	case OP_SHL:
1497		if (insn->opcode != OP_TRUNC)
1498			break;
1499		mask = bits_mask(insn->size);
1500		return simplify_mask_shift(def, mask);
1501	case OP_TRUNC:
1502		switch (insn->opcode) {
1503		case OP_TRUNC:
1504			insn->orig_type = def->orig_type;
1505			return replace_pseudo(insn, &insn->src1, def->src);
1506		case OP_ZEXT:
1507			if (size != def->orig_type->bit_size)
1508				break;
1509			insn->opcode = OP_AND;
1510			insn->src2 = value_pseudo((1ULL << def->size) - 1);
1511			return replace_pseudo(insn, &insn->src1, def->src);
1512		}
1513		break;
1514	case OP_ZEXT:
1515		switch (insn->opcode) {
1516		case OP_SEXT:
1517			insn->opcode = OP_ZEXT;
1518			/* fall through */
1519		case OP_ZEXT:
1520			insn->orig_type = def->orig_type;
1521			return replace_pseudo(insn, &insn->src, def->src);
1522		}
1523		/* fall through */
1524	case OP_SEXT:
1525		switch (insn->opcode) {
1526		case OP_TRUNC:
1527			osize = def->orig_type->bit_size;
1528			if (size == osize)
1529				return replace_with_pseudo(insn, def->src);
1530			if (size > osize)
1531				insn->opcode = def->opcode;
1532			insn->orig_type = def->orig_type;
1533			return replace_pseudo(insn, &insn->src, def->src);
1534		}
1535		switch (insn->opcode) {
1536		case OP_SEXT:
1537			insn->orig_type = def->orig_type;
1538			return replace_pseudo(insn, &insn->src, def->src);
1539		}
1540		break;
1541	}
1542
1543	return 0;
1544}
1545
1546static int simplify_select(struct instruction *insn)
1547{
1548	pseudo_t cond, src1, src2;
1549
1550	if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
1551		return REPEAT_CSE;
1552
1553	cond = insn->src1;
1554	src1 = insn->src2;
1555	src2 = insn->src3;
1556	if (constant(cond) || src1 == src2) {
1557		pseudo_t *kill, take;
1558		kill_use(&insn->src1);
1559		take = cond->value ? src1 : src2;
1560		kill = cond->value ? &insn->src3 : &insn->src2;
1561		kill_use(kill);
1562		replace_with_pseudo(insn, take);
1563		return REPEAT_CSE;
1564	}
1565	if (constant(src1) && constant(src2)) {
1566		long long val1 = src1->value;
1567		long long val2 = src2->value;
1568
1569		/* The pair 0/1 is special - replace with SETNE/SETEQ */
1570		if ((val1 | val2) == 1) {
1571			int opcode = OP_SET_EQ;
1572			if (val1) {
1573				src1 = src2;
1574				opcode = OP_SET_NE;
1575			}
1576			insn->opcode = opcode;
1577			/* insn->src1 is already cond */
1578			insn->src2 = src1; /* Zero */
1579			return REPEAT_CSE;
1580		}
1581	}
1582	if (cond == src2 && is_zero(src1)) {
1583		kill_use(&insn->src1);
1584		kill_use(&insn->src3);
1585		replace_with_pseudo(insn, value_pseudo(0));
1586		return REPEAT_CSE;
1587	}
1588	return 0;
1589}
1590
1591static int is_in_range(pseudo_t src, long long low, long long high)
1592{
1593	long long value;
1594
1595	switch (src->type) {
1596	case PSEUDO_VAL:
1597		value = src->value;
1598		return value >= low && value <= high;
1599	default:
1600		return 0;
1601	}
1602}
1603
1604static int simplify_range(struct instruction *insn)
1605{
1606	pseudo_t src1, src2, src3;
1607
1608	src1 = insn->src1;
1609	src2 = insn->src2;
1610	src3 = insn->src3;
1611	if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
1612		return 0;
1613	if (is_in_range(src1, src2->value, src3->value)) {
1614		kill_instruction(insn);
1615		return REPEAT_CSE;
1616	}
1617	return 0;
1618}
1619
1620///
1621// simplify SET_NE/EQ $0 + BR
1622static int simplify_cond_branch(struct instruction *br, struct instruction *def, pseudo_t newcond)
1623{
1624	replace_pseudo(br, &br->cond, newcond);
1625	if (def->opcode == OP_SET_EQ) {
1626		struct basic_block *tmp = br->bb_true;
1627		br->bb_true = br->bb_false;
1628		br->bb_false = tmp;
1629	}
1630	return REPEAT_CSE;
1631}
1632
1633static int simplify_branch(struct instruction *insn)
1634{
1635	pseudo_t cond = insn->cond;
1636
1637	/* Constant conditional */
1638	if (constant(cond)) {
1639		insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
1640		return REPEAT_CSE;
1641	}
1642
1643	/* Same target? */
1644	if (insn->bb_true == insn->bb_false) {
1645		struct basic_block *bb = insn->bb;
1646		struct basic_block *target = insn->bb_false;
1647		remove_bb_from_list(&target->parents, bb, 1);
1648		remove_bb_from_list(&bb->children, target, 1);
1649		insn->bb_false = NULL;
1650		kill_use(&insn->cond);
1651		insn->cond = NULL;
1652		insn->opcode = OP_BR;
1653		return REPEAT_CSE;
1654	}
1655
1656	/* Conditional on a SETNE $0 or SETEQ $0 */
1657	if (cond->type == PSEUDO_REG) {
1658		struct instruction *def = cond->def;
1659
1660		if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
1661			if (constant(def->src1) && !def->src1->value)
1662				return simplify_cond_branch(insn, def, def->src2);
1663			if (constant(def->src2) && !def->src2->value)
1664				return simplify_cond_branch(insn, def, def->src1);
1665		}
1666		if (def->opcode == OP_SEL) {
1667			if (constant(def->src2) && constant(def->src3)) {
1668				long long val1 = def->src2->value;
1669				long long val2 = def->src3->value;
1670				if (!val1 && !val2) {
1671					insert_branch(insn->bb, insn, insn->bb_false);
1672					return REPEAT_CSE;
1673				}
1674				if (val1 && val2) {
1675					insert_branch(insn->bb, insn, insn->bb_true);
1676					return REPEAT_CSE;
1677				}
1678				if (val2) {
1679					struct basic_block *tmp = insn->bb_true;
1680					insn->bb_true = insn->bb_false;
1681					insn->bb_false = tmp;
1682				}
1683				return replace_pseudo(insn, &insn->cond, def->src1);
1684			}
1685		}
1686		if (def->opcode == OP_SEXT || def->opcode == OP_ZEXT)
1687			return replace_pseudo(insn, &insn->cond, def->src);
1688	}
1689	return 0;
1690}
1691
1692static int simplify_switch(struct instruction *insn)
1693{
1694	pseudo_t cond = insn->cond;
1695	long long val;
1696	struct multijmp *jmp;
1697
1698	if (!constant(cond))
1699		return 0;
1700	val = insn->cond->value;
1701
1702	FOR_EACH_PTR(insn->multijmp_list, jmp) {
1703		/* Default case */
1704		if (jmp->begin > jmp->end)
1705			goto found;
1706		if (val >= jmp->begin && val <= jmp->end)
1707			goto found;
1708	} END_FOR_EACH_PTR(jmp);
1709	warning(insn->pos, "Impossible case statement");
1710	return 0;
1711
1712found:
1713	insert_branch(insn->bb, insn, jmp->target);
1714	return REPEAT_CSE;
1715}
1716
1717int simplify_instruction(struct instruction *insn)
1718{
1719	if (!insn->bb)
1720		return 0;
1721	switch (insn->opcode) {
1722	case OP_ADD: case OP_MUL:
1723	case OP_AND: case OP_OR: case OP_XOR:
1724		canonicalize_commutative(insn);
1725		if (simplify_binop(insn))
1726			return REPEAT_CSE;
1727		return simplify_associative_binop(insn);
1728
1729	case OP_SET_EQ: case OP_SET_NE:
1730		canonicalize_commutative(insn);
1731		return simplify_binop(insn);
1732
1733	case OP_SET_LE: case OP_SET_GE:
1734	case OP_SET_LT: case OP_SET_GT:
1735	case OP_SET_B:  case OP_SET_A:
1736	case OP_SET_BE: case OP_SET_AE:
1737		canonicalize_compare(insn);
1738		/* fall through */
1739	case OP_SUB:
1740	case OP_DIVU: case OP_DIVS:
1741	case OP_MODU: case OP_MODS:
1742	case OP_SHL:
1743	case OP_LSR: case OP_ASR:
1744		return simplify_binop(insn);
1745
1746	case OP_NOT: case OP_NEG: case OP_FNEG:
1747		return simplify_unop(insn);
1748	case OP_LOAD:
1749		if (!has_users(insn->target))
1750			return kill_instruction(insn);
1751		/* fall-through */
1752	case OP_STORE:
1753		return simplify_memop(insn);
1754	case OP_SYMADDR:
1755		if (dead_insn(insn, &insn->src, NULL, NULL))
1756			return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1757		return replace_with_pseudo(insn, insn->src);
1758	case OP_SEXT: case OP_ZEXT:
1759	case OP_TRUNC:
1760		return simplify_cast(insn);
1761	case OP_FCVTU: case OP_FCVTS:
1762	case OP_UCVTF: case OP_SCVTF:
1763	case OP_FCVTF:
1764	case OP_PTRCAST:
1765		if (dead_insn(insn, &insn->src, NULL, NULL))
1766			return REPEAT_CSE;
1767		break;
1768	case OP_UTPTR:
1769	case OP_PTRTU:
1770		return replace_with_pseudo(insn, insn->src);
1771	case OP_SLICE:
1772		if (dead_insn(insn, &insn->src, NULL, NULL))
1773			return REPEAT_CSE;
1774		break;
1775	case OP_SETVAL:
1776	case OP_SETFVAL:
1777		if (dead_insn(insn, NULL, NULL, NULL))
1778			return REPEAT_CSE;
1779		break;
1780	case OP_PHI:
1781		if (dead_insn(insn, NULL, NULL, NULL)) {
1782			kill_use_list(insn->phi_list);
1783			return REPEAT_CSE;
1784		}
1785		return clean_up_phi(insn);
1786	case OP_PHISOURCE:
1787		if (dead_insn(insn, &insn->phi_src, NULL, NULL))
1788			return REPEAT_CSE;
1789		break;
1790	case OP_SEL:
1791		return simplify_select(insn);
1792	case OP_CBR:
1793		return simplify_branch(insn);
1794	case OP_SWITCH:
1795		return simplify_switch(insn);
1796	case OP_RANGE:
1797		return simplify_range(insn);
1798	case OP_FADD:
1799	case OP_FSUB:
1800	case OP_FMUL:
1801	case OP_FDIV:
1802		if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
1803			return REPEAT_CSE;
1804		break;
1805	}
1806	return 0;
1807}
1808