Clan
0.8.0
|
00001 00002 /*+------- <| --------------------------------------------------------** 00003 ** A Clan ** 00004 **--- /.\ -----------------------------------------------------** 00005 ** <| [""M# scop.c ** 00006 **- A | # -----------------------------------------------------** 00007 ** /.\ [""M# First version: 30/04/2008 ** 00008 **- [""M# | # U"U#U -----------------------------------------------** 00009 | # | # \ .:/ 00010 | # | #___| # 00011 ****** | "--' .-" ****************************************************** 00012 * |"-"-"-"-"-#-#-## Clan : the Chunky Loop Analyzer (experimental) * 00013 **** | # ## ###### ***************************************************** 00014 * \ .::::'/ * 00015 * \ ::::'/ Copyright (C) 2008 University Paris-Sud 11 * 00016 * :8a| # # ## * 00017 * ::88a ### This is free software; you can redistribute it * 00018 * ::::888a 8a ##::. and/or modify it under the terms of the GNU Lesser * 00019 * ::::::::888a88a[]::: General Public License as published by the Free * 00020 *::8:::::::::SUNDOGa8a::. Software Foundation, either version 2.1 of the * 00021 *::::::::8::::888:Y8888:: License, or (at your option) any later version. * 00022 *::::':::88::::888::Y88a::::::::::::... * 00023 *::'::.. . ..... .. ... . * 00024 * This software is distributed in the hope that it will be useful, but * 00025 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY * 00026 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * 00027 * for more details. * 00028 * * 00029 * You should have received a copy of the GNU Lesser General Public License * 00030 * along with software; if not, write to the Free Software Foundation, Inc., * 00031 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * 00032 * * 00033 * Clan, the Chunky Loop Analyzer * 00034 * Written by Cedric Bastoul, Cedric.Bastoul@u-psud.fr * 00035 * * 00036 ******************************************************************************/ 00037 00038 00039 #include <stdlib.h> 00040 #include <stdio.h> 00041 #include <ctype.h> 00042 #include <string.h> 00043 00044 #include <osl/vector.h> 00045 #include <osl/relation.h> 00046 #include <osl/relation_list.h> 00047 #include <osl/statement.h> 00048 #include <osl/strings.h> 00049 #include <osl/extensions/scatnames.h> 00050 #include <osl/extensions/arrays.h> 00051 #include <osl/extensions/coordinates.h> 00052 #include <osl/extensions/clay.h> 00053 #include <osl/extensions/extbody.h> 00054 #include <osl/generic.h> 00055 #include <osl/body.h> 00056 #include <osl/scop.h> 00057 #include <parser.h> 00058 #include <clan/macros.h> 00059 #include <clan/options.h> 00060 #include <clan/relation.h> 00061 #include <clan/statement.h> 00062 #include <clan/scop.h> 00063 00064 00065 extern int scanner_scop_start; 00066 extern int scanner_scop_end; 00067 extern int parser_indent; 00068 00069 00070 /*+**************************************************************************** 00071 * Processing functions * 00072 ******************************************************************************/ 00073 00074 osl_scop_p clan_parse(FILE*, clan_options_p); 00075 00084 osl_scop_p clan_scop_extract(FILE* input, clan_options_p options) { 00085 return clan_parse(input, options); 00086 } 00087 00088 00096 void clan_scop_compact(osl_scop_p scop) { 00097 clan_statement_compact(scop->statement, osl_scop_get_nb_parameters(scop)); 00098 } 00099 00100 00109 void clan_scop_print(FILE* file, osl_scop_p scop, clan_options_p options) { 00110 00111 if ((scop != NULL) && (options->castle)) { 00112 fprintf(file, "# \n"); 00113 fprintf(file, "# <| \n"); 00114 fprintf(file, "# A \n"); 00115 fprintf(file, "# /.\\ \n"); 00116 fprintf(file, "# <| [\"\"M# \n"); 00117 fprintf(file, "# A | # Clan McCloog Castle \n"); 00118 fprintf(file, "# /.\\ [\"\"M# [Generated by Clan "); 00119 fprintf(file, "%s]\n", CLAN_VERSION); 00120 fprintf(file, "# [\"\"M# | # U\"U#U \n"); 00121 fprintf(file, "# | # | # \\ .:/ \n"); 00122 fprintf(file, "# | # | #___| # \n"); 00123 fprintf(file, "# | \"--' .-\" \n"); 00124 fprintf(file, "# |\"-\"-\"-\"-\"-#-#-## \n"); 00125 fprintf(file, "# | # ## ###### \n"); 00126 fprintf(file, "# \\ .::::'/ \n"); 00127 fprintf(file, "# \\ ::::'/ \n"); 00128 fprintf(file, "# :8a| # # ## \n"); 00129 fprintf(file, "# ::88a ### \n"); 00130 fprintf(file, "# ::::888a 8a ##::. \n"); 00131 fprintf(file, "# ::::::888a88a[]:::: \n"); 00132 fprintf(file, "# :::::::::SUNDOGa8a::::. .. \n"); 00133 fprintf(file, "# :::::8::::888:Y8888:::::::::... \n"); 00134 fprintf(file, "#::':::88::::888::Y88a______________________________"); 00135 fprintf(file, "________________________\n"); 00136 fprintf(file, "#:: ::::88a::::88a:Y88a "); 00137 fprintf(file, " __---__-- __\n"); 00138 fprintf(file, "#' .: ::Y88a:::::8a:Y88a "); 00139 fprintf(file, "__----_-- -------_-__\n"); 00140 fprintf(file, "# :' ::::8P::::::::::88aa. _ _- -"); 00141 fprintf(file, "- --_ --- __ --- __--\n"); 00142 fprintf(file, "#.:: :::::::::::::::::::Y88as88a...s88aa.\n#\n"); 00143 } 00144 00145 if (options->outscoplib) 00146 osl_scop_print_scoplib(file, scop); 00147 else 00148 osl_scop_print(file, scop); 00149 } 00150 00151 00161 void clan_scop_generate_scatnames(osl_scop_p scop) { 00162 osl_statement_p current, deepest; 00163 osl_scatnames_p scatnames; 00164 osl_strings_p iterators = NULL; 00165 osl_strings_p names; 00166 osl_generic_p extension; 00167 osl_body_p body = NULL; 00168 char ** string; 00169 char buffer[CLAN_MAX_STRING]; 00170 int max_depth = -1; 00171 int i; 00172 00173 // Find the deepest statement to reuse its original iterators. 00174 current = scop->statement; 00175 while (current != NULL) { 00176 if (current->domain->nb_output_dims > max_depth) { 00177 max_depth = current->domain->nb_output_dims; 00178 deepest = current; 00179 body = (osl_body_p)osl_generic_lookup(deepest->extension, OSL_URI_BODY); 00180 if (body) 00181 iterators = body->iterators; 00182 } 00183 current = current->next; 00184 } 00185 00186 // It there are no scattering dimension, do nothing. 00187 if (max_depth <= 0) 00188 return; 00189 00190 // Create the NULL-terminated list of scattering dimension names. 00191 CLAN_malloc(string, char**, (2*max_depth + 2) * sizeof(char *)); 00192 string[2*max_depth + 1] = NULL; 00193 for (i = 0; i < max_depth; i++) { 00194 sprintf(buffer, "b%d", i); 00195 CLAN_strdup(string[2*i], buffer); 00196 CLAN_strdup(string[2*i+1], iterators->string[i]); 00197 } 00198 sprintf(buffer, "b%d", max_depth); 00199 CLAN_strdup(string[2*max_depth], buffer); 00200 00201 // Build the scatnames extension. 00202 names = osl_strings_malloc(); 00203 names->string = string; 00204 scatnames = osl_scatnames_malloc(); 00205 scatnames->names = names; 00206 00207 // Build the generic extension and insert it to the extension list. 00208 extension = osl_generic_malloc(); 00209 extension->interface = osl_scatnames_interface(); 00210 extension->data = scatnames; 00211 osl_generic_add(&scop->extension, extension); 00212 } 00213 00214 00222 void clan_scop_generate_coordinates(osl_scop_p scop, char* name) { 00223 osl_coordinates_p coordinates; 00224 osl_generic_p extension; 00225 00226 // Build the coordinates extension 00227 coordinates = osl_coordinates_malloc(); 00228 CLAN_strdup(coordinates->name, name); 00229 coordinates->line_start = scanner_scop_start + 1; 00230 coordinates->line_end = scanner_scop_end; 00231 coordinates->column_start = 0; 00232 coordinates->column_end = 0; 00233 coordinates->indent = (parser_indent != CLAN_UNDEFINED) ? parser_indent : 0; 00234 00235 // Build the generic extension and insert it to the extension list. 00236 extension = osl_generic_malloc(); 00237 extension->interface = osl_coordinates_interface(); 00238 extension->data = coordinates; 00239 osl_generic_add(&scop->extension, extension); 00240 } 00241 00242 00250 void clan_scop_generate_clay(osl_scop_p scop, char* script) { 00251 osl_clay_p clay; 00252 osl_generic_p extension; 00253 00254 if ((script != NULL) && (strlen(script) > 0)) { 00255 // Build the clay extension 00256 clay = osl_clay_malloc(); 00257 CLAN_strdup(clay->script, script); 00258 00259 // Build the generic extension and insert it to the extension list. 00260 extension = osl_generic_malloc(); 00261 extension->interface = osl_clay_interface(); 00262 extension->data = clay; 00263 osl_generic_add(&scop->extension, extension); 00264 } 00265 } 00266 00267 00280 void clan_scop_update_coordinates(osl_scop_p scop, 00281 int coordinates[5][CLAN_MAX_SCOPS]) { 00282 int i = 0; 00283 osl_coordinates_p old; 00284 00285 while (scop != NULL) { 00286 if (i > CLAN_MAX_SCOPS) 00287 CLAN_error("too many SCoPs! Change CLAN_MAX_SCOPS and recompile Clan."); 00288 00289 old = osl_generic_lookup(scop->extension, OSL_URI_COORDINATES); 00290 if (old == NULL) 00291 CLAN_error("coordinates extension not present"); 00292 // When columns are at 0, it means the scop has not been autodetected. 00293 // - The line starts at +1 (after the pragma scop) if no autodetection, 00294 // - The column stops at -1 (previous read char) if autodetection. 00295 old->line_start = coordinates[0][i] + ((coordinates[2][i] == 0)? 1 : 0); 00296 old->line_end = coordinates[1][i]; 00297 old->column_start = coordinates[2][i]; 00298 old->column_end = coordinates[3][i] - ((coordinates[3][i] > 0)? 1 : 0); 00299 i++; 00300 scop = scop->next; 00301 } 00302 } 00303 00304 00317 void clan_scop_print_autopragma(FILE* input, int nb_scops, 00318 int coordinates[5][CLAN_MAX_SCOPS]) { 00319 int i, j, line, column; 00320 char c; 00321 FILE* autopragma; 00322 00323 if (CLAN_DEBUG) { 00324 CLAN_debug("coordinates:"); 00325 for (i = 0; i < 5; i++) { 00326 for (j = 0; j < nb_scops; j++) 00327 printf("%3d ", coordinates[i][j]); 00328 printf("\n"); 00329 } 00330 } 00331 00332 if ((autopragma = fopen(CLAN_AUTOPRAGMA_FILE, "w")) == NULL) 00333 CLAN_error("cannot create the autopragma file"); 00334 line = 1; 00335 column = 1; 00336 i = 0; 00337 while ((c = fgetc(input)) != EOF) { 00338 if (nb_scops > 0) { 00339 if ((line == coordinates[0][i]) && (column == coordinates[2][i])) { 00340 fprintf(autopragma, "\n#pragma scop\n"); 00341 for (j = 0; j < coordinates[2][i] - 1; j++) 00342 fprintf(autopragma, " "); 00343 } 00344 if ((line == coordinates[1][i]) && (column == coordinates[3][i])) { 00345 fprintf(autopragma, "\n#pragma endscop\n"); 00346 for (j = 0; j < coordinates[3][i] - 1; j++) 00347 fprintf(autopragma, " "); 00348 if (i < nb_scops - 1) { 00349 do 00350 i++; 00351 while ((i < nb_scops - 1) && !coordinates[4][i]); 00352 } 00353 } 00354 } 00355 fputc(c, autopragma); 00356 column++; 00357 if (c == '\n') { 00358 line++; 00359 column = 1; 00360 } 00361 } 00362 fclose(autopragma); 00363 } 00364 00365 00375 static 00376 int clan_scop_no_pragma(char * filename, int line_start) { 00377 int lines = 0; 00378 int read = 1; 00379 char c; 00380 FILE* file; 00381 char s1[CLAN_MAX_STRING]; 00382 char s2[CLAN_MAX_STRING]; 00383 00384 if (line_start < 0) 00385 CLAN_error("negative line number"); 00386 00387 if (!(file = fopen(filename, "r"))) 00388 CLAN_error("unable to read the file"); 00389 00390 // Go to line_start in the file. 00391 while ((lines < line_start - 1) && (read != EOF)) { 00392 read = fscanf(file, "%c", &c); 00393 if (read != EOF) { 00394 if (c == '\n') 00395 lines ++; 00396 } 00397 } 00398 00399 if (lines != line_start - 1) { 00400 fclose(file); 00401 CLAN_error("not enough lines in the file"); 00402 } 00403 00404 if (fscanf(file, " %s %s", s1, s2) != 2) { 00405 fclose(file); 00406 CLAN_debug("pragma not found: cannot read the two chains"); 00407 return CLAN_TRUE; 00408 } 00409 00410 fclose(file); 00411 if (strcmp(s1, "#pragma") || strcmp(s2, "scop")) { 00412 CLAN_debug("pragma not found: do not match \"#pragma scop\""); 00413 return CLAN_TRUE; 00414 } 00415 00416 CLAN_debug("pragma found"); 00417 return CLAN_FALSE; 00418 } 00419 00420 00431 void clan_scop_insert_pragmas(osl_scop_p scop, char* filename, int test) { 00432 int i, j, n = 0; 00433 int infos[5][CLAN_MAX_SCOPS]; 00434 int tmp[5]; 00435 osl_coordinates_p coordinates; 00436 FILE* input, *output; 00437 size_t size; 00438 char buffer[BUFSIZ]; 00439 00440 // Get coordinate information from the list of SCoPS. 00441 while (scop != NULL) { 00442 coordinates = osl_generic_lookup(scop->extension, OSL_URI_COORDINATES); 00443 infos[0][n] = coordinates->line_start; 00444 infos[1][n] = coordinates->line_end; 00445 infos[2][n] = coordinates->column_start; 00446 infos[3][n] = coordinates->column_end + 1; 00447 infos[4][n] = clan_scop_no_pragma(filename, coordinates->line_start); 00448 n++; 00449 scop = scop->next; 00450 } 00451 00452 // Dirty and inefficient bubble sort to ensure the SCoP ordering is correct 00453 // (this is ensured in Clan, but not if it is called from outside...). 00454 for (i = n - 2; i >= 0; i--) { 00455 for (j = 0; j <= i; j++) { 00456 if (infos[0][j] > infos[0][j+1]) { 00457 tmp[0]=infos[0][j]; infos[0][j]=infos[0][j+1]; infos[0][j+1]=tmp[0]; 00458 tmp[1]=infos[1][j]; infos[1][j]=infos[1][j+1]; infos[1][j+1]=tmp[1]; 00459 tmp[2]=infos[2][j]; infos[2][j]=infos[2][j+1]; infos[2][j+1]=tmp[2]; 00460 tmp[3]=infos[3][j]; infos[3][j]=infos[3][j+1]; infos[3][j+1]=tmp[3]; 00461 tmp[4]=infos[4][j]; infos[4][j]=infos[4][j+1]; infos[4][j+1]=tmp[4]; 00462 } 00463 } 00464 } 00465 00466 // Quick check that there is no scop interleaving. 00467 for (i = 0; i < n - 1; i++) 00468 if (infos[1][i] > infos[0][i+1]) 00469 CLAN_error("SCoP interleaving"); 00470 00471 // Generate the temporary file with the pragma inserted. 00472 if (!(input = fopen(filename, "r"))) 00473 CLAN_error("unable to read the input file"); 00474 clan_scop_print_autopragma(input, n, infos); 00475 fclose(input); 00476 00477 // Replace the original file, or keep the temporary file. 00478 if (!test) { 00479 if (!(input = fopen(CLAN_AUTOPRAGMA_FILE, "rb"))) 00480 CLAN_error("unable to read the temporary file"); 00481 00482 if (!(output = fopen(filename, "wb"))) 00483 CLAN_error("unable to write the output file"); 00484 00485 while ((size = fread(buffer, 1, BUFSIZ, input))) { 00486 fwrite(buffer, 1, size, output); 00487 } 00488 00489 fclose(input); 00490 fclose(output); 00491 } 00492 } 00493 00494 00500 void clan_scop_simplify(osl_scop_p scop) { 00501 osl_statement_p statement; 00502 00503 while (scop != NULL) { 00504 statement = scop->statement; 00505 while (statement != NULL) { 00506 clan_relation_simplify(statement->domain); 00507 statement = statement->next; 00508 } 00509 scop = scop->next; 00510 } 00511 }