+/* A Reduced Dependence Graph (RDG) vertex representing a statement. */
+typedef struct rdg_vertex
+{
+ /* The statement represented by this vertex. */
+ gimple stmt;
+
+ /* True when the statement contains a write to memory. */
+ bool has_mem_write;
+
+ /* True when the statement contains a read from memory. */
+ bool has_mem_reads;
+} *rdg_vertex_p;
+
+#define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
+#define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
+#define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
+#define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
+#define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
+#define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
+
+void dump_rdg_vertex (FILE *, struct graph *, int);
+void debug_rdg_vertex (struct graph *, int);
+void dump_rdg_component (FILE *, struct graph *, int, bitmap);
+void debug_rdg_component (struct graph *, int);
+void dump_rdg (FILE *, struct graph *);
+void debug_rdg (struct graph *);
+int rdg_vertex_for_stmt (struct graph *, gimple);
+
+/* Data dependence type. */
+
+enum rdg_dep_type
+{
+ /* Read After Write (RAW). */
+ flow_dd = 'f',
+
+ /* Write After Read (WAR). */
+ anti_dd = 'a',
+
+ /* Write After Write (WAW). */
+ output_dd = 'o',
+
+ /* Read After Read (RAR). */
+ input_dd = 'i'
+};
+
+/* Dependence information attached to an edge of the RDG. */
+
+typedef struct rdg_edge
+{
+ /* Type of the dependence. */
+ enum rdg_dep_type type;
+
+ /* Levels of the dependence: the depth of the loops that carry the
+ dependence. */
+ unsigned level;
+
+ /* Dependence relation between data dependences, NULL when one of
+ the vertices is a scalar. */
+ ddr_p relation;
+} *rdg_edge_p;
+
+#define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
+#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 *,
+ VEC (loop_p, heap) **,
+ VEC (ddr_p, heap) **,
+ VEC (data_reference_p, heap) **);
+struct graph *build_empty_rdg (int);
+void free_rdg (struct graph *);
+
+/* Return the index of the variable VAR in the LOOP_NEST array. */
+
+static inline int
+index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
+{
+ struct loop *loopi;
+ int var_index;
+
+ for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
+ var_index++)
+ if (loopi->num == var)
+ break;
+
+ return var_index;
+}
+
+void stores_from_loop (struct loop *, VEC (gimple, heap) **);
+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. */
+
+static inline bool
+stride_of_unit_type_p (tree stride, tree type)
+{
+ return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (stride),
+ stride),
+ TYPE_SIZE_UNIT (type));
+}
+
+/* Determines whether RDG vertices V1 and V2 access to similar memory
+ locations, in which case they have to be in the same partition. */
+
+static inline bool
+rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2)
+{
+ return have_similar_memory_accesses (RDG_STMT (rdg, v1),
+ RDG_STMT (rdg, v2));
+}
+
+/* In tree-data-ref.c */
+void split_constant_offset (tree , tree *, tree *);
+
+/* Strongly connected components of the reduced data dependence graph. */
+
+typedef struct rdg_component
+{
+ int num;
+ VEC (int, heap) *vertices;
+} *rdgc;
+
+DEF_VEC_P (rdgc);
+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;
+}
+