[PATCH 0/2] split OP_BR between OP_BR & OP_CBR

[PATCH 0/2] split OP_BR between OP_BR & OP_CBR

[Luc Van Oostenryck]

This series introduces a new instruction opcode (OP_CBR)
for conditional branches. Previously both conditional and
non-conditional branches used the OP_BR opcode which is
now reserved for non-conditional branches.

The motivation is the correctness of the test between
the two kind of branches and an added benefit is the
simplicity of this test now.

Luc Van Oostenryck (2):
  split OP_BR between unconditional & conditional: OP_CBR
  remove unused helper is_branch_goto()

 example.c                       |   2 +
 flow.c                          |  13 ++--
 linearize.c                     |  14 +++--
 linearize.h                     |   5 +-
 liveness.c                      |   3 +-
 simplify.c                      |  11 ++--
 sparse-llvm.c                   |  25 ++++----
 validation/loop-linearization.c | 136 ++++++++++++++++++++++++++++++++++++++++
 8 files changed, 176 insertions(+), 33 deletions(-)
 create mode 100644 validation/loop-linearization.c

-- 
2.11.0

[PATCH 1/2] split OP_BR between unconditional & conditional: OP_CBR

[Luc Van Oostenryck]

OP_BR instructions exist in two flavours: conditional &
non-conditional. There is some significant differences
between them:
1) one has an operand (and thus needs correct handling of
   its usage, must be handled in liveness analysis, ..) while
   the other has none
2) one has two BB targets, the other only one.

There is essentially no places in the code where both flavours
are handled the same. Sometimes they both must be handled but
each with their specificities but in most cases only one of
them is concerned and we need to filter out the other one.
In both cases it means that we need to make to make a test
to know what kind we're dealing with.

There is a problem with this because there is several ways
to test this and they are not exactly equivalent:
1) testing if insn->cond is NULL
2) testing if one of insn->bb_true or ->bb_false is NULL.
There exist also an helper (is_branch_goto()) which does
the second tests but which is never used.

It appears that the first test should not be used because
in some cases an conditional OP_BR is changed into
a non-conditional one by (amongst others things) setting
it's ->cond to VOID. We should thus always use the second
test (which need two compares with NULL).

This could be corrected in several ways (like changing all
the places wheer the first test is used, use the helper
everywhere or never set ->cond to VOID) but the simplest
is to simply split them in two separated instructions:
OP_BR & OP_CBR, especailly given the fact that in most cases
the OP_BR was first selected by a switch (opcode).

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 example.c                       |   2 +
 flow.c                          |  13 ++--
 linearize.c                     |  14 +++--
 linearize.h                     |   1 +
 liveness.c                      |   3 +-
 simplify.c                      |  11 ++--
 sparse-llvm.c                   |  25 ++++----
 validation/loop-linearization.c | 136 ++++++++++++++++++++++++++++++++++++++++
 8 files changed, 176 insertions(+), 29 deletions(-)
 create mode 100644 validation/loop-linearization.c

