[PATCH 00/22] essential OP_ADD & OP_SUB simplifications

[PATCH 00/22] essential OP_ADD & OP_SUB simplifications

[Luc Van Oostenryck]

These patches are a first set aiming at improving canonicalization
and essential simplifications.

Luc Van Oostenryck (22):
  add testcases about OP_ADD & OP_SUB simplifications
  let switch_pseudo() return REPEAT_CSE
  extract eval_op() from eval_insn()
  unop: add helper eval_unop()
  unop: add helper replace_with_unop()
  add a flag to identify commutative & associative ops
  constants must be truncated to the operation's size
  reassoc: simplify (x # C) # K --> x # eval(C # K)
  sub: reorganize handling of OP_{ADD,SUB}s with constant rightside
  sub: canonicalize (0 - x) into -x
  sub: simplify C - (y + D) --> eval(C-D) - y
  sub: simplify C - (D - z) --> z + eval(C-D)
  sub: simplify (C - y) + D --> eval(C+D) - y
  sub: simplify (x - -y) --> (x + y)
  add: simplify (x + -y) --> (x - y)
  add: simplify (-x + y) --> (y - x)
  sub: simplify (x + y) - x --> y
  sub: simplify (x + y) - y --> x
  sub: simplify x - (x + y) --> -y
  sub: simplify x - (y + x) --> -y
  sub: simplify (x - y) + y --> x
  sub: simplify x + (y - x) --> y

 opcode.def                                |  50 ++---
 opcode.h                                  |   5 +
 simplify.c                                | 250 ++++++++++++++++++----
 validation/optim/canonical-sub-cte.c      |   9 +
 validation/optim/reassoc-op-op1.c         |  14 ++
 validation/optim/simplify-add-neg.c       |   9 +
 validation/optim/simplify-cte-sub-addl.c  |   9 +
 validation/optim/simplify-cte-sub-addr.c  |   9 +
 validation/optim/simplify-cte-sub-subr.c  |   9 +
 validation/optim/simplify-neg-add.c       |   9 +
 validation/optim/simplify-same-add-subl.c |  15 ++
 validation/optim/simplify-same-add-subr.c |  15 ++
 validation/optim/simplify-same-addl-sub.c |   9 +
 validation/optim/simplify-same-sub-addl.c |   9 +
 validation/optim/simplify-same-subl-add.c |  11 +
 validation/optim/simplify-same-subr-add.c |  11 +
 validation/optim/simplify-sub-neg.c       |   9 +
 validation/optim/simplify-zero-sub.c      |   9 +
 18 files changed, 397 insertions(+), 64 deletions(-)
 create mode 100644 validation/optim/canonical-sub-cte.c
 create mode 100644 validation/optim/reassoc-op-op1.c
 create mode 100644 validation/optim/simplify-add-neg.c
 create mode 100644 validation/optim/simplify-cte-sub-addl.c
 create mode 100644 validation/optim/simplify-cte-sub-addr.c
 create mode 100644 validation/optim/simplify-cte-sub-subr.c
 create mode 100644 validation/optim/simplify-neg-add.c
 create mode 100644 validation/optim/simplify-same-add-subl.c
 create mode 100644 validation/optim/simplify-same-add-subr.c
 create mode 100644 validation/optim/simplify-same-addl-sub.c
 create mode 100644 validation/optim/simplify-same-sub-addl.c
 create mode 100644 validation/optim/simplify-same-subl-add.c
 create mode 100644 validation/optim/simplify-same-subr-add.c
 create mode 100644 validation/optim/simplify-sub-neg.c
 create mode 100644 validation/optim/simplify-zero-sub.c


base-commit: 5192dc1ff23dae8644480a89ada8ff420ebb674a
-- 
2.28.0

[PATCH 01/22] add testcases about OP_ADD & OP_SUB simplifications

[Luc Van Oostenryck]

Add some testcases about basic simplifications of additions
and subtractions.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/canonical-sub-cte.c      | 10 ++++++++++
 validation/optim/reassoc-op-op1.c         | 15 +++++++++++++++
 validation/optim/simplify-add-neg.c       | 10 ++++++++++
 validation/optim/simplify-cte-sub-addl.c  | 10 ++++++++++
 validation/optim/simplify-cte-sub-addr.c  | 10 ++++++++++
 validation/optim/simplify-cte-sub-subr.c  | 10 ++++++++++
 validation/optim/simplify-neg-add.c       | 10 ++++++++++
 validation/optim/simplify-same-add-subl.c | 16 ++++++++++++++++
 validation/optim/simplify-same-add-subr.c | 16 ++++++++++++++++
 validation/optim/simplify-same-addl-sub.c | 10 ++++++++++
 validation/optim/simplify-same-sub-addl.c | 10 ++++++++++
 validation/optim/simplify-same-subl-add.c | 12 ++++++++++++
 validation/optim/simplify-same-subr-add.c | 12 ++++++++++++
 validation/optim/simplify-sub-neg.c       | 10 ++++++++++
 validation/optim/simplify-zero-sub.c      | 10 ++++++++++
 15 files changed, 171 insertions(+)
 create mode 100644 validation/optim/canonical-sub-cte.c
 create mode 100644 validation/optim/reassoc-op-op1.c
 create mode 100644 validation/optim/simplify-add-neg.c
 create mode 100644 validation/optim/simplify-cte-sub-addl.c
 create mode 100644 validation/optim/simplify-cte-sub-addr.c
 create mode 100644 validation/optim/simplify-cte-sub-subr.c
 create mode 100644 validation/optim/simplify-neg-add.c
 create mode 100644 validation/optim/simplify-same-add-subl.c
 create mode 100644 validation/optim/simplify-same-add-subr.c
 create mode 100644 validation/optim/simplify-same-addl-sub.c
 create mode 100644 validation/optim/simplify-same-sub-addl.c
 create mode 100644 validation/optim/simplify-same-subl-add.c
 create mode 100644 validation/optim/simplify-same-subr-add.c
 create mode 100644 validation/optim/simplify-sub-neg.c
 create mode 100644 validation/optim/simplify-zero-sub.c

diff --git a/validation/optim/canonical-sub-cte.c b/validation/optim/canonical-sub-cte.c
new file mode 100644
index 000000000000..223be96fa5a5
--- /dev/null
+++ b/validation/optim/canonical-sub-cte.c
@@ -0,0 +1,10 @@
+int sub_cte(int x) { return (x - 1) != (x + -1); }
+
+/*
+ * check-name: canonical-sub-cte
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: ret\\..*\\$0
+ */
diff --git a/validation/optim/reassoc-op-op1.c b/validation/optim/reassoc-op-op1.c
new file mode 100644
index 000000000000..aa7092ff57a0
--- /dev/null
+++ b/validation/optim/reassoc-op-op1.c
@@ -0,0 +1,15 @@
+int foo(int x, int *ptr)
+{
+	int t = x + 1;
+	*ptr = t;
+	return t + -1;
+}
+
+/*
+ * check-name: reassoc-op-op1
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-pattern(1): add\\.
+ */
diff --git a/validation/optim/simplify-add-neg.c b/validation/optim/simplify-add-neg.c
new file mode 100644
index 000000000000..19b64b096567
--- /dev/null
+++ b/validation/optim/simplify-add-neg.c
@@ -0,0 +1,10 @@
+int add_neg(int x, int y) { return x + -y; }
+
+/*
+ * check-name: simplify-add-neg
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: sub\\..*%arg1, %arg2
+ */
diff --git a/validation/optim/simplify-cte-sub-addl.c b/validation/optim/simplify-cte-sub-addl.c
new file mode 100644
index 000000000000..49e510062c03
--- /dev/null
+++ b/validation/optim/simplify-cte-sub-addl.c
@@ -0,0 +1,10 @@
+int cte_sub_addl(int x) { return (1 - x) + 1; }
+
+/*
+ * check-name: simplify-cte-sub-addl
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: sub\\..*\\$2, %arg1
+ */
diff --git a/validation/optim/simplify-cte-sub-addr.c b/validation/optim/simplify-cte-sub-addr.c
new file mode 100644
index 000000000000..81f5b34551c6
--- /dev/null
+++ b/validation/optim/simplify-cte-sub-addr.c
@@ -0,0 +1,10 @@
+int cte_sub_addr(int x) { return 2 - (x + 1); }
+
+/*
+ * check-name: simplify-cte-sub-addr
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: sub\\..*\\$1, %arg1
+ */
diff --git a/validation/optim/simplify-cte-sub-subr.c b/validation/optim/simplify-cte-sub-subr.c
new file mode 100644
index 000000000000..950b233e60c3
--- /dev/null
+++ b/validation/optim/simplify-cte-sub-subr.c
@@ -0,0 +1,10 @@
+int cte_sub_subr(int x) { return 1 - (1 - x); }
+
+/*
+ * check-name: simplify-cte-sub-subr
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: ret\\..* %arg1
+ */
diff --git a/validation/optim/simplify-neg-add.c b/validation/optim/simplify-neg-add.c
new file mode 100644
index 000000000000..66a820f28069
--- /dev/null
+++ b/validation/optim/simplify-neg-add.c
@@ -0,0 +1,10 @@
+int neg_add(int x, int y) { return -x + y; }
+
+/*
+ * check-name: simplify-neg-add
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: sub\\..*%arg2, %arg1
+ */
diff --git a/validation/optim/simplify-same-add-subl.c b/validation/optim/simplify-same-add-subl.c
new file mode 100644
index 000000000000..1f17ef0b968e
--- /dev/null
+++ b/validation/optim/simplify-same-add-subl.c
@@ -0,0 +1,16 @@
+int add_subl(int x, int y) { return (x + y) - x; }
+
+/*
+ * check-name: simplify-same-add-subl
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-start
+add_subl:
+.L0:
+	<entry-point>
+	ret.32      %arg2
+
+
+ * check-output-end
+ */
diff --git a/validation/optim/simplify-same-add-subr.c b/validation/optim/simplify-same-add-subr.c
new file mode 100644
index 000000000000..e8540703ee7d
--- /dev/null
+++ b/validation/optim/simplify-same-add-subr.c
@@ -0,0 +1,16 @@
+int add_subr(int x, int y) { return (x + y) - y; }
+
+/*
+ * check-name: simplify-same-add-subr
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-start
+add_subr:
+.L0:
+	<entry-point>
+	ret.32      %arg1
+
+
+ * check-output-end
+ */
diff --git a/validation/optim/simplify-same-addl-sub.c b/validation/optim/simplify-same-addl-sub.c
new file mode 100644
index 000000000000..51d2b07966f4
--- /dev/null
+++ b/validation/optim/simplify-same-addl-sub.c
@@ -0,0 +1,10 @@
+int foo(int x, int y) { return x + (y - x); }
+
+/*
+ * check-name: simplify-same-addl-sub
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: ret\\..*%arg2
+ */
diff --git a/validation/optim/simplify-same-sub-addl.c b/validation/optim/simplify-same-sub-addl.c
new file mode 100644
index 000000000000..78f217399e50
--- /dev/null
+++ b/validation/optim/simplify-same-sub-addl.c
@@ -0,0 +1,10 @@
+int foo(int x, int y) { return (x - y) + y; }
+
+/*
+ * check-name: simplify-same-sub-addl
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: ret\\..*%arg1
+ */
diff --git a/validation/optim/simplify-same-subl-add.c b/validation/optim/simplify-same-subl-add.c
new file mode 100644
index 000000000000..dbc0fe97f126
--- /dev/null
+++ b/validation/optim/simplify-same-subl-add.c
@@ -0,0 +1,12 @@
+int subl_add(int x, int y) { return x - (x + y); }
+
+/*
+ * check-name: simplify-same-subl-add
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: neg\\..* %arg2
+ * check-output-excludes: add\\.
+ * check-output-excludes: sub\\.
+ */
diff --git a/validation/optim/simplify-same-subr-add.c b/validation/optim/simplify-same-subr-add.c
new file mode 100644
index 000000000000..bafd2643bfd0
--- /dev/null
+++ b/validation/optim/simplify-same-subr-add.c
@@ -0,0 +1,12 @@
+int subr_add(int x, int y) { return x - (y + x); }
+
+/*
+ * check-name: simplify-same-subr-add
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: neg\\..* %arg2
+ * check-output-excludes: add\\.
+ * check-output-excludes: sub\\.
+ */
diff --git a/validation/optim/simplify-sub-neg.c b/validation/optim/simplify-sub-neg.c
new file mode 100644
index 000000000000..b6fcc2baabec
--- /dev/null
+++ b/validation/optim/simplify-sub-neg.c
@@ -0,0 +1,10 @@
+int sub_neg(int x, int y) { return x - -y; }
+
+/*
+ * check-name: simplify-sub-neg
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: add\\..*%arg., %arg.
+ */
diff --git a/validation/optim/simplify-zero-sub.c b/validation/optim/simplify-zero-sub.c
new file mode 100644
index 000000000000..cc8fe7a3159b
--- /dev/null
+++ b/validation/optim/simplify-zero-sub.c
@@ -0,0 +1,10 @@
+int zero_sub(int x) { return 0 - x; }
+
+/*
+ * check-name: simplify-zero-sub
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-contains: neg\\..* %arg1
+ */
-- 
2.28.0

[PATCH 02/22] let switch_pseudo() return REPEAT_CSE

[Luc Van Oostenryck]

It make some uses easier and more compact.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 15452a585598..edef3a7e5c1e 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1202,7 +1202,7 @@ static int simplify_binop(struct instruction *insn)
 	return 0;
 }
 
