Compile Time Constant Expressions for Swift

XXXX-constexpr.md

Compile Time Constant Expressions for Swift

• Proposal: SE-NNNN
• Authors: Marc Rasi, Chris Lattner
• Review Manager: TBD
• Status: Awaiting implementation

Swift-evolution thread: https://forums.swift.org/t/pitch-compile-time-constant-expressions-for-swift/12879

Introduction

If Swift guaranteed compile-time evaluation of certain user code, then Swift could support many new inherently static features. For example, Swift could support a #assert operation that detects assertion failures at compile time:

struct MyStruct {
  let x: Int
  let y: Bool
}

#assert(
  MemoryLayout<MyStruct>.size <= 16,
  "The serialization format only has 16 bytes for MyStruct.")

It is important that Swift exposes an easy-to-understand contract for what code is compatible with static clients like #assert, so that users can look at Swift documentation and Swift compiler diagnostics for guidance about what kind of code they can write.

This proposal proposes a contract that guarantees compile-time evaluation of certain user code. Whenever a user writes code conforming to this contract, the compiler evaluates it -- not merely as an optimization, but so that static clients can use the results to implement useful compile-time behavior. For example, #assert can emit a compile-time error when its condition evaluates to false.

Compile-time evaluation of user code enables many clients (explored in the motivation section below), but tackling a complicated client would unnecessarily complicate this proposal. As such, here we focus on a trivial #assert feature as a first use-case that helps us develop the underlying mechanics. Other features described in the motivation section can be explored in future work.

Big picture: how constant expression evaluation works

Compile-time evaluation relies on an interpreter for a subset of Swift code, which operates on the SIL intermediate representation. The base level of this interpreter is hardcoded knowledge of the LLVM IR types (like Builtin.Int64) and instructions (like Builtin.add_Int64) we scope into our model.

The Swift standard library and user-defined types and operations (like the Int and Bool values used in the #assert example above) are abstractions built on top of this core calculus of LLVM primitives. As such, we expand our interpreter to handle specific language features (like let declarations, tuples, and fixed layout structs) and user abstractions (like user defined functions without looping). It is possible to scope many things into the model, but we start with a conservative set of features and future proposals can add more if/when there is a reason to.

To make it easy for users to understand what code runs at compile time, we introduce an attribute that marks functions that run at compile time, and we allow a specific well-defined subset of Swift within those functions. We also add a semantic analysis pass that checks marked functions and emits informative error messages when they use unsupported code.

Motivation

Constant expressions are an enabling feature of many high level capabilities. In order to keep this proposal small, we’ve picked one trivial application, but this section explores several possible (future!) applications of this feature:

Static Assertions

Swift's static types let the user rely on the compiler to catch certain kinds of errors at compile time. Static assertions allow the user to ask the compiler to catch a few new kinds of errors. Some common use cases for static assertions in other languages that support them (such as C++ and D) are:

// Ensure that data fits in a serialization format with limited space.
struct MyStruct {
  let x: Int
  let y: Bool
}

#assert(
  MemoryLayout<MyStruct>.size <= 16,
  "The serialization format only has 16 bytes for MyStruct.")

// Verify assumptions made by unsafe casting.
struct Foo {
  let x: Int
}
struct Bar {
  let v: Foo
}

func printFoosAsBars(foos: Array<Foo>) {
  #assert(
    MemoryLayout<Foo>.stride == MemoryLayout<Bar>.stride,
    "We assume that Foo and Bar have the same stride.")
  #assert(
    MemoryLayout<Foo>.size == MemoryLayout<Bar>.size,
    "We assume that Foo and Bar have the same size.")
  UnsafeBufferPointer(start: UnsafePointer(foos), count: foos.count)
    .withMemoryRebound(to: Bar.self, {
      for bar in $0 {
        print(bar)
      }
    })
}

Static assertions are the simplest possible application of constant expressions that we could think of, and we use them as the specific proposed client of them for this proposal only so we can focus on getting the core design of constant expressions right - without getting bogged down in the details of a complex client.

TensorFlow Operations

The Swift for TensorFlow Graph Program Extraction algorithm turns certain #tfop statements in Swift programs into "TensorFlow Graph Operations". Most details about how this works are not important to understand this proposal -- the relevant detail is that Graph Program Extraction needs to know values of certain #tfop arguments at compile time (e.g. the strides of a convolution) so that it can encode them in the graph operation.

