xref: /illumos-gate/usr/src/tools/smatch/src/simplify.c (revision c85f09cc)
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
phi_parent(struct basic_block * source,pseudo_t pseudo)56 static 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'.
get_phisources(struct instruction * sources[],int nbr,struct instruction * insn)78 static 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 
if_convert_phi(struct instruction * insn)97 static 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.
trivial_phi(pseudo_t pseudo,struct instruction * insn,struct pseudo_list ** list)188 static 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 
clean_up_phi(struct instruction * insn)227 static 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 
delete_pseudo_user_list_entry(struct pseudo_user_list ** list,pseudo_t * entry,int count)241 static 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);
253 out:
254 	if (pseudo_user_list_empty(*list))
255 		*list = NULL;
256 	return count;
257 }
258 
rem_usage(pseudo_t p,pseudo_t * usep,int kill)259 static 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 
remove_usage(pseudo_t p,pseudo_t * usep)270 static inline void remove_usage(pseudo_t p, pseudo_t *usep)
271 {
272 	rem_usage(p, usep, 1);
273 }
274 
kill_use(pseudo_t * usep)275 void 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
remove_use(pseudo_t * usep)285 void remove_use(pseudo_t *usep)
286 {
287 	pseudo_t p = *usep;
288 	*usep = VOID;
289 	rem_usage(p, usep, 0);
290 }
291 
kill_use_list(struct pseudo_list * list)292 static 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.
kill_insn(struct instruction * insn,int force)312 int 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
dead_insn(struct instruction * insn,pseudo_t * src1,pseudo_t * src2,pseudo_t * src3)393 static 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 
has_target(struct instruction * insn)405 static inline bool has_target(struct instruction *insn)
406 {
407 	return opcode_table[insn->opcode].flags & OPF_TARGET;
408 }
409 
remove_dead_insns(struct entrypoint * ep)410 void 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 
constant(pseudo_t pseudo)427 static 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.
replace_pseudo(struct instruction * insn,pseudo_t * pp,pseudo_t new)438 static 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 
replace_with_pseudo(struct instruction * insn,pseudo_t pseudo)446 static 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 
def_opcode(pseudo_t p)468 static 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 
value_size(long long value)475 static 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.
operand_size(struct instruction * insn,pseudo_t pseudo)494 static 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 
eval_insn(struct instruction * insn)514 static 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 
631 undef:
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.
simplify_mask_or_and(struct instruction * insn,unsigned long long mask,pseudo_t ora,pseudo_t orb)646 static 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.
simplify_mask_or(struct instruction * insn,unsigned long long mask,struct instruction * or)685 static 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.
simplify_mask_shift_or(struct instruction * sh,struct instruction * or,unsigned long long mask)725 static 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 
simplify_mask_shift(struct instruction * sh,unsigned long long mask)737 static 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 
check_shift_count(struct instruction * insn,unsigned long long uval)752 static 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 
simplify_shift(struct instruction * insn,pseudo_t pseudo,long long value)781 static 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 
914 new_value:
915 	if (value < size) {
916 		insn->src2 = value_pseudo(value);
917 		return replace_pseudo(insn, &insn->src1, pseudo->def->src1);
918 	}
919 zero:
920 	return replace_with_pseudo(insn, value_pseudo(0));
921 replace_mask:
922 	insn->opcode = OP_AND;
923 	insn->src2 = value_pseudo(mask);
924 	return replace_pseudo(insn, &insn->src1, def->src1);
925 }
926 
simplify_mul_div(struct instruction * insn,long long value)927 static 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 
simplify_seteq_setne(struct instruction * insn,long long value)954 static 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 
simplify_constant_mask(struct instruction * insn,unsigned long long mask)1038 static 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 
simplify_constant_rightside(struct instruction * insn)1074 static 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 
simplify_constant_leftside(struct instruction * insn)1133 static 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 
simplify_constant_binop(struct instruction * insn)1154 static 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 
simplify_binop_same_args(struct instruction * insn,pseudo_t arg)1165 static 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 
simplify_binop(struct instruction * insn)1195 static 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 
switch_pseudo(struct instruction * insn1,pseudo_t * pp1,struct instruction * insn2,pseudo_t * pp2)1211 static 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 
canonical_order(pseudo_t p1,pseudo_t p2)1221 static 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 
canonicalize_commutative(struct instruction * insn)1233 static 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 
canonicalize_compare(struct instruction * insn)1242 static 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 
simple_pseudo(pseudo_t pseudo)1252 static inline int simple_pseudo(pseudo_t pseudo)
1253 {
1254 	return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
1255 }
1256 
simplify_associative_binop(struct instruction * insn)1257 static 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 
simplify_constant_unop(struct instruction * insn)1279 static 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 
simplify_unop(struct instruction * insn)1310 static 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 
simplify_one_memop(struct instruction * insn,pseudo_t orig)1336 static 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 
1362 offset:
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.
simplify_memop(struct instruction * insn)1390 static 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 
simplify_cast(struct instruction * insn)1402 static 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 
simplify_select(struct instruction * insn)1546 static 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 
is_in_range(pseudo_t src,long long low,long long high)1591 static 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 
simplify_range(struct instruction * insn)1604 static 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
simplify_cond_branch(struct instruction * br,struct instruction * def,pseudo_t newcond)1622 static 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 
simplify_branch(struct instruction * insn)1633 static 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 
simplify_switch(struct instruction * insn)1692 static 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 
1712 found:
1713 	insert_branch(insn->bb, insn, jmp->target);
1714 	return REPEAT_CSE;
1715 }
1716 
simplify_instruction(struct instruction * insn)1717 int 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