xref: /illumos-gate/usr/src/tools/smatch/src/simplify.c (revision c85f09cc92abd00c84e58ec9f0f5d942906cb713)

/*
 * Simplify - do instruction simplification before CSE
 *
 * Copyright (C) 2004 Linus Torvalds
 */

///
// Instruction simplification
// --------------------------
//
// Notation
// ^^^^^^^^
// The following conventions are used to describe the simplications:
// * Uppercase letters are reserved for constants:
//   * `M` for a constant mask,
//   * `S` for a constant shift,
//   * `N` for a constant number of bits (usually other than a shift),
//   * `C` or 'K' for others constants.
// * Lowercase letters `a`, `b`, `x`, `y`, ... are used for non-constants
//   or when it doesn't matter if the pseudo is a constant or not.
// * Primes are used if needed to distinguish symbols (`M`, `M'`, ...).
// * Expressions or sub-expressions involving only constants are
//   understood to be evaluated.
// * `$mask(N)` is used for `((1 << N) -1)`
// * `$trunc(x, N)` is used for `(x & $mask(N))`
// * Expressions like `(-1 << S)`, `(-1 >> S)` and others formulae are
//   understood to be truncated to the size of the current instruction
//   (needed, since in general this size is not the same as the one used
//   by sparse for the evaluation of arithmetic operations).
// * `TRUNC(x, N)` is used for a truncation *to* a size of `N` bits
// * `ZEXT(x, N)` is used for a zero-extension *from* a size of `N` bits
// * `OP(x, C)` is used to represent some generic operation using a constant,
//   including when the constant is implicit (e.g. `TRUNC(x, N)`).
// * `MASK(x, M)` is used to respresent a 'masking' instruction:
//   - `AND(x, M)`
//   - `LSR(x, S)`, with `M` = (-1 << S)
//   - `SHL(x, S)`, with `M` = (-1 >> S)
//   - `TRUNC(x, N)`, with `M` = $mask(N)
//   - `ZEXT(x, N)`, with `M` = $mask(N)
// * `SHIFT(x, S)` is used for `LSR(x, S)` or `SHL(x, S)`.

#include <assert.h>

#include "parse.h"
#include "expression.h"
#include "linearize.h"
#include "flow.h"
#include "symbol.h"

///
// Utilities
// ^^^^^^^^^

///
// find the trivial parent for a phi-source
static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
{
	/* Can't go upwards if the pseudo is defined in the bb it came from.. */
	if (pseudo->type == PSEUDO_REG) {
		struct instruction *def = pseudo->def;
		if (def->bb == source)
			return source;
	}
	if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
		return source;
	return first_basic_block(source->parents);
}

///
// copy the phi-node's phisrcs into to given array
// @return: 0 if the the list contained the expected
//	number of element, a positive number if there was
//	more than expected and a negative one if less.
//
// :note: we can't reuse a function like linearize_ptr_list()
//	because any VOIDs in the phi-list must be ignored here
//	as in this context they mean 'entry has been removed'.
static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
{
	pseudo_t phi;
	int i = 0;

	assert(insn->opcode == OP_PHI);
	FOR_EACH_PTR(insn->phi_list, phi) {
		struct instruction *def;
		if (phi == VOID)
			continue;
		if (i >= nbr)
			return 1;
		def = phi->def;
		assert(def->opcode == OP_PHISOURCE);
		sources[i++] = def;
	} END_FOR_EACH_PTR(phi);
	return i - nbr;
}

static int if_convert_phi(struct instruction *insn)
{
	struct instruction *array[2];
	struct basic_block *parents[3];
	struct basic_block *bb, *bb1, *bb2, *source;
	struct instruction *br;
	pseudo_t p1, p2;

	bb = insn->bb;
	if (get_phisources(array, 2, insn))
		return 0;
	if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
		return 0;
	p1 = array[0]->phi_src;
	bb1 = array[0]->bb;
	p2 = array[1]->phi_src;
	bb2 = array[1]->bb;

	/* Only try the simple "direct parents" case */
	if ((bb1 != parents[0] || bb2 != parents[1]) &&
	    (bb1 != parents[1] || bb2 != parents[0]))
		return 0;

	/*
	 * See if we can find a common source for this..
	 */
	source = phi_parent(bb1, p1);
	if (source != phi_parent(bb2, p2))
		return 0;

	/*
	 * Cool. We now know that 'source' is the exclusive
	 * parent of both phi-nodes, so the exit at the
	 * end of it fully determines which one it is, and
	 * we can turn it into a select.
	 *
	 * HOWEVER, right now we only handle regular
	 * conditional branches. No multijumps or computed
	 * stuff. Verify that here.
	 */
	br = last_instruction(source->insns);
	if (!br || br->opcode != OP_CBR)
		return 0;

	assert(br->cond);
	assert(br->bb_false);

	/*
	 * We're in business. Match up true/false with p1/p2.
	 */
	if (br->bb_true == bb2 || br->bb_false == bb1) {
		pseudo_t p = p1;
		p1 = p2;
		p2 = p;
	}

	/*
	 * OK, we can now replace that last
	 *
	 *	br cond, a, b
	 *
	 * with the sequence
	 *
	 *	setcc cond
	 *	select pseudo, p1, p2
	 *	br cond, a, b
	 *
	 * and remove the phi-node. If it then
	 * turns out that 'a' or 'b' is entirely
	 * empty (common case), and now no longer
	 * a phi-source, we'll be able to simplify
	 * the conditional branch too.
	 */
	insert_select(source, br, insn, p1, p2);
	kill_instruction(insn);
	return REPEAT_CSE;
}

