backwards threader cleanups

backwards threader cleanups

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 434 bytes --]

Hi.

Attached are misc cleanups to tree-ssa-threadbackwards.c and friends.
The main gist of the patch is making the path vectors live in the
heap, not GC.  But I also cleaned up some comments to reflect reality,
and renamed VAR_BB which could use a more meaningful name.  Finally, I
abstracted some common code to
register_jump_thread_path_if_profitable() in preparation for some
upcoming work by me :).

Tested on x86-64 Linux.

OK?

[-- Attachment #2: curr --]
[-- Type: application/octet-stream, Size: 22666 bytes --]

gcc/

	* tree-ssa-threadbackward.c (fsm_find_thread_path): Make GC
	vectors heap vectors.  Clean up comments.
	(profitable_jump_thread_path): Same.
	Misc cleanups.
	(convert_and_register_jump_thread_path): Make GC vectors heap
	vectors.
	(check_subpath_and_update_thread_path): Same.  Clean up comments.
	(handle_phi): Abstract common code to to
	register_jump_thread_path_if_profitable.
	Rename VAR_BB to DEF_BB.
	Update comments.
	Make GC vectors heap vectors.
	(handle_assignment): Same.
	(register_jump_thread_path_if_profitable): New.
	(fsm_find_control_statement_thread_paths): Rename VAR_BB to
	DEF_BB.
	Make GC
	vectors heap vectors.  Clean up comments.
	* tree-ssa-threadupdate.c (delete_jump_thread_path): Fix typo in
	comment.

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 24def1deed9..73105c9c387 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -59,14 +59,15 @@ get_gimple_control_stmt (basic_block bb)
   return NULL;
 }
 
-/* Return true if the CFG contains at least one path from START_BB to END_BB.
-   When a path is found, record in PATH the blocks from END_BB to START_BB.
-   VISITED_BBS is used to make sure we don't fall into an infinite loop.  Bound
-   the recursion to basic blocks belonging to LOOP.  */
+/* Return true if the CFG contains at least one path from START_BB to
+   END_BB.  When a path is found, record in PATH the blocks from
+   END_BB to START_BB.  VISITED_BBS is used to make sure we don't fall
+   into an infinite loop.  Bound the recursion to basic blocks
+   belonging to LOOP.  */
 
 static bool
 fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
-		      vec<basic_block, va_gc> *&path,
+		      vec<basic_block> &path,
 		      hash_set<basic_block> *visited_bbs, loop_p loop)
 {
   if (loop != start_bb->loop_father)
@@ -74,7 +75,7 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
 
   if (start_bb == end_bb)
     {
-      vec_safe_push (path, start_bb);
+      path.safe_push (start_bb);
       return true;
     }
 
@@ -85,7 +86,7 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
       FOR_EACH_EDGE (e, ei, start_bb->succs)
 	if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop))
 	  {
-	    vec_safe_push (path, start_bb);
+	    path.safe_push (start_bb);
 	    return true;
 	  }
     }
@@ -99,21 +100,21 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
    final taken edge from the path, NULL otherwise.
 
    NAME is the SSA_NAME of the variable we found to have a constant
-   value on PATH.  ARG is the value of that SSA_NAME.
+   value on PATH.  ARG is the constant value of NAME on that path.
 
    BBI will be appended to PATH when we have a profitable jump threading
    path.  Callers are responsible for removing BBI from PATH in that case.
 
-   SPEED_P indicate that we could increase code size to improve the code path */
+   SPEED_P indicate that we could increase code size to improve the
+   code path.  */
 
 static edge
-profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
-			     basic_block bbi, tree name, tree arg, bool speed_p,
-			     bool *creates_irreducible_loop)
+profitable_jump_thread_path (vec<basic_block> &path,
+			     basic_block bbi, tree name, tree arg,
+			     bool speed_p, bool *creates_irreducible_loop)
 {
   /* Note BBI is not in the path yet, hence the +1 in the test below
      to make sure BBI is accounted for in the path length test.  */
-  int path_length = path->length ();
 
   /* We can get a length of 0 here when the statement that
      makes a conditional generate a compile-time constant
@@ -124,10 +125,10 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
      wanted by wiring up all the incoming edges.  If we run this
      early in IPA, that might be worth doing.   For now we just
      reject that case.  */
-  if (path_length == 0)
+  if (path.is_empty ())
       return NULL;
 
-  if (path_length + 1 > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
+  if (path.length () + 1 > (unsigned) PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "FSM jump-thread path not considered: "
@@ -148,13 +149,11 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
   /* Add BBI to the path.
      From this point onward, if we decide we the path is not profitable
      to thread, we must remove BBI from the path.  */
-  vec_safe_push (path, bbi);
-  ++path_length;
+  path.safe_push (bbi);
 
   int n_insns = 0;
   gimple_stmt_iterator gsi;
-  int j;
-  loop_p loop = (*path)[0]->loop_father;
+  loop_p loop = path[0]->loop_father;
   bool path_crosses_loops = false;
   bool threaded_through_latch = false;
   bool multiway_branch_in_path = false;
@@ -168,9 +167,9 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
      will have to be duplicated, we will not record the path if there
      are too many instructions on the path.  Also check that all the
      blocks in the path belong to a single loop.  */
-  for (j = 0; j < path_length; j++)
+  for (unsigned j = 0; j < path.length (); j++)
     {
-      basic_block bb = (*path)[j];
+      basic_block bb = path[j];
 
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, " bb:%i", bb->index);
@@ -181,7 +180,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	 loop father, nor how many statements are in that block because
 	 it will not be copied or whether or not it ends in a multiway
 	 branch.  */
-      if (j < path_length - 1)
+      if (j < path.length () - 1)
 	{
 	  int orig_n_insns = n_insns;
 	  if (bb->loop_father != loop)
@@ -268,7 +267,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	threaded_through_latch = true;
     }
 
-  gimple *stmt = get_gimple_control_stmt ((*path)[0]);
+  gimple *stmt = get_gimple_control_stmt (path[0]);
   gcc_assert (stmt);
 
   /* We are going to remove the control statement at the end of the
@@ -301,14 +300,14 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
      latch, then this thread would create an irreducible loop.
 
      We have to know the outgoing edge to figure this out.  */
-  edge taken_edge = find_taken_edge ((*path)[0], arg);
+  edge taken_edge = find_taken_edge (path[0], arg);
 
   /* There are cases where we may not be able to extract the
      taken edge.  For example, a computed goto to an absolute
      address.  Handle those cases gracefully.  */
   if (taken_edge == NULL)
     {
-      path->pop ();
+      path.pop ();
       return NULL;
     }
 
@@ -324,7 +323,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "FSM jump-thread path not considered: "
 		 "the path crosses loops.\n");
-      path->pop ();
+      path.pop ();
       return NULL;
     }
 
@@ -340,7 +339,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	    fprintf (dump_file, "FSM jump-thread path not considered: "
 		     "the number of instructions on the path "
 		     "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
-	  path->pop ();
+	  path.pop ();
 	  return NULL;
 	}
     }
@@ -350,7 +349,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	fprintf (dump_file, "FSM jump-thread path not considered: "
 		 "duplication of %i insns is needed and optimizing for size.\n",
 		 n_insns);
-      path->pop ();
+      path.pop ();
       return NULL;
     }
 
