CbC/CbC_gcc: gcc/tree-ssa-coalesce.c comparison

comparison gcc/tree-ssa-coalesce.c @ 55:77e2b8dfacca gcc-4.4.5

update it from 4.4.3 to 4.5.0

author	ryoma <e075725@ie.u-ryukyu.ac.jp>
date	Fri, 12 Feb 2010 23:39:51 +0900
parents	a06113de4d67
children	b7f97abdc517

comparison

equal deleted inserted replaced

-:c156f1bd5cd9
+:77e2b8dfacca
 #include "toplev.h"
 /* This set of routines implements a coalesce_list.  This is an object which
 is used to track pairs of ssa_names which are desirable to coalesce
 together to avoid copies.  Costs are associated with each pair, and when
 all desired information has been collected, the object can be used to
 order the pairs for processing.  */
 /* This structure defines a pair entry.  */
 typedef struct coalesce_pair
 struct cost_one_pair_d *next;
 } * cost_one_pair_p;
 /* This structure maintains the list of coalesce pairs.  */
 typedef struct coalesce_list_d
 {
 htab_t list;			/* Hash table.  */
 coalesce_pair_p *sorted;	/* List when sorted.  */
 int num_sorted;		/* Number in the sorted list.  */
 cost_one_pair_p cost_one_list;/* Single use coalesces with cost 1.  */
 #define NO_BEST_COALESCE	-1
 #define MUST_COALESCE_COST	INT_MAX
-/* Return cost of execution of copy instruction with FREQUENCY
+/* Return cost of execution of copy instruction with FREQUENCY.  */
-possibly on CRITICAL edge and in HOT basic block.  */
 static inline int
-coalesce_cost (int frequency, bool optimize_for_size, bool critical)
+coalesce_cost (int frequency, bool optimize_for_size)
 {
 /* Base costs on BB frequencies bounded by 1.  */
 int cost = frequency;
 if (!cost)
 cost = 1;
 if (optimize_for_size)
 cost = 1;
+return cost;
+}
+/* Return the cost of executing a copy instruction in basic block BB.  */
+static inline int
+coalesce_cost_bb (basic_block bb)
+{
+return coalesce_cost (bb->frequency, optimize_bb_for_size_p (bb));
+}
+/* Return the cost of executing a copy instruction on edge E.  */
+static inline int
+coalesce_cost_edge (edge e)
+{
+int mult = 1;
 /* Inserting copy on critical edge costs more than inserting it elsewhere.  */
-if (critical)
+if (EDGE_CRITICAL_P (e))
-cost *= 2;
+mult = 2;
-return cost;
-}
-/* Return the cost of executing a copy instruction in basic block BB.  */
-static inline int
-coalesce_cost_bb (basic_block bb)
-{
-return coalesce_cost (bb->frequency, optimize_bb_for_size_p (bb), false);
-}
-/* Return the cost of executing a copy instruction on edge E.  */
-static inline int
-coalesce_cost_edge (edge e)
-{
 if (e->flags & EDGE_ABNORMAL)
 return MUST_COALESCE_COST;
+if (e->flags & EDGE_EH)
-return coalesce_cost (EDGE_FREQUENCY (e),
+{
-			optimize_edge_for_size_p (e),
+edge e2;
-			EDGE_CRITICAL_P (e));
+edge_iterator ei;
-}
+FOR_EACH_EDGE (e2, ei, e->dest->preds)
+	if (e2 != e)
+	  {
-/* Retrieve a pair to coalesce from the cost_one_list in CL.  Returns the
+	    /* Putting code on EH edge that leads to BB
+	       with multiple predecestors imply splitting of
+	       edge too.  */
+	    if (mult < 2)
+	      mult = 2;
+	    /* If there are multiple EH predecestors, we
+	       also copy EH regions and produce separate
+	       landing pad.  This is expensive.  */
+	    if (e2->flags & EDGE_EH)
+	      {
+	        mult = 5;
+	        break;
+	      }
+	  }
+}
+return coalesce_cost (EDGE_FREQUENCY (e),
+			optimize_edge_for_size_p (e)) * mult;
+}
+/* Retrieve a pair to coalesce from the cost_one_list in CL.  Returns the
 2 elements via P1 and P2.  1 is returned by the function if there is a pair,
 NO_BEST_COALESCE is returned if there aren't any.  */
 static inline int
 pop_cost_one_pair (coalesce_list_p cl, int *p1, int *p2)
 free (ptr);
 return 1;
 }
 /* Retrieve the most expensive remaining pair to coalesce from CL.  Returns the
 2 elements via P1 and P2.  Their calculated cost is returned by the function.
 NO_BEST_COALESCE is returned if the coalesce list is empty.  */
 static inline int
 pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2)
 #define COALESCE_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
 /* Hash function for coalesce list.  Calculate hash for PAIR.   */
 static unsigned int
 coalesce_pair_map_hash (const void *pair)
 {
 hashval_t a = (hashval_t)(((const_coalesce_pair_p)pair)->first_element);
 hashval_t b = (hashval_t)(((const_coalesce_pair_p)pair)->second_element);
 /* Equality function for coalesce list hash table.  Compare PAIR1 and PAIR2,
 returning TRUE if the two pairs are equivalent.  */
 static int
 coalesce_pair_map_eq (const void *pair1, const void *pair2)
 {
 const_coalesce_pair_p const p1 = (const_coalesce_pair_p) pair1;
 const_coalesce_pair_p const p2 = (const_coalesce_pair_p) pair2;
 }
 /* Create a new empty coalesce list object and return it.  */
 static inline coalesce_list_p
 create_coalesce_list (void)
 {
 coalesce_list_p list;
 unsigned size = num_ssa_names * 3;
 if (size < 40)
 size = 40;
 list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d));
 list->list = htab_create (size, coalesce_pair_map_hash,
 			    coalesce_pair_map_eq, NULL);
 }
 /* Delete coalesce list CL.  */
 static inline void
 delete_coalesce_list (coalesce_list_p cl)
 {
 gcc_assert (cl->cost_one_list == NULL);
 htab_delete (cl->list);
 if (cl->sorted)
 gcc_assert (cl->num_sorted == 0);
 free (cl);
 }
 /* Find a matching coalesce pair object in CL for the pair P1 and P2.  If
 one isn't found, return NULL if CREATE is false, otherwise create a new
 coalesce pair object and return it.  */
 static coalesce_pair_p
 find_coalesce_pair (coalesce_list_p cl, int p1, int p2, bool create)
 {
 struct coalesce_pair p, *pair;
 void **slot;
 unsigned int hash;
 /* Normalize so that p1 is the smaller value.  */
 if (p2 < p1)
 {
 p.first_element = p2;
 p.second_element = p1;
 else
 {
 p.first_element = p1;
 p.second_element = p2;
 }
 hash = coalesce_pair_map_hash (&p);
 pair = (struct coalesce_pair *) htab_find_with_hash (cl->list, &p, hash);
 if (create && !pair)
 {
 }
 /* Add a coalesce between P1 and P2 in list CL with a cost of VALUE.  */
 static inline void
 add_coalesce (coalesce_list_p cl, int p1, int p2, int value)
 {
 coalesce_pair_p node;
 gcc_assert (cl->sorted == NULL);
 }
 /* Comparison function to allow qsort to sort P1 and P2 in Ascending order.  */
 static int
 compare_pairs (const void *p1, const void *p2)
 {
 const_coalesce_pair_p const *const pp1 = (const_coalesce_pair_p const *) p1;
 const_coalesce_pair_p const *const pp2 = (const_coalesce_pair_p const *) p2;
 int result;
-result = (* pp2)->cost - (* pp1)->cost;
+result = (* pp1)->cost - (* pp2)->cost;
 /* Since qsort does not guarantee stability we use the elements
 as a secondary key.  This provides us with independence from
 the host's implementation of the sorting algorithm.  */
 if (result == 0)
 {
 }
 /* Send debug info for coalesce list CL to file F.  */
 static void
 dump_coalesce_list (FILE *f, coalesce_list_p cl)
 {
 coalesce_pair_p node;
 coalesce_pair_iterator ppi;
 int x;
 	}
 }
 }
 /* This represents a conflict graph.  Implemented as an array of bitmaps.
 A full matrix is used for conflicts rather than just upper triangular form.
 this make sit much simpler and faster to perform conflict merges.  */
 typedef struct ssa_conflicts_d
 {
 	dump_bitmap (file, ptr->conflicts[x]);
 }
 }
 /* This structure is used to efficiently record the current status of live
 SSA_NAMES when building a conflict graph.
 LIVE_BASE_VAR has a bit set for each base variable which has at least one
 ssa version live.
 LIVE_BASE_PARTITIONS is an array of bitmaps using the basevar table as an
 index, and is used to track what partitions of each base variable are
 live.  This makes it easy to add conflicts between just live partitions
 with the same base variable.
 The values in LIVE_BASE_PARTITIONS are only valid if the base variable is
 marked as being live.  This delays clearing of these bitmaps until
 they are actually needed again.  */
 typedef struct live_track_d
 {
 live_track_add_partition (live_track_p ptr, int partition)
 {
 int root;
 root = basevar_index (ptr->map, partition);
 /* If this base var wasn't live before, it is now.  Clear the element list
 since it was delayed until needed.  */
 if (!bitmap_bit_p (ptr->live_base_var, root))
 {
 bitmap_set_bit (ptr->live_base_var, root);
 bitmap_clear (ptr->live_base_partitions[root]);
 }
 bitmap_set_bit (ptr->live_base_partitions[root], partition);
 }
 /* Clear the live bit for VAR in PTR.  */
 }
 return false;
 }
 /* This routine will add USE to PTR.  USE will be marked as live in both the
 ssa live map and the live bitmap for the root of USE.  */
 static inline void
 live_track_process_use (live_track_p ptr, tree use)
 {
 live_track_add_partition (ptr, p);
 }
 /* This routine will process a DEF in PTR.  DEF will be removed from the live
 lists, and if there are any other live partitions with the same base
 variable, conflicts will be added to GRAPH.  */
 static inline void
 live_track_process_def (live_track_p ptr, tree def, ssa_conflicts_p graph)
 {
 bitmap_clear (ptr->live_base_var);
 }
 /* Build a conflict graph based on LIVEINFO.  Any partitions which are in the
 partition view of the var_map liveinfo is based on get entries in the
 conflict graph.  Only conflicts between ssa_name partitions with the same
 base variable are added.  */
 static ssa_conflicts_p
 build_ssa_conflict_graph (tree_live_info_p liveinfo)
 {
 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
 {
 	  tree var;
 	  gimple stmt = gsi_stmt (gsi);
 	  /* A copy between 2 partitions does not introduce an interference
 	     by itself.  If they did, you would never be able to coalesce
 	     two things which are copied.  If the two variables really do
 	     conflict, they will conflict elsewhere in the program.
 	     This is handled by simply removing the SRC of the copy from the
 	     live list, and processing the stmt normally.  */
 	  if (is_gimple_assign (stmt))
 	    {
 	      tree lhs = gimple_assign_lhs (stmt);
 	      tree rhs1 = gimple_assign_rhs1 (stmt);
 	      if (gimple_assign_copy_p (stmt)
 && TREE_CODE (lhs) == SSA_NAME
 && TREE_CODE (rhs1) == SSA_NAME)
 		live_track_clear_var (live, rhs1);
 	    }
+	  else if (is_gimple_debug (stmt))
+	    continue;
 	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
 	    live_track_process_def (live, var, graph);
 	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
 	    live_track_process_use (live, var);
 	}
 /* If result of a PHI is unused, looping over the statements will not
 	 record any conflicts since the def was never live.  Since the PHI node
 	 is going to be translated out of SSA form, it will insert a copy.
 	 There must be a conflict recorded between the result of the PHI and
 	 any variables that are live.  Otherwise the out-of-ssa translation
 	 may create incorrect code.  */
 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 	{
 	  gimple phi = gsi_stmt (gsi);
 	  tree result = PHI_RESULT (phi);
 fprintf (f, "%s", str3);
 }
 /* Called if a coalesce across and abnormal edge cannot be performed.  PHI is
 the phi node at fault, I is the argument index at fault.  A message is
 printed and compilation is then terminated.  */
 static inline void
 abnormal_corrupt (gimple phi, int i)
 {
 used_in_real_ops = BITMAP_ALLOC (NULL);
 used_in_virtual_ops = BITMAP_ALLOC (NULL);
 #endif
-map = init_var_map (num_ssa_names + 1);
+map = init_var_map (num_ssa_names);
 FOR_EACH_BB (bb)
 {
 tree arg;
 	  res = gimple_phi_result (phi);
 	  ver = SSA_NAME_VERSION (res);
 	  register_ssa_partition (map, res);
 	  /* Register ssa_names and coalesces between the args and the result
 	     of all PHI.  */
 	  for (i = 0; i < gimple_phi_num_args (phi); i++)
 	    {
 	      edge e = gimple_phi_arg_edge (phi, i);
 	      arg = PHI_ARG_DEF (phi, i);
 	      if (TREE_CODE (arg) == SSA_NAME)
 		register_ssa_partition (map, arg);
 	      if (TREE_CODE (arg) == SSA_NAME
 		  && SSA_NAME_VAR (arg) == SSA_NAME_VAR (res))
 	        {
 		  saw_copy = true;
 		  bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (arg));
 		  if ((e->flags & EDGE_ABNORMAL) == 0)
 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 {
 	  stmt = gsi_stmt (gsi);
+	  if (is_gimple_debug (stmt))
+	    continue;
 	  /* Register USE and DEF operands in each statement.  */
 	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
 	    register_ssa_partition (map, var);
 	  /* Check for copy coalesces.  */
 		    v1 = SSA_NAME_VERSION (outputs[match]);
 		    v2 = SSA_NAME_VERSION (input);
 		    if (SSA_NAME_VAR (outputs[match]) == SSA_NAME_VAR (input))
 		      {
 			cost = coalesce_cost (REG_BR_PROB_BASE,
-					      optimize_bb_for_size_p (bb),
+					      optimize_bb_for_size_p (bb));
-					      false);
 			add_coalesce (cl, v1, v2, cost);
 			bitmap_set_bit (used_in_copy, v1);
 			bitmap_set_bit (used_in_copy, v2);
 		      }
 		  }
 	      }
 	    default:
 	      break;
 	    }
 #ifdef ENABLE_CHECKING
 	  /* Mark real uses and defs.  */
 	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, (SSA_OP_DEF|SSA_OP_USE))
 	    bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (var)));
 	  /* Validate that virtual ops don't get used in funny ways.  */
