时间戳

首页 > 解决方案 > 在编译时如何实现引用计数器？

memory-management - 在编译时如何实现引用计数器？

问题描述

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

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，因此将之前的 x 链接到 this x。By 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
}

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

标签： memory-managementgarbage-collectioncompiler-constructionstatic-analysisreference-counting

解决方案

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

  1. 声明变量时，增加其引用计数
  2. 当变量超出范围时，减少其引用计数
  3. 将引用变量分配给变量时，调整变量的引用计数：
    • 增加正在分配其引用的变量的引用计数
    • 减少其引用先前在分配给的变量中的变量的引用计数（如果它不为空）
  4. 当包含对变量的非空引用的变量超出范围时，减少它引用的变量的引用计数。

笔记：

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

编译时引用计数：

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

推荐阅读