scop.c

   1 #include <isl/constraint.h>
   2 #include <isl/union_set.h>
   3
   4 #include "scop.h"
   5
   6 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
   7
   8 static char *type_str[] = {
   9         [pet_expr_access] = "access",
  10         [pet_expr_call] = "call",
  11         [pet_expr_double] = "double",
  12         [pet_expr_unary] = "unary",
  13         [pet_expr_binary] = "binary",
  14         [pet_expr_ternary] = "ternary"
  15 };
  16
  17 static char *op_str[] = {
  18         [pet_op_add_assign] = "+=",
  19         [pet_op_sub_assign] = "-=",
  20         [pet_op_mul_assign] = "*=",
  21         [pet_op_div_assign] = "/=",
  22         [pet_op_assign] = "=",
  23         [pet_op_add] = "+",
  24         [pet_op_sub] = "-",
  25         [pet_op_mul] = "*",
  26         [pet_op_div] = "/",
  27         [pet_op_le] = "<=",
  28         [pet_op_lt] = "<",
  29         [pet_op_gt] = ">",
  30         [pet_op_minus] = "-"
  31 };
  32
  33 const char *pet_op_str(enum pet_op_type op)
  34 {
  35         return op_str[op];
  36 }
  37
  38 const char *pet_type_str(enum pet_expr_type type)
  39 {
  40         return type_str[type];
  41 }
  42
  43 enum pet_op_type pet_str_op(const char *str)
  44 {
  45         int i;
  46
  47         for (i = 0; i < ARRAY_SIZE(op_str); ++i)
  48                 if (!strcmp(op_str[i], str))
  49                         return i;
  50
  51         return -1;
  52 }
  53
  54 enum pet_expr_type pet_str_type(const char *str)
  55 {
  56         int i;
  57
  58         for (i = 0; i < ARRAY_SIZE(type_str); ++i)
  59                 if (!strcmp(type_str[i], str))
  60                         return i;
  61
  62         return -1;
  63 }
  64
  65 /* Construct a pet_expr from an access relation.
  66  * By default, it is considered to be a read access.
  67  */
  68 struct pet_expr *pet_expr_from_access(__isl_take isl_map *access)
  69 {
  70         isl_ctx *ctx = isl_map_get_ctx(access);
  71         struct pet_expr *expr;
  72
  73         if (!access)
  74                 return NULL;
  75         expr = isl_calloc_type(ctx, struct pet_expr);
  76         if (!expr)
  77                 goto error;
  78
  79         expr->type = pet_expr_access;
  80         expr->acc.access = access;
  81         expr->acc.read = 1;
  82         expr->acc.write = 0;
  83
  84         return expr;
  85 error:
  86         isl_map_free(access);
  87         return NULL;
  88 }
  89
  90 /* Construct a unary pet_expr that performs "op" on "arg".
  91  */
  92 struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op,
  93         struct pet_expr *arg)
  94 {
  95         struct pet_expr *expr;
  96
  97         if (!arg)
  98                 goto error;
  99         expr = isl_alloc_type(ctx, struct pet_expr);
 100         if (!expr)
 101                 goto error;
 102
 103         expr->type = pet_expr_unary;
 104         expr->op = op;
 105         expr->n_arg = 1;
 106         expr->args = isl_calloc_array(ctx, struct pet_expr *, 1);
 107         if (!expr->args)
 108                 goto error;
 109         expr->args[pet_un_arg] = arg;
 110
 111         return expr;
 112 error:
 113         pet_expr_free(arg);
 114         return NULL;
 115 }
 116
 117 /* Construct a binary pet_expr that performs "op" on "lhs" and "rhs".
 118  */
 119 struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op,
 120         struct pet_expr *lhs, struct pet_expr *rhs)
 121 {
 122         struct pet_expr *expr;
 123
 124         if (!lhs || !rhs)
 125                 goto error;
 126         expr = isl_alloc_type(ctx, struct pet_expr);
 127         if (!expr)
 128                 goto error;
 129
 130         expr->type = pet_expr_binary;
 131         expr->op = op;
 132         expr->n_arg = 2;
 133         expr->args = isl_calloc_array(ctx, struct pet_expr *, 2);
 134         if (!expr->args)
 135                 goto error;
 136         expr->args[pet_bin_lhs] = lhs;
 137         expr->args[pet_bin_rhs] = rhs;
 138
 139         return expr;
 140 error:
 141         pet_expr_free(lhs);
 142         pet_expr_free(rhs);
 143         return NULL;
 144 }
 145
 146 /* Construct a ternary pet_expr that performs "cond" ? "lhs" : "rhs".
 147  */
 148 struct pet_expr *pet_expr_new_ternary(isl_ctx *ctx, struct pet_expr *cond,
 149         struct pet_expr *lhs, struct pet_expr *rhs)
 150 {
 151         struct pet_expr *expr;
 152
 153         if (!cond || !lhs || !rhs)
 154                 goto error;
 155         expr = isl_alloc_type(ctx, struct pet_expr);
 156         if (!expr)
 157                 goto error;
 158
 159         expr->type = pet_expr_ternary;
 160         expr->n_arg = 3;
 161         expr->args = isl_calloc_array(ctx, struct pet_expr *, 3);
 162         if (!expr->args)
 163                 goto error;
 164         expr->args[pet_ter_cond] = cond;
 165         expr->args[pet_ter_true] = lhs;
 166         expr->args[pet_ter_false] = rhs;
 167
 168         return expr;
 169 error:
 170         pet_expr_free(cond);
 171         pet_expr_free(lhs);
 172         pet_expr_free(rhs);
 173         return NULL;
 174 }
 175
 176 /* Construct a call pet_expr that calls function "name" with "n_arg"
 177  * arguments.  The caller is responsible for filling in the arguments.
 178  */
 179 struct pet_expr *pet_expr_new_call(isl_ctx *ctx, const char *name,
 180         unsigned n_arg)
 181 {
 182         struct pet_expr *expr;
 183
 184         expr = isl_alloc_type(ctx, struct pet_expr);
 185         if (!expr)
 186                 return NULL;
 187
 188         expr->type = pet_expr_call;
 189         expr->n_arg = n_arg;
 190         expr->name = strdup(name);
 191         expr->args = isl_calloc_array(ctx, struct pet_expr *, n_arg);
 192         if (!expr->name || !expr->args)
 193                 return pet_expr_free(expr);
 194
 195         return expr;
 196 }
 197
 198 /* Construct a pet_expr that represents the double "d".
 199  */
 200 struct pet_expr *pet_expr_new_double(isl_ctx *ctx, double d)
 201 {
 202         struct pet_expr *expr;
 203
 204         expr = isl_calloc_type(ctx, struct pet_expr);
 205         if (!expr)
 206                 return NULL;
 207
 208         expr->type = pet_expr_double;
 209         expr->d = d;
 210
 211         return expr;
 212 }
 213
 214 void *pet_expr_free(struct pet_expr *expr)
 215 {
 216         int i;
 217
 218         if (!expr)
 219                 return NULL;
 220
 221         for (i = 0; i < expr->n_arg; ++i)
 222                 pet_expr_free(expr->args[i]);
 223         free(expr->args);
 224
 225         switch (expr->type) {
 226         case pet_expr_access:
 227                 isl_map_free(expr->acc.access);
 228                 break;
 229         case pet_expr_call:
 230                 free(expr->name);
 231                 break;
 232         case pet_expr_double:
 233         case pet_expr_unary:
 234         case pet_expr_binary:
 235         case pet_expr_ternary:
 236                 break;
 237         }
 238
 239         free(expr);
 240         return NULL;
 241 }
 242
 243 static void expr_dump(struct pet_expr *expr, int indent)
 244 {
 245         int i;
 246
 247         if (!expr)
 248                 return;
 249
 250         fprintf(stderr, "%*s", indent, "");
 251
 252         switch (expr->type) {
 253         case pet_expr_double:
 254                 fprintf(stderr, "%g\n", expr->d);
 255                 break;
 256         case pet_expr_access:
 257                 isl_map_dump(expr->acc.access);
 258                 fprintf(stderr, "%*sread: %d\n", indent + 2,
 259                                 "", expr->acc.read);
 260                 fprintf(stderr, "%*swrite: %d\n", indent + 2,
 261                                 "", expr->acc.write);
 262                 for (i = 0; i < expr->n_arg; ++i)
 263                         expr_dump(expr->args[i], indent + 2);
 264                 break;
 265         case pet_expr_unary:
 266                 fprintf(stderr, "%s\n", op_str[expr->op]);
 267                 expr_dump(expr->args[pet_un_arg], indent + 2);
 268                 break;
 269         case pet_expr_binary:
 270                 fprintf(stderr, "%s\n", op_str[expr->op]);
 271                 expr_dump(expr->args[pet_bin_lhs], indent + 2);
 272                 expr_dump(expr->args[pet_bin_rhs], indent + 2);
 273                 break;
 274         case pet_expr_ternary:
 275                 fprintf(stderr, "?:\n");
 276                 expr_dump(expr->args[pet_ter_cond], indent + 2);
 277                 expr_dump(expr->args[pet_ter_true], indent + 2);
 278                 expr_dump(expr->args[pet_ter_false], indent + 2);
 279                 break;
 280         case pet_expr_call:
 281                 fprintf(stderr, "%s/%d\n", expr->name, expr->n_arg);
 282                 for (i = 0; i < expr->n_arg; ++i)
 283                         expr_dump(expr->args[i], indent + 2);
 284                 break;
 285         }
 286 }
 287
 288 void pet_expr_dump(struct pet_expr *expr)
 289 {
 290         expr_dump(expr, 0);
 291 }
 292
 293 /* Return 1 if the two pet_exprs are equivalent.
 294  */
 295 int pet_expr_is_equal(struct pet_expr *expr1, struct pet_expr *expr2)
 296 {
 297         int i;
 298
 299         if (!expr1 || !expr2)
 300                 return 0;
 301
 302         if (expr1->type != expr2->type)
 303                 return 0;
 304         if (expr1->n_arg != expr2->n_arg)
 305                 return 0;
 306         for (i = 0; i < expr1->n_arg; ++i)
 307                 if (!pet_expr_is_equal(expr1->args[i], expr2->args[i]))
 308                         return 0;
 309         switch (expr1->type) {
 310         case pet_expr_double:
 311                 if (expr1->d != expr2->d)
 312                         return 0;
 313                 break;
 314         case pet_expr_access:
 315                 if (expr1->acc.read != expr2->acc.read)
 316                         return 0;
 317                 if (expr1->acc.write != expr2->acc.write)
 318                         return 0;
 319                 if (!isl_map_is_equal(expr1->acc.access, expr2->acc.access))
 320                         return 0;
 321                 break;
 322         case pet_expr_unary:
 323         case pet_expr_binary:
 324         case pet_expr_ternary:
 325                 if (expr1->op != expr2->op)
 326                         return 0;
 327                 break;
 328         case pet_expr_call:
 329                 if (strcmp(expr1->name, expr2->name))
 330                         return 0;
 331                 break;
 332         }
 333
 334         return 1;
 335 }
 336
 337 /* Add extra conditions on the parameters to all access relations in "expr".
 338  */
 339 struct pet_expr *pet_expr_restrict(struct pet_expr *expr,
 340         __isl_take isl_set *cond)
 341 {
 342         int i;
 343
 344         if (!expr)
 345                 goto error;
 346
 347         for (i = 0; i < expr->n_arg; ++i) {
 348                 expr->args[i] = pet_expr_restrict(expr->args[i],
 349                                                         isl_set_copy(cond));
 350                 if (!expr->args[i])
 351                         goto error;
 352         }
 353
 354         if (expr->type == pet_expr_access) {
 355                 expr->acc.access = isl_map_intersect_params(expr->acc.access,
 356                                                             isl_set_copy(cond));
 357                 if (!expr->acc.access)
 358                         goto error;
 359         }
 360
 361         isl_set_free(cond);
 362         return expr;
 363 error:
 364         isl_set_free(cond);
 365         return pet_expr_free(expr);
 366 }
 367
 368 /* Modify all access relations in "expr" by calling "fn" on them.
 369  */
 370 static struct pet_expr *expr_foreach_access(struct pet_expr *expr,
 371         __isl_give isl_map *(*fn)(__isl_take isl_map *access, void *user),
 372         void *user)
 373 {
 374         int i;
 375
 376         if (!expr)
 377                 return NULL;
 378
 379         for (i = 0; i < expr->n_arg; ++i) {
 380                 expr->args[i] = expr_foreach_access(expr->args[i], fn, user);
 381                 if (!expr->args[i])
 382                         return pet_expr_free(expr);
 383         }
 384
 385         if (expr->type == pet_expr_access) {
 386                 expr->acc.access = fn(expr->acc.access, user);
 387                 if (!expr->acc.access)
 388                         return pet_expr_free(expr);
 389         }
 390
 391         return expr;
 392 }
 393
 394 /* Modify the given access relation based on the given iteration space
 395  * transformation.
 396  * If the access has any arguments then the domain of the access relation
 397  * is a wrapped mapping from the iteration space to the space of
 398  * argument values.  We only need to change the domain of this wrapped
 399  * mapping, so we extend the input transformation with an identity mapping
 400  * on the space of argument values.
 401  */
 402 static __isl_give isl_map *update_domain(__isl_take isl_map *access,
 403         void *user)
 404 {
 405         isl_map *update = user;
 406         isl_dim *dim;
 407
 408         update = isl_map_copy(update);
 409
 410         dim = isl_map_get_dim(access);
 411         dim = isl_dim_domain(dim);
 412         if (!isl_dim_is_wrapping(dim))
 413                 isl_dim_free(dim);
 414         else {
 415                 isl_map *id;
 416                 dim = isl_dim_unwrap(dim);
 417                 dim = isl_dim_range(dim);
 418                 dim = isl_dim_map_from_set(dim);
 419                 id = isl_map_identity(dim);
 420                 update = isl_map_product(update, id);
 421         }
 422
 423         return isl_map_apply_domain(access, update);
 424 }
 425
 426 /* Modify all access relations in "expr" based on the given iteration space
 427  * transformation.
 428  */
 429 static struct pet_expr *expr_update_domain(struct pet_expr *expr,
 430         __isl_take isl_map *update)
 431 {
 432         expr = expr_foreach_access(expr, &update_domain, update);
 433         isl_map_free(update);
 434         return expr;
 435 }
 436
 437 /* Construct a pet_stmt with given line number and statement
 438  * number from a pet_expr.
 439  * The initial iteration domain is the zero-dimensional universe.
 440  * The domains of all access relations are modified to refer
 441  * to the statement iteration domain.
 442  */
 443 struct pet_stmt *pet_stmt_from_pet_expr(isl_ctx *ctx, int line, int id,
 444         struct pet_expr *expr)
 445 {
 446         struct pet_stmt *stmt;
 447         isl_dim *dim;
 448         isl_set *dom;
 449         isl_map *sched;
 450         isl_map *add_name;
 451         char name[50];
 452
 453         if (!expr)
 454                 return NULL;
 455
 456         stmt = isl_alloc_type(ctx, struct pet_stmt);
 457         if (!stmt)
 458                 return pet_expr_free(expr);
 459
 460         dim = isl_dim_set_alloc(ctx, 0, 0);
 461         snprintf(name, sizeof(name), "S_%d", id);
 462         dim = isl_dim_set_tuple_name(dim, isl_dim_set, name);
 463         dom = isl_set_universe(isl_dim_copy(dim));
 464         sched = isl_map_from_domain(isl_set_copy(dom));
 465
 466         dim = isl_dim_from_range(dim);
 467         add_name = isl_map_universe(dim);
 468         expr = expr_update_domain(expr, add_name);
 469
 470         stmt->line = line;
 471         stmt->domain = dom;
 472         stmt->schedule = sched;
 473         stmt->body = expr;
 474
 475         if (!stmt->domain || !stmt->schedule || !stmt->body)
 476                 return pet_stmt_free(stmt);
 477
 478         return stmt;
 479 }
 480
 481 void *pet_stmt_free(struct pet_stmt *stmt)
 482 {
 483         if (!stmt)
 484                 return NULL;
 485
 486         isl_set_free(stmt->domain);
 487         isl_map_free(stmt->schedule);
 488         pet_expr_free(stmt->body);
 489
 490         free(stmt);
 491         return NULL;
 492 }
 493
 494 static void stmt_dump(struct pet_stmt *stmt, int indent)
 495 {
 496         if (!stmt)
 497                 return;
 498
 499         fprintf(stderr, "%*s%d\n", indent, "", stmt->line);
 500         fprintf(stderr, "%*s", indent, "");
 501         isl_set_dump(stmt->domain);
 502         fprintf(stderr, "%*s", indent, "");
 503         isl_map_dump(stmt->schedule);
 504         expr_dump(stmt->body, indent);
 505 }
 506
 507 void pet_stmt_dump(struct pet_stmt *stmt)
 508 {
 509         stmt_dump(stmt, 0);
 510 }
 511
 512 void *pet_array_free(struct pet_array *array)
 513 {
 514         if (!array)
 515                 return NULL;
 516
 517         isl_set_free(array->context);
 518         isl_set_free(array->extent);
 519         isl_set_free(array->value_bounds);
 520         free(array->element_type);
 521
 522         free(array);
 523         return NULL;
 524 }
 525
 526 void pet_array_dump(struct pet_array *array)
 527 {
 528         if (!array)
 529                 return;
 530
 531         isl_set_dump(array->context);
 532         isl_set_dump(array->extent);
 533         isl_set_dump(array->value_bounds);
 534         fprintf(stderr, "%s %s\n", array->element_type,
 535                 array->live_out ? "live-out" : "");
 536 }
 537
 538 /* Construct a pet_scop with room for n statements.
 539  */
 540 static struct pet_scop *scop_alloc(isl_ctx *ctx, int n)
 541 {
 542         struct pet_scop *scop;
 543
 544         scop = isl_calloc_type(ctx, struct pet_scop);
 545         if (!scop)
 546                 return NULL;
 547
 548         scop->context = isl_set_universe(isl_dim_set_alloc(ctx, 0, 0));
 549         scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
 550         if (!scop->context || !scop->stmts)
 551                 return pet_scop_free(scop);
 552
 553         scop->n_stmt = n;
 554
 555         return scop;
 556 }
 557
 558 struct pet_scop *pet_scop_empty(isl_ctx *ctx)
 559 {
 560         return scop_alloc(ctx, 0);
 561 }
 562
 563 /* Construct a pet_scop that contains the given pet_stmt.
 564  */
 565 struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt)
 566 {
 567         struct pet_scop *scop;
 568
 569         if (!stmt)
 570                 return NULL;
 571
 572         scop = scop_alloc(ctx, 1);
 573
 574         scop->stmts[0] = stmt;
 575
 576         return scop;
 577 error:
 578         pet_stmt_free(stmt);
 579         pet_scop_free(scop);
 580         return NULL;
 581 }
 582
 583 /* Construct a pet_scop that contains the statements in "scop1" and "scop2".
 584  */
 585 struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
 586         struct pet_scop *scop2)
 587 {
 588         int i;
 589         struct pet_scop *scop;
 590
 591         if (!scop1 || !scop2)
 592                 goto error;
 593
 594         if (scop1->n_stmt == 0) {
 595                 pet_scop_free(scop1);
 596                 return scop2;
 597         }
 598
 599         if (scop2->n_stmt == 0) {
 600                 pet_scop_free(scop2);
 601                 return scop1;
 602         }
 603
 604         scop = scop_alloc(ctx, scop1->n_stmt + scop2->n_stmt);
 605         if (!scop)
 606                 goto error;
 607
 608         for (i = 0; i < scop1->n_stmt; ++i) {
 609                 scop->stmts[i] = scop1->stmts[i];
 610                 scop1->stmts[i] = NULL;
 611         }
 612
 613         for (i = 0; i < scop2->n_stmt; ++i) {
 614                 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
 615                 scop2->stmts[i] = NULL;
 616         }
 617
 618         pet_scop_free(scop1);
 619         pet_scop_free(scop2);
 620         return scop;
 621 error:
 622         pet_scop_free(scop1);
 623         pet_scop_free(scop2);
 624         return NULL;
 625 }
 626
 627 void *pet_scop_free(struct pet_scop *scop)
 628 {
 629         int i;
 630
 631         if (!scop)
 632                 return NULL;
 633         isl_set_free(scop->context);
 634         if (scop->arrays)
 635                 for (i = 0; i < scop->n_array; ++i)
 636                         pet_array_free(scop->arrays[i]);
 637         free(scop->arrays);
 638         if (scop->stmts)
 639                 for (i = 0; i < scop->n_stmt; ++i)
 640                         pet_stmt_free(scop->stmts[i]);
 641         free(scop->stmts);
 642         free(scop);
 643         return NULL;
 644 }
 645
 646 void pet_scop_dump(struct pet_scop *scop)
 647 {
 648         int i;
 649
 650         if (!scop)
 651                 return;
 652
 653         isl_set_dump(scop->context);
 654         for (i = 0; i < scop->n_array; ++i)
 655                 pet_array_dump(scop->arrays[i]);
 656         for (i = 0; i < scop->n_stmt; ++i)
 657                 pet_stmt_dump(scop->stmts[i]);
 658 }
 659
 660 /* Return 1 if the two pet_arrays are equivalent.
 661  */
 662 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
 663 {
 664         if (!array1 || !array2)
 665                 return 0;
 666
 667         if (!isl_set_is_equal(array1->context, array2->context))
 668                 return 0;
 669         if (!isl_set_is_equal(array1->extent, array2->extent))
 670                 return 0;
 671         if (!!array1->value_bounds != !!array2->value_bounds)
 672                 return 0;
 673         if (array1->value_bounds &&
 674             !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
 675                 return 0;
 676         if (strcmp(array1->element_type, array2->element_type))
 677                 return 0;
 678         if (array1->live_out != array2->live_out)
 679                 return 0;
 680
 681         return 1;
 682 }
 683
 684 /* Return 1 if the two pet_stmts are equivalent.
 685  */
 686 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
 687 {
 688         if (!stmt1 || !stmt2)
 689                 return 0;
 690
 691         if (stmt1->line != stmt2->line)
 692                 return 0;
 693         if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
 694                 return 0;
 695         if (!isl_map_is_equal(stmt1->schedule, stmt2->schedule))
 696                 return 0;
 697         if (!pet_expr_is_equal(stmt1->body, stmt2->body))
 698                 return 0;
 699
 700         return 1;
 701 }
 702
 703 /* Return 1 if the two pet_scops are equivalent.
 704  */
 705 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
 706 {
 707         int i;
 708
 709         if (!scop1 || !scop2)
 710                 return 0;
 711
 712         if (!isl_set_is_equal(scop1->context, scop2->context))
 713                 return 0;
 714
 715         if (scop1->n_array != scop2->n_array)
 716                 return 0;
 717         for (i = 0; i < scop1->n_array; ++i)
 718                 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
 719                         return 0;
 720
 721         if (scop1->n_stmt != scop2->n_stmt)
 722                 return 0;
 723         for (i = 0; i < scop1->n_stmt; ++i)
 724                 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
 725                         return 0;
 726
 727         return 1;
 728 }
 729
 730 /* Prefix the schedule of "stmt" with an extra dimension with constant
 731  * value "pos".
 732  */
 733 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos)
 734 {
 735         if (!stmt)
 736                 return NULL;
 737
 738         stmt->schedule = isl_map_insert_dims(stmt->schedule, isl_dim_out, 0, 1);
 739         stmt->schedule = isl_map_fix_si(stmt->schedule, isl_dim_out, 0, pos);
 740         if (!stmt->schedule)
 741                 return pet_stmt_free(stmt);
 742
 743         return stmt;
 744 }
 745
 746 /* Prefix the schedules of all statements in "scop" with an extra
 747  * dimension with constant value "pos".
 748  */
 749 struct pet_scop *pet_scop_prefix(struct pet_scop *scop, int pos)
 750 {
 751         int i;
 752
 753         if (!scop)
 754                 return NULL;
 755
 756         for (i = 0; i < scop->n_stmt; ++i) {
 757                 scop->stmts[i] = pet_stmt_prefix(scop->stmts[i], pos);
 758                 if (!scop->stmts[i])
 759                         return pet_scop_free(scop);
 760         }
 761
 762         return scop;
 763 }
 764
 765 /* Data used in embed_access.
 766  * extend adds an iterator to the iteration domain
 767  * var_id represents the induction variable of the corresponding loop
 768  */
 769 struct pet_embed_access {
 770         isl_map *extend;
 771         isl_id *var_id;
 772 };
 773
 774 /* Embed the access relation in an extra outer loop.
 775  *
 776  * We first update the iteration domain to insert the extra dimension.
 777  *
 778  * If the access refers to the induction variable, then it is
 779  * turned into an access to the set of integers with index (and value)
 780  * equal to the induction variable.
 781  *
 782  * If the induction variable appears in the constraints (as a parameter),
 783  * then the parameter is equated to the newly introduced iteration
 784  * domain dimension and subsequently projected out.
 785  */
 786 static __isl_give isl_map *embed_access(__isl_take isl_map *access,
 787         void *user)
 788 {
 789         struct pet_embed_access *data = user;
 790         isl_id *array_id = NULL;
 791         int pos;
 792
 793         access = update_domain(access, data->extend);
 794
 795         if (isl_map_has_tuple_id(access, isl_dim_out))
 796                 array_id = isl_map_get_tuple_id(access, isl_dim_out);
 797         if (array_id == data->var_id) {
 798                 access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
 799                 access = isl_map_equate(access,
 800                                         isl_dim_in, 0, isl_dim_out, 0);
 801         }
 802         isl_id_free(array_id);
 803
 804         pos = isl_map_find_dim_by_id(access, isl_dim_param, data->var_id);
 805         if (pos >= 0) {
 806                 access = isl_map_equate(access,
 807                                         isl_dim_param, pos, isl_dim_in, 0);
 808                 access = isl_map_project_out(access, isl_dim_param, pos, 1);
 809         }
 810         access = isl_map_set_dim_id(access, isl_dim_in, 0,
 811                                         isl_id_copy(data->var_id));
 812
 813         return access;
 814 }
 815
 816 /* Embed all access relations in "expr" in an extra loop.
 817  * "extend" inserts an outer loop iterator in the iteration domains.
 818  * "var_id" represents the induction variable.
 819  */
 820 static struct pet_expr *expr_embed(struct pet_expr *expr,
 821         __isl_take isl_map *extend, __isl_keep isl_id *var_id)
 822 {
 823         struct pet_embed_access data = { .extend = extend, .var_id = var_id };
 824
 825         expr = expr_foreach_access(expr, &embed_access, &data);
 826         isl_map_free(extend);
 827         return expr;
 828 }
 829
 830 /* Embed the given pet_stmt in an extra outer loop with iteration domain
 831  * "dom" and schedule "sched".  "var_id" represents the induction variable
 832  * of the loop.
 833  *
 834  * The iteration domain and schedule of the statement are updated
 835  * according to the iteration domain and schedule of the new loop.
 836  *
 837  * If the induction variable appears in the constraints (as a parameter)
 838  * of the current iteration domain or the schedule of the statement,
 839  * then the parameter is equated to the newly introduced iteration
 840  * domain dimension and subsequently projected out.
 841  *
 842  * Finally, all access relations are updated based on the extra loop.
 843  */
 844 struct pet_stmt *pet_stmt_embed(struct pet_stmt *stmt, __isl_take isl_set *dom,
 845         __isl_take isl_map *sched, __isl_take isl_id *var_id)
 846 {
 847         int pos;
 848         isl_id *stmt_id;
 849         isl_dim *dim;
 850         isl_map *extend;
 851
 852         stmt_id = isl_set_get_tuple_id(stmt->domain);
 853         stmt->domain = isl_set_flat_product(isl_set_copy(dom), stmt->domain);
 854         stmt->domain = isl_set_set_tuple_id(stmt->domain, isl_id_copy(stmt_id));
 855
 856         pos = isl_set_find_dim_by_id(stmt->domain, isl_dim_param, var_id);
 857         if (pos >= 0) {
 858                 stmt->domain = isl_set_equate(stmt->domain,
 859                                             isl_dim_param, pos, isl_dim_set, 0);
 860                 stmt->domain = isl_set_project_out(stmt->domain,
 861                                                     isl_dim_param, pos, 1);
 862         }
 863
 864         stmt->schedule = isl_map_flat_product(sched, stmt->schedule);
 865         stmt->schedule = isl_map_set_tuple_id(stmt->schedule,
 866                                                 isl_dim_in, stmt_id);
 867
 868         pos = isl_map_find_dim_by_id(stmt->schedule, isl_dim_param, var_id);
 869         if (pos >= 0) {
 870                 stmt->schedule = isl_map_equate(stmt->schedule,
 871                                             isl_dim_param, pos, isl_dim_in, 0);
 872                 stmt->schedule = isl_map_project_out(stmt->schedule,
 873                                                     isl_dim_param, pos, 1);
 874         }
 875
 876         dim = isl_dim_map_from_set(isl_set_get_dim(stmt->domain));
 877         extend = isl_map_identity(dim);
 878         extend = isl_map_remove_dims(extend, isl_dim_in, 0, 1);
 879         extend = isl_map_set_tuple_id(extend, isl_dim_in,
 880                                     isl_map_get_tuple_id(extend, isl_dim_out));
 881         stmt->body = expr_embed(stmt->body, extend, var_id);
 882
 883         isl_set_free(dom);
 884         isl_id_free(var_id);
 885
 886         if (!stmt->domain || !stmt->schedule || !stmt->body)
 887                 return pet_stmt_free(stmt);
 888         return stmt;
 889 }
 890
 891 /* Embed all statements in "scop" in an extra outer loop with iteration domain
 892  * "dom" and schedule "sched".  "var_id" represents the induction variable
 893  * of the loop.
 894  */
 895 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
 896         __isl_take isl_map *sched, __isl_take isl_id *id)
 897 {
 898         int i;
 899
 900         if (!scop)
 901                 goto error;
 902
 903         for (i = 0; i < scop->n_stmt; ++i) {
 904                 scop->stmts[i] = pet_stmt_embed(scop->stmts[i],
 905                                         isl_set_copy(dom),
 906                                         isl_map_copy(sched), isl_id_copy(id));
 907                 if (!scop->stmts[i])
 908                         goto error;
 909         }
 910
 911         isl_set_free(dom);
 912         isl_map_free(sched);
 913         isl_id_free(id);
 914         return scop;
 915 error:
 916         isl_set_free(dom);
 917         isl_map_free(sched);
 918         isl_id_free(id);
 919         return pet_scop_free(scop);
 920 }
 921
 922 /* Add extra conditions on the parameters to iteration domain of "stmt".
 923  */
 924 static struct pet_stmt *stmt_restrict(struct pet_stmt *stmt,
 925         __isl_take isl_set *cond)
 926 {
 927         if (!stmt)
 928                 goto error;
 929
 930         stmt->domain = isl_set_intersect_params(stmt->domain, cond);
 931
 932         return stmt;
 933 error:
 934         isl_set_free(cond);
 935         return pet_stmt_free(stmt);
 936 }
 937
 938 /* Add extra conditions on the parameters to all iteration domains.
 939  */
 940 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
 941         __isl_take isl_set *cond)
 942 {
 943         int i;
 944
 945         if (!scop)
 946                 goto error;
 947
 948         for (i = 0; i < scop->n_stmt; ++i) {
 949                 scop->stmts[i] = stmt_restrict(scop->stmts[i],
 950                                                     isl_set_copy(cond));
 951                 if (!scop->stmts[i])
 952                         goto error;
 953         }
 954
 955         isl_set_free(cond);
 956         return scop;
 957 error:
 958         isl_set_free(cond);
 959         return pet_scop_free(scop);
 960 }
 961
 962 /* Add all parameters in "expr" to "dim" and return the result.
 963  */
 964 static __isl_give isl_dim *expr_collect_params(struct pet_expr *expr,
 965         __isl_take isl_dim *dim)
 966 {
 967         int i;
 968
 969         if (!expr)
 970                 goto error;
 971         for (i = 0; i < expr->n_arg; ++i)
 972
 973                 dim = expr_collect_params(expr->args[i], dim);
 974
 975         if (expr->type == pet_expr_access)
 976                 dim = isl_dim_align_params(dim,
 977                                             isl_map_get_dim(expr->acc.access));
 978
 979         return dim;
 980 error:
 981         isl_dim_free(dim);
 982         return pet_expr_free(expr);
 983 }
 984
 985 /* Add all parameters in "stmt" to "dim" and return the result.
 986  */
 987 static __isl_give isl_dim *stmt_collect_params(struct pet_stmt *stmt,
 988         __isl_take isl_dim *dim)
 989 {
 990         if (!stmt)
 991                 goto error;
 992
 993         dim = isl_dim_align_params(dim, isl_set_get_dim(stmt->domain));
 994         dim = isl_dim_align_params(dim, isl_map_get_dim(stmt->schedule));
 995         dim = expr_collect_params(stmt->body, dim);
 996
 997         return dim;
 998 error:
 999         isl_dim_free(dim);
1000         return pet_stmt_free(stmt);
1001 }
1002
1003 /* Add all parameters in "array" to "dim" and return the result.
1004  */
1005 static __isl_give isl_dim *array_collect_params(struct pet_array *array,
1006         __isl_take isl_dim *dim)
1007 {
1008         if (!array)
1009                 goto error;
1010
1011         dim = isl_dim_align_params(dim, isl_set_get_dim(array->context));
1012         dim = isl_dim_align_params(dim, isl_set_get_dim(array->extent));
1013
1014         return dim;
1015 error:
1016         isl_dim_free(dim);
1017         return pet_array_free(array);
1018 }
1019
1020 /* Add all parameters in "scop" to "dim" and return the result.
1021  */
1022 static __isl_give isl_dim *scop_collect_params(struct pet_scop *scop,
1023         __isl_take isl_dim *dim)
1024 {
1025         int i;
1026
1027         if (!scop)
1028                 goto error;
1029
1030         for (i = 0; i < scop->n_array; ++i)
1031                 dim = array_collect_params(scop->arrays[i], dim);
1032
1033         for (i = 0; i < scop->n_stmt; ++i)
1034                 dim = stmt_collect_params(scop->stmts[i], dim);
1035
1036         return dim;
1037 error:
1038         isl_dim_free(dim);
1039         return pet_scop_free(scop);
1040 }
1041
1042 /* Add all parameters in "dim" to all access relations in "expr".
1043  */
1044 static struct pet_expr *expr_propagate_params(struct pet_expr *expr,
1045         __isl_take isl_dim *dim)
1046 {
1047         int i;
1048
1049         if (!expr)
1050                 goto error;
1051
1052         for (i = 0; i < expr->n_arg; ++i) {
1053                 expr->args[i] =
1054                         expr_propagate_params(expr->args[i],
1055                                                 isl_dim_copy(dim));
1056                 if (!expr->args[i])
1057                         goto error;
1058         }
1059
1060         if (expr->type == pet_expr_access) {
1061                 expr->acc.access = isl_map_align_params(expr->acc.access,
1062                                                         isl_dim_copy(dim));
1063                 if (!expr->acc.access)
1064                         goto error;
1065         }
1066
1067         isl_dim_free(dim);
1068         return expr;
1069 error:
1070         isl_dim_free(dim);
1071         return pet_expr_free(expr);
1072 }
1073
1074 /* Add all parameters in "dim" to the domain, schedule and
1075  * all access relations in "stmt".
1076  */
1077 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
1078         __isl_take isl_dim *dim)
1079 {
1080         if (!stmt)
1081                 goto error;
1082
1083         stmt->domain = isl_set_align_params(stmt->domain, isl_dim_copy(dim));
1084         stmt->schedule = isl_map_align_params(stmt->schedule,
1085                                                 isl_dim_copy(dim));
1086         stmt->body = expr_propagate_params(stmt->body, isl_dim_copy(dim));
1087
1088         if (!stmt->domain || !stmt->schedule || !stmt->body)
1089                 goto error;
1090
1091         isl_dim_free(dim);
1092         return stmt;
1093 error:
1094         isl_dim_free(dim);
1095         return pet_stmt_free(stmt);
1096 }
1097
1098 /* Add all parameters in "dim" to "array".
1099  */
1100 static struct pet_array *array_propagate_params(struct pet_array *array,
1101         __isl_take isl_dim *dim)
1102 {
1103         if (!array)
1104                 goto error;
1105
1106         array->context = isl_set_align_params(array->context,
1107                                                 isl_dim_copy(dim));
1108         array->extent = isl_set_align_params(array->extent,
1109                                                 isl_dim_copy(dim));
1110         if (array->value_bounds) {
1111                 array->value_bounds = isl_set_align_params(array->value_bounds,
1112                                                         isl_dim_copy(dim));
1113                 if (!array->value_bounds)
1114                         goto error;
1115         }
1116
1117         if (!array->context || !array->extent)
1118                 goto error;
1119
1120         isl_dim_free(dim);
1121         return array;
1122 error:
1123         isl_dim_free(dim);
1124         return pet_array_free(array);
1125 }
1126
1127 /* Add all parameters in "dim" to "scop".
1128  */
1129 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
1130         __isl_take isl_dim *dim)
1131 {
1132         int i;
1133
1134         if (!scop)
1135                 goto error;
1136
1137         for (i = 0; i < scop->n_array; ++i) {
1138                 scop->arrays[i] = array_propagate_params(scop->arrays[i],
1139                                                         isl_dim_copy(dim));
1140                 if (!scop->arrays[i])
1141                         goto error;
1142         }
1143
1144         for (i = 0; i < scop->n_stmt; ++i) {
1145                 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
1146                                                         isl_dim_copy(dim));
1147                 if (!scop->stmts[i])
1148                         goto error;
1149         }
1150
1151         isl_dim_free(dim);
1152         return scop;
1153 error:
1154         isl_dim_free(dim);
1155         return pet_scop_free(scop);
1156 }
1157
1158 /* Update all isl_sets and isl_maps in "scop" such that they all
1159  * have the same parameters.
1160  */
1161 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
1162 {
1163         isl_dim *dim;
1164
1165         if (!scop)
1166                 return NULL;
1167
1168         dim = isl_set_get_dim(scop->context);
1169         dim = scop_collect_params(scop, dim);
1170
1171         scop->context = isl_set_align_params(scop->context, isl_dim_copy(dim));
1172         scop = scop_propagate_params(scop, dim);
1173
1174         return scop;
1175 }
1176
1177 /* Check if the given access relation accesses a (0D) array that corresponds
1178  * to one of the parameters in "dim".  If so, replace the array access
1179  * by an access to the set of integers with as index (and value)
1180  * that parameter.
1181  */
1182 static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
1183         __isl_take isl_dim *dim)
1184 {
1185         isl_id *array_id = NULL;
1186         int pos = -1;
1187
1188         if (isl_map_has_tuple_id(access, isl_dim_out)) {
1189                 array_id = isl_map_get_tuple_id(access, isl_dim_out);
1190                 pos = isl_dim_find_dim_by_id(dim, isl_dim_param, array_id);
1191         }
1192         isl_dim_free(dim);
1193
1194         if (pos < 0) {
1195                 isl_id_free(array_id);
1196                 return access;
1197         }
1198
1199         pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
1200         if (pos < 0) {
1201                 access = isl_map_insert_dims(access, isl_dim_param, 0, 1);
1202                 access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
1203                 pos = 0;
1204         } else
1205                 isl_id_free(array_id);
1206
1207         access = isl_map_insert_dims(access, isl_dim_out, 0, 1);
1208         access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
1209
1210         return access;
1211 }
1212
1213 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1214  * in "dim" by a value equal to the corresponding parameter.
1215  */
1216 static struct pet_expr *expr_detect_parameter_accesses(struct pet_expr *expr,
1217         __isl_take isl_dim *dim)
1218 {
1219         int i;
1220
1221         if (!expr)
1222                 goto error;
1223
1224         for (i = 0; i < expr->n_arg; ++i) {
1225                 expr->args[i] =
1226                         expr_detect_parameter_accesses(expr->args[i],
1227                                                 isl_dim_copy(dim));
1228                 if (!expr->args[i])
1229                         goto error;
1230         }
1231
1232         if (expr->type == pet_expr_access) {
1233                 expr->acc.access = access_detect_parameter(expr->acc.access,
1234                                                         isl_dim_copy(dim));
1235                 if (!expr->acc.access)
1236                         goto error;
1237         }
1238
1239         isl_dim_free(dim);
1240         return expr;
1241 error:
1242         isl_dim_free(dim);
1243         return pet_expr_free(expr);
1244 }
1245
1246 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1247  * in "dim" by a value equal to the corresponding parameter.
1248  */
1249 static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
1250         __isl_take isl_dim *dim)
1251 {
1252         if (!stmt)
1253                 goto error;
1254
1255         stmt->body = expr_detect_parameter_accesses(stmt->body,
1256                                                         isl_dim_copy(dim));
1257
1258         if (!stmt->domain || !stmt->schedule || !stmt->body)
1259                 goto error;
1260
1261         isl_dim_free(dim);
1262         return stmt;
1263 error:
1264         isl_dim_free(dim);
1265         return pet_stmt_free(stmt);
1266 }
1267
1268 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1269  * in "dim" by a value equal to the corresponding parameter.
1270  */
1271 static struct pet_scop *scop_detect_parameter_accesses(struct pet_scop *scop,
1272         __isl_take isl_dim *dim)
1273 {
1274         int i;
1275
1276         if (!scop)
1277                 goto error;
1278
1279         for (i = 0; i < scop->n_stmt; ++i) {
1280                 scop->stmts[i] = stmt_detect_parameter_accesses(scop->stmts[i],
1281                                                         isl_dim_copy(dim));
1282                 if (!scop->stmts[i])
1283                         goto error;
1284         }
1285
1286         isl_dim_free(dim);
1287         return scop;
1288 error:
1289         isl_dim_free(dim);
1290         return pet_scop_free(scop);
1291 }
1292
1293 /* Replace all accesses to (0D) arrays that correspond to any of
1294  * the parameters used in "scop" by a value equal
1295  * to the corresponding parameter.
1296  */
1297 struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
1298 {
1299         isl_dim *dim;
1300
1301         if (!scop)
1302                 return NULL;
1303
1304         dim = isl_set_get_dim(scop->context);
1305         dim = scop_collect_params(scop, dim);
1306
1307         scop = scop_detect_parameter_accesses(scop, dim);
1308
1309         return scop;
1310 }
1311
1312 /* Add all read access relations (if "read" is set) and/or all write
1313  * access relations (if "write" is set) to "accesses" and return the result.
1314  */
1315 static __isl_give isl_union_map *expr_collect_accesses(struct pet_expr *expr,
1316         int read, int write, __isl_take isl_union_map *accesses)
1317 {
1318         int i;
1319         isl_id *id;
1320         isl_dim *dim;
1321
1322         if (!expr)
1323                 return NULL;
1324
1325         for (i = 0; i < expr->n_arg; ++i)
1326                 accesses = expr_collect_accesses(expr->args[i],
1327                                                  read, write, accesses);
1328
1329         if (expr->type == pet_expr_access) {
1330                 id = isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
1331                 if (id &&
1332                     ((read && expr->acc.read) || (write && expr->acc.write)))
1333                         accesses = isl_union_map_add_map(accesses,
1334                                                 isl_map_copy(expr->acc.access));
1335                 isl_id_free(id);
1336         }
1337
1338         return accesses;
1339 }
1340
1341 /* Collect and return all read access relations (if "read" is set)
1342  * and/or all write * access relations (if "write" is set) in "stmt".
1343  */
1344 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
1345         int read, int write, __isl_take isl_dim *dim)
1346 {
1347         isl_union_map *accesses;
1348
1349         if (!stmt)
1350                 return NULL;
1351
1352         accesses = isl_union_map_empty(dim);
1353         accesses = expr_collect_accesses(stmt->body, read, write, accesses);
1354         accesses = isl_union_map_intersect_domain(accesses,
1355                         isl_union_set_from_set(isl_set_copy(stmt->domain)));
1356
1357         return accesses;
1358 }
1359
1360 /* Collect and return all read access relations (if "read" is set)
1361  * and/or all write * access relations (if "write" is set) in "scop".
1362  */
1363 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
1364         int read, int write)
1365 {
1366         int i;
1367         isl_union_map *accesses;
1368
1369         if (!scop)
1370                 return NULL;
1371
1372         accesses = isl_union_map_empty(isl_set_get_dim(scop->context));
1373
1374         for (i = 0; i < scop->n_stmt; ++i) {
1375                 isl_union_map *accesses_i;
1376                 isl_dim *dim = isl_set_get_dim(scop->context);
1377                 accesses_i = stmt_collect_accesses(scop->stmts[i],
1378                                                    read, write, dim);
1379                 accesses = isl_union_map_union(accesses, accesses_i);
1380         }
1381
1382         return accesses;
1383 }
1384
1385 __isl_give isl_union_map *pet_scop_collect_reads(struct pet_scop *scop)
1386 {
1387         return scop_collect_accesses(scop, 1, 0);
1388 }
1389
1390 __isl_give isl_union_map *pet_scop_collect_writes(struct pet_scop *scop)
1391 {
1392         return scop_collect_accesses(scop, 0, 1);
1393 }
1394
1395 /* Collect and return the union of iteration domains in "scop".
1396  */
1397 __isl_give isl_union_set *pet_scop_collect_domains(struct pet_scop *scop)
1398 {
1399         int i;
1400         isl_set *domain_i;
1401         isl_union_set *domain;
1402
1403         if (!scop)
1404                 return NULL;
1405
1406         domain = isl_union_set_empty(isl_set_get_dim(scop->context));
1407
1408         for (i = 0; i < scop->n_stmt; ++i) {
1409                 domain_i = isl_set_copy(scop->stmts[i]->domain);
1410                 domain = isl_union_set_add_set(domain, domain_i);
1411         }
1412
1413         return domain;
1414 }
1415
1416 /* Collect and return the schedules of the statements in "scop".
1417  * The range is normalized to the maximal number of scheduling
1418  * dimensions.
1419  */
1420 __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
1421 {
1422         int i, j;
1423         isl_map *schedule_i;
1424         isl_union_map *schedule;
1425         int depth, max_depth = 0;
1426
1427         if (!scop)
1428                 return NULL;
1429
1430         schedule = isl_union_map_empty(isl_set_get_dim(scop->context));
1431
1432         for (i = 0; i < scop->n_stmt; ++i) {
1433                 depth = isl_map_dim(scop->stmts[i]->schedule, isl_dim_out);
1434                 if (depth > max_depth)
1435                         max_depth = depth;
1436         }
1437
1438         for (i = 0; i < scop->n_stmt; ++i) {
1439                 schedule_i = isl_map_copy(scop->stmts[i]->schedule);
1440                 depth = isl_map_dim(schedule_i, isl_dim_out);
1441                 schedule_i = isl_map_add_dims(schedule_i, isl_dim_out,
1442                                                 max_depth - depth);
1443                 for (j = depth; j < max_depth; ++j)
1444                         schedule_i = isl_map_fix_si(schedule_i,
1445                                                         isl_dim_out, j, 0);
1446                 schedule = isl_union_map_add_map(schedule, schedule_i);
1447         }
1448
1449         return schedule;
1450 }