1. はじめに

PeepHole最適化は覗き窓を用意してその覗き窓にマッチした場合はより短い命令に書き換える最適化手法です。
私は今までPeepHole最適化をしたことがなかったので、やってみることにしました。

peephole --> [movi(R,I1),addi(R,I2)],peephole,{I is I1+I2},append([movi(R,I)]).
peephole --> [push(R1),pop(R2)],peephole,append([mov(R2,R1)]).
peephole --> [mov(R,R)],peephole.
peephole --> [addi(_,0)],peephole.
peephole --> [I],peephole,append([I]).
peephole([],[]).

図に書くとpeephole最適化はこのような規則で書くことができます。

例えば、以下のコードは

  [
    movi(r(1), 3),
    addi(r(1), 4),
    push(r(1)),
    pop(r(1)),
    mov(r(2), r(2)),
    addi(r(3), 0)
  ]

peephole最適化をすることで

  [
    movi(r(1),7)
  ]

に最適化できます。

2. OCaml版

ここまで辿り着くまでの道のりを解説しましょう。
まず、ChatGPT に OCaml で PeepHole 最適化を書いてみてもらいました。

(* 独自アセンブリ定義 *)
type reg = R of int

type inst =
  | Mov  of reg * reg
  | MovI of reg * int
  | Add  of reg * reg
  | AddI of reg * int
  | Push of reg
  | Pop  of reg
  | Label of string
  | Jmp of string

(* 表示用（デバッグ） *)
let string_of_reg = function
  | R n -> "r" ^ string_of_int n

let string_of_inst = function
  | Mov (r1,r2) -> Printf.sprintf "MOV %s,%s" (string_of_reg r1) (string_of_reg r2)
  | MovI (r,i) -> Printf.sprintf "MOV %s,#%d" (string_of_reg r) i
  | Add (r1,r2) -> Printf.sprintf "ADD %s,%s" (string_of_reg r1) (string_of_reg r2)
  | AddI (r,i) -> Printf.sprintf "ADD %s,#%d" (string_of_reg r) i
  | Push r -> Printf.sprintf "PUSH %s" (string_of_reg r)
  | Pop r -> Printf.sprintf "POP %s" (string_of_reg r)
  | Label s -> s ^ ":"
  | Jmp s -> "JMP " ^ s

let dump code =
  List.iter (fun i -> print_endline (string_of_inst i)) code

(* Peephole 最適化 *)
let rec peephole = function
  | MovI (r1,a) :: AddI (r2,b) :: rest when r1 = r2 -> MovI (r1, a + b) :: peephole rest
  | Mov (r1,r2) :: rest                when r1 = r2 -> peephole rest
  | AddI (_,0) :: rest                              -> peephole rest
  | Push r1 :: Pop r2 :: rest          when r1 = r2 -> peephole rest
  | Push r1 :: Pop r2 :: rest                       -> Mov (r2, r1) :: peephole rest
  | i :: rest                                       -> i :: peephole rest
  | [] -> []

let rec fix f x =
  let x_ = f x in
  if x = x_ then x else fix f x_

let optimize code =
  fix peephole code

(* テスト *)

let () =
  let code = [
    MovI (R 1, 3);
    AddI (R 1, 4);
    Push (R 1);
    Pop (R 1);
    Mov (R 2, R 2);
    AddI (R 3, 0);
  ] in

  print_endline "=== before ===";
  dump code;

  let code_ = optimize code in

  print_endline "\n=== after ===";
  dump code_;
  assert (code_ = [MovI(R 1, 7)])

素晴らしいですね。若干書き換えましたがほぼChatGPTが十分わかりやすいコードを生成してくれました。

AST を定義して、出力関数を作り、peephole最適化の関数と、安定するまで実行し続ける関数fixを作ってテストしています。

3. Prolog移植版

peephole関数では when r1 = r2 のような記述が多々あります。こういったケースだとPrologの単一化を使うと綺麗に書けることが知られています。
素直にPrologに移植してみましょう:

int(I):-integer(I).
reg(r(I)):- int(I).
inst(mov(R1,R2)):-reg(R1),reg(R2).
inst(movi(R,I)):-reg(R),int(I).
inst(add(R1,R2)):-reg(R1),reg(R2).
inst(addi(R,I)):-reg(R),int(I).
inst(push(R)):-reg(R).
inst(pop(R)):-reg(R).
inst(label(A)):-atom(A).
inst(jmp(A)):-atom(A).

dump(Code):- maplist(writeln,Code).

