リポジトリ / emssr / independent_common_compiler

# -*- coding: utf-8 -*-

"""lane64 の実行台。

仕様は docs/common-compiler/arch/20。標準機能だけで書く。

道は二本ある。

  解釈器  式 (2.1) の mask 付き意味をそのまま持つ。これが定義になる

  翻訳器  block を Python の code object へ落とす。速い道になる

命題 6.1 が二本の一致を保証し、test_vcpu.py がそれを実際に確かめる。

lane の作業領域は式 (1.2) で交わらないので、翻訳器の道は lane を process へ配れる。

  python vcpu.py image.bin --lanes 8 --words 65536 --procs 6 --in corpus.txt

"""

import os

import sys

import time

INSN = 16

HALT, MAT, ADD, MUL, NEG, EQ, LT, JMP, LD, ST, OK, KO, PUT = range(13)

NAME = ('HALT', 'MAT', 'ADD', 'MUL', 'NEG', 'EQ', 'LT', 'JMP',

        'LD', 'ST', 'OK', 'KO', 'PUT')

# block を閉じる箱（20 章 式 7.4）

TERM = frozenset([EQ, LT, JMP, OK, KO, HALT])

# 報告の返り値。block の番号と混ざらないよう負で持つ

R_OK, R_KO, R_END = -1, -2, -3

LANDMARKS = 256

# ===== 復号（20 章 §2）=====

def decode(image):

    """image を欄の組の並びへ開く。

    固定 16 byte なので、長さを数える走査が要らない。欄の並びは

    op / a / b / c / s_b / s_c / imm で、全部 little endian になる。

    """

    if len(image) % INSN:

        raise ValueError('image の byte 数が %d の倍数でない: %d' % (INSN, len(image)))

    prog = []

    for k in range(0, len(image), INSN):

        w = image[k:k + INSN]

        prog.append((w[0], w[1], w[2], w[3],

                     w[4] | (w[5] << 8), w[6] | (w[7] << 8),

                     int.from_bytes(w[8:16], 'little', signed=True)))

    return prog

def encode(prog):

    """復号の逆（式 40.1、30.4）。二つを往復させると image が戻る。"""

    out = bytearray()

    for (op, a, b, c, sb, sc, im) in prog:

        out += bytes([op, a, b, c, sb & 255, sb >> 8, sc & 255, sc >> 8])

        out += int(im).to_bytes(8, 'little', signed=True)

    return bytes(out)

def disasm(prog):

    out = []

    for i, (op, a, b, c, sb, sc, im) in enumerate(prog):

        out.append('%5d  %-4s a=%-3d b=%-3d c=%-3d sb=%-2d sc=%-2d imm=%d'

                   % (i, NAME[op] if op < len(NAME) else '?', a, b, c, sb, sc, im))

    return out

# ===== block（20 章 §7.3）=====

def entries(prog):

    """block の入口（式 7.4）。分岐の行き先と、分岐の次が入口になる。"""

    n = len(prog)

    e = set([0])

    for i, (op, _a, _b, _c, _sb, _sc, im) in enumerate(prog):

        if op in TERM:

            e.add(i + 1)

            if op in (EQ, LT, JMP):

                e.add(i + im)

    return sorted(x for x in e if 0 <= x < n)

def blocks(prog):

    """(入口, 直線部分の箱, 閉じる箱 or None, 次の入口) の並び。

    閉じる箱が None のときは、次の入口へそのまま落ちる。

    """

    ent = entries(prog)

    n = len(prog)

    out = []

    for k, pc in enumerate(ent):

        stop = ent[k + 1] if k + 1 < len(ent) else n

        j = pc

        body = []

        while j < stop and prog[j][0] not in TERM:

            body.append(j)

            j += 1

        out.append((pc, body, j if j < stop else None, stop))

    return ent, dict((pc, k) for k, pc in enumerate(ent)), out

# ===== 層（20 章 §7.1）=====

