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