[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[steven at gcc dot gnu dot org]

------- Comment #2 from steven at gcc dot gnu dot org  2005-11-13 01:43 -------
This hasn't been addressed yet in r106784.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2005-09-21 01:43:19         |2005-11-13 01:43:25
               date|                            |


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[rakdver at gcc dot gnu dot org]

------- Comment #3 from rakdver at gcc dot gnu dot org  2005-11-13 10:02 -------
This is easy to implement; the question is whether we really want to waste
compile time to handle this type of examples that do not seem very likely to
appear in practice.


-- 


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2005-11-13 11:47 -------
They can happen due to macro expansion or C++ template inlining.  I wonder if
PRE for scalar-evolutions would be useful ;)


-- 


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #5 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2005-11-14 09:27 -------
Subject: Re:  IVs with the same evolution not eliminated

> They can happen due to macro expansion or C++ template inlining.

And do they?

> I wonder if PRE for scalar-evolutions would be useful ;)

I would guess that this would be unnecessarily expensive.  The only
place where scev should give you some useful information should be for
induction variables inside loops, in which case you can simply pass over
the loop phi nodes and merge the variables with the same evolution.


-- 


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2005-11-14 09:45 -------
> > They can happen due to macro expansion or C++ template inlining.

> And do they?

If they can, they will do.  Will this regularly happen?  I think no.


-- 


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[steven at gcc dot gnu dot org]

------- Comment #7 from steven at gcc dot gnu dot org  2005-11-14 10:32 -------
It would be more interesting to measure than think ;-)

My experience is that when it is in Briggs' test suite, it usually also happens
in actually useful code. But, only the numbers will tell :-)

Zdenek is right, it's just a matter of comparing the evolutions of loop PHI
nodes.  Instrumenting the compiler to count how often this happens is half the
work of implementing the optimization if it turns out to be useful. 


-- 


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[pinskia at gcc dot gnu dot org]

------- Comment #8 from pinskia at gcc dot gnu dot org  2006-04-08 02:26 -------
Comparing the IVs themselves take no time, now figuring out which one are equal
to which set could take some time, at max O(n^2) time.  Now n is going to be
small for most cases anyways.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2006-02-13 04:03:32         |2006-04-08 02:26:25
               date|                            |


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[dberlin at gcc dot gnu dot org]

------- Comment #9 from dberlin at gcc dot gnu dot org  2006-04-08 02:53 -------
Actually, it's not really expensive at all.
It's certainly not N^2.
The new SCC value numberer for PRE i'm working on gets this case right (and
this is in fact, one of the advantages of SCC based value numbering).

You could also do it with an RPO iteration algorithm, which is what open64
does, but that will iterate over defs/uses in changing blocks repeatedly
instead of only iterating over the members of the SCC.

For this case, i get:
Value numbers:
n_3 = m_2
n_9 = m_8
n_21 = m_20

Which is what you wanted.


-- 


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[stevenb dot gcc at gmail dot com]

------- Comment #10 from stevenb dot gcc at gmail dot com  2006-04-08 21:13 -------
Subject: Re:  IVs with the same evolution not eliminated

> The new SCC value numberer for PRE i'm working on gets this case right (and
> this is in fact, one of the advantages of SCC based value numbering).

Is the SCC-VN patch I posted long ago still of some use to you, or are
you writing something new from scratch?
(See http://gcc.gnu.org/ml/gcc-patches/2004-01/msg00211.html)


-- 


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

Re: [Bug tree-optimization/19590] IVs with the same evolution not eliminated

[Daniel Berlin]

> ------- Comment #10 from stevenb dot gcc at gmail dot com  2006-04-08 21:13 -------
> Subject: Re:  IVs with the same evolution not eliminated
> 
> > The new SCC value numberer for PRE i'm working on gets this case right (and
> > this is in fact, one of the advantages of SCC based value numbering).
> 
> Is the SCC-VN patch I posted long ago still of some use to you, or are
> you writing something new from scratch?
I ended up rewriting it from scratch, for other reasons.

In particular
1. I keep separate hash tables for unary, binary, references, and phi
expressions, each with their own structure
This is because you really want valuized structures in the hash table.
Your implementation will get the wrong answers during optimistic lookup
at times, because the value representative for a phi argument can change
and will get hashed to the wrong value.
2. I keep track of what expressions simplified to, and whether they have
constants in the simplified expression.   This enables much more
simplification that simply storing the value number name.

In particular, in something like
int main(int argc)
{
  int a;
  int b;
  int c;
  int d;
  a = argc + 4;
  b = argc + 8;
  c = a & b;
  d = a + 4;
  return c + d;
}

We will prove that d and b have the same value.

BTW, you missed the part of the thesis where he explains that phi nodes
in different blocks can't be congruent to each other (this isn't quite
true, but it's a much harder property to prove).

