Skip to content

gh-95335: extract 'struct cfg_builder' from the compiler so that the CFG can be manipulated directly #95107

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
iritkatriel merged 11 commits into from
Jul 26, 2022
Merged

gh-95335: extract 'struct cfg_builder' from the compiler so that the CFG can be manipulated directly #95107

Changes from 1 commit
Commits
Show all changes
11 commits
Select commit Hold shift + click to select a range
98b4902
gh-93678: extract 'struct cfg' from the compiler so that the CFG can …
iritkatriel Jul 21, 2022
4bbebf8
add two missing static qualifiers
iritkatriel Jul 21, 2022
7984b09
add entryblock field to cfg struct
iritkatriel Jul 24, 2022
43fa292
remove basicblock_new_b_list_successor and use cfg_new_block instead
iritkatriel Jul 24, 2022
1e7d1df
inline new_basicblock - it's called in onyl one place now and it's no…
iritkatriel Jul 25, 2022
e943cc2
rename cfg --> cfg_builder, entryblock field --> cfg
iritkatriel Jul 25, 2022
f7ba9e8
📜🤖 Added by blurb_it.
blurb-it[bot] Jul 26, 2022
c3e767a
Merge branch 'main' into cfg_struct
iritkatriel Jul 26, 2022
5a6dc5d
cfg --> cfg_entryblock
iritkatriel Jul 26, 2022
3a8436e
remove obsolete comment
iritkatriel Jul 26, 2022
873d34f
pass location by value
iritkatriel Jul 26, 2022
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
rename cfg --> cfg_builder, entryblock field --> cfg
  • Loading branch information
@iritkatriel
iritkatriel committed Jul 25, 2022
commit e943cc2f4ec47944772873ccc380cad0f030f6cf
113 changes: 58 additions & 55 deletions Python/compile.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -325,13 +325,16 @@ enum {
COMPILER_SCOPE_COMPREHENSION,
};

typedef struct cfg_ {
basicblock *entryblock; /* Where control flow begins */
typedef struct cfg_builder_ {
/* The entryblock, at which control flow begins. All blocks of the
CFG are reachable through the b_next links */
basicblock *cfg;
/* Pointer to the most recently allocated block. By following
b_list links, you can reach all allocated blocks. */
basicblock *block_list;
basicblock *curblock; /* pointer to current block */
} cfg;
/* pointer to the block currently being constructed */
basicblock *curblock;
} cfg_builder;

/* The following items change on entry and exit of code blocks.
They must be saved and restored when returning to a block.
Expand Down Expand Up @@ -361,7 +364,7 @@ struct compiler_unit {
/* Pointer to the most recently allocated block. By following b_list
members, you can reach all early allocated blocks. */

cfg u_cfg; /* The control flow graph */
cfg_builder u_cfg_builder; /* The control flow graph */

int u_nfblocks;
struct fblockinfo u_fblock[CO_MAXBLOCKS];
Expand Down Expand Up @@ -398,7 +401,7 @@ struct compiler {
PyArena *c_arena; /* pointer to memory allocation arena */
};

#define CFG(c) (&((c)->u->u_cfg))
#define CFG_BUILDER(c) (&((c)->u->u_cfg_builder))
#define COMPILER_LOC(c) (&((c)->u->u_loc))

