instruction-set.rst 96.1 KB
Newer Older
1 2 3 4
===============
Instruction Set
===============

Kunshan Wang's avatar
Kunshan Wang committed
5 6
Overview
========
7

8
Mu uses a variant of static single assignment (SSA) form and a comprehensive but
Kunshan Wang's avatar
Kunshan Wang committed
9
low-level instruction set.
10

Kunshan Wang's avatar
Kunshan Wang committed
11 12 13
Conventions
===========

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

Kunshan Wang's avatar
Kunshan Wang committed
18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
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>
Kunshan Wang's avatar
Kunshan Wang committed
34 35
    .typedef @sref    = stackref
    .typedef @tref    = threadref
Kunshan Wang's avatar
Kunshan Wang committed
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
    .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

Kunshan Wang's avatar
Kunshan Wang committed
53 54
    .const @NULLREF <@refvoid> = NULL

Kunshan Wang's avatar
Kunshan Wang committed
55 56
SSA Variables
=============
57

58 59 60 61
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.
62

Kunshan Wang's avatar
Kunshan Wang committed
63
An **SSA variable**, or **variable** when unambiguous, holds a data value of a
64 65
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.
66

Kunshan Wang's avatar
Kunshan Wang committed
67 68 69 70
    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
Kunshan Wang's avatar
Kunshan Wang committed
71 72 73
    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.
Kunshan Wang's avatar
Kunshan Wang committed
74

Kunshan Wang's avatar
Kunshan Wang committed
75 76 77
..

    For LLVM users: The concept of *SSA variable* or *variable* is the
Kunshan Wang's avatar
Kunshan Wang committed
78 79
    counterpart of the concept of *SSA value* or *value* in LLVM. Mu uses the
    traditional terminology that "a variable holds a value". 
Kunshan Wang's avatar
Kunshan Wang committed
80

Kunshan Wang's avatar
Kunshan Wang committed
81
* SSA variable
82

Kunshan Wang's avatar
Kunshan Wang committed
83
  * Global SSA variable
84

Kunshan Wang's avatar
Kunshan Wang committed
85 86
    * Constant
    * Global cell reference
87 88
    * Function reference
    * Exposed function
89

Kunshan Wang's avatar
Kunshan Wang committed
90
  * Local SSA variable
91

Kunshan Wang's avatar
Kunshan Wang committed
92
    * Parameter
93
    * Instruction result
Kunshan Wang's avatar
Kunshan Wang committed
94

Kunshan Wang's avatar
Kunshan Wang committed
95
A **global SSA variable** is valid in the whole Mu instance after it is defined.
96
Their values never change.
Kunshan Wang's avatar
Kunshan Wang committed
97

98
- A **constant** is a global SSA variable. Its value is the constant value.
Kunshan Wang's avatar
Kunshan Wang committed
99

100 101 102
- 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.)
Kunshan Wang's avatar
Kunshan Wang committed
103

104 105 106
- 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.)
Kunshan Wang's avatar
Kunshan Wang committed
107

108 109 110 111
- 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.
112

113 114
A **local SSA variable** is valid in the same basic block of the same function
activation (frame) it is in.
Kunshan Wang's avatar
Kunshan Wang committed
115

116 117
- A **parameter** is a local SSA variable whose value is the value passed to the
  basic block as an argument.
Kunshan Wang's avatar
Kunshan Wang committed
118

119 120 121
- 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).
Kunshan Wang's avatar
Kunshan Wang committed
122 123 124 125

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

Kunshan Wang's avatar
Kunshan Wang committed
126
    NOTE: This allows a Mu implementation to store constants in the machine
Kunshan Wang's avatar
Kunshan Wang committed
127 128 129 130
    instruction flow as immediate values, or save the result of some
    instructions in registers and also spilling some other registers to the
    stack.

131 132
A local variable can be **live** or **dead**.

133 134
- A parameter is live when the current instruction of the frame is in the basic
  block.
135

136 137 138 139
- 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.
140 141

Otherwise it is dead.
Kunshan Wang's avatar
Kunshan Wang committed
142

143 144
    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
145
    in "a live stack contains all live local variables". This definition may
146 147
    not be necessary.

148
The execution of an instruction is called **an evaluation**. An evaluation
149
determines its results, and this process is called **value computation**.
150
Accessing the memory (see `Memory Model <memory.rst>`__) or changing the
151 152
state of the execution environment is called **side effect**. An evaluation may
have side effects.
Kunshan Wang's avatar
Kunshan Wang committed
153

Kunshan Wang's avatar
Kunshan Wang committed
154 155 156
Common Structures
=================

157
The following grammar structures are common to several instructions.
Kunshan Wang's avatar
Kunshan Wang committed
158

159 160 161 162 163 164 165 166
Lists
-----

+ *typeList* ::= ``<`` *type* :sub:`rep` ``>``

+ *funcSigList* ::= ``<[`` *funcSig* :sub:`rep` ``]>``

+ *argList* ::= ``(`` *var* :sub:`rep` ``)``
167

168 169
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.
170

171
A **type list** is a list of types.
172

173 174 175 176 177
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.
178

179 180
An **argument list** is a list of SSA variables.

181 182
    Example::

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

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