///
// detect trivial phi-nodes
// @insn: the phi-node
// @pseudo: the candidate resulting pseudo (NULL when starting)
// @return: the unique result if the phi-node is trivial, NULL otherwise
//
// A phi-node is trivial if it has a single possible result:
//	* all operands are the same
//	* the operands are themselves defined by a chain or cycle of phi-nodes
//		and the set of all operands involved contains a single value
//		not defined by these phi-nodes
//
// Since the result is unique, these phi-nodes can be removed.
static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn, struct pseudo_list **list)
{
	pseudo_t target = insn->target;
	pseudo_t phi;

	add_pseudo(list, target);

	FOR_EACH_PTR(insn->phi_list, phi) {
		struct instruction *def;
		pseudo_t src;

		if (phi == VOID)
			continue;
		def = phi->def;
		if (!def->bb)
			continue;
		src = def->phi_src; // bypass OP_PHISRC & get the real source
		if (src == VOID)
			continue;
		if (!pseudo) {
			pseudo = src;
			continue;
		}
		if (src == pseudo)
			continue;
		if (src == target)
			continue;
		if (DEF_OPCODE(def, src) == OP_PHI) {
			if (pseudo_in_list(*list, src))
				continue;
			if ((pseudo = trivial_phi(pseudo, def, list)))
				continue;
		}
		return NULL;
	} END_FOR_EACH_PTR(phi);

	return pseudo ? pseudo : VOID;
}

static int clean_up_phi(struct instruction *insn)
{
	struct pseudo_list *list = NULL;
	pseudo_t pseudo;

	if ((pseudo = trivial_phi(NULL, insn, &list))) {
		convert_instruction_target(insn, pseudo);
		kill_instruction(insn);
		return REPEAT_CSE;
	}

	return if_convert_phi(insn);
}

static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
{
	struct pseudo_user *pu;

	FOR_EACH_PTR(*list, pu) {
		if (pu->userp == entry) {
			MARK_CURRENT_DELETED(pu);
			if (!--count)
				goto out;
		}
	} END_FOR_EACH_PTR(pu);
	assert(count <= 0);
out:
	if (pseudo_user_list_empty(*list))
		*list = NULL;
	return count;
}

static inline void rem_usage(pseudo_t p, pseudo_t *usep, int kill)
{
	if (has_use_list(p)) {
		if (p->type == PSEUDO_SYM)
			repeat_phase |= REPEAT_SYMBOL_CLEANUP;
		delete_pseudo_user_list_entry(&p->users, usep, 1);
		if (kill && !p->users)
			kill_instruction(p->def);
	}
}

static inline void remove_usage(pseudo_t p, pseudo_t *usep)
{
	rem_usage(p, usep, 1);
}

void kill_use(pseudo_t *usep)
{
	if (usep) {
		pseudo_t p = *usep;
		*usep = VOID;
		rem_usage(p, usep, 1);
	}
}

// Like kill_use() but do not (recursively) kill dead instructions
void remove_use(pseudo_t *usep)
{
	pseudo_t p = *usep;
	*usep = VOID;
	rem_usage(p, usep, 0);
}

static void kill_use_list(struct pseudo_list *list)
{
	pseudo_t p;
	FOR_EACH_PTR(list, p) {
		if (p == VOID)
			continue;
		kill_use(THIS_ADDRESS(p));
	} END_FOR_EACH_PTR(p);
}

///
// kill an instruction
// @insn: the instruction to be killed
// @force: if unset, the normal case, the instruction is not killed
//	if not free of possible side-effect; if set the instruction
//	is unconditionally killed.
//
// The killed instruction is removed from its BB and the usage
// of all its operands are removed. The instruction is also
// marked as killed by setting its ->bb to NULL.
int kill_insn(struct instruction *insn, int force)
{
	if (!insn || !insn->bb)
		return 0;

	switch (insn->opcode) {
	case OP_SEL:
	case OP_RANGE:
		kill_use(&insn->src3);
		/* fall through */

	case OP_BINARY ... OP_BINCMP_END:
		kill_use(&insn->src2);
		/* fall through */

	case OP_UNOP ... OP_UNOP_END:
	case OP_SETVAL:
	case OP_SLICE:
		kill_use(&insn->src1);
		break;

	case OP_PHI:
		kill_use_list(insn->phi_list);
		break;
	case OP_PHISOURCE:
		kill_use(&insn->phi_src);
		break;

	case OP_SYMADDR:
		kill_use(&insn->src);
		repeat_phase |= REPEAT_SYMBOL_CLEANUP;
		break;

	case OP_CBR:
	case OP_SWITCH:
	case OP_COMPUTEDGOTO:
		kill_use(&insn->cond);
		break;

	case OP_CALL:
		if (!force) {
			/* a "pure" function can be killed too */
			if (!(insn->func->type == PSEUDO_SYM))
				return 0;
			if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
				return 0;
		}
		kill_use_list(insn->arguments);
		if (insn->func->type == PSEUDO_REG)
			kill_use(&insn->func);
		break;

	case OP_LOAD:
		if (!force && insn->is_volatile)
			return 0;
		kill_use(&insn->src);
		break;

	case OP_STORE:
		if (!force)
			return 0;
		kill_use(&insn->src);
		kill_use(&insn->target);
		break;

	case OP_ENTRY:
		/* ignore */
		return 0;

	case OP_BR:
	case OP_SETFVAL:
	default:
		break;
	}

	insn->bb = NULL;
	return repeat_phase |= REPEAT_CSE;
}

///
// kill trivially dead instructions
static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
{
	if (has_users(insn->target))
		return 0;

	insn->bb = NULL;
	kill_use(src1);
	kill_use(src2);
	kill_use(src3);
	return REPEAT_CSE;
}

static inline bool has_target(struct instruction *insn)
{
	return opcode_table[insn->opcode].flags & OPF_TARGET;
}

void remove_dead_insns(struct entrypoint *ep)
{
	struct basic_block *bb;

	FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
		struct instruction *insn;
		FOR_EACH_PTR_REVERSE(bb->insns, insn) {
			if (!insn->bb)
				continue;
			if (!has_target(insn))
				continue;
			if (!has_users(insn->target))
				kill_instruction(insn);
		} END_FOR_EACH_PTR_REVERSE(insn);
	} END_FOR_EACH_PTR_REVERSE(bb);
}

static inline int constant(pseudo_t pseudo)
{
	return pseudo->type == PSEUDO_VAL;
}

///
// replace the operand of an instruction
// @insn: the instruction
// @pp: the address of the instruction's operand
// @new: the new value for the operand
// @return: REPEAT_CSE.
static inline int replace_pseudo(struct instruction *insn, pseudo_t *pp, pseudo_t new)
{
	pseudo_t old = *pp;
	use_pseudo(insn, new, pp);
	remove_usage(old, pp);
	return REPEAT_CSE;
}

