flowgraph.c

#include"Python.h"
#include"pycore_flowgraph.h"
#include"pycore_compile.h"
#include"pycore_pymem.h"// _PyMem_IsPtrFreed()

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

#include<stdbool.h>


#undef SUCCESS
#undef ERROR
#defineSUCCESS 0
#defineERROR -1

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

#defineDEFAULT_BLOCK_SIZE 16

typedef_Py_SourceLocationlocation;
typedef_PyJumpTargetLabeljump_target_label;

typedefstruct_PyCfgInstruction {
inti_opcode;
inti_oparg;
_Py_SourceLocationi_loc;
struct_PyCfgBasicblock*i_target; /* target block (if jump instruction) */
struct_PyCfgBasicblock*i_except; /* target block when exception is raised */
} cfg_instr;

typedefstruct_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 */
_PyJumpTargetLabelb_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 */
intb_iused;
/* length of instruction array (b_instr) */
intb_ialloc;
/* Used by add_checks_for_loads_of_unknown_variables */
uint64_tb_unsafe_locals_mask;
/* Number of predecessors that a block has. */
intb_predecessors;
/* depth of stack upon entry of block, computed by stackdepth() */
intb_startdepth;
/* Basic block is an exception handler that preserves lasti */
unsignedb_preserve_lasti : 1;
/* Used by compiler passes to mark whether they have visited a basic block. */
unsignedb_visited : 1;
/* b_except_handler is used by the cold-detection algorithm to mark exception targets */
unsignedb_except_handler : 1;
/* b_cold is true if this block is not perf critical (like an exception handler) */
unsignedb_cold : 1;
/* b_warm is used by the cold-detection algorithm to mark blocks which are definitely not cold */
unsignedb_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 */
_PyJumpTargetLabelg_current_label;
};

typedefstruct_PyCfgBuildercfg_builder;

staticconstjump_target_labelNO_LABEL= {-1};

#defineSAME_LABEL(L1, L2) ((L1).id == (L2).id)
#defineIS_LABEL(L) (!SAME_LABEL((L), (NO_LABEL)))

#defineLOCATION(LNO, END_LNO, COL, END_COL) \
 ((const _Py_SourceLocation){(LNO), (END_LNO), (COL), (END_COL)})

staticinlineint
is_block_push(cfg_instr*i)
{
assert(OPCODE_HAS_ARG(i->i_opcode) || !IS_BLOCK_PUSH_OPCODE(i->i_opcode));
returnIS_BLOCK_PUSH_OPCODE(i->i_opcode);
}

staticinlineint
is_jump(cfg_instr*i)
{
returnOPCODE_HAS_JUMP(i->i_opcode);
}

/* One arg*/
#defineINSTR_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*/
#defineINSTR_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);

/***** 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.
*/
staticint
basicblock_next_instr(basicblock*b)
{
assert(b!=NULL);
RETURN_IF_ERROR(
_PyCompile_EnsureArrayLargeEnough(
b->b_iused+1,
 (void**)&b->b_instr,
&b->b_ialloc,
DEFAULT_BLOCK_SIZE,
sizeof(cfg_instr)));
returnb->b_iused++;
}

staticcfg_instr*
basicblock_last_instr(constbasicblock*b) {
assert(b->b_iused >= 0);
if (b->b_iused>0) {
assert(b->b_instr!=NULL);
return&b->b_instr[b->b_iused-1];
 }
returnNULL;
}

/* Allocate a new block and return a pointer to it.
 Returns NULL on error.
*/

