[PATCH] Add support for may writes.
Tobias Grosser
object there also exist accesses which may write or may not write. This
can happen e.g. in cases of aliasing or unknown access functions.
There is no need to add may read support as this can be seen as a
normal read where the data read is just not used.
---
include/openscop/statement.h | 19 ++++++++++---------
source/statement.c | 26 +++++++++++++++++++++-----
tests/polynom.scop | 4 ++++
3 files changed, 35 insertions(+), 14 deletions(-)
diff --git a/include/openscop/statement.h b/include/openscop/statement.h
index 83f6d80..d40b452 100644
--- a/include/openscop/statement.h
+++ b/include/openscop/statement.h
@@ -82,15 +82,16 @@ extern "C"
*/
struct openscop_statement
{
- int version; /**< Version of the data structure */
- openscop_relation_p domain; /**< Iteration domain of the statement */
- openscop_relation_p schedule; /**< Scheduling function for the statement */
- openscop_relation_list_p read; /**< Array read access informations */
- openscop_relation_list_p write; /**< Array write access informations */
- int nb_iterators; /**< Number of names in 'iterators' */
- char ** iterators; /**< Array of iterator names */
- char * body; /**< Original statement body */
- void * usr; /**< A user-defined field, not touched
+ int version; /**< Version of the data structure */
+ openscop_relation_p domain; /**< Iteration domain */
+ openscop_relation_p schedule; /**< Scheduling function */
+ openscop_relation_list_p read; /**< Array read access information */
+ openscop_relation_list_p write; /**< Array write access information */
+ openscop_relation_list_p may_write; /**< Array may write access information */
+ int nb_iterators; /**< Number of names in 'iterators' */
+ char ** iterators; /**< Array of iterator names */
+ char * body; /**< Original statement body */
+ void * usr; /**< A user-defined field, not touched
by the OpenScop Library. */
struct openscop_statement * next; /**< Next statement in the linked list */
};
diff --git a/source/statement.c b/source/statement.c
index 560e640..829fc2c 100644
--- a/source/statement.c
+++ b/source/statement.c
@@ -127,6 +127,9 @@ openscop_statement_print_structure(FILE * file, openscop_statement_p statement,
// Print the array write access informations of the statement.
openscop_relation_list_print_structure(file, statement->write, level+1);
+ // Print the array may write access informations of the statement.
+ openscop_relation_list_print_structure(file, statement->may_write, level+1);
+
// Print the original iterator names.
for (i = 0; i <= level; i++)
fprintf(file, "|\t");
@@ -253,6 +256,13 @@ openscop_statement_print_openscop(FILE * file, openscop_statement_p statement,
statement->nb_iterators, statement->iterators,
nb_parameters, parameters,
nb_arrays, arrays);
+ fprintf(file, "# May write access informations\n");
+ openscop_relation_list_print_openscop(file, statement->may_write,
+ OPENSCOP_TYPE_ACCESS,
+ statement->nb_iterators, statement->iterators,
+ nb_parameters, parameters,
+ nb_arrays, arrays);
+
fprintf(file, "\n");
fprintf(file, "# ---------------------------------------------- ");
@@ -311,6 +321,7 @@ openscop_statement_read(FILE * file)
{
stmt->read = openscop_relation_list_read(file);
stmt->write = openscop_relation_list_read(file);
+ stmt->may_write = openscop_relation_list_read(file);
}
// Read the body information, if any.
@@ -373,6 +384,7 @@ openscop_statement_malloc()
statement->schedule = NULL;
statement->read = NULL;
statement->write = NULL;
+ statement->may_write = NULL;
statement->nb_iterators = 0;
statement->iterators = NULL;
statement->body = NULL;
@@ -401,6 +413,7 @@ openscop_statement_free(openscop_statement_p statement)
openscop_relation_free(statement->schedule);
openscop_relation_list_free(statement->read);
openscop_relation_list_free(statement->write);
+ openscop_relation_list_free(statement->may_write);
if (statement->iterators != NULL)
{
for (i = 0; i < statement->nb_iterators; i++)
@@ -481,6 +494,7 @@ openscop_statement_copy(openscop_statement_p statement)
node->schedule = openscop_relation_copy(statement->schedule);
node->read = openscop_relation_list_copy(statement->read);
node->write = openscop_relation_list_copy(statement->write);
+ node->may_write = openscop_relation_list_copy(statement->may_write);
node->nb_iterators = statement->nb_iterators;
node->iterators = openscop_util_copy_strings(statement->iterators,
statement->nb_iterators);
@@ -528,11 +542,12 @@ openscop_statement_equal(openscop_statement_p s1, openscop_statement_p s2)
return 0;
if (//(s1->version != s2->version) ||
- (s1->nb_iterators != s2->nb_iterators) ||
- (!openscop_relation_equal(s1->domain, s2->domain)) ||
- (!openscop_relation_equal(s1->schedule, s2->schedule)) ||
- (!openscop_relation_list_equal(s1->read, s2->read)) ||
- (!openscop_relation_list_equal(s1->write, s2->write)) ||
+ (s1->nb_iterators != s2->nb_iterators) ||
+ (!openscop_relation_equal(s1->domain, s2->domain)) ||
+ (!openscop_relation_equal(s1->schedule, s2->schedule)) ||
+ (!openscop_relation_list_equal(s1->read, s2->read)) ||
+ (!openscop_relation_list_equal(s1->write, s2->write)) ||
+ (!openscop_relation_list_equal(s1->may_write, s2->may_write)) ||
(strcmp(s1->body, s2->body) != 0))
return 0;
@@ -541,4 +556,5 @@ openscop_statement_equal(openscop_statement_p s1, openscop_statement_p s2)
return 0;
return 1;
+
}
diff --git a/tests/polynom.scop b/tests/polynom.scop
index 8408c44..1c7eee6 100644
--- a/tests/polynom.scop
+++ b/tests/polynom.scop
@@ -93,6 +93,10 @@ c0 c1 c2 c3 c4
1
1 5
1 1 1 0 0 ## C[i+j]
+# May write access informations
+1
+1 5
+ 1 1 1 0 0 ## C[i+j]
# ---------------------------------------------- 1.4 Body
# Statement body is provided
--
1.7.1
Tobias Grosser
> Besides plain read and write accesses, which always read or write a data
> object there also exist accesses which may write or may not write. This
> can happen e.g. in cases of aliasing or unknown access functions.
> There is no need to add may read support as this can be seen as a
> normal read where the data read is just not used.
This patch is on top of your relations branch.
Any plans to push your work to the official repository?
Cheers
Tobi
Cédric Bastoul
On 10/22/2010 07:37 AM, Cédric Bastoul wrote:Great.
Hi Tobias,
thanks for this patch.
Sure I do have plans to push the relation branch to the main repository, but
it's not finished yet, I failed to finish last week and this one has been
full of other stuff. By next week it will be ready, including documentation.
I think I found a good tradeoff to embed both matrix and relation notation :
there is only one relation data structure and it includes a matrix iff the
nb_local_dims is -1. I'll document this.
I understand your concern about extending openscop too much and I totally agree everything that adds additional information to a SCoP, which is not needed by every tool should be optional. In case this optional information is missing or not supported the tools will return conservative results.
I my quest to keep the data structure as minimal as possible, can't the may
write be embedded in an optional field that would detail for each statement
which write is a must, and which write is a may ? No option meaning must
write everywhere.
I am not sure if this can be achieved with may writes, because if a program has may writes and they are treated as must writes because e.g. candl does not yet support them, the calculated dependences will be incorrect. I can not see any good way to express may writes using only must writes and reads. I believe it could be simulated by creating a read and a must write on the same value, however this will introduce a lot of new dependences.
Also may writes are more and more important in upcoming tools. We have them in graphite/gcc and polly/llvm because of aliasing, but they are also used to express unknown access functions. ISL dependency analysis has native support for them and the upcoming dependency analysis in polly will also have them.
I strongly believe there is no difference in terms of importance between read/write/may-write and would highly prefer to add them into the standard openscop library.You are right. However are those data structures necessary for the correctness of a program or do they add more information for the analysis?
I plan an optional part for live-in live-out information as well, rather
than including it directly in the data structure. Same for the types of the
accessed data. The point is we will never end-up finding new interesting
properties to add and I don't like the idea of an always growing scop data
structure...
However for such useful options, I suggest to:be aopenscop_util_write_tag_arrays as
- create a new "openscop_options_t" data structure,
- put in this structure all the stuff we would like,
- and provide functions at least to read/write the options from the option
tags (see the example of openscop_util_read_tag_arrays, and there will
well),
- provide full specification/documentation for those options/functions.
I think this is a good idea. I am e.g. highly interested in the options representing dependences.I agree we should separate between optional and non optional parts. To decide what is optional or not I believe we should choose the criteria suggested above.
I mean I would like a clear separation between the core (I think it's well
defined now) and the options, just like in the file. So we can let the
optional part grow and the core part be clean and well defined.
What do you think ?
Anything needed for correctness is non optional, everything that can be conservatively approximated or recalculated without the optional part is optional.
What do you think?
Cheers
Tobi
P.S.: What about using the mailing list for such discussions? I think they are helpful for a wider range of people.
Tobias Grosser
On 10/25/2010 01:03 PM, C�dric Bastoul wrote:
> Hi Tobias,
> I mostly agree with your criterion. However I'm still not fond of putting
> may writes in the "main part", let me give you three reasons for that (well,
> in the end there is only one reason):
> - (part I) Correctness is relative to the analysis that will be done, e.g.,
> considering may write as must write is OK for a basic data dependence
> analysis, but not for dataflow analysis, so I'm sure we could find many
> analyses that would require other additional info to be correct...
You are right on this point. All depends on the analysis.
> - (part II) May-write information is necessary mostly (only ?) when we have
> to deal with codes that are not static. I do plan to add support for as many
> irregularities as possible, starting with Walid's work, but I think the
> optional part is the way to go (in the SCoP part, let there be... SCoPs).
This depends on what you regard as static. During my work on
graphite/polly every function that is internally completely static, but
takes pointers as input to define the arrays that it is working on,
needs may writes, as those arrays may alias.
Consider this function:
void foo (int *A, int *B, int *C);
GCC/LLVM alias analysis just gives you the information that A & B and B
& C may alias. This means there are two alias sets S1 = {A,B}, S2 = {B,
C}. We model this as if A must write to S1, C must write to S2 and B may
write to either S1 or S2.
The SCoP is internally completely static, but because it works on user
defined arrays it needs may writes. As all useful functions work on user
defined arrays, any function has may writes as long as the alias
analysis can not prove otherwise.
For GCC/LLVM those may writes appear for a lot of "all-static" SCoPs and
are as common as normal writes. Treating them as an extension seems to
be wrong (for graphite/polly).
> - (synthesis) Considering only static control programs in the main part
> would ensure we can do a wide range of analyses in an exact way without any
> additional information, so I believe we should dedicate the main part to
> them and only them.
I agree we should not try to put everything into core openscop, however
for me may writes are very common and important (as stated above).
I believe they are simple, very well understood and do not add a lot of
overhead on tools using openscop. Tools can either treat them as plain
writes or bail out if this would be incorrect.
In case we add them as optional I am afraid a lot of tools that use
openscop will forget about may writes and will therefore be unusable for
graphite/polly. Especially as the work on supporting them is so easy,
this would be really sad.
Therefore I still propose including may writes in the openscop core, but
I am fine with adding anything just needed for non static extensions to
the optional part.
Cheers
Tobi
P.S.: I added Sebastian, Albert & Louis-Noel to check if my view of the
importance of may writes is actually correct.
> "options" is probably a badly chosen name, "extensions" sounds better...
>
> Ced
>
> On Fri, Oct 22, 2010 at 2:13 PM, Tobias Grosser
> <gro...@fim.uni-passau.de>wrote:
>
Tobias Grosser
> On Fri, Oct 29, 2010 at 07:23:22AM +0200, Albert Cohen wrote:
>> Hi Tobias, Cedric,
>>
>> I agree that may-writes are ubiquitous in GCC/LLVM and with you
>> overall analysis.
>>
>> I propose to have array references to be qualified as may or must in
>> the main part of OpenSCoP, the default being must, and may being
>> encoded with some extra flag in the array reference. The most
>> important filter to inform about may/must will be ADA, so I include
>> Skimo as well in the discussion. All the other filters should work
>> without any change, or at most checking the flag in case there is no
>> clean way to avoid adding a 0 for the must case.
>>
>> Adapting ADA will be harder, and need some form of FADA (even a
>> conservative one). Skimo may have suggestions there. Mine would be
>> to simply bail out from ADA when a may def reference is encountered,
>> for now.
>
> Is the current support in isl for may accesses insufficient in some way?
I have not seen any problem with it. I used it to implement the
dependence analysis in polly (which took me a day). I believe it
calculates everything we need in an optimal form. For now I do not have
any idea how to improve this, as it already contains perfect may write
support. I am just waiting for it to appear in the isl version bundled
with CLooG.
Thanks a lot
Tobi
Tobias Grosser
> On Fri, Oct 29, 2010 at 09:55:26AM -0400, Tobias Grosser wrote:
>> I have not seen any problem with it. I used it to implement the
>> dependence analysis in polly (which took me a day). I believe it
>> calculates everything we need in an optimal form. For now I do not
>> have any idea how to improve this, as it already contains perfect
>> may write support. I am just waiting for it to appear in the isl
>> version bundled with CLooG.
>
> but, more generally, why would you wait for the isl that is used
> inside CLooG to get upgraded when you are using it for something
> not related to CLooG?
Because CLooG and ISL are both linked to Polly, which is why I need to
use a ISL that is compatible with CLooG.
CLooG does currently neither compile nor work with trunk ISL. The
version which is most probably working with CLooG is the one bundled
with it.
Cheers
Tobi
Sven Verdoolaege
> Because CLooG and ISL are both linked to Polly, which is why I need
> to use a ISL that is compatible with CLooG.
> CLooG does currently neither compile nor work with trunk ISL. The
> version which is most probably working with CLooG is the one bundled
> with it.
Which versions of isl and CLooG are you using?
All I can think of is the incompatible change in commit
27b6c99 (rename isl_map_remove to isl_map_remove_dims,
Sat Oct 23 13:42:21 2010 +0200) and that you are using
a descent of that commit, while you don't have the corresponding
24ae49f (update isl for renaming of isl_map_remove,
Sat Oct 23 13:42:44 2010 +0200) in CLooG yet.
If so, either move to 27b6c99^ in isl or update CLooG.
If not, please let me know what kind of problem you are experiencing.
In general, you shouldn't have to wait for an update in CLooG
to use a new feature in isl. That sort of defeats the purpose
of having isl as a submodule.
skimo
Albert Cohen
>> Is the current support in isl for may accesses insufficient in some way?
>
> dependence analysis in polly (which took me a day). I believe it
> calculates everything we need in an optimal form. For now I do not have
> any idea how to improve this, as it already contains perfect may write
> support. I am just waiting for it to appear in the isl version bundled
> with CLooG.
The question was more for ADA. But indeed, if isl now checks for the may
attribute in the incremental computation of instancewise reaching
definitions (a.k.a. value-based deps), we are fine. I must have missed
this improvement. A more accurate analysis will be needed later, but at
least it should be correct and a good motivation for supporting may in
the trunk of OpenSCoP.
Albert
Sven Verdoolaege
> The question was more for ADA. But indeed, if isl now checks for the
> may attribute in the incremental computation of instancewise
> reaching definitions (a.k.a. value-based deps), we are fine.
What's the difference between ADA and value-based deps?
> I must have missed this improvement.
I demonstrated it during my (second) iscc tutorial.
It's how I implemented the perhaps not so aptly named
any - last - before - under - operation.
skimo
Albert Cohen
> On Sat, Oct 30, 2010 at 04:18:28PM +0200, Albert Cohen wrote:
>> may attribute in the incremental computation of instancewise
>> reaching definitions (a.k.a. value-based deps), we are fine.
>
There is none. That's why we should be fine with the current
conservative implementation.
>> I must have missed this improvement.
>
> I demonstrated it during my (second) iscc tutorial.
> It's how I implemented the perhaps not so aptly named
> any - last - before - under - operation.
I probably missed that part when I was answering a call :-(
> skimo