Truffle Tutorial Slides Personal translation memo ①

Truffle Tutorial Slides (30-60p) This is my own translation memo.

We do not guarantee mistranslations or omissions.

If there is a problem, delete it.

Highlights of SL (A Simple Language)

--Any type of key and value can be used

--The key is usually of type String

Mold

SL type value Implementation in Java?(Java Type in Implementation)
Number Arbitrary precision integer Long within 64 bits
If it overflows java.lang.BigInteger
Boolean true or false boolean
String Unicode string java.lang.String
Function Reference to function SLFunction
Object Key and value DynamicObject
Null null SLNull.SINGLETON

best practice

syntax

C-like control syntax

operator

literal

Built-in function? (Builtin functions)

Parsing

Abbreviation

SL example

Abbreviation

Getting Started

Abbreviation

AST interpreter

I'm sorry I omit

Truffle nodes and trees

Class Node

Base class of Truffle node? (base class of all Truffle tree nodes)

NodeUtil provides convenient utility methods.

public abstract class Node implements Cloneable {
    public final Node getParent() { ... }
    public final Iterable<Node> getChildren() { ... }
    public final <T extends Node> T replace(T newNode) { ... }
    public Node copy() { ... }
    public SourceSection getSourceSection();
} 

If syntax

public final class SLIfNode extends SLStatementNode {
    
    @Child private SLExpressionNode conditionNode;
    @Child private SLStatementNode thenPartNode;
    @Child private SLStatementNode elsePartNode;
    
    public SLIfNode(SLExpressionNode conditionNode, SLStatementNode thenPartNode, SLStatementNode elsePartNode) {
        this.conditionNode = conditionNode;
        this.thenPartNode = thenPartNode;
        this.elsePartNode = elsePartNode;
    }
    
    public void executeVoid(VirtualFrame frame) {
        if (conditionNode.executeBoolean(frame)) {
            thenPartNode.executeVoid(frame);
        }else{
            elsePartNode.executeVoid(frame);
        }
    }
}

Annotate the field of the child node with @Child and do not make it final.

If syntax with profiling

public final class SLIfNode extends SLStatementNode {
    
    @Child private SLExpressionNode conditionNode;
    @Child private SLStatementNode thenPartNode;
    @Child private SLStatementNode elsePartNode;
    private final ConditionProfile condition = ConditionProfile.createCountingProfile();
    
    public SLIfNode(SLExpressionNode conditionNode, SLStatementNode thenPartNode, SLStatementNode elsePartNode) {
        this.conditionNode = conditionNode;
        this.thenPartNode = thenPartNode;
        this.elsePartNode = elsePartNode;
    }
    
    public void executeVoid(VirtualFrame frame) {
        if (condition.profile(conditionNode.executeBoolean(frame))) {
            thenPartNode.executeVoid(frame);
        }else{
            elsePartNode.executeVoid(frame);
        }
    }
}

Profiling with an interpreter allows the compiler to generate better code.

block

public final class SLBlockNode extends SLStatementNode {
    
    @Children private final SLStatementNode[] bodyNodes;
    
    public SLBlockNode(SLStatementNode[] bodyNodes) {
        this.bodyNodes =  bodyNodes;
    }
    
    @ExplodeLoop public void executeVoid(VirtualFrame frame) {
        for (SLStatementNode statement : bodyNodes) {
            statement.executeVoid(frame);
        }
    }
}

return syntax: Control flow between nodes

public final class SLReturnNode extends SLStatementNode {
    
    @Child private SLExpressionNode valueNode;
    
    ...
    
    public void executeVoid(VirtualFrame frame) {
        throw new SLReturnException(valueNode.executeGeneric(frame));
    }
}
public final class SLReturnException extends ControlFlowException {
    
    private final Object result;
    
    ...
}
public final class SLFunctionBodyNode extends SLExpressionNode {
    
    @Child private SLStatementNode bodyNode;
    
    ...
    
