1#include <stdlib.h> 2#include <string.h> 3#include <assert.h> 4#include "../include/cloog/cloog.h" 5 6#define ALLOC(type) (type*)malloc(sizeof(type)) 7#define ALLOCN(type,n) (type*)malloc((n)*sizeof(type)) 8 9/** 10 * CloogInfos structure: 11 * this structure contains all the informations necessary for pretty printing, 12 * they come from the original CloogProgram structure (language, names), from 13 * genereral options (options) or are built only for pretty printing (stride). 14 * This structure is mainly there to reduce the number of function parameters, 15 * since most pprint.c functions need most of its field. 16 */ 17struct clooginfos { 18 CloogState *state; /**< State. */ 19 CloogStride **stride; 20 int stride_level; /**< Number of valid entries in stride array. */ 21 int nb_scattdims ; /**< Scattering dimension number. */ 22 int * scaldims ; /**< Boolean array saying whether a given 23 * scattering dimension is scalar or not. 24 */ 25 CloogNames * names ; /**< Names of iterators and parameters. */ 26 CloogOptions * options ; /**< Options on CLooG's behaviour. */ 27 CloogEqualities *equal; /**< Matrix of equalities. */ 28} ; 29 30typedef struct clooginfos CloogInfos ; 31 32static int clast_expr_cmp(struct clast_expr *e1, struct clast_expr *e2); 33static int clast_term_cmp(struct clast_term *t1, struct clast_term *t2); 34static int clast_binary_cmp(struct clast_binary *b1, struct clast_binary *b2); 35static int clast_reduction_cmp(struct clast_reduction *r1, 36 struct clast_reduction *r2); 37 38static struct clast_expr *clast_expr_copy(struct clast_expr *e); 39 40static int clast_equal_add(CloogEqualities *equal, 41 CloogConstraintSet *constraints, 42 int level, CloogConstraint *constraint, 43 CloogInfos *infos); 44 45static struct clast_stmt *clast_equal(int level, CloogInfos *infos); 46static struct clast_expr *clast_minmax(CloogConstraintSet *constraints, 47 int level, int max, int guard, 48 int lower_bound, int no_earlier, 49 CloogInfos *infos); 50static void insert_guard(CloogConstraintSet *constraints, int level, 51 struct clast_stmt ***next, CloogInfos *infos); 52static int insert_modulo_guard(CloogConstraint *upper, 53 CloogConstraint *lower, int level, 54 struct clast_stmt ***next, CloogInfos *infos); 55static int insert_equation(CloogDomain *domain, CloogConstraint *upper, 56 CloogConstraint *lower, int level, 57 struct clast_stmt ***next, CloogInfos *infos); 58static int insert_for(CloogDomain *domain, CloogConstraintSet *constraints, 59 int level, int otl, struct clast_stmt ***next, 60 CloogInfos *infos); 61static void insert_block(CloogDomain *domain, CloogBlock *block, int level, 62 struct clast_stmt ***next, CloogInfos *infos); 63static void insert_loop(CloogLoop * loop, int level, 64 struct clast_stmt ***next, CloogInfos *infos); 65 66 67struct clast_name *new_clast_name(const char *name) 68{ 69 struct clast_name *n = malloc(sizeof(struct clast_name)); 70 n->expr.type = clast_expr_name; 71 n->name = name; 72 return n; 73} 74 75struct clast_term *new_clast_term(cloog_int_t c, struct clast_expr *v) 76{ 77 struct clast_term *t = malloc(sizeof(struct clast_term)); 78 t->expr.type = clast_expr_term; 79 cloog_int_init(t->val); 80 cloog_int_set(t->val, c); 81 t->var = v; 82 return t; 83} 84 85struct clast_binary *new_clast_binary(enum clast_bin_type t, 86 struct clast_expr *lhs, cloog_int_t rhs) 87{ 88 struct clast_binary *b = malloc(sizeof(struct clast_binary)); 89 b->expr.type = clast_expr_bin; 90 b->type = t; 91 b->LHS = lhs; 92 cloog_int_init(b->RHS); 93 cloog_int_set(b->RHS, rhs); 94 return b; 95} 96 97struct clast_reduction *new_clast_reduction(enum clast_red_type t, int n) 98{ 99 int i; 100 struct clast_reduction *r; 101 r = malloc(sizeof(struct clast_reduction)+(n-1)*sizeof(struct clast_expr *)); 102 r->expr.type = clast_expr_red; 103 r->type = t; 104 r->n = n; 105 for (i = 0; i < n; ++i) 106 r->elts[i] = NULL; 107 return r; 108} 109 110static void free_clast_root(struct clast_stmt *s); 111 112const struct clast_stmt_op stmt_root = { free_clast_root }; 113 114static void free_clast_root(struct clast_stmt *s) 115{ 116 struct clast_root *r = (struct clast_root *)s; 117 assert(CLAST_STMT_IS_A(s, stmt_root)); 118 cloog_names_free(r->names); 119 free(r); 120} 121 122struct clast_root *new_clast_root(CloogNames *names) 123{ 124 struct clast_root *r = malloc(sizeof(struct clast_root)); 125 r->stmt.op = &stmt_root; 126 r->stmt.next = NULL; 127 r->names = cloog_names_copy(names); 128 return r; 129} 130 131static void free_clast_assignment(struct clast_stmt *s); 132 133const struct clast_stmt_op stmt_ass = { free_clast_assignment }; 134 135static void free_clast_assignment(struct clast_stmt *s) 136{ 137 struct clast_assignment *a = (struct clast_assignment *)s; 138 assert(CLAST_STMT_IS_A(s, stmt_ass)); 139 free_clast_expr(a->RHS); 140 free(a); 141} 142 143struct clast_assignment *new_clast_assignment(const char *lhs, 144 struct clast_expr *rhs) 145{ 146 struct clast_assignment *a = malloc(sizeof(struct clast_assignment)); 147 a->stmt.op = &stmt_ass; 148 a->stmt.next = NULL; 149 a->LHS = lhs; 150 a->RHS = rhs; 151 return a; 152} 153 154static void free_clast_user_stmt(struct clast_stmt *s); 155 156const struct clast_stmt_op stmt_user = { free_clast_user_stmt }; 157 158static void free_clast_user_stmt(struct clast_stmt *s) 159{ 160 struct clast_user_stmt *u = (struct clast_user_stmt *)s; 161 assert(CLAST_STMT_IS_A(s, stmt_user)); 162 cloog_domain_free(u->domain); 163 cloog_statement_free(u->statement); 164 cloog_clast_free(u->substitutions); 165 free(u); 166} 167 168struct clast_user_stmt *new_clast_user_stmt(CloogDomain *domain, 169 CloogStatement *stmt, struct clast_stmt *subs) 170{ 171 struct clast_user_stmt *u = malloc(sizeof(struct clast_user_stmt)); 172 u->stmt.op = &stmt_user; 173 u->stmt.next = NULL; 174 u->domain = cloog_domain_copy(domain); 175 u->statement = cloog_statement_copy(stmt); 176 u->substitutions = subs; 177 return u; 178} 179 180static void free_clast_block(struct clast_stmt *b); 181 182const struct clast_stmt_op stmt_block = { free_clast_block }; 183 184static void free_clast_block(struct clast_stmt *s) 185{ 186 struct clast_block *b = (struct clast_block *)s; 187 assert(CLAST_STMT_IS_A(s, stmt_block)); 188 cloog_clast_free(b->body); 189 free(b); 190} 191 192struct clast_block *new_clast_block() 193{ 194 struct clast_block *b = malloc(sizeof(struct clast_block)); 195 b->stmt.op = &stmt_block; 196 b->stmt.next = NULL; 197 b->body = NULL; 198 return b; 199} 200 201static void free_clast_for(struct clast_stmt *s); 202 203const struct clast_stmt_op stmt_for = { free_clast_for }; 204 205static void free_clast_for(struct clast_stmt *s) 206{ 207 struct clast_for *f = (struct clast_for *)s; 208 assert(CLAST_STMT_IS_A(s, stmt_for)); 209 cloog_domain_free(f->domain); 210 free_clast_expr(f->LB); 211 free_clast_expr(f->UB); 212 cloog_int_clear(f->stride); 213 cloog_clast_free(f->body); 214 if (f->private_vars) free(f->private_vars); 215 if (f->reduction_vars) free(f->reduction_vars); 216 free(f); 217} 218 219struct clast_for *new_clast_for(CloogDomain *domain, const char *it, 220 struct clast_expr *LB, struct clast_expr *UB, 221 CloogStride *stride) 222{ 223 struct clast_for *f = malloc(sizeof(struct clast_for)); 224 f->stmt.op = &stmt_for; 225 f->stmt.next = NULL; 226 f->domain = cloog_domain_copy(domain); 227 f->iterator = it; 228 f->LB = LB; 229 f->UB = UB; 230 f->body = NULL; 231 f->parallel = CLAST_PARALLEL_NOT; 232 f->private_vars = NULL; 233 f->reduction_vars = NULL; 234 cloog_int_init(f->stride); 235 if (stride) 236 cloog_int_set(f->stride, stride->stride); 237 else 238 cloog_int_set_si(f->stride, 1); 239 return f; 240} 241 242static void free_clast_guard(struct clast_stmt *s); 243 244const struct clast_stmt_op stmt_guard = { free_clast_guard }; 245 246static void free_clast_guard(struct clast_stmt *s) 247{ 248 int i; 249 struct clast_guard *g = (struct clast_guard *)s; 250 assert(CLAST_STMT_IS_A(s, stmt_guard)); 251 cloog_clast_free(g->then); 252 for (i = 0; i < g->n; ++i) { 253 free_clast_expr(g->eq[i].LHS); 254 free_clast_expr(g->eq[i].RHS); 255 } 256 free(g); 257} 258 259struct clast_guard *new_clast_guard(int n) 260{ 261 int i; 262 struct clast_guard *g = malloc(sizeof(struct clast_guard) + 263 (n-1) * sizeof(struct clast_equation)); 264 g->stmt.op = &stmt_guard; 265 g->stmt.next = NULL; 266 g->then = NULL; 267 g->n = n; 268 for (i = 0; i < n; ++i) { 269 g->eq[i].LHS = NULL; 270 g->eq[i].RHS = NULL; 271 } 272 return g; 273} 274 275void free_clast_name(struct clast_name *n) 276{ 277 free(n); 278} 279 280void free_clast_term(struct clast_term *t) 281{ 282 cloog_int_clear(t->val); 283 free_clast_expr(t->var); 284 free(t); 285} 286 287void free_clast_binary(struct clast_binary *b) 288{ 289 cloog_int_clear(b->RHS); 290 free_clast_expr(b->LHS); 291 free(b); 292} 293 294void free_clast_reduction(struct clast_reduction *r) 295{ 296 int i; 297 for (i = 0; i < r->n; ++i) 298 free_clast_expr(r->elts[i]); 299 free(r); 300} 301 302void free_clast_expr(struct clast_expr *e) 303{ 304 if (!e) 305 return; 306 switch (e->type) { 307 case clast_expr_name: 308 free_clast_name((struct clast_name*) e); 309 break; 310 case clast_expr_term: 311 free_clast_term((struct clast_term*) e); 312 break; 313 case clast_expr_red: 314 free_clast_reduction((struct clast_reduction*) e); 315 break; 316 case clast_expr_bin: 317 free_clast_binary((struct clast_binary*) e); 318 break; 319 default: 320 assert(0); 321 } 322} 323 324void free_clast_stmt(struct clast_stmt *s) 325{ 326 assert(s->op); 327 assert(s->op->free); 328 s->op->free(s); 329} 330 331void cloog_clast_free(struct clast_stmt *s) 332{ 333 struct clast_stmt *next; 334 while (s) { 335 next = s->next; 336 free_clast_stmt(s); 337 s = next; 338 } 339} 340 341static int clast_name_cmp(struct clast_name *n1, struct clast_name *n2) 342{ 343 return n1->name == n2->name ? 0 : strcmp(n1->name, n2->name); 344} 345 346static int clast_term_cmp(struct clast_term *t1, struct clast_term *t2) 347{ 348 int c; 349 if (!t1->var && t2->var) 350 return -1; 351 if (t1->var && !t2->var) 352 return 1; 353 c = clast_expr_cmp(t1->var, t2->var); 354 if (c) 355 return c; 356 return cloog_int_cmp(t1->val, t2->val); 357} 358 359static int clast_binary_cmp(struct clast_binary *b1, struct clast_binary *b2) 360{ 361 int c; 362 363 if (b1->type != b2->type) 364 return b1->type - b2->type; 365 if ((c = cloog_int_cmp(b1->RHS, b2->RHS))) 366 return c; 367 return clast_expr_cmp(b1->LHS, b2->LHS); 368} 369 370static int clast_reduction_cmp(struct clast_reduction *r1, struct clast_reduction *r2) 371{ 372 int i; 373 int c; 374 375 if (r1->n == 1 && r2->n == 1) 376 return clast_expr_cmp(r1->elts[0], r2->elts[0]); 377 if (r1->type != r2->type) 378 return r1->type - r2->type; 379 if (r1->n != r2->n) 380 return r1->n - r2->n; 381 for (i = 0; i < r1->n; ++i) 382 if ((c = clast_expr_cmp(r1->elts[i], r2->elts[i]))) 383 return c; 384 return 0; 385} 386 387static int clast_expr_cmp(struct clast_expr *e1, struct clast_expr *e2) 388{ 389 if (!e1 && !e2) 390 return 0; 391 if (!e1) 392 return -1; 393 if (!e2) 394 return 1; 395 if (e1->type != e2->type) 396 return e1->type - e2->type; 397 switch (e1->type) { 398 case clast_expr_name: 399 return clast_name_cmp((struct clast_name*) e1, 400 (struct clast_name*) e2); 401 case clast_expr_term: 402 return clast_term_cmp((struct clast_term*) e1, 403 (struct clast_term*) e2); 404 case clast_expr_bin: 405 return clast_binary_cmp((struct clast_binary*) e1, 406 (struct clast_binary*) e2); 407 case clast_expr_red: 408 return clast_reduction_cmp((struct clast_reduction*) e1, 409 (struct clast_reduction*) e2); 410 default: 411 assert(0); 412 } 413} 414 415int clast_expr_equal(struct clast_expr *e1, struct clast_expr *e2) 416{ 417 return clast_expr_cmp(e1, e2) == 0; 418} 419 420/** 421 * Return 1 is both expressions are constant terms and e1 is bigger than e2. 422 */ 423int clast_expr_is_bigger_constant(struct clast_expr *e1, struct clast_expr *e2) 424{ 425 struct clast_term *t1, *t2; 426 struct clast_reduction *r; 427 428 if (!e1 || !e2) 429 return 0; 430 if (e1->type == clast_expr_red) { 431 r = (struct clast_reduction *)e1; 432 return r->n == 1 && clast_expr_is_bigger_constant(r->elts[0], e2); 433 } 434 if (e2->type == clast_expr_red) { 435 r = (struct clast_reduction *)e2; 436 return r->n == 1 && clast_expr_is_bigger_constant(e1, r->elts[0]); 437 } 438 if (e1->type != clast_expr_term || e2->type != clast_expr_term) 439 return 0; 440 t1 = (struct clast_term *)e1; 441 t2 = (struct clast_term *)e2; 442 if (t1->var || t2->var) 443 return 0; 444 return cloog_int_gt(t1->val, t2->val); 445} 446 447static int qsort_expr_cmp(const void *p1, const void *p2) 448{ 449 return clast_expr_cmp(*(struct clast_expr **)p1, *(struct clast_expr **)p2); 450} 451 452static void clast_reduction_sort(struct clast_reduction *r) 453{ 454 qsort(&r->elts[0], r->n, sizeof(struct clast_expr *), qsort_expr_cmp); 455} 456 457static int qsort_eq_cmp(const void *p1, const void *p2) 458{ 459 struct clast_equation *eq1 = (struct clast_equation *)p1; 460 struct clast_equation *eq2 = (struct clast_equation *)p2; 461 int cmp; 462 463 cmp = clast_expr_cmp(eq1->LHS, eq2->LHS); 464 if (cmp) 465 return cmp; 466 467 cmp = clast_expr_cmp(eq1->RHS, eq2->RHS); 468 if (cmp) 469 return cmp; 470 471 return eq1->sign - eq2->sign; 472} 473 474/** 475 * Sort equations in a clast_guard. 476 */ 477static void clast_guard_sort(struct clast_guard *g) 478{ 479 qsort(&g->eq[0], g->n, sizeof(struct clast_equation), qsort_eq_cmp); 480} 481 482 483/** 484 * Construct a (deep) copy of an expression clast. 485 */ 486static struct clast_expr *clast_expr_copy(struct clast_expr *e) 487{ 488 if (!e) 489 return NULL; 490 switch (e->type) { 491 case clast_expr_name: { 492 struct clast_name* n = (struct clast_name*) e; 493 return &new_clast_name(n->name)->expr; 494 } 495 case clast_expr_term: { 496 struct clast_term* t = (struct clast_term*) e; 497 return &new_clast_term(t->val, clast_expr_copy(t->var))->expr; 498 } 499 case clast_expr_red: { 500 int i; 501 struct clast_reduction *r = (struct clast_reduction*) e; 502 struct clast_reduction *r2 = new_clast_reduction(r->type, r->n); 503 for (i = 0; i < r->n; ++i) 504 r2->elts[i] = clast_expr_copy(r->elts[i]); 505 return &r2->expr; 506 } 507 case clast_expr_bin: { 508 struct clast_binary *b = (struct clast_binary*) e; 509 return &new_clast_binary(b->type, clast_expr_copy(b->LHS), b->RHS)->expr; 510 } 511 default: 512 assert(0); 513 } 514} 515 516 517/****************************************************************************** 518 * Equalities spreading functions * 519 ******************************************************************************/ 520 521 522/** 523 * clast_equal_allow function: 524 * This function checks whether the options allow us to spread the equality or 525 * not. It returns 1 if so, 0 otherwise. 526 * - equal is the matrix of equalities, 527 * - level is the column number in equal of the element which is 'equal to', 528 * - line is the line number in equal of the constraint we want to study, 529 * - the infos structure gives the user all options on code printing and more. 530 ** 531 * - October 27th 2005: first version (extracted from old pprint_equal_add). 532 */ 533static int clast_equal_allow(CloogEqualities *equal, int level, int line, 534 CloogInfos *infos) 535{ 536 if (level < infos->options->fsp) 537 return 0 ; 538 539 if ((cloog_equal_type(equal, level) == EQTYPE_EXAFFINE) && 540 !infos->options->esp) 541 return 0 ; 542 543 return 1 ; 544} 545 546 547/** 548 * clast_equal_add function: 549 * This function updates the row (level-1) of the equality matrix (equal) with 550 * the row that corresponds to the row (line) of the matrix (matrix). It returns 551 * 1 if the row can be updated, 0 otherwise. 552 * - equal is the matrix of equalities, 553 * - matrix is the matrix of constraints, 554 * - level is the column number in matrix of the element which is 'equal to', 555 * - line is the line number in matrix of the constraint we want to study, 556 * - the infos structure gives the user all options on code printing and more. 557 */ 558static int clast_equal_add(CloogEqualities *equal, 559 CloogConstraintSet *constraints, 560 int level, CloogConstraint *constraint, 561 CloogInfos *infos) 562{ 563 cloog_equal_add(equal, constraints, level, constraint, 564 infos->names->nb_parameters); 565 566 return clast_equal_allow(equal, level, level-1, infos); 567} 568 569 570 571/** 572 * clast_equal function: 573 * This function prints the substitution data of a statement into a clast_stmt. 574 * Using this function instead of pprint_equal is useful for generating 575 * a compilable pseudo-code by using preprocessor macro for each statement. 576 * By opposition to pprint_equal, the result is less human-readable. For 577 * instance this function will print (i,i+3,k,3) where pprint_equal would 578 * return (j=i+3,l=3). 579 * - level is the number of loops enclosing the statement, 580 * - the infos structure gives the user all options on code printing and more. 581 ** 582 * - March 12th 2004: first version. 583 * - November 21th 2005: (debug) now works well with GMP version. 584 */ 585static struct clast_stmt *clast_equal(int level, CloogInfos *infos) 586{ 587 int i ; 588 struct clast_expr *e; 589 struct clast_stmt *a = NULL; 590 struct clast_stmt **next = &a; 591 CloogEqualities *equal = infos->equal; 592 CloogConstraint *equal_constraint; 593 594 for (i=infos->names->nb_scattering;i<level-1;i++) 595 { if (cloog_equal_type(equal, i+1)) { 596 equal_constraint = cloog_equal_constraint(equal, i); 597 e = clast_bound_from_constraint(equal_constraint, i+1, infos->names); 598 cloog_constraint_release(equal_constraint); 599 } else { 600 e = &new_clast_term(infos->state->one, &new_clast_name( 601 cloog_names_name_at_level(infos->names, i+1))->expr)->expr; 602 } 603 *next = &new_clast_assignment(NULL, e)->stmt; 604 next = &(*next)->next; 605 } 606 607 return a; 608} 609 610 611/** 612 * clast_bound_from_constraint function: 613 * This function returns a clast_expr containing the printing of the 614 * 'right part' of a constraint according to an element. 615 * For instance, for the constraint -3*i + 2*j - M >=0 and the element j, 616 * we have j >= (3*i + M)/2. As we are looking for integral solutions, this 617 * function should return 'ceild(3*i+M,2)'. 618 * - matrix is the polyhedron containing all the constraints, 619 * - line_num is the line number in domain of the constraint we want to print, 620 * - level is the column number in domain of the element we want to use, 621 * - names structure gives the user some options about code printing, 622 * the number of parameters in domain (nb_par), and the arrays of iterator 623 * names and parameters (iters and params). 624 ** 625 * - November 2nd 2001: first version. 626 * - June 27th 2003: 64 bits version ready. 627 */ 628struct clast_expr *clast_bound_from_constraint(CloogConstraint *constraint, 629 int level, CloogNames *names) 630{ 631 int i, sign, nb_elts=0, len; 632 cloog_int_t *line, numerator, denominator, temp, division; 633 struct clast_expr *e = NULL; 634 struct cloog_vec *line_vector; 635 636 len = cloog_constraint_total_dimension(constraint) + 2; 637 line_vector = cloog_vec_alloc(len); 638 line = line_vector->p; 639 cloog_constraint_copy_coefficients(constraint, line+1); 640 cloog_int_init(temp); 641 cloog_int_init(numerator); 642 cloog_int_init(denominator); 643 644 if (!cloog_int_is_zero(line[level])) { 645 struct clast_reduction *r; 646 /* Maybe we need to invert signs in such a way that the element sign is>0.*/ 647 sign = -cloog_int_sgn(line[level]); 648 649 for (i = 1, nb_elts = 0; i <= len - 1; ++i) 650 if (i != level && !cloog_int_is_zero(line[i])) 651 nb_elts++; 652 r = new_clast_reduction(clast_red_sum, nb_elts); 653 nb_elts = 0; 654 655 /* First, we have to print the iterators and the parameters. */ 656 for (i = 1; i <= len - 2; i++) { 657 struct clast_expr *v; 658 659 if (i == level || cloog_int_is_zero(line[i])) 660 continue; 661 662 v = cloog_constraint_variable_expr(constraint, i, names); 663 664 if (sign == -1) 665 cloog_int_neg(temp,line[i]); 666 else 667 cloog_int_set(temp,line[i]); 668 669 r->elts[nb_elts++] = &new_clast_term(temp, v)->expr; 670 } 671 672 if (sign == -1) { 673 cloog_int_neg(numerator, line[len - 1]); 674 cloog_int_set(denominator, line[level]); 675 } 676 else { 677 cloog_int_set(numerator, line[len - 1]); 678 cloog_int_neg(denominator, line[level]); 679 } 680 681 /* Finally, the constant, and the final printing. */ 682 if (nb_elts) { 683 if (!cloog_int_is_zero(numerator)) 684 r->elts[nb_elts++] = &new_clast_term(numerator, NULL)->expr; 685 686 if (!cloog_int_is_one(line[level]) && !cloog_int_is_neg_one(line[level])) 687 { if (!cloog_constraint_is_equality(constraint)) 688 { if (cloog_int_is_pos(line[level])) 689 e = &new_clast_binary(clast_bin_cdiv, &r->expr, denominator)->expr; 690 else 691 e = &new_clast_binary(clast_bin_fdiv, &r->expr, denominator)->expr; 692 } else 693 e = &new_clast_binary(clast_bin_div, &r->expr, denominator)->expr; 694 } 695 else 696 e = &r->expr; 697 } else { 698 free_clast_reduction(r); 699 if (cloog_int_is_zero(numerator)) 700 e = &new_clast_term(numerator, NULL)->expr; 701 else 702 { if (!cloog_int_is_one(denominator)) 703 { if (!cloog_constraint_is_equality(constraint)) { /* useful? */ 704 if (cloog_int_is_divisible_by(numerator, denominator)) { 705 cloog_int_divexact(temp, numerator, denominator); 706 e = &new_clast_term(temp, NULL)->expr; 707 } 708 else { 709 cloog_int_init(division); 710 cloog_int_tdiv_q(division, numerator, denominator); 711 if (cloog_int_is_neg(numerator)) { 712 if (cloog_int_is_pos(line[level])) { 713 /* nb<0 need max */ 714 e = &new_clast_term(division, NULL)->expr; 715 } else { 716 /* nb<0 need min */ 717 cloog_int_sub_ui(temp, division, 1); 718 e = &new_clast_term(temp, NULL)->expr; 719 } 720 } 721 else 722 { if (cloog_int_is_pos(line[level])) 723 { /* nb>0 need max */ 724 cloog_int_add_ui(temp, division, 1); 725 e = &new_clast_term(temp, NULL)->expr; 726 } 727 else 728 /* nb>0 need min */ 729 e = &new_clast_term(division, NULL)->expr; 730 } 731 cloog_int_clear(division); 732 } 733 } 734 else 735 e = &new_clast_binary(clast_bin_div, 736 &new_clast_term(numerator, NULL)->expr, 737 denominator)->expr; 738 } 739 else 740 e = &new_clast_term(numerator, NULL)->expr; 741 } 742 } 743 } 744 745 cloog_vec_free(line_vector); 746 747 cloog_int_clear(temp); 748 cloog_int_clear(numerator); 749 cloog_int_clear(denominator); 750 751 return e; 752} 753 754 755/* Temporary structure for communication between clast_minmax and 756 * its cloog_constraint_set_foreach_constraint callback functions. 757 */ 758struct clast_minmax_data { 759 int level; 760 int max; 761 int guard; 762 int lower_bound; 763 int no_earlier; 764 CloogInfos *infos; 765 int n; 766 struct clast_reduction *r; 767}; 768 769 770/* Should constraint "c" be considered by clast_minmax? 771 * 772 * If d->no_earlier is set, then the constraint may not involve 773 * any earlier variables. 774 */ 775static int valid_bound(CloogConstraint *c, struct clast_minmax_data *d) 776{ 777 int i; 778 779 if (d->max && !cloog_constraint_is_lower_bound(c, d->level - 1)) 780 return 0; 781 if (!d->max && !cloog_constraint_is_upper_bound(c, d->level - 1)) 782 return 0; 783 if (cloog_constraint_is_equality(c)) 784 return 0; 785 if (d->guard && cloog_constraint_involves(c, d->guard - 1)) 786 return 0; 787 788 if (d->no_earlier) 789 for (i = 0; i < d->level - 1; ++i) 790 if (cloog_constraint_involves(c, i)) 791 return 0; 792 793 return 1; 794} 795 796 797/* Increment n for each bound that should be considered by clast_minmax. 798 */ 799static int count_bounds(CloogConstraint *c, void *user) 800{ 801 struct clast_minmax_data *d = (struct clast_minmax_data *) user; 802 803 if (!valid_bound(c, d)) 804 return 0; 805 806 d->n++; 807 808 return 0; 809} 810 811 812/* Update the given lower bound based on stride information, 813 * for those cases where the stride offset is represented by 814 * a constraint. 815 * Note that cloog_loop_stride may have already performed a 816 * similar update of the lower bounds, but the updated lower 817 * bounds may have been eliminated because they are redundant 818 * by definition. On the other hand, performing the update 819 * on an already updated constraint is an identity operation 820 * and is therefore harmless. 821 */ 822static CloogConstraint *update_lower_bound_c(CloogConstraint *c, int level, 823 CloogStride *stride) 824{ 825 if (!stride->constraint) 826 return c; 827 return cloog_constraint_stride_lower_bound(c, level, stride); 828} 829 830 831/* Update the given lower bound based on stride information. 832 * If the stride offset is represented by a constraint, 833 * then we have already performed the update in update_lower_bound_c. 834 * Otherwise, the original lower bound is known to be a constant. 835 * If the bound has already been updated and it just happens 836 * to be a constant, then this function performs an identity 837 * operation on the constant. 838 */ 839static void update_lower_bound(struct clast_expr *expr, int level, 840 CloogStride *stride) 841{ 842 struct clast_term *t; 843 if (stride->constraint) 844 return; 845 if (expr->type != clast_expr_term) 846 return; 847 t = (struct clast_term *)expr; 848 if (t->var) 849 return; 850 cloog_int_sub(t->val, t->val, stride->offset); 851 cloog_int_cdiv_q(t->val, t->val, stride->stride); 852 cloog_int_mul(t->val, t->val, stride->stride); 853 cloog_int_add(t->val, t->val, stride->offset); 854} 855 856 857/* Add all relevant bounds to r->elts and update lower bounds 858 * based on stride information. 859 */ 860static int collect_bounds(CloogConstraint *c, void *user) 861{ 862 struct clast_minmax_data *d = (struct clast_minmax_data *) user; 863 864 if (!valid_bound(c, d)) 865 return 0; 866 867 c = cloog_constraint_copy(c); 868 869 if (d->lower_bound && d->infos->stride[d->level - 1]) 870 c = update_lower_bound_c(c, d->level, d->infos->stride[d->level - 1]); 871 872 d->r->elts[d->n] = clast_bound_from_constraint(c, d->level, 873 d->infos->names); 874 if (d->lower_bound && d->infos->stride[d->level - 1]) { 875 update_lower_bound(d->r->elts[d->n], d->level, 876 d->infos->stride[d->level - 1]); 877 } 878 879 cloog_constraint_release(c); 880 881 d->n++; 882 883 return 0; 884} 885 886 887/** 888 * clast_minmax function: 889 * This function returns a clast_expr containing the printing of a minimum or a 890 * maximum of the 'right parts' of all constraints according to an element. 891 * For instance consider the constraints: 892 * -3*i +2*j -M >= 0 893 * 2*i +j >= 0 894 * -i -j +2*M >= 0 895 * if we are looking for the minimum for the element j, the function should 896 * return 'max(ceild(3*i+M,2),-2*i)'. 897 * - constraints is the constraints, 898 * - level is the column number in domain of the element we want to use, 899 * - max is a boolean set to 1 if we are looking for a maximum, 0 for a minimum, 900 * - guard is set to 0 if there is no guard, and set to the level of the element 901 * with a guard otherwise (then the function gives the max or the min only 902 * for the constraint where the guarded coefficient is 0), 903 * - lower is set to 1 if the maximum is to be used a lower bound on a loop 904 * - no_earlier is set if no constraints should be used that involve 905 * earlier dimensions, 906 * - the infos structure gives the user some options about code printing, 907 * the number of parameters in domain (nb_par), and the arrays of iterator 908 * names and parameters (iters and params). 909 ** 910 * - November 2nd 2001: first version. 911 */ 912static struct clast_expr *clast_minmax(CloogConstraintSet *constraints, 913 int level, int max, int guard, 914 int lower_bound, int no_earlier, 915 CloogInfos *infos) 916{ 917 struct clast_minmax_data data = { level, max, guard, lower_bound, 918 no_earlier, infos }; 919 920 data.n = 0; 921 922 cloog_constraint_set_foreach_constraint(constraints, count_bounds, &data); 923 924 if (!data.n) 925 return NULL; 926 data.r = new_clast_reduction(max ? clast_red_max : clast_red_min, data.n); 927 928 data.n = 0; 929 cloog_constraint_set_foreach_constraint(constraints, collect_bounds, &data); 930 931 clast_reduction_sort(data.r); 932 return &data.r->expr; 933} 934 935 936/** 937 * Insert modulo guards defined by existentially quantified dimensions, 938 * not involving the given level. 939 * 940 * This function is called from within insert_guard. 941 * Any constraint used in constructing a modulo guard is removed 942 * from the constraint set to avoid insert_guard 943 * adding a duplicate (pair of) constraint(s). 944 * 945 * Return the updated CloogConstraintSet. 946 */ 947static CloogConstraintSet *insert_extra_modulo_guards( 948 CloogConstraintSet *constraints, int level, 949 struct clast_stmt ***next, CloogInfos *infos) 950{ 951 int i; 952 int nb_iter; 953 int total_dim; 954 CloogConstraint *upper, *lower; 955 956 total_dim = cloog_constraint_set_total_dimension(constraints); 957 nb_iter = cloog_constraint_set_n_iterators(constraints, 958 infos->names->nb_parameters); 959 960 for (i = total_dim - infos->names->nb_parameters; i >= nb_iter + 1; i--) { 961 if (cloog_constraint_is_valid(upper = 962 cloog_constraint_set_defining_equality(constraints, i))) { 963 if (!level || (nb_iter < level) || 964 !cloog_constraint_involves(upper, level-1)) { 965 insert_modulo_guard(upper, 966 cloog_constraint_invalid(), i, next, infos); 967 constraints = cloog_constraint_set_drop_constraint(constraints, 968 upper); 969 } 970 cloog_constraint_release(upper); 971 } else if (cloog_constraint_is_valid(upper = 972 cloog_constraint_set_defining_inequalities(constraints, 973 i, &lower, infos->names->nb_parameters))) { 974 if (!level || (nb_iter < level) || 975 !cloog_constraint_involves(upper, level-1)) { 976 insert_modulo_guard(upper, lower, i, next, infos); 977 constraints = cloog_constraint_set_drop_constraint(constraints, 978 upper); 979 constraints = cloog_constraint_set_drop_constraint(constraints, 980 lower); 981 } 982 cloog_constraint_release(upper); 983 cloog_constraint_release(lower); 984 } 985 } 986 987 return constraints; 988} 989 990 991/* Temporary structure for communication between insert_guard and 992 * its cloog_constraint_set_foreach_constraint callback function. 993 */ 994struct clast_guard_data { 995 int level; 996 CloogInfos *infos; 997 int n; 998 int i; 999 int nb_iter; 1000 CloogConstraintSet *copy; 1001 struct clast_guard *g; 1002 1003 int min; 1004 int max; 1005}; 1006 1007 1008static int guard_count_bounds(CloogConstraint *c, void *user) 1009{ 1010 struct clast_guard_data *d = (struct clast_guard_data *) user; 1011 1012 d->n++; 1013 1014 return 0; 1015} 1016 1017 1018/* Insert a guard, if necesessary, for constraint j. 1019 * 1020 * If the constraint involves any earlier dimensions, then we have 1021 * already considered it during a previous iteration over the constraints. 1022 * 1023 * If we have already generated a min [max] for the current level d->i 1024 * and if the current constraint is an upper [lower] bound, then we 1025 * can skip the constraint as it will already have been used 1026 * in that previously generated min [max]. 1027 */ 1028static int insert_guard_constraint(CloogConstraint *j, void *user) 1029{ 1030 int i; 1031 struct clast_guard_data *d = (struct clast_guard_data *) user; 1032 int minmax = -1; 1033 int individual_constraint; 1034 struct clast_expr *v; 1035 struct clast_term *t; 1036 1037 if (!cloog_constraint_involves(j, d->i - 1)) 1038 return 0; 1039 1040 for (i = 0; i < d->i - 1; ++i) 1041 if (cloog_constraint_involves(j, i)) 1042 return 0; 1043 1044 if (d->level && d->nb_iter >= d->level && 1045 cloog_constraint_involves(j, d->level - 1)) 1046 return 0; 1047 1048 individual_constraint = !d->level || cloog_constraint_is_equality(j); 1049 if (!individual_constraint) { 1050 if (d->max && cloog_constraint_is_lower_bound(j, d->i - 1)) 1051 return 0; 1052 if (d->min && cloog_constraint_is_upper_bound(j, d->i - 1)) 1053 return 0; 1054 } 1055 1056 v = cloog_constraint_variable_expr(j, d->i, d->infos->names); 1057 d->g->eq[d->n].LHS = &(t = new_clast_term(d->infos->state->one, v))->expr; 1058 if (individual_constraint) { 1059 /* put the "denominator" in the LHS */ 1060 cloog_constraint_coefficient_get(j, d->i - 1, &t->val); 1061 cloog_constraint_coefficient_set(j, d->i - 1, d->infos->state->one); 1062 if (cloog_int_is_neg(t->val)) { 1063 cloog_int_neg(t->val, t->val); 1064 cloog_constraint_coefficient_set(j, d->i - 1, d->infos->state->negone); 1065 } 1066 if (d->level || cloog_constraint_is_equality(j)) 1067 d->g->eq[d->n].sign = 0; 1068 else if (cloog_constraint_is_lower_bound(j, d->i - 1)) 1069 d->g->eq[d->n].sign = 1; 1070 else 1071 d->g->eq[d->n].sign = -1; 1072 d->g->eq[d->n].RHS = clast_bound_from_constraint(j, d->i, d->infos->names); 1073 } else { 1074 int guarded; 1075 1076 if (cloog_constraint_is_lower_bound(j, d->i - 1)) { 1077 minmax = 1; 1078 d->max = 1; 1079 d->g->eq[d->n].sign = 1; 1080 } else { 1081 minmax = 0; 1082 d->min = 1; 1083 d->g->eq[d->n].sign = -1; 1084 } 1085 1086 guarded = (d->nb_iter >= d->level) ? d->level : 0 ; 1087 d->g->eq[d->n].RHS = clast_minmax(d->copy, d->i, minmax, guarded, 0, 1, 1088 d->infos); 1089 } 1090 d->n++; 1091 1092 return 0; 1093} 1094 1095 1096/** 1097 * insert_guard function: 1098 * This function inserts a guard in the clast. 1099 * A guard on an element (level) is : 1100 * -> the conjunction of all the existing constraints where the coefficient of 1101 * this element is 0 if the element is an iterator, 1102 * -> the conjunction of all the existing constraints if the element isn't an 1103 * iterator. 1104 * For instance, considering these constraints and the element j: 1105 * -3*i +2*j -M >= 0 1106 * 2*i +M >= 0 1107 * this function should return 'if (2*i+M>=0) {'. 1108 * - matrix is the polyhedron containing all the constraints, 1109 * - level is the column number of the element in matrix we want to use, 1110 * - the infos structure gives the user some options about code printing, 1111 * the number of parameters in matrix (nb_par), and the arrays of iterator 1112 * names and parameters (iters and params). 1113 ** 1114 * - November 3rd 2001: first version. 1115 * - November 14th 2001: a lot of 'purifications'. 1116 * - July 31th 2002: (debug) some guard parts are no more redundants. 1117 * - August 12th 2002: polyhedra union ('or' conditions) are now supported. 1118 * - October 27th 2005: polyhedra union ('or' conditions) are no more supported 1119 * (the need came from loop_simplify that may result in 1120 * domain unions, now it should be fixed directly in 1121 * cloog_loop_simplify). 1122 */ 1123static void insert_guard(CloogConstraintSet *constraints, int level, 1124 struct clast_stmt ***next, CloogInfos *infos) 1125{ 1126 int total_dim; 1127 struct clast_guard_data data = { level, infos, 0 }; 1128 1129 if (!constraints) 1130 return; 1131 1132 data.copy = cloog_constraint_set_copy(constraints); 1133 1134 data.copy = insert_extra_modulo_guards(data.copy, level, next, infos); 1135 1136 cloog_constraint_set_foreach_constraint(constraints, 1137 guard_count_bounds, &data); 1138 1139 data.g = new_clast_guard(data.n); 1140 data.n = 0; 1141 1142 /* Well, it looks complicated because I wanted to have a particular, more 1143 * readable, ordering, obviously this function may be far much simpler ! 1144 */ 1145 data.nb_iter = cloog_constraint_set_n_iterators(constraints, 1146 infos->names->nb_parameters); 1147 1148 /* We search for guard parts. */ 1149 total_dim = cloog_constraint_set_total_dimension(constraints); 1150 for (data.i = 1; data.i <= total_dim; data.i++) { 1151 data.min = 0; 1152 data.max = 0; 1153 cloog_constraint_set_foreach_constraint(data.copy, 1154 insert_guard_constraint, &data); 1155 } 1156 1157 cloog_constraint_set_free(data.copy); 1158 1159 data.g->n = data.n; 1160 if (data.n) { 1161 clast_guard_sort(data.g); 1162 **next = &data.g->stmt; 1163 *next = &data.g->then; 1164 } else 1165 free_clast_stmt(&data.g->stmt); 1166} 1167 1168/** 1169 * Check if the constant "cst" satisfies the modulo guard that 1170 * would be introduced by insert_computed_modulo_guard. 1171 * The constant is assumed to have been reduced prior to calling 1172 * this function. 1173 */ 1174static int constant_modulo_guard_is_satisfied(CloogConstraint *lower, 1175 cloog_int_t bound, cloog_int_t cst) 1176{ 1177 if (cloog_constraint_is_valid(lower)) 1178 return cloog_int_le(cst, bound); 1179 else 1180 return cloog_int_is_zero(cst); 1181} 1182 1183/** 1184 * Insert a modulo guard "r % mod == 0" or "r % mod <= bound", 1185 * depending on whether lower represents a valid constraint. 1186 */ 1187static void insert_computed_modulo_guard(struct clast_reduction *r, 1188 CloogConstraint *lower, cloog_int_t mod, cloog_int_t bound, 1189 struct clast_stmt ***next) 1190{ 1191 struct clast_expr *e; 1192 struct clast_guard *g; 1193 1194 e = &new_clast_binary(clast_bin_mod, &r->expr, mod)->expr; 1195 g = new_clast_guard(1); 1196 if (!cloog_constraint_is_valid(lower)) { 1197 g->eq[0].LHS = e; 1198 cloog_int_set_si(bound, 0); 1199 g->eq[0].RHS = &new_clast_term(bound, NULL)->expr; 1200 g->eq[0].sign = 0; 1201 } else { 1202 g->eq[0].LHS = e; 1203 g->eq[0].RHS = &new_clast_term(bound, NULL)->expr; 1204 g->eq[0].sign = -1; 1205 } 1206 1207 **next = &g->stmt; 1208 *next = &g->then; 1209} 1210 1211 1212/* Try and eliminate coefficients from a modulo constraint based on 1213 * stride information of an earlier level. 1214 * The modulo of the constraint being constructed is "m". 1215 * The stride information at level "level" is given by "stride" 1216 * and indicated that the iterator i at level "level" is equal to 1217 * some expression modulo stride->stride. 1218 * If stride->stride is a multiple of "m' then i is also equal to 1219 * the expression modulo m and so we can eliminate the coefficient of i. 1220 * 1221 * If stride->constraint is NULL, then i has a constant value modulo m, stored 1222 * stride->offset. We simply multiply this constant with the coefficient 1223 * of i and add the result to the constant term, reducing it modulo m. 1224 * 1225 * If stride->constraint is not NULL, then it is a constraint of the form 1226 * 1227 * e + k i = s a 1228 * 1229 * with s equal to stride->stride, e an expression in terms of the 1230 * parameters and earlier iterators and a some arbitrary expression 1231 * in terms of existentially quantified variables. 1232 * stride->factor is a value f such that f * k = -1 mod s. 1233 * Adding stride->constraint f * c times to the current modulo constraint, 1234 * with c the coefficient of i eliminates i in favor of parameters and 1235 * earlier variables. 1236 */ 1237static void eliminate_using_stride_constraint(cloog_int_t *line, int len, 1238 int nb_iter, CloogStride *stride, int level, cloog_int_t m) 1239{ 1240 if (!stride) 1241 return; 1242 if (!cloog_int_is_divisible_by(stride->stride, m)) 1243 return; 1244 1245 if (stride->constraint) { 1246 int i, s_len; 1247 cloog_int_t t, v; 1248 1249 cloog_int_init(t); 1250 cloog_int_init(v); 1251 cloog_int_mul(t, line[level], stride->factor); 1252 for (i = 1; i < level; ++i) { 1253 cloog_constraint_coefficient_get(stride->constraint, 1254 i - 1, &v); 1255 cloog_int_addmul(line[i], t, v); 1256 cloog_int_fdiv_r(line[i], line[i], m); 1257 } 1258 s_len = cloog_constraint_total_dimension(stride->constraint)+2; 1259 for (i = nb_iter + 1; i <= len - 2; ++i) { 1260 cloog_constraint_coefficient_get(stride->constraint, 1261 i - (len - s_len) - 1, &v); 1262 cloog_int_addmul(line[i], t, v); 1263 cloog_int_fdiv_r(line[i], line[i], m); 1264 } 1265 cloog_constraint_constant_get(stride->constraint, &v); 1266 cloog_int_addmul(line[len - 1], t, v); 1267 cloog_int_fdiv_r(line[len - 1], line[len - 1], m); 1268 cloog_int_clear(v); 1269 cloog_int_clear(t); 1270 } else { 1271 cloog_int_addmul(line[len - 1], line[level], stride->offset); 1272 cloog_int_fdiv_r(line[len - 1], line[len - 1], m); 1273 } 1274 1275 cloog_int_set_si(line[level], 0); 1276} 1277 1278 1279/* Temporary structure for communication between insert_modulo_guard and 1280 * its cloog_constraint_set_foreach_constraint callback function. 1281 */ 1282struct clast_modulo_guard_data { 1283 CloogConstraint *lower; 1284 int level; 1285 struct clast_stmt ***next; 1286 CloogInfos *infos; 1287 int empty; 1288 cloog_int_t val, bound; 1289}; 1290 1291 1292/* Insert a modulo guard for constraint c. 1293 * The constraint may be either an equality or an inequality. 1294 * Since this function returns -1, it is only called on a single constraint. 1295 * In case of an inequality, the constraint is usually an upper bound 1296 * on d->level. However, if this variable is an existentially 1297 * quantified variable, the upper bound constraint may get removed 1298 * as trivially holding and then this function is called with 1299 * a lower bound instead. In this case, we need to adjust the constraint 1300 * based on the sum of the constant terms of the lower and upper bound 1301 * stored in d->bound. 1302 */ 1303static int insert_modulo_guard_constraint(CloogConstraint *c, void *user) 1304{ 1305 struct clast_modulo_guard_data *d = (struct clast_modulo_guard_data *) user; 1306 int level = d->level; 1307 CloogInfos *infos = d->infos; 1308 int i, nb_elts = 0, len, nb_iter, nb_par; 1309 int constant; 1310 struct cloog_vec *line_vector; 1311 cloog_int_t *line; 1312 1313 len = cloog_constraint_total_dimension(c) + 2; 1314 nb_par = infos->names->nb_parameters; 1315 nb_iter = len - 2 - nb_par; 1316 1317 line_vector = cloog_vec_alloc(len); 1318 line = line_vector->p; 1319 cloog_constraint_copy_coefficients(c, line + 1); 1320 1321 if (cloog_int_is_pos(line[level])) { 1322 cloog_seq_neg(line + 1, line + 1, len - 1); 1323 if (!cloog_constraint_is_equality(c)) 1324 cloog_int_add(line[len - 1], line[len - 1], d->bound); 1325 } 1326 cloog_int_neg(line[level], line[level]); 1327 assert(cloog_int_is_pos(line[level])); 1328 1329 nb_elts = 0; 1330 for (i = 1; i <= len-1; ++i) { 1331 if (i == level) 1332 continue; 1333 cloog_int_fdiv_r(line[i], line[i], line[level]); 1334 if (cloog_int_is_zero(line[i])) 1335 continue; 1336 if (i == len-1) 1337 continue; 1338 1339 nb_elts++; 1340 } 1341 1342 if (nb_elts || !cloog_int_is_zero(line[len-1])) { 1343 struct clast_reduction *r; 1344 const char *name; 1345 1346 r = new_clast_reduction(clast_red_sum, nb_elts + 1); 1347 nb_elts = 0; 1348 1349 /* First, the modulo guard : the iterators... */ 1350 i = level - 1; 1351 if (i > infos->stride_level) 1352 i = infos->stride_level; 1353 for (; i >= 1; --i) 1354 eliminate_using_stride_constraint(line, len, nb_iter, 1355 infos->stride[i - 1], i, line[level]); 1356 for (i=1;i<=nb_iter;i++) { 1357 if (i == level || cloog_int_is_zero(line[i])) 1358 continue; 1359 1360 name = cloog_names_name_at_level(infos->names, i); 1361 1362 r->elts[nb_elts++] = &new_clast_term(line[i], 1363 &new_clast_name(name)->expr)->expr; 1364 } 1365 1366 /* ...the parameters... */ 1367 for (i=nb_iter+1;i<=len-2;i++) { 1368 if (cloog_int_is_zero(line[i])) 1369 continue; 1370 1371 name = infos->names->parameters[i-nb_iter-1] ; 1372 r->elts[nb_elts++] = &new_clast_term(line[i], 1373 &new_clast_name(name)->expr)->expr; 1374 } 1375 1376 constant = nb_elts == 0; 1377 /* ...the constant. */ 1378 if (!cloog_int_is_zero(line[len-1])) 1379 r->elts[nb_elts++] = &new_clast_term(line[len-1], NULL)->expr; 1380 1381 /* our initial computation may have been an overestimate */ 1382 r->n = nb_elts; 1383 1384 if (constant) { 1385 d->empty = !constant_modulo_guard_is_satisfied(d->lower, d->bound, 1386 line[len - 1]); 1387 free_clast_reduction(r); 1388 } else 1389 insert_computed_modulo_guard(r, d->lower, line[level], d->bound, 1390 d->next); 1391 } 1392 1393 cloog_vec_free(line_vector); 1394 1395 return -1; 1396} 1397 1398 1399/** 1400 * insert_modulo_guard: 1401 * This function inserts a modulo guard corresponding to an equality 1402 * or a pair of inequalities. 1403 * Returns 0 if the modulo guard is discovered to be unsatisfiable. 1404 * 1405 * See insert_equation. 1406 * - matrix is the polyhedron containing all the constraints, 1407 * - upper and lower are the line numbers of the constraint in matrix 1408 * we want to print; in particular, if we want to print an equality, 1409 * then lower == -1 and upper is the row of the equality; if we want 1410 * to print an inequality, then upper is the row of the upper bound 1411 * and lower in the row of the lower bound 1412 * - level is the column number of the element in matrix we want to use, 1413 * - the infos structure gives the user some options about code printing, 1414 * the number of parameters in matrix (nb_par), and the arrays of iterator 1415 * names and parameters (iters and params). 1416 */ 1417static int insert_modulo_guard(CloogConstraint *upper, 1418 CloogConstraint *lower, int level, 1419 struct clast_stmt ***next, CloogInfos *infos) 1420{ 1421 int nb_par; 1422 CloogConstraintSet *set; 1423 struct clast_modulo_guard_data data = { lower, level, next, infos, 0 }; 1424 1425 cloog_int_init(data.val); 1426 cloog_constraint_coefficient_get(upper, level-1, &data.val); 1427 if (cloog_int_is_one(data.val) || cloog_int_is_neg_one(data.val)) { 1428 cloog_int_clear(data.val); 1429 return 1; 1430 } 1431 1432 nb_par = infos->names->nb_parameters; 1433 1434 cloog_int_init(data.bound); 1435 /* Check if would be emitting the redundant constraint mod(e,m) <= m-1 */ 1436 if (cloog_constraint_is_valid(lower)) { 1437 cloog_constraint_constant_get(upper, &data.val); 1438 cloog_constraint_constant_get(lower, &data.bound); 1439 cloog_int_add(data.bound, data.val, data.bound); 1440 cloog_constraint_coefficient_get(lower, level-1, &data.val); 1441 cloog_int_sub_ui(data.val, data.val, 1); 1442 if (cloog_int_eq(data.val, data.bound)) { 1443 cloog_int_clear(data.val); 1444 cloog_int_clear(data.bound); 1445 return 1; 1446 } 1447 } 1448 1449 if (cloog_constraint_needs_reduction(upper, level)) { 1450 set = cloog_constraint_set_for_reduction(upper, lower); 1451 set = cloog_constraint_set_reduce(set, level, infos->equal, 1452 nb_par, &data.bound); 1453 cloog_constraint_set_foreach_constraint(set, 1454 insert_modulo_guard_constraint, &data); 1455 cloog_constraint_set_free(set); 1456 } else 1457 insert_modulo_guard_constraint(upper, &data); 1458 1459 cloog_int_clear(data.val); 1460 cloog_int_clear(data.bound); 1461 1462 return !data.empty; 1463} 1464 1465 1466/** 1467 * We found an equality or a pair of inequalities identifying 1468 * a loop with a single iteration, but the user wants us to generate 1469 * a loop anyway, so we do it here. 1470 */ 1471static int insert_equation_as_loop(CloogDomain *domain, CloogConstraint *upper, 1472 CloogConstraint *lower, int level, struct clast_stmt ***next, 1473 CloogInfos *infos) 1474{ 1475 const char *iterator = cloog_names_name_at_level(infos->names, level); 1476 struct clast_expr *e1, *e2; 1477 struct clast_for *f; 1478 1479 e2 = clast_bound_from_constraint(upper, level, infos->names); 1480 if (!cloog_constraint_is_valid(lower)) 1481 e1 = clast_expr_copy(e2); 1482 else 1483 e1 = clast_bound_from_constraint(lower, level, infos->names); 1484 1485 f = new_clast_for(domain, iterator, e1, e2, infos->stride[level-1]); 1486 **next = &f->stmt; 1487 *next = &f->body; 1488 1489 cloog_constraint_release(lower); 1490 cloog_constraint_release(upper); 1491 return 1; 1492} 1493 1494 1495/** 1496 * insert_equation function: 1497 * This function inserts an equality 1498 * constraint according to an element in the clast. 1499 * Returns 1 if the calling function should recurse into inner loops. 1500 * 1501 * An equality can be preceded by a 'modulo guard'. 1502 * For instance, consider the constraint i -2*j = 0 and the 1503 * element j: pprint_equality should return 'if(i%2==0) { j = i/2 ;'. 1504 * - matrix is the polyhedron containing all the constraints, 1505 * - num is the line number of the constraint in matrix we want to print, 1506 * - level is the column number of the element in matrix we want to use, 1507 * - the infos structure gives the user some options about code printing, 1508 * the number of parameters in matrix (nb_par), and the arrays of iterator 1509 * names and parameters (iters and params). 1510 ** 1511 * - November 13th 2001: first version. 1512 * - June 26th 2003: simplification of the modulo guards (remove parts such as 1513 * modulo is 0, compare vivien or vivien2 with a previous 1514 * version for an idea). 1515 * - June 29th 2003: non-unit strides support. 1516 * - July 14th 2003: (debug) no more print the constant in the modulo guard when 1517 * it was previously included in a stride calculation. 1518 */ 1519static int insert_equation(CloogDomain *domain, CloogConstraint *upper, 1520 CloogConstraint *lower, int level, struct clast_stmt 1521 ***next, CloogInfos *infos) 1522{ 1523 struct clast_expr *e; 1524 struct clast_assignment *ass; 1525 1526 if (!infos->options->otl) 1527 return insert_equation_as_loop(domain, upper, lower, level, next, infos); 1528 1529 if (!insert_modulo_guard(upper, lower, level, next, infos)) { 1530 cloog_constraint_release(lower); 1531 cloog_constraint_release(upper); 1532 1533 return 0; 1534 } 1535 1536 if (cloog_constraint_is_valid(lower) || 1537 !clast_equal_add(infos->equal, NULL, level, upper, infos)) 1538 { /* Finally, the equality. */ 1539 1540 /* If we have to make a block by dimension, we start the block. Function 1541 * pprint knows if there is an equality, if this is the case, it checks 1542 * for the same following condition to close the brace. 1543 */ 1544 if (infos->options->block) { 1545 struct clast_block *b = new_clast_block(); 1546 **next = &b->stmt; 1547 *next = &b->body; 1548 } 1549 1550 e = clast_bound_from_constraint(upper, level, infos->names); 1551 ass = new_clast_assignment(cloog_names_name_at_level(infos->names, level), e); 1552 1553 **next = &ass->stmt; 1554 *next = &(**next)->next; 1555 } 1556 1557 cloog_constraint_release(lower); 1558 cloog_constraint_release(upper); 1559 1560 return 1; 1561} 1562 1563 1564/** 1565 * Insert a loop that is executed exactly once as an assignment. 1566 * In particular, the loop 1567 * 1568 * for (i = e; i <= e; ++i) { 1569 * S; 1570 * } 1571 * 1572 * is generated as 1573 * 1574 * i = e; 1575 * S; 1576 * 1577 */ 1578static void insert_otl_for(CloogConstraintSet *constraints, int level, 1579 struct clast_expr *e, struct clast_stmt ***next, CloogInfos *infos) 1580{ 1581 const char *iterator; 1582 1583 iterator = cloog_names_name_at_level(infos->names, level); 1584 1585 if (!clast_equal_add(infos->equal, constraints, level, 1586 cloog_constraint_invalid(), infos)) { 1587 struct clast_assignment *ass; 1588 if (infos->options->block) { 1589 struct clast_block *b = new_clast_block(); 1590 **next = &b->stmt; 1591 *next = &b->body; 1592 } 1593 ass = new_clast_assignment(iterator, e); 1594 **next = &ass->stmt; 1595 *next = &(**next)->next; 1596 } else { 1597 free_clast_expr(e); 1598 } 1599} 1600 1601 1602/** 1603 * Insert a loop that is executed at most once as an assignment followed 1604 * by a guard. In particular, the loop 1605 * 1606 * for (i = e1; i <= e2; ++i) { 1607 * S; 1608 * } 1609 * 1610 * is generated as 1611 * 1612 * i = e1; 1613 * if (i <= e2) { 1614 * S; 1615 * } 1616 * 1617 */ 1618static void insert_guarded_otl_for(CloogConstraintSet *constraints, int level, 1619 struct clast_expr *e1, struct clast_expr *e2, 1620 struct clast_stmt ***next, CloogInfos *infos) 1621{ 1622 const char *iterator; 1623 struct clast_assignment *ass; 1624 struct clast_guard *guard; 1625 1626 iterator = cloog_names_name_at_level(infos->names, level); 1627 1628 if (infos->options->block) { 1629 struct clast_block *b = new_clast_block(); 1630 **next = &b->stmt; 1631 *next = &b->body; 1632 } 1633 ass = new_clast_assignment(iterator, e1); 1634 **next = &ass->stmt; 1635 *next = &(**next)->next; 1636 1637 guard = new_clast_guard(1); 1638 guard->eq[0].sign = -1; 1639 guard->eq[0].LHS = &new_clast_term(infos->state->one, 1640 &new_clast_name(iterator)->expr)->expr; 1641 guard->eq[0].RHS = e2; 1642 1643 **next = &guard->stmt; 1644 *next = &guard->then; 1645} 1646 1647 1648/** 1649 * insert_for function: 1650 * This function inserts a for loop in the clast. 1651 * Returns 1 if the calling function should recurse into inner loops. 1652 * 1653 * A loop header according to an element is the conjunction of a minimum and a 1654 * maximum on a given element (they give the loop bounds). 1655 * For instance, considering these constraints and the element j: 1656 * i + j -9*M >= 0 1657 * -j +5*M >= 0 1658 * j -4*M >= 0 1659 * this function should return 'for (j=max(-i+9*M,4*M),j<=5*M;j++) {'. 1660 * - constraints contains all constraints, 1661 * - level is the column number of the element in matrix we want to use, 1662 * - otl is set if the loop is executed at most once, 1663 * - the infos structure gives the user some options about code printing, 1664 * the number of parameters in matrix (nb_par), and the arrays of iterator 1665 * names and parameters (iters and params). 1666 */ 1667static int insert_for(CloogDomain *domain, CloogConstraintSet *constraints, 1668 int level, int otl, struct clast_stmt ***next, 1669 CloogInfos *infos) 1670{ 1671 const char *iterator; 1672 struct clast_expr *e1; 1673 struct clast_expr *e2; 1674 1675 e1 = clast_minmax(constraints, level, 1, 0, 1, 0, infos); 1676 e2 = clast_minmax(constraints, level, 0, 0, 0, 0, infos); 1677 1678 if (clast_expr_is_bigger_constant(e1, e2)) { 1679 free_clast_expr(e1); 1680 free_clast_expr(e2); 1681 return 0; 1682 } 1683 1684 /* If min and max are not equal there is a 'for' else, there is a '='. 1685 * In the special case e1 = e2 = NULL, this is an infinite loop 1686 * so this is not a '='. 1687 */ 1688 if (e1 && e2 && infos->options->otl && clast_expr_equal(e1, e2)) { 1689 free_clast_expr(e2); 1690 insert_otl_for(constraints, level, e1, next, infos); 1691 } else if (otl) { 1692 insert_guarded_otl_for(constraints, level, e1, e2, next, infos); 1693 } else { 1694 struct clast_for *f; 1695 iterator = cloog_names_name_at_level(infos->names, level); 1696 1697 f = new_clast_for(domain, iterator, e1, e2, infos->stride[level-1]); 1698 **next = &f->stmt; 1699 *next = &f->body; 1700 } 1701 1702 return 1; 1703} 1704 1705 1706/** 1707 * insert_block function: 1708 * This function inserts a statement block. 1709 * - block is the statement block, 1710 * - level is the number of loops enclosing the statement, 1711 * - the infos structure gives the user some options about code printing, 1712 * the number of parameters in domain (nb_par), and the arrays of iterator 1713 * names and parameters (iters and params). 1714 ** 1715 * - September 21th 2003: first version (pick from pprint function). 1716 */ 1717static void insert_block(CloogDomain *domain, CloogBlock *block, int level, 1718 struct clast_stmt ***next, CloogInfos *infos) 1719{ 1720 CloogStatement * statement ; 1721 struct clast_stmt *subs; 1722 1723 if (!block) 1724 return; 1725 1726 for (statement = block->statement; statement; statement = statement->next) { 1727 CloogStatement *s_next = statement->next; 1728 1729 subs = clast_equal(level,infos); 1730 1731 statement->next = NULL; 1732 **next = &new_clast_user_stmt(domain, statement, subs)->stmt; 1733 statement->next = s_next; 1734 *next = &(**next)->next; 1735 } 1736} 1737 1738 1739/** 1740 * insert_loop function: 1741 * This function converts the content of a CloogLoop structure (loop) into a 1742 * clast_stmt (inserted at **next). 1743 * The iterator (level) of 1744 * the current loop is given by 'level': this is the column number of the 1745 * domain corresponding to the current loop iterator. The data of a loop are 1746 * written in this order: 1747 * 1. The guard of the loop, i.e. each constraint in the domain that does not 1748 * depend on the iterator (when the entry in the column 'level' is 0). 1749 * 2. The iteration domain of the iterator, given by the constraints in the 1750 * domain depending on the iterator, i.e.: 1751 * * an equality if the iterator has only one value (possibly preceded by 1752 * a guard verifying if this value is integral), *OR* 1753 * * a loop from the minimum possible value of the iterator to the maximum 1754 * possible value. 1755 * 3. The included statement block. 1756 * 4. The inner loops (recursive call). 1757 * 5. The following loops (recursive call). 1758 * - level is the recursion level or the iteration level that we are printing, 1759 * - the infos structure gives the user some options about code printing, 1760 * the number of parameters in domain (nb_par), and the arrays of iterator 1761 * names and parameters (iters and params). 1762 ** 1763 * - November 2nd 2001: first version. 1764 * - March 6th 2003: infinite domain support. 1765 * - April 19th 2003: (debug) NULL loop support. 1766 * - June 29th 2003: non-unit strides support. 1767 * - April 28th 2005: (debug) level is level+equality when print statement! 1768 * - June 16th 2005: (debug) the N. Vasilache normalization step has been 1769 * added to avoid iteration duplication (see DaeGon Kim 1770 * bug in cloog_program_generate). Try vasilache.cloog 1771 * with and without the call to cloog_polylib_matrix_normalize, 1772 * using -f 8 -l 9 options for an idea. 1773 * - September 15th 2005: (debug) don't close equality braces when unnecessary. 1774 * - October 16th 2005: (debug) scalar value is saved for next loops. 1775 */ 1776static void insert_loop(CloogLoop * loop, int level, 1777 struct clast_stmt ***next, CloogInfos *infos) 1778{ 1779 int equality = 0; 1780 CloogConstraintSet *constraints, *temp; 1781 struct clast_stmt **top = *next; 1782 CloogConstraint *i, *j; 1783 int empty_loop = 0; 1784 1785 /* It can happen that loop be NULL when an input polyhedron is empty. */ 1786 if (loop == NULL) 1787 return; 1788 1789 /* The constraints do not always have a shape that allows us to generate code from it, 1790 * thus we normalize it, we also simplify it with the equalities. 1791 */ 1792 temp = cloog_domain_constraints(loop->domain); 1793 cloog_constraint_set_normalize(temp,level); 1794 constraints = cloog_constraint_set_simplify(temp,infos->equal,level, 1795 infos->names->nb_parameters); 1796 cloog_constraint_set_free(temp); 1797 if (level) { 1798 infos->stride[level - 1] = loop->stride; 1799 infos->stride_level++; 1800 } 1801 1802 /* First of all we have to print the guard. */ 1803 insert_guard(constraints,level, next, infos); 1804 1805 if (level && cloog_constraint_set_contains_level(constraints, level, 1806 infos->names->nb_parameters)) { 1807 /* We scan all the constraints to know in which case we are : 1808 * [[if] equation] or [for]. 1809 */ 1810 if (cloog_constraint_is_valid(i = 1811 cloog_constraint_set_defining_equality(constraints, level))) { 1812 empty_loop = !insert_equation(loop->unsimplified, i, 1813 cloog_constraint_invalid(), level, next, 1814 infos); 1815 equality = 1 ; 1816 } else if (cloog_constraint_is_valid(i = 1817 cloog_constraint_set_defining_inequalities(constraints, 1818 level, &j, infos->names->nb_parameters))) { 1819 empty_loop = !insert_equation(loop->unsimplified, i, j, level, next, 1820 infos); 1821 } else 1822 empty_loop = !insert_for(loop->unsimplified, constraints, level, 1823 loop->otl, next, infos); 1824 } 1825 1826 if (!empty_loop) { 1827 /* Finally, if there is an included statement block, print it. */ 1828 insert_block(loop->unsimplified, loop->block, level+equality, next, infos); 1829 1830 /* Go to the next level. */ 1831 if (loop->inner != NULL) 1832 insert_loop(loop->inner, level+1, next, infos); 1833 } 1834 1835 if (level) { 1836 cloog_equal_del(infos->equal,level); 1837 infos->stride_level--; 1838 } 1839 cloog_constraint_set_free(constraints); 1840 1841 /* Go to the next loop on the same level. */ 1842 while (*top) 1843 top = &(*top)->next; 1844 if (loop->next != NULL) 1845 insert_loop(loop->next, level, &top,infos); 1846} 1847 1848 1849struct clast_stmt *cloog_clast_create(CloogProgram *program, 1850 CloogOptions *options) 1851{ 1852 CloogInfos *infos = ALLOC(CloogInfos); 1853 int nb_levels; 1854 struct clast_stmt *root = &new_clast_root(program->names)->stmt; 1855 struct clast_stmt **next = &root->next; 1856 1857 infos->state = options->state; 1858 infos->names = program->names; 1859 infos->options = options; 1860 infos->scaldims = program->scaldims; 1861 infos->nb_scattdims = program->nb_scattdims; 1862 1863 /* Allocation for the array of strides, there is a +1 since the statement can 1864 * be included inside an external loop without iteration domain. 1865 */ 1866 nb_levels = program->names->nb_scattering+program->names->nb_iterators+1; 1867 infos->stride = ALLOCN(CloogStride *, nb_levels); 1868 infos->stride_level = 0; 1869 1870 infos->equal = cloog_equal_alloc(nb_levels, 1871 nb_levels, program->names->nb_parameters); 1872 1873 insert_loop(program->loop, 0, &next, infos); 1874 1875 cloog_equal_free(infos->equal); 1876 1877 free(infos->stride); 1878 free(infos); 1879 1880 return root; 1881} 1882 1883 1884struct clast_stmt *cloog_clast_create_from_input(CloogInput *input, 1885 CloogOptions *options) 1886{ 1887 CloogProgram *program; 1888 struct clast_stmt *root; 1889 1890 program = cloog_program_alloc(input->context, input->ud, options); 1891 free(input); 1892 1893 program = cloog_program_generate(program, options); 1894 1895 root = cloog_clast_create(program, options); 1896 cloog_program_free(program); 1897 1898 return root; 1899} 1900 1901/* Adds to the list if not already in it */ 1902static int add_if_new(void **list, int num, void *new, int size) 1903{ 1904 int i; 1905 1906 for (i=0; i<num; i++) { 1907 if (!memcmp((*list) + i*size, new, size)) break; 1908 } 1909 1910 if (i==num) { 1911 *list = realloc(*list, (num+1)*size); 1912 memcpy(*list + num*size, new, size); 1913 return 1; 1914 } 1915 1916 return 0; 1917} 1918 1919 1920/* Concatenates all elements of list2 that are not in list1; 1921 * Returns the new size of the list */ 1922int concat_if_new(void **list1, int num1, void *list2, int num2, int size) 1923{ 1924 int i, ret; 1925 1926 for (i=0; i<num2; i++) { 1927 ret = add_if_new(list1, num1, (char *)list2 + i*size, size); 1928 if (ret) num1++; 1929 } 1930 1931 return num1; 1932} 1933 1934/* Compares list1 to list2 1935 * Returns 0 if both have the same elements; returns -1 if all elements of 1936 * list1 are strictly contained in list2; 1 otherwise 1937 */ 1938int list_compare(const int *list1, int num1, const int *list2, int num2) 1939{ 1940 int i, j; 1941 1942 for (i=0; i<num1; i++) { 1943 for (j=0; j<num2; j++) { 1944 if (list1[i] == list2[j]) break; 1945 } 1946 if (j==num2) break; 1947 } 1948 if (i==num1) { 1949 if (num1 == num2) { 1950 return 0; 1951 } 1952 return -1; 1953 } 1954 1955 return 1; 1956} 1957 1958 1959 1960/* 1961 * A multi-purpose function to traverse and get information on Clast 1962 * loops 1963 * 1964 * node: clast node where processing should start 1965 * 1966 * Returns: 1967 * A list of loops under clast_stmt 'node' filtered in two ways: (1) it contains 1968 * statements appearing in 'stmts_filter', (2) loop iterator's name is 'iter' 1969 * If iter' is set to NULL, no filtering based on iterator name is done 1970 * 1971 * iter: loop iterator name 1972 * stmts_filter: list of statement numbers for filtering (1-indexed) 1973 * nstmts_filter: number of statements in stmts_filter 1974 * 1975 * FilterType: match exact (i.e., loops containing only and all those statements 1976 * in stmts_filter) or subset, i.e., loops which have only those statements 1977 * that appear in stmts_filter 1978 * 1979 * To disable all filtering, set 'iter' to NULL, provide all statement 1980 * numbers in 'stmts_filter' and set FilterType to subset 1981 * 1982 * Return fields 1983 * 1984 * stmts: an array of statement numbers under node 1985 * nstmts: number of stmt numbers pointed to by stmts 1986 * loops: list of clast loops 1987 * nloops: number of clast loops in loops 1988 * 1989 */ 1990void clast_filter(struct clast_stmt *node, 1991 ClastFilter filter, 1992 struct clast_for ***loops, int *nloops, 1993 int **stmts, int *nstmts) 1994{ 1995 int num_next_stmts, num_next_loops, ret, *stmts_next; 1996 struct clast_for **loops_next; 1997 1998 *loops = NULL; 1999 *nloops = 0; 2000 *nstmts = 0; 2001 *stmts = NULL; 2002 2003 if (node == NULL) { 2004 return; 2005 } 2006 2007 ClastFilterType filter_type = filter.filter_type; 2008 const char *iter = filter.iter; 2009 int nstmts_filter = filter.nstmts_filter; 2010 const int *stmts_filter = filter.stmts_filter; 2011 2012 if (CLAST_STMT_IS_A(node, stmt_root)) { 2013 // printf("root stmt\n"); 2014 struct clast_root *root = (struct clast_root *) node; 2015 clast_filter((root->stmt).next, filter, &loops_next, 2016 &num_next_loops, &stmts_next, &num_next_stmts); 2017 *nstmts = concat_if_new((void **)stmts, *nstmts, stmts_next, num_next_stmts, sizeof(int)); 2018 *nloops = concat_if_new((void **)loops, *nloops, loops_next, num_next_loops, 2019 sizeof(struct clast_stmt *)); 2020 free(loops_next); 2021 free(stmts_next); 2022 } 2023 2024 if (CLAST_STMT_IS_A(node, stmt_guard)) { 2025 // printf("guard stmt\n"); 2026 struct clast_guard *guard = (struct clast_guard *) node; 2027 clast_filter(guard->then, filter, &loops_next, 2028 &num_next_loops, &stmts_next, &num_next_stmts); 2029 *nstmts = concat_if_new((void **)stmts, *nstmts, stmts_next, num_next_stmts, sizeof(int)); 2030 *nloops = concat_if_new((void **)loops, *nloops, loops_next, num_next_loops, 2031 sizeof(struct clast_stmt *)); 2032 free(loops_next); 2033 free(stmts_next); 2034 clast_filter((guard->stmt).next, filter, &loops_next, 2035 &num_next_loops, &stmts_next, &num_next_stmts); 2036 *nstmts = concat_if_new((void **)stmts, *nstmts, stmts_next, num_next_stmts, sizeof(int)); 2037 *nloops = concat_if_new((void **)loops, *nloops, loops_next, num_next_loops, 2038 sizeof(struct clast_stmt *)); 2039 free(loops_next); 2040 free(stmts_next); 2041 } 2042 2043 if (CLAST_STMT_IS_A(node, stmt_user)) { 2044 struct clast_user_stmt *user_stmt = (struct clast_user_stmt *) node; 2045 // printf("user stmt: S%d\n", user_stmt->statement->number); 2046 ret = add_if_new((void **)stmts, *nstmts, &user_stmt->statement->number, sizeof(int)); 2047 if (ret) (*nstmts)++; 2048 clast_filter((user_stmt->stmt).next, filter, &loops_next, 2049 &num_next_loops, &stmts_next, &num_next_stmts); 2050 *nstmts = concat_if_new((void **)stmts, *nstmts, stmts_next, num_next_stmts, sizeof(int)); 2051 *nloops = concat_if_new((void **)loops, *nloops, loops_next, num_next_loops, 2052 sizeof(struct clast_stmt *)); 2053 free(loops_next); 2054 free(stmts_next); 2055 } 2056 if (CLAST_STMT_IS_A(node, stmt_for)) { 2057 struct clast_for *for_stmt = (struct clast_for *) node; 2058 clast_filter(for_stmt->body, filter, &loops_next, 2059 &num_next_loops, &stmts_next, &num_next_stmts); 2060 *nstmts = concat_if_new((void **)stmts, *nstmts, stmts_next, num_next_stmts, sizeof(int)); 2061 *nloops = concat_if_new((void **)loops, *nloops, loops_next, num_next_loops, 2062 sizeof(struct clast_stmt *)); 2063 2064 if (iter == NULL || !strcmp(for_stmt->iterator, iter)) { 2065 if (stmts_filter == NULL || 2066 (filter_type == subset && list_compare(stmts_next, num_next_stmts, 2067 stmts_filter, nstmts_filter) <= 0) 2068 || (filter_type == exact && list_compare(stmts_next, num_next_stmts, 2069 stmts_filter, nstmts_filter) == 0 )) { 2070 ret = add_if_new((void **)loops, *nloops, &for_stmt, sizeof(struct clast_for *)); 2071 if (ret) (*nloops)++; 2072 } 2073 } 2074 free(loops_next); 2075 free(stmts_next); 2076 2077 clast_filter((for_stmt->stmt).next, filter, &loops_next, 2078 &num_next_loops, &stmts_next, &num_next_stmts); 2079 *nstmts = concat_if_new((void **)stmts, *nstmts, stmts_next, num_next_stmts, sizeof(int)); 2080 *nloops = concat_if_new((void **)loops, *nloops, loops_next, num_next_loops, 2081 sizeof(struct clast_stmt *)); 2082 free(loops_next); 2083 free(stmts_next); 2084 } 2085} 2086