# \[MIR\] constant evaluation

**URL:** <https://internals.rust-lang.org/t/mir-constant-evaluation/3143>\
**Category:** compiler\
**Created:** [February 2, 2016, 12:48pm UTC](https://internals.rust-lang.org/t/mir-constant-evaluation/3143 "2016-02-02T12:48:22Z")\
**Posts on this page:** 1\
**Showing post:** 31

<div class="post-metadata">

**Author:** ![eddyb](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/eddyb/32/8411_2.png) [@eddyb](https://internals.rust-lang.org/u/eddyb)\
**Post date:** [February 10, 2016, 7:35am UTC](https://internals.rust-lang.org/t/mir-constant-evaluation/3143/31 "2016-02-10T07:35:48Z")

</div>

I’m sorry for being late to this discussion, given that @nikomatsakis and I have gone over this in slightly more detail that is available here.

I mostly agree with @matthieum in that allocations are more useful than full-blown IO, but there is a deeper issue: **purity**.

To be able to use `const fn` with the typesystem (i.e. `[T; ctfe()]`), `const fn` functions must be _pure_, in the sense that repeated calls with identical arguments must produce identical results.

While it may be possible to design a system where impurity _cannot_ affect type safety, it’s a non-goal for Rust 1.x.

As for claims of complexity, a MIR interpreter capable of evaluating everything _but_ impure/IO code should be simpler than the MIR -\> LLVM IR translator and a LLVM JIT/interpreter, and cleaner than the current constant folder (which has been getting better, thanks to @ker).

@scott has started work on an [out-of-tree prototype named `miri`](https://github.com/tsion/miri/blob/master/src/interpreter.rs), which reassures me that MIR is great for tooling and that we can do a lot with an order of magnitude less code than, say, the name resolution pass.

Without further ado:

### Rust/CTFE Abstract Machine

A proper subset of the Rust Abstract Machine, restricted to deterministic reproducible evaluation.

That is, only `const fn` functions may be called, which are required to always return structurally equivalent values and produce the same writes to memory reachable by arguments, given structurally equivalent arguments.

C functions are _never_ `const fn`, as the above property (also referred to as _purity_) cannot be enforced, although a C-to-Rust transpiler could fill in that gap.

Writes to `static` (global) memory and inline assembly are also prohibited, and compile-time pointers do not have observable addresses.

The CTFE capabilities offered are similar to those found in C++14 constexpr.

#### Data layout

The machine works with octets as its fundamental unit of measurement (for sizes, alignments and offsets), which will henceforth be referred to as _bytes_.  
It’s parametrized by the target architecture’s _data layout_, which consists of:

- endianness (the order of bytes in a multi-byte integer value)
- size of pointers and `usize`/`isize`
- alignments of all primitive types

Based on the machine _data layout_, the layout (size, alignement and field offsets) of aggregate types can be determined.  
The layout of non-`#[repr(C)]` aggregates is implementation-dependent.

#### Primitive types

Boolean, C-like `enum`, character codepoint, integer and floating-point values will be represented as exactly one valid value in their respective representable range.

Addresses (pointers, references, all non-local lvalues) will be one of:

- integer addresses: `x: usize` in `(x as *T)`.  
Cannot be read/written through, but other operations do work (on the integer value), e.g.:

```rust
&(*(0 as *const Struct)).field as *const _ as usize

```

- abstract locations: `(region, x: usize)` in `region.offset(x)` with `x < region.size`.  
Can be read/written through, except for writes to `static` (global) memory.  
Can only be compared with another abstract location from the same abstract memory region (the offsets are compared).  
No bits of a pointer holding an abstract location may be observed as any other type than a pointer, for which the whole value must be used.

#### Abstract memory region

A contiguous block of memory with a fixed size, consisting of `size` constant bytes and a set of non-overlapping special values (undef bytes and relocations).

Undef bytes can be found in uninitialized memory (e.g. `mem::uninitialized()`) and are also produced by writing an aggregate, at positions not covered by leaf fields (i.e. padding bytes).

Reading undef bytes is prohibited, as code that does this is likely to exhibit undefined behavior at runtime.  
Aggregate reads side-step this by only reading bytes covered by leaf fields.

Primitives are read/written at the byte level, and the combined bit pattern must represent a valid value (`transmute` is no different).

For non-pointer primitives, none of the bytes read may overlap with a relocation.  
For pointers, either:

- None of the bytes read overlap with a relocation, producing an _integer address_.
- The entire pointer aligns perfectly with one relocation, producing an _abstract location_, where the constant bytes gives the offset, and the relocation gives the abstract memory region it’s pointing into.

Writing over a relocation is only permitted if the entire relocation is written over in the same operation, replacing it (e.g. a 32-bit pointer relocation can be written over with `*mut T`, `u32` or `(u16, u16)` but not two `u16` writes).

To give an example, the following two abstract memory regions would be produced to hold `&[(0u8, 1u16), (2, 3)][1..]`, for a little-endian target with 32-bit pointers:

```rust
Region A:
Data: 04 00 00 00 01 00 00 00
Special: └──Reloc(B)──┘

Region B:
Data: 00 00 01 00 02 00 03 00
Special: Undef Undef

```

#### Dynamic memory allocation (optional)

An implementation can provide intrinsics to allocate new abstract memory regions, deallocate them (invalidating dangling references and preventing further uses) and resize them (which can always be done “in place”).

Special care must be taken to ensure that values of types that administer such memory (`Box`, `Vec`, `String`, etc.) do not escape into runtime code while holding a pointer to an abstract memory region.

The implementation can generate runtime allocations from abstract memory regions when a `const` item “owns” the allocation, although this alone is not enough to get e.g. a `&'static str` from `String` CTFE.

_EDIT: discussion resulted in the addition of the paragraphs below:_

All abstract memory regions reachable from a `&'static T` can be placed in static memory, with the same restrictions as borrowing in a `const` item (no `UnsafeCell`), e.g.:

```rust
const WORKS: &'static str = &5.to_string();
const WORKS2: &'static str =
    Box::leak(5.to_string().into_boxed_str());

const FAILS_OLD: &'static AtomicBool =
    &AtomicBool::new(false);
// Arc uses 
const FAILS: &'static Arc<i32> = &Arc::new(0);

```

No runtime allocations shall be used, only read-only static allocations. `static` items could also be extended to allow thread-safe shared data, e.g.:

```rust
static FOO: Arc<Foo> = Arc::new(Foo {...});

```

One could only increment and decrement the refcount of `FOO`, but it would never go below 1, so the allocation being in `.data` would not be an issue.

The `UnsafeCell` is more subtle, though, as the following also needs to be forbidden:

```rust
static GOOD: Arc<Mutex<String>> =
    Arc::new(Mutex::new(String::new()));
static BAD: Arc<Mutex<String>> =
    Arc::new(Mutex::new(String::from("foo")));
...
mem::replace(BAD.lock(), String::new())

```

Now you have a runtime String pointing to .rodata.  
The root of the problem is a “dynamic” abstract memory region being pointed to from memory owned by the `UnsafeCell<String>` instance.

I believe we can detect that by finding “mutable ranges” based on the types used to access a memory region.

That does mean, though, that unsafe abstraction providing `const fn` facilities has to be extra careful: keeping track of an allocation with `*mut u8` instead of `*mut T` may prevent the compiler from detecting `UnsafeCell`.

We can warn about pointers not reflecting the full size of the allocation they point to (but this breaks `Vec`, unless that starts using `*mut [T]` instead, which we might want to do anyway, e.g. to support `Vec<DST>`), and only point to `.rodata` in those cases, which would result in page faults instead of unsafety.

The other danger I can see here is querying jemalloc for some information about the allocation of a `String` and failing (Servo does something like this, cc @Manishearth).

---

_[View the full topic](https://internals.rust-lang.org/t/mir-constant-evaluation/3143)._