编译时如何实现引用计数器？

Question

这是一组函数调用（我试图让它变得复杂，但也许很简单）。

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
}

您通常如何确定变量的活跃度以及您可以在何处插入引用计数指令？

这是我的尝试...

从顶部函数开始 main。它以 2 个参数开头。假设没有发生复制。它将实际可变值传递给 do_foo.

然后我们有 x。 X拥有a和b。然后我们看到 y。 y 设置为 x，因此 link 前一个 x 到此 x。通过r，我们再也看不到x，所以也许它可以被释放....看do_bar本身，我们基本上知道p和q 无法在此范围内进行垃圾回收。

基本上，我不知道如何开始实现一个算法来实现 ARC（理想情况下是编译时引用计数，但运行时现在也可以开始）。

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
}

我如何开始实施这样的算法。我搜索了关于该主题的每篇论文，但没有找到任何算法。

Answer 1

以下规则应该适合您的语言。

声明变量时，增加其引用计数
当变量超出范围时，减少其引用计数
当 reference-to-variable 被分配给一个变量时，调整变量的引用计数：
- 增加其引用被赋值的变量的引用计数
- 减少其引用先前在被分配给的变量中的变量的引用计数（如果它不为空）
当包含 non-null reference-to-variable 的变量超出范围时，减少它引用的变量的引用计数。

注：

如果您的语言允许 reference-to-variable 类型用于数据结构、“静态”变量等，则需要扩展上述规则……以明显的方式。
优化编译器可能能够消除一些引用计数增量和减量。

编译时引用计数：

真的没有这样的东西。引用计数是在运行时完成的。在编译时做是没有意义的。
您可能正在谈论分析代码以确定是否可以优化或完全消除运行时引用计数。
- 我在上面提到了前者。真是一种窥视孔优化
- 后者需要检查 reference-to-variable 是否可以逃脱；即是否可以在变量超出范围后使用。（尝试谷歌搜索“逃逸分析”。这有点类似于“逃逸分析”，编译器可以用来决定一个对象是否可以分配到堆栈而不是堆中。）

编译时如何实现引用计数器？

How is a reference counter implemented at compile time?

compiler-construction

garbage-collection

static-analysis

memory-management

reference-counting