2 /*+-----------------------------------------------------------------**
4 **-----------------------------------------------------------------**
6 **-----------------------------------------------------------------**
7 ** First version: 08/10/2010 **
8 **-----------------------------------------------------------------**
11 *****************************************************************************
12 * OpenScop: Structures and formats for polyhedral tools to talk together *
13 *****************************************************************************
14 * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, *
15 * / / / // // // // / / / // // / / // / /|,_, *
16 * / / / // // // // / / / // // / / // / / / /\ *
17 * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ *
18 * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ *
19 * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ *
20 * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ *
21 * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ *
22 * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ *
23 * | I | | | | e | | | | | | | | | | | | | \ \ \ *
24 * | T | | | | | | | | | | | | | | | | | \ \ \ *
25 * | E | | | | | | | | | | | | | | | | | \ \ \ *
26 * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ *
27 * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / *
28 * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' *
30 * Copyright (C) 2008 University Paris-Sud 11 and INRIA *
32 * (3-clause BSD license) *
33 * Redistribution and use in source and binary forms, with or without *
34 * modification, are permitted provided that the following conditions *
37 * 1. Redistributions of source code must retain the above copyright notice, *
38 * this list of conditions and the following disclaimer. *
39 * 2. Redistributions in binary form must reproduce the above copyright *
40 * notice, this list of conditions and the following disclaimer in the *
41 * documentation and/or other materials provided with the distribution. *
42 * 3. The name of the author may not be used to endorse or promote products *
43 * derived from this software without specific prior written permission. *
45 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR *
46 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES *
47 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. *
48 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, *
49 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT *
50 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
51 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY *
52 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT *
53 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF *
54 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
56 * OpenScop Library, a library to manipulate OpenScop formats and data *
57 * structures. Written by: *
58 * Cedric Bastoul <Cedric.Bastoul@u-psud.fr> and *
59 * Louis-Noel Pouchet <Louis-Noel.pouchet@inria.fr> *
61 *****************************************************************************/
68 # include <osl/relation_list.h>
71 /*+***************************************************************************
72 * Structure display function *
73 *****************************************************************************/
77 * osl_relation_list_idump function:
78 * Displays a osl_relation_list_t structure (a list of relations) into a
79 * file (file, possibly stdout). See osl_relation_print_structure for
81 * \param file File where informations are printed.
82 * \param l The list of relations whose information has to be printed.
83 * \param level Number of spaces before printing, for each line.
85 void osl_relation_list_idump(FILE * file
, osl_relation_list_p l
, int level
) {
88 // Go to the right level.
89 for (j
= 0; j
< level
; j
++)
93 fprintf(file
, "+-- osl_relation_list_t\n");
95 fprintf(file
, "+-- NULL relation list\n");
99 // Go to the right level.
100 for (j
= 0; j
< level
; j
++)
101 fprintf(file
, "|\t");
102 fprintf(file
, "| osl_relation_list_t\n");
108 for (j
= 0; j
<= level
+1; j
++)
109 fprintf(file
, "|\t");
113 osl_relation_idump(file
, l
->elt
, level
+1);
119 for (j
= 0; j
<= level
; j
++)
120 fprintf(file
, "|\t");
121 fprintf(file
, "V\n");
126 for (j
= 0; j
<= level
; j
++)
127 fprintf(file
, "|\t");
133 * osl_relation_dump function:
134 * This function prints the content of a osl_relation_list_t into
135 * a file (file, possibly stdout).
136 * \param file File where informations are printed.
137 * \param list The relation whose information has to be printed.
139 void osl_relation_list_dump(FILE * file
, osl_relation_list_p list
) {
140 osl_relation_list_idump(file
, list
, 0);
145 * osl_relation_list_pprint_elts function:
146 * This function pretty-prints the elements of a osl_relation_list_t structure
147 * into a file (file, possibly stdout) in the OpenScop format. I.e., it prints
148 * only the elements and not the number of elements. It prints an element of the
149 * list only if it is not NULL.
150 * \param file File where informations are printed.
151 * \param list The relation list whose information has to be printed.
152 * \param[in] names Array of constraint columns names.
154 void osl_relation_list_pprint_elts(FILE * file
, osl_relation_list_p list
,
157 osl_relation_list_p head
= list
;
159 // Count the number of elements in the list with non-NULL content.
160 i
= osl_relation_list_count(list
);
162 // Print each element of the relation list.
166 if (head
->elt
!= NULL
) {
167 osl_relation_pprint(file
, head
->elt
, names
);
168 if (head
->next
!= NULL
)
176 fprintf(file
, "# NULL relation list\n");
182 * osl_relation_list_pprint function:
183 * This function pretty-prints the content of a osl_relation_list_t structure
184 * into a file (file, possibly stdout) in the OpenScop format. It prints
185 * an element of the list only if it is not NULL.
186 * \param[in] file File where informations are printed.
187 * \param[in] list The relation list whose information has to be printed.
188 * \param[in] names Array of constraint columns names.
190 void osl_relation_list_pprint(FILE * file
, osl_relation_list_p list
,
194 // Count the number of elements in the list with non-NULL content.
195 i
= osl_relation_list_count(list
);
199 fprintf(file
,"# List of %d elements\n%d\n", i
, i
);
201 fprintf(file
,"# List of %d element \n%d\n", i
, i
);
203 // Print each element of the relation list.
204 osl_relation_list_pprint_elts(file
, list
, names
);
209 * osl_relation_list_print function:
210 * This function prints the content of a osl_relation_list_t structure
211 * into a file (file, possibly stdout) in the OpenScop format. It prints
212 * an element of the list only if it is not NULL.
213 * \param file File where informations are printed.
214 * \param list The relation list whose information has to be printed.
216 void osl_relation_list_print(FILE * file
, osl_relation_list_p list
) {
218 osl_relation_list_pprint(file
, list
, NULL
);
221 /*****************************************************************************
223 *****************************************************************************/
227 * osl_relation_list_pread function ("precision read"):
228 * this function reads a list of relations into a file (foo,
229 * posibly stdin) and returns a pointer this relation list.
230 * \param[in] file The input stream.
231 * \param[in] precision The precision of the relation elements.
232 * \return A pointer to the relation list structure that has been read.
234 osl_relation_list_p
osl_relation_list_pread(FILE * file
, int precision
) {
236 osl_relation_list_p list
;
237 osl_relation_list_p res
;
240 // Read the number of relations to read.
241 nb_mat
= osl_util_read_int(file
, NULL
);
244 OSL_error("negative number of relations");
246 // Allocate the header of the list and start reading each element.
247 res
= list
= osl_relation_list_malloc();
248 for (i
= 0; i
< nb_mat
; ++i
) {
249 list
->elt
= osl_relation_pread(file
, precision
);
251 list
->next
= osl_relation_list_malloc();
260 * osl_relation_list_read function:
261 * this function is equivalent to osl_relation_list_pread() except that
262 * the precision corresponds to the precision environment variable or
263 * to the highest available precision if it is not defined.
264 * \see{osl_relation_list_pread}
266 osl_relation_list_p
osl_relation_list_read(FILE * foo
) {
267 int precision
= osl_util_get_precision();
268 return osl_relation_list_pread(foo
, precision
);
272 /*+***************************************************************************
273 * Memory allocation/deallocation function *
274 *****************************************************************************/
278 * osl_relation_list_malloc function:
279 * This function allocates the memory space for a osl_relation_list_t
280 * structure and sets its fields with default values. Then it returns
281 * a pointer to the allocated space.
282 * \return A pointer to an empty relation list with fields set to default
285 osl_relation_list_p
osl_relation_list_malloc() {
286 osl_relation_list_p res
;
288 OSL_malloc(res
, osl_relation_list_p
, sizeof(osl_relation_list_t
));
298 * osl_relation_list_free function:
299 * This function frees the allocated memory for a osl_relation_list_t
300 * structure, and all the relations stored in the list.
301 * \param list The pointer to the relation list we want to free.
303 void osl_relation_list_free(osl_relation_list_p list
) {
304 osl_relation_list_p tmp
;
309 while (list
!= NULL
) {
310 if (list
->elt
!= NULL
)
311 osl_relation_free(list
->elt
);
319 /*+***************************************************************************
320 * Processing functions *
321 *****************************************************************************/
325 * osl_relation_list_node function:
326 * This function builds an osl_relation_list_t node and sets its
327 * relation element as a copy of the one provided as parameter.
328 * \param r The pointer to the relation to copy/paste in a list node.
329 * \return A pointer to a relation list node containing a copy of "relation".
331 osl_relation_list_p
osl_relation_list_node(osl_relation_p r
) {
332 osl_relation_list_p
new = osl_relation_list_malloc();
333 new->elt
= osl_relation_clone(r
);
339 * osl_relation_list_clone function:
340 * This functions builds and returns a quasi-"hard copy" (not a pointer copy)
341 * of a osl_relation_list_t data structure provided as parameter.
342 * \param list The pointer to the relation list we want to copy.
343 * \return A pointer to the full copy of the relation list in parameter.
345 osl_relation_list_p
osl_relation_list_clone(osl_relation_list_p list
) {
347 osl_relation_list_p clone
= NULL
, node
, previous
= NULL
;
350 while (list
!= NULL
) {
351 node
= osl_relation_list_malloc();
352 node
->elt
= osl_relation_clone(list
->elt
);
360 previous
->next
= node
;
361 previous
= previous
->next
;
372 * osl_relation_list_concat function:
373 * this function builds a new relation list as the concatenation of the
374 * two lists sent as parameters.
375 * \param l1 The first relation list.
376 * \param l2 The second relation list.
377 * \return A pointer to the relation list resulting from the concatenation of
380 osl_relation_list_p
osl_relation_list_concat(osl_relation_list_p l1
,
381 osl_relation_list_p l2
) {
382 osl_relation_list_p
new, end
;
385 return osl_relation_list_clone(l2
);
388 return osl_relation_list_clone(l1
);
390 new = osl_relation_list_clone(l1
);
392 while (end
->next
!= NULL
)
394 end
->next
= osl_relation_list_clone(l2
);
401 * osl_relation_list_concat_inplace function:
402 * this function concatenates a relation list to another. No new list is
403 * created: this functions links the two input lists. If the first relation
404 * list is NULL, it is set to the second relation list.
405 * two lists sent as parameters.
406 * \param[in,out] l1 Pointer to the first relation list.
407 * \param[in] l2 The second relation list.
409 void osl_relation_list_concat_inplace(osl_relation_list_p
*l1
,
410 osl_relation_list_p l2
) {
411 osl_relation_list_p temp
;
419 while (temp
->next
!= NULL
)
426 * osl_relation_list_equal function:
427 * This function returns true if the two relation lists are the same, false
429 * \param l1 The first relation list.
430 * \param l2 The second relation list.
431 * \return 1 if l1 and l2 are the same (content-wise), 0 otherwise.
433 int osl_relation_list_equal(osl_relation_list_p l1
, osl_relation_list_p l2
) {
434 while ((l1
!= NULL
) && (l2
!= NULL
)) {
438 if (!osl_relation_equal(l1
->elt
, l2
->elt
))
445 if (((l1
== NULL
) && (l2
!= NULL
)) || ((l1
!= NULL
) && (l2
== NULL
)))
453 * osl_relation_integrity_check function:
454 * This function checks that a list of relation is "well formed" according to
455 * some expected properties (setting an expected value to OSL_UNDEFINED
456 * means that we do not expect a specific value) and what the relations are
457 * supposed to represent (all relations of a list are supposed to have the
458 * same semantics). It returns 0 if the check failed or 1 if no problem has
460 * \param list The relation list we want to check.
461 * \param type Semantics about this relation (domain, access...).
462 * \param expected_nb_output_dims Expected number of output dimensions.
463 * \param expected_nb_input_dims Expected number of input dimensions.
464 * \param expected_nb_parameters Expected number of parameters.
465 * \return 0 if the integrity check fails, 1 otherwise.
467 int osl_relation_list_integrity_check(osl_relation_list_p list
,
469 int expected_nb_output_dims
,
470 int expected_nb_input_dims
,
471 int expected_nb_parameters
) {
472 while (list
!= NULL
) {
473 // Check the access function.
474 if (!osl_relation_integrity_check(list
->elt
,
476 expected_nb_output_dims
,
477 expected_nb_input_dims
,
478 expected_nb_parameters
)) {
490 * osl_relation_list_set_type function:
491 * this function sets the type of each relation in the relation list to the
492 * one provided as parameter.
493 * \param list The list of relations to set the type.
494 * \param type The type.
496 void osl_relation_list_set_type(osl_relation_list_p list
, int type
) {
498 while (list
!= NULL
) {
499 if (list
->elt
!= NULL
) {
500 list
->elt
->type
= type
;
508 * osl_relation_list_filter function:
509 * this function returns a copy of the input relation list, restricted to
510 * the relations of a given type. The special type OSL_TYPE_ACCESS
511 * filters any kind of access (read, write, rdwr etc.).
512 * \param list The relation list to copy/filter.
513 * \param type The filtering type.
514 * \return A copy of the input list with only relation of the given type.
516 osl_relation_list_p
osl_relation_list_filter(osl_relation_list_p list
,
519 osl_relation_list_p copy
= osl_relation_list_clone(list
);
520 osl_relation_list_p filtered
= NULL
;
521 osl_relation_list_p previous
= NULL
;
522 osl_relation_list_p trash
;
525 while (copy
!= NULL
) {
526 if ((copy
->elt
!= NULL
) &&
527 (((type
== OSL_TYPE_ACCESS
) &&
528 (osl_relation_is_access(copy
->elt
))) ||
529 ((type
!= OSL_TYPE_ACCESS
) &&
530 (type
== copy
->elt
->type
)))) {
542 previous
->next
= copy
->next
;
545 osl_relation_list_free(trash
);
554 * osl_relation_list_count function:
555 * this function returns the number of elements with non-NULL content
556 * in a relation list.
557 * \param list The relation list to count the number of elements.
558 * \return The number of nodes with non-NULL content in the relation list.
560 int osl_relation_list_count(osl_relation_list_p list
) {
563 while (list
!= NULL
) {
564 if (list
->elt
!= NULL
)
574 * osl_relation_list_get_attributes function:
575 * this function returns, through its parameters, the maximum values of the
576 * relation attributes (nb_iterators, nb_parameters etc) in the relation list,
577 * depending on its type. HOWEVER, it updates the parameter value iff the
578 * attribute is greater than the input parameter value. Hence it may be used
579 * to get the attributes as well as to find the maximum attributes for several
580 * relation lists. The array identifier 0 is used when there is no array
581 * identifier (AND this is OK), OSL_UNDEFINED is used to report it is
582 * impossible to provide the property while it should. This function is not
583 * intended for checking, the input relation list should be correct.
584 * \param[in] list The relation list to extract attribute values.
585 * \param[in,out] nb_parameters Number of parameter attribute.
586 * \param[in,out] nb_iterators Number of iterators attribute.
587 * \param[in,out] nb_scattdims Number of scattering dimensions attribute.
588 * \param[in,out] nb_localdims Number of local dimensions attribute.
589 * \param[in,out] array_id Maximum array identifier attribute.
591 void osl_relation_list_get_attributes(osl_relation_list_p list
,
597 int local_nb_parameters
= OSL_UNDEFINED
;
598 int local_nb_iterators
= OSL_UNDEFINED
;
599 int local_nb_scattdims
= OSL_UNDEFINED
;
600 int local_nb_localdims
= OSL_UNDEFINED
;
601 int local_array_id
= OSL_UNDEFINED
;
603 while (list
!= NULL
) {
604 osl_relation_get_attributes(list
->elt
,
605 &local_nb_parameters
,
611 *nb_parameters
= OSL_max(*nb_parameters
, local_nb_parameters
);
612 *nb_iterators
= OSL_max(*nb_iterators
, local_nb_iterators
);
613 *nb_scattdims
= OSL_max(*nb_scattdims
, local_nb_scattdims
);
614 *nb_localdims
= OSL_max(*nb_localdims
, local_nb_localdims
);
615 *array_id
= OSL_max(*array_id
, local_array_id
);