print.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 <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 /* Given an access expression, check if any of its arguments
  44  * are not themselves access expressions.
  45  * If so, set *found and abort the search.
  46  */
  47 static int depends_on_expressions(__isl_keep pet_expr *expr, void *user)
  48 {
  49         int i;
  50         int *found = user;
  51
  52         for (i = 0; i < expr->n_arg; ++i)
  53                 if (expr->args[i]->type != pet_expr_access) {
  54                         *found = 1;
  55                         return -1;
  56                 }
  57
  58         return 0;
  59 }
  60
  61 /* pet_stmt_build_ast_exprs is currently limited to only handle
  62  * some forms of data dependent accesses.
  63  * If pet_stmt_can_build_ast_exprs returns 1, then pet_stmt_build_ast_exprs
  64  * can safely be called on "stmt".
  65  */
  66 int pet_stmt_can_build_ast_exprs(struct pet_stmt *stmt)
  67 {
  68         int r;
  69         int found = 0;
  70
  71         if (!stmt)
  72                 return -1;
  73
  74         r = pet_tree_foreach_access_expr(stmt->body,
  75                                         &depends_on_expressions, &found);
  76         if (r < 0 && !found)
  77                 return -1;
  78
  79         return !found;
  80 }
  81
  82 /* pet_stmt_build_ast_exprs is currently limited to only handle
  83  * some forms of data dependent accesses.
  84  * If pet_scop_can_build_ast_exprs returns 1, then pet_stmt_build_ast_exprs
  85  * can safely be called on all statements in the scop.
  86  */
  87 int pet_scop_can_build_ast_exprs(struct pet_scop *scop)
  88 {
  89         int i;
  90
  91         if (!scop)
  92                 return -1;
  93
  94         for (i = 0; i < scop->n_stmt; ++i) {
  95                 int ok = pet_stmt_can_build_ast_exprs(scop->stmts[i]);
  96                 if (ok < 0 || !ok)
  97                         return ok;
  98         }
  99
 100         return 1;
 101 }
 102
 103 /* Internal data structure for pet_stmt_build_ast_exprs.
 104  *
 105  * "build" is used to construct an AST expression from an index expression.
 106  * "fn_index" is used to transform the index expression prior to
 107  *      the construction of the AST expression.
 108  * "fn_expr" is used to transform the constructed AST expression.
 109  * "ref2expr" collects the results.
 110  */
 111 struct pet_build_ast_expr_data {
 112         isl_ast_build *build;
 113         __isl_give isl_multi_pw_aff *(*fn_index)(
 114                 __isl_take isl_multi_pw_aff *mpa, __isl_keep isl_id *id,
 115                 void *user);
 116         void *user_index;
 117         __isl_give isl_ast_expr *(*fn_expr)(__isl_take isl_ast_expr *expr,
 118                 __isl_keep isl_id *id, void *user);
 119         void *user_expr;
 120         isl_id_to_ast_expr *ref2expr;
 121 };
 122
 123 /* Given an index expression "index" with nested expressions, replace
 124  * those nested expressions by parameters.  The identifiers
 125  * of those parameters reference the corresponding arguments
 126  * of "expr".  The same identifiers are used in
 127  * pet_expr_build_nested_ast_exprs.
 128  *
 129  * In particular, if "index" is of the form
 130  *
 131  *      { [domain -> [e_1, ..., e_n]] -> array[f(e_1, ..., e_n)] }
 132  *
 133  * then we construct the expression
 134  *
 135  *      [p_1, ..., p_n] -> { domain -> array[f(p_1, ..., p_n)] }
 136  *
 137  */
 138 static __isl_give isl_multi_pw_aff *parametrize_nested_exprs(
 139         __isl_take isl_multi_pw_aff *index, __isl_keep pet_expr *expr)
 140 {
 141         int i;
 142         isl_ctx *ctx;
 143         isl_space *space, *space2;
 144         isl_local_space *ls;
 145         isl_multi_aff *ma, *ma2;
 146
 147         ctx = isl_multi_pw_aff_get_ctx(index);
 148         space = isl_multi_pw_aff_get_domain_space(index);
 149         space = isl_space_unwrap(space);
 150
 151         space2 = isl_space_domain(isl_space_copy(space));
 152         ma = isl_multi_aff_identity(isl_space_map_from_set(space2));
 153
 154         space = isl_space_insert_dims(space, isl_dim_param, 0,
 155                                         expr->n_arg);
 156         for (i = 0; i < expr->n_arg; ++i) {
 157                 isl_id *id = isl_id_alloc(ctx, NULL, expr->args[i]);
 158
 159                 space = isl_space_set_dim_id(space, isl_dim_param, i, id);
 160         }
 161         space2 = isl_space_domain(isl_space_copy(space));
 162         ls = isl_local_space_from_space(space2);
 163         ma2 = isl_multi_aff_zero(space);
 164         for (i = 0; i < expr->n_arg; ++i) {
 165                 isl_aff *aff;
 166                 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
 167                                                 isl_dim_param, i);
 168                 ma2 = isl_multi_aff_set_aff(ma2, i, aff);
 169         }
 170         isl_local_space_free(ls);
 171
 172         ma = isl_multi_aff_range_product(ma, ma2);
 173
 174         return isl_multi_pw_aff_pullback_multi_aff(index, ma);
 175 }
 176
 177 static __isl_give isl_ast_expr *pet_expr_build_ast_expr(
 178         __isl_keep pet_expr *expr, struct pet_build_ast_expr_data *data);
 179
 180 /* Construct an associative array from identifiers for the nested
 181  * expressions of "expr" to the corresponding isl_ast_expr.
 182  * The identifiers reference the corresponding arguments of "expr".
 183  * The same identifiers are used in parametrize_nested_exprs.
 184  */
 185 static __isl_give isl_id_to_ast_expr *pet_expr_build_nested_ast_exprs(
 186         __isl_keep pet_expr *expr, struct pet_build_ast_expr_data *data)
 187 {
 188         int i;
 189         isl_ctx *ctx = isl_ast_build_get_ctx(data->build);
 190         isl_id_to_ast_expr *id2expr;
 191
 192         id2expr = isl_id_to_ast_expr_alloc(ctx, expr->n_arg);
 193
 194         for (i = 0; i < expr->n_arg; ++i) {
 195                 isl_id *id = isl_id_alloc(ctx, NULL, expr->args[i]);
 196                 isl_ast_expr *ast_expr;
 197
 198                 ast_expr = pet_expr_build_ast_expr(expr->args[i], data);
 199                 id2expr = isl_id_to_ast_expr_set(id2expr, id, ast_expr);
 200         }
 201
 202         return id2expr;
 203 }
 204
 205 /* Construct an AST expression from an access expression.
 206  *
 207  * If the expression has any arguments, we first convert those
 208  * to AST expressions and replace the references to those arguments
 209  * in the index expression by parameters.
 210  *
 211  * Then we apply the index transformation if any was provided by the user.
 212  *
 213  * If the "access" is actually an affine expression, we print is as such.
 214  * Otherwise, we print a proper access.
 215  *
 216  * If the original expression had any arguments, then they are plugged in now.
 217  *
 218  * Finally, we apply an AST transformation on the result, if any was provided
 219  * by the user.
 220  */
 221 static __isl_give isl_ast_expr *pet_expr_build_ast_expr(
 222         __isl_keep pet_expr *expr, struct pet_build_ast_expr_data *data)
 223 {
 224         isl_pw_aff *pa;
 225         isl_multi_pw_aff *mpa;
 226         isl_ast_expr *ast_expr;
 227         isl_id_to_ast_expr *id2expr;
 228         isl_ast_build *build = data->build;
 229
 230         if (!expr)
 231                 return NULL;
 232         if (expr->type != pet_expr_access)
 233                 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
 234                         "not an access expression", return NULL);
 235
 236         mpa = isl_multi_pw_aff_copy(expr->acc.index);
 237
 238         if (expr->n_arg > 0) {
 239                 mpa = parametrize_nested_exprs(mpa, expr);
 240                 id2expr = pet_expr_build_nested_ast_exprs(expr, data);
 241         }
 242
 243         if (data->fn_index)
 244                 mpa = data->fn_index(mpa, expr->acc.ref_id, data->user_index);
 245         mpa = isl_multi_pw_aff_coalesce(mpa);
 246
 247         if (!pet_expr_is_affine(expr)) {
 248                 ast_expr = isl_ast_build_access_from_multi_pw_aff(build, mpa);
 249         } else {
 250                 pa = isl_multi_pw_aff_get_pw_aff(mpa, 0);
 251                 ast_expr = isl_ast_build_expr_from_pw_aff(build, pa);
 252                 isl_multi_pw_aff_free(mpa);
 253         }
 254         if (expr->n_arg > 0)
 255                 ast_expr = isl_ast_expr_substitute_ids(ast_expr, id2expr);
 256         if (data->fn_expr)
 257                 ast_expr = data->fn_expr(ast_expr, expr->acc.ref_id,
 258                                             data->user_index);
 259
 260         return ast_expr;
 261 }
 262
 263 /* Construct an AST expression from the access expression "expr" and
 264  * add the mapping from reference identifier to AST expression to
 265  * data->ref2expr.
 266  */
 267 static int add_access(__isl_keep pet_expr *expr, void *user)
 268 {
 269         struct pet_build_ast_expr_data *data = user;
 270         isl_id *id;
 271         isl_ast_expr *ast_expr;
 272
 273         ast_expr = pet_expr_build_ast_expr(expr, data);
 274
 275         id = isl_id_copy(expr->acc.ref_id);
 276         data->ref2expr = isl_id_to_ast_expr_set(data->ref2expr, id, ast_expr);
 277
 278         return 0;
 279 }
 280
 281 /* Construct an associative array from reference identifiers of
 282  * access expressions in "stmt" to the corresponding isl_ast_expr.
 283  * Each index expression is first transformed through "fn_index"
 284  * (if not NULL).  Then an AST expression is generated using "build".
 285  * Finally, the AST expression is transformed using "fn_expr"
 286  * (if not NULL).
 287  */
 288 __isl_give isl_id_to_ast_expr *pet_stmt_build_ast_exprs(struct pet_stmt *stmt,
 289         __isl_keep isl_ast_build *build,
 290         __isl_give isl_multi_pw_aff *(*fn_index)(
 291                 __isl_take isl_multi_pw_aff *mpa, __isl_keep isl_id *id,
 292                 void *user), void *user_index,
 293         __isl_give isl_ast_expr *(*fn_expr)(__isl_take isl_ast_expr *expr,
 294                 __isl_keep isl_id *id, void *user), void *user_expr)
 295 {
 296         struct pet_build_ast_expr_data data =
 297                 { build, fn_index, user_index, fn_expr, user_expr };
 298         isl_ctx *ctx;
 299
 300         if (!stmt || !build)
 301                 return NULL;
 302
 303         ctx = isl_ast_build_get_ctx(build);
 304         data.ref2expr = isl_id_to_ast_expr_alloc(ctx, 0);
 305         if (pet_tree_foreach_access_expr(stmt->body, &add_access, &data) < 0)
 306                 data.ref2expr = isl_id_to_ast_expr_free(data.ref2expr);
 307
 308         return data.ref2expr;
 309 }
 310
 311 /* Print the access expression "expr" to "p".
 312  *
 313  * We look up the corresponding isl_ast_expr in "ref2expr"
 314  * and print that to "p".
 315  */
 316 static __isl_give isl_printer *print_access(__isl_take isl_printer *p,
 317         __isl_keep pet_expr *expr, __isl_keep isl_id_to_ast_expr *ref2expr)
 318 {
 319         isl_ast_expr *ast_expr;
 320         int is_access;
 321
 322         if (!isl_id_to_ast_expr_has(ref2expr, expr->acc.ref_id))
 323                 isl_die(isl_printer_get_ctx(p), isl_error_internal,
 324                         "missing expression", return isl_printer_free(p));
 325
 326         ast_expr = isl_id_to_ast_expr_get(ref2expr,
 327                                         isl_id_copy(expr->acc.ref_id));
 328         is_access = isl_ast_expr_get_type(ast_expr) == isl_ast_expr_op &&
 329                 isl_ast_expr_get_op_type(ast_expr) == isl_ast_op_access;
 330         if (!is_access)
 331                 p = isl_printer_print_str(p, "(");
 332         p = isl_printer_print_ast_expr(p, ast_expr);
 333         if (!is_access)
 334                 p = isl_printer_print_str(p, ")");
 335         isl_ast_expr_free(ast_expr);
 336
 337         return p;
 338 }
 339
 340 /* Is "op" a postfix operator?
 341  */
 342 static int is_postfix(enum pet_op_type op)
 343 {
 344         switch (op) {
 345         case pet_op_post_inc:
 346         case pet_op_post_dec:
 347                 return 1;
 348         default:
 349                 return 0;
 350         }
 351 }
 352
 353 static __isl_give isl_printer *print_pet_expr(__isl_take isl_printer *p,
 354         __isl_keep pet_expr *expr, int outer,
 355         __isl_keep isl_id_to_ast_expr *ref2expr);
 356
 357 /* Print operation expression "expr" to "p".
 358  *
 359  * The access subexpressions are replaced by the isl_ast_expr
 360  * associated to its reference identifier in "ref2expr".
 361  */
 362 static __isl_give isl_printer *print_op(__isl_take isl_printer *p,
 363         __isl_keep pet_expr *expr, __isl_keep isl_id_to_ast_expr *ref2expr)
 364 {
 365         switch (expr->n_arg) {
 366         case 1:
 367                 if (!is_postfix(expr->op))
 368                         p = isl_printer_print_str(p, pet_op_str(expr->op));
 369                 p = print_pet_expr(p, expr->args[pet_un_arg], 0, ref2expr);
 370                 if (is_postfix(expr->op))
 371                         p = isl_printer_print_str(p, pet_op_str(expr->op));
 372                 break;
 373         case 2:
 374                 p = print_pet_expr(p, expr->args[pet_bin_lhs], 0,
 375                                         ref2expr);
 376                 p = isl_printer_print_str(p, " ");
 377                 p = isl_printer_print_str(p, pet_op_str(expr->op));
 378                 p = isl_printer_print_str(p, " ");
 379                 p = print_pet_expr(p, expr->args[pet_bin_rhs], 0,
 380                                         ref2expr);
 381                 break;
 382         case 3:
 383                 p = print_pet_expr(p, expr->args[pet_ter_cond], 0,
 384                                         ref2expr);
 385                 p = isl_printer_print_str(p, " ? ");
 386                 p = print_pet_expr(p, expr->args[pet_ter_true], 0,
 387                                         ref2expr);
 388                 p = isl_printer_print_str(p, " : ");
 389                 p = print_pet_expr(p, expr->args[pet_ter_false], 0,
 390                                         ref2expr);
 391                 break;
 392         }
 393
 394         return p;
 395 }
 396
 397 /* Print "expr" to "p".
 398  *
 399  * If "outer" is set, then we are printing the outer expression statement.
 400  *
 401  * The access subexpressions are replaced by the isl_ast_expr
 402  * associated to its reference identifier in "ref2expr".
 403  */
 404 static __isl_give isl_printer *print_pet_expr(__isl_take isl_printer *p,
 405         __isl_keep pet_expr *expr, int outer,
 406         __isl_keep isl_id_to_ast_expr *ref2expr)
 407 {
 408         int i;
 409
 410         switch (expr->type) {
 411         case pet_expr_error:
 412                 p = isl_printer_free(p);
 413                 break;
 414         case pet_expr_int:
 415                 p = isl_printer_print_val(p, expr->i);
 416                 break;
 417         case pet_expr_double:
 418                 p = isl_printer_print_str(p, expr->d.s);
 419                 break;
 420         case pet_expr_access:
 421                 p = print_access(p, expr, ref2expr);
 422                 break;
 423         case pet_expr_op:
 424                 if (!outer)
 425                         p = isl_printer_print_str(p, "(");
 426                 p = print_op(p, expr, ref2expr);
 427                 if (!outer)
 428                         p = isl_printer_print_str(p, ")");
 429                 break;
 430         case pet_expr_call:
 431                 p = isl_printer_print_str(p, expr->c.name);
 432                 p = isl_printer_print_str(p, "(");
 433                 for (i = 0; i < expr->n_arg; ++i) {
 434                         if (i)
 435                                 p = isl_printer_print_str(p, ", ");
 436                         p = print_pet_expr(p, expr->args[i], 1, ref2expr);
 437                 }
 438                 p = isl_printer_print_str(p, ")");
 439                 break;
 440         case pet_expr_cast:
 441                 if (!outer)
 442                         p = isl_printer_print_str(p, "(");
 443                 p = isl_printer_print_str(p, "(");
 444                 p = isl_printer_print_str(p, expr->type_name);
 445                 p = isl_printer_print_str(p, ") ");
 446                 p = print_pet_expr(p, expr->args[0], 0, ref2expr);
 447                 if (!outer)
 448                         p = isl_printer_print_str(p, ")");
 449                 break;
 450         }
 451
 452         return p;
 453 }
 454
 455 static __isl_give isl_printer *print_pet_tree(__isl_take isl_printer *p,
 456         __isl_keep pet_tree *tree, int in_block,
 457         __isl_keep isl_id_to_ast_expr *ref2expr);
 458
 459 /* Print "tree" to "p", where "tree" is of type pet_tree_block.
 460  *
 461  * If "in_block" is set, then the caller has just printed a block,
 462  * so there is no need to print one for this node.
 463  *
 464  * The access subexpressions are replaced by the isl_ast_expr
 465  * associated to its reference identifier in "ref2expr".
 466  */
 467 static __isl_give isl_printer *print_pet_tree_block(__isl_take isl_printer *p,
 468         __isl_keep pet_tree *tree, int in_block,
 469         __isl_keep isl_id_to_ast_expr *ref2expr)
 470 {
 471         int i, n;
 472
 473         if (!in_block) {
 474                 p = isl_printer_start_line(p);
 475                 p = isl_printer_print_str(p, "{");
 476                 p = isl_printer_end_line(p);
 477                 p = isl_printer_indent(p, 2);
 478         }
 479
 480         n = pet_tree_block_n_child(tree);
 481
 482         for (i = 0; i < n; ++i) {
 483                 pet_tree *child;
 484
 485                 child = pet_tree_block_get_child(tree, i);
 486                 p = print_pet_tree(p, child, 0, ref2expr);
 487                 pet_tree_free(child);
 488         }
 489
 490         if (!in_block) {
 491                 p = isl_printer_indent(p, -2);
 492                 p = isl_printer_start_line(p);
 493                 p = isl_printer_print_str(p, "}");
 494                 p = isl_printer_end_line(p);
 495         }
 496
 497         return p;
 498 }
 499
 500 /* Print "tree" to "p", where "tree" is of type pet_tree_if or
 501  * pet_tree_if_else..
 502  *
 503  * The access subexpressions are replaced by the isl_ast_expr
 504  * associated to its reference identifier in "ref2expr".
 505  */
 506 static __isl_give isl_printer *print_pet_tree_if(__isl_take isl_printer *p,
 507         __isl_keep pet_tree *tree, __isl_keep isl_id_to_ast_expr *ref2expr)
 508 {
 509         pet_expr *expr;
 510         pet_tree *body;
 511
 512         p = isl_printer_start_line(p);
 513         p = isl_printer_print_str(p, "if (");
 514         expr = pet_tree_if_get_cond(tree);
 515         p = print_pet_expr(p, expr, 1, ref2expr);
 516         pet_expr_free(expr);
 517         p = isl_printer_print_str(p, ") {");
 518         p = isl_printer_end_line(p);
 519
 520         p = isl_printer_indent(p, 2);
 521         body = pet_tree_if_get_then(tree);
 522         p = print_pet_tree(p, body, 1, ref2expr);
 523         pet_tree_free(body);
 524         p = isl_printer_indent(p, -2);
 525
 526         p = isl_printer_start_line(p);
 527         p = isl_printer_print_str(p, "}");
 528
 529         if (pet_tree_get_type(tree) == pet_tree_if_else) {
 530                 p = isl_printer_print_str(p, " else {");
 531                 p = isl_printer_end_line(p);
 532
 533                 p = isl_printer_indent(p, 2);
 534                 body = pet_tree_if_get_else(tree);
 535                 p = print_pet_tree(p, body, 1, ref2expr);
 536                 pet_tree_free(body);
 537                 p = isl_printer_indent(p, -2);
 538
 539                 p = isl_printer_start_line(p);
 540                 p = isl_printer_print_str(p, "}");
 541         }
 542
 543         p = isl_printer_end_line(p);
 544
 545         return p;
 546 }
 547
 548 /* Print "tree" to "p", where "tree" is of type pet_tree_for.
 549  *
 550  * The access subexpressions are replaced by the isl_ast_expr
 551  * associated to its reference identifier in "ref2expr".
 552  */
 553 static __isl_give isl_printer *print_pet_tree_for(__isl_take isl_printer *p,
 554         __isl_keep pet_tree *tree, __isl_keep isl_id_to_ast_expr *ref2expr)
 555 {
 556         pet_expr *expr_iv, *expr;
 557         pet_tree *body;
 558
 559         expr_iv = pet_tree_loop_get_var(tree);
 560
 561         p = isl_printer_start_line(p);
 562         p = isl_printer_print_str(p, "for (");
 563         p = print_pet_expr(p, expr_iv, 1, ref2expr);
 564         p = isl_printer_print_str(p, " = ");
 565         expr = pet_tree_loop_get_init(tree);
 566         p = print_pet_expr(p, expr, 0, ref2expr);
 567         pet_expr_free(expr);
 568         p = isl_printer_print_str(p, "; ");
 569         expr = pet_tree_loop_get_cond(tree);
 570         p = print_pet_expr(p, expr, 1, ref2expr);
 571         pet_expr_free(expr);
 572         p = isl_printer_print_str(p, "; ");
 573         p = print_pet_expr(p, expr_iv, 1, ref2expr);
 574         p = isl_printer_print_str(p, " += ");
 575         expr = pet_tree_loop_get_inc(tree);
 576         p = print_pet_expr(p, expr, 0, ref2expr);
 577         pet_expr_free(expr);
 578         p = isl_printer_print_str(p, ") {");
 579         p = isl_printer_end_line(p);
 580
 581         pet_expr_free(expr_iv);
 582
 583         p = isl_printer_indent(p, 2);
 584         body = pet_tree_loop_get_body(tree);
 585         p = print_pet_tree(p, body, 1, ref2expr);
 586         pet_tree_free(body);
 587         p = isl_printer_indent(p, -2);
 588
 589         p = isl_printer_start_line(p);
 590         p = isl_printer_print_str(p, "}");
 591         p = isl_printer_end_line(p);
 592
 593         return p;
 594 }
 595
 596 /* Print "tree" to "p", where "tree" is of type pet_tree_while or
 597  * pet_tree_infinite_loop.
 598  *
 599  * The access subexpressions are replaced by the isl_ast_expr
 600  * associated to its reference identifier in "ref2expr".
 601  *
 602  * pet_tree_loop_get_cond returns "1" when called on a tree of type
 603  * pet_tree_infinite_loop, so we can treat them in the same way
 604  * as trees of type pet_tree_while.
 605  */
 606 static __isl_give isl_printer *print_pet_tree_while(__isl_take isl_printer *p,
 607         __isl_keep pet_tree *tree, __isl_keep isl_id_to_ast_expr *ref2expr)
 608 {
 609         pet_expr *expr;
 610         pet_tree *body;
 611
 612         p = isl_printer_start_line(p);
 613         p = isl_printer_print_str(p, "while (");
 614         expr = pet_tree_loop_get_cond(tree);
 615         p = print_pet_expr(p, expr, 1, ref2expr);
 616         pet_expr_free(expr);
 617         p = isl_printer_print_str(p, ") {");
 618         p = isl_printer_end_line(p);
 619
 620         p = isl_printer_indent(p, 2);
 621         body = pet_tree_loop_get_body(tree);
 622         p = print_pet_tree(p, body, 1, ref2expr);
 623         pet_tree_free(body);
 624         p = isl_printer_indent(p, -2);
 625
 626         p = isl_printer_start_line(p);
 627         p = isl_printer_print_str(p, "}");
 628         p = isl_printer_end_line(p);
 629
 630         return p;
 631 }
 632
 633 /* Print "tree" to "p", where "tree" is of type pet_tree_decl_init.
 634  *
 635  * We assume all variables have already been declared, so we
 636  * only print the assignment implied by the declaration initialization.
 637  *
 638  * The access subexpressions are replaced by the isl_ast_expr
 639  * associated to its reference identifier in "ref2expr".
 640  */
 641 static __isl_give isl_printer *print_pet_tree_decl_init(
 642         __isl_take isl_printer *p, __isl_keep pet_tree *tree,
 643         __isl_keep isl_id_to_ast_expr *ref2expr)
 644 {
 645         pet_expr *var, *init;
 646
 647         p = isl_printer_start_line(p);
 648
 649         var = pet_tree_decl_get_var(tree);
 650         p = print_pet_expr(p, var, 1, ref2expr);
 651         pet_expr_free(var);
 652
 653         p = isl_printer_print_str(p, " = ");
 654
 655         init = pet_tree_decl_get_init(tree);
 656         p = print_pet_expr(p, init, 1, ref2expr);
 657         pet_expr_free(init);
 658
 659         p = isl_printer_print_str(p, ";");
 660         p = isl_printer_end_line(p);
 661
 662         return p;
 663 }
 664
 665 /* Print "tree" to "p".
 666  *
 667  * If "in_block" is set, then the caller has just printed a block,
 668  * so there is no need to print one for this node.
 669  *
 670  * The access subexpressions are replaced by the isl_ast_expr
 671  * associated to its reference identifier in "ref2expr".
 672  *
 673  * We assume all variables have already been declared,
 674  * so there is nothing to print for nodes of type pet_tree_decl.
 675  */
 676 static __isl_give isl_printer *print_pet_tree(__isl_take isl_printer *p,
 677         __isl_keep pet_tree *tree, int in_block,
 678         __isl_keep isl_id_to_ast_expr *ref2expr)
 679 {
 680         pet_expr *expr;
 681         enum pet_tree_type type;
 682
 683         type = pet_tree_get_type(tree);
 684         switch (type) {
 685         case pet_tree_error:
 686                 return isl_printer_free(p);
 687         case pet_tree_block:
 688                 return print_pet_tree_block(p, tree, in_block, ref2expr);
 689         case pet_tree_break:
 690         case pet_tree_continue:
 691                 p = isl_printer_start_line(p);
 692                 if (type == pet_tree_break)
 693                         p = isl_printer_print_str(p, "break;");
 694                 else
 695                         p = isl_printer_print_str(p, "continue;");
 696                 return isl_printer_end_line(p);
 697         case pet_tree_expr:
 698                 expr = pet_tree_expr_get_expr(tree);
 699                 p = isl_printer_start_line(p);
 700                 p = print_pet_expr(p, expr, 1, ref2expr);
 701                 p = isl_printer_print_str(p, ";");
 702                 p = isl_printer_end_line(p);
 703                 pet_expr_free(expr);
 704                 break;
 705         case pet_tree_if:
 706         case pet_tree_if_else:
 707                 return print_pet_tree_if(p, tree, ref2expr);
 708         case pet_tree_for:
 709                 return print_pet_tree_for(p, tree, ref2expr);
 710         case pet_tree_while:
 711         case pet_tree_infinite_loop:
 712                 return print_pet_tree_while(p, tree, ref2expr);
 713         case pet_tree_decl:
 714                 return p;
 715         case pet_tree_decl_init:
 716                 return print_pet_tree_decl_init(p, tree, ref2expr);
 717         }
 718
 719         return p;
 720 }
 721
 722 /* Print "stmt" to "p".
 723  *
 724  * The access expressions in "stmt" are replaced by the isl_ast_expr
 725  * associated to its reference identifier in "ref2expr".
 726  *
 727  * If the statement is an assume statement, then we print nothing.
 728  */
 729 __isl_give isl_printer *pet_stmt_print_body(struct pet_stmt *stmt,
 730         __isl_take isl_printer *p, __isl_keep isl_id_to_ast_expr *ref2expr)
 731 {
 732         if (!stmt)
 733                 return isl_printer_free(p);
 734         if (pet_stmt_is_assume(stmt))
 735                 return p;
 736         p = print_pet_tree(p, stmt->body, 0, ref2expr);
 737
 738         return p;
 739 }
 740
 741 /* Copy the contents of "input" from offset "start" to "end" to "output".
 742  */
 743 int copy(FILE *input, FILE *output, long start, long end)
 744 {
 745         char buffer[1024];
 746         size_t n, m;
 747
 748         if (end < 0) {
 749                 fseek(input, 0, SEEK_END);
 750                 end = ftell(input);
 751         }
 752
 753         fseek(input, start, SEEK_SET);
 754
 755         while (start < end) {
 756                 n = end - start;
 757                 if (n > 1024)
 758                         n = 1024;
 759                 n = fread(buffer, 1, n, input);
 760                 if (n <= 0)
 761                         return -1;
 762                 m = fwrite(buffer, 1, n, output);
 763                 if (n != m)
 764                         return -1;
 765                 start += n;
 766         }
 767
 768         return 0;
 769 }