2
/*+-----------------------------------------------------------------**
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
* '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' *
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
*****************************************************************************/
66
#include <osl/macros.h>
68
#include <osl/statement.h>
69
#include <osl/relation.h>
70
#include <osl/names.h>
72
#include <osl/extensions/dependence.h>
75
* Most of these functions where extracted from candl and ported to osl
78
/******************************************************************************
79
* Structure display function *
80
******************************************************************************/
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
90
* - 18/09/2003: first version.
92
void osl_dependence_idump(FILE* file,
93
osl_dependence_p dependence,
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");
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");
118
for (j=0; j<=level+1; j++)
119
fprintf(file, "|\t");
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;
138
for (j=0; j<=level+1; j++)
139
fprintf(file, "|\t");
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);
148
for (j=0; j<=level+1; j++)
149
fprintf(file, "|\t");
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);
159
for (j=0; j<=level+1; j++)
160
fprintf(file, "|\t");
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;
198
if (dependence != NULL) {
199
for (j=0; j<=level; j++)
200
fprintf(file, "|\t");
201
fprintf(file, "V\n");
206
for (j=0; j<=level; j++)
207
fprintf(file, "|\t");
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);
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;
242
int buffer_size = 2048;
248
OSL_malloc(buffer, char*, buffer_size);
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);
257
for (tmp = dependence, nb_deps = 1; tmp; tmp = tmp->next, ++nb_deps) {
263
case OSL_DEPENDENCE_RAW:
264
type = "RAW #(flow)";
266
case OSL_DEPENDENCE_WAR:
267
type = "WAR #(anti)";
269
case OSL_DEPENDENCE_WAW:
270
type = "WAW #(output)";
272
case OSL_DEPENDENCE_RAR:
273
type = "RAR #(input)";
275
case OSL_DEPENDENCE_RAW_SCALPRIV:
276
type = "RAW_SCALPRIV #(scalar priv)";
283
/* Output dependence information. */
284
snprintf(buff, OSL_MAX_STRING, "# Description of dependence %d\n"
286
"# From source statement id\n%d\n"
287
"# To target statement id\n%d\n"
289
"# From source access ref\n%d\n"
290
"# To target access ref\n%d\n"
291
"# Dependence domain\n",
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);
313
* osl_dependence_read_one_dep function:
314
* Read one dependence from a string.
317
osl_dependence_p osl_dependence_read_one_dep(char **input, int precision) {
318
osl_dependence_p dep = osl_dependence_malloc();
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;
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);
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);
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");
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);
388
currdep = first = adep;
390
currdep->next = adep;
391
currdep = currdep->next;
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
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;
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);
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;
505
previous->next = node;
506
previous = previous->next;
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) {
543
if ((d1->next != NULL && d2->next == NULL) ||
544
(d1->next == NULL && d2->next != NULL))
547
if (d1->next != NULL && d2->next != NULL)
548
if (!osl_dependence_equal(d1->next, d2->next))
551
if (!osl_relation_equal(d1->domain, d2->domain))
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)
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) {
607
(*now)->next = dependence;
611
while ((*now)->next != NULL)
618
* osl_nb_dependences function:
619
* This function returns the number of dependences in the dependence
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;
627
while (dep != NULL) {
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
interface->URI = strdup(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;
added
removed
osl/source/extensions/dependence.c
