[Bug tree-optimization/18880] New: DSE is not doing its job for global variables

[Bug tree-optimization/18880] New: DSE is not doing its job for global variables

[pinskia at gcc dot gnu dot org]

Take the following:
char Bool_Glob;
void f(void)
{
  Bool_Glob = 0;
  Bool_Glob = 1;
}

There should be only one store to Bool_Glob in the last tree dump.

The corresponding pointer example works correctly:
int f(char *Bool_Glob )
{
  *Bool_Glob = 0;
  *Bool_Glob = 1;
}

-- 
           Summary: DSE is not doing its job for global variables
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: missed-optimization, TREE
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-08 02:27 -------
Looks like DSE is not following V_MUST_DEF chains (well since really V_MUST_DEF just became chains I 
would assume this was not like not before).

If we use "--param global-var-threshold=0", DSE removes the store.

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


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[steven at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at redhat dot com


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-08 17:02 -------
Subject: Re:  DSE is not doing its job for
	global variables

Note that we're only fixing regressions, and I can't see a way to
classify this as a regression since the RTL DSE code ought to
catch this.  This should be marked as postponed until 4.1.


This (untested) code ought to do the trick though:



------- Additional Comments From law at redhat dot com  2004-12-08 17:02 -------
Created an attachment (id=7706)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=7706&action=view)


-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-08 18:03 -------
Yes I know it is regression only time which is why I filed it and marked it as an enhancement but I 
should note that I found this while looking into a benchmark.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-12-08 18:03:40
               date|                            |


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-08 20:02 -------
Subject: Re:  DSE is not doing its job for
	global variables

On Wed, 2004-12-08 at 18:03 +0000, pinskia at gcc dot gnu dot org wrote:
> ------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-08 18:03 -------
> Yes I know it is regression only time which is why I filed it and marked it as an
> enhancement
OK.


>  but I should note that I found this while looking into a benchmark.
Were you looking at the final output, or just the output from the SSA
optimizers?  As I mentioned, we have a DSE that works on the RTL level
which ought to have a reasonable chance of catching this.

If you get a chance to play with the patch and benchmark it, that would
be great.

Jeff

ps.  What benchmark?






-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-08 20:09 -------
(In reply to comment #5)
> Subject: Re:  DSE is not doing its job for
>         global variables
> >  but I should note that I found this while looking into a benchmark.
> Were you looking at the final output, or just the output from the SSA
> optimizers?  As I mentioned, we have a DSE that works on the RTL level
> which ought to have a reasonable chance of catching this.

Yes the RTL level one catches it.  I just filed it because it would help out on
memory usage sometimes.
> If you get a chance to play with the patch and benchmark it, that would
> be great.

I will try after I after I benchmark my tree combine pass which looks like it could
improve even the compile time speed as it removes some ifs which can be proved
to be always true.
 
> ps.  What benchmark?

dhrystone 2.0 but it might be a modified version as it was designed to run on DOS
and I modified it back to run on UNIX.

-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-22 15:00 -------
*** Bug 19130 has been marked as a duplicate of this bug. ***

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |kazu at cs dot umass dot edu


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-12 16:56 -------
I'll have a look at Jeff's patch. 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |steven at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2004-12-08 18:03:40         |2005-01-12 16:56:17
               date|                            |


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-13 20:38 -------
Hmpf, does DSE do anything *at* *all*??? 
 
Test cases: 
--------------------------------------- 
int x; 
 
int 
f1 (int i, int j, int k) 
{ 
  int *p = k ? &i : &j; 
  i = 3; /* Dead store.  */ 
  *p = 5; 
  x = j; 
} 
 
int 
f2 (int l, int m, int n) 
{ 
  int *q = n ? &l : &m; 
  *q = 3; /* Dead store.  */ 
  *q = 5; 
  x = m; 
} 
--------------------------------------- 
 
 
.optimized dump at -O2: 
--------------------------------------- 
;; Function f1 (f1) 
 
Analyzing Edge Insertions. 
f1 (i, j, k) 
{ 
  int * p; 
  int j.1; 
  int * iftmp.0; 
 
<bb 0>: 
  if (k != 0) goto <L4>; else goto <L3>; 
 
<L4>:; 
  p = &i; 
  goto <bb 2> (<L2>); 
 
<L3>:; 
  p = &j; 
 
<L2>:; 
  i = 3; 
  *p = 5; 
  x = j; 
  return; 
 
} 
 
 
;; Function f2 (f2) 
 
Analyzing Edge Insertions. 
f2 (l, m, n) 
{ 
  int * q; 
  int m.3; 
  int * iftmp.2; 
 
<bb 0>: 
  if (n != 0) goto <L4>; else goto <L3>; 
 
<L4>:; 
  q = &l; 
  goto <bb 2> (<L2>); 
 
<L3>:; 
  q = &m; 
 
<L2>:; 
  *q = 3; 
  *q = 5; 
  x = m; 
  return; 
 
} 
--------------------------------------- 
 
 
 

-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-01-17 18:33 -------
Subject: Re:  DSE is not doing its job for
	global variables

On Thu, 2005-01-13 at 20:38 +0000, steven at gcc dot gnu dot org wrote:
> ------- Additional Comments From steven at gcc dot gnu dot org  2005-01-13 20:38 -------
> Hmpf, does DSE do anything *at* *all*???
Yes.


 foo( int *a)
{
  *a  =5;
  *a = 3;
}


>From the .dse1 dump:


 ;; Function foo (foo)

  Deleted dead store '*a_1 = 5'
foo (a)
{
  # BLOCK 0
  # PRED: ENTRY [100.0%]  (fallthru)
  *a_1 = 3;
  return;
  # SUCC: EXIT [100.0%]

}

Your tests fail because of the mixture of V_MUST_DEF and V_MAY_DEFs
as well as the aliasing for the references through i and *p in the
first test and the aliasing between l & m in the second test.

I wouldn't expect my change to handle V_MUST_DEF to fix the first
test.


Feel free to improve :-)

