Merge branch 'bit-trans' into next

* factorize (x OP1 z) OP2 (y OP1 z) into (x OP2 y) OP1 z
* factorize SHIFT(x, s) OP SHIFT(y, s) into SHIFT((x OP y), s)
* factorize SEL(x, OP(y,z), y) into OP(SEL(x, z, 0), y)
* convert SEL(x & BIT1, BIT2, 0) into SHIFT(x & BIT1, S)

11 files changed, 504 insertions, 17 deletions

diff --git a/bits.h b/bits.h
index c0dc952e..9908190d 100644
--- a/bits.h
+++ b/bits.h
@@ -58,4 +58,16 @@ static inline long long bits_extend(long long val, unsigned size, int is_signed)
 	return val;
 }
 
+static inline int is_power_of_2(long long val)
+{
+	return val && !(val & (val - 1));
+}
+
+///
+// log base 2 of an exact power-of-2
+static inline int log2_exact(unsigned long long val)
+{
+	return 8 * sizeof(val) - __builtin_clzl(val) - 1;
+}
+
 #endif
diff --git a/simplify.c b/simplify.c
index 5238d33f..334839a2 100644
--- a/simplify.c
+++ b/simplify.c
@@ -46,12 +46,22 @@
 #include "linearize.h"
 #include "flow.h"
 #include "symbol.h"
+#include "flowgraph.h"
 
 ///
 // Utilities
 // ^^^^^^^^^
 
 ///
+// check if a pseudo is a power of 2
+static inline bool is_pow2(pseudo_t src)
+{
+	if (src->type != PSEUDO_VAL)
+		return false;
+	return is_power_of_2(src->value);
+}
+
+///
 // find the trivial parent for a phi-source
 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
 {
@@ -497,6 +507,23 @@ static inline int replace_binop_value(struct instruction *insn, int op, long lon
 }
 
 ///
+// replace binop's opcode and values
+// @insn: the instruction to be replaced
+// @op: the instruction's new opcode
+// @return: REPEAT_CSE
+static inline int replace_binop(struct instruction *insn, int op, pseudo_t *pa, pseudo_t a, pseudo_t *pb, pseudo_t b)
+{
+	pseudo_t olda = *pa;
+	pseudo_t oldb = *pb;
+	insn->opcode = op;
+	use_pseudo(insn, a, pa);
+	use_pseudo(insn, b, pb);
+	remove_usage(olda, pa);
+	remove_usage(oldb, pb);
+	return REPEAT_CSE;
+}
+
+///
 // replace the opcode of an instruction
 // @return: REPEAT_CSE
 static inline int replace_opcode(struct instruction *insn, int op)
@@ -505,6 +532,47 @@ static inline int replace_opcode(struct instruction *insn, int op)
 	return REPEAT_CSE;
 }
 
+///
+// create an instruction pair OUT(IN(a, b), c)
+static int replace_insn_pair(struct instruction *out, int op_out, struct instruction *in, int op_in, pseudo_t a, pseudo_t b, pseudo_t c)
+{
+	pseudo_t old_a = in->src1;
+	pseudo_t old_b = in->src2;
+	pseudo_t old_1 = out->src1;
+	pseudo_t old_2 = out->src2;
+
+	use_pseudo(in, a, &in->src1);
+	use_pseudo(in, b, &in->src2);
+	use_pseudo(out, in->target, &out->src1);
+	use_pseudo(out, c, &out->src2);
+
+	remove_usage(old_a, &in->src1);
+	remove_usage(old_b, &in->src2);
+	remove_usage(old_1, &out->src1);
+	remove_usage(old_2, &out->src2);
+
+	out->opcode = op_out;
+	in->opcode = op_in;
+	return REPEAT_CSE;
+}
+
+///
+// create an instruction pair OUT(IN(a, b), c) with swapped opcodes
+static inline int swap_insn(struct instruction *out, struct instruction *in, pseudo_t a, pseudo_t b, pseudo_t c)
+{
+	return replace_insn_pair(out, in->opcode, in, out->opcode, a, b, c);
+}
+
+///
+// create an instruction pair OUT(SELECT(a, b, c), d)
+static int swap_select(struct instruction *out, struct instruction *in, pseudo_t a, pseudo_t b, pseudo_t c, pseudo_t d)
+{
+	use_pseudo(in, c, &in->src3);
+	swap_insn(out, in, a, b, d);
+	kill_use(&out->src3);
+	return REPEAT_CSE;
+}
+
 static inline int def_opcode(pseudo_t p)
 {
 	if (p->type != PSEUDO_REG)
@@ -1508,6 +1576,42 @@ static inline int simple_pseudo(pseudo_t pseudo)
 	return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
 }
 
