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 end 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 call. 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 constant propagation) algorithm which is linear and pretty fast for all practical purposes. 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 guards: 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 Fixnums 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 somewhere args = [a] v1 = call, m, args m = meth_addr Fixnum, 'value' # Assume there is a static method somewhere 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 somewhere args = [v3] ret = call m, args jump L2 L1: m = meth_addr a, '+' args = [b] ret = call m, args L2: return ret ---------- Clearly, there is a lot of overhead unboxing the objects -- but that is because 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 literals, 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 overhead. 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 inlining, 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 to: args = [3,5] a = args b = args 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 =  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 L1: args =  n = ocall 3, '+', args L2: ... Clearly, this is still simplistic because you might be boxing the 8 into a Fixnum prematurely, and it might never be needed. So, in order to be able to optimize boxing and unboxing, it might be useful to introduce IR instructions that encapsulate boxing and unboxing of primitive types. Since the target is the JVM, you will introduce boxing/unboxing IR instructions for JVM primitives. Fixnum and Array 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 L1: args =  n = ocall 3, '+', args L2: ... The next problem is to propagate type information throughout a method to allow optimizations to be as global as possible. In the optimization analyses, you have the option of carrying around the state implicitly (carried along in hashtables while running analyses), or explicitly (by introducing attribute instructions in the IR). The implicit approach is easy and preferable for cases where information about a variable is not use-site specific (constant propagation, for example). But for cases where this is not true, the explicit approach is preferable. For example, the type of an object along two paths of a branch would be different. 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 can 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 attribute). - by converting site-use specific information to constants, you can incorporate 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 an 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 lets you use attributes as additional meta-information to optimize that instruction. 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 instruction: 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 Summary: -------- 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, etc.) 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 values: 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 L 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) Note: - a_attr is just naming convention. As far as representation is concerned, it is just another SSA IR variable. - You need to identify the different types of meta-information you might pass 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.