def layers(prog, body):

    """直線部分の因果深度（式 7.1）と層（式 7.2）。

    実行の速さには効かない。効くのは「並べ替えてよい」という保証のほうで、

    それが block を直線に書き下せる根拠になる（定理 21.1）。層の幅は

    その保証がどれだけ広いかの目安として出す。

    """

    depth, last, lay = {}, {}, []

    for i in body:

        op, a, b, c = prog[i][0], prog[i][1], prog[i][2], prog[i][3]

        pred = ()

        if op in (ADD, MUL):

            pred = (b, c)

        elif op in (NEG, LD):

            pred = (b,)

        elif op in (ST, PUT):

            pred = (b, c) if op == ST else (b,)

        d = 0

        for r in pred:

            if r in last:

                d = max(d, last[r] + 1)

        depth[i] = d

        if op in (MAT, ADD, MUL, NEG, LD):

            last[a] = d

        while len(lay) <= d:

            lay.append([])

        lay[d].append(i)

    return lay

# ===== 層を同時に走らせる（定理 21.1）=====

#

# 層の中の箱は互いに独立なので、どの順で走らせても、同時に走らせても観測が変わらない。

#

#   (C1 ⊗ id);(id ⊗ C2) = C1 ⊗ C2                          定理 21.1

#

# 配るのは値の箱だけになる。作業領域を触る箱は番地がワイヤの値なので別名を排除できず

# （§19）、本文の順のまま置く。だから値の箱の連なりを先に切り出し、その中でだけ

# 層を作る。

#

# 割に合うかは箱一つの重さで決まる。分子が Z なので、深い作図では一つの ⋆ が

# 多倍長の乗算になり、配る費用を上回る。

_ARITH = frozenset([MAT, ADD, MUL, NEG])

def _box(job):

    """値の箱を一つ。ワイヤの値だけを受けるので、worker は state を持たない。"""

    op, a, u, v, sb, sc, im = job

    if op == MUL:

        return a, u * v

    if op == ADD:

        return a, (u << sb) + (v << sc)

    if op == MAT:

        return a, im

    if op == NEG:

        return a, -u

    raise ValueError('値の箱ではない: %s' % NAME[op])

def _runs(prog, body):

    """値の箱の連なりと、作業領域を触る箱を、本文の順に切り分ける。"""

    out, cur = [], []

    for i in body:

        if prog[i][0] in _ARITH:

            cur.append(i)

        else:

            if cur:

                out.append((True, cur))

                cur = []

            out.append((False, i))

    if cur:

        out.append((True, cur))

    return out

def _layers_hz(prog, seg):

    """並べ替えてよい層。式 (7.1) の Pred に WAR と WAW を足す。

    landmark は allocator が使い回す（13 §13 の wire-to-landmark embedding）ので、

    RAW だけでは並べ替えの根拠にならない。定理 21.1 の独立性はワイヤの上の話であり、

    割り当ての後まで自動では届かない。

    """

    lastw, lastr, lay = {}, {}, []

    for i in seg:

        rs, w = _regs(prog, i)

        d = 0

        for r in rs:

            if r in lastw:

                d = max(d, lastw[r] + 1)

        if w is not None:

            if w in lastw:

                d = max(d, lastw[w] + 1)

            if w in lastr:

                d = max(d, lastr[w] + 1)

        for r in rs:

            lastr[r] = max(lastr.get(r, -1), d)

        if w is not None:

            lastw[w] = d

        while len(lay) <= d:

            lay.append([])

        lay[d].append(i)

    return lay

def _job(prog, R, i):

    op, a, b, c, sb, sc, im = prog[i]

    return (op, a, R[b], R[c], sb, sc, im)

def run_lane_par(prog, lane, pool=None, minw=2, budget=1 << 34):

    """block を層の順に走らせ、幅のある層を pool へ配る。"""

    R, M, OUT = lane.R, lane.M, lane.OUT

    _ent, idx, bl = blocks(prog)

    n, b = len(prog), 0

    for step in range(budget):

        _pc, body, term, stop = bl[b]

        for arith, seg in _runs(prog, body):

            if not arith:

                op, a, u, v = prog[seg][0], prog[seg][1], prog[seg][2], prog[seg][3]

                if op == LD:

                    R[a] = M[R[u]]

                elif op == ST:

                    M[R[u]] = R[v]

                elif op == PUT:

                    OUT.append(R[u] & 255)

                else:

                    raise ValueError('直線部分に置けない箱: %s' % NAME[op])

                continue

            for L in _layers_hz(prog, seg):

                outs = [prog[i][1] for i in L]

                wide = (pool is not None and len(L) >= minw

                        and len(set(outs)) == len(outs))

                if wide:

                    for a, val in pool.map(_box, [_job(prog, R, i) for i in L]):

                        R[a] = val

                else:

                    for i in L:

                        a, val = _box(_job(prog, R, i))

                        R[a] = val

        lane.blocks = step + 1

        if term is None:

            if stop < n:

                b = idx[stop]

                continue

            lane.report = None

            return None

        op, _a, bb, cc, sb, sc, im = prog[term]

        if op == OK:

            lane.report = 0

            return 0

        if op == KO:

            lane.report = 42

            return 42

        if op == HALT:

            lane.report = None

            return None

        if op == JMP:

            t = term + im

        else:

            u, v = R[bb] << sb, R[cc] << sc

            t = term + im if ((u == v) if op == EQ else (u < v)) else term + 1

        if 0 <= t < n and t in idx:

            b = idx[t]

        else:

            lane.report = None

            return None

    raise RuntimeError('block の歩数上限 %d を越えた' % budget)

