[PATCH 0/4] simplification of computed goto

[PATCH 0/4] simplification of computed goto

[Luc Van Oostenryck]

This series contains some simplification of computed gotos with
1 or 2 possible target as well as a new instruction which now
really allows the CSE of 'labels-as-values'.

Luc Van Oostenryck (4):
  add testcases for COMPUTEDGOTO simplification
  simplify OP_COMPUTEDGOTO with unique and known target
  simplify CGOTO(SEL(x, L1, L2)) into CBR x, L1, L2
  add a new instruction for label-as-value

 cse.c                        |  9 +++++
 example.c                    |  8 +++--
 linearize.c                  |  6 ++++
 liveness.c                   |  1 +
 opcode.def                   |  1 +
 simplify.c                   | 68 ++++++++++++++++++++++++++++++++++--
 sparse-llvm.c                | 11 ++++++
 validation/optim/cgoto01.c   | 24 +++++++++++++
 validation/optim/cgoto02.c   | 17 +++++++++
 validation/optim/cse-label.c | 13 +++++++
 10 files changed, 153 insertions(+), 5 deletions(-)
 create mode 100644 validation/optim/cgoto01.c
 create mode 100644 validation/optim/cgoto02.c
 create mode 100644 validation/optim/cse-label.c

-- 
2.29.2

[PATCH 1/4] add testcases for COMPUTEDGOTO simplification

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/optim/cgoto01.c   | 25 +++++++++++++++++++++++++
 validation/optim/cgoto02.c   | 18 ++++++++++++++++++
 validation/optim/cse-label.c | 14 ++++++++++++++
 3 files changed, 57 insertions(+)
 create mode 100644 validation/optim/cgoto01.c
 create mode 100644 validation/optim/cgoto02.c
 create mode 100644 validation/optim/cse-label.c

diff --git a/validation/optim/cgoto01.c b/validation/optim/cgoto01.c
new file mode 100644
index 000000000000..350c6cd99f08
--- /dev/null
+++ b/validation/optim/cgoto01.c
@@ -0,0 +1,25 @@
+void abort(void) __attribute__((__noreturn__));
+
+int foo(int a)
+{
+	void *label;
+
+	if (a == a)
+		label = &&L1;
+	else
+		label = &&L2;
+	goto *label;
+L1:	return 0;
+L2:	abort();
+}
+
+/*
+ * check-name: cgoto01
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-excludes: set\\.
+ * check-output-excludes: jmp
+ * check-output-excludes: call
+ */
diff --git a/validation/optim/cgoto02.c b/validation/optim/cgoto02.c
new file mode 100644
index 000000000000..5869d5b4a24d
--- /dev/null
+++ b/validation/optim/cgoto02.c
@@ -0,0 +1,18 @@
+int foo(int a)
+{
+	void *label = a ? &&l1 : &&l2;
+	goto *label;
+l1:
+	return a;
+l2:
+	return 0;
+}
+
+/*
+ * check-name: cgoto02
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: %arg1
+ */
diff --git a/validation/optim/cse-label.c b/validation/optim/cse-label.c
new file mode 100644
index 000000000000..e42968204615
--- /dev/null
+++ b/validation/optim/cse-label.c
@@ -0,0 +1,14 @@
+int foo(void)
+{
+label:
+	return &&label == &&label;
+}
+
+/*
+ * check-name: cse-label
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */
-- 
2.29.2

[PATCH 2/4] simplify OP_COMPUTEDGOTO with unique and known target

[Luc Van Oostenryck]

If the OP_COMPUTEDGOTO's source pseudo is defined by a single
OP_SETVAL/EXPR_LABEL, then the corresponding basic block is the
only possible destination and the computed goto can then be
simplified into a simple branch.

So, convert such computed goto into a simple OP_BR which may
then participate in other flow simplifications.

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

diff --git a/simplify.c b/simplify.c
index e58fb6cf3941..132d408f59f1 100644
--- a/simplify.c
+++ b/simplify.c
@@ -2112,6 +2112,34 @@ found:
 	return REPEAT_CSE;
 }
 
