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 struct data_reference GTY(())
  26 {
  27   /* An identifier.  */
  28   unsigned int id;
  29
  30   /* A pointer to the statement that contains this DR.  */
  31   tree stmt;
  32
  33   /* A pointer to the ARRAY_REF node.  */
  34   tree ref;
  35
  36   /* The name of the array.  */
  37   tree base_name;
  38
  39   /* A list of chrecs.  */
  40   varray_type access_fns;
  41
  42   /* Auxiliary info specific to a pass.  */
  43   int aux;
  44
  45   /* True when the data reference is in RHS of a stmt.  */
  46   bool is_read;
  47
  48 };
  49
  50 #define DR_ID(DR) DR->id
  51 #define DR_STMT(DR) DR->stmt
  52 #define DR_REF(DR) DR->ref
  53 #define DR_BASE_NAME(DR) DR->base_name
  54 #define DR_ACCESS_FNS(DR) DR->access_fns
  55 #define DR_ACCESS_FN(DR, I) VARRAY_TREE (DR_ACCESS_FNS (DR), I)
  56 #define DR_NUM_DIMENSIONS(DR) VARRAY_ACTIVE_SIZE (DR_ACCESS_FNS (DR))
  57 #define DR_IS_READ(DR) DR->is_read
  58
  59 enum data_dependence_direction {
  60   dir_positive,
  61   dir_negative,
  62   dir_equal,
  63   dir_positive_or_negative,
  64   dir_positive_or_equal,
  65   dir_negative_or_equal,
  66   dir_star,
  67   dir_independent
  68 };
  69
  70 /* What is a subscript?  Given two array accesses a subscript is the
  71    tuple composed of the access functions for a given dimension.
  72    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
  73    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
  74    are stored in the data_dependence_relation structure under the form
  75    of an array of subscripts.  */
  76
  77 struct subscript GTY(())
  78 {
  79   /* A description of the iterations for which the elements are
  80      accessed twice.  */
  81   tree conflicting_iterations_in_a;
  82   tree conflicting_iterations_in_b;
  83
  84   /* These fields store the information about the iteration domain
  85      validity of the dependence relation.  */
  86   tree last_conflict_in_a;
  87   tree last_conflict_in_b;
  88
  89   /* Distance from the iteration that access a conflicting element in
  90      A to the iteration that access this same conflicting element in
  91      B.  The distance is a tree scalar expression, ie. a constant or a
  92      symbolic expression, but certainly not a chrec function.  */
  93   tree distance;
  94
  95   /* Direction (or sign) of the distance.  This more abstract (less
  96      precise) information is extracted from the distance field, for
  97      the convenience of some analyzers.  */
  98   enum data_dependence_direction direction;
  99 };
 100
 101 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
 102 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
 103 #define SUB_LAST_CONFLICT_IN_A(SUB) SUB->last_conflict_in_a
 104 #define SUB_LAST_CONFLICT_IN_B(SUB) SUB->last_conflict_in_b
 105 #define SUB_DISTANCE(SUB) SUB->distance
 106 #define SUB_DIRECTION(SUB) SUB->direction
 107
 108 /* A data_dependence_relation represents a relation between two
 109    data_references A and B.  */
 110
 111 struct data_dependence_relation GTY(())
 112 {
 113
 114   struct data_reference *a;
 115   struct data_reference *b;
 116
 117   /* A "yes/no/maybe" field for the dependence relation:
 118
 119      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
 120        relation between A and B, and the description of this relation
 121        is given in the SUBSCRIPTS array,
 122
 123      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
 124        SUBSCRIPTS is empty,
 125
 126      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
 127        but the analyzer cannot be more specific.  */
 128   tree are_dependent;
 129
 130   /* For each subscript in the dependence test, there is an element in
 131      this array.  This is the attribute that labels the edge A->B of
 132      the data_dependence_relation.  */
 133   varray_type subscripts;
 134 };
 135
 136 #define DDR_A(DDR) DDR->a
 137 #define DDR_B(DDR) DDR->b
 138 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
 139 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
 140 #define DDR_SUBSCRIPTS_VECTOR_INIT(DDR, N) \
 141   VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector");
 142 #define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I)
 143 #define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR))
 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                                                varray_type *, varray_type *);
 154 extern struct data_reference * init_data_ref (tree, tree, tree, tree);
 155 extern struct data_reference *analyze_array (tree, tree, bool);
 156
 157 extern void dump_data_reference (FILE *, struct data_reference *);
 158 extern void dump_data_references (FILE *, varray_type);
 159 extern void dump_data_dependence_relation (FILE *,
 160                                            struct data_dependence_relation *);
 161 extern void dump_data_dependence_relations (FILE *, varray_type);
 162 extern void dump_data_dependence_direction (FILE *,
 163                                             enum data_dependence_direction);
 164
 165 \f
 166
 167 /* Inline functions.  */
 168
 169 /* This is the simplest data dependence test: determines whether the
 170    data references A and B access the same array.  */
 171
 172 static inline bool
 173 array_base_name_differ_p (struct data_reference *a,
 174                           struct data_reference *b)
 175 {
 176   if (DR_BASE_NAME (a) == DR_BASE_NAME (b))
 177     return false;
 178
 179   if (TREE_CODE (DR_BASE_NAME (a)) == INDIRECT_REF
 180       && TREE_CODE (DR_BASE_NAME (b)) == INDIRECT_REF
 181       && TREE_OPERAND (DR_BASE_NAME (a), 0)
 182       == TREE_OPERAND (DR_BASE_NAME (b), 0))
 183     return false;
 184
 185   return true;
 186 }
 187
 188 #endif  /* GCC_TREE_DATA_REF_H  */