Possible regression in DF analysis

Possible regression in DF analysis

[Claudiu Zissulescu Ianculescu]

[-- Attachment #1: Type: text/plain, Size: 2336 bytes --]

Hi,

I've stumbled over a potential issue related to Dataflow analysis,
and maybe you can help me with it. It can be reproduced for AARCH64
but other architectures are affected as well.

I have the next snip before CSE1 pass:

(insn 14 11 15 3 (set (reg:CC 66 cc)
        (compare:CC (reg/v:SI 98 [ bytes ])
            (const_int 8 [0x8]))) "bad_cc.c":11:8 406 {cmpsi}
     (nil))
(jump_insn 15 14 16 3 (set (pc)
        (if_then_else (gtu (reg:CC 66 cc)
                (const_int 0 [0]))
            (label_ref 27)
            (pc))) "bad_cc.c":11:8 15 {condjump}
     (int_list:REG_BR_PROB 955630228 (nil))
 -> 27)

(note 16 15 17 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
(insn 17 16 18 4 (set (reg:CC 66 cc)
        (compare:CC (reg/v:SI 98 [ bytes ])
            (const_int 8 [0x8]))) "bad_cc.c":12:10 406 {cmpsi}
     (nil))
(jump_insn 18 17 19 4 (set (pc)
        (if_then_else (eq (reg:CC 66 cc)
                (const_int 0 [0]))
            (label_ref:DI 34)
            (pc))) "bad_cc.c":12:10 15 {condjump}
     (int_list:REG_BR_PROB 365072228 (nil))
 -> 34)

The CSE1 optimizes the second comparison (i.e., INSN 17) as it is similar with
the one from INSN 14.

However, after this optimization I get the CC reg being dead after
JUMP_INSN 15, which may lead to wrong code gen. Here it is the dump
from fwprop1:

(insn 14 11 15 3 (set (reg:CC 66 cc)
        (compare:CC (reg/v:SI 98 [ bytes ])
            (const_int 8 [0x8]))) "bad_cc.c":11:8 406 {cmpsi}
     (nil))
(jump_insn 15 14 16 3 (set (pc)
        (if_then_else (gtu (reg:CC 66 cc)
                (const_int 0 [0]))
            (label_ref 27)
            (pc))) "bad_cc.c":11:8 15 {condjump}
     (expr_list:REG_DEAD (reg:CC 66 cc)
        (int_list:REG_BR_PROB 955630228 (nil)))
 -> 27)
(note 16 15 18 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
(jump_insn 18 16 19 4 (set (pc)
        (if_then_else (eq (reg:CC 66 cc)
                (const_int 0 [0]))
            (label_ref:DI 34)
            (pc))) "bad_cc.c":12:10 15 {condjump}
     (expr_list:REG_DEAD (reg:CC 66 cc)
        (int_list:REG_BR_PROB 365072228 (nil)))
 -> 34)

Please observe the REG_DEAD note on the both jump instructions.

I see this behaviour in GCC 12.2.1 release for AARCH64, but I cannot
see it for GCC 10.x

A test code snip is attached, and it needs to be compiled with aarch64
backend using -Os option.

[-- Attachment #2: bad_cc.c --]
[-- Type: text/x-csrc, Size: 309 bytes --]

typedef unsigned int uint32_t;
typedef unsigned char uint8_t;

void foo (uint32_t *src, uint8_t *c, uint32_t bytes)
{
  uint8_t *ctarget;

  for (;;) {
    c[0] = src[0] & 0xff;

    if (bytes <= 8) {
      if (bytes < 8) {
	 ctarget[4] = c[4];
      }
      return;
    }

    bytes -= 8;
    c += 8;
  }
}

Re: Possible regression in DF analysis

[Eric Botcazou]

> However, after this optimization I get the CC reg being dead after
> JUMP_INSN 15, which may lead to wrong code gen. Here it is the dump
> from fwprop1:
> 
> (insn 14 11 15 3 (set (reg:CC 66 cc)
>         (compare:CC (reg/v:SI 98 [ bytes ])
>             (const_int 8 [0x8]))) "bad_cc.c":11:8 406 {cmpsi}
>      (nil))
> (jump_insn 15 14 16 3 (set (pc)
>         (if_then_else (gtu (reg:CC 66 cc)
>                 (const_int 0 [0]))
>             (label_ref 27)
>             (pc))) "bad_cc.c":11:8 15 {condjump}
>      (expr_list:REG_DEAD (reg:CC 66 cc)
>         (int_list:REG_BR_PROB 955630228 (nil)))
>  -> 27)
> (note 16 15 18 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
> (jump_insn 18 16 19 4 (set (pc)
>         (if_then_else (eq (reg:CC 66 cc)
>                 (const_int 0 [0]))
>             (label_ref:DI 34)
>             (pc))) "bad_cc.c":12:10 15 {condjump}
>      (expr_list:REG_DEAD (reg:CC 66 cc)
>         (int_list:REG_BR_PROB 365072228 (nil)))
>  -> 34)
> 
> Please observe the REG_DEAD note on the both jump instructions.

Passes that consume REG_DEAD/REG_UNUSED notes need to recompute them 
explicitly, they are not updated on the fly.

-- 
Eric Botcazou

Re: Possible regression in DF analysis

[Claudiu Zissulescu Ianculescu]

Hi Eric,
The problem shows in loop-doloop.c when I introduce a loop end pattern
that replaces the first jump instruction (JUMP_INSN 15) with a pattern
that clobbers CC reg. However, the DF doesn't look like it works as
the doloop step cannot find the CC reg alive. Please see
loop-doloop.c:766. Hence, it introduces the doloop_end patterns, and
renders the compare instruction (INSN 14) dead code. leading to
errors.

Thanks,
Claudiu

On Thu, Dec 8, 2022 at 1:33 PM Eric Botcazou <botcazou@adacore.com> wrote:
>
> > However, after this optimization I get the CC reg being dead after
> > JUMP_INSN 15, which may lead to wrong code gen. Here it is the dump
> > from fwprop1:
> >
> > (insn 14 11 15 3 (set (reg:CC 66 cc)
> >         (compare:CC (reg/v:SI 98 [ bytes ])
> >             (const_int 8 [0x8]))) "bad_cc.c":11:8 406 {cmpsi}
> >      (nil))
> > (jump_insn 15 14 16 3 (set (pc)
> >         (if_then_else (gtu (reg:CC 66 cc)
> >                 (const_int 0 [0]))
> >             (label_ref 27)
> >             (pc))) "bad_cc.c":11:8 15 {condjump}
> >      (expr_list:REG_DEAD (reg:CC 66 cc)
> >         (int_list:REG_BR_PROB 955630228 (nil)))
> >  -> 27)
> > (note 16 15 18 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
> > (jump_insn 18 16 19 4 (set (pc)
> >         (if_then_else (eq (reg:CC 66 cc)
> >                 (const_int 0 [0]))
> >             (label_ref:DI 34)
> >             (pc))) "bad_cc.c":12:10 15 {condjump}
> >      (expr_list:REG_DEAD (reg:CC 66 cc)
> >         (int_list:REG_BR_PROB 365072228 (nil)))
> >  -> 34)
> >
> > Please observe the REG_DEAD note on the both jump instructions.
>
> Passes that consume REG_DEAD/REG_UNUSED notes need to recompute them
> explicitly, they are not updated on the fly.
>
> --
> Eric Botcazou
>
>

Re: Possible regression in DF analysis

[Eric Botcazou]

> The problem shows in loop-doloop.c when I introduce a loop end pattern
> that replaces the first jump instruction (JUMP_INSN 15) with a pattern
> that clobbers CC reg. However, the DF doesn't look like it works as
> the doloop step cannot find the CC reg alive. Please see
> loop-doloop.c:766. Hence, it introduces the doloop_end patterns, and
> renders the compare instruction (INSN 14) dead code. leading to
> errors.

So df_get_live_out does not contain the CC register?  iv_analysis_loop_init 
only performs a local update of the DF information, maybe it does not cover 
the basic block containing insn 14 and 15?

-- 
Eric Botcazou

Re: Possible regression in DF analysis

[Claudiu Zissulescu Ianculescu]

It looks like that. The df_analyze_loop is only looking at the loop
BBs, and it is not clear for me if df_analyze_loop is required to have
all the df_live_outs correctly computed or not. Do you know if it is
true?

If the df_analyze_loop is not supposed to compute all the df_live_outs
correctly, then the error resides in how loop-doloop is using the
iv_analysis_loop_init().

Thank you for your help,
Claudiu

On Tue, Dec 13, 2022 at 10:41 AM Eric Botcazou <botcazou@adacore.com> wrote:
>
> > The problem shows in loop-doloop.c when I introduce a loop end pattern
> > that replaces the first jump instruction (JUMP_INSN 15) with a pattern
> > that clobbers CC reg. However, the DF doesn't look like it works as
> > the doloop step cannot find the CC reg alive. Please see
> > loop-doloop.c:766. Hence, it introduces the doloop_end patterns, and
> > renders the compare instruction (INSN 14) dead code. leading to
> > errors.
>
> So df_get_live_out does not contain the CC register?  iv_analysis_loop_init
> only performs a local update of the DF information, maybe it does not cover
> the basic block containing insn 14 and 15?
>
> --
> Eric Botcazou
>
>

Re: Possible regression in DF analysis

[Claudiu Zissulescu Ianculescu]

UPDATE:
The df_analyze_loop is calling the df_set_blocks. Thus, the analysis
behaves as if the function only contains those blocks and any edges
that occur directly between the blocks in the set (see df-core.cc).
This said, the loop-doloop behaves faulty at loop-doloop.cc:772 as the
df_get_lives_out (loop_end) is not computed correctly.

A possible solution is to include in the blocks_to_analyze the missing
basic blocks, something like:

diff --git a/gcc/df-core.cc b/gcc/df-core.cc
index a901b84878f..d7059c188b2 100644
--- a/gcc/df-core.cc
+++ b/gcc/df-core.cc
@@ -1437,7 +1437,15 @@ df_analyze_loop (class loop *loop)
   df_set_blocks (blocks);
   BITMAP_FREE (blocks);

-  df_analyze_1 ();
+  /* Add the loop's header successor bbs too.  */
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, loop->header->succs)
+    bitmap_set_bit (df->blocks_to_analyze, e->dest->index);
+
+  if (dump_file)
+    debug_bitmap_file (dump_file, df->blocks_to_analyze);
+  df_analyze ();
 }

What do you think,
Claudiu

On Tue, Dec 13, 2022 at 2:30 PM Claudiu Zissulescu Ianculescu
<claziss@gmail.com> wrote:
>
> It looks like that. The df_analyze_loop is only looking at the loop
> BBs, and it is not clear for me if df_analyze_loop is required to have
> all the df_live_outs correctly computed or not. Do you know if it is
> true?
>
> If the df_analyze_loop is not supposed to compute all the df_live_outs
> correctly, then the error resides in how loop-doloop is using the
> iv_analysis_loop_init().
>
> Thank you for your help,
> Claudiu
>
> On Tue, Dec 13, 2022 at 10:41 AM Eric Botcazou <botcazou@adacore.com> wrote:
> >
> > > The problem shows in loop-doloop.c when I introduce a loop end pattern
> > > that replaces the first jump instruction (JUMP_INSN 15) with a pattern
> > > that clobbers CC reg. However, the DF doesn't look like it works as
> > > the doloop step cannot find the CC reg alive. Please see
> > > loop-doloop.c:766. Hence, it introduces the doloop_end patterns, and
> > > renders the compare instruction (INSN 14) dead code. leading to
> > > errors.
> >
> > So df_get_live_out does not contain the CC register?  iv_analysis_loop_init
> > only performs a local update of the DF information, maybe it does not cover
> > the basic block containing insn 14 and 15?
> >
> > --
> > Eric Botcazou
> >
> >

Re: Possible regression in DF analysis

[Richard Biener]

> Am 13.12.2022 um 17:54 schrieb Claudiu Zissulescu Ianculescu via Gcc <gcc@gcc.gnu.org>:
> 
> UPDATE:
> The df_analyze_loop is calling the df_set_blocks. Thus, the analysis
> behaves as if the function only contains those blocks and any edges
> that occur directly between the blocks in the set (see df-core.cc).
> This said, the loop-doloop behaves faulty at loop-doloop.cc:772 as the
> df_get_lives_out (loop_end) is not computed correctly.
> 
> A possible solution is to include in the blocks_to_analyze the missing
> basic blocks, something like:
> 
> diff --git a/gcc/df-core.cc b/gcc/df-core.cc
> index a901b84878f..d7059c188b2 100644
> --- a/gcc/df-core.cc
> +++ b/gcc/df-core.cc
> @@ -1437,7 +1437,15 @@ df_analyze_loop (class loop *loop)
>   df_set_blocks (blocks);
>   BITMAP_FREE (blocks);
> 
> -  df_analyze_1 ();
> +  /* Add the loop's header successor bbs too.  */
> +  edge e;
> +  edge_iterator ei;
> +  FOR_EACH_EDGE (e, ei, loop->header->succs)
> +    bitmap_set_bit (df->blocks_to_analyze, e->dest->index);
> +
> +  if (dump_file)
> +    debug_bitmap_file (dump_file, df->blocks_to_analyze);
> +  df_analyze ();
> }
> 
> What do you think,

Maybe you want to iterate over the loops exit edges and include their destination block instead?

> Claudiu
> 
>> On Tue, Dec 13, 2022 at 2:30 PM Claudiu Zissulescu Ianculescu
>> <claziss@gmail.com> wrote:
>> 
>> It looks like that. The df_analyze_loop is only looking at the loop
>> BBs, and it is not clear for me if df_analyze_loop is required to have
>> all the df_live_outs correctly computed or not. Do you know if it is
>> true?
>> 
>> If the df_analyze_loop is not supposed to compute all the df_live_outs
>> correctly, then the error resides in how loop-doloop is using the
>> iv_analysis_loop_init().
>> 
>> Thank you for your help,
>> Claudiu
>> 
>>> On Tue, Dec 13, 2022 at 10:41 AM Eric Botcazou <botcazou@adacore.com> wrote:
>>> 
>>>> The problem shows in loop-doloop.c when I introduce a loop end pattern
>>>> that replaces the first jump instruction (JUMP_INSN 15) with a pattern
>>>> that clobbers CC reg. However, the DF doesn't look like it works as
>>>> the doloop step cannot find the CC reg alive. Please see
>>>> loop-doloop.c:766. Hence, it introduces the doloop_end patterns, and
>>>> renders the compare instruction (INSN 14) dead code. leading to
>>>> errors.
>>> 
>>> So df_get_live_out does not contain the CC register?  iv_analysis_loop_init
>>> only performs a local update of the DF information, maybe it does not cover
>>> the basic block containing insn 14 and 15?
>>> 
>>> --
>>> Eric Botcazou
>>> 
>>> 

Re: Possible regression in DF analysis

[Claudiu Zissulescu Ianculescu]

>
> Maybe you want to iterate over the loops exit edges and include their destination block instead?
>

This is better approach, let me try it and I will be back to you.

Thanks,
Claudiu

Re: Possible regression in DF analysis

[Claudiu Zissulescu Ianculescu]

I have update the fix to this one:

diff --git a/gcc/df-core.cc b/gcc/df-core.cc
index a901b84878f..cc6383990a1 100644
--- a/gcc/df-core.cc
+++ b/gcc/df-core.cc
@@ -1437,7 +1437,16 @@ df_analyze_loop (class loop *loop)
   df_set_blocks (blocks);
   BITMAP_FREE (blocks);

-  df_analyze_1 ();
+  /* Iterate over loop's exit edges and add theirs destinations BB
+     indexes.  */
+  struct loop_exit *exit;
+  for (exit = loop->exits->next; exit->e; exit = exit->next)
+    bitmap_set_bit (df->blocks_to_analyze, exit->e->dest->index);
+
+  if (dump_file)
+    debug_bitmap_file (dump_file, df->blocks_to_analyze);
+
+  df_analyze ();
 }

I still need to validate it for x86

Best,
Claudiu

On Tue, Dec 13, 2022 at 7:38 PM Claudiu Zissulescu Ianculescu
<claziss@gmail.com> wrote:
>
> >
> > Maybe you want to iterate over the loops exit edges and include their destination block instead?
> >
>
> This is better approach, let me try it and I will be back to you.
>
> Thanks,
> Claudiu

Re: Possible regression in DF analysis

[Richard Biener]

On Wed, Dec 14, 2022 at 11:37 AM Claudiu Zissulescu Ianculescu
<claziss@gmail.com> wrote:
>
> I have update the fix to this one:
>
> diff --git a/gcc/df-core.cc b/gcc/df-core.cc
> index a901b84878f..cc6383990a1 100644
> --- a/gcc/df-core.cc
> +++ b/gcc/df-core.cc
> @@ -1437,7 +1437,16 @@ df_analyze_loop (class loop *loop)
>    df_set_blocks (blocks);
>    BITMAP_FREE (blocks);
>
> -  df_analyze_1 ();
> +  /* Iterate over loop's exit edges and add theirs destinations BB
> +     indexes.  */
> +  struct loop_exit *exit;
> +  for (exit = loop->exits->next; exit->e; exit = exit->next)
> +    bitmap_set_bit (df->blocks_to_analyze, exit->e->dest->index);

I think you want to adjust the local 'blocks' bitmap passed to df_set_blocks.
There's also the issue that the computed postorder doesn't include the new
blocks and thus the computation will likely be invalid?

> +
> +  if (dump_file)
> +    debug_bitmap_file (dump_file, df->blocks_to_analyze);
> +
> +  df_analyze ();
>  }
>
> I still need to validate it for x86
>
> Best,
> Claudiu
>
> On Tue, Dec 13, 2022 at 7:38 PM Claudiu Zissulescu Ianculescu
> <claziss@gmail.com> wrote:
> >
> > >
> > > Maybe you want to iterate over the loops exit edges and include their destination block instead?
> > >
> >
> > This is better approach, let me try it and I will be back to you.
> >
> > Thanks,
> > Claudiu

Re: Possible regression in DF analysis

[Claudiu Zissulescu Ianculescu]

Hi Richard,

Sorry for my misunderstanding. I am calling the df_analyze() instead
of df_analyze1() at the end. Shouldn't df_analyze take care and
compute the correct postorder  (df-core.cc:1273) ?

Thank you,
Claudiu

On Wed, Dec 14, 2022 at 1:06 PM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Wed, Dec 14, 2022 at 11:37 AM Claudiu Zissulescu Ianculescu
> <claziss@gmail.com> wrote:
> >
> > I have update the fix to this one:
> >
> > diff --git a/gcc/df-core.cc b/gcc/df-core.cc
> > index a901b84878f..cc6383990a1 100644
> > --- a/gcc/df-core.cc
> > +++ b/gcc/df-core.cc
> > @@ -1437,7 +1437,16 @@ df_analyze_loop (class loop *loop)
> >    df_set_blocks (blocks);
> >    BITMAP_FREE (blocks);
> >
> > -  df_analyze_1 ();
> > +  /* Iterate over loop's exit edges and add theirs destinations BB
> > +     indexes.  */
> > +  struct loop_exit *exit;
> > +  for (exit = loop->exits->next; exit->e; exit = exit->next)
> > +    bitmap_set_bit (df->blocks_to_analyze, exit->e->dest->index);
>
> I think you want to adjust the local 'blocks' bitmap passed to df_set_blocks.
> There's also the issue that the computed postorder doesn't include the new
> blocks and thus the computation will likely be invalid?
>
> > +
> > +  if (dump_file)
> > +    debug_bitmap_file (dump_file, df->blocks_to_analyze);
> > +
> > +  df_analyze ();
> >  }
> >
> > I still need to validate it for x86
> >
> > Best,
> > Claudiu
> >
> > On Tue, Dec 13, 2022 at 7:38 PM Claudiu Zissulescu Ianculescu
> > <claziss@gmail.com> wrote:
> > >
> > > >
> > > > Maybe you want to iterate over the loops exit edges and include their destination block instead?
> > > >
> > >
> > > This is better approach, let me try it and I will be back to you.
> > >
> > > Thanks,
> > > Claudiu

