« back to all changes in this revision
Viewing changes to osl/source/relation.c
- browse files at revision 12
- compare with another revision
- download diff
- download tarball
- view history from revision 12
- Committer: Package Import Robot
- Author(s): Matthias Klose
- Date: 2014-02-26 14:21:11 UTC
- mfrom: (3.1.8 sid)
- Revision ID: package-import@ubuntu.com-20140226142111-vsbb1isby30uundd
Tags: 0.18.2-1
New upstream version.
- files added:
- .pc
- .pc/add-cmake-files.diff
- .pc/add-cmake-files.diff/cmake
- debian/patches
- debian/source
- files removed:
- .gitignore
- autom4te.cache
- isl/autom4te.cache
- osl
- osl/autoconf
- osl/autom4te.cache
- osl/doc
- osl/doc/images
- osl/include
- osl/include/osl
- osl/include/osl/extensions
- osl/m4
- osl/source
- osl/source/extensions
- osl/tests
- test/bigs
- test/challenges
- test/openscop
- test/published
- test/published/CC2003
- test/published/CC2006
- test/published/PACT2004
- test/published/Web
- test/reports
- test/urgent
- files modified:
- Makefile.in
added
removed
osl/source/relation.c
1
2
/*+-----------------------------------------------------------------**
3
** OpenScop Library **
4
**-----------------------------------------------------------------**
5
** relation.c **
6
**-----------------------------------------------------------------**
7
** First version: 30/04/2008 **
8
**-----------------------------------------------------------------**
9
10
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
*****************************************************************************/
62
63
64
#include <stdlib.h>
65
#include <stdio.h>
66
#include <string.h>
67
#include <ctype.h>
68
69
#include <osl/macros.h>
70
#include <osl/int.h>
71
#include <osl/util.h>
72
#include <osl/vector.h>
73
#include <osl/strings.h>
74
#include <osl/names.h>
75
#include <osl/relation.h>
76
77
78
/*+***************************************************************************
79
* Structure display function *
80
*****************************************************************************/
81
82
83
/**
84
* osl_relation_sprint_type function:
85
* this function prints the textual type of an osl_relation_t structure into
86
* a string, according to the OpenScop specification, and returns that string.
87
* \param[in] relation The relation whose type has to be printed.
88
* \return A string containing the relation type.
89
*/
90
static
91
char * osl_relation_sprint_type(osl_relation_p relation) {
92
char * string = NULL;
93
94
OSL_malloc(string, char *, OSL_MAX_STRING * sizeof(char));
95
string[0] = '\0';
96
97
if (relation != NULL) {
98
switch (relation->type) {
99
case OSL_UNDEFINED: {
100
snprintf(string, OSL_MAX_STRING, OSL_STRING_UNDEFINED);
101
break;
102
}
103
case OSL_TYPE_CONTEXT: {
104
snprintf(string, OSL_MAX_STRING, OSL_STRING_CONTEXT);
105
break;
106
}
107
case OSL_TYPE_DOMAIN: {
108
snprintf(string, OSL_MAX_STRING, OSL_STRING_DOMAIN);
109
break;
110
}
111
case OSL_TYPE_SCATTERING: {
112
snprintf(string, OSL_MAX_STRING, OSL_STRING_SCATTERING);
113
break;
114
}
115
case OSL_TYPE_READ: {
116
snprintf(string, OSL_MAX_STRING, OSL_STRING_READ);
117
break;
118
}
119
case OSL_TYPE_WRITE: {
120
snprintf(string, OSL_MAX_STRING, OSL_STRING_WRITE);
121
break;
122
}
123
case OSL_TYPE_MAY_WRITE: {
124
snprintf(string, OSL_MAX_STRING, OSL_STRING_MAY_WRITE);
125
break;
126
}
127
default: {
128
OSL_warning("unknown relation type, "
129
"replaced with "OSL_STRING_UNDEFINED);
130
snprintf(string, OSL_MAX_STRING, OSL_STRING_UNDEFINED);
131
}
132
}
133
}
134
135
return string;
136
}
137
138
139
/**
140
* osl_relation_print_type function:
141
* this function displays the textual type of an osl_relation_t structure into
142
* a file (file, possibly stdout), according to the OpenScop specification.
143
* \param[in] file File where informations are printed.
144
* \param[in] relation The relation whose type has to be printed.
145
*/
146
static
147
void osl_relation_print_type(FILE * file, osl_relation_p relation) {
148
char * string = osl_relation_sprint_type(relation);
149
fprintf(file, "%s", string);
150
free(string);
151
}
152
153
154
/**
155
* osl_relation_idump function:
156
* this function displays a osl_relation_t structure (*relation) into a
157
* file (file, possibly stdout) in a way that trends to be understandable.
158
* It includes an indentation level (level) in order to work with others
159
* idump functions.
160
* \param[in] file File where informations are printed.
161
* \param[in] relation The relation whose information has to be printed.
162
* \param[in] level Number of spaces before printing, for each line.
163
*/
164
void osl_relation_idump(FILE * file, osl_relation_p relation, int level) {
165
int i, j, first = 1;
166
167
// Go to the right level.
168
for (j = 0; j < level; j++)
169
fprintf(file, "|\t");
170
171
if (relation != NULL) {
172
fprintf(file, "+-- osl_relation_t (");
173
osl_relation_print_type(file, relation);
174
fprintf(file, ", ");
175
osl_int_dump_precision(file, relation->precision);
176
fprintf(file, ")\n");
177
}
178
else {
179
fprintf(file, "+-- NULL relation\n");
180
}
181
182
while (relation != NULL) {
183
if (! first) {
184
// Go to the right level.
185
for (j = 0; j < level; j++)
186
fprintf(file, "|\t");
187
fprintf(file, "| osl_relation_t (");
188
osl_relation_print_type(file, relation);
189
fprintf(file, ", ");
190
osl_int_dump_precision(file, relation->precision);
191
fprintf(file, ")\n");
192
}
193
else
194
first = 0;
195
196
// A blank line
197
for(j = 0; j <= level; j++)
198
fprintf(file, "|\t");
199
fprintf(file, "%d %d %d %d %d %d\n",
200
relation->nb_rows, relation->nb_columns,
201
relation->nb_output_dims, relation->nb_input_dims,
202
relation->nb_local_dims, relation->nb_parameters);
203
204
// Display the relation.
205
for (i = 0; i < relation->nb_rows; i++) {
206
for (j = 0; j <= level; j++)
207
fprintf(file, "|\t");
208
209
fprintf(file, "[ ");
210
211
for (j = 0; j < relation->nb_columns; j++) {
212
osl_int_print(file, relation->precision, relation->m[i][j]);
213
fprintf(file, " ");
214
}
215
216
fprintf(file, "]\n");
217
}
218
219
relation = relation->next;
220
221
// Next line.
222
if (relation != NULL) {
223
for (j = 0; j <= level; j++)
224
fprintf(file, "|\t");
225
fprintf(file, "|\n");
226
for (j = 0; j <= level; j++)
227
fprintf(file, "|\t");
228
fprintf(file, "V\n");
229
}
230
}
231
232
// The last line.
233
for (j = 0; j <= level; j++)
234
fprintf(file, "|\t");
235
fprintf(file, "\n");
236
}
237
238
239
/**
240
* osl_relation_dump function:
241
* this function prints the content of a osl_relation_t structure
242
* (*relation) into a file (file, possibly stdout).
243
* \param[in] file File where informations are printed.
244
* \param[in] relation The relation whose information have to be printed.
245
*/
246
void osl_relation_dump(FILE * file, osl_relation_p relation) {
247
osl_relation_idump(file, relation, 0);
248
}
249
250
251
/**
252
* osl_relation_expression_element function:
253
* this function returns a string containing the printing of a value (e.g.,
254
* an iterator with its coefficient or a constant).
255
* \param[in] val Coefficient or constant value.
256
* \param[in] precision The precision of the value.
257
* \param[in,out] first Pointer to a boolean set to 1 if the current value
258
* is the first of an expresion, 0 otherwise (maybe
259
* updated).
260
* \param[in] cst A boolean set to 1 if the value is a constant,
261
* 0 otherwise.
262
* \param[in] name String containing the name of the element.
263
* \return A string that contains the printing of a value.
264
*/
265
static
266
char * osl_relation_expression_element(osl_int_t val,
267
int precision, int * first,
268
int cst, char * name) {
269
char * temp, * body, * sval;
270
271
OSL_malloc(temp, char *, OSL_MAX_STRING * sizeof(char));
272
OSL_malloc(body, char *, OSL_MAX_STRING * sizeof(char));
273
OSL_malloc(sval, char *, OSL_MAX_STRING * sizeof(char));
274
275
body[0] = '\0';
276
sval[0] = '\0';
277
278
// statements for the 'normal' processing.
279
if (!osl_int_zero(precision, val) && (!cst)) {
280
if ((*first) || osl_int_neg(precision, val)) {
281
if (osl_int_one(precision, val)) { // case 1
282
sprintf(sval, "%s", name);
283
}
284
else {
285
if (osl_int_mone(precision, val)) { // case -1
286
sprintf(sval, "-%s", name);
287
}
288
else { // default case
289
osl_int_sprint_txt(sval, precision, val);
290
sprintf(temp, "*%s", name);
291
strcat(sval, temp);
292
}
293
}
294
*first = 0;
295
}
296
else {
297
if (osl_int_one(precision, val)) {
298
sprintf(sval, "+%s", name);
299
}
300
else {
301
sprintf(sval, "+");
302
osl_int_sprint_txt(temp, precision, val);
303
strcat(sval, temp);
304
sprintf(temp, "*%s", name);
305
strcat(sval, temp);
306
}
307
}
308
}
309
else {
310
if (cst) {
311
if ((osl_int_zero(precision, val) && (*first)) ||
312
(osl_int_neg(precision, val)))
313
osl_int_sprint_txt(sval, precision, val);
314
if (osl_int_pos(precision, val)) {
315
if (!(*first)) {
316
sprintf(sval, "+");
317
osl_int_sprint_txt(temp, precision, val);
318
strcat(sval, temp);
319
}
320
else {
321
osl_int_sprint_txt(sval, precision, val);
322
}
323
}
324
}
325
}
326
free(temp);
327
free(body);
328
329
return(sval);
330
}
331
332
333
/**
334
* osl_relation_strings function:
335
* this function creates a NULL-terminated array of strings from an
336
* osl_names_t structure in such a way that the ith string is the "name"
337
* corresponding to the ith column of the constraint matrix.
338
* \param[in] relation The relation for which we need an array of names.
339
* \param[in] names The set of names for each element.
340
* \return An array of strings with one string per constraint matrix column.
341
*/
342
static
343
char ** osl_relation_strings(osl_relation_p relation, osl_names_p names) {
344
char ** strings;
345
char temp[OSL_MAX_STRING];
346
int i, offset;
347
348
if ((relation == NULL) || (names == NULL)) {
349
OSL_debug("no names or relation to build the name array");
350
return NULL;
351
}
352
353
OSL_malloc(strings, char **, (relation->nb_columns + 1)*sizeof(char *));
354
strings[relation->nb_columns] = NULL;
355
356
// 1. Equality/inequality marker.
357
OSL_strdup(strings[0], "e/i");
358
offset = 1;
359
360
// 2. Output dimensions.
361
if (osl_relation_is_access(relation)) {
362
// The first output dimension is the array name.
363
OSL_strdup(strings[offset], "Arr");
364
// The other ones are the array dimensions [1]...[n]
365
for (i = offset + 1; i < relation->nb_output_dims + offset; i++) {
366
sprintf(temp, "[%d]", i - 1);
367
OSL_strdup(strings[i], temp);
368
}
369
}
370
else
371
if ((relation->type == OSL_TYPE_DOMAIN) ||
372
(relation->type == OSL_TYPE_CONTEXT)) {
373
for (i = offset; i < relation->nb_output_dims + offset; i++) {
374
OSL_strdup(strings[i], names->iterators->string[i - offset]);
375
}
376
}
377
else {
378
for (i = offset; i < relation->nb_output_dims + offset; i++) {
379
OSL_strdup(strings[i], names->scatt_dims->string[i - offset]);
380
}
381
}
382
offset += relation->nb_output_dims;
383
384
// 3. Input dimensions.
385
for (i = offset; i < relation->nb_input_dims + offset; i++)
386
OSL_strdup(strings[i], names->iterators->string[i - offset]);
387
offset += relation->nb_input_dims;
388
389
// 4. Local dimensions.
390
for (i = offset; i < relation->nb_local_dims + offset; i++)
391
OSL_strdup(strings[i], names->local_dims->string[i - offset]);
392
offset += relation->nb_local_dims;
393
394
// 5. Parameters.
395
for (i = offset; i < relation->nb_parameters + offset; i++)
396
OSL_strdup(strings[i], names->parameters->string[i - offset]);
397
offset += relation->nb_parameters;
398
399
// 6. Scalar.
400
OSL_strdup(strings[offset], "1");
401
402
return strings;
403
}
404
405
406
/**
407
* osl_relation_subexpression function:
408
* this function returns a string corresponding to an affine (sub-)expression
409
* stored at the "row"^th row of the relation pointed by "relation" between
410
* the start and stop columns. Optionally it may oppose the whole expression.
411
* \param[in] relation A set of linear expressions.
412
* \param[in] row The row corresponding to the expression.
413
* \param[in] start The first column for the expression (inclusive).
414
* \param[in] stop The last column for the expression (inclusive).
415
* \param[in] oppose Boolean set to 1 to negate the expression, 0 otherwise.
416
* \param[in] strings Array of textual names of the various elements.
417
* \return A string that contains the printing of an affine (sub-)expression.
418
*/
419
static
420
char * osl_relation_subexpression(osl_relation_p relation,
421
int row, int start, int stop, int oppose,
422
char ** strings) {
423
int i, first = 1, constant;
424
char * sval;
425
char * sline;
426
427
OSL_malloc(sline, char *, OSL_MAX_STRING * sizeof(char));
428
sline[0] = '\0';
429
430
// Create the expression. The constant is a special case.
431
for (i = start; i <= stop; i++) {
432
if (oppose) {
433
osl_int_oppose(relation->precision,
434
&relation->m[row][i], relation->m[row][i]);
435
}
436
437
if (i == relation->nb_columns - 1)
438
constant = 1;
439
else
440
constant = 0;
441
442
sval = osl_relation_expression_element(relation->m[row][i],
443
relation->precision, &first, constant, strings[i]);
444
445
if (oppose) {
446
osl_int_oppose(relation->precision,
447
&relation->m[row][i], relation->m[row][i]);
448
}
449
strcat(sline, sval);
450
free(sval);
451
}
452
453
return sline;
454
}
455
456
457
/**
458
* osl_relation_expression function:
459
* this function returns a string corresponding to an affine expression
460
* stored at the "row"^th row of the relation pointed by "relation".
461
* \param[in] relation A set of linear expressions.
462
* \param[in] row The row corresponding to the expression.
463
* \param[in] strings Array of textual names of the various elements.
464
* \return A string that contains the printing of an affine expression.
465
*/
466
char * osl_relation_expression(osl_relation_p relation,
467
int row, char ** strings) {
468
469
return osl_relation_subexpression(relation, row,
470
1, relation->nb_columns - 1, 0,
471
strings);
472
}
473
474
475
/**
476
* osl_relation_is_simple_output function:
477
* this function returns 1 or -1 if a given constraint row of a relation
478
* corresponds to an output, 0 otherwise. We call a simple output an equality
479
* constraint where exactly one output coefficient is not 0 and is either
480
* 1 (in this case the function returns 1) or -1 (in this case the function
481
* returns -1).
482
* \param[in] relation The relation to test for simple output.
483
* \param[in] row The row corresponding to the constraint to test.
484
* \return 1 or -1 if the row is a simple output, 0 otherwise.
485
*/
486
static
487
int osl_relation_is_simple_output(osl_relation_p relation, int row) {
488
int i;
489
int first = 1;
490
int sign = 0;
491
492
if ((relation == NULL) ||
493
(relation->m == NULL) ||
494
(relation->nb_output_dims == 0))
495
return 0;
496
497
if ((row < 0) || (row > relation->nb_rows))
498
OSL_error("the specified row does not exist in the relation");
499
500
// The constraint must be an equality.
501
if (!osl_int_zero(relation->precision, relation->m[row][0]))
502
return 0;
503
504
// Check the output part has one and only one non-zero +1 or -1 coefficient.
505
first = 1;
506
for (i = 1; i <= relation->nb_output_dims; i++) {
507
if (!osl_int_zero(relation->precision, relation->m[row][i])) {
508
if (first)
509
first = 0;
510
else
511
return 0;
512
513
if (osl_int_one(relation->precision, relation->m[row][i]))
514
sign = 1;
515
else if (osl_int_mone(relation->precision, relation->m[row][i]))
516
sign = -1;
517
else
518
return 0;
519
}
520
}
521
522
return sign;
523
}
524
525
526
/**
527
* osl_relation_sprint_comment function:
528
* this function prints into a string a comment corresponding to a constraint
529
* of a relation, according to its type, then it returns this string. This
530
* function does not check that printing the comment is possible (i.e., are
531
* there enough names ?), hence it is the responsibility of the user to ensure
532
* he/she can call this function safely.
533
* \param[in] relation The relation for which a comment has to be printed.
534
* \param[in] row The constrain row for which a comment has to be printed.
535
* \param[in] strings Array of textual names of the various elements.
536
* \param[in] arrays Array of textual identifiers of the arrays.
537
* \return A string which contains the comment for the row.
538
*/
539
static
540
char * osl_relation_sprint_comment(osl_relation_p relation, int row,
541
char ** strings, char ** arrays) {
542
int sign;
543
int high_water_mark = OSL_MAX_STRING;
544
char * string = NULL;
545
char * expression;
546
char buffer[OSL_MAX_STRING];
547
548
OSL_malloc(string, char *, high_water_mark * sizeof(char));
549
string[0] = '\0';
550
551
if ((relation == NULL) || (strings == NULL)) {
552
OSL_debug("no relation or names while asked to print a comment");
553
return string;
554
}
555
556
if ((sign = osl_relation_is_simple_output(relation, row))) {
557
// First case : output == expression.
558
559
expression = osl_relation_subexpression(relation, row,
560
1, relation->nb_output_dims,
561
sign < 0,
562
strings);
563
snprintf(buffer, OSL_MAX_STRING, " ## %s", expression);
564
osl_util_safe_strcat(&string, buffer, &high_water_mark);
565
free(expression);
566
567
// We don't print the right hand side if it's an array identifier.
568
if (!osl_relation_is_access(relation) ||
569
osl_int_zero(relation->precision, relation->m[row][1])) {
570
expression = osl_relation_subexpression(relation, row,
571
relation->nb_output_dims + 1,
572
relation->nb_columns - 1,
573
sign > 0,
574
strings);
575
snprintf(buffer, OSL_MAX_STRING, " == %s", expression);
576
osl_util_safe_strcat(&string, buffer, &high_water_mark);
577
free(expression);
578
}
579
else {
580
snprintf(buffer, OSL_MAX_STRING, " == %s",
581
arrays[osl_relation_get_array_id(relation) - 1]);
582
osl_util_safe_strcat(&string, buffer, &high_water_mark);
583
}
584
}
585
else {
586
// Second case : general case.
587
588
expression = osl_relation_expression(relation, row, strings);
589
snprintf(buffer, OSL_MAX_STRING, " ## %s", expression);
590
osl_util_safe_strcat(&string, buffer, &high_water_mark);
591
free(expression);
592
593
if (osl_int_zero(relation->precision, relation->m[row][0]))
594
snprintf(buffer, OSL_MAX_STRING, " == 0");
595
else
596
snprintf(buffer, OSL_MAX_STRING, " >= 0");
597
osl_util_safe_strcat(&string, buffer, &high_water_mark);
598
}
599
600
return string;
601
}
602
603
604
/**
605
* osl_relation_column_string function:
606
* this function returns an OpenScop comment string showing all column
607
* names. It is designed to nicely fit a constraint matrix that would be
608
* printed just below this line.
609
* \param[in] relation The relation related to the comment line to build.
610
* \param[in] strings Array of textual names of the various elements.
611
* \return A fancy comment string with all the dimension names.
612
*/
613
static
614
char * osl_relation_column_string(osl_relation_p relation, char ** strings) {
615
int i, j;
616
int index_output_dims;
617
int index_input_dims;
618
int index_local_dims;
619
int index_parameters;
620
int index_scalar;
621
int space, length, left, right;
622
char * scolumn;
623
char temp[OSL_MAX_STRING];
624
625
OSL_malloc(scolumn, char *, OSL_MAX_STRING);
626
627
index_output_dims = 1;
628
index_input_dims = index_output_dims + relation->nb_output_dims;
629
index_local_dims = index_input_dims + relation->nb_input_dims;
630
index_parameters = index_local_dims + relation->nb_local_dims;
631
index_scalar = index_parameters + relation->nb_parameters;
632
633
// 1. The comment part.
634
sprintf(scolumn, "#");
635
for (j = 0; j < (OSL_FMT_LENGTH - 1)/2 - 1; j++)
636
strcat(scolumn, " ");
637
638
i = 0;
639
while (strings[i] != NULL) {
640
space = OSL_FMT_LENGTH;
641
length = (space > strlen(strings[i])) ? strlen(strings[i]) : space;
642
right = (space - length + (OSL_FMT_LENGTH % 2)) / 2;
643
left = space - length - right;
644
645
// 2. Spaces before the name
646
for (j = 0; j < left; j++)
647
strcat(scolumn, " ");
648
649
// 3. The (abbreviated) name
650
for (j = 0; j < length - 1; j++) {
651
sprintf(temp, "%c", strings[i][j]);
652
strcat(scolumn, temp);
653
}
654
if (length >= strlen(strings[i]))
655
sprintf(temp, "%c", strings[i][j]);
656
else
657
sprintf(temp, ".");
658
strcat(scolumn, temp);
659
660
// 4. Spaces after the name
661
for (j = 0; j < right; j++)
662
strcat(scolumn, " ");
663
664
i++;
665
if ((i == index_output_dims) ||
666
(i == index_input_dims) ||
667
(i == index_local_dims) ||
668
(i == index_parameters) ||
669
(i == index_scalar))
670
strcat(scolumn, "|");
671
else
672
strcat(scolumn, " ");
673
}
674
strcat(scolumn, "\n");
675
676
return scolumn;
677
}
678
679
680
/**
681
* osl_relation_column_string_scoplib function:
682
* this function returns an OpenScop comment string showing all column
683
* names. It is designed to nicely fit a constraint matrix that would be
684
* printed just below this line.
685
* \param[in] relation The relation related to the comment line to build.
686
* \param[in] strings Array of textual names of the various elements.
687
* \return A fancy comment string with all the dimension names.
688
*/
689
static
690
char * osl_relation_column_string_scoplib(osl_relation_p relation,
691
char ** strings) {
692
int i, j;
693
int index_output_dims;
694
int index_input_dims;
695
int index_local_dims;
696
int index_parameters;
697
int index_scalar;
698
int space, length, left, right;
699
char * scolumn;
700
char temp[OSL_MAX_STRING];
701
702
OSL_malloc(scolumn, char *, OSL_MAX_STRING);
703
704
index_output_dims = 1;
705
index_input_dims = index_output_dims + relation->nb_output_dims;
706
index_local_dims = index_input_dims + relation->nb_input_dims;
707
index_parameters = index_local_dims + relation->nb_local_dims;
708
index_scalar = index_parameters + relation->nb_parameters;
709
710
// 1. The comment part.
711
sprintf(scolumn, "#");
712
for (j = 0; j < (OSL_FMT_LENGTH - 1)/2 - 1; j++)
713
strcat(scolumn, " ");
714
715
i = 0;
716
while (strings[i] != NULL) {
717
718
if (i == 0 ||
719
(relation->type != OSL_TYPE_DOMAIN && i >= index_input_dims) ||
720
(relation->type == OSL_TYPE_DOMAIN && i <= index_output_dims) ||
721
i >= index_parameters) {
722
space = OSL_FMT_LENGTH;
723
length = (space > strlen(strings[i])) ? strlen(strings[i]) : space;
724
right = (space - length + (OSL_FMT_LENGTH % 2)) / 2;
725
left = space - length - right;
726
727
// 2. Spaces before the name
728
for (j = 0; j < left; j++)
729
strcat(scolumn, " ");
730
731
// 3. The (abbreviated) name
732
for (j = 0; j < length - 1; j++) {
733
sprintf(temp, "%c", strings[i][j]);
734
strcat(scolumn, temp);
735
}
736
if (length >= strlen(strings[i]))
737
sprintf(temp, "%c", strings[i][j]);
738
else
739
sprintf(temp, ".");
740
strcat(scolumn, temp);
741
742
// 4. Spaces after the name
743
for (j = 0; j < right; j++)
744
strcat(scolumn, " ");
745
746
if ((i == index_output_dims-1) ||
747
(i == index_input_dims-1) ||
748
(i == index_local_dims-1) ||
749
(i == index_parameters-1) ||
750
(i == index_scalar-1))
751
strcat(scolumn, "|");
752
else
753
strcat(scolumn, " ");
754
}
755
756
i++;
757
}
758
strcat(scolumn, "\n");
759
760
return scolumn;
761
}
762
763
764
/**
765
* osl_relation_names function:
766
* this function generates as set of names for all the dimensions
767
* involved in a given relation.
768
* \param[in] relation The relation we have to generate names for.
769
* \return A set of generated names for the input relation dimensions.
770
*/
771
static
772
osl_names_p osl_relation_names(osl_relation_p relation) {
773
int nb_parameters = OSL_UNDEFINED;
774
int nb_iterators = OSL_UNDEFINED;
775
int nb_scattdims = OSL_UNDEFINED;
776
int nb_localdims = OSL_UNDEFINED;
777
int array_id = OSL_UNDEFINED;
778
779
osl_relation_get_attributes(relation, &nb_parameters, &nb_iterators,
780
&nb_scattdims, &nb_localdims, &array_id);
781
782
return osl_names_generate("P", nb_parameters,
783
"i", nb_iterators,
784
"c", nb_scattdims,
785
"l", nb_localdims,
786
"A", array_id);
787
}
788
789
790
/**
791
* osl_relation_nb_components function:
792
* this function returns the number of component in the union of relations
793
* provided as parameter.
794
* \param[in] relation The input union of relations.
795
* \return The number of components in the input union of relations.
796
*/
797
int osl_relation_nb_components(osl_relation_p relation) {
798
int nb_components = 0;
799
800
while (relation != NULL) {
801
nb_components++;
802
relation = relation->next;
803
}
804
805
return nb_components;
806
}
807
808
809
/**
810
* osl_relation_spprint_polylib function:
811
* this function pretty-prints the content of an osl_relation_t structure
812
* (*relation) into a string in the extended polylib format, and returns this
813
* string. This format is the same as OpenScop's, minus the type.
814
* \param[in] relation The relation whose information has to be printed.
815
* \param[in] names The names of the constraint columns for comments.
816
* \return A string containing the relation pretty-printing.
817
*/
818
char * osl_relation_spprint_polylib(osl_relation_p relation,
819
osl_names_p names) {
820
int i, j;
821
int part, nb_parts;
822
int generated_names = 0;
823
int high_water_mark = OSL_MAX_STRING;
824
char * string = NULL;
825
char buffer[OSL_MAX_STRING];
826
char ** name_array = NULL;
827
char * scolumn;
828
char * comment;
829
830
if (relation == NULL)
831
return strdup("# NULL relation\n");
832
833
OSL_malloc(string, char *, high_water_mark * sizeof(char));
834
string[0] = '\0';
835
836
// Generates the names for the comments if necessary.
837
if (names == NULL) {
838
generated_names = 1;
839
names = osl_relation_names(relation);
840
}
841
842
nb_parts = osl_relation_nb_components(relation);
843
844
if (nb_parts > 1) {
845
snprintf(buffer, OSL_MAX_STRING, "# Union with %d parts\n%d\n",
846
nb_parts, nb_parts);
847
osl_util_safe_strcat(&string, buffer, &high_water_mark);
848
}
849
850
// Print each part of the union.
851
for (part = 1; part <= nb_parts; part++) {
852
// Prepare the array of strings for comments.
853
name_array = osl_relation_strings(relation, names);
854
855
if (nb_parts > 1) {
856
snprintf(buffer, OSL_MAX_STRING, "# Union part No.%d\n", part);
857
osl_util_safe_strcat(&string, buffer, &high_water_mark);
858
}
859
860
snprintf(buffer, OSL_MAX_STRING, "%d %d %d %d %d %d\n",
861
relation->nb_rows, relation->nb_columns,
862
relation->nb_output_dims, relation->nb_input_dims,
863
relation->nb_local_dims, relation->nb_parameters);
864
osl_util_safe_strcat(&string, buffer, &high_water_mark);
865
866
if (relation->nb_rows > 0) {
867
scolumn = osl_relation_column_string(relation, name_array);
868
snprintf(buffer, OSL_MAX_STRING, "%s", scolumn);
869
osl_util_safe_strcat(&string, buffer, &high_water_mark);
870
free(scolumn);
871
}
872
873
for (i = 0; i < relation->nb_rows; i++) {
874
for (j = 0; j < relation->nb_columns; j++) {
875
osl_int_sprint(buffer, relation->precision, relation->m[i][j]);
876
osl_util_safe_strcat(&string, buffer, &high_water_mark);
877
snprintf(buffer, OSL_MAX_STRING, " ");
878
osl_util_safe_strcat(&string, buffer, &high_water_mark);
879
}
880
881
if (name_array != NULL) {
882
comment = osl_relation_sprint_comment(relation, i, name_array,
883
names->arrays->string);
884
osl_util_safe_strcat(&string, comment, &high_water_mark);
885
free(comment);
886
}
887
snprintf(buffer, OSL_MAX_STRING, "\n");
888
osl_util_safe_strcat(&string, buffer, &high_water_mark);
889
}
890
891
// Free the array of strings.
892
if (name_array != NULL) {
893
for (i = 0; i < relation->nb_columns; i++)
894
free(name_array[i]);
895
free(name_array);
896
}
897
898
relation = relation->next;
899
}
900
901
if (generated_names)
902
osl_names_free(names);
903
904
return string;
905
}
906
907
908
/**
909
* osl_relation_spprint_polylib_scoplib function:
910
* this function pretty-prints the content of an osl_relation_t structure
911
* (*relation) into a string in the extended polylib format, and returns this
912
* string.
913
* \param[in] relation The relation whose information has to be printed.
914
* \param[in] names The names of the constraint columns for comments.
915
* \param[in] print_nth_part Print the value of `n' (used for domain union)
916
* \param[in] add_fakeiter
917
* \return A string containing the relation pretty-printing.
918
*/
919
char * osl_relation_spprint_polylib_scoplib(osl_relation_p relation,
920
osl_names_p names,
921
int print_nth_part,
922
int add_fakeiter) {
923
int i, j;
924
int part, nb_parts;
925
int generated_names = 0;
926
int is_access_array;
927
int high_water_mark = OSL_MAX_STRING;
928
int start_row; // for removing the first line in the access matrix
929
int index_output_dims;
930
int index_input_dims;
931
int index_params;
932
char * string = NULL;
933
char buffer[OSL_MAX_STRING];
934
char ** name_array = NULL;
935
char * scolumn;
936
char * comment;
937
938
if (relation == NULL)
939
return strdup("# NULL relation\n");
940
941
OSL_malloc(string, char *, high_water_mark * sizeof(char));
942
string[0] = '\0';
943
944
// Generates the names for the comments if necessary.
945
if (names == NULL) {
946
generated_names = 1;
947
names = osl_relation_names(relation);
948
}
949
950
nb_parts = osl_relation_nb_components(relation);
951
if (nb_parts > 1) {
952
snprintf(buffer, OSL_MAX_STRING, "# Union with %d parts\n%d\n",
953
nb_parts, nb_parts);
954
osl_util_safe_strcat(&string, buffer, &high_water_mark);
955
}
956
957
is_access_array = (relation->type == OSL_TYPE_READ ||
958
relation->type == OSL_TYPE_WRITE ? 1 : 0);
959
960
// Print each part of the union.
961
962
for (part = 1; part <= nb_parts; part++) {
963
964
index_output_dims = 1;
965
index_input_dims = index_output_dims + relation->nb_output_dims;
966
index_params = index_input_dims + relation->nb_input_dims;
967
968
// Prepare the array of strings for comments.
969
name_array = osl_relation_strings(relation, names);
970
971
if (nb_parts > 1) {
972
snprintf(buffer, OSL_MAX_STRING, "# Union part No.%d\n", part);
973
osl_util_safe_strcat(&string, buffer, &high_water_mark);
974
}
975
976
if (print_nth_part) {
977
snprintf(buffer, OSL_MAX_STRING, "%d\n", part);
978
osl_util_safe_strcat(&string, buffer, &high_water_mark);
979
}
980
981
// Don't print the array size for access array
982
// (the total size is printed in osl_relation_list_pprint_access_array_scoplib)
983
if (!is_access_array) {
984
985
// Print array size
986
if (relation->type == OSL_TYPE_DOMAIN) {
987
988
if (add_fakeiter) {
989
990
snprintf(buffer, OSL_MAX_STRING, "%d %d\n",
991
relation->nb_rows+1, relation->nb_columns -
992
relation->nb_input_dims + 1);
993
osl_util_safe_strcat(&string, buffer, &high_water_mark);
994
995
// add the fakeiter line
996
snprintf(buffer, OSL_MAX_STRING, " 0 ");
997
osl_util_safe_strcat(&string, buffer, &high_water_mark);
998
snprintf(buffer, OSL_MAX_STRING, " 1 "); // fakeiter
999
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1000
1001
for (i = 0 ; i < relation->nb_parameters ; i++) {
1002
snprintf(buffer, OSL_MAX_STRING, " 0 ");
1003
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1004
}
1005
1006
snprintf(buffer, OSL_MAX_STRING, " 0 ## fakeiter == 0\n");
1007
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1008
1009
} else {
1010
snprintf(buffer, OSL_MAX_STRING, "%d %d\n",
1011
relation->nb_rows, relation->nb_columns -
1012
relation->nb_input_dims);
1013
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1014
}
1015
1016
} else { // SCATTERING
1017
1018
if (add_fakeiter) {
1019
snprintf(buffer, OSL_MAX_STRING, "%d %d\n",
1020
relation->nb_rows+2, relation->nb_columns -
1021
relation->nb_output_dims + 1);
1022
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1023
} else {
1024
snprintf(buffer, OSL_MAX_STRING, "%d %d\n",
1025
relation->nb_rows, relation->nb_columns -
1026
relation->nb_output_dims);
1027
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1028
}
1029
}
1030
1031
// Print column names in comment
1032
if (relation->nb_rows > 0) {
1033
scolumn = osl_relation_column_string_scoplib(relation, name_array);
1034
snprintf(buffer, OSL_MAX_STRING, "%s", scolumn);
1035
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1036
free(scolumn);
1037
}
1038
1039
start_row = 0;
1040
1041
} else {
1042
1043
if (relation->nb_rows == 1) // for non array variables
1044
start_row = 0;
1045
else // Remove the 'Arr' line
1046
start_row = 1;
1047
}
1048
1049
// Print the array
1050
for (i = start_row; i < relation->nb_rows; i++) {
1051
1052
// First column
1053
if (!is_access_array) {
1054
// array index name for scoplib
1055
osl_int_sprint(buffer, relation->precision, relation->m[i][0]);
1056
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1057
snprintf(buffer, OSL_MAX_STRING, " ");
1058
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1059
1060
} else {
1061
// The first column represents the array index name in openscop
1062
if (i == start_row)
1063
osl_int_sprint(buffer, relation->precision,
1064
relation->m[0][relation->nb_columns-1]);
1065
else
1066
snprintf(buffer, OSL_MAX_STRING, " 0 ");
1067
1068
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1069
snprintf(buffer, OSL_MAX_STRING, " ");
1070
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1071
}
1072
1073
// Rest of the array
1074
if (relation->type == OSL_TYPE_DOMAIN) {
1075
1076
for (j = 1; j < index_input_dims; j++) {
1077
osl_int_sprint(buffer, relation->precision, relation->m[i][j]);
1078
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1079
snprintf(buffer, OSL_MAX_STRING, " ");
1080
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1081
}
1082
1083
// Jmp input_dims
1084
for (j = index_params; j < relation->nb_columns; j++) {
1085
osl_int_sprint(buffer, relation->precision, relation->m[i][j]);
1086
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1087
snprintf(buffer, OSL_MAX_STRING, " ");
1088
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1089
}
1090
1091
} else {
1092
1093
// Jmp output_dims
1094
for (j = index_input_dims; j < index_params; j++) {
1095
if (is_access_array && relation->nb_rows == 1 &&
1096
j == relation->nb_columns-1) {
1097
snprintf(buffer, OSL_MAX_STRING, " 0 ");
1098
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1099
} else {
1100
osl_int_sprint(buffer, relation->precision, relation->m[i][j]);
1101
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1102
snprintf(buffer, OSL_MAX_STRING, " ");
1103
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1104
}
1105
}
1106
1107
if (add_fakeiter) {
1108
snprintf(buffer, OSL_MAX_STRING, " 0 ");
1109
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1110
}
1111
1112
for (; j < relation->nb_columns; j++) {
1113
if (is_access_array && relation->nb_rows == 1 &&
1114
j == relation->nb_columns-1) {
1115
snprintf(buffer, OSL_MAX_STRING, " 0 ");
1116
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1117
} else {
1118
osl_int_sprint(buffer, relation->precision, relation->m[i][j]);
1119
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1120
snprintf(buffer, OSL_MAX_STRING, " ");
1121
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1122
}
1123
}
1124
}
1125
1126
// equation in comment
1127
if (name_array != NULL) {
1128
comment = osl_relation_sprint_comment(relation, i, name_array,
1129
names->arrays->string);
1130
osl_util_safe_strcat(&string, comment, &high_water_mark);
1131
free(comment);
1132
snprintf(buffer, OSL_MAX_STRING, "\n");
1133
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1134
}
1135
1136
// add the lines in the scattering if we need the fakeiter
1137
if (relation->nb_rows > 0 && add_fakeiter &&
1138
relation->type == OSL_TYPE_SCATTERING) {
1139
1140
for (i = 0 ; i < 2 ; i++) {
1141
for (j = 0; j < relation->nb_columns; j++) {
1142
if (j == index_output_dims && i == 0)
1143
snprintf(buffer, OSL_MAX_STRING, " 1 "); // fakeiter
1144
else
1145
snprintf(buffer, OSL_MAX_STRING, " 0 ");
1146
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1147
}
1148
snprintf(buffer, OSL_MAX_STRING, "\n");
1149
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1150
}
1151
}
1152
1153
}
1154
1155
// Free the array of strings.
1156
if (name_array != NULL) {
1157
for (i = 0; i < relation->nb_columns; i++)
1158
free(name_array[i]);
1159
free(name_array);
1160
}
1161
1162
relation = relation->next;
1163
}
1164
1165
if (generated_names)
1166
osl_names_free(names);
1167
1168
return string;
1169
}
1170
1171
1172
/**
1173
* osl_relation_spprint function:
1174
* this function pretty-prints the content of an osl_relation_t structure
1175
* (*relation) into a string in the OpenScop format, and returns this string.
1176
* \param[in] relation The relation whose information has to be printed.
1177
* \param[in] names The names of the constraint columns for comments.
1178
* \return A string
1179
*/
1180
char * osl_relation_spprint(osl_relation_p relation, osl_names_p names) {
1181
int high_water_mark = OSL_MAX_STRING;
1182
char * string = NULL;
1183
char * temp;
1184
char buffer[OSL_MAX_STRING];
1185
OSL_malloc(string, char *, high_water_mark * sizeof(char));
1186
string[0] = '\0';
1187
1188
if (osl_relation_nb_components(relation) > 0) {
1189
temp = osl_relation_sprint_type(relation);
1190
osl_util_safe_strcat(&string, temp, &high_water_mark);
1191
free(temp);
1192
1193
snprintf(buffer, OSL_MAX_STRING, "\n");
1194
osl_util_safe_strcat(&string, buffer, &high_water_mark);
1195
1196
temp = osl_relation_spprint_polylib(relation, names);
1197
osl_util_safe_strcat(&string, temp, &high_water_mark);
1198
free(temp);
1199
}
1200
1201
return string;
1202
}
1203
1204
1205
/**
1206
* osl_relation_spprint_scoplib function:
1207
* this function pretty-prints the content of an osl_relation_t structure
1208
* (*relation) into a string in the SCoPLib format, and returns this string.
1209
* \param[in] relation The relation whose information has to be printed.
1210
* \param[in] names The names of the constraint columns for comments.
1211
* \param[in] print_nth_part Print the value of `n' (used for domain union)
1212
* \param[in] add_fakeiter
1213
* \return A string
1214
*/
1215
char * osl_relation_spprint_scoplib(osl_relation_p relation, osl_names_p names,
1216
int print_nth_part, int add_fakeiter) {
1217
int high_water_mark = OSL_MAX_STRING;
1218
char * string = NULL;
1219
char * temp;
1220
OSL_malloc(string, char *, high_water_mark * sizeof(char));
1221
string[0] = '\0';
1222
1223
if (relation) {
1224
temp = osl_relation_spprint_polylib_scoplib(relation, names,
1225
print_nth_part, add_fakeiter);
1226
osl_util_safe_strcat(&string, temp, &high_water_mark);
1227
free(temp);
1228
}
1229
1230
return string;
1231
}
1232
1233
1234
/**
1235
* osl_relation_pprint function:
1236
* this function pretty-prints the content of an osl_relation_t structure
1237
* (*relation) into a file (file, possibly stdout) in the OpenScop format.
1238
* \param[in] file File where informations are printed.
1239
* \param[in] relation The relation whose information has to be printed.
1240
* \param[in] names The names of the constraint columns for comments.
1241
*/
1242
void osl_relation_pprint(FILE * file, osl_relation_p relation,
1243
osl_names_p names) {
1244
char * string = osl_relation_spprint(relation, names);
1245
fprintf(file, "%s", string);
1246
free(string);
1247
}
1248
1249
1250
/**
1251
* osl_relation_pprint_scoplib function:
1252
* this function pretty-prints the content of an osl_relation_t structure
1253
* (*relation) into a file (file, possibly stdout) in the SCoPLibformat.
1254
* \param[in] file File where informations are printed.
1255
* \param[in] relation The relation whose information has to be printed.
1256
* \param[in] names The names of the constraint columns for comments.
1257
* \param[in] print_nth_part
1258
* \param[in] add_fakeiter
1259
*/
1260
void osl_relation_pprint_scoplib(FILE * file, osl_relation_p relation,
1261
osl_names_p names, int print_nth_part,
1262
int add_fakeiter) {
1263
char * string = osl_relation_spprint_scoplib(relation, names,
1264
print_nth_part, add_fakeiter);
1265
fprintf(file, "%s", string);
1266
free(string);
1267
}
1268
1269
1270
/**
1271
* osl_relation_sprint function:
1272
* this function prints the content of an osl_relation_t structure
1273
* (*relation) into a string (returned) in the OpenScop textual format.
1274
* \param[in] relation The relation structure to print.
1275
* \return A string containing the OpenScop dump of the relation structure.
1276
*/
1277
char * osl_relation_sprint(osl_relation_p relation) {
1278
1279
return osl_relation_spprint(relation, NULL);
1280
}
1281
1282
1283
/**
1284
* osl_relation_print function:
1285
* this function prints the content of an osl_relation_t structure
1286
* (*relation) into a file (file, possibly stdout) in the OpenScop format.
1287
* \param[in] file File where informations are printed.
1288
* \param[in] relation The relation whose information has to be printed.
1289
*/
1290
void osl_relation_print(FILE * file, osl_relation_p relation) {
1291
1292
osl_relation_pprint(file, relation, NULL);
1293
}
1294
1295
1296
/*****************************************************************************
1297
* Reading function *
1298
*****************************************************************************/
1299
1300
1301
/**
1302
* osl_relation_read_type function:
1303
* this function reads a textual relation type on the input 'file' or the
1304
* input string 'str' depending on which one is not NULL (exactly
1305
* one of them must not be NULL). It returns its integer counterpart.
1306
* \param[in] file The file where to read a relation type (if not NULL).
1307
* \param[in,out] str The string where to read a relation type (if not NULL).
1308
* This pointer is updated to reflect the read and points
1309
* after the tag in the input string.
1310
* \return The relation type.
1311
*/
1312
static
1313
int osl_relation_read_type(FILE * file, char ** str) {
1314
int type;
1315
osl_strings_p strings;
1316
1317
if ((file != NULL && str != NULL) || (file == NULL && str == NULL))
1318
OSL_error("one and only one of the two parameters can be non-NULL");
1319
1320
if (file != NULL)
1321
strings = osl_strings_read(file);
1322
else
1323
strings = osl_strings_sread(str);
1324
1325
if (osl_strings_size(strings) > 1) {
1326
OSL_warning("uninterpreted information (after the relation type)");
1327
}
1328
if (osl_strings_size(strings) == 0)
1329
OSL_error("no relation type");
1330
1331
if (!strcmp(strings->string[0], OSL_STRING_UNDEFINED)) {
1332
type = OSL_UNDEFINED;
1333
goto return_type;
1334
}
1335
1336
if (!strcmp(strings->string[0], OSL_STRING_CONTEXT)) {
1337
type = OSL_TYPE_CONTEXT;
1338
goto return_type;
1339
}
1340
1341
if (!strcmp(strings->string[0], OSL_STRING_DOMAIN)) {
1342
type = OSL_TYPE_DOMAIN;
1343
goto return_type;
1344
}
1345
1346
if (!strcmp(strings->string[0], OSL_STRING_SCATTERING)) {
1347
type = OSL_TYPE_SCATTERING;
1348
goto return_type;
1349
}
1350
1351
if (!strcmp(strings->string[0], OSL_STRING_READ)) {
1352
type = OSL_TYPE_READ;
1353
goto return_type;
1354
}
1355
1356
if (!strcmp(strings->string[0], OSL_STRING_WRITE)) {
1357
type = OSL_TYPE_WRITE;
1358
goto return_type;
1359
}
1360
1361
if (!strcmp(strings->string[0], OSL_STRING_MAY_WRITE)) {
1362
type = OSL_TYPE_MAY_WRITE;
1363
goto return_type;
1364
}
1365
1366
OSL_error("relation type not supported");
1367
1368
return_type:
1369
osl_strings_free(strings);
1370
return type;
1371
}
1372
1373
1374
/**
1375
* osl_relation_pread function ("precision read"):
1376
* this function reads a relation into a file (foo, posibly stdin) and
1377
* returns a pointer this relation.
1378
* \param[in] foo The input stream.
1379
* \param[in] precision The precision of the relation elements.
1380
* \return A pointer to the relation structure that has been read.
1381
*/
1382
osl_relation_p osl_relation_pread(FILE * foo, int precision) {
1383
int i, j, k, n, read = 0;
1384
int nb_rows, nb_columns;
1385
int nb_output_dims, nb_input_dims, nb_local_dims, nb_parameters;
1386
int nb_union_parts = 1;
1387
int may_read_nb_union_parts = 1;
1388
int read_attributes = 1;
1389
int first = 1;
1390
int type;
1391
char * c, s[OSL_MAX_STRING], str[OSL_MAX_STRING], *tmp;
1392
osl_relation_p relation, relation_union = NULL, previous = NULL;
1393
1394
type = osl_relation_read_type(foo, NULL);
1395
1396
// Read each part of the union (the number of parts may be updated inside)
1397
for (k = 0; k < nb_union_parts; k++) {
1398
// Read the number of union parts or the attributes of the union part
1399
while (read_attributes) {
1400
read_attributes = 0;
1401
1402
// Read relation attributes.
1403
c = osl_util_skip_blank_and_comments(foo, s);
1404
read = sscanf(c, " %d %d %d %d %d %d", &nb_rows, &nb_columns,
1405
&nb_output_dims, &nb_input_dims,
1406
&nb_local_dims, &nb_parameters);
1407
1408
if (((read != 1) && (read != 6)) ||
1409
((read == 1) && (may_read_nb_union_parts != 1)))
1410
OSL_error("not 1 or 6 integers on the first relation line");
1411
1412
if (read == 1) {
1413
// Only one number means a union and is the number of parts.
1414
nb_union_parts = nb_rows;
1415
if (nb_union_parts < 1)
1416
OSL_error("negative nb of union parts");
1417
1418
// Allow to read the properties of the first part of the union.
1419
read_attributes = 1;
1420
}
1421
1422
may_read_nb_union_parts = 0;
1423
}
1424
1425
// Allocate the union part and fill its properties.
1426
relation = osl_relation_pmalloc(precision, nb_rows, nb_columns);
1427
relation->type = type;
1428
relation->nb_output_dims = nb_output_dims;
1429
relation->nb_input_dims = nb_input_dims;
1430
relation->nb_local_dims = nb_local_dims;
1431
relation->nb_parameters = nb_parameters;
1432
1433
// Read the matrix of constraints.
1434
for (i = 0; i < relation->nb_rows; i++) {
1435
c = osl_util_skip_blank_and_comments(foo, s);
1436
if (c == NULL)
1437
OSL_error("not enough rows");
1438
1439
for (j = 0; j < relation->nb_columns; j++) {
1440
if (c == NULL || *c == '#' || *c == '\n')
1441
OSL_error("not enough columns");
1442
if (sscanf(c, "%s%n", str, &n) == 0)
1443
OSL_error("not enough rows");
1444
1445
// TODO: remove this tmp (sread updates the pointer).
1446
tmp = str;
1447
osl_int_sread(&tmp, precision, &relation->m[i][j]);
1448
c += n;
1449
}
1450
}
1451
1452
// Build the linked list of union parts.
1453
if (first == 1) {
1454
relation_union = relation;
1455
first = 0;
1456
}
1457
else {
1458
previous->next = relation;
1459
}
1460
1461
previous = relation;
1462
read_attributes = 1;
1463
}
1464
1465
return relation_union;
1466
}
1467
1468
1469
/**
1470
* osl_relation_psread function ("precision read"):
1471
* this function reads a relation from a string complying to the OpenScop
1472
* textual format and returns a pointer this relation. The input parameter
1473
* is updated to the position in the input string this function reach right
1474
* after reading the generic structure.
1475
* \param[in,out] input The input string where to find a relation.
1476
* Updated to the position after what has been read.
1477
* \param[in] precision The precision of the relation elements.
1478
* \return A pointer to the relation structure that has been read.
1479
*/
1480
osl_relation_p osl_relation_psread(char ** input, int precision) {
1481
int i, j, k, n, read = 0;
1482
int nb_rows, nb_columns;
1483
int nb_output_dims, nb_input_dims, nb_local_dims, nb_parameters;
1484
int nb_union_parts = 1;
1485
int may_read_nb_union_parts = 1;
1486
int read_attributes = 1;
1487
int first = 1;
1488
int type;
1489
char str[OSL_MAX_STRING], *tmp;
1490
osl_relation_p relation, relation_union = NULL, previous = NULL;
1491
1492
type = osl_relation_read_type(NULL, input);
1493
1494
// Read each part of the union (the number of parts may be updated inside)
1495
for (k = 0; k < nb_union_parts; k++) {
1496
// Read the number of union parts or the attributes of the union part
1497
while (read_attributes) {
1498
read_attributes = 0;
1499
1500
// Read relation attributes.
1501
osl_util_sskip_blank_and_comments(input);
1502
1503
read = sscanf(*input, " %d %d %d %d %d %d%n",
1504
&nb_rows, &nb_columns,
1505
&nb_output_dims, &nb_input_dims,
1506
&nb_local_dims, &nb_parameters, &n);
1507
*input += n;
1508
1509
if (((read != 1) && (read != 6)) ||
1510
((read == 1) && (may_read_nb_union_parts != 1)))
1511
OSL_error("not 1 or 6 integers on the first relation line");
1512
1513
if (read == 1) {
1514
// Only one number means a union and is the number of parts.
1515
nb_union_parts = nb_rows;
1516
if (nb_union_parts < 1)
1517
OSL_error("negative nb of union parts");
1518
1519
// Allow to read the properties of the first part of the union.
1520
read_attributes = 1;
1521
}
1522
1523
may_read_nb_union_parts = 0;
1524
}
1525
1526
// Allocate the union part and fill its properties.
1527
relation = osl_relation_pmalloc(precision, nb_rows, nb_columns);
1528
relation->type = type;
1529
relation->nb_output_dims = nb_output_dims;
1530
relation->nb_input_dims = nb_input_dims;
1531
relation->nb_local_dims = nb_local_dims;
1532
relation->nb_parameters = nb_parameters;
1533
1534
// Read the matrix of constraints.
1535
for (i = 0; i < relation->nb_rows; i++) {
1536
osl_util_sskip_blank_and_comments(input);
1537
if (!(*input))
1538
OSL_error("not enough rows");
1539
1540
for (j = 0; j < relation->nb_columns; j++) {
1541
if (*input == NULL || **input == '#' || **input == '\n')
1542
OSL_error("not enough columns");
1543
if (sscanf(*input, "%s%n", str, &n) == 0)
1544
OSL_error("not enough rows");
1545
1546
// TODO: remove this tmp (sread updates the pointer).
1547
tmp = str;
1548
osl_int_sread(&tmp, precision, &relation->m[i][j]);
1549
*input += n;
1550
}
1551
}
1552
1553
// Build the linked list of union parts.
1554
if (first == 1) {
1555
relation_union = relation;
1556
first = 0;
1557
}
1558
else {
1559
previous->next = relation;
1560
}
1561
1562
previous = relation;
1563
read_attributes = 1;
1564
}
1565
1566
return relation_union;
1567
}
1568
1569
1570
/**
1571
* osl_relation_sread function:
1572
* this function is equivalent to osl_relation_psread() except that
1573
* the precision corresponds to the precision environment variable or
1574
* to the highest available precision if it is not defined.
1575
* \see{osl_relation_psread}
1576
*/
1577
osl_relation_p osl_relation_sread(char ** input) {
1578
int precision = osl_util_get_precision();
1579
return osl_relation_psread(input, precision);
1580
}
1581
1582
1583
/**
1584
* osl_relation_read function:
1585
* this function is equivalent to osl_relation_pread() except that
1586
* the precision corresponds to the precision environment variable or
1587
* to the highest available precision if it is not defined.
1588
* \see{osl_relation_pread}
1589
*/
1590
osl_relation_p osl_relation_read(FILE * foo) {
1591
int precision = osl_util_get_precision();
1592
return osl_relation_pread(foo, precision);
1593
}
1594
1595
1596
/*+***************************************************************************
1597
* Memory allocation/deallocation function *
1598
*****************************************************************************/
1599
1600
1601
/**
1602
* osl_relation_pmalloc function:
1603
* (precision malloc) this function allocates the memory space for an
1604
* osl_relation_t structure and sets its fields with default values.
1605
* Then it returns a pointer to the allocated space.
1606
* \param[in] precision The precision of the constraint matrix.
1607
* \param[in] nb_rows The number of row of the relation to allocate.
1608
* \param[in] nb_columns The number of columns of the relation to allocate.
1609
* \return A pointer to an empty relation with fields set to default values
1610
* and a ready-to-use constraint matrix.
1611
*/
1612
osl_relation_p osl_relation_pmalloc(int precision,
1613
int nb_rows, int nb_columns) {
1614
osl_relation_p relation;
1615
osl_int_t ** p, * q;
1616
int i, j;
1617
1618
if ((precision != OSL_PRECISION_SP) &&
1619
(precision != OSL_PRECISION_DP) &&
1620
(precision != OSL_PRECISION_MP))
1621
OSL_error("unknown precision");
1622
1623
if ((nb_rows < 0) || (nb_columns < 0))
1624
OSL_error("negative sizes");
1625
1626
OSL_malloc(relation, osl_relation_p, sizeof(osl_relation_t));
1627
relation->type = OSL_UNDEFINED;
1628
relation->nb_rows = nb_rows;
1629
relation->nb_columns = nb_columns;
1630
relation->nb_output_dims = OSL_UNDEFINED;
1631
relation->nb_input_dims = OSL_UNDEFINED;
1632
relation->nb_parameters = OSL_UNDEFINED;
1633
relation->nb_local_dims = OSL_UNDEFINED;
1634
relation->precision = precision;
1635
1636
if ((nb_rows == 0) || (nb_columns == 0) ||
1637
(nb_rows == OSL_UNDEFINED) || (nb_columns == OSL_UNDEFINED)) {
1638
relation->m = NULL;
1639
}
1640
else {
1641
OSL_malloc(p, osl_int_t**, nb_rows * sizeof(osl_int_t*));
1642
OSL_malloc(q, osl_int_t*, nb_rows * nb_columns * sizeof(osl_int_t));
1643
relation->m = p;
1644
for (i = 0; i < nb_rows; i++) {
1645
relation->m[i] = q + i * nb_columns ;
1646
for (j = 0; j < nb_columns; j++)
1647
osl_int_init_set_si(precision, &relation->m[i][j], 0);
1648
}
1649
}
1650
1651
relation->next = NULL;
1652
1653
return relation;
1654
}
1655
1656
1657
/**
1658
* osl_relation_malloc function:
1659
* this function is equivalent to osl_relation_pmalloc() except that
1660
* the precision corresponds to the precision environment variable or
1661
* to the highest available precision if it is not defined.
1662
* \see{osl_relation_pmalloc}
1663
*/
1664
osl_relation_p osl_relation_malloc(int nb_rows, int nb_columns) {
1665
int precision = osl_util_get_precision();
1666
return osl_relation_pmalloc(precision, nb_rows, nb_columns);
1667
}
1668
1669
1670
/**
1671
* osl_relation_free_inside function:
1672
* this function frees the allocated memory for the inside of a
1673
* osl_relation_t structure, i.e. only m.
1674
* \param[in] relation The pointer to the relation we want to free internals.
1675
*/
1676
void osl_relation_free_inside(osl_relation_p relation) {
1677
int i, nb_elements;
1678
1679
if (relation == NULL)
1680
return;
1681
1682
nb_elements = relation->nb_rows * relation->nb_columns;
1683
1684
for (i = 0; i < nb_elements; i++)
1685
osl_int_clear(relation->precision, &relation->m[0][i]);
1686
1687
if (relation->m != NULL) {
1688
if (nb_elements > 0)
1689
free(relation->m[0]);
1690
free(relation->m);
1691
}
1692
}
1693
1694
1695
/**
1696
* osl_relation_free function:
1697
* this function frees the allocated memory for an osl_relation_t
1698
* structure.
1699
* \param[in] relation The pointer to the relation we want to free.
1700
*/
1701
void osl_relation_free(osl_relation_p relation) {
1702
osl_relation_p tmp;
1703
1704
while (relation != NULL) {
1705
tmp = relation->next;
1706
osl_relation_free_inside(relation);
1707
free(relation);
1708
relation = tmp;
1709
}
1710
}
1711
1712
1713
/*+***************************************************************************
1714
* Processing functions *
1715
*****************************************************************************/
1716
1717
1718
/**
1719
* osl_relation_nclone function:
1720
* this functions builds and returns a "hard copy" (not a pointer copy) of the
1721
* first n parts of a relation union.
1722
* \param[in] relation The pointer to the relation we want to clone.
1723
* \param[in] n The number of union parts of the relation we want to
1724
* clone (the special value -1 means "all the parts").
1725
* \return A pointer to the clone of the relation union restricted to the
1726
* first n parts of the relation union.
1727
*/
1728
osl_relation_p osl_relation_nclone(osl_relation_p relation, int n) {
1729
int i, j, k;
1730
int first = 1, nb_components, nb_parts;
1731
osl_relation_p clone = NULL, node, previous = NULL;
1732
1733
nb_components = osl_relation_nb_components(relation);
1734
nb_parts = (n == -1) ? nb_components : n;
1735
if (nb_components < nb_parts)
1736
OSL_error("not enough union parts to clone");
1737
1738
for (k = 0; k < nb_parts; k++) {
1739
node = osl_relation_pmalloc(relation->precision,
1740
relation->nb_rows, relation->nb_columns);
1741
node->type = relation->type;
1742
node->nb_output_dims = relation->nb_output_dims;
1743
node->nb_input_dims = relation->nb_input_dims;
1744
node->nb_local_dims = relation->nb_local_dims;
1745
node->nb_parameters = relation->nb_parameters;
1746
1747
for (i = 0; i < relation->nb_rows; i++)
1748
for (j = 0; j < relation->nb_columns; j++)
1749
osl_int_assign(relation->precision,
1750
&node->m[i][j], relation->m[i][j]);
1751
1752
if (first) {
1753
first = 0;
1754
clone = node;
1755
previous = node;
1756
}
1757
else {
1758
previous->next = node;
1759
previous = previous->next;
1760
}
1761
1762
relation = relation->next;
1763
}
1764
1765
return clone;
1766
}
1767
1768
1769
/**
1770
* osl_relation_clone_nconstraints function:
1771
* this functions builds and returns a "hard copy" (not a pointer copy) of a
1772
* osl_relation_t data structure such that the clone is restricted to the
1773
* "n" first rows of the relation. This applies to all the parts in the case
1774
* of a relation union.
1775
* \param[in] relation The pointer to the relation we want to clone.
1776
* \param[in] n The number of row of the relation we want to clone (the
1777
* special value -1 means "all the rows").
1778
* \return A pointer to the clone of the relation union restricted to the
1779
* first n rows of constraint matrix for each part of the union.
1780
*/
1781
osl_relation_p osl_relation_clone_nconstraints(osl_relation_p relation,
1782
int n) {
1783
int i, j;
1784
int first = 1, all_rows = 0;
1785
osl_relation_p clone = NULL, node, previous = NULL;
1786
1787
if (n == -1)
1788
all_rows = 1;
1789
1790
while (relation != NULL) {
1791
if (all_rows)
1792
n = relation->nb_rows;
1793
1794
if (n > relation->nb_rows)
1795
OSL_error("not enough rows to clone in the relation");
1796
1797
node = osl_relation_pmalloc(relation->precision, n, relation->nb_columns);
1798
node->type = relation->type;
1799
node->nb_output_dims = relation->nb_output_dims;
1800
node->nb_input_dims = relation->nb_input_dims;
1801
node->nb_local_dims = relation->nb_local_dims;
1802
node->nb_parameters = relation->nb_parameters;
1803
1804
for (i = 0; i < n; i++)
1805
for (j = 0; j < relation->nb_columns; j++)
1806
osl_int_assign(relation->precision,
1807
&node->m[i][j], relation->m[i][j]);
1808
1809
if (first) {
1810
first = 0;
1811
clone = node;
1812
previous = node;
1813
}
1814
else {
1815
previous->next = node;
1816
previous = previous->next;
1817
}
1818
1819
relation = relation->next;
1820
}
1821
1822
return clone;
1823
}
1824
1825
1826
/**
1827
* osl_relation_clone function:
1828
* this function builds and returns a "hard copy" (not a pointer copy) of an
1829
* osl_relation_t data structure (the full union of relation).
1830
* \param[in] relation The pointer to the relation we want to clone.
1831
* \return A pointer to the clone of the union of relations.
1832
*/
1833
osl_relation_p osl_relation_clone(osl_relation_p relation) {
1834
if (relation == NULL)
1835
return NULL;
1836
1837
return osl_relation_nclone(relation, -1);
1838
}
1839
1840
1841
/**
1842
* osl_relation_add function:
1843
* this function adds a relation (union) at the end of the relation (union)
1844
* pointed by r1. No new relation is created: this functions links the two
1845
* input unions. If the first relation is NULL, it is set to the
1846
* second relation.
1847
* \param[in,out] r1 Pointer to the first relation (union).
1848
* \param[in] r2 The second relation (union).
1849
*/
1850
void osl_relation_add(osl_relation_p *r1, osl_relation_p r2) {
1851
while (*r1 != NULL)
1852
r1 = &((*r1)->next);
1853
1854
*r1 = r2;
1855
}
1856
1857
1858
/**
1859
* osl_relation_union function:
1860
* this function builds a new relation from two relations provided
1861
* as parameters. The new relation is built as an union of the
1862
* two relations: the list of constraint sets are linked together.
1863
* \param[in] r1 The first relation.
1864
* \param[in] r2 The second relation.
1865
* \return A new relation corresponding to the union of r1 and r2.
1866
*/
1867
osl_relation_p osl_relation_union(osl_relation_p r1,
1868
osl_relation_p r2) {
1869
osl_relation_p copy1, copy2;
1870
1871
if ((r1 == NULL) && (r2 == NULL))
1872
return NULL;
1873
1874
copy1 = osl_relation_clone(r1);
1875
copy2 = osl_relation_clone(r2);
1876
osl_relation_add(©1, copy2);
1877
1878
return copy1;
1879
}
1880
1881
1882
/**
1883
* osl_relation_replace_vector function:
1884
* this function replaces the "row"^th row of a relation "relation" with the
1885
* vector "vector". It directly updates the relation union part pointed
1886
* by "relation" and this part only.
1887
* \param[in,out] relation The relation we want to replace a row.
1888
* \param[in] vector The vector that will replace a row of the relation.
1889
* \param[in] row The row of the relation to be replaced.
1890
*/
1891
void osl_relation_replace_vector(osl_relation_p relation,
1892
osl_vector_p vector, int row) {
1893
int i;
1894
1895
if ((relation == NULL) || (vector == NULL) ||
1896
(relation->precision != vector->precision) ||
1897
(relation->nb_columns != vector->size) ||
1898
(row >= relation->nb_rows) || (row < 0))
1899
OSL_error("vector cannot replace relation row");
1900
1901
for (i = 0; i < vector->size; i++)
1902
osl_int_assign(relation->precision, &relation->m[row][i], vector->v[i]);
1903
}
1904
1905
1906
/**
1907
* osl_relation_add_vector function:
1908
* this function adds (meaning, +) a vector to the "row"^th row of a
1909
* relation "relation". It directly updates the relation union part pointed
1910
* by "relation" and this part only.
1911
* \param[in,out] relation The relation we want to add a vector to a row.
1912
* \param[in] vector The vector that will replace a row of the relation.
1913
* \param[in] row The row of the relation to add the vector.
1914
*/
1915
void osl_relation_add_vector(osl_relation_p relation,
1916
osl_vector_p vector, int row) {
1917
int i;
1918
1919
if ((relation == NULL) || (vector == NULL) ||
1920
(relation->precision != vector->precision) ||
1921
(relation->nb_columns != vector->size) ||
1922
(row >= relation->nb_rows) || (row < 0))
1923
OSL_error("vector cannot be added to relation");
1924
1925
if (osl_int_get_si(relation->precision, relation->m[row][0]) == 0)
1926
osl_int_assign(relation->precision, &relation->m[row][0], vector->v[0]);
1927
1928
for (i = 1; i < vector->size; i++)
1929
osl_int_add(relation->precision,
1930
&relation->m[row][i], relation->m[row][i], vector->v[i]);
1931
}
1932
1933
1934
/**
1935
* osl_relation_sub_vector function:
1936
* this function subtracts the vector "vector" to the "row"^th row of
1937
* a relation "relation. It directly updates the relation union part pointed
1938
* by "relation" and this part only.
1939
* \param[in,out] relation The relation where to subtract a vector to a row.
1940
* \param[in] vector The vector to subtract to a relation row.
1941
* \param[in] row The row of the relation to subtract the vector.
1942
*/
1943
void osl_relation_sub_vector(osl_relation_p relation,
1944
osl_vector_p vector, int row) {
1945
int i;
1946
1947
if ((relation == NULL) || (vector == NULL) ||
1948
(relation->precision != vector->precision) ||
1949
(relation->nb_columns != vector->size) ||
1950
(row >= relation->nb_rows) || (row < 0))
1951
OSL_error("vector cannot be subtracted to row");
1952
1953
if (osl_int_get_si(relation->precision, relation->m[row][0]) == 0)
1954
osl_int_assign(relation->precision, &relation->m[row][0], vector->v[0]);
1955
1956
for (i = 1; i < vector->size; i++)
1957
osl_int_sub(relation->precision,
1958
&relation->m[row][i], relation->m[row][i], vector->v[i]);
1959
}
1960
1961
1962
/**
1963
* osl_relation_insert_vector function:
1964
* this function inserts a new row corresponding to the vector "vector" to
1965
* the relation "relation" by inserting it at the "row"^th row of
1966
* "relation" (-1 is a shortcut to insert the vector after the constraints
1967
* of the relation). It directly updates the relation union part pointed
1968
* by "relation" and this part only. If "vector" (or "relation") is NULL,
1969
* the relation is left unmodified.
1970
* \param[in,out] relation The relation we want to extend.
1971
* \param[in] vector The vector that will be added relation.
1972
* \param[in] row The row where to insert the vector (-1 to
1973
* insert it after the relation constraints).
1974
*/
1975
void osl_relation_insert_vector(osl_relation_p relation,
1976
osl_vector_p vector, int row) {
1977
osl_relation_p temp;
1978
1979
temp = osl_relation_from_vector(vector);
1980
osl_relation_insert_constraints(relation, temp, row);
1981
osl_relation_free(temp);
1982
}
1983
1984
1985
/**
1986
* osl_relation_concat_vector function:
1987
* this function builds a new relation from one relation and a vector sent as
1988
* parameters. The new set of constraints is built as the concatenation
1989
* of the rows of the first part of the relation and of the vector
1990
* constraint. This means, there is no next field in the result.
1991
* \param[in] r The input relation.
1992
* \param[in] v The input vector.
1993
* \return A pointer to the relation resulting from the concatenation of
1994
* the constraints of the relation and of the vector.
1995
*/
1996
osl_relation_p osl_relation_concat_vector(osl_relation_p relation,
1997
osl_vector_p vector) {
1998
osl_relation_p new, temp;
1999
2000
temp = osl_relation_from_vector(vector);
2001
new = osl_relation_concat_constraints(relation, temp);
2002
osl_relation_free(temp);
2003
return new;
2004
}
2005
2006
2007
/**
2008
* osl_relation_insert_blank_row function:
2009
* this function inserts a new row filled with zeros o an existing relation
2010
* union part (it only affects the first union part).
2011
* \param[in,out] relation The relation to add a row in.
2012
* \param[in] row The row where to insert the blank row.
2013
*/
2014
void osl_relation_insert_blank_row(osl_relation_p relation, int row) {
2015
osl_vector_p vector;
2016
2017
if (relation != NULL) {
2018
vector = osl_vector_pmalloc(relation->precision, relation->nb_columns);
2019
osl_relation_insert_vector(relation, vector, row);
2020
osl_vector_free(vector);
2021
}
2022
}
2023
2024
2025
/**
2026
* osl_relation_insert_blank_column function:
2027
* this function inserts a new column filled with zeros to an existing
2028
* relation union part (it only affects the first union part). WARNING:
2029
* this function does not update the relation attributes.
2030
* \param[in,out] relation The relation to add a column in.
2031
* \param[in] column The column where to insert the blank column.
2032
*/
2033
void osl_relation_insert_blank_column(osl_relation_p relation, int column) {
2034
2035
int i, j;
2036
osl_relation_p temp;
2037
2038
if (relation == NULL)
2039
return;
2040
2041
if ((column < 0) || (column > relation->nb_columns))
2042
OSL_error("bad column number");
2043
2044
// We use a temporary relation just to reuse existing functions. Cleaner.
2045
temp = osl_relation_pmalloc(relation->precision,
2046
relation->nb_rows, relation->nb_columns + 1);
2047
2048
for (i = 0; i < relation->nb_rows; i++) {
2049
for (j = 0; j < column; j++)
2050
osl_int_assign(relation->precision, &temp->m[i][j], relation->m[i][j]);
2051
2052
for (j = column; j < relation->nb_columns; j++)
2053
osl_int_assign(relation->precision, &temp->m[i][j+1], relation->m[i][j]);
2054
}
2055
2056
osl_relation_free_inside(relation);
2057
2058
// Replace the inside of relation.
2059
relation->nb_columns = temp->nb_columns;
2060
relation->m = temp->m;
2061
2062
// Free the temp "shell".
2063
free(temp);
2064
}
2065
2066
2067
/**
2068
* osl_relation_from_vector function:
2069
* this function converts a vector "vector" to a relation with a single row
2070
* and returns a pointer to that relation.
2071
* \param[in] vector The vector to convert to a relation.
2072
* \return A pointer to a relation resulting from the vector conversion.
2073
*/
2074
osl_relation_p osl_relation_from_vector(osl_vector_p vector) {
2075
osl_relation_p relation;
2076
2077
if (vector == NULL)
2078
return NULL;
2079
2080
relation = osl_relation_pmalloc(vector->precision, 1, vector->size);
2081
osl_relation_replace_vector(relation, vector, 0);
2082
return relation;
2083
}
2084
2085
2086
/**
2087
* osl_relation_replace_constraints function:
2088
* this function replaces some rows of a relation "r1" with the rows of
2089
* the relation "r2". It begins at the "row"^th row of "r1". It directly
2090
* updates the relation union part pointed by "r1" and this part only.
2091
* \param[in,out] r1 The relation we want to change some rows.
2092
* \param[in] r2 The relation containing the new rows.
2093
* \param[in] row The first row of the relation r1 to be replaced.
2094
*/
2095
void osl_relation_replace_constraints(osl_relation_p r1,
2096
osl_relation_p r2, int row) {
2097
int i, j;
2098
2099
if ((r1 == NULL) || (r2 == NULL) ||
2100
(r1->precision != r2->precision) ||
2101
(r1->nb_columns != r1->nb_columns) ||
2102
((row + r2->nb_rows) > r1->nb_rows) || (row < 0))
2103
OSL_error("relation rows could not be replaced");
2104
2105
for (i = 0; i < r2->nb_rows; i++)
2106
for (j = 0; j < r2->nb_columns; j++)
2107
osl_int_assign(r1->precision, &r1->m[i+row][j], r2->m[i][j]);
2108
}
2109
2110
2111
/**
2112
* osl_relation_insert_constraints function:
2113
* this function inserts the rows of the relation "r2" to the relation
2114
* "r1", starting from the "row"^th row of "r1" (-1 is a
2115
* shortcut to insert the "r2" constraints after the constraints of r1).
2116
* It directly updates the relation union part pointed by "r1" and this
2117
* part only. If "r2" (or "r1") is NULL, the relation is left unmodified.
2118
* \param[in,out] r1 The relation we want to extend.
2119
* \param[in] r2 The relation to be inserted.
2120
* \param[in] row The row where to insert the constraints (-1 to
2121
* insert them after those of "r1").
2122
*/
2123
void osl_relation_insert_constraints(osl_relation_p r1,
2124
osl_relation_p r2, int row) {
2125
int i, j;
2126
osl_relation_p temp;
2127
2128
if ((r1 == NULL) || (r2 == NULL))
2129
return;
2130
2131
if (row == -1)
2132
row = r1->nb_rows;
2133
2134
if ((r1->nb_columns != r2->nb_columns) ||
2135
(r1->precision != r2->precision) ||
2136
(row > r1->nb_rows) || (row < 0))
2137
OSL_error("constraints cannot be inserted");
2138
2139
// We use a temporary relation just to reuse existing functions. Cleaner.
2140
temp = osl_relation_pmalloc(r1->precision,
2141
r1->nb_rows + r2->nb_rows, r1->nb_columns);
2142
2143
for (i = 0; i < row; i++)
2144
for (j = 0; j < r1->nb_columns; j++)
2145
osl_int_assign(r1->precision, &temp->m[i][j], r1->m[i][j]);
2146
2147
osl_relation_replace_constraints(temp, r2, row);
2148
2149
for (i = row + r2->nb_rows; i < r2->nb_rows + r1->nb_rows; i++)
2150
for (j = 0; j < r1->nb_columns; j++)
2151
osl_int_assign(r1->precision, &temp->m[i][j], r1->m[i-r2->nb_rows][j]);
2152
2153
osl_relation_free_inside(r1);
2154
2155
// Replace the inside of relation.
2156
r1->nb_rows = temp->nb_rows;
2157
r1->m = temp->m;
2158
2159
// Free the temp "shell".
2160
free(temp);
2161
}
2162
2163
2164
/**
2165
* osl_relation_swap_constraints function:
2166
* this function swaps two constraints (i.e., rows) of the relation matrix.
2167
* This function updates the relation directly.
2168
* \param[in,out] relation The relation to swap two rows (modified).
2169
* \param[in] c1 The row corresponding to the first constraint.
2170
* \param[in] c2 The row corresponding to the second constraint.
2171
*/
2172
void osl_relation_swap_constraints(osl_relation_p relation, int c1, int c2) {
2173
int i;
2174
2175
if ((relation == NULL) || (c1 == c2))
2176
return;
2177
2178
if ((c1 >= relation->nb_rows) || (c1 < 0) ||
2179
(c2 >= relation->nb_rows) || (c2 < 0))
2180
OSL_error("bad constraint rows");
2181
2182
for (i = 0; i < relation->nb_columns; i++)
2183
osl_int_swap(relation->precision,
2184
&relation->m[c1][i], &relation->m[c2][i]);
2185
}
2186
2187
2188
/**
2189
* osl_relation_remove_row function:
2190
* this function removes a given row to the relation "r". It directly
2191
* updates the relation union part pointed by "r" and this part only.
2192
* \param[in,out] r The relation to remove a row.
2193
* \param[in] row The row number to remove.
2194
*/
2195
void osl_relation_remove_row(osl_relation_p r, int row) {
2196
int i, j;
2197
osl_relation_p temp;
2198
2199
if (r == NULL)
2200
return;
2201
2202
if ((row < 0) || (row >= r->nb_rows))
2203
OSL_error("bad row number");
2204
2205
// We use a temporary relation just to reuse existing functions. Cleaner.
2206
temp = osl_relation_pmalloc(r->precision,
2207
r->nb_rows - 1, r->nb_columns);
2208
2209
for (i = 0; i < row; i++)
2210
for (j = 0; j < r->nb_columns; j++)
2211
osl_int_assign(r->precision, &temp->m[i][j], r->m[i][j]);
2212
2213
for (i = row + 1; i < r->nb_rows; i++)
2214
for (j = 0; j < r->nb_columns; j++)
2215
osl_int_assign(r->precision, &temp->m[i - 1][j], r->m[i][j]);
2216
2217
osl_relation_free_inside(r);
2218
2219
// Replace the inside of relation.
2220
r->nb_rows = temp->nb_rows;
2221
r->m = temp->m;
2222
2223
// Free the temp "shell".
2224
free(temp);
2225
}
2226
2227
2228
/**
2229
* osl_relation_remove_column function:
2230
* this function removes a given column to the relation "r". It directly
2231
* updates the relation union part pointed by "r" and this part only.
2232
* \param[in,out] r The relation to remove a column.
2233
* \param[in] column The column number to remove.
2234
*/
2235
void osl_relation_remove_column(osl_relation_p r, int column) {
2236
int i, j;
2237
osl_relation_p temp;
2238
2239
if (r == NULL)
2240
return;
2241
2242
if ((column < 0) || (column >= r->nb_columns))
2243
OSL_error("bad column number");
2244
2245
// We use a temporary relation just to reuse existing functions. Cleaner.
2246
temp = osl_relation_pmalloc(r->precision,
2247
r->nb_rows, r->nb_columns - 1);
2248
2249
for (i = 0; i < r->nb_rows; i++) {
2250
for (j = 0; j < column; j++)
2251
osl_int_assign(r->precision, &temp->m[i][j], r->m[i][j]);
2252
2253
for (j = column + 1; j < r->nb_columns; j++)
2254
osl_int_assign(r->precision, &temp->m[i][j - 1], r->m[i][j]);
2255
}
2256
2257
osl_relation_free_inside(r);
2258
2259
// Replace the inside of relation.
2260
r->nb_rows = temp->nb_rows;
2261
r->m = temp->m;
2262
2263
// Free the temp "shell".
2264
free(temp);
2265
}
2266
2267
2268
/**
2269
* osl_relation_insert_columns function:
2270
* this function inserts new columns to an existing relation union part (it
2271
* only affects the first union part). The columns are copied out from the
2272
* matrix of an input relation which must have the convenient number of rows.
2273
* All columns of the input matrix are copied. WARNING: this function does not
2274
* update the relation attributes of the modified matrix.
2275
* \param[in,out] relation The relation to add columns in.
2276
* \param[in] insert The relation containing the columns to add.
2277
* \param[in] column The column where to insert the new columns.
2278
*/
2279
void osl_relation_insert_columns(osl_relation_p relation,
2280
osl_relation_p insert, int column) {
2281
int i, j;
2282
osl_relation_p temp;
2283
2284
if ((relation == NULL) || (insert == NULL))
2285
return;
2286
2287
if ((relation->precision != insert->precision) ||
2288
(relation->nb_rows != insert->nb_rows) ||
2289
(column < 0) || (column > relation->nb_columns))
2290
OSL_error("columns cannot be inserted");
2291
2292
// We use a temporary relation just to reuse existing functions. Cleaner.
2293
temp = osl_relation_pmalloc(relation->precision, relation->nb_rows,
2294
relation->nb_columns + insert->nb_columns);
2295
2296
for (i = 0; i < relation->nb_rows; i++) {
2297
for (j = 0; j < column; j++)
2298
osl_int_assign(relation->precision, &temp->m[i][j], relation->m[i][j]);
2299
2300
for (j = column; j < column + insert->nb_columns; j++)
2301
osl_int_assign(relation->precision,
2302
&temp->m[i][j], insert->m[i][j - column]);
2303
2304
for (j = column + insert->nb_columns;
2305
j < insert->nb_columns + relation->nb_columns; j++)
2306
osl_int_assign(relation->precision,
2307
&temp->m[i][j], relation->m[i][j - insert->nb_columns]);
2308
}
2309
2310
osl_relation_free_inside(relation);
2311
2312
// Replace the inside of relation.
2313
relation->nb_columns = temp->nb_columns;
2314
relation->m = temp->m;
2315
2316
// Free the temp "shell".
2317
free(temp);
2318
}
2319
2320
2321
/**
2322
* osl_relation_concat_constraints function:
2323
* this function builds a new relation from two relations sent as
2324
* parameters. The new set of constraints is built as the concatenation
2325
* of the rows of the first elements of the two relation unions r1 and r2.
2326
* This means, there is no next field in the result.
2327
* \param[in] r1 The first relation.
2328
* \param[in] r2 The second relation.
2329
* \return A pointer to the relation resulting from the concatenation of
2330
* the first elements of r1 and r2.
2331
*/
2332
osl_relation_p osl_relation_concat_constraints(
2333
osl_relation_p r1,
2334
osl_relation_p r2) {
2335
osl_relation_p new;
2336
2337
if (r1 == NULL)
2338
return osl_relation_clone(r2);
2339
2340
if (r2 == NULL)
2341
return osl_relation_clone(r1);
2342
2343
if (r1->nb_columns != r2->nb_columns)
2344
OSL_error("incompatible sizes for concatenation");
2345
2346
if (r1->next || r2->next)
2347
OSL_warning("relation concatenation is done on the first elements "
2348
"of union only");
2349
2350
new = osl_relation_pmalloc(r1->precision,
2351
r1->nb_rows + r2->nb_rows, r1->nb_columns);
2352
osl_relation_replace_constraints(new, r1, 0);
2353
osl_relation_replace_constraints(new, r2, r1->nb_rows);
2354
2355
return new;
2356
}
2357
2358
2359
/**
2360
* osl_relation_part_equal function:
2361
* this function returns true if the two relations parts provided as
2362
* parameters are the same, false otherwise. In the case of relation
2363
* unions, only the first part of the two relations are tested.
2364
* \param[in] r1 The first relation.
2365
* \param[in] r2 The second relation.
2366
* \return 1 if r1 and r2 are the same (content-wise), 0 otherwise.
2367
*/
2368
int osl_relation_part_equal(osl_relation_p r1, osl_relation_p r2) {
2369
int i, j;
2370
2371
if (r1 == r2)
2372
return 1;
2373
2374
if (((r1 == NULL) && (r2 != NULL)) ||
2375
((r1 != NULL) && (r2 == NULL)))
2376
return 0;
2377
2378
if ((r1->type != r2->type) ||
2379
(r1->precision != r2->precision) ||
2380
(r1->nb_rows != r2->nb_rows) ||
2381
(r1->nb_columns != r2->nb_columns) ||
2382
(r1->nb_output_dims != r2->nb_output_dims) ||
2383
(r1->nb_input_dims != r2->nb_input_dims) ||
2384
(r1->nb_local_dims != r2->nb_local_dims) ||
2385
(r1->nb_parameters != r2->nb_parameters))
2386
return 0;
2387
2388
for (i = 0; i < r1->nb_rows; ++i)
2389
for (j = 0; j < r1->nb_columns; ++j)
2390
if (osl_int_ne(r1->precision, r1->m[i][j], r2->m[i][j]))
2391
return 0;
2392
2393
return 1;
2394
}
2395
2396
2397
/**
2398
* osl_relation_equal function:
2399
* this function returns true if the two relations provided as parameters
2400
* are the same, false otherwise.
2401
* \param[in] r1 The first relation.
2402
* \param[in] r2 The second relation.
2403
* \return 1 if r1 and r2 are the same (content-wise), 0 otherwise.
2404
*/
2405
int osl_relation_equal(osl_relation_p r1, osl_relation_p r2) {
2406
while ((r1 != NULL) && (r2 != NULL)) {
2407
if (!osl_relation_part_equal(r1, r2))
2408
return 0;
2409
2410
r1 = r1->next;
2411
r2 = r2->next;
2412
}
2413
2414
if (((r1 == NULL) && (r2 != NULL)) || ((r1 != NULL) && (r2 == NULL)))
2415
return 0;
2416
2417
return 1;
2418
}
2419
2420
2421
/**
2422
* osl_relation_check_attribute internal function:
2423
* This function checks whether an "actual" value is the same as an
2424
* "expected" value or not. If the expected value is set to
2425
* OSL_UNDEFINED, this function sets it to the "actual" value
2426
* and do not report a difference has been detected.
2427
* It returns 0 if a difference has been detected, 1 otherwise.
2428
* \param[in,out] expected Pointer to the expected value (the value is
2429
* modified if it was set to OSL_UNDEFINED).
2430
* \param[in] actual Value we want to check.
2431
* \return 0 if the values are not the same while the expected value was
2432
* not OSL_UNDEFINED, 1 otherwise.
2433
*/
2434
static
2435
int osl_relation_check_attribute(int * expected, int actual) {
2436
if (*expected != OSL_UNDEFINED) {
2437
if ((actual != OSL_UNDEFINED) &&
2438
(actual != *expected)) {
2439
OSL_warning("unexpected atribute");
2440
return 0;
2441
}
2442
}
2443
else {
2444
*expected = actual;
2445
}
2446
2447
return 1;
2448
}
2449
2450
2451
/**
2452
* osl_relation_check_nb_columns internal function:
2453
* This function checks that the number of columns of a relation
2454
* corresponds to some expected properties (setting an expected property to
2455
* OSL_UNDEFINED makes this function unable to detect a problem).
2456
* It returns 0 if the number of columns seems incorrect or 1 if no problem
2457
* has been detected.
2458
* \param[in] relation The relation we want to check the number of columns.
2459
* \param[in] expected_nb_output_dims Expected number of output dimensions.
2460
* \param[in] expected_nb_input_dims Expected number of input dimensions.
2461
* \param[in] expected_nb_parameters Expected number of parameters.
2462
* \return 0 if the number of columns seems incorrect, 1 otherwise.
2463
*/
2464
static
2465
int osl_relation_check_nb_columns(osl_relation_p relation,
2466
int expected_nb_output_dims,
2467
int expected_nb_input_dims,
2468
int expected_nb_parameters) {
2469
int expected_nb_local_dims, expected_nb_columns;
2470
2471
if ((expected_nb_output_dims != OSL_UNDEFINED) &&
2472
(expected_nb_input_dims != OSL_UNDEFINED) &&
2473
(expected_nb_parameters != OSL_UNDEFINED)) {
2474
2475
if (relation->nb_local_dims == OSL_UNDEFINED)
2476
expected_nb_local_dims = 0;
2477
else
2478
expected_nb_local_dims = relation->nb_local_dims;
2479
2480
expected_nb_columns = expected_nb_output_dims +
2481
expected_nb_input_dims +
2482
expected_nb_local_dims +
2483
expected_nb_parameters +
2484
2;
2485
2486
if (expected_nb_columns != relation->nb_columns) {
2487
OSL_warning("unexpected number of columns");
2488
return 0;
2489
}
2490
}
2491
2492
return 1;
2493
}
2494
2495
2496
/**
2497
* osl_relation_integrity_check function:
2498
* this function checks that a relation is "well formed" according to some
2499
* expected properties (setting an expected value to OSL_UNDEFINED means
2500
* that we do not expect a specific value) and what the relation is supposed
2501
* to represent. It returns 0 if the check failed or 1 if no problem has been
2502
* detected.
2503
* \param[in] relation The relation we want to check.
2504
* \param[in] expected_type Semantics about this relation (domain, access...).
2505
* \param[in] expected_nb_output_dims Expected number of output dimensions.
2506
* \param[in] expected_nb_input_dims Expected number of input dimensions.
2507
* \param[in] expected_nb_parameters Expected number of parameters.
2508
* \return 0 if the integrity check fails, 1 otherwise.
2509
*/
2510
int osl_relation_integrity_check(osl_relation_p relation,
2511
int expected_type,
2512
int expected_nb_output_dims,
2513
int expected_nb_input_dims,
2514
int expected_nb_parameters) {
2515
int i;
2516
2517
// Check the NULL case.
2518
if (relation == NULL) {
2519
if ((expected_nb_output_dims != OSL_UNDEFINED) ||
2520
(expected_nb_input_dims != OSL_UNDEFINED) ||
2521
(expected_nb_parameters != OSL_UNDEFINED)) {
2522
OSL_debug("NULL relation with some expected attibutes");
2523
//return 0;
2524
}
2525
2526
return 1;
2527
}
2528
2529
// Check the type.
2530
if (((expected_type != OSL_TYPE_ACCESS) &&
2531
(expected_type != relation->type)) ||
2532
((expected_type == OSL_TYPE_ACCESS) &&
2533
(!osl_relation_is_access(relation)))) {
2534
OSL_warning("wrong type");
2535
osl_relation_dump(stderr, relation);
2536
return 0;
2537
}
2538
2539
// Check that relations have no undefined atributes.
2540
if ((relation->nb_output_dims == OSL_UNDEFINED) ||
2541
(relation->nb_input_dims == OSL_UNDEFINED) ||
2542
(relation->nb_local_dims == OSL_UNDEFINED) ||
2543
(relation->nb_parameters == OSL_UNDEFINED)) {
2544
OSL_warning("all attributes should be defined");
2545
osl_relation_dump(stderr, relation);
2546
return 0;
2547
}
2548
2549
// Check that a context has actually 0 output dimensions.
2550
if ((relation->type == OSL_TYPE_CONTEXT) &&
2551
(relation->nb_output_dims != 0)) {
2552
OSL_warning("context without 0 as number of output dimensions");
2553
osl_relation_dump(stderr, relation);
2554
return 0;
2555
}
2556
2557
// Check that a domain or a context has actually 0 input dimensions.
2558
if (((relation->type == OSL_TYPE_DOMAIN) ||
2559
(relation->type == OSL_TYPE_CONTEXT)) &&
2560
(relation->nb_input_dims != 0)) {
2561
OSL_warning("domain or context without 0 input dimensions");
2562
osl_relation_dump(stderr, relation);
2563
return 0;
2564
}
2565
2566
// Check properties according to expected values (and if expected values
2567
// are undefined, define them with the first relation part properties).
2568
if (!osl_relation_check_attribute(&expected_nb_output_dims,
2569
relation->nb_output_dims) ||
2570
!osl_relation_check_attribute(&expected_nb_input_dims,
2571
relation->nb_input_dims) ||
2572
!osl_relation_check_attribute(&expected_nb_parameters,
2573
relation->nb_parameters)) {
2574
osl_relation_dump(stderr, relation);
2575
return 0;
2576
}
2577
2578
while (relation != NULL) {
2579
2580
// Attributes (except the number of local dimensions) should be the same
2581
// in all parts of the union.
2582
if ((expected_nb_output_dims != relation->nb_output_dims) ||
2583
(expected_nb_input_dims != relation->nb_input_dims) ||
2584
(expected_nb_parameters != relation->nb_parameters)) {
2585
OSL_warning("inconsistent attributes");
2586
osl_relation_dump(stderr, relation);
2587
return 0;
2588
}
2589
2590
// Check whether the number of columns is OK or not.
2591
if (!osl_relation_check_nb_columns(relation,
2592
expected_nb_output_dims,
2593
expected_nb_input_dims,
2594
expected_nb_parameters)) {
2595
osl_relation_dump(stderr, relation);
2596
return 0;
2597
}
2598
2599
// Check the first column. The first column of a relation part should be
2600
// made of 0 or 1 only.
2601
if ((relation->nb_rows > 0) && (relation->nb_columns > 0)) {
2602
for (i = 0; i < relation->nb_rows; i++) {
2603
if (!osl_int_zero(relation->precision, relation->m[i][0]) &&
2604
!osl_int_one(relation->precision, relation->m[i][0])) {
2605
OSL_warning("first column of a relation is not "
2606
"strictly made of 0 or 1");
2607
osl_relation_dump(stderr, relation);
2608
return 0;
2609
}
2610
}
2611
}
2612
2613
// Array accesses must provide the array identifier.
2614
if ((osl_relation_is_access(relation)) &&
2615
(osl_relation_get_array_id(relation) == OSL_UNDEFINED)) {
2616
osl_relation_dump(stderr, relation);
2617
return 0;
2618
}
2619
2620
relation = relation->next;
2621
}
2622
2623
return 1;
2624
}
2625
2626
2627
/**
2628
* osl_relation_set_attributes_one function:
2629
* this functions sets the attributes of a relation part provided as a
2630
* parameter. It updates the relation directly.
2631
* \param[in,out] relation The relation (union part) to set the attributes.
2632
* \param[in] nb_output_dims Number of output dimensions.
2633
* \param[in] nb_input_dims Number of input dimensions.
2634
* \param[in] nb_local_dims Number of local dimensions.
2635
* \param[in] nb_parameters Number of parameters.
2636
*/
2637
void osl_relation_set_attributes_one(osl_relation_p relation,
2638
int nb_output_dims, int nb_input_dims,
2639
int nb_local_dims, int nb_parameters) {
2640
if (relation != NULL) {
2641
relation->nb_output_dims = nb_output_dims;
2642
relation->nb_input_dims = nb_input_dims;
2643
relation->nb_local_dims = nb_local_dims;
2644
relation->nb_parameters = nb_parameters;
2645
}
2646
}
2647
2648
2649
/**
2650
* osl_relation_set_attributes function:
2651
* this functions sets the attributes of a relation (union) provided
2652
* as a parameter. It updates the relation directly.
2653
* \param[in,out] relation The relation (union) to set the attributes.
2654
* \param[in] nb_output_dims Number of output dimensions.
2655
* \param[in] nb_input_dims Number of input dimensions.
2656
* \param[in] nb_local_dims Number of local dimensions.
2657
* \param[in] nb_parameters Number of parameters.
2658
*/
2659
void osl_relation_set_attributes(osl_relation_p relation,
2660
int nb_output_dims, int nb_input_dims,
2661
int nb_local_dims, int nb_parameters) {
2662
while (relation != NULL) {
2663
osl_relation_set_attributes_one(relation,
2664
nb_output_dims, nb_input_dims,
2665
nb_local_dims, nb_parameters);
2666
relation = relation->next;
2667
}
2668
}
2669
2670
2671
/**
2672
* osl_relation_set_type function:
2673
* this function sets the type of each relation union part in the relation
2674
* to the one provided as parameter.
2675
* \param relation The relation to set the type.
2676
* \param type The type.
2677
*/
2678
void osl_relation_set_type(osl_relation_p relation, int type) {
2679
2680
while (relation != NULL) {
2681
relation->type = type;
2682
relation = relation->next;
2683
}
2684
}
2685
2686
2687
/**
2688
* osl_relation_get_array_id function:
2689
* this function returns the array identifier in a relation with access type
2690
* It returns OSL_UNDEFINED if it is not able to find it (in particular
2691
* if there are irregularities in the relation).
2692
* \param[in] relation The relation where to find an array identifier.
2693
* \return The array identifier in the relation or OSL_UNDEFINED.
2694
*/
2695
int osl_relation_get_array_id(osl_relation_p relation) {
2696
int i;
2697
int first = 1;
2698
int array_id = OSL_UNDEFINED;
2699
int reference_array_id = OSL_UNDEFINED;
2700
int nb_array_id;
2701
int row_id = 0;
2702
int precision;
2703
2704
if (relation == NULL)
2705
return OSL_UNDEFINED;
2706
2707
if (!osl_relation_is_access(relation)) {
2708
OSL_warning("asked for an array id of non-array relation");
2709
return OSL_UNDEFINED;
2710
}
2711
2712
while (relation != NULL) {
2713
precision = relation->precision;
2714
2715
// There should be room to store the array identifier.
2716
if ((relation->nb_rows < 1) ||
2717
(relation->nb_columns < 3)) {
2718
OSL_warning("no array identifier in an access function");
2719
return OSL_UNDEFINED;
2720
}
2721
2722
// Array identifiers are m[i][#columns -1] / m[i][1], with i the only row
2723
// where m[i][1] is not 0.
2724
// - check there is exactly one row such that m[i][1] is not 0,
2725
// - check the whole ith row if full of 0 except m[i][1] and the id,
2726
// - check that (m[i][#columns -1] % m[i][1]) == 0,
2727
// - check that (-m[i][#columns -1] / m[i][1]) > 0.
2728
nb_array_id = 0;
2729
for (i = 0; i < relation->nb_rows; i++) {
2730
if (!osl_int_zero(precision, relation->m[i][1])) {
2731
nb_array_id ++;
2732
row_id = i;
2733
}
2734
}
2735
if (nb_array_id == 0) {
2736
OSL_warning("no array identifier in an access function");
2737
return OSL_UNDEFINED;
2738
}
2739
if (nb_array_id > 1) {
2740
OSL_warning("several array identifiers in one access function");
2741
return OSL_UNDEFINED;
2742
}
2743
for (i = 0; i < relation->nb_columns - 1; i++) {
2744
if ((i != 1) && !osl_int_zero(precision, relation->m[row_id][i])) {
2745
OSL_warning("non integer array identifier");
2746
return OSL_UNDEFINED;
2747
}
2748
}
2749
if (!osl_int_divisible(precision,
2750
relation->m[row_id][relation->nb_columns - 1],
2751
relation->m[row_id][1])) {
2752
OSL_warning("rational array identifier");
2753
return OSL_UNDEFINED;
2754
}
2755
array_id = -osl_int_get_si(precision,
2756
relation->m[row_id][relation->nb_columns - 1]);
2757
array_id /= osl_int_get_si(precision, relation->m[row_id][1]);
2758
if (array_id <= 0) {
2759
OSL_warning("negative or 0 identifier in access function");
2760
return OSL_UNDEFINED;
2761
}
2762
2763
// Unions of accesses are allowed, but they should refer at the same array.
2764
if (first) {
2765
reference_array_id = array_id;
2766
first = 0;
2767
}
2768
else {
2769
if (reference_array_id != array_id) {
2770
OSL_warning("inconsistency of array identifiers in an "
2771
"union of access relations");
2772
return OSL_UNDEFINED;
2773
}
2774
}
2775
2776
relation = relation->next;
2777
}
2778
2779
return array_id;
2780
}
2781
2782
2783
/**
2784
* osl_relation_is_access function:
2785
* this function returns 1 if the relation corresponds to an access relation,
2786
* whatever its precise type (read, write etc.), 0 otherwise.
2787
* \param relation The relation to check wheter it is an access relation or not.
2788
* \return 1 if the relation is an access relation, 0 otherwise.
2789
*/
2790
int osl_relation_is_access(osl_relation_p relation) {
2791
2792
if (relation == NULL)
2793
return 0;
2794
2795
if ((relation->type == OSL_TYPE_ACCESS) ||
2796
(relation->type == OSL_TYPE_READ) ||
2797
(relation->type == OSL_TYPE_WRITE) ||
2798
(relation->type == OSL_TYPE_MAY_WRITE))
2799
return 1;
2800
2801
return 0;
2802
}
2803
2804
2805
/**
2806
* osl_relation_get_attributes function:
2807
* this function returns, through its parameters, the maximum values of the
2808
* relation attributes (nb_iterators, nb_parameters etc), depending on its
2809
* type. HOWEVER, it updates the parameter value iff the attribute is greater
2810
* than the input parameter value. Hence it may be used to get the
2811
* attributes as well as to find the maximum attributes for several relations.
2812
* The array identifier 0 is used when there is no array identifier (AND this
2813
* is OK), OSL_UNDEFINED is used to report it is impossible to provide the
2814
* property while it should. This function is not intended for checking, the
2815
* input relation should be correct.
2816
* \param[in] relation The relation to extract attribute values.
2817
* \param[in,out] nb_parameters Number of parameter attribute.
2818
* \param[in,out] nb_iterators Number of iterators attribute.
2819
* \param[in,out] nb_scattdims Number of scattering dimensions attribute.
2820
* \param[in,out] nb_localdims Number of local dimensions attribute.
2821
* \param[in,out] array_id Maximum array identifier attribute.
2822
*/
2823
void osl_relation_get_attributes(osl_relation_p relation,
2824
int * nb_parameters,
2825
int * nb_iterators,
2826
int * nb_scattdims,
2827
int * nb_localdims,
2828
int * array_id) {
2829
int type;
2830
int local_nb_parameters = OSL_UNDEFINED;
2831
int local_nb_iterators = OSL_UNDEFINED;
2832
int local_nb_scattdims = OSL_UNDEFINED;
2833
int local_nb_localdims = OSL_UNDEFINED;
2834
int local_array_id = OSL_UNDEFINED;
2835
2836
while (relation != NULL) {
2837
if (osl_relation_is_access(relation))
2838
type = OSL_TYPE_ACCESS;
2839
else
2840
type = relation->type;
2841
2842
// There is some redundancy but I believe the code is cleaner this way.
2843
switch (type) {
2844
case OSL_TYPE_CONTEXT:
2845
local_nb_parameters = relation->nb_parameters;
2846
local_nb_iterators = 0;
2847
local_nb_scattdims = 0;
2848
local_nb_localdims = relation->nb_local_dims;
2849
local_array_id = 0;
2850
break;
2851
2852
case OSL_TYPE_DOMAIN:
2853
local_nb_parameters = relation->nb_parameters;
2854
local_nb_iterators = relation->nb_output_dims;
2855
local_nb_scattdims = 0;
2856
local_nb_localdims = relation->nb_local_dims;
2857
local_array_id = 0;
2858
break;
2859
2860
case OSL_TYPE_SCATTERING:
2861
local_nb_parameters = relation->nb_parameters;
2862
local_nb_iterators = relation->nb_input_dims;
2863
local_nb_scattdims = relation->nb_output_dims;
2864
local_nb_localdims = relation->nb_local_dims;
2865
local_array_id = 0;
2866
break;
2867
2868
case OSL_TYPE_ACCESS:
2869
local_nb_parameters = relation->nb_parameters;
2870
local_nb_iterators = relation->nb_input_dims;
2871
local_nb_scattdims = 0;
2872
local_nb_localdims = relation->nb_local_dims;
2873
local_array_id = osl_relation_get_array_id(relation);
2874
break;
2875
2876
default:
2877
local_nb_parameters = relation->nb_parameters;
2878
local_nb_iterators = relation->nb_input_dims;
2879
local_nb_scattdims = relation->nb_output_dims;
2880
local_nb_localdims = relation->nb_local_dims;
2881
local_array_id = 0;
2882
}
2883
2884
// Update.
2885
*nb_parameters = OSL_max(*nb_parameters, local_nb_parameters);
2886
*nb_iterators = OSL_max(*nb_iterators, local_nb_iterators);
2887
*nb_scattdims = OSL_max(*nb_scattdims, local_nb_scattdims);
2888
*nb_localdims = OSL_max(*nb_localdims, local_nb_localdims);
2889
*array_id = OSL_max(*array_id, local_array_id);
2890
relation = relation->next;
2891
}
2892
}
2893
2894
2895
/**
2896
* osl_relation_extend_output function:
2897
* this function extends the number of output dimensions of a given relation. It
2898
* returns a copy of the input relation with a number of output dimensions
2899
* extended to "dim" for all its union components. The new output dimensions
2900
* are simply set equal to 0. The extended number of dimensions must be higher
2901
* than or equal to the original one (an error will be raised otherwise).
2902
* \param[in] relation The input relation to extend.
2903
* \param[in] dim The number of output dimension to reach.
2904
* \return A new relation: "relation" extended to "dim" output dims.
2905
*/
2906
osl_relation_p osl_relation_extend_output(osl_relation_p relation, int dim) {
2907
int i, j;
2908
int first = 1;
2909
int offset;
2910
int precision = relation->precision;
2911
osl_relation_p extended = NULL, node, previous = NULL;
2912
2913
while (relation != NULL) {
2914
if (relation->nb_output_dims > dim)
2915
OSL_error("Number of output dims is greater than required extension");
2916
offset = dim - relation->nb_output_dims;
2917
2918
node = osl_relation_pmalloc(precision,
2919
relation->nb_rows + offset,
2920
relation->nb_columns + offset);
2921
2922
node->type = relation->type;
2923
node->nb_output_dims = OSL_max(relation->nb_output_dims, dim);
2924
node->nb_input_dims = relation->nb_input_dims;
2925
node->nb_local_dims = relation->nb_local_dims;
2926
node->nb_parameters = relation->nb_parameters;
2927
2928
// Copy of the original relation with some 0 columns for the new dimensions
2929
// Note that we use the fact that the matrix is initialized with zeros.
2930
for (i = 0; i < relation->nb_rows; i++) {
2931
for (j = 0; j <= relation->nb_output_dims; j++)
2932
osl_int_assign(precision, &node->m[i][j], relation->m[i][j]);
2933
2934
for (j = relation->nb_output_dims + offset + 1;
2935
j < relation->nb_columns + offset; j++)
2936
osl_int_assign(precision, &node->m[i][j], relation->m[i][j - offset]);
2937
}
2938
2939
// New rows dedicated to the new dimensions
2940
for (i = relation->nb_rows; i < relation->nb_rows + offset; i++) {
2941
for (j = 0; j < relation->nb_columns + offset; j++) {
2942
if ((i - relation->nb_rows) == (j - relation->nb_output_dims - 1))
2943
osl_int_set_si(precision, &node->m[i][j], -1);
2944
}
2945
}
2946
2947
if (first) {
2948
first = 0;
2949
extended = node;
2950
previous = node;
2951
}
2952
else {
2953
previous->next = node;
2954
previous = previous->next;
2955
}
2956
2957
relation = relation->next;
2958
}
2959
2960
return extended;
2961
}
2962
2963
2964
/**
2965
* osl_relation_interface function:
2966
* this function creates an interface structure corresponding to the relation
2967
* and returns it.
2968
* \return An interface structure for the relation structure.
2969
*/
2970
osl_interface_p osl_relation_interface() {
2971
osl_interface_p interface = osl_interface_malloc();
2972
2973
interface->URI = strdup(OSL_URI_RELATION);
2974
interface->idump = (osl_idump_f)osl_relation_idump;
2975
interface->sprint = (osl_sprint_f)osl_relation_sprint;
2976
interface->sread = (osl_sread_f)osl_relation_sread;
2977
interface->malloc = (osl_malloc_f)osl_relation_malloc;
2978
interface->free = (osl_free_f)osl_relation_free;
2979
interface->clone = (osl_clone_f)osl_relation_clone;
2980
interface->equal = (osl_equal_f)osl_relation_equal;
2981
2982
return interface;
2983
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1