1\input texinfo 2@c % 3@c % /**-----------------------------------------------------------------** 4@c % ** OpenScop Library ** 5@c % **-----------------------------------------------------------------** 6@c % ** openscop.texi ** 7@c % **-----------------------------------------------------------------** 8@c % ** First version: september 10th 2006 ** 9@c % **-----------------------------------------------------------------**/ 10@c % 11@c % release 0.0: May 4th 2008 12@c % 13 14@c % /************************************************************************* 15@c % * PART I: HEADER * 16@c % *************************************************************************/ 17@c %**start of header 18@setfilename openscop.info 19@settitle OpenScop Specification and Library 20 21@set EDITION 1.0 22@set SPEC_VERSION 1.0 23@set LIB_VERSION 0.8.3 24@set UPDATED February 17th 2012 25@setchapternewpage odd 26 27@c % This is to ask for A4 instead of Letter size document. 28@iftex 29 @afourpaper 30@end iftex 31 32@c %**end of header 33 34@c % /************************************************************************ 35@c % * PART II: SUMMARY DESCRIPTION AND COPYRIGHT * 36@c % ************************************************************************/ 37 38@copying 39This document describes OpenScop, a specification of a file format and a set 40of data structures for polyhedral compilation tools to talk 41together. It also describes briefly the OpenScop Library version @value{LIB_VERSION}, 42a Free Software that provides an example of OpenScop implementation. 43 44It would be quite kind to refer at the present document in any publication that 45results from the use of the OpenScop Library: 46 47@example 48@@TechReport@{Bas11, 49@ @ author =@ @ @ @ @ @ @{C\'edric Bastoul@}, 50@ @ title =@ @ @ @ @ @ @ @{OpenScop: A Specification and a Library for Data 51@ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ Exchange in Polyhedral Compilation Tools@}, 52@ @ month =@ @ @ @ @ @ @ @{September@}, 53@ @ year =@ @ @ @ @ @ @ @ 2011, 54@ @ institution = @{Paris-Sud University, France@} 55@} 56@end example 57 58Copyright @copyright{} 2011 Paris-Sud University and INRIA. 59 60@c quotation 61Permission is granted to copy, distribute and/or modify this document under 62the terms of the GNU Free Documentation License, Version 1.2 published by the 63Free Software Foundation; with no Invariant Sections, with no Front-Cover 64Texts, and with no Back-Cover Texts. To receive a copy of the 65GNU Free Documentation License, write to the Free Software Foundation, Inc., 6659 Temple Place, Suite 330, Boston, MA 02111-1307 USA. 67@c end quotation 68@end copying 69 70@c % /************************************************************************* 71@c % * PART III: TITLEPAGE, CONTENTS, COPYRIGHT * 72@c % *************************************************************************/ 73@titlepage 74@title OpenScop 75@subtitle A Specification and a Library for Data Exchange in Polyhedral Compilation Tools 76@subtitle Edition @value{EDITION}, for OpenScop Specification @value{SPEC_VERSION} and OpenScop Library @value{LIB_VERSION} 77@subtitle @value{UPDATED} 78@author C@'edric Bastoul 79 80@c The following two commands start the copyright page. 81@page 82@vskip 0pt plus 1filll 83@insertcopying 84@end titlepage 85 86@c Output the table of contents at the beginning. 87@contents 88 89@c % /************************************************************************* 90@c % * PART IV: TOP NODE AND MASTER MENU * 91@c % *************************************************************************/ 92@ifnottex 93@node Top 94@top OpenSCop 95 96@insertcopying 97@end ifnottex 98 99@menu 100* Introduction:: 101* Polyhedral Representation:: 102* OpenScop Specification:: 103* OpenScop Library:: 104* References:: 105@end menu 106 107@c % /************************************************************************* 108@c % * PART V: BODY OF THE DOCUMENT * 109@c % *************************************************************************/ 110 111@c % ****************************** INTRODUCTION ****************************** 112@node Introduction 113@chapter Introduction 114OpenScop is an open specification that defines a file format and a set of 115data structures to represent a @emph{static control part} (SCoP for short), 116i.e., a program part that can be represented in the @emph{polyhedral model}. 117The goal of OpenScop is to provide a common interface to various 118polyhedral compilation tools in order to simplify their interaction. 119 120Designing a single format for tools that have different purposes 121(e.g., as different as code generation and data dependence analysis) may 122sound strange at first. However we could observe that most available 123polyhedral compilation tools during the last decade were manipulating 124more or less the same kind of data (polyhedra, affine functions...) and 125were actually sharing a part of their input (e.g., iteration domains and 126context concepts are nearly everywhere). We could also observe that 127those tools may rely on different internal representations, mostly based on 128one of the major polyhedral libraries (e.g., Polylib, PPL or isl), and 129this representation may change over time (e.g., when switching to a 130more convenient polyhedral library). 131The OpenScop aim is to provide a stable, unified format that offers a 132durable guarantee that a tool can use an output or provide an input to 133another tool without breaking a tool chain because of some internal 134changes in one element of the chain. The other promise of OpenScop is 135the ability to assemble or replace the basic blocks of a polyhedral 136compilation framework at no, or at least low engineering cost. 137 138The policy that drives OpenScop can be summarized by these three rules: 139@itemize @bullet 140@item Embed the @emph{minimum} information to build a complete polyhedral 141 compilation framework in the so-called @emph{core part} 142 (to avoid as much as possible empty or useless information 143 for each tool). 144@item Provide a @emph{very stable} core part (so users have some 145 guarantee that they will not need to update their tool 146 because of frequent specification evolution), 147@item Provide a @emph{very flexible} extension part (so it can also 148 be used to test wild new ideas). 149@end itemize 150 151@noindent Another, more technical, rule may be added: 152@itemize @bullet 153@item Avoid any need for external library or tool to support it 154 (i.e., it's not XML or YAML or anything like that). 155@end itemize 156 157The success of OpenScop in meeting its goals totally depends on its 158acceptance by the tool developers (that have to support it in their tools). 159To help them, we provide an example implementation: the OpenScop Library. 160This library (and in particular its API) is not part of the OpenScop 161specification (which includes only the file format and the set of data 162structures). It is licensed under the 3-clause BSD license so developers may 163feel free to use it in their code (either by linking it or copy-pasting its 164code). This document also describes this library briefly (readers are 165invited to read at its technical documentation). 166The current version of the OpenScop Library is still under evaluation, 167and there is no guarantee that the upward compatibility will be respected, 168even if we do think so. A lot of reports are 169necessary to freeze the library API. Thus you are very welcome and 170encouraged to send reports on bugs, wishes, critics, comments, suggestions 171or (please!) successful experiences to the OpenScop mailing list 172@email{openscop-development@@googlegroups.com}. 173 174This document is organized as follows. First, we provide some 175background on the polyhedral model and how it is used to represent and to 176manipulate programs (@pxref{Polyhedral Representation}). Next, 177we describe the OpenScop specification, from the file format 178(@pxref{OpenScop File Format Specification}) to the data structures 179and the OpenScop Library API 180(@pxref{OpenScop Data Structure Specification}). 181Finally we will detail how to install the OpenScop Library 182(@pxref{Installation}). 183 184 185@c % ******************* POLYHEDRAL REPRESENTATION OF PROGRAMS **************** 186@node Polyhedral Representation 187@chapter Polyhedral Representation of Programs 188If you are reading at the OpenScop documentation, you probably don't need any 189explanation about the polyhedral model. It is unlikely that someone will read 190this paper by mistake. However some vicious advisor may ask their poor 191engineers/interns/students 192to work for the very first time on this exciting topic. Most papers on 193polyhedral compilation are hard to read. Despite my efforts, 194mine are no exception according to some reviewers. Hence I give there a new 195try to provide a comprehensive explanation of the polyhedral model without the 196size and style limits of a classical research paper. 197 198Be aware that to be able to understand the polyhedral model, there are a few 199prerequisites. You should not read the following while you still ignore 200what is: 201@itemize @bullet 202@item a @code{for} loop construction in C programs (@code{do} loops in FORTRAN are OK too!), 203@item an @emph{affine expression}, 204@item a @emph{vector}, 205@item a @emph{matrix}, 206@item a @emph{matrix-vector multiply}. 207@end itemize 208If you do not know those concepts, please do some search and come back 209afterwards. And if you are courageous enough, send me a few lines that 210describe them so I can insert them here! 211 212@menu 213* Motivation:: 214* Thinking in Polyhedra:: 215* What's Next?:: 216@end menu 217 218 219@node Motivation 220@section Motivation: Program Transformations 221 222A direct translation of high level programs written, e.g., in C, to assembly 223then to object code is likely to produce (very) inefficient applications. 224Architectures are 225quite complex, including several levels of cache memory, many cores, deep 226pipelines, various number of functional units, of registers etc. 227The list of such 228"architectural features" is growing with each new generation of processors. 229To achieve the best performance, the object program must use 230these features in a smart way. 231Programmers use high level languages for productivity and portability: 232typically they do not have to take care of the target architecture but 233to ensure they write programs which produce the right output. Hence, 234the problem of mapping the program to the target architecture in the most 235efficient way is left to the compiler. 236 237The compiler may see a high level program as a specification 238@emph{of an output}. The program is a list of instructions to be executed to 239produce the output. As long as the output is guaranteed to be as the 240programmer specified in his code, the compiler is free to modify 241the program. 242For instance, let us imagine we are working on an architecture with only 243three registers and we consider the following statements written by 244a programmer: 245 246@example 247@group 248x = a + b; 249y = c + d; 250z = a * b; 251@end group 252@end example 253 254It is easy to see that we can reorder the three statements in any way without 255modifying the semantics (no statement reads or writes a variable that another 256statement writes). Because of the lack of registers, the solutions such that 257the first and the third statements are one after the other are better 258because @code{a} and @code{b} will be put in the processor registers by 259one statement and can be reused directly by the other one 260without reading from memory (this is called a @emph{data locality 261improving} transformation). Hence a better statement order is, e.g.: 262 263@example 264@group 265x = a + b; 266z = a * b; // a and b are still in processor registers 267y = c + d; 268@end group 269@end example 270 271We can also notice that it is possible to run the three statements in 272parallel (possibly on different processors). The programmer may 273explicit this in a way the compiler 274and/or the architecture is able to understand. For instance, 275we can use OpenMP to describe parallelism 276(this is called a @emph{parallelizing} transformation): 277 278@example 279@group 280#pragma omp parallel sections 281@{ 282 #pragma omp section 283 @{ 284 x = a + b; 285 @} 286 #pragma omp section 287 @{ 288 y = c + d; 289 @} 290 #pragma omp section 291 @{ 292 z = a * b; 293 @} 294@} 295@end group 296@end example 297 298However, the right way to optimize this program is probably a tradeoff 299between these two techniques. This is true if, e.g., the target 300architecture has some limitations to run too many operations in parallel, 301or, like in our case, when some data may be reused by some processors. 302Hence, the best optimization for our small example is probably the 303following: 304 305@example 306@group 307#pragma omp parallel sections 308@{ 309 #pragma omp section 310 @{ 311 x = a + b; 312 z = a * b; 313 @} 314 #pragma omp section 315 @{ 316 y = c + d; 317 @} 318@} 319@end group 320@end example 321 322This example is quite trivial because the statements are 323executed only once. The real sport begins when we have to deal with loops, 324as we will see momentarily. However, polyhedral compilation framework users 325have to be conscious that we @emph{need} to transform programs to achieve 326the best performance and that the best transformation that has to be 327discovered (at the price of many, many efforts) and performed may be 328quite complex. Hence the need of powerful model and tools. 329 330 331@node Thinking in Polyhedra 332@section Thinking in Polyhedra 333 334 335Since the very first compilers, the internal representation of programs 336is the @emph{Abstract Syntax Tree}, or AST. In such representation, 337each statement appears only once even if it is executed many times (e.g., 338when it is enclosed inside a loop). This is a limitation 339for finding and applying complex transformations: 340@itemize @bullet 341@item It limits program analysis power. For instance if a statement 342 @emph{depends} on another statement (i.e., they access the same 343 memory location and at least one of these accesses is a write), 344 we will consider both statements as unique entities while the 345 dependence relation may involve only few statement executions. 346@item It limits program transformation power. Loop transformations 347 operate on statement executions. For instance, because they 348 consider all statement executions at the same time, present day 349 production compilers are not able to achieve loop fusion 350 (that tries to merge the loop bodies of two loops) if the loop bounds 351 of the two loops do not match (yes, that's ridiculous). 352@item It limits program manipulation flexibility. 353 Trees are very rigid data structures that are not easy to manipulate. 354 Program transformation may require very complex transformations that will 355 imply deep modifications of the control flow. 356@end itemize 357 358The Polyhedral Model is a convenient alternative representation which 359combines analysis power, expressiveness and high flexibility. The drawback 360is it breaks the classical structure of programs that every programmer 361is familiar with. It requires some (real) efforts 362to be smoothly manipulated, but it definitely worth it. It is based on three 363main concepts, @emph{iteration domain}, @emph{scattering function} and 364@emph{access function} that are described in depth in the 365following sections. 366 367A program part that can be represented using the Polyhedral Model is called 368a @strong{Static Control Part} or @strong{SCoP} for short. 369 370@menu 371* Iteration Domain:: 372* Scattering Function:: 373* Access Function:: 374@end menu 375 376@node Iteration Domain 377@subsection Iteration Domain 378 379The key aspect of the polyhedral model is to consider @emph{statement 380instances}. A statement instance is @emph{one} execution of a statement. 381A statement 382outside a loop has only one instance while those inside loops may have many. 383Let us consider the following code with two statements @code{S1} 384and @code{S2}: 385 386@example 387@group 388pi = 3.14; // S1 389for (i = 0; i < 5; i++) 390 A[i] = pi; // S2 391@end group 392@end example 393 394The list of statement instances is the following (we just have to fully 395unroll the loop): 396 397@example 398@group 399pi = 3.14; 400A[0] = pi; 401A[1] = pi; 402A[2] = pi; 403A[3] = pi; 404A[4] = pi; 405@end group 406@end example 407 408Each instance of a statement which is enclosed inside a loop may be referred 409thanks to its outer loop counters (or @emph{iterators}). In the polyhedral 410model we consider statements as functions of the outer loop counters that may 411produce statement instances: 412instead of simply "@code{S2}", we use preferably the notation @code{S2(i)}. 413For instance we denote the statement instance @code{A[3] = pi;} of the 414previous example as @code{S2(3)}. This means @emph{instance of 415statement @code{S2} for} @code{i = 3}. 416If a statement @code{S3} is enclosed inside two loops of iterators @code{i} 417(outermost loop) and @code{j} (innermost loop), we would denote it 418@code{S3(i,j)}, and so on with more enclosing loops. 419 420The ordered list 421of iterators (ordered from the outermost iterator to the innermost iterator) 422is called the @strong{iteration vector}. For instance the iteration vector for 423@code{S3} is @code{(i,j)}, for @code{S2} it is @code{(i)}, and for @code{S1} 424it is empty since it has no enclosing loop: @code{()}. A more precise reading 425at the notation @code{S2(3)} would show that it denotes the instance of 426statement @code{S2} for the iteration vector @code{(2)}. 427 428Obviously, dealing with statement instances does not mean we have to unroll all 429loops. First because there would be probably too many instances to deal with, 430and second because we probably just do not know how many instances there are. 431For instance in the following loop it is impossible to know (at compile time) 432how many times the statement @code{S3} will be executed: 433 434@example 435@group 436for (i = 2; i <= N; i++) 437 for (j = 2; j <= N; j++) 438 A[i] = pi; // S3 439@end group 440@end example 441 442@noindent Such a loop is said to be @emph{parametric}: it depends on 443(at least) a value called a @emph{parameter} which is not modified 444during the execution of the whole loop, but is unknown at compile time. 445Here, the only parameter is @code{N}. 446 447A compact way to represent all the instances of a given statement 448is to consider the set of all possible values of its iteration vector. 449This set is called the @strong{iteration domain}. It can be conveniently 450described thanks to all the constraints on the various iterators the statement 451depends on. For instance, let us consider 452the statement @code{S3} of the previous program. The iteration domain is the set 453of iteration vectors @code{(i,j)}. Because of the parameter, we are not able to 454achieve a precise list of all possible values. It would look like this: 455 456@example 457@group 458(2,2) (2,3) (2,4) ... (2,N) 459(3,2) (3,3) (3,4) ... (3,N) 460... ... ... ... ... 461(N,2) (N,3) (N,4) ... (N,N) 462@end group 463@end example 464 465@noindent A better way is to say it is the set 466of iteration vectors @code{(i,j)} such that @code{i} is an integer greater or 467equal than 2 and lower or equal than @code{N}, and @code{j} is an integer 468greater or equal than 2 and lower or equal than @code{N}. This may be written 469in the following mathematical form: 470 471@tex 472$$D _{S3} = \{(i,j) \in Z^2 \; | \; 2 \leq i \leq N \land 2 \leq j \leq N \}$$ 473@end tex 474 475@ifnottex 476@example 477@group 478D_S3 = @{(i,j) in Z^2 | 2 <= i <= N && 2 <= j <= N @} 479@end group 480@end example 481@end ifnottex 482 483@noindent It is easy to see that this iteration domain is a part of the 4842-dimensional space 485@tex 486$Z^2$. 487@end tex 488@ifnottex 489@example 490@group 491Z^2. 492@end group 493@end example 494@end ifnottex 495We often use in our research papers a graphical representation that gives a 496better view of this subspace: 497 498@image{images/basic1,4cm} 499 500@noindent Here, the iteration domain is specified thanks to a set of 501constraints. When those constraints are affine and 502depend only on the outer loop counters and some parameters, the set of 503constraints defines a @emph{polyhedron} (more precisely this is a 504@emph{Z-polyhedron}, but we use @emph{polyhedron} for short). 505Hence the @emph{polyhedral model}! 506 507To manipulate a set of affine constraints easily, we rely on a matrix 508representation. To write it, we use the @emph{homogeneous} iteration vector: 509it is simply the iteration vector with some additional dimensions to 510represent the parameters and the constant. 511For instance for the statement @code{S3}, the 512iteration vector in homogeneous coordinates is @code{(i, j, N, 1)} 513(we will now call it @emph{iteration vector} directly for short). 514Then we write all the constraints as affine inequalities of the form 515@emph{affine constraint} 516@tex 517$\geq 0$. 518@end tex 519@ifnottex 520@code{ >= 0}. 521@end ifnottex 522For instance for the statement @code{S3} the set of constraints is: 523 524@tex 525$$ 526\hbox{$ \cases{ i - 2 &$\geq 0$\cr 527 -i + N &$\geq 0$\cr 528 j - 2 &$\geq 0$\cr 529 -j + N &$\geq 0$}$} 530$$ 531@end tex 532 533@ifnottex 534@example 535@group 536 i - 2 >= 0 537 -i + N >= 0 538 j - 2 >= 0 539 -j + N >= 0 540@end group 541@end example 542@end ifnottex 543 544@noindent Lastly, we translate the constraint system to the form 545@strong{domain matrix}@code{ * }@emph{iteration vector}@code{ >= 0}: 546 547@c Thanks to Harald Devos for the TeX :-) ! 548@tex 549$$ 550\left[ 551\matrix{ 552 1 & 0 & 0 & -2 \cr 553-1 & 0 & 1 & 0 \cr 554 0 & 1 & 0 & -2 \cr 555 0 & -1 & 1 & 0 556 } 557\right] 558\left( 559\matrix{ 560i \cr 561j \cr 562N \cr 5631 564 } 565\right) 566\ge 567\left( 568\matrix{ 5690 \cr 5700 \cr 5710 \cr 5720 573} 574\right) 575$$ 576@end tex 577@ifnottex 578@example 579@group 580[ 1 0 0 -2 ] [ i ] [ 0 ] 581[ -1 0 1 0 ] [ j ] [ 0 ] 582[ 0 1 0 -2 ] * [ N ] >= [ 0 ] 583[ 0 -1 1 0 ] [ 1 ] [ 0 ] 584@end group 585@end example 586@end ifnottex 587 588@noindent @strong{The domain matrix will be used in all our tools to provide the 589information on the iteration domain of a given statement (the iteration vector 590is in general an implicit information).} 591 592@node Scattering Function 593@subsection Scattering Function 594 595There is no ordering information inside the iteration domain: it only describes 596the set of statement instances but @strong{not} the order in which they have 597to be executed relatively to each other. In the past the lexicographic order 598of the iteration domain was considered, this is no more true 599(especially when using CLooG). If we do not provide any ordering information, this 600means that the statement instances may be executed in any order 601(this is useful, e.g., to specify parallelism). However, some statement instances 602may depend on some others and it may be critical to enforce a given order (or 603non-order). Hence we need another information. 604 605We call @emph{scattering} any kind of ordering information in the polyhedral 606model. There exists many kind of ordering, such as @emph{allocation}, 607@emph{scheduling}, @emph{chunking} etc. They are all expressed 608in the same way, i.e., using @emph{logical stamps}, but they may have 609different semantics. 610 611In the case of @strong{scheduling}, the logical stamps are logical dates that 612express at which date a statement instance has to be executed. For instance, 613let us consider the following three statements: 614 615@example 616@group 617x = a + b; // S1 618y = c + d; // S2 619z = a * b; // S3 620@end group 621@end example 622 623@noindent The scheduling of a statement @code{S} is typically 624denoted by 625@tex 626$\theta_{S}$. 627@end tex 628@ifnottex 629T_S. 630@end ifnottex 631Let us consider the following logical dates for each statement: 632 633@tex 634@example 635@group 636$\theta_{S1} = 2$ 637$\theta_{S2} = 3$ 638$\theta_{S3} = 1$ 639@end group 640@end example 641@end tex 642 643@ifnottex 644@example 645@group 646T_S1 = 1 647T_S2 = 2 648T_S3 = 3 649@end group 650@end example 651@end ifnottex 652 653@noindent It means that statement @code{S3} has to be executed at logical date 654@code{1}, statement @code{S1} has to be executed at logical date 655@code{2} and statement @code{S2} has to be executed at logical date 656@code{3}. The target code has to respect this scheduling (the order of 657the logical dates), hence it would look like the following where the 658variable @code{t} denotes the time: 659 660@example 661@group 662t = 1; 663z = a * b; // S3 664t = 2; 665x = a + b; // S1 666t = 3; 667y = c + d; // S2 668@end group 669@end example 670 671@noindent When some statements share the same logical date, this means that, 672once the program reaches this logical date, the two statements can be executed 673in any order, or better, in parallel. For instance let us consider the 674following scheduling: 675 676@tex 677@example 678@group 679$\theta_{S1} = 1$ 680$\theta_{S2} = 2$ 681$\theta_{S3} = 1$ 682@end group 683@end example 684@end tex 685 686@ifnottex 687@example 688@group 689T_S1 = 1 690T_S2 = 2 691T_S3 = 1 692@end group 693@end example 694@end ifnottex 695 696@noindent Statements @code{S1} and @code{S3} have the same logical date, 697moreover, @code{S2} has a greater logical date than @code{S1} and @code{S3}. 698Hence the target code would be: 699 700@example 701@group 702t = 1; 703#pragma omp parallel sections 704@{ 705 #pragma omp section 706 @{ 707 x = a + b; // S1 708 @} 709 #pragma omp section 710 @{ 711 z = a * b; // S3 712 @} 713@} 714t = 2; 715y = c + d; // S2 716@end group 717@end example 718 719Logical dates may be multidimensional, as clocks: the first dimension 720may correspond to days (most significant), the next one to hours (less 721significant), the third to minutes and so on. For instance we can consider 722the following multidimensional schedules for our example: 723 724@tex 725@example 726@group 727$\theta_{S1} = (1,1)$ 728$\theta_{S2} = (2,1)$ 729$\theta_{S3} = (1,2)$ 730@end group 731@end example 732@end tex 733 734@ifnottex 735@example 736@group 737T_S1 = (1,1) 738T_S2 = (2,1) 739T_S3 = (1,2) 740@end group 741@end example 742@end ifnottex 743 744@noindent It is not very hard to decypher the meaning of such scheduling. 745Because of the first dimension, statements @code{S1} and @code{S3} will be 746executed before statement @code{S2} (@code{S1} and @code{S3} are executed at 747day 1, while @code{S2} is executed at day 2). The second dimension is not 748really useful there for @code{S2} because it is the only statement executed 749at day 2. Nevertheless it allows to order @code{S1} and 750@code{S3} relatively to each other since @code{S1} is executed at hour 1 of day 7511 while @code{S3} is executed at hour 2 of day 1. 752The corresponding target code is the following, with some 753additional time variables for a better view of the ordering (@code{t1} 754corresponds to the first time dimension, @code{t2} to the second one): 755 756@example 757@group 758t1 = 1; 759t2 = 1; 760x = a + b; // S1 761t2 = 2; 762z = a * b; // S3 763t1 = 2; 764t2 = 1; 765y = c + d; // S2 766@end group 767@end example 768 769In the case of @strong{allocation} (in the literature we can find some 770papers calling it @emph{placement}), the logical stamp is a processor 771number expressing on which processor a statement instance has to be 772executed. Typically, allocations are written in the same way as scheduling. 773Here, we denote it @math{P_S} for a statement @code{S}. 774For instance, let us consider the following allocation: 775 776@tex 777@example 778@group 779$P_{S1} = 1$ 780$P_{S2} = 2$ 781$P_{S3} = 1$ 782@end group 783@end example 784@end tex 785 786@ifnottex 787@example 788@group 789P_S1 = 1 790P_S2 = 2 791P_S3 = 1 792@end group 793@end example 794@end ifnottex 795 796@noindent The corresponding target code has to take into account that both 797statements @code{S1} and @code{S3} have to be executed on the same processor 798(they have the same logical number 1) and that statement @code{S2} has 799to be executed on another processor (logical number 2). A possible target code 800is the following: 801 802@example 803@group 804#pragma omp parallel sections 805@{ 806 #pragma omp section 807 @{ 808 // Logical processor 1 809 x = a + b; // S1 810 z = a * b; // S3 811 @} 812 #pragma omp section 813 @{ 814 // Logical processor 2 815 y = c + d; // S2 816 @} 817@} 818@end group 819@end example 820 821@noindent We can note that no order has been specified for the 822statements @code{S1} and @code{S3} that are executed on the same processor. 823Hence any order is satisfying. For sake of flexibility, it is usual to build 824a scattering whose various dimensions do not have the same semantics. A 825typical construction is @emph{space/time mapping} where the first @code{n} 826dimensions are devoted to allocation, then the last @code{m} 827dimensions are devoted to scheduling. Typically, space/time mapping is 828written in the same way as scheduling. 829Here we denote it @math{M_S} for a statement @code{S}. 830For instance, let us consider the following space/time mapping for our 831example where one dimension is devoted to mapping and one dimension is 832devoted to scheduling: 833 834@tex 835@example 836@group 837$M_{S1} = (1,2)$ 838$M_{S2} = (2,1)$ 839$M_{S3} = (1,1)$ 840@end group 841@end example 842@end tex 843 844@ifnottex 845@example 846@group 847M_S1 = (1,2) 848M_S2 = (2,1) 849M_S3 = (1,1) 850@end group 851@end example 852@end ifnottex 853 854@noindent Here we have the same first dimension as the previous example, thus 855the allocation of the statements to processors is the same. The second 856dimension precises on a given processor at which logical date a statement 857instance has to be executed. Here, the statement @code{S1} is executed at 858day 2 on processor 1 while the statement @code{S3} is executed at day 1 onto 859the same processor. It follows this space/time mapping corresponds to the 860following target code (we added an additional variable to represent the 861local logical clocks): 862 863@example 864@group 865#pragma omp parallel sections 866@{ 867 #pragma omp section 868 @{ 869 // Logical processor 1 870 t = 1; 871 z = a * b; // S3 872 t = 2; 873 x = a + b; // S1 874 @} 875 #pragma omp section 876 @{ 877 // Logical processor 2 878 t = 1; 879 y = c + d; // S2 880 @} 881@} 882@end group 883@end example 884 885For the same reason as discussed for iteration domains 886(@pxref{Iteration Domain}), it is not possible to define a scattering for 887each statement instance, especially if the statement belongs to a 888(possibly parametric) loop. The iteration vector fully defines an 889instance of a given statement. Thus, a practical way to provide a scattering 890for each instance of a given statement is to use a @emph{function} 891that depends on the iteration vector. In this way the function may associate 892to each iteration vector a different scattering. We call these functions 893@strong{scattering functions}. Scattering functions are @emph{affine} 894functions of the outer loop counter and the global parameters. 895For instance, let us consider the following source code: 896 897@example 898@group 899for (i = 2; i <= 4; i++) 900 for (j = 2; j <= 4; j++) 901 P[i+j] += A[i] + B[j]; // S4 902@end group 903@end example 904 905@noindent The iteration domain of the statement @code{S4} is: 906 907 908@tex 909$$D _{S4} = \{(i,j) \in Z^2 \; | \; 2 \leq i \leq 4 \land 2 \leq j \leq 4 \}.$$ 910@end tex 911@ifnottex 912@example 913@group 914D_S4= @{(i,j) in Z^2 | 2 <= i <= 4 && 2 <= j <= 4 @}. 915@end group 916@end example 917@end ifnottex 918 919@noindent If you are still not comfortable with the mathematical notation, it 920corresponds to the following graphical representation: 921 922@image{images/basic2,3cm} 923 924@noindent The list of the statement instances of @code{S4} (the integer 925points of its iteration domain) corresponds to the following iteration vectors: 926 927@example 928@group 929iteration vector 930 (2,2) 931 (2,3) 932 (2,4) 933 (3,2) 934 (3,3) 935 (3,4) 936 (4,2) 937 (4,3) 938 (4,4) 939@end group 940@end example 941 942@noindent Let us suppose we want to schedule the instances of the statement 943@code{S4} (the integer points of its iteration domain) using the following 944scheduling function: 945 946@tex 947@example 948@group 949$\theta_{S4}(i, j) = (j+2, 3*i+j)$ 950@end group 951@end example 952@end tex 953 954@ifnottex 955@example 956@group 957T_S4(i,j) = (j+2,3*i+j) 958@end group 959@end example 960@end ifnottex 961 962@noindent We only need to apply the function to each iteration vector to find 963the logical date of each instance: 964 965@example 966@group 967iteration vector logical date 968 (2,2) --> (4,8) 969 (2,3) --> (5,9) 970 (2,4) --> (6,10) 971 (3,2) --> (4,11) 972 (3,3) --> (5,12) 973 (3,4) --> (6,13) 974 (4,2) --> (4,14) 975 (4,3) --> (5,15) 976 (4,4) --> (6,16) 977@end group 978@end example 979 980The polyhedral model users do not have to take care about the generation of a 981target code that respects the scattering: the 982CLooG@footnote{@url{http://www.cloog.org}} tool is there to 983solve the problem quite easily. For the previous 984example, the target code would be the following (@code{t1} and @code{t2} 985correspond to the two dimensions of the logical date, the reader may 986take care that this code actually implements the scattering function): 987 988@example 989@group 990for (t1 = 4; t1 <= 6; t1++) @{ 991 for (t2 = t1+4; t2 <= t1+10; t2++) @{ 992 if ((-t1+t2+2)%3 == 0) @{ 993 i = (-t1+t2+2)/3 ; 994 j = t1-2 ; 995 P[i+j] += A[i] + B[j]; // S4 996 @} 997 @} 998@} 999@end group 1000@end example 1001 1002 1003 1004Obviously with such a twisted scheduling, it is hard to see the "meaning" 1005of the transformation. To name any kind of program transformation as 1006a magic spell ("tile", "fuse", "skew"...) is an old bad habit which is not 1007relevant anymore in the polyhedral model: a scheduling may be an arbitrary 1008complex sequence of basic-old-good transformations. Nevertheless it is most 1009of the time quite easy to translate well known transformations to schedules. 1010For instance, let us consider this new scheduling function: 1011 1012@tex 1013@example 1014@group 1015$\theta_{S4}(i,j) = (j,i)$ 1016@end group 1017@end example 1018@end tex 1019 1020@ifnottex 1021@example 1022@group 1023T_S4(i,j) = (j,i) 1024@end group 1025@end example 1026@end ifnottex 1027 1028@noindent Using CLooG, we can generate the target code: 1029 1030@example 1031@group 1032for (t1 = 2; t1 <= 4; t1++) @{ 1033 for (t2 = 2; t2 <= 4; t2++) @{ 1034 i = t2; 1035 j = t1; 1036 P[i+j] += A[i] + B[j]; // S4 1037 @} 1038@} 1039@end group 1040@end example 1041 1042 1043@noindent It is easy to see (and analyze) that it corresponds to a classical 1044@emph{loop interchange} transformation. 1045 1046A very useful example of multi-dimensional scattering functions is 1047the @strong{scheduling of the original program}. 1048The method to compute it is quite simple (@pxref{Fea92}). The idea is to 1049build an abstract syntax tree of the program and to read the scheduling for 1050each statement. For instance, let us consider the following implementation of 1051a Cholesky factorization: 1052 1053@example 1054@group 1055/* A Cholesky factorization kernel. */ 1056for (i=1;i<=N;i++) @{ 1057 for (j=1;j<=i-1;j++) @{ 1058 a[i][i] -= a[i][j] ; // S1 1059 @} 1060 a[i][i] = sqrt(a[i][i]) ; // S2 1061 for (j=i+1;j<=N;j++) @{ 1062 for (k=1;k<=i-1;k++) @{ 1063 a[j][i] -= a[j][k]*a[i][k] ; // S3 1064 @} 1065 a[j][i] /= a[i][i] ; // S4 1066 @} 1067 @} 1068@} 1069@end group 1070@end example 1071 1072@noindent The corresponding abstract syntax tree is shown in the following 1073figure. It directly gives the scattering functions (schedules) for all the 1074statements of the program (just follow the paths). 1075 1076@image{images/tree,6cm} 1077 1078@tex 1079$$ 1080\hbox{$ \cases{ \theta _{S1}(i,j) &$= (0,i,0,j,0)$\cr 1081 \theta _{S2}(i) &$= (0,i,1)$\cr 1082 \theta _{S3}(i,j,k) &$= (0,i,2,j,0,k,0)$\cr 1083 \theta _{S4}(i,j) &$= (0,i,2,j,1)$}$} 1084$$ 1085@end tex 1086 1087@ifnottex 1088@example 1089@group 1090T_S1(i,j) = (0,i,0,j,0) 1091T_S2(i) = (0,i,1) 1092T_S3(i,j,k) = (0,i,2,j,0,k,0) 1093T_S4(i,j) = (0,i,2,j,1) 1094@end group 1095@end example 1096@end ifnottex 1097 1098@noindent These schedules depend on the iterators and give for each instance 1099of each statement a unique execution date. Using such scattering functions 1100allows CLooG to re-generate the input code. 1101 1102@noindent To easily manipulate the scattering function of any 1103statement @code{S}, we translate it to the matrix form: 1104@tex 1105@math{\theta_S}(@emph{iteration vector}) 1106@end tex 1107@ifnottex 1108T_S(@emph{iteration vector}) 1109@end ifnottex 1110@code{ = }@strong{scattering matrix}@code{ * }@emph{iteration vector}. 1111For instance let us consider again our previous example 1112@tex 1113$\theta_{S4}(i, j) = (j+2, 3*i+j).$ 1114@end tex 1115@ifnottex 1116T_S4(i,j) = (j+2,3*i+j). 1117@end ifnottex 1118We write it in the following way: 1119@tex 1120$$ 1121\theta_{S4} 1122\left( 1123\matrix{ 1124 i \cr 1125 j \cr 1126 1 1127 } 1128\right) 1129= 1130\left[ 1131\matrix{ 1132 0 & 0 & 2 \cr 1133 3 & 1 & 0 1134 } 1135\right] 1136\left( 1137\matrix{ 1138 i \cr 1139 j \cr 1140 1 1141 } 1142\right) 1143$$ 1144@end tex 1145@ifnottex 1146@example 1147@group 1148 [ i ] [ 0 1 2 ] [ i ] 1149T_S4([ j ]) = [ 3 1 0 ] * [ j ] 1150 [ 1 ] [ 1 ] 1151@end group 1152@end example 1153@end ifnottex 1154 1155@noindent @strong{The scattering matrix will be used in all our tools to provide 1156the information on the scattering of a given statement 1157(the iteration vector is in general an implicit information).} 1158 1159 1160@node Access Function 1161@subsection Access Function 1162 1163Before applying any transformation, it is essential to deeply analyze both the 1164original program and the transformation to ensure the transformation does not 1165imply any modification of the original program semantics. In the polyhedral 1166model, we are able to achieve 1167an exact analysis when all the memory accesses are made through arrays 1168(note that variables are a particular case of arrays since they are simply 1169arrays with only one memory location) with affine subscripts that depend 1170on outer loop counters and global parameters (note that @emph{subscripts} 1171are sometimes called @emph{index} or @emph{accesses} in the literature). 1172 1173For instance let us consider the array access @code{A[2*i+j][j][i+N]}. It has 1174three dimensions, each subscript dimension is an affine form of some outer loop 1175iterarors (@code{i} and @code{j}) and global parameters (@code{N}) hence 1176it corresponds to an acceptable array access to be analyzed in the 1177polyhedral model. 1178 1179Each array access can target a different memory cell depending on the 1180statement instance, i.e., depending on the iteration vector. 1181Thus we use access functions (or subscript functions, or index functions, as you 1182prefer to call it) depending on the iteration vector to describe an array 1183access. In our example, the access function would be written 1184@math{F_A(i, j) = (2*i+j, j, i+N)}. 1185 1186@noindent To easily manipulate the access function of any 1187array @code{A}, we translate it to the matrix form: 1188@math{F_A}(@emph{iteration vector}) 1189@code{ = }@strong{access matrix}@code{ * }@emph{iteration vector}. 1190For instance let us consider again our previous example. We would 1191write it in the following way: 1192@tex 1193$$ 1194F_A 1195\left( 1196\matrix{ 1197 i \cr 1198 j \cr 1199 N \cr 1200 1 1201 } 1202\right) 1203= 1204\left[ 1205\matrix{ 1206 2 & 1 & 0 & 0 \cr 1207 0 & 1 & 0 & 0 \cr 1208 1 & 0 & 1 & 0 1209 } 1210\right] 1211\left( 1212\matrix{ 1213 i \cr 1214 j \cr 1215 N \cr 1216 1 1217 } 1218\right) 1219$$ 1220@end tex 1221@ifnottex 1222@example 1223@group 1224 [ i ] [ 2 1 0 0 ] [ i ] 1225F_A([ j ]) = [ 0 1 0 0 ] * [ j ] 1226 [ N ] [ 1 0 1 0 ] [ N ] 1227 [ 1 ] [ 1 ] 1228@end group 1229@end example 1230@end ifnottex 1231 1232@noindent @strong{The access matrix will be used in all our tools to provide the 1233information on the access of a given statement 1234(the iteration vector is in general an implicit information).} 1235 1236@node What's Next? 1237@section What's Next? 1238 1239OK, now you have an idea about how we do represent a program part in the 1240polyhedral model. You know the three main concepts, namely: domain, scattering 1241and access. What can you do with this?! Well, pretty much anything related 1242to code restructuring! The core idea will be to rely on the mathematical 1243representation to extract useful information about your 1244code (data reuse, parallelism...) and to generate a scattering 1245to benefit from the properties you analysed. 1246However, OpenScop's documentation is not the right 1247place to learn at this (OpenScop is all about representation, not about 1248manipulation). Probably it is the right time for you to 1249have a look at: 1250@itemize @bullet 1251@item PoCC @url{http://pocc.sourceforge.net} 1252@item Pluto @url{http://pluto-compiler.sourceforge.net} 1253@end itemize 1254 1255@noindent Have fun :-) ! 1256 1257 1258@c % *********************** OpenScop Specification ************************** 1259@node OpenScop Specification 1260@chapter OpenScop Specification 1261 1262OpenScop provides an explicit polyhedral representation of a static control 1263part. It has been designed by various polyhedral compilation tool writers from 1264various institutions. It builds on previous popular polyhedral file and data 1265structure formats (such as @emph{.cloog} and CLooG data structures) to provide 1266a unique, extensible format to most polyhedral compilation tools. It 1267is composed of two parts. The first part, the so-called 1268@emph{core part}, is devoted to the polyhedral representation of a SCoP. 1269It contains what is strictly necessary to build a 1270complete source-to-source framework in the polyhedral model and to output a 1271semantically equivalent code for the SCoP, from analysis to code generation. 1272The second part of the format, the so-called @emph{extension part}, 1273contains extensions to provide additional informations to some tools. 1274 1275@menu 1276* Preliminary Example:: 1277* OpenScop File Format Specification:: 1278* OpenScop Data Structure Specification:: 1279* Extensions:: 1280* History:: 1281@end menu 1282 1283@c %/************************************************************************* 1284@c % * PRELIMINARY EXAMPLE * 1285@c % *************************************************************************/ 1286@node Preliminary Example 1287@section Preliminary Example 1288OpenScop is a specification for representing static control program parts in 1289the polyhedral model. Thus, we can translate some code parts to an equivalent 1290OpenScop representation. As an example, let us consider the 1291following matrix-multiply kernel: 1292 1293@example 1294#pragma scop 1295if (N > 0) @{ 1296 for (i = 0; i < N; i++) @{ 1297 for (j = 0; j < N; j++) @{ 1298 C[i][j] = 0.0; 1299 for (k = 0; k < N; k++) 1300 C[i][j] = C[i][j] + A[i][k] * B[k][j]; 1301 @} 1302 @} 1303@} 1304@end example 1305 1306The Clan@footnote{@url{http://www.lri.fr/~bastoul/development/clan/}} 1307tool may be used to translate this code part to an OpenScop 1308representation automatically. The @code{#pragma scop} is used here for 1309Clan, but some other tool may not need it. Here is the result of the 1310translation to an OpenScop textual representation. 1311 1312@sp 1 1313@center @strong{DON'T PANIC} 1314@sp 1 1315 1316@noindent Explanations will follow and it is not 1317as cryptic as it seems to be ! 1318@sp 1 1319 1320@example 1321<OpenScop> 1322 1323# =============================================== Global 1324# Backend Language 1325C 1326 1327# Context 1328CONTEXT 13291 3 0 0 0 1 1330# e/i | N | 1 1331 1 1 -1 ## N-1 >= 0 1332 1333# Parameter names are provided 13341 1335# Parameter names 1336<strings> 1337N 1338</strings> 1339 1340# Number of statements 13412 1342 1343# =============================================== Statement 1 1344# Number of relations describing the statement 13453 1346 1347# ---------------------------------------------- 1.1 Domain 1348DOMAIN 13494 5 2 0 0 1 1350# e/i | i j | N | 1 1351 1 1 0 0 0 ## i >= 0 1352 1 -1 0 1 -1 ## -i+N-1 >= 0 1353 1 0 1 0 0 ## j >= 0 1354 1 0 -1 1 -1 ## -j+N-1 >= 0 1355 1356# ---------------------------------------------- 1.2 Scattering 1357SCATTERING 13585 10 5 2 0 1 1359# e/i| s1 s2 s3 s4 s5 | i j | N | 1 1360 0 -1 0 0 0 0 0 0 0 0 ## s1 = 0 1361 0 0 -1 0 0 0 1 0 0 0 ## s2 = i 1362 0 0 0 -1 0 0 0 0 0 0 ## s3 = 0 1363 0 0 0 0 -1 0 0 1 0 0 ## s4 = j 1364 0 0 0 0 0 -1 0 0 0 0 ## s5 = 0 1365 1366# ---------------------------------------------- 1.3 Access 1367WRITE 13683 8 3 2 0 1 1369# e/i| Arr [1] [2] | i j | N | 1 1370 0 -1 0 0 0 0 0 1 ## C 1371 0 0 -1 0 1 0 0 0 ## [i] 1372 0 0 0 -1 0 1 0 0 ## [j] 1373 1374# ---------------------------------------------- 1.4 Body 1375# Statement body is provided 13761 1377# Statement body 1378<body> 1379# Number of original iterators 13802 1381# Original iterator names 1382i j 1383# Statement body expression 1384C[i][j] = 0.0; 1385</body> 1386 1387# =============================================== Statement 2 1388# Number of relations describing the statement 13895 1390 1391# ---------------------------------------------- 2.1 Domain 1392DOMAIN 13936 6 3 0 0 1 1394# e/i| i j k | N | 1 1395 1 1 0 0 0 0 ## i >= 0 1396 1 -1 0 0 1 -1 ## -i+N-1 >= 0 1397 1 0 1 0 0 0 ## j >= 0 1398 1 0 -1 0 1 -1 ## -j+N-1 >= 0 1399 1 0 0 1 0 0 ## k >= 0 1400 1 0 0 -1 1 -1 ## -k+N-1 >= 0 1401 1402# ---------------------------------------------- 2.2 Scattering 1403SCATTERING 14047 13 7 3 0 1 1405# e/i| s1 s2 s3 s4 s5 s6 s7 | i j k | N | 1 1406 0 -1 0 0 0 0 0 0 0 0 0 0 0 ## s1 = 0 1407 0 0 -1 0 0 0 0 0 1 0 0 0 0 ## s2 = i 1408 0 0 0 -1 0 0 0 0 0 0 0 0 0 ## s3 = 0 1409 0 0 0 0 -1 0 0 0 0 1 0 0 0 ## s4 = j 1410 0 0 0 0 0 -1 0 0 0 0 0 0 1 ## s5 = 1 1411 0 0 0 0 0 0 -1 0 0 0 1 0 0 ## s6 = k 1412 0 0 0 0 0 0 0 -1 0 0 0 0 0 ## s7 = 0 1413 1414# ---------------------------------------------- 2.3 Access 1415WRITE 14163 9 3 3 0 1 1417# e/i| Arr [1] [2] | i j k | N | 1 1418 0 -1 0 0 0 0 0 0 1 ## C 1419 0 0 -1 0 1 0 0 0 0 ## [i] 1420 0 0 0 -1 0 1 0 0 0 ## [j] 1421 1422READ 14233 9 3 3 0 1 1424# e/i| Arr [1] [2] | i j k | N | 1 1425 0 -1 0 0 0 0 0 0 1 ## C 1426 0 0 -1 0 1 0 0 0 0 ## [i] 1427 0 0 0 -1 0 1 0 0 0 ## [j] 1428 1429READ 14303 9 3 3 0 1 1431# e/i| Arr [1] [2] | i j k | N | 1 1432 0 -1 0 0 0 0 0 0 2 ## A 1433 0 0 -1 0 1 0 0 0 0 ## [i] 1434 0 0 0 -1 0 0 1 0 0 ## [k] 1435 1436READ 14373 9 3 3 0 1 1438# e/i| Arr [1] [2] | i j k | N | 1 1439 0 -1 0 0 0 0 0 0 3 ## B 1440 0 0 -1 0 0 0 1 0 0 ## [k] 1441 0 0 0 -1 0 1 0 0 0 ## [j] 1442 1443# ---------------------------------------------- 2.4 Body 1444# Statement body is provided 14451 1446# Statement body 1447<body> 1448# Number of original iterators 14493 1450# Original iterator names 1451i j k 1452# Statement body expression 1453C[i][j] = C[i][j] + A[i][k] * B[k][j]; 1454</body> 1455 1456# =============================================== Extensions 1457<comment> 1458May the power of the polyhedral model be with you. 1459</comment> 1460 1461</OpenScop> 1462@end example 1463 1464 1465We will not describe here precisely the structure and the components of this 1466output, this is described in depth in a further section 1467(@pxref{OpenScop File Format Specification}). This format 1468has been designed to be a possible input or output file format of most of 1469polyhedral compilation tools. If you read the description of the polyhedral 1470representation of programs, you should already feel familiar with this file 1471format (@pxref{Polyhedral Representation}). 1472 1473 1474@c %/************************************************************************* 1475@c % * FILE FORMAT SPECIFICATION * 1476@c % *************************************************************************/ 1477@node OpenScop File Format Specification 1478@section OpenScop File Format Specification 1479 1480@menu 1481* Relations:: 1482* Generics:: 1483@end menu 1484 1485The following grammar describes the structure of the 1486OpenScop file format where terminals are preceeded by "_". Except 1487stated otherwise, there can be at most one terminal per line in the file. 1488Moreover, each line may finish with a comment, starting by the @samp{#} 1489character. Each relevant part will be explained in more details momentarily: 1490 1491@example 1492OpenScop ::= Start_tag Data End_tag 1493Start_tag ::= "<OpenScop>" 1494End_tag ::= "</OpenScop>" 1495Data ::= Context Statements Extension_list 1496Context ::= Language Parameter_Domain Parameters 1497Statements ::= Nb_statements Statement_list 1498Statement_list ::= Statement Statement_list | (void) 1499Relation_list ::= _Relation Relation_list | (void) 1500Extension_list ::= _Generic Extension_list | (void) 1501Statement ::= Statement_relations Body 1502Body ::= "0" | "1" Body_information 1503Parameters ::= "0" | "1" Parameter_information 1504Statement_relations ::= Nb_relations Relation_List 1505Parameter_domain ::= _Relation 1506Language ::= _String 1507Nb_Relations ::= _Integer 1508Parameter_information ::= _Generic 1509Body_information ::= _Generic 1510@end example 1511 1512The @samp{Context} and the @samp{Statements} parts compose the 1513@emph{core part}, i.e., what is strictly necessary to build 1514a complete source to source framework based on OpenSCop: 1515@itemize @bullet 1516@item @samp{Context} represents the global information of the SCoP. It 1517 consists on the target language, the global constraints on the 1518 parameters and optionally the parameter information which may be necessary 1519 for the code generation process. The constraints on the parameters 1520 are represented as a relation (@pxref{Context Domain Relation}). 1521 The parameter information is optional. It is preceded by a 1522 boolean which precises whether it is provided or not. 1523 It is a generic information (@pxref{Generics}), a @code{strings} 1524 (@pxref{Strings Generic}) for instance. 1525@item @samp{Statements} represents the information about the statements. 1526 @samp{Nb_statements} is the number of statements in the SCoP, 1527 i.e. the number of @samp{Statement} items in the @samp{Statement_list}. 1528 @samp{Statement} represents the information on a given statement. 1529 To each statement is associated a list of relations and, 1530 optionaly, a body. The list of relations may include 1531 one iteration domain (@pxref{Iteration Domain Relation}), 1532 one scattering relation (@pxref{Scattering Relation}) 1533 and several access relations (@pxref{Access Relation}). 1534 There is no mandatory ordering, but for consistency reason it would 1535 be much appreciated that iteration domain comes first (if present) 1536 then scattering (if present), then accesses (if present). 1537 The statement body is an optional information. It is preceded by a 1538 boolean which precises whether it is provided or not. 1539 It is a generic information (@pxref{Generics}), a @code{body} 1540 (@pxref{Body Generic}) for instance. 1541@end itemize 1542 1543The @samp{Extension_list} represents the @emph{extension part} and may contain 1544an arbitrary number of generic informations (@pxref{Generics}). 1545Few examples of possible extensions are presented in a further 1546section (@pxref{Extensions}). 1547 1548As shown by the grammar, the input file describes the various pieces of 1549information based on strings, integers, @emph{relations} and @emph{generics}. 1550Relations and Generics are specific to OpenScop and are described in depth 1551in the following Sections (@pxref{Relations} and @pxref{Generics}). 1552 1553 1554@c %/************************************************************************* 1555@c % * RELATIONS * 1556@c % *************************************************************************/ 1557@node Relations 1558@subsection Relations 1559 1560@menu 1561* Iteration Domain Relation:: 1562* Context Domain Relation:: 1563* Scattering Relation:: 1564* Access Relation:: 1565@end menu 1566 1567@emph{Relations} are the essence of the OpenScop format and contain the 1568"polyhedral" information. They are used to describe either an iteration 1569domain, or a context domain, or a scattering or a memory access. 1570 1571We use the relation term as a shortcut to denote a 1572union of convex relations, each element of the union being described by a set of 1573constraints in an extended PolyLib format (@pxref{Wil93}). 1574The number of elements in the union is given by an integer on the first line, 1575optionally followed by a comment starting with @samp{#}. 1576This number of elements can be omitted when there is only one element. 1577Each element in the union has the following syntax: 1578 1579@enumerate 1580@item Some optional comment lines beginning with @samp{#}. 1581@item A line with the type of the relation, possibly followed by comments. 1582 The type can be one of the following: 1583 @itemize @bullet 1584 @item @code{UNDEFINED}: generic relation, 1585 @item @code{CONTEXT}: for context information, 1586 @item @code{DOMAIN}: for iteration domains, 1587 @item @code{SCATTERING}: for scattering relation, 1588 @item @code{READ}: for read accesses, 1589 @item @code{WRITE}: for write accesses, 1590 @item @code{MAY_WRITE}: for may-write accesses, 1591 @end itemize 1592@item A line with 6 numbers, possibly followed by comments: 1593 @enumerate 1594 @item the number of rows of the constraint matrix, 1595 @item the number of columns of the constraint matrix, 1596 @item the number of @emph{output dimensions}, 1597 @item the number of @emph{input dimension}, 1598 @item the number of @emph{local dimensions} 1599 (existentially quantified dimensions), 1600 @item the number of @emph{parameters}. 1601 @end enumerate 1602 The sum of the last four numbers should be equal to the number of columns 1603 minus two. The remaining two columns are the equality/inequality 1604 indicator and the constant term. The number of parameters should be the 1605 same for all relations in the entire OpenScop file or data structure. 1606@item The constraint rows. Each row corresponds to a constraint the 1607 relation has to satisfy. Each row must be on a single line and is possibly 1608 followed by comments. The constraint is an equality @math{p(x) = 0} if the 1609 first element is 0, an inequality @math{p(x) \geq 0} if the first element 1610 is 1. The next elements are the coefficients of the output dimensions, 1611 followed by coefficients of the input dimensions, the existentially 1612 quantified dimensions and finally the parameters. 1613 The last element is the constant term. 1614@end enumerate 1615 1616This representation is the basis for several purposes. Examples for 1617iteration domains (@pxref{Iteration Domain Relation}), context domains 1618(@pxref{Context Domain Relation}), scattering 1619relations (@pxref{Scattering Relation}) and 1620access relations (@pxref{Access Relation}) are provided in further sections. 1621 1622@c %/************************** ITERATION DOMAIN **************************** 1623@node Iteration Domain Relation 1624@subsubsection Iteration Domain Relation 1625 1626Iteration domain represents the set of instances of the corresponding statement. 1627OpenScop iteration domains are represented as relations with the following 1628conventions: 1629@itemize @bullet 1630@item the type is @code{DOMAIN}, 1631@item there is 0 input dimension, 1632@item loop iterators correspond to output dimensions. 1633@end itemize 1634 1635@noindent For instance, assuming that @samp{i}, @samp{j} and @samp{k} are the loop 1636iterators and @samp{M} and @samp{N} are the parameters, the domain defined by 1637the following constraints : 1638 1639@tex 1640$$ 1641\hbox{$ \cases{ -i + M &$\geq 0$\cr 1642 -j + N &$\geq 0$\cr 1643 i + j - k &$\geq 0$}$} 1644$$ 1645@end tex 1646@ifnottex 1647@example 1648@group 1649 -i + M >= 0 1650 -j + N >= 0 1651i + j - k >= 0 1652@end group 1653@end example 1654@end ifnottex 1655 1656@noindent can be written in the input file as follows: 1657 1658@example 1659@group 1660# This is an iteration domain 1661DOMAIN 16621 # Number of relations in the union 16633 7 3 0 0 2 # 3 rows, 7 cols: 3 output dims and 2 params 1664# e/i| i j k | M N | 1 1665 1 -1 0 0 1 0 0 # -i + M >= 0 1666 1 0 -1 0 0 1 0 # -j + N >= 0 1667 1 1 1 -1 0 0 0 # i + j - k >= 0 1668@end group 1669@end example 1670 1671@noindent Equivalently, it can be written in the following way as the number 1672of relations in the union can be omitted if it is 1: 1673 1674@example 1675@group 1676# This is an iteration domain 1677DOMAIN 16783 7 3 0 0 2 # 3 rows, 7 cols: 3 output dims and 2 params 1679# e/i| i j k | M N | 1 1680 1 -1 0 0 1 0 0 # -i + M >= 0 1681 1 0 -1 0 0 1 0 # -j + N >= 0 1682 1 1 1 -1 0 0 0 # i + j - k >= 0 1683@end group 1684@end example 1685 1686@noindent As an example for unions, let us consider the following pseudo-code: 1687 1688@example 1689@group 1690for (i = 1; i <= N; i++) @{ 1691 if ((i >= M) || (i <= 2*M)) 1692 S1(i); 1693@} 1694@end group 1695@end example 1696 1697@noindent The iteration domain of @samp{S1} can be divided into two 1698relations and written in the OpenScop file as follows: 1699 1700@example 1701@group 1702# This is an iteration domain 1703DOMAIN 17042 # Number of relations in the union 1705# Union part No.1 17063 5 1 0 0 2 # 3 rows, 5 cols: 1 output dim and 2 params 1707# e/i| i | M N | 1 1708 1 1 0 0 -1 # i >= 1 1709 1 -1 0 1 0 # i <= N 1710 1 1 -1 0 0 # i >= M 1711# Union part No.2 17123 5 1 0 0 2 # 3 rows, 5 cols: 1 output dim and 2 params 1713# e/i| i | M N | 1 1714 1 1 0 0 -1 # i >= 1 1715 1 -1 0 1 0 # i <= N 1716 1 -1 2 0 0 # i <= 2*M 1717@end group 1718@end example 1719 1720@noindent As an example for local dimensions (existentially quantified 1721dimensions), let us consider the following pseudo-code: 1722 1723@example 1724@group 1725for (i = 1; i <= N; i++) @{ 1726 if ((i % 2) == 0) 1727 S1(i); 1728@} 1729@end group 1730@end example 1731 1732@noindent The iteration domain of @samp{S1} is composed of all even 1733integer values between 1 and N. The "divisible by two" constraint can 1734be expressed as follows: there exists an integer @samp{ld} such that 1735@samp{i = 2*ld}. We encode this thanks to a new local dimension: 1736 1737@example 1738@group 1739# This is an iteration domain 1740DOMAIN 17413 5 1 0 1 1 # 3 rows, 5 cols: 1 output dim, 1 local dim, 1 param 1742# e/i| i |ld | N | 1 1743 0 1 -2 0 0 # i = 2*ld 1744 1 1 0 0 1 # i >= 1 1745 1 -1 0 1 0 # i <= N 1746@end group 1747@end example 1748 1749 1750@c %/************************** CONTEXT DOMAIN ****************************** 1751@node Context Domain Relation 1752@subsubsection Context Domain Relation 1753 1754The context domain is a particular case of iteration domain 1755(@pxref{Iteration Domain Relation}) where there are only 1756constraints about parameters (no loop iterators). Hence it is the same 1757as an iteration domain, with the following conventions: 1758@itemize @bullet 1759@item the type is @code{CONTEXT}, 1760@item there is 0 input dimension, 1761@item there is 0 output dimension. 1762@end itemize 1763 1764 1765@c %/************************* SCATTERING RELATION ************************** 1766@node Scattering Relation 1767@subsubsection Scattering Relation 1768 1769Scattering relation maps an iteration domain to a logical time and/or 1770space (and/or) anything. 1771OpenScop scattering information is represented as relations 1772(@pxref{Relations}) with the following conventions: 1773 1774@itemize @bullet 1775@item the type is @code{SCATTERING}, 1776@item output dimensions correspond to scattering dimensions, 1777@item loop iterators correspond to input dimensions. 1778@end itemize 1779 1780As an example of a scattering relation and 1781assuming that @samp{i}, @samp{j} and @samp{k} are the loop 1782iterators and @samp{M} and @samp{N} are the parameters, take for instance: 1783@tex 1784$\theta_{S}(i,j,k) = (j+2,3*i+j,k+N+1).$ 1785@end tex 1786@ifnottex 1787@example 1788T_@{S@}(i,j,k) = (j+2,3*i+j,k+N+1). 1789@end example 1790@end ifnottex 1791We can represent it in the following way: 1792 1793@example 1794@group 1795# A scattering relation 1796SCATTERING 1797# 3 rows, 10 columns: 3 scattering dimensions, 3 iterators, 2 parameters 17983 10 3 3 0 2 1799# e/i|s1 s2 s3 | i j k | M N | 1 1800 0 -1 0 0 0 1 0 0 0 2 # s1 = j+2 1801 0 0 -1 0 3 1 0 0 0 0 # s2 = 3*i+j 1802 0 0 0 -1 0 0 1 0 1 1 # s3 = k+N+1 1803@end group 1804@end example 1805 1806@c %/************************** ACCESS RELATION ***************************** 1807@node Access Relation 1808@subsubsection Access Relation 1809 1810Access relation maps an iteration domain to an array space. 1811Each array accessed in the SCoP has a unique identification number. 1812OpenScop relation information is represented as relations 1813(@pxref{Relations}) with the following conventions: 1814 1815@itemize @bullet 1816@item the type is one of the following: 1817 @itemize @bullet 1818 @item @code{READ}, for read accesses, 1819 @item @code{WRITE}, for write accesses, 1820 @item @code{MAY_WRITE}, for may write accesses, 1821 @end itemize 1822@item output dimensions correspond to the array identifier and dimensions, 1823@item the first output dimension corresponds to the array identifier, 1824@item the (i+1)th output dimension corresponds to the ith array dimension (i>1), 1825@item loop iterators correspond to input dimensions. 1826@end itemize 1827 1828As an example of a scattering relation and 1829assuming that @samp{i}, @samp{j} and @samp{k} are the loop 1830iterators and @samp{M} and @samp{N} are the parameters, let us consider 1831the array access @code{A[2*i+j][j][i+N]} (the identifier of @code{A} is 42), 1832and let us suppose this is a read access. Its representation would be the 1833following: 1834 1835@example 1836@group 1837# A read access relation 1838READ 1839# 4 rows, 11 columns: 4 array dimensions, 3 iterators, 2 parameters 18404 11 4 3 0 2 1841# e/i|Arr [1] [2] [3]| i j k | M N | 1 1842 0 -1 0 0 0 0 0 0 0 0 42 # A 1843 0 0 -1 0 0 2 1 0 0 0 0 # [2*i+j] 1844 0 0 0 -1 0 0 1 0 0 0 0 # [j] 1845 0 0 0 0 -1 1 0 0 0 1 0 # [i+N] 1846@end group 1847@end example 1848 1849To understand this representation, consider that OpenScop accesses 1850are general memory accesses and not array accesses. The memory is 1851seen as a big array @code{Mem} while usual array names correspond to 1852the first dimension. Hence our example translates to @code{Mem[42][2*i+j][j][i+N]}. 1853 1854Unions of access relations are allowed. In this case, each union part must 1855refer at the same array identifier, and the number of dimensions must be 1856consistent. 1857 1858@c %/************************************************************************* 1859@c % * GENERICS * 1860@c % *************************************************************************/ 1861@node Generics 1862@subsection Generics 1863@menu 1864* Strings Generic:: 1865* Body Generic:: 1866@end menu 1867 1868@emph{Generics} represent any elaborated non-polyhedral information in the 1869OpenScop format. They are used to represent the parameter information, the 1870statement body information as well as the extensions. Each generic information 1871is delimited using XML-like tags corresponding to its URI (Unique Resource 1872Identifier), For instance, if the generic has the URI @code{foo}, the begin 1873tag is @code{<foo>} and the end tag is @code{</foo>}). 1874 1875Two generics, namely @code{strings} (@pxref{Strings Generic}) and 1876@code{body} (@pxref{Body Generic}) are part of the OpenScop 1877specification to provide the minimum, stricly necessary information to 1878build a complete source-to-source polyhedral framework based on OpenScop. 1879However, generics can be basically @emph{anything} as long as they are 1880properly delimited. OpenScop implementations will simply ignore 1881non-supported generics and warn the user with the mention of the 1882non-supported URIs. Support of new generics will be added throught the 1883extension mechanism. 1884 1885@c --------------------------------------------------------------------------- 1886 1887@node Strings Generic 1888@subsubsection Strings Generic 1889 1890The purpose of the @code{strings} generic is to represent a list of 1891textual strings on one line (which may be used, e.g., to represent the list of 1892parameter names in the order used in the relation). Its URI is @code{strings} 1893and its file format respects the following grammar: 1894@example 1895Strings_generic ::= "<strings>" Strings "</strings>" 1896Strings ::= _String String_list | (void) 1897@end example 1898 1899@noindent A possible example of textual @code{strings} is the following: 1900@example 1901@group 1902<strings> 1903Not one sentence but 6 strings! 1904</strings> 1905@end group 1906@end example 1907 1908@c --------------------------------------------------------------------------- 1909 1910@node Body Generic 1911@subsubsection Body Generic 1912 1913The purpose of the @code{body} generic is to represent the textual 1914information about a statement. It contains the number of original iterators on 1915the first line, the list of original iterators on the second 1916line (the loop counters of the statement surrounding loops in the original 1917program) and the original textual body expression on the third line. 1918Its URI is @code{body} and its file format respects the following grammar 1919(the @code{String} rule is reused, @pxref{Strings Generic}): 1920@example 1921Body_generic ::= "<body>" Body "</body>" 1922Body ::= Nb_iterators Iterator_list Expression 1923Nb_iterators ::= _Integer 1924Iterator_list ::= Strings 1925Expression ::= Strings 1926@end example 1927 1928@noindent A possible example of textual @code{body} is the following: 1929@example 1930@group 1931<body> 1932# Number of original iterators 19332 1934# Original iterators 1935i j 1936# Original statement expression 1937A[i+j] += B[i] * C[j]; 1938</body> 1939@end group 1940@end example 1941 1942 1943@c %/************************************************************************* 1944@c % * DATA STRUCTURE SPECIFICATION * 1945@c % *************************************************************************/ 1946@node OpenScop Data Structure Specification 1947@section OpenScop Data Structure Specification 1948 1949@menu 1950* osl_relation_t:: 1951* osl_relation_list_t:: 1952* osl_interface_t:: 1953* osl_generic_t:: 1954* osl_strings_t:: 1955* osl_body_t:: 1956* osl_statement_t:: 1957* osl_scop_t:: 1958@end menu 1959 1960The OpenScop specification offers a small set of C data structures devoted to 1961represent a SCoP in memory in a convenient way. Using them in some tool or 1962library may greatly facilitate its interaction with other tools or libraries 1963which rely on this representation as well. Every field may not be useful for 1964a given tool or library. A general rule for all the data structure is 1965that a @code{NULL} pointer or a -1 integer value means the information is 1966not present. Contrary to engineering time, memory is cheap today, so it's much 1967probably not a big deal that some fields are left empty. Every field may not 1968be enough for a given tool or library. In this case it is much recommended 1969to provide a new extension which may be reused by other users 1970(@pxref{Extensions}). 1971 1972Each tool or library may have its own implementation of the OpenScop 1973data structures. The type names should not be the same as those provided 1974as an example here (they correspond to the OpenScop Library implementation). 1975The names of the fields, and their ordering, should however be the same. In this 1976way, the interaction between tools and libraries should be as simple as a cast. 1977 1978Before reading at the OpenScop data structures, it is much recommended to 1979read at the OpenScop file format description, as it is quite close to this 1980representation (@pxref{OpenScop File Format Specification}). 1981 1982 1983@node osl_relation_t 1984@subsection osl_relation_t 1985 1986@example 1987@group 1988struct osl_relation @{ 1989 int type; /* What this relation is encoding */ 1990 int precision; /* Precision of the matrix elements */ 1991 int nb_rows; /* Number of rows */ 1992 int nb_columns; /* Number of columns */ 1993 int nb_output_dims; /* Number of output dimensions */ 1994 int nb_input_dims; /* Number of input dimensions */ 1995 int nb_local_dims; /* Number of local dimensions */ 1996 int nb_parameters; /* Number of parameters */ 1997 void ** m; /* Matrix of constraints */ 1998 struct osl_relation * next; /* Next relation in the union */ 1999@}; 2000typedef struct osl_relation osl_relation_t; 2001typedef struct osl_relation * osl_relation_p; 2002@end group 2003@end example 2004 2005@noindent The @code{osl_relation_t} structure stores a part of an 2006union of relations. A union of relation is a @code{NULL}-terminated 2007linked list of union parts (@code{next} field). The @code{type} field 2008may provide some information about what the relation is encoding: 2009@itemize @bullet 2010@item -1: undefined (@code{OSL_UNDEFINED}), 2011@item 2: context domain (@code{OSL_TYPE_CONTEXT}), 2012@item 3: iteration domain (@code{OSL_TYPE_DOMAIN}), 2013@item 4: scattering relation (@code{OSL_TYPE_SCATTERING}), 2014@item 6: read access relation (@code{OSL_TYPE_READ}), 2015@item 7: write access relation (@code{OSL_TYPE_WRITE}), 2016@item 8: may write access relation (@code{OSL_TYPE_MAY_WRITE}), 2017@end itemize 2018The various numbers provide the details on the relation itself 2019(@pxref{Relations}) while the @code{m} field points to 2020the constraint matrix. The precision of the constraint matrix elements is 2021provided by the @code{precision} field. It can take the following 2022values: 2023@itemize @bullet 2024@item 32: 32 bits precision, elements are @code{long int} 2025 (@code{OSL_PRECISION_SP}), 2026@item 64: 64 bits precision, elements are @code{long long int} 2027 (@code{OSL_PRECISION_DP}), 2028@item 0: multiple precision, elements are GNU GMP Library's 2029 @code{mpz_t} (@code{OSL_PRECISION_MP}). 2030@end itemize 2031 2032@c --------------------------------------------------------------------------- 2033 2034@node osl_relation_list_t 2035@subsection osl_relation_list_t 2036 2037@example 2038@group 2039struct osl_relation_list @{ 2040 osl_relation_p elt; /* Element of the list */ 2041 struct osl_relation_list * next; /* Next element of the list */ 2042@}; 2043typedef struct osl_relation_list osl_relation_list_t; 2044typedef struct osl_relation_list * osl_relation_list_p; 2045@end group 2046@end example 2047 2048@noindent The @code{osl_relation_list_t} structure is a @code{NULL}-terminated 2049linked list of @code{osl_relation_t} data structures. 2050@code{elt} is a relation element of the list and @code{next} is the pointer to 2051the next element of the list. 2052 2053@c --------------------------------------------------------------------------- 2054 2055@node osl_interface_t 2056@subsection osl_interface_t 2057 2058@example 2059@group 2060typedef void (*osl_idump_f) (FILE *, void *, int); 2061typedef char * (*osl_sprint_f)(void *); 2062typedef void * (*osl_sread_f) (char *); 2063typedef void * (*osl_malloc_f)(); 2064typedef void (*osl_free_f) (void *); 2065typedef void * (*osl_clone_f) (void *); 2066typedef int (*osl_equal_f) (void *, void *); 2067 2068struct osl_interface @{ 2069 char * URI; /* Unique interface identifier string */ 2070 osl_idump_f idump; /* Pointer to the idump function */ 2071 osl_sprint_f sprint; /* Pointer to the sprint function */ 2072 osl_sread_f sread; /* Pointer to the sread function */ 2073 osl_malloc_f malloc; /* Pointer to the malloc function */ 2074 osl_free_f free; /* Pointer to the free function */ 2075 osl_clone_f clone; /* Pointer to the clone function */ 2076 osl_equal_f equal; /* Pointer to the equal function */ 2077 struct osl_interface * next; /* Next interface in the list */ 2078@}; 2079typedef struct osl_interface osl_interface_t; 2080typedef struct osl_interface * osl_interface_p; 2081@end group 2082@end example 2083 2084@noindent The @code{osl_interface_t} structure represents a 2085node in a @code{NULL}-terminated list of interfaces. Each node stores the 2086@emph{interface} of a generic OpenScop object, i.e., its unique name 2087(@code{URI}) and the function pointers to all the base functions it has 2088to provide. Extension providers will find information relative to those 2089functions in the OpenScop Library description (@pxref{Base Functions}) 2090and the section dedicated to writing extensions 2091(@pxref{Extension Development}). 2092 2093@c --------------------------------------------------------------------------- 2094 2095@node osl_generic_t 2096@subsection osl_generic_t 2097 2098@example 2099@group 2100struct osl_generic @{ 2101 void * data; /* Pointer to some data */ 2102 osl_interface_p interface; /* Interface to work with the data */ 2103 struct osl_generic * next; /* Pointer to the next generic */ 2104@}; 2105typedef struct osl_generic osl_generic_t; 2106typedef struct osl_generic * osl_generic_p; 2107@end group 2108@end example 2109 2110@noindent The @code{osl_generic_t} structure represents a node in a 2111@code{NULL}-terminated list of generic elements. It stores some data 2112and operations with no pre-defined type. The information is accessible 2113through the @code{data} pointer while the type and operations are 2114accessible through the @code{interface} pointer. It is used to represent 2115data that are allowed to differ in implementations, such as symbols and 2116extensions. 2117 2118@c --------------------------------------------------------------------------- 2119 2120@node osl_strings_t 2121@subsection osl_strings_t 2122 2123@example 2124@group 2125struct osl_string @{ 2126 char ** string; /* NULL-terminated array of strings */ 2127@}; 2128typedef struct osl_strings osl_strings_t; 2129typedef struct osl_strings * osl_strings_p; 2130@end group 2131@end example 2132 2133@noindent The @code{osl_strings_t} structure represents a NULL-terminated 2134list of C character strings. It is encapsulated into a structure to allow 2135its manipulation through a generic type. 2136 2137@c --------------------------------------------------------------------------- 2138 2139@node osl_body_t 2140@subsection osl_body_t 2141 2142@example 2143@group 2144struct osl_body @{ 2145 osl_strings_p iterators; /* Original iterators */ 2146 osl_strings_p expression; /* Original statement expression */ 2147@}; 2148typedef struct osl_body osl_body_t; 2149typedef struct osl_body * osl_body_p; 2150@end group 2151@end example 2152 2153@noindent The @code{osl_body_t} structure stores a statement body in a 2154textual form. The complete original expression (directly copy-pasted 2155from the original code) is in the expression field while the textual forms 2156of the original iterators are in the iterators field. They may be used for 2157substitutions inside the expression. 2158 2159@c --------------------------------------------------------------------------- 2160 2161@node osl_statement_t 2162@subsection osl_statement_t 2163 2164@example 2165@group 2166struct osl_statement @{ 2167 osl_relation_p domain; /* Iteration domain */ 2168 osl_relation_p scattering; /* Scattering relation */ 2169 osl_relation_list_p access; /* List of array access relations */ 2170 osl_generic_p body; /* Original statement body */ 2171 void * usr; /* A user-defined field */ 2172 struct osl_statement * next; /* Next statement in the list */ 2173@}; 2174typedef struct osl_statement osl_statement_t; 2175typedef struct osl_statement * osl_statement_p; 2176@end group 2177@end example 2178 2179@noindent The @code{osl_statement_t} structure represents a node 2180in a @code{NULL}-terminated linked list of statements. Each node contains the 2181useful information for a given statement to process it within a polyhedral 2182framework. The order in the list may matter for naming conventions 2183(e.g. "S1" for the first statement in the list). The iteration domain 2184and the scattering are represented using an @code{osl_relation_p} 2185structure while the accesses are using a list of 2186relations: one for each memory access in the statement. 2187The @code{body} field should provide information about the statement body 2188(since it has a generic type, the specification is not strict about how it 2189is used), e.g., using the @code{osl_body_t} data structure (@pxref{osl_body_t}). 2190It is also possible to use the @code{usr} field, but it has to be 2191totally managed by the user. 2192 2193@c --------------------------------------------------------------------------- 2194 2195@node osl_scop_t 2196@subsection osl_scop_t 2197@example 2198@group 2199struct osl_scop @{ 2200 int version; /* Version of the data structure */ 2201 char * language; /* Target language */ 2202 osl_relation_p context; /* Constraints on the parameters */ 2203 osl_generic_p parameters; /* Information about parameters */ 2204 osl_statement_p statement; /* Statement list */ 2205 osl_interface_p registry; /* Registered extension interfaces */ 2206 osl_generic_p extension; /* Extension list */ 2207 void * usr; /* A user-defined field */ 2208 struct osl_scop * next; /* Next scop in the list */ 2209@}; 2210typedef struct osl_scop osl_scop_t; 2211typedef struct osl_scop * osl_scop_p; 2212@end group 2213@end example 2214 2215@noindent @code{osl_scop_t} represents a node in a 2216@code{NULL}-terminated list of scops. It stores the useful informations 2217of a static control part of a program to process it within a polyhedral 2218framework. To prepare OpenScop specification evolution, the @code{version} 2219field tells the version of the data structure. It should be set to 1 for 2220now (and hopefully a very, very, long time). 2221First, it contains the informations about the context. The target language 2222in expressed in the @code{language} field. The constraints on the 2223global parameters are detailed in the @code{context} field. 2224The @code{paremeters} field should provide information about the 2225parameters (since it has a generic type, the specification is not strict 2226about how it is used), e.g., using the @code{osl_strings_t} data structure 2227(@pxref{osl_strings_t}). 2228Finally, it contains the list of statements @code{statement}, the list 2229of registered interfaces for generic types @code{registry} and the list of 2230extentions @code{extension}. 2231It is also possible to use the @code{usr} field, but it has to be 2232totally managed by the user. 2233 2234As an example, let us consider again the matrix multiply program 2235(@pxref{Preliminary Example}). 2236The next figure gives a possible representation in memory for this 2237SCoP thanks to the OpenScop data structures (it has been actually printed 2238by the @code{osl_scop_dump} function), note that symbols like 2239parameters, original iterators and statement expression are represented 2240with an @code{osl_strings_t} which does not belong to the 2241specification but to the OpenScop Library implementation: 2242 2243@c @smallexample 2244@example 2245+-- osl_scop_t 2246| | 2247| Version: 1 2248| | 2249| Language: C 2250| | 2251| +-- osl_relation_t (CONTEXT, 32 bits) 2252| | 1 3 0 0 0 1 2253| | [ 1 1 -1 ] 2254| | 2255| +-- osl_generic_t 2256| | | 2257| | +-- osl_interface_t: URI = strings 2258| | | 2259| | +-- osl_strings_t: N 2260| | | 2261| | 2262| +-- osl_statement_t (S1) 2263| | | 2264| | +-- osl_relation_t (DOMAIN, 32 bits) 2265| | | 4 5 2 0 0 1 2266| | | [ 1 1 0 0 0 ] 2267| | | [ 1 -1 0 1 -1 ] 2268| | | [ 1 0 1 0 0 ] 2269| | | [ 1 0 -1 1 -1 ] 2270| | | 2271| | +-- osl_relation_t (SCATTERING, 32 bits) 2272| | | 5 10 5 2 0 1 2273| | | [ 0 -1 0 0 0 0 0 0 0 0 ] 2274| | | [ 0 0 -1 0 0 0 1 0 0 0 ] 2275| | | [ 0 0 0 -1 0 0 0 0 0 0 ] 2276| | | [ 0 0 0 0 -1 0 0 1 0 0 ] 2277| | | [ 0 0 0 0 0 -1 0 0 0 0 ] 2278| | | 2279| | +-- osl_relation_list_t 2280| | | | 2281| | | +-- osl_relation_t (WRITE, 32 bits) 2282| | | | 3 8 3 2 0 1 2283| | | | [ 0 -1 0 0 0 0 0 1 ] 2284| | | | [ 0 0 -1 0 1 0 0 0 ] 2285| | | | [ 0 0 0 -1 0 1 0 0 ] 2286| | | | 2287| | | 2288| | +-- osl_generic_t 2289| | | | 2290| | | +-- osl_interface_t: URI = body 2291| | | | 2292| | | +-- osl_strings_t: i j 2293| | | | 2294| | | +-- osl_strings_t: C[i][j] = 0.0; 2295| | | | 2296| | | 2297| | V 2298| | osl_statement_t (S2) 2299| | | 2300| | +-- osl_relation_t (DOMAIN, 32 bits) 2301| | | 6 6 3 0 0 1 2302| | | [ 1 1 0 0 0 0 ] 2303| | | [ 1 -1 0 0 1 -1 ] 2304| | | [ 1 0 1 0 0 0 ] 2305| | | [ 1 0 -1 0 1 -1 ] 2306| | | [ 1 0 0 1 0 0 ] 2307| | | [ 1 0 0 -1 1 -1 ] 2308| | | 2309| | +-- osl_relation_t (SCATTERING, 32 bits) 2310| | | 7 13 7 3 0 1 2311| | | [ 0 -1 0 0 0 0 0 0 0 0 0 0 0 ] 2312| | | [ 0 0 -1 0 0 0 0 0 1 0 0 0 0 ] 2313| | | [ 0 0 0 -1 0 0 0 0 0 0 0 0 0 ] 2314| | | [ 0 0 0 0 -1 0 0 0 0 1 0 0 0 ] 2315| | | [ 0 0 0 0 0 -1 0 0 0 0 0 0 1 ] 2316| | | [ 0 0 0 0 0 0 -1 0 0 0 1 0 0 ] 2317| | | [ 0 0 0 0 0 0 0 -1 0 0 0 0 0 ] 2318| | | 2319| | +-- osl_relation_list_t 2320| | | | 2321| | | +-- osl_relation_t (WRITE, 32 bits) 2322| | | | 3 9 3 3 0 1 2323| | | | [ 0 -1 0 0 0 0 0 0 1 ] 2324| | | | [ 0 0 -1 0 1 0 0 0 0 ] 2325| | | | [ 0 0 0 -1 0 1 0 0 0 ] 2326| | | | 2327| | | V 2328| | | osl_relation_list_t 2329| | | | 2330| | | +-- osl_relation_t (READ, 32 bits) 2331| | | | 3 9 3 3 0 1 2332| | | | [ 0 -1 0 0 0 0 0 0 1 ] 2333| | | | [ 0 0 -1 0 1 0 0 0 0 ] 2334| | | | [ 0 0 0 -1 0 1 0 0 0 ] 2335| | | | 2336| | | V 2337| | | osl_relation_list_t 2338| | | | 2339| | | +-- osl_relation_t (READ, 32 bits) 2340| | | | 3 9 3 3 0 1 2341| | | | [ 0 -1 0 0 0 0 0 0 2 ] 2342| | | | [ 0 0 -1 0 1 0 0 0 0 ] 2343| | | | [ 0 0 0 -1 0 0 1 0 0 ] 2344| | | | 2345| | | V 2346| | | osl_relation_list_t 2347| | | | 2348| | | +-- osl_relation_t (READ, 32 bits) 2349| | | | 3 9 3 3 0 1 2350| | | | [ 0 -1 0 0 0 0 0 0 3 ] 2351| | | | [ 0 0 -1 0 0 0 1 0 0 ] 2352| | | | [ 0 0 0 -1 0 1 0 0 0 ] 2353| | | | 2354| | | 2355| | +-- osl_generic_t 2356| | | | 2357| | | +-- osl_interface_t: URI = body 2358| | | | 2359| | | +-- osl_strings_t: i j k 2360| | | | 2361| | | +-- osl_strings_t: C[i][j] = C[i][j] + A[i][k]*B[k][j]; 2362| | | | 2363| | | 2364| | 2365| +-- NULL interface 2366| | 2367| +-- NULL generic 2368| | 2369| 2370@end example 2371@c @end smallexample 2372 2373 2374@c %/************************************************************************* 2375@c % * EXTENSIONS * 2376@c % *************************************************************************/ 2377@node Extensions 2378@section Extensions 2379 2380The core part of the OpenScop representation embeds what is strictly 2381necessary to build a complete source-to-source polyhedral framework. 2382However it may not be enough. Hence, OpenScop offers a very flexible 2383extension part. Actually, the only constraint to build an extension is 2384to request the OpenScop maintainer for a unique extension name: its URI 2385(ask the maintainer through the OpenScop mailing list 2386@email{openscop-development@@googlegroups.com}). 2387 2388The policy to support extensions is the following and is pretty simple: an 2389OpenScop implementation is not required to support any extension. If it 2390is processing an OpenScop file or data structure which contains an 2391extension which is not supported, it must (1) warn the user with the 2392mention of the URI of the non-supported extension 2393and (2) ignore this extension. 2394 2395Extensions in an OpenScop file are provided after the core part, without 2396any specific order. Each extension is delimited using 2397XML-like tags corresponding to its URI (e.g., if the extension has the URI 2398@code{foo}, the begin tag is @code{<foo>} and the end tag is @code{</foo>}). 2399There is no specification or preferred way to write the extension body. 2400Extensions in an OpenScop data structure must be accessible through one 2401pointer. This pointer will be stored in the @code{data} field of an 2402@code{osl_generic_t} container (@pxref{osl_generic_t}). There must be only 2403one extension with the same URI in an OpenScop file or data structure. 2404 2405Extension writers may write a short documentation about their extension to 2406be added to this document. For consistency reason, this 2407documentation should comply to the documentation of the 2408@code{comment} option (@pxref{Comment Extension}). To describe the 2409file format, it is allowed to reuse the existing rules and terminals 2410present in the OpenScop file format description without defining them 2411(@pxref{OpenScop File Format Specification}). By sending a 2412documentation, you accept it to be added to this document. In 2413particular, the sender fully accepts the license and copyright notice. 2414 2415@menu 2416* Comment Extension:: 2417* Arrays Extension:: 2418* Scatnames Extension:: 2419* Coordinates Extension:: 2420* Irregular Extension:: 2421@end menu 2422 2423@c --------------------------------------------------------------------------- 2424 2425@node Comment Extension 2426@subsection Comment Extension 2427 2428@noindent @strong{Description} 2429@itemize @bullet 2430@item URI: @code{comment}. 2431@item Author: C@'edric Bastoul <cedric.bastoul@@u-psud.fr>. 2432@item Purpose: the @code{comment} extension stores a textual string. 2433@end itemize 2434 2435@noindent @strong{File Format} 2436 2437@noindent The @code{comment} extension file format respects the following 2438grammar: 2439@example 2440Comment_generic ::= "<comment>" Comment "</comment>" 2441Comment ::= _Text 2442@end example 2443 2444@noindent An example of textual @code{comment} extension is the following: 2445@example 2446@group 2447<comment> 2448This is a comment string. 2449</comment> 2450@end group 2451@end example 2452 2453@noindent @strong{Data Structure} 2454 2455@noindent The @code{comment} extension data structure is the following: 2456@example 2457@group 2458struct osl_comment @{ 2459 char * comment; /* Comment message as a 0-terminated string */ 2460@}; 2461typedef struct osl_comment osl_comment_t; 2462typedef struct osl_comment * osl_comment_p; 2463@end group 2464@end example 2465 2466@c --------------------------------------------------------------------------- 2467 2468 2469@node Scatnames Extension 2470@subsection Scatnames Extension 2471 2472@noindent @strong{Description} 2473@itemize @bullet 2474@item URI: @code{scatnames}. 2475@item Author: C@'edric Bastoul <cedric.bastoul@@u-psud.fr>. 2476@item Purpose: the @code{scatnames} extension provides a list of textual 2477scattering dimension names. 2478@end itemize 2479 2480@noindent @strong{File Format} 2481 2482@noindent The @code{scatnames} extension file format respects the following 2483grammar. It reuses the @code{Strings} description (@pxref{Strings Generic}): 2484@example 2485Scatnames_generic ::= "<scatnames>" Scatnames "</scatnames>" 2486Scatnames ::= Strings 2487@end example 2488 2489@noindent The list of scattering dimension names is provided on one single 2490line. The names are separated with spaces. A possible 2491example of such an extension is the following: 2492 2493@example 2494@group 2495<scatnames> 2496# List of scattering dimension names: 2497beta_0 i beta_1 j beta_2 2498</scatnames> 2499@end group 2500@end example 2501 2502@noindent @strong{Data Structure} 2503 2504@noindent The @code{scatnames} extension data structure is the following: 2505 2506@example 2507@group 2508struct osl_scatnames @{ 2509 osl_strings_p names; /* List of textual scattering dimension names. */ 2510@}; 2511typedef struct osl_scatnames osl_scatnames_t; 2512typedef struct osl_scatnames * osl_scatnames_p; 2513@end group 2514@end example 2515 2516@noindent The order of the scattering dimension names in the list corresponds 2517to the order of the scattering dimensions. 2518 2519@c --------------------------------------------------------------------------- 2520 2521 2522@node Arrays Extension 2523@subsection Arrays Extension 2524 2525@noindent @strong{Description} 2526@itemize @bullet 2527@item URI: @code{arrays}. 2528@item Author: C@'edric Bastoul <cedric.bastoul@@u-psud.fr>. 2529@item Purpose: the @code{arrays} extension provides a set of textual array 2530names corresponding to the array identifiers used in the access relations. 2531@end itemize 2532 2533@noindent @strong{File Format} 2534 2535@noindent The @code{arrays} extension file format respects the following 2536grammar: 2537@example 2538Arrays_generic ::= "<arrays>" Arrays "</arrays>" 2539Arrays ::= Nb_items Item_list 2540Item_List ::= Item Item_list | (void) 2541Item ::= Identifier Name 2542Nb_items ::= _Integer 2543Identifier ::= _Integer 2544Name ::= _String 2545@end example 2546 2547@noindent The number of array names is provided on the first line, 2548then each following line contains a couple identifier-name. 2549For instance, the following example is a correct textual @code{arrays} 2550extension. It corresponds to the array names of the preliminary example 2551(@pxref{Preliminary Example}): 2552 2553@example 2554@group 2555<arrays> 2556# Number of array names: 25573 25581 C # Identifier 1 corresponds to array name "C" 25593 B # Identifier 3 corresponds to array name "B" 25602 A # Identifier 2 corresponds to array name "A" 2561</arrays> 2562@end group 2563@end example 2564 2565@noindent @strong{Data Structure} 2566 2567@noindent The @code{arrays} extension data structure is the following: 2568 2569@example 2570@group 2571struct osl_arrays @{ 2572 int nb_names; /* Number of names */ 2573 int * id; /* Array of nb_names identifiers */ 2574 char ** names; /* Array of nb_names names */ 2575@}; 2576typedef struct osl_arrays osl_arrays_t; 2577typedef struct osl_arrays * osl_arrays_p; 2578@end group 2579@end example 2580 2581@noindent Each name has a name string and an identifier: the ith name has name 2582string @code{names[i]} and identifier @code{id[i]}. 2583 2584 2585@c --------------------------------------------------------------------------- 2586 2587@node Coordinates Extension 2588@subsection Coordinates Extension 2589 2590@noindent @strong{Description} 2591@itemize @bullet 2592@item URI: @code{coordinates}. 2593@item Author: C@'edric Bastoul <cedric.bastoul@@u-psud.fr>. 2594@item Purpose: the @code{coordinates} extension provides the information 2595about the SCoP location in the original code: the original file name/path, 2596the starting and ending lines of the SCoP in this file (inclusives) and 2597the indentation level. 2598@end itemize 2599 2600@noindent @strong{File Format} 2601 2602@noindent The @code{coordinates} extension file format respects the following 2603grammar: 2604@example 2605Coordinates_generic ::= "<coordinates>" Coordinates "</coordinates>" 2606Coordinates ::= File_name Start_line End_line Indentation 2607File_name ::= _String 2608Start_line ::= _Integer 2609End_line ::= _Integer 2610Indentation ::= _Integer 2611@end example 2612 2613@noindent The original file name where the SCoP has been extracted is 2614provided on the first line, then the starting line number of the SCoP, 2615then the ending line number of the SCoP, and lastly the indentation level 2616(the number of spaces characters each line of the SCoP starts with). 2617For instance, the following example is a correct textual 2618@code{coordinates} extension: 2619 2620@example 2621@group 2622<coordinates> 2623# File name 2624./test/ax-do.c 2625# Starting line 26269 2627# Ending line 262815 2629# Indentation 26302 2631</coordinates> 2632@end group 2633@end example 2634 2635@noindent @strong{Data Structure} 2636 2637@noindent The @code{coordinates} extension data structure is the following: 2638 2639@example 2640@group 2641struct osl_coordinates @{ 2642 char * name; /* File name */ 2643 int start; /* First line of the SCoP in the source file */ 2644 int end; /* Last line of the SCoP in the source file */ 2645 int indent; /* Indentation */ 2646@}; 2647typedef struct osl_coordinates osl_coordinates_t; 2648typedef struct osl_coordinates * osl_coordinates_p; 2649@end group 2650@end example 2651 2652 2653@c --------------------------------------------------------------------------- 2654 2655@node Irregular Extension 2656@subsection Irregular Extension 2657 2658 2659@c --------------------------------------------------------------------------- 2660 2661@node History 2662@section History 2663 2664OpenScop is a follow-up of Louis-No@"el Pouchet et al.'s ScopLib effort which 2665was itself based on C@'edric Bastoul et al.'s Clan tool. People involved in 2666OpenScop's genesis are: 2667@itemize @bullet 2668@item C@'edric Bastoul 2669@item Uday Bondhugula 2670@item Tobias Grosser 2671@item Louis-No@"el Pouchet 2672@item Sven Verdoolaege 2673@end itemize 2674 2675@c %/************************************************************************* 2676@c % * OpenScop LIBRARY * 2677@c % *************************************************************************/ 2678 2679@node OpenScop Library 2680@chapter OpenScop Library 2681 2682The OpenScop Library, or OSL for short, is an example implementation of the 2683OpenScop specification. Its API is not part of the OpenScop specification. 2684It offers basic functionalities to manipulate the OpenScop data structures 2685(allocate, free, copy, dump, etc.) and file format (read, print, etc.). 2686The OpenScop Library is @emph{not} a polyhedral library. OpenScop is an 2687exchange format, and the OpenScop Library reflects this. 2688 2689It is a Free Software using the 3-clause BSD License. 2690Programmers should feel free to use 2691it or copy/paste its code in any project, Open Source or not@footnote{Closed 2692source projects should consider to provide some OpenScop file input 2693and output, so they can be incorporated to any OpenScop-based tool chain.}. 2694 2695@menu 2696* Precision:: 2697* Base Functions:: 2698* Example of OpenScop Library Utilization:: 2699* Installation:: 2700* Documentation:: 2701* Development:: 2702@end menu 2703 2704@node Precision 2705@section Precision 2706 2707The OpenScop specification does not impose a specific type for the 2708constraint matrix elements. For a maximum flexibility, the OpenScop Library 2709offers an hybrid precision implementation. It supports 32 bits, 64 bits and 2710multiple precision (relying on GNU GMP) relations transparently. At relation 2711allocation time, users have two ways to set the precision. The first way is 2712to call an allocation function with a precision parameter. The second way is 2713to rely on the environment variable @code{OSL_PRECISION}. 2714The accepted values for this variable are @code{32} for 32 bits precision, 2715@code{64} for 64 bits precision and @code{0} for multiple precision. When this 2716variable is set, its value becomes the default precision for relation elements. 2717For instance, to ensure the OpenScop Library will use 64 bits precision 2718by default, the user may set: 2719@example 2720export OSL_PRECISION=64 2721@end example 2722@noindent if his shell is, e.g., bash or 2723@example 2724setenv OSL_PRECISION 64 2725@end example 2726@noindent if his shell is, e.g., tcsh. The user should ad this line to 2727his .bashrc or .tcshrc (or whatever convenient file) to make this 2728setting permanent. 2729 2730@node Base Functions 2731@section Base Functions 2732 2733The OpenScop Library provides, for each OpenScop data structure, 2734a set of functions devoted to basic manipulation, conversion 2735from file format to data structures and from data structures to 2736file format. The naming convention is consistent for all data 2737structures. Hence, the function prototypes differ only with the 2738name of the data structure. In the following, we will use the 2739generic term of @emph{structure} to refer at any OpenScop 2740data structure. For instance the 2741@code{osl_}@emph{structure}@code{_malloc()} function is a 2742generic name can be instantiated to 2743@code{osl_relation_malloc()} or 2744@code{osl_statement_malloc()} etc. 2745 2746We present in this documentation only 2747the main functions. Many other utility functions are provided 2748to ease OpenScop format manipulation. The reader is invited to 2749refer at the technical documentation to learn everything about the 2750OpenScop Library. 2751 2752@menu 2753* Dumping:: 2754* Printing:: 2755* Reading:: 2756* Allocating:: 2757* Deallocating:: 2758* Cloning:: 2759* Testing:: 2760@end menu 2761 2762 2763@node Dumping 2764@subsection Dumping: osl_@emph{structure}_dump and idump 2765 2766@example 2767@group 2768void osl_@emph{structure}_dump(FILE * output, osl_@emph{structure}_p s); 2769void osl_@emph{structure}_idump(FILE * output, osl_@emph{structure}_p s, int i); 2770@end group 2771@end example 2772 2773@noindent Each OpenScop data structure has a dumping functions 2774as shown above. Dumping means writing down the content of the data 2775structure pointed by @code{s} (and its fields recursively) 2776in a textual form to the 2777@code{output} file (the file, possibly @code{stdout}, has to be open 2778for writing). The textual form is not the OpenScop file format but 2779another representation closer to the internal representation in 2780memory and mainly intended for debugging purpose. The @code{idump} 2781function has an additional integer parameter which corresponds to 2782an indentation level. 2783 2784@node Printing 2785@subsection Printing: osl_@emph{structure}_print 2786 2787@example 2788@group 2789void osl_@emph{structure}_print(FILE * output, osl_@emph{structure}_p s); 2790@end group 2791@end example 2792 2793@noindent Each OpenScop data structure has a pretty printing function 2794as shown above. It prints the content of the data 2795structure pointed by @code{s} (and its fields recursively) 2796according to the OpenScop file format 2797(@pxref{OpenScop File Format Specification}) to the 2798@code{output} file (the file, possibly @code{stdout}, has to be open 2799for writing). 2800 2801@node Reading 2802@subsection Reading: osl_@emph{structure}_read 2803 2804@example 2805@group 2806osl_@emph{structure}_p osl_@emph{structure}_read(FILE * input); 2807@end group 2808@end example 2809 2810@noindent Each OpenScop data structure has a reading function 2811as shown above. It reads the content of an OpenScop 2812data structure written according to the OpenScop file format 2813(@pxref{OpenScop File Format Specification}) from 2814the @code{input} file (the file, possibly @code{stdin}, has to be open 2815for reading). It returns a pointer to a freshly allocated 2816@code{osl_@emph{structure}_t} structure containing the 2817information. 2818 2819@node Allocating 2820@subsection Allocating: osl_@emph{structure}_malloc 2821 2822@example 2823@group 2824osl_@emph{structure}_p osl_@emph{structure}_malloc(); 2825@end group 2826@end example 2827 2828@noindent Each OpenScop data structure has a memory allocation function 2829as shown above (except one see below). It allocates the memory to store 2830the corresponding data structure, it initializes the pointer fields to 2831@code{NULL} and the integer fields to @code{OSL_UNDEFINED} 2832(@code{-1}) and it returns a pointer to the allocated space. 2833 2834An exception to this base description is the 2835@code{osl_relation_malloc()} function which requires two 2836parameters: the number of rows and columns of the constraint 2837matrix (@pxref{Relations}): 2838 2839@example 2840@group 2841osl_relation_p osl_relation_malloc(int nb_rows, int nb_columns); 2842@end group 2843@end example 2844 2845@noindent The precision of the relation elements will depend on the 2846@code{OSL_PRECISION} environment variable (@pxref{Precision}) if it is set, 2847or the maximum available precision if it is not set. Another allocation 2848function is provided to explicitly set a given precision: 2849 2850@example 2851@group 2852osl_relation_p osl_relation_pmalloc(int precision, 2853 int nb_rows, int nb_columns); 2854@end group 2855@end example 2856 2857@noindent The @code{precision} field may take the following values: 2858@itemize @bullet 2859@item @code{OSL_PRECISION_SP} for 32 bits precision, 2860@item @code{OSL_PRECISION_DP} for 64 bits precision, 2861@item @code{OSL_PRECISION_MP} for multiple precision, 2862@end itemize 2863 2864@node Deallocating 2865@subsection Deallocating: osl_@emph{structure}_free 2866 2867@example 2868@group 2869void osl_@emph{structure}_free(osl_@emph{structure}_p s); 2870@end group 2871@end example 2872 2873@noindent Each OpenScop data structure has a memory deallocation function 2874as shown above. It recursively frees the memory allocated for the 2875structure pointed by @code{s}, i.e., internal structures are also freed. 2876 2877@node Cloning 2878@subsection Cloning: osl_@emph{structure}_clone 2879 2880@example 2881@group 2882osl_@emph{structure}_p osl_@emph{structure}_clone(osl_@emph{structure}_p s); 2883@end group 2884@end example 2885 2886@noindent Each OpenScop data structure has a clone function 2887as shown above. It recursively copies the content of the 2888structure pointed by @code{s}, i.e., internal structures are also copied. 2889It returns a pointer to the clone of the structure pointed by @code{s}. 2890 2891@node Testing 2892@subsection Testing: osl_@emph{structure}_equal 2893 2894@example 2895@group 2896int osl_@emph{structure}_equal(osl_@emph{structure}_p s1, osl_@emph{structure}_p s2); 2897@end group 2898@end example 2899 2900@noindent Each OpenScop data structure has a testing function 2901as shown above. It checks whether two pointers are referring to equivalent 2902structures (either by pointing to the same structure or to different 2903structures which contain the same information). It returns 1 if the 2904pointed structures are equivalent, 0 otherwise. This test is 2905@emph{content-based} and is intended for debugging purpose. It is not 2906(and will never be) able to state, e.g., that two relations with 2907different constraint matrices are actually representing the same relation. 2908 2909 2910@node Example of OpenScop Library Utilization 2911@section Example of OpenScop Library Utilization 2912Here is a basic example showing how it is possible to use the 2913OpenScop Library, assuming that a standard installation has been done. 2914The following C program reads an OpenScop file from the standard 2915input and dumps the content of the data structures to the standard output. 2916 2917@example 2918/* example.c */ 2919# include <stdio.h> 2920# include <osl/osl.h> 2921 2922int main() @{ 2923 osl_scop_p scop; 2924 2925 // Read the OpenScop file. 2926 scop = osl_scop_read(stdin); 2927 2928 // Dump the content of the scop data structure. 2929 osl_scop_dump(stdout, scop); 2930 2931 // Save the planet. 2932 osl_scop_free(scop); 2933 2934 return 0; 2935@} 2936@end example 2937 2938@noindent The compilation command could be: 2939@example 2940gcc example.c -losl -o example 2941@end example 2942@noindent A calling command with the input file test.scop could be: 2943@example 2944more test.scop | ./example 2945@end example 2946 2947 2948@c % ****************************** INSTALLING ******************************** 2949@node Installation 2950@section Installation 2951 2952@menu 2953* License:: 2954* Requirements:: 2955* Installation Instructions:: 2956* Optional Features:: 2957* Uninstallation:: 2958@end menu 2959 2960@node License 2961@subsection License 2962First of all, it would be very kind to refer the present document in any 2963publication that results from the use of the OpenScop specification or library, 2964@pxref{Bas11} (a bibtex entry is provided behind the title page of this 2965manual, along with the copyright notice). 2966The OpenScop Library is provided under the 3-clause BSD license: 2967 2968Copyright (C) 2011 University Paris-Sud 11 and INRIA 2969 2970Redistribution and use in source and binary forms, with or without 2971modification, are permitted provided that the following conditions 2972are met: 2973@enumerate 2974@item Redistributions of source code must retain the above copyright notice, 2975 this list of conditions and the following disclaimer. 2976@item Redistributions in binary form must reproduce the above copyrigh 2977 notice, this list of conditions and the following disclaimer in the 2978 documentation and/or other materials provided with the distribution. 2979@item The name of the author may not be used to endorse or promote products 2980 derived from this software without specific prior written permission 2981@end enumerate 2982 2983THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 2984IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 2985OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2986IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 2987INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2988NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2989DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2990THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2991(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2992THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2993 2994@node Requirements 2995@subsection Requirements 2996 2997The OpenScop Library is a stand-alone library. For a basic use, 2998it does not need any additional tool or library. Anyway, to be able to 2999work in conjunction with other tools that manipulate multiple precision 3000numbers, the GNU GMP library can be used as an option. 3001 3002@menu 3003* GMP Library:: 3004@end menu 3005 3006 3007@node GMP Library 3008@subsubsection GMP Library (optional) 3009 3010To be able to deal with insanely large coefficient, the user will need to 3011install the GNU Multiple Precision Library (GMP for short) version 4.2.2 3012or above@footnote{@code{http://www.swox.com/gmp}}. 3013The user can compile it by typing the following commands on the GMP root 3014directory: 3015 3016@itemize @bullet 3017@item @code{./configure} 3018@item @code{make} 3019@item And as root: @code{make install} 3020@end itemize 3021 3022The GMP default installation is @code{/usr/local}. This directory may 3023not be inside the user's library path. To fix the problem, the user should set 3024@example 3025export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib 3026@end example 3027@noindent if your shell is, e.g., bash or 3028@example 3029setenv LD_LIBRARY_PATH $LD_LIBRARY_PATH:/usr/local/lib 3030@end example 3031@noindent if your shell is, e.g., tcsh. Add the line to your .bashrc or .tcshrc (or 3032whatever convenient file) to make this change permanent. Another solution 3033is to ask GMP to install in the standard path by using the prefix 3034option of the configure script: 3035@samp{./configure --prefix=/usr}. 3036 3037The OpenScop Library has to be built using the GMP library by specifying 3038the convenient configure script options to buid the GMP version 3039(@pxref{Optional Features}). 3040 3041 3042@node Installation Instructions 3043@subsection Installation Instructions 3044 3045Once downloaded and unpacked 3046(e.g. using the @samp{tar -zxvf openscop-@value{LIB_VERSION}.tar.gz} command), 3047you can compile the OpenScop Library by typing the following commands 3048on the OpenScop Library's root directory: 3049 3050@itemize @bullet 3051@item @code{./autogen.sh} 3052@item @code{./configure} 3053@item @code{make} 3054@item And as root: @code{make install} 3055@end itemize 3056 3057The program binaries and object files can be removed from the 3058source code directory by typing @code{make clean}. To also remove the 3059files that the @code{configure} script created (so you can compile the 3060package for a different kind of computer) type @code{make distclean}. 3061 3062@node Optional Features 3063@subsection Optional Features 3064The @code{configure} shell script attempts to guess correct values for 3065various system-dependent variables and user options used during compilation. 3066It uses those values to create the @code{Makefile}. Various user options 3067are provided by the OpenScop Library's configure script. They are summarized in the 3068following list and may be printed by typing @code{./configure --help} in the 3069OpenScop Library top-level directory. 3070 3071@itemize @bullet 3072@item By default, the installation directory is @code{/usr/local}: 3073@code{make install} will install the package's files in 3074@code{/usr/local/bin}, @code{/usr/local/lib} and @code{/usr/local/include}. 3075The user can specify an installation prefix other than @code{/usr/local} by 3076giving @code{configure} the option @code{--prefix=PATH}. 3077 3078@item By default, The OpenScop Library supports 32 bits, 64 bits and GMP if 3079it is installed in the standard locations. Using the @code{--with-gmp} option 3080of @code{configure} the user can specify that no GMP (@code{--with-gmp=no}), 3081a previously installed (@code{--with-gmp=system}, the default) GMP or a 3082build GMP (@code{--with-gmp=build}) GMP should be used. 3083In case of an installed GMP, the installation location can be specified 3084using the @code{--with-isl-prefix=PATH} and if different, the installation 3085of the library can be specified using the 3086@code{--with-isl-exec-prefix=PATH} options of @code{configure}. 3087In the case of a build GMP, the user can also specify the build location 3088using @code{--with-isl-builddir=PATH}. 3089@end itemize 3090 3091@node Uninstallation 3092@subsection Uninstallation 3093The user can easily remove the OpenScop Library from his system 3094by typing (as root if necessary) from the OpenScop Library top-level 3095directory 3096@code{make uninstall}. 3097 3098@c % **************************** DOCUMENTATION ****************************** 3099@node Documentation 3100@section Documentation 3101The OpenScop Library distribution provides several sources of documentation. 3102First, the source code itself is as documented as much as possible. 3103The code comments use the Doxygen technical documentation system. 3104The user may install 3105Doxygen@footnote{@code{http://www.stack.nl/~dimitri/doxygen}} to automatically 3106generate a technical documentation by typing @code{make doc} or 3107@code{doxygen ./autoconf/Doxyfile} at the OpenScop Library 3108top-level directory after running the configure script 3109(@pxref{Installation Instructions}). Doxygen will generate 3110documentation sources (in HTML, LaTeX and man) in the @code{doc/source} 3111directory of the OpenScop Library distribution. 3112 3113The Texinfo source of the present document is also provided in the @code{doc} 3114directory. The user can build it in either PDF format 3115(by typing @code{texi2pdf openscop.texi}) or HTML format 3116(by typing @code{makeinfo --html openscop.texi}, using @code{--no-split} 3117option to generate a single HTML file) or info format 3118(by typing @code{makeinfo openscop.texi}). 3119 3120@c % **************************** DEVELOPPING ******************************** 3121@node Development 3122@section Development 3123 3124@menu 3125* Copyright Issue:: 3126* Repository:: 3127* Coding Style:: 3128* Extension Development:: 3129@end menu 3130 3131@node Copyright Issue 3132@subsection Copyright Issue 3133 3134The OpenScop Library is an Open Source project and you should feel free to 3135contribute by adding functionalities (in particular extensions), correcting 3136bugs or improving documentation. However, for painful administrative reasons, 3137the copyright of the core part (everything except extensions) should not be 3138impacted by your work. Hence, if you are doing a significant contribution to 3139the main part, the OpenScop Library maintainer may ask you for an agreement 3140about this copyright. If you plan to do such a significant contribution, it 3141may be wise to discuss this issue with the maintainer first. Extensions 3142may include developer's own copyright. 3143 3144@node Repository 3145@subsection Repository 3146 3147The main repository of the OpenScop Library is 3148@url{http://repo.or.cz/w/openscop.git}. Developers may ask the OpenScop Library 3149maintainer to open them a write access to this repository. Only the maintainer 3150should ever change the @code{master} branch. Developers should work on their 3151own branches. To avoid any problem developers should use the @emph{fork} 3152functionality of the repository. 3153 3154@node Coding Style 3155@subsection Coding Style 3156 3157The OpenScop Library is written in C using an object oriented style. Each 3158important data structure (e.g., @code{struct foo}) has its own header file 3159(@code{include/osl/foo.h}) where lies the definition of 3160the data structure, the two typedefs for the data structure (one for the 3161structure, @code{osl_foo_t}, and one for a pointer 3162to the structure, @code{osl_foo_p}), the prototypes of the various 3163functions related to this data structure, all named using the 3164prefix "@code{osl_foo_}". The source code of the functions is provided in a 3165separated C file (@code{source/foo.c}). 3166 3167Utility functions independent from the main data structures may be placed in 3168separate source files (e.g., definition in @code{include/osl/util.h} 3169and code in @code{source/util.c}). Tool-wide preprocessor directives are 3170placed in @code{include/osl/macros.h}, macros are prefixed with 3171"@code{OSL_}". 3172 3173The core code itself has to be written according to the Google C++ Coding Style: 3174@url{http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml} (for 3175what can apply to C), plus the naming conventions discussed above with 3176highest priority. The extension parts must only respect the naming convention, 3177but a consistent coding style is much appreciated. 3178 3179@node Extension Development 3180@subsection Extension Development 3181 3182It's fairly easy to integrate a new extension to OpenScop and the OpenScop 3183Library. Developing a new extension is very much like adding a new "object": 3184it requires writing a data structure for the extension data and the 7 base 3185functions to manage this extension. Here is how developers should proceed 3186to add an extension called @code{foo} (beware that the naming convention is 3187strict): 3188 3189@enumerate 3190@item Send the name @code{foo} to the maintainer to ensure it is unique and 3191 hence can be used as an URI. The name (one single 3192 word, or words separated with underscores "_") should be 3193 suggested by the extension developers to the OpenScop development 3194 mailing list @email{openscop-development@@googlegroups.com}). It 3195 should not correspond to an existing structure name 3196 (see @code{include/osl/osl.h} for the list). The 3197 maintainer will update @code{include/osl/osl.h} in the development 3198 version accordingly. 3199@item Look at the @code{comment} extension. The @code{comment} extension 3200 (@pxref{Comment Extension}) has been written to be used as a basic 3201 example for extension developers. Having a look at 3202 @code{include/osl/extensions/comment.h} and 3203 @code{source/extensions/comment.c} will be a great help to do it right. 3204@item Create the extension data structure: it is necessary that the 3205 extension data can be accessible through only one pointer. 3206@item Code the 7 base functions for the extension. Any extension must provide 3207 this set of functions (naming convention apply only if the 3208 extension is planed to be integrated to the OpenScop Library 3209 default extensions): 3210 @itemize @bullet 3211 @item @code{osl_foo_idump} (@pxref{Dumping}) 3212 @item @code{osl_foo_sprint} has the following prototype: 3213@example 3214@group 3215char * osl_@emph{structure}_sprint(osl_@emph{structure}_p s); 3216@end group 3217@end example 3218 It corresponds to the pretty printing functions of the core 3219 data structures (@pxref{Printing}) with the 3220 difference that the OpenScop textual representation is written 3221 to a string (returned by the function) instead of a file. 3222 @item @code{osl_foo_sread} has the following prototype: 3223@example 3224@group 3225osl_@emph{structure}_p osl_@emph{structure}_sread(char ** string); 3226@end group 3227@end example 3228 It corresponds to the reading functions of the core 3229 data structures (@pxref{Reading}) with the 3230 difference that the OpenScop textual representation is read 3231 from a string (provided as a parameter) instead of a file. 3232 The address of the string to read is passed as a parameter and 3233 is updated to point immediately after what has been actually read. 3234 @item @code{osl_foo_malloc} (@pxref{Allocating}) 3235 @item @code{osl_foo_free} (@pxref{Deallocating}) 3236 @item @code{osl_foo_clone} (@pxref{Cloning}) 3237 @item @code{osl_foo_equal} (@pxref{Testing}) 3238 @end itemize 3239@item Code the other functions you need! 3240@end enumerate 3241 3242Now let us consider two scenarios. 3243 3244First scenario, the extension is external and is 3245not planned to be integrated to the OpenScop Library. In this case you are 3246all set. Simply generate an @code{osl_interface_t} for your 3247extension and have a look at the function 3248@code{osl_scop_register_extension()} which is devoted to register 3249a new extension interface to an existing @code{osl_scop_t}. 3250 3251Second scenario, the extension will integrate the set of default 3252OpenScop Library extensions (the best solution to share it to other 3253potential users). In this case, a few additional 3254things have to be done: 3255@enumerate 3256@item Create the extension header 3257 @code{include/osl/extensions/foo.h} to store the extension 3258 structure and function prototypes and the 3259 extension source file @code{source/extensions/foo.c} for the code 3260 of the functions. 3261@item Add the documentation for the extension to the texinfo source of 3262 this document (in @code{doc/openscop.texi}), following the example 3263 of the @code{comment} documentation (@pxref{Comment Extension}). 3264@item Integrate the extension by adding the @code{extensions/foo.c} entry 3265 to the @code{libosl_la_SOURCES} in the @code{source/Makefile.am} 3266 file, the @code{osl/foo.h} entry to the 3267 @code{nobase_pkginclude_HEADERS} and add the corresponding 3268 @code{#include <osl/extensions/foo.h>} in the 3269 @code{include/scop.h.in} file. 3270@item Add the new extension in the 3271 @code{osl_interface_get_default_registry()} function. 3272@item You are done! Prepare a single commit or patch corresponding to the 3273 integration of the new extension and ask the maintainer to merge it 3274 to the master branch. 3275@end enumerate 3276 3277 3278@c % ****************************** REFERENCES ******************************** 3279@node References 3280@chapter References 3281 3282@itemize 3283@item 3284@anchor{Bas03a}[Bas03a] C. Bastoul, P. Feautrier. Improving data locality 3285by chunking. CC'12 International Conference on Compiler Construction, 3286LNCS 2622, pages 320-335, Warsaw, April 2003. 3287 3288@item 3289@anchor{Bas11}[Bas11] C. Bastoul. 3290OpenScop: A Specification and a Library for Data Exchange in Polyhedral 3291Compilation Tools. Technical Report, Paris-Sud University, France, June 2011. 3292 3293@item 3294@anchor{Fea92}[Fea92] P. Feautrier. Some efficient solutions to the affine 3295scheduling problem, part II: multidimensional time. 3296International Journal of Parallel Programming, 21(6):389--420, December 1992. 3297 3298@item 3299@anchor{Gri04}[Gri04] M. Griebl. Automatic parallelization of loop programs 3300for distributed memory architectures. Habilitation Thesis. Facult@"at f@"ur 3301Mathematik und Informatik, Universit@"at Passau, 2004. 3302@emph{http://www.infosun.fmi.uni-passau.de/cl/loopo/} 3303 3304@item 3305@anchor{Wil93}[Wil93] Doran K. Wilde. 3306A library for doing polyhedral operations. 3307Technical Report 785, IRISA, Rennes, France, 1993. 3308 3309@end itemize 3310 3311 3312 3313 3314@c % /************************************************************************* 3315@c % * PART VI: END OF THE DOCUMENT * 3316@c % *************************************************************************/ 3317@c @unnumbered Index 3318 3319@c @printindex cp 3320 3321@bye 3322