Add overflow detection
[openscop.git] / source / extensions / dependence.c
blobd065a3f8f07cd45241e5e1e2e5839e283bfe94da
2 /*+-----------------------------------------------------------------**
3 ** OpenScop Library **
4 **-----------------------------------------------------------------**
5 ** extensions/dependence.h **
6 **-----------------------------------------------------------------**
7 ** First version: 02/07/2012 **
8 **-----------------------------------------------------------------**
11 *****************************************************************************
12 * OpenScop: Structures and formats for polyhedral tools to talk together *
13 *****************************************************************************
14 * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, *
15 * / / / // // // // / / / // // / / // / /|,_, *
16 * / / / // // // // / / / // // / / // / / / /\ *
17 * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ *
18 * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ *
19 * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ *
20 * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ *
21 * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ *
22 * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ *
23 * | I | | | | e | | | | | | | | | | | | | \ \ \ *
24 * | T | | | | | | | | | | | | | | | | | \ \ \ *
25 * | E | | | | | | | | | | | | | | | | | \ \ \ *
26 * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ *
27 * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / *
28 * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' *
29 * *
30 * Copyright (C) 2008 University Paris-Sud 11 and INRIA *
31 * *
32 * (3-clause BSD license) *
33 * Redistribution and use in source and binary forms, with or without *
34 * modification, are permitted provided that the following conditions *
35 * are met: *
36 * *
37 * 1. Redistributions of source code must retain the above copyright notice, *
38 * this list of conditions and the following disclaimer. *
39 * 2. Redistributions in binary form must reproduce the above copyright *
40 * notice, this list of conditions and the following disclaimer in the *
41 * documentation and/or other materials provided with the distribution. *
42 * 3. The name of the author may not be used to endorse or promote products *
43 * derived from this software without specific prior written permission. *
44 * *
45 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR *
46 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES *
47 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. *
48 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, *
49 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT *
50 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
51 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY *
52 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT *
53 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF *
54 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
55 * *
56 * OpenScop Library, a library to manipulate OpenScop formats and data *
57 * structures. Written by: *
58 * Cedric Bastoul <Cedric.Bastoul@u-psud.fr> and *
59 * Louis-Noel Pouchet <Louis-Noel.pouchet@inria.fr> *
60 * *
61 *****************************************************************************/
63 #include <stdlib.h>
64 #include <stdio.h>
65 #include <string.h>
66 #include <osl/macros.h>
67 #include <osl/scop.h>
68 #include <osl/statement.h>
69 #include <osl/relation.h>
70 #include <osl/names.h>
71 #include <osl/util.h>
72 #include <osl/extensions/dependence.h>
74 /**
75 * Most of these functions where extracted from candl and ported to osl
78 /******************************************************************************
79 * Structure display function *
80 ******************************************************************************/
83 /**
84 * osl_dependence_idump function:
85 * Displays a osl_dependence_p structure (dependence) into a file (file,
86 * possibly stdout) in a way that trends to be understandable without falling
87 * in a deep depression or, for the lucky ones, getting a headache... It
88 * includes an indentation level (level) in order to work with others
89 * idump functions.
90 * - 18/09/2003: first version.
92 void osl_dependence_idump(FILE* file,
93 osl_dependence_p dependence,
94 int level) {
95 int j, first = 1;
96 osl_statement_p tmp;
98 if (dependence != NULL) { /* Go to the right level. */
99 for (j=0; j<level; j++)
100 fprintf(file, "|\t");
101 fprintf(file, "+-- osl_dependence_p\n");
102 } else {
103 for (j=0; j<level; j++)
104 fprintf(file, "|\t");
105 fprintf(file, "+-- NULL dependence\n");
108 while (dependence != NULL) {
109 if (!first) { /* Go to the right level. */
110 for (j=0; j<level; j++)
111 fprintf(file, "|\t");
112 fprintf(file, "| osl_dependence_p\n");
113 } else {
114 first = 0;
117 /* A blank line. */
118 for (j=0; j<=level+1; j++)
119 fprintf(file, "|\t");
120 fprintf(file, "\n");
122 /* Go to the right level and print the type. */
123 for (j=0; j<=level; j++)
124 fprintf(file, "|\t");
125 fprintf(file, "Type: ");
126 switch (dependence->type) {
127 case OSL_UNDEFINED : fprintf(file, "UNSET\n"); break;
128 case OSL_DEPENDENCE_RAW : fprintf(file, "RAW (flow)\n"); break;
129 case OSL_DEPENDENCE_WAR : fprintf(file, "WAR (anti)\n"); break;
130 case OSL_DEPENDENCE_WAW : fprintf(file, "WAW (output)\n"); break;
131 case OSL_DEPENDENCE_RAR : fprintf(file, "RAR (input)\n"); break;
132 case OSL_DEPENDENCE_RAW_SCALPRIV :
133 fprintf(file, "RAW_SCALPRIV (scalar priv)\n"); break;
134 default : fprintf(file, "unknown\n"); break;
137 /* A blank line. */
138 for (j=0; j<=level+1; j++)
139 fprintf(file, "|\t");
140 fprintf(file, "\n");
142 /* Go to the right level and print the depth. */
143 for (j=0; j<=level; j++)
144 fprintf(file, "|\t");
145 fprintf(file, "Depth: %d\n", dependence->depth);
147 /* A blank line. */
148 for (j=0; j<=level+1; j++)
149 fprintf(file, "|\t");
150 fprintf(file, "\n");
152 /* Ref source and target */
153 for (j=0; j<=level; j++)
154 fprintf(file, "|\t");
155 fprintf(file, "Ref source: %d, Ref target: %d\n",
156 dependence->ref_source, dependence->ref_target);
158 /* A blank line. */
159 for (j=0; j<=level+1; j++)
160 fprintf(file, "|\t");
161 fprintf(file, "\n");
163 /* Print the source statement. */
164 for (j=0; j<=level; j++)
165 fprintf(file, "|\t");
166 fprintf(file, "Statement label: %d\n", dependence->label_source);
167 tmp = dependence->stmt_source_ptr->next;
168 dependence->stmt_source_ptr->next = NULL;
169 osl_statement_idump(file, dependence->stmt_source_ptr, level+1);
170 dependence->stmt_source_ptr->next = tmp;
172 /* Print the target statement. */
173 for (j=0; j<=level; j++)
174 fprintf(file, "|\t");
175 fprintf(file, "Target label: %d\n", dependence->label_target);
176 tmp = dependence->stmt_target_ptr->next;
177 dependence->stmt_target_ptr->next = NULL;
178 osl_statement_idump(file, dependence->stmt_target_ptr, level+1);
179 dependence->stmt_target_ptr->next = tmp;
181 /* Print the dependence polyhedron. */
182 for (j=0; j<=level; j++)
183 fprintf(file, "|\t");
184 fprintf(file, "%d %d %d %d %d %d %d %d\n",
185 dependence->source_nb_output_dims_domain,
186 dependence->source_nb_output_dims_access,
187 dependence->target_nb_output_dims_domain,
188 dependence->target_nb_output_dims_access,
189 dependence->source_nb_local_dims_domain,
190 dependence->source_nb_local_dims_access,
191 dependence->target_nb_local_dims_domain,
192 dependence->target_nb_local_dims_access);
193 osl_relation_idump(file, dependence->domain, level+1);
195 dependence = dependence->next;
197 /* Next line. */
198 if (dependence != NULL) {
199 for (j=0; j<=level; j++)
200 fprintf(file, "|\t");
201 fprintf(file, "V\n");
205 /* The last line. */
206 for (j=0; j<=level; j++)
207 fprintf(file, "|\t");
208 fprintf(file, "\n");
213 * osl_dependence_dump function:
214 * This function prints the content of a osl_dependence_p structure (dependence)
215 * into a file (file, possibly stdout).
217 void osl_dependence_dump(FILE * file, osl_dependence_p dependence) {
218 osl_dependence_idump(file, dependence, 0);
223 * osl_dependence_print function:
224 * Print the dependence, formatted to fit the .scop representation.
226 void osl_dependence_print(FILE *file, osl_dependence_p dependence) {
227 char *string = osl_dependence_sprint(dependence);
228 fprintf(file, "%s\n", string);
229 free(string);
234 * osl_dependence_sprint function:
235 * Returns a string containing the dependence, formatted to fit the
236 * .scop representation.
238 char* osl_dependence_sprint(osl_dependence_p dependence) {
240 osl_dependence_p tmp = dependence;
241 int nb_deps;
242 int buffer_size = 2048;
243 char* buffer;
244 char buff[2048];
245 char* type;
246 char* pbuffer;
248 OSL_malloc(buffer, char*, buffer_size);
249 buffer[0] = '\0';
251 for (tmp = dependence, nb_deps = 0; tmp; tmp = tmp->next, ++nb_deps)
253 snprintf(buff, OSL_MAX_STRING, "# Number of dependences\n%d\n", nb_deps);
254 strcat(buffer, buff);
256 if (nb_deps) {
257 for (tmp = dependence, nb_deps = 1; tmp; tmp = tmp->next, ++nb_deps) {
259 switch (tmp->type) {
260 case OSL_UNDEFINED:
261 type = "UNSET";
262 break;
263 case OSL_DEPENDENCE_RAW:
264 type = "RAW #(flow)";
265 break;
266 case OSL_DEPENDENCE_WAR:
267 type = "WAR #(anti)";
268 break;
269 case OSL_DEPENDENCE_WAW:
270 type = "WAW #(output)";
271 break;
272 case OSL_DEPENDENCE_RAR:
273 type = "RAR #(input)";
274 break;
275 case OSL_DEPENDENCE_RAW_SCALPRIV:
276 type = "RAW_SCALPRIV #(scalar priv)";
277 break;
278 default:
279 exit(1);
280 break;
283 /* Output dependence information. */
284 snprintf(buff, OSL_MAX_STRING, "# Description of dependence %d\n"
285 "# type\n%s\n"
286 "# From source statement id\n%d\n"
287 "# To target statement id\n%d\n"
288 "# Depth \n%d\n"
289 "# From source access ref\n%d\n"
290 "# To target access ref\n%d\n"
291 "# Dependence domain\n",
292 nb_deps, type,
293 tmp->label_source,
294 tmp->label_target,
295 tmp->depth,
296 tmp->ref_source,
297 tmp->ref_target);
299 osl_util_safe_strcat(&buffer, buff, &buffer_size);
301 /* Output dependence domain. */
302 pbuffer = osl_relation_sprint(tmp->domain);
303 osl_util_safe_strcat(&buffer, pbuffer, &buffer_size);
304 free(pbuffer);
308 return buffer;
313 * osl_dependence_read_one_dep function:
314 * Read one dependence from a string.
316 static
317 osl_dependence_p osl_dependence_read_one_dep(char **input, int precision) {
318 osl_dependence_p dep = osl_dependence_malloc();
319 char *buffer;
321 /* Dependence type */
322 buffer = osl_util_read_string(NULL, input);
323 if (! strcmp(buffer, "RAW"))
324 dep->type = OSL_DEPENDENCE_RAW;
325 else if (! strcmp(buffer, "RAR"))
326 dep->type = OSL_DEPENDENCE_RAR;
327 else if (! strcmp(buffer, "WAR"))
328 dep->type = OSL_DEPENDENCE_WAR;
329 else if (! strcmp(buffer, "WAW"))
330 dep->type = OSL_DEPENDENCE_WAW;
331 else if (! strcmp(buffer, "RAW_SCALPRIV"))
332 dep->type = OSL_DEPENDENCE_RAW_SCALPRIV;
333 free(buffer);
335 /* # From source statement xxx */
336 dep->label_source = osl_util_read_int(NULL, input);
338 /* # To target statement xxx */
339 dep->label_target = osl_util_read_int(NULL, input);
341 /* # Depth */
342 dep->depth = osl_util_read_int(NULL, input);
344 /* # From source access ref */
345 dep->ref_source = osl_util_read_int(NULL, input);
347 /* # To target access ref */
348 dep->ref_target = osl_util_read_int(NULL, input);
350 /* Read the osl_relation */
351 dep->domain = osl_relation_psread(input, precision);
353 return dep;
358 * osl_dependence_sread function:
359 * Retrieve a osl_dependence_p list from the option tag in the scop.
361 osl_dependence_p osl_dependence_sread(char **input) {
362 int precision = osl_util_get_precision();
363 return osl_dependence_psread(input, precision);
368 * osl_dependence_psread function
369 * Retrieve a osl_dependence_p list from the option tag in the scop.
371 osl_dependence_p osl_dependence_psread(char **input, int precision) {
372 osl_dependence_p first = NULL;
373 osl_dependence_p currdep = NULL;
375 if (*input == NULL) {
376 OSL_debug("no dependence optional tag");
377 return NULL;
380 int i;
381 /* Get the number of dependences. */
382 int nbdeps = osl_util_read_int(NULL, input);
384 /* For each of them, read 1 and shift of the read size. */
385 for (i = 0; i < nbdeps; i++) {
386 osl_dependence_p adep = osl_dependence_read_one_dep(input, precision);
387 if (first == NULL) {
388 currdep = first = adep;
389 } else {
390 currdep->next = adep;
391 currdep = currdep->next;
395 return first;
399 /******************************************************************************
400 * Memory deallocation function *
401 ******************************************************************************/
405 * osl_dependence_malloc function:
406 * This function allocates the memory space for a osl_dependence_p structure and
407 * sets its fields with default values. Then it returns a pointer to the
408 * allocated space.
409 * - 07/12/2005: first version.
411 osl_dependence_p osl_dependence_malloc() {
412 osl_dependence_p dependence;
414 /* Memory allocation for the osl_dependence_p structure. */
415 OSL_malloc(dependence, osl_dependence_p, sizeof(osl_dependence_t));
417 /* We set the various fields with default values. */
418 dependence->depth = OSL_UNDEFINED;
419 dependence->type = OSL_UNDEFINED;
420 dependence->label_source = OSL_UNDEFINED;
421 dependence->label_target = OSL_UNDEFINED;
422 dependence->ref_source = OSL_UNDEFINED;
423 dependence->ref_target = OSL_UNDEFINED;
424 dependence->domain = NULL;
425 dependence->next = NULL;
426 dependence->usr = NULL;
427 dependence->source_nb_output_dims_domain = OSL_UNDEFINED;
428 dependence->source_nb_output_dims_access = OSL_UNDEFINED;
429 dependence->target_nb_output_dims_domain = OSL_UNDEFINED;
430 dependence->target_nb_output_dims_access = OSL_UNDEFINED;
431 dependence->source_nb_local_dims_domain = OSL_UNDEFINED;
432 dependence->source_nb_local_dims_access = OSL_UNDEFINED;
433 dependence->target_nb_local_dims_domain = OSL_UNDEFINED;
434 dependence->target_nb_local_dims_access = OSL_UNDEFINED;
435 dependence->ref_source_access_ptr = NULL;
436 dependence->ref_target_access_ptr = NULL;
437 dependence->stmt_source_ptr = NULL;
438 dependence->stmt_target_ptr = NULL;
440 return dependence;
445 * osl_dependence_free function:
446 * This function frees the allocated memory for a osl_dependence_p structure.
447 * - 18/09/2003: first version.
449 void osl_dependence_free(osl_dependence_p dependence) {
450 osl_dependence_p next;
451 while (dependence != NULL) {
452 next = dependence->next;
453 osl_relation_free(dependence->domain);
454 free(dependence);
455 dependence = next;
460 /******************************************************************************
461 * Processing functions *
462 ******************************************************************************/
466 * osl_dependence_nclone function:
467 * This function builds and returns a "hard copy" (not a pointer copy) of the
468 * n first elements of an osl_dependence_t list.
469 * \param statement The pointer to the dependence structure we want to clone.
470 * \param n The number of nodes we want to copy (-1 for infinity).
471 * \return The clone of the n first nodes of the dependence list.
473 osl_dependence_p osl_dependence_nclone(osl_dependence_p dep, int n) {
474 int first = 1, i = 0;
475 osl_dependence_p clone = NULL, node, previous = NULL;
477 while ((dep != NULL) && ((n == -1) || (i < n))) {
478 node = osl_dependence_malloc();
479 node->stmt_source_ptr = dep->stmt_source_ptr;
480 node->stmt_target_ptr = dep->stmt_target_ptr;
481 node->depth = dep->depth;
482 node->type = dep->type;
483 node->label_source = dep->label_source;
484 node->label_target = dep->label_target;
485 node->ref_source = dep->ref_source;
486 node->ref_target = dep->ref_target;
487 node->domain = osl_relation_clone(dep->domain);
488 node->source_nb_output_dims_domain = dep->source_nb_output_dims_domain;
489 node->source_nb_output_dims_access = dep->source_nb_output_dims_access;
490 node->target_nb_output_dims_domain = dep->target_nb_output_dims_domain;
491 node->target_nb_output_dims_access = dep->target_nb_output_dims_access;
492 node->source_nb_local_dims_domain = dep->source_nb_local_dims_domain;
493 node->source_nb_local_dims_access = dep->source_nb_local_dims_access;
494 node->target_nb_local_dims_domain = dep->target_nb_local_dims_domain;
495 node->target_nb_local_dims_access = dep->target_nb_local_dims_access;
496 node->next = NULL;
497 node->usr = NULL;
499 if (first) {
500 first = 0;
501 clone = node;
502 previous = node;
504 else {
505 previous->next = node;
506 previous = previous->next;
509 i++;
510 dep = dep->next;
513 return clone;
518 * osl_dependence_clone function:
519 * This functions builds and returns a "hard copy" (not a pointer copy) of an
520 * osl_dependence_t data structure provided as parameter.
521 * \param[in] statement The pointer to the dependence we want to clone.
522 * \return A pointer to the clone of the dependence provided as parameter.
524 osl_dependence_p osl_dependence_clone(osl_dependence_p dep) {
525 return osl_dependence_nclone(dep, -1);
530 * osl_dependence_equal function:
531 * this function returns true if the two dependences provided as parameters
532 * are the same, false otherwise (the usr field is not tested).
533 * NOTE: the different pointer to statements or relations are nto compared
534 * \param[in] d1 The first dependence.
535 * \param[in] d2 The second dependence.
536 * \return 1 if d1 and d2 are the same (content-wise), 0 otherwise.
538 int osl_dependence_equal(osl_dependence_p d1, osl_dependence_p d2) {
540 if (d1 == d2)
541 return 1;
543 if ((d1->next != NULL && d2->next == NULL) ||
544 (d1->next == NULL && d2->next != NULL))
545 return 0;
547 if (d1->next != NULL && d2->next != NULL)
548 if (!osl_dependence_equal(d1->next, d2->next))
549 return 0;
551 if (!osl_relation_equal(d1->domain, d2->domain))
552 return 0;
554 if (d1->label_source != d2->label_source ||
555 d1->label_target != d2->label_target ||
556 d1->ref_source != d2->ref_source ||
557 d1->ref_target != d2->ref_target ||
558 d1->depth != d2->depth ||
559 d1->type != d2->type ||
561 d1->source_nb_output_dims_domain !=
562 d2->source_nb_output_dims_domain ||
564 d1->source_nb_output_dims_access !=
565 d2->source_nb_output_dims_access ||
567 d1->target_nb_output_dims_domain !=
568 d2->target_nb_output_dims_domain ||
570 d1->target_nb_output_dims_access !=
571 d2->target_nb_output_dims_access ||
573 d1->source_nb_local_dims_domain !=
574 d2->source_nb_local_dims_domain ||
576 d1->source_nb_local_dims_access !=
577 d2->source_nb_local_dims_access ||
579 d1->target_nb_local_dims_domain !=
580 d2->target_nb_local_dims_domain ||
582 d1->target_nb_local_dims_access !=
583 d2->target_nb_local_dims_access)
584 return 0;
586 return 1;
591 * osl_dependence_add function:
592 * This function adds a osl_dependence_p structure (dependence) at a given place
593 * (now) of a NULL terminated list of osl_dependence_p structures. The beginning
594 * of this list is (start). This function updates (now) to the end of the loop
595 * list (loop), and updates (start) if the added element is the first one -that
596 * is when (start) is NULL-.
597 * - 18/09/2003: first version.
599 void osl_dependence_add(osl_dependence_p* start,
600 osl_dependence_p* now,
601 osl_dependence_p dependence) {
602 if (dependence != NULL) {
603 if (*start == NULL) {
604 *start = dependence;
605 *now = *start;
606 } else {
607 (*now)->next = dependence;
608 *now = (*now)->next;
611 while ((*now)->next != NULL)
612 *now = (*now)->next;
618 * osl_nb_dependences function:
619 * This function returns the number of dependences in the dependence
620 * list
621 * \param dependence The first dependence of the dependence list.
624 int osl_nb_dependences(osl_dependence_p deps) {
625 osl_dependence_p dep = deps;
626 int num = 0;
627 while (dep != NULL) {
628 num++;
629 dep = dep->next;
631 return num;
636 * osl_dependence_interface function:
637 * this function creates an interface structure corresponding to the dependence
638 * extension and returns it).
639 * \return An interface structure for the dependence extension.
641 osl_interface_p osl_dependence_interface() {
642 osl_interface_p interface = osl_interface_malloc();
644 OSL_strdup(interface->URI, OSL_URI_DEPENDENCE);
645 interface->idump = (osl_idump_f)osl_dependence_idump;
646 interface->sprint = (osl_sprint_f)osl_dependence_sprint;
647 interface->sread = (osl_sread_f)osl_dependence_sread;
648 interface->malloc = (osl_malloc_f)osl_dependence_malloc;
649 interface->free = (osl_free_f)osl_dependence_free;
650 interface->clone = (osl_clone_f)osl_dependence_clone;
651 interface->equal = (osl_equal_f)osl_dependence_equal;
653 return interface;