1#include <assert.h> 2#include <stdlib.h> 3#include <stdio.h> 4#include <string.h> 5#include <ctype.h> 6#include <cloog/isl/cloog.h> 7#include <isl/list.h> 8#include <isl/constraint.h> 9#include <isl/ilp.h> 10#include <isl/aff.h> 11 12#ifdef OSL_SUPPORT 13#include <osl/macros.h> 14#include <osl/relation.h> 15#endif 16 17CloogDomain *cloog_domain_from_isl_set(__isl_take isl_set *set) 18{ 19 if (isl_set_is_params(set)) 20 set = isl_set_from_params(set); 21 set = isl_set_detect_equalities(set); 22 set = isl_set_compute_divs(set); 23 return (CloogDomain *)set; 24} 25 26__isl_give isl_set *isl_set_from_cloog_domain(CloogDomain *domain) 27{ 28 return (isl_set *)domain; 29} 30 31CloogScattering *cloog_scattering_from_isl_map(__isl_take isl_map *map) 32{ 33 return (CloogScattering *)map; 34} 35 36__isl_give isl_map *isl_map_from_cloog_scattering(CloogScattering *scattering) 37{ 38 return (isl_map *)scattering; 39} 40 41 42/** 43 * Returns true if each scattering dimension is defined in terms 44 * of the original iterators. 45 */ 46int cloog_scattering_fully_specified(CloogScattering *scattering, 47 CloogDomain *domain) 48{ 49 isl_map *map = isl_map_from_cloog_scattering(scattering); 50 return isl_map_is_single_valued(map); 51} 52 53 54CloogConstraintSet *cloog_domain_constraints(CloogDomain *domain) 55{ 56 isl_basic_set *bset; 57 isl_set *set = isl_set_from_cloog_domain(domain); 58 assert(isl_set_n_basic_set(set) == 1); 59 bset = isl_set_copy_basic_set(set); 60 return cloog_constraint_set_from_isl_basic_set(bset); 61} 62 63 64void cloog_domain_print_constraints(FILE *foo, CloogDomain *domain, 65 int print_number) 66{ 67 isl_basic_set *bset; 68 isl_set *set = isl_set_from_cloog_domain(domain); 69 70 if (print_number) 71 isl_set_print(set, foo, 0, ISL_FORMAT_EXT_POLYLIB); 72 else { 73 assert(isl_set_n_basic_set(set) == 1); 74 bset = isl_set_copy_basic_set(set); 75 isl_basic_set_print(bset, foo, 76 0, NULL, NULL, ISL_FORMAT_POLYLIB); 77 isl_basic_set_free(bset); 78 } 79} 80 81 82void cloog_scattering_print_constraints(FILE *foo, CloogScattering *scattering) 83{ 84 isl_map *map = isl_map_from_cloog_scattering(scattering); 85 isl_map_print(map, foo, 0, ISL_FORMAT_EXT_POLYLIB); 86} 87 88 89void cloog_domain_free(CloogDomain * domain) 90{ 91 isl_set *set = isl_set_from_cloog_domain(domain); 92 isl_set_free(set); 93} 94 95 96void cloog_scattering_free(CloogScattering *scatt) 97{ 98 isl_map *map = isl_map_from_cloog_scattering(scatt); 99 isl_map_free(map); 100} 101 102 103CloogDomain * cloog_domain_copy(CloogDomain * domain) 104{ 105 isl_set *set = isl_set_from_cloog_domain(domain); 106 return cloog_domain_from_isl_set(isl_set_copy(set)); 107} 108 109 110/** 111 * cloog_domain_convex function: 112 * Computes the convex hull of domain. 113 */ 114CloogDomain *cloog_domain_convex(CloogDomain *domain) 115{ 116 isl_set *set = isl_set_from_cloog_domain(domain); 117 set = isl_set_from_basic_set(isl_set_convex_hull(isl_set_copy(set))); 118 return cloog_domain_from_isl_set(set); 119} 120 121 122/** 123 * cloog_domain_simple_convex: 124 * Given a list (union) of polyhedra, this function returns a "simple" 125 * convex hull of this union. In particular, the constraints of the 126 * the returned polyhedron consist of (parametric) lower and upper 127 * bounds on individual variables and constraints that appear in the 128 * original polyhedra. 129 */ 130CloogDomain *cloog_domain_simple_convex(CloogDomain *domain) 131{ 132 struct isl_basic_set *hull; 133 isl_set *set = isl_set_from_cloog_domain(domain); 134 135 if (cloog_domain_isconvex(domain)) 136 return cloog_domain_copy(domain); 137 138 hull = isl_set_bounded_simple_hull(isl_set_copy(set)); 139 return cloog_domain_from_isl_set(isl_set_from_basic_set(hull)); 140} 141 142 143/** 144 * cloog_domain_simplify function: 145 * Given two polyhedral domains (dom1) and (dom2), 146 * this function finds the largest domain set (or the smallest list 147 * of non-redundant constraints), that when intersected with polyhedral 148 * domain (dom2) equals (dom1)intersect(dom2). The output is a new CloogDomain 149 * structure with a polyhedral domain with the "redundant" constraints removed. 150 * NB: the second domain is required not to be a union. 151 */ 152CloogDomain *cloog_domain_simplify(CloogDomain *dom1, CloogDomain *dom2) 153{ 154 isl_set *set1 = isl_set_from_cloog_domain(dom1); 155 isl_set *set2 = isl_set_from_cloog_domain(dom2); 156 set1 = isl_set_gist(isl_set_copy(set1), isl_set_copy(set2)); 157 return cloog_domain_from_isl_set(set1); 158} 159 160 161/** 162 * cloog_domain_union function: 163 * This function returns a new polyhedral domain which is the union of 164 * two polyhedral domains (dom1) U (dom2). 165 * Frees dom1 and dom2; 166 */ 167CloogDomain *cloog_domain_union(CloogDomain *dom1, CloogDomain *dom2) 168{ 169 isl_set *set1 = isl_set_from_cloog_domain(dom1); 170 isl_set *set2 = isl_set_from_cloog_domain(dom2); 171 set1 = isl_set_union(set1, set2); 172 return cloog_domain_from_isl_set(set1); 173} 174 175 176 177/** 178 * cloog_domain_intersection function: 179 * This function returns a new polyhedral domain which is the intersection of 180 * two polyhedral domains (dom1) \cap (dom2). 181 */ 182CloogDomain *cloog_domain_intersection(CloogDomain *dom1, CloogDomain *dom2) 183{ 184 isl_set *set1 = isl_set_from_cloog_domain(dom1); 185 isl_set *set2 = isl_set_from_cloog_domain(dom2); 186 set1 = isl_set_intersect(isl_set_copy(set1), isl_set_copy(set2)); 187 return cloog_domain_from_isl_set(set1); 188} 189 190 191/** 192 * cloog_domain_difference function: 193 * Returns the set difference domain \ minus. 194 */ 195CloogDomain *cloog_domain_difference(CloogDomain *domain, CloogDomain *minus) 196{ 197 isl_set *set1 = isl_set_from_cloog_domain(domain); 198 isl_set *set2 = isl_set_from_cloog_domain(minus); 199 set1 = isl_set_subtract(isl_set_copy(set1), isl_set_copy(set2)); 200 return cloog_domain_from_isl_set(set1); 201} 202 203 204/** 205 * cloog_domain_sort function: 206 * This function topologically sorts (nb_doms) domains. Here (doms) is an 207 * array of pointers to CloogDomains, (nb_doms) is the number of domains, 208 * (level) is the level to consider for partial ordering (nb_par) is the 209 * parameter space dimension, (permut) if not NULL, is an array of (nb_doms) 210 * integers that contains a permutation specification after call in order to 211 * apply the topological sorting. 212 */ 213void cloog_domain_sort(CloogDomain **doms, unsigned nb_doms, unsigned level, 214 int *permut) 215{ 216 int i, j, k, cmp; 217 struct isl_ctx *ctx; 218 unsigned char **follows; 219 isl_set *set_i, *set_j; 220 isl_basic_set *bset_i, *bset_j; 221 222 if (!nb_doms) 223 return; 224 set_i = isl_set_from_cloog_domain(doms[0]); 225 ctx = isl_set_get_ctx(set_i); 226 for (i = 0; i < nb_doms; i++) { 227 set_i = isl_set_from_cloog_domain(doms[i]); 228 assert(isl_set_n_basic_set(set_i) == 1); 229 } 230 231 follows = isl_alloc_array(ctx, unsigned char *, nb_doms); 232 assert(follows); 233 for (i = 0; i < nb_doms; ++i) { 234 follows[i] = isl_alloc_array(ctx, unsigned char, nb_doms); 235 assert(follows[i]); 236 for (j = 0; j < nb_doms; ++j) 237 follows[i][j] = 0; 238 } 239 240 for (i = 1; i < nb_doms; ++i) { 241 for (j = 0; j < i; ++j) { 242 if (follows[i][j] || follows[j][i]) 243 continue; 244 set_i = isl_set_from_cloog_domain(doms[i]); 245 set_j = isl_set_from_cloog_domain(doms[j]); 246 bset_i = isl_set_copy_basic_set(set_i); 247 bset_j = isl_set_copy_basic_set(set_j); 248 cmp = isl_basic_set_compare_at(bset_i, bset_j, level-1); 249 isl_basic_set_free(bset_i); 250 isl_basic_set_free(bset_j); 251 if (!cmp) 252 continue; 253 if (cmp > 0) { 254 follows[i][j] = 1; 255 for (k = 0; k < i; ++k) 256 follows[i][k] |= follows[j][k]; 257 } else { 258 follows[j][i] = 1; 259 for (k = 0; k < i; ++k) 260 follows[k][i] |= follows[k][j]; 261 } 262 } 263 } 264 265 for (i = 0, j = 0; i < nb_doms; j = (j + 1) % nb_doms) { 266 for (k = 0; k < nb_doms; ++k) 267 if (follows[j][k]) 268 break; 269 if (k < nb_doms) 270 continue; 271 for (k = 0; k < nb_doms; ++k) 272 follows[k][j] = 0; 273 follows[j][j] = 1; 274 permut[i] = 1 + j; 275 ++i; 276 } 277 278 for (i = 0; i < nb_doms; ++i) 279 free(follows[i]); 280 free(follows); 281} 282 283 284/** 285 * Check whether there is or may be any value of dom1 at the given level 286 * that is greater than or equal to a value of dom2 at the same level. 287 * 288 * Return 289 * 1 is there is or may be a greater-than pair. 290 * 0 if there is no greater-than pair, but there may be an equal-to pair 291 * -1 if there is definitely no such pair 292 */ 293int cloog_domain_follows(CloogDomain *dom1, CloogDomain *dom2, unsigned level) 294{ 295 isl_set *set1 = isl_set_from_cloog_domain(dom1); 296 isl_set *set2 = isl_set_from_cloog_domain(dom2); 297 int follows; 298 299 follows = isl_set_follows_at(set1, set2, level - 1); 300 assert(follows >= -1); 301 302 return follows; 303} 304 305 306/** 307 * cloog_domain_empty function: 308 * Returns an empty domain of the same dimensions as template. 309 */ 310CloogDomain *cloog_domain_empty(CloogDomain *template) 311{ 312 isl_set *set = isl_set_from_cloog_domain(template); 313 isl_space *space = isl_set_get_space(set); 314 return cloog_domain_from_isl_set(isl_set_empty(space)); 315} 316 317 318/** 319 * Return 1 if the specified dimension has both an upper and a lower bound. 320 */ 321int cloog_domain_is_bounded(CloogDomain *dom, unsigned level) 322{ 323 isl_set *set = isl_set_from_cloog_domain(dom); 324 return isl_set_dim_is_bounded(set, isl_dim_set, level - 1); 325} 326 327 328/****************************************************************************** 329 * Structure display function * 330 ******************************************************************************/ 331 332 333/** 334 * cloog_domain_print_structure : 335 * this function is a more human-friendly way to display the CloogDomain data 336 * structure, it only shows the constraint system and includes an indentation 337 * level (level) in order to work with others print_structure functions. 338 */ 339void cloog_domain_print_structure(FILE *file, CloogDomain *domain, int level, 340 const char *name) 341{ 342 int i ; 343 isl_set *set = isl_set_from_cloog_domain(domain); 344 345 /* Go to the right level. */ 346 for (i = 0; i < level; i++) 347 fprintf(file, "|\t"); 348 349 if (!set) { 350 fprintf(file, "+-- Null CloogDomain\n"); 351 return; 352 } 353 fprintf(file, "+-- %s\n", name); 354 for (i = 0; i < level+1; ++i) 355 fprintf(file, "|\t"); 356 357 isl_set_print(set, file, 0, ISL_FORMAT_ISL); 358 359 fprintf(file, "\n"); 360} 361 362 363/****************************************************************************** 364 * Memory deallocation function * 365 ******************************************************************************/ 366 367 368void cloog_domain_list_free(CloogDomainList *list) 369{ 370 CloogDomainList *next; 371 372 for ( ; list; list = next) { 373 next = list->next; 374 cloog_domain_free(list->domain); 375 free(list); 376 } 377} 378 379 380/** 381 * cloog_scattering_list_free function: 382 * This function frees the allocated memory for a CloogScatteringList structure. 383 */ 384void cloog_scattering_list_free(CloogScatteringList *list) 385{ 386 while (list != NULL) { 387 CloogScatteringList *temp = list->next; 388 isl_map *map = isl_map_from_cloog_scattering(list->scatt); 389 isl_map_free(map); 390 free(list); 391 list = temp; 392 } 393} 394 395 396/****************************************************************************** 397 * Reading function * 398 ******************************************************************************/ 399 400 401/** 402 * cloog_domain_read_context function: 403 * Read parameter domain. 404 */ 405CloogDomain *cloog_domain_read_context(CloogState *state, FILE *input) 406{ 407 struct isl_ctx *ctx = state->backend->ctx; 408 isl_set *set; 409 410 set = isl_set_read_from_file(ctx, input); 411 set = isl_set_move_dims(set, isl_dim_param, 0, 412 isl_dim_set, 0, isl_set_dim(set, isl_dim_set)); 413 414 return cloog_domain_from_isl_set(set); 415} 416 417 418/** 419 * cloog_domain_from_context 420 * Reinterpret context by turning parameters into variables. 421 */ 422CloogDomain *cloog_domain_from_context(CloogDomain *context) 423{ 424 isl_set *set = isl_set_from_cloog_domain(context); 425 426 set = isl_set_move_dims(set, isl_dim_set, 0, 427 isl_dim_param, 0, isl_set_dim(set, isl_dim_param)); 428 429 return cloog_domain_from_isl_set(set); 430} 431 432 433/** 434 * cloog_domain_union_read function: 435 * This function reads a union of polyhedra into a file (input) and 436 * returns a pointer to a CloogDomain containing the read information. 437 */ 438CloogDomain *cloog_domain_union_read(CloogState *state, 439 FILE *input, int nb_parameters) 440{ 441 struct isl_ctx *ctx = state->backend->ctx; 442 struct isl_set *set; 443 444 set = isl_set_read_from_file(ctx, input); 445 if (isl_set_dim(set, isl_dim_param) != nb_parameters) { 446 int dim = isl_set_dim(set, isl_dim_set); 447 set = isl_set_move_dims(set, isl_dim_param, 0, 448 isl_dim_set, dim - nb_parameters, nb_parameters); 449 } 450 return cloog_domain_from_isl_set(set); 451} 452 453 454/** 455 * cloog_domain_read_scattering function: 456 * This function reads in a scattering function from the file input. 457 * 458 * We try to read the scattering relation as a map, but if it is 459 * specified in the original PolyLib format, then isl_map_read_from_file 460 * will treat the input as a set return a map with zero input dimensions. 461 * In this case, we need to decompose the set into a map from 462 * scattering dimensions to domain dimensions and then invert the 463 * resulting map. 464 */ 465CloogScattering *cloog_domain_read_scattering(CloogDomain *domain, FILE *input) 466{ 467 isl_set *set = isl_set_from_cloog_domain(domain); 468 isl_ctx *ctx = isl_set_get_ctx(set); 469 struct isl_map *scat; 470 unsigned nparam; 471 unsigned dim; 472 unsigned n_scat; 473 474 dim = isl_set_dim(set, isl_dim_set); 475 nparam = isl_set_dim(set, isl_dim_param); 476 scat = isl_map_read_from_file(ctx, input); 477 if (isl_map_dim(scat, isl_dim_param) != nparam) { 478 int n_out = isl_map_dim(scat, isl_dim_out); 479 scat = isl_map_move_dims(scat, isl_dim_param, 0, 480 isl_dim_out, n_out - nparam, nparam); 481 } 482 if (isl_map_dim(scat, isl_dim_in) != dim) { 483 n_scat = isl_map_dim(scat, isl_dim_out) - dim; 484 scat = isl_map_move_dims(scat, isl_dim_in, 0, 485 isl_dim_out, n_scat, dim); 486 } 487 return cloog_scattering_from_isl_map(scat); 488} 489 490/****************************************************************************** 491 * CloogMatrix Reading function * 492 ******************************************************************************/ 493 494/** 495 * isl_constraint_read_from_matrix: 496 * Convert a single line of a matrix to a isl_constraint. 497 * Returns a pointer to the constraint if successful; NULL otherwise. 498 */ 499static struct isl_constraint *isl_constraint_read_from_matrix( 500 struct isl_space *dim, cloog_int_t *row) 501{ 502 struct isl_constraint *constraint; 503 int j; 504 int nvariables = isl_space_dim(dim, isl_dim_set); 505 int nparam = isl_space_dim(dim, isl_dim_param); 506 isl_local_space *ls = isl_local_space_from_space(dim); 507 508 if (cloog_int_is_zero(row[0])) 509 constraint = isl_equality_alloc(ls); 510 else 511 constraint = isl_inequality_alloc(ls); 512 513 for (j = 0; j < nvariables; ++j) 514 isl_constraint_set_coefficient(constraint, isl_dim_out, j, 515 row[1 + j]); 516 517 for (j = 0; j < nparam; ++j) 518 isl_constraint_set_coefficient(constraint, isl_dim_param, j, 519 row[1 + nvariables + j]); 520 521 isl_constraint_set_constant(constraint, row[1 + nvariables + nparam]); 522 523 return constraint; 524} 525 526/** 527 * isl_basic_set_read_from_matrix: 528 * Convert matrix to basic_set. The matrix contains nparam parameter columns. 529 * Returns a pointer to the basic_set if successful; NULL otherwise. 530 */ 531static struct isl_basic_set *isl_basic_set_read_from_matrix(struct isl_ctx *ctx, 532 CloogMatrix* matrix, int nparam) 533{ 534 struct isl_space *dim; 535 struct isl_basic_set *bset; 536 int i; 537 unsigned nrows, ncolumns; 538 539 nrows = matrix->NbRows; 540 ncolumns = matrix->NbColumns; 541 int nvariables = ncolumns - 2 - nparam; 542 543 dim = isl_space_set_alloc(ctx, nparam, nvariables); 544 545 bset = isl_basic_set_universe(isl_space_copy(dim)); 546 547 for (i = 0; i < nrows; ++i) { 548 cloog_int_t *row = matrix->p[i]; 549 struct isl_constraint *constraint = 550 isl_constraint_read_from_matrix(isl_space_copy(dim), row); 551 bset = isl_basic_set_add_constraint(bset, constraint); 552 } 553 554 isl_space_free(dim); 555 556 return bset; 557} 558 559/** 560 * cloog_domain_from_cloog_matrix: 561 * Create a CloogDomain containing the constraints described in matrix. 562 * nparam is the number of parameters contained in the domain. 563 * Returns a pointer to the CloogDomain if successful; NULL otherwise. 564 */ 565CloogDomain *cloog_domain_from_cloog_matrix(CloogState *state, 566 CloogMatrix *matrix, int nparam) 567{ 568 struct isl_ctx *ctx = state->backend->ctx; 569 struct isl_basic_set *bset; 570 571 bset = isl_basic_set_read_from_matrix(ctx, matrix, nparam); 572 573 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset)); 574} 575 576/** 577 * cloog_scattering_from_cloog_matrix: 578 * Create a CloogScattering containing the constraints described in matrix. 579 * nparam is the number of parameters contained in the domain. 580 * Returns a pointer to the CloogScattering if successful; NULL otherwise. 581 */ 582CloogScattering *cloog_scattering_from_cloog_matrix(CloogState *state, 583 CloogMatrix *matrix, int nb_scat, int nb_par) 584{ 585 struct isl_ctx *ctx = state->backend->ctx; 586 struct isl_basic_set *bset; 587 struct isl_basic_map *scat; 588 struct isl_space *dims; 589 unsigned dim; 590 591 bset = isl_basic_set_read_from_matrix(ctx, matrix, nb_par); 592 dim = isl_basic_set_n_dim(bset) - nb_scat; 593 dims = isl_space_alloc(ctx, nb_par, nb_scat, dim); 594 595 scat = isl_basic_map_from_basic_set(bset, dims); 596 scat = isl_basic_map_reverse(scat); 597 return cloog_scattering_from_isl_map(isl_map_from_basic_map(scat)); 598} 599 600 601/****************************************************************************** 602 * Processing functions * 603 ******************************************************************************/ 604 605 606#ifdef OSL_SUPPORT 607/** 608 * Converts an openscop relation to a CLooG domain. 609 * \param[in,out] state CLooG state. 610 * \param[in] relation OpenScop relation to convert. 611 * \return A new CloogDomain corresponding to the input OpenScop relation. 612 */ 613CloogDomain *cloog_domain_from_osl_relation(CloogState *state, 614 osl_relation_p relation) { 615 char *str; 616 struct isl_ctx *ctx = state->backend->ctx; 617 isl_set *set; 618 CloogDomain *domain = NULL; 619 620 if (relation != NULL) { 621 if (relation->precision != OSL_PRECISION_MP) 622 cloog_die("Non-GMP precision is not supported yet.\n"); 623 624 str = osl_relation_spprint_polylib(relation, NULL); 625 set = isl_set_read_from_str(ctx, str); 626 free(str); 627 628 domain = cloog_domain_from_isl_set(set); 629 } 630 631 return domain; 632} 633 634 635/** 636 * Converts an openscop scattering relation to a CLooG scattering. 637 * \param[in,out] state CLooG state. 638 * \param[in] relation OpenScop relation to convert. 639 * \return A new CloogScattering corresponding to the input OpenScop relation. 640 */ 641CloogScattering *cloog_scattering_from_osl_relation(CloogState *state, 642 osl_relation_p relation) { 643 char *str; 644 struct isl_ctx *ctx = state->backend->ctx; 645 isl_map *map; 646 CloogScattering *scattering = NULL; 647 648 if (relation != NULL) { 649 if (relation->precision != OSL_PRECISION_MP) 650 cloog_die("Non-GMP precision is not supported yet.\n"); 651 652 if (relation->type != OSL_TYPE_SCATTERING) 653 cloog_die("Cannot convert a non-scattering relation to a scattering.\n"); 654 655 str = osl_relation_spprint_polylib(relation, NULL); 656 map = isl_map_read_from_str(ctx, str); 657 free(str); 658 659 scattering = cloog_scattering_from_isl_map(map); 660 } 661 662 return scattering; 663} 664#endif 665 666/** 667 * cloog_domain_isempty function: 668 */ 669int cloog_domain_isempty(CloogDomain *domain) 670{ 671 isl_set *set = isl_set_from_cloog_domain(domain); 672 return isl_set_is_empty(set); 673} 674 675 676/** 677 * cloog_domain_universe function: 678 * This function returns the complete dim-dimensional space. 679 */ 680CloogDomain *cloog_domain_universe(CloogState *state, unsigned dim) 681{ 682 struct isl_space *dims; 683 struct isl_basic_set *bset; 684 685 dims = isl_space_set_alloc(state->backend->ctx, 0, dim); 686 bset = isl_basic_set_universe(dims); 687 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset)); 688} 689 690 691/** 692 * cloog_domain_project function: 693 * This function returns the projection of 694 * (domain) on the (level) first dimensions (i.e. outer loops). 695 */ 696CloogDomain *cloog_domain_project(CloogDomain *domain, int level) 697{ 698 isl_set *set = isl_set_from_cloog_domain(domain); 699 set = isl_set_remove_dims(isl_set_copy(set), isl_dim_set, 700 level, isl_set_n_dim(set) - level); 701 set = isl_set_compute_divs(set); 702 if (level > 0) 703 set = isl_set_remove_divs_involving_dims(set, 704 isl_dim_set, level - 1, 1); 705 return cloog_domain_from_isl_set(set); 706} 707 708 709/** 710 * cloog_domain_extend function: 711 * This function returns the (domain) given as input with (dim) 712 * dimensions and (nb_par) parameters. 713 * This function does not free (domain), and returns a new CloogDomain. 714 */ 715CloogDomain *cloog_domain_extend(CloogDomain *domain, int dim) 716{ 717 isl_set *set = isl_set_from_cloog_domain(domain); 718 int n = isl_set_dim(set, isl_dim_set); 719 set = isl_set_add_dims(isl_set_copy(set), isl_dim_set, dim - n); 720 return cloog_domain_from_isl_set(set); 721} 722 723 724/** 725 * cloog_domain_never_integral function: 726 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0. 727 * There is no need to check for such constraints explicitly for the isl 728 * backend. 729 */ 730int cloog_domain_never_integral(CloogDomain * domain) 731{ 732 isl_set *set = isl_set_from_cloog_domain(domain); 733 return isl_set_is_empty(set); 734} 735 736 737/** 738 * Check whether the loop at "level" is executed at most once. 739 * We construct a map that maps all remaining variables to this iterator 740 * and check whether this map is single valued. 741 * 742 * Alternatively, we could have mapped the domain through a mapping 743 * [p] -> { [..., i] -> [..., i'] : i' > i } 744 * and then taken the intersection of the original domain and the transformed 745 * domain. If this intersection is empty, then the corresponding 746 * loop is executed at most once. 747 */ 748int cloog_domain_is_otl(CloogDomain *domain, int level) 749{ 750 int otl; 751 isl_set *set = isl_set_from_cloog_domain(domain); 752 isl_map *map; 753 754 map = isl_map_from_domain(isl_set_copy(set)); 755 map = isl_map_move_dims(map, isl_dim_out, 0, isl_dim_in, level - 1, 1); 756 otl = isl_map_is_single_valued(map); 757 isl_map_free(map); 758 759 return otl; 760} 761 762 763/** 764 * cloog_domain_stride function: 765 * This function finds the stride imposed to unknown with the column number 766 * 'strided_level' in order to be integral. For instance, if we have a 767 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral 768 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to 769 * the unknown i. The function returns the imposed stride in a parameter field. 770 * - domain is the set of constraint we have to consider, 771 * - strided_level is the column number of the unknown for which a stride have 772 * to be found, 773 * - looking_level is the column number of the unknown that impose a stride to 774 * the first unknown. 775 * - stride is the stride that is returned back as a function parameter. 776 * - offset is the value of the constant c if the condition is of the shape 777 * (i + c)%s = 0, s being the stride. 778 */ 779void cloog_domain_stride(CloogDomain *domain, int strided_level, 780 cloog_int_t *stride, cloog_int_t *offset) 781{ 782 isl_set *set = isl_set_from_cloog_domain(domain); 783 isl_set_dim_residue_class(set, strided_level - 1, stride, offset); 784 if (!isl_int_is_zero(*offset)) 785 isl_int_sub(*offset, *stride, *offset); 786 return; 787} 788 789 790struct cloog_can_stride { 791 int level; 792 int can_stride; 793}; 794 795static int constraint_can_stride(__isl_take isl_constraint *c, void *user) 796{ 797 struct cloog_can_stride *ccs = (struct cloog_can_stride *)user; 798 int i; 799 isl_int v; 800 unsigned n_div; 801 802 if (isl_constraint_is_equality(c)) { 803 isl_constraint_free(c); 804 return 0; 805 } 806 807 isl_int_init(v); 808 isl_constraint_get_coefficient(c, isl_dim_set, ccs->level - 1, &v); 809 if (isl_int_is_pos(v)) { 810 n_div = isl_constraint_dim(c, isl_dim_div); 811 for (i = 0; i < n_div; ++i) { 812 isl_constraint_get_coefficient(c, isl_dim_div, i, &v); 813 if (!isl_int_is_zero(v)) 814 break; 815 } 816 if (i < n_div) 817 ccs->can_stride = 0; 818 } 819 isl_int_clear(v); 820 isl_constraint_free(c); 821 822 return 0; 823} 824 825static int basic_set_can_stride(__isl_take isl_basic_set *bset, void *user) 826{ 827 struct cloog_can_stride *ccs = (struct cloog_can_stride *)user; 828 int r; 829 830 r = isl_basic_set_foreach_constraint(bset, constraint_can_stride, ccs); 831 isl_basic_set_free(bset); 832 return r; 833} 834 835 836/** 837 * Return 1 if CLooG is allowed to perform stride detection on level "level" 838 * and 0 otherwise. 839 * Currently, stride detection is only allowed when none of the lower 840 * bound constraints involve any existentially quantified variables. 841 * The reason is that the current isl interface does not make it 842 * easy to construct an integer division that depends on other integer 843 * divisions. 844 * By not allowing existentially quantified variables in the constraints, 845 * we can ignore them in cloog_domain_stride_lower_bound. 846 */ 847int cloog_domain_can_stride(CloogDomain *domain, int level) 848{ 849 struct cloog_can_stride ccs = { level, 1 }; 850 isl_set *set = isl_set_from_cloog_domain(domain); 851 int r; 852 r = isl_set_foreach_basic_set(set, basic_set_can_stride, &ccs); 853 assert(r == 0); 854 return ccs.can_stride; 855} 856 857 858struct cloog_stride_lower { 859 int level; 860 CloogStride *stride; 861 isl_set *set; 862 isl_basic_set *bounds; 863}; 864 865/* If the given constraint is a lower bound on csl->level, then add 866 * a lower bound to csl->bounds that makes sure that the remainder 867 * of the smallest value on division by csl->stride is equal to csl->offset. 868 * 869 * In particular, the given lower bound is of the form 870 * 871 * a i + f >= 0 872 * 873 * where f may depend on the parameters and other iterators. 874 * The stride is s and the offset is d. 875 * The lower bound -f/a may not satisfy the above condition. In fact, 876 * it may not even be integral. We want to round this value of i up 877 * to the nearest value that satisfies the condition and add the corresponding 878 * lower bound constraint. This nearest value is obtained by rounding 879 * i - d up to the nearest multiple of s. 880 * That is, we first subtract d 881 * 882 * i' = -f/a - d 883 * 884 * then we round up to the nearest multiple of s 885 * 886 * i'' = s * ceil(i'/s) 887 * 888 * and finally, we add d again 889 * 890 * i''' = i'' + d 891 * 892 * and impose the constraint i >= i'''. 893 * 894 * We find 895 * 896 * i'' = s * ceil((-f - a * d)/(a * s)) = - s * floor((f + a * d)/(a * s)) 897 * 898 * i >= - s * floor((f + a * d)/(a * s)) + d 899 * 900 * or 901 * i + s * floor((f + a * d)/(a * s)) - d >= 0 902 */ 903static int constraint_stride_lower(__isl_take isl_constraint *c, void *user) 904{ 905 struct cloog_stride_lower *csl = (struct cloog_stride_lower *)user; 906 isl_int v; 907 isl_constraint *bound; 908 isl_aff *b; 909 910 if (isl_constraint_is_equality(c)) { 911 isl_constraint_free(c); 912 return 0; 913 } 914 915 isl_int_init(v); 916 isl_constraint_get_coefficient(c, isl_dim_set, csl->level - 1, &v); 917 if (!isl_int_is_pos(v)) { 918 isl_int_clear(v); 919 isl_constraint_free(c); 920 921 return 0; 922 } 923 924 b = isl_constraint_get_bound(c, isl_dim_set, csl->level - 1); 925 926 b = isl_aff_neg(b); 927 b = isl_aff_add_constant(b, csl->stride->offset); 928 b = isl_aff_scale_down(b, csl->stride->stride); 929 b = isl_aff_floor(b); 930 b = isl_aff_scale(b, csl->stride->stride); 931 isl_int_neg(v, csl->stride->offset); 932 b = isl_aff_add_constant(b, v); 933 b = isl_aff_add_coefficient_si(b, isl_dim_in, csl->level - 1, 1); 934 935 bound = isl_inequality_from_aff(b); 936 937 csl->bounds = isl_basic_set_add_constraint(csl->bounds, bound); 938 939 isl_int_clear(v); 940 isl_constraint_free(c); 941 942 return 0; 943} 944 945/* This functions performs essentially the same operation as 946 * constraint_stride_lower, the only difference being that the offset d 947 * is not a constant, but an affine expression in terms of the parameters 948 * and earlier variables. In particular the affine expression is equal 949 * to the coefficients of stride->constraint multiplied by stride->factor. 950 * As in constraint_stride_lower, we add an extra bound 951 * 952 * i + s * floor((f + a * d)/(a * s)) - d >= 0 953 * 954 * for each lower bound 955 * 956 * a i + f >= 0 957 * 958 * where d is not the aforementioned affine expression. 959 */ 960static int constraint_stride_lower_c(__isl_take isl_constraint *c, void *user) 961{ 962 struct cloog_stride_lower *csl = (struct cloog_stride_lower *)user; 963 isl_int v; 964 isl_constraint *bound; 965 isl_constraint *csl_c; 966 isl_aff *d, *b; 967 968 if (isl_constraint_is_equality(c)) { 969 isl_constraint_free(c); 970 return 0; 971 } 972 973 isl_int_init(v); 974 isl_constraint_get_coefficient(c, isl_dim_set, csl->level - 1, &v); 975 if (!isl_int_is_pos(v)) { 976 isl_int_clear(v); 977 isl_constraint_free(c); 978 979 return 0; 980 } 981 982 csl_c = cloog_constraint_to_isl(csl->stride->constraint); 983 984 d = isl_constraint_get_aff(csl_c); 985 d = isl_aff_drop_dims(d, isl_dim_div, 0, isl_aff_dim(d, isl_dim_div)); 986 d = isl_aff_set_coefficient_si(d, isl_dim_in, csl->level - 1, 0); 987 d = isl_aff_scale(d, csl->stride->factor); 988 989 b = isl_constraint_get_bound(c, isl_dim_set, csl->level - 1); 990 991 b = isl_aff_neg(b); 992 b = isl_aff_add(b, isl_aff_copy(d)); 993 b = isl_aff_scale_down(b, csl->stride->stride); 994 b = isl_aff_floor(b); 995 b = isl_aff_scale(b, csl->stride->stride); 996 b = isl_aff_sub(b, d); 997 b = isl_aff_add_coefficient_si(b, isl_dim_in, csl->level - 1, 1); 998 999 bound = isl_inequality_from_aff(b); 1000 1001 csl->bounds = isl_basic_set_add_constraint(csl->bounds, bound); 1002 1003 isl_int_clear(v); 1004 isl_constraint_free(c); 1005 1006 return 0; 1007} 1008 1009static int basic_set_stride_lower(__isl_take isl_basic_set *bset, void *user) 1010{ 1011 struct cloog_stride_lower *csl = (struct cloog_stride_lower *)user; 1012 int r; 1013 1014 csl->bounds = isl_basic_set_universe(isl_basic_set_get_space(bset)); 1015 if (csl->stride->constraint) 1016 r = isl_basic_set_foreach_constraint(bset, 1017 &constraint_stride_lower_c, csl); 1018 else 1019 r = isl_basic_set_foreach_constraint(bset, 1020 &constraint_stride_lower, csl); 1021 bset = isl_basic_set_intersect(bset, csl->bounds); 1022 csl->set = isl_set_union(csl->set, isl_set_from_basic_set(bset)); 1023 1024 return r; 1025} 1026 1027/** 1028 * Update the lower bounds at level "level" to the given stride information. 1029 * That is, make sure that the remainder on division by "stride" 1030 * is equal to "offset". 1031 */ 1032CloogDomain *cloog_domain_stride_lower_bound(CloogDomain *domain, int level, 1033 CloogStride *stride) 1034{ 1035 struct cloog_stride_lower csl; 1036 isl_set *set = isl_set_from_cloog_domain(domain); 1037 int r; 1038 1039 csl.stride = stride; 1040 csl.level = level; 1041 csl.set = isl_set_empty(isl_set_get_space(set)); 1042 1043 r = isl_set_foreach_basic_set(set, basic_set_stride_lower, &csl); 1044 assert(r == 0); 1045 1046 cloog_domain_free(domain); 1047 return cloog_domain_from_isl_set(csl.set); 1048} 1049 1050 1051/* Add stride constraint, if any, to domain. 1052 */ 1053CloogDomain *cloog_domain_add_stride_constraint(CloogDomain *domain, 1054 CloogStride *stride) 1055{ 1056 isl_constraint *c; 1057 isl_set *set; 1058 1059 if (!stride || !stride->constraint) 1060 return domain; 1061 1062 set = isl_set_from_cloog_domain(domain); 1063 c = isl_constraint_copy(cloog_constraint_to_isl(stride->constraint)); 1064 1065 set = isl_set_add_constraint(set, c); 1066 1067 return cloog_domain_from_isl_set(set); 1068} 1069 1070 1071/** 1072 * cloog_domain_lazy_equal function: 1073 * This function returns 1 if the domains given as input are the same, 0 if it 1074 * is unable to decide. 1075 */ 1076int cloog_domain_lazy_equal(CloogDomain *d1, CloogDomain *d2) 1077{ 1078 isl_set *set1 = isl_set_from_cloog_domain(d1); 1079 isl_set *set2 = isl_set_from_cloog_domain(d2); 1080 return isl_set_fast_is_equal(set1, set2); 1081} 1082 1083struct cloog_bound_split { 1084 isl_set *set; 1085 int level; 1086 int lower; 1087 int upper; 1088}; 1089 1090static int constraint_bound_split(__isl_take isl_constraint *c, void *user) 1091{ 1092 struct cloog_bound_split *cbs = (struct cloog_bound_split *)user; 1093 isl_int v; 1094 int i; 1095 int handle = 0; 1096 1097 isl_int_init(v); 1098 isl_constraint_get_coefficient(c, isl_dim_set, cbs->level - 1, &v); 1099 if (!cbs->lower && isl_int_is_pos(v)) 1100 cbs->lower = handle = 1; 1101 else if (!cbs->upper && isl_int_is_neg(v)) 1102 cbs->upper = handle = 1; 1103 if (handle) { 1104 for (i = 0; i < isl_set_dim(cbs->set, isl_dim_param); ++i) { 1105 isl_constraint_get_coefficient(c, isl_dim_param, i, &v); 1106 if (isl_int_is_zero(v)) 1107 continue; 1108 cbs->set = isl_set_split_dims(cbs->set, 1109 isl_dim_param, i, 1); 1110 } 1111 } 1112 isl_int_clear(v); 1113 isl_constraint_free(c); 1114 1115 return (cbs->lower && cbs->upper) ? -1 : 0; 1116} 1117 1118static int basic_set_bound_split(__isl_take isl_basic_set *bset, void *user) 1119{ 1120 struct cloog_bound_split *cbs = (struct cloog_bound_split *)user; 1121 int r; 1122 1123 cbs->lower = 0; 1124 cbs->upper = 0; 1125 r = isl_basic_set_foreach_constraint(bset, constraint_bound_split, cbs); 1126 isl_basic_set_free(bset); 1127 return ((!cbs->lower || !cbs->upper) && r < 0) ? -1 : 0; 1128} 1129 1130/** 1131 * Return a union of sets S_i such that the convex hull of "dom", 1132 * when intersected with one the sets S_i, will have an upper and 1133 * lower bound for the dimension at "level" (provided "dom" itself 1134 * has such bounds for the dimensions). 1135 * 1136 * We currently take a very simple approach. For each of the basic 1137 * sets in "dom" we pick a lower and an upper bound and split the 1138 * range of any parameter involved in these two bounds in a 1139 * nonnegative and a negative part. This ensures that the symbolic 1140 * constant in these two constraints are themselves bounded and 1141 * so there will be at least one upper and one lower bound 1142 * in the convex hull. 1143 */ 1144CloogDomain *cloog_domain_bound_splitter(CloogDomain *dom, int level) 1145{ 1146 struct cloog_bound_split cbs; 1147 isl_set *set = isl_set_from_cloog_domain(dom); 1148 int r; 1149 cbs.level = level; 1150 cbs.set = isl_set_universe(isl_set_get_space(set)); 1151 r = isl_set_foreach_basic_set(set, basic_set_bound_split, &cbs); 1152 assert(r == 0); 1153 return cloog_domain_from_isl_set(cbs.set); 1154} 1155 1156 1157/* Check whether the union of scattering functions over all domains 1158 * is obviously injective. 1159 */ 1160static int injective_scattering(CloogScatteringList *list) 1161{ 1162 isl_map *map; 1163 isl_union_map *umap; 1164 int injective; 1165 int i = 0; 1166 char name[30]; 1167 1168 if (!list) 1169 return 1; 1170 1171 map = isl_map_copy(isl_map_from_cloog_scattering(list->scatt)); 1172 snprintf(name, sizeof(name), "S%d", i); 1173 map = isl_map_set_tuple_name(map, isl_dim_in, name); 1174 umap = isl_union_map_from_map(map); 1175 1176 for (list = list->next, ++i; list; list = list->next, ++i) { 1177 map = isl_map_copy(isl_map_from_cloog_scattering(list->scatt)); 1178 snprintf(name, sizeof(name), "S%d", i); 1179 map = isl_map_set_tuple_name(map, isl_dim_in, name); 1180 umap = isl_union_map_add_map(umap, map); 1181 } 1182 1183 injective = isl_union_map_plain_is_injective(umap); 1184 1185 isl_union_map_free(umap); 1186 1187 return injective; 1188} 1189 1190 1191/** 1192 * cloog_scattering_lazy_block function: 1193 * This function returns 1 if the two scattering functions s1 and s2 given 1194 * as input are the same (except possibly for the final dimension, where we 1195 * allow a difference of 1), assuming that the domains on which this 1196 * scatterings are applied are the same. 1197 * In fact this function answers the question "can I 1198 * safely consider the two domains as only one with two statements (a block) ?". 1199 * A difference of 1 in the final dimension is only allowed if the 1200 * entire scattering function is injective. 1201 * - s1 and s2 are the two domains to check for blocking, 1202 * - scattering is the linked list of all domains, 1203 * - scattdims is the total number of scattering dimentions. 1204 */ 1205int cloog_scattering_lazy_block(CloogScattering *s1, CloogScattering *s2, 1206 CloogScatteringList *scattering, int scattdims) 1207{ 1208 int i; 1209 struct isl_space *dim; 1210 struct isl_map *rel; 1211 struct isl_set *delta; 1212 isl_map *map1 = isl_map_from_cloog_scattering(s1); 1213 isl_map *map2 = isl_map_from_cloog_scattering(s2); 1214 int fixed, block; 1215 isl_int cst; 1216 unsigned n_scat; 1217 1218 n_scat = isl_map_dim(map1, isl_dim_out); 1219 if (n_scat != isl_map_dim(map2, isl_dim_out)) 1220 return 0; 1221 1222 dim = isl_map_get_space(map1); 1223 dim = isl_space_map_from_set(isl_space_domain(dim)); 1224 rel = isl_map_identity(dim); 1225 rel = isl_map_apply_domain(rel, isl_map_copy(map1)); 1226 rel = isl_map_apply_range(rel, isl_map_copy(map2)); 1227 delta = isl_map_deltas(rel); 1228 isl_int_init(cst); 1229 for (i = 0; i < n_scat; ++i) { 1230 fixed = isl_set_fast_dim_is_fixed(delta, i, &cst); 1231 if (fixed != 1) 1232 break; 1233 if (isl_int_is_zero(cst)) 1234 continue; 1235 if (i + 1 < n_scat) 1236 break; 1237 if (!isl_int_is_one(cst)) 1238 break; 1239 if (!injective_scattering(scattering)) 1240 break; 1241 } 1242 block = i >= n_scat; 1243 isl_int_clear(cst); 1244 isl_set_free(delta); 1245 return block; 1246} 1247 1248 1249/** 1250 * cloog_domain_lazy_disjoint function: 1251 * This function returns 1 if the domains given as input are disjoint, 0 if it 1252 * is unable to decide. 1253 */ 1254int cloog_domain_lazy_disjoint(CloogDomain *d1, CloogDomain *d2) 1255{ 1256 isl_set *set1 = isl_set_from_cloog_domain(d1); 1257 isl_set *set2 = isl_set_from_cloog_domain(d2); 1258 return isl_set_fast_is_disjoint(set1, set2); 1259} 1260 1261 1262/** 1263 * cloog_scattering_list_lazy_same function: 1264 * This function returns 1 if two domains in the list are the same, 0 if it 1265 * is unable to decide. 1266 */ 1267int cloog_scattering_list_lazy_same(CloogScatteringList *list) 1268{ 1269 CloogScatteringList *one, *other; 1270 isl_map *one_map, *other_map; 1271 1272 for (one = list; one; one = one->next) { 1273 one_map = isl_map_from_cloog_scattering(one->scatt); 1274 for (other = one->next; other; other = other->next) { 1275 other_map = isl_map_from_cloog_scattering(other->scatt); 1276 if (isl_map_fast_is_equal(one_map, other_map)) 1277 return 1; 1278 } 1279 } 1280 return 0; 1281} 1282 1283int cloog_domain_dimension(CloogDomain * domain) 1284{ 1285 isl_set *set = isl_set_from_cloog_domain(domain); 1286 return isl_set_dim(set, isl_dim_set); 1287} 1288 1289int cloog_domain_parameter_dimension(CloogDomain *domain) 1290{ 1291 isl_set *set = isl_set_from_cloog_domain(domain); 1292 return isl_set_dim(set, isl_dim_param); 1293} 1294 1295int cloog_scattering_dimension(CloogScattering *scatt, CloogDomain *domain) 1296{ 1297 isl_map *map = isl_map_from_cloog_scattering(scatt); 1298 return isl_map_dim(map, isl_dim_out); 1299} 1300 1301int cloog_domain_isconvex(CloogDomain * domain) 1302{ 1303 isl_set *set = isl_set_from_cloog_domain(domain); 1304 return isl_set_n_basic_set(set) <= 1; 1305} 1306 1307 1308/** 1309 * cloog_domain_cut_first function: 1310 * This function splits off and returns the first convex set in the 1311 * union "domain". The remainder of the union is returned in rest. 1312 * The original "domain" itself is destroyed and may not be used 1313 * after a call to this function. 1314 */ 1315CloogDomain *cloog_domain_cut_first(CloogDomain *domain, CloogDomain **rest) 1316{ 1317 isl_set *set = isl_set_from_cloog_domain(domain); 1318 struct isl_basic_set *first; 1319 1320 first = isl_set_copy_basic_set(set); 1321 set = isl_set_drop_basic_set(set, first); 1322 *rest = cloog_domain_from_isl_set(set); 1323 1324 return cloog_domain_from_isl_set(isl_set_from_basic_set(first)); 1325} 1326 1327 1328/** 1329 * Given a union domain, try to find a simpler representation 1330 * using fewer sets in the union. 1331 * The original "domain" itself is destroyed and may not be used 1332 * after a call to this function. 1333 */ 1334CloogDomain *cloog_domain_simplify_union(CloogDomain *domain) 1335{ 1336 isl_set *set = isl_set_from_cloog_domain(domain); 1337 return cloog_domain_from_isl_set(isl_set_coalesce(set)); 1338} 1339 1340 1341/** 1342 * cloog_scattering_lazy_isscalar function: 1343 * this function returns 1 if the scattering dimension 'dimension' in the 1344 * scattering 'scatt' is constant. 1345 * If value is not NULL, then it is set to the constant value of dimension. 1346 */ 1347int cloog_scattering_lazy_isscalar(CloogScattering *scatt, int dimension, 1348 cloog_int_t *value) 1349{ 1350 isl_map *map = isl_map_from_cloog_scattering(scatt); 1351 return isl_map_fast_is_fixed(map, isl_dim_out, dimension, value); 1352} 1353 1354 1355/** 1356 * cloog_domain_lazy_isconstant function: 1357 * this function returns 1 if the dimension 'dimension' in the 1358 * domain 'domain' is constant. 1359 * If value is not NULL, then it is set to the constant value of dimension. 1360 */ 1361int cloog_domain_lazy_isconstant(CloogDomain *domain, int dimension, 1362 cloog_int_t *value) 1363{ 1364 isl_set *set = isl_set_from_cloog_domain(domain); 1365 return isl_set_fast_dim_is_fixed(set, dimension, value); 1366} 1367 1368 1369/** 1370 * cloog_scattering_erase_dimension function: 1371 * this function returns a CloogDomain structure builds from 'domain' where 1372 * we removed the dimension 'dimension' and every constraint involving this 1373 * dimension. 1374 */ 1375CloogScattering *cloog_scattering_erase_dimension(CloogScattering *scattering, 1376 int dimension) 1377{ 1378 isl_map *map = isl_map_from_cloog_scattering(scattering); 1379 map = isl_map_remove_dims(isl_map_copy(map), isl_dim_out, dimension, 1); 1380 return cloog_scattering_from_isl_map(map); 1381} 1382 1383/** 1384 * cloog_domain_cube: 1385 * Construct and return a dim-dimensional cube, with values ranging 1386 * between min and max in each dimension. 1387 */ 1388CloogDomain *cloog_domain_cube(CloogState *state, 1389 int dim, cloog_int_t min, cloog_int_t max) 1390{ 1391 int i; 1392 struct isl_basic_set *cube; 1393 struct isl_basic_set *interval; 1394 struct isl_basic_set_list *list; 1395 1396 if (dim == 0) 1397 return cloog_domain_universe(state, dim); 1398 1399 interval = isl_basic_set_interval(state->backend->ctx, min, max); 1400 list = isl_basic_set_list_alloc(state->backend->ctx, dim); 1401 for (i = 0; i < dim; ++i) 1402 list = isl_basic_set_list_add(list, isl_basic_set_copy(interval)); 1403 isl_basic_set_free(interval); 1404 cube = isl_basic_set_list_product(list); 1405 return cloog_domain_from_isl_set(isl_set_from_basic_set(cube)); 1406} 1407 1408 1409/** 1410 * cloog_domain_scatter function: 1411 * This function add the scattering (scheduling) informations to a domain. 1412 */ 1413CloogDomain *cloog_domain_scatter(CloogDomain *domain, CloogScattering *scatt) 1414{ 1415 isl_set *set = isl_set_from_cloog_domain(domain); 1416 isl_map *map = isl_map_from_cloog_scattering(scatt); 1417 1418 map = isl_map_reverse(isl_map_copy(map)); 1419 map = isl_map_intersect_range(map, set); 1420 set = isl_set_flatten(isl_map_wrap(map)); 1421 return cloog_domain_from_isl_set(set); 1422} 1423 1424static int add_domain_from_map(__isl_take isl_map *map, void *user) 1425{ 1426 isl_space *dim; 1427 const char *name; 1428 CloogDomain *domain; 1429 CloogScattering *scat; 1430 CloogUnionDomain **ud = (CloogUnionDomain **)user; 1431 1432 dim = isl_map_get_space(map); 1433 name = isl_space_get_tuple_name(dim, isl_dim_in); 1434 domain = cloog_domain_from_isl_set(isl_map_domain(isl_map_copy(map))); 1435 scat = cloog_scattering_from_isl_map(map); 1436 *ud = cloog_union_domain_add_domain(*ud, name, domain, scat, NULL); 1437 isl_space_free(dim); 1438 1439 return 0; 1440} 1441 1442/** 1443 * Construct a CloogUnionDomain from an isl_union_map representing 1444 * a global scattering function. The input is a mapping from different 1445 * spaces (different tuple names and possibly different dimensions) 1446 * to a common space. The iteration domains are set to the domains 1447 * in each space. The statement names are set to the names of the 1448 * spaces. The parameter names of the result are set to those of 1449 * the input, but the iterator and scattering dimension names are 1450 * left unspecified. 1451 */ 1452CloogUnionDomain *cloog_union_domain_from_isl_union_map( 1453 __isl_take isl_union_map *umap) 1454{ 1455 int i; 1456 int nparam; 1457 isl_space *dim; 1458 CloogUnionDomain *ud; 1459 1460 dim = isl_union_map_get_space(umap); 1461 nparam = isl_space_dim(dim, isl_dim_param); 1462 1463 ud = cloog_union_domain_alloc(nparam); 1464 1465 for (i = 0; i < nparam; ++i) { 1466 const char *s = isl_space_get_dim_name(dim, isl_dim_param, i); 1467 ud = cloog_union_domain_set_name(ud, CLOOG_PARAM, i, s); 1468 } 1469 isl_space_free(dim); 1470 1471 if (isl_union_map_foreach_map(umap, &add_domain_from_map, &ud) < 0) { 1472 isl_union_map_free(umap); 1473 cloog_union_domain_free(ud); 1474 assert(0); 1475 } 1476 1477 isl_union_map_free(umap); 1478 1479 return ud; 1480} 1481 1482static int count_same_name(__isl_keep isl_space *dim, 1483 enum isl_dim_type type, unsigned pos, const char *name) 1484{ 1485 enum isl_dim_type t; 1486 unsigned p, s; 1487 int count = 0; 1488 int len = strlen(name); 1489 1490 for (t = isl_dim_param; t <= type && t <= isl_dim_out; ++t) { 1491 s = t == type ? pos : isl_space_dim(dim, t); 1492 for (p = 0; p < s; ++p) { 1493 const char *n = isl_space_get_dim_name(dim, t, p); 1494 if (n && !strncmp(n, name, len)) 1495 count++; 1496 } 1497 } 1498 return count; 1499} 1500 1501static CloogUnionDomain *add_domain(__isl_take isl_set *set, CloogUnionDomain *ud) 1502{ 1503 int i, nvar; 1504 isl_ctx *ctx; 1505 isl_space *dim; 1506 char buffer[20]; 1507 const char *name; 1508 CloogDomain *domain; 1509 1510 ctx = isl_set_get_ctx(set); 1511 dim = isl_set_get_space(set); 1512 name = isl_space_get_tuple_name(dim, isl_dim_set); 1513 set = isl_set_flatten(set); 1514 set = isl_set_set_tuple_name(set, NULL); 1515 domain = cloog_domain_from_isl_set(set); 1516 ud = cloog_union_domain_add_domain(ud, name, domain, NULL, NULL); 1517 1518 nvar = isl_space_dim(dim, isl_dim_set); 1519 for (i = 0; i < nvar; ++i) { 1520 char *long_name = NULL; 1521 int n; 1522 1523 name = isl_space_get_dim_name(dim, isl_dim_set, i); 1524 if (!name) { 1525 snprintf(buffer, sizeof(buffer), "i%d", i); 1526 name = buffer; 1527 } 1528 n = count_same_name(dim, isl_dim_set, i, name); 1529 if (n) { 1530 int size = strlen(name) + 10; 1531 long_name = isl_alloc_array(ctx, char, size); 1532 if (!long_name) 1533 cloog_die("memory overflow.\n"); 1534 snprintf(long_name, size, "%s_%d", name, n); 1535 name = long_name; 1536 } 1537 ud = cloog_union_domain_set_name(ud, CLOOG_ITER, i, name); 1538 free(long_name); 1539 } 1540 isl_space_free(dim); 1541 1542 return ud; 1543} 1544 1545/** 1546 * Construct a CloogUnionDomain from an isl_set. 1547 * The statement names are set to the names of the 1548 * spaces. The parameter and iterator names of the result are set to those of 1549 * the input, but the scattering dimension names are left unspecified. 1550 */ 1551CloogUnionDomain *cloog_union_domain_from_isl_set( 1552 __isl_take isl_set *set) 1553{ 1554 int i; 1555 int nparam; 1556 isl_space *dim; 1557 CloogUnionDomain *ud; 1558 1559 dim = isl_set_get_space(set); 1560 nparam = isl_space_dim(dim, isl_dim_param); 1561 1562 ud = cloog_union_domain_alloc(nparam); 1563 1564 for (i = 0; i < nparam; ++i) { 1565 const char *s = isl_space_get_dim_name(dim, isl_dim_param, i); 1566 ud = cloog_union_domain_set_name(ud, CLOOG_PARAM, i, s); 1567 } 1568 isl_space_free(dim); 1569 1570 ud = add_domain(set, ud); 1571 1572 return ud; 1573} 1574 1575/* Computes x, y and g such that g = gcd(a,b) and a*x+b*y = g */ 1576static void Euclid(cloog_int_t a, cloog_int_t b, 1577 cloog_int_t *x, cloog_int_t *y, cloog_int_t *g) 1578{ 1579 cloog_int_t c, d, e, f, tmp; 1580 1581 cloog_int_init(c); 1582 cloog_int_init(d); 1583 cloog_int_init(e); 1584 cloog_int_init(f); 1585 cloog_int_init(tmp); 1586 cloog_int_abs(c, a); 1587 cloog_int_abs(d, b); 1588 cloog_int_set_si(e, 1); 1589 cloog_int_set_si(f, 0); 1590 while (cloog_int_is_pos(d)) { 1591 cloog_int_tdiv_q(tmp, c, d); 1592 cloog_int_mul(tmp, tmp, f); 1593 cloog_int_sub(e, e, tmp); 1594 cloog_int_tdiv_q(tmp, c, d); 1595 cloog_int_mul(tmp, tmp, d); 1596 cloog_int_sub(c, c, tmp); 1597 cloog_int_swap(c, d); 1598 cloog_int_swap(e, f); 1599 } 1600 cloog_int_set(*g, c); 1601 if (cloog_int_is_zero(a)) 1602 cloog_int_set_si(*x, 0); 1603 else if (cloog_int_is_pos(a)) 1604 cloog_int_set(*x, e); 1605 else cloog_int_neg(*x, e); 1606 if (cloog_int_is_zero(b)) 1607 cloog_int_set_si(*y, 0); 1608 else { 1609 cloog_int_mul(tmp, a, *x); 1610 cloog_int_sub(tmp, c, tmp); 1611 cloog_int_divexact(*y, tmp, b); 1612 } 1613 cloog_int_clear(c); 1614 cloog_int_clear(d); 1615 cloog_int_clear(e); 1616 cloog_int_clear(f); 1617 cloog_int_clear(tmp); 1618} 1619 1620/* Construct a CloogStride from the given constraint for the given level, 1621 * if possible. 1622 * We first compute the gcd of the coefficients of the existentially 1623 * quantified variables and then remove any common factors it has 1624 * with the coefficient at the given level. 1625 * The result is the value of the stride and if it is not one, 1626 * then it is possible to construct a CloogStride. 1627 * The constraint leading to the stride is stored in the CloogStride 1628 * as well a value (factor) such that the product of this value 1629 * and the coefficient at the given level is equal to -1 modulo the stride. 1630 */ 1631static CloogStride *construct_stride(isl_constraint *c, int level) 1632{ 1633 int i, n, sign; 1634 isl_int v, m, gcd, stride, factor; 1635 CloogStride *s; 1636 1637 if (!c) 1638 return NULL; 1639 1640 isl_int_init(v); 1641 isl_int_init(m); 1642 isl_int_init(gcd); 1643 isl_int_init(factor); 1644 isl_int_init(stride); 1645 1646 isl_constraint_get_coefficient(c, isl_dim_set, level - 1, &v); 1647 sign = isl_int_sgn(v); 1648 isl_int_abs(m, v); 1649 1650 isl_int_set_si(gcd, 0); 1651 n = isl_constraint_dim(c, isl_dim_div); 1652 for (i = 0; i < n; ++i) { 1653 isl_constraint_get_coefficient(c, isl_dim_div, i, &v); 1654 isl_int_gcd(gcd, gcd, v); 1655 } 1656 1657 isl_int_gcd(v, m, gcd); 1658 isl_int_divexact(stride, gcd, v); 1659 1660 if (isl_int_is_zero(stride) || isl_int_is_one(stride)) 1661 s = NULL; 1662 else { 1663 Euclid(m, stride, &factor, &v, &gcd); 1664 if (sign > 0) 1665 isl_int_neg(factor, factor); 1666 1667 c = isl_constraint_copy(c); 1668 s = cloog_stride_alloc_from_constraint(stride, 1669 cloog_constraint_from_isl_constraint(c), factor); 1670 } 1671 1672 isl_int_clear(stride); 1673 isl_int_clear(factor); 1674 isl_int_clear(gcd); 1675 isl_int_clear(m); 1676 isl_int_clear(v); 1677 1678 return s; 1679} 1680 1681struct cloog_isl_find_stride_data { 1682 int level; 1683 CloogStride *stride; 1684}; 1685 1686/* Check if the given constraint can be used to derive 1687 * a stride on the iterator identified by data->level. 1688 * We first check that there are some existentially quantified variables 1689 * and that the coefficient at data->level is non-zero. 1690 * Then we call construct_stride for further checks and the actual 1691 * construction of the CloogStride. 1692 */ 1693static int find_stride(__isl_take isl_constraint *c, void *user) 1694{ 1695 struct cloog_isl_find_stride_data *data; 1696 int n; 1697 isl_int v; 1698 1699 if (!isl_constraint_is_equality(c)) { 1700 isl_constraint_free(c); 1701 return 0; 1702 } 1703 1704 data = (struct cloog_isl_find_stride_data *)user; 1705 1706 if (data->stride) { 1707 isl_constraint_free(c); 1708 return 0; 1709 } 1710 1711 n = isl_constraint_dim(c, isl_dim_div); 1712 if (n == 0) { 1713 isl_constraint_free(c); 1714 return 0; 1715 } 1716 1717 isl_int_init(v); 1718 1719 isl_constraint_get_coefficient(c, isl_dim_set, data->level - 1, &v); 1720 if (!isl_int_is_zero(v)) 1721 data->stride = construct_stride(c, data->level); 1722 1723 isl_int_clear(v); 1724 1725 isl_constraint_free(c); 1726 1727 return 0; 1728} 1729 1730/* Check if the given list of domains has a common stride on the given level. 1731 * If so, return a pointer to a CloogStride object. If not, return NULL. 1732 * 1733 * We project out all later variables, take the union and compute 1734 * the affine hull of the union. Then we check the (equality) 1735 * constraints in this affine hull for imposing a stride. 1736 */ 1737CloogStride *cloog_domain_list_stride(CloogDomainList *list, int level) 1738{ 1739 struct cloog_isl_find_stride_data data = { level, NULL }; 1740 isl_set *set; 1741 isl_basic_set *aff; 1742 int first = level; 1743 int n; 1744 int r; 1745 1746 set = isl_set_from_cloog_domain(list->domain); 1747 n = isl_set_dim(set, isl_dim_set) - first; 1748 set = isl_set_project_out(isl_set_copy(set), isl_dim_set, first, n); 1749 1750 for (list = list->next; list; list = list->next) { 1751 isl_set *set_i = isl_set_from_cloog_domain(list->domain); 1752 n = isl_set_dim(set_i, isl_dim_set) - first; 1753 set_i = isl_set_project_out(isl_set_copy(set_i), 1754 isl_dim_set, first, n); 1755 set = isl_set_union(set, set_i); 1756 } 1757 aff = isl_set_affine_hull(set); 1758 1759 r = isl_basic_set_foreach_constraint(aff, &find_stride, &data); 1760 assert(r == 0); 1761 1762 isl_basic_set_free(aff); 1763 1764 return data.stride; 1765} 1766 1767struct cloog_can_unroll { 1768 int can_unroll; 1769 int level; 1770 isl_constraint *c; 1771 isl_set *set; 1772 isl_int *n; 1773}; 1774 1775 1776/* 1777 * Check if the given lower bound can be used for unrolling 1778 * and, if so, return the unrolling factor/trip count in *v. 1779 * If the lower bound involves any existentially quantified 1780 * variables, we currently punt. 1781 * Otherwise we compute the maximal value of (i - ceil(l) + 1), 1782 * with l the given lower bound and i the iterator identified by level. 1783 */ 1784static int is_valid_unrolling_lower_bound(struct cloog_can_unroll *ccu, 1785 __isl_keep isl_constraint *c, isl_int *v) 1786{ 1787 unsigned n_div; 1788 isl_aff *aff; 1789 enum isl_lp_result res; 1790 1791 n_div = isl_constraint_dim(c, isl_dim_div); 1792 if (isl_constraint_involves_dims(c, isl_dim_div, 0, n_div)) 1793 return 0; 1794 1795 aff = isl_constraint_get_bound(c, isl_dim_set, ccu->level - 1); 1796 aff = isl_aff_ceil(aff); 1797 aff = isl_aff_neg(aff); 1798 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, ccu->level - 1, 1); 1799 res = isl_set_max(ccu->set, aff, v); 1800 isl_aff_free(aff); 1801 1802 if (res == isl_lp_unbounded) 1803 return 0; 1804 1805 assert(res == isl_lp_ok); 1806 1807 cloog_int_add_ui(*v, *v, 1); 1808 1809 return 1; 1810} 1811 1812 1813/* Check if we can unroll based on the given constraint. 1814 * Only lower bounds can be used. 1815 * Record it if it turns out to be usable and if we haven't recorded 1816 * any other constraint already. 1817 */ 1818static int constraint_can_unroll(__isl_take isl_constraint *c, void *user) 1819{ 1820 struct cloog_can_unroll *ccu = (struct cloog_can_unroll *)user; 1821 isl_int v; 1822 isl_int count; 1823 1824 isl_int_init(v); 1825 isl_int_init(count); 1826 isl_constraint_get_coefficient(c, isl_dim_set, ccu->level - 1, &v); 1827 if (isl_int_is_pos(v) && 1828 is_valid_unrolling_lower_bound(ccu, c, &count) && 1829 (!ccu->c || isl_int_lt(count, *ccu->n))) { 1830 isl_constraint_free(ccu->c); 1831 ccu->c = isl_constraint_copy(c); 1832 isl_int_set(*ccu->n, count); 1833 } 1834 isl_int_clear(count); 1835 isl_int_clear(v); 1836 isl_constraint_free(c); 1837 1838 return 0; 1839} 1840 1841 1842/* Check if we can unroll the domain at the current level. 1843 * If the domain is a union, we cannot. Otherwise, we check the 1844 * constraints. 1845 */ 1846static int basic_set_can_unroll(__isl_take isl_basic_set *bset, void *user) 1847{ 1848 struct cloog_can_unroll *ccu = (struct cloog_can_unroll *)user; 1849 int r = 0; 1850 1851 if (ccu->c || !ccu->can_unroll) 1852 ccu->can_unroll = 0; 1853 else { 1854 bset = isl_basic_set_remove_redundancies(bset); 1855 r = isl_basic_set_foreach_constraint(bset, 1856 &constraint_can_unroll, ccu); 1857 } 1858 isl_basic_set_free(bset); 1859 return r; 1860} 1861 1862 1863/* Check if we can unroll the given domain at the given level, and 1864 * if so, return the single lower bound in *lb and an upper bound 1865 * on the number of iterations in *n. 1866 * If we cannot unroll, return 0 and set *lb to NULL. 1867 * 1868 * We can unroll, if we can identify a lower bound on level 1869 * such that the number of iterations is bounded by a constant. 1870 */ 1871int cloog_domain_can_unroll(CloogDomain *domain, int level, cloog_int_t *n, 1872 CloogConstraint **lb) 1873{ 1874 isl_set *set = isl_set_from_cloog_domain(domain); 1875 struct cloog_can_unroll ccu = { 1, level, NULL, set, n }; 1876 int r; 1877 1878 *lb = NULL; 1879 r = isl_set_foreach_basic_set(set, &basic_set_can_unroll, &ccu); 1880 assert(r == 0); 1881 if (!ccu.c) 1882 ccu.can_unroll = 0; 1883 if (!ccu.can_unroll) { 1884 isl_constraint_free(ccu.c); 1885 return 0; 1886 } 1887 1888 *lb = cloog_constraint_from_isl_constraint(ccu.c); 1889 1890 return ccu.can_unroll; 1891} 1892 1893 1894/* Fix the iterator i at the given level to l + o, 1895 * where l is prescribed by the constraint lb and o is equal to offset. 1896 * In particular, if lb is the constraint 1897 * 1898 * a i >= f(j) 1899 * 1900 * then l = ceil(f(j)/a). 1901 */ 1902CloogDomain *cloog_domain_fixed_offset(CloogDomain *domain, 1903 int level, CloogConstraint *lb, cloog_int_t offset) 1904{ 1905 isl_aff *aff; 1906 isl_set *set = isl_set_from_cloog_domain(domain); 1907 isl_constraint *c; 1908 isl_constraint *eq; 1909 1910 c = cloog_constraint_to_isl(lb); 1911 aff = isl_constraint_get_bound(c, isl_dim_set, level - 1); 1912 aff = isl_aff_ceil(aff); 1913 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, level - 1, -1); 1914 aff = isl_aff_add_constant(aff, offset); 1915 eq = isl_equality_from_aff(aff); 1916 set = isl_set_add_constraint(set, eq); 1917 1918 return cloog_domain_from_isl_set(set); 1919} 1920