[PATCH 0/7] simplify logical negation

[PATCH 0/7] simplify logical negation

[Luc Van Oostenryck]

This series contains simplifications for tautologies and
contradictions involving logical negation, like (~x & x)
or ((x > y) | (x <= y)).

As a bonus (but needed for these simplifications), now
PSEUDO_REGs and PSEUDO_ARGs are also taken in account when
checking if operands are in canonical order, which creates
a few CSE opportunities of its own.


Luc Van Oostenryck (7):
  not: add testcases for canonicalization & simplification of negations
  canon: put PSEUDO_ARGs in canonical order too
  canon: put PSEUDO_REGs in canonical order too
  canon: simplify calculation of canonical order
  opcode: add helpers opcode_negate() & opcode_swap()
  not: simplify (~x {&,|,^} x) --> {0,~0,~0}
  not: simplify ((x cmp y) {&,|,^} (x !cmp y)) --> {0,1,1}

 linearize.h                         |   4 +-
 opcode.h                            |  10 +++
 simplify.c                          | 118 +++++++++++++++++++++++++---
 validation/linear/pointer-arith32.c |  12 +--
 validation/linear/pointer-arith64.c |  10 +--
 validation/optim/canonical-arg.c    |  20 +++++
 validation/optim/canonical-not.c    |   9 +++
 validation/optim/cse-arg01.c        |   9 +++
 validation/optim/cse-not01.c        |  11 +++
 validation/optim/cse-not02.c        |  11 +++
 validation/optim/cse-reg01.c        |   9 +++
 11 files changed, 200 insertions(+), 23 deletions(-)
 create mode 100644 validation/optim/canonical-arg.c
 create mode 100644 validation/optim/canonical-not.c
 create mode 100644 validation/optim/cse-arg01.c
 create mode 100644 validation/optim/cse-not01.c
 create mode 100644 validation/optim/cse-not02.c
 create mode 100644 validation/optim/cse-reg01.c

-- 
2.29.2

[PATCH 1/7] not: add testcases for canonicalization & simplification of negations

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/canonical-arg.c | 20 ++++++++++++++++++++
 validation/optim/canonical-not.c |  9 +++++++++
 validation/optim/cse-arg01.c     | 10 ++++++++++
 validation/optim/cse-not01.c     | 12 ++++++++++++
 validation/optim/cse-not02.c     | 12 ++++++++++++
 validation/optim/cse-reg01.c     | 10 ++++++++++
 6 files changed, 73 insertions(+)
 create mode 100644 validation/optim/canonical-arg.c
 create mode 100644 validation/optim/canonical-not.c
 create mode 100644 validation/optim/cse-arg01.c
 create mode 100644 validation/optim/cse-not01.c
 create mode 100644 validation/optim/cse-not02.c
 create mode 100644 validation/optim/cse-reg01.c