@@ -364,15 +363,16 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
      optimizer would have done anyway, so an irreducible loop is not
      so bad.  */
   if (!threaded_multiway_branch && *creates_irreducible_loop
-      && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
-	  > path_length * PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS)))
+      && (n_insns * (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
+	  > (path.length () *
+	     (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS))))
 
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
 		 "FSM would create irreducible loop without threading "
 		 "multiway branch.\n");
-      path->pop ();
+      path.pop ();
       return NULL;
     }
 
@@ -392,7 +392,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	fprintf (dump_file,
 		 "FSM did not thread around loop and would copy too "
 		 "many statements.\n");
-      path->pop ();
+      path.pop ();
       return NULL;
     }
 
@@ -406,7 +406,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	fprintf (dump_file,
 		 "FSM Thread through multiway branch without threading "
 		 "a multiway branch.\n");
-      path->pop ();
+      path.pop ();
       return NULL;
     }
   return taken_edge;
@@ -419,16 +419,15 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
    register the path.   */
 
 static void
-convert_and_register_jump_thread_path (vec<basic_block, va_gc> *path,
-				       edge taken_edge)
+convert_and_register_jump_thread_path (vec<basic_block> &path, edge taken_edge)
 {
   vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> ();
 
   /* Record the edges between the blocks in PATH.  */
-  for (unsigned int j = 0; j < path->length () - 1; j++)
+  for (unsigned int j = 0; j + 1 < path.length (); j++)
     {
-      basic_block bb1 = (*path)[path->length () - j - 1];
-      basic_block bb2 = (*path)[path->length () - j - 2];
+      basic_block bb1 = path[path.length () - j - 1];
+      basic_block bb2 = path[path.length () - j - 2];
 
       edge e = find_edge (bb1, bb2);
       gcc_assert (e);
@@ -445,26 +444,27 @@ convert_and_register_jump_thread_path (vec<basic_block, va_gc> *path,
   --max_threaded_paths;
 }
 
-/* While following a chain of SSA_NAME definitions, we jumped from a definition
-   in LAST_BB to a definition in VAR_BB (walking backwards).
+/* While following a chain of SSA_NAME definitions, we jumped from a
+   definition in LAST_BB to a definition in NEW_BB (walking
+   backwards).
 
-   Verify there is a single path between the blocks and none of the blocks
-   in the path is already in VISITED_BBS.  If so, then update VISISTED_BBS,
-   add the new blocks to PATH and return TRUE.  Otherwise return FALSE.
+   Verify there is a single path between the blocks and none of the
+   blocks in the path is already in VISITED_BBS.  If so, then update
+   VISISTED_BBS, add the new blocks to PATH and return TRUE.
+   Otherwise return FALSE.
 
    Store the length of the subpath in NEXT_PATH_LENGTH.  */
 
 static bool
 check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb,
 				      hash_set<basic_block> *visited_bbs,
-				      vec<basic_block, va_gc> *&path,
+				      vec<basic_block> &path,
 				      int *next_path_length)
 {
   edge e;
   int e_count = 0;
   edge_iterator ei;
-  vec<basic_block, va_gc> *next_path;
-  vec_alloc (next_path, 10);
+  vec<basic_block> next_path = vNULL;
 
   FOR_EACH_EDGE (e, ei, last_bb->preds)
     {
@@ -479,7 +479,7 @@ check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb,
       /* If there is more than one path, stop.  */
       if (e_count > 1)
 	{
-	  vec_free (next_path);
+	  next_path.release ();
 	  return false;
 	}
     }
@@ -488,39 +488,72 @@ check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb,
      is stopped by one of the bounds.  */
   if (e_count == 0)
     {
-      vec_free (next_path);
+      next_path.release ();
       return false;
     }
 
   /* Make sure we haven't already visited any of the nodes in
      NEXT_PATH.  Don't add them here to avoid pollution.  */
-  for (unsigned int i = 0; i < next_path->length () - 1; i++)
+  for (unsigned int i = 0; i + 1 < next_path.length (); i++)
     {
-      if (visited_bbs->contains ((*next_path)[i]))
+      if (visited_bbs->contains (next_path[i]))
 	{
-	  vec_free (next_path);
+	  next_path.release ();
 	  return false;
 	}
     }
 
   /* Now add the nodes to VISISTED_BBS.  */
-  for (unsigned int i = 0; i < next_path->length () - 1; i++)
-    visited_bbs->add ((*next_path)[i]);
+  for (unsigned int i = 0; i + 1 < next_path.length (); i++)
+    visited_bbs->add (next_path[i]);
 
   /* Append all the nodes from NEXT_PATH to PATH.  */
-  vec_safe_splice (path, next_path);
-  *next_path_length = next_path->length ();
-  vec_free (next_path);
+  path.safe_splice (next_path);
+  *next_path_length = next_path.length ();
+  next_path.release ();
 
   return true;
 }
 
+/* If this is a profitable jump thread path, register it.
+
+   NAME is an SSA NAME with a possible constant value of ARG on PATH.
+
+   DEF_BB is the basic block that ultimately defines the constant.
+
+   SPEED_P indicate that we could increase code size to improve the
+   code path.
+*/
+
+static void
+register_jump_thread_path_if_profitable (vec<basic_block> &path,
+					 tree name,
+					 tree arg,
+					 basic_block def_bb,
+					 bool speed_p)
+{
+  if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant)
+    return;
+
+  bool irreducible = false;
+  edge taken_edge = profitable_jump_thread_path (path, def_bb, name, arg,
+						 speed_p, &irreducible);
+  if (taken_edge)
+    {
+      convert_and_register_jump_thread_path (path, taken_edge);
+      path.pop ();
+
+      if (irreducible)
+	vect_free_loop_info_assumptions (path[0]->loop_father);
+    }
+}
+
 static void fsm_find_control_statement_thread_paths (tree,
 						     hash_set<basic_block> *,
-						     vec<basic_block, va_gc> *&,
+						     vec<basic_block> &,
 						     bool, bool);
 
-/* Given PHI which defines NAME in block VAR_BB, recurse through the
+/* Given PHI which defines NAME in block DEF_BB, recurse through the
    PHI's arguments searching for paths where NAME will ultimately have
    a constant value.
 
@@ -534,9 +567,9 @@ static void fsm_find_control_statement_thread_paths (tree,
    SPEED_P indicates if we are optimizing for speed over space.  */
 
 static void
-handle_phi (gphi *phi, tree name, basic_block var_bb,
+handle_phi (gphi *phi, tree name, basic_block def_bb,
 	    hash_set<basic_block> *visited_bbs,
-	    vec<basic_block, va_gc> *&path,
+	    vec<basic_block> &path,
 	    bool seen_loop_phi, bool speed_p)
 {
   /* Iterate over the arguments of PHI.  */
@@ -546,37 +579,22 @@ handle_phi (gphi *phi, tree name, basic_block var_bb,
       basic_block bbi = gimple_phi_arg_edge (phi, i)->src;
 
       /* Skip edges pointing outside the current loop.  */
-      if (!arg || var_bb->loop_father != bbi->loop_father)
+      if (!arg || def_bb->loop_father != bbi->loop_father)
 	continue;
 
       if (TREE_CODE (arg) == SSA_NAME)
 	{
-	  vec_safe_push (path, bbi);
+	  path.safe_push (bbi);
 	  /* Recursively follow SSA_NAMEs looking for a constant
 	     definition.  */
 	  fsm_find_control_statement_thread_paths (arg, visited_bbs, path,
 						   seen_loop_phi, speed_p);
 
-	  path->pop ();
+	  path.pop ();
 	  continue;
 	}
 
-      if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant)
-	continue;
-
-      /* If this is a profitable jump thread path, then convert it
-	 into the canonical form and register it.  */
-      bool irreducible = false;
-      edge taken_edge = profitable_jump_thread_path (path, bbi, name, arg,
-						     speed_p, &irreducible);
-      if (taken_edge)
-	{
-	  convert_and_register_jump_thread_path (path, taken_edge);
-	  path->pop ();
-
-	  if (irreducible)
-	    vect_free_loop_info_assumptions ((*path)[0]->loop_father);
-	}
+      register_jump_thread_path_if_profitable (path, name, arg, bbi, speed_p);
     }
 }
 