staticbasicblock*
cfg_builder_new_block(cfg_builder*g)
{
basicblock*b= (basicblock*)PyMem_Calloc(1, sizeof(basicblock));
if (b==NULL) {
PyErr_NoMemory();
returnNULL;
 }
/* 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;
returnb;
}

staticint
basicblock_addop(basicblock*b, intopcode, intoparg, locationloc)
{
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));

intoff=basicblock_next_instr(b);
if (off<0) {
returnERROR;
 }
cfg_instr*i=&b->b_instr[off];
i->i_opcode=opcode;
i->i_oparg=oparg;
i->i_target=NULL;
i->i_loc=loc;

returnSUCCESS;
}

staticint
basicblock_add_jump(basicblock*b, intopcode, basicblock*target, locationloc)
{
cfg_instr*last=basicblock_last_instr(b);
if (last&&is_jump(last)) {
returnERROR;
 }

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;
returnSUCCESS;
}

staticinlineint
basicblock_append_instructions(basicblock*to, basicblock*from)
{
for (inti=0; i<from->b_iused; i++) {
intn=basicblock_next_instr(to);
if (n<0) {
returnERROR;
 }
to->b_instr[n] =from->b_instr[i];
 }
returnSUCCESS;
}

staticinlineint
basicblock_nofallthrough(constbasicblock*b) {
cfg_instr*last=basicblock_last_instr(b);
return (last&&
 (IS_SCOPE_EXIT_OPCODE(last->i_opcode) ||
IS_UNCONDITIONAL_JUMP_OPCODE(last->i_opcode)));
}

#defineBB_NO_FALLTHROUGH(B) (basicblock_nofallthrough(B))
#defineBB_HAS_FALLTHROUGH(B) (!basicblock_nofallthrough(B))

staticbasicblock*
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) {
returnNULL;
 }
if (basicblock_append_instructions(result, block) <0) {
returnNULL;
 }
returnresult;
}

staticint
basicblock_insert_instruction(basicblock*block, intpos, cfg_instr*instr) {
RETURN_IF_ERROR(basicblock_next_instr(block));
for (inti=block->b_iused-1; i>pos; i--) {
block->b_instr[i] =block->b_instr[i-1];
 }
block->b_instr[pos] =*instr;
returnSUCCESS;
}

/* For debugging purposes only */
#if0
staticvoid
dump_instr(cfg_instr*i)
{
constchar*jump=is_jump(i) ? "jump " : "";

chararg[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);
}

staticinlineint
basicblock_returns(constbasicblock*b) {
cfg_instr*last=basicblock_last_instr(b);
returnlast&& (last->i_opcode==RETURN_VALUE||last->i_opcode==RETURN_CONST);
}

staticvoid
dump_basicblock(constbasicblock*b)
{
constchar*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) {
inti;
for (i=0; i<b->b_iused; i++) {
fprintf(stderr, " [%02d] ", i);
dump_instr(b->b_instr+i);
 }
 }
}

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

#endif


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

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

staticinlineint
basicblock_exits_scope(constbasicblock*b) {
cfg_instr*last=basicblock_last_instr(b);
returnlast&&IS_SCOPE_EXIT_OPCODE(last->i_opcode);
}

staticinlineint
basicblock_has_eval_break(constbasicblock*b) {
for (inti=0; i<b->b_iused; i++) {
if (OPCODE_HAS_EVAL_BREAK(b->b_instr[i].i_opcode)) {
return true;
 }
 }
return false;
}

staticbool
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;
}

staticint
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) {
returnERROR;
 }
b->b_label=g->g_current_label;
g->g_current_label=NO_LABEL;
cfg_builder_use_next_block(g, b);
 }
returnSUCCESS;
}

#ifndefNDEBUG
staticbool
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

staticint
init_cfg_builder(cfg_builder*g)
{
g->g_block_list=NULL;
basicblock*block=cfg_builder_new_block(g);
if (block==NULL) {
returnERROR;
 }
g->g_curblock=g->g_entryblock=block;
g->g_current_label=NO_LABEL;
returnSUCCESS;
}

cfg_builder*
_PyCfgBuilder_New(void)
{
cfg_builder*g=PyMem_Malloc(sizeof(cfg_builder));
if (g==NULL) {
PyErr_NoMemory();
returnNULL;
 }
memset(g, 0, sizeof(cfg_builder));
if (init_cfg_builder(g) <0) {
PyMem_Free(g);
returnNULL;
 }
returng;
}

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)
{
intnblocks=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();
returnERROR;
 }
returnSUCCESS;
}

