[Bug tree-optimization/33302] New: follow-up on bug 33291 dead-store not eliminated

[Bug tree-optimization/33302] New: follow-up on bug 33291 dead-store not eliminated

[wouter dot vermaelen at scarlet dot be]

This is a follow-up on bug 33291. It uses the same testcase (repeated here) but
with some additional optimization flags.

-------------------------------------------
struct Clock {
 void f();
 void add(unsigned n) { a += n; }
 int a;
};

struct CPU : Clock {
 virtual ~CPU();
 unsigned char readSlow();
 void execute();

 void delay() { add(2); }
 unsigned char readFast() {
  if (unsigned char* p = ptrs[addr >> 8]) {
   // fast-path
   delay();
   delay();
   return p[addr & 255];
  } else {
   // slow-path
   return readSlow();
  }
 }

 typedef void (CPU::*FuncPtr)();
 static FuncPtr tab[256];
 unsigned char* ptrs[256];
 unsigned addr;
};

void CPU::execute() {
 f();
 while (true) {
  unsigned char b = readFast();
  delay();
  (this->*tab[b])();
 }
}
----------------------------------------

When compiled with SVN revision 128074 on a linux x86_64 machine:

> g++ -O3 -fforce-addr -ftracer -S CPU.ii
> cat CPU.s
    ...
    movl    (%rbx), %eax
    leal    4(%rax), %edx
    addl    $6, %eax
    movl    %edx, (%rbx)       #### dead store
    movzbl  (%r12), %edx
    movzbl  (%rcx,%rdx), %edx
    movl    %eax, (%rbx)
    ...


-- 
           Summary: follow-up on bug 33291   dead-store not eliminated
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: wouter dot vermaelen at scarlet dot be


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

[Bug tree-optimization/33302] dead-store not eliminated

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2007-09-05 11:33 -------
While RTL dse eliminates the redundant store to this->D.2013.a, tree-level DSE
does not do so.  (RTL dse also fails with -O3 -fforce-addr -ftracer)

<bb 4>:
  # VUSE <tab_54, SMT.9_56>
  D.2089_34 = this_2(D)->D.2013.a;
  D.2090_35 = (unsigned int) D.2089_34;
  D.2091_36 = D.2090_35 + 2;
  D.2092_37 = (int) D.2091_36;
  # tab_62 = VDEF <tab_54>
  # SMT.9_63 = VDEF <SMT.9_56>
  this_2(D)->D.2013.a = D.2092_37;
  D.2095_40 = D.2091_36 + 2;
  D.2096_41 = (int) D.2095_40;
  # tab_64 = VDEF <tab_62>
  # SMT.9_65 = VDEF <SMT.9_63>
  this_2(D)->D.2013.a = D.2096_41;
  # VUSE <tab_64, SMT.9_65>
  D.2087_42 = this_2(D)->addr;
  D.2097_43 = (long unsigned int) D.2087_42;
  D.2098_44 = D.2097_43 & 255;
  D.2099_45 = p_33 + D.2098_44;
  # VUSE <tab_64, SMT.9_65>
  b_46 = *D.2099_45;
  goto <bb 6>;

clearly there is no reason for DSE not to discard the store.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |missed-optimization, TREE
   Last reconfirmed|0000-00-00 00:00:00         |2007-09-05 11:33:31
               date|                            |
            Summary|follow-up on bug 33291      |dead-store not eliminated
                   |dead-store not eliminated   |


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

[Bug tree-optimization/33302] dead-store not eliminated

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2007-09-05 11:48 -------
DSE does a post-dominator walk starting from the exit block.  But the exit
block
has no predecessors because the function does never exit ;)

void foo(int *p)
{
  while (1)
    {
      *p = 0;
      *p = 0;
    }
}

after DSE:

foo (p)
{
<bb 2>:

<bb 3>:
  *p_1(D) = 0;
  *p_1(D) = 0;
  goto <bb 3>;

}

I suppose more post-dom walk optimizations are affected by this "bug".


-- 


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

[Bug tree-optimization/33302] dead-store not eliminated

[steven at gcc dot gnu dot org]

------- Comment #3 from steven at gcc dot gnu dot org  2007-09-05 12:35 -------
You can connect the exits by inserting fake edges. See
add_noreturn_fake_exit_edges and connect_infinite_loops_to_exit. Not sure which
one you would need in this case. Just be sure to call it before computing
(post)dominator info.


-- 


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

[Bug tree-optimization/33302] dead-store not eliminated

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2007-09-05 12:41 -------
Ah, I only found add_noreturn_fake_exit_edges which obviously didn't help.
connect_infinite_loops_to_exit does.  Thx.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-09-05 11:33:31         |2007-09-05 12:41:53
               date|                            |


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

[Bug tree-optimization/33302] dead-store not eliminated

[rakdver at gcc dot gnu dot org]

