[Bug tree-optimization/62291] New: PRE uses too much memory and compile-time

[Bug tree-optimization/62291] New: PRE uses too much memory and compile-time

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291

            Bug ID: 62291
           Summary: PRE uses too much memory and compile-time
           Product: gcc
           Version: 4.9.1
            Status: UNCONFIRMED
          Keywords: compile-time-hog, memory-hog
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org
            Blocks: 47344

Created attachment 33409
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=33409&action=edit
preprocessed testcase

For the attached testcase (from GHC) PRE blows up memory and compile-time wise
at -O2, -O2 -fno-tree-pre and -O1 are fine.

Usual suspect is AVAIL_OUT which was only eliminated for FRE.

[Bug tree-optimization/62291] PRE uses too much memory and compile-time

[steven at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-08-29
     Ever confirmed|0                           |1

[Bug tree-optimization/62291] PRE uses too much memory and compile-time

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Fri Aug 29 12:39:50 2014
New Revision: 214727

URL: https://gcc.gnu.org/viewcvs?rev=214727&root=gcc&view=rev
Log:
2014-08-29  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/62291
    * tree-ssa-pre.c (sorted_array_from_bitmap_set): Reserve
    exactly the vector size needed and use quick_push.
    (phi_translate_1): Adjust comment.
    (valid_in_sets): Remove block argument and remove pointless
    checking of NAMEs.
    (dependent_clean): Adjust for removal of block argument.
    (clean): Likewise.
    (compute_antic_aux): Likewise.
    (compute_partial_antic_aux): Likewise.

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

[Bug tree-optimization/62291] PRE uses too much memory and compile-time

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
As said in the mail for the just applied patch:

"The second patch (once done) will refactor insertion phase
to do a dominator walk similar to what elimination does
computing AVAIL_OUT on-the-fly (and only keeping it live
for a single block).  It's a bit more complicated than
for elimination as insertion looks at a block and all its
predecessors, it's also a bit more costly as we iterate
insertion.  It's also more costly because computing
AVAIL_OUT on-the-fly requires looking at all statements
which insertion currently doesn't do at all.
So I've not yet settled on a final idea how to best re-factor it,
eventually insertion and elimination can be merged (and then
still iterate(?)).

Ideas welcome ;)"

[Bug tree-optimization/62291] PRE uses too much memory and compile-time

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
So what remains is insertion computing whether a value is available on some
predecessor (partial redundancy) or all (full redundancy) which needs AVAIL_OUT
for the predecessors and the immediate dominator.

Then the actual insertion code needs to lookup leaders for expression operands
it wants to insert.  I think this part can be easily delayed until eliminate
if we store all necessary information in some new data structure.

The first part is harder - especially as it is that what needs to be iterated
(with taking into account newly inserted stuff).  One could imagine
iterating over sucessors of a block (and immediate dominated-bys) and compute
"candidate" sets, both pruning and extending it during the iteration.

[Bug tree-optimization/62291] tree PRE uses too much memory and compile-time

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62291

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|PRE uses too much memory    |tree PRE uses too much
                   |and compile-time            |memory and compile-time
      Known to work|                            |10.1.0, 11.1.0, 12.1.0,
                   |                            |13.1.0

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
On a Ryzen 9 7900X I get with GCC 13.2

-O0   1.4s  430MB
-O1  17.4s  640MB
-O2  26.9s  822MB
-O2 -fdisable-tree-pre  22.3s  690MB
-O3  26.9s  824MB

it's now far from blowing up (in PRE).  GCC 5.5 needs 3.5GB of memory, GCC 7
needs 5.5GB.  I can't really reproduce high compile-time even with 4.9.5.

The problem that AVAIL_OUT compute requires quadratic memory isn't solved.

-ftime-report with GCC 13.2 shows

 alias stmt walking                 :   8.42 ( 31%)   0.17 ( 18%)   8.29 ( 29%)
 4743k (  1%)
 tree PTA                           :   7.74 ( 28%)   0.20 ( 22%)   7.95 ( 28%)
 2706k (  1%)
 tree PRE                           :   0.29 (  1%)   0.01 (  1%)   0.31 (  1%)
   23M (  4%)

and with -details

 tree PRE                           :   0.29 (  1%)   0.00 (  0%)   0.34 (  1%)
   23M (  4%)
 `- tree tail merge                 :   0.02 (  0%)   0.00 (  0%)   0.03 (  0%)
    0  (  0%)
 `- loop init                       :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
    0  (  0%)
 `- tree PTA                        :   2.64 ( 10%)   0.05 (  6%)   2.69 (  9%)
  604k (  0%)
 `- alias stmt walking              :   2.02 (  7%)   0.04 (  5%)   2.01 (  7%)
 1185k (  0%)