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