Strange IV choices?

Strange IV choices?

[Richard Guenther]

Hi!

It seems that ivopts is confused by local copies of objects.
Suppose you have some complex array managing class, the two
functionally identical functions

void arrayAssignManual(const Array<2, double, BrickViewU>& a,
                       const Array<2, double, BrickViewU>& b,
                       const Array<2, double, BrickViewU>& c,
                       const Array<2, double, BrickViewU>& d,
                       const Interval<2> &I)
{
        int ie = I[0].length();
        int je = I[1].length();
        for (int j=0; j<je; ++j)
          for (int i=0; i<ie; ++i)
            a(i,j) = b(i,j)+c(i,j)+d(i,j);
}

and

void arrayAssignManualCopy(const Array<2, double, BrickViewU>& a_,
                       const Array<2, double, BrickViewU>& b_,
                       const Array<2, double, BrickViewU>& c_,
                       const Array<2, double, BrickViewU>& d_,
                       const Interval<2> &I)
{
        Array<2, double, BrickViewU> a(a_), b(b_), c(c_), d(d_);
        int ie = I[0].length();
        int je = I[1].length();
        for (int j=0; j<je; ++j)
          for (int i=0; i<ie; ++i)
            a(i,j) = b(i,j)+c(i,j)+d(i,j);
}

get optimized vastly different.  While the first one gets an
inner loop with

.L71:
        fldl    (%ebx)  #* ivtmp.627
        faddl   (%esi)  #* ivtmp.623
        faddl   (%ecx)  #* ivtmp.629
        fstpl   (%eax)  #* ivtmp.631
        addl    $1, %edx        #, i
        addl    $8, %esi        #, ivtmp.623
        addl    $8, %ebx        #, ivtmp.627
        addl    $8, %ecx        #, ivtmp.629
        addl    $8, %eax        #, ivtmp.631
        cmpl    %edx, -20(%ebp) # i, D.162565
        jg      .L71    #,

i.e. nice - the second one gets optimized to

.L320:
        leal    (%ebx,%edi), %eax       #,
        movl    %eax, -364(%ebp)        #,
        movl    -408(%ebp), %ecx        #,
        leal    (%ebx,%ecx), %edx       #, tmp136
        movl    -404(%ebp), %ecx        #,
        leal    (%ebx,%ecx), %eax       #, tmp140
        movl    -388(%ebp), %ecx        #,
        fldl    (%ecx,%eax,8)   #
        movl    -380(%ebp), %eax        #,
        faddl   (%eax,%edx,8)   #
        movl    -400(%ebp), %edx        #,
        leal    (%ebx,%edx), %eax       #, tmp147
        movl    -396(%ebp), %ecx        #,
        faddl   (%ecx,%eax,8)   #
        movl    -364(%ebp), %eax        #,
        movl    -372(%ebp), %edx        #,
        fstpl   (%edx,%eax,8)   #
        movl    %esi, %ebx      # ivtmp.889, i
        leal    1(%esi), %esi   #, ivtmp.889
        cmpl    %ebx, -360(%ebp)        # i, D.167717
        jg      .L320   #,

using recent 4.0 with -O2 -funroll-loops -ffast-math --param
max-unroll-times=1

The difference seems to be that in the ivopts dump file for
the second case with the object copies, the scalar evolution is
not know for whatever reason.

Note that the 3.4 loop optimizer does not have problems with local copies
like this.

Any hints on where to look at the actual reason of the failing scev?
(No, trying to produce a simple C testcase did not work)

I placed the ivopts dump file at
http://www.tat.physik.uni-tuebingen.de/~rguenth/gcc/perf.cpp.t54.ivopts

Thanks for any hints!

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: Strange IV choices?

[Steven Bosscher]

On Dec 14, 2004 03:56 PM, Richard Guenther wrote:
> Thanks for any hints!

Did you try with this patch applied:
http://gcc.gnu.org/ml/gcc-patches/2004-12/msg00950.html

Gr.
Steven

Re: Strange IV choices?

[Richard Guenther]

On Tue, 14 Dec 2004, Steven Bosscher wrote:

> On Dec 14, 2004 03:56 PM, Richard Guenther wrote:
> > Thanks for any hints!
>
> Did you try with this patch applied:
> http://gcc.gnu.org/ml/gcc-patches/2004-12/msg00950.html

No, but does this help the scev analyzer with currently
unknown evolution?  It looks like it changes only iv choice.

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: Strange IV choices?

[Steven Bosscher]

On Dec 14, 2004 04:02 PM, Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> wrote:
> No, but does this help the scev analyzer with currently
> unknown evolution?

No.  I misread your mail as just another "IVOPTS sucks" mail,
sorry about that.

