#ifdef _Py_TIER2

/*

* This file contains the support code for CPython's uops optimizer.

* It also performs some simple optimizations.

* It performs a traditional data-flow analysis[1] over the trace of uops.

* Using the information gained, it chooses to emit, or skip certain instructions

* if possible.

*

* [1] For information on data-flow analysis, please see

* https://clang.llvm.org/docs/DataFlowAnalysisIntro.html

*

* */

#include "Python.h"

#include "opcode.h"

#include "pycore_dict.h"

#include "pycore_interp.h"

#include "pycore_opcode_metadata.h"

#include "pycore_opcode_utils.h"

#include "pycore_pystate.h" // _PyInterpreterState_GET()

#include "pycore_pyatomic_ft_wrappers.h" // FT_ATOMIC_*

#include "pycore_tstate.h" // _PyThreadStateImpl

#include "pycore_uop_metadata.h"

#include "pycore_long.h"

#include "pycore_interpframe.h" // _PyFrame_GetCode

#include "pycore_optimizer.h"

#include "pycore_object.h"

#include "pycore_function.h"

#include "pycore_uop_ids.h"

#include "pycore_range.h"

#include "pycore_unicodeobject.h"

#include "pycore_ceval.h"

#include "pycore_floatobject.h"

#include "pycore_setobject.h"

#include "pycore_typeobject.h"

#include <stdarg.h>

#include <stdbool.h>

#include <stdint.h>

#include <stddef.h>

#ifdef Py_DEBUG

extern const char *_PyUOpName(int index);

extern void _PyUOpPrint(const _PyUOpInstruction *uop);

extern void _PyUOpSymPrint(JitOptRef ref);

static const char *const DEBUG_ENV = "PYTHON_OPT_DEBUG";

static inline int get_lltrace(void) {

char *uop_debug = Py_GETENV(DEBUG_ENV);

int lltrace = 0;

if (uop_debug != NULL && *uop_debug >= '0') {

lltrace = *uop_debug - '0'; // TODO: Parse an int and all that

}

return lltrace;

}

#define DPRINTF(level, ...) \

if (get_lltrace() >= (level)) { printf(__VA_ARGS__); }

static void

dump_abstract_stack(_Py_UOpsAbstractFrame *frame, JitOptRef *stack_pointer)

{

printf(" locals=[");

for (int i = 0 ; i < frame->locals_len; i++) {

if (i > 0) {

printf(", ");

}

_PyUOpSymPrint(frame->locals[i]);

}

printf("]\n");

if (stack_pointer < frame->stack) {

printf(" stack=%d\n", (int)(stack_pointer - frame->stack));

}

else {

printf(" stack=[");

for (JitOptRef *ptr = frame->stack; ptr < stack_pointer; ptr++) {

if (ptr != frame->stack) {

printf(", ");

}

_PyUOpSymPrint(*ptr);

}

printf("]\n");

}

fflush(stdout);

}

static void

dump_uop(JitOptContext *ctx, const char *label, int index,

const _PyUOpInstruction *instr, JitOptRef *stack_pointer)

{

if (get_lltrace() >= 3) {

printf("%4d %s: ", index, label);

_PyUOpPrint(instr);

printf("\n");

if (get_lltrace() >= 5 && ctx->frame->code != ((PyCodeObject *)&_Py_InitCleanup)) {

dump_abstract_stack(ctx->frame, stack_pointer);

}

}

}

static void

dump_uops(JitOptContext *ctx, const char *label,

_PyUOpInstruction *start, JitOptRef *stack_pointer)

{

int current_len = uop_buffer_length(&ctx->out_buffer);

int added_count = (int)(ctx->out_buffer.next - start);

for (int j = 0; j < added_count; j++) {

dump_uop(ctx, label, current_len - added_count + j, &start[j], stack_pointer);

}

}

#define DUMP_UOP dump_uop

#define DUMP_UOPS dump_uops

#else

#define DPRINTF(level, ...)

