Truffle DSL feature suggestions
Christian Humer
christian.humer at gmail.com
Fri Nov 8 08:48:18 PST 2013
Hi Stefan,
Seems that your making good progress!
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.
@NodeChild elements should be inherited already. Unfortunately there is a
bug when inheriting more than one @NodeChild defined int he base class and
there is another @NodeChild annotation defined in the inheriting class, the
second @NodeChild of the base class is not inherited. Seems that nobody
used this annotation in this way so far ;-). Will fix this and keep you
posted.
However, what already works is using a variable number of arguments
@NodeChild in the base class like this:
@NodeChildren({@NodeChild(value = "receiver", type = ValueNode.class),
@NodeChild(value = "arguments", type = ValueNode[].class)})
abstract static class BaseNode extends ValueNode {
public abstract ValueNode getReceiver();
public abstract ValueNode[] getArguments();
}
abstract static class UnaryNode extends BaseNode {
@Specialization
public int doIt(Object receiver, int value0) {
return value;
}
}
abstract static class BinaryNode extends BaseNode {
@Specialization
public int doIt(Object receiver, int value0, int value1) {
return value0 + value1;
}
}
abstract static class TernaryNode extends BaseNode {
@Specialization
public int doIt(Object receiver, int value0, int value1, int
value2) {
return value0 + value1 + value2;
}
}
Also take a look at the generated code. There you can see that instead of
accessing a field per child the generated source now accesses the children
in an array using fixed indexes. So for the third value it accesses
arguments[1].execute() to execute the value. Please note that all
specializations in one operation must have the same number of arguments.
Using the NodeFactory#getExecutionSignature() method you can find out the
actual number of arguments that were used dynamically. So you would be able
to write one generic rewrite mechanism.
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.
I see your point. Just @Generic should be possible. I've put it on my list.
I do not recommend doing manual replaces inside of @Specialization or
@Generic annotated methods at all. Think of the use-case of polymorphic
chains where a call to replace would just replace one entry of the
polymorphic chain. This would lead to a wrong tree. If you want do do that
please turn off the polymorphic chaining by using @PolymorphicDepth(0). But
I don't think you will need that if you do it the way I describe it below.
Polymorphic Inline Caching
> —————————————————————————-
First thanks for your input on the new DSL feature. I hope we will be able
to implement it soon.
Let me explain to you how polymorphic inline caches are currently
implemented in most of the truffle languages by referencing what i think
you want to achieve.
final class Message {
String name;
...
CallTarget target;
...
}
Each available message is represented as such an instance. A CallTarget for
the message can be created by a call to
Truffle.getRuntime().createCallTarget(...). These Message instances are
usually stored in a global map or a similar concept.
For a call you start off with one uninitialized call/message node which has
a child for receiving the function and one for the receiver.
class UninitializedSendNode {
message = ... // returns a Message (may do a lookup in a local variable or
global map)
receiver = ... // returns the receiver object
uninitializedArguments[] = ... // the uninitialized arguments of the call
as they are parsed
}
When the first call to the execute method in UninitializedMessageNode
occurs the uninitialized node creates a cache like this:
class CachedSendNode {
final CallTarget cachedTarget; // the call target this node is specialized
on
receiver, message;
uninitializedArguments[];
current = DispatchedSendNode // Implementation of the call (may get inlined
later or immediatly)
arguments // copied from uninitializedArguments
next = UninitializedMessageNode or again CachedSendNode
// how an implementation for that node could look like:
Object execute(VirtualFrame frame) {
Object receiver = receiver.execute(frame); // we need to ensure that the
receiver is just evaluated once per call
Message m = message.execute(frame);
if (this.cachedTarget == m.getCallTargetTarget()) {
return current.execute(frame, receiver);
}
return next.execute(frame, receiver);
}
}
This CachedSendNode can be chained as a cache using the next field. After
reaching some depth the chain should rewrite itself to a
GenericSendNode which then does not store the callTarget as a final field
but always dispatches the call to the callTarget (no inlining possible
anymore).
Each DispatchedSendNode knows about their callTarget as a final field and
just calls the constant/final CallTarget in the default case.
After some inlining policy (which could be immediately, later or not at
all) the DispatchedSendNode gets replaced by a compatible node which
represents the CallTarget. This can usually be achieved by casting the
CallTarget to DefaultCallTarget and looking at its RootNode to copy it.
I think the described pattern should work for you and it has been proven to
work for our implementations.
I will try to put together an example using the SimpleLanguage next week.
Have a nice weekend!
Christian Humer
On Thu, Nov 7, 2013 at 5:30 PM, Stefan Marr <java at stefan-marr.de> wrote:
> 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
>
>
More information about the graal-dev
mailing list