How things worked
Here's how the current algorithm works. Method inlining takes place within Factor's sparse conditional constant propagation pass. SCCP infers upper bounds for the classes of values that the code manipulates. When SCCP processes a generic word call, it examines the class of the receiver as well as the list of classes that have methods on the generic word. If SCCP can tell that a particular method will always be called, it can select that method. Below is some pseudocode for how it detects that.
For each method on the generic word:
If the class for that method intersects the receiver class:
If the class for that method is a superclass of the receiver class:
Put it on a list
We don't know whether this method will be called at runtime
or not, so bail out and fail to inline a method
Inline the method for the smallest class on the list
There's an additional complication. It might be that a word is compiled, with the method inlining optimization applied, but then after this, more vocabs get loaded that add additional methods to the generic word. This might invalidate the correctness of the method inlining, and the word should get recompiled to fix this problem. Factor uses a simple system to track these dependencies, in
My new addition
A few days ago, another Factor developer told me about a hack he'd added to SCCP to make a particular benchmark faster. The hack was, if
>fixnumis called on an object that SCCP knows is either a
f, then the
>fixnumcall is replaced with
dup [ \ >fixnum no-method ] unless. This works because
>fixnumdoesn't have any methods on
fixnums is a no-op.
My immediate instinct here was to generalize this solution. The first step is to convert that code into
dup fixnum? [ M\ fixnum >fixnum ] [ \ >fixnum no-method ] if, which we can do since
>fixnumdoesn't have any other methods on the union of
fixnum. Unlike the kind of method inlining described earlier, this requires the insertion of a guard. Later code will know (through SCCP) that the object is a
fixnum, even after the conditional exits, since it can tell that an exception would be thrown otherwise.
The second step is to convert
>boolean, which we can do because we know that the value on the top of the stack is either
fixnum. With these two transformations, we should generate the same code as the hack generated, but the transformation should also work on other things.
The second change was easy. I just added custom inlining for the
instance?word to detect basically this exact case, and convert the test into
>booleanwhen this is valid.
The first change was a lot more work. First, I had to come up with the algorithm for choosing the right method (even if it seems obvious now in retrospect).
Make a list of methods on the generic word whose class intersects the receiver class
If this list consists of one element, then return it
If the list consists of multiple or zero elements, then there is no method to inline
Once this class is found, then propagation should generate code like this:
dup method's-class instance? [
M\ method's-class generic-word execute
\ generic-word no-method
This is valid because we know that, if the receiver fails the test, then it must be of some class that has no method on the generic word.
An extra requirement for the correct implementation of this compiler optimization is to track dependencies. For this, I made two new types of dependencies. One corresponds to the test that the generic word only has one particular method intersecting the class that's on the stack. The other tracks if a method that's inlined is overwritten. I wasn't able to reuse the dependency tracking for the other kind of method inlining, but it all fits into the same framework and didn't take much code.
All of this was pretty hard for me to debug, but it was a fun thing to work on. Among the code loaded in a basic development image, over 2400 methods are inlined using this technique, which were previously impossible to inline. There was probably also more method inlining done following this, due to improved type information, though I haven't collected statistics. And most importantly, I was able to eliminate the hack with
>fixnumwith no regression in performance.
Once I get a couple kinks worked out, this should be merged into mainline Factor. For now, it's in the propagation branch of my repository.