|
OpenScop
0.9.0
|
00001 00002 /*+-----------------------------------------------------------------** 00003 ** OpenScop Library ** 00004 **-----------------------------------------------------------------** 00005 ** extensions/dependence.h ** 00006 **-----------------------------------------------------------------** 00007 ** First version: 02/07/2012 ** 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 <osl/macros.h> 00067 #include <osl/scop.h> 00068 #include <osl/statement.h> 00069 #include <osl/relation.h> 00070 #include <osl/names.h> 00071 #include <osl/util.h> 00072 #include <osl/extensions/dependence.h> 00073 00078 /****************************************************************************** 00079 * Structure display function * 00080 ******************************************************************************/ 00081 00082 00092 void osl_dependence_idump(FILE* file, 00093 osl_dependence_p dependence, 00094 int level) { 00095 int j, first = 1; 00096 osl_statement_p tmp; 00097 00098 if (dependence != NULL) { /* Go to the right level. */ 00099 for (j=0; j<level; j++) 00100 fprintf(file, "|\t"); 00101 fprintf(file, "+-- osl_dependence_p\n"); 00102 } else { 00103 for (j=0; j<level; j++) 00104 fprintf(file, "|\t"); 00105 fprintf(file, "+-- NULL dependence\n"); 00106 } 00107 00108 while (dependence != NULL) { 00109 if (!first) { /* Go to the right level. */ 00110 for (j=0; j<level; j++) 00111 fprintf(file, "|\t"); 00112 fprintf(file, "| osl_dependence_p\n"); 00113 } else { 00114 first = 0; 00115 } 00116 00117 /* A blank line. */ 00118 for (j=0; j<=level+1; j++) 00119 fprintf(file, "|\t"); 00120 fprintf(file, "\n"); 00121 00122 /* Go to the right level and print the type. */ 00123 for (j=0; j<=level; j++) 00124 fprintf(file, "|\t"); 00125 fprintf(file, "Type: "); 00126 switch (dependence->type) { 00127 case OSL_UNDEFINED : fprintf(file, "UNSET\n"); break; 00128 case OSL_DEPENDENCE_RAW : fprintf(file, "RAW (flow)\n"); break; 00129 case OSL_DEPENDENCE_WAR : fprintf(file, "WAR (anti)\n"); break; 00130 case OSL_DEPENDENCE_WAW : fprintf(file, "WAW (output)\n"); break; 00131 case OSL_DEPENDENCE_RAR : fprintf(file, "RAR (input)\n"); break; 00132 case OSL_DEPENDENCE_RAW_SCALPRIV : 00133 fprintf(file, "RAW_SCALPRIV (scalar priv)\n"); break; 00134 default : fprintf(file, "unknown\n"); break; 00135 } 00136 00137 /* A blank line. */ 00138 for (j=0; j<=level+1; j++) 00139 fprintf(file, "|\t"); 00140 fprintf(file, "\n"); 00141 00142 /* Go to the right level and print the depth. */ 00143 for (j=0; j<=level; j++) 00144 fprintf(file, "|\t"); 00145 fprintf(file, "Depth: %d\n", dependence->depth); 00146 00147 /* A blank line. */ 00148 for (j=0; j<=level+1; j++) 00149 fprintf(file, "|\t"); 00150 fprintf(file, "\n"); 00151 00152 /* Ref source and target */ 00153 for (j=0; j<=level; j++) 00154 fprintf(file, "|\t"); 00155 fprintf(file, "Ref source: %d, Ref target: %d\n", 00156 dependence->ref_source, dependence->ref_target); 00157 00158 /* A blank line. */ 00159 for (j=0; j<=level+1; j++) 00160 fprintf(file, "|\t"); 00161 fprintf(file, "\n"); 00162 00163 /* Print the source statement. */ 00164 for (j=0; j<=level; j++) 00165 fprintf(file, "|\t"); 00166 fprintf(file, "Statement label: %d\n", dependence->label_source); 00167 tmp = dependence->stmt_source_ptr->next; 00168 dependence->stmt_source_ptr->next = NULL; 00169 osl_statement_idump(file, dependence->stmt_source_ptr, level+1); 00170 dependence->stmt_source_ptr->next = tmp; 00171 00172 /* Print the target statement. */ 00173 for (j=0; j<=level; j++) 00174 fprintf(file, "|\t"); 00175 fprintf(file, "Target label: %d\n", dependence->label_target); 00176 tmp = dependence->stmt_target_ptr->next; 00177 dependence->stmt_target_ptr->next = NULL; 00178 osl_statement_idump(file, dependence->stmt_target_ptr, level+1); 00179 dependence->stmt_target_ptr->next = tmp; 00180 00181 /* Print the dependence polyhedron. */ 00182 for (j=0; j<=level; j++) 00183 fprintf(file, "|\t"); 00184 fprintf(file, "%d %d %d %d %d %d %d %d\n", 00185 dependence->source_nb_output_dims_domain, 00186 dependence->source_nb_output_dims_access, 00187 dependence->target_nb_output_dims_domain, 00188 dependence->target_nb_output_dims_access, 00189 dependence->source_nb_local_dims_domain, 00190 dependence->source_nb_local_dims_access, 00191 dependence->target_nb_local_dims_domain, 00192 dependence->target_nb_local_dims_access); 00193 osl_relation_idump(file, dependence->domain, level+1); 00194 00195 dependence = dependence->next; 00196 00197 /* Next line. */ 00198 if (dependence != NULL) { 00199 for (j=0; j<=level; j++) 00200 fprintf(file, "|\t"); 00201 fprintf(file, "V\n"); 00202 } 00203 } 00204 00205 /* The last line. */ 00206 for (j=0; j<=level; j++) 00207 fprintf(file, "|\t"); 00208 fprintf(file, "\n"); 00209 } 00210 00211 00217 void osl_dependence_dump(FILE * file, osl_dependence_p dependence) { 00218 osl_dependence_idump(file, dependence, 0); 00219 } 00220 00221 00226 void osl_dependence_print(FILE *file, osl_dependence_p dependence) { 00227 char *string = osl_dependence_sprint(dependence); 00228 fprintf(file, "%s\n", string); 00229 free(string); 00230 } 00231 00232 00238 char* osl_dependence_sprint(osl_dependence_p dependence) { 00239 00240 osl_dependence_p tmp = dependence; 00241 int nb_deps; 00242 int buffer_size = 2048; 00243 char* buffer; 00244 char buff[2048]; 00245 char* type; 00246 char* pbuffer; 00247 00248 OSL_malloc(buffer, char*, buffer_size); 00249 buffer[0] = '\0'; 00250 00251 for (tmp = dependence, nb_deps = 0; tmp; tmp = tmp->next, ++nb_deps) 00252 ; 00253 snprintf(buff, OSL_MAX_STRING, "# Number of dependences\n%d\n", nb_deps); 00254 strcat(buffer, buff); 00255 00256 if (nb_deps) { 00257 for (tmp = dependence, nb_deps = 1; tmp; tmp = tmp->next, ++nb_deps) { 00258 00259 switch (tmp->type) { 00260 case OSL_UNDEFINED: 00261 type = "UNSET"; 00262 break; 00263 case OSL_DEPENDENCE_RAW: 00264 type = "RAW #(flow)"; 00265 break; 00266 case OSL_DEPENDENCE_WAR: 00267 type = "WAR #(anti)"; 00268 break; 00269 case OSL_DEPENDENCE_WAW: 00270 type = "WAW #(output)"; 00271 break; 00272 case OSL_DEPENDENCE_RAR: 00273 type = "RAR #(input)"; 00274 break; 00275 case OSL_DEPENDENCE_RAW_SCALPRIV: 00276 type = "RAW_SCALPRIV #(scalar priv)"; 00277 break; 00278 default: 00279 exit(1); 00280 break; 00281 } 00282 00283 /* Output dependence information. */ 00284 snprintf(buff, OSL_MAX_STRING, "# Description of dependence %d\n" 00285 "# type\n%s\n" 00286 "# From source statement id\n%d\n" 00287 "# To target statement id\n%d\n" 00288 "# Depth \n%d\n" 00289 "# From source access ref\n%d\n" 00290 "# To target access ref\n%d\n" 00291 "# Dependence domain\n", 00292 nb_deps, type, 00293 tmp->label_source, 00294 tmp->label_target, 00295 tmp->depth, 00296 tmp->ref_source, 00297 tmp->ref_target); 00298 00299 osl_util_safe_strcat(&buffer, buff, &buffer_size); 00300 00301 /* Output dependence domain. */ 00302 pbuffer = osl_relation_sprint(tmp->domain); 00303 osl_util_safe_strcat(&buffer, pbuffer, &buffer_size); 00304 free(pbuffer); 00305 } 00306 } 00307 00308 return buffer; 00309 } 00310 00311 00316 static 00317 osl_dependence_p osl_dependence_read_one_dep(char **input, int precision) { 00318 osl_dependence_p dep = osl_dependence_malloc(); 00319 char *buffer; 00320 00321 /* Dependence type */ 00322 buffer = osl_util_read_string(NULL, input); 00323 if (! strcmp(buffer, "RAW")) 00324 dep->type = OSL_DEPENDENCE_RAW; 00325 else if (! strcmp(buffer, "RAR")) 00326 dep->type = OSL_DEPENDENCE_RAR; 00327 else if (! strcmp(buffer, "WAR")) 00328 dep->type = OSL_DEPENDENCE_WAR; 00329 else if (! strcmp(buffer, "WAW")) 00330 dep->type = OSL_DEPENDENCE_WAW; 00331 else if (! strcmp(buffer, "RAW_SCALPRIV")) 00332 dep->type = OSL_DEPENDENCE_RAW_SCALPRIV; 00333 free(buffer); 00334 00335 /* # From source statement xxx */ 00336 dep->label_source = osl_util_read_int(NULL, input); 00337 00338 /* # To target statement xxx */ 00339 dep->label_target = osl_util_read_int(NULL, input); 00340 00341 /* # Depth */ 00342 dep->depth = osl_util_read_int(NULL, input); 00343 00344 /* # From source access ref */ 00345 dep->ref_source = osl_util_read_int(NULL, input); 00346 00347 /* # To target access ref */ 00348 dep->ref_target = osl_util_read_int(NULL, input); 00349 00350 /* Read the osl_relation */ 00351 dep->domain = osl_relation_psread(input, precision); 00352 00353 return dep; 00354 } 00355 00356 00361 osl_dependence_p osl_dependence_sread(char **input) { 00362 int precision = osl_util_get_precision(); 00363 return osl_dependence_psread(input, precision); 00364 } 00365 00366 00371 osl_dependence_p osl_dependence_psread(char **input, int precision) { 00372 osl_dependence_p first = NULL; 00373 osl_dependence_p currdep = NULL; 00374 00375 if (*input == NULL) { 00376 OSL_debug("no dependence optional tag"); 00377 return NULL; 00378 } 00379 00380 int i; 00381 /* Get the number of dependences. */ 00382 int nbdeps = osl_util_read_int(NULL, input); 00383 00384 /* For each of them, read 1 and shift of the read size. */ 00385 for (i = 0; i < nbdeps; i++) { 00386 osl_dependence_p adep = osl_dependence_read_one_dep(input, precision); 00387 if (first == NULL) { 00388 currdep = first = adep; 00389 } else { 00390 currdep->next = adep; 00391 currdep = currdep->next; 00392 } 00393 } 00394 00395 return first; 00396 } 00397 00398 00399 /****************************************************************************** 00400 * Memory deallocation function * 00401 ******************************************************************************/ 00402 00403 00411 osl_dependence_p osl_dependence_malloc() { 00412 osl_dependence_p dependence; 00413 00414 /* Memory allocation for the osl_dependence_p structure. */ 00415 OSL_malloc(dependence, osl_dependence_p, sizeof(osl_dependence_t)); 00416 00417 /* We set the various fields with default values. */ 00418 dependence->depth = OSL_UNDEFINED; 00419 dependence->type = OSL_UNDEFINED; 00420 dependence->label_source = OSL_UNDEFINED; 00421 dependence->label_target = OSL_UNDEFINED; 00422 dependence->ref_source = OSL_UNDEFINED; 00423 dependence->ref_target = OSL_UNDEFINED; 00424 dependence->domain = NULL; 00425 dependence->next = NULL; 00426 dependence->usr = NULL; 00427 dependence->source_nb_output_dims_domain = OSL_UNDEFINED; 00428 dependence->source_nb_output_dims_access = OSL_UNDEFINED; 00429 dependence->target_nb_output_dims_domain = OSL_UNDEFINED; 00430 dependence->target_nb_output_dims_access = OSL_UNDEFINED; 00431 dependence->source_nb_local_dims_domain = OSL_UNDEFINED; 00432 dependence->source_nb_local_dims_access = OSL_UNDEFINED; 00433 dependence->target_nb_local_dims_domain = OSL_UNDEFINED; 00434 dependence->target_nb_local_dims_access = OSL_UNDEFINED; 00435 dependence->ref_source_access_ptr = NULL; 00436 dependence->ref_target_access_ptr = NULL; 00437 dependence->stmt_source_ptr = NULL; 00438 dependence->stmt_target_ptr = NULL; 00439 00440 return dependence; 00441 } 00442 00443 00449 void osl_dependence_free(osl_dependence_p dependence) { 00450 osl_dependence_p next; 00451 while (dependence != NULL) { 00452 next = dependence->next; 00453 osl_relation_free(dependence->domain); 00454 free(dependence); 00455 dependence = next; 00456 } 00457 } 00458 00459 00460 /****************************************************************************** 00461 * Processing functions * 00462 ******************************************************************************/ 00463 00464 00473 osl_dependence_p osl_dependence_nclone(osl_dependence_p dep, int n) { 00474 int first = 1, i = 0; 00475 osl_dependence_p clone = NULL, node, previous = NULL; 00476 00477 while ((dep != NULL) && ((n == -1) || (i < n))) { 00478 node = osl_dependence_malloc(); 00479 node->stmt_source_ptr = dep->stmt_source_ptr; 00480 node->stmt_target_ptr = dep->stmt_target_ptr; 00481 node->depth = dep->depth; 00482 node->type = dep->type; 00483 node->label_source = dep->label_source; 00484 node->label_target = dep->label_target; 00485 node->ref_source = dep->ref_source; 00486 node->ref_target = dep->ref_target; 00487 node->domain = osl_relation_clone(dep->domain); 00488 node->source_nb_output_dims_domain = dep->source_nb_output_dims_domain; 00489 node->source_nb_output_dims_access = dep->source_nb_output_dims_access; 00490 node->target_nb_output_dims_domain = dep->target_nb_output_dims_domain; 00491 node->target_nb_output_dims_access = dep->target_nb_output_dims_access; 00492 node->source_nb_local_dims_domain = dep->source_nb_local_dims_domain; 00493 node->source_nb_local_dims_access = dep->source_nb_local_dims_access; 00494 node->target_nb_local_dims_domain = dep->target_nb_local_dims_domain; 00495 node->target_nb_local_dims_access = dep->target_nb_local_dims_access; 00496 node->next = NULL; 00497 node->usr = NULL; 00498 00499 if (first) { 00500 first = 0; 00501 clone = node; 00502 previous = node; 00503 } 00504 else { 00505 previous->next = node; 00506 previous = previous->next; 00507 } 00508 00509 i++; 00510 dep = dep->next; 00511 } 00512 00513 return clone; 00514 } 00515 00516 00524 osl_dependence_p osl_dependence_clone(osl_dependence_p dep) { 00525 return osl_dependence_nclone(dep, -1); 00526 } 00527 00528 00538 int osl_dependence_equal(osl_dependence_p d1, osl_dependence_p d2) { 00539 00540 if (d1 == d2) 00541 return 1; 00542 00543 if ((d1->next != NULL && d2->next == NULL) || 00544 (d1->next == NULL && d2->next != NULL)) 00545 return 0; 00546 00547 if (d1->next != NULL && d2->next != NULL) 00548 if (!osl_dependence_equal(d1->next, d2->next)) 00549 return 0; 00550 00551 if (!osl_relation_equal(d1->domain, d2->domain)) 00552 return 0; 00553 00554 if (d1->label_source != d2->label_source || 00555 d1->label_target != d2->label_target || 00556 d1->ref_source != d2->ref_source || 00557 d1->ref_target != d2->ref_target || 00558 d1->depth != d2->depth || 00559 d1->type != d2->type || 00560 00561 d1->source_nb_output_dims_domain != 00562 d2->source_nb_output_dims_domain || 00563 00564 d1->source_nb_output_dims_access != 00565 d2->source_nb_output_dims_access || 00566 00567 d1->target_nb_output_dims_domain != 00568 d2->target_nb_output_dims_domain || 00569 00570 d1->target_nb_output_dims_access != 00571 d2->target_nb_output_dims_access || 00572 00573 d1->source_nb_local_dims_domain != 00574 d2->source_nb_local_dims_domain || 00575 00576 d1->source_nb_local_dims_access != 00577 d2->source_nb_local_dims_access || 00578 00579 d1->target_nb_local_dims_domain != 00580 d2->target_nb_local_dims_domain || 00581 00582 d1->target_nb_local_dims_access != 00583 d2->target_nb_local_dims_access) 00584 return 0; 00585 00586 return 1; 00587 } 00588 00589 00599 void osl_dependence_add(osl_dependence_p* start, 00600 osl_dependence_p* now, 00601 osl_dependence_p dependence) { 00602 if (dependence != NULL) { 00603 if (*start == NULL) { 00604 *start = dependence; 00605 *now = *start; 00606 } else { 00607 (*now)->next = dependence; 00608 *now = (*now)->next; 00609 } 00610 00611 while ((*now)->next != NULL) 00612 *now = (*now)->next; 00613 } 00614 } 00615 00616 00624 int osl_nb_dependences(osl_dependence_p deps) { 00625 osl_dependence_p dep = deps; 00626 int num = 0; 00627 while (dep != NULL) { 00628 num++; 00629 dep = dep->next; 00630 } 00631 return num; 00632 } 00633 00634 00641 osl_interface_p osl_dependence_interface() { 00642 osl_interface_p interface = osl_interface_malloc(); 00643 00644 OSL_strdup(interface->URI, OSL_URI_DEPENDENCE); 00645 interface->idump = (osl_idump_f)osl_dependence_idump; 00646 interface->sprint = (osl_sprint_f)osl_dependence_sprint; 00647 interface->sread = (osl_sread_f)osl_dependence_sread; 00648 interface->malloc = (osl_malloc_f)osl_dependence_malloc; 00649 interface->free = (osl_free_f)osl_dependence_free; 00650 interface->clone = (osl_clone_f)osl_dependence_clone; 00651 interface->equal = (osl_equal_f)osl_dependence_equal; 00652 00653 return interface; 00654 }
1.8.0