diff --git a/example.c b/example.c
index 24444c6c0..691e0f97c 100644
--- a/example.c
+++ b/example.c
@@ -23,6 +23,7 @@ static const char *opcodes[] = {
 	/* Terminator */
 	[OP_RET] = "ret",
 	[OP_BR] = "br",
+	[OP_CBR] = "cbr",
 	[OP_SWITCH] = "switch",
 	[OP_INVOKE] = "invoke",
 	[OP_COMPUTEDGOTO] = "jmp *",
@@ -1428,6 +1429,7 @@ static void generate_one_insn(struct instruction *insn, struct bb_state *state)
 		break;
 
 	case OP_BR:
+	case OP_CBR:
 		generate_branch(state, insn);
 		break;
 
diff --git a/flow.c b/flow.c
index 088c21785..7730e70f1 100644
--- a/flow.c
+++ b/flow.c
@@ -111,7 +111,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 		br = last_instruction(source->insns);
 		if (!br)
 			continue;
-		if (br->opcode != OP_BR)
+		if (br->opcode != OP_CBR && br->opcode != OP_BR)
 			continue;
 		true = pseudo_truth_value(pseudo);
 		if (true < 0)
@@ -176,7 +176,7 @@ static int simplify_branch_branch(struct basic_block *bb, struct instruction *br
 	if (target == bb)
 		return 0;
 	insn = last_instruction(target->insns);
-	if (!insn || insn->opcode != OP_BR || insn->cond != br->cond)
+	if (!insn || insn->opcode != OP_CBR  || insn->cond != br->cond)
 		return 0;
 	/*
 	 * Ahhah! We've found a branch to a branch on the same conditional!
@@ -218,7 +218,7 @@ static int simplify_branch_nodes(struct entrypoint *ep)
 	FOR_EACH_PTR(ep->bbs, bb) {
 		struct instruction *br = last_instruction(bb->insns);
 
-		if (!br || br->opcode != OP_BR || !br->bb_false)
+		if (!br || br->opcode != OP_CBR)
 			continue;
 		changed |= simplify_one_branch(bb, br);
 	} END_FOR_EACH_PTR(bb);
@@ -811,9 +811,10 @@ static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old
 		return 0;
 
 	switch (insn->opcode) {
+	case OP_CBR:
+		changed |= rewrite_branch(bb, &insn->bb_false, old, new);
 	case OP_BR:
 		changed |= rewrite_branch(bb, &insn->bb_true, old, new);
-		changed |= rewrite_branch(bb, &insn->bb_false, old, new);
 		assert(changed);
 		return changed;
 	case OP_SWITCH: {
@@ -886,9 +887,10 @@ static void vrfy_children(struct basic_block *bb)
 	}
 	switch (br->opcode) {
 		struct multijmp *jmp;
+	case OP_CBR:
+		vrfy_bb_in_list(br->bb_false, bb->children);
 	case OP_BR:
 		vrfy_bb_in_list(br->bb_true, bb->children);
-		vrfy_bb_in_list(br->bb_false, bb->children);
 		break;
 	case OP_SWITCH:
 	case OP_COMPUTEDGOTO:
@@ -945,6 +947,7 @@ void pack_basic_blocks(struct entrypoint *ep)
 			switch (first->opcode) {
 			case OP_NOP: case OP_LNOP: case OP_SNOP:
 				continue;
+			case OP_CBR:
 			case OP_BR: {
 				struct basic_block *replace;
 				replace = rewrite_branch_bb(bb, first);
diff --git a/linearize.c b/linearize.c
index 99203d915..3b4741822 100644
--- a/linearize.c
+++ b/linearize.c
@@ -169,6 +169,7 @@ static const char *opcodes[] = {
 	/* Terminator */
 	[OP_RET] = "ret",
 	[OP_BR] = "br",
+	[OP_CBR] = "cbr",
 	[OP_SWITCH] = "switch",
 	[OP_INVOKE] = "invoke",
 	[OP_COMPUTEDGOTO] = "jmp *",
@@ -303,12 +304,13 @@ const char *show_instruction(struct instruction *insn)
 		if (insn->src && insn->src != VOID)
 			buf += sprintf(buf, "%s", show_pseudo(insn->src));
 		break;
+
+	case OP_CBR:
+		buf += sprintf(buf, "%s, .L%u, .L%u", show_pseudo(insn->cond), insn->bb_true->nr, insn->bb_false->nr);
+		break;
+
 	case OP_BR:
-		if (insn->bb_true && insn->bb_false) {
-			buf += sprintf(buf, "%s, .L%u, .L%u", show_pseudo(insn->cond), insn->bb_true->nr, insn->bb_false->nr);
-			break;
-		}
-		buf += sprintf(buf, ".L%u", insn->bb_true ? insn->bb_true->nr : insn->bb_false->nr);
+		buf += sprintf(buf, ".L%u", insn->bb_true->nr);
 		break;
 
 	case OP_SYMADDR: {
@@ -723,7 +725,7 @@ static void add_branch(struct entrypoint *ep, struct expression *expr, pseudo_t
 	struct instruction *br;
 
 	if (bb_reachable(bb)) {
-       		br = alloc_instruction(OP_BR, 0);
+		br = alloc_instruction(OP_CBR, 0);
 		use_pseudo(br, cond, &br->cond);
 		br->bb_true = bb_true;
 		br->bb_false = bb_false;
diff --git a/linearize.h b/linearize.h
index 5c938cd5d..2aa255154 100644
--- a/linearize.h
+++ b/linearize.h
@@ -137,6 +137,7 @@ enum opcode {
 	OP_TERMINATOR,
 	OP_RET = OP_TERMINATOR,
 	OP_BR,
+	OP_CBR,
 	OP_SWITCH,
 	OP_INVOKE,
 	OP_COMPUTEDGOTO,
diff --git a/liveness.c b/liveness.c
index 2e5139433..7461738b4 100644
--- a/liveness.c
+++ b/liveness.c
@@ -56,7 +56,8 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 		USES(src);
 		break;
 
-	case OP_BR: case OP_SWITCH:
+	case OP_CBR:
+	case OP_SWITCH:
 		USES(cond);
 		break;
 
diff --git a/simplify.c b/simplify.c
index 3bc9985e8..c157c6153 100644
--- a/simplify.c
+++ b/simplify.c
@@ -67,7 +67,7 @@ static int if_convert_phi(struct instruction *insn)
 	 * stuff. Verify that here.
 	 */
 	br = last_instruction(source->insns);
-	if (!br || br->opcode != OP_BR)
+	if (!br || br->opcode != OP_CBR)
 		return 0;
 
 	assert(br->cond);
@@ -227,11 +227,7 @@ void kill_insn(struct instruction *insn, int force)
 		repeat_phase |= REPEAT_SYMBOL_CLEANUP;
 		break;
 
-	case OP_BR:
-		if (!insn->bb_true || !insn->bb_false)
-			break;
-		/* fall through */
-
+	case OP_CBR:
 	case OP_COMPUTEDGOTO:
 		kill_use(&insn->cond);
 		break;
@@ -266,6 +262,7 @@ void kill_insn(struct instruction *insn, int force)
 		/* ignore */
 		return;
 
+	case OP_BR:
 	default:
 		break;
 	}
@@ -1052,6 +1049,7 @@ static int simplify_branch(struct instruction *insn)
 		insn->bb_false = NULL;
 		kill_use(&insn->cond);
 		insn->cond = NULL;
+		insn->opcode = OP_BR;
 		return REPEAT_CSE;
 	}
 
@@ -1181,6 +1179,7 @@ int simplify_instruction(struct instruction *insn)
 		break;
 	case OP_SEL:
 		return simplify_select(insn);
+	case OP_CBR:
 	case OP_BR:
 		return simplify_branch(insn);
 	case OP_SWITCH:
diff --git a/sparse-llvm.c b/sparse-llvm.c
index 3d2218ef6..9f362b3ed 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -642,19 +642,19 @@ static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
 	return value;
 }
 
-static void output_op_br(struct function *fn, struct instruction *br)
+static void output_op_cbr(struct function *fn, struct instruction *br)
 {
-	if (br->cond) {
-		LLVMValueRef cond = bool_value(fn,
-				pseudo_to_value(fn, br, br->cond));
+	LLVMValueRef cond = bool_value(fn,
+			pseudo_to_value(fn, br, br->cond));
 
-		LLVMBuildCondBr(fn->builder, cond,
-				br->bb_true->priv,
-				br->bb_false->priv);
-	} else
-		LLVMBuildBr(fn->builder,
-			    br->bb_true ? br->bb_true->priv :
-			    br->bb_false->priv);
+	LLVMBuildCondBr(fn->builder, cond,
+			br->bb_true->priv,
+			br->bb_false->priv);
+}
+
+static void output_op_br(struct function *fn, struct instruction *br)
+{
+	LLVMBuildBr(fn->builder, br->bb_true->priv);
 }
 
 static void output_op_sel(struct function *fn, struct instruction *insn)
@@ -810,6 +810,9 @@ static void output_insn(struct function *fn, struct instruction *insn)
 	case OP_BR:
 		output_op_br(fn, insn);
 		break;
+	case OP_CBR:
+		output_op_cbr(fn, insn);
+		break;
 	case OP_SYMADDR:
 		assert(0);
 		break;
diff --git a/validation/loop-linearization.c b/validation/loop-linearization.c
new file mode 100644
index 000000000..25c6dfb87
--- /dev/null
+++ b/validation/loop-linearization.c
@@ -0,0 +1,136 @@
+extern int p(int);
+
+static int ffor(void)
+{
+	int i;
+	for (int i = 0; i < 10; i++) {
+		if (!p(i))
+			return 0;
+	}
+	return 1;
+}
+
+static int fwhile(void)
+{
+	int i = 0;
+	while (i < 10) {
+		if (!p(i))
+			return 0;
+		i++;
+	}
+	return 1;
+}
+
+static int fdo(void)
+{
+	int i = 0;
+	do {
+		if (!p(i))
+			return 0;
+	} while (i++ < 10);
+	return 1;
+}
+
+/*
+ * check-name: loop-linearization
+ * check-command: test-linearize $file
+ *
+ * check-output-start
+ffor:
+.L0:
+	<entry-point>
+	phisrc.32   %phi5(i) <- $0
+	br          .L4
+
+.L4:
+	phi.32      %r1(i) <- %phi5(i), %phi6(i)
+	setlt.32    %r2 <- %r1(i), $10
+	cbr         %r2, .L1, .L3
+
+.L1:
+	call.32     %r4 <- p, %r1(i)
+	cbr         %r4, .L2, .L5
+
+.L5:
+	phisrc.32   %phi1(return) <- $0
+	br          .L7
+
+.L2:
+	add.32      %r7 <- %r1(i), $1
+	phisrc.32   %phi6(i) <- %r7
+	br          .L4
+
+.L3:
+	phisrc.32   %phi2(return) <- $1
+	br          .L7
+
+.L7:
+	phi.32      %r5 <- %phi1(return), %phi2(return)
+	ret.32      %r5
+
+
+fwhile:
+.L8:
+	<entry-point>
+	phisrc.32   %phi11(i) <- $0
+	br          .L12
+
+.L12:
+	phi.32      %r8(i) <- %phi11(i), %phi12(i)
+	setlt.32    %r9 <- %r8(i), $10
+	cbr         %r9, .L9, .L11
+
+.L9:
+	call.32     %r11 <- p, %r8(i)
+	cbr         %r11, .L14, .L13
+
+.L13:
+	phisrc.32   %phi7(return) <- $0
+	br          .L15
+
+.L14:
+	add.32      %r14 <- %r8(i), $1
+	phisrc.32   %phi12(i) <- %r14
+	br          .L12
+
+.L11:
+	phisrc.32   %phi8(return) <- $1
+	br          .L15
+
+.L15:
+	phi.32      %r12 <- %phi7(return), %phi8(return)
+	ret.32      %r12
+
+
+fdo:
+.L16:
+	<entry-point>
+	phisrc.32   %phi16(i) <- $0
+	br          .L17
+
+.L17:
+	phi.32      %r15(i) <- %phi16(i), %phi17(i)
+	call.32     %r16 <- p, %r15(i)
+	cbr         %r16, .L18, .L20
+
+.L20:
+	phisrc.32   %phi13(return) <- $0
+	br          .L22
+
+.L18:
+	add.32      %r19 <- %r15(i), $1
+	setlt.32    %r20 <- %r15(i), $10
+	phisrc.32   %phi17(i) <- %r19
+	cbr         %r20, .L17, .L19
+
+.L19:
+	phisrc.32   %phi14(return) <- $1
+	br          .L22
+
+.L22:
+	phi.32      %r17 <- %phi13(return), %phi14(return)
+	ret.32      %r17
+
+
+ * check-output-end
+ */
-- 
2.11.0

[PATCH 2/2] remove unused helper is_branch_goto()

[Luc Van Oostenryck]

This helper is also made unneeded since the introduction of OP_CBR.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h | 4 ----
 1 file changed, 4 deletions(-)

diff --git a/linearize.h b/linearize.h
index 2aa255154..bac82d7ff 100644
--- a/linearize.h
+++ b/linearize.h
@@ -237,10 +237,6 @@ struct basic_block {
 	};
 };
 
-static inline int is_branch_goto(struct instruction *br)
-{
-	return br && br->opcode==OP_BR && (!br->bb_true || !br->bb_false);
-}
 
 static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
 {
-- 
2.11.0

Re: [PATCH 1/2] split OP_BR between unconditional & conditional: OP_CBR

[Christopher Li]

On Sat, Feb 18, 2017 at 9:28 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> This could be corrected in several ways (like changing all
> the places wheer the first test is used, use the helper
> everywhere or never set ->cond to VOID) but the simplest
> is to simply split them in two separated instructions:
> OP_BR & OP_CBR, especailly given the fact that in most cases
> the OP_BR was first selected by a switch (opcode).

I think that change itself is fine. The implications is that all sparse
back end user will need to be updated to use CBR instead of BR.

Sparse can be compiled as a lib to link against. We might want to
have some API version for sprase to check which version of sparse
it is.  Currently there is SPARSE_VERSION but that is a macro
which does not reflect in the lib version of sparse. That is a separate
patch though.

> @@ -811,9 +811,10 @@ static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old
>                 return 0;
>
>         switch (insn->opcode) {
> +       case OP_CBR:
> +               changed |= rewrite_branch(bb, &insn->bb_false, old, new);

We can use some comment of fall though the case here.

>         case OP_BR:
>                 changed |= rewrite_branch(bb, &insn->bb_true, old, new);
> -               changed |= rewrite_branch(bb, &insn->bb_false, old, new);
>                 assert(changed);
>                 return changed;
>         case OP_SWITCH: {
> @@ -886,9 +887,10 @@ static void vrfy_children(struct basic_block *bb)
>         }
>         switch (br->opcode) {
>                 struct multijmp *jmp;
> +       case OP_CBR:
> +               vrfy_bb_in_list(br->bb_false, bb->children);

Same here.

Chris

Re: [PATCH 1/2] split OP_BR between unconditional & conditional: OP_CBR

[Luc Van Oostenryck]

On Mon, Feb 27, 2017 at 4:02 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Sat, Feb 18, 2017 at 9:28 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> This could be corrected in several ways (like changing all
>> the places wheer the first test is used, use the helper
>> everywhere or never set ->cond to VOID) but the simplest
>> is to simply split them in two separated instructions:
>> OP_BR & OP_CBR, especailly given the fact that in most cases
>> the OP_BR was first selected by a switch (opcode).
>
> I think that change itself is fine. The implications is that all sparse
> back end user will need to be updated to use CBR instead of BR.

Yes, indeed.
BTW, I've often wondered about backend using sparse,
do you know any others than smatch (and I think smatch won't
be impacted here becaue it don't use the linearized code but
I can be wrong)?

> Sparse can be compiled as a lib to link against. We might want to
> have some API version for sprase to check which version of sparse
> it is.  Currently there is SPARSE_VERSION but that is a macro
> which does not reflect in the lib version of sparse.

Yes, but how useful such a macro really is?
A backend still need to be changed to be able to use it.

> That is a separate patch though.

Sure, I'll do something for it.

>> @@ -811,9 +811,10 @@ static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old
>>                 return 0;
>>
>>         switch (insn->opcode) {
>> +       case OP_CBR:
>> +               changed |= rewrite_branch(bb, &insn->bb_false, old, new);
>
> We can use some comment of fall though the case here.

Sure, I'll send a new version.
>> @@ -886,9 +887,10 @@ static void vrfy_children(struct basic_block *bb)
>>         }
>>         switch (br->opcode) {
>>                 struct multijmp *jmp;
>> +       case OP_CBR:
>> +               vrfy_bb_in_list(br->bb_false, bb->children);
>
> Same here.

Yup.

Luc

[PATCH v2 0/2] split OP_BR between OP_BR & OP_CBR

[Luc Van Oostenryck]

This series introduces a new instruction opcode (OP_CBR)
for conditional branches. Previously both conditional and
non-conditional branches used the OP_BR opcode which is
now reserved for non-conditional branches.

The motivation is the correctness of the test between
the two kind of branches and an added benefit is the
simplicity of this test now.


Changes since v1:
- add missing '/* fall through */' 
- convert 2 more tests of ->cond/->bb_{true,false}
  into tests of ->opcode == OP_CBR/OP_BR

Luc Van Oostenryck (2):
  split OP_BR between unconditional & conditional: OP_CBR
  remove unused helper is_branch_goto()

 example.c                       |   2 +
 flow.c                          |  17 +++--
 linearize.c                     |  14 +++--
 linearize.h                     |   5 +-
 liveness.c                      |   3 +-
 simplify.c                      |  15 ++---
 sparse-llvm.c                   |  25 ++++----
 validation/loop-linearization.c | 136 ++++++++++++++++++++++++++++++++++++++++
 8 files changed, 179 insertions(+), 38 deletions(-)
 create mode 100644 validation/loop-linearization.c

-- 
2.11.1

[PATCH v2 1/2] split OP_BR between unconditional & conditional: OP_CBR

[Luc Van Oostenryck]

OP_BR instructions exist in two flavours, relatively much
differentiated: conditional & non-conditional. One has an
operand (and thus its usage need to be cared for, must be
handled in liveness analysis, ..) the other has not; one has
two BB target, the other only one.

There is essentially no places in the code where both flavours
are handled the same. Sometimes they both must be handled but
each with their specificities but in most cases only one of
them is concerned and we need to filter out the other one.
In both cases it means that we need to check what kind we're
dealing with.

There is already a problem with this because there is
several ways to test which kind an OP_BR is and they
are not exactly equivalent:
1) testing if insn->cond is NULL
2) testing if one of insn->bb_true or ->bb_false is NULL.
There exist also an helper (is_branch_goto()) which does
the second tests but which is never used.

It appears that the first test should not be used because
in some cases an conditional OP_BR is changed into
a non-conditional one by (amongst others things) setting
it's ->cond to VOID. We should thus always use the seconds
test (which need two compares with NULL).

This could be corrected in several ways (like changing all
the places wheer the first test is used, use the helper
everywhere or never set ->cond to VOID) but the simplest
is to simply split them in two separated instructions:
OP_BR & OP_CBR, especailly given the fact that in most cases
the OP_BR was first selected by a switch (opcode).

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 example.c                       |   2 +
 flow.c                          |  17 +++--
 linearize.c                     |  14 +++--
 linearize.h                     |   1 +
 liveness.c                      |   3 +-
 simplify.c                      |  15 ++---
 sparse-llvm.c                   |  25 ++++----
 validation/loop-linearization.c | 136 ++++++++++++++++++++++++++++++++++++++++
 8 files changed, 179 insertions(+), 34 deletions(-)
 create mode 100644 validation/loop-linearization.c

diff --git a/example.c b/example.c
index 24444c6c0..691e0f97c 100644
--- a/example.c
+++ b/example.c
@@ -23,6 +23,7 @@ static const char *opcodes[] = {
 	/* Terminator */
 	[OP_RET] = "ret",
 	[OP_BR] = "br",
+	[OP_CBR] = "cbr",
 	[OP_SWITCH] = "switch",
 	[OP_INVOKE] = "invoke",
 	[OP_COMPUTEDGOTO] = "jmp *",
@@ -1428,6 +1429,7 @@ static void generate_one_insn(struct instruction *insn, struct bb_state *state)
 		break;
 
 	case OP_BR:
+	case OP_CBR:
 		generate_branch(state, insn);
 		break;
 
diff --git a/flow.c b/flow.c
index 088c21785..a5332203f 100644
--- a/flow.c
+++ b/flow.c
@@ -111,7 +111,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 		br = last_instruction(source->insns);
 		if (!br)
 			continue;
-		if (br->opcode != OP_BR)
+		if (br->opcode != OP_CBR && br->opcode != OP_BR)
 			continue;
 		true = pseudo_truth_value(pseudo);
 		if (true < 0)
@@ -176,7 +176,7 @@ static int simplify_branch_branch(struct basic_block *bb, struct instruction *br
 	if (target == bb)
 		return 0;
 	insn = last_instruction(target->insns);
-	if (!insn || insn->opcode != OP_BR || insn->cond != br->cond)
+	if (!insn || insn->opcode != OP_CBR || insn->cond != br->cond)
 		return 0;
 	/*
 	 * Ahhah! We've found a branch to a branch on the same conditional!
@@ -218,7 +218,7 @@ static int simplify_branch_nodes(struct entrypoint *ep)
 	FOR_EACH_PTR(ep->bbs, bb) {
 		struct instruction *br = last_instruction(bb->insns);
 
-		if (!br || br->opcode != OP_BR || !br->bb_false)
+		if (!br || br->opcode != OP_CBR)
 			continue;
 		changed |= simplify_one_branch(bb, br);
 	} END_FOR_EACH_PTR(bb);
@@ -811,9 +811,11 @@ static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old
 		return 0;
 
 	switch (insn->opcode) {
+	case OP_CBR:
+		changed |= rewrite_branch(bb, &insn->bb_false, old, new);
+		/* fall through */
 	case OP_BR:
 		changed |= rewrite_branch(bb, &insn->bb_true, old, new);
-		changed |= rewrite_branch(bb, &insn->bb_false, old, new);
 		assert(changed);
 		return changed;
 	case OP_SWITCH: {
@@ -835,7 +837,7 @@ static struct basic_block * rewrite_branch_bb(struct basic_block *bb, struct ins
 	struct basic_block *target = br->bb_true;
 	struct basic_block *false = br->bb_false;
 
-	if (target && false) {
+	if (br->opcode == OP_CBR) {
 		pseudo_t cond = br->cond;
 		if (cond->type != PSEUDO_VAL)
 			return NULL;
@@ -886,9 +888,11 @@ static void vrfy_children(struct basic_block *bb)
 	}
 	switch (br->opcode) {
 		struct multijmp *jmp;
+	case OP_CBR:
+		vrfy_bb_in_list(br->bb_false, bb->children);
+		/* fall through */
 	case OP_BR:
 		vrfy_bb_in_list(br->bb_true, bb->children);
-		vrfy_bb_in_list(br->bb_false, bb->children);
 		break;
 	case OP_SWITCH:
 	case OP_COMPUTEDGOTO:
@@ -945,6 +949,7 @@ void pack_basic_blocks(struct entrypoint *ep)
 			switch (first->opcode) {
 			case OP_NOP: case OP_LNOP: case OP_SNOP:
 				continue;
+			case OP_CBR:
 			case OP_BR: {
 				struct basic_block *replace;
 				replace = rewrite_branch_bb(bb, first);
diff --git a/linearize.c b/linearize.c
index 99203d915..3b4741822 100644
--- a/linearize.c
+++ b/linearize.c
@@ -169,6 +169,7 @@ static const char *opcodes[] = {
 	/* Terminator */
 	[OP_RET] = "ret",
 	[OP_BR] = "br",
+	[OP_CBR] = "cbr",
 	[OP_SWITCH] = "switch",
 	[OP_INVOKE] = "invoke",
 	[OP_COMPUTEDGOTO] = "jmp *",
@@ -303,12 +304,13 @@ const char *show_instruction(struct instruction *insn)
 		if (insn->src && insn->src != VOID)
 			buf += sprintf(buf, "%s", show_pseudo(insn->src));
 		break;
+
+	case OP_CBR:
+		buf += sprintf(buf, "%s, .L%u, .L%u", show_pseudo(insn->cond), insn->bb_true->nr, insn->bb_false->nr);
+		break;
+
 	case OP_BR:
-		if (insn->bb_true && insn->bb_false) {
-			buf += sprintf(buf, "%s, .L%u, .L%u", show_pseudo(insn->cond), insn->bb_true->nr, insn->bb_false->nr);
-			break;
-		}
-		buf += sprintf(buf, ".L%u", insn->bb_true ? insn->bb_true->nr : insn->bb_false->nr);
+		buf += sprintf(buf, ".L%u", insn->bb_true->nr);
 		break;
 
 	case OP_SYMADDR: {
@@ -723,7 +725,7 @@ static void add_branch(struct entrypoint *ep, struct expression *expr, pseudo_t
 	struct instruction *br;
 
 	if (bb_reachable(bb)) {
-       		br = alloc_instruction(OP_BR, 0);
+		br = alloc_instruction(OP_CBR, 0);
 		use_pseudo(br, cond, &br->cond);
 		br->bb_true = bb_true;
 		br->bb_false = bb_false;
diff --git a/linearize.h b/linearize.h
index 5c938cd5d..2aa255154 100644
--- a/linearize.h
+++ b/linearize.h
@@ -137,6 +137,7 @@ enum opcode {
 	OP_TERMINATOR,
 	OP_RET = OP_TERMINATOR,
 	OP_BR,
+	OP_CBR,
 	OP_SWITCH,
 	OP_INVOKE,
 	OP_COMPUTEDGOTO,
diff --git a/liveness.c b/liveness.c
index 2e5139433..7461738b4 100644
--- a/liveness.c
+++ b/liveness.c
@@ -56,7 +56,8 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 		USES(src);
 		break;
 
-	case OP_BR: case OP_SWITCH:
+	case OP_CBR:
+	case OP_SWITCH:
 		USES(cond);
 		break;
 
diff --git a/simplify.c b/simplify.c
index 3bc9985e8..71687b940 100644
--- a/simplify.c
+++ b/simplify.c
@@ -67,7 +67,7 @@ static int if_convert_phi(struct instruction *insn)
 	 * stuff. Verify that here.
 	 */
 	br = last_instruction(source->insns);
-	if (!br || br->opcode != OP_BR)
+	if (!br || br->opcode != OP_CBR)
 		return 0;
 
 	assert(br->cond);
@@ -227,11 +227,7 @@ void kill_insn(struct instruction *insn, int force)
 		repeat_phase |= REPEAT_SYMBOL_CLEANUP;
 		break;
 
-	case OP_BR:
-		if (!insn->bb_true || !insn->bb_false)
-			break;
-		/* fall through */
-
+	case OP_CBR:
 	case OP_COMPUTEDGOTO:
 		kill_use(&insn->cond);
 		break;
@@ -266,6 +262,7 @@ void kill_insn(struct instruction *insn, int force)
 		/* ignore */
 		return;
 
+	case OP_BR:
 	default:
 		break;
 	}
@@ -1034,9 +1031,6 @@ static int simplify_branch(struct instruction *insn)
 {
 	pseudo_t cond = insn->cond;
 
-	if (!cond)
-		return 0;
-
 	/* Constant conditional */
 	if (constant(cond)) {
 		insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
@@ -1052,6 +1046,7 @@ static int simplify_branch(struct instruction *insn)
 		insn->bb_false = NULL;
 		kill_use(&insn->cond);
 		insn->cond = NULL;
+		insn->opcode = OP_BR;
 		return REPEAT_CSE;
 	}
 
@@ -1181,7 +1176,7 @@ int simplify_instruction(struct instruction *insn)
 		break;
 	case OP_SEL:
 		return simplify_select(insn);
-	case OP_BR:
+	case OP_CBR:
 		return simplify_branch(insn);
 	case OP_SWITCH:
 		return simplify_switch(insn);
diff --git a/sparse-llvm.c b/sparse-llvm.c
index 3d2218ef6..9f362b3ed 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -642,19 +642,19 @@ static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
 	return value;
 }
 
-static void output_op_br(struct function *fn, struct instruction *br)
+static void output_op_cbr(struct function *fn, struct instruction *br)
 {
-	if (br->cond) {
-		LLVMValueRef cond = bool_value(fn,
-				pseudo_to_value(fn, br, br->cond));
+	LLVMValueRef cond = bool_value(fn,
+			pseudo_to_value(fn, br, br->cond));
 
-		LLVMBuildCondBr(fn->builder, cond,
-				br->bb_true->priv,
-				br->bb_false->priv);
-	} else
-		LLVMBuildBr(fn->builder,
-			    br->bb_true ? br->bb_true->priv :
-			    br->bb_false->priv);
+	LLVMBuildCondBr(fn->builder, cond,
+			br->bb_true->priv,
+			br->bb_false->priv);
+}
+
+static void output_op_br(struct function *fn, struct instruction *br)
+{
+	LLVMBuildBr(fn->builder, br->bb_true->priv);
 }
 
 static void output_op_sel(struct function *fn, struct instruction *insn)
@@ -810,6 +810,9 @@ static void output_insn(struct function *fn, struct instruction *insn)
 	case OP_BR:
 		output_op_br(fn, insn);
 		break;
+	case OP_CBR:
+		output_op_cbr(fn, insn);
+		break;
 	case OP_SYMADDR:
 		assert(0);
 		break;
diff --git a/validation/loop-linearization.c b/validation/loop-linearization.c
new file mode 100644
index 000000000..25c6dfb87
--- /dev/null
+++ b/validation/loop-linearization.c
@@ -0,0 +1,136 @@
+extern int p(int);
+
+static int ffor(void)
+{
+	int i;
+	for (int i = 0; i < 10; i++) {
+		if (!p(i))
+			return 0;
+	}
+	return 1;
+}
+
+static int fwhile(void)
+{
+	int i = 0;
+	while (i < 10) {
+		if (!p(i))
+			return 0;
+		i++;
+	}
+	return 1;
+}
+
+static int fdo(void)
+{
+	int i = 0;
+	do {
+		if (!p(i))
+			return 0;
+	} while (i++ < 10);
+	return 1;
+}
+
+/*
+ * check-name: loop-linearization
+ * check-command: test-linearize $file
+ *
+ * check-output-start
+ffor:
+.L0:
+	<entry-point>
+	phisrc.32   %phi5(i) <- $0
+	br          .L4
+
+.L4:
+	phi.32      %r1(i) <- %phi5(i), %phi6(i)
+	setlt.32    %r2 <- %r1(i), $10
+	cbr         %r2, .L1, .L3
+
+.L1:
+	call.32     %r4 <- p, %r1(i)
+	cbr         %r4, .L2, .L5
+
+.L5:
+	phisrc.32   %phi1(return) <- $0
+	br          .L7
+
+.L2:
+	add.32      %r7 <- %r1(i), $1
+	phisrc.32   %phi6(i) <- %r7
+	br          .L4
+
+.L3:
+	phisrc.32   %phi2(return) <- $1
+	br          .L7
+
+.L7:
+	phi.32      %r5 <- %phi1(return), %phi2(return)
+	ret.32      %r5
+
+
+fwhile:
+.L8:
+	<entry-point>
+	phisrc.32   %phi11(i) <- $0
+	br          .L12
+
+.L12:
+	phi.32      %r8(i) <- %phi11(i), %phi12(i)
+	setlt.32    %r9 <- %r8(i), $10
+	cbr         %r9, .L9, .L11
+
+.L9:
+	call.32     %r11 <- p, %r8(i)
+	cbr         %r11, .L14, .L13
+
+.L13:
+	phisrc.32   %phi7(return) <- $0
+	br          .L15
+
+.L14:
+	add.32      %r14 <- %r8(i), $1
+	phisrc.32   %phi12(i) <- %r14
+	br          .L12
+
+.L11:
+	phisrc.32   %phi8(return) <- $1
+	br          .L15
+
+.L15:
+	phi.32      %r12 <- %phi7(return), %phi8(return)
+	ret.32      %r12
+
+
+fdo:
+.L16:
+	<entry-point>
+	phisrc.32   %phi16(i) <- $0
+	br          .L17
+
+.L17:
+	phi.32      %r15(i) <- %phi16(i), %phi17(i)
+	call.32     %r16 <- p, %r15(i)
+	cbr         %r16, .L18, .L20
+
+.L20:
+	phisrc.32   %phi13(return) <- $0
+	br          .L22
+
+.L18:
+	add.32      %r19 <- %r15(i), $1
+	setlt.32    %r20 <- %r15(i), $10
+	phisrc.32   %phi17(i) <- %r19
+	cbr         %r20, .L17, .L19
+
+.L19:
+	phisrc.32   %phi14(return) <- $1
+	br          .L22
+
+.L22:
+	phi.32      %r17 <- %phi13(return), %phi14(return)
+	ret.32      %r17
+
+
+ * check-output-end
+ */
-- 
2.11.1

[PATCH v2 2/2] remove unused helper is_branch_goto()

[Luc Van Oostenryck]

This helper is also made unneeded since the introduction of OP_CBR.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h | 4 ----
 1 file changed, 4 deletions(-)

diff --git a/linearize.h b/linearize.h
index 2aa255154..bac82d7ff 100644
--- a/linearize.h
+++ b/linearize.h
@@ -237,10 +237,6 @@ struct basic_block {
 	};
 };
 
-static inline int is_branch_goto(struct instruction *br)
-{
-	return br && br->opcode==OP_BR && (!br->bb_true || !br->bb_false);
-}
 
 static inline void add_bb(struct basic_block_list **list, struct basic_block *bb)
 {
-- 
2.11.1