[Bug middle-end/30905] New: [dataflow] Fails to cross-jump

[Bug middle-end/30905] New: [dataflow] Fails to cross-jump

[rguenth at gcc dot gnu dot org]

static int a[30];
static int b[30];
int gen_int(int);
void kernel ()
{
  int i;

  i = gen_int (1);

  if (i != 0)
    {
      a[0] = a[0] + (a[0] & 3);
      b[0] = b[0] + (b[0] | 3);
    }
  else
    {
      a[0] = a[0] + (a[0] & 3);
      b[0] = b[0] + (b[0] | 3);
    }
  if (i != 1)
    {
      a[1] = a[1] + (a[1] & 3);
      b[1] = b[1] + (b[1] | 3);
    }
  else
    {
      a[1] = a[1] + (a[1] & 3);
      b[1] = b[1] + (b[1] | 3);
    }
}

is optimized by mainline to straight line code without compares and jumps at
-O2.  dataflow branch retains the comparisons with i and the duplicate
instructions.


-- 
           Summary: [dataflow] Fails to cross-jump
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rguenth at gcc dot gnu dot org


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

[Bug middle-end/30905] [dataflow] Fails to cross-jump

[steven at gcc dot gnu dot org]

------- Comment #1 from steven at gcc dot gnu dot org  2007-02-21 20:59 -------
Confirmed, we almost never do cross-jumping on the dataflow-branch anymore:
only after regmove.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-02-21 20:59:58
               date|                            |


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

[Bug middle-end/30905] [dataflow] Fails to cross-jump

[steven at gcc dot gnu dot org]

------- Comment #2 from steven at gcc dot gnu dot org  2007-02-21 22:09 -------
On the trunk, *and* on the dataflow branch, we crossjump the code starting with
"if (i != 1)" on the first cleanup_cfg iteration when it's called from
rest_of_handle_stack_adjustments.  Trunk then goes on to crossjump the other
blocks, but the df-branch stops because there is a set to the CC-reg in the
way. That set has a REG_UNUSED flag on it.

What probably happens, is that flow on the trunk does some dce in the liveness
update, and the df-branch does not.


-- 


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

[Bug middle-end/30905] [dataflow] Fails to cross-jump

[steven at gcc dot gnu dot org]

------- Comment #3 from steven at gcc dot gnu dot org  2007-05-08 23:15 -------
This patch would fix it, but it's brute-force and it causes a ~1.5% slowdown. 
Some form of DCE a little more delicate than this will be necessary to fix this
bug, though.


Index: cfgcleanup.c
===================================================================
--- cfgcleanup.c        (revision 124550)
+++ cfgcleanup.c        (working copy)
@@ -2286,10 +2286,10 @@ cleanup_cfg (int mode)
     {
       delete_unreachable_blocks (), changed = true;
       if (!(mode & CLEANUP_NO_INSN_DEL)
-         && (mode & CLEANUP_EXPENSIVE)
-         && !reload_completed)
+         && (mode & (CLEANUP_EXPENSIVE | CLEANUP_CROSSJUMP)))
        {
-         if (!delete_trivially_dead_insns (get_insns (), max_reg_num ()))
+         gcc_assert (df);
+         if (! run_fast_dce ())
            break;
        }
       else
@@ -2343,10 +2343,9 @@ static unsigned int
 rest_of_handle_jump2 (void)
 {
   delete_trivially_dead_insns (get_insns (), max_reg_num ());
+  delete_unreachable_blocks ();
   if (dump_file)
     dump_flow_info (dump_file, dump_flags);
-  cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0)
-              | (flag_thread_jumps ? CLEANUP_THREADING : 0));
   return 0;
 }


-- 


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2007-06-12 19:17 -------
Now in mainline.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.2.0
            Summary|[dataflow] Fails to cross-  |[4.3 Regression] Fails to
                   |jump                        |cross-jump
   Target Milestone|---                         |4.3.0


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[pinskia at gcc dot gnu dot org]