static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
{
	convert_instruction_target(insn, pseudo);

	switch (insn->opcode) {
	case OP_SEL:
	case OP_RANGE:
		kill_use(&insn->src3);
	case OP_BINARY ... OP_BINCMP_END:
		kill_use(&insn->src2);
	case OP_UNOP ... OP_UNOP_END:
	case OP_SYMADDR:
		kill_use(&insn->src1);
		break;

	default:
		assert(0);
	}
	insn->bb = NULL;
	return REPEAT_CSE;
}

static inline int def_opcode(pseudo_t p)
{
	if (p->type != PSEUDO_REG)
		return OP_BADOP;
	return p->def->opcode;
}

static unsigned int value_size(long long value)
{
	value >>= 8;
	if (!value)
		return 8;
	value >>= 8;
	if (!value)
		return 16;
	value >>= 16;
	if (!value)
		return 32;
	return 64;
}

///
// try to determine the maximum size of bits in a pseudo
//
// Right now this only follow casts and constant values, but we
// could look at things like AND instructions, etc.
static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
{
	unsigned int size = insn->size;

	if (pseudo->type == PSEUDO_REG) {
		struct instruction *src = pseudo->def;
		if (src && src->opcode == OP_ZEXT && src->orig_type) {
			unsigned int orig_size = src->orig_type->bit_size;
			if (orig_size < size)
				size = orig_size;
		}
	}
	if (pseudo->type == PSEUDO_VAL) {
		unsigned int orig_size = value_size(pseudo->value);
		if (orig_size < size)
			size = orig_size;
	}
	return size;
}

static pseudo_t eval_insn(struct instruction *insn)
{
	/* FIXME! Verify signs and sizes!! */
	unsigned int size = insn->size;
	long long left = insn->src1->value;
	long long right = insn->src2->value;
	unsigned long long ul, ur;
	long long res, mask, bits;

	mask = 1ULL << (size-1);
	bits = mask | (mask-1);

	if (left & mask)
		left |= ~bits;
	if (right & mask)
		right |= ~bits;
	ul = left & bits;
	ur = right & bits;

	switch (insn->opcode) {
	case OP_ADD:
		res = left + right;
		break;
	case OP_SUB:
		res = left - right;
		break;
	case OP_MUL:
		res = ul * ur;
		break;
	case OP_DIVU:
		if (!ur)
			goto undef;
		res = ul / ur;
		break;
	case OP_DIVS:
		if (!right)
			goto undef;
		if (left == mask && right == -1)
			goto undef;
		res = left / right;
		break;
	case OP_MODU:
		if (!ur)
			goto undef;
		res = ul % ur;
		break;
	case OP_MODS:
		if (!right)
			goto undef;
		if (left == mask && right == -1)
			goto undef;
		res = left % right;
		break;
	case OP_SHL:
		if (ur >= size)
			goto undef;
		res = left << right;
		break;
	case OP_LSR:
		if (ur >= size)
			goto undef;
		res = ul >> ur;
		break;
	case OP_ASR:
		if (ur >= size)
			goto undef;
		res = left >> right;
		break;
       /* Logical */
	case OP_AND:
		res = left & right;
		break;
	case OP_OR:
		res = left | right;
		break;
	case OP_XOR:
		res = left ^ right;
		break;

	/* Binary comparison */
	case OP_SET_EQ:
		res = left == right;
		break;
	case OP_SET_NE:
		res = left != right;
		break;
	case OP_SET_LE:
		res = left <= right;
		break;
	case OP_SET_GE:
		res = left >= right;
		break;
	case OP_SET_LT:
		res = left < right;
		break;
	case OP_SET_GT:
		res = left > right;
		break;
	case OP_SET_B:
		res = ul < ur;
		break;
	case OP_SET_A:
		res = ul > ur;
		break;
	case OP_SET_BE:
		res = ul <= ur;
		break;
	case OP_SET_AE:
		res = ul >= ur;
		break;
	default:
		return NULL;
	}
	res &= bits;

	return value_pseudo(res);

undef:
	return NULL;
}

///
// Simplifications
// ^^^^^^^^^^^^^^^

///
// try to simplify MASK(OR(AND(x, M'), b), M)
// @insn: the masking instruction
// @mask: the associated mask (M)
// @ora: one of the OR's operands, guaranteed to be PSEUDO_REG
// @orb: the other OR's operand
// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
static int simplify_mask_or_and(struct instruction *insn, unsigned long long mask,
	pseudo_t ora, pseudo_t orb)
{
	unsigned long long omask, nmask;
	struct instruction *and = ora->def;
	pseudo_t src2 = and->src2;

	if (and->opcode != OP_AND)
		return 0;
	if (!constant(src2))
		return 0;
	omask = src2->value;
	nmask = omask & mask;
	if (nmask == 0) {
		// if (M' & M) == 0: ((a & M') | b) -> b
		return replace_pseudo(insn, &insn->src1, orb);
	}
	if (multi_users(insn->src1))
		return 0;	// can't modify anything inside the OR
	if (nmask == mask) {
		struct instruction *or = insn->src1->def;
		pseudo_t *arg = (ora == or->src1) ? &or->src1 : &or->src2;
		// if (M' & M) == M: ((a & M') | b) -> (a | b)
		return replace_pseudo(or, arg, and->src1);
	}
	if (nmask != omask && !multi_users(ora)) {
		// if (M' & M) != M': AND(a, M') -> AND(a, (M' & M))
		and->src2 = value_pseudo(nmask);
		return REPEAT_CSE;
	}
	return 0;
}

///
// try to simplify MASK(OR(a, b), M)
// @insn: the masking instruction
// @mask: the associated mask (M)
// @or: the OR instruction
// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
static int simplify_mask_or(struct instruction *insn, unsigned long long mask, struct instruction *or)
{
	pseudo_t src1 = or->src1;
	pseudo_t src2 = or->src2;
	int rc;

	if (src1->type == PSEUDO_REG) {
		if ((rc = simplify_mask_or_and(insn, mask, src1, src2)))
			return rc;
	}
	if (src2->type == PSEUDO_REG) {
		if ((rc = simplify_mask_or_and(insn, mask, src2, src1)))
			return rc;
	} else if (src2->type == PSEUDO_VAL) {
		unsigned long long oval = src2->value;
		unsigned long long nval = oval & mask;
		// Try to simplify:
		//	MASK(OR(x, C), M)
		if (nval == 0) {
			// if (C & M) == 0: OR(x, C) -> x
			return replace_pseudo(insn, &insn->src1, src1);
		}
		if (nval == mask) {
			// if (C & M) == M: OR(x, C) -> M
			return replace_pseudo(insn, &insn->src1, value_pseudo(mask));
		}
		if (nval != oval && !multi_users(or->target)) {
			// if (C & M) != C: OR(x, C) -> OR(x, (C & M))
			return replace_pseudo(or, &or->src2, value_pseudo(nval));
		}
	}
	return 0;
}

