Truffle DSL feature suggestions

[Stefan Marr]

Hi Christian,
Hi all:

On 07 Nov 2013, at 14:27, Christian Humer <christian.humer at gmail.com> wrote:

> Unfortunately it is not and I also failed myself to abuse it in that way. There are some features (eg. caching of values) missing to declare polymorphic inline caches using the DSL. At the moment all polymorphic inline caches are implemented manually using Truffle API only. We are still in phase of collecting required use-cases to compile a list of required DSL features to support it. There are some concepts like resorting of cache entries or generic cache entry promotion (not completely go to generic but keep some hot cache entries) which would also be quite difficult to support. But we would be happy if we could use your implementation as an additional use-case for DSL support.

I am just about to finish a rather large rewrite of TruffleSOM [1].
And for that it would be very useful if I could coerce the DSL into generating multiple cases out of a single specialization in order to handle polymorphic message sends.

Overall, I think, I have three suggestions based on the TruffleSOM rewrite.
I’ll try to detail them below to outline the use case and my understanding. Perhaps somethings are by design and should be done differently.

The three things I would like to suggest are:

 - Allowing @Generic for simple non-specializing nodes, as a base case (uninitialized state) for custom specialization hierarchies
 - Support for inheriting @NodeChilds
 - Support for polymorphic inline caching, perhaps based on chaining multiple instances of the same specialization.


Allowing @Generic for Simple Nodes
—————————————————————————————————-

In my new node hierarchy, I use UnaryMessageNode (..Binary/Ternary/KeywordMsgNode) [2] to represent the initial state of message send as generated by the parser. So, the main idea is to avoid specialization before execution starts. The parser could do some simple specializations already purely based on the static name of a message. However, I decided against doing that, following what I understand to be one of the main suggestions for Truffle.

As a result I have the UnaryMessageNode (Binary/Ternary/Keyword) class just implementing a doGeneric(.) method, which replace the node by a UnaryMonomorphicNode. For the doGeneric(.) method, I feel that @Generic would be the better annotation, and putting @Specialization there, because it otherwise wouldn’t have a specialization, feels a little unnatural. The @Generic annotation also has another benefit, because it enforces certain constraints on the method signature, which is useful to make the type system happy.


Support for inheriting @NodeChild
————————————————————————————————-

The next thing I noticed is that @NodeChild annotation are not inherited when the subclass defines additional @NodeChilds. While it is not a big issue, it feel counter intuitive when I noticed it for the first time. My expectation was that these annotations have an additive semantics.

As an example, I have a AbstractMonomorphicMessageNode [3] with the @NodeChild(value = “receiver”, ExpN.class) annotation, and in the subclass BinaryMonomorphicNode [4] I need to specify the receiver again, because I want to add an argument NodeChild.


Polymorphic Inline Caching
—————————————————————————-

I assume that you got already a number of specific use case form other Truffle languages, so I will try to outline how I would imagine potential support for PICs in the DSL based on what I see in TruffleSOM.

One thing upfront: I decided that it want to try to conflate the notion of monomorphic message sends and primitive implementations.
Thus, you will currently find the following hierarchy of nodes in TruffleSOM (still need to figure out whether that’s actually going to work):

ExpressionNode
+- AbstractMessageNode
|  +- AbstractMonomorphicMessageNode
|     +- BinaryMonomorphicNode
|     |  +- AdditionPrimitive
|     |  +- MultiplicationPrimitive
|     +- UnaryMonomorphicNode
|        +- PrintPrimitive
|        +- ...
+- BinaryMessageNode
+- UnaryMessageNode
+- ...

The reason why I thought that might be a good idea is to essential see every specialization for the primitive nodes as one variant of a potentially polymorphic message send.

Let’s assume we have a #print primitive implemented for strings, and normal #print messages for other types of object, implementing something custom to first convert the value into a string and then printing it.