------- Comment #5 from rakdver at gcc dot gnu dot org  2007-09-05 12:51 -------
(In reply to comment #4)
> Ah, I only found add_noreturn_fake_exit_edges which obviously didn't help.
> connect_infinite_loops_to_exit does.  Thx.

dominance.c contains code (probably buggy) that adds such edges implicitly, so
this should not be needed.


-- 


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

[Bug tree-optimization/33302] dead-store not eliminated

[rguenther at suse dot de]

------- Comment #6 from rguenther at suse dot de  2007-09-05 14:17 -------
Subject: Re:  dead-store not eliminated

On Wed, 5 Sep 2007, rakdver at gcc dot gnu dot org wrote:

> (In reply to comment #4)
> > Ah, I only found add_noreturn_fake_exit_edges which obviously didn't help.
> > connect_infinite_loops_to_exit does.  Thx.
> 
> dominance.c contains code (probably buggy) that adds such edges implicitly, so
> this should not be needed.

Maybe, but then domwalk.c is buggy as walk_dominator_tree does

  while (true)
    {
      /* Don't worry about unreachable blocks.  */
      if (EDGE_COUNT (bb->preds) > 0 || bb == ENTRY_BLOCK_PTR)
        {

and obviously in my case bb (the exit block) has no preds.  Maybe
simply special-casing EXIT_BLOCK_PTR as well helps.

Richard.


-- 


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

[Bug tree-optimization/33302] dead-store not eliminated

[rakdver at kam dot mff dot cuni dot cz]

------- Comment #7 from rakdver at kam dot mff dot cuni dot cz  2007-09-05 14:30 -------
Subject: Re:  dead-store not eliminated

> > > Ah, I only found add_noreturn_fake_exit_edges which obviously didn't help.
> > > connect_infinite_loops_to_exit does.  Thx.
> > 
> > dominance.c contains code (probably buggy) that adds such edges implicitly, so
> > this should not be needed.
> 
> Maybe, but then domwalk.c is buggy as walk_dominator_tree does
> 
>   while (true)
>     {
>       /* Don't worry about unreachable blocks.  */
>       if (EDGE_COUNT (bb->preds) > 0 || bb == ENTRY_BLOCK_PTR)
>         {
> 
> and obviously in my case bb (the exit block) has no preds.  Maybe
> simply special-casing EXIT_BLOCK_PTR as well helps.

Yes, that seems reasonable (I think domwalk was originally only used
for dominator tree walks, so it may contain this kind of bugs for
post-dominator walks)


-- 


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

[Bug tree-optimization/33302] dead-store not eliminated

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2007-09-06 09:06 -------
Subject: Bug 33302

Author: rguenth
Date: Thu Sep  6 09:05:58 2007
New Revision: 128180

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=128180
Log:
2007-09-06  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/33302
        * tree-ssa-dse.c (tree_ssa_dse): Connect infinite loops
        to the exit block before doing the post-dominator walk.
        * domwalk.c (walk_dominator_tree): The exit block is
        interesting even if it is not reachable.

        * gcc.dg/tree-ssa/ssa-dse-11.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-11.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/domwalk.c
    trunk/gcc/testsuite/ChangeLog


-- 


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

[Bug tree-optimization/33302] dead-store not eliminated

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2007-09-06 09:06 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.3.0


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

[Bug tree-optimization/33302] dead-store not eliminated

[wouter dot vermaelen at scarlet dot be]

------- Comment #10 from wouter dot vermaelen at scarlet dot be  2007-09-06 11:48 -------
I'm sorry, but can you recheck? The testcase at the top of this bug report
still generates the same asm code for me.


-- 

wouter dot vermaelen at scarlet dot be changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|enhancement                 |normal


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

[Bug tree-optimization/33302] dead-store not eliminated

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2007-09-06 12:13 -------
The extra store you still see is caused by -ftracer duplicating it. 
Optimizations
after that don't catch that (because of the intervening possibly aliasing loads
I guess):

(insn 25 24 27 4 t.ii:3 (set (mem/s:SI (reg/f:DI 102) [4 <variable>.D.2014.a+0
S4 A64])
        (reg:SI 75)) 47 {*movsi_1} (expr_list:REG_DEAD (reg:SI 75)
        (expr_list:REG_EQUAL (plus:SI (mem/s:SI (reg/f:DI 102) [4
<variable>.D.2014.a+0 S4 A64])
                (const_int 4 [0x4]))
            (nil))))

(insn 27 25 28 4 t.ii:18 (set (reg:DI 78 [ <variable>.addr ])
        (zero_extend:DI (mem/s:SI (reg/f:DI 101) [4 <variable>.addr+0 S4
A64]))) 120 {zero_extendsidi2_rex64} (nil))

...

(insn 96 95 97 4 t.ii:3 (parallel [
            (set (reg:SI 83)
                (plus:SI (reg:SI 76 [ <variable>.D.2014.a ])
                    (const_int 6 [0x6])))
            (clobber (reg:CC 17 flags))
        ]) 235 {*addsi_1} (expr_list:REG_UNUSED (reg:CC 17 flags)
        (expr_list:REG_DEAD (reg:SI 84 [ <variable>.D.2014.a ])
            (nil))))

(insn 97 96 98 4 t.ii:3 (set (mem/s:SI (reg/f:DI 102) [4 <variable>.D.2014.a+0
S4 A64])
        (reg:SI 83)) 47 {*movsi_1} (expr_list:REG_EQUAL (plus:SI (mem/s:SI
(reg/f:DI 102) [4 <variable>.D.2014.a+0 S4 A64])
            (const_int 2 [0x2]))
        (expr_list:REG_DEAD (reg:SI 83)
            (nil))))


If you build without -ftracer or without -fforce-addr it works (but won't
combine the add on one path).  But.. -ftracer was supposed to be moved
to the tree level...


-- 


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