///
// try to simplify MASK(SHIFT(OR(a, b), S), M)
// @sh: the shift instruction
// @or: the OR instruction
// @mask: the mask associated to MASK (M):
// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
static int simplify_mask_shift_or(struct instruction *sh, struct instruction *or, unsigned long long mask)
{
	unsigned long long smask = bits_mask(sh->size);
	int shift = sh->src2->value;

	if (sh->opcode == OP_LSR)
		mask <<= shift;
	else
		mask >>= shift;
	return simplify_mask_or(sh, smask & mask, or);
}

static int simplify_mask_shift(struct instruction *sh, unsigned long long mask)
{
	struct instruction *inner;

	if (!constant(sh->src2) || sh->tainted)
		return 0;
	switch (DEF_OPCODE(inner, sh->src1)) {
	case OP_OR:
		if (!multi_users(sh->target))
			return simplify_mask_shift_or(sh, inner, mask);
		break;
	}
	return 0;
}

static long long check_shift_count(struct instruction *insn, unsigned long long uval)
{
	unsigned int size = insn->size;
	long long sval = uval;

	if (uval < size)
		return uval;

	sval = sign_extend_safe(sval, size);
	sval = sign_extend_safe(sval, bits_in_int);
	if (sval < 0)
		insn->src2 = value_pseudo(sval);
	if (insn->tainted)
		return sval;

	if (sval < 0 && Wshift_count_negative)
		warning(insn->pos, "shift count is negative (%lld)", sval);
	if (sval > 0 && Wshift_count_overflow) {
		struct symbol *ctype = insn->type;
		const char *tname;
		if (ctype->type == SYM_NODE)
			ctype = ctype->ctype.base_type;
		tname = show_typename(ctype);
		warning(insn->pos, "shift too big (%llu) for type %s", sval, tname);
	}
	insn->tainted = 1;
	return sval;
}

static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
{
	struct instruction *def;
	unsigned long long mask, omask, nmask;
	unsigned long long nval;
	unsigned int size;
	pseudo_t src2;

	if (!value)
		return replace_with_pseudo(insn, pseudo);
	value = check_shift_count(insn, value);
	if (value < 0)
		return 0;

	size = insn->size;
	switch (insn->opcode) {
	case OP_ASR:
		if (value >= size)
			return 0;
		if (pseudo->type != PSEUDO_REG)
			break;
		def = pseudo->def;
		switch (def->opcode) {
		case OP_LSR:
		case OP_ASR:
			if (def == insn)	// cyclic DAG!
				break;
			src2 = def->src2;
			if (src2->type != PSEUDO_VAL)
				break;
			nval = src2->value;
			if (nval > insn->size || nval == 0)
				break;
			value += nval;
			if (def->opcode == OP_LSR)
				insn->opcode = OP_LSR;
			else if (value >= size)
				value = size - 1;
			goto new_value;

		case OP_ZEXT:
			// transform:
			//	zext.N	%t <- (O) %a
			//	asr.N	%r <- %t, C
			// into
			//	zext.N	%t <- (O) %a
			//	lsr.N	%r <- %t, C
			insn->opcode = OP_LSR;
			return REPEAT_CSE;
		}
		break;
	case OP_LSR:
		size = operand_size(insn, pseudo);
		if (value >= size)
			goto zero;
		switch(DEF_OPCODE(def, pseudo)) {
		case OP_AND:
			// replace (A & M) >> S
			// by      (A >> S) & (M >> S)
			if (!constant(def->src2))
				break;
			mask = bits_mask(insn->size - value) << value;
			omask = def->src2->value;
			nmask = omask & mask;
			if (nmask == 0)
				return replace_with_pseudo(insn, value_pseudo(0));
			if (nmask == mask)
				return replace_pseudo(insn, &insn->src1, def->src1);
			if (nbr_users(pseudo) > 1)
				break;
			def->opcode = OP_LSR;
			def->src2 = insn->src2;
			insn->opcode = OP_AND;
			insn->src2 = value_pseudo(omask >> value);
			return REPEAT_CSE;
		case OP_LSR:
			goto case_shift_shift;
		case OP_OR:
			mask = bits_mask(size);
			return simplify_mask_shift_or(insn, def, mask);
		case OP_SHL:
			// replace ((x << S) >> S)
			// by      (x & (-1 >> S))
			if (def->src2 != insn->src2)
				break;
			mask = bits_mask(insn->size - value);
			goto replace_mask;
		}
		break;
	case OP_SHL:
		if (value >= size)
			goto zero;
		switch(DEF_OPCODE(def, pseudo)) {
		case OP_AND:
			// simplify (A & M) << S
			if (!constant(def->src2))
				break;
			mask = bits_mask(insn->size) >> value;
			omask = def->src2->value;
			nmask = omask & mask;
			if (nmask == 0)
				return replace_with_pseudo(insn, value_pseudo(0));
			if (nmask == mask)
				return replace_pseudo(insn, &insn->src1, def->src1);
			// do not simplify into ((A << S) & (M << S))
			break;
		case OP_LSR:
			// replace ((x >> S) << S)
			// by      (x & (-1 << S))
			if (def->src2 != insn->src2)
				break;
			mask = bits_mask(insn->size - value) << value;
			goto replace_mask;
		case OP_OR:
			mask = bits_mask(size);
			return simplify_mask_shift_or(insn, def, mask);
		case OP_SHL:
		case_shift_shift:		// also for LSR - LSR
			if (def == insn)	// cyclic DAG!
				break;
			src2 = def->src2;
			if (src2->type != PSEUDO_VAL)
				break;
			nval = src2->value;
			if (nval > insn->size)
				break;
			value += nval;
			goto new_value;
		}
		break;
	}
	return 0;

new_value:
	if (value < size) {
		insn->src2 = value_pseudo(value);
		return replace_pseudo(insn, &insn->src1, pseudo->def->src1);
	}
zero:
	return replace_with_pseudo(insn, value_pseudo(0));
replace_mask:
	insn->opcode = OP_AND;
	insn->src2 = value_pseudo(mask);
	return replace_pseudo(insn, &insn->src1, def->src1);
}

