Pythonを読む
compiler_mod (Python/compile.c) †
さて、シンボルテーブル作成が予想以上に長かったですがともかくできたので次のステップです。compile.cの先頭に書かれているコメントを再掲すると、
1
2
3
4
5
6
7
8
9
10
11
12
| -
|
|
|
|
|
|
|
|
|
|
!
|
|
2.まで終わって、次は3.のcompiler_modです。（一部省略して掲載）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
-
|
|
|
-
|
!
|
|
|
-
|
-
|
|
!
|
|
|
|
|
|
|
|
|
|
!
|
|
|
!
| static PyCodeObject *
compiler_mod(struct compiler *c, mod_ty mod)
{
PyCodeObject *co;
int addNone = 1;
static PyObject *module;
if (!module) {
module = PyUnicode_InternFromString("<module>");
}
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構造体の上に書いてあるコメントを掲載。
名前の通り、スコープへのインとアウトを行っています。その際、前回作ったシンボルテーブルの情報を取得しています。
さてというわけでcompiler_enter_scopeはさらっと流して次、VISIT_SEQ_IN_SCOPEです。シンボルテーブル作成でも同じようなのがあったのでもうわかりますが、
1
2
3
4
5
6
7
8
9
10
11
| -
|
|
-
|
-
|
|
!
!
!
| #define VISIT_SEQ_IN_SCOPE(C, TYPE, SEQ) { \
int _i; \
asdl_seq *seq = (SEQ); \
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 †
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です。対応部分を見ると、
1
2
3
4
5
6
7
8
9
10
11
|
-
|
|
!
-
|
|
!
| 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を先に見ておきます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| -
|
|
!
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
!
| #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 †
さて、compiler_visit_exprに進みます。こちらもcompiler_visit_stmt同様switch文なので先に進んで、ListCompなのでcompiler_listcomp経由でcompiler_comprehensionが呼び出されます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
-
|
|
|
|
|
|
|
|
|
|
|
-
|
-
|
|
|
-
!
|
|
!
-
|
!
!
| 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 †
まずはcompiler_comprehension_generatorを見てみましょう。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
-
-
!
|
|
|
|
|
|
|
|
|
|
|
|
-
|
|
|
!
-
|
|
|
!
|
|
|
|
|
|
|
-
|
|
|
|
!
|
|
|
|
|
|
|
|
-
|
-
|
|
|
|
-
!
|
|
!
!
| static int
compiler_comprehension_generator(struct compiler *c,
asdl_seq *generators, int gen_index,
expr_ty elt, expr_ty val, int type)
{
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) {
c->u->u_argcount = 1;
ADDOP_I(c, LOAD_FAST, 0);
}
else {
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);
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;
if (gen_index >= asdl_seq_LEN(generators)) {
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が作成されています。そして、
1
2
3
4
|
| 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 †
compiler_visit_nameopはスコープによってどのように参照するかのopcodeが変わるようです。今回の場合、スコープはLOCALで、FunctionBlockで、Storeなので、STORE_FASTが使われます。で、最終的に以下のコードが実行されます。
1
|
| ADDOP_O(c, op, mangled, varnames);
|
ADDOP_Oを追っかけましょう。
1
2
3
4
| -
|
|
!
| #define ADDOP_O(C, OP, O, TYPE) { \
if (!compiler_addop_o((C), (OP), (C)->u->u_ ## TYPE, (O))) \
return 0; \
}
|
OとTYPEがひっくり返るのが地味にめんどくさいです。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
-
|
|
|
|
!
-
|
|
|
|
|
|
-
-
!
-
-
!
-
!
|
|
-
-
|
|
|
!
!
|
|
|
|
!
| 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;
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に戻る †
さて、compiler_comprehension_generatorに戻りましょう。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
-
|
|
|
|
!
-
|
-
|
|
|
|
-
!
!
|
|
|
|
|
|
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;
if (gen_index >= asdl_seq_LEN(generators)) {
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」のように書けるのに対応する分、複雑になっていますがそこをさくっと省略すると非常に素直です。
1
2
3
4
5
6
7
8
9
10
11
|
-
|
|
|
|
|
|
|
!
| 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に戻る †
さてだいぶ長くなってきましたがまだ続きます。compiler_comprehension_generatorから戻ってきた後はassembleが呼び出されていますがそれは後から見ることにしてcompiler_comprehensionの続きは以下の通りです。
1
2
3
4
5
6
7
8
|
| 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、ブロックの外の変数の取り込みとかを処理していますが今回はないので以下が実行されます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
-
|
|
|
|
-
|
|
|
|
!
!
| 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。
1
2
3
4
5
|
-
|
|
!
| 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 †
最後に、飛ばしたassembleを見ます。assembleは今までに2回出てきました。
- トップレベルに対するassemble
- 内包表記のスコープに対するassemble
このことからスコープに対して最終的なバイトコードを作っていると思われます（とcompile.c先頭のコメントに書いてありますが）
assembleのコードは次の通り（一部省略）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
-
|
|
|
|
|
|
|
-
|
|
!
|
|
|
|
|
|
|
|
|
-
|
|
|
|
!
|
|
|
|
|
|
|
|
|
|
!
| 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);
assemble_jump_offsets(&a, c);
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です。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
-
|
|
|
|
|
|
|
|
-
|
|
|
!
|
!
| 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を作る際にスタックの最大深さを計算しているようですがかなり長くなってしまったのでもう終わりにします。まあ実行のイメージを見るだけなら最適化されたコードや厳密なスタックの最大深さは不要でしょう(笑)
|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
