[PATCH 0/5] simplify SEL(SEL, ...), ...)

[PATCH 0/5] simplify SEL(SEL, ...), ...)

[Luc Van Oostenryck]

These patch add a few simplifications when the condition of a
select is another select and have constants as operands.

@Linus,
  The patch you wanted is patch #3.

Luc Van Oostenryck (5):
  select: add some testcases for select simplification
  select: simplify SEL(SEL(x, C, 0), y, z) --> SEL(x, y, z) and its dual
  select: simplify SEL(SEL(x, C, 0), C, 0) --> SEL(x, C, 0) == cond
  select: simplify SEL(SEL(x, C1, C2), y, z) --> y (with C1, C2 != 0)
  select: simplify handling of constant cond or src1 == src2

 simplify.c                                   | 40 ++++++++++++++++----
 validation/optim/select-constant-cond.c      | 10 +++++
 validation/optim/select-same-args.c          |  9 +++++
 validation/optim/select-select-true-false0.c | 10 +++++
 validation/optim/select-select-true-false1.c | 13 +++++++
 validation/optim/select-select-true-true.c   |  9 +++++
 6 files changed, 83 insertions(+), 8 deletions(-)
 create mode 100644 validation/optim/select-constant-cond.c
 create mode 100644 validation/optim/select-same-args.c
 create mode 100644 validation/optim/select-select-true-false0.c
 create mode 100644 validation/optim/select-select-true-false1.c
 create mode 100644 validation/optim/select-select-true-true.c

-- 
2.29.2

[PATCH 1/5] select: add some testcases for select simplification

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/select-constant-cond.c      | 10 ++++++++++
 validation/optim/select-same-args.c          |  9 +++++++++
 validation/optim/select-select-true-false0.c | 11 +++++++++++
 validation/optim/select-select-true-false1.c | 14 ++++++++++++++
 validation/optim/select-select-true-true.c   | 10 ++++++++++
 5 files changed, 54 insertions(+)
 create mode 100644 validation/optim/select-constant-cond.c
 create mode 100644 validation/optim/select-same-args.c
 create mode 100644 validation/optim/select-select-true-false0.c
 create mode 100644 validation/optim/select-select-true-false1.c
 create mode 100644 validation/optim/select-select-true-true.c