int
_PyCfgBuilder_UseLabel(cfg_builder*g, jump_target_labellbl)
{
g->g_current_label=lbl;
returncfg_builder_maybe_start_new_block(g);
}

int
_PyCfgBuilder_Addop(cfg_builder*g, intopcode, intoparg, locationloc)
{
RETURN_IF_ERROR(cfg_builder_maybe_start_new_block(g));
returnbasicblock_addop(g->g_curblock, opcode, oparg, loc);
}


staticbasicblock*
next_nonempty_block(basicblock*b)
{
while (b&&b->b_iused==0) {
b=b->b_next;
 }
returnb;
}

/***** debugging helpers *****/

#ifndefNDEBUG
staticintremove_redundant_nops(cfg_builder*g);

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

staticbool
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) *****/

staticint
normalize_jumps_in_block(cfg_builder*g, basicblock*b) {
cfg_instr*last=basicblock_last_instr(b);
if (last==NULL|| !is_jump(last) ||
IS_UNCONDITIONAL_JUMP_OPCODE(last->i_opcode)) {
returnSUCCESS;
 }
assert(!IS_ASSEMBLER_OPCODE(last->i_opcode));

boolis_forward=last->i_target->b_visited==0;
if (is_forward) {
returnSUCCESS;
 }

intreversed_opcode=0;
switch(last->i_opcode) {
casePOP_JUMP_IF_NOT_NONE:
reversed_opcode=POP_JUMP_IF_NONE;
break;
casePOP_JUMP_IF_NONE:
reversed_opcode=POP_JUMP_IF_NOT_NONE;
break;
casePOP_JUMP_IF_FALSE:
reversed_opcode=POP_JUMP_IF_TRUE;
break;
casePOP_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) {
returnERROR;
 }
RETURN_IF_ERROR(
basicblock_add_jump(backwards_jump, JUMP, target, last->i_loc));
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;
returnSUCCESS;
}


staticint
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));
 }
returnSUCCESS;
}

staticint
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 (inti=0; i<b->b_iused; i++) {
intopcode=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.");
returnERROR;
 }
 }
 }
 }
returnSUCCESS;
}

staticint
get_max_label(basicblock*entryblock)
{
intlbl=-1;
for (basicblock*b=entryblock; b!=NULL; b=b->b_next) {
if (b->b_label.id>lbl) {
lbl=b->b_label.id;
 }
 }
returnlbl;
}

/* Calculate the actual jump target from the target_label */
staticint
translate_jump_labels_to_targets(basicblock*entryblock)
{
intmax_label=get_max_label(entryblock);
size_tmapsize=sizeof(basicblock*) * (max_label+1);
basicblock**label2block= (basicblock**)PyMem_Malloc(mapsize);
if (!label2block) {
PyErr_NoMemory();
returnERROR;
 }
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 (inti=0; i<b->b_iused; i++) {
cfg_instr*instr=&b->b_instr[i];
assert(instr->i_target==NULL);
if (HAS_TARGET(instr->i_opcode)) {
intlbl=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);
returnSUCCESS;
}

staticint
mark_except_handlers(basicblock*entryblock) {
#ifndefNDEBUG
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 (inti=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;
 }
 }
 }
returnSUCCESS;
}


struct_PyCfgExceptStack {
basicblock*handlers[CO_MAXBLOCKS+2];
intdepth;
};


staticbasicblock*
push_except_block(struct_PyCfgExceptStack*stack, cfg_instr*setup) {
assert(is_block_push(setup));
intopcode=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;
returntarget;
}

staticbasicblock*
pop_except_block(struct_PyCfgExceptStack*stack) {
assert(stack->depth>0);
returnstack->handlers[--stack->depth];
}

staticbasicblock*
except_stack_top(struct_PyCfgExceptStack*stack) {
returnstack->handlers[stack->depth];
}

staticstruct_PyCfgExceptStack*
make_except_stack(void) {
struct_PyCfgExceptStack*new=PyMem_Malloc(sizeof(struct_PyCfgExceptStack));
if (new==NULL) {
PyErr_NoMemory();
returnNULL;
 }
new->depth=0;
new->handlers[0] =NULL;
returnnew;
}

