add a new instruction for label-as-value

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>

10 files changed, 63 insertions, 17 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 ab91113d..4391f09c 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 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 24ecf074..01882b50 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;
@@ -2228,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:
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/cse-label.c b/validation/optim/cse-label.c
index e4296820..c3b552d3 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