This note interweaves code optimization with discussion about IR because
the IR choice will be influenced by what you want to do with it.  I am
going to use examples below to guide this discussion.  A lot of it is
somewhat 'stream-of-thought' writing -- this is not a tight spec.

Since we let HotSpot do a lot of heavy lifting, the goal of the IR and
associated transformations would be to transform the code by exploting
available type information, inlining where necessary, method caching, etc.

Example 1:
   def add(a, b)
     a + b

I'll use this example first to discuss what the IR needs to enable.
Even this simple example proves impressively complex in the face of
Ruby's dynamic nature that lets us explore different aspects of the
optimization problem.

Straightforward transformation to IR
Instructions are basically multi-operand format and most instructions
compute a result which can be stored into a variable.

Attempt 1:
   a    = meth_arg(0)
   b    = meth_arg(1)
   args = [b]
   ret  = ocall a, '+', args
   return ret

This IR transformation is straightforward and no surprises here.  The
ocall is basically a method call that does method lookup prior to the

Alternatively, by splitting a call into a method-address computation
and the actual call, we might be able to eliminate repeated method-table
lookups (or whatever else is involved in identifying a method address).

Attempt 2:
   a    = meth_arg(0)
   b    = meth_arg(1)
   m    = meth_addr a, '+'
   args = [b]
   ret  = call m, args
   return ret

Here 'call' could be a regular C call for all you care.  So, what would
happen in the compiler is that you would first transform the code into
a higher-level IR (with virtual calls as above), and at some point in the
optimization, you will ratchet down the IR one level lower that might
expose other optimizations such as this one.  If you took care to maintain
the SSA-ness during transformations, optimizations such as eliminating
duplicate method look ups can be done by the SCCP (sparse conditional
propagation) algorithm which is linear and pretty fast for all practical

Open classes & JIT => All optimizations have to be guarded
Unlike Java, in Ruby, because of open classes, code can be modified at any
time and the code changes can have sweeping effect across the application.
For example, overriding the '+' in Fixnum is likely to affect lots of code.
So, whereas in Java, once you optimize code, that code is gold (except for
inheritance hierarchy changes -- which Hotspot catches anyway), in Ruby, all
optimizations need to guard against code modifications at all times.  If you
live entirely in JRuby land, you can always back out optimizations.

But, if you are going to JIT Ruby code and enter JVM/HotSpot land, you have
to build in optimization guards throughout the code.  This means the IR has
to incorporate guard instructions.  For example, here are few types of

   type_guard(o, Fixnum, L)     <-- if type of o is not Fixnum, jump to L
   class_guard(Fixnum, L)       <-- if Fixnum has been monkey-patched, jump
to L
   method_guard(Fixnum, '+', L) <-- if Fixnum.+ has been monkey-patched,
jump to L

With this in mind, assuming (however you get this information) you expect
to dominate this call, you might compile the example above into:

   a = meth_arg(0)
   b = meth_arg(1)
   type_guard(a, Fixnum, L1)
   type_guard(b, Fixnum, L1)
   method_guard(Fixnum, '+', L1)

   m    = meth_addr Fixnum, 'value'  # Assume there is a static method
   args = [a]
   v1   = call, m, args
   m    = meth_addr Fixnum, 'value'  # Assume there is a static method
   args = [b]
   v2   = call, m, args
   v3   = add v1, v2                 # This is a standard ALU operation
(iadd bytecode)
   m    = meth_addr Fixnum, 'new'    # Assume there is a static method
   args = [v3]
   ret  = call m, args
   jump L2

   m    = meth_addr a, '+'
   args = [b]
   ret  = call m, args

   return ret

Clearly, there is a lot of overhead unboxing the objects -- but that is
the objects are being passed in as arguments.  But, you can see that if this
expression had one or both literals, the overhead drops.  If both were
the code reduces to boxing the result into a Fixnum.  But, if not, HotSpot
might be
able to inline the 'value' calls at this site and get rid of the unboxing

JRuby Inlining
Since HotSpot won't really be able to optimize the unboxing and add
type-based guards
as above, at some point, you might have to embrace method inlining.  For
you will use the high-level IR.

Consider this call site (Ruby):

  n = add(3,5)

This translates to (IR):

  args = [3,5]
  n = call 'add', args

After inlining (ignoring any required inlining guards for now), this changes
   args = [3,5]
   a    = args[0]
   b    = args[1]
   args = [b]
   ret  = ocall a, '+', args
   n    = ret

When you convert to SSA and run SCCP (Sparse Conditional Constant
Propagation) on this, you get:
   args = [5]
   ret = ocall 3, '+', args

