Escaping objects and what is escape analysis modelling anyway?

[Richard Andrew Cattermole (Rikki)]

Another year has passed where people have felt the need to use 
DIP1000 in projects.
So I want to go over some important details of what escape 
analysis is trying to model, and what DIP1000 is trying to model.

But first we need to go over some basic terminology.
First a memory allocation is called an object.
This could be the stack or heap; but ultimately it doesn't matter 
what the memory allocator was used to do the allocation.

Second, we need to identify locations in memory that can hold 
values (whatever that may be), this could be a stack variable, a 
field in a class, or even an element in an array.
This is called a cell; it's all about storage locations for 
values.
All objects are cells, but not all cells are objects.
Not all objects have cells as children either.

The following description is based upon my study of escape 
analysis, design work and current implementation work of 
introducing escape analysis into the fast DFA engine.
It is currently waiting on being 
[merged](https://github.com/dlang/dmd/pull/23314) and has been 
completed for a little while now.
However, I haven't really put together a good description in the 
changelog entry, and a good reason for this is that it isn't 
supposed to require you to understand it.
If it requires attributes for normal code, I've failed and need 
to fix the engine.

Escape analysis is formed from the basis of points-to and 
dependency analysis.
Points-to analysis is used for modelling the stack variables 
within a function body, it allows finding what out what a pointer 
stored in one points at.
For example, another stack variable.
It is used for null pointer dereference detection.

For example, the following code can error with points-to analysis:

```d
void checkViaObjNullDeref(bool cond, int** ptrArg) @system
{
     int* var;
     int** ptr = cond ? &var : ptrArg;
     **ptr = 2; // error
}
```

Dependency analysis goes a step further than points-to analysis.
It can track that one object stored in a cell relates to another.

For example, we can see that the return value is dependent upon 
the parameter's object:

```d
int** grab(int* param)
{
     int** obj = new int*;
     *obj = param;
     return obj;
}
```

The information gained from inference gets serialized down to a 
compact form that can be stored at a function level.
This information may not be so simple that it may be represented 
with attributes like D has.
For this static analyzers may use a dedicate file format to 
communicate this information between compiler calls.

An example of this is you can utilize conditionals to model 
relationships:

```d
int* returnCond(bool cond, int* obj)
{
     if (cond)
         return null;
     else
         return obj;
}
```

So this could have a graph that looks like:

```
[
     ( if (params[0] == true)
         return = null
     ),
     ( if (params[0] == false)
         return = params[1]
     )
]
```

This isn't some unlikely-to-exist feature for D either; it's a 
very real possibility that D may need to gain this to model 
inline declarations of variables within function calls:

```d
if (tryGet(int i))
```

C# has implemented this back in 2019 to model the TryGet pattern. 
[``[NotNullWhen(true)] out string? 
message``](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/attributes/nullable-analysis#conditional-postconditions-notnullwhen-maybenullwhen-and-notnullifnotnull)
Naturally, I'm not keen on adding this when there is an 
alternative design that doesn't require it.

So far the examples are quite simple, but how do we differentiate 
the relationship between all the objects involved in a function 
call?
Do the following functions have the same relationship between 
their function parameter and return value?

```d
int** rel1(int** param) => param;
int** rel2(ref int* param) => ¶m;
```

Yes and no.
A big part of the problem here is `rel2`, you can look at it and 
think oh I know it's got two cells, just like `rel1`!
And that is true as far as what you should have access to.
But its not; it's actually the same parameter as the first 
`rel1`, but you've specified that the first indirection is 
guaranteed to be non-null and should be ignored.
This gives you three cells, with the first being hidden to the 
user, and the second being automatically dereferenced.
That is storage of the parameter, pointer to `int*` that was 
passed in, and then the `int*` itself.

Knowing this allows us to model function calls of functions like 
these and know that the assert will hold true during compilation:

```d
int* var;
int** ptr = rel2(var);

assert(&var is ptr);
```

This is a particularly useful bit of information, but sometimes 
we don't want an identity function, but want to return what was 
contained within that object.

```d
int* rel3(ref int* param) => param;

int* var = new int;
int* ptr = rel3(var);

assert(var is ptr);
```

That is not the same relationship as say `rel1` or `rel2`.
Remember the big three cells that I just mentioned?
"That is storage of the parameter, pointer to `int*` that was 
passed in, and then the `int*` itself."
Well, that is a tad important; see before we were dealing with 
the second cell, now we are onto the third.

So what these three cells actually represent when deconstructed:

1. Stack variable that holds a value.
2. Pointer that was passed in and stored in the stack variable.
3. Pointer that can be accessed by performing a dereference on 
the stack variable.

And you know what? That third one doesn't have to be a pointer, 
it could be a struct for all we care about.

Pragmatically, this tells us what we need to model in an escape 
analysis solution.
We need to model the following scenarios:

1. We are escaping stack memory to an output location.
2. We are escaping an object that was passed in to an output 
location.
3. We are escaping an object acquired from an object that was 
passed in but is not the input, to an output location either 
directly or indirectly.

```
[ CELL 1 ]                       [ CELL 2 ]                       
[ CELL 3 ]
+------------------------+       +------------------------+       
+------------------------+
| Storage Location       | ----> | Pointer / Reference    | ----> 
| Pointed-to Payload     |
| (Stack Frame / Slot)   |       | Value                  |       
| (Primitive / Struct)   |
+------------------------+       +------------------------+       
+------------------------+
   Parameter storage                First indirection              
   Second indirection
```

By knowing if it is two or three, that tells us whether to 
activate the first error up the call stack.

```
[ caller frame ] ──(passes &localPtr)──► [ rel2(ref int* param) ]
        │                                         │
        │                                         │ Returns Cell 2 
(&param)
        ▼                                         ▼
    [ ERROR: Cell 2 points to stack slot of localPtr in caller ]

[ caller frame ] ──(passes &localPtr)──► [ rel3(ref int* param) ]
        │                                        │
        │                                        │ Returns Cell 3 
(param)
        ▼                                        ▼
    [ PASS: Cell 3 payload is Heap / Unrestricted Lifetime ]
```

Now DIP1000 tried to model exactly this, but it got it pretty 
badly wrong.
The `rel1` and `rel2` have two separate attributes `return` and 
`return ref`.
And `rel3` has another `return scope ref` on top of that.

When really the differentiation is just: "am I returning the 
outermost object?"

This is not the only issue with DIP1000, but it's a pretty big 
one.
That has led to the D community not understanding how or why 
DIP1000 works the way that it does.
It's not how the attributes are presented; it's what the 
attributes are representing.

I have and continue to call the differentiation between two and 
three "relationship strengths".
There is another that we need, and it's to activate a borrow 
checker.

Hopefully this explanation helps people to understand how and 
what escape analysis is supposed to be representing.
It's not a particularly easy subject to get into, but yet 
everyone learns this stuff implicitly when using D.

P.S.
We can thank Gemini for the help with the ASCII diagrams, I'm 
terrible at it.