#define DUMP_UOP(ctx, label, index, instr, stack_pointer)

#define DUMP_UOPS(ctx, label, start, stack_pointer)

#endif

static int

get_mutations(PyObject* dict) {

assert(PyDict_CheckExact(dict));

PyDictObject *d = (PyDictObject *)dict;

uint64_t tag = FT_ATOMIC_LOAD_UINT64_RELAXED(d->_ma_watcher_tag);

return (tag >> DICT_MAX_WATCHERS) & ((1 << DICT_WATCHED_MUTATION_BITS) - 1);

}

static void

increment_mutations(PyObject* dict) {

assert(PyDict_CheckExact(dict));

PyDictObject *d = (PyDictObject *)dict;

FT_ATOMIC_ADD_UINT64(d->_ma_watcher_tag, 1ULL << DICT_MAX_WATCHERS);

}

/* The first two dict watcher IDs are reserved for CPython,

* so we don't need to check that they haven't been used */

#define BUILTINS_WATCHER_ID 0

#define GLOBALS_WATCHER_ID 1

#define TYPE_WATCHER_ID 0

static int

globals_watcher_callback(PyDict_WatchEvent event, PyObject* dict,

PyObject* key, PyObject* new_value)

{

RARE_EVENT_STAT_INC(watched_globals_modification);

assert(get_mutations(dict) < _Py_MAX_ALLOWED_GLOBALS_MODIFICATIONS);

_Py_Executors_InvalidateDependency(_PyInterpreterState_GET(), dict, 1);

increment_mutations(dict);

PyDict_Unwatch(GLOBALS_WATCHER_ID, dict);

return 0;

}

static int

type_watcher_callback(PyTypeObject* type)

{

_Py_Executors_InvalidateDependency(_PyInterpreterState_GET(), type, 1);

PyType_Unwatch(TYPE_WATCHER_ID, (PyObject *)type);

return 0;

}

static int

_setup_optimizer_watchers(void *Py_UNUSED(arg))

{

PyInterpreterState *interp = _PyInterpreterState_GET();

FT_ATOMIC_STORE_PTR_RELEASE(

interp->dict_state.watchers[GLOBALS_WATCHER_ID],

globals_watcher_callback);

interp->type_watchers[TYPE_WATCHER_ID] = type_watcher_callback;

return 0;

}

static void

watch_type(PyTypeObject *type, _PyBloomFilter *filter)

{

if (_Py_IsImmortal(type) && (type->tp_flags & Py_TPFLAGS_IMMUTABLETYPE)) {

return;

}

PyType_Watch(TYPE_WATCHER_ID, (PyObject *)type);

_Py_BloomFilter_Add(filter, type);

}

static PyObject *

convert_global_to_const(_PyUOpInstruction *inst, PyObject *obj)

{

assert(inst->opcode == _LOAD_GLOBAL_MODULE || inst->opcode == _LOAD_GLOBAL_BUILTINS || inst->opcode == _LOAD_ATTR_MODULE);

assert(PyDict_CheckExact(obj));

PyDictObject *dict = (PyDictObject *)obj;

assert(dict->ma_keys->dk_kind == DICT_KEYS_UNICODE);

PyDictUnicodeEntry *entries = DK_UNICODE_ENTRIES(dict->ma_keys);

int64_t index = inst->operand1;

assert(index <= UINT16_MAX);

if ((int)index >= dict->ma_keys->dk_nentries) {

return NULL;

}

PyDictKeysObject *keys = dict->ma_keys;

if (keys->dk_version != inst->operand0) {

return NULL;

}

PyObject *res = entries[index].me_value;

if (res == NULL) {

return NULL;

}

if (_Py_IsImmortal(res)) {

inst->opcode = _LOAD_CONST_INLINE_BORROW;

} else {

inst->opcode = _LOAD_CONST_INLINE;

}

inst->operand0 = (uint64_t)res;

return res;

}

static bool

incorrect_keys(PyObject *obj, uint32_t version)

