User account creation filtered due to spam.

Bug 43567 - linear loop transform
Summary: linear loop transform
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.5.0
: P3 normal
Target Milestone: ---
Assignee: Sebastian Pop
URL:
Keywords: wrong-code
: 43568 (view as bug list)
Depends on:
Blocks:
 
Reported: 2010-03-29 12:38 UTC by Alex Turjan
Modified: 2011-02-02 17:48 UTC (History)
5 users (show)

See Also:
Host:
Target: x86
Build:
Known to work:
Known to fail:
Last reconfirmed: 2011-01-18 20:57:45


Attachments
slightly more minimal testcase (180 bytes, text/plain)
2010-06-25 19:16 UTC, Tom de Vries
Details
partially redoing the fix for bug 20612 (1.07 KB, patch)
2010-06-25 20:06 UTC, Tom de Vries
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Alex Turjan 2010-03-29 12:38:12 UTC
The observed bug takes place in linear loop transform. 
The bug can be reproduce by compiling the following C file with gcc.4.5.0 (20100204, 20100325) on x86 machine:
----------------------------------------------------------------
#include <stdio.h>

int test (int n, int *a)
{
  int i, j;

  for (i = 0; i < n; i++)
    {
      for (j = 0; j < n; j++)
	{
	  a[j] = i + n;
	}
    }


    if (a[0] != 31 || i + n - 1 != 31)
       printf("incorrect %d  %d \n", a[0], i+n-1);	

  return 0;
}

int main (void)
{
  int a[16];
  test (16, a);
  return 0;
}
----------------------------------------------------------------

The compiler flags that reproduce the error are:
-O2 -fno-inline -fno-tree-ch -ftree-loop-linear

If the compiler is run with:
-O2 -fno-inline -fno-tree-ch -fno-tree-loop-linear 
then the produced code is correct.
Comment 1 Ozkan Sezer 2010-03-29 13:27:32 UTC
Happens with 4.3 and 4.4, too.
Comment 2 Tom de Vries 2010-06-25 19:16:05 UTC
Created attachment 21007 [details]
slightly more minimal testcase

reproduced on trunk revision 161295
Comment 3 Tom de Vries 2010-06-25 20:06:10 UTC
Created attachment 21008 [details]
partially redoing the fix for bug 20612

The problem is in this piece of code in lambda_loopnest_gcc_loopnest:
...
      /* Create the new iv.  */

      standard_iv_increment_position (temp, &bsi, &insert_after);
      create_iv (newlowerbound,
		 build_int_cst (type, LL_STEP (newloop)),
		 ivvar, temp, &bsi, insert_after, &ivvar,
		 NULL);

      /* Unfortunately, the incremented ivvar that create_iv inserted may not
	 dominate the block containing the exit condition.
	 So we simply create our own incremented iv to use in the new exit
	 test,  and let redundancy elimination sort it out.  */
      inc_stmt = gimple_build_assign_with_ops (PLUS_EXPR, SSA_NAME_VAR (ivvar),
					       ivvar,
					       build_int_cst (type, LL_STEP (newloop)));

      ivvarinced = make_ssa_name (SSA_NAME_VAR (ivvar), inc_stmt);
      gimple_assign_set_lhs (inc_stmt, ivvarinced);
      bsi = gsi_for_stmt (exitcond);
      gsi_insert_before (&bsi, inc_stmt, GSI_SAME_STMT);
...

In case the loop header is copied (-ftree-ch), the second increment is in the same block as the first increment:
...
  lnivtmp.6_13 = lnivtmp.6_20 + 1;
  lnivtmp.6_1 = lnivtmp.6_20 + 1;
  if (lletmp.8_21 >= lnivtmp.6_1)
...
indeed redundancy elimination sorts this out.

However, if the loop header is not copied:
...<bb 5>:
  i_11 = i_1 + 1;
  lnivtmp.2_19 = lnivtmp.2_5 + 1;

<bb 6>:
  # i_1 = PHI <0(2), i_11(5)>
  # lnivtmp.2_5 = PHI <0(2), lnivtmp.2_19(5)>
  lletmp.4_16 = n_4(D) + -1;
  lnivtmp.2_17 = lnivtmp.2_5 + 1;
  if (lletmp.4_16 >= lnivtmp.2_17)
...
the second increment is an extra increment, on top of the first one.

The patches fixes this, I'm not sure how minimal or efficient, but I did a x86_64-unknown-linux-gnu bootstrap build and ran testsuites (gcc, objc, gfortran, g++, libgomp, libstdc++, libjava, libmudflap, libffi) for r161295
and r161295+patch, with identical results.
Comment 4 Tom de Vries 2010-07-11 06:10:45 UTC
submitted patch for review: http://gcc.gnu.org/ml/gcc-patches/2010-07/msg00879.html
Comment 5 Sebastian Pop 2011-01-18 20:47:10 UTC
*** Bug 43568 has been marked as a duplicate of this bug. ***
Comment 6 Sebastian Pop 2011-01-18 20:54:23 UTC
Author: spop
Date: Tue Jan 18 20:54:18 2011
New Revision: 168962

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=168962
Log:
Add testcase for PR43567.

2011-01-18  Sebastian Pop  <sebastian.pop@amd.com>

	PR tree-optimization/43567
	* gcc.dg/graphite/pr43567.c: New.

Added:
    branches/graphite/gcc/testsuite/gcc.dg/graphite/pr43567.c
Modified:
    branches/graphite/gcc/ChangeLog.graphite
Comment 7 Sebastian Pop 2011-01-18 20:57:45 UTC
Fixed on the graphite branch.
Comment 8 Sebastian Pop 2011-01-25 21:24:41 UTC
Author: spop
Date: Tue Jan 25 21:24:35 2011
New Revision: 169252

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=169252
Log:
Add testcase for PR43567.

2011-01-25  Sebastian Pop  <sebastian.pop@amd.com>

	PR tree-optimization/43567
	* gcc.dg/graphite/pr43567.c: New.

Added:
    trunk/gcc/testsuite/gcc.dg/graphite/pr43567.c
Modified:
    trunk/gcc/ChangeLog.graphite
    trunk/gcc/testsuite/ChangeLog
Comment 9 Sebastian Pop 2011-01-25 21:28:23 UTC
Fixed.
Comment 10 Diego Novillo 2011-02-02 17:48:04 UTC
Author: dnovillo
Date: Wed Feb  2 17:48:00 2011
New Revision: 169591

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=169591
Log:
Add testcase for PR43567.

2011-01-25  Sebastian Pop  <sebastian.pop@amd.com>

	PR tree-optimization/43567
	* gcc.dg/graphite/pr43567.c: New.

Added:
    branches/google/integration/gcc/testsuite/gcc.dg/graphite/pr43567.c
Modified:
    branches/google/integration/gcc/ChangeLog.graphite
    branches/google/integration/gcc/testsuite/ChangeLog