[PATCH] tcg: `reachable_code_pass()` remove empty else-branch

[PATCH] tcg: `reachable_code_pass()` remove empty else-branch

[Anton Johansson via]

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);
-                    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:
--
2.39.1

RE: [PATCH] tcg: `reachable_code_pass()` remove empty else-branch

[Taylor Simpson]

> -----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

Re: [PATCH] tcg: `reachable_code_pass()` remove empty else-branch

[Anton Johansson via]

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! :)

-- 
Anton Johansson,
rev.ng Labs Srl.

RE: [PATCH] tcg: `reachable_code_pass()` remove empty else-branch

[Taylor Simpson]

> -----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.

Re: [PATCH] tcg: `reachable_code_pass()` remove empty else-branch

[Anton Johansson via]

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.