/* 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>
#define GCC_TREE_DATA_REF_H
#include "graphds.h"
-#include "lambda.h"
#include "omega.h"
#include "tree-chrec.h"
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
#define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I)
#define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR))
#define DR_IS_READ(DR) (DR)->is_read
+#define DR_IS_WRITE(DR) (!DR_IS_READ (DR))
#define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
#define DR_OFFSET(DR) (DR)->innermost.offset
#define DR_INIT(DR) (DR)->innermost.init
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,
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
+ the same memory object. */
+
+static inline bool
+same_data_refs_base_objects (data_reference_p a, data_reference_p b)
+{
+ return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
+ && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
+}
+
+/* Return true when the data references A and B are accessing the same
+ memory object with the same access functions. */
+
+static inline bool
+same_data_refs (data_reference_p a, data_reference_p b)
+{
+ unsigned int i;
+
+ /* The references are exactly the same. */
+ if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
+ return true;
+
+ if (!same_data_refs_base_objects (a, b))
+ return false;
+
+ for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
+ if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
+ return false;
+
+ return true;
+}
/* Return true when the DDR contains two data references that have the
same access functions. */
{
return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
&& DR_IS_READ (DDR_A (ddr))
- && !DR_IS_READ (DDR_B (ddr))
+ && DR_IS_WRITE (DDR_B (ddr))
&& !same_access_functions (ddr));
}
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
#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 *);
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. */
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 *);
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 */
OSDN Git Service