static int simplify_mul_div(struct instruction *insn, long long value)
{
	unsigned long long sbit = 1ULL << (insn->size - 1);
	unsigned long long bits = sbit | (sbit - 1);

	if (value == 1)
		return replace_with_pseudo(insn, insn->src1);

	switch (insn->opcode) {
	case OP_MUL:
		if (value == 0)
			return replace_with_pseudo(insn, insn->src2);
	/* Fall through */
	case OP_DIVS:
		if (!(value & sbit))	// positive
			break;

		value |= ~bits;
		if (value == -1) {
			insn->opcode = OP_NEG;
			return REPEAT_CSE;
		}
	}

	return 0;
}

static int simplify_seteq_setne(struct instruction *insn, long long value)
{
	pseudo_t old = insn->src1;
	struct instruction *def;
	unsigned osize;
	int inverse;
	int opcode;

	if (value != 0 && value != 1)
		return 0;

	if (old->type != PSEUDO_REG)
		return 0;
	def = old->def;
	if (!def)
		return 0;

	inverse = (insn->opcode == OP_SET_NE) == value;
	if (!inverse && def->size == 1 && insn->size == 1) {
		// Replace:
		//	setne   %r <- %s, $0
		// or:
		//	seteq   %r <- %s, $1
		// by %s when boolean
		return replace_with_pseudo(insn, old);
	}
	opcode = def->opcode;
	switch (opcode) {
	case OP_AND:
		if (inverse)
			break;
		if (def->size != insn->size)
			break;
		if (def->src2->type != PSEUDO_VAL)
			break;
		if (def->src2->value != 1)
			break;
		return replace_with_pseudo(insn, old);
	case OP_FPCMP ... OP_BINCMP_END:
		// Convert:
		//	setcc.n	%t <- %a, %b
		//	setne.m %r <- %t, $0
		// into:
		//	setcc.n	%t <- %a, %b
		//	setcc.m %r <- %a, $b
		// and similar for setne/eq ... 0/1
		insn->opcode = inverse ? opcode_table[opcode].negate : opcode;
		use_pseudo(insn, def->src1, &insn->src1);
		use_pseudo(insn, def->src2, &insn->src2);
		remove_usage(old, &insn->src1);
		return REPEAT_CSE;

	case OP_SEXT:
		if (value && (def->orig_type->bit_size == 1))
			break;
		/* Fall through */
	case OP_ZEXT:
		// Convert:
		//	*ext.m	%s <- (1) %a
		//	setne.1 %r <- %s, $0
		// into:
		//	setne.1 %s <- %a, $0
		// and same for setne/eq ... 0/1
		return replace_pseudo(insn, &insn->src1, def->src);
	case OP_TRUNC:
		if (multi_users(old))
			break;
		// convert
		//	trunc.n	%s <- (o) %a
		//	setne.m %r <- %s, $0
		// into:
		//	and.o	%s <- %a, $((1 << o) - 1)
		//	setne.m %r <- %s, $0
		// and same for setne/eq ... 0/1
		osize = def->size;
		def->opcode = OP_AND;
		def->type = def->orig_type;
		def->size = def->type->bit_size;
		def->src2 = value_pseudo(bits_mask(osize));
		return REPEAT_CSE;
	}
	return 0;
}

static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
{
	pseudo_t old = insn->src1;
	unsigned long long omask;
	unsigned long long nmask;
	struct instruction *def;
	int osize;

	switch (DEF_OPCODE(def, old)) {
	case OP_FPCMP ... OP_BINCMP_END:
		osize = 1;
		goto oldsize;
	case OP_OR:
		return simplify_mask_or(insn, mask, def);
	case OP_LSR:
	case OP_SHL:
		return simplify_mask_shift(def, mask);
	case OP_ZEXT:
		osize = def->orig_type->bit_size;
		/* fall through */
	oldsize:
		omask = (1ULL << osize) - 1;
		nmask = mask & omask;
		if (nmask == omask)
			// the AND mask is redundant
			return replace_with_pseudo(insn, old);
		if (nmask != mask) {
			// can use a smaller mask
			insn->src2 = value_pseudo(nmask);
			return REPEAT_CSE;
		}
		break;
	}
	return 0;
}

static int simplify_constant_rightside(struct instruction *insn)
{
	long long value = insn->src2->value;
	long long sbit = 1ULL << (insn->size - 1);
	long long bits = sbit | (sbit - 1);

	switch (insn->opcode) {
	case OP_OR:
		if ((value & bits) == bits)
			return replace_with_pseudo(insn, insn->src2);
		goto case_neutral_zero;

	case OP_XOR:
		if ((value & bits) == bits) {
			insn->opcode = OP_NOT;
			return REPEAT_CSE;
		}
		goto case_neutral_zero;

	case OP_SUB:
		if (value) {
			insn->opcode = OP_ADD;
			insn->src2 = value_pseudo(-value);
			return REPEAT_CSE;
		}
	/* Fall through */
	case OP_ADD:
	case_neutral_zero:
		if (!value)
			return replace_with_pseudo(insn, insn->src1);
		return 0;
	case OP_ASR:
	case OP_SHL:
	case OP_LSR:
		return simplify_shift(insn, insn->src1, value);

	case OP_MODU: case OP_MODS:
		if (value == 1)
			return replace_with_pseudo(insn, value_pseudo(0));
		return 0;

	case OP_DIVU: case OP_DIVS:
	case OP_MUL:
		return simplify_mul_div(insn, value);

	case OP_AND:
		if (!value)
			return replace_with_pseudo(insn, insn->src2);
		if ((value & bits) == bits)
			return replace_with_pseudo(insn, insn->src1);
		return simplify_constant_mask(insn, value);

	case OP_SET_NE:
	case OP_SET_EQ:
		return simplify_seteq_setne(insn, value);
	}
	return 0;
}

