* [PATCH 1/8] add testscases for some factorization of distributive operations
2020-11-27 16:49 [PATCH 0/8] factorization of distributive operations Luc Van Oostenryck
@ 2020-11-27 16:49 ` Luc Van Oostenryck
2020-11-27 16:49 ` [PATCH 2/8] reassoc: add helper can_move_to() Luc Van Oostenryck
` (6 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Luc Van Oostenryck @ 2020-11-27 16:49 UTC (permalink / raw)
To: linux-sparse; +Cc: Luc Van Oostenryck
Add some testcases for factorizations of:
(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
and
(x << s) | (y << s) --> ((x | y) << s)
and same for &, ^, LSR and ASR.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
validation/optim/fact-add-mul.c | 28 ++++++++++++++++++++++++++++
validation/optim/fact-and-ior.c | 28 ++++++++++++++++++++++++++++
validation/optim/fact-and-shift.c | 27 +++++++++++++++++++++++++++
validation/optim/fact-ior-and.c | 28 ++++++++++++++++++++++++++++
validation/optim/fact-ior-shift.c | 27 +++++++++++++++++++++++++++
validation/optim/fact-xor-and.c | 28 ++++++++++++++++++++++++++++
validation/optim/fact-xor-shift.c | 27 +++++++++++++++++++++++++++
7 files changed, 193 insertions(+)
create mode 100644 validation/optim/fact-add-mul.c
create mode 100644 validation/optim/fact-and-ior.c
create mode 100644 validation/optim/fact-and-shift.c
create mode 100644 validation/optim/fact-ior-and.c
create mode 100644 validation/optim/fact-ior-shift.c
create mode 100644 validation/optim/fact-xor-and.c
create mode 100644 validation/optim/fact-xor-shift.c
diff --git a/validation/optim/fact-add-mul.c b/validation/optim/fact-add-mul.c
new file mode 100644
index 000000000000..48c3d656accc
--- /dev/null
+++ b/validation/optim/fact-add-mul.c
@@ -0,0 +1,28 @@
+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-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
new file mode 100644
index 000000000000..f2a78eddf41d
--- /dev/null
+++ b/validation/optim/fact-and-ior.c
@@ -0,0 +1,28 @@
+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-known-to-fail
+ *
+ * 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 000000000000..401750216b44
--- /dev/null
+++ b/validation/optim/fact-and-shift.c
@@ -0,0 +1,27 @@
+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-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
new file mode 100644
index 000000000000..7af89df1e1f0
--- /dev/null
+++ b/validation/optim/fact-ior-and.c
@@ -0,0 +1,28 @@
+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-known-to-fail
+ *
+ * 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 000000000000..07fdf80604dc
--- /dev/null
+++ b/validation/optim/fact-ior-shift.c
@@ -0,0 +1,27 @@
+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-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
new file mode 100644
index 000000000000..905cbf4ab659
--- /dev/null
+++ b/validation/optim/fact-xor-and.c
@@ -0,0 +1,28 @@
+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-known-to-fail
+ *
+ * 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 000000000000..81fcda851400
--- /dev/null
+++ b/validation/optim/fact-xor-shift.c
@@ -0,0 +1,27 @@
+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-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
--
2.29.2
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 2/8] reassoc: add helper can_move_to()
2020-11-27 16:49 [PATCH 0/8] factorization of distributive operations Luc Van Oostenryck
2020-11-27 16:49 ` [PATCH 1/8] add testscases for some " Luc Van Oostenryck
@ 2020-11-27 16:49 ` Luc Van Oostenryck
2020-11-27 16:49 ` [PATCH 3/8] add helper make_insn_pair() & swap_insn() Luc Van Oostenryck
` (5 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Luc Van Oostenryck @ 2020-11-27 16:49 UTC (permalink / raw)
To: linux-sparse; +Cc: Luc Van Oostenryck
When transforming IR expressions, it may happen that we want to
reuse an instruction and move a pseudo into it but that this pseudo
is only defined later.
Add a small help to check this: can_move_to().
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 37 +++++++++++++++++++++++++++++++++++++
1 file changed, 37 insertions(+)
diff --git a/simplify.c b/simplify.c
index de03d315ec33..d16390caed49 100644
--- a/simplify.c
+++ b/simplify.c
@@ -46,6 +46,7 @@
#include "linearize.h"
#include "flow.h"
#include "symbol.h"
+#include "flowgraph.h"
///
// Utilities
@@ -1508,6 +1509,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;
--
2.29.2
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 3/8] add helper make_insn_pair() & swap_insn()
2020-11-27 16:49 [PATCH 0/8] factorization of distributive operations Luc Van Oostenryck
2020-11-27 16:49 ` [PATCH 1/8] add testscases for some " Luc Van Oostenryck
2020-11-27 16:49 ` [PATCH 2/8] reassoc: add helper can_move_to() Luc Van Oostenryck
@ 2020-11-27 16:49 ` Luc Van Oostenryck
2020-11-27 16:49 ` [PATCH 4/8] add helper replace_binop() Luc Van Oostenryck
` (4 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Luc Van Oostenryck @ 2020-11-27 16:49 UTC (permalink / raw)
To: linux-sparse; +Cc: Luc Van Oostenryck
Add two helpers to create instruction pair OUT(IN(a, b), c).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 31 +++++++++++++++++++++++++++++++
1 file changed, 31 insertions(+)
diff --git a/simplify.c b/simplify.c
index d16390caed49..24b3dcb52428 100644
--- a/simplify.c
+++ b/simplify.c
@@ -506,6 +506,37 @@ 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);
+}
+
static inline int def_opcode(pseudo_t p)
{
if (p->type != PSEUDO_REG)
--
2.29.2
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 4/8] add helper replace_binop()
2020-11-27 16:49 [PATCH 0/8] factorization of distributive operations Luc Van Oostenryck
` (2 preceding siblings ...)
2020-11-27 16:49 ` [PATCH 3/8] add helper make_insn_pair() & swap_insn() Luc Van Oostenryck
@ 2020-11-27 16:49 ` Luc Van Oostenryck
2020-11-27 16:49 ` [PATCH 5/8] refactor simplify_add() to avoid code duplication (preparation) Luc Van Oostenryck
` (3 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Luc Van Oostenryck @ 2020-11-27 16:49 UTC (permalink / raw)
To: linux-sparse; +Cc: Luc Van Oostenryck
Add an helper to replace a binop OP(a, b) and taking care to
drop the usage of the previous operands.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 17 +++++++++++++++++
1 file changed, 17 insertions(+)
diff --git a/simplify.c b/simplify.c
index 24b3dcb52428..046bf02c6d36 100644
--- a/simplify.c
+++ b/simplify.c
@@ -497,6 +497,23 @@ static inline int replace_binop_value(struct instruction *insn, int op, long lon
return REPEAT_CSE;
}
+///
+// 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
--
2.29.2
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 5/8] refactor simplify_add() to avoid code duplication (preparation)
2020-11-27 16:49 [PATCH 0/8] factorization of distributive operations Luc Van Oostenryck
` (3 preceding siblings ...)
2020-11-27 16:49 ` [PATCH 4/8] add helper replace_binop() Luc Van Oostenryck
@ 2020-11-27 16:49 ` Luc Van Oostenryck
2020-11-27 16:49 ` [PATCH 6/8] refactor simplify_add() to avoid code duplication Luc Van Oostenryck
` (2 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Luc Van Oostenryck @ 2020-11-27 16:49 UTC (permalink / raw)
To: linux-sparse; +Cc: Luc Van Oostenryck
Do some refactoring in simplify_add() to prepare the next patch
which will avoid some code duplication there.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 7 ++-----
1 file changed, 2 insertions(+), 5 deletions(-)
diff --git a/simplify.c b/simplify.c
index 046bf02c6d36..82ff1242bb0e 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1628,9 +1628,7 @@ static int simplify_add(struct instruction *insn)
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);
+ return replace_binop(insn, OP_SUB, &insn->src1, src2, &insn->src2, def->src);
case OP_SUB:
if (def->src2 == src2) // (x - y) + y --> x
@@ -1640,8 +1638,7 @@ static int simplify_add(struct instruction *insn)
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 replace_binop(insn, OP_SUB, &insn->src1, src1, &insn->src2, def->src);
case OP_SUB:
if (src1 == def->src2) // x + (y - x) --> y
return replace_with_pseudo(insn, def->src1);
--
2.29.2
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 6/8] refactor simplify_add() to avoid code duplication
2020-11-27 16:49 [PATCH 0/8] factorization of distributive operations Luc Van Oostenryck
` (4 preceding siblings ...)
2020-11-27 16:49 ` [PATCH 5/8] refactor simplify_add() to avoid code duplication (preparation) Luc Van Oostenryck
@ 2020-11-27 16:49 ` Luc Van Oostenryck
2020-11-27 16:49 ` [PATCH 7/8] factorize (x OP1 z) OP2 (y OP1 z) into (x OP2 y) OP1 z Luc Van Oostenryck
2020-11-27 16:49 ` [PATCH 8/8] factorize SHIFT(x, s) OP SHIFT(y, s) into SHIFT((x OP y), s) Luc Van Oostenryck
7 siblings, 0 replies; 9+ messages in thread
From: Luc Van Oostenryck @ 2020-11-27 16:49 UTC (permalink / raw)
To: linux-sparse; +Cc: Luc Van Oostenryck
Do some refactoring in simplify_add() to avoid some code
duplication there and better handle generic transforms
that need to be applied on both operands.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 22 +++++++++-------------
1 file changed, 9 insertions(+), 13 deletions(-)
diff --git a/simplify.c b/simplify.c
index 82ff1242bb0e..5174a903dfd6 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1620,11 +1620,11 @@ 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 *def;
+ pseudo_t src1 = *p1;
+ pseudo_t src2 = *p2;
switch (DEF_OPCODE(def, src1)) {
case OP_NEG: // (-x + y) --> (y - x)
@@ -1635,19 +1635,15 @@ static int simplify_add(struct instruction *insn)
return replace_with_pseudo(insn, def->src1);
break;
}
-
- switch (DEF_OPCODE(def, src2)) {
- case OP_NEG: // (x + -y) --> (x - y)
- return replace_binop(insn, OP_SUB, &insn->src1, src1, &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;
--
2.29.2
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 7/8] factorize (x OP1 z) OP2 (y OP1 z) into (x OP2 y) OP1 z
2020-11-27 16:49 [PATCH 0/8] factorization of distributive operations Luc Van Oostenryck
` (5 preceding siblings ...)
2020-11-27 16:49 ` [PATCH 6/8] refactor simplify_add() to avoid code duplication Luc Van Oostenryck
@ 2020-11-27 16:49 ` Luc Van Oostenryck
2020-11-27 16:49 ` [PATCH 8/8] factorize SHIFT(x, s) OP SHIFT(y, s) into SHIFT((x OP y), s) Luc Van Oostenryck
7 siblings, 0 replies; 9+ messages in thread
From: Luc Van Oostenryck @ 2020-11-27 16:49 UTC (permalink / raw)
To: linux-sparse; +Cc: Luc Van Oostenryck
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>
---
simplify.c | 78 +++++++++++++++++++++++++++++++++
validation/optim/fact-add-mul.c | 1 -
validation/optim/fact-and-ior.c | 1 -
validation/optim/fact-ior-and.c | 1 -
validation/optim/fact-xor-and.c | 1 -
5 files changed, 78 insertions(+), 4 deletions(-)
diff --git a/simplify.c b/simplify.c
index 5174a903dfd6..319112a90b7b 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 48c3d656accc..9da6d71c9a7d 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 f2a78eddf41d..96466616d877 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 7af89df1e1f0..a6ad3c45515d 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 905cbf4ab659..62232b29da40 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
--
2.29.2
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 8/8] factorize SHIFT(x, s) OP SHIFT(y, s) into SHIFT((x OP y), s)
2020-11-27 16:49 [PATCH 0/8] factorization of distributive operations Luc Van Oostenryck
` (6 preceding siblings ...)
2020-11-27 16:49 ` [PATCH 7/8] factorize (x OP1 z) OP2 (y OP1 z) into (x OP2 y) OP1 z Luc Van Oostenryck
@ 2020-11-27 16:49 ` Luc Van Oostenryck
7 siblings, 0 replies; 9+ messages in thread
From: Luc Van Oostenryck @ 2020-11-27 16:49 UTC (permalink / raw)
To: linux-sparse; +Cc: Luc Van Oostenryck
Factorize bitwise OPs of shifts with identical counts.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
simplify.c | 27 +++++++++++++++++++++++++++
validation/optim/fact-and-shift.c | 1 -
validation/optim/fact-ior-shift.c | 1 -
validation/optim/fact-xor-shift.c | 1 -
4 files changed, 27 insertions(+), 3 deletions(-)
diff --git a/simplify.c b/simplify.c
index 319112a90b7b..89a064b93e85 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1754,6 +1754,15 @@ static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_
}
}
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;
}
@@ -1799,6 +1808,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;
}
@@ -1844,6 +1862,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;
}
diff --git a/validation/optim/fact-and-shift.c b/validation/optim/fact-and-shift.c
index 401750216b44..e9eb9cceef95 100644
--- a/validation/optim/fact-and-shift.c
+++ b/validation/optim/fact-and-shift.c
@@ -20,7 +20,6 @@ sint fact_and_asr(sint a, sint b, sint s)
/*
* check-name: fact-and-shift
* 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-shift.c b/validation/optim/fact-ior-shift.c
index 07fdf80604dc..5fa91eb5cfc2 100644
--- a/validation/optim/fact-ior-shift.c
+++ b/validation/optim/fact-ior-shift.c
@@ -20,7 +20,6 @@ sint fact_ior_asr(sint a, sint b, sint s)
/*
* check-name: fact-ior-shift
* 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-shift.c b/validation/optim/fact-xor-shift.c
index 81fcda851400..5fb228bd80a1 100644
--- a/validation/optim/fact-xor-shift.c
+++ b/validation/optim/fact-xor-shift.c
@@ -20,7 +20,6 @@ sint fact_xor_asr(sint a, sint b, sint s)
/*
* check-name: fact-xor-shift
* check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
*
* check-output-ignore
* check-output-returns: 1
--
2.29.2
^ permalink raw reply related [flat|nested] 9+ messages in thread