Next Previous Contents

2. Pipeline hazards description language

A pipeline hazards description describes mainly reservations of processor functional units by an instruction during its execution. The instruction reservations are given by regular expression describing nondeterministic finite state automaton (NDFA).

2.1 Layout of pipeline hazards description

Pipeline hazards description structure has the following layout which is similar to one of YACC file. 

     DECLARATIONS
     %%
     EXPRESSIONS
     %%
     ADDITIONAL C/C++ CODE
The `%%' serves to separate the sections of description. All sections are optional. The first `%%' starts section of rules and is obligatory even if the section is empty, the second `%%' may be absent if section of additional C/C++ code is absent too.

The section of declarations contains declarations of functional units and instructions of a processor. The section also may contain declarations of automata on which result automaton are split in order to decrease size of tables needed for fast recognition of pipeline hazards. And finally the section may contain subsections of code on C/C++.

The next section contains expressions list which describes functional units reservations by instructions. Regular expressions in general case correspond to nondeterministic final state automaton. The expression list can be empty. In this case the result automaton can contains only arcs marked by special token corresponding advancing cycle.

The additional C/C++ code can contain any C/C++ code you want to use. Often functions which are not generated by the translator but are needed to work of the instruction scheduler go here. This code without changes is placed at the end of file generated by the translator.

2.2 Declarations

The section of declarations may contain the following construction: 

     %instruction IDENTIFIER ...
Such constructions declare instructions (or instruction class) of processor. All instructions must be defined in constructions of such kind. The same instruction identifier can be defined repeatedly. There is analogous construction which can serves to describe frequently repeated functional units reservations by real instructions. 
     %reservation IDENTIFIER ...
The functional unit declarations has the following form: 
     %unit <automaton identifier> IDENTIFIER ...
The construction is used to describe functional units of given processor. Optional identifier in angle brackets describes how to split result automaton onto smaller automata. Each such automaton will contain states corresponding to only reservations of functional units described with given automaton identifier. The same unit identifier can be defined repeatedly with the same automaton identifier.

Sometimes it is necessary to describe that some units can not be reserved simultaneously, e.g. floating point unit is pipelined but can execute only single or double floating point operation. The following construction is useful in such situations 

     %exclude IDENTIFIER ... : IDENTIFIER ...
The functional units left to the semicolon can not be reserved with the units right to the semicolon (and vise versa) on the same cycle. All units in the construction should belong the same automata.

All automaton identifiers present in unit declarations must be declared in the following construction 

     %automaton IDENTIFIER ...
If there is an automaton declaration, all unit declarations must be with a declared automaton. There may be also the following constructions in the declaration section 
     %local {
        C/C++ DECLARATIONS
     }

     %import {
        C/C++ DECLARATION
     }

     and

     %export {
        C/C++ DECLARATION
     }
which contain any C/C++ declarations (types, variables, macros, and so on) used in sections. The local C/C++ declarations are inserted at the begin of generated implementation file (see pipeline hazards description interface) but after include-directive of interface file. C/C++ declarations which start with `%import' are inserted at the begin of generated interface file. C/C++ declarations which start with `%export' are inserted at the end of generated interface file. For example, such C/C++ code may contain definitions of of external variables and functions which refer to definitions generated by OKA. All C/C++ declarations are placed in the same order as in the section of declarations.

2.3 Expressions

The section of declarations is followed by section of expressions. A expression is described the following construction 

     instruction or reservation identifiers : expression;
This construction means that instructions given in the left part reserves units according to the expression. In the case of reservation identifier, it is usually used for describing sub-expression frequently used in other expressions. Of course, each declared instruction and reservation must be present in only one such construction. The expression describes non-deterministic finite state automaton (NDFA) in general case and can contain the following forms: 
      EXPRESSION   EXPRESSION
      EXPRESSION + EXPRESSION
      EXPRESSION * NUMBER
      EXPRESSION | EXPRESSION
      %nothing
      UNIT OR RESERVATION IDENTIFIER
      [ EXPRESSION ]
      ( EXPRESSION )
Binary operator ` ' (blank) and `+' describes sequential reservations given by the expressions. In the first case the first unit in the right expression is reserved on the next cycle after the reservation of the last unit in left expression (so called concatenation with cycle advancing). The reservation of an unit is described simply by the unit identifier. In the second case the first unit in the right expression is reserved on the same cycle after the reservation of the last unit in left expression (so called concatenation without cycle advancing). Sometimes it is necessary to describe absence of unit reservations during several cycles. The construction `%nothing' serves for this purpose. `%nothing' can be in the same place as an unit identifier.

Reservation identifier is simply changed by the construction `(the corresponding reservation expression)'.

The construction `EXPRESSION * NUMBER' is simply abbreviation of `EXPRESSION EXPRESSION ...' where the expression is repeated by given positive number times.

The construction `EXPRESSION | EXPRESSION' means that the instructions reserve units according to the left or to the right expression (so called alternative). If an unit is present only on one alternative it should belong to the same automaton as units on other alternative. OKA checks this and reports if it is not true.

All binary operators have the left associativity and the following priority: 

      `*'          - the highest priority
      `+' and ` '  - the middle priority
      `|'          - the lowest priority

The construction `[EXPRESSION]' serves for describing optional construction and is simply abbreviation of the following construction ` | EXPRESSION'.

The parentheses are used to grouping sub-expressions in another order then the one given by priorities and associativities of operators.

Full YACC syntax (with some hints in order to transform into LALR (1)-grammar) of pipeline hazards description language is placed in Appendix 1.

Next Previous Contents