{

if (!PyDict_CheckExact(obj)) {

return true;

}

PyDictObject *dict = (PyDictObject *)obj;

return dict->ma_keys->dk_version != version;

}

#define STACK_LEVEL() ((int)(stack_pointer - ctx->frame->stack))

#define STACK_SIZE() ((int)(ctx->frame->stack_len))

static inline int

is_terminator_uop(const _PyUOpInstruction *uop)

{

int opcode = uop->opcode;

return (

opcode == _EXIT_TRACE ||

opcode == _JUMP_TO_TOP ||

opcode == _DYNAMIC_EXIT ||

opcode == _DEOPT

);

}

#define CURRENT_FRAME_IS_INIT_SHIM() (ctx->frame->code == ((PyCodeObject *)&_Py_InitCleanup))

#define GETLOCAL(idx) ((ctx->frame->locals[idx]))

#define REPLACE_OP(INST, OP, ARG, OPERAND) \

(INST)->opcode = OP; \

(INST)->oparg = ARG; \

(INST)->operand0 = OPERAND;

#define ADD_OP(OP, ARG, OPERAND) add_op(ctx, this_instr, (OP), (ARG), (OPERAND))

static inline void

add_op(JitOptContext *ctx, _PyUOpInstruction *this_instr,

uint16_t opcode, uint16_t oparg, uintptr_t operand0)

{

_PyUOpInstruction *out = ctx->out_buffer.next;

assert(out < ctx->out_buffer.end);

out->opcode = (opcode);

out->format = this_instr->format;

out->oparg = (oparg);

out->target = this_instr->target;

out->operand0 = (operand0);

out->operand1 = this_instr->operand1;

#ifdef Py_STATS

out->fitness = this_instr->fitness;

#endif

ctx->out_buffer.next++;

}

/* Shortened forms for convenience, used in optimizer_bytecodes.c */

#define sym_is_not_null _Py_uop_sym_is_not_null

#define sym_is_const _Py_uop_sym_is_const

#define sym_is_safe_const _Py_uop_sym_is_safe_const

#define sym_is_not_container _Py_uop_sym_is_not_container

#define sym_get_const _Py_uop_sym_get_const

#define sym_new_const_steal _Py_uop_sym_new_const_steal

#define sym_get_const_as_stackref _Py_uop_sym_get_const_as_stackref

#define sym_new_unknown _Py_uop_sym_new_unknown

#define sym_new_not_null _Py_uop_sym_new_not_null

#define sym_new_type _Py_uop_sym_new_type

#define sym_is_null _Py_uop_sym_is_null

#define sym_new_const _Py_uop_sym_new_const

#define sym_new_null _Py_uop_sym_new_null

#define sym_has_type _Py_uop_sym_has_type

#define sym_get_type _Py_uop_sym_get_type

#define sym_get_probable_type _Py_uop_sym_get_probable_type

#define sym_matches_type _Py_uop_sym_matches_type

#define sym_matches_type_version _Py_uop_sym_matches_type_version

#define sym_get_type_version _Py_uop_sym_get_type_version

#define sym_set_null(SYM) _Py_uop_sym_set_null(ctx, SYM)

#define sym_set_non_null(SYM) _Py_uop_sym_set_non_null(ctx, SYM)

#define sym_set_type(SYM, TYPE) _Py_uop_sym_set_type(ctx, SYM, TYPE)

#define sym_set_type_version(SYM, VERSION) _Py_uop_sym_set_type_version(ctx, SYM, VERSION)

#define sym_set_const(SYM, CNST) _Py_uop_sym_set_const(ctx, SYM, CNST)

#define sym_set_compact_int(SYM) _Py_uop_sym_set_compact_int(ctx, SYM)

#define sym_is_bottom _Py_uop_sym_is_bottom

#define sym_truthiness _Py_uop_sym_truthiness

#define frame_new _Py_uop_frame_new

#define frame_new_from_symbol _Py_uop_frame_new_from_symbol

#define frame_pop _Py_uop_frame_pop