187 188 189
        CALL     <@sig> @func (%arg0 %arg1 %arg2)
        TAILCALL <@sig> @func (%arg0 %arg1 %arg2)
        CCALL    #DEFAULT <@func_ty @sig> @func (%arg0 %arg1 %arg2)
190
        NEWTHREAD %stack PASS_VALUES <@T1 @T2 @T3> (%arg0 %arg1 %arg2)
191 192 193 194 195 196 197 198 199 200 201 202 203
        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,
204 205 206 207 208
either normal or exceptional. The destination must be in the same function
version as the instruction that includes the destination clause.

A destination clause takes many arguments, which will be received by the normal
parameters of the ``dest`` basic block.  The arguments must match the number and
209 210 211 212 213
the types of the normal parameters. The exceptional parameter does not need to
be explicitly passed to.

Only terminator instructions may have destination clauses.

Kunshan Wang's avatar
Kunshan Wang committed
214 215 216
Exception Clause
----------------

Kunshan Wang's avatar
Kunshan Wang committed
217
*excClause* ::= *(* ``EXC`` ``(`` *nor* *exc* ``)`` *)* :sub:`opt`
Kunshan Wang's avatar
Kunshan Wang committed
218

219
nor
220
    *destination clause*: The normal destination
221
exc
222
    *destination clause*: The exceptional destination
Kunshan Wang's avatar
Kunshan Wang committed
223

Kunshan Wang's avatar
Kunshan Wang committed
224
The exception clause provides two destinations for instructions that may have
225 226
diverging control flows. *nor* and *exc* are the **normal destination** and the
**exceptional destination**, respectively.
Kunshan Wang's avatar
Kunshan Wang committed
227

228
The exception clause can be omitted. Any instruction that may have exception
229
clauses is not a *terminator* (see `Mu IR <ir.rst>`__) if the exception
230
clause is omitted.  Otherwise it is a *terminator*.
Kunshan Wang's avatar
Kunshan Wang committed
231 232 233 234 235 236

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,
237

Kunshan Wang's avatar
Kunshan Wang committed
238 239 240
  - 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.
241

Kunshan Wang's avatar
Kunshan Wang committed
242
+ When continuing exceptionally,
243

Kunshan Wang's avatar
Kunshan Wang committed
244
  - if the exception clause is absent, it has undefined behaviour unless
245
    explicitly defined to be otherwise in some instructions;
Kunshan Wang's avatar
Kunshan Wang committed
246 247
  - if the exception clause is present, then branch to the exceptional
    destination.
Kunshan Wang's avatar
Kunshan Wang committed
248

Kunshan Wang's avatar
Kunshan Wang committed
249
..
Kunshan Wang's avatar
Kunshan Wang committed
250

Kunshan Wang's avatar
Kunshan Wang committed
251
    For example, the ``CALL`` instruction has an exception clause. When the
252 253
    exception clause is omitted, it does not have undefined behaviour. Instead
    the exception will be thrown out of the current function::
Kunshan Wang's avatar
Kunshan Wang committed
254

255 256 257 258 259 260 261
        %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]:
Kunshan Wang's avatar
Kunshan Wang committed
262 263
            ...

Kunshan Wang's avatar
Kunshan Wang committed
264 265 266 267 268
    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::

269 270 271 272
        %entry():
            %rv1 = SDIV <@i64> %some_val @I64_0                             // undefined behaviour
            %rv2 = SDIV <@i64> %some_val @I64_0 EXC(%cont() %exc_hdlr())    // handled locally
        %cont():
Kunshan Wang's avatar
Kunshan Wang committed
273
            ...
274
        %exc_hdlr():
Kunshan Wang's avatar
Kunshan Wang committed
275 276
            ... // handle divide-by-zero error here

Kunshan Wang's avatar
Kunshan Wang committed
277 278 279 280 281
Keep-alive Clause
-----------------

*keepAliveClause* ::= *(* ``KEEPALIVE`` ``(`` *lv* :sub:`rep` ``)`` *)* :sub:`opt`

282 283 284
lv :sub:`rep`
    *list of local SSA variable*: A sequence of local SSA variables. Those
    SSA variables are forced to be alive.
Kunshan Wang's avatar
Kunshan Wang committed
285

286 287 288 289
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.
Kunshan Wang's avatar
Kunshan Wang committed
290 291 292 293 294 295

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
296
zero local variables.
Kunshan Wang's avatar
Kunshan Wang committed
297 298

    Example: The ``TRAP`` instruction optionally has a keep-alive clause. The
Kunshan Wang's avatar
Kunshan Wang committed
299
    values of those variables in the clause are available for the client to
Kunshan Wang's avatar
Kunshan Wang committed
300 301 302 303 304 305
    introspect::

        %a = ADD ...
        %b = SUB ...
        %c = MUL ...
        %trap1 = TRAP <@ty>                     // Does not keep alive any variables
Kunshan Wang's avatar
Kunshan Wang committed
306
        %trap2 = TRAP <@ty> KEEPALIVE(%a %b)    // Keep %a and %b alive
Kunshan Wang's avatar
Kunshan Wang committed
307

308 309 310 311 312 313 314 315
Flag and Flag List
------------------

*flag* ::= ``#`` [``A-Z_``] :sub:`rep`