Gr.
Steven

[scev] Re: Strange IV choices?

[Richard Guenther]

On Tue, 14 Dec 2004, Steven Bosscher wrote:

> On Dec 14, 2004 04:02 PM, Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> wrote:
> > No, but does this help the scev analyzer with currently
> > unknown evolution?

It seems to depend on the level of "indirection" in the C++ class
hierarchy, if I short-cut one level, it works again.  Are there
any complexity limits in the scev analyzer?  How would they depend
on the amount of "local" variables?

I'm slightly confused.  Maybe someone can have a look at the ivopts dump.

> No.  I misread your mail as just another "IVOPTS sucks" mail,
> sorry about that.

No problem.

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: [scev] Re: Strange IV choices?

[Richard Guenther]

On Tue, 14 Dec 2004, Richard Guenther wrote:

> On Tue, 14 Dec 2004, Steven Bosscher wrote:
>
> > On Dec 14, 2004 04:02 PM, Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> wrote:
> > > No, but does this help the scev analyzer with currently
> > > unknown evolution?
>
> It seems to depend on the level of "indirection" in the C++ class
> hierarchy, if I short-cut one level, it works again.  Are there
> any complexity limits in the scev analyzer?  How would they depend
> on the amount of "local" variables?
>
> I'm slightly confused.  Maybe someone can have a look at the ivopts dump.

"Testcase" (sorry, big) at

http://www.tat.physik.uni-tuebingen.de/~rguenth/gcc/perf.iu.ii.gz

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: Strange IV choices?

[Sebastian Pop]

On Tue, Dec 14, 2004 at 03:56:32PM +0100, Richard Guenther wrote:
> Hi!
> 
> It seems that ivopts is confused by local copies of objects.
> Suppose you have some complex array managing class, the two
> functionally identical functions
> 
> void arrayAssignManual(const Array<2, double, BrickViewU>& a,
>                        const Array<2, double, BrickViewU>& b,
>                        const Array<2, double, BrickViewU>& c,
>                        const Array<2, double, BrickViewU>& d,
>                        const Interval<2> &I)
> {
>         int ie = I[0].length();
>         int je = I[1].length();
>         for (int j=0; j<je; ++j)
>           for (int i=0; i<ie; ++i)
>             a(i,j) = b(i,j)+c(i,j)+d(i,j);
> }
> 
> and
> 
> void arrayAssignManualCopy(const Array<2, double, BrickViewU>& a_,
>                        const Array<2, double, BrickViewU>& b_,
>                        const Array<2, double, BrickViewU>& c_,
>                        const Array<2, double, BrickViewU>& d_,
>                        const Interval<2> &I)
> {
>         Array<2, double, BrickViewU> a(a_), b(b_), c(c_), d(d_);
>         int ie = I[0].length();
>         int je = I[1].length();
>         for (int j=0; j<je; ++j)
>           for (int i=0; i<ie; ++i)
>             a(i,j) = b(i,j)+c(i,j)+d(i,j);
> }
> 
> get optimized vastly different.  While the first one gets an
> inner loop with
> 


In the second case the analyzer produces a scev_not_known element:

(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = ostride_192)
(get_scalar_evolution 
  (scalar = ostride_192)
  (scalar_evolution = ))
(analyze_initial_condition 
  (loop_phi_node = 
ostride_192 = PHI <ostride_362(11), ostride_125(16)>;)
  (init_cond = ostride_125))
(analyze_evolution_in_loop 
  (loop_phi_node = ostride_192 = PHI <ostride_362(11), ostride_125(16)>;)
  (evolution_function = scev_not_known))
(set_scalar_evolution 
  (scalar = ostride_192)
  (scalar_evolution = ostride_192))
)

This situation is generated by the following code:

# ostrideD.165952_5 = PHI <1(0)>;
D.166161_150 = (*dD.166162_151)[1];
ostrideD.165952_125 = ostrideD.165952_5 * D.166161_150;
loop
  # ostrideD.165952_192 = PHI <ostrideD.165952_362(11), ostrideD.165952_125(16)>;
  D.166161_358 = (*dD.166162_356)[1];
  ostrideD.165952_362 = ostrideD.165952_192 * D.166161_358;
endloop

the above code is the same as: 

a = loop-phi (someconstant, a * T[1])

that is an exponential evolution with an undetermined step: T[1], and
these are not handled.

Re: Strange IV choices?

[Richard Guenther]

On Wed, 15 Dec 2004, Sebastian Pop wrote:

