This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[tree-ssa]: Speed up SSAPRE a few percent


This patch speeds up SSAPRE a few percent, particularly on large cases.
The number of ephis is small compared to the total number of occurrences
of basic blocks in medium->large cases, so just the memory accesses can be
a drag of a few percent.
To solve this, we just keep a list of ephis as well.
This adds a bit of overhead in the case of very small numbers of ephis and
very small numbers of bbs/occurrences (IE very small functions), so it's
not *always* a win, but it's never more than a small lose, and for large
cases, it's a moderate win.

2004-03-16  Daniel Berlin  <dberlin@dberlin.org>

	* tree-ssa-pre.c (struct expr_info): Add ephis member.
	(create_and_insert_occ_in_preorder_dt_order):  push EPHIs onto
	the EPHIS array.
	Sort the ephis array in dom order too.
	(insert_euse_in_preorder_dt_order): Ditto.
	(rename_1): Replace iteration through all bbs looking for ephis
	with iteration through ephis list.
	(compute_downsafety): Ditto.
	(compute_du_info): Replace iteration through all occurrences
	looking for ephis with iteration through ephis list.
	(compute_stops): Ditto.
	(finalize_2): Ditto.
	(do_ephi_df_search): Ditto.
	(code_motion): Ditto.
	(free_expr_info): Free ephi list.
	(collect_expressions): Init ephi list.
Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-pre.c,v
retrieving revision 1.1.4.133
diff -u -3 -p -r1.1.4.133 tree-ssa-pre.c
--- tree-ssa-pre.c	16 Mar 2004 15:59:29 -0000	1.1.4.133
+++ tree-ssa-pre.c	16 Mar 2004 18:44:09 -0000
@@ -312,6 +312,8 @@ struct expr_info
   bool loadpre_cand;
   /* The euses/ephis in preorder dt order. */
   varray_type euses_dt_order;
+  /* The ephis in preorder dt order.  */
+  varray_type ephis;
   /* The name of the temporary for this expression. */
   tree temp;
 };
@@ -970,7 +972,10 @@ create_and_insert_occ_in_preorder_dt_ord
     /* The ordering for a given BB is EPHI's, real/left/kill
        occurrences, phi preds, exit occurrences.   */
     if (ephi != NULL_TREE)
-      VARRAY_PUSH_TREE (ei->euses_dt_order, ephi);
+      {
+	VARRAY_PUSH_TREE (ei->euses_dt_order, ephi);
+	VARRAY_PUSH_TREE (ei->ephis, ephi);
+      }
   }

   /* The non-ephis have to actually be created, so do that, then push
@@ -1072,6 +1077,10 @@ create_and_insert_occ_in_preorder_dt_ord
 	 VARRAY_ACTIVE_SIZE (ei->euses_dt_order),
 	 sizeof (tree),
 	 eref_compare);
+  qsort (ei->ephis->data.tree,
+	 VARRAY_ACTIVE_SIZE (ei->ephis),
+	 sizeof (tree),
+	 eref_compare);
 }


@@ -1606,7 +1615,6 @@ static void
 rename_1 (struct expr_info *ei)
 {
   tree occur;
-  basic_block phi_bb;
   size_t i;
   varray_type stack;

@@ -1752,36 +1760,34 @@ rename_1 (struct expr_info *ei)
   /* Now process the renames for EPHI's that actually have the result
      valid and used.  These will be the EPHI's that have the statement
      set above.  */
-  FOR_EACH_BB (phi_bb)
-  {
-    tree ephi = ephi_at_block (phi_bb);
-    if (ephi != NULL && EREF_STMT (ephi) != NULL)
-      process_delayed_rename (ei, ephi, EREF_STMT (ephi));
-  }
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->ephis); i++)
+    {
+      tree ephi = VARRAY_TREE (ei->ephis, i);
+      if (EREF_STMT (ephi) != NULL)
+        process_delayed_rename (ei, ephi, EREF_STMT (ephi));
+    }

   /* If we didn't process the delayed rename for an ephi argument,
      but thought we needed to, mark the operand as NULL.  Also, if the
      operand was defined by an  EPHI, we can mark it not downsafe
      because there can't have been a real occurrence (or else we would
      have processed a rename for it).  */