Jeff



-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-19 01:34 -------
DSE2 also does almost nothing, so I just went ahead and posted a proposal 
to just disable DSE: http://gcc.gnu.org/ml/gcc-patches/2005-01/msg01183.html 

-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-01-19 01:43 -------
Subject: Re:  DSE is not doing its job for
	global variables

On Wed, 2005-01-19 at 01:34 +0000, steven at gcc dot gnu dot org wrote:
> ------- Additional Comments From steven at gcc dot gnu dot org  2005-01-19 01:34 -------
> DSE2 also does almost nothing, so I just went ahead and posted a proposal 
> to just disable DSE: http://gcc.gnu.org/ml/gcc-patches/2005-01/msg01183.html 
DSE is reasonably fast.  How about we just disable one pass rather than
disabling it completely.

jeff




-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[dje at gcc dot gnu dot org]

------- Additional Comments From dje at gcc dot gnu dot org  2005-01-19 02:44 -------
Steven's experiments seem to demonstrate that the current DSE implementation is
not very effective.  GCC 4.0 includes RTL optimizations that will catch most if
not all of these cases, so it is not as if this will cause GCC to miss some
optimizations.  If the concern is performance impact, then I think that we
should consider adding adding some aggressive optimizations instead of retaining
DSE.  Even if DSE is very fast, what does GCC gain by fewer iterations of an
optimization pass that has almost no benefit?


-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-01-19 06:46 -------
Subject: Re:  DSE is not doing its job for
	global variables

On Wed, 2005-01-19 at 02:44 +0000, dje at gcc dot gnu dot org wrote:
> ------- Additional Comments From dje at gcc dot gnu dot org  2005-01-19 02:44 -------
> Steven's experiments seem to demonstrate that the current DSE implementation is
> not very effective.  GCC 4.0 includes RTL optimizations that will catch most if
> not all of these cases, so it is not as if this will cause GCC to miss some
> optimizations.  
Err, umm, wrong.  I checked when I wrote the original code and I just
double checked tonight.  The tree DSE implementation as is stands right
now, today, without any improvements, will catch things which the RTL
optimizers will miss.  And there are some pretty simple things that can
be done to make it more effective, though to be really effective we need
better alias analysis.  The stuff we have now sucks badly.

Jeff



-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[stevenb at novell dot com]

------- Additional Comments From stevenb at novell dot com  2005-01-19 09:12 -------
Subject: Re:  DSE is not doing its job for global variables


Do you happen to have numbers on how many dead stores the RTL dead
store elimination (in flow.c, right) catches?



-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-01-19 16:22 -------
Subject: Re:  DSE is not doing its job for
	global variables

On Wed, 2005-01-19 at 09:12 +0000, stevenb at novell dot com wrote:
> ------- Additional Comments From stevenb at novell dot com  2005-01-19 09:12 -------
> Subject: Re:  DSE is not doing its job for global variables
> 
> 
> Do you happen to have numbers on how many dead stores the RTL dead
> store elimination (in flow.c, right) catches?
Unfortunately, no.  I doubt I've run those numbers since the original
RTL DSE code was installed several years ago.

jeff




-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-01 00:23 -------
Let's just leave it as-is and revisit for 4.1. 

-- 
           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=18880

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2005-04-13 23:49 -------
Steven, what about posting your patch for review?

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |stevenb at suse dot de


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-04-13 23:50 -------
I am no longer interested in working on this DSE pass. 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|stevenb at suse dot de      |


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-04-17 23:52 -------
*** Bug 13799 has been marked as a duplicate of this bug. ***

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dann at godzilla dot ics dot
                   |                            |uci dot edu


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-04-17 23:55 -------
*** Bug 13796 has been marked as a duplicate of this bug. ***

-- 


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-04-26 22:21 -------
Fixed.

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


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

[Bug tree-optimization/18880] DSE is not doing its job for global variables

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.1.0


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