[Bug rtl-optimization/85180] Infinite loop in RTL DSE optimizer

["rguenth at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 43850
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=43850&action=edit
alternative patch

The most simple hash_map variant is the attached.  Comparing (-O0 optimized
cc1)
compile-time for your testcase shows

hash-map:
> /usr/bin/time ./cc1 -quiet t.c -O -I include 
13.80user 0.01system 0:13.83elapsed 99%CPU (0avgtext+0avgdata
43556maxresident)k
0inputs+144outputs (0major+7967minor)pagefaults 0swaps

vector-unwind:
> /usr/bin/time ./cc1 -quiet t.c -O -I include 
12.10user 0.01system 0:12.12elapsed 99%CPU (0avgtext+0avgdata
43656maxresident)k
0inputs+144outputs (0major+7949minor)pagefaults 0swaps

just building alias.c with -O2:

hash-map:
11.28user 0.01system 0:11.30elapsed 99%CPU (0avgtext+0avgdata
43256maxresident)k
0inputs+144outputs (0major+7855minor)pagefaults 0swaps

vector-unwind:
11.03user 0.01system 0:11.04elapsed 100%CPU (0avgtext+0avgdata
43168maxresident)k
0inputs+144outputs (0major+7872minor)pagefaults 0swaps

caching directly in an enlarged cselib_val yields in

11.03user 0.02system 0:11.05elapsed 99%CPU (0avgtext+0avgdata
43148maxresident)k
0inputs+144outputs (0major+7852minor)pagefaults 0swaps

Index: gcc/alias.c
===================================================================
--- gcc/alias.c (revision 259082)
+++ gcc/alias.c (working copy)
@@ -1939,6 +1939,9 @@ find_base_term (rtx x)
       if (cselib_sp_based_value_p (val))
        return static_reg_base_value[STACK_POINTER_REGNUM];

+      if (val->base_term != (rtx)-1)
+       return val->base_term;
+      val->base_term = NULL_RTX;
       f = val->locs;
       /* Temporarily reset val->locs to avoid infinite recursion.  */
       val->locs = NULL;
@@ -1953,6 +1956,7 @@ find_base_term (rtx x)
          break;

       val->locs = f;
+      val->base_term = ret;
       return ret;

     case LO_SUM: