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_bool is_wrapping;
 152         isl_space *range;
 153         isl_id_list *list;
 154
 155         is_wrapping = isl_space_is_wrapping(space);
 156         if (is_wrapping < 0)
 157                 return NULL;
 158         if (!is_wrapping)
 159                 return extract_list_from_tuple_id(space);
 160         space = isl_space_unwrap(isl_space_copy(space));
 161         range = isl_space_range(isl_space_copy(space));
 162         list = extract_list(range);
 163         isl_space_free(range);
 164         space = isl_space_domain(space);
 165         list = isl_id_list_concat(extract_list(space), list);
 166         isl_space_free(space);
 167         return list;
 168 }
 169
 170 /* Extract one or more sequences of declarations from the accessed
 171  * data space "space" and add them to "arrays".
 172  *
 173  * If "space" represents an array access, then the extracted sequence
 174  * contains a single element corresponding to the array declaration.
 175  * Otherwise, if "space" represents a member access, then the extracted
 176  * sequences contain an element for the outer array of structures and
 177  * for each nested array or scalar.  If such a sequence is constructed
 178  * corresponding to a given member access, then such sequences are
 179  * also constructed for the other members in the same structure.
 180  *
 181  * If the array being accessed has a NULL ValueDecl, then it
 182  * is a virtual scalar.  We don't need to collect such scalars
 183  * because they are added to the scop of the statement writing
 184  * to the scalar.  extract_list returns an empty list for
 185  * such arrays.
 186  *
 187  * If the sequence corresponding to "space" already appears
 188  * in "arrays", then its siblings have already been added as well,
 189  * so there is nothing left to do.
 190  */
 191 static isl_stat space_collect_arrays(__isl_take isl_space *space, void *user)
 192 {
 193         array_desc_set *arrays = (array_desc_set *) user;
 194         int n;
 195         isl_id_list *list;
 196
 197         list = extract_list(space);
 198         n = isl_id_list_n_id(list);
 199         if (n > 0 && arrays->find(list) == arrays->end())
 200                 add_with_siblings(list, *arrays);
 201         else
 202                 isl_id_list_free(list);
 203         isl_space_free(space);
 204
 205         return isl_stat_ok;
 206 }
 207
 208 /* Extract one or more sequences of declarations from the access expression
 209  * "expr" and add them to "arrays".
 210  */
 211 static void access_collect_arrays(__isl_keep pet_expr *expr,
 212         array_desc_set &arrays)
 213 {
 214         if (pet_expr_is_affine(expr))
 215                 return;
 216
 217         pet_expr_access_foreach_data_space(expr,
 218                                             &space_collect_arrays, &arrays);
 219 }
 220
 221 static void expr_collect_arrays(__isl_keep pet_expr *expr,
 222         array_desc_set &arrays)
 223 {
 224         int n;
 225
 226         if (!expr)
 227                 return;
 228
 229         n = pet_expr_get_n_arg(expr);
 230         for (int i = 0; i < n; ++i) {
 231                 pet_expr *arg;
 232
 233                 arg = pet_expr_get_arg(expr, i);
 234                 expr_collect_arrays(arg, arrays);
 235                 pet_expr_free(arg);
 236         }
 237
 238         if (pet_expr_get_type(expr) == pet_expr_access)
 239                 access_collect_arrays(expr, arrays);
 240 }
 241
 242 /* Wrapper around access_collect_arrays for use as a callback function
 243  * to pet_tree_foreach_access_expr.
 244  */
 245 static int access_collect_wrap(__isl_keep pet_expr *expr, void *user)
 246 {
 247         array_desc_set *arrays = (array_desc_set *) user;
 248
 249         access_collect_arrays(expr, *arrays);
 250
 251         return 0;
 252 }
 253
 254 static void stmt_collect_arrays(struct pet_stmt *stmt,
 255         array_desc_set &arrays)
 256 {
 257         if (!stmt)
 258                 return;
 259
 260         for (unsigned i = 0; i < stmt->n_arg; ++i)
 261                 expr_collect_arrays(stmt->args[i], arrays);
 262
 263         pet_tree_foreach_access_expr(stmt->body, &access_collect_wrap, &arrays);
 264 }
 265
 266 /* Collect the set of all accessed arrays (or scalars) in "scop",
 267  * except those that already appear in scop->arrays,
 268  * and put them in "arrays".
 269  *
 270  * Each accessed array is represented by a sequence of nested
 271  * array declarations, one for the outer array of structures
 272  * and one for each member access.
 273  *
 274  * The arrays that already appear in scop->arrays are assumed
 275  * to be simple arrays, represented by a sequence of a single element.
 276  */
 277 void pet_scop_collect_arrays(struct pet_scop *scop,
 278         array_desc_set &arrays)
 279 {
 280         if (!scop)
 281                 return;
 282
 283         for (int i = 0; i < scop->n_stmt; ++i)
 284                 stmt_collect_arrays(scop->stmts[i], arrays);
 285
 286         for (int i = 0; i < scop->n_array; ++i) {
 287                 ValueDecl *decl;
 288                 isl_id_list *ancestors;
 289
 290                 isl_id *id = isl_set_get_tuple_id(scop->arrays[i]->extent);
 291                 decl = pet_id_get_decl(id);
 292
 293                 if (!decl) {
 294                         isl_id_free(id);
 295                         continue;
 296                 }
 297
 298                 ancestors = isl_id_list_from_id(id);
 299                 arrays.erase(ancestors);
 300                 isl_id_list_free(ancestors);
 301         }
 302 }