Merge branch 'optim-not' into next

* put PSEUDO_ARGS and PSEUDO_REGs in canonical order too
* simplify (~x {&,|,^} x) --> {0,~0,~0}
* simplify ((x cmp y) {&,|,^} (x !cmp y)) --> {0,1,1}

11 files changed, 200 insertions, 23 deletions

diff --git a/linearize.h b/linearize.h
index 31c754e2..2c548d43 100644
--- a/linearize.h
+++ b/linearize.h
@@ -24,11 +24,11 @@ DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t);
 enum pseudo_type {
 	PSEUDO_VOID,
 	PSEUDO_UNDEF,
+	PSEUDO_PHI,
 	PSEUDO_REG,
+	PSEUDO_ARG,
 	PSEUDO_SYM,
 	PSEUDO_VAL,
-	PSEUDO_ARG,
-	PSEUDO_PHI,
 };
 
 struct pseudo {
diff --git a/opcode.h b/opcode.h
index 1524272f..b74ba02d 100644
--- a/opcode.h
+++ b/opcode.h
@@ -32,6 +32,16 @@ extern const struct opcode_table {
 } opcode_table[];
 
 
+static inline int opcode_negate(int opcode)
+{
+	return opcode_table[opcode].negate;
+}
+
+static inline int opcode_swap(int opcode)
+{
+	return opcode_table[opcode].swap;
+}
+
 static inline int opcode_float(int opcode, struct symbol *type)
 {
 	if (!type || !is_float_type(type))
diff --git a/simplify.c b/simplify.c
index e05ad8ac..de03d315 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1452,16 +1452,36 @@ static int switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instru
 	return REPEAT_CSE;
 }
 
+///
+// check if the given pseudos are in canonical order
+//
+// The canonical order is VOID < UNDEF < PHI < REG < ARG < SYM < VAL
+// The rationale is:
+//	* VALs at right (they don't need a definition)
+//	* REGs at left (they need a defining instruction)
+//	* SYMs & ARGs between REGs & VALs
+//	* REGs & ARGs are ordered between themselves by their internal number
+//	* SYMs are ordered between themselves by address
+//	* VOID, UNDEF and PHI are uninteresting (but VOID should have type 0)
 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;
+	int t1 = p1->type;
+	int t2 = p2->type;
 
-	return 1;
+	/* symbol/constants on the right */
+	if (t1 < t2)
+		return 1;
+	if (t1 > t2)
+		return 0;
+	switch (t1) {
+	case PSEUDO_SYM:
+		return p1->sym <= p2->sym;
+	case PSEUDO_REG:
+	case PSEUDO_ARG:
+		return p1->nr <= p2->nr;
+	default:
+		return 1;
+	}
 }
 
 static int canonicalize_commutative(struct instruction *insn)
@@ -1600,6 +1620,84 @@ static int simplify_compare(struct instruction *insn)
 	return 0;
 }
 