staticstruct_PyCfgExceptStack*
copy_except_stack(struct_PyCfgExceptStack*stack) {
struct_PyCfgExceptStack*copy=PyMem_Malloc(sizeof(struct_PyCfgExceptStack));
if (copy==NULL) {
PyErr_NoMemory();
returnNULL;
 }
memcpy(copy, stack, sizeof(struct_PyCfgExceptStack));
returncopy;
}

staticbasicblock**
make_cfg_traversal_stack(basicblock*entryblock) {
intnblocks=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();
 }
returnstack;
}

Py_LOCAL_INLINE(int)
stackdepth_push(basicblock***sp, basicblock*b, intdepth)
{
if (!(b->b_startdepth<0||b->b_startdepth==depth)) {
PyErr_Format(PyExc_ValueError, "Invalid CFG, inconsistent stackdepth");
returnERROR;
 }
if (b->b_startdepth<depth&&b->b_startdepth<100) {
assert(b->b_startdepth<0);
b->b_startdepth=depth;
*(*sp)++=b;
 }
returnSUCCESS;
}

/* 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.
 */
staticint
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) {
returnERROR;
 }


intstackdepth=-1;
intmaxdepth=0;
basicblock**sp=stack;
if (stackdepth_push(&sp, entryblock, 0) <0) {
 goto error;
 }
while (sp!=stack) {
basicblock*b=*--sp;
intdepth=b->b_startdepth;
assert(depth >= 0);
basicblock*next=b->b_next;
for (inti=0; i<b->b_iused; i++) {
cfg_instr*instr=&b->b_instr[i];
inteffect=PyCompile_OpcodeStackEffectWithJump(
instr->i_opcode, instr->i_oparg, 0);
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;
 }
intnew_depth=depth+effect;
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);
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;
 }
inttarget_depth=depth+effect;
assert(target_depth >= 0); /* invalid code or bug in stackdepth() */
if (target_depth>maxdepth) {
maxdepth=target_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);
returnstackdepth;
}

staticint
label_exception_targets(basicblock*entryblock) {
basicblock**todo_stack=make_cfg_traversal_stack(entryblock);
if (todo_stack==NULL) {
returnERROR;
 }
struct_PyCfgExceptStack*except_stack=make_except_stack();
if (except_stack==NULL) {
PyMem_Free(todo_stack);
PyErr_NoMemory();
returnERROR;
 }
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);
intlast_yield_except_depth=-1;
for (inti=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);
 }
elseif (instr->i_opcode==POP_BLOCK) {
handler=pop_except_block(except_stack);
INSTR_SET_OP0(instr, NOP);
 }
elseif (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++;
 }
 }
elseif (instr->i_opcode==YIELD_VALUE) {
instr->i_except=handler;
last_yield_except_depth=except_stack->depth;
 }
elseif (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++;
 }
elseif (except_stack!=NULL) {
PyMem_Free(except_stack);
 }
 }
#ifdefPy_DEBUG
for (basicblock*b=entryblock; b!=NULL; b=b->b_next) {
assert(b->b_exceptstack==NULL);
 }
#endif
PyMem_Free(todo_stack);
returnSUCCESS;
error:
PyMem_Free(todo_stack);
PyMem_Free(except_stack);
returnERROR;
}

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

staticint
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) {
returnERROR;
 }
basicblock**sp=stack;
entryblock->b_predecessors=1;
*sp++=entryblock;
entryblock->b_visited=1;
while (sp>stack) {
basicblock*b=*(--sp);
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++;
 }
for (inti=0; i<b->b_iused; i++) {
basicblock*target;
cfg_instr*instr=&b->b_instr[i];
if (is_jump(instr) ||is_block_push(instr)) {
target=instr->i_target;
if (!target->b_visited) {
*sp++=target;
target->b_visited=1;
 }
target->b_predecessors++;
 }
 }
 }
PyMem_Free(stack);

/* 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;
 }
 }
returnSUCCESS;
}

staticint
basicblock_remove_redundant_nops(basicblock*bb) {
/* Remove NOPs when legal to do so. */