Skip to end of metadata
Go to start of metadata

The optimizing compiler uses the Bottom-Up Rewrite System (BURS) for instruction selection. BURS is essentially a tree pattern matching system derived from Iburg by David R. Hanson. (See "Engineering a Simple, Efficient Code-Generator Generator" by Fraser, Hanson, and Proebsting, LOPLAS 1(3), Sept. 1992, doi: 10.1145/151640.151642). The instruction selection rules for each architecture are specified in an architecture-specific file located in $RVM_ROOT/rvm/src-generated/opt-burs/${arch}, where ${arch} is the specific instruction architecture of interest. The rules are used in generating a parser, which transforms the IR.

Each rule is defined by a four-line record, consisting of:

  • PRODUCTION: the tree pattern to be matched. The format of each pattern is explained below.
  • COST: the cost of matching the pattern as opposed to skipping it. It is a Java expression that evaluates to an integer.
  • FLAGS: The flags for the operation:
    • NOFLAGS: this production performs no operation
    • EMIT_INSTRUCTION: this production will emit instructions
    • LEFT_CHILD_FIRST: visit child on left-and side of production first
    • RIGHT_CHILD_FIRST: visit child on right-hand side of production first
  • TEMPLATE: Java code to emit

Each production has a non-terminal, which denotes a value, followed by a colon (":"), followed by a dependence tree that produces that value. For example, the rule resulting in memory add on the Intel IA32 architecture is expressed in the following way:

stm:    INT_STORE(INT_ADD_ACC(INT_LOAD(r,riv),riv),OTHER_OPERAND(r, riv))
ADDRESS_EQUAL(P(p), PLL(p), 17)
EMIT_INSTRUCTION
EMIT(MIR_BinaryAcc.mutate(P(p), IA32_ADD, MO_S(P(p), DW), BinaryAcc.getValue(PL(p))));

The production in this rule represents the following tree:

         r     riv
          \    /
         INT_LOAD  riv
             \     /
           INT_ADD_ACC  r  riv
                    \   |  /
                   INT_STORE

where r is a non-terminal that represents a register or a tree producing a register, riv is a non-terminal that represents a register (or a tree producing one) or an immediate value, and INT_LOAD, INT_ADD_ACC and INT_STORE are operators (terminals). OTHER_OPERAND is just an abstraction to make the tree binary.

There are multiple helper functions that can be used in Java code (both cost expressions and generation templates). In all code sequences the name p is reserved for the current tree node. Some of the helper methods are shortcuts for accessing properties of tree nodes:

  • P(p) is used to access the instruction associated with the current (root) node,
  • PL(p) is used to access the instruction associated with the left child of the current (root) node (provided it exists),
  • PR(p) is used to access the instruction associated with the right child of the current (root) node (provided it exists),
  • similarly, PLL(p), PLR(p), PRL(p) and PRR(p) are used to access the instruction associated with the left child of the left child, right child of the left child, left child of the right child and right child of the right child, respectively, of the current (root) node (provided they exist).
  • VL(p) is used to access the integer constant value associated with the left child of the current (root) node
  • VR(p) is used to access the integer constant value associated with the right child of the current (root) node
  • See BURS_Common_Helpers class for definitions of the helper methods

 

How the above rule basically reads is as follows:
If a tree shown above is seen, evaluate the cost expression (which, in this case, calls a helper function to test whether the addresses in the STORE (P(p)) and the LOAD (PLL(p)) instructions are equal. The function returns 17 if they are, and a special value INFINITE if not), and if the cost is acceptable, emit the STORE instruction (P(p)) mutated in place into a machine-dependent add-accumulate instruction (IA32_ADD) that adds a given value to the contents of a given memory location.

The rules file is used to generate a file called ir.brg, which, in turn, is used to produce a file called BURS_STATE.java. Note that if the BURS rules are changed, it is necessary to run ant real-clean in order to recreate the auto-generated Java source code for the BURS rules.

For more information on helper functions look at BURS_Helpers.java. For more information on the BURS algorithm see BURS.java.

Future directions

Whilst jburg allows us to do good instruction selection there are a number of areas where it is lacking:

Vector operations

We can't write productions for vector operations unless we match an entire tree of operations. For example, it would be nice to write a rule of the form:

(r, r): ADD(r,r), ADD(r,r)

if say the architecture supported a vector add operation (ie SIMD). Unfortunately we can't have tuples on the LHS of expressions and the comma represents that matching two coverings is necessary. Leupers has shown how with a modified BURS system they can achieve this result. Their syntax is:

r: ADD(r,r)
r: ADD(r,r)

  • No labels