print.c

   1 /*
   2  * Copyright 2011 Leiden University. All rights reserved.
   3  * Copyright 2012-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 <isl/aff.h>
  36 #include <isl/ast.h>
  37 #include <isl/ast_build.h>
  38 #include <pet.h>
  39 #include "expr.h"
  40 #include "print.h"
  41 #include "scop.h"
  42
  43 /* Internal data structure for pet_stmt_build_ast_exprs.
  44  *
  45  * "build" is used to construct an AST expression from an index expression.
  46  * "fn_index" is used to transform the index expression prior to
  47  *      the construction of the AST expression.
  48  * "fn_expr" is used to transform the constructed AST expression.
  49  * "ref2expr" collects the results.
  50  */
  51 struct pet_build_ast_expr_data {
  52         isl_ast_build *build;
  53         __isl_give isl_multi_pw_aff *(*fn_index)(
  54                 __isl_take isl_multi_pw_aff *mpa, __isl_keep isl_id *id,
  55                 void *user);
  56         void *user_index;
  57         __isl_give isl_ast_expr *(*fn_expr)(__isl_take isl_ast_expr *expr,
  58                 __isl_keep isl_id *id, void *user);
  59         void *user_expr;
  60         isl_id_to_ast_expr *ref2expr;
  61 };
  62
  63 /* Given an index expression "index" with nested expressions, replace
  64  * those nested expressions by parameters.  The identifiers
  65  * of those parameters reference the corresponding arguments
  66  * of "expr".  The same identifiers are used in
  67  * pet_expr_build_nested_ast_exprs.
  68  *
  69  * In particular, if "index" is of the form
  70  *
  71  *      { [domain -> [e_1, ..., e_n]] -> array[f(e_1, ..., e_n)] }
  72  *
  73  * then we construct the expression
  74  *
  75  *      [p_1, ..., p_n] -> { domain -> array[f(p_1, ..., p_n)] }
  76  *
  77  */
  78 static __isl_give isl_multi_pw_aff *parametrize_nested_exprs(
  79         __isl_take isl_multi_pw_aff *index, struct pet_expr *expr)
  80 {
  81         int i;
  82         isl_ctx *ctx;
  83         isl_space *space, *space2;
  84         isl_local_space *ls;
  85         isl_multi_aff *ma, *ma2;
  86
  87         ctx = isl_multi_pw_aff_get_ctx(index);
  88         space = isl_multi_pw_aff_get_domain_space(index);
  89         space = isl_space_unwrap(space);
  90
  91         space2 = isl_space_domain(isl_space_copy(space));
  92         ma = isl_multi_aff_identity(isl_space_map_from_set(space2));
  93
  94         space = isl_space_insert_dims(space, isl_dim_param, 0,
  95                                         expr->n_arg);
  96         for (i = 0; i < expr->n_arg; ++i) {
  97                 isl_id *id = isl_id_alloc(ctx, NULL, expr->args[i]);
  98
  99                 space = isl_space_set_dim_id(space, isl_dim_param, i, id);
 100         }
 101         space2 = isl_space_domain(isl_space_copy(space));
 102         ls = isl_local_space_from_space(space2);
 103         ma2 = isl_multi_aff_zero(space);
 104         for (i = 0; i < expr->n_arg; ++i) {
 105                 isl_aff *aff;
 106                 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
 107                                                 isl_dim_param, i);
 108                 ma2 = isl_multi_aff_set_aff(ma2, i, aff);
 109         }
 110         isl_local_space_free(ls);
 111
 112         ma = isl_multi_aff_range_product(ma, ma2);
 113
 114         return isl_multi_pw_aff_pullback_multi_aff(index, ma);
 115 }
 116
 117 static __isl_give isl_ast_expr *pet_expr_build_ast_expr(struct pet_expr *expr,
 118         struct pet_build_ast_expr_data *data);
 119
 120 /* Construct an associative array from identifiers for the nested
 121  * expressions of "expr" to the corresponding isl_ast_expr.
 122  * The identifiers reference the corresponding arguments of "expr".
 123  * The same identifiers are used in parametrize_nested_exprs.
 124  */
 125 static __isl_give isl_id_to_ast_expr *pet_expr_build_nested_ast_exprs(
 126         struct pet_expr *expr, struct pet_build_ast_expr_data *data)
 127 {
 128         int i;
 129         isl_ctx *ctx = isl_ast_build_get_ctx(data->build);
 130         isl_id_to_ast_expr *id2expr;
 131
 132         id2expr = isl_id_to_ast_expr_alloc(ctx, expr->n_arg);
 133
 134         for (i = 0; i < expr->n_arg; ++i) {
 135                 isl_id *id = isl_id_alloc(ctx, NULL, expr->args[i]);
 136                 isl_ast_expr *ast_expr;
 137
 138                 ast_expr = pet_expr_build_ast_expr(expr->args[i], data);
 139                 id2expr = isl_id_to_ast_expr_set(id2expr, id, ast_expr);
 140         }
 141
 142         return id2expr;
 143 }
 144
 145 /* Construct an AST expression from an access expression.
 146  *
 147  * If the expression has any arguments, we first convert those
 148  * to AST expressions and replace the references to those arguments
 149  * in the index expression by parameters.
 150  *
 151  * Then we apply the index transformation if any was provided by the user.
 152  *
 153  * If the "access" is actually an affine expression, we print is as such.
 154  * Otherwise, we print a proper access.
 155  *
 156  * If the original expression had any arguments, then they are plugged in now.
 157  *
 158  * Finally, we apply an AST transformation on the result, if any was provided
 159  * by the user.
 160  */
 161 static __isl_give isl_ast_expr *pet_expr_build_ast_expr(struct pet_expr *expr,
 162         struct pet_build_ast_expr_data *data)
 163 {
 164         isl_pw_aff *pa;
 165         isl_multi_pw_aff *mpa;
 166         isl_ast_expr *ast_expr;
 167         isl_id_to_ast_expr *id2expr;
 168         isl_ast_build *build = data->build;
 169
 170         if (!expr)
 171                 return NULL;
 172         if (expr->type != pet_expr_access)
 173                 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
 174                         "not an access expression", return NULL);
 175
 176         mpa = isl_multi_pw_aff_copy(expr->acc.index);
 177
 178         if (expr->n_arg > 0) {
 179                 mpa = parametrize_nested_exprs(mpa, expr);
 180                 id2expr = pet_expr_build_nested_ast_exprs(expr, data);
 181         }
 182
 183         if (data->fn_index)
 184                 mpa = data->fn_index(mpa, expr->acc.ref_id, data->user_index);
 185         mpa = isl_multi_pw_aff_coalesce(mpa);
 186
 187         if (!pet_expr_is_affine(expr)) {
 188                 ast_expr = isl_ast_build_access_from_multi_pw_aff(build, mpa);
 189         } else {
 190                 pa = isl_multi_pw_aff_get_pw_aff(mpa, 0);
 191                 ast_expr = isl_ast_build_expr_from_pw_aff(build, pa);
 192                 isl_multi_pw_aff_free(mpa);
 193         }
 194         if (expr->n_arg > 0)
 195                 ast_expr = isl_ast_expr_substitute_ids(ast_expr, id2expr);
 196         if (data->fn_expr)
 197                 ast_expr = data->fn_expr(ast_expr, expr->acc.ref_id,
 198                                             data->user_index);
 199
 200         return ast_expr;
 201 }
 202
 203 /* Construct an AST expression from the access expression "expr" and
 204  * add the mapping from reference identifier to AST expression to
 205  * data->ref2expr.
 206  */
 207 static int add_access(struct pet_expr *expr, void *user)
 208 {
 209         struct pet_build_ast_expr_data *data = user;
 210         isl_id *id;
 211         isl_ast_expr *ast_expr;
 212
 213         ast_expr = pet_expr_build_ast_expr(expr, data);
 214
 215         id = isl_id_copy(expr->acc.ref_id);
 216         data->ref2expr = isl_id_to_ast_expr_set(data->ref2expr, id, ast_expr);
 217
 218         return 0;
 219 }
 220
 221 /* Construct an associative array from reference identifiers of
 222  * access expressions in "stmt" to the corresponding isl_ast_expr.
 223  * Each index expression is first transformed through "fn_index"
 224  * (if not NULL).  Then an AST expression is generated using "build".
 225  * Finally, the AST expression is transformed using "fn_expr"
 226  * (if not NULL).
 227  */
 228 __isl_give isl_id_to_ast_expr *pet_stmt_build_ast_exprs(struct pet_stmt *stmt,
 229         __isl_keep isl_ast_build *build,
 230         __isl_give isl_multi_pw_aff *(*fn_index)(
 231                 __isl_take isl_multi_pw_aff *mpa, __isl_keep isl_id *id,
 232                 void *user), void *user_index,
 233         __isl_give isl_ast_expr *(*fn_expr)(__isl_take isl_ast_expr *expr,
 234                 __isl_keep isl_id *id, void *user), void *user_expr)
 235 {
 236         struct pet_build_ast_expr_data data =
 237                 { build, fn_index, user_index, fn_expr, user_expr };
 238         isl_ctx *ctx;
 239
 240         if (!stmt || !build)
 241                 return NULL;
 242
 243         ctx = isl_ast_build_get_ctx(build);
 244         data.ref2expr = isl_id_to_ast_expr_alloc(ctx, 0);
 245         if (pet_expr_foreach_access_expr(stmt->body, &add_access, &data) < 0)
 246                 data.ref2expr = isl_id_to_ast_expr_free(data.ref2expr);
 247
 248         return data.ref2expr;
 249 }
 250
 251 /* Print the access expression "expr" to "p".
 252  *
 253  * We look up the corresponding isl_ast_expr in "ref2expr"
 254  * and print that to "p".
 255  */
 256 static __isl_give isl_printer *print_access(__isl_take isl_printer *p,
 257         struct pet_expr *expr, __isl_keep isl_id_to_ast_expr *ref2expr)
 258 {
 259         isl_ast_expr *ast_expr;
 260         int is_access;
 261
 262         if (!isl_id_to_ast_expr_has(ref2expr, expr->acc.ref_id))
 263                 isl_die(isl_printer_get_ctx(p), isl_error_internal,
 264                         "missing expression", return isl_printer_free(p));
 265
 266         ast_expr = isl_id_to_ast_expr_get(ref2expr,
 267                                         isl_id_copy(expr->acc.ref_id));
 268         is_access = isl_ast_expr_get_type(ast_expr) == isl_ast_expr_op &&
 269                 isl_ast_expr_get_op_type(ast_expr) == isl_ast_op_access;
 270         if (!is_access)
 271                 p = isl_printer_print_str(p, "(");
 272         p = isl_printer_print_ast_expr(p, ast_expr);
 273         if (!is_access)
 274                 p = isl_printer_print_str(p, ")");
 275         isl_ast_expr_free(ast_expr);
 276
 277         return p;
 278 }
 279
 280 /* Is "op" a postfix operator?
 281  */
 282 static int is_postfix(enum pet_op_type op)
 283 {
 284         switch (op) {
 285         case pet_op_post_inc:
 286         case pet_op_post_dec:
 287                 return 1;
 288         default:
 289                 return 0;
 290         }
 291 }
 292
 293 static __isl_give isl_printer *print_pet_expr(__isl_take isl_printer *p,
 294         struct pet_expr *expr, int outer,
 295         __isl_keep isl_id_to_ast_expr *ref2expr);
 296
 297 /* Print operation expression "expr" to "p".
 298  *
 299  * The access subexpressions are replaced by the isl_ast_expr
 300  * associated to its reference identifier in "ref2expr".
 301  */
 302 static __isl_give isl_printer *print_op(__isl_take isl_printer *p,
 303         struct pet_expr *expr, __isl_keep isl_id_to_ast_expr *ref2expr)
 304 {
 305         switch (expr->n_arg) {
 306         case 1:
 307                 if (!is_postfix(expr->op))
 308                         p = isl_printer_print_str(p, pet_op_str(expr->op));
 309                 p = print_pet_expr(p, expr->args[pet_un_arg], 0, ref2expr);
 310                 if (is_postfix(expr->op))
 311                         p = isl_printer_print_str(p, pet_op_str(expr->op));
 312                 break;
 313         case 2:
 314                 p = print_pet_expr(p, expr->args[pet_bin_lhs], 0,
 315                                         ref2expr);
 316                 p = isl_printer_print_str(p, " ");
 317                 p = isl_printer_print_str(p, pet_op_str(expr->op));
 318                 p = isl_printer_print_str(p, " ");
 319                 p = print_pet_expr(p, expr->args[pet_bin_rhs], 0,
 320                                         ref2expr);
 321                 break;
 322         case 3:
 323                 p = print_pet_expr(p, expr->args[pet_ter_cond], 0,
 324                                         ref2expr);
 325                 p = isl_printer_print_str(p, " ? ");
 326                 p = print_pet_expr(p, expr->args[pet_ter_true], 0,
 327                                         ref2expr);
 328                 p = isl_printer_print_str(p, " : ");
 329                 p = print_pet_expr(p, expr->args[pet_ter_false], 0,
 330                                         ref2expr);
 331                 break;
 332         }
 333
 334         return p;
 335 }
 336
 337 /* Print "expr" to "p".
 338  *
 339  * If "outer" is set, then we are printing the outer expression statement.
 340  *
 341  * The access subexpressions are replaced by the isl_ast_expr
 342  * associated to its reference identifier in "ref2expr".
 343  */
 344 static __isl_give isl_printer *print_pet_expr(__isl_take isl_printer *p,
 345         struct pet_expr *expr, int outer,
 346         __isl_keep isl_id_to_ast_expr *ref2expr)
 347 {
 348         int i;
 349
 350         switch (expr->type) {
 351         case pet_expr_int:
 352                 p = isl_printer_print_val(p, expr->i);
 353                 break;
 354         case pet_expr_double:
 355                 p = isl_printer_print_str(p, expr->d.s);
 356                 break;
 357         case pet_expr_access:
 358                 p = print_access(p, expr, ref2expr);
 359                 break;
 360         case pet_expr_op:
 361                 if (!outer)
 362                         p = isl_printer_print_str(p, "(");
 363                 p = print_op(p, expr, ref2expr);
 364                 if (!outer)
 365                         p = isl_printer_print_str(p, ")");
 366                 break;
 367         case pet_expr_call:
 368                 p = isl_printer_print_str(p, expr->name);
 369                 p = isl_printer_print_str(p, "(");
 370                 for (i = 0; i < expr->n_arg; ++i) {
 371                         if (i)
 372                                 p = isl_printer_print_str(p, ", ");
 373                         p = print_pet_expr(p, expr->args[i], 1, ref2expr);
 374                 }
 375                 p = isl_printer_print_str(p, ")");
 376                 break;
 377         case pet_expr_cast:
 378                 if (!outer)
 379                         p = isl_printer_print_str(p, "(");
 380                 p = isl_printer_print_str(p, "(");
 381                 p = isl_printer_print_str(p, expr->type_name);
 382                 p = isl_printer_print_str(p, ") ");
 383                 p = print_pet_expr(p, expr->args[0], 0, ref2expr);
 384                 if (!outer)
 385                         p = isl_printer_print_str(p, ")");
 386                 break;
 387         }
 388
 389         return p;
 390 }
 391
 392 /* Print "stmt" to "p".
 393  *
 394  * The access expressions in "stmt" are replaced by the isl_ast_expr
 395  * associated to its reference identifier in "ref2expr".
 396  *
 397  * If the statement is an assume statement, then we print nothing.
 398  */
 399 __isl_give isl_printer *pet_stmt_print_body(struct pet_stmt *stmt,
 400         __isl_take isl_printer *p, __isl_keep isl_id_to_ast_expr *ref2expr)
 401 {
 402         if (!stmt)
 403                 return isl_printer_free(p);
 404         if (pet_stmt_is_assume(stmt))
 405                 return p;
 406         p = isl_printer_start_line(p);
 407         p = print_pet_expr(p, stmt->body, 1, ref2expr);
 408         p = isl_printer_print_str(p, ";");
 409         p = isl_printer_end_line(p);
 410
 411         return p;
 412 }
 413
 414 /* Copy the contents of "input" from offset "start" to "end" to "output".
 415  */
 416 int copy(FILE *input, FILE *output, long start, long end)
 417 {
 418         char buffer[1024];
 419         size_t n, m;
 420
 421         if (end < 0) {
 422                 fseek(input, 0, SEEK_END);
 423                 end = ftell(input);
 424         }
 425
 426         fseek(input, start, SEEK_SET);
 427
 428         while (start < end) {
 429                 n = end - start;
 430                 if (n > 1024)
 431                         n = 1024;
 432                 n = fread(buffer, 1, n, input);
 433                 if (n <= 0)
 434                         return -1;
 435                 m = fwrite(buffer, 1, n, output);
 436                 if (n != m)
 437                         return -1;
 438                 start += n;
 439         }
 440
 441         return 0;
 442 }