simplify.c - pub/scm/linux/kernel/git/viro/sparse - Git at Google

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

 #include <assert.h>

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

 /* 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);
 }

 static void clear_phi(struct instruction *insn)
 {
 	pseudo_t phi;

 	insn->bb = NULL;
 	FOR_EACH_PTR(insn->phi_list, phi) {
 		*THIS_ADDRESS(phi) = VOID;
 	} END_FOR_EACH_PTR(phi);
 }

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

 	bb = insn->bb;
 	if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
 		return 0;
 	if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
 		return 0;
 	p1 = array[0]->def->src1;
 	bb1 = array[0]->def->bb;
 	p2 = array[1]->def->src1;
 	bb2 = array[1]->def->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_BR)
 		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);
 	clear_phi(insn);
 	return REPEAT_CSE;
 }

 static int clean_up_phi(struct instruction *insn)
 {
 	pseudo_t phi;
 	struct instruction *last;
 	int same;

 	last = NULL;
 	same = 1;
 	FOR_EACH_PTR(insn->phi_list, phi) {
 		struct instruction *def;
 		if (phi == VOID)
 			continue;
 		def = phi->def;
 		if (def->src1 == VOID || !def->bb)
 			continue;
 		if (last) {
 			if (last->src1 != def->src1)
 				same = 0;
 			continue;
 		}
 		last = def;
 	} END_FOR_EACH_PTR(phi);

 	if (same) {
 		pseudo_t pseudo = last ? last->src1 : VOID;
 		convert_instruction_target(insn, pseudo);
 		clear_phi(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) {
 			DELETE_CURRENT_PTR(pu);
 			if (!--count)
 				goto out;
 		}
 	} END_FOR_EACH_PTR(pu);
 	assert(count <= 0);
 out:
 	pack_ptr_list((struct ptr_list **)list);
 	return count;
 }

 static inline void remove_usage(pseudo_t p, pseudo_t *usep)
 {
 	if (has_use_list(p)) {
 		delete_pseudo_user_list_entry(&p->users, usep, 1);
 		if (!p->users)
 			kill_instruction(p->def);
 	}
 }

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

 void kill_instruction(struct instruction *insn)
 {
 	if (!insn || !insn->bb)
 		return;

 	switch (insn->opcode) {
 	case OP_BINARY ... OP_BINCMP_END:
 		insn->bb = NULL;
 		kill_use(&insn->src1);
 		kill_use(&insn->src2);
 		repeat_phase |= REPEAT_CSE;
 		return;

 	case OP_NOT: case OP_NEG:
 		insn->bb = NULL;
 		kill_use(&insn->src1);
 		repeat_phase |= REPEAT_CSE;
 		return;

 	case OP_PHI:
 		insn->bb = NULL;
 		repeat_phase |= REPEAT_CSE;
 		return;

 	case OP_SYMADDR:
 		insn->bb = NULL;
 		repeat_phase |= REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 		return;

 	case OP_RANGE:
 		insn->bb = NULL;
 		repeat_phase |= REPEAT_CSE;
 		kill_use(&insn->src1);
 		kill_use(&insn->src2);
 		kill_use(&insn->src3);
 		return;
 	case OP_BR:
 		insn->bb = NULL;
 		repeat_phase |= REPEAT_CSE;
 		if (insn->cond)
 			kill_use(&insn->cond);
 		return;
 	}
 }

 /*
  * Kill trivially dead instructions
  */
 static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
 {
 	struct pseudo_user *pu;
 	FOR_EACH_PTR(insn->target->users, pu) {
 		if (*pu->userp != VOID)
 			return 0;
 	} END_FOR_EACH_PTR(pu);

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

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

 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 {
 	convert_instruction_target(insn, pseudo);
 	insn->bb = NULL;
 	return REPEAT_CSE;
 }

 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 logical '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_CAST && 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 int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long value)
 {
 	unsigned int size = operand_size(insn, pseudo);

 	if (value >= size) {
 		warning(insn->pos, "right shift by bigger than source value");
 		return replace_with_pseudo(insn, value_pseudo(0));
 	}
 	if (!value)
 		return replace_with_pseudo(insn, pseudo);
 	return 0;
 }

 static int simplify_constant_rightside(struct instruction *insn)
 {
 	long long value = insn->src2->value;

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

 	case OP_MULU: case OP_MULS:
 	case OP_AND_BOOL:
 		if (value == 1)
 			return replace_with_pseudo(insn, insn->src1);
 	/* Fall through */
 	case OP_AND:
 		if (!value)
 			return replace_with_pseudo(insn, insn->src2);
 		return 0;
 	}
 	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_MULU: case OP_MULS:
 		if (!value)
 			return replace_with_pseudo(insn, insn->src1);
 		return 0;
 	}
 	return 0;
 }

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

 	mask = 1ULL << (insn->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_MULU:
 		res = ul * ur;
 		break;
 	case OP_MULS:
 		res = left * right;
 		break;
 	case OP_DIVU:
 		if (!ur)
 			return 0;
 		res = ul / ur;
 		break;
 	case OP_DIVS:
 		if (!right)
 			return 0;
 		res = left / right;
 		break;
 	case OP_MODU:
 		if (!ur)
 			return 0;
 		res = ul % ur;
 		break;
 	case OP_MODS:
 		if (!right)
 			return 0;
 		res = left % right;
 		break;
 	case OP_SHL:
 		res = left << right;
 		break;
 	case OP_LSR:
 		res = ul >> ur;
 		break;
 	case OP_ASR:
 		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;
 	case OP_AND_BOOL:
 		res = left && right;
 		break;
 	case OP_OR_BOOL:
 		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 0;
 	}
 	res &= bits;

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

 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);
 	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 simplify_commutative_binop(struct instruction *insn)
 {
 	if (!canonical_order(insn->src1, insn->src2)) {
 		switch_pseudo(insn, &insn->src1, insn, &insn->src2);
 		return REPEAT_CSE;
 	}
 	return 0;
 }

 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 (ptr_list_size((struct ptr_list *)def->target->users) != 1)
 		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;
 	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);
 	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) {
 		if (new == VOID)
 			return 0;
 		new = VOID;
 		warning(insn->pos, "crazy programmer");
 	}
 	insn->offset += off->value;
 	use_pseudo(insn, new, &insn->src);
 	remove_usage(addr, &insn->src);
 	return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 }

 /*
  * 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 long long get_cast_value(long long val, int old_size, int new_size, int sign)
 {
 	long long mask;

 	if (sign && new_size > old_size) {
 		mask = 1 << (old_size-1);
 		if (val & mask)
 			val |= ~(mask | (mask-1));
 	}
 	mask = 1 << (new_size-1);
 	return val & (mask | (mask-1));
 }

 static int simplify_cast(struct instruction *insn)
 {
 	struct symbol *orig_type;
 	int orig_size, size;
 	pseudo_t src;

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

 	orig_type = insn->orig_type;
 	if (!orig_type)
 		return 0;
 	orig_size = orig_type->bit_size;
 	size = insn->size;
 	src = insn->src;

 	/* A cast of a constant? */
 	if (constant(src)) {
 		int sign = orig_type->ctype.modifiers & MOD_SIGNED;
 		long long val = get_cast_value(src->value, orig_size, size, sign);
 		src = value_pseudo(val);
 		goto simplify;
 	}

 	/* A cast of a "and" might be a no-op.. */
 	if (src->type == PSEUDO_REG) {
 		struct instruction *def = src->def;
 		if (def->opcode == OP_AND && def->size >= size) {
 			pseudo_t val = def->src2;
 			if (val->type == PSEUDO_VAL) {
 				unsigned long long value = val->value;
 				if (!(value >> (size-1)))
 					goto simplify;
 			}
 		}
 	}

 	if (size == orig_size) {
 		int op = (orig_type->ctype.modifiers & MOD_SIGNED) ? OP_SCAST : OP_CAST;
 		if (insn->opcode == op)
 			goto simplify;
 	}

 	return 0;

 simplify:
 	return replace_with_pseudo(insn, src);
 }

 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;
 		}
 	}
 	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, pseudo_t cond, struct instruction *def, pseudo_t *pp)
 {
 	use_pseudo(br, *pp, &br->cond);
 	remove_usage(cond, &br->cond);
 	if (def->opcode == OP_SET_EQ) {
 		struct basic_block *true = br->bb_true;
 		struct basic_block *false = br->bb_false;
 		br->bb_false = true;
 		br->bb_true = false;
 	}
 	return REPEAT_CSE;
 }

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

 	if (!cond)
 		return 0;

 	/* 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;
 		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, cond, def, &def->src2);
 			if (constant(def->src2) && !def->src2->value)
 				return simplify_cond_branch(insn, cond, 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 *true = insn->bb_true;
 					struct basic_block *false = insn->bb_false;
 					insn->bb_false = true;
 					insn->bb_true = false;
 				}
 				use_pseudo(insn, def->src1, &insn->cond);
 				remove_usage(cond, &insn->cond);
 				return REPEAT_CSE;
 			}
 		}
 		if (def->opcode == OP_CAST || def->opcode == OP_SCAST) {
 			int orig_size = def->orig_type ? def->orig_type->bit_size : 0;
 			if (def->size > orig_size) {
 				use_pseudo(insn, def->src, &insn->cond);
 				remove_usage(cond, &insn->cond);
 				return REPEAT_CSE;
 			}
 		}
 	}
 	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_MULS:
 	case OP_AND: case OP_OR: case OP_XOR:
 	case OP_AND_BOOL: case OP_OR_BOOL:
 		if (simplify_binop(insn))
 			return REPEAT_CSE;
 		if (simplify_commutative_binop(insn))
 			return REPEAT_CSE;
 		return simplify_associative_binop(insn);

 	case OP_MULU:
 	case OP_SET_EQ: case OP_SET_NE:
 		if (simplify_binop(insn))
 			return REPEAT_CSE;
 		return simplify_commutative_binop(insn);

 	case OP_SUB:
 	case OP_DIVU: case OP_DIVS:
 	case OP_MODU: case OP_MODS:
 	case OP_SHL:
 	case OP_LSR: case OP_ASR:
 	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:
 		return simplify_binop(insn);

 	case OP_NOT: case OP_NEG:
 		return simplify_unop(insn);
 	case OP_LOAD: case OP_STORE:
 		return simplify_memop(insn);
 	case OP_SYMADDR:
 		if (dead_insn(insn, NULL, NULL, NULL))
 			return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 		return replace_with_pseudo(insn, insn->symbol);
 	case OP_CAST:
 	case OP_SCAST:
 	case OP_FPCAST:
 	case OP_PTRCAST:
 		return simplify_cast(insn);
 	case OP_PHI:
 		if (dead_insn(insn, NULL, NULL, NULL)) {
 			clear_phi(insn);
 			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_BR:
 		return simplify_branch(insn);
 	case OP_SWITCH:
 		return simplify_switch(insn);
 	case OP_RANGE:
 		return simplify_range(insn);
 	}
 	return 0;
 }
	/*
	* Simplify - do instruction simplification before CSE
	*
	* Copyright (C) 2004 Linus Torvalds
	*/

	#include <assert.h>

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

	/* 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);
	}

	static void clear_phi(struct instruction *insn)
	{
	pseudo_t phi;

	insn->bb = NULL;
	FOR_EACH_PTR(insn->phi_list, phi) {
	*THIS_ADDRESS(phi) = VOID;
	} END_FOR_EACH_PTR(phi);
	}

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

	bb = insn->bb;
	if (linearize_ptr_list((struct ptr_list )insn->phi_list, (void *)array, 3) != 2)
	return 0;
	if (linearize_ptr_list((struct ptr_list )bb->parents, (void *)parents, 3) != 2)
	return 0;
	p1 = array[0]->def->src1;
	bb1 = array[0]->def->bb;
	p2 = array[1]->def->src1;
	bb2 = array[1]->def->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_BR)
	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);
	clear_phi(insn);
	return REPEAT_CSE;
	}

	static int clean_up_phi(struct instruction *insn)
	{
	pseudo_t phi;
	struct instruction *last;
	int same;

	last = NULL;
	same = 1;
	FOR_EACH_PTR(insn->phi_list, phi) {
	struct instruction *def;
	if (phi == VOID)
	continue;
	def = phi->def;
	if (def->src1 == VOID \|\| !def->bb)
	continue;
	if (last) {
	if (last->src1 != def->src1)
	same = 0;
	continue;
	}
	last = def;
	} END_FOR_EACH_PTR(phi);

	if (same) {
	pseudo_t pseudo = last ? last->src1 : VOID;
	convert_instruction_target(insn, pseudo);
	clear_phi(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) {
	DELETE_CURRENT_PTR(pu);
	if (!--count)
	goto out;
	}
	} END_FOR_EACH_PTR(pu);
	assert(count <= 0);
	out:
	pack_ptr_list((struct ptr_list **)list);
	return count;
	}

	static inline void remove_usage(pseudo_t p, pseudo_t *usep)
	{
	if (has_use_list(p)) {
	delete_pseudo_user_list_entry(&p->users, usep, 1);
	if (!p->users)
	kill_instruction(p->def);
	}
	}

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

	void kill_instruction(struct instruction *insn)
	{
	if (!insn \|\| !insn->bb)
	return;

	switch (insn->opcode) {
	case OP_BINARY ... OP_BINCMP_END:
	insn->bb = NULL;
	kill_use(&insn->src1);
	kill_use(&insn->src2);
	repeat_phase \|= REPEAT_CSE;
	return;

	case OP_NOT: case OP_NEG:
	insn->bb = NULL;
	kill_use(&insn->src1);
	repeat_phase \|= REPEAT_CSE;
	return;

	case OP_PHI:
	insn->bb = NULL;
	repeat_phase \|= REPEAT_CSE;
	return;

	case OP_SYMADDR:
	insn->bb = NULL;
	repeat_phase \|= REPEAT_CSE \| REPEAT_SYMBOL_CLEANUP;
	return;

	case OP_RANGE:
	insn->bb = NULL;
	repeat_phase \|= REPEAT_CSE;
	kill_use(&insn->src1);
	kill_use(&insn->src2);
	kill_use(&insn->src3);
	return;
	case OP_BR:
	insn->bb = NULL;
	repeat_phase \|= REPEAT_CSE;
	if (insn->cond)
	kill_use(&insn->cond);
	return;
	}
	}

	/*
	* Kill trivially dead instructions
	*/
	static int dead_insn(struct instruction insn, pseudo_t src1, pseudo_t src2, pseudo_t src3)
	{
	struct pseudo_user *pu;
	FOR_EACH_PTR(insn->target->users, pu) {
	if (*pu->userp != VOID)
	return 0;
	} END_FOR_EACH_PTR(pu);

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

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

	static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
	{
	convert_instruction_target(insn, pseudo);
	insn->bb = NULL;
	return REPEAT_CSE;
	}

	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 logical '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_CAST && 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 int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long value)
	{
	unsigned int size = operand_size(insn, pseudo);

	if (value >= size) {
	warning(insn->pos, "right shift by bigger than source value");
	return replace_with_pseudo(insn, value_pseudo(0));
	}
	if (!value)
	return replace_with_pseudo(insn, pseudo);
	return 0;
	}

	static int simplify_constant_rightside(struct instruction *insn)
	{
	long long value = insn->src2->value;

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

	case OP_MULU: case OP_MULS:
	case OP_AND_BOOL:
	if (value == 1)
	return replace_with_pseudo(insn, insn->src1);
	/* Fall through */
	case OP_AND:
	if (!value)
	return replace_with_pseudo(insn, insn->src2);
	return 0;
	}
	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_MULU: case OP_MULS:
	if (!value)
	return replace_with_pseudo(insn, insn->src1);
	return 0;
	}
	return 0;
	}

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

	mask = 1ULL << (insn->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_MULU:
	res = ul * ur;
	break;
	case OP_MULS:
	res = left * right;
	break;
	case OP_DIVU:
	if (!ur)
	return 0;
	res = ul / ur;
	break;
	case OP_DIVS:
	if (!right)
	return 0;
	res = left / right;
	break;
	case OP_MODU:
	if (!ur)
	return 0;
	res = ul % ur;
	break;
	case OP_MODS:
	if (!right)
	return 0;
	res = left % right;
	break;
	case OP_SHL:
	res = left << right;
	break;
	case OP_LSR:
	res = ul >> ur;
	break;
	case OP_ASR:
	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;
	case OP_AND_BOOL:
	res = left && right;
	break;
	case OP_OR_BOOL:
	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 0;
	}
	res &= bits;

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

	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);
	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 simplify_commutative_binop(struct instruction *insn)
	{
	if (!canonical_order(insn->src1, insn->src2)) {
	switch_pseudo(insn, &insn->src1, insn, &insn->src2);
	return REPEAT_CSE;
	}
	return 0;
	}

	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 (ptr_list_size((struct ptr_list *)def->target->users) != 1)
	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;
	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);
	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) {
	if (new == VOID)
	return 0;
	new = VOID;
	warning(insn->pos, "crazy programmer");
	}
	insn->offset += off->value;
	use_pseudo(insn, new, &insn->src);
	remove_usage(addr, &insn->src);
	return REPEAT_CSE \| REPEAT_SYMBOL_CLEANUP;
	}

	/*
	* 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 long long get_cast_value(long long val, int old_size, int new_size, int sign)
	{
	long long mask;

	if (sign && new_size > old_size) {
	mask = 1 << (old_size-1);
	if (val & mask)
	val \|= ~(mask \| (mask-1));
	}
	mask = 1 << (new_size-1);
	return val & (mask \| (mask-1));
	}

	static int simplify_cast(struct instruction *insn)
	{
	struct symbol *orig_type;
	int orig_size, size;
	pseudo_t src;

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

	orig_type = insn->orig_type;
	if (!orig_type)
	return 0;
	orig_size = orig_type->bit_size;
	size = insn->size;
	src = insn->src;

	/* A cast of a constant? */
	if (constant(src)) {
	int sign = orig_type->ctype.modifiers & MOD_SIGNED;
	long long val = get_cast_value(src->value, orig_size, size, sign);
	src = value_pseudo(val);
	goto simplify;
	}

	/* A cast of a "and" might be a no-op.. */
	if (src->type == PSEUDO_REG) {
	struct instruction *def = src->def;
	if (def->opcode == OP_AND && def->size >= size) {
	pseudo_t val = def->src2;
	if (val->type == PSEUDO_VAL) {
	unsigned long long value = val->value;
	if (!(value >> (size-1)))
	goto simplify;
	}
	}
	}

	if (size == orig_size) {
	int op = (orig_type->ctype.modifiers & MOD_SIGNED) ? OP_SCAST : OP_CAST;
	if (insn->opcode == op)
	goto simplify;
	}

	return 0;

	simplify:
	return replace_with_pseudo(insn, src);
	}

	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;
	}
	}
	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, pseudo_t cond, struct instruction def, pseudo_t *pp)
	{
	use_pseudo(br, *pp, &br->cond);
	remove_usage(cond, &br->cond);
	if (def->opcode == OP_SET_EQ) {
	struct basic_block *true = br->bb_true;
	struct basic_block *false = br->bb_false;
	br->bb_false = true;
	br->bb_true = false;
	}
	return REPEAT_CSE;
	}

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

	if (!cond)
	return 0;

	/* 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;
	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, cond, def, &def->src2);
	if (constant(def->src2) && !def->src2->value)
	return simplify_cond_branch(insn, cond, 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 *true = insn->bb_true;
	struct basic_block *false = insn->bb_false;
	insn->bb_false = true;
	insn->bb_true = false;
	}
	use_pseudo(insn, def->src1, &insn->cond);
	remove_usage(cond, &insn->cond);
	return REPEAT_CSE;
	}
	}
	if (def->opcode == OP_CAST \|\| def->opcode == OP_SCAST) {
	int orig_size = def->orig_type ? def->orig_type->bit_size : 0;
	if (def->size > orig_size) {
	use_pseudo(insn, def->src, &insn->cond);
	remove_usage(cond, &insn->cond);
	return REPEAT_CSE;
	}
	}
	}
	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_MULS:
	case OP_AND: case OP_OR: case OP_XOR:
	case OP_AND_BOOL: case OP_OR_BOOL:
	if (simplify_binop(insn))
	return REPEAT_CSE;
	if (simplify_commutative_binop(insn))
	return REPEAT_CSE;
	return simplify_associative_binop(insn);

	case OP_MULU:
	case OP_SET_EQ: case OP_SET_NE:
	if (simplify_binop(insn))
	return REPEAT_CSE;
	return simplify_commutative_binop(insn);

	case OP_SUB:
	case OP_DIVU: case OP_DIVS:
	case OP_MODU: case OP_MODS:
	case OP_SHL:
	case OP_LSR: case OP_ASR:
	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:
	return simplify_binop(insn);

	case OP_NOT: case OP_NEG:
	return simplify_unop(insn);
	case OP_LOAD: case OP_STORE:
	return simplify_memop(insn);
	case OP_SYMADDR:
	if (dead_insn(insn, NULL, NULL, NULL))
	return REPEAT_CSE \| REPEAT_SYMBOL_CLEANUP;
	return replace_with_pseudo(insn, insn->symbol);
	case OP_CAST:
	case OP_SCAST:
	case OP_FPCAST:
	case OP_PTRCAST:
	return simplify_cast(insn);
	case OP_PHI:
	if (dead_insn(insn, NULL, NULL, NULL)) {
	clear_phi(insn);
	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_BR:
	return simplify_branch(insn);
	case OP_SWITCH:
	return simplify_switch(insn);
	case OP_RANGE:
	return simplify_range(insn);
	}
	return 0;
	}