static int simplify_constant_leftside(struct instruction *insn)
{
	long long value = insn->src1->value;

	switch (insn->opcode) {
	case OP_ADD: case OP_OR: case OP_XOR:
		if (!value)
			return replace_with_pseudo(insn, insn->src2);
		return 0;

	case OP_SHL:
	case OP_LSR: case OP_ASR:
	case OP_AND:
	case OP_MUL:
		if (!value)
			return replace_with_pseudo(insn, insn->src1);
		return 0;
	}
	return 0;
}

static int simplify_constant_binop(struct instruction *insn)
{
	pseudo_t res = eval_insn(insn);

	if (!res)
		return 0;

	replace_with_pseudo(insn, res);
	return REPEAT_CSE;
}

static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
{
	switch (insn->opcode) {
	case OP_SET_NE:
	case OP_SET_LT: case OP_SET_GT:
	case OP_SET_B:  case OP_SET_A:
		if (Wtautological_compare)
			warning(insn->pos, "self-comparison always evaluates to false");
	case OP_SUB:
	case OP_XOR:
		return replace_with_pseudo(insn, value_pseudo(0));

	case OP_SET_EQ:
	case OP_SET_LE: case OP_SET_GE:
	case OP_SET_BE: case OP_SET_AE:
		if (Wtautological_compare)
			warning(insn->pos, "self-comparison always evaluates to true");
		return replace_with_pseudo(insn, value_pseudo(1));

	case OP_AND:
	case OP_OR:
		return replace_with_pseudo(insn, arg);

	default:
		break;
	}

	return 0;
}

static int simplify_binop(struct instruction *insn)
{
	if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
		return REPEAT_CSE;
	if (constant(insn->src1)) {
		if (constant(insn->src2))
			return simplify_constant_binop(insn);
		return simplify_constant_leftside(insn);
	}
	if (constant(insn->src2))
		return simplify_constant_rightside(insn);
	if (insn->src1 == insn->src2)
		return simplify_binop_same_args(insn, insn->src1);
	return 0;
}

static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
{
	pseudo_t p1 = *pp1, p2 = *pp2;

	use_pseudo(insn1, p2, pp1);
	use_pseudo(insn2, p1, pp2);
	remove_usage(p1, pp1);
	remove_usage(p2, pp2);
}

static int canonical_order(pseudo_t p1, pseudo_t p2)
{
	/* symbol/constants on the right */
	if (p1->type == PSEUDO_VAL)
		return p2->type == PSEUDO_VAL;

	if (p1->type == PSEUDO_SYM)
		return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;

	return 1;
}

static int canonicalize_commutative(struct instruction *insn)
{
	if (canonical_order(insn->src1, insn->src2))
		return 0;

	switch_pseudo(insn, &insn->src1, insn, &insn->src2);
	return repeat_phase |= REPEAT_CSE;
}

static int canonicalize_compare(struct instruction *insn)
{
	if (canonical_order(insn->src1, insn->src2))
		return 0;

	switch_pseudo(insn, &insn->src1, insn, &insn->src2);
	insn->opcode = opcode_table[insn->opcode].swap;
	return repeat_phase |= REPEAT_CSE;
}

static inline int simple_pseudo(pseudo_t pseudo)
{
	return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
}

static int simplify_associative_binop(struct instruction *insn)
{
	struct instruction *def;
	pseudo_t pseudo = insn->src1;

	if (!simple_pseudo(insn->src2))
		return 0;
	if (pseudo->type != PSEUDO_REG)
		return 0;
	def = pseudo->def;
	if (def == insn)
		return 0;
	if (def->opcode != insn->opcode)
		return 0;
	if (!simple_pseudo(def->src2))
		return 0;
	if (multi_users(def->target))
		return 0;
	switch_pseudo(def, &def->src1, insn, &insn->src2);
	return REPEAT_CSE;
}

static int simplify_constant_unop(struct instruction *insn)
{
	long long val = insn->src1->value;
	long long res, mask;

	switch (insn->opcode) {
	case OP_NOT:
		res = ~val;
		break;
	case OP_NEG:
		res = -val;
		break;
	case OP_SEXT:
		mask = 1ULL << (insn->orig_type->bit_size-1);
		if (val & mask)
			val |= ~(mask | (mask-1));
		/* fall through */
	case OP_ZEXT:
	case OP_TRUNC:
		res = val;
		break;
	default:
		return 0;
	}
	mask = 1ULL << (insn->size-1);
	res &= mask | (mask-1);

	replace_with_pseudo(insn, value_pseudo(res));
	return REPEAT_CSE;
}

static int simplify_unop(struct instruction *insn)
{
	if (dead_insn(insn, &insn->src1, NULL, NULL))
		return REPEAT_CSE;
	if (constant(insn->src1))
		return simplify_constant_unop(insn);

	switch (insn->opcode) {
		struct instruction *def;

	case OP_NOT:
		def = insn->src->def;
		if (def && def->opcode == OP_NOT)
			return replace_with_pseudo(insn, def->src);
		break;
	case OP_NEG:
		def = insn->src->def;
		if (def && def->opcode == OP_NEG)
			return replace_with_pseudo(insn, def->src);
		break;
	default:
		return 0;
	}
	return 0;
}

static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
{
	pseudo_t addr = insn->src;
	pseudo_t new, off;

	if (addr->type == PSEUDO_REG) {
		struct instruction *def = addr->def;
		if (def->opcode == OP_SYMADDR && def->src) {
			kill_use(&insn->src);
			use_pseudo(insn, def->src, &insn->src);
			return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
		}
		if (def->opcode == OP_ADD) {
			new = def->src1;
			off = def->src2;
			if (constant(off))
				goto offset;
			new = off;
			off = def->src1;
			if (constant(off))
				goto offset;
			return 0;
		}
	}
	return 0;

offset:
	/* Invalid code */
	if (new == orig || new == addr) {
		if (new == VOID)
			return 0;
		/*
		 * If some BB have been removed it is possible that this
		 * memop is in fact part of a dead BB. In this case
		 * we must not warn since nothing is wrong.
		 * If not part of a dead BB this will be redone after
		 * the BBs have been cleaned up.
		 */
		if (repeat_phase & REPEAT_CFG_CLEANUP)
			return 0;
		warning(insn->pos, "crazy programmer");
		replace_pseudo(insn, &insn->src, VOID);
		return 0;
	}
	insn->offset += off->value;
	replace_pseudo(insn, &insn->src, new);
	return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
}

