OSDN Git Service

2011-07-01 Jonathan Wakely <jwakely.gcc@gmail.com>
[pf3gnuchains/gcc-fork.git] / gcc / tree-data-ref.h
index d929f31..0588136 100644 (file)
@@ -1,5 +1,5 @@
 /* Data references and dependences detectors.
-   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
    Free Software Foundation, Inc.
    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
 
@@ -23,7 +23,6 @@ along with GCC; see the file COPYING3.  If not see
 #define GCC_TREE_DATA_REF_H
 
 #include "graphds.h"
-#include "lambda.h"
 #include "omega.h"
 #include "tree-chrec.h"
 
@@ -96,6 +95,19 @@ struct dr_alias
   bitmap vops;
 };
 
+/* An integer vector.  A vector formally consists of an element of a vector
+   space. A vector space is a set that is closed under vector addition
+   and scalar multiplication.  In this vector space, an element is a list of
+   integers.  */
+typedef int *lambda_vector;
+DEF_VEC_P(lambda_vector);
+DEF_VEC_ALLOC_P(lambda_vector,heap);
+DEF_VEC_ALLOC_P(lambda_vector,gc);
+
+/* An integer matrix.  A matrix consists of m vectors of length n (IE
+   all vectors are the same length).  */
+typedef lambda_vector *lambda_matrix;
+
 /* Each vector of the access matrix represents a linear access
    function for a subscript.  First elements correspond to the
    leftmost indices, ie. for a[i][j] the first vector corresponds to
@@ -376,6 +388,7 @@ DEF_VEC_ALLOC_O (data_ref_loc, heap);
 bool get_references_in_stmt (gimple, VEC (data_ref_loc, heap) **);
 bool dr_analyze_innermost (struct data_reference *);
 extern bool compute_data_dependences_for_loop (struct loop *, bool,
+                                              VEC (loop_p, heap) **,
                                               VEC (data_reference_p, heap) **,
                                               VEC (ddr_p, heap) **);
 extern bool compute_data_dependences_for_bb (basic_block, bool,
@@ -406,17 +419,21 @@ extern void free_data_ref (data_reference_p);
 extern void free_data_refs (VEC (data_reference_p, heap) *);
 extern bool find_data_references_in_stmt (struct loop *, gimple,
                                          VEC (data_reference_p, heap) **);
-extern bool graphite_find_data_references_in_stmt (struct loop *, gimple,
+extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple,
                                                   VEC (data_reference_p, heap) **);
-struct data_reference *create_data_ref (struct loop *, tree, gimple, bool);
+struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool);
 extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
 extern void compute_all_dependences (VEC (data_reference_p, heap) *,
                                     VEC (ddr_p, heap) **, VEC (loop_p, heap) *,
                                     bool);
+extern tree find_data_references_in_bb (struct loop *, basic_block,
+                                        VEC (data_reference_p, heap) **);
 
 extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
 extern bool dr_may_alias_p (const struct data_reference *,
                            const struct data_reference *);
+extern bool dr_equal_offsets_p (struct data_reference *,
+                                struct data_reference *);
 
 
 /* Return true when the base objects of data references A and B are
@@ -493,6 +510,22 @@ ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations)
   return false;
 }
 
+/* Returns the dependence level for a vector DIST of size LENGTH.
+   LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
+   to the sequence of statements, not carried by any loop.  */
+
+static inline unsigned
+dependence_level (lambda_vector dist_vect, int length)
+{
+  int i;
+
+  for (i = 0; i < length; i++)
+    if (dist_vect[i] != 0)
+      return i + 1;
+
+  return 0;
+}
+
 /* Return the dependence level for the DDR relation.  */
 
 static inline unsigned
@@ -577,7 +610,10 @@ typedef struct rdg_edge
 #define RDGE_LEVEL(E)       ((struct rdg_edge *) ((E)->data))->level
 #define RDGE_RELATION(E)    ((struct rdg_edge *) ((E)->data))->relation
 
