flowgraph.c

#include "Python.h"
#include "opcode.h"
#include "pycore_c_array.h"       // _Py_CArray_EnsureCapacity
#include "pycore_flowgraph.h"
#include "pycore_compile.h"
#include "pycore_intrinsics.h"
#include "pycore_pymem.h"         // _PyMem_IsPtrFreed()
#include "pycore_long.h"          // _PY_IS_SMALL_INT()

#include "pycore_opcode_utils.h"
#include "pycore_opcode_metadata.h" // OPCODE_HAS_ARG, etc

#include <stdbool.h>


#undef SUCCESS
#undef ERROR
#define SUCCESS 0
#define ERROR -1

#define RETURN_IF_ERROR(X)  \
    if ((X) == -1) {        \
        return ERROR;       \
    }

#define DEFAULT_BLOCK_SIZE 16

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;

#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 OPCODE_HAS_JUMP(i->i_opcode);
}

/* One arg*/
#define INSTR_SET_OP1(I, OP, ARG) \
    do { \
        assert(OPCODE_HAS_ARG(OP)); \
        cfg_instr *_instr__ptr_ = (I); \
        _instr__ptr_->i_opcode = (OP); \
        _instr__ptr_->i_oparg = (ARG); \
    } while (0);

/* No args*/
#define INSTR_SET_OP0(I, OP) \
    do { \
        assert(!OPCODE_HAS_ARG(OP)); \
        cfg_instr *_instr__ptr_ = (I); \
        _instr__ptr_->i_opcode = (OP); \
        _instr__ptr_->i_oparg = 0; \
    } while (0);

#define INSTR_SET_LOC(I, LOC) \
    do { \
        cfg_instr *_instr__ptr_ = (I); \
        _instr__ptr_->i_loc = (LOC); \
    } while (0);

/***** Blocks *****/

