make var-tracking iteration consistent

This eliminates the visited bitmap and makes whether a to be processed
block goes to the next or the current iteration only depend on its
position in RPO order rather than on whether it was visited in the
current iteration.  As optimization single-BB iteration is processed
immediately.

2020-07-10  Richard Biener  <rguenther@suse.de>

	* var-tracking.c (bb_heap_node_t): Remove unused typedef.
	(vt_find_locations): Eliminate visited bitmap in favor of
	RPO order check.  Dump statistics about the number of
	local BB dataflow computes.

1 files changed, 115 insertions, 120 deletions

diff --git a/gcc/var-tracking.c b/gcc/var-tracking.c
index 899a5c0..cca7506 100644
--- a/gcc/var-tracking.c
+++ b/gcc/var-tracking.c
@@ -118,7 +118,6 @@
 #include "function-abi.h"
 
 typedef fibonacci_heap <long, basic_block_def> bb_heap_t;
-typedef fibonacci_node <long, basic_block_def> bb_heap_node_t;
 
 /* var-tracking.c assumes that tree code with the same value as VALUE rtx code
    has no chance to appear in REG_EXPR/MEM_EXPRs and isn't a decl.
@@ -7078,6 +7077,7 @@ vt_find_locations (void)
   int htabsz = 0;
   int htabmax = param_max_vartrack_size;
   bool success = true;
+  unsigned int n_blocks_processed = 0;
 
   timevar_push (TV_VAR_TRACKING_DATAFLOW);
   /* Compute reverse completion order of depth first search of the CFG
@@ -7089,7 +7089,6 @@ vt_find_locations (void)
     bb_order[rc_order[i]] = i;
   free (rc_order);
 
-  auto_sbitmap visited (last_basic_block_for_fn (cfun));
   in_worklist = sbitmap_alloc (last_basic_block_for_fn (cfun));
   in_pending = sbitmap_alloc (last_basic_block_for_fn (cfun));
   bitmap_clear (in_worklist);
@@ -7103,154 +7102,150 @@ vt_find_locations (void)
       std::swap (worklist, pending);
       std::swap (in_worklist, in_pending);
 
-      bitmap_clear (visited);
-
       while (!worklist->empty ())
 	{
+	  bool changed;
+	  edge_iterator ei;
+	  int oldinsz, oldoutsz;
+
 	  bb = worklist->extract_min ();
 	  bitmap_clear_bit (in_worklist, bb->index);
-	  gcc_assert (!bitmap_bit_p (visited, bb->index));
-	  if (!bitmap_bit_p (visited, bb->index))
+
+	  if (VTI (bb)->in.vars)
 	    {
-	      bool changed;
-	      edge_iterator ei;
-	      int oldinsz, oldoutsz;
+	      htabsz -= (shared_hash_htab (VTI (bb)->in.vars)->size ()
+			 + shared_hash_htab (VTI (bb)->out.vars)->size ());
+	      oldinsz = shared_hash_htab (VTI (bb)->in.vars)->elements ();
+	      oldoutsz = shared_hash_htab (VTI (bb)->out.vars)->elements ();
+	    }
+	  else
+	    oldinsz = oldoutsz = 0;
 
-	      bitmap_set_bit (visited, bb->index);
+	  if (MAY_HAVE_DEBUG_BIND_INSNS)
+	    {
+	      dataflow_set *in = &VTI (bb)->in, *first_out = NULL;
+	      bool first = true, adjust = false;
 
-	      if (VTI (bb)->in.vars)
-		{
-		  htabsz
-		    -= shared_hash_htab (VTI (bb)->in.vars)->size ()
-			+ shared_hash_htab (VTI (bb)->out.vars)->size ();
-		  oldinsz = shared_hash_htab (VTI (bb)->in.vars)->elements ();
-		  oldoutsz
-		    = shared_hash_htab (VTI (bb)->out.vars)->elements ();
-		}
-	      else
-		oldinsz = oldoutsz = 0;
+	      /* Calculate the IN set as the intersection of
+		 predecessor OUT sets.  */
 
