[Bug tree-optimization/54489] New: tree FRE uses an excessive amount of memory

[Bug tree-optimization/54489] New: tree FRE uses an excessive amount of memory

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54489

             Bug #: 54489
           Summary: tree FRE uses an excessive amount of memory
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Keywords: memory-hog
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: rguenth@gcc.gnu.org


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.

[Bug tree-optimization/54489] tree FRE uses an excessive amount of memory

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54489

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 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.

[Bug tree-optimization/54489] tree FRE uses an excessive amount of memory

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54489

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2012-09-10
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-10 14:38:21 UTC ---
I have a patch that I just need to polish somewhat.

[Bug tree-optimization/54489] tree FRE uses an excessive amount of memory

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54489

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 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

[Bug tree-optimization/54489] tree FRE uses an excessive amount of memory

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54489

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.8.0

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-12 14:48:22 UTC ---
Fixed for GCC 4.8.