+///
+// test if, in the given BB, the ordering of 2 instructions
+static bool insn_before(struct basic_block *bb, struct instruction *x, struct instruction *y)
+{
+	struct instruction *insn;
+
+	FOR_EACH_PTR(bb->insns, insn) {
+		if (insn == x)
+			return true;
+		if (insn == y)
+			return false;
+	} END_FOR_EACH_PTR(insn);
+	return false;
+}
+
+///
+// check if it safe for a pseudo to be used by an instruction
+static inline bool can_move_to(pseudo_t src, struct instruction *dst)
+{
+	struct basic_block *bbs, *bbd;
+	struct instruction *def;
+
+	if (!one_use(dst->target))
+		return false;
+	if (src->type != PSEUDO_REG)
+		return true;
+
+	def = src->def;
+	bbs = def->bb;
+	bbd = dst->bb;
+	if (bbs == bbd)
+		return insn_before(bbs, def, dst);
+	else
+		return domtree_dominates(bbs, bbd);
+}
+
 static int simplify_associative_binop(struct instruction *insn)
 {
 	struct instruction *def;
@@ -1535,37 +1639,51 @@ static int simplify_associative_binop(struct instruction *insn)
 	return REPEAT_CSE;
 }
 
-static int simplify_add(struct instruction *insn)
+static int simplify_add_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
 {
-	pseudo_t src1 = insn->src1;
-	pseudo_t src2 = insn->src2;
+	struct instruction *defr = NULL;
 	struct instruction *def;
+	pseudo_t src1 = *p1;
+	pseudo_t src2 = *p2;
 
 	switch (DEF_OPCODE(def, src1)) {
+	case OP_MUL:
+		if (DEF_OPCODE(defr, *p2) == OP_MUL) {
+			if (defr->src2 == def->src2 && can_move_to(def->src2, defr)) {
+				// ((x * z) + (y * z)) into ((x + y) * z)
+				swap_insn(insn, defr, def->src1, defr->src1, def->src2);
+				return REPEAT_CSE;
+			}
+			if (defr->src1 == def->src1 && can_move_to(def->src1, defr)) {
+				// ((z * x) + (z * y)) into ((x + y) * z)
+				swap_insn(insn, defr, def->src2, defr->src2, def->src1);
+				return REPEAT_CSE;
+			}
+			if (defr->src1 == def->src2 && can_move_to(def->src1, defr)) {
+				// ((x * z) + (z * y)) into ((x + y) * z)
+				swap_insn(insn, defr, def->src1, defr->src2, def->src2);
+				return REPEAT_CSE;
+			}
+		}
+		break;
+
 	case OP_NEG:				// (-x + y) --> (y - x)
-		switch_pseudo(insn, &insn->src1, insn, &insn->src2);
-		insn->opcode = OP_SUB;
-		return replace_pseudo(insn, &insn->src2, def->src);
+		return replace_binop(insn, OP_SUB, &insn->src1, src2, &insn->src2, def->src);
 
 	case OP_SUB:
 		if (def->src2 == src2)		// (x - y) + y --> x
 			return replace_with_pseudo(insn, def->src1);
 		break;
 	}
-
-	switch (DEF_OPCODE(def, src2)) {
-	case OP_NEG:				// (x + -y) --> (x - y)
-		insn->opcode = OP_SUB;
-		return replace_pseudo(insn, &insn->src2, def->src);
-	case OP_SUB:
-		if (src1 == def->src2)		// x + (y - x) --> y
-			return replace_with_pseudo(insn, def->src1);
-		break;
-	}
-
 	return 0;
 }
 
+static int simplify_add(struct instruction *insn)
+{
+	return simplify_add_one_side(insn, &insn->src1, &insn->src2) ||
+	       simplify_add_one_side(insn, &insn->src2, &insn->src1);
+}
+
 static int simplify_sub(struct instruction *insn)
 {
 	pseudo_t src1 = insn->src1;
@@ -1636,6 +1754,34 @@ static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_
 				return replace_with_value(insn, 0);
 		}
 		break;