% Peephole 最適化
peephole([movi(R,A),addi(R,B)|C],[movi(R,I)|C2]):-I is A+B,peephole(C,C2).
peephole([mov(R,R)|C],C2):- peephole(C,C2).
peephole([addi(_,0)|C],C2):- peephole(C,C2).
peephole([push(R),pop(R)|C],C2):- peephole(C,C2).
peephole([push(R1),pop(R2)|C],[mov(R2,R1)|C2]):- peephole(C,C2).
peephole([I|C],[I|C2]):- peephole(C,C2).
peephole([],[]).

fix(F,X,X2):- call(F,X,X1),X\=X1,fix(F,X1,X2).
fix(_,X,X).

optimize(C,C2):- maplist(inst,C),fix(peephole,C,C2).

% テスト
:-
  Code = [
    movi(r(1), 3),
    addi(r(1), 4),
    push(r(1)),
    pop(r(1)),
    mov(r(2), r(2)),
    addi(r(3), 0)
  ],
  writeln("=== before ==="),
  dump(Code),
  optimize(Code,Code_),
  writeln("\n=== after ==="),
  dump(Code_),
  Code_ = [movi(r(1), 7)].
:- halt.

Prologは型定義がないので、構文定義として書きました。
ASTの出力関数は作らなくても出力できますが、dump述語は作りました。
peephole述語は規則の羅列にできました。
optimize述語では構文検査の後にpeephole最適化を行います。

4. Prolog簡潔版

このPrologコードでも十分なのですが、Prologならもっと短くできるんじゃないかな？
DCGを使ってpeephole述語を書き換えたり、構文検査無しにしたりすれば、、、。
やってみました:

% Peephole 最適化
peephole --> [movi(R,I1),addi(R,I2)],peephole,{I is I1+I2},append([movi(R,I)]).
peephole --> [push(R1),pop(R2)],peephole,append([mov(R2,R1)]).
peephole --> [mov(R,R)],peephole.
peephole --> [addi(_,0)],peephole.
peephole --> [I],peephole,append([I]).
peephole([],[]).
optimize(X,X2):- peephole(X,X1),X\=X1,optimize(X1,X2).
optimize(X,X).

:-
  Code = [
    movi(r(1), 3),
    addi(r(1), 4),
    push(r(1)),
    pop(r(1)),
    mov(r(2), r(2)),
    addi(r(3), 0)
  ],
  writeln('=== before ==='),maplist(writeln,Code),
  optimize(Code,Code_),
  writeln('\n=== after ==='),maplist(writeln,Code_),
  Code_ = [movi(r(1),7)].
:- halt.

inst/1 は削除しました。
最初は、DCG化のために emit/3 述語を作りました。これは通常 DCG のリスト表記はリストから値を取り出す意味があります。ですが、peephole最適化では最後にリストに追加する処理を行いたいので、書き戻す処理をemitで行うことにしました。しかし、append/3 を使えば複数のリストを手前に追加できることに気がついたのでemit/3は消しました。
optimize述語から構文検査を消して、fix述語を展開してしまいました。
push(R),pop(R)を消すルールは、push(R1),pop(R2)をmov(R2,R1)にする規則でmov(R,R)になって消されるので削除しました。

5. 関連事項

mescc は z80 の CP/M 上で動作する Small C コンパイラですが peephole 最適化を行う専用のコマンドがあります。
https://github.com/MiguelVis/mescc/blob/master/ccopt.c

Z80上でセルフホストしたいとこのコンパイラのソースを読んでいて難しいなと思ったのが今回の記事を書く動機になりました。

実践コンパイラ構成法には OCamlLex を用いて正規表現でのパターンマッチングで最適化を行う例があります。

ccopt でしていることも OCamlLex でしていることに近いです。

ふつうのコンパイラをつくろうにも peephole最適化について書かれてはいたのですが理解できませんでした。

6. まとめ

PeepHole最適化は覗き窓を用意してパターンマッチしより短いコードに書き換える最適化手法です。
はじめに例を示し、OCamlのコードで実装し、それをPrologに移植、さらにより簡潔なコードにしました。

C言語を実装する簡単な例はスタックマシンのJIT結果を保存したようなアセンブラを生成することになりますが、その最適化をどうしたらいいかのとっかかりとしてPeepHole最適化は知られていますが、意外と簡単な例は知られていないように思います。文字列操作でのパターンマッチによる例もありますが、代数的データ型のような形であるとより理解しやすいですし、論理型言語の単一化やDCGを使うとより簡潔に記述できました。

理解して仕舞えば簡単ですので、最適化をしてみたことがない方はチャレンジしてみてはいかがでしょうか？