> On Tue, Dec 14, 2004 at 03:56:32PM +0100, Richard Guenther wrote:
> > Hi!
> >
> > It seems that ivopts is confused by local copies of objects.
> > Suppose you have some complex array managing class, the two
> > functionally identical functions
> >
> > void arrayAssignManual(const Array<2, double, BrickViewU>& a,
> >                        const Array<2, double, BrickViewU>& b,
> >                        const Array<2, double, BrickViewU>& c,
> >                        const Array<2, double, BrickViewU>& d,
> >                        const Interval<2> &I)
> > {
> >         int ie = I[0].length();
> >         int je = I[1].length();
> >         for (int j=0; j<je; ++j)
> >           for (int i=0; i<ie; ++i)
> >             a(i,j) = b(i,j)+c(i,j)+d(i,j);
> > }
> >
> > and
> >
> > void arrayAssignManualCopy(const Array<2, double, BrickViewU>& a_,
> >                        const Array<2, double, BrickViewU>& b_,
> >                        const Array<2, double, BrickViewU>& c_,
> >                        const Array<2, double, BrickViewU>& d_,
> >                        const Interval<2> &I)
> > {
> >         Array<2, double, BrickViewU> a(a_), b(b_), c(c_), d(d_);
> >         int ie = I[0].length();
> >         int je = I[1].length();
> >         for (int j=0; j<je; ++j)
> >           for (int i=0; i<ie; ++i)
> >             a(i,j) = b(i,j)+c(i,j)+d(i,j);
> > }
> >
> > get optimized vastly different.  While the first one gets an
> > inner loop with
> >
>
>
> In the second case the analyzer produces a scev_not_known element:
>
> (analyze_scalar_evolution
>   (loop_nb = 1)
>   (scalar = ostride_192)
> (get_scalar_evolution
>   (scalar = ostride_192)
>   (scalar_evolution = ))
> (analyze_initial_condition
>   (loop_phi_node =
> ostride_192 = PHI <ostride_362(11), ostride_125(16)>;)
>   (init_cond = ostride_125))
> (analyze_evolution_in_loop
>   (loop_phi_node = ostride_192 = PHI <ostride_362(11), ostride_125(16)>;)
>   (evolution_function = scev_not_known))
> (set_scalar_evolution
>   (scalar = ostride_192)
>   (scalar_evolution = ostride_192))
> )
>
> This situation is generated by the following code:
>
> # ostrideD.165952_5 = PHI <1(0)>;
> D.166161_150 = (*dD.166162_151)[1];
> ostrideD.165952_125 = ostrideD.165952_5 * D.166161_150;
> loop
>   # ostrideD.165952_192 = PHI <ostrideD.165952_362(11), ostrideD.165952_125(16)>;
>   D.166161_358 = (*dD.166162_356)[1];
>   ostrideD.165952_362 = ostrideD.165952_192 * D.166161_358;
> endloop
>
> the above code is the same as:
>
> a = loop-phi (someconstant, a * T[1])
>
> that is an exponential evolution with an undetermined step: T[1], and
> these are not handled.

As this is completely equivalent code apart from using a local on
stack copy of the Array structure, do you agree that some earlier
optimization pass must be messing something up here?  Disabling
DOM leads to similar code for both cases, but ivopts doesn't seem
to do anything in this case.  Also, all element access with
operator()(int i, int j) are of the form data[i+j*stride], so
they are definitely not exponential.

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: Strange IV choices?

[Giovanni Bajo]

Sebastian Pop <sebastian.pop@cri.ensmp.fr> wrote:

> In the second case the analyzer produces a scev_not_known element:
>
> (analyze_scalar_evolution
>   (loop_nb = 1)
>   (scalar = ostride_192)
> (get_scalar_evolution
>   (scalar = ostride_192)
>   (scalar_evolution = ))
> (analyze_initial_condition
>   (loop_phi_node =
> ostride_192 = PHI <ostride_362(11), ostride_125(16)>;)
>   (init_cond = ostride_125))
> (analyze_evolution_in_loop
>   (loop_phi_node = ostride_192 = PHI <ostride_362(11), ostride_125(16)>;)
>   (evolution_function = scev_not_known))
> (set_scalar_evolution
>   (scalar = ostride_192)
>   (scalar_evolution = ostride_192))
> )
>
> This situation is generated by the following code:
>
> # ostrideD.165952_5 = PHI <1(0)>;
> D.166161_150 = (*dD.166162_151)[1];
> ostrideD.165952_125 = ostrideD.165952_5 * D.166161_150;
> loop
>   # ostrideD.165952_192 = PHI <ostrideD.165952_362(11),
>   ostrideD.165952_125(16)>; D.166161_358 = (*dD.166162_356)[1];
>   ostrideD.165952_362 = ostrideD.165952_192 * D.166161_358;
> endloop

Then, why does it recognize the evolution of the first testcase? They should
be identical.
-- 
Giovanni Bajo