data_reference *,
                                struct data_reference *);

extern opt_result runtime_alias_check_p (ddr_p, class loop *, bool);
extern int data_ref_compare_tree (tree, tree);
extern void prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *,
					   poly_uint64);
extern void create_runtime_alias_checks (class loop *,
					 const vec<dr_with_seg_len_pair_t> *,
					 tree*);
extern tree dr_direction_indicator (struct data_reference *);
extern tree dr_zero_step_indicator (struct data_reference *);
extern bool dr_known_forward_stride_p (struct data_reference *);

/* Return true when the base objects of data references A and B are
   the same memory object.  */

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.  Optionally skip the
   last OFFSET dimensions in the data reference.  */

inline bool
same_data_refs (data_reference_p a, data_reference_p b, int offset = 0)
{
  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 = offset; i < DR_NUM_DIMENSIONS (a); i++)
    if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
      return false;

  return true;
}

/* Returns true when all the dependences are computable.  */

inline bool
known_dependences_p (vec<ddr_p> dependence_relations)
{
  ddr_p ddr;
  unsigned int i;

  FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
    if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
      return false;

  return true;
}

/* 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.  */

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.  */

inline unsigned
ddr_dependence_level (ddr_p ddr)
{
  unsigned vector;
  unsigned level = 0;

  if (DDR_DIST_VECTS (ddr).exists ())
    level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));

  for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
    level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
					  DDR_NB_LOOPS (ddr)));
  return level;
}

/* Return the index of the variable VAR in the LOOP_NEST array.  */

inline int
index_in_loop_nest (int var, const vec<loop_p> &loop_nest)
{
  class loop *loopi;
  int var_index;

  for (var_index = 0; loop_nest.iterate (var_index, &loopi); var_index++)
    if (loopi->num == var)
      return var_index;

  gcc_unreachable ();
}

/* Returns true when the data reference DR the form "A[i] = ..."
   with a stride equal to its unit type size.  */

inline bool
adjacent_dr_p (struct data_reference *dr)
{
  /* If this is a bitfield store bail out.  */
  if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
      && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
    return false;

  if (!DR_STEP (dr)
      || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
    return false;

  return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
					 DR_STEP (dr)),
			     TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
}

void split_constant_offset (tree , tree *, tree *);

/* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */

inline lambda_int
lambda_vector_gcd (lambda_vector vector, int size)
{
  int i;
  lambda_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.  */

inline lambda_vector
lambda_vector_new (int size)
{
  /* ???  We shouldn't abuse the GC allocator here.  */
  return ggc_cleared_vec_alloc<lambda_int> (size);
}

/* Clear out vector VEC1 of length SIZE.  */

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.  */

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.  */

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.  */

inline lambda_matrix
lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
{
  lambda_matrix mat;
  int i;

  mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);

  for (i = 0; i < m; i++)
    mat[i] = XOBNEWVEC (lambda_obstack, lambda_int, n);

  return mat;
}

#endif  /* GCC_TREE_DATA_REF_H  */
