![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
[[Pythonを読む]] #contents *compiler_mod (Python/compile.c) [#x6f2de9f] さて、シンボルテーブル作成が予想以上に長かったですがともかくできたので次のステップです。compile.cの先頭に書かれているコメントを再掲すると、 #code(C){{ /* * This file compiles an abstract syntax tree (AST) into Python bytecode. * * The primary entry point is PyAST_Compile(), which returns a * PyCodeObject. The compiler makes several passes to build the code * object: * 1. Checks for future statements. See future.c * 2. Builds a symbol table. See symtable.c. * 3. Generate code for basic blocks. See compiler_mod() in this file. * 4. Assemble the basic blocks into final code. See assemble() in this file. * 5. Optimize the byte code (peephole optimizations). See peephole.c */ }} 2.まで終わって、次は3.のcompiler_modです。（一部省略して掲載） #code(C){{ static PyCodeObject * compiler_mod(struct compiler *c, mod_ty mod) { PyCodeObject *co; int addNone = 1; static PyObject *module; if (!module) { module = PyUnicode_InternFromString("<module>"); } /* Use 0 for firstlineno initially, will fixup in assemble(). */ if (!compiler_enter_scope(c, module, COMPILER_SCOPE_MODULE, mod, 0)) return NULL; switch (mod->kind) { case Module_kind: if (!compiler_body(c, mod->v.Module.body)) { compiler_exit_scope(c); return 0; } break; case Interactive_kind: c->c_interactive = 1; VISIT_SEQ_IN_SCOPE(c, stmt, mod->v.Interactive.body); break; case Expression_kind: VISIT_IN_SCOPE(c, expr, mod->v.Expression.body); addNone = 0; break; } co = assemble(c, addNone); compiler_exit_scope(c); return co; } }} compiler_enter_scopeは長いので代わりにcompiler構造体の上に書いてあるコメントを掲載。 #code(C){{ /* This struct captures the global state of a compilation. The u pointer points to the current compilation unit, while units for enclosing blocks are stored in c_stack. The u and c_stack are managed by compiler_enter_scope() and compiler_exit_scope(). */ }} 名前の通り、スコープへのインとアウトを行っています。その際、前回作ったシンボルテーブルの情報を取得しています。 さてというわけでcompiler_enter_scopeはさらっと流して次、VISIT_SEQ_IN_SCOPEです。シンボルテーブル作成でも同じようなのがあったのでもうわかりますが、 #code(C){{ #define VISIT_SEQ_IN_SCOPE(C, TYPE, SEQ) { \ int _i; \ asdl_seq *seq = (SEQ); /* avoid variable capture */ \ for (_i = 0; _i < asdl_seq_LEN(seq); _i++) { \ TYPE ## _ty elt = (TYPE ## _ty)asdl_seq_GET(seq, _i); \ if (!compiler_visit_ ## TYPE((C), elt)) { \ compiler_exit_scope(c); \ return 0; \ } \ } \ } }} というわけでcompiler_visit_stmtに進みます。 *compiler_visit_stmt [#h88941dd] compiler_visit_stmtはシンボルテーブル作成と同じでswitch文です。ASTを見てみると、 Expr ListComp Name(n) Load Comprephension Name(n) Store Call Name(Range) Load Num(10) Compare BinOp Mult Name(n) Load Name(n) Load Gt Num(10) Exprです。対応部分を見ると、 #code(C){{ case Expr_kind: if (c->c_interactive && c->c_nestlevel <= 1) { VISIT(c, expr, s->v.Expr.value); ADDOP(c, PRINT_EXPR); } else if (s->v.Expr.value->kind != Str_kind && s->v.Expr.value->kind != Num_kind) { VISIT(c, expr, s->v.Expr.value); ADDOP(c, POP_TOP); } break; }} interactiveでnestlevelも1なのでExprをたどった後にPRINT_EXPRが追加されています。シェルだと何か書いた後その値が表示されるあれと予想されますね。 ADDOPを先に見ておきます。 #code(C){{ #define ADDOP(C, OP) { \ if (!compiler_addop((C), (OP))) \ return 0; \ } static int compiler_addop(struct compiler *c, int opcode) { basicblock *b; struct instr *i; int off; off = compiler_next_instr(c, c->u->u_curblock); if (off < 0) return 0; b = c->u->u_curblock; i = &b->b_instr[off]; i->i_opcode = opcode; i->i_hasarg = 0; if (opcode == RETURN_VALUE) b->b_return = 1; compiler_set_lineno(c, off); return 1; } }} basicblockはASTをたどった結果作られる命令列を格納する構造体です。先ほど詳細に踏み込まなかったcompiler_enter_scope（から呼ばれているcompiler_use_new_block）で作られています。 instrは紛らわしいですが、instructionの略で1命令を表す構造体です。compiler_next_instrはその名の通り、次にinstrをセットする場所を返す関数です。必要なら命令列を入れる領域を広げるようになっています。 *compiler_comprehension [#hbd6d8c0] さて、compiler_visit_exprに進みます。こちらもcompiler_visit_stmt同様switch文なので先に進んで、ListCompなのでcompiler_listcomp経由でcompiler_comprehensionが呼び出されます。 #code(C){{ static int compiler_comprehension(struct compiler *c, expr_ty e, int type, identifier name, asdl_seq *generators, expr_ty elt, expr_ty val) { PyCodeObject *co = NULL; expr_ty outermost_iter; PyObject *qualname = NULL; outermost_iter = ((comprehension_ty) asdl_seq_GET(generators, 0))->iter; if (!compiler_enter_scope(c, name, COMPILER_SCOPE_COMPREHENSION, (void *)e, e->lineno)) goto error; if (type != COMP_GENEXP) { int op; switch (type) { case COMP_LISTCOMP: op = BUILD_LIST; break; // 他省略 } ADDOP_I(c, op, 0); } if (!compiler_comprehension_generator(c, generators, 0, elt, val, type)) goto error_in_scope; if (type != COMP_GENEXP) { ADDOP(c, RETURN_VALUE); } co = assemble(c, 1); qualname = c->u->u_qualname; Py_INCREF(qualname); compiler_exit_scope(c); if (!compiler_make_closure(c, co, 0, qualname)) goto error; Py_DECREF(qualname); Py_DECREF(co); VISIT(c, expr, outermost_iter); ADDOP(c, GET_ITER); ADDOP_I(c, CALL_FUNCTION, 1); return 1; error_in_scope: compiler_exit_scope(c); error: Py_XDECREF(qualname); Py_XDECREF(co); return 0; } }} 新しいスコープを作っているのは予想通りです。その後は少しややこしいです。整理してみましょう。 +ADDOP(BUILD_LIST) +compiler_comprehension_generator呼び出し +ADDOP(RETURN_VALUE) この後にcompiler_exit_scopeがあるのでスコープが戻ります。続いて、 +compiler_make_closure呼び出し +VISIT(outermost_iter) +ADDOP(GET_ITER) +ADDOP(CALL_FUNCTION) を行っています。これらは元々のスコープに対して行われます。 **compiler_comprehension_generator [#yfe4fb89] まずはcompiler_comprehension_generatorを見てみましょう。 #code(C){{ static int compiler_comprehension_generator(struct compiler *c, asdl_seq *generators, int gen_index, expr_ty elt, expr_ty val, int type) { /* generate code for the iterator, then each of the ifs, and then write to the element */ comprehension_ty gen; basicblock *start, *anchor, *skip, *if_cleanup; Py_ssize_t i, n; start = compiler_new_block(c); skip = compiler_new_block(c); if_cleanup = compiler_new_block(c); anchor = compiler_new_block(c); gen = (comprehension_ty)asdl_seq_GET(generators, gen_index); if (gen_index == 0) { /* Receive outermost iter as an implicit argument */ c->u->u_argcount = 1; ADDOP_I(c, LOAD_FAST, 0); } else { /* Sub-iter - calculate on the fly */ VISIT(c, expr, gen->iter); ADDOP(c, GET_ITER); } compiler_use_next_block(c, start); ADDOP_JREL(c, FOR_ITER, anchor); NEXT_BLOCK(c); VISIT(c, expr, gen->target); /* XXX this needs to be cleaned up...a lot! */ n = asdl_seq_LEN(gen->ifs); for (i = 0; i < n; i++) { expr_ty e = (expr_ty)asdl_seq_GET(gen->ifs, i); VISIT(c, expr, e); ADDOP_JABS(c, POP_JUMP_IF_FALSE, if_cleanup); NEXT_BLOCK(c); } if (++gen_index < asdl_seq_LEN(generators)) if (!compiler_comprehension_generator(c, generators, gen_index, elt, val, type)) return 0; /* only append after the last for generator */ if (gen_index >= asdl_seq_LEN(generators)) { /* comprehension specific code */ switch (type) { case COMP_LISTCOMP: VISIT(c, expr, elt); ADDOP_I(c, LIST_APPEND, gen_index + 1); break; // 他省略 } compiler_use_next_block(c, skip); } compiler_use_next_block(c, if_cleanup); ADDOP_JABS(c, JUMP_ABSOLUTE, start); compiler_use_next_block(c, anchor); return 1; } }} 急にいろいろ出てきました。ひとつずつ確認していきましょう。 まず先頭、start, skip, if_cleanup, anchorというblockが作成されています。そして、 #code(C){{ compiler_use_next_block(c, start); ADDOP_JREL(c, FOR_ITER, anchor); NEXT_BLOCK(c); VISIT(c, expr, gen->target); }} という記述から、ジャンプの飛び先のラベルとして使われているようです。 さて、target、今回の場合はName(n)、compiler_visit_exprを経由してcompiler_visit_nameopが呼び出されます。 **compiler_visit_nameop [#z0adc0fc] compiler_visit_nameopはスコープによってどのように参照するかのopcodeが変わるようです。今回の場合、スコープはLOCALで、FunctionBlockで、Storeなので、STORE_FASTが使われます。で、最終的に以下のコードが実行されます。 #code(C){{ ADDOP_O(c, op, mangled, varnames); }} ADDOP_Oを追っかけましょう。 #code(C){{ #define ADDOP_O(C, OP, O, TYPE) { \ if (!compiler_addop_o((C), (OP), (C)->u->u_ ## TYPE, (O))) \ return 0; \ } }} OとTYPEがひっくり返るのが地味にめんどくさいです。 #code(C){{ static int compiler_addop_o(struct compiler *c, int opcode, PyObject *dict, PyObject *o) { Py_ssize_t arg = compiler_add_o(c, dict, o); if (arg < 0) return 0; return compiler_addop_i(c, opcode, arg); } static Py_ssize_t compiler_add_o(struct compiler *c, PyObject *dict, PyObject *o) { PyObject *t, *v; Py_ssize_t arg; double d; /* necessary to make sure types aren't coerced (e.g., float and complex) */ /* _and_ to distinguish 0.0 from -0.0 e.g. on IEEE platforms */ if (PyFloat_Check(o)) { // 省略 } else if (PyComplex_Check(o)) { // 省略 } else { t = PyTuple_Pack(2, o, o->ob_type); } v = PyDict_GetItem(dict, t); if (!v) { arg = PyDict_Size(dict); v = PyLong_FromSsize_t(arg); if (PyDict_SetItem(dict, t, v) < 0) { Py_DECREF(t); Py_DECREF(v); return -1; } Py_DECREF(v); } else arg = PyLong_AsLong(v); Py_DECREF(t); return arg; } }} nという名前から0番目というインデックスに置き換えられ、opcodeではそのインデックスを使って変数にアクセスをするようになっています。 **compiler_comprehension_generatorに戻る [#nbe985a6] さて、compiler_comprehension_generatorに戻りましょう。 #code(C){{ /* XXX this needs to be cleaned up...a lot! */ n = asdl_seq_LEN(gen->ifs); for (i = 0; i < n; i++) { expr_ty e = (expr_ty)asdl_seq_GET(gen->ifs, i); VISIT(c, expr, e); ADDOP_JABS(c, POP_JUMP_IF_FALSE, if_cleanup); NEXT_BLOCK(c); } if (++gen_index < asdl_seq_LEN(generators)) if (!compiler_comprehension_generator(c, generators, gen_index, elt, val, type)) return 0; /* only append after the last for generator */ if (gen_index >= asdl_seq_LEN(generators)) { /* comprehension specific code */ switch (type) { case COMP_LISTCOMP: VISIT(c, expr, elt); ADDOP_I(c, LIST_APPEND, gen_index + 1); break; // 他省略 } compiler_use_next_block(c, skip); } compiler_use_next_block(c, if_cleanup); ADDOP_JABS(c, JUMP_ABSOLUTE, start); compiler_use_next_block(c, anchor); return 1; }} まず、ifsの処理をします。今回の場合、以下のASTです。 Compare BinOp Mult Name(n) Load Name(n) Load Gt Num(10) 対応するompile_compareは「0 < x < 10」のように書けるのに対応する分、複雑になっていますがそこをさくっと省略すると非常に素直です。 #code(C){{ static int compiler_compare(struct compiler *c, expr_ty e) { Py_ssize_t i, n; VISIT(c, expr, e->v.Compare.left); n = asdl_seq_LEN(e->v.Compare.ops); VISIT(c, expr, (expr_ty)asdl_seq_GET(e->v.Compare.comparators, n - 1)); ADDOP_I(c, COMPARE_OP, cmpop((cmpop_ty)(asdl_seq_GET(e->v.Compare.ops, n - 1)))); return 1; } }} 左辺を処理して、右辺を処理して、比較を行うということが想像できます。BinOpはもうそんなに難しくないので説明は省くとして、CompareのASTから以下のバイトコードが生成されることになります。 LOAD_FAST 0(n) LOAD_FAST 0(n) BINARY_MULTIPLY LOAD_CONST 10 COMPARE_OP > 0(n)というのはバイトコードの引数としては0が設定される、それが指している変数はn、という意味です。 ifsの処理が終わって、最終的にcompiler_comprehensionの初めに作ったスコープに対応するバイトコードは以下のようになるはずです。 BUILD_LIST 0 LOAD_FAST 0 :start FOR_ITER REL:anchor : STORE_FAST 0(n) LOAD_FAST 0(n) LOAD_FAST 0(n) BINARY_MULTIPLY LOAD_CONST 10 COMPARE_OP > POP_JUMP_IF_FALSE ABS:if_cleanup : LOAD_FAST 0(n) LIST_APPEND 2 :skip :if_cleanup JUMP_ABSOLUTE ABS:start :anchor RETURN_VALUE RELとかABSとか書いてあるのはジャンプです。また、:startなどはblockの先頭のラベルのつもり。見ていて大体わかりますがいまいちわからないところもあるので動作については実行編で確認することにします。 **compiler_comprehensionに戻る [#ge4f6aa3] さてだいぶ長くなってきましたがまだ続きます。compiler_comprehension_generatorから戻ってきた後はassembleが呼び出されていますがそれは後から見ることにしてcompiler_comprehensionの続きは以下の通りです。 #code(C){{ if (!compiler_make_closure(c, co, 0, qualname)) goto error; Py_DECREF(qualname); Py_DECREF(co); VISIT(c, expr, outermost_iter); ADDOP(c, GET_ITER); ADDOP_I(c, CALL_FUNCTION, 1); }} まずはcompiler_make_closure、ブロックの外の変数の取り込みとかを処理していますが今回はないので以下が実行されます。 #code(C){{ static int compiler_make_closure(struct compiler *c, PyCodeObject *co, Py_ssize_t args, PyObject *qualname) { Py_ssize_t i, free = PyCode_GetNumFree(co); if (qualname == NULL) qualname = co->co_name; if (free == 0) { ADDOP_O(c, LOAD_CONST, (PyObject*)co, consts); ADDOP_O(c, LOAD_CONST, qualname, consts); ADDOP_I(c, MAKE_FUNCTION, args); return 1; } } }} 次にoutermost_iterを処理、対応するASTは以下です。 Call Name(Range) Load Num(10) プログラミングの華、関数呼び出しです。対応するのはcompiler_visit_call。 #code(C){{ compiler_call(struct compiler *c, expr_ty e) { VISIT(c, expr, e->v.Call.func); return compiler_call_helper(c, 0, e->v.Call.args, e->v.Call.keywords); } }} compiler_call_helperはキーワード変数など様々な呼び出しの処理が行われていますが今回は単純に10という即値なので中身は省略。 最終的に、compiler_comprehensionが呼ばれて出来上がったバイトコードは以下になります。 LOAD_CONST 内包表記のコード LOAD_CONST <listcomp> MAKE_FUNCTION 0 LOAD_NAME 0(range) LOAD_CONST 10 CALL_FUNCTION 1 GET_ITER CALL_FUNCTION 1 *assemble [#xa027eaf] 最後に、飛ばしたassembleを見ます。assembleは今までに2回出てきました。 -トップレベルに対するassemble -内包表記のスコープに対するassemble このことからスコープに対して最終的なバイトコードを作っていると思われます（とcompile.c先頭のコメントに書いてありますが） assembleのコードは次の通り（一部省略） #code(C){{ static PyCodeObject * assemble(struct compiler *c, int addNone) { basicblock *b, *entryblock; struct assembler a; int i, j, nblocks; PyCodeObject *co = NULL; nblocks = 0; entryblock = NULL; for (b = c->u->u_blocks; b != NULL; b = b->b_list) { nblocks++; entryblock = b; } if (!assemble_init(&a, nblocks, c->u->u_firstlineno)) goto error; dfs(c, entryblock, &a); /* Can't modify the bytecode after computing jump offsets. */ assemble_jump_offsets(&a, c); /* Emit code in reverse postorder from dfs. */ for (i = a.a_nblocks - 1; i >= 0; i--) { b = a.a_postorder[i]; for (j = 0; j < b->b_iused; j++) if (!assemble_emit(&a, &b->b_instr[j])) goto error; } if (_PyBytes_Resize(&a.a_lnotab, a.a_lnotab_off) < 0) goto error; if (_PyBytes_Resize(&a.a_bytecode, a.a_offset) < 0) goto error; co = makecode(c, &a); error: assemble_free(&a); return co; } }} 初期化を除くと初めに呼ばれるのはdfs、depth-first searchです。 #code(C){{ static void dfs(struct compiler *c, basicblock *b, struct assembler *a) { int i; struct instr *instr = NULL; if (b->b_seen) return; b->b_seen = 1; if (b->b_next != NULL) dfs(c, b->b_next, a); for (i = 0; i < b->b_iused; i++) { instr = &b->b_instr[i]; if (instr->i_jrel || instr->i_jabs) dfs(c, instr->i_target, a); } a->a_postorder[a->a_nblocks++] = b; } }} blockを次がある間再帰、次にinstrを見てジャンプが行われていたら飛び先を引数に再帰、この時に未訪問のことがあるのかな？ともかく今回の場合はblockが逆順にpostorderに設定されるようです。 assembleに戻って次に呼んでいるのはassemble_jump_offsets、visitの時点だとblockのポインタとして表現されていたジャンプ先を実際にジャンプする量に変換しています。まあ見ればわかるのでコードは省略。 続いて個々のinstrに対してassemble_emitを呼び出しています。これも地道に数値を埋め込んでいるだけなので省略。 最後にmakecode。簡単な最適化を行ったうえで最終的なPyCodeを作成しています。PyCodeを作る際にスタックの最大深さを計算しているようですがかなり長くなってしまったのでもう終わりにします。まあ実行のイメージを見るだけなら最適化されたコードや厳密なスタックの最大深さは不要でしょう(笑)