#define sym_new_tuple _Py_uop_sym_new_tuple

#define sym_tuple_getitem _Py_uop_sym_tuple_getitem

#define sym_tuple_length _Py_uop_sym_tuple_length

#define sym_is_immortal _Py_uop_symbol_is_immortal

#define sym_is_compact_int _Py_uop_sym_is_compact_int

#define sym_new_compact_int _Py_uop_sym_new_compact_int

#define sym_new_truthiness _Py_uop_sym_new_truthiness

#define sym_new_predicate _Py_uop_sym_new_predicate

#define sym_apply_predicate_narrowing _Py_uop_sym_apply_predicate_narrowing

#define sym_set_recorded_type(SYM, TYPE) _Py_uop_sym_set_recorded_type(ctx, SYM, TYPE)

#define sym_set_recorded_value(SYM, VAL) _Py_uop_sym_set_recorded_value(ctx, SYM, VAL)

#define sym_set_recorded_gen_func(SYM, VAL) _Py_uop_sym_set_recorded_gen_func(ctx, SYM, VAL)

#define sym_get_probable_func_code _Py_uop_sym_get_probable_func_code

#define sym_get_probable_value _Py_uop_sym_get_probable_value

#define sym_set_stack_depth(DEPTH, SP) _Py_uop_sym_set_stack_depth(ctx, DEPTH, SP)

/* Comparison oparg masks */

#define COMPARE_LT_MASK 2

#define COMPARE_GT_MASK 4

#define COMPARE_EQ_MASK 8

#define JUMP_TO_LABEL(label) goto label;

static int

check_stack_bounds(JitOptContext *ctx, JitOptRef *stack_pointer, int offset, int opcode)

{

int stack_level = (int)(stack_pointer + (offset) - ctx->frame->stack);

int should_check = !CURRENT_FRAME_IS_INIT_SHIM() ||

(opcode == _RETURN_VALUE) ||

(opcode == _RETURN_GENERATOR) ||

(opcode == _YIELD_VALUE);

if (should_check && (stack_level < 0 || stack_level > STACK_SIZE() + MAX_CACHED_REGISTER)) {

ctx->contradiction = true;

ctx->done = true;

return 1;

}

return 0;

}

#define CHECK_STACK_BOUNDS(offset) \

if (check_stack_bounds(ctx, stack_pointer, offset, opcode)) { \

break; \

} \

static int

optimize_to_bool(

_PyUOpInstruction *this_instr,

JitOptContext *ctx,

JitOptRef value,

JitOptRef *result_ptr,

uint16_t prefix, uint16_t suffix)

{

if (sym_matches_type(value, &PyBool_Type)) {

ADD_OP(_NOP, 0, 0);

*result_ptr = value;

return 1;

}

int truthiness = sym_truthiness(ctx, value);

if (truthiness >= 0) {

PyObject *load = truthiness ? Py_True : Py_False;

if (prefix != _NOP) {

ADD_OP(prefix, 0, 0);

}

ADD_OP(_LOAD_CONST_INLINE_BORROW, 0, (uintptr_t)load);

if (suffix != _NOP) {

ADD_OP(suffix, 2, 0);

}

*result_ptr = sym_new_const(ctx, load);

return 1;

}

return 0;

}

static void

optimize_dict_known_hash(

JitOptContext *ctx, _PyBloomFilter *dependencies, _PyUOpInstruction *this_instr,

PyObject *sub, uint16_t opcode)

{

if (PyUnicode_CheckExact(sub) || PyLong_CheckExact(sub) || PyBytes_CheckExact(sub)

|| PyFloat_CheckExact(sub) || PyComplex_CheckExact(sub)) {

// PyObject_Hash can't fail on these types

ADD_OP(opcode, 0, PyObject_Hash(sub));

}

else if (PyTuple_CheckExact(sub)) {

// only use known hash variant when hash of tuple is already computed

// since computing it can call arbitrary code

Py_hash_t hash = ((PyTupleObject *)sub)->ob_hash;

if (hash != -1) {

ADD_OP(opcode, 0, hash);

}

}

else if (Py_TYPE(sub)->tp_hash == PyBaseObject_Type.tp_hash) {

// for user-defined objects which don't override tp_hash

Py_hash_t hash = PyObject_Hash(sub);

ADD_OP(opcode, 0, hash);

watch_type(Py_TYPE(sub), dependencies);

}

}

