[PATCH][2/n] Wading through data-dependence analysis

[Richard Guenther <rguenther at suse dot de>]

This patch tries to disentangle the loop vs. non-loop code in
data dependence analysis.  For loop data-dependences we always
want (and need) to compute a distance vector if two references
from any loop iteration may alias.  Thus we have to disable
all offset-based analysis.  This is not yet what this patch does,
this patch merely makes the non-loop code stronger which
relies (*sigh*) on those invalid disambiguations (well, invalid
only for the loop case ...).

Thus we employ something slightly stronger than refs_may_alias_p,
namely what loop invariant motion does (but cheaper, without
actually expanding things).

Which allows us to do nothing for the non-loop case in
dr_analyze_indices, which makes sense.

Bootstrapped and tested on x86_64-unknown-linux-gnu, re-bootstrapping
after a stylistic change (s/VEC() *loop_nest/bool/ for dr_may_alias_p).

Richard.

2011-08-23  Richard Guenther  <rguenther@suse.de>

	* Makefile.in (tree-data-ref.o): Add tree-affine.h dependency.
	* tree-affine.h (aff_comb_cannot_overlap_p): Declare.
	* tree-affine.c (aff_comb_cannot_overlap_p): New function, moved
	from ...
	* tree-ssa-loop-im.c (cannot_overlap_p): ... here.
	(mem_refs_may_alias_p): Adjust.
	* tree-data-ref.h (dr_may_alias_p): Adjust.
	* tree-data-ref.c: Include tree-affine.h.
	(dr_analyze_indices): Do nothing for the non-loop case.
	(dr_may_alias_p): Distinguish loop and non-loop case.  Disambiguate
	more cases in the non-loop case.
	* graphite-sese-to-poly.c (write_alias_graph_to_ascii_dimacs): Adjust
	calls to dr_may_alias_p.
	(write_alias_graph_to_ascii_ecc): Likewise.
	(write_alias_graph_to_ascii_dot): Likewise.
	(build_alias_set_optimal_p): Likewise.

Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 177983)
+++ gcc/Makefile.in	(working copy)
@@ -2690,7 +2690,7 @@ tree-scalar-evolution.o : tree-scalar-ev
    $(TREE_PASS_H) $(PARAMS_H) gt-tree-scalar-evolution.h
 tree-data-ref.o : tree-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    gimple-pretty-print.h $(TREE_FLOW_H) $(CFGLOOP_H) $(TREE_DATA_REF_H) \
-   $(TREE_PASS_H) langhooks.h
+   $(TREE_PASS_H) langhooks.h tree-affine.h
 sese.o : sese.c sese.h $(CONFIG_H) $(SYSTEM_H) coretypes.h tree-pretty-print.h \
    $(TREE_FLOW_H) $(CFGLOOP_H) $(TREE_DATA_REF_H) tree-pass.h value-prof.h
 graphite.o : graphite.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(DIAGNOSTIC_CORE_H) \
Index: gcc/tree-affine.c
===================================================================
--- gcc/tree-affine.c	(revision 177983)
+++ gcc/tree-affine.c	(working copy)
@@ -887,3 +887,30 @@ get_inner_reference_aff (tree ref, aff_t
   *size = shwi_to_double_int ((bitsize + BITS_PER_UNIT - 1) / BITS_PER_UNIT);
 }
 
+/* Returns true if a region of size SIZE1 at position 0 and a region of
+   size SIZE2 at position DIFF cannot overlap.  */
+
+bool
+aff_comb_cannot_overlap_p (aff_tree *diff, double_int size1, double_int size2)
+{
+  double_int d, bound;
+
+  /* Unless the difference is a constant, we fail.  */
+  if (diff->n != 0)
+    return false;
+
+  d = diff->offset;
+  if (double_int_negative_p (d))
+    {
+      /* The second object is before the first one, we succeed if the last
+	 element of the second object is before the start of the first one.  */
+      bound = double_int_add (d, double_int_add (size2, double_int_minus_one));
+      return double_int_negative_p (bound);
+    }
+  else
+    {
+      /* We succeed if the second object starts after the first one ends.  */
+      return double_int_scmp (size1, d) <= 0;
+    }
+}
+
Index: gcc/tree-affine.h
===================================================================
--- gcc/tree-affine.h	(revision 177983)
+++ gcc/tree-affine.h	(working copy)
@@ -76,6 +76,7 @@ void tree_to_aff_combination_expand (tre
 				     struct pointer_map_t **);
 void get_inner_reference_aff (tree, aff_tree *, double_int *);
 void free_affine_expand_cache (struct pointer_map_t **);