So, a nice polymorphic example would be something like the following loop over an array: `{1. ’two’. #three. 4.0. FiveClass} do: [:elem | elem print]`.

The print primitive could than be implemented like this:

    public abstract class PrintStringPrim extends UnaryMonomorphicNode {
      public PrintStringPrim(final SSymbol selector, final Universe universe, final SClass rcvrClass, final SMethod invokable) {
                             super(selector, universe, rcvrClass, invokable); }
      public PrintStringPrim(final PrintStringPrim prim) { this(prim.selector, prim.universe, prim.rcvrClass, prim.invokable); }

      @Specialization
      public Object doSString(final SString receiver) {
        Universe.print(receiver.getEmbeddedString());
        return receiver;
      }
    }

And the UnaryMonomorphicNode implements a simple monomorphic method cache:

    public abstract class UnaryMonomorphicNode extends AbstractMonomorphicMessageNode {

      @Specialization(guards = "isCachedReceiverClass", order = PriorityMonomorphicCase)
      public SAbstractObject doMonomorphic(final VirtualFrame frame, final SAbstractObject receiver) {
        return invokable.invoke(frame.pack(), receiver, noArgs);
      }
    }

So, my understanding is now that a normal node that has multiple specializations, perhaps based on types, can become ’node-polymorphic’.
Thus, multiple specializations get instantiated and instead of replacing a previous specialization, they get chained one after another.
And then, during execution, you walk the chain to find the one where the guards do not fail.
I understand now that this chain can build up because there are multiple cases that can be easily identified based on different guards/tests.
However, for the doMonomorphic(.) method, it is not multiple tests, it is not multiple specializations. 
Instead, the value on which a test is based differs.

So, what I would find useful is if I could tell the DSL to multiply my specialization doMonomorphic(.) up to a given number of times, and then, I think for the instantiation, I would also need to give it a function that allows it to derive the necessary state for such ‘value-based’ specializations.

Perhaps something like this:

    @Specialization(guards = “isCachedReceiverClass”, order = PriorityMonomorphicCase,
                    multiplicity = 8, specialization = {rcvrClass = “classOfReceiver”, invokable = “lookUp” } )
    public SAbstractObject doMonomorphic(final VirtualFrame frame, final SAbstractObject receiver) { /* ... /* }

    public SClass classOfReceiver(final SAbstractObject receiver) {
      return classOfReceiver(receiver, getReceiver());
    }

    public SMethod lookUp(final SAbstractObject receiver) {
      return classOfReceiver(receiver).lookupInvokable(selector);
    }

I think, this might give me enough flexibility to express value-based specialization for polymorphic messages.

When it comes to cleaning up or optimizing such polymorphic-node chains, well, I don’t know enough how it would behave yet. So, no ideas there so far.

Would be interested to hear whether any of that sounds like it fits into how you see Truffle being used.

Thanks
Stefan



[1] https://github.com/smarr/TruffleSOM/commit/482ccaa88306a1e7a989afdfd91e4121c5be163a
[2] https://github.com/smarr/TruffleSOM/blob/482ccaa88306a1e7a989afdfd91e4121c5be163a/src/som/interpreter/nodes/UnaryMessageNode.java#L30
[3] https://github.com/smarr/TruffleSOM/blob/482ccaa88306a1e7a989afdfd91e4121c5be163a/src/som/interpreter/nodes/messages/AbstractMonomorphicMessageNode.java#L18
[4] https://github.com/smarr/TruffleSOM/blob/482ccaa88306a1e7a989afdfd91e4121c5be163a/src/som/interpreter/nodes/messages/BinaryMonomorphicNode.java#L21
-- 
Stefan Marr
Software Languages Lab
Vrije Universiteit Brussel
Pleinlaan 2 / B-1050 Brussels / Belgium
http://soft.vub.ac.be/~smarr
Phone: +32 2 629 2974
Fax:   +32 2 629 3525