*flagList* ::= ``[`` *flag* :sub:`rep` ``]``

In the text form, a **flag** starts with a hash character ``#`` which is
316
followed by many capital letters ``[A-Z]`` or underscores ``_``.
317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339

    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.

340 341 342
Basic Operations
================

Kunshan Wang's avatar
Kunshan Wang committed
343
Binary Operations
344 345
-----------------

346
*binOp* ``<`` *T* ``>`` *op1* *op2* *excClause*
347

348 349 350 351 352 353
binOp
    The binary operation.
T
    *type*: The type of both operands.
op1, op2
    *variable* of type *T*: The two operands.
354
excClause
355
    *exception clause*: the destination for erroneous conditions.
356
result:
357
    Type *T*: return the result of the computation.
358

359
*binOp* is one in the following table:
360 361

========= ======== ===== ========================
362
 binOp     opcode   T     operation
363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383
========= ======== ===== ========================
 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           
========= ======== ===== ========================

384 385
    TODO: Move the opcode to the IR Builder API.

Kunshan Wang's avatar
Kunshan Wang committed
386
In all binary operations, the type of both *op1* and *op2* must have type *T*.
387

Kunshan Wang's avatar
Kunshan Wang committed
388
For ADD, SUB, MUL, SDIV, SREM, UDIV, UREM, SHL, LSHR, ASHR, AND, OR and XOR,
389
*T* must be ``int`` of a vector of ``int``.
390

391 392 393 394
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
Kunshan Wang's avatar
Kunshan Wang committed
395 396 397 398
elements of the two vectors.

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

For ADD, SUB and MUL, both operands are considered unsigned. When overflow,
Kunshan Wang's avatar
Kunshan Wang committed
401
returns the result modulo 2^n where n is the length of *T*.
402 403 404 405

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

Kunshan Wang's avatar
Kunshan Wang committed
406 407 408 409 410 411 412 413 414 415 416 417 418 419 420
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
Kunshan Wang's avatar
Kunshan Wang committed
421
in Mu.
422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439

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
Kunshan Wang's avatar
Kunshan Wang committed
440 441
    Return the value of *op1* shifted to the left by the value of some lowest
    bits of *op2*. 
442
LSHR
Kunshan Wang's avatar
Kunshan Wang committed
443 444 445
    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.
446
ASHR
Kunshan Wang's avatar
Kunshan Wang committed
447 448 449
    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*.
450
AND
Kunshan Wang's avatar
Kunshan Wang committed
451
    Return the result of bit-wise AND.
452
OR
Kunshan Wang's avatar
Kunshan Wang committed
453
    Return the result of bit-wise inclusive OR.
454
XOR
Kunshan Wang's avatar
Kunshan Wang committed
455
    Return the result of bit-wise exclusive OR.
Kunshan Wang's avatar
Kunshan Wang committed
456 457 458 459 460 461 462 463 464 465
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.
466 467 468 469

..

    For LLVM users: this is directly borrowed from LLVM. Exceptional cases,
Kunshan Wang's avatar
Kunshan Wang committed
470
    including division by zero and signed division overflow, have defined
Kunshan Wang's avatar
Kunshan Wang committed
471
    behaviours in Mu.
472 473 474 475 476

..

    Example::

Kunshan Wang's avatar
Kunshan Wang committed
477 478 479 480

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

        // in some function
483
        %entry():
Kunshan Wang's avatar
Kunshan Wang committed
484 485
            %b = ADD <@i32> @a @I32_1
            %c = SUB <@i32> @a %b
486

Kunshan Wang's avatar
Kunshan Wang committed
487 488
            %y = FADD <@double> @x @D_1
            %z = FSUB <@double> @x %y
489

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

493
        %cont():
Kunshan Wang's avatar
Kunshan Wang committed
494
            ...     // continue on normal condition
495

496
        %handler():
Kunshan Wang's avatar
Kunshan Wang committed
497
            ...     // handle divide-by-zero error here
498 499 500 501

Comparison
----------

502
*cmpOp* ``<`` *T* ``>`` *op1* *op2*
503

504 505 506 507 508 509
cmpOp
    The comparison operation.
T
    *type*: The type of both operands.
op1, op2
    *variable* of *T*: The two operands.
510 511 512 513 514 515
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.
516

517
*cmpOp* is one in the following table:
518

519
========= ======== =================== ==================================
520
 cmpOp     opcode   T                   Condition
521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548
========= ======== =================== ==================================
 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
========= ======== =================== ==================================
549

550 551
    TODO: Move the opcode to the IR Builder API.

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

554
For EQ and NE, *T* must be a EQ-comparable type (see `<type-system.rst>`__) or a
555 556 557 558 559 560 561 562 563 564 565
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.

Kunshan Wang's avatar
Kunshan Wang committed
566
All floating point operations follow the IEEE 754 standard.  Floating point
Kunshan Wang's avatar
Kunshan Wang committed
567
exceptions do not cause exceptional control flow in Mu.
568

Kunshan Wang's avatar
Kunshan Wang committed
569
Comparison operations return 1 if the condition of the comparison is true, or 0
570 571 572
otherwise. The conditions are:

EQ
573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588
    - 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.
Kunshan Wang's avatar
Kunshan Wang committed
589