static void

eliminate_pop_guard(_PyUOpInstruction *this_instr, JitOptContext *ctx, bool exit)

{

ADD_OP(_POP_TOP, 0, 0);

if (exit) {

REPLACE_OP((this_instr+1), _EXIT_TRACE, 0, 0);

this_instr[1].target = this_instr->target;

}

}

static JitOptRef

lookup_attr(JitOptContext *ctx, _PyBloomFilter *dependencies, _PyUOpInstruction *this_instr,

PyTypeObject *type, PyObject *name,

uint16_t prefix, uint16_t suffix)

{

// The cached value may be dead, so we need to do the lookup again... :(

if (type && PyType_Check(type)) {

PyObject *lookup = _PyType_Lookup(type, name);

if (lookup) {

bool immortal = _Py_IsImmortal(lookup) || (type->tp_flags & Py_TPFLAGS_IMMUTABLETYPE);

if (prefix != _NOP) {

ADD_OP(prefix, 0, 0);

}

ADD_OP(immortal ? _LOAD_CONST_INLINE_BORROW : _LOAD_CONST_INLINE,

0, (uintptr_t)lookup);

if (suffix != _NOP) {

ADD_OP(suffix, 2, 0);

}

if ((type->tp_flags & Py_TPFLAGS_IMMUTABLETYPE) == 0) {

watch_type(type, dependencies);

}

return sym_new_const(ctx, lookup);

}

}

return sym_new_not_null(ctx);

}

static void

optimize_pop_top(JitOptContext *ctx, _PyUOpInstruction *this_instr, JitOptRef value)

{

PyTypeObject *typ = sym_get_type(value);

if (PyJitRef_IsBorrowed(value) ||

sym_is_immortal(PyJitRef_Unwrap(value)) ||

sym_is_null(value)) {

ADD_OP(_POP_TOP_NOP, 0, 0);

}

else if (typ == &PyLong_Type) {

ADD_OP(_POP_TOP_INT, 0, 0);

}

else if (typ == &PyFloat_Type) {

ADD_OP(_POP_TOP_FLOAT, 0, 0);

}

else if (typ == &PyUnicode_Type) {

ADD_OP(_POP_TOP_UNICODE, 0, 0);

}

else {

ADD_OP(_POP_TOP, 0, 0);

}

}

/* Look up name via super (normal case from supercheck where

su_obj_type = Py_TYPE(obj)). */

static JitOptRef

lookup_super_attr(JitOptContext *ctx, _PyBloomFilter *dependencies,

_PyUOpInstruction *this_instr,

PyTypeObject *su_type, PyTypeObject *obj_type,

PyObject *name,

uint16_t immortal, uint16_t mortal, uint16_t suffix)

{

if (su_type == NULL || obj_type == NULL) {

return sym_new_not_null(ctx);

}

/* Normal case: obj_type must be a subtype of su_type */

if (!PyType_IsSubtype(obj_type, su_type)) {

return sym_new_not_null(ctx);

}

PyObject *lookup = _PySuper_LookupDescr(su_type, obj_type, name);

if (lookup == NULL) {

if (PyErr_Occurred()) {

PyErr_Clear();

}

return sym_new_not_null(ctx);

}

if ((Py_TYPE(lookup)->tp_flags & Py_TPFLAGS_METHOD_DESCRIPTOR) == 0) {

Py_DECREF(lookup);

return sym_new_not_null(ctx);

}

int opcode = mortal;

if (_Py_IsImmortal(lookup) || (obj_type->tp_flags & Py_TPFLAGS_IMMUTABLETYPE)) {

opcode = immortal;

}

ADD_OP(_SWAP, 3, 0);

ADD_OP(_POP_TOP, 0, 0);

ADD_OP(_POP_TOP, 0, 0);

ADD_OP(opcode, 0, (uintptr_t)lookup);

if (suffix != _NOP) {

ADD_OP(suffix, 2, 0);

}

// if obj_type is immutable, then all its superclasses are immutable

if ((obj_type->tp_flags & Py_TPFLAGS_IMMUTABLETYPE) == 0) {

watch_type(su_type, dependencies);

watch_type(obj_type, dependencies);

}

return sym_new_const_steal(ctx, lookup);

}