-static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
+static int switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
 {
 	pseudo_t p1 = *pp1, p2 = *pp2;
 
@@ -1210,6 +1210,7 @@ static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instr
 	use_pseudo(insn2, p1, pp2);
 	remove_usage(p1, pp1);
 	remove_usage(p2, pp2);
+	return REPEAT_CSE;
 }
 
 static int canonical_order(pseudo_t p1, pseudo_t p2)
-- 
2.28.0

[PATCH 03/22] extract eval_op() from eval_insn()

[Luc Van Oostenryck]

eval_insn() can be handy when there is an existing instruction
to evaluate but it can happen that there isn't one, only pseudos.

Allow to reuse the evaluation code by using a new API: eval_op()
extracted from eval_insn() and taking all its input as arguments
(opcode, size, src1 & src2).

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

diff --git a/simplify.c b/simplify.c
index edef3a7e5c1e..ac27debfcefb 100644
--- a/simplify.c
+++ b/simplify.c
@@ -516,12 +516,11 @@ static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
 	return size;
 }
 
-static pseudo_t eval_insn(struct instruction *insn)
+static pseudo_t eval_op(int op, unsigned size, pseudo_t src1, pseudo_t src2)
 {
 	/* FIXME! Verify signs and sizes!! */
-	unsigned int size = insn->size;
-	long long left = insn->src1->value;
-	long long right = insn->src2->value;
+	long long left = src1->value;
+	long long right = src2->value;
 	unsigned long long ul, ur;
 	long long res, mask, bits;
 
@@ -535,7 +534,7 @@ static pseudo_t eval_insn(struct instruction *insn)
 	ul = left & bits;
 	ur = right & bits;
 
-	switch (insn->opcode) {
+	switch (op) {
 	case OP_ADD:
 		res = left + right;
 		break;
@@ -754,6 +753,11 @@ static int simplify_mask_shift(struct instruction *sh, unsigned long long mask)
 	return 0;
 }
 
+static pseudo_t eval_insn(struct instruction *insn)
+{
+	return eval_op(insn->opcode, insn->size, insn->src1, insn->src2);
+}
+
 static long long check_shift_count(struct instruction *insn, unsigned long long uval)
 {
 	unsigned int size = insn->size;
-- 
2.28.0

[PATCH 04/22] unop: add helper eval_unop()

[Luc Van Oostenryck]

Currently, eval_op() only do the evaluation of binops but unops
need sometimes to be evaluated too.

So, teach eval_op() about OP_NEG & OP_NOT and add a new helper,
eval_unop() for making it easier to use with unops.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/simplify.c b/simplify.c
index ac27debfcefb..4c6569eba036 100644
--- a/simplify.c
+++ b/simplify.c
@@ -535,6 +535,13 @@ static pseudo_t eval_op(int op, unsigned size, pseudo_t src1, pseudo_t src2)
 	ur = right & bits;
 
 	switch (op) {
+	case OP_NEG:
+		res = -left;
+		break;
+	case OP_NOT:
+		res = ~ul;
+		break;
+
 	case OP_ADD:
 		res = left + right;
 		break;
@@ -636,6 +643,11 @@ undef:
 	return NULL;
 }
 
+static inline pseudo_t eval_unop(int op, unsigned size, pseudo_t src)
+{
+	return eval_op(op, size, src, VOID);
+}
+
 ///
 // Simplifications
 // ^^^^^^^^^^^^^^^
-- 
2.28.0

[PATCH 05/22] unop: add helper replace_with_unop()

[Luc Van Oostenryck]

Some simplifications reduce to transforming a binop into an unop.
Add an helper for making this change easier and more readable.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/simplify.c b/simplify.c
index 4c6569eba036..3cac124f7d9f 100644
--- a/simplify.c
+++ b/simplify.c
@@ -470,6 +470,20 @@ static inline int replace_with_value(struct instruction *insn, long long val)
 	return replace_with_pseudo(insn, value_pseudo(val));
 }
 
+///
+// replace a binop with an unop
+// @insn: the instruction to be replaced
+// @op: the instruction's new opcode
+// @src: the instruction's new operand
+// @return: REPEAT_CSE
+static inline int replace_with_unop(struct instruction *insn, int op, pseudo_t src)
+{
+	insn->opcode = op;
+	replace_pseudo(insn, &insn->src1, src);
+	remove_usage(insn->src2, &insn->src2);
+	return REPEAT_CSE;
+}
+
 static inline int def_opcode(pseudo_t p)
 {
 	if (p->type != PSEUDO_REG)
-- 
2.28.0

[PATCH 06/22] add a flag to identify commutative & associative ops

[Luc Van Oostenryck]

The way how the functions doing the simplification of commutative
or associative binops are called is simple but complicates the
simplification of a specific binop.

Fix this by adding a flag to the opcode table to identify the
commutative and the associative binops and using this flag
to call or not the functions doing the corresponding simplification.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 opcode.def | 50 +++++++++++++++++++--------------------
 opcode.h   |  5 ++++
 simplify.c | 69 ++++++++++++++++++++++++++++++++++++------------------
 3 files changed, 76 insertions(+), 48 deletions(-)

diff --git a/opcode.def b/opcode.def
index 1401d988d73a..c65722f0b9bb 100644
--- a/opcode.def
+++ b/opcode.def
@@ -15,16 +15,16 @@ OPCODE(COMPUTEDGOTO,    BADOP,    BADOP,    BADOP, 1, OPF_NONE)
 OPCODE_RANGE(TERMINATOR, RET, COMPUTEDGOTO)
 
 /* Binary */
-OPCODE(ADD,             BADOP,    BADOP,    FADD,  2, OPF_TARGET)
-OPCODE(SUB,             BADOP,    BADOP,    FSUB,  2, OPF_TARGET)
-OPCODE(MUL,             BADOP,    BADOP,    FMUL,  2, OPF_TARGET)
-OPCODE(DIVU,            BADOP,    BADOP,    FDIV,  2, OPF_TARGET)
-OPCODE(DIVS,            BADOP,    BADOP,    FDIV,  2, OPF_TARGET)
-OPCODE(MODU,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(MODS,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(SHL,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(LSR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(ASR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
+OPCODE(ADD,             BADOP,    BADOP,    FADD,  2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(MUL,             BADOP,    BADOP,    FMUL,  2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(SUB,             BADOP,    BADOP,    FSUB,  2, OPF_TARGET|OPF_BINOP)
+OPCODE(DIVU,            BADOP,    BADOP,    FDIV,  2, OPF_TARGET|OPF_BINOP)
+OPCODE(DIVS,            BADOP,    BADOP,    FDIV,  2, OPF_TARGET|OPF_BINOP)
+OPCODE(MODU,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(MODS,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(SHL,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(LSR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
+OPCODE(ASR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_BINOP)
 
 /* Floating-point binops */
 OPCODE(FADD,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
@@ -33,9 +33,9 @@ OPCODE(FMUL,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
 OPCODE(FDIV,            BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
 
 /* Logical */
-OPCODE(AND,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(OR,              BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
-OPCODE(XOR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET)
+OPCODE(AND,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(OR,              BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
+OPCODE(XOR,             BADOP,    BADOP,    BADOP, 2, OPF_TARGET|OPF_COMMU|OPF_ASSOC|OPF_BINOP)
 OPCODE_RANGE(BINARY, ADD, XOR)
 
 /* floating-point comparison */
@@ -56,21 +56,21 @@ OPCODE(FCMP_UNO,        FCMP_ORD, FCMP_UNO, BADOP, 2, OPF_TARGET)
 OPCODE_RANGE(FPCMP, FCMP_ORD, FCMP_UNO)
 
 /* Binary comparison */
-OPCODE(SET_EQ,          SET_NE,   SET_EQ,   FCMP_OEQ, 2, OPF_TARGET)
-OPCODE(SET_LT,          SET_GE,   SET_GT,   FCMP_OLT, 2, OPF_TARGET)
-OPCODE(SET_LE,          SET_GT,   SET_GE,   FCMP_OLE, 2, OPF_TARGET)
-OPCODE(SET_GE,          SET_LT,   SET_LE,   FCMP_OGE, 2, OPF_TARGET)
-OPCODE(SET_GT,          SET_LE,   SET_LT,   FCMP_OGT, 2, OPF_TARGET)
-OPCODE(SET_B,           SET_AE,   SET_A,    FCMP_OLT, 2, OPF_TARGET)
-OPCODE(SET_BE,          SET_A,    SET_AE,   FCMP_OLE, 2, OPF_TARGET)
-OPCODE(SET_AE,          SET_B,    SET_BE,   FCMP_OGE, 2, OPF_TARGET)
-OPCODE(SET_A,           SET_BE,   SET_B,    FCMP_OGT, 2, OPF_TARGET)
-OPCODE(SET_NE,          SET_EQ,   SET_NE,   FCMP_UNE, 2, OPF_TARGET)
+OPCODE(SET_EQ,          SET_NE,   SET_EQ,   FCMP_OEQ, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_COMMU)
+OPCODE(SET_LT,          SET_GE,   SET_GT,   FCMP_OLT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
+OPCODE(SET_LE,          SET_GT,   SET_GE,   FCMP_OLE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
+OPCODE(SET_GE,          SET_LT,   SET_LE,   FCMP_OGE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
+OPCODE(SET_GT,          SET_LE,   SET_LT,   FCMP_OGT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
+OPCODE(SET_B,           SET_AE,   SET_A,    FCMP_OLT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
+OPCODE(SET_BE,          SET_A,    SET_AE,   FCMP_OLE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
+OPCODE(SET_AE,          SET_B,    SET_BE,   FCMP_OGE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
+OPCODE(SET_A,           SET_BE,   SET_B,    FCMP_OGT, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE)
+OPCODE(SET_NE,          SET_EQ,   SET_NE,   FCMP_UNE, 2, OPF_TARGET|OPF_BINOP|OPF_COMPARE|OPF_COMMU)
 OPCODE_RANGE(BINCMP, SET_EQ, SET_NE)
 
 /* Uni */
-OPCODE(NOT,             BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
-OPCODE(NEG,             BADOP,    BADOP,    FNEG,  1, OPF_TARGET)
+OPCODE(NOT,             BADOP,    BADOP,    BADOP, 1, OPF_TARGET|OPF_UNOP)
+OPCODE(NEG,             BADOP,    BADOP,    FNEG,  1, OPF_TARGET|OPF_UNOP)
 OPCODE(FNEG,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
 OPCODE(TRUNC,           BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
 OPCODE(ZEXT,            BADOP,    BADOP,    BADOP, 1, OPF_TARGET)
diff --git a/opcode.h b/opcode.h
index e426bed4f7e2..bb94ec81c832 100644
--- a/opcode.h
+++ b/opcode.h
@@ -20,6 +20,11 @@ extern const struct opcode_table {
 	unsigned int flags:6;
 #define			OPF_NONE	0
 #define			OPF_TARGET	(1 << 0)
+#define			OPF_COMMU	(1 << 1)
+#define			OPF_ASSOC	(1 << 2)
+#define			OPF_UNOP	(1 << 3)
+#define			OPF_BINOP	(1 << 4)
+#define			OPF_COMPARE	(1 << 5)
 } opcode_table[];
 
 
diff --git a/simplify.c b/simplify.c
index 3cac124f7d9f..db7a1e47ff0a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1736,35 +1736,57 @@ found:
 
 int simplify_instruction(struct instruction *insn)
 {
+	unsigned flags;
+	int changed = 0;
+
 	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);
+	flags = opcode_table[insn->opcode].flags;
+	if (flags & OPF_COMMU)
+		canonicalize_commutative(insn) ;
+	if (flags & OPF_COMPARE)
+		canonicalize_compare(insn) ;
+	if (flags & OPF_BINOP) {
+		if ((changed = simplify_binop(insn)))
+			return changed;
+	}
+	if (flags & OPF_ASSOC) {
+		if ((changed = simplify_associative_binop(insn)))
+			return changed;
+	}
+	if (flags & OPF_UNOP) {
+		if ((changed = simplify_unop(insn)))
+			return changed;
+	}
 
-	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 */
+	switch (insn->opcode) {
+	case OP_ADD:
 	case OP_SUB:
-	case OP_DIVU: case OP_DIVS:
-	case OP_MODU: case OP_MODS:
+	case OP_MUL:
+	case OP_AND:
+	case OP_OR:
+	case OP_XOR:
 	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_LSR:
+	case OP_ASR:
+	case OP_NOT:
+	case OP_NEG:
+	case OP_DIVU:
+	case OP_DIVS:
+	case OP_MODU:
+	case OP_MODS:
+	case OP_SET_EQ:
+	case OP_SET_NE:
+	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:
+		break;
 	case OP_LOAD:
 		if (!has_users(insn->target))
 			return kill_instruction(insn);
@@ -1778,6 +1800,7 @@ int simplify_instruction(struct instruction *insn)
 	case OP_SEXT: case OP_ZEXT:
 	case OP_TRUNC:
 		return simplify_cast(insn);
+	case OP_FNEG:
 	case OP_FCVTU: case OP_FCVTS:
 	case OP_UCVTF: case OP_SCVTF:
 	case OP_FCVTF:
-- 
2.28.0

[PATCH 07/22] constants must be truncated to the operation's size

[Luc Van Oostenryck]

At expansion phase, when simplified, all constants are truncated
to the size of the operations that generate them.

This should be done during simplification too because:
*) if some constants are sometimes truncated and sometimes
   sign-extended, CSE will miss some opportunities.
*) it's not possible to sign-extend them because it's not
   always known if the constant is used in a signed context or not.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                           | 2 +-
 validation/optim/canonical-sub-cte.c | 1 -
 2 files changed, 1 insertion(+), 2 deletions(-)

diff --git a/simplify.c b/simplify.c
index db7a1e47ff0a..3935552bd6fa 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1118,7 +1118,7 @@ static int simplify_constant_rightside(struct instruction *insn)
 	case OP_SUB:
 		if (value) {
 			insn->opcode = OP_ADD;
-			insn->src2 = value_pseudo(-value);
+			insn->src2 = eval_unop(OP_NEG, insn->size, insn->src2);
 			return REPEAT_CSE;
 		}
 	/* Fall through */
diff --git a/validation/optim/canonical-sub-cte.c b/validation/optim/canonical-sub-cte.c
index 223be96fa5a5..c0072884b1e6 100644
--- a/validation/optim/canonical-sub-cte.c
+++ b/validation/optim/canonical-sub-cte.c
@@ -3,7 +3,6 @@ int sub_cte(int x) { return (x - 1) != (x + -1); }
 /*
  * check-name: canonical-sub-cte
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: ret\\..*\\$0
-- 
2.28.0

[PATCH 08/22] reassoc: simplify (x # C) # K --> x # eval(C # K)

[Luc Van Oostenryck]

Do this simplification once for all associative binops.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                        | 5 +++++
 validation/optim/reassoc-op-op1.c | 1 -
 2 files changed, 5 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 3935552bd6fa..b14f88405861 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1295,6 +1295,11 @@ static int simplify_associative_binop(struct instruction *insn)
 		return 0;
 	if (!simple_pseudo(def->src2))
 		return 0;
+	if (constant(def->src2) && constant(insn->src2)) {
+		// (x # C) # K --> x # eval(C # K)
+		insn->src2 = eval_op(insn->opcode, insn->size, insn->src2, def->src2);
+		return replace_pseudo(insn, &insn->src1, def->src1);
+	}
 	if (multi_users(def->target))
 		return 0;
 	switch_pseudo(def, &def->src1, insn, &insn->src2);
diff --git a/validation/optim/reassoc-op-op1.c b/validation/optim/reassoc-op-op1.c
index aa7092ff57a0..3d050c142249 100644
--- a/validation/optim/reassoc-op-op1.c
+++ b/validation/optim/reassoc-op-op1.c
@@ -8,7 +8,6 @@ int foo(int x, int *ptr)
 /*
  * check-name: reassoc-op-op1
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-pattern(1): add\\.
-- 
2.28.0

[PATCH 09/22] sub: reorganize handling of OP_{ADD,SUB}s with constant rightside

[Luc Van Oostenryck]

This is a preparatory step for more interesting changes later.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/simplify.c b/simplify.c
index b14f88405861..f837b003efd4 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1101,6 +1101,7 @@ 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);
+	int changed = 0;
 
 	switch (insn->opcode) {
 	case OP_OR:
@@ -1113,20 +1114,21 @@ static int simplify_constant_rightside(struct instruction *insn)
 			insn->opcode = OP_NOT;
 			return REPEAT_CSE;
 		}
-		goto case_neutral_zero;
+		/* fallthrough */
+	case_neutral_zero:
+		if (!value)
+			return replace_with_pseudo(insn, insn->src1);
+		return 0;
 
 	case OP_SUB:
-		if (value) {
-			insn->opcode = OP_ADD;
-			insn->src2 = eval_unop(OP_NEG, insn->size, insn->src2);
-			return REPEAT_CSE;
-		}
-	/* Fall through */
+		insn->opcode = OP_ADD;
+		insn->src2 = eval_unop(OP_NEG, insn->size, insn->src2);
+		changed = REPEAT_CSE;
+		/* fallthrough */
 	case OP_ADD:
-	case_neutral_zero:
 		if (!value)
 			return replace_with_pseudo(insn, insn->src1);
-		return 0;
+		return changed;
 	case OP_ASR:
 	case OP_SHL:
 	case OP_LSR:
-- 
2.28.0

[PATCH 10/22] sub: canonicalize (0 - x) into -x

[Luc Van Oostenryck]

Not really a simplification in itself but it make some other
simplification a little easier (already because there is one
argument less to be matched).

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                           | 4 ++++
 validation/optim/simplify-zero-sub.c | 1 -
 2 files changed, 4 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index f837b003efd4..aa0357d9e285 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1174,6 +1174,10 @@ static int simplify_constant_leftside(struct instruction *insn)
 		if (!value)
 			return replace_with_pseudo(insn, insn->src1);
 		return 0;
+	case OP_SUB:
+		if (!value)			// (0 - x) --> -x
+			return replace_with_unop(insn, OP_NEG, insn->src2);
+		break;
 	}
 	return 0;
 }
diff --git a/validation/optim/simplify-zero-sub.c b/validation/optim/simplify-zero-sub.c
index cc8fe7a3159b..70ce7c908844 100644
--- a/validation/optim/simplify-zero-sub.c
+++ b/validation/optim/simplify-zero-sub.c
@@ -3,7 +3,6 @@ int zero_sub(int x) { return 0 - x; }
 /*
  * check-name: simplify-zero-sub
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: neg\\..* %arg1
-- 
2.28.0

[PATCH 11/22] sub: simplify C - (y + D) --> eval(C-D) - y

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                               | 18 ++++++++++++++++++
 validation/optim/simplify-cte-sub-addr.c |  1 -
 2 files changed, 18 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index aa0357d9e285..b97354bc40cc 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1157,6 +1157,22 @@ static int simplify_constant_rightside(struct instruction *insn)
 	return 0;
 }
 
+static int simplify_const_leftsub(struct instruction *insn, struct instruction *def)
+{
+	unsigned size = insn->size;
+	pseudo_t src1 = insn->src1;
+
+	switch (def->opcode) {
+	case OP_ADD:
+		if (constant(def->src2)) { // C - (y + D) --> eval(C-D) - y
+			insn->src1 = eval_op(OP_SUB, size, src1, def->src2);
+			return replace_pseudo(insn, &insn->src2, def->src1);
+		}
+		break;
+	}
+	return 0;
+}
+
 static int simplify_constant_leftside(struct instruction *insn)
 {
 	long long value = insn->src1->value;
@@ -1177,6 +1193,8 @@ static int simplify_constant_leftside(struct instruction *insn)
 	case OP_SUB:
 		if (!value)			// (0 - x) --> -x
 			return replace_with_unop(insn, OP_NEG, insn->src2);
+		if (insn->src2->type == PSEUDO_REG)
+			return simplify_const_leftsub(insn, insn->src2->def);
 		break;
 	}
 	return 0;
diff --git a/validation/optim/simplify-cte-sub-addr.c b/validation/optim/simplify-cte-sub-addr.c
index 81f5b34551c6..bf36c8a0a30a 100644
--- a/validation/optim/simplify-cte-sub-addr.c
+++ b/validation/optim/simplify-cte-sub-addr.c
@@ -3,7 +3,6 @@ int cte_sub_addr(int x) { return 2 - (x + 1); }
 /*
  * check-name: simplify-cte-sub-addr
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: sub\\..*\\$1, %arg1
-- 
2.28.0

[PATCH 12/22] sub: simplify C - (D - z) --> z + eval(C-D)

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                               | 8 ++++++++
 validation/optim/simplify-cte-sub-subr.c | 1 -
 2 files changed, 8 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index b97354bc40cc..7d1897e65b07 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1169,6 +1169,14 @@ static int simplify_const_leftsub(struct instruction *insn, struct instruction *
 			return replace_pseudo(insn, &insn->src2, def->src1);
 		}
 		break;
+	case OP_SUB:
+		if (constant(def->src1)) { // C - (D - z) --> z + eval(C-D)
+			pseudo_t val = eval_op(OP_SUB, size, src1, def->src1);
+			insn->opcode = OP_ADD;
+			use_pseudo(insn, def->src2, &insn->src1);
+			return replace_pseudo(insn, &insn->src2, val);
+		}
+		break;
 	}
 	return 0;
 }
diff --git a/validation/optim/simplify-cte-sub-subr.c b/validation/optim/simplify-cte-sub-subr.c
index 950b233e60c3..10fdbbc82933 100644
--- a/validation/optim/simplify-cte-sub-subr.c
+++ b/validation/optim/simplify-cte-sub-subr.c
@@ -3,7 +3,6 @@ int cte_sub_subr(int x) { return 1 - (1 - x); }
 /*
  * check-name: simplify-cte-sub-subr
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: ret\\..* %arg1
-- 
2.28.0

[PATCH 13/22] sub: simplify (C - y) + D --> eval(C+D) - y

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                               | 20 ++++++++++++++++++++
 validation/optim/simplify-cte-sub-addl.c |  1 -
 2 files changed, 20 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 7d1897e65b07..929a177631e5 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1096,6 +1096,24 @@ static int simplify_constant_mask(struct instruction *insn, unsigned long long m
 	return 0;
 }
 
+static int simplify_const_rightadd(struct instruction *def, struct instruction *insn)
+{
+	unsigned size = insn->size;
+	pseudo_t src2 = insn->src2;
+
+	switch (def->opcode) {
+	case OP_SUB:
+		if (constant(def->src1)) { // (C - y) + D --> eval(C+D) - y
+			pseudo_t val = eval_op(OP_ADD, size, def->src1, src2);
+			insn->opcode = OP_SUB;
+			use_pseudo(insn, def->src2, &insn->src2);
+			return replace_pseudo(insn, &insn->src1, val);
+		}
+		break;
+	}
+	return 0;
+}
+
 static int simplify_constant_rightside(struct instruction *insn)
 {
 	long long value = insn->src2->value;
@@ -1128,6 +1146,8 @@ static int simplify_constant_rightside(struct instruction *insn)
 	case OP_ADD:
 		if (!value)
 			return replace_with_pseudo(insn, insn->src1);
+		if (insn->src1->type == PSEUDO_REG)	// (x # y) + z
+			changed |= simplify_const_rightadd(insn->src1->def, insn);
 		return changed;
 	case OP_ASR:
 	case OP_SHL:
diff --git a/validation/optim/simplify-cte-sub-addl.c b/validation/optim/simplify-cte-sub-addl.c
index 49e510062c03..137029636f2d 100644
--- a/validation/optim/simplify-cte-sub-addl.c
+++ b/validation/optim/simplify-cte-sub-addl.c
@@ -3,7 +3,6 @@ int cte_sub_addl(int x) { return (1 - x) + 1; }
 /*
  * check-name: simplify-cte-sub-addl
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: sub\\..*\\$2, %arg1
-- 
2.28.0

[PATCH 14/22] sub: simplify (x - -y) --> (x + y)

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                          | 16 +++++++++++++++-
 validation/optim/simplify-sub-neg.c |  1 -
 2 files changed, 15 insertions(+), 2 deletions(-)

diff --git a/simplify.c b/simplify.c
index 929a177631e5..fa7e1679d7ac 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1358,6 +1358,20 @@ static int simplify_associative_binop(struct instruction *insn)
 	return REPEAT_CSE;
 }
 
+static int simplify_sub(struct instruction *insn)
+{
+	pseudo_t src2 = insn->src2;
+	struct instruction *def;
+
+	switch (DEF_OPCODE(def, src2)) {
+	case OP_NEG:				// (x - -y) --> (x + y)
+		insn->opcode = OP_ADD;
+		return replace_pseudo(insn, &insn->src2, def->src);
+	}
+
+	return 0;
+}
+
 static int simplify_constant_unop(struct instruction *insn)
 {
 	long long val = insn->src1->value;
@@ -1818,8 +1832,8 @@ int simplify_instruction(struct instruction *insn)
 	}
 
 	switch (insn->opcode) {
+	case OP_SUB: return simplify_sub(insn);
 	case OP_ADD:
-	case OP_SUB:
 	case OP_MUL:
 	case OP_AND:
 	case OP_OR:
diff --git a/validation/optim/simplify-sub-neg.c b/validation/optim/simplify-sub-neg.c
index b6fcc2baabec..49be847cca7d 100644
--- a/validation/optim/simplify-sub-neg.c
+++ b/validation/optim/simplify-sub-neg.c
@@ -3,7 +3,6 @@ int sub_neg(int x, int y) { return x - -y; }
 /*
  * check-name: simplify-sub-neg
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: add\\..*%arg., %arg.
-- 
2.28.0

[PATCH 15/22] add: simplify (x + -y) --> (x - y)

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                          | 16 +++++++++++++++-
 validation/optim/simplify-add-neg.c |  1 -
 2 files changed, 15 insertions(+), 2 deletions(-)

diff --git a/simplify.c b/simplify.c
index fa7e1679d7ac..f8a0ba726561 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1358,6 +1358,20 @@ static int simplify_associative_binop(struct instruction *insn)
 	return REPEAT_CSE;
 }
 
+static int simplify_add(struct instruction *insn)
+{
+	pseudo_t src2 = insn->src2;
+	struct instruction *def;
+
+	switch (DEF_OPCODE(def, src2)) {
+	case OP_NEG:				// (x + -y) --> (x - y)
+		insn->opcode = OP_SUB;
+		return replace_pseudo(insn, &insn->src2, def->src);
+	}
+
+	return 0;
+}
+
 static int simplify_sub(struct instruction *insn)
 {
 	pseudo_t src2 = insn->src2;
@@ -1832,8 +1846,8 @@ 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_ADD:
 	case OP_MUL:
 	case OP_AND:
 	case OP_OR:
diff --git a/validation/optim/simplify-add-neg.c b/validation/optim/simplify-add-neg.c
index 19b64b096567..c24b8e19e5c3 100644
--- a/validation/optim/simplify-add-neg.c
+++ b/validation/optim/simplify-add-neg.c
@@ -3,7 +3,6 @@ int add_neg(int x, int y) { return x + -y; }
 /*
  * check-name: simplify-add-neg
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: sub\\..*%arg1, %arg2
-- 
2.28.0

[PATCH 16/22] add: simplify (-x + y) --> (y - x)

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                          | 8 ++++++++
 validation/optim/simplify-neg-add.c | 1 -
 2 files changed, 8 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index f8a0ba726561..187d4fc0c9ab 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1360,9 +1360,17 @@ static int simplify_associative_binop(struct instruction *insn)
 
 static int simplify_add(struct instruction *insn)
 {
+	pseudo_t src1 = insn->src1;
 	pseudo_t src2 = insn->src2;
 	struct instruction *def;
 
+	switch (DEF_OPCODE(def, src1)) {
+	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);
+	}
+
 	switch (DEF_OPCODE(def, src2)) {
 	case OP_NEG:				// (x + -y) --> (x - y)
 		insn->opcode = OP_SUB;
diff --git a/validation/optim/simplify-neg-add.c b/validation/optim/simplify-neg-add.c
index 66a820f28069..6223b4f98f3b 100644
--- a/validation/optim/simplify-neg-add.c
+++ b/validation/optim/simplify-neg-add.c
@@ -3,7 +3,6 @@ int neg_add(int x, int y) { return -x + y; }
 /*
  * check-name: simplify-neg-add
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: sub\\..*%arg2, %arg1
-- 
2.28.0

[PATCH 17/22] sub: simplify (x + y) - x --> y

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                                | 8 ++++++++
 validation/optim/simplify-same-add-subl.c | 1 -
 2 files changed, 8 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 187d4fc0c9ab..cb401d8fac9f 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1382,9 +1382,17 @@ static int simplify_add(struct instruction *insn)
 
 static int simplify_sub(struct instruction *insn)
 {
+	pseudo_t src1 = insn->src1;
 	pseudo_t src2 = insn->src2;
 	struct instruction *def;
 
+	switch (DEF_OPCODE(def, src1)) {
+	case OP_ADD:
+		if (def->src1 == src2)		// (x + y) - x --> y
+			return replace_with_pseudo(insn, def->src2);
+		break;
+	}
+
 	switch (DEF_OPCODE(def, src2)) {
 	case OP_NEG:				// (x - -y) --> (x + y)
 		insn->opcode = OP_ADD;
diff --git a/validation/optim/simplify-same-add-subl.c b/validation/optim/simplify-same-add-subl.c
index 1f17ef0b968e..394e7dc5a404 100644
--- a/validation/optim/simplify-same-add-subl.c
+++ b/validation/optim/simplify-same-add-subl.c
@@ -3,7 +3,6 @@ int add_subl(int x, int y) { return (x + y) - x; }
 /*
  * check-name: simplify-same-add-subl
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-start
 add_subl:
-- 
2.28.0

[PATCH 18/22] sub: simplify (x + y) - y --> x

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                                | 2 ++
 validation/optim/simplify-same-add-subr.c | 1 -
 2 files changed, 2 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index cb401d8fac9f..08b706ca8f41 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1390,6 +1390,8 @@ static int simplify_sub(struct instruction *insn)
 	case OP_ADD:
 		if (def->src1 == src2)		// (x + y) - x --> y
 			return replace_with_pseudo(insn, def->src2);
+		if (def->src2 == src2)		// (x + y) - y --> x
+			return replace_with_pseudo(insn, def->src1);
 		break;
 	}
 
diff --git a/validation/optim/simplify-same-add-subr.c b/validation/optim/simplify-same-add-subr.c
index e8540703ee7d..071021c485d7 100644
--- a/validation/optim/simplify-same-add-subr.c
+++ b/validation/optim/simplify-same-add-subr.c
@@ -3,7 +3,6 @@ int add_subr(int x, int y) { return (x + y) - y; }
 /*
  * check-name: simplify-same-add-subr
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-start
 add_subr:
-- 
2.28.0

[PATCH 19/22] sub: simplify x - (x + y) --> -y

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                                | 4 ++++
 validation/optim/simplify-same-subl-add.c | 1 -
 2 files changed, 4 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 08b706ca8f41..48bf48d29f9a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1396,6 +1396,10 @@ static int simplify_sub(struct instruction *insn)
 	}
 
 	switch (DEF_OPCODE(def, src2)) {
+	case OP_ADD:
+		if (src1 == def->src1)		// x - (x + z) --> -z
+			return replace_with_unop(insn, OP_NEG, def->src2);
+		break;
 	case OP_NEG:				// (x - -y) --> (x + y)
 		insn->opcode = OP_ADD;
 		return replace_pseudo(insn, &insn->src2, def->src);
diff --git a/validation/optim/simplify-same-subl-add.c b/validation/optim/simplify-same-subl-add.c
index dbc0fe97f126..e7ae08092556 100644
--- a/validation/optim/simplify-same-subl-add.c
+++ b/validation/optim/simplify-same-subl-add.c
@@ -3,7 +3,6 @@ int subl_add(int x, int y) { return x - (x + y); }
 /*
  * check-name: simplify-same-subl-add
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: neg\\..* %arg2
-- 
2.28.0

[PATCH 20/22] sub: simplify x - (y + x) --> -y

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                                | 2 ++
 validation/optim/simplify-same-subr-add.c | 1 -
 2 files changed, 2 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 48bf48d29f9a..68ee6ed015c1 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1399,6 +1399,8 @@ static int simplify_sub(struct instruction *insn)
 	case OP_ADD:
 		if (src1 == def->src1)		// x - (x + z) --> -z
 			return replace_with_unop(insn, OP_NEG, def->src2);
+		if (src1 == def->src2)		// x - (y + x) --> -y
+			return replace_with_unop(insn, OP_NEG, def->src1);
 		break;
 	case OP_NEG:				// (x - -y) --> (x + y)
 		insn->opcode = OP_ADD;
diff --git a/validation/optim/simplify-same-subr-add.c b/validation/optim/simplify-same-subr-add.c
index bafd2643bfd0..950c55f67c24 100644
--- a/validation/optim/simplify-same-subr-add.c
+++ b/validation/optim/simplify-same-subr-add.c
@@ -3,7 +3,6 @@ int subr_add(int x, int y) { return x - (y + x); }
 /*
  * check-name: simplify-same-subr-add
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: neg\\..* %arg2
-- 
2.28.0

[PATCH 21/22] sub: simplify (x - y) + y --> x

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                                | 5 +++++
 validation/optim/simplify-same-sub-addl.c | 1 -
 2 files changed, 5 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 68ee6ed015c1..65fca35099a6 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1369,6 +1369,11 @@ static int simplify_add(struct instruction *insn)
 		switch_pseudo(insn, &insn->src1, insn, &insn->src2);
 		insn->opcode = OP_SUB;
 		return replace_pseudo(insn, &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)) {
diff --git a/validation/optim/simplify-same-sub-addl.c b/validation/optim/simplify-same-sub-addl.c
index 78f217399e50..56b6fcc24e9d 100644
--- a/validation/optim/simplify-same-sub-addl.c
+++ b/validation/optim/simplify-same-sub-addl.c
@@ -3,7 +3,6 @@ int foo(int x, int y) { return (x - y) + y; }
 /*
  * check-name: simplify-same-sub-addl
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: ret\\..*%arg1
-- 
2.28.0

[PATCH 22/22] sub: simplify x + (y - x) --> y

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                                | 4 ++++
 validation/optim/simplify-same-addl-sub.c | 1 -
 2 files changed, 4 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 65fca35099a6..6caf6cbcf918 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1380,6 +1380,10 @@ static int simplify_add(struct instruction *insn)
 	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;
diff --git a/validation/optim/simplify-same-addl-sub.c b/validation/optim/simplify-same-addl-sub.c
index 51d2b07966f4..9cca1d12ff92 100644
--- a/validation/optim/simplify-same-addl-sub.c
+++ b/validation/optim/simplify-same-addl-sub.c
@@ -3,7 +3,6 @@ int foo(int x, int y) { return x + (y - x); }
 /*
  * check-name: simplify-same-addl-sub
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-contains: ret\\..*%arg2
-- 
2.28.0