[PATCH 3/3] Speed-up ifcvt_memrefs_wont_trap caching previous results.

[Sebastian Pop <sebpop at gmail dot com>]

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.
	(IFC_DR): New.
	(DR_WRITTEN_AT_LEAST_ONCE): New.
	(DR_RW_UNCONDITIONALLY): 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 |   64 ++++++++++++++++++++++++++++++++++++++++++++++++---
 1 files changed, 60 insertions(+), 4 deletions(-)

diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 1cf53f5..f215e97 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -446,6 +446,21 @@ 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 written_at_least_once;
+
+  /* -1 when not initialized, 0 when false, 1 when true.  */
+  int rw_unconditionally;
+};
+
+#define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
+#define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
+#define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
+
 /* Returns true when the memory reference A at position POS in the
    data references vector DRS and executed under the condition CA, is
    read or written unconditionally.  In other words, this function
@@ -461,18 +476,28 @@ memref_read_or_written_unconditionally (int pos, data_reference_p a,
 {
   int i;
   data_reference_p b;
+  int x = DR_RW_UNCONDITIONALLY (a);
+
+  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 (DR_RW_UNCONDITIONALLY (b) == 1
+	    || is_true_predicate (cb)
 	    || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
 							   ca, cb)))
-	  return true;
+	  {
+	    DR_RW_UNCONDITIONALLY (a) = 1;
+	    DR_RW_UNCONDITIONALLY (b) = 1;
+	    return true;
+	  }
       }
 
+  DR_RW_UNCONDITIONALLY (a) = 0;
   return false;
 }
 
@@ -507,6 +532,10 @@ write_memref_written_at_least_once (int pos, data_reference_p a,
 {
   int i;
   data_reference_p b;
+  int x = DR_WRITTEN_AT_LEAST_ONCE (a);
+
+  if (x != -1)
+    return x;
 
   for (i = 0; VEC_iterate (data_reference_p, drs, i, b); i++)
     if (i != pos
@@ -515,12 +544,18 @@ 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 (DR_WRITTEN_AT_LEAST_ONCE (b) == 1
+	    || is_true_predicate (cb)
 	    || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
 							   ca, cb)))
-	  return true;
+	  {
+	    DR_WRITTEN_AT_LEAST_ONCE (a) = 1;
+	    DR_WRITTEN_AT_LEAST_ONCE (b) = 1;
+	    return true;
+	  }
       }
 
+  DR_WRITTEN_AT_LEAST_ONCE (a) = 0;
   return false;
 }
 
@@ -984,6 +1019,18 @@ if_convertible_loop_p_1 (struct loop *loop,
   if (!res)
     return false;
 
+  if (flag_tree_loop_if_convert_memory_writes)
+    {
+      data_reference_p dr;
+
+      for (i = 0; VEC_iterate (data_reference_p, *refs, i, dr); i++)
+	{
+	  dr->aux = XNEW (struct ifc_dr);
+	  DR_WRITTEN_AT_LEAST_ONCE (dr) = -1;
+	  DR_RW_UNCONDITIONALLY (dr) = -1;
+	}
+    }
+
   for (i = 0; i < loop->num_nodes; i++)
     {
       basic_block bb = ifc_bbs[i];
@@ -1057,6 +1104,15 @@ if_convertible_loop_p (struct loop *loop)
   ddrs = VEC_alloc (ddr_p, heap, 25);
   res = if_convertible_loop_p_1 (loop, &refs, &ddrs);
 
+  if (flag_tree_loop_if_convert_memory_writes)
+    {
+      data_reference_p dr;
+      unsigned int i;
+
+      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;
-- 
1.7.0.4