+	case OP_OR:
+		if (DEF_OPCODE(defr, *p2) == OP_OR) {
+			if (defr->src2 == def->src2 && can_move_to(def->src2, defr)) {
+				// ((x | z) & (y | z)) into ((x & y) | z)
+				swap_insn(insn, defr, def->src1, defr->src1, def->src2);
+				return REPEAT_CSE;
+			}
+			if (defr->src1 == def->src1 && can_move_to(def->src1, defr)) {
+				// ((z | x) & (z | y)) into ((x & y) | z)
+				swap_insn(insn, defr, def->src2, defr->src2, def->src1);
+				return REPEAT_CSE;
+			}
+			if (defr->src1 == def->src2 && can_move_to(def->src1, defr)) {
+				// ((x | z) & (z | y)) into ((x & y) | z)
+				swap_insn(insn, defr, def->src1, defr->src2, def->src2);
+				return REPEAT_CSE;
+			}
+		}
+		break;
+	case OP_SHL: case OP_LSR: case OP_ASR:
+		if (DEF_OPCODE(defr, *p2) == def->opcode && defr->src2 == def->src2) {
+			if (can_move_to(def->src1, defr)) {
+				// SHIFT(x, s) & SHIFT(y, s) --> SHIFT((x & y), s)
+				swap_insn(insn, defr, def->src1, defr->src1, def->src2);
+				return REPEAT_CSE;
+			}
+		}
+		break;
 	}
 	return 0;
 }
@@ -1652,6 +1798,25 @@ static int simplify_ior_one_side(struct instruction *insn, pseudo_t *p1, pseudo_
 	pseudo_t src1 = *p1;
 
 	switch (DEF_OPCODE(def, src1)) {
+	case OP_AND:
+		if (DEF_OPCODE(defr, *p2) == OP_AND) {
+			if (defr->src2 == def->src2 && can_move_to(def->src2, defr)) {
+				// ((x & z) | (y & z)) into ((x | y) & z)
+				swap_insn(insn, defr, def->src1, defr->src1, def->src2);
+				return REPEAT_CSE;
+			}
+			if (defr->src1 == def->src1 && can_move_to(def->src1, defr)) {
+				// ((z & x) | (z & y)) into ((x | y) & z)
+				swap_insn(insn, defr, def->src2, defr->src2, def->src1);
+				return REPEAT_CSE;
+			}
+			if (defr->src1 == def->src2 && can_move_to(def->src1, defr)) {
+				// ((x & z) | (z & y)) into ((x | y) & z)
+				swap_insn(insn, defr, def->src1, defr->src2, def->src2);
+				return REPEAT_CSE;
+			}
+		}
+		break;
 	case OP_NOT:
 		if (def->src == *p2)
 			return replace_with_value(insn, bits_mask(insn->size));
@@ -1662,6 +1827,15 @@ static int simplify_ior_one_side(struct instruction *insn, pseudo_t *p1, pseudo_
 				return replace_with_value(insn, 1);
 		}
 		break;
+	case OP_SHL: case OP_LSR: case OP_ASR:
+		if (DEF_OPCODE(defr, *p2) == def->opcode && defr->src2 == def->src2) {
+			if (can_move_to(def->src1, defr)) {
+				// SHIFT(x, s) | SHIFT(y, s) --> SHIFT((x | y), s)
+				swap_insn(insn, defr, def->src1, defr->src1, def->src2);
+				return REPEAT_CSE;
+			}
+		}
+		break;
 	}
 	return 0;
 }
