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 *****************************************************************************/
68 # include <openscop/relation.h>
71 /*+***************************************************************************
72 * Structure display function *
73 *****************************************************************************/
77 * openscop_relation_print_type function:
78 * this function displays the textual type of an openscop_relation_t structure
79 * into a file (file, possibly stdout), accoding to the OpenScop specification.
80 * \param[in] file File where informations are printed.
81 * \param[in] relation The relation whose type has to be printed.
84 void openscop_relation_print_type(FILE * file
, openscop_relation_p relation
) {
86 if (relation
!= NULL
) {
87 switch (relation
->type
) {
88 case OPENSCOP_UNDEFINED
: {
89 fprintf(file
, OPENSCOP_STRING_UNDEFINED
);
92 case OPENSCOP_TYPE_CONTEXT
: {
93 fprintf(file
, OPENSCOP_STRING_CONTEXT
);
96 case OPENSCOP_TYPE_DOMAIN
: {
97 fprintf(file
, OPENSCOP_STRING_DOMAIN
);
100 case OPENSCOP_TYPE_SCATTERING
: {
101 fprintf(file
, OPENSCOP_STRING_SCATTERING
);
104 case OPENSCOP_TYPE_READ
: {
105 fprintf(file
, OPENSCOP_STRING_READ
);
108 case OPENSCOP_TYPE_WRITE
: {
109 fprintf(file
, OPENSCOP_STRING_WRITE
);
112 case OPENSCOP_TYPE_MAY_WRITE
: {
113 fprintf(file
, OPENSCOP_STRING_MAY_WRITE
);
117 OPENSCOP_warning("unknown relation type, "
118 "replaced with "OPENSCOP_STRING_UNDEFINED
);
119 fprintf(file
, OPENSCOP_STRING_UNDEFINED
);
127 * openscop_relation_idump function:
128 * this function displays a openscop_relation_t structure (*relation) into a
129 * file (file, possibly stdout) in a way that trends to be understandable.
130 * It includes an indentation level (level) in order to work with others
131 * print_structure functions.
132 * \param[in] file File where informations are printed.
133 * \param[in] relation The relation whose information has to be printed.
134 * \param[in] level Number of spaces before printing, for each line.
136 void openscop_relation_idump(FILE * file
,
137 openscop_relation_p relation
,
141 // Go to the right level.
142 for (j
= 0; j
< level
; j
++)
143 fprintf(file
, "|\t");
145 if (relation
!= NULL
) {
146 fprintf(file
, "+-- openscop_relation_t (");
147 openscop_relation_print_type(file
, relation
);
148 fprintf(file
, ")\n");
151 fprintf(file
, "+-- NULL relation\n");
154 while (relation
!= NULL
) {
156 // Go to the right level.
157 for (j
= 0; j
< level
; j
++)
158 fprintf(file
, "|\t");
159 fprintf(file
, "| openscop_relation_t (");
160 openscop_relation_print_type(file
, relation
);
161 fprintf(file
, ")\n");
167 for(j
= 0; j
<= level
; j
++)
168 fprintf(file
, "|\t");
169 fprintf(file
, "%d %d %d %d %d %d\n",
170 relation
->nb_rows
, relation
->nb_columns
,
171 relation
->nb_output_dims
, relation
->nb_input_dims
,
172 relation
->nb_local_dims
, relation
->nb_parameters
);
174 // Display the relation.
175 for (i
= 0; i
< relation
->nb_rows
; i
++) {
176 for (j
= 0; j
<= level
; j
++)
177 fprintf(file
, "|\t");
181 for (j
= 0; j
< relation
->nb_columns
; j
++) {
182 OPENSCOP_INT_dump(file
, OPENSCOP_FMT
, relation
->m
[i
][j
]);
186 fprintf(file
, "]\n");
189 relation
= relation
->next
;
192 if (relation
!= NULL
) {
193 for (j
= 0; j
<= level
; j
++)
194 fprintf(file
, "|\t");
195 fprintf(file
, "|\n");
196 for (j
= 0; j
<= level
; j
++)
197 fprintf(file
, "|\t");
198 fprintf(file
, "V\n");
203 for (j
= 0; j
<= level
; j
++)
204 fprintf(file
, "|\t");
210 * openscop_relation_dump function:
211 * this function prints the content of a openscop_relation_t structure
212 * (*relation) into a file (file, possibly stdout).
213 * \param[in] file File where informations are printed.
214 * \param[in] relation The relation whose information have to be printed.
216 void openscop_relation_dump(FILE * file
, openscop_relation_p relation
) {
217 openscop_relation_idump(file
, relation
, 0);
223 * openscop_relation_expression_element function:
224 * this function returns a string containing the printing of a value (possibly
225 * an iterator or a parameter with its coefficient or a constant).
226 * \param[in] val The coefficient or constant value.
227 * \param[in,out] first Pointer to a boolean set to 1 if the current value is
228 * the first of an expresion, 0 otherwise (maybe updated).
229 * \param[in] cst A boolean set to 1 if the value is a constant,
231 * \param[in] name String containing the name of the element.
232 * \return A string that contains the printing of a value.
235 char * openscop_relation_expression_element(openscop_int_t val
, int * first
,
236 int cst
, char * name
) {
237 char * temp
= (char *)malloc(OPENSCOP_MAX_STRING
* sizeof(char));
238 char * body
= (char *)malloc(OPENSCOP_MAX_STRING
* sizeof(char));
239 char * sval
= (char *)malloc(OPENSCOP_MAX_STRING
* sizeof(char));
244 // statements for the 'normal' processing.
245 if (OPENSCOP_INT_notzero_p(val
) && (!cst
)) {
246 if ((*first
) || OPENSCOP_INT_neg_p(val
)) {
247 if (OPENSCOP_INT_one_p(val
)) { // case 1
248 sprintf(sval
, "%s", name
);
251 if (OPENSCOP_INT_mone_p(val
)) { // case -1
252 sprintf(sval
, "-%s", name
);
254 else { // default case
255 OPENSCOP_INT_sprint(sval
, OPENSCOP_FMT_TXT
, val
);
256 sprintf(temp
, "*%s", name
);
263 if (OPENSCOP_INT_one_p(val
)) {
264 sprintf(sval
, "+%s", name
);
268 OPENSCOP_INT_sprint(temp
, OPENSCOP_FMT_TXT
, val
);
270 sprintf(temp
, "*%s", name
);
277 if ((OPENSCOP_INT_zero_p(val
) && (*first
)) || OPENSCOP_INT_neg_p(val
))
278 OPENSCOP_INT_sprint(sval
, OPENSCOP_FMT_TXT
, val
);
279 if (OPENSCOP_INT_pos_p(val
)) {
281 OPENSCOP_INT_sprint(sval
, "+"OPENSCOP_FMT_TXT
, val
); // Block macro !
284 OPENSCOP_INT_sprint(sval
, OPENSCOP_FMT_TXT
, val
);
297 * openscop_relation_expression function:
298 * this function returns a string corresponding to an affine expression
299 * stored at the "row"^th row of the relation pointed by "relation".
300 * \param[in] relation A set of linear expressions.
301 * \param[in] row The row corresponding to the expression.
302 * \param[in] names The textual names of the various elements.
303 * Set to NULL if printing comments is not needed.
304 * \return A string that contains the printing of an affine expression.
306 char * openscop_relation_expression(openscop_relation_p relation
,
307 int row
, openscop_names_p names
) {
310 char * sline
= (char *)malloc(OPENSCOP_MAX_STRING
* sizeof(char));
313 // First the iterator part.
314 for (i
= 1; i
<= names
->nb_iterators
; i
++) {
315 sval
= openscop_relation_expression_element(
316 relation
->m
[row
][i
], &first
, 0, names
->iterators
[i
-1]);
321 // Next the local dims part.
322 for (i
= names
->nb_iterators
+ 1;
323 i
<= names
->nb_iterators
+ names
->nb_localdims
; i
++) {
324 sval
= openscop_relation_expression_element(
325 relation
->m
[row
][i
], &first
, 0,
326 names
->localdims
[i
- names
->nb_iterators
- 1]);
331 // Next the parameter part.
332 for (i
= names
->nb_iterators
+ names
->nb_localdims
+ 1;
333 i
<= names
->nb_iterators
+ names
->nb_localdims
+ names
->nb_parameters
;
335 sval
= openscop_relation_expression_element(
336 relation
->m
[row
][i
], &first
, 0,
337 names
->parameters
[i
- names
->nb_iterators
- names
->nb_localdims
- 1]);
342 // Finally the constant part (yes, I reused it).
343 sval
= openscop_relation_expression_element(relation
->m
[row
][i
],
353 * openscop_relation_properties function:
354 * this function returns, through its parameters, the values of the relation
355 * attributes (nb_iterators, nb_parameters etc), depending on its value and
356 * its type. The array identifier 0 is used when there is no array
357 * identifier (AND this is OK), OPENSCOP_UNDEFINED is used to report it
358 * is impossible to provide the property while it should.
359 * This function is not intended for checking, the input relation should be
361 * \param[in] relation The relation to extract property values.
362 * \param[out] nb_parameters Number of parameter property.
363 * \param[out] nb_iterators Number of iterators property.
364 * \param[out] nb_scattdims Number of scattering dimensions property.
365 * \param[out] nb_localdims Number of local dimensions property.
366 * \param[out] array_id Array identifier property.
369 void openscop_relation_properties(openscop_relation_p relation
,
378 *nb_parameters
= OPENSCOP_UNDEFINED
;
379 *nb_iterators
= OPENSCOP_UNDEFINED
;
380 *nb_scattdims
= OPENSCOP_UNDEFINED
;
381 *nb_localdims
= OPENSCOP_UNDEFINED
;
382 *array_id
= OPENSCOP_UNDEFINED
;
384 if (relation
== NULL
)
387 if (openscop_relation_is_access(relation
))
388 type
= OPENSCOP_TYPE_ACCESS
;
390 type
= relation
->type
;
392 // There is some redundancy but I believe the code is cleaner this way.
394 case OPENSCOP_TYPE_CONTEXT
: {
395 *nb_parameters
= relation
->nb_parameters
;
398 *nb_localdims
= relation
->nb_local_dims
;
402 case OPENSCOP_TYPE_DOMAIN
: {
403 *nb_parameters
= relation
->nb_parameters
;
404 *nb_iterators
= relation
->nb_output_dims
;
406 *nb_localdims
= relation
->nb_local_dims
;
410 case OPENSCOP_TYPE_SCATTERING
: {
411 *nb_parameters
= relation
->nb_parameters
;
412 *nb_iterators
= relation
->nb_input_dims
;
413 *nb_scattdims
= relation
->nb_output_dims
;
414 *nb_localdims
= relation
->nb_local_dims
;
418 case OPENSCOP_TYPE_ACCESS
: {
419 *nb_parameters
= relation
->nb_parameters
;
420 *nb_iterators
= relation
->nb_input_dims
;
422 *nb_localdims
= relation
->nb_local_dims
;
423 *array_id
= openscop_relation_get_array_id(relation
);
431 * openscop_relation_printable_comments function:
432 * this function returns 1 if we can print safely the comments for the
433 * relation provided as parameter (in the OpenScop file), 0 otherwise.
434 * \param[in] relation The relation we want to know if we can print comments.
435 * \param[in] names The names used for comment printing.
436 * \return 1 if we can print the comments safely, 0 otherwise.
439 int openscop_relation_printable_comments(openscop_relation_p relation
,
440 openscop_names_p names
) {
447 if ((relation
== NULL
) || (names
== NULL
))
450 // TODO: remove this !!!
451 // Temporarily deactivate comments, to finish OpenScop RFC first.
454 // We cannot print comments if the names are not textual.
455 if (names
->textual
!= 1)
458 // We cannot print comments if the relation is not of one known type.
459 if (!(relation
->type
== OPENSCOP_TYPE_DOMAIN
) &&
460 !(relation
->type
== OPENSCOP_TYPE_SCATTERING
) &&
461 !(relation
->type
== OPENSCOP_TYPE_ACCESS
))
464 // We cannot print comments if we are not sure we have enough names.
465 nb_parameters
= names
->nb_parameters
;
466 openscop_relation_properties(relation
, &nb_parameters
, &nb_iterators
,
467 &nb_scattdims
, &nb_localdims
, &array_id
);
469 if ((nb_parameters
== OPENSCOP_UNDEFINED
) ||
470 (nb_iterators
== OPENSCOP_UNDEFINED
) ||
471 (nb_scattdims
== OPENSCOP_UNDEFINED
) ||
472 (nb_localdims
== OPENSCOP_UNDEFINED
) ||
473 (array_id
== OPENSCOP_UNDEFINED
) ||
474 (nb_parameters
> names
->nb_parameters
) ||
475 (nb_iterators
> names
->nb_iterators
) ||
476 (nb_scattdims
> names
->nb_scattdims
) ||
477 (nb_localdims
> names
->nb_localdims
) ||
478 (array_id
> names
->nb_arrays
)) {
480 OPENSCOP_warning("something is wrong with the names or "
481 "an array identifier, printing comments deactivated");
490 * openscop_relation_print_comment function:
491 * this function prints a comment corresponding to a constraint of a relation,
492 * according to its type. This function does not check that printing the
493 * comment is possible (i.e., are there enough names ?), hence it is the
494 * responsibility of the user to ensure he/she can call this function safely.
495 * \param[in] file File where informations are printed.
496 * \param[in] relation The relation for which a comment has to be printed.
497 * \param[in] row The constrain row for which a comment has to be printed.
498 * \param[in] names The textual names of the various elements.
501 void openscop_relation_print_comment(FILE * file
,
502 openscop_relation_p relation
, int row
,
503 openscop_names_p names
) {
508 if (openscop_relation_is_access(relation
))
509 type
= OPENSCOP_TYPE_ACCESS
;
511 type
= relation
->type
;
514 case OPENSCOP_TYPE_DOMAIN
: {
515 expression
= openscop_relation_expression(relation
, row
, names
);
516 fprintf(file
, " ## %s", expression
);
518 if (OPENSCOP_INT_zero_p(relation
->m
[row
][0]))
519 fprintf(file
, " == 0");
521 fprintf(file
, " >= 0");
524 case OPENSCOP_TYPE_SCATTERING
: {
525 expression
= openscop_relation_expression(relation
, row
, names
);
526 fprintf(file
, " ## %s", expression
);
530 case OPENSCOP_TYPE_ACCESS
: {
531 //TODO: works only for matrix: use openscop_relation_get_array_id
532 if (OPENSCOP_INT_notzero_p(relation
->m
[row
][0])) {
533 if (strncmp(names
->arrays
[OPENSCOP_INT_get_si(relation
->m
[row
][0]) - 1],
534 OPENSCOP_FAKE_ARRAY
, strlen(OPENSCOP_FAKE_ARRAY
)))
535 fprintf(file
, " ## %s",
536 names
->arrays
[OPENSCOP_INT_get_si(relation
->m
[row
][0]) - 1]);
539 expression
= openscop_relation_expression(relation
, k
, names
);
540 fprintf(file
, "[%s]", expression
);
544 while ((k
< relation
->nb_rows
) &&
545 OPENSCOP_INT_zero_p(relation
->m
[k
][0]));
548 fprintf(file
, " ##");
556 * openscop_relation_print function:
557 * this function prints the content of an openscop_relation_t structure
558 * (*relation) into a file (file, possibly stdout) in the OpenScop format.
559 * \param[in] file File where informations are printed.
560 * \param[in] relation The relation whose information has to be printed.
561 * \param[in] names The textual names of the various elements.
562 * Set to NULL if printing comments is not needed.
564 void openscop_relation_print(FILE * file
,
565 openscop_relation_p relation
,
566 openscop_names_p names
) {
569 int printable_comments
;
570 openscop_relation_p r
;
572 if (relation
== NULL
) {
573 fprintf(file
, "# NULL relation\n");
577 printable_comments
= openscop_relation_printable_comments(relation
, names
);
579 // Count the number of parts in the union and print it if it is not 1.
588 openscop_relation_print_type(file
, relation
);
593 fprintf(file
, "# Union with %d parts\n%d\n", nb_parts
, nb_parts
);
595 // Print each part of the union.
596 for (part
= 1; part
<= nb_parts
; part
++) {
598 fprintf(file
, "# Union part No.%d\n", part
);
599 if ((relation
->nb_output_dims
== OPENSCOP_UNDEFINED
) &&
600 (relation
->nb_input_dims
== OPENSCOP_UNDEFINED
) &&
601 (relation
->nb_local_dims
== OPENSCOP_UNDEFINED
) &&
602 (relation
->nb_parameters
== OPENSCOP_UNDEFINED
))
603 fprintf(file
, "%d %d\n", relation
->nb_rows
, relation
->nb_columns
);
605 fprintf(file
, "%d %d %d %d %d %d\n",
606 relation
->nb_rows
, relation
->nb_columns
,
607 relation
->nb_output_dims
, relation
->nb_input_dims
,
608 relation
->nb_local_dims
, relation
->nb_parameters
);
610 for (i
= 0; i
< relation
->nb_rows
; i
++) {
611 for (j
= 0; j
< relation
->nb_columns
; j
++) {
612 OPENSCOP_INT_dump(file
, OPENSCOP_FMT
, relation
->m
[i
][j
]);
616 if (printable_comments
)
617 openscop_relation_print_comment(file
, relation
, i
, names
);
621 relation
= relation
->next
;
626 /*****************************************************************************
628 *****************************************************************************/
632 * openscop_relation_read_type function:
633 * this function reads a textual relation type and returns its integer
635 * \param[in] file The input stream.
636 * \return The relation type.
639 int openscop_relation_read_type(FILE * file
) {
644 strings
= openscop_util_strings_read(file
, &nb_strings
);
645 if (nb_strings
> 1) {
646 OPENSCOP_warning("uninterpreted information (after the relation type)");
649 OPENSCOP_error("no relation type");
651 if (!strcmp(strings
[0], OPENSCOP_STRING_UNDEFINED
)) {
652 type
= OPENSCOP_UNDEFINED
;
656 if (!strcmp(strings
[0], OPENSCOP_STRING_CONTEXT
)) {
657 type
= OPENSCOP_TYPE_CONTEXT
;
661 if (!strcmp(strings
[0], OPENSCOP_STRING_DOMAIN
)) {
662 type
= OPENSCOP_TYPE_DOMAIN
;
666 if (!strcmp(strings
[0], OPENSCOP_STRING_SCATTERING
)) {
667 type
= OPENSCOP_TYPE_SCATTERING
;
671 if (!strcmp(strings
[0], OPENSCOP_STRING_READ
)) {
672 type
= OPENSCOP_TYPE_READ
;
676 if (!strcmp(strings
[0], OPENSCOP_STRING_WRITE
)) {
677 type
= OPENSCOP_TYPE_WRITE
;
681 if (!strcmp(strings
[0], OPENSCOP_STRING_MAY_WRITE
)) {
682 type
= OPENSCOP_TYPE_MAY_WRITE
;
686 OPENSCOP_error("relation type not supported");
689 openscop_util_strings_free(strings
, nb_strings
);
695 * openscop_relation_read function:
696 * this function reads a relation into a file (foo, posibly stdin) and
697 * returns a pointer this relation.
698 * \param[in] file The input stream.
699 * \return A pointer to the relation structure that has been read.
701 openscop_relation_p
openscop_relation_read(FILE * foo
) {
702 int i
, j
, k
, n
, read
= 0;
703 int nb_rows
, nb_columns
;
704 int nb_output_dims
, nb_input_dims
, nb_local_dims
, nb_parameters
;
705 int nb_union_parts
= 1;
706 int may_read_nb_union_parts
= 1;
707 int read_properties
= 1;
710 char * c
, s
[OPENSCOP_MAX_STRING
], str
[OPENSCOP_MAX_STRING
];
711 openscop_relation_p relation
, relation_union
= NULL
, previous
= NULL
;
712 openscop_int_t
* p
= NULL
;
714 type
= openscop_relation_read_type(foo
);
716 // Read each part of the union (the number of parts may be updated inside)
717 for (k
= 0; k
< nb_union_parts
; k
++) {
718 // Read the number of union parts or the properties of the union part
719 while (read_properties
) {
722 // Read relation properties.
723 c
= openscop_util_skip_blank_and_comments(foo
, s
);
724 read
= sscanf(c
, " %d %d %d %d %d %d", &nb_rows
, &nb_columns
,
725 &nb_output_dims
, &nb_input_dims
,
726 &nb_local_dims
, &nb_parameters
);
728 if (((read
!= 1) && (read
!= 6)) ||
729 ((read
== 1) && (may_read_nb_union_parts
!= 1)))
730 OPENSCOP_error("not 1 or 6 integers on the first relation line");
733 // Only one number means a union and is the number of parts.
734 nb_union_parts
= nb_rows
;
735 if (nb_union_parts
< 1)
736 OPENSCOP_error("negative nb of union parts");
738 // Allow to read the properties of the first part of the union.
742 may_read_nb_union_parts
= 0;
745 // Allocate the union part and fill its properties.
746 relation
= openscop_relation_malloc(nb_rows
, nb_columns
);
747 relation
->type
= type
;
748 relation
->nb_output_dims
= nb_output_dims
;
749 relation
->nb_input_dims
= nb_input_dims
;
750 relation
->nb_local_dims
= nb_local_dims
;
751 relation
->nb_parameters
= nb_parameters
;
753 // Read the matrix of constraints.
754 if ((relation
->nb_rows
!= 0) && (relation
->nb_columns
!= 0))
757 for (i
= 0; i
< relation
->nb_rows
; i
++) {
758 c
= openscop_util_skip_blank_and_comments(foo
, s
);
760 OPENSCOP_error("not enough rows");
762 for (j
= 0; j
< relation
->nb_columns
; j
++) {
763 if (c
== NULL
|| *c
== '#' || *c
== '\n')
764 OPENSCOP_error("not enough columns");
765 if (sscanf(c
, "%s%n", str
, &n
) == 0)
766 OPENSCOP_error("not enough rows");
767 #if defined(OPENSCOP_INT_T_IS_MP)
769 if (sscanf(str
, "%lld", &val
) == 0)
770 OPENSCOP_error("failed to read an integer (in a relation)");
771 mpz_set_si(*p
++, val
);
773 if (sscanf(str
, OPENSCOP_FMT_TXT
, p
++) == 0)
774 OPENSCOP_error("failed to read an integer (in a relation)");
780 // Build the linked list of union parts.
782 relation_union
= relation
;
786 previous
->next
= relation
;
793 return relation_union
;
797 /*+***************************************************************************
798 * Memory allocation/deallocation function *
799 *****************************************************************************/
803 * openscop_relation_malloc function:
804 * this function allocates the memory space for a openscop_relation_t
805 * structure and sets its fields with default values. Then it returns a
806 * pointer to the allocated space.
807 * \param[in] nb_rows The number of row of the relation to allocate.
808 * \param[in] nb_columns The number of columns of the relation to allocate.
809 * \return A pointer to an empty relation with fields set to default values
810 * and a ready-to-use constraint matrix.
812 openscop_relation_p
openscop_relation_malloc(int nb_rows
, int nb_columns
) {
813 openscop_relation_p relation
;
814 openscop_int_t
** p
, * q
;
817 OPENSCOP_malloc(relation
, openscop_relation_p
, sizeof(openscop_relation_t
));
818 relation
->type
= OPENSCOP_UNDEFINED
;
819 relation
->nb_rows
= nb_rows
;
820 relation
->nb_columns
= nb_columns
;
821 relation
->nb_output_dims
= OPENSCOP_UNDEFINED
;
822 relation
->nb_input_dims
= OPENSCOP_UNDEFINED
;
823 relation
->nb_parameters
= OPENSCOP_UNDEFINED
;
824 relation
->nb_local_dims
= OPENSCOP_UNDEFINED
;
826 if ((nb_rows
== 0) || (nb_columns
== 0) ||
827 (nb_rows
== OPENSCOP_UNDEFINED
) || (nb_columns
== OPENSCOP_UNDEFINED
)) {
831 OPENSCOP_malloc(p
, openscop_int_t
**,
832 nb_rows
* sizeof(openscop_int_t
*));
833 OPENSCOP_malloc(q
, openscop_int_t
*,
834 nb_rows
* nb_columns
* sizeof(openscop_int_t
));
836 for (i
= 0; i
< nb_rows
; i
++) {
838 for (j
= 0; j
< nb_columns
; j
++)
839 OPENSCOP_INT_init_set_si(*(q
+j
),0);
844 relation
->next
= NULL
;
851 * openscop_relation_free_inside function:
852 * this function frees the allocated memory for the inside of a
853 * openscop_relation_t structure, i.e. only m.
854 * \param[in] relation The pointer to the relation we want to free internals.
856 void openscop_relation_free_inside(openscop_relation_p relation
) {
860 if (relation
== NULL
)
863 nb_elements
= relation
->nb_rows
* relation
->nb_columns
;
868 for (i
= 0; i
< nb_elements
; i
++)
869 OPENSCOP_INT_clear(*p
++);
871 if (relation
->m
!= NULL
) {
873 free(relation
->m
[0]);
880 * openscop_relation_free function:
881 * this function frees the allocated memory for a openscop_relation_t
883 * \param[in] relation The pointer to the relation we want to free.
885 void openscop_relation_free(openscop_relation_p relation
) {
886 openscop_relation_p tmp
;
888 if (relation
== NULL
)
891 while (relation
!= NULL
) {
892 tmp
= relation
->next
;
893 openscop_relation_free_inside(relation
);
900 /*+***************************************************************************
901 * Processing functions *
902 *****************************************************************************/
906 * openscop_relation_ncopy function:
907 * this functions builds and returns a "hard copy" (not a pointer copy) of a
908 * openscop_relation_t data structure such that the copy is restricted to the
909 * "n" first rows of the relation. This applies to all the parts in the case
910 * of a relation union.
911 * \param[in] relation The pointer to the relation we want to copy.
912 * \param[in] n The number of row of the relation we want to copy (the
913 * special value -1 means "all the rows").
914 * \return A pointer to the full copy of the relation union restricted to the
915 * first n rows of constraint matrix for each part of the union.
917 openscop_relation_p
openscop_relation_ncopy(openscop_relation_p relation
,
920 int first
= 1, all_rows
= 0;
921 openscop_relation_p copy
= NULL
, node
, previous
= NULL
;
926 while (relation
!= NULL
) {
928 n
= relation
->nb_rows
;
930 if (n
> relation
->nb_rows
)
931 OPENSCOP_error("not enough rows to copy in the relation");
933 node
= openscop_relation_malloc(n
, relation
->nb_columns
);
934 node
->type
= relation
->type
;
935 node
->nb_output_dims
= relation
->nb_output_dims
;
936 node
->nb_input_dims
= relation
->nb_input_dims
;
937 node
->nb_local_dims
= relation
->nb_local_dims
;
938 node
->nb_parameters
= relation
->nb_parameters
;
940 for (i
= 0; i
< n
; i
++)
941 for (j
= 0; j
< relation
->nb_columns
; j
++)
942 OPENSCOP_INT_assign(node
->m
[i
][j
], relation
->m
[i
][j
]);
950 previous
->next
= node
;
951 previous
= previous
->next
;
954 relation
= relation
->next
;
962 * openscop_relation_copy function:
963 * this function builds and returns a "hard copy" (not a pointer copy) of an
964 * openscop_relation_t data structure (the full union of relation).
965 * \param[in] relation The pointer to the relation we want to copy.
966 * \return A pointer to the copy of the union of relations.
968 openscop_relation_p
openscop_relation_copy(openscop_relation_p relation
) {
969 if (relation
== NULL
)
972 return openscop_relation_ncopy(relation
, -1);
977 * openscop_relation_replace_vector function:
978 * this function replaces the "row"^th row of a relation "relation" with the
979 * vector "vector". It directly updates the relation union part pointed
980 * by "relation" and this part only.
981 * \param[in,out] relation The relation we want to replace a row.
982 * \param[in] vector The vector that will replace a row of the relation.
983 * \param[in] row The row of the relation to be replaced.
985 void openscop_relation_replace_vector(openscop_relation_p relation
,
986 openscop_vector_p vector
, int row
) {
989 if ((relation
== NULL
) || (vector
== NULL
) ||
990 (relation
->nb_columns
!= vector
->size
) ||
991 (row
>= relation
->nb_rows
) || (row
< 0))
992 OPENSCOP_error("vector cannot replace relation row");
994 for (i
= 0; i
< vector
->size
; i
++)
995 OPENSCOP_INT_assign(relation
->m
[row
][i
], vector
->v
[i
]);
1000 * openscop_relation_add_vector function:
1001 * this function adds (meaning, +) a vector to the "row"^th row of a
1002 * relation "relation". It directly updates the relation union part pointed
1003 * by "relation" and this part only.
1004 * \param[in,out] relation The relation we want to add a vector to a row.
1005 * \param[in] vector The vector that will replace a row of the relation.
1006 * \param[in] row The row of the relation to be replaced.
1008 void openscop_relation_add_vector(openscop_relation_p relation
,
1009 openscop_vector_p vector
, int row
) {
1012 if ((relation
== NULL
) || (vector
== NULL
) ||
1013 (relation
->nb_columns
!= vector
->size
) ||
1014 (row
>= relation
->nb_rows
) || (row
< 0))
1015 OPENSCOP_error("vector cannot be added to relation");
1017 if (OPENSCOP_INT_get_si(relation
->m
[row
][0]) == 0)
1018 OPENSCOP_INT_assign(relation
->m
[row
][0], vector
->v
[0]);
1020 for (i
= 1; i
< vector
->size
; i
++)
1021 OPENSCOP_INT_addto(relation
->m
[row
][i
], relation
->m
[row
][i
], vector
->v
[i
]);
1026 * openscop_relation_sub_vector function:
1027 * this function subtracts the vector "vector" to the "row"^th row of
1028 * a relation "relation. It directly updates the relation union part pointed
1029 * by "relation" and this part only.
1030 * \param[in,out] relation The relation where to subtract a vector to a row.
1031 * \param[in] vector The vector to subtract to a relation row.
1032 * \param[in] row The row of the relation to subtract the vector.
1034 void openscop_relation_sub_vector(openscop_relation_p relation
,
1035 openscop_vector_p vector
, int row
) {
1038 if ((relation
== NULL
) || (vector
== NULL
) ||
1039 (relation
->nb_columns
!= vector
->size
) ||
1040 (row
>= relation
->nb_rows
) || (row
< 0))
1041 OPENSCOP_error("vector cannot be subtracted to row");
1043 if (OPENSCOP_INT_get_si(relation
->m
[row
][0]) == 0)
1044 OPENSCOP_INT_assign(relation
->m
[row
][0], vector
->v
[0]);
1046 for (i
= 1; i
< vector
->size
; i
++)
1047 OPENSCOP_INT_subtract(relation
->m
[row
][i
], relation
->m
[row
][i
], vector
->v
[i
]);
1052 * openscop_relation_insert_vector function:
1053 * this function inserts a new row corresponding to the vector "vector" to
1054 * the relation "relation" by inserting it at the "row"^th row. It directly
1055 * updates the relation union part pointed by "relation" and this part only.
1056 * If "vector" (or "relation") is NULL, the relation is left unmodified.
1057 * \param[in,out] relation The relation we want to extend.
1058 * \param[in] vector The vector that will be added relation.
1059 * \param[in] row The row where to insert the vector.
1061 void openscop_relation_insert_vector(openscop_relation_p relation
,
1062 openscop_vector_p vector
, int row
) {
1063 openscop_relation_p temp
;
1065 temp
= openscop_relation_from_vector(vector
);
1066 openscop_relation_insert_constraints(relation
, temp
, row
);
1067 openscop_relation_free(temp
);
1072 * openscop_relation_from_vector function:
1073 * this function converts a vector "vector" to a relation with a single row
1074 * and returns a pointer to that relation.
1075 * \param[in] vector The vector to convert to a relation.
1076 * \return A pointer to a relation resulting from the vector conversion.
1078 openscop_relation_p
openscop_relation_from_vector(openscop_vector_p vector
) {
1079 openscop_relation_p relation
;
1084 relation
= openscop_relation_malloc(1, vector
->size
);
1085 openscop_relation_replace_vector(relation
, vector
, 0);
1091 * openscop_relation_replace_constraints function:
1092 * this function replaces some rows of a relation "r1" with the rows of
1093 * the relation "r2". It begins at the "row"^th row of "r1". It directly
1094 * updates the relation union part pointed by "r1" and this part only.
1095 * \param[in,out] r1 The relation we want to change some rows.
1096 * \param[in] r2 The relation containing the new rows.
1097 * \param[in] row The first row of the relation r1 to be replaced.
1099 void openscop_relation_replace_constraints(openscop_relation_p r1
,
1100 openscop_relation_p r2
, int row
) {
1103 if ((r1
== NULL
) || (r2
== NULL
) ||
1104 (r1
->nb_columns
!= r1
->nb_columns
) ||
1105 ((row
+ r2
->nb_rows
) > r1
->nb_rows
) || (row
< 0))
1106 OPENSCOP_error("relation rows could not be replaced");
1108 for (i
= 0; i
< r2
->nb_rows
; i
++)
1109 for (j
= 0; j
< r2
->nb_columns
; j
++)
1110 OPENSCOP_INT_assign(r1
->m
[i
+row
][j
], r2
->m
[i
][j
]);
1115 * openscop_relation_insert_constraints function:
1116 * this function adds new rows corresponding to the relation "r1" to
1117 * the relation "r2" by inserting it at the "row"^th row. It directly
1118 * updates the relation union part pointed by "r1" and this part only.
1119 * If "r2" (or "r1") is NULL, the relation is left unmodified.
1120 * \param[in,out] r1 The relation we want to extend.
1121 * \param[in] r2 The relation to be inserted.
1122 * \param[in] row The row where to insert the relation
1124 void openscop_relation_insert_constraints(openscop_relation_p r1
,
1125 openscop_relation_p r2
, int row
) {
1127 openscop_relation_p temp
;
1129 if ((r1
== NULL
) || (r2
== NULL
))
1132 if ((r1
->nb_columns
!= r2
->nb_columns
) ||
1133 (row
> r1
->nb_rows
) || (row
< 0))
1134 OPENSCOP_error("constraints cannot be inserted");
1136 // We use a temporary relation just to reuse existing functions. Cleaner.
1137 temp
= openscop_relation_malloc(r1
->nb_rows
+r2
->nb_rows
, r1
->nb_columns
);
1139 for (i
= 0; i
< row
; i
++)
1140 for (j
= 0; j
< r1
->nb_columns
; j
++)
1141 OPENSCOP_INT_assign(temp
->m
[i
][j
], r1
->m
[i
][j
]);
1143 openscop_relation_replace_constraints(temp
, r2
, row
);
1145 for (i
= row
+ r2
->nb_rows
; i
< r2
->nb_rows
+ r1
->nb_rows
; i
++)
1146 for (j
= 0; j
< r1
->nb_columns
; j
++)
1147 OPENSCOP_INT_assign(temp
->m
[i
][j
], r1
->m
[i
-r2
->nb_rows
][j
]);
1149 openscop_relation_free_inside(r1
);
1151 // Replace the inside of relation.
1152 r1
->nb_rows
= temp
->nb_rows
;
1155 // Free the temp "shell".
1161 * openscop_relation_concat_constraints function:
1162 * this function builds a new relation from two relations sent as
1163 * parameters. The new set of constraints is built as the concatenation
1164 * of the rows of the first elements of the two relation unions r1 and r2.
1165 * This means, there is no next field in the result.
1166 * \param[in] r1 The first relation.
1167 * \param[in] r2 The second relation.
1168 * \return A pointer to the relation resulting from the concatenation of
1169 * the first elements of r1 and r2.
1171 openscop_relation_p
openscop_relation_concat_constraints(
1172 openscop_relation_p r1
,
1173 openscop_relation_p r2
) {
1174 openscop_relation_p
new;
1177 return openscop_relation_copy(r2
);
1180 return openscop_relation_copy(r1
);
1182 if (r1
->nb_columns
!= r2
->nb_columns
)
1183 OPENSCOP_error("incompatible sizes for concatenation");
1185 if (r1
->next
|| r2
->next
)
1186 OPENSCOP_warning("relation concatenation is done on the first elements "
1189 new = openscop_relation_malloc(r1
->nb_rows
+r2
->nb_rows
, r1
->nb_columns
);
1190 openscop_relation_replace_constraints(new, r1
, 0);
1191 openscop_relation_replace_constraints(new, r2
, r1
->nb_rows
);
1198 * openscop_relation_equal function:
1199 * this function returns true if the two relations provided as parameters
1200 * are the same, false otherwise.
1201 * \param[in] r1 The first relation.
1202 * \param[in] r2 The second relation.
1203 * \return 1 if r1 and r2 are the same (content-wise), 0 otherwise.
1205 int openscop_relation_equal(openscop_relation_p r1
, openscop_relation_p r2
) {
1208 while ((r1
!= NULL
) && (r2
!= NULL
)) {
1212 if ((r1
->type
!= r2
->type
) ||
1213 (r1
->nb_rows
!= r2
->nb_rows
) ||
1214 (r1
->nb_columns
!= r2
->nb_columns
) ||
1215 (r1
->nb_output_dims
!= r2
->nb_output_dims
) ||
1216 (r1
->nb_input_dims
!= r2
->nb_input_dims
) ||
1217 (r1
->nb_local_dims
!= r2
->nb_local_dims
) ||
1218 (r1
->nb_parameters
!= r2
->nb_parameters
))
1221 for (i
= 0; i
< r1
->nb_rows
; ++i
)
1222 for (j
= 0; j
< r1
->nb_columns
; ++j
)
1223 if (OPENSCOP_INT_ne(r1
->m
[i
][j
], r2
->m
[i
][j
]))
1230 if (((r1
== NULL
) && (r2
!= NULL
)) || ((r1
!= NULL
) && (r2
== NULL
)))
1238 * openscop_relation_check_attribute internal function:
1239 * This function checks whether an "actual" value is the same as an
1240 * "expected" value or not. If the expected value is set to
1241 * OPENSCOP_UNDEFINED, this function sets it to the "actual" value
1242 * and do not report a difference has been detected.
1243 * It returns 0 if a difference has been detected, 1 otherwise.
1244 * \param[in,out] expected Pointer to the expected value (the value is
1245 * modified if it was set to OPENSCOP_UNDEFINED).
1246 * \param[in] actual Value we want to check.
1247 * \return 0 if the values are not the same while the expected value was
1248 * not OPENSCOP_UNDEFINED, 1 otherwise.
1251 int openscop_relation_check_attribute(int * expected
, int actual
) {
1252 if (*expected
!= OPENSCOP_UNDEFINED
) {
1253 if ((actual
!= OPENSCOP_UNDEFINED
) &&
1254 (actual
!= *expected
)) {
1255 OPENSCOP_warning("unexpected atribute");
1268 * openscop_relation_check_nb_columns internal function:
1269 * This function checks that the number of columns of a relation
1270 * corresponds to some expected properties (setting an expected property to
1271 * OPENSCOP_UNDEFINED makes this function unable to detect a problem).
1272 * It returns 0 if the number of columns seems incorrect or 1 if no problem
1273 * has been detected.
1274 * \param[in] relation The relation we want to check the number of columns.
1275 * \param[in] expected_nb_output_dims Expected number of output dimensions.
1276 * \param[in] expected_nb_input_dims Expected number of input dimensions.
1277 * \param[in] expected_nb_parameters Expected number of parameters.
1278 * \return 0 if the number of columns seems incorrect, 1 otherwise.
1281 int openscop_relation_check_nb_columns(openscop_relation_p relation
,
1282 int expected_nb_output_dims
,
1283 int expected_nb_input_dims
,
1284 int expected_nb_parameters
) {
1285 int expected_nb_local_dims
, expected_nb_columns
;
1287 if ((expected_nb_output_dims
!= OPENSCOP_UNDEFINED
) &&
1288 (expected_nb_input_dims
!= OPENSCOP_UNDEFINED
) &&
1289 (expected_nb_parameters
!= OPENSCOP_UNDEFINED
)) {
1291 if (relation
->nb_local_dims
== OPENSCOP_UNDEFINED
)
1292 expected_nb_local_dims
= 0;
1294 expected_nb_local_dims
= relation
->nb_local_dims
;
1296 expected_nb_columns
= expected_nb_output_dims
+
1297 expected_nb_input_dims
+
1298 expected_nb_local_dims
+
1299 expected_nb_parameters
+
1302 if (expected_nb_columns
!= relation
->nb_columns
) {
1303 OPENSCOP_warning("unexpected number of columns");
1313 * openscop_relation_integrity_check function:
1314 * this function checks that a relation is "well formed" according to some
1315 * expected properties (setting an expected value to OPENSCOP_UNDEFINED means
1316 * that we do not expect a specific value) and what the relation is supposed
1317 * to represent. It returns 0 if the check failed or 1 if no problem has been
1319 * \param[in] relation The relation we want to check.
1320 * \param[in] type Semantics about this relation (domain, access...).
1321 * \param[in] expected_nb_output_dims Expected number of output dimensions.
1322 * \param[in] expected_nb_input_dims Expected number of input dimensions.
1323 * \param[in] expected_nb_parameters Expected number of parameters.
1324 * \return 0 if the integrity check fails, 1 otherwise.
1326 int openscop_relation_integrity_check(openscop_relation_p relation
,
1328 int expected_nb_output_dims
,
1329 int expected_nb_input_dims
,
1330 int expected_nb_parameters
) {
1333 // Check the NULL case.
1334 if (relation
== NULL
) {
1335 if ((expected_nb_output_dims
!= OPENSCOP_UNDEFINED
) ||
1336 (expected_nb_input_dims
!= OPENSCOP_UNDEFINED
) ||
1337 (expected_nb_parameters
!= OPENSCOP_UNDEFINED
)) {
1338 OPENSCOP_warning("NULL relation with some expected attibutes");
1346 if (((expected_type
!= OPENSCOP_TYPE_ACCESS
) &&
1347 (expected_type
!= relation
->type
)) ||
1348 ((expected_type
== OPENSCOP_TYPE_ACCESS
) &&
1349 (!openscop_relation_is_access(relation
)))) {
1350 OPENSCOP_warning("wrong type");
1351 openscop_relation_dump(stderr
, relation
);
1355 // Check that relations have no undefined atributes.
1356 if ((relation
->nb_output_dims
== OPENSCOP_UNDEFINED
) ||
1357 (relation
->nb_input_dims
== OPENSCOP_UNDEFINED
) ||
1358 (relation
->nb_local_dims
== OPENSCOP_UNDEFINED
) ||
1359 (relation
->nb_parameters
== OPENSCOP_UNDEFINED
)) {
1360 OPENSCOP_warning("all attributes should be defined");
1361 openscop_relation_dump(stderr
, relation
);
1365 // Check that a context has actually 0 output dimensions.
1366 if ((relation
->type
== OPENSCOP_TYPE_CONTEXT
) &&
1367 (relation
->nb_output_dims
!= 0)) {
1368 OPENSCOP_warning("context without 0 as number of output dimensions");
1369 openscop_relation_dump(stderr
, relation
);
1373 // Check that a domain or a context has actually 0 input dimensions.
1374 if (((relation
->type
== OPENSCOP_TYPE_DOMAIN
) ||
1375 (relation
->type
== OPENSCOP_TYPE_CONTEXT
)) &&
1376 (relation
->nb_input_dims
!= 0)) {
1377 OPENSCOP_warning("domain or context without 0 input dimensions");
1378 openscop_relation_dump(stderr
, relation
);
1382 // Check properties according to expected values (and if expected values
1383 // are undefined, define them with the first relation part properties).
1384 if (!openscop_relation_check_attribute(&expected_nb_output_dims
,
1385 relation
->nb_output_dims
) ||
1386 !openscop_relation_check_attribute(&expected_nb_input_dims
,
1387 relation
->nb_input_dims
) ||
1388 !openscop_relation_check_attribute(&expected_nb_parameters
,
1389 relation
->nb_parameters
)) {
1390 openscop_relation_dump(stderr
, relation
);
1394 while (relation
!= NULL
) {
1396 // Attributes (except the number of local dimensions) should be the same
1397 // in all parts of the union.
1398 if ((expected_nb_output_dims
!= relation
->nb_output_dims
) ||
1399 (expected_nb_input_dims
!= relation
->nb_input_dims
) ||
1400 (expected_nb_parameters
!= relation
->nb_parameters
)) {
1401 OPENSCOP_warning("inconsistent attributes");
1402 openscop_relation_dump(stderr
, relation
);
1406 // Check whether the number of columns is OK or not.
1407 if (!openscop_relation_check_nb_columns(relation
,
1408 expected_nb_output_dims
,
1409 expected_nb_input_dims
,
1410 expected_nb_parameters
)) {
1411 openscop_relation_dump(stderr
, relation
);
1415 // Check the first column. The first column of a relation part should be
1416 // made of 0 or 1 only.
1417 if ((relation
->nb_rows
> 0) && (relation
->nb_columns
> 0)) {
1418 for (i
= 0; i
< relation
->nb_rows
; i
++) {
1419 if (!OPENSCOP_INT_zero_p(relation
->m
[i
][0]) &&
1420 !OPENSCOP_INT_one_p(relation
->m
[i
][0])) {
1421 OPENSCOP_warning("first column of a relation is not "
1422 "strictly made of 0 or 1");
1423 openscop_relation_dump(stderr
, relation
);
1429 // Array accesses must provide the array identifier.
1430 if ((openscop_relation_is_access(relation
)) &&
1431 (openscop_relation_get_array_id(relation
) == OPENSCOP_UNDEFINED
)) {
1432 openscop_relation_dump(stderr
, relation
);
1436 relation
= relation
->next
;
1444 * openscop_relation_union function:
1445 * this function builds a new relation from two relations provided
1446 * as parameters. The new relation is built as an union of the
1447 * two relations: the list of constraint sets are linked together.
1448 * \param[in] r1 The first relation.
1449 * \param[in] r2 The second relation.
1450 * \return A new relation corresponding to the union of r1 and r2.
1452 openscop_relation_p
openscop_relation_union(openscop_relation_p r1
,
1453 openscop_relation_p r2
) {
1454 openscop_relation_p copy1
, copy2
, tmp
;
1456 if ((r1
== NULL
) && (r2
== NULL
))
1459 copy1
= openscop_relation_copy(r1
);
1460 copy2
= openscop_relation_copy(r2
);
1462 if ((r1
!= NULL
) && (r2
== NULL
))
1465 if ((r1
== NULL
) && (r2
!= NULL
))
1469 while (tmp
->next
!= NULL
)
1478 * openscop_relation_set_type function:
1479 * this function sets the type of each relation union part in the relation
1480 * to the one provided as parameter.
1481 * \param relation The relation to set the type.
1482 * \param type The type.
1484 void openscop_relation_set_type(openscop_relation_p relation
, int type
) {
1486 while (relation
!= NULL
) {
1487 relation
->type
= type
;
1488 relation
= relation
->next
;
1494 * openscop_relation_get_array_id function:
1495 * this function returns the array identifier in a relation with access type
1496 * It returns OPENSCOP_UNDEFINED if it is not able to find it (in particular
1497 * if there are irregularities in the relation).
1498 * \param[in] relation The relation where to find an array identifier.
1499 * \return The array identifier in the relation or OPENSCOP_UNDEFINED.
1501 int openscop_relation_get_array_id(openscop_relation_p relation
) {
1504 int array_id
= OPENSCOP_UNDEFINED
;
1505 int reference_array_id
= OPENSCOP_UNDEFINED
;
1509 if (relation
== NULL
)
1510 return OPENSCOP_UNDEFINED
;
1512 if (!openscop_relation_is_access(relation
)) {
1513 OPENSCOP_warning("asked for an array id of non-array relation");
1514 return OPENSCOP_UNDEFINED
;
1517 while (relation
!= NULL
) {
1518 // There should be room to store the array identifier.
1519 if ((relation
->nb_rows
< 1) ||
1520 (relation
->nb_columns
< 3)) {
1521 OPENSCOP_warning("no array identifier in an access function");
1522 return OPENSCOP_UNDEFINED
;
1525 // Array identifiers are m[i][#columns -1] / m[i][1], with i the only row
1526 // where m[i][1] is not 0.
1527 // - check there is exactly one row such that m[i][1] is not 0,
1528 // - check the whole ith row if full of 0 except m[i][1] and the id,
1529 // - check that (m[i][#columns -1] % m[i][1]) == 0,
1530 // - check that (-m[i][#columns -1] / m[i][1]) > 0.
1532 for (i
= 0; i
< relation
->nb_rows
; i
++) {
1533 if (!OPENSCOP_INT_zero_p(relation
->m
[i
][1])) {
1538 if (nb_array_id
== 0) {
1539 OPENSCOP_warning("no array identifier in an access function");
1540 return OPENSCOP_UNDEFINED
;
1542 if (nb_array_id
> 1) {
1543 OPENSCOP_warning("several array identifiers in one access function");
1544 return OPENSCOP_UNDEFINED
;
1546 for (i
= 0; i
< relation
->nb_columns
- 1; i
++) {
1547 if ((i
!= 1) && !OPENSCOP_INT_zero_p(relation
->m
[row_id
][i
])) {
1548 OPENSCOP_warning("non integer array identifier");
1549 return OPENSCOP_UNDEFINED
;
1552 if (!OPENSCOP_INT_divisible(relation
->m
[row_id
][relation
->nb_columns
- 1],
1553 relation
->m
[row_id
][1])) {
1554 OPENSCOP_warning("rational array identifier");
1555 return OPENSCOP_UNDEFINED
;
1557 array_id
= -OPENSCOP_INT_get_si(relation
->m
[row_id
][relation
->nb_columns
-1]);
1558 array_id
/= OPENSCOP_INT_get_si(relation
->m
[row_id
][1]);
1559 if (array_id
<= 0) {
1560 OPENSCOP_warning("negative or 0 identifier in access function");
1561 return OPENSCOP_UNDEFINED
;
1564 // Unions of accesses are allowed, but they should refer at the same array.
1566 reference_array_id
= array_id
;
1570 if (reference_array_id
!= array_id
) {
1571 OPENSCOP_warning("inconsistency of array identifiers in an "
1572 "union of access relations");
1573 return OPENSCOP_UNDEFINED
;
1577 relation
= relation
->next
;
1585 * openscop_relation_is_access function:
1586 * this function returns 1 if the relation corresponds to an access relation,
1587 * whatever its precise type (read, write etc.), 0 otherwise.
1588 * \param relation The relation to check wheter it is an access relation or not.
1589 * \return 1 if the relation is an access relation, 0 otherwise.
1591 int openscop_relation_is_access(openscop_relation_p relation
) {
1593 if (relation
== NULL
)
1596 if ((relation
->type
== OPENSCOP_TYPE_ACCESS
) ||
1597 (relation
->type
== OPENSCOP_TYPE_READ
) ||
1598 (relation
->type
== OPENSCOP_TYPE_WRITE
) ||
1599 (relation
->type
== OPENSCOP_TYPE_MAY_WRITE
))