OpenScop
0.9.0
|
00001 00002 /*+-----------------------------------------------------------------** 00003 ** OpenScop Library ** 00004 **-----------------------------------------------------------------** 00005 ** relation_list.c ** 00006 **-----------------------------------------------------------------** 00007 ** First version: 08/10/2010 ** 00008 **-----------------------------------------------------------------** 00009 00010 00011 ***************************************************************************** 00012 * OpenScop: Structures and formats for polyhedral tools to talk together * 00013 ***************************************************************************** 00014 * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, * 00015 * / / / // // // // / / / // // / / // / /|,_, * 00016 * / / / // // // // / / / // // / / // / / / /\ * 00017 * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ * 00018 * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ * 00019 * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ * 00020 * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ * 00021 * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ * 00022 * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ * 00023 * | I | | | | e | | | | | | | | | | | | | \ \ \ * 00024 * | T | | | | | | | | | | | | | | | | | \ \ \ * 00025 * | E | | | | | | | | | | | | | | | | | \ \ \ * 00026 * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ * 00027 * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / * 00028 * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' * 00029 * * 00030 * Copyright (C) 2008 University Paris-Sud 11 and INRIA * 00031 * * 00032 * (3-clause BSD license) * 00033 * Redistribution and use in source and binary forms, with or without * 00034 * modification, are permitted provided that the following conditions * 00035 * are met: * 00036 * * 00037 * 1. Redistributions of source code must retain the above copyright notice, * 00038 * this list of conditions and the following disclaimer. * 00039 * 2. Redistributions in binary form must reproduce the above copyright * 00040 * notice, this list of conditions and the following disclaimer in the * 00041 * documentation and/or other materials provided with the distribution. * 00042 * 3. The name of the author may not be used to endorse or promote products * 00043 * derived from this software without specific prior written permission. * 00044 * * 00045 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * 00046 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * 00047 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * 00048 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * 00049 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * 00050 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * 00051 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * 00052 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * 00053 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * 00054 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * 00055 * * 00056 * OpenScop Library, a library to manipulate OpenScop formats and data * 00057 * structures. Written by: * 00058 * Cedric Bastoul <Cedric.Bastoul@u-psud.fr> and * 00059 * Louis-Noel Pouchet <Louis-Noel.pouchet@inria.fr> * 00060 * * 00061 *****************************************************************************/ 00062 00063 00064 #include <stdlib.h> 00065 #include <stdio.h> 00066 #include <string.h> 00067 #include <ctype.h> 00068 00069 #include <osl/macros.h> 00070 #include <osl/util.h> 00071 #include <osl/relation.h> 00072 #include <osl/relation_list.h> 00073 00074 00075 /*+*************************************************************************** 00076 * Structure display function * 00077 *****************************************************************************/ 00078 00079 00089 void osl_relation_list_idump(FILE * file, osl_relation_list_p l, int level) { 00090 int j, first = 1; 00091 00092 // Go to the right level. 00093 for (j = 0; j < level; j++) 00094 fprintf(file,"|\t"); 00095 00096 if (l != NULL) 00097 fprintf(file, "+-- osl_relation_list_t\n"); 00098 else 00099 fprintf(file, "+-- NULL relation list\n"); 00100 00101 while (l != NULL) { 00102 if (!first) { 00103 // Go to the right level. 00104 for (j = 0; j < level; j++) 00105 fprintf(file, "|\t"); 00106 fprintf(file, "| osl_relation_list_t\n"); 00107 } 00108 else 00109 first = 0; 00110 00111 // A blank line. 00112 for (j = 0; j <= level+1; j++) 00113 fprintf(file, "|\t"); 00114 fprintf(file, "\n"); 00115 00116 // Print a relation. 00117 osl_relation_idump(file, l->elt, level+1); 00118 00119 l = l->next; 00120 00121 // Next line. 00122 if (l != NULL) { 00123 for (j = 0; j <= level; j++) 00124 fprintf(file, "|\t"); 00125 fprintf(file, "V\n"); 00126 } 00127 } 00128 00129 // The last line. 00130 for (j = 0; j <= level; j++) 00131 fprintf(file, "|\t"); 00132 fprintf(file, "\n"); 00133 } 00134 00135 00143 void osl_relation_list_dump(FILE * file, osl_relation_list_p list) { 00144 osl_relation_list_idump(file, list, 0); 00145 } 00146 00147 00158 void osl_relation_list_pprint_elts(FILE * file, osl_relation_list_p list, 00159 osl_names_p names) { 00160 size_t i; 00161 osl_relation_list_p head = list; 00162 00163 // Count the number of elements in the list with non-NULL content. 00164 i = osl_relation_list_count(list); 00165 00166 // Print each element of the relation list. 00167 if (i > 0) { 00168 i = 0; 00169 while (head) { 00170 if (head->elt != NULL) { 00171 osl_relation_pprint(file, head->elt, names); 00172 if (head->next != NULL) 00173 fprintf(file, "\n"); 00174 i++; 00175 } 00176 head = head->next; 00177 } 00178 } 00179 else { 00180 fprintf(file, "# NULL relation list\n"); 00181 } 00182 } 00183 00184 00196 void osl_relation_list_pprint_access_array_scoplib(FILE * file, 00197 osl_relation_list_p list, osl_names_p names, int add_fakeiter) { 00198 size_t i; 00199 int nb_rows_read = 0, nb_columns_read = 0; 00200 int nb_rows_write = 0, nb_columns_write = 0; 00201 int nb_rows_may_write = 0, nb_columns_may_write = 0; 00202 osl_relation_list_p head ; 00203 00204 // Count the number of elements in the list with non-NULL content. 00205 i = osl_relation_list_count(list); 00206 00207 // Print each element of the relation list. 00208 if (i > 0) { 00209 00210 // Read/Write arrays size 00211 head = list; 00212 while (head) { 00213 if (head->elt != NULL) { 00214 if (head->elt->type == OSL_TYPE_READ) { 00215 if (head->elt->nb_rows == 1) 00216 nb_rows_read++; 00217 else 00218 nb_rows_read += head->elt->nb_rows - 1; // remove the 'Arr' 00219 00220 nb_columns_read = head->elt->nb_columns - head->elt->nb_output_dims; 00221 00222 } else if (head->elt->type == OSL_TYPE_WRITE) { 00223 if (head->elt->nb_rows == 1) 00224 nb_rows_write++; 00225 else 00226 nb_rows_write += head->elt->nb_rows - 1; // remove the 'Arr' 00227 00228 nb_columns_write = head->elt->nb_columns - head->elt->nb_output_dims; 00229 00230 } else if (head->elt->type == OSL_TYPE_MAY_WRITE) { 00231 if (head->elt->nb_rows == 1) 00232 nb_rows_may_write++; 00233 else 00234 nb_rows_may_write += head->elt->nb_rows - 1; // remove the 'Arr' 00235 00236 nb_columns_may_write = head->elt->nb_columns - 00237 head->elt->nb_output_dims; 00238 } 00239 } 00240 head = head->next; 00241 } 00242 00243 if (add_fakeiter) { 00244 nb_columns_read++; 00245 nb_columns_write++; 00246 nb_columns_may_write++; 00247 } 00248 00249 fprintf(file, "# Read access informations\n%d %d\n", 00250 nb_rows_read, nb_columns_read); 00251 head = list; 00252 while (head) { 00253 if (head->elt != NULL && head->elt->type == OSL_TYPE_READ) { 00254 osl_relation_pprint_scoplib(file, head->elt, names, 0, add_fakeiter); 00255 } 00256 head = head->next; 00257 } 00258 00259 fprintf(file, "# Write access informations\n%d %d\n", 00260 nb_rows_write, nb_columns_write); 00261 head = list; 00262 while (head) { 00263 if (head->elt != NULL && head->elt->type == OSL_TYPE_WRITE) { 00264 osl_relation_pprint_scoplib(file, head->elt, names, 0, add_fakeiter); 00265 } 00266 head = head->next; 00267 } 00268 00269 if (nb_rows_may_write > 0) { 00270 fprintf(file, "# May Write access informations\n%d %d\n", 00271 nb_rows_may_write, nb_columns_may_write); 00272 head = list; 00273 while (head) { 00274 if (head->elt != NULL && head->elt->type == OSL_TYPE_MAY_WRITE) { 00275 osl_relation_pprint_scoplib(file, head->elt, names, 0, add_fakeiter); 00276 } 00277 head = head->next; 00278 } 00279 } 00280 } 00281 else { 00282 fprintf(file, "# NULL relation list\n"); 00283 } 00284 } 00285 00286 00296 void osl_relation_list_pprint(FILE * file, osl_relation_list_p list, 00297 osl_names_p names) { 00298 size_t i; 00299 00300 // Count the number of elements in the list with non-NULL content. 00301 i = osl_relation_list_count(list); 00302 00303 // Print it. 00304 if (i > 1) 00305 fprintf(file,"# List of %lu elements\n%lu\n", i, i); 00306 else 00307 fprintf(file,"# List of %lu element \n%lu\n", i, i); 00308 00309 // Print each element of the relation list. 00310 osl_relation_list_pprint_elts(file, list, names); 00311 } 00312 00313 00322 void osl_relation_list_print(FILE * file, osl_relation_list_p list) { 00323 00324 osl_relation_list_pprint(file, list, NULL); 00325 } 00326 00327 /***************************************************************************** 00328 * Reading function * 00329 *****************************************************************************/ 00330 00331 00340 osl_relation_list_p osl_relation_list_pread(FILE * file, int precision) { 00341 int i; 00342 osl_relation_list_p list; 00343 osl_relation_list_p res; 00344 int nb_mat; 00345 00346 // Read the number of relations to read. 00347 nb_mat = osl_util_read_int(file, NULL); 00348 00349 if (nb_mat < 0) 00350 OSL_error("negative number of relations"); 00351 00352 // Allocate the header of the list and start reading each element. 00353 res = list = osl_relation_list_malloc(); 00354 for (i = 0; i < nb_mat; ++i) { 00355 list->elt = osl_relation_pread(file, precision); 00356 if (i < nb_mat - 1) 00357 list->next = osl_relation_list_malloc(); 00358 list = list->next; 00359 } 00360 00361 return res; 00362 } 00363 00364 00372 osl_relation_list_p osl_relation_list_read(FILE * foo) { 00373 int precision = osl_util_get_precision(); 00374 return osl_relation_list_pread(foo, precision); 00375 } 00376 00377 00378 /*+*************************************************************************** 00379 * Memory allocation/deallocation function * 00380 *****************************************************************************/ 00381 00382 00391 osl_relation_list_p osl_relation_list_malloc() { 00392 osl_relation_list_p res; 00393 00394 OSL_malloc(res, osl_relation_list_p, sizeof(osl_relation_list_t)); 00395 res->elt = NULL; 00396 res->next = NULL; 00397 00398 return res; 00399 } 00400 00401 00402 00409 void osl_relation_list_free(osl_relation_list_p list) { 00410 osl_relation_list_p tmp; 00411 00412 if (list == NULL) 00413 return; 00414 00415 while (list != NULL) { 00416 if (list->elt != NULL) 00417 osl_relation_free(list->elt); 00418 tmp = list->next; 00419 free(list); 00420 list = tmp; 00421 } 00422 } 00423 00424 00425 /*+*************************************************************************** 00426 * Processing functions * 00427 *****************************************************************************/ 00428 00429 00438 osl_relation_list_p osl_relation_list_node(osl_relation_p r) { 00439 osl_relation_list_p new = NULL; 00440 00441 if (r != NULL) { 00442 new = osl_relation_list_malloc(); 00443 new->elt = osl_relation_clone(r); 00444 } 00445 return new; 00446 } 00447 00448 00456 osl_relation_list_p osl_relation_list_clone(osl_relation_list_p list) { 00457 00458 osl_relation_list_p clone = NULL, node, previous = NULL; 00459 int first = 1; 00460 00461 while (list != NULL) { 00462 node = osl_relation_list_malloc(); 00463 node->elt = osl_relation_clone(list->elt); 00464 00465 if (first) { 00466 first = 0; 00467 clone = node; 00468 previous = node; 00469 } 00470 else { 00471 previous->next = node; 00472 previous = previous->next; 00473 } 00474 00475 list = list->next; 00476 } 00477 00478 return clone; 00479 } 00480 00481 00491 osl_relation_list_p osl_relation_list_concat(osl_relation_list_p l1, 00492 osl_relation_list_p l2) { 00493 osl_relation_list_p new, end; 00494 00495 if (l1 == NULL) 00496 return osl_relation_list_clone(l2); 00497 00498 if (l2 == NULL) 00499 return osl_relation_list_clone(l1); 00500 00501 new = osl_relation_list_clone(l1); 00502 end = new; 00503 while (end->next != NULL) 00504 end = end->next; 00505 end->next = osl_relation_list_clone(l2); 00506 00507 return new; 00508 } 00509 00510 00520 void osl_relation_list_add(osl_relation_list_p *l1, osl_relation_list_p l2) { 00521 while (*l1 != NULL) 00522 l1 = &((*l1)->next); 00523 00524 *l1 = l2; 00525 } 00526 00527 00536 void osl_relation_list_push(osl_relation_list_p *head, 00537 osl_relation_list_p node) { 00538 if (node != NULL) { 00539 node->next = *head; 00540 *head = node; 00541 } 00542 } 00543 00544 00554 osl_relation_list_p osl_relation_list_pop(osl_relation_list_p *head) { 00555 osl_relation_list_p top = NULL; 00556 00557 if (*head != NULL) { 00558 top = *head; 00559 *head = (*head)->next; 00560 top->next = NULL; 00561 } 00562 00563 return top; 00564 } 00565 00566 00575 void osl_relation_list_dup(osl_relation_list_p *head) { 00576 osl_relation_list_p top = osl_relation_list_pop(head); 00577 osl_relation_list_push(head, osl_relation_list_clone(top)); 00578 osl_relation_list_push(head, top); 00579 } 00580 00581 00591 void osl_relation_list_drop(osl_relation_list_p *head) { 00592 osl_relation_list_p top = osl_relation_list_pop(head); 00593 osl_relation_list_free(top); 00594 } 00595 00596 00605 void osl_relation_list_destroy(osl_relation_list_p *head) { 00606 00607 while (*head != NULL) 00608 osl_relation_list_drop(head); 00609 } 00610 00611 00620 int osl_relation_list_equal(osl_relation_list_p l1, osl_relation_list_p l2) { 00621 while ((l1 != NULL) && (l2 != NULL)) { 00622 if (l1 == l2) 00623 return 1; 00624 00625 if (!osl_relation_equal(l1->elt, l2->elt)) 00626 return 0; 00627 00628 l1 = l1->next; 00629 l2 = l2->next; 00630 } 00631 00632 if (((l1 == NULL) && (l2 != NULL)) || ((l1 != NULL) && (l2 == NULL))) 00633 return 0; 00634 00635 return 1; 00636 } 00637 00638 00654 int osl_relation_list_integrity_check(osl_relation_list_p list, 00655 int type, 00656 int expected_nb_output_dims, 00657 int expected_nb_input_dims, 00658 int expected_nb_parameters) { 00659 while (list != NULL) { 00660 // Check the access function. 00661 if (!osl_relation_integrity_check(list->elt, 00662 type, 00663 expected_nb_output_dims, 00664 expected_nb_input_dims, 00665 expected_nb_parameters)) { 00666 return 0; 00667 } 00668 00669 list = list->next; 00670 } 00671 00672 return 1; 00673 } 00674 00675 00683 void osl_relation_list_set_type(osl_relation_list_p list, int type) { 00684 00685 while (list != NULL) { 00686 if (list->elt != NULL) { 00687 list->elt->type = type; 00688 } 00689 list = list->next; 00690 } 00691 } 00692 00693 00703 osl_relation_list_p osl_relation_list_filter(osl_relation_list_p list, 00704 int type) { 00705 00706 osl_relation_list_p copy = osl_relation_list_clone(list); 00707 osl_relation_list_p filtered = NULL; 00708 osl_relation_list_p previous = NULL; 00709 osl_relation_list_p trash; 00710 int first = 1; 00711 00712 while (copy != NULL) { 00713 if ((copy->elt != NULL) && 00714 (((type == OSL_TYPE_ACCESS) && 00715 (osl_relation_is_access(copy->elt))) || 00716 ((type != OSL_TYPE_ACCESS) && 00717 (type == copy->elt->type)))) { 00718 if (first) { 00719 filtered = copy; 00720 first = 0; 00721 } 00722 00723 previous = copy; 00724 copy = copy->next; 00725 } 00726 else { 00727 trash = copy; 00728 if (!first) 00729 previous->next = copy->next; 00730 copy = copy->next; 00731 trash->next = NULL; 00732 osl_relation_list_free(trash); 00733 } 00734 } 00735 00736 return filtered; 00737 } 00738 00739 00747 size_t osl_relation_list_count(osl_relation_list_p list) { 00748 size_t i = 0; 00749 00750 while (list != NULL) { 00751 if (list->elt != NULL) 00752 i++; 00753 list = list->next; 00754 } 00755 00756 return i; 00757 } 00758 00759 00778 void osl_relation_list_get_attributes(osl_relation_list_p list, 00779 int * nb_parameters, 00780 int * nb_iterators, 00781 int * nb_scattdims, 00782 int * nb_localdims, 00783 int * array_id) { 00784 int local_nb_parameters = OSL_UNDEFINED; 00785 int local_nb_iterators = OSL_UNDEFINED; 00786 int local_nb_scattdims = OSL_UNDEFINED; 00787 int local_nb_localdims = OSL_UNDEFINED; 00788 int local_array_id = OSL_UNDEFINED; 00789 00790 while (list != NULL) { 00791 osl_relation_get_attributes(list->elt, 00792 &local_nb_parameters, 00793 &local_nb_iterators, 00794 &local_nb_scattdims, 00795 &local_nb_localdims, 00796 &local_array_id); 00797 // Update. 00798 *nb_parameters = OSL_max(*nb_parameters, local_nb_parameters); 00799 *nb_iterators = OSL_max(*nb_iterators, local_nb_iterators); 00800 *nb_scattdims = OSL_max(*nb_scattdims, local_nb_scattdims); 00801 *nb_localdims = OSL_max(*nb_localdims, local_nb_localdims); 00802 *array_id = OSL_max(*array_id, local_array_id); 00803 list = list->next; 00804 } 00805 } 00806