Skip to content

bpo-42246: Eliminate jumps to exit blocks by copying those blocks. #23251

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
markshannon merged 5 commits into from
Nov 12, 2020
Merged

bpo-42246: Eliminate jumps to exit blocks by copying those blocks. #23251

Changes from 1 commit
Commits
Show all changes
5 commits
Select commit Hold shift + click to select a range
ed97b68
Leave b_next pointer, mark basic blocks as exit and/or no fallthrough.
markshannon Nov 12, 2020
4b470d9
Remove redundant array from assembler.
markshannon Nov 12, 2020
a861abc
Compiler: eliminate jumps to short exit blocks by copying.
markshannon Nov 12, 2020
3f021fa
Fix up dis test.
markshannon Nov 12, 2020
0d2af11
Update importlib.
markshannon Nov 12, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Remove redundant array from assembler.
  • Loading branch information
@markshannon
markshannon committed Nov 12, 2020
commit 4b470d988c0edfc136a8a6e4e6cf4a60f014a2d3
61 changes: 19 additions & 42 deletions Python/compile.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -5438,28 +5438,14 @@ struct assembler {
PyObject *a_bytecode; /* string containing bytecode */
int a_offset; /* offset into bytecode */
int a_nblocks; /* number of reachable blocks */
basicblock **a_reverse_postorder; /* list of blocks in dfs postorder */
PyObject *a_lnotab; /* string containing lnotab */
int a_lnotab_off; /* offset into lnotab */
int a_prevlineno; /* lineno of last emitted line in line table */
int a_lineno; /* lineno of last emitted instruction */
int a_lineno_start; /* bytecode start offset of current lineno */
basicblock *a_entry;
};

static void
dfs(struct compiler *c, basicblock *b, struct assembler *a, int end)
{

/* There is no real depth-first-search to do here because all the
* blocks are emitted in topological order already, so we just need to
* follow the b_next pointers and place them in a->a_reverse_postorder in
* reverse order and make sure that the first one starts at 0. */

for (a->a_nblocks = 0; b != NULL; b = b->b_next) {
a->a_reverse_postorder[a->a_nblocks++] = b;
}
}

Py_LOCAL_INLINE(void)
stackdepth_push(basicblock ***sp, basicblock *b, int depth)
{
Expand Down Expand Up @@ -5557,12 +5543,7 @@ assemble_init(struct assembler *a, int nblocks, int firstlineno)
PyErr_NoMemory();
return 0;
}
a->a_reverse_postorder = (basicblock **)PyObject_Malloc(
sizeof(basicblock *) * nblocks);
if (!a->a_reverse_postorder) {
PyErr_NoMemory();
return 0;
}

return 1;
}

Expand All @@ -5571,8 +5552,6 @@ assemble_free(struct assembler *a)
{
Py_XDECREF(a->a_bytecode);
Py_XDECREF(a->a_lnotab);
if (a->a_reverse_postorder)
PyObject_Free(a->a_reverse_postorder);
}

static int
Expand Down Expand Up @@ -5701,8 +5680,7 @@ assemble_jump_offsets(struct assembler *a, struct compiler *c)
Replace block pointer with position in bytecode. */
do {
totsize = 0;
for (i = 0; i < a->a_nblocks; i++) {
b = a->a_reverse_postorder[i];
for (basicblock *b = a->a_entry; b != NULL; b = b->b_next) {
bsize = blocksize(b);
b->b_offset = totsize;
totsize += bsize;
Expand Down Expand Up @@ -5970,7 +5948,7 @@ assemble(struct compiler *c, int addNone)
{
basicblock *b, *entryblock;
struct assembler a;
int i, j, nblocks;
int j, nblocks;
PyCodeObject *co = NULL;
PyObject *consts = NULL;

Expand Down Expand Up @@ -6001,7 +5979,8 @@ assemble(struct compiler *c, int addNone)
}
if (!assemble_init(&a, nblocks, c->u->u_firstlineno))
goto error;
dfs(c, entryblock, &a, nblocks);
a.a_entry = entryblock;
a.a_nblocks = nblocks;

consts = consts_dict_keys_inorder(c->u->u_consts);
if (consts == NULL) {
Expand All @@ -6014,9 +5993,8 @@ assemble(struct compiler *c, int addNone)
/* Can't modify the bytecode after computing jump offsets. */
assemble_jump_offsets(&a, c);

/* Emit code in reverse postorder from dfs. */
for (i = 0; i < a.a_nblocks; i++) {
b = a.a_reverse_postorder[i];
/* Emit code. */
for(b = entryblock; b != NULL; b = b->b_next) {
for (j = 0; j < b->b_iused; j++)
if (!assemble_emit(&a, &b->b_instr[j]))
goto error;
Expand Down Expand Up @@ -6330,9 +6308,8 @@ mark_reachable(struct assembler *a) {
if (stack == NULL) {
return -1;
}
basicblock *entry = a->a_reverse_postorder[0];
entry->b_reachable = 1;
*sp++ = entry;
a->a_entry->b_reachable = 1;
*sp++ = a->a_entry;
while (sp > stack) {
basicblock *b = *(--sp);
if (b->b_next && !b->b_nofallthrough && b->b_next->b_reachable == 0) {
Expand Down Expand Up @@ -6367,23 +6344,23 @@ mark_reachable(struct assembler *a) {
static int
optimize_cfg(struct assembler *a, PyObject *consts)
{
for (int i = 0; i < a->a_nblocks; i++) {
normalise_basic_block(a->a_reverse_postorder[i]);
for (basicblock *b = a->a_entry; b != NULL; b = b->b_next) {
normalise_basic_block(b);
}
for (int i = 0; i < a->a_nblocks; i++) {
if (optimize_basic_block(a->a_reverse_postorder[i], consts)) {
for (basicblock *b = a->a_entry; b != NULL; b = b->b_next) {
if (optimize_basic_block(b, consts)) {
return -1;
}
clean_basic_block(a->a_reverse_postorder[i]);
assert(a->a_reverse_postorder[i]->b_reachable == 0);
clean_basic_block(b);
assert(b->b_reachable == 0);
}
if (mark_reachable(a)) {
return -1;
}
/* Delete unreachable instructions */
for (int i = 0; i < a->a_nblocks; i++) {
if (a->a_reverse_postorder[i]->b_reachable == 0) {
a->a_reverse_postorder[i]->b_iused = 0;
for (basicblock *b = a->a_entry; b != NULL; b = b->b_next) {
if (b->b_reachable == 0) {
b->b_iused = 0;
}
}
return 0;
Expand Down