@@ -1678,6 +1852,25 @@ static int simplify_xor_one_side(struct instruction *insn, pseudo_t *p1, pseudo_
 	pseudo_t src1 = *p1;
 
 	switch (DEF_OPCODE(def, src1)) {
+	case OP_AND:
+		if (DEF_OPCODE(defr, *p2) == OP_AND) {
+			if (defr->src2 == def->src2 && can_move_to(def->src2, defr)) {
+				// ((x & z) ^ (y & z)) into ((x ^ y) & z)
+				swap_insn(insn, defr, def->src1, defr->src1, def->src2);
+				return REPEAT_CSE;
+			}
+			if (defr->src1 == def->src1 && can_move_to(def->src1, defr)) {
+				// ((z & x) ^ (z & y)) into ((x ^ y) & z)
+				swap_insn(insn, defr, def->src2, defr->src2, def->src1);
+				return REPEAT_CSE;
+			}
+			if (defr->src1 == def->src2 && can_move_to(def->src1, defr)) {
+				// ((x & z) ^ (z & y)) into ((x ^ y) & z)
+				swap_insn(insn, defr, def->src1, defr->src2, def->src2);
+				return REPEAT_CSE;
+			}
+		}
+		break;
 	case OP_NOT:
 		if (def->src == *p2)
 			return replace_with_value(insn, bits_mask(insn->size));
@@ -1688,6 +1881,15 @@ static int simplify_xor_one_side(struct instruction *insn, pseudo_t *p1, pseudo_
 				return replace_with_value(insn, 1);
 		}
 		break;
+	case OP_SHL: case OP_LSR: case OP_ASR:
+		if (DEF_OPCODE(defr, *p2) == def->opcode && defr->src2 == def->src2) {
+			if (can_move_to(def->src1, defr)) {
+				// SHIFT(x, s) ^ SHIFT(y, s) --> SHIFT((x ^ y), s)
+				swap_insn(insn, defr, def->src1, defr->src1, def->src2);
+				return REPEAT_CSE;
+			}
+		}
+		break;
 	}
 	return 0;
 }
@@ -2069,6 +2271,51 @@ static int simplify_select(struct instruction *insn)
 			// both values must be non-zero
 			return replace_with_pseudo(insn, src1);
 		}
+	case OP_AND:
+		if (is_pow2(def->src2) && is_pow2(src1) && is_zero(src2) && insn->size == def->size && one_use(cond)) {
+			unsigned s1 = log2_exact(def->src2->value);
+			unsigned s2 = log2_exact(insn->src2->value);
+			unsigned shift;
+
+			if (s1 == s2)
+				return replace_with_pseudo(insn, cond);
+
+			// SEL(x & A, B, 0) --> SHIFT(x & A, S)
+			insn->opcode = (s1 < s2) ? OP_SHL : OP_LSR;
+			shift = (s1 < s2) ? (s2 - s1) : (s1 - s2);
+			insn->src2 = value_pseudo(shift);
+			return REPEAT_CSE;
+		}
+		break;
+	}
+
+	switch (DEF_OPCODE(def, src1)) {
+	case OP_ADD: case OP_OR: case OP_XOR:
+		if ((def->src1 == src2) && can_move_to(cond, def)) {
+			// SEL(x, OP(y,z), y) --> OP(SEL(x, z, 0), y)
+			swap_select(insn, def, cond, def->src2, value_pseudo(0), src2);
+			return REPEAT_CSE;
+		}
+		if ((def->src2 == src2) && can_move_to(cond, def)) {
+			// SEL(x, OP(z,y), y) --> OP(SEL(x, z, 0), y)
+			swap_select(insn, def, cond, def->src1, value_pseudo(0), src2);
+			return REPEAT_CSE;
+		}
+		break;
+	}
+
+	switch (DEF_OPCODE(def, src2)) {
+	case OP_ADD: case OP_OR: case OP_XOR:
+		if ((def->src1 == src1) && can_move_to(cond, def)) {
+			// SEL(x, y, OP(y,z)) --> OP(SEL(x, 0, z), y)
+			swap_select(insn, def, cond, value_pseudo(0), def->src2, src1);
+			return REPEAT_CSE;
+		}
+		if ((def->src2 == src1) && can_move_to(cond, def)) {
+			// SEL(x, y, OP(z,y)) --> OP(SEL(x, 0, z), y)
+			swap_select(insn, def, cond, value_pseudo(0), def->src1, src1);
+			return REPEAT_CSE;
+		}
 		break;
 	}
 	return 0;