diff --git a/validation/optim/canonical-arg.c b/validation/optim/canonical-arg.c
new file mode 100644
index 000000000000..a8ecc9bd0083
--- /dev/null
+++ b/validation/optim/canonical-arg.c
@@ -0,0 +1,20 @@
+int def(void);
+
+int canon_arg_arg(int a, int b)
+{
+	return (a + b) == (b + a);
+}
+
+int canon_arg_reg(int a)
+{
+	int b = def();
+	return (a + b) == (b + a);
+}
+
+/*
+ * check-name: canonical-arg
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/canonical-not.c b/validation/optim/canonical-not.c
new file mode 100644
index 000000000000..9698590fd245
--- /dev/null
+++ b/validation/optim/canonical-not.c
@@ -0,0 +1,9 @@
+int canon_not(int a, int b) { return (a & ~b) == (~b & a); }
+
+/*
+ * check-name: canonical-not
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cse-arg01.c b/validation/optim/cse-arg01.c
new file mode 100644
index 000000000000..c3f2963ffdeb
--- /dev/null
+++ b/validation/optim/cse-arg01.c
@@ -0,0 +1,10 @@
+int foo(int a, int b) { return (a < b) == (b > a); }
+
+/*
+ * check-name: cse-arg01
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cse-not01.c b/validation/optim/cse-not01.c
new file mode 100644
index 000000000000..f87123f14f13
--- /dev/null
+++ b/validation/optim/cse-not01.c
@@ -0,0 +1,12 @@
+int and(int a) { return (~a & a) ==  0; }
+int ior(int a) { return (~a | a) == ~0; }
+int xor(int a) { return (~a ^ a) == ~0; }
+
+/*
+ * check-name: cse-not01
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cse-not02.c b/validation/optim/cse-not02.c
new file mode 100644
index 000000000000..aa54a375a9ea
--- /dev/null
+++ b/validation/optim/cse-not02.c
@@ -0,0 +1,12 @@
+int and(int a, int b) { return ((a == b) & (a != b)) == 0; }
+int ior(int a, int b) { return ((a == b) | (a != b)) == 1; }
+int xor(int a, int b) { return ((a == b) ^ (a != b)) == 1; }
+
+/*
+ * check-name: cse-not02
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/cse-reg01.c b/validation/optim/cse-reg01.c
new file mode 100644
index 000000000000..938858f4649b
--- /dev/null
+++ b/validation/optim/cse-reg01.c
@@ -0,0 +1,10 @@
+int foo(int a, int b) { int x = a + b, y = ~b; return (x < y) == (y > x); }
+
+/*
+ * check-name: cse-reg01
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
-- 
2.29.2

[PATCH 2/7] canon: put PSEUDO_ARGs in canonical order too

[Luc Van Oostenryck]

Currently, only binops containing PSEUDO_VAL or PSEUDO_SYM were
put in canonical order. This means that binops containing only
PSEUDO_ARGs or PSEUDO_REGs are not ordered. This is not directly
a problem for CSE because commutativity is taken in account but:
* more combination need to be checked during simplification
* 'anti-commutative' operations like (a > b) & (b < a) are not
  recognized as such.

So, as a first step, also take PSEUDO_ARGs in account when checking
if operands are in canonical order.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                          |  3 +++
 validation/linear/pointer-arith32.c | 12 ++++++------
 validation/linear/pointer-arith64.c | 10 +++++-----
 validation/optim/cse-arg01.c        |  1 -
 4 files changed, 14 insertions(+), 12 deletions(-)

diff --git a/simplify.c b/simplify.c
index a0e23d6de01f..c809b832afeb 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1471,6 +1471,9 @@ static int canonical_order(pseudo_t p1, pseudo_t p2)
 	if (p1->type == PSEUDO_SYM)
 		return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
 
+	if (p1->type == PSEUDO_ARG)
+		return (p2->type == PSEUDO_ARG && p1->nr <= p2->nr) || p2->type == PSEUDO_VAL || p2->type == PSEUDO_SYM;
+
 	return 1;
 }
 
diff --git a/validation/linear/pointer-arith32.c b/validation/linear/pointer-arith32.c
index 531fd2324911..c0163a6f528b 100644
--- a/validation/linear/pointer-arith32.c
+++ b/validation/linear/pointer-arith32.c
@@ -42,7 +42,7 @@ cps:
 .L0:
 	<entry-point>
 	sext.32     %r2 <- (16) %arg2
-	add.32      %r5 <- %arg1, %r2
+	add.32      %r5 <- %r2, %arg1
 	ret.32      %r5
 
 
@@ -51,7 +51,7 @@ ipss:
 	<entry-point>
 	sext.32     %r10 <- (16) %arg2
 	mul.32      %r11 <- %r10, $4
-	add.32      %r14 <- %arg1, %r11
+	add.32      %r14 <- %r11, %arg1
 	ret.32      %r14
 
 
@@ -60,7 +60,7 @@ ipus:
 	<entry-point>
 	zext.32     %r19 <- (16) %arg2
 	mul.32      %r20 <- %r19, $4
-	add.32      %r23 <- %arg1, %r20
+	add.32      %r23 <- %r20, %arg1
 	ret.32      %r23
 
 
@@ -68,7 +68,7 @@ cpq:
 .L6:
 	<entry-point>
 	trunc.32    %r28 <- (64) %arg2
-	add.32      %r31 <- %arg1, %r28
+	add.32      %r31 <- %r28, %arg1
 	ret.32      %r31
 
 
@@ -77,7 +77,7 @@ ipq_ref:
 	<entry-point>
 	trunc.32    %r37 <- (64) %arg2
 	mul.32      %r38 <- %r37, $4
-	add.32      %r39 <- %arg1, %r38
+	add.32      %r39 <- %r38, %arg1
 	ret.32      %r39
 
 
@@ -86,7 +86,7 @@ ipq:
 	<entry-point>
 	trunc.32    %r43 <- (64) %arg2
 	mul.32      %r44 <- %r43, $4
-	add.32      %r47 <- %arg1, %r44
+	add.32      %r47 <- %r44, %arg1
 	ret.32      %r47
 
 
diff --git a/validation/linear/pointer-arith64.c b/validation/linear/pointer-arith64.c
index dad10331b297..7f1aac56bfc2 100644
--- a/validation/linear/pointer-arith64.c
+++ b/validation/linear/pointer-arith64.c
@@ -35,7 +35,7 @@ cps:
 .L0:
 	<entry-point>
 	sext.64     %r2 <- (16) %arg2
-	add.64      %r5 <- %arg1, %r2
+	add.64      %r5 <- %r2, %arg1
 	ret.64      %r5
 
 
@@ -44,7 +44,7 @@ ipss:
 	<entry-point>
 	sext.64     %r10 <- (16) %arg2
 	mul.64      %r11 <- %r10, $4
-	add.64      %r14 <- %arg1, %r11
+	add.64      %r14 <- %r11, %arg1
 	ret.64      %r14
 
 
@@ -53,7 +53,7 @@ ipus:
 	<entry-point>
 	zext.64     %r19 <- (16) %arg2
 	mul.64      %r20 <- %r19, $4
-	add.64      %r23 <- %arg1, %r20
+	add.64      %r23 <- %r20, %arg1
 	ret.64      %r23
 
 
@@ -62,7 +62,7 @@ ipsi:
 	<entry-point>
 	sext.64     %r28 <- (32) %arg2
 	mul.64      %r29 <- %r28, $4
-	add.64      %r32 <- %arg1, %r29
+	add.64      %r32 <- %r29, %arg1
 	ret.64      %r32
 
 
@@ -71,7 +71,7 @@ ipui:
 	<entry-point>
 	zext.64     %r37 <- (32) %arg2
 	mul.64      %r38 <- %r37, $4
-	add.64      %r41 <- %arg1, %r38
+	add.64      %r41 <- %r38, %arg1
 	ret.64      %r41
 
 
diff --git a/validation/optim/cse-arg01.c b/validation/optim/cse-arg01.c
index c3f2963ffdeb..3e3e141aa1fb 100644
--- a/validation/optim/cse-arg01.c
+++ b/validation/optim/cse-arg01.c
@@ -3,7 +3,6 @@ int foo(int a, int b) { return (a < b) == (b > a); }
 /*
  * check-name: cse-arg01
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2

[PATCH 3/7] canon: put PSEUDO_REGs in canonical order too

[Luc Van Oostenryck]

Currently, only binops containing PSEUDO_VAL, SYM or ARG were
put in canonical order. This means that binops containing only
PSEUDO_REGs are not ordered. This is not directly
a problem for CSE because commutativity is taken in account but:
* more combination need to be checked during simplification
* 'anti-commutative' operations like (a > b) & (b < a) are not
  recognized as such.

So, take PSEUDO_REGs in account when checking if operands
are in canonical order.

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

diff --git a/simplify.c b/simplify.c
index c809b832afeb..ee485798148b 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1474,6 +1474,9 @@ static int canonical_order(pseudo_t p1, pseudo_t p2)
 	if (p1->type == PSEUDO_ARG)
 		return (p2->type == PSEUDO_ARG && p1->nr <= p2->nr) || p2->type == PSEUDO_VAL || p2->type == PSEUDO_SYM;
 
+	if (p1->type == PSEUDO_REG)
+		return (p2->type == PSEUDO_REG && p1->nr <= p2->nr) || p2->type == PSEUDO_VAL || p2->type == PSEUDO_SYM || p2->type == PSEUDO_ARG;
+
 	return 1;
 }
 
diff --git a/validation/optim/cse-reg01.c b/validation/optim/cse-reg01.c
index 938858f4649b..3ea283d35368 100644
--- a/validation/optim/cse-reg01.c
+++ b/validation/optim/cse-reg01.c
@@ -3,7 +3,6 @@ int foo(int a, int b) { int x = a + b, y = ~b; return (x < y) == (y > x); }
 /*
  * check-name: cse-reg01
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2

[PATCH 4/7] canon: simplify calculation of canonical order

[Luc Van Oostenryck]

The calculation of the canonical order is currently somehow
complicated.

Fix this by reordering the definition of the different type of
pseudos so that they are already in canonical order and just
comparing the types to determine the order.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h |  4 ++--
 simplify.c  | 40 +++++++++++++++++++++++++++-------------
 2 files changed, 29 insertions(+), 15 deletions(-)

diff --git a/linearize.h b/linearize.h
index 31c754e200c2..2c548d43526f 100644
--- a/linearize.h
+++ b/linearize.h
@@ -24,11 +24,11 @@ DECLARE_PTRMAP(phi_map, struct symbol *, pseudo_t);
 enum pseudo_type {
 	PSEUDO_VOID,
 	PSEUDO_UNDEF,
+	PSEUDO_PHI,
 	PSEUDO_REG,
+	PSEUDO_ARG,
 	PSEUDO_SYM,
 	PSEUDO_VAL,
-	PSEUDO_ARG,
-	PSEUDO_PHI,
 };
 
 struct pseudo {
diff --git a/simplify.c b/simplify.c
index ee485798148b..203472972bca 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1462,22 +1462,36 @@ static int switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instru
 	return REPEAT_CSE;
 }
 
+///
+// check if the given pseudos are in canonical order
+//
+// The canonical order is VOID < UNDEF < PHI < REG < ARG < SYM < VAL
+// The rationale is:
+//	* VALs at right (they don't need a definition)
+//	* REGs at left (they need a defining instruction)
+//	* SYMs & ARGs between REGs & VALs
+//	* REGs & ARGs are ordered between themselves by their internal number
+//	* SYMs are ordered between themselves by address
+//	* VOID, UNDEF and PHI are uninteresting (but VOID should have type 0)
 static int canonical_order(pseudo_t p1, pseudo_t p2)
 {
-	/* symbol/constants on the right */
-	if (p1->type == PSEUDO_VAL)
-		return p2->type == PSEUDO_VAL;
-
-	if (p1->type == PSEUDO_SYM)
-		return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
-
-	if (p1->type == PSEUDO_ARG)
-		return (p2->type == PSEUDO_ARG && p1->nr <= p2->nr) || p2->type == PSEUDO_VAL || p2->type == PSEUDO_SYM;
+	int t1 = p1->type;
+	int t2 = p2->type;
 