static

PyCodeObject *

get_current_code_object(JitOptContext *ctx)

{

return (PyCodeObject *)ctx->frame->code;

}

static PyObject *

get_co_name(JitOptContext *ctx, int index)

{

return PyTuple_GET_ITEM(get_current_code_object(ctx)->co_names, index);

}

static int

get_test_bit_for_bools(void) {

#ifdef Py_STACKREF_DEBUG

uintptr_t false_bits = _Py_STACKREF_FALSE_INDEX;

uintptr_t true_bits = _Py_STACKREF_TRUE_INDEX;

#else

uintptr_t false_bits = (uintptr_t)&_Py_FalseStruct;

uintptr_t true_bits = (uintptr_t)&_Py_TrueStruct;

#endif

for (int i = 4; i < 8; i++) {

if ((true_bits ^ false_bits) & (uintptr_t)(1 << i)) {

return i;

}

}

return 0;

}

static int

test_bit_set_in_true(int bit) {

#ifdef Py_STACKREF_DEBUG

uintptr_t true_bits = _Py_STACKREF_TRUE_INDEX;

#else

uintptr_t true_bits = (uintptr_t)&_Py_TrueStruct;

#endif

assert((true_bits ^ ((uintptr_t)&_Py_FalseStruct)) & (uintptr_t)(1 << bit));

return true_bits & (uintptr_t)(1 << bit);

}

#ifdef Py_DEBUG

void

_Py_opt_assert_within_stack_bounds(

_Py_UOpsAbstractFrame *frame, JitOptRef *stack_pointer,

const char *filename, int lineno

) {

if (frame->code == ((PyCodeObject *)&_Py_InitCleanup)) {

return;

}

int level = (int)(stack_pointer - frame->stack);

if (level < 0) {

printf("Stack underflow (depth = %d) at %s:%d\n", level, filename, lineno);

fflush(stdout);

abort();

}

int size = (int)(frame->stack_len) + MAX_CACHED_REGISTER;

if (level > size) {

printf("Stack overflow (depth = %d) at %s:%d\n", level, filename, lineno);

fflush(stdout);

abort();

}

}

#endif

#ifdef Py_DEBUG

#define ASSERT_WITHIN_STACK_BOUNDS(F, L) _Py_opt_assert_within_stack_bounds(ctx->frame, stack_pointer, (F), (L))

#else

#define ASSERT_WITHIN_STACK_BOUNDS(F, L) (void)0

#endif

/* >0 (length) for success, 0 for not ready, clears all possible errors. */

static int

optimize_uops(

_PyThreadStateImpl *tstate,

_PyUOpInstruction *trace,

int trace_len,

int curr_stacklen,

_PyUOpInstruction *output,

_PyBloomFilter *dependencies

)