# ===== 翻訳（20 章 §7.2）=====

# ===== 定理 21.1 の回収 =====

#

# 層分解（式 7.1、7.2）は block を「state を共有しない独立 chamber の積」だと言う。

#

#   (C1 ⊗ id);(id ⊗ C2) = C1 ⊗ C2                          定理 21.1

#

# だから block の中で landmark file を辿る必要が無い。読む前に書かない landmark を

# 入口で local へ写し、書いた landmark を出口で戻せば、間は local variable で足りる。

# CPython では R[k] が LOAD_FAST + LOAD_CONST + BINARY_SUBSCR、local は LOAD_FAST 一つ。

#

# 作業領域 M は別。番地がワイヤの値なので別名を排除できない（§19）。

def _regs(prog, i):

    """(読む landmark, 書く landmark)。M と OUT はここに現れない。"""

    op, a, b, c = prog[i][0], prog[i][1], prog[i][2], prog[i][3]

    if op == MAT:

        return (), a

    if op in (ADD, MUL):

        return (b, c), a

    if op in (NEG, LD):

        return (b,), a

    if op == ST:

        return (b, c), None

    if op in (PUT,):

        return (b,), None

    if op in (EQ, LT):

        return (b, c), None

    return (), None

def _shift(name, r, s):

    return name(r) if s == 0 else '(%s<<%d)' % (name(r), s)

def _stmt(prog, i, name=None):

    if name is None:

        name = lambda r: 'R[%d]' % r

    op, a, b, c, sb, sc, im = prog[i]

    if op == MAT:

        return '%s=%d' % (name(a), im)

    if op == ADD:

        return '%s=%s+%s' % (name(a), _shift(name, b, sb), _shift(name, c, sc))

    if op == MUL:

        return '%s=%s*%s' % (name(a), name(b), name(c))

    if op == NEG:

        return '%s=-%s' % (name(a), name(b))

    if op == LD:

        return '%s=M[%s]' % (name(a), name(b))

    if op == ST:

        return 'M[%s]=%s' % (name(b), name(c))

    if op == PUT:

        return 'OUT.append(%s&255)' % name(b)

    raise ValueError('直線部分に置けない箱: %s' % NAME[op])

def _tail(prog, i, stop, idx, n, name=None):

    """block の閉じ。行の並びを返す。"""

    if name is None:

        name = lambda r: 'R[%d]' % r

    if i is None:

        return ['return %d' % idx[stop]] if stop < n else ['return %d' % R_END]

    def to(t):

        return idx[t] if 0 <= t < n and t in idx else R_END

    op, _a, b, c, sb, sc, im = prog[i]

    if op == OK:

        return ['return %d' % R_OK]

    if op == KO:

        return ['return %d' % R_KO]

    if op == HALT:

        return ['return %d' % R_END]

    if op == JMP:

        return ['return %d' % to(i + im)]

    rel = '==' if op == EQ else '<'

    return ['if %s%s%s: return %d'

            % (_shift(name, b, sb), rel, _shift(name, c, sc), to(i + im)),

            'return %d' % to(i + 1)]

def _succ(prog, term, stop, idx, n):

    """block の後続。_tail の行き先と同じ。"""

    if term is None:

        return [idx[stop]] if stop < n else []

    def to(t):

        return idx[t] if 0 <= t < n and t in idx else None

    op, _a, _b, _c, _sb, _sc, im = prog[term]

    if op in (OK, KO, HALT):

        return []

    if op == JMP:

        return [x for x in [to(term + im)] if x is not None]

    return [x for x in [to(term + im), to(term + 1)] if x is not None]