@@ -610,7 +628,7 @@ handle_assignment_p (gimple *stmt)
   return false;
 }
 
-/* Given STMT which defines NAME in block VAR_BB, recurse through the
+/* Given STMT which defines NAME in block DEF_BB, recurse through the
    PHI's arguments searching for paths where NAME will ultimately have
    a constant value.
 
@@ -624,9 +642,9 @@ handle_assignment_p (gimple *stmt)
    SPEED_P indicates if we are optimizing for speed over space.  */
 
 static void
-handle_assignment (gimple *stmt, tree name, basic_block var_bb,
+handle_assignment (gimple *stmt, tree name, basic_block def_bb,
 		   hash_set<basic_block> *visited_bbs,
-		   vec<basic_block, va_gc> *&path,
+		   vec<basic_block> &path,
 		   bool seen_loop_phi, bool speed_p)
 {
   tree arg = gimple_assign_rhs1 (stmt);
@@ -637,40 +655,31 @@ handle_assignment (gimple *stmt, tree name, basic_block var_bb,
 
   else
     {
-      /* profitable_jump_thread_path is going to push the current
+      /* register_jump_thread_path_if_profitable will push the current
 	 block onto the path.  But the path will always have the current
 	 block at this point.  So we can just pop it.  */
-      path->pop ();
+      path.pop ();
 
-      bool irreducible = false;
-      edge taken_edge = profitable_jump_thread_path (path, var_bb,
-						     name, arg, speed_p,
-						     &irreducible);
-      if (taken_edge)
-	{
-	  convert_and_register_jump_thread_path (path, taken_edge);
-	  path->pop ();
-
-	  if (irreducible)
-	    vect_free_loop_info_assumptions ((*path)[0]->loop_father);
-	}
+      register_jump_thread_path_if_profitable (path, name, arg, def_bb,
+					       speed_p);
 
       /* And put the current block back onto the path so that the
 	 state of the stack is unchanged when we leave.  */
-      vec_safe_push (path, var_bb);
+      path.safe_push (def_bb);
     }
 }
 
-/* We trace the value of the SSA_NAME NAME back through any phi nodes looking
-   for places where it gets a constant value and save the path.  Stop after
-   having recorded MAX_PATHS jump threading paths.
+/* We trace the value of the SSA_NAME NAME back through any phi nodes
+   looking for places where it gets a constant value and save the
+   path.
 
-   SPEED_P indicate that we could increase code size to improve the code path */
+   SPEED_P indicate that we could increase code size to improve the
+   code path.  */
 
 static void
 fsm_find_control_statement_thread_paths (tree name,
 					 hash_set<basic_block> *visited_bbs,
-					 vec<basic_block, va_gc> *&path,
+					 vec<basic_block> &path,
 					 bool seen_loop_phi, bool speed_p)
 {
   /* If NAME appears in an abnormal PHI, then don't try to trace its
@@ -679,9 +688,9 @@ fsm_find_control_statement_thread_paths (tree name,
     return;
 
   gimple *def_stmt = SSA_NAME_DEF_STMT (name);
-  basic_block var_bb = gimple_bb (def_stmt);
+  basic_block def_bb = gimple_bb (def_stmt);
 
-  if (var_bb == NULL)
+  if (def_bb == NULL)
     return;
 
   /* We allow the SSA chain to contains PHIs and simple copies and constant
@@ -700,11 +709,11 @@ fsm_find_control_statement_thread_paths (tree name,
     return;
 
   /* Avoid infinite recursion.  */
-  if (visited_bbs->add (var_bb))
+  if (visited_bbs->add (def_bb))
     return;
 
   int next_path_length = 0;
-  basic_block last_bb_in_path = path->last ();
+  basic_block last_bb_in_path = path.last ();
 
   if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt))
     {
@@ -715,33 +724,33 @@ fsm_find_control_statement_thread_paths (tree name,
     }
 
   /* Following the chain of SSA_NAME definitions, we jumped from a definition in
-     LAST_BB_IN_PATH to a definition in VAR_BB.  When these basic blocks are
-     different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB.  */
-  if (var_bb != last_bb_in_path)
+     LAST_BB_IN_PATH to a definition in DEF_BB.  When these basic blocks are
+     different, append to PATH the blocks from LAST_BB_IN_PATH to DEF_BB.  */
+  if (def_bb != last_bb_in_path)
     {
-      /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path
+      /* When DEF_BB == LAST_BB_IN_PATH, then the first block in the path
 	 will already be in VISITED_BBS.  When they are not equal, then we
 	 must ensure that first block is accounted for to ensure we do not
 	 create bogus jump threading paths.  */
-      visited_bbs->add ((*path)[0]);
-      if (!check_subpath_and_update_thread_path (last_bb_in_path, var_bb,
+      visited_bbs->add (path[0]);
+      if (!check_subpath_and_update_thread_path (last_bb_in_path, def_bb,
 						 visited_bbs, path,
 						 &next_path_length))
 	return;
     }
 
-  gcc_assert (path->last () == var_bb);
+  gcc_assert (path.last () == def_bb);
 
   if (gimple_code (def_stmt) == GIMPLE_PHI)
-    handle_phi (as_a <gphi *> (def_stmt), name, var_bb,
+    handle_phi (as_a <gphi *> (def_stmt), name, def_bb,
 		visited_bbs, path, seen_loop_phi, speed_p);
   else if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
-    handle_assignment (def_stmt, name, var_bb,
+    handle_assignment (def_stmt, name, def_bb,
 		       visited_bbs, path, seen_loop_phi, speed_p);
 
   /* Remove all the nodes that we added from NEXT_PATH.  */
   if (next_path_length)
-    vec_safe_truncate (path, (path->length () - next_path_length));
+    path.truncate (path.length () - next_path_length);
 }
 
 /* Search backwards from BB looking for paths where NAME (an SSA_NAME)
@@ -749,7 +758,8 @@ fsm_find_control_statement_thread_paths (tree name,
 
    It is assumed that BB ends with a control statement and that by
    finding a path where NAME is a constant, we can thread the path.
-   SPEED_P indicate that we could increase code size to improve the code path */
+   SPEED_P indicate that we could increase code size to improve the
+   code path.  */
 
 void  
 find_jump_threads_backwards (basic_block bb, bool speed_p)
@@ -776,9 +786,8 @@ find_jump_threads_backwards (basic_block bb, bool speed_p)
   if (!name || TREE_CODE (name) != SSA_NAME)
     return;
 
-  vec<basic_block, va_gc> *bb_path;
-  vec_alloc (bb_path, 10);
-  vec_safe_push (bb_path, bb);
+  vec<basic_block> bb_path = vNULL;
+  bb_path.safe_push (bb);
   hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;
 
   max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS);
@@ -786,7 +795,7 @@ find_jump_threads_backwards (basic_block bb, bool speed_p)
 					   speed_p);
 
   delete visited_bbs;
-  vec_free (bb_path);
+  bb_path.release ();
 }
 
 namespace {
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 9da74675eef..d5d534fde04 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2588,7 +2588,7 @@ thread_through_all_blocks (bool may_peel_loop_headers)
   return retval;
 }
 
-/* Delete the jump threading path PATH.  We have to explcitly delete
+/* Delete the jump threading path PATH.  We have to explicitly delete
    each entry in the vector, then the container.  */
 
 void

Re: backwards threader cleanups

[Jeff Law]

On 09/01/2017 02:18 PM, Aldy Hernandez wrote:
> Hi.
> 
> Attached are misc cleanups to tree-ssa-threadbackwards.c and friends.
> The main gist of the patch is making the path vectors live in the
> heap, not GC.  But I also cleaned up some comments to reflect reality,
> and renamed VAR_BB which could use a more meaningful name.  Finally, I
> abstracted some common code to
> register_jump_thread_path_if_profitable() in preparation for some
> upcoming work by me :).
> 
> Tested on x86-64 Linux.
It looks like you dropped a level of indirection for path in
profitable_jump_thread_path and perhaps others that push blocks onto the
path?   Does your change from having the vectors in the GC space to the
heap also change them from embeddable vectors to a space efficient
vector?  It has to for this change to be safe.

See the discussion in vec.h

I don't recall any inherent reason we use the embedded vector layout.
It's the default which is probably why it's used here more than anything.

Otherwise the change looks good.  I think you just to make sure you're
not using the embedded layout.  Which I think is just a different type
when  you declare the vec.



Jeff

Re: backwards threader cleanups

[Trevor Saunders]

On Fri, Sep 01, 2017 at 04:18:20PM -0400, Aldy Hernandez wrote:
> Hi.
> 
> Attached are misc cleanups to tree-ssa-threadbackwards.c and friends.
> The main gist of the patch is making the path vectors live in the
> heap, not GC.  But I also cleaned up some comments to reflect reality,
> and renamed VAR_BB which could use a more meaningful name.  Finally, I
> abstracted some common code to
> register_jump_thread_path_if_profitable() in preparation for some
> upcoming work by me :).
> 
> Tested on x86-64 Linux.
> 
> OK?

 check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb,
 				      hash_set<basic_block> *visited_bbs,
