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
