gcc/tree-data-ref.h

   1 /* Data references and dependences detectors.
   2    Copyright (C) 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <s.pop@laposte.net>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #ifndef GCC_TREE_DATA_REF_H
  23 #define GCC_TREE_DATA_REF_H
  24
  25 #include "lambda.h"
  26
  27 struct data_reference
  28 {
  29   /* A pointer to the statement that contains this DR.  */
  30   tree stmt;
  31
  32   /* A pointer to the ARRAY_REF node.  */
  33   tree ref;
  34
  35   /* The name of the array.  */
  36   tree base_name;
  37
  38   /* A list of chrecs.  */
  39   varray_type access_fns;
  40
  41   /* Auxiliary info specific to a pass.  */
  42   int aux;
  43
  44   /* True when the data reference is in RHS of a stmt.  */
  45   bool is_read;
  46
  47 };
  48
  49 #define DR_STMT(DR) DR->stmt
  50 #define DR_REF(DR) DR->ref
  51 #define DR_BASE_NAME(DR) DR->base_name
  52 #define DR_ACCESS_FNS(DR) DR->access_fns
  53 #define DR_ACCESS_FN(DR, I) VARRAY_TREE (DR_ACCESS_FNS (DR), I)
  54 #define DR_NUM_DIMENSIONS(DR) VARRAY_ACTIVE_SIZE (DR_ACCESS_FNS (DR))
  55 #define DR_IS_READ(DR) DR->is_read
  56
  57 enum data_dependence_direction {
  58   dir_positive,
  59   dir_negative,
  60   dir_equal,
  61   dir_positive_or_negative,
  62   dir_positive_or_equal,
  63   dir_negative_or_equal,
  64   dir_star,
  65   dir_independent
  66 };
  67
  68 /* What is a subscript?  Given two array accesses a subscript is the
  69    tuple composed of the access functions for a given dimension.
  70    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
  71    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
  72    are stored in the data_dependence_relation structure under the form
  73    of an array of subscripts.  */
  74
  75 struct subscript
  76 {
  77   /* A description of the iterations for which the elements are
  78      accessed twice.  */
  79   tree conflicting_iterations_in_a;
  80   tree conflicting_iterations_in_b;
  81
  82   /* These fields store the information about the iteration domain
  83      validity of the dependence relation.  */
  84   tree last_conflict_in_a;
  85   tree last_conflict_in_b;
  86
  87   /* Distance from the iteration that access a conflicting element in
  88      A to the iteration that access this same conflicting element in
  89      B.  The distance is a tree scalar expression, i.e. a constant or a
  90      symbolic expression, but certainly not a chrec function.  */
  91   tree distance;
  92 };
  93
  94 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
  95 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
  96 #define SUB_LAST_CONFLICT_IN_A(SUB) SUB->last_conflict_in_a
  97 #define SUB_LAST_CONFLICT_IN_B(SUB) SUB->last_conflict_in_b
  98 #define SUB_DISTANCE(SUB) SUB->distance
  99
 100 /* A data_dependence_relation represents a relation between two
 101    data_references A and B.  */
 102
 103 struct data_dependence_relation
 104 {
 105
 106   struct data_reference *a;
 107   struct data_reference *b;
 108
 109   /* A "yes/no/maybe" field for the dependence relation:
 110
 111      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
 112        relation between A and B, and the description of this relation
 113        is given in the SUBSCRIPTS array,
 114
 115      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
 116        SUBSCRIPTS is empty,
 117
 118      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
 119        but the analyzer cannot be more specific.  */
 120   tree are_dependent;
 121
 122   /* For each subscript in the dependence test, there is an element in
 123      this array.  This is the attribute that labels the edge A->B of
 124      the data_dependence_relation.  */
 125   varray_type subscripts;
 126
 127   /* The classic direction vector.  */
 128   lambda_vector dir_vect;
 129
 130   /* The classic distance vector.  */
 131   lambda_vector dist_vect;
 132 };
 133
 134 #define DDR_A(DDR) DDR->a
 135 #define DDR_B(DDR) DDR->b
 136 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
 137 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
 138 #define DDR_SUBSCRIPTS_VECTOR_INIT(DDR, N) \
 139   VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector");
 140 #define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I)
 141 #define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR))
 142 #define DDR_DIR_VECT(DDR) DDR->dir_vect
 143 #define DDR_DIST_VECT(DDR) DDR->dist_vect
 144
 145 \f
 146
 147 struct data_dependence_relation *initialize_data_dependence_relation
 148 (struct data_reference *, struct data_reference *);
 149 void compute_affine_dependence (struct data_dependence_relation *);
 150 extern void analyze_all_data_dependences (struct loops *);
 151 extern void compute_data_dependences_for_loop (unsigned, struct loop *,
 152                                                varray_type *, varray_type *);
 153 extern struct data_reference * init_data_ref (tree, tree, tree, tree, bool);
 154 extern struct data_reference *analyze_array (tree, tree, bool);
 155
 156 extern void dump_data_reference (FILE *, struct data_reference *);
 157 extern void dump_data_references (FILE *, varray_type);
 158 extern void dump_data_dependence_relation (FILE *,
 159                                            struct data_dependence_relation *);
 160 extern void dump_data_dependence_relations (FILE *, varray_type);
 161 extern void dump_data_dependence_direction (FILE *,
 162                                             enum data_dependence_direction);
 163 extern bool array_base_name_differ_p (struct data_reference *,
 164                                       struct data_reference *, bool *p);
 165 extern void free_dependence_relation (struct data_dependence_relation *);
 166 extern void free_dependence_relations (varray_type);
 167 extern void free_data_refs (varray_type);
 168
 169 \f
 170
 171 #endif  /* GCC_TREE_DATA_REF_H  */