Bug 43360 - [4.3/4.4/4.5 Regression] wrong loop invariant hoisting
Summary: [4.3/4.4/4.5 Regression] wrong loop invariant hoisting
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: rtl-optimization (show other bugs)
Version: 4.5.0
: P2 normal
Target Milestone: 4.3.5
Assignee: Steven Bosscher
URL:
Keywords: wrong-code
Depends on:
Blocks:
 
Reported: 2010-03-14 06:22 UTC by John Regehr
Modified: 2010-03-18 13:20 UTC (History)
7 users (show)

See Also:
Host:
Target: x86-64-*-*, i?86-*-*
Build:
Known to work: 4.2.1 4.3.5 4.4.4 4.5.0
Known to fail: 4.3.4 4.4.3
Last reconfirmed: 2010-03-17 08:33:51


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description John Regehr 2010-03-14 06:22:15 UTC
I believe the -O1 result is correct.

regehr@john-home:~/volatile/bugs/tmp290/2$ current-gcc -O1 small.c -o small
regehr@john-home:~/volatile/bugs/tmp290/2$ ./small
11
regehr@john-home:~/volatile/bugs/tmp290/2$ current-gcc -O2 small.c -o small
regehr@john-home:~/volatile/bugs/tmp290/2$ ./small
8
regehr@john-home:~/volatile/bugs/tmp290/2$ current-gcc -v

Using built-in specs.
COLLECT_GCC=current-gcc
COLLECT_LTO_WRAPPER=/home/regehr/z/compiler-install/gcc-r157445-install/libexec/gcc/i686-pc-linux-gnu/4.5.0/lto-wrapper
Target: i686-pc-linux-gnu
Configured with: ../configure --with-libelf=/usr/local --enable-lto --prefix=/home/regehr/z/compiler-install/gcc-r157445-install --program-prefix=r157445- --enable-languages=c,c++
Thread model: posix
gcc version 4.5.0 20100314 (experimental) (GCC) 

regehr@john-home:~/volatile/bugs/tmp290/2$ cat small.c

extern int printf (__const char *__restrict __format, ...);

int g_3[9][2];
int l_5[7][6];

void func_1 (void);
void func_1 (void)
{
  int i, j;

  for (i = 0; i < 7; i++) {
    for (j = 0; j < 6; j++) {
      l_5[i][j] = 4;
    }
  }

  for (g_3[8][0] = 1; g_3[8][0] < 8; g_3[8][0] += 7) {
    int *l_6 = &g_3[8][0];
    *l_6 = l_5[5][2];
  }

}

int main (void)
{
  func_1 ();
  printf ("%d\n", g_3[8][0]);
  return 0;
}
Comment 1 Ozkan Sezer 2010-03-14 06:37:35 UTC
gcc-4.4 seems affected, too.
Comment 2 Mikael Pettersson 2010-03-14 09:08:45 UTC
Confirmed current 4.4 is affected too, -01 works -O2 fails. Reduced test case:

int l_5_5_2 = 4;
int g_3[1][1];

void func_1 (void)
{
  for (g_3[0][0] = 1; g_3[0][0] < 8; g_3[0][0] += 7) {
    int *l_6 = &g_3[0][0];
    *l_6 = l_5_5_2;
  }
}

int main (void)
{
  func_1 ();
  if (g_3[0][0] != 11)
      __builtin_abort ();
  return 0;
}
Comment 3 H.J. Lu 2010-03-14 15:32:49 UTC
Gcc 4.3 also failed. It also failed on Linux/x86-64.
Comment 4 H.J. Lu 2010-03-14 18:25:00 UTC
It is caused by revision 121227:

http://gcc.gnu.org/ml/gcc-cvs/2007-01/msg00933.html
Comment 5 H.J. Lu 2010-03-14 18:31:28 UTC
The patch started at:

http://gcc.gnu.org/ml/gcc-patches/2007-01/msg01682.html
Comment 6 Uroš Bizjak 2010-03-14 20:59:20 UTC
The problem is actually in loop2_invariant rtl pass, and -O1/-O2 difference is in fact due to missing cprop pass in -O1 case.

