[Bug tree-optimization/20256] New: -ftree-loop-linear doesn't work right in small loop

[Bug tree-optimization/20256] New: -ftree-loop-linear doesn't work right in small loop

[fjahanian at apple dot com]

This is a small extract from a benchmark. It shows that -O1 -ftree-loop-linear generates a couple
of empty loops, and incorrect behavior. 

/* main.c */
#include <stdio.h>

extern void init();

double mid_wts[8][35];
double  in_pats[1][35];

double  do_mid_forward(int patt)
{
double  sum;
int     neurode, i;

for (neurode=0;neurode<8; neurode++)
{
        sum = 0.0;
        for (i=0; i<35; i++)
        { 
                sum += mid_wts[neurode][i]*in_pats[patt][i];
        }
        sum = 1.0/(1.0+sum);
}
return sum;
}


double value;

main()
{
  init();
  printf(" %e\n", do_mid_forward (0));
}

/* init.c */
extern double mid_wts[8][35];
extern double  in_pats[1][35];

double value;

void init()
{
int i;
int neurode;

value=(double)1.0 - (double) 0.5;

for (neurode = 0; neurode<8; neurode++)
   for (i=0; i<35; i++)
      mid_wts[neurode][i] = value;

for (i=0; i<35; i++)
   in_pats[0][i] = 1.234;
}

% cc -c -O0 init.c
% cc -O1 -ftree-loop-linear main.c init.o
% ./a.out
 -2.384238e+11

Assembly file for ppc-darwin shows a couple of do-nothing empty loops. 
Remove -ftree-loop-linear and program behaves correctly.

-- 
           Summary: -ftree-loop-linear  doesn't work right in small loop
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: fjahanian at apple dot com
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: powerpc-apple-darwin
  GCC host triplet: powerpc-apple-darwin
GCC target triplet: powerpc-apple-darwin


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

[Bug tree-optimization/20256] -ftree-loop-linear doesn't work right in small loop

[fjahanian at apple dot com]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dalej at apple dot com


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

[Bug tree-optimization/20256] -ftree-loop-linear doesn't work right in small loop

[fjahanian at apple dot com]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dberlin at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/20256] -ftree-loop-linear doesn't work right in small loop

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
           Keywords|                            |wrong-code


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

[Bug tree-optimization/20256] -ftree-loop-linear doesn't work right in small loop

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-01 01:54 -------
Confirmed, here is the reduced self testing testcase:
void abort (void);
int mid_wts[2][2]={};
int in_pats[2]={};
int do_mid_forward()
{
  int sum;
  int     neurode, i;
  for (neurode=0;neurode<2; neurode++)
  {
    sum = 0;
    for (i=0; i<2; i++)
      sum += mid_wts[neurode][i]*in_pats[i];
    sum += 1;
  }
  return sum;
}
int main()
{
  if (do_mid_forward(0) != 1)
    abort ();
  return 0;
}


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-03-01 01:54:32
               date|                            |


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[dberlin at gcc dot gnu dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-03-01 03:01 -------
This is a problem in testing legality of the perfect nest transform.
We think we can transform the loop into a perfect nest, but can't really (at
least with the code we have now), and do it wrong.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|-ftree-loop-linear  doesn't |Perfect nest transformation
                   |work right in small loop    |not conservative enough


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-01 03:43 -------
Assigning to Daniel as he requestioned it :).

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |dberlin at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[pinskia at gcc dot gnu dot org]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 894 bytes --]


------- Additional Comments From pinskia at gcc dot gnu dot org  2005-05-27 01:17 -------
We now get an ICE:
t.c: In function ‘do_mid_forward’:
t.c:5: error: Definition in block 9 does not dominate use in block 3
for SSA_NAME: sum_11 in statement:
sum_23 = PHI <sum_11(3)>;
PHI argument
sum_11
for PHI node
sum_23 = PHI <sum_11(3)>;
t.c:5: internal compiler error: verify_ssa failed.
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://gcc.gnu.org/bugs.html> for instructions.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |ice-on-valid-code
   Last reconfirmed|2005-03-01 01:54:32         |2005-05-27 01:17:34
               date|                            |


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-06-10 21:18 -------
On the mainline we get a different ICE:
t.c: In function 'do_mid_forward':
t.c:5: internal compiler error: tree check: expected integer_cst, have scev_not_known in int_cst_value, at 
tree.c:6342
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://gcc.gnu.org/bugs.html> for instructions.

Comes from:
2186            step = evolution_part_in_loop_num (access_fn, loop->num);
2187          if ((step && int_cst_value (step) == xstep)
2188              || USE_FROM_PTR (use_p) == x)

-- 


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-06-10 21:41 -------
(In reply to comment #5)
> On the mainline we get a different ICE:

After:
2005-06-10  Daniel Berlin  <dberlin@dberlin.org>

        * lambda-code.c (replace_uses_equiv_to_x_with_y): Check step
        and access function against chrec_dont_know.

We are back to the ICE in comment #4.

-- 


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[bangerth at dealii dot org]

------- Additional Comments From bangerth at dealii dot org  2005-06-28 23:17 -------
Andrew's code in comment #4 is invalid (don't call no-arg functions with 
arguments!), but here's a version that also passes through the c++ 
frontend and crashes the optimizers: 
 
---------------------- 
int foo() { 
  int x[2][2], y[2]; 
  int s; 
  for (int n=0; n<2; n++) 
    { 
      s = 0; 
      for (int i=0; i<2; i++) 
        s += x[n][i]*y[i]; 
      s += 1; 
    } 
  return s; 
} 
-------------------- 
 