diff --git a/validation/optim/fact-add-mul.c b/validation/optim/fact-add-mul.c
new file mode 100644
index 00000000..9da6d71c
--- /dev/null
+++ b/validation/optim/fact-add-mul.c
@@ -0,0 +1,27 @@
+int fr_abx(int a, int b, int x) { return ((a * x) + (b * x)) == ((a + b) * x); }
+int fl_abx(int a, int b, int x) { return ((x * a) + (x * b)) == ((a + b) * x); }
+int fm_abx(int a, int b, int x) { return ((a * x) + (x * b)) == ((a + b) * x); }
+int fn_abx(int a, int b, int x) { return ((x * a) + (b * x)) == ((a + b) * x); }
+
+int fr_bax(int b, int a, int x) { return ((a * x) + (b * x)) == ((b + a) * x); }
+int fl_bax(int b, int a, int x) { return ((x * a) + (x * b)) == ((b + a) * x); }
+int fm_bax(int b, int a, int x) { return ((a * x) + (x * b)) == ((b + a) * x); }
+int fn_bax(int b, int a, int x) { return ((x * a) + (b * x)) == ((b + a) * x); }
+
+int fr_axb(int a, int x, int b) { return ((a * x) + (b * x)) == ((a + b) * x); }
+int fl_axb(int a, int x, int b) { return ((x * a) + (x * b)) == ((a + b) * x); }
+int fm_axb(int a, int x, int b) { return ((a * x) + (x * b)) == ((a + b) * x); }
+int fn_axb(int a, int x, int b) { return ((x * a) + (b * x)) == ((a + b) * x); }
+
+int fr_bxa(int b, int x, int a) { return ((b * x) + (a * x)) == ((b + a) * x); }
+int fl_bxa(int b, int x, int a) { return ((x * b) + (x * a)) == ((b + a) * x); }
+int fm_bxa(int b, int x, int a) { return ((b * x) + (x * a)) == ((b + a) * x); }
+int fn_bxa(int b, int x, int a) { return ((x * b) + (a * x)) == ((b + a) * x); }
+
+/*
+ * check-name: fact-add-mul
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/fact-and-ior.c b/validation/optim/fact-and-ior.c
new file mode 100644
index 00000000..96466616
--- /dev/null
+++ b/validation/optim/fact-and-ior.c
@@ -0,0 +1,27 @@
+int fr_abx(int a, int b, int x) { return ((a | x) & (b | x)) == ((a & b) | x); }
+int fl_abx(int a, int b, int x) { return ((x | a) & (x | b)) == ((a & b) | x); }
+int fm_abx(int a, int b, int x) { return ((a | x) & (x | b)) == ((a & b) | x); }
+int fn_abx(int a, int b, int x) { return ((x | a) & (b | x)) == ((a & b) | x); }
+
+int fr_bax(int b, int a, int x) { return ((a | x) & (b | x)) == ((b & a) | x); }
+int fl_bax(int b, int a, int x) { return ((x | a) & (x | b)) == ((b & a) | x); }
+int fm_bax(int b, int a, int x) { return ((a | x) & (x | b)) == ((b & a) | x); }
+int fn_bax(int b, int a, int x) { return ((x | a) & (b | x)) == ((b & a) | x); }
+
+int fr_axb(int a, int x, int b) { return ((a | x) & (b | x)) == ((a & b) | x); }
+int fl_axb(int a, int x, int b) { return ((x | a) & (x | b)) == ((a & b) | x); }
+int fm_axb(int a, int x, int b) { return ((a | x) & (x | b)) == ((a & b) | x); }
+int fn_axb(int a, int x, int b) { return ((x | a) & (b | x)) == ((a & b) | x); }
+
+int fr_bxa(int b, int x, int a) { return ((b | x) & (a | x)) == ((b & a) | x); }
+int fl_bxa(int b, int x, int a) { return ((x | b) & (x | a)) == ((b & a) | x); }
+int fm_bxa(int b, int x, int a) { return ((b | x) & (x | a)) == ((b & a) | x); }
+int fn_bxa(int b, int x, int a) { return ((x | b) & (a | x)) == ((b & a) | x); }
+
+/*
+ * check-name: fact-and-ior
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/fact-and-shift.c b/validation/optim/fact-and-shift.c
new file mode 100644
index 00000000..e9eb9cce
--- /dev/null
+++ b/validation/optim/fact-and-shift.c
@@ -0,0 +1,26 @@
+typedef unsigned int uint;
+typedef   signed int sint;
+
+
+uint fact_and_shl(uint a, uint b, uint s)
+{
+	return ((a << s) & (b << s)) == ((a & b) << s);
+}
+
+uint fact_and_lsr(uint a, uint b, uint s)
+{
+	return ((a >> s) & (b >> s)) == ((a & b) >> s);
+}
+
+sint fact_and_asr(sint a, sint b, sint s)
+{
+	return ((a >> s) & (b >> s)) == ((a & b) >> s);
+}
+
+/*
+ * check-name: fact-and-shift
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/fact-ior-and.c b/validation/optim/fact-ior-and.c
new file mode 100644
index 00000000..a6ad3c45
--- /dev/null
+++ b/validation/optim/fact-ior-and.c
@@ -0,0 +1,27 @@
+int fr_abx(int a, int b, int x) { return ((a & x) | (b & x)) == ((a | b) & x); }
+int fl_abx(int a, int b, int x) { return ((x & a) | (x & b)) == ((a | b) & x); }
+int fm_abx(int a, int b, int x) { return ((a & x) | (x & b)) == ((a | b) & x); }
+int fn_abx(int a, int b, int x) { return ((x & a) | (b & x)) == ((a | b) & x); }
+
+int fr_bax(int b, int a, int x) { return ((a & x) | (b & x)) == ((b | a) & x); }
+int fl_bax(int b, int a, int x) { return ((x & a) | (x & b)) == ((b | a) & x); }
+int fm_bax(int b, int a, int x) { return ((a & x) | (x & b)) == ((b | a) & x); }
+int fn_bax(int b, int a, int x) { return ((x & a) | (b & x)) == ((b | a) & x); }
+
+int fr_axb(int a, int x, int b) { return ((a & x) | (b & x)) == ((a | b) & x); }
+int fl_axb(int a, int x, int b) { return ((x & a) | (x & b)) == ((a | b) & x); }
+int fm_axb(int a, int x, int b) { return ((a & x) | (x & b)) == ((a | b) & x); }
+int fn_axb(int a, int x, int b) { return ((x & a) | (b & x)) == ((a | b) & x); }
+
+int fr_bxa(int b, int x, int a) { return ((b & x) | (a & x)) == ((b | a) & x); }
+int fl_bxa(int b, int x, int a) { return ((x & b) | (x & a)) == ((b | a) & x); }
+int fm_bxa(int b, int x, int a) { return ((b & x) | (x & a)) == ((b | a) & x); }
+int fn_bxa(int b, int x, int a) { return ((x & b) | (a & x)) == ((b | a) & x); }
+
+/*
+ * check-name: fact-ior-and
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/fact-ior-shift.c b/validation/optim/fact-ior-shift.c
new file mode 100644
index 00000000..5fa91eb5
--- /dev/null
+++ b/validation/optim/fact-ior-shift.c
@@ -0,0 +1,26 @@
+typedef unsigned int uint;
+typedef   signed int sint;
+
+
+uint fact_ior_shl(uint a, uint b, uint s)
+{
+	return ((a << s) | (b << s)) == ((a | b) << s);
+}
+
+uint fact_ior_lsr(uint a, uint b, uint s)
+{
+	return ((a >> s) | (b >> s)) == ((a | b) >> s);
+}
+
+sint fact_ior_asr(sint a, sint b, sint s)
+{
+	return ((a >> s) | (b >> s)) == ((a | b) >> s);
+}
+
+/*
+ * check-name: fact-ior-shift
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/fact-select01.c b/validation/optim/fact-select01.c
new file mode 100644
index 00000000..9232fc90
--- /dev/null
+++ b/validation/optim/fact-select01.c
@@ -0,0 +1,25 @@
+int add_yx_y(int p, int x, int y) { return (p ? (y+x) : y) == ((p ? x : 0) + y); }
+int add_xy_y(int p, int y, int x) { return (p ? (x+y) : y) == ((p ? x : 0) + y); }
+int add_xy_x(int p, int x, int y) { return (p ? (x+y) : x) == ((p ? y : 0) + x); }
+int add_yx_x(int p, int y, int x) { return (p ? (y+x) : x) == ((p ? y : 0) + x); }
+int add_y_yx(int p, int x, int y) { return (p ? y : (y+x)) == ((p ? 0 : x) + y); }
+
+int ior_yx_y(int p, int x, int y) { return (p ? (y|x) : y) == ((p ? x : 0) | y); }
+int ior_xy_y(int p, int y, int x) { return (p ? (x|y) : y) == ((p ? x : 0) | y); }
+int ior_xy_x(int p, int x, int y) { return (p ? (x|y) : x) == ((p ? y : 0) | x); }
+int ior_yx_x(int p, int y, int x) { return (p ? (y|x) : x) == ((p ? y : 0) | x); }
+int ior_y_yx(int p, int x, int y) { return (p ? y : (y|x)) == ((p ? 0 : x) | y); }
+
+int xor_yx_y(int p, int x, int y) { return (p ? (y^x) : y) == ((p ? x : 0) ^ y); }
+int xor_xy_y(int p, int y, int x) { return (p ? (x^y) : y) == ((p ? x : 0) ^ y); }
+int xor_xy_x(int p, int x, int y) { return (p ? (x^y) : x) == ((p ? y : 0) ^ x); }
+int xor_yx_x(int p, int y, int x) { return (p ? (y^x) : x) == ((p ? y : 0) ^ x); }
+int xor_y_yx(int p, int x, int y) { return (p ? y : (y^x)) == ((p ? 0 : x) ^ y); }
+
+/*
+ * check-name: fact-select01
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/fact-xor-and.c b/validation/optim/fact-xor-and.c
new file mode 100644
index 00000000..62232b29
--- /dev/null
+++ b/validation/optim/fact-xor-and.c
@@ -0,0 +1,27 @@
+int fr_abx(int a, int b, int x) { return ((a & x) ^ (b & x)) == ((a ^ b) & x); }
+int fl_abx(int a, int b, int x) { return ((x & a) ^ (x & b)) == ((a ^ b) & x); }
+int fm_abx(int a, int b, int x) { return ((a & x) ^ (x & b)) == ((a ^ b) & x); }
+int fn_abx(int a, int b, int x) { return ((x & a) ^ (b & x)) == ((a ^ b) & x); }
+
+int fr_bax(int b, int a, int x) { return ((a & x) ^ (b & x)) == ((b ^ a) & x); }
+int fl_bax(int b, int a, int x) { return ((x & a) ^ (x & b)) == ((b ^ a) & x); }
+int fm_bax(int b, int a, int x) { return ((a & x) ^ (x & b)) == ((b ^ a) & x); }
+int fn_bax(int b, int a, int x) { return ((x & a) ^ (b & x)) == ((b ^ a) & x); }
+
+int fr_axb(int a, int x, int b) { return ((a & x) ^ (b & x)) == ((a ^ b) & x); }
+int fl_axb(int a, int x, int b) { return ((x & a) ^ (x & b)) == ((a ^ b) & x); }
+int fm_axb(int a, int x, int b) { return ((a & x) ^ (x & b)) == ((a ^ b) & x); }
+int fn_axb(int a, int x, int b) { return ((x & a) ^ (b & x)) == ((a ^ b) & x); }
+
+int fr_bxa(int b, int x, int a) { return ((b & x) ^ (a & x)) == ((b ^ a) & x); }
+int fl_bxa(int b, int x, int a) { return ((x & b) ^ (x & a)) == ((b ^ a) & x); }
+int fm_bxa(int b, int x, int a) { return ((b & x) ^ (x & a)) == ((b ^ a) & x); }
+int fn_bxa(int b, int x, int a) { return ((x & b) ^ (a & x)) == ((b ^ a) & x); }
+
+/*
+ * check-name: fact-xor-and
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/fact-xor-shift.c b/validation/optim/fact-xor-shift.c
new file mode 100644
index 00000000..5fb228bd
--- /dev/null
+++ b/validation/optim/fact-xor-shift.c
@@ -0,0 +1,26 @@
+typedef unsigned int uint;
+typedef   signed int sint;
+
+
+uint fact_xor_shl(uint a, uint b, uint s)
+{
+	return ((a << s) ^ (b << s)) == ((a ^ b) << s);
+}
+
+uint fact_xor_lsr(uint a, uint b, uint s)
+{
+	return ((a >> s) ^ (b >> s)) == ((a ^ b) >> s);
+}
+
+sint fact_xor_asr(sint a, sint b, sint s)
+{
+	return ((a >> s) ^ (b >> s)) == ((a ^ b) >> s);
+}
+
+/*
+ * check-name: fact-xor-shift
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/select-and-shift.c b/validation/optim/select-and-shift.c
new file mode 100644
index 00000000..5313fe4b
--- /dev/null
+++ b/validation/optim/select-and-shift.c
@@ -0,0 +1,17 @@
+#define S1	2
+#define S2	5
+#define S	(S2 - S1)
+
+#define	A	(1 << S1)
+#define	B	(1 << S2)
+
+int foo(int p) { return ((p & A) ? B : 0) == ((((unsigned)p) & A) << S); }
+int bar(int p) { return ((p & B) ? A : 0) == ((((unsigned)p) & B) >> S); }
+
+/*
+ * check-name: select-and-shift
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */