<commit_before>***************************
Cretonne Language Reference
***************************

.. default-domain:: cton
.. highlight:: cton

The Cretonne intermediate language (:term:`IL`) has two equivalent
representations: an *in-memory data structure* that the code generator library
is using, and a *text format* which is used for test cases and debug output.
Files containing Cretonne textual IL have the ``.cton`` filename extension.

This reference uses the text format to describe IL semantics but glosses over
the finer details of the lexical and syntactic structure of the format.


Overall structure
=================

Cretonne compiles functions independently. A ``.cton`` IL file may contain
multiple functions, and the programmatic API can create multiple function
handles at the same time, but the functions don't share any data or reference
each other directly.

This is a simple C function that computes the average of an array of floats:

.. literalinclude:: example.c
    :language: c

Here is the same function compiled into Cretonne IL:

.. literalinclude:: example.cton
    :language: cton
    :lines: 2-

The first line of a function definition provides the function *name* and
the :term:`function signature` which declares the argument and return types.
Then follows the :term:`function preamble` which declares a number of entities
that can be referenced inside the function. In the example above, the preamble
declares a single local variable, ``ss1``.

After the preamble follows the :term:`function body` which consists of
:term:`extended basic block`\s (EBBs), the first of which is the
:term:`entry block`. Every EBB ends with a :term:`terminator instruction`, so
execution can never fall through to the next EBB without an explicit branch.

A ``.cton`` file consists of a sequence of independent function definitions:

.. productionlist::
    function_list : { function }
    function      : function_spec "{" preamble function_body "}"
    function_spec : "function" function_name signature
    preamble      : { preamble_decl }
    function_body : { extended_basic_block }

Static single assignment form
-----------------------------

The instructions in the function body use and produce *values* in SSA form. This
means that every value is defined exactly once, and every use of a value must be
dominated by the definition.

Cretonne does not have phi instructions but uses *EBB arguments* instead. An EBB
can be defined with a list of typed arguments. Whenever control is transferred
to the EBB, values for the arguments must be provided. When entering a function,
the incoming function arguments are passed as arguments to the entry EBB.

Instructions define zero, one, or more result values. All SSA values are either
EBB arguments or instruction results.

In the example above, the loop induction variable ``i`` is represented as three
SSA values: In the entry block, ``v4`` is the initial value. In the loop block
``ebb2``, the EBB argument ``v5`` represents the value of the induction
variable during each iteration. Finally, ``v12`` is computed as the induction
variable value for the next iteration.

It can be difficult to generate correct SSA form if the program being converted
into Cretonne :term:`IL` contains multiple assignments to the same variables.
Such variables can be presented to Cretonne as :term:`stack slot`\s instead.
Stack slots are accessed with the :inst:`stack_store` and :inst:`stack_load`
instructions which behave more like variable accesses in a typical programming
language. Cretonne can perform the necessary data-flow analysis to convert stack
slots to SSA form.

.. _value-types:

Value types
===========

All SSA values have a type which determines the size and shape (for SIMD
vectors) of the value. Many instructions are polymorphic -- they can operate on
different types.

Boolean types
-------------

Boolean values are either true or false. While this only requires a single bit
to represent, more bits are often used when holding a boolean value in a
register or in memory. The :type:`b1` type represents an abstract boolean
value. It can only exist as an SSA value, it can't be stored in memory or
converted to another type. The larger boolean types can be stored in memory.
They are represented as either all zero bits or all one bits.

.. autoctontype:: b1
.. autoctontype:: b8
.. autoctontype:: b16
.. autoctontype:: b32
.. autoctontype:: b64

Integer types
-------------

Integer values have a fixed size and can be interpreted as either signed or
unsigned. Some instructions will interpret an operand as a signed or unsigned
number, others don't care.

.. autoctontype:: i8
.. autoctontype:: i16
.. autoctontype:: i32
.. autoctontype:: i64

Floating point types
--------------------

The floating point types have the IEEE semantics that are supported by most
hardware. There is no support for higher-precision types like quads or
double-double formats.

.. autoctontype:: f32
.. autoctontype:: f64

CPU flags types
---------------

Some target ISAs use CPU flags to represent the result of a comparison. These
CPU flags are represented as two value types depending on the type of values
compared.

Since some ISAs don't have CPU flags, these value types should not be used
until the legalization phase of compilation where the code is adapted to fit
the target ISA. Use instructions like :inst:`icmp` instead.

.. autoctontype:: iflags
.. autoctontype:: fflags

SIMD vector types
-----------------<commit_msg>Expand on the floating-point section and provide the NaN rules.<commit_after>***************************
Cretonne Language Reference
***************************

.. default-domain:: cton
.. highlight:: cton

The Cretonne intermediate language (:term:`IL`) has two equivalent
representations: an *in-memory data structure* that the code generator library
is using, and a *text format* which is used for test cases and debug output.
Files containing Cretonne textual IL have the ``.cton`` filename extension.

This reference uses the text format to describe IL semantics but glosses over
the finer details of the lexical and syntactic structure of the format.


Overall structure
=================

Cretonne compiles functions independently. A ``.cton`` IL file may contain
multiple functions, and the programmatic API can create multiple function
handles at the same time, but the functions don't share any data or reference
each other directly.

This is a simple C function that computes the average of an array of floats:

.. literalinclude:: example.c
    :language: c

Here is the same function compiled into Cretonne IL:

.. literalinclude:: example.cton
    :language: cton
    :lines: 2-

The first line of a function definition provides the function *name* and
the :term:`function signature` which declares the argument and return types.
Then follows the :term:`function preamble` which declares a number of entities
that can be referenced inside the function. In the example above, the preamble
declares a single local variable, ``ss1``.

After the preamble follows the :term:`function body` which consists of
:term:`extended basic block`\s (EBBs), the first of which is the
:term:`entry block`. Every EBB ends with a :term:`terminator instruction`, so
execution can never fall through to the next EBB without an explicit branch.

A ``.cton`` file consists of a sequence of independent function definitions:

.. productionlist::
    function_list : { function }
    function      : function_spec "{" preamble function_body "}"
    function_spec : "function" function_name signature
    preamble      : { preamble_decl }
    function_body : { extended_basic_block }

Static single assignment form
-----------------------------

The instructions in the function body use and produce *values* in SSA form. This
means that every value is defined exactly once, and every use of a value must be
dominated by the definition.

Cretonne does not have phi instructions but uses *EBB arguments* instead. An EBB
can be defined with a list of typed arguments. Whenever control is transferred
to the EBB, values for the arguments must be provided. When entering a function,
the incoming function arguments are passed as arguments to the entry EBB.

Instructions define zero, one, or more result values. All SSA values are either
EBB arguments or instruction results.

In the example above, the loop induction variable ``i`` is represented as three
SSA values: In the entry block, ``v4`` is the initial value. In the loop block
``ebb2``, the EBB argument ``v5`` represents the value of the induction
variable during each iteration. Finally, ``v12`` is computed as the induction
variable value for the next iteration.

It can be difficult to generate correct SSA form if the program being converted
into Cretonne :term:`IL` contains multiple assignments to the same variables.
Such variables can be presented to Cretonne as :term:`stack slot`\s instead.
Stack slots are accessed with the :inst:`stack_store` and :inst:`stack_load`
instructions which behave more like variable accesses in a typical programming
language. Cretonne can perform the necessary data-flow analysis to convert stack
slots to SSA form.

.. _value-types:

Value types
===========

All SSA values have a type which determines the size and shape (for SIMD
vectors) of the value. Many instructions are polymorphic -- they can operate on
different types.

Boolean types
-------------

Boolean values are either true or false. While this only requires a single bit
to represent, more bits are often used when holding a boolean value in a
register or in memory. The :type:`b1` type represents an abstract boolean
value. It can only exist as an SSA value, it can't be stored in memory or
converted to another type. The larger boolean types can be stored in memory.
They are represented as either all zero bits or all one bits.

.. autoctontype:: b1
.. autoctontype:: b8
.. autoctontype:: b16
.. autoctontype:: b32
.. autoctontype:: b64

Integer types
-------------

Integer values have a fixed size and can be interpreted as either signed or
unsigned. Some instructions will interpret an operand as a signed or unsigned
number, others don't care.

.. autoctontype:: i8
.. autoctontype:: i16
.. autoctontype:: i32
.. autoctontype:: i64

Floating point types
--------------------

The floating point types have the IEEE 754 semantics that are supported by most
hardware, except that non-default rounding modes, unmasked exceptions, and
exception flags are not currently supported.

There is currently no support for higher-precision types like quad-precision,
double-double, or extended-precision, nor for narrower-precision types like
half-precision.

NaNs are encoded following the IEEE 754-2008 recommendation, with quiet NaN
being encoded with the MSB of the trailing significand set to 1, and signaling
NaNs being indicated by the MSB of the trailing significand set to 0.

Except for bitwise and memory instructions, NaNs returned from arithmetic
instructions are encoded as follows:
- If all NaN inputs to an instruction are quiet NaNs with all bits of the
  trailing significand other than the MSB set to 0, the result is a quiet
  NaN with a nondeterministic sign bit and all bits of the trailing
  significand other than the MSB set to 0.
- Otherwise the result is a quiet NaN with a nondeterministic sign bit
  and all bits of the trailing significand other than the MSB set to
  nondeterministic values.

.. autoctontype:: f32
.. autoctontype:: f64

CPU flags types
---------------

Some target ISAs use CPU flags to represent the result of a comparison. These
CPU flags are represented as two value types depending on the type of values
compared.

Since some ISAs don't have CPU flags, these value types should not be used
until the legalization phase of compilation where the code is adapted to fit
the target ISA. Use instructions like :inst:`icmp` instead.

.. autoctontype:: iflags
.. autoctontype:: fflags

SIMD vector types
-----------------
{'fraction_non_alphanumeric': 0.08221685944911375, 'fraction_numerical': 0.005658650245485562, 'mean_word_length': 4.047459050818984, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4378900', 'n_tokens_mistral': 3086, 'n_tokens_neox': 2940, 'n_words': 1708}