factorize (x OP1 z) OP2 (y OP1 z) into (x OP2 y) OP1 z

Factorize common distributive operations:
	(x * z) + (y * z) --> (x + y) * z
	(x | z) & (y | z) --> (x & y) | z
	(x & z) | (y & z) --> (x | y) & z
	(x & z) ^ (y & z) --> (x ^ y) & z

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>

5 files changed, 78 insertions, 4 deletions

diff --git a/simplify.c b/simplify.c
index 5174a903..319112a9 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1622,11 +1622,32 @@ static int simplify_associative_binop(struct instruction *insn)
 
 static int simplify_add_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
 {
+	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)
 		return replace_binop(insn, OP_SUB, &insn->src1, src2, &insn->src2, def->src);
 
@@ -1714,6 +1735,25 @@ 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;
 	}
 	return 0;
 }
@@ -1730,6 +1770,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));
@@ -1756,6 +1815,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));
diff --git a/validation/optim/fact-add-mul.c b/validation/optim/fact-add-mul.c
index 48c3d656..9da6d71c 100644
--- a/validation/optim/fact-add-mul.c
+++ b/validation/optim/fact-add-mul.c
@@ -21,7 +21,6 @@ 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-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
diff --git a/validation/optim/fact-and-ior.c b/validation/optim/fact-and-ior.c
index f2a78edd..96466616 100644
--- a/validation/optim/fact-and-ior.c
+++ b/validation/optim/fact-and-ior.c
@@ -21,7 +21,6 @@ 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-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
diff --git a/validation/optim/fact-ior-and.c b/validation/optim/fact-ior-and.c
index 7af89df1..a6ad3c45 100644
--- a/validation/optim/fact-ior-and.c
+++ b/validation/optim/fact-ior-and.c
@@ -21,7 +21,6 @@ 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-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
diff --git a/validation/optim/fact-xor-and.c b/validation/optim/fact-xor-and.c
index 905cbf4a..62232b29 100644
--- a/validation/optim/fact-xor-and.c
+++ b/validation/optim/fact-xor-and.c
@@ -21,7 +21,6 @@ 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-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1