Memory – Predicting When to Deallocate Memory from Source Code

memoryparsing

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.

Best Answer

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.

Related Topic