scop_plus.cc

   1 /*
   2  * Copyright 2011 Leiden University. All rights reserved.
   3  * Copyright 2013 Ecole Normale Superieure. All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  *    1. Redistributions of source code must retain the above copyright
  10  *       notice, this list of conditions and the following disclaimer.
  11  *
  12  *    2. Redistributions in binary form must reproduce the above
  13  *       copyright notice, this list of conditions and the following
  14  *       disclaimer in the documentation and/or other materials provided
  15  *       with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
  18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  20  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
  21  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  22  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  23  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
  24  * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * The views and conclusions contained in the software and documentation
  30  * are those of the authors and should not be interpreted as
  31  * representing official policies, either expressed or implied, of
  32  * Leiden University.
  33  */
  34
  35 #include <set>
  36 #include <vector>
  37
  38 #include "clang.h"
  39 #include "expr.h"
  40 #include "id.h"
  41 #include "scop_plus.h"
  42 #include "tree.h"
  43
  44 using namespace std;
  45 using namespace clang;
  46
  47 /* Add the sequence of nested arrays of structures represented by "ancestors"
  48  * to "arrays".  The final element in the sequence may be a leaf
  49  * and may therefore refer to a primitive type rather than a record type.
  50  *
  51  * Futhermore, if the innermost array in the sequence is an array of structures
  52  * then recursively call collect_sub_arrays for all subfields of this
  53  * structure.
  54  */
  55 static void collect_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         arrays.insert(isl_id_list_copy(ancestors));
  64
  65         type = pet_clang_base_type(type);
  66
  67         if (!type->isRecordType())
  68                 return;
  69
  70         record = pet_clang_record_decl(type);
  71
  72         ctx = isl_id_list_get_ctx(ancestors);
  73         for (it = record->field_begin(); it != record->field_end(); ++it) {
  74                 FieldDecl *field = *it;
  75                 bool anonymous = field->isAnonymousStructOrUnion();
  76                 isl_id_list *extended;
  77
  78                 extended = isl_id_list_copy(ancestors);
  79                 if (!anonymous) {
  80                         isl_id *id = pet_id_from_decl(ctx, field);
  81                         extended = isl_id_list_add(extended, id);
  82                 }
  83                 collect_sub_arrays(field, extended, arrays);
  84                 isl_id_list_free(extended);
  85         }
  86 }
  87
  88 /* Extract one or more sequences of declarations from the access expression
  89  * "expr" and them to "arrays".
  90  *
  91  * If "expr" represents an array access, then the extracted sequence
  92  * contains a single element corresponding to the array declaration.
  93  * Otherwise, if "expr" represents a member access, then the extracted
  94  * sequences contain an element for the outer array of structures and
  95  * for each nested array or scalar.  One such sequence is (recursively)
  96  * added for each member of the accessed outer array.
  97  *
  98  * If the array being accessed has a NULL ValueDecl, then it
  99  * is a virtual scalar.  We don't need to collect such scalars
 100  * because they are added to the scop of the statement writing
 101  * to the scalar.
 102  */
 103 static void access_collect_arrays(__isl_keep pet_expr *expr,
 104         array_desc_set &arrays)
 105 {
 106         isl_id *id;
 107         isl_space *space;
 108         ValueDecl *decl;
 109         isl_id_list *ancestors;
 110
 111         if (pet_expr_is_affine(expr))
 112                 return;
 113
 114         space = pet_expr_access_get_data_space(expr);
 115
 116         while (space && isl_space_is_wrapping(space))
 117                 space = isl_space_domain(isl_space_unwrap(space));
 118
 119         id = isl_space_get_tuple_id(space, isl_dim_set);
 120         isl_space_free(space);
 121         if (!id)
 122                 return;
 123
 124         decl = pet_id_get_decl(id);
 125
 126         if (!decl) {
 127                 isl_id_free(id);
 128                 return;
 129         }
 130
 131         ancestors = isl_id_list_from_id(id);
 132         collect_sub_arrays(decl, ancestors, arrays);
 133         isl_id_list_free(ancestors);
 134 }
 135
 136 static void expr_collect_arrays(__isl_keep pet_expr *expr,
 137         array_desc_set &arrays)
 138 {
 139         int n;
 140
 141         if (!expr)
 142                 return;
 143
 144         n = pet_expr_get_n_arg(expr);
 145         for (int i = 0; i < n; ++i) {
 146                 pet_expr *arg;
 147
 148                 arg = pet_expr_get_arg(expr, i);
 149                 expr_collect_arrays(arg, arrays);
 150                 pet_expr_free(arg);
 151         }
 152
 153         if (pet_expr_get_type(expr) == pet_expr_access)
 154                 access_collect_arrays(expr, arrays);
 155 }
 156
 157 /* Wrapper around access_collect_arrays for use as a callback function
 158  * to pet_tree_foreach_access_expr.
 159  */
 160 static int access_collect_wrap(__isl_keep pet_expr *expr, void *user)
 161 {
 162         array_desc_set *arrays = (array_desc_set *) user;
 163
 164         access_collect_arrays(expr, *arrays);
 165
 166         return 0;
 167 }
 168
 169 static void stmt_collect_arrays(struct pet_stmt *stmt,
 170         array_desc_set &arrays)
 171 {
 172         if (!stmt)
 173                 return;
 174
 175         for (unsigned i = 0; i < stmt->n_arg; ++i)
 176                 expr_collect_arrays(stmt->args[i], arrays);
 177
 178         pet_tree_foreach_access_expr(stmt->body, &access_collect_wrap, &arrays);
 179 }
 180
 181 /* Collect the set of all accessed arrays (or scalars) in "scop",
 182  * except those that already appear in scop->arrays,
 183  * and put them in "arrays".
 184  *
 185  * Each accessed array is represented by a sequence of nested
 186  * array declarations, one for the outer array of structures
 187  * and one for each member access.
 188  *
 189  * The arrays that already appear in scop->arrays are assumed
 190  * to be simple arrays, represented by a sequence of a single element.
 191  */
 192 void pet_scop_collect_arrays(struct pet_scop *scop,
 193         array_desc_set &arrays)
 194 {
 195         if (!scop)
 196                 return;
 197
 198         for (int i = 0; i < scop->n_stmt; ++i)
 199                 stmt_collect_arrays(scop->stmts[i], arrays);
 200
 201         for (int i = 0; i < scop->n_array; ++i) {
 202                 ValueDecl *decl;
 203                 isl_id_list *ancestors;
 204
 205                 isl_id *id = isl_set_get_tuple_id(scop->arrays[i]->extent);
 206                 decl = pet_id_get_decl(id);
 207
 208                 if (!decl) {
 209                         isl_id_free(id);
 210                         continue;
 211                 }
 212
 213                 ancestors = isl_id_list_from_id(id);
 214                 arrays.erase(ancestors);
 215                 isl_id_list_free(ancestors);
 216         }
 217 }