Re: Dead-code elimination can't remove string copy insns?

Re: Dead-code elimination can't remove string copy insns?

[Naveen Sharma, Noida]

> >> but the alias information should be sufficient to see that 
> the memory region being written into is on the stack, and unused past 
> this insn, hence the store is dead and can be deleted.
> 
> > It should, but we don't do that currently.
> 
> Do you have a sense for how hard this would be to implement?  Is it
> something that's done on tree-ssa, so there's no point adding it in
> mainline?  Will Naveen's stack-slot allocator help?

The stack pseudos rely on the flow infrastructure.
At the moment, the dead stores to the stack should be removed 
in the tail blocks (but not for BLKmode mems). 
But it should be simple to teach flow analysis to handle this 
case with stack pseudos.

Best Regards,
  Naveen Sharma.

Dead-code elimination can't remove string copy insns?

[Zack Weinberg]

On an x86 (i386-linux, -march=i386), I'm seeing this insn survive
intact from initial RTL generation all the way to final, despite the
fact that all its outputs are dead:

(insn 15 13 52 0 0x4019191c (parallel [
            (set (reg:SI 62)
                (const_int 0 [0x0]))
            (set (reg/f:SI 59)
                (plus:SI (ashift:SI (reg:SI 61)
                        (const_int 2 [0x2]))
                    (reg/f:SI 59)))
            (set (reg/f:SI 60)
                (plus:SI (ashift:SI (reg:SI 61)
                        (const_int 2 [0x2]))
                    (reg/f:SI 60)))
            (set (mem/s:BLK (reg/f:SI 59) [4 S+0 S24 A128])
                (mem/s/u:BLK (reg/f:SI 60) [1 S24 A32]))
            (use (reg:SI 61))
            (use (reg:SI 19 dirflag))
        ]) 472 {rep_movsi}
    (insn_list 10 (insn_list 11 (insn_list 12 (insn_list 13 (nil)))))
    (expr_list:REG_DEAD (reg:SI 19 dirflag)
        (expr_list:REG_DEAD (reg:SI 61)
            (expr_list:REG_UNUSED (reg:SI 62)
                (expr_list:REG_UNUSED (reg/f:SI 59)
                    (expr_list:REG_UNUSED (reg/f:SI 60)
                        (nil)))))))

On an RS/6000 (rs6000-ibm-aix5, no -m switches), the same thing
happens to:

(insn 11 55 47 0 0x403a40c0 (parallel [
            (set (mem/s:BLK (reg/f:SI 128) [6 S+0 S24 A128])
                (mem/s/u:BLK (reg/f:SI 119) [2 S24 A32]))
            (use (const_int 24 [0x18]))
            (use (const_int 4 [0x4]))
            (clobber (reg:SI 5 r5))
            (clobber (reg:SI 6 r6))
            (clobber (reg:SI 7 r7))
            (clobber (reg:SI 8 r8))
            (clobber (reg:SI 9 r9))
            (clobber (reg:SI 10 r10))
            (clobber (scratch:SI))
        ]) 344 {*rs6000.md:9244}
    (insn_list 10 (insn_list 55 (nil)))
    (expr_list:REG_DEAD (reg/f:SI 119)
        (expr_list:REG_DEAD (reg/f:SI 128)
            (expr_list:REG_UNUSED (reg:SI 5 r5)
                (expr_list:REG_UNUSED (reg:SI 6 r6)
                    (expr_list:REG_UNUSED (reg:SI 7 r7)
                        (expr_list:REG_UNUSED (reg:SI 8 r8)
                            (expr_list:REG_UNUSED (reg:SI 9 r9)
                                (expr_list:REG_UNUSED (reg:SI 10 r10)
                                    (expr_list:REG_UNUSED (scratch:SI)
                                        (nil)))))))))))

Why can't anything delete these insns? I'm guessing it has something
to do with the BLKmode memory access, but the alias information should
be sufficient to see that the memory region being written into is on
the stack, and unused past this insn, hence the store is dead and can
be deleted.