-	      if (MAY_HAVE_DEBUG_BIND_INSNS)
-		{
-		  dataflow_set *in = &VTI (bb)->in, *first_out = NULL;
-		  bool first = true, adjust = false;
+	      dataflow_set_clear (in);
+	      dst_can_be_shared = true;
 
-		  /* Calculate the IN set as the intersection of
-		     predecessor OUT sets.  */
+	      FOR_EACH_EDGE (e, ei, bb->preds)
+		if (!VTI (e->src)->flooded)
+		  gcc_assert (bb_order[bb->index]
+			      <= bb_order[e->src->index]);
+		else if (first)
+		  {
+		    dataflow_set_copy (in, &VTI (e->src)->out);
+		    first_out = &VTI (e->src)->out;
+		    first = false;
+		  }
+		else
+		  {
+		    dataflow_set_merge (in, &VTI (e->src)->out);
+		    adjust = true;
+		  }
 
-		  dataflow_set_clear (in);
-		  dst_can_be_shared = true;
+	      if (adjust)
+		{
+		  dataflow_post_merge_adjust (in, &VTI (bb)->permp);
 
-		  FOR_EACH_EDGE (e, ei, bb->preds)
-		    if (!VTI (e->src)->flooded)
-		      gcc_assert (bb_order[bb->index]
-				  <= bb_order[e->src->index]);
-		    else if (first)
-		      {
-			dataflow_set_copy (in, &VTI (e->src)->out);
-			first_out = &VTI (e->src)->out;
-			first = false;
-		      }
-		    else
-		      {
-			dataflow_set_merge (in, &VTI (e->src)->out);
-			adjust = true;
-		      }
+		  if (flag_checking)
+		    /* Merge and merge_adjust should keep entries in
+		       canonical order.  */
+		    shared_hash_htab (in->vars)
+		      ->traverse <dataflow_set *,
+				  canonicalize_loc_order_check> (in);
 
-		  if (adjust)
+		  if (dst_can_be_shared)
 		    {
-		      dataflow_post_merge_adjust (in, &VTI (bb)->permp);
+		      shared_hash_destroy (in->vars);
+		      in->vars = shared_hash_copy (first_out->vars);
+		    }
+		}
 
-		      if (flag_checking)
-			/* Merge and merge_adjust should keep entries in
-			   canonical order.  */
-			shared_hash_htab (in->vars)
-			  ->traverse <dataflow_set *,
-				      canonicalize_loc_order_check> (in);
+	      VTI (bb)->flooded = true;
+	    }
+	  else
+	    {
+	      /* Calculate the IN set as union of predecessor OUT sets.  */
+	      dataflow_set_clear (&VTI (bb)->in);
+	      FOR_EACH_EDGE (e, ei, bb->preds)
+		dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
+	    }
 
-		      if (dst_can_be_shared)
-			{
-			  shared_hash_destroy (in->vars);
-			  in->vars = shared_hash_copy (first_out->vars);
-			}
-		    }
+	  changed = compute_bb_dataflow (bb);
+	  n_blocks_processed++;
+	  htabsz += (shared_hash_htab (VTI (bb)->in.vars)->size ()
+		     + shared_hash_htab (VTI (bb)->out.vars)->size ());
 
-		  VTI (bb)->flooded = true;
-		}
+	  if (htabmax && htabsz > htabmax)
+	    {
+	      if (MAY_HAVE_DEBUG_BIND_INSNS)
+		inform (DECL_SOURCE_LOCATION (cfun->decl),
+			"variable tracking size limit exceeded with "
+			"%<-fvar-tracking-assignments%>, retrying without");
 	      else
-		{
-		  /* Calculate the IN set as union of predecessor OUT sets.  */
-		  dataflow_set_clear (&VTI (bb)->in);
-		  FOR_EACH_EDGE (e, ei, bb->preds)
-		    dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
-		}
-
-	      changed = compute_bb_dataflow (bb);
-	      htabsz += shared_hash_htab (VTI (bb)->in.vars)->size ()
-			 + shared_hash_htab (VTI (bb)->out.vars)->size ();
+		inform (DECL_SOURCE_LOCATION (cfun->decl),
+			"variable tracking size limit exceeded");
+	      success = false;
+	      break;
+	    }
 
