noalias on all parameters by default (with debug safety); ability to specify mayalias

[andrewrk]

I'm extracting this (flawed) proposal out of #733.

• Add mayalias keyword
• Remove noalias keyword
• mayalias valid only on a pointer parameter. It means "may be aliased by global variables or other arguments to this function which are mutable pointers"
• Debug safety
  • At the beginning of each function, verify that no mutable pointers with known sizes (*T, *[N]T, and []T) overlap with each other, or with any const pointers with known sizes
• In Zig IR, pointer values track the set of noalias parameters and global variables possibly referenced
  • slice and getelementptr instructions that include a noalias var of
    unknown len ptr in the set do a safety check to find overlap
• When generating LLVM,
  • load instructions based on const ptr noalias variables !alias.scope
    a scope unique to the function but shared by each other (the function's
    const ptr alias scope)
  • load instructions based on mut ptr noalias variables !alias.scope
    a unique scope per var
  • Store instructions based on noalias variables !noalias all the
    function's noalias var scopes they are not based on, and the function's
    const ptr alias scope
• Verify that LLVM can take advantage of these annotations

Depends on #561 so we can put llvm parameter attributes on slice pointers

This proposal needs work. Consider this example:

const Context = struct {
    // some useful fields, and then
    preallocated_point: Point,
};

const Point = struct {
    x: i32,
    y: i32,
}

fn incrementXAndPrint(self: *Context, pt: *Point) {
    pt.x += 1;
    self.log("point: {v}\n", pt);
}

test "aoeu" {
    var c = Context {
        .preallocated_point = Point { .x = 0, .y = 0 },
    };
    incrementXAndPrint(&c, &c.preallocated_point);
}

This would trigger the proposed debug safety but it does not actually represent problematic behavior, since the value is never accessed via the other pointer.

One proposal adjustment could be to do all the runtime safety only at store instructions for everything. I fear this would be too slow in practice, however it is worth experimenting with before shutting the idea down. I'll first verify that LLVM would be able to take advantage of these annotations though.

[andrewrk]

Related: #476

[daurnimator]

I'll first verify that LLVM would be able to take advantage of these annotations though.

It is, but there have been some issues. It looks like rust currently has related optimizations disabled due to rust-lang/rust#54878

[daurnimator]

• mayalias valid only on a pointer parameter. It means "may be aliased by global variables or other arguments to this function which are mutable pointers"

What if you could provide a list of variables that it might alias?

[JesseRMeyer]

What if you could provide a list of variables that it might alias?

This was essentially how GCC leveraged unions to specify semantics of aliased data operations, see https://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html#union_1
https://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html#union_2
and perhaps more importantly (which demonstrates an invalid method, as of the time of the last update to the article):
https://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html#union_3

We could piggyback on union semantics for this by introducing a new kind of union, an alias. If you want restricted pointer semantics, use an alias.
However, a mayalias keyword would be very handy when interfacing with imported C code though.

[JesseRMeyer]

I took the opportunity to translate the 'Benefits to The Strict Aliasing Rule' C example into Zig on Godbolt here, https://godbolt.org/z/r3dhdo.

Notice that LLVM always reloads the memory at uniform.*.b with movzx ecx, word ptr [rsi + 2] inside the loop body instead of hoisting the load up out of the body to occur once. This is sub-optimal if values and uniform never overlap in memory in the loop.

It's a bit harder to understand the output with --release-fast, although the compiler seems to generate a few different loop structures based on how many elements could be processed in wider SIMD units per iteration. This implies the aliasing semantics between --release-fast and --release-safe are currently different.

[matu3ba]

One proposal adjustment could be to do all the runtime safety only at store instructions for everything. I fear this would be too slow in practice, however it is worth experimenting with before shutting the idea down. I'll first verify that LLVM would be able to take advantage of these annotations though.

The LLVM patch for full noalias optimization is a quite big one and not yet upstream.
I would however consider this more of a safety feature as know exact and fast which types overlap.

Also look at a Rust example.

By the way, noalias might not be enough. But that is to come after noalias and restrict lands in LLVM.

Related discussion on rust issue

[SpexGuy]

Would this apply to pointers inside structs? For example, if I pass a parameter of type struct{ a: [*]u32, b: [*]u32 }, are those pointers (and derived pointers) allowed to alias? There's no way to attach mayalias to one pointer but not the other.

[matu3ba]

@SpexGuy Restrict only defines the pointer relation as being uniquely pointing to an object o1. If the object contains further pointer, they are free to alias other objects o2..on (but not o1).

Two pointers pointing to the same object are by construction forbidden, but I dont understand how your struct is assumed to be used.

An object means always a continuous chunk of stuff, so you will have the base address and length known at comptime in the typesystem.

[matu3ba]

@andrewrk This breaks on the LLVM side, if one does anywhere unchecked pointer arithmetic relying on LLVM to figure out pointer provenance. The suggested linear memory model might fix this, but could require new methods.

see here

I guess zig assumes a linear memory model?