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 "scop_plus.h"
  40
  41 using namespace std;
  42 using namespace clang;
  43
  44 /* And the sequence of nested arrays of structures "ancestors"
  45  * to "arrays".  The final element in the sequence may be a leaf
  46  * and may therefore refer to a primitive type rather than a record type.
  47  *
  48  * Futhermore, if the innermost array in the sequence is an array of structures
  49  * then recursively call collect_sub_arrays for all subfields of this
  50  * structure.
  51  */
  52 static void collect_sub_arrays(ValueDecl *decl, vector<ValueDecl *> ancestors,
  53         set<vector<ValueDecl *> > &arrays)
  54 {
  55         QualType type = decl->getType();
  56         RecordDecl *record;
  57         RecordDecl::field_iterator it;
  58
  59         arrays.insert(ancestors);
  60
  61         type = pet_clang_base_type(type);
  62
  63         if (!type->isRecordType())
  64                 return;
  65
  66         record = pet_clang_record_decl(type);
  67
  68         for (it = record->field_begin(); it != record->field_end(); ++it) {
  69                 FieldDecl *field = *it;
  70                 bool anonymous = field->isAnonymousStructOrUnion();
  71
  72                 if (!anonymous)
  73                         ancestors.push_back(field);
  74                 collect_sub_arrays(field, ancestors, arrays);
  75                 if (!anonymous)
  76                         ancestors.pop_back();
  77         }
  78 }
  79
  80 /* Extract one or more sequences of declarations from the access expression
  81  * "expr" and them to "arrays".
  82  *
  83  * If "expr" represents an array access, then the extracted sequence
  84  * contains a single element corresponding to the array declaration.
  85  * Otherwise, if "expr" represents a member access, then the extracted
  86  * sequences contain an element for the outer array of structures and
  87  * for each nested array or scalar.  One such sequence is (recursively)
  88  * added for each member of the accessed outer array.
  89  *
  90  * If the array being accessed has a NULL ValueDecl, then it
  91  * is a virtual scalar.  We don't need to collect such scalars
  92  * because they are added to the scop of the statement writing
  93  * to the scalar.
  94  */
  95 static void access_collect_arrays(struct pet_expr *expr,
  96         set<vector<ValueDecl *> > &arrays)
  97 {
  98         isl_id *id;
  99         isl_space *space;
 100         ValueDecl *decl;
 101         vector<ValueDecl *> ancestors;
 102
 103         if (pet_expr_is_affine(expr))
 104                 return;
 105
 106         space = isl_map_get_space(expr->acc.access);
 107         space = isl_space_range(space);
 108
 109         while (space && isl_space_is_wrapping(space))
 110                 space = isl_space_domain(isl_space_unwrap(space));
 111
 112         id = isl_space_get_tuple_id(space, isl_dim_set);
 113         isl_space_free(space);
 114         if (!id)
 115                 return;
 116
 117         decl = (ValueDecl *)isl_id_get_user(id);
 118         isl_id_free(id);
 119
 120         if (!decl)
 121                 return;
 122
 123         ancestors.push_back(decl);
 124         collect_sub_arrays(decl, ancestors, arrays);
 125 }
 126
 127 static void expr_collect_arrays(struct pet_expr *expr,
 128         set<vector<ValueDecl *> > &arrays)
 129 {
 130         if (!expr)
 131                 return;
 132
 133         for (int i = 0; i < expr->n_arg; ++i)
 134                 expr_collect_arrays(expr->args[i], arrays);
 135
 136         if (expr->type == pet_expr_access)
 137                 access_collect_arrays(expr, arrays);
 138 }
 139
 140 static void stmt_collect_arrays(struct pet_stmt *stmt,
 141         set<vector<ValueDecl *> > &arrays)
 142 {
 143         if (!stmt)
 144                 return;
 145
 146         for (int i = 0; i < stmt->n_arg; ++i)
 147                 expr_collect_arrays(stmt->args[i], arrays);
 148
 149         expr_collect_arrays(stmt->body, arrays);
 150 }
 151
 152 /* Collect the set of all accessed arrays (or scalars) in "scop",
 153  * except those that already appear in scop->arrays,
 154  * and put them in "arrays".
 155  *
 156  * Each accessed array is represented by a sequence of nested
 157  * array declarations, one for the outer array of structures
 158  * and one for each member access.
 159  *
 160  * The arrays that already appear in scop->arrays are assumed
 161  * to be simple arrays, represented by a sequence of a single element.
 162  */
 163 void pet_scop_collect_arrays(struct pet_scop *scop,
 164         set<vector<ValueDecl *> > &arrays)
 165 {
 166         if (!scop)
 167                 return;
 168
 169         for (int i = 0; i < scop->n_stmt; ++i)
 170                 stmt_collect_arrays(scop->stmts[i], arrays);
 171
 172         for (int i = 0; i < scop->n_array; ++i) {
 173                 ValueDecl *decl;
 174                 vector<ValueDecl *> ancestors;
 175
 176                 isl_id *id = isl_set_get_tuple_id(scop->arrays[i]->extent);
 177                 decl = (ValueDecl *)isl_id_get_user(id);
 178                 isl_id_free(id);
 179
 180                 ancestors.push_back(decl);
 181
 182                 arrays.erase(ancestors);
 183         }
 184 }