+static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
+{
+	struct instruction *def, *defr = NULL;
+	pseudo_t src1 = *p1;
+
+	switch (DEF_OPCODE(def, src1)) {
+	case OP_NOT:
+		if (def->src == *p2)
+			return replace_with_value(insn, 0);
+		break;
+	case OP_BINCMP ... OP_BINCMP_END:
+		if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) {
+			if (def->src1 == defr->src1 && def->src2 == defr->src2)
+				return replace_with_value(insn, 0);
+		}
+		break;
+	}
+	return 0;
+}
+
+static int simplify_and(struct instruction *insn)
+{
+	return simplify_and_one_side(insn, &insn->src1, &insn->src2) ||
+	       simplify_and_one_side(insn, &insn->src2, &insn->src1);
+}
+
+static int simplify_ior_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
+{
+	struct instruction *def, *defr = NULL;
+	pseudo_t src1 = *p1;
+
+	switch (DEF_OPCODE(def, src1)) {
+	case OP_NOT:
+		if (def->src == *p2)
+			return replace_with_value(insn, bits_mask(insn->size));
+		break;
+	case OP_BINCMP ... OP_BINCMP_END:
+		if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) {
+			if (def->src1 == defr->src1 && def->src2 == defr->src2)
+				return replace_with_value(insn, 1);
+		}
+		break;
+	}
+	return 0;
+}
+
+static int simplify_ior(struct instruction *insn)
+{
+	return simplify_ior_one_side(insn, &insn->src1, &insn->src2) ||
+	       simplify_ior_one_side(insn, &insn->src2, &insn->src1);
+}
+
+static int simplify_xor_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
+{
+	struct instruction *def, *defr = NULL;
+	pseudo_t src1 = *p1;
+
+	switch (DEF_OPCODE(def, src1)) {
+	case OP_NOT:
+		if (def->src == *p2)
+			return replace_with_value(insn, bits_mask(insn->size));
+		break;
+	case OP_BINCMP ... OP_BINCMP_END:
+		if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) {
+			if (def->src1 == defr->src1 && def->src2 == defr->src2)
+				return replace_with_value(insn, 1);
+		}
+		break;
+	}
+	return 0;
+}
+
+static int simplify_xor(struct instruction *insn)
+{
+	return simplify_xor_one_side(insn, &insn->src1, &insn->src2) ||
+	       simplify_xor_one_side(insn, &insn->src2, &insn->src1);
+}
+
 static int simplify_constant_unop(struct instruction *insn)
 {
 	long long val = insn->src1->value;
@@ -2191,10 +2289,10 @@ int simplify_instruction(struct instruction *insn)
 	switch (insn->opcode) {
 	case OP_ADD: return simplify_add(insn);
 	case OP_SUB: return simplify_sub(insn);
+	case OP_AND: return simplify_and(insn);
+	case OP_OR:  return simplify_ior(insn);
+	case OP_XOR: return simplify_xor(insn);
 	case OP_MUL:
-	case OP_AND:
-	case OP_OR:
-	case OP_XOR:
 	case OP_SHL:
 	case OP_LSR:
 	case OP_ASR:
diff --git a/validation/linear/pointer-arith32.c b/validation/linear/pointer-arith32.c
index 531fd232..c0163a6f 100644
--- a/validation/linear/pointer-arith32.c
+++ b/validation/linear/pointer-arith32.c
@@ -42,7 +42,7 @@ cps:
 .L0:
 	<entry-point>
 	sext.32     %r2 <- (16) %arg2
-	add.32      %r5 <- %arg1, %r2
+	add.32      %r5 <- %r2, %arg1
 	ret.32      %r5
 
 
@@ -51,7 +51,7 @@ ipss:
 	<entry-point>
 	sext.32     %r10 <- (16) %arg2
 	mul.32      %r11 <- %r10, $4
-	add.32      %r14 <- %arg1, %r11
+	add.32      %r14 <- %r11, %arg1
 	ret.32      %r14
 
 
@@ -60,7 +60,7 @@ ipus:
 	<entry-point>
 	zext.32     %r19 <- (16) %arg2
 	mul.32      %r20 <- %r19, $4
-	add.32      %r23 <- %arg1, %r20
+	add.32      %r23 <- %r20, %arg1
 	ret.32      %r23
 
 
@@ -68,7 +68,7 @@ cpq:
 .L6:
 	<entry-point>
 	trunc.32    %r28 <- (64) %arg2
-	add.32      %r31 <- %arg1, %r28
+	add.32      %r31 <- %r28, %arg1
 	ret.32      %r31
 
 
@@ -77,7 +77,7 @@ ipq_ref:
 	<entry-point>
 	trunc.32    %r37 <- (64) %arg2
 	mul.32      %r38 <- %r37, $4
-	add.32      %r39 <- %arg1, %r38
+	add.32      %r39 <- %r38, %arg1
 	ret.32      %r39
 
 
@@ -86,7 +86,7 @@ ipq:
 	<entry-point>
 	trunc.32    %r43 <- (64) %arg2
 	mul.32      %r44 <- %r43, $4
-	add.32      %r47 <- %arg1, %r44
+	add.32      %r47 <- %r44, %arg1
 	ret.32      %r47
 
 
diff --git a/validation/linear/pointer-arith64.c b/validation/linear/pointer-arith64.c
index dad10331..7f1aac56 100644
--- a/validation/linear/pointer-arith64.c
+++ b/validation/linear/pointer-arith64.c
@@ -35,7 +35,7 @@ cps:
 .L0:
 	<entry-point>
 	sext.64     %r2 <- (16) %arg2
-	add.64      %r5 <- %arg1, %r2
+	add.64      %r5 <- %r2, %arg1
 	ret.64      %r5
 
 
@@ -44,7 +44,7 @@ ipss:
 	<entry-point>
 	sext.64     %r10 <- (16) %arg2
 	mul.64      %r11 <- %r10, $4
-	add.64      %r14 <- %arg1, %r11
+	add.64      %r14 <- %r11, %arg1
 	ret.64      %r14
 
 
@@ -53,7 +53,7 @@ ipus:
 	<entry-point>
 	zext.64     %r19 <- (16) %arg2
 	mul.64      %r20 <- %r19, $4
-	add.64      %r23 <- %arg1, %r20
+	add.64      %r23 <- %r20, %arg1
 	ret.64      %r23
 
 
@@ -62,7 +62,7 @@ ipsi:
 	<entry-point>
 	sext.64     %r28 <- (32) %arg2
 	mul.64      %r29 <- %r28, $4
-	add.64      %r32 <- %arg1, %r29
+	add.64      %r32 <- %r29, %arg1
 	ret.64      %r32
 
 
@@ -71,7 +71,7 @@ ipui:
 	<entry-point>
 	zext.64     %r37 <- (32) %arg2
 	mul.64      %r38 <- %r37, $4
-	add.64      %r41 <- %arg1, %r38
+	add.64      %r41 <- %r38, %arg1
 	ret.64      %r41
 
 
diff --git a/validation/optim/canonical-arg.c b/validation/optim/canonical-arg.c
new file mode 100644
index 00000000..a8ecc9bd
--- /dev/null
+++ b/validation/optim/canonical-arg.c
@@ -0,0 +1,20 @@
+int def(void);
+
+int canon_arg_arg(int a, int b)
+{
+	return (a + b) == (b + a);
+}
+
+int canon_arg_reg(int a)
+{
+	int b = def();
+	return (a + b) == (b + a);
+}
+
+/*
+ * check-name: canonical-arg
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/canonical-not.c b/validation/optim/canonical-not.c
new file mode 100644
index 00000000..9698590f
--- /dev/null
+++ b/validation/optim/canonical-not.c
@@ -0,0 +1,9 @@
+int canon_not(int a, int b) { return (a & ~b) == (~b & a); }
+
+/*
+ * check-name: canonical-not
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cse-arg01.c b/validation/optim/cse-arg01.c
new file mode 100644
index 00000000..3e3e141a
--- /dev/null
+++ b/validation/optim/cse-arg01.c
@@ -0,0 +1,9 @@
+int foo(int a, int b) { return (a < b) == (b > a); }
+
+/*
+ * check-name: cse-arg01
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cse-not01.c b/validation/optim/cse-not01.c
new file mode 100644
index 00000000..ea1bb7cf
--- /dev/null
+++ b/validation/optim/cse-not01.c
@@ -0,0 +1,11 @@
+int and(int a) { return (~a & a) ==  0; }
+int ior(int a) { return (~a | a) == ~0; }
+int xor(int a) { return (~a ^ a) == ~0; }
+
+/*
+ * check-name: cse-not01
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cse-not02.c b/validation/optim/cse-not02.c
new file mode 100644
index 00000000..70addebc
--- /dev/null
+++ b/validation/optim/cse-not02.c
@@ -0,0 +1,11 @@
+int and(int a, int b) { return ((a == b) & (a != b)) == 0; }
+int ior(int a, int b) { return ((a == b) | (a != b)) == 1; }
+int xor(int a, int b) { return ((a == b) ^ (a != b)) == 1; }
+
+/*
+ * check-name: cse-not02
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cse-reg01.c b/validation/optim/cse-reg01.c
new file mode 100644
index 00000000..3ea283d3
--- /dev/null
+++ b/validation/optim/cse-reg01.c
@@ -0,0 +1,9 @@
+int foo(int a, int b) { int x = a + b, y = ~b; return (x < y) == (y > x); }
+
+/*
+ * check-name: cse-reg01
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */