[Bug rtl-optimization/48773] New: Dataflow and REG_DEAD notes

[Bug rtl-optimization/48773] New: Dataflow and REG_DEAD notes

[mfortune at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48773

           Summary: Dataflow and REG_DEAD notes
           Product: gcc
           Version: 4.3.5
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: mfortune@gmail.com


Hello all,

I have recently been updating an out of tree target from GCC 4.2.4 to GCC 4.3.5
and have noticed that REG_DEAD notes can get out of sync at the end of multiple
passes. (i.e. be attached to instructions where the register does not die)

The first pass that appears to get REG_DEAD notes out of sync is GCSE. This
gets fixed and broken multiple times as some of the later passes solve the DF
note problem via df_analyze, some delete all notes and some get the notes out
of sync again. When the second schedule pass (sched2) runs the DF note problem
is solved at the start but then instructions can be re-ordered and notes are
once again left out of sync. In my case this causes (an admittedly old)
peephole to be applied incorrectly and bad code is generated. 

It seems to be that each pass, which may get notes out of sync, should run the
note problem before finishing.

With some experimentation I have seen that running df_analyze to solve the note
problem at the end of some passes leads to an apparent improvement in the code.
 It would therefore seem that some passes use REG_DEAD information without
first solving the REG_DEAD problem. This sounds reasonable as I would expect
each pass to end leaving notes valid.

Is the behaviour I have described here intentional? If so, could someone
explain the rationale? I can't see any changes in this area (up to trunk) and I
have seen REG_DEAD notes get out of sync with at least one in-tree target for
which I could provide a testcase if that is useful (GCC 4.5.1). This issue is
quite general though so I believe a large amount of code should trigger the
notes to get out of sync. This clearly does not lead to actual bugs in most
cases otherwise it would have already been reported.

regards,
Matthew

[Bug rtl-optimization/48773] Dataflow and REG_DEAD notes

[mfortune at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48773

--- Comment #1 from Matthew Fortune <mfortune at gmail dot com> 2011-04-28 11:59:09 UTC ---
Created attachment 24124
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24124
testcase

[Bug rtl-optimization/48773] Dataflow and REG_DEAD notes

[mfortune at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48773

--- Comment #2 from Matthew Fortune <mfortune at gmail dot com> 2011-04-28 12:00:01 UTC ---
Created attachment 24125
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24125
ce3 dump

[Bug rtl-optimization/48773] Dataflow and REG_DEAD notes

[mfortune at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48773

--- Comment #3 from Matthew Fortune <mfortune at gmail dot com> 2011-04-28 12:01:17 UTC ---
Created attachment 24126
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24126
nothrow dump

[Bug rtl-optimization/48773] Dataflow and REG_DEAD notes

[mfortune at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48773

Matthew Fortune <mfortune at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|4.3.5                       |4.6.0

--- Comment #4 from Matthew Fortune <mfortune at gmail dot com> 2011-04-28 12:03:22 UTC ---
Hello all,

I have re-produced this issue using GCC 4.6.0 targetting x86 linux. The
compiler does not produce bad code but the testcase shows how REG_DEAD notes
can be invalid in the final pass which can then cause peepholes to go wrong.
This is just one example, other passes that use REG_DEAD notes could go equally
wrong if they do not specifically analyze/run the dataflow note problem (not
sure if any other passes would actually suffer from this).

[mfortune@mfortune-linux test]$ ../tk_x86/bin/gcc -v
Using built-in specs.
COLLECT_GCC=../tk_x86/bin/gcc
COLLECT_LTO_WRAPPER=/home/mfortune/gcc-4.6.0-root/libexec/gcc/i686-pc-linux-gnu/4.6.0/lto-wrapper
Target: i686-pc-linux-gnu
Configured with: ../gcc-4.6.0/configure --prefix=/home/mfortune/gcc-4.6.0-root
--enable-languages=c --with-gmp=/home/mfortune/gcc-4.6.0-prereq/
Thread model: posix
gcc version 4.6.0 (GCC)

The second scheduling pass has to be disabled to demonstrate this particular
instance of the bug.

gcc -O2 -S -dapA inflate.i -fno-schedule-insns2

A REG_DEAD note is correctly added tgo insn 3388 in the ce3 dump:
-- ce3 --
(insn 3387 1196 1197 173 (set (reg:SI 3 bx)
        (mem/c:SI (plus:SI (reg/f:SI 7 sp)
                (const_int 60 [0x3c])) [11 %sfp+-68 S4 A32]))
lib/zlib_inflate/inflate.c:435 50 {*movsi_internal}
     (nil))

(insn 1197 3387 3388 173 (set (reg/v:SI 6 bp [orig:117 hold ] [117])
        (mem/s:SI (plus:SI (reg:SI 3 bx)
                (const_int 52 [0x34])) [5 MEM[(struct inflate_state
*)D.3891_186].hold+0 S4 A32])) lib/zlib_inflate/inflate.c:435 50
{*movsi_internal}
     (nil))

(insn 3388 1197 1198 173 (set (reg:SI 0 ax)
        (reg:SI 3 bx)) lib/zlib_inflate/inflate.c:435 50 {*movsi_internal}
     (expr_list:REG_DEAD (reg:SI 3 bx)
        (nil)))

(insn 1198 3388 3389 173 (set (reg/v:SI 3 bx [orig:138 bits ] [138])
        (mem/s:SI (plus:SI (reg:SI 0 ax)
                (const_int 56 [0x38])) [4 MEM[(struct inflate_state
*)D.3891_186].bits+0 S4 A32])) lib/zlib_inflate/inflate.c:435 50
{*movsi_internal}
     (nil))
-- end ce3 --

REG_DEAD notes are left to get out of sync as shown in cprop_hardreg dump:
-- cprop_hardreg --
(insn 3387 1196 1197 173 (set (reg:SI 3 bx)
        (mem/c:SI (plus:SI (reg/f:SI 7 sp)
                (const_int 60 [0x3c])) [11 %sfp+-68 S4 A32]))
lib/zlib_inflate/inflate.c:435 50 {*movsi_internal}
     (nil))

(insn 1197 3387 3388 173 (set (reg/v:SI 6 bp [orig:117 hold ] [117])
        (mem/s:SI (plus:SI (reg:SI 3 bx)
                (const_int 52 [0x34])) [5 MEM[(struct inflate_state
*)D.3891_186].hold+0 S4 A32])) lib/zlib_inflate/inflate.c:435 50
{*movsi_internal}
     (nil))

(insn 3388 1197 1198 173 (set (reg:SI 0 ax)
        (reg:SI 3 bx)) lib/zlib_inflate/inflate.c:435 50 {*movsi_internal}
     (expr_list:REG_DEAD (reg:SI 3 bx)
        (nil)))

(insn 1198 3388 3389 173 (set (reg/v:SI 3 bx [orig:138 bits ] [138])
        (mem/s:SI (plus:SI (reg:SI 3 bx [0])
                (const_int 56 [0x38])) [4 MEM[(struct inflate_state
*)D.3891_186].bits+0 S4 A32])) lib/zlib_inflate/inflate.c:435 50
{*movsi_internal}
     (nil))
-- end cprop_hardreg --

REG_DEAD notes are still out of sync just before final:
-- nothrow --
(insn 3387 1196 1197 237 (set (reg:SI 3 bx)
        (mem/c:SI (plus:SI (reg/f:SI 7 sp)
                (const_int 60 [0x3c])) [11 %sfp+-68 S4 A32]))
lib/zlib_inflate/inflate.c:435 50 {*movsi_internal}
     (nil))

(insn 1197 3387 3388 237 (set (reg/v:SI 6 bp [orig:117 hold ] [117])
        (mem/s:SI (plus:SI (reg:SI 3 bx)
                (const_int 52 [0x34])) [5 MEM[(struct inflate_state
*)D.3891_186].hold+0 S4 A32])) lib/zlib_inflate/inflate.c:435 50
{*movsi_internal}
     (nil))

(insn 3388 1197 1198 237 (set (reg:SI 0 ax)
        (reg:SI 3 bx)) lib/zlib_inflate/inflate.c:435 50 {*movsi_internal}
     (expr_list:REG_DEAD (reg:SI 3 bx)
        (nil)))

(insn 1198 3388 1199 237 (set (reg/v:SI 3 bx [orig:138 bits ] [138])
        (mem/s:SI (plus:SI (reg:SI 3 bx [0])
                (const_int 56 [0x38])) [4 MEM[(struct inflate_state
*)D.3891_186].bits+0 S4 A32])) lib/zlib_inflate/inflate.c:435 50
{*movsi_internal}
     (nil))
-- end nothrow --

This sequence of code 'could' then have a peephole applied to it such that the
bx register is replaced with ax in insns 3387, 1197 and insn 3388 is deleted.
There is no such peephole for i386 but other architectures do have peepholes
that rely on REG_DEAD notes being correct.

Attached inflate.i and full dumps for the ce3 and nothrow passes mentioned
above with REG_DEAD_DEBUGGING enabled

regards,
Matthew

[Bug rtl-optimization/48773] Dataflow and REG_DEAD notes

[ebotcazou at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48773

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.04.28 20:48:36
                 CC|                            |ebotcazou at gcc dot
                   |                            |gnu.org
     Ever Confirmed|0                           |1
           Severity|major                       |normal

--- Comment #5 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2011-04-28 20:48:36 UTC ---
This is a known issue introduced by the DF merge.  I think that the current
state of affairs is that the passes consuming REG_DEAD/REG_UNUSED notes have to
invoke df_note_add_problem on entry.

[Bug rtl-optimization/48773] Dataflow and REG_DEAD notes

[mfortune at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48773

--- Comment #6 from Matthew Fortune <mfortune at gmail dot com> 2011-05-04 16:19:32 UTC ---
(In reply to comment #5)
> This is a known issue introduced by the DF merge.  I think that the current
> state of affairs is that the passes consuming REG_DEAD/REG_UNUSED notes have to
> invoke df_note_add_problem on entry.

Can anyone speculate as to which passes consume REG_DEAD notes or is it a case
of trawling the source? invoking df_note_add_problem in the final pass should
resolve the bug I have seen but I expect there are more.

[Bug rtl-optimization/48773] Dataflow and REG_DEAD notes

[ebotcazou at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48773

--- Comment #7 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2011-05-04 16:38:54 UTC ---
> Can anyone speculate as to which passes consume REG_DEAD notes or is it a case
> of trawling the source? invoking df_note_add_problem in the final pass should
> resolve the bug I have seen but I expect there are more.

The latter.  That would be a little surprising at this point.

[Bug rtl-optimization/48773] Dataflow and REG_DEAD notes

[froydnj at codesourcery dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48773

--- Comment #8 from froydnj at codesourcery dot com <froydnj at codesourcery dot com> 2011-05-04 16:47:52 UTC ---
On Wed, May 04, 2011 at 04:25:19PM +0000, mfortune at gmail dot com wrote:
> Can anyone speculate as to which passes consume REG_DEAD notes or is it a case
> of trawling the source? invoking df_note_add_problem in the final pass should
> resolve the bug I have seen but I expect there are more.

Grepping for REG_DEAD shows up a number of places.

[Bug rtl-optimization/48773] Dataflow and REG_DEAD notes

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48773

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |INVALID

--- Comment #9 from Steven Bosscher <steven at gcc dot gnu.org> ---
It's up to a pass that needs these notes to compute them.