590 591 592
NE
    The opposite of EQ.
SGE
Kunshan Wang's avatar
Kunshan Wang committed
593
    Interpret both operands as signed values and *op1* is greater than or equal
594 595
    to *op2*.
SGT
Kunshan Wang's avatar
Kunshan Wang committed
596
    Interpret both operands as signed values and *op1* is greater than *op2*.
597
SLE
Kunshan Wang's avatar
Kunshan Wang committed
598
    Interpret both operands as signed values and *op1* is less than or equal to
599 600
    *op2*.
SLT
Kunshan Wang's avatar
Kunshan Wang committed
601
    Interpret both operands as signed values and *op1* is less than *op2*.
602
UGE
603 604 605 606 607 608
    - 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.
609
UGT
610 611 612 613 614
    - 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.
615
ULE
616 617 618 619 620 621
    - 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.
622
ULT
623 624 625 626 627
    - 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.
628 629 630 631

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

632 633 634 635 636
FFALSE
    Always false.
FTRUE 
    Always true.
FUNO  
Kunshan Wang's avatar
Kunshan Wang committed
637
    Either operand is NaN.
638
FUEQ  
Kunshan Wang's avatar
Kunshan Wang committed
639
    Either operand is NaN or *op1* is equal to *op2*.
640
FUNE  
Kunshan Wang's avatar
Kunshan Wang committed
641
    Either operand is NaN or *op1* is not equal to *op2*.
642
FUGT  
Kunshan Wang's avatar
Kunshan Wang committed
643
    Either operand is NaN or *op1* is greater than *op2*.
644
FUGE  
Kunshan Wang's avatar
Kunshan Wang committed
645
    Either operand is NaN or *op1* is greater than or equal to *op2*.
646
FULT  
Kunshan Wang's avatar
Kunshan Wang committed
647
    Either operand is NaN or *op1* is less than *op2*.
648
FULE  
Kunshan Wang's avatar
Kunshan Wang committed
649
    Either operand is NaN or *op1* is less than or equal to *op2*.
650
FORD  
Kunshan Wang's avatar
Kunshan Wang committed
651
    Both operands are not NaN.
652
FOEQ  
Kunshan Wang's avatar
Kunshan Wang committed
653
    Both operands are not NaN and *op1* is equal to *op2*.
654
FONE  
Kunshan Wang's avatar
Kunshan Wang committed
655
    Both operands are not NaN and *op1* is not equal to *op2*.
656
FOGT  
Kunshan Wang's avatar
Kunshan Wang committed
657
    Both operands are not NaN and *op1* is greater than *op2*.
658
FOGE  
Kunshan Wang's avatar
Kunshan Wang committed
659
    Both operands are not NaN and *op1* is greater than or equal to *op2*.
660
FOLT  
Kunshan Wang's avatar
Kunshan Wang committed
661
    Both operands are not NaN and *op1* is less than *op2*.
662
FOLE  
Kunshan Wang's avatar
Kunshan Wang committed
663
    Both operands are not NaN and *op1* is less than or equal to *op2*.
664 665 666 667 668 669 670 671 672 673 674

..

    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.

    =========== =========== =========== =============== =========== ===========
675
    Comparison  unordered   less than   greater than    equal       negation
676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702
    =========== =========== =========== =============== =========== ===========
    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::

Kunshan Wang's avatar
Kunshan Wang committed
703 704 705 706 707 708 709
        .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)
710

Kunshan Wang's avatar
Kunshan Wang committed
711 712
        %y = FOGT <@double> @w @x   // 0 (false)
        %z = FULT <@double> @w @x   // 1 (true)
713

Kunshan Wang's avatar
Kunshan Wang committed
714 715
        %u = FOGT <@double> @w @D_NAN   // 0 (false) (result is "unordered")
        %v = FUGT <@double> @w @D_NAN   // 1 (true)  (result is "unordered")
716

Kunshan Wang's avatar
Kunshan Wang committed
717 718 719 720 721
        %e = NEW <@i64>
        %f = EQ <@refi64> %e %e     // 1 (true) (same object)

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

723 724 725 726 727 728 729 730 731 732
        .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)

733 734 735
Conversion
----------

736
*convOp* ``<`` *T1* *T2* ``>`` *opnd*
737

738 739 740 741 742 743
convOp
    The conversion operation.
T1, T2
    *type*: The source type and the destination type, respectively.
opnd
    *value* of type *T1*: The operand.
744
result:
745
    Type *T2*: The result of the conversion.
746 747 748 749 750 751 752

+--------+-----+-----+-----+
| opct   | idt | idt | idt |
+========+=====+=====+=====+
| opcode | T1  | T2  | op  |
+--------+-----+-----+-----+

753
*convOp* is one in the following table.
754 755

========== ======== ============    ============
756
 convOp     opcode   T1              T2
757 758 759 760 761 762 763 764 765 766 767 768
========== ======== ============    ============
 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)
769
 PTRCAST    0x3B    (see below)     (see below)
770 771
========== ======== ============    ============

772 773
    TODO: Move the opcode to the IR Builder API.

774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798
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.
Kunshan Wang's avatar
Kunshan Wang committed
799
  + *T1* is a floating point type and *T2* is an integer type of the same number