------- Comment #5 from pinskia at gcc dot gnu dot org  2007-07-04 22:35 -------
I can't reproduce this on the trunk,  unless I am making a mistake.  I think
the cross jump is happening now.


-- 


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2007-07-05 08:41 -------
For 4.1.x I get

kernel:
.LFB2:
        subq    $8, %rsp
.LCFI0:
        movl    $1, %edi
        call    gen_int
        movl    a(%rip), %eax
        movl    %eax, %edx
        andl    $3, %edx
        addl    %edx, %eax
        movl    %eax, a(%rip)
        movl    b(%rip), %eax
        movl    %eax, %edx
        orl     $3, %edx
        addl    %edx, %eax
        movl    %eax, b(%rip)
        movl    a+4(%rip), %eax
        movl    %eax, %edx
        andl    $3, %edx
        addl    %edx, %eax
        movl    %eax, a+4(%rip)
        movl    b+4(%rip), %eax
        movl    %eax, %edx
        orl     $3, %edx
        addl    %edx, %eax
        movl    %eax, b+4(%rip)
        addq    $8, %rsp
        ret

while with trunk we have

kernel:
.LFB2:
        subq    $8, %rsp
.LCFI0:
        movl    $1, %edi
        call    gen_int
        testl   %eax, %eax
        je      .L2
        movl    a(%rip), %edx
        movl    %edx, %eax
        andl    $3, %eax
        addl    %edx, %eax
        movl    b(%rip), %edx
        movl    %eax, a(%rip)
        movl    %edx, %eax
        orl     $3, %eax
        addl    %edx, %eax
        movl    %eax, b(%rip)
.L7:
        movl    a+4(%rip), %edx
        movl    %edx, %eax
        andl    $3, %eax
        addl    %edx, %eax
        movl    b+4(%rip), %edx
        movl    %eax, a+4(%rip)
        movl    %edx, %eax
        orl     $3, %eax
        addl    %edx, %eax
        movl    %eax, b+4(%rip)
        addq    $8, %rsp
        ret
        .p2align 4,,10
        .p2align 3
.L2:
        movl    a(%rip), %edx
        movl    %edx, %eax
        andl    $3, %eax
        addl    %edx, %eax
        movl    b(%rip), %edx
        movl    %eax, a(%rip)
        movl    %edx, %eax
        orl     $3, %eax
        addl    %edx, %eax
        movl    %eax, b(%rip)
        jmp     .L7
.LFE2:

so, no, this is not yet fixed.


-- 


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[steven at gcc dot gnu dot org]

------- Comment #7 from steven at gcc dot gnu dot org  2007-10-16 13:34 -------
Does not really "block" 24001, but the test case for that bug would be fixed if
code hoisting would be implemented properly.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |24001
              nThis|                            |


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[steven at gcc dot gnu dot org]

------- Comment #8 from steven at gcc dot gnu dot org  2008-01-10 19:18 -------
We start with a CFG that looks like this (all edges directed down):

ENTRY
|
2
|\
| \
3  5
|\  \
| \  \
7  4--6
 \   /
  \ /
   8
   |
  EXIT

where basic block 4 is a forwarder block.  Insns in blocks 6 and 7 match and
are cross-jumped, to give a new CFG:

ENTRY
|
2
|\
| \
3  5
|\  \
| \  \
|  4--6
 \   /
  \ /
   7
   |
   8
   |
  EXIT

where basic blocks 4 *and* 6 are now forwarder blocks.  try_optimize_cfg then
removes the redundant forwarders, which results in the following simpler CFG:

ENTRY
|
2
|\
3 5
|/
7
|
EXIT

where basic blocks 3 and 5 have matching insns that could be cross-jumped,
except that there is a dead "(set (reg:CCZ 17 flags) (compare ...))" in the way
that the delete_trivially_dead_insns() call in cleanup_cfg() can obviously not
delete.  If that dead SET is deleted, blocks 3 and 5 are merged and we get the
same code as previous releases.