-				      vec<basic_block, va_gc> *&path,
+				      vec<basic_block> &path,
 				      int *next_path_length)
 {
   edge e;
   int e_count = 0;
   edge_iterator ei;
-  vec<basic_block, va_gc> *next_path;
-  vec_alloc (next_path, 10);
+  vec<basic_block> next_path = vNULL;

I believe all paths out of this scope release next_path, so it can be
said the scope owns this vector and you could use auto_vec here.

@@ -776,9 +786,8 @@ find_jump_threads_backwards (basic_block bb, bool speed_p)
   if (!name || TREE_CODE (name) != SSA_NAME)
     return;
 
-  vec<basic_block, va_gc> *bb_path;
-  vec_alloc (bb_path, 10);
-  vec_safe_push (bb_path, bb);
+  vec<basic_block> bb_path = vNULL;

same holds here I think.

+  bb_path.safe_push (bb);
   hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;

   btw I don't see why this hash table can't be just a hash_table<> and
   live on the stack.

thanks

Trev

Re: backwards threader cleanups

[Aldy Hernandez]

On Fri, Sep 1, 2017 at 10:16 PM, Trevor Saunders <tbsaunde@tbsaunde.org> wrote:
> On Fri, Sep 01, 2017 at 04:18:20PM -0400, Aldy Hernandez wrote:
>> Hi.
>>
>> Attached are misc cleanups to tree-ssa-threadbackwards.c and friends.
>> The main gist of the patch is making the path vectors live in the
>> heap, not GC.  But I also cleaned up some comments to reflect reality,
>> and renamed VAR_BB which could use a more meaningful name.  Finally, I
>> abstracted some common code to
>> register_jump_thread_path_if_profitable() in preparation for some
>> upcoming work by me :).
>>
>> Tested on x86-64 Linux.
>>
>> OK?
>
>  check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb,
>                                       hash_set<basic_block> *visited_bbs,
> -                                     vec<basic_block, va_gc> *&path,
> +                                     vec<basic_block> &path,
>                                       int *next_path_length)
>  {
>    edge e;
>    int e_count = 0;
>    edge_iterator ei;
> -  vec<basic_block, va_gc> *next_path;
> -  vec_alloc (next_path, 10);
> +  vec<basic_block> next_path = vNULL;
>
> I believe all paths out of this scope release next_path, so it can be
> said the scope owns this vector and you could use auto_vec here.

I originally wanted plain vec<> so it could be passed around to other
work I'm doing on the threader, but I see that auto_vec<> inherits
from vec<T, va_heap>, and the default vec<> is just vec<T, va_heap,
va_heap::default_layout>.  So...it's all the same, and will work
seamlessly.

Thanks.  Will do.

>
> @@ -776,9 +786,8 @@ find_jump_threads_backwards (basic_block bb, bool speed_p)
>    if (!name || TREE_CODE (name) != SSA_NAME)
>      return;
>
> -  vec<basic_block, va_gc> *bb_path;
> -  vec_alloc (bb_path, 10);
> -  vec_safe_push (bb_path, bb);
> +  vec<basic_block> bb_path = vNULL;
>
> same holds here I think.

Will do.

>
> +  bb_path.safe_push (bb);
>    hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;
>
>    btw I don't see why this hash table can't be just a hash_table<> and
>    live on the stack.

Very good point.  Thanks.

Re: backwards threader cleanups

[Aldy Hernandez]

On Fri, Sep 1, 2017 at 6:11 PM, Jeff Law <law@redhat.com> wrote:
> On 09/01/2017 02:18 PM, Aldy Hernandez wrote:
>> Hi.
>>
>> Attached are misc cleanups to tree-ssa-threadbackwards.c and friends.
>> The main gist of the patch is making the path vectors live in the
>> heap, not GC.  But I also cleaned up some comments to reflect reality,
>> and renamed VAR_BB which could use a more meaningful name.  Finally, I
>> abstracted some common code to
>> register_jump_thread_path_if_profitable() in preparation for some
>> upcoming work by me :).
>>
>> Tested on x86-64 Linux.
> It looks like you dropped a level of indirection for path in
> profitable_jump_thread_path and perhaps others that push blocks onto the
> path?   Does your change from having the vectors in the GC space to the
> heap also change them from embeddable vectors to a space efficient
> vector?  It has to for this change to be safe.

Part of my initial motivation was eliminating the double indirection
as well as removing the out-of-line calls to vec_alloc() and
vec_whatever_push().

And yes, the default plain vector<> uses the heap:

template<typename T,
         typename A = va_heap,
         typename L = typename A::default_layout>
struct GTY((user)) vec
{
};

...and va_heap defaults to the space efficient vector:

struct va_heap
{
  typedef vl_ptr default_layout;
...
}

>
> See the discussion in vec.h
>
> I don't recall any inherent reason we use the embedded vector layout.
> It's the default which is probably why it's used here more than anything.

Just a wild guess, but this may be why:

   FIXME - Ideally, they would all be vl_ptr to encourage using regular
           instances for vectors, but the existing GTY machinery is limited
           in that it can only deal with GC objects that are pointers
           themselves.

