[gcc(refs/users/marxin/heads/marxin-gcc-benchmark-branch)] alias: Punt after walking too many VALUEs during a toplevel find_base_term call [PR94045]

[Martin Liska]

https://gcc.gnu.org/g:2e94d3ee47be0742df843d95e3d1bf1da11e4796

commit 2e94d3ee47be0742df843d95e3d1bf1da11e4796
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Mar 9 13:38:23 2020 +0100

    alias: Punt after walking too many VALUEs during a toplevel find_base_term call [PR94045]
    
    As mentioned in the PR, on a largish C++ testcase the compile time
    on i686-linux is about 16 minutes on a fast box, mostly spent in
    find_base_term recursive calls dealing with very deep chains of preserved
    VALUEs during var-tracking.
    
    The following patch punts after we process many VALUEs (we already have code
    to punt if we run into a VALUE cycle).
    
    I've gathered statistics on when we punt this way (with BITS_PER_WORD, TU,
    function columns piped through sort | uniq -c | sort -n):
         36 32 ../../gcc/asan.c _Z29initialize_sanitizer_builtinsv.part.0
        108 32 _first_test.go reflect_test.reflect_test..import
       1005 32 /home/jakub/src/gcc/gcc/testsuite/gcc.dg/pr85180.c foo
       1005 32 /home/jakub/src/gcc/gcc/testsuite/gcc.dg/pr87985.c foo
       1005 64 /home/jakub/src/gcc/gcc/testsuite/gcc.dg/pr85180.c foo
       1005 64 /home/jakub/src/gcc/gcc/testsuite/gcc.dg/pr87985.c foo
       2534 32 /home/jakub/src/gcc/gcc/testsuite/gcc.dg/stack-check-9.c f3
       6346 32 ../../gcc/brig/brig-lang.c brig_define_builtins
       6398 32 ../../gcc/d/d-builtins.cc d_define_builtins
       8816 32 ../../gcc/c-family/c-common.c c_common_nodes_and_builtins
       8824 32 ../../gcc/lto/lto-lang.c lto_define_builtins
      41413 32 /home/jakub/src/gcc/gcc/testsuite/gcc.dg/pr43058.c test
    Additionally, for most of these (for the builtins definitions tested just
    one) I've verified with a different alias.c change which didn't punt but
    in the toplevel find_base_term recorded if visited_vals reached the limit
    whether the return value was NULL_RTX or something different, and in all
    these cases the end result was NULL_RTX, so at least in these cases it
    should just shorten the time until it returns NULL.
    
    2020-03-09  Jakub Jelinek  <jakub@redhat.com>
    
            PR rtl-optimization/94045
            * params.opt (-param=max-find-base-term-values=): New option.
            * alias.c (find_base_term): Add cut-off for number of visited VALUEs
            in a single toplevel find_base_term call.

Diff:
---
 gcc/ChangeLog  | 7 +++++++
 gcc/alias.c    | 3 +++
 gcc/params.opt | 4 ++++
 3 files changed, 14 insertions(+)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 2bc6f39b014..c9c4e7503c7 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2020-03-09  Jakub Jelinek  <jakub@redhat.com>
+
+	PR rtl-optimization/94045
+	* params.opt (-param=max-find-base-term-values=): New option.
+	* alias.c (find_base_term): Add cut-off for number of visited VALUEs
+	in a single toplevel find_base_term call.
+
 2020-03-06  Wilco Dijkstra  <wdijkstr@arm.com>
 
 	PR target/91598
diff --git a/gcc/alias.c b/gcc/alias.c
index d38e386d0e8..82a27f686a5 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -2005,6 +2005,9 @@ find_base_term (rtx x, vec<std::pair<cselib_val *,
       if (cselib_sp_based_value_p (val))
 	return static_reg_base_value[STACK_POINTER_REGNUM];
 
+      if (visited_vals.length () > (unsigned) param_max_find_base_term_values)
+	return ret;
+
       f = val->locs;
       /* Reset val->locs to avoid infinite recursion.  */
       if (f)
diff --git a/gcc/params.opt b/gcc/params.opt
index ea0c2bfc52b..e39216aa7d0 100644
--- a/gcc/params.opt
+++ b/gcc/params.opt
@@ -662,6 +662,10 @@ Max. size of loc list for which reverse ops should be added.
 Common Joined UInteger Var(param_max_vartrack_size) Init(50000000) Param Optimization
 Max. size of var tracking hash tables.
 
+-param=max-find-base-term-values=
+Common Joined UInteger Var(param_max_find_base_term_values) Init(2000) Param Optimization
+Maximum number of VALUEs handled during a single find_base_term call.
+
 -param=max-vrp-switch-assertions=
 Common Joined UInteger Var(param_max_vrp_switch_assertions) Init(10) Param Optimization
 Maximum number of assertions to add along the default edge of a switch statement during VRP.