g/x> /home/bangerth/bin/gcc-4.1-pre/bin/gcc -c x.cc -O2 -ftree-loop-linear 
x.cc: In function &#8216;int foo()&#8217;: 
x.cc:1: error: Definition in block 9 does not dominate use in block 3 
for SSA_NAME: s_11 in statement: 
s_7 = PHI <s_11(3)>; 
PHI argument 
s_11 
for PHI node 
s_7 = PHI <s_11(3)>; 
x.cc:1: internal compiler error: verify_ssa failed. 
Please submit a full bug report, 
with preprocessed source if appropriate. 
See <URL:http://gcc.gnu.org/bugs.html> for instructions. 
 
W. 

-- 


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-06-28 23:20 -------
(In reply to comment #7)
> Andrew's code in comment #4 is invalid (don't call no-arg functions with 
> arguments!), but here's a version that also passes through the c++ 
> frontend and crashes the optimizers: 
Actually it is valid C.  because "void f()" in C means the same as "void f(...)".
My testcase was to show the wrong code at the time.

-- 


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-06-29 00:11 -------
Subject: Re:  Perfect nest transformation not
	conservative enough

On Tue, 2005-06-28 at 23:17 +0000, bangerth at dealii dot org wrote:
> ------- Additional Comments From bangerth at dealii dot org  2005-06-28 23:17 -------
> Andrew's code in comment #4 is invalid (don't call no-arg functions with 
> arguments!), but here's a version that also passes through the c++ 
> frontend and crashes the optimizers: 
>  
> ---------------------- 
> int foo() { 
>   int x[2][2], y[2]; 
>   int s; 
>   for (int n=0; n<2; n++) 
>     { 
>       s = 0; 
>       for (int i=0; i<2; i++) 
>         s += x[n][i]*y[i]; 
>       s += 1; 
>     } 
>   return s; 
> } 
> -------------------- 
>  
yeah, we shouldn't be trying to transform this :)
at least, not with the current scheme



-- 


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.2.0                       |4.1.2


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[spop at gcc dot gnu dot org]

------- Comment #13 from spop at gcc dot gnu dot org  2006-08-17 13:14 -------
Subject: Bug 20256

Author: spop
Date: Thu Aug 17 13:14:26 2006
New Revision: 116223

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=116223
Log:
        PR middle-end/25211
        PR middle-end/20256
        PR middle-end/26435
        * tree-loop-linear.c (linear_transform_loops): Don't test
perfect_nest_p.
        Call rewrite_into_loop_closed_ssa only when something changed.
        * lambda.h (gcc_loopnest_to_lambda_loopnest): Update declaration.
        * lambda-code.c (can_convert_to_perfect_nest): Declared.
        (gcc_loopnest_to_lambda_loopnest): Removed need_perfect_nest parameter.
        Test for perfect_nest_p here.  Fix formating.
        (replace_uses_equiv_to_x_with_y): Fix formating.
        (stmt_uses_op): Removed.
        (can_convert_to_perfect_nest): Removed loopivs parameter.
        Complete the test by checking the scalar dependences.
        (perfect_nestify): Remove the test for can_convert_to_perfect_nest.
        Fix formating.  Don't copy statements in the inner loop: move them to
        the inner loop header.


Added:
    branches/gcc-4_1-branch/gcc/testsuite/gcc.dg/tree-ssa/pr20256.c
    branches/gcc-4_1-branch/gcc/testsuite/gcc.dg/tree-ssa/pr26435.c
    branches/gcc-4_1-branch/gcc/testsuite/gfortran.dg/pr27745.f90
Modified:
    branches/gcc-4_1-branch/gcc/ChangeLog
    branches/gcc-4_1-branch/gcc/lambda-code.c
    branches/gcc-4_1-branch/gcc/lambda.h
    branches/gcc-4_1-branch/gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c
    branches/gcc-4_1-branch/gcc/tree-loop-linear.c


-- 


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[pinskia at gcc dot gnu dot org]

------- Comment #12 from pinskia at gcc dot gnu dot org  2006-05-18 04:57 -------
Fixed on the mainline.


-- 

pinskia at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[spop at gcc dot gnu dot org]

------- Comment #11 from spop at gcc dot gnu dot org  2006-05-17 14:26 -------
Subject: Bug 20256

Author: spop
Date: Wed May 17 14:25:59 2006
New Revision: 113862

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=113862
Log:
        PR middle-end/20256
        PR middle-end/26435
        * tree-loop-linear.c (linear_transform_loops): Don't test
perfect_nest_p.
        Call rewrite_into_loop_closed_ssa only when something changed.
        * lambda.h (gcc_loopnest_to_lambda_loopnest): Update declaration.
        * lambda-code.c (can_convert_to_perfect_nest): Declared.
        (gcc_loopnest_to_lambda_loopnest): Removed need_perfect_nest parameter.
        Test for perfect_nest_p here.  Fix formating.
        (replace_uses_equiv_to_x_with_y): Fix formating.
        (stmt_uses_op): Removed.
        (can_convert_to_perfect_nest): Removed loopivs parameter.
        Complete the test by checking the scalar dependences.
        (perfect_nestify): Remove the test for can_convert_to_perfect_nest.
        Fix formating.


Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr20256.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr26435.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/lambda-code.c
    trunk/gcc/lambda.h
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c
    trunk/gcc/tree-loop-linear.c


-- 


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

[Bug tree-optimization/20256] Perfect nest transformation not conservative enough

[pinskia at gcc dot gnu dot org]

------- Comment #10 from pinskia at gcc dot gnu dot org  2006-03-09 13:28 -------
*** Bug 25449 has been marked as a duplicate of this bug. ***


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |RonnyPeine at gmx dot de


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