{

assert(!PyErr_Occurred());

assert(tstate->jit_tracer_state != NULL);

PyFunctionObject *func = tstate->jit_tracer_state->initial_state.func;

JitOptContext *ctx = &tstate->jit_tracer_state->opt_context;

uint32_t opcode = UINT16_MAX;

uop_buffer_init(&ctx->out_buffer, output, UOP_MAX_TRACE_LENGTH);

// Make sure that watchers are set up

PyInterpreterState *interp = _PyInterpreterState_GET();

_PyOnceFlag_CallOnce(&interp->dict_state.watcher_setup_once,

_setup_optimizer_watchers, NULL);

_Py_uop_abstractcontext_init(ctx, dependencies);

_Py_UOpsAbstractFrame *frame = _Py_uop_frame_new(ctx, (PyCodeObject *)func->func_code, NULL, 0);

if (frame == NULL) {

return 0;

}

frame->func = func;

ctx->curr_frame_depth++;

ctx->frame = frame;

_Py_uop_sym_set_stack_depth(ctx, curr_stacklen, frame->stack_pointer);

_PyUOpInstruction *this_instr = NULL;

JitOptRef *stack_pointer = ctx->frame->stack_pointer;

for (int i = 0; i < trace_len; i++) {

this_instr = &trace[i];

if (ctx->done) {

// Don't do any more optimization, but

// we still need to reach a terminator for corrctness.

*(ctx->out_buffer.next++) = *this_instr;

if (is_terminator_uop(this_instr)) {

break;

}

continue;

}

int oparg = this_instr->oparg;

opcode = this_instr->opcode;

if (!CURRENT_FRAME_IS_INIT_SHIM()) {

stack_pointer = ctx->frame->stack_pointer;

}

DUMP_UOP(ctx, "abs", (int)(this_instr - trace), this_instr, stack_pointer);

_PyUOpInstruction *out_ptr = ctx->out_buffer.next;

switch (opcode) {

#include "optimizer_cases.c.h"

default:

DPRINTF(1, "\nUnknown opcode in abstract interpreter\n");

Py_UNREACHABLE();

}

// If no ADD_OP was called during this iteration, copy the original instruction

if (ctx->out_buffer.next == out_ptr) {

*(ctx->out_buffer.next++) = *this_instr;

}

assert(ctx->frame != NULL);

DUMP_UOPS(ctx, "out", out_ptr, stack_pointer);

if (!CURRENT_FRAME_IS_INIT_SHIM() && !ctx->done) {

DPRINTF(3, " stack_level %d\n", STACK_LEVEL());

ctx->frame->stack_pointer = stack_pointer;

assert(STACK_LEVEL() >= 0);

}

}

if (ctx->out_of_space) {

DPRINTF(3, "\n");

DPRINTF(1, "Out of space in abstract interpreter\n");

}

if (ctx->contradiction) {

// Attempted to push a "bottom" (contradiction) symbol onto the stack.

// This means that the abstract interpreter has optimized to trace

// to an unreachable estate.

// We *could* generate an _EXIT_TRACE or _FATAL_ERROR here, but hitting

// bottom usually indicates an optimizer bug, so we are probably better off

// retrying later.

DPRINTF(3, "\n");

DPRINTF(1, "Hit bottom in abstract interpreter\n");

_Py_uop_abstractcontext_fini(ctx);

OPT_STAT_INC(optimizer_contradiction);

return 0;

}

/* Either reached the end or cannot optimize further, but there

* would be no benefit in retrying later */

_Py_uop_abstractcontext_fini(ctx);

// Check that the trace ends with a proper terminator

if (uop_buffer_length(&ctx->out_buffer) > 0) {

assert(is_terminator_uop(uop_buffer_last(&ctx->out_buffer)));

}

return uop_buffer_length(&ctx->out_buffer);

error:

DPRINTF(3, "\n");

DPRINTF(1, "Encountered error in abstract interpreter\n");

if (opcode <= MAX_UOP_ID) {

OPT_ERROR_IN_OPCODE(opcode);

}

_Py_uop_abstractcontext_fini(ctx);

assert(PyErr_Occurred());

PyErr_Clear();

return 0;

}

const uint16_t op_without_push[MAX_UOP_ID + 1] = {

[_COPY] = _NOP,

[_LOAD_CONST_INLINE] = _NOP,

[_LOAD_CONST_INLINE_BORROW] = _NOP,

[_LOAD_FAST] = _NOP,

[_LOAD_FAST_BORROW] = _NOP,

[_LOAD_SMALL_INT] = _NOP,

[_PUSH_NULL] = _NOP,

};

