How is a reference counter implemented at compile time?

Question

Here is a made up set of function calls (I tried to make it complicated but perhaps it is easy).

function main(arg1, arg2) {
  do_foo(arg1, arg2)
}

function do_foo(a, b) {
  let x = a + b
  let y = x * a
  let z = x * b
  let p = y + z
  let q = x + z
  let r = do_bar(&p)
  let s = do_bar(&q)
}

function do_bar(&p, &q) {
  *p += 1
  *q += 3
  let r = &p * &q
  let s = &p + &q
  let v = do_baz(&r, &s)
  return &v
}

function do_baz(&a, &b) {
  return *a + *b
}

How do you generally go about figuring out the liveness of variables and where you can insert instructions for reference counting?

Here is my attempt...

Start at the top function main. It starts with 2 arguments. Assume there is no copying that occurs. It passes the actual mutable values to do_foo.

Then we have x. X owns a and b. Then we see y. y is set to x, so link the previous x to this x. By r, we don't see x anymore, so perhaps it can be freed.... Looking at do_bar by itself, we know basically that p and q can't be garbage collected within this scope.

Basically, I have no idea how to start implementing an algorithm to implement ARC (ideally compile time reference counting, but runtime would be okay for now too to get started).

function main(arg1, arg2) {
  let x = do_foo(arg1, arg2)
  free(arg1)
  free(arg2)
  free(x)
}

function do_foo(a, b) {
  let x = a + b
  let y = x * a
  let z = x * b
  let p = y + z
  free(y)
  let q = x + z
  free(x)
  free(z)
  let r = do_bar(&p)
  let s = do_bar(&q)
  return r + s
}

function do_bar(&p, &q) {
  *p += 1
  *q += 3
  let r = &p * &q
  let s = &p + &q
  let v = do_baz(&r, &s)
  free(r)
  free(s)
  return &v
}

function do_baz(&a, &b) {
  return *a + *b
}

How do I start with implementing such an algorithm. I have searched for every paper on the topic but found no algorithms.

Answer 1

The following rules should do the job for your language.

1. When a variable is declared, increment its refcount
2. When a variable goes out of scope, decrement its refcount
3. When a reference-to-variable is assigned to a variable, adjust the reference counts for the variable(s):
   • increment the refcount for the variable whose reference is being assigned
   • decrement the refcount for the variable whose references was previously in the variable being assigned to (if it was not null)
4. When a variable containing a non-null reference-to-variable goes out of scope, decrement the refcount for the variable it referred to.

Note:

• If your language allows reference-to-variable types to be used in data structures, "static" variables, etcetera, the rules abouve need to be extended ... in the obvious fashion.
• An optimizing compiler may be able to eliminate some refcount increments and decrements.

---

Compile time reference counting:

1. There isn't really any such thing. Reference counting is done at runtime. It doesn't make sense to do it at compile time.
2. You are probably talking about analyzing the code to determine if runtime reference counting can be optimized or entirely eliminated.
   • I alluded to the former above. It is really a kind of peephole optimization.
   • The latter entails checking whether a reference-to-variable can ever escape; i.e. whether it could be used after the variable goes out of scope. (Try Googling for "escape analysis". This is kind of analogous to the "escape analysis" that a compiler could do to decide if an object could be allocated on the stack rather than in the heap.)