1 2 /*+-----------------------------------------------------------------** 3 ** OpenScop Library ** 4 **-----------------------------------------------------------------** 5 ** relation.c ** 6 **-----------------------------------------------------------------** 7 ** First version: 30/04/2008 ** 8 **-----------------------------------------------------------------** 9 10 11 ***************************************************************************** 12 * OpenScop: Structures and formats for polyhedral tools to talk together * 13 ***************************************************************************** 14 * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, * 15 * / / / // // // // / / / // // / / // / /|,_, * 16 * / / / // // // // / / / // // / / // / / / /\ * 17 * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ * 18 * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ * 19 * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ * 20 * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ * 21 * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ * 22 * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ * 23 * | I | | | | e | | | | | | | | | | | | | \ \ \ * 24 * | T | | | | | | | | | | | | | | | | | \ \ \ * 25 * | E | | | | | | | | | | | | | | | | | \ \ \ * 26 * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ * 27 * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / * 28 * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' * 29 * * 30 * Copyright (C) 2008 University Paris-Sud 11 and INRIA * 31 * * 32 * (3-clause BSD license) * 33 * Redistribution and use in source and binary forms, with or without * 34 * modification, are permitted provided that the following conditions * 35 * are met: * 36 * * 37 * 1. Redistributions of source code must retain the above copyright notice, * 38 * this list of conditions and the following disclaimer. * 39 * 2. Redistributions in binary form must reproduce the above copyright * 40 * notice, this list of conditions and the following disclaimer in the * 41 * documentation and/or other materials provided with the distribution. * 42 * 3. The name of the author may not be used to endorse or promote products * 43 * derived from this software without specific prior written permission. * 44 * * 45 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * 46 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * 47 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * 48 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * 49 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * 50 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * 51 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * 52 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * 53 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * 54 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * 55 * * 56 * OpenScop Library, a library to manipulate OpenScop formats and data * 57 * structures. Written by: * 58 * Cedric Bastoul <Cedric.Bastoul@u-psud.fr> and * 59 * Louis-Noel Pouchet <Louis-Noel.pouchet@inria.fr> * 60 * * 61 *****************************************************************************/ 62 63 64#include <stdlib.h> 65#include <stdio.h> 66#include <string.h> 67#include <ctype.h> 68 69#include <osl/macros.h> 70#include <osl/int.h> 71#include <osl/util.h> 72#include <osl/vector.h> 73#include <osl/strings.h> 74#include <osl/names.h> 75#include <osl/relation.h> 76 77 78/*+*************************************************************************** 79 * Structure display function * 80 *****************************************************************************/ 81 82 83/** 84 * osl_relation_sprint_type function: 85 * this function prints the textual type of an osl_relation_t structure into 86 * a string, according to the OpenScop specification, and returns that string. 87 * \param[in] relation The relation whose type has to be printed. 88 * \return A string containing the relation type. 89 */ 90static 91char * osl_relation_sprint_type(osl_relation_p relation) { 92 char * string = NULL; 93 94 OSL_malloc(string, char *, OSL_MAX_STRING * sizeof(char)); 95 string[0] = '\0'; 96 97 if (relation != NULL) { 98 switch (relation->type) { 99 case OSL_UNDEFINED: { 100 snprintf(string, OSL_MAX_STRING, OSL_STRING_UNDEFINED); 101 break; 102 } 103 case OSL_TYPE_CONTEXT: { 104 snprintf(string, OSL_MAX_STRING, OSL_STRING_CONTEXT); 105 break; 106 } 107 case OSL_TYPE_DOMAIN: { 108 snprintf(string, OSL_MAX_STRING, OSL_STRING_DOMAIN); 109 break; 110 } 111 case OSL_TYPE_SCATTERING: { 112 snprintf(string, OSL_MAX_STRING, OSL_STRING_SCATTERING); 113 break; 114 } 115 case OSL_TYPE_READ: { 116 snprintf(string, OSL_MAX_STRING, OSL_STRING_READ); 117 break; 118 } 119 case OSL_TYPE_WRITE: { 120 snprintf(string, OSL_MAX_STRING, OSL_STRING_WRITE); 121 break; 122 } 123 case OSL_TYPE_MAY_WRITE: { 124 snprintf(string, OSL_MAX_STRING, OSL_STRING_MAY_WRITE); 125 break; 126 } 127 default: { 128 OSL_warning("unknown relation type, " 129 "replaced with "OSL_STRING_UNDEFINED); 130 snprintf(string, OSL_MAX_STRING, OSL_STRING_UNDEFINED); 131 } 132 } 133 } 134 135 return string; 136} 137 138 139/** 140 * osl_relation_print_type function: 141 * this function displays the textual type of an osl_relation_t structure into 142 * a file (file, possibly stdout), according to the OpenScop specification. 143 * \param[in] file File where informations are printed. 144 * \param[in] relation The relation whose type has to be printed. 145 */ 146static 147void osl_relation_print_type(FILE * file, osl_relation_p relation) { 148 char * string = osl_relation_sprint_type(relation); 149 fprintf(file, "%s", string); 150 free(string); 151} 152 153 154/** 155 * osl_relation_idump function: 156 * this function displays a osl_relation_t structure (*relation) into a 157 * file (file, possibly stdout) in a way that trends to be understandable. 158 * It includes an indentation level (level) in order to work with others 159 * idump functions. 160 * \param[in] file File where informations are printed. 161 * \param[in] relation The relation whose information has to be printed. 162 * \param[in] level Number of spaces before printing, for each line. 163 */ 164void osl_relation_idump(FILE * file, osl_relation_p relation, int level) { 165 int i, j, first = 1; 166 167 // Go to the right level. 168 for (j = 0; j < level; j++) 169 fprintf(file, "|\t"); 170 171 if (relation != NULL) { 172 fprintf(file, "+-- osl_relation_t ("); 173 osl_relation_print_type(file, relation); 174 fprintf(file, ", "); 175 osl_int_dump_precision(file, relation->precision); 176 fprintf(file, ")\n"); 177 } 178 else { 179 fprintf(file, "+-- NULL relation\n"); 180 } 181 182 while (relation != NULL) { 183 if (! first) { 184 // Go to the right level. 185 for (j = 0; j < level; j++) 186 fprintf(file, "|\t"); 187 fprintf(file, "| osl_relation_t ("); 188 osl_relation_print_type(file, relation); 189 fprintf(file, ", "); 190 osl_int_dump_precision(file, relation->precision); 191 fprintf(file, ")\n"); 192 } 193 else 194 first = 0; 195 196 // A blank line 197 for(j = 0; j <= level; j++) 198 fprintf(file, "|\t"); 199 fprintf(file, "%d %d %d %d %d %d\n", 200 relation->nb_rows, relation->nb_columns, 201 relation->nb_output_dims, relation->nb_input_dims, 202 relation->nb_local_dims, relation->nb_parameters); 203 204 // Display the relation. 205 for (i = 0; i < relation->nb_rows; i++) { 206 for (j = 0; j <= level; j++) 207 fprintf(file, "|\t"); 208 209 fprintf(file, "[ "); 210 211 for (j = 0; j < relation->nb_columns; j++) { 212 osl_int_print(file, relation->precision, relation->m[i], j); 213 fprintf(file, " "); 214 } 215 216 fprintf(file, "]\n"); 217 } 218 219 relation = relation->next; 220 221 // Next line. 222 if (relation != NULL) { 223 for (j = 0; j <= level; j++) 224 fprintf(file, "|\t"); 225 fprintf(file, "|\n"); 226 for (j = 0; j <= level; j++) 227 fprintf(file, "|\t"); 228 fprintf(file, "V\n"); 229 } 230 } 231 232 // The last line. 233 for (j = 0; j <= level; j++) 234 fprintf(file, "|\t"); 235 fprintf(file, "\n"); 236} 237 238 239/** 240 * osl_relation_dump function: 241 * this function prints the content of a osl_relation_t structure 242 * (*relation) into a file (file, possibly stdout). 243 * \param[in] file File where informations are printed. 244 * \param[in] relation The relation whose information have to be printed. 245 */ 246void osl_relation_dump(FILE * file, osl_relation_p relation) { 247 osl_relation_idump(file, relation, 0); 248} 249 250 251/** 252 * osl_relation_expression_element function: 253 * this function returns a string containing the printing of a value (e.g., 254 * an iterator with its coefficient or a constant). 255 * \param[in] val Address of the coefficient or constant value. 256 * \param[in] precision The precision of the value. 257 * \param[in,out] first Pointer to a boolean set to 1 if the current value 258 * is the first of an expresion, 0 otherwise (maybe 259 * updated). 260 * \param[in] cst A boolean set to 1 if the value is a constant, 261 * 0 otherwise. 262 * \param[in] name String containing the name of the element. 263 * \return A string that contains the printing of a value. 264 */ 265static 266char * osl_relation_expression_element(void * val, 267 int precision, int * first, 268 int cst, char * name) { 269 char * temp, * body, * sval; 270 271 OSL_malloc(temp, char *, OSL_MAX_STRING * sizeof(char)); 272 OSL_malloc(body, char *, OSL_MAX_STRING * sizeof(char)); 273 OSL_malloc(sval, char *, OSL_MAX_STRING * sizeof(char)); 274 275 body[0] = '\0'; 276 sval[0] = '\0'; 277 278 // statements for the 'normal' processing. 279 if (!osl_int_zero(precision, val, 0) && (!cst)) { 280 if ((*first) || osl_int_neg(precision, val, 0)) { 281 if (osl_int_one(precision, val, 0)) { // case 1 282 sprintf(sval, "%s", name); 283 } 284 else { 285 if (osl_int_mone(precision, val, 0)) { // case -1 286 sprintf(sval, "-%s", name); 287 } 288 else { // default case 289 osl_int_sprint_txt(sval, precision, val, 0); 290 sprintf(temp, "*%s", name); 291 strcat(sval, temp); 292 } 293 } 294 *first = 0; 295 } 296 else { 297 if (osl_int_one(precision, val, 0)) { 298 sprintf(sval, "+%s", name); 299 } 300 else { 301 sprintf(sval, "+"); 302 osl_int_sprint_txt(temp, precision, val, 0); 303 strcat(sval, temp); 304 sprintf(temp, "*%s", name); 305 strcat(sval, temp); 306 } 307 } 308 } 309 else { 310 if (cst) { 311 if ((osl_int_zero(precision, val, 0) && (*first)) || 312 (osl_int_neg(precision, val, 0))) 313 osl_int_sprint_txt(sval, precision, val, 0); 314 if (osl_int_pos(precision, val, 0)) { 315 if (!(*first)) { 316 sprintf(sval, "+"); 317 osl_int_sprint_txt(temp, precision, val, 0); 318 strcat(sval, temp); 319 } 320 else { 321 osl_int_sprint_txt(sval, precision, val, 0); 322 } 323 } 324 } 325 } 326 free(temp); 327 free(body); 328 329 return(sval); 330} 331 332 333/** 334 * osl_relation_strings function: 335 * this function creates a NULL-terminated array of strings from an 336 * osl_names_t structure in such a way that the ith string is the "name" 337 * corresponding to the ith column of the constraint matrix. 338 * \param[in] relation The relation for which we need an array of names. 339 * \param[in] names The set of names for each element. 340 * \return An array of strings with one string per constraint matrix column. 341 */ 342static 343char ** osl_relation_strings(osl_relation_p relation, osl_names_p names) { 344 char ** strings; 345 char temp[OSL_MAX_STRING]; 346 int i, offset, array_id; 347 348 if ((relation == NULL) || (names == NULL)) { 349 OSL_debug("no names or relation to build the name array"); 350 return NULL; 351 } 352 353 OSL_malloc(strings, char **, (relation->nb_columns + 1)*sizeof(char *)); 354 strings[relation->nb_columns] = NULL; 355 356 // 1. Equality/inequality marker. 357 OSL_strdup(strings[0], "e/i"); 358 offset = 1; 359 360 // 2. Output dimensions. 361 if (osl_relation_is_access(relation)) { 362 // The first output dimension is the array name. 363 array_id = osl_relation_get_array_id(relation); 364 OSL_strdup(strings[offset], "Arr"); 365 // The other ones are the array dimensions [1]...[n] 366 for (i = offset + 1; i < relation->nb_output_dims + offset; i++) { 367 sprintf(temp, "[%d]", i - 1); 368 OSL_strdup(strings[i], temp); 369 } 370 } 371 else 372 if (relation->type == OSL_TYPE_SCATTERING) { 373 for (i = offset; i < relation->nb_output_dims + offset; i++) { 374 OSL_strdup(strings[i], names->scatt_dims->string[i - offset]); 375 } 376 } 377 else { 378 for (i = offset; i < relation->nb_output_dims + offset; i++) { 379 OSL_strdup(strings[i], names->iterators->string[i - offset]); 380 } 381 } 382 offset += relation->nb_output_dims; 383 384 // 3. Input dimensions. 385 for (i = offset; i < relation->nb_input_dims + offset; i++) 386 OSL_strdup(strings[i], names->iterators->string[i - offset]); 387 offset += relation->nb_input_dims; 388 389 // 4. Local dimensions. 390 for (i = offset; i < relation->nb_local_dims + offset; i++) 391 OSL_strdup(strings[i], names->local_dims->string[i - offset]); 392 offset += relation->nb_local_dims; 393 394 // 5. Parameters. 395 for (i = offset; i < relation->nb_parameters + offset; i++) 396 OSL_strdup(strings[i], names->parameters->string[i - offset]); 397 offset += relation->nb_parameters; 398 399 // 6. Scalar. 400 OSL_strdup(strings[offset], "1"); 401 402 return strings; 403} 404 405 406/** 407 * osl_relation_subexpression function: 408 * this function returns a string corresponding to an affine (sub-)expression 409 * stored at the "row"^th row of the relation pointed by "relation" between 410 * the start and stop columns. Optionally it may oppose the whole expression. 411 * \param[in] relation A set of linear expressions. 412 * \param[in] row The row corresponding to the expression. 413 * \param[in] start The first column for the expression (inclusive). 414 * \param[in] stop The last column for the expression (inclusive). 415 * \param[in] oppose Boolean set to 1 to negate the expression, 0 otherwise. 416 * \param[in] strings Array of textual names of the various elements. 417 * \return A string that contains the printing of an affine (sub-)expression. 418 */ 419static 420char * osl_relation_subexpression(osl_relation_p relation, 421 int row, int start, int stop, int oppose, 422 char ** strings) { 423 int i, first = 1, constant; 424 char * sval; 425 char * sline; 426 427 OSL_malloc(sline, char *, OSL_MAX_STRING * sizeof(char)); 428 sline[0] = '\0'; 429 430 // Create the expression. The constant is a special case. 431 for (i = start; i <= stop; i++) { 432 if (oppose) { 433 osl_int_oppose(relation->precision, 434 relation->m[row], i, relation->m[row], i); 435 } 436 437 if (i == relation->nb_columns - 1) 438 constant = 1; 439 else 440 constant = 0; 441 442 sval = osl_relation_expression_element( 443 osl_int_address(relation->precision, relation->m[row], i), 444 relation->precision, &first, constant, strings[i]); 445 446 if (oppose) { 447 osl_int_oppose(relation->precision, 448 relation->m[row], i, relation->m[row], i); 449 } 450 strcat(sline, sval); 451 free(sval); 452 } 453 454 return sline; 455} 456 457 458/** 459 * osl_relation_expression function: 460 * this function returns a string corresponding to an affine expression 461 * stored at the "row"^th row of the relation pointed by "relation". 462 * \param[in] relation A set of linear expressions. 463 * \param[in] row The row corresponding to the expression. 464 * \param[in] strings Array of textual names of the various elements. 465 * \return A string that contains the printing of an affine expression. 466 */ 467char * osl_relation_expression(osl_relation_p relation, 468 int row, char ** strings) { 469 470 return osl_relation_subexpression(relation, row, 471 1, relation->nb_columns - 1, 0, 472 strings); 473} 474 475 476/** 477 * osl_relation_is_simple_output function: 478 * this function returns 1 or -1 if a given constraint row of a relation 479 * corresponds to an output, 0 otherwise. We call a simple output an equality 480 * constraint where exactly one output coefficient is not 0 and is either 481 * 1 (in this case the function returns 1) or -1 (in this case the function 482 * returns -1). 483 * \param[in] relation The relation to test for simple output. 484 * \param[in] row The row corresponding to the constraint to test. 485 * \return 1 or -1 if the row is a simple output, 0 otherwise. 486 */ 487static 488int osl_relation_is_simple_output(osl_relation_p relation, int row) { 489 int i; 490 int first = 1; 491 int sign = 0; 492 493 if ((relation == NULL) || 494 (relation->m == NULL) || 495 (relation->nb_output_dims == 0)) 496 return 0; 497 498 if ((row < 0) || (row > relation->nb_rows)) 499 OSL_error("the specified row does not exist in the relation"); 500 501 // The constraint must be an equality. 502 if (!osl_int_zero(relation->precision, relation->m[row], 0)) 503 return 0; 504 505 // Check the output part has one and only one non-zero +1 or -1 coefficient. 506 first = 1; 507 for (i = 1; i <= relation->nb_output_dims; i++) { 508 if (!osl_int_zero(relation->precision, relation->m[row], i)) { 509 if (first) 510 first = 0; 511 else 512 return 0; 513 514 if (osl_int_one(relation->precision, relation->m[row], i)) 515 sign = 1; 516 else if (osl_int_mone(relation->precision, relation->m[row], i)) 517 sign = -1; 518 else 519 return 0; 520 } 521 } 522 523 return sign; 524} 525 526 527/** 528 * osl_relation_sprint_comment function: 529 * this function prints into a string a comment corresponding to a constraint 530 * of a relation, according to its type, then it returns this string. This 531 * function does not check that printing the comment is possible (i.e., are 532 * there enough names ?), hence it is the responsibility of the user to ensure 533 * he/she can call this function safely. 534 * \param[in] relation The relation for which a comment has to be printed. 535 * \param[in] row The constrain row for which a comment has to be printed. 536 * \param[in] strings Array of textual names of the various elements. 537 * \param[in] arrays Array of textual identifiers of the arrays. 538 * \return A string which contains the comment for the row. 539 */ 540static 541char * osl_relation_sprint_comment(osl_relation_p relation, int row, 542 char ** strings, char ** arrays) { 543 int sign; 544 int high_water_mark = OSL_MAX_STRING; 545 char * string = NULL; 546 char * expression; 547 char buffer[OSL_MAX_STRING]; 548 549 OSL_malloc(string, char *, high_water_mark * sizeof(char)); 550 string[0] = '\0'; 551 552 if ((relation == NULL) || (strings == NULL)) { 553 OSL_debug("no relation or names while asked to print a comment"); 554 return string; 555 } 556 557 if ((sign = osl_relation_is_simple_output(relation, row))) { 558 // First case : output == expression. 559 560 expression = osl_relation_subexpression(relation, row, 561 1, relation->nb_output_dims, 562 sign < 0, 563 strings); 564 snprintf(buffer, OSL_MAX_STRING, " ## %s", expression); 565 osl_util_safe_strcat(&string, buffer, &high_water_mark); 566 free(expression); 567 568 // We don't print the right hand side if it's an array identifier. 569 if (!osl_relation_is_access(relation) || 570 osl_int_zero(relation->precision, relation->m[row], 1)) { 571 expression = osl_relation_subexpression(relation, row, 572 relation->nb_output_dims + 1, 573 relation->nb_columns - 1, 574 sign > 0, 575 strings); 576 snprintf(buffer, OSL_MAX_STRING, " == %s", expression); 577 osl_util_safe_strcat(&string, buffer, &high_water_mark); 578 free(expression); 579 } 580 else { 581 snprintf(buffer, OSL_MAX_STRING, " == %s", 582 arrays[osl_relation_get_array_id(relation) - 1]); 583 osl_util_safe_strcat(&string, buffer, &high_water_mark); 584 } 585 } 586 else { 587 // Second case : general case. 588 589 expression = osl_relation_expression(relation, row, strings); 590 snprintf(buffer, OSL_MAX_STRING, " ## %s", expression); 591 osl_util_safe_strcat(&string, buffer, &high_water_mark); 592 free(expression); 593 594 if (osl_int_zero(relation->precision, relation->m[row], 0)) 595 snprintf(buffer, OSL_MAX_STRING, " == 0"); 596 else 597 snprintf(buffer, OSL_MAX_STRING, " >= 0"); 598 osl_util_safe_strcat(&string, buffer, &high_water_mark); 599 } 600 601 return string; 602} 603 604 605/** 606 * osl_relation_column_string function: 607 * this function returns an OpenScop comment string showing all column 608 * names. It is designed to nicely fit a constraint matrix that would be 609 * printed just below this line. 610 * \param[in] relation The relation related to the comment line to build. 611 * \param[in] strings Array of textual names of the various elements. 612 * \return A fancy comment string with all the dimension names. 613 */ 614static 615char * osl_relation_column_string(osl_relation_p relation, char ** strings) { 616 int i, j; 617 int index_output_dims; 618 int index_input_dims; 619 int index_local_dims; 620 int index_parameters; 621 int index_scalar; 622 int space, length, left, right; 623 char * scolumn; 624 char temp[OSL_MAX_STRING]; 625 626 OSL_malloc(scolumn, char *, OSL_MAX_STRING); 627 628 index_output_dims = 1; 629 index_input_dims = index_output_dims + relation->nb_output_dims; 630 index_local_dims = index_input_dims + relation->nb_input_dims; 631 index_parameters = index_local_dims + relation->nb_local_dims; 632 index_scalar = index_parameters + relation->nb_parameters; 633 634 // 1. The comment part. 635 sprintf(scolumn, "#"); 636 for (j = 0; j < (OSL_FMT_LENGTH - 1)/2 - 1; j++) 637 strcat(scolumn, " "); 638 639 i = 0; 640 while (strings[i] != NULL) { 641 space = OSL_FMT_LENGTH; 642 length = (space > strlen(strings[i])) ? strlen(strings[i]) : space; 643 right = (space - length + (OSL_FMT_LENGTH % 2)) / 2; 644 left = space - length - right; 645 646 // 2. Spaces before the name 647 for (j = 0; j < left; j++) 648 strcat(scolumn, " "); 649 650 // 3. The (abbreviated) name 651 for (j = 0; j < length - 1; j++) { 652 sprintf(temp, "%c", strings[i][j]); 653 strcat(scolumn, temp); 654 } 655 if (length >= strlen(strings[i])) 656 sprintf(temp, "%c", strings[i][j]); 657 else 658 sprintf(temp, "."); 659 strcat(scolumn, temp); 660 661 // 4. Spaces after the name 662 for (j = 0; j < right; j++) 663 strcat(scolumn, " "); 664 665 i++; 666 if ((i == index_output_dims) || 667 (i == index_input_dims) || 668 (i == index_local_dims) || 669 (i == index_parameters) || 670 (i == index_scalar)) 671 strcat(scolumn, "|"); 672 else 673 strcat(scolumn, " "); 674 } 675 strcat(scolumn, "\n"); 676 677 return scolumn; 678} 679 680 681/** 682 * osl_relation_names function: 683 * this function generates as set of names for all the dimensions 684 * involved in a given relation. 685 * \param[in] relation The relation we have to generate names for. 686 * \return A set of generated names for the input relation dimensions. 687 */ 688static 689osl_names_p osl_relation_names(osl_relation_p relation) { 690 int nb_parameters = OSL_UNDEFINED; 691 int nb_iterators = OSL_UNDEFINED; 692 int nb_scattdims = OSL_UNDEFINED; 693 int nb_localdims = OSL_UNDEFINED; 694 int array_id = OSL_UNDEFINED; 695 696 osl_relation_get_attributes(relation, &nb_parameters, &nb_iterators, 697 &nb_scattdims, &nb_localdims, &array_id); 698 699 return osl_names_generate("P", nb_parameters, 700 "i", nb_iterators, 701 "c", nb_scattdims, 702 "l", nb_localdims, 703 "A", array_id); 704} 705 706 707/** 708 * osl_relation_nb_components function: 709 * this function returns the number of component in the union of relations 710 * provided as parameter. 711 * \param[in] relation The input union of relations. 712 * \return The number of components in the input union of relations. 713 */ 714int osl_relation_nb_components(osl_relation_p relation) { 715 int nb_components = 0; 716 717 while (relation != NULL) { 718 nb_components++; 719 relation = relation->next; 720 } 721 722 return nb_components; 723} 724 725 726/** 727 * osl_relation_spprint_polylib function: 728 * this function pretty-prints the content of an osl_relation_t structure 729 * (*relation) into a string in the extended polylib format, and returns this 730 * string. This format is the same as OpenScop's, minus the type. 731 * \param[in] relation The relation whose information has to be printed. 732 * \param[in] names The names of the constraint columns for comments. 733 * \return A string containing the relation pretty-printing. 734 */ 735char * osl_relation_spprint_polylib(osl_relation_p relation, 736 osl_names_p names) { 737 int i, j; 738 int part, nb_parts; 739 int generated_names = 0; 740 int high_water_mark = OSL_MAX_STRING; 741 char * string = NULL; 742 char buffer[OSL_MAX_STRING]; 743 char ** name_array = NULL; 744 char * scolumn; 745 char * comment; 746 747 if (relation == NULL) 748 return strdup("# NULL relation\n"); 749 750 OSL_malloc(string, char *, high_water_mark * sizeof(char)); 751 string[0] = '\0'; 752 753 // Generates the names for the comments if necessary. 754 if (names == NULL) { 755 generated_names = 1; 756 names = osl_relation_names(relation); 757 } 758 759 nb_parts = osl_relation_nb_components(relation); 760 761 if (nb_parts > 1) { 762 snprintf(buffer, OSL_MAX_STRING, "# Union with %d parts\n%d\n", 763 nb_parts, nb_parts); 764 osl_util_safe_strcat(&string, buffer, &high_water_mark); 765 } 766 767 // Print each part of the union. 768 for (part = 1; part <= nb_parts; part++) { 769 // Prepare the array of strings for comments. 770 name_array = osl_relation_strings(relation, names); 771 772 if (nb_parts > 1) { 773 snprintf(buffer, OSL_MAX_STRING, "# Union part No.%d\n", part); 774 osl_util_safe_strcat(&string, buffer, &high_water_mark); 775 } 776 777 snprintf(buffer, OSL_MAX_STRING, "%d %d %d %d %d %d\n", 778 relation->nb_rows, relation->nb_columns, 779 relation->nb_output_dims, relation->nb_input_dims, 780 relation->nb_local_dims, relation->nb_parameters); 781 osl_util_safe_strcat(&string, buffer, &high_water_mark); 782 783 if (relation->nb_rows > 0) { 784 scolumn = osl_relation_column_string(relation, name_array); 785 snprintf(buffer, OSL_MAX_STRING, "%s", scolumn); 786 osl_util_safe_strcat(&string, buffer, &high_water_mark); 787 free(scolumn); 788 } 789 790 for (i = 0; i < relation->nb_rows; i++) { 791 for (j = 0; j < relation->nb_columns; j++) { 792 osl_int_sprint(buffer, relation->precision, relation->m[i], j); 793 osl_util_safe_strcat(&string, buffer, &high_water_mark); 794 snprintf(buffer, OSL_MAX_STRING, " "); 795 osl_util_safe_strcat(&string, buffer, &high_water_mark); 796 } 797 798 if (name_array != NULL) { 799 comment = osl_relation_sprint_comment(relation, i, name_array, 800 names->arrays->string); 801 osl_util_safe_strcat(&string, comment, &high_water_mark); 802 free(comment); 803 } 804 snprintf(buffer, OSL_MAX_STRING, "\n"); 805 osl_util_safe_strcat(&string, buffer, &high_water_mark); 806 } 807 808 // Free the array of strings. 809 if (name_array != NULL) { 810 for (i = 0; i < relation->nb_columns; i++) 811 free(name_array[i]); 812 free(name_array); 813 } 814 815 relation = relation->next; 816 } 817 818 if (generated_names) 819 osl_names_free(names); 820 821 return string; 822} 823 824 825/** 826 * osl_relation_spprint function: 827 * this function pretty-prints the content of an osl_relation_t structure 828 * (*relation) into a string in the OpenScop format, and returns this string. 829 * \param[in] relation The relation whose information has to be printed. 830 * \param[in] names The names of the constraint columns for comments. 831 * \return A string 832 */ 833char * osl_relation_spprint(osl_relation_p relation, osl_names_p names) { 834 int high_water_mark = OSL_MAX_STRING; 835 char * string = NULL; 836 char * temp; 837 char buffer[OSL_MAX_STRING]; 838 OSL_malloc(string, char *, high_water_mark * sizeof(char)); 839 string[0] = '\0'; 840 841 if (osl_relation_nb_components(relation) > 0) { 842 temp = osl_relation_sprint_type(relation); 843 osl_util_safe_strcat(&string, temp, &high_water_mark); 844 free(temp); 845 846 snprintf(buffer, OSL_MAX_STRING, "\n"); 847 osl_util_safe_strcat(&string, buffer, &high_water_mark); 848 849 temp = osl_relation_spprint_polylib(relation, names); 850 osl_util_safe_strcat(&string, temp, &high_water_mark); 851 free(temp); 852 } 853 854 return string; 855} 856 857 858/** 859 * osl_relation_pprint function: 860 * this function pretty-prints the content of an osl_relation_t structure 861 * (*relation) into a file (file, possibly stdout) in the OpenScop format. 862 * \param[in] file File where informations are printed. 863 * \param[in] relation The relation whose information has to be printed. 864 * \param[in] names The names of the constraint columns for comments. 865 */ 866void osl_relation_pprint(FILE * file, osl_relation_p relation, 867 osl_names_p names) { 868 char * string = osl_relation_spprint(relation, names); 869 fprintf(file, "%s", string); 870 free(string); 871} 872 873 874/** 875 * osl_relation_print function: 876 * this function prints the content of an osl_relation_t structure 877 * (*relation) into a file (file, possibly stdout) in the OpenScop format. 878 * \param[in] file File where informations are printed. 879 * \param[in] relation The relation whose information has to be printed. 880 */ 881void osl_relation_print(FILE * file, osl_relation_p relation) { 882 883 osl_relation_pprint(file, relation, NULL); 884} 885 886 887/***************************************************************************** 888 * Reading function * 889 *****************************************************************************/ 890 891 892/** 893 * osl_relation_read_type function: 894 * this function reads a textual relation type and returns its integer 895 * counterpart. 896 * \param[in] file The input stream. 897 * \return The relation type. 898 */ 899static 900int osl_relation_read_type(FILE * file) { 901 int type; 902 osl_strings_p strings; 903 904 strings = osl_strings_read(file); 905 if (osl_strings_size(strings) > 1) { 906 OSL_warning("uninterpreted information (after the relation type)"); 907 } 908 if (osl_strings_size(strings) == 0) 909 OSL_error("no relation type"); 910 911 if (!strcmp(strings->string[0], OSL_STRING_UNDEFINED)) { 912 type = OSL_UNDEFINED; 913 goto return_type; 914 } 915 916 if (!strcmp(strings->string[0], OSL_STRING_CONTEXT)) { 917 type = OSL_TYPE_CONTEXT; 918 goto return_type; 919 } 920 921 if (!strcmp(strings->string[0], OSL_STRING_DOMAIN)) { 922 type = OSL_TYPE_DOMAIN; 923 goto return_type; 924 } 925 926 if (!strcmp(strings->string[0], OSL_STRING_SCATTERING)) { 927 type = OSL_TYPE_SCATTERING; 928 goto return_type; 929 } 930 931 if (!strcmp(strings->string[0], OSL_STRING_READ)) { 932 type = OSL_TYPE_READ; 933 goto return_type; 934 } 935 936 if (!strcmp(strings->string[0], OSL_STRING_WRITE)) { 937 type = OSL_TYPE_WRITE; 938 goto return_type; 939 } 940 941 if (!strcmp(strings->string[0], OSL_STRING_MAY_WRITE)) { 942 type = OSL_TYPE_MAY_WRITE; 943 goto return_type; 944 } 945 946 OSL_error("relation type not supported"); 947 948return_type: 949 osl_strings_free(strings); 950 return type; 951} 952 953 954/** 955 * osl_relation_pread function ("precision read"): 956 * this function reads a relation into a file (foo, posibly stdin) and 957 * returns a pointer this relation. The relation is set to the maximum 958 * available precision. 959 * \param[in] foo The input stream. 960 * \param[in] precision The precision of the relation elements. 961 * \return A pointer to the relation structure that has been read. 962 */ 963osl_relation_p osl_relation_pread(FILE * foo, int precision) { 964 int i, j, k, n, read = 0; 965 int nb_rows, nb_columns; 966 int nb_output_dims, nb_input_dims, nb_local_dims, nb_parameters; 967 int nb_union_parts = 1; 968 int may_read_nb_union_parts = 1; 969 int read_attributes = 1; 970 int first = 1; 971 int type; 972 char * c, s[OSL_MAX_STRING], str[OSL_MAX_STRING], *tmp; 973 osl_relation_p relation, relation_union = NULL, previous = NULL; 974 975 type = osl_relation_read_type(foo); 976 977 // Read each part of the union (the number of parts may be updated inside) 978 for (k = 0; k < nb_union_parts; k++) { 979 // Read the number of union parts or the attributes of the union part 980 while (read_attributes) { 981 read_attributes = 0; 982 983 // Read relation attributes. 984 c = osl_util_skip_blank_and_comments(foo, s); 985 read = sscanf(c, " %d %d %d %d %d %d", &nb_rows, &nb_columns, 986 &nb_output_dims, &nb_input_dims, 987 &nb_local_dims, &nb_parameters); 988 989 if (((read != 1) && (read != 6)) || 990 ((read == 1) && (may_read_nb_union_parts != 1))) 991 OSL_error("not 1 or 6 integers on the first relation line"); 992 993 if (read == 1) { 994 // Only one number means a union and is the number of parts. 995 nb_union_parts = nb_rows; 996 if (nb_union_parts < 1) 997 OSL_error("negative nb of union parts"); 998 999 // Allow to read the properties of the first part of the union. 1000 read_attributes = 1; 1001 } 1002 1003 may_read_nb_union_parts = 0; 1004 } 1005 1006 // Allocate the union part and fill its properties. 1007 relation = osl_relation_pmalloc(precision, nb_rows, nb_columns); 1008 relation->type = type; 1009 relation->nb_output_dims = nb_output_dims; 1010 relation->nb_input_dims = nb_input_dims; 1011 relation->nb_local_dims = nb_local_dims; 1012 relation->nb_parameters = nb_parameters; 1013 1014 // Read the matrix of constraints. 1015 for (i = 0; i < relation->nb_rows; i++) { 1016 c = osl_util_skip_blank_and_comments(foo, s); 1017 if (c == NULL) 1018 OSL_error("not enough rows"); 1019 1020 for (j = 0; j < relation->nb_columns; j++) { 1021 if (c == NULL || *c == '#' || *c == '\n') 1022 OSL_error("not enough columns"); 1023 if (sscanf(c, "%s%n", str, &n) == 0) 1024 OSL_error("not enough rows"); 1025 1026 // TODO: remove this tmp (sread updates the pointer). 1027 tmp = str; 1028 osl_int_sread(&tmp, precision, relation->m[i], j); 1029 c += n; 1030 } 1031 } 1032 1033 // Build the linked list of union parts. 1034 if (first == 1) { 1035 relation_union = relation; 1036 first = 0; 1037 } 1038 else { 1039 previous->next = relation; 1040 } 1041 1042 previous = relation; 1043 read_attributes = 1; 1044 } 1045 1046 return relation_union; 1047} 1048 1049 1050/** 1051 * osl_relation_read function: 1052 * this function is equivalent to osl_relation_pread() except that 1053 * the precision corresponds to the precision environment variable or 1054 * to the highest available precision if it is not defined. 1055 * \see{osl_relation_pread} 1056 */ 1057osl_relation_p osl_relation_read(FILE * foo) { 1058 int precision = osl_util_get_precision(); 1059 return osl_relation_pread(foo, precision); 1060} 1061 1062 1063/*+*************************************************************************** 1064 * Memory allocation/deallocation function * 1065 *****************************************************************************/ 1066 1067 1068/** 1069 * osl_relation_pmalloc function: 1070 * (precision malloc) this function allocates the memory space for an 1071 * osl_relation_t structure and sets its fields with default values. 1072 * Then it returns a pointer to the allocated space. 1073 * \param[in] precision The precision of the constraint matrix. 1074 * \param[in] nb_rows The number of row of the relation to allocate. 1075 * \param[in] nb_columns The number of columns of the relation to allocate. 1076 * \return A pointer to an empty relation with fields set to default values 1077 * and a ready-to-use constraint matrix. 1078 */ 1079osl_relation_p osl_relation_pmalloc(int precision, 1080 int nb_rows, int nb_columns) { 1081 osl_relation_p relation; 1082 void ** p, * q; 1083 int i, j; 1084 1085 OSL_malloc(relation, osl_relation_p, sizeof(osl_relation_t)); 1086 relation->type = OSL_UNDEFINED; 1087 relation->nb_rows = nb_rows; 1088 relation->nb_columns = nb_columns; 1089 relation->nb_output_dims = OSL_UNDEFINED; 1090 relation->nb_input_dims = OSL_UNDEFINED; 1091 relation->nb_parameters = OSL_UNDEFINED; 1092 relation->nb_local_dims = OSL_UNDEFINED; 1093 relation->precision = precision; 1094 1095 if ((nb_rows == 0) || (nb_columns == 0) || 1096 (nb_rows == OSL_UNDEFINED) || (nb_columns == OSL_UNDEFINED)) { 1097 relation->m = NULL; 1098 } 1099 else { 1100 OSL_malloc(p, void **, nb_rows * sizeof(void *)); 1101 OSL_malloc(q, void *, 1102 nb_rows * nb_columns * osl_int_sizeof(precision)); 1103 relation->m = p; 1104 for (i = 0; i < nb_rows; i++) { 1105 relation->m[i] = osl_int_address(precision, q, i * nb_columns); 1106 for (j = 0; j < nb_columns; j++) 1107 osl_int_init_set_si(precision, relation->m[i], j, 0); 1108 } 1109 } 1110 1111 relation->next = NULL; 1112 1113 return relation; 1114} 1115 1116 1117/** 1118 * osl_relation_malloc function: 1119 * this function is equivalent to osl_relation_pmalloc() except that 1120 * the precision corresponds to the precision environment variable or 1121 * to the highest available precision if it is not defined. 1122 * \see{osl_relation_pmalloc} 1123 */ 1124osl_relation_p osl_relation_malloc(int nb_rows, int nb_columns) { 1125 int precision = osl_util_get_precision(); 1126 return osl_relation_pmalloc(precision, nb_rows, nb_columns); 1127} 1128 1129 1130/** 1131 * osl_relation_free_inside function: 1132 * this function frees the allocated memory for the inside of a 1133 * osl_relation_t structure, i.e. only m. 1134 * \param[in] relation The pointer to the relation we want to free internals. 1135 */ 1136void osl_relation_free_inside(osl_relation_p relation) { 1137 int i, nb_elements; 1138 void * p; 1139 1140 if (relation == NULL) 1141 return; 1142 1143 nb_elements = relation->nb_rows * relation->nb_columns; 1144 1145 if (nb_elements > 0) 1146 p = relation->m[0]; 1147 1148 for (i = 0; i < nb_elements; i++) 1149 osl_int_clear(relation->precision, p, i); 1150 1151 if (relation->m != NULL) { 1152 if (nb_elements > 0) 1153 free(relation->m[0]); 1154 free(relation->m); 1155 } 1156} 1157 1158 1159/** 1160 * osl_relation_free function: 1161 * this function frees the allocated memory for an osl_relation_t 1162 * structure. 1163 * \param[in] relation The pointer to the relation we want to free. 1164 */ 1165void osl_relation_free(osl_relation_p relation) { 1166 osl_relation_p tmp; 1167 1168 if (relation == NULL) 1169 return; 1170 1171 while (relation != NULL) { 1172 tmp = relation->next; 1173 osl_relation_free_inside(relation); 1174 free(relation); 1175 relation = tmp; 1176 } 1177} 1178 1179 1180/*+*************************************************************************** 1181 * Processing functions * 1182 *****************************************************************************/ 1183 1184 1185/** 1186 * osl_relation_nclone function: 1187 * this functions builds and returns a "hard copy" (not a pointer copy) of a 1188 * osl_relation_t data structure such that the clone is restricted to the 1189 * "n" first rows of the relation. This applies to all the parts in the case 1190 * of a relation union. 1191 * \param[in] relation The pointer to the relation we want to clone. 1192 * \param[in] n The number of row of the relation we want to clone (the 1193 * special value -1 means "all the rows"). 1194 * \return A pointer to the clone of the relation union restricted to the 1195 * first n rows of constraint matrix for each part of the union. 1196 */ 1197osl_relation_p osl_relation_nclone(osl_relation_p relation, int n) { 1198 int i, j; 1199 int first = 1, all_rows = 0; 1200 osl_relation_p clone = NULL, node, previous = NULL; 1201 1202 if (n == -1) 1203 all_rows = 1; 1204 1205 while (relation != NULL) { 1206 if (all_rows) 1207 n = relation->nb_rows; 1208 1209 if (n > relation->nb_rows) 1210 OSL_error("not enough rows to clone in the relation"); 1211 1212 node = osl_relation_pmalloc(relation->precision, n, relation->nb_columns); 1213 node->type = relation->type; 1214 node->nb_output_dims = relation->nb_output_dims; 1215 node->nb_input_dims = relation->nb_input_dims; 1216 node->nb_local_dims = relation->nb_local_dims; 1217 node->nb_parameters = relation->nb_parameters; 1218 1219 for (i = 0; i < n; i++) 1220 for (j = 0; j < relation->nb_columns; j++) 1221 osl_int_assign(relation->precision, node->m[i], j, relation->m[i], j); 1222 1223 if (first) { 1224 first = 0; 1225 clone = node; 1226 previous = node; 1227 } 1228 else { 1229 previous->next = node; 1230 previous = previous->next; 1231 } 1232 1233 relation = relation->next; 1234 } 1235 1236 return clone; 1237} 1238 1239 1240/** 1241 * osl_relation_clone function: 1242 * this function builds and returns a "hard copy" (not a pointer copy) of an 1243 * osl_relation_t data structure (the full union of relation). 1244 * \param[in] relation The pointer to the relation we want to clone. 1245 * \return A pointer to the clone of the union of relations. 1246 */ 1247osl_relation_p osl_relation_clone(osl_relation_p relation) { 1248 if (relation == NULL) 1249 return NULL; 1250 1251 return osl_relation_nclone(relation, -1); 1252} 1253 1254 1255/** 1256 * osl_relation_add function: 1257 * this function adds a relation (union) at the end of the relation (union) 1258 * pointed by r1. No new relation is created: this functions links the two 1259 * input unions. If the first relation is NULL, it is set to the 1260 * second relation. 1261 * \param[in,out] r1 Pointer to the first relation (union). 1262 * \param[in] r2 The second relation (union). 1263 */ 1264void osl_relation_add(osl_relation_p *r1, osl_relation_p r2) { 1265 while (*r1 != NULL) 1266 r1 = &((*r1)->next); 1267 1268 *r1 = r2; 1269} 1270 1271 1272/** 1273 * osl_relation_union function: 1274 * this function builds a new relation from two relations provided 1275 * as parameters. The new relation is built as an union of the 1276 * two relations: the list of constraint sets are linked together. 1277 * \param[in] r1 The first relation. 1278 * \param[in] r2 The second relation. 1279 * \return A new relation corresponding to the union of r1 and r2. 1280 */ 1281osl_relation_p osl_relation_union(osl_relation_p r1, 1282 osl_relation_p r2) { 1283 osl_relation_p copy1, copy2; 1284 1285 if ((r1 == NULL) && (r2 == NULL)) 1286 return NULL; 1287 1288 copy1 = osl_relation_clone(r1); 1289 copy2 = osl_relation_clone(r2); 1290 osl_relation_add(©1, copy2); 1291 1292 return copy1; 1293} 1294 1295 1296/** 1297 * osl_relation_replace_vector function: 1298 * this function replaces the "row"^th row of a relation "relation" with the 1299 * vector "vector". It directly updates the relation union part pointed 1300 * by "relation" and this part only. 1301 * \param[in,out] relation The relation we want to replace a row. 1302 * \param[in] vector The vector that will replace a row of the relation. 1303 * \param[in] row The row of the relation to be replaced. 1304 */ 1305void osl_relation_replace_vector(osl_relation_p relation, 1306 osl_vector_p vector, int row) { 1307 int i; 1308 1309 if ((relation == NULL) || (vector == NULL) || 1310 (relation->precision != vector->precision) || 1311 (relation->nb_columns != vector->size) || 1312 (row >= relation->nb_rows) || (row < 0)) 1313 OSL_error("vector cannot replace relation row"); 1314 1315 for (i = 0; i < vector->size; i++) 1316 osl_int_assign(relation->precision, relation->m[row], i, vector->v, i); 1317} 1318 1319 1320/** 1321 * osl_relation_add_vector function: 1322 * this function adds (meaning, +) a vector to the "row"^th row of a 1323 * relation "relation". It directly updates the relation union part pointed 1324 * by "relation" and this part only. 1325 * \param[in,out] relation The relation we want to add a vector to a row. 1326 * \param[in] vector The vector that will replace a row of the relation. 1327 * \param[in] row The row of the relation to add the vector. 1328 */ 1329void osl_relation_add_vector(osl_relation_p relation, 1330 osl_vector_p vector, int row) { 1331 int i; 1332 1333 if ((relation == NULL) || (vector == NULL) || 1334 (relation->precision != vector->precision) || 1335 (relation->nb_columns != vector->size) || 1336 (row >= relation->nb_rows) || (row < 0)) 1337 OSL_error("vector cannot be added to relation"); 1338 1339 if (osl_int_get_si(relation->precision, relation->m[row], 0) == 0) 1340 osl_int_assign(relation->precision, relation->m[row], 0, vector->v, 0); 1341 1342 for (i = 1; i < vector->size; i++) 1343 osl_int_add(relation->precision, 1344 relation->m[row], i, relation->m[row], i, vector->v, i); 1345} 1346 1347 1348/** 1349 * osl_relation_sub_vector function: 1350 * this function subtracts the vector "vector" to the "row"^th row of 1351 * a relation "relation. It directly updates the relation union part pointed 1352 * by "relation" and this part only. 1353 * \param[in,out] relation The relation where to subtract a vector to a row. 1354 * \param[in] vector The vector to subtract to a relation row. 1355 * \param[in] row The row of the relation to subtract the vector. 1356 */ 1357void osl_relation_sub_vector(osl_relation_p relation, 1358 osl_vector_p vector, int row) { 1359 int i; 1360 1361 if ((relation == NULL) || (vector == NULL) || 1362 (relation->precision != vector->precision) || 1363 (relation->nb_columns != vector->size) || 1364 (row >= relation->nb_rows) || (row < 0)) 1365 OSL_error("vector cannot be subtracted to row"); 1366 1367 if (osl_int_get_si(relation->precision, relation->m[row], 0) == 0) 1368 osl_int_assign(relation->precision, relation->m[row], 0, vector->v, 0); 1369 1370 for (i = 1; i < vector->size; i++) 1371 osl_int_sub(relation->precision, 1372 relation->m[row], i, relation->m[row], i, vector->v, i); 1373} 1374 1375 1376/** 1377 * osl_relation_insert_vector function: 1378 * this function inserts a new row corresponding to the vector "vector" to 1379 * the relation "relation" by inserting it at the "row"^th row of 1380 * "relation" (-1 is a shortcut to insert the vector after the constraints 1381 * of the relation). It directly updates the relation union part pointed 1382 * by "relation" and this part only. If "vector" (or "relation") is NULL, 1383 * the relation is left unmodified. 1384 * \param[in,out] relation The relation we want to extend. 1385 * \param[in] vector The vector that will be added relation. 1386 * \param[in] row The row where to insert the vector (-1 to 1387 * insert it after the relation constraints). 1388 */ 1389void osl_relation_insert_vector(osl_relation_p relation, 1390 osl_vector_p vector, int row) { 1391 osl_relation_p temp; 1392 1393 temp = osl_relation_from_vector(vector); 1394 osl_relation_insert_constraints(relation, temp, row); 1395 osl_relation_free(temp); 1396} 1397 1398 1399/** 1400 * osl_relation_concat_vector function: 1401 * this function builds a new relation from one relation and a vector sent as 1402 * parameters. The new set of constraints is built as the concatenation 1403 * of the rows of the first part of the relation and of the vector 1404 * constraint. This means, there is no next field in the result. 1405 * \param[in] r The input relation. 1406 * \param[in] v The input vector. 1407 * \return A pointer to the relation resulting from the concatenation of 1408 * the constraints of the relation and of the vector. 1409 */ 1410osl_relation_p osl_relation_concat_vector(osl_relation_p relation, 1411 osl_vector_p vector) { 1412 osl_relation_p new, temp; 1413 1414 temp = osl_relation_from_vector(vector); 1415 new = osl_relation_concat_constraints(relation, temp); 1416 osl_relation_free(temp); 1417 return new; 1418} 1419 1420 1421/** 1422 * osl_relation_insert_blank_row function: 1423 * this function inserts a new row filled with zeros o an existing relation 1424 * union part (it only affects the first union part). 1425 * \param[in,out] relation The relation to add a row in. 1426 * \param[in] row The row where to insert the blank row. 1427 */ 1428void osl_relation_insert_blank_row(osl_relation_p relation, int row) { 1429 osl_vector_p vector; 1430 1431 if (relation != NULL) { 1432 vector = osl_vector_pmalloc(relation->precision, relation->nb_columns); 1433 osl_relation_insert_vector(relation, vector, row); 1434 osl_vector_free(vector); 1435 } 1436} 1437 1438 1439/** 1440 * osl_relation_insert_blank_column function: 1441 * this function inserts a new column filled with zeros to an existing 1442 * relation union part (it only affects the first union part). WARNING: 1443 * this function does not update the relation attributes. 1444 * \param[in,out] relation The relation to add a column in. 1445 * \param[in] column The column where to insert the blank column. 1446 */ 1447void osl_relation_insert_blank_column(osl_relation_p relation, int column) { 1448 1449 int i, j; 1450 osl_relation_p temp; 1451 1452 if (relation == NULL) 1453 return; 1454 1455 if ((column < 0) || (column > relation->nb_columns)) 1456 OSL_error("bad column number"); 1457 1458 // We use a temporary relation just to reuse existing functions. Cleaner. 1459 temp = osl_relation_pmalloc(relation->precision, 1460 relation->nb_rows, relation->nb_columns + 1); 1461 1462 for (i = 0; i < relation->nb_rows; i++) { 1463 for (j = 0; j < column; j++) 1464 osl_int_assign(relation->precision, temp->m[i], j, relation->m[i], j); 1465 1466 for (j = column; j < relation->nb_columns; j++) 1467 osl_int_assign(relation->precision, temp->m[i], j+1, relation->m[i], j); 1468 } 1469 1470 osl_relation_free_inside(relation); 1471 1472 // Replace the inside of relation. 1473 relation->nb_columns = temp->nb_columns; 1474 relation->m = temp->m; 1475 1476 // Free the temp "shell". 1477 free(temp); 1478} 1479 1480 1481/** 1482 * osl_relation_from_vector function: 1483 * this function converts a vector "vector" to a relation with a single row 1484 * and returns a pointer to that relation. 1485 * \param[in] vector The vector to convert to a relation. 1486 * \return A pointer to a relation resulting from the vector conversion. 1487 */ 1488osl_relation_p osl_relation_from_vector(osl_vector_p vector) { 1489 osl_relation_p relation; 1490 1491 if (vector == NULL) 1492 return NULL; 1493 1494 relation = osl_relation_pmalloc(vector->precision, 1, vector->size); 1495 osl_relation_replace_vector(relation, vector, 0); 1496 return relation; 1497} 1498 1499 1500/** 1501 * osl_relation_replace_constraints function: 1502 * this function replaces some rows of a relation "r1" with the rows of 1503 * the relation "r2". It begins at the "row"^th row of "r1". It directly 1504 * updates the relation union part pointed by "r1" and this part only. 1505 * \param[in,out] r1 The relation we want to change some rows. 1506 * \param[in] r2 The relation containing the new rows. 1507 * \param[in] row The first row of the relation r1 to be replaced. 1508 */ 1509void osl_relation_replace_constraints(osl_relation_p r1, 1510 osl_relation_p r2, int row) { 1511 int i, j; 1512 1513 if ((r1 == NULL) || (r2 == NULL) || 1514 (r1->precision != r2->precision) || 1515 (r1->nb_columns != r1->nb_columns) || 1516 ((row + r2->nb_rows) > r1->nb_rows) || (row < 0)) 1517 OSL_error("relation rows could not be replaced"); 1518 1519 for (i = 0; i < r2->nb_rows; i++) 1520 for (j = 0; j < r2->nb_columns; j++) 1521 osl_int_assign(r1->precision, r1->m[i+row], j, r2->m[i], j); 1522} 1523 1524 1525/** 1526 * osl_relation_insert_constraints function: 1527 * this function inserts the rows of the relation "r2" to the relation 1528 * "r1", starting from the "row"^th row of "r1" (-1 is a 1529 * shortcut to insert the "r2" constraints after the constraints of r1). 1530 * It directly updates the relation union part pointed by "r1" and this 1531 * part only. If "r2" (or "r1") is NULL, the relation is left unmodified. 1532 * \param[in,out] r1 The relation we want to extend. 1533 * \param[in] r2 The relation to be inserted. 1534 * \param[in] row The row where to insert the constraints (-1 to 1535 * insert them after those of "r1"). 1536 */ 1537void osl_relation_insert_constraints(osl_relation_p r1, 1538 osl_relation_p r2, int row) { 1539 int i, j; 1540 osl_relation_p temp; 1541 1542 if ((r1 == NULL) || (r2 == NULL)) 1543 return; 1544 1545 if (row == -1) 1546 row = r1->nb_rows; 1547 1548 if ((r1->nb_columns != r2->nb_columns) || 1549 (r1->precision != r2->precision) || 1550 (row > r1->nb_rows) || (row < 0)) 1551 OSL_error("constraints cannot be inserted"); 1552 1553 // We use a temporary relation just to reuse existing functions. Cleaner. 1554 temp = osl_relation_pmalloc(r1->precision, 1555 r1->nb_rows + r2->nb_rows, r1->nb_columns); 1556 1557 for (i = 0; i < row; i++) 1558 for (j = 0; j < r1->nb_columns; j++) 1559 osl_int_assign(r1->precision, temp->m[i], j, r1->m[i], j); 1560 1561 osl_relation_replace_constraints(temp, r2, row); 1562 1563 for (i = row + r2->nb_rows; i < r2->nb_rows + r1->nb_rows; i++) 1564 for (j = 0; j < r1->nb_columns; j++) 1565 osl_int_assign(r1->precision, temp->m[i], j, r1->m[i-r2->nb_rows], j); 1566 1567 osl_relation_free_inside(r1); 1568 1569 // Replace the inside of relation. 1570 r1->nb_rows = temp->nb_rows; 1571 r1->m = temp->m; 1572 1573 // Free the temp "shell". 1574 free(temp); 1575} 1576 1577 1578/** 1579 * osl_relation_remove_row function: 1580 * this function removes a given row to the relation "r". It directly 1581 * updates the relation union part pointed by "r" and this part only. 1582 * \param[in,out] r The relation to remove a row. 1583 * \param[in] row The row number to remove. 1584 */ 1585void osl_relation_remove_row(osl_relation_p r, int row) { 1586 int i, j; 1587 osl_relation_p temp; 1588 1589 if (r == NULL) 1590 return; 1591 1592 if ((row < 0) || (row >= r->nb_rows)) 1593 OSL_error("bad row number"); 1594 1595 // We use a temporary relation just to reuse existing functions. Cleaner. 1596 temp = osl_relation_pmalloc(r->precision, 1597 r->nb_rows - 1, r->nb_columns); 1598 1599 for (i = 0; i < row; i++) 1600 for (j = 0; j < r->nb_columns; j++) 1601 osl_int_assign(r->precision, temp->m[i], j, r->m[i], j); 1602 1603 for (i = row + 1; i < r->nb_rows; i++) 1604 for (j = 0; j < r->nb_columns; j++) 1605 osl_int_assign(r->precision, temp->m[i - 1], j, r->m[i], j); 1606 1607 osl_relation_free_inside(r); 1608 1609 // Replace the inside of relation. 1610 r->nb_rows = temp->nb_rows; 1611 r->m = temp->m; 1612 1613 // Free the temp "shell". 1614 free(temp); 1615} 1616 1617 1618/** 1619 * osl_relation_remove_column function: 1620 * this function removes a given column to the relation "r". It directly 1621 * updates the relation union part pointed by "r" and this part only. 1622 * \param[in,out] r The relation to remove a column. 1623 * \param[in] column The column number to remove. 1624 */ 1625void osl_relation_remove_column(osl_relation_p r, int column) { 1626 int i, j; 1627 osl_relation_p temp; 1628 1629 if (r == NULL) 1630 return; 1631 1632 if ((column < 0) || (column >= r->nb_columns)) 1633 OSL_error("bad column number"); 1634 1635 // We use a temporary relation just to reuse existing functions. Cleaner. 1636 temp = osl_relation_pmalloc(r->precision, 1637 r->nb_rows, r->nb_columns - 1); 1638 1639 for (i = 0; i < r->nb_rows; i++) { 1640 for (j = 0; j < column; j++) 1641 osl_int_assign(r->precision, temp->m[i], j, r->m[i], j); 1642 1643 for (j = column + 1; j < r->nb_columns; j++) 1644 osl_int_assign(r->precision, temp->m[i], j - 1, r->m[i], j); 1645 } 1646 1647 osl_relation_free_inside(r); 1648 1649 // Replace the inside of relation. 1650 r->nb_rows = temp->nb_rows; 1651 r->m = temp->m; 1652 1653 // Free the temp "shell". 1654 free(temp); 1655} 1656 1657 1658/** 1659 * osl_relation_insert_columns function: 1660 * this function inserts new columns to an existing relation union part (it 1661 * only affects the first union part). The columns are copied out from the 1662 * matrix of an input relation which must have the convenient number of rows. 1663 * All columns of the input matrix are copied. WARNING: this function does not 1664 * update the relation attributes of the modified matrix. 1665 * \param[in,out] relation The relation to add columns in. 1666 * \param[in] insert The relation containing the columns to add. 1667 * \param[in] column The column where to insert the new columns. 1668 */ 1669void osl_relation_insert_columns(osl_relation_p relation, 1670 osl_relation_p insert, int column) { 1671 int i, j; 1672 osl_relation_p temp; 1673 1674 if ((relation == NULL) || (insert == NULL)) 1675 return; 1676 1677 if ((relation->precision != insert->precision) || 1678 (relation->nb_rows != insert->nb_rows) || 1679 (column < 0) || (column > relation->nb_columns)) 1680 OSL_error("columns cannot be inserted"); 1681 1682 // We use a temporary relation just to reuse existing functions. Cleaner. 1683 temp = osl_relation_pmalloc(relation->precision, relation->nb_rows, 1684 relation->nb_columns + insert->nb_columns); 1685 1686 for (i = 0; i < relation->nb_rows; i++) { 1687 for (j = 0; j < column; j++) 1688 osl_int_assign(relation->precision, temp->m[i], j, relation->m[i], j); 1689 1690 for (j = column; j < column + insert->nb_columns; j++) 1691 osl_int_assign(relation->precision, 1692 temp->m[i], j, insert->m[i], j - column); 1693 1694 for (j = column + insert->nb_columns; 1695 j < insert->nb_columns + relation->nb_columns; j++) 1696 osl_int_assign(relation->precision, 1697 temp->m[i], j, relation->m[i], j - insert->nb_columns); 1698 } 1699 1700 osl_relation_free_inside(relation); 1701 1702 // Replace the inside of relation. 1703 relation->nb_columns = temp->nb_columns; 1704 relation->m = temp->m; 1705 1706 // Free the temp "shell". 1707 free(temp); 1708} 1709 1710 1711/** 1712 * osl_relation_concat_constraints function: 1713 * this function builds a new relation from two relations sent as 1714 * parameters. The new set of constraints is built as the concatenation 1715 * of the rows of the first elements of the two relation unions r1 and r2. 1716 * This means, there is no next field in the result. 1717 * \param[in] r1 The first relation. 1718 * \param[in] r2 The second relation. 1719 * \return A pointer to the relation resulting from the concatenation of 1720 * the first elements of r1 and r2. 1721 */ 1722osl_relation_p osl_relation_concat_constraints( 1723 osl_relation_p r1, 1724 osl_relation_p r2) { 1725 osl_relation_p new; 1726 1727 if (r1 == NULL) 1728 return osl_relation_clone(r2); 1729 1730 if (r2 == NULL) 1731 return osl_relation_clone(r1); 1732 1733 if (r1->nb_columns != r2->nb_columns) 1734 OSL_error("incompatible sizes for concatenation"); 1735 1736 if (r1->next || r2->next) 1737 OSL_warning("relation concatenation is done on the first elements " 1738 "of union only"); 1739 1740 new = osl_relation_pmalloc(r1->precision, 1741 r1->nb_rows + r2->nb_rows, r1->nb_columns); 1742 osl_relation_replace_constraints(new, r1, 0); 1743 osl_relation_replace_constraints(new, r2, r1->nb_rows); 1744 1745 return new; 1746} 1747 1748 1749/** 1750 * osl_relation_equal function: 1751 * this function returns true if the two relations provided as parameters 1752 * are the same, false otherwise. 1753 * \param[in] r1 The first relation. 1754 * \param[in] r2 The second relation. 1755 * \return 1 if r1 and r2 are the same (content-wise), 0 otherwise. 1756 */ 1757int osl_relation_equal(osl_relation_p r1, osl_relation_p r2) { 1758 int i, j; 1759 1760 while ((r1 != NULL) && (r2 != NULL)) { 1761 if (r1 == r2) 1762 return 1; 1763 1764 if ((r1->type != r2->type) || 1765 (r1->precision != r2->precision) || 1766 (r1->nb_rows != r2->nb_rows) || 1767 (r1->nb_columns != r2->nb_columns) || 1768 (r1->nb_output_dims != r2->nb_output_dims) || 1769 (r1->nb_input_dims != r2->nb_input_dims) || 1770 (r1->nb_local_dims != r2->nb_local_dims) || 1771 (r1->nb_parameters != r2->nb_parameters)) 1772 return 0; 1773 1774 for (i = 0; i < r1->nb_rows; ++i) 1775 for (j = 0; j < r1->nb_columns; ++j) 1776 if (osl_int_ne(r1->precision, r1->m[i], j, r2->m[i], j)) 1777 return 0; 1778 1779 r1 = r1->next; 1780 r2 = r2->next; 1781 } 1782 1783 if (((r1 == NULL) && (r2 != NULL)) || ((r1 != NULL) && (r2 == NULL))) 1784 return 0; 1785 1786 return 1; 1787} 1788 1789 1790/** 1791 * osl_relation_check_attribute internal function: 1792 * This function checks whether an "actual" value is the same as an 1793 * "expected" value or not. If the expected value is set to 1794 * OSL_UNDEFINED, this function sets it to the "actual" value 1795 * and do not report a difference has been detected. 1796 * It returns 0 if a difference has been detected, 1 otherwise. 1797 * \param[in,out] expected Pointer to the expected value (the value is 1798 * modified if it was set to OSL_UNDEFINED). 1799 * \param[in] actual Value we want to check. 1800 * \return 0 if the values are not the same while the expected value was 1801 * not OSL_UNDEFINED, 1 otherwise. 1802 */ 1803static 1804int osl_relation_check_attribute(int * expected, int actual) { 1805 if (*expected != OSL_UNDEFINED) { 1806 if ((actual != OSL_UNDEFINED) && 1807 (actual != *expected)) { 1808 OSL_warning("unexpected atribute"); 1809 return 0; 1810 } 1811 } 1812 else { 1813 *expected = actual; 1814 } 1815 1816 return 1; 1817} 1818 1819 1820/** 1821 * osl_relation_check_nb_columns internal function: 1822 * This function checks that the number of columns of a relation 1823 * corresponds to some expected properties (setting an expected property to 1824 * OSL_UNDEFINED makes this function unable to detect a problem). 1825 * It returns 0 if the number of columns seems incorrect or 1 if no problem 1826 * has been detected. 1827 * \param[in] relation The relation we want to check the number of columns. 1828 * \param[in] expected_nb_output_dims Expected number of output dimensions. 1829 * \param[in] expected_nb_input_dims Expected number of input dimensions. 1830 * \param[in] expected_nb_parameters Expected number of parameters. 1831 * \return 0 if the number of columns seems incorrect, 1 otherwise. 1832 */ 1833static 1834int osl_relation_check_nb_columns(osl_relation_p relation, 1835 int expected_nb_output_dims, 1836 int expected_nb_input_dims, 1837 int expected_nb_parameters) { 1838 int expected_nb_local_dims, expected_nb_columns; 1839 1840 if ((expected_nb_output_dims != OSL_UNDEFINED) && 1841 (expected_nb_input_dims != OSL_UNDEFINED) && 1842 (expected_nb_parameters != OSL_UNDEFINED)) { 1843 1844 if (relation->nb_local_dims == OSL_UNDEFINED) 1845 expected_nb_local_dims = 0; 1846 else 1847 expected_nb_local_dims = relation->nb_local_dims; 1848 1849 expected_nb_columns = expected_nb_output_dims + 1850 expected_nb_input_dims + 1851 expected_nb_local_dims + 1852 expected_nb_parameters + 1853 2; 1854 1855 if (expected_nb_columns != relation->nb_columns) { 1856 OSL_warning("unexpected number of columns"); 1857 return 0; 1858 } 1859 } 1860 1861 return 1; 1862} 1863 1864 1865/** 1866 * osl_relation_integrity_check function: 1867 * this function checks that a relation is "well formed" according to some 1868 * expected properties (setting an expected value to OSL_UNDEFINED means 1869 * that we do not expect a specific value) and what the relation is supposed 1870 * to represent. It returns 0 if the check failed or 1 if no problem has been 1871 * detected. 1872 * \param[in] relation The relation we want to check. 1873 * \param[in] expected_type Semantics about this relation (domain, access...). 1874 * \param[in] expected_nb_output_dims Expected number of output dimensions. 1875 * \param[in] expected_nb_input_dims Expected number of input dimensions. 1876 * \param[in] expected_nb_parameters Expected number of parameters. 1877 * \return 0 if the integrity check fails, 1 otherwise. 1878 */ 1879int osl_relation_integrity_check(osl_relation_p relation, 1880 int expected_type, 1881 int expected_nb_output_dims, 1882 int expected_nb_input_dims, 1883 int expected_nb_parameters) { 1884 int i; 1885 1886 // Check the NULL case. 1887 if (relation == NULL) { 1888 if ((expected_nb_output_dims != OSL_UNDEFINED) || 1889 (expected_nb_input_dims != OSL_UNDEFINED) || 1890 (expected_nb_parameters != OSL_UNDEFINED)) { 1891 OSL_debug("NULL relation with some expected attibutes"); 1892 //return 0; 1893 } 1894 1895 return 1; 1896 } 1897 1898 // Check the type. 1899 if (((expected_type != OSL_TYPE_ACCESS) && 1900 (expected_type != relation->type)) || 1901 ((expected_type == OSL_TYPE_ACCESS) && 1902 (!osl_relation_is_access(relation)))) { 1903 OSL_warning("wrong type"); 1904 osl_relation_dump(stderr, relation); 1905 return 0; 1906 } 1907 1908 // Check that relations have no undefined atributes. 1909 if ((relation->nb_output_dims == OSL_UNDEFINED) || 1910 (relation->nb_input_dims == OSL_UNDEFINED) || 1911 (relation->nb_local_dims == OSL_UNDEFINED) || 1912 (relation->nb_parameters == OSL_UNDEFINED)) { 1913 OSL_warning("all attributes should be defined"); 1914 osl_relation_dump(stderr, relation); 1915 return 0; 1916 } 1917 1918 // Check that a context has actually 0 output dimensions. 1919 if ((relation->type == OSL_TYPE_CONTEXT) && 1920 (relation->nb_output_dims != 0)) { 1921 OSL_warning("context without 0 as number of output dimensions"); 1922 osl_relation_dump(stderr, relation); 1923 return 0; 1924 } 1925 1926 // Check that a domain or a context has actually 0 input dimensions. 1927 if (((relation->type == OSL_TYPE_DOMAIN) || 1928 (relation->type == OSL_TYPE_CONTEXT)) && 1929 (relation->nb_input_dims != 0)) { 1930 OSL_warning("domain or context without 0 input dimensions"); 1931 osl_relation_dump(stderr, relation); 1932 return 0; 1933 } 1934 1935 // Check properties according to expected values (and if expected values 1936 // are undefined, define them with the first relation part properties). 1937 if (!osl_relation_check_attribute(&expected_nb_output_dims, 1938 relation->nb_output_dims) || 1939 !osl_relation_check_attribute(&expected_nb_input_dims, 1940 relation->nb_input_dims) || 1941 !osl_relation_check_attribute(&expected_nb_parameters, 1942 relation->nb_parameters)) { 1943 osl_relation_dump(stderr, relation); 1944 return 0; 1945 } 1946 1947 while (relation != NULL) { 1948 1949 // Attributes (except the number of local dimensions) should be the same 1950 // in all parts of the union. 1951 if ((expected_nb_output_dims != relation->nb_output_dims) || 1952 (expected_nb_input_dims != relation->nb_input_dims) || 1953 (expected_nb_parameters != relation->nb_parameters)) { 1954 OSL_warning("inconsistent attributes"); 1955 osl_relation_dump(stderr, relation); 1956 return 0; 1957 } 1958 1959 // Check whether the number of columns is OK or not. 1960 if (!osl_relation_check_nb_columns(relation, 1961 expected_nb_output_dims, 1962 expected_nb_input_dims, 1963 expected_nb_parameters)) { 1964 osl_relation_dump(stderr, relation); 1965 return 0; 1966 } 1967 1968 // Check the first column. The first column of a relation part should be 1969 // made of 0 or 1 only. 1970 if ((relation->nb_rows > 0) && (relation->nb_columns > 0)) { 1971 for (i = 0; i < relation->nb_rows; i++) { 1972 if (!osl_int_zero(relation->precision, relation->m[i], 0) && 1973 !osl_int_one(relation->precision, relation->m[i], 0)) { 1974 OSL_warning("first column of a relation is not " 1975 "strictly made of 0 or 1"); 1976 osl_relation_dump(stderr, relation); 1977 return 0; 1978 } 1979 } 1980 } 1981 1982 // Array accesses must provide the array identifier. 1983 if ((osl_relation_is_access(relation)) && 1984 (osl_relation_get_array_id(relation) == OSL_UNDEFINED)) { 1985 osl_relation_dump(stderr, relation); 1986 return 0; 1987 } 1988 1989 relation = relation->next; 1990 } 1991 1992 return 1; 1993} 1994 1995 1996/** 1997 * osl_relation_set_attributes_one function: 1998 * this functions sets the attributes of a relation part provided as a 1999 * parameter. It updates the relation directly. 2000 * \param[in,out] relation The relation (union part) to set the attributes. 2001 * \param[in] nb_output_dims Number of output dimensions. 2002 * \param[in] nb_input_dims Number of input dimensions. 2003 * \param[in] nb_local_dims Number of local dimensions. 2004 * \param[in] nb_parameters Number of parameters. 2005 */ 2006void osl_relation_set_attributes_one(osl_relation_p relation, 2007 int nb_output_dims, int nb_input_dims, 2008 int nb_local_dims, int nb_parameters) { 2009 if (relation != NULL) { 2010 relation->nb_output_dims = nb_output_dims; 2011 relation->nb_input_dims = nb_input_dims; 2012 relation->nb_local_dims = nb_local_dims; 2013 relation->nb_parameters = nb_parameters; 2014 } 2015} 2016 2017 2018/** 2019 * osl_relation_set_attributes function: 2020 * this functions sets the attributes of a relation (union) provided 2021 * as a parameter. It updates the relation directly. 2022 * \param[in,out] relation The relation (union) to set the attributes. 2023 * \param[in] nb_output_dims Number of output dimensions. 2024 * \param[in] nb_input_dims Number of input dimensions. 2025 * \param[in] nb_local_dims Number of local dimensions. 2026 * \param[in] nb_parameters Number of parameters. 2027 */ 2028void osl_relation_set_attributes(osl_relation_p relation, 2029 int nb_output_dims, int nb_input_dims, 2030 int nb_local_dims, int nb_parameters) { 2031 while (relation != NULL) { 2032 osl_relation_set_attributes_one(relation, 2033 nb_output_dims, nb_input_dims, 2034 nb_local_dims, nb_parameters); 2035 relation = relation->next; 2036 } 2037} 2038 2039 2040/** 2041 * osl_relation_set_type function: 2042 * this function sets the type of each relation union part in the relation 2043 * to the one provided as parameter. 2044 * \param relation The relation to set the type. 2045 * \param type The type. 2046 */ 2047void osl_relation_set_type(osl_relation_p relation, int type) { 2048 2049 while (relation != NULL) { 2050 relation->type = type; 2051 relation = relation->next; 2052 } 2053} 2054 2055 2056/** 2057 * osl_relation_get_array_id function: 2058 * this function returns the array identifier in a relation with access type 2059 * It returns OSL_UNDEFINED if it is not able to find it (in particular 2060 * if there are irregularities in the relation). 2061 * \param[in] relation The relation where to find an array identifier. 2062 * \return The array identifier in the relation or OSL_UNDEFINED. 2063 */ 2064int osl_relation_get_array_id(osl_relation_p relation) { 2065 int i; 2066 int first = 1; 2067 int array_id = OSL_UNDEFINED; 2068 int reference_array_id = OSL_UNDEFINED; 2069 int nb_array_id; 2070 int row_id = 0; 2071 int precision; 2072 2073 if (relation == NULL) 2074 return OSL_UNDEFINED; 2075 2076 if (!osl_relation_is_access(relation)) { 2077 OSL_warning("asked for an array id of non-array relation"); 2078 return OSL_UNDEFINED; 2079 } 2080 2081 while (relation != NULL) { 2082 precision = relation->precision; 2083 2084 // There should be room to store the array identifier. 2085 if ((relation->nb_rows < 1) || 2086 (relation->nb_columns < 3)) { 2087 OSL_warning("no array identifier in an access function"); 2088 return OSL_UNDEFINED; 2089 } 2090 2091 // Array identifiers are m[i][#columns -1] / m[i][1], with i the only row 2092 // where m[i][1] is not 0. 2093 // - check there is exactly one row such that m[i][1] is not 0, 2094 // - check the whole ith row if full of 0 except m[i][1] and the id, 2095 // - check that (m[i][#columns -1] % m[i][1]) == 0, 2096 // - check that (-m[i][#columns -1] / m[i][1]) > 0. 2097 nb_array_id = 0; 2098 for (i = 0; i < relation->nb_rows; i++) { 2099 if (!osl_int_zero(precision, relation->m[i], 1)) { 2100 nb_array_id ++; 2101 row_id = i; 2102 } 2103 } 2104 if (nb_array_id == 0) { 2105 OSL_warning("no array identifier in an access function"); 2106 return OSL_UNDEFINED; 2107 } 2108 if (nb_array_id > 1) { 2109 OSL_warning("several array identifiers in one access function"); 2110 return OSL_UNDEFINED; 2111 } 2112 for (i = 0; i < relation->nb_columns - 1; i++) { 2113 if ((i != 1) && !osl_int_zero(precision, relation->m[row_id], i)) { 2114 OSL_warning("non integer array identifier"); 2115 return OSL_UNDEFINED; 2116 } 2117 } 2118 if (!osl_int_divisible(precision, 2119 relation->m[row_id], relation->nb_columns - 1, 2120 relation->m[row_id], 1)) { 2121 OSL_warning("rational array identifier"); 2122 return OSL_UNDEFINED; 2123 } 2124 array_id = -osl_int_get_si(precision, 2125 relation->m[row_id], 2126 relation->nb_columns - 1); 2127 array_id /= osl_int_get_si(precision, relation->m[row_id], 1); 2128 if (array_id <= 0) { 2129 OSL_warning("negative or 0 identifier in access function"); 2130 return OSL_UNDEFINED; 2131 } 2132 2133 // Unions of accesses are allowed, but they should refer at the same array. 2134 if (first) { 2135 reference_array_id = array_id; 2136 first = 0; 2137 } 2138 else { 2139 if (reference_array_id != array_id) { 2140 OSL_warning("inconsistency of array identifiers in an " 2141 "union of access relations"); 2142 return OSL_UNDEFINED; 2143 } 2144 } 2145 2146 relation = relation->next; 2147 } 2148 2149 return array_id; 2150} 2151 2152 2153/** 2154 * osl_relation_is_access function: 2155 * this function returns 1 if the relation corresponds to an access relation, 2156 * whatever its precise type (read, write etc.), 0 otherwise. 2157 * \param relation The relation to check wheter it is an access relation or not. 2158 * \return 1 if the relation is an access relation, 0 otherwise. 2159 */ 2160int osl_relation_is_access(osl_relation_p relation) { 2161 2162 if (relation == NULL) 2163 return 0; 2164 2165 if ((relation->type == OSL_TYPE_ACCESS) || 2166 (relation->type == OSL_TYPE_READ) || 2167 (relation->type == OSL_TYPE_WRITE) || 2168 (relation->type == OSL_TYPE_MAY_WRITE)) 2169 return 1; 2170 2171 return 0; 2172} 2173 2174 2175/** 2176 * osl_relation_get_attributes function: 2177 * this function returns, through its parameters, the maximum values of the 2178 * relation attributes (nb_iterators, nb_parameters etc), depending on its 2179 * type. HOWEVER, it updates the parameter value iff the attribute is greater 2180 * than the input parameter value. Hence it may be used to get the 2181 * attributes as well as to find the maximum attributes for several relations. 2182 * The array identifier 0 is used when there is no array identifier (AND this 2183 * is OK), OSL_UNDEFINED is used to report it is impossible to provide the 2184 * property while it should. This function is not intended for checking, the 2185 * input relation should be correct. 2186 * \param[in] relation The relation to extract attribute values. 2187 * \param[in,out] nb_parameters Number of parameter attribute. 2188 * \param[in,out] nb_iterators Number of iterators attribute. 2189 * \param[in,out] nb_scattdims Number of scattering dimensions attribute. 2190 * \param[in,out] nb_localdims Number of local dimensions attribute. 2191 * \param[in,out] array_id Maximum array identifier attribute. 2192 */ 2193void osl_relation_get_attributes(osl_relation_p relation, 2194 int * nb_parameters, 2195 int * nb_iterators, 2196 int * nb_scattdims, 2197 int * nb_localdims, 2198 int * array_id) { 2199 int type; 2200 int local_nb_parameters = OSL_UNDEFINED; 2201 int local_nb_iterators = OSL_UNDEFINED; 2202 int local_nb_scattdims = OSL_UNDEFINED; 2203 int local_nb_localdims = OSL_UNDEFINED; 2204 int local_array_id = OSL_UNDEFINED; 2205 2206 while (relation != NULL) { 2207 if (osl_relation_is_access(relation)) 2208 type = OSL_TYPE_ACCESS; 2209 else 2210 type = relation->type; 2211 2212 // There is some redundancy but I believe the code is cleaner this way. 2213 switch (type) { 2214 case OSL_TYPE_CONTEXT: 2215 local_nb_parameters = relation->nb_parameters; 2216 local_nb_iterators = 0; 2217 local_nb_scattdims = 0; 2218 local_nb_localdims = relation->nb_local_dims; 2219 local_array_id = 0; 2220 break; 2221 2222 case OSL_TYPE_DOMAIN: 2223 local_nb_parameters = relation->nb_parameters; 2224 local_nb_iterators = relation->nb_output_dims; 2225 local_nb_scattdims = 0; 2226 local_nb_localdims = relation->nb_local_dims; 2227 local_array_id = 0; 2228 break; 2229 2230 case OSL_TYPE_SCATTERING: 2231 local_nb_parameters = relation->nb_parameters; 2232 local_nb_iterators = relation->nb_input_dims; 2233 local_nb_scattdims = relation->nb_output_dims; 2234 local_nb_localdims = relation->nb_local_dims; 2235 local_array_id = 0; 2236 break; 2237 2238 case OSL_TYPE_ACCESS: 2239 local_nb_parameters = relation->nb_parameters; 2240 local_nb_iterators = relation->nb_input_dims; 2241 local_nb_scattdims = 0; 2242 local_nb_localdims = relation->nb_local_dims; 2243 local_array_id = osl_relation_get_array_id(relation); 2244 break; 2245 } 2246 2247 // Update. 2248 *nb_parameters = OSL_max(*nb_parameters, local_nb_parameters); 2249 *nb_iterators = OSL_max(*nb_iterators, local_nb_iterators); 2250 *nb_scattdims = OSL_max(*nb_scattdims, local_nb_scattdims); 2251 *nb_localdims = OSL_max(*nb_localdims, local_nb_localdims); 2252 *array_id = OSL_max(*array_id, local_array_id); 2253 relation = relation->next; 2254 } 2255} 2256 2257 2258/** 2259 * osl_relation_extend_output function: 2260 * this function extends the number of output dimensions of a given relation. It 2261 * returns a copy of the input relation with a number of output dimensions 2262 * extended to "dim" for all its union components. The new output dimensions 2263 * are simply set equal to 0. The extended number of dimensions must be higher 2264 * than or equal to the original one (an error will be raised otherwise). 2265 * \param[in] relation The input relation to extend. 2266 * \param[in] dim The number of output dimension to reach. 2267 * \return A new relation: "relation" extended to "dim" output dims. 2268 */ 2269osl_relation_p osl_relation_extend_output(osl_relation_p relation, int dim) { 2270 int i, j; 2271 int first = 1; 2272 int offset; 2273 osl_relation_p extended = NULL, node, previous = NULL; 2274 2275 while (relation != NULL) { 2276 if (relation->nb_output_dims > dim) 2277 OSL_error("Number of output dims is greater than required extension"); 2278 offset = dim - relation->nb_output_dims; 2279 2280 node = osl_relation_pmalloc(relation->precision, 2281 relation->nb_rows + offset, 2282 relation->nb_columns + offset); 2283 2284 node->type = relation->type; 2285 node->nb_output_dims = OSL_max(relation->nb_output_dims, dim); 2286 node->nb_input_dims = relation->nb_input_dims; 2287 node->nb_local_dims = relation->nb_local_dims; 2288 node->nb_parameters = relation->nb_parameters; 2289 2290 // Copy of the original relation with some 0 columns for the new dimensions 2291 // Note that we use the fact that the matrix is initialized with zeros. 2292 for (i = 0; i < relation->nb_rows; i++) { 2293 for (j = 0; j <= relation->nb_output_dims; j++) 2294 osl_int_assign(relation->precision, node->m[i], j, relation->m[i], j); 2295 2296 for (j = relation->nb_output_dims + offset + 1; 2297 j < relation->nb_columns + offset; j++) 2298 osl_int_assign(relation->precision, 2299 node->m[i], j, relation->m[i], j - offset); 2300 } 2301 2302 // New rows dedicated to the new dimensions 2303 for (i = relation->nb_rows; i < relation->nb_rows + offset; i++) { 2304 for (j = 0; j < relation->nb_columns + offset; j++) { 2305 if ((i - relation->nb_rows) == (j - relation->nb_output_dims - 1)) 2306 osl_int_set_si(relation->precision, node->m[i], j, -1); 2307 } 2308 } 2309 2310 if (first) { 2311 first = 0; 2312 extended = node; 2313 previous = node; 2314 } 2315 else { 2316 previous->next = node; 2317 previous = previous->next; 2318 } 2319 2320 relation = relation->next; 2321 } 2322 2323 return extended; 2324} 2325 2326