Merge branch 'optim-cgoto' into next

* simplification of computed gotos with 1 or 2 targets

12 files changed, 159 insertions, 6 deletions

diff --git a/Documentation/IR.rst b/Documentation/IR.rst
index 6330ee9c..38df84ff 100644
--- a/Documentation/IR.rst
+++ b/Documentation/IR.rst
@@ -352,13 +352,20 @@ Others
 	* .type: type of the literal & .target
 
 .. op:: OP_SETVAL
-	Create a pseudo corresponding to a string literal or a label-as-value.
-	The value is given as an expression EXPR_STRING or EXPR_LABEL.
+	Create a pseudo corresponding to a string literal.
+	The value is given as an expression EXPR_STRING.
 
 	* .val: (expression) input expression
 	* .target: the resulting value
 	* .type: type of .target, the value
 
+.. op:: OP_LABEL
+	Create a pseudo corresponding to a label-as-value.
+
+	* .bb_true: the BB corresponding to the label
+	* .target: the resulting value
+	* .type: type of .target (void \*)
+
 .. op:: OP_PHI
 	Phi-node (for SSA form).
 
diff --git a/cse.c b/cse.c
index 22dfd4ba..1e58a973 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 8a2b1ab4..0c2ddf50 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/ir.c b/ir.c
index 2e284c25..2a932f8f 100644
--- a/ir.c
+++ b/ir.c
@@ -175,6 +175,7 @@ static int validate_insn(struct entrypoint *ep, struct instruction *insn)
 		break;
 
 	case OP_ENTRY:
+	case OP_LABEL:
 	case OP_SETVAL:
 	default:
 		break;
diff --git a/linearize.c b/linearize.c
index 104f5747..8a3cf09b 100644
--- a/linearize.c
+++ b/linearize.c
@@ -245,6 +245,7 @@ static const char *opcodes[] = {
 	/* Memory */
 	[OP_LOAD] = "load",
 	[OP_STORE] = "store",
+	[OP_LABEL] = "label",
 	[OP_SETVAL] = "set",
 	[OP_SETFVAL] = "setfval",
 	[OP_SYMADDR] = "symaddr",
@@ -341,6 +342,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 33cd0483..30a9a5b6 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 2627abd4..ba757dae 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 a0e23d6d..2e002cec 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;
@@ -2112,6 +2113,65 @@ found:
 	return REPEAT_CSE;
 }
 
+static struct basic_block *is_label(pseudo_t pseudo)
+{
+	struct instruction *def;
+
+	if (DEF_OPCODE(def, pseudo) != OP_LABEL)
+		return NULL;
+	return def->bb_true;
+}
+
+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_LABEL:
+		target = def->bb_true;
+		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;
+}
+
+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;
@@ -2178,6 +2238,8 @@ int simplify_instruction(struct instruction *insn)
 	case OP_SLICE:
 		break;
 	case OP_SETVAL:
+		return simplify_setval(insn);
+	case OP_LABEL:
 	case OP_SETFVAL:
 		break;
 	case OP_PHI:
@@ -2190,6 +2252,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/sparse-llvm.c b/sparse-llvm.c
index c984dc87..658744ee 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -935,6 +935,11 @@ 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)
+{
+	insn->target->priv = LLVMBlockAddress(fn->fn, insn->bb_true->priv);
+}
+
 static void output_op_setval(struct function *fn, struct instruction *insn)
 {
 	struct expression *val = insn->val;
@@ -975,6 +980,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/cgoto01.c b/validation/optim/cgoto01.c
new file mode 100644
index 00000000..94b2c2c4
--- /dev/null
+++ b/validation/optim/cgoto01.c
@@ -0,0 +1,24 @@
+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-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 00000000..932c3164
--- /dev/null
+++ b/validation/optim/cgoto02.c
@@ -0,0 +1,17 @@
+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-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 00000000..c3b552d3
--- /dev/null
+++ b/validation/optim/cse-label.c
@@ -0,0 +1,13 @@
+int foo(void)
+{
+label:
+	return &&label == &&label;
+}
+
+/*
+ * check-name: cse-label
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-ignore
+ * check-output-returns: 1
+ */