-	if (p1->type == PSEUDO_REG)
-		return (p2->type == PSEUDO_REG && p1->nr <= p2->nr) || p2->type == PSEUDO_VAL || p2->type == PSEUDO_SYM || p2->type == PSEUDO_ARG;
-
-	return 1;
+	/* symbol/constants on the right */
+	if (t1 < t2)
+		return 1;
+	if (t1 > t2)
+		return 0;
+	switch (t1) {
+	case PSEUDO_SYM:
+		return p1->sym <= p2->sym;
+	case PSEUDO_REG:
+	case PSEUDO_ARG:
+		return p1->nr <= p2->nr;
+	default:
+		return 1;
+	}
 }
 
 static int canonicalize_commutative(struct instruction *insn)
-- 
2.29.2

[PATCH 5/7] opcode: add helpers opcode_negate() & opcode_swap()

[Luc Van Oostenryck]

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

diff --git a/opcode.h b/opcode.h
index 1524272f0320..b74ba02d94bd 100644
--- a/opcode.h
+++ b/opcode.h
@@ -32,6 +32,16 @@ extern const struct opcode_table {
 } opcode_table[];
 
 
+static inline int opcode_negate(int opcode)
+{
+	return opcode_table[opcode].negate;
+}
+
+static inline int opcode_swap(int opcode)
+{
+	return opcode_table[opcode].swap;
+}
+
 static inline int opcode_float(int opcode, struct symbol *type)
 {
 	if (!type || !is_float_type(type))
-- 
2.29.2

[PATCH 6/7] not: simplify (~x {&,|,^} x) --> {0,~0,~0}

[Luc Van Oostenryck]

Simplify bitwise operations on a pseudo and its complement
into 0 (for &) or ~0 for (| and ^).

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

diff --git a/simplify.c b/simplify.c
index 203472972bca..b41c155735d1 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1630,6 +1630,66 @@ static int simplify_compare(struct instruction *insn)
 	return 0;
 }
 
