Skip to content

Intrinsic Functions Design

Jump to bottom Edit New page
Ondřej Čertík edited this page Apr 11, 2022 · 36 revisions

Current Status and Background

Currently both LPython and LFortran has intrinsic functions of two types:

  • an actual language intrinsic function such as chr or len in Python and modulo or sin in Fortran
  • functions that are not directly called by the user, but are still intrinsic, inserted by the frontend (AST to ASR pass) into ASR, an example is the string formatting % operator in Python, or format in Fortran. You can think of these a auxiliary functions that help the frontend represent certain operations, but from the ASR and backend perspectives they just behave like intrinsic functions.

They are all implemented in the runtime library in src/runtime as either Python or Fortran source code. There are either just interfaces, or have an implementation:

  • Interface only: those are functions that must be implemented by the backends, they cannot be implemented in the language itself. Examples are: len, size, ubound; as well as operations like bitwise integer operations, and even arithmetic operations (such as plus as in 1+1, minus, multiply, power, etc).
  • Implementation: functions that can be implemented in the frontend language, or more specifically, they can be implemented using other ASR operations. These are the vast majority of functions, such as trigonometric functions (sin, cos, ...) and other mathematical functions, file operations, string formatting and manipulation, even things like modulo or floor. These functions are implemented either directly, or via calling into C, but in both cases they are implemented in ASR and the backends can treat them like any other function.

A special case of the "Implementation" intrinsic functions are functions like flipsign which is an intrinsic function, inserted by an optimization pass to represent a certain operation:

And then the backend can optionally provide a very efficient implementation:

We will have hundreds of such optimizations like flipsign, there is no upper bound on how many we can do. However, they all have an implementation, so if the backend doesn't want to implement them, it can just use the implementation and compile them like any other user function.

I think the number of intrinsic functions that are "Interface" only is limited.

See also the LFortran initial brainstorming for the compile time handling of intrinsic functions like sin and the current implementation in LFortran and LPython:

Requirements

The requirements on ASR passes and backends is that:

  • they must be able to quickly identify a given function; probably using an integer ID that is unique
  • there shouldn't be any overhead over representing such operation in ASR directly such as currently BinOp: https://github.com/lcompilers/lpython/blob/1d7ba2e6de540c7a5a926fe70ae3a32c88adcfd0/grammar/ASR.asdl#L205; that means that instead of representing * as BinOp and checking the "op" argument (effectively an integer), it would be a FunctionCall, but one would check the ID argument (an integer), there would be just many more options for the ID (hundreds or thousands instead of 5), but it should be possible to implement it as efficiently, using the techniques from re2c --- possibly even as a large switch statement.
  • It should be as fast to construct the ASR, that is, if * is represented as mul_i32_i32 function, constructing the FunctionCall node should be as fast as constructing the BinOp node --- the frontend has understanding of these operations anyway, so it can load the function mul_i32_i32 and store it in a symbol table and then just reference it quickly. With such an approach it should be possible to make it as fast as the current BinOp implementation.
  • We should not manage integers directly, but either some enum, or defines, so that we have one place in libasr that lists / registers these functions in some kind of a list, but underneath it would be equivalent to integer comparison for speed.
  • The "interface" operations are set and the same (equivalent) for each front end language
  • The functions like flipsign for optimizations are also the same for each language
  • Each frontend language then has its own functions, such as string formatting functions (Python and Fortran has different string formatting)

We might later convert even BinOp, BoolOp, StrOp into just function calls like any other intrinsic functions, but those should be done at the end, once the design is implemented, so that we can ensure the performance is the same. For now we will implement the above design for other functions first, and we get to these fundamental operations like integer arithmetic at the very end.

Ideas

Some ideas:

  • For the common functions len, size (interface), flipsign, fma (implementation) we can maintain them as ASR code (pretty printed) in libasr itself. Then libasr will have printers of ASR to the surface languages (Python, Fortran, ...), so we simply generate all the code for len, size, flipsign, ... into LPython and LFortran from libasr's ASR "reference" implementation. To update it, one can update the Python code via LPython, or Fortran code via LFortran, get new ASR and commit to libasr. As we sync libasr across LPython/LFortran, we simply regenerate this part of the runtime library. This approach would apply to all functions for which libasr must have special knowledge, that is, it needs these functions either in the LLVM or other backends (len, flipsign), or in the ASR passes (flipsign).

  • The functions that are unique to each frontend (such as string formatting) would simply only be maintained by that frontend. Libasr would not have any special knowledge of these (besides being intrinsic).

Proposal for "Interface/Builtin" Intrinsics

For intrinsic functions that cannot be implemented in the frontend language, such as len, size, reshape, list.append(), ubound, as well as +, -, *, etc. would be implemented in ASR itself. Then we can remove the lfortran/lpython_builtin module; ASR becomes 100% self sufficient. It will not require any runtime library. The backends might choose to implement some functionality using a runtime library specific to the backend, but that's a separate issue (say a complex multiplication can be implemented as a C function, but that cannot be done at the ASR level, as the C function requires access to the "internals" of the complex number, which at the ASR level is an "opaque" intrinsic type).

Let us list all such intrinsic "operations". Divided by type:

Integer

+, -, *, /, **, bit and, bit or, bit xor, <<, >>

Real

+, -, *, /, **

Complex

+, -, *, /, **, %re, %im

Logical

and, or, xor

String/Character

len, string concatenation, string indexing, allocate, deallocate

Note: "string repeat" can be implemented using the above intrinsic operations.

Array

size, shape, reshape, indexing/slicing, array operations: +, -, *, /, ** (and "%re, %im" for complex arrays, "bit and, bit or, bit xor, <<, >>" for integer arrays, and "and, or, xor" for logical arrays) --- possibly these operations can be represented using the operators on the basic types that could accept arrays (of exactly the same shape, type and kind) as well.

allocate, deallocate

List

allocate, deallocate, append, indexing/slicing, len

Tuple

len, indexing/slicing

Dict

add_item, remove_item_at_index, len, indexing

Set

add_item, remove_item, len

Add a custom footer
Add a custom sidebar
Clone this wiki locally