///
// simplify memops instructions
//
// :note: We walk the whole chain of adds/subs backwards.
//	That's not only more efficient, but it allows us to find loops.
static int simplify_memop(struct instruction *insn)
{
	int one, ret = 0;
	pseudo_t orig = insn->src;

	do {
		one = simplify_one_memop(insn, orig);
		ret |= one;
	} while (one);
	return ret;
}

static int simplify_cast(struct instruction *insn)
{
	unsigned long long mask;
	struct instruction *def;
	pseudo_t src;
	pseudo_t val;
	int osize;
	int size;

	if (dead_insn(insn, &insn->src, NULL, NULL))
		return REPEAT_CSE;

	src = insn->src;

	/* A cast of a constant? */
	if (constant(src))
		return simplify_constant_unop(insn);

	// can merge with the previous instruction?
	size = insn->size;
	def = src->def;
	switch (def_opcode(src)) {
	case OP_AND:
		val = def->src2;
		if (val->type != PSEUDO_VAL)
			break;
		/* A cast of a AND might be a no-op.. */
		switch (insn->opcode) {
		case OP_TRUNC:
			if (multi_users(src))
				break;
			def->opcode = OP_TRUNC;
			def->orig_type = def->type;
			def->type = insn->type;
			def->size = size;

			insn->opcode = OP_AND;
			mask = val->value;
			mask &= (1ULL << size) - 1;
			insn->src2 = value_pseudo(mask);
			return REPEAT_CSE;

		case OP_SEXT:
			if (val->value & (1 << (def->size - 1)))
				break;
			// OK, sign bit is 0
		case OP_ZEXT:
			if (multi_users(src))
				break;
			// transform:
			//	and.n	%b <- %a, M
			//	*ext.m	%c <- (n) %b
			// into:
			//	zext.m	%b <- %a
			//	and.m	%c <- %b, M
			// For ZEXT, the mask will always be small
			// enough. For SEXT, it can only be done if
			// the mask force the sign bit to 0.
			def->opcode = OP_ZEXT;
			def->orig_type = insn->orig_type;
			def->type = insn->type;
			def->size = insn->size;
			insn->opcode = OP_AND;
			insn->src2 = val;
			return REPEAT_CSE;
		}
		break;
	case OP_FPCMP ... OP_BINCMP_END:
		switch (insn->opcode) {
		case OP_SEXT:
			if (insn->size == 1)
				break;
			/* fall through */
		case OP_ZEXT:
		case OP_TRUNC:
			// simplify:
			//	setcc.n	%t <- %a, %b
			//	zext.m	%r <- (n) %t
			// into:
			//	setcc.m	%r <- %a, %b
			// and same for s/zext/trunc/
			insn->opcode = def->opcode;
			use_pseudo(insn, def->src2, &insn->src2);
			return replace_pseudo(insn, &insn->src1, def->src1);
		}
		break;
	case OP_OR:
		switch (insn->opcode) {
		case OP_TRUNC:
			mask = bits_mask(insn->size);
			return simplify_mask_or(insn, mask, def);
		}
		break;
	case OP_LSR:
	case OP_SHL:
		if (insn->opcode != OP_TRUNC)
			break;
		mask = bits_mask(insn->size);
		return simplify_mask_shift(def, mask);
	case OP_TRUNC:
		switch (insn->opcode) {
		case OP_TRUNC:
			insn->orig_type = def->orig_type;
			return replace_pseudo(insn, &insn->src1, def->src);
		case OP_ZEXT:
			if (size != def->orig_type->bit_size)
				break;
			insn->opcode = OP_AND;
			insn->src2 = value_pseudo((1ULL << def->size) - 1);
			return replace_pseudo(insn, &insn->src1, def->src);
		}
		break;
	case OP_ZEXT:
		switch (insn->opcode) {
		case OP_SEXT:
			insn->opcode = OP_ZEXT;
			/* fall through */
		case OP_ZEXT:
			insn->orig_type = def->orig_type;
			return replace_pseudo(insn, &insn->src, def->src);
		}
		/* fall through */
	case OP_SEXT:
		switch (insn->opcode) {
		case OP_TRUNC:
			osize = def->orig_type->bit_size;
			if (size == osize)
				return replace_with_pseudo(insn, def->src);
			if (size > osize)
				insn->opcode = def->opcode;
			insn->orig_type = def->orig_type;
			return replace_pseudo(insn, &insn->src, def->src);
		}
		switch (insn->opcode) {
		case OP_SEXT:
			insn->orig_type = def->orig_type;
			return replace_pseudo(insn, &insn->src, def->src);
		}
		break;
	}

	return 0;
}

static int simplify_select(struct instruction *insn)
{
	pseudo_t cond, src1, src2;

	if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
		return REPEAT_CSE;

	cond = insn->src1;
	src1 = insn->src2;
	src2 = insn->src3;
	if (constant(cond) || src1 == src2) {
		pseudo_t *kill, take;
		kill_use(&insn->src1);
		take = cond->value ? src1 : src2;
		kill = cond->value ? &insn->src3 : &insn->src2;
		kill_use(kill);
		replace_with_pseudo(insn, take);
		return REPEAT_CSE;
	}
	if (constant(src1) && constant(src2)) {
		long long val1 = src1->value;
		long long val2 = src2->value;

		/* The pair 0/1 is special - replace with SETNE/SETEQ */
		if ((val1 | val2) == 1) {
			int opcode = OP_SET_EQ;
			if (val1) {
				src1 = src2;
				opcode = OP_SET_NE;
			}
			insn->opcode = opcode;
			/* insn->src1 is already cond */
			insn->src2 = src1; /* Zero */
			return REPEAT_CSE;
		}
	}
	if (cond == src2 && is_zero(src1)) {
		kill_use(&insn->src1);
		kill_use(&insn->src3);
		replace_with_pseudo(insn, value_pseudo(0));
		return REPEAT_CSE;
	}
	return 0;
}

static int is_in_range(pseudo_t src, long long low, long long high)
{
	long long value;

	switch (src->type) {
	case PSEUDO_VAL:
		value = src->value;
		return value >= low && value <= high;
	default:
		return 0;
	}
}

