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   /* This field stores the information about the iteration domain
  83      validity of the dependence relation.  */
  84   tree last_conflict;
  85
  86   /* Distance from the iteration that access a conflicting element in
  87      A to the iteration that access this same conflicting element in
  88      B.  The distance is a tree scalar expression, i.e. a constant or a
  89      symbolic expression, but certainly not a chrec function.  */
  90   tree distance;
  91 };
  92
  93 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
  94 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
  95 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
  96 #define SUB_DISTANCE(SUB) SUB->distance
  97
  98 /* A data_dependence_relation represents a relation between two
  99    data_references A and B.  */
 100
 101 struct data_dependence_relation
 102 {
 103
 104   struct data_reference *a;
 105   struct data_reference *b;
 106
 107   /* When the dependence relation is affine, it can be represented by
 108      a distance vector.  */
 109   bool affine_p;
 110
 111   /* A "yes/no/maybe" field for the dependence relation:
 112
 113      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
 114        relation between A and B, and the description of this relation
 115        is given in the SUBSCRIPTS array,
 116
 117      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
 118        SUBSCRIPTS is empty,
 119
 120      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
 121        but the analyzer cannot be more specific.  */
 122   tree are_dependent;
 123
 124   /* For each subscript in the dependence test, there is an element in
 125      this array.  This is the attribute that labels the edge A->B of
 126      the data_dependence_relation.  */
 127   varray_type subscripts;
 128
 129   /* The size of the direction/distance vectors.  */
 130   int size_vect;
 131
 132   /* The classic direction vector.  */
 133   lambda_vector dir_vect;
 134
 135   /* The classic distance vector.  */
 136   lambda_vector dist_vect;
 137 };
 138
 139 #define DDR_A(DDR) DDR->a
 140 #define DDR_B(DDR) DDR->b
 141 #define DDR_AFFINE_P(DDR) DDR->affine_p
 142 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
 143 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
 144 #define DDR_SUBSCRIPTS_VECTOR_INIT(DDR, N) \
 145   VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector");
 146 #define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I)
 147 #define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR))
 148 #define DDR_SIZE_VECT(DDR) DDR->size_vect
 149 #define DDR_DIR_VECT(DDR) DDR->dir_vect
 150 #define DDR_DIST_VECT(DDR) DDR->dist_vect
 151
 152 \f
 153
 154 extern tree find_data_references_in_loop (struct loop *, varray_type *);
 155 extern struct data_dependence_relation *initialize_data_dependence_relation
 156 (struct data_reference *, struct data_reference *);
 157 extern void compute_affine_dependence (struct data_dependence_relation *);
 158 extern void analyze_all_data_dependences (struct loops *);
 159 extern void compute_data_dependences_for_loop (unsigned, struct loop *,
 160                                                varray_type *, varray_type *);
 161 extern struct data_reference * init_data_ref (tree, tree, tree, tree, bool);
 162 extern struct data_reference *analyze_array (tree, tree, bool);
 163
 164 extern void dump_subscript (FILE *, struct subscript *);
 165 extern void dump_ddrs (FILE *, varray_type);
 166 extern void dump_dist_dir_vectors (FILE *, varray_type);
 167 extern void dump_data_reference (FILE *, struct data_reference *);
 168 extern void dump_data_references (FILE *, varray_type);
 169 extern void dump_data_dependence_relation (FILE *,
 170                                            struct data_dependence_relation *);
 171 extern void dump_data_dependence_relations (FILE *, varray_type);
 172 extern void dump_data_dependence_direction (FILE *,
 173                                             enum data_dependence_direction);
 174 extern bool array_base_name_differ_p (struct data_reference *,
 175                                       struct data_reference *, bool *);
 176 extern void free_dependence_relation (struct data_dependence_relation *);
 177 extern void free_dependence_relations (varray_type);
 178 extern void free_data_refs (varray_type);
 179
 180
 181 \f
 182
 183 #endif  /* GCC_TREE_DATA_REF_H  */