scop_plus.cc

   1 /*
   2  * Copyright 2011 Leiden University. All rights reserved.
   3  * Copyright 2013 Ecole Normale Superieure. All rights reserved.
   4  * Copyright 2017 Sven Verdoolaege. All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  *    1. Redistributions of source code must retain the above copyright
  11  *       notice, this list of conditions and the following disclaimer.
  12  *
  13  *    2. Redistributions in binary form must reproduce the above
  14  *       copyright notice, this list of conditions and the following
  15  *       disclaimer in the documentation and/or other materials provided
  16  *       with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
  19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  21  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
  22  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  23  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  24  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
  25  * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  * The views and conclusions contained in the software and documentation
  31  * are those of the authors and should not be interpreted as
  32  * representing official policies, either expressed or implied, of
  33  * Leiden University.
  34  */
  35
  36 #include <set>
  37 #include <vector>
  38
  39 #include "clang.h"
  40 #include "expr.h"
  41 #include "id.h"
  42 #include "scop_plus.h"
  43 #include "tree.h"
  44
  45 using namespace std;
  46 using namespace clang;
  47
  48 /* Add the sequence of nested arrays of structures of the direct
  49  * subfields of the record type represented by "ancestors"
  50  * to "arrays".  The final element in the sequence is guaranteed
  51  * to refer to a record type.
  52  *
  53  * If any of the subfields is anonymous, then add its subfields as well.
  54  */
  55 static void collect_direct_sub_arrays(ValueDecl *decl,
  56         __isl_keep isl_id_list *ancestors, array_desc_set &arrays)
  57 {
  58         isl_ctx *ctx;
  59         QualType type = decl->getType();
  60         RecordDecl *record;
  61         RecordDecl::field_iterator it;
  62
  63         type = pet_clang_base_type(type);
  64         record = pet_clang_record_decl(type);
  65
  66         ctx = isl_id_list_get_ctx(ancestors);
  67         for (it = record->field_begin(); it != record->field_end(); ++it) {
  68                 FieldDecl *field = *it;
  69                 bool anonymous = field->isAnonymousStructOrUnion();
  70                 isl_id *id;
  71                 isl_id_list *extended;
  72
  73                 if (anonymous) {
  74                         collect_direct_sub_arrays(field, ancestors, arrays);
  75                         continue;
  76                 }
  77                 extended = isl_id_list_copy(ancestors);
  78                 id = pet_id_from_decl(ctx, field);
  79                 extended = isl_id_list_add(extended, id);
  80                 arrays.insert(extended);
  81         }
  82 }
  83
  84 /* Add the sequence of nested array declarations "list" to "arrays".
  85  *
  86  * If "list" represents a member access (i.e., the list has at least
  87  * two elements), then also add the other members in each of its
  88  * outer arrays.
  89  */
  90 static void add_with_siblings(__isl_take isl_id_list *list,
  91         array_desc_set &arrays)
  92 {
  93         int n;
  94
  95         arrays.insert(isl_id_list_copy(list));
  96
  97         n = isl_id_list_n_id(list);
  98         while (n > 1) {
  99                 isl_id *id;
 100                 ValueDecl *decl;
 101
 102                 list = isl_id_list_drop(list, --n, 1);
 103                 arrays.insert(isl_id_list_copy(list));
 104                 id = isl_id_list_get_id(list, n - 1);
 105                 decl = pet_id_get_decl(id);
 106                 isl_id_free(id);
 107                 collect_direct_sub_arrays(decl, list, arrays);
 108         }
 109         isl_id_list_free(list);
 110 }
 111
 112 /* Construct a sequence of nested array declarations containing
 113  * a single element corresponding to the tuple identifier
 114  * of the set space "space".
 115  *
 116  * If the array being accessed has a NULL ValueDecl, then it
 117  * is a virtual scalar.  These do not need to be collected
 118  * because they are added to the scop of the statement writing
 119  * to the scalar.  Return an empty list instead.
 120  */
 121 static __isl_give isl_id_list *extract_list_from_tuple_id(
 122         __isl_keep isl_space *space)
 123 {
 124         isl_ctx *ctx;
 125         isl_id *id;
 126
 127         id = isl_space_get_tuple_id(space, isl_dim_set);
 128         if (pet_id_get_decl(id))
 129                 return isl_id_list_from_id(id);
 130         isl_id_free(id);
 131         ctx = isl_space_get_ctx(space);
 132         return isl_id_list_alloc(ctx, 0);
 133 }
 134
 135 /* Construct a sequence of nested array declarations corresponding
 136  * to the accessed data space "space".
 137  *
 138  * If "space" represents an array access, then the extracted sequence
 139  * contains a single element corresponding to the array declaration.
 140  * Otherwise, if "space" represents a member access, then the extracted
 141  * sequence contains an element for the outer array of structures and
 142  * for each nested array or scalar.
 143  *
 144  * If the array being accessed has a NULL ValueDecl, then it
 145  * is a virtual scalar.  These do not need to be collected
 146  * because they are added to the scop of the statement writing
 147  * to the scalar.  Return an empty list instead.
 148  */
 149 static __isl_give isl_id_list *extract_list(__isl_keep isl_space *space)
 150 {
 151         isl_space *range;
 152         isl_id_list *list;
 153
 154         if (!isl_space_is_wrapping(space))
 155                 return extract_list_from_tuple_id(space);
 156         space = isl_space_unwrap(isl_space_copy(space));
 157         range = isl_space_range(isl_space_copy(space));
 158         list = extract_list(range);
 159         isl_space_free(range);
 160         space = isl_space_domain(space);
 161         list = isl_id_list_concat(extract_list(space), list);
 162         isl_space_free(space);
 163         return list;
 164 }
 165
 166 /* Extract one or more sequences of declarations from the accessed
 167  * data space "space" and add them to "arrays".
 168  *
 169  * If "space" represents an array access, then the extracted sequence
 170  * contains a single element corresponding to the array declaration.
 171  * Otherwise, if "space" represents a member access, then the extracted
 172  * sequences contain an element for the outer array of structures and
 173  * for each nested array or scalar.  If such a sequence is constructed
 174  * corresponding to a given member access, then such sequences are
 175  * also constructed for the other members in the same structure.
 176  *
 177  * If the array being accessed has a NULL ValueDecl, then it
 178  * is a virtual scalar.  We don't need to collect such scalars
 179  * because they are added to the scop of the statement writing
 180  * to the scalar.  extract_list returns an empty list for
 181  * such arrays.
 182  *
 183  * If the sequence corresponding to "space" already appears
 184  * in "arrays", then its siblings have already been added as well,
 185  * so there is nothing left to do.
 186  */
 187 static isl_stat space_collect_arrays(__isl_take isl_space *space, void *user)
 188 {
 189         array_desc_set *arrays = (array_desc_set *) user;
 190         int n;
 191         isl_id_list *list;
 192
 193         list = extract_list(space);
 194         n = isl_id_list_n_id(list);
 195         if (n > 0 && arrays->find(list) == arrays->end())
 196                 add_with_siblings(list, *arrays);
 197         else
 198                 isl_id_list_free(list);
 199         isl_space_free(space);
 200
 201         return isl_stat_ok;
 202 }
 203
 204 /* Extract one or more sequences of declarations from the access expression
 205  * "expr" and add them to "arrays".
 206  */
 207 static void access_collect_arrays(__isl_keep pet_expr *expr,
 208         array_desc_set &arrays)
 209 {
 210         if (pet_expr_is_affine(expr))
 211                 return;
 212
 213         pet_expr_access_foreach_data_space(expr,
 214                                             &space_collect_arrays, &arrays);
 215 }
 216
 217 static void expr_collect_arrays(__isl_keep pet_expr *expr,
 218         array_desc_set &arrays)
 219 {
 220         int n;
 221
 222         if (!expr)
 223                 return;
 224
 225         n = pet_expr_get_n_arg(expr);
 226         for (int i = 0; i < n; ++i) {
 227                 pet_expr *arg;
 228
 229                 arg = pet_expr_get_arg(expr, i);
 230                 expr_collect_arrays(arg, arrays);
 231                 pet_expr_free(arg);
 232         }
 233
 234         if (pet_expr_get_type(expr) == pet_expr_access)
 235                 access_collect_arrays(expr, arrays);
 236 }
 237
 238 /* Wrapper around access_collect_arrays for use as a callback function
 239  * to pet_tree_foreach_access_expr.
 240  */
 241 static int access_collect_wrap(__isl_keep pet_expr *expr, void *user)
 242 {
 243         array_desc_set *arrays = (array_desc_set *) user;
 244
 245         access_collect_arrays(expr, *arrays);
 246
 247         return 0;
 248 }
 249
 250 static void stmt_collect_arrays(struct pet_stmt *stmt,
 251         array_desc_set &arrays)
 252 {
 253         if (!stmt)
 254                 return;
 255
 256         for (unsigned i = 0; i < stmt->n_arg; ++i)
 257                 expr_collect_arrays(stmt->args[i], arrays);
 258
 259         pet_tree_foreach_access_expr(stmt->body, &access_collect_wrap, &arrays);
 260 }
 261
 262 /* Collect the set of all accessed arrays (or scalars) in "scop",
 263  * except those that already appear in scop->arrays,
 264  * and put them in "arrays".
 265  *
 266  * Each accessed array is represented by a sequence of nested
 267  * array declarations, one for the outer array of structures
 268  * and one for each member access.
 269  *
 270  * The arrays that already appear in scop->arrays are assumed
 271  * to be simple arrays, represented by a sequence of a single element.
 272  */
 273 void pet_scop_collect_arrays(struct pet_scop *scop,
 274         array_desc_set &arrays)
 275 {
 276         if (!scop)
 277                 return;
 278
 279         for (int i = 0; i < scop->n_stmt; ++i)
 280                 stmt_collect_arrays(scop->stmts[i], arrays);
 281
 282         for (int i = 0; i < scop->n_array; ++i) {
 283                 ValueDecl *decl;
 284                 isl_id_list *ancestors;
 285
 286                 isl_id *id = isl_set_get_tuple_id(scop->arrays[i]->extent);
 287                 decl = pet_id_get_decl(id);
 288
 289                 if (!decl) {
 290                         isl_id_free(id);
 291                         continue;
 292                 }
 293
 294                 ancestors = isl_id_list_from_id(id);
 295                 arrays.erase(ancestors);
 296                 isl_id_list_free(ancestors);
 297         }
 298 }