| This is openscop.info, produced by makeinfo version 4.13 from |
| openscop.texi. |
| |
| This document describes OpenScop, a specification of a file format and |
| a set of data structures for polyhedral compilation tools to talk |
| together. It also describes briefly the OpenScop Library version |
| 0.8.1, a Free Software that provides an example of OpenScop |
| implementation. |
| |
| It would be quite kind to refer at the present document in any |
| publication that results from the use of the OpenScop Library: |
| |
| @TechReport{Bas11, |
| author = {C\'edric Bastoul}, |
| title = {OpenScop: A Specification and a Library for Data |
| Exchange in Polyhedral Compilation Tools}, |
| month = {September}, |
| year = 2011, |
| institution = {Paris-Sud University, France} |
| } |
| |
| Copyright (C) 2011 Paris-Sud University and INRIA. |
| |
| Permission is granted to copy, distribute and/or modify this |
| document under the terms of the GNU Free Documentation License, Version |
| 1.2 published by the Free Software Foundation; with no Invariant |
| Sections, with no Front-Cover Texts, and with no Back-Cover Texts. To |
| receive a copy of the GNU Free Documentation License, write to the Free |
| Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 02111-1307 USA. |
| |
| |
| File: openscop.info, Node: Top, Next: Introduction, Up: (dir) |
| |
| OpenSCop |
| ******** |
| |
| This document describes OpenScop, a specification of a file format and |
| a set of data structures for polyhedral compilation tools to talk |
| together. It also describes briefly the OpenScop Library version |
| 0.8.1, a Free Software that provides an example of OpenScop |
| implementation. |
| |
| It would be quite kind to refer at the present document in any |
| publication that results from the use of the OpenScop Library: |
| |
| @TechReport{Bas11, |
| author = {C\'edric Bastoul}, |
| title = {OpenScop: A Specification and a Library for Data |
| Exchange in Polyhedral Compilation Tools}, |
| month = {September}, |
| year = 2011, |
| institution = {Paris-Sud University, France} |
| } |
| |
| Copyright (C) 2011 Paris-Sud University and INRIA. |
| |
| Permission is granted to copy, distribute and/or modify this |
| document under the terms of the GNU Free Documentation License, Version |
| 1.2 published by the Free Software Foundation; with no Invariant |
| Sections, with no Front-Cover Texts, and with no Back-Cover Texts. To |
| receive a copy of the GNU Free Documentation License, write to the Free |
| Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 02111-1307 USA. |
| |
| * Menu: |
| |
| * Introduction:: |
| * Polyhedral Representation:: |
| * OpenScop Specification:: |
| * OpenScop Library:: |
| * References:: |
| |
| |
| File: openscop.info, Node: Introduction, Next: Polyhedral Representation, Prev: Top, Up: Top |
| |
| 1 Introduction |
| ************** |
| |
| OpenScop is an open specification that defines a file format and a set |
| of data structures to represent a _static control part_ (SCoP for |
| short), i.e., a program part that can be represented in the _polyhedral |
| model_. The goal of OpenScop is to provide a common interface to |
| various 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 tools 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 some internal changes in one |
| element of the chain. The other promise of OpenScop is the ability to |
| assemble or replace the basic blocks of a polyhedral compilation |
| framework at no, or at least low engineering cost. |
| |
| The policy that drives OpenScop can be summarized by these three |
| rules: |
| * Embed the _minimum_ information to build a complete polyhedral |
| compilation framework in the so-called _core part_ (to |
| avoid as much as possible empty or useless information for |
| each tool). |
| |
| * Provide a _very stable_ core part (so users have some |
| guarantee that they will not need to update their tool |
| because of frequent specification evolution), |
| |
| * Provide a _very flexible_ extension part (so it can also be |
| used to test wild new ideas). |
| |
| Another, more technical, rule may be added: |
| * Avoid any need for external library or tool to support it |
| (i.e., it's not XML or YAML or anything like that). |
| |
| The success of OpenScop in meeting its goals totally depends on its |
| acceptance by the tool developers (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 developers may feel free to use it in their code (either by |
| linking it or copy-pasting its code). This document also describes this |
| library briefly (readers are invited to read at its technical |
| documentation). 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 the |
| OpenScop mailing list <openscop-development@googlegroups.com>. |
| |
| 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 (*note Polyhedral Representation::). Next, we |
| describe the OpenScop specification, from the file format (*note |
| OpenScop File Format Specification::) to the data structures and the |
| OpenScop Library API (*note OpenScop Data Structure Specification::). |
| Finally we will detail how to install the OpenScop Library (*note |
| Installation::). |
| |
| |
| File: openscop.info, Node: Polyhedral Representation, Next: OpenScop Specification, Prev: Introduction, Up: Top |
| |
| 2 Polyhedral Representation of Programs |
| *************************************** |
| |
| If you are reading at the OpenScop documentation, you probably don't |
| need any explanation about the polyhedral model. It is unlikely that |
| someone will read this paper by mistake. 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, 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 a few prerequisites. You should not read the following while you |
| still ignore what is: |
| * a `for' loop construction in C programs (`do' loops in FORTRAN are |
| OK too!), |
| |
| * an _affine expression_, |
| |
| * a _vector_, |
| |
| * a _matrix_, |
| |
| * a _matrix-vector multiply_. |
| 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 them here! |
| |
| * Menu: |
| |
| * Motivation:: |
| * Thinking in Polyhedra:: |
| * What's Next?:: |
| |
| |
| File: openscop.info, Node: Motivation, Next: Thinking in Polyhedra, Up: Polyhedral Representation |
| |
| 2.1 Motivation: Program Transformations |
| ======================================= |
| |
| 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 |
| functional units, of registers etc. The list of such "architectural |
| features" is growing with each new generation of processors. To |
| achieve the best performance, the object program must use these |
| features in a smart way. Programmers use high level languages for |
| productivity and portability: typically they do not have to take care |
| of the target architecture but to ensure they write programs which |
| produce the right output. Hence, the problem of mapping the program to |
| the target architecture in the most efficient way is left to the |
| compiler. |
| |
| The compiler may see a high level program as a specification _of an |
| output_. The program is a list of instructions to be executed to |
| produce the output. As long as the output is guaranteed to be as the |
| programmer specified in his code, the compiler is free to modify the |
| program. For instance, let us imagine we are working on an |
| architecture with only three registers and we consider the following |
| statements written by a programmer: |
| |
| x = a + b; |
| y = c + d; |
| z = a * b; |
| |
| It is easy to see that we can reorder the three statements in any |
| way without modifying the semantics (no statement reads or writes a |
| variable that another statement writes). Because of the lack of |
| registers, the solutions such that the first and the third statements |
| are one after the other are better because `a' and `b' will be put in |
| the processor registers by one statement and can be reused directly by |
| the other one without reading from memory (this is called a _data |
| locality improving_ transformation). Hence a better statement order is, |
| e.g.: |
| |
| x = a + b; |
| z = a * b; // a and b are still in processor registers |
| y = c + d; |
| |
| We can also notice that it is possible to run the three statements in |
| parallel (possibly on different processors). The programmer may |
| explicit this in a way the compiler and/or the architecture is able to |
| understand. For instance, we can use OpenMP to describe parallelism |
| (this is called a _parallelizing_ transformation): |
| |
| #pragma omp parallel sections |
| { |
| #pragma omp section |
| { |
| x = a + b; |
| } |
| #pragma omp section |
| { |
| y = c + d; |
| } |
| #pragma omp section |
| { |
| z = a * b; |
| } |
| } |
| |
| However, the right way to optimize this program is probably a |
| tradeoff between these two techniques. This is true if, e.g., the target |
| architecture has some limitations to run too many operations in |
| parallel, or, like in our case, when some data may be reused by some |
| processors. Hence, the best optimization for our small example is |
| probably the following: |
| |
| #pragma omp parallel sections |
| { |
| #pragma omp section |
| { |
| x = a + b; |
| z = a * b; |
| } |
| #pragma omp section |
| { |
| y = c + d; |
| } |
| } |
| |
| This example is quite trivial because the statements are executed |
| only once. The real sport begins when we have to deal with loops, as we |
| will see momentarily. However, polyhedral compilation framework users |
| have to be conscious that we _need_ to transform programs to achieve |
| the best performance and that the best transformation that has to be |
| discovered (at the price of many, many efforts) and performed may be |
| quite complex. Hence the need of powerful model and tools. |
| |
| |
| File: openscop.info, Node: Thinking in Polyhedra, Next: What's Next?, Prev: Motivation, Up: Polyhedral Representation |
| |
| 2.2 Thinking in Polyhedra |
| ========================= |
| |
| Since the very first compilers, the internal representation of programs |
| is the _Abstract Syntax Tree_, or AST. In such representation, each |
| statement appears only once even if it is executed many times (e.g., |
| when it is enclosed inside a loop). This is a limitation for finding |
| and applying complex transformations: |
| * It limits program analysis power. For instance if a statement |
| _depends_ on another statement (i.e., they access the same |
| memory location and at least one of these accesses is a write), |
| we will consider both statements as unique entities while the |
| dependence relation may involve only few statement executions. |
| |
| * It limits program transformation power. 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 (yes, that's |
| ridiculous). |
| |
| * It limits program manipulation flexibility. Trees are very |
| rigid data structures that are not easy to manipulate. |
| Program transformation may require very complex transformations |
| that will imply deep modifications of the control flow. |
| |
| The Polyhedral Model is a convenient alternative representation which |
| combines analysis power, expressiveness and high flexibility. The |
| drawback is it breaks the classical structure of programs that every |
| programmer is familiar with. It requires some (real) efforts to be |
| smoothly manipulated, but it definitely worth it. It is based on three |
| main concepts, _iteration domain_, _scattering function_ and _access |
| function_ that are described in depth in the following sections. |
| |
| A program part that can be represented using the Polyhedral Model is |
| called a *Static Control Part* or *SCoP* for short. |
| |
| * Menu: |
| |
| * Iteration Domain:: |
| * Scattering Function:: |
| * Access Function:: |
| |
| |
| File: openscop.info, Node: Iteration Domain, Next: Scattering Function, Up: Thinking in Polyhedra |
| |
| 2.2.1 Iteration Domain |
| ---------------------- |
| |
| The key aspect of the polyhedral model is to consider _statement |
| instances_. A statement instance is _one_ execution of a statement. A |
| statement outside a loop has only one instance while those inside loops |
| may have many. Let us consider the following code with two statements |
| `S1' and `S2': |
| |
| pi = 3.14; // S1 |
| for (i = 0; i < 5; i++) |
| A[i] = pi; // S2 |
| |
| The list of statement instances is the following (we just have to |
| fully unroll the loop): |
| |
| pi = 3.14; |
| A[0] = pi; |
| A[1] = pi; |
| A[2] = pi; |
| A[3] = pi; |
| A[4] = pi; |
| |
| Each instance of a statement which is enclosed inside a loop may be |
| referred thanks to its outer loop counters (or _iterators_). In the |
| polyhedral model we consider statements as functions of the outer loop |
| counters that may produce statement instances: instead of simply |
| "`S2'", we use preferably the notation `S2(i)'. For instance we |
| denote the statement instance `A[3] = pi;' of the previous example as |
| `S2(3)'. This means _instance of statement `S2' for_ `i = 3'. If a |
| statement `S3' is enclosed inside two loops of iterators `i' (outermost |
| loop) and `j' (innermost loop), we would denote it `S3(i,j)', and so on |
| with more enclosing loops. |
| |
| The ordered list of iterators (ordered from the outermost iterator |
| to the innermost iterator) is called the *iteration vector*. For |
| instance the iteration vector for `S3' is `(i,j)', for `S2' it is |
| `(i)', and for `S1' it is empty since it has no enclosing loop: `()'. A |
| more precise reading at the notation `S2(3)' would show that it denotes |
| the instance of statement `S2' for the iteration vector `(2)'. |
| |
| Obviously, dealing with statement instances does not mean we have to |
| unroll all loops. First because there would be probably too many |
| instances to deal with, and second because we probably just do not know |
| how many instances there are. For instance in the following loop it is |
| impossible to know (at compile time) how many times the statement `S3' |
| will be executed: |
| |
| for (i = 2; i <= N; i++) |
| for (j = 2; j <= N; j++) |
| A[i] = pi; // S3 |
| |
| Such a loop is said to be _parametric_: it depends on (at least) a |
| value called a _parameter_ which is not modified during the execution |
| of the whole loop, but is unknown at compile time. Here, the only |
| parameter is `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 *iteration domain*. It can be conveniently |
| described thanks to all the constraints on the various iterators the |
| statement depends on. For instance, let us consider the statement `S3' |
| of the previous program. The iteration domain is the set of iteration |
| vectors `(i,j)'. Because of the parameter, we are not able to achieve a |
| precise list of all possible values. It would look like this: |
| |
| (2,2) (2,3) (2,4) ... (2,N) |
| (3,2) (3,3) (3,4) ... (3,N) |
| ... ... ... ... ... |
| (N,2) (N,3) (N,4) ... (N,N) |
| |
| A better way is to say it is the set of iteration vectors `(i,j)' such |
| that `i' is an integer greater or equal than 2 and lower or equal than |
| `N', and `j' is an integer greater or equal than 2 and lower or equal |
| than `N'. This may be written in the following mathematical form: |
| |
| D_S3 = {(i,j) in Z^2 | 2 <= i <= N && 2 <= j <= N } |
| |
| It is easy to see that this iteration domain is a part of the |
| 2-dimensional space |
| Z^2. |
| We often use in our research papers a graphical representation that |
| gives a better view of this subspace: |
| |
| [image src="images/basic1.jpg" text=" j^ i>=2 i<=N |
| | | | |
| | | | |
| N-+-********--j<=N |
| | ******** |
| | ******** |
| | ******** |
| 2-+-********--j>=2 |
| | | | |
| 0-+-+------+--->i |
| | | | |
| 0 2 N |
| "] |
| |
| Here, the iteration domain is specified thanks to a set of constraints. |
| When those constraints are affine and depend only on the outer loop |
| counters and some parameters, the set of constraints defines a |
| _polyhedron_ (more precisely this is a _Z-polyhedron_, but we use |
| _polyhedron_ for short). Hence the _polyhedral model_! |
| |
| To manipulate a set of affine constraints easily, we rely on a matrix |
| representation. To write it, we use the _homogeneous_ iteration vector: |
| it is simply the iteration vector with some additional dimensions to |
| represent the parameters and the constant. For instance for the |
| statement `S3', the iteration vector in homogeneous coordinates is `(i, |
| j, N, 1)' (we will now call it _iteration vector_ directly for short). |
| Then we write all the constraints as affine inequalities of the form |
| _affine constraint_ ` >= 0'. For instance for the statement `S3' the |
| set of constraints is: |
| |
| i - 2 >= 0 |
| -i + N >= 0 |
| j - 2 >= 0 |
| -j + N >= 0 |
| |
| Lastly, we translate the constraint system to the form *domain matrix*` |
| * '_iteration vector_` >= 0': |
| |
| [ 1 0 0 -2 ] [ i ] [ 0 ] |
| [ -1 0 1 0 ] [ j ] [ 0 ] |
| [ 0 1 0 -2 ] * [ N ] >= [ 0 ] |
| [ 0 -1 1 0 ] [ 1 ] [ 0 ] |
| |
| *The domain matrix will be used in all our tools to provide the |
| information on the iteration domain of a given statement (the iteration |
| vector is in general an implicit information).* |
| |
| |
| File: openscop.info, Node: Scattering Function, Next: Access Function, Prev: Iteration Domain, Up: Thinking in Polyhedra |
| |
| 2.2.2 Scattering Function |
| ------------------------- |
| |
| There is no ordering information inside the iteration domain: it only |
| describes the set of statement instances but *not* the order in which |
| they have to be executed relatively to each other. In the past the |
| lexicographic order of the iteration domain was considered, this is no |
| more true (especially when using CLooG). If we do not provide any |
| ordering information, this means that the statement instances may be |
| executed in any order (this is useful, e.g., to specify parallelism). |
| However, some statement instances may depend on some others and it may |
| be critical to enforce a given order (or non-order). Hence we need |
| another information. |
| |
| We call _scattering_ any kind of ordering information in the |
| polyhedral model. There exists many kind of ordering, such as |
| _allocation_, _scheduling_, _chunking_ etc. They are all expressed in |
| the same way, i.e., using _logical stamps_, but they may have different |
| semantics. |
| |
| In the case of *scheduling*, the logical stamps are logical dates |
| that express at which date a statement instance has to be executed. For |
| instance, let us consider the following three statements: |
| |
| x = a + b; // S1 |
| y = c + d; // S2 |
| z = a * b; // S3 |
| |
| The scheduling of a statement `S' is typically denoted by T_S. Let us |
| consider the following logical dates for each statement: |
| |
| T_S1 = 1 |
| T_S2 = 2 |
| T_S3 = 3 |
| |
| It means that statement `S3' has to be executed at logical date `1', |
| statement `S1' has to be executed at logical date `2' and statement |
| `S2' has to be executed at logical date `3'. The target code has to |
| respect this scheduling (the order of the logical dates), hence it |
| would look like the following where the variable `t' denotes the time: |
| |
| t = 1; |
| z = a * b; // S3 |
| t = 2; |
| x = a + b; // S1 |
| t = 3; |
| y = c + d; // S2 |
| |
| When some statements share the same logical date, this means that, once |
| the program reaches this logical date, the two statements can be |
| executed in any order, or better, in parallel. For instance let us |
| consider the following scheduling: |
| |
| T_S1 = 1 |
| T_S2 = 2 |
| T_S3 = 1 |
| |
| Statements `S1' and `S3' have the same logical date, moreover, `S2' has |
| a greater logical date than `S1' and `S3'. Hence the target code would |
| be: |
| |
| t = 1; |
| #pragma omp parallel sections |
| { |
| #pragma omp section |
| { |
| x = a + b; // S1 |
| } |
| #pragma omp section |
| { |
| z = a * b; // S3 |
| } |
| } |
| t = 2; |
| y = c + d; // S2 |
| |
| Logical dates may be multidimensional, as clocks: the first dimension |
| may correspond to days (most significant), the next one to hours (less |
| significant), the third to minutes and so on. For instance we can |
| consider the following multidimensional schedules for our example: |
| |
| T_S1 = (1,1) |
| T_S2 = (2,1) |
| T_S3 = (1,2) |
| |
| It is not very hard to decypher the meaning of such scheduling. |
| Because of the first dimension, statements `S1' and `S3' will be |
| executed before statement `S2' (`S1' and `S3' are executed at day 1, |
| while `S2' is executed at day 2). The second dimension is not really |
| useful there for `S2' because it is the only statement executed at day |
| 2. Nevertheless it allows to order `S1' and `S3' relatively to each |
| other since `S1' is executed at hour 1 of day 1 while `S3' is executed |
| at hour 2 of day 1. The corresponding target code is the following, |
| with some additional time variables for a better view of the ordering |
| (`t1' corresponds to the first time dimension, `t2' to the second one): |
| |
| t1 = 1; |
| t2 = 1; |
| x = a + b; // S1 |
| t2 = 2; |
| z = a * b; // S3 |
| t1 = 2; |
| t2 = 1; |
| y = c + d; // S2 |
| |
| In the case of *allocation* (in the literature we can find some |
| papers calling it _placement_), the logical stamp is a processor number |
| expressing on which processor a statement instance has to be executed. |
| Typically, allocations are written in the same way as scheduling. |
| Here, we denote it P_S for a statement `S'. For instance, let us |
| consider the following allocation: |
| |
| P_S1 = 1 |
| P_S2 = 2 |
| P_S3 = 1 |
| |
| The corresponding target code has to take into account that both |
| statements `S1' and `S3' have to be executed on the same processor |
| (they have the same logical number 1) and that statement `S2' has to be |
| executed on another processor (logical number 2). A possible target code |
| is the following: |
| |
| #pragma omp parallel sections |
| { |
| #pragma omp section |
| { |
| // Logical processor 1 |
| x = a + b; // S1 |
| z = a * b; // S3 |
| } |
| #pragma omp section |
| { |
| // Logical processor 2 |
| y = c + d; // S2 |
| } |
| } |
| |
| We can note that no order has been specified for the statements `S1' |
| and `S3' that are executed on the same processor. Hence any order is |
| satisfying. For sake of flexibility, it is usual to build a scattering |
| whose various dimensions do not have the same semantics. A typical |
| construction is _space/time mapping_ where the first `n' dimensions are |
| devoted to allocation, then the last `m' dimensions are devoted to |
| scheduling. Typically, space/time mapping is written in the same way as |
| scheduling. Here we denote it M_S for a statement `S'. For instance, |
| let us consider the following space/time mapping for our example where |
| one dimension is devoted to mapping and one dimension is devoted to |
| scheduling: |
| |
| M_S1 = (1,2) |
| M_S2 = (2,1) |
| M_S3 = (1,1) |
| |
| Here we have the same first dimension as the previous example, thus the |
| allocation of the statements to processors is the same. The second |
| dimension precises on a given processor at which logical date a |
| statement instance has to be executed. Here, the statement `S1' is |
| executed at day 2 on processor 1 while the statement `S3' is executed |
| at day 1 onto the same processor. It follows this space/time mapping |
| corresponds to the following target code (we added an additional |
| variable to represent the local logical clocks): |
| |
| #pragma omp parallel sections |
| { |
| #pragma omp section |
| { |
| // Logical processor 1 |
| t = 1; |
| z = a * b; // S3 |
| t = 2; |
| x = a + b; // S1 |
| } |
| #pragma omp section |
| { |
| // Logical processor 2 |
| t = 1; |
| y = c + d; // S2 |
| } |
| } |
| |
| For the same reason as discussed for iteration domains (*note |
| Iteration Domain::), it is not possible to define a scattering for each |
| statement instance, especially if the statement belongs to a (possibly |
| parametric) loop. The iteration vector fully defines an instance of a |
| given statement. Thus, a practical way to provide a scattering for each |
| instance of a given statement is to use a _function_ that depends on |
| the iteration vector. In this way the function may associate to each |
| iteration vector a different scattering. We call these functions |
| *scattering functions*. Scattering functions are _affine_ functions of |
| the outer loop counter and the global parameters. For instance, let us |
| consider the following source code: |
| |
| for (i = 2; i <= 4; i++) |
| for (j = 2; j <= 4; j++) |
| P[i+j] += A[i] + B[j]; // S4 |
| |
| The iteration domain of the statement `S4' is: |
| |
| D_S4= {(i,j) in Z^2 | 2 <= i <= 4 && 2 <= j <= 4 }. |
| |
| If you are still not comfortable with the mathematical notation, it |
| corresponds to the following graphical representation: |
| |
| [image src="images/basic2.jpg" text=" j^ i>=2 |
| | | i<=4 |
| | | | |
| 4-+-***--j<=4 |
| | *** |
| 2-+-***--j>=2 |
| | | | |
| 0-+-+-+--->i |
| | | | |
| 0 2 4 |
| "] |
| |
| The list of the statement instances of `S4' (the integer points of its |
| iteration domain) corresponds to the following iteration vectors: |
| |
| iteration vector |
| (2,2) |
| (2,3) |
| (2,4) |
| (3,2) |
| (3,3) |
| (3,4) |
| (4,2) |
| (4,3) |
| (4,4) |
| |
| Let us suppose we want to schedule the instances of the statement `S4' |
| (the integer points of its iteration domain) using the following |
| scheduling function: |
| |
| T_S4(i,j) = (j+2,3*i+j) |
| |
| We only need to apply the function to each iteration vector to find the |
| logical date of each instance: |
| |
| iteration vector logical date |
| (2,2) --> (4,8) |
| (2,3) --> (5,9) |
| (2,4) --> (6,10) |
| (3,2) --> (4,11) |
| (3,3) --> (5,12) |
| (3,4) --> (6,13) |
| (4,2) --> (4,14) |
| (4,3) --> (5,15) |
| (4,4) --> (6,16) |
| |
| The polyhedral model users do not have to take care about the |
| generation of a target code that respects the scattering: the CLooG(1) |
| tool is there to solve the problem quite easily. For the previous |
| example, the target code would be the following (`t1' and `t2' |
| correspond to the two dimensions of the logical date, the reader may |
| take care that this code actually implements the scattering function): |
| |
| for (t1 = 4; t1 <= 6; t1++) { |
| for (t2 = t1+4; t2 <= t1+10; t2++) { |
| if ((-t1+t2+2)%3 == 0) { |
| i = (-t1+t2+2)/3 ; |
| j = t1-2 ; |
| P[i+j] += A[i] + B[j]; // S4 |
| } |
| } |
| } |
| |
| Obviously with such a twisted scheduling, it is hard to see the |
| "meaning" of the transformation. To name any kind of program |
| transformation as a magic spell ("tile", "fuse", "skew"...) is an old |
| bad habit which is not relevant anymore in the polyhedral model: a |
| scheduling may be an arbitrary complex sequence of basic-old-good |
| transformations. Nevertheless it is most of the time quite easy to |
| translate well known transformations to schedules. For instance, let |
| us consider this new scheduling function: |
| |
| T_S4(i,j) = (j,i) |
| |
| Using CLooG, we can generate the target code: |
| |
| for (t1 = 2; t1 <= 4; t1++) { |
| for (t2 = 2; t2 <= 4; t2++) { |
| i = t2; |
| j = t1; |
| P[i+j] += A[i] + B[j]; // S4 |
| } |
| } |
| |
| It is easy to see (and analyze) that it corresponds to a classical |
| _loop interchange_ transformation. |
| |
| A very useful example of multi-dimensional scattering functions is |
| the *scheduling of the original program*. The method to compute it is |
| quite simple (*note Fea92::). The idea is to build an abstract syntax |
| tree of the program and to read the scheduling for each statement. For |
| instance, let us consider the following implementation of a Cholesky |
| factorization: |
| |
| /* A Cholesky factorization kernel. */ |
| for (i=1;i<=N;i++) { |
| for (j=1;j<=i-1;j++) { |
| a[i][i] -= a[i][j] ; // S1 |
| } |
| a[i][i] = sqrt(a[i][i]) ; // S2 |
| for (j=i+1;j<=N;j++) { |
| for (k=1;k<=i-1;k++) { |
| a[j][i] -= a[j][k]*a[i][k] ; // S3 |
| } |
| a[j][i] /= a[i][i] ; // S4 |
| } |
| } |
| } |
| |
| The corresponding abstract syntax tree is shown in the following |
| figure. It directly gives the scattering functions (schedules) for all |
| the statements of the program (just follow the paths). |
| |
| [image src="images/tree.jpg" text=" * |
| | |
| |0 |
| | |
| V |
| i |
| | |
| +-----+-----+ |
| | | | |
| |0 |1 |2 |
| | | | |
| V V V |
| j S2 j |
| | | |
| |0 +--+--+ |
| | | | |
| V |0 |1 |
| S1 | | |
| V V |
| k S4 |
| | |
| |0 |
| | |
| V |
| S3 |
| "] |
| |
| T_S1(i,j) = (0,i,0,j,0) |
| T_S2(i) = (0,i,1) |
| T_S3(i,j,k) = (0,i,2,j,0,k,0) |
| T_S4(i,j) = (0,i,2,j,1) |
| |
| These schedules depend on the iterators and give for each instance of |
| each statement a unique execution date. Using such scattering functions |
| allows CLooG to re-generate the input code. |
| |
| To easily manipulate the scattering function of any statement `S', we |
| translate it to the matrix form: T_S(_iteration vector_) ` = |
| '*scattering matrix*` * '_iteration vector_. For instance let us |
| consider again our previous example T_S4(i,j) = (j+2,3*i+j). We write |
| it in the following way: |
| [ i ] [ 0 1 2 ] [ i ] |
| T_S4([ j ]) = [ 3 1 0 ] * [ j ] |
| [ 1 ] [ 1 ] |
| |
| *The scattering matrix will be used in all our tools to provide the |
| information on the scattering of a given statement (the iteration |
| vector is in general an implicit information).* |
| |
| ---------- Footnotes ---------- |
| |
| (1) `http://www.cloog.org' |
| |
| |
| File: openscop.info, Node: Access Function, Prev: Scattering Function, Up: Thinking in Polyhedra |
| |
| 2.2.3 Access Function |
| --------------------- |
| |
| Before applying any transformation, it is essential to deeply analyze |
| both the original program and the transformation to ensure the |
| transformation does not imply any modification of the original program |
| semantics. In the polyhedral model, we are able to achieve an exact |
| analysis when all the memory accesses are made through arrays (note |
| that variables are a particular case of arrays since they are simply |
| arrays with only one memory location) with affine subscripts that depend |
| on outer loop counters and global parameters (note that _subscripts_ |
| are sometimes called _index_ or _accesses_ in the literature). |
| |
| For instance let us consider the array access `A[2*i+j][j][i+N]'. It |
| has three dimensions, each subscript dimension is an affine form of |
| some outer loop iterarors (`i' and `j') and global parameters (`N') |
| hence it corresponds to an acceptable array access to be analyzed in the |
| polyhedral model. |
| |
| Each array access can target a different memory cell depending on the |
| statement instance, i.e., depending on the iteration vector. Thus we |
| use access functions (or subscript functions, or index functions, as you |
| prefer to call it) depending on the iteration vector to describe an |
| array access. In our example, the access function would be written |
| F_A(i, j) = (2*i+j, j, i+N). |
| |
| To easily manipulate the access function of any array `A', we translate |
| it to the matrix form: F_A(_iteration vector_) ` = '*access matrix*` * |
| '_iteration vector_. For instance let us consider again our previous |
| example. We would write it in the following way: |
| [ i ] [ 2 1 0 0 ] [ i ] |
| F_A([ j ]) = [ 0 1 0 0 ] * [ j ] |
| [ N ] [ 1 0 1 0 ] [ N ] |
| [ 1 ] [ 1 ] |
| |
| *The access matrix will be used in all our tools to provide the |
| information on the access of a given statement (the iteration vector is |
| in general an implicit information).* |
| |
| |
| File: openscop.info, Node: What's Next?, Prev: Thinking in Polyhedra, Up: Polyhedral Representation |
| |
| 2.3 What's Next? |
| ================ |
| |
| OK, now you have an idea about how we do represent a program part in the |
| polyhedral model. You know the three main concepts, namely: domain, |
| scattering and access. What can you do with this?! Well, pretty much |
| anything related to code restructuring! The core idea will be to rely |
| on the mathematical representation to extract useful information about |
| your code (data reuse, parallelism...) and to generate a scattering to |
| benefit from the properties you analysed. However, OpenScop's |
| documentation is not the right place to learn at this (OpenScop is all |
| about representation, not about manipulation). Probably it is the right |
| time for you to have a look at: |
| * PoCC `http://pocc.sourceforge.net' |
| |
| * Pluto `http://pluto-compiler.sourceforge.net' |
| |
| Have fun :-) ! |
| |
| |
| File: openscop.info, Node: OpenScop Specification, Next: OpenScop Library, Prev: Polyhedral Representation, Up: Top |
| |
| 3 OpenScop Specification |
| ************************ |
| |
| OpenScop provides an explicit polyhedral representation of a static |
| control part. It has been designed by various polyhedral compilation |
| tool writers from various institutions. It builds on previous popular |
| polyhedral file and data structure formats (such as _.cloog_ and CLooG |
| data structures) to provide a unique, extensible format to most |
| polyhedral compilation tools. It is composed of two parts. The first |
| part, the so-called _core part_, is devoted to the polyhedral |
| representation of a SCoP. It contains what is strictly necessary to |
| build a complete source-to-source framework in the polyhedral model and |
| to output a semantically equivalent code for the SCoP, from analysis to |
| code generation. The second part of the format, the so-called |
| _extension part_, contains extensions to provide additional |
| informations to some tools. |
| |
| * Menu: |
| |
| * Preliminary Example:: |
| * OpenScop File Format Specification:: |
| * OpenScop Data Structure Specification:: |
| * Extensions:: |
| * History:: |
| |
| |
| File: openscop.info, Node: Preliminary Example, Next: OpenScop File Format Specification, Up: OpenScop Specification |
| |
| 3.1 Preliminary Example |
| ======================= |
| |
| OpenScop is a specification for representing static control program |
| parts in the polyhedral model. Thus, we can translate some code parts |
| to an equivalent OpenScop representation. As an example, let us |
| consider the following matrix-multiply kernel: |
| |
| #pragma scop |
| if (N > 0) { |
| for (i = 0; i < N; i++) { |
| for (j = 0; j < N; j++) { |
| C[i][j] = 0.0; |
| for (k = 0; k < N; k++) |
| C[i][j] = C[i][j] + A[i][k] * B[k][j]; |
| } |
| } |
| } |
| |
| The Clan(1) tool may be used to translate this code part to an |
| OpenScop representation automatically. The `#pragma scop' is used here |
| for Clan, but some other tool may not need it. Here is the result of the |
| translation to an OpenScop textual representation. |
| |
| |
| *DON'T PANIC* |
| |
| Explanations will follow and it is not as cryptic as it seems to be ! |
| |
| <OpenScop> |
| |
| # =============================================== Global |
| # Backend Language |
| C |
| |
| # Context |
| CONTEXT |
| 1 3 0 0 0 1 |
| # e/i | N | 1 |
| 1 1 -1 ## N-1 >= 0 |
| |
| # Parameter names are provided |
| 1 |
| # Parameter names |
| <strings> |
| N |
| </strings> |
| |
| # Number of statements |
| 2 |
| |
| # =============================================== Statement 1 |
| # Number of relations describing the statement |
| 3 |
| |
| # ---------------------------------------------- 1.1 Domain |
| DOMAIN |
| 4 5 2 0 0 1 |
| # e/i | i j | N | 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 |
| |
| # ---------------------------------------------- 1.2 Scattering |
| SCATTERING |
| 5 10 5 2 0 1 |
| # e/i| s1 s2 s3 s4 s5 | i j | N | 1 |
| 0 -1 0 0 0 0 0 0 0 0 ## s1 = 0 |
| 0 0 -1 0 0 0 1 0 0 0 ## s2 = i |
| 0 0 0 -1 0 0 0 0 0 0 ## s3 = 0 |
| 0 0 0 0 -1 0 0 1 0 0 ## s4 = j |
| 0 0 0 0 0 -1 0 0 0 0 ## s5 = 0 |
| |
| # ---------------------------------------------- 1.3 Access |
| WRITE |
| 3 8 3 2 0 1 |
| # e/i| Arr [1] [2] | i j | N | 1 |
| 0 -1 0 0 0 0 0 1 ## C |
| 0 0 -1 0 1 0 0 0 ## [i] |
| 0 0 0 -1 0 1 0 0 ## [j] |
| |
| # ---------------------------------------------- 1.4 Body |
| # Statement body is provided |
| 1 |
| # Statement body |
| <body> |
| # Number of original iterators |
| 2 |
| # Original iterator names |
| i j |
| # Statement body expression |
| C[i][j] = 0.0; |
| </body> |
| |
| # =============================================== Statement 2 |
| # Number of relations describing the statement |
| 5 |
| |
| # ---------------------------------------------- 2.1 Domain |
| DOMAIN |
| 6 6 3 0 0 1 |
| # e/i| i j k | N | 1 |
| 1 1 0 0 0 0 ## i >= 0 |
| 1 -1 0 0 1 -1 ## -i+N-1 >= 0 |
| 1 0 1 0 0 0 ## j >= 0 |
| 1 0 -1 0 1 -1 ## -j+N-1 >= 0 |
| 1 0 0 1 0 0 ## k >= 0 |
| 1 0 0 -1 1 -1 ## -k+N-1 >= 0 |
| |
| # ---------------------------------------------- 2.2 Scattering |
| SCATTERING |
| 7 13 7 3 0 1 |
| # e/i| s1 s2 s3 s4 s5 s6 s7 | i j k | N | 1 |
| 0 -1 0 0 0 0 0 0 0 0 0 0 0 ## s1 = 0 |
| 0 0 -1 0 0 0 0 0 1 0 0 0 0 ## s2 = i |
| 0 0 0 -1 0 0 0 0 0 0 0 0 0 ## s3 = 0 |
| 0 0 0 0 -1 0 0 0 0 1 0 0 0 ## s4 = j |
| 0 0 0 0 0 -1 0 0 0 0 0 0 1 ## s5 = 1 |
| 0 0 0 0 0 0 -1 0 0 0 1 0 0 ## s6 = k |
| 0 0 0 0 0 0 0 -1 0 0 0 0 0 ## s7 = 0 |
| |
| # ---------------------------------------------- 2.3 Access |
| WRITE |
| 3 9 3 3 0 1 |
| # e/i| Arr [1] [2] | i j k | N | 1 |
| 0 -1 0 0 0 0 0 0 1 ## C |
| 0 0 -1 0 1 0 0 0 0 ## [i] |
| 0 0 0 -1 0 1 0 0 0 ## [j] |
| |
| READ |
| 3 9 3 3 0 1 |
| # e/i| Arr [1] [2] | i j k | N | 1 |
| 0 -1 0 0 0 0 0 0 1 ## C |
| 0 0 -1 0 1 0 0 0 0 ## [i] |
| 0 0 0 -1 0 1 0 0 0 ## [j] |
| |
| READ |
| 3 9 3 3 0 1 |
| # e/i| Arr [1] [2] | i j k | N | 1 |
| 0 -1 0 0 0 0 0 0 2 ## A |
| 0 0 -1 0 1 0 0 0 0 ## [i] |
| 0 0 0 -1 0 0 1 0 0 ## [k] |
| |
| READ |
| 3 9 3 3 0 1 |
| # e/i| Arr [1] [2] | i j k | N | 1 |
| 0 -1 0 0 0 0 0 0 3 ## B |
| 0 0 -1 0 0 0 1 0 0 ## [k] |
| 0 0 0 -1 0 1 0 0 0 ## [j] |
| |
| # ---------------------------------------------- 2.4 Body |
| # Statement body is provided |
| 1 |
| # Statement body |
| <body> |
| # Number of original iterators |
| 3 |
| # Original iterator names |
| i j k |
| # Statement body expression |
| C[i][j] = C[i][j] + A[i][k] * B[k][j]; |
| </body> |
| |
| # =============================================== Extensions |
| <comment> |
| May the power of the polyhedral model be with you. |
| </comment> |
| |
| </OpenScop> |
| |
| We will not describe here precisely the structure and the components |
| of this output, this is described in depth in a further section (*note |
| OpenScop File Format Specification::). This format has been designed to |
| be a possible input or output file format of most of polyhedral |
| compilation tools. If you read the description of the polyhedral |
| representation of programs, you should already feel familiar with this |
| file format (*note Polyhedral Representation::). |
| |
| ---------- Footnotes ---------- |
| |
| (1) `http://www.lri.fr/~bastoul/development/clan/' |
| |
| |
| File: openscop.info, Node: OpenScop File Format Specification, Next: OpenScop Data Structure Specification, Prev: Preliminary Example, Up: OpenScop Specification |
| |
| 3.2 OpenScop File Format Specification |
| ====================================== |
| |
| * Menu: |
| |
| * Relations:: |
| * Generics:: |
| |
| The following grammar describes the structure of the OpenScop file |
| format where terminals are preceeded by "_". Except stated otherwise, |
| there can be at most one terminal per line in the file. Moreover, each |
| line may finish with a comment, starting by the `#' character. Each |
| relevant part will be explained in more details momentarily: |
| |
| OpenScop ::= Start_tag Data End_tag |
| Start_tag ::= "<OpenScop>" |
| End_tag ::= "</OpenScop>" |
| Data ::= Context Statements Extension_list |
| Context ::= Language Parameter_Domain Parameters |
| Statements ::= Nb_statements Statement_list |
| Statement_list ::= Statement Statement_list | (void) |
| Relation_list ::= _Relation Relation_list | (void) |
| Extension_list ::= _Generic Extension_list | (void) |
| Statement ::= Statement_relations Body |
| Body ::= "0" | "1" Body_information |
| Parameters ::= "0" | "1" Parameter_information |
| Statement_relations ::= Nb_relations Relation_List |
| Parameter_domain ::= _Relation |
| Language ::= _String |
| Nb_Relations ::= _Integer |
| Parameter_information ::= _Generic |
| Body_information ::= _Generic |
| |
| The `Context' and the `Statements' parts compose the _core part_, |
| i.e., what is strictly necessary to build a complete source to source |
| framework based on OpenSCop: |
| * `Context' represents the global information of the SCoP. It |
| consists on the target language, the global constraints on the |
| parameters and optionally the parameter information which may be |
| necessary for the code generation process. The constraints |
| on the parameters are represented as a relation (*note |
| Context Domain Relation::). The parameter information is |
| optional. It is preceded by a boolean which precises |
| whether it is provided or not. It is a generic information |
| (*note Generics::), a `strings' (*note Strings Generic::) |
| for instance. |
| |
| * `Statements' represents the information about the statements. |
| `Nb_statements' is the number of statements in the SCoP, |
| i.e. the number of `Statement' items in the `Statement_list'. |
| `Statement' represents the information on a given statement. |
| To each statement is associated a list of relations and, |
| optionaly, a body. The list of relations may include one |
| iteration domain (*note Iteration Domain Relation::), one |
| scattering relation (*note Scattering Relation::) and |
| several access relations (*note Access Relation::). There |
| is no mandatory ordering, but for consistency reason it would |
| be much appreciated that iteration domain comes first (if present) |
| then scattering (if present), then accesses (if present). |
| The statement body is an optional information. It is preceded |
| by a boolean which precises whether it is provided or not. |
| It is a generic information (*note Generics::), a `body' |
| (*note Body Generic::) for instance. |
| |
| The `Extension_list' represents the _extension part_ and may contain |
| an arbitrary number of generic informations (*note Generics::). Few |
| examples of possible extensions are presented in a further section |
| (*note Extensions::). |
| |
| As shown by the grammar, the input file describes the various pieces |
| of information based on strings, integers, _relations_ and _generics_. |
| Relations and Generics are specific to OpenScop and are described in |
| depth in the following Sections (*note Relations:: and *note |
| Generics::). |
| |
| |
| File: openscop.info, Node: Relations, Next: Generics, Up: OpenScop File Format Specification |
| |
| 3.2.1 Relations |
| --------------- |
| |
| * Menu: |
| |
| * Iteration Domain Relation:: |
| * Context Domain Relation:: |
| * Scattering Relation:: |
| * Access Relation:: |
| |
| _Relations_ are the essence of the OpenScop format and contain the |
| "polyhedral" information. They are used to describe either an iteration |
| domain, or a context domain, or a scattering or a memory access. |
| |
| We use the relation term as a shortcut to denote a union of convex |
| relations, each element of the union being described by a set of |
| constraints in an extended PolyLib format (*note Wil93::). The number |
| of elements in the union is given by an integer on the first line, |
| optionally followed by a comment starting with `#'. This number of |
| elements can be omitted when there is only one element. Each element |
| in the union has the following syntax: |
| |
| 1. Some optional comment lines beginning with `#'. |
| |
| 2. A line with the type of the relation, possibly followed by |
| comments. The type can be one of the following: |
| * `UNDEFINED': generic relation, |
| |
| * `CONTEXT': for context information, |
| |
| * `DOMAIN': for iteration domains, |
| |
| * `SCATTERING': for scattering relation, |
| |
| * `READ': for read accesses, |
| |
| * `WRITE': for write accesses, |
| |
| * `MAY_WRITE': for may-write accesses, |
| |
| 3. A line with 6 numbers, possibly followed by comments: |
| 1. the number of rows of the constraint matrix, |
| |
| 2. the number of columns of the constraint matrix, |
| |
| 3. the number of _output dimensions_, |
| |
| 4. the number of _input dimension_, |
| |
| 5. the number of _local dimensions_ (existentially |
| quantified dimensions), |
| |
| 6. the number of _parameters_. |
| The sum of the last four numbers should be equal to the |
| number of columns minus two. The remaining two columns are |
| the equality/inequality indicator and the constant term. The |
| number of parameters should be the same for all relations in |
| the entire OpenScop file or data structure. |
| |
| 4. The constraint rows. Each row corresponds to a constraint the |
| relation has to satisfy. Each row must be on a single line and is |
| possibly followed by comments. The constraint is an equality |
| p(x) = 0 if the first element is 0, an inequality p(x) \geq |
| 0 if the first element is 1. The next elements are the |
| coefficients of the output dimensions, followed by |
| coefficients of the input dimensions, the existentially |
| quantified dimensions and finally the parameters. The last |
| element is the constant term. |
| |
| This representation is the basis for several purposes. Examples for |
| iteration domains (*note Iteration Domain Relation::), context domains |
| (*note Context Domain Relation::), scattering relations (*note |
| Scattering Relation::) and access relations (*note Access Relation::) |
| are provided in further sections. |
| |
| |
| File: openscop.info, Node: Iteration Domain Relation, Next: Context Domain Relation, Up: Relations |
| |
| 3.2.1.1 Iteration Domain Relation |
| ................................. |
| |
| Iteration domain represents the set of instances of the corresponding |
| statement. OpenScop iteration domains are represented as relations |
| with the following conventions: |
| * the type is `DOMAIN', |
| |
| * there is 0 input dimension, |
| |
| * loop iterators correspond to output dimensions. |
| |
| For instance, assuming that `i', `j' and `k' are the loop iterators and |
| `M' and `N' are the parameters, the domain defined by the following |
| constraints : |
| |
| -i + M >= 0 |
| -j + N >= 0 |
| i + j - k >= 0 |
| |
| can be written in the input file as follows: |
| |
| # This is an iteration domain |
| DOMAIN |
| 1 # Number of relations in the union |
| 3 7 3 0 0 2 # 3 rows, 7 cols: 3 output dims and 2 params |
| # e/i| i j k | M N | 1 |
| 1 -1 0 0 1 0 0 # -i + M >= 0 |
| 1 0 -1 0 0 1 0 # -j + N >= 0 |
| 1 1 1 -1 0 0 0 # i + j - k >= 0 |
| |
| Equivalently, it can be written in the following way as the number of |
| relations in the union can be omitted if it is 1: |
| |
| # This is an iteration domain |
| DOMAIN |
| 3 7 3 0 0 2 # 3 rows, 7 cols: 3 output dims and 2 params |
| # e/i| i j k | M N | 1 |
| 1 -1 0 0 1 0 0 # -i + M >= 0 |
| 1 0 -1 0 0 1 0 # -j + N >= 0 |
| 1 1 1 -1 0 0 0 # i + j - k >= 0 |
| |
| As an example for unions, let us consider the following pseudo-code: |
| |
| for (i = 1; i <= N; i++) { |
| if ((i >= M) || (i <= 2*M)) |
| S1(i); |
| } |
| |
| The iteration domain of `S1' can be divided into two relations and |
| written in the OpenScop file as follows: |
| |
| # This is an iteration domain |
| DOMAIN |
| 2 # Number of relations in the union |
| # Union part No.1 |
| 3 5 1 0 0 2 # 3 rows, 5 cols: 1 output dim and 2 params |
| # e/i| i | M N | 1 |
| 1 1 0 0 -1 # i >= 1 |
| 1 -1 0 1 0 # i <= N |
| 1 1 -1 0 0 # i >= M |
| # Union part No.2 |
| 3 5 1 0 0 2 # 3 rows, 5 cols: 1 output dim and 2 params |
| # e/i| i | M N | 1 |
| 1 1 0 0 -1 # i >= 1 |
| 1 -1 0 1 0 # i <= N |
| 1 -1 2 0 0 # i <= 2*M |
| |
| As an example for local dimensions (existentially quantified |
| dimensions), let us consider the following pseudo-code: |
| |
| for (i = 1; i <= N; i++) { |
| if ((i % 2) == 0) |
| S1(i); |
| } |
| |
| The iteration domain of `S1' is composed of all even integer values |
| between 1 and N. The "divisible by two" constraint can be expressed as |
| follows: there exists an integer `ld' such that `i = 2*ld'. We encode |
| this thanks to a new local dimension: |
| |
| # This is an iteration domain |
| DOMAIN |
| 3 5 1 0 1 1 # 3 rows, 5 cols: 1 output dim, 1 local dim, 1 param |
| # e/i| i |ld | N | 1 |
| 0 1 -2 0 0 # i = 2*ld |
| 1 1 0 0 1 # i >= 1 |
| 1 -1 0 1 0 # i <= N |
| |
| |
| File: openscop.info, Node: Context Domain Relation, Next: Scattering Relation, Prev: Iteration Domain Relation, Up: Relations |
| |
| 3.2.1.2 Context Domain Relation |
| ............................... |
| |
| The context domain is a particular case of iteration domain (*note |
| Iteration Domain Relation::) where there are only constraints about |
| parameters (no loop iterators). Hence it is the same as an iteration |
| domain, with the following conventions: |
| * the type is `CONTEXT', |
| |
| * there is 0 input dimension, |
| |
| * there is 0 output dimension. |
| |
| |
| File: openscop.info, Node: Scattering Relation, Next: Access Relation, Prev: Context Domain Relation, Up: Relations |
| |
| 3.2.1.3 Scattering Relation |
| ........................... |
| |
| Scattering relation maps an iteration domain to a logical time and/or |
| space (and/or) anything. OpenScop scattering information is |
| represented as relations (*note Relations::) with the following |
| conventions: |
| |
| * the type is `SCATTERING', |
| |
| * output dimensions correspond to scattering dimensions, |
| |
| * loop iterators correspond to input dimensions. |
| |
| As an example of a scattering relation and assuming that `i', `j' |
| and `k' are the loop iterators and `M' and `N' are the parameters, take |
| for instance: |
| T_{S}(i,j,k) = (j+2,3*i+j,k+N+1). |
| We can represent it in the following way: |
| |
| # A scattering relation |
| SCATTERING |
| # 3 rows, 10 columns: 3 scattering dimensions, 3 iterators, 2 parameters |
| 3 10 3 3 0 2 |
| # e/i|s1 s2 s3 | i j k | M N | 1 |
| 0 -1 0 0 0 1 0 0 0 2 # s1 = j+2 |
| 0 0 -1 0 3 1 0 0 0 0 # s2 = 3*i+j |
| 0 0 0 -1 0 0 1 0 1 1 # s3 = k+N+1 |
| |
| |
| File: openscop.info, Node: Access Relation, Prev: Scattering Relation, Up: Relations |
| |
| 3.2.1.4 Access Relation |
| ....................... |
| |
| Access relation maps an iteration domain to an array space. Each array |
| accessed in the SCoP has a unique identification number. OpenScop |
| relation information is represented as relations (*note Relations::) |
| with the following conventions: |
| |
| * the type is one of the following: |
| * `READ', for read accesses, |
| |
| * `WRITE', for write accesses, |
| |
| * `MAY_WRITE', for may write accesses, |
| |
| * output dimensions correspond to the array identifier and |
| dimensions, |
| |
| * the first output dimension corresponds to the array identifier, |
| |
| * the (i+1)th output dimension corresponds to the ith array |
| dimension (i>1), |
| |
| * loop iterators correspond to input dimensions. |
| |
| As an example of a scattering relation and assuming that `i', `j' |
| and `k' are the loop iterators and `M' and `N' are the parameters, let |
| us consider the array access `A[2*i+j][j][i+N]' (the identifier of `A' |
| is 42), and let us suppose this is a read access. Its representation |
| would be the following: |
| |
| # A read access relation |
| READ |
| # 4 rows, 11 columns: 4 array dimensions, 3 iterators, 2 parameters |
| 4 11 4 3 0 2 |
| # e/i|Arr [1] [2] [3]| i j k | M N | 1 |
| 0 -1 0 0 0 0 0 0 0 0 42 # A |
| 0 0 -1 0 0 2 1 0 0 0 0 # [2*i+j] |
| 0 0 0 -1 0 0 1 0 0 0 0 # [j] |
| 0 0 0 0 -1 1 0 0 0 1 0 # [i+N] |
| |
| To understand this representation, consider that OpenScop accesses |
| are general memory accesses and not array accesses. The memory is seen |
| as a big array `Mem' while usual array names correspond to the first |
| dimension. Hence our example translates to `Mem[42][2*i+j][j][i+N]'. |
| |
| Unions of access relations are allowed. In this case, each union |
| part must refer at the same array identifier, and the number of |
| dimensions must be consistent. |
| |
| |
| File: openscop.info, Node: Generics, Prev: Relations, Up: OpenScop File Format Specification |
| |
| 3.2.2 Generics |
| -------------- |
| |
| * Menu: |
| |
| * Strings Generic:: |
| * Body Generic:: |
| |
| _Generics_ represent any elaborated non-polyhedral information in the |
| OpenScop format. They are used to represent the parameter information, |
| the statement body information as well as the extensions. Each generic |
| information is delimited using XML-like tags corresponding to its URI |
| (Unique Resource Identifier), For instance, if the generic has the URI |
| `foo', the begin tag is `<foo>' and the end tag is `</foo>'). |
| |
| Two generics, namely `strings' (*note Strings Generic::) and `body' |
| (*note Body Generic::) are part of the OpenScop specification to |
| provide the minimum, stricly necessary information to build a complete |
| source-to-source polyhedral framework based on OpenScop. However, |
| generics can be basically _anything_ as long as they are properly |
| delimited. OpenScop implementations will simply ignore non-supported |
| generics and warn the user with the mention of the non-supported URIs. |
| Support of new generics will be added throught the extension mechanism. |
| |
| |
| File: openscop.info, Node: Strings Generic, Next: Body Generic, Up: Generics |
| |
| 3.2.2.1 Strings Generic |
| ....................... |
| |
| The purpose of the `strings' generic is to represent a list of textual |
| strings on one line (which may be used, e.g., to represent the list of |
| parameter names in the order used in the relation). Its URI is `strings' |
| and its file format respects the following grammar: |
| Strings_generic ::= "<strings>" Strings "</strings>" |
| Strings ::= _String String_list | (void) |
| |
| A possible example of textual `strings' is the following: |
| <strings> |
| Not one sentence but 6 strings! |
| </strings> |
| |
| |
| File: openscop.info, Node: Body Generic, Prev: Strings Generic, Up: Generics |
| |
| 3.2.2.2 Body Generic |
| .................... |
| |
| The purpose of the `body' generic is to represent the textual |
| information about a statement. It contains the number of original |
| iterators on the first line, the list of original iterators on the |
| second line (the loop counters of the statement surrounding loops in |
| the original program) and the original textual body expression on the |
| third line. Its URI is `body' and its file format respects the |
| following grammar (the `String' rule is reused, *note Strings |
| Generic::): |
| Body_generic ::= "<body>" Body "</body>" |
| Body ::= Nb_iterators Iterator_list Expression |
| Nb_iterators ::= _Integer |
| Iterator_list ::= Strings |
| Expression ::= Strings |
| |
| A possible example of textual `body' is the following: |
| <body> |
| # Number of original iterators |
| 2 |
| # Original iterators |
| i j |
| # Original statement expression |
| A[i+j] += B[i] * C[j]; |
| </body> |
| |
| |
| File: openscop.info, Node: OpenScop Data Structure Specification, Next: Extensions, Prev: OpenScop File Format Specification, Up: OpenScop Specification |
| |
| 3.3 OpenScop Data Structure Specification |
| ========================================= |
| |
| * Menu: |
| |
| * osl_relation_t:: |
| * osl_relation_list_t:: |
| * osl_interface_t:: |
| * osl_generic_t:: |
| * osl_strings_t:: |
| * osl_body_t:: |
| * osl_statement_t:: |
| * osl_scop_t:: |
| |
| The OpenScop specification offers a small set of C data structures |
| devoted to represent a SCoP in memory in a convenient way. Using them |
| in some tool or library may greatly facilitate its interaction with |
| other tools or libraries which rely on this representation as well. |
| Every field may not be useful for a given tool or library. A general |
| rule for all the data structure is that a `NULL' pointer or a -1 |
| integer value means the information is not present. Contrary to |
| engineering time, memory is cheap today, so it's much probably not a |
| big deal that some fields are left empty. Every field may not be enough |
| for a given tool or library. In this case it is much recommended to |
| provide a new extension which may be reused by other users (*note |
| Extensions::). |
| |
| Each tool or library may have its own implementation of the OpenScop |
| data structures. The type names should not be the same as those provided |
| as an example here (they correspond to the OpenScop Library |
| implementation). The names of the fields, and their ordering, should |
| however be the same. In this way, the interaction between tools and |
| libraries should be as simple as a cast. |
| |
| Before reading at the OpenScop data structures, it is much |
| recommended to read at the OpenScop file format description, as it is |
| quite close to this representation (*note OpenScop File Format |
| Specification::). |
| |
| |
| File: openscop.info, Node: osl_relation_t, Next: osl_relation_list_t, Up: OpenScop Data Structure Specification |
| |
| 3.3.1 osl_relation_t |
| -------------------- |
| |
| struct osl_relation { |
| int type; /* What this relation is encoding */ |
| int precision; /* Precision of the matrix elements */ |
| int nb_rows; /* Number of rows */ |
| int nb_columns; /* Number of columns */ |
| int nb_output_dims; /* Number of output dimensions */ |
| int nb_input_dims; /* Number of input dimensions */ |
| int nb_local_dims; /* Number of local dimensions */ |
| int nb_parameters; /* Number of parameters */ |
| void ** m; /* Matrix of constraints */ |
| struct osl_relation * next; /* Next relation in the union */ |
| }; |
| typedef struct osl_relation osl_relation_t; |
| typedef struct osl_relation * osl_relation_p; |
| |
| The `osl_relation_t' structure stores a part of an union of relations. |
| A union of relation is a `NULL'-terminated linked list of union parts |
| (`next' field). The `type' field may provide some information about |
| what the relation is encoding: |
| * -1: undefined (`OSL_UNDEFINED'), |
| |
| * 2: context domain (`OSL_TYPE_CONTEXT'), |
| |
| * 3: iteration domain (`OSL_TYPE_DOMAIN'), |
| |
| * 4: scattering relation (`OSL_TYPE_SCATTERING'), |
| |
| * 6: read access relation (`OSL_TYPE_READ'), |
| |
| * 7: write access relation (`OSL_TYPE_WRITE'), |
| |
| * 8: may write access relation (`OSL_TYPE_MAY_WRITE'), |
| The various numbers provide the details on the relation itself |
| (*note Relations::) while the `m' field points to the constraint |
| matrix. The precision of the constraint matrix elements is provided by |
| the `precision' field. It can take the following values: |
| * 32: 32 bits precision, elements are `long int' |
| (`OSL_PRECISION_SP'), |
| |
| * 64: 64 bits precision, elements are `long long int' |
| (`OSL_PRECISION_DP'), |
| |
| * 0: multiple precision, elements are GNU GMP Library's |
| `mpz_t' (`OSL_PRECISION_MP'). |
| |
| |
| File: openscop.info, Node: osl_relation_list_t, Next: osl_interface_t, Prev: osl_relation_t, Up: OpenScop Data Structure Specification |
| |
| 3.3.2 osl_relation_list_t |
| ------------------------- |
| |
| struct osl_relation_list { |
| osl_relation_p elt; /* Element of the list */ |
| struct osl_relation_list * next; /* Next element of the list */ |
| }; |
| typedef struct osl_relation_list osl_relation_list_t; |
| typedef struct osl_relation_list * osl_relation_list_p; |
| |
| The `osl_relation_list_t' structure is a `NULL'-terminated linked list |
| of `osl_relation_t' data structures. `elt' is a relation element of |
| the list and `next' is the pointer to the next element of the list. |
| |
| |
| File: openscop.info, Node: osl_interface_t, Next: osl_generic_t, Prev: osl_relation_list_t, Up: OpenScop Data Structure Specification |
| |
| 3.3.3 osl_interface_t |
| --------------------- |
| |
| typedef void (*osl_idump_f) (FILE *, void *, int); |
| typedef char * (*osl_sprint_f)(void *); |
| typedef void * (*osl_sread_f) (char *); |
| typedef void * (*osl_malloc_f)(); |
| typedef void (*osl_free_f) (void *); |
| typedef void * (*osl_clone_f) (void *); |
| typedef int (*osl_equal_f) (void *, void *); |
| |
| struct osl_interface { |
| char * URI; /* Unique interface identifier string */ |
| osl_idump_f idump; /* Pointer to the idump function */ |
| osl_sprint_f sprint; /* Pointer to the sprint function */ |
| osl_sread_f sread; /* Pointer to the sread function */ |
| osl_malloc_f malloc; /* Pointer to the malloc function */ |
| osl_free_f free; /* Pointer to the free function */ |
| osl_clone_f clone; /* Pointer to the clone function */ |
| osl_equal_f equal; /* Pointer to the equal function */ |
| struct osl_interface * next; /* Next interface in the list */ |
| }; |
| typedef struct osl_interface osl_interface_t; |
| typedef struct osl_interface * osl_interface_p; |
| |
| The `osl_interface_t' structure represents a node in a |
| `NULL'-terminated list of interfaces. Each node stores the _interface_ |
| of a generic OpenScop object, i.e., its unique name (`URI') and the |
| function pointers to all the base functions it has to provide. |
| Extension providers will find information relative to those functions |
| in the OpenScop Library description (*note Base Functions::) and the |
| section dedicated to writing extensions (*note Extension Development::). |
| |
| |
| File: openscop.info, Node: osl_generic_t, Next: osl_strings_t, Prev: osl_interface_t, Up: OpenScop Data Structure Specification |
| |
| 3.3.4 osl_generic_t |
| ------------------- |
| |
| struct osl_generic { |
| void * data; /* Pointer to some data */ |
| osl_interface_p interface; /* Interface to work with the data */ |
| struct osl_generic * next; /* Pointer to the next generic */ |
| }; |
| typedef struct osl_generic osl_generic_t; |
| typedef struct osl_generic * osl_generic_p; |
| |
| The `osl_generic_t' structure represents a node in a `NULL'-terminated |
| list of generic elements. It stores some data and operations with no |
| pre-defined type. The information is accessible through the `data' |
| pointer while the type and operations are accessible through the |
| `interface' pointer. It is used to represent data that are allowed to |
| differ in implementations, such as symbols and extensions. |
| |
| |
| File: openscop.info, Node: osl_strings_t, Next: osl_body_t, Prev: osl_generic_t, Up: OpenScop Data Structure Specification |
| |
| 3.3.5 osl_strings_t |
| ------------------- |
| |
| struct osl_string { |
| char ** string; /* NULL-terminated array of strings */ |
| }; |
| typedef struct osl_strings osl_strings_t; |
| typedef struct osl_strings * osl_strings_p; |
| |
| The `osl_strings_t' structure represents a NULL-terminated list of C |
| character strings. It is encapsulated into a structure to allow its |
| manipulation through a generic type. |
| |
| |
| File: openscop.info, Node: osl_body_t, Next: osl_statement_t, Prev: osl_strings_t, Up: OpenScop Data Structure Specification |
| |
| 3.3.6 osl_body_t |
| ---------------- |
| |
| struct osl_body { |
| osl_strings_p iterators; /* Original iterators */ |
| osl_strings_p expression; /* Original statement expression */ |
| }; |
| typedef struct osl_body osl_body_t; |
| typedef struct osl_body * osl_body_p; |
| |
| The `osl_body_t' structure stores a statement body in a textual form. |
| The complete original expression (directly copy-pasted from the |
| original code) is in the expression field while the textual forms of |
| the original iterators are in the iterators field. They may be used for |
| substitutions inside the expression. |
| |
| |
| File: openscop.info, Node: osl_statement_t, Next: osl_scop_t, Prev: osl_body_t, Up: OpenScop Data Structure Specification |
| |
| 3.3.7 osl_statement_t |
| --------------------- |
| |
| struct osl_statement { |
| osl_relation_p domain; /* Iteration domain */ |
| osl_relation_p scattering; /* Scattering relation */ |
| osl_relation_list_p access; /* List of array access relations */ |
| osl_generic_p body; /* Original statement body */ |
| void * usr; /* A user-defined field */ |
| struct osl_statement * next; /* Next statement in the list */ |
| }; |
| typedef struct osl_statement osl_statement_t; |
| typedef struct osl_statement * osl_statement_p; |
| |
| The `osl_statement_t' structure represents a node in a |
| `NULL'-terminated linked list of statements. Each node contains the |
| useful information 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). The |
| iteration domain and the scattering are represented using an |
| `osl_relation_p' structure while the accesses are using a list of |
| relations: one for each memory access in the statement. The `body' |
| field should provide information about the statement body (since it has |
| a generic type, the specification is not strict about how it is used), |
| e.g., using the `osl_body_t' data structure (*note osl_body_t::). It |
| is also possible to use the `usr' field, but it has to be totally |
| managed by the user. |
| |
| |
| File: openscop.info, Node: osl_scop_t, Prev: osl_statement_t, Up: OpenScop Data Structure Specification |
| |
| 3.3.8 osl_scop_t |
| ---------------- |
| |
| struct osl_scop { |
| int version; /* Version of the data structure */ |
| char * language; /* Target language */ |
| osl_relation_p context; /* Constraints on the parameters */ |
| osl_generic_p parameters; /* Information about parameters */ |
| osl_statement_p statement; /* Statement list */ |
| osl_interface_p registry; /* Registered extension interfaces */ |
| osl_generic_p extension; /* Extension list */ |
| void * usr; /* A user-defined field */ |
| struct osl_scop * next; /* Next scop in the list */ |
| }; |
| typedef struct osl_scop osl_scop_t; |
| typedef struct osl_scop * osl_scop_p; |
| |
| `osl_scop_t' represents a node in a `NULL'-terminated list of scops. It |
| stores the useful informations of a static control part of a program to |
| process it within a polyhedral framework. To prepare OpenScop |
| specification evolution, the `version' field tells the version of the |
| data structure. It should be set to 1 for now (and hopefully a very, |
| very, long time). First, it contains the informations about the |
| context. The target language in expressed in the `language' field. The |
| constraints on the global parameters are detailed in the `context' |
| field. The `paremeters' field should provide information about the |
| parameters (since it has a generic type, the specification is not strict |
| about how it is used), e.g., using the `osl_strings_t' data structure |
| (*note osl_strings_t::). Finally, it contains the list of statements |
| `statement', the list of registered interfaces for generic types |
| `registry' and the list of extentions `extension'. It is also possible |
| to use the `usr' field, but it has to be totally managed by the user. |
| |
| As an example, let us consider again the matrix multiply program |
| (*note Preliminary Example::). The next figure gives a possible |
| representation in memory for this SCoP thanks to the OpenScop data |
| structures (it has been actually printed by the `osl_scop_dump' |
| function), note that symbols like parameters, original iterators and |
| statement expression are represented with an `osl_strings_t' which does |
| not belong to the specification but to the OpenScop Library |
| implementation: |
| |
| +-- osl_scop_t |
| | | |
| | Version: 1 |
| | | |
| | Language: C |
| | | |
| | +-- osl_relation_t (CONTEXT, 32 bits) |
| | | 1 3 0 0 0 1 |
| | | [ 1 1 -1 ] |
| | | |
| | +-- osl_generic_t |
| | | | |
| | | +-- osl_interface_t: URI = strings |
| | | | |
| | | +-- osl_strings_t: N |
| | | | |
| | | |
| | +-- osl_statement_t (S1) |
| | | | |
| | | +-- osl_relation_t (DOMAIN, 32 bits) |
| | | | 4 5 2 0 0 1 |
| | | | [ 1 1 0 0 0 ] |
| | | | [ 1 -1 0 1 -1 ] |
| | | | [ 1 0 1 0 0 ] |
| | | | [ 1 0 -1 1 -1 ] |
| | | | |
| | | +-- osl_relation_t (SCATTERING, 32 bits) |
| | | | 5 10 5 2 0 1 |
| | | | [ 0 -1 0 0 0 0 0 0 0 0 ] |
| | | | [ 0 0 -1 0 0 0 1 0 0 0 ] |
| | | | [ 0 0 0 -1 0 0 0 0 0 0 ] |
| | | | [ 0 0 0 0 -1 0 0 1 0 0 ] |
| | | | [ 0 0 0 0 0 -1 0 0 0 0 ] |
| | | | |
| | | +-- osl_relation_list_t |
| | | | | |
| | | | +-- osl_relation_t (WRITE, 32 bits) |
| | | | | 3 8 3 2 0 1 |
| | | | | [ 0 -1 0 0 0 0 0 1 ] |
| | | | | [ 0 0 -1 0 1 0 0 0 ] |
| | | | | [ 0 0 0 -1 0 1 0 0 ] |
| | | | | |
| | | | |
| | | +-- osl_generic_t |
| | | | | |
| | | | +-- osl_interface_t: URI = body |
| | | | | |
| | | | +-- osl_strings_t: i j |
| | | | | |
| | | | +-- osl_strings_t: C[i][j] = 0.0; |
| | | | | |
| | | | |
| | | V |
| | | osl_statement_t (S2) |
| | | | |
| | | +-- osl_relation_t (DOMAIN, 32 bits) |
| | | | 6 6 3 0 0 1 |
| | | | [ 1 1 0 0 0 0 ] |
| | | | [ 1 -1 0 0 1 -1 ] |
| | | | [ 1 0 1 0 0 0 ] |
| | | | [ 1 0 -1 0 1 -1 ] |
| | | | [ 1 0 0 1 0 0 ] |
| | | | [ 1 0 0 -1 1 -1 ] |
| | | | |
| | | +-- osl_relation_t (SCATTERING, 32 bits) |
| | | | 7 13 7 3 0 1 |
| | | | [ 0 -1 0 0 0 0 0 0 0 0 0 0 0 ] |
| | | | [ 0 0 -1 0 0 0 0 0 1 0 0 0 0 ] |
| | | | [ 0 0 0 -1 0 0 0 0 0 0 0 0 0 ] |
| | | | [ 0 0 0 0 -1 0 0 0 0 1 0 0 0 ] |
| | | | [ 0 0 0 0 0 -1 0 0 0 0 0 0 1 ] |
| | | | [ 0 0 0 0 0 0 -1 0 0 0 1 0 0 ] |
| | | | [ 0 0 0 0 0 0 0 -1 0 0 0 0 0 ] |
| | | | |
| | | +-- osl_relation_list_t |
| | | | | |
| | | | +-- osl_relation_t (WRITE, 32 bits) |
| | | | | 3 9 3 3 0 1 |
| | | | | [ 0 -1 0 0 0 0 0 0 1 ] |
| | | | | [ 0 0 -1 0 1 0 0 0 0 ] |
| | | | | [ 0 0 0 -1 0 1 0 0 0 ] |
| | | | | |
| | | | V |
| | | | osl_relation_list_t |
| | | | | |
| | | | +-- osl_relation_t (READ, 32 bits) |
| | | | | 3 9 3 3 0 1 |
| | | | | [ 0 -1 0 0 0 0 0 0 1 ] |
| | | | | [ 0 0 -1 0 1 0 0 0 0 ] |
| | | | | [ 0 0 0 -1 0 1 0 0 0 ] |
| | | | | |
| | | | V |
| | | | osl_relation_list_t |
| | | | | |
| | | | +-- osl_relation_t (READ, 32 bits) |
| | | | | 3 9 3 3 0 1 |
| | | | | [ 0 -1 0 0 0 0 0 0 2 ] |
| | | | | [ 0 0 -1 0 1 0 0 0 0 ] |
| | | | | [ 0 0 0 -1 0 0 1 0 0 ] |
| | | | | |
| | | | V |
| | | | osl_relation_list_t |
| | | | | |
| | | | +-- osl_relation_t (READ, 32 bits) |
| | | | | 3 9 3 3 0 1 |
| | | | | [ 0 -1 0 0 0 0 0 0 3 ] |
| | | | | [ 0 0 -1 0 0 0 1 0 0 ] |
| | | | | [ 0 0 0 -1 0 1 0 0 0 ] |
| | | | | |
| | | | |
| | | +-- osl_generic_t |
| | | | | |
| | | | +-- osl_interface_t: URI = body |
| | | | | |
| | | | +-- osl_strings_t: i j k |
| | | | | |
| | | | +-- osl_strings_t: C[i][j] = C[i][j] + A[i][k]*B[k][j]; |
| | | | | |
| | | | |
| | | |
| | +-- NULL interface |
| | | |
| | +-- NULL generic |
| | | |
| | |
| |
| |
| File: openscop.info, Node: Extensions, Next: History, Prev: OpenScop Data Structure Specification, Up: OpenScop Specification |
| |
| 3.4 Extensions |
| ============== |
| |
| The core part of the OpenScop representation embeds what is strictly |
| necessary to build a complete source-to-source polyhedral framework. |
| However it may not be enough. Hence, OpenScop offers a very flexible |
| extension part. Actually, the only constraint to build an extension is |
| to request the OpenScop maintainer for a unique extension name: its URI |
| (ask the maintainer through the OpenScop mailing list |
| <openscop-development@googlegroups.com>). |
| |
| The policy to support extensions is the following and is pretty |
| simple: an OpenScop implementation is not required to support any |
| extension. If it is processing an OpenScop file or data structure which |
| contains an extension which is not supported, it must (1) warn the user |
| with the mention of the URI of the non-supported extension and (2) |
| ignore this extension. |
| |
| Extensions in an OpenScop file are provided after the core part, |
| without any specific order. Each extension is delimited using XML-like |
| tags corresponding to its URI (e.g., if the extension has the URI |
| `foo', the begin tag is `<foo>' and the end tag is `</foo>'). There is |
| no specification or preferred way to write the extension body. |
| Extensions in an OpenScop data structure must be accessible through one |
| pointer. This pointer will be stored in the `data' field of an |
| `osl_generic_t' container (*note osl_generic_t::). There must be only |
| one extension with the same URI in an OpenScop file or data structure. |
| |
| Extension writers may write a short documentation about their |
| extension to be added to this document. For consistency reason, this |
| documentation should comply to the documentation of the `comment' |
| option (*note Comment Extension::). To describe the file format, it is |
| allowed to reuse the existing rules and terminals present in the |
| OpenScop file format description without defining them (*note OpenScop |
| File Format Specification::). By sending a documentation, you accept it |
| to be added to this document. In particular, the sender fully accepts |
| the license and copyright notice. |
| |
| * Menu: |
| |
| * Comment Extension:: |
| * Arrays Extension:: |
| * Scatnames Extension:: |
| * Lines Extension:: |
| * Irregular Extension:: |
| |
| |
| File: openscop.info, Node: Comment Extension, Next: Arrays Extension, Up: Extensions |
| |
| 3.4.1 Comment Extension |
| ----------------------- |
| |
| *Description* |
| * URI: `comment'. |
| |
| * Author: Ce'dric Bastoul <cedric.bastoul@u-psud.fr>. |
| |
| * Purpose: the `comment' extension stores a textual string. |
| |
| *File Format* |
| |
| The `comment' extension file format respects the following grammar: |
| Comment_generic ::= "<comment>" Comment "</comment>" |
| Comment ::= _Text |
| |
| An example of textual `comment' extension is the following: |
| <comment> |
| This is a comment string. |
| </comment> |
| |
| *Data Structure* |
| |
| The `comment' extension data structure is the following: |
| struct osl_comment { |
| char * comment; /* Comment message as a 0-terminated string */ |
| }; |
| typedef struct osl_comment osl_comment_t; |
| typedef struct osl_comment * osl_comment_p; |
| |
| |
| File: openscop.info, Node: Scatnames Extension, Next: Lines Extension, Prev: Arrays Extension, Up: Extensions |
| |
| 3.4.2 Scatnames Extension |
| ------------------------- |
| |
| *Description* |
| * URI: `scatnames'. |
| |
| * Author: Ce'dric Bastoul <cedric.bastoul@u-psud.fr>. |
| |
| * Purpose: the `scatnames' extension provides a list of textual |
| scattering dimension names. |
| |
| *File Format* |
| |
| The `scatnames' extension file format respects the following grammar. |
| It reuses the `Strings' description (*note Strings Generic::): |
| Scatnames_generic ::= "<scatnames>" Scatnames "</scatnames>" |
| Scatnames ::= Strings |
| |
| The list of scattering dimension names is provided on one single line. |
| The names are separated with spaces. A possible example of such an |
| extension is the following: |
| |
| <scatnames> |
| # List of scattering dimension names: |
| beta_0 i beta_1 j beta_2 |
| </scatnames> |
| |
| *Data Structure* |
| |
| The `scatnames' extension data structure is the following: |
| |
| struct osl_scatnames { |
| osl_strings_p names; /* List of textual scattering dimension names. */ |
| }; |
| typedef struct osl_scatnames osl_scatnames_t; |
| typedef struct osl_scatnames * osl_scatnames_p; |
| |
| The order of the scattering dimension names in the list corresponds to |
| the order of the scattering dimensions. |
| |
| |
| File: openscop.info, Node: Arrays Extension, Next: Scatnames Extension, Prev: Comment Extension, Up: Extensions |
| |
| 3.4.3 Arrays Extension |
| ---------------------- |
| |
| *Description* |
| * URI: `arrays'. |
| |
| * Author: Ce'dric Bastoul <cedric.bastoul@u-psud.fr>. |
| |
| * Purpose: the `arrays' extension provides a set of textual array |
| names corresponding to the array identifiers used in the access |
| relations. |
| |
| *File Format* |
| |
| The `arrays' extension file format respects the following grammar: |
| Arrays_generic ::= "<arrays>" Arrays "</arrays>" |
| Arrays ::= Nb_items Item_list |
| Item_List ::= Item Item_list | (void) |
| Item ::= Identifier Name |
| Nb_items ::= _Integer |
| Identifier ::= _Integer |
| Name ::= _String |
| |
| The number of array names is provided on the first line, then each |
| following line contains a couple identifier-name. For instance, the |
| following example is a correct textual `arrays' extension. It |
| corresponds to the array names of the preliminary example (*note |
| Preliminary Example::): |
| |
| <arrays> |
| # Number of array names: |
| 3 |
| 1 C # Identifier 1 corresponds to array name "C" |
| 3 B # Identifier 3 corresponds to array name "B" |
| 2 A # Identifier 2 corresponds to array name "A" |
| </arrays> |
| |
| *Data Structure* |
| |
| The `arrays' extension data structure is the following: |
| |
| struct osl_arrays { |
| int nb_names; /* Number of names */ |
| int * id; /* Array of nb_names identifiers */ |
| char ** names; /* Array of nb_names names */ |
| }; |
| typedef struct osl_arrays osl_arrays_t; |
| typedef struct osl_arrays * osl_arrays_p; |
| |
| Each name has a name string and an identifier: the ith name has name |
| string `names[i]' and identifier `id[i]'. |
| |
| |
| File: openscop.info, Node: Lines Extension, Next: Irregular Extension, Prev: Scatnames Extension, Up: Extensions |
| |
| 3.4.4 Lines Extension |
| --------------------- |
| |
| |
| File: openscop.info, Node: Irregular Extension, Prev: Lines Extension, Up: Extensions |
| |
| 3.4.5 Irregular Extension |
| ------------------------- |
| |
| |
| File: openscop.info, Node: History, Prev: Extensions, Up: OpenScop Specification |
| |
| 3.5 History |
| =========== |
| |
| OpenScop is a follow-up of Louis-Noe"l Pouchet et al.'s ScopLib effort |
| which was itself based on Ce'dric Bastoul et al.'s Clan tool. People |
| involved in OpenScop's genesis are: |
| * Ce'dric Bastoul |
| |
| * Uday Bondhugula |
| |
| * Tobias Grosser |
| |
| * Louis-Noe"l Pouchet |
| |
| * Sven Verdoolaege |
| |
| |
| File: openscop.info, Node: OpenScop Library, Next: References, Prev: OpenScop Specification, Up: Top |
| |
| 4 OpenScop Library |
| ****************** |
| |
| The OpenScop Library, or OSL for short, is an example implementation of |
| the OpenScop specification. Its API is not part of the OpenScop |
| specification. It offers basic functionalities to manipulate the |
| OpenScop data structures (allocate, free, copy, dump, etc.) and file |
| format (read, print, etc.). The OpenScop Library is _not_ a polyhedral |
| library. OpenScop is an exchange format, and the OpenScop Library |
| reflects this. |
| |
| It is a Free Software using the 3-clause BSD License. Programmers |
| should feel free to use it or copy/paste its code in any project, Open |
| Source or not(1). |
| |
| * Menu: |
| |
| * Precision:: |
| * Base Functions:: |
| * Example of OpenScop Library Utilization:: |
| * Installation:: |
| * Documentation:: |
| * Development:: |
| |
| ---------- Footnotes ---------- |
| |
| (1) Closed source projects should consider to provide some OpenScop |
| file input and output, so they can be incorporated to any |
| OpenScop-based tool chain. |
| |
| |
| File: openscop.info, Node: Precision, Next: Base Functions, Up: OpenScop Library |
| |
| 4.1 Precision |
| ============= |
| |
| The OpenScop specification does not impose a specific type for the |
| constraint matrix elements. For a maximum flexibility, the OpenScop |
| Library offers an hybrid precision implementation. It supports 32 bits, |
| 64 bits and multiple precision (relying on GNU GMP) relations |
| transparently. At relation allocation time, users have two ways to set |
| the precision. The first way is to call an allocation function with a |
| precision parameter. The second way is to rely on the environment |
| variable `OSL_PRECISION'. The accepted values for this variable are |
| `32' for 32 bits precision, `64' for 64 bits precision and `0' for |
| multiple precision. When this variable is set, its value becomes the |
| default precision for relation elements. For instance, to ensure the |
| OpenScop Library will use 64 bits precision by default, the user may |
| set: |
| export OSL_PRECISION=64 |
| if his shell is, e.g., bash or |
| setenv OSL_PRECISION 64 |
| if his shell is, e.g., tcsh. The user should ad this line to his |
| .bashrc or .tcshrc (or whatever convenient file) to make this setting |
| permanent. |
| |
| |
| File: openscop.info, Node: Base Functions, Next: Example of OpenScop Library Utilization, Prev: Precision, Up: OpenScop Library |
| |
| 4.2 Base Functions |
| ================== |
| |
| The OpenScop Library provides, for each OpenScop data structure, a set |
| of functions devoted to basic manipulation, conversion from file format |
| to data structures and from data structures to file format. The naming |
| convention is consistent for all data structures. Hence, the function |
| prototypes differ only with the name of the data structure. In the |
| following, we will use the generic term of _structure_ to refer at any |
| OpenScop data structure. For instance the `osl_'_structure_`_malloc()' |
| function is a generic name can be instantiated to |
| `osl_relation_malloc()' or `osl_statement_malloc()' etc. |
| |
| We present in this documentation only the main functions. Many other |
| utility functions are provided to ease OpenScop format manipulation. |
| The reader is invited to refer at the technical documentation to learn |
| everything about the OpenScop Library. |
| |
| * Menu: |
| |
| * Dumping:: |
| * Printing:: |
| * Reading:: |
| * Allocating:: |
| * Deallocating:: |
| * Cloning:: |
| * Testing:: |
| |
| |
| File: openscop.info, Node: Dumping, Next: Printing, Up: Base Functions |
| |
| 4.2.1 Dumping: osl__structure__dump and idump |
| --------------------------------------------- |
| |
| void osl__structure__dump(FILE * output, osl__structure__p s); |
| void osl__structure__idump(FILE * output, osl__structure__p s, int i); |
| |
| Each OpenScop data structure has a dumping functions as shown above. |
| Dumping means writing down the content of the data structure pointed by |
| `s' (and its fields recursively) in a textual form to the `output' file |
| (the file, possibly `stdout', has to be open for writing). The textual |
| form is not the OpenScop file format but another representation closer |
| to the internal representation in memory and mainly intended for |
| debugging purpose. The `idump' function has an additional integer |
| parameter which corresponds to an indentation level. |
| |
| |
| File: openscop.info, Node: Printing, Next: Reading, Prev: Dumping, Up: Base Functions |
| |
| 4.2.2 Printing: osl__structure__print |
| ------------------------------------- |
| |
| void osl__structure__print(FILE * output, osl__structure__p s); |
| |
| Each OpenScop data structure has a pretty printing function as shown |
| above. It prints the content of the data structure pointed by `s' (and |
| its fields recursively) according to the OpenScop file format (*note |
| OpenScop File Format Specification::) to the `output' file (the file, |
| possibly `stdout', has to be open for writing). |
| |
| |
| File: openscop.info, Node: Reading, Next: Allocating, Prev: Printing, Up: Base Functions |
| |
| 4.2.3 Reading: osl__structure__read |
| ----------------------------------- |
| |
| osl__structure__p osl__structure__read(FILE * input); |
| |
| Each OpenScop data structure has a reading function as shown above. It |
| reads the content of an OpenScop data structure written according to |
| the OpenScop file format (*note OpenScop File Format Specification::) |
| from the `input' file (the file, possibly `stdin', has to be open for |
| reading). It returns a pointer to a freshly allocated |
| `osl__structure__t' structure containing the information. |
| |
| |
| File: openscop.info, Node: Allocating, Next: Deallocating, Prev: Reading, Up: Base Functions |
| |
| 4.2.4 Allocating: osl__structure__malloc |
| ---------------------------------------- |
| |
| osl__structure__p osl__structure__malloc(); |
| |
| Each OpenScop data structure has a memory allocation function as shown |
| above (except one see below). It allocates the memory to store the |
| corresponding data structure, it initializes the pointer fields to |
| `NULL' and the integer fields to `OSL_UNDEFINED' (`-1') and it returns |
| a pointer to the allocated space. |
| |
| An exception to this base description is the `osl_relation_malloc()' |
| function which requires two parameters: the number of rows and columns |
| of the constraint matrix (*note Relations::): |
| |
| osl_relation_p osl_relation_malloc(int nb_rows, int nb_columns); |
| |
| The precision of the relation elements will depend on the |
| `OSL_PRECISION' environment variable (*note Precision::) if it is set, |
| or the maximum available precision if it is not set. Another allocation |
| function is provided to explicitly set a given precision: |
| |
| osl_relation_p osl_relation_pmalloc(int precision, |
| int nb_rows, int nb_columns); |
| |
| The `precision' field may take the following values: |
| * `OSL_PRECISION_SP' for 32 bits precision, |
| |
| * `OSL_PRECISION_DP' for 64 bits precision, |
| |
| * `OSL_PRECISION_MP' for multiple precision, |
| |
| |
| File: openscop.info, Node: Deallocating, Next: Cloning, Prev: Allocating, Up: Base Functions |
| |
| 4.2.5 Deallocating: osl__structure__free |
| ---------------------------------------- |
| |
| void osl__structure__free(osl__structure__p s); |
| |
| Each OpenScop data structure has a memory deallocation function as |
| shown above. It recursively frees the memory allocated for the |
| structure pointed by `s', i.e., internal structures are also freed. |
| |
| |
| File: openscop.info, Node: Cloning, Next: Testing, Prev: Deallocating, Up: Base Functions |
| |
| 4.2.6 Cloning: osl__structure__clone |
| ------------------------------------ |
| |
| osl__structure__p osl__structure__clone(osl__structure__p s); |
| |
| Each OpenScop data structure has a clone function as shown above. It |
| recursively copies the content of the structure pointed by `s', i.e., |
| internal structures are also copied. It returns a pointer to the clone |
| of the structure pointed by `s'. |
| |
| |
| File: openscop.info, Node: Testing, Prev: Cloning, Up: Base Functions |
| |
| 4.2.7 Testing: osl__structure__equal |
| ------------------------------------ |
| |
| int osl__structure__equal(osl__structure__p s1, osl__structure__p s2); |
| |
| Each OpenScop data structure has a testing function as shown above. It |
| checks whether two pointers are referring to equivalent structures |
| (either by pointing to the same structure or to different structures |
| which contain the same information). It returns 1 if the pointed |
| structures are equivalent, 0 otherwise. This test is _content-based_ |
| and is intended for debugging purpose. It is not (and will never be) |
| able to state, e.g., that two relations with different constraint |
| matrices are actually representing the same relation. |
| |
| |
| File: openscop.info, Node: Example of OpenScop Library Utilization, Next: Installation, Prev: Base Functions, Up: OpenScop Library |
| |
| 4.3 Example of OpenScop Library Utilization |
| =========================================== |
| |
| Here is a basic example showing how it is possible to use the OpenScop |
| Library, assuming that a standard installation has been done. The |
| following C program reads an OpenScop file from the standard input and |
| dumps the content of the data structures to the standard output. |
| |
| /* example.c */ |
| # include <stdio.h> |
| # include <osl/osl.h> |
| |
| int main() { |
| osl_scop_p scop; |
| |
| // Read the OpenScop file. |
| scop = osl_scop_read(stdin); |
| |
| // Dump the content of the scop data structure. |
| osl_scop_dump(stdout, scop); |
| |
| // Save the planet. |
| osl_scop_free(scop); |
| |
| return 0; |
| } |
| |
| The compilation command could be: |
| gcc example.c -losl -o example |
| A calling command with the input file test.scop could be: |
| more test.scop | ./example |
| |
| |
| File: openscop.info, Node: Installation, Next: Documentation, Prev: Example of OpenScop Library Utilization, Up: OpenScop Library |
| |
| 4.4 Installation |
| ================ |
| |
| * Menu: |
| |
| * License:: |
| * Requirements:: |
| * Installation Instructions:: |
| * Optional Features:: |
| * Uninstallation:: |
| |
| |
| File: openscop.info, Node: License, Next: Requirements, Up: Installation |
| |
| 4.4.1 License |
| ------------- |
| |
| First of all, it would be very kind to refer the present document in any |
| publication that results from the use of the OpenScop specification or |
| library, *note Bas11:: (a bibtex entry is provided behind the title |
| page of this manual, along with the copyright notice). The OpenScop |
| Library is provided under the 3-clause BSD license: |
| |
| Copyright (C) 2011 University Paris-Sud 11 and INRIA |
| |
| 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 copyrigh |
| 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. |
| |
| |
| File: openscop.info, Node: Requirements, Next: Installation Instructions, Prev: License, Up: Installation |
| |
| 4.4.2 Requirements |
| ------------------ |
| |
| The OpenScop Library is a stand-alone library. For a basic use, it does |
| not need any additional tool or library. Anyway, to be able to work in |
| conjunction with other tools that manipulate multiple precision |
| numbers, the GNU GMP library can be used as an option. |
| |
| * Menu: |
| |
| * GMP Library:: |
| |
| |
| File: openscop.info, Node: GMP Library, Up: Requirements |
| |
| 4.4.2.1 GMP Library (optional) |
| .............................. |
| |
| To be able to deal with insanely large coefficient, the user will need |
| to install the GNU Multiple Precision Library (GMP for short) version |
| 4.2.2 or above(1). The user can compile it by typing the following |
| commands on the GMP root directory: |
| |
| * `./configure' |
| |
| * `make' |
| |
| * And as root: `make install' |
| |
| The GMP default installation is `/usr/local'. This directory may not |
| be inside the user's library path. To fix the problem, the user should |
| set |
| export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib |
| if your shell is, e.g., bash or |
| setenv LD_LIBRARY_PATH $LD_LIBRARY_PATH:/usr/local/lib |
| if your shell is, e.g., tcsh. Add the line to your .bashrc or |
| .tcshrc (or whatever convenient file) to make this change permanent. |
| Another solution is to ask GMP to install in the standard path by using |
| the prefix option of the configure script: `./configure --prefix=/usr'. |
| |
| The OpenScop Library has to be built using the GMP library by |
| specifying the convenient configure script options to buid the GMP |
| version (*note Optional Features::). |
| |
| ---------- Footnotes ---------- |
| |
| (1) `http://www.swox.com/gmp' |
| |
| |
| File: openscop.info, Node: Installation Instructions, Next: Optional Features, Prev: Requirements, Up: Installation |
| |
| 4.4.3 Installation Instructions |
| ------------------------------- |
| |
| Once downloaded and unpacked (e.g. using the `tar -zxvf |
| openscop-0.8.1.tar.gz' command), you can compile the OpenScop Library |
| by typing the following commands on the OpenScop Library's root |
| directory: |
| |
| * `./autogen.sh' |
| |
| * `./configure' |
| |
| * `make' |
| |
| * And as root: `make install' |
| |
| The program binaries and object files can be removed from the source |
| code directory by typing `make clean'. To also remove the files that |
| the `configure' script created (so you can compile the package for a |
| different kind of computer) type `make distclean'. |
| |
| |
| File: openscop.info, Node: Optional Features, Next: Uninstallation, Prev: Installation Instructions, Up: Installation |
| |
| 4.4.4 Optional Features |
| ----------------------- |
| |
| The `configure' shell script attempts to guess correct values for |
| various system-dependent variables and user options used during |
| compilation. It uses those values to create the `Makefile'. Various |
| user options are provided by the OpenScop Library's configure script. |
| They are summarized in the following list and may be printed by typing |
| `./configure --help' in the OpenScop Library top-level directory. |
| |
| * By default, the installation directory is `/usr/local': `make |
| install' will install the package's files in `/usr/local/bin', |
| `/usr/local/lib' and `/usr/local/include'. The user can specify |
| an installation prefix other than `/usr/local' by giving |
| `configure' the option `--prefix=PATH'. |
| |
| * By default, The OpenScop Library is built in 64bits version. If |
| the user gives to `configure' the option `--enable-int-version', |
| the 32bits version of the OpenScop Library will be compiled. In |
| the same way, the option `--enable-mp-version' has to be used to |
| build the multiple precision version. |
| |
| * By default, `configure' will look for the GMP library (necessary |
| to build the multiple precision version) in standard locations. If |
| necessary, the user can specify the GMP path by giving `configure' |
| the option `--with-gmp=PATH'. |
| |
| |
| File: openscop.info, Node: Uninstallation, Prev: Optional Features, Up: Installation |
| |
| 4.4.5 Uninstallation |
| -------------------- |
| |
| The user can easily remove the OpenScop Library from his system by |
| typing (as root if necessary) from the OpenScop Library top-level |
| directory `make uninstall'. |
| |
| |
| File: openscop.info, Node: Documentation, Next: Development, Prev: Installation, Up: OpenScop Library |
| |
| 4.5 Documentation |
| ================= |
| |
| The OpenScop Library distribution provides several sources of |
| documentation. First, the source code itself is as documented as much |
| as possible. The code comments use the Doxygen technical documentation |
| system. The user may install Doxygen(1) to automatically generate a |
| technical documentation by typing `make doc' or `doxygen |
| ./autoconf/Doxyfile' at the OpenScop Library top-level directory after |
| running the configure script (*note Installation Instructions::). |
| Doxygen will generate documentation sources (in HTML, LaTeX and man) in |
| the `doc/source' directory of the OpenScop Library distribution. |
| |
| The Texinfo source of the present document is also provided in the |
| `doc' directory. The user can build it in either PDF format (by typing |
| `texi2pdf openscop.texi') or HTML format (by typing `makeinfo --html |
| openscop.texi', using `--no-split' option to generate a single HTML |
| file) or info format (by typing `makeinfo openscop.texi'). |
| |
| ---------- Footnotes ---------- |
| |
| (1) `http://www.stack.nl/~dimitri/doxygen' |
| |
| |
| File: openscop.info, Node: Development, Prev: Documentation, Up: OpenScop Library |
| |
| 4.6 Development |
| =============== |
| |
| * Menu: |
| |
| * Copyright Issue:: |
| * Repository:: |
| * Coding Style:: |
| * Extension Development:: |
| |
| |
| File: openscop.info, Node: Copyright Issue, Next: Repository, Up: Development |
| |
| 4.6.1 Copyright Issue |
| --------------------- |
| |
| The OpenScop Library is an Open Source project and you should feel free |
| to contribute by adding functionalities (in particular extensions), |
| correcting bugs or improving documentation. However, for painful |
| administrative reasons, the copyright of the core part (everything |
| except extensions) should not be impacted by your work. Hence, if you |
| are doing a significant contribution to the main part, the OpenScop |
| Library maintainer may ask you for an agreement about this copyright. |
| If you plan to do such a significant contribution, it may be wise to |
| discuss this issue with the maintainer first. Extensions may include |
| developer's own copyright. |
| |
| |
| File: openscop.info, Node: Repository, Next: Coding Style, Prev: Copyright Issue, Up: Development |
| |
| 4.6.2 Repository |
| ---------------- |
| |
| The main repository of the OpenScop Library is |
| `http://repo.or.cz/w/openscop.git'. Developers may ask the OpenScop |
| Library maintainer to open them a write access to this repository. Only |
| the maintainer should ever change the `master' branch. Developers |
| should work on their own branches. To avoid any problem developers |
| should use the _fork_ functionality of the repository. |
| |
| |
| File: openscop.info, Node: Coding Style, Next: Extension Development, Prev: Repository, Up: Development |
| |
| 4.6.3 Coding Style |
| ------------------ |
| |
| The OpenScop Library is written in C using an object oriented style. |
| Each important data structure (e.g., `struct foo') has its own header |
| file (`include/osl/foo.h') where lies the definition of the data |
| structure, the two typedefs for the data structure (one for the |
| structure, `osl_foo_t', and one for a pointer to the structure, |
| `osl_foo_p'), the prototypes of the various functions related to this |
| data structure, all named using the prefix "`osl_foo_'". The source |
| code of the functions is provided in a separated C file |
| (`source/foo.c'). |
| |
| Utility functions independent from the main data structures may be |
| placed in separate source files (e.g., definition in |
| `include/osl/util.h' and code in `source/util.c'). Tool-wide |
| preprocessor directives are placed in `include/osl/macros.h', macros |
| are prefixed with "`OSL_'". |
| |
| The core code itself has to be written according to the Google C++ |
| Coding Style: |
| `http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml' (for |
| what can apply to C), plus the naming conventions discussed above with |
| highest priority. The extension parts must only respect the naming |
| convention, but a consistent coding style is much appreciated. |
| |
| |
| File: openscop.info, Node: Extension Development, Prev: Coding Style, Up: Development |
| |
| 4.6.4 Extension Development |
| --------------------------- |
| |
| It's fairly easy to integrate a new extension to OpenScop and the |
| OpenScop Library. Developing a new extension is very much like adding a |
| new "object": it requires writing a data structure for the extension |
| data and the 7 base functions to manage this extension. Here is how |
| developers should proceed to add an extension called `foo' (beware that |
| the naming convention is strict): |
| |
| 1. Send the name `foo' to the maintainer to ensure it is unique and |
| hence can be used as an URI. The name (one single word, |
| or words separated with underscores "_") should be suggested |
| by the extension developers to the OpenScop development |
| mailing list <openscop-development@googlegroups.com>). It |
| should not correspond to an existing structure name (see |
| `include/osl/osl.h' for the list). The maintainer will |
| update `include/osl/osl.h' in the development version |
| accordingly. |
| |
| 2. Look at the `comment' extension. The `comment' extension |
| (*note Comment Extension::) has been written to be used as a basic |
| example for extension developers. Having a look at |
| `include/osl/extensions/comment.h' and |
| `source/extensions/comment.c' will be a great help to do it right. |
| |
| 3. Create the extension data structure: it is necessary that the |
| extension data can be accessible through only one pointer. |
| |
| 4. Code the 7 base functions for the extension. Any extension must |
| provide this set of functions (naming convention apply only |
| if the extension is planed to be integrated to the OpenScop |
| Library default extensions): |
| * `osl_foo_idump' (*note Dumping::) |
| |
| * `osl_foo_sprint' has the following prototype: |
| char * osl__structure__sprint(osl__structure__p s); |
| It corresponds to the pretty printing functions of |
| the core data structures (*note Printing::) with |
| the difference that the OpenScop textual |
| representation is written to a string (returned by |
| the function) instead of a file. |
| |
| * `osl_foo_sread' has the following prototype: |
| osl__structure__p osl__structure__sread(char ** string); |
| It corresponds to the reading functions of the core |
| data structures (*note Reading::) with the |
| difference that the OpenScop textual representation is read |
| from a string (provided as a parameter) instead of a |
| file. The address of the string to read is passed |
| as a parameter and is updated to point immediately |
| after what has been actually read. |
| |
| * `osl_foo_malloc' (*note Allocating::) |
| |
| * `osl_foo_free' (*note Deallocating::) |
| |
| * `osl_foo_clone' (*note Cloning::) |
| |
| * `osl_foo_equal' (*note Testing::) |
| |
| 5. Code the other functions you need! |
| |
| Now let us consider two scenarios. |
| |
| First scenario, the extension is external and is not planned to be |
| integrated to the OpenScop Library. In this case you are all set. |
| Simply generate an `osl_interface_t' for your extension and have a look |
| at the function `osl_scop_register_extension()' which is devoted to |
| register a new extension interface to an existing `osl_scop_t'. |
| |
| Second scenario, the extension will integrate the set of default |
| OpenScop Library extensions (the best solution to share it to other |
| potential users). In this case, a few additional things have to be done: |
| 1. Create the extension header `include/osl/extensions/foo.h' |
| to store the extension structure and function prototypes and |
| the extension source file `source/extensions/foo.c' for the |
| code of the functions. |
| |
| 2. Add the documentation for the extension to the texinfo source of |
| this document (in `doc/openscop.texi'), following the example |
| of the `comment' documentation (*note Comment Extension::). |
| |
| 3. Integrate the extension by adding the `extensions/foo.c' entry |
| to the `libosl_la_SOURCES' in the `source/Makefile.am' |
| file, the `osl/foo.h' entry to the |
| `nobase_pkginclude_HEADERS' and add the corresponding |
| `#include <osl/extensions/foo.h>' in the `include/scop.h.in' |
| file. |
| |
| 4. Add the new extension in the |
| `osl_interface_get_default_registry()' function. |
| |
| 5. You are done! Prepare a single commit or patch corresponding to the |
| integration of the new extension and ask the maintainer to |
| merge it to the master branch. |
| |
| |
| File: openscop.info, Node: References, Prev: OpenScop Library, Up: Top |
| |
| 5 References |
| ************ |
| |
| * [Bas03a] C. Bastoul, P. Feautrier. Improving data locality by |
| chunking. CC'12 International Conference on Compiler Construction, |
| LNCS 2622, pages 320-335, Warsaw, April 2003. |
| |
| * [Bas11] C. Bastoul. OpenScop: A Specification and a Library for |
| Data Exchange in Polyhedral Compilation Tools. Technical Report, |
| Paris-Sud University, France, June 2011. |
| |
| * [Fea92] P. Feautrier. Some efficient solutions to the affine |
| scheduling problem, part II: multidimensional time. International |
| Journal of Parallel Programming, 21(6):389-420, December 1992. |
| |
| * [Gri04] M. Griebl. Automatic parallelization of loop programs for |
| distributed memory architectures. Habilitation Thesis. Faculta"t |
| fu"r Mathematik und Informatik, Universita"t Passau, 2004. |
| _http://www.infosun.fmi.uni-passau.de/cl/loopo/_ |
| |
| * [Wil93] Doran K. Wilde. A library for doing polyhedral operations. |
| Technical Report 785, IRISA, Rennes, France, 1993. |
| |
| |
| |
| |
| Tag Table: |
| Node: Top1290 |
| Node: Introduction2709 |
| Node: Polyhedral Representation6664 |
| Node: Motivation8062 |
| Node: Thinking in Polyhedra11844 |
| Node: Iteration Domain14040 |
| Node: Scattering Function19422 |
| Ref: Scattering Function-Footnote-131896 |
| Node: Access Function31927 |
| Node: What's Next?33977 |
| Node: OpenScop Specification34887 |
| Node: Preliminary Example36041 |
| Ref: Preliminary Example-Footnote-142380 |
| Node: OpenScop File Format Specification42435 |
| Node: Relations46426 |
| Node: Iteration Domain Relation49447 |
| Node: Context Domain Relation52486 |
| Node: Scattering Relation53026 |
| Node: Access Relation54164 |
| Node: Generics56186 |
| Node: Strings Generic57335 |
| Node: Body Generic57983 |
| Node: OpenScop Data Structure Specification59038 |
| Node: osl_relation_t60806 |
| Node: osl_relation_list_t62867 |
| Node: osl_interface_t63571 |
| Node: osl_generic_t65352 |
| Node: osl_strings_t66270 |
| Node: osl_body_t66823 |
| Node: osl_statement_t67554 |
| Node: osl_scop_t69077 |
| Node: Extensions76326 |
| Node: Comment Extension78627 |
| Node: Scatnames Extension79508 |
| Node: Arrays Extension80817 |
| Node: Lines Extension82630 |
| Node: Irregular Extension82795 |
| Node: History82940 |
| Node: OpenScop Library83342 |
| Ref: OpenScop Library-Footnote-184248 |
| Node: Precision84405 |
| Node: Base Functions85588 |
| Node: Dumping86718 |
| Node: Printing87573 |
| Node: Reading88141 |
| Node: Allocating88763 |
| Node: Deallocating90154 |
| Node: Cloning90590 |
| Node: Testing91075 |
| Node: Example of OpenScop Library Utilization91834 |
| Node: Installation92861 |
| Node: License93143 |
| Node: Requirements95030 |
| Node: GMP Library95471 |
| Ref: GMP Library-Footnote-196696 |
| Node: Installation Instructions96730 |
| Node: Optional Features97470 |
| Node: Uninstallation98937 |
| Node: Documentation99233 |
| Ref: Documentation-Footnote-1100359 |
| Node: Development100406 |
| Node: Copyright Issue100615 |
| Node: Repository101390 |
| Node: Coding Style101906 |
| Node: Extension Development103239 |
| Node: References107964 |
| Ref: Bas03a108073 |
| Ref: Bas11108264 |
| Ref: Fea92108451 |
| Ref: Gri04108658 |
| Ref: Wil93108918 |
| |
| End Tag Table |