and:

  /* Use vl_embed as the default layout for GC vectors.  Due to GTY
     limitations, GC vectors must always be pointers, so it is more
     efficient to use a pointer to the vl_embed layout, rather than
     using a pointer to a pointer as would be the case with vl_ptr.  */

>
> Otherwise the change looks good.  I think you just to make sure you're
> not using the embedded layout.  Which I think is just a different type
> when  you declare the vec.

I have made the vectors auto_vec as Trevor suggested.  As auto_vec is
just an inherited plain vec<> with some magic allocation sauce, they
can be passed around interchangeably.

I also changed the hash sets so they live on the stack as opposed to
allocating memory dynamically, at Trevor's request as well.

Bootstraps.  OK pending another round of tests?

Aldy

Re: backwards threader cleanups

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 2875 bytes --]

PING.

An this time with an actual patch ;-).
Aldy

On Sat, Sep 2, 2017 at 1:43 PM, Aldy Hernandez <aldyh@redhat.com> wrote:
> On Fri, Sep 1, 2017 at 6:11 PM, Jeff Law <law@redhat.com> wrote:
>> On 09/01/2017 02:18 PM, Aldy Hernandez wrote:
>>> Hi.
>>>
>>> Attached are misc cleanups to tree-ssa-threadbackwards.c and friends.
>>> The main gist of the patch is making the path vectors live in the
>>> heap, not GC.  But I also cleaned up some comments to reflect reality,
>>> and renamed VAR_BB which could use a more meaningful name.  Finally, I
>>> abstracted some common code to
>>> register_jump_thread_path_if_profitable() in preparation for some
>>> upcoming work by me :).
>>>
>>> Tested on x86-64 Linux.
>> It looks like you dropped a level of indirection for path in
>> profitable_jump_thread_path and perhaps others that push blocks onto the
>> path?   Does your change from having the vectors in the GC space to the
>> heap also change them from embeddable vectors to a space efficient
>> vector?  It has to for this change to be safe.
>
> Part of my initial motivation was eliminating the double indirection
> as well as removing the out-of-line calls to vec_alloc() and
> vec_whatever_push().
>
> And yes, the default plain vector<> uses the heap:
>
> template<typename T,
>          typename A = va_heap,
>          typename L = typename A::default_layout>
> struct GTY((user)) vec
> {
> };
>
> ...and va_heap defaults to the space efficient vector:
>
> struct va_heap
> {
>   typedef vl_ptr default_layout;
> ...
> }
>
>>
>> See the discussion in vec.h
>>
>> I don't recall any inherent reason we use the embedded vector layout.
>> It's the default which is probably why it's used here more than anything.
>
> Just a wild guess, but this may be why:
>
>    FIXME - Ideally, they would all be vl_ptr to encourage using regular
>            instances for vectors, but the existing GTY machinery is limited
>            in that it can only deal with GC objects that are pointers
>            themselves.
>
> and:
>
>   /* Use vl_embed as the default layout for GC vectors.  Due to GTY
>      limitations, GC vectors must always be pointers, so it is more
>      efficient to use a pointer to the vl_embed layout, rather than
>      using a pointer to a pointer as would be the case with vl_ptr.  */
>
>>
>> Otherwise the change looks good.  I think you just to make sure you're
>> not using the embedded layout.  Which I think is just a different type
>> when  you declare the vec.
>
> I have made the vectors auto_vec as Trevor suggested.  As auto_vec is
> just an inherited plain vec<> with some magic allocation sauce, they
> can be passed around interchangeably.
>
> I also changed the hash sets so they live on the stack as opposed to
> allocating memory dynamically, at Trevor's request as well.
>
> Bootstraps.  OK pending another round of tests?
>
> Aldy

[-- Attachment #2: curr --]
[-- Type: application/octet-stream, Size: 23635 bytes --]

commit feacae1edb2f70d2f7b6f1bf5730acc1671041d6
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Thu Aug 31 06:32:37 2017 -0400

            * tree-ssa-threadbackward.c (fsm_find_thread_path): Make GC
            vectors heap vectors.  Clean up comments.
            Make visited_bbs a reference.
            (profitable_jump_thread_path): Make GC
            vectors heap vectors.  Clean up comments.
            Misc cleanups.
            (convert_and_register_jump_thread_path): Make GC vectors heap
            vectors.
            (check_subpath_and_update_thread_path): Same.  Clean up comments.
            Make visited_bbs a reference.
            (handle_phi): Abstract common code to to
            register_jump_thread_path_if_profitable.
            Rename VAR_BB to DEF_BB.
            Update comments.
            Make GC vectors heap vectors.
            Make visited_bbs a reference.
            (handle_assignment): Same.
            (register_jump_thread_path_if_profitable): New.
            (fsm_find_control_statement_thread_paths): Rename VAR_BB to
            DEF_BB.
            Make GC vectors heap vectors.  Clean up comments.
            Make visited_bbs a reference.
            (find_jump_threads_backwards): Make visited_bbs live in the stack.
            * tree-ssa-threadupdate.c (delete_jump_thread_path): Fix typo in
            comment.

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 24def1deed9..12bc80350f5 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -59,33 +59,34 @@ get_gimple_control_stmt (basic_block bb)
   return NULL;
 }
 
-/* Return true if the CFG contains at least one path from START_BB to END_BB.
-   When a path is found, record in PATH the blocks from END_BB to START_BB.
-   VISITED_BBS is used to make sure we don't fall into an infinite loop.  Bound
-   the recursion to basic blocks belonging to LOOP.  */
+/* Return true if the CFG contains at least one path from START_BB to
+   END_BB.  When a path is found, record in PATH the blocks from
+   END_BB to START_BB.  VISITED_BBS is used to make sure we don't fall
+   into an infinite loop.  Bound the recursion to basic blocks
+   belonging to LOOP.  */
 
 static bool
 fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
-		      vec<basic_block, va_gc> *&path,
-		      hash_set<basic_block> *visited_bbs, loop_p loop)
+		      vec<basic_block> &path,
+		      hash_set<basic_block> &visited_bbs, loop_p loop)
 {
   if (loop != start_bb->loop_father)
     return false;
 
   if (start_bb == end_bb)
     {
-      vec_safe_push (path, start_bb);
+      path.safe_push (start_bb);
       return true;
     }
 
-  if (!visited_bbs->add (start_bb))
+  if (!visited_bbs.add (start_bb))
     {
       edge e;
       edge_iterator ei;
       FOR_EACH_EDGE (e, ei, start_bb->succs)
 	if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop))
 	  {
-	    vec_safe_push (path, start_bb);
+	    path.safe_push (start_bb);
 	    return true;
 	  }
     }
@@ -99,21 +100,21 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
    final taken edge from the path, NULL otherwise.
 
    NAME is the SSA_NAME of the variable we found to have a constant
-   value on PATH.  ARG is the value of that SSA_NAME.
+   value on PATH.  ARG is the constant value of NAME on that path.
 
    BBI will be appended to PATH when we have a profitable jump threading
    path.  Callers are responsible for removing BBI from PATH in that case.
 
-   SPEED_P indicate that we could increase code size to improve the code path */
+   SPEED_P indicate that we could increase code size to improve the
+   code path.  */
 
 static edge
-profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
-			     basic_block bbi, tree name, tree arg, bool speed_p,
-			     bool *creates_irreducible_loop)
+profitable_jump_thread_path (vec<basic_block> &path,
+			     basic_block bbi, tree name, tree arg,
+			     bool speed_p, bool *creates_irreducible_loop)
 {
   /* Note BBI is not in the path yet, hence the +1 in the test below
      to make sure BBI is accounted for in the path length test.  */
-  int path_length = path->length ();
 
   /* We can get a length of 0 here when the statement that
      makes a conditional generate a compile-time constant
@@ -124,10 +125,10 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
      wanted by wiring up all the incoming edges.  If we run this
      early in IPA, that might be worth doing.   For now we just
      reject that case.  */
-  if (path_length == 0)
+  if (path.is_empty ())
       return NULL;
 
-  if (path_length + 1 > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
+  if (path.length () + 1 > (unsigned) PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "FSM jump-thread path not considered: "
@@ -148,13 +149,11 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
   /* Add BBI to the path.
      From this point onward, if we decide we the path is not profitable
      to thread, we must remove BBI from the path.  */
-  vec_safe_push (path, bbi);
-  ++path_length;
+  path.safe_push (bbi);
 
   int n_insns = 0;
   gimple_stmt_iterator gsi;
-  int j;
-  loop_p loop = (*path)[0]->loop_father;
+  loop_p loop = path[0]->loop_father;
   bool path_crosses_loops = false;
   bool threaded_through_latch = false;
   bool multiway_branch_in_path = false;
@@ -168,9 +167,9 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
      will have to be duplicated, we will not record the path if there
      are too many instructions on the path.  Also check that all the
      blocks in the path belong to a single loop.  */
-  for (j = 0; j < path_length; j++)
+  for (unsigned j = 0; j < path.length (); j++)
     {
-      basic_block bb = (*path)[j];
+      basic_block bb = path[j];
 
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, " bb:%i", bb->index);
@@ -181,7 +180,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	 loop father, nor how many statements are in that block because
 	 it will not be copied or whether or not it ends in a multiway
 	 branch.  */
-      if (j < path_length - 1)
+      if (j < path.length () - 1)
 	{
 	  int orig_n_insns = n_insns;
 	  if (bb->loop_father != loop)
@@ -268,7 +267,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	threaded_through_latch = true;
     }
 
-  gimple *stmt = get_gimple_control_stmt ((*path)[0]);
+  gimple *stmt = get_gimple_control_stmt (path[0]);
   gcc_assert (stmt);
 
   /* We are going to remove the control statement at the end of the
@@ -301,14 +300,14 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
      latch, then this thread would create an irreducible loop.
 
      We have to know the outgoing edge to figure this out.  */
-  edge taken_edge = find_taken_edge ((*path)[0], arg);
+  edge taken_edge = find_taken_edge (path[0], arg);
 
   /* There are cases where we may not be able to extract the
      taken edge.  For example, a computed goto to an absolute
      address.  Handle those cases gracefully.  */
   if (taken_edge == NULL)
     {
-      path->pop ();
+      path.pop ();
       return NULL;
     }
 
@@ -324,7 +323,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "FSM jump-thread path not considered: "
 		 "the path crosses loops.\n");
-      path->pop ();
+      path.pop ();
       return NULL;
     }
 
@@ -340,7 +339,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	    fprintf (dump_file, "FSM jump-thread path not considered: "
 		     "the number of instructions on the path "
 		     "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
-	  path->pop ();
+	  path.pop ();
 	  return NULL;
 	}
     }
@@ -350,7 +349,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	fprintf (dump_file, "FSM jump-thread path not considered: "
 		 "duplication of %i insns is needed and optimizing for size.\n",
 		 n_insns);
-      path->pop ();
+      path.pop ();
       return NULL;
     }
 
@@ -364,15 +363,16 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
      optimizer would have done anyway, so an irreducible loop is not
      so bad.  */
   if (!threaded_multiway_branch && *creates_irreducible_loop
-      && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
-	  > path_length * PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS)))
+      && (n_insns * (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
+	  > (path.length () *
+	     (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS))))
 
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
 		 "FSM would create irreducible loop without threading "
 		 "multiway branch.\n");
-      path->pop ();
+      path.pop ();
       return NULL;
     }
 
@@ -392,7 +392,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	fprintf (dump_file,
 		 "FSM did not thread around loop and would copy too "
 		 "many statements.\n");
-      path->pop ();
+      path.pop ();
       return NULL;
     }
 
@@ -406,7 +406,7 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
 	fprintf (dump_file,
 		 "FSM Thread through multiway branch without threading "
 		 "a multiway branch.\n");
-      path->pop ();
+      path.pop ();
       return NULL;
     }
   return taken_edge;
@@ -419,16 +419,15 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
    register the path.   */
 
 static void
-convert_and_register_jump_thread_path (vec<basic_block, va_gc> *path,
-				       edge taken_edge)
+convert_and_register_jump_thread_path (vec<basic_block> &path, edge taken_edge)
 {
   vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> ();
 
   /* Record the edges between the blocks in PATH.  */
-  for (unsigned int j = 0; j < path->length () - 1; j++)
+  for (unsigned int j = 0; j + 1 < path.length (); j++)
     {
-      basic_block bb1 = (*path)[path->length () - j - 1];
-      basic_block bb2 = (*path)[path->length () - j - 2];
+      basic_block bb1 = path[path.length () - j - 1];
+      basic_block bb2 = path[path.length () - j - 2];
 
       edge e = find_edge (bb1, bb2);
       gcc_assert (e);
@@ -445,82 +444,104 @@ convert_and_register_jump_thread_path (vec<basic_block, va_gc> *path,
   --max_threaded_paths;
 }
 
-/* While following a chain of SSA_NAME definitions, we jumped from a definition
-   in LAST_BB to a definition in VAR_BB (walking backwards).
+/* While following a chain of SSA_NAME definitions, we jumped from a
+   definition in LAST_BB to a definition in NEW_BB (walking
+   backwards).
 
-   Verify there is a single path between the blocks and none of the blocks
-   in the path is already in VISITED_BBS.  If so, then update VISISTED_BBS,
-   add the new blocks to PATH and return TRUE.  Otherwise return FALSE.
+   Verify there is a single path between the blocks and none of the
+   blocks in the path is already in VISITED_BBS.  If so, then update
+   VISISTED_BBS, add the new blocks to PATH and return TRUE.
+   Otherwise return FALSE.
 
    Store the length of the subpath in NEXT_PATH_LENGTH.  */
 
 static bool
 check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb,
-				      hash_set<basic_block> *visited_bbs,
-				      vec<basic_block, va_gc> *&path,
+				      hash_set<basic_block> &visited_bbs,
+				      vec<basic_block> &path,
 				      int *next_path_length)
 {
   edge e;
   int e_count = 0;
   edge_iterator ei;
-  vec<basic_block, va_gc> *next_path;
-  vec_alloc (next_path, 10);
+  auto_vec<basic_block> next_path;
 
   FOR_EACH_EDGE (e, ei, last_bb->preds)
     {
-      hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;
+      hash_set<basic_block> visited_bbs;
 
       if (fsm_find_thread_path (new_bb, e->src, next_path, visited_bbs,
 				e->src->loop_father))
 	++e_count;
 
-      delete visited_bbs;
-
       /* If there is more than one path, stop.  */
       if (e_count > 1)
-	{
-	  vec_free (next_path);
-	  return false;
-	}
+	return false;
     }
 
   /* Stop if we have not found a path: this could occur when the recursion
      is stopped by one of the bounds.  */
   if (e_count == 0)
-    {
-      vec_free (next_path);
-      return false;
-    }
+    return false;
 
   /* Make sure we haven't already visited any of the nodes in
      NEXT_PATH.  Don't add them here to avoid pollution.  */
-  for (unsigned int i = 0; i < next_path->length () - 1; i++)
+  for (unsigned int i = 0; i + 1 < next_path.length (); i++)
     {
-      if (visited_bbs->contains ((*next_path)[i]))
-	{
-	  vec_free (next_path);
-	  return false;
-	}
+      if (visited_bbs.contains (next_path[i]))
+	return false;
     }
 
   /* Now add the nodes to VISISTED_BBS.  */
-  for (unsigned int i = 0; i < next_path->length () - 1; i++)
-    visited_bbs->add ((*next_path)[i]);
+  for (unsigned int i = 0; i + 1 < next_path.length (); i++)
+    visited_bbs.add (next_path[i]);
 
   /* Append all the nodes from NEXT_PATH to PATH.  */
-  vec_safe_splice (path, next_path);
-  *next_path_length = next_path->length ();
-  vec_free (next_path);
+  path.safe_splice (next_path);
+  *next_path_length = next_path.length ();
 
   return true;
 }
 
+/* If this is a profitable jump thread path, register it.
+
+   NAME is an SSA NAME with a possible constant value of ARG on PATH.
+
+   DEF_BB is the basic block that ultimately defines the constant.
+
+   SPEED_P indicate that we could increase code size to improve the
+   code path.
+*/
+
+static void
+register_jump_thread_path_if_profitable (vec<basic_block> &path,
+					 tree name,
+					 tree arg,
+					 basic_block def_bb,
+					 bool speed_p)
+{
+  if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant)
+    return;
+
+  bool irreducible = false;
+  edge taken_edge = profitable_jump_thread_path (path, def_bb, name, arg,
+						 speed_p, &irreducible);
+  if (taken_edge)
+    {
+      convert_and_register_jump_thread_path (path, taken_edge);
+      path.pop ();
+
+      if (irreducible)
+	vect_free_loop_info_assumptions (path[0]->loop_father);
+    }
+}
+
 static void fsm_find_control_statement_thread_paths (tree,
-						     hash_set<basic_block> *,
-						     vec<basic_block, va_gc> *&,
+						     hash_set<basic_block> &,
+						     vec<basic_block> &,
 						     bool, bool);
 