-  FOR_EACH_BB (phi_bb)
-  {
-    tree ephi = ephi_at_block (phi_bb);
-    if (ephi != NULL)
-      {
-	int j;
-	for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
-	  {
-	    if (EPHI_ARG_DELAYED_RENAME (ephi, j))
-	      {
-		tree def = EPHI_ARG_DEF (ephi, j);
-		if (def && TREE_CODE (def) == EPHI_NODE)
-		  EPHI_DOWNSAFE (def) = false;
-		EPHI_ARG_DEF (ephi, j) = NULL;
-	      }
-	  }
-      }
-  }
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->ephis); i++)
+    {
+      int j;
+      tree ephi = VARRAY_TREE (ei->ephis, i);
+      for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
+	{
+	  if (EPHI_ARG_DELAYED_RENAME (ephi, j))
+	    {
+	      tree def = EPHI_ARG_DEF (ephi, j);
+	      if (def && TREE_CODE (def) == EPHI_NODE)
+		EPHI_DOWNSAFE (def) = false;
+	      EPHI_ARG_DEF (ephi, j) = NULL;
+	    }
+	}
+    }
+
   VARRAY_FREE (stack);
 }

@@ -1827,22 +1833,17 @@ static void
 compute_down_safety (struct expr_info *ei)
 {
   size_t i;
-  basic_block bb;
-  FOR_EACH_BB (bb)
-  {
-    tree ephi = ephi_at_block (bb);
-    if (ephi == NULL_TREE)
-      continue;
-    if (ephi_has_unsafe_arg (ephi))
-      EPHI_DOWNSAFE (ephi) = false;
-  }
-  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
+
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->ephis); i++)
+    {
+      tree ephi = VARRAY_TREE (ei->ephis, i);
+      if (ephi_has_unsafe_arg (ephi))
+	EPHI_DOWNSAFE (ephi) = false;
+    }
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->ephis); i++)
     {
       int j;
-      tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
-      if (TREE_CODE (ephi) != EPHI_NODE)
-	continue;
-
+      tree ephi = VARRAY_TREE (ei->ephis, i);
       if (!EPHI_DOWNSAFE (ephi))
 	for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
 	  reset_down_safe (ephi, j);
@@ -1874,12 +1875,10 @@ static void
 compute_du_info (struct expr_info *ei)
 {
   size_t i;
-  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->ephis); i++)
     {
       int j;
-      tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
-      if (TREE_CODE (ephi) != EPHI_NODE)
-	continue;
+      tree ephi = VARRAY_TREE (ei->ephis, i);
       for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
 	{
 	  tree def = EPHI_ARG_DEF (ephi, j);
@@ -1905,13 +1904,10 @@ compute_stops (struct expr_info *ei)
 {
   size_t i;

-  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->ephis); i++)
     {
-      tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
+      tree ephi = VARRAY_TREE (ei->ephis, i);
       int j;
-
-      if (TREE_CODE (ephi) != EPHI_NODE)
-	continue;
       if (EPHI_CANT_BE_AVAIL (ephi))
 	EPHI_STOPS (ephi) = true;
       for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
@@ -1936,23 +1932,34 @@ compute_will_be_avail (struct expr_info
 static void
 insert_euse_in_preorder_dt_order (struct expr_info *ei)
 {
-  varray_type new_euses_dt_order;
+  varray_type new_euses_dt_order, new_ephis;
   size_t i;
   VARRAY_GENERIC_PTR_NOGC_INIT (new_euses_dt_order, 1, "EUSEs");
-
+  VARRAY_GENERIC_PTR_NOGC_INIT (new_ephis, 1, "EPHIs");
+
   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
     {
       tree ref = VARRAY_TREE (ei->euses_dt_order, i);
       if (TREE_CODE (ref) == EUSE_NODE || TREE_CODE (ref) == EPHI_NODE)
-	VARRAY_PUSH_TREE (new_euses_dt_order, ref);
+	{
+
+	  VARRAY_PUSH_TREE (new_euses_dt_order, ref);
+	  if (TREE_CODE (ref) == EPHI_NODE)
+	    VARRAY_PUSH_TREE (new_ephis, ref);
+	}
     }
   VARRAY_FREE (ei->euses_dt_order);
+  VARRAY_FREE (ei->ephis);
   ei->euses_dt_order = new_euses_dt_order;
+  ei->ephis = new_ephis;
   qsort (ei->euses_dt_order->data.tree,
 	 VARRAY_ACTIVE_SIZE (ei->euses_dt_order),
 	 sizeof (tree),
 	 eref_compare);
-
+  qsort (ei->ephis->data.tree,
+	 VARRAY_ACTIVE_SIZE (ei->ephis),
+	 sizeof (tree),
+	 eref_compare);
 }

 /* Determine if we can insert operand OPND_INDX of EPHI.  */
@@ -2532,19 +2539,17 @@ finalize_2 (struct expr_info *ei)
   /* ESSA Minimization.  Determines which phis are identical to other
      phis, and not strictly necessary.  */

-  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->ephis); i++)
     {
-      tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
-      if (TREE_CODE (ephi) != EPHI_NODE)
-	continue;
+      tree ephi = VARRAY_TREE (ei->ephis, i);
       EPHI_IDENTITY (ephi) = true;
       EPHI_IDENTICAL_TO (ephi) = NULL;
     }

-  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->ephis); i++)
     {
-      tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
-      if (!ephi || TREE_CODE (ephi) != EPHI_NODE)
+      tree ephi = VARRAY_TREE (ei->ephis, i);
+      if (!ephi)
 	continue;
       if (ephi_will_be_avail (ephi))
 	{
@@ -2594,10 +2599,10 @@ static void
 do_ephi_df_search (struct expr_info *ei, struct ephi_df_search search)
 {
   size_t i;
-  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->ephis); i++)
     {
-      tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
-      if (!ephi || TREE_CODE (ephi) != EPHI_NODE)
+      tree ephi = VARRAY_TREE (ei->ephis, i);
+      if (!ephi)
 	continue;
       if (!search.seen (ephi)
 	  && search.start_from (ephi))
@@ -2720,13 +2725,10 @@ code_motion (struct expr_info *ei)
   /* First, add the phi node temporaries so the reaching defs are
      always right. */
   for (euse_iter = 0;
-       euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order);
+       euse_iter < VARRAY_ACTIVE_SIZE (ei->ephis);
        euse_iter++)
     {
-
-      use = VARRAY_TREE (ei->euses_dt_order, euse_iter);
-      if (TREE_CODE (use) != EPHI_NODE)
-	continue;
+      use = VARRAY_TREE (ei->ephis, euse_iter);
       if (ephi_will_be_avail (use) && !EPHI_IDENTITY (use))
 	{
 	  bb = bb_for_stmt (use);
@@ -2824,10 +2826,10 @@ code_motion (struct expr_info *ei)

   /* Now do the phi nodes. */
   for (euse_iter = 0;
-       euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order);
+       euse_iter < VARRAY_ACTIVE_SIZE (ei->ephis);
        euse_iter++)
     {
-      use = VARRAY_TREE (ei->euses_dt_order, euse_iter);
+      use = VARRAY_TREE (ei->ephis, euse_iter);
       if (TREE_CODE (use) == EPHI_NODE
 	  && ephi_will_be_avail (use)
 	  && !EPHI_IDENTITY (use))
@@ -2999,6 +3001,7 @@ free_expr_info (struct expr_info *v1)
   VARRAY_FREE (e1->lefts);
   VARRAY_FREE (e1->reals);
   VARRAY_FREE (e1->euses_dt_order);
+  VARRAY_FREE (e1->ephis);
 }

 /* Process left occurrences and kills due to EXPR.
@@ -3249,7 +3252,7 @@ collect_expressions (basic_block block,
 		  VARRAY_GENERIC_PTR_NOGC_INIT (slot->lefts, 1, "Left occurrences");
 		  VARRAY_GENERIC_PTR_NOGC_INIT (slot->reals, 1, "Real occurrences");
 		  VARRAY_GENERIC_PTR_NOGC_INIT (slot->euses_dt_order, 1, "EUSEs");
-
+		  VARRAY_GENERIC_PTR_NOGC_INIT (slot->ephis, 1, "EPHIs");
 		  VARRAY_PUSH_TREE (slot->occurs, orig_expr);
 		  VARRAY_PUSH_TREE (slot->kills, NULL);
 		  VARRAY_PUSH_TREE (slot->lefts, NULL);
@@ -3289,7 +3292,6 @@ execute_pre (void)
   if (ENTRY_BLOCK_PTR->succ->dest->pred->pred_next)
     if (!(ENTRY_BLOCK_PTR->succ->flags & EDGE_ABNORMAL))
       split_edge (ENTRY_BLOCK_PTR->succ);
-
   euse_node_pool = create_alloc_pool ("EUSE node pool",
 				      sizeof (struct tree_euse_node), 30);
   eref_node_pool = create_alloc_pool ("EREF node pool",


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]