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\n", array->element_type);
 535 }
 536
 537 /* Construct a pet_scop with room for n statements.
 538  */
 539 static struct pet_scop *scop_alloc(isl_ctx *ctx, int n)
 540 {
 541         struct pet_scop *scop;
 542
 543         scop = isl_calloc_type(ctx, struct pet_scop);
 544         if (!scop)
 545                 return NULL;
 546
 547         scop->context = isl_set_universe(isl_dim_set_alloc(ctx, 0, 0));
 548         scop->stmts = isl_calloc_array(ctx, struct pet_stmt *, n);
 549         if (!scop->context || !scop->stmts)
 550                 return pet_scop_free(scop);
 551
 552         scop->n_stmt = n;
 553
 554         return scop;
 555 }
 556
 557 struct pet_scop *pet_scop_empty(isl_ctx *ctx)
 558 {
 559         return scop_alloc(ctx, 0);
 560 }
 561
 562 /* Construct a pet_scop that contains the given pet_stmt.
 563  */
 564 struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt)
 565 {
 566         struct pet_scop *scop;
 567
 568         if (!stmt)
 569                 return NULL;
 570
 571         scop = scop_alloc(ctx, 1);
 572
 573         scop->stmts[0] = stmt;
 574
 575         return scop;
 576 error:
 577         pet_stmt_free(stmt);
 578         pet_scop_free(scop);
 579         return NULL;
 580 }
 581
 582 /* Construct a pet_scop that contains the statements in "scop1" and "scop2".
 583  */
 584 struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1,
 585         struct pet_scop *scop2)
 586 {
 587         int i;
 588         struct pet_scop *scop;
 589
 590         if (!scop1 || !scop2)
 591                 goto error;
 592
 593         if (scop1->n_stmt == 0) {
 594                 pet_scop_free(scop1);
 595                 return scop2;
 596         }
 597
 598         if (scop2->n_stmt == 0) {
 599                 pet_scop_free(scop2);
 600                 return scop1;
 601         }
 602
 603         scop = scop_alloc(ctx, scop1->n_stmt + scop2->n_stmt);
 604         if (!scop)
 605                 goto error;
 606
 607         for (i = 0; i < scop1->n_stmt; ++i) {
 608                 scop->stmts[i] = scop1->stmts[i];
 609                 scop1->stmts[i] = NULL;
 610         }
 611
 612         for (i = 0; i < scop2->n_stmt; ++i) {
 613                 scop->stmts[scop1->n_stmt + i] = scop2->stmts[i];
 614                 scop2->stmts[i] = NULL;
 615         }
 616
 617         pet_scop_free(scop1);
 618         pet_scop_free(scop2);
 619         return scop;
 620 error:
 621         pet_scop_free(scop1);
 622         pet_scop_free(scop2);
 623         return NULL;
 624 }
 625
 626 void *pet_scop_free(struct pet_scop *scop)
 627 {
 628         int i;
 629
 630         if (!scop)
 631                 return NULL;
 632         isl_set_free(scop->context);
 633         if (scop->arrays)
 634                 for (i = 0; i < scop->n_array; ++i)
 635                         pet_array_free(scop->arrays[i]);
 636         free(scop->arrays);
 637         if (scop->stmts)
 638                 for (i = 0; i < scop->n_stmt; ++i)
 639                         pet_stmt_free(scop->stmts[i]);
 640         free(scop->stmts);
 641         free(scop);
 642         return NULL;
 643 }
 644
 645 void pet_scop_dump(struct pet_scop *scop)
 646 {
 647         int i;
 648
 649         if (!scop)
 650                 return;
 651
 652         isl_set_dump(scop->context);
 653         for (i = 0; i < scop->n_array; ++i)
 654                 pet_array_dump(scop->arrays[i]);
 655         for (i = 0; i < scop->n_stmt; ++i)
 656                 pet_stmt_dump(scop->stmts[i]);
 657 }
 658
 659 /* Return 1 if the two pet_arrays are equivalent.
 660  */
 661 int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2)
 662 {
 663         if (!array1 || !array2)
 664                 return 0;
 665
 666         if (!isl_set_is_equal(array1->context, array2->context))
 667                 return 0;
 668         if (!isl_set_is_equal(array1->extent, array2->extent))
 669                 return 0;
 670         if (!!array1->value_bounds != !!array2->value_bounds)
 671                 return 0;
 672         if (array1->value_bounds &&
 673             !isl_set_is_equal(array1->value_bounds, array2->value_bounds))
 674                 return 0;
 675         if (strcmp(array1->element_type, array2->element_type))
 676                 return 0;
 677
 678         return 1;
 679 }
 680
 681 /* Return 1 if the two pet_stmts are equivalent.
 682  */
 683 int pet_stmt_is_equal(struct pet_stmt *stmt1, struct pet_stmt *stmt2)
 684 {
 685         if (!stmt1 || !stmt2)
 686                 return 0;
 687
 688         if (stmt1->line != stmt2->line)
 689                 return 0;
 690         if (!isl_set_is_equal(stmt1->domain, stmt2->domain))
 691                 return 0;
 692         if (!isl_map_is_equal(stmt1->schedule, stmt2->schedule))
 693                 return 0;
 694         if (!pet_expr_is_equal(stmt1->body, stmt2->body))
 695                 return 0;
 696
 697         return 1;
 698 }
 699
 700 /* Return 1 if the two pet_scops are equivalent.
 701  */
 702 int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2)
 703 {
 704         int i;
 705
 706         if (!scop1 || !scop2)
 707                 return 0;
 708
 709         if (!isl_set_is_equal(scop1->context, scop2->context))
 710                 return 0;
 711
 712         if (scop1->n_array != scop2->n_array)
 713                 return 0;
 714         for (i = 0; i < scop1->n_array; ++i)
 715                 if (!pet_array_is_equal(scop1->arrays[i], scop2->arrays[i]))
 716                         return 0;
 717
 718         if (scop1->n_stmt != scop2->n_stmt)
 719                 return 0;
 720         for (i = 0; i < scop1->n_stmt; ++i)
 721                 if (!pet_stmt_is_equal(scop1->stmts[i], scop2->stmts[i]))
 722                         return 0;
 723
 724         return 1;
 725 }
 726
 727 /* Prefix the schedule of "stmt" with an extra dimension with constant
 728  * value "pos".
 729  */
 730 struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos)
 731 {
 732         if (!stmt)
 733                 return NULL;
 734
 735         stmt->schedule = isl_map_insert(stmt->schedule, isl_dim_out, 0, 1);
 736         stmt->schedule = isl_map_fix_si(stmt->schedule, isl_dim_out, 0, pos);
 737         if (!stmt->schedule)
 738                 return pet_stmt_free(stmt);
 739
 740         return stmt;
 741 }
 742
 743 /* Prefix the schedules of all statements in "scop" with an extra
 744  * dimension with constant value "pos".
 745  */
 746 struct pet_scop *pet_scop_prefix(struct pet_scop *scop, int pos)
 747 {
 748         int i;
 749
 750         if (!scop)
 751                 return NULL;
 752
 753         for (i = 0; i < scop->n_stmt; ++i) {
 754                 scop->stmts[i] = pet_stmt_prefix(scop->stmts[i], pos);
 755                 if (!scop->stmts[i])
 756                         return pet_scop_free(scop);
 757         }
 758
 759         return scop;
 760 }
 761
 762 /* Data used in embed_access.
 763  * extend adds an iterator to the iteration domain
 764  * var_id represents the induction variable of the corresponding loop
 765  */
 766 struct pet_embed_access {
 767         isl_map *extend;
 768         isl_id *var_id;
 769 };
 770
 771 /* Embed the access relation in an extra outer loop.
 772  *
 773  * We first update the iteration domain to insert the extra dimension.
 774  *
 775  * If the access refers to the induction variable, then it is
 776  * turned into an access to the set of integers with index (and value)
 777  * equal to the induction variable.
 778  *
 779  * If the induction variable appears in the constraints (as a parameter),
 780  * then the parameter is equated to the newly introduced iteration
 781  * domain dimension and subsequently projected out.
 782  */
 783 static __isl_give isl_map *embed_access(__isl_take isl_map *access,
 784         void *user)
 785 {
 786         struct pet_embed_access *data = user;
 787         isl_id *array_id;
 788         int pos;
 789
 790         access = update_domain(access, data->extend);
 791
 792         array_id = isl_map_get_tuple_id(access, isl_dim_out);
 793         if (array_id == data->var_id) {
 794                 access = isl_map_insert(access, isl_dim_out, 0, 1);
 795                 access = isl_map_equate(access,
 796                                         isl_dim_in, 0, isl_dim_out, 0);
 797         }
 798         isl_id_free(array_id);
 799
 800         pos = isl_map_find_dim_by_id(access, isl_dim_param, data->var_id);
 801         if (pos >= 0) {
 802                 access = isl_map_equate(access,
 803                                         isl_dim_param, pos, isl_dim_in, 0);
 804                 access = isl_map_project_out(access, isl_dim_param, pos, 1);
 805         }
 806         access = isl_map_set_dim_id(access, isl_dim_in, 0,
 807                                         isl_id_copy(data->var_id));
 808
 809         return access;
 810 }
 811
 812 /* Embed all access relations in "expr" in an extra loop.
 813  * "extend" inserts an outer loop iterator in the iteration domains.
 814  * "var_id" represents the induction variable.
 815  */
 816 static struct pet_expr *expr_embed(struct pet_expr *expr,
 817         __isl_take isl_map *extend, __isl_keep isl_id *var_id)
 818 {
 819         struct pet_embed_access data = { .extend = extend, .var_id = var_id };
 820
 821         expr = expr_foreach_access(expr, &embed_access, &data);
 822         isl_map_free(extend);
 823         return expr;
 824 }
 825
 826 /* Embed the given pet_stmt in an extra outer loop with iteration domain
 827  * "dom" and schedule "sched".  "var_id" represents the induction variable
 828  * of the loop.
 829  *
 830  * The iteration domain and schedule of the statement are updated
 831  * according to the iteration domain and schedule of the new loop.
 832  *
 833  * If the induction variable appears in the constraints (as a parameter)
 834  * of the current iteration domain or the schedule of the statement,
 835  * then the parameter is equated to the newly introduced iteration
 836  * domain dimension and subsequently projected out.
 837  *
 838  * Finally, all access relations are updated based on the extra loop.
 839  */
 840 struct pet_stmt *pet_stmt_embed(struct pet_stmt *stmt, __isl_take isl_set *dom,
 841         __isl_take isl_map *sched, __isl_take isl_id *var_id)
 842 {
 843         int pos;
 844         isl_id *stmt_id;
 845         isl_dim *dim;
 846         isl_map *extend;
 847
 848         stmt_id = isl_set_get_tuple_id(stmt->domain);
 849         stmt->domain = isl_set_flat_product(isl_set_copy(dom), stmt->domain);
 850         stmt->domain = isl_set_set_tuple_id(stmt->domain, isl_id_copy(stmt_id));
 851
 852         pos = isl_set_find_dim_by_id(stmt->domain, isl_dim_param, var_id);
 853         if (pos >= 0) {
 854                 stmt->domain = isl_set_equate(stmt->domain,
 855                                             isl_dim_param, pos, isl_dim_set, 0);
 856                 stmt->domain = isl_set_project_out(stmt->domain,
 857                                                     isl_dim_param, pos, 1);
 858         }
 859
 860         stmt->schedule = isl_map_flat_product(sched, stmt->schedule);
 861         stmt->schedule = isl_map_set_tuple_id(stmt->schedule,
 862                                                 isl_dim_in, stmt_id);
 863
 864         pos = isl_map_find_dim_by_id(stmt->schedule, isl_dim_param, var_id);
 865         if (pos >= 0) {
 866                 stmt->schedule = isl_map_equate(stmt->schedule,
 867                                             isl_dim_param, pos, isl_dim_in, 0);
 868                 stmt->schedule = isl_map_project_out(stmt->schedule,
 869                                                     isl_dim_param, pos, 1);
 870         }
 871
 872         dim = isl_dim_map_from_set(isl_set_get_dim(stmt->domain));
 873         extend = isl_map_identity(dim);
 874         extend = isl_map_remove_dims(extend, isl_dim_in, 0, 1);
 875         extend = isl_map_set_tuple_id(extend, isl_dim_in,
 876                                     isl_map_get_tuple_id(extend, isl_dim_out));
 877         stmt->body = expr_embed(stmt->body, extend, var_id);
 878
 879         isl_set_free(dom);
 880         isl_id_free(var_id);
 881
 882         if (!stmt->domain || !stmt->schedule || !stmt->body)
 883                 return pet_stmt_free(stmt);
 884         return stmt;
 885 }
 886
 887 /* Embed all statements in "scop" in an extra outer loop with iteration domain
 888  * "dom" and schedule "sched".  "var_id" represents the induction variable
 889  * of the loop.
 890  */
 891 struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom,
 892         __isl_take isl_map *sched, __isl_take isl_id *id)
 893 {
 894         int i;
 895
 896         if (!scop)
 897                 goto error;
 898
 899         for (i = 0; i < scop->n_stmt; ++i) {
 900                 scop->stmts[i] = pet_stmt_embed(scop->stmts[i],
 901                                         isl_set_copy(dom),
 902                                         isl_map_copy(sched), isl_id_copy(id));
 903                 if (!scop->stmts[i])
 904                         goto error;
 905         }
 906
 907         isl_set_free(dom);
 908         isl_map_free(sched);
 909         isl_id_free(id);
 910         return scop;
 911 error:
 912         isl_set_free(dom);
 913         isl_map_free(sched);
 914         isl_id_free(id);
 915         return pet_scop_free(scop);
 916 }
 917
 918 /* Add extra conditions on the parameters to iteration domain of "stmt".
 919  */
 920 static struct pet_stmt *stmt_restrict(struct pet_stmt *stmt,
 921         __isl_take isl_set *cond)
 922 {
 923         if (!stmt)
 924                 goto error;
 925
 926         stmt->domain = isl_set_intersect_params(stmt->domain, cond);
 927
 928         return stmt;
 929 error:
 930         isl_set_free(cond);
 931         return pet_stmt_free(stmt);
 932 }
 933
 934 /* Add extra conditions on the parameters to all iteration domains.
 935  */
 936 struct pet_scop *pet_scop_restrict(struct pet_scop *scop,
 937         __isl_take isl_set *cond)
 938 {
 939         int i;
 940
 941         if (!scop)
 942                 goto error;
 943
 944         for (i = 0; i < scop->n_stmt; ++i) {
 945                 scop->stmts[i] = stmt_restrict(scop->stmts[i],
 946                                                     isl_set_copy(cond));
 947                 if (!scop->stmts[i])
 948                         goto error;
 949         }
 950
 951         isl_set_free(cond);
 952         return scop;
 953 error:
 954         isl_set_free(cond);
 955         return pet_scop_free(scop);
 956 }
 957
 958 /* Add all parameters in "expr" to "dim" and return the result.
 959  */
 960 static __isl_give isl_dim *expr_collect_params(struct pet_expr *expr,
 961         __isl_take isl_dim *dim)
 962 {
 963         int i;
 964
 965         if (!expr)
 966                 goto error;
 967         for (i = 0; i < expr->n_arg; ++i)
 968
 969                 dim = expr_collect_params(expr->args[i], dim);
 970
 971         if (expr->type == pet_expr_access)
 972                 dim = isl_dim_align_params(dim,
 973                                             isl_map_get_dim(expr->acc.access));
 974
 975         return dim;
 976 error:
 977         isl_dim_free(dim);
 978         return pet_expr_free(expr);
 979 }
 980
 981 /* Add all parameters in "stmt" to "dim" and return the result.
 982  */
 983 static __isl_give isl_dim *stmt_collect_params(struct pet_stmt *stmt,
 984         __isl_take isl_dim *dim)
 985 {
 986         if (!stmt)
 987                 goto error;
 988
 989         dim = isl_dim_align_params(dim, isl_set_get_dim(stmt->domain));
 990         dim = isl_dim_align_params(dim, isl_map_get_dim(stmt->schedule));
 991         dim = expr_collect_params(stmt->body, dim);
 992
 993         return dim;
 994 error:
 995         isl_dim_free(dim);
 996         return pet_stmt_free(stmt);
 997 }
 998
 999 /* Add all parameters in "array" to "dim" and return the result.
1000  */
1001 static __isl_give isl_dim *array_collect_params(struct pet_array *array,
1002         __isl_take isl_dim *dim)
1003 {
1004         if (!array)
1005                 goto error;
1006
1007         dim = isl_dim_align_params(dim, isl_set_get_dim(array->context));
1008         dim = isl_dim_align_params(dim, isl_set_get_dim(array->extent));
1009
1010         return dim;
1011 error:
1012         isl_dim_free(dim);
1013         return pet_array_free(array);
1014 }
1015
1016 /* Add all parameters in "scop" to "dim" and return the result.
1017  */
1018 static __isl_give isl_dim *scop_collect_params(struct pet_scop *scop,
1019         __isl_take isl_dim *dim)
1020 {
1021         int i;
1022
1023         if (!scop)
1024                 goto error;
1025
1026         for (i = 0; i < scop->n_array; ++i)
1027                 dim = array_collect_params(scop->arrays[i], dim);
1028
1029         for (i = 0; i < scop->n_stmt; ++i)
1030                 dim = stmt_collect_params(scop->stmts[i], dim);
1031
1032         return dim;
1033 error:
1034         isl_dim_free(dim);
1035         return pet_scop_free(scop);
1036 }
1037
1038 /* Add all parameters in "dim" to all access relations in "expr".
1039  */
1040 static struct pet_expr *expr_propagate_params(struct pet_expr *expr,
1041         __isl_take isl_dim *dim)
1042 {
1043         int i;
1044
1045         if (!expr)
1046                 goto error;
1047
1048         for (i = 0; i < expr->n_arg; ++i) {
1049                 expr->args[i] =
1050                         expr_propagate_params(expr->args[i],
1051                                                 isl_dim_copy(dim));
1052                 if (!expr->args[i])
1053                         goto error;
1054         }
1055
1056         if (expr->type == pet_expr_access) {
1057                 expr->acc.access = isl_map_align_params(expr->acc.access,
1058                                                         isl_dim_copy(dim));
1059                 if (!expr->acc.access)
1060                         goto error;
1061         }
1062
1063         isl_dim_free(dim);
1064         return expr;
1065 error:
1066         isl_dim_free(dim);
1067         return pet_expr_free(expr);
1068 }
1069
1070 /* Add all parameters in "dim" to the domain, schedule and
1071  * all access relations in "stmt".
1072  */
1073 static struct pet_stmt *stmt_propagate_params(struct pet_stmt *stmt,
1074         __isl_take isl_dim *dim)
1075 {
1076         if (!stmt)
1077                 goto error;
1078
1079         stmt->domain = isl_set_align_params(stmt->domain, isl_dim_copy(dim));
1080         stmt->schedule = isl_map_align_params(stmt->schedule,
1081                                                 isl_dim_copy(dim));
1082         stmt->body = expr_propagate_params(stmt->body, isl_dim_copy(dim));
1083
1084         if (!stmt->domain || !stmt->schedule || !stmt->body)
1085                 goto error;
1086
1087         isl_dim_free(dim);
1088         return stmt;
1089 error:
1090         isl_dim_free(dim);
1091         return pet_stmt_free(stmt);
1092 }
1093
1094 /* Add all parameters in "dim" to "array".
1095  */
1096 static struct pet_array *array_propagate_params(struct pet_array *array,
1097         __isl_take isl_dim *dim)
1098 {
1099         if (!array)
1100                 goto error;
1101
1102         array->context = isl_set_align_params(array->context,
1103                                                 isl_dim_copy(dim));
1104         array->extent = isl_set_align_params(array->extent,
1105                                                 isl_dim_copy(dim));
1106         if (array->value_bounds) {
1107                 array->value_bounds = isl_set_align_params(array->value_bounds,
1108                                                         isl_dim_copy(dim));
1109                 if (!array->value_bounds)
1110                         goto error;
1111         }
1112
1113         if (!array->context || !array->extent)
1114                 goto error;
1115
1116         isl_dim_free(dim);
1117         return array;
1118 error:
1119         isl_dim_free(dim);
1120         return pet_array_free(array);
1121 }
1122
1123 /* Add all parameters in "dim" to "scop".
1124  */
1125 static struct pet_scop *scop_propagate_params(struct pet_scop *scop,
1126         __isl_take isl_dim *dim)
1127 {
1128         int i;
1129
1130         if (!scop)
1131                 goto error;
1132
1133         for (i = 0; i < scop->n_array; ++i) {
1134                 scop->arrays[i] = array_propagate_params(scop->arrays[i],
1135                                                         isl_dim_copy(dim));
1136                 if (!scop->arrays[i])
1137                         goto error;
1138         }
1139
1140         for (i = 0; i < scop->n_stmt; ++i) {
1141                 scop->stmts[i] = stmt_propagate_params(scop->stmts[i],
1142                                                         isl_dim_copy(dim));
1143                 if (!scop->stmts[i])
1144                         goto error;
1145         }
1146
1147         isl_dim_free(dim);
1148         return scop;
1149 error:
1150         isl_dim_free(dim);
1151         return pet_scop_free(scop);
1152 }
1153
1154 /* Update all isl_sets and isl_maps in "scop" such that they all
1155  * have the same parameters.
1156  */
1157 struct pet_scop *pet_scop_align_params(struct pet_scop *scop)
1158 {
1159         isl_dim *dim;
1160
1161         if (!scop)
1162                 return NULL;
1163
1164         dim = isl_set_get_dim(scop->context);
1165         dim = scop_collect_params(scop, dim);
1166
1167         scop->context = isl_set_align_params(scop->context, isl_dim_copy(dim));
1168         scop = scop_propagate_params(scop, dim);
1169
1170         return scop;
1171 }
1172
1173 /* Check if the given access relation accesses a (0D) array that corresponds
1174  * to one of the parameters in "dim".  If so, replace the array access
1175  * by an access to the set of integers with as index (and value)
1176  * that parameter.
1177  */
1178 static __isl_give isl_map *access_detect_parameter(__isl_take isl_map *access,
1179         __isl_take isl_dim *dim)
1180 {
1181         isl_id *array_id;
1182         int pos;
1183
1184         array_id = isl_map_get_tuple_id(access, isl_dim_out);
1185
1186         pos = isl_dim_find_dim_by_id(dim, isl_dim_param, array_id);
1187         isl_dim_free(dim);
1188
1189         if (pos < 0) {
1190                 isl_id_free(array_id);
1191                 return access;
1192         }
1193
1194         pos = isl_map_find_dim_by_id(access, isl_dim_param, array_id);
1195         if (pos < 0) {
1196                 access = isl_map_insert(access, isl_dim_param, 0, 1);
1197                 access = isl_map_set_dim_id(access, isl_dim_param, 0, array_id);
1198                 pos = 0;
1199         } else
1200                 isl_id_free(array_id);
1201
1202         access = isl_map_insert(access, isl_dim_out, 0, 1);
1203         access = isl_map_equate(access, isl_dim_param, pos, isl_dim_out, 0);
1204
1205         return access;
1206 }
1207
1208 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1209  * in "dim" by a value equal to the corresponding parameter.
1210  */
1211 static struct pet_expr *expr_detect_parameter_accesses(struct pet_expr *expr,
1212         __isl_take isl_dim *dim)
1213 {
1214         int i;
1215
1216         if (!expr)
1217                 goto error;
1218
1219         for (i = 0; i < expr->n_arg; ++i) {
1220                 expr->args[i] =
1221                         expr_detect_parameter_accesses(expr->args[i],
1222                                                 isl_dim_copy(dim));
1223                 if (!expr->args[i])
1224                         goto error;
1225         }
1226
1227         if (expr->type == pet_expr_access) {
1228                 expr->acc.access = access_detect_parameter(expr->acc.access,
1229                                                         isl_dim_copy(dim));
1230                 if (!expr->acc.access)
1231                         goto error;
1232         }
1233
1234         isl_dim_free(dim);
1235         return expr;
1236 error:
1237         isl_dim_free(dim);
1238         return pet_expr_free(expr);
1239 }
1240
1241 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1242  * in "dim" by a value equal to the corresponding parameter.
1243  */
1244 static struct pet_stmt *stmt_detect_parameter_accesses(struct pet_stmt *stmt,
1245         __isl_take isl_dim *dim)
1246 {
1247         if (!stmt)
1248                 goto error;
1249
1250         stmt->body = expr_detect_parameter_accesses(stmt->body,
1251                                                         isl_dim_copy(dim));
1252
1253         if (!stmt->domain || !stmt->schedule || !stmt->body)
1254                 goto error;
1255
1256         isl_dim_free(dim);
1257         return stmt;
1258 error:
1259         isl_dim_free(dim);
1260         return pet_stmt_free(stmt);
1261 }
1262
1263 /* Replace all accesses to (0D) arrays that correspond to one of the parameters
1264  * in "dim" by a value equal to the corresponding parameter.
1265  */
1266 static struct pet_scop *scop_detect_parameter_accesses(struct pet_scop *scop,
1267         __isl_take isl_dim *dim)
1268 {
1269         int i;
1270
1271         if (!scop)
1272                 goto error;
1273
1274         for (i = 0; i < scop->n_stmt; ++i) {
1275                 scop->stmts[i] = stmt_detect_parameter_accesses(scop->stmts[i],
1276                                                         isl_dim_copy(dim));
1277                 if (!scop->stmts[i])
1278                         goto error;
1279         }
1280
1281         isl_dim_free(dim);
1282         return scop;
1283 error:
1284         isl_dim_free(dim);
1285         return pet_scop_free(scop);
1286 }
1287
1288 /* Replace all accesses to (0D) arrays that correspond to any of
1289  * the parameters used in "scop" by a value equal
1290  * to the corresponding parameter.
1291  */
1292 struct pet_scop *pet_scop_detect_parameter_accesses(struct pet_scop *scop)
1293 {
1294         isl_dim *dim;
1295
1296         if (!scop)
1297                 return NULL;
1298
1299         dim = isl_set_get_dim(scop->context);
1300         dim = scop_collect_params(scop, dim);
1301
1302         scop = scop_detect_parameter_accesses(scop, dim);
1303
1304         return scop;
1305 }
1306
1307 /* Add all read access relations (if "read" is set) and/or all write
1308  * access relations (if "write" is set) to "accesses" and return the result.
1309  */
1310 static __isl_give isl_union_map *expr_collect_accesses(struct pet_expr *expr,
1311         int read, int write, __isl_take isl_union_map *accesses)
1312 {
1313         int i;
1314         isl_id *id;
1315         isl_dim *dim;
1316
1317         if (!expr)
1318                 return NULL;
1319
1320         for (i = 0; i < expr->n_arg; ++i)
1321                 accesses = expr_collect_accesses(expr->args[i],
1322                                                  read, write, accesses);
1323
1324         if (expr->type == pet_expr_access) {
1325                 id = isl_map_get_tuple_id(expr->acc.access, isl_dim_out);
1326                 if (id &&
1327                     ((read && expr->acc.read) || (write && expr->acc.write)))
1328                         accesses = isl_union_map_add_map(accesses,
1329                                                 isl_map_copy(expr->acc.access));
1330                 isl_id_free(id);
1331         }
1332
1333         return accesses;
1334 }
1335
1336 /* Collect and return all read access relations (if "read" is set)
1337  * and/or all write * access relations (if "write" is set) in "stmt".
1338  */
1339 static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt,
1340         int read, int write, __isl_take isl_dim *dim)
1341 {
1342         isl_union_map *accesses;
1343
1344         if (!stmt)
1345                 return NULL;
1346
1347         accesses = isl_union_map_empty(dim);
1348         accesses = expr_collect_accesses(stmt->body, read, write, accesses);
1349         accesses = isl_union_map_intersect_domain(accesses,
1350                         isl_union_set_from_set(isl_set_copy(stmt->domain)));
1351
1352         return accesses;
1353 }
1354
1355 /* Collect and return all read access relations (if "read" is set)
1356  * and/or all write * access relations (if "write" is set) in "scop".
1357  */
1358 static __isl_give isl_union_map *scop_collect_accesses(struct pet_scop *scop,
1359         int read, int write)
1360 {
1361         int i;
1362         isl_union_map *accesses;
1363
1364         if (!scop)
1365                 return NULL;
1366
1367         accesses = isl_union_map_empty(isl_set_get_dim(scop->context));
1368
1369         for (i = 0; i < scop->n_stmt; ++i) {
1370                 isl_union_map *accesses_i;
1371                 isl_dim *dim = isl_set_get_dim(scop->context);
1372                 accesses_i = stmt_collect_accesses(scop->stmts[i],
1373                                                    read, write, dim);
1374                 accesses = isl_union_map_union(accesses, accesses_i);
1375         }
1376
1377         return accesses;
1378 }
1379
1380 __isl_give isl_union_map *pet_scop_collect_reads(struct pet_scop *scop)
1381 {
1382         return scop_collect_accesses(scop, 1, 0);
1383 }
1384
1385 __isl_give isl_union_map *pet_scop_collect_writes(struct pet_scop *scop)
1386 {
1387         return scop_collect_accesses(scop, 0, 1);
1388 }
1389
1390 /* Collect and return the union of iteration domains in "scop".
1391  */
1392 __isl_give isl_union_set *pet_scop_collect_domains(struct pet_scop *scop)
1393 {
1394         int i;
1395         isl_set *domain_i;
1396         isl_union_set *domain;
1397
1398         if (!scop)
1399                 return NULL;
1400
1401         domain = isl_union_set_empty(isl_set_get_dim(scop->context));
1402
1403         for (i = 0; i < scop->n_stmt; ++i) {
1404                 domain_i = isl_set_copy(scop->stmts[i]->domain);
1405                 domain = isl_union_set_add_set(domain, domain_i);
1406         }
1407
1408         return domain;
1409 }
1410
1411 /* Collect and return the schedules of the statements in "scop".
1412  * The range is normalized to the maximal number of scheduling
1413  * dimensions.
1414  */
1415 __isl_give isl_union_map *pet_scop_collect_schedule(struct pet_scop *scop)
1416 {
1417         int i, j;
1418         isl_map *schedule_i;
1419         isl_union_map *schedule;
1420         int depth, max_depth = 0;
1421
1422         if (!scop)
1423                 return NULL;
1424
1425         schedule = isl_union_map_empty(isl_set_get_dim(scop->context));
1426
1427         for (i = 0; i < scop->n_stmt; ++i) {
1428                 depth = isl_map_dim(scop->stmts[i]->schedule, isl_dim_out);
1429                 if (depth > max_depth)
1430                         max_depth = depth;
1431         }
1432
1433         for (i = 0; i < scop->n_stmt; ++i) {
1434                 schedule_i = isl_map_copy(scop->stmts[i]->schedule);
1435                 depth = isl_map_dim(schedule_i, isl_dim_out);
1436                 schedule_i = isl_map_add_dims(schedule_i, isl_dim_out,
1437                                                 max_depth - depth);
1438                 for (j = depth; j < max_depth; ++j)
1439                         schedule_i = isl_map_fix_si(schedule_i,
1440                                                         isl_dim_out, j, 0);
1441                 schedule = isl_union_map_add_map(schedule, schedule_i);
1442         }
1443
1444         return schedule;
1445 }