bpo-31113: Get rid of recursion in the compiler for normal control flow.#3015
bpo-31113: Get rid of recursion in the compiler for normal control flow.#3015serhiy-storchaka merged 12 commits intopython:masterfrom
Conversation
Lib/test/test_compile.py
Outdated
| compile("42", PathLike("test_compile_pathlike"), "single") | ||
|
|
||
| def test_dfs_next(self): | ||
| # Issue #31113: Stack overflow when compile a long sequence of |
There was a problem hiding this comment.
Please use the new "bpo-xxx" format.
| for (j = nblocks; b && !b->b_seen; b = b->b_next) { | ||
| b->b_seen = 1; | ||
| assert(a->a_nblocks < j); | ||
| a->a_postorder[--j] = b; |
There was a problem hiding this comment.
This only works because blocks are emitted in topological order, right? It would be nice to add a comment.
There was a problem hiding this comment.
Or are you using a_postorder as a stack or worklist?
There was a problem hiding this comment.
Yes, since the number of blocks is limited, the space at the end of a_postorder can be used as a stack.
Python/compile.c
Outdated
| while (j < nblocks) { | ||
| b = a->a_postorder[j++]; | ||
| for (i = 0; i < b->b_iused; i++) { | ||
| struct instr *instr = instr = &b->b_instr[i]; |
There was a problem hiding this comment.
I don't understand the struct instr *instr = instr part.
There was a problem hiding this comment.
Good catch! This is just a copying error.
|
It's telling that you're still getting a stack overflow on Windows :-) |
| dfs(c, instr->i_target, a); | ||
| int i, j; | ||
|
|
||
| /* Get rid of recursion for normal control flow. |
There was a problem hiding this comment.
Perhaps it is possible to get rid of recursion entirely -- perhaps by allocating a separate stack? Or is it unlikely to have a stack overflow though i_target?
There was a problem hiding this comment.
Perhaps, though this likely will complicate the code. I don't have an example that overflows a stack though i_target. After getting such example I'll try to get rid of recursion entirely.
Python/compile.c
Outdated
| int i; | ||
| basicblock *next; | ||
| b = sp[-1]; | ||
| if (b->b_seen == 2) { |
There was a problem hiding this comment.
Perhaps add some comment as to the different values of b_seen? Does 1 mean "queued for processing" and 2 "already processed"?
| if (instr->i_jrel || instr->i_jabs) | ||
| dfs(c, instr->i_target, a, j); | ||
| } | ||
| a->a_postorder[a->a_nblocks++] = b; |
There was a problem hiding this comment.
Can we add something like assert(a->a_nblocks <= j) here? The stack trick is smart but I'd like to make sure it's not buggy.
Python/compile.c
Outdated
| while (sp != stack) { | ||
| int i; | ||
| basicblock *next; | ||
| b = sp[-1]; |
There was a problem hiding this comment.
Why don't we decrement sp here instead of setting b->b_seen = 2 below?
There was a problem hiding this comment.
This is closer to the current implementation. If just pop a block from the stack and keep b->b_seen == 1, all seems working, but the result is different. I don't know what result is more correct, but larger depth is safer. Clearing b->b_seen after popping a block causes an infinite loop. Current code contains bugs (see bpo-24340), may be after fixing them this code could be simplified.
|
What is the status of this? |
|
I'm wary of backporting this and would prefer it to be 3.7-only. |
|
I think a good experiment would be to take the PR for bpo-17611 and make it non-recursive. It should be similar to this PR in principle. |
4 participants
https://bugs.python.org/issue31113