So, before _.162r.loop2_invariant, we have:

    6 [`g_3']=0x1
    7 r61:SI=[`l_5_5_2']
L13:
    8 NOTE_INSN_BASIC_BLOCK
    9 [`g_3']=r61:SI
   11 {r60:SI=r61:SI+0x7;clobber flags:CC;}
      REG_DEAD: r63:SI
      REG_UNUSED: flags:CC
      REG_EQUAL: [`g_3']+0x7
   12 [`g_3']=r60:SI

and loop2_invariant pass declares (insn 11) as invariant even when REG_EQUAL says it depends on ['g_3']:

    6 [`g_3']=0x1
    7 r61:SI=[`l_5_5_2']
   11 {r63:SI=r61:SI+0x7;clobber flags:CC;}
      REG_DEAD: r62:SI
      REG_UNUSED: flags:CC
      REG_EQUAL: [`g_3']+0x7
L13:
    8 NOTE_INSN_BASIC_BLOCK
    9 [`g_3']=r61:SI
   22 r60:SI=r63:SI
   12 [`g_3']=r63:SI

Things go down the hill from there, since later pass substitutes (insn 11) with REG_EQUAL value: [`g_3']+0x7 -> 0x1 + 0x7 = 0x8.

So, the solution is to teach loop2_invariant to also look into REG_EQUAL notes if the insn is _really_ invariant or eventually clear REG_EQUAL notes when insn is moved out of the loop.

Re-classified as rtl-optimization bug.
Comment 7 Eric Botcazou 2010-03-14 21:40:18 UTC
> So, the solution is to teach loop2_invariant to also look into REG_EQUAL notes
> if the insn is _really_ invariant or eventually clear REG_EQUAL notes when
> insn is moved out of the loop.

Both should already happen though, see move_invariant_reg:

      /* If there is a REG_EQUAL note on the insn we just moved, and
	 insn is in a basic block that is not always executed, the note
	 may no longer be valid after we move the insn.
	 Note that uses in REG_EQUAL notes are taken into account in
	 the computation of invariants.  Hence it is safe to retain the
	 note even if the note contains register references.  */
      if (! inv->always_executed
	  && (note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX)))
	remove_note (inv->insn, note);

so there is apparently a flaw somewhere.
Comment 8 Jakub Jelinek 2010-03-14 22:17:45 UTC
Well, it is always executed, just [`g_3'] in REG_EQUAL is not invariant.
Comment 9 Richard Biener 2010-03-15 11:30:17 UTC
I'd say its P2 only because it does affect released compilers and is not a
regression on their branches.
Comment 10 Paolo Bonzini 2010-03-17 06:41:48 UTC
REG_EQUAL notes are not there to guarantee correctness.  Relying on them to avoid misoptimization is always wrong and just hides the bug.

It is a regression from 4.2.
Comment 11 Steven Bosscher 2010-03-17 08:23:48 UTC
So why not just something like the following:

 	 Note that uses in REG_EQUAL notes are taken into account in
 	 the computation of invariants.  Hence it is safe to retain the
 	 note even if the note contains register references.  */
-      if (! inv->always_executed
-	  && (note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX)))
+      note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX);
+      if (note
+          && (! inv->always_executed
+              || ! check_maybe_invariant (XEXP (note, 0)))
 	remove_note (inv->insn, note);
     }
   else


In other words, nuke the note if it is not always executed or if the note value is not invariant?
Comment 12 Jakub Jelinek 2010-03-17 08:30:57 UTC
If it is ok to call check_maybe_invariant in this spot, then I think that's the right fix.
Comment 13 Steven Bosscher 2010-03-17 08:33:51 UTC
Mine.
Comment 14 Eric Botcazou 2010-03-17 08:59:31 UTC
I just posted the same fix. :-)  Yes, it is OK for all branches.
Comment 15 hjl@gcc.gnu.org 2010-03-18 13:11:09 UTC
Subject: Bug 43360

Author: hjl
Date: Thu Mar 18 13:10:49 2010
New Revision: 157539

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=157539
Log:
Remove the REG_EQUAL note if we don't know its invariant status.

gcc/

2010-03-18  Steven Bosscher  <steven@gcc.gnu.org>
	    Eric Botcazou  <ebotcazou@adacore.com>

	PR rtl-optimization/43360
	* loop-invariant.c (move_invariant_reg): Remove the REG_EQUAL
	note if we don't know its invariant status.

gcc/testsuite/

2010-03-18  H.J. Lu  <hongjiu.lu@intel.com>

	PR rtl-optimization/43360
	* gcc.dg/torture/pr43360.c: New.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr43360.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/loop-invariant.c
    trunk/gcc/testsuite/ChangeLog

Comment 16 hjl@gcc.gnu.org 2010-03-18 13:13:56 UTC
Subject: Bug 43360

Author: hjl
Date: Thu Mar 18 13:13:42 2010
New Revision: 157540

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=157540
Log:
Remove the REG_EQUAL note if we don't know its invariant status.

gcc/

2010-03-18  H.J. Lu  <hongjiu.lu@intel.com>

	Backport from mainline:
	2010-03-18  Steven Bosscher  <steven@gcc.gnu.org>
		    Eric Botcazou  <ebotcazou@adacore.com>

	PR rtl-optimization/43360
	* loop-invariant.c (move_invariant_reg): Remove the REG_EQUAL
	note if we don't know its invariant status.

gcc/testsuite/

2010-03-18  H.J. Lu  <hongjiu.lu@intel.com>

	Backport from mainline:
	2010-03-18  H.J. Lu  <hongjiu.lu@intel.com>

	PR rtl-optimization/43360
	* gcc.dg/torture/pr43360.c: New.

Added:
    branches/gcc-4_3-branch/gcc/testsuite/gcc.dg/torture/pr43360.c
      - copied unchanged from r157539, trunk/gcc/testsuite/gcc.dg/torture/pr43360.c
Modified:
    branches/gcc-4_3-branch/gcc/ChangeLog
    branches/gcc-4_3-branch/gcc/loop-invariant.c
    branches/gcc-4_3-branch/gcc/testsuite/ChangeLog

Comment 17 hjl@gcc.gnu.org 2010-03-18 13:15:40 UTC
Subject: Bug 43360

Author: hjl
Date: Thu Mar 18 13:15:21 2010
New Revision: 157541

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=157541
Log:
Remove the REG_EQUAL note if we don't know its invariant status.

gcc/

2010-03-18  H.J. Lu  <hongjiu.lu@intel.com>

	Backport from mainline:
	2010-03-18  Steven Bosscher  <steven@gcc.gnu.org>
		    Eric Botcazou  <ebotcazou@adacore.com>

	PR rtl-optimization/43360
	* loop-invariant.c (move_invariant_reg): Remove the REG_EQUAL
	note if we don't know its invariant status.

gcc/testsuite/

2010-03-18  H.J. Lu  <hongjiu.lu@intel.com>

	Backport from mainline:
	2010-03-18  H.J. Lu  <hongjiu.lu@intel.com>

	PR rtl-optimization/43360
	* gcc.dg/torture/pr43360.c: New.

Added:
    branches/gcc-4_4-branch/gcc/testsuite/gcc.dg/torture/pr43360.c
      - copied unchanged from r157540, trunk/gcc/testsuite/gcc.dg/torture/pr43360.c
Modified:
    branches/gcc-4_4-branch/gcc/ChangeLog
    branches/gcc-4_4-branch/gcc/loop-invariant.c
    branches/gcc-4_4-branch/gcc/testsuite/ChangeLog

Comment 18 H.J. Lu 2010-03-18 13:16:38 UTC
Fixed.
Comment 19 Steven Bosscher 2010-03-18 13:20:55 UTC
For the record: bootstrapped+tested on amd64-linux and ia64-linux.