def _liveness(prog, bl, idx, n):

    """block ごとの live-out（後続が読む landmark の合併）。

    block を出た landmark file を読むのは後続 block だけであり、実行台は

    作業領域と OUT しか見ない。だから最後の block の live-out は空になる。

    """

    use, dfs, succ = [], [], []

    for pc, body, term, stop in bl:

        w, u = set(), set()

        for i in list(body) + ([] if term is None else [term]):

            rs, d = _regs(prog, i)

            u |= set(r for r in rs if r not in w)

            if d is not None:

                w.add(d)

        use.append(u)

        dfs.append(w)

        succ.append(_succ(prog, term, stop, idx, n))

    live_in = [set() for _ in bl]

    live_out = [set() for _ in bl]

    moved = True

    while moved:

        moved = False

        for k in range(len(bl) - 1, -1, -1):

            o = set()

            for t in succ[k]:

                o |= live_in[t]

            i = use[k] | (o - dfs[k])

            if o != live_out[k] or i != live_in[k]:

                live_out[k], live_in[k] = o, i

                moved = True

    return live_out

def _block(prog, k, body, term, stop, idx, n, out_live=None, dead=None, scan=None):

    """block ひとつを関数の行へ落とす。

    block の中では値を記号で追う（局所の値番号付け）。doc: casm.lane64.vn

      landmark   reg[r] は入口の値 R[r]、即値、または局所変数の名前

      作業領域   mem[c] は定数番地 c へこの block が書いた値。次の Load はその名前を使う

    即値どうしの算術は畳む。commonc の lane64 版はワイヤを語 64 + w に置き、

    一箱が MAT・LD・ST の往復に開くので（back_lane64.cam の覆い）、この追跡で

    往復が消え、綴った数は一つの即値に畳まれる。Store は他の block が読むので残す。

    ただし dead に入った番地への Store は落とす（他のどの block も読まないワイヤ）。

    scan を渡すと文を出さず、この block が読む定数番地のうち、自分の Store より前に

    読むものを scan へ集める（translate の一巡目）。

    意味は式 (2.1) の解釈器が定義であり、test_vcpu.py が両者の一致を確かめる。

    """

    steps = list(body) + ([] if term is None else [term])

    reg = {}

    mem = {}

    tmp = [0]

    out = ['def _b%d(R, M, OUT):' % k]

    def get(r):

        if r not in reg:

            reg[r] = 'R[%d]' % r

        return reg[r]

    def lit(e):

        try:

            return int(e)

        except ValueError:

            return None

    def shifted(r, sh):

        e = get(r)

        v = lit(e)

        if sh == 0:

            return e

        if v is not None:

            return str(v << sh)

        return '(%s<<%d)' % (e, sh)

    def fresh(expr):

        tmp[0] += 1

        name = 't%d' % tmp[0]

        out.append('    %s=%s' % (name, expr))

        return name

    def fold2(x, y, f, sym):

        vx, vy = lit(x), lit(y)

        if vx is not None and vy is not None:

            return str(f(vx, vy))

        return fresh('%s%s%s' % (x, sym, y))

    for i in body:

        op, a, b, c, sb, sc, im = prog[i]

        if op == MAT:

            reg[a] = str(im)

        elif op == ADD:

            reg[a] = fold2(shifted(b, sb), shifted(c, sc), lambda x, y: x + y, '+')

        elif op == MUL:

            reg[a] = fold2(get(b), get(c), lambda x, y: x * y, '*')

        elif op == NEG:

            e = get(b)

            v = lit(e)

            reg[a] = str(-v) if v is not None else fresh('-%s' % e)

        elif op == LD:

            addr = get(b)

            v = lit(addr)

            if v is not None and v in mem:

                reg[a] = mem[v]

            else:

                if scan is not None:

                    scan.add(v)

                reg[a] = fresh('M[%s]' % addr)

                if v is not None:

                    mem[v] = reg[a]

        elif op == ST:

            addr, val = get(b), get(c)

            v = lit(addr)

            if not (dead is not None and v in dead):

                out.append('    M[%s]=%s' % (addr, val))

            if v is not None:

                mem[v] = val

            else:

                mem.clear()

        elif op == PUT:

            out.append('    OUT.append(%s&255)' % get(b))

        else:

            raise ValueError('直線部分に置けない箱: %s' % NAME[op])

    keep = set(reg) if out_live is None else (set(reg) & out_live)

    for r in sorted(keep):

        if reg[r] != 'R[%d]' % r:

            out.append('    R[%d]=%s' % (r, reg[r]))

    if term is None:

        tail = _tail(prog, None, stop, idx, n)

    else:

        op, _a, b, c, sb, sc, im = prog[term]

        if op in (EQ, LT):

            rel = '==' if op == EQ else '<'

            x, y = shifted(b, sb), shifted(c, sc)

            vx, vy = lit(x), lit(y)

            to = lambda t: idx[t] if 0 <= t < n and t in idx else R_END

            if vx is not None and vy is not None:

                taken = (vx == vy) if op == EQ else (vx < vy)

                tail = ['return %d' % (to(term + im) if taken else to(term + 1))]

            else:

                tail = ['if %s%s%s: return %d' % (x, rel, y, to(term + im)),

                        'return %d' % to(term + 1)]

        else:

            tail = _tail(prog, term, stop, idx, n)

    out += ['    ' + t for t in tail]

    return out + ['']