In pre-DF gcc releases, a liveness update would run a liveness update with dead
code elimination.  Copying that code from the GCC 4.2 release branch:

          /* Cleaning up CFG introduces more opportunities for dead code
             removal that in turn may introduce more opportunities for
             cleaning up the CFG.  */
          if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
                                                 PROP_DEATH_NOTES
                                                 | PROP_SCAN_DEAD_CODE
                                                 | PROP_KILL_DEAD_CODE
                                                 | ((mode & CLEANUP_LOG_LINKS)
                                                    ? PROP_LOG_LINKS : 0)))

I don't believe we have to aggressively delete dead code on every cleanup_cfg()
iteration.  We did plenty experiments with that on the DF branch, and running
DCE all the time just loses in the cost/benefit trade-off.  As I've noted
before, we should remove dead code when it is beneficial.

In this case, when we remove the forwarder edges and turn a conditional jump
into a non-conditional jump, we should kill the code that computes the
condition if the condition is dead at the end of the basic block.  We can do
this if we have liveness information available during cleanup_cfg().


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2007-02-21 20:59:58         |2008-01-10 19:18:34
               date|                            |


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[steven at gcc dot gnu dot org]

------- Comment #9 from steven at gcc dot gnu dot org  2008-01-10 20:16 -------
Created an attachment (id=14915)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14915&action=view)
Fix using run_fast_dce

I see no way around running run_fast_DCE.  But at least let's try to run it
only when really necessary, and try to avoid unnecessary repetitive work if
CLEANUP_CROSSJUMP is set.


-- 


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[zadeck at naturalbridge dot com]

------- Comment #10 from zadeck at naturalbridge dot com  2008-01-11 13:15 -------
stevens patch bootstrapped and regression tested on x86-86, ppc-32 and ia-64.


-- 


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2008-01-11 13:41 -------
The patch is ok.


-- 


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[stevenb dot gcc at gmail dot com]

------- Comment #12 from stevenb dot gcc at gmail dot com  2008-01-11 13:48 -------
Subject: Re:  [4.3 Regression] Fails to cross-jump

Richi, could you commit it for me?


-- 


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[rguenth at gcc dot gnu dot org]

------- Comment #13 from rguenth at gcc dot gnu dot org  2008-01-11 14:56 -------
Subject: Bug 30905

Author: rguenth
Date: Fri Jan 11 14:55:34 2008
New Revision: 131468

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=131468
Log:
2008-01-11  Steven Bosscher  <stevenb.gcc@gmail.com>

        PR rtl-optimization/30905
        * cfgcleanup.c: Include dce.h
        (crossjumps_occured): New global variable.
        (try_crossjump_bb): Exit loop after finding a fallthru edge.
        If something changed, set crossjumps_occured to true.
        (try_optimize_cfg): Clear crossjumps_occured at the beginning.
        Don't add/remove fake edges to exit here...
        (cleanup_cfg): ...but do it here, when crossjumping.
        Run a fast DCE when successful crossjumps occured in the latest
        iteration of try_optimize_cfg.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cfgcleanup.c


-- 


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[steven at gcc dot gnu dot org]

------- Comment #14 from steven at gcc dot gnu dot org  2008-01-11 15:09 -------
Whee, thanks Kenny and Richi!!!

Zapp...


-- 

steven at gcc dot gnu dot org changed:

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


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[rahul at icerasemi dot com]

------- Comment #15 from rahul at icerasemi dot com  2009-06-11 17:38 -------
GCC4.4 is still missing this fix. GCC-4.4.1 (20090507) on x86_64 produces the
following with O2/O3

kernel:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $24, %esp
        movl    $1, (%esp)
        call    gen_int
        testl   %eax, %eax
        je      .L2
        movl    a, %edx
        movl    %edx, %ecx
        andl    $3, %ecx
        leal    (%ecx,%edx), %edx
        movl    %edx, a
        movl    b, %edx
        movl    %edx, %ecx
        orl     $3, %ecx
        leal    (%ecx,%edx), %edx
        movl    %edx, b
