From 6fe63ddc1896790c162bb2d13ce5c8050f4180de Mon Sep 17 00:00:00 2001 From: Cedric Bastoul Date: Tue, 5 Oct 2010 23:02:25 +0200 Subject: [PATCH] Switch from matrix to relation data structure --- autogen.sh | 2 +- configure.in | 2 +- doc/clan.texi | 196 ++- include/Makefile.am | 17 +- include/openscop/{vector.h => arrays.h} | 60 +- include/openscop/{vector.h => comment.h} | 58 +- include/openscop/{vector.h => extension.h} | 63 +- include/openscop/macros.h | 33 +- include/openscop/openscop.h | 7 +- include/openscop/relation.h | 22 +- include/openscop/{matrix.h => relation_list.h} | 80 +- include/openscop/scop.h.in | 40 +- include/openscop/statement.h | 55 +- include/openscop/{openscop.h => util.h} | 37 +- include/openscop/vector.h | 4 +- redo.sh | 5 + source/Makefile.am | 19 +- source/extension.c | 380 +++++ .../vector.h => source/extensions/arrays.c | 102 +- .../vector.h => source/extensions/comment.c | 100 +- source/matrix.c | 975 ----------- source/relation.c | 1416 +++++++++++++++ source/relation_list.c | 459 +++++ source/scop.c | 1802 ++++++++++---------- source/statement.c | 508 +++--- source/util.c | 463 +++++ source/vector.c | 155 +- tests/Makefile.am | 2 +- tests/openscop_test.c | 12 +- tests/polynom.scop | 38 +- 30 files changed, 4565 insertions(+), 2547 deletions(-) copy include/openscop/{vector.h => arrays.h} (78%) copy include/openscop/{vector.h => comment.h} (78%) copy include/openscop/{vector.h => extension.h} (74%) rename include/openscop/{matrix.h => relation_list.h} (68%) copy include/openscop/{openscop.h => util.h} (82%) create mode 100755 redo.sh create mode 100644 source/extension.c copy include/openscop/vector.h => source/extensions/arrays.c (76%) copy include/openscop/vector.h => source/extensions/comment.c (76%) delete mode 100644 source/matrix.c create mode 100644 source/relation.c create mode 100644 source/relation_list.c rewrite source/scop.c (65%) create mode 100644 source/util.c diff --git a/autogen.sh b/autogen.sh index ec90c00..b67de1f 100755 --- a/autogen.sh +++ b/autogen.sh @@ -1,5 +1,5 @@ #! /bin/sh aclocal -I autoconf -glibtoolize --force --copy +libtoolize --force --copy autoreconf -vfi diff --git a/configure.in b/configure.in index 19ab7a0..1073144 100644 --- a/configure.in +++ b/configure.in @@ -67,7 +67,7 @@ dnl Input file for autoconf to build a configuration shellscript. AC_PREREQ(2.13) dnl Fill here the @bug email adress. -AC_INIT([openscop], [0.3.0], [cedric.bastoul@u-psud.fr,pouchet@cse.ohio-state.edu]) +AC_INIT([openscop], [0.4.0], [cedric.bastoul@u-psud.fr,pouchet@cse.ohio-state.edu]) dnl A common file, which serve as a test. AC_CONFIG_SRCDIR([include/openscop/macros.h]) dnl Put as most as possible configuration files to an auxialiry diff --git a/doc/clan.texi b/doc/clan.texi index 983cabc..9c33e60 100644 --- a/doc/clan.texi +++ b/doc/clan.texi @@ -1,30 +1,27 @@ \input texinfo @c % @c % /**-----------------------------------------------------------------** -@c % ** Clan ** +@c % ** OpenScop Library ** @c % **-----------------------------------------------------------------** -@c % ** clan.texi ** +@c % ** openscop.texi ** @c % **-----------------------------------------------------------------** @c % ** First version: september 10th 2006 ** @c % **-----------------------------------------------------------------**/ @c % @c % release 0.0: May 4th 2008 @c % -@c %/************************************************************************** -@c % * Clan: the Chunky Loop Analyzer (experimental) * -@c % **************************************************************************/ - @c % /************************************************************************* @c % * PART I: HEADER * @c % *************************************************************************/ @c %**start of header -@setfilename clan.info -@settitle Clan - a polyhedral representation extractor for high level programs +@setfilename openscop.info +@settitle OpenScop - File Format and Data Structures for Polyhedral Compilation Tools @set EDITION 1.0 -@set VERSION 1.0.0 -@set UPDATED May 4th 2008 +@set SPEC_VERSION 1.0 +@set LIB_VERSION 1.0 +@set UPDATED November 13th 2010 @c @set UPDATED Coming soon @setchapternewpage odd @@ -35,18 +32,19 @@ @c %**end of header -@c % /************************************************************************* -@c % * PART II: SUMMARY DESCRIPTION AND COPYRIGHT * -@c % *************************************************************************/ +@c % /************************************************************************ +@c % * PART II: SUMMARY DESCRIPTION AND COPYRIGHT * +@c % ************************************************************************/ @copying -This manual is for Clan version @value{VERSION}, a software -which extracts the polyhedral representation of some parts of -high level programs written in C, C++, C# or Java. +This document describes OpenScop, a specification of a file format and a set +of data structures for polyhedral compilation tools to be able to talk +together. It also describes the OpenScop Library version @value{LIB_VERSION}, +a Free Software that provides an example of OpenScop implementation. It would be quite kind to refer the following paper in any publication that -results from the use of the Clan software or its library (the reason to cite -it is, amongst many other interesting things, it defines what is a @emph{SCoP}, +results from the use of the OpenScop library (the reason to cite this paper is, +amongst many other interesting thing, that it defines what is a @emph{SCoP}, or @emph{static control part}): @example @@ -63,7 +61,7 @@ or @emph{static control part}): @} @end example -Copyright @copyright{} 2008 C@'edric Bastoul. +Copyright @copyright{} 2010 C@'edric Bastoul. @c quotation Permission is granted to copy, distribute and/or modify this document under @@ -78,9 +76,9 @@ GNU Free Documentation License, write to the Free Software Foundation, Inc., @c % * PART III: TITLEPAGE, CONTENTS, COPYRIGHT * @c % *************************************************************************/ @titlepage -@title Clan -@subtitle A Polyhedral Representation Extractor for High Level Programs -@subtitle Edition @value{EDITION}, for Clan @value{VERSION} +@title OpenScop +@subtitle File Format and Data Structures for Data Exchange in Polyhedral Compilation Tools +@subtitle Edition @value{EDITION}, for OpenScop Specification @value{SPEC_VERSION} and OpenScop Library @value{LIB_VERSION} @subtitle @value{UPDATED} @author C@'edric Bastoul @@ -98,7 +96,7 @@ GNU Free Documentation License, write to the Free Software Foundation, Inc., @c % *************************************************************************/ @ifnottex @node Top -@top CLooG +@top OpenSCop @insertcopying @end ifnottex @@ -106,9 +104,8 @@ GNU Free Documentation License, write to the Free Software Foundation, Inc., @menu * Introduction:: * Polyhedral Representation:: -* Clan Software:: +* OpenScop File Format Specification:: * Clan Library:: -@c * Hacking:: * Installing:: * Documentation:: * References:: @@ -123,55 +120,94 @@ GNU Free Documentation License, write to the Free Software Foundation, Inc., @c % ****************************** INTRODUCTION ****************************** @node Introduction @chapter Introduction -Clan is a free software and library that translates some particular parts of -high level programs written in C, C++, C# or Java into a polyhedral representation. -This representation -may be manipulated by other tools to, e.g., achieve complex program -restructurations (for optimization, parallelization or any other kind of -manipulation). It has been created to avoid tedious and error-prone input -file writing for polyhedral tools (such as CLooG, LeTSeE, Candl etc.). -Using Clan, the user has to deal with source codes based on C grammar only -(as C, C++, C# or Java). - -Clan stands for @emph{Chunky Loop ANalyzer}: it is a part of the Chunky -project, a research tool for data locality improvement (@pxref{Bas03a}). -It is designed to be the front-end of any source-to-source automatic optimizers -and/or parallelizers. - -Clan is a very basic tool since it is only a translator from a given program -representation to another representation. Nevertheless the current version is -still under evaluation, and there is no guarantee that the upward compatibility -will be respected. A lot of reports are necessary to freeze the library -API and the input/output file shapes. The current output file format has been -designed after discussions between several compilation researchers from -various institutions. Thus you are very welcome and encouraged to send reports -on bugs, wishes, critics, comments, suggestions or (please !) successful -experiences to cedric.bastoul@@inria.fr. +OpenScop is an open specification that defines a file format and a set of +data structures to represent a @emph{static control part} (SCoP for short), +i.e., a program part that can be represented in the @emph{polyhedral model}. +The goal of OpenScop is to provide a common interface to the different +polyhedral compilation tools in order to simplify their interaction. + +Designing a single format for tools that have different purposes +(e.g., as different as code generation and data dependence analysis) may +sound strange at first. However we could observe that most available +polyhedral compilation tool during the last decade were manipulating +more or less the same kind of data (polyhedra, affine functions...) and +were actually sharing a part of their input (e.g., iteration domains and +context concepts are nearly everywhere). We could also observe that +those tools may rely on different internal representations, mostly based on +one of the major polyhedral libraries (e.g., Polylib, PPL or isl), and +this representation may change over time (e.g., when switching to a +more convenient polyhedral library). +The OpenScop aim is to provide a stable, unified format that offers a +durable guarantee that a tool can use an output or provide an input to +another tool without breaking a tool chain because of slight internal +changes. The other promise of OpenScop is the ablility to assemble or +replace the basic blocs of a polyhedral compilation framework at no, or +at least low engineering cost. + +The policy that drives OpenScop can be summarized by these three main rules: +@itemize @bullet +@item Embbed the @emph{minimum} information to build a complete polyhedral + compilation framework in the core part (to avoid as much as possible + empty or useless fields for each tool). +@item Provide a @emph{very stable} core part (including powerful enough + objects to support state-of-the-art techniques, to avoid + spending time to maintain an OpenScop input or output), +@item Provide a @emph{very flexible} extension part (so OpenScop can also + be used to test wild new ideas). +@end itemize + +The success of OpenScop in meeting its goals totally depend on its +acceptance by the tool developpers (that have to support it in their tools). +To help them, we provide an example implementation: the OpenScop Library. +This library (and in particular its API) is not part of the OpenScop +specification (which includes only the file format and the set of data +structures). It is licensed under the 3-clause BSD license so developpers may +feel free to use it in their code (either by linking it or copy-pasting its +code). This document also describes this library in details. +The current version of the OpenScop Library is still under evaluation, +and there is no guarantee that the upward compatibility will be respected, +even if we do think so. A lot of reports are +necessary to freeze the library API. Thus you are very welcome and +encouraged to send reports on bugs, wishes, critics, comments, suggestions +or (please !) successful experiences to cedric.bastoul@@u-psud.fr. + +This document is organized as follows. First, we provide some +background on the polyhedral model and how it is used to represent and to +manipulate programs (@pxref{Polyhedral Representation}). Next, +we describe the OpenScop specification, from the file format +(@pxref{OpenScop File Format Specification}) to the data structures and +details of the OpenScop Library API +(@pxref{OpenScop Data Structure Specification}). +Finally we will detail how to install the OpenScop Library +(@pxref{Installing}). @c % ******************* POLYHEDRAL REPRESENTATION OF PROGRAMS **************** @node Polyhedral Representation @chapter Polyhedral Representation of Programs -If you are reading the Clan's user manual, you probably don't need any -explanation about the Polyhedral Model. It's unlikely someone will read this -manual by chance. However some vicious advisor may ask their poor +If you are reading at OpenScop's documentation, you probably don't need any +explanation about the Polyhedral Model. It is unlikely someone will read this +paper by chance. However some vicious advisor may ask their poor engineers/interns/students to work for the very first time on this exciting topic. Most papers on -Polyhedral Compilation are hard to read. Despite my efforts, +polyhedral compilation are hard to read. Despite my efforts, mine are no exception according to some reviewers... Hence I give there a new try to provide a comprehensive explanation of the polyhedral model without the size and style limits of a classical research paper. -Be aware that to be able to understand the Polyhedral Model, there are few +Be aware that to be able to understand the polyhedral model, there are few prerequisites. You should not read the following while you still ignore what is: @itemize @bullet -@item a @code{for} loop construction in C programs, +@item a @code{for} loop construction in C programs (@code{do} loops in FORTRAN are OK too !), @item an @emph{affine expression}, @item a @emph{vector}, @item a @emph{matrix}, @item a @emph{matrix-vector multiply}. @end itemize +If you do not know those concepts, please do some search and come back +afterwards. And if you are courageous enough, send me a few lines that +describe them so I can insert that here ! @menu * Motivation:: @@ -182,8 +218,8 @@ what is: @node Motivation @section Motivation: Program Transformations -A direct translation of high level programs written, e.g., in C to assembly -then object code is likely to produce (very) inefficient applications. +A direct translation of high level programs written, e.g., in C, to assembly +then to object code is likely to produce (very) inefficient applications. Architectures are quite complex, including several levels of cache memory, many cores, deep pipelines, various number of functionnal units, of registers etc. @@ -233,9 +269,8 @@ y = c + d; We could also notice that it is possible to run the three statements in parallel and explicit this in the way the compiler and/or the architecture is -able to understand. Here we use OpenMP to describe parallelism. It is -supported in GCC since 4.2 version (this is called a @emph{parallelizing} -transformation): +able to understand. Here we use OpenMP to describe parallelism +(this is called a @emph{parallelizing} transformation): @example @group @@ -280,12 +315,11 @@ to run too many operations in parallel: Such transformations are quite trivial. The reason is the statements are executed only once. The real sport begins when we have to deal with loops -as we will see momentarily. However, Clan users have to be conscious that -we @emph{need} to transform programs to achieve the best performance and that -the best transformation that have to be discovered -(with often many, many efforts) and performed may be -quite complex. Hence the need of powerful model and tools -(Who said Polyhedral Model and CLooG ? Right !). +as we will see momentarily. However, polyhedral compilation framework users +have to be conscious that we @emph{need} to transform programs to achieve +the best performance and that the best transformation that have to be +discovered (with often many, many efforts) and performed may be +quite complex. Hence the need of powerful model and tools. @node Thinking in Polyhedra @@ -308,7 +342,7 @@ Loop transformations operate on statement executions. For instance, because they consider all statement executions at the same time, present day production compilers are not able to achieve loop fusion (that tries to merge the loop bodies of two loops) if the loop bounds -of the two loops do not match. +of the two loops do not match (hahaha). @noindent @strong{This is a limitation for program manipulation flexibility.} Trees are very rigid data structures that are not easy to manipulate. @@ -337,7 +371,7 @@ a @strong{Static Control Part} or @strong{SCoP} for short. @node Iteration Domain @subsection Iteration Domain -The key aspect of the Polyhedral Model is to consider @emph{statement +The key aspect of the polyhedral model is to consider @emph{statement instances}. A statement instance is @emph{one} execution of a statement. A statement outside a loop has only one instance while those inside loops may have many. @@ -358,11 +392,11 @@ unroll the loop): @example @group pi = 3.14; -A[0] = x; -A[1] = x; -A[2] = x; -A[3] = x; -A[4] = x; +A[0] = pi; +A[1] = pi; +A[2] = pi; +A[3] = pi; +A[4] = pi; @end group @end example @@ -371,7 +405,7 @@ thanks to its outer loop counters (or @emph{iterators}). In the Polyhedral Model we consider statements as functions of the outer loop counters that may produce statement instances: instead of simply "@code{S2}", we use preferably the notation @code{S2(i)}. -For instance we denote the statement instance @code{A[3] = x;} of the +For instance we denote the statement instance @code{A[3] = pi;} of the previous example as @code{S2(3)}. This means @emph{instance of statement @code{S2} for} @code{i = 3}. If a statement @code{S3} is enclosed inside two loops of iterators @code{i} @@ -408,7 +442,7 @@ Here the only parameter is @code{N}. A compact way to represent all the instances of a given statement is to consider the set of all possible values of its iteration vector. This set is called the @strong{iteration domain}. It can be conveniently -described thanks to all the constraints on the various iterator the statement +described thanks to all the constraints on the various iterators the statement depends on. For instance, let us consider the statement @code{S3} of the previous program. The iteration domain is the set of iteration vectors @code{(i,j)}. Because of the parameter, we are not able to @@ -1106,9 +1140,9 @@ of a given statement. -@c % *********************** Using the Clan Software ************************** -@node Clan Software -@chapter Using the Clan Software +@c % *********************** OpenScop Specification ************************** +@node OpenScop File Format Specification +@chapter OpenScop File Format Specification @menu @@ -1734,10 +1768,10 @@ the end of the .scop file, between the @samp{} and @c %/************************************************************************* -@c % * Clan Library * +@c % * OpenScop Data Structure Specification * @c % *************************************************************************/ -@node Clan Library -@chapter Using the Clan Library +@node OpenScop Data Structure Specification +@chapter OpenScop Data Structure Specification The Clan Library was implemented to allow the user to call Clan directly from his programs, without file accesses or system calls. The user only needs to link his programs with C libraries. The Clan diff --git a/include/Makefile.am b/include/Makefile.am index c5bd82c..aa0f57e 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -75,10 +75,15 @@ MAINTAINERCLEANFILES = Makefile.in ############################################################################# -pkginclude_HEADERS = \ - openscop/openscop.h \ - openscop/statement.h \ - openscop/vector.h \ - openscop/matrix.h \ - openscop/macros.h \ +pkginclude_HEADERS = \ + openscop/openscop.h \ + openscop/statement.h \ + openscop/comment.h \ + openscop/arrays.h \ + openscop/extension.h \ + openscop/vector.h \ + openscop/relation.h \ + openscop/relation_list.h \ + openscop/macros.h \ + openscop/util.h \ openscop/scop.h diff --git a/include/openscop/vector.h b/include/openscop/arrays.h similarity index 78% copy from include/openscop/vector.h copy to include/openscop/arrays.h index cf50e79..36b3b2a 100644 --- a/include/openscop/vector.h +++ b/include/openscop/arrays.h @@ -2,9 +2,9 @@ /*+-----------------------------------------------------------------** ** OpenScop Library ** **-----------------------------------------------------------------** - ** vector.h ** + ** extensions/arrays.h ** **-----------------------------------------------------------------** - ** First version: 01/05/2008 ** + ** First version: 07/12/2010 ** **-----------------------------------------------------------------** @@ -61,12 +61,11 @@ *****************************************************************************/ -#ifndef OPENSCOP_VECTOR_H -# define OPENSCOP_VECTOR_H +#ifndef OPENSCOP_ARRAYS_H +# define OPENSCOP_ARRAYS_H -# include # include - +# include # if defined(__cplusplus) extern "C" @@ -74,47 +73,54 @@ extern "C" # endif +# define OPENSCOP_TAG_ARRAYS_START "" +# define OPENSCOP_TAG_ARRAYS_STOP "" + + /** - * The openscop_vector_t structure stores a vector information in the PolyLib - * format (the first entry has a specific meaning). When a vector - * describes a linear constraint, a 0 means it is an equality == 0, a 1 means - * an inequality >= 0. When the vector describes an array access, a number - * different than 0 is the array identifier. + * The openscop_arrays_t structure stores an arrays to the core + * OpenScop representation. It is a node of a NULL-terminated linked list of + * arrayss. */ -struct openscop_vector +struct openscop_arrays { - unsigned Size; /**< The number of vector entries */ - openscop_int_t * p; /**< An array of values */ + int textual; /**< 1 is the array names are strings, 0 otherwise. */ + void * names; /**< NULL-terminated array of names. */ }; -typedef struct openscop_vector openscop_vector_t; -typedef struct openscop_vector * openscop_vector_p; +typedef struct openscop_arrays openscop_arrays_t; +typedef struct openscop_arrays * openscop_arrays_p; /*+*************************************************************************** * Structure display function * *****************************************************************************/ -void openscop_vector_print_structure(FILE *, openscop_vector_p, int); -void openscop_vector_print(FILE *, openscop_vector_p); +void openscop_arrays_print_structure(FILE *, openscop_arrays_p, int); +void openscop_arrays_print(FILE *, openscop_arrays_p); +void openscop_arrays_print_openscop(FILE *, openscop_arrays_p); + + +/***************************************************************************** + * Reading function * + *****************************************************************************/ +openscop_arrays_p openscop_arrays_read(char *); /*+*************************************************************************** * Memory allocation/deallocation function * *****************************************************************************/ -openscop_vector_p openscop_vector_malloc(unsigned); -void openscop_vector_free(openscop_vector_p); +openscop_arrays_p openscop_arrays_malloc(); +void openscop_arrays_free(openscop_arrays_p); /*+*************************************************************************** * Processing functions * *****************************************************************************/ -openscop_vector_p openscop_vector_add_scalar(openscop_vector_p, int); -openscop_vector_p openscop_vector_add(openscop_vector_p, openscop_vector_p); -openscop_vector_p openscop_vector_sub(openscop_vector_p, openscop_vector_p); -void openscop_vector_tag_inequality(openscop_vector_p); -void openscop_vector_tag_equality(openscop_vector_p); -int openscop_vector_equal(openscop_vector_p, openscop_vector_p); +openscop_arrays_p openscop_arrays_copy(openscop_arrays_p); +int openscop_arrays_equal(openscop_arrays_p, openscop_arrays_p); + # if defined(__cplusplus) } # endif -#endif /* define OPENSCOP_VECTOR_H */ + +#endif /* define OPENSCOP_ARRAYS_H */ diff --git a/include/openscop/vector.h b/include/openscop/comment.h similarity index 78% copy from include/openscop/vector.h copy to include/openscop/comment.h index cf50e79..adfdb4e 100644 --- a/include/openscop/vector.h +++ b/include/openscop/comment.h @@ -2,9 +2,9 @@ /*+-----------------------------------------------------------------** ** OpenScop Library ** **-----------------------------------------------------------------** - ** vector.h ** + ** extensions/comment.h ** **-----------------------------------------------------------------** - ** First version: 01/05/2008 ** + ** First version: 07/12/2010 ** **-----------------------------------------------------------------** @@ -61,12 +61,11 @@ *****************************************************************************/ -#ifndef OPENSCOP_VECTOR_H -# define OPENSCOP_VECTOR_H +#ifndef OPENSCOP_COMMENT_H +# define OPENSCOP_COMMENT_H -# include # include - +# include # if defined(__cplusplus) extern "C" @@ -74,47 +73,52 @@ extern "C" # endif +# define OPENSCOP_TAG_COMMENT_START "" +# define OPENSCOP_TAG_COMMENT_STOP "" + + /** - * The openscop_vector_t structure stores a vector information in the PolyLib - * format (the first entry has a specific meaning). When a vector - * describes a linear constraint, a 0 means it is an equality == 0, a 1 means - * an inequality >= 0. When the vector describes an array access, a number - * different than 0 is the array identifier. + * The openscop_comment_t structure stores a comment extention to the core + * OpenScop representation. It is simply a 0-terminated string. */ -struct openscop_vector +struct openscop_comment { - unsigned Size; /**< The number of vector entries */ - openscop_int_t * p; /**< An array of values */ + char * comment; /**< A comment message as a 0-terminated string. */ }; -typedef struct openscop_vector openscop_vector_t; -typedef struct openscop_vector * openscop_vector_p; +typedef struct openscop_comment openscop_comment_t; +typedef struct openscop_comment * openscop_comment_p; /*+*************************************************************************** * Structure display function * *****************************************************************************/ -void openscop_vector_print_structure(FILE *, openscop_vector_p, int); -void openscop_vector_print(FILE *, openscop_vector_p); +void openscop_comment_print_structure(FILE *, openscop_comment_p, int); +void openscop_comment_print(FILE *, openscop_comment_p); +void openscop_comment_print_openscop(FILE *, openscop_comment_p); + + +/***************************************************************************** + * Reading function * + *****************************************************************************/ +openscop_comment_p openscop_comment_read(char *); /*+*************************************************************************** * Memory allocation/deallocation function * *****************************************************************************/ -openscop_vector_p openscop_vector_malloc(unsigned); -void openscop_vector_free(openscop_vector_p); +openscop_comment_p openscop_comment_malloc(); +void openscop_comment_free(openscop_comment_p); /*+*************************************************************************** * Processing functions * *****************************************************************************/ -openscop_vector_p openscop_vector_add_scalar(openscop_vector_p, int); -openscop_vector_p openscop_vector_add(openscop_vector_p, openscop_vector_p); -openscop_vector_p openscop_vector_sub(openscop_vector_p, openscop_vector_p); -void openscop_vector_tag_inequality(openscop_vector_p); -void openscop_vector_tag_equality(openscop_vector_p); -int openscop_vector_equal(openscop_vector_p, openscop_vector_p); +openscop_comment_p openscop_comment_copy(openscop_comment_p); +int openscop_comment_equal(openscop_comment_p, openscop_comment_p); + # if defined(__cplusplus) } # endif -#endif /* define OPENSCOP_VECTOR_H */ + +#endif /* define OPENSCOP_COMMENT_H */ diff --git a/include/openscop/vector.h b/include/openscop/extension.h similarity index 74% copy from include/openscop/vector.h copy to include/openscop/extension.h index cf50e79..814585c 100644 --- a/include/openscop/vector.h +++ b/include/openscop/extension.h @@ -2,9 +2,9 @@ /*+-----------------------------------------------------------------** ** OpenScop Library ** **-----------------------------------------------------------------** - ** vector.h ** + ** extension.h ** **-----------------------------------------------------------------** - ** First version: 01/05/2008 ** + ** First version: 26/11/2010 ** **-----------------------------------------------------------------** @@ -61,60 +61,69 @@ *****************************************************************************/ -#ifndef OPENSCOP_VECTOR_H -# define OPENSCOP_VECTOR_H +#ifndef OPENSCOP_EXTENSION_H +# define OPENSCOP_EXTENSION_H -# include # include - +# include +# include +# include # if defined(__cplusplus) extern "C" { # endif +#define OPENSCOP_EXTENSION_UNDEFINED 0 +#define OPENSCOP_EXTENSION_COMMENT 1 +#define OPENSCOP_EXTENSION_ARRAYS 2 /** - * The openscop_vector_t structure stores a vector information in the PolyLib - * format (the first entry has a specific meaning). When a vector - * describes a linear constraint, a 0 means it is an equality == 0, a 1 means - * an inequality >= 0. When the vector describes an array access, a number - * different than 0 is the array identifier. + * The openscop_extension_t structure stores an extension to the core + * OpenScop representation. It is a node of a NULL-terminated linked list of + * extensions. */ -struct openscop_vector +struct openscop_extension { - unsigned Size; /**< The number of vector entries */ - openscop_int_t * p; /**< An array of values */ + int type; /**< This extension's type. */ + void * extension; /**< Pointer to the extension itself. */ + struct openscop_extension * next; /**< Pointer to the next extension. */ }; -typedef struct openscop_vector openscop_vector_t; -typedef struct openscop_vector * openscop_vector_p; +typedef struct openscop_extension openscop_extension_t; +typedef struct openscop_extension * openscop_extension_p; /*+*************************************************************************** * Structure display function * *****************************************************************************/ -void openscop_vector_print_structure(FILE *, openscop_vector_p, int); -void openscop_vector_print(FILE *, openscop_vector_p); +void openscop_extension_print_structure(FILE *, openscop_extension_p, int); +void openscop_extension_print(FILE *, openscop_extension_p); +void openscop_extension_print_openscop(FILE *, openscop_extension_p); + + +/***************************************************************************** + * Reading function * + *****************************************************************************/ +char * openscop_extension_read_string(FILE *); +openscop_extension_p openscop_extension_read(FILE *); /*+*************************************************************************** * Memory allocation/deallocation function * *****************************************************************************/ -openscop_vector_p openscop_vector_malloc(unsigned); -void openscop_vector_free(openscop_vector_p); +openscop_extension_p openscop_extension_malloc(); +void openscop_extension_free(openscop_extension_p); /*+*************************************************************************** * Processing functions * *****************************************************************************/ -openscop_vector_p openscop_vector_add_scalar(openscop_vector_p, int); -openscop_vector_p openscop_vector_add(openscop_vector_p, openscop_vector_p); -openscop_vector_p openscop_vector_sub(openscop_vector_p, openscop_vector_p); -void openscop_vector_tag_inequality(openscop_vector_p); -void openscop_vector_tag_equality(openscop_vector_p); -int openscop_vector_equal(openscop_vector_p, openscop_vector_p); +openscop_extension_p openscop_extension_copy(openscop_extension_p); +int openscop_extension_equal(openscop_extension_p, openscop_extension_p); + # if defined(__cplusplus) } # endif -#endif /* define OPENSCOP_VECTOR_H */ + +#endif /* define OPENSCOP_EXTENSION_H */ diff --git a/include/openscop/macros.h b/include/openscop/macros.h index 9bc7074..6ea0c17 100644 --- a/include/openscop/macros.h +++ b/include/openscop/macros.h @@ -86,26 +86,31 @@ # endif -# define OPENSCOP_DEBUG 0 /* Set to 1 for debug mode, - 0 otherwise */ +# define OPENSCOP_DEBUG 0 // 1 for debug mode, 0 otherwise. +# define OPENSCOP_BACKEND_C 0 +# define OPENSCOP_BACKEND_FORTRAN 1 +# define OPENSCOP_UNDEFINED -1 # define OPENSCOP_MAX_STRING 2048 +# define OPENSCOP_MAX_ARRAYS 128 +# define OPENSCOP_TYPE_BARE 0 # define OPENSCOP_TYPE_ITERATOR 1 # define OPENSCOP_TYPE_PARAMETER 2 # define OPENSCOP_TYPE_ARRAY 3 # define OPENSCOP_TYPE_FUNCTION 4 -# define OPENSCOP_TYPE_DOMAIN 6 -# define OPENSCOP_TYPE_SCATTERING 7 -# define OPENSCOP_TYPE_ACCESS 8 -# define OPENSCOP_TYPE_UNKNOWN 9 +# define OPENSCOP_TYPE_CONTEXT 6 +# define OPENSCOP_TYPE_DOMAIN 7 +# define OPENSCOP_TYPE_SCATTERING 8 +# define OPENSCOP_TYPE_ACCESS 9 +# define OPENSCOP_TYPE_UNKNOWN 10 # define OPENSCOP_FAKE_ARRAY "fakearray" -# define OPENSCOP_SCOP_PRINT_CASTLE 1 -# define OPENSCOP_SCOP_PRINT_ARRAYSTAG 2 +# define OPENSCOP_TAG_ARRAY_START "" +# define OPENSCOP_TAG_ARRAY_STOP "" -/*+**************************************************************************** - * SCOP GMP MACROS * - ******************************************************************************/ +/*+*************************************************************************** + * OPENSCOP GMP MACROS * + *****************************************************************************/ # ifdef OPENSCOP_INT_T_IS_MP /* Basic Macros */ # define SCOPINT_init(val) (mpz_init((val))) @@ -143,9 +148,9 @@ # define SCOPINT_one_p(val) (mpz_cmp_si(val,1) == 0) # define SCOPINT_mone_p(val) (mpz_cmp_si(val,-1) == 0) -/*+**************************************************************************** - * SCOPINT BASIC TYPES MACROS * - ******************************************************************************/ +/*+*************************************************************************** + * OPENSCOP BASIC TYPES MACROS * + *****************************************************************************/ # else /* Basic Macros */ # define SCOPINT_init(val) ((val) = 0) diff --git a/include/openscop/openscop.h b/include/openscop/openscop.h index f0a06a1..10ee504 100644 --- a/include/openscop/openscop.h +++ b/include/openscop/openscop.h @@ -2,7 +2,7 @@ /*+-----------------------------------------------------------------** ** OpenScop Library ** **-----------------------------------------------------------------** - ** scop.h ** + ** openscop.h ** **-----------------------------------------------------------------** ** First version: 11/05/2010 ** **-----------------------------------------------------------------** @@ -66,8 +66,11 @@ # include +# include # include -# include +# include +# include +# include # include # include diff --git a/include/openscop/relation.h b/include/openscop/relation.h index 4365b51..c263e6c 100644 --- a/include/openscop/relation.h +++ b/include/openscop/relation.h @@ -66,6 +66,7 @@ # include # include +# include # include @@ -97,13 +98,13 @@ extern "C" */ struct openscop_relation { - unsigned nb_rows; /**< The number of rows */ - unsigned nb_columns; /**< The number of columns */ - unsigned nb_output_dims; /**< The number of output dimensions */ - unsigned nb_input_dims; /**< The number of input dimensions */ - unsigned nb_local_dims; /**< The number of local (existentially + int nb_rows; /**< The number of rows */ + int nb_columns; /**< The number of columns */ + int nb_output_dims; /**< The number of output dimensions */ + int nb_input_dims; /**< The number of input dimensions */ + int nb_local_dims; /**< The number of local (existentially quantified) dimensions */ - unsigned nb_parameters; /**< The number of parameters */ + int nb_parameters; /**< The number of parameters */ openscop_int_t ** m; /**< An array of pointers to the beginning of each row of the relation matrix */ struct openscop_relation * next; /**< Pointer to the next relation in the @@ -119,7 +120,7 @@ typedef struct openscop_relation * openscop_relation_p; void openscop_relation_print_structure(FILE *, openscop_relation_p, int); void openscop_relation_print(FILE *, openscop_relation_p); -void openscop_relation_print_dot_scop(FILE *, +void openscop_relation_print_openscop(FILE *, openscop_relation_p, int, int, char **, int, char **, int, char **); @@ -135,7 +136,7 @@ openscop_relation_p openscop_relation_read_arrays(FILE *, char ***, int *); /*+*************************************************************************** * Memory allocation/deallocation function * *****************************************************************************/ -openscop_relation_p openscop_relation_malloc(unsigned, unsigned); +openscop_relation_p openscop_relation_malloc(int, int); void openscop_relation_free_inside(openscop_relation_p); void openscop_relation_free(openscop_relation_p); @@ -143,6 +144,7 @@ void openscop_relation_free(openscop_relation_p); /*+*************************************************************************** * Processing functions * *****************************************************************************/ +int openscop_relation_is_matrix(openscop_relation_p); openscop_relation_p openscop_relation_ncopy(openscop_relation_p, int); openscop_relation_p openscop_relation_copy(openscop_relation_p); void openscop_relation_replace_vector(openscop_relation_p, @@ -162,7 +164,9 @@ openscop_relation_p openscop_relation_concat(openscop_relation_p, openscop_relation_p); int openscop_relation_equal(openscop_relation_p, openscop_relation_p); - +int openscop_relation_integrity_check(openscop_relation_p, + int, int, int, int); + # if defined(__cplusplus) } # endif diff --git a/include/openscop/matrix.h b/include/openscop/relation_list.h similarity index 68% rename from include/openscop/matrix.h rename to include/openscop/relation_list.h index f145419..bb1b41b 100644 --- a/include/openscop/matrix.h +++ b/include/openscop/relation_list.h @@ -2,9 +2,9 @@ /*+-----------------------------------------------------------------** ** OpenScop Library ** **-----------------------------------------------------------------** - ** matrix.h ** + ** relation_list.h ** **-----------------------------------------------------------------** - ** First version: 30/04/2008 ** + ** First version: 08/10/2010 ** **-----------------------------------------------------------------** @@ -61,12 +61,13 @@ *****************************************************************************/ -#ifndef OPENSCOP_MATRIX_H -# define OPENSCOP_MATRIX_H +#ifndef OPENSCOP_RELATION_LIST_H +# define OPENSCOP_RELATION_LIST_H # include # include # include +# include # if defined(__cplusplus) @@ -76,69 +77,60 @@ extern "C" /** - * The openscop_matrix_t structure stores a matrix information in the PolyLib - * format (the first entry of each row has a specific meaning). When a row - * describes a linear constraint, a 0 means it is an equality == 0, a 1 means - * an inequality >= 0. When a row describes an array access, a number different - * than 0 is the array identifier (the remainder of the row describes the - * access function of the first dimension of this array), otherwise it means - * the row describes access functions for next array dimensions. + * The openscop_relation_list_t structure describes a (NULL-terminated + * linked) list of relations. */ -struct openscop_matrix +struct openscop_relation_list { - unsigned NbRows; /**< The number of rows */ - unsigned NbColumns; /**< The number of columns */ - openscop_int_t ** p; /**< An array of pointers to the beginning - of each row */ - openscop_int_t * p_Init; /**< The matrix is stored here, contiguously - in memory */ - int p_Init_size; /**< Needed to free the memory allocated by - mpz_init. */ + openscop_relation_p elt; /**< An element of the list. */ + struct openscop_relation_list * next; /**< Pointer to the next element + of the list.*/ }; -typedef struct openscop_matrix openscop_matrix_t; -typedef struct openscop_matrix * openscop_matrix_p; +typedef struct openscop_relation_list openscop_relation_list_t; +typedef struct openscop_relation_list * openscop_relation_list_p; /*+*************************************************************************** * Structure display function * *****************************************************************************/ -void openscop_matrix_print_structure(FILE *, openscop_matrix_p, int); -void openscop_matrix_print(FILE *, openscop_matrix_p); -void openscop_matrix_print_dot_scop(FILE *, openscop_matrix_p, int, - int, char **, int, char **, int, char **); +void openscop_relation_list_print_structure(FILE *, + openscop_relation_list_p, int); +void openscop_relation_list_print(FILE *, openscop_relation_list_p); +void openscop_relation_list_print_openscop(FILE *, + openscop_relation_list_p, int, + int, char **, + int, char **, + int, char **); /***************************************************************************** * Reading function * *****************************************************************************/ -openscop_matrix_p openscop_matrix_read(FILE *); -openscop_matrix_p openscop_matrix_read_arrays(FILE *, char ***, int *); +openscop_relation_list_p openscop_relation_list_read(FILE *); /*+*************************************************************************** * Memory allocation/deallocation function * *****************************************************************************/ -openscop_matrix_p openscop_matrix_malloc(unsigned, unsigned); -void openscop_matrix_free_inside(openscop_matrix_p); -void openscop_matrix_free(openscop_matrix_p); +openscop_relation_list_p openscop_relation_list_malloc(); +void openscop_relation_list_free(openscop_relation_list_p); /*+*************************************************************************** * Processing functions * *****************************************************************************/ -openscop_matrix_p openscop_matrix_ncopy(openscop_matrix_p, int); -openscop_matrix_p openscop_matrix_copy(openscop_matrix_p); -openscop_matrix_p openscop_matrix_concat(openscop_matrix_p, openscop_matrix_p); -openscop_matrix_p openscop_matrix_from_vector(openscop_vector_p); -void openscop_matrix_replace_vector(openscop_matrix_p, openscop_vector_p, int); -void openscop_matrix_insert_vector(openscop_matrix_p, openscop_vector_p, int); -void openscop_matrix_add_vector(openscop_matrix_p, openscop_vector_p, int); -void openscop_matrix_sub_vector(openscop_matrix_p, openscop_vector_p, int); -void openscop_matrix_replace_matrix(openscop_matrix_p, openscop_matrix_p, int); -void openscop_matrix_insert_matrix(openscop_matrix_p, openscop_matrix_p, int); -int openscop_matrix_equal(openscop_matrix_p, openscop_matrix_p); - +openscop_relation_list_p openscop_relation_list_node(openscop_relation_p); +openscop_relation_list_p openscop_relation_list_copy(openscop_relation_list_p); +openscop_relation_list_p openscop_relation_list_concat( + openscop_relation_list_p, + openscop_relation_list_p); +int openscop_relation_list_equal(openscop_relation_list_p, + openscop_relation_list_p); +int openscop_relation_list_integrity_check( + openscop_relation_list_p, + int, int, int, int); + # if defined(__cplusplus) } # endif -#endif /* define OPENSCOP_MATRIX_H */ +#endif /* define OPENSCOP_RELATION_LIST_H */ diff --git a/include/openscop/scop.h.in b/include/openscop/scop.h.in index 9afd3f0..88b46ce 100644 --- a/include/openscop/scop.h.in +++ b/include/openscop/scop.h.in @@ -78,9 +78,11 @@ # endif # include -# include -# include +# include # include +# include +# include +# include # if defined(__cplusplus) @@ -90,25 +92,29 @@ extern "C" /** - * The scop_t structure stores the useful informations of a static + * The scop_t structure stores the useful information of a static * control part of a program to process it within a polyhedral framework. */ struct openscop_scop { int version; /**< Version of the data structure */ - openscop_matrix_p context; /**< Constraints on the SCoP parameters */ + int textual_names; /**< 1 if names are strings, 0 otherwise. */ + int textual_extensions; /**< 1 if extensions is a string, 0 if not.*/ + char * language; /**< Target language (backend) */ + openscop_relation_p context; /**< Constraints on the SCoP parameters */ int nb_parameters; /**< Number of parameters for the SCoP */ + int nb_iterators; /**< Number (max) of output dimensions */ int nb_scattdims; /**< Number (max) of scattering dimensions */ - int nb_arrays; /**< Number of arrays accessed in the SCoP */ - char ** parameters; /**< Array of (nb_parameters) param names */ - char ** scattdims; /**< Array of (nb_scattdims) scattering + char ** parameters; /**< Array of nb_parameters param names */ + char ** iterators; /**< Array of nb_iterators iterator names */ + char ** scattdims; /**< Array of nb_scattdims scattering dimension names */ - char ** arrays; /**< Array of (nb_arrays) array names */ openscop_statement_p statement; /**< Statement list of the SCoP */ - char * optiontags; /**< The content (as a 0 terminated - string) of the optional tags. */ + void * extensions; /**< Extensions. A 0-terminated string if + textual_extensions is 1, an + openscop_extension_p otherwise. */ void * usr; /**< A user-defined field, not touched - by the OpenScop Library. */ + AT ALL by the OpenScop Library. */ }; typedef struct openscop_scop openscop_scop_t; typedef struct openscop_scop * openscop_scop_p; @@ -119,17 +125,13 @@ typedef struct openscop_scop * openscop_scop_p; *****************************************************************************/ void openscop_scop_print_structure(FILE *, openscop_scop_p, int); void openscop_scop_print(FILE *, openscop_scop_p); -void openscop_scop_print_dot_scop(FILE *, openscop_scop_p); -void openscop_scop_print_dot_scop_options(FILE * file, openscop_scop_p scop, - int options); +void openscop_scop_print_openscop(FILE *, openscop_scop_p); /***************************************************************************** * Reading function * *****************************************************************************/ openscop_scop_p openscop_scop_read(FILE *); -char * openscop_scop_tag_content(openscop_scop_p, char *, char *); -char * openscop_scop_tag_content_from_string(char *, char *, char *); /*+*************************************************************************** @@ -137,12 +139,14 @@ char * openscop_scop_tag_content_from_string(char *, char *, char *); *****************************************************************************/ openscop_scop_p openscop_scop_malloc(); void openscop_scop_free(openscop_scop_p); -openscop_scop_p openscop_scop_dup(openscop_scop_p); + /*+*************************************************************************** * Processing functions * *****************************************************************************/ -int openscop_scop_equal(openscop_scop_p, openscop_scop_p); +openscop_scop_p openscop_scop_copy(openscop_scop_p); +int openscop_scop_equal(openscop_scop_p, openscop_scop_p); +int openscop_scop_integrity_check(openscop_scop_p); # if defined(__cplusplus) diff --git a/include/openscop/statement.h b/include/openscop/statement.h index 722f7ba..a4fae72 100644 --- a/include/openscop/statement.h +++ b/include/openscop/statement.h @@ -66,7 +66,9 @@ # include # include -# include +# include +# include +# include # if defined(__cplusplus) extern "C" @@ -75,21 +77,23 @@ extern "C" /** - * The openscop_statement_t structure stores the useful informations of a - * given statement to process it within a polyhedral framework. + * The openscop_statement_t structure stores a list of statement. Each node + * contains the useful informations for a given statement to process it + * within a polyhedral framework. The order in the list may matter for naming + * conventions (e.g. "S1" for the first statement in the list). */ struct openscop_statement { - int version; /**< Version of the data structure */ - openscop_matrix_p domain; /**< Iteration domain of the statement */ - openscop_matrix_p schedule; /**< Scheduling function for the statement */ - openscop_matrix_p read; /**< Array read access informations */ - openscop_matrix_p write; /**< Array write access informations */ - int nb_iterators; /**< Original depth of the statement */ - char ** iterators; /**< Array of (nb_iterators) iterator names */ - char * body; /**< Original statement body */ - void * usr; /**< A user-defined field, not touched - by the OpenScop Library. */ + int version; /**< Version of the data structure */ + openscop_relation_p domain; /**< Iteration domain of the statement */ + openscop_relation_p scattering; /**< Scattering 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 + AT ALL by the OpenScop Library. */ struct openscop_statement * next; /**< Next statement in the linked list */ }; typedef struct openscop_statement openscop_statement_t; @@ -101,31 +105,32 @@ typedef struct openscop_statement * openscop_statement_p; *****************************************************************************/ void openscop_statement_print_structure(FILE *, openscop_statement_p, int); void openscop_statement_print(FILE *, openscop_statement_p); -void openscop_statement_print_dot_scop(FILE *, openscop_statement_p, +void openscop_statement_print_openscop(FILE *, openscop_statement_p, int, char **, int, char **); -/****************************************************************************** - * Reading function * - ******************************************************************************/ -openscop_statement_p openscop_statement_read(FILE*, int, char***, int*); +/***************************************************************************** + * Reading function * + *****************************************************************************/ +openscop_statement_p openscop_statement_read(FILE*); -/*+**************************************************************************** - * Memory allocation/deallocation function * - ******************************************************************************/ +/*+*************************************************************************** + * Memory allocation/deallocation function * + *****************************************************************************/ openscop_statement_p openscop_statement_malloc(); void openscop_statement_free(openscop_statement_p); -/*+**************************************************************************** - * Processing functions * - ******************************************************************************/ +/*+*************************************************************************** + * Processing functions * + *****************************************************************************/ void openscop_statement_add(openscop_statement_p *, openscop_statement_p); void openscop_statement_compact(openscop_statement_p, int); int openscop_statement_number(openscop_statement_p); +openscop_statement_p openscop_statement_copy(openscop_statement_p); int openscop_statement_equal(openscop_statement_p, openscop_statement_p); - +int openscop_statement_integrity_check(openscop_statement_p, int); # if defined(__cplusplus) } diff --git a/include/openscop/openscop.h b/include/openscop/util.h similarity index 82% copy from include/openscop/openscop.h copy to include/openscop/util.h index f0a06a1..a664720 100644 --- a/include/openscop/openscop.h +++ b/include/openscop/util.h @@ -2,9 +2,9 @@ /*+-----------------------------------------------------------------** ** OpenScop Library ** **-----------------------------------------------------------------** - ** scop.h ** + ** util.h ** **-----------------------------------------------------------------** - ** First version: 11/05/2010 ** + ** First version: 08/10/2010 ** **-----------------------------------------------------------------** @@ -61,15 +61,32 @@ *****************************************************************************/ -#ifndef OPENSCOP_OPENSCOP_H -# define OPENSCOP_OPENSCOP_H - +#ifndef OPENSCOP_UTIL_H +# define OPENSCOP_UTIL_H # include -# include -# include -# include -# include +# if defined(__cplusplus) +extern "C" + { +# endif + + +/*+*************************************************************************** + * Processing functions * + *****************************************************************************/ +char ** openscop_util_copy_strings(char **, int); +char * openscop_util_skip_blank_and_comments(FILE *, char *); +char ** openscop_util_read_strings(FILE *, int, int *); +int openscop_util_read_int(FILE *, char **); +void openscop_util_free_name_array(char **, int); +char ** openscop_util_generate_names(char *, int); +char * openscop_util_tag_content(char *, char *, char *); +char ** openscop_util_read_tag_arrays(char *, int *); + + +# if defined(__cplusplus) + } +# endif -#endif /* define OPENSCOP_OPENSCOP_H */ +#endif /* define OPENSCOP_UTIL_H */ diff --git a/include/openscop/vector.h b/include/openscop/vector.h index cf50e79..2bf7033 100644 --- a/include/openscop/vector.h +++ b/include/openscop/vector.h @@ -83,8 +83,8 @@ extern "C" */ struct openscop_vector { - unsigned Size; /**< The number of vector entries */ - openscop_int_t * p; /**< An array of values */ + unsigned size; /**< The number of vector entries */ + openscop_int_t * v; /**< An array of values */ }; typedef struct openscop_vector openscop_vector_t; typedef struct openscop_vector * openscop_vector_p; diff --git a/redo.sh b/redo.sh new file mode 100755 index 0000000..a36a3aa --- /dev/null +++ b/redo.sh @@ -0,0 +1,5 @@ +#!/bin/sh +make maintainer-clean +./autogen.sh +./configure --prefix=$HOME/usr +make diff --git a/source/Makefile.am b/source/Makefile.am index c970024..2dd1fb7 100644 --- a/source/Makefile.am +++ b/source/Makefile.am @@ -73,8 +73,8 @@ SUBDIRS = ############################################################################# MAINTAINERCLEANFILES = Makefile.in -INCLUDES = -I$(top_builddir) -I$(top_srcdir) \ - -I$(top_builddir)/include \ +INCLUDES = -I$(top_builddir) -I$(top_srcdir) \ + -I$(top_builddir)/include \ -I$(top_srcdir)/include ############################################################################# @@ -82,10 +82,15 @@ INCLUDES = -I$(top_builddir) -I$(top_srcdir) \ lib_LTLIBRARIES = libopenscop.la -libopenscop_la_SOURCES = \ - scop.c \ - statement.c \ - matrix.c \ - vector.c +libopenscop_la_SOURCES = \ + scop.c \ + statement.c \ + extensions/comment.c \ + extensions/arrays.c \ + extension.c \ + relation.c \ + relation_list.c \ + vector.c \ + util.c AM_CFLAGS = -Wall -fomit-frame-pointer -g diff --git a/source/extension.c b/source/extension.c new file mode 100644 index 0000000..1023b36 --- /dev/null +++ b/source/extension.c @@ -0,0 +1,380 @@ + + /*+-----------------------------------------------------------------** + ** OpenScop Library ** + **-----------------------------------------------------------------** + ** extension.c ** + **-----------------------------------------------------------------** + ** First version: 26/11/2010 ** + **-----------------------------------------------------------------** + + + ***************************************************************************** + * OpenScop: Structures and formats for polyhedral tools to talk together * + ***************************************************************************** + * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, * + * / / / // // // // / / / // // / / // / /|,_, * + * / / / // // // // / / / // // / / // / / / /\ * + * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ * + * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ * + * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ * + * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ * + * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ * + * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ * + * | I | | | | e | | | | | | | | | | | | | \ \ \ * + * | T | | | | | | | | | | | | | | | | | \ \ \ * + * | E | | | | | | | | | | | | | | | | | \ \ \ * + * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ * + * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / * + * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' * + * * + * Copyright (C) 2008 University Paris-Sud 11 and INRIA * + * * + * (3-clause BSD license) * + * Redistribution and use in source and binary forms, with or without * + * modification, are permitted provided that the following conditions * + * are met: * + * * + * 1. Redistributions of source code must retain the above copyright notice, * + * this list of conditions and the following disclaimer. * + * 2. Redistributions in binary form must reproduce the above copyright * + * notice, this list of conditions and the following disclaimer in the * + * documentation and/or other materials provided with the distribution. * + * 3. The name of the author may not be used to endorse or promote products * + * derived from this software without specific prior written permission. * + * * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * + * * + * OpenScop Library, a library to manipulate OpenScop formats and data * + * structures. Written by: * + * Cedric Bastoul and * + * Louis-Noel Pouchet * + * * + *****************************************************************************/ + +# include +# include +# include +# include + + +/*+*************************************************************************** + * Structure display function * + *****************************************************************************/ + + +/** + * openscop_extension_print_structure function: + * Displays a openscop_extension_t structure (*extensions) into a file (file, + * possibly stdout) in a way that trends to be understandable. It includes an + * indentation level (level) in order to work with others print_structure + * functions. + * \param file File where informations are printed. + * \param extensions The extensions whose information have to be printed. + * \param level Number of spaces before printing, for each line. + */ +void +openscop_extension_print_structure(FILE * file, + openscop_extension_p extension, + int level) +{ + if (extension == NULL) + return; + + switch (extension->type) { + case OPENSCOP_EXTENSION_COMMENT: { + openscop_comment_print_structure(file, extension->extension, level); + break; + } + case OPENSCOP_EXTENSION_ARRAYS: { + openscop_arrays_print_structure(file, extension->extension, level); + break; + } + default: { + fprintf(stderr, "[OpenScop] Error: unknown extension.\n"); + exit(1); + } + } +} + + +void openscop_extension_print(FILE * file, openscop_extension_p extension) +{ + +} + +void openscop_extension_print_openscop(FILE * file, + openscop_extension_p extension) +{ + +} + + +/***************************************************************************** + * Reading function * + *****************************************************************************/ + +char * openscop_extension_read_string(FILE * file) +{ + int high_water_mark = OPENSCOP_MAX_STRING; + int nb_chars = 0; + char buff[OPENSCOP_MAX_STRING], *c; + char * extensions; + + extensions = (char *)malloc(high_water_mark * sizeof(char)); + if (extensions == NULL) + { + fprintf(stderr, "[OpenScop] Error: memory overflow.\n"); + exit(1); + } + + // - Skip blank/commented lines and spaces. + c = openscop_util_skip_blank_and_comments(file, buff); + strcpy(extensions, c); + nb_chars = strlen(c); + + // - Copy everything else to the option tags field. + while (!feof(file)) + { + extensions[nb_chars] = fgetc(file); + nb_chars++; + + //printf("EXTENSIONS: %s", extensions); + if (nb_chars >= high_water_mark) + { + high_water_mark += high_water_mark; + extensions = (char *)realloc(extensions, high_water_mark * sizeof(char)); + if (extensions == NULL) + { + fprintf(stderr, "[OpenScop] Error: memory overflow.\n"); + exit(1); + } + } + } + + // - 0-terminate the string. + extensions = (char *)realloc(extensions, nb_chars * sizeof(char)); + extensions[nb_chars - 1] = '\0'; + + return extensions; +} + +/* +openscop_extension_p openscop_extension_read(FILE * file) +{ + char * extension_string; + openscop_extension_p extension = NULL; + + extension_string = openscop_extension_read_string(file); + + openscop_extension_add(&extension, extension_string, + OPENSCOP_EXTENSION_COMMENT, openscop_comment_read); + openscop_extension_add(&extension, extension_string, + OPENSCOP_EXTENSION_ARRAYS, openscop_arrays_read); + + return NULL; +} +*/ + + +/*+*************************************************************************** + * Memory allocation/deallocation function * + *****************************************************************************/ +/* +void openscop_extension(openscop_extension_p * extension, char * string, + int type, (void *)read(char *)) +{ + void * new_ext; + + new_ext = (void *) + if (*extension == NULL) + { + + } + +} +*/ + +openscop_extension_p openscop_extension_malloc() +{ + openscop_extension_p extension; + + extension = (openscop_extension_p)malloc(sizeof(openscop_extension_p)); + extension->type = OPENSCOP_EXTENSION_UNDEFINED; + extension->extension = NULL; + extension->next = NULL; + + return extension; +} + + +void openscop_extension_free(openscop_extension_p extension) +{ + + +} + + +/*+*************************************************************************** + * Processing functions * + *****************************************************************************/ + + +openscop_extension_p openscop_extension_copy(openscop_extension_p extension) +{ + + return NULL; +} + + +int openscop_extension_equal(openscop_extension_p x1, openscop_extension_p x2) +{ + + return 1; +} + + +/*+*************************************************************************** + * Extension-Dependent Functions * + *****************************************************************************/ + +/* + * For each extension called FOOEXT that a programmer wishes to add to + * OpenScop, the following functions must be provided in a dedicated + * section (follow the "Array Extension" example): + * - Display function (for internal use) + * - Print function (to OpenScop's file format as a string) + * - Read function (from OpenScop's file format as a string) + * - Malloc function (allocate the extension part in an extension structure) + * - Free function (free the extension part in an extension structure) + * - Copy function + * - Equal function + */ + + +/*+*************************************************************************** + * Array Extension * + *****************************************************************************/ + + +/* +char ** +openscop_extension_read_tag_arrays(char * str, int * nb_arrays) +{ + int i, k, nb_names, array_index, max_index = 0; + int high_water_mark = OPENSCOP_MAX_ARRAYS; + char ** arrays; + char ** tmpnames; + char * content; + char buff[OPENSCOP_MAX_STRING]; + + content = openscop_util_tag_content(str, OPENSCOP_TAG_ARRAY_START, + OPENSCOP_TAG_ARRAY_STOP); + + if (content == NULL) + { + fprintf(stderr, "[OpenScop] Info: no array optional tag.\n"); + *nb_arrays = 0; + return NULL; + } + + // Allocate the array of names. + arrays = (char **)malloc(high_water_mark * sizeof(char *)); + for (i = 0; i < high_water_mark; i++) + arrays[i] = NULL; + + // Find the number of names provided. + nb_names = openscop_util_read_int(NULL, &content); + + // Get each array name. + for (k = 0; k < nb_names; k++) + { + // Skip blank or commented lines. + while (*content == '#' || *content == '\n') + { + for (; *content != '\n'; ++content) + ; + ++content; + } + + // Get the array name index. + for (i = 0; *content && ! isspace(*content); ++i, ++content) + buff[i] = *content; + buff[i] = '\0'; + sscanf(buff, "%d", &array_index); + max_index = (max_index > array_index) ? max_index : array_index; + if (array_index > high_water_mark) + { + fprintf(stderr, "[OpenScop] Info: array name indices sound high.\n"); + high_water_mark += OPENSCOP_MAX_ARRAYS; + arrays = (char **)realloc(arrays, high_water_mark * sizeof(char *)); + if (arrays == NULL) + { + fprintf(stderr, "[OpenScop] Error: memory overflow.\n"); + exit(1); + } + for (i = high_water_mark - OPENSCOP_MAX_ARRAYS; i < high_water_mark; i++) + arrays[i] = NULL; + } + if (array_index <= 0) + { + fprintf(stderr, "[OpenScop] Error: array index must be > 0.\n"); + exit(1); + } + + // Get the array name in buff. + while (*content && isspace(*content)) + ++content; + for (i = 0; *content && ! isspace(*content); ++i, ++content) + buff[i] = *content; + buff[i] = '\0'; + + // Array index is in 0-basis. + if (arrays[array_index - 1] != NULL) + { + fprintf(stderr, "[OpenScop] Warning: two array names have the " + "same index.\n"); + free(arrays[array_index - 1]); + } + arrays[array_index - 1] = strdup(buff); + + // Go to the end of line. + while (*content && *content != '\n') + ++content; + } + + // Free unused memory. + arrays = (char **)realloc(arrays, max_index * sizeof(char *)); + + // Fill the missing names (and let's hope there is no need for higher index). + tmpnames = openscop_util_generate_names("var", max_index); + for (i = 0; i < max_index; i++) + { + if (arrays[i] == NULL || arrays[i][0] == '\0') + arrays[i] = tmpnames[i]; // Use a generated name. + else + free(tmpnames[i]); // Use a read name. + } + free(tmpnames); + + + if (OPENSCOP_DEBUG == 1) + { + printf("max_index: %d\n", max_index); + for (i = 0; i < max_index; i++) + printf("%s ", arrays[i]); + printf("\n"); + } + + *nb_arrays = max_index; + return arrays; +} +*/ diff --git a/include/openscop/vector.h b/source/extensions/arrays.c similarity index 76% copy from include/openscop/vector.h copy to source/extensions/arrays.c index cf50e79..8369915 100644 --- a/include/openscop/vector.h +++ b/source/extensions/arrays.c @@ -2,9 +2,9 @@ /*+-----------------------------------------------------------------** ** OpenScop Library ** **-----------------------------------------------------------------** - ** vector.h ** + ** extensions/arrays.c ** **-----------------------------------------------------------------** - ** First version: 01/05/2008 ** + ** First version: 07/12/2010 ** **-----------------------------------------------------------------** @@ -60,61 +60,83 @@ * * *****************************************************************************/ +# include +# include +# include +# include -#ifndef OPENSCOP_VECTOR_H -# define OPENSCOP_VECTOR_H -# include -# include +/*+*************************************************************************** + * Structure display function * + *****************************************************************************/ -# if defined(__cplusplus) -extern "C" - { -# endif +void openscop_arrays_print_structure(FILE * file, openscop_arrays_p arrays, + int level) +{ + +} -/** - * The openscop_vector_t structure stores a vector information in the PolyLib - * format (the first entry has a specific meaning). When a vector - * describes a linear constraint, a 0 means it is an equality == 0, a 1 means - * an inequality >= 0. When the vector describes an array access, a number - * different than 0 is the array identifier. - */ -struct openscop_vector + +void openscop_arrays_print(FILE * file, openscop_arrays_p arrays) { - unsigned Size; /**< The number of vector entries */ - openscop_int_t * p; /**< An array of values */ -}; -typedef struct openscop_vector openscop_vector_t; -typedef struct openscop_vector * openscop_vector_p; + openscop_arrays_print_structure(file, arrays, 0); +} -/*+*************************************************************************** - * Structure display function * +void openscop_arrays_print_openscop(FILE * file, openscop_arrays_p arrays) +{ + +} + + +/***************************************************************************** + * Reading function * *****************************************************************************/ -void openscop_vector_print_structure(FILE *, openscop_vector_p, int); -void openscop_vector_print(FILE *, openscop_vector_p); + +openscop_arrays_p openscop_arrays_read(char * extensions) +{ + + + return NULL; +} /*+*************************************************************************** * Memory allocation/deallocation function * *****************************************************************************/ -openscop_vector_p openscop_vector_malloc(unsigned); -void openscop_vector_free(openscop_vector_p); + + +openscop_arrays_p openscop_arrays_malloc() +{ + + + return NULL; +} + + +void openscop_arrays_free(openscop_arrays_p arrays) +{ + + +} /*+*************************************************************************** * Processing functions * *****************************************************************************/ -openscop_vector_p openscop_vector_add_scalar(openscop_vector_p, int); -openscop_vector_p openscop_vector_add(openscop_vector_p, openscop_vector_p); -openscop_vector_p openscop_vector_sub(openscop_vector_p, openscop_vector_p); -void openscop_vector_tag_inequality(openscop_vector_p); -void openscop_vector_tag_equality(openscop_vector_p); -int openscop_vector_equal(openscop_vector_p, openscop_vector_p); - -# if defined(__cplusplus) - } -# endif -#endif /* define OPENSCOP_VECTOR_H */ + + +openscop_arrays_p openscop_arrays_copy(openscop_arrays_p arrays) +{ + + return NULL; +} + + +int openscop_arrays_equal(openscop_arrays_p a1, openscop_arrays_p a2) +{ + + return 1; +} diff --git a/include/openscop/vector.h b/source/extensions/comment.c similarity index 76% copy from include/openscop/vector.h copy to source/extensions/comment.c index cf50e79..31480f8 100644 --- a/include/openscop/vector.h +++ b/source/extensions/comment.c @@ -2,9 +2,9 @@ /*+-----------------------------------------------------------------** ** OpenScop Library ** **-----------------------------------------------------------------** - ** vector.h ** + ** extensions/comment.c ** **-----------------------------------------------------------------** - ** First version: 01/05/2008 ** + ** First version: 07/12/2010 ** **-----------------------------------------------------------------** @@ -60,61 +60,81 @@ * * *****************************************************************************/ +# include +# include +# include +# include -#ifndef OPENSCOP_VECTOR_H -# define OPENSCOP_VECTOR_H -# include -# include +/*+*************************************************************************** + * Structure display function * + *****************************************************************************/ -# if defined(__cplusplus) -extern "C" - { -# endif +void openscop_comment_print_structure(FILE * file, openscop_comment_p comment, + int level) +{ + +} -/** - * The openscop_vector_t structure stores a vector information in the PolyLib - * format (the first entry has a specific meaning). When a vector - * describes a linear constraint, a 0 means it is an equality == 0, a 1 means - * an inequality >= 0. When the vector describes an array access, a number - * different than 0 is the array identifier. - */ -struct openscop_vector + +void openscop_comment_print(FILE * file, openscop_comment_p comment) { - unsigned Size; /**< The number of vector entries */ - openscop_int_t * p; /**< An array of values */ -}; -typedef struct openscop_vector openscop_vector_t; -typedef struct openscop_vector * openscop_vector_p; + openscop_comment_print_structure(file, comment, 0); +} -/*+*************************************************************************** - * Structure display function * +void openscop_comment_print_openscop(FILE * file, openscop_comment_p comment) +{ + +} + + +/***************************************************************************** + * Reading function * *****************************************************************************/ -void openscop_vector_print_structure(FILE *, openscop_vector_p, int); -void openscop_vector_print(FILE *, openscop_vector_p); + +openscop_comment_p openscop_comment_read(char * extensions) +{ + + return NULL; +} /*+*************************************************************************** * Memory allocation/deallocation function * *****************************************************************************/ -openscop_vector_p openscop_vector_malloc(unsigned); -void openscop_vector_free(openscop_vector_p); + + +openscop_comment_p openscop_comment_malloc() +{ + + return NULL; +} + + +void openscop_comment_free(openscop_comment_p comment) +{ + + +} /*+*************************************************************************** * Processing functions * *****************************************************************************/ -openscop_vector_p openscop_vector_add_scalar(openscop_vector_p, int); -openscop_vector_p openscop_vector_add(openscop_vector_p, openscop_vector_p); -openscop_vector_p openscop_vector_sub(openscop_vector_p, openscop_vector_p); -void openscop_vector_tag_inequality(openscop_vector_p); -void openscop_vector_tag_equality(openscop_vector_p); -int openscop_vector_equal(openscop_vector_p, openscop_vector_p); - -# if defined(__cplusplus) - } -# endif -#endif /* define OPENSCOP_VECTOR_H */ + + +openscop_comment_p openscop_comment_copy(openscop_comment_p comment) +{ + + return NULL; +} + + +int openscop_comment_equal(openscop_comment_p c1, openscop_comment_p c2) +{ + + return 1; +} diff --git a/source/matrix.c b/source/matrix.c deleted file mode 100644 index 05e7d6c..0000000 --- a/source/matrix.c +++ /dev/null @@ -1,975 +0,0 @@ - - /*+-----------------------------------------------------------------** - ** OpenScop Library ** - **-----------------------------------------------------------------** - ** matrix.c ** - **-----------------------------------------------------------------** - ** First version: 30/04/2008 ** - **-----------------------------------------------------------------** - - - ***************************************************************************** - * OpenScop: Structures and formats for polyhedral tools to talk together * - ***************************************************************************** - * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, * - * / / / // // // // / / / // // / / // / /|,_, * - * / / / // // // // / / / // // / / // / / / /\ * - * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ * - * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ * - * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ * - * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ * - * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ * - * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ * - * | I | | | | e | | | | | | | | | | | | | \ \ \ * - * | T | | | | | | | | | | | | | | | | | \ \ \ * - * | E | | | | | | | | | | | | | | | | | \ \ \ * - * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ * - * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / * - * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' * - * * - * Copyright (C) 2008 University Paris-Sud 11 and INRIA * - * * - * (3-clause BSD license) * - * Redistribution and use in source and binary forms, with or without * - * modification, are permitted provided that the following conditions * - * are met: * - * * - * 1. Redistributions of source code must retain the above copyright notice, * - * this list of conditions and the following disclaimer. * - * 2. Redistributions in binary form must reproduce the above copyright * - * notice, this list of conditions and the following disclaimer in the * - * documentation and/or other materials provided with the distribution. * - * 3. The name of the author may not be used to endorse or promote products * - * derived from this software without specific prior written permission. * - * * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * - * * - * OpenScop Library, a library to manipulate OpenScop formats and data * - * structures. Written by: * - * Cedric Bastoul and * - * Louis-Noel Pouchet * - * * - *****************************************************************************/ - - -# include -# include -# include -# include -# include - - -/*+*************************************************************************** - * Structure display function * - *****************************************************************************/ - - -/** - * openscop_matrix_print_structure function: - * Displays a openscop_matrix_t structure (*matrix) into a file (file, possibly - * stdout) in a way that trends to be understandable without falling in a deep - * depression or, for the lucky ones, getting a headache... It includes an - * indentation level (level) in order to work with others print_structure - * functions. - * \param file File where informations are printed. - * \param matrix The matrix whose information have to be printed. - * \param level Number of spaces before printing, for each line. - */ -void -openscop_matrix_print_structure(FILE * file, openscop_matrix_p matrix, - int level) -{ - int i, j; - - /* Go to the right level. */ - for (j = 0; j < level; j++) - fprintf(file,"|\t"); - - if (matrix != NULL) - { - fprintf(file,"+-- openscop_matrix_t\n"); - - for(j = 0; j <= level; j++) - fprintf(file,"|\t"); - fprintf(file,"%d %d\n",matrix->NbRows,matrix->NbColumns); - - /* Display the matrix. */ - for (i = 0; i < matrix->NbRows; i++) - { - for (j = 0; j <= level; j++) - fprintf(file,"|\t"); - - fprintf(file,"[ "); - - for (j = 0; j < matrix->NbColumns; j++) - { - SCOPINT_print(file,OPENSCOP_FMT,matrix->p[i][j]); - fprintf(file," "); - } - - fprintf(file,"]\n"); - } - } - else - fprintf(file,"+-- NULL matrix\n"); - - /* The last line. */ - for (j = 0; j <= level; j++) - fprintf(file,"|\t"); - fprintf(file,"\n"); -} - - -/** - * openscop_matrix_print function: - * This function prints the content of a openscop_matrix_t structure - * (*matrix) into a file (file, possibly stdout). - * \param file File where informations are printed. - * \param matrix The matrix whose information have to be printed. - */ -void -openscop_matrix_print(FILE * file, openscop_matrix_p matrix) -{ - openscop_matrix_print_structure(file,matrix,0); -} - - - -/** - * openscop_matrix_expression_element function: - * This function returns a string containing the printing of a value (possibly - * an iterator or a parameter with its coefficient or a constant). - * \param val The coefficient or constant value. - * \param first Pointer to a boolean set to 1 if the current value is the first - * of an expresion, 0 otherwise (this function may update it). - * \param cst A boolean set to 1 if the value is a constant, 0 otherwise. - * \param name String containing the name of the iterator or of the parameter. - */ -static -char * -openscop_matrix_expression_element(openscop_int_t val, int * first, int cst, - char * name) -{ - char * sval, * body, * temp; - - temp = (char *)malloc(OPENSCOP_MAX_STRING * sizeof(char)); - body = (char *)malloc(OPENSCOP_MAX_STRING * sizeof(char)); - sval = (char *)malloc(OPENSCOP_MAX_STRING * sizeof(char)); - body[0] = '\0'; - sval[0] = '\0'; - - /* statements for the 'normal' processing. */ - if (SCOPINT_notzero_p(val) && (!cst)) - { - if ((*first) || SCOPINT_neg_p(val)) - { - if (SCOPINT_one_p(val)) /* case 1 */ - sprintf(sval,"%s",name); - else - { - if (SCOPINT_mone_p(val)) /* case -1 */ - sprintf(sval,"-%s",name); - else /* default case */ - { - SCOPINT_sprint(sval,OPENSCOP_FMT_TXT,val); - sprintf(temp,"*%s",name); - strcat(sval,temp); - } - } - *first = 0; - } - else - { - if (SCOPINT_one_p(val)) - sprintf(sval,"+%s",name); - else - { - sprintf(sval,"+"); - SCOPINT_sprint(temp,OPENSCOP_FMT_TXT,val); - strcat(sval,temp); - sprintf(temp,"*%s",name); - strcat(sval,temp); - } - } - } - else - { - if (cst) - { - if ((SCOPINT_zero_p(val) && (*first)) || SCOPINT_neg_p(val)) - SCOPINT_sprint(sval,OPENSCOP_FMT_TXT,val); - if (SCOPINT_pos_p(val)) - { - if (!(*first)) - { - SCOPINT_sprint(sval,"+"OPENSCOP_FMT_TXT,val); /* Block macro ! */ - } - else - SCOPINT_sprint(sval,OPENSCOP_FMT_TXT,val); - } - } - } - free(temp); - free(body); - - return(sval); -} - - -/** - * openscop_matrix_expression function: - * This function returns a string corresponding to an affine expression - * stored at the "row"^th row of the matrix pointed by "matrix". - * \param matrix A set of linear expressions. - * \param row The row of the matrix corresponding to the expression. - * \param nb_iterators The number of iterators for the considered statement. - * \param iterators An array containing iterator names for the statement. - * \param nb_parameters The number of parameters in the SCoP. - * \param parameters An array containing all parameters names. - */ -static -char * -openscop_matrix_expression(openscop_matrix_p matrix, int row, - int nb_iterators, char ** iterators, - int nb_parameters, char ** parameters) -{ - int i, first = 1; - char * sline, * sval; - - sline = (char *)malloc(OPENSCOP_MAX_STRING * sizeof(char)) ; - sline[0] = '\0' ; - - /* First the iterator part. */ - for (i = 1; i <= nb_iterators; i++) - { - sval = openscop_matrix_expression_element(matrix->p[row][i],&first,0, - iterators[i-1]); - strcat(sline,sval); - free(sval); - } - - /* Next the parameter part. */ - for (i = nb_iterators + 1; i <= nb_iterators + nb_parameters; i++) - { - sval = openscop_matrix_expression_element(matrix->p[row][i],&first,0, - parameters[i - nb_iterators - 1]); - strcat(sline,sval); - free(sval); - } - - /* Finally the constant part (yes, I reused it). */ - sval = openscop_matrix_expression_element(matrix->p[row][i],&first,1,NULL); - strcat(sline,sval); - free(sval); - - return sline; -} - - -/** - * openscop_matrix_print_dot_scop function: - * This function prints the content of a openscop_matrix_t structure - * (*matrix) into a file (file, possibly stdout) for the .scop format. - * \param file File where informations are printed. - * \param matrix The matrix whose information have to be printed. - * \param type Semantic about this matrix (domain, access...). - * \param nb_iterators The number of iterators for the considered statement. - * \param iterators An array containing iterator names for the statement. - * \param nb_parameters The number of parameters in the SCoP. - * \param parameters An array containing all parameters names. - * \param nb_arrays The number of arrays accessed in the SCoP. - * \param arrays An array containing all accessed array names. - */ -void -openscop_matrix_print_dot_scop(FILE * file, openscop_matrix_p matrix, int type, - int nb_iterators, char ** iterators, - int nb_parameters, char ** parameters, - int nb_arrays, char ** arrays) -{ - int i, j, k; - char * expression; - - if (matrix == NULL) - { - fprintf(file,"0 %d\n",nb_iterators+nb_parameters+2); - return; - } - - fprintf(file,"%d %d\n",matrix->NbRows,matrix->NbColumns); - - for (i = 0; i < matrix->NbRows; i++) - { - for (j = 0; j < matrix->NbColumns; j++) - { - SCOPINT_print(file,OPENSCOP_FMT,matrix->p[i][j]); - fprintf(file," "); - } - - if (type == OPENSCOP_TYPE_DOMAIN) - { - expression = openscop_matrix_expression(matrix,i,nb_iterators,iterators, - nb_parameters,parameters); - fprintf(file," ## %s",expression); - free(expression); - if (SCOPINT_zero_p(matrix->p[i][0])) - fprintf(file," == 0"); - else - fprintf(file," >= 0"); - } - - if (type == OPENSCOP_TYPE_SCATTERING) - { - expression = openscop_matrix_expression(matrix,i,nb_iterators,iterators, - nb_parameters,parameters); - fprintf(file," ## %s",expression); - free(expression); - } - - if (type == OPENSCOP_TYPE_ACCESS) - { - if (SCOPINT_notzero_p(matrix->p[i][0])) - { - if (strncmp(arrays[SCOPINT_get_si(matrix->p[i][0]) - 1], - OPENSCOP_FAKE_ARRAY, strlen(OPENSCOP_FAKE_ARRAY))) - fprintf(file," ## %s",arrays[SCOPINT_get_si(matrix->p[i][0]) - 1]); - k = i; - do - { - expression = openscop_matrix_expression(matrix,k,nb_iterators, - iterators, - nb_parameters,parameters); - fprintf(file,"[%s]",expression); - free(expression); - k++; - } - while ((k < matrix->NbRows) && SCOPINT_zero_p(matrix->p[k][0])); - } - else - fprintf(file," ##"); - } - - fprintf(file,"\n"); - } -} - - -/***************************************************************************** - * Reading function * - *****************************************************************************/ - - -/** - * openscop_matrix_read function: - * Adaptation from the PolyLib. This function reads a matrix into a file (foo, - * posibly stdin) and returns a pointer this matrix. - */ -openscop_matrix_p -openscop_matrix_read(FILE* foo) -{ - unsigned NbRows, NbColumns; - int i, j, n; - char* c, s[OPENSCOP_MAX_STRING], str[OPENSCOP_MAX_STRING]; - openscop_matrix_p matrix; - openscop_int_t* p; - - while (fgets(s, OPENSCOP_MAX_STRING, foo) == 0) - ; - while ((*s=='#' || *s=='\n') || - (sscanf(s, " %u %u", &NbRows, &NbColumns) < 2)) - fgets(s, OPENSCOP_MAX_STRING, foo); - - matrix = openscop_matrix_malloc(NbRows, NbColumns); - - p = matrix->p_Init; - for (i = 0; i < matrix->NbRows; i++) - { - do - { - c = fgets(s, OPENSCOP_MAX_STRING, foo); - while ((c != NULL) && isspace(*c) && (*c != '\n')) - c++; - } - while (c != NULL && (*c == '#' || *c == '\n')); - - if (c == NULL) - { - fprintf(stderr, "[Scoplib] Error: not enough rows\n"); - exit(1); - } - for (j = 0; j < matrix->NbColumns; j++) - { - if (c == NULL || *c == '#' || *c == '\n') - { - fprintf(stderr, "[Scoplib] Error: not enough columns\n"); - exit(1); - } - if (sscanf(c, "%s%n", str, &n) == 0) - { - fprintf(stderr, "[Scoplib] Error: not enough rows\n"); - exit(1); - } -#if defined(OPENSCOP_INT_T_IS_MP) - long long val; - sscanf(str, "%lld", &val); - mpz_set_si(*p++, val); -#else - sscanf(str, OPENSCOP_FMT_TXT, p++); -#endif - c += n; - } - } - - return matrix; -} - - -/** - * openscop_matrix_read_arrays function: - * This function reads a matrix into a file (foo, posibly stdin) and - * returns a pointer this matrix. In addition, it reads the arrays as - * comments at the end of the line. - */ -openscop_matrix_p -openscop_matrix_read_arrays(FILE* foo, char*** arrays, int* nb_arr) -{ - unsigned NbRows, NbColumns; - int i, j, n; - int count; - char* c, s[OPENSCOP_MAX_STRING], str[OPENSCOP_MAX_STRING], - buff[OPENSCOP_MAX_STRING]; - openscop_matrix_p matrix; - openscop_int_t* p; - - while (fgets(s, OPENSCOP_MAX_STRING, foo) == 0) - ; - while ((*s=='#' || *s=='\n') || - (sscanf(s, " %u %u", &NbRows, &NbColumns) < 2)) - fgets(s, OPENSCOP_MAX_STRING, foo); - - matrix = openscop_matrix_malloc(NbRows, NbColumns); - - p = matrix->p_Init; - for (i = 0; i < matrix->NbRows; i++) - { - do - { - c = fgets(s, OPENSCOP_MAX_STRING, foo); - while ((c != NULL) && isspace(*c) && (*c != '\n')) - c++; - } - while (c != NULL && (*c == '#' || *c == '\n')); - - if (c == NULL) - { - fprintf(stderr, "[Scoplib] Error: not enough rows\n"); - exit(1); - } - - for (j = 0; j < matrix->NbColumns; j++) - { - if (c == NULL || *c == '#' || *c == '\n') - { - fprintf(stderr, "[Scoplib] Error: not enough columns\n"); - exit(1); - } - if (sscanf(c, "%s%n", str, &n) == 0) - { - fprintf(stderr, "[Scoplib] Error: not enough rows\n"); - exit(1); - } -#if defined(OPENSCOP_INT_T_IS_MP) - long long val; - sscanf(str, "%lld", &val); - mpz_set_si(*p++, val); -#else - sscanf(str, OPENSCOP_FMT_TXT, p++); -#endif - c += n; - } - /* Read the array, passed as a comment at the end of the line. */ - if (c) - { - while (c && (isspace(*c) || *c == '#')) - ++c; - for (count = 0; c && *c != '[' && *c != '\n'; ++count) - buff[count] = *(c++); - buff[count] = '\0'; - if (count && SCOPINT_get_si(matrix->p[i][0])) - { - /* Increase the buffer size if we run out of space. */ - if (SCOPINT_get_si(matrix->p[i][0]) - 1 > *nb_arr) - { - *nb_arr = SCOPINT_get_si(matrix->p[i][0]) - 1; - *arrays = (char**) realloc(*arrays, - sizeof(char*) * (*nb_arr + 1)); - } - /* Backup the array name. */ - (*arrays)[SCOPINT_get_si(matrix->p[i][0]) - 1] = strdup(buff); - } - } - } - - return matrix; -} - - -/*+**************************************************************************** - * Memory allocation/deallocation function * - ******************************************************************************/ - -/** - * openscop_matrix_malloc function: - * This function allocates the memory space for a openscop_matrix_t structure and - * sets its fields with default values. Then it returns a pointer to the - * allocated space. - * \param NbRows The number of row of the matrix to allocate. - * \param NbColumns The number of columns of the matrix to allocate. - */ -openscop_matrix_p -openscop_matrix_malloc(unsigned NbRows, unsigned NbColumns) -{ - openscop_matrix_p matrix; - openscop_int_t ** p, * q; - int i, j; - - matrix = (openscop_matrix_p)malloc(sizeof(openscop_matrix_t)); - if (matrix == NULL) - { - fprintf(stderr, "[Scoplib] Memory Overflow.\n"); - exit(1); - } - matrix->NbRows = NbRows; - matrix->NbColumns = NbColumns; - matrix->p_Init_size = NbRows * NbColumns; - if (matrix->p_Init_size == 0) - { - matrix->p = NULL; - matrix->p_Init = NULL; - } - else - { - p = (openscop_int_t **)malloc(NbRows*sizeof(openscop_int_t *)); - if (p == NULL) - { - fprintf(stderr, "[Scoplib] Memory Overflow.\n"); - exit(1); - } - q = (openscop_int_t *)malloc(NbRows * NbColumns * sizeof(openscop_int_t)); - if (q == NULL) - { - fprintf(stderr, "[Scoplib] Memory Overflow.\n"); - exit(1); - } - matrix->p = p; - matrix->p_Init = q; - for (i = 0; i < NbRows; i++) - { - *p++ = q; - for (j = 0; j < NbColumns; j++) - SCOPINT_init_set_si(*(q+j),0); - q += NbColumns; - } - } - return matrix; -} - - -/** - * openscop_matrix_free_inside function: - * This function frees the allocated memory for the inside of a - * openscop_matrix_t structure, i.e. only p and p_Init. - * \param matrix The pointer to the matrix we want to free. - */ -void -openscop_matrix_free_inside(openscop_matrix_p matrix) -{ - int i; - openscop_int_t * p; - - if (matrix == NULL) - return; - - p = matrix->p_Init; - for (i = 0; i < matrix->p_Init_size; i++) - SCOPINT_clear(*p++); - - if (matrix->p_Init != NULL) - free(matrix->p_Init); - - if (matrix->p != NULL) - free(matrix->p); -} - - -/** - * openscop_matrix_free function: - * This function frees the allocated memory for a openscop_matrix_t structure. - * \param matrix The pointer to the matrix we want to free. - */ -void -openscop_matrix_free(openscop_matrix_p matrix) -{ - if (matrix == NULL) - return; - - openscop_matrix_free_inside(matrix); - free(matrix); -} - - -/*+**************************************************************************** - * Processing functions * - ******************************************************************************/ - - -/** - * openscop_matrix_ncopy function: - * this functions builds and returns a "hard copy" (not a pointer copy) of a - * openscop_matrix_t data structure such that the copy is restricted to the "n" - * first rows of the matrix. - * \param matrix The pointer to the matrix we want to copy. - * \param n The number of row of the matrix we want to copy. - */ -openscop_matrix_p -openscop_matrix_ncopy(openscop_matrix_p matrix, int n) -{ - int i, j; - openscop_matrix_p copy; - - if (matrix == NULL) - return NULL; - - if (n > matrix->NbRows) - { - fprintf(stderr,"[Scoplib] Error: not enough rows in the matrix\n"); - exit(1); - } - - copy = openscop_matrix_malloc(n,matrix->NbColumns); - - for (i = 0; i < n; i++) - for (j = 0; j < matrix->NbColumns; j++) - SCOPINT_assign(copy->p[i][j],matrix->p[i][j]); - - return copy; -} - - -/** - * openscop_matrix_copy function: - * this function builds and returns a "hard copy" (not a pointer copy) of a - * openscop_matrix_t data structure. - * \param matrix The pointer to the matrix we want to copy. - */ -openscop_matrix_p -openscop_matrix_copy(openscop_matrix_p matrix) -{ - if (matrix == NULL) - return NULL; - - return openscop_matrix_ncopy(matrix,matrix->NbRows); -} - - -/** - * openscop_matrix_replace_vector function: - * this function replaces the "row"^th row of a matrix "matrix" with the - * vector "vector". It directly updates "matrix". - * \param matrix The matrix we want to change a row. - * \param vector The vector that will replace a row of the matrix. - * \param row The row of the matrix to be replaced. - */ -void -openscop_matrix_replace_vector(openscop_matrix_p matrix, - openscop_vector_p vector, int row) -{ - int i; - - if ((matrix == NULL) || (vector == NULL) || - (matrix->NbColumns != vector->Size) || - (row >= matrix->NbRows) || (row < 0)) - { - fprintf(stderr,"[Scoplib] Error: vector cannot replace a matrix row\n"); - exit(1); - } - - for (i = 0; i < vector->Size; i++) - SCOPINT_assign(matrix->p[row][i],vector->p[i]); -} - - -/** - * openscop_matrix_add_vector function: - * this function adds the "row"^th row of a matrix "matrix" with the - * vector "vector". It directly updates "matrix". - * \param matrix The matrix we want to change a row. - * \param vector The vector that will replace a row of the matrix. - * \param row The row of the matrix to be replaced. - */ -void -openscop_matrix_add_vector(openscop_matrix_p matrix, openscop_vector_p vector, - int row) -{ - int i; - - if ((matrix == NULL) || (vector == NULL) || - (matrix->NbColumns != vector->Size) || - (row >= matrix->NbRows) || (row < 0)) - { - fprintf(stderr,"[Scoplib] Error: vector cannot replace a matrix row\n"); - exit(1); - } - - if (SCOPINT_get_si(matrix->p[row][0]) == 0) - SCOPINT_assign(matrix->p[row][0],vector->p[0]); - for (i = 1; i < vector->Size; i++) - SCOPINT_addto(matrix->p[row][i],matrix->p[row][i],vector->p[i]); -} - - -/** - * openscop_matrix_sub_vector function: - * this function substracts the vector "vector" to the "row"^th row of - * a matrix "matrix. It directly updates "matrix". - * \param matrix The matrix we want to change a row. - * \param vector The vector that will replace a row of the matrix. - * \param row The row of the matrix to be replaced. - */ -void -openscop_matrix_sub_vector(openscop_matrix_p matrix, openscop_vector_p vector, - int row) -{ - int i; - - if ((matrix == NULL) || (vector == NULL) || - (matrix->NbColumns != vector->Size) || - (row >= matrix->NbRows) || (row < 0)) - { - fprintf(stderr,"[Scoplib] Error: vector cannot replace a matrix row\n"); - exit(1); - } - - if (SCOPINT_get_si(matrix->p[row][0]) == 0) - SCOPINT_assign(matrix->p[row][0],vector->p[0]); - for (i = 1; i < vector->Size; i++) - SCOPINT_subtract(matrix->p[row][i],matrix->p[row][i],vector->p[i]); -} - - -/** - * openscop_matrix_insert_vector function: - * this function adds a new row corresponding to the vector "vector" to - * the matrix "matrix" by inserting it at the "row"^th row. It directly - * updates "matrix". If "vector" (or "matrix") is NULL, the matrix is left - * unmodified. - * \param matrix The matrix we want to extend. - * \param vector The vector that will be added matrix. - * \param row The row where to insert the vector. - */ -void -openscop_matrix_insert_vector(openscop_matrix_p matrix, openscop_vector_p vector, - int row) -{ - int i, j; - openscop_matrix_p new; - - if ((vector == NULL) || (matrix == NULL)) - return; - - if ((matrix->NbColumns != vector->Size) || - (row > matrix->NbRows) || (row < 0)) - { - fprintf(stderr,"[Scoplib] Error: vector cannot be inserted\n"); - exit(1); - } - - /* We use a temporary matrix just to reuse existing functions. Cleaner. */ - new = openscop_matrix_malloc(matrix->NbRows+1,matrix->NbColumns); - - for (i = 0; i < row; i++) - for (j = 0; j < matrix->NbColumns; j++) - SCOPINT_assign(new->p[i][j],matrix->p[i][j]); - - openscop_matrix_replace_vector(new,vector,row); - - for (i = row+1; i < matrix->NbRows; i++) - for (j = 0; j < matrix->NbColumns; j++) - SCOPINT_assign(new->p[i][j],matrix->p[i-1][j]); - - openscop_matrix_free_inside(matrix); - - /* Replace the inside of matrix */ - matrix->NbRows = new->NbRows; - matrix->NbColumns = new->NbColumns; - matrix->p = new->p; - matrix->p_Init = new->p_Init; - /* Free the new "shell" */ - free(new); -} - - -/** - * openscop_matrix_from_vector function: - * this function converts a vector "vector" to a matrix with a single row - * and returns a pointer to that matrix. - * \param vector The vector to convert to a matrix. - */ -openscop_matrix_p -openscop_matrix_from_vector(openscop_vector_p vector) -{ - openscop_matrix_p matrix; - - if (vector == NULL) - return NULL; - - matrix = openscop_matrix_malloc(1,vector->Size); - openscop_matrix_replace_vector(matrix,vector,0); - return matrix; -} - - -/** - * openscop_matrix_replace_matrix function: - * this function replaces some rows of a matrix "m1" with the rows of - * the matrix "m2". It begins at the "row"^th row of "m1". It directly - * updates "m1". - * \param m1 The matrix we want to change some row1. - * \param m2 The matrix containing the new rows. - * \param row The first row of the matrix m1 to be replaced. - */ -void -openscop_matrix_replace_matrix(openscop_matrix_p m1, openscop_matrix_p m2, int row) -{ - int i, j; - - if ((m1 == NULL) || (m2 == NULL) || - (m1->NbColumns != m1->NbColumns) || - ((row + m2->NbRows) > m1->NbRows) || (row < 0)) - { - fprintf(stderr,"[Scoplib] Error: vector cannot replace a matrix row\n"); - exit(1); - } - - for (i = 0; i < m2->NbRows; i++) - for (j = 0; j < m2->NbColumns; j++) - SCOPINT_assign(m1->p[i+row][j],m2->p[i][j]); -} - - -/** - * openscop_matrix_insert_matrix function: - * this function adds new rows corresponding to the matrix "m1" to - * the matrix "m2" by inserting it at the "row"^th row. It directly - * updates "m1". If "m2" (or "m1") is NULL, the matrix is left - * unmodified. - * \param m1 The matrix we want to extend. - * \param m2 The matrix to be inserted. - * \param row The row where to insert the matrix - */ -void -openscop_matrix_insert_matrix(openscop_matrix_p m1, openscop_matrix_p m2, int row) -{ - int i, j; - openscop_matrix_p new; - - if ((m1 == NULL) || (m2 == NULL)) - return; - - if ((m1->NbColumns != m2->NbColumns) || - (row > m1->NbRows) || (row < 0)) - { - fprintf(stderr,"[Scoplib] Error: matrix cannot be inserted\n"); - exit(1); - } - - /* We use a temporary matrix just to reuse existing functions. Cleaner. */ - new = openscop_matrix_malloc(m1->NbRows+m2->NbRows,m1->NbColumns); - - for (i = 0; i < row; i++) - for (j = 0; j < m1->NbColumns; j++) - SCOPINT_assign(new->p[i][j],m1->p[i][j]); - - openscop_matrix_replace_matrix(new,m2,row); - - for (i = row + m2->NbRows; i < m1->NbRows; i++) - for (j = 0; j < m1->NbColumns; j++) - SCOPINT_assign(new->p[i][j],m1->p[i-m2->NbRows][j]); - - openscop_matrix_free_inside(m1); - - /* Replace the inside of matrix */ - m1->NbRows = new->NbRows; - m1->NbColumns = new->NbColumns; - m1->p = new->p; - m1->p_Init = new->p_Init; - - /* Free the new "container" */ - free(new); -} - - -/** - * openscop_matrix_concat function: - * this function builds a new matrix as the concatenation of the rows of - * two other matrices sent as parameters. - * \param m1 The first matrix. - * \param m2 The second matrix. - */ -openscop_matrix_p -openscop_matrix_concat(openscop_matrix_p m1, openscop_matrix_p m2) -{ - openscop_matrix_p new; - - if (m1 == NULL) - return openscop_matrix_copy(m2); - - if (m2 == NULL) - return openscop_matrix_copy(m1); - - if (m1->NbColumns != m2->NbColumns) - { - fprintf(stderr,"[Scoplib] Error: matrices cannot be concatenated\n"); - exit(1); - } - - new = openscop_matrix_malloc(m1->NbRows+m2->NbRows,m1->NbColumns); - openscop_matrix_replace_matrix(new,m1,0); - openscop_matrix_replace_matrix(new,m2,m1->NbRows); - - return new; -} - - -/** - * openscop_matrix_equal function: - * this function returns true if the two matrices are the same, false - * otherwise. - * \param m1 The first matrix. - * \param m2 The second matrix. - * \return 1 if m1 and m2 are the same (content-wise), 0 otherwise. - */ -int -openscop_matrix_equal(openscop_matrix_p m1, openscop_matrix_p m2) -{ - if (m1 == m2) - return 1; - if (m1 == NULL || m2 == NULL) - return 0; - if (m1->NbRows != m2->NbRows || m1->NbColumns != m2->NbColumns) - return 0; - int i, j; - for (i = 0; i < m1->NbRows; ++i) - for (j = 0; j < m1->NbColumns; ++j) - if (SCOPINT_ne(m1->p[i][j], m2->p[i][j])) - return 0; - return 1; -} diff --git a/source/relation.c b/source/relation.c new file mode 100644 index 0000000..6bf10d1 --- /dev/null +++ b/source/relation.c @@ -0,0 +1,1416 @@ + + /*+-----------------------------------------------------------------** + ** OpenScop Library ** + **-----------------------------------------------------------------** + ** relation.c ** + **-----------------------------------------------------------------** + ** First version: 30/04/2008 ** + **-----------------------------------------------------------------** + + + ***************************************************************************** + * OpenScop: Structures and formats for polyhedral tools to talk together * + ***************************************************************************** + * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, * + * / / / // // // // / / / // // / / // / /|,_, * + * / / / // // // // / / / // // / / // / / / /\ * + * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ * + * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ * + * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ * + * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ * + * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ * + * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ * + * | I | | | | e | | | | | | | | | | | | | \ \ \ * + * | T | | | | | | | | | | | | | | | | | \ \ \ * + * | E | | | | | | | | | | | | | | | | | \ \ \ * + * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ * + * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / * + * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' * + * * + * Copyright (C) 2008 University Paris-Sud 11 and INRIA * + * * + * (3-clause BSD license) * + * Redistribution and use in source and binary forms, with or without * + * modification, are permitted provided that the following conditions * + * are met: * + * * + * 1. Redistributions of source code must retain the above copyright notice, * + * this list of conditions and the following disclaimer. * + * 2. Redistributions in binary form must reproduce the above copyright * + * notice, this list of conditions and the following disclaimer in the * + * documentation and/or other materials provided with the distribution. * + * 3. The name of the author may not be used to endorse or promote products * + * derived from this software without specific prior written permission. * + * * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * + * * + * OpenScop Library, a library to manipulate OpenScop formats and data * + * structures. Written by: * + * Cedric Bastoul and * + * Louis-Noel Pouchet * + * * + *****************************************************************************/ + + +# include +# include +# include +# include +# include + + +/*+*************************************************************************** + * Structure display function * + *****************************************************************************/ + + +/** + * openscop_relation_print_structure function: + * Displays a openscop_relation_t structure (*relation) into a file (file, + * possibly stdout) in a way that trends to be understandable. It includes an + * indentation level (level) in order to work with others print_structure + * functions. + * \param file File where informations are printed. + * \param relation The relation whose information have to be printed. + * \param level Number of spaces before printing, for each line. + */ +void +openscop_relation_print_structure(FILE * file, openscop_relation_p relation, + int level) +{ + int i, j, first = 1; + + // Go to the right level. + for (j = 0; j < level; j++) + fprintf(file, "|\t"); + + if (relation != NULL) + fprintf(file,"+-- openscop_relation_t\n"); + else + fprintf(file, "+-- NULL relation\n"); + + while (relation != NULL) + { + if (! first) + { + // Go to the right level. + for (j = 0; j < level; j++) + fprintf(file, "|\t"); + fprintf(file, "| openscop_relation_t\n"); + } + else + first = 0; + + // A blank line + for(j = 0; j <= level; j++) + fprintf(file, "|\t"); + fprintf(file, "%d %d %d %d %d %d\n", + relation->nb_rows, relation->nb_columns, + relation->nb_output_dims, relation->nb_input_dims, + relation->nb_local_dims, relation->nb_parameters); + + // Display the relation. + for (i = 0; i < relation->nb_rows; i++) + { + for (j = 0; j <= level; j++) + fprintf(file, "|\t"); + + fprintf(file, "[ "); + + for (j = 0; j < relation->nb_columns; j++) + { + SCOPINT_print(file, OPENSCOP_FMT, relation->m[i][j]); + fprintf(file, " "); + } + + fprintf(file, "]\n"); + } + + relation = relation->next; + + // Next line. + if (relation != NULL) + { + for (j = 0; j <= level; j++) + fprintf(file, "|\t"); + fprintf(file, "|\n"); + for (j = 0; j <= level; j++) + fprintf(file, "|\t"); + fprintf(file, "V\n"); + } + } + + // The last line. + for (j = 0; j <= level; j++) + fprintf(file, "|\t"); + fprintf(file, "\n"); +} + + +/** + * openscop_relation_print function: + * This function prints the content of a openscop_relation_t structure + * (*relation) into a file (file, possibly stdout). + * \param file File where informations are printed. + * \param relation The relation whose information have to be printed. + */ +void +openscop_relation_print(FILE * file, openscop_relation_p relation) +{ + openscop_relation_print_structure(file, relation, 0); +} + + + +/** + * openscop_relation_expression_element function: + * This function returns a string containing the printing of a value (possibly + * an iterator or a parameter with its coefficient or a constant). + * \param val The coefficient or constant value. + * \param first Pointer to a boolean set to 1 if the current value is the first + * of an expresion, 0 otherwise (this function may update it). + * \param cst A boolean set to 1 if the value is a constant, 0 otherwise. + * \param name String containing the name of the iterator or of the parameter. + * \return A string that contains the printing of a value. + */ +static +char * +openscop_relation_expression_element(openscop_int_t val, int * first, int cst, + char * name) +{ + char * sval, * body, * temp; + + temp = (char *)malloc(OPENSCOP_MAX_STRING * sizeof(char)); + body = (char *)malloc(OPENSCOP_MAX_STRING * sizeof(char)); + sval = (char *)malloc(OPENSCOP_MAX_STRING * sizeof(char)); + body[0] = '\0'; + sval[0] = '\0'; + + // statements for the 'normal' processing. + if (SCOPINT_notzero_p(val) && (!cst)) + { + if ((*first) || SCOPINT_neg_p(val)) + { + if (SCOPINT_one_p(val)) // case 1 + sprintf(sval, "%s", name); + else + { + if (SCOPINT_mone_p(val)) // case -1 + sprintf(sval, "-%s", name); + else // default case + { + SCOPINT_sprint(sval, OPENSCOP_FMT_TXT, val); + sprintf(temp, "*%s", name); + strcat(sval, temp); + } + } + *first = 0; + } + else + { + if (SCOPINT_one_p(val)) + sprintf(sval, "+%s", name); + else + { + sprintf(sval, "+"); + SCOPINT_sprint(temp, OPENSCOP_FMT_TXT, val); + strcat(sval, temp); + sprintf(temp, "*%s", name); + strcat(sval, temp); + } + } + } + else + { + if (cst) + { + if ((SCOPINT_zero_p(val) && (*first)) || SCOPINT_neg_p(val)) + SCOPINT_sprint(sval, OPENSCOP_FMT_TXT, val); + if (SCOPINT_pos_p(val)) + { + if (!(*first)) + { + SCOPINT_sprint(sval, "+"OPENSCOP_FMT_TXT, val); // Block macro ! + } + else + SCOPINT_sprint(sval, OPENSCOP_FMT_TXT, val); + } + } + } + free(temp); + free(body); + + return(sval); +} + + +/** + * openscop_relation_expression function: + * This function returns a string corresponding to an affine expression + * stored at the "row"^th row of the relation pointed by "relation". + * \param relation A set of linear expressions. + * \param row The row corresponding to the expression. + * \param nb_iterators The number of iterators for the considered statement. + * \param iterators An array containing iterator names for the statement. + * \param nb_parameters The number of parameters in the SCoP. + * \param parameters An array containing all parameters names. + * \return A string that contains the printing of an affine expression. + */ +static +char * +openscop_relation_expression(openscop_relation_p relation, int row, + int nb_iterators, char ** iterators, + int nb_parameters, char ** parameters) +{ + int i, first = 1; + char * sline, * sval; + + sline = (char *)malloc(OPENSCOP_MAX_STRING * sizeof(char)) ; + sline[0] = '\0' ; + + // First the iterator part. + for (i = 1; i <= nb_iterators; i++) + { + sval = openscop_relation_expression_element(relation->m[row][i], + &first, 0, iterators[i-1]); + strcat(sline, sval); + free(sval); + } + + // Next the parameter part. + for (i = nb_iterators + 1; i <= nb_iterators + nb_parameters; i++) + { + sval = openscop_relation_expression_element(relation->m[row][i], &first, 0, + parameters[i - nb_iterators - 1]); + strcat(sline, sval); + free(sval); + } + + // Finally the constant part (yes, I reused it). + sval = openscop_relation_expression_element(relation->m[row][i], + &first, 1, NULL); + strcat(sline, sval); + free(sval); + + return sline; +} + + +/** + * openscop_relation_get_array_id internal function: + * This function returns the array identifier when the relation provided + * as parameter corresponds to an access function. + * \param relation The access function. + * \return The accessed array identifier. + */ +static +int +openscop_relation_get_array_id(openscop_relation_p relation) +{ + if (relation == NULL) + { + fprintf(stderr, "[OpenScop] Error: cannot find nb_arrays " + "in a NULL relation.\n"); + exit(1); + } + + if (relation->nb_local_dims == OPENSCOP_UNDEFINED) + { + // Matrix representation case. + if ((relation->nb_rows < 1) || (relation->nb_columns < 1)) + { + fprintf(stderr, "[OpenScop] Error: not enough rows or columns " + "to extract nb_arrays.\n"); + exit(1); + } + return SCOPINT_get_si(relation->m[0][0]); + } + else + { + // Relation representation case. + if ((relation->nb_rows < 1) || (relation->nb_columns < 2)) + { + fprintf(stderr, "[OpenScop] Error: not enough rows or columns " + "to extract nb_arrays.\n"); + exit(1); + } + // TODO: do something more general + return SCOPINT_get_si(relation->m[0][1]); + } +} + + +/** + * openscop_relation_print_openscop function: + * This function prints the content of a openscop_relation_t structure + * (*relation) into a file (file, possibly stdout) in the OpenScop format. + * \param file File where informations are printed. + * \param relation The relation whose information have to be printed. + * \param type Semantics about this relation (domain, access...). + * \param nb_iterators The number of iterators for the considered statement. + * \param iterators An array containing iterator names for the statement. + * \param nb_parameters The number of parameters in the SCoP. + * \param parameters An array containing all parameters names. + * \param nb_arrays The number of arrays accessed in the SCoP. + * \param arrays An array containing all accessed array names. + */ +void +openscop_relation_print_openscop(FILE * file, openscop_relation_p relation, + int type, + int nb_iterators, char ** iterators, + int nb_parameters, char ** parameters, + int nb_arrays, char ** arrays) +{ + int i, j, k; + int generated_iterator_names = 0; + int generated_parameter_names = 0; + int generated_array_names = 0; + int part, nb_parts; + int array_id; + char * expression; + openscop_relation_p r; + + if (relation == NULL) + { + fprintf(stderr, "[OpenScop] Warning: asked to print a NULL relation.\n"); + fprintf(file, "# NULL relation\n"); + return; + } + + // Generate names for comments if necessary. + if (((type == OPENSCOP_TYPE_DOMAIN) && + (relation->nb_output_dims > nb_iterators)) || + (((type == OPENSCOP_TYPE_SCATTERING) || + (type == OPENSCOP_TYPE_ACCESS)) && + (relation->nb_input_dims > nb_iterators))) + { + generated_iterator_names = 1; + if (type == OPENSCOP_TYPE_DOMAIN) + nb_iterators = relation->nb_output_dims; + else + nb_iterators = relation->nb_input_dims; + + iterators = openscop_util_generate_names("i_", nb_iterators); + } + + if (relation->nb_parameters > nb_parameters) + { + generated_parameter_names = 1; + nb_parameters = relation->nb_parameters; + parameters = openscop_util_generate_names("P_", nb_parameters); + } + + if ((type == OPENSCOP_TYPE_ACCESS) && + ((array_id = openscop_relation_get_array_id(relation)) > nb_arrays)) + { + generated_array_names = 1; + arrays = openscop_util_generate_names("A_", array_id); + } + + // Count the number of parts in the union and print it if it is not 1. + r = relation; + nb_parts = 0; + while (r != NULL) + { + nb_parts++; + r = r->next; + } + if (nb_parts > 1) + fprintf(file, "# Union with %d parts\n%d\n", nb_parts, nb_parts); + + // Print each part of the union. + for (part = 1; part <= nb_parts; part++) + { + if (nb_parts > 1) + fprintf(file, "# Union part No.%d\n", part); + if ((relation->nb_output_dims == OPENSCOP_UNDEFINED) && + (relation->nb_input_dims == OPENSCOP_UNDEFINED) && + (relation->nb_local_dims == OPENSCOP_UNDEFINED) && + (relation->nb_parameters == OPENSCOP_UNDEFINED)) + fprintf(file, "%d %d\n", relation->nb_rows, relation->nb_columns); + else + fprintf(file, "%d %d %d %d %d %d\n", + relation->nb_rows, relation->nb_columns, + relation->nb_output_dims, relation->nb_input_dims, + relation->nb_local_dims, relation->nb_parameters); + + for (i = 0; i < relation->nb_rows; i++) + { + for (j = 0; j < relation->nb_columns; j++) + { + SCOPINT_print(file, OPENSCOP_FMT, relation->m[i][j]); + fprintf(file, " "); + } + + if (type == OPENSCOP_TYPE_DOMAIN) + { + expression = openscop_relation_expression(relation, i, + nb_iterators, iterators, + nb_parameters, parameters); + fprintf(file, " ## %s", expression); + free(expression); + if (SCOPINT_zero_p(relation->m[i][0])) + fprintf(file, " == 0"); + else + fprintf(file, " >= 0"); + } + + if (type == OPENSCOP_TYPE_SCATTERING) + { + expression = openscop_relation_expression(relation, i, + nb_iterators, iterators, + nb_parameters, parameters); + fprintf(file, " ## %s", expression); + free(expression); + } + + if (type == OPENSCOP_TYPE_ACCESS) + { + if (SCOPINT_notzero_p(relation->m[i][0])) + { + if (strncmp(arrays[SCOPINT_get_si(relation->m[i][0]) - 1], + OPENSCOP_FAKE_ARRAY, strlen(OPENSCOP_FAKE_ARRAY))) + fprintf(file, " ## %s", + arrays[SCOPINT_get_si(relation->m[i][0]) - 1]); + k = i; + do + { + expression = openscop_relation_expression(relation, k, + nb_iterators, iterators, + nb_parameters, parameters); + fprintf(file, "[%s]", expression); + free(expression); + k++; + } + while ((k < relation->nb_rows) && + SCOPINT_zero_p(relation->m[k][0])) + ; + } + else + fprintf(file, " ##"); + } + + fprintf(file, "\n"); + } + relation = relation->next; + } + + if (generated_iterator_names) + openscop_util_free_name_array(iterators, nb_iterators); + if (generated_parameter_names) + openscop_util_free_name_array(parameters, nb_parameters); + if (generated_array_names) + openscop_util_free_name_array(arrays, nb_arrays); +} + + +/***************************************************************************** + * Reading function * + *****************************************************************************/ + + +/** + * openscop_relation_read function: + * This function reads a relation into a file (foo, posibly stdin) and + * returns a pointer this relation. In addition, it reads the arrays as + * comments at the end of the line. + * \param file The input stream. + * \return A pointer to the relation structure that has been read. + */ +openscop_relation_p +openscop_relation_read(FILE * foo) +{ + int i, j, k, n, read = 0; + int nb_rows, nb_columns; + int nb_output_dims, nb_input_dims, nb_local_dims, nb_parameters; + int nb_union_parts = 1; + int may_read_nb_union_parts = 1; + int read_properties = 1; + int first = 1; + char * c, s[OPENSCOP_MAX_STRING], str[OPENSCOP_MAX_STRING]; + openscop_relation_p relation, relation_union = NULL, previous = NULL; + openscop_int_t * p = NULL; + + // Read each part of the union (the number of parts may be updated inside) + for (k = 0; k < nb_union_parts; k++) + { + // Read the number of union parts or the properties of the union part + while (read_properties) + { + read_properties = 0; + + // Read relation properties. + c = openscop_util_skip_blank_and_comments(foo, s); + read = sscanf(c, " %d %d %d %d %d %d", &nb_rows, &nb_columns, + &nb_output_dims, &nb_input_dims, + &nb_local_dims, &nb_parameters); + + if (((read != 1) && (read != 2) && (read != 6)) || + ((read == 1) && (may_read_nb_union_parts != 1))) + { + fprintf(stderr, "[OpenScop] Error:: badly formated relation.\n"); + exit(1); + } + if (read == 1) + { + // Only one number means a union and is the number of parts. + nb_union_parts = nb_rows; + if (nb_union_parts < 1) + { + fprintf(stderr, "[OpenScop] Error: negative nb of union parts.\n"); + exit(1); + } + // Allow to read the properties of the first part of the union. + read_properties = 1; + } + if (read == 2) + { + nb_output_dims = OPENSCOP_UNDEFINED; + nb_input_dims = OPENSCOP_UNDEFINED; + nb_local_dims = OPENSCOP_UNDEFINED; + nb_parameters = OPENSCOP_UNDEFINED; + } + + may_read_nb_union_parts = 0; + } + + // Allocate the union part and fill its properties. + relation = openscop_relation_malloc(nb_rows, nb_columns); + relation->nb_output_dims = nb_output_dims; + relation->nb_input_dims = nb_input_dims; + relation->nb_local_dims = nb_local_dims; + relation->nb_parameters = nb_parameters; + + // Read the matrix of constraints. + if ((relation->nb_rows != 0) && (relation->nb_columns != 0)) + p = relation->m[0]; + + for (i = 0; i < relation->nb_rows; i++) + { + c = openscop_util_skip_blank_and_comments(foo, s); + if (c == NULL) + { + fprintf(stderr, "[OpenScop] Error: not enough rows.\n"); + exit(1); + } + + for (j = 0; j < relation->nb_columns; j++) + { + if (c == NULL || *c == '#' || *c == '\n') + { + fprintf(stderr, "[OpenScop] Error: not enough columns.\n"); + exit(1); + } + if (sscanf(c, "%s%n", str, &n) == 0) + { + fprintf(stderr, "[OpenScop] Error: not enough rows.\n"); + exit(1); + } +#if defined(OPENSCOP_INT_T_IS_MP) + long long val; + sscanf(str, "%lld", &val); + mpz_set_si(*p++, val); +#else + sscanf(str, OPENSCOP_FMT_TXT, p++); +#endif + c += n; + } + } + + // Build the linked list of union parts. + if (first == 1) + { + relation_union = relation; + first = 0; + } + else + previous->next = relation; + + previous = relation; + read_properties = 1; + } + + return relation_union; +} + + +/*+*************************************************************************** + * Memory allocation/deallocation function * + *****************************************************************************/ + +/** + * openscop_relation_malloc function: + * This function allocates the memory space for a openscop_relation_t + * structure and sets its fields with default values. Then it returns a + * pointer to the allocated space. + * \param nb_rows The number of row of the relation to allocate. + * \param nb_columns The number of columns of the relation to allocate. + * \return A pointer to an empty relation with fields set to default values + * and a ready-to-use constraint matrix. + */ +openscop_relation_p +openscop_relation_malloc(int nb_rows, int nb_columns) +{ + openscop_relation_p relation; + openscop_int_t ** p, * q; + int i, j; + + relation = (openscop_relation_p)malloc(sizeof(openscop_relation_t)); + if (relation == NULL) + { + fprintf(stderr, "[OpenScop] Memory Overflow.\n"); + exit(1); + } + + relation->nb_rows = nb_rows; + relation->nb_columns = nb_columns; + relation->nb_output_dims = OPENSCOP_UNDEFINED; + relation->nb_input_dims = OPENSCOP_UNDEFINED; + relation->nb_parameters = OPENSCOP_UNDEFINED; + relation->nb_local_dims = OPENSCOP_UNDEFINED; + + if ((nb_rows == 0) || (nb_columns == 0) || + (nb_rows == OPENSCOP_UNDEFINED) || (nb_columns == OPENSCOP_UNDEFINED)) + relation->m = NULL; + else + { + p = (openscop_int_t **)malloc(nb_rows * sizeof(openscop_int_t *)); + if (p == NULL) + { + fprintf(stderr, "[OpenScop] Memory Overflow.\n"); + exit(1); + } + q = (openscop_int_t *)malloc(nb_rows*nb_columns*sizeof(openscop_int_t)); + if (q == NULL) + { + fprintf(stderr, "[OpenScop] Memory Overflow.\n"); + exit(1); + } + relation->m = p; + for (i = 0; i < nb_rows; i++) + { + *p++ = q; + for (j = 0; j < nb_columns; j++) + SCOPINT_init_set_si(*(q+j),0); + q += nb_columns; + } + } + + relation->next = NULL; + + return relation; +} + + +/** + * openscop_relation_free_inside function: + * This function frees the allocated memory for the inside of a + * openscop_relation_t structure, i.e. only m. + * \param relation The pointer to the relation we want to free. + */ +void +openscop_relation_free_inside(openscop_relation_p relation) +{ + int i, nb_elements; + openscop_int_t * p; + + if (relation == NULL) + return; + + nb_elements = relation->nb_rows * relation->nb_columns; + + if (nb_elements > 0) + p = relation->m[0]; + + for (i = 0; i < nb_elements; i++) + SCOPINT_clear(*p++); + + if (relation->m != NULL) + { + if (nb_elements > 0) + free(relation->m[0]); + free(relation->m); + } +} + + +/** + * openscop_relation_free function: + * This function frees the allocated memory for a openscop_relation_t + * structure. + * \param relation The pointer to the relation we want to free. + */ +void +openscop_relation_free(openscop_relation_p relation) +{ + openscop_relation_p tmp; + + if (relation == NULL) + return; + + while (relation != NULL) + { + tmp = relation->next; + openscop_relation_free_inside(relation); + free(relation); + relation = tmp; + } +} + + +/*+*************************************************************************** + * Processing functions * + *****************************************************************************/ + + +/** + * openscop_relation_is_matrix function: + * This function returns 1 if the relation provided as parameter corresponds + * to a "matrix" representation (see documentation), -1 if it is NULL and + * 0 in all other cases. + * \param relation The relation we want to know whether it is a matrix or not. + * \return 1 if the relation has "matrix" representation, -1 if it is NULL, + * 0 in all other cases. + */ +int +openscop_relation_is_matrix(openscop_relation_p relation) +{ + if (relation == NULL) + return -1; + + // A relation has matrix representation if all nb_local_dims fields + // of all parts of the union is OPENSCOP_UNDEFINED. + while (relation != NULL) + { + if (relation->nb_local_dims != OPENSCOP_UNDEFINED) + return 0; + + relation = relation->next; + } + + return 1; +} + + +/** + * openscop_relation_ncopy function: + * This functions builds and returns a "hard copy" (not a pointer copy) of a + * openscop_relation_t data structure such that the copy is restricted to the + * "n" first rows of the relation. This applies to all the parts in the case + * of a relation union. + * \param relation The pointer to the relation we want to copy. + * \param n The number of row of the relation we want to copy (the + * special value -1 means "all the rows"). + * \return A pointer to the full copy of the relation union restricted to the + * first n rows of constraint matrix for each part of the union. + */ +openscop_relation_p +openscop_relation_ncopy(openscop_relation_p relation, int n) +{ + int i, j; + int first = 1, all_rows = 0; + openscop_relation_p copy = NULL, node, previous = NULL; + + if (n == -1) + all_rows = 1; + + while (relation != NULL) + { + if (all_rows) + n = relation->nb_rows; + + if (n > relation->nb_rows) + { + fprintf(stderr,"[OpenScop] Error: not enough rows in the relation\n"); + exit(1); + } + + node = openscop_relation_malloc(n, relation->nb_columns); + + for (i = 0; i < n; i++) + for (j = 0; j < relation->nb_columns; j++) + SCOPINT_assign(node->m[i][j], relation->m[i][j]); + + if (first) + { + first = 0; + copy = node; + previous = node; + } + else + { + previous->next = node; + previous = previous->next; + } + + relation = relation->next; + } + + return copy; +} + + +/** + * openscop_relation_copy function: + * this function builds and returns a "hard copy" (not a pointer copy) of a + * openscop_relation_t data structure (the full union of relation). + * \param relation The pointer to the relation we want to copy. + * \return A pointer to the copy of the union of relations. + */ +openscop_relation_p +openscop_relation_copy(openscop_relation_p relation) +{ + if (relation == NULL) + return NULL; + + return openscop_relation_ncopy(relation, relation->nb_rows); +} + + +/** + * openscop_relation_replace_vector function: + * this function replaces the "row"^th row of a relation "relation" with the + * vector "vector". It directly updates the relation union part pointed + * by "relation" and this part only. + * \param relation The relation we want to change a row. + * \param vector The vector that will replace a row of the relation. + * \param row The row of the relation to be replaced. + */ +void +openscop_relation_replace_vector(openscop_relation_p relation, + openscop_vector_p vector, int row) +{ + int i; + + if ((relation == NULL) || (vector == NULL) || + (relation->nb_columns != vector->size) || + (row >= relation->nb_rows) || (row < 0)) + { + fprintf(stderr,"[OpenScop] Error: vector cannot replace relation row.\n"); + exit(1); + } + + for (i = 0; i < vector->size; i++) + SCOPINT_assign(relation->m[row][i], vector->v[i]); +} + + +/** + * openscop_relation_add_vector function: + * this function adds the "row"^th row of a relation "relation" with the + * vector "vector". It directly updates the relation union part pointed + * by "relation" and this part only. + * \param relation The relation we want to change a row. + * \param vector The vector that will replace a row of the relation. + * \param row The row of the relation to be replaced. + */ +void +openscop_relation_add_vector(openscop_relation_p relation, + openscop_vector_p vector, + int row) +{ + int i; + + if ((relation == NULL) || (vector == NULL) || + (relation->nb_columns != vector->size) || + (row >= relation->nb_rows) || (row < 0)) + { + fprintf(stderr,"[OpenScop] Error: vector cannot be added to relation.\n"); + exit(1); + } + + if (SCOPINT_get_si(relation->m[row][0]) == 0) + SCOPINT_assign(relation->m[row][0], vector->v[0]); + for (i = 1; i < vector->size; i++) + SCOPINT_addto(relation->m[row][i], relation->m[row][i], vector->v[i]); +} + + +/** + * openscop_relation_sub_vector function: + * this function substracts the vector "vector" to the "row"^th row of + * a relation "relation. It directly updates the relation union part pointed + * by "relation" and this part only. + * \param relation The relation we want to change a row. + * \param vector The vector that will be subtracted to a row of the relation. + * \param row The row of the relation to subtract the vector. + */ +void +openscop_relation_sub_vector(openscop_relation_p relation, + openscop_vector_p vector, + int row) +{ + int i; + + if ((relation == NULL) || (vector == NULL) || + (relation->nb_columns != vector->size) || + (row >= relation->nb_rows) || (row < 0)) + { + fprintf(stderr,"[OpenScop] Error: vector cannot be subtracted to row.\n"); + exit(1); + } + + if (SCOPINT_get_si(relation->m[row][0]) == 0) + SCOPINT_assign(relation->m[row][0], vector->v[0]); + for (i = 1; i < vector->size; i++) + SCOPINT_subtract(relation->m[row][i], relation->m[row][i], vector->v[i]); +} + + +/** + * openscop_relation_insert_vector function: + * this function adds a new row corresponding to the vector "vector" to + * the relation "relation" by inserting it at the "row"^th row. It directly + * updates the relation union part pointed by "relation" and this part only. + * If "vector" (or "relation") is NULL, the relation is left unmodified. + * \param relation The relation we want to extend. + * \param vector The vector that will be added relation. + * \param row The row where to insert the vector. + */ +void +openscop_relation_insert_vector(openscop_relation_p relation, + openscop_vector_p vector, + int row) +{ + int i, j; + openscop_relation_p new; + + if ((vector == NULL) || (relation == NULL)) + return; + + if ((relation->nb_columns != vector->size) || + (row > relation->nb_rows) || (row < 0)) + { + fprintf(stderr,"[OpenScop] Error: vector cannot be inserted.\n"); + exit(1); + } + + // We use a temporary relation just to reuse existing functions. Cleaner. + new = openscop_relation_malloc(relation->nb_rows+1, relation->nb_columns); + + for (i = 0; i < row; i++) + for (j = 0; j < relation->nb_columns; j++) + SCOPINT_assign(new->m[i][j], relation->m[i][j]); + + openscop_relation_replace_vector(new,vector, row); + + for (i = row+1; i < relation->nb_rows; i++) + for (j = 0; j < relation->nb_columns; j++) + SCOPINT_assign(new->m[i][j], relation->m[i-1][j]); + + openscop_relation_free_inside(relation); + + // Replace the inside of relation. + relation->nb_rows = new->nb_rows; + relation->nb_columns = new->nb_columns; + relation->m = new->m; + // Free the new "shell". + free(new); +} + + +/** + * openscop_relation_from_vector function: + * this function converts a vector "vector" to a relation with a single row + * and returns a pointer to that relation. + * \param vector The vector to convert to a relation. + * \return A pointer to a relation resulting from the conversion of the vector. + */ +openscop_relation_p +openscop_relation_from_vector(openscop_vector_p vector) +{ + openscop_relation_p relation; + + if (vector == NULL) + return NULL; + + relation = openscop_relation_malloc(1, vector->size); + openscop_relation_replace_vector(relation, vector, 0); + return relation; +} + + +/** + * openscop_relation_replace_relation function: + * this function replaces some rows of a relation "r1" with the rows of + * the relation "r2". It begins at the "row"^th row of "r1". It directly + * updates the relation union part pointed by "r1" and this part only. + * \param r1 The relation we want to change some rows. + * \param r2 The relation containing the new rows. + * \param row The first row of the relation r1 to be replaced. + */ +void +openscop_relation_replace_relation(openscop_relation_p r1, + openscop_relation_p r2, int row) +{ + int i, j; + + if ((r1 == NULL) || (r2 == NULL) || + (r1->nb_columns != r1->nb_columns) || + ((row + r2->nb_rows) > r1->nb_rows) || (row < 0)) + { + fprintf(stderr,"[OpenScop] Error: relation rows could not be replaced.\n"); + exit(1); + } + + for (i = 0; i < r2->nb_rows; i++) + for (j = 0; j < r2->nb_columns; j++) + SCOPINT_assign(r1->m[i+row][j], r2->m[i][j]); +} + + +/** + * openscop_relation_insert_relation function: + * this function adds new rows corresponding to the relation "r1" to + * the relation "r2" by inserting it at the "row"^th row. It directly + * updates the relation union part pointed by "r1" and this part only. + * If "r2" (or "r1") is NULL, the relation is left unmodified. + * \param r1 The relation we want to extend. + * \param r2 The relation to be inserted. + * \param row The row where to insert the relation + */ +void +openscop_relation_insert_relation(openscop_relation_p r1, + openscop_relation_p r2, int row) +{ + int i, j; + openscop_relation_p new; + + if ((r1 == NULL) || (r2 == NULL)) + return; + + if ((r1->nb_columns != r2->nb_columns) || + (row > r1->nb_rows) || (row < 0)) + { + fprintf(stderr,"[OpenScop] Error: relation cannot be inserted.\n"); + exit(1); + } + + // We use a temporary relation just to reuse existing functions. Cleaner. + new = openscop_relation_malloc(r1->nb_rows+r2->nb_rows, r1->nb_columns); + + for (i = 0; i < row; i++) + for (j = 0; j < r1->nb_columns; j++) + SCOPINT_assign(new->m[i][j], r1->m[i][j]); + + openscop_relation_replace_relation(new, r2, row); + + for (i = row + r2->nb_rows; i < r1->nb_rows; i++) + for (j = 0; j < r1->nb_columns; j++) + SCOPINT_assign(new->m[i][j], r1->m[i-r2->nb_rows][j]); + + openscop_relation_free_inside(r1); + + // Replace the inside of relation. + r1->nb_rows = new->nb_rows; + r1->nb_columns = new->nb_columns; + r1->m = new->m; + + // Free the new "container". + free(new); +} + + +/** + * openscop_relation_concat function: + * this function builds a new relation as the concatenation of the rows of + * two other matrices sent as parameters. + * \param r1 The first relation. + * \param r2 The second relation. + * \return A pointer to the relation resulting from the concatenation of + * r1 and r2. + */ +openscop_relation_p +openscop_relation_concat(openscop_relation_p r1, openscop_relation_p r2) +{ + openscop_relation_p new; + + if (r1 == NULL) + return openscop_relation_copy(r2); + + if (r2 == NULL) + return openscop_relation_copy(r1); + + if (r1->nb_columns != r2->nb_columns) + { + fprintf(stderr,"[OpenScop] Error: matrices cannot be concatenated\n"); + exit(1); + } + + new = openscop_relation_malloc(r1->nb_rows+r2->nb_rows, r1->nb_columns); + openscop_relation_replace_relation(new, r1, 0); + openscop_relation_replace_relation(new, r2, r1->nb_rows); + + return new; +} + + +/** + * openscop_relation_equal function: + * this function returns true if the two matrices are the same, false + * otherwise. + * \param r1 The first relation. + * \param r2 The second relation. + * \return 1 if r1 and r2 are the same (content-wise), 0 otherwise. + */ +int +openscop_relation_equal(openscop_relation_p r1, openscop_relation_p r2) +{ + int i, j; + + while ((r1 != NULL) && (r2 != NULL)) + { + if (r1 == r2) + return 1; + + if ((r1->nb_rows != r2->nb_rows) || (r1->nb_columns != r2->nb_columns)) + return 0; + + for (i = 0; i < r1->nb_rows; ++i) + for (j = 0; j < r1->nb_columns; ++j) + if (SCOPINT_ne(r1->m[i][j], r2->m[i][j])) + return 0; + + r1 = r1->next; + r2 = r2->next; + } + + if (((r1 == NULL) && (r2 != NULL)) || ((r1 != NULL) && (r2 == NULL))) + return 0; + + return 1; +} + + +/** + * openscop_relation_check_property internal function: + * This function checks whether an "actual" value is the same as an + * "expected" value or not. If the expected value is set to + * OPENSCOP_UNDEFINED, this function sets it to the "actual" value + * and do not report a difference has been detected. + * It returns 0 if a difference has been detected, 1 otherwise. + * \param expected Pointer to the expected value (the value is modified if + * it was set to OPENSCOP_UNDEFINED). + * \param actual Value we want to check. + * \return 0 if the values are not the same while the expected value was + * not OPENSCOP_UNDEFINED, 1 otherwise. + */ +static +int +openscop_relation_check_property(int * expected, int actual) +{ + if (*expected != OPENSCOP_UNDEFINED) + { if ((actual != OPENSCOP_UNDEFINED) && + (actual != *expected)) + { + fprintf(stderr, "[OpenScop] Warning: unexpected property.\n"); + return 0; + } + } + else + *expected = actual; + + return 1; +} + + +/** + * openscop_relation_check_nb_columns internal function: + * This function checks that the number of columns of a relation is + * corresponds to some expected properties (setting an expected property to + * OPENSCOP_UNDEFINED makes this function unable to detect a problem). + * It returns 0 if the number of columns seems incorrect or 1 if no problem + * has been detected. + * \param relation The relation we want to check the number of column. + * \param expected_nb_output_dims Expected number of output dimensions. + * \param expected_nb_input_dims Expected number of input dimensions. + * \param expected_nb_parameters Expected number of parameters. + * \return 0 if the number of columns seems incorrect, 1 otherwise. + */ +static +int +openscop_relation_check_nb_columns(openscop_relation_p relation, + int expected_nb_output_dims, + int expected_nb_input_dims, + int expected_nb_parameters) +{ + int expected_nb_local_dims, expected_nb_columns; + + if ((expected_nb_output_dims != OPENSCOP_UNDEFINED) && + (expected_nb_input_dims != OPENSCOP_UNDEFINED) && + (expected_nb_parameters != OPENSCOP_UNDEFINED)) + { + if (relation->nb_local_dims == OPENSCOP_UNDEFINED) + expected_nb_local_dims = 0; + else + expected_nb_local_dims = relation->nb_local_dims; + + expected_nb_columns = expected_nb_output_dims + + expected_nb_input_dims + + expected_nb_local_dims + + expected_nb_parameters + + 2; + + if (expected_nb_columns != relation->nb_columns) + { + fprintf(stderr, "[OpenScop] Warning: unexpected number of columns.\n"); + return 0; + } + } + + return 1; +} + + +/** + * openscop_relation_integrity_check function: + * This function checks that a relation is "well formed" according to some + * expected properties (setting an expected value to OPENSCOP_UNDEFINED means + * that we do not expect a specific value) and what the relation is supposed + * to represent. It returns 0 if the check failed or 1 if no problem has been + * detected. + * \param relation The relation we want to check. + * \param type Semantics about this relation (domain, access...). + * \param expected_nb_output_dims Expected number of output dimensions. + * \param expected_nb_input_dims Expected number of input dimensions. + * \param expected_nb_parameters Expected number of parameters. + * \return 0 if the integrity check fails, 1 otherwise. + */ +int +openscop_relation_integrity_check(openscop_relation_p relation, + int type, + int expected_nb_output_dims, + int expected_nb_input_dims, + int expected_nb_parameters) +{ + int i, start; + + // Check the NULL case. + if (relation == NULL) + { + if ((expected_nb_output_dims != OPENSCOP_UNDEFINED) && + (expected_nb_input_dims != OPENSCOP_UNDEFINED) && + (expected_nb_parameters != OPENSCOP_UNDEFINED)) + { + fprintf(stderr, "[OpenScop] Warning: NULL relation with " + "some expected properties.\n"); + return 0; + } + else + { + fprintf(stderr, "[OpenScop] Warning: NULL relation.\n"); + return 1; + } + } + + // Check properties according to expected values (and if expected values + // are undefined, define them with the first relation part properties). + if (!openscop_relation_check_property(&expected_nb_output_dims, + relation->nb_output_dims) || + !openscop_relation_check_property(&expected_nb_input_dims, + relation->nb_input_dims) || + !openscop_relation_check_property(&expected_nb_parameters, + relation->nb_parameters)) + return 0; + + // Check that a domain has actually 0 input dimensions. + if (((type == OPENSCOP_TYPE_DOMAIN) || + (type == OPENSCOP_TYPE_CONTEXT)) && + ((relation->nb_input_dims != 0) && + (relation->nb_input_dims != OPENSCOP_UNDEFINED))) + { + fprintf(stderr, "[OpenScop] Warning: domain or context without 0 " + "as number of input dimensions.\n"); + return 0; + } + + while (relation != NULL) + { + // Properties (except the number of local dimensions) should be the same + // in all parts. + if ((expected_nb_output_dims != relation->nb_output_dims) || + (expected_nb_input_dims != relation->nb_input_dims) || + (expected_nb_parameters != relation->nb_parameters)) + { + fprintf(stderr, "[OpenScop] Warning: inconsistent properties.\n"); + return 0; + } + + // Check whether the number of columns is OK or not. + if (!openscop_relation_check_nb_columns(relation, + expected_nb_output_dims, + expected_nb_input_dims, + expected_nb_parameters)) + return 0; + + // The first column of a relation part should be made of 0 or 1 only, + // except: + // - for the [0][0] element of an access function in "matrix" + // representation which should be > 0 (array identifier), + // and all other elements are 0. + // - for scattering functions in "matrix" representation, the + // first column is made only of 0. + if ((relation->nb_rows > 0) && (relation->nb_columns > 0)) + { + start = 0; + if ((relation->nb_local_dims == OPENSCOP_UNDEFINED) && + (type == OPENSCOP_TYPE_ACCESS)) + { + start = 1; + if (SCOPINT_get_si(relation->m[0][0]) <= 0) + { + fprintf(stderr, "[OpenScop] Warning: bad array identifier " + "in access function.\n"); + return 0; + } + } + + for (i = start; i < relation->nb_rows; i++) + { + if ((type == OPENSCOP_TYPE_ACCESS) && + (relation->nb_local_dims == OPENSCOP_UNDEFINED)) + { + if (!SCOPINT_zero_p(relation->m[i][0])) + { + fprintf(stderr, "[OpenScop] Warning: non-first element of the " + "first column of an access function is not 0.\n"); + return 0; + } + } + else if ((type == OPENSCOP_TYPE_SCATTERING) && + (relation->nb_local_dims == OPENSCOP_UNDEFINED)) + { + if (!SCOPINT_zero_p(relation->m[i][0])) + { + fprintf(stderr, "[OpenScop] Warning: first column of a " + "scattering function not made of 0s.\n"); + return 0; + } + } + else + { + if (!SCOPINT_zero_p(relation->m[i][0]) && + !SCOPINT_one_p(relation->m[i][0])) + { + fprintf(stderr, "[OpenScop] Warning: first column of a relation " + "is not made of 0 or 1 only.\n"); + return 0; + } + } + } + } + + relation = relation->next; + } + + return 1; +} diff --git a/source/relation_list.c b/source/relation_list.c new file mode 100644 index 0000000..b7fe516 --- /dev/null +++ b/source/relation_list.c @@ -0,0 +1,459 @@ + + /*+-----------------------------------------------------------------** + ** OpenScop Library ** + **-----------------------------------------------------------------** + ** relation_list.c ** + **-----------------------------------------------------------------** + ** First version: 08/10/2010 ** + **-----------------------------------------------------------------** + + + ***************************************************************************** + * OpenScop: Structures and formats for polyhedral tools to talk together * + ***************************************************************************** + * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, * + * / / / // // // // / / / // // / / // / /|,_, * + * / / / // // // // / / / // // / / // / / / /\ * + * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ * + * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ * + * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ * + * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ * + * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ * + * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ * + * | I | | | | e | | | | | | | | | | | | | \ \ \ * + * | T | | | | | | | | | | | | | | | | | \ \ \ * + * | E | | | | | | | | | | | | | | | | | \ \ \ * + * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ * + * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / * + * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' * + * * + * Copyright (C) 2008 University Paris-Sud 11 and INRIA * + * * + * (3-clause BSD license) * + * Redistribution and use in source and binary forms, with or without * + * modification, are permitted provided that the following conditions * + * are met: * + * * + * 1. Redistributions of source code must retain the above copyright notice, * + * this list of conditions and the following disclaimer. * + * 2. Redistributions in binary form must reproduce the above copyright * + * notice, this list of conditions and the following disclaimer in the * + * documentation and/or other materials provided with the distribution. * + * 3. The name of the author may not be used to endorse or promote products * + * derived from this software without specific prior written permission. * + * * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * + * * + * OpenScop Library, a library to manipulate OpenScop formats and data * + * structures. Written by: * + * Cedric Bastoul and * + * Louis-Noel Pouchet * + * * + *****************************************************************************/ + + +# include +# include +# include +# include +# include + + +/*+*************************************************************************** + * Structure display function * + *****************************************************************************/ + + +/** + * openscop_relation_list_print_structure function: + * Displays a openscop_relation_list_t structure (a list of relations) into a + * file (file, possibly stdout). See openscop_relation_print_structure for + * more details. + * \param file File where informations are printed. + * \param l The list of relations whose information have to be printed. + * \param level Number of spaces before printing, for each line. + */ +void +openscop_relation_list_print_structure(FILE * file, openscop_relation_list_p l, + int level) +{ + int j, first = 1; + + // Go to the right level. + for (j = 0; j < level; j++) + fprintf(file,"|\t"); + + if (l != NULL) + fprintf(file, "+-- openscop_relation_list_t\n"); + else + fprintf(file, "+-- NULL relation list\n"); + + while (l != NULL) + { + if (!first) + { + // Go to the right level. + for (j = 0; j < level; j++) + fprintf(file, "|\t"); + fprintf(file, "| openscop_relation_list_t\n"); + } + else + first = 0; + + // A blank line. + for (j = 0; j <= level+1; j++) + fprintf(file, "|\t"); + fprintf(file, "\n"); + + // Print a relation. + openscop_relation_print_structure(file, l->elt, level+1); + + l = l->next; + + // Next line. + if (l != NULL) + { + for (j = 0; j <= level; j++) + fprintf(file, "|\t"); + fprintf(file, "V\n"); + } + } + + // The last line. + for (j = 0; j <= level; j++) + fprintf(file, "|\t"); + fprintf(file, "\n"); +} + + +/** + * openscop_relation_list_print function: + * This function prints the content of a openscop_relation_list_t into + * a file (file, possibly stdout). + * \param file File where informations are printed. + * \param list The relation whose information have to be printed. + */ +void +openscop_relation_list_print(FILE * file, openscop_relation_list_p list) +{ + openscop_relation_list_print_structure(file, list, 0); +} + + +/** + * openscop_relation_list_print_openscop function: + * This function prints the content of a openscop_relation_list_t structure + * into a file (file, possibly stdout) in the OpenScop format. + * \param file File where informations are printed. + * \param list The relation list whose information have to be printed. + * \param type Semantic about this relation (domain, access...). + * \param nb_iterators The number of iterators for the considered statement. + * \param iterators An array containing iterator names for the statement. + * \param nb_parameters The number of parameters in the SCoP. + * \param parameters An array containing all parameters names. + * \param nb_arrays The number of arrays accessed in the SCoP. + * \param arrays An array containing all accessed array names. + */ +void +openscop_relation_list_print_openscop(FILE * file, + openscop_relation_list_p list, + int type, + int nb_iterators, char ** iterators, + int nb_parameters, char ** parameters, + int nb_arrays, char ** arrays) +{ + int i; + openscop_relation_list_p head = list; + + // Count the number of elements in the list. + for (i = 0; list; list = list->next, i++) + ; + + // Print it. + if (i > 1) + fprintf(file,"# List of %d elements\n%d\n", i, i); + else + fprintf(file,"# List of %d element \n%d\n", i, i); + + // Print each element of the relation list. + i = 0; + while (head) + { + fprintf(file, "# List element No.%d\n", i); + openscop_relation_print_openscop(file, head->elt, type, + nb_iterators, iterators, + nb_parameters, parameters, + nb_arrays, arrays); + head = head->next; + i++; + } +} + + +/***************************************************************************** + * Reading function * + *****************************************************************************/ + + +/** + * openscop_relation_list_read function: + * This function reads a list of relations into a file (foo, + * posibly stdin) and returns a pointer this relation list. + * \param file The input stream. + * \return A pointer to the relation list structure that has been read. + */ +openscop_relation_list_p +openscop_relation_list_read(FILE* file) +{ + char s[OPENSCOP_MAX_STRING]; + int i; + openscop_relation_list_p list; + openscop_relation_list_p res; + int nb_mat; + + // Skip blank/commented lines. + while (fgets(s, OPENSCOP_MAX_STRING, file) == 0 || s[0] == '#' || + isspace(s[0])) + ; + + // Read the number of relations to read. + sscanf(s, "%d", &nb_mat); + + // Allocate the header of the list and start reading each element. + res = list = openscop_relation_list_malloc(); + for (i = 0; i < nb_mat; ++i) + { + list->elt = openscop_relation_read(file); + if (i < nb_mat - 1) + list->next = openscop_relation_list_malloc(); + list = list->next; + } + + return res; +} + + +/*+*************************************************************************** + * Memory allocation/deallocation function * + *****************************************************************************/ + + +/** + * openscop_relation_list_malloc function: + * This function allocates the memory space for a openscop_relation_list_t + * structure and sets its fields with default values. Then it returns + * a pointer to the allocated space. + * \return A pointer to an empty relation list with fields set to default + * values. + */ +openscop_relation_list_p +openscop_relation_list_malloc() +{ + openscop_relation_list_p res = + (openscop_relation_list_p) malloc(sizeof(openscop_relation_list_t)); + + if (res == NULL) + { + fprintf(stderr, "[OpenScop] Error: memory overflow.\n"); + exit(1); + } + + res->elt = NULL; + res->next = NULL; + + return res; +} + + + +/** + * openscop_relation_list_free function: + * This function frees the allocated memory for a openscop_relation_list_t + * structure, and all the relations stored in the list. + * \param list The pointer to the relation list we want to free. + */ +void +openscop_relation_list_free(openscop_relation_list_p list) +{ + openscop_relation_list_p tmp; + + if (list == NULL) + return; + + while (list) + { + if (list->elt) + openscop_relation_free(list->elt); + tmp = list->next; + free(list); + list = tmp; + } +} + + +/*+*************************************************************************** + * Processing functions * + *****************************************************************************/ + + +/** + * openscop_relation_list_node function: + * This function builds an openscop_relation_list_t node and sets its + * relation element as a copy of the one provided as parameter. + * \param relation The pointer to the relation to copy/paste in a list node. + * \return A pointer to a relation list node containing a copy of "relation". + */ +openscop_relation_list_p +openscop_relation_list_node(openscop_relation_p relation) +{ + openscop_relation_list_p new; + + new = openscop_relation_list_malloc(); + new->elt = openscop_relation_copy(relation); + + return new; +} + + +/** + * openscop_relation_list_copy function: + * This functions builds and returns a quasi-"hard copy" (not a pointer copy) + * of a openscop_relation_list_t data structure provided as parameter. + * \param list The pointer to the relation list we want to copy. + * \return A pointer to the full copy of the relation list in parameter. + */ +openscop_relation_list_p +openscop_relation_list_copy(openscop_relation_list_p list) +{ + int first = 1; + openscop_relation_list_p copy = NULL, node, previous = NULL; + + while (list != NULL) + { + node = openscop_relation_list_malloc(); + node->elt = openscop_relation_copy(list->elt); + + if (first) + { + first = 0; + copy = node; + previous = node; + } + else + { + previous->next = node; + previous = previous->next; + } + + list = list->next; + } + + return copy; +} + + +/** + * openscop_relation_list_concat function: + * this function builds a new relation list as the concatenation of the + * two lists sent as parameters. + * \param l1 The first relation list. + * \param l2 The second relation list. + * \return A pointer to the relation list resulting from the concatenation of + * l1 and l2. + */ +openscop_relation_list_p +openscop_relation_list_concat(openscop_relation_list_p l1, + openscop_relation_list_p l2) +{ + openscop_relation_list_p new, end; + + if (l1 == NULL) + return openscop_relation_list_copy(l2); + + if (l2 == NULL) + return openscop_relation_list_copy(l1); + + new = openscop_relation_list_copy(l1); + end = new; + while (end->next != NULL) + end = end->next; + end->next = openscop_relation_list_copy(l2); + + return new; +} + + +/** + * openscop_relation_list_equal function: + * This function returns true if the two relation lists are the same, false + * otherwise.. + * \param l1 The first relation list. + * \param l2 The second relation list. + * \return 1 if l1 and l2 are the same (content-wise), 0 otherwise. + */ +int +openscop_relation_list_equal(openscop_relation_list_p l1, + openscop_relation_list_p l2) +{ + while ((l1 != NULL) && (l2 != NULL)) + { + if (!openscop_relation_equal(l1->elt, l2->elt)) + return 0; + + l1 = l1->next; + l2 = l2->next; + } + + if (((l1 == NULL) && (l2 != NULL)) || ((l1 != NULL) && (l2 == NULL))) + return 0; + + return 1; +} + + +/** + * openscop_relation_integrity_check function: + * This function checks that a list of relation is "well formed" according to + * some expected properties (setting an expected value to OPENSCOP_UNDEFINED + * means that we do not expect a specific value) and what the relations are + * supposed to represent (all relations of a list are supposed to have the + * same semantics). It returns 0 if the check failed or 1 if no problem has + * been detected. + * \param list The relation list we want to check. + * \param type Semantics about this relation (domain, access...). + * \param expected_nb_output_dims Expected number of output dimensions. + * \param expected_nb_input_dims Expected number of input dimensions. + * \param expected_nb_parameters Expected number of parameters. + * \return 0 if the integrity check fails, 1 otherwise. + */ +int +openscop_relation_list_integrity_check(openscop_relation_list_p list, + int type, + int expected_nb_output_dims, + int expected_nb_input_dims, + int expected_nb_parameters) +{ + while (list != NULL) + { + if (!openscop_relation_integrity_check(list->elt, + type, + expected_nb_output_dims, + expected_nb_input_dims, + expected_nb_parameters)) + return 0; + + list = list->next; + } + + return 1; +} + diff --git a/source/scop.c b/source/scop.c dissimilarity index 65% index dd3e7c4..a508ba1 100644 --- a/source/scop.c +++ b/source/scop.c @@ -1,875 +1,927 @@ - - /*+-----------------------------------------------------------------** - ** OpenScop Library ** - **-----------------------------------------------------------------** - ** scop.c ** - **-----------------------------------------------------------------** - ** First version: 30/04/2008 ** - **-----------------------------------------------------------------** - - - ***************************************************************************** - * OpenScop: Structures and formats for polyhedral tools to talk together * - ***************************************************************************** - * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, * - * / / / // // // // / / / // // / / // / /|,_, * - * / / / // // // // / / / // // / / // / / / /\ * - * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ * - * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ * - * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ * - * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ * - * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ * - * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ * - * | I | | | | e | | | | | | | | | | | | | \ \ \ * - * | T | | | | | | | | | | | | | | | | | \ \ \ * - * | E | | | | | | | | | | | | | | | | | \ \ \ * - * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ * - * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / * - * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' * - * * - * Copyright (C) 2008 University Paris-Sud 11 and INRIA * - * * - * (3-clause BSD license) * - * Redistribution and use in source and binary forms, with or without * - * modification, are permitted provided that the following conditions * - * are met: * - * * - * 1. Redistributions of source code must retain the above copyright notice, * - * this list of conditions and the following disclaimer. * - * 2. Redistributions in binary form must reproduce the above copyright * - * notice, this list of conditions and the following disclaimer in the * - * documentation and/or other materials provided with the distribution. * - * 3. The name of the author may not be used to endorse or promote products * - * derived from this software without specific prior written permission. * - * * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * - * * - * OpenScop Library, a library to manipulate OpenScop formats and data * - * structures. Written by: * - * Cedric Bastoul and * - * Louis-Noel Pouchet * - * * - *****************************************************************************/ - -# include -# include -# include -# include -# include - - -/*+**************************************************************************** - * Structure display functions * - ******************************************************************************/ - - -/** - * openscop_scop_print_structure function: - * Displays a openscop_scop_t structure (*scop) into a file (file, possibly - * stdout) in a way that trends to be understandable without falling in a deep - * depression or, for the lucky ones, getting a headache... It includes an - * indentation level (level) in order to work with others print_structure - * functions. - * \param file File where informations are printed. - * \param scop The scop whose information have to be printed. - * \param level Number of spaces before printing, for each line. - ** - * - 30/04/2008: first version. - */ -void -openscop_scop_print_structure(FILE * file, openscop_scop_p scop, int level) -{ - int i, j; - - if (scop != NULL) - { - /* Go to the right level. */ - for (j = 0; j < level; j++) - fprintf(file,"|\t"); - fprintf(file,"+-- openscop_scop_t\n"); - - /* A blank line. */ - for (j = 0; j <= level+1; j++) - fprintf(file,"|\t"); - fprintf(file,"\n"); - - /* Print the context of the scop. */ - openscop_matrix_print_structure(file,scop->context,level+1); - - /* Print the original parameter names. */ - for (i = 0; i <= level; i++) - fprintf(file,"|\t"); - if (scop->nb_parameters > 0) - { - fprintf(file,"+-- Original parameters strings:"); - for (i = 0; i < scop->nb_parameters; i++) - fprintf(file," %s",scop->parameters[i]); - fprintf(file,"\n"); - } - else - fprintf(file,"+-- No original parameters string\n"); - - /* A blank line. */ - for (j = 0; j <= level+1; j++) - fprintf(file,"|\t"); - fprintf(file,"\n"); - - /* Print the original parameter names. */ - for (i = 0; i <= level; i++) - fprintf(file,"|\t"); - if (scop->nb_arrays > 0) - { - fprintf(file,"+-- Accessed array strings:"); - for (i = 0; i < scop->nb_arrays; i++) - fprintf(file," %s",scop->arrays[i]); - fprintf(file,"\n"); - } - else - fprintf(file,"+-- No accessed array string\n"); - - /* A blank line. */ - for (j = 0; j <= level+1; j++) - fprintf(file,"|\t"); - fprintf(file,"\n"); - - /* Print the statements. */ - openscop_statement_print_structure(file,scop->statement,level+1); - } - else - { - /* Go to the right level. */ - for (j = 0; j < level; j++) - fprintf(file,"|\t"); - fprintf(file,"+-- NULL scop\n"); - } - - /* The last line. */ - for (j = 0; j <= level; j++) - fprintf(file,"|\t"); - fprintf(file,"\n"); -} - - -/** - * openscop_scop_print function: - * This function prints the content of a openscop_scop_t structure (*scop) into - * a file (file, possibly stdout). - * \param file File where informations are printed. - * \param scop The scop whose information have to be printed. - ** - * - 30/04/2008: first version. - */ -void -openscop_scop_print(FILE * file, openscop_scop_p scop) -{ - openscop_scop_print_structure(file,scop,0); -} - - - -static -void -openscop_scop_print_dot_scop_(FILE * file, openscop_scop_p scop, - int castle, int arraystag) -{ - int i; - - if (castle) - { - fprintf(file,"# \n"); - fprintf(file,"# <| \n"); - fprintf(file,"# A \n"); - fprintf(file,"# /.\\ \n"); - fprintf(file,"# <| [\"\"M# \n"); - fprintf(file,"# A | # Clan McCloog Castle \n"); - fprintf(file,"# /.\\ [\"\"M# [Generated by the OpenScop "); - fprintf(file,"Library %s %s bits]\n",OPENSCOP_RELEASE, OPENSCOP_VERSION); - fprintf(file,"# [\"\"M# | # U\"U#U \n"); - fprintf(file,"# | # | # \\ .:/ \n"); - fprintf(file,"# | # | #___| # \n"); - fprintf(file,"# | \"--' .-\" \n"); - fprintf(file,"# |\"-\"-\"-\"-\"-#-#-## \n"); - fprintf(file,"# | # ## ###### \n"); - fprintf(file,"# \\ .::::'/ \n"); - fprintf(file,"# \\ ::::'/ \n"); - fprintf(file,"# :8a| # # ## \n"); - fprintf(file,"# ::88a ### \n"); - fprintf(file,"# ::::888a 8a ##::. \n"); - fprintf(file,"# ::::::888a88a[]:::: \n"); - fprintf(file,"# :::::::::SUNDOGa8a::::. .. \n"); - fprintf(file,"# :::::8::::888:Y8888:::::::::... \n"); - fprintf(file,"#::':::88::::888::Y88a______________________________"); - fprintf(file,"________________________\n"); - fprintf(file,"#:: ::::88a::::88a:Y88a "); - fprintf(file," __---__-- __\n"); - fprintf(file,"#' .: ::Y88a:::::8a:Y88a "); - fprintf(file,"__----_-- -------_-__\n"); - fprintf(file,"# :' ::::8P::::::::::88aa. _ _- -"); - fprintf(file,"- --_ --- __ --- __--\n"); - fprintf(file,"#.:: :::::::::::::::::::Y88as88a...s88aa.\n"); - } - else - { - fprintf(file,"# [File generated by ScopLib %s %s bits]\n", - OPENSCOP_RELEASE,OPENSCOP_VERSION); - } - - fprintf(file,"\n"); - fprintf(file,"SCoP\n"); - fprintf(file,"\n"); - fprintf(file,"# =============================================== Global\n"); - fprintf(file,"# Language\n"); - fprintf(file,"C\n"); - fprintf(file,"\n"); - - fprintf(file,"# Context\n"); - openscop_matrix_print_dot_scop(file,scop->context,OPENSCOP_TYPE_DOMAIN, - 0,NULL, - scop->nb_parameters,scop->parameters, - scop->nb_arrays,scop->arrays); - fprintf(file,"\n"); - - if (scop->nb_parameters > 0) - { - fprintf(file,"# Parameter names are provided\n"); - fprintf(file,"1\n"); - fprintf(file,"# Parameter names\n"); - for (i = 0; i < scop->nb_parameters; i++) - fprintf(file,"%s ",scop->parameters[i]); - fprintf(file,"\n"); - fprintf(file,"\n"); - } - else - { - fprintf(file,"# Parameter names are not provided\n"); - fprintf(file,"0\n"); - fprintf(file,"\n"); - } - - fprintf(file,"# Number of statements\n"); - fprintf(file,"%d\n",openscop_statement_number(scop->statement)); - fprintf(file,"\n"); - - openscop_statement_print_dot_scop(file,scop->statement, - scop->nb_parameters,scop->parameters, - scop->nb_arrays,scop->arrays); - - fprintf(file,"# =============================================== Options\n"); - if (scop->optiontags) - fprintf(file, "%s", scop->optiontags); - if (arraystag) - { - /* If the tag is present in the option tags, don't dump it. */ - char* content = openscop_scop_tag_content (scop, "", ""); - if (! content) - { - /* It isn't, so dump the list of arrays. */ - fprintf(file, "\n"); - fprintf(file, "%d\n", scop->nb_arrays); - for (i = 0; i < scop->nb_arrays; ++i) - fprintf(file, "%d %s\n", i + 1, scop->arrays[i]); - fprintf(file, "\n"); - } - else - free(content); - } -} - - -/** - * openscop_scop_print_dot_scop function: - * This function prints the content of a openscop_scop_t structure (*scop) - * into a file (file, possibly stdout) for the .scop format. - * \param file File where informations are printed. - * \param scop The scop whose information have to be printed. - ** - * - 02/05/2008: first version. - */ -void -openscop_scop_print_dot_scop(FILE * file, openscop_scop_p scop) -{ - openscop_scop_print_dot_scop_(file, scop, 0, 0); -} - -/** - * openscop_scop_print_dot_scop_castle function: - * This function prints the content of a openscop_scop_t structure (*scop) - * into a file (file, possibly stdout) for the .scop format, with the castle. - * \param file File where informations are printed. - * \param scop The scop whose information have to be printed. - ** - * - 02/05/2008: first version. - */ -void -openscop_scop_print_dot_scop_options(FILE * file, openscop_scop_p scop, - int options) -{ - int castle = 0; - int arraystag = 0; - if ((options & OPENSCOP_SCOP_PRINT_CASTLE) != 0) - castle = 1; - if ((options & OPENSCOP_SCOP_PRINT_ARRAYSTAG) != 0) - arraystag = 1; - openscop_scop_print_dot_scop_(file, scop, castle, arraystag); -} - - -/****************************************************************************** - * Reading function * - ******************************************************************************/ - -/** - * Internal function. Read 'nb_strings' strings on the input 'file'. - * - * \FIXME should be placed somewhere else, it's duplicated in statement.c. - */ -static -char** -openscop_scop_read_strings(FILE* file, int nb_strings) -{ - char str[OPENSCOP_MAX_STRING]; - char tmp[OPENSCOP_MAX_STRING]; - char* s; - char** res = NULL; - int i; - int count; - - /* Skip blank/commented lines. */ - while (fgets(str, OPENSCOP_MAX_STRING, file) == 0 || str[0] == '#' || - isspace(str[0])) - ; - s = str; - - /* Allocate the array of string. Make it NULL-terminated. */ - res = (char**) malloc(sizeof(char*) * (nb_strings + 1)); - res[nb_strings] = NULL; - - /* Read the desired number of strings. */ - for (i = 0; i < nb_strings; ++i) - { - for (count = 0; *s && ! isspace(*s) && *s != '#'; ++count) - tmp[count] = *(s++); - tmp[count] = '\0'; - res[i] = strdup(tmp); - if (*s != '#') - ++s; - } - - return res; -} - - -/** - * Internal function. Read an int on the input 'file'. - * - * \FIXME should be placed somewhere else, it's duplicated in statement.c. - */ -static -int -openscop_scop_read_int(FILE* file, char** str) -{ - char s[OPENSCOP_MAX_STRING]; - int res; - int i = 0; - int read_int = 0; - - if (file != NULL && str != NULL) - { - fprintf(stderr, "[Scoplib] Error: only one of the two parameters of" - " scop_read_int can be non-NULL\n"); - exit (1); - } - - if (file != NULL) - { - /* Parse from a file. */ - /* Skip blank/commented lines. */ - while (fgets(s, OPENSCOP_MAX_STRING, file) == 0 || s[0] == '#' || - isspace(s[0])) - ; - sscanf(s, "%d", &res); - } - if (str != NULL) - { - /* Parse from a string. */ - /* Skip blank/commented lines. */ - do - { - while (*str && **str && isspace(**str)) - ++(*str); - if (**str == '#') - { - while (**str && **str != '\n') - ++(*str); - } - else - { - /* Build the chain to analyze. */ - while (**str && !isspace(**str) && **str != '\n') - s[i++] = *((*str)++); - s[i] = '\0'; - sscanf(s, "%d", &res); - read_int = 1; - } - } - while (! read_int); - } - - return res; -} - - -/** - * openscop_scop_generate_names function: - * This function generates an array of size 'nb' of chars of the form - * "seedXX" where XX goes from 1 to nb. - * \param seed The template for the created names - * \param nb The number of created items. - */ -char** -openscop_scop_generate_names(char* seed, int nb) -{ - char** res = NULL; - char buff[strlen(seed) + 16]; - int i; - - if (nb) - { - res = (char**) malloc(sizeof(char*)* nb); - if (res == NULL) - { - fprintf(stderr, "[Scoplib] Memory Overflow.\n"); - exit(1); - } - for (i = 0; i < nb; ++i) - { - sprintf(buff, "%s%d", seed, i + 1); - res[i] = strdup(buff); - } - } - - return res; -} - - -/** - * openscop_scop_tag_content function: - * This function returns a freshly allocated string containing the - * content, in the optional tags section, between the tag 'tag' and - * the tag 'endtag'. If the tag 'tag' is not found, returns NULL. - */ -char* -openscop_scop_tag_content(openscop_scop_p scop, char* tag, char* endtag) -{ - return openscop_scop_tag_content_from_string(scop->optiontags, tag, endtag); -} - - -/** - * openscop_scop_tag_content_from_string function: - * This function returns a freshly allocated string containing the - * content, in the given string 'str', between the tag 'tag' and - * the tag 'endtag'. If the tag 'tag' is not found, returns NULL. - */ -char* -openscop_scop_tag_content_from_string(char* str, char* tag, char* endtag) -{ - int i; - char* start; - char* stop; - int size = 0; - int lentag; - char* res = NULL; - - if (str) - { - start = str; - lentag = strlen(tag); - for (; start && *start && strncmp(start, tag, lentag); ++start) - ; - /* The tag 'tag' was not found.*/ - if (! *start) - return NULL; - start += lentag; - stop = start; - lentag = strlen(endtag); - for (size = 0; *stop && strncmp(stop, endtag, lentag); ++stop, ++size) - ; - /* the tag 'endtag' was not found. */ - if (! *stop) - return NULL; - res = (char*) malloc((size + 1) * sizeof(char)); - if (res == NULL) - { - fprintf(stderr, "[Scoplib] Error: memory exhausted\n"); - exit(1); - } - /* Copy the chain between the two tags. */ - for (++start, i = 0; start != stop; ++start, ++i) - res[i] = *start; - res[i] = '\0'; - } - - return res; -} - - -/** - * openscop_scop_read function: - * This function reads a openscop_scop_t structure from an input stream - * (possibly stdin) corresponding to a openscop SCoP dump. - * \param file The input stream - */ -openscop_scop_p -openscop_scop_read(FILE* file) -{ - char tmpbuff[OPENSCOP_MAX_STRING]; - openscop_scop_p scop = NULL; - openscop_statement_p stmt = NULL; - openscop_statement_p prev = NULL; - int nb_statements; - char** tmp; - int i; - char* content; - - if (file == NULL) - return NULL; - - scop = openscop_scop_malloc(); - - /* Backup the arrays of the program. Buffer is reajustable. */ - int nb_arr = OPENSCOP_MAX_STRING; - char** arrays = (char**) malloc (sizeof(char*) * nb_arr); - for (i = 0; i < nb_arr; ++i) - arrays[i] = NULL; - - /* Ensure the file is a .scop. */ - tmp = openscop_scop_read_strings(file, 1); - if (strcmp(*tmp, "SCoP")) - { - fprintf(stderr, "[Scoplib] Error. The file is not a .scop\n"); - exit (1); - } - free(*tmp); - free(tmp); - - /* Read the language. */ - char** language = openscop_scop_read_strings(file, 1); - if (strcmp(*language, "C") && strcmp(*language, "JAVA") && - strcmp(*language, "C#")) - { - fprintf(stderr, "[Scoplib] Error. The language is not recognized\n"); - exit (1); - } - /* language is not used so far. */ - free(*language); - free(language); - - /* Read the context. */ - scop->context = openscop_matrix_read (file); - scop->nb_parameters = scop->context->NbColumns - 2; - - /* Read the parameter names, if any. */ - if (openscop_scop_read_int(file, NULL) > 0) - scop->parameters = openscop_scop_read_strings (file, scop->nb_parameters); - else - scop->parameters = openscop_scop_generate_names("M", scop->nb_parameters); - - /* Read the number of statements. */ - nb_statements = openscop_scop_read_int (file, NULL); - - for (i = 0; i < nb_statements; ++i) - { - /* Read each statement. */ - stmt = openscop_statement_read (file, scop->nb_parameters, - &arrays, &nb_arr); - if (scop->statement == NULL) - scop->statement = stmt; - else - prev->next = stmt; - prev = stmt; - } - - /* Read the remainder of the file, and store it in the optiontags - field. */ - /* Skip blank lines. */ - while (! feof(file) && - (fgets(tmpbuff, OPENSCOP_MAX_STRING, file) == 0 || - tmpbuff[0] == '#' || isspace(tmpbuff[0]) || tmpbuff[0] != '<')) - ; - /* Store the remainder of the file, if any. */ - if (tmpbuff[0]) - { - int count = strlen(tmpbuff) + 1; - int pos = 0; - int bufs = OPENSCOP_MAX_STRING; - scop->optiontags = (char*) malloc(bufs * sizeof(char)); - do - { - scop->optiontags = (char*) realloc - (scop->optiontags, (bufs += count) * sizeof(char)); - for (i = 0; i < count; ++i) - scop->optiontags[pos++] = tmpbuff[i]; - } - while ((count = fread(tmpbuff, sizeof(char), OPENSCOP_MAX_STRING, file)) - > 0); - scop->optiontags[pos++] = 0; - } - - /* Count the number of referenced arrays/variables. */ - scop->nb_arrays = 0; - for (stmt = scop->statement; stmt; stmt = stmt->next) - { - if (stmt->read) - for (i = 0; i < stmt->read->NbRows; ++i) - if (scop->nb_arrays < SCOPINT_get_si(stmt->read->p[i][0])) - scop->nb_arrays = SCOPINT_get_si(stmt->read->p[i][0]); - if (stmt->write) - for (i = 0; i < stmt->write->NbRows; ++i) - if (scop->nb_arrays < SCOPINT_get_si(stmt->write->p[i][0])) - scop->nb_arrays = SCOPINT_get_si(stmt->write->p[i][0]); - } - - /* Allocate the array names array. */ - scop->arrays = (char**) malloc(sizeof(char*) * (scop->nb_arrays + 1)); - for (i = 0; i < scop->nb_arrays; ++i) - scop->arrays[i] = NULL; - - /* Populate the array list with referenced in the tag, if - any. */ - if ((content = openscop_scop_tag_content(scop, "", ""))) - { - char* start = content; - int n_arr = openscop_scop_read_int(NULL, &content); - char buff2[OPENSCOP_MAX_STRING]; - int idx_array; - i = 0; - while (n_arr--) - { - /* Skip blank or commented lines. */ - while (*content == '#' || *content == '\n') - { - for (; *content != '\n'; ++content) - ; - ++content; - } - /* Get the variable id. */ - for (i = 0; *content && ! isspace(*content); ++i, ++content) - buff2[i] = *content; - buff2[i] = '\0'; - sscanf (buff2, "%d", &idx_array); - /* Get the variable name. */ - while (*content && isspace(*content)) - ++content; - for (i = 0; *content && ! isspace(*content); ++i, ++content) - buff2[i] = *content; - buff2[i] = '\0'; - /* array is in 0-basis. */ - if (arrays[idx_array - 1]) - free(arrays[idx_array - 1]); - arrays[idx_array - 1] = strdup(buff2); - /* Go to the end of line. */ - while (*content && *content != '\n') - ++content; - } - content = start; - } - - /* Fill the array of array names. */ - char** tmparrays = openscop_scop_generate_names("var", scop->nb_arrays); - for (i = 0; i < scop->nb_arrays; ++i) - { - if (arrays[i] == NULL || arrays[i][0] == '\0') - { - /* Use a generated name in case no array name was parsed. */ - scop->arrays[i] = tmparrays[i]; - if (arrays[i]) - free(arrays[i]); - } - else - { - /* Use the parsed array name. */ - scop->arrays[i] = arrays[i]; - free(tmparrays[i]); - } - } - scop->arrays[i] = NULL; - free(arrays); - free(tmparrays); - - - return scop; -} - - - -/*+**************************************************************************** - * Memory allocation/deallocation functions * - ******************************************************************************/ - - -/** - * openscop_scop_malloc function: - * This function allocates the memory space for a openscop_scop_t structure and - * sets its fields with default values. Then it returns a pointer to the - * allocated space. - ** - * - 30/04/2008: first version. - */ -openscop_scop_p -openscop_scop_malloc() -{ - openscop_scop_p scop; - - scop = (openscop_scop_p)malloc(sizeof(openscop_scop_t)); - if (scop == NULL) - { - fprintf(stderr, "[Scoplib] Memory Overflow.\n"); - exit(1); - } - - scop->context = NULL; - scop->nb_parameters = 0; - scop->parameters = NULL; - scop->nb_arrays = 0; - scop->arrays = NULL; - scop->statement = NULL; - scop->optiontags = NULL; - scop->usr = NULL; - - return scop; -} - - -/** - * openscop_scop_free function: - * This function frees the allocated memory for a openscop_scop_t structure. - * \param scop The pointer to the scop we want to free. - ** - * - 30/04/2008: first version. - */ -void -openscop_scop_free(openscop_scop_p scop) -{ - int i; - - if (scop != NULL) - { - openscop_matrix_free(scop->context); - if (scop->parameters != NULL) - { - for (i = 0; i < scop->nb_parameters; i++) - free(scop->parameters[i]); - free(scop->parameters); - } - if (scop->arrays != NULL) - { - for (i = 0; i < scop->nb_arrays; i++) - free(scop->arrays[i]); - free(scop->arrays); - } - openscop_statement_free(scop->statement); - free(scop->optiontags); - free(scop); - } -} - - - -/** - * openscop_scop_dup function: - * This function returns a fresh identical (non shadow) copy of the - * input scop. - * \param scop The scop whose information have to be printed. - ** - */ -openscop_scop_p -openscop_scop_dup(openscop_scop_p scop) -{ - int i; - openscop_statement_p stm; - openscop_statement_p tmp = NULL; - openscop_scop_p ret = openscop_scop_malloc(); - ret->context = openscop_matrix_copy(scop->context); - ret->nb_parameters = scop->nb_parameters; - ret->parameters = (char**) malloc(sizeof(char*) * ret->nb_parameters); - for (i = 0; i < ret->nb_parameters; ++i) - ret->parameters[i] = strdup(scop->parameters[i]); - ret->nb_arrays = scop->nb_arrays; - ret->arrays = (char**) malloc(sizeof(char*) * ret->nb_arrays); - for (i = 0; i < ret->nb_arrays; ++i) - ret->arrays[i] = strdup(scop->arrays[i]); - - for (stm = scop->statement; stm; stm = stm->next) - { - openscop_statement_p newstm = openscop_statement_malloc(); - newstm->domain = openscop_matrix_copy(stm->domain); - newstm->schedule = openscop_matrix_copy(stm->schedule); - newstm->read = openscop_matrix_copy(stm->read); - newstm->write = openscop_matrix_copy(stm->write); - newstm->nb_iterators = stm->nb_iterators; - newstm->iterators = (char**) malloc(sizeof(char*) * newstm->nb_iterators); - for (i = 0; i < newstm->nb_iterators; ++i) - newstm->iterators[i] = strdup(stm->iterators[i]); - newstm->body = strdup (stm->body); - if (ret->statement == NULL) - ret->statement = tmp = newstm; - else - { - tmp->next = newstm; - tmp = tmp->next; - } - } - if (scop->optiontags) - ret->optiontags = strdup(scop->optiontags); - ret->usr = scop->usr; - - return ret; -} - -/*+*************************************************************************** - * Processing functions * - *****************************************************************************/ - - -/** - * openscop_scop_equal function: - * this function returns true if the two scops are the same, false - * otherwise (the usr field is not tested). - * \param s1 The first scop. - * \param s2 The second scop. - * \return 1 if s1 and s2 are the same (content-wise), 0 otherwise. - */ -int -openscop_scop_equal(openscop_scop_p s1, openscop_scop_p s2) -{ - int i; - - if (//(s1->version != s2->version) || - (!openscop_matrix_equal(s1->context, s2->context)) || - (s1->nb_parameters != s2->nb_parameters) || - (s1->nb_scattdims != s2->nb_scattdims) || - (!openscop_statement_equal(s1->statement, s2->statement)) || - (strcmp(s1->optiontags, s2->optiontags) != 0)) - return 0; - - for (i = 0; i < s1->nb_parameters; i++) - if (strcmp(s1->parameters[i], s2->parameters[i]) != 0) - return 0; - - for (i = 0; i < s1->nb_scattdims; i++) - if (strcmp(s1->scattdims[i], s2->scattdims[i]) != 0) - return 0; - - return 1; -} - + + /*+-----------------------------------------------------------------** + ** OpenScop Library ** + **-----------------------------------------------------------------** + ** scop.c ** + **-----------------------------------------------------------------** + ** First version: 30/04/2008 ** + **-----------------------------------------------------------------** + + + ***************************************************************************** + * OpenScop: Structures and formats for polyhedral tools to talk together * + ***************************************************************************** + * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, * + * / / / // // // // / / / // // / / // / /|,_, * + * / / / // // // // / / / // // / / // / / / /\ * + * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ * + * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ * + * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ * + * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ * + * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ * + * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ * + * | I | | | | e | | | | | | | | | | | | | \ \ \ * + * | T | | | | | | | | | | | | | | | | | \ \ \ * + * | E | | | | | | | | | | | | | | | | | \ \ \ * + * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ * + * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / * + * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' * + * * + * Copyright (C) 2008 University Paris-Sud 11 and INRIA * + * * + * (3-clause BSD license) * + * Redistribution and use in source and binary forms, with or without * + * modification, are permitted provided that the following conditions * + * are met: * + * * + * 1. Redistributions of source code must retain the above copyright notice, * + * this list of conditions and the following disclaimer. * + * 2. Redistributions in binary form must reproduce the above copyright * + * notice, this list of conditions and the following disclaimer in the * + * documentation and/or other materials provided with the distribution. * + * 3. The name of the author may not be used to endorse or promote products * + * derived from this software without specific prior written permission. * + * * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * + * * + * OpenScop Library, a library to manipulate OpenScop formats and data * + * structures. Written by: * + * Cedric Bastoul and * + * Louis-Noel Pouchet * + * * + *****************************************************************************/ + +# include +# include +# include +# include +# include + + +/*+*************************************************************************** + * Structure display functions * + *****************************************************************************/ + + +/** + * openscop_scop_print_structure function: + * Displays a openscop_scop_t structure (*scop) into a file (file, possibly + * stdout) in a way that trends to be understandable without falling in a deep + * depression or, for the lucky ones, getting a headache... It includes an + * indentation level (level) in order to work with others print_structure + * functions. + * \param file File where informations are printed. + * \param scop The scop whose information have to be printed. + * \param level Number of spaces before printing, for each line. + */ +void +openscop_scop_print_structure(FILE * file, openscop_scop_p scop, int level) +{ + int i, j; + + if (scop != NULL) + { + // Go to the right level. + for (j = 0; j < level; j++) + fprintf(file, "|\t"); + fprintf(file, "+-- openscop_scop_t\n"); + + // A blank line. + for (j = 0; j <= level+1; j++) + fprintf(file, "|\t"); + fprintf(file, "\n"); + + // Print the language. + for (j = 0; j < level; j++) + fprintf(file, "|\t"); + fprintf(file, "|\tLanguage: %s\n", scop->language); + + // A blank line. + for (j = 0; j <= level+1; j++) + fprintf(file, "|\t"); + fprintf(file, "\n"); + + // Print the context of the scop. + openscop_relation_print_structure(file, scop->context, level+1); + + // Print the original parameter names. + for (i = 0; i <= level; i++) + fprintf(file, "|\t"); + if (scop->nb_parameters > 0) + { + fprintf(file, "+-- Parameter strings:"); + for (i = 0; i < scop->nb_parameters; i++) + fprintf(file, " %s", scop->parameters[i]); + fprintf(file, "\n"); + } + else + fprintf(file, "+-- No parameter strings\n"); + + // A blank line. + for (j = 0; j <= level+1; j++) + fprintf(file, "|\t"); + fprintf(file, "\n"); + + // Print the iterator names. + for (i = 0; i <= level; i++) + fprintf(file, "|\t"); + if (scop->nb_iterators > 0) + { + fprintf(file, "+-- Iterator strings:"); + for (i = 0; i < scop->nb_iterators; i++) + fprintf(file, " %s", scop->iterators[i]); + fprintf(file, "\n"); + } + else + fprintf(file,"+-- No iterator string\n"); + + // A blank line. + for (j = 0; j <= level+1; j++) + fprintf(file, "|\t"); + fprintf(file, "\n"); + + // Print the scattering dimension names. + for (i = 0; i <= level; i++) + fprintf(file, "|\t"); + if (scop->nb_scattdims > 0) + { + fprintf(file, "+-- Scattering dimension strings:"); + for (i = 0; i < scop->nb_scattdims; i++) + fprintf(file, " %s", scop->scattdims[i]); + fprintf(file, "\n"); + } + else + fprintf(file, "+-- No scattering dimension string\n"); + + // A blank line. + for (j = 0; j <= level+1; j++) + fprintf(file, "|\t"); + fprintf(file, "\n"); + + // Print the statements. + openscop_statement_print_structure(file, scop->statement, level+1); + } + else + { + // Go to the right level. + for (j = 0; j < level; j++) + fprintf(file, "|\t"); + fprintf(file, "+-- NULL scop\n"); + } + + // The last line. + for (j = 0; j <= level; j++) + fprintf(file, "|\t"); + fprintf(file, "\n"); +} + + +/** + * openscop_scop_print function: + * This function prints the content of a openscop_scop_t structure (*scop) into + * a file (file, possibly stdout). + * \param file File where informations are printed. + * \param scop The scop whose information have to be printed. + */ +void +openscop_scop_print(FILE * file, openscop_scop_p scop) +{ + openscop_scop_print_structure(file, scop, 0); +} + + +/** + * openscop_scop_print_openscop function: + * This function prints the content of a openscop_scop_t structure (*scop) + * into a file (file, possibly stdout) in the OpenScop format. + * \param file File where informations are printed. + * \param scop The scop whose information have to be printed. + */ +void +openscop_scop_print_openscop(FILE * file, openscop_scop_p scop) +{ + int i; + int nb_arrays = 0; + char ** arrays = NULL; + + // Extract array names information. + arrays = openscop_util_read_tag_arrays(scop->extensions, &nb_arrays); + + if (0) + { + fprintf(file, "# \n"); + fprintf(file, "# <| \n"); + fprintf(file, "# A \n"); + fprintf(file, "# /.\\ \n"); + fprintf(file, "# <| [\"\"M# \n"); + fprintf(file, "# A | # Clan McCloog Castle \n"); + fprintf(file, "# /.\\ [\"\"M# [Generated by the OpenScop "); + fprintf(file, "Library %s %s bits]\n",OPENSCOP_RELEASE, OPENSCOP_VERSION); + fprintf(file, "# [\"\"M# | # U\"U#U \n"); + fprintf(file, "# | # | # \\ .:/ \n"); + fprintf(file, "# | # | #___| # \n"); + fprintf(file, "# | \"--' .-\" \n"); + fprintf(file, "# |\"-\"-\"-\"-\"-#-#-## \n"); + fprintf(file, "# | # ## ###### \n"); + fprintf(file, "# \\ .::::'/ \n"); + fprintf(file, "# \\ ::::'/ \n"); + fprintf(file, "# :8a| # # ## \n"); + fprintf(file, "# ::88a ### \n"); + fprintf(file, "# ::::888a 8a ##::. \n"); + fprintf(file, "# ::::::888a88a[]:::: \n"); + fprintf(file, "# :::::::::SUNDOGa8a::::. .. \n"); + fprintf(file, "# :::::8::::888:Y8888:::::::::... \n"); + fprintf(file, "#::':::88::::888::Y88a______________________________"); + fprintf(file, "________________________\n"); + fprintf(file, "#:: ::::88a::::88a:Y88a "); + fprintf(file, " __---__-- __\n"); + fprintf(file, "#' .: ::Y88a:::::8a:Y88a "); + fprintf(file, "__----_-- -------_-__\n"); + fprintf(file, "# :' ::::8P::::::::::88aa. _ _- -"); + fprintf(file, "- --_ --- __ --- __--\n"); + fprintf(file, "#.:: :::::::::::::::::::Y88as88a...s88aa.\n"); + } + else + { + fprintf(file, "# [File generated by the OpenScop Library %s %s bits]\n", + OPENSCOP_RELEASE,OPENSCOP_VERSION); + } + + fprintf(file, "\nOpenScop\n\n"); + fprintf(file, "# =============================================== Global\n"); + fprintf(file, "# Language\n"); + fprintf(file, "%s\n\n", scop->language); + + fprintf(file, "# Context\n"); + openscop_relation_print_openscop(file, scop->context, OPENSCOP_TYPE_DOMAIN, + 0, NULL, + scop->nb_parameters, scop->parameters, + nb_arrays, arrays); + fprintf(file, "\n"); + + if (scop->nb_parameters > 0) + { + fprintf(file, "# Parameter names are provided\n"); + fprintf(file, "1\n"); + fprintf(file, "# Parameter names\n"); + for (i = 0; i < scop->nb_parameters; i++) + fprintf(file, "%s ", scop->parameters[i]); + fprintf(file, "\n\n"); + } + else + { + fprintf(file, "# Parameter names are not provided\n"); + fprintf(file, "0\n\n"); + } + + if (scop->nb_iterators > 0) + { + fprintf(file, "# Iterator names are provided\n"); + fprintf(file, "1\n"); + fprintf(file, "# Iterator names\n"); + for (i = 0; i < scop->nb_iterators; i++) + fprintf(file, "%s ", scop->iterators[i]); + fprintf(file, "\n\n"); + } + else + { + fprintf(file, "# Iterator names are not provided\n"); + fprintf(file, "0\n\n"); + } + + if (scop->nb_scattdims > 0) + { + fprintf(file, "# Scattering dimension names are provided\n"); + fprintf(file, "1\n"); + fprintf(file, "# Scattering dimension names\n"); + for (i = 0; i < scop->nb_scattdims; i++) + fprintf(file, "%s ", scop->scattdims[i]); + fprintf(file, "\n\n"); + } + else + { + fprintf(file, "# Scattering dimension names are not provided\n"); + fprintf(file, "0\n\n"); + } + + fprintf(file, "# Number of statements\n"); + fprintf(file, "%d\n\n",openscop_statement_number(scop->statement)); + + openscop_statement_print_openscop(file, scop->statement, + scop->nb_parameters, scop->parameters, + nb_arrays, arrays); + + fprintf(file, "# =============================================== Options\n"); + if (scop->extensions) + { + if (scop->textual_extensions) + fprintf(file, "%s", (char *)scop->extensions); + else + openscop_extension_print(file, (openscop_extension_p)scop->extensions); + } + + // Free array names + if (nb_arrays != 0) + { + for (i = 0; i < nb_arrays; i++) + free(arrays[i]); + free(arrays); + } +} + + +/***************************************************************************** + * Reading function * + *****************************************************************************/ + + +static +void +openscop_scop_update_val(int * variable, int value) +{ + if ((*variable == OPENSCOP_UNDEFINED) || (*variable == value)) + *variable = value; + else + fprintf(stderr, "[OpenScop] Warning: number of iterators and " + "parameters inconsistency.\n"); +} + +static +void +openscop_scop_update_properties(openscop_relation_p relation, + int nb_output_dims, int nb_input_dims, + int nb_parameters) +{ + if (relation != NULL) + { + openscop_scop_update_val(&(relation->nb_output_dims), nb_output_dims); + openscop_scop_update_val(&(relation->nb_input_dims), nb_input_dims); + openscop_scop_update_val(&(relation->nb_parameters), nb_parameters); + } +} + + +/** + * openscop_scop_propagate_properties internal function: + * This function tries to propagate information in all relations through the + * whole openscop representation. For instance, the number of parameters can + * be found in the context as well as in any relation: if it is undefined in + * the relation, this function defines it, if it is different than the + * expected value, it reports an error. This function does the same for + * the number of output and input dimensions. + * \param scop The SCoP we want to propagate properties. + */ +static +void +openscop_scop_propagate_properties(openscop_scop_p scop) +{ + int i, nb_parameters; + openscop_statement_p statement; + openscop_relation_p relation; + openscop_relation_list_p list; + + // Context part: get the number of parameters. + if ((scop->context != NULL) && + (openscop_relation_is_matrix(scop->context))) + { + nb_parameters = scop->context->nb_columns - 2; + openscop_scop_update_properties(scop->context, 0, 0, nb_parameters); + } + else + return; + + // For each statement: + statement = scop->statement; + while (statement != NULL) + { + // - Domain part, + relation = statement->domain; + if (openscop_relation_is_matrix(relation)) + { + while (relation != NULL) + { + openscop_scop_update_properties(relation, + relation->nb_columns - nb_parameters - 2, 0, nb_parameters); + relation = relation->next; + } + } + + // - Scattering part, + relation = statement->scattering; + if (openscop_relation_is_matrix(relation)) + { + while (relation != NULL) + { + openscop_scop_update_properties(relation, + 0, relation->nb_columns - nb_parameters - 2, nb_parameters); + relation = relation->next; + } + } + + // - Access part. + for (i = 0; i < 2; i++) + { + if (i == 0) + list = statement->read; + else + list = statement->write; + + while (list != NULL) + { + relation = list->elt; + if (openscop_relation_is_matrix(relation)) + { + while (relation != NULL) + { + openscop_scop_update_properties(relation, + 0, relation->nb_columns - nb_parameters - 2, nb_parameters); + relation = relation->next; + } + } + + list = list->next; + } + } + + statement = statement->next; + } +} + + +/** + * openscop_scop_read function: + * This function reads a openscop_scop_t structure from an input stream + * (possibly stdin) corresponding to an OpenScop input file. If some relation + * properties (number of input/output/local dimensions and number of + * parameters) are undefined, it will define them according to the available + * information. + * \param file The input stream + */ +openscop_scop_p +openscop_scop_read(FILE * file) +{ + openscop_scop_p scop = NULL; + openscop_statement_p stmt = NULL; + openscop_statement_p prev = NULL; + int nb_statements; + int max; + char ** tmp; + int i; + + if (file == NULL) + return NULL; + + scop = openscop_scop_malloc(); + + // Backup the arrays of the program. Buffer is reajustable. + /*int nb_arr = OPENSCOP_MAX_STRING; + char ** arrays = (char **) malloc (sizeof(char *) * nb_arr); + for (i = 0; i < nb_arr; ++i) + arrays[i] = NULL; + */ + + // + // I. CONTEXT PART + // + + // Ensure the file is a .scop. + tmp = openscop_util_read_strings(file, 1, &max); + if ((max == 0) || (strcmp(*tmp, "OpenScop"))) + { + fprintf(stderr, "[OpenScop] Error: not an OpenScop file " + "(type \"%s\".\n", *tmp); + exit (1); + } + if (max > 1) + fprintf(stderr, "[OpenScop] Warning: uninterpreted information " + "(after file type).\n"); + free(*tmp); + free(tmp); + + // Read the language. + char ** language = openscop_util_read_strings(file, 1, &max); + if (max == 0) + { + fprintf(stderr, "[OpenScop] Error: no language (backend) specified.\n"); + exit (1); + } + if (max > 1) + fprintf(stderr, "[OpenScop] Warning: uninterpreted information " + "(after language).\n"); + scop->language = *language; + free(language); + + // Read the context. + scop->context = openscop_relation_read(file); + scop->nb_parameters = scop->context->nb_columns - 2; + + // Read the parameter names, if any. + if (openscop_util_read_int(file, NULL) > 0) + { + scop->parameters = openscop_util_read_strings(file, + scop->nb_parameters, &max); + if (max < scop->nb_parameters) + { + fprintf(stderr, "[OpenScop] Error: not enough parameter names.\n"); + exit (1); + } + if (max > scop->nb_parameters) + fprintf(stderr, "[OpenScop] Warning: uninterpreted information " + "(after parameter names).\n"); + } + else + scop->parameters = NULL; + + // Read the iterator names, if any. + if (openscop_util_read_int(file, NULL) > 0) + scop->iterators = openscop_util_read_strings(file, -1, + &(scop->nb_iterators)); + else + { + scop->nb_iterators = 0; + scop->iterators = NULL; + } + + // Read the scattering dimension names, if any. + if (openscop_util_read_int(file, NULL) > 0) + scop->scattdims = openscop_util_read_strings(file, -1, + &(scop->nb_scattdims)); + else + { + scop->nb_scattdims = 0; + scop->scattdims = NULL; + } + + // + // II. STATEMENT PART + // + + // Read the number of statements. + nb_statements = openscop_util_read_int(file, NULL); + + for (i = 0; i < nb_statements; ++i) + { + // Read each statement. + stmt = openscop_statement_read(file); + if (scop->statement == NULL) + scop->statement = stmt; + else + prev->next = stmt; + prev = stmt; + } + + // + // III. OPTION PART + // + + // Read the remainder of the file, and store it in the extensions field. + scop->textual_extensions = 1; + scop->extensions = (void *)openscop_extension_read_string(file); + + // + // VI. FINALIZE AND CHECK + // + openscop_scop_propagate_properties(scop); + + if (!openscop_scop_integrity_check(scop)) + fprintf(stderr, "[OpenScop] Warning: global integrity check failed.\n"); + + return scop; +} + + +/*+*************************************************************************** + * Memory allocation/deallocation functions * + *****************************************************************************/ + + +/** + * openscop_scop_malloc function: + * This function allocates the memory space for a openscop_scop_t structure and + * sets its fields with default values. Then it returns a pointer to the + * allocated space. + * \return A pointer to an empty scop with fields set to default values. + */ +openscop_scop_p +openscop_scop_malloc() +{ + openscop_scop_p scop; + + scop = (openscop_scop_p)malloc(sizeof(openscop_scop_t)); + if (scop == NULL) + { + fprintf(stderr, "[OpenScop] Memory Overflow.\n"); + exit(1); + } + + scop->version = 1; + scop->textual_names = 1; + scop->textual_extensions = 1; + scop->language = NULL; + scop->context = NULL; + scop->nb_parameters = 0; + scop->nb_iterators = 0; + scop->nb_scattdims = 0; + scop->parameters = NULL; + scop->iterators = NULL; + scop->scattdims = NULL; + scop->statement = NULL; + scop->extensions = NULL; + scop->usr = NULL; + + return scop; +} + + +/** + * openscop_scop_free function: + * This function frees the allocated memory for a openscop_scop_t structure. + * \param scop The pointer to the scop we want to free. + */ +void +openscop_scop_free(openscop_scop_p scop) +{ + int i; + + if (scop != NULL) + { + if (scop->language != NULL) + free(scop->language); + + openscop_relation_free(scop->context); + + if (scop->parameters != NULL) + { + for (i = 0; i < scop->nb_parameters; i++) + free(scop->parameters[i]); + free(scop->parameters); + } + + if (scop->iterators != NULL) + { + for (i = 0; i < scop->nb_iterators; i++) + free(scop->iterators[i]); + free(scop->iterators); + } + + if (scop->scattdims != NULL) + { + for (i = 0; i < scop->nb_scattdims; i++) + free(scop->scattdims[i]); + free(scop->scattdims); + } + + openscop_statement_free(scop->statement); + + if (scop->textual_extensions) + free(scop->extensions); + else + openscop_extension_free((openscop_extension_p)scop->extensions); + + free(scop); + } +} + + +/*+*************************************************************************** + * Processing functions * + *****************************************************************************/ + + +/** + * openscop_scop_copy function: + * This functions builds and returns a "hard copy" (not a pointer copy) + * of a openscop_statement_t data structure provided as parameter. + * Note that the usr field is not touched by this function. + * \param statement The pointer to the scop we want to copy. + * \return A pointer to the full copy of the scop provided as parameter. + */ +openscop_scop_p +openscop_scop_copy(openscop_scop_p scop) +{ + openscop_scop_p copy; + + copy = openscop_scop_malloc(); + copy->textual_names = scop->textual_names; + copy->textual_extensions = scop->textual_extensions; + copy->version = scop->version; + copy->language = strdup(scop->language); + copy->context = openscop_relation_copy(scop->context); + copy->nb_parameters = scop->nb_parameters; + copy->nb_iterators = scop->nb_iterators; + copy->nb_scattdims = scop->nb_scattdims; + copy->parameters = openscop_util_copy_strings(scop->parameters, + scop->nb_parameters); + copy->iterators = openscop_util_copy_strings(scop->iterators, + scop->nb_iterators); + copy->scattdims = openscop_util_copy_strings(scop->scattdims, + scop->nb_scattdims); + copy->statement = openscop_statement_copy(scop->statement); + + if (scop->textual_extensions) + copy->extensions = strdup((char *)scop->extensions); + else + copy->extensions = openscop_extension_copy((openscop_extension_p) + scop->extensions); + + return copy; +} + + +/** + * openscop_scop_equal function: + * this function returns true if the two scops are the same, false + * otherwise (the usr field is not tested). + * \param s1 The first scop. + * \param s2 The second scop. + * \return 1 if s1 and s2 are the same (content-wise), 0 otherwise. + */ +int +openscop_scop_equal(openscop_scop_p s1, openscop_scop_p s2) +{ + int i; + + if (s1->version != s2->version) + { + fprintf(stderr, "[OpenScop] info: versions are not the same.\n"); + //return 0; + } + + if (strcmp(s1->language, s2->language) != 0) + { + fprintf(stderr, "[OpenScop] info: languages are not the same.\n"); + return 0; + } + + if (!openscop_relation_equal(s1->context, s2->context)) + { + fprintf(stderr, "[OpenScop] info: contexts are not the same.\n"); + return 0; + } + + if (s1->nb_parameters != s2->nb_parameters) + { + fprintf(stderr, "[OpenScop] info: #parameters are not the same.\n"); + return 0; + } + + if (s1->nb_iterators != s2->nb_iterators) + { + fprintf(stderr, "[OpenScop] info: #iterators are not the same.\n"); + return 0; + } + + if (s1->nb_scattdims != s2->nb_scattdims) + { + fprintf(stderr, "[OpenScop] info: #scattdims are not the same.\n"); + return 0; + } + + if (!openscop_statement_equal(s1->statement, s2->statement)) + { + fprintf(stderr, "[OpenScop] info: statements are not the same.\n"); + return 0; + } + + if ((s1->textual_extensions != s2->textual_extensions) || + (s1->textual_extensions && strcmp(s1->extensions, s2->extensions)) || + (!s1->textual_extensions && !openscop_extension_equal(s1->extensions, + s2->extensions))) + { + fprintf(stderr, "[OpenScop] info: extensions are not the same.\n"); + return 0; + } + + for (i = 0; i < s1->nb_parameters; i++) + if (strcmp(s1->parameters[i], s2->parameters[i]) != 0) + { + fprintf(stderr, "[OpenScop] info: parameter names are not the same.\n"); + return 0; + } + + for (i = 0; i < s1->nb_iterators; i++) + if (strcmp(s1->iterators[i], s2->iterators[i]) != 0) + { + fprintf(stderr, "[OpenScop] info: iterator names are not the same.\n"); + return 0; + } + + for (i = 0; i < s1->nb_scattdims; i++) + if (strcmp(s1->scattdims[i], s2->scattdims[i]) != 0) + { + fprintf(stderr, "[OpenScop] info: scattdims names are not the same.\n"); + return 0; + } + + return 1; +} + + +/** + * openscop_scop_integrity_check function: + * This function checks that a scop is "well formed". It returns 0 if the + * check failed or 1 if no problem has been detected. + * \param scop The scop we want to check. + * \return 0 if the integrity check fails, 1 otherwise. + */ +int +openscop_scop_integrity_check(openscop_scop_p scop) +{ + int expected_nb_parameters; + int nb_iterators, max_nb_iterators = 0; + int max_nb_scattdims = 0; + openscop_statement_p statement; + + // Check the language. + if ((scop->language != NULL) && + (!strcmp(scop->language, "caml") || !strcmp(scop->language, "Caml") || + !strcmp(scop->language, "ocaml") || !strcmp(scop->language, "OCaml"))) + fprintf(stderr, "[OpenScop] Alert: Caml ?! Are you sure ?! ;)\n"); + + // Check the context. + if (!openscop_relation_integrity_check(scop->context, + OPENSCOP_TYPE_CONTEXT, + 0, 0, OPENSCOP_UNDEFINED)) + return 0; + + // Get the number of parameters. + if (scop->context != NULL) + { + if (openscop_relation_is_matrix(scop->context)) + expected_nb_parameters = scop->context->nb_columns - 2; + else + expected_nb_parameters = scop->context->nb_parameters; + } + else + expected_nb_parameters = OPENSCOP_UNDEFINED; + + if (!openscop_statement_integrity_check(scop->statement, + expected_nb_parameters)) + return 0; + + // Ensure we have enough names. + if (expected_nb_parameters == OPENSCOP_UNDEFINED) + expected_nb_parameters = 0; + + statement = scop->statement; + while (statement != NULL) + { + if (statement->domain != NULL) + { + if (openscop_relation_is_matrix(statement->domain)) + { + nb_iterators = statement->domain->nb_columns - + expected_nb_parameters - 2; + if (nb_iterators > max_nb_iterators) + max_nb_iterators = nb_iterators; + } + else + { + if (statement->domain->nb_output_dims > max_nb_iterators) + max_nb_iterators = statement->domain->nb_output_dims; + } + } + + if (statement->scattering != NULL) + { + if (openscop_relation_is_matrix(statement->scattering)) + { + if (statement->domain->nb_rows > max_nb_scattdims) + max_nb_scattdims = statement->scattering->nb_rows; + } + else + { + if (statement->scattering->nb_input_dims > max_nb_scattdims) + max_nb_scattdims = statement->scattering->nb_input_dims; + } + } + + statement = statement->next; + } + + if ((scop->nb_iterators > 0) && + (scop->nb_iterators < max_nb_iterators)) + { + fprintf(stderr, "[OpenScop] Warning: not enough iterator names.\n"); + return 0; + } + + if ((scop->nb_scattdims > 0) && + (scop->nb_scattdims < max_nb_scattdims)) + { + fprintf(stderr, "[OpenScop] Warning: not enough scattering " + "dimension names.\n"); + return 0; + } + + return 1; +} diff --git a/source/statement.c b/source/statement.c index 4a03840..8d3a4ae 100644 --- a/source/statement.c +++ b/source/statement.c @@ -86,94 +86,94 @@ */ void openscop_statement_print_structure(FILE * file, openscop_statement_p statement, - int level) + int level) { int i, j, first = 1, number = 1; - /* Go to the right level. */ + // Go to the right level. for (j = 0; j < level; j++) - fprintf(file,"|\t"); + fprintf(file, "|\t"); if (statement != NULL) - fprintf(file,"+-- openscop_statement_t (S%d)\n",number); + fprintf(file, "+-- openscop_statement_t (S%d)\n", number); else - fprintf(file,"+-- NULL statement\n"); + fprintf(file, "+-- NULL statement\n"); while (statement != NULL) { if (!first) { - /* Go to the right level. */ + // Go to the right level. for (j = 0; j < level; j++) - fprintf(file,"|\t"); - fprintf(file,"| openscop_statement_t (S%d)\n",number); + fprintf(file, "|\t"); + fprintf(file, "| openscop_statement_t (S%d)\n", number); } else first = 0; - /* A blank line. */ + // A blank line. for (j = 0; j <= level+1; j++) - fprintf(file,"|\t"); - fprintf(file,"\n"); + fprintf(file, "|\t"); + fprintf(file, "\n"); - /* Print the domain of the statement. */ - openscop_matrix_print_structure(file,statement->domain,level+1); + // Print the domain of the statement. + openscop_relation_print_structure(file, statement->domain, level+1); - /* Print the schedule of the statement. */ - openscop_matrix_print_structure(file,statement->schedule,level+1); + // Print the scattering of the statement. + openscop_relation_print_structure(file, statement->scattering, level+1); - /* Print the array read access informations of the statement. */ - openscop_matrix_print_structure(file,statement->read,level+1); + // Print the array read access informations of the statement. + openscop_relation_list_print_structure(file, statement->read, level+1); - /* Print the array write access informations of the statement. */ - openscop_matrix_print_structure(file,statement->write,level+1); + // Print the array write access informations of the statement. + openscop_relation_list_print_structure(file, statement->write, level+1); - /* Print the original iterator names. */ - for (i=0; i<=level; i++) - fprintf(file,"|\t"); + // Print the original iterator names. + for (i = 0; i <= level; i++) + fprintf(file, "|\t"); if (statement->nb_iterators > 0) { - fprintf(file,"+-- Original iterator strings:"); + fprintf(file, "+-- Original iterator strings:"); for (i = 0; i < statement->nb_iterators; i++) - fprintf(file," %s",statement->iterators[i]); - fprintf(file,"\n"); + fprintf(file, " %s", statement->iterators[i]); + fprintf(file, "\n"); } else - fprintf(file,"+-- No original iterator string\n"); + fprintf(file, "+-- No original iterator string\n"); - /* A blank line. */ + // A blank line. for (i = 0; i <= level+1; i++) - fprintf(file,"|\t"); - fprintf(file,"\n"); + fprintf(file, "|\t"); + fprintf(file, "\n"); - /* Print the original statement body. */ + // Print the original statement body. for (i = 0; i <= level; i++) - fprintf(file,"|\t"); + fprintf(file, "|\t"); if (statement->body != NULL) - fprintf(file,"+-- Original body: %s\n",statement->body); + fprintf(file, "+-- Original body: %s\n", statement->body); else - fprintf(file,"+-- No original body\n"); + fprintf(file, "+-- No original body\n"); - /* A blank line. */ + // A blank line. for (i = 0; i <= level+1; i++) - fprintf(file,"|\t"); - fprintf(file,"\n"); + fprintf(file, "|\t"); + fprintf(file, "\n"); statement = statement->next; number++; - /* Next line. */ + // Next line. if (statement != NULL) { for (j = 0; j <= level; j++) - fprintf(file,"|\t"); - fprintf(file,"V\n"); + fprintf(file, "|\t"); + fprintf(file, "V\n"); } } - /* The last line. */ + // The last line. for (j = 0; j <= level; j++) - fprintf(file,"|\t"); - fprintf(file,"\n"); + fprintf(file, "|\t"); + fprintf(file, "\n"); } @@ -192,9 +192,9 @@ openscop_statement_print(FILE * file, openscop_statement_p statement) /** - * openscop_statement_print_dot_scop function: + * openscop_statement_print_openscop function: * This function prints the content of a openscop_statement_t structure - * (*statement) into a file (file, possibly stdout) for the .scop format. + * (*statement) into a file (file, possibly stdout) in the OpenScop format. * \param file File where informations are printed. * \param statement The statement whose information have to be printed. * \param nb_parameters The number of parameters in the SCoP. @@ -203,72 +203,74 @@ openscop_statement_print(FILE * file, openscop_statement_p statement) * \param arrays An array containing all accessed array names. */ void -openscop_statement_print_dot_scop(FILE * file, openscop_statement_p statement, - int nb_parameters, char ** parameters, - int nb_arrays, char ** arrays) +openscop_statement_print_openscop(FILE * file, openscop_statement_p statement, + int nb_parameters, char ** parameters, + int nb_arrays, char ** arrays) { int i, number = 1; while (statement != NULL) { - fprintf(file,"# =============================================== "); - fprintf(file,"Statement %d\n",number); - - fprintf(file,"# ---------------------------------------------- "); - fprintf(file,"%2d.1 Domain\n",number); - fprintf(file,"# Iteration domain\n"); - openscop_matrix_print_dot_scop(file, statement->domain, - OPENSCOP_TYPE_DOMAIN, - statement->nb_iterators, - statement->iterators, - nb_parameters,parameters, - nb_arrays,arrays); - fprintf(file,"\n"); - - fprintf(file,"# ---------------------------------------------- "); - fprintf(file,"%2d.2 Scattering\n",number); - fprintf(file,"# Scattering function is provided\n"); - fprintf(file,"1\n"); - fprintf(file,"# Scattering function\n"); - openscop_matrix_print_dot_scop(file,statement->schedule, - OPENSCOP_TYPE_SCATTERING, - statement->nb_iterators,statement->iterators, - nb_parameters,parameters, - nb_arrays,arrays); - fprintf(file,"\n"); - - fprintf(file,"# ---------------------------------------------- "); - fprintf(file,"%2d.3 Access\n",number); - fprintf(file,"# Access informations are provided\n"); - fprintf(file,"1\n"); - fprintf(file,"# Read access informations\n"); - openscop_matrix_print_dot_scop(file,statement->read,OPENSCOP_TYPE_ACCESS, - statement->nb_iterators,statement->iterators, - nb_parameters,parameters, - nb_arrays,arrays); - fprintf(file,"# Write access informations\n"); - openscop_matrix_print_dot_scop(file,statement->write,OPENSCOP_TYPE_ACCESS, - statement->nb_iterators,statement->iterators, - nb_parameters,parameters, - nb_arrays,arrays); - fprintf(file,"\n"); - - fprintf(file,"# ---------------------------------------------- "); - fprintf(file,"%2d.4 Body\n",number); - fprintf(file,"# Statement body is provided\n"); - fprintf(file,"1\n"); + fprintf(file, "# =============================================== "); + fprintf(file, "Statement %d\n", number); + + fprintf(file, "# ---------------------------------------------- "); + fprintf(file, "%2d.1 Domain\n", number); + fprintf(file, "# Iteration domain\n"); + openscop_relation_print_openscop(file, statement->domain, + OPENSCOP_TYPE_DOMAIN, + statement->nb_iterators, + statement->iterators, + nb_parameters, parameters, + nb_arrays, arrays); + fprintf(file, "\n"); + + fprintf(file, "# ---------------------------------------------- "); + fprintf(file, "%2d.2 Scattering\n", number); + fprintf(file, "# Scattering function is provided\n"); + fprintf(file, "1\n"); + fprintf(file, "# Scattering function\n"); + openscop_relation_print_openscop(file, statement->scattering, + OPENSCOP_TYPE_SCATTERING, + statement->nb_iterators, statement->iterators, + nb_parameters, parameters, + nb_arrays, arrays); + fprintf(file, "\n"); + + fprintf(file, "# ---------------------------------------------- "); + fprintf(file, "%2d.3 Access\n", number); + fprintf(file, "# Access informations are provided\n"); + fprintf(file, "1\n"); + fprintf(file, "\n# Read access information\n"); + openscop_relation_list_print_openscop(file, statement->read, + OPENSCOP_TYPE_ACCESS, + statement->nb_iterators, statement->iterators, + nb_parameters, parameters, + nb_arrays, arrays); + fprintf(file, "\n# Write access information\n"); + openscop_relation_list_print_openscop(file, statement->write, + OPENSCOP_TYPE_ACCESS, + statement->nb_iterators, statement->iterators, + nb_parameters, parameters, + nb_arrays, arrays); + fprintf(file, "\n"); + + fprintf(file, "# ---------------------------------------------- "); + fprintf(file, "%2d.4 Body\n", number); + fprintf(file, "# Statement body is provided\n"); + fprintf(file, "1\n"); if (statement->nb_iterators > 0) { - fprintf(file,"# Original iterator names\n"); + fprintf(file, "# Original iterator names\n"); for (i = 0; i < statement->nb_iterators; i++) - fprintf(file,"%s ",statement->iterators[i]); - fprintf(file,"\n"); + fprintf(file, "%s ", statement->iterators[i]); + fprintf(file, "\n"); } else - fprintf(file,"# No original iterator names\n"); - fprintf(file,"# Statement body\n"); - fprintf(file,"%s\n",statement->body); - fprintf(file,"\n\n"); + fprintf(file, "# No original iterator names\n"); + fprintf(file, "# Statement body\n"); + fprintf(file, "%s\n", statement->body); + fprintf(file, "\n\n"); statement = statement->next; number++; @@ -280,128 +282,72 @@ openscop_statement_print_dot_scop(FILE * file, openscop_statement_p statement, * Reading function * *****************************************************************************/ -/** - * Internal function. Read 'nb_strings' strings on the input 'file'. - * - * \FIXME should be placed somewhere else, it's duplicated in scop.c. - */ -static -char** -openscop_statement_read_strings(FILE* file, int nb_strings) -{ - char str[OPENSCOP_MAX_STRING]; - char tmp[OPENSCOP_MAX_STRING]; - char* s; - char** res = NULL; - int i; - int count; - - /* Skip blank/commented lines. */ - while (fgets(str, OPENSCOP_MAX_STRING, file) == 0 || str[0] == '#' || - isspace(str[0])) - ; - s = str; - - /* Allocate the array of string. Make it NULL-terminated. */ - res = (char**) malloc(sizeof(char*) * (nb_strings + 1)); - res[nb_strings] = NULL; - - /* Read the desired number of strings. */ - for (i = 0; i < nb_strings; ++i) - { - for (count = 0; *s && ! isspace(*s) && *s != '#'; ++count) - tmp[count] = *(s++); - tmp[count] = '\0'; - res[i] = strdup(tmp); - if (*s != '#') - ++s; - } - - return res; -} - -/** - * Internal function. Read an int on the input 'file'. - * - * \FIXME should be placed somewhere else, it's duplicated in scop.c. - */ -static -int -openscop_statement_read_int(FILE* file) -{ - char s[OPENSCOP_MAX_STRING]; - int res; - - /* Skip blank/commented lines. */ - while (fgets(s, OPENSCOP_MAX_STRING, file) == 0 || s[0] == '#' || - isspace(s[0])) - ; - sscanf(s, "%d", &res); - - return res; -} - -char** openscop_scop_generate_names(char*, int); /** * openscop_statement_read function: * This function reads a openscop_statement_t structure from an input stream * (possibly stdin). - * \param file The input stream - * \param nb_parameters The number of global parameters for the program - * \param arrays The array containing names of arrays of the - * input program - * \param nb_arr The size of the array parameter + * \param file The input stream. + * \return A pointer to the statement structure that has been read. */ openscop_statement_p -openscop_statement_read(FILE* file, int nb_parameters, char*** arrays, - int* nb_arr) +openscop_statement_read(FILE * file) { openscop_statement_p stmt = openscop_statement_malloc(); - char** tmp; + char buff[OPENSCOP_MAX_STRING], * start, * end; + int nb_iterators; if (file) + { + // Read the domain matrices. + stmt->domain = openscop_relation_read(file); + + // Read the scattering, if any. + if (openscop_util_read_int(file, NULL) > 0) + stmt->scattering = openscop_relation_read(file); + + // Read the access functions, if any. + if (openscop_util_read_int(file, NULL) > 0) { - /* Read the domain matrices. */ - stmt->domain = openscop_matrix_read(file); - - /* Read the scattering, if any. */ - if (openscop_statement_read_int(file) > 0) - stmt->schedule = openscop_matrix_read(file); - - /* Read the access functions, if any. */ - if (openscop_statement_read_int(file) > 0) - { - stmt->read = openscop_matrix_read_arrays(file, arrays, nb_arr); - stmt->write = openscop_matrix_read_arrays(file, arrays, nb_arr); - } - - stmt->nb_iterators = stmt->domain->NbColumns - 2 - nb_parameters; - /* Read the body information, if any. */ - if (openscop_statement_read_int(file) > 0) - { - if (stmt->nb_iterators > 0) - stmt->iterators = openscop_statement_read_strings(file, - stmt->nb_iterators); - tmp = openscop_statement_read_strings(file, 1); - stmt->body = tmp[0]; - free(tmp); - } - else - { - stmt->iterators = openscop_scop_generate_names("i", - stmt->nb_iterators); - stmt->body = strdup("[undefined]"); - } + stmt->read = openscop_relation_list_read(file); + stmt->write = openscop_relation_list_read(file); + } + + // Read the body information, if any. + if (openscop_util_read_int(file, NULL) > 0) + { + // Read the original iterator names. + stmt->iterators = openscop_util_read_strings(file, -1, &nb_iterators); + stmt->nb_iterators = nb_iterators; + + // Read the body: + // - Skip blank/commented lines and spaces. + start = openscop_util_skip_blank_and_comments(file, buff); + + // - Remove the comments. + end = start; + while ((*end != '#') && (*end != '\n')) + end++; + *end = '\0'; + + // - Copy the body. + stmt->body = strdup(start); + } + else + { + stmt->nb_iterators = OPENSCOP_UNDEFINED; + stmt->iterators = NULL; + stmt->body = strdup("[undefined]"); } + } return stmt; } -/*+************************************************************************** - * Memory allocation/deallocation functions * - ****************************************************************************/ +/*+*************************************************************************** + * Memory allocation/deallocation functions * + *****************************************************************************/ /** @@ -409,6 +355,7 @@ openscop_statement_read(FILE* file, int nb_parameters, char*** arrays, * This function allocates the memory space for a openscop_statement_t * structure and sets its fields with default values. Then it returns a pointer * to the allocated space. + * \return A pointer to an empty statement with fields set to default values. */ openscop_statement_p openscop_statement_malloc() @@ -418,18 +365,18 @@ openscop_statement_malloc() statement = (openscop_statement_p)malloc(sizeof(openscop_statement_t)); if (statement == NULL) { - fprintf(stderr, "[Scoplib] Memory Overflow.\n"); + fprintf(stderr, "[OpenScop] Error: memory overflow.\n"); exit(1); } - statement->domain = NULL; - statement->schedule = NULL; - statement->read = NULL; - statement->write = NULL; + statement->domain = NULL; + statement->scattering = NULL; + statement->read = NULL; + statement->write = NULL; statement->nb_iterators = 0; - statement->iterators = NULL; - statement->body = NULL; - statement->next = NULL; + statement->iterators = NULL; + statement->body = NULL; + statement->next = NULL; return statement; } @@ -450,10 +397,10 @@ openscop_statement_free(openscop_statement_p statement) while (statement != NULL) { next = statement->next; - openscop_matrix_free(statement->domain); - openscop_matrix_free(statement->schedule); - openscop_matrix_free(statement->read); - openscop_matrix_free(statement->write); + openscop_relation_free(statement->domain); + openscop_relation_free(statement->scattering); + openscop_relation_list_free(statement->read); + openscop_relation_list_free(statement->write); if (statement->iterators != NULL) { for (i = 0; i < statement->nb_iterators; i++) @@ -483,7 +430,7 @@ openscop_statement_free(openscop_statement_p statement) */ void openscop_statement_add(openscop_statement_p * location, - openscop_statement_p statement) + openscop_statement_p statement) { while (*location != NULL) location = &((*location)->next); @@ -492,12 +439,12 @@ openscop_statement_add(openscop_statement_p * location, } - /** * openscop_statement_number function: * This function returns the number of statements in the statement list * provided as parameter. * \param statement The first element of the statement list. + * \return The number of statements in the statement list. */ int openscop_statement_number(openscop_statement_p statement) @@ -514,8 +461,54 @@ openscop_statement_number(openscop_statement_p statement) /** + * openscop_statement_copy function: + * This functions builds and returns a "hard copy" (not a pointer copy) of a + * openscop_statement_t data structure provided as parameter. + * \param statement The pointer to the statement we want to copy. + * \return A pointer to the full copy of the statement provided as parameter. + */ +openscop_statement_p +openscop_statement_copy(openscop_statement_p statement) +{ + int first = 1; + openscop_statement_p copy = NULL, node, previous = NULL; + + while (statement != NULL) + { + node = openscop_statement_malloc(); + node->version = statement->version; + node->domain = openscop_relation_copy(statement->domain); + node->scattering = openscop_relation_copy(statement->scattering); + node->read = openscop_relation_list_copy(statement->read); + node->write = openscop_relation_list_copy(statement->write); + node->nb_iterators = statement->nb_iterators; + node->iterators = openscop_util_copy_strings(statement->iterators, + statement->nb_iterators); + node->body = strdup(statement->body); + node->next = NULL; + + if (first) + { + first = 0; + copy = node; + previous = node; + } + else + { + previous->next = node; + previous = previous->next; + } + + statement = statement->next; + } + + return copy; +} + + +/** * openscop_statement_equal function: - * this function returns true if the two statements are the same, false + * This function returns true if the two statements are the same, false * otherwise (the usr field is not tested). * \param s1 The first statement. * \param s2 The second statement. @@ -536,10 +529,10 @@ openscop_statement_equal(openscop_statement_p s1, openscop_statement_p s2) if (//(s1->version != s2->version) || (s1->nb_iterators != s2->nb_iterators) || - (!openscop_matrix_equal(s1->domain, s2->domain)) || - (!openscop_matrix_equal(s1->schedule, s2->schedule)) || - (!openscop_matrix_equal(s1->read, s2->read)) || - (!openscop_matrix_equal(s1->write, s2->write)) || + (!openscop_relation_equal(s1->domain, s2->domain)) || + (!openscop_relation_equal(s1->scattering, s2->scattering)) || + (!openscop_relation_list_equal(s1->read, s2->read)) || + (!openscop_relation_list_equal(s1->write, s2->write)) || (strcmp(s1->body, s2->body) != 0)) return 0; @@ -551,4 +544,73 @@ openscop_statement_equal(openscop_statement_p s1, openscop_statement_p s2) } +/** + * openscop_statement_integrity_check function: + * This function checks that a statement is "well formed" according to some + * expected properties (setting an expected value to OPENSCOP_UNDEFINED means + * that we do not expect a specific value). It returns 0 if the check failed + * or 1 if no problem has been detected. + * \param statement The statement we want to check. + * \param expected_nb_parameters Expected number of parameters. + * \return 0 if the integrity check fails, 1 otherwise. + */ +int +openscop_statement_integrity_check(openscop_statement_p statement, + int expected_nb_parameters) +{ + int expected_nb_iterators = OPENSCOP_UNDEFINED; + while (statement != NULL) + { + if (!openscop_relation_integrity_check(statement->domain, + OPENSCOP_TYPE_DOMAIN, + OPENSCOP_UNDEFINED, + 0, + expected_nb_parameters)) + return 0; + + // Get the number of iterators. + if (statement->domain != NULL) + { + if (openscop_relation_is_matrix(statement->domain)) + { + if (expected_nb_parameters != OPENSCOP_UNDEFINED) + expected_nb_iterators = statement->domain->nb_columns - + expected_nb_parameters - 2; + else + expected_nb_iterators = OPENSCOP_UNDEFINED; + } + else + expected_nb_iterators = statement->domain->nb_output_dims; + } + + if (!openscop_relation_integrity_check(statement->scattering, + OPENSCOP_TYPE_SCATTERING, + OPENSCOP_UNDEFINED, + expected_nb_iterators, + expected_nb_parameters) || + !openscop_relation_list_integrity_check(statement->read, + OPENSCOP_TYPE_ACCESS, + OPENSCOP_UNDEFINED, + expected_nb_iterators, + expected_nb_parameters) || + !openscop_relation_list_integrity_check(statement->write, + OPENSCOP_TYPE_ACCESS, + OPENSCOP_UNDEFINED, + expected_nb_iterators, + expected_nb_parameters)) + return 0; + + if ((statement->nb_iterators > 0) && + (statement->nb_iterators < statement->domain->nb_output_dims)) + { + fprintf(stderr, "[OpenScop] Warning: not enough original iterator " + "names.\n"); + return 0; + } + + statement = statement->next; + } + + return 1; +} diff --git a/source/util.c b/source/util.c new file mode 100644 index 0000000..b2ce00e --- /dev/null +++ b/source/util.c @@ -0,0 +1,463 @@ + + /*+-----------------------------------------------------------------** + ** OpenScop Library ** + **-----------------------------------------------------------------** + ** util.c ** + **-----------------------------------------------------------------** + ** First version: 08/10/2010 ** + **-----------------------------------------------------------------** + + + ***************************************************************************** + * OpenScop: Structures and formats for polyhedral tools to talk together * + ***************************************************************************** + * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, * + * / / / // // // // / / / // // / / // / /|,_, * + * / / / // // // // / / / // // / / // / / / /\ * + * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ * + * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ * + * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ * + * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ * + * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ * + * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ * + * | I | | | | e | | | | | | | | | | | | | \ \ \ * + * | T | | | | | | | | | | | | | | | | | \ \ \ * + * | E | | | | | | | | | | | | | | | | | \ \ \ * + * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ * + * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / * + * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' * + * * + * Copyright (C) 2008 University Paris-Sud 11 and INRIA * + * * + * (3-clause BSD license) * + * Redistribution and use in source and binary forms, with or without * + * modification, are permitted provided that the following conditions * + * are met: * + * * + * 1. Redistributions of source code must retain the above copyright notice, * + * this list of conditions and the following disclaimer. * + * 2. Redistributions in binary form must reproduce the above copyright * + * notice, this list of conditions and the following disclaimer in the * + * documentation and/or other materials provided with the distribution. * + * 3. The name of the author may not be used to endorse or promote products * + * derived from this software without specific prior written permission. * + * * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * + * * + * OpenScop Library, a library to manipulate OpenScop formats and data * + * structures. Written by: * + * Cedric Bastoul and * + * Louis-Noel Pouchet * + * * + *****************************************************************************/ + +# include +# include +# include +# include +# include + + +/** + * openscop_util_copy_strings internal function. + * This function builds and return a "hard copy" (not a pointer copy) of an + * array of strings. + * \param strings The array of strings to copy. + * \param nb_strings The number of strings in the array to copy. + * \return A pointer to the copy of the array of strings. + */ +char ** +openscop_util_copy_strings(char ** strings, int nb_strings) +{ + int i; + char ** copy; + + if ((strings == NULL) || (nb_strings == 0)) + return NULL; + + copy = (char **)malloc(nb_strings * sizeof(char *)); + + for (i = 0; i < nb_strings; i++) + copy[i] = strdup(strings[i]); + + return copy; +} + + +/** + * openscop_util_skip_blank_and_comments internal function. + * This function reads the open file 'file' line by line and skips + * blank/comment lines and spaces. The first line where there is some + * useful information is stored at the address 'str' (the memory to + * store the line must be allocated before the call to this function + * and must be at least OPENSCOP_MAX_STRING*sizeof(char)). The pointer + * to the first useful information in this line is returned by the + * function. + * \param file The (opened) file to read. + * \param str Address of an allocated space to store the first line + * that contains useful information. + * \return The address of the the first useful digit in str. + */ +char * openscop_util_skip_blank_and_comments(FILE * file, char * str) +{ + char * start; + + do + { + start = fgets(str, OPENSCOP_MAX_STRING, file); + while ((start != NULL) && isspace(*start) && (*start != '\n')) + start++; + } + while (start != NULL && (*start == '#' || *start == '\n')); + + return start; +} + + +/** + * openscop_util_read_strings internal function. + * Read a line in the input 'file' and extract the first 'nb_strings' strings + * from it. nb_strings is a maximum number (the special value -1 corresponds + * to infinity). If *max is not NULL, it is updated with the maximum number + * of strings that could have been read. It returns the NULL-terminated array + * of strings that have been read. + * \param file The file where to read some strings. + * \param nb_strings Maximum number of strings to read (-1: infinity). + * \param max Address to store the maximum number of strings that could + * have been read (stored if the address is not NULL). + * \return An array of strings. + */ +char ** +openscop_util_read_strings(FILE * file, int nb_strings, int * max) +{ + char str[OPENSCOP_MAX_STRING]; + char tmp[OPENSCOP_MAX_STRING]; + char * s, * start; + char ** res = NULL; + int i, count, actual_nb_strings = 0; + + // Skip blank/commented lines and spaces. + start = openscop_util_skip_blank_and_comments(file, str); + + // Count the actual number of strings. + s = start; + while (1) + { + for (count = 0; *s && ! isspace(*s) && *s != '#'; ++count) + s++; + + if (count != 0) + actual_nb_strings++; + + if ((*s == '#') || (*s == '\n')) + break; + else + ++s; + } + + // Update the number of strings if necessary. + if ((nb_strings == -1) || (actual_nb_strings < nb_strings)) + nb_strings = actual_nb_strings; + + if (max != NULL) + *max = actual_nb_strings; + + // Allocate the array of strings. Make it NULL-terminated. + res = (char **) malloc(sizeof(char *) * (nb_strings + 1)); + res[nb_strings] = NULL; + + // Read the desired number of strings. + s = start; + for (i = 0; i < nb_strings; ++i) + { + for (count = 0; *s && ! isspace(*s) && *s != '#'; ++count) + tmp[count] = *(s++); + tmp[count] = '\0'; + res[i] = strdup(tmp); + if (*s != '#') + ++s; + } + + return res; +} + + +/** + * openscop_util_read_int internal function. + * Read an int on the input 'file' or the input string 'str' depending on + * which one is not NULL. + * \param file The file where to read an int (if not NULL). + * \param str The string where to read an int (if not NULL). This pointer + * is updated to reflect the read and points after the int. + * \return The int that have been read. + */ +int +openscop_util_read_int(FILE * file, char ** str) +{ + char s[OPENSCOP_MAX_STRING], * start; + int res; + int i = 0; + int read_int = 0; + + if ((file != NULL && str != NULL) || (file == NULL && str == NULL)) + { + fprintf(stderr, "[OpenScop] Error: one and only one of the two parameters" + " of util_read_int can be non-NULL\n"); + exit (1); + } + + if (file != NULL) + { + // Parse from a file. + start = openscop_util_skip_blank_and_comments(file, s); + sscanf(start, " %d", &res); + } + if (str != NULL) + { + // Parse from a string. + // Skip blank/commented lines. + do + { + while (*str && **str && isspace(**str)) + ++(*str); + if (**str == '#') + { + while (**str && **str != '\n') + ++(*str); + } + else + { + // Build the chain to analyze. + while (**str && !isspace(**str) && **str != '\n') + s[i++] = *((*str)++); + s[i] = '\0'; + sscanf(s, "%d", &res); + read_int = 1; + } + } + while (! read_int); + } + + return res; +} + + +void +openscop_util_free_name_array(char ** name_array, int nb_names) +{ + int i; + + for (i = 0; i < nb_names; i++) + free(name_array[i]); + free(name_array); +} + + +/** + * openscop_util_generate_names internal function: + * This function generates an array of size 'nb' of chars of the form + * "seedXX" where XX goes from 1 to nb. + * \param seed The prefix for the created names. + * \param nb The number of names to generate. + * \return An array of 'nb' generated strings. + */ +char ** +openscop_util_generate_names(char * seed, int nb) +{ + char ** res = NULL; + char buff[strlen(seed) + 16]; + int i; + + if (nb) + { + res = (char **)malloc(sizeof(char *) * nb); + if (res == NULL) + { + fprintf(stderr, "[OpenScop] Error: memory overflow.\n"); + exit(1); + } + for (i = 0; i < nb; ++i) + { + sprintf(buff, "%s%d", seed, i + 1); + res[i] = strdup(buff); + } + } + + return res; +} + + +/** + * openscop_util_tag_content function: + * This function returns a freshly allocated string containing the + * content, in the given string 'str', between the tag 'tag' and + * the tag 'endtag'. If the tag 'tag' is not found, returns NULL. + * \param str The string where to find a given content. + * \param tag The string that marks the beginning of the content. + * \param endtag The string that marks the end of the content. + * \return The string between 'tag' and 'endtag' in 'str'. + */ +char * +openscop_util_tag_content(char * str, char * tag, char * endtag) +{ + int i; + char * start; + char * stop; + int size = 0; + int lentag; + char * res = NULL; + + if (str) + { + start = str; + lentag = strlen(tag); + for (; start && *start && strncmp(start, tag, lentag); ++start) + ; + // The tag 'tag' was not found. + if (! *start) + return NULL; + start += lentag; + stop = start; + lentag = strlen(endtag); + for (size = 0; *stop && strncmp(stop, endtag, lentag); ++stop, ++size) + ; + // the tag 'endtag' was not found. + if (! *stop) + return NULL; + res = (char *)malloc((size + 1) * sizeof(char)); + if (res == NULL) + { + fprintf(stderr, "[OpenScop] Error: memory overflow.\n"); + exit(1); + } + // Copy the chain between the two tags. + for (++start, i = 0; start != stop; ++start, ++i) + res[i] = *start; + res[i] = '\0'; + } + + return res; +} + + +char ** +openscop_util_read_tag_arrays(char * str, int * nb_arrays) +{ + int i, k, nb_names, array_index, max_index = 0; + int high_water_mark = OPENSCOP_MAX_ARRAYS; + char ** arrays; + char ** tmpnames; + char * content, * content_backup; + char buff[OPENSCOP_MAX_STRING]; + + content = openscop_util_tag_content(str, OPENSCOP_TAG_ARRAY_START, + OPENSCOP_TAG_ARRAY_STOP); + + if (content == NULL) + { + fprintf(stderr, "[OpenScop] Info: no array optional tag.\n"); + *nb_arrays = 0; + return NULL; + } + content_backup = content; + + // Allocate the array of names. + arrays = (char **)malloc(high_water_mark * sizeof(char *)); + for (i = 0; i < high_water_mark; i++) + arrays[i] = NULL; + + // Find the number of names provided. + nb_names = openscop_util_read_int(NULL, &content); + + // Get each array name. + for (k = 0; k < nb_names; k++) + { + // Skip blank or commented lines. + while (*content == '#' || *content == '\n') + { + for (; *content != '\n'; ++content) + ; + ++content; + } + + // Get the array name index. + for (i = 0; *content && ! isspace(*content); ++i, ++content) + buff[i] = *content; + buff[i] = '\0'; + sscanf(buff, "%d", &array_index); + max_index = (max_index > array_index) ? max_index : array_index; + if (array_index > high_water_mark) + { + fprintf(stderr, "[OpenScop] Info: array name indices sound high.\n"); + high_water_mark += OPENSCOP_MAX_ARRAYS; + arrays = (char **)realloc(arrays, high_water_mark * sizeof(char *)); + if (arrays == NULL) + { + fprintf(stderr, "[OpenScop] Error: memory overflow.\n"); + exit(1); + } + for (i = high_water_mark - OPENSCOP_MAX_ARRAYS; i < high_water_mark; i++) + arrays[i] = NULL; + } + if (array_index <= 0) + { + fprintf(stderr, "[OpenScop] Error: array index must be > 0.\n"); + exit(1); + } + + // Get the array name in buff. + while (*content && isspace(*content)) + ++content; + for (i = 0; *content && ! isspace(*content); ++i, ++content) + buff[i] = *content; + buff[i] = '\0'; + + // Array index is in 0-basis. + if (arrays[array_index - 1] != NULL) + { + fprintf(stderr, "[OpenScop] Warning: two array names have the " + "same index.\n"); + free(arrays[array_index - 1]); + } + arrays[array_index - 1] = strdup(buff); + + // Go to the end of line. + while (*content && *content != '\n') + ++content; + } + free(content_backup); + + // Free unused memory. + arrays = (char **)realloc(arrays, max_index * sizeof(char *)); + + // Fill the missing names (and let's hope there is no need for higher index). + tmpnames = openscop_util_generate_names("var", max_index); + for (i = 0; i < max_index; i++) + { + if (arrays[i] == NULL || arrays[i][0] == '\0') + arrays[i] = tmpnames[i]; // Use a generated name. + else + free(tmpnames[i]); // Use a read name. + } + free(tmpnames); + + if (OPENSCOP_DEBUG == 1) + { + printf("max_index: %d\n", max_index); + for (i = 0; i < max_index; i++) + printf("%s ", arrays[i]); + printf("\n"); + } + + *nb_arrays = max_index; + return arrays; +} diff --git a/source/vector.c b/source/vector.c index da32e23..7dc7b60 100644 --- a/source/vector.c +++ b/source/vector.c @@ -67,9 +67,9 @@ # include -/*+**************************************************************************** - * Structure display function * - ******************************************************************************/ +/*+*************************************************************************** + * Structure display function * + *****************************************************************************/ /** @@ -82,34 +82,33 @@ * \param file File where informations are printed. * \param vector The vector whose information have to be printed. * \param level Number of spaces before printing, for each line. - ** - * - 01/05/2008: first version. */ void -openscop_vector_print_structure(FILE * file, openscop_vector_p vector, int level) +openscop_vector_print_structure(FILE * file, openscop_vector_p vector, + int level) { int j; if (vector != NULL) { - /* Go to the right level. */ + // Go to the right level. for (j = 0; j < level; j++) fprintf(file,"|\t"); fprintf(file,"+-- openscop_vector_t\n"); for (j = 0; j <= level; j++) fprintf(file,"|\t"); - fprintf(file,"%d\n",vector->Size); + fprintf(file,"%d\n",vector->size); - /* Display the vector. */ + // Display the vector. for (j = 0; j <= level; j++) fprintf(file,"|\t"); fprintf(file,"[ "); - for (j = 0; j < vector->Size; j++) + for (j = 0; j < vector->size; j++) { - SCOPINT_print(file,OPENSCOP_FMT,vector->p[j]); + SCOPINT_print(file,OPENSCOP_FMT,vector->v[j]); fprintf(file," "); } @@ -117,13 +116,13 @@ openscop_vector_print_structure(FILE * file, openscop_vector_p vector, int level } else { - /* Go to the right level. */ + // Go to the right level. for (j = 0; j < level; j++) fprintf(file,"|\t"); fprintf(file,"+-- NULL vector\n"); } - /* The last line. */ + // The last line. for (j = 0; j <= level; j++) fprintf(file,"|\t"); fprintf(file,"\n"); @@ -136,8 +135,6 @@ openscop_vector_print_structure(FILE * file, openscop_vector_p vector, int level * (*vector) into a file (file, possibly stdout). * \param file File where informations are printed. * \param vector The vector whose information have to be printed. - ** - * - 01/05/2008: first version. */ void openscop_vector_print(FILE * file, openscop_vector_p vector) @@ -146,22 +143,21 @@ openscop_vector_print(FILE * file, openscop_vector_p vector) } -/*+**************************************************************************** - * Memory allocation/deallocation function * - ******************************************************************************/ +/*+*************************************************************************** + * Memory allocation/deallocation function * + *****************************************************************************/ /** * openscop_vector_malloc function: - * This function allocates the memory space for a openscop_vector_t structure and - * sets its fields with default values. Then it returns a pointer to the + * This function allocates the memory space for a openscop_vector_t structure + * and sets its fields with default values. Then it returns a pointer to the * allocated space. - * \param Size The number of entries of the vector to allocate. - ** - * - 01/05/2008: first version. + * \param size The number of entries of the vector to allocate. + * \return A pointer to the newly allocated openscop_vector_t structure. */ openscop_vector_p -openscop_vector_malloc(unsigned Size) +openscop_vector_malloc(unsigned size) { openscop_vector_p vector; openscop_int_t * p; @@ -170,23 +166,23 @@ openscop_vector_malloc(unsigned Size) vector = (openscop_vector_p)malloc(sizeof(openscop_vector_t)); if (vector == NULL) { - fprintf(stderr, "[Scoplib] Memory Overflow.\n"); + fprintf(stderr, "[OpenScop] Error: memory overflow.\n"); exit(1); } - vector->Size = Size; - if (Size == 0) - vector->p = NULL; + vector->size = size; + if (size == 0) + vector->v = NULL; else { - p = (openscop_int_t *)malloc(Size * sizeof(openscop_int_t)); + p = (openscop_int_t *)malloc(size * sizeof(openscop_int_t)); if (p == NULL) { - fprintf(stderr, "[Scoplib] Memory Overflow.\n"); + fprintf(stderr, "[OpenScop] Error: memory overflow.\n"); exit(1); } - vector->p = p; - for (i = 0; i < Size; i++) - SCOPINT_init_set_si(vector->p[i],0); + vector->v = p; + for (i = 0; i < size; i++) + SCOPINT_init_set_si(vector->v[i],0); } return vector; } @@ -196,8 +192,6 @@ openscop_vector_malloc(unsigned Size) * openscop_vector_free function: * This function frees the allocated memory for a openscop_vector_t structure. * \param vector The pointer to the vector we want to free. - ** - * - 01/05/2008: first version. */ void openscop_vector_free(openscop_vector_p vector) @@ -207,19 +201,20 @@ openscop_vector_free(openscop_vector_p vector) if (vector != NULL) { - p = vector->p; - for (i = 0; i < vector->Size; i++) + p = vector->v; + for (i = 0; i < vector->size; i++) SCOPINT_clear(*p++); - free(vector->p); + free(vector->v); free(vector); } } -/*+**************************************************************************** - * Processing functions * - ******************************************************************************/ +/*+*************************************************************************** + * Processing functions * + *****************************************************************************/ + /** * openscop_vector_add_scalar function: @@ -228,8 +223,7 @@ openscop_vector_free(openscop_vector_p vector) * vector). It returns a new vector resulting from this addition. * \param vector The basis vector. * \param scalar The scalar to add to the vector. - ** - * - 01/05/2008: first version. + * \return A pointer to a new vector, copy of the basis one plus the scalar. */ openscop_vector_p openscop_vector_add_scalar(openscop_vector_p vector, int scalar) @@ -237,17 +231,17 @@ openscop_vector_add_scalar(openscop_vector_p vector, int scalar) int i; openscop_vector_p result; - if ((vector == NULL) || (vector->Size < 2)) + if ((vector == NULL) || (vector->size < 2)) { - fprintf(stderr,"[Scoplib] Error: incompatible vector for addition\n"); + fprintf(stderr,"[OpenScop] Error: incompatible vector for addition.\n"); exit(1); } - result = openscop_vector_malloc(vector->Size); - for (i = 0; i < vector->Size; i++) - SCOPINT_assign(result->p[i],vector->p[i]); - SCOPINT_add_int(result->p[vector->Size - 1], - vector->p[vector->Size - 1],scalar); + result = openscop_vector_malloc(vector->size); + for (i = 0; i < vector->size; i++) + SCOPINT_assign(result->v[i],vector->v[i]); + SCOPINT_add_int(result->v[vector->size - 1], + vector->v[vector->size - 1],scalar); return result; } @@ -259,9 +253,8 @@ openscop_vector_add_scalar(openscop_vector_p vector, int scalar) * result as a new vector (the addition means the ith entry of the new vector * is equal to the ith entry of vector v1 plus the ith entry of vector v2). * \param v1 The first vector for the addition. - * \param v2 The second vector for the addition (result is v1+v2). - ** - * - 01/05/2008: first version. + * \param v2 The second vector for the addition. + * \return A pointer to a new vector, corresponding to v1 + v2. */ openscop_vector_p openscop_vector_add(openscop_vector_p v1, openscop_vector_p v2) @@ -269,15 +262,15 @@ openscop_vector_add(openscop_vector_p v1, openscop_vector_p v2) int i; openscop_vector_p v3; - if ((v1 == NULL) || (v2 == NULL) || (v1->Size != v2->Size)) + if ((v1 == NULL) || (v2 == NULL) || (v1->size != v2->size)) { - fprintf(stderr,"[Scoplib] Error: incompatible vectors for addition\n"); + fprintf(stderr,"[OpenScop] Error: incompatible vectors for addition.\n"); exit(1); } - v3 = openscop_vector_malloc(v1->Size); - for (i = 0; i < v1->Size; i++) - SCOPINT_addto(v3->p[i],v1->p[i],v2->p[i]); + v3 = openscop_vector_malloc(v1->size); + for (i = 0; i < v1->size; i++) + SCOPINT_addto(v3->v[i],v1->v[i],v2->v[i]); return v3; } @@ -290,8 +283,7 @@ openscop_vector_add(openscop_vector_p v1, openscop_vector_p v2) * is equal to the ith entry of vector v1 minus the ith entry of vector v2). * \param v1 The first vector for the subtraction. * \param v2 The second vector for the subtraction (result is v1-v2). - ** - * - 01/05/2008: first version. + * \return A pointer to a new vector, corresponding to v1 - v2. */ openscop_vector_p openscop_vector_sub(openscop_vector_p v1, openscop_vector_p v2) @@ -299,15 +291,16 @@ openscop_vector_sub(openscop_vector_p v1, openscop_vector_p v2) int i; openscop_vector_p v3; - if ((v1 == NULL) || (v2 == NULL) || (v1->Size != v2->Size)) + if ((v1 == NULL) || (v2 == NULL) || (v1->size != v2->size)) { - fprintf(stderr,"[Scoplib] Error: incompatible vectors for subtraction\n"); + fprintf(stderr,"[OpenScop] Error: " + "incompatible vectors for subtraction.\n"); exit(1); } - v3 = openscop_vector_malloc(v1->Size); - for (i = 0; i < v1->Size; i++) - SCOPINT_subtract(v3->p[i],v1->p[i],v2->p[i]); + v3 = openscop_vector_malloc(v1->size); + for (i = 0; i < v1->size; i++) + SCOPINT_subtract(v3->v[i],v1->v[i],v2->v[i]); return v3; } @@ -316,42 +309,40 @@ openscop_vector_sub(openscop_vector_p v1, openscop_vector_p v2) /** * openscop_vector_tag_inequality function: * This function tags a vector representation of a contraint as being an - * inequality >=0. This means in the PolyLib format, to set to 1 the very first - * entry of the vector. It modifies directly the vector provided as an argument. + * inequality >=0. This means in the PolyLib format, to set to 1 the very + * first entry of the vector. It modifies directly the vector provided as + * an argument. * \param vector The vector to be tagged. - ** - * - 01/05/2008: first version. */ void openscop_vector_tag_inequality(openscop_vector_p vector) { - if ((vector == NULL) || (vector->Size < 1)) + if ((vector == NULL) || (vector->size < 1)) { - fprintf(stderr,"[Scoplib] Error: vector cannot be tagged\n"); + fprintf(stderr,"[OpenScop] Error: vector cannot be tagged.\n"); exit(1); } - SCOPINT_set_si(vector->p[0],1); + SCOPINT_set_si(vector->v[0],1); } /** * openscop_vector_tag_equality function: * This function tags a vector representation of a contraint as being an - * equality ==0. This means in the PolyLib format, to set to 0 the very first - * entry of the vector. It modifies directly the vector provided as an argument. + * equality ==0. This means in the PolyLib format, to set to 0 the very + * first entry of the vector. It modifies directly the vector provided as + * an argument. * \param vector The vector to be tagged. - ** - * - 01/05/2008: first version. */ void openscop_vector_tag_equality(openscop_vector_p vector) { - if ((vector == NULL) || (vector->Size < 1)) + if ((vector == NULL) || (vector->size < 1)) { - fprintf(stderr,"[Scoplib] Error: vector cannot be tagged\n"); + fprintf(stderr,"[OpenScop] Error: vector cannot be tagged.\n"); exit(1); } - SCOPINT_set_si(vector->p[0],0); + SCOPINT_set_si(vector->v[0],0); } @@ -368,11 +359,11 @@ openscop_vector_equal(openscop_vector_p v1, openscop_vector_p v2) { int i; - if (v1->Size != v2->Size) + if (v1->size != v2->size) return 0; - for (i = 0; i < v1->Size; i++) - if (SCOPINT_ne(v1->p[i], v2->p[i])) + for (i = 0; i < v1->size; i++) + if (SCOPINT_ne(v1->v[i], v2->v[i])) return 0; return 1; diff --git a/tests/Makefile.am b/tests/Makefile.am index cd93a0a..53823bb 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -79,7 +79,7 @@ noinst_PROGRAMS = openscop_test TESTS = openscop_test -openscop_test_CPPFLAGS = -I$(top_srcdir)/include +openscop_test_CPPFLAGS = -I$(top_srcdir)/include -static openscop_test_LDFLAGS = -L$(top_srcdir)/source diff --git a/tests/openscop_test.c b/tests/openscop_test.c index 956270b..60ef912 100644 --- a/tests/openscop_test.c +++ b/tests/openscop_test.c @@ -108,18 +108,20 @@ int test_file(char * input_name, int verbose) // Dump the OpenScop data structures to OpenScop file format. output_name = tmpnam(NULL); output_file = fopen(output_name, "w"); - openscop_scop_print_dot_scop(output_file, input_scop); + openscop_scop_print_openscop(output_file, input_scop); fclose(output_file); // Raise the generated file to data structures. output_file = fopen(output_name, "r"); output_scop = openscop_scop_read(output_file); + //output_scop = openscop_scop_copy(output_scop); fclose(output_file); if (verbose) { printf("\n\n*************************************************\n\n"); - openscop_scop_print_dot_scop(stdout, output_scop); + openscop_scop_print(stdout, output_scop); + openscop_scop_print_openscop(stdout, output_scop); printf("\n*************************************************\n\n"); } @@ -152,6 +154,7 @@ int main(int argc, char * argv[]) int verbose = 0; // 1 if the verbose option is set, 0 otherwise. int dirtest = 1; // 1 if we check a whole directory, 0 for a single file. int fileidx = 0; // Index of the file to check in argv (0 if none). + int d_namlen; int suffix_length; DIR * dir; struct dirent * dp; @@ -182,9 +185,10 @@ int main(int argc, char * argv[]) dir = opendir(TEST_DIR); while ((dp = readdir(dir)) != NULL) { + d_namlen = strlen(dp->d_name); // If the file has the convenient suffix... - if ((dp->d_namlen > suffix_length) && - (!strcmp(dp->d_name+(dp->d_namlen-suffix_length), TEST_SUFFIX))) + if ((d_namlen > suffix_length) && + (!strcmp(dp->d_name+(d_namlen-suffix_length), TEST_SUFFIX))) { // Test it ! success += test_file(dp->d_name, verbose); diff --git a/tests/polynom.scop b/tests/polynom.scop index d670f77..e48851f 100644 --- a/tests/polynom.scop +++ b/tests/polynom.scop @@ -25,7 +25,7 @@ # :' ::::8P::::::::::88aa. _ _- -- --_ --- __ --- __-- #.:: :::::::::::::::::::Y88as88a...s88aa. -SCoP +OpenScop # =============================================== Global # Language @@ -37,7 +37,17 @@ C # Parameter names are provided 1 # Parameter names -N +N + +# Iterator names are provided +1 +# Iterator names +i j + +# Scattering dimension names are provided +1 +# Scattering dimension names +c0 c1 c2 c3 c4 # Number of statements 1 @@ -45,7 +55,13 @@ N # =============================================== Statement 1 # ---------------------------------------------- 1.1 Domain # Iteration domain -4 5 +2 +4 5 2 0 -1 1 + 1 1 0 0 0 ## i >= 0 + 1 -1 0 1 -1 ## -i+N-1 >= 0 + 1 0 1 0 0 ## j >= 0 + 1 0 -1 1 -1 ## -j+N-1 >= 0 +4 5 2 0 -1 1 1 1 0 0 0 ## i >= 0 1 -1 0 1 -1 ## -i+N-1 >= 0 1 0 1 0 0 ## j >= 0 @@ -65,12 +81,16 @@ N # ---------------------------------------------- 1.3 Access # Access informations are provided 1 -# Read access informations -3 5 +# Read access information +3 +1 5 1 1 1 0 0 ## C[i+j] +1 5 2 1 0 0 0 ## A[i] +1 5 3 0 1 0 0 ## B[j] -# Write access informations +# Write access information +1 1 5 1 1 1 0 0 ## C[i+j] @@ -84,3 +104,9 @@ C[i+j]+=A[i]*B[j]; # =============================================== Options + +3 +1 C +2 A +3 B + -- 2.11.4.GIT