+#include "omega.h"
+#include "tree-chrec.h"
+
+/*
+ innermost_loop_behavior describes the evolution of the address of the memory
+ reference in the innermost enclosing loop. The address is expressed as
+ BASE + STEP * # of iteration, and base is further decomposed as the base
+ pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and
+ constant offset (INIT). Examples, in loop nest
+
+ for (i = 0; i < 100; i++)
+ for (j = 3; j < 100; j++)
+
+ Example 1 Example 2
+ data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
+
+
+ innermost_loop_behavior
+ base_address &a p
+ offset i * D_i x
+ init 3 * D_j + offsetof (b) 28
+ step D_j 4
+
+ */
+struct innermost_loop_behavior
+{
+ tree base_address;
+ tree offset;
+ tree init;
+ tree step;
+
+ /* Alignment information. ALIGNED_TO is set to the largest power of two
+ that divides OFFSET. */
+ tree aligned_to;
+};
+
+/* Describes the evolutions of indices of the memory reference. The indices
+ are indices of the ARRAY_REFs and the operands of INDIRECT_REFs.
+ For ARRAY_REFs, BASE_OBJECT is the reference with zeroed indices
+ (note that this reference does not have to be valid, if zero does not
+ belong to the range of the array; hence it is not recommended to use
+ BASE_OBJECT in any code generation). For INDIRECT_REFs, the address is
+ set to the loop-invariant part of the address of the object, except for
+ the constant offset. For the examples above,
+
+ base_object: a[0].b[0][0] *(p + x + 4B * j_0)
+ indices: {j_0, +, 1}_2 {16, +, 4}_2
+ {i_0, +, 1}_1
+ {j_0, +, 1}_2
+*/
+
+struct indices
+{
+ /* The object. */
+ tree base_object;
+
+ /* A list of chrecs. Access functions of the indices. */
+ VEC(tree,heap) *access_fns;
+};
+
+struct dr_alias
+{
+ /* The alias information that should be used for new pointers to this
+ location. SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG. */
+ tree symbol_tag;
+ struct ptr_info_def *ptr_info;
+
+ /* The set of virtual operands corresponding to this memory reference,
+ serving as a description of the alias information for the memory
+ reference. This could be eliminated if we had alias oracle. */
+ bitmap vops;
+};
+
+/* 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
+ the subscript in "i". The elements of a vector are relative to
+ the loop nests in which the data reference is considered,
+ i.e. the vector is relative to the SCoP that provides the context
+ in which this data reference occurs.
+
+ For example, in
+
+ | loop_1
+ | loop_2
+ | a[i+3][2*j+n-1]
+
+ if "i" varies in loop_1 and "j" varies in loop_2, the access
+ matrix with respect to the loop nest {loop_1, loop_2} is:
+
+ | loop_1 loop_2 param_n cst
+ | 1 0 0 3
+ | 0 2 1 -1
+
+ whereas the access matrix with respect to loop_2 considers "i" as
+ a parameter:
+
+ | loop_2 param_i param_n cst
+ | 0 1 0 3
+ | 2 0 1 -1
+*/
+struct access_matrix
+{
+ int loop_nest_num;
+ int nb_induction_vars;
+ VEC (tree, heap) *parameters;
+ VEC (lambda_vector, heap) *matrix;
+};
+
+#define AM_LOOP_NEST_NUM(M) (M)->loop_nest_num
+#define AM_NB_INDUCTION_VARS(M) (M)->nb_induction_vars
+#define AM_PARAMETERS(M) (M)->parameters
+#define AM_MATRIX(M) (M)->matrix
+#define AM_NB_PARAMETERS(M) (VEC_length (tree, AM_PARAMETERS(M)))
+#define AM_CONST_COLUMN_INDEX(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M))
+#define AM_NB_COLUMNS(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1)
+#define AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I) VEC_index (lambda_vector, AM_MATRIX (M), I)
+#define AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J) AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J]
+
+/* Return the column in the access matrix of LOOP_NUM. */
+
+static inline int
+am_vector_index_for_loop (struct access_matrix *access_matrix, int loop_num)
+{
+ gcc_assert (loop_num >= AM_LOOP_NEST_NUM (access_matrix));
+ return loop_num - AM_LOOP_NEST_NUM (access_matrix);
+}
+
+int access_matrix_get_index_for_parameter (tree, struct access_matrix *);