+bool aff_comb_cannot_overlap_p (aff_tree *, double_int, double_int);
 
 /* Debugging functions.  */
 void print_aff (FILE *, aff_tree *);
Index: gcc/tree-ssa-loop-im.c
===================================================================
--- gcc/tree-ssa-loop-im.c	(revision 177983)
+++ gcc/tree-ssa-loop-im.c	(working copy)
@@ -1835,33 +1835,6 @@ analyze_memory_references (void)
   create_vop_ref_mapping ();
 }
 
-/* Returns true if a region of size SIZE1 at position 0 and a region of
-   size SIZE2 at position DIFF cannot overlap.  */
-
-static bool
-cannot_overlap_p (aff_tree *diff, double_int size1, double_int size2)
-{
-  double_int d, bound;
-
-  /* Unless the difference is a constant, we fail.  */
-  if (diff->n != 0)
-    return false;
-
-  d = diff->offset;
-  if (double_int_negative_p (d))
-    {
-      /* The second object is before the first one, we succeed if the last
-	 element of the second object is before the start of the first one.  */
-      bound = double_int_add (d, double_int_add (size2, double_int_minus_one));
-      return double_int_negative_p (bound);
-    }
-  else
-    {
-      /* We succeed if the second object starts after the first one ends.  */
-      return double_int_scmp (size1, d) <= 0;
-    }
-}
-
 /* Returns true if MEM1 and MEM2 may alias.  TTAE_CACHE is used as a cache in
    tree_to_aff_combination_expand.  */
 
@@ -1890,7 +1863,7 @@ mem_refs_may_alias_p (tree mem1, tree me
   aff_combination_scale (&off1, double_int_minus_one);
   aff_combination_add (&off2, &off1);
 
-  if (cannot_overlap_p (&off2, size1, size2))
+  if (aff_comb_cannot_overlap_p (&off2, size1, size2))
     return false;
 
   return true;
Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c	(revision 177983)
+++ gcc/tree-data-ref.c	(working copy)
@@ -84,6 +84,7 @@ along with GCC; see the file COPYING3.
 #include "tree-scalar-evolution.h"
 #include "tree-pass.h"
 #include "langhooks.h"
+#include "tree-affine.h"
 
 static struct datadep_stats
 {
@@ -841,8 +842,14 @@ dr_analyze_indices (struct data_referenc
   tree base, off, access_fn = NULL_TREE;
   basic_block before_loop = NULL;
 
-  if (nest)
-    before_loop = block_before_loop (nest);
+  if (!nest)
+    {
+      DR_BASE_OBJECT (dr) = ref;
+      DR_ACCESS_FNS (dr) = NULL;
+      return;
+    }
+
+  before_loop = block_before_loop (nest);
 
   /* Analyze access functions of dimensions we know to be independent.  */
   while (handled_component_p (aref))
@@ -852,12 +859,9 @@ dr_analyze_indices (struct data_referenc
       if (TREE_CODE (aref) == ARRAY_REF)
 	{
 	  op = TREE_OPERAND (aref, 1);
-	  if (nest)
-	    {
-	      access_fn = analyze_scalar_evolution (loop, op);
-	      access_fn = instantiate_scev (before_loop, loop, access_fn);
-	      VEC_safe_push (tree, heap, access_fns, access_fn);
-	    }
+	  access_fn = analyze_scalar_evolution (loop, op);
+	  access_fn = instantiate_scev (before_loop, loop, access_fn);
+	  VEC_safe_push (tree, heap, access_fns, access_fn);
 	  TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
 	}
       /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
@@ -877,8 +881,7 @@ dr_analyze_indices (struct data_referenc
       aref = TREE_OPERAND (aref, 0);
     }
 
-  if (nest
-      && TREE_CODE (aref) == MEM_REF)
+  if (TREE_CODE (aref) == MEM_REF)
     {
       op = TREE_OPERAND (aref, 0);
       access_fn = analyze_scalar_evolution (loop, op);
@@ -1286,14 +1289,33 @@ object_address_invariant_in_loop_p (cons
 }
 
 /* Returns false if we can prove that data references A and B do not alias,
-   true otherwise.  */
+   true otherwise.  If LOOP_NEST is false no cross-iteration aliases are
+   considered.  */
 
 bool
-dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
+dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
+		bool loop_nest)
 {
   tree addr_a = DR_BASE_OBJECT (a);
   tree addr_b = DR_BASE_OBJECT (b);
 
+  /* If we are not processing a loop nest but scalar code we
+     do not need to care about possible cross-iteration dependences
+     and thus can process the full original reference.  Do so,
+     similar to how loop invariant motion applies extra offset-based
+     disambiguation.  */
+  if (!loop_nest)
+    {
+      aff_tree off1, off2;
+      double_int size1, size2;
+      get_inner_reference_aff (DR_REF (a), &off1, &size1);
+      get_inner_reference_aff (DR_REF (b), &off2, &size2);
+      aff_combination_scale (&off1, double_int_minus_one);
+      aff_combination_add (&off2, &off1);
+      if (aff_comb_cannot_overlap_p (&off2, size1, size2))
+	return false;
+    }
+
   if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
     return refs_output_dependent_p (addr_a, addr_b);
   else if (DR_IS_READ (a) && DR_IS_WRITE (b))
@@ -1331,7 +1353,7 @@ initialize_data_dependence_relation (str
     }
 
   /* If the data references do not alias, then they are independent.  */
-  if (!dr_may_alias_p (a, b))
+  if (!dr_may_alias_p (a, b, loop_nest != NULL))
     {
       DDR_ARE_DEPENDENT (res) = chrec_known;
       return res;
Index: gcc/tree-data-ref.h
===================================================================
--- gcc/tree-data-ref.h	(revision 177983)
+++ gcc/tree-data-ref.h	(working copy)
@@ -431,7 +431,7 @@ extern tree find_data_references_in_bb (
 
 extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
 extern bool dr_may_alias_p (const struct data_reference *,
-			    const struct data_reference *);
+			    const struct data_reference *, bool);
 extern bool dr_equal_offsets_p (struct data_reference *,
                                 struct data_reference *);
 
Index: gcc/graphite-sese-to-poly.c
===================================================================
--- gcc/graphite-sese-to-poly.c	(revision 177983)
+++ gcc/graphite-sese-to-poly.c	(working copy)
@@ -1720,7 +1720,7 @@ write_alias_graph_to_ascii_dimacs (FILE
 
   FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
-      if (dr_may_alias_p (dr1, dr2))
+      if (dr_may_alias_p (dr1, dr2, true))
 	edge_num++;
 
   fprintf (file, "$\n");
@@ -1732,7 +1732,7 @@ write_alias_graph_to_ascii_dimacs (FILE
 
   FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
-      if (dr_may_alias_p (dr1, dr2))
+      if (dr_may_alias_p (dr1, dr2, true))
 	fprintf (file, "e %d %d\n", i + 1, j + 1);
 
   return true;
@@ -1762,7 +1762,7 @@ write_alias_graph_to_ascii_dot (FILE *fi
 
   FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
-      if (dr_may_alias_p (dr1, dr2))
+      if (dr_may_alias_p (dr1, dr2, true))
 	fprintf (file, "n%d n%d\n", i, j);
 
   return true;
@@ -1788,7 +1788,7 @@ write_alias_graph_to_ascii_ecc (FILE *fi
 
   FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
     for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
-      if (dr_may_alias_p (dr1, dr2))
+      if (dr_may_alias_p (dr1, dr2, true))
 	fprintf (file, "%d %d\n", i, j);
 
   return true;
@@ -1824,7 +1824,7 @@ build_alias_set_optimal_p (VEC (data_ref
 
   FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
     for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
-      if (dr_may_alias_p (dr1, dr2))
+      if (dr_may_alias_p (dr1, dr2, true))
 	{
 	  add_edge (g, i, j);
 	  add_edge (g, j, i);