Patchwork [4/4] Speed-up ifcvt_memrefs_wont_trap caching previous results.

login
register
mail settings
Submitter Sebastian Pop
Date July 8, 2010, 9:41 p.m.
Message ID <1278625285-12667-5-git-send-email-sebpop@gmail.com>
Download mbox | patch
Permalink /patch/58305/
State New
Headers show

Comments

Sebastian Pop - July 8, 2010, 9:41 p.m.
This patch speeds up the ifcvt_memrefs_wont_trap computation by
caching the results of the computations in the data references ->aux
fields.

	* tree-if-conv.c (struct ifc_dr): New.
	(memref_read_or_written_unconditionally): Use the cached values
	when possible.
	(write_memref_written_at_least_once): Same.
	(if_convertible_loop_p): Initialize and free DR->aux fields.
---
 gcc/tree-if-conv.c |   53 ++++++++++++++++++++++++++++++++++++++++++++++++---
 1 files changed, 49 insertions(+), 4 deletions(-)
Richard Guenther - Aug. 13, 2010, 8:58 a.m.
On Thu, 8 Jul 2010, Sebastian Pop wrote:

> This patch speeds up the ifcvt_memrefs_wont_trap computation by
> caching the results of the computations in the data references ->aux
> fields.
> 
> 	* tree-if-conv.c (struct ifc_dr): New.
> 	(memref_read_or_written_unconditionally): Use the cached values
> 	when possible.
> 	(write_memref_written_at_least_once): Same.
> 	(if_convertible_loop_p): Initialize and free DR->aux fields.
> ---
>  gcc/tree-if-conv.c |   53 ++++++++++++++++++++++++++++++++++++++++++++++++---
>  1 files changed, 49 insertions(+), 4 deletions(-)
> 
> diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
> index f0bc026..655c168 100644
> --- a/gcc/tree-if-conv.c
> +++ b/gcc/tree-if-conv.c
> @@ -441,6 +441,17 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
>    return true;
>  }
>  
> +/* Records the status of a data reference.  This struct is attached to
> +   each DR->aux field.  */
> +
> +struct ifc_dr {
> +  /* -1 when not initialized, 0 when false, 1 when true.  */
> +  int dr_is_written_at_least_once;
> +
> +  /* -1 when not initialized, 0 when false, 1 when true.  */
> +  int dr_is_rw_unconditionally;
> +};
> +
>  /* Returns true when the memory reference A at position P in the data
>     references vector DRS and executed under the condition CA, is read
>     or written unconditionally.  */
> @@ -452,17 +463,27 @@ memref_read_or_written_unconditionally (int pos, data_reference_p a,
>  {
>    int i;
>    data_reference_p b;
> +  int x = ((struct ifc_dr *) a->aux)->dr_is_rw_unconditionally;

These casts are ugly.  Please add a #define like

#define DR_IFCVT(dr) ((struct ifc_dr *) a->aux)

and use that.

Ok with that change.

Richard.

> +
> +  if (x != -1)
> +    return x;
>  
>    for (i = 0; VEC_iterate (data_reference_p, drs, i, b); i++)
>      if (i != pos && same_data_refs (a, b))
>        {
>  	tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
>  
> -	if (is_true_predicate (cb)
> +	if (((struct ifc_dr *) b->aux)->dr_is_rw_unconditionally == 1
> +	    || is_true_predicate (cb)
>  	    || is_true_predicate (ca = fold_or_predicates (ca, cb)))
> -	  return true;
> +	  {
> +	    ((struct ifc_dr *) a->aux)->dr_is_rw_unconditionally = 1;
> +	    ((struct ifc_dr *) b->aux)->dr_is_rw_unconditionally = 1;
> +	    return true;
> +	  }
>        }
>  
> +  ((struct ifc_dr *) a->aux)->dr_is_rw_unconditionally = 0;
>    return false;
>  }
>  
> @@ -497,6 +518,10 @@ write_memref_written_at_least_once (int pos, data_reference_p a,
>  {
>    int i;
>    data_reference_p b;
> +  int x = ((struct ifc_dr *) a->aux)->dr_is_written_at_least_once;
> +
> +  if (x != -1)
> +    return x;
>  
>    for (i = 0; VEC_iterate (data_reference_p, drs, i, b); i++)
>      if (i != pos
> @@ -505,11 +530,17 @@ write_memref_written_at_least_once (int pos, data_reference_p a,
>        {
>  	tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
>  
> -	if (is_true_predicate (cb)
> +	if (((struct ifc_dr *) b->aux)->dr_is_written_at_least_once == 1
> +	    || is_true_predicate (cb)
>  	    || is_true_predicate (ca = fold_or_predicates (ca, cb)))
> -	  return true;
> +	  {
> +	    ((struct ifc_dr *) a->aux)->dr_is_written_at_least_once = 1;
> +	    ((struct ifc_dr *) b->aux)->dr_is_written_at_least_once = 1;
> +	    return true;
> +	  }
>        }
>  
> +  ((struct ifc_dr *) a->aux)->dr_is_written_at_least_once = 0;
>    return false;
>  }
>  
> @@ -972,6 +1003,7 @@ if_convertible_loop_p (struct loop *loop)
>    edge_iterator ei;
>    basic_block exit_bb = NULL;
>    bool res = false;
> +  data_reference_p dr;
>    VEC (data_reference_p, heap) *refs;
>    VEC (ddr_p, heap) *ddrs;
>  
> @@ -1048,6 +1080,14 @@ if_convertible_loop_p (struct loop *loop)
>  
>    res = false;
>  
> +  if (flag_tree_loop_if_convert_memory_writes)
> +    for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++)
> +      {
> +	dr->aux = XNEW (struct ifc_dr);
> +	((struct ifc_dr *) dr->aux)->dr_is_written_at_least_once = -1;
> +	((struct ifc_dr *) dr->aux)->dr_is_rw_unconditionally = -1;
> +      }
> +
>    for (i = 0; i < loop->num_nodes; i++)
>      {
>        basic_block bb = ifc_bbs[i];
> @@ -1069,6 +1109,11 @@ if_convertible_loop_p (struct loop *loop)
>      fprintf (dump_file, "Applying if-conversion\n");
>  
>   cleanup:
> +
> +  if (flag_tree_loop_if_convert_memory_writes)
> +    for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++)
> +      free (dr->aux);
> +
>    free_data_refs (refs);
>    free_dependence_relations (ddrs);
>    return res;
>

Patch

diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index f0bc026..655c168 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -441,6 +441,17 @@  if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
   return true;
 }
 
+/* Records the status of a data reference.  This struct is attached to
+   each DR->aux field.  */
+
+struct ifc_dr {
+  /* -1 when not initialized, 0 when false, 1 when true.  */
+  int dr_is_written_at_least_once;
+
+  /* -1 when not initialized, 0 when false, 1 when true.  */
+  int dr_is_rw_unconditionally;
+};
+
 /* Returns true when the memory reference A at position P in the data
    references vector DRS and executed under the condition CA, is read
    or written unconditionally.  */
@@ -452,17 +463,27 @@  memref_read_or_written_unconditionally (int pos, data_reference_p a,
 {
   int i;
   data_reference_p b;
+  int x = ((struct ifc_dr *) a->aux)->dr_is_rw_unconditionally;
+
+  if (x != -1)
+    return x;
 
   for (i = 0; VEC_iterate (data_reference_p, drs, i, b); i++)
     if (i != pos && same_data_refs (a, b))
       {
 	tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
 
-	if (is_true_predicate (cb)
+	if (((struct ifc_dr *) b->aux)->dr_is_rw_unconditionally == 1
+	    || is_true_predicate (cb)
 	    || is_true_predicate (ca = fold_or_predicates (ca, cb)))
-	  return true;
+	  {
+	    ((struct ifc_dr *) a->aux)->dr_is_rw_unconditionally = 1;
+	    ((struct ifc_dr *) b->aux)->dr_is_rw_unconditionally = 1;
+	    return true;
+	  }
       }
 
+  ((struct ifc_dr *) a->aux)->dr_is_rw_unconditionally = 0;
   return false;
 }
 
@@ -497,6 +518,10 @@  write_memref_written_at_least_once (int pos, data_reference_p a,
 {
   int i;
   data_reference_p b;
+  int x = ((struct ifc_dr *) a->aux)->dr_is_written_at_least_once;
+
+  if (x != -1)
+    return x;
 
   for (i = 0; VEC_iterate (data_reference_p, drs, i, b); i++)
     if (i != pos
@@ -505,11 +530,17 @@  write_memref_written_at_least_once (int pos, data_reference_p a,
       {
 	tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
 
-	if (is_true_predicate (cb)
+	if (((struct ifc_dr *) b->aux)->dr_is_written_at_least_once == 1
+	    || is_true_predicate (cb)
 	    || is_true_predicate (ca = fold_or_predicates (ca, cb)))
-	  return true;
+	  {
+	    ((struct ifc_dr *) a->aux)->dr_is_written_at_least_once = 1;
+	    ((struct ifc_dr *) b->aux)->dr_is_written_at_least_once = 1;
+	    return true;
+	  }
       }
 
+  ((struct ifc_dr *) a->aux)->dr_is_written_at_least_once = 0;
   return false;
 }
 
@@ -972,6 +1003,7 @@  if_convertible_loop_p (struct loop *loop)
   edge_iterator ei;
   basic_block exit_bb = NULL;
   bool res = false;
+  data_reference_p dr;
   VEC (data_reference_p, heap) *refs;
   VEC (ddr_p, heap) *ddrs;
 
@@ -1048,6 +1080,14 @@  if_convertible_loop_p (struct loop *loop)
 
   res = false;
 
+  if (flag_tree_loop_if_convert_memory_writes)
+    for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++)
+      {
+	dr->aux = XNEW (struct ifc_dr);
+	((struct ifc_dr *) dr->aux)->dr_is_written_at_least_once = -1;
+	((struct ifc_dr *) dr->aux)->dr_is_rw_unconditionally = -1;
+      }
+
   for (i = 0; i < loop->num_nodes; i++)
     {
       basic_block bb = ifc_bbs[i];
@@ -1069,6 +1109,11 @@  if_convertible_loop_p (struct loop *loop)
     fprintf (dump_file, "Applying if-conversion\n");
 
  cleanup:
+
+  if (flag_tree_loop_if_convert_memory_writes)
+    for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++)
+      free (dr->aux);
+
   free_data_refs (refs);
   free_dependence_relations (ddrs);
   return res;