Re: Possible regression in DF analysis

[Richard Biener]

On Wed, Dec 14, 2022 at 12:30 PM Claudiu Zissulescu Ianculescu
<claziss@gmail.com> wrote:
>
> Hi Richard,
>
> Sorry for my misunderstanding. I am calling the df_analyze() instead
> of df_analyze1() at the end. Shouldn't df_analyze take care and
> compute the correct postorder  (df-core.cc:1273) ?

The point of df_analyze_loop is to be more efficient than doing a
full df_analyze (but of course that's only so in a limited way, still ...)

> Thank you,
> Claudiu
>
> On Wed, Dec 14, 2022 at 1:06 PM Richard Biener
> <richard.guenther@gmail.com> wrote:
> >
> > On Wed, Dec 14, 2022 at 11:37 AM Claudiu Zissulescu Ianculescu
> > <claziss@gmail.com> wrote:
> > >
> > > I have update the fix to this one:
> > >
> > > diff --git a/gcc/df-core.cc b/gcc/df-core.cc
> > > index a901b84878f..cc6383990a1 100644
> > > --- a/gcc/df-core.cc
> > > +++ b/gcc/df-core.cc
> > > @@ -1437,7 +1437,16 @@ df_analyze_loop (class loop *loop)
> > >    df_set_blocks (blocks);
> > >    BITMAP_FREE (blocks);
> > >
> > > -  df_analyze_1 ();
> > > +  /* Iterate over loop's exit edges and add theirs destinations BB
> > > +     indexes.  */
> > > +  struct loop_exit *exit;
> > > +  for (exit = loop->exits->next; exit->e; exit = exit->next)
> > > +    bitmap_set_bit (df->blocks_to_analyze, exit->e->dest->index);
> >
> > I think you want to adjust the local 'blocks' bitmap passed to df_set_blocks.
> > There's also the issue that the computed postorder doesn't include the new
> > blocks and thus the computation will likely be invalid?
> >
> > > +
> > > +  if (dump_file)
> > > +    debug_bitmap_file (dump_file, df->blocks_to_analyze);
> > > +
> > > +  df_analyze ();
> > >  }
> > >
> > > I still need to validate it for x86
> > >
> > > Best,
> > > Claudiu
> > >
> > > On Tue, Dec 13, 2022 at 7:38 PM Claudiu Zissulescu Ianculescu
> > > <claziss@gmail.com> wrote:
> > > >
> > > > >
> > > > > Maybe you want to iterate over the loops exit edges and include their destination block instead?
> > > > >
> > > >
> > > > This is better approach, let me try it and I will be back to you.
> > > >
> > > > Thanks,
> > > > Claudiu