+static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
+{
+	struct instruction *def;
+	pseudo_t src1 = *p1;
+
+	switch (DEF_OPCODE(def, src1)) {
+	case OP_NOT:
+		if (def->src == *p2)
+			return replace_with_value(insn, 0);
+		break;
+	}
+	return 0;
+}
+
+static int simplify_and(struct instruction *insn)
+{
+	return simplify_and_one_side(insn, &insn->src1, &insn->src2) ||
+	       simplify_and_one_side(insn, &insn->src2, &insn->src1);
+}
+
+static int simplify_ior_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
+{
+	struct instruction *def;
+	pseudo_t src1 = *p1;
+
+	switch (DEF_OPCODE(def, src1)) {
+	case OP_NOT:
+		if (def->src == *p2)
+			return replace_with_value(insn, bits_mask(insn->size));
+		break;
+	}
+	return 0;
+}
+
+static int simplify_ior(struct instruction *insn)
+{
+	return simplify_ior_one_side(insn, &insn->src1, &insn->src2) ||
+	       simplify_ior_one_side(insn, &insn->src2, &insn->src1);
+}
+
+static int simplify_xor_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
+{
+	struct instruction *def;
+	pseudo_t src1 = *p1;
+
+	switch (DEF_OPCODE(def, src1)) {
+	case OP_NOT:
+		if (def->src == *p2)
+			return replace_with_value(insn, bits_mask(insn->size));
+		break;
+	}
+	return 0;
+}
+
+static int simplify_xor(struct instruction *insn)
+{
+	return simplify_xor_one_side(insn, &insn->src1, &insn->src2) ||
+	       simplify_xor_one_side(insn, &insn->src2, &insn->src1);
+}
+
 static int simplify_constant_unop(struct instruction *insn)
 {
 	long long val = insn->src1->value;
@@ -2162,10 +2222,10 @@ int simplify_instruction(struct instruction *insn)
 	switch (insn->opcode) {
 	case OP_ADD: return simplify_add(insn);
 	case OP_SUB: return simplify_sub(insn);
+	case OP_AND: return simplify_and(insn);
+	case OP_OR:  return simplify_ior(insn);
+	case OP_XOR: return simplify_xor(insn);
 	case OP_MUL:
-	case OP_AND:
-	case OP_OR:
-	case OP_XOR:
 	case OP_SHL:
 	case OP_LSR:
 	case OP_ASR:
diff --git a/validation/optim/cse-not01.c b/validation/optim/cse-not01.c
index f87123f14f13..ea1bb7cf25d4 100644
--- a/validation/optim/cse-not01.c
+++ b/validation/optim/cse-not01.c
@@ -5,7 +5,6 @@ int xor(int a) { return (~a ^ a) == ~0; }
 /*
  * check-name: cse-not01
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2

[PATCH 7/7] not: simplify ((x cmp y) {&,|,^} (x !cmp y)) --> {0,1,1}

[Luc Van Oostenryck]

Simplify bitwise operations on a compare and its complement
into 0 (for &) or 1 for (| and ^).

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

diff --git a/simplify.c b/simplify.c
index b41c155735d1..9938a5974744 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1632,7 +1632,7 @@ static int simplify_compare(struct instruction *insn)
 
 static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
 {
-	struct instruction *def;
+	struct instruction *def, *defr = NULL;
 	pseudo_t src1 = *p1;
 
 	switch (DEF_OPCODE(def, src1)) {
@@ -1640,6 +1640,12 @@ static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_
 		if (def->src == *p2)
 			return replace_with_value(insn, 0);
 		break;
+	case OP_BINCMP ... OP_BINCMP_END:
+		if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) {
+			if (def->src1 == defr->src1 && def->src2 == defr->src2)
+				return replace_with_value(insn, 0);
+		}
+		break;
 	}
 	return 0;
 }
@@ -1652,7 +1658,7 @@ static int simplify_and(struct instruction *insn)
 
 static int simplify_ior_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
 {
-	struct instruction *def;
+	struct instruction *def, *defr = NULL;
 	pseudo_t src1 = *p1;
 
 	switch (DEF_OPCODE(def, src1)) {
@@ -1660,6 +1666,12 @@ static int simplify_ior_one_side(struct instruction *insn, pseudo_t *p1, pseudo_
 		if (def->src == *p2)
 			return replace_with_value(insn, bits_mask(insn->size));
 		break;
+	case OP_BINCMP ... OP_BINCMP_END:
+		if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) {
+			if (def->src1 == defr->src1 && def->src2 == defr->src2)
+				return replace_with_value(insn, 1);
+		}
+		break;
 	}
 	return 0;
 }
@@ -1672,7 +1684,7 @@ static int simplify_ior(struct instruction *insn)
 
 static int simplify_xor_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
 {
-	struct instruction *def;
+	struct instruction *def, *defr = NULL;
 	pseudo_t src1 = *p1;
 
 	switch (DEF_OPCODE(def, src1)) {
@@ -1680,6 +1692,12 @@ static int simplify_xor_one_side(struct instruction *insn, pseudo_t *p1, pseudo_
 		if (def->src == *p2)
 			return replace_with_value(insn, bits_mask(insn->size));
 		break;
+	case OP_BINCMP ... OP_BINCMP_END:
+		if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) {
+			if (def->src1 == defr->src1 && def->src2 == defr->src2)
+				return replace_with_value(insn, 1);
+		}
+		break;
 	}
 	return 0;
 }
diff --git a/validation/optim/cse-not02.c b/validation/optim/cse-not02.c
index aa54a375a9ea..70addebcfbb6 100644
--- a/validation/optim/cse-not02.c
+++ b/validation/optim/cse-not02.c
@@ -5,7 +5,6 @@ int xor(int a, int b) { return ((a == b) ^ (a != b)) == 1; }
 /*
  * check-name: cse-not02
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2

Re: [PATCH 1/7] not: add testcases for canonicalization & simplification of negations

[Linus Torvalds]

I thought we already canonicalized the pseudo ordering, but clearly not..

Anyway., looks good to me.

Btw, if you want to do another simplification, one that I've actually
seen multiple times in the kernel is this one:

    if (val1 & BITx)
       val2 |= BITy;

and turning it into

    val2 |= (val1 & BITx) .. shift left or right by (BITx-BITy);

and while actually testing the above, I note that sparse seems to have
problems with even simple if-conversion:

   #define BIT1 4
   #define BIT2 8

   int fn(int x, int y)
   {
        if (x & BIT1)
                y |= BIT2;
        return y;
   }

linearizes to a nasty mess of actual phi nodes and conditional jumps
rather than just a 'select' op. Never mind the actual unconditional
version, of course.

I didn't check why the if-conversion doesn't happen.

           Linus

Re: [PATCH 1/7] not: add testcases for canonicalization & simplification of negations

[Luc Van Oostenryck]

On Sun, Nov 22, 2020 at 11:00:26AM -0800, Linus Torvalds wrote:
> I thought we already canonicalized the pseudo ordering, but clearly not..
> 
> Anyway., looks good to me.
> 
> Btw, if you want to do another simplification, one that I've actually
> seen multiple times in the kernel is this one:
> 
>     if (val1 & BITx)
>        val2 |= BITy;
> 
> and turning it into
> 
>     val2 |= (val1 & BITx) .. shift left or right by (BITx-BITy);

Mmmm, yes, interesting. I'll look at this but ...
 
> and while actually testing the above, I note that sparse seems to have
> problems with even simple if-conversion:
> 
>    #define BIT1 4
>    #define BIT2 8
> 
>    int fn(int x, int y)
>    {
>         if (x & BIT1)
>                 y |= BIT2;
>         return y;
>    }
> 
> linearizes to a nasty mess of actual phi nodes and conditional jumps
> rather than just a 'select' op. Never mind the actual unconditional
> version, of course.
> 
> I didn't check why the if-conversion doesn't happen.

Yes, I know. I'm currently working on it the last days but it's nasty.
Very often, a (good) change blocks another one and I'm often bitten by
the CFG changing and thus invalidating things like dominance relation-
ships.

In the case here with your example, the if-conversion doesn't happen
because the phi-sources is not defined in the top block because of
the OR:
	fn:
		and.32      %r2 <- %arg1, $4
		phisrc.32   %phi2(y) <- %arg2
		cbr         %r2, .L1, .L2
	.L1:
		or.32       %r5 <- %arg2, $8
		phisrc.32   %phi3(y) <- %r5
		br          .L2
	.L2:
		phi.32      %r8(y) <- %phi2(y), %phi3(y)
		ret.32      %r8(y)

It's quite frequent and the obvious solution is to move up such
instructions (and maybe, if the if-conversion succeed, the BBs
will be merged and there won't be a top and bottom block anymore).
I've a very crude patch moving all such instructions up if possible,
it gives some positive results for the context imbalance but nothing
miraculous (IIRC something like 35 warnings less on a total of ~1000).

Another interesting example is something like:
	int foo(int a)
	{
		int e;
		if (a) {
			__context__(1);
			e = 1;
		} else {
			e = 0;
		}
		if (!e)
			return 1;
		__context__(-1);
		return 0;
	}

which produces the following IR:
	foo:
	.L0:
		cbr         %arg1, .L1, .L3
	.L1:
		context     1
		br          .L3
	.L3:
		seteq.32    %r5 <- %arg1, $0
		cbr         %arg1, .L5, .L6
	.L5:
		context     -1
		br          .L6
	.L6:
		ret.32      %r5

Sparse issues a "context imbalance" warnings on it but in fact
everything is OK. Three different things could unblock things:
1) the seteq move up to L0, then L1 can directly jump to L5
2) the seteq move down to L6, then again L1 can jump to L5
3) the context in L1 is changed into a conditional (a new instruction,
   essentially a select but for contexts) it can then be moved up
   to L0, L1 disappears and L3 can be merged with L0.
None of these are really hard but the problem, I'm sure you can guess
it, is that none bring a definitive, clear solution because, very often,
moving things up or down just displaces the problem to somewhere else.
But well, it's life.

-- Luc

Re: [PATCH 1/7] not: add testcases for canonicalization & simplification of negations

[Linus Torvalds]

On Sun, Nov 22, 2020 at 11:57 AM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> In the case here with your example, the if-conversion doesn't happen
> because the phi-sources is not defined in the top block because of
> the OR:

Ahh. Yes, it's more obvious with a more realistic test-case that
actually translates one set of bits to another set of bits (which is
something we do in the kernel for various reasons - different bit
"namespaces", for example user interfaces etc):

   #define BIT1   4
   #define BIT1x 16

   #define BIT2   8
   #define BIT2x 32

   int translate_bits(int x)
   {
        int y = 0;
        if (x & BIT1)
                y |= BIT1x;
        if (x & BIT2)
                y |= BIT2x;
        return y;
   }

and the first one gets nicely translated as

   and.32      %r2 <- %arg1, $4
   select.32   %r14(y) <- %r2, $16, $0

but then the second one doesn't for the reason you mention.

Honestly, particularly in the conditional form, the OP_SEL
optimization might not even be the right thing. It adds register
pressure.

So maybe a better model would be to not try to do jump-conversion, but
have some kind of general "can we simplify phi nodes", where jump
conversion to OP_SEL is just one of the options.

              Linus

Re: [PATCH 1/7] not: add testcases for canonicalization & simplification of negations

[Luc Van Oostenryck]

On Sun, Nov 22, 2020 at 12:13:46PM -0800, Linus Torvalds wrote:
> 
> Honestly, particularly in the conditional form, the OP_SEL
> optimization might not even be the right thing. It adds register
> pressure.
> 
> So maybe a better model would be to not try to do jump-conversion, but
> have some kind of general "can we simplify phi nodes", where jump
> conversion to OP_SEL is just one of the options.

Yes, for the "context imbalance" problem, it's best to eliminate
the most possible conditional branches (and if-conversion and jump
threading help each other at this (when not blocking each other)).
So, yes, probably what's missing the most is some strategy to
attack the problem.

-- Luc

Re: [PATCH 1/7] not: add testcases for canonicalization & simplification of negations

[Luc Van Oostenryck]

On Sun, Nov 22, 2020 at 12:13:46PM -0800, Linus Torvalds wrote:
> On Sun, Nov 22, 2020 at 11:57 AM Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > In the case here with your example, the if-conversion doesn't happen
> > because the phi-sources is not defined in the top block because of
> > the OR:
> 
> Ahh. Yes, it's more obvious with a more realistic test-case that
> actually translates one set of bits to another set of bits (which is
> something we do in the kernel for various reasons - different bit
> "namespaces", for example user interfaces etc):
> 
>    #define BIT1   4
>    #define BIT1x 16
> 
>    #define BIT2   8
>    #define BIT2x 32
> 
>    int translate_bits(int x)
>    {
>         int y = 0;
>         if (x & BIT1)
>                 y |= BIT1x;
>         if (x & BIT2)
>                 y |= BIT2x;
>         return y;
>    }
> 
> and the first one gets nicely translated as
> 
>    and.32      %r2 <- %arg1, $4
>    select.32   %r14(y) <- %r2, $16, $0
> 
> but then the second one doesn't for the reason you mention.

One thing that can be done (but probably excessive) is something
like the patch below: each time a phi-source is 'blocked' by
it's defining instruction, try to move this instruction up.
With this, we get the expected result for your patch:
	translate_bits:
		and.32      %r2 <- %arg1, $4
		select.32   %r14(y) <- %r2, $16, $0
		and.32      %r7 <- %arg1, $8
		or.32       %r10 <- %r14(y), $32
		select.32   %r13(y) <- %r7, %r10, %r14(y)
		ret.32      %r13(y)

It gives very good result in all sort of code but sadly it
doesn't improve the context imbalance warnings, it even
make them (very) slightly worse.


From be38aca2a4ca3fc0911da9187e2ea58a379824cc Mon Sep 17 00:00:00 2001
From: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Date: Sun, 22 Nov 2020 22:49:13 +0100
Subject: [PATCH] move up instructions blocking if-conversion

---
 linearize.h |  6 +++++
 simplify.c  | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 69 insertions(+), 2 deletions(-)

diff --git a/linearize.h b/linearize.h
index 31c754e200c2..dcd4359eb2a6 100644
--- a/linearize.h
+++ b/linearize.h
@@ -300,6 +300,12 @@ static inline void replace_bb_in_list(struct basic_block_list **list,
 	replace_ptr_list_entry((struct ptr_list **)list, old, new, count);
 }
 
+static inline void replace_insn(struct instruction *old, struct instruction *new)
+{
+	replace_ptr_list_entry((struct ptr_list **)&old->bb->insns, old, new, 1);
+}
+
+
 struct entrypoint {
 	struct symbol *name;
 	struct symbol_list *syms;
diff --git a/simplify.c b/simplify.c
index a0e23d6de01f..7d5e0d9bcb3a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -46,11 +46,69 @@
 #include "linearize.h"
 #include "flow.h"
 #include "symbol.h"
+#include "flowgraph.h"
 
 ///
 // Utilities
 // ^^^^^^^^^
 
+///
+// check if a pseudo is defined in a BB
+//
+// :note: this could also use the liveness information if available.
+//
+static inline bool is_defined_at(pseudo_t src, struct basic_block *bb)
+{
+	if (src->type != PSEUDO_REG)
+		return true;
+	return domtree_dominates(src->def->bb, bb);
+}
+
+///
+// move an instruction at the end of the given BB
+static void move_insn(struct instruction *insn, struct basic_block *bb)
+{
+	struct instruction *last = delete_last_instruction(&bb->insns);
+	insn->bb = bb;
+	add_instruction(&bb->insns, insn);
+	add_instruction(&bb->insns, last);
+}
+
+///
+// move an instruction into a BB if all its arguments are defined there
+static bool try_to_move_insn(struct instruction *insn, struct basic_block *bb)
+{
+	static struct instruction NOP;	// will later be ignore because !ep
+
+	if (!bb || bb == insn->bb)
+		return 0;
+
+	switch (insn->opcode) {
+	case OP_SEL:
+		if (!is_defined_at(insn->src3, bb))
+			return 0;
+	case OP_ADD: case OP_SUB:
+	case OP_ASR: case OP_LSR: case OP_SHL:
+	case OP_AND: case OP_XOR: case OP_OR:
+	case OP_BINCMP ... OP_BINCMP_END:
+	case OP_FPCMP ... OP_FPCMP_END:
+	case OP_FADD: case OP_FSUB:
+		// basically, all the binops but multiply and divide, just because
+		if (!is_defined_at(insn->src2, bb))
+			return 0;
+	case OP_UNOP ... OP_UNOP_END:
+		if (!is_defined_at(insn->src1, bb))
+			return 0;
+		break;
+	default:
+		return 0;
+	}
+	replace_insn(insn, &NOP);
+	move_insn(insn, bb);
+	repeat_phase |= REPEAT_CSE;
+	return 1;
+}
+
 ///
 // find the trivial parent for a phi-source
 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
@@ -58,8 +116,11 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud
 	/* Can't go upwards if the pseudo is defined in the bb it came from.. */
 	if (pseudo->type == PSEUDO_REG) {
 		struct instruction *def = pseudo->def;
-		if (def->bb == source)
-			return source;
+		if (def->bb == source) {
+			// unless we can move the defining instruction up
+			if (!try_to_move_insn(def, source->idom))
+				return source;
+		}
 	}
 	if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
 		return source;
-- 
2.29.2

[PATCH 0/6] 'bits translation' simplification

[Luc Van Oostenryck]

This series allows the simplification of expressions like:
	if (val1 & 4)
		val2 |= 8;
into
	val2 |= (val1 & 4) << 1;

With a better if-conversion mechanism it also allows to optimize
	int translate_bits(int x)
	{
		int y = 0;
		if (x & 4)
			y |= 16;
		if (x & 8)
			y |= 32;
		return y;
	}

into this nice:
	translate_bits:
		and.32      %r2 <- %arg1, $12
		shl.32      %r5 <- %r2, $2
		ret.32      %r5

when applied on top of the previous 'factorization' series.

This series is available for review and testing at:
  git://git.kernel.org/pub/scm/devel/sparse/sparse-dev.git bit-trans

Luc Van Oostenryck (6):
  add testscases for 'bits translation' optimization
  factorize SEL(x, OP(y,z), y) into OP(SEL(x, z, 0), y)
  add helper is_power_of_2()
  add helper is_pow2()
  add log base 2 function: log2_exact()
  convert SEL(x & BIT1, BIT2, 0) into SHIFT(x & BIT1, S)

 bits.h                              | 12 ++++++
 simplify.c                          | 64 +++++++++++++++++++++++++++++
 validation/optim/fact-select01.c    | 25 +++++++++++
 validation/optim/select-and-shift.c | 17 ++++++++
 4 files changed, 118 insertions(+)
 create mode 100644 validation/optim/fact-select01.c
 create mode 100644 validation/optim/select-and-shift.c

-- 
2.29.2

[PATCH 1/6] add testscases for 'bits translation' optimization

[Luc Van Oostenryck]

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 <luc.vanoostenryck@gmail.com>
---
 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

diff --git a/validation/optim/fact-select01.c b/validation/optim/fact-select01.c
new file mode 100644
index 000000000000..ef4e5e89a7be
--- /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 000000000000..fbe044c7cb44
--- /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
+ */
-- 
2.29.2

[PATCH 2/6] factorize SEL(x, OP(y,z), y) into OP(SEL(x, z, 0), y)

[Luc Van Oostenryck]

'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 <luc.vanoostenryck@gmail.com>
---
 simplify.c                       | 40 ++++++++++++++++++++++++++++++++
 validation/optim/fact-select01.c |  1 -
 2 files changed, 40 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 89a064b93e85..d729b390ae76 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 ef4e5e89a7be..9232fc908e34 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
-- 
2.29.2

[PATCH 3/6] add helper is_power_of_2()

[Luc Van Oostenryck]

Add is_power_of_2() to test if a value is a power of 2.

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

diff --git a/bits.h b/bits.h
index c0dc952eaed9..63a663c248e4 100644
--- a/bits.h
+++ b/bits.h
@@ -58,4 +58,9 @@ static inline long long bits_extend(long long val, unsigned size, int is_signed)
 	return val;
 }
 
+static inline int is_power_of_2(long long val)
+{
+	return val && !(val & (val - 1));
+}
+
 #endif
-- 
2.29.2

[PATCH 4/6] add helper is_pow2()

[Luc Van Oostenryck]

Add is_pow2() to test if a pseudo is a power of 2.

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

diff --git a/simplify.c b/simplify.c
index d729b390ae76..0d9391e21a56 100644
--- a/simplify.c
+++ b/simplify.c
@@ -52,6 +52,15 @@
 // Utilities
 // ^^^^^^^^^
 
+///
+// check if a pseudo is a power of 2
+static inline bool is_pow2(pseudo_t src)
+{
+	if (src->type != PSEUDO_VAL)
+		return false;
+	return is_power_of_2(src->value);
+}
+
 ///
 // find the trivial parent for a phi-source
 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
-- 
2.29.2

[PATCH 5/6] add log base 2 function: log2_exact()

[Luc Van Oostenryck]

Add log2_exact() to get the base 2 logarithm of a value known
to be a power of 2.

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

diff --git a/bits.h b/bits.h
index 63a663c248e4..9908190d8c2f 100644
--- a/bits.h
+++ b/bits.h
@@ -63,4 +63,11 @@ static inline int is_power_of_2(long long val)
 	return val && !(val & (val - 1));
 }
 
