summary.c

   1 /*
   2  * Copyright 2014      Ecole Normale Superieure. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  *    1. Redistributions of source code must retain the above copyright
   9  *       notice, this list of conditions and the following disclaimer.
  10  *
  11  *    2. Redistributions in binary form must reproduce the above
  12  *       copyright notice, this list of conditions and the following
  13  *       disclaimer in the documentation and/or other materials provided
  14  *       with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY ECOLE NORMALE SUPERIEURE ''AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ECOLE NORMALE SUPERIEURE OR
  20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  21  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  22  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
  23  * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * The views and conclusions contained in the software and documentation
  29  * are those of the authors and should not be interpreted as
  30  * representing official policies, either expressed or implied, of
  31  * Ecole Normale Superieure.
  32  */
  33
  34 #include <isl/union_set.h>
  35
  36 #include "aff.h"
  37 #include "summary.h"
  38
  39 /* A pet_function_summary objects represents an argument of a function.
  40  *
  41  * If "type" is pet_arg_int, then the argument has an integer type and
  42  * can be used to describe the accesses performed by the pet_arg_array
  43  * arguments.  In this case, "id" refers to the formal argument.
  44  *
  45  * If "type" is pet_arg_array, then we keep track of the accesses
  46  * through this argument in the access relations in "access".
  47  * The domains of these access relations refer to the integer arguments
  48  * of the function.  That is, the input dimensions correspond
  49  * to the arguments of type pet_arg_int.
  50  *
  51  * If "type" is pet_arg_other, then we do not keep track of any
  52  * further information.
  53  */
  54 struct pet_function_summary_arg {
  55         enum pet_arg_type type;
  56
  57         union {
  58                 isl_id *id;
  59                 isl_union_map *access[pet_expr_access_end];
  60         };
  61 };
  62
  63 /* A pet_function_summary object keeps track of the accesses performed
  64  * by a function in terms of the function arguments.
  65  *
  66  * "n" is the number of arguments.
  67  * "arg" contains a description of the "n" arguments.
  68  */
  69 struct pet_function_summary {
  70         int ref;
  71         isl_ctx *ctx;
  72
  73         unsigned n;
  74
  75         struct pet_function_summary_arg arg[];
  76 };
  77
  78 /* Construct and return a new pet_function_summary object with
  79  * "n_arg" arguments, initialized to pet_arg_other.
  80  */
  81 __isl_give pet_function_summary *pet_function_summary_alloc(isl_ctx *ctx,
  82         unsigned n_arg)
  83 {
  84         pet_function_summary *summary;
  85         int i;
  86
  87         summary = isl_calloc(ctx, struct pet_function_summary,
  88                             sizeof(struct pet_function_summary) +
  89                             n_arg * sizeof(struct pet_function_summary_arg));
  90         if (!summary)
  91                 return summary;
  92
  93         summary->ctx = ctx;
  94         isl_ctx_ref(ctx);
  95         summary->ref = 1;
  96         summary->n = n_arg;
  97         for (i = 0; i < n_arg; ++i)
  98                 summary->arg[i].type = pet_arg_other;
  99
 100         return summary;
 101 }
 102
 103 /* Return an extra reference to "summary".
 104  */
 105 __isl_give pet_function_summary *pet_function_summary_copy(
 106         __isl_keep pet_function_summary *summary)
 107 {
 108         if (!summary)
 109                 return NULL;
 110
 111         summary->ref++;
 112         return summary;
 113 }
 114
 115 /* Free the data stored in "arg".
 116  */
 117 static void free_arg(struct pet_function_summary_arg *arg)
 118 {
 119         enum pet_expr_access_type type;
 120
 121         if (arg->type == pet_arg_int)
 122                 isl_id_free(arg->id);
 123         if (arg->type != pet_arg_array)
 124                 return;
 125         for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type)
 126                 arg->access[type] = isl_union_map_free(arg->access[type]);
 127 }
 128
 129 /* Free a reference to "summary".
 130  */
 131 __isl_null pet_function_summary *pet_function_summary_free(
 132         __isl_take pet_function_summary *summary)
 133 {
 134         int i;
 135
 136         if (!summary)
 137                 return NULL;
 138         if (--summary->ref > 0)
 139                 return NULL;
 140
 141         for (i = 0; i < summary->n; ++i)
 142                 free_arg(&summary->arg[i]);
 143
 144         isl_ctx_deref(summary->ctx);
 145         free(summary);
 146         return NULL;
 147 }
 148
 149 /* Return the number of arguments of the function summarized by "summary".
 150  */
 151 int pet_function_summary_get_n_arg(__isl_keep pet_function_summary *summary)
 152 {
 153         if (!summary)
 154                 return -1;
 155
 156         return summary->n;
 157 }
 158
 159 /* Mark the argument at position "pos" of "summary" as an integer argument
 160  * with the given identifier.
 161  */
 162 __isl_give pet_function_summary *pet_function_summary_set_int(
 163         __isl_take pet_function_summary *summary, int pos,
 164         __isl_take isl_id *id)
 165 {
 166         if (!summary || !id)
 167                 goto error;
 168
 169         if (pos < 0 || pos >= summary->n)
 170                 isl_die(summary->ctx, isl_error_invalid,
 171                         "position out of bounds", goto error);
 172
 173         free_arg(&summary->arg[pos]);
 174
 175         summary->arg[pos].type = pet_arg_int;
 176         summary->arg[pos].id = id;
 177
 178         return summary;
 179 error:
 180         isl_id_free(id);
 181         return pet_function_summary_free(summary);
 182 }
 183
 184 /* Mark the argument at position "pos" of "summary" as an array argument
 185  * with the given sets of accessed elements.
 186  * The integer arguments of "summary" may appear as parameters
 187  * in these sets of accessed elements.
 188  * These parameters are turned into input dimensions of
 189  * the corresponding access relations, which are then associated
 190  * to the array argument.
 191  * The order of the input dimensions is the same as the order
 192  * in which the integer arguments appear in the sequence of arguments.
 193  */
 194 __isl_give pet_function_summary *pet_function_summary_set_array(
 195         __isl_take pet_function_summary *summary, int pos,
 196         __isl_take isl_union_set *may_read, __isl_take isl_union_set *may_write,
 197         __isl_take isl_union_set *must_write)
 198 {
 199         int i, n;
 200         isl_space *space;
 201         enum pet_expr_access_type type;
 202
 203         if (!summary || !may_read || !may_write || !must_write)
 204                 goto error;
 205
 206         if (pos < 0 || pos >= summary->n)
 207                 isl_die(summary->ctx, isl_error_invalid,
 208                         "position out of bounds", goto error);
 209
 210         n = 0;
 211         for (i = 0; i < summary->n; ++i)
 212                 if (pet_function_summary_arg_is_int(summary, i))
 213                         n++;
 214
 215         space = isl_space_params_alloc(summary->ctx, n);
 216
 217         n = 0;
 218         for (i = 0; i < summary->n; ++i)
 219                 if (pet_function_summary_arg_is_int(summary, i))
 220                         space = isl_space_set_dim_id(space, isl_dim_param, n++,
 221                                             isl_id_copy(summary->arg[i].id));
 222
 223         free_arg(&summary->arg[pos]);
 224
 225         summary->arg[pos].type = pet_arg_array;
 226         summary->arg[pos].access[pet_expr_access_may_read] =
 227                 isl_union_map_from_range(may_read);
 228         summary->arg[pos].access[pet_expr_access_may_write] =
 229                 isl_union_map_from_range(may_write);
 230         summary->arg[pos].access[pet_expr_access_must_write] =
 231                 isl_union_map_from_range(must_write);
 232
 233         for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
 234                 isl_union_map *umap;
 235                 umap = summary->arg[pos].access[type];
 236                 umap = isl_union_map_align_params(umap, isl_space_copy(space));
 237                 umap = pet_union_map_move_dims(umap, isl_dim_in, 0,
 238                                                 isl_dim_param, 0, n);
 239                 summary->arg[pos].access[type] = umap;
 240                 if (!umap)
 241                         break;
 242         }
 243
 244         isl_space_free(space);
 245
 246         if (type < pet_expr_access_end)
 247                 return pet_function_summary_free(summary);
 248
 249         return summary;
 250 error:
 251         isl_union_set_free(may_read);
 252         isl_union_set_free(may_write);
 253         isl_union_set_free(must_write);
 254         return pet_function_summary_free(summary);
 255 }
 256
 257 /* Has the argument of "summary" at position "pos" been marked
 258  * as an integer argument?
 259  */
 260 int pet_function_summary_arg_is_int(__isl_keep pet_function_summary *summary,
 261         int pos)
 262 {
 263         if (!summary)
 264                 return -1;
 265
 266         if (pos < 0 || pos >= summary->n)
 267                 isl_die(summary->ctx, isl_error_invalid,
 268                         "position out of bounds", return -1);
 269
 270         return summary->arg[pos].type == pet_arg_int;
 271 }
 272
 273 /* Has the argument of "summary" at position "pos" been marked
 274  * as an array argument?
 275  */
 276 int pet_function_summary_arg_is_array(__isl_keep pet_function_summary *summary,
 277         int pos)
 278 {
 279         if (!summary)
 280                 return -1;
 281
 282         if (pos < 0 || pos >= summary->n)
 283                 isl_die(summary->ctx, isl_error_invalid,
 284                         "position out of bounds", return -1);
 285
 286         return summary->arg[pos].type == pet_arg_array;
 287 }
 288
 289 /* Return the access relation of type "type" associated to
 290  * the argument of "summary" at position "pos", which is assumed
 291  * to be an array argument.
 292  */
 293 __isl_give isl_union_map *pet_function_summary_arg_get_access(
 294         __isl_keep pet_function_summary *summary, int pos,
 295         enum pet_expr_access_type type)
 296 {
 297         if (!summary)
 298                 return NULL;
 299         if (pos < 0 || pos >= summary->n)
 300                 isl_die(summary->ctx, isl_error_invalid,
 301                         "position out of bounds", return NULL);
 302         if (summary->arg[pos].type != pet_arg_array)
 303                 isl_die(summary->ctx, isl_error_invalid,
 304                         "not an array argument", return NULL);
 305
 306         return isl_union_map_copy(summary->arg[pos].access[type]);
 307 }
 308
 309 void pet_function_summary_dump_with_indent(
 310         __isl_keep pet_function_summary *summary, int indent)
 311 {
 312         int i;
 313
 314         if (!summary)
 315                 return;
 316         fprintf(stderr, "%*s", indent, "");
 317         fprintf(stderr, "n: %d\n", summary->n);
 318         for (i = 0; i < summary->n; ++i) {
 319                 switch (summary->arg[i].type) {
 320                 case pet_arg_int:
 321                         fprintf(stderr, "%*s", indent, "");
 322                         fprintf(stderr, "id:");
 323                         isl_id_dump(summary->arg[i].id);
 324                         break;
 325                 case pet_arg_other:
 326                         fprintf(stderr, "%*s", indent, "");
 327                         fprintf(stderr, "other\n");
 328                         break;
 329                 case pet_arg_array:
 330                         fprintf(stderr, "%*s", indent, "");
 331                         fprintf(stderr, "may_read: ");
 332                         isl_union_map_dump(
 333                             summary->arg[i].access[pet_expr_access_may_read]);
 334                         fprintf(stderr, "%*s", indent, "");
 335                         fprintf(stderr, "may_write: ");
 336                         isl_union_map_dump(
 337                             summary->arg[i].access[pet_expr_access_may_write]);
 338                         fprintf(stderr, "%*s", indent, "");
 339                         fprintf(stderr, "must_write: ");
 340                         isl_union_map_dump(
 341                             summary->arg[i].access[pet_expr_access_must_write]);
 342                         break;
 343                 }
 344         }
 345 }
 346
 347 void pet_function_summary_dump(__isl_keep pet_function_summary *summary)
 348 {
 349         pet_function_summary_dump_with_indent(summary, 0);
 350 }