gcc を途中で止め、電卓を二度作る

目標

gccを、プリプロセス・コンパイル・アセンブル・リンクの段階ごとに止めて出力ファイルを確認し、同じRPN計算を、すぐに計算するインタプリターとCに移して焼くコンパイラーの2通りで作って、2つが同じ答えを出すかを突き合わせます。

なぜ重要なのか

コンパイラーとインタプリターは、同じ前段を使い、最後の一歩だけが違います。その一歩のせいで、エラーを見つける時点(実行前か実行中か)、速度(翻訳コストを何回に分けて払うか)、そして意味がずれる危険が生まれます。Pythonで作ったインタプリターが、Pythonの除算規則をそのまま使うと、Cで焼いた側と、負の数で答えが分かれます。このラボは、その違いを、小さな計算機で自分の手で体験させます。

RPN計算機の言葉

낱말      정수(부호가 붙을 수 있음, 예: 7, -3) · x(실행할 때 받는 값) · + - * / %
뜻        낱말을 왼쪽부터 읽는다. 수는 스택에 올리고, 연산자는 두 값을 내려(먼저 내린 것이 오른쪽)
          계산한 결과를 올린다. 끝에 값이 정확히 하나 남아야 한다.
나눗셈    C 처럼 0 쪽으로 자른다: -7 / 2 = -3, 나머지의 부호는 나눠지는 수를 따른다: -7 % 2 = -1
예        "x 1 + 2 *" 는 (x + 1) * 2
오류 글자 bad token 'foo' at 3      (1부터 센 낱말 자리)
          stack underflow at 2      (그 연산자의 자리)
          expected one value, got 2 (끝에 남은 값의 수)
          division by zero

ステップ

/opt/fixtures/mini/c/hello.cを段階ごとに止めて、/root/mini/stages/hello.i(プリプロセス)、hello.s(アセンブリ)、hello.o(オブジェクトファイル)、hello(実行ファイル)を作ります。nm hello.oで、まだ解決されていない名前(U)を確認してみてください。
/root/mini/rpn.pyのtokenize(text)を埋めます。空白で切った単語のリストを返し、知らない単語はRpnError("bad token 'foo' at 3")です。
evaluate(tokens, x)を埋めます。スタックですぐに計算するインタプリターです。エラーは上の文字列のとおりRpnErrorです。
check(tokens)を埋めます。実行せずにスタックの深さだけをたどり、問題がなければ最も深いときの段数を、あればevaluateと同じ文字列のRpnErrorを出します。0での除算はxに依存するので、ここでは判断しません。
to_c(tokens)を埋めます。同じ計算をするCプログラムの文字列です。まずcheckで検査して、間違ったプログラムならCを書かずRpnErrorを出します。xはargv[1]、結果は1行で出力し、0で割るとruntime error: division by zeroを出力して1で終了します。
build(tokens, out)を埋めます。out.c → out.s → out.o → outをgccで順に作り、中間出力ファイルを削除しません。
自分のインタプリターと自分のコンパイラーを、互いに突き合わせます。採点ツールが、ランダムなプログラム15個を、xの4つの値で、2つの道の両方で実行します。負の数の除算・剰余で分かれないかを確認してください。
bench(tokens, xs, out)を埋め、/opt/fixtures/mini/rpn/big.rpnをx = 0から199までで測った結果を、/root/mini/rpn_report.jsonにそのまま書きます。

参考

作業場所は/root/miniで、ラボを開始するとrpn.pyの骨組みが置かれています(関数名と引数はそのままにしてください。採点ツールが名前で呼び出します)。削除した場合は、bash /opt/lab/minic/prepare.sh cc-pipeline-labで復元します。
よくある間違いは、除算にPythonの//と%をそのまま使う、演算子の位置を0から数える、checkで実際に計算して0での除算をエラーにする、の3つです。
セッションは60分で始まり、＋時間で延ばせます。終わると/root/miniが消えます。残したいコードは、別に移しておいてください。

gccを4回止める

gccは、-E(プリプロセス)・-S(コンパイル)・-c(アセンブル)で止められ、オプションがなければリンクまで進みます。前の段階の出力を次の段階の入力に渡せば、1段階ずつ分けて見られます。.oにはprintfのアドレスがまだないので、nmがUと表示します。

単語に切る

text.split()で切ったあと、単語ごとにx・演算子・整数のどれかを調べます。整数は、符号が1つ付けられる数字列です(「--3」は整数ではありません)。位置は1から数えます。

スタックですぐに計算する: インタプリター

演算子に出会ったら、2つの値を取り出します。先に取り出したものが右のオペランドです。除算は、absで商を求めてから符号を付けて0の方向へ切り捨て、剰余はa - 商*bで求めればCと同じになります。

実行せずに検査する

値の代わりに、スタックの深さだけを数えます。数は+1、演算子は2つを取り出して1つを積むので-1で、その前に深さが2以上かどうかを確認します。最も深かった値が、C配列のサイズになります。

同じ計算をCに移す: コンパイラー

Cにもスタック配列1つと段の番号(sp)を置けば、単語ごとに1行ずつそのまま移せます。配列サイズはcheckが測った深さです。Cの/と%はすでに0の方向へ切り捨てるので、別にすることはありませんが、0で割るとプロセスが落ちるので、その前に検査します。

C → アセンブリ → オブジェクトファイル → 実行ファイル

ステップ1で手でやった4段階を、subprocessで順に呼び出します(gcc -S、gcc -c、gcc)。1段階でも失敗したら、gccエラーの最後の行をRpnErrorに入れて出します。

2つの道が同じ答えを出すかを突き合わせる

このステップでは新しいコードを書きません。採点ツールが、ランダムなプログラムを、自分のevaluateとbuildの結果の両方で実行します。落ちたら、負の数の除算・剰余の符号から確認してください。インタプリターがPythonの規則に従うと、Cと分かれます。

コンパイルがいつ得になるかを測る

time.perf_counterで3つの区間を測ります。値ごとのevaluate、buildを1回、値ごとの実行ファイルの起動です。プロセスを起動するコストが、計算より大きいことがあることも、数字で見えます。sameは、2つの結果リストが同じかどうかです。