-/* Given PHI which defines NAME in block VAR_BB, recurse through the
+/* Given PHI which defines NAME in block DEF_BB, recurse through the
    PHI's arguments searching for paths where NAME will ultimately have
    a constant value.
 
@@ -534,9 +555,9 @@ static void fsm_find_control_statement_thread_paths (tree,
    SPEED_P indicates if we are optimizing for speed over space.  */
 
 static void
-handle_phi (gphi *phi, tree name, basic_block var_bb,
-	    hash_set<basic_block> *visited_bbs,
-	    vec<basic_block, va_gc> *&path,
+handle_phi (gphi *phi, tree name, basic_block def_bb,
+	    hash_set<basic_block> &visited_bbs,
+	    vec<basic_block> &path,
 	    bool seen_loop_phi, bool speed_p)
 {
   /* Iterate over the arguments of PHI.  */
@@ -546,37 +567,22 @@ handle_phi (gphi *phi, tree name, basic_block var_bb,
       basic_block bbi = gimple_phi_arg_edge (phi, i)->src;
 
       /* Skip edges pointing outside the current loop.  */
-      if (!arg || var_bb->loop_father != bbi->loop_father)
+      if (!arg || def_bb->loop_father != bbi->loop_father)
 	continue;
 
       if (TREE_CODE (arg) == SSA_NAME)
 	{
-	  vec_safe_push (path, bbi);
+	  path.safe_push (bbi);
 	  /* Recursively follow SSA_NAMEs looking for a constant
 	     definition.  */
 	  fsm_find_control_statement_thread_paths (arg, visited_bbs, path,
 						   seen_loop_phi, speed_p);
 
-	  path->pop ();
+	  path.pop ();
 	  continue;
 	}
 
-      if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant)
-	continue;
-
-      /* If this is a profitable jump thread path, then convert it
-	 into the canonical form and register it.  */
-      bool irreducible = false;
-      edge taken_edge = profitable_jump_thread_path (path, bbi, name, arg,
-						     speed_p, &irreducible);
-      if (taken_edge)
-	{
-	  convert_and_register_jump_thread_path (path, taken_edge);
-	  path->pop ();
-
-	  if (irreducible)
-	    vect_free_loop_info_assumptions ((*path)[0]->loop_father);
-	}
+      register_jump_thread_path_if_profitable (path, name, arg, bbi, speed_p);
     }
 }
 
@@ -610,7 +616,7 @@ handle_assignment_p (gimple *stmt)
   return false;
 }
 
-/* Given STMT which defines NAME in block VAR_BB, recurse through the
+/* Given STMT which defines NAME in block DEF_BB, recurse through the
    PHI's arguments searching for paths where NAME will ultimately have
    a constant value.
 
@@ -624,9 +630,9 @@ handle_assignment_p (gimple *stmt)
    SPEED_P indicates if we are optimizing for speed over space.  */
 
 static void
