Bug 54489 - tree FRE uses an excessive amount of memory
Summary: tree FRE uses an excessive amount of memory
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.8.0
: P3 normal
Target Milestone: 4.8.0
Assignee: Richard Biener
URL:
Keywords: memory-hog
Depends on:
Blocks:
 
Reported: 2012-09-05 10:28 UTC by Richard Biener
Modified: 2012-09-12 14:48 UTC (History)
0 users

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2012-09-10 00:00:00

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Richard Biener 2012-09-05 10:28:20 UTC 
FRE can use an excessive amount of memory for storing AVAIL_OUT bitmaps
needed for leader finding in eliminate ().  The testcase of PR46590 does
not fit into 4GB of memory because of this.  The root cause is:

      /* Initially, the set of available values in BLOCK is that of
         its immediate dominator.  */
      dom = get_immediate_dominator (CDI_DOMINATORS, block);
      if (dom)
        bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));

basically accumulating at least all dominating SSA defs with different
value-number in each basic-block.

Instead of applying surgery to FRE in tree-ssa-pre.c FRE should be split
out and unify eliminate () and avail computation in a dominator walk
which would avoid keeping all AVAIL_OUT bitmaps live at a time.
Comment 1 Richard Biener 2012-09-05 13:52:25 UTC 
Testcase:

int foo (int a)
{
  int b = 0;
#define X if (a) b = b + 1;
#define XX X X X X X X X X X X
#define XXX XX XX XX XX XX XX XX XX XX XX
#define XXXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX
#define XXXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
#define XXXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX XXXXX
#define XXXXXXX XXXXXX XXXXXX XXXXXX XXXXXX XXXXXX XXXXXX XXXXXX XXXXXX XXXXXX XXXXXX
  XXXXXX
  return b;
}

also relevant is the testcase from PR54492 which we should not regress.
Comment 2 Richard Biener 2012-09-10 14:38:21 UTC 
I have a patch that I just need to polish somewhat.
Comment 3 Richard Biener 2012-09-12 14:46:35 UTC 
Author: rguenth
Date: Wed Sep 12 14:46:22 2012
New Revision: 191225

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=191225
Log:
2012-09-12  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/54489
	* tree-ssa-pre.c: Include domwalk.h.
	(in_fre): Remove.
	(sccvn_valnum_from_value_id): New function.
	(debug_bitmap_sets_for): Simplify.
	(get_representative_for): Properly initialize the SCCVN valnum.
	(create_expression_by_pieces): Likewise.
	(insert_into_preds_of_block): Likewise.
	(can_PRE_operation): Remove.
	(make_values_for_phi): Simplify.
	(compute_avail): Likewise.
	(do_SCCVN_insertion): Remove.
	(eliminate_avail, eliminate_push_avail, eliminate_insert):
	New functions.
	(eliminate): Split and perform a domwalk.
	(eliminate_bb): Former eliminate part that is now dom-enter.
	(eliminate_leave_block): New function.
	(fini_eliminate): Likewise.
	(init_pre): Simplify.
	(fini_pre): Likewise.
	(execute_pre): Fold into do_pre and do_fre.
	(do_pre): Consume execute_pre.
	(do_fre): Likewise.
	* Makefile.in (tree-ssa-pre.o): Add domwalk.h dependency.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/Makefile.in
    trunk/gcc/tree-ssa-pre.c
Comment 4 Richard Biener 2012-09-12 14:48:22 UTC 
Fixed for GCC 4.8.