Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

27

C-DVM Compiler

Detailed design

Март 31, 1999

Keldysh Institute of Applied Mathematics

Russia Academy of Sciences

Contents

1 EXTERNAL INTERFACE OF THE COMPILER 3

2 PHASES OF COMPILATION 3

2.1 Internal representation of program 4

2.2 The Scanner 4

2.3 The Parser 5

2.4 The Transformer 5

2.5 The Unparser 5

3 SEMANTIC ACTIONS 6

3.1 Parser actions 6

3.2 Transformation concerning "main" 10

3.3 "IS_LOCAL" transformation 11

3.4 Access transformation 11

3.5 DVM-directive transformation 12

3.6 Data tracing transformation 13

3.7 DVM-types and I/O transformation 14

4 AUXILIARY SEMANTIC FUNCTIONS 16

4.1 PARALLEL loop functions 16

4.2 SHADOW functions 17

4.3 REDUCTION functions 19

4.4 REMOTE_ACCESS functions 19

Appendix A. Table of tokens and their symbolic names 20

A.1 Terminals 20

A.2 Delimiters and operators 20

A.3 Keywords 21

A.4 DVM keywords 22

Appendix B. Parsing tree nodes 23

B.1 Terminals, lists and braces 23

B.2 C-language nodes 23

B.3 DVM-specific nodes 26

1 EXTERNAL INTERFACE OF THE COMPILER

For portability the compiler is written on ANSI-C and starts from the command line (under OS UNIX and WINDOWS 9x) by the following command (the name of executable may be changed):

cdvm [<options>] [-o <outfile>] <infile>

where

<infile> -- required parameter: source CDVM file; covertor expects that it was compiled with standard C compiler and is correct with respect to C syntax;

-o <outfile> -- optional parameter: output file name for converted program (by default it is CDVM_OUT.C)

<options> -- one or more of the following:

-s -- generate Sequential program (no DVM, trace only); by default parallel program is generated.

tracing modes:

-d1 -- trace modification of DVM-arrays,

-d2 -- trace all accesses to DVM-arrays,

-d3 -- trace modification of all data,

-d4 -- trace all accesses to all data.

performance analyzer modes:

-e1 -- Parallel loops and enclosing sequential loops,

-e2 -- Parallel loops and user defined INTERVALs,

-e3 -- e1 + e2,

-e4 -- e3 + all other sequential loops.

other:

-v -- Verbose mode,

-w- -- disable Warnings,

-? -h -H -- show "Usage" screen and stop.

2 PHASES OF COMPILATION

Compilation is made upon an internal representation of a program. The main "large" data structures used as internal representation are the following:

• string memory for character representation of tokens (LX);

• table converting internal token number to its position in token table (LXIX);

• hash table for quick search of tokens (HT);

• linked memory buffer in which a parsing tree (or an abstract syntax tree) is build.

Size of this structures depends on the size of the source program. Storage for those is allocated statically but may be "scaled" by command line parameter (+1 ... +9).

The main program of compiler performs the following steps:

• gets and verifies command line parameters;

• allocates variable-size data (buffers);

• initializes lexical and syntactical tables;

• opens the input file and generates a standard heading of the output file;

• invokes a parser to read source file and to build its internal representation; the parser in its turn invokes a scanner to move to the next token;

• if the parser successfully builds the tree (not reported syntax errors) the main program invokes a transformer, which analyzes source tree structure and rebuilds it;

• if the transformer successfully rebuilds the tree, the second part (depending on results of analyze) of output file heading is generated, and an unparser generates output code.

2.1 Internal representation of program

As an internal representation of a program CDVM-compiler uses a parsing tree. Each node of the tree has the following four fields:

• C -- code of the node, usually an internal number of C operation or operator, or DVM-directive;

• A and B -- references to subtrees for operands or components; they may be equal to zero for optional subconstruct or for unary operations or constructs; sometimes these fields are not references to subtrees, e.g. for a node, representing identifier, it contain internal number of the identifier;

• D -- attributes of the node.

Constructs having more than two components are represented by two (ore more) linked nodes. In such a case the code field of auxiliary nodes may be equal to zero.

Nodes are created in the tree buffer. There are to functions for this purpose: one of them always creates new node, while the second first searches for existing node with the same C, A, and B fields.

Access to fields of node number N is realized by functions C(N), A(N), B(N), D(N) for reading, and wC(N,x), wA(N,x), wB(N,x) and wD(N,x) for writing (of value x).

Detailed structure of parsing tree is described in Appendix B

2.2 The Scanner

On each invocation the scanner moves to the next token in source code (skipping comments and reading next line if necessary) and assigns two global variables for use by the parser (LXcode and LXvalue). LXcode is the code of the current token, namely: for keywords (of C and DVM), operators and delimiters (of C) it is their internal number; and for identifier or constant it is their lexical category number. In the letter case an internal number of identifier or constant is assigned to LXvalue. String representation of identifiers are kept in a string memory (LX) for using at generation phase. For parser they are represented by their internal numbers. Internal number is assigned to an identifier at its first occurence. The scanner looks for the current token in the token table (hash function is used), and adds new token to it if necessary. In special "trial", "look forward" mode the scanner saves information about tokens in buffer allowing return to previous position, if parsing failed. Token codes also used as node codes of the parsing tree.