-handle_assignment (gimple *stmt, tree name, basic_block var_bb,
-		   hash_set<basic_block> *visited_bbs,
-		   vec<basic_block, va_gc> *&path,
+handle_assignment (gimple *stmt, tree name, basic_block def_bb,
+		   hash_set<basic_block> &visited_bbs,
+		   vec<basic_block> &path,
 		   bool seen_loop_phi, bool speed_p)
 {
   tree arg = gimple_assign_rhs1 (stmt);
@@ -637,40 +643,31 @@ handle_assignment (gimple *stmt, tree name, basic_block var_bb,
 
   else
     {
-      /* profitable_jump_thread_path is going to push the current
+      /* register_jump_thread_path_if_profitable will push the current
 	 block onto the path.  But the path will always have the current
 	 block at this point.  So we can just pop it.  */
-      path->pop ();
+      path.pop ();
 
-      bool irreducible = false;
-      edge taken_edge = profitable_jump_thread_path (path, var_bb,
-						     name, arg, speed_p,
-						     &irreducible);
-      if (taken_edge)
-	{
-	  convert_and_register_jump_thread_path (path, taken_edge);
-	  path->pop ();
-
-	  if (irreducible)
-	    vect_free_loop_info_assumptions ((*path)[0]->loop_father);
-	}
+      register_jump_thread_path_if_profitable (path, name, arg, def_bb,
+					       speed_p);
 
       /* And put the current block back onto the path so that the
 	 state of the stack is unchanged when we leave.  */
-      vec_safe_push (path, var_bb);
+      path.safe_push (def_bb);
     }
 }
 
-/* We trace the value of the SSA_NAME NAME back through any phi nodes looking
-   for places where it gets a constant value and save the path.  Stop after
-   having recorded MAX_PATHS jump threading paths.
+/* We trace the value of the SSA_NAME NAME back through any phi nodes
+   looking for places where it gets a constant value and save the
+   path.
 
-   SPEED_P indicate that we could increase code size to improve the code path */
+   SPEED_P indicate that we could increase code size to improve the
+   code path.  */
 
 static void
 fsm_find_control_statement_thread_paths (tree name,
-					 hash_set<basic_block> *visited_bbs,
-					 vec<basic_block, va_gc> *&path,
+					 hash_set<basic_block> &visited_bbs,
+					 vec<basic_block> &path,
 					 bool seen_loop_phi, bool speed_p)
 {
   /* If NAME appears in an abnormal PHI, then don't try to trace its
@@ -679,9 +676,9 @@ fsm_find_control_statement_thread_paths (tree name,
     return;
 
   gimple *def_stmt = SSA_NAME_DEF_STMT (name);
-  basic_block var_bb = gimple_bb (def_stmt);
+  basic_block def_bb = gimple_bb (def_stmt);
 
-  if (var_bb == NULL)
+  if (def_bb == NULL)
     return;
 
   /* We allow the SSA chain to contains PHIs and simple copies and constant
@@ -700,11 +697,11 @@ fsm_find_control_statement_thread_paths (tree name,
     return;
 
   /* Avoid infinite recursion.  */
-  if (visited_bbs->add (var_bb))
+  if (visited_bbs.add (def_bb))
     return;
 
   int next_path_length = 0;
-  basic_block last_bb_in_path = path->last ();
+  basic_block last_bb_in_path = path.last ();
 
   if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt))
     {
@@ -715,33 +712,33 @@ fsm_find_control_statement_thread_paths (tree name,
     }
 
   /* Following the chain of SSA_NAME definitions, we jumped from a definition in
-     LAST_BB_IN_PATH to a definition in VAR_BB.  When these basic blocks are
-     different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB.  */
-  if (var_bb != last_bb_in_path)
+     LAST_BB_IN_PATH to a definition in DEF_BB.  When these basic blocks are
+     different, append to PATH the blocks from LAST_BB_IN_PATH to DEF_BB.  */
+  if (def_bb != last_bb_in_path)
     {
-      /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path
+      /* When DEF_BB == LAST_BB_IN_PATH, then the first block in the path
 	 will already be in VISITED_BBS.  When they are not equal, then we
 	 must ensure that first block is accounted for to ensure we do not
 	 create bogus jump threading paths.  */
-      visited_bbs->add ((*path)[0]);
-      if (!check_subpath_and_update_thread_path (last_bb_in_path, var_bb,
+      visited_bbs.add (path[0]);
+      if (!check_subpath_and_update_thread_path (last_bb_in_path, def_bb,
 						 visited_bbs, path,
 						 &next_path_length))
 	return;
     }
 
-  gcc_assert (path->last () == var_bb);
+  gcc_assert (path.last () == def_bb);
 
   if (gimple_code (def_stmt) == GIMPLE_PHI)
-    handle_phi (as_a <gphi *> (def_stmt), name, var_bb,
+    handle_phi (as_a <gphi *> (def_stmt), name, def_bb,
 		visited_bbs, path, seen_loop_phi, speed_p);
   else if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
-    handle_assignment (def_stmt, name, var_bb,
+    handle_assignment (def_stmt, name, def_bb,
 		       visited_bbs, path, seen_loop_phi, speed_p);
 
   /* Remove all the nodes that we added from NEXT_PATH.  */
   if (next_path_length)
-    vec_safe_truncate (path, (path->length () - next_path_length));
+    path.truncate (path.length () - next_path_length);
 }
 
 /* Search backwards from BB looking for paths where NAME (an SSA_NAME)
@@ -749,7 +746,8 @@ fsm_find_control_statement_thread_paths (tree name,
 
    It is assumed that BB ends with a control statement and that by
    finding a path where NAME is a constant, we can thread the path.
-   SPEED_P indicate that we could increase code size to improve the code path */
+   SPEED_P indicate that we could increase code size to improve the
+   code path.  */
 
 void  
 find_jump_threads_backwards (basic_block bb, bool speed_p)
@@ -776,17 +774,13 @@ find_jump_threads_backwards (basic_block bb, bool speed_p)
   if (!name || TREE_CODE (name) != SSA_NAME)
     return;
 
-  vec<basic_block, va_gc> *bb_path;
-  vec_alloc (bb_path, 10);
-  vec_safe_push (bb_path, bb);
-  hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;
+  auto_vec<basic_block> bb_path;
+  bb_path.safe_push (bb);
+  hash_set<basic_block> visited_bbs;
 
   max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS);
   fsm_find_control_statement_thread_paths (name, visited_bbs, bb_path, false,
 					   speed_p);
-
-  delete visited_bbs;
-  vec_free (bb_path);
 }
 
 namespace {
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index 9da74675eef..d5d534fde04 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -2588,7 +2588,7 @@ thread_through_all_blocks (bool may_peel_loop_headers)
   return retval;
 }
 
-/* Delete the jump threading path PATH.  We have to explcitly delete
+/* Delete the jump threading path PATH.  We have to explicitly delete
    each entry in the vector, then the container.  */
 
 void

Re: backwards threader cleanups

[Jeff Law]

On 09/02/2017 11:43 AM, Aldy Hernandez wrote:
> On Fri, Sep 1, 2017 at 6:11 PM, Jeff Law <law@redhat.com> wrote:
>> On 09/01/2017 02:18 PM, Aldy Hernandez wrote:
>>> Hi.
>>>
>>> Attached are misc cleanups to tree-ssa-threadbackwards.c and friends.
>>> The main gist of the patch is making the path vectors live in the
>>> heap, not GC.  But I also cleaned up some comments to reflect reality,
>>> and renamed VAR_BB which could use a more meaningful name.  Finally, I
>>> abstracted some common code to
>>> register_jump_thread_path_if_profitable() in preparation for some
>>> upcoming work by me :).
>>>
>>> Tested on x86-64 Linux.
>> It looks like you dropped a level of indirection for path in
>> profitable_jump_thread_path and perhaps others that push blocks onto the
>> path?   Does your change from having the vectors in the GC space to the
>> heap also change them from embeddable vectors to a space efficient
>> vector?  It has to for this change to be safe.
> 
> Part of my initial motivation was eliminating the double indirection
> as well as removing the out-of-line calls to vec_alloc() and
> vec_whatever_push().
> 
> And yes, the default plain vector<> uses the heap:
> 
> template<typename T,
>          typename A = va_heap,
>          typename L = typename A::default_layout>
> struct GTY((user)) vec
> {
> };
> 
> ...and va_heap defaults to the space efficient vector:
> 
> struct va_heap
> {
>   typedef vl_ptr default_layout;
> ...
> }
> 
>>
>> See the discussion in vec.h
>>
>> I don't recall any inherent reason we use the embedded vector layout.
>> It's the default which is probably why it's used here more than anything.
> 
> Just a wild guess, but this may be why:
> 
>    FIXME - Ideally, they would all be vl_ptr to encourage using regular
>            instances for vectors, but the existing GTY machinery is limited
>            in that it can only deal with GC objects that are pointers
>            themselves.
> 
> and:
> 
>   /* Use vl_embed as the default layout for GC vectors.  Due to GTY
>      limitations, GC vectors must always be pointers, so it is more
>      efficient to use a pointer to the vl_embed layout, rather than
>      using a pointer to a pointer as would be the case with vl_ptr.  */
> 
>>
>> Otherwise the change looks good.  I think you just to make sure you're
>> not using the embedded layout.  Which I think is just a different type
>> when  you declare the vec.
> 
> I have made the vectors auto_vec as Trevor suggested.  As auto_vec is
> just an inherited plain vec<> with some magic allocation sauce, they
> can be passed around interchangeably.
> 
> I also changed the hash sets so they live on the stack as opposed to
> allocating memory dynamically, at Trevor's request as well.
> 
> Bootstraps.  OK pending another round of tests?
Yes.  Thanks for double-checking on the embedded vs space efficient stuff.

jeff