introduce size limit parameter for var-tracking

[Alexandre Oliva <aoliva at redhat dot com>]

Variable tracking sometimes takes far too long to complete.  This patch
provides users with a means to tell the compiler to just give up when
dataflow analysis is taking too long (or rather too much memory, which
is correlated).

I'm undecided as to whether or not we should report the final sizes upon
success, when the parameter is given.  It was useful for finding out a
suitable default for Red Hat's gcc 4.4 branch, but reporting is not
enabled there.  Should I take it out too?

I haven't introduced a default for the trunk.  I still hope to speed up
var-tracking some more, so that we don't have to introduce a cut-off for
normal testcases, but the approach I've been working on for the last
month or so isn't working so well :-(

Ok to install?

for  gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	* params.def (PARAM_MAX_VARTRACK_SIZE): New.
	* doc/invoke.texi: Document it.
	* var-tracking.c: Include toplev.h and params.h.
	(vt_find_locations): Return bool indicating success.  Compute
	hash sizes unconditionally.  Check new parameter, report.
	(variable_tracking_main_1): Check vt_find_locations results and
	retry.  Renamed from...
	(variable_tracking_main): ... this.  New wrapper to preserve
	flag_var_tracking_assignments.
	* Makefile.in (var-tracking.o): Adjust dependencies.
	
Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi.orig	2010-01-14 03:15:48.000000000 -0200
+++ gcc/doc/invoke.texi	2010-01-14 03:28:24.000000000 -0200
@@ -8442,6 +8442,15 @@ with more basic blocks than this paramet
 motion optimization performed on them.  The default value of the
 parameter is 1000 for -O1 and 10000 for -O2 and above.
 
+@item max-vartrack-size
+Sets a maximum number of hash table slots to use during variable
+tracking dataflow analysis of any function.  If this limit is exceeded
+with variable tracking at assignments enabled, analysis for that
+function is retried without it, after removing all debug insns from
+the function.  If the limit is exceeded even without debug insns, var
+tracking analysis is completely disabled for the function.  Setting
+the parameter to zero makes it unlimited.
+
 @item min-nondebug-insn-uid
 Use uids starting at this parameter for nondebug insns.  The range below
 the parameter is reserved exclusively for debug insns created by
Index: gcc/params.def
===================================================================
--- gcc/params.def.orig	2010-01-14 03:15:48.000000000 -0200
+++ gcc/params.def	2010-01-14 03:28:17.000000000 -0200
@@ -764,6 +764,13 @@ DEFPARAM (PARAM_PREFETCH_MIN_INSN_TO_MEM
 	  "Min. ratio of insns to mem ops to enable prefetching in a loop",
 	  3, 0, 0)
 
+/* Set maximum hash table size for var tracking.  */
+
+DEFPARAM (PARAM_MAX_VARTRACK_SIZE,
+	  "max-vartrack-size",
+	  "Max. size of var tracking hash tables",
+	  0, 0, 0)
+
 /* Set minimum insn uid for non-debug insns.  */
 
 DEFPARAM (PARAM_MIN_NONDEBUG_INSN_UID,
Index: gcc/var-tracking.c
===================================================================
--- gcc/var-tracking.c.orig	2010-01-14 03:17:23.000000000 -0200
+++ gcc/var-tracking.c	2010-01-14 03:29:36.000000000 -0200
@@ -108,6 +108,8 @@
 #include "tree-pass.h"
 #include "cselib.h"
 #include "target.h"
+#include "toplev.h"
+#include "params.h"
 
 /* Type of micro operation.  */
 enum micro_operation_type
@@ -443,7 +445,7 @@ static int add_uses (rtx *, void *);
 static void add_uses_1 (rtx *, void *);
 static void add_stores (rtx, const_rtx, void *);
 static bool compute_bb_dataflow (basic_block);
-static void vt_find_locations (void);
+static bool vt_find_locations (void);
 
 static void dump_attrs_list (attrs);
 static int dump_variable_slot (void **, void *);
@@ -5495,7 +5497,7 @@ compute_bb_dataflow (basic_block bb)
 
 /* Find the locations of variables in the whole function.  */
 
-static void
+static bool
 vt_find_locations (void)
 {
   fibheap_t worklist, pending, fibheap_swap;
@@ -5506,6 +5508,8 @@ vt_find_locations (void)
   int *rc_order;
   int i;
   int htabsz = 0;
+  int htabmax = PARAM_VALUE (PARAM_MAX_VARTRACK_SIZE);
+  bool success = true;
 
   /* Compute reverse completion order of depth first search of the CFG
      so that the data-flow runs faster.  */
@@ -5527,7 +5531,7 @@ vt_find_locations (void)
     fibheap_insert (pending, bb_order[bb->index], bb);
   sbitmap_ones (in_pending);
 
-  while (!fibheap_empty (pending))
+  while (success && !fibheap_empty (pending))
     {
       fibheap_swap = pending;
       pending = worklist;
@@ -5550,11 +5554,11 @@ vt_find_locations (void)
 
 	      SET_BIT (visited, bb->index);
 
-	      if (dump_file && VTI (bb)->in.vars)
+	      if (VTI (bb)->in.vars)
 		{
 		  htabsz
-		    -= htab_size (shared_hash_htab (VTI (bb)->in.vars))
-		       + htab_size (shared_hash_htab (VTI (bb)->out.vars));
+		    -= (htab_size (shared_hash_htab (VTI (bb)->in.vars))
+			+ htab_size (shared_hash_htab (VTI (bb)->out.vars)));
 		  oldinsz
 		    = htab_elements (shared_hash_htab (VTI (bb)->in.vars));
 		  oldoutsz
@@ -5618,9 +5622,20 @@ vt_find_locations (void)
 		}
 
 	      changed = compute_bb_dataflow (bb);
-	      if (dump_file)
-		htabsz += htab_size (shared_hash_htab (VTI (bb)->in.vars))
-			  + htab_size (shared_hash_htab (VTI (bb)->out.vars));
+	      htabsz += (htab_size (shared_hash_htab (VTI (bb)->in.vars))
+			 + htab_size (shared_hash_htab (VTI (bb)->out.vars)));
+
+	      if (htabmax && htabsz > htabmax)
+		{
+		  if (MAY_HAVE_DEBUG_INSNS)
+		    inform (DECL_SOURCE_LOCATION (cfun->decl),
+			    "variable tracking size limit exceeded with debug insns, retrying without");
+		  else
+		    inform (DECL_SOURCE_LOCATION (cfun->decl),
+			    "variable tracking size limit exceeded");
+		  success = false;
+		  break;
+		}
 
 	      if (changed)
 		{
@@ -5671,7 +5686,12 @@ vt_find_locations (void)
 	}
     }
 
-  if (MAY_HAVE_DEBUG_INSNS)
+  /* ??? Remove or document.  */
+  if (success && PARAM_SET_P (PARAM_MAX_VARTRACK_SIZE))
+    inform (DECL_SOURCE_LOCATION (cfun->decl),
+	    "variable tracking size: %i", htabsz);
+
+  if (success && MAY_HAVE_DEBUG_INSNS)
     FOR_EACH_BB (bb)
       gcc_assert (VTI (bb)->flooded);
 
@@ -5682,6 +5702,8 @@ vt_find_locations (void)
   sbitmap_free (visited);
   sbitmap_free (in_worklist);
   sbitmap_free (in_pending);
+
+  return success;
 }
 
 /* Print the content of the LIST to dump file.  */
@@ -7297,7 +7319,6 @@ vt_add_function_parameters (void)
       cselib_preserve_only_values (true);
       cselib_reset_table_with_next_value (cselib_get_next_unknown_value ());
     }