Full dumps on request.  The above snippets are from the .life dump.
The input file is gcc.dg/const-elim-1.c.

zw

Re: Dead-code elimination can't remove string copy insns?

[Dale Johannesen]

On Monday, May 12, 2003, at 05:26  PM, Zack Weinberg wrote:
> Why can't anything delete these insns? I'm guessing it has something
> to do with the BLKmode memory access, but the alias information should
> be sufficient to see that the memory region being written into is on
> the stack, and unused past this insn, hence the store is dead and can
> be deleted.

Can it tell the region's address hasn't been taken and stored somewhere?

> Full dumps on request.  The above snippets are from the .life dump.
> The input file is gcc.dg/const-elim-1.c.

Re: Dead-code elimination can't remove string copy insns?

[Zack Weinberg]

Dale Johannesen <dalej@apple.com> writes:

> On Monday, May 12, 2003, at 05:26  PM, Zack Weinberg wrote:
>> Why can't anything delete these insns? I'm guessing it has something
>> to do with the BLKmode memory access, but the alias information should
>> be sufficient to see that the memory region being written into is on
>> the stack, and unused past this insn, hence the store is dead and can
>> be deleted.
>
> Can it tell the region's address hasn't been taken and stored somewhere?

I don't know what it can or can't tell.  In the initial RTL, the
region's address was taken and passed to a subroutine call, but CSE
deletes all of that, because it's unreachable.  By the time we get to
life analysis, the insn I quoted is the last one in the function, so
even if someone had stored the address somewhere, using it would
provoke undefined behavior.

zw

Re: Dead-code elimination can't remove string copy insns?

[Michael Matz]

Hi,

On Mon, 12 May 2003, Zack Weinberg wrote:

> On an x86 (i386-linux, -march=i386), I'm seeing this insn survive
> intact from initial RTL generation all the way to final, despite the
> fact that all its outputs are dead:
>
> (insn 15 13 52 0 0x4019191c (parallel [
> ...
>             (set (mem/s:BLK (reg/f:SI 59) [4 S+0 S24 A128])
>                 (mem/s/u:BLK (reg/f:SI 60) [1 S24 A32]))
>
> Why can't anything delete these insns? I'm guessing it has something
> to do with the BLKmode memory access,

Exactly.  We don't track dead stores to memory.

> but the alias information should be sufficient to see that the memory
> region being written into is on the stack, and unused past this insn,
> hence the store is dead and can be deleted.

It should, but we don't do that currently.


Ciao,
Michael.

Re: Dead-code elimination can't remove string copy insns?

[Zack Weinberg]

Michael Matz <matz@suse.de> writes:

>> but the alias information should be sufficient to see that the memory
>> region being written into is on the stack, and unused past this insn,
>> hence the store is dead and can be deleted.
>
> It should, but we don't do that currently.

Do you have a sense for how hard this would be to implement?  Is it
something that's done on tree-ssa, so there's no point adding it in
mainline?  Will Naveen's stack-slot allocator help?

zw

Re: Dead-code elimination can't remove string copy insns?

[Diego Novillo]

On Tue, 2003-05-13 at 12:17, Zack Weinberg wrote:
> Michael Matz <matz@suse.de> writes:
> 
> >> but the alias information should be sufficient to see that the memory
> >> region being written into is on the stack, and unused past this insn,
> >> hence the store is dead and can be deleted.
> >
> > It should, but we don't do that currently.
> 
> Do you have a sense for how hard this would be to implement?  Is it
> something that's done on tree-ssa, so there's no point adding it in
> mainline?  Will Naveen's stack-slot allocator help?
> 
If you show me the original source code I could tell you.  Once things
are in RTL form, it's difficult for me to trace them back into trees. 
There's also the situation in which we have dead code at the RTL level
that it's impossible to detect at the tree level (e.g. address
arithmetic for array references).


Diego.

Re: Dead-code elimination can't remove string copy insns?

[Zack Weinberg]

Diego Novillo <dnovillo@redhat.com> writes:

> On Tue, 2003-05-13 at 12:17, Zack Weinberg wrote:
>> Michael Matz <matz@suse.de> writes:
>> 
>> >> but the alias information should be sufficient to see that the memory
>> >> region being written into is on the stack, and unused past this insn,
>> >> hence the store is dead and can be deleted.
>> >
>> > It should, but we don't do that currently.
>> 
>> Do you have a sense for how hard this would be to implement?  Is it
>> something that's done on tree-ssa, so there's no point adding it in
>> mainline?  Will Naveen's stack-slot allocator help?
>> 
> If you show me the original source code I could tell you.  Once things
> are in RTL form, it's difficult for me to trace them back into trees. 
> There's also the situation in which we have dead code at the RTL level
> that it's impossible to detect at the tree level (e.g. address
> arithmetic for array references).

gcc.dg/const-elim-1.c.  On an x86, compile it with -march=i386 -O2;
rs6000-ibm-aix5 and arm-elf also show the problem.

zw

Re: Dead-code elimination can't remove string copy insns?

[Diego Novillo]

On Tue, May 13, 2003 at 09:40:33AM -0700, Zack Weinberg wrote:

> gcc.dg/const-elim-1.c.  On an x86, compile it with -march=i386 -O2;
> rs6000-ibm-aix5 and arm-elf also show the problem.
> 
Yup, tree-ssa handles it.  The original program in GIMPLE form is
on the left.  The optimized version is on the right (we still
don't linearize GOTO_EXPRs).


Diego.

-----------------------------------------------------------------------------
;; Function test1 (test1)		;; Function test1 (test1)

test1 ()				test1 ()
{					{
  int retval.6;				  int retval.6;
  int T.1;				  int T.1;
  char[37] * T.2;			  char[37] * T.2;
  char * T.3;				  char * T.3;
  const char * T.4;			  const char * T.4;
  struct S <UVd90>;			  struct S <UVd90>;
  struct S * T.5;			  struct S * T.5;

  {					  {
    {				      |	    int <UV42a0>;
      int <UV42a0>;		      <

      {				      |	    goto <UL4230>;;
        {			      |	    <UL4230>:;
          <UV42a0> = 23;	      <
          goto <UL4230>;	      <
        }			      <
      };			      <
      <UL4230>:;;		      <
      retval.6 = <UV42a0>	      <
    };				      <
    T.1 = retval.6;		      <
    if (T.1 == 23)		      <
      {				      <
        {			      <
          return;		      <
        }			      <
      }				      <
  };					  };
  T.2 = "waltz, nymph, for quick jigs |	  return;;
  T.3 = (char *)T.2;		      |	  (void)0
  T.4 = (const char *)T.3;	      <
  use_str (T.4);		      <
  <UVd90> = {};			      <
  <UVd90>.a = 12;		      <
  <UVd90>.b = {};		      <
  <UVd90>.b[0] = 3.141500000000000181 <
  <UVd90>.b[1] = 2.182799999999999851 <
  <UVd90>.c = 0B;		      <
  T.5 = &<UVd90>;		      <
  use_S (T.5);			      <
  use_cplx (__complex__ (3.1415000000 <
}					}


;; Function test2 (test2)		;; Function test2 (test2)

test2 ()				test2 ()
{					{
  int retval.11;			  int retval.11;
  char[40] * T.7;			  char[40] * T.7;
  char * T.8;				  char * T.8;
  int T.9;				  int T.9;
  struct S * S.10;			  struct S * S.10;
  const char * str;			  const char * str;
  struct S S;				  struct S S;
  const complex double cplx;		  const complex double cplx;

  T.7 = "pack my box with five dozen  <
  T.8 = (char *)T.7;		      <
  str = (const char *)T.8;	      <
  S = {};			      <
  S.a = 23;			      <
  S.b = {};			      <
  S.b[0] = 1.413999999999999923616655 <
  S.b[1] = 1.618000000000000104805053 <
  S.c = 0B;			      <
  cplx = __complex__ (1.4139999999999 <
  {					  {
    {				      |	    int <UVf5b0>;
      int <UVf5b0>;		      <

      {				      |	    goto <ULf540>;;
        {			      |	    <ULf540>:;
          <UVf5b0> = 23;	      <
          goto <ULf540>;	      <
        }			      <
      };			      <
      <ULf540>:;;		      <
      retval.11 = <UVf5b0>	      <
    };				      <
    T.9 = retval.11;		      <
    if (T.9 == 23)		      <
      {				      <
        {			      <
          return;		      <
        }			      <
      }				      <
    else			      <
      {				      <
        (void)0			      <
      }				      <
  };					  };
  use_str (str);		      |	  return;;
  S.10 = &S;			      |	  (void)0
  use_S (S.10);			      <
  use_cplx (__complex__ (1.4139999999 <
}					}


;; Function returns_23 (returns_23)	;; Function returns_23 (returns_23)

returns_23 ()				returns_23 ()
{					{
  return 23;				  return 23;
}					}

Re: Dead-code elimination can't remove string copy insns?

[law]

In message <20030513170722.GA7112@tornado.toronto.redhat.com>, Diego Novillo wr
ites:
 >On Tue, May 13, 2003 at 09:40:33AM -0700, Zack Weinberg wrote:
 >
 >> gcc.dg/const-elim-1.c.  On an x86, compile it with -march=i386 -O2;
 >> rs6000-ibm-aix5 and arm-elf also show the problem.
 >> 
 >Yup, tree-ssa handles it.  The original program in GIMPLE form is
 >on the left.  The optimized version is on the right (we still
 >don't linearize GOTO_EXPRs).
Err, we do zap GOTO_EXPRs to the next statement.  See
remove_useless_stmts_and_vars.   It's restricted in that it can't deal
with removal of a GOTO_EXPR when the label is at a different control
nesting depth, but they're at the same nesting depth in your example.



jeff

Re: Dead-code elimination can't remove string copy insns?

[Diego Novillo]

On Tue, 2003-05-13 at 13:16, law@redhat.com wrote:

> Err, we do zap GOTO_EXPRs to the next statement.  See
> remove_useless_stmts_and_vars.   It's restricted in that it can't deal
> with removal of a GOTO_EXPR when the label is at a different control
> nesting depth, but they're at the same nesting depth in your example.
> 
Then I found a bug :)  We didn't remove that goto in this case.

Maybe we apply the goto removal before the BIND_EXPR removal?  In this
case, we initially have the goto and the label at different nesting
levels.


Diego.

Re: Dead-code elimination can't remove string copy insns?

[Zack Weinberg]

Diego Novillo <dnovillo@redhat.com> writes:

> On Tue, May 13, 2003 at 09:40:33AM -0700, Zack Weinberg wrote:
>
>> gcc.dg/const-elim-1.c.  On an x86, compile it with -march=i386 -O2;
>> rs6000-ibm-aix5 and arm-elf also show the problem.
>> 
> Yup, tree-ssa handles it.  The original program in GIMPLE form is
> on the left.  The optimized version is on the right (we still
> don't linearize GOTO_EXPRs).

Excellent.  In that case I will not worry about getting const-elim-1.c
to work for all targets on the mainline.  The present situation is not
a regression -- we just weren't testing for dead-constant removal
before.

Could those port maintainers seeing failures for const-elim-1.c please
apply patches to mark it XFAIL for their target?

zw

Re: Dead-code elimination can't remove string copy insns?

[law]

In message <20030513170722.GA7112@tornado.toronto.redhat.com>, Diego Novillo wr
ites:
 >On Tue, May 13, 2003 at 09:40:33AM -0700, Zack Weinberg wrote:
 >
 >> gcc.dg/const-elim-1.c.  On an x86, compile it with -march=i386 -O2;
 >> rs6000-ibm-aix5 and arm-elf also show the problem.
 >> 
 >Yup, tree-ssa handles it.  The original program in GIMPLE form is
 >on the left.  The optimized version is on the right (we still
 >don't linearize GOTO_EXPRs).
Does this look better? :-)

test1 ()
{       
  int retval.6;
  int T.1;
  char[37] * T.2;
  char * T.3;
  const char * T.4;
  struct S <UVda10>;
  struct S * T.5;
        
  { 
    int <UVdee0>;
        
    <ULde70>:;
  };  
  return;
}
    
    
;; Function test2 (test2)
    
test2 ()
{ 
  int retval.11;
  char[40] * T.7;
  char * T.8;
  int T.9;
  struct S * S.10;
  const char * str;
  struct S S;
  const complex double cplx;
  
  {
    int <UVc230>;
  
    <ULc1c0>:;
  };
  return;
} 
  

;; Function returns_23 (returns_23)

returns_23 ()
{ 
  return 23; 
} 


Note the GOTOs are gone :-)

The problem was the code didn't match the toplevel comments in regards
to when the pass should be repeated.  Basically we want to repeat if
we eliminated a control structure as that can in turn expose more
GOTOs that we know how to eliminate.

Testing of the fix is in progress.

jeff

Re: Dead-code elimination can't remove string copy insns?

[Diego Novillo]

On Tue, 2003-05-13 at 13:38, law@redhat.com wrote:

> Does this look better? :-)
> 
Much :)

Now, if we could also get rid of those pesky labels.  You mentioned
something about that, but I forget what.


Diego.

Re: Dead-code elimination can't remove string copy insns?

[law]

In message <1052848240.27232.407.camel@frodo.toronto.redhat.com>, Diego Novillo
 writes:
 >On Tue, 2003-05-13 at 13:38, law@redhat.com wrote:
 >
 >> Does this look better? :-)
 >> 
 >Much :)
 >
 >Now, if we could also get rid of those pesky labels.  You mentioned
 >something about that, but I forget what.
Well, it's simply a matter of building a use count for the labels.  As
we remove GOTO_EXPRs we decrement the count.  If the count goes to zero
and the label is not special (such as the target of a nonlocal goto), then
the label is unused and can be eliminated.

There's nothing particularly tricky here except that we want to build
those use counts efficiently.  Meaning we don't want a separate walk
over the tree structures merely to build the use counts.

It's on the TODO, but it hasn't bubbled up to the top yet.  Removal
of unused variables is a much bigger win as far as compilation time
is concerned.



Jeff

Re: Dead-code elimination can't remove string copy insns?

[Joe Buck]

On Tue, May 13, 2003 at 12:02:05PM -0600, law@redhat.com wrote:
> In message <1052848240.27232.407.camel@frodo.toronto.redhat.com>, Diego Novillo
>  writes:
>  >Now, if we could also get rid of those pesky labels.  You mentioned
>  >something about that, but I forget what.
> Well, it's simply a matter of building a use count for the labels.  As
> we remove GOTO_EXPRs we decrement the count.

I don't know anything about the code in question, but is it certain that
the cost of maintaining, incrementing, and decrementing reference counts
is less than the cost of doing a sweep at the end to clean up unused cruft?
Reference counting is not necessarily cheap.

Re: Dead-code elimination can't remove string copy insns?

[Richard Henderson]

On Tue, May 13, 2003 at 11:30:12AM +0200, Michael Matz wrote:
> Exactly.  We don't track dead stores to memory.

Well, we do, but it only works on tail blocks.  See
the end of init_propagate_block_info and insn_dead_p.


r~

Re: Dead-code elimination can't remove string copy insns?

[Michael Matz]

Hi,

On Tue, 13 May 2003, Richard Henderson wrote:

> On Tue, May 13, 2003 at 11:30:12AM +0200, Michael Matz wrote:
> > Exactly.  We don't track dead stores to memory.
>
> Well, we do, but it only works on tail blocks.

I know.  But this uses the mem expressions to represent the stored-into
memory, and hence doesn't work on BLKmode mems.  I guess one could special
case Zacks example by noting (for the tail blocks), that all stores to
stack mem are dead if there is _no_ read from stack afterwards.  But this
special casing quickly becomes silly.


Ciao,
Michael.