Rename functions working on constraints
[openscop.git] / source / relation.c
blob4cfdd2bd94815467843fffc41a93bc9687bdcb37
2 /*+-----------------------------------------------------------------**
3 ** OpenScop Library **
4 **-----------------------------------------------------------------**
5 ** relation.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 *****************************************************************************/
64 # include <stdlib.h>
65 # include <stdio.h>
66 # include <string.h>
67 # include <ctype.h>
68 # include <openscop/relation.h>
71 /*+***************************************************************************
72 * Structure display function *
73 *****************************************************************************/
76 /**
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.
83 static
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);
90 break;
92 case OPENSCOP_TYPE_CONTEXT: {
93 fprintf(file, OPENSCOP_STRING_CONTEXT);
94 break;
96 case OPENSCOP_TYPE_DOMAIN: {
97 fprintf(file, OPENSCOP_STRING_DOMAIN);
98 break;
100 case OPENSCOP_TYPE_SCATTERING: {
101 fprintf(file, OPENSCOP_STRING_SCATTERING);
102 break;
104 case OPENSCOP_TYPE_READ: {
105 fprintf(file, OPENSCOP_STRING_READ);
106 break;
108 case OPENSCOP_TYPE_WRITE: {
109 fprintf(file, OPENSCOP_STRING_WRITE);
110 break;
112 case OPENSCOP_TYPE_MAY_WRITE: {
113 fprintf(file, OPENSCOP_STRING_MAY_WRITE);
114 break;
116 default: {
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,
138 int level) {
139 int i, j, first = 1;
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");
150 else {
151 fprintf(file, "+-- NULL relation\n");
154 while (relation != NULL) {
155 if (! first) {
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");
163 else
164 first = 0;
166 // A blank line
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");
179 fprintf(file, "[ ");
181 for (j = 0; j < relation->nb_columns; j++) {
182 OPENSCOP_INT_dump(file, OPENSCOP_FMT, relation->m[i][j]);
183 fprintf(file, " ");
186 fprintf(file, "]\n");
189 relation = relation->next;
191 // Next line.
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");
202 // The last line.
203 for (j = 0; j <= level; j++)
204 fprintf(file, "|\t");
205 fprintf(file, "\n");
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,
230 * 0 otherwise.
231 * \param[in] name String containing the name of the element.
232 * \return A string that contains the printing of a value.
234 static
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));
241 body[0] = '\0';
242 sval[0] = '\0';
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);
250 else {
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);
257 strcat(sval, temp);
260 *first = 0;
262 else {
263 if (OPENSCOP_INT_one_p(val)) {
264 sprintf(sval, "+%s", name);
266 else {
267 sprintf(sval, "+");
268 OPENSCOP_INT_sprint(temp, OPENSCOP_FMT_TXT, val);
269 strcat(sval, temp);
270 sprintf(temp, "*%s", name);
271 strcat(sval, temp);
275 else {
276 if (cst) {
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)) {
280 if (!(*first)) {
281 OPENSCOP_INT_sprint(sval, "+"OPENSCOP_FMT_TXT, val); // Block macro !
283 else {
284 OPENSCOP_INT_sprint(sval, OPENSCOP_FMT_TXT, val);
289 free(temp);
290 free(body);
292 return(sval);
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) {
308 int i, first = 1;
309 char * sval;
310 char * sline = (char *)malloc(OPENSCOP_MAX_STRING * sizeof(char));
311 sline[0] = '\0';
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]);
317 strcat(sline, sval);
318 free(sval);
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]);
327 strcat(sline, sval);
328 free(sval);
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;
334 i++) {
335 sval = openscop_relation_expression_element(
336 relation->m[row][i], &first, 0,
337 names->parameters[i - names->nb_iterators - names->nb_localdims - 1]);
338 strcat(sline, sval);
339 free(sval);
342 // Finally the constant part (yes, I reused it).
343 sval = openscop_relation_expression_element(relation->m[row][i],
344 &first, 1, NULL);
345 strcat(sline, sval);
346 free(sval);
348 return sline;
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
360 * correct.
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.
368 static
369 void openscop_relation_properties(openscop_relation_p relation,
370 int * nb_parameters,
371 int * nb_iterators,
372 int * nb_scattdims,
373 int * nb_localdims,
374 int * array_id) {
376 int type;
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)
385 return;
387 if (openscop_relation_is_access(relation))
388 type = OPENSCOP_TYPE_ACCESS;
389 else
390 type = relation->type;
392 // There is some redundancy but I believe the code is cleaner this way.
393 switch (type) {
394 case OPENSCOP_TYPE_CONTEXT: {
395 *nb_parameters = relation->nb_parameters;
396 *nb_iterators = 0;
397 *nb_scattdims = 0;
398 *nb_localdims = relation->nb_local_dims;
399 *array_id = 0;
400 break;
402 case OPENSCOP_TYPE_DOMAIN: {
403 *nb_parameters = relation->nb_parameters;
404 *nb_iterators = relation->nb_output_dims;
405 *nb_scattdims = 0;
406 *nb_localdims = relation->nb_local_dims;
407 *array_id = 0;
408 break;
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;
415 *array_id = 0;
416 break;
418 case OPENSCOP_TYPE_ACCESS: {
419 *nb_parameters = relation->nb_parameters;
420 *nb_iterators = relation->nb_input_dims;
421 *nb_scattdims = 0;
422 *nb_localdims = relation->nb_local_dims;
423 *array_id = openscop_relation_get_array_id(relation);
424 break;
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.
438 static
439 int openscop_relation_printable_comments(openscop_relation_p relation,
440 openscop_names_p names) {
441 int nb_parameters;
442 int nb_iterators;
443 int nb_scattdims;
444 int nb_localdims;
445 int array_id;
447 if ((relation == NULL) || (names == NULL))
448 return 0;
450 // TODO: remove this !!!
451 // Temporarily deactivate comments, to finish OpenScop RFC first.
452 return 0;
454 // We cannot print comments if the names are not textual.
455 if (names->textual != 1)
456 return 0;
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))
462 return 0;
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");
482 return 0;
485 return 1;
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.
500 static
501 void openscop_relation_print_comment(FILE * file,
502 openscop_relation_p relation, int row,
503 openscop_names_p names) {
504 int k;
505 int type;
506 char * expression;
508 if (openscop_relation_is_access(relation))
509 type = OPENSCOP_TYPE_ACCESS;
510 else
511 type = relation->type;
513 switch (type) {
514 case OPENSCOP_TYPE_DOMAIN: {
515 expression = openscop_relation_expression(relation, row, names);
516 fprintf(file, " ## %s", expression);
517 free(expression);
518 if (OPENSCOP_INT_zero_p(relation->m[row][0]))
519 fprintf(file, " == 0");
520 else
521 fprintf(file, " >= 0");
522 break;
524 case OPENSCOP_TYPE_SCATTERING: {
525 expression = openscop_relation_expression(relation, row, names);
526 fprintf(file, " ## %s", expression);
527 free(expression);
528 break;
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]);
537 k = row;
538 do {
539 expression = openscop_relation_expression(relation, k, names);
540 fprintf(file, "[%s]", expression);
541 free(expression);
542 k++;
544 while ((k < relation->nb_rows) &&
545 OPENSCOP_INT_zero_p(relation->m[k][0]));
547 else {
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) {
567 int i, j;
568 int part, nb_parts;
569 int printable_comments;
570 openscop_relation_p r;
572 if (relation == NULL) {
573 fprintf(file, "# NULL relation\n");
574 return;
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.
580 r = relation;
581 nb_parts = 0;
582 while (r != NULL) {
583 nb_parts++;
584 r = r->next;
587 if (nb_parts > 0) {
588 openscop_relation_print_type(file, relation);
589 fprintf(file, "\n");
592 if (nb_parts > 1)
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++) {
597 if (nb_parts > 1)
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);
604 else
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]);
613 fprintf(file, " ");
616 if (printable_comments)
617 openscop_relation_print_comment(file, relation, i, names);
619 fprintf(file, "\n");
621 relation = relation->next;
626 /*****************************************************************************
627 * Reading function *
628 *****************************************************************************/
632 * openscop_relation_read_type function:
633 * this function reads a textual relation type and returns its integer
634 * counterpart.
635 * \param[in] file The input stream.
636 * \return The relation type.
638 static
639 int openscop_relation_read_type(FILE * file) {
640 int nb_strings;
641 int type;
642 char ** strings;
644 strings = openscop_util_strings_read(file, &nb_strings);
645 if (nb_strings > 1) {
646 OPENSCOP_warning("uninterpreted information (after the relation type)");
648 if (nb_strings == 0)
649 OPENSCOP_error("no relation type");
651 if (!strcmp(strings[0], OPENSCOP_STRING_UNDEFINED)) {
652 type = OPENSCOP_UNDEFINED;
653 goto return_type;
656 if (!strcmp(strings[0], OPENSCOP_STRING_CONTEXT)) {
657 type = OPENSCOP_TYPE_CONTEXT;
658 goto return_type;
661 if (!strcmp(strings[0], OPENSCOP_STRING_DOMAIN)) {
662 type = OPENSCOP_TYPE_DOMAIN;
663 goto return_type;
666 if (!strcmp(strings[0], OPENSCOP_STRING_SCATTERING)) {
667 type = OPENSCOP_TYPE_SCATTERING;
668 goto return_type;
671 if (!strcmp(strings[0], OPENSCOP_STRING_READ)) {
672 type = OPENSCOP_TYPE_READ;
673 goto return_type;
676 if (!strcmp(strings[0], OPENSCOP_STRING_WRITE)) {
677 type = OPENSCOP_TYPE_WRITE;
678 goto return_type;
681 if (!strcmp(strings[0], OPENSCOP_STRING_MAY_WRITE)) {
682 type = OPENSCOP_TYPE_MAY_WRITE;
683 goto return_type;
686 OPENSCOP_error("relation type not supported");
688 return_type:
689 openscop_util_strings_free(strings, nb_strings);
690 return type;
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;
708 int first = 1;
709 int type;
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) {
720 read_properties = 0;
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");
732 if (read == 1) {
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.
739 read_properties = 1;
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))
755 p = relation->m[0];
757 for (i = 0; i < relation->nb_rows; i++) {
758 c = openscop_util_skip_blank_and_comments(foo, s);
759 if (c == NULL)
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)
768 long long val;
769 if (sscanf(str, "%lld", &val) == 0)
770 OPENSCOP_error("failed to read an integer (in a relation)");
771 mpz_set_si(*p++, val);
772 #else
773 if (sscanf(str, OPENSCOP_FMT_TXT, p++) == 0)
774 OPENSCOP_error("failed to read an integer (in a relation)");
775 #endif
776 c += n;
780 // Build the linked list of union parts.
781 if (first == 1) {
782 relation_union = relation;
783 first = 0;
785 else {
786 previous->next = relation;
789 previous = relation;
790 read_properties = 1;
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;
815 int i, j;
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)) {
828 relation->m = NULL;
830 else {
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));
835 relation->m = p;
836 for (i = 0; i < nb_rows; i++) {
837 *p++ = q;
838 for (j = 0; j < nb_columns; j++)
839 OPENSCOP_INT_init_set_si(*(q+j),0);
840 q += nb_columns;
844 relation->next = NULL;
846 return relation;
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) {
857 int i, nb_elements;
858 openscop_int_t * p;
860 if (relation == NULL)
861 return;
863 nb_elements = relation->nb_rows * relation->nb_columns;
865 if (nb_elements > 0)
866 p = relation->m[0];
868 for (i = 0; i < nb_elements; i++)
869 OPENSCOP_INT_clear(*p++);
871 if (relation->m != NULL) {
872 if (nb_elements > 0)
873 free(relation->m[0]);
874 free(relation->m);
880 * openscop_relation_free function:
881 * this function frees the allocated memory for a openscop_relation_t
882 * structure.
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)
889 return;
891 while (relation != NULL) {
892 tmp = relation->next;
893 openscop_relation_free_inside(relation);
894 free(relation);
895 relation = tmp;
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,
918 int n) {
919 int i, j;
920 int first = 1, all_rows = 0;
921 openscop_relation_p copy = NULL, node, previous = NULL;
923 if (n == -1)
924 all_rows = 1;
926 while (relation != NULL) {
927 if (all_rows)
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]);
944 if (first) {
945 first = 0;
946 copy = node;
947 previous = node;
949 else {
950 previous->next = node;
951 previous = previous->next;
954 relation = relation->next;
957 return copy;
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)
970 return 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) {
987 int i;
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) {
1010 int i;
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) {
1036 int i;
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;
1081 if (vector == NULL)
1082 return NULL;
1084 relation = openscop_relation_malloc(1, vector->size);
1085 openscop_relation_replace_vector(relation, vector, 0);
1086 return relation;
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) {
1101 int i, j;
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) {
1126 int i, j;
1127 openscop_relation_p temp;
1129 if ((r1 == NULL) || (r2 == NULL))
1130 return;
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;
1153 r1->m = temp->m;
1155 // Free the temp "shell".
1156 free(temp);
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;
1176 if (r1 == NULL)
1177 return openscop_relation_copy(r2);
1179 if (r2 == NULL)
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 "
1187 "of union only");
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);
1193 return new;
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) {
1206 int i, j;
1208 while ((r1 != NULL) && (r2 != NULL)) {
1209 if (r1 == r2)
1210 return 1;
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))
1219 return 0;
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]))
1224 return 0;
1226 r1 = r1->next;
1227 r2 = r2->next;
1230 if (((r1 == NULL) && (r2 != NULL)) || ((r1 != NULL) && (r2 == NULL)))
1231 return 0;
1233 return 1;
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.
1250 static
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");
1256 return 0;
1259 else {
1260 *expected = actual;
1263 return 1;
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.
1280 static
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;
1293 else
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");
1304 return 0;
1308 return 1;
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
1318 * detected.
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,
1327 int expected_type,
1328 int expected_nb_output_dims,
1329 int expected_nb_input_dims,
1330 int expected_nb_parameters) {
1331 int i;
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");
1339 //return 0;
1342 return 1;
1345 // Check the type.
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);
1352 return 0;
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);
1362 return 0;
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);
1370 return 0;
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);
1379 return 0;
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);
1391 return 0;
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);
1403 return 0;
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);
1412 return 0;
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);
1424 return 0;
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);
1433 return 0;
1436 relation = relation->next;
1439 return 1;
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))
1457 return NULL;
1459 copy1 = openscop_relation_copy(r1);
1460 copy2 = openscop_relation_copy(r2);
1462 if ((r1 != NULL) && (r2 == NULL))
1463 return copy1;
1465 if ((r1 == NULL) && (r2 != NULL))
1466 return copy2;
1468 tmp = copy1;
1469 while (tmp->next != NULL)
1470 tmp = tmp->next;
1472 tmp->next = copy2;
1473 return copy1;
1477 /**
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) {
1502 int i;
1503 int first = 1;
1504 int array_id = OPENSCOP_UNDEFINED;
1505 int reference_array_id = OPENSCOP_UNDEFINED;
1506 int nb_array_id;
1507 int row_id = 0;
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.
1531 nb_array_id = 0;
1532 for (i = 0; i < relation->nb_rows; i++) {
1533 if (!OPENSCOP_INT_zero_p(relation->m[i][1])) {
1534 nb_array_id ++;
1535 row_id = i;
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.
1565 if (first) {
1566 reference_array_id = array_id;
1567 first = 0;
1569 else {
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;
1580 return array_id;
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)
1594 return 0;
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))
1600 return 1;
1602 return 0;