From fbd81ed45d5889db28c9d60696048a97dc0ca8cb Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Thu, 26 Nov 2020 22:38:21 +0100 Subject: add testscases for some factorization of distributive operations 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 --- 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 (limited to 'validation/optim') diff --git a/validation/optim/fact-add-mul.c b/validation/optim/fact-add-mul.c new file mode 100644 index 00000000..48c3d656 --- /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 00000000..f2a78edd --- /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 00000000..40175021 --- /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 00000000..7af89df1 --- /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 00000000..07fdf806 --- /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 00000000..905cbf4a --- /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 00000000..81fcda85 --- /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 + */ -- cgit 1.2.3-korg From 7d385de8172a961c7a48ca974442b5227ac62f8e Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Wed, 25 Nov 2020 20:43:52 +0100 Subject: 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 --- 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(-) (limited to 'validation/optim') 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 -- cgit 1.2.3-korg From 90c1d15708d44c59046568592abcad8bdd1de126 Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Wed, 25 Nov 2020 20:45:15 +0100 Subject: factorize SHIFT(x, s) OP SHIFT(y, s) into SHIFT((x OP y), s) Factorize bitwise OPs of shifts with identical counts. Signed-off-by: Luc Van Oostenryck --- 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(-) (limited to 'validation/optim') diff --git a/simplify.c b/simplify.c index 319112a9..89a064b9 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 40175021..e9eb9cce 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 07fdf806..5fa91eb5 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 81fcda85..5fb228bd 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 -- cgit 1.2.3-korg From 3aaa16eac7f07302bcf3d733aeee901d378b7e9d Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Thu, 26 Nov 2020 22:38:21 +0100 Subject: add testscases for 'bits translation' optimization Add some testcase related to the simplification of expressions like: if (val1 & BIT1) val2 |= BIT2; into val2 |= (val1 & BIT1) {SHL/LSR} |BIT2-BIT1|; Signed-off-by: Luc Van Oostenryck --- validation/optim/fact-select01.c | 26 ++++++++++++++++++++++++++ validation/optim/select-and-shift.c | 18 ++++++++++++++++++ 2 files changed, 44 insertions(+) create mode 100644 validation/optim/fact-select01.c create mode 100644 validation/optim/select-and-shift.c (limited to 'validation/optim') diff --git a/validation/optim/fact-select01.c b/validation/optim/fact-select01.c new file mode 100644 index 00000000..ef4e5e89 --- /dev/null +++ b/validation/optim/fact-select01.c @@ -0,0 +1,26 @@ +int add_yx_y(int p, int x, int y) { return (p ? (y+x) : y) == ((p ? x : 0) + y); } +int add_xy_y(int p, int y, int x) { return (p ? (x+y) : y) == ((p ? x : 0) + y); } +int add_xy_x(int p, int x, int y) { return (p ? (x+y) : x) == ((p ? y : 0) + x); } +int add_yx_x(int p, int y, int x) { return (p ? (y+x) : x) == ((p ? y : 0) + x); } +int add_y_yx(int p, int x, int y) { return (p ? y : (y+x)) == ((p ? 0 : x) + y); } + +int ior_yx_y(int p, int x, int y) { return (p ? (y|x) : y) == ((p ? x : 0) | y); } +int ior_xy_y(int p, int y, int x) { return (p ? (x|y) : y) == ((p ? x : 0) | y); } +int ior_xy_x(int p, int x, int y) { return (p ? (x|y) : x) == ((p ? y : 0) | x); } +int ior_yx_x(int p, int y, int x) { return (p ? (y|x) : x) == ((p ? y : 0) | x); } +int ior_y_yx(int p, int x, int y) { return (p ? y : (y|x)) == ((p ? 0 : x) | y); } + +int xor_yx_y(int p, int x, int y) { return (p ? (y^x) : y) == ((p ? x : 0) ^ y); } +int xor_xy_y(int p, int y, int x) { return (p ? (x^y) : y) == ((p ? x : 0) ^ y); } +int xor_xy_x(int p, int x, int y) { return (p ? (x^y) : x) == ((p ? y : 0) ^ x); } +int xor_yx_x(int p, int y, int x) { return (p ? (y^x) : x) == ((p ? y : 0) ^ x); } +int xor_y_yx(int p, int x, int y) { return (p ? y : (y^x)) == ((p ? 0 : x) ^ y); } + +/* + * check-name: fact-select01 + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ diff --git a/validation/optim/select-and-shift.c b/validation/optim/select-and-shift.c new file mode 100644 index 00000000..fbe044c7 --- /dev/null +++ b/validation/optim/select-and-shift.c @@ -0,0 +1,18 @@ +#define S1 2 +#define S2 5 +#define S (S2 - S1) + +#define A (1 << S1) +#define B (1 << S2) + +int foo(int p) { return ((p & A) ? B : 0) == ((((unsigned)p) & A) << S); } +int bar(int p) { return ((p & B) ? A : 0) == ((((unsigned)p) & B) >> S); } + +/* + * check-name: select-and-shift + * check-command: test-linearize -Wno-decl $file + * check-known-to-fail + * + * check-output-ignore + * check-output-returns: 1 + */ -- cgit 1.2.3-korg From 2eb69efa7f912e604092b46d7b12a9bce3ea9995 Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Wed, 25 Nov 2020 22:46:22 +0100 Subject: factorize SEL(x, OP(y,z), y) into OP(SEL(x, z, 0), y) 'Factorize' and expression like: x ? (y | z) : y; into (x ? z : 0) | y; and some positional variants as well as replacing '|' by '+' or '^'. Note: it's not very clear if this is really an improvement but it allows some very nice simplification of 'bits translations'. Note: the same can be done for others operations, for example it can be done for '&' if '0' (the neuter value for '|', '+' and '^') by '~0' (same with '*' and '1'). Signed-off-by: Luc Van Oostenryck --- simplify.c | 40 ++++++++++++++++++++++++++++++++++++++++ validation/optim/fact-select01.c | 1 - 2 files changed, 40 insertions(+), 1 deletion(-) (limited to 'validation/optim') diff --git a/simplify.c b/simplify.c index 89a064b9..d729b390 100644 --- a/simplify.c +++ b/simplify.c @@ -554,6 +554,16 @@ static inline int swap_insn(struct instruction *out, struct instruction *in, pse return replace_insn_pair(out, in->opcode, in, out->opcode, a, b, c); } +/// +// create an instruction pair OUT(SELECT(a, b, c), d) +static int swap_select(struct instruction *out, struct instruction *in, pseudo_t a, pseudo_t b, pseudo_t c, pseudo_t d) +{ + use_pseudo(in, c, &in->src3); + swap_insn(out, in, a, b, d); + kill_use(&out->src3); + return REPEAT_CSE; +} + static inline int def_opcode(pseudo_t p) { if (p->type != PSEUDO_REG) @@ -2254,6 +2264,36 @@ static int simplify_select(struct instruction *insn) } break; } + + switch (DEF_OPCODE(def, src1)) { + case OP_ADD: case OP_OR: case OP_XOR: + if ((def->src1 == src2) && can_move_to(cond, def)) { + // SEL(x, OP(y,z), y) --> OP(SEL(x, z, 0), y) + swap_select(insn, def, cond, def->src2, value_pseudo(0), src2); + return REPEAT_CSE; + } + if ((def->src2 == src2) && can_move_to(cond, def)) { + // SEL(x, OP(z,y), y) --> OP(SEL(x, z, 0), y) + swap_select(insn, def, cond, def->src1, value_pseudo(0), src2); + return REPEAT_CSE; + } + break; + } + + switch (DEF_OPCODE(def, src2)) { + case OP_ADD: case OP_OR: case OP_XOR: + if ((def->src1 == src1) && can_move_to(cond, def)) { + // SEL(x, y, OP(y,z)) --> OP(SEL(x, 0, z), y) + swap_select(insn, def, cond, value_pseudo(0), def->src2, src1); + return REPEAT_CSE; + } + if ((def->src2 == src1) && can_move_to(cond, def)) { + // SEL(x, y, OP(z,y)) --> OP(SEL(x, 0, z), y) + swap_select(insn, def, cond, value_pseudo(0), def->src1, src1); + return REPEAT_CSE; + } + break; + } return 0; } diff --git a/validation/optim/fact-select01.c b/validation/optim/fact-select01.c index ef4e5e89..9232fc90 100644 --- a/validation/optim/fact-select01.c +++ b/validation/optim/fact-select01.c @@ -19,7 +19,6 @@ int xor_y_yx(int p, int x, int y) { return (p ? y : (y^x)) == ((p ? 0 : x) ^ y); /* * check-name: fact-select01 * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1 -- cgit 1.2.3-korg From cafabc769e77f14e47ab44866b304e51af42c44c Mon Sep 17 00:00:00 2001 From: Luc Van Oostenryck Date: Wed, 25 Nov 2020 23:01:48 +0100 Subject: convert SEL(x & BIT1, BIT2, 0) into SHIFT(x & BIT1, S) Convert an expression like: (x & (1 << A)) ? (1 << B) : 0 into: (x & (1 << A)) << (B - A) or: (x & (1 << A)) >> (A - B) Suggested-by: Linus Torvalds Signed-off-by: Luc Van Oostenryck --- simplify.c | 15 +++++++++++++++ validation/optim/select-and-shift.c | 1 - 2 files changed, 15 insertions(+), 1 deletion(-) (limited to 'validation/optim') diff --git a/simplify.c b/simplify.c index 0d9391e2..fc64e5b7 100644 --- a/simplify.c +++ b/simplify.c @@ -2271,6 +2271,21 @@ static int simplify_select(struct instruction *insn) // both values must be non-zero return replace_with_pseudo(insn, src1); } + case OP_AND: + if (is_pow2(def->src2) && is_pow2(src1) && is_zero(src2) && insn->size == def->size && one_use(cond)) { + unsigned s1 = log2_exact(def->src2->value); + unsigned s2 = log2_exact(insn->src2->value); + unsigned shift; + + if (s1 == s2) + return replace_with_pseudo(insn, cond); + + // SEL(x & A, B, 0) --> SHIFT(x & A, S) + insn->opcode = (s1 < s2) ? OP_SHL : OP_LSR; + shift = (s1 < s2) ? (s2 - s1) : (s1 - s2); + insn->src2 = value_pseudo(shift); + return REPEAT_CSE; + } break; } diff --git a/validation/optim/select-and-shift.c b/validation/optim/select-and-shift.c index fbe044c7..5313fe4b 100644 --- a/validation/optim/select-and-shift.c +++ b/validation/optim/select-and-shift.c @@ -11,7 +11,6 @@ int bar(int p) { return ((p & B) ? A : 0) == ((((unsigned)p) & B) >> S); } /* * check-name: select-and-shift * check-command: test-linearize -Wno-decl $file - * check-known-to-fail * * check-output-ignore * check-output-returns: 1 -- cgit 1.2.3-korg