diff options
Diffstat (limited to 'contrib/tools/python3/Python/flowgraph.c')
| -rw-r--r-- | contrib/tools/python3/Python/flowgraph.c | 1483 |
1 files changed, 1019 insertions, 464 deletions
diff --git a/contrib/tools/python3/Python/flowgraph.c b/contrib/tools/python3/Python/flowgraph.c index fbbe053ae58..ecf510842ea 100644 --- a/contrib/tools/python3/Python/flowgraph.c +++ b/contrib/tools/python3/Python/flowgraph.c @@ -1,15 +1,12 @@ - -#include <stdbool.h> - #include "Python.h" #include "pycore_flowgraph.h" #include "pycore_compile.h" #include "pycore_pymem.h" // _PyMem_IsPtrFreed() #include "pycore_opcode_utils.h" -#define NEED_OPCODE_METADATA -#include "opcode_metadata.h" // _PyOpcode_opcode_metadata, _PyOpcode_num_popped/pushed -#undef NEED_OPCODE_METADATA +#include "pycore_opcode_metadata.h" // OPCODE_HAS_ARG, etc + +#include <stdbool.h> #undef SUCCESS @@ -24,35 +21,96 @@ #define DEFAULT_BLOCK_SIZE 16 -typedef _PyCompilerSrcLocation location; -typedef _PyCfgJumpTargetLabel jump_target_label; -typedef _PyCfgBasicblock basicblock; -typedef _PyCfgBuilder cfg_builder; -typedef _PyCfgInstruction cfg_instr; +typedef _Py_SourceLocation location; +typedef _PyJumpTargetLabel jump_target_label; + +typedef struct _PyCfgInstruction { + int i_opcode; + int i_oparg; + _Py_SourceLocation i_loc; + struct _PyCfgBasicblock *i_target; /* target block (if jump instruction) */ + struct _PyCfgBasicblock *i_except; /* target block when exception is raised */ +} cfg_instr; + +typedef struct _PyCfgBasicblock { + /* Each basicblock in a compilation unit is linked via b_list in the + reverse order that the block are allocated. b_list points to the next + block in this list, not to be confused with b_next, which is next by + control flow. */ + struct _PyCfgBasicblock *b_list; + /* The label of this block if it is a jump target, -1 otherwise */ + _PyJumpTargetLabel b_label; + /* Exception stack at start of block, used by assembler to create the exception handling table */ + struct _PyCfgExceptStack *b_exceptstack; + /* pointer to an array of instructions, initially NULL */ + cfg_instr *b_instr; + /* If b_next is non-NULL, it is a pointer to the next + block reached by normal control flow. */ + struct _PyCfgBasicblock *b_next; + /* number of instructions used */ + int b_iused; + /* length of instruction array (b_instr) */ + int b_ialloc; + /* Used by add_checks_for_loads_of_unknown_variables */ + uint64_t b_unsafe_locals_mask; + /* Number of predecessors that a block has. */ + int b_predecessors; + /* depth of stack upon entry of block, computed by stackdepth() */ + int b_startdepth; + /* Basic block is an exception handler that preserves lasti */ + unsigned b_preserve_lasti : 1; + /* Used by compiler passes to mark whether they have visited a basic block. */ + unsigned b_visited : 1; + /* b_except_handler is used by the cold-detection algorithm to mark exception targets */ + unsigned b_except_handler : 1; + /* b_cold is true if this block is not perf critical (like an exception handler) */ + unsigned b_cold : 1; + /* b_warm is used by the cold-detection algorithm to mark blocks which are definitely not cold */ + unsigned b_warm : 1; +} basicblock; + + +struct _PyCfgBuilder { + /* The entryblock, at which control flow begins. All blocks of the + CFG are reachable through the b_next links */ + struct _PyCfgBasicblock *g_entryblock; + /* Pointer to the most recently allocated block. By following + b_list links, you can reach all allocated blocks. */ + struct _PyCfgBasicblock *g_block_list; + /* pointer to the block currently being constructed */ + struct _PyCfgBasicblock *g_curblock; + /* label for the next instruction to be placed */ + _PyJumpTargetLabel g_current_label; +}; + +typedef struct _PyCfgBuilder cfg_builder; static const jump_target_label NO_LABEL = {-1}; #define SAME_LABEL(L1, L2) ((L1).id == (L2).id) #define IS_LABEL(L) (!SAME_LABEL((L), (NO_LABEL))) +#define LOCATION(LNO, END_LNO, COL, END_COL) \ + ((const _Py_SourceLocation){(LNO), (END_LNO), (COL), (END_COL)}) static inline int is_block_push(cfg_instr *i) { + assert(OPCODE_HAS_ARG(i->i_opcode) || !IS_BLOCK_PUSH_OPCODE(i->i_opcode)); return IS_BLOCK_PUSH_OPCODE(i->i_opcode); } static inline int is_jump(cfg_instr *i) { - return IS_JUMP_OPCODE(i->i_opcode); + return OPCODE_HAS_JUMP(i->i_opcode); } /* One arg*/ #define INSTR_SET_OP1(I, OP, ARG) \ do { \ - assert(HAS_ARG(OP)); \ - _PyCfgInstruction *_instr__ptr_ = (I); \ + assert(OPCODE_HAS_ARG(OP)); \ + cfg_instr *_instr__ptr_ = (I); \ _instr__ptr_->i_opcode = (OP); \ _instr__ptr_->i_oparg = (ARG); \ } while (0); @@ -60,8 +118,8 @@ is_jump(cfg_instr *i) /* No args*/ #define INSTR_SET_OP0(I, OP) \ do { \ - assert(!HAS_ARG(OP)); \ - _PyCfgInstruction *_instr__ptr_ = (I); \ + assert(!OPCODE_HAS_ARG(OP)); \ + cfg_instr *_instr__ptr_ = (I); \ _instr__ptr_->i_opcode = (OP); \ _instr__ptr_->i_oparg = 0; \ } while (0); @@ -86,6 +144,16 @@ basicblock_next_instr(basicblock *b) return b->b_iused++; } +static cfg_instr * +basicblock_last_instr(const basicblock *b) { + assert(b->b_iused >= 0); + if (b->b_iused > 0) { + assert(b->b_instr != NULL); + return &b->b_instr[b->b_iused - 1]; + } + return NULL; +} + /* Allocate a new block and return a pointer to it. Returns NULL on error. */ @@ -93,7 +161,7 @@ basicblock_next_instr(basicblock *b) static basicblock * cfg_builder_new_block(cfg_builder *g) { - basicblock *b = (basicblock *)PyObject_Calloc(1, sizeof(basicblock)); + basicblock *b = (basicblock *)PyMem_Calloc(1, sizeof(basicblock)); if (b == NULL) { PyErr_NoMemory(); return NULL; @@ -110,7 +178,7 @@ basicblock_addop(basicblock *b, int opcode, int oparg, location loc) { assert(IS_WITHIN_OPCODE_RANGE(opcode)); assert(!IS_ASSEMBLER_OPCODE(opcode)); - assert(HAS_ARG(opcode) || HAS_TARGET(opcode) || oparg == 0); + assert(OPCODE_HAS_ARG(opcode) || HAS_TARGET(opcode) || oparg == 0); assert(0 <= oparg && oparg < (1 << 30)); int off = basicblock_next_instr(b); @@ -126,19 +194,46 @@ basicblock_addop(basicblock *b, int opcode, int oparg, location loc) return SUCCESS; } +static int +basicblock_add_jump(basicblock *b, int opcode, basicblock *target, location loc) +{ + cfg_instr *last = basicblock_last_instr(b); + if (last && is_jump(last)) { + return ERROR; + } + + RETURN_IF_ERROR( + basicblock_addop(b, opcode, target->b_label.id, loc)); + last = basicblock_last_instr(b); + assert(last && last->i_opcode == opcode); + last->i_target = target; + return SUCCESS; +} + static inline int -basicblock_append_instructions(basicblock *target, basicblock *source) +basicblock_append_instructions(basicblock *to, basicblock *from) { - for (int i = 0; i < source->b_iused; i++) { - int n = basicblock_next_instr(target); + for (int i = 0; i < from->b_iused; i++) { + int n = basicblock_next_instr(to); if (n < 0) { return ERROR; } - target->b_instr[n] = source->b_instr[i]; + to->b_instr[n] = from->b_instr[i]; } return SUCCESS; } +static inline int +basicblock_nofallthrough(const basicblock *b) { + cfg_instr *last = basicblock_last_instr(b); + return (last && + (IS_SCOPE_EXIT_OPCODE(last->i_opcode) || + IS_UNCONDITIONAL_JUMP_OPCODE(last->i_opcode))); +} + +#define BB_NO_FALLTHROUGH(B) (basicblock_nofallthrough(B)) +#define BB_HAS_FALLTHROUGH(B) (!basicblock_nofallthrough(B)) + static basicblock * copy_basicblock(cfg_builder *g, basicblock *block) { @@ -156,8 +251,8 @@ copy_basicblock(cfg_builder *g, basicblock *block) return result; } -int -_PyBasicblock_InsertInstruction(basicblock *block, int pos, cfg_instr *instr) { +static int +basicblock_insert_instruction(basicblock *block, int pos, cfg_instr *instr) { RETURN_IF_ERROR(basicblock_next_instr(block)); for (int i = block->b_iused - 1; i > pos; i--) { block->b_instr[i] = block->b_instr[i-1]; @@ -166,22 +261,6 @@ _PyBasicblock_InsertInstruction(basicblock *block, int pos, cfg_instr *instr) { return SUCCESS; } -static int -instr_size(cfg_instr *instruction) -{ - return _PyCompile_InstrSize(instruction->i_opcode, instruction->i_oparg); -} - -static int -blocksize(basicblock *b) -{ - int size = 0; - for (int i = 0; i < b->b_iused; i++) { - size += instr_size(&b->b_instr[i]); - } - return size; -} - /* For debugging purposes only */ #if 0 static void @@ -192,19 +271,19 @@ dump_instr(cfg_instr *i) char arg[128]; *arg = '\0'; - if (HAS_ARG(i->i_opcode)) { + if (OPCODE_HAS_ARG(i->i_opcode)) { sprintf(arg, "arg: %d ", i->i_oparg); } if (HAS_TARGET(i->i_opcode)) { sprintf(arg, "target: %p [%d] ", i->i_target, i->i_oparg); } - fprintf(stderr, "line: %d, opcode: %d %s%s\n", - i->i_loc.lineno, i->i_opcode, arg, jump); + fprintf(stderr, "line: %d, %s (%d) %s%s\n", + i->i_loc.lineno, _PyOpcode_OpName[i->i_opcode], i->i_opcode, arg, jump); } static inline int basicblock_returns(const basicblock *b) { - cfg_instr *last = _PyCfg_BasicblockLastInstr(b); + cfg_instr *last = basicblock_last_instr(b); return last && (last->i_opcode == RETURN_VALUE || last->i_opcode == RETURN_CONST); } @@ -212,9 +291,9 @@ static void dump_basicblock(const basicblock *b) { const char *b_return = basicblock_returns(b) ? "return " : ""; - fprintf(stderr, "%d: [EH=%d CLD=%d WRM=%d NO_FT=%d %p] used: %d, depth: %d, offset: %d %s\n", + fprintf(stderr, "%d: [EH=%d CLD=%d WRM=%d NO_FT=%d %p] used: %d, depth: %d, preds: %d %s\n", b->b_label.id, b->b_except_handler, b->b_cold, b->b_warm, BB_NO_FALLTHROUGH(b), b, b->b_iused, - b->b_startdepth, b->b_offset, b_return); + b->b_startdepth, b->b_predecessors, b_return); if (b->b_instr) { int i; for (i = 0; i < b->b_iused; i++) { @@ -246,26 +325,26 @@ cfg_builder_use_next_block(cfg_builder *g, basicblock *block) return block; } -cfg_instr * -_PyCfg_BasicblockLastInstr(const basicblock *b) { - assert(b->b_iused >= 0); - if (b->b_iused > 0) { - assert(b->b_instr != NULL); - return &b->b_instr[b->b_iused - 1]; - } - return NULL; -} - static inline int basicblock_exits_scope(const basicblock *b) { - cfg_instr *last = _PyCfg_BasicblockLastInstr(b); + cfg_instr *last = basicblock_last_instr(b); return last && IS_SCOPE_EXIT_OPCODE(last->i_opcode); } +static inline int +basicblock_has_eval_break(const basicblock *b) { + for (int i = 0; i < b->b_iused; i++) { + if (OPCODE_HAS_EVAL_BREAK(b->b_instr[i].i_opcode)) { + return true; + } + } + return false; +} + static bool cfg_builder_current_block_is_terminated(cfg_builder *g) { - cfg_instr *last = _PyCfg_BasicblockLastInstr(g->g_curblock); + cfg_instr *last = basicblock_last_instr(g->g_curblock); if (last && IS_TERMINATOR_OPCODE(last->i_opcode)) { return true; } @@ -318,8 +397,8 @@ cfg_builder_check(cfg_builder *g) } #endif -int -_PyCfgBuilder_Init(cfg_builder *g) +static int +init_cfg_builder(cfg_builder *g) { g->g_block_list = NULL; basicblock *block = cfg_builder_new_block(g); @@ -331,19 +410,53 @@ _PyCfgBuilder_Init(cfg_builder *g) return SUCCESS; } +cfg_builder * +_PyCfgBuilder_New(void) +{ + cfg_builder *g = PyMem_Malloc(sizeof(cfg_builder)); + if (g == NULL) { + PyErr_NoMemory(); + return NULL; + } + memset(g, 0, sizeof(cfg_builder)); + if (init_cfg_builder(g) < 0) { + PyMem_Free(g); + return NULL; + } + return g; +} + void -_PyCfgBuilder_Fini(cfg_builder* g) +_PyCfgBuilder_Free(cfg_builder *g) { + if (g == NULL) { + return; + } assert(cfg_builder_check(g)); basicblock *b = g->g_block_list; while (b != NULL) { if (b->b_instr) { - PyObject_Free((void *)b->b_instr); + PyMem_Free((void *)b->b_instr); } basicblock *next = b->b_list; - PyObject_Free((void *)b); + PyMem_Free((void *)b); b = next; } + PyMem_Free(g); +} + +int +_PyCfgBuilder_CheckSize(cfg_builder *g) +{ + int nblocks = 0; + for (basicblock *b = g->g_block_list; b != NULL; b = b->b_list) { + nblocks++; + } + if ((size_t)nblocks > SIZE_MAX / sizeof(basicblock *)) { + PyErr_NoMemory(); + return ERROR; + } + return SUCCESS; } int @@ -361,29 +474,24 @@ _PyCfgBuilder_Addop(cfg_builder *g, int opcode, int oparg, location loc) } +static basicblock * +next_nonempty_block(basicblock *b) +{ + while (b && b->b_iused == 0) { + b = b->b_next; + } + return b; +} + /***** debugging helpers *****/ #ifndef NDEBUG -static int remove_redundant_nops(basicblock *bb); +static int remove_redundant_nops(cfg_builder *g); -/* static bool no_redundant_nops(cfg_builder *g) { - for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { - if (remove_redundant_nops(b) != 0) { - return false; - } - } - return true; -} -*/ - -static bool -no_empty_basic_blocks(cfg_builder *g) { - for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { - if (b->b_iused == 0) { - return false; - } + if (remove_redundant_nops(g) != 0) { + return false; } return true; } @@ -391,12 +499,17 @@ no_empty_basic_blocks(cfg_builder *g) { static bool no_redundant_jumps(cfg_builder *g) { for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { - cfg_instr *last = _PyCfg_BasicblockLastInstr(b); + cfg_instr *last = basicblock_last_instr(b); if (last != NULL) { if (IS_UNCONDITIONAL_JUMP_OPCODE(last->i_opcode)) { - assert(last->i_target != b->b_next); - if (last->i_target == b->b_next) { - return false; + basicblock *next = next_nonempty_block(b->b_next); + basicblock *jump_target = next_nonempty_block(last->i_target); + if (jump_target == next) { + assert(next); + if (last->i_loc.lineno == next->b_instr[0].i_loc.lineno) { + assert(0); + return false; + } } } } @@ -410,21 +523,18 @@ no_redundant_jumps(cfg_builder *g) { static int normalize_jumps_in_block(cfg_builder *g, basicblock *b) { - cfg_instr *last = _PyCfg_BasicblockLastInstr(b); - if (last == NULL || !is_jump(last)) { + cfg_instr *last = basicblock_last_instr(b); + if (last == NULL || !is_jump(last) || + IS_UNCONDITIONAL_JUMP_OPCODE(last->i_opcode)) { return SUCCESS; } assert(!IS_ASSEMBLER_OPCODE(last->i_opcode)); + bool is_forward = last->i_target->b_visited == 0; - switch(last->i_opcode) { - case JUMP: - last->i_opcode = is_forward ? JUMP_FORWARD : JUMP_BACKWARD; - return SUCCESS; - case JUMP_NO_INTERRUPT: - last->i_opcode = is_forward ? - JUMP_FORWARD : JUMP_BACKWARD_NO_INTERRUPT; - return SUCCESS; + if (is_forward) { + return SUCCESS; } + int reversed_opcode = 0; switch(last->i_opcode) { case POP_JUMP_IF_NOT_NONE: @@ -440,9 +550,6 @@ normalize_jumps_in_block(cfg_builder *g, basicblock *b) { reversed_opcode = POP_JUMP_IF_FALSE; break; } - if (is_forward) { - return SUCCESS; - } /* transform 'conditional jump T' to * 'reversed_jump b_next' followed by 'jump_backwards T' */ @@ -452,8 +559,8 @@ normalize_jumps_in_block(cfg_builder *g, basicblock *b) { if (backwards_jump == NULL) { return ERROR; } - basicblock_addop(backwards_jump, JUMP, target->b_label.id, last->i_loc); - backwards_jump->b_instr[0].i_target = target; + RETURN_IF_ERROR( + basicblock_add_jump(backwards_jump, JUMP, target, last->i_loc)); last->i_opcode = reversed_opcode; last->i_target = b->b_next; @@ -465,7 +572,7 @@ normalize_jumps_in_block(cfg_builder *g, basicblock *b) { static int -normalize_jumps(_PyCfgBuilder *g) +normalize_jumps(cfg_builder *g) { basicblock *entryblock = g->g_entryblock; for (basicblock *b = entryblock; b != NULL; b = b->b_next) { @@ -478,74 +585,6 @@ normalize_jumps(_PyCfgBuilder *g) return SUCCESS; } -static void -resolve_jump_offsets(basicblock *entryblock) -{ - int bsize, totsize, extended_arg_recompile; - - /* Compute the size of each block and fixup jump args. - Replace block pointer with position in bytecode. */ - do { - totsize = 0; - for (basicblock *b = entryblock; b != NULL; b = b->b_next) { - bsize = blocksize(b); - b->b_offset = totsize; - totsize += bsize; - } - extended_arg_recompile = 0; - for (basicblock *b = entryblock; b != NULL; b = b->b_next) { - bsize = b->b_offset; - for (int i = 0; i < b->b_iused; i++) { - cfg_instr *instr = &b->b_instr[i]; - int isize = instr_size(instr); - /* jump offsets are computed relative to - * the instruction pointer after fetching - * the jump instruction. - */ - bsize += isize; - if (is_jump(instr)) { - instr->i_oparg = instr->i_target->b_offset; - if (instr->i_oparg < bsize) { - assert(IS_BACKWARDS_JUMP_OPCODE(instr->i_opcode)); - instr->i_oparg = bsize - instr->i_oparg; - } - else { - assert(!IS_BACKWARDS_JUMP_OPCODE(instr->i_opcode)); - instr->i_oparg -= bsize; - } - if (instr_size(instr) != isize) { - extended_arg_recompile = 1; - } - } - } - } - - /* XXX: This is an awful hack that could hurt performance, but - on the bright side it should work until we come up - with a better solution. - - The issue is that in the first loop blocksize() is called - which calls instr_size() which requires i_oparg be set - appropriately. There is a bootstrap problem because - i_oparg is calculated in the second loop above. - - So we loop until we stop seeing new EXTENDED_ARGs. - The only EXTENDED_ARGs that could be popping up are - ones in jump instructions. So this should converge - fairly quickly. - */ - } while (extended_arg_recompile); -} - -int -_PyCfg_ResolveJumps(_PyCfgBuilder *g) -{ - RETURN_IF_ERROR(normalize_jumps(g)); - assert(no_redundant_jumps(g)); - resolve_jump_offsets(g->g_entryblock); - return SUCCESS; -} - static int check_cfg(cfg_builder *g) { for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { @@ -610,12 +649,6 @@ translate_jump_labels_to_targets(basicblock *entryblock) return SUCCESS; } -int -_PyCfg_JumpLabelsToTargets(basicblock *entryblock) -{ - return translate_jump_labels_to_targets(entryblock); -} - static int mark_except_handlers(basicblock *entryblock) { #ifndef NDEBUG @@ -635,10 +668,14 @@ mark_except_handlers(basicblock *entryblock) { } -typedef _PyCfgExceptStack ExceptStack; +struct _PyCfgExceptStack { + basicblock *handlers[CO_MAXBLOCKS+2]; + int depth; +}; + static basicblock * -push_except_block(ExceptStack *stack, cfg_instr *setup) { +push_except_block(struct _PyCfgExceptStack *stack, cfg_instr *setup) { assert(is_block_push(setup)); int opcode = setup->i_opcode; basicblock * target = setup->i_target; @@ -651,19 +688,19 @@ push_except_block(ExceptStack *stack, cfg_instr *setup) { } static basicblock * -pop_except_block(ExceptStack *stack) { +pop_except_block(struct _PyCfgExceptStack *stack) { assert(stack->depth > 0); return stack->handlers[--stack->depth]; } static basicblock * -except_stack_top(ExceptStack *stack) { +except_stack_top(struct _PyCfgExceptStack *stack) { return stack->handlers[stack->depth]; } -static ExceptStack * +static struct _PyCfgExceptStack * make_except_stack(void) { - ExceptStack *new = PyMem_Malloc(sizeof(ExceptStack)); + struct _PyCfgExceptStack *new = PyMem_Malloc(sizeof(struct _PyCfgExceptStack)); if (new == NULL) { PyErr_NoMemory(); return NULL; @@ -673,14 +710,14 @@ make_except_stack(void) { return new; } -static ExceptStack * -copy_except_stack(ExceptStack *stack) { - ExceptStack *copy = PyMem_Malloc(sizeof(ExceptStack)); +static struct _PyCfgExceptStack * +copy_except_stack(struct _PyCfgExceptStack *stack) { + struct _PyCfgExceptStack *copy = PyMem_Malloc(sizeof(struct _PyCfgExceptStack)); if (copy == NULL) { PyErr_NoMemory(); return NULL; } - memcpy(copy, stack, sizeof(ExceptStack)); + memcpy(copy, stack, sizeof(struct _PyCfgExceptStack)); return copy; } @@ -698,23 +735,28 @@ make_cfg_traversal_stack(basicblock *entryblock) { return stack; } -Py_LOCAL_INLINE(void) +Py_LOCAL_INLINE(int) stackdepth_push(basicblock ***sp, basicblock *b, int depth) { - assert(b->b_startdepth < 0 || b->b_startdepth == depth); + if (!(b->b_startdepth < 0 || b->b_startdepth == depth)) { + PyErr_Format(PyExc_ValueError, "Invalid CFG, inconsistent stackdepth"); + return ERROR; + } if (b->b_startdepth < depth && b->b_startdepth < 100) { assert(b->b_startdepth < 0); b->b_startdepth = depth; *(*sp)++ = b; } + return SUCCESS; } /* Find the flow path that needs the largest stack. We assume that * cycles in the flow graph have no net effect on the stack depth. */ -int -_PyCfg_Stackdepth(basicblock *entryblock, int code_flags) +static int +calculate_stackdepth(cfg_builder *g) { + basicblock *entryblock = g->g_entryblock; for (basicblock *b = entryblock; b != NULL; b = b->b_next) { b->b_startdepth = INT_MIN; } @@ -723,14 +765,13 @@ _PyCfg_Stackdepth(basicblock *entryblock, int code_flags) return ERROR; } + + int stackdepth = -1; int maxdepth = 0; basicblock **sp = stack; - if (code_flags & (CO_GENERATOR | CO_COROUTINE | CO_ASYNC_GENERATOR)) { - stackdepth_push(&sp, entryblock, 1); - } else { - stackdepth_push(&sp, entryblock, 0); + if (stackdepth_push(&sp, entryblock, 0) < 0) { + goto error; } - while (sp != stack) { basicblock *b = *--sp; int depth = b->b_startdepth; @@ -738,27 +779,40 @@ _PyCfg_Stackdepth(basicblock *entryblock, int code_flags) basicblock *next = b->b_next; for (int i = 0; i < b->b_iused; i++) { cfg_instr *instr = &b->b_instr[i]; - int effect = PyCompile_OpcodeStackEffectWithJump(instr->i_opcode, instr->i_oparg, 0); + int effect = PyCompile_OpcodeStackEffectWithJump( + instr->i_opcode, instr->i_oparg, 0); if (effect == PY_INVALID_STACK_EFFECT) { PyErr_Format(PyExc_SystemError, - "compiler PyCompile_OpcodeStackEffectWithJump(opcode=%d, arg=%i) failed", + "Invalid stack effect for opcode=%d, arg=%i", instr->i_opcode, instr->i_oparg); - return ERROR; + goto error; } int new_depth = depth + effect; - assert(new_depth >= 0); /* invalid code or bug in stackdepth() */ + if (new_depth < 0) { + PyErr_Format(PyExc_ValueError, + "Invalid CFG, stack underflow"); + goto error; + } if (new_depth > maxdepth) { maxdepth = new_depth; } if (HAS_TARGET(instr->i_opcode)) { - effect = PyCompile_OpcodeStackEffectWithJump(instr->i_opcode, instr->i_oparg, 1); - assert(effect != PY_INVALID_STACK_EFFECT); + effect = PyCompile_OpcodeStackEffectWithJump( + instr->i_opcode, instr->i_oparg, 1); + if (effect == PY_INVALID_STACK_EFFECT) { + PyErr_Format(PyExc_SystemError, + "Invalid stack effect for opcode=%d, arg=%i", + instr->i_opcode, instr->i_oparg); + goto error; + } int target_depth = depth + effect; assert(target_depth >= 0); /* invalid code or bug in stackdepth() */ if (target_depth > maxdepth) { maxdepth = target_depth; } - stackdepth_push(&sp, instr->i_target, target_depth); + if (stackdepth_push(&sp, instr->i_target, target_depth) < 0) { + goto error; + } } depth = new_depth; assert(!IS_ASSEMBLER_OPCODE(instr->i_opcode)); @@ -772,11 +826,15 @@ _PyCfg_Stackdepth(basicblock *entryblock, int code_flags) } if (next != NULL) { assert(BB_HAS_FALLTHROUGH(b)); - stackdepth_push(&sp, next, depth); + if (stackdepth_push(&sp, next, depth) < 0) { + goto error; + } } } + stackdepth = maxdepth; +error: PyMem_Free(stack); - return maxdepth; + return stackdepth; } static int @@ -785,7 +843,7 @@ label_exception_targets(basicblock *entryblock) { if (todo_stack == NULL) { return ERROR; } - ExceptStack *except_stack = make_except_stack(); + struct _PyCfgExceptStack *except_stack = make_except_stack(); if (except_stack == NULL) { PyMem_Free(todo_stack); PyErr_NoMemory(); @@ -805,11 +863,12 @@ label_exception_targets(basicblock *entryblock) { assert(except_stack != NULL); b->b_exceptstack = NULL; handler = except_stack_top(except_stack); + int last_yield_except_depth = -1; for (int i = 0; i < b->b_iused; i++) { cfg_instr *instr = &b->b_instr[i]; if (is_block_push(instr)) { if (!instr->i_target->b_visited) { - ExceptStack *copy = copy_except_stack(except_stack); + struct _PyCfgExceptStack *copy = copy_except_stack(except_stack); if (copy == NULL) { goto error; } @@ -822,13 +881,14 @@ label_exception_targets(basicblock *entryblock) { } else if (instr->i_opcode == POP_BLOCK) { handler = pop_except_block(except_stack); + INSTR_SET_OP0(instr, NOP); } else if (is_jump(instr)) { instr->i_except = handler; assert(i == b->b_iused -1); if (!instr->i_target->b_visited) { if (BB_HAS_FALLTHROUGH(b)) { - ExceptStack *copy = copy_except_stack(except_stack); + struct _PyCfgExceptStack *copy = copy_except_stack(except_stack); if (copy == NULL) { goto error; } @@ -843,10 +903,21 @@ label_exception_targets(basicblock *entryblock) { todo++; } } - else { - if (instr->i_opcode == YIELD_VALUE) { - instr->i_oparg = except_stack->depth; + else if (instr->i_opcode == YIELD_VALUE) { + instr->i_except = handler; + last_yield_except_depth = except_stack->depth; + } + else if (instr->i_opcode == RESUME) { + instr->i_except = handler; + if (instr->i_oparg != RESUME_AT_FUNC_START) { + assert(last_yield_except_depth >= 0); + if (last_yield_except_depth == 1) { + instr->i_oparg |= RESUME_OPARG_DEPTH1_MASK; + } + last_yield_except_depth = -1; } + } + else { instr->i_except = handler; } } @@ -877,7 +948,10 @@ error: /***** CFG optimizations *****/ static int -mark_reachable(basicblock *entryblock) { +remove_unreachable(basicblock *entryblock) { + for (basicblock *b = entryblock; b != NULL; b = b->b_next) { + b->b_predecessors = 0; + } basicblock **stack = make_cfg_traversal_stack(entryblock); if (stack == NULL) { return ERROR; @@ -885,13 +959,14 @@ mark_reachable(basicblock *entryblock) { basicblock **sp = stack; entryblock->b_predecessors = 1; *sp++ = entryblock; + entryblock->b_visited = 1; while (sp > stack) { basicblock *b = *(--sp); - b->b_visited = 1; if (b->b_next && BB_HAS_FALLTHROUGH(b)) { if (!b->b_next->b_visited) { assert(b->b_next->b_predecessors == 0); *sp++ = b->b_next; + b->b_next->b_visited = 1; } b->b_next->b_predecessors++; } @@ -901,55 +976,27 @@ mark_reachable(basicblock *entryblock) { if (is_jump(instr) || is_block_push(instr)) { target = instr->i_target; if (!target->b_visited) { - assert(target->b_predecessors == 0 || target == b->b_next); *sp++ = target; + target->b_visited = 1; } target->b_predecessors++; } } } PyMem_Free(stack); - return SUCCESS; -} -static void -eliminate_empty_basic_blocks(cfg_builder *g) { - /* Eliminate empty blocks */ - for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { - basicblock *next = b->b_next; - while (next && next->b_iused == 0) { - next = next->b_next; - } - b->b_next = next; - } - while(g->g_entryblock && g->g_entryblock->b_iused == 0) { - g->g_entryblock = g->g_entryblock->b_next; - } - int next_lbl = get_max_label(g->g_entryblock) + 1; - for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { - assert(b->b_iused > 0); - for (int i = 0; i < b->b_iused; i++) { - cfg_instr *instr = &b->b_instr[i]; - if (HAS_TARGET(instr->i_opcode)) { - basicblock *target = instr->i_target; - while (target->b_iused == 0) { - target = target->b_next; - } - if (instr->i_target != target) { - if (!IS_LABEL(target->b_label)) { - target->b_label.id = next_lbl++; - } - instr->i_target = target; - instr->i_oparg = target->b_label.id; - } - assert(instr->i_target && instr->i_target->b_iused > 0); - } - } + /* Delete unreachable instructions */ + for (basicblock *b = entryblock; b != NULL; b = b->b_next) { + if (b->b_predecessors == 0) { + b->b_iused = 0; + b->b_except_handler = 0; + } } + return SUCCESS; } static int -remove_redundant_nops(basicblock *bb) { +basicblock_remove_redundant_nops(basicblock *bb) { /* Remove NOPs when legal to do so. */ int dest = 0; int prev_lineno = -1; @@ -976,10 +1023,7 @@ remove_redundant_nops(basicblock *bb) { } } else { - basicblock* next = bb->b_next; - while (next && next->b_iused == 0) { - next = next->b_next; - } + basicblock *next = next_nonempty_block(bb->b_next); /* or if last instruction in BB and next BB has same line number */ if (next) { location next_loc = NO_LOCATION; @@ -1012,6 +1056,17 @@ remove_redundant_nops(basicblock *bb) { } static int +remove_redundant_nops(cfg_builder *g) { + int changes = 0; + for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { + int change = basicblock_remove_redundant_nops(b); + RETURN_IF_ERROR(change); + changes += change; + } + return changes; +} + +static int remove_redundant_nops_and_pairs(basicblock *entryblock) { bool done = false; @@ -1021,7 +1076,7 @@ remove_redundant_nops_and_pairs(basicblock *entryblock) cfg_instr *prev_instr = NULL; cfg_instr *instr = NULL; for (basicblock *b = entryblock; b != NULL; b = b->b_next) { - remove_redundant_nops(b); + RETURN_IF_ERROR(basicblock_remove_redundant_nops(b)); if (IS_LABEL(b->b_label)) { /* this block is a jump target, forget instr */ instr = NULL; @@ -1061,36 +1116,55 @@ remove_redundant_jumps(cfg_builder *g) { * non-empty block reached through normal flow control is the target * of that jump. If it is, then the jump instruction is redundant and * can be deleted. + * + * Return the number of changes applied, or -1 on error. */ - assert(no_empty_basic_blocks(g)); + + int changes = 0; for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { - cfg_instr *last = _PyCfg_BasicblockLastInstr(b); - assert(last != NULL); + cfg_instr *last = basicblock_last_instr(b); + if (last == NULL) { + continue; + } assert(!IS_ASSEMBLER_OPCODE(last->i_opcode)); if (IS_UNCONDITIONAL_JUMP_OPCODE(last->i_opcode)) { - if (last->i_target == NULL) { + basicblock* jump_target = next_nonempty_block(last->i_target); + if (jump_target == NULL) { PyErr_SetString(PyExc_SystemError, "jump with NULL target"); return ERROR; } - if (last->i_target == b->b_next) { - assert(b->b_next->b_iused); + basicblock *next = next_nonempty_block(b->b_next); + if (jump_target == next) { + changes++; INSTR_SET_OP0(last, NOP); } } } - return SUCCESS; + + return changes; +} + +static inline bool +basicblock_has_no_lineno(basicblock *b) { + for (int i = 0; i < b->b_iused; i++) { + if (b->b_instr[i].i_loc.lineno >= 0) { + return false; + } + } + return true; } /* Maximum size of basic block that should be copied in optimizer */ #define MAX_COPY_SIZE 4 -/* If this block ends with an unconditional jump to a small exit block, then +/* If this block ends with an unconditional jump to a small exit block or + * a block that has no line numbers (and no fallthrough), then * remove the jump and extend this block with the target. * Returns 1 if extended, 0 if no change, and -1 on error. */ static int -inline_small_exit_blocks(basicblock *bb) { - cfg_instr *last = _PyCfg_BasicblockLastInstr(bb); +basicblock_inline_small_or_no_lineno_blocks(basicblock *bb) { + cfg_instr *last = basicblock_last_instr(bb); if (last == NULL) { return 0; } @@ -1098,29 +1172,67 @@ inline_small_exit_blocks(basicblock *bb) { return 0; } basicblock *target = last->i_target; - if (basicblock_exits_scope(target) && target->b_iused <= MAX_COPY_SIZE) { + bool small_exit_block = (basicblock_exits_scope(target) && + target->b_iused <= MAX_COPY_SIZE); + bool no_lineno_no_fallthrough = (basicblock_has_no_lineno(target) && + !BB_HAS_FALLTHROUGH(target)); + if (small_exit_block || no_lineno_no_fallthrough) { + assert(is_jump(last)); + int removed_jump_opcode = last->i_opcode; INSTR_SET_OP0(last, NOP); RETURN_IF_ERROR(basicblock_append_instructions(bb, target)); + if (no_lineno_no_fallthrough) { + last = basicblock_last_instr(bb); + if (IS_UNCONDITIONAL_JUMP_OPCODE(last->i_opcode) && + removed_jump_opcode == JUMP) + { + /* Make sure we don't lose eval breaker checks */ + last->i_opcode = JUMP; + } + } + target->b_predecessors--; return 1; } return 0; } +static int +inline_small_or_no_lineno_blocks(basicblock *entryblock) { + bool changes; + do { + changes = false; + for (basicblock *b = entryblock; b != NULL; b = b->b_next) { + int res = basicblock_inline_small_or_no_lineno_blocks(b); + RETURN_IF_ERROR(res); + if (res) { + changes = true; + } + } + } while(changes); /* every change removes a jump, ensuring convergence */ + return changes; +} + // Attempt to eliminate jumps to jumps by updating inst to jump to // target->i_target using the provided opcode. Return whether or not the // optimization was successful. static bool -jump_thread(cfg_instr *inst, cfg_instr *target, int opcode) +jump_thread(basicblock *bb, cfg_instr *inst, cfg_instr *target, int opcode) { assert(is_jump(inst)); assert(is_jump(target)); + assert(inst == basicblock_last_instr(bb)); // bpo-45773: If inst->i_target == target->i_target, then nothing actually // changes (and we fall into an infinite loop): - if ((inst->i_loc.lineno == target->i_loc.lineno || target->i_loc.lineno == -1) && - inst->i_target != target->i_target) - { - inst->i_target = target->i_target; - inst->i_opcode = opcode; + if (inst->i_target != target->i_target) { + /* Change inst to NOP and append a jump to target->i_target. The + * NOP will be removed later if it's not needed for the lineno. + */ + INSTR_SET_OP0(inst, NOP); + + RETURN_IF_ERROR( + basicblock_add_jump( + bb, opcode, target->i_target, target->i_loc)); + return true; } return false; @@ -1130,7 +1242,7 @@ static PyObject* get_const_value(int opcode, int oparg, PyObject *co_consts) { PyObject *constant = NULL; - assert(HAS_CONST(opcode)); + assert(OPCODE_HAS_CONST(opcode)); if (opcode == LOAD_CONST) { constant = PyList_GET_ITEM(co_consts, oparg); } @@ -1143,6 +1255,36 @@ get_const_value(int opcode, int oparg, PyObject *co_consts) return Py_NewRef(constant); } +// Steals a reference to newconst. +static int +add_const(PyObject *newconst, PyObject *consts, PyObject *const_cache) +{ + if (_PyCompile_ConstCacheMergeOne(const_cache, &newconst) < 0) { + Py_DECREF(newconst); + return -1; + } + + Py_ssize_t index; + for (index = 0; index < PyList_GET_SIZE(consts); index++) { + if (PyList_GET_ITEM(consts, index) == newconst) { + break; + } + } + if (index == PyList_GET_SIZE(consts)) { + if ((size_t)index >= (size_t)INT_MAX - 1) { + PyErr_SetString(PyExc_OverflowError, "too many constants"); + Py_DECREF(newconst); + return -1; + } + if (PyList_Append(consts, newconst)) { + Py_DECREF(newconst); + return -1; + } + } + Py_DECREF(newconst); + return (int)index; +} + /* Replace LOAD_CONST c1, LOAD_CONST c2 ... LOAD_CONST cn, BUILD_TUPLE n with LOAD_CONST (c1, c2, ... cn). The consts table must still be in list form so that the @@ -1161,7 +1303,7 @@ fold_tuple_on_constants(PyObject *const_cache, assert(inst[n].i_oparg == n); for (int i = 0; i < n; i++) { - if (!HAS_CONST(inst[i].i_opcode)) { + if (!OPCODE_HAS_CONST(inst[i].i_opcode)) { return SUCCESS; } } @@ -1180,33 +1322,14 @@ fold_tuple_on_constants(PyObject *const_cache, } PyTuple_SET_ITEM(newconst, i, constant); } - if (_PyCompile_ConstCacheMergeOne(const_cache, &newconst) < 0) { - Py_DECREF(newconst); + int index = add_const(newconst, consts, const_cache); + if (index < 0) { return ERROR; } - - Py_ssize_t index; - for (index = 0; index < PyList_GET_SIZE(consts); index++) { - if (PyList_GET_ITEM(consts, index) == newconst) { - break; - } - } - if (index == PyList_GET_SIZE(consts)) { - if ((size_t)index >= (size_t)INT_MAX - 1) { - Py_DECREF(newconst); - PyErr_SetString(PyExc_OverflowError, "too many constants"); - return ERROR; - } - if (PyList_Append(consts, newconst)) { - Py_DECREF(newconst); - return ERROR; - } - } - Py_DECREF(newconst); for (int i = 0; i < n; i++) { INSTR_SET_OP0(&inst[i], NOP); } - INSTR_SET_OP1(&inst[n], LOAD_CONST, (int)index); + INSTR_SET_OP1(&inst[n], LOAD_CONST, index); return SUCCESS; } @@ -1402,16 +1525,12 @@ apply_static_swaps(basicblock *block, int i) } static int -optimize_basic_block(PyObject *const_cache, basicblock *bb, PyObject *consts) +basicblock_optimize_load_const(PyObject *const_cache, basicblock *bb, PyObject *consts) { assert(PyDict_CheckExact(const_cache)); assert(PyList_CheckExact(consts)); - cfg_instr nop; - INSTR_SET_OP0(&nop, NOP); - cfg_instr *target = &nop; int opcode = 0; int oparg = 0; - int nextop = 0; for (int i = 0; i < bb->b_iused; i++) { cfg_instr *inst = &bb->b_instr[i]; bool is_copy_of_load_const = (opcode == LOAD_CONST && @@ -1420,71 +1539,148 @@ optimize_basic_block(PyObject *const_cache, basicblock *bb, PyObject *consts) if (! is_copy_of_load_const) { opcode = inst->i_opcode; oparg = inst->i_oparg; - if (HAS_TARGET(opcode)) { - assert(inst->i_target->b_iused > 0); - target = &inst->i_target->b_instr[0]; - assert(!IS_ASSEMBLER_OPCODE(target->i_opcode)); - } - else { - target = &nop; - } } - nextop = i+1 < bb->b_iused ? bb->b_instr[i+1].i_opcode : 0; assert(!IS_ASSEMBLER_OPCODE(opcode)); - switch (opcode) { - /* Remove LOAD_CONST const; conditional jump */ - case LOAD_CONST: + if (opcode != LOAD_CONST) { + continue; + } + int nextop = i+1 < bb->b_iused ? bb->b_instr[i+1].i_opcode : 0; + switch(nextop) { + case POP_JUMP_IF_FALSE: + case POP_JUMP_IF_TRUE: { - PyObject* cnt; - int is_true; - int jump_if_true; - switch(nextop) { - case POP_JUMP_IF_FALSE: - case POP_JUMP_IF_TRUE: - cnt = get_const_value(opcode, oparg, consts); - if (cnt == NULL) { - goto error; - } - is_true = PyObject_IsTrue(cnt); - Py_DECREF(cnt); - if (is_true == -1) { - goto error; - } - INSTR_SET_OP0(inst, NOP); - jump_if_true = nextop == POP_JUMP_IF_TRUE; - if (is_true == jump_if_true) { - bb->b_instr[i+1].i_opcode = JUMP; - } - else { - INSTR_SET_OP0(&bb->b_instr[i + 1], NOP); - } - break; - case IS_OP: - cnt = get_const_value(opcode, oparg, consts); - if (cnt == NULL) { - goto error; - } - int jump_op = i+2 < bb->b_iused ? bb->b_instr[i+2].i_opcode : 0; - if (Py_IsNone(cnt) && (jump_op == POP_JUMP_IF_FALSE || jump_op == POP_JUMP_IF_TRUE)) { - unsigned char nextarg = bb->b_instr[i+1].i_oparg; - INSTR_SET_OP0(inst, NOP); - INSTR_SET_OP0(&bb->b_instr[i + 1], NOP); - bb->b_instr[i+2].i_opcode = nextarg ^ (jump_op == POP_JUMP_IF_FALSE) ? - POP_JUMP_IF_NOT_NONE : POP_JUMP_IF_NONE; - } - Py_DECREF(cnt); - break; - case RETURN_VALUE: - INSTR_SET_OP0(inst, NOP); - INSTR_SET_OP1(&bb->b_instr[++i], RETURN_CONST, oparg); + /* Remove LOAD_CONST const; conditional jump */ + PyObject* cnt = get_const_value(opcode, oparg, consts); + if (cnt == NULL) { + return ERROR; + } + int is_true = PyObject_IsTrue(cnt); + Py_DECREF(cnt); + if (is_true == -1) { + return ERROR; + } + INSTR_SET_OP0(inst, NOP); + int jump_if_true = nextop == POP_JUMP_IF_TRUE; + if (is_true == jump_if_true) { + bb->b_instr[i+1].i_opcode = JUMP; + } + else { + INSTR_SET_OP0(&bb->b_instr[i + 1], NOP); + } + break; + } + case IS_OP: + { + // Fold to POP_JUMP_IF_NONE: + // - LOAD_CONST(None) IS_OP(0) POP_JUMP_IF_TRUE + // - LOAD_CONST(None) IS_OP(1) POP_JUMP_IF_FALSE + // - LOAD_CONST(None) IS_OP(0) TO_BOOL POP_JUMP_IF_TRUE + // - LOAD_CONST(None) IS_OP(1) TO_BOOL POP_JUMP_IF_FALSE + // Fold to POP_JUMP_IF_NOT_NONE: + // - LOAD_CONST(None) IS_OP(0) POP_JUMP_IF_FALSE + // - LOAD_CONST(None) IS_OP(1) POP_JUMP_IF_TRUE + // - LOAD_CONST(None) IS_OP(0) TO_BOOL POP_JUMP_IF_FALSE + // - LOAD_CONST(None) IS_OP(1) TO_BOOL POP_JUMP_IF_TRUE + PyObject *cnt = get_const_value(opcode, oparg, consts); + if (cnt == NULL) { + return ERROR; + } + if (!Py_IsNone(cnt)) { + Py_DECREF(cnt); + break; + } + if (bb->b_iused <= i + 2) { + break; + } + cfg_instr *is_instr = &bb->b_instr[i + 1]; + cfg_instr *jump_instr = &bb->b_instr[i + 2]; + // Get rid of TO_BOOL regardless: + if (jump_instr->i_opcode == TO_BOOL) { + INSTR_SET_OP0(jump_instr, NOP); + if (bb->b_iused <= i + 3) { break; + } + jump_instr = &bb->b_instr[i + 3]; + } + bool invert = is_instr->i_oparg; + if (jump_instr->i_opcode == POP_JUMP_IF_FALSE) { + invert = !invert; + } + else if (jump_instr->i_opcode != POP_JUMP_IF_TRUE) { + break; } + INSTR_SET_OP0(inst, NOP); + INSTR_SET_OP0(is_instr, NOP); + jump_instr->i_opcode = invert ? POP_JUMP_IF_NOT_NONE + : POP_JUMP_IF_NONE; break; } - /* Try to fold tuples of constants. - Skip over BUILD_TUPLE(1) UNPACK_SEQUENCE(1). - Replace BUILD_TUPLE(2) UNPACK_SEQUENCE(2) with SWAP(2). - Replace BUILD_TUPLE(3) UNPACK_SEQUENCE(3) with SWAP(3). */ + case RETURN_VALUE: + { + INSTR_SET_OP0(inst, NOP); + INSTR_SET_OP1(&bb->b_instr[++i], RETURN_CONST, oparg); + break; + } + case TO_BOOL: + { + PyObject *cnt = get_const_value(opcode, oparg, consts); + if (cnt == NULL) { + return ERROR; + } + int is_true = PyObject_IsTrue(cnt); + Py_DECREF(cnt); + if (is_true == -1) { + return ERROR; + } + cnt = PyBool_FromLong(is_true); + int index = add_const(cnt, consts, const_cache); + if (index < 0) { + return ERROR; + } + INSTR_SET_OP0(inst, NOP); + INSTR_SET_OP1(&bb->b_instr[i + 1], LOAD_CONST, index); + break; + } + } + } + return SUCCESS; +} + +static int +optimize_load_const(PyObject *const_cache, cfg_builder *g, PyObject *consts) { + for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { + RETURN_IF_ERROR(basicblock_optimize_load_const(const_cache, b, consts)); + } + return SUCCESS; +} + +static int +optimize_basic_block(PyObject *const_cache, basicblock *bb, PyObject *consts) +{ + assert(PyDict_CheckExact(const_cache)); + assert(PyList_CheckExact(consts)); + cfg_instr nop; + INSTR_SET_OP0(&nop, NOP); + for (int i = 0; i < bb->b_iused; i++) { + cfg_instr *inst = &bb->b_instr[i]; + cfg_instr *target; + int opcode = inst->i_opcode; + int oparg = inst->i_oparg; + if (HAS_TARGET(opcode)) { + assert(inst->i_target->b_iused > 0); + target = &inst->i_target->b_instr[0]; + assert(!IS_ASSEMBLER_OPCODE(target->i_opcode)); + } + else { + target = &nop; + } + int nextop = i+1 < bb->b_iused ? bb->b_instr[i+1].i_opcode : 0; + assert(!IS_ASSEMBLER_OPCODE(opcode)); + switch (opcode) { + /* Try to fold tuples of constants. + Skip over BUILD_TUPLE(1) UNPACK_SEQUENCE(1). + Replace BUILD_TUPLE(2) UNPACK_SEQUENCE(2) with SWAP(2). + Replace BUILD_TUPLE(3) UNPACK_SEQUENCE(3) with SWAP(3). */ case BUILD_TUPLE: if (nextop == UNPACK_SEQUENCE && oparg == bb->b_instr[i+1].i_oparg) { switch(oparg) { @@ -1509,25 +1705,30 @@ optimize_basic_block(PyObject *const_cache, basicblock *bb, PyObject *consts) case POP_JUMP_IF_NONE: switch (target->i_opcode) { case JUMP: - i -= jump_thread(inst, target, inst->i_opcode); + i -= jump_thread(bb, inst, target, inst->i_opcode); } break; case POP_JUMP_IF_FALSE: switch (target->i_opcode) { case JUMP: - i -= jump_thread(inst, target, POP_JUMP_IF_FALSE); + i -= jump_thread(bb, inst, target, POP_JUMP_IF_FALSE); } break; case POP_JUMP_IF_TRUE: switch (target->i_opcode) { case JUMP: - i -= jump_thread(inst, target, POP_JUMP_IF_TRUE); + i -= jump_thread(bb, inst, target, POP_JUMP_IF_TRUE); } break; case JUMP: + case JUMP_NO_INTERRUPT: switch (target->i_opcode) { case JUMP: - i -= jump_thread(inst, target, JUMP); + i -= jump_thread(bb, inst, target, JUMP); + continue; + case JUMP_NO_INTERRUPT: + i -= jump_thread(bb, inst, target, opcode); + continue; } break; case FOR_ITER: @@ -1538,31 +1739,72 @@ optimize_basic_block(PyObject *const_cache, basicblock *bb, PyObject *consts) * of FOR_ITER. */ /* - i -= jump_thread(inst, target, FOR_ITER); + i -= jump_thread(bb, inst, target, FOR_ITER); */ } break; + case STORE_FAST: + if (opcode == nextop && + oparg == bb->b_instr[i+1].i_oparg && + bb->b_instr[i].i_loc.lineno == bb->b_instr[i+1].i_loc.lineno) { + bb->b_instr[i].i_opcode = POP_TOP; + bb->b_instr[i].i_oparg = 0; + } + break; case SWAP: if (oparg == 1) { INSTR_SET_OP0(inst, NOP); - break; } - if (swaptimize(bb, &i) < 0) { - goto error; + break; + case LOAD_GLOBAL: + if (nextop == PUSH_NULL && (oparg & 1) == 0) { + INSTR_SET_OP1(inst, LOAD_GLOBAL, oparg | 1); + INSTR_SET_OP0(&bb->b_instr[i + 1], NOP); + } + break; + case COMPARE_OP: + if (nextop == TO_BOOL) { + INSTR_SET_OP0(inst, NOP); + INSTR_SET_OP1(&bb->b_instr[i + 1], COMPARE_OP, oparg | 16); + continue; } - apply_static_swaps(bb, i); break; - case KW_NAMES: + case CONTAINS_OP: + case IS_OP: + if (nextop == TO_BOOL) { + INSTR_SET_OP0(inst, NOP); + INSTR_SET_OP1(&bb->b_instr[i + 1], opcode, oparg); + continue; + } break; - case PUSH_NULL: - if (nextop == LOAD_GLOBAL && (bb->b_instr[i+1].i_oparg & 1) == 0) { + case TO_BOOL: + if (nextop == TO_BOOL) { + INSTR_SET_OP0(inst, NOP); + continue; + } + break; + case UNARY_NOT: + if (nextop == TO_BOOL) { + INSTR_SET_OP0(inst, NOP); + INSTR_SET_OP0(&bb->b_instr[i + 1], UNARY_NOT); + continue; + } + if (nextop == UNARY_NOT) { INSTR_SET_OP0(inst, NOP); - bb->b_instr[i+1].i_oparg |= 1; + INSTR_SET_OP0(&bb->b_instr[i + 1], NOP); + continue; } break; - default: - /* All HAS_CONST opcodes should be handled with LOAD_CONST */ - assert (!HAS_CONST(inst->i_opcode)); + } + } + + for (int i = 0; i < bb->b_iused; i++) { + cfg_instr *inst = &bb->b_instr[i]; + if (inst->i_opcode == SWAP) { + if (swaptimize(bb, &i) < 0) { + goto error; + } + apply_static_swaps(bb, i); } } return SUCCESS; @@ -1570,6 +1812,23 @@ error: return ERROR; } +static int resolve_line_numbers(cfg_builder *g, int firstlineno); + +static int +remove_redundant_nops_and_jumps(cfg_builder *g) +{ + int removed_nops, removed_jumps; + do { + /* Convergence is guaranteed because the number of + * redundant jumps and nops only decreases. + */ + removed_nops = remove_redundant_nops(g); + RETURN_IF_ERROR(removed_nops); + removed_jumps = remove_redundant_jumps(g); + RETURN_IF_ERROR(removed_jumps); + } while(removed_nops + removed_jumps > 0); + return SUCCESS; +} /* Perform optimizations on a control flow graph. The consts object should still be in list form to allow new constants @@ -1579,42 +1838,70 @@ error: NOPs. Later those NOPs are removed. */ static int -optimize_cfg(cfg_builder *g, PyObject *consts, PyObject *const_cache) +optimize_cfg(cfg_builder *g, PyObject *consts, PyObject *const_cache, int firstlineno) { assert(PyDict_CheckExact(const_cache)); RETURN_IF_ERROR(check_cfg(g)); - eliminate_empty_basic_blocks(g); - for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { - RETURN_IF_ERROR(inline_small_exit_blocks(b)); - } - assert(no_empty_basic_blocks(g)); + RETURN_IF_ERROR(inline_small_or_no_lineno_blocks(g->g_entryblock)); + RETURN_IF_ERROR(remove_unreachable(g->g_entryblock)); + RETURN_IF_ERROR(resolve_line_numbers(g, firstlineno)); + RETURN_IF_ERROR(optimize_load_const(const_cache, g, consts)); for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { RETURN_IF_ERROR(optimize_basic_block(const_cache, b, consts)); - assert(b->b_predecessors == 0); } RETURN_IF_ERROR(remove_redundant_nops_and_pairs(g->g_entryblock)); - for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { - RETURN_IF_ERROR(inline_small_exit_blocks(b)); - } - RETURN_IF_ERROR(mark_reachable(g->g_entryblock)); + RETURN_IF_ERROR(remove_unreachable(g->g_entryblock)); + RETURN_IF_ERROR(remove_redundant_nops_and_jumps(g)); + assert(no_redundant_jumps(g)); + return SUCCESS; +} - /* Delete unreachable instructions */ - for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { - if (b->b_predecessors == 0) { - b->b_iused = 0; - } +static void +make_super_instruction(cfg_instr *inst1, cfg_instr *inst2, int super_op) +{ + int32_t line1 = inst1->i_loc.lineno; + int32_t line2 = inst2->i_loc.lineno; + /* Skip if instructions are on different lines */ + if (line1 >= 0 && line2 >= 0 && line1 != line2) { + return; + } + if (inst1->i_oparg >= 16 || inst2->i_oparg >= 16) { + return; } + INSTR_SET_OP1(inst1, super_op, (inst1->i_oparg << 4) | inst2->i_oparg); + INSTR_SET_OP0(inst2, NOP); +} + +static int +insert_superinstructions(cfg_builder *g) +{ for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { - remove_redundant_nops(b); + + for (int i = 0; i < b->b_iused; i++) { + cfg_instr *inst = &b->b_instr[i]; + int nextop = i+1 < b->b_iused ? b->b_instr[i+1].i_opcode : 0; + switch(inst->i_opcode) { + case LOAD_FAST: + if (nextop == LOAD_FAST) { + make_super_instruction(inst, &b->b_instr[i + 1], LOAD_FAST_LOAD_FAST); + } + break; + case STORE_FAST: + switch (nextop) { + case LOAD_FAST: + make_super_instruction(inst, &b->b_instr[i + 1], STORE_FAST_LOAD_FAST); + break; + case STORE_FAST: + make_super_instruction(inst, &b->b_instr[i + 1], STORE_FAST_STORE_FAST); + break; + } + break; + } + } } - eliminate_empty_basic_blocks(g); - /* This assertion fails in an edge case (See gh-109889). - * Remove it for the release (it's just one more NOP in the - * bytecode for unlikely code). - */ - // assert(no_redundant_nops(g)); - RETURN_IF_ERROR(remove_redundant_jumps(g)); - return SUCCESS; + int res = remove_redundant_nops(g); + assert(no_redundant_nops(g)); + return res; } // helper functions for add_checks_for_loads_of_unknown_variables @@ -1644,7 +1931,6 @@ scan_block_for_locals(basicblock *b, basicblock ***sp) for (int i = 0; i < b->b_iused; i++) { cfg_instr *instr = &b->b_instr[i]; assert(instr->i_opcode != EXTENDED_ARG); - assert(!IS_SUPERINSTRUCTION_OPCODE(instr->i_opcode)); if (instr->i_except != NULL) { maybe_push(instr->i_except, unsafe_mask, sp); } @@ -1677,7 +1963,7 @@ scan_block_for_locals(basicblock *b, basicblock ***sp) if (b->b_next && BB_HAS_FALLTHROUGH(b)) { maybe_push(b->b_next, unsafe_mask, sp); } - cfg_instr *last = _PyCfg_BasicblockLastInstr(b); + cfg_instr *last = basicblock_last_instr(b); if (last && is_jump(last)) { assert(last->i_target != NULL); maybe_push(last->i_target, unsafe_mask, sp); @@ -1703,7 +1989,6 @@ fast_scan_many_locals(basicblock *entryblock, int nlocals) for (int i = 0; i < b->b_iused; i++) { cfg_instr *instr = &b->b_instr[i]; assert(instr->i_opcode != EXTENDED_ARG); - assert(!IS_SUPERINSTRUCTION_OPCODE(instr->i_opcode)); int arg = instr->i_oparg; if (arg < 64) { continue; @@ -1758,7 +2043,7 @@ remove_unused_consts(basicblock *entryblock, PyObject *consts) /* mark used consts */ for (basicblock *b = entryblock; b != NULL; b = b->b_next) { for (int i = 0; i < b->b_iused; i++) { - if (HAS_CONST(b->b_instr[i].i_opcode)) { + if (OPCODE_HAS_CONST(b->b_instr[i].i_opcode)) { int index = b->b_instr[i].i_oparg; index_map[index] = index; } @@ -1811,7 +2096,7 @@ remove_unused_consts(basicblock *entryblock, PyObject *consts) for (basicblock *b = entryblock; b != NULL; b = b->b_next) { for (int i = 0; i < b->b_iused; i++) { - if (HAS_CONST(b->b_instr[i].i_opcode)) { + if (OPCODE_HAS_CONST(b->b_instr[i].i_opcode)) { int index = b->b_instr[i].i_oparg; assert(reverse_index_map[index] >= 0); assert(reverse_index_map[index] < n_used_consts); @@ -1961,7 +2246,7 @@ mark_cold(basicblock *entryblock) { static int -push_cold_blocks_to_end(cfg_builder *g, int code_flags) { +push_cold_blocks_to_end(cfg_builder *g) { basicblock *entryblock = g->g_entryblock; if (entryblock->b_next == NULL) { /* single basicblock, no need to reorder */ @@ -1982,13 +2267,15 @@ push_cold_blocks_to_end(cfg_builder *g, int code_flags) { if (!IS_LABEL(b->b_next->b_label)) { b->b_next->b_label.id = next_lbl++; } - basicblock_addop(explicit_jump, JUMP, b->b_next->b_label.id, NO_LOCATION); + basicblock_addop(explicit_jump, JUMP_NO_INTERRUPT, b->b_next->b_label.id, + NO_LOCATION); explicit_jump->b_cold = 1; explicit_jump->b_next = b->b_next; + explicit_jump->b_predecessors = 1; b->b_next = explicit_jump; /* set target */ - cfg_instr *last = _PyCfg_BasicblockLastInstr(explicit_jump); + cfg_instr *last = basicblock_last_instr(explicit_jump); last->i_target = explicit_jump->b_next; } } @@ -2034,41 +2321,42 @@ push_cold_blocks_to_end(cfg_builder *g, int code_flags) { b->b_next = cold_blocks; if (cold_blocks != NULL) { - RETURN_IF_ERROR(remove_redundant_jumps(g)); + RETURN_IF_ERROR(remove_redundant_nops_and_jumps(g)); } return SUCCESS; } -void -_PyCfg_ConvertPseudoOps(basicblock *entryblock) +static int +convert_pseudo_ops(cfg_builder *g) { + basicblock *entryblock = g->g_entryblock; for (basicblock *b = entryblock; b != NULL; b = b->b_next) { for (int i = 0; i < b->b_iused; i++) { cfg_instr *instr = &b->b_instr[i]; - if (is_block_push(instr) || instr->i_opcode == POP_BLOCK) { + if (is_block_push(instr)) { INSTR_SET_OP0(instr, NOP); } + else if (instr->i_opcode == LOAD_CLOSURE) { + assert(is_pseudo_target(LOAD_CLOSURE, LOAD_FAST)); + instr->i_opcode = LOAD_FAST; + } else if (instr->i_opcode == STORE_FAST_MAYBE_NULL) { + assert(is_pseudo_target(STORE_FAST_MAYBE_NULL, STORE_FAST)); instr->i_opcode = STORE_FAST; } } } - for (basicblock *b = entryblock; b != NULL; b = b->b_next) { - remove_redundant_nops(b); - } + return remove_redundant_nops_and_jumps(g); } static inline bool -is_exit_without_lineno(basicblock *b) { - if (!basicblock_exits_scope(b)) { - return false; +is_exit_or_eval_check_without_lineno(basicblock *b) { + if (basicblock_exits_scope(b) || basicblock_has_eval_break(b)) { + return basicblock_has_no_lineno(b); } - for (int i = 0; i < b->b_iused; i++) { - if (b->b_instr[i].i_loc.lineno >= 0) { - return false; - } + else { + return false; } - return true; } @@ -2084,19 +2372,19 @@ is_exit_without_lineno(basicblock *b) { static int duplicate_exits_without_lineno(cfg_builder *g) { - assert(no_empty_basic_blocks(g)); - int next_lbl = get_max_label(g->g_entryblock) + 1; /* Copy all exit blocks without line number that are targets of a jump. */ basicblock *entryblock = g->g_entryblock; for (basicblock *b = entryblock; b != NULL; b = b->b_next) { - cfg_instr *last = _PyCfg_BasicblockLastInstr(b); - assert(last != NULL); + cfg_instr *last = basicblock_last_instr(b); + if (last == NULL) { + continue; + } if (is_jump(last)) { - basicblock *target = last->i_target; - if (is_exit_without_lineno(target) && target->b_predecessors > 1) { + basicblock *target = next_nonempty_block(last->i_target); + if (is_exit_or_eval_check_without_lineno(target) && target->b_predecessors > 1) { basicblock *new_target = copy_basicblock(g, target); if (new_target == NULL) { return ERROR; @@ -2116,8 +2404,8 @@ duplicate_exits_without_lineno(cfg_builder *g) * fall through, and thus can only have a single predecessor */ for (basicblock *b = entryblock; b != NULL; b = b->b_next) { if (BB_HAS_FALLTHROUGH(b) && b->b_next && b->b_iused > 0) { - if (is_exit_without_lineno(b->b_next)) { - cfg_instr *last = _PyCfg_BasicblockLastInstr(b); + if (is_exit_or_eval_check_without_lineno(b->b_next)) { + cfg_instr *last = basicblock_last_instr(b); assert(last != NULL); b->b_next->b_instr[0].i_loc = last->i_loc; } @@ -2137,7 +2425,7 @@ duplicate_exits_without_lineno(cfg_builder *g) static void propagate_line_numbers(basicblock *entryblock) { for (basicblock *b = entryblock; b != NULL; b = b->b_next) { - cfg_instr *last = _PyCfg_BasicblockLastInstr(b); + cfg_instr *last = basicblock_last_instr(b); if (last == NULL) { continue; } @@ -2152,9 +2440,10 @@ propagate_line_numbers(basicblock *entryblock) { } } if (BB_HAS_FALLTHROUGH(b) && b->b_next->b_predecessors == 1) { - assert(b->b_next->b_iused); - if (b->b_next->b_instr[0].i_loc.lineno < 0) { - b->b_next->b_instr[0].i_loc = prev_location; + if (b->b_next->b_iused > 0) { + if (b->b_next->b_instr[0].i_loc.lineno < 0) { + b->b_next->b_instr[0].i_loc = prev_location; + } } } if (is_jump(last)) { @@ -2168,46 +2457,17 @@ propagate_line_numbers(basicblock *entryblock) { } } -/* Make sure that all returns have a line number, even if early passes - * have failed to propagate a correct line number. - * The resulting line number may not be correct according to PEP 626, - * but should be "good enough", and no worse than in older versions. */ -static void -guarantee_lineno_for_exits(basicblock *entryblock, int firstlineno) { - int lineno = firstlineno; - assert(lineno > 0); - for (basicblock *b = entryblock; b != NULL; b = b->b_next) { - cfg_instr *last = _PyCfg_BasicblockLastInstr(b); - if (last == NULL) { - continue; - } - if (last->i_loc.lineno < 0) { - if (last->i_opcode == RETURN_VALUE) { - for (int i = 0; i < b->b_iused; i++) { - assert(b->b_instr[i].i_loc.lineno < 0); - - b->b_instr[i].i_loc.lineno = lineno; - } - } - } - else { - lineno = last->i_loc.lineno; - } - } -} - static int resolve_line_numbers(cfg_builder *g, int firstlineno) { RETURN_IF_ERROR(duplicate_exits_without_lineno(g)); propagate_line_numbers(g->g_entryblock); - guarantee_lineno_for_exits(g->g_entryblock, firstlineno); return SUCCESS; } int _PyCfg_OptimizeCodeUnit(cfg_builder *g, PyObject *consts, PyObject *const_cache, - int code_flags, int nlocals, int nparams, int firstlineno) + int nlocals, int nparams, int firstlineno) { assert(cfg_builder_check(g)); /** Preprocessing **/ @@ -2217,13 +2477,308 @@ _PyCfg_OptimizeCodeUnit(cfg_builder *g, PyObject *consts, PyObject *const_cache, RETURN_IF_ERROR(label_exception_targets(g->g_entryblock)); /** Optimization **/ - RETURN_IF_ERROR(optimize_cfg(g, consts, const_cache)); + RETURN_IF_ERROR(optimize_cfg(g, consts, const_cache, firstlineno)); RETURN_IF_ERROR(remove_unused_consts(g->g_entryblock, consts)); RETURN_IF_ERROR( add_checks_for_loads_of_uninitialized_variables( g->g_entryblock, nlocals, nparams)); + RETURN_IF_ERROR(insert_superinstructions(g)); - RETURN_IF_ERROR(push_cold_blocks_to_end(g, code_flags)); + RETURN_IF_ERROR(push_cold_blocks_to_end(g)); RETURN_IF_ERROR(resolve_line_numbers(g, firstlineno)); return SUCCESS; } + +static int * +build_cellfixedoffsets(_PyCompile_CodeUnitMetadata *umd) +{ + int nlocals = (int)PyDict_GET_SIZE(umd->u_varnames); + int ncellvars = (int)PyDict_GET_SIZE(umd->u_cellvars); + int nfreevars = (int)PyDict_GET_SIZE(umd->u_freevars); + + int noffsets = ncellvars + nfreevars; + int *fixed = PyMem_New(int, noffsets); + if (fixed == NULL) { + PyErr_NoMemory(); + return NULL; + } + for (int i = 0; i < noffsets; i++) { + fixed[i] = nlocals + i; + } + + PyObject *varname, *cellindex; + Py_ssize_t pos = 0; + while (PyDict_Next(umd->u_cellvars, &pos, &varname, &cellindex)) { + PyObject *varindex; + if (PyDict_GetItemRef(umd->u_varnames, varname, &varindex) < 0) { + goto error; + } + if (varindex == NULL) { + continue; + } + + int argoffset = PyLong_AsInt(varindex); + Py_DECREF(varindex); + if (argoffset == -1 && PyErr_Occurred()) { + goto error; + } + + int oldindex = PyLong_AsInt(cellindex); + if (oldindex == -1 && PyErr_Occurred()) { + goto error; + } + fixed[oldindex] = argoffset; + } + return fixed; + +error: + PyMem_Free(fixed); + return NULL; +} + +#define IS_GENERATOR(CF) \ + ((CF) & (CO_GENERATOR | CO_COROUTINE | CO_ASYNC_GENERATOR)) + +static int +insert_prefix_instructions(_PyCompile_CodeUnitMetadata *umd, basicblock *entryblock, + int *fixed, int nfreevars, int code_flags) +{ + assert(umd->u_firstlineno > 0); + + /* Add the generator prefix instructions. */ + if (IS_GENERATOR(code_flags)) { + /* Note that RETURN_GENERATOR + POP_TOP have a net stack effect + * of 0. This is because RETURN_GENERATOR pushes an element + * with _PyFrame_StackPush before switching stacks. + */ + + location loc = LOCATION(umd->u_firstlineno, umd->u_firstlineno, -1, -1); + cfg_instr make_gen = { + .i_opcode = RETURN_GENERATOR, + .i_oparg = 0, + .i_loc = loc, + .i_target = NULL, + }; + RETURN_IF_ERROR(basicblock_insert_instruction(entryblock, 0, &make_gen)); + cfg_instr pop_top = { + .i_opcode = POP_TOP, + .i_oparg = 0, + .i_loc = loc, + .i_target = NULL, + }; + RETURN_IF_ERROR(basicblock_insert_instruction(entryblock, 1, &pop_top)); + } + + /* Set up cells for any variable that escapes, to be put in a closure. */ + const int ncellvars = (int)PyDict_GET_SIZE(umd->u_cellvars); + if (ncellvars) { + // umd->u_cellvars has the cells out of order so we sort them + // before adding the MAKE_CELL instructions. Note that we + // adjust for arg cells, which come first. + const int nvars = ncellvars + (int)PyDict_GET_SIZE(umd->u_varnames); + int *sorted = PyMem_RawCalloc(nvars, sizeof(int)); + if (sorted == NULL) { + PyErr_NoMemory(); + return ERROR; + } + for (int i = 0; i < ncellvars; i++) { + sorted[fixed[i]] = i + 1; + } + for (int i = 0, ncellsused = 0; ncellsused < ncellvars; i++) { + int oldindex = sorted[i] - 1; + if (oldindex == -1) { + continue; + } + cfg_instr make_cell = { + .i_opcode = MAKE_CELL, + // This will get fixed in offset_derefs(). + .i_oparg = oldindex, + .i_loc = NO_LOCATION, + .i_target = NULL, + }; + if (basicblock_insert_instruction(entryblock, ncellsused, &make_cell) < 0) { + PyMem_RawFree(sorted); + return ERROR; + } + ncellsused += 1; + } + PyMem_RawFree(sorted); + } + + if (nfreevars) { + cfg_instr copy_frees = { + .i_opcode = COPY_FREE_VARS, + .i_oparg = nfreevars, + .i_loc = NO_LOCATION, + .i_target = NULL, + }; + RETURN_IF_ERROR(basicblock_insert_instruction(entryblock, 0, ©_frees)); + } + + return SUCCESS; +} + +static int +fix_cell_offsets(_PyCompile_CodeUnitMetadata *umd, basicblock *entryblock, int *fixedmap) +{ + int nlocals = (int)PyDict_GET_SIZE(umd->u_varnames); + int ncellvars = (int)PyDict_GET_SIZE(umd->u_cellvars); + int nfreevars = (int)PyDict_GET_SIZE(umd->u_freevars); + int noffsets = ncellvars + nfreevars; + + // First deal with duplicates (arg cells). + int numdropped = 0; + for (int i = 0; i < noffsets ; i++) { + if (fixedmap[i] == i + nlocals) { + fixedmap[i] -= numdropped; + } + else { + // It was a duplicate (cell/arg). + numdropped += 1; + } + } + + // Then update offsets, either relative to locals or by cell2arg. + for (basicblock *b = entryblock; b != NULL; b = b->b_next) { + for (int i = 0; i < b->b_iused; i++) { + cfg_instr *inst = &b->b_instr[i]; + // This is called before extended args are generated. + assert(inst->i_opcode != EXTENDED_ARG); + int oldoffset = inst->i_oparg; + switch(inst->i_opcode) { + case MAKE_CELL: + case LOAD_CLOSURE: + case LOAD_DEREF: + case STORE_DEREF: + case DELETE_DEREF: + case LOAD_FROM_DICT_OR_DEREF: + assert(oldoffset >= 0); + assert(oldoffset < noffsets); + assert(fixedmap[oldoffset] >= 0); + inst->i_oparg = fixedmap[oldoffset]; + } + } + } + + return numdropped; +} + +static int +prepare_localsplus(_PyCompile_CodeUnitMetadata *umd, cfg_builder *g, int code_flags) +{ + assert(PyDict_GET_SIZE(umd->u_varnames) < INT_MAX); + assert(PyDict_GET_SIZE(umd->u_cellvars) < INT_MAX); + assert(PyDict_GET_SIZE(umd->u_freevars) < INT_MAX); + int nlocals = (int)PyDict_GET_SIZE(umd->u_varnames); + int ncellvars = (int)PyDict_GET_SIZE(umd->u_cellvars); + int nfreevars = (int)PyDict_GET_SIZE(umd->u_freevars); + assert(INT_MAX - nlocals - ncellvars > 0); + assert(INT_MAX - nlocals - ncellvars - nfreevars > 0); + int nlocalsplus = nlocals + ncellvars + nfreevars; + int* cellfixedoffsets = build_cellfixedoffsets(umd); + if (cellfixedoffsets == NULL) { + return ERROR; + } + + // This must be called before fix_cell_offsets(). + if (insert_prefix_instructions(umd, g->g_entryblock, cellfixedoffsets, nfreevars, code_flags)) { + PyMem_Free(cellfixedoffsets); + return ERROR; + } + + int numdropped = fix_cell_offsets(umd, g->g_entryblock, cellfixedoffsets); + PyMem_Free(cellfixedoffsets); // At this point we're done with it. + cellfixedoffsets = NULL; + if (numdropped < 0) { + return ERROR; + } + + nlocalsplus -= numdropped; + return nlocalsplus; +} + +int +_PyCfg_ToInstructionSequence(cfg_builder *g, _PyInstructionSequence *seq) +{ + int lbl = 0; + for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { + b->b_label = (jump_target_label){lbl}; + lbl += 1; + } + for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) { + RETURN_IF_ERROR(_PyInstructionSequence_UseLabel(seq, b->b_label.id)); + for (int i = 0; i < b->b_iused; i++) { + cfg_instr *instr = &b->b_instr[i]; + if (HAS_TARGET(instr->i_opcode)) { + /* Set oparg to the label id (it will later be mapped to an offset) */ + instr->i_oparg = instr->i_target->b_label.id; + } + RETURN_IF_ERROR( + _PyInstructionSequence_Addop( + seq, instr->i_opcode, instr->i_oparg, instr->i_loc)); + + _PyExceptHandlerInfo *hi = &seq->s_instrs[seq->s_used-1].i_except_handler_info; + if (instr->i_except != NULL) { + hi->h_label = instr->i_except->b_label.id; + hi->h_startdepth = instr->i_except->b_startdepth; + hi->h_preserve_lasti = instr->i_except->b_preserve_lasti; + } + else { + hi->h_label = -1; + } + } + } + return SUCCESS; +} + + +int +_PyCfg_OptimizedCfgToInstructionSequence(cfg_builder *g, + _PyCompile_CodeUnitMetadata *umd, int code_flags, + int *stackdepth, int *nlocalsplus, + _PyInstructionSequence *seq) +{ + *stackdepth = calculate_stackdepth(g); + if (*stackdepth < 0) { + return ERROR; + } + + /* prepare_localsplus adds instructions for generators that push + * and pop an item on the stack. This assertion makes sure there + * is space on the stack for that. + * It should always be true, because a generator must have at + * least one expression or call to INTRINSIC_STOPITERATION_ERROR, + * which requires stackspace. + */ + assert(!(IS_GENERATOR(code_flags) && *stackdepth == 0)); + + *nlocalsplus = prepare_localsplus(umd, g, code_flags); + if (*nlocalsplus < 0) { + return ERROR; + } + + RETURN_IF_ERROR(convert_pseudo_ops(g)); + + /* Order of basic blocks must have been determined by now */ + + RETURN_IF_ERROR(normalize_jumps(g)); + assert(no_redundant_jumps(g)); + + /* Can't modify the bytecode after computing jump offsets. */ + if (_PyCfg_ToInstructionSequence(g, seq) < 0) { + return ERROR; + } + + return SUCCESS; +} + +/* This is used by _PyCompile_Assemble to fill in the jump and exception + * targets in a synthetic CFG (which is not the ouptut of the builtin compiler). + */ +int +_PyCfg_JumpLabelsToTargets(cfg_builder *g) +{ + RETURN_IF_ERROR(translate_jump_labels_to_targets(g->g_entryblock)); + RETURN_IF_ERROR(label_exception_targets(g->g_entryblock)); + return SUCCESS; +} |