def translate(prog, wires=None):

    """image を Python の source と code object へ落とす。

    block ひとつが関数ひとつになる。式 (0.1) の B は block を実行した回数であり、

    箱の数ではない。landmark file は block の入口と出口だけで触る（定理 21.1）。

    wires = (lo, hi) を渡すと、その区間の語は commonc のワイヤ（語 64 + w、19 §3.3）とみなし、

    他のどの block も読まない Store を落とす。ワイヤは箱の番号で名指しされるので、

    平文の側から計算した番地で読まれることは無い（toolchain が作業領域をワイヤの上に置く）。

    区間の外の語（出口 0..63、作業領域、退避語）は残す。

    """

    ent, idx, bl = blocks(prog)

    n = len(prog)

    live = _liveness(prog, bl, idx, n)

    dead = None

    if wires is not None:

        lo, hi = wires

        read = set()

        for k, (pc, body, term, stop) in enumerate(bl):

            _block(prog, k, body, term, stop, idx, n, live[k], scan=read)

        dead = set(c for c in range(lo, hi) if c not in read)

    lines = []

    for k, (pc, body, term, stop) in enumerate(bl):

        lines += _block(prog, k, body, term, stop, idx, n, live[k], dead=dead)

    lines.append('TAB = (' + ''.join('_b%d,' % k for k in range(len(bl))) + ')')

    src = chr(10).join(lines)

    ns = {}

    exec(compile(src, '<lane64>', 'exec'), ns)

    return src, ns['TAB']

# ===== lane 一枚（翻訳器の道）=====

class Lane(object):

    """Σ_lane64 の一枚（20 章 式 1.1）。語は Z なので巻き戻さない（§0.3）。"""

    def __init__(self, words):

        self.R = [0] * LANDMARKS

        self.M = [0] * words

        self.OUT = []

        self.report = None

        self.blocks = 0

    def put_input(self, data, base):

        """18 章 §7.1 と同じ置き方（式 8.2）。"""

        n = min(len(data), len(self.M) - base)

        self.M[0] = n

        self.M[1] = base

        self.M[base:base + n] = data[:n]

        return n

def run_lane(tab, lane, budget=1 << 34):

    """block を辿る。式 (0.1) の T_trans がこの loop になる。"""

    R, M, OUT = lane.R, lane.M, lane.OUT

    b = 0

    try:

        for k in range(budget):

            b = tab[b](R, M, OUT)

            if b < 0:

                lane.blocks = k + 1

                lane.report = 0 if b == R_OK else (42 if b == R_KO else None)

                return lane.report

    except IndexError:

        # 語番号が作業領域を越えた。式 (50.4) の image 実現不能にあたる。

        # try は例外が飛ばない限り費用ゼロなので、速い道の邪魔にならない

        raise IndexError('語番号が作業領域を越える（語数 %d）。--words を増やす'

                         % len(M))

    raise RuntimeError('block の歩数上限 %d を越えた' % budget)

# ===== 解釈器（式 2.1、3.1、3.2、3.3）=====

#

# active relation は W bit の整数一個で持つ。m1 = m & c、m0 = m & ~c が

# それぞれ一演算になる。速さのためではなく、意味の定義を一箇所に置くために書く。

