Clan  0.8.0
scop.c
Go to the documentation of this file.
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 }