/* Returns the offset of the next instruction in the current block's
   b_instr array.  Resizes the b_instr as necessary.
   Returns -1 on failure.
*/
static int
basicblock_next_instr(basicblock *b)
{
    assert(b != NULL);
    _Py_c_array_t array = {
        .array = (void*)b->b_instr,
        .allocated_entries = b->b_ialloc,
        .item_size = sizeof(cfg_instr),
        .initial_num_entries = DEFAULT_BLOCK_SIZE,
    };

    RETURN_IF_ERROR(_Py_CArray_EnsureCapacity(&array, b->b_iused + 1));
    b->b_instr = array.array;
    b->b_ialloc = array.allocated_entries;
    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.
*/

static basicblock *
cfg_builder_new_block(cfg_builder *g)
{
    basicblock *b = (basicblock *)PyMem_Calloc(1, sizeof(basicblock));
    if (b == NULL) {
        PyErr_NoMemory();
        return NULL;
    }
    /* Extend the singly linked list of blocks with new block. */
    b->b_list = g->g_block_list;
    g->g_block_list = b;
    b->b_label = NO_LABEL;
    return b;
}

static int
basicblock_addop(basicblock *b, int opcode, int oparg, location loc)
{
    assert(IS_WITHIN_OPCODE_RANGE(opcode));
    assert(!IS_ASSEMBLER_OPCODE(opcode));
    assert(OPCODE_HAS_ARG(opcode) || HAS_TARGET(opcode) || oparg == 0);
    assert(0 <= oparg && oparg < (1 << 30));

    int off = basicblock_next_instr(b);
    if (off < 0) {
        return ERROR;
    }
    cfg_instr *i = &b->b_instr[off];
    i->i_opcode = opcode;
    i->i_oparg = oparg;
    i->i_target = NULL;
    i->i_loc = 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 *to, basicblock *from)
{
    for (int i = 0; i < from->b_iused; i++) {
        int n = basicblock_next_instr(to);
        if (n < 0) {
            return ERROR;
        }
        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)
{
    /* 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_builder_new_block(g);
    if (result == NULL) {
        return NULL;
    }
    if (basicblock_append_instructions(result, block) < 0) {
        return NULL;
    }
    return result;
}

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];
    }
    block->b_instr[pos] = *instr;
    return SUCCESS;
}

/* For debugging purposes only */
#if 0
static void
dump_instr(cfg_instr *i)
{
    const char *jump = is_jump(i) ? "jump " : "";

    char arg[128];

    *arg = '\0';
    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, %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 = basicblock_last_instr(b);
    return last && IS_RETURN_OPCODE(last->i_opcode);
}

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, 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_predecessors, b_return);
    if (b->b_instr) {
        int i;
        for (i = 0; i < b->b_iused; i++) {
            fprintf(stderr, "  [%02d] ", i);
            dump_instr(b->b_instr + i);
        }
    }
}

void
_PyCfgBuilder_DumpGraph(const basicblock *entryblock)
{
    for (const basicblock *b = entryblock; b != NULL; b = b->b_next) {
        dump_basicblock(b);
    }
}

#endif


/***** CFG construction and modification *****/

static basicblock *
cfg_builder_use_next_block(cfg_builder *g, basicblock *block)
{
    assert(block != NULL);
    g->g_curblock->b_next = block;
    g->g_curblock = block;
    return block;
}

static inline int
basicblock_exits_scope(const basicblock *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 = basicblock_last_instr(g->g_curblock);
    if (last && IS_TERMINATOR_OPCODE(last->i_opcode)) {
        return true;
    }
    if (IS_LABEL(g->g_current_label)) {
        if (last || IS_LABEL(g->g_curblock->b_label)) {
            return true;
        }
        else {
            /* current block is empty, label it */
            g->g_curblock->b_label = g->g_current_label;
            g->g_current_label = NO_LABEL;
        }
    }
    return false;
}

static int
cfg_builder_maybe_start_new_block(cfg_builder *g)
{
    if (cfg_builder_current_block_is_terminated(g)) {
        basicblock *b = cfg_builder_new_block(g);
        if (b == NULL) {
            return ERROR;
        }
        b->b_label = g->g_current_label;
        g->g_current_label = NO_LABEL;
        cfg_builder_use_next_block(g, b);
    }
    return SUCCESS;
}

#ifndef NDEBUG
static bool
cfg_builder_check(cfg_builder *g)
{
    assert(g->g_entryblock->b_iused > 0);
    for (basicblock *block = g->g_block_list; block != NULL; block = block->b_list) {
        assert(!_PyMem_IsPtrFreed(block));
        if (block->b_instr != NULL) {
            assert(block->b_ialloc > 0);
            assert(block->b_iused >= 0);
            assert(block->b_ialloc >= block->b_iused);
        }
        else {
            assert (block->b_iused == 0);
            assert (block->b_ialloc == 0);
        }
    }
    return true;
}
#endif

static int
init_cfg_builder(cfg_builder *g)
{
    g->g_block_list = NULL;
    basicblock *block = cfg_builder_new_block(g);
    if (block == NULL) {
        return ERROR;
    }
    g->g_curblock = g->g_entryblock = block;
    g->g_current_label = NO_LABEL;
    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_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) {
            PyMem_Free((void *)b->b_instr);
        }
        basicblock *next = b->b_list;
        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
_PyCfgBuilder_UseLabel(cfg_builder *g, jump_target_label lbl)
{
    g->g_current_label = lbl;
    return cfg_builder_maybe_start_new_block(g);
}

int
_PyCfgBuilder_Addop(cfg_builder *g, int opcode, int oparg, location loc)
{
    RETURN_IF_ERROR(cfg_builder_maybe_start_new_block(g));
    return basicblock_addop(g->g_curblock, opcode, oparg, 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(cfg_builder *g);

static bool
no_redundant_nops(cfg_builder *g) {
    if (remove_redundant_nops(g) != 0) {
        return false;
    }
    return true;
}

static bool
no_redundant_jumps(cfg_builder *g) {
    for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) {
        cfg_instr *last = basicblock_last_instr(b);
        if (last != NULL) {
            if (IS_UNCONDITIONAL_JUMP_OPCODE(last->i_opcode)) {
                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;
                    }
                }
            }
        }
    }
    return true;
}
#endif

/***** CFG preprocessing (jump targets and exceptions) *****/

