Syntax for caller-visible stack setup

[dmchurch]

This is an alternate (but non-conflicting) solution for the coding problem that inspired #8156. In that issue, I mention that adding out parameters to a method is nearly cost-free in terms of performance. This proposal, on the other hand, is completely cost-free in terms of performance.

The core idea is that, just as you can annotate a local variable declaration in a method with a ref keyword, you will be allowed to annotate with the out keyword instead. The semantics for a local variable declared as out are as follows:

• The variable must be declared at the top level of the method (not within a loop, conditional, or block). It can be declared anywhere in the function, but code style should be that all out-declared variables be at the top.
• The IL stores information (name and location) about all declared out variables for a given method, but they do not contribute to overload resolution - in other words, they aren't part of the method's signature. Since local variables aren't allowed to shadow the names of parameters, these will be guaranteed to be distinct from all parameter names (but see below for special syntax around that).
• When invoking a method with out locals, the callsite may use named argument syntax to declare an out argument with the name of one of these out locals, with one additional restriction: the argument must use the variable declaration form. In other words, it must be out TypeName explicitlyTypedVariable or out var implicitlyTypedVariable, not out existingLocalVariable.
• During codegen, if the invocation is not inlined, the invoked method will allocate any out variables as high in the stack as possible - likely just below the return address. The calling method can then use the value of the variable after the call has returned, just like with out parameters. Since it is the invoked method that determines the contents and layout of this caller-visible stack area, it can use these caller-visible stack addresses the same way it can use any stack variable, without an additional layer of indirection. If the caller wishes to use those variables even past another method call, it can either copy them into its own stack frame or simply extend its own stack frame to encompass them, after the call returns.

In this scenario, a change that adds an out variable to a method is source-compatible, IL-compatible, and even binary-compatible, as the method's calling convention does not change at all.

One other possible addition to this protocol would be to allow an out-declared local variable with no initializer to share a name with a mandatory or optional parameter passed by value. This would allow for both passing a variable in and capturing any mutations performed on the parameter by the invoked method. For syntax, I'd recommend using the syntax ref TypeName varName = value in the argument position when specifying the input value, or out TypeName varName in the argument position if the parameter is optional and the input value is omitted. Since this can cause the invocation to match a different method overload, an alternate syntax should also be supported, like specifying the argument twice (once by position or named to provide the input value without any ref or out, and the second by named argument using out TypeName varName syntax).

I would not recommend allowing this syntax on virtual methods, including those defined as part of an interface. This functionality can only be used for methods whose actual implementation can be determined at compile-time.

A modification of the CaseInsensitiveOrderPreservingStringDictionary from #8156 to use caller-visible stack variables rather than optional ref/out parameters would be as follows:

public class CaseInsensitiveOrderPreservingStringDictionary<TValue>
{
    private List<string> keys = new();
    private List<TValue> values = new();

    public int Count => keys.Count;

    // A reference to a dictionary location that has just been looked up, can index this dictionary
    public readonly ref struct Slot
    {
        public required readonly string Key { get; init; }
        public required int Index { get; init; }
        public bool HasValue => Index >= 0;
    }

    public TValue this[string key]
    {
        get => TryGetSlot(key, out Slot slot) ? GetFromSlot(slot) : throw new KeyNotFoundException();
        set => this[GetSlot(key)] = value;
    }

    public TValue this[Slot slot]
    {
        get => GetFromSlot(slot);
        set => SetFromSlot(ref slot, value);
    }

    public bool ContainsKey(string key, int index = 0)
    {
        // declaring both parameters as ref-able
        out var key, index;
        GetSlot(ref key, ref index).HasValue;
    }

    public bool TryGetValue(string key, out TValue value)
    {
        // The key parameter is ref-able
        out var key;
        // The slot variable is out-able
        out Slot slot;
        GetSlot(ref key, out slot);
        if (slot.HasValue) {
            value = this[slot];
            return true;
        } else {
            value = default;
            return false;
        }
    }

    public bool TryAdd(string key, TValue value)
    {
        out var key, value;
        out Slot slot;
        GetSlot(ref key, out slot)
        if (!slot.HasValue) {
            SetFromSlot(ref slot, value);
            slot = targetSlot;
            return true;
        } else {
            value = GetFromSlot(slot);
            return false;
        }
    }

    public bool TryGetSlot(string key, out Slot slot, int index = 0)
    {
        out var key, index;
        slot = GetSlot(ref key, ref index);
        return slot.HasValue;
    }

    protected Slot GetSlot(ref string key, ref int index = 0)
    {
        key = key.ToLowerInvariant();
        index = keys.IndexOf(key, index);
        return new Slot
        {
            Key = key,
            Index = index,
        };
    }
    protected TValue GetFromSlot(Slot slot)
    {
        return slot.HasValue ? values[slot.Index] : throw new KeyNotFoundException();
    }
    protected void SetFromSlot(ref Slot slot, TValue value)
    {
        if (slot.HasValue) {
            values[slot.Index] = value;
        } else {
            slot = slot with { Index = Count };
            keys.Add(slot.Key);
            values.Add(value);
        }
    }
}

[HaloFour]

I really don't understand what this proposal is attempting to achieve, but the notion that somehow a local can silently leak to the outside scope and somehow not impact the signature of the method is very unappealing to me. I don't even understand how such a thing would be achieved. Either the ref is exposed from the method and thus is a part of the signature, or it's not.