-
 }
 
 /* Allocate and initialize the data structures for variable tracking
@@ -7582,9 +7603,11 @@ vt_finalize (void)
 
 /* The entry point to variable tracking pass.  */
 
-unsigned int
-variable_tracking_main (void)
+static inline unsigned int
+variable_tracking_main_1 (void)
 {
+  bool success;
+
   if (flag_var_tracking_assignments < 0)
     {
       delete_debug_insns ();
@@ -7609,7 +7632,31 @@ variable_tracking_main (void)
 	}
     }
 
-  vt_find_locations ();
+  success = vt_find_locations ();
+
+  if (!success && flag_var_tracking_assignments > 0)
+    {
+      vt_finalize ();
+
+      delete_debug_insns ();
+
+      /* This is later restored by our caller.  */
+      flag_var_tracking_assignments = 0;
+
+      vt_initialize ();
+
+      if (!frame_pointer_needed && !vt_stack_adjustments ())
+	gcc_unreachable ();
+
+      success = vt_find_locations ();
+    }
+
+  if (!success)
+    {
+      vt_finalize ();
+      vt_debug_insns_local (false);
+      return 0;
+    }
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -7623,6 +7670,19 @@ variable_tracking_main (void)
   vt_debug_insns_local (false);
   return 0;
 }
+
+unsigned int
+variable_tracking_main (void)
+{
+  unsigned int ret;
+  int save = flag_var_tracking_assignments;
+
+  ret = variable_tracking_main_1 ();
+
+  flag_var_tracking_assignments = save;
+
+  return ret;
+}
 
 static bool
 gate_handle_var_tracking (void)
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in.orig	2010-01-14 03:15:48.000000000 -0200
+++ gcc/Makefile.in	2010-01-14 03:28:17.000000000 -0200
@@ -3024,7 +3024,8 @@ regstat.o : regstat.c $(CONFIG_H) $(SYST
 var-tracking.o : var-tracking.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(RTL_H) $(TREE_H) hard-reg-set.h insn-config.h reload.h $(FLAGS_H) \
    $(BASIC_BLOCK_H) output.h sbitmap.h alloc-pool.h $(FIBHEAP_H) $(HASHTAB_H) \
-   $(REGS_H) $(EXPR_H) $(TIMEVAR_H) $(TREE_PASS_H) cselib.h $(TARGET_H)
+   $(REGS_H) $(EXPR_H) $(TIMEVAR_H) $(TREE_PASS_H) \
+   cselib.h $(TARGET_H) $(TOPLEV_H) $(PARAMS_H)
 profile.o : profile.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    $(TREE_H) $(FLAGS_H) output.h $(REGS_H) $(EXPR_H) $(FUNCTION_H) \
    $(TOPLEV_H) $(COVERAGE_H) $(TREE_FLOW_H) value-prof.h cfghooks.h \

-- 
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer