Instruction Set

Overview

Mu uses a variant of static single assignment (SSA) form and a comprehensive but low-level instruction set.

Conventions

If the results of an instruction is not mentioned, the instruction produces no results. Otherwise an instruction produces one result, unless explicitly stated otherwise.

In all examples in this chapter, the following definitions are assumed to be present:

.typedef @i1  = int<1>
.typedef @i8  = int<8>
.typedef @i16 = int<16>
.typedef @i32 = int<32>
.typedef @i64 = int<64>
.typedef @float  = float
.typedef @double = double
.typedef @void = void
.typedef @refvoid     = ref<@void>
.typedef @irefvoid    = iref<@void>
.typedef @weakrefvoid = weakref<@void>
.typedef @refi64  = ref<@i64>
.typedef @irefi64 = iref<@i64>
.typedef @sref    = stackref
.typedef @tref    = threadref
.typedef @tagref64 = tagref64

.typedef @4xi32 = vector<@i32 4>
.typedef @4xfloat = vector<@float 4>
.typedef @2xdouble = vector<@double 2>

.const @I32_0 <@i64> = 0
.const @I32_1 <@i64> = 1
.const @I64_0 <@i64> = 0
.const @I64_1 <@i64> = 1
.const @F_0 <@float> = 0.0f
.const @F_1 <@float> = 1.0f
.const @F_NAN <@float> = nanf
.const @D_0 <@double> = 0.0d
.const @D_1 <@double> = 1.0d
.const @D_NAN <@double> = nand

.const @NULLREF <@refvoid> = NULL

SSA Variables

Mu uses a variant of static single assignment (SSA) form. The single-definition rule still applies, but PHI-nodes are replaced with parameters at the beginning of basic blocks. Variables also do not live across basic blocks, and must be explicitly passed.

An SSA variable, or variable when unambiguous, holds a data value of a specific type. Every variable is defined (assigned) in exactly one place, but an SSA variable may hold different values in different contexts at different times.

NOTE: The original publications about SSA used the term "SSA form" and simply "variable". This specification uses the term "SSA variable" to emphasise that they are not variables in the usual sense that they can be updated arbitrarily as opposite to "constants". Most SSA variables, or simply "variables", in Mu never change. Some are changeable (instructions) not because they are assigned in another place, but because they themselves are re-evaluated.

For LLVM users: The concept of SSA variable or variable is the counterpart of the concept of SSA value or value in LLVM. Mu uses the traditional terminology that "a variable holds a value".

SSA variable
- Global SSA variable
  - Constant
  - Global cell reference
  - Function reference
  - Exposed function
- Local SSA variable
  - Parameter
  - Instruction result

A global SSA variable is valid in the whole Mu instance after it is defined. Their values never change.

A constant is a global SSA variable. Its value is the constant value.
A global cell is a global SSA variable. Its value is an internal reference to the global cell. (NOTE: The content in the global cell can change, but its iref never changes.)
A function is a global SSA variable. Its value is a funcref to the function. (NOTE: A function version is NOT an SSA variable. Redefining the function does not change the value of the function.)
An exposed function (defined by the top-level function exposing definition, not by the @uvm.native.expose instruction or the expose API) is a global SSA variable. Its value is the calling-convention-specific exposed value.

A local SSA variable is valid in the same basic block of the same function activation (frame) it is in.

A parameter is a local SSA variable whose value is the value passed to the basic block as an argument.
An instruction result is a local SSA variable whose value is one of the (0, 1 or many) results of the latest evaluation of an instruction in the current frame (defined later).

Whether an SSA variable uses the memory is implementation dependent. An SSA variable does not have a memory location.

NOTE: This allows a Mu implementation to store constants in the machine instruction flow as immediate values, or save the result of some instructions in registers and also spilling some other registers to the stack.

A local variable can be live or dead.

A parameter is live when the current instruction of the frame is in the basic block.
An instruction result is live in its basic block after the instruction is executed. For terminator instructions, the result(s) may only be live when the instruction will continue with some destinations but not others. These cases are defined by concrete instructions.

Otherwise it is dead.

TODO: Check if the definition of "local variable being live/dead" is (or will be) used in other parts of the specification. Currently only mentioned in "a live stack contains all live local variables". This definition may not be necessary.

The execution of an instruction is called an evaluation. An evaluation determines its results, and this process is called value computation. Accessing the memory (see Memory Model) or changing the state of the execution environment is called side effect. An evaluation may have side effects.

Common Structures

The following grammar structures are common to several instructions.

Lists

typeList ::= < type _rep >
funcSigList ::= <[ funcSig _rep ]>
argList ::= ( var _rep )

where type, funcSig and var are names of types, function signatures and SSA variables, respectively. The "rep" means there may be zero or more such names.

A type list is a list of types.

A function signature list is a list of function signatures. This is only used in COMMINST to distinguish from type lists. Ordinary instructions usually take no more than one function signature as argument, so the function signature is written in angular brackets < > directly in the same way as types.

An argument list is a list of SSA variables.

Example:

SWAPSTACK %swappee RET_WITH <@T1 @T2> PASS_VALUES <@U1 @U2 @U3> (%a1 %a2 %a3)

%val = COMMINST @uvm.native.expose [#DEFAULT] <[@sig]> (%func @COOKIE)

CALL     <@sig> @func (%arg0 %arg1 %arg2)
TAILCALL <@sig> @func (%arg0 %arg1 %arg2)
CCALL    #DEFAULT <@func_ty @sig> @func (%arg0 %arg1 %arg2)
NEWTHREAD %stack PASS_VALUES <@T1 @T2 @T3> (%arg0 %arg1 %arg2)
COMMINST @some.common.instruction (%arg0 %arg1 %arg2)

Destination Clause

destClause ::= dest argList

dest: basic block: The destination
argList: list of SSA variable: Arguments to the destination basic block

The destination clause designates a basic block as the destination of branching, either normal or exceptional. It takes many arguments, which will be received by the normal parameters of dest. The arguments must match the number and the types of the normal parameters. The exceptional parameter does not need to be explicitly passed to.

Only terminator instructions may have destination clauses.

Exception Clause

excClause ::= ( EXC ( nor exc ) ) _opt

nor: destination clause: The normal destination
exc: destination clause: The exceptional destination

The exception clause provides two destinations for instructions that may have diverging control flows. nor and exc are the normal destination and the exceptional destination, respectively.

The exception clause can be omitted. Any instruction that may have exception clauses is not a terminator (see Mu IR) if the exception clause is omitted. Otherwise it is a terminator.

Any instruction that may have exception clause may continue normally or continue exceptionally. An instruction shall continue normally unless explicitly defined otherwise.

When continuing normally,
- if the exception clause is absent, then the execution continues with the next instruction after the current instruction;
- if the exception clause is present, then branch to the normal destination.
When continuing exceptionally,
- if the exception clause is absent, it has undefined behaviour unless explicitly defined to be otherwise in some instructions;
- if the exception clause is present, then branch to the exceptional destination.

For example, the CALL instruction has an exception clause. When the exception clause is omitted, it does not have undefined behaviour. Instead the exception will be thrown out of the current function:
%entry():
    ...
    %rv1 = CALL <@sig1> @func1 (%arg0 %arg1)                                // throw out
    %rv2 = CALL <@sig2> @func2 (%arg0 %arg1) EXC(%cont(%a) %exc_hdlr(%b))   // caught locally
%cont(<@T> %a):
    ...
%exc_hdlr(<@T> %b) [%exc]:
    ...
On the contrary, UDIV and SDIV rely on the exceptional destination to handle the case of division by zero. If the exception clause is omitted and the right-hand-side operand is zero, then they have undefined behaviours:
%entry():
    %rv1 = SDIV <@i64> %some_val @I64_0                             // undefined behaviour
    %rv2 = SDIV <@i64> %some_val @I64_0 EXC(%cont() %exc_hdlr())    // handled locally
%cont():
    ...
%exc_hdlr():
    ... // handle divide-by-zero error here

Keep-alive Clause

keepAliveClause ::= ( KEEPALIVE ( lv _rep ) ) _opt

lv _rep: list of local SSA variable: A sequence of local SSA variables. Those SSA variables are forced to be alive.

The keep-alive clause keeps some local SSA variables alive. During stack introspection, exactly the local variables in the keep-alive clause of the current instruction in any stack frames can be introspected. This clause is intended to assist on-stack replacement.

A variable in the keep-alive clause is considered a "use" of it. It must obey the SSA requirement that the definition of a local variable dominates all its uses.

The absence of a keep-alive clause is equivalent to a keep-alive clause with zero local variables.

Example: The TRAP instruction optionally has a keep-alive clause. The values of those variables in the clause are available for the client to introspect:
%a = ADD ...
%b = SUB ...
%c = MUL ...
%trap1 = TRAP <@ty>                     // Does not keep alive any variables
%trap2 = TRAP <@ty> KEEPALIVE(%a %b)    // Keep %a and %b alive

Flag and Flag List

flag ::= # [A-Z_] _rep

flagList ::= [ flag _rep ]

In the text form, a flag starts with a hash character # which is followed by many capital letters [A-Z] or underscores _.

Examples:

#DEFAULT

#STDCALL

#ADD

#SIGNED_OVERFLOW

A flag list is a list of flags. Currently only used by the COMMINST super instruction.

Examples:

[ #FLAG_FOO #FLAG_BAR #FLAG_BAZ ]

[]

NOTE: The purpose of flags is to allow the IR to be extended without changing the IR grammar. One particular user is the calling convention. Available calling conventions differ from platform to platform and they cannot be described by a fixed set of key words.

Basic Operations

Binary Operations

binOp < T > op1 op2 excClause

binOp: The binary operation.
T: type: The type of both operands.
op1, op2: variable of type T: The two operands.
excClause: exception clause: the destination for erroneous conditions.
result:: Type T: return the result of the computation.

binOp is one in the following table:

binOp	opcode	T	operation
ADD	0x01	int	add
SUB	0x02	int	subtract
MUL	0x03	int	multiply
SDIV	0x04	int	signed divide
SREM	0x05	int	signed remainder
UDIV	0x06	int	unsigned divide
UREM	0x07	int	unsigned remainder
SHL	0x08	int	left shift
LSHR	0x09	int	logical right shift
ASHR	0x0A	int	arithmetic right shift
AND	0x0B	int	bit-wise and
OR	0x0C	int	bit-wise or
XOR	0x0D	int	bit-wise exclusive or
FADD	0xB0	FP	FP add
FSUB	0xB1	FP	FP subtract
FMUL	0xB2	FP	FP multiply
FDIV	0xB3	FP	FP divide
FREM	0xB4	FP	FP remainder

TODO: Move the opcode to the IR Builder API.

In all binary operations, the type of both op1 and op2 must have type T.

For ADD, SUB, MUL, SDIV, SREM, UDIV, UREM, SHL, LSHR, ASHR, AND, OR and XOR, T must be int of a vector of int.

For FADD, FSUB, FMUL, FDIV and FREM, T must be a floating point type or a vector of floating point type.

When T is a vector type, the operation is applied for the corresponding elements of the two vectors.

SDIV, SREM, UDIV and UREM may have exception clause. For other operations, the exception clause must be omitted.

For ADD, SUB and MUL, both operands are considered unsigned. When overflow, returns the result modulo 2^n where n is the length of T.

NOTE: Since negative numbers are encoded in the 2's complement notation, ADD, SUB and MUL work for both signed and unsigned numbers.

For SDIV, SREM, UDIV and UREM, when dividing by zero, it continues exceptionally. For SDIV and SREM, when overflow, the result is truncated to n bits where n is the length of T.

For SHL, LSHR and ASHR, the second operand op2 is considered unsigned. Only the lowest m bits of op2 are used, where m is the smallest integer that 2^m >= n and n is the length T.

NOTE: For 32-bit and 64-bit integers, the lowest 5 and 6 bits of op2 are used, respectively. This is the "natural" behaviour of x86_64 and A64, but not ARMv7.

All floating point operations follow the IEEE 754 standard. They use the default roundTiesToEven rounding attribute. If either operand is NaN, the result is NaN. Floating point exceptions do not cause exceptional control flow in Mu.

Semantics:

ADD: Return the sum of the two operands.
SUB: Return the difference of the two operands.
MUL: Return the product of the two operands.
SDIV: Return the quotient of the two operands, rounded towards zero.
SREM: Return the remainder of the two operands.
UDIV: Return the quotient of the two operands, rounded towards zero.
UREM: Return the remainder of the two operands.
SHL: Return the value of op1 shifted to the left by the value of some lowest bits of op2.
LSHR: Return the value of op1 shifted to the right by the value of some lowest bits of op2. The most significant bits of the shifted value are filled with 0.
ASHR: Return the value of op1 shifted to the right by the value of some lowest bits of op2. The most significant bits of the shifted value are filled with the most significant bit of op1.
AND: Return the result of bit-wise AND.
OR: Return the result of bit-wise inclusive OR.
XOR: Return the result of bit-wise exclusive OR.
FADD: Return the sum of the two operands.
FSUB: Return the difference of the two operands.
FMUL: Return the product of the two operands.
FDIV: Return the quotient of the two operands.
FREM: Return the remainder of the two operands.

For LLVM users: this is directly borrowed from LLVM. Exceptional cases, including division by zero and signed division overflow, have defined behaviours in Mu.

Example:

.const @a <@i32>    = 42
.const @x <@double> = 42.0d
.const @z <@i64>    = 0

// in some function
%entry():
    %b = ADD <@i32> @a @I32_1
    %c = SUB <@i32> @a %b

    %y = FADD <@double> @x @D_1
    %z = FSUB <@double> @x %y

    // The presence of the exception clause makes it a terminator
    %d = UDIV <@i32> %b @z EXC(%cont() %handler())   // terminator

%cont():
    ...     // continue on normal condition

%handler():
    ...     // handle divide-by-zero error here

Comparison

cmpOp < T > op1 op2

cmpOp

The comparison operation.

T

type: The type of both operands.

op1, op2

variable of T: The two operands.

result:

If T is a scalar type, then the result type is int<1>: returns 1 for true or 0 for false, or
If T is a vector type, then the result type is vector<int<1> n>: returns a vector of int<1> where each element is the result of the comparison of the corresponding elements.

cmpOp is one in the following table:

cmpOp	opcode	T	Condition
EQ	0x20	EQ-comparable	equal
NE	0x21	EQ-comparable	not equal
SGE	0x22	int	signed greater than or equal
SGT	0x23	int	signed greater than
SLE	0x24	int	signed less than or equal
SLT	0x25	int	signed less than
UGE	0x26	ULT-comparable	unsigned greater than or equal
UGT	0x27	ULT-comparable	unsigned greater than
ULE	0x28	ULT-comparable	unsigned less than or equal
ULT	0x29	ULT-comparable	unsigned less than
FFALSE	0xC0	FP	always false
FTRUE	0xC1	FP	always true
FUNO	0xC2	FP	unordered
FUEQ	0xC3	FP	unordered equal
FUNE	0xC4	FP	unordered not equal
FUGT	0xC5	FP	unordered greater than
FUGE	0xC6	FP	unordered greater than or equal
FULT	0xC7	FP	unordered less than
FULE	0xC8	FP	unordered less than or equal
FORD	0xC9	FP	ordered
FOEQ	0xCA	FP	ordered equal
FONE	0xCB	FP	ordered not equal
FOGT	0xCC	FP	ordered greater than
FOGE	0xCD	FP	ordered greater than or equal
FOLT	0xCE	FP	ordered less than
FOLE	0xCF	FP	ordered less than or equal

TODO: Move the opcode to the IR Builder API.

In all comparison operations, both op1 and op2 must have type T.

For EQ and NE, T must be a EQ-comparable type (see type-system.rest) or a vector of EQ-comparable types.

For SGE, SGT, SLE, SLT, UGE, UGT, ULE and ULT, T must be int or a vector of int.

For FFALSE, FTRUE, FUNO, FUEQ, FUNE, FUGT, FUGE, FULT, FULE, FORD, FOEQ, FONE, FOGT, FOGE, FOLT, FOLE, T must be a floating point type or a vector of a floating point type.

If T is a vector type, the comparison is done element-wise.

All floating point operations follow the IEEE 754 standard. Floating point exceptions do not cause exceptional control flow in Mu.

Comparison operations return 1 if the condition of the comparison is true, or 0 otherwise. The conditions are:

EQ

For integers, op1 is equal to op2.
For pointers, operands are converted to integers and then compare for EQ.
For general reference types, op1 refers to the same object/memory location/function/stack/thread as op2.
- For iref, if any of op1 and op2 refer to a memory location whose lifetime has expired, the result is unspecified.
  
  NOTE: The reason is that Mu does not prevent dangling internal references referring to alloca cells on the stack. Two different alloca cells (likely generated by two consecutive calls of the same function) may have the same address, but are considered different memory locations in Mu. This also means that it is dangerous to leak an internal references to alloca cells out of the scope of a function invocation.

NE

The opposite of EQ.

SGE

Interpret both operands as signed values and op1 is greater than or equal to op2.

SGT

Interpret both operands as signed values and op1 is greater than op2.

SLE

Interpret both operands as signed values and op1 is less than or equal to op2.

SLT

Interpret both operands as signed values and op1 is less than op2.

UGE

For integers and pointers, interpret both operands as unsigned integral values and op1 is greater than or equal to op2.
For internal references, if both operands refer to elements in the same memory array, the result is true if and only if the referent of op1 is after the referent of op2 or both op1 and op2 refer to the same element; otherwise the result is unspecified.

UGT

For integers and pointers, interpret both operands as unsigned integral values and op1 is greater than op2.
For internal references, if both operands refer to elements in the same memory array, the result is true if and only if the referent of op1 is after the referent of op2; otherwise the result is unspecified.

ULE

For integers and pointers, interpret both operands as unsigned integral values and op1 is less than or equal to op2.
For internal references, if both operands refer to elements in the same memory array, the result is true if and only if the referent of op1 is before the referent of op2 or both op1 and op2 refer to the same element; otherwise the result is unspecified.

ULT

For integers and pointers, interpret both operands as unsigned integral values and op1 is less than op2.
For internal references, if both operands refer to elements in the same memory array, the result is true if and only if the referent of op1 is before the referent of op2; otherwise the result is unspecified.

NOTE: Memory arrays includes arrays, vectors and the variable part of hybrids in the Mu memory.

FFALSE

Always false.

FTRUE

Always true.

FUNO

Either operand is NaN.

FUEQ

Either operand is NaN or op1 is equal to op2.

FUNE

Either operand is NaN or op1 is not equal to op2.

FUGT

Either operand is NaN or op1 is greater than op2.

FUGE

Either operand is NaN or op1 is greater than or equal to op2.

FULT

Either operand is NaN or op1 is less than op2.

FULE

Either operand is NaN or op1 is less than or equal to op2.

FORD

Both operands are not NaN.

FOEQ

Both operands are not NaN and op1 is equal to op2.

FONE

Both operands are not NaN and op1 is not equal to op2.

FOGT

Both operands are not NaN and op1 is greater than op2.

FOGE

Both operands are not NaN and op1 is greater than or equal to op2.

FOLT

Both operands are not NaN and op1 is less than op2.

FOLE

Both operands are not NaN and op1 is less than or equal to op2.

NOTE: All floating point numbers of the same type are comparable, including NaN. When comparing, there can only be four results: equal, less than, greater than and unordered. Unordered is returned whenever either of the operands is NaN. Those floating point comparisons can be summarised by the following table, where a predicate is true if and only if the comparison gets one of the listed results.

Comparison unordered less than greater than equal negation

FFALSE FTRUE

FOEQ EQ FUNE

FOGT GT FULE

FOGE GT EQ FULT

FOLT LT FUGE

FOLE LT EQ FUGT

FONE LT GT FUEQ

FORD LT GT EQ FUNO

FUNO unordered FORD

FUEQ unordered EQ FONE

FUGT unordered GT FOLE

FUGE unordered GT EQ FOLT

FULT unordered LT FOGE

FULE unordered LT EQ FOGT

FUNE unordered LT GT FOEQ

FTRUE unordered LT GT EQ FFALSE

For LLVM users: this is directly borrowed from LLVM.

Example:

.const @a <@i32> = 42
.const @b <@i32> = 43
.const @w <@double> = 42.0d
.const @x <@double> = 43.0d

%c = GT <@i32> @a @b    // 0 (false)
%d = LT <@i32> @a @b    // 1 (true)

%y = FOGT <@double> @w @x   // 0 (false)
%z = FULT <@double> @w @x   // 1 (true)

%u = FOGT <@double> @w @D_NAN   // 0 (false) (result is "unordered")
%v = FUGT <@double> @w @D_NAN   // 1 (true)  (result is "unordered")

%e = NEW <@i64>
%f = EQ <@refi64> %e %e     // 1 (true) (same object)

%g = ALLOCA <@i64>
%h = EQ <@irefi64> %g %g    // 1 (true) (same location)

.typedef @i64array <@i64 10>
.const @I64_3 <@i64> = 3
.const @I64_5 <@i64> = 5
%ar  = ALLOCA <@i64array>
%ar3 = GETELEMIREF <@i64array @i64> %ar @I64_3
%ar5 = GETELEMIREF <@i64array @i64> %ar @I64_5
%i = ULT <@irefi64> %ar3 %ar5   // 1 (true)  (%a3 is before %a5 in the array)
%j = ULT <@irefi64> %ar3 %ar3   // 0 (false) (%a3 is not before itself)
%k = ULE <@irefi64> %ar3 %ar3   // 1 (true)  (%a3 is equal to itself)

Conversion

convOp < T1 T2 > opnd

convOp: The conversion operation.
T1, T2: type: The source type and the destination type, respectively.
opnd: value of type T1: The operand.
result:: Type T2: The result of the conversion.

opct	idt	idt	idt
opcode	T1	T2	op

convOp is one in the following table.

convOp	opcode	T1	T2
TRUNC	0x30	int	int
ZEXT	0x31	int	int
SEXT	0x32	int	int
FPTRUNC	0x33	FP	FP
FPEXT	0x34	FP	FP
FPTOUI	0x35	FP	int
FPTOSI	0x36	FP	int
UITOFP	0x37	int	FP
SITOFP	0x38	int	FP
BITCAST	0x39	(see below)	(see below)
REFCAST	0x3A	(see below)	(see below)
PTRCAST	0x3B	(see below)	(see below)

TODO: Move the opcode to the IR Builder API.

In all conversions, the operand opnd must have type T1. All conversions convert opnd to type T2.

T1 and T2 can be either scalar types as shown below or vector types of the types shown below as its elements. In the case of vector types, T1 and T2 must have the same length and the conversion is done element-wise.

For TRUNC, ZEXT and SEXT, Both T1 and T2 must be integer types.
- For TRUNC, the length of T2 must be less than the length of T1.
- For ZEXT and SEXT, the length of T2 must be greater than the length of T1.
For FPTRUNC and FPEXT, Both T1 and T2 must be floating point types.
- For FPTRUNC, the length of T2 must be less than the length of T1.
- For FPEXT, the length of T2 must be greater than the length of T1.
For FPTOUI and FPTOSI, T1 must be a floating point type and T2 must be an integer type.
For UITOFP and SITOFP, T1 must be an integer type and T2 must be a floating point type.
For BITCAST, T1 and T2 must be one of the following combinations:
- T1 is an integer type and T2 is a floating point type of the same number of bits.
- T1 is a floating point type and T2 is an integer type of the same number of bits.
For REFCAST, T1 and T2 must be one of the following combinations:
- Both T1 and T2 are ref.
- Both T1 and T2 are iref.
- Both T1 and T2 are funcref.
For PTRCAST, T1 and T2 must be two of the three cases:
- uptr<T> for some T.
- ufuncptr<sig> for some sig.
- int<n> for some n.

Semantics:

TRUNC

Truncate the high order bits of opnd, keeping only the lowest n bits of opnd where n is the length of T2.

ZEXT

Fill zero bits to opnd until it reaches the length of T2.

SEXT

Copy the highest order bit of opnd until it reaches the length of T2.

FPTRUNC

Convert opnd to a smaller floating point type, rounding to nearest and round ties to even according to IEEE754.

FPEXT

Convert opnd to a larger floating point type. Always exact.

FPTOUI

Convert opnd to an unsigned integer, rounding towards zero. NaN is converted to 0. If the value of opnd is greater than or less than the maximum or minimum representable value of the result type, the result shall be the maximum or minimum representable value of that type.

FPTOSI

Convert opnd to a signed integer, rounding towards zero. NaN is converted to 0. If the value of opnd is greater than or less than the maximum or minimum representable value of the result type, the result shall be the maximum or minimum representable value of that type.

UITOFP

Interpret opnd as unsigned and convert opnd to a floating point type, rounding to nearest and round ties to even according to IEEE754.

SITOFP

Interpret opnd as signed and convert opnd to a floating point type, rounding to nearest and round ties to even according to IEEE754.

BITCAST

The result has the same bit-wise representation as opnd.

REFCAST

When converting between ref, the result refers to the same object as opnd, but may have a different referent type.
When converting between iref, the result refers to a memory location with the same beginning as opnd.
When converting between funcref, the result refers to the same function as opnd, but may treat the function as having a different signature.
In all cases, if the operand is NULL, the result is the NULL value of the result type.

PTRCAST

Cast between integers and pointer types, preserving the address. If the length of the result is less than opnd, only the lowest bits are kept. If the length of the result is greater than opnd, it is zero-extended.

For LLVM users: These instructions are borrowed from LLVM. Mu currently lacks the conversion between raw pointer types and numerical types and they will be added when raw pointers are introduce. REFCAST is Mu-specific. Mu cannot use bitcast to cast between reference types.

Example:

.const @a  <@i32> = 42
.const @a2 <@i32> = -42
%b  = TRUNC  <@i32 @i16> @a         // is a @i16
%c  = ZEXT   <@i32 @i64> @a         // is a @i64
%c2 = SEXT   <@i32 @i64> @a2        // is a @i64
%d  = UITOFP <@i32 @double> @a      // is a @double
%d2 = SITOFP <@i32 @double> @a2     // is a @double

.const @x  <@double> = 42.0d
%y = FPTRUNC    <@double @float>  @x    // is a @float
%z = FPEXT      <@float  @double> %y    // is a @double
%w = FPTOSI     <@double @i64>    @x    // is a @i64

.typedef @Foo = ...
.typedef @Bar = ...
.typedef @refFoo = ref<@Foo>
.typedef @refBar = ref<@Bar>
.typedef @irefFoo = iref<@Foo>
.typedef @irefBar = iref<@Bar>

%f = NEW <@Foo>                     // is a ref<@Foo>
%g = REFCAST <@refFoo @refBar> %f   // is a ref<@Bar>

%h = ALLOCA <@Foo>                  // is a iref<@Foo>
%i = REFCAST <@irefFoo @irefBar> %h // is a iref<@Bar>

.typedef @ii8  = iref<@i8>          // iref<int<8>>
.typedef @iii8 = iref<@ii8>         // iref<iref<int<8>>>

.funcsig @vv = () -> ()
.funcsig @main_sig = (@i32 @iii8) -> (@i32)
.funcdecl @j <@main_sig>
%k = REFCAST <@main_sig @vv> @j     // is a funcref<@vv>

`SELECT` Instruction

SELECT < S T > cond ifTrue ifFalse

S: type: The type of cond.
T: type: The type of ifTrue, ifFalse and the result.
cond: variable of type S: The condition.
ifTrue, ifFalse: variable of T: The candidates of the result.
result:: Type T: A value according to cond.

S can be either int<1> or a vector type of int<1>. When S is a vector type of int<1>, T must also be a vector type of the same length as S.

cond must have type S. Both ifTrue and ifFalse must have the same type as T. The result of this instruction has type T.

When S is int<1>, then the result is ifTrue if cond is 1, or ifFalse if cond is 0.

When S is a vector of int<1>, the corresponding element of the result is the corresponding element of ifTrue if the corresponding element of cond is 1, or the corresponding element of ifFalse otherwise.

For LLVM users: This instruction is directly borrowed from LLVM's select instruction.

Example:

.const @a <@i64> = 42
.const @I64_2 <@i64> = 2
.const @I64_100 <@i64> = 100
.const @I64_200 <@i64> = 200

%a_mod_2    = SREM <@64> @a @I64_2
%a_is_even  = EQ <@64> %a_mod_2 @I64_0
%b = SELECT <@i1 @i64> %a_is_even @I64_100 @I64_200     // %b is 100 if %a is even
                                                        // 200 otherwise

Intra-function Control Flow

NOTE: The following instructions are for jumping within a function.

`BRANCH` Instruction

BRANCH dest

dest: destination clause: The destination of jumping.

This instruction branches to dest.

For LLVM users: This is the same as the one-branch br instruction. Mu uses the goto-with-values form.

Example:
%entry():
    BRANCH %head(%a)

%head(<@T> %a):
    // Continue executing here.

`BRANCH2` Instruction

BRANCH2 cond ifTrue ifFalse

cond: variable of type int<1>: The condition
ifTrue, ifFalse: destination clause: The destinations to jump to when cond is 1 or 0, respectively

If cond is 1, jump to ifTrue, otherwise jump to ifFalse.

For LLVM users: This is the same as the two-branch br instruction. Mu uses the goto-with-values form.

Example:

.const @a <@i64> = ...

%entry():
    %b = EQ <@i64> @a @I64_1
    BRANCH2 %b %equal() %notequal()

%equal():
    // if %b is 1, jump here

%notequal():
    // if %b is 0, jump here

`SWITCH` Instruction

SWITCH < T > opnd default { ( value dest ) _rep }

T: type: The type of opnd and all value
opnd: variable of T: The value to compare against.
default:: destination clause: The default destination, i.e. the destination if no case matches.
value:: constant value of T: The case value for a branch.
dest:: destination clause: The destination for the corresponding case.

There are zero or more value-dest pairs.

opnd and all value must have type T. default and all dest must be basic blocks.

T must be an EQ-comparable type.

All value must be constants and must have distinct values.

If the value of opnd equals one of the value, then jump to the corresponding dest. If no such value equals opnd, then jump to default.

For LLVM users: This is the same as the switch instruction.

Example:

.const @a <@i64> = ...
.const @ONE <@i64> = 1
.const @TWO <@i64> = 2
.const @THREE <@i64> = 3

%entry():
    SWITCH <@i64> @a %defbranch() {
        @ONE %one()
        @TWO %two()
        @THREE %three()
        }

%defbranch():
    ...

%one():
    ...

%two():
    ...

%three():
    ...

Inter-function Control Flow

`CALL` and `TAILCALL` Instruction

CALL < sig > callee argList excClause keepAliveClause

TAILCALL < sig > callee argList

sig

function signature: The signature of the callee.

callee

variable of type funcref<sig>: The callee.

argList

argument list: Argument list.

excClause

exception clause: Specifies the basic block to handle Mu exceptions and stack overflow.

keepAliveClause

keep-alive clause: For on-stack replacement.

results:

CALL produce as many results as the number of return values of the callee. The type of each return value matches the corresponding return type.
TAILCALL does not produce results.

The CALL instruction creates a new stack frame for the callee, passes the arguments in argList and starts executing from the entry block of the callee.

The CALL instruction sets the state of the frame of the caller to READY<Ts> where Ts is the return types of the callee. The callee frame's state is ACTIVE.

A CALL instruction continues normally when the callee returns. In this case the results of the CALL instruction are the return values of the callee.

A CALL instruction continues exceptionally when an exception is thrown from the callee. In this case the value of the CALL instruction is not defined. When the exception clause is present, the exception is received by the exceptional parameter in the exceptional destination. When the exception clause is absent, the exception is re-thrown out of the function activation which the CALL instruction is in.

A CALL instruction continues exceptionally when the function call causes a stack overflow. In this case the value of the CALL instruction is not defined. When the exception clause is present, the value of the exceptional parameter in the exceptional destination is NULL. When the exception clause is absent, it has undefined behaviour.

TODO: There could be a standard error system where "serious" errors can be represented as pre-defined heap objects.

Whenever CALL continues exceptionally, the CALL instruction does not produce results.

NOTE: This is to say, the following program is illegal:

%bb1():
    %rv = CALL <...> @foo (...) EXC(%nor() %exc(%rv)) // ERROR: %rv cannot be used in the exceptional destination

%exc(<@T> %rv) [%exc]:
    ...

The CALL instruction is an OSR point.

When a stack is rebound and the top frame is pausing on a CALL instruction, it continues normally with the results being the values received, or continues exceptionally, catching the exception received.

NOTE: This can be the result of OSR: Upper frames are popped and the current CALL instruction receives values provided by the client, or by other means of stack binding. See Threads and Stacks.

The TAILCALL instruction replaces the caller's stack frame with a new stack frame for the callee. If the frame below the current frame has state READY<Ts>, the callee must have return type Ts. The caller of the current function becomes the caller of the function TAILCALL calls. The TAILCALL instruction cannot have any exception clause and is not an OSR point. After TAILCALL, the new frame is in the ACTIVE state.

NOTE: TAILCALL is semantically similar to calling a function and immediately return the returned value, but replaces the current frame. OSR will not see the old frame.

NOTE: TAILCALL is not the same as branching to a basic block, even the goto-with-values form makes them look similar. BRANCH cannot branch to the entry block. TAILCALL is also subject to function redefinition: it may ends up tail-calling a newer version of the callee, even if the callee is the current function. (The instruction can't explicitly specify which version to call.)

Calling an undefined function is allowed. Such functions will trigger a trap when executed so that the client can handle it. See Mu IR for the behaviour of undefined functions.

For LLVM users:

Like any instructions with the exception clause, CALL instruction is conditionally a terminator. When the exception clause is present, it is like the invoke instruction in LLVM and, when absent, it is like the call instruction.

Mu functions may return multiple values.

Mu uses the goto-with-values form.

The meaning of TAILCALL is similar to LLVM's musttail: in Mu, a TAILCALL always replaces the current stack frame.

Calling conventions cannot be specified in Mu: Mu always uses its internal calling conventions. The CCALL instruction is for native calls.

Arguments will not be automatically zero or sign-extended or truncated for the programmer. Conversions must be explicitly done before calling.

The funcref type in Mu is a dedicated function reference, not a pointer. See CCALL which calls a native function.

All parameters are passed by value and parameters are SSA Values. To pass on-stack data or arrays, use alloca and pass iref.

The keep-alive clause is similar to the experimental intrinsic function @llvm.experimental.stackmap and @llvm.experimental.patchpoint in LLVM.

Example:

.funcsig @sig = (@double @double) -> (@double)

.funcdecl @sum <@sig>

.funcdef @square_sum VERSION %v1 <@sig> {
    %entry(<@double> %x <@double> %y):
        %x2 = MUL <@double> %x %x
        %y2 = MUL <@double> %y %y

        // return the result of sum(x2,y2)
        TAILCALL <@sig> @sum (%x2 %y2)
}

.funcsig @vv = () -> ()

.const @D_3 <@double> = 3.0d
.const @D_4 <@double> = 4.0d
.const @D_5 <@double> = 5.0d
.const @D_6 <@double> = 6.0d

.funcdef @main VERSION %v1 <@vv> {
    %entry():
        %a = CALL <@sig> @square_sum (@D_3 @D_4)
        %b = CALL <@sig> @square_sum (%a   @D_5) EXC(%nor(%a %b) %exc())

    %nor(<@double> %a <@double> %b):
        %c = [%important_call_site] CALL <@sig> @square_sum (@D_5 @D_6) KEEPALIVE(%a %b)
        %d = CALL <@sig> @square_sum (%c   %c)   EXC(%nor2(%c %d) %exc()) KEEPALIVE(%a %c)

    %nor2(<@double> %c <@double> %d):
        // continue here

    %exc() [%the_exc]:
        // handle the exception
}

`RET` Instruction

RET ( rv _rep )

RET rv

rv _rep: The return value of the current function. The number and the types must match the return types of the current function.

The RET instruction returns from the current function with a list of rv as the return values of the current function. The types of rv values must match the return types of the current function.

From the stack's point of view, the RET instruction removes the current frame, and resumes the previous frame into the ACTIVE state.

RET rv is a syntax sugar of RET (rv). In order to return from a function with zero return values, use RET ().

The RET instruction itself does not produce results. The return values are returned to the caller.

For LLVM users: Equivalent to LLVM's ret and ret void.

Example:

.funcsig @sig1 = (@double @double) -> (@double)
.funcsig @sig2 = () -> ()
.funcsig @sig3 = (@i64 @i64) -> (@i64 @i64)

.funcdef @sum VERSION %v1 <@sig1> {
    %entry(<@double> %x <@double> %y):
        %s = ADD <@double> %x %y
        RET %s
}

.funcdef @main VERSION %v1 <@sig2> {
    %entry():
        RET ()
}

.funcdef @swap VERSION %v1 <@sig3> {
    %entry(<@i64> %x <@i64> %y):
        RET (%y %x)
}

`THROW` Instruction

THROW exc

exc: variable of type ref to any type: The exception object.

The THROW instruction throws the exception exc from the current function to its caller frame. Exceptions in Mu are object references to any type.

For LLVM users: There is no equivalent in LLVM. The resume instruction in LLVM continues the propagation of a in-flight exception. This can also be done by Mu's THROW instruction. Mu programs can create a new exception object by NEW and throw it, where LLVM must depend on platform-specific libraries to allocate new exceptions.

Example:

.funcsig @sig = (@i64 @i64) -> (@i64)
.typedef @SomeExceptionType = ...    // user-defined exception type

.funcdef @safe_divide VERSION %v1 <@sig> {
    %entry(<@double> %x <@double> %y):
        %y0 = EQ <@i64> %y @I64_0
        BRANCH %y0 %divbyzero() %okay(%x %y)

    %divbyzero():
        %exc = NEW <@SomeExceptionType>
        // initialise %exc
        THROW %exc

    %okay(<@double> %x <@double> %y):
        %rv = SDIV <@i64> %x %y
        RET %rv
}

Aggregate Type Operations

These instructions operate on the struct, the array and the vector types as SSA variables.

Struct Operations

`EXTRACTVALUE` Instruction

EXTRACTVALUE < T index > opnd

T: type, must be a struct: The type of the operand.
index: integer literal The index of the field to extract.
opnd: variable of type T: The struct to extract value from.
result:: Type is the index-th field of the struct type T: The value of the index-th field of opnd.

The EXTRACTVALUE instruction extracts the index-th field from the value of an SSA variable opnd which has type struct.

For LLVM users: It is the counterpart of the extractvalue instruction in LLVM. But Mu's EXTRACTVALUE does not work on arrays or nested struct. Use EXTRACTVALUE multiple times to extract the field in nested structs.

Example: see the example of INSERTVALUE

`INSERTVALUE` Instruction

INSERTVALUE < T index > opnd newVal

T: type, must be a struct: The type of the operand.
index: integer literal The index of the field to insert.
opnd: variable of type T: The struct to insert value into.
newVal: variable of the type of the index-th field of T: The new value for the field specified by index.
result:: Type is T: A new struct with the index-th field being newVal.

The INSERTVALUE instruction constructs a struct value which has the same field values as opnd except the field specified by index which has the value newVal.

For LLVM users: It is the counterpart of the insertvalue instruction in LLVM. But Mu's INSERTVALUE does not work on arrays or nested struct. Use a combination of EXTRACTVALUE and INSERTVALUE to replace a field in a nested struct.

Example:

.typedef @Foo = struct <@i32 @double @float>
.const @A <@i32>    = 42
.const @B <@double> = 84.0d
.const @C <@float>  = 3.14f

.const @B2 <@double>  = 126.0d

.const @S <@Foo>    = {@A @B @C}    // {42 84.0d 3.14f}

%a  = EXTRACTVALUE <@Foo 1> @S      // %a  == 84.0d and is a double
%s2 = INSERTVALUE  <@Foo 1> @S @B2  // %s2 == {42 126.0d 3.14f} and is a @Foo

.typedef @Baz = struct <@double @double>
.typedef @Bar = struct <@double @Baz @double>

.const @D <@double> = 1.0d
.const @E <@double> = 2.1d
.const @F <@double> = 2.2d
.const @G <@double> = 3.0d

.const @H <@double> = 999.0d

.const @U <@Baz> = {@E @F}          // {2.1d 2.2d}
.const @T <@Bar> = {@D @U @G}       // {1.0d {2.1d 2.2d} 3.0d}

%b = EXTRACTVALUE <@Bar 1> @T       // %b == {2.1d 2.2d} and is a @Baz
%c = EXTRACTVALUE <@Baz 0> %b       // %c == 2.1d and is a double

%b2 = INSERTVALUE <@Baz 0> %b @H    // %b2 == {999.0d 2.2d} and is a @Baz
%t2 = INSERTVALUE <@Bar 1> @T %c    // %t2 == {1.0d {999.9d 2.2d} 3.0d} and is a @Bar

Array and Vector Operations

`EXTRACTELEMENT` Instruction

EXTRACTELEMENT < T1 T2 > opnd index

T1: type, must be an array or vector type: The type of opnd
T2: type, must be an int type: The type of index.
opnd: variable of type T1: The array or vector to extract from.
index: variable of type T2: The index of the element to extract.
result:: Type is the element type of T1: The extracted element.

The EXTRACTELEMENT instruction extracts the element at index from an array or vector value opnd of vector type T1.

The index may have any integer type and is treated as unsigned. If index exceeds the length of the array or vector, it has undefined behaviour.

For LLVM users: This is the counterpart of the extractelement instruction of LLVM.

Example: See the example in SHUFFLEVECTOR.

`INSERTELEMENT` Instruction

INSERTELEMENT < T1 T2 > opnd index newVal

T1: type, must be an array or vector type: The type of opnd.
T2: type, must be an int type: The type of index.
opnd: variable of type T1: The array or vector to insert into.
index: variable of type T2: The index of the element to insert.
newVal: variable of the element type of T1: The new value for that element.
result:: Type is T1: A new array or vector with the index-th element being newVal.

The INSERTELEMENT instruction creates a new array or vector value which has the same element values as opnd except the element at index which has the value of newVal.

The index may have any integer type and is treated as unsigned. If index exceeds the length of the array or vector, it has undefined behaviour.

For LLVM users: This is the counterpart of the insertelement instruction of LLVM.

Example: See the example in SHUFFLEVECTOR.

`SHUFFLEVECTOR` Instruction

SHUFFLEVECTOR < T1 T2 > vec1 vec2 mask

T1: type, must be a vector: The type of vec1 and vec2.
T2: type, must be a vector of any int type: The type of mask.
vec1, vec2: variables of type T1: The two vectors to select values from.
mask: variable of type T2: The mask that determines the elements to select from vec1 and vec2.
result:: Type is a vector type of the element type of T1 and the size of T2: The new vector with elements selected from T1 and T2 according to mask.

The SHUFFLEVECTOR instruction constructs a permutation of elements from two vectors vec1 and vec2. The result is a vector with the same element type as T1 and the same length as T2.

The elements of vec1 and vec2 are numbered from left to right. Specifically, the i-th element in vec1 is numbered i and the j-th element in vec2 is numbered n+j where n is the length of T1. Then the element in the result vector is the element of the correspondent number in the mask vector. Specifically, the k-th element of the result vector is the element numbered l where l equals the value of the k-th element of mask.

The element type of mask can be any integer type and is treated as unsigned. If any element in mask is not within the range between 0 and 2*n-1, inclusively, where n is the length of T1, then it has undefined behaviour.

For LLVM users: This is the counterpart of the shufflevector instruction in LLVM.

Example:

.const @S0 <@float> = 3.1f
.const @S1 <@float> = 4.1f
.const @S2 <@float> = 5.9f
.const @S3 <@float> = 2.6f
.const @S4 <@float> = 5.3f
.const @S5 <@float> = 5.8f
.const @S6 <@float> = 9.7f
.const @S7 <@float> = 9.3f

.const @V0 <@4xfloat> = { @S0 @S1 @S2 @S3 }     // { 3.1f 4.1f 5.9f 2.6f }
.const @V1 <@4xfloat> = { @S4 @S5 @S6 @S7 }     // { 5.3f 5.8f 9.7f 9.3f }

.const @I32_2 <@i32> = 2
.const @I32_3 <@i32> = 3
.const @I32_4 <@i32> = 4
.const @I32_5 <@i32> = 5
.const @I32_6 <@i32> = 6
.const @I32_7 <@i32> = 7

.const @M0 <@4xi32> = { @I32_1 @I32_0 @I32_2 @I32_1 }

.typedef @8xi32     = vector <@i32 8>
.typedef @8xfloat   = vector <@float 8>

.const @M1 <@8xi32> = { @I32_7 @I32_5 @I32_6 @I32_4 @I32_2 @I32_1 @I32_3 @I32_0 }

%a = EXTRACTELEMENT <@4xfloat @i64> @V0 @I64_2      // 5.9f
%b = INSERTELEMENT  <@4xfloat @i64> @V0 @I64_3 @S7  // { 3.1f 4.1f 5.9f 9.3f }
%c1 = SHUFFLEVECTOR <@4xfloat @4xi32> @V0 @V1 @M0   // { 4.1f 3.1f 5.9f 4.1f }
%c2 = SHUFFLEVECTOR <@4xfloat @8xi32> @V0 @V1 @M1   // { 9.3f 5.8f 9.7f 5.3f 5.9f 4.1f 2.6f 3.1f }

Memory Operations

Memory allocation

This family of instructions allocate memory on the heap or the stack.

NEW < T1 > excClause
NEWHYBRID < T1 T2 > length excClause
ALLOCA < T1 > excClause
ALLOCAHYBRID < T1 T2 > length excClause

T1

type: The type to allocate.

For NEW and ALLOCA: T must not be hybrid.
For NEWHYBRID and ALLOCAHYBRID: T must be hybrid.

T2

type, must be int: The type of length.

excClause

exception clause: Specifies the basic block to handle allocation failure.

result:

For NEW and NEWHYBRID: Type is ref<T>: An object reference to the newly allocated object.
For ALLOCA and ALLOCAHYBRID: Type is iref<T>: An internal reference to the newly allocated stack cell.

The NEW instruction allocates an object of a fixed-length type T on the heap. Return an object reference to it.

The NEWHYBRID instruction allocates an object of the hybrid type T1 type on the heap. Return an object reference to it.

The ALLOCA instruction allocates a stack cell of a fixed-length type T on the stack. Return an internal reference to it.

The ALLOCAHYBRID instruction allocates a stack cell of a hybrid type T1 on the stack. Return an internal reference to it.

For NEWHYBRID and ALLOCAHYBRID, length is the length of the variable part of the hybrid. T2 can be any integer type and is treated as unsigned.

If the allocation failed, this instruction continues exceptionally.

For LLVM users: LLVM does not have instructions for heap allocation. malloc is the unmanaged counterpart.

ALLOCA is similar to LLVM's alloca with a fixed-length type. ALLOCAHYBRID is similar to alloca with a number of elements. A hybrid in Mu may have a fixed prefix. This is similar to C99 flexible array member like struct Something { ...; char suffix[];};.

Example:

.typedef @Foo = struct <@i64 @float @double>
.typedef @Bar = hybrid <@Foo @i8>

.const @I64_42 <@i64> = 42

%n1 = NEW <@i64>                        // ref<@i64>
%n2 = NEW <@Foo>                        // ref<@Foo>
%nh = NEWHYBRID <@Bar @i64> @I64_42     // ref<@Bar>

%a1 = ALLOCA <@i64>                     // iref<@i64>
%a2 = ALLOCA <@Foo>                     // iref<@Foo>
%ah = ALLOCAHYBRID <@Bar @i64> @I64_42  // iref<@Bar>

Memory Addressing

This family of instructions manipulates references/pointers, but does not actually read or write memory.

`GETIREF` Instruction

GETIREF < T > opnd

T: type: The referent type of opnd.
opnd: variable of type ref<T>: The object reference to derive internal reference.
result:: Type is iref<T>: An internal reference of the memory location of type T at the beginning of the memory location of object opnd.

NOTE: The cryptic description of the return value means the referent type T may be a prefix (see Mu and the Memory) of the actual type represented in the object. In this case, this instruction only provides access to the prefix part.

The GETIREF instruction converts the object reference opnd to an internal reference. The resulting internal reference refers to the memory location of the heap object opnd.

For LLVM users: There is no equivalent instructions in LLVM.

Example:

%a = NEW <@i32>
%b = GETIREF <@i32> %a

Other Memory Addressing Instructions

GETFIELDIREF PTR _opt < T1 index > opnd
GETELEMIREF PTR _opt < T1 T2 > opnd index
SHIFTIREF PTR _opt < T1 T2 > opnd offset
GETVARPARTIREF PTR _opt < T1 > opnd

PTR _opt

If present, the types of opnd and the result are pointers. Otherwise they are internal references.

T1

type: The referent type of opnd.

For GETFIELDIREF, T1 must be struct or hybrid.
For GETELEMIREF, T1 must be array.
For GETVARPARTIREF, T1 must be hybrid.

T2

type, must be int: The type of index (for GETELEMIREF) and offset (for SHIFTIREF).

index

For GETFIELDIREF: integer literal: The index of the field.
For GETELEMIREF: variable of type T2: The index of the element.

offset

variable of type T2: The offset to move the opnd.

opnd

variable of type iref<T> or uptr<T>: The reference/pointer to derive reference from.

result

Type is iref<U> or uptr<U>: The derived reference/pointer.

For GETFIELDIREF, U is the type of the index-th field of struct T1 or the fixed part of hybrid T1.
For GETELEMIREF, U is the element type of T1.
For SHIFTIREF, U is the same as T1.
For GETVARPARTIREF, U is the type of the elements of the variable part of T1.

The GETFIELDIREF instruction gets an internal reference/pointer to the index-th field of the struct or the fixed part of the hybrid referenced by opnd.

The GETELEMIREF instruction gets an internal reference/pointer to the index-th element of the array referenced by opnd.

The SHIFTIREF instruction assumes the opnd already refers to an element of a memory array (including arrays, vectors and the variable part of hybrids, see Mu and the Memory). It moves opnd internal reference/pointer forward by offset elements. If offset is negative, it moves the reference/pointer backwards by the absolute value of offset.

For GETELEMIREF and SHIFTIREF, T2 can be any integer type and is treated as signed. When working with internal references, if the resulting memory location is outside the range of the array, it has undefined behaviour.

The GETVARPARTIREF instruction gets an internal reference/pointer to the first (0-th) element in the variable part of the hybrid referenced by opnd. When working with internal references, if the variable part of opnd has zero elements, the GETVARPARTIREF has undefined behaviour.

For LLVM users: This family of instructions are essentially a decomposed version of the getelementptr instruction.

Example:

.typedef @Foo = struct <@i64 @float @double>

%foo_r = NEW <@Foo>                     // ref<@Foo>
%foo_i = GETIREF <@Foo> %foo_r          // iref<@Foo>
%foo_1 = GETFIELDIREF <@Foo 1>          // iref<@float>

.typedef @Bar = array <@i32 10>
.const @I64_5       <@i64> = 5
.const @I64_NEG_2   <@i64> = -2

%bar_r = NEW <@Bar>                                 // ref<@Bar>
%bar_i = GETIREF <@Bar> %bar_r                      // iref<@Bar>
%bar_5 = GETELEMIREF <@Bar @i64> %bar_i @I64_5      // iref<@i32> the 5th element
%bar_6 = SHIFTIREF   <@Bar @i64> %bar_5 @I64_1      // iref<@i32> the 6th element
%bar_4 = SHIFTIREF   <@Bar @i64> %bar_6 @I64_NEG_2  // iref<@i32> the 4th element

.typedef @Baz = hybrid <@Foo @i8>

.const @I64_42 <@i64> = 42

%baz_i = ALLOCAHYBRID   <@Baz @i64> @I64_42         // iref<@Baz>
%baz_f = GETFIELDIREF   <@Baz 0>    %baz_i          // iref<@Foo>
%baz_v = GETVARPARTIREF <@Baz>      %baz_i          // iref<@i8> the 0th element
%baz_v5 = SHIFTIREF <@i8 @i64> %baz_i @I64_5        // iref<@i8> the 5th element

.typedef @BigHybrid = hybrid <@i32 @i64 @double @i8>    // 3 fields in the fixed part.

%bh_i = ALLOCAHYBRID <@BigHybrid @i64> @I64_42      // iref<@BigHybrid>
%bh_0 = GETFIELDIREF <@BigHybrid 0> %bh_i           // iref<@i32>
%bh_1 = GETFIELDIREF <@BigHybrid 1> %bh_i           // iref<@i64>
%bh_2 = GETFIELDIREF <@BigHybrid 2> %bh_i           // iref<@double>
%bh_v = GETVARPARTIREF <@BigHybrid> %bh_i           // iref<@i8> the 0th element
%bh_v2 = SHIFTIREF <@i8 @i64> %bh_v @I64_2          // iref<@i8> the 1st element

Example 2:

.typedef @Foo = struct <@i64 @float @double>

%foo_r = NEW <@Foo>                                 // ref<@Foo>
%foo_p = COMMINST @uvm.native.pin <@Foo> (%foo_r)   // uptr<@Foo>
%foo_1 = GETFIELDIREF PTR <@Foo 1>                  // uptr<@float>

COMMINST @uvm.native.unpin <@Foo> (%foo_r)

// @foo_p and @foo_1 should not be used from now on.

Memory Accessing

This family of instructions actually load from or store into the memory.

The LOAD, STORE, CMPXCHG and ATOMICRMW instructions have optional exceptional clauses. When the memory location argument loc is a NULL reference, the instruction will continue exceptionally.

Memory Order

A memory order is one in the following table. Their semantics are described in memory-model.rest. Different instructions have different requirements for their memory orders. See memory-model.rest.

Keyword	Binary	Semantic
NOT_ATOMIC	0x00	not atomic
RELAXED	0x01	relaxed
CONSUME	0x02	consume
ACQUIRE	0x03	acquire
RELEASE	0x04	release
ACQ_REL	0x05	acquire+release
SEQ_CST	0x06	sequentially consistent

TODO: Move the binary codes to the IR Builder API.

`LOAD` Instruction

LOAD PTR _opt ord _opt < T > loc excClause

PTR _opt: If present, loc is a pointer. Otherwise it is an internal reference.
ord _opt: memory order: The memory order. Default: NOT_ATOMIC
T: type: The referent type of loc.
loc: variable of type iref<T> or uptr<T>: The memory location/address to load from.
excClause: exception clause: Used to handle NULL reference errors.
result: Type is the strong variant of T: The result of the load operation.

The LOAD instruction performs a load operation with argument (ord, T, loc) as defined in Mu and the Memory.

In the text form, ord can be omitted and defaults to NOT_ATOMIC.

For LLVM users: This is the counterpart of the load instruction. volatile is absent in Mu because memory accesses are part of the behaviours.

Example:

.typedef @Foo = struct<@i64 @double @float>
%r  = NEW <@Foo>                         // ref<@Foo>
%i  = GETIREF <@Foo> %r                  // iref<@Foo>
%i1 = GETFIELDIREF <@Foo 1> %i           // iref<double>
%d  = LOAD <@double> %i1                 // double

// Note: all allocations initialise the memory to zero.

`STORE` Instruction

STORE PTR _opt ord _opt < T > loc newVal excClause

PTR _opt: If present, loc is a pointer. Otherwise it is an internal reference.
ord _opt: memory order: The memory order. Default: NOT_ATOMIC
T: type: The referent type of loc.
loc: variable of type iref<T> or uptr<T>: The memory location/address to store into.
excClause: exception clause: Used to handle NULL reference errors.
newVal: Type is the strong variant of T: The new value to store.

The STORE instruction performs a store operation with argument (ord, T, loc, newVal) as defined in Mu and the Memory.

In the text form, ord can be omitted and defaults to NOT_ATOMIC.

For LLVM users: This is the counterpart of the store instruction. volatile is absent.

Example:

.const @D_PI <@double> = 3.14159d

.typedef @Foo = struct<@i64 @double @float>
%r  = NEW <@Foo>                         // ref<@Foo>
%i  = GETIREF <@Foo> %r                  // iref<@Foo>
%i1 = GETFIELDIREF <@Foo 1> %i           // iref<double>
STORE <@double> %i1 @D_PI

`CMPXCHG` Instruction

CMPXCHG PTR _opt WEAK _opt ordSucc ordFail < T > loc expected desired excClause

PTR _opt

If present, loc is a pointer. Otherwise it is an internal reference.

WEAK _opt

If present, the CMPXCHG operation is weak.

ordSucc, ordFail

memory order: The memory order for success and failure, respectively.

T

type, must be EQ-comparable: The referent type of loc.

loc

variable of iref<T> or uptr<T>: The memory location/address to access.

expected

variable of the strong variant of T: The expected value in the memory.

desired

variable of the strong variant of T: The new value to store into the memory.

excClause

exception clause: Used to handle NULL reference errors.

results:

The underlying compare exchange operation produces a pair (v, s). The CMPXCHG instruction produces two results:

Type is U where U is the strong variant of T: The value v.
Type is int<1>: The result s. 1 for success and 0 for failure.

The CMPXCHG instruction performs a compare exchange operation with argument (isWeak, ordSucc, ordFail, T, loc, expected, desired), where isWeak is true if WEAK is present, otherwise false. The operation is defined in Mu and the Memory.

This instruction produces two results which represent the v and s value as defined in Mu and the Memory. The second result is 1 for true and 0 for false.

For LLVM users: This is the counterpart of the cmpxchg instruction.

Example:

.global @foo <@i64>
.typedef @ResultType = struct<@i64 @i1>

%orig           = LOAD <@i64> @foo                 // @i64
%squared        = MUL <@i64> %orig %orig           // @i64
(%old %succ)    = CMPXCHG ACQ_REL RELAXED <@i64> @foo %orig %squared   // struct<@i64 @i1>
BRANCH2 %succ %cont() %failed()

Example 2: This function tries to atomically update the content of @foo to its square by repeatedly doing CMPXCHG, and returns the old value just before the actual atomic update:

.global @foo <@i64>
.typedef @ResultType = struct<@i64 @i1>

.funcsig @atomic_square.sig = () -> (@i64)
.funcdef @atomic_square VERSION %v1 <@atomic_square.sig> {
    %entry():
        %old     = LOAD <@i64> @foo             // @i64
        BRANCH %loop(%old)

    %loop(<@i64> %old):
        %squared        = MUL <@i64> %old %old         // @i64
        (%old2 %succ)   = CMPXCHG WEAK ACQ_REL RELAXED <@i64> @foo %old %squared  // <@i64 @i1>
        BRANCH2 %succ %done(%old2) %loop(%old2)

    %done(<@i64> %old):
        RET %old
}

`ATOMICRMW` Instruction

ATOMICRMW PTR _opt ord op < T > loc opnd excClause

PTR _opt: If present, loc is a pointer. Otherwise it is an internal reference.
ord: memory order: The memory order.
op: AtomicRMW operator: The operator.
T: type: The referent type of loc.
loc: variable of iref<T> or uptr<T>: The memory location/address to access.
opnd: variable of the strong variant of T: The right-hand-side of the operation.
excClause: exception clause: Used to handle NULL reference errors.
result:: Type is the strong variant of T: The result of the atomic-x operation where x is op.

An AtomicRMW operator is one of the following:

Keyword	Binary	T	Semantic
XCHG	0x00	any	exchange
ADD	0x01	int	add
SUB	0x02	int	subtract
AND	0x03	int	bitwise and
NAND	0x04	int	bitwise nand
OR	0x05	int	bitwise or
XOR	0x06	int	bitwise xor
MAX	0x07	int	signed max
MIN	0x08	int	signed min
UMAX	0x09	int	unsigned max
UMIN	0x0A	int	unsigned min

TODO: Move the binary code to the IR Builder API.

The ATOMICRMW instruction performs an atomic-x operation with argument (ord, T, loc, opnd), where the x in atomic-x is op. The operation is defined in Mu and the Memory.

For LLVM users: This is the counterpart of the atomicrmw instruction. volatile is absent.

Example:

.global @foo <@i64>

%old = ATOMICRMW SEQ_CST ADD <@i64> @foo 42

Fence

FENCE ord

ord: memory order: The memory order.

The FENCE is a fence of memory order ord. Its semantics is specified in memory-model.rest.

For LLVM users: This is the counterpart of the fence instruction.

Example:

FENCE ACQUIRE
FENCE RELEASE
FENCE ACQ_REL
FENCE SEQ_CST

Traps and Watchpoints

`TRAP` and `WATCHPOINT` Instruction

TRAP < Ts > excClause keepAliveClause

WATCHPOINT wpid < Ts > dis ena ( WPEXC ( exc ) ) _opt keepAliveClause

wpid: integer literal: Watchpoint identifier.
Ts: list of types: The types of the return values.
excClause: exception clause: For TRAP, specify the basic block to handle exception.
keepAliveClause: keep-alive clause: For on-stack replacement.
dis: destination clause: For WATCHPOINT, the normal destination before the watchpoint is enabled.
ena: destination clause: For WATCHPOINT, the normal destination after the watchpoint is enabled.
exc: Optional destination clause: For WATCHPOINT, the exceptional destination after the watchpoint is enabled. This can be omitted.
results: When the stack is rebound passing values, the results are those values passed. There are as many results as the types Ts, matching each type.

TRAP and WATCHPOINTS are designed to let the trap handler registered by the client handle occasions which the Mu micro VM cannot handle by itself.

A TRAP instruction is always enabled. A WATCHPOINT can be enabled or disabled by its watch point ID wpid. A disabled WATCHPOINT does not produce any results and unconditionally branches to the destination dis.

The API provides functions to enable or disable watchpoints.

A TRAP or an enabled WATCHPOINT temporarily unbinds the current thread from the current stack, leaving the current frame in the READY< Ts > state, and transfers the control to a trap handler in the Mu client. When the current stack is bound again, this instruction may continue normally with results of types Ts, and may continue exceptionally with a Mu exception.

When rebinding to a stack stopping at an enabled TRAP or WATCHPOINT instruction, if rebinding (normally) with values, the results of the TRAP or WATCHPOINT instruction are the values passed to the current stack, and the instruction continues normally. Specifically, WATCHPOINT branches to the ena destination.

When rebinding with an exception, the TRAP or WATCHPOINT continues exceptionally. Specifically, WATCHPOINT branches to the exc destination where the exception is received by the exception parameter. When the exception clause of TRAP or the exc destination of WATCHPOINT is absent, the exception is thrown out of the current frame.

If a WATCHPOINT is enabled when it is executed, but is disabled before the current stack is rebound, the current WATCHPOINT instruction continues as if it is enabled.

NOTE: This means a particular evaluation of a WATCHPOINT determines its "enabled-ness" as soon as the instruction starts. The client may disable the very same watchpoint in the trap handler, but it does not make it branch to the dis destination.

Consider the following example:
[%wp] WATCHPOINT 42 <> %dis() %ena() %exc()
If the client disabled watch point 42 when handling this watchpoint and rebinds the current stack (see Threads and Stacks for stack/thread rebinding), then it will branch to %ena. The %wp instruction will branch to %dis if and only if watch point 42 is disabled when it is executed.

It is recommended to name the instruction so that the trap handler can identify each individual traps (using the syntax %rv = [%trap_name] TRAP <@T> ...).

TRAP and WATCHPOINT are OSR points.

NOTE: They are deliberately designed as OSR points. Its designed to interact with the client, and OSR is one of the main purposes.

For LLVM users: LLVM has the llvm.trap intrinsic function, but its semantics is not defined. LLVM itself does not have on-stack replacement support, but Lameed and Hendren proposed a framework for supporting on-stack replacement in LLVM.

Example 1:

%bb1():
    %rv1 = [%trap1] TRAP <@i64> EXC(%bb2() %bb3()) KEEPALIVE(%a %b %c ...)

%bb2():
    // %trap1 normally continues here

%bb3() [%exc]
    // %trap1 handles exception here

%bb4():
    %rv2 = [%wp1] WATCHPINT 1 <@i64> %bb5() %bb6() WPEXC(%bb7()) KEEPALIVE(%a %b %c ...)

%bb5():
    // %wp1 normally continues here when disabled

%bb6():
    // %wp1 normally continues here when enabled

%bb7() [%exc]:
    // %wp1 handles exception here when enabled

Example 2: Use TRAP to let the client do anything, for instance, obtain the version number of Mu:
.funcdef @some_func VERSION %v1 <...> {
    %entry(...):
        %version_num = [%the_trap] TRAP <@i64>

        CALL <...> @print (%version_num)
        ...
}
The hypothetical client identifies this concrete TRAP instruction by its ID or its global name @some_func_v1.the_trap. Then it can help this particular instruction by returning normally, supplying its version number.

Example 3: use loop back-edge counting and an unconditional TRAP to handle frequently-executed loops:

.const @LOOP_THRESHOLD <@i64> = 1000
.global @loop_count_for_some_loop <@i64>

%loop_head(...):
    ...
    BRANCH2 %loop_cond %loop_body(...) %loop_exit(...)

%loop_body(...):
    ...
    %old_count      = LOAD <@i64> @loop_count_for_some_loop
    %new_count      = ADD <@i64> %old_count @I64_1
                      STORE <@i64> @loop_count_for_some_loop %new_count
    %is_frequent    = SGE <@i64> %new_count @LOOP_THRESHOLD
    BRANCH2 %is_frequent %to_trap(...) %loop_head(...)

%to_trap(...):
    [%trap12345] TRAP <> KEEPALIVE(%some %local %variables)
    ...

%loop_exit(...):

Example 4: use WATCHPOINT for de-optimising speculatively generated code. This code demonstrates a virtual table lookup:
.const @SomeVFuncOffset <@i64> = 9

%bb1(...):
    %obj    = ...
    %vtable = CALL <...> @get_virtual_table (%obj)
    %vt_ent = CALL <...> @get_virtual_table_entry (%vtable @SomeVFuncOffset)
    %func   = LOAD <@SomeVFuncType> %vt_ent

    %rv     = CALL <...> %func (%obj ...)

    ...
But if the client knows that the class has no subclass, it can speculatively use static call rather than virtual call:
%bb1(...):
    %obj    = ...

    [%wp1234] WATCHPOINT 5678 <> %bb1_cont(%obj) %bb2() KEEPALIVE(%obj)

%bb1_cont(<@ref_T> %obj):
    %rv     = CALL <...> @TheActualFunction (%obj ...)

    ...

%bb2():
    THROW @NULLREF  // unreachable because the client should have
                    // replaced the frame and not let the %wp1234
                    // continue at all.
Then when the client loaded a new class which extends the class of %obj and overrides the virtual function, then the speculatively generated code is no longer valid. Then the client can enable the watchpoint 5678 and the %wp1234 instruction will go to the client.

`WPBRANCH` instruction

WPBRANCH wpid dis ena

wpid: integer literal: Watchpoint identifier.
dis, ena: destination clause: The destinations to jump to when wpid is disabled or enabled.

WPBRANCH:

The WPBRANCH instruction is a binary branching instruction. The destination is determined by whether the watchpoint ID wpid is enabled or disabled. It can be enabled or disabled in the same way as WATCHPOINT.

Unlike WATCHPOINT, this instruction does not trap to the client, and is not an OSR point.

Example:

%entry():
    WPBRANCH 42 %cont() %oops()

%cont():
    // continue normally here

%oops():
    // Oops! Something happened!

Unsafe Native Call

`CCALL` Instruction

CCALL callConv < T sig > callee argList excClause keepAliveClause

callConv: flag: The calling convention.
T: type: The type of callee.
sig: function signature: The signature of the callee.
callee: variable of type T: The callee.
argList: argument list: Arguments to the callee.
excClause: exception clause: Specify the basic block to handle exception.
keepAliveClause: keep-alive clause: For on-stack replacement.
results: The return values of the callee. There are as many results as the return types in sig, matching each return type.

calling convention is one in the following table or others defined by the platform-specific part of the Mu native interface:

Flag	Binary
#DEFAULT	0x00

TODO: Move the binary flag into the IR Builder API.

The CCALL instruction calls a native function.

NOTE: The name CCALL indicates that it is intended to call C functions.

callConv specifies the calling convention used by this instruction.

The callee must have type T. The allowed type of T, and the number of return values, are implementation-dependent and calling convention-dependent.

See native-interface.rest for a detailed description of the native interface.

The return values of CCALL are the return values of the native callee.

CCALL may have an exception clause. How CCALL receives exceptions from the native callee is implementation-defined.

When executing the CCALL instruction, the current frame enters the READY<Rs> state, where Rs are the return types of the callee. It creates a native frame which is in the ACTIVE state. Upon running from the native function, the current frame enters the ACTIVE state again.

CCALL is an OSR point.

If a stack is rebound and the top frame stops on a CCALL instruction (because of OSR), the result values of CCALL are the values passed normally, or it receives the exception provided by the rebinding process.

For LLVM users: Mu is not designed to be compatible with C and functions defined in Mu IR does not use the native C ABI. This instruction is necessary to communicate with other parts of the system, especially operating systems since most operating systems are currently written in C and provide C interfaces.

For Java users: The CCALL instruction is not like JNI. JNI is a thick layer between the JVM and the native world, but the CCALL intends to introduce minimal overhead. However, JEP191 proposed a similar approach as C#'s unsafe native function calls and it may be similar to Mu's CCALL instruction.

For JikesRVM users: This instruction is similar to the "syscall" mechanism where the overhead is minimum and great freedom is provided to the user, but the Mu VM provides no protection of abusing. This is the preferred way to call native functions.

Example: This example uses the C function write to print "Hello world!\n":

// The client loads libc and gets the address for write.
// Then the client defines a constant which hard-codes the address.
.typedef @AddrType = int<64>
.const @write_address <@AddrType> = 0x0011223344556600   // hard-coded address

// A compatible signature must be provided to call this native function.
// Note: write's signature in C is:
// ssize_t write(int fildes, const void *buf, size_t nbytes);
// Assume x86_64 architecture.
.typedef @c_ssize_t = int<64>
.typedef @c_int     = int<32>
.typedef @c_void    = void
.typedef @c_ptrvoid = uptr<@c_void>
.typedef @c_size_t  = int<64>
.funcsig @write_sig = (@c_int @c_ptrvoid @c_size_t) -> (@c_ssize_t)
.typedef @write_ptr = ufuncptr<@write_sig>

// Define necessary constants and types
.const @FD = 1      // 1 is for stdout

.typedef @DynByteArray = hybrid<@i8>        // No fixed part. Just a @i8 array of unknown length.
.typedef @irefi8 = iref<@i8>
.typedef @ptri8  = uptr<@i8>
.const @ARY_SZ <@i64> = 13
.const @CHAR_H  <@i8> = 0x48    // 'H'
.const @CHAR_e  <@i8> = 0x65    // 'e'
.const @CHAR_l  <@i8> = 0x6c    // 'l'
.const @CHAR_o  <@i8> = 0x6f    // 'o'
.const @CHAR_SP <@i8> = 0x20    // ' '
.const @CHAR_w  <@i8> = 0x77    // 'w'
.const @CHAR_r  <@i8> = 0x72    // 'r'
.const @CHAR_d  <@i8> = 0x64    // 'd'
.const @CHAR_EX <@i8> = 0x21    // '!'
.const @CHAR_NL <@i8> = 0x0a    // '\n'

// A Mu program allocates an array (represented as a hybrid)
%h  = NEWHYBRID <@DynByteArray @i64> @ARY_SZ
%hi = GETIREF <@DynByteArray> %h
%v  = GETVARPARTIREF <@DynByteArray> %hi

// Then fill %v with string "Hello world\n\0"
STORE <@i8> %v @CHAR_H          // store 'H'
%v1 = SHIFTIREF <@i8 @i64> %v %I64_1
STORE <@i8> %v1 @CHAR_e         // store 'e'
...
%v12 = SHIFTIREF <@i8 @i64> %v11 %I64_1
STORE <@i8> %v12 @CHAR_NL       // store '\n'

// Before calling the C function, we need to pin the object
%bufptr = COMMINST @uvm.native.pin <@irefi8> %v     // pins the underlying object of %v. %bufptr is a uptr<@i8>
%bufptr_pv = PTRCAST <@ptri8 @c_ptrvoid> %bufptr    // cast to the correct type

// Cast the function to a ufuncptr type
%callee = PTRCAST <@AddrType @write_ptr> @write_address

// Then use the CCALL instruction to call the write function.
%bytes_written = CCALL #DEFAULT <@write_ptr @write_sig> @callee (@FD %bufptr_pv @ARY_SZ)

// Unpin the object after calling to C so that the garbage collector
// can move the object again.
COMMINST @uvm.native.unpin <@irefi8> %v

Thread and Stack

See Thread and Stack for more information of stack creation and the swap-stack operation.

NOTE: New stacks can be created by the @uvm.new_stack common instruction or the new_stack API function.

Common Structures

newStackClause ::= PASS_VALUES < Ts > ( vals )
newStackClause ::= THROW_EXC exc

Ts: list of types: The type of vals.
vals: list of variables matching the types of Ts: The values to pass to the target stack.
exc: variable of type ref: The exception object to raise to the target stack.

The new stack clause determines how to bind a thread to the target stack. It is used by both NEWTHREAD and SWAPSTACK, since both binds a thread (new or existing) to a given stack.

PASS_VALUES will pass values vals which has types Ts to the target stack.
THROW_EXC will raise the exception exc to the target stack.

`NEWTHREAD` Instruction

NEWTHREAD stack threadLocalClause _opt newStackClause excClause

threadLocalClause ::= THREADLOCAL ( threadLocal )
newStackClause ::= PASS_VALUES < Ts2 > ( vals )
newStackClause ::= THROW_EXC exc

stack: variable of stackref: The stack to bind the new thread to.
threadLocal: variable of ref<T> for any T: The initial thread-local object reference of the created thread. If omitted, it defaults to NULL.
newStackClause: new stack clause: Determines how to bind to the stack.
excClause: exception clause: To handle thread creation errors.
result:: Type is threadref: The newly created thread.

The NEWTHREAD instruction creates a new thread which immediately binds to stack, passing values or raising exceptions to it according to the newStackClause.

The threadLocalClause determines the initial thread-local object reference of the newly created thread. If it is omitted, the thread-local object reference will be NULL.

This instruction continues exceptionally if Mu cannot create the new thread. The exception parameter receives NULL.

Example:

%stack  = COMMINST @uvm.new_stack <[@sig]> @func
%thread = NEWTHREAD %stack PASS_VALUES <@T1 @T2> (%a1 %a2)

Rare case: Create a thread to unwind a stack:

%stack  = ...
%thread = NEWTHREAD %stack THROW_EXC %some_exception

Create a new thread with a thread-local objref:

.typedef @my_threadlocal_t = struct<...>  // an arbitrary type

%stack  = COMMINST @uvm.new_stack <[@sig]> @func
%tlobj  = NEW <@my_threadlocal_t>
%thread = NEWTHREAD %stack THREADLOCAL(%tlobj)
                PASS_VALUES <...> (...)

`SWAPSTACK` Instruction

SWAPSTACK swappee curStackClause newStackClause excClause keepAliveClause

curStackClause ::= RET_WITH < Ts >
curStackClause ::= KILL_OLD

newStackClause: See above.

swappee: variable of type stackref: The stack to swap to.
curStackClause: current stack clause: Action to the current stack.
Ts: list of types: The result types of this instruction if this stack is bound to a thread again.
newStackClause: new stack clause: Action to the swappee stack.
excClause: exception clause: To handle exceptions thrown to this stack.
keepAliveClause: keep-alive clause: For on-stack replacement.

The SWAPSTACK instruction unbinds the current thread with the current stack and rebinds it to another stack swappee.

In the curStackClause:

If the curStackClause is RET_WITH, then the current frame will enter the READY<Ts> state. Ts1 can be an empty list, in which case it does not expect values.
If the curStackClause is KILL_OLD, then the current stack is killed.

According to the newStackClause, values or an exception can be passed to the swappee stack.

See Thread and Stack for more details about the SWAP-STACK operation.

When a stack is rebound and the top frame pauses on a SWAPSTACK instruction it continues normally with the return value being the value received, or continues exceptionally, catching the exception received.

The SWAPSTACK instruction is an OSR point.

For LLVM users: There is no native facilities provided by the official LLVM, but Dolan, Muralidharan and Gregg proposed an extension to LLVM to support the SWAPSTACK operation. The SWAPSTACK interface of Mu is inspired by their works.

Example: The following example demonstrates a coroutine that yields 1, 2 and 3 and then raise an exception in the main coroutine to terminate the iteration:

.funcsig @sig1 = (@sref) -> ()
.const @I64_2 <@i64> = 2
.const @I64_3 <@i64> = 3

.typedef @StopIterationException = ...

// This coroutine (a generator) yields 1, 2 and 3 sequentially and stop.
// param %from: the stack of the main coroutine, i.e. the "caller" stack
.funcdef @one_two_three VERSION %v1 <@sig1> {
    %entry(<@sref> %from):
        // Return to the main stack after receiving the initial
        // parameter %from. So the main stack can use a loop.
        SWAPSTACK %from RET_WITH <> PASS_VALUES <> ()

        SWAPSTACK %from RET_WITH <> PASS_VALUES <@i64> (@I64_1)
        SWAPSTACK %from RET_WITH <> PASS_VALUES <@i64> (@I64_2)
        SWAPSTACK %from RET_WITH <> PASS_VALUES <@i64> (@I64_3)

        %exc = NEW <@StopIterationException>
        SWAPSTACK %from KILL_OLD THROW_EXC %exc
}

.funcsig @main_sig = () -> ()

.funcdef @main VERSION %v1 <@main_sig> {
    %entry():
        // Get the reference to the current stack
        %cur_stack = COMMINST @uvm.current_stack

        // Create a new stack
        %coro = COMMINST @uvm.new_stack <[@sig1]> (@one_two_three)

        // Initialise its parameters
        SWAPSTACK %coro RET_WITH <> PASS_VALUES <@sref> (%cur_stack)

        // Enter the loop
        BRANCH %head

    %head(<@sref> %coro):
        // Go to the coroutine
        %cur_num = SWAPSTACK %coro RET_WITH <@i64> PASS_VALUES <> () EXC(
                   %body(%coro %cur_num)
                   %exit()
                   )

    %body(<@sref> %coro <@i64> %cur_num):
        // Do something with %cur_num
        CALL <...> @print_num (%cur_num)

        // Get the next number
        BRANCH %head(%coro)

    %exit() [%exc]:     // %exc receives the StopIterationException
        COMMINST @thread_exit
}

Common Instructions

`COMMINST` Instruction

COMMINST inst flagList _opt typeList _opt funcSigList _opt argList _opt excClause keepAliveClause

inst: global name: The name of the common instruction.
flagList _opt: Optional flag list: A list of flags. Can be omitted.
typeList _opt: Optional type list: A list of type arguments. Can be omitted.
funcSigList _opt: Optional function signature list: A list of function signature arguments. Can be omitted.
argList _opt: Optional argument list: A list of value arguments. Can be omitted.
excClause: exception clause: To provide an alternative control flow destination.
keepAliveClause: keep-alive clause: For on-stack replacement.
results:: Determined by the respective common instructions.

The COMMINST instruction calls a common instruction identified by inst in the text form. A list of flags flagList, a list of type arguments typeList, a list of function signature arguments funcSigList, a list of value arguments argList, an optional exception clause excClause and a possibly empty keep-alive clause keepAliveClause are provided for the common instruction. The return value of this instruction is decided by the specific common instruction. The semantics is defined by the specific common instruction.

The flagList, typeList, funcSigList and argList are considered empty when omitted in the text form.

A COMMINST instruction must supply as many type arguments and value arguments as the specific common instruction requires. A COMMINST instruction must not have an exception clause unless the common instruction can continue exceptionally. A COMMINST instruction must have an empty keep-alive clause unless the common instruction is an OSR point.

See common-insts.rest for a complete list of common instructions.

For LLVM users: Common instructions in Mu is the counterpart of intrinsic functions of the LLVM. Common instructions are just like other Mu instructions except they have the same instruction format and can be extended without changing the Mu IR grammar. They are not functions and are not called by the CALL instructions which calls Mu functions.

Example:

.const @F_2 <@float> = 2.0f
.const @D_2 <@double> = 2.0d
.const @MAX_SINT <@i32> = 0x7fffffff

// extra math functions (planned, to be extended)
%v1 = COMMINST @uvm.math.sin  <@float>  (@F_1)
%v2 = COMMINST @uvm.math.cos  <@float>  (@F_2)
%v3 = COMMINST @uvm.math.tan  <@double> (@D_1)
%v4 = COMMINST @uvm.math.sqrt <@double> (@D_2)
%v5 = COMMINST @uvm.math.add_ovf <@i32> (@MAX_SINT @I32_1) EXC(%bb1() %bb2())

%bb1():
    ...

%bb2():
    // Handle signed integer overflow here.

// extra stack/thread operations
%s = COMMINST @uvm.new_stack <[@sig]> (@func)
%t = NEWTHREAD %s THROW_EXC %some_exc

// the proper thread exit
COMMINST @uvm.thread_exit       // no type args or value args

Files

instruction-set.rest

Latest commit

History

instruction-set.rest

File metadata and controls

Instruction Set

Overview

Conventions

SSA Variables

Common Structures

Lists

Destination Clause

Exception Clause

Keep-alive Clause

Flag and Flag List

Basic Operations

Binary Operations

Comparison

Conversion

SELECT Instruction

Intra-function Control Flow

BRANCH Instruction

BRANCH2 Instruction

SWITCH Instruction

Inter-function Control Flow

CALL and TAILCALL Instruction

RET Instruction

THROW Instruction

Aggregate Type Operations

Struct Operations

EXTRACTVALUE Instruction

INSERTVALUE Instruction

Array and Vector Operations

EXTRACTELEMENT Instruction

INSERTELEMENT Instruction

SHUFFLEVECTOR Instruction

Memory Operations

Memory allocation

Memory Addressing

GETIREF Instruction

Other Memory Addressing Instructions

Memory Accessing

Memory Order

LOAD Instruction

STORE Instruction

CMPXCHG Instruction

ATOMICRMW Instruction

Fence

Traps and Watchpoints

TRAP and WATCHPOINT Instruction

WPBRANCH instruction

Unsafe Native Call

CCALL Instruction

Thread and Stack

Common Structures

NEWTHREAD Instruction

SWAPSTACK Instruction

Common Instructions

COMMINST Instruction

`SELECT` Instruction

`BRANCH` Instruction

`BRANCH2` Instruction

`SWITCH` Instruction

`CALL` and `TAILCALL` Instruction

`RET` Instruction

`THROW` Instruction

`EXTRACTVALUE` Instruction

`INSERTVALUE` Instruction

`EXTRACTELEMENT` Instruction

`INSERTELEMENT` Instruction

`SHUFFLEVECTOR` Instruction

`GETIREF` Instruction

`LOAD` Instruction

`STORE` Instruction

`CMPXCHG` Instruction

`ATOMICRMW` Instruction

`TRAP` and `WATCHPOINT` Instruction

`WPBRANCH` instruction

`CCALL` Instruction

`NEWTHREAD` Instruction

`SWAPSTACK` Instruction

`COMMINST` Instruction