-	      if (htabmax && htabsz > htabmax)
+	  if (changed)
+	    {
+	      FOR_EACH_EDGE (e, ei, bb->succs)
 		{
-		  if (MAY_HAVE_DEBUG_BIND_INSNS)
-		    inform (DECL_SOURCE_LOCATION (cfun->decl),
-			    "variable tracking size limit exceeded with "
-			    "%<-fvar-tracking-assignments%>, retrying without");
-		  else
-		    inform (DECL_SOURCE_LOCATION (cfun->decl),
-			    "variable tracking size limit exceeded");
-		  success = false;
-		  break;
-		}
+		  if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
+		    continue;
 
-	      if (changed)
-		{
-		  FOR_EACH_EDGE (e, ei, bb->succs)
+		  /* Iterate to an earlier block in RPO in the next
+		     round, iterate to the same block immediately.  */
+		  if (bb_order[e->dest->index] < bb_order[bb->index])
 		    {
-		      if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
-			continue;
-
-		      if (bitmap_bit_p (visited, e->dest->index))
+		      if (!bitmap_bit_p (in_pending, e->dest->index))
 			{
-			  if (!bitmap_bit_p (in_pending, e->dest->index))
-			    {
-			      /* Send E->DEST to next round.  */
-			      bitmap_set_bit (in_pending, e->dest->index);
-			      pending->insert (bb_order[e->dest->index],
-					       e->dest);
-			    }
-			}
-		      else if (!bitmap_bit_p (in_worklist, e->dest->index))
-			{
-			  /* Add E->DEST to current round.  */
-			  bitmap_set_bit (in_worklist, e->dest->index);
-			  worklist->insert (bb_order[e->dest->index],
-					    e->dest);
+			  /* Send E->DEST to next round.  */
+			  bitmap_set_bit (in_pending, e->dest->index);
+			  pending->insert (bb_order[e->dest->index],
+					   e->dest);
 			}
 		    }
+		  else if (!bitmap_bit_p (in_worklist, e->dest->index))
+		    {
+		      /* Add E->DEST to current round.  */
+		      bitmap_set_bit (in_worklist, e->dest->index);
+		      worklist->insert (bb_order[e->dest->index],
+					e->dest);
+		    }
 		}
+	    }
 
-	      if (dump_file)
-		fprintf (dump_file,
-			 "BB %i: in %i (was %i), out %i (was %i), rem %i + %i, tsz %i\n",
-			 bb->index,
-			 (int)shared_hash_htab (VTI (bb)->in.vars)->size (),
-			 oldinsz,
-			 (int)shared_hash_htab (VTI (bb)->out.vars)->size (),
-			 oldoutsz,
-			 (int)worklist->nodes (), (int)pending->nodes (),
-			 htabsz);
-
-	      if (dump_file && (dump_flags & TDF_DETAILS))
-		{
-		  fprintf (dump_file, "BB %i IN:\n", bb->index);
-		  dump_dataflow_set (&VTI (bb)->in);
-		  fprintf (dump_file, "BB %i OUT:\n", bb->index);
-		  dump_dataflow_set (&VTI (bb)->out);
-		}
+	  if (dump_file)
+	    fprintf (dump_file,
+		     "BB %i: in %i (was %i), out %i (was %i), rem %i + %i, tsz %i\n",
+		     bb->index,
+		     (int)shared_hash_htab (VTI (bb)->in.vars)->size (),
+		     oldinsz,
+		     (int)shared_hash_htab (VTI (bb)->out.vars)->size (),
+		     oldoutsz,
+		     (int)worklist->nodes (), (int)pending->nodes (), htabsz);
+
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "BB %i IN:\n", bb->index);
+	      dump_dataflow_set (&VTI (bb)->in);
+	      fprintf (dump_file, "BB %i OUT:\n", bb->index);
+	      dump_dataflow_set (&VTI (bb)->out);
 	    }
 	}
     }
 
+  statistics_counter_event (cfun, "compute_bb_dataflow times",
+			    n_blocks_processed);
+
   if (success && MAY_HAVE_DEBUG_BIND_INSNS)
     FOR_EACH_BB_FN (bb, cfun)
       gcc_assert (VTI (bb)->flooded);