1#include <stdlib.h> 2#include <stdio.h> 3#include <ctype.h> 4#include <cloog/isl/cloog.h> 5#include <cloog/isl/backend.h> 6#include <isl/aff.h> 7#include <isl/set.h> 8 9 10#define ALLOC(type) (type*)malloc(sizeof(type)) 11#define ALLOCN(type,n) (type*)malloc((n)*sizeof(type)) 12 13CloogConstraintSet *cloog_constraint_set_from_isl_basic_set(struct isl_basic_set *bset) 14{ 15 return (CloogConstraintSet *)bset; 16} 17 18CloogConstraint *cloog_constraint_from_isl_constraint(struct isl_constraint *constraint) 19{ 20 return (CloogConstraint *)constraint; 21} 22 23isl_constraint *cloog_constraint_to_isl(CloogConstraint *constraint) 24{ 25 return (isl_constraint *)constraint; 26} 27 28isl_basic_set *cloog_constraints_set_to_isl(CloogConstraintSet *constraints) 29{ 30 return (isl_basic_set *)constraints; 31} 32 33 34/****************************************************************************** 35 * Memory leaks hunting * 36 ******************************************************************************/ 37 38 39 40void cloog_constraint_set_free(CloogConstraintSet *constraints) 41{ 42 isl_basic_set_free(cloog_constraints_set_to_isl(constraints)); 43} 44 45 46int cloog_constraint_set_contains_level(CloogConstraintSet *constraints, 47 int level, int nb_parameters) 48{ 49 isl_basic_set *bset; 50 bset = cloog_constraints_set_to_isl(constraints); 51 return isl_basic_set_dim(bset, isl_dim_set) >= level; 52} 53 54struct cloog_isl_dim { 55 enum isl_dim_type type; 56 int pos; 57}; 58 59static struct cloog_isl_dim basic_set_cloog_dim_to_isl_dim( 60 __isl_keep isl_basic_set *bset, int pos) 61{ 62 enum isl_dim_type types[] = { isl_dim_set, isl_dim_div, isl_dim_param }; 63 int i; 64 struct cloog_isl_dim ci_dim; 65 66 for (i = 0; i < 3; ++i) { 67 unsigned dim = isl_basic_set_dim(bset, types[i]); 68 if (pos < dim) { 69 ci_dim.type = types[i]; 70 ci_dim.pos = pos; 71 return ci_dim; 72 } 73 pos -= dim; 74 } 75 assert(0); 76} 77 78static struct cloog_isl_dim set_cloog_dim_to_isl_dim( 79 CloogConstraintSet *constraints, int pos) 80{ 81 isl_basic_set *bset; 82 83 bset = cloog_constraints_set_to_isl(constraints); 84 return basic_set_cloog_dim_to_isl_dim(bset, pos); 85} 86 87/* Check if the variable at position level is defined by an 88 * equality. If so, return the row number. Otherwise, return -1. 89 */ 90CloogConstraint *cloog_constraint_set_defining_equality( 91 CloogConstraintSet *constraints, int level) 92{ 93 struct isl_constraint *c; 94 struct cloog_isl_dim dim; 95 isl_basic_set *bset; 96 97 bset = cloog_constraints_set_to_isl(constraints); 98 dim = set_cloog_dim_to_isl_dim(constraints, level - 1); 99 if (isl_basic_set_has_defining_equality(bset, dim.type, dim.pos, &c)) 100 return cloog_constraint_from_isl_constraint(c); 101 else 102 return NULL; 103} 104 105 106struct cloog_isl_other { 107 int level; 108 int found; 109 isl_constraint *u; 110 isl_constraint *l; 111}; 112 113 114/* Set other->found to 1 if the given constraint involves other->level 115 * and is different from other->u and other->l. 116 */ 117static int check_other_constraint(__isl_take isl_constraint *c, void *user) 118{ 119 struct cloog_isl_other *other = user; 120 CloogConstraint *cc; 121 122 if (!isl_constraint_is_equal(c, other->l) && 123 !isl_constraint_is_equal(c, other->u)) { 124 cc = cloog_constraint_from_isl_constraint(c); 125 if (cloog_constraint_involves(cc, other->level - 1)) 126 other->found = 1; 127 } 128 129 isl_constraint_free(c); 130 131 return other->found ? -1 : 0; 132} 133 134 135/* Check if the variable (e) at position level is defined by a 136 * pair of inequalities 137 * <a, i> + -m e + <b, p> + k1 >= 0 138 * <-a, i> + m e + <-b, p> + k2 >= 0 139 * with 0 <= k1 + k2 < m 140 * If so return the row number of the upper bound and set *lower 141 * to the row number of the lower bound. If not, return -1. 142 * 143 * If the variable at position level occurs in any other constraint, 144 * then we currently return -1. The modulo guard that we would generate 145 * would still be correct, but we would also need to generate 146 * guards corresponding to the other constraints, and this has not 147 * been implemented yet. 148 */ 149CloogConstraint *cloog_constraint_set_defining_inequalities( 150 CloogConstraintSet *constraints, 151 int level, CloogConstraint **lower, int nb_par) 152{ 153 struct isl_constraint *u; 154 struct isl_constraint *l; 155 struct cloog_isl_dim dim; 156 struct isl_basic_set *bset; 157 struct cloog_isl_other other; 158 159 bset = cloog_constraints_set_to_isl(constraints); 160 dim = set_cloog_dim_to_isl_dim(constraints, level - 1); 161 if (!isl_basic_set_has_defining_inequalities(bset, dim.type, dim.pos, 162 &l, &u)) 163 return cloog_constraint_invalid(); 164 165 other.l = l; 166 other.u = u; 167 other.found = 0; 168 other.level = level; 169 isl_basic_set_foreach_constraint(bset, &check_other_constraint, &other); 170 if (other.found) { 171 isl_constraint_free(l); 172 isl_constraint_free(u); 173 *lower = NULL; 174 return NULL; 175 } 176 *lower = cloog_constraint_from_isl_constraint(l); 177 return cloog_constraint_from_isl_constraint(u); 178} 179 180int cloog_constraint_set_total_dimension(CloogConstraintSet *constraints) 181{ 182 isl_basic_set *bset; 183 bset = cloog_constraints_set_to_isl(constraints); 184 return isl_basic_set_total_dim(bset); 185} 186 187int cloog_constraint_set_n_iterators(CloogConstraintSet *constraints, int n_par) 188{ 189 isl_basic_set *bset; 190 bset = cloog_constraints_set_to_isl(constraints); 191 return isl_basic_set_dim(bset, isl_dim_set); 192} 193 194 195/****************************************************************************** 196 * Equalities spreading functions * 197 ******************************************************************************/ 198 199 200/* Equalities are stored inside a Matrix data structure called "equal". 201 * This matrix has (nb_scattering + nb_iterators + 1) rows (i.e. total 202 * dimensions + 1, the "+ 1" is because a statement can be included inside an 203 * external loop without iteration domain), and (nb_scattering + nb_iterators + 204 * nb_parameters + 2) columns (all unknowns plus the scalar plus the equality 205 * type). The ith row corresponds to the equality "= 0" for the ith dimension 206 * iterator. The first column gives the equality type (0: no equality, then 207 * EQTYPE_* -see pprint.h-). At each recursion of pprint, if an equality for 208 * the current level is found, the corresponding row is updated. Then the 209 * equality if it exists is used to simplify expressions (e.g. if we have 210 * "i+1" while we know that "i=2", we simplify it in "3"). At the end of 211 * the pprint call, the corresponding row is reset to zero. 212 */ 213 214CloogEqualities *cloog_equal_alloc(int n, int nb_levels, int nb_parameters) 215{ 216 int i; 217 CloogEqualities *equal = ALLOC(CloogEqualities); 218 219 equal->total_dim = nb_levels - 1 + nb_parameters; 220 equal->n = n; 221 equal->constraints = ALLOCN(isl_constraint *, n); 222 equal->types = ALLOCN(int, n); 223 for (i = 0; i < n; ++i) { 224 equal->constraints[i] = NULL; 225 equal->types[i] = EQTYPE_NONE; 226 } 227 return equal; 228} 229 230int cloog_equal_total_dimension(CloogEqualities *equal) 231{ 232 return equal->total_dim; 233} 234 235void cloog_equal_free(CloogEqualities *equal) 236{ 237 int i; 238 239 for (i = 0; i < equal->n; ++i) 240 isl_constraint_free(equal->constraints[i]); 241 free(equal->constraints); 242 free(equal->types); 243 free(equal); 244} 245 246int cloog_equal_count(CloogEqualities *equal) 247{ 248 return equal->n; 249} 250 251 252/** 253 * cloog_constraint_equal_type function : 254 * This function returns the type of the equality in the constraint (line) of 255 * (constraints) for the element (level). An equality is 'constant' iff all 256 * other factors are null except the constant one. It is a 'pure item' iff 257 * it is equal or opposite to a single variable or parameter. 258 * Otherwise it is an 'affine expression'. 259 * For instance: 260 * i = -13 is constant, i = j, j = -M are pure items, 261 * j = 2*M, i = j+1, 2*j = M are affine expressions. 262 * 263 * - constraints is the matrix of constraints, 264 * - level is the column number in equal of the element which is 'equal to', 265 */ 266static int cloog_constraint_equal_type(CloogConstraint *cc, int level) 267{ 268 int i; 269 isl_int c; 270 int type = EQTYPE_NONE; 271 struct isl_constraint *constraint = cloog_constraint_to_isl(cc); 272 273 isl_int_init(c); 274 isl_constraint_get_constant(constraint, &c); 275 if (!isl_int_is_zero(c)) 276 type = EQTYPE_CONSTANT; 277 isl_constraint_get_coefficient(constraint, isl_dim_set, level - 1, &c); 278 if (!isl_int_is_one(c) && !isl_int_is_negone(c)) 279 type = EQTYPE_EXAFFINE; 280 for (i = 0; i < isl_constraint_dim(constraint, isl_dim_param); ++i) { 281 isl_constraint_get_coefficient(constraint, isl_dim_param, i, &c); 282 if (isl_int_is_zero(c)) 283 continue; 284 if ((!isl_int_is_one(c) && !isl_int_is_negone(c)) || 285 type != EQTYPE_NONE) { 286 type = EQTYPE_EXAFFINE; 287 break; 288 } 289 type = EQTYPE_PUREITEM; 290 } 291 for (i = 0; i < isl_constraint_dim(constraint, isl_dim_set); ++i) { 292 if (i == level - 1) 293 continue; 294 isl_constraint_get_coefficient(constraint, isl_dim_set, i, &c); 295 if (isl_int_is_zero(c)) 296 continue; 297 if ((!isl_int_is_one(c) && !isl_int_is_negone(c)) || 298 type != EQTYPE_NONE) { 299 type = EQTYPE_EXAFFINE; 300 break; 301 } 302 type = EQTYPE_PUREITEM; 303 } 304 for (i = 0; i < isl_constraint_dim(constraint, isl_dim_div); ++i) { 305 isl_constraint_get_coefficient(constraint, isl_dim_div, i, &c); 306 if (isl_int_is_zero(c)) 307 continue; 308 if ((!isl_int_is_one(c) && !isl_int_is_negone(c)) || 309 type != EQTYPE_NONE) { 310 type = EQTYPE_EXAFFINE; 311 break; 312 } 313 type = EQTYPE_PUREITEM; 314 } 315 isl_int_clear(c); 316 317 if (type == EQTYPE_NONE) 318 type = EQTYPE_CONSTANT; 319 320 return type; 321} 322 323 324int cloog_equal_type(CloogEqualities *equal, int level) 325{ 326 return equal->types[level-1]; 327} 328 329 330/** 331 * cloog_equal_add function: 332 * This function updates the row (level-1) of the equality matrix (equal) with 333 * the row that corresponds to the row (line) of the matrix (matrix). 334 * - equal is the matrix of equalities, 335 * - matrix is the matrix of constraints, 336 * - level is the column number in matrix of the element which is 'equal to', 337 * - line is the line number in matrix of the constraint we want to study, 338 * - the infos structure gives the user all options on code printing and more. 339 ** 340 * line is set to an invalid constraint for equalities that CLooG itself has 341 * discovered because the lower and upper bound of a loop happened to be equal. 342 * This situation shouldn't happen in the isl port since isl should 343 * have found the equality itself. 344 */ 345void cloog_equal_add(CloogEqualities *equal, CloogConstraintSet *matrix, 346 int level, CloogConstraint *line, int nb_par) 347{ 348 isl_constraint *c; 349 assert(cloog_constraint_is_valid(line)); 350 351 equal->types[level-1] = cloog_constraint_equal_type(line, level); 352 c = cloog_constraint_to_isl(line); 353 equal->constraints[level - 1] = isl_constraint_copy(c); 354} 355 356 357/** 358 * cloog_equal_del function : 359 * This function reset the equality corresponding to the iterator (level) 360 * in the equality matrix (equal). 361 * - July 2nd 2002: first version. 362 */ 363void cloog_equal_del(CloogEqualities *equal, int level) 364{ 365 equal->types[level-1] = EQTYPE_NONE; 366 isl_constraint_free(equal->constraints[level - 1]); 367 equal->constraints[level-1] = NULL; 368} 369 370 371 372/****************************************************************************** 373 * Processing functions * 374 ******************************************************************************/ 375 376/** 377 * Function cloog_constraint_set_normalize: 378 * This function will modify the constraint system in such a way that when 379 * there is an equality depending on the element at level 'level', there are 380 * no more (in)equalities depending on this element. 381 * 382 * The simplified form of isl automatically satisfies this condition. 383 */ 384void cloog_constraint_set_normalize(CloogConstraintSet *matrix, int level) 385{ 386} 387 388 389 390/** 391 * cloog_constraint_set_copy function: 392 * this functions builds and returns a "hard copy" (not a pointer copy) of a 393 * CloogConstraintSet data structure. 394 */ 395CloogConstraintSet *cloog_constraint_set_copy(CloogConstraintSet *constraints) 396{ 397 isl_basic_set *bset; 398 bset = cloog_constraints_set_to_isl(constraints); 399 return cloog_constraint_set_from_isl_basic_set(isl_basic_set_dup(bset)); 400} 401 402 403/** 404 * cloog_constraint_set_simplify function: 405 * this function simplify all constraints inside the matrix "matrix" thanks to 406 * an equality matrix "equal" that gives for some elements of the affine 407 * constraint an equality with other elements, preferably constants. 408 * For instance, if a row of the matrix contains i+j+3>=0 and the equality 409 * matrix gives i=n and j=2, the constraint is simplified to n+3>=0. The 410 * simplified constraints are returned back inside a new simplified matrix. 411 * - matrix is the set of constraints to simplify, 412 * - equal is the matrix of equalities, 413 * - level is a level we don't want to simplify (-1 if none), 414 * - nb_par is the number of parameters of the program. 415 ** 416 * isl should have performed these simplifications already in isl_set_gist. 417 */ 418CloogConstraintSet *cloog_constraint_set_simplify(CloogConstraintSet *matrix, 419 CloogEqualities *equal, int level, int nb_par) 420{ 421 return cloog_constraint_set_copy(matrix); 422} 423 424 425static struct cloog_isl_dim constraint_cloog_dim_to_isl_dim( 426 CloogConstraint *constraint, int pos) 427{ 428 enum isl_dim_type types[] = { isl_dim_set, isl_dim_div, isl_dim_param }; 429 int i; 430 struct cloog_isl_dim ci_dim; 431 432 for (i = 0; i < 3; ++i) { 433 isl_constraint *c = cloog_constraint_to_isl(constraint); 434 unsigned dim = isl_constraint_dim(c, types[i]); 435 if (pos < dim) { 436 ci_dim.type = types[i]; 437 ci_dim.pos = pos; 438 return ci_dim; 439 } 440 pos -= dim; 441 } 442 assert(0); 443} 444 445static struct clast_expr *div_expr(CloogConstraint *constraint, int pos, 446 CloogNames *names) 447{ 448 int i, nb_elts; 449 unsigned dim = cloog_constraint_total_dimension(constraint); 450 cloog_int_t c; 451 struct clast_reduction *r; 452 struct clast_expr *e = NULL; 453 isl_aff *div; 454 455 div = isl_constraint_get_div(cloog_constraint_to_isl(constraint), pos); 456 457 cloog_int_init(c); 458 for (i = 0, nb_elts = 0; i < dim; ++i) { 459 struct cloog_isl_dim dim; 460 461 dim = constraint_cloog_dim_to_isl_dim(constraint, i); 462 if (dim.type == isl_dim_set) 463 dim.type = isl_dim_in; 464 isl_aff_get_coefficient(div, dim.type, dim.pos, &c); 465 if (!cloog_int_is_zero(c)) 466 ++nb_elts; 467 } 468 isl_aff_get_constant(div, &c); 469 if (!cloog_int_is_zero(c)) 470 ++nb_elts; 471 472 r = new_clast_reduction(clast_red_sum, nb_elts); 473 for (i = 0, nb_elts = 0; i < dim; ++i) { 474 struct clast_expr *v; 475 struct cloog_isl_dim dim; 476 477 dim = constraint_cloog_dim_to_isl_dim(constraint, i); 478 if (dim.type == isl_dim_set) 479 dim.type = isl_dim_in; 480 isl_aff_get_coefficient(div, dim.type, dim.pos, &c); 481 if (cloog_int_is_zero(c)) 482 continue; 483 484 v = cloog_constraint_variable_expr(constraint, 1 + i, names); 485 486 r->elts[nb_elts++] = &new_clast_term(c, v)->expr; 487 } 488 isl_aff_get_constant(div, &c); 489 if (!cloog_int_is_zero(c)) 490 r->elts[nb_elts++] = &new_clast_term(c, NULL)->expr; 491 492 isl_aff_get_denominator(div, &c); 493 e = &new_clast_binary(clast_bin_fdiv, &r->expr, c)->expr; 494 495 cloog_int_clear(c); 496 497 isl_aff_free(div); 498 499 return e; 500} 501 502/** 503 * Return clast_expr corresponding to the variable "level" (1 based) in 504 * the given constraint. 505 */ 506struct clast_expr *cloog_constraint_variable_expr(CloogConstraint *constraint, 507 int level, CloogNames *names) 508{ 509 struct cloog_isl_dim dim; 510 const char *name; 511 512 assert(constraint); 513 514 dim = constraint_cloog_dim_to_isl_dim(constraint, level - 1); 515 if (dim.type == isl_dim_div) 516 return div_expr(constraint, dim.pos, names); 517 518 if (dim.type == isl_dim_set) 519 name = cloog_names_name_at_level(names, level); 520 else 521 name = names->parameters[dim.pos]; 522 523 return &new_clast_name(name)->expr; 524} 525 526 527/** 528 * Return true if constraint c involves variable v (zero-based). 529 */ 530int cloog_constraint_involves(CloogConstraint *constraint, int v) 531{ 532 isl_int c; 533 int res; 534 535 isl_int_init(c); 536 cloog_constraint_coefficient_get(constraint, v, &c); 537 res = !isl_int_is_zero(c); 538 isl_int_clear(c); 539 return res; 540} 541 542int cloog_constraint_is_lower_bound(CloogConstraint *constraint, int v) 543{ 544 isl_int c; 545 int res; 546 547 isl_int_init(c); 548 cloog_constraint_coefficient_get(constraint, v, &c); 549 res = isl_int_is_pos(c); 550 isl_int_clear(c); 551 return res; 552} 553 554int cloog_constraint_is_upper_bound(CloogConstraint *constraint, int v) 555{ 556 isl_int c; 557 int res; 558 559 isl_int_init(c); 560 cloog_constraint_coefficient_get(constraint, v, &c); 561 res = isl_int_is_neg(c); 562 isl_int_clear(c); 563 return res; 564} 565 566int cloog_constraint_is_equality(CloogConstraint *constraint) 567{ 568 return isl_constraint_is_equality(cloog_constraint_to_isl(constraint)); 569} 570 571CloogConstraintSet *cloog_constraint_set_drop_constraint( 572 CloogConstraintSet *constraints, CloogConstraint *constraint) 573{ 574 isl_basic_set *bset; 575 isl_constraint *c; 576 577 bset = cloog_constraints_set_to_isl(constraints); 578 c = cloog_constraint_to_isl(cloog_constraint_copy(constraint)); 579 bset = isl_basic_set_drop_constraint(bset, c); 580 return cloog_constraint_set_from_isl_basic_set(bset); 581} 582 583void cloog_constraint_coefficient_get(CloogConstraint *constraint, 584 int var, cloog_int_t *val) 585{ 586 struct cloog_isl_dim dim; 587 isl_constraint *c; 588 589 if (!constraint) 590 return; 591 592 dim = constraint_cloog_dim_to_isl_dim(constraint, var); 593 c = cloog_constraint_to_isl(constraint); 594 isl_constraint_get_coefficient(c, dim.type, dim.pos, val); 595} 596 597void cloog_constraint_coefficient_set(CloogConstraint *constraint, 598 int var, cloog_int_t val) 599{ 600 struct cloog_isl_dim dim; 601 isl_constraint *c; 602 603 assert(constraint); 604 605 dim = constraint_cloog_dim_to_isl_dim(constraint, var); 606 c = cloog_constraint_to_isl(constraint); 607 isl_constraint_set_coefficient(c, dim.type, dim.pos, val); 608} 609 610void cloog_constraint_constant_get(CloogConstraint *constraint, cloog_int_t *val) 611{ 612 isl_constraint_get_constant(cloog_constraint_to_isl(constraint), val); 613} 614 615/** 616 * Copy the coefficient of constraint c into dst in PolyLib order, 617 * i.e., first the coefficients of the variables, then the coefficients 618 * of the parameters and finally the constant. 619 */ 620void cloog_constraint_copy_coefficients(CloogConstraint *constraint, 621 cloog_int_t *dst) 622{ 623 int i; 624 unsigned dim; 625 626 dim = cloog_constraint_total_dimension(constraint); 627 628 for (i = 0; i < dim; ++i) 629 cloog_constraint_coefficient_get(constraint, i, dst+i); 630 cloog_constraint_constant_get(constraint, dst+dim); 631} 632 633CloogConstraint *cloog_constraint_invalid(void) 634{ 635 return NULL; 636} 637 638int cloog_constraint_is_valid(CloogConstraint *constraint) 639{ 640 return constraint != NULL; 641} 642 643int cloog_constraint_total_dimension(CloogConstraint *constraint) 644{ 645 isl_constraint *c; 646 c = cloog_constraint_to_isl(constraint); 647 return isl_constraint_dim(c, isl_dim_all); 648} 649 650 651/** 652 * Check whether there is any need for the constraint "upper" on 653 * "level" to get reduced. 654 * In case of the isl backend, there should be no need to do so 655 * if the level corresponds to an existentially quantified variable. 656 * Moreover, the way reduction is performed does not work for such 657 * variables since its position might chance during the construction 658 * of a set for reduction. 659 */ 660int cloog_constraint_needs_reduction(CloogConstraint *upper, int level) 661{ 662 isl_basic_set *bset; 663 isl_constraint *c; 664 struct cloog_isl_dim dim; 665 666 c = cloog_constraint_to_isl(upper); 667 bset = isl_basic_set_from_constraint(isl_constraint_copy(c)); 668 dim = basic_set_cloog_dim_to_isl_dim(bset, level - 1); 669 isl_basic_set_free(bset); 670 671 return dim.type == isl_dim_set; 672} 673 674 675/** 676 * Create a CloogConstraintSet containing enough information to perform 677 * a reduction on the upper equality (in this case lower is an invalid 678 * CloogConstraint) or the pair of inequalities upper and lower 679 * from within insert_modulo_guard. 680 * In the isl backend, we return a CloogConstraintSet containing both 681 * bounds, as the stride may change during the reduction and we may 682 * need to recompute the bound on the modulo expression. 683 */ 684CloogConstraintSet *cloog_constraint_set_for_reduction(CloogConstraint *upper, 685 CloogConstraint *lower) 686{ 687 struct isl_basic_set *bset; 688 isl_constraint *c; 689 690 c = cloog_constraint_to_isl(upper); 691 bset = isl_basic_set_from_constraint(isl_constraint_copy(c)); 692 if (cloog_constraint_is_valid(lower)) { 693 c = cloog_constraint_to_isl(lower); 694 bset = isl_basic_set_add_constraint(bset, 695 isl_constraint_copy(c)); 696 } 697 return cloog_constraint_set_from_isl_basic_set(bset); 698} 699 700 701static int add_constant_term(CloogConstraint *c, void *user) 702{ 703 isl_int *bound = (isl_int *)user; 704 isl_int v; 705 706 isl_int_init(v); 707 708 cloog_constraint_constant_get(c, &v); 709 isl_int_add(*bound, *bound, v); 710 711 isl_int_clear(v); 712 713 return 0; 714} 715 716 717/* Return an isl_basic_set representation of the equality stored 718 * at position i in the given CloogEqualities. 719 */ 720static __isl_give isl_basic_set *equality_to_basic_set(CloogEqualities *equal, 721 int i) 722{ 723 isl_constraint *c; 724 isl_basic_set *bset; 725 unsigned nparam; 726 unsigned nvar; 727 728 c = isl_constraint_copy(equal->constraints[i]); 729 bset = isl_basic_set_from_constraint(c); 730 nparam = isl_basic_set_dim(bset, isl_dim_param); 731 nvar = isl_basic_set_dim(bset, isl_dim_set); 732 bset = isl_basic_set_add_dims(bset, isl_dim_set, 733 equal->total_dim - (nparam + nvar)); 734 return bset; 735} 736 737/** 738 * Reduce the modulo guard expressed by "constraints" using equalities 739 * found in outer nesting levels (stored in "equal"). 740 * The modulo guard may be an equality or a pair of inequalities. 741 * In case of a pair of inequalities, *bound contains the bound on the 742 * corresponding modulo expression. If any reduction is performed 743 * then this bound is recomputed. 744 * 745 * "level" may not correspond to an existentially quantified variable. 746 * 747 * We first check if there are any equalities we can use. If not, 748 * there is again nothing to reduce. 749 * For the actual reduction, we use isl_basic_set_gist, but this 750 * function will only perform the reduction we want here if the 751 * the variable that imposes the modulo constraint has been projected 752 * out (i.e., turned into an existentially quantified variable). 753 * After the call to isl_basic_set_gist, we need to move the 754 * existential variable back into the position where the calling 755 * function expects it (assuming there are any constraints left). 756 * We do this by adding an equality between the given dimension and 757 * the existentially quantified variable. 758 * 759 * If there are no existentially quantified variables left, then 760 * we don't need to add this equality. 761 * If, on the other hand, the resulting basic set involves more 762 * than one existentially quantified variable, then the caller 763 * will not be able to handle the result, so we just return the 764 * original input instead. 765 */ 766CloogConstraintSet *cloog_constraint_set_reduce(CloogConstraintSet *constraints, 767 int level, CloogEqualities *equal, int nb_par, cloog_int_t *bound) 768{ 769 int j; 770 isl_space *idim; 771 struct isl_basic_set *eq; 772 struct isl_basic_map *id; 773 struct cloog_isl_dim dim; 774 struct isl_constraint *c; 775 unsigned constraints_dim; 776 unsigned n_div; 777 isl_basic_set *bset, *orig; 778 779 bset = cloog_constraints_set_to_isl(constraints); 780 orig = isl_basic_set_copy(bset); 781 dim = set_cloog_dim_to_isl_dim(constraints, level - 1); 782 assert(dim.type == isl_dim_set); 783 784 eq = NULL; 785 for (j = 0; j < level - 1; ++j) { 786 isl_basic_set *bset_j; 787 if (equal->types[j] != EQTYPE_EXAFFINE) 788 continue; 789 bset_j = equality_to_basic_set(equal, j); 790 if (!eq) 791 eq = bset_j; 792 else 793 eq = isl_basic_set_intersect(eq, bset_j); 794 } 795 if (!eq) { 796 isl_basic_set_free(orig); 797 return cloog_constraint_set_from_isl_basic_set(bset); 798 } 799 800 idim = isl_space_map_from_set(isl_basic_set_get_space(bset)); 801 id = isl_basic_map_identity(idim); 802 id = isl_basic_map_remove_dims(id, isl_dim_out, dim.pos, 1); 803 bset = isl_basic_set_apply(bset, isl_basic_map_copy(id)); 804 bset = isl_basic_set_apply(bset, isl_basic_map_reverse(id)); 805 806 constraints_dim = isl_basic_set_dim(bset, isl_dim_set); 807 eq = isl_basic_set_remove_dims(eq, isl_dim_set, constraints_dim, 808 isl_basic_set_dim(eq, isl_dim_set) - constraints_dim); 809 bset = isl_basic_set_gist(bset, eq); 810 n_div = isl_basic_set_dim(bset, isl_dim_div); 811 if (n_div > 1) { 812 isl_basic_set_free(bset); 813 return cloog_constraint_set_from_isl_basic_set(orig); 814 } 815 if (n_div < 1) { 816 isl_basic_set_free(orig); 817 return cloog_constraint_set_from_isl_basic_set(bset); 818 } 819 820 c = isl_equality_alloc(isl_basic_set_get_local_space(bset)); 821 c = isl_constraint_set_coefficient_si(c, isl_dim_div, 0, 1); 822 c = isl_constraint_set_coefficient_si(c, isl_dim_set, dim.pos, -1); 823 bset = isl_basic_set_add_constraint(bset, c); 824 825 isl_int_set_si(*bound, 0); 826 constraints = cloog_constraint_set_from_isl_basic_set(bset); 827 cloog_constraint_set_foreach_constraint(constraints, 828 add_constant_term, bound); 829 830 isl_basic_set_free(orig); 831 return cloog_constraint_set_from_isl_basic_set(bset); 832} 833 834CloogConstraint *cloog_constraint_copy(CloogConstraint *constraint) 835{ 836 return cloog_constraint_from_isl_constraint( 837 isl_constraint_copy(cloog_constraint_to_isl(constraint))); 838} 839 840void cloog_constraint_release(CloogConstraint *constraint) 841{ 842 isl_constraint_free(cloog_constraint_to_isl(constraint)); 843} 844 845struct cloog_isl_foreach { 846 int (*fn)(CloogConstraint *constraint, void *user); 847 void *user; 848}; 849 850static int cloog_isl_foreach_cb(__isl_take isl_constraint *c, void *user) 851{ 852 struct cloog_isl_foreach *data = (struct cloog_isl_foreach *)user; 853 int ret; 854 855 if (isl_constraint_is_div_constraint(c)) { 856 isl_constraint_free(c); 857 return 0; 858 } 859 860 ret = data->fn(cloog_constraint_from_isl_constraint(c), data->user); 861 862 isl_constraint_free(c); 863 864 return ret; 865} 866 867int cloog_constraint_set_foreach_constraint(CloogConstraintSet *constraints, 868 int (*fn)(CloogConstraint *constraint, void *user), void *user) 869{ 870 struct cloog_isl_foreach data = { fn, user }; 871 isl_basic_set *bset; 872 873 bset = cloog_constraints_set_to_isl(constraints); 874 return isl_basic_set_foreach_constraint(bset, 875 cloog_isl_foreach_cb, &data); 876} 877 878CloogConstraint *cloog_equal_constraint(CloogEqualities *equal, int j) 879{ 880 isl_constraint *c; 881 882 c = isl_constraint_copy(equal->constraints[j]); 883 return cloog_constraint_from_isl_constraint(c); 884} 885 886/* Given a stride constraint on iterator i (specified by level) of the form 887 * 888 * i = f(outer iterators) + stride * f(existentials) 889 * 890 * extract f as an isl_aff. 891 */ 892static isl_aff *extract_stride_offset(__isl_keep isl_constraint *c, 893 int level, CloogStride *stride) 894{ 895 int i; 896 isl_space *dim = isl_constraint_get_space(c); 897 isl_local_space *ls = isl_local_space_from_space(dim); 898 isl_aff *offset = isl_aff_zero_on_domain(ls); 899 isl_int u; 900 unsigned nparam, nvar; 901 902 isl_int_init(u); 903 904 nparam = isl_constraint_dim(c, isl_dim_param); 905 nvar = isl_constraint_dim(c, isl_dim_set); 906 907 for (i = 0; i < nparam; ++i) { 908 isl_constraint_get_coefficient(c, isl_dim_param, i, &u); 909 isl_int_mul(u, u, stride->factor); 910 offset = isl_aff_set_coefficient(offset, isl_dim_param, i, u); 911 } 912 for (i = 0; i < nvar; ++i) { 913 if (i == level - 1) 914 continue; 915 isl_constraint_get_coefficient(c, isl_dim_set, i, &u); 916 isl_int_mul(u, u, stride->factor); 917 offset = isl_aff_set_coefficient(offset, isl_dim_in, i, u); 918 } 919 isl_constraint_get_constant(c, &u); 920 isl_int_mul(u, u, stride->factor); 921 offset = isl_aff_set_constant(offset, u); 922 923 isl_int_clear(u); 924 925 return offset; 926} 927 928/* Update the given lower bound on level such that it satisfies the stride 929 * constraint. The computation performed here is essentially the same 930 * as that performed in constraint_stride_lower_c. 931 * 932 * We update the constraint 933 * 934 * a i + f >= 0 935 * 936 * to 937 * 938 * i >= s * ceil((-f/a - d)/s) + d 939 * 940 * with s the stride and d the offset encoded in the stride constraint. 941 */ 942CloogConstraint *cloog_constraint_stride_lower_bound(CloogConstraint *c, 943 int level, CloogStride *stride) 944{ 945 isl_constraint *stride_c = cloog_constraint_to_isl(stride->constraint); 946 isl_constraint *bound = cloog_constraint_to_isl(c); 947 isl_aff *offset; 948 isl_aff *lower; 949 950 lower = isl_constraint_get_bound(bound, isl_dim_set, level - 1); 951 isl_constraint_free(bound); 952 953 offset = extract_stride_offset(stride_c, level, stride); 954 955 lower = isl_aff_sub(lower, isl_aff_copy(offset)); 956 lower = isl_aff_scale_down(lower, stride->stride); 957 lower = isl_aff_ceil(lower); 958 lower = isl_aff_scale(lower, stride->stride); 959 lower = isl_aff_add(lower, offset); 960 lower = isl_aff_neg(lower); 961 lower = isl_aff_add_coefficient_si(lower, isl_dim_in, level - 1, 1); 962 963 bound = isl_inequality_from_aff(lower); 964 965 return cloog_constraint_from_isl_constraint(bound); 966} 967