nest.c

   1 /*
   2  * Copyright 2011      Leiden University. All rights reserved.
   3  * Copyright 2012-2014 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 "expr.h"
  36 #include "nest.h"
  37 #include "scop.h"
  38
  39 /* Create an isl_id that refers to the nested access "expr".
  40  */
  41 __isl_give isl_id *pet_nested_clang_expr(isl_ctx *ctx, void *expr)
  42 {
  43         return isl_id_alloc(ctx, NULL, expr);
  44 }
  45
  46 /* Does "id" refer to a nested access created by pet_nested_clang_expr?
  47  */
  48 int pet_nested_in_id(__isl_keep isl_id *id)
  49 {
  50         return id && isl_id_get_user(id) && !isl_id_get_name(id);
  51 }
  52
  53 /* Does parameter "pos" of "space" refer to a nested access?
  54  */
  55 static int pet_nested_in_space(__isl_keep isl_space *space, int pos)
  56 {
  57         int nested;
  58         isl_id *id;
  59
  60         id = isl_space_get_dim_id(space, isl_dim_param, pos);
  61         nested = pet_nested_in_id(id);
  62         isl_id_free(id);
  63
  64         return nested;
  65 }
  66
  67 /* Does parameter "pos" of "set" refer to a nested access?
  68  */
  69 int pet_nested_in_set(__isl_keep isl_set *set, int pos)
  70 {
  71         int nested;
  72         isl_id *id;
  73
  74         id = isl_set_get_dim_id(set, isl_dim_param, pos);
  75         nested = pet_nested_in_id(id);
  76         isl_id_free(id);
  77
  78         return nested;
  79 }
  80
  81 /* Does parameter "pos" of "map" refer to a nested access?
  82  */
  83 int pet_nested_in_map(__isl_keep isl_map *map, int pos)
  84 {
  85         int nested;
  86         isl_id *id;
  87
  88         id = isl_map_get_dim_id(map, isl_dim_param, pos);
  89         nested = pet_nested_in_id(id);
  90         isl_id_free(id);
  91
  92         return nested;
  93 }
  94
  95 /* Does "space" involve any parameters that refer to nested accesses?
  96  */
  97 int pet_nested_any_in_space(__isl_keep isl_space *space)
  98 {
  99         int i;
 100         int nparam;
 101
 102         nparam = isl_space_dim(space, isl_dim_param);
 103         for (i = 0; i < nparam; ++i)
 104                 if (pet_nested_in_space(space, i))
 105                         return 1;
 106
 107         return 0;
 108 }
 109
 110 /* Does "pa" involve any parameters that refer to nested accesses?
 111  */
 112 int pet_nested_any_in_pw_aff(__isl_keep isl_pw_aff *pa)
 113 {
 114         isl_space *space;
 115         int nested;
 116
 117         space = isl_pw_aff_get_space(pa);
 118         nested = pet_nested_any_in_space(space);
 119         isl_space_free(space);
 120
 121         return nested;
 122 }
 123
 124 /* How many parameters of "space" refer to nested accesses?
 125  */
 126 int pet_nested_n_in_space(__isl_keep isl_space *space)
 127 {
 128         int i, n = 0;
 129         int nparam;
 130
 131         nparam = isl_space_dim(space, isl_dim_param);
 132         for (i = 0; i < nparam; ++i)
 133                 if (pet_nested_in_space(space, i))
 134                         ++n;
 135
 136         return n;
 137 }
 138
 139 /* How many parameters of "map" refer to nested accesses?
 140  */
 141 int pet_nested_n_in_map(__isl_keep isl_map *map)
 142 {
 143         isl_space *space;
 144         int n;
 145
 146         space = isl_map_get_space(map);
 147         n = pet_nested_n_in_space(space);
 148         isl_space_free(space);
 149
 150         return n;
 151 }
 152
 153 /* How many parameters of "set" refer to nested accesses?
 154  */
 155 int pet_nested_n_in_set(__isl_keep isl_set *set)
 156 {
 157         isl_space *space;
 158         int n;
 159
 160         space = isl_set_get_space(set);
 161         n = pet_nested_n_in_space(space);
 162         isl_space_free(space);
 163
 164         return n;
 165 }
 166
 167 /* Remove all parameters from "set" that refer to nested accesses.
 168  */
 169 __isl_give isl_set *pet_nested_remove_from_set(__isl_take isl_set *set)
 170 {
 171         int i;
 172         int nparam;
 173
 174         nparam = isl_set_dim(set, isl_dim_param);
 175         for (i = nparam - 1; i >= 0; --i)
 176                 if (pet_nested_in_set(set, i))
 177                         set = isl_set_project_out(set, isl_dim_param, i, 1);
 178
 179         return set;
 180 }
 181
 182 /* Remove all parameters from "map" that refer to nested accesses.
 183  */
 184 static __isl_give isl_map *pet_nested_remove_from_map(__isl_take isl_map *map)
 185 {
 186         int i;
 187         int nparam;
 188
 189         nparam = isl_map_dim(map, isl_dim_param);
 190         for (i = nparam - 1; i >= 0; --i)
 191                 if (pet_nested_in_map(map, i))
 192                         map = isl_map_project_out(map, isl_dim_param, i, 1);
 193
 194         return map;
 195 }
 196
 197 /* Remove all parameters from "mpa" that refer to nested accesses.
 198  */
 199 static __isl_give isl_multi_pw_aff *pet_nested_remove_from_multi_pw_aff(
 200         __isl_take isl_multi_pw_aff *mpa)
 201 {
 202         int i;
 203         int nparam;
 204         isl_space *space;
 205
 206         space = isl_multi_pw_aff_get_space(mpa);
 207         nparam = isl_space_dim(space, isl_dim_param);
 208         for (i = nparam - 1; i >= 0; --i) {
 209                 if (!pet_nested_in_space(space, i))
 210                         continue;
 211                 mpa = isl_multi_pw_aff_drop_dims(mpa, isl_dim_param, i, 1);
 212         }
 213         isl_space_free(space);
 214
 215         return mpa;
 216 }
 217
 218 /* Remove all parameters from the index expression and access relation of "expr"
 219  * that refer to nested accesses.
 220  */
 221 static __isl_give pet_expr *expr_remove_nested_parameters(
 222         __isl_take pet_expr *expr, void *user)
 223 {
 224         expr = pet_expr_cow(expr);
 225         if (!expr)
 226                 return NULL;
 227
 228         expr->acc.access = pet_nested_remove_from_map(expr->acc.access);
 229         expr->acc.index = pet_nested_remove_from_multi_pw_aff(expr->acc.index);
 230         if (!expr->acc.access || !expr->acc.index)
 231                 return pet_expr_free(expr);
 232
 233         return expr;
 234 }
 235
 236 /* Remove all nested access parameters from the schedule and all
 237  * accesses of "stmt".
 238  * There is no need to remove them from the domain as these parameters
 239  * have already been removed from the domain when this function is called.
 240  */
 241 struct pet_stmt *pet_stmt_remove_nested_parameters(struct pet_stmt *stmt)
 242 {
 243         int i;
 244
 245         if (!stmt)
 246                 return NULL;
 247         stmt->schedule = pet_nested_remove_from_map(stmt->schedule);
 248         stmt->body = pet_expr_map_access(stmt->body,
 249                             &expr_remove_nested_parameters, NULL);
 250         if (!stmt->schedule || !stmt->body)
 251                 goto error;
 252         for (i = 0; i < stmt->n_arg; ++i) {
 253                 stmt->args[i] = pet_expr_map_access(stmt->args[i],
 254                             &expr_remove_nested_parameters, NULL);
 255                 if (!stmt->args[i])
 256                         goto error;
 257         }
 258
 259         return stmt;
 260 error:
 261         pet_stmt_free(stmt);
 262         return NULL;
 263 }