* [PATCH 0/2] split OP_BR between OP_BR & OP_CBR @ 2017-02-18 1:28 Luc Van Oostenryck 2017-02-18 1:28 ` [PATCH 1/2] split OP_BR between unconditional & conditional: OP_CBR Luc Van Oostenryck 2017-02-18 1:28 ` [PATCH " Luc Van Oostenryck 0 siblings, 2 replies; 8+ messages in thread From: Luc Van Oostenryck @ 2017-02-18 1:28 UTC (permalink / raw) To: linux-sparse; +Cc: Christopher Li, 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH 1/2] split OP_BR between unconditional & conditional: OP_CBR 2017-02-18 1:28 [PATCH 0/2] split OP_BR between OP_BR & OP_CBR Luc Van Oostenryck @ 2017-02-18 1:28 ` Luc Van Oostenryck 2017-02-27 15:02 ` Christopher Li 2017-02-18 1:28 ` [PATCH " Luc Van Oostenryck 1 sibling, 1 reply; 8+ messages in thread From: Luc Van Oostenryck @ 2017-02-18 1:28 UTC (permalink / raw) To: linux-sparse; +Cc: Christopher Li, 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 ^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: [PATCH 1/2] split OP_BR between unconditional & conditional: OP_CBR 2017-02-18 1:28 ` [PATCH 1/2] split OP_BR between unconditional & conditional: OP_CBR Luc Van Oostenryck @ 2017-02-27 15:02 ` Christopher Li 2017-02-27 21:22 ` Luc Van Oostenryck 2017-02-28 13:30 ` [PATCH v2 0/2] split OP_BR between OP_BR & OP_CBR Luc Van Oostenryck 0 siblings, 2 replies; 8+ messages in thread From: Christopher Li @ 2017-02-27 15:02 UTC (permalink / raw) To: Luc Van Oostenryck; +Cc: Linux-Sparse 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 1/2] split OP_BR between unconditional & conditional: OP_CBR 2017-02-27 15:02 ` Christopher Li @ 2017-02-27 21:22 ` Luc Van Oostenryck 2017-02-28 13:30 ` [PATCH v2 0/2] split OP_BR between OP_BR & OP_CBR Luc Van Oostenryck 1 sibling, 0 replies; 8+ messages in thread From: Luc Van Oostenryck @ 2017-02-27 21:22 UTC (permalink / raw) To: Christopher Li; +Cc: Linux-Sparse 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH v2 0/2] split OP_BR between OP_BR & OP_CBR 2017-02-27 15:02 ` Christopher Li 2017-02-27 21:22 ` Luc Van Oostenryck @ 2017-02-28 13:30 ` Luc Van Oostenryck 2017-02-28 13:30 ` [PATCH v2 1/2] split OP_BR between unconditional & conditional: OP_CBR Luc Van Oostenryck 2017-02-28 13:30 ` [PATCH v2 2/2] remove unused helper is_branch_goto() Luc Van Oostenryck 1 sibling, 2 replies; 8+ messages in thread From: Luc Van Oostenryck @ 2017-02-28 13:30 UTC (permalink / raw) To: linux-sparse; +Cc: Christopher Li, 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH v2 1/2] split OP_BR between unconditional & conditional: OP_CBR 2017-02-28 13:30 ` [PATCH v2 0/2] split OP_BR between OP_BR & OP_CBR Luc Van Oostenryck @ 2017-02-28 13:30 ` Luc Van Oostenryck 2017-02-28 13:30 ` [PATCH v2 2/2] remove unused helper is_branch_goto() Luc Van Oostenryck 1 sibling, 0 replies; 8+ messages in thread From: Luc Van Oostenryck @ 2017-02-28 13:30 UTC (permalink / raw) To: linux-sparse; +Cc: Christopher Li, 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 ^ permalink raw reply related [flat|nested] 8+ messages in thread
* [PATCH v2 2/2] remove unused helper is_branch_goto() 2017-02-28 13:30 ` [PATCH v2 0/2] split OP_BR between OP_BR & OP_CBR Luc Van Oostenryck 2017-02-28 13:30 ` [PATCH v2 1/2] split OP_BR between unconditional & conditional: OP_CBR Luc Van Oostenryck @ 2017-02-28 13:30 ` Luc Van Oostenryck 1 sibling, 0 replies; 8+ messages in thread From: Luc Van Oostenryck @ 2017-02-28 13:30 UTC (permalink / raw) To: linux-sparse; +Cc: Christopher Li, 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 ^ permalink raw reply related [flat|nested] 8+ messages in thread
* [PATCH 2/2] remove unused helper is_branch_goto() 2017-02-18 1:28 [PATCH 0/2] split OP_BR between OP_BR & OP_CBR Luc Van Oostenryck 2017-02-18 1:28 ` [PATCH 1/2] split OP_BR between unconditional & conditional: OP_CBR Luc Van Oostenryck @ 2017-02-18 1:28 ` Luc Van Oostenryck 1 sibling, 0 replies; 8+ messages in thread From: Luc Van Oostenryck @ 2017-02-18 1:28 UTC (permalink / raw) To: linux-sparse; +Cc: Christopher Li, 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 ^ permalink raw reply related [flat|nested] 8+ messages in thread
end of thread, other threads:[~2017-02-28 13:33 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-02-18 1:28 [PATCH 0/2] split OP_BR between OP_BR & OP_CBR Luc Van Oostenryck 2017-02-18 1:28 ` [PATCH 1/2] split OP_BR between unconditional & conditional: OP_CBR Luc Van Oostenryck 2017-02-27 15:02 ` Christopher Li 2017-02-27 21:22 ` Luc Van Oostenryck 2017-02-28 13:30 ` [PATCH v2 0/2] split OP_BR between OP_BR & OP_CBR Luc Van Oostenryck 2017-02-28 13:30 ` [PATCH v2 1/2] split OP_BR between unconditional & conditional: OP_CBR Luc Van Oostenryck 2017-02-28 13:30 ` [PATCH v2 2/2] remove unused helper is_branch_goto() Luc Van Oostenryck 2017-02-18 1:28 ` [PATCH " Luc Van Oostenryck
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.