OpenScop
0.9.0
|
00001 00002 /*+-----------------------------------------------------------------** 00003 ** OpenScop Library ** 00004 **-----------------------------------------------------------------** 00005 ** extensions/loop.c ** 00006 **-----------------------------------------------------------------** 00007 ** First version: 03/06/2013 ** 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 #include <stdlib.h> 00064 #include <stdio.h> 00065 #include <string.h> 00066 #include <ctype.h> 00067 00068 #include <osl/macros.h> 00069 #include <osl/util.h> 00070 #include <osl/strings.h> 00071 #include <osl/interface.h> 00072 #include <osl/extensions/loop.h> 00073 00074 00075 /*+*************************************************************************** 00076 * Structure display function * 00077 *****************************************************************************/ 00078 00079 00091 void osl_loop_idump(FILE * file, osl_loop_p loop, int level) { 00092 int i, j, first = 1, number=1; 00093 00094 // Go to the right level. 00095 for (j = 0; j < level; j++) 00096 fprintf(file, "|\t"); 00097 00098 if (loop != NULL) 00099 fprintf(file, "+-- osl_loop_t\n"); 00100 else 00101 fprintf(file, "+-- NULL loop\n"); 00102 00103 while (loop != NULL) { 00104 // Go to the right level. 00105 if (!first) { 00106 // Go to the right level. 00107 for (j = 0; j < level; j++) 00108 fprintf(file, "|\t"); 00109 00110 fprintf(file, "| osl_loop_t (node %d)\n", number); 00111 } else { 00112 first = 0; 00113 } 00114 00115 // A blank line. 00116 for (j = 0; j <= level+1; j++) 00117 fprintf(file, "|\t"); 00118 fprintf(file, "\n"); 00119 00120 // Display the number of names. 00121 for (j = 0; j <= level; j++) 00122 fprintf(file, "|\t"); 00123 fprintf(file, "+--iterator: %s\n", loop->iter); 00124 00125 for (j = 0; j <= level; j++) 00126 fprintf(file, "|\t"); 00127 fprintf(file, "+--nb_stmts: %d\n", loop->nb_stmts); 00128 00129 // Display the id/name. 00130 for (j = 0; j <= level; j++) 00131 fprintf(file, "|\t"); 00132 fprintf(file, "+--stmt_ids:"); 00133 for(i = 0; i < loop->nb_stmts; i++) { 00134 // Go to the right level. 00135 fprintf(file, "%2d, ", loop->stmt_ids[i]); 00136 } 00137 fprintf(file, "\n"); 00138 00139 00140 for (j = 0; j <= level; j++) 00141 fprintf(file, "|\t"); 00142 fprintf(file, "+--private_vars: %s\n", loop->private_vars); 00143 00144 for (j = 0; j <= level; j++) 00145 fprintf(file, "|\t"); 00146 fprintf(file, "+--directive: %d\n", loop->directive); 00147 00148 loop = loop->next; 00149 number++; 00150 00151 // Next line. 00152 if (loop != NULL) { 00153 for (j = 0; j <= level; j++) 00154 fprintf(file, "|\t"); 00155 fprintf(file, "V\n"); 00156 } 00157 } 00158 00159 // The last line. 00160 for (j = 0; j <= level; j++) 00161 fprintf(file, "|\t"); 00162 fprintf(file, "\n"); 00163 } 00164 00165 00174 void osl_loop_dump(FILE * file, osl_loop_p loop) { 00175 osl_loop_idump(file, loop, 0); 00176 } 00177 00178 00186 char * osl_loop_sprint(osl_loop_p loop) { 00187 int i; 00188 int nloop = 0; 00189 int high_water_mark = OSL_MAX_STRING; 00190 char *string = NULL; 00191 char buffer[OSL_MAX_STRING]; 00192 00193 OSL_malloc(string, char *, high_water_mark * sizeof(char)); 00194 string[0] = '\0'; 00195 00196 sprintf(buffer, "# Number of loops\n%d\n",osl_loop_count(loop)); 00197 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00198 00199 while (loop != NULL) { 00200 sprintf(buffer, "# ===========================================\n"); 00201 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00202 00203 sprintf(buffer, "# Loop number %d \n", ++nloop); 00204 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00205 00206 sprintf(buffer, "# Iterator name\n"); 00207 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00208 sprintf(buffer, "%s\n", loop->iter); 00209 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00210 00211 sprintf(buffer, "# Number of stmts\n"); 00212 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00213 sprintf(buffer, "%d\n", loop->nb_stmts); 00214 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00215 00216 if (loop->nb_stmts) { 00217 sprintf(buffer, "# Statement identifiers\n"); 00218 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00219 } 00220 for (i = 0; i < loop->nb_stmts; i++) { 00221 sprintf(buffer, "%d\n", loop->stmt_ids[i]); 00222 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00223 } 00224 00225 sprintf(buffer, "# Private variables\n"); 00226 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00227 sprintf(buffer, "%s\n", loop->private_vars); 00228 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00229 00230 sprintf(buffer, "# Directive\n"); 00231 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00232 sprintf(buffer, "%d\n", loop->directive); 00233 osl_util_safe_strcat(&string, buffer, &high_water_mark); 00234 00235 loop = loop->next; 00236 } 00237 00238 OSL_realloc(string, char *, (strlen(string) + 1) * sizeof(char)); 00239 return string; 00240 } 00241 00242 00243 /***************************************************************************** 00244 * Reading function * 00245 *****************************************************************************/ 00246 00247 00259 osl_loop_p osl_loop_sread(char **input) { 00260 int i; 00261 int nb_loops; 00262 osl_loop_p head; 00263 osl_loop_p loop; 00264 00265 if (input == NULL) { 00266 OSL_debug("no loop optional tag"); 00267 return NULL; 00268 } 00269 00270 // Find the number of names provided. 00271 nb_loops = osl_util_read_int(NULL, input); 00272 if(nb_loops == 0) 00273 return NULL; 00274 00275 // Allocate the array of id and names. 00276 head = loop = osl_loop_malloc(); 00277 00278 while (nb_loops != 0) { 00279 00280 loop->iter = osl_util_read_string(NULL, input); 00281 loop->nb_stmts = osl_util_read_int(NULL, input); 00282 00283 OSL_malloc(loop->stmt_ids, int *, loop->nb_stmts * sizeof(int)); 00284 for (i = 0; i < loop->nb_stmts; i++) 00285 loop->stmt_ids[i] = osl_util_read_int(NULL, input); 00286 00287 loop->private_vars = osl_util_read_line(NULL, input); 00288 if (!strcmp(loop->private_vars, "(null)")) { 00289 free(loop->private_vars); 00290 loop->private_vars=NULL; 00291 } 00292 00293 loop->directive = osl_util_read_int(NULL, input); 00294 00295 nb_loops--; 00296 if (nb_loops != 0) { 00297 loop->next = osl_loop_malloc (); 00298 loop = loop->next; 00299 } 00300 } 00301 00302 return head; 00303 } 00304 00305 00306 /*+*************************************************************************** 00307 * Memory allocation/deallocation function * 00308 *****************************************************************************/ 00309 00310 00320 osl_loop_p osl_loop_malloc() { 00321 osl_loop_p loop; 00322 00323 OSL_malloc(loop, osl_loop_p, sizeof(osl_loop_t)); 00324 loop->iter = NULL; 00325 loop->nb_stmts = 0; 00326 loop->stmt_ids = NULL; 00327 loop->private_vars = NULL; 00328 loop->directive = 0; 00329 loop->next = NULL; 00330 00331 return loop; 00332 } 00333 00334 00341 void osl_loop_free(osl_loop_p loop) { 00342 00343 while (loop != NULL) { 00344 osl_loop_p tmp = loop; 00345 00346 if (loop->iter) free(loop->iter); 00347 if (loop->stmt_ids) free(loop->stmt_ids); 00348 if (loop->private_vars) free(loop->private_vars); 00349 00350 loop = loop->next; 00351 00352 free(tmp); 00353 } 00354 } 00355 00356 00357 /*+*************************************************************************** 00358 * Processing functions * 00359 *****************************************************************************/ 00360 00361 00370 osl_loop_p osl_loop_clone_one(osl_loop_p loop) { 00371 int i; 00372 osl_loop_p clone; 00373 00374 if (loop == NULL) 00375 return NULL; 00376 00377 clone = osl_loop_malloc(); 00378 OSL_strdup(clone->iter, loop->iter); 00379 clone->nb_stmts = loop->nb_stmts; 00380 OSL_malloc(clone->stmt_ids, int *, loop->nb_stmts * sizeof(int)); 00381 00382 for (i = 0; i < loop->nb_stmts; i++) { 00383 clone->stmt_ids[i] = loop->stmt_ids[i]; 00384 } 00385 00386 clone->directive = loop->directive; 00387 00388 if(loop->private_vars != NULL) 00389 OSL_strdup(clone->private_vars, loop->private_vars); 00390 00391 return clone; 00392 } 00393 00402 osl_loop_p osl_loop_clone(osl_loop_p loop) { 00403 osl_loop_p clone = NULL; 00404 osl_loop_p head = NULL; 00405 00406 if (loop == NULL) 00407 return NULL; 00408 00409 while (loop) { 00410 00411 if (clone==NULL) { 00412 head = clone = osl_loop_clone_one(loop); 00413 } 00414 else { 00415 clone->next = osl_loop_clone_one(loop); 00416 clone = clone->next; 00417 } 00418 00419 loop = loop->next; 00420 } 00421 00422 return head; 00423 } 00424 00436 int osl_loop_equal_one(osl_loop_p a1, osl_loop_p a2) { 00437 int i, j, found; 00438 00439 if (a1 == a2) 00440 return 1; 00441 00442 if (((a1 == NULL) && (a2 != NULL)) || ((a1 != NULL) && (a2 == NULL))) { 00443 //OSL_info("loops are not the same (compare with NULL)"); 00444 return 0; 00445 } 00446 00447 // Check whether the number of names is the same. 00448 if (a1->nb_stmts != a2->nb_stmts) { 00449 //OSL_info("loops are not the same (nb_stmts)"); 00450 return 0; 00451 } 00452 00453 if (strcmp(a1->iter, a2->iter)) { 00454 //OSL_info("loops are not the same (iter name)"); 00455 return 0; 00456 } 00457 // We accept a different order of the names, as long as the identifiers 00458 // are the same. 00459 for (i = 0; i < a1->nb_stmts; i++) { 00460 found = 0; 00461 for (j = 0; j < a2->nb_stmts; j++) { 00462 if (a1->stmt_ids[i] == a2->stmt_ids[j]) { 00463 found = 1; 00464 break; 00465 } 00466 } 00467 if (found != 1) { 00468 //OSL_info("loop are not the same (stmt ids)"); 00469 return 0; 00470 } 00471 } 00472 00473 //TODO: necessarily same ??? 00474 if (a1->private_vars != a2->private_vars) { // NULL check 00475 if (strcmp(a1->private_vars, a2->private_vars)) { 00476 //OSL_info("loops are not the same (private vars)"); 00477 return 0; 00478 } 00479 } 00480 00481 //TODO: necessarily same ??? 00482 if (a1->directive != a2->directive) { 00483 //OSL_info("loops are not the same (directive)"); 00484 return 0; 00485 } 00486 00487 return 1; 00488 } 00489 00501 int osl_loop_equal(osl_loop_p a1, osl_loop_p a2) { 00502 int found = 0; 00503 00504 if (a1 == a2) 00505 return 1; 00506 00507 if (((a1 == NULL) && (a2 != NULL)) || ((a1 != NULL) && (a2 == NULL))) { 00508 OSL_info("lists of loops are not the same (compare with NULL)"); 00509 return 0; 00510 } 00511 00512 if (osl_loop_count(a1) != osl_loop_count(a2)) { 00513 OSL_info("list of loops are not the same"); 00514 return 0; 00515 } 00516 00517 while (a1) { 00518 found = 0; 00519 osl_loop_p temp = a2; 00520 00521 while (temp) { 00522 if(osl_loop_equal_one(a1, temp)==1){ 00523 found= 1; 00524 break; 00525 } 00526 temp = temp->next; 00527 } 00528 00529 if(found!=1){ 00530 OSL_info("list of loops are not the same"); 00531 return 0; 00532 } 00533 a1 = a1->next; 00534 } 00535 00536 return 1; 00537 } 00538 00539 00547 osl_interface_p osl_loop_interface() { 00548 osl_interface_p interface = osl_interface_malloc(); 00549 00550 OSL_strdup(interface->URI, OSL_URI_LOOP); 00551 interface->idump = (osl_idump_f)osl_loop_idump; 00552 interface->sprint = (osl_sprint_f)osl_loop_sprint; 00553 interface->sread = (osl_sread_f)osl_loop_sread; 00554 interface->malloc = (osl_malloc_f)osl_loop_malloc; 00555 interface->free = (osl_free_f)osl_loop_free; 00556 interface->clone = (osl_clone_f)osl_loop_clone; 00557 interface->equal = (osl_equal_f)osl_loop_equal; 00558 00559 return interface; 00560 } 00561 00562 00570 void osl_loop_add(osl_loop_p loop, osl_loop_p *ll) { 00571 00572 while (*ll != NULL) 00573 ll = &(*ll)->next; 00574 00575 *ll = loop; 00576 } 00577 00578 00586 int osl_loop_count(osl_loop_p ll) { 00587 int count = 0; 00588 while (ll) { 00589 count++; 00590 ll = ll->next; 00591 } 00592 00593 return count; 00594 }