With compile-time constant expressions, Graph Program Extraction can get the values of arguments that it needs and emit an informative error message if they are not constant. TensorFlow attributes support more types than we include in this proposal (they support integers, floating point, and string values, and arrays thereof) but we see this proposal as the first step towards being able to evaluate expressions of all the necessary types.

Value Parameters in Generics and Fixed Length Arrays

The Swift Generics Manifesto says:

Currently, Swift's generic parameters are always types. One could imagine allowing generic parameters that are values, e.g.,

struct MultiArray<T, let Dimensions: Int> { // specify the number of dimensions to the array
 subscript (indices: Int...) -> T {
   get {
     require(indices.count == Dimensions)
     // ...
   }
}

A suitably general feature might allow us to express fixed-length array or vector types as a standard library component, and perhaps also allow one to implement a useful dimensional analysis library. Tackling this feature potentially means determining what it is for an expression to be a "constant expression" and diving into dependent-typing, hence the "maybe".

Compile-time constant expressions allow the compiler to evaluate the values of generic value parameters, which is an important first step in allowing the type checker to check types involving generic value parameters.

Improvements to existing features

Swift has parts that could be improved with constant expressions:

Conditional compiler directives: Swift currently supports #if directives that allow users to conditionally compile things based on special-purpose conditions involving things like the target platform and compiler flags. With constant expressions, #if could support general conditions, and Swift would no longer need special support for special-purpose conditions for #if statements.

StaticString: A compile-time String expression (which we don't introduce in this proposal, but which could be added in later work) represents a String that is known at compile time. This could replace the special-purpose StaticString type that currently represents a String that is known at compile time. This simplifies the standard library by removing a type, and it also makes compile-time Strings more powerful: for example, "hello " + "world" is not a StaticString, but it could be a compile-time String expression.

Global constant initialization: Global variables are semantically always lazily initialized: every access does an atomic operation (implemented with something like pthread_once) to check if the global is initialized. This is silly for something like let foobarCount = 42. To offset this, the Swift optimizer has heuristics for promoting initializers to constants. These heuristics are currently very simple and they are also opaque to the developer. With constant expressions, we could chose to provide a model like @constexpr let foobarCount = 42 which reliably folds to a constant or produces an error if the initializer is not a constant expression. This would also allow later uses of foobarCount to be treated as a compile-time constant.

DiagnosticConstantPropagation Pass: This pass exists to generate compile time errors for obviously invalid code that would produce a runtime trap (e.g. let x: Int8 = 127+42). This pass is hard coded for a few cases, but a trivial generalization of the model proposed here would subsume this pass and allow it to be user extensible through arbitrary constant expressions. This would also allow us to statically diagnose failing assert() statements in constant expressions invoked with constants. These operations would not need to be marked @_transparent any more.

@_transparent attribute: The @_transparent attribute is a hack with poorly defined semantics, that exists primarily because of the DiagnosticConstantPropagation pass. Once this use has been eliminated, we are much closer to eliminating @_transparent entirely. We would probably have to introduce a first-class @nodebug attribute (analogous to the Clang nodebug attribute) to replace the remaining uses, but that would be much better defined than the existing @_transparent attribute.

Unreachable code diagnostics: Unreachable code is diagnosed with a simple pass that happens after mandatory inlining and DiagnosticConstantPropagation pass. Replacing DiagnosticConstantPropagation with something more general would increase the power of this diagnostic pass.

Other applications

If Swift eventually gets hygienic macro system, the macro system could use the ability to evaluate expressions at compile time.

Related Work

C defines integer constant expressions for expressions in contexts requiring compile-time integer values (e.g. the value of an enumerator). C compilers evaluate these expressions using hard-coded knowledge about how to represent intermediate integer results and how to perform operations on integers.

C++11 (and later) define a more flexible and user-extensible constant expression model that allows most of C++'s user-defined abstraction features (functions, classes, etc) to execute at compile time. Like C compilers, C++ compilers still need a core of hard-coded knowledge about primitive types and operations in order to operate on them at compile time, but they also know how to execute and instantiate user-defined abstractions like functions and classes.

D has Compile Time Function Execution, which can execute any D function at compile time, subject to a few restrictions on portability and side effects.

Proposed solution - Intuitive approach

We propose an interpreter that executes a subset of Swift code at compile time, during mandatory SIL passes. This interpreter keeps track of intermediate values using an algebraic data type (ADT) whose variants correspond to the types that the interpreter can operate on. We call these "compiler-representable types". The interpreter also emits informative error messages when the user asks for compile-time execution of code that the interpreter cannot handle.

To explain the interpreter, we provide a bottom-up intuitive explanation that starts with a trivial (and not very useful) programming model, and explains how the interpreter operates on that model. Then we incrementally build it up into a more full-featured model, describing how the interpreter changes to support the new features available in each step.

We cut off our buildup at a somewhat arbitrary point, to keep this proposal small. Future work can continue to increase the power of the model in service of specific clients that need that power.

A trivial programming model

Let's start with a programming model that only allows compile-time execution for functions that take no arguments and return builtin integer literals.

We require that users mark functions with a @compilerEvaluable annotation to enable compile-time execution. This makes compile-time executability part of the function's contract rather than an implementation detail, so that implementation changes don't accidentally break callers that depend on compile-time executability. @compilerEvaluable also turns on some checks and other features that we describe later in this section.

Here is an example (In the next few sections, pretend that users can write builtin integer literals like builtin_int64(100)):

@compilerEvaluable
func one() -> Builtin.Int64 {
  return builtin_int64(1)
}

Users may call these functions from anywhere in their normal code. We add a mandatory SIL pass "interpreter" that always folds calls to @compilerEvaluable functions. For example, after the SIL pass interpreter, print(one()) becomes:

%0 = integer_literal $Builtin.Int64, 1
... SIL that prints the contents of %0 ...

(Note that, while this does make the code faster, the optimization is not the main reason we are proposing this. The main reason we replace the call to one() with the resulting value is so that compile-time features, implemented in later SIL passes, can see the value and act on it.)

The interpreter operates by stepping through the function's SIL, keeping track of intermediate results using a representation of "compiler-representable types" that has one variant per builtin integer type. When the interpreter encounters an integer_literal instruction, it parses the literal and stores it as a value in its representation. When the interpreter encounters a return instruction, it halts interpretation and replaces the callsite with an integer_literal instruction corresponding to the returned value. When the interpreter encounters any other instruction, it emits an error stating that it encountered an unsupported instruction. The interpreter caches and reuses values.

We make @compilerEvaluable imply @inlinable for public and internal functions, so that the SIL interpreter can access the SIL for evaluating @compilerEvaluable functions defined in external modules.

We would like to provide informative error messages when users do forbidden things in @compilerEvaluable functions, even if they do not call the functions. This prevents them from accidentally publishing a @compilerEvaluable function that cannot execute at compile time. For example, because we do not (yet) support addition, this code would produce an error:

@compilerEvaluable
func badOnePlusOne() -> Builtin.Int64 {
  return builtin_int64(1) + builtin_int64(1)
  // error: operator '+' is not allowed in '@compilerEvaluable' functions.
}

To do this, we add a semantic analysis pass that checks all functions marked @compilerEvaluable. This semantic analysis pass first looks at the function signature and rejects functions that take arguments (we'll allow arguments later) and functions that return types that are not compiler-representable (now, only builtin integer types are compiler-representable). Then, it walks the function body's AST and checks all the nodes against a whitelist of nodes that are part of our allowed programming model (now, only return statements and builtin integer literals are allowed).

Adding operations on builtin integers

Let's allow users to perform certain LLVM IR operations on their builtin integer values. We'll allow:

• all the integer binary operations (add, and, or, mul, sdiv, srem, sub, udiv, urem, xor),
• all the integer binary predicates (cmp_eq, cmp_ne, cmp_sle, cmp_slt, cmp_sge, cmp_sgt, cmp_ule, cmp_ult, cmp_uge, cmp_ugt),
• all the integer cast operations (trunc, zext, sext), and
• all the integer castOrBitCast operations (truncOrBitCast, zextOrBitCast, sextOrBitCast).

Here is an example of a new thing that users can do with the model:

@compilerEvaluable
func onePlusOne() -> Builtin.Int64 {
  return Builtin.add_Int64(builtin_int64(1), builtin_int64(1))
}

To implement this model in the interpreter, we add hardcoded knowledge about how to fold these LLVM IR instructions.

To extend the semantic analysis pass to support this model, we make the semantic analysis pass accept calls to these builtins.

Tuples

Some of the LLVM IR operations used in the standard library's Integers.swift.gyb return tuples, and we'd like our programming model to support those, as well as user-defined tuple values. This requires our interpreter to represent and manipulate tuples. Therefore, we add tuples, tuple construction, and tuple extraction to our model. We also add the following LLVM IR operations that return tuples:

• all the integer binary operations with overflow (sadd_with_overflow, uadd_with_overflow, ssub_with_overflow, usub_with_overflow, sadd_with_overflow, uadd_with_overflow, ssub_with_overflow, usub_with_overflow),
• all the integer checked truncation operations (u_to_s_checked_trunc, s_to_s_checked_trunc, s_to_u_checked_trunc, u_to_u_checked_trunc), and
• all the integer checked signed <-> unsigned conversion operations (s_to_u_checked_conversion, u_to_s_checked_conversion).

Here are some examples of new things users can do with the model:

@compilerEvaluable
func oneAndTwo() -> (Builtin.Int64, Builtin.Int64) {
  return (builtin_int64(1), builtin_int64(2))
}

@compilerEvaluable
func three() -> Builtin.Int64 {
  return (builtin_int64(3), builtin_int64(4)).0
}

@compilerEvaluable
func onePlusTwo() -> Builtin.Int64 {
  return Builtin.sadd_with_overflow_Int64(builtin_int64(1), builtin_int64(2)).0
}

To extend the SIL interpreter for this model, we add a new tuple variant to the compiler-representable type ADT, and we teach the interpreter fold the tuple and tuple_extract SIL instructions. We also teach the interpreter to fold the new LLVM IR operations that we added.

To extend the semantic analysis pass for this model, we allow tuple construction and tuple access, and we allow calls to the newly allowed builtins.

Reading let-bound names

Our next extension is to allow let-bound names. For example:

@compilerEvaluable
func twoPlusTwo() -> Builtin.Int64 {
  let two = builtin_int64(2)
  return Builtin.add_Int64(two, two)
}

We do not need to extend the interpreter to allow this, because the SIL representation of let bindings is completely transparent to it.

To extend the semantic analysis pass to allow this, we allow let statements and declrefs to locally-bound names.

Function arguments

We would like to allow @compilerEvaluable functions to accept arguments. For example:

@compilerEvaluable
func add(x: Builtin.Int64, y: Builtin.Int64) -> Builtin.Int64 {
  return Builtin.add_Int64(x, y)
}

When the callsite passes literal arguments or arguments that come from other @compilerEvaluable functions, the SIL pass folds the call. For example, print(add(x: one(), y: builtin_int64(9)) becomes:

%0 = integer_literal $Builtin.Int64, 10
... SIL that prints the contents of %0 ...

To do this, the interpreter SIL pass repeatedly folds calls with known arguments and propagates constants, until there are no more foldable calls to @compilerEvaluable functions.

To extend the semantic analysis pass to support this, we allow functions to have arguments of compiler-representable type.

Function application

Let's allow users to call @compilerEvaluable functions from within other @compilerEvaluable functions. For example:

@compilerEvaluable
func addOne(x: Builtin.Int64) -> Builtin.Int64 {
  return add(x: x, y: one())
}

To implement this in the interpreter, we simply teach the interpreter to fold function calls by interpreting the called function. If the interpreter encounters a function call to a non-@compilerEvaluable function while interpreting a @compilerEvaluable function, it emits an error. We will add a recursion depth limit (e.g. 16). This prevents infinite compile time for cases of infinite recursion.

To extend the semantic analysis pass to allow this, we allow calls to @compilerEvaluable functions.

Structs

Structs are an important part of the type system, particularly for user visible types like Int and Bool. Let's allow users to instantiate and operate on structs at compile time.

To do this, first extend the definition of "compiler-representable type" to include structs whose fields all have compiler-representable type and whose layout is available at compile time. This includes builtin integers and tuples.

Next, allow users to mark initializers, methods, and getters on compiler-representable structs as @compilerEvaluable. Also implicitly mark the implicitly synthesized initializers and getters on compiler-evaluable structs as @compilerEvaluable.

For example:

struct Point {
  let x: Builtin.Int64
  let y: Builtin.Int64

  @compilerEvaluable
  func inFirstQuadrant() -> Builtin.Int1 {
    return Builtin.and_int1(
      Builtin.cmp_sge_Int64(x, builtin_int64(0),
      Builtin.cmp_sge_Int64(y, builtin_int64(0))
  }
}

print(Point(x: builtin_int64(10), y: builtin_int64(5)).inFirstQuadrant())
// The SIL interpreter pass evaluates the above print's argument to `builtin_int1(1)`.

print(Point(x: builtin_int64(-5), y: builtin_int64(10)).inFirstQuadrant())
// The SIL interpreter pass evaluates the above print's argument to `builtin_int1(0)`.

To implement this in the interpreter, we add a struct variant to the ADT of compiler-representable types. This variant has one field that stores the type of the struct, and one field that stores a list of compiler-representable values for the struct's fields' values. Then, we teach the interpreter to fold struct and struct_extract instructions.

To extend the semantic analysis pass for structs, we allow calls to @compilerEvaluable initializers, methods, and getters.

Standard library Bool and Int types

Note that the struct features from the previous section allow us to use the standard library's Bool and Int types in our programming model, because they are structs over builtin integers! All we need to do is to add @compilerEvaluable to some Bool and Int initializers and operators.

Here are some examples:

print(1 + 1)
// The SIL interpreter pass evaluates the above print's argument to `2`.

print(1 > 10)
// The SIL interpreter pass evaluates the above print's argument to `false`.

With our proposed implementation model, these will reliably fold to constants, even at -O0.

#assert

Now that we have Bool, we can implement a #assert feature that takes advantage of compile-time evaluation. #assert takes a condition expression of type Bool and an optional message string literal. It evaluates its condition at compile time, and emits an error message if the condition is false or if the condition cannot be evaluated at compile time. For example:

#assert(1 == 1)
// No-op.

#assert(1 == 2)
// error: static assertion failed.

#assert(1 == 2, "1 is not 2")
// error: 1 is not 2

#assert(promptUserForInt() == 2)
// error: 'promptUserForInt' is not a '@compilerEvaluable` function

We implement #assert by SILGen'ing SIL that extracts the argument's logic value and passes that value to a builtin "static_assert" instruction. Then, in a mandatory SIL pass that runs after the SIL interpreter pass, we eliminate all builtin "static_assert" instructions and emit errors for those with unknown condition and for those with 0 condition.

If statements and ternary operators

Let's allow if statements and ternary operators in @compilerEvaluable functions. For example:

@compilerEvaluable
func piecewiseLinear(x: Int) -> Int {
  if x < 10 {
    return x
  } else {
    return x + 10
  }
}

print(piecewiseLinear(x: 100))
// The SIL interpreter pass evaluates the above print's argument to `110`

To implement this in the interpreter, we teach it how to interpret cond_br instructions.

To extend the semantic analysis pass to support this, we allow if statements and ternary expressions.

Mutation

Some arithmetic operations in the standard library are implemented using mutation (for example, + is implemented in terms of +=), so let's allow mutation in @compilerEvaluable functions to enable those operations.

Specifically, we'll allow @compilerEvaluable functions to

• declare local vars,
• take inout arguments,
• assign to local vars,
• assign to inout arguments,
• apply @compilerEvaluable functions taking inout arguments to local vars, and
• apply @compilerEvaluable functions taking inout arguments to inout arguments.

We do not allow vars to escape, or be used in any other way.

Here are some example allowed mutations:

@compilerEvaluable
func set(_ x: inout Int, to: Int) {
  x = to
}

@compilerEvaluable
func five() -> Int {
  var x = 1
  x = 2
  set(&x, to: 5)
  return x
}

print(five())
// The SIL interpreter pass evaluates the above print's argument to `5`.

We will not execute mutations at compile time outside of @compilerEvaluable functions. For example, the SIL interpreter pass will not fold any part of the following code that's not in a @compilerEvaluable function:

var x = 1
set(&x, 2)
print(x)

The interpreter implements mutations by maintaining the state of the program, including stack-allocated mutable memory, while it is interpreting functions.

To extend the semantic analysis pass to support mutations, we allow:

• inout arguments in the function signature,
• var statements in the function body, and
• assignments to local vars and inout arguments in the function body.

Conclusion of build-up

We conclude our build-up here, because we can support basic standard library types and operations. Future work can continue the build-up when clients need support for more things.

Intentional limitation: Constant expressions of generic type

Consider:

func bad<T: Numeric>() {
  let x: T = 1
  #assert(x == 1)
}

The Swift generics model is based on the idea of separate compilation and dynamic implementation - it is not based on “template instantiation” like C++. So the compiler has no information about the implementation of T when it is compiling bad, and it cannot figure out what let x: T = 1 should do or what x == 1 should evaluate to. Therefore, the compiler will not compile bad.

This is intentional, we don’t see any way (given the Swift model for generics) that functions like bad can be supported.

Detailed Proposal

We describe the concrete capabilities this proposal includes. Future proposals can extend this to support other types (floating point, etc).

Compiler implementation

A new “constant expression folding” pass will be written and added to the mandatory pass pipeline right before the existing DiagnosticConstantPropagation pass (which we hope to eventually be subsumed). It replaces calls to constant expression functions with their result and eliminates the call. This happens even at -O0, providing predictable runtime performance for constant expressions at all optimization levels.

The existing EmitDFDiagnostics mandatory SIL pass will be enhanced to detect the condition of #assert operations, emitting an error if they fail, and removing them if they succeed.

Types

This model supports:

• builtin integer type
• tuples of compiler-representable types
• user-defined structs whose fields are compiler-representable types, which are defined in the current module or which otherwise have a known/fixed layout.
• metatypes
• addresses of stack objects

Builtin Instructions

The interpreter can fold the following builtin instructions:

• all the integer binary operations (add, and, or, mul, sdiv, srem, sub, udiv, urem, xor),
• all the integer binary predicates (cmp_eq, cmp_ne, cmp_sle, cmp_slt, cmp_sge, cmp_sgt, cmp_ule, cmp_ult, cmp_uge, cmp_ugt),
• all the integer cast operations (trunc, zext, sext), and
• all the integer castOrBitCast operations (truncOrBitCast, zextOrBitCast, sextOrBitCast).
• all the integer binary operations with overflow (sadd_with_overflow, uadd_with_overflow, ssub_with_overflow, usub_with_overflow, sadd_with_overflow, uadd_with_overflow, ssub_with_overflow, usub_with_overflow),
• all the integer checked truncation operations (u_to_s_checked_trunc, s_to_s_checked_trunc, s_to_u_checked_trunc, u_to_u_checked_trunc), and
• all the integer checked signed <-> unsigned conversion operations (s_to_u_checked_conversion, u_to_s_checked_conversion).
• sizeof, strideof, and alignof

Other SIL Instructions

The interpreter can also fold the following SIL instructions when their operands are representable by our constant model:

• tuple
• tuple_extract
• apply (as long as the function is @compilerEvaluable)
• struct
• struct_extract
• metatype
• cond_br
• alloc_stack
• dealloc_stack
• begin_access
• end_access
• load
• store

#assert

We define a new Swift statement #assert that takes a condition expression of type Bool and an optional message string literal. The #assert statement is SILGen’d to SIL that extracts the condition's builtin logic value, stores the message string (if present), and then passes the condition and message to a new builtin "static_assert". For example:

// SIL that computes the condition.
%condition = ...

// Extract the builtin logic value.
// function_ref Bool._getBuiltinLogicValue()
%1 = function_ref @$SSb21_getBuiltinLogicValueBi1_yF : $@convention(method) (Bool) -> Builtin.Int1
%2 = apply %1(%condition) : $@convention(method) (Bool) -> Builtin.Int1

// The message string.
%3 = string_literal "custom error message"

// Invoke the new builtin.
builtin "static_assert" %2 : Builtin.Int1, %3 : Builtin.RawPointer

The EmitDFDiagnostics pass eliminates static_assert builtins, so that later compiler passes do not have to deal with it. While eliminating static_assert, the EmitDFDiagnostics performs the following side effects:

• If it cannot determine the value of the condition, then it emits an error explaining why it cannot determine the value.
• If it determines that the value of the condition is 0, then it emits an error message. If a custom message is present, then the custom message is used as the error message. Otherwise, the error message is "static assertion failed".
• If it determines that the value of the condition is 1, then the static assert is successful, and the builtin is removed from the function.

@compilerEvaluable attribute

We require that users mark functions with a @compilerEvaluable annotation to enable compile-time execution. This makes compile-time executability part of the function's contract rather than an implementation detail, so that implementation changes don't accidentally break clients that depend on compile-time executability.

@compilerEvaluable implies @inlinable for public and internal functions, so that the SIL interpreter can access the SIL for evaluating @compilerEvaluable functions defined in external modules.

@compilerEvaluable also turns on a semantic analysis check that verifies that the function only uses features that can execute at compile time. This check verifies that the function signature only contains compiler-representable argument types and return types. This check also walks the function body's AST and verifies that it only contains whitelisted AST nodes. The whitelist allows:

• integer and boolean literals,
• return statements,
• all builtin instructions described in the Builtin Instructions section above,
• tuple construction and access,
• let and var statements,
• declrefs referencing locally bound names,
• function calls, for any @compilerEvaluable function whose SIL is statically available,
• struct member access,
• if statements,
• ternary expressions, and
• assignment to locally vars and inout arguments.

Interaction with requirements in generic code

Consider a generic function like this:

@compilerEvaluable
func mulAdd<T: Integer>(a: T, b: T) -> T {
  return a*a+b
}
#assert(mulAdd(4, 1) == 17)

As described above, our semantic analysis pass will evaluate the body of mulAdd and require that all code within it be foldable by the rules above. However, we have a problem: we don’t know if the * and + members in the Integer protocol are constant foldable without knowing that T is. In any given invocation of #assert, we will know the concrete type of T and will be able to determine this, but we cannot know this when type checking the mulAdd function itself.

This poses unfortunate tradeoffs. We see several possible solutions to this:

1. Eliminate @compilerEvaluable entirely, and forgo all static checking of constant expressions, deferring that checking to the interpreter (which is only invoked if a constant expression is actually used).
2. Make the static check verify all the obvious invariants, but assume that generic constraints are ok. If generic constraints are not ok in practice for a given call site, then the interpreter produces an error message so the issue is still caught.
3. Introduce significant extensions to the generics system to infer conditional conformance to “compiler evaluable” based on whether the conforming type has constant members that are compiler evaluable.
4. Make @compilerEvaluable an attribute that may be applied to protocol requirements, and pervasively spread it across the numeric protocols. This would preclude big integers from conforming, given that they have to do memory allocation and perform looping operations in general.

For this proposal, we recommend following approach #2. We don't recommend #1 because @compilerEvaluable is useful for implying @inlinable and for detecting certain classes of errors early. We don't recommend #3 because it's very big and complicated, and we don't recommend #4 because of the things it precludes. We are comfortable relaxing the semantic analysis check because the interpreter will catch the errors in all cases.

Source compatibility

This proposal is an additive feature that does not break existing code.

Effect on ABI stability

This does not affect ABI stability.

Effect on API resilience

Functions defined as @compilerEvaluable have the same API resilience restrictions as @inlinable functions. That said, @compilerEvaluable is a stronger guarantee (in the resilience sense) for a public function: in addition to promising a compatible implementation going forward, you would also be promising that future implementations of that API will not introduce non-constant expressions.

Alternatives considered

Here are a few alternatives we considered:

Eliminate the @compilerEvaluable attribute for functions

We don't need a @compilerEvaluable attribute on functions that get executed at compile time. We could allow any function to execute at compile time as long as it meets the requirements for a @compilerEvaluable function.

The advantage of removing the attribute is that you don’t get the attribute added to lots of functions. However, the attribute provides several important benefits:

1. It catches user errors in functions-intended-to-be-constants without requiring a caller to invoke them.
2. It prevents action-at-a-distance behavior where adding non-constant code to a function deep within a call chain breaks a distant caller that requires it to be constant.
3. The resilience contract of a public constant expression function is a stronger guarantee that of a normal public inlininable function: you are promising not to add non-constant code into its body in future revisions of it.

As such, we feel that the attribute is an important and meaningful marker.

Name the @compilerEvaluable attribute something else

Other names could include @constantFoldable, @constant, @constantExpression or something else.

Evaluate the AST instead of the SIL

Instead of interpreting SIL, we could interpret the AST. An advantage of this approach is that it evaluates values earlier during compilation, allowing more compiler passes access to the values. For example, if we interpret the AST before type-checking, then we can use the values during type-checking, which makes the type-checking strategy described in the Generic Value Parameters section easier to implement.

We rejected this approach because the SIL generation pass does work that makes SIL easier to interpret than the AST. If we interpreted the AST, then we would be duplicating this work.

Fully compile the expressions and evaluate them on the machine

Instead of implementing an interpreter in the compiler, we could extract code that needs to be evaluated at compile time, compile it, execute it, and then use the results of the execution.

We rejected this approach because it adds more moving pieces, makes the compile-time evaluation mechanism more complicated, and would make the compiler slower and use more memory.