.L7:
        movl    a+4, %eax
        movl    %eax, %edx
        andl    $3, %edx
        leal    (%edx,%eax), %eax
        movl    %eax, a+4
        movl    b+4, %eax
        movl    %eax, %edx
        orl     $3, %edx
        leal    (%edx,%eax), %eax
        movl    %eax, b+4
        leave
        ret
        .p2align 4,,7
        .p2align 3
.L2:
        movl    a, %eax
        movl    %eax, %edx
        andl    $3, %edx
        leal    (%edx,%eax), %eax
        movl    %eax, a
        movl    b, %eax
        movl    %eax, %edx
        orl     $3, %edx
        leal    (%edx,%eax), %eax
        movl    %eax, b
        jmp     .L7

Any reason why this shouldn't go into 4.4?


-- 

rahul at icerasemi dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rahul at icerasemi dot com


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[steven at gcc dot gnu dot org]

------- Comment #16 from steven at gcc dot gnu dot org  2009-06-11 19:48 -------
The patch is in 4.4.  Apparently it doesn't work?  I'll have another look...


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|FIXED                       |


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[steven at gcc dot gnu dot org]

-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |steven at gcc dot gnu dot
                   |dot org                     |org
             Status|REOPENED                    |ASSIGNED
   Last reconfirmed|2008-01-10 19:18:34         |2009-06-11 19:49:12
               date|                            |


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

[Bug middle-end/30905] [4.3 Regression] Fails to cross-jump

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.3.0                       |4.3.5


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

[Bug middle-end/30905] [4.3/4.4/4.5 Regression] Fails to cross-jump

[steven at gcc dot gnu dot org]

------- Comment #17 from steven at gcc dot gnu dot org  2010-01-09 22:17 -------
In GCC 4.4 only one crossjump happens. The second crossjump does not happen
because the basic blocks are not identical. The register allocator has not
allocated the registers in the same way:
                                        .L2:
        movl    a, %edx                         movl    a, %eax
        movl    %edx, %ecx                      movl    %eax, %edx
        andl    $3, %ecx                        andl    $3, %edx
        leal    (%ecx,%edx), %edx               leal    (%edx,%eax), %eax
        movl    %edx, a                         movl    %eax, a
        movl    b, %edx                         movl    b, %eax
        movl    %edx, %ecx                      movl    %eax, %edx
        orl     $3, %ecx                        orl     $3, %edx
        leal    (%ecx,%edx), %edx               leal    (%edx,%eax), %eax
        movl    %edx, b                         movl    %eax, b
                                                jmp     .L7

The problem in this case is thus, that there is no pre-RA crossjumping pass
anymore.

Works for me with my patch for PR20070.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |20070
      Known to fail|                            |4.4.0 4.4.1 4.4.2 4.5.0
            Summary|[4.3 Regression] Fails to   |[4.3/4.4/4.5 Regression]
                   |cross-jump                  |Fails to cross-jump


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

[Bug middle-end/30905] [4.3/4.4/4.5 Regression] Fails to cross-jump

[steven at gcc dot gnu dot org]

------- Comment #18 from steven at gcc dot gnu dot org  2010-02-12 21:11 -------
As far as I'm concerned, this is WONTFIX for all affected compilers.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|steven at gcc dot gnu dot   |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


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

[Bug middle-end/30905] [4.3/4.4/4.5 Regression] Fails to cross-jump

[steven at gcc dot gnu dot org]

------- Comment #19 from steven at gcc dot gnu dot org  2010-03-21 12:03 -------
Cause here is better register allocation and lack of cross-jumping before
register allocation. This will not be fixed. For GCC 4.6 we should add a
cross-jumping patch (an improved version if this pass, anyway) before RA.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
           Keywords|                            |ra
         Resolution|                            |WONTFIX


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