+static int simplify_cgoto(struct instruction *insn)
+{
+	struct basic_block *target, *bb = insn->bb;
+	struct instruction *def;
+	struct multijmp *jmp;
+
+	switch (DEF_OPCODE(def, insn->src)) {
+	case OP_SETVAL:
+		if (def->val->type != EXPR_LABEL)
+			break;
+		target = def->val->symbol->bb_target;
+		if (!target->ep)
+			return 0;
+		FOR_EACH_PTR(insn->multijmp_list, jmp) {
+			if (jmp->target == target)
+				continue;
+			remove_bb_from_list(&jmp->target->parents, bb, 1);
+			remove_bb_from_list(&bb->children, jmp->target, 1);
+			MARK_CURRENT_DELETED(jmp);
+		} END_FOR_EACH_PTR(jmp);
+		kill_use(&insn->src);
+		insn->opcode = OP_BR;
+		insn->bb_true = target;
+		return REPEAT_CSE|REPEAT_CFG_CLEANUP;
+	}
+	return 0;
+}
+
 int simplify_instruction(struct instruction *insn)
 {
 	unsigned flags;
@@ -2190,6 +2218,8 @@ int simplify_instruction(struct instruction *insn)
 		return simplify_branch(insn);
 	case OP_SWITCH:
 		return simplify_switch(insn);
+	case OP_COMPUTEDGOTO:
+		return simplify_cgoto(insn);
 	case OP_RANGE:
 		return simplify_range(insn);
 	case OP_FADD:
diff --git a/validation/optim/cgoto01.c b/validation/optim/cgoto01.c
index 350c6cd99f08..94b2c2c429db 100644
--- a/validation/optim/cgoto01.c
+++ b/validation/optim/cgoto01.c
@@ -16,7 +16,6 @@ L2:	abort();
 /*
  * check-name: cgoto01
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-excludes: set\\.
-- 
2.29.2

[PATCH 3/4] simplify CGOTO(SEL(x, L1, L2)) into CBR x, L1, L2

[Luc Van Oostenryck]

A computed goto having as operand a select of 2 statically known addresses
(OP_SETVAL/EXPR_LABEL) is equivalent to a simple conditional branch.

Simplify such computed goto into the corresponding OP_CBR

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

diff --git a/simplify.c b/simplify.c
index 132d408f59f1..24ecf074206e 100644
--- a/simplify.c
+++ b/simplify.c
@@ -2112,13 +2112,35 @@ found:
 	return REPEAT_CSE;
 }
 
+static struct basic_block *is_label(pseudo_t pseudo)
+{
+	struct expression *expr;
+	struct instruction *def;
+
+	if (DEF_OPCODE(def, pseudo) != OP_SETVAL)
+		return NULL;
+	expr = def->val;
+	if (expr->type != EXPR_LABEL)
+		return NULL;
+	return expr->symbol->bb_target;
+}
+
 static int simplify_cgoto(struct instruction *insn)
 {
 	struct basic_block *target, *bb = insn->bb;
+	struct basic_block *bbt, *bbf;
 	struct instruction *def;
 	struct multijmp *jmp;
 
 	switch (DEF_OPCODE(def, insn->src)) {
+	case OP_SEL:	// CGOTO(SEL(x, L1, L2)) --> CBR x, L1, L2
+		if ((bbt = is_label(def->src2)) && (bbf = is_label(def->src3))) {
+			insn->opcode = OP_CBR;
+			insn->bb_true = bbt;
+			insn->bb_false = bbf;
+			return replace_pseudo(insn, &insn->src1, def->cond);
+		}
+		break;
 	case OP_SETVAL:
 		if (def->val->type != EXPR_LABEL)
 			break;
diff --git a/validation/optim/cgoto02.c b/validation/optim/cgoto02.c
index 5869d5b4a24d..932c3164e5ee 100644
--- a/validation/optim/cgoto02.c
+++ b/validation/optim/cgoto02.c
@@ -11,7 +11,6 @@ l2:
 /*
  * check-name: cgoto02
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: %arg1
-- 
2.29.2

[PATCH 4/4] add a new instruction for label-as-value

[Luc Van Oostenryck]

Convert OP_SETVAL of a label into a new instruction: OP_LABEL.
There is 2 reasons to do this:
*) there is slightly less checking to be done in later phases
   (since OP_SETVAL can be for labels but also strings)
*) OP_SETVAL is CSEd but this is largely useless because this
   instruction is hashed on the expression's address and these
   are (most) often not shared. With a separate instruction
   for label expressions, their CSE is now OK because the hashing
   is done on the BB.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 cse.c                        |  9 +++++++++
 example.c                    |  8 +++++---
 linearize.c                  |  6 ++++++
 liveness.c                   |  1 +
 opcode.def                   |  1 +
 simplify.c                   | 36 ++++++++++++++++++++++++------------
 sparse-llvm.c                | 11 +++++++++++
 validation/optim/cse-label.c |  1 -
 8 files changed, 57 insertions(+), 16 deletions(-)

diff --git a/cse.c b/cse.c
index 22dfd4ba5d19..1e58a973ecf6 100644
--- a/cse.c
+++ b/cse.c
@@ -80,6 +80,10 @@ void cse_collect(struct instruction *insn)
 		hash += hashval(insn->src1);
 		break;
 
+	case OP_LABEL:
+		hash += hashval(insn->bb_true);
+		break;
+
 	case OP_SETVAL:
 		hash += hashval(insn->val);
 		break;
@@ -215,6 +219,11 @@ static int insn_compare(const void *_i1, const void *_i2)
 			return i1->src1 < i2->src1 ? -1 : 1;
 		break;
 
+	case OP_LABEL:
+		if (i1->bb_true != i2->bb_true)
+			return i1->bb_true < i2->bb_true ? -1 : 1;
+		break;
+
 	case OP_SETVAL:
 		if (i1->val != i2->val)
 			return i1->val < i2->val ? -1 : 1;
diff --git a/example.c b/example.c
index 8a2b1ab46fe8..0c2ddf50c015 100644
--- a/example.c
+++ b/example.c
@@ -66,6 +66,7 @@ static const char *opcodes[] = {
 	/* Memory */
 	[OP_LOAD] = "load",
 	[OP_STORE] = "store",
+	[OP_LABEL] = "label",
 	[OP_SETVAL] = "set",
 
 	/* Other */
@@ -619,7 +620,7 @@ static struct hardreg *fill_reg(struct bb_state *state, struct hardreg *hardreg,
 	case PSEUDO_ARG:
 	case PSEUDO_REG:
 		def = pseudo->def;
-		if (def && def->opcode == OP_SETVAL) {
+		if (def && (def->opcode == OP_SETVAL || def->opcode == OP_LABEL)) {
 			output_insn(state, "movl $<%s>,%s", show_pseudo(def->target), hardreg->name);
 			break;
 		}
@@ -1375,10 +1376,11 @@ static void generate_one_insn(struct instruction *insn, struct bb_state *state)
 	}
 
 	/*
-	 * OP_SETVAL likewise doesn't actually generate any
+	 * OP_LABEL & OP_SETVAL likewise doesn't actually generate any
 	 * code. On use, the "def" of the pseudo will be
 	 * looked up.
 	 */
+	case OP_LABEL:
 	case OP_SETVAL:
 		break;
 
@@ -1531,7 +1533,7 @@ static void fill_output(struct bb_state *state, pseudo_t pseudo, struct storage
 		return;
 	case PSEUDO_REG:
 		def = pseudo->def;
-		if (def && def->opcode == OP_SETVAL) {
+		if (def && (def->opcode == OP_SETVAL || def->opcode == OP_LABEL)) {
 			write_val_to_storage(state, pseudo, out);
 			return;
 		}
diff --git a/linearize.c b/linearize.c
index ab91113d00eb..4391f09cb0da 100644
--- a/linearize.c
+++ b/linearize.c
@@ -249,6 +249,7 @@ static const char *opcodes[] = {
 	/* Memory */
 	[OP_LOAD] = "load",
 	[OP_STORE] = "store",
+	[OP_LABEL] = "label",
 	[OP_SETVAL] = "set",
 	[OP_SETFVAL] = "setfval",
 	[OP_SYMADDR] = "symaddr",
@@ -345,6 +346,11 @@ const char *show_instruction(struct instruction *insn)
 		buf += sprintf(buf, "%s", show_label(insn->bb_true));
 		break;
 
+	case OP_LABEL:
+		buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
+		buf += sprintf(buf, "%s", show_label(insn->bb_true));
+		break;
+
 	case OP_SETVAL: {
 		struct expression *expr = insn->val;
 		buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
diff --git a/liveness.c b/liveness.c
index 33cd04831fc0..30a9a5b6b169 100644
--- a/liveness.c
+++ b/liveness.c
@@ -92,6 +92,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 		USES(src); USES(target);
 		break;
 
+	case OP_LABEL:
 	case OP_SETVAL:
 	case OP_SETFVAL:
 		DEFINES(target);
diff --git a/opcode.def b/opcode.def
index 2627abd4d894..ba757dae3c5a 100644
--- a/opcode.def
+++ b/opcode.def
@@ -98,6 +98,7 @@ OPCODE(STORE,        BADOP,    BADOP,    BADOP, BADOP, 1, OPF_NONE)
 /* Other */
 OPCODE(PHISOURCE,    BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
 OPCODE(PHI,          BADOP,    BADOP,    BADOP, BADOP, 0, OPF_TARGET)
+OPCODE(LABEL,        BADOP,    BADOP,    BADOP, BADOP, 0, OPF_TARGET)
 OPCODE(SETVAL,       BADOP,    BADOP,    BADOP, BADOP, 0, OPF_TARGET)
 OPCODE(SETFVAL,      BADOP,    BADOP,    BADOP, BADOP, 0, OPF_TARGET)
 OPCODE(CALL,         BADOP,    BADOP,    BADOP, BADOP, 1, OPF_TARGET)
diff --git a/simplify.c b/simplify.c
index 24ecf074206e..e3344434f6d1 100644
--- a/simplify.c
+++ b/simplify.c
@@ -325,7 +325,6 @@ int kill_insn(struct instruction *insn, int force)
 		/* fall through */
 
 	case OP_UNOP ... OP_UNOP_END:
-	case OP_SETVAL:
 	case OP_SLICE:
 		kill_use(&insn->src1);
 		break;
@@ -379,6 +378,8 @@ int kill_insn(struct instruction *insn, int force)
 		return 0;
 
 	case OP_BR:
+	case OP_LABEL:
+	case OP_SETVAL:
 	case OP_SETFVAL:
 	default:
 		break;
@@ -2114,15 +2115,11 @@ found:
 
 static struct basic_block *is_label(pseudo_t pseudo)
 {
-	struct expression *expr;
 	struct instruction *def;
 
-	if (DEF_OPCODE(def, pseudo) != OP_SETVAL)
+	if (DEF_OPCODE(def, pseudo) != OP_LABEL)
 		return NULL;
-	expr = def->val;
-	if (expr->type != EXPR_LABEL)
-		return NULL;
-	return expr->symbol->bb_target;
+	return def->bb_true;
 }
 
 static int simplify_cgoto(struct instruction *insn)
@@ -2141,10 +2138,8 @@ static int simplify_cgoto(struct instruction *insn)
 			return replace_pseudo(insn, &insn->src1, def->cond);
 		}
 		break;
-	case OP_SETVAL:
-		if (def->val->type != EXPR_LABEL)
-			break;
-		target = def->val->symbol->bb_target;
+	case OP_LABEL:
+		target = def->bb_true;
 		if (!target->ep)
 			return 0;
 		FOR_EACH_PTR(insn->multijmp_list, jmp) {
@@ -2162,6 +2157,21 @@ static int simplify_cgoto(struct instruction *insn)
 	return 0;
 }
 
+static int simplify_setval(struct instruction *insn)
+{
+	struct expression *val = insn->val;
+
+	switch (val->type) {
+	case EXPR_LABEL:
+		insn->opcode = OP_LABEL;
+		insn->bb_true = val->symbol->bb_target;
+		return REPEAT_CSE;
+	default:
+		break;
+	}
+	return 0;
+}
+
 int simplify_instruction(struct instruction *insn)
 {
 	unsigned flags;
@@ -2227,9 +2237,11 @@ int simplify_instruction(struct instruction *insn)
 		return replace_with_pseudo(insn, insn->src);
 	case OP_SLICE:
 		break;
-	case OP_SETVAL:
+	case OP_LABEL:
 	case OP_SETFVAL:
 		break;
+	case OP_SETVAL:
+		return simplify_setval(insn);
 	case OP_PHI:
 		return clean_up_phi(insn);
 	case OP_PHISOURCE:
diff --git a/sparse-llvm.c b/sparse-llvm.c
index c984dc877a61..972ddfeea54f 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -935,6 +935,14 @@ static void output_op_fpcast(struct function *fn, struct instruction *insn)
 	insn->target->priv = target;
 }
 
+static void output_op_label(struct function *fn, struct instruction *insn)
+{
+	LLVMValueRef target;
+
+	target = LLVMBlockAddress(fn->fn, insn->bb_true->priv);
+	insn->target->priv = target;
+}
+
 static void output_op_setval(struct function *fn, struct instruction *insn)
 {
 	struct expression *val = insn->val;
@@ -975,6 +983,9 @@ static void output_insn(struct function *fn, struct instruction *insn)
 	case OP_SYMADDR:
 		assert(0);
 		break;
+	case OP_LABEL:
+		output_op_label(fn, insn);
+		break;
 	case OP_SETVAL:
 		output_op_setval(fn, insn);
 		break;
diff --git a/validation/optim/cse-label.c b/validation/optim/cse-label.c
index e42968204615..c3b552d3dec9 100644
--- a/validation/optim/cse-label.c
+++ b/validation/optim/cse-label.c
@@ -7,7 +7,6 @@ label:
 /*
  * check-name: cse-label
  * check-command: test-linearize -Wno-decl $file
- * check-known-to-fail
  *
  * check-output-ignore
  * check-output-returns: 1
-- 
2.29.2

Re: [PATCH 0/4] simplification of computed goto

[Linus Torvalds]

On Sat, Nov 21, 2020 at 12:54 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> This series contains some simplification of computed gotos with
> 1 or 2 possible target as well as a new instruction which now
> really allows the CSE of 'labels-as-values'.

Looks sane, but where did you actually find cases of this in real life?

I think we have one computed goto in the kernel, that does an array
label load. They are very rare, and when they are used, that tends to
be the normal pattern.

Just about the only place I've ever seen them are in that kind of
interpreter loops for instruction dispatch tables.

          Linus

Re: [PATCH 0/4] simplification of computed goto

[Luc Van Oostenryck]

On Sat, Nov 21, 2020 at 01:09:50PM -0800, Linus Torvalds wrote:
> On Sat, Nov 21, 2020 at 12:54 PM Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > This series contains some simplification of computed gotos with
> > 1 or 2 possible target as well as a new instruction which now
> > really allows the CSE of 'labels-as-values'.
> 
> Looks sane, but where did you actually find cases of this in real life?
>
> I think we have one computed goto in the kernel, that does an array
> label load. They are very rare, and when they are used, that tends to
> be the normal pattern.
> 

Bah, they're not really from real life.
When IR and optimizations are concerned, I'm using code from some
testsuites (GCC, LLVM, some benchmarks, code I've generated myself)
to check for anything abnormal and sometimes when inspecting the
results I fall on some testcases that doesn't make sense. Sometimes
it's because of some errors from my part but it also happens it's
one of these silly/exotic transformations.

So, yes, I'm fully aware that these patches (and some other
'optimizations' I'm sometimes adding) have practically no values
but they just make things easier for me when comparing results.

> Just about the only place I've ever seen them are in that kind of
> interpreter loops for instruction dispatch tables.

Yes. They were also fundamental to a prolog-to-C compiler I wrote
many years ago. This maybe explains some fondness I've for them.

-- Luc

Re: [PATCH 0/4] simplification of computed goto

[Linus Torvalds]

On Sat, Nov 21, 2020 at 1:40 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Bah, they're not really from real life.

Ok, I was worried I was missing something, and you'd find some really
odd kernel code ;)

             Linus