3. I needed the structures i made so i could directly transform the
results into value handles.

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[dberlin at dberlin dot org]

------- Comment #11 from dberlin at gcc dot gnu dot org  2006-04-08 23:20 -------
Subject: Re:  IVs with the same evolution not
        eliminated

> ------- Comment #10 from stevenb dot gcc at gmail dot com  2006-04-08 21:13 -------
> Subject: Re:  IVs with the same evolution not eliminated
> 
> > The new SCC value numberer for PRE i'm working on gets this case right (and
> > this is in fact, one of the advantages of SCC based value numbering).
> 
> Is the SCC-VN patch I posted long ago still of some use to you, or are
> you writing something new from scratch?
I ended up rewriting it from scratch, for other reasons.

In particular
1. I keep separate hash tables for unary, binary, references, and phi
expressions, each with their own structure
This is because you really want valuized structures in the hash table.
Your implementation will get the wrong answers during optimistic lookup
at times, because the value representative for a phi argument can change
and will get hashed to the wrong value.
2. I keep track of what expressions simplified to, and whether they have
constants in the simplified expression.   This enables much more
simplification that simply storing the value number name.

In particular, in something like
int main(int argc)
{
  int a;
  int b;
  int c;
  int d;
  a = argc + 4;
  b = argc + 8;
  c = a & b;
  d = a + 4;
  return c + d;
}

We will prove that d and b have the same value.

BTW, you missed the part of the thesis where he explains that phi nodes
in different blocks can't be congruent to each other (this isn't quite
true, but it's a much harder property to prove).

3. I needed the structures i made so i could directly transform the
results into value handles.


-- 


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[sebastian dot pop at cri dot ensmp dot fr]

------- Comment #12 from sebastian dot pop at cri dot ensmp dot fr  2006-04-10 09:14 -------
Created an attachment (id=11235)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=11235&action=view)
proposed fix

This patch fixes the problem, but probably it is a more general optimization
fix than the one described in the PR.


-- 


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[rguenth at gcc dot gnu dot org]

------- Comment #13 from rguenth at gcc dot gnu dot org  2006-04-10 15:31 -------
I wonder if it helps placing this between cunroll and ivopts...

void foo(int n, int m, int stridex, int stridey, int stridex2, int stridey2,
double *x, double *y)
{
 for (int k=0; k<m; ++k)
  for (int j=0; j<n; ++j)
    for (int i=0; i<2; ++i)
      x[i + stridex*j + stridex2*k] = y[i + stridey*j + stridey2*k];
}

producing better IV selection than what we get now.


-- 


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #14 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-04-10 15:53 -------
Subject: Re:  IVs with the same evolution not eliminated

> I wonder if it helps placing this between cunroll and ivopts...
> 
> void foo(int n, int m, int stridex, int stridey, int stridex2, int stridey2,
> double *x, double *y)
> {
>  for (int k=0; k<m; ++k)
>   for (int j=0; j<n; ++j)
>     for (int i=0; i<2; ++i)
>       x[i + stridex*j + stridex2*k] = y[i + stridey*j + stridey2*k];
> }
> 
> producing better IV selection than what we get now.

ivopts do not care (they will recognize that the two array references
have the same offsets).


-- 


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[pinskia at gcc dot gnu dot org]

------- Comment #15 from pinskia at gcc dot gnu dot org  2006-12-09 06:30 -------
*** Bug 30098 has been marked as a duplicate of this bug. ***


-- 

pinskia at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[spop at gcc dot gnu dot org]

------- Comment #16 from spop at gcc dot gnu dot org  2007-06-21 17:06 -------
Subject: Bug 19590

Author: spop
Date: Thu Jun 21 17:06:05 2007
New Revision: 125925

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=125925
Log:
        PR tree-optimization/19590
        * tree-vrp.c (adjust_range_with_scev): Set the range when the result
        of scev is a constant.
        * gcc/testsuite/gcc.dg/tree-ssa/pr19590.c: New.


Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr19590.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-vrp.c


-- 


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[pinskia at gcc dot gnu dot org]

------- Comment #17 from pinskia at gcc dot gnu dot org  2007-06-24 03:53 -------
Fixed.
Note I think the proposed patch attached here will fix PR 32200.  That testcase
was not fixed the VRP patch.  The VRP patch fixes the case where we have IV -
IV inside the loop.


-- 

pinskia at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/19590] IVs with the same evolution not eliminated

[spop at gcc dot gnu dot org]

------- Comment #18 from spop at gcc dot gnu dot org  2007-06-24 21:30 -------
Subject: Re:  IVs with the same evolution not eliminated

> Note I think the proposed patch attached here will fix PR 32200.

Nop.

Reverting the patch and diffing the assembly code for i686-linux on
both codes from PR32200 does not show any change.  I'm going to look
more closely at PR32200.

Sebastian


-- 


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