1 2 /*+-----------------------------------------------------------------** 3 ** OpenScop Library ** 4 **-----------------------------------------------------------------** 5 ** relation_list.c ** 6 **-----------------------------------------------------------------** 7 ** First version: 08/10/2010 ** 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/util.h> 71#include <osl/relation.h> 72#include <osl/relation_list.h> 73 74 75/*+*************************************************************************** 76 * Structure display function * 77 *****************************************************************************/ 78 79 80/** 81 * osl_relation_list_idump function: 82 * Displays a osl_relation_list_t structure (a list of relations) into a 83 * file (file, possibly stdout). See osl_relation_print_structure for 84 * more details. 85 * \param file File where informations are printed. 86 * \param l The list of relations whose information has to be printed. 87 * \param level Number of spaces before printing, for each line. 88 */ 89void osl_relation_list_idump(FILE * file, osl_relation_list_p l, int level) { 90 int j, first = 1; 91 92 // Go to the right level. 93 for (j = 0; j < level; j++) 94 fprintf(file,"|\t"); 95 96 if (l != NULL) 97 fprintf(file, "+-- osl_relation_list_t\n"); 98 else 99 fprintf(file, "+-- NULL relation list\n"); 100 101 while (l != NULL) { 102 if (!first) { 103 // Go to the right level. 104 for (j = 0; j < level; j++) 105 fprintf(file, "|\t"); 106 fprintf(file, "| osl_relation_list_t\n"); 107 } 108 else 109 first = 0; 110 111 // A blank line. 112 for (j = 0; j <= level+1; j++) 113 fprintf(file, "|\t"); 114 fprintf(file, "\n"); 115 116 // Print a relation. 117 osl_relation_idump(file, l->elt, level+1); 118 119 l = l->next; 120 121 // Next line. 122 if (l != NULL) { 123 for (j = 0; j <= level; j++) 124 fprintf(file, "|\t"); 125 fprintf(file, "V\n"); 126 } 127 } 128 129 // The last line. 130 for (j = 0; j <= level; j++) 131 fprintf(file, "|\t"); 132 fprintf(file, "\n"); 133} 134 135 136/** 137 * osl_relation_dump function: 138 * This function prints the content of a osl_relation_list_t into 139 * a file (file, possibly stdout). 140 * \param file File where informations are printed. 141 * \param list The relation whose information has to be printed. 142 */ 143void osl_relation_list_dump(FILE * file, osl_relation_list_p list) { 144 osl_relation_list_idump(file, list, 0); 145} 146 147 148/** 149 * osl_relation_list_pprint_elts function: 150 * This function pretty-prints the elements of a osl_relation_list_t structure 151 * into a file (file, possibly stdout) in the OpenScop format. I.e., it prints 152 * only the elements and not the number of elements. It prints an element of the 153 * list only if it is not NULL. 154 * \param file File where informations are printed. 155 * \param list The relation list whose information has to be printed. 156 * \param[in] names Array of constraint columns names. 157 */ 158void osl_relation_list_pprint_elts(FILE * file, osl_relation_list_p list, 159 osl_names_p names) { 160 int i; 161 osl_relation_list_p head = list; 162 163 // Count the number of elements in the list with non-NULL content. 164 i = osl_relation_list_count(list); 165 166 // Print each element of the relation list. 167 if (i > 0) { 168 i = 0; 169 while (head) { 170 if (head->elt != NULL) { 171 osl_relation_pprint(file, head->elt, names); 172 if (head->next != NULL) 173 fprintf(file, "\n"); 174 i++; 175 } 176 head = head->next; 177 } 178 } 179 else { 180 fprintf(file, "# NULL relation list\n"); 181 } 182} 183 184 185/** 186 * osl_relation_list_pprint function: 187 * This function pretty-prints the content of a osl_relation_list_t structure 188 * into a file (file, possibly stdout) in the OpenScop format. It prints 189 * an element of the list only if it is not NULL. 190 * \param[in] file File where informations are printed. 191 * \param[in] list The relation list whose information has to be printed. 192 * \param[in] names Array of constraint columns names. 193 */ 194void osl_relation_list_pprint(FILE * file, osl_relation_list_p list, 195 osl_names_p names) { 196 int i; 197 198 // Count the number of elements in the list with non-NULL content. 199 i = osl_relation_list_count(list); 200 201 // Print it. 202 if (i > 1) 203 fprintf(file,"# List of %d elements\n%d\n", i, i); 204 else 205 fprintf(file,"# List of %d element \n%d\n", i, i); 206 207 // Print each element of the relation list. 208 osl_relation_list_pprint_elts(file, list, names); 209} 210 211 212/** 213 * osl_relation_list_print function: 214 * This function prints the content of a osl_relation_list_t structure 215 * into a file (file, possibly stdout) in the OpenScop format. It prints 216 * an element of the list only if it is not NULL. 217 * \param file File where informations are printed. 218 * \param list The relation list whose information has to be printed. 219 */ 220void osl_relation_list_print(FILE * file, osl_relation_list_p list) { 221 222 osl_relation_list_pprint(file, list, NULL); 223} 224 225/***************************************************************************** 226 * Reading function * 227 *****************************************************************************/ 228 229 230/** 231 * osl_relation_list_pread function ("precision read"): 232 * this function reads a list of relations into a file (foo, 233 * posibly stdin) and returns a pointer this relation list. 234 * \param[in] file The input stream. 235 * \param[in] precision The precision of the relation elements. 236 * \return A pointer to the relation list structure that has been read. 237 */ 238osl_relation_list_p osl_relation_list_pread(FILE * file, int precision) { 239 int i; 240 osl_relation_list_p list; 241 osl_relation_list_p res; 242 int nb_mat; 243 244 // Read the number of relations to read. 245 nb_mat = osl_util_read_int(file, NULL); 246 247 if (nb_mat < 0) 248 OSL_error("negative number of relations"); 249 250 // Allocate the header of the list and start reading each element. 251 res = list = osl_relation_list_malloc(); 252 for (i = 0; i < nb_mat; ++i) { 253 list->elt = osl_relation_pread(file, precision); 254 if (i < nb_mat - 1) 255 list->next = osl_relation_list_malloc(); 256 list = list->next; 257 } 258 259 return res; 260} 261 262 263/** 264 * osl_relation_list_read function: 265 * this function is equivalent to osl_relation_list_pread() except that 266 * the precision corresponds to the precision environment variable or 267 * to the highest available precision if it is not defined. 268 * \see{osl_relation_list_pread} 269 */ 270osl_relation_list_p osl_relation_list_read(FILE * foo) { 271 int precision = osl_util_get_precision(); 272 return osl_relation_list_pread(foo, precision); 273} 274 275 276/*+*************************************************************************** 277 * Memory allocation/deallocation function * 278 *****************************************************************************/ 279 280 281/** 282 * osl_relation_list_malloc function: 283 * This function allocates the memory space for a osl_relation_list_t 284 * structure and sets its fields with default values. Then it returns 285 * a pointer to the allocated space. 286 * \return A pointer to an empty relation list with fields set to default 287 * values. 288 */ 289osl_relation_list_p osl_relation_list_malloc() { 290 osl_relation_list_p res; 291 292 OSL_malloc(res, osl_relation_list_p, sizeof(osl_relation_list_t)); 293 res->elt = NULL; 294 res->next = NULL; 295 296 return res; 297} 298 299 300 301/** 302 * osl_relation_list_free function: 303 * This function frees the allocated memory for a osl_relation_list_t 304 * structure, and all the relations stored in the list. 305 * \param list The pointer to the relation list we want to free. 306 */ 307void osl_relation_list_free(osl_relation_list_p list) { 308 osl_relation_list_p tmp; 309 310 if (list == NULL) 311 return; 312 313 while (list != NULL) { 314 if (list->elt != NULL) 315 osl_relation_free(list->elt); 316 tmp = list->next; 317 free(list); 318 list = tmp; 319 } 320} 321 322 323/*+*************************************************************************** 324 * Processing functions * 325 *****************************************************************************/ 326 327 328/** 329 * osl_relation_list_node function: 330 * This function builds an osl_relation_list_t node and sets its 331 * relation element as a copy of the one provided as parameter. 332 * If the relation provided as an argument is NULL, NULL is returned. 333 * \param r The pointer to the relation to copy/paste in a list node. 334 * \return A pointer to a relation list node containing a copy of "relation". 335 */ 336osl_relation_list_p osl_relation_list_node(osl_relation_p r) { 337 osl_relation_list_p new = NULL; 338 339 if (r != NULL) { 340 new = osl_relation_list_malloc(); 341 new->elt = osl_relation_clone(r); 342 } 343 return new; 344} 345 346 347/** 348 * osl_relation_list_clone function: 349 * This functions builds and returns a quasi-"hard copy" (not a pointer copy) 350 * of a osl_relation_list_t data structure provided as parameter. 351 * \param list The pointer to the relation list we want to copy. 352 * \return A pointer to the full copy of the relation list in parameter. 353 */ 354osl_relation_list_p osl_relation_list_clone(osl_relation_list_p list) { 355 356 osl_relation_list_p clone = NULL, node, previous = NULL; 357 int first = 1; 358 359 while (list != NULL) { 360 node = osl_relation_list_malloc(); 361 node->elt = osl_relation_clone(list->elt); 362 363 if (first) { 364 first = 0; 365 clone = node; 366 previous = node; 367 } 368 else { 369 previous->next = node; 370 previous = previous->next; 371 } 372 373 list = list->next; 374 } 375 376 return clone; 377} 378 379 380/** 381 * osl_relation_list_concat function: 382 * this function builds a new relation list as the concatenation of the 383 * two lists sent as parameters. 384 * \param l1 The first relation list. 385 * \param l2 The second relation list. 386 * \return A pointer to the relation list resulting from the concatenation of 387 * l1 and l2. 388 */ 389osl_relation_list_p osl_relation_list_concat(osl_relation_list_p l1, 390 osl_relation_list_p l2) { 391 osl_relation_list_p new, end; 392 393 if (l1 == NULL) 394 return osl_relation_list_clone(l2); 395 396 if (l2 == NULL) 397 return osl_relation_list_clone(l1); 398 399 new = osl_relation_list_clone(l1); 400 end = new; 401 while (end->next != NULL) 402 end = end->next; 403 end->next = osl_relation_list_clone(l2); 404 405 return new; 406} 407 408 409/** 410 * osl_relation_list_add function: 411 * this function adds a relation list at the end of the relation list 412 * pointed by l1. No new list is created: this functions links the two 413 * input lists. If the first relation list is NULL, it is set to the 414 * second relation list. 415 * \param[in,out] l1 Pointer to the first relation list. 416 * \param[in] l2 The second relation list. 417 */ 418void osl_relation_list_add(osl_relation_list_p *l1, osl_relation_list_p l2) { 419 while (*l1 != NULL) 420 l1 = &((*l1)->next); 421 422 *l1 = l2; 423} 424 425 426/** 427 * osl_relation_list_push function: 428 * this function sees a list of relations as a stack of relations and 429 * performs the push operation onto this stack. 430 * \param[in,out] head Pointer to the head of the relation stack. 431 * \param[in,out] node Relation node to add to the stack. Its next field is 432 * updated to the previous head of the stack. 433 */ 434void osl_relation_list_push(osl_relation_list_p *head, 435 osl_relation_list_p node) { 436 if (node != NULL) { 437 node->next = *head; 438 *head = node; 439 } 440} 441 442 443/** 444 * osl_relation_list_pop function: 445 * this function sees a list of relations as a stack of relations and 446 * performs the pop operation onto this stack. 447 * \param[in,out] head Pointer to the head of the relation stack. It is 448 * updated to the previous element in the stack (NULL 449 * if there is none). 450 * \return The top element of the stack (detached from the list). 451 */ 452osl_relation_list_p osl_relation_list_pop(osl_relation_list_p *head) { 453 osl_relation_list_p top = NULL; 454 455 if (*head != NULL) { 456 top = *head; 457 *head = (*head)->next; 458 top->next = NULL; 459 } 460 461 return top; 462} 463 464 465/** 466 * osl_relation_list_dup function: 467 * this function sees a list of relations as a stack of relations and 468 * performs the dup operation (duplicate the top element) onto 469 * this stack. 470 * \param[in,out] head Pointer to the head of the relation stack. It is 471 * updated to the new element after duplication. 472 */ 473void osl_relation_list_dup(osl_relation_list_p *head) { 474 osl_relation_list_p top = osl_relation_list_pop(head); 475 osl_relation_list_push(head, osl_relation_list_clone(top)); 476 osl_relation_list_push(head, top); 477} 478 479 480/** 481 * osl_relation_list_drop function: 482 * this function sees a list of relations as a stack of relations and 483 * performs the drop operation (pop and destroy popped element) onto 484 * this stack. 485 * \param[in,out] head Pointer to the head of the relation stack. It is 486 * updated to the previous element in the stack (NULL 487 * if there is none). 488 */ 489void osl_relation_list_drop(osl_relation_list_p *head) { 490 osl_relation_list_p top = osl_relation_list_pop(head); 491 osl_relation_list_free(top); 492} 493 494 495/** 496 * osl_relation_list_destroy function: 497 * this function sees a list of relations as a stack of relations and 498 * performs the destroy operation onto this stack, i.e., it completely 499 * free it. 500 * \param[in,out] head Pointer to the head of the relation stack. 501 * Updated to NULL. 502 */ 503void osl_relation_list_destroy(osl_relation_list_p *head) { 504 505 while (*head != NULL) 506 osl_relation_list_drop(head); 507} 508 509 510/** 511 * osl_relation_list_equal function: 512 * This function returns true if the two relation lists are the same, false 513 * otherwise.. 514 * \param l1 The first relation list. 515 * \param l2 The second relation list. 516 * \return 1 if l1 and l2 are the same (content-wise), 0 otherwise. 517 */ 518int osl_relation_list_equal(osl_relation_list_p l1, osl_relation_list_p l2) { 519 while ((l1 != NULL) && (l2 != NULL)) { 520 if (l1 == l2) 521 return 1; 522 523 if (!osl_relation_equal(l1->elt, l2->elt)) 524 return 0; 525 526 l1 = l1->next; 527 l2 = l2->next; 528 } 529 530 if (((l1 == NULL) && (l2 != NULL)) || ((l1 != NULL) && (l2 == NULL))) 531 return 0; 532 533 return 1; 534} 535 536 537/** 538 * osl_relation_integrity_check function: 539 * This function checks that a list of relation is "well formed" according to 540 * some expected properties (setting an expected value to OSL_UNDEFINED 541 * means that we do not expect a specific value) and what the relations are 542 * supposed to represent (all relations of a list are supposed to have the 543 * same semantics). It returns 0 if the check failed or 1 if no problem has 544 * been detected. 545 * \param list The relation list we want to check. 546 * \param type Semantics about this relation (domain, access...). 547 * \param expected_nb_output_dims Expected number of output dimensions. 548 * \param expected_nb_input_dims Expected number of input dimensions. 549 * \param expected_nb_parameters Expected number of parameters. 550 * \return 0 if the integrity check fails, 1 otherwise. 551 */ 552int osl_relation_list_integrity_check(osl_relation_list_p list, 553 int type, 554 int expected_nb_output_dims, 555 int expected_nb_input_dims, 556 int expected_nb_parameters) { 557 while (list != NULL) { 558 // Check the access function. 559 if (!osl_relation_integrity_check(list->elt, 560 type, 561 expected_nb_output_dims, 562 expected_nb_input_dims, 563 expected_nb_parameters)) { 564 return 0; 565 } 566 567 list = list->next; 568 } 569 570 return 1; 571} 572 573 574/** 575 * osl_relation_list_set_type function: 576 * this function sets the type of each relation in the relation list to the 577 * one provided as parameter. 578 * \param list The list of relations to set the type. 579 * \param type The type. 580 */ 581void osl_relation_list_set_type(osl_relation_list_p list, int type) { 582 583 while (list != NULL) { 584 if (list->elt != NULL) { 585 list->elt->type = type; 586 } 587 list = list->next; 588 } 589} 590 591 592/** 593 * osl_relation_list_filter function: 594 * this function returns a copy of the input relation list, restricted to 595 * the relations of a given type. The special type OSL_TYPE_ACCESS 596 * filters any kind of access (read, write, rdwr etc.). 597 * \param list The relation list to copy/filter. 598 * \param type The filtering type. 599 * \return A copy of the input list with only relation of the given type. 600 */ 601osl_relation_list_p osl_relation_list_filter(osl_relation_list_p list, 602 int type) { 603 604 osl_relation_list_p copy = osl_relation_list_clone(list); 605 osl_relation_list_p filtered = NULL; 606 osl_relation_list_p previous = NULL; 607 osl_relation_list_p trash; 608 int first = 1; 609 610 while (copy != NULL) { 611 if ((copy->elt != NULL) && 612 (((type == OSL_TYPE_ACCESS) && 613 (osl_relation_is_access(copy->elt))) || 614 ((type != OSL_TYPE_ACCESS) && 615 (type == copy->elt->type)))) { 616 if (first) { 617 filtered = copy; 618 first = 0; 619 } 620 621 previous = copy; 622 copy = copy->next; 623 } 624 else { 625 trash = copy; 626 if (!first) 627 previous->next = copy->next; 628 copy = copy->next; 629 trash->next = NULL; 630 osl_relation_list_free(trash); 631 } 632 } 633 634 return filtered; 635} 636 637 638/** 639 * osl_relation_list_count function: 640 * this function returns the number of elements with non-NULL content 641 * in a relation list. 642 * \param list The relation list to count the number of elements. 643 * \return The number of nodes with non-NULL content in the relation list. 644 */ 645int osl_relation_list_count(osl_relation_list_p list) { 646 int i = 0; 647 648 while (list != NULL) { 649 if (list->elt != NULL) 650 i++; 651 list = list->next; 652 } 653 654 return i; 655} 656 657 658/** 659 * osl_relation_list_get_attributes function: 660 * this function returns, through its parameters, the maximum values of the 661 * relation attributes (nb_iterators, nb_parameters etc) in the relation list, 662 * depending on its type. HOWEVER, it updates the parameter value iff the 663 * attribute is greater than the input parameter value. Hence it may be used 664 * to get the attributes as well as to find the maximum attributes for several 665 * relation lists. The array identifier 0 is used when there is no array 666 * identifier (AND this is OK), OSL_UNDEFINED is used to report it is 667 * impossible to provide the property while it should. This function is not 668 * intended for checking, the input relation list should be correct. 669 * \param[in] list The relation list to extract attribute values. 670 * \param[in,out] nb_parameters Number of parameter attribute. 671 * \param[in,out] nb_iterators Number of iterators attribute. 672 * \param[in,out] nb_scattdims Number of scattering dimensions attribute. 673 * \param[in,out] nb_localdims Number of local dimensions attribute. 674 * \param[in,out] array_id Maximum array identifier attribute. 675 */ 676void osl_relation_list_get_attributes(osl_relation_list_p list, 677 int * nb_parameters, 678 int * nb_iterators, 679 int * nb_scattdims, 680 int * nb_localdims, 681 int * array_id) { 682 int local_nb_parameters = OSL_UNDEFINED; 683 int local_nb_iterators = OSL_UNDEFINED; 684 int local_nb_scattdims = OSL_UNDEFINED; 685 int local_nb_localdims = OSL_UNDEFINED; 686 int local_array_id = OSL_UNDEFINED; 687 688 while (list != NULL) { 689 osl_relation_get_attributes(list->elt, 690 &local_nb_parameters, 691 &local_nb_iterators, 692 &local_nb_scattdims, 693 &local_nb_localdims, 694 &local_array_id); 695 // Update. 696 *nb_parameters = OSL_max(*nb_parameters, local_nb_parameters); 697 *nb_iterators = OSL_max(*nb_iterators, local_nb_iterators); 698 *nb_scattdims = OSL_max(*nb_scattdims, local_nb_scattdims); 699 *nb_localdims = OSL_max(*nb_localdims, local_nb_localdims); 700 *array_id = OSL_max(*array_id, local_array_id); 701 list = list->next; 702 } 703} 704 705