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

["rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.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.