GCC Bugzilla has been upgraded from version 4.4.9 to 5.0rc3. If you see any problem, please report it to bug 64968.

Bug 49217

Summary: Wrong optimization of code
Product: gcc Reporter: e-maxx <personal>
Component: tree-optimizationAssignee: Richard Biener <rguenth>
Status: RESOLVED FIXED    
Severity: normal CC: hubicka, personal
Priority: P3    
Version: 4.6.0   
Target Milestone: 4.6.1   
Host: Target:
Build: Known to work:
Known to fail: 4.6.0 Last reconfirmed: 2011-05-29 10:17:18
Attachments: The program demostrating the bug (should return 0 if OK, but throws in case of wrong optimization)

Description e-maxx 2011-05-29 01:17:27 UTC
Created attachment 24387 [details]
The program demostrating the bug (should return 0 if OK, but throws in case of wrong optimization)

A bug in gcc 4.6.0 optimizer leads to incorrect program flow.

It looks like this exact bug is difficult to reproduce in small program, so the attached program is a result of my minimization.

The bug requires quite complex environment: recursive function, std::vector, std::vector::iterator, zeroing the global array, unreachable 'else'.

Though, I think, the main idea of the program is not so difficult: we call DFS(0), it calls DFS(1), and as a result both 0 and 1 are marked as visited, so the number of calls of DFS() from main() is equal to one. But in g++ 4.6.0 with -O2 that's not true (it looks like DFS(0) never calls DFS(1), but that's my hypothesis).

Inserting cerr or cout into some places of DFS makes the program work fine.
Comment 1 Richard Biener 2011-05-29 10:17:18 UTC
Confirmed.  Looks like alias analysis thinks that DFS() does not clobber visited.
Comment 2 Richard Biener 2011-05-29 10:56:58 UTC
Partial inlining is responsible for this.  With -fdump-tree-all-details we
ICE in CFG-cleanup that runs after fnsplit.

Then IPA pure-const computes garbage so alias analysis is confused.  Hmm.
main calls DFS:

void DFS(int)/83(71) @0x1429ec580 (asm: _Z3DFSi) availability:available analyzed 12 time, 13 benefit (114 after inlining) 8 size, 5 benefit (17 after inlining) needed reachable body externally_visible finalized inlinable
  called by: int main()/84 (0.58 per call) void _Z3DFSi.part.0(int)/97 (6.17 per call)
  calls: void _Z3DFSi.part.0(int)/97 (inlined) (0.61 per call)
  References:  var:bool visited [2] (read)
  Refering this function:

void _Z3DFSi.part.0(int)/97(-1) @0x101764dc0 (asm: _Z3DFSi.part.0) (inline copy in void DFS(int)/83) availability:local analyzed 181 time, 13 benefit 14 size, 5 benefit reachable body local prevailing_def_ironly finalized inlinable
  called by: void DFS(int)/83 (0.61 per call) (inlined)
  calls: void DFS(int)/83 (6.17 per call) (nested in 2 loops)
  References:  var:bool visited [2] (write) var:std::vector<int> g [2] (addr) var:std::vector<int> g [2] (addr)
  Refering this function:

but

Starting cycle
  Visiting void DFS(int)/83 state:const looping 0
    Call to void _Z3DFSi.part.0(int)/97 state:pure looping:1
    nonreadonly global var read
  Visiting void _Z3DFSi.part.0(int)/97 state:pure looping 1
    Call to void DFS(int)/83 state:const looping:0
    nonreadonly global var read
Result pure looping 1Function found to be looping pure: void DFS(int)Function found to be looping pure: void _Z3DFSi.part.0(int)

so it seems, contrary to the comment from local analysis code, at IPA
propagation time the IPA references are _not_ taken into account.

Shouldn't bot indirect call processing and ipa reference walking use
w and not node?

Thus, the bug seems to be fixed with

Index: ipa-pure-const.c
===================================================================
--- ipa-pure-const.c	(revision 174393)
+++ ipa-pure-const.c	(working copy)
@@ -1223,7 +1223,7 @@
 	    break;
 
 	  /* Now process the indirect call.  */
-          for (ie = node->indirect_calls; ie; ie = ie->next_callee)
+          for (ie = w->indirect_calls; ie; ie = ie->next_callee)
 	    {
 	      enum pure_const_state_e edge_state = IPA_CONST;
 	      bool edge_looping = false;
@@ -1246,7 +1246,7 @@
 	    break;
 
 	  /* And finally all loads and stores.  */
-	  for (i = 0; ipa_ref_list_reference_iterate (&node->ref_list, i, ref); i++)
+	  for (i = 0; ipa_ref_list_reference_iterate (&w->ref_list, i, ref); i++)
 	    {
 	      enum pure_const_state_e ref_state = IPA_CONST;
 	      bool ref_looping = false;
Comment 3 Richard Biener 2011-05-29 17:00:16 UTC
Author: rguenth
Date: Sun May 29 17:00:13 2011
New Revision: 174399

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=174399
Log:
2011-05-29  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/49217
	* ipa-pure-const.c (propagate_pure_const): Fix typos.

	* gcc.dg/torture/pr49217.c: New testcase.

Added:
    branches/gcc-4_6-branch/gcc/testsuite/gcc.dg/torture/pr49217.c
Modified:
    branches/gcc-4_6-branch/gcc/ChangeLog
    branches/gcc-4_6-branch/gcc/ipa-pure-const.c
    branches/gcc-4_6-branch/gcc/testsuite/ChangeLog
Comment 4 Richard Biener 2011-05-29 17:01:28 UTC
Fixed.
Comment 5 Richard Biener 2011-05-29 17:03:42 UTC
Author: rguenth
Date: Sun May 29 17:03:38 2011
New Revision: 174400

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=174400
Log:
2011-05-29  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/49217
	* ipa-pure-const.c (propagate_pure_const): Fix typos.

	* gcc.dg/torture/pr49217.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr49217.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ipa-pure-const.c
    trunk/gcc/testsuite/ChangeLog