| /* Data references and dependences detectors. |
| Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. |
| Contributed by Sebastian Pop <pop@cri.ensmp.fr> |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify it under |
| the terms of the GNU General Public License as published by the Free |
| Software Foundation; either version 2, or (at your option) any later |
| version. |
| |
| GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
| WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING. If not, write to the Free |
| Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA |
| 02110-1301, USA. */ |
| |
| #ifndef GCC_TREE_DATA_REF_H |
| #define GCC_TREE_DATA_REF_H |
| |
| #include "lambda.h" |
| |
| /** {base_address + offset + init} is the first location accessed by data-ref |
| in the loop, and step is the stride of data-ref in the loop in bytes; |
| e.g.: |
| |
| Example 1 Example 2 |
| data-ref a[j].b[i][j] a + x + 16B (a is int*) |
| |
| First location info: |
| base_address &a a |
| offset j_0*D_j + i_0*D_i + C_a x |
| init C_b 16 |
| step D_j 4 |
| access_fn NULL {16, +, 1} |
| |
| Base object info: |
| base_object a NULL |
| access_fn <access_fns of indexes of b> NULL |
| |
| **/ |
| struct first_location_in_loop |
| { |
| tree base_address; |
| tree offset; |
| tree init; |
| tree step; |
| /* Access function related to first location in the loop. */ |
| VEC(tree,heap) *access_fns; |
| |
| }; |
| |
| struct base_object_info |
| { |
| /* The object. */ |
| tree base_object; |
| |
| /* A list of chrecs. Access functions related to BASE_OBJECT. */ |
| VEC(tree,heap) *access_fns; |
| }; |
| |
| enum data_ref_type { |
| ARRAY_REF_TYPE, |
| POINTER_REF_TYPE |
| }; |
| |
| struct data_reference |
| { |
| /* A pointer to the statement that contains this DR. */ |
| tree stmt; |
| |
| /* A pointer to the ARRAY_REF node. */ |
| tree ref; |
| |
| /* Auxiliary info specific to a pass. */ |
| int aux; |
| |
| /* True when the data reference is in RHS of a stmt. */ |
| bool is_read; |
| |
| /* First location accessed by the data-ref in the loop. */ |
| struct first_location_in_loop first_location; |
| |
| /* Base object related info. */ |
| struct base_object_info object_info; |
| |
| /* Aliasing information. This field represents the symbol that |
| should be aliased by a pointer holding the address of this data |
| reference. If the original data reference was a pointer |
| dereference, then this field contains the memory tag that should |
| be used by the new vector-pointer. */ |
| tree memtag; |
| struct ptr_info_def *ptr_info; |
| subvar_t subvars; |
| |
| /* Alignment information. */ |
| /* The offset of the data-reference from its base in bytes. */ |
| tree misalignment; |
| /* The maximum data-ref's alignment. */ |
| tree aligned_to; |
| |
| /* The type of the data-ref. */ |
| enum data_ref_type type; |
| }; |
| |
| typedef struct data_reference *data_reference_p; |
| DEF_VEC_P(data_reference_p); |
| DEF_VEC_ALLOC_P (data_reference_p, heap); |
| |
| #define DR_STMT(DR) (DR)->stmt |
| #define DR_REF(DR) (DR)->ref |
| #define DR_BASE_OBJECT(DR) (DR)->object_info.base_object |
| #define DR_TYPE(DR) (DR)->type |
| #define DR_ACCESS_FNS(DR)\ |
| (DR_TYPE(DR) == ARRAY_REF_TYPE ? \ |
| (DR)->object_info.access_fns : (DR)->first_location.access_fns) |
| #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_BASE_ADDRESS(DR) (DR)->first_location.base_address |
| #define DR_OFFSET(DR) (DR)->first_location.offset |
| #define DR_INIT(DR) (DR)->first_location.init |
| #define DR_STEP(DR) (DR)->first_location.step |
| #define DR_MEMTAG(DR) (DR)->memtag |
| #define DR_ALIGNED_TO(DR) (DR)->aligned_to |
| #define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment |
| #define DR_PTR_INFO(DR) (DR)->ptr_info |
| #define DR_SUBVARS(DR) (DR)->subvars |
| |
| #define DR_ACCESS_FNS_ADDR(DR) \ |
| (DR_TYPE(DR) == ARRAY_REF_TYPE ? \ |
| &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns)) |
| #define DR_SET_ACCESS_FNS(DR, ACC_FNS) \ |
| { \ |
| if (DR_TYPE(DR) == ARRAY_REF_TYPE) \ |
| (DR)->object_info.access_fns = ACC_FNS; \ |
| else \ |
| (DR)->first_location.access_fns = ACC_FNS; \ |
| } |
| #define DR_FREE_ACCESS_FNS(DR) \ |
| { \ |
| if (DR_TYPE(DR) == ARRAY_REF_TYPE) \ |
| VEC_free (tree, heap, (DR)->object_info.access_fns); \ |
| else \ |
| VEC_free (tree, heap, (DR)->first_location.access_fns); \ |
| } |
| |
| enum data_dependence_direction { |
| dir_positive, |
| dir_negative, |
| dir_equal, |
| dir_positive_or_negative, |
| dir_positive_or_equal, |
| dir_negative_or_equal, |
| dir_star, |
| dir_independent |
| }; |
| |
| /* What is a subscript? Given two array accesses a subscript is the |
| tuple composed of the access functions for a given dimension. |
| Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three |
| subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts |
| are stored in the data_dependence_relation structure under the form |
| of an array of subscripts. */ |
| |
| struct subscript |
| { |
| /* A description of the iterations for which the elements are |
| accessed twice. */ |
| tree conflicting_iterations_in_a; |
| tree conflicting_iterations_in_b; |
| |
| /* This field stores the information about the iteration domain |
| validity of the dependence relation. */ |
| tree last_conflict; |
| |
| /* Distance from the iteration that access a conflicting element in |
| A to the iteration that access this same conflicting element in |
| B. The distance is a tree scalar expression, i.e. a constant or a |
| symbolic expression, but certainly not a chrec function. */ |
| tree distance; |
| }; |
| |
| typedef struct subscript *subscript_p; |
| DEF_VEC_P(subscript_p); |
| DEF_VEC_ALLOC_P (subscript_p, heap); |
| |
| #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a |
| #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b |
| #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict |
| #define SUB_DISTANCE(SUB) SUB->distance |
| |
| typedef struct loop *loop_p; |
| DEF_VEC_P(loop_p); |
| DEF_VEC_ALLOC_P (loop_p, heap); |
| |
| /* A data_dependence_relation represents a relation between two |
| data_references A and B. */ |
| |
| struct data_dependence_relation |
| { |
| |
| struct data_reference *a; |
| struct data_reference *b; |
| |
| /* When the dependence relation is affine, it can be represented by |
| a distance vector. */ |
| bool affine_p; |
| |
| /* A "yes/no/maybe" field for the dependence relation: |
| |
| - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence |
| relation between A and B, and the description of this relation |
| is given in the SUBSCRIPTS array, |
| |
| - when "ARE_DEPENDENT == chrec_known", there is no dependence and |
| SUBSCRIPTS is empty, |
| |
| - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, |
| but the analyzer cannot be more specific. */ |
| tree are_dependent; |
| |
| /* For each subscript in the dependence test, there is an element in |
| this array. This is the attribute that labels the edge A->B of |
| the data_dependence_relation. */ |
| VEC (subscript_p, heap) *subscripts; |
| |
| /* The analyzed loop nest. */ |
| VEC (loop_p, heap) *loop_nest; |
| |
| /* The classic direction vector. */ |
| VEC (lambda_vector, heap) *dir_vects; |
| |
| /* The classic distance vector. */ |
| VEC (lambda_vector, heap) *dist_vects; |
| }; |
| |
| typedef struct data_dependence_relation *ddr_p; |
| DEF_VEC_P(ddr_p); |
| DEF_VEC_ALLOC_P(ddr_p,heap); |
| |
| #define DDR_A(DDR) DDR->a |
| #define DDR_B(DDR) DDR->b |
| #define DDR_AFFINE_P(DDR) DDR->affine_p |
| #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent |
| #define DDR_SUBSCRIPTS(DDR) DDR->subscripts |
| #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I) |
| #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR)) |
| |
| #define DDR_LOOP_NEST(DDR) DDR->loop_nest |
| /* The size of the direction/distance vectors: the number of loops in |
| the loop nest. */ |
| #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR))) |
| |
| #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects) |
| #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects) |
| #define DDR_NUM_DIST_VECTS(DDR) \ |
| (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR))) |
| #define DDR_NUM_DIR_VECTS(DDR) \ |
| (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR))) |
| #define DDR_DIR_VECT(DDR, I) \ |
| VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I) |
| #define DDR_DIST_VECT(DDR, I) \ |
| VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I) |
| |
| |
| |
| extern tree find_data_references_in_loop (struct loop *, |
| VEC (data_reference_p, heap) **); |
| extern void compute_data_dependences_for_loop (struct loop *, bool, |
| VEC (data_reference_p, heap) **, |
| VEC (ddr_p, heap) **); |
| extern void print_direction_vector (FILE *, lambda_vector, int); |
| extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int); |
| extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int); |
| extern void dump_subscript (FILE *, struct subscript *); |
| extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *); |
| extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *); |
| extern void dump_data_reference (FILE *, struct data_reference *); |
| extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *); |
| extern void debug_data_dependence_relation (struct data_dependence_relation *); |
| extern void dump_data_dependence_relation (FILE *, |
| struct data_dependence_relation *); |
| extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *); |
| extern void dump_data_dependence_direction (FILE *, |
| enum data_dependence_direction); |
| extern void free_dependence_relation (struct data_dependence_relation *); |
| extern void free_dependence_relations (VEC (ddr_p, heap) *); |
| extern void free_data_refs (VEC (data_reference_p, heap) *); |
| extern struct data_reference *analyze_array (tree, tree, bool); |
| extern void estimate_iters_using_array (tree, tree); |
| |
| |
| /* 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; |
| } |
| |
| /* In lambda-code.c */ |
| bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *); |
| |
| #endif /* GCC_TREE_DATA_REF_H */ |
