Is it possible to statically predict when to deallocate memory---from source code only?

Question

Memory (and resource locks) are returned to the OS at deterministic points during a program's execution. The control flow of a program by itself is enough to know where, for sure, a given resource can be deallocated. Just like how a human programmer knows where to write fclose(file) when the program is done with it.

GCs solve this by figuring it out directly during runtime when the control flow is executed. But the real source of truth about the control flow is the source. So theoretically, it should be possible to determine where to insert the free() calls before compilation by analyzing the source (or AST).

Reference counting is an obvious way to implement this, but it's easy to encounter situations where pointers are still referenced (still in scope) yet no longer needed. This just converts the responsibility of manually deallocating pointers to a responsibility to manually manage the scope/references to those pointers.

It seems like it's possible to write a program that can read a program's source and:

1. predict all the permutations of the program's control flow---to similar accuracy as watching the live execution of the program
2. track all the references to allocated resources
3. for each reference, traverse the whole subsequent control flow in order to find the earliest point that the reference is guaranteed to never be dereferenced
4. at that point, insert a deallocation statement at that line of source code

Is there anything out there that does this already? I don't think Rust or C++ smart pointers/RAII is the same thing.

Answer 1

Take this (contrived) example:

void* resource1;
void* resource2;

while(true){

    int input = getInputFromUser();

    switch(input){
        case 1: resource1 = malloc(500); break;
        case 2: resource2 = resource1; break;
        case 3: useResource(resource1); useResource(resource2); break;
    }
}

When should free be called? before malloc and assign to resource1 we can't because it might be copied to resource2, before assigning to resource2 we can't because we may have gotten 2 from the user twice without a intervening 1.

The only way to be sure is to test resource1 and resource2 to see if they are not equal in cases 1 and 2 and free the old value if they were not. This is essentially reference counting where you know there are only 2 possible references.

Answer 2

RAII is not automatically the same thing, but it has the same effect. It provides an easy answer to the question "how do you know when this cannot be accessed any more?" by using scope to cover the area when a particular resource is being used.

You might want to consider the similar problem "how can I know my program will not suffer a type error at runtime?". The solution to this is not predicting all the execution paths through the program but by using a system of type annotation and inference to prove that there cannot be such an error. Rust is an attempt to extend this proof property to memory allocation.

It is possible to write proofs about program behaviour without having to solve the halting problem, but only if you use annotations of some kind to constrain the program. See also security proofs (sel4 etc.)

Answer 3

Yes, this exists in the wild. The ML Kit is a production-quality compiler that has the described strategy (more or less) as one of its available memory management options. It also allows for the use of a conventional GC or hybridizing with reference counting (you can use a heap profiler to see which strategy will actually produce the best results for your program).

A retrospective on region-based memory management is an article by the original authors of the ML Kit that goes into its successes and failures. The eventual conclusion is that the strategy is practical when writing with the assistance of a heap profiler.

(This is a good illustration of why you shouldn't usually look to the Halting Problem for an answer to practical engineering questions: we don't want or need to solve the general case for most realistic programs.)

Answer 4

predict all the permutations of the program's control flow

This is where the problem lies. The amount of permutations is so huge (in practice it is infinite) for any non-trivial program, that time and memory needed would make this completely impractical.

Answer 5

The halting problem proves this isn't possible in all cases. However, it is still possible in a great many cases, and in fact, is done by nearly all compilers for probably a majority of variables. This is how a compiler can tell it's safe to merely allocate a variable on the stack or even a register, instead of to longer-term heap storage.

If you have pure functions or really good ownership semantics, you can extend that static analysis further, although it becomes prohibitively more costly to do so the more branches your code takes.

Answer 6

If a single programmer or team writes the whole program, it is reasonable that design points can be identified where memory (and other resources) should be freed. Thus, yes, static analysis of the design may be sufficient in more limited contexts.

However, when you factor in third party DLLs, APIs, frameworks, (and throw in threads, too), it can be very difficult (nay, impossible in all cases) for the using programmers to correctly reason about what entity owns what memory and when the last use of it is. Our usual suspect of languages don't sufficiently document the transfer of memory ownership of objects and arrays, shallow and deep. If a programmer can't reason over that (statically or dynamically!) then a compiler most likely can't either. Again, this is due to the fact that memory ownership transfers are not captured in method calls or by interfaces, etc.., so, no it is not possible to statically predict when or where in the code to release memory.

As this is such a serious problem, many modern languages choose garbage collection, which automatically reclaims memory sometime after last live reference. GC has a significant performance cost (especially for real-time applications), however, so is not a universal cure all. Further, you can still have memory leaks using GC (e.g. a collection that only grows). Still, this is a good solution for most programming exercises.

There are some alternatives (some emerging).

The Rust language takes RAII to an extreme. It provides linguistic constructs that define the transfer of ownership in methods of classes and interfaces in more detail, e.g. objects being transferred-to vs. borrowed-by between a caller and callee, or in longer lifetime objects. It provides a high level of compile time safety toward memory management. However, it is not a trivial language to pick up, and is also not without it's problems (e.g. I don't think the design is fully stable, certain things are still being experimented with, and thus, changing).

Swift and Objective-C go yet another route, which is mostly-automatic reference counting. Reference counting gets into issues with cycles, and, there are significant programmer challenges, for example, especially with closures.

Answer 7

If a program does not depend on any unknown input then yes, it should be possible (with the caveat that it may be a complex task and may take long; but that would be true for the program as well). Such programs would be completely solvable at compile time; in C++ terms, they could be (almost) completely composed of constexprs. Simple examples would be to compute the first 100 digits of pi or to sort a known dictionary.

Answer 8

Freeing of memory, in general, is equivalent to the halting problem - if you can't statically tell whether a program will halt (statically), you can't tell whether it will free memory (statically) either.

function foo(int a) {
    void *p = malloc(1);
    ... do something which may, or may not, halt ...
    free(p);
}

https://en.wikipedia.org/wiki/Halting_problem

That said, Rust is very nice... https://doc.rust-lang.org/book/ownership.html