Remove matrix representation support
[openscop.git] / source / scop.c
blob05d6c9a402c57cf817f4bb8a32f3db1855ca31a1
2 /*+-----------------------------------------------------------------**
3 ** OpenScop Library **
4 **-----------------------------------------------------------------**
5 ** scop.c **
6 **-----------------------------------------------------------------**
7 ** First version: 30/04/2008 **
8 **-----------------------------------------------------------------**
11 *****************************************************************************
12 * OpenScop: Structures and formats for polyhedral tools to talk together *
13 *****************************************************************************
14 * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, *
15 * / / / // // // // / / / // // / / // / /|,_, *
16 * / / / // // // // / / / // // / / // / / / /\ *
17 * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ *
18 * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ *
19 * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ *
20 * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ *
21 * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ *
22 * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ *
23 * | I | | | | e | | | | | | | | | | | | | \ \ \ *
24 * | T | | | | | | | | | | | | | | | | | \ \ \ *
25 * | E | | | | | | | | | | | | | | | | | \ \ \ *
26 * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ *
27 * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / *
28 * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' *
29 * *
30 * Copyright (C) 2008 University Paris-Sud 11 and INRIA *
31 * *
32 * (3-clause BSD license) *
33 * Redistribution and use in source and binary forms, with or without *
34 * modification, are permitted provided that the following conditions *
35 * are met: *
36 * *
37 * 1. Redistributions of source code must retain the above copyright notice, *
38 * this list of conditions and the following disclaimer. *
39 * 2. Redistributions in binary form must reproduce the above copyright *
40 * notice, this list of conditions and the following disclaimer in the *
41 * documentation and/or other materials provided with the distribution. *
42 * 3. The name of the author may not be used to endorse or promote products *
43 * derived from this software without specific prior written permission. *
44 * *
45 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR *
46 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES *
47 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. *
48 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, *
49 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT *
50 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
51 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY *
52 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT *
53 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF *
54 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
55 * *
56 * OpenScop Library, a library to manipulate OpenScop formats and data *
57 * structures. Written by: *
58 * Cedric Bastoul <Cedric.Bastoul@u-psud.fr> and *
59 * Louis-Noel Pouchet <Louis-Noel.pouchet@inria.fr> *
60 * *
61 *****************************************************************************/
63 # include <stdlib.h>
64 # include <stdio.h>
65 # include <ctype.h>
66 # include <string.h>
67 # include <openscop/scop.h>
70 /*+***************************************************************************
71 * Structure display functions *
72 *****************************************************************************/
75 /**
76 * openscop_scop_idump function:
77 * this function displays an openscop_scop_t structure (*scop) into a
78 * file (file, possibly stdout) in a way that trends to be understandable. It
79 * includes an indentation level (level) in order to work with others
80 * print_structure functions.
81 * \param file The file where the information has to be printed.
82 * \param scop The scop structure whose information has to be printed.
83 * \param level Number of spaces before printing, for each line.
85 void openscop_scop_idump(FILE * file, openscop_scop_p scop, int level) {
86 int j;
88 // Go to the right level.
89 for (j = 0; j < level; j++)
90 fprintf(file, "|\t");
92 if (scop != NULL) {
93 fprintf(file, "+-- openscop_scop_t\n");
95 // A blank line.
96 for (j = 0; j <= level+1; j++)
97 fprintf(file, "|\t");
98 fprintf(file, "\n");
100 // Print the language.
101 for (j = 0; j < level; j++)
102 fprintf(file, "|\t");
103 fprintf(file, "|\tLanguage: %s\n", scop->language);
105 // A blank line.
106 for (j = 0; j <= level+1; j++)
107 fprintf(file, "|\t");
108 fprintf(file, "\n");
110 // Print the context of the scop.
111 openscop_relation_idump(file, scop->context, level+1);
113 // Print the names.
114 openscop_names_idump(file, scop->names, level+1);
116 // Print the statements.
117 openscop_statement_idump(file, scop->statement, level+1);
119 // Print the extensions.
120 openscop_extension_idump(file, scop->extension, level+1);
122 // A blank line.
123 for (j = 0; j <= level+1; j++)
124 fprintf(file, "|\t");
125 fprintf(file, "\n");
127 else {
128 fprintf(file, "+-- NULL scop\n");
131 // The last line.
132 for (j = 0; j <= level; j++)
133 fprintf(file, "|\t");
134 fprintf(file, "\n");
139 * openscop_scop_dump function:
140 * this function prints the content of an openscop_scop_t structure (*scop)
141 * into a file (file, possibly stdout).
142 * \param file The file where the information has to be printed.
143 * \param scop The scop structure whose information has to be printed.
145 void openscop_scop_dump(FILE * file, openscop_scop_p scop) {
146 openscop_scop_idump(file, scop, 0);
151 * openscop_scop_name_limits function:
152 * this function finds the (maximum) number of various elements of a scop and
153 * return the values through parameters. To ensure the correctness of the
154 * results, an integrity check of the input scop should be run before calling
155 * this function.
156 * \param scop The scop to analyse.
157 * \parem nb_parameters The number of parameters in the scop (output).
158 * \parem nb_iterators The number of iterators in the scop (output).
159 * \parem nb_scattdims The number of scattdims in the scop (output).
160 * \parem nb_localdims The number of local dimensions in the scop (output).
161 * \parem nb_arrays The number of arrays in the scop (output).
163 static
164 void openscop_scop_name_limits(openscop_scop_p scop,
165 int * nb_parameters,
166 int * nb_iterators,
167 int * nb_scattdims,
168 int * nb_localdims,
169 int * nb_arrays) {
170 int array_id;
171 openscop_statement_p statement;
172 openscop_relation_list_p list;
174 // * The number of parameters is collected from the context,
175 // * The numbers of local dimensions are collected from all relations
176 // in the corresponding field.
177 *nb_parameters = 0;
178 *nb_localdims = 0;
179 if (scop->context != NULL) {
180 *nb_parameters = scop->context->nb_parameters;
181 *nb_localdims = scop->context->nb_local_dims;
184 *nb_iterators = 0;
185 *nb_scattdims = 0;
186 *nb_arrays = 0;
187 statement = scop->statement;
188 while (statement != NULL) {
189 // * The number of iterators are defined by iteration domains,
190 // it corresponds to the #output_dims.
191 if (statement->domain != NULL) {
192 if (statement->domain->nb_output_dims > *nb_iterators)
193 *nb_iterators = statement->domain->nb_output_dims;
195 if (statement->domain->nb_local_dims > *nb_localdims)
196 *nb_localdims = statement->domain->nb_local_dims;
199 // * The number of scattdims are defined by scattering,
200 // it corresponds to the #output_dims.
201 if (statement->scattering != NULL) {
202 if (statement->scattering->nb_output_dims > *nb_scattdims)
203 *nb_scattdims = statement->scattering->nb_output_dims;
205 if (statement->scattering->nb_local_dims > *nb_localdims)
206 *nb_localdims = statement->scattering->nb_local_dims;
209 // * The number of arrays are defined by accesses,
210 list = statement->access;
211 while (list != NULL) {
212 array_id = openscop_relation_get_array_id(list->elt);
213 if (array_id > *nb_arrays)
214 *nb_arrays = array_id;
216 list = list->next;
219 statement = statement->next;
225 * openscop_scop_full_names function:
226 * this function generates an openscop_names_p structure which contains
227 * enough names for the scop provided as parameter, for each kind of names.
228 * If the names contained in the input scop are not sufficient, this function
229 * generated the missing names.
230 * \param scop The scop we need a name for each element.
231 * \return A set of names for the scop.
233 static
234 openscop_names_p openscop_scop_full_names(openscop_scop_p scop) {
235 int nb_parameters;
236 int nb_iterators;
237 int nb_scattdims;
238 int nb_localdims;
239 int nb_arrays;
240 openscop_arrays_p arrays;
241 openscop_names_p names;
243 names = openscop_names_copy(scop->names);
245 // Extract array names information from extensions.
246 openscop_util_strings_free(names->arrays, names->nb_arrays);
247 arrays = (openscop_arrays_p)openscop_extension_lookup(scop->extension,
248 OPENSCOP_EXTENSION_ARRAYS);
249 names->arrays = openscop_arrays_generate_names(arrays,
250 &(names->nb_arrays));
252 // Complete names if necessary.
253 openscop_scop_name_limits(scop, &nb_parameters,
254 &nb_iterators,
255 &nb_scattdims,
256 &nb_localdims,
257 &nb_arrays);
259 openscop_util_strings_complete(&names->parameters, &names->nb_parameters,
260 "P_", nb_parameters);
262 openscop_util_strings_complete(&names->iterators, &names->nb_iterators,
263 "i_", nb_iterators);
265 openscop_util_strings_complete(&names->scattdims, &names->nb_scattdims,
266 "s_", nb_scattdims);
268 openscop_util_strings_complete(&names->localdims, &names->nb_localdims,
269 "l_", nb_localdims);
271 openscop_util_strings_complete(&names->arrays, &names->nb_arrays,
272 "A_", nb_arrays);
274 return names;
279 * openscop_scop_print function:
280 * this function prints the content of an openscop_scop_t structure (*scop)
281 * into a file (file, possibly stdout) in the OpenScop textual format.
282 * \param file The file where the information has to be printed.
283 * \param scop The scop structure whose information has to be printed.
285 void openscop_scop_print(FILE * file, openscop_scop_p scop) {
286 openscop_names_p names;
287 int tmp_nb_iterators = 0;
288 char ** tmp_iterators = NULL;
290 if (openscop_scop_integrity_check(scop) == 0) {
291 fprintf(stderr, "[OpenScop] Warning: OpenScop integrity check failed. "
292 " Something may go wrong.\n");
295 // Build a name structure for pretty printing of relations.
296 names = openscop_scop_full_names(scop);
298 if (0) {
299 fprintf(file, "# \n");
300 fprintf(file, "# <| \n");
301 fprintf(file, "# A \n");
302 fprintf(file, "# /.\\ \n");
303 fprintf(file, "# <| [\"\"M# \n");
304 fprintf(file, "# A | # Clan McCloog Castle \n");
305 fprintf(file, "# /.\\ [\"\"M# [Generated by the OpenScop ");
306 fprintf(file, "Library %s %s bits]\n",OPENSCOP_RELEASE, OPENSCOP_VERSION);
307 fprintf(file, "# [\"\"M# | # U\"U#U \n");
308 fprintf(file, "# | # | # \\ .:/ \n");
309 fprintf(file, "# | # | #___| # \n");
310 fprintf(file, "# | \"--' .-\" \n");
311 fprintf(file, "# |\"-\"-\"-\"-\"-#-#-## \n");
312 fprintf(file, "# | # ## ###### \n");
313 fprintf(file, "# \\ .::::'/ \n");
314 fprintf(file, "# \\ ::::'/ \n");
315 fprintf(file, "# :8a| # # ## \n");
316 fprintf(file, "# ::88a ### \n");
317 fprintf(file, "# ::::888a 8a ##::. \n");
318 fprintf(file, "# ::::::888a88a[]:::: \n");
319 fprintf(file, "# :::::::::SUNDOGa8a::::. .. \n");
320 fprintf(file, "# :::::8::::888:Y8888:::::::::... \n");
321 fprintf(file, "#::':::88::::888::Y88a______________________________");
322 fprintf(file, "________________________\n");
323 fprintf(file, "#:: ::::88a::::88a:Y88a ");
324 fprintf(file, " __---__-- __\n");
325 fprintf(file, "#' .: ::Y88a:::::8a:Y88a ");
326 fprintf(file, "__----_-- -------_-__\n");
327 fprintf(file, "# :' ::::8P::::::::::88aa. _ _- -");
328 fprintf(file, "- --_ --- __ --- __--\n");
329 fprintf(file, "#.:: :::::::::::::::::::Y88as88a...s88aa.\n");
331 else {
332 fprintf(file, "# [File generated by the OpenScop Library %s %s bits]\n",
333 OPENSCOP_RELEASE,OPENSCOP_VERSION);
336 fprintf(file, "\nOpenScop\n\n");
337 fprintf(file, "# =============================================== Global\n");
338 fprintf(file, "# Language\n");
339 fprintf(file, "%s\n\n", scop->language);
341 fprintf(file, "# Context\n");
342 // Remove the iterators from the names structure to print comments, as
343 // this information is used to know the number of iterators.
344 // TODO: do this in openscop_relation_print_openscop
345 tmp_nb_iterators = names->nb_iterators;
346 tmp_iterators = names->iterators;
347 names->nb_iterators = 0;
348 names->iterators = NULL;
349 openscop_relation_print(file, scop->context, names);
350 names->nb_iterators = tmp_nb_iterators;
351 names->iterators = tmp_iterators;
352 fprintf(file, "\n");
354 openscop_names_print(file, scop->names);
356 fprintf(file, "# Number of statements\n");
357 fprintf(file, "%d\n\n",openscop_statement_number(scop->statement));
359 openscop_statement_print(file, scop->statement, names);
361 if (scop->extension) {
362 fprintf(file, "# ==============================================="
363 " Extensions\n");
364 openscop_extension_print(file, scop->extension);
367 openscop_names_free(names);
371 /*****************************************************************************
372 * Reading function *
373 *****************************************************************************/
377 * openscop_scop_read function:
378 * this function reads a scop structure from a file (possibly stdin)
379 * complying to the OpenScop textual format and returns a pointer to this
380 * scop structure. If some relation properties (number of input/output/local
381 * dimensions and number of parameters) are undefined, it will define them
382 * according to the available information.
383 * \param file The file where the scop has to be read.
384 * \return A pointer to the scop structure that has been read.
386 openscop_scop_p openscop_scop_read(FILE * file) {
387 openscop_scop_p scop = NULL;
388 openscop_statement_p stmt = NULL;
389 openscop_statement_p prev = NULL;
390 int nb_statements;
391 int max;
392 char ** tmp;
393 int i;
395 if (file == NULL)
396 return NULL;
398 scop = openscop_scop_malloc();
401 // I. CONTEXT PART
404 // Ensure the file is a .scop.
405 tmp = openscop_util_strings_read(file, &max);
406 if ((max == 0) || (strcmp(*tmp, "OpenScop"))) {
407 fprintf(stderr, "[OpenScop] Error: not an OpenScop file "
408 "(type \"%s\".\n", *tmp);
409 exit (1);
411 if (max > 1)
412 fprintf(stderr, "[OpenScop] Warning: uninterpreted information "
413 "(after file type).\n");
414 free(*tmp);
415 free(tmp);
417 // Read the language.
418 char ** language = openscop_util_strings_read(file, &max);
419 if (max == 0) {
420 fprintf(stderr, "[OpenScop] Error: no language (backend) specified.\n");
421 exit (1);
423 if (max > 1)
424 fprintf(stderr, "[OpenScop] Warning: uninterpreted information "
425 "(after language).\n");
426 scop->language = *language;
427 free(language);
429 // Read the context.
430 scop->context = openscop_relation_read(file);
431 scop->names = openscop_names_read(file);
434 // II. STATEMENT PART
437 // Read the number of statements.
438 nb_statements = openscop_util_read_int(file, NULL);
440 for (i = 0; i < nb_statements; i++) {
441 // Read each statement.
442 stmt = openscop_statement_read(file);
443 if (scop->statement == NULL)
444 scop->statement = stmt;
445 else
446 prev->next = stmt;
447 prev = stmt;
451 // III. EXTENSION PART
454 // Read the remainder of the file, and store it in the extension field.
455 scop->extension = openscop_extension_read(file);
458 // VI. FINALIZE AND CHECK
460 if (!openscop_scop_integrity_check(scop))
461 fprintf(stderr, "[OpenScop] Warning: global integrity check failed.\n");
463 return scop;
467 /*+***************************************************************************
468 * Memory allocation/deallocation functions *
469 *****************************************************************************/
473 * openscop_scop_malloc function:
474 * this function allocates the memory space for a openscop_scop_t structure and
475 * sets its fields with default values. Then it returns a pointer to the
476 * allocated space.
477 * \return A pointer to an empty scop with fields set to default values.
479 openscop_scop_p openscop_scop_malloc() {
480 openscop_scop_p scop;
482 scop = (openscop_scop_p)malloc(sizeof(openscop_scop_t));
483 if (scop == NULL) {
484 fprintf(stderr, "[OpenScop] Memory Overflow.\n");
485 exit(1);
488 scop->version = 1;
489 scop->language = NULL;
490 scop->context = NULL;
491 scop->names = NULL;
492 scop->statement = NULL;
493 scop->extension = NULL;
494 scop->usr = NULL;
496 return scop;
501 * openscop_scop_free function:
502 * This function frees the allocated memory for a openscop_scop_t structure.
503 * \param scop The pointer to the scop we want to free.
505 void openscop_scop_free(openscop_scop_p scop) {
506 if (scop != NULL) {
507 if (scop->language != NULL)
508 free(scop->language);
510 openscop_relation_free(scop->context);
511 openscop_names_free(scop->names);
512 openscop_statement_free(scop->statement);
513 openscop_extension_free(scop->extension);
515 free(scop);
520 /*+***************************************************************************
521 * Processing functions *
522 *****************************************************************************/
526 * openscop_scop_copy function:
527 * This functions builds and returns a "hard copy" (not a pointer copy)
528 * of a openscop_statement_t data structure provided as parameter.
529 * Note that the usr field is not touched by this function.
530 * \param statement The pointer to the scop we want to copy.
531 * \return A pointer to the full copy of the scop provided as parameter.
533 openscop_scop_p openscop_scop_copy(openscop_scop_p scop) {
534 openscop_scop_p copy;
536 copy = openscop_scop_malloc();
537 copy->version = scop->version;
538 if (scop->language != NULL)
539 copy->language = strdup(scop->language);
540 copy->context = openscop_relation_copy(scop->context);
541 copy->names = openscop_names_copy(scop->names);
542 copy->statement = openscop_statement_copy(scop->statement);
543 copy->extension = openscop_extension_copy(scop->extension);
545 return copy;
550 * openscop_scop_equal function:
551 * this function returns true if the two scops are the same, false
552 * otherwise (the usr field is not tested).
553 * \param s1 The first scop.
554 * \param s2 The second scop.
555 * \return 1 if s1 and s2 are the same (content-wise), 0 otherwise.
557 int openscop_scop_equal(openscop_scop_p s1, openscop_scop_p s2) {
559 if (s1 == s2)
560 return 1;
562 if (s1->version != s2->version) {
563 fprintf(stderr, "[OpenScop] info: versions are not the same.\n");
564 return 0;
567 if (strcmp(s1->language, s2->language) != 0) {
568 fprintf(stderr, "[OpenScop] info: languages are not the same.\n");
569 return 0;
572 if (!openscop_relation_equal(s1->context, s2->context)) {
573 fprintf(stderr, "[OpenScop] info: contexts are not the same.\n");
574 return 0;
577 if (!openscop_names_equal(s1->names, s2->names)) {
578 fprintf(stderr, "[OpenScop] info: names are not the same.\n");
579 return 0;
582 if (!openscop_statement_equal(s1->statement, s2->statement)) {
583 fprintf(stderr, "[OpenScop] info: statements are not the same.\n");
584 return 0;
587 if (!openscop_extension_equal(s1->extension, s2->extension)) {
588 fprintf(stderr, "[OpenScop] info: extensions are not the same.\n");
589 return 0;
592 return 1;
597 * openscop_scop_integrity_check function:
598 * This function checks that a scop is "well formed". It returns 0 if the
599 * check failed or 1 if no problem has been detected.
600 * \param scop The scop we want to check.
601 * \return 0 if the integrity check fails, 1 otherwise.
603 int openscop_scop_integrity_check(openscop_scop_p scop) {
604 int expected_nb_parameters;
605 int max_nb_parameters;
606 int max_nb_iterators;
607 int max_nb_scattdims;
608 int max_nb_localdims;
609 int max_nb_arrays;
611 // Check the language.
612 if ((scop->language != NULL) &&
613 (!strcmp(scop->language, "caml") || !strcmp(scop->language, "Caml") ||
614 !strcmp(scop->language, "ocaml") || !strcmp(scop->language, "OCaml")))
615 fprintf(stderr, "[OpenScop] Alert: What ?! Caml ?! Are you sure ?!?!\n");
617 // Check the context.
618 if (!openscop_relation_integrity_check(scop->context,
619 OPENSCOP_TYPE_CONTEXT,
620 OPENSCOP_UNDEFINED,
621 OPENSCOP_UNDEFINED,
622 OPENSCOP_UNDEFINED))
623 return 0;
625 // Get the number of parameters.
626 if (scop->context != NULL)
627 expected_nb_parameters = scop->context->nb_parameters;
628 else
629 expected_nb_parameters = OPENSCOP_UNDEFINED;
631 if (!openscop_statement_integrity_check(scop->statement,
632 expected_nb_parameters))
633 return 0;
635 // Ensure we have enough names.
636 openscop_scop_name_limits(scop, &max_nb_parameters,
637 &max_nb_iterators,
638 &max_nb_scattdims,
639 &max_nb_localdims,
640 &max_nb_arrays);
642 return openscop_names_integrity_check(scop->names, expected_nb_parameters,
643 max_nb_iterators, max_nb_scattdims);