-	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_VIRTUALS)
+	  if (gimple_vuse (stmt))
-	    {
+	    bitmap_set_bit (used_in_virtual_ops,
-	      bitmap_set_bit (used_in_virtual_ops,
+			    DECL_UID (SSA_NAME_VAR (gimple_vuse (stmt))));
-			      DECL_UID (SSA_NAME_VAR (var)));
-	    }
 #endif /* ENABLE_CHECKING */
 	}
 }
 /* Now process result decls and live on entry variables for entry into
 the coalesce list.  */
 first = NULL_TREE;
 for (i = 1; i < num_ssa_names; i++)
 {
-var = map->partition_to_var[i];
+var = ssa_name (i);
-if (var != NULL_TREE)
+if (var != NULL_TREE && is_gimple_reg (var))
 {
 	  /* Add coalesces between all the result decls.  */
 	  if (TREE_CODE (SSA_NAME_VAR (var)) == RESULT_DECL)
 	    {
 	      if (first == NULL_TREE)
 		}
 	    }
 	  /* Mark any default_def variables as being in the coalesce list
 	     since they will have to be coalesced with the base variable.  If
 	     not marked as present, they won't be in the coalesce view. */
-	  if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var)
+	  if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var
+	      && !has_zero_uses (var))
 	    bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
 	}
 }
 #if defined ENABLE_CHECKING
 print_generic_expr (debug, partition_to_var (map, p1), TDF_SLIM);
 fprintf (debug, " & (%d)", y);
 print_generic_expr (debug, partition_to_var (map, p2), TDF_SLIM);
 }
 if (p1 == p2)
 {
 if (debug)
 	fprintf (debug, ": Already Coalesced.\n");
 return true;
 }
 	  if (debug)
 	    fprintf (debug, ": Unable to perform partition union.\n");
 	  return false;
 	}
 /* z is the new combined partition.  Remove the other partition from
 	 the list, and merge the conflicts.  */
 if (z == p1)
 	ssa_conflicts_merge (graph, p1, p2);
 else
 	ssa_conflicts_merge (graph, p2, p1);
 return false;
 }
 /* Attempt to Coalesce partitions in MAP which occur in the list CL using
 GRAPH.  Debug output is sent to DEBUG if it is non-NULL.  */
 static void
 coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
 		     FILE *debug)
 {
 int x = 0, y = 0;
 tree var1, var2;
 int cost;
 basic_block bb;
 edge e;
 edge_iterator ei;
 /* First, coalesce all the copies across abnormal edges.  These are not placed
 in the coalesce list because they do not need to be sorted, and simply
 consume extra memory/compilation time in large programs.  */
 FOR_EACH_BB (bb)
 {
 FOR_EACH_EDGE (e, ei, bb->preds)
 a partition map with the resulting coalesces.  */
 extern var_map
 coalesce_ssa_name (void)
 {
-unsigned num, x;
 tree_live_info_p liveinfo;
 ssa_conflicts_p graph;
 coalesce_list_p cl;
 bitmap used_in_copies = BITMAP_ALLOC (NULL);
 var_map map;
 				   eq_ssa_name_by_var, NULL);
 for (i = 1; i < num_ssa_names; i++)
 	{
 	  tree a = ssa_name (i);
-	  if (a && SSA_NAME_VAR (a) && !DECL_ARTIFICIAL (SSA_NAME_VAR (a)))
+	  if (a
+	      && SSA_NAME_VAR (a)
+	      && !DECL_ARTIFICIAL (SSA_NAME_VAR (a))
+	      && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)))
 	    {
 	      tree *slot = (tree *) htab_find_slot (ssa_name_hash, a, INSERT);
 	      if (!*slot)
 		*slot = a;
 {
 fprintf (dump_file, "\nAfter sorting:\n");
 dump_coalesce_list (dump_file, cl);
 }
 /* First, coalesce all live on entry variables to their base variable.
 This will ensure the first use is coming from the correct location.  */
-num = num_var_partitions (map);
-for (x = 0 ; x < num; x++)
-{
-tree var = partition_to_var (map, x);
-tree root;
-if (TREE_CODE (var) != SSA_NAME)
-	continue;
-root = SSA_NAME_VAR (var);
-if (gimple_default_def (cfun, root) == var)
-{
-	  /* This root variable should have not already been assigned
-	     to another partition which is not coalesced with this one.  */
-	  gcc_assert (!var_ann (root)->out_of_ssa_tag);
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    {
-	      print_exprs (dump_file, "Must coalesce ", var,
-			   " with the root variable ", root, ".\n");
-	    }
-	  change_partition_var (map, root, x);
-	}
-}
 if (dump_file && (dump_flags & TDF_DETAILS))
 dump_var_map (dump_file, map);
 /* Now coalesce everything in the list.  */
 coalesce_partitions (map, graph, cl,
 		       ((dump_flags & TDF_DETAILS) ? dump_file
 						   : NULL));
 delete_coalesce_list (cl);
 ssa_conflicts_delete (graph);

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-coalesce.c @ 55:77e2b8dfacca gcc-4.4.5