    public Object executeGeneric(VirtualFrame frame) {
        try {
            bodyNode.executeVoid(frame);
        }catch (SLReturnException ex){
            return ex.getResult();
        }
        return SLNull.SINGLETON;
    }
}

Inter-node control with exceptions? (Exceptions for Inter-Node Control Flow)

Does the exception rewind all stack frames? (Exception unwinds all the interpreter stack frames of the method (loops, conditions, blocks, ...))

Addition? (Addition)

@NodeChildren({@NodeChild("leftNode"), @NodeChild("rightNode")})
public abstract class SLBinaryNode extends SLExpressionNode {
}

public abstract class SLAddNode extends SLBinaryNode {
    
    @Specialization(rewriteOn = ArithmeticException.class)
    protected final long add(long left, long right) {
        return ExactMath.addExact(left, right);
    }
    
    @Specialization
    protected final BigInteger add(BigInteger left, BigInteger right) {
        return left.add(right);
    }
    
    @Specialization(guards = "isString(left, right)")
    protected final String add(Object left, Object right) {
        return left.toString() + right.toString();
    }
    
    protected final boolean isString(Object a, Object b) {
        return a instanceof String || b instanceof String;
    }
} 

Code generated by Truffle DSL ①

Code generated by factory methods

@GeneratedBy(SLAddNode.class)
public final class SLAddNodeGen extends SLAddNode {

    public static SLAddNode create(SLExpressionNode leftNode, SLExpressionNode rightNode) {
        ... 
    }
    
    ...
}

Code generated by Truffle DSL ②

@GeneratedBy(methodName = "add(long, long)", value = SLAddNode.class)
private static final class Add0Node_ extends BaseNode_ {
    
    @Override public long executeLong(VirtualFrame frameValue) throws UnexpectedResultException {
        long leftNodeValue_;
        try {
            leftNodeValue_ = root.leftNode_.executeLong(frameValue);
        }catch (UnexpectedResultException ex){
            Object rightNodeValue =  executeRightNode_(frameValue);
            return SLTypesGen.expectLong(getNext().execute_(frameValue,  ex.getResult(), rightNodeValue));
        }
        long rightNodeValue_;
        try {
            rightNodeValue_ = root.rightNode_.executeLong(frameValue);
        }catch (UnexpectedResultException ex){
            return SLTypesGen.expectLong(getNext().execute_(frameValue,  leftNodeValue_, ex.getResult()));
        }
        try {
            return root.add(leftNodeValue_, rightNodeValue_);
        } catch (ArithmeticException ex) {
            root.excludeAdd0_ = true;
            return SLTypesGen.expectLong(remove("threw rewrite exception", frameValue, leftNodeValue_, rightNodeValue_));
        }
    }
    
    @Override public Object execute(VirtualFrame frameValue) {
        try {
            return executeLong(frameValue);
        } catch (UnexpectedResultException ex) {
            return ex.getResult();
        }
    } //The original article does not have this closing brace
}

Truffle DSL type system definition

@TypeSystem({long.class, BigInteger.class, boolean.class,              String.class, SLFunction.class, SLNull.class})
public abstract class SLTypes {
    @ImplicitCast
    public BigInteger castBigInteger(long value) {
        return BigInteger.valueOf(value);
    }
}
@TypeSystemReference(SLTypes.class)
public abstract class SLExpressionNode extends SLStatementNode {
    
    public abstract Object executeGeneric(VirtualFrame frame);
    
    public long executeLong(VirtualFrame frame) throws UnexpectedResultException {
        return SLTypesGen.SLTYPES.expectLong(executeGeneric(frame));
    }
    
    public boolean executeBoolean(VirtualFrame frame) ...
} 

UnexpectedResultException

Truffle DSL workflow

Abbreviation

Frame layout

--Is the function assigned to the prologue? (Allocated in the function prologue)

--Passed as a parameter to the execute () method? (Passed around as parameter to execute () methods)

