2 /*+-----------------------------------------------------------------**
4 **-----------------------------------------------------------------**
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 * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' *
30 * Copyright (C) 2008 University Paris-Sud 11 and INRIA *
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 *
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. *
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. *
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> *
61 *****************************************************************************/
67 # include <openscop/scop.h>
70 /*+***************************************************************************
71 * Structure display functions *
72 *****************************************************************************/
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
) {
88 // Go to the right level.
89 for (j
= 0; j
< level
; j
++)
93 fprintf(file
, "+-- openscop_scop_t\n");
96 for (j
= 0; j
<= level
+1; j
++)
100 // Print the language.
101 for (j
= 0; j
< level
; j
++)
102 fprintf(file
, "|\t");
103 fprintf(file
, "|\tLanguage: %s\n", scop
->language
);
106 for (j
= 0; j
<= level
+1; j
++)
107 fprintf(file
, "|\t");
110 // Print the context of the scop.
111 openscop_relation_idump(file
, scop
->context
, level
+1);
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);
123 for (j
= 0; j
<= level
+1; j
++)
124 fprintf(file
, "|\t");
128 fprintf(file
, "+-- NULL scop\n");
132 for (j
= 0; j
<= level
; j
++)
133 fprintf(file
, "|\t");
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
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).
164 void openscop_scop_name_limits(openscop_scop_p scop
,
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.
179 if (scop
->context
!= NULL
) {
180 *nb_parameters
= scop
->context
->nb_parameters
;
181 *nb_localdims
= scop
->context
->nb_local_dims
;
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
;
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.
234 openscop_names_p
openscop_scop_full_names(openscop_scop_p scop
) {
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
,
259 openscop_util_strings_complete(&names
->parameters
, &names
->nb_parameters
,
260 "P_", nb_parameters
);
262 openscop_util_strings_complete(&names
->iterators
, &names
->nb_iterators
,
265 openscop_util_strings_complete(&names
->scattdims
, &names
->nb_scattdims
,
268 openscop_util_strings_complete(&names
->localdims
, &names
->nb_localdims
,
271 openscop_util_strings_complete(&names
->arrays
, &names
->nb_arrays
,
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
);
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");
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
;
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
, "# ==============================================="
364 openscop_extension_print(file
, scop
->extension
);
367 openscop_names_free(names
);
371 /*****************************************************************************
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
;
398 scop
= openscop_scop_malloc();
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
);
412 fprintf(stderr
, "[OpenScop] Warning: uninterpreted information "
413 "(after file type).\n");
417 // Read the language.
418 char ** language
= openscop_util_strings_read(file
, &max
);
420 fprintf(stderr
, "[OpenScop] Error: no language (backend) specified.\n");
424 fprintf(stderr
, "[OpenScop] Warning: uninterpreted information "
425 "(after language).\n");
426 scop
->language
= *language
;
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
;
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");
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
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
));
484 fprintf(stderr
, "[OpenScop] Memory Overflow.\n");
489 scop
->language
= NULL
;
490 scop
->context
= NULL
;
492 scop
->statement
= NULL
;
493 scop
->extension
= NULL
;
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
) {
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
);
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
);
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
) {
562 if (s1
->version
!= s2
->version
) {
563 fprintf(stderr
, "[OpenScop] info: versions are not the same.\n");
567 if (strcmp(s1
->language
, s2
->language
) != 0) {
568 fprintf(stderr
, "[OpenScop] info: languages are not the same.\n");
572 if (!openscop_relation_equal(s1
->context
, s2
->context
)) {
573 fprintf(stderr
, "[OpenScop] info: contexts are not the same.\n");
577 if (!openscop_names_equal(s1
->names
, s2
->names
)) {
578 fprintf(stderr
, "[OpenScop] info: names are not the same.\n");
582 if (!openscop_statement_equal(s1
->statement
, s2
->statement
)) {
583 fprintf(stderr
, "[OpenScop] info: statements are not the same.\n");
587 if (!openscop_extension_equal(s1
->extension
, s2
->extension
)) {
588 fprintf(stderr
, "[OpenScop] info: extensions are not the same.\n");
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
;
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
,
625 // Get the number of parameters.
626 if (scop
->context
!= NULL
)
627 expected_nb_parameters
= scop
->context
->nb_parameters
;
629 expected_nb_parameters
= OPENSCOP_UNDEFINED
;
631 if (!openscop_statement_integrity_check(scop
->statement
,
632 expected_nb_parameters
))
635 // Ensure we have enough names.
636 openscop_scop_name_limits(scop
, &max_nb_parameters
,
642 return openscop_names_integrity_check(scop
->names
, expected_nb_parameters
,
643 max_nb_iterators
, max_nb_scattdims
);