800 801 802 803 804 805
    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``.
Kunshan Wang's avatar
Kunshan Wang committed
806
  + Both *T1* and *T2* are ``funcref``.
807

808 809
* For PTRCAST, *T1* and *T2* must be two of the three cases:

Kunshan Wang's avatar
Kunshan Wang committed
810 811
  + ``uptr<T>`` for some T.
  + ``ufuncptr<sig>`` for some sig.
812 813
  + ``int<n>`` for some n.

814 815 816 817 818 819 820 821 822 823
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
Kunshan Wang's avatar
Kunshan Wang committed
824 825
    Convert *opnd* to a smaller floating point type, rounding to nearest and
    round ties to even according to IEEE754.
826
FPEXT
Kunshan Wang's avatar
Kunshan Wang committed
827
    Convert *opnd* to a larger floating point type. Always exact.
828
FPTOUI
Kunshan Wang's avatar
Kunshan Wang committed
829 830 831 832
    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.
833
FPTOSI
Kunshan Wang's avatar
Kunshan Wang committed
834 835 836 837
    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.
838
UITOFP
Kunshan Wang's avatar
Kunshan Wang committed
839 840
    Interpret *opnd* as unsigned and convert *opnd* to a floating point type,
    rounding to nearest and round ties to even according to IEEE754.
841
SITOFP
Kunshan Wang's avatar
Kunshan Wang committed
842 843
    Interpret *opnd* as signed and convert *opnd* to a floating point type,
    rounding to nearest and round ties to even according to IEEE754.
844 845 846 847 848 849 850
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*.
Kunshan Wang's avatar
Kunshan Wang committed
851 852 853
    * When converting between ``funcref``, the result refers to the same
      function as *opnd*, but may treat the function as having a different
      signature.
854 855
    * In all cases, if the operand is ``NULL``, the result is the ``NULL`` value
      of the result type.
856 857 858 859
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.
860 861 862

..

Kunshan Wang's avatar
Kunshan Wang committed
863
    For LLVM users: These instructions are borrowed from LLVM. Mu currently
864
    lacks the conversion between raw pointer types and numerical types and they
Kunshan Wang's avatar
Kunshan Wang committed
865 866
    will be added when raw pointers are introduce. ``REFCAST`` is Mu-specific.
    Mu cannot use ``bitcast`` to cast between reference types.
867 868 869 870 871

..

    Example::

Kunshan Wang's avatar
Kunshan Wang committed
872 873
        .const @a  <@i32> = 42
        .const @a2 <@i32> = -42
Kunshan Wang's avatar
Kunshan Wang committed
874 875 876 877 878
        %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
879 880

        .const @x  <@double> = 42.0d
Kunshan Wang's avatar
Kunshan Wang committed
881 882 883
        %y = FPTRUNC    <@double @float>  @x    // is a @float
        %z = FPEXT      <@float  @double> %y    // is a @double
        %w = FPTOSI     <@double @i64>    @x    // is a @i64
884 885 886 887 888 889 890 891

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

Kunshan Wang's avatar
Kunshan Wang committed
892 893
        %f = NEW <@Foo>                     // is a ref<@Foo>
        %g = REFCAST <@refFoo @refBar> %f   // is a ref<@Bar>
894

Kunshan Wang's avatar
Kunshan Wang committed
895 896
        %h = ALLOCA <@Foo>                  // is a iref<@Foo>
        %i = REFCAST <@irefFoo @irefBar> %h // is a iref<@Bar>
897 898 899 900

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

901 902
        .funcsig @vv = () -> ()
        .funcsig @main_sig = (@i32 @iii8) -> (@i32)
903
        .funcdecl @j <@main_sig>
Kunshan Wang's avatar
Kunshan Wang committed
904
        %k = REFCAST <@main_sig @vv> @j     // is a funcref<@vv>
905

Kunshan Wang's avatar
Kunshan Wang committed
906 907
``SELECT`` Instruction
----------------------
908

909
``SELECT`` ``<`` *S* *T* ``>`` *cond* *ifTrue* *ifFalse*
910

911 912 913
S
    *type*: The type of *cond*.
T
914
    *type*: The type of *ifTrue*, *ifFalse* and the result.
915 916
cond
    *variable* of type *S*: The condition.
917
ifTrue, ifFalse
918
    *variable* of *T*: The candidates of the result.
919
result:
920
    Type *T*: A value according to *cond*.
921

922 923 924 925
*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*.

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

929
When *S* is ``int<1>``, then the result is *ifTrue* if *cond* is 1, or *ifFalse*
930
if *cond* is 0.
931

932
When *S* is a vector of ``int<1>``, the corresponding element of the result is
933 934
the corresponding element of *ifTrue* if the corresponding element of *cond* is
1, or the corresponding element of *ifFalse* otherwise.
935

936 937 938 939
..

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

941 942 943 944 945
..

    Example::

        .const @a <@i64> = 42
946 947 948 949 950 951 952 953
        .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
954 955 956 957

Intra-function Control Flow
===========================

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

Kunshan Wang's avatar
Kunshan Wang committed
960 961
``BRANCH`` Instruction
----------------------
962

963
``BRANCH`` *dest*
964

965
dest
966
    *destination clause*: The destination of jumping.
967