Also, inlining and assumptions about the interactions between methods bodies is something the compiler very explicitly doesn't get involved with. Every method is opaque and the IL represents the intent of the code, it doesn't shuffle stuff around for the sake of optimization because the compiler never has the full picture to do so. Inlining and the like is a runtime concern.

[dmchurch]

"return a buffer that may be allocated in the callers stack space"

This isn't quite it - this isn't about returning allocated memory, but about returning values (which, yes, may be reference types, but wouldn't include stackalloc'd buffers, which would be illegal to return even in an out local, I think). This comment has I think my best description of the problem space, but I suppose I could summarize it as "it allows methods to return values, including structs and ref structs larger than sizeof(nint), without incurring a copy". The core innovation is in providing a sufficiently-restricted reference-sharing mechanism (at the high level) that a calling method can safely (and provably) interrogate and potentially adopt the stack frame of a just-returned invocation (at the low level). That's why I initially termed it "caller-visible stack setup".

[tannergooding]

Returning values is already possibly via T M() or out T if you need to return multiple. This is already the most optimal way to return values and avoids needing a custom ABI per method (which would hurt performance and the ability for the register allocator to do its job).

out T gives you direct access to the location and allows you to avoid the copy. But that copy is also typically non-expensive in the first place and may be more desirable than repeated access to the memory location in the case you're doing many manipulations or setting and then repeatedly reading the value.

T returns are already in register (depending on ABI) for sufficiently sized value types and otherwise are already handled via an implicit return buffer (basically a hidden out T result) parameter.

[dmchurch]

Returning values is already possibly via T M() or out T if you need to return multiple.

Agreed, though I'll note that T M() is kinder to the called procedure than out T - with T M(), the method doesn't even have to spill the result to memory if it doesn't want to (and if T is small enough). With out T, it will always be a reference, which means the called method's asm will always be indirect and it will always be storing to memory (if this method invocation is emitted as a function call rather than an inline).

If you want to return values T, U, and V, though, then (T, U, V) M() isn't fantastic - again, in the case that the method becomes a procedure call. (T, U, V) implies a storage layout, which means - again, since returns are going by the system ABI - that in practice, you can never return more than two ints from a method without spilling into the stack.

By contrast, out locals explicitly don't define a memory layout; two of them could be returned in registers, and one in the stack, or whatever combination. It doesn't require supporting multiple ABIs, because out locals always use whatever registers and/or memory are left over by the ABI. A native-to-managed call to a method with out locals conforms to the appropriate native ABI; it's just that the native code won't be able to use the out locals. (It'd have to call to a managed trampoline, first, which could return them in a more traditional fashion.)

handled via an implicit return buffer (basically a hidden out T result) parameter

Yes, but so far as I've observed, the runtime won't write to the return buffer until the return statement is encountered - which means that return-by-value for larger structs always involves a copy, from the method's local stack variables, and that the stack + return buffer is always twice the size it needs to be, since the lvar of the struct is in a separate memory space than the result buffer. Return-by-out-local avoids making that copy by simply guaranteeing that the result will be in a predictable location relative to the stack pointer after return from the procedure call, and the runtime can emit static offset opcodes since it knows, at the time it's compiling the calling method, what the realized out-local addresses/registers are for the called method. And if the method wanted to return a 1024-byte struct, by value, as an out local, it could simply spill it to the top of the frame, the caller could extend its stack by 1k upon return, et voilà, now the calling method owns that 1k struct. Zero runtime cost.

[ETA: if the out local mechanism were implemented, there's no reason the runtime couldn't use the out local plumbing in order to opportunistically rewrite return-by-value methods to use the same zero-copy mechanism, in the case of managed-to-managed calls.]

[tannergooding]

With out T, it will always be a reference, which means the called method's asm will always be indirect and it will always be storing to memory (if this method invocation is emitted as a function call rather than an inline).

Yes, which is a requirement in order to meet the platform ABI and ensure the register allocator can do its job. While you could say "this method has a custom ABI and also uses r8 to return a second result", that is overall worse for performance in the typical case.

Spilling to the stack is not a problem, especially for almost any CPU that's shipped in the past 14 or so years. CPUs have long had support for "mirroring" stack spills into part of the internal register file set and avoid actually accessing memory unless it's truly required (because something goes and tries to actually mutate stack space it shouldn't be touching).

Yes, but so far as I've observed, the runtime won't write to the return buffer until the return statement is encountered - which means that return-by-value for larger structs always involves a copy,

There are several cases it can, but yes in general it will copy, which isn't an issue in the vast majority of code and helps keep semantics and observability of the mutation well-formed. For some cases, the JIT handling could just be better improved and then it wouldn't be an issue.

And if the method wanted to return a 1024-byte struct, by value, as an out local, it could simply spill it to the top of the frame, the caller could extend its stack by 1k upon return, et voilà, now the calling method owns that 1k struct. Zero runtime cost.

This doesn't work due to the caller's return address and stack pointer existing between the callee and caller's stack space.

---

In general what you're trying to go for here is something which is overall going to be worse for performance, not better. There's a reason that even native C/C++ compilers don't typically do these types of things.

The natural code is typically the best code, especially over time.

[dmchurch]

In general what you're trying to go for here is something which is overall going to be worse for performance, not better.

Okay, understood! I think I've communicated the idea well enough that if you think it's a non-starter, then the smart bet is that it is - you are the expert here, after all. That's good enough for me, I have no desire to go digging around in codegen to make a POC if it's not gonna be worthwhile. 😄

Thank you so much for taking the time to look at this and think on it! I really appreciate it.

[CyrusNajmabadi]

Thanks for bringing the discussion back to a friendly and constructive place :)