| Message ID | 20230301142221.24495-1-anjo@rev.ng (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | tcg: `reachable_code_pass()` remove empty else-branch | expand |
> -----Original Message----- > From: Anton Johansson <anjo@rev.ng> > Sent: Wednesday, March 1, 2023 7:22 AM > To: qemu-devel@nongnu.org > Cc: ale@rev.ng; richard.henderson@linaro.org; Taylor Simpson > <tsimpson@quicinc.com> > Subject: [PATCH] tcg: `reachable_code_pass()` remove empty else-branch > > This patch extends reachable_code_pass() to also deal with empty else- > branches of the form > > br $L0 > set_label $L1 > set_label $L0 > > converting them to > > set_label $L1 > > when $L0 is only referenced by the br op. This type of empty-else branch will > be emitted by idef-parser in the Hexagon frontend once CANCEL statements > have been ignored. > > Signed-off-by: Anton Johansson <anjo@rev.ng> > --- > tcg/tcg.c | 41 ++++++++++++++++++++++++++++++----------- > 1 file changed, 30 insertions(+), 11 deletions(-) > > diff --git a/tcg/tcg.c b/tcg/tcg.c > index a4a3da6804..531bc74231 100644 > --- a/tcg/tcg.c > +++ b/tcg/tcg.c > @@ -2664,21 +2664,40 @@ static void reachable_code_pass(TCGContext *s) > dead = false; > remove = false; > > - /* > - * Optimization can fold conditional branches to unconditional. > - * If we find a label with one reference which is preceded by > - * an unconditional branch to it, remove both. This needed to > - * wait until the dead code in between them was removed. > - */ > - if (label->refs == 1) { > - TCGOp *op_prev = QTAILQ_PREV(op, link); Can't we just insert a while loop here to move op_prev back across labels? while (op_next->opc == INDEX_op_set_label) { op_prev = QTAILQ_PREV(op, op_prev); } > - if (op_prev->opc == INDEX_op_br && > - label == arg_label(op_prev->args[0])) { Also, here is the patch that exposes the need for this optimization https://lists.gnu.org/archive/html/qemu-devel/2023-01/msg07236.html Thanks, Taylor
On 3/1/23 23:37, Taylor Simpson wrote: >> diff --git a/tcg/tcg.c b/tcg/tcg.c >> index a4a3da6804..531bc74231 100644 >> --- a/tcg/tcg.c >> +++ b/tcg/tcg.c >> @@ -2664,21 +2664,40 @@ static void reachable_code_pass(TCGContext *s) >> dead = false; >> remove = false; >> >> - /* >> - * Optimization can fold conditional branches to unconditional. >> - * If we find a label with one reference which is preceded by >> - * an unconditional branch to it, remove both. This needed to >> - * wait until the dead code in between them was removed. >> - */ >> - if (label->refs == 1) { >> - TCGOp *op_prev = QTAILQ_PREV(op, link); > Can't we just insert a while loop here to move op_prev back across labels? > > while (op_next->opc == INDEX_op_set_label) { > op_prev = QTAILQ_PREV(op, op_prev); > } > >> - if (op_prev->opc == INDEX_op_br && >> - label == arg_label(op_prev->args[0])) { Ah I see, you're thinking something like dead = false; remove = false; if (label->refs == 1) { TCGOp *op_prev = NULL; do { op_prev = QTAILQ_PREV(op_prev, link); } while (op_prev->opc == INDEX_op_set_label); if (op_prev->opc == INDEX_op_br && label == arg_label(op_prev->args[0])) { tcg_op_remove(s, op_prev); remove = true; } } to handle br set_label ... set_label I do like being able to combine both branches, and we're no longer relying on the next iteration of the loop to clean up the final set_label. Since we won't ever encounter more than one intermediate set_label this might be overkill, but either way I think it's an improvement. Thanks for the feedback, I'll resubmit with this change! :)
> -----Original Message----- > From: Anton Johansson <anjo@rev.ng> > Sent: Friday, March 3, 2023 7:32 AM > To: Taylor Simpson <tsimpson@quicinc.com>; qemu-devel@nongnu.org > Cc: ale@rev.ng; richard.henderson@linaro.org > Subject: Re: [PATCH] tcg: `reachable_code_pass()` remove empty else- > branch > > On 3/1/23 23:37, Taylor Simpson wrote: > >> diff --git a/tcg/tcg.c b/tcg/tcg.c > >> index a4a3da6804..531bc74231 100644 > >> --- a/tcg/tcg.c > >> +++ b/tcg/tcg.c > >> @@ -2664,21 +2664,40 @@ static void reachable_code_pass(TCGContext > *s) > >> dead = false; > >> remove = false; > >> > >> - /* > >> - * Optimization can fold conditional branches to unconditional. > >> - * If we find a label with one reference which is preceded by > >> - * an unconditional branch to it, remove both. This needed to > >> - * wait until the dead code in between them was removed. > >> - */ > >> - if (label->refs == 1) { > >> - TCGOp *op_prev = QTAILQ_PREV(op, link); > > Can't we just insert a while loop here to move op_prev back across labels? > > > > while (op_next->opc == INDEX_op_set_label) { > > op_prev = QTAILQ_PREV(op, op_prev); > > } > > > >> - if (op_prev->opc == INDEX_op_br && > >> - label == arg_label(op_prev->args[0])) { > Ah I see, you're thinking something like > > dead = false; > remove = false; > > if (label->refs == 1) { > TCGOp *op_prev = NULL; > do { > op_prev = QTAILQ_PREV(op_prev, link); You can't use op_prev as the argument here. It is NULL the first time through the loop ☹ > } while (op_prev->opc == INDEX_op_set_label); > > if (op_prev->opc == INDEX_op_br && > label == arg_label(op_prev->args[0])) { > tcg_op_remove(s, op_prev); > remove = true; > } > } > > to handle > > br > set_label > ... > set_label > > I do like being able to combine both branches, and we're no longer relying on > the next iteration of the loop to clean up the final set_label. Since we won't > ever encounter more than one intermediate set_label this might be overkill, > but either way I think it's an improvement. It's overkill for the code that idef-parser generates, but my suggestion is to make able to skip back over as many labels as possible. > > Thanks for the feedback, I'll resubmit with this change! :) > > -- > Anton Johansson, > rev.ng Labs Srl.
On 3/3/23 16:39, Taylor Simpson wrote: >> dead = false; >> remove = false; >> >> if (label->refs == 1) { >> TCGOp *op_prev = NULL; >> do { >> op_prev = QTAILQ_PREV(op_prev, link); > You can't use op_prev as the argument here. It is NULL the first time through the loop ☹ Ah right TCGop *op_prev = op; should do it.
diff --git a/tcg/tcg.c b/tcg/tcg.c index a4a3da6804..531bc74231 100644 --- a/tcg/tcg.c +++ b/tcg/tcg.c @@ -2664,21 +2664,40 @@ static void reachable_code_pass(TCGContext *s) dead = false; remove = false; - /* - * Optimization can fold conditional branches to unconditional. - * If we find a label with one reference which is preceded by - * an unconditional branch to it, remove both. This needed to - * wait until the dead code in between them was removed. - */ - if (label->refs == 1) { - TCGOp *op_prev = QTAILQ_PREV(op, link); - if (op_prev->opc == INDEX_op_br && - label == arg_label(op_prev->args[0])) { + TCGOp *op_prev = QTAILQ_PREV(op, link); + if (label->refs == 1 && + op_prev->opc == INDEX_op_br && + label == arg_label(op_prev->args[0])) { + /* + * Optimization can fold conditional branches to + * unconditional. If we find a label with one reference + * which is preceded by an unconditional branch to it, + * remove both. This needed to wait until the dead code + * in between them was removed. + */ + tcg_op_remove(s, op_prev); + remove = true; + } else if (op_next->opc == INDEX_op_set_label) { + /* + * The Hexagon frontend can generate empty else-branches for + * certain instructions. If we encounter + * + * br $L0 + * set_label $L1 + * set_label $L0 + * + * where $L0 only has a single reference, remove the branch + * to $L0 and the corresonding label. + */ + TCGLabel *next_label = arg_label(op_next->args[0]); + if (next_label->refs == 1 && + op_prev->opc == INDEX_op_br && + next_label == arg_label(op_prev->args[0])) { tcg_op_remove(s, op_prev); - remove = true; } } } + break; case INDEX_op_br:
This patch extends reachable_code_pass() to also deal with empty else-branches of the form br $L0 set_label $L1 set_label $L0 converting them to set_label $L1 when $L0 is only referenced by the br op. This type of empty-else branch will be emitted by idef-parser in the Hexagon frontend once CANCEL statements have been ignored. Signed-off-by: Anton Johansson <anjo@rev.ng> --- tcg/tcg.c | 41 ++++++++++++++++++++++++++++++----------- 1 file changed, 30 insertions(+), 11 deletions(-) -- 2.39.1