class Interp(object):

    def __init__(self, prog, lanes=1, words=4096):

        self.prog = prog

        self.W = lanes

        self.R = [[0] * LANDMARKS for _ in range(lanes)]

        self.M = [[0] * words for _ in range(lanes)]

        self.OUT = [[] for _ in range(lanes)]

        self.report = [None] * lanes

        self.steps = 0

    def put_input(self, lane, data, base):

        m = self.M[lane]

        n = min(len(data), len(m) - base)

        m[0] = n

        m[1] = base

        m[base:base + n] = data[:n]

        return n

    _one = (0,)

    def _active(self, m):

        return [l for l in range(self.W) if (m >> l) & 1]

    def run(self, budget=1 << 30):

        prog, n = self.prog, len(self.prog)

        groups = [(((1 << self.W) - 1), 0)]

        while groups:

            self.steps += 1

            if self.steps > budget:

                raise RuntimeError('歩数上限 %d を越えた' % budget)

            if len(groups) == 1:

                msk, pc = groups.pop()          # 判定が割れるまでは組が一つ

            else:

                k = min(range(len(groups)), key=lambda i: groups[i][1])

                msk, pc = groups.pop(k)

            if msk == 0 or pc < 0 or pc >= n:

                continue

            op, a, b, c, sb, sc, im = prog[pc]

            act = (self._one if msk == 1 else self._active(msk))

            if op == HALT:

                continue

            if op == OK or op == KO:

                for l in act:

                    self.report[l] = 0 if op == OK else 42

                continue

            if op == JMP:

                groups = _merge(groups, [(msk, pc + im)])

                continue

            if op == EQ or op == LT:

                cm = 0

                for l in act:

                    R = self.R[l]

                    u, v = R[b] << sb, R[c] << sc

                    if (u == v) if op == EQ else (u < v):

                        cm |= 1 << l

                m1, m0 = msk & cm, msk & ~cm     # 式 (3.2)

                groups = _merge(groups, [(m1, pc + im), (m0, pc + 1)])

                continue

            # 値の箱。mask を外れた lane は動かない（式 2.1）

            for l in act:

                R = self.R[l]

                if op == MAT:

                    R[a] = im

                elif op == ADD:

                    R[a] = (R[b] << sb) + (R[c] << sc)

                elif op == MUL:

                    R[a] = R[b] * R[c]

                elif op == NEG:

                    R[a] = -R[b]

                elif op == LD:

                    R[a] = self.M[l][R[b]]

                elif op == ST:

                    self.M[l][R[b]] = R[c]

                elif op == PUT:

                    self.OUT[l].append(R[b] & 255)

            groups = _merge(groups, [(msk, pc + 1)])

        return self.report

def _merge(groups, fresh):

    """reconvergence（式 3.3）。pc が同じ組は mask を合わせて一つにする。"""

    if not groups and len(fresh) == 1 and fresh[0][0]:

        return list(fresh)                      # 割れていない間はそのまま渡す

    out = list(groups)

    for msk, pc in fresh:

        if msk == 0:

            continue

        for k, (m2, p2) in enumerate(out):

            if p2 == pc:

                out[k] = (m2 | msk, pc)

                break

        else:

            out.append((msk, pc))

    return out

# ===== lane を process へ配る（20 章 §0.5）=====

#

# 立ち上げに 600 ms かかるので、pool は host の寿命だけ持ち続ける。

# lane の作業領域が式 (1.2) で交わらないから、持ち回しても state が混ざらない。

_W = {}          # worker の中の束縛。image ごとに一度だけ翻訳する

def _worker_init():

    _W.clear()

def _worker_run(job):

    image, words, data, in_base, head, emit, count = job

    # 束縛の鍵は image そのものにする。長さや id で引くと、同じ大きさの別の

    # image が前の翻訳を拾う

    tab = _W.get(image)

    if tab is None:

        tab = translate(decode(image))[1]

        _W[image] = tab

    res = []

    for _ in range(count):

        lane = Lane(words)

        if data is not None:

            lane.put_input(data, in_base)

        rep = run_lane(tab, lane)

        emitted = None

        if emit:

            base, ln = lane.M[1], lane.M[2]

            if base and ln:

                emitted = bytes(v & 255 for v in lane.M[base:base + ln])

        res.append((rep, bytes(lane.OUT), list(lane.M[:head]), emitted, lane.blocks))

    return res

