1
2    /*+-----------------------------------------------------------------**
3     **                       OpenScop Library                          **
4     **-----------------------------------------------------------------**
5     **                        relation_list.c                          **
6     **-----------------------------------------------------------------**
7     **                   First version: 08/10/2010                     **
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/util.h>
71#include <osl/relation.h>
72#include <osl/relation_list.h>
73
74
75/*+***************************************************************************
76 *                          Structure display function                       *
77 *****************************************************************************/
78
79
80/**
81 * osl_relation_list_idump function:
82 * Displays a osl_relation_list_t structure (a list of relations) into a
83 * file (file, possibly stdout). See osl_relation_print_structure for
84 * more details.
85 * \param file   File where informations are printed.
86 * \param l	 The list of relations whose information has to be printed.
87 * \param level  Number of spaces before printing, for each line.
88 */
89void osl_relation_list_idump(FILE * file, osl_relation_list_p l, int level) {
90  int j, first = 1;
91
92  // Go to the right level.
93  for (j = 0; j < level; j++)
94    fprintf(file,"|\t");
95
96  if (l != NULL)
97    fprintf(file, "+-- osl_relation_list_t\n");
98  else
99    fprintf(file, "+-- NULL relation list\n");
100
101  while (l != NULL) {
102    if (!first) {
103      // Go to the right level.
104      for (j = 0; j < level; j++)
105        fprintf(file, "|\t");
106      fprintf(file, "|   osl_relation_list_t\n");
107    }
108    else
109      first = 0;
110
111    // A blank line.
112    for (j = 0; j <= level+1; j++)
113      fprintf(file, "|\t");
114    fprintf(file, "\n");
115
116    // Print a relation.
117    osl_relation_idump(file, l->elt, level+1);
118
119    l = l->next;
120
121    // Next line.
122    if (l != NULL) {
123      for (j = 0; j <= level; j++)
124        fprintf(file, "|\t");
125      fprintf(file, "V\n");
126    }
127  }
128
129  // The last line.
130  for (j = 0; j <= level; j++)
131    fprintf(file, "|\t");
132  fprintf(file, "\n");
133}
134
135
136/**
137 * osl_relation_dump function:
138 * This function prints the content of a osl_relation_list_t into
139 * a file (file, possibly stdout).
140 * \param file File where informations are printed.
141 * \param list The relation whose information has to be printed.
142 */
143void osl_relation_list_dump(FILE * file, osl_relation_list_p list) {
144  osl_relation_list_idump(file, list, 0);
145}
146
147
148/**
149 * osl_relation_list_pprint_elts function:
150 * This function pretty-prints the elements of a osl_relation_list_t structure
151 * into a file (file, possibly stdout) in the OpenScop format. I.e., it prints
152 * only the elements and not the number of elements. It prints an element of the
153 * list only if it is not NULL.
154 * \param file  File where informations are printed.
155 * \param list  The relation list whose information has to be printed.
156 * \param[in] names Array of constraint columns names.
157 */
158void osl_relation_list_pprint_elts(FILE * file, osl_relation_list_p list,
159                                   osl_names_p names) {
160  int i;
161  osl_relation_list_p head = list;
162
163  // Count the number of elements in the list with non-NULL content.
164  i = osl_relation_list_count(list);
165
166  // Print each element of the relation list.
167  if (i > 0) {
168    i = 0;
169    while (head) {
170      if (head->elt != NULL) {
171        osl_relation_pprint(file, head->elt, names);
172        if (head->next != NULL)
173          fprintf(file, "\n");
174        i++;
175      }
176      head = head->next;
177    }
178  }
179  else {
180    fprintf(file, "# NULL relation list\n");
181  }
182}
183
184
185/**
186 * osl_relation_list_pprint function:
187 * This function pretty-prints the content of a osl_relation_list_t structure
188 * into a file (file, possibly stdout) in the OpenScop format. It prints
189 * an element of the list only if it is not NULL.
190 * \param[in] file  File where informations are printed.
191 * \param[in] list  The relation list whose information has to be printed.
192 * \param[in] names Array of constraint columns names.
193 */
194void osl_relation_list_pprint(FILE * file, osl_relation_list_p list,
195                              osl_names_p names) {
196  int i;
197
198  // Count the number of elements in the list with non-NULL content.
199  i = osl_relation_list_count(list);
200
201  // Print it.
202  if (i > 1)
203    fprintf(file,"# List of %d elements\n%d\n", i, i);
204  else
205    fprintf(file,"# List of %d element \n%d\n", i, i);
206
207  // Print each element of the relation list.
208  osl_relation_list_pprint_elts(file, list, names);
209}
210
211
212/**
213 * osl_relation_list_print function:
214 * This function prints the content of a osl_relation_list_t structure
215 * into a file (file, possibly stdout) in the OpenScop format. It prints
216 * an element of the list only if it is not NULL.
217 * \param file  File where informations are printed.
218 * \param list  The relation list whose information has to be printed.
219 */
220void osl_relation_list_print(FILE * file, osl_relation_list_p list) {
221
222  osl_relation_list_pprint(file, list, NULL);
223}
224
225/*****************************************************************************
226 *                               Reading function                            *
227 *****************************************************************************/
228
229
230/**
231 * osl_relation_list_pread function ("precision read"):
232 * this function reads a list of relations into a file (foo,
233 * posibly stdin) and returns a pointer this relation list.
234 * \param[in] file      The input stream.
235 * \param[in] precision The precision of the relation elements.
236 * \return A pointer to the relation list structure that has been read.
237 */
238osl_relation_list_p osl_relation_list_pread(FILE * file, int precision) {
239  int i;
240  osl_relation_list_p list;
241  osl_relation_list_p res;
242  int nb_mat;
243
244  // Read the number of relations to read.
245  nb_mat = osl_util_read_int(file, NULL);
246
247  if (nb_mat < 0)
248    OSL_error("negative number of relations");
249
250  // Allocate the header of the list and start reading each element.
251  res = list = osl_relation_list_malloc();
252  for (i = 0; i < nb_mat; ++i) {
253    list->elt = osl_relation_pread(file, precision);
254    if (i < nb_mat - 1)
255      list->next = osl_relation_list_malloc();
256    list = list->next;
257  }
258
259  return res;
260}
261
262
263/**
264 * osl_relation_list_read function:
265 * this function is equivalent to osl_relation_list_pread() except that
266 * the precision corresponds to the precision environment variable or
267 * to the highest available precision if it is not defined.
268 * \see{osl_relation_list_pread}
269 */
270osl_relation_list_p osl_relation_list_read(FILE * foo) {
271  int precision = osl_util_get_precision();
272  return osl_relation_list_pread(foo, precision);
273}
274
275
276/*+***************************************************************************
277 *                    Memory allocation/deallocation function                *
278 *****************************************************************************/
279
280
281/**
282 * osl_relation_list_malloc function:
283 * This function allocates the memory space for a osl_relation_list_t
284 * structure and sets its fields with default values. Then it returns
285 * a pointer to the allocated space.
286 * \return A pointer to an empty relation list with fields set to default
287 *         values.
288 */
289osl_relation_list_p osl_relation_list_malloc() {
290  osl_relation_list_p res;
291
292  OSL_malloc(res, osl_relation_list_p, sizeof(osl_relation_list_t));
293  res->elt  = NULL;
294  res->next = NULL;
295
296  return res;
297}
298
299
300
301/**
302 * osl_relation_list_free function:
303 * This function frees the allocated memory for a osl_relation_list_t
304 * structure, and all the relations stored in the list.
305 * \param list The pointer to the relation list we want to free.
306 */
307void osl_relation_list_free(osl_relation_list_p list) {
308  osl_relation_list_p tmp;
309
310  if (list == NULL)
311    return;
312
313  while (list != NULL) {
314    if (list->elt != NULL)
315      osl_relation_free(list->elt);
316    tmp = list->next;
317    free(list);
318    list = tmp;
319  }
320}
321
322
323/*+***************************************************************************
324 *                            Processing functions                           *
325 *****************************************************************************/
326
327
328/**
329 * osl_relation_list_node function:
330 * This function builds an osl_relation_list_t node and sets its
331 * relation element as a copy of the one provided as parameter.
332 * If the relation provided as an argument is NULL, NULL is returned.
333 * \param r The pointer to the relation to copy/paste in a list node.
334 * \return A pointer to a relation list node containing a copy of "relation".
335 */
336osl_relation_list_p osl_relation_list_node(osl_relation_p r) {
337  osl_relation_list_p new = NULL;
338
339  if (r != NULL) {
340    new = osl_relation_list_malloc();
341    new->elt = osl_relation_clone(r);
342  }
343  return new;
344}
345
346
347/**
348 * osl_relation_list_clone function:
349 * This functions builds and returns a quasi-"hard copy" (not a pointer copy)
350 * of a osl_relation_list_t data structure provided as parameter.
351 * \param list  The pointer to the relation list we want to copy.
352 * \return A pointer to the full copy of the relation list in parameter.
353 */
354osl_relation_list_p osl_relation_list_clone(osl_relation_list_p list) {
355
356  osl_relation_list_p clone = NULL, node, previous = NULL;
357  int first = 1;
358
359  while (list != NULL) {
360    node      = osl_relation_list_malloc();
361    node->elt = osl_relation_clone(list->elt);
362
363    if (first) {
364      first = 0;
365      clone = node;
366      previous = node;
367    }
368    else {
369      previous->next = node;
370      previous = previous->next;
371    }
372
373    list = list->next;
374  }
375
376  return clone;
377}
378
379
380/**
381 * osl_relation_list_concat function:
382 * this function builds a new relation list as the concatenation of the
383 * two lists sent as parameters.
384 * \param l1  The first relation list.
385 * \param l2  The second relation list.
386 * \return A pointer to the relation list resulting from the concatenation of
387 *         l1 and l2.
388 */
389osl_relation_list_p osl_relation_list_concat(osl_relation_list_p l1,
390                                             osl_relation_list_p l2) {
391  osl_relation_list_p new, end;
392
393  if (l1 == NULL)
394    return osl_relation_list_clone(l2);
395
396  if (l2 == NULL)
397    return osl_relation_list_clone(l1);
398
399  new = osl_relation_list_clone(l1);
400  end = new;
401  while (end->next != NULL)
402    end = end->next;
403  end->next = osl_relation_list_clone(l2);
404
405  return new;
406}
407
408
409/**
410 * osl_relation_list_add function:
411 * this function adds a relation list at the end of the relation list
412 * pointed by l1. No new list is created: this functions links the two
413 * input lists. If the first relation list is NULL, it is set to the
414 * second relation list.
415 * \param[in,out] l1  Pointer to the first relation list.
416 * \param[in]     l2  The second relation list.
417 */
418void osl_relation_list_add(osl_relation_list_p *l1, osl_relation_list_p l2) {
419  while (*l1 != NULL)
420    l1 = &((*l1)->next);
421
422  *l1 = l2;
423}
424
425
426/**
427 * osl_relation_list_push function:
428 * this function sees a list of relations as a stack of relations and
429 * performs the push operation onto this stack.
430 * \param[in,out] head Pointer to the head of the relation stack.
431 * \param[in,out] node Relation node to add to the stack. Its next field is
432 *                     updated to the previous head of the stack.
433 */
434void osl_relation_list_push(osl_relation_list_p *head,
435                            osl_relation_list_p node) {
436  if (node != NULL) {
437    node->next = *head;
438    *head = node;
439  }
440}
441
442
443/**
444 * osl_relation_list_pop function:
445 * this function sees a list of relations as a stack of relations and
446 * performs the pop operation onto this stack.
447 * \param[in,out] head Pointer to the head of the relation stack. It is
448 *                     updated to the previous element in the stack (NULL
449 *                     if there is none).
450 * \return The top element of the stack (detached from the list).
451 */
452osl_relation_list_p osl_relation_list_pop(osl_relation_list_p *head) {
453  osl_relation_list_p top = NULL;
454
455  if (*head != NULL) {
456    top = *head;
457    *head = (*head)->next;
458    top->next = NULL;
459  }
460
461  return top;
462}
463
464
465/**
466 * osl_relation_list_dup function:
467 * this function sees a list of relations as a stack of relations and
468 * performs the dup operation (duplicate the top element) onto
469 * this stack.
470 * \param[in,out] head Pointer to the head of the relation stack. It is
471 *                     updated to the new element after duplication.
472 */
473void osl_relation_list_dup(osl_relation_list_p *head) {
474  osl_relation_list_p top = osl_relation_list_pop(head);
475  osl_relation_list_push(head, osl_relation_list_clone(top));
476  osl_relation_list_push(head, top);
477}
478
479
480/**
481 * osl_relation_list_drop function:
482 * this function sees a list of relations as a stack of relations and
483 * performs the drop operation (pop and destroy popped element) onto
484 * this stack.
485 * \param[in,out] head Pointer to the head of the relation stack. It is
486 *                     updated to the previous element in the stack (NULL
487 *                     if there is none).
488 */
489void osl_relation_list_drop(osl_relation_list_p *head) {
490  osl_relation_list_p top = osl_relation_list_pop(head);
491  osl_relation_list_free(top);
492}
493
494
495/**
496 * osl_relation_list_destroy function:
497 * this function sees a list of relations as a stack of relations and
498 * performs the destroy operation onto this stack, i.e., it completely
499 * free it.
500 * \param[in,out] head Pointer to the head of the relation stack.
501 *                     Updated to NULL.
502 */
503void osl_relation_list_destroy(osl_relation_list_p *head) {
504
505  while (*head != NULL)
506    osl_relation_list_drop(head);
507}
508
509
510/**
511 * osl_relation_list_equal function:
512 * This function returns true if the two relation lists are the same, false
513 * otherwise..
514 * \param l1 The first relation list.
515 * \param l2 The second relation list.
516 * \return 1 if l1 and l2 are the same (content-wise), 0 otherwise.
517 */
518int osl_relation_list_equal(osl_relation_list_p l1, osl_relation_list_p l2) {
519  while ((l1 != NULL) && (l2 != NULL)) {
520    if (l1 == l2)
521      return 1;
522
523    if (!osl_relation_equal(l1->elt, l2->elt))
524      return 0;
525
526    l1 = l1->next;
527    l2 = l2->next;
528  }
529
530  if (((l1 == NULL) && (l2 != NULL)) || ((l1 != NULL) && (l2 == NULL)))
531    return 0;
532
533  return 1;
534}
535
536
537/**
538 * osl_relation_integrity_check function:
539 * This function checks that a list of relation is "well formed" according to
540 * some expected properties (setting an expected value to OSL_UNDEFINED
541 * means that we do not expect a specific value) and what the relations are
542 * supposed to represent (all relations of a list are supposed to have the
543 * same semantics). It returns 0 if the check failed or 1 if no problem has
544 * been detected.
545 * \param list      The relation list we want to check.
546 * \param type      Semantics about this relation (domain, access...).
547 * \param expected_nb_output_dims Expected number of output dimensions.
548 * \param expected_nb_input_dims  Expected number of input dimensions.
549 * \param expected_nb_parameters  Expected number of parameters.
550 * \return 0 if the integrity check fails, 1 otherwise.
551 */
552int osl_relation_list_integrity_check(osl_relation_list_p list,
553                                      int type,
554                                      int expected_nb_output_dims,
555                                      int expected_nb_input_dims,
556                                      int expected_nb_parameters) {
557  while (list != NULL) {
558    // Check the access function.
559    if (!osl_relation_integrity_check(list->elt,
560                                      type,
561                                      expected_nb_output_dims,
562                                      expected_nb_input_dims,
563                                      expected_nb_parameters)) {
564      return 0;
565    }
566
567    list = list->next;
568  }
569
570  return 1;
571}
572
573
574/**
575 * osl_relation_list_set_type function:
576 * this function sets the type of each relation in the relation list to the
577 * one provided as parameter.
578 * \param list The list of relations to set the type.
579 * \param type The type.
580 */
581void osl_relation_list_set_type(osl_relation_list_p list, int type) {
582
583  while (list != NULL) {
584    if (list->elt != NULL) {
585      list->elt->type = type;
586    }
587    list = list->next;
588  }
589}
590
591
592/**
593 * osl_relation_list_filter function:
594 * this function returns a copy of the input relation list, restricted to
595 * the relations of a given type. The special type OSL_TYPE_ACCESS
596 * filters any kind of access (read, write, rdwr etc.).
597 * \param list The relation list to copy/filter.
598 * \param type The filtering type.
599 * \return A copy of the input list with only relation of the given type.
600 */
601osl_relation_list_p osl_relation_list_filter(osl_relation_list_p list,
602                                             int type) {
603
604  osl_relation_list_p copy = osl_relation_list_clone(list);
605  osl_relation_list_p filtered = NULL;
606  osl_relation_list_p previous = NULL;
607  osl_relation_list_p trash;
608  int first = 1;
609
610  while (copy != NULL) {
611    if ((copy->elt != NULL) &&
612        (((type == OSL_TYPE_ACCESS) &&
613          (osl_relation_is_access(copy->elt))) ||
614         ((type != OSL_TYPE_ACCESS) &&
615          (type == copy->elt->type)))) {
616      if (first) {
617        filtered = copy;
618        first = 0;
619      }
620
621      previous = copy;
622      copy = copy->next;
623    }
624    else {
625      trash = copy;
626      if (!first)
627        previous->next = copy->next;
628      copy = copy->next;
629      trash->next = NULL;
630      osl_relation_list_free(trash);
631    }
632  }
633
634  return filtered;
635}
636
637
638/**
639 * osl_relation_list_count function:
640 * this function returns the number of elements with non-NULL content
641 * in a relation list.
642 * \param list The relation list to count the number of elements.
643 * \return The number of nodes with non-NULL content in the relation list.
644 */
645int osl_relation_list_count(osl_relation_list_p list) {
646  int i = 0;
647
648  while (list != NULL) {
649    if (list->elt != NULL)
650      i++;
651    list = list->next;
652  }
653
654  return i;
655}
656
657
658/**
659 * osl_relation_list_get_attributes function:
660 * this function returns, through its parameters, the maximum values of the
661 * relation attributes (nb_iterators, nb_parameters etc) in the relation list,
662 * depending on its type. HOWEVER, it updates the parameter value iff the
663 * attribute is greater than the input parameter value. Hence it may be used
664 * to get the attributes as well as to find the maximum attributes for several
665 * relation lists. The array identifier 0 is used when there is no array
666 * identifier (AND this is OK), OSL_UNDEFINED is used to report it is
667 * impossible to provide the property while it should. This function is not
668 * intended for checking, the input relation list should be correct.
669 * \param[in]     list          The relation list to extract attribute values.
670 * \param[in,out] nb_parameters Number of parameter attribute.
671 * \param[in,out] nb_iterators  Number of iterators attribute.
672 * \param[in,out] nb_scattdims  Number of scattering dimensions attribute.
673 * \param[in,out] nb_localdims  Number of local dimensions attribute.
674 * \param[in,out] array_id      Maximum array identifier attribute.
675 */
676void osl_relation_list_get_attributes(osl_relation_list_p list,
677                                      int * nb_parameters,
678                                      int * nb_iterators,
679                                      int * nb_scattdims,
680                                      int * nb_localdims,
681                                      int * array_id) {
682  int local_nb_parameters = OSL_UNDEFINED;
683  int local_nb_iterators  = OSL_UNDEFINED;
684  int local_nb_scattdims  = OSL_UNDEFINED;
685  int local_nb_localdims  = OSL_UNDEFINED;
686  int local_array_id      = OSL_UNDEFINED;
687
688  while (list != NULL) {
689    osl_relation_get_attributes(list->elt,
690                                &local_nb_parameters,
691                                &local_nb_iterators,
692                                &local_nb_scattdims,
693                                &local_nb_localdims,
694                                &local_array_id);
695    // Update.
696    *nb_parameters = OSL_max(*nb_parameters, local_nb_parameters);
697    *nb_iterators  = OSL_max(*nb_iterators,  local_nb_iterators);
698    *nb_scattdims  = OSL_max(*nb_scattdims,  local_nb_scattdims);
699    *nb_localdims  = OSL_max(*nb_localdims,  local_nb_localdims);
700    *array_id      = OSL_max(*array_id,      local_array_id);
701    list = list->next;
702  }
703}
704
705