968
This instruction branches to *dest*.
969

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

973
    Example::
974

975 976
        %entry():
            BRANCH %head(%a)
977

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

Kunshan Wang's avatar
Kunshan Wang committed
981 982
``BRANCH2`` Instruction
-----------------------
983

984
``BRANCH2`` *cond* *ifTrue* *ifFalse*
985

986
cond
987
    *variable* of type ``int<1>``: The condition
988
ifTrue, ifFalse
989
    *destination clause*: The destinations to jump to when *cond* is 1 or 0,
990
    respectively
991

992
If *cond* is 1, jump to *ifTrue*, otherwise jump to *ifFalse*.
993

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

..
998

999
    Example::
1000

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

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

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

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

Kunshan Wang's avatar
Kunshan Wang committed
1013 1014
``SWITCH`` Instruction
----------------------
1015

1016
``SWITCH`` ``<`` *T* ``>`` *opnd* *default* ``{`` *(* *value* *dest* *)* :sub:`rep` ``}``
1017

1018
T
1019
    *type*: The type of *opnd* and all *value*
1020 1021 1022
opnd
    *variable* of *T*: The value to compare against.
default:
1023 1024
    *destination clause*: The default destination, i.e. the destination if no
    case matches.
1025
value:
1026
    *constant value* of *T*: The case value for a branch.
1027
dest:
1028
    *destination clause*: The destination for the corresponding case.
1029

1030
There are zero or more *value*-*dest* pairs.
1031

1032
*opnd* and all *value* must have type *T*. *default* and all *dest* must be
1033 1034 1035 1036
basic blocks.

*T* must be an EQ-comparable type.

1037
All *value* must be constants and must have distinct values.
1038

1039 1040
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*.
1041

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

1044
    Example::
1045

1046 1047 1048 1049
        .const @a <@i64> = ...
        .const @ONE <@i64> = 1
        .const @TWO <@i64> = 2
        .const @THREE <@i64> = 3
1050

1051 1052 1053 1054 1055
        %entry():
            SWITCH <@i64> @a %defbranch() {
                @ONE %one()
                @TWO %two()
                @THREE %three()
1056
                }
1057

1058
        %defbranch():
1059
            ...
1060

1061
        %one():
1062 1063
            ...

1064
        %two():
1065 1066
            ...
            
1067
        %three():
1068
            ...
1069 1070 1071 1072

Inter-function Control Flow
===========================

Kunshan Wang's avatar
Kunshan Wang committed
1073 1074
``CALL`` and ``TAILCALL`` Instruction
-------------------------------------
1075

1076
``CALL`` ``<`` *sig* ``>`` *callee* *argList* *excClause* *keepAliveClause*
1077

1078
``TAILCALL`` ``<`` *sig* ``>`` *callee* *argList*
1079 1080 1081

sig
    *function signature*: The signature of the callee.
1082
callee
Kunshan Wang's avatar
Kunshan Wang committed
1083
    *variable* of type ``funcref<sig>``: The callee.
Kunshan Wang's avatar
Kunshan Wang committed
1084 1085
argList
    *argument list*: Argument list.
1086
excClause
Kunshan Wang's avatar
Kunshan Wang committed
1087
    *exception clause*: Specifies the basic block to handle Mu exceptions and
1088 1089
    stack overflow.
keepAliveClause
Kunshan Wang's avatar
Kunshan Wang committed
1090
    *keep-alive clause*: For on-stack replacement.
1091 1092 1093 1094 1095
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.
1096

1097
The ``CALL`` instruction creates a new stack frame for the callee, passes the
Kunshan Wang's avatar
Kunshan Wang committed
1098
arguments in *argList* and starts executing from the entry block of the callee.
1099

1100 1101 1102 1103
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**.

1104
A ``CALL`` instruction *continues normally* when the callee returns. In this
1105 1106
case the results of the ``CALL`` instruction are the return values of the
callee.
1107 1108 1109 1110

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
1111 1112 1113
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.
1114 1115 1116

A ``CALL`` instruction *continues exceptionally* when the function call causes a
stack overflow. In this case the value of the ``CALL`` instruction is not
1117 1118 1119 1120 1121 1122 1123
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.

1124 1125
Whenever ``CALL`` continues exceptionally, the ``CALL`` instruction does not
produce results.
1126 1127 1128 1129 1130 1131 1132 1133

    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]:
            ...
1134 1135 1136

The ``CALL`` instruction is an OSR point.

1137 1138 1139
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.
1140

1141 1142
    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
1143
    means of stack binding. See `Threads and Stacks <threads-stacks.rst>`__.
1144

1145
The ``TAILCALL`` instruction replaces the caller's stack frame with a new stack
1146 1147 1148 1149 1150
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.
1151 1152

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

1156 1157 1158 1159 1160 1161 1162 1163
    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
1164
when executed so that the client can handle it. See `Mu IR <ir.rst>`__ for
1165
the behaviour of undefined functions.
1166

Kunshan Wang's avatar
Kunshan Wang committed
1167
..
1168

Kunshan Wang's avatar
Kunshan Wang committed
1169 1170 1171 1172 1173 1174
    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.
1175
    - Mu functions may return multiple values.
1176
    - Mu uses the goto-with-values form.
