3

在编译器上工作时，我面临与命名参数列表和评估顺序相关的问题。基本上，该语言确保对于以下函数和函数调用：

int call(int first, int second) = first - second

int sideEffect(int i) { println(i); return i }

println(call(second: sideEffect(0), first: sideEffect(1)))

输出将是

0
1
1

尽管参数以相反的顺序给出。我正在研究 JVM，因此必须在字节码级别对它们进行排序以匹配call. 在基于堆栈的伪字节码中：

push 0
call sideEffect(int)
push 1
call sideEffect(int)
swap
call call(int, int)

正如你所看到的，swap这里需要一个字节码指令来确保它们都被评估并以正确的顺序传递。这可以绘制为图表：

Actual:   second   first
                \ /
                swap
                / \
Formal:    first   second

只有一条swap指令可以交换堆栈顶部的两个元素，因此对于更多元素，编译器需要生成局部变量。

Actual: third   second   first
          |       |  /¯¯¯¯
        local0   swap    local0
            ____/ |        |
Formal: first   second   third

在字节码中：

third...
store local0
second...
first...
swap
load local0
call ...

当然，这可以扩展到任意数量的实际和形式参数。

我现在正在寻找的是某种算法，它确定我是否应该以及在哪里插入这些swap或局部变量指令。对编译器实现的引用也会有所帮助。

请注意，哪个实际参数属于哪个形式参数不是我的问题的一部分。我的编译器已经解决了这个问题。为简化起见，可以这样看待问题：

给定两个大小相同的数组，其中包含不同顺序的相同元素，哪些元素可以从第一个数组交换或移动以获得第二个数组的顺序。

4

1 回答 1

3

仅使用寄存器，基本上只有一种解决方案。以所需的堆栈顺序遍历参数。如果已经计算了当前参数，则从本地加载它。否则，按执行顺序计算它之前的未计算参数，将它们存储在寄存器中，然后计算当前参数。

操作的存在swap意味着我们可以将栈顶用作事实上的局部变量。下面是 Python 代码。

import heapq
import itertools


class Allocator:

  def __init__(self):
    self.free_heap = []
    self.next_free = 0

  def allocate(self):
    if self.free_heap:
      return heapq.heappop(self.free_heap)
    i = self.next_free
    self.next_free += 1
    return i

  def free(self, i):
    heapq.heappush(self.free_heap, i)

  def is_allocated(self, i):
    return i < self.next_free and i not in self.free_heap


def loads_and_stores(perm):
  perm = list(perm)
  n = len(perm)
  assert set(perm) == set(range(n))
  location = {}
  allocator = Allocator()
  i = iter(perm)
  # "location 0" is the top of the stack
  for j in range(n):
    if j in location:
      if location[j] != 0:
        # not top of stack; need an actual load
        print 'load', location[j]
        if allocator.is_allocated(0):
          # need to maintain the top of the stack
          print 'swap'
      allocator.free(location[j])
    else:
      while True:
        k = next(i)
        print 'compute', k
        if k == j:
          if allocator.is_allocated(0):
            # need to maintain the top of the stack
            print 'swap'
          break
        location[k] = allocator.allocate()
        if location[k] != 0:
          # not top of stack; need an actual store
          print 'store', location[k]
  return perm


def test(n):
  for perm in itertools.permutations(range(n)):
    print perm
    loads_and_stores(perm)


test(4)

这里有一些有趣的优化，因为allocate可以返回任何免费的本地。最佳算法将考虑进行每次分配的执行成本。

于 2016-06-15T20:32:29.993 回答