Re: Possible regression in DF analysis

[Jeff Law]

On 12/8/22 04:51, Claudiu Zissulescu Ianculescu via Gcc wrote:
> Hi Eric,
> The problem shows in loop-doloop.c when I introduce a loop end pattern
> that replaces the first jump instruction (JUMP_INSN 15) with a pattern
> that clobbers CC reg. However, the DF doesn't look like it works as
> the doloop step cannot find the CC reg alive. Please see
> loop-doloop.c:766. Hence, it introduces the doloop_end patterns, and
> renders the compare instruction (INSN 14) dead code. leading to
But simply inserting an instruction that clobbers CC can't be a valid 
thing to do.  You have to verify that the register isn't live at the 
point where you want to do the insertion.

Or is that the core of the problem -- that life analysis is inaccurate 
or unavailable?

Jeff

Fwd: Possible regression in DF analysis

[Claudiu Zissulescu Ianculescu]

+ gcc mailing list

---------- Forwarded message ---------
From: Claudiu Zissulescu Ianculescu <claziss@gmail.com>
Date: Tue, Dec 20, 2022 at 2:31 PM
Subject: Re: Possible regression in DF analysis
To: Jeff Law <jeffreyalaw@gmail.com>


Hi Jeff,

> Or is that the core of the problem -- that life analysis is inaccurate
> or unavailable?
>
The life analysis is not accurate/missing and loop-doloop check is not
performed, leading in inserting the doloop end pattern when it
shouldn't.
The issue is how df_analyse_loop sets the df problem subset, not
including the destination BB from the exit edges of a loop. I am
looking now how loop_post_order_compute and
loop_inverted_post_order_compute can include those missing BBs too.

Thanks,
Claudiu