[JAVA] 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)

• Dynamic typing
• Strong typing
• No implicit type conversion
• Arbitrary precision integer
• First-class function
• Dynamic function definition? (Dynamic function redefinition)
• Objects are data structures that store keys and values

--Any type of key and value can be used

--The key is usually of type String

Mold

• Is Null a type that has itself? (Null is its own type)
• Also called "Undefined"

best practice

• Use primitive types as much as possible for performance

• Don't use Java null in your Guest language

syntax

C-like control syntax

• if, while, break, continue, return

operator

• +, -, *, /, ==, !=, <, <=, >, >=, &&, ||, ()
• \ + Is also defined as a string concatenation operator
• ||When&&Has short-circuit evaluation
• Use. Or [] to access the property? (. or [] for property access)

literal

• Number, String, Function

Built-in function? (Builtin functions)

• println, readln: Standard I / O
• nanoTime: Time measurement? (to allow time measurements)
• defineFunction: Dynamic function definition? (Dynamic function redefinition)
• stacktrace, helloEqualsWorld: "stack walking" and "stack frame" operations
• new: Assign a new object without properties

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)

• Parent / child management
• Replace itself with a new node? (Replacement of this node with a (new) node)
• Copy of node
• The execute () method is defined in a subclass, so why not define it here? (No execute () methods: define your own in subclasses)

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);
        }
    }
}

• Fields that represent multiple nodes are represented by a final array with @Children.

• Do I need to add @ExplodeLoop when repeating child elements? (The iteration of the children must be annotated with @ExplodeLoop)

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;
    }
}

• Use exceptions for control flow between nodes.
• Exception used for control flow inherits ControlFlowException.

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;
    }
} 

• The order of the @Specialization methods is important. The first matching element is selected.

• In all other specializations, guarding is implicit based on the method signature.

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) {
        ... 
    }
    
    ...
}

• The parser uses the factory to create a node that is initially in the uninitialized state.
• The generated code performs all the transitions between specialization states.

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);
    }
}

• Use @TypeCheck and @TypeCast to customize type conversions.

@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)　...
} 

• SLTypesGen is a generated subclass of SLTypes.
• In addition to abstract executeGeneric (), execute () method for each specialization

UnexpectedResultException

• Type-specific execute () methods have a special return type --Allow primitive return types to avoid autoboxing. --Results can be used without casting. (Allows to use the result without type casts)

• Speculation types are stable and the specialization fits.

• But what to do when speculation was too optimistic? --You need to return a value with a more general type than the return value. --Returns the value "boxed" with UnexpectedResultException.

• Exception handler performs node rewriting --There is no performance bottleneck as exceptions are thrown only once.

Truffle DSL workflow

Abbreviation

Frame layout

• Frames are objects on the heap.

--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)

• The compiler removes the assignment.

• No object allocation and object access. --Local variables in your Guest language perform the same as in Java.

• FrameDescriptor: describes the layout of a frame.

--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.

• Frame

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

Frame management

• The Truffle API only exposes the frame interface. --Implementation class depends on the optimization system.

• Virtual frame

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

• Materialized Frame

--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)

• Frame allocation

--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();
}

• Frames support all Java primitive types and objects.

• SL String, SLFunction, SLNull are stored as Object.

• Do not allocate frames or implement frames.

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;
    }
}

• If kind? Is long, setKind () does nothing.
• If you can't specialize in a single primitive type, switch all reads and writes to Object.

@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

• guard ensures that the frame slot contains a long value.
• Can I still write a frame with primitive values before switching a local variable to type Object? (we can still have frames with primitive values written before we switched the local variable to the kind Object.)

compile? (Compilation)

• Automatic partial evaluation of abstract syntax trees.

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

• Compilation assumes that the abstract syntax tree is stable

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

• Does later node rewriting invalidate the machine code? (Later node rewriting invalidates the machine code)

--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)

• Compiler optimization eliminates interpreter overhead.

--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)