static int
normalize_jumps_in_block(cfg_builder *g, basicblock *b) {
    cfg_instr *last = basicblock_last_instr(b);
    if (last == NULL || !IS_CONDITIONAL_JUMP_OPCODE(last->i_opcode)) {
        return SUCCESS;
    }
    assert(!IS_ASSEMBLER_OPCODE(last->i_opcode));

    bool is_forward = last->i_target->b_visited == 0;
    if (is_forward) {
        RETURN_IF_ERROR(
            basicblock_addop(b, NOT_TAKEN, 0, last->i_loc));
        return SUCCESS;
    }

    int reversed_opcode = 0;
    switch(last->i_opcode) {
        case POP_JUMP_IF_NOT_NONE:
            reversed_opcode = POP_JUMP_IF_NONE;
            break;
        case POP_JUMP_IF_NONE:
            reversed_opcode = POP_JUMP_IF_NOT_NONE;
            break;
        case POP_JUMP_IF_FALSE:
            reversed_opcode = POP_JUMP_IF_TRUE;
            break;
        case POP_JUMP_IF_TRUE:
            reversed_opcode = POP_JUMP_IF_FALSE;
            break;
    }
    /* transform 'conditional jump T' to
     * 'reversed_jump b_next' followed by 'jump_backwards T'
     */

    basicblock *target = last->i_target;
    basicblock *backwards_jump = cfg_builder_new_block(g);
    if (backwards_jump == NULL) {
        return ERROR;
    }
    RETURN_IF_ERROR(
        basicblock_addop(backwards_jump, NOT_TAKEN, 0, last->i_loc));
    RETURN_IF_ERROR(
        basicblock_add_jump(backwards_jump, JUMP, target, last->i_loc));
    backwards_jump->b_startdepth = target->b_startdepth;
    last->i_opcode = reversed_opcode;
    last->i_target = b->b_next;

    backwards_jump->b_cold = b->b_cold;
    backwards_jump->b_next = b->b_next;
    b->b_next = backwards_jump;
    return SUCCESS;
}


static int
normalize_jumps(cfg_builder *g)
{
    basicblock *entryblock = g->g_entryblock;
    for (basicblock *b = entryblock; b != NULL; b = b->b_next) {
        b->b_visited = 0;
    }
    for (basicblock *b = entryblock; b != NULL; b = b->b_next) {
        b->b_visited = 1;
        RETURN_IF_ERROR(normalize_jumps_in_block(g, b));
    }
    return SUCCESS;
}

static int
check_cfg(cfg_builder *g) {
    for (basicblock *b = g->g_entryblock; b != NULL; b = b->b_next) {
        /* Raise SystemError if jump or exit is not last instruction in the block. */
        for (int i = 0; i < b->b_iused; i++) {
            int opcode = b->b_instr[i].i_opcode;
            assert(!IS_ASSEMBLER_OPCODE(opcode));
            if (IS_TERMINATOR_OPCODE(opcode)) {
                if (i != b->b_iused - 1) {
                    PyErr_SetString(PyExc_SystemError, "malformed control flow graph.");
                    return ERROR;
                }
            }
        }
    }
    return SUCCESS;
}

static int
get_max_label(basicblock *entryblock)
{
    int lbl = -1;
    for (basicblock *b = entryblock; b != NULL; b = b->b_next) {
        if (b->b_label.id > lbl) {
            lbl = b->b_label.id;
        }
    }
    return lbl;
}

/* Calculate the actual jump target from the target_label */
static int
translate_jump_labels_to_targets(basicblock *entryblock)
{
    int max_label = get_max_label(entryblock);
    size_t mapsize = sizeof(basicblock *) * (max_label + 1);
    basicblock **label2block = (basicblock **)PyMem_Malloc(mapsize);
    if (!label2block) {
        PyErr_NoMemory();
        return ERROR;
    }
    memset(label2block, 0, mapsize);
    for (basicblock *b = entryblock; b != NULL; b = b->b_next) {
        if (b->b_label.id >= 0) {
            label2block[b->b_label.id] = b;
        }
    }
    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];
            assert(instr->i_target == NULL);
            if (HAS_TARGET(instr->i_opcode)) {
                int lbl = instr->i_oparg;
                assert(lbl >= 0 && lbl <= max_label);
                instr->i_target = label2block[lbl];
                assert(instr->i_target != NULL);
                assert(instr->i_target->b_label.id == lbl);
            }
        }
    }
    PyMem_Free(label2block);
    return SUCCESS;
}

