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

スタックの上位 2 つの要素を交換できる命令は 1 つしかないswapため、要素が増えると、コンパイラはローカル変数を生成する必要があります。

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

バイトコード:

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

もちろん、これは任意の量の実パラメータと形式パラメータに拡張できます。

私が今探しているのは、これらswapまたはローカル変数命令を挿入する必要があるかどうか、およびどこに挿入する必要があるかを決定するアルゴリズムです。コンパイラの実装への参照も役立ちます。

どの実引数がどの仮パラメータに属しているかは、私の問題の一部ではないことに注意してください。それは私のコンパイラによってすでに解決されています。簡単にするために、問題は次のように見ることができます。

同じ要素を異なる順序で含む同じサイズの 2 つの配列が与えられた場合、どの要素を最初の配列からスワップまたはシフトして、2 番目の配列の順序を取得できます。

4

1 に答える 1

3

レジスタのみでは、基本的に 1 つのソリューションしかありません。必要なスタック順序で引数を反復処理します。現在の引数がすでに計算されている場合は、ローカルからロードします。それ以外の場合は、その前の未計算の引数を実行順序で計算し、それらをレジスタに格納してから、現在の引数を計算します。

操作が存在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 に答える