def _run_share(tab, count, words, data, in_base, head, emit):

    """同じ image を lane 何本か分だけ回す。lane の作業領域は式 (1.2) で

    交わらないので、この呼びは互いに独立になる（定理 21.1）。"""

    out = []

    for _ in range(count):

        lane = Lane(words)

        if data is not None:

            lane.put_input(data, in_base)

        rep = run_lane(tab, lane)

        emitted = None

        if emit:

            base, ln = lane.M[1], lane.M[2]

            if base and ln:

                emitted = bytes(v & 255 for v in lane.M[base:base + ln])

        out.append((rep, bytes(lane.OUT), list(lane.M[:head]), emitted,

                    lane.blocks))

    return out

class VCPU(object):

    """常駐の実行台。pool を作り直さない（式 0.4）。

    lane を配る先は二つある。process は写す量が要るかわりに本当に同時に走る。

    thread は image の翻訳を共有できるので配る費用がほぼ無い。どちらを取るかは

    lane 一本の仕事量で決まるので、両方を持って測れるようにする。

    """

    def __init__(self, procs=1, threads=1):

        self.P = max(1, int(procs))

        self.T = max(1, int(threads))

        self.pool = None

        self.tpool = None

        self._tab = {}

    def close(self):

        if self.pool is not None:

            self.pool.close()

            self.pool.join()

            self.pool = None

        if self.tpool is not None:

            self.tpool.shutdown()

            self.tpool = None

    def _ensure(self):

        if self.pool is None and self.P > 1:

            import multiprocessing as mp

            self.pool = mp.Pool(self.P, initializer=_worker_init)

        return self.pool

    def _threads(self):

        """立ち上げたら畳まない。次の run は待機中の worker がそのまま拾う。"""

        if self.tpool is None and self.T > 1:

            from concurrent.futures import ThreadPoolExecutor

            self.tpool = ThreadPoolExecutor(self.T)

            list(self.tpool.map(lambda _: None, range(self.T)))

        return self.tpool

    def _shares(self, lanes, n):

        return [c for c in (lanes // n + (1 if k < lanes % n else 0)

                            for k in range(n)) if c]

    def _table(self, image):

        tab = self._tab.get(image)

        if tab is None:

            tab = translate(decode(image))[1]

            self._tab[image] = tab

        return tab

    def run(self, image, lanes=1, words=4096, data=None, in_base=64,

            head=64, emit=False):

        """lane を P 本の process へ均等に配る。返りは lane ごとの組になる。

        組は (報告, Put の byte 列, 先頭 head 語, 取り出した image, block 数)。

        作業領域まるごとを持ち帰らないのは、process 間で写す量を抑えるためになる。

        """

        if lanes > 1 and self.T > 1:

            tab = self._table(image)

            futs = [self._threads().submit(_run_share, tab, c, words, data,

                                           in_base, head, emit)

                    for c in self._shares(lanes, self.T)]

            res = []

            for f in futs:

                res.extend(f.result())

            return res

        if self.P <= 1 or lanes == 1:

            return _run_share(self._table(image), lanes, words, data, in_base,

                              head, emit)

        jobs = [(image, words, data, in_base, head, emit, c)

                for c in self._shares(lanes, self.P)]

        res = []

        for part in self._ensure().map(_worker_run, jobs):

            res.extend(part)

        return res

# ===== CLI =====

def _usage():

    sys.stderr.write(

        'vcpu <image.bin> [option]\n'

        '  --lanes W    lane 数。既定 1（20 章 式 1.1）\n'

        '  --words S    lane あたりの語数。既定 4096\n'

        '  --procs P    lane を配る process の本数。既定 1\n'

        '  --in F       全 lane の作業領域へ F を写す。語 0 が byte 数、語 1 が基底\n'

        '  --in-base B  本文の基底語番号。既定 64\n'

        '  --dump N     復帰後に語 0..N-1 を出す\n'

        '  --emit F     lane 0 が組んだ image を取り出す（19 章 §3.1）\n'

        '  --interp     式 (2.1) の mask 付き解釈器で走らせる\n'

        '  --cupy       語も述語も bit のまま GPU で走らせる（cuvcpu）\n'

        '  --bits NB    --cupy の語の幅。既定 32\n'

        '  --list       image を逆アセンブルして並べる\n'

        '  --source     翻訳した Python を出す\n')

