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
*****************************************************************************/
69
#include <osl/macros.h>
71
#include <osl/strings.h>
73
#include <osl/relation.h>
74
#include <osl/relation_list.h>
75
#include <osl/names.h>
76
#include <osl/interface.h>
77
#include <osl/generic.h>
78
#include <osl/statement.h>
81
/*+***************************************************************************
82
* Structure display functions *
83
*****************************************************************************/
87
* osl_statement_idump function:
88
* this function displays an osl_statement_t structure (*statement) into
89
* a file (file, possibly stdout) in a way that trends to be understandable.
90
* It includes an indentation level (level) in order to work with others
92
* \param[in] file File where the information has to be printed.
93
* \param[in] statement The statement whose information has to be printed.
94
* \param[in] level Number of spaces before printing, for each line.
96
void osl_statement_idump(FILE * file, osl_statement_p statement, int level) {
97
int j, first = 1, number = 1;
99
// Go to the right level.
100
for (j = 0; j < level; j++)
101
fprintf(file, "|\t");
103
if (statement != NULL)
104
fprintf(file, "+-- osl_statement_t (S%d)\n", number);
106
fprintf(file, "+-- NULL statement\n");
108
while (statement != NULL) {
110
// Go to the right level.
111
for (j = 0; j < level; j++)
112
fprintf(file, "|\t");
113
fprintf(file, "| osl_statement_t (S%d)\n", number);
119
for (j = 0; j <= level + 1; j++)
120
fprintf(file, "|\t");
123
// Print the domain of the statement.
124
osl_relation_idump(file, statement->domain, level + 1);
126
// Print the scattering of the statement.
127
osl_relation_idump(file, statement->scattering, level + 1);
129
// Print the array access information of the statement.
130
osl_relation_list_idump(file, statement->access, level + 1);
132
// Print the original body expression.
133
osl_generic_idump(file, statement->body, level + 1);
135
statement = statement->next;
139
if (statement != NULL) {
140
for (j = 0; j <= level; j++)
141
fprintf(file, "|\t");
142
fprintf(file, "V\n");
147
for (j = 0; j <= level; j++)
148
fprintf(file, "|\t");
154
* osl_statement_dump function:
155
* this function prints the content of an osl_statement_t structure
156
* (*statement) into a file (file, possibly stdout).
157
* \param[in] file The file where the information has to be printed.
158
* \param[in] statement The statement whose information has to be printed.
160
void osl_statement_dump(FILE * file, osl_statement_p statement) {
161
osl_statement_idump(file, statement, 0);
166
* osl_statement_names function:
167
* this function generates as set of names for all the dimensions
168
* involved in a given statement.
169
* \param[in] statement The statement (list) we have to generate names for.
170
* \return A set of generated names for the input statement dimensions.
173
osl_names_p osl_statement_names(osl_statement_p statement) {
174
int nb_parameters = OSL_UNDEFINED;
175
int nb_iterators = OSL_UNDEFINED;
176
int nb_scattdims = OSL_UNDEFINED;
177
int nb_localdims = OSL_UNDEFINED;
178
int array_id = OSL_UNDEFINED;
180
osl_statement_get_attributes(statement, &nb_parameters, &nb_iterators,
181
&nb_scattdims, &nb_localdims, &array_id);
183
return osl_names_generate("P", nb_parameters,
192
* osl_statement_pprint function:
193
* this function pretty-prints the content of an osl_statement_t structure
194
* (*statement) into a file (file, possibly stdout) in the OpenScop format.
195
* \param[in] file The file where the information has to be printed.
196
* \param[in] statement The statement whose information has to be printed.
197
* \param[in] names The names of the constraint columns for comments.
199
void osl_statement_pprint(FILE * file, osl_statement_p statement,
201
int nb_relations, number = 1;
202
int generated_names = 0;
203
int iterators_backedup = 0;
204
osl_strings_p iterators_backup = NULL;
206
// Generate the dimension names if necessary and replace iterators with
207
// statement iterators if possible.
210
names = osl_statement_names(statement);
213
while (statement != NULL) {
214
// If possible, replace iterator names with statement iterator names.
215
if (osl_generic_has_URI(statement->body, OSL_URI_BODY) &&
216
(((osl_body_p)(statement->body->data))->iterators != NULL)) {
217
iterators_backedup = 1;
218
iterators_backup = names->iterators;
219
names->iterators = ((osl_body_p)(statement->body->data))->iterators;
224
fprintf(file, "# =============================================== ");
225
fprintf(file, "Statement %d\n", number);
227
fprintf(file, "# Number of relations describing the statement:\n");
229
if (statement->domain != NULL)
231
if (statement->scattering != NULL)
233
nb_relations += osl_relation_list_count(statement->access);
235
fprintf(file, "%d\n\n", nb_relations);
237
fprintf(file, "# ---------------------------------------------- ");
238
fprintf(file, "%2d.1 Domain\n", number);
239
osl_relation_pprint(file, statement->domain, names);
242
fprintf(file, "# ---------------------------------------------- ");
243
fprintf(file, "%2d.2 Scattering\n", number);
244
osl_relation_pprint(file, statement->scattering, names);
247
fprintf(file, "# ---------------------------------------------- ");
248
fprintf(file, "%2d.3 Access\n", number);
249
osl_relation_list_pprint_elts(file, statement->access, names);
252
fprintf(file, "# ---------------------------------------------- ");
253
fprintf(file, "%2d.4 Body\n", number);
254
if (statement->body != NULL) {
255
fprintf(file, "# Statement body is provided\n");
256
fprintf(file, "1\n");
257
osl_generic_print(file, statement->body);
260
fprintf(file, "# Statement body is not provided\n");
261
fprintf(file, "0\n");
266
// If necessary, switch back iterator names.
267
if (iterators_backedup) {
268
iterators_backedup = 0;
269
names->iterators = iterators_backup;
272
statement = statement->next;
277
osl_names_free(names);
282
* osl_statement_print function:
283
* this function prints the content of an osl_statement_t structure
284
* (*statement) into a file (file, possibly stdout) in the OpenScop format.
285
* \param[in] file The file where the information has to be printed.
286
* \param[in] statement The statement whose information has to be printed.
288
void osl_statement_print(FILE * file, osl_statement_p statement) {
290
osl_statement_pprint(file, statement, NULL);
294
/*****************************************************************************
296
*****************************************************************************/
300
* osl_statement_dispatch function:
301
* this function dispatches the relations from a relation list to the
302
* convenient fields of a statement structure: it extracts the domain,
303
* the scattering and the access list and store them accordingly in the
304
* statement structure provided as a parameter.
305
* \param[in,out] stmt The statement where to dispatch the relations.
306
* \param[in,out] list The "brute" relation list to sort and dispatch (freed).
309
void osl_statement_dispatch(osl_statement_p stmt, osl_relation_list_p list) {
310
osl_relation_list_p domain_list;
311
osl_relation_list_p scattering_list;
312
int nb_domains, nb_scattering, nb_accesses;
315
domain_list = osl_relation_list_filter(list, OSL_TYPE_DOMAIN);
316
nb_domains = osl_relation_list_count(domain_list);
318
OSL_error("more than one domain for a statement");
320
if (domain_list != NULL) {
321
stmt->domain = domain_list->elt;
322
domain_list->elt = NULL;
323
osl_relation_list_free(domain_list);
330
scattering_list=osl_relation_list_filter(list,OSL_TYPE_SCATTERING);
331
nb_scattering = osl_relation_list_count(scattering_list);
332
if (nb_scattering > 1)
333
OSL_error("more than one scattering relation for a statement");
335
if (scattering_list != NULL) {
336
stmt->scattering = scattering_list->elt;
337
scattering_list->elt = NULL;
338
osl_relation_list_free(scattering_list);
341
stmt->scattering = NULL;
345
stmt->access = osl_relation_list_filter(list, OSL_TYPE_ACCESS);
346
nb_accesses = osl_relation_list_count(stmt->access);
348
if ((nb_domains + nb_scattering + nb_accesses) !=
349
(osl_relation_list_count(list)))
350
OSL_error("unexpected relation type to define a statement");
352
osl_relation_list_free(list);
357
* osl_statement_pread function ("precision read"):
358
* this function reads an osl_statement_t structure from an input stream
360
* \param[in] file The input stream.
361
* \param[in] registry The list of known interfaces (others are ignored).
362
* \param[in] precision The precision of the relation elements.
363
* \return A pointer to the statement structure that has been read.
365
osl_statement_p osl_statement_pread(FILE * file, osl_interface_p registry,
367
osl_statement_p stmt = osl_statement_malloc();
368
osl_relation_list_p list;
371
// Read all statement relations.
372
list = osl_relation_list_pread(file, precision);
374
// Store relations at the right place according to their type.
375
osl_statement_dispatch(stmt, list);
377
// Read the body information.
378
if (osl_util_read_int(file, NULL) > 0)
379
stmt->body = osl_generic_read_one(file, registry);
387
* osl_statement_read function:
388
* this function is equivalent to osl_statement_pread() except that
389
* (1) the precision corresponds to the precision environment variable or
390
* to the highest available precision if it is not defined, and
391
* (2) the list of known interface is set to the default one.
392
* \see{osl_statement_pread}
394
osl_statement_p osl_statement_read(FILE * foo) {
395
int precision = osl_util_get_precision();
396
osl_interface_p registry = osl_interface_get_default_registry();
397
osl_statement_p statement = osl_statement_pread(foo, registry, precision);
399
osl_interface_free(registry);
404
/*+***************************************************************************
405
* Memory allocation/deallocation functions *
406
*****************************************************************************/
410
* osl_statement_malloc function:
411
* this function allocates the memory space for an osl_statement_t
412
* structure and sets its fields with default values. Then it returns a pointer
413
* to the allocated space.
414
* \return A pointer to an empty statement with fields set to default values.
416
osl_statement_p osl_statement_malloc() {
417
osl_statement_p statement;
419
OSL_malloc(statement, osl_statement_p, sizeof(osl_statement_t));
420
statement->domain = NULL;
421
statement->scattering = NULL;
422
statement->access = NULL;
423
statement->body = NULL;
424
statement->next = NULL;
431
* osl_statement_free function:
432
* this function frees the allocated memory for an osl_statement_t
434
* \param[in,out] statement The pointer to the statement we want to free.
436
void osl_statement_free(osl_statement_p statement) {
437
osl_statement_p next;
439
while (statement != NULL) {
440
next = statement->next;
441
osl_relation_free(statement->domain);
442
osl_relation_free(statement->scattering);
443
osl_relation_list_free(statement->access);
444
osl_generic_free(statement->body);
452
/*+***************************************************************************
453
* Processing functions *
454
*****************************************************************************/
458
* osl_statement_add function:
459
* this function adds a statement "statement" at the end of the statement
460
* list pointed by "location".
461
* \param[in,out] location Address of the first element of the statement list.
462
* \param[in] statement The statement to add to the list.
464
void osl_statement_add(osl_statement_p * location,
465
osl_statement_p statement) {
466
while (*location != NULL)
467
location = &((*location)->next);
469
*location = statement;
474
* osl_statement_number function:
475
* this function returns the number of statements in the statement list
476
* provided as parameter.
477
* \param[in] statement The first element of the statement list.
478
* \return The number of statements in the statement list.
480
int osl_statement_number(osl_statement_p statement) {
483
while (statement != NULL) {
485
statement = statement->next;
492
* osl_statement_clone function:
493
* This functions builds and returns a "hard copy" (not a pointer copy) of an
494
* osl_statement_t data structure provided as parameter.
495
* \param[in] statement The pointer to the statement we want to clone.
496
* \return A pointer to the clone of the statement provided as parameter.
498
osl_statement_p osl_statement_clone(osl_statement_p statement) {
500
osl_statement_p clone = NULL, node, previous = NULL;
502
while (statement != NULL) {
503
node = osl_statement_malloc();
504
node->domain = osl_relation_clone(statement->domain);
505
node->scattering = osl_relation_clone(statement->scattering);
506
node->access = osl_relation_list_clone(statement->access);
507
node->body = osl_generic_clone(statement->body);
516
previous->next = node;
517
previous = previous->next;
520
statement = statement->next;
528
* osl_statement_equal function:
529
* this function returns true if the two statements provided as parameters
530
* are the same, false otherwise (the usr field is not tested).
531
* \param[in] s1 The first statement.
532
* \param[in] s2 The second statement.
533
* \return 1 if s1 and s2 are the same (content-wise), 0 otherwise.
535
int osl_statement_equal(osl_statement_p s1, osl_statement_p s2) {
540
if (((s1->next != NULL) && (s2->next == NULL)) ||
541
((s1->next == NULL) && (s2->next != NULL))) {
542
OSL_info("statements are not the same");
546
if ((s1->next != NULL) && (s2->next != NULL)) {
547
if (!osl_statement_equal(s1->next, s2->next)) {
548
OSL_info("number of statements is not the same");
553
if (!osl_relation_equal(s1->domain, s2->domain)) {
554
OSL_info("statement domains are not the same");
558
if (!osl_relation_equal(s1->scattering, s2->scattering)) {
559
OSL_info("statement scatterings are not the same");
563
if (!osl_relation_list_equal(s1->access, s2->access)) {
564
OSL_info("statement accesses are not the same");
568
if (!osl_generic_equal(s1->body, s2->body)) {
569
OSL_info("statement bodies are not the same");
578
* osl_statement_integrity_check function:
579
* this function checks that a statement is "well formed" according to some
580
* expected properties (setting an expected value to OSL_UNDEFINED means
581
* that we do not expect a specific value). It returns 0 if the check failed
582
* or 1 if no problem has been detected.
583
* \param[in] statement The statement we want to check.
584
* \param[in] expected_nb_parameters Expected number of parameters.
585
* \return 0 if the integrity check fails, 1 otherwise.
587
int osl_statement_integrity_check(osl_statement_p statement,
588
int expected_nb_parameters) {
589
int expected_nb_iterators;
591
while (statement != NULL) {
593
if (!osl_relation_integrity_check(statement->domain,
597
expected_nb_parameters)) {
601
// Get the number of iterators.
602
if (statement->domain != NULL)
603
expected_nb_iterators = statement->domain->nb_output_dims;
605
expected_nb_iterators = OSL_UNDEFINED;
607
// Check the scattering relation.
608
if (!osl_relation_integrity_check(statement->scattering,
611
expected_nb_iterators,
612
expected_nb_parameters)) {
616
// Check the access relations.
617
if (!osl_relation_list_integrity_check(statement->access,
620
expected_nb_iterators,
621
expected_nb_parameters)) {
625
// Check the statement body.
626
if ((expected_nb_iterators != OSL_UNDEFINED) &&
627
(osl_generic_has_URI(statement->body, OSL_URI_BODY)) &&
628
(((osl_body_p)(statement->body->data))->iterators != NULL) &&
629
(expected_nb_iterators != osl_strings_size(
630
((osl_body_p)(statement->body->data))->iterators))) {
631
OSL_warning("unexpected number of original iterators");
635
statement = statement->next;
643
* osl_statement_get_nb_iterators function:
644
* this function returns the number of surroounding iterators of a given
646
* \param statement The statement we want to know the number of iterators.
647
* \return The number of surrounding iterators for the statement.
649
int osl_statement_get_nb_iterators(osl_statement_p statement) {
651
if (statement->domain == NULL) {
652
OSL_warning("no statement domain, assuming 0 iterators");
656
return statement->domain->nb_output_dims;
662
* osl_statement_get_attributes function:
663
* this function returns, through its parameters, the maximum values of the
664
* relation attributes (nb_iterators, nb_parameters etc) in the statement.
665
* HOWEVER, it updates the parameter value iff the attribute is greater than
666
* the input parameter value. Hence it may be used to get the attributes as
667
* well as to find the maximum attributes for several statement lists. The
668
* array identifier 0 is used when there is no array identifier (AND this is
669
* OK), OSL_UNDEFINED is used to report it is impossible to provide the
670
* property while it should. This function is not intended for checking, the
671
* input statement should be correct.
672
* \param[in] statement The statement to extract attributes values.
673
* \param[in,out] nb_parameters Number of parameter attribute.
674
* \param[in,out] nb_iterators Number of iterators attribute.
675
* \param[in,out] nb_scattdims Number of scattering dimensions attribute.
676
* \param[in,out] nb_localdims Number of local dimensions attribute.
677
* \param[in,out] array_id Maximum array identifier attribute.
679
void osl_statement_get_attributes(osl_statement_p statement,
685
int local_nb_parameters = OSL_UNDEFINED;
686
int local_nb_iterators = OSL_UNDEFINED;
687
int local_nb_scattdims = OSL_UNDEFINED;
688
int local_nb_localdims = OSL_UNDEFINED;
689
int local_array_id = OSL_UNDEFINED;
691
while (statement != NULL) {
692
osl_relation_get_attributes(statement->domain,
693
&local_nb_parameters,
699
osl_relation_get_attributes(statement->scattering,
700
&local_nb_parameters,
706
osl_relation_list_get_attributes(statement->access,
707
&local_nb_parameters,
713
*nb_parameters = OSL_max(*nb_parameters, local_nb_parameters);
714
*nb_iterators = OSL_max(*nb_iterators, local_nb_iterators);
715
*nb_scattdims = OSL_max(*nb_scattdims, local_nb_scattdims);
716
*nb_localdims = OSL_max(*nb_localdims, local_nb_localdims);
717
*array_id = OSL_max(*array_id, local_array_id);
718
statement = statement->next;