diff --git a/validation/optim/select-constant-cond.c b/validation/optim/select-constant-cond.c
new file mode 100644
index 000000000000..a9337e2ceaee
--- /dev/null
+++ b/validation/optim/select-constant-cond.c
@@ -0,0 +1,10 @@
+int t(int p, int a, int b) { return ((p == p) ? a : b) == a; }
+int f(int p, int a, int b) { return ((p != p) ? a : b) == b; }
+
+/*
+ * check-name: select-constant-cond
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/select-same-args.c b/validation/optim/select-same-args.c
new file mode 100644
index 000000000000..403af47169c3
--- /dev/null
+++ b/validation/optim/select-same-args.c
@@ -0,0 +1,9 @@
+int foo(int p, int a) { return (p ? a : a) == a; }
+
+/*
+ * check-name: select-same-args
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/select-select-true-false0.c b/validation/optim/select-select-true-false0.c
new file mode 100644
index 000000000000..46bd7667400d
--- /dev/null
+++ b/validation/optim/select-select-true-false0.c
@@ -0,0 +1,11 @@
+int fw(int p, int a, int b) { return ((p ? 42 : 0) ? a : b) == ( p ? a : b); }
+int bw(int p, int a, int b) { return ((p ? 0 : 42) ? a : b) == ( p ? b : a); }
+
+/*
+ * check-name: select-select-true-false0
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/select-select-true-false1.c b/validation/optim/select-select-true-false1.c
new file mode 100644
index 000000000000..00ffdcd1bc9b
--- /dev/null
+++ b/validation/optim/select-select-true-false1.c
@@ -0,0 +1,14 @@
+int foo(int p)
+{
+	int t = (p ? 42 : 0);
+	return (t ? 42 : 0) == ( p ? 42 : 0);
+}
+
+/*
+ * check-name: select-select-true-false1
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
diff --git a/validation/optim/select-select-true-true.c b/validation/optim/select-select-true-true.c
new file mode 100644
index 000000000000..e6fa2c89febb
--- /dev/null
+++ b/validation/optim/select-select-true-true.c
@@ -0,0 +1,10 @@
+int foo(int p, int a, int b) { return ((p ? 42 : 43) ? a : b) == a ; }
+
+/*
+ * check-name: select-select-true-true
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
-- 
2.29.2

[PATCH 2/5] select: simplify SEL(SEL(x, C, 0), y, z) --> SEL(x, y, z) and its dual

[Luc Van Oostenryck]

If the condition of a select is also a select but with constant
operands, some simplification can be done:
* if the second operand is 0, the original condition can be used,
* idem if the first operand is 0s but the operand must be swapped.

Originally-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                                   | 20 ++++++++++++++++++++
 validation/optim/select-select-true-false0.c |  1 -
 validation/optim/select-select-true-false1.c |  1 -
 3 files changed, 20 insertions(+), 2 deletions(-)

diff --git a/simplify.c b/simplify.c
index f2aaa52de84b..6b44d447c0a9 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1748,6 +1748,7 @@ static int simplify_cast(struct instruction *insn)
 static int simplify_select(struct instruction *insn)
 {
 	pseudo_t cond, src1, src2;
+	struct instruction *def;
 
 	cond = insn->src1;
 	src1 = insn->src2;
@@ -1782,6 +1783,25 @@ static int simplify_select(struct instruction *insn)
 		kill_use(&insn->src3);
 		return replace_with_value(insn, 0);
 	}
+
+	switch (DEF_OPCODE(def, cond)) {
+	case OP_SEL:
+		if (constant(def->src2) && constant(def->src3)) {
+			// Is the def of the conditional another select?
+			// And if that one results in a "zero or not", use the
+			// original conditional instead.
+			//	SEL(SEL(x, C, 0), y, z) --> SEL(x, y, z)
+			//	SEL(SEL(x, 0, C), y, z) --> SEL(x, z, y)
+			if (!def->src3->value) {
+				return replace_pseudo(insn, &insn->cond, def->cond);
+			}
+			if (!def->src2->value) {
+				switch_pseudo(insn, &insn->src2, insn, &insn->src3);
+				return replace_pseudo(insn, &insn->cond, def->cond);
+			}
+		}
+		break;
+	}
 	return 0;
 }
 
diff --git a/validation/optim/select-select-true-false0.c b/validation/optim/select-select-true-false0.c
index 46bd7667400d..4066c2dad6fc 100644
--- a/validation/optim/select-select-true-false0.c
+++ b/validation/optim/select-select-true-false0.c
@@ -4,7 +4,6 @@ int bw(int p, int a, int b) { return ((p ? 0 : 42) ? a : b) == ( p ? b : a); }
 /*
  * check-name: select-select-true-false0
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
diff --git a/validation/optim/select-select-true-false1.c b/validation/optim/select-select-true-false1.c
index 00ffdcd1bc9b..32c0364de2ba 100644
--- a/validation/optim/select-select-true-false1.c
+++ b/validation/optim/select-select-true-false1.c
@@ -7,7 +7,6 @@ int foo(int p)
 /*
  * check-name: select-select-true-false1
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2

[PATCH 3/5] select: simplify SEL(SEL(x, C, 0), C, 0) --> SEL(x, C, 0) == cond

[Luc Van Oostenryck]

If the condition of a select is also a select, both with the same
arguments: first a non-zero constant, then a zero constant, then
the outer select is equivalent to the inner one and can thus
be replaced by the result of the inner select (which is its own
condition).

Note: this is a special case of:
	SEL(SEL(x, C, 0), y, z) --> SEL(x, y, z)
      and without this patch we'll have:
	t = SEL(x, C, 0)
	r = SEL(t, C, 0)
      simplified into:
	t = SEL(x, C, 0)	// possibly unused now
	r = SEL(x, C, 0)
      but the present patch do
	t = SEL(x, C, 0)
	r = t
      In other words, functionally, the result is the same but
      now the result is taken from the first instruction.

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

diff --git a/simplify.c b/simplify.c
index 6b44d447c0a9..1fcfc691579a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1791,8 +1791,11 @@ static int simplify_select(struct instruction *insn)
 			// And if that one results in a "zero or not", use the
 			// original conditional instead.
 			//	SEL(SEL(x, C, 0), y, z) --> SEL(x, y, z)
+			//	SEL(SEL(x, C, 0), C, 0) --> SEL(x, C, 0) == cond
 			//	SEL(SEL(x, 0, C), y, z) --> SEL(x, z, y)
 			if (!def->src3->value) {
+				if ((src1 == def->src2) && (src2 == def->src3))
+					return replace_with_pseudo(insn, cond);
 				return replace_pseudo(insn, &insn->cond, def->cond);
 			}
 			if (!def->src2->value) {
-- 
2.29.2

[PATCH 4/5] select: simplify SEL(SEL(x, C1, C2), y, z) --> y (with C1, C2 != 0)

[Luc Van Oostenryck]

If the condition of a select is also a select, with constant
but non-zero operands, then the result of this inner select
is always true and the outer select can be replaced by its
second operand.

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

diff --git a/simplify.c b/simplify.c
index 1fcfc691579a..20ea5f1be71a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1793,6 +1793,7 @@ static int simplify_select(struct instruction *insn)
 			//	SEL(SEL(x, C, 0), y, z) --> SEL(x, y, z)
 			//	SEL(SEL(x, C, 0), C, 0) --> SEL(x, C, 0) == cond
 			//	SEL(SEL(x, 0, C), y, z) --> SEL(x, z, y)
+			//	SEL(SEL(x, C1, C2), y, z) --> y
 			if (!def->src3->value) {
 				if ((src1 == def->src2) && (src2 == def->src3))
 					return replace_with_pseudo(insn, cond);
@@ -1802,6 +1803,8 @@ static int simplify_select(struct instruction *insn)
 				switch_pseudo(insn, &insn->src2, insn, &insn->src3);
 				return replace_pseudo(insn, &insn->cond, def->cond);
 			}
+			// both values must be non-zero
+			return replace_with_pseudo(insn, src1);
 		}
 		break;
 	}
diff --git a/validation/optim/select-select-true-true.c b/validation/optim/select-select-true-true.c
index e6fa2c89febb..c0c26fdd199a 100644
--- a/validation/optim/select-select-true-true.c
+++ b/validation/optim/select-select-true-true.c
@@ -3,7 +3,6 @@ int foo(int p, int a, int b) { return ((p ? 42 : 43) ? a : b) == a ; }
 /*
  * check-name: select-select-true-true
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2

[PATCH 5/5] select: simplify handling of constant cond or src1 == src2

[Luc Van Oostenryck]

If the operands of a select instruction are identical, then
this select can be replaced by its operand.
If the condition of a select is a constant, the this select
can be replaced by one of its condition, depending on the
truth value of the condition.

This simplification is already done but:
* when src1 == src2, the condition's value is tested although
  it may not be a constant. It's kinda OK because in all case
  one of the operand will be selected and both are identical
  but it's a bit weird and unclean.
* since the instruction will be replaced, the usage of its
  condition and operands must be removed. This is done here but
  the kill_instruction() inside replace_with_pseudo() take
  already care of this.

So, separate the two cases and simply use replace_with_pseudo()
for both without bothering killing the operands.

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

diff --git a/simplify.c b/simplify.c
index 20ea5f1be71a..20ab9b3b3ecf 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1753,14 +1753,12 @@ static int simplify_select(struct instruction *insn)
 	cond = insn->src1;
 	src1 = insn->src2;
 	src2 = insn->src3;
-	if (constant(cond) || src1 == src2) {
-		pseudo_t *kill, take;
-		kill_use(&insn->src1);
-		take = cond->value ? src1 : src2;
-		kill = cond->value ? &insn->src3 : &insn->src2;
-		kill_use(kill);
-		return replace_with_pseudo(insn, take);
-	}
+
+	if (constant(cond))
+		return replace_with_pseudo(insn, cond->value ? src1 : src2);
+	if (src1 == src2)
+		return replace_with_pseudo(insn, src1);
+
 	if (constant(src1) && constant(src2)) {
 		long long val1 = src1->value;
 		long long val2 = src2->value;
-- 
2.29.2

Re: [PATCH 0/5] simplify SEL(SEL, ...), ...)

[Linus Torvalds]

On Sat, Nov 7, 2020 at 3:42 AM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> These patch add a few simplifications when the condition of a
> select is another select and have constants as operands.

Looks good to me.

I think there's a couple of others, like

  SEL(x, x, 0) -> x

which looks insane, but I think these are the kinds of things that end
up showing up when you inline things that return errors, and then you
test them for zero etc.

I haven't thought them all through, and didn't check your cases deeply
and just took your word for them, but it looked all sane to me.

            Linus

Re: [PATCH 0/5] simplify SEL(SEL, ...), ...)

[Linus Torvalds]

On Sat, Nov 7, 2020 at 10:38 AM Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> I think there's a couple of others, like
>
>   SEL(x, x, 0) -> x
>
> which looks insane, but I think these are the kinds of things that end
> up showing up when you inline things that return errors, and then you
> test them for zero etc.

Made-up crazy example:

    extern int fn(int);

    int t(int x)
    {
        int err = fn(x);
        if (err)
                return err;
        return 0;
    }

which is the kind of thing that can happen when you have various
config options and code goes away. It *should* just result in a no-op
(ie just call 'fn()' and return its value), but currently sparse
generates

    call.32     %r2 <- fn, %arg1
    select.32   %r6 <- %r2, %r2, $0
    ret.32      %r6

instead of

    call.32     %r2 <- fn, %arg1
    ret.32      %r2

but I hadn't actually applied your patches when I did that test, so
maybe you had caught this case already without me realizing it.

           Linus