static int
mark_except_handlers(basicblock *entryblock) {
#ifndef NDEBUG
    for (basicblock *b = entryblock; b != NULL; b = b->b_next) {
        assert(!b->b_except_handler);
    }
#endif
    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_target->b_except_handler = 1;
            }
        }
    }
    return SUCCESS;
}


struct _PyCfgExceptStack {
    basicblock *handlers[CO_MAXBLOCKS+2];
    int depth;
};


static basicblock *
push_except_block(struct _PyCfgExceptStack *stack, cfg_instr *setup) {
    assert(is_block_push(setup));
    int opcode = setup->i_opcode;
    basicblock * target = setup->i_target;
    if (opcode == SETUP_WITH || opcode == SETUP_CLEANUP) {
        target->b_preserve_lasti = 1;
    }
    assert(stack->depth <= CO_MAXBLOCKS);
    stack->handlers[++stack->depth] = target;
    return target;
}

static basicblock *
pop_except_block(struct _PyCfgExceptStack *stack) {
    assert(stack->depth > 0);
    return stack->handlers[--stack->depth];
}

static basicblock *
except_stack_top(struct _PyCfgExceptStack *stack) {
    return stack->handlers[stack->depth];
}

static struct _PyCfgExceptStack *
make_except_stack(void) {
    struct _PyCfgExceptStack *new = PyMem_Malloc(sizeof(struct _PyCfgExceptStack));
    if (new == NULL) {
        PyErr_NoMemory();
        return NULL;
    }
    new->depth = 0;
    new->handlers[0] = NULL;
    return new;
}

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(struct _PyCfgExceptStack));
    return copy;
}

static basicblock**
make_cfg_traversal_stack(basicblock *entryblock) {
    int nblocks = 0;
    for (basicblock *b = entryblock; b != NULL; b = b->b_next) {
        b->b_visited = 0;
        nblocks++;
    }
    basicblock **stack = (basicblock **)PyMem_Malloc(sizeof(basicblock *) * nblocks);
    if (!stack) {
        PyErr_NoMemory();
    }
    return stack;
}

/* Compute the stack effects of opcode with argument oparg.

   Some opcodes have different stack effect when jump to the target and
   when not jump. The 'jump' parameter specifies the case:

   * 0 -- when not jump
   * 1 -- when jump
   * -1 -- maximal
 */
typedef struct {
    /* The stack effect of the instruction. */
    int net;
} stack_effects;

Py_LOCAL(int)
get_stack_effects(int opcode, int oparg, int jump, stack_effects *effects)
{
    if (opcode < 0) {
        return -1;
    }
    if ((opcode <= MAX_REAL_OPCODE) && (_PyOpcode_Deopt[opcode] != opcode)) {
        // Specialized instructions are not supported.
        return -1;
    }
    int popped = _PyOpcode_num_popped(opcode, oparg);
    int pushed = _PyOpcode_num_pushed(opcode, oparg);
    if (popped < 0 || pushed < 0) {
        return -1;
    }
    if (IS_BLOCK_PUSH_OPCODE(opcode) && !jump) {
        effects->net = 0;
        return 0;
    }
    effects->net = pushed - popped;
    return 0;
}

