[gcc r14-61] rtl-optimization/109237 - quadraticness in delete_trivially_dead_insns

[gcc r14-61] rtl-optimization/109237 - quadraticness in delete_trivially_dead_insns

[Richard Biener]

https://gcc.gnu.org/g:675ac8822b51a39f6a66a44858d7c31ece8700f2

commit r14-61-g675ac8822b51a39f6a66a44858d7c31ece8700f2
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Mar 22 09:29:49 2023 +0100

    rtl-optimization/109237 - quadraticness in delete_trivially_dead_insns
    
    The following addresses quadraticness in processing debug insns
    in delete_trivially_dead_insns and insn_live_p by using TREE_VISITED
    on the INSN_VAR_LOCATION_DECL to indicate a later debug bind
    with the same decl and no intervening real insn or debug marker.
    That gets rid of the NEXT_INSN walk in insn_live_p in favor of
    first clearing TREE_VISITED in the first loop over insn and
    the book-keeping of decls we set the bit since we need to clear
    them when visiting a real or debug marker insn.
    
    That improves the time spent in delete_trivially_dead_insns from
    10.6s to 2.2s for the testcase.
    
            PR rtl-optimization/109237
            * cse.cc (insn_live_p): Remove NEXT_INSN walk, instead check
            TREE_VISITED on INSN_VAR_LOCATION_DECL.
            (delete_trivially_dead_insns): Maintain TREE_VISITED on
            active debug bind INSN_VAR_LOCATION_DECL.

Diff:
---
 gcc/cse.cc | 39 ++++++++++++++++++++++++---------------
 1 file changed, 24 insertions(+), 15 deletions(-)

diff --git a/gcc/cse.cc b/gcc/cse.cc
index 8fbda4ecc86..204047b0e0b 100644
--- a/gcc/cse.cc
+++ b/gcc/cse.cc
@@ -6906,22 +6906,12 @@ insn_live_p (rtx_insn *insn, int *counts)
     }
   else if (DEBUG_INSN_P (insn))
     {
-      rtx_insn *next;
-
       if (DEBUG_MARKER_INSN_P (insn))
 	return true;
 
-      for (next = NEXT_INSN (insn); next; next = NEXT_INSN (next))
-	if (NOTE_P (next))
-	  continue;
-	else if (!DEBUG_INSN_P (next))
-	  return true;
-	/* If we find an inspection point, such as a debug begin stmt,
-	   we want to keep the earlier debug insn.  */
-	else if (DEBUG_MARKER_INSN_P (next))
-	  return true;
-	else if (INSN_VAR_LOCATION_DECL (insn) == INSN_VAR_LOCATION_DECL (next))
-	  return false;
+      if (DEBUG_BIND_INSN_P (insn)
+	  && TREE_VISITED (INSN_VAR_LOCATION_DECL (insn)))
+	return false;
 
       return true;
     }
@@ -7007,8 +6997,11 @@ delete_trivially_dead_insns (rtx_insn *insns, int nreg)
       counts = XCNEWVEC (int, nreg * 3);
       for (insn = insns; insn; insn = NEXT_INSN (insn))
 	if (DEBUG_BIND_INSN_P (insn))
-	  count_reg_usage (INSN_VAR_LOCATION_LOC (insn), counts + nreg,
-			   NULL_RTX, 1);
+	  {
+	    count_reg_usage (INSN_VAR_LOCATION_LOC (insn), counts + nreg,
+			     NULL_RTX, 1);
+	    TREE_VISITED (INSN_VAR_LOCATION_DECL (insn)) = 0;
+	  }
 	else if (INSN_P (insn))
 	  {
 	    count_reg_usage (insn, counts, NULL_RTX, 1);
@@ -7048,6 +7041,7 @@ delete_trivially_dead_insns (rtx_insn *insns, int nreg)
      the setter.  Then go through DEBUG_INSNs and if a DEBUG_EXPR
      has been created for the unused register, replace it with
      the DEBUG_EXPR, otherwise reset the DEBUG_INSN.  */
+  auto_vec<tree, 32> later_debug_set_vars;
   for (insn = get_last_insn (); insn; insn = prev)
     {
       int live_insn = 0;
@@ -7110,6 +7104,21 @@ delete_trivially_dead_insns (rtx_insn *insns, int nreg)
 	    }
 	  cse_cfg_altered |= delete_insn_and_edges (insn);
 	}
+      else
+	{
+	  if (!DEBUG_INSN_P (insn) || DEBUG_MARKER_INSN_P (insn))
+	    {
+	      for (tree var : later_debug_set_vars)
+		TREE_VISITED (var) = 0;
+	      later_debug_set_vars.truncate (0);
+	    }
+	  else if (DEBUG_BIND_INSN_P (insn)
+		   && !TREE_VISITED (INSN_VAR_LOCATION_DECL (insn)))
+	    {
+	      later_debug_set_vars.safe_push (INSN_VAR_LOCATION_DECL (insn));
+	      TREE_VISITED (INSN_VAR_LOCATION_DECL (insn)) = 1;
+	    }
+	}
     }
 
   if (MAY_HAVE_DEBUG_BIND_INSNS)