-struct graph *build_rdg (struct loop *);
+struct graph *build_rdg (struct loop *,
+                        VEC (loop_p, heap) **,
+                        VEC (ddr_p, heap) **,
+                        VEC (data_reference_p, heap) **);
 struct graph *build_empty_rdg (int);
 void free_rdg (struct graph *);
 
@@ -602,6 +638,7 @@ void stores_zero_from_loop (struct loop *, VEC (gimple, heap) **);
 void remove_similar_memory_refs (VEC (gimple, heap) **);
 bool rdg_defs_used_in_other_loops_p (struct graph *, int);
 bool have_similar_memory_accesses (gimple, gimple);
+bool stmt_with_adjacent_zero_store_dr_p (gimple);
 
 /* Returns true when STRIDE is equal in absolute value to the size of
    the unit type of TYPE.  */
@@ -624,16 +661,6 @@ rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2)
                                       RDG_STMT (rdg, v2));
 }
 
-/* In lambda-code.c  */
-bool lambda_transform_legal_p (lambda_trans_matrix, int,
-                              VEC (ddr_p, heap) *);
-void lambda_collect_parameters (VEC (data_reference_p, heap) *,
-                               VEC (tree, heap) **);
-bool lambda_compute_access_matrices (VEC (data_reference_p, heap) *,
-                                    VEC (tree, heap) *,
-                                    VEC (loop_p, heap) *,
-                                    struct obstack *);
-
 /* In tree-data-ref.c  */
 void split_constant_offset (tree , tree *, tree *);
 
@@ -651,4 +678,86 @@ DEF_VEC_ALLOC_P (rdgc, heap);
 DEF_VEC_P (bitmap);
 DEF_VEC_ALLOC_P (bitmap, heap);
 
+/* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
+
+static inline int
+lambda_vector_gcd (lambda_vector vector, int size)
+{
+  int i;
+  int gcd1 = 0;
+
+  if (size > 0)
+    {
+      gcd1 = vector[0];
+      for (i = 1; i < size; i++)
+       gcd1 = gcd (gcd1, vector[i]);
+    }
+  return gcd1;
+}
+
+/* Allocate a new vector of given SIZE.  */
+
+static inline lambda_vector
+lambda_vector_new (int size)
+{
+  return (lambda_vector) ggc_alloc_cleared_atomic (sizeof (int) * size);
+}
+
+/* Clear out vector VEC1 of length SIZE.  */
+
+static inline void
+lambda_vector_clear (lambda_vector vec1, int size)
+{
+  memset (vec1, 0, size * sizeof (*vec1));
+}
+
+/* Returns true when the vector V is lexicographically positive, in
+   other words, when the first nonzero element is positive.  */
+
+static inline bool
+lambda_vector_lexico_pos (lambda_vector v,
+                         unsigned n)
+{
+  unsigned i;
+  for (i = 0; i < n; i++)
+    {
+      if (v[i] == 0)
+       continue;
+      if (v[i] < 0)
+       return false;
+      if (v[i] > 0)
+       return true;
+    }
+  return true;
+}
+
+/* Return true if vector VEC1 of length SIZE is the zero vector.  */
+
+static inline bool
+lambda_vector_zerop (lambda_vector vec1, int size)
+{
+  int i;
+  for (i = 0; i < size; i++)
+    if (vec1[i] != 0)
+      return false;
+  return true;
+}
+
+/* Allocate a matrix of M rows x  N cols.  */
+
+static inline lambda_matrix
+lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
+{
+  lambda_matrix mat;
+  int i;
+
+  mat = (lambda_matrix) obstack_alloc (lambda_obstack,
+                                      sizeof (lambda_vector *) * m);
+
+  for (i = 0; i < m; i++)
+    mat[i] = lambda_vector_new (n);
+
+  return mat;
+}
+
 #endif  /* GCC_TREE_DATA_REF_H  */