def main(argv):

    if len(argv) < 2:

        _usage()

        return 2

    img_path = argv[1]

    lanes, words, procs, dump, in_base, threads = 1, 4096, 1, 0, 64, 1

    par = 0

    bits = 32

    in_path = emit_path = None

    listing = interp = source = cupy = False

    i = 2

    while i < len(argv):

        a = argv[i]

        if a in ('--lanes', '--words', '--procs', '--dump', '--in-base',

                 '--threads', '--par', '--bits'):

            i += 1

            v = int(argv[i])

            if a == '--lanes':

                lanes = v

            elif a == '--words':

                words = v

            elif a == '--procs':

                procs = v

            elif a == '--threads':

                threads = v

            elif a == '--par':

                par = v

            elif a == '--bits':

                bits = v

            elif a == '--dump':

                dump = v

            else:

                in_base = v

        elif a == '--in':

            i += 1

            in_path = argv[i]

        elif a == '--emit':

            i += 1

            emit_path = argv[i]

        elif a == '--list':

            listing = True

        elif a == '--interp':

            interp = True

        elif a == '--cupy':

            cupy = True

        elif a == '--source':

            source = True

        else:

            _usage()

            return 2

        i += 1

    with open(img_path, 'rb') as f:

        image = f.read()

    prog = decode(image)

    if listing:

        for ln in disasm(prog):

            print(ln)

        return 0

    if source:

        print(translate(prog)[0])

        return 0

    data = None

    if in_path is not None:

        with open(in_path, 'rb') as f:

            data = f.read()

    t0 = time.perf_counter()

    if interp:

        m = Interp(prog, lanes=lanes, words=words)

        if data is not None:

            for l in range(lanes):

                m.put_input(l, data, in_base)

        rep = m.run()

        res = [(rep[l], bytes(m.OUT[l]), m.M[l][:max(dump, 3)], None, 0)

               for l in range(lanes)]

        note = '解釈器 %d 歩' % m.steps

    elif cupy:

        import cuvcpu

        res = cuvcpu.run(prog, lanes=lanes, words=words, bits=bits, data=data,

                         in_base=in_base, head=max(dump, 4),

                         emit=emit_path is not None)

        note = 'GPU %d bit  %d 歩' % (bits, res[0][4])

    elif par:

        import multiprocessing as mp

        tab = None

        pool = mp.Pool(par)

        lane = Lane(words)

        if data is not None:

            lane.put_input(data, in_base)

        rep = run_lane_par(prog, lane, pool)

        pool.close()

        pool.join()

        res = [(rep, bytes(lane.OUT), list(lane.M[:max(dump, 4)]), None,

                lane.blocks)]

        note = '層並列 block %d 回' % lane.blocks

        del tab

    else:

        vm = VCPU(procs, threads)

        res = vm.run(image, lanes=lanes, words=words, data=data,

                     in_base=in_base, head=max(dump, 4), emit=emit_path is not None)

        vm.close()

        note = '翻訳器 block %d 回' % sum(r[4] for r in res)

    el = time.perf_counter() - t0

    bad = 0

    for l, (rep, out, head, _em, _b) in enumerate(res):

        tag = 'tu' if rep == 0 else ('te' if rep == 42 else '報告なし')

        if rep != 0:

            bad += 1

        if lanes <= 8 or l < 2 or l == lanes - 1:

            print('lane %-4d %s' % (l, tag))

    print('%s   %.3f 秒   lane %d   process %d   thread %d'

          % (note, el, lanes, procs, threads))

    rep0, out0, head0, em0, _ = res[0]

    if out0:

        print('out    : %d byte  %s' % (len(out0), out0.decode('latin-1')))

    for k in range(dump):

        v = head0[k]

        # 分子は Z なので、深い作図では十進へ落とすほうが計算より重くなる

        if v.bit_length() > 4096:

            print('  w[%d] = %d bit の整数' % (k, v.bit_length()))

        else:

            print('  w[%d] = %d' % (k, v))

    if emit_path is not None:

        if em0 is None:

            sys.stderr.write('image が空（語1=%d 語2=%d）\n' % (head0[1], head0[2]))

            return 1

        with open(emit_path, 'wb') as f:

            f.write(em0)

        print('image  : %s  %d byte' % (emit_path, len(em0)))

    return 1 if bad else 0

if __name__ == '__main__':

    sys.exit(main(sys.argv))