Kunshan Wang's avatar
Kunshan Wang committed
1177
    - The meaning of ``TAILCALL`` is similar to LLVM's ``musttail``: in Mu, a
Kunshan Wang's avatar
Kunshan Wang committed
1178
      ``TAILCALL`` always replaces the current stack frame.
Kunshan Wang's avatar
Kunshan Wang committed
1179
    - Calling conventions cannot be specified in Mu: Mu always uses its
1180 1181
      internal calling conventions. The ``CCALL`` instruction is for native
      calls.
Kunshan Wang's avatar
Kunshan Wang committed
1182 1183
    - Arguments will not be automatically zero or sign-extended or truncated for
      the programmer. Conversions must be explicitly done before calling.  
Kunshan Wang's avatar
Kunshan Wang committed
1184 1185
    - The ``funcref`` type in Mu is a dedicated function reference, not a
      pointer. See ``CCALL`` which calls a native function.
Kunshan Wang's avatar
Kunshan Wang committed
1186 1187
    - All parameters are passed by value and parameters are SSA Values. To pass
      on-stack data or arrays, use ``alloca`` and pass ``iref``.  
1188 1189 1190
    - The keep-alive clause is similar to the experimental intrinsic function
      ``@llvm.experimental.stackmap`` and ``@llvm.experimental.patchpoint`` in
      LLVM.
1191

Kunshan Wang's avatar
Kunshan Wang committed
1192
..
1193

Kunshan Wang's avatar
Kunshan Wang committed
1194
    Example::
1195

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

Kunshan Wang's avatar
Kunshan Wang committed
1198
        .funcdecl @sum <@sig>
1199

1200 1201
        .funcdef @square_sum VERSION %v1 <@sig> {
            %entry(<@double> %x <@double> %y):
Kunshan Wang's avatar
Kunshan Wang committed
1202 1203
                %x2 = MUL <@double> %x %x
                %y2 = MUL <@double> %y %y
1204

Kunshan Wang's avatar
Kunshan Wang committed
1205 1206 1207
                // return the result of sum(x2,y2)
                TAILCALL <@sig> @sum (%x2 %y2)    
        }
1208

1209
        .funcsig @vv = () -> ()
1210

Kunshan Wang's avatar
Kunshan Wang committed
1211 1212 1213 1214
        .const @D_3 <@double> = 3.0d
        .const @D_4 <@double> = 4.0d
        .const @D_5 <@double> = 5.0d
        .const @D_6 <@double> = 6.0d
1215

1216
        .funcdef @main VERSION %v1 <@vv> {
1217
            %entry():
Kunshan Wang's avatar
Kunshan Wang committed
1218
                %a = CALL <@sig> @square_sum (@D_3 @D_4)
1219
                %b = CALL <@sig> @square_sum (%a   @D_5) EXC(%nor(%a %b) %exc())
1220

1221
            %nor(<@double> %a <@double> %b):
1222
                %c = [%important_call_site] CALL <@sig> @square_sum (@D_5 @D_6) KEEPALIVE(%a %b)
1223
                %d = CALL <@sig> @square_sum (%c   %c)   EXC(%nor2(%c %d) %exc()) KEEPALIVE(%a %c)
Kunshan Wang's avatar
Kunshan Wang committed
1224

1225
            %nor2(<@double> %c <@double> %d):
Kunshan Wang's avatar
Kunshan Wang committed
1226 1227
                // continue here
            
1228
            %exc() [%the_exc]:
Kunshan Wang's avatar
Kunshan Wang committed
1229 1230
                // handle the exception
        }
1231

1232 1233
``RET`` Instruction
-------------------
1234

1235 1236
``RET`` ``(`` *rv* :sub:`rep` ``)``

1237
``RET`` *rv*
1238

1239 1240 1241
rv :sub:`rep`
    The return value of the current function. The number and the types must
    match the return types of the current function.
1242

1243 1244 1245
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.
1246

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

1250 1251
``RET rv`` is a syntax sugar of ``RET (rv)``. In order to return from a function
with zero return values, use ``RET ()``.
Kunshan Wang's avatar
Kunshan Wang committed
1252

1253 1254
The ``RET`` instruction itself does not produce results. The return values are
returned to the caller.
Kunshan Wang's avatar
Kunshan Wang committed
1255 1256

..
1257

Kunshan Wang's avatar
Kunshan Wang committed
1258
    For LLVM users: Equivalent to LLVM's ``ret`` and ``ret void``.
1259

Kunshan Wang's avatar
Kunshan Wang committed
1260
..
1261

Kunshan Wang's avatar
Kunshan Wang committed
1262
    Example::
1263

1264 1265 1266
        .funcsig @sig1 = (@double @double) -> (@double)
        .funcsig @sig2 = () -> ()
        .funcsig @sig3 = (@i64 @i64) -> (@i64 @i64)
1267

1268 1269
        .funcdef @sum VERSION %v1 <@sig1> {
            %entry(<@double> %x <@double> %y):
Kunshan Wang's avatar
Kunshan Wang committed
1270
                %s = ADD <@double> %x %y
1271
                RET %s
Kunshan Wang's avatar
Kunshan Wang committed
1272 1273
        }

