Bug 40761

Ack.

Is it the nesting of loops or really the number of function calls that is important?

do while does not have the same behavior, so the loop "shape" is important.  the following is as bad and does not have function calls.

#define ONE     while (x-- > y)
#define TEN     ONE ONE ONE ONE ONE ONE ONE ONE ONE ONE
#define HUN     TEN TEN TEN TEN TEN TEN TEN TEN TEN TEN
#define THOU    HUN HUN HUN HUN HUN HUN HUN HUN HUN HUN

void foo(int x, int y)
{
  /* 11,000 nested whiles.  */
  THOU THOU THOU THOU THOU THOU THOU THOU THOU THOU THOU
  y++;
}

This now causes an ICE:

ig25@linux-fd1f:/tmp> cat haha.c
#define ONE     while (b())
#define TEN     ONE ONE ONE ONE ONE ONE ONE ONE ONE ONE
#define HUN     TEN TEN TEN TEN TEN TEN TEN TEN TEN TEN
#define THOU    HUN HUN HUN HUN HUN HUN HUN HUN HUN HUN

void foo()
{
  /* 1,000 nested whiles.  */
  THOU
  a();
}
ig25@linux-fd1f:/tmp> gcc -O3 haha.c
haha.c: In Funktion »foo«:
haha.c:6:6: interner Compiler-Fehler: in compute_antic, bei tree-ssa-pre.c:2557
Bitte senden Sie einen vollständigen Fehlerbericht auf Englisch ein;
bearbeiten Sie die Quellen zunächst mit einem Präprozessor, wenn es
dienlich ist.
Fehler in der deutschen Übersetzung sind an translation-team-de@lists.sourceforge.net zu melden.

Gehen Sie gemäß den Hinweisen in <http://gcc.gnu.org/bugs.html> vor.

Backtrace:

Breakpoint 1, fancy_abort (file=0xd791f0 "../../trunk/gcc/tree-ssa-pre.c", line=2557,
    function=0xd799ed "compute_antic") at ../../trunk/gcc/diagnostic.c:728
728     {
(gdb) up
#1  0x00000000008ab23c in compute_antic () at ../../trunk/gcc/tree-ssa-pre.c:2557
2557          gcc_assert (num_iterations < 500);

The gcc_assert appears to be triggered for this case was introduced
by jakub:

118169    dberlin       }
137036      jakub #ifdef ENABLE_CHECKING
118821    dberlin       /* Theoretically possible, but *highly* unlikely.  */
137036      jakub       gcc_assert (num_iterations < 500);
137036      jakub #endif
 81764   dnovillo     }


Resetting to P3 for new triage, as this is now ice-on-valid-code.

We shouldn't have deferred BB31 in the first iteration (with just TEN):

<bb 2>:
  goto <bb 13>;

...
<bb 31>:

<bb 13>:
  D.2759_1 = b ();
  if (D.2759_1 != 0)
    goto <bb 32>;
  else
    goto <bb 14>;

<bb 32>:
  goto <bb 12>;

<bb 14>:
  return;

Starting iteration 0
...
Block 31 was deferred for a future iteration.
ANTIC_OUT[14] := {  }
ANTIC_IN[14] := {  }
S[14] := {  }
ANTIC_OUT[13] := {  }
ANTIC_IN[13] := {  }
S[13] := {  }
ANTIC_OUT[2] := {  }
ANTIC_IN[2] := {  }
S[2] := {  }
Starting iteration 1

which means we are iterating in non-optimal order - which is postorder.
It looks like post_order_compute computes BS.

Mine.

Subject: Bug 40761

Author: rguenth
Date: Thu Mar  4 13:25:27 2010
New Revision: 157225

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=157225
Log:
2010-03-04  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/40761
	* tree-ssa-pre.c (compute_antic): Walk reverse postorder
	in reverse order.
	(my_rev_post_order_compute): New function.
	(init_pre): Call it.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-pre.c

PRE issue fixed for 4.5, still latent on the 4.4 branch.

Should we also commit the test case from #4 ?

(In reply to comment #9)
> Should we also commit the test case from #4 ?

No.  It's too slow.

GCC 4.5.0 is being released.  Deferring to 4.5.1.

GCC 4.5.1 is being released, adjusting target milestone.

GCC 4.5.2 is being released, adjusting target milestone.

GCC 4.5.3 is being released, adjusting target milestone.

Blocks the memory-hog/compile-time-hog regression.  Removing regression
markers.

I'll work on it.

  The problem was in building CFG loops which took the most of time.   CFG loops were built even if we don't use regional allocation as for -O0.

  I'll send a patch soon.  It is not small because IRA in any case uses one region with CFG loop representing the whole function.

Author: vmakarov
Date: Thu Jan 19 20:46:31 2012
New Revision: 183312

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=183312
Log:
2012-01-19  Vladimir Makarov  <vmakarov@redhat.com>

	PR rtl-optimization/40761
	* ira-int.h (struct ira_loop_tree_node): Add comment for member
	loop.  Add new member loop_num.
	(IRA_LOOP_NODE_BY_INDEX): Modify the check.
	(ira_build): Remove the parameter.

	* ira.c (ira_print_disposition): Use loop_num instead of
	loop->num.
	(ira.c): Do not build CFG loops for one region allocation.  Remove
	argument from ira_build call.

	* ira-build.c (init_loop_tree_node): New function.
	(create_loop_tree_nodes): Use it.  Separate the case when CFG
	loops are not built.
	(more_one_region_p): Check current_loops.
	(finish_loop_tree_nodes): Separate the case when CFG loops are not
	built.
	(add_loop_to_tree): Process loop equal to NULL too.
	(form_loop_tree): Separate the case when CFG loops are not built.
	Use explicitly number for the root.
	(rebuild_regno_allocno_maps, create_loop_tree_node_allocnos): Add
	an assertion.
	(ira_print_expanded_allocno, loop_compare_func): Use loop_num
	instead of loop->num.
	(mark_loops_for_removal): Ditto.  Use loop_num instead of
	loop->num.
	(mark_all_loops_for_removal): Ditto.
	(remove_unnecessary_regions): Separate the case when CFG loops
	are not built.
	(ira_build): Remove the parameter.  Use explicit number of regions
	when CFG loops are not built.

	* ira-color.c (print_loop_title): Separate the case for the root
	node.  Use loop_num instead of loop->num.
	(move_spill_restore): Use loop_num instead of loop->num.

	* ira-emit.c (setup_entered_from_non_parent_p): Add an assertion.
	(change_loop): Ditto.
	(change_loop): Use loop_num instead of loop->num.

	* ira-lives.c (process_bb_node_lives): Ditto.

	* ira-costs.c (print_allocno_costs, find_costs_and_classes):
	Ditto.

	* ira-conflicts.c (print_allocno_conflicts): Ditto.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ira-build.c
    trunk/gcc/ira-color.c
    trunk/gcc/ira-conflicts.c
    trunk/gcc/ira-costs.c
    trunk/gcc/ira-emit.c
    trunk/gcc/ira-int.h
    trunk/gcc/ira-lives.c
    trunk/gcc/ira.c

See c#18.  This issue has been resolved.