Py_LOCAL_INLINE(int)
stackdepth_push(basicblock ***sp, basicblock *b, int 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.
 */
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;
    }
    basicblock **stack = make_cfg_traversal_stack(entryblock);
    if (!stack) {
        return ERROR;
    }


    int stackdepth = -1;
    int maxdepth = 0;
    basicblock **sp = stack;
    if (stackdepth_push(&sp, entryblock, 0) < 0) {
        goto error;
    }
    while (sp != stack) {
        basicblock *b = *--sp;
        int depth = b->b_startdepth;
        assert(depth >= 0);
        basicblock *next = b->b_next;
        for (int i = 0; i < b->b_iused; i++) {
            cfg_instr *instr = &b->b_instr[i];
            stack_effects effects;
            if (get_stack_effects(instr->i_opcode, instr->i_oparg, 0, &effects) < 0) {
                PyErr_Format(PyExc_SystemError,
                             "Invalid stack effect for opcode=%d, arg=%i",
                             instr->i_opcode, instr->i_oparg);
                goto error;
            }
            int new_depth = depth + effects.net;
            if (new_depth < 0) {
                PyErr_Format(PyExc_ValueError,
                             "Invalid CFG, stack underflow");
                goto error;
            }
            maxdepth = Py_MAX(maxdepth, depth);
            if (HAS_TARGET(instr->i_opcode) && instr->i_opcode != END_ASYNC_FOR) {
                if (get_stack_effects(instr->i_opcode, instr->i_oparg, 1, &effects) < 0) {
                    PyErr_Format(PyExc_SystemError,
                                 "Invalid stack effect for opcode=%d, arg=%i",
                                 instr->i_opcode, instr->i_oparg);
                    goto error;
                }
                int target_depth = depth + effects.net;
                assert(target_depth >= 0); /* invalid code or bug in stackdepth() */
                maxdepth = Py_MAX(maxdepth, depth);
                if (stackdepth_push(&sp, instr->i_target, target_depth) < 0) {
                    goto error;
                }
            }
            depth = new_depth;
            assert(!IS_ASSEMBLER_OPCODE(instr->i_opcode));
            if (IS_UNCONDITIONAL_JUMP_OPCODE(instr->i_opcode) ||
                IS_SCOPE_EXIT_OPCODE(instr->i_opcode))
            {
                /* remaining code is dead */
                next = NULL;
                break;
            }
        }
        if (next != NULL) {
            assert(BB_HAS_FALLTHROUGH(b));
            if (stackdepth_push(&sp, next, depth) < 0) {
                goto error;
            }
        }
    }
    stackdepth = maxdepth;
error:
    PyMem_Free(stack);
    return stackdepth;
}

static int
label_exception_targets(basicblock *entryblock) {
    basicblock **todo_stack = make_cfg_traversal_stack(entryblock);
    if (todo_stack == NULL) {
        return ERROR;
    }
    struct _PyCfgExceptStack *except_stack = make_except_stack();
    if (except_stack == NULL) {
        PyMem_Free(todo_stack);
        PyErr_NoMemory();
        return ERROR;
    }
    except_stack->depth = 0;
    todo_stack[0] = entryblock;
    entryblock->b_visited = 1;
    entryblock->b_exceptstack = except_stack;
    basicblock **todo = &todo_stack[1];
    basicblock *handler = NULL;
    while (todo > todo_stack) {
        todo--;
        basicblock *b = todo[0];
        assert(b->b_visited == 1);
        except_stack = b->b_exceptstack;
        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) {
                    struct _PyCfgExceptStack *copy = copy_except_stack(except_stack);
                    if (copy == NULL) {
                        goto error;
                    }
                    instr->i_target->b_exceptstack = copy;
                    todo[0] = instr->i_target;
                    instr->i_target->b_visited = 1;
                    todo++;
                }
                handler = push_except_block(except_stack, instr);
            }
            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)) {
                        struct _PyCfgExceptStack *copy = copy_except_stack(except_stack);
                        if (copy == NULL) {
                            goto error;
                        }
                        instr->i_target->b_exceptstack = copy;
                    }
                    else {
                        instr->i_target->b_exceptstack = except_stack;
                        except_stack = NULL;
                    }
                    todo[0] = instr->i_target;
                    instr->i_target->b_visited = 1;
                    todo++;
                }
            }
            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;
            }
        }
        if (BB_HAS_FALLTHROUGH(b) && !b->b_next->b_visited) {
            assert(except_stack != NULL);
            b->b_next->b_exceptstack = except_stack;
            todo[0] = b->b_next;
            b->b_next->b_visited = 1;
            todo++;
        }
        else if (except_stack != NULL) {
           PyMem_Free(except_stack);
        }
    }
#ifdef Py_DEBUG
    for (basicblock *b = entryblock; b != NULL; b = b->b_next) {
        assert(b->b_exceptstack == NULL);
    }
#endif
    PyMem_Free(todo_stack);
    return SUCCESS;
error:
    PyMem_Free(todo_stack);
    PyMem_Free(except_stack);
    return ERROR;
}

/***** CFG optimizations *****/

static int
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) {