After introducing type guards and re-running SCCP, you get:
   method_guard(Fixnum, '+', L1)
   v = 8
   ... code to box v into a Fixnum ...
   n = v
   jump L2
   args = [5]
   n = ocall 3, '+', args

Clearly, this is still simplistic because you might be boxing the 8 into a
prematurely, and it might never be needed.  So, in order to be able to
boxing and unboxing, it might be useful to introduce IR instructions that
boxing and unboxing of primitive types.  Since the target is the JVM, you
introduce boxing/unboxing IR instructions for JVM primitives.  Fixnum and
are obvious candidates.

So, box and unbox IR instructions could be:
   n = box_primitive(Fixnum, v)
   v = unbox_primitive(Fixnum, n)

With this, the inlined and optimized code above would become:
   method_guard(Fixnum, '+', L1)
   n = box_primitive(Fixnum, 8)
   jump L2
   args = [5]
   n = ocall 3, '+', args

The next problem is to propagate type information throughout a method to
optimizations to be as global as possible.  In the optimization analyses,
have the option of carrying around the state implicitly (carried along in
while running analyses), or explicitly (by introducing attribute
instructions in
the IR).  The implicit approach is easy and preferable for cases where
about a variable is not use-site specific (constant propagation, for
But for cases where this is not true, the explicit approach is preferable.
example, the type of an object along two paths of a branch would be
So, a variable 'v' (in SSA form) might have type 'Fixnum' along one path and
'String' along another.

I prefer the explicit approach:
- they lend themselves to easier debugging because when you dump the IR, you
  see what information is being generated.
- you convert use-site specific information to attributes that are no longer
  use-site specific (because every branched path gets its own SSA
- by converting site-use specific information to constants, you can
  transformations as part of regular constant propagation via SCCP.

I have used this approach to good benefit in my JVM compiler I wrote for my
dissertation -- I used this approach to eliminate null checks and array
bounds checks.

So, with this in mind, you will now augment all IR instructions to include
array of attributes.  So, the generic IR form will now be:

    v = OP(operands, attributes)

When you run SCCP on this, you also run SCCP on the attribute values.  This
you use attributes as additional meta-information to optimize that

For example, consider this sequence of IR instructions:

   v = 5
   a = box_primitive(Fixnum, v, [])
   a_attr = [BOXED_FIXNUM(v)]
   ... a is not used anywhere here ...
   b = a
   b_attr = a_attr
   x = unbox_primitive(Fixnum, b, [b_attr])
   y = x

When you run SCCP on this, here is what happens to the unbox_primitive
   x = unbox_primitive(Fixnum, b, [[BOXED_FIXNUM(v)]])

Thus, you know that you are unboxing a boxed value 'v'.  So, you can
simplify this
instruction to:
   x = v

So, when you run SCCP, the above sequence reduces to (I am excluding some
useless copies here)
   v = 5
   a = box_primitive(Fixnum, v, [])
   y = 5

After you run dead code elimination, assuming a is not used anywhere, the
code simplifies to
   v = 5
   y = 5

1. Every IR instruction is basically of the form
      v = OP(operand_array, attribute_array)

   Since this is a high-level IR, you are not bound to a 3-operand format.
   You can have an array of operands and an array of attributes.
   But, you can also have IR instructions of the form:
      v = OP(op1, attribute_array)
      v = OP(op1, op2, attribute_array)

2. You have regular ALU kind of IR instructions (add, sub, cmp, lshift,

3. You have various flavor of call instructions:
     v = call(method, args)
     v = ocall(receiver, method, args)
     ... and anything else you can think of ...

4. You have a method-address instruction:
     m = meth_addr(receiver, method)

5. Instructions to extract function/method arguments and return function
     x = meth_arg(arg_index)
     return y

6. You have various kinds of guard instructions:
     type_guard(obj, class, L)      <-- if type of obj is not class, jump to
     class_guard(class, L)          <-- if class has been monkey-patched,
jump to L
     method_guard(class, method, L) <-- if class.method has been
monkey-patched, jump to L

7. You have box/unbox instructions for primitives:
     n = box_primitive(class, v)
     v = unbox_primitive(class, n)

8. You have attribute instructions for passing around meta-information
(types, etc.)
     init_attr(a_attr, [])
     add_attr(a_attr, X)

    - a_attr is just naming convention.  As far as representation is
      it is just another SSA IR variable.
    - You need to identify the different types of meta-information you might
      around.  The X above is a place-holder for that.

    Some kinds of X are:
      - BOXED_FIXNUM(n)
      - BOXED_ARRAY(a)
      - HAS_TYPE(class)

This is it for the 1st pass.  More later with an example of closures.

Reply via email to