static int simplify_range(struct instruction *insn)
{
	pseudo_t src1, src2, src3;

	src1 = insn->src1;
	src2 = insn->src2;
	src3 = insn->src3;
	if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
		return 0;
	if (is_in_range(src1, src2->value, src3->value)) {
		kill_instruction(insn);
		return REPEAT_CSE;
	}
	return 0;
}

///
// simplify SET_NE/EQ $0 + BR
static int simplify_cond_branch(struct instruction *br, struct instruction *def, pseudo_t newcond)
{
	replace_pseudo(br, &br->cond, newcond);
	if (def->opcode == OP_SET_EQ) {
		struct basic_block *tmp = br->bb_true;
		br->bb_true = br->bb_false;
		br->bb_false = tmp;
	}
	return REPEAT_CSE;
}

static int simplify_branch(struct instruction *insn)
{
	pseudo_t cond = insn->cond;

	/* Constant conditional */
	if (constant(cond)) {
		insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
		return REPEAT_CSE;
	}

	/* Same target? */
	if (insn->bb_true == insn->bb_false) {
		struct basic_block *bb = insn->bb;
		struct basic_block *target = insn->bb_false;
		remove_bb_from_list(&target->parents, bb, 1);
		remove_bb_from_list(&bb->children, target, 1);
		insn->bb_false = NULL;
		kill_use(&insn->cond);
		insn->cond = NULL;
		insn->opcode = OP_BR;
		return REPEAT_CSE;
	}

	/* Conditional on a SETNE $0 or SETEQ $0 */
	if (cond->type == PSEUDO_REG) {
		struct instruction *def = cond->def;

		if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
			if (constant(def->src1) && !def->src1->value)
				return simplify_cond_branch(insn, def, def->src2);
			if (constant(def->src2) && !def->src2->value)
				return simplify_cond_branch(insn, def, def->src1);
		}
		if (def->opcode == OP_SEL) {
			if (constant(def->src2) && constant(def->src3)) {
				long long val1 = def->src2->value;
				long long val2 = def->src3->value;
				if (!val1 && !val2) {
					insert_branch(insn->bb, insn, insn->bb_false);
					return REPEAT_CSE;
				}
				if (val1 && val2) {
					insert_branch(insn->bb, insn, insn->bb_true);
					return REPEAT_CSE;
				}
				if (val2) {
					struct basic_block *tmp = insn->bb_true;
					insn->bb_true = insn->bb_false;
					insn->bb_false = tmp;
				}
				return replace_pseudo(insn, &insn->cond, def->src1);
			}
		}
		if (def->opcode == OP_SEXT || def->opcode == OP_ZEXT)
			return replace_pseudo(insn, &insn->cond, def->src);
	}
	return 0;
}

static int simplify_switch(struct instruction *insn)
{
	pseudo_t cond = insn->cond;
	long long val;
	struct multijmp *jmp;

	if (!constant(cond))
		return 0;
	val = insn->cond->value;

	FOR_EACH_PTR(insn->multijmp_list, jmp) {
		/* Default case */
		if (jmp->begin > jmp->end)
			goto found;
		if (val >= jmp->begin && val <= jmp->end)
			goto found;
	} END_FOR_EACH_PTR(jmp);
	warning(insn->pos, "Impossible case statement");
	return 0;

found:
	insert_branch(insn->bb, insn, jmp->target);
	return REPEAT_CSE;
}

int simplify_instruction(struct instruction *insn)
{
	if (!insn->bb)
		return 0;
	switch (insn->opcode) {
	case OP_ADD: case OP_MUL:
	case OP_AND: case OP_OR: case OP_XOR:
		canonicalize_commutative(insn);
		if (simplify_binop(insn))
			return REPEAT_CSE;
		return simplify_associative_binop(insn);

	case OP_SET_EQ: case OP_SET_NE:
		canonicalize_commutative(insn);
		return simplify_binop(insn);

	case OP_SET_LE: case OP_SET_GE:
	case OP_SET_LT: case OP_SET_GT:
	case OP_SET_B:  case OP_SET_A:
	case OP_SET_BE: case OP_SET_AE:
		canonicalize_compare(insn);
		/* fall through */
	case OP_SUB:
	case OP_DIVU: case OP_DIVS:
	case OP_MODU: case OP_MODS:
	case OP_SHL:
	case OP_LSR: case OP_ASR:
		return simplify_binop(insn);

	case OP_NOT: case OP_NEG: case OP_FNEG:
		return simplify_unop(insn);
	case OP_LOAD:
		if (!has_users(insn->target))
			return kill_instruction(insn);
		/* fall-through */
	case OP_STORE:
		return simplify_memop(insn);
	case OP_SYMADDR:
		if (dead_insn(insn, &insn->src, NULL, NULL))
			return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
		return replace_with_pseudo(insn, insn->src);
	case OP_SEXT: case OP_ZEXT:
	case OP_TRUNC:
		return simplify_cast(insn);
	case OP_FCVTU: case OP_FCVTS:
	case OP_UCVTF: case OP_SCVTF:
	case OP_FCVTF:
	case OP_PTRCAST:
		if (dead_insn(insn, &insn->src, NULL, NULL))
			return REPEAT_CSE;
		break;
	case OP_UTPTR:
	case OP_PTRTU:
		return replace_with_pseudo(insn, insn->src);
	case OP_SLICE:
		if (dead_insn(insn, &insn->src, NULL, NULL))
			return REPEAT_CSE;
		break;
	case OP_SETVAL:
	case OP_SETFVAL:
		if (dead_insn(insn, NULL, NULL, NULL))
			return REPEAT_CSE;
		break;
	case OP_PHI:
		if (dead_insn(insn, NULL, NULL, NULL)) {
			kill_use_list(insn->phi_list);
			return REPEAT_CSE;
		}
		return clean_up_phi(insn);
	case OP_PHISOURCE:
		if (dead_insn(insn, &insn->phi_src, NULL, NULL))
			return REPEAT_CSE;
		break;
	case OP_SEL:
		return simplify_select(insn);
	case OP_CBR:
		return simplify_branch(insn);
	case OP_SWITCH:
		return simplify_switch(insn);
	case OP_RANGE:
		return simplify_range(insn);
	case OP_FADD:
	case OP_FSUB:
	case OP_FMUL:
	case OP_FDIV:
		if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
			return REPEAT_CSE;
		break;
	}
	return 0;
}