typedef struct {
Expand Down Expand Up @@ -428,7 +431,7 @@ typedef struct {

static int basicblock_next_instr(basicblock *);

static int cfg_addop_i(cfg *g, int opcode, Py_ssize_t oparg, const struct location *loc);
static int cfg_builder_addop_i(cfg_builder *g, int opcode, Py_ssize_t oparg, const struct location *loc);

static void compiler_free(struct compiler *);
static int compiler_error(struct compiler *, const char *, ...);
Expand Down Expand Up @@ -721,7 +724,7 @@ dictbytype(PyObject *src, int scope_type, int flag, Py_ssize_t offset)
}

static void
cfg_check(cfg *g)
cfg_builder_check(cfg_builder *g)
{
for (basicblock *block = g->block_list; block != NULL; block = block->b_list) {
assert(!_PyMem_IsPtrFreed(block));
Expand All @@ -738,9 +741,9 @@ cfg_check(cfg *g)
}

static void
cfg_free(cfg* g)
cfg_builder_free(cfg_builder* g)
{
cfg_check(g);
cfg_builder_check(g);
basicblock *b = g->block_list;
while (b != NULL) {
if (b->b_instr) {
Expand All @@ -755,7 +758,7 @@ cfg_free(cfg* g)
static void
compiler_unit_free(struct compiler_unit *u)
{
cfg_free(&u->u_cfg);
cfg_builder_free(&u->u_cfg_builder);
Py_CLEAR(u->u_ste);
Py_CLEAR(u->u_name);
Py_CLEAR(u->u_qualname);
Expand Down Expand Up @@ -843,7 +846,7 @@ compiler_set_qualname(struct compiler *c)
Returns NULL on error.
*/
static basicblock *
cfg_new_block(cfg *g)
cfg_builder_new_block(cfg_builder *g)
{
basicblock *b = (basicblock *)PyObject_Calloc(1, sizeof(basicblock));
if (b == NULL) {
Expand All @@ -857,7 +860,7 @@ cfg_new_block(cfg *g)
}

static basicblock *
cfg_use_next_block(cfg *g, basicblock *block)
cfg_builder_use_next_block(cfg_builder *g, basicblock *block)
{
assert(block != NULL);
g->curblock->b_next = block;
Expand All @@ -868,23 +871,23 @@ cfg_use_next_block(cfg *g, basicblock *block)
static basicblock *
compiler_new_block(struct compiler *c)
{
return cfg_new_block(CFG(c));
return cfg_builder_new_block(CFG_BUILDER(c));
}

static basicblock *
compiler_use_next_block(struct compiler *c, basicblock *block)
{
return cfg_use_next_block(CFG(c), block);
return cfg_builder_use_next_block(CFG_BUILDER(c), block);
}

static basicblock *
copy_basicblock(cfg *g, basicblock *block)
copy_basicblock(cfg_builder *g, basicblock *block)
{
/* Cannot copy a block if it has a fallthrough, since
* a block can only have one fallthrough predecessor.
*/
assert(BB_NO_FALLTHROUGH(block));
basicblock *result = cfg_new_block(g);
basicblock *result = cfg_builder_new_block(g);
if (result == NULL) {
return NULL;
}
Expand Down Expand Up @@ -1278,25 +1281,25 @@ basicblock_addop(basicblock *b, int opcode, int oparg,
}

static int
cfg_addop(cfg *g, int opcode, int oparg, basicblock *target,
cfg_builder_addop(cfg_builder *g, int opcode, int oparg, basicblock *target,
const struct location *loc)
{
struct instr *last = basicblock_last_instr(g->curblock);
if (last && IS_TERMINATOR_OPCODE(last->i_opcode)) {
basicblock *b = cfg_new_block(g);
basicblock *b = cfg_builder_new_block(g);
if (b == NULL) {
return -1;
}
cfg_use_next_block(g, b);
cfg_builder_use_next_block(g, b);
}
return basicblock_addop(g->curblock, opcode, oparg, target, loc);
}

static int
cfg_addop_noarg(cfg *g, int opcode, const struct location *loc)
cfg_builder_addop_noarg(cfg_builder *g, int opcode, const struct location *loc)
{
assert(!HAS_ARG(opcode));
return cfg_addop(g, opcode, 0, NULL, loc);
return cfg_builder_addop(g, opcode, 0, NULL, loc);
}

static Py_ssize_t
Expand Down Expand Up @@ -1456,7 +1459,7 @@ compiler_addop_load_const(struct compiler *c, PyObject *o)
Py_ssize_t arg = compiler_add_const(c, o);
if (arg < 0)
return 0;
return cfg_addop_i(CFG(c), LOAD_CONST, arg, COMPILER_LOC(c));
return cfg_builder_addop_i(CFG_BUILDER(c), LOAD_CONST, arg, COMPILER_LOC(c));
}

static int
Expand All @@ -1466,7 +1469,7 @@ compiler_addop_o(struct compiler *c, int opcode, PyObject *dict,
Py_ssize_t arg = dict_add_o(dict, o);
if (arg < 0)
return 0;
return cfg_addop_i(CFG(c), opcode, arg, COMPILER_LOC(c));
return cfg_builder_addop_i(CFG_BUILDER(c), opcode, arg, COMPILER_LOC(c));
}

static int
Expand All @@ -1490,14 +1493,14 @@ compiler_addop_name(struct compiler *c, int opcode, PyObject *dict,
arg <<= 1;
arg |= 1;
}
return cfg_addop_i(CFG(c), opcode, arg, COMPILER_LOC(c));
return cfg_builder_addop_i(CFG_BUILDER(c), opcode, arg, COMPILER_LOC(c));
}

/* Add an opcode with an integer argument.
Returns 0 on failure, 1 on success.
*/
static int
cfg_addop_i(cfg *g, int opcode, Py_ssize_t oparg, const struct location *loc)
cfg_builder_addop_i(cfg_builder *g, int opcode, Py_ssize_t oparg, const struct location *loc)
{
/* oparg value is unsigned, but a signed C int is usually used to store
it in the C code (like Python/ceval.c).
Expand All @@ -1508,30 +1511,30 @@ cfg_addop_i(cfg *g, int opcode, Py_ssize_t oparg, const struct location *loc)
EXTENDED_ARG is used for 16, 24, and 32-bit arguments. */

int oparg_ = Py_SAFE_DOWNCAST(oparg, Py_ssize_t, int);
return cfg_addop(g, opcode, oparg_, NULL, loc);
return cfg_builder_addop(g, opcode, oparg_, NULL, loc);
}

static int
cfg_addop_j(cfg *g, int opcode, basicblock *target, const struct location *loc)
cfg_builder_addop_j(cfg_builder *g, int opcode, basicblock *target, const struct location *loc)
{
assert(target != NULL);
assert(IS_JUMP_OPCODE(opcode) || IS_BLOCK_PUSH_OPCODE(opcode));
return cfg_addop(g, opcode, 0, target, loc);
return cfg_builder_addop(g, opcode, 0, target, loc);
}


#define ADDOP(C, OP) { \
if (!cfg_addop_noarg(CFG(C), (OP), COMPILER_LOC(C))) \
if (!cfg_builder_addop_noarg(CFG_BUILDER(C), (OP), COMPILER_LOC(C))) \
return 0; \
}

#define ADDOP_NOLINE(C, OP) { \
if (!cfg_addop_noarg(CFG(C), (OP), NULL)) \
if (!cfg_builder_addop_noarg(CFG_BUILDER(C), (OP), NULL)) \
return 0; \
}

#define ADDOP_IN_SCOPE(C, OP) { \
if (!cfg_addop_noarg(CFG(C), (OP), COMPILER_LOC(C))) { \
if (!cfg_builder_addop_noarg(CFG_BUILDER(C), (OP), COMPILER_LOC(C))) { \
compiler_exit_scope(c); \
return 0; \
} \
Expand Down Expand Up @@ -1570,25 +1573,25 @@ cfg_addop_j(cfg *g, int opcode, basicblock *target, const struct location *loc)
}

#define ADDOP_I(C, OP, O) { \
if (!cfg_addop_i(CFG(C), (OP), (O), COMPILER_LOC(C))) \
if (!cfg_builder_addop_i(CFG_BUILDER(C), (OP), (O), COMPILER_LOC(C))) \
return 0; \
}

#define ADDOP_I_NOLINE(C, OP, O) { \
if (!cfg_addop_i(CFG(C), (OP), (O), NULL)) \
if (!cfg_builder_addop_i(CFG_BUILDER(C), (OP), (O), NULL)) \
return 0; \
}

#define ADDOP_JUMP(C, OP, O) { \
if (!cfg_addop_j(CFG(C), (OP), (O), COMPILER_LOC(C))) \
if (!cfg_builder_addop_j(CFG_BUILDER(C), (OP), (O), COMPILER_LOC(C))) \
return 0; \
}

/* Add a jump with no line number.
* Used for artificial jumps that have no corresponding
* token in the source code. */
#define ADDOP_JUMP_NOLINE(C, OP, O) { \
if (!cfg_addop_j(CFG(C), (OP), (O), NULL)) \
if (!cfg_builder_addop_j(CFG_BUILDER(C), (OP), (O), NULL)) \
return 0; \
}

Expand Down Expand Up @@ -1737,12 +1740,12 @@ compiler_enter_scope(struct compiler *c, identifier name,

c->c_nestlevel++;

cfg *g = CFG(c);
cfg_builder *g = CFG_BUILDER(c);
g->block_list = NULL;
block = cfg_new_block(g);
block = cfg_builder_new_block(g);
if (block == NULL)
return 0;
g->curblock = g->entryblock = block;
g->curblock = g->cfg = block;

if (u->u_scope_type == COMPILER_SCOPE_MODULE) {
c->u->u_loc.lineno = 0;
Expand Down Expand Up @@ -1779,7 +1782,7 @@ compiler_exit_scope(struct compiler *c)
_PyErr_WriteUnraisableMsg("on removing the last compiler "
"stack item", NULL);
}
cfg_check(CFG(c));
cfg_builder_check(CFG_BUILDER(c));
}
else {
c->u = NULL;
Expand Down Expand Up @@ -4236,7 +4239,7 @@ compiler_nameop(struct compiler *c, identifier name, expr_context_ty ctx)
if (op == LOAD_GLOBAL) {
arg <<= 1;
}
return cfg_addop_i(CFG(c), op, arg, COMPILER_LOC(c));
return cfg_builder_addop_i(CFG_BUILDER(c), op, arg, COMPILER_LOC(c));
}

static int
Expand Down Expand Up @@ -6276,7 +6279,7 @@ emit_and_reset_fail_pop(struct compiler *c, pattern_context *pc)
}
while (--pc->fail_pop_size) {
compiler_use_next_block(c, pc->fail_pop[pc->fail_pop_size]);
if (!cfg_addop_noarg(CFG(c), POP_TOP, COMPILER_LOC(c))) {
if (!cfg_builder_addop_noarg(CFG_BUILDER(c), POP_TOP, COMPILER_LOC(c))) {
pc->fail_pop_size = 0;
PyObject_Free(pc->fail_pop);
pc->fail_pop = NULL;
Expand Down Expand Up @@ -6710,7 +6713,7 @@ compiler_pattern_or(struct compiler *c, pattern_ty p, pattern_context *pc)
pc->fail_pop = NULL;
pc->fail_pop_size = 0;
pc->on_top = 0;
if (!cfg_addop_i(CFG(c), COPY, 1, COMPILER_LOC(c)) ||
if (!cfg_builder_addop_i(CFG_BUILDER(c), COPY, 1, COMPILER_LOC(c)) ||
!compiler_pattern(c, alt, pc)) {
goto error;
}
Expand Down Expand Up @@ -6774,7 +6777,7 @@ compiler_pattern_or(struct compiler *c, pattern_ty p, pattern_context *pc)
}
}
assert(control);
if (!cfg_addop_j(CFG(c), JUMP, end, COMPILER_LOC(c)) ||
if (!cfg_builder_addop_j(CFG_BUILDER(c), JUMP, end, COMPILER_LOC(c)) ||
!emit_and_reset_fail_pop(c, pc))
{
goto error;
Expand All @@ -6786,7 +6789,7 @@ compiler_pattern_or(struct compiler *c, pattern_ty p, pattern_context *pc)
// Need to NULL this for the PyObject_Free call in the error block.
old_pc.fail_pop = NULL;
// No match. Pop the remaining copy of the subject and fail:
if (!cfg_addop_noarg(CFG(c), POP_TOP, COMPILER_LOC(c)) || !jump_to_fail_pop(c, pc, JUMP)) {
if (!cfg_builder_addop_noarg(CFG_BUILDER(c), POP_TOP, COMPILER_LOC(c)) || !jump_to_fail_pop(c, pc, JUMP)) {
goto error;
}
compiler_use_next_block(c, end);
Expand Down Expand Up @@ -7416,8 +7419,8 @@ mark_cold(basicblock *entryblock) {
}

static int
push_cold_blocks_to_end(cfg *g, int code_flags) {
basicblock *entryblock = g->entryblock;
push_cold_blocks_to_end(cfg_builder *g, int code_flags) {
basicblock *entryblock = g->cfg;
if (entryblock->b_next == NULL) {
/* single basicblock, no need to reorder */
return 0;
Expand All @@ -7430,7 +7433,7 @@ push_cold_blocks_to_end(cfg *g, int code_flags) {
/* an explicit jump instead of fallthrough */
for (basicblock *b = entryblock; b != NULL; b = b->b_next) {
if (b->b_cold && BB_HAS_FALLTHROUGH(b) && b->b_next && b->b_next->b_warm) {
basicblock *explicit_jump = cfg_new_block(g);
basicblock *explicit_jump = cfg_builder_new_block(g);
if (explicit_jump == NULL) {
return -1;
}
Expand Down Expand Up @@ -8283,7 +8286,7 @@ trim_unused_consts(basicblock *entryblock, PyObject *consts);

/* Duplicates exit BBs, so that line numbers can be propagated to them */
static int
duplicate_exits_without_lineno(cfg *g);
duplicate_exits_without_lineno(cfg_builder *g);

static int
extend_block(basicblock *bb);
Expand Down Expand Up @@ -8534,7 +8537,7 @@ assemble(struct compiler *c, int addNone)
}

/* Make sure every block that falls off the end returns None. */
if (!basicblock_returns(CFG(c)->curblock)) {
if (!basicblock_returns(CFG_BUILDER(c)->curblock)) {
UNSET_LOC(c);
if (addNone)
ADDOP_LOAD_CONST(c, Py_None);
Expand All @@ -8556,16 +8559,16 @@ assemble(struct compiler *c, int addNone)
}

int nblocks = 0;
for (basicblock *b = CFG(c)->block_list; b != NULL; b = b->b_list) {
for (basicblock *b = CFG_BUILDER(c)->block_list; b != NULL; b = b->b_list) {
nblocks++;
}
if ((size_t)nblocks > SIZE_MAX / sizeof(basicblock *)) {
PyErr_NoMemory();
goto error;
}

cfg *g = CFG(c);
basicblock *entryblock = g->entryblock;
cfg_builder *g = CFG_BUILDER(c);
basicblock *entryblock = g->cfg;
assert(entryblock != NULL);

/* Set firstlineno if it wasn't explicitly set. */
Expand Down Expand Up @@ -9538,11 +9541,11 @@ is_exit_without_lineno(basicblock *b) {
* copy the line number from the sole predecessor block.
*/
static int
duplicate_exits_without_lineno(cfg *g)
duplicate_exits_without_lineno(cfg_builder *g)
{
/* Copy all exit blocks without line number that are targets of a jump.
*/
basicblock *entryblock = g->entryblock;
basicblock *entryblock = g->cfg;
for (basicblock *b = entryblock; b != NULL; b = b->b_next) {
if (b->b_iused > 0 && is_jump(&b->b_instr[b->b_iused-1])) {
basicblock *target = b->b_instr[b->b_iused-1].i_target;
Expand Down