1274 1275
        .funcdef @main VERSION %v1 <@sig2> {
            %entry():
1276 1277 1278 1279 1280 1281
                RET ()
        }

        .funcdef @swap VERSION %v1 <@sig3> {
            %entry(<@i64> %x <@i64> %y):
                RET (%y %x)
Kunshan Wang's avatar
Kunshan Wang committed
1282
        }
1283

Kunshan Wang's avatar
Kunshan Wang committed
1284 1285
``THROW`` Instruction
---------------------
1286

1287
``THROW`` *exc*
1288

1289 1290
exc
    *variable* of type ``ref`` to any type: The exception object.
1291

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

Kunshan Wang's avatar
Kunshan Wang committed
1295 1296
    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
Kunshan Wang's avatar
Kunshan Wang committed
1297
    done by Mu's ``THROW`` instruction. Mu programs can create a new exception
Kunshan Wang's avatar
Kunshan Wang committed
1298 1299
    object by ``NEW`` and throw it, where LLVM must depend on platform-specific
    libraries to allocate new exceptions.
1300

Kunshan Wang's avatar
Kunshan Wang committed
1301
..
1302

Kunshan Wang's avatar
Kunshan Wang committed
1303
    Example::
1304

1305
        .funcsig @sig = (@i64 @i64) -> (@i64)
Kunshan Wang's avatar
Kunshan Wang committed
1306
        .typedef @SomeExceptionType = ...    // user-defined exception type
1307

1308 1309
        .funcdef @safe_divide VERSION %v1 <@sig> {
            %entry(<@double> %x <@double> %y):
Kunshan Wang's avatar
Kunshan Wang committed
1310
                %y0 = EQ <@i64> %y @I64_0
1311
                BRANCH %y0 %divbyzero() %okay(%x %y)
1312

1313
            %divbyzero():
Kunshan Wang's avatar
Kunshan Wang committed
1314 1315 1316 1317
                %exc = NEW <@SomeExceptionType>
                // initialise %exc
                THROW %exc

1318 1319 1320
            %okay(<@double> %x <@double> %y):
                %rv = SDIV <@i64> %x %y
                RET %rv
Kunshan Wang's avatar
Kunshan Wang committed
1321
        }
1322 1323 1324 1325

Aggregate Type Operations
=========================

1326 1327
These instructions operate on the ``struct``, the ``array`` and the ``vector``
types as SSA variables.
1328

Kunshan Wang's avatar
Kunshan Wang committed
1329 1330
Struct Operations
-----------------
1331

Kunshan Wang's avatar
Kunshan Wang committed
1332 1333
``EXTRACTVALUE`` Instruction
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1334

Kunshan Wang's avatar
Kunshan Wang committed
1335 1336 1337 1338 1339 1340 1341 1342
``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.
1343
result:
Kunshan Wang's avatar
Kunshan Wang committed
1344 1345
    Type is the index-th field of the struct type *T*: The value of the
    *index*-th field of *opnd*.
1346

Kunshan Wang's avatar
Kunshan Wang committed
1347 1348
The ``EXTRACTVALUE`` instruction extracts the index-th field from the value of
an SSA variable *opnd* which has type ``struct``.
1349

Kunshan Wang's avatar
Kunshan Wang committed
1350
    For LLVM users: It is the counterpart of the ``extractvalue`` instruction in
Kunshan Wang's avatar
Kunshan Wang committed
1351
    LLVM. But Mu's ``EXTRACTVALUE`` does not work on arrays or nested
1352 1353
    ``struct``.  Use ``EXTRACTVALUE`` multiple times to extract the field in
    nested structs.
Kunshan Wang's avatar
Kunshan Wang committed
1354 1355

..
1356

Kunshan Wang's avatar
Kunshan Wang committed
1357
    Example: see the example of ``INSERTVALUE``
1358

Kunshan Wang's avatar
Kunshan Wang committed
1359 1360
``INSERTVALUE`` Instruction
~~~~~~~~~~~~~~~~~~~~~~~~~~~
1361

1362
``INSERTVALUE`` ``<`` *T* *index* ``>`` *opnd* *newVal*
1363

Kunshan Wang's avatar
Kunshan Wang committed
1364 1365 1366 1367 1368 1369
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.
1370
newVal
Kunshan Wang's avatar
Kunshan Wang committed
1371 1372
    *variable* of the type of the *index*-th field of *T*: The new value for the
    field specified by *index*.
1373
result:
1374
    Type is *T*: A new struct with the *index*-th field being *newVal*.
1375

Kunshan Wang's avatar
Kunshan Wang committed
1376 1377
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
1378
*newVal*.
1379

Kunshan Wang's avatar
Kunshan Wang committed
1380
    For LLVM users: It is the counterpart of the ``insertvalue`` instruction in
Kunshan Wang's avatar
Kunshan Wang committed
1381
    LLVM. But Mu's ``INSERTVALUE`` does not work on arrays or nested
Kunshan Wang's avatar
Kunshan Wang committed
1382 1383 1384 1385
    ``struct``.  Use a combination of ``EXTRACTVALUE`` and ``INSERTVALUE`` to
    replace a field in a nested struct.

..
1386

Kunshan Wang's avatar
Kunshan Wang committed
1387
    Example::
1388

Kunshan Wang's avatar