--Mapping from identifiers (usually variable names) to typed slots? (A mapping from identifiers (usually variable names) to typed slots.) -Does every slot have a unique index to the frame object? (Every slot has a unique index into the frame object.) --Created and filled during parsing.

--Created for each function of your own (Guest) language called.

Frame management

--Automatically optimized by the compiler. --Do not assign to fields or leave the interpreted function.

--A frame that can be stored without restrictions? (A frame that can be stored without restrictions) --Example: Closure frame that needs to be passed to another function? (frame of a closure that needs to be passed to other function)

--Factory method of TruffleRuntime class

Frame management

public interface Frame {
    
    FrameDescriptor getFrameDescriptor();
    Object[] getArguments();
    boolean isType(FrameSlot slot);
    
    Type getType(FrameSlot slot) throws FrameSlotTypeException;
    
    void setType(FrameSlot slot, Type value);
    
    Object getValue(FrameSlot slot);
    
    MaterializedFrame materialize();
}

Local variables

@NodeChild("valueNode")
@NodeField(name = "slot", type = FrameSlot.class)
public abstract class SLWriteLocalVariableNode extends SLExpressionNode {
    
    protected abstract FrameSlot getSlot();
    
    @Specialization(guards = "isLongOrIllegal(frame)")
    protected long writeLong(VirtualFrame frame, long value) {
        getSlot().setKind(FrameSlotKind.Long);
        frame.setLong(getSlot(), value);
        return value;
    }
    
    protected boolean isLongOrIllegal(VirtualFrame frame) {
        return getSlot().getKind() == FrameSlotKind.Long || getSlot().getKind() == FrameSlotKind.Illegal;
    }
    
    ...
     
    @Specialization(contains = {"writeLong", "  writeBoolean"})
    protected Object write(VirtualFrame frame, Object value) {
        getSlot().setKind(FrameSlotKind.Object);
        frame.setObject(getSlot(), value);
        return value;
    }
}
@NodeField(name = "slot", type = FrameSlot.class)
public abstract class SLReadLocalVariableNode extends SLExpressionNode {
    
    protected abstract FrameSlot getSlot();
    
    @Specialization(guards = "isLong(frame)")
    protected long readLong(VirtualFrame frame) {
        return FrameUtil.getLongSafe(frame, getSlot());
    }
    
    protected boolean isLong(VirtualFrame frame) {
        return getSlot().getKind() == FrameSlotKind.Long;
    }
    
    ...
        
    @Specialization(contains = {"readLong", "readBoolean"})
    protected Object readObject(VirtualFrame frame) {
        if (!frame.isObject(getSlot())) {
            CompilerDirectives.transferToInterpreter();
            Object result = frame.getValue(getSlot());
            frame.setObject(getSlot(), result);
            return result;
        }
        return FrameUtil.getObjectSafe(frame, getSlot());
    }
} //There is no closing brace in the original text

compile? (Compilation)

--It starts automatically depending on the number of times the function is executed.

--All @Child and @Children fields are treated like final.

--Send back "deoptimization" to the interpreter? (Transfer back to the interpreter: “Deoptimization”) --Isn't the complex logic for node rewriting part of the compiled code? (Complex logic for node rewriting not part of compiled code) -Indispensable for excellent peak performance? (Essential for excellent peak performance)

--Would you like to dispatch any more between nodes? (No more dispatch between nodes) --Would you like to allocate more VirtualFrames? (No more allocation of VirtualFrame objects) --No more exceptions for inter-node control flow? (No more exceptions for inter-node control flow)

Recommended Posts

Truffle Tutorial Slides Personal translation memo ①
docker tutorial (memo)
[Personal memo] try-catch summary
[Translation] Byte Buddy Tutorial
[Personal memo] About Spring framework
Personal memo Progate Ruby I (2)
[Swift] Closure basics (personal memo)
Personal memo Eclipse plug-in installation
[Personal memo] Number guessing game
Personal memo Lombok's typical annotation
Personal memo Progate Ruby I (1)
Apache Shiro tutorial translation summary
Java HashMap, entrySet [Personal memo]