Tokens and symbolic names for their codes are listed in Appendix A.

2.3 The Parser

Purpose of the parser is evident:

• to analyze context-free structure of the program;

• to report errors, if they encountered;

• and to build the parsing tree.

A method of parsing is straitforward top-down descent with backtracking in not numerous doubtful cases. The structure of resulting tree is described in Appendix B.

2.4 The Transformer

The tree transformation is performed in several successive traverses of the tree, namely:.

• transformation concerning "main";

• "IS_LOCAL" transformation;

• access transformation;

• DVM-directive transformation; executable and structured directives elaborated;

• data tracing transformation;

• DVM-types and I/O transformation; finally, declarations of distributed data modified.

Every tree traversal is performed by function bypass() with parameters identifying the current step. While traversing tree this function invokes semantic functions to perform semantic actions and transformations depending on step of transformation, on code of a visited node and on current direction (downward -- the first visit of the node, or upward -- the last visit of the node).

Semantic action functions is the main part of the compiler and they are described in the following section.

2.5 The Unparser

The unparser traverses the tree and restores external text representation. As for this file is only temporary, formatting may be simple. Note that output file is written in terms of CDVM macros, not directly RTL calls.

3 SEMANTIC ACTIONS

Semantic actions are performed when parser builds the tree or transformer passes the tree. Actions depend on:

• number of pass;

• direction (downward the tree or upward);

• code of a visited node.

In the following description semantic actions arranged in this manner. Implementation may gather them into functions and/or modules in another way.

For simple actions their description is provided. For more complex only reference to function (see Section 4) or macro (see Preliminary Design.)

3.1 Parser actions

Downward action is performed immediately after creation of a node. The node is not yet filled. Here some context conditions are verified. Upward actions verifies well-formedness conditions after subtree is build by parser.

3.1.1 Downward direction actions (CNTX -- context)

Nodes LX_DISTR, LX_REDISTR,

LX_ALIGN, LX_REALIGN, LX_CRTEMP,

LX_SG, LX_CRSG, LX_SS, LX_SW,

LX_RG, LX_CRRG, LX_RS, LX_RW,

LX_REMOTE, RETURN

Not allowed in parallel loop body. (Function notINploop.)

Nodes LX_SNEW, LX_SS, LX_SW, LX_RED, LX_REMOTE

If in parallel loop header, check duplication and compatibility of parallel loop subdirectives, i.e. SHADOW_RENEW, SHADOW_START, SHADOW_WAIT, REDUCTION, REMOTE_ACCESS). (Function nonDupl.) Issue an error message if:

• any subdirective duplicated,

• any two of shadow directives used.

Node LBS

Open new visibility scope. (Function SCOPEnew.)

Node XXdecl

For formal parameters list open new visibility scope. (Function SCOPEnew.)

Node XXoper and XXdecl

Check compatibility of DVM-directive (if there exists) and operator. (Function Allowed.) Issue an error message if:

• declarative directive (DISTRIBUTE, ALIGN, SHADOW_GROUP, REDUCTION_GROUP) stays before operator;

• executable directive (REDISTRIBUTE, REALIGN, CREATE_TEMPLATE, CREATE_SHADOW_GROUP, CREATE_REDUCTION_GROUP, SHADOW_START, SHADOW_WAIT, REDUCTION_START, REDUCTION_WAIT) not followed by semicolon, or used outside function;

• PARALLEL, REMOTE_ACCESS and INTERVAL directive not followed by non-empty operator;

• parameter is specified by a directive other than DISTRIBUTE or ALIGN, or without '*'.

3.1.2 Upward direction actions (ISWF -- well-formedness)

Node LXI

Find declaration of identifier and save reference to it. (Function DCLfnd.)

Nodes LXI and LBK

Verify access to DVM-array and convert to DAElm-macro. (Function ISWFaccess.) Issue an error message if:

• rank exceeds Lib-DVM limitation (now 4);

• rank of access does not match with declaration;

• it is not DVM-array;

• wrong parameter of read-write function;

• assignment to non-pointer or malloc of pointer is made;

• REMOTE_ACCESS is used for lefthand side of assignment.

Nodes LBS, XXbody

Close current visibility scope. (Function SCOPEend.)

Node ASS

If in declaration, so it is initializer. Initialization of distributed data (DVM-arrays) is not allowed. (Function ISWFinit.)

Node LX_SHAD

Number of width must match with the rank of array.

Node LX_DISTR

Topmost syntax of DISTRIBUTE: "*" is allowed for parameters and pointers only. (Function ISWFdistr.)

Nodes LX_REDISTR, LX_CRTEMP

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов учебной работы