+///
+// log base 2 of an exact power-of-2
+static inline int log2_exact(unsigned long long val)
+{
+	return 8 * sizeof(val) - __builtin_clzl(val) - 1;
+}
+
 #endif
-- 
2.29.2

[PATCH 6/6] convert SEL(x & BIT1, BIT2, 0) into SHIFT(x & BIT1, S)

[Luc Van Oostenryck]

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 <torvalds@linux-foundation.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                          | 15 +++++++++++++++
 validation/optim/select-and-shift.c |  1 -
 2 files changed, 15 insertions(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 0d9391e21a56..fc64e5b77adf 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 fbe044c7cb44..5313fe4b1d86 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
-- 
2.29.2

[PATCH 7/7] move up instructions blocking if-conversion

[Luc Van Oostenryck]

---
 linearize.h |  6 +++++
 simplify.c  | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 68 insertions(+), 2 deletions(-)

diff --git a/linearize.h b/linearize.h
index 2c548d43526f..71a693960c9e 100644
--- a/linearize.h
+++ b/linearize.h
@@ -300,6 +300,12 @@ static inline void replace_bb_in_list(struct basic_block_list **list,
 	replace_ptr_list_entry((struct ptr_list **)list, old, new, count);
 }
 
+static inline void replace_insn(struct instruction *old, struct instruction *new)
+{
+	replace_ptr_list_entry((struct ptr_list **)&old->bb->insns, old, new, 1);
+}
+
+
 struct entrypoint {
 	struct symbol *name;
 	struct symbol_list *syms;
diff --git a/simplify.c b/simplify.c
index fc64e5b77adf..14a5562c84a4 100644
--- a/simplify.c
+++ b/simplify.c
@@ -61,6 +61,63 @@ static inline bool is_pow2(pseudo_t src)
 	return is_power_of_2(src->value);
 }
 
+///
+// check if a pseudo is defined in a BB
+//
+// :note: this could also use the liveness information if available.
+//
+static inline bool is_defined_at(pseudo_t src, struct basic_block *bb)
+{
+	if (src->type != PSEUDO_REG)
+		return true;
+	return domtree_dominates(src->def->bb, bb);
+}
+
+///
+// move an instruction at the end of the given BB
+static void move_insn(struct instruction *insn, struct basic_block *bb)
+{
+	struct instruction *last = delete_last_instruction(&bb->insns);
+	insn->bb = bb;
+	add_instruction(&bb->insns, insn);
+	add_instruction(&bb->insns, last);
+}
+
+///
+// try to move an instruction into a BB if all its arguments are defined there
+static bool try_to_move_insn(struct instruction *insn, struct basic_block *bb)
+{
+	static struct instruction NOP;	// will later be ignore because !ep
+
+	if (!bb || bb == insn->bb)
+		return 0;
+
+	switch (insn->opcode) {
+	case OP_SEL:
+		if (!is_defined_at(insn->src3, bb))
+			return 0;
+	case OP_ADD: case OP_SUB:
+	case OP_ASR: case OP_LSR: case OP_SHL:
+	case OP_AND: case OP_XOR: case OP_OR:
+	case OP_BINCMP ... OP_BINCMP_END:
+	case OP_FPCMP ... OP_FPCMP_END:
+	case OP_FADD: case OP_FSUB:
+		// basically, all the binops but multiply and divide, just because
+		if (!is_defined_at(insn->src2, bb))
+			return 0;
+	case OP_UNOP ... OP_UNOP_END:
+		if (!is_defined_at(insn->src1, bb))
+			return 0;
+		break;
+	default:
+		return 0;
+	}
+	replace_insn(insn, &NOP);
+	move_insn(insn, bb);
+	repeat_phase |= REPEAT_CSE;
+	return 1;
+}
+
 ///
 // find the trivial parent for a phi-source
 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
@@ -68,8 +125,11 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud
 	/* Can't go upwards if the pseudo is defined in the bb it came from.. */
 	if (pseudo->type == PSEUDO_REG) {
 		struct instruction *def = pseudo->def;
-		if (def->bb == source)
-			return source;
+		if (def->bb == source) {
+			// unless we can move the defining instruction up
+			if (!try_to_move_insn(def, source->idom))
+				return source;
+		}
 	}
 	if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
 		return source;
-- 
2.29.2

Re: [PATCH 0/6] 'bits translation' simplification

[Linus Torvalds]

On Fri, Nov 27, 2020 at 2:28 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> With a better if-conversion mechanism it also allows to optimize
>         int translate_bits(int x)
>         {
>                 int y = 0;
>                 if (x & 4)
>                         y |= 16;
>                 if (x & 8)
>                         y |= 32;
>                 return y;
>         }
>
> into this nice:
>         translate_bits:
>                 and.32      %r2 <- %arg1, $12
>                 shl.32      %r5 <- %r2, $2
>                 ret.32      %r5
>
> when applied on top of the previous 'factorization' series.

Heh. Very nice. Thanks,

            Linus