const bool op_skip[MAX_UOP_ID + 1] = {

[_NOP] = true,

[_CHECK_VALIDITY] = true,

[_CHECK_PERIODIC] = true,

[_SET_IP] = true,

};

const uint16_t op_without_pop[MAX_UOP_ID + 1] = {

[_POP_TOP] = _NOP,

[_POP_TOP_NOP] = _NOP,

[_POP_TOP_INT] = _NOP,

[_POP_TOP_FLOAT] = _NOP,

[_POP_TOP_UNICODE] = _NOP,

};

static int

remove_unneeded_uops(_PyUOpInstruction *buffer, int buffer_size)

{

/* Remove _SET_IP and _CHECK_VALIDITY where possible.

* _SET_IP is needed if the following instruction escapes or

* could error. _CHECK_VALIDITY is needed if the previous

* instruction could have escaped. */

int last_set_ip = -1;

bool may_have_escaped = true;

for (int pc = 0; pc < buffer_size; pc++) {

int opcode = buffer[pc].opcode;

switch (opcode) {

case _START_EXECUTOR:

may_have_escaped = false;

break;

case _SET_IP:

buffer[pc].opcode = _NOP;

last_set_ip = pc;

break;

case _CHECK_VALIDITY:

if (may_have_escaped) {

may_have_escaped = false;

}

else {

buffer[pc].opcode = _NOP;

}

break;

case _EXIT_TRACE:

default:

{

// Cancel out pushes and pops, repeatedly. So:

// _LOAD_FAST + _POP_TOP + _POP_TOP + _LOAD_CONST_INLINE_BORROW + _POP_TOP

// ...becomes:

// _NOP + _NOP + _POP_TOP + _NOP + _NOP

while (op_without_pop[opcode]) {

_PyUOpInstruction *last = &buffer[pc - 1];

while (op_skip[last->opcode]) {

last--;

}

if (op_without_push[last->opcode] && op_without_pop[opcode]) {

last->opcode = op_without_push[last->opcode];

opcode = buffer[pc].opcode = op_without_pop[opcode];

if (op_without_pop[last->opcode]) {

opcode = last->opcode;

pc = (int)(last - buffer);

}

}

else {

break;

}

}

/* _PUSH_FRAME doesn't escape or error, but it

* does need the IP for the return address */

bool needs_ip = (opcode == _PUSH_FRAME || opcode == _YIELD_VALUE || opcode == _DYNAMIC_EXIT || opcode == _EXIT_TRACE);

if (_PyUop_Flags[opcode] & HAS_ESCAPES_FLAG) {

needs_ip = true;

may_have_escaped = true;

}

if (needs_ip && last_set_ip >= 0) {

assert(buffer[last_set_ip].opcode == _NOP);

buffer[last_set_ip].opcode = _SET_IP;

last_set_ip = -1;

}

if (opcode == _EXIT_TRACE) {

return pc + 1;

}

break;

}

case _JUMP_TO_TOP:

case _DYNAMIC_EXIT:

case _DEOPT:

return pc + 1;

}

}

Py_UNREACHABLE();

}

// 0 - failure, no error raised, just fall back to Tier 1

// -1 - failure, and raise error

// > 0 - length of optimized trace

int

_Py_uop_analyze_and_optimize(

_PyThreadStateImpl *tstate,

_PyUOpInstruction *buffer,

int length,

int curr_stacklen,

_PyUOpInstruction *output,

_PyBloomFilter *dependencies

)

{

OPT_STAT_INC(optimizer_attempts);

length = optimize_uops(

tstate, buffer, length, curr_stacklen, output, dependencies);

if (length == 0) {

return length;

}

assert(length > 0);

length = remove_unneeded_uops(output, length);

assert(length > 0);

OPT_STAT_INC(optimizer_successes);

return length;

}

#endif /* _Py_TIER2 */