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:

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:

EMIT(MIR_BinaryAcc.mutate(P(p), IA32_ADD, MO_S(P(p), DW),

The production in this rule represents the following tree:

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

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:


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)