Next Previous Contents

2. Code selector description language

An code selector description describes mainly tree patterns of low level internal representation with associated usage constraints, costs and semantic actions. The tree pattern may contains terminal representing the low level internal representation node. Nonterminals serves to designate the tree patterns. Each terminal or nonterminal may have attribute which is evaluated in actions.

2.1 Layout of code selector description

Code selector description structure has the following layout which is similar to one of YACC file. 

     DECLARATIONS
     %%
     RULES
     %%
     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 terminals by names of constants which represent modes of the low level internal representation nodes. The section also may contain declarations of commutativeness of some terminals. Type and union declarations can be used to declare types of terminal and nonterminal attributes. And finally the section may contain subsections of code on C/C++.

The next section contains rules. Each rule describes tree pattern, nonterminal designating the pattern, the pattern cost, its usage constraint, and associated action. The rule list can be empty. In this case the code selector description is used to locate machine dependent code and generated code of the tree pattern matcher can not be used.

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 with code selector description 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: 

     %term <TYPE> IDENTIFIER ...
All terminals must be defined in constructions of such kind (or in construction `%commutative'). The same identifier can be defined repeatedly. The identifier is a name of constant which represents mode of the low level internal representation node. If the user needs usage of attributes of different types, the terminal attribute type can be given in this construction. The union declaration can be used for this. 
     %union {
       any thing that can go inside a `union' in C/C++
     }
The last such construction in the declarations section specifies the entire collection of possible types for attribute values. For example: 
     %union {
       IR_node_t node;
       int number;
     }
This means that the two alternative types are `IR_node_t' and `int'. They are given by names `node' and `number'. These names are used in the type and commutativeness declarations to instruct type of attribute for a terminal or nonterminal. The type declarations has the following form: 
     %type <TYPE> IDENTIFIER ...
The construction can be used when union declaration is present. Here `TYPE' is a name of type given in union declaration. If the type of terminal or nonterminal is not given its type is believed to be `CS_TYPE' (see next section). The identifier is one of terminal or nonterminal. The construction 
     %commutative <TYPE> TERMINAL_IDENTIFIER ...
describes terminal and commutativeness of operator represented by the terminal besides optional instruction for the terminal attribute type. For example, if the terminal `plus' is described as commutative then pattern `plus (register, constant)' simultaneously designates pattern `plus (constant, register)'. 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 code selector 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. For example, such C/C++ code may redefine some internal definitions, e.g. macro defining type of attributes. 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 NONA. All C/C++ declarations are placed in the same order as in the section of declarations.

2.3 Rules

The section of declarations is followed by section of rules . A rule is described the following construction 

     nonterminal : pattern cost %if constraint action
The rule connects tree pattern with nonterminal. Several tree patterns can be connected to a nonterminal. Nonterminal is given by its identifier. The rest constructions cost, constraint with keyword `%if', and actions are optional. Cost is a integer expression on C/C++ in brackets `[' and `]'. If the cost is omited in the rule, then its value is believed to be zero. The cost value has to be non-negative. Constraint which is given as a boolean expression on C/C++ in brackets `[' and `]' defines a condition of the tree pattern usage. In the case of absent constraint its value is believed to be nonzero. The tree pattern will be never in a minimal cost cover if constraint value is equal to zero during testing the tree pattern as a candidate on inclusion into minimal cost cover. For example, the following rule with constraint describes Am29k instruction CONST 
     register : integer_constant [1]
                %if [IR_value ($1) >=0 && IR_value ($1) < 256]
The actions can contain any statements on C/C++ in figure brackets `{' and `}'. Constructions `$$' and `$n' (n is a integer number here) denote attributes of correspondingly nonterminal before `:' and terminal or nonterminal in the pattern with order number equal to `n'. The order numbers start with 1. These constructions may be present in the cost, the constraint and the action. But it should be remembered that definition of the moment of the cost and the constraint evaluation is quite difficult. Moreover there is not guaranty that given cost and constraint will be evaluated. Therefore side effects should be not in the cost and in the constraint, and usage attributes of nonterminals should be not in the cost and in the constraint. The cost and the constraint may be fulfilled on the first bottom up pass. It is known only that the cost is fulfilled after evaluation of constraint give nonzero result. The action of the tree pattern which is a part of result minimal cost cover is fulfilled on the second bottom up pass. Tree pattern is given by one of the following forms: 
     TERMINAL ( PATTERN , ...)
     TERMINAL
     NONTERMINAL
For example, the following pattern describes Am29050 instruction DMSM 
     double_addition (twin, double_multiplication (twin,
                                                   accumulator0))
It should be remembered that each terminal must have fixed arity in all patterns. It means that usage of the following patterns in a code selector description will be erroneous. 
     integer_addition (register, register)
     integer_addition (register)
Full YACC syntax of internal representation description language is placed in Appendix 1.

Next Previous Contents