#include "Python.h"

#ifdef _Py_TIER2

#include "opcode.h"

#include "pycore_interp.h"

#include "pycore_backoff.h"

#include "pycore_bitutils.h" // _Py_popcount32()

#include "pycore_ceval.h" // _Py_set_eval_breaker_bit

#include "pycore_code.h" // _Py_GetBaseCodeUnit

#include "pycore_interpframe.h"

#include "pycore_object.h" // _PyObject_GC_UNTRACK()

#include "pycore_opcode_metadata.h" // _PyOpcode_OpName[]

#include "pycore_opcode_utils.h" // MAX_REAL_OPCODE

#include "pycore_optimizer.h" // _Py_uop_analyze_and_optimize()

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

#include "pycore_tuple.h" // _PyTuple_FromArraySteal

#include "pycore_unicodeobject.h" // _PyUnicode_FromASCII

#include "pycore_uop_ids.h"

#include "pycore_jit.h"

#include <stdbool.h>

#include <stdint.h>

#include <stddef.h>

#define NEED_OPCODE_METADATA

#include "pycore_uop_metadata.h" // Uop tables

#undef NEED_OPCODE_METADATA

#define MAX_EXECUTORS_SIZE 256

// Trace too short, no progress:

// _START_EXECUTOR

// _MAKE_WARM

// _CHECK_VALIDITY

// _SET_IP

// is 4-5 instructions.

#define CODE_SIZE_NO_PROGRESS 5

// We start with _START_EXECUTOR, _MAKE_WARM

#define CODE_SIZE_EMPTY 2

#define _PyExecutorObject_CAST(op) ((_PyExecutorObject *)(op))

#ifndef Py_GIL_DISABLED

static bool

has_space_for_executor(PyCodeObject *code, _Py_CODEUNIT *instr)

{

if (code == (PyCodeObject *)&_Py_InitCleanup) {

return false;

}

if (instr->op.code == ENTER_EXECUTOR) {

return true;

}

if (code->co_executors == NULL) {

return true;

}

return code->co_executors->size < MAX_EXECUTORS_SIZE;

}

static int32_t

get_index_for_executor(PyCodeObject *code, _Py_CODEUNIT *instr)

{

if (instr->op.code == ENTER_EXECUTOR) {

return instr->op.arg;

}

_PyExecutorArray *old = code->co_executors;

int size = 0;

int capacity = 0;

if (old != NULL) {

size = old->size;

capacity = old->capacity;

assert(size < MAX_EXECUTORS_SIZE);

}

assert(size <= capacity);

if (size == capacity) {

/* Array is full. Grow array */

int new_capacity = capacity ? capacity * 2 : 4;

_PyExecutorArray *new = PyMem_Realloc(

old,

offsetof(_PyExecutorArray, executors) +

new_capacity * sizeof(_PyExecutorObject *));

if (new == NULL) {

return -1;

}

new->capacity = new_capacity;

new->size = size;

code->co_executors = new;

}

assert(size < code->co_executors->capacity);

return size;

}

static void

insert_executor(PyCodeObject *code, _Py_CODEUNIT *instr, int index, _PyExecutorObject *executor)

{

Py_INCREF(executor);

if (instr->op.code == ENTER_EXECUTOR) {

assert(index == instr->op.arg);

_Py_ExecutorDetach(code->co_executors->executors[index]);

}

else {

assert(code->co_executors->size == index);

assert(code->co_executors->capacity > index);

code->co_executors->size++;

}

executor->vm_data.opcode = instr->op.code;

executor->vm_data.oparg = instr->op.arg;

executor->vm_data.code = code;

executor->vm_data.index = (int)(instr - _PyCode_CODE(code));

code->co_executors->executors[index] = executor;

assert(index < MAX_EXECUTORS_SIZE);

instr->op.code = ENTER_EXECUTOR;

instr->op.arg = index;

}

#endif // Py_GIL_DISABLED

static _PyExecutorObject *

make_executor_from_uops(_PyThreadStateImpl *tstate, _PyUOpInstruction *buffer, int length, const _PyBloomFilter *dependencies);

static int

uop_optimize(_PyInterpreterFrame *frame, PyThreadState *tstate,

_PyExecutorObject **exec_ptr,

bool progress_needed);

/* Returns 1 if optimized, 0 if not optimized, and -1 for an error.

* If optimized, *executor_ptr contains a new reference to the executor

*/

// gh-137573: inlining this function causes stack overflows

Py_NO_INLINE int

_PyOptimizer_Optimize(

_PyInterpreterFrame *frame, PyThreadState *tstate)

{

_PyThreadStateImpl *_tstate = (_PyThreadStateImpl *)tstate;

PyInterpreterState *interp = _PyInterpreterState_GET();

if (!interp->jit) {

// gh-140936: It is possible that interp->jit will become false during

// interpreter finalization. However, the specialized JUMP_BACKWARD_JIT

// instruction may still be present. In this case, we should

// return immediately without optimization.

return 0;

}

_PyExecutorObject *prev_executor = _tstate->jit_tracer_state->initial_state.executor;

if (prev_executor != NULL && !prev_executor->vm_data.valid) {

// gh-143604: If we are a side exit executor and the original executor is no

// longer valid, don't compile to prevent a reference leak.

return 0;

}

assert(!interp->compiling);

assert(_tstate->jit_tracer_state->initial_state.stack_depth >= 0);

#ifndef Py_GIL_DISABLED

assert(_tstate->jit_tracer_state->initial_state.func != NULL);

interp->compiling = true;

// The first executor in a chain and the MAX_CHAIN_DEPTH'th executor *must*

// make progress in order to avoid infinite loops or excessively-long

// side-exit chains. We can only insert the executor into the bytecode if

// this is true, since a deopt won't infinitely re-enter the executor:

int chain_depth = _tstate->jit_tracer_state->initial_state.chain_depth;

chain_depth %= MAX_CHAIN_DEPTH;

bool progress_needed = chain_depth == 0;

PyCodeObject *code = (PyCodeObject *)_tstate->jit_tracer_state->initial_state.code;

_Py_CODEUNIT *start = _tstate->jit_tracer_state->initial_state.start_instr;

if (progress_needed && !has_space_for_executor(code, start)) {

interp->compiling = false;

return 0;

}

_PyExecutorObject *executor;

int err = uop_optimize(frame, tstate, &executor, progress_needed);

if (err <= 0) {

interp->compiling = false;

return err;

}

assert(executor != NULL);

if (progress_needed) {

int index = get_index_for_executor(code, start);

if (index < 0) {

/* Out of memory. Don't raise and assume that the

* error will show up elsewhere.

*

* If an optimizer has already produced an executor,

* it might get confused by the executor disappearing,

* but there is not much we can do about that here. */

Py_DECREF(executor);

interp->compiling = false;

return 0;

}

insert_executor(code, start, index, executor);

}

executor->vm_data.chain_depth = chain_depth;

assert(executor->vm_data.valid);

_PyExitData *exit = _tstate->jit_tracer_state->initial_state.exit;

if (exit != NULL && !progress_needed) {

exit->executor = executor;

}

else {

// An executor inserted into the code object now has a strong reference

// to it from the code object. Thus, we don't need this reference anymore.

Py_DECREF(executor);

}

interp->compiling = false;

return 1;

#else

return 0;

#endif

}

static _PyExecutorObject *

get_executor_lock_held(PyCodeObject *code, int offset)

{

int code_len = (int)Py_SIZE(code);

for (int i = 0 ; i < code_len;) {

if (_PyCode_CODE(code)[i].op.code == ENTER_EXECUTOR && i*2 == offset) {

int oparg = _PyCode_CODE(code)[i].op.arg;

_PyExecutorObject *res = code->co_executors->executors[oparg];

Py_INCREF(res);

return res;

}

i += _PyInstruction_GetLength(code, i);

}

PyErr_SetString(PyExc_ValueError, "no executor at given byte offset");

return NULL;

}

_PyExecutorObject *

_Py_GetExecutor(PyCodeObject *code, int offset)

{

_PyExecutorObject *executor;

Py_BEGIN_CRITICAL_SECTION(code);

executor = get_executor_lock_held(code, offset);

Py_END_CRITICAL_SECTION();

return executor;

}

static PyObject *

is_valid(PyObject *self, PyObject *Py_UNUSED(ignored))

{

return PyBool_FromLong(((_PyExecutorObject *)self)->vm_data.valid);

}

static PyObject *

get_opcode(PyObject *self, PyObject *Py_UNUSED(ignored))

{

return PyLong_FromUnsignedLong(((_PyExecutorObject *)self)->vm_data.opcode);

}

static PyObject *

get_oparg(PyObject *self, PyObject *Py_UNUSED(ignored))

{

return PyLong_FromUnsignedLong(((_PyExecutorObject *)self)->vm_data.oparg);

}

///////////////////// Experimental UOp Optimizer /////////////////////

static int executor_clear(PyObject *executor);

void

_PyExecutor_Free(_PyExecutorObject *self)

{

#ifdef _Py_JIT

_PyJIT_Free(self);

#endif

PyObject_GC_Del(self);

}

static void executor_invalidate(PyObject *op);

static void

executor_clear_exits(_PyExecutorObject *executor)

{

_PyExecutorObject *cold = _PyExecutor_GetColdExecutor();

_PyExecutorObject *cold_dynamic = _PyExecutor_GetColdDynamicExecutor();

for (uint32_t i = 0; i < executor->exit_count; i++) {

_PyExitData *exit = &executor->exits[i];

exit->temperature = initial_unreachable_backoff_counter();

_PyExecutorObject *old = executor->exits[i].executor;

exit->executor = exit->is_dynamic ? cold_dynamic : cold;

Py_DECREF(old);

}

}

void

_Py_ClearExecutorDeletionList(PyInterpreterState *interp)

{

if (interp->executor_deletion_list_head == NULL) {

return;

}

_PyRuntimeState *runtime = &_PyRuntime;

HEAD_LOCK(runtime);

PyThreadState* ts = PyInterpreterState_ThreadHead(interp);

while (ts) {

_PyExecutorObject *current = (_PyExecutorObject *)ts->current_executor;

Py_XINCREF(current);

ts = ts->next;

}

HEAD_UNLOCK(runtime);

_PyExecutorObject *keep_list = NULL;

do {

_PyExecutorObject *exec = interp->executor_deletion_list_head;

interp->executor_deletion_list_head = exec->vm_data.links.next;

if (Py_REFCNT(exec) == 0) {

_PyExecutor_Free(exec);

} else {

exec->vm_data.links.next = keep_list;

keep_list = exec;

}

} while (interp->executor_deletion_list_head != NULL);

interp->executor_deletion_list_head = keep_list;

HEAD_LOCK(runtime);

ts = PyInterpreterState_ThreadHead(interp);

while (ts) {

_PyExecutorObject *current = (_PyExecutorObject *)ts->current_executor;

if (current != NULL) {

Py_DECREF((PyObject *)current);

}

ts = ts->next;

}

HEAD_UNLOCK(runtime);

}

static void

add_to_pending_deletion_list(_PyExecutorObject *self)

{

if (self->vm_data.pending_deletion) {

return;

}

self->vm_data.pending_deletion = 1;

PyInterpreterState *interp = PyInterpreterState_Get();

self->vm_data.links.previous = NULL;

self->vm_data.links.next = interp->executor_deletion_list_head;

interp->executor_deletion_list_head = self;

}

static void

uop_dealloc(PyObject *op) {

_PyExecutorObject *self = _PyExecutorObject_CAST(op);

executor_invalidate(op);

assert(self->vm_data.code == NULL);

add_to_pending_deletion_list(self);

}

const char *

_PyUOpName(int index)

{

if (index < 0 || index > MAX_UOP_REGS_ID) {

return NULL;

}

return _PyOpcode_uop_name[index];

}

#ifdef Py_DEBUG

void

_PyUOpPrint(const _PyUOpInstruction *uop)

{

const char *name = _PyUOpName(uop->opcode);

if (name == NULL) {

printf("<uop %d>", uop->opcode);

}

else {

printf("%s", name);

}

switch(uop->format) {

case UOP_FORMAT_TARGET:

printf(" (%d, target=%d, operand0=%#" PRIx64 ", operand1=%#" PRIx64,

uop->oparg,

uop->target,

(uint64_t)uop->operand0,

(uint64_t)uop->operand1);

break;

case UOP_FORMAT_JUMP:

printf(" (%d, jump_target=%d, operand0=%#" PRIx64 ", operand1=%#" PRIx64,

uop->oparg,

uop->jump_target,

(uint64_t)uop->operand0,

(uint64_t)uop->operand1);

break;

default:

printf(" (%d, Unknown format)", uop->oparg);

}

if (_PyUop_Flags[_PyUop_Uncached[uop->opcode]] & HAS_ERROR_FLAG) {

printf(", error_target=%d", uop->error_target);

}

printf(")");

}

#endif

static Py_ssize_t

uop_len(PyObject *op)

{

_PyExecutorObject *self = _PyExecutorObject_CAST(op);

return self->code_size;

}

static PyObject *

uop_item(PyObject *op, Py_ssize_t index)

{

_PyExecutorObject *self = _PyExecutorObject_CAST(op);

Py_ssize_t len = uop_len(op);

if (index < 0 || index >= len) {

PyErr_SetNone(PyExc_IndexError);

return NULL;

}

int opcode = self->trace[index].opcode;

int base_opcode = _PyUop_Uncached[opcode];

const char *name = _PyUOpName(base_opcode);

if (name == NULL) {

name = "<nil>";

}

PyObject *oname = _PyUnicode_FromASCII(name, strlen(name));

if (oname == NULL) {

return NULL;

}

PyObject *oparg = PyLong_FromUnsignedLong(self->trace[index].oparg);

if (oparg == NULL) {

Py_DECREF(oname);

return NULL;

}

PyObject *target = PyLong_FromUnsignedLong(self->trace[index].target);

if (target == NULL) {

Py_DECREF(oparg);

Py_DECREF(oname);

return NULL;

}

PyObject *operand = PyLong_FromUnsignedLongLong(self->trace[index].operand0);

if (operand == NULL) {

Py_DECREF(target);

Py_DECREF(oparg);

Py_DECREF(oname);

return NULL;

}

PyObject *args[4] = { oname, oparg, target, operand };

return _PyTuple_FromArraySteal(args, 4);

}

PySequenceMethods uop_as_sequence = {

.sq_length = uop_len,

.sq_item = uop_item,

};

static int

executor_traverse(PyObject *o, visitproc visit, void *arg)

{

_PyExecutorObject *executor = _PyExecutorObject_CAST(o);

for (uint32_t i = 0; i < executor->exit_count; i++) {

Py_VISIT(executor->exits[i].executor);

}

return 0;

}

static PyObject *

get_jit_code(PyObject *self, PyObject *Py_UNUSED(ignored))

{

#ifndef _Py_JIT

PyErr_SetString(PyExc_RuntimeError, "JIT support not enabled.");

return NULL;

#else

_PyExecutorObject *executor = _PyExecutorObject_CAST(self);

if (executor->jit_code == NULL || executor->jit_size == 0) {

Py_RETURN_NONE;

}

return PyBytes_FromStringAndSize(executor->jit_code, executor->jit_size);

#endif

}

static PyMethodDef uop_executor_methods[] = {

{ "is_valid", is_valid, METH_NOARGS, NULL },

{ "get_jit_code", get_jit_code, METH_NOARGS, NULL},

{ "get_opcode", get_opcode, METH_NOARGS, NULL },

{ "get_oparg", get_oparg, METH_NOARGS, NULL },

{ NULL, NULL },

};

static int

executor_is_gc(PyObject *o)

{

return !_Py_IsImmortal(o);

}

PyTypeObject _PyUOpExecutor_Type = {

PyVarObject_HEAD_INIT(&PyType_Type, 0)

.tp_name = "uop_executor",

.tp_basicsize = offsetof(_PyExecutorObject, exits),

.tp_itemsize = 1,

.tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION | Py_TPFLAGS_HAVE_GC,

.tp_dealloc = uop_dealloc,

.tp_as_sequence = &uop_as_sequence,

.tp_methods = uop_executor_methods,

.tp_traverse = executor_traverse,

.tp_clear = executor_clear,

.tp_is_gc = executor_is_gc,

};

/* TO DO -- Generate these tables */

static const uint16_t

_PyUOp_Replacements[MAX_UOP_ID + 1] = {

[_ITER_JUMP_RANGE] = _GUARD_NOT_EXHAUSTED_RANGE,

[_ITER_JUMP_LIST] = _GUARD_NOT_EXHAUSTED_LIST,

[_ITER_JUMP_TUPLE] = _GUARD_NOT_EXHAUSTED_TUPLE,

[_FOR_ITER] = _FOR_ITER_TIER_TWO,

[_FOR_ITER_VIRTUAL] = _FOR_ITER_VIRTUAL_TIER_TWO,

[_ITER_NEXT_LIST] = _ITER_NEXT_LIST_TIER_TWO,

[_CHECK_PERIODIC_AT_END] = _TIER2_RESUME_CHECK,

[_LOAD_BYTECODE] = _NOP,

[_SEND_VIRTUAL] = _SEND_VIRTUAL_TIER_TWO,

[_SEND_ASYNC_GEN] = _SEND_ASYNC_GEN_TIER_TWO,

};

static const uint8_t

is_for_iter_test[MAX_UOP_ID + 1] = {

[_GUARD_NOT_EXHAUSTED_RANGE] = 1,

[_GUARD_NOT_EXHAUSTED_LIST] = 1,

[_GUARD_NOT_EXHAUSTED_TUPLE] = 1,

[_FOR_ITER_TIER_TWO] = 1,

[_ITER_NEXT_INLINE] = 1,

};

static const uint16_t

BRANCH_TO_GUARD[4][2] = {

[POP_JUMP_IF_FALSE - POP_JUMP_IF_FALSE][0] = _GUARD_IS_TRUE_POP,

[POP_JUMP_IF_FALSE - POP_JUMP_IF_FALSE][1] = _GUARD_IS_FALSE_POP,

[POP_JUMP_IF_TRUE - POP_JUMP_IF_FALSE][0] = _GUARD_IS_FALSE_POP,

[POP_JUMP_IF_TRUE - POP_JUMP_IF_FALSE][1] = _GUARD_IS_TRUE_POP,

[POP_JUMP_IF_NONE - POP_JUMP_IF_FALSE][0] = _GUARD_IS_NOT_NONE_POP,

[POP_JUMP_IF_NONE - POP_JUMP_IF_FALSE][1] = _GUARD_IS_NONE_POP,

[POP_JUMP_IF_NOT_NONE - POP_JUMP_IF_FALSE][0] = _GUARD_IS_NONE_POP,

[POP_JUMP_IF_NOT_NONE - POP_JUMP_IF_FALSE][1] = _GUARD_IS_NOT_NONE_POP,

};

static const uint16_t

guard_ip_uop[MAX_UOP_ID + 1] = {

[_PUSH_FRAME] = _GUARD_IP__PUSH_FRAME,

[_RETURN_GENERATOR] = _GUARD_IP_RETURN_GENERATOR,

[_RETURN_VALUE] = _GUARD_IP_RETURN_VALUE,

[_YIELD_VALUE] = _GUARD_IP_YIELD_VALUE,

};

static const uint16_t

guard_code_version_uop[MAX_UOP_ID + 1] = {

[_PUSH_FRAME] = _GUARD_CODE_VERSION__PUSH_FRAME,

[_RETURN_GENERATOR] = _GUARD_CODE_VERSION_RETURN_GENERATOR,

[_RETURN_VALUE] = _GUARD_CODE_VERSION_RETURN_VALUE,

[_YIELD_VALUE] = _GUARD_CODE_VERSION_YIELD_VALUE,

};

static const uint16_t

dynamic_exit_uop[MAX_UOP_ID + 1] = {

[_GUARD_IP__PUSH_FRAME] = 1,

[_GUARD_IP_RETURN_GENERATOR] = 1,

[_GUARD_IP_RETURN_VALUE] = 1,

[_GUARD_IP_YIELD_VALUE] = 1,

[_GUARD_CODE_VERSION__PUSH_FRAME] = 1,

[_GUARD_CODE_VERSION_RETURN_GENERATOR] = 1,

[_GUARD_CODE_VERSION_RETURN_VALUE] = 1,

[_GUARD_CODE_VERSION_YIELD_VALUE] = 1,

};

#ifdef Py_DEBUG

#define DPRINTF(level, ...) \

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

#else

#define DPRINTF(level, ...)

#endif

static inline void

add_to_trace(

_PyJitTracerState *tracer,

uint16_t opcode,

uint16_t oparg,

uint64_t operand,

uint32_t target)

{

_PyJitUopBuffer *trace = &tracer->code_buffer;

_PyUOpInstruction *inst = trace->next;

inst->opcode = opcode;

inst->format = UOP_FORMAT_TARGET;

inst->target = target;

inst->oparg = oparg;

inst->operand0 = operand;

#ifdef Py_STATS

inst->execution_count = 0;

inst->fitness = tracer->translator_state.fitness;

#endif

trace->next++;

}

#ifdef Py_DEBUG

#define ADD_TO_TRACE(OPCODE, OPARG, OPERAND, TARGET) \

add_to_trace(tracer, (OPCODE), (OPARG), (OPERAND), (TARGET)); \

if (lltrace >= 2) { \

printf("%4d ADD_TO_TRACE: ", uop_buffer_length(trace)); \

_PyUOpPrint(uop_buffer_last(trace)); \

printf("\n"); \

}

#else

#define ADD_TO_TRACE(OPCODE, OPARG, OPERAND, TARGET) \

add_to_trace(tracer, (OPCODE), (OPARG), (OPERAND), (TARGET))

#endif

#define INSTR_IP(INSTR, CODE) \

((uint32_t)((INSTR) - ((_Py_CODEUNIT *)(CODE)->co_code_adaptive)))

/* Branch penalty: 0 for a fully biased branch and FITNESS_BRANCH_BALANCED for

* a balanced or fully off-trace branch. This keeps any single branch from

* consuming more than one balanced-branch cost.

*/

static inline int

compute_branch_penalty(uint16_t history)

{

bool branch_taken = history & 1;

int taken_count = _Py_popcount32((uint32_t)history);

int on_trace_count = branch_taken ? taken_count : 16 - taken_count;

int off_trace = 16 - on_trace_count;

int penalty = off_trace * FITNESS_BRANCH_BALANCED / 8;

if (penalty > FITNESS_BRANCH_BALANCED) {

penalty = FITNESS_BRANCH_BALANCED;

}

return penalty;

}

/* Compute exit quality for the current trace position.

* Higher values mean better places to stop the trace. */

static inline int32_t

compute_exit_quality(_Py_CODEUNIT *target_instr, int opcode,

const _PyJitTracerState *tracer)

{

if (target_instr == tracer->initial_state.close_loop_instr) {

return EXIT_QUALITY_CLOSE_LOOP;

}

else if (target_instr->op.code == ENTER_EXECUTOR) {

return EXIT_QUALITY_ENTER_EXECUTOR;

}

else if (opcode == JUMP_BACKWARD_JIT ||

opcode == JUMP_BACKWARD ||

opcode == JUMP_BACKWARD_NO_INTERRUPT) {

return EXIT_QUALITY_BACKWARD_EDGE;

}

else if (_PyOpcode_Caches[_PyOpcode_Deopt[opcode]] > 0) {

return EXIT_QUALITY_SPECIALIZABLE;

}

return EXIT_QUALITY_DEFAULT;

}

/* Frame penalty: (MAX_ABSTRACT_FRAME_DEPTH-1) pushes exhaust fitness. */

static inline int32_t

compute_frame_penalty(uint16_t fitness_initial)

{

return (int32_t)fitness_initial / (MAX_ABSTRACT_FRAME_DEPTH - 1) + 1;

}

static int

is_terminator(const _PyUOpInstruction *uop)

{

int opcode = _PyUop_Uncached[uop->opcode];

return (

opcode == _EXIT_TRACE ||

opcode == _DEOPT ||

opcode == _JUMP_TO_TOP ||

opcode == _DYNAMIC_EXIT

);

}

/* Returns 1 on success (added to trace), 0 on trace end.

*/

// gh-142543: inlining this function causes stack overflows

Py_NO_INLINE int

_PyJit_translate_single_bytecode_to_trace(

PyThreadState *tstate,

_PyInterpreterFrame *frame,

_Py_CODEUNIT *next_instr,

int stop_tracing_opcode)

{

#ifdef Py_DEBUG

char *python_lltrace = Py_GETENV("PYTHON_LLTRACE");

int lltrace = 0;

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

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

}

#endif

_PyThreadStateImpl *_tstate = (_PyThreadStateImpl *)tstate;

_PyJitTracerState *tracer = _tstate->jit_tracer_state;

PyCodeObject *old_code = tracer->prev_state.instr_code;

bool progress_needed = (tracer->initial_state.chain_depth % MAX_CHAIN_DEPTH) == 0;

_PyJitUopBuffer *trace = &tracer->code_buffer;

_Py_CODEUNIT *this_instr = tracer->prev_state.instr;

_Py_CODEUNIT *target_instr = this_instr;

uint32_t target = 0;

target = Py_IsNone((PyObject *)old_code)

? (uint32_t)(target_instr - _Py_INTERPRETER_TRAMPOLINE_INSTRUCTIONS_PTR)

: INSTR_IP(target_instr, old_code);

// Rewind EXTENDED_ARG so that we see the whole thing.

// We must point to the first EXTENDED_ARG when deopting.

int oparg = tracer->prev_state.instr_oparg;

int opcode = this_instr->op.code;

int rewind_oparg = oparg;

while (rewind_oparg > 255) {

rewind_oparg >>= 8;

target--;

}

if (opcode == ENTER_EXECUTOR) {

_PyExecutorObject *executor = old_code->co_executors->executors[oparg & 255];

opcode = executor->vm_data.opcode;

oparg = (oparg & ~255) | executor->vm_data.oparg;

}

if (_PyOpcode_Caches[_PyOpcode_Deopt[opcode]] > 0) {

uint16_t backoff = (this_instr + 1)->counter.value_and_backoff;

// adaptive_counter_cooldown is a fresh specialization.

// trigger_backoff_counter is what we set during tracing.

// All tracing backoffs should be freshly specialized or untouched.

// If not, that indicates a deopt during tracing, and

// thus the "actual" instruction executed is not the one that is

// in the instruction stream, but rather the deopt.

// It's important we check for this, as some specializations might make

// no progress (they can immediately deopt after specializing).

// We do this to improve performance, as otherwise a compiled trace

// will just deopt immediately.

if (backoff != adaptive_counter_cooldown().value_and_backoff &&

backoff != trigger_backoff_counter().value_and_backoff) {

OPT_STAT_INC(trace_immediately_deopts);

opcode = _PyOpcode_Deopt[opcode];

}

}

// Strange control-flow

bool has_dynamic_jump_taken = OPCODE_HAS_UNPREDICTABLE_JUMP(opcode) &&

(next_instr != this_instr + 1 + _PyOpcode_Caches[_PyOpcode_Deopt[opcode]]);

/* Special case the first instruction,

* so that we can guarantee forward progress */

if (progress_needed && uop_buffer_length(&tracer->code_buffer) < CODE_SIZE_NO_PROGRESS) {

if (OPCODE_HAS_EXIT(opcode) || OPCODE_HAS_DEOPT(opcode)) {

opcode = _PyOpcode_Deopt[opcode];

}

assert(!OPCODE_HAS_EXIT(opcode));

assert(!OPCODE_HAS_DEOPT(opcode));

}

bool needs_guard_ip = OPCODE_HAS_NEEDS_GUARD_IP(opcode);

if (has_dynamic_jump_taken && !needs_guard_ip) {

DPRINTF(2, "Unsupported: dynamic jump taken %s\n", _PyOpcode_OpName[opcode]);

goto unsupported;

}

int is_sys_tracing = (tstate->c_tracefunc != NULL) || (tstate->c_profilefunc != NULL);

if (is_sys_tracing) {

goto done;

}

if (stop_tracing_opcode == _DEOPT) {

// gh-143183: It's important we rewind to the last known proper target.

// The current target might be garbage as stop tracing usually indicates

// we are in something that we can't trace.

DPRINTF(2, "Told to stop tracing\n");

goto unsupported;

}

else if (stop_tracing_opcode != 0) {

assert(stop_tracing_opcode == _EXIT_TRACE);

ADD_TO_TRACE(stop_tracing_opcode, 0, 0, target);

goto done;

}

DPRINTF(2, "%p %d: %s(%d) %d\n", old_code, target, _PyOpcode_OpName[opcode], oparg, needs_guard_ip);

#ifdef Py_DEBUG

if (oparg > 255) {

assert(_Py_GetBaseCodeUnit(old_code, target).op.code == EXTENDED_ARG);

}

#endif

// This happens when a recursive call happens that we can't trace. Such as Python -> C -> Python calls

// If we haven't guarded the IP, then it's untraceable.

if (frame != tracer->prev_state.instr_frame && !needs_guard_ip) {

DPRINTF(2, "Unsupported: unguardable jump taken\n");

goto unsupported;

}

if (oparg > 0xFFFF) {

DPRINTF(2, "Unsupported: oparg too large\n");

unsupported:

{

_PyUOpInstruction *curr = uop_buffer_last(trace);

while (curr->opcode != _SET_IP && uop_buffer_length(trace) > 2) {

trace->next--;

curr = uop_buffer_last(trace);

}

if (curr->opcode == _SET_IP) {

int32_t old_target = (int32_t)uop_get_target(curr);

curr->opcode = _DEOPT;

curr->format = UOP_FORMAT_TARGET;

curr->target = old_target;

}

goto done;

}

}

if (opcode == NOP) {

return 1;

}

if (opcode == JUMP_FORWARD) {

return 1;

}

if (opcode == EXTENDED_ARG) {

return 1;

}

// Stop the trace if fitness has dropped below the exit quality threshold.

_PyJitTracerTranslatorState *ts = &tracer->translator_state;

int32_t eq = compute_exit_quality(target_instr, opcode, tracer);

DPRINTF(3, "Fitness check: %s(%d) fitness=%d, exit_quality=%d, depth=%d\n",

_PyOpcode_OpName[opcode], oparg, ts->fitness, eq, ts->frame_depth);

if (ts->fitness < eq) {

// Heuristic exit: leave operand1=0 so the side exit increments chain_depth.

ADD_TO_TRACE(_EXIT_TRACE, 0, 0, target);

OPT_STAT_INC(fitness_terminated_traces);

DPRINTF(2, "Fitness terminated: %s(%d) fitness=%d < exit_quality=%d\n",

_PyOpcode_OpName[opcode], oparg, ts->fitness, eq);

goto done;

}

// Snapshot remaining space so the later fitness charge reflects all buffer

// space this bytecode consumed, including reserved tail slots.

int32_t remaining_before = uop_buffer_remaining_space(trace);

// One for possible _DEOPT, one because _CHECK_VALIDITY itself might _DEOPT

trace->end -= 2;

const _PyOpcodeRecordSlotMap *record_slot_map = &_PyOpcode_RecordSlotMaps[opcode];

assert(opcode != ENTER_EXECUTOR && opcode != EXTENDED_ARG);

assert(!_PyErr_Occurred(tstate));

if (OPCODE_HAS_EXIT(opcode)) {

// Make space for side exit

trace->end--;

}

if (OPCODE_HAS_ERROR(opcode)) {

// Make space for error stub

trace->end--;

}

if (OPCODE_HAS_DEOPT(opcode)) {

// Make space for side exit

trace->end--;

}

// _GUARD_IP leads to an exit.

trace->end -= needs_guard_ip;

#if Py_DEBUG

const struct opcode_macro_expansion *expansion = &_PyOpcode_macro_expansion[opcode];

int space_needed = expansion->nuops + needs_guard_ip + 2 + (!OPCODE_HAS_NO_SAVE_IP(opcode));

assert(uop_buffer_remaining_space(trace) > space_needed);

#endif

ADD_TO_TRACE(_CHECK_VALIDITY, 0, 0, target);

if (!OPCODE_HAS_NO_SAVE_IP(opcode)) {

ADD_TO_TRACE(_SET_IP, 0, (uintptr_t)target_instr, target);

}

switch (opcode) {

case POP_JUMP_IF_NONE:

case POP_JUMP_IF_NOT_NONE:

case POP_JUMP_IF_FALSE:

case POP_JUMP_IF_TRUE:

{

_Py_CODEUNIT *computed_next_instr_without_modifiers = target_instr + 1 + _PyOpcode_Caches[_PyOpcode_Deopt[opcode]];

_Py_CODEUNIT *computed_next_instr = computed_next_instr_without_modifiers + (computed_next_instr_without_modifiers->op.code == NOT_TAKEN);

_Py_CODEUNIT *computed_jump_instr = computed_next_instr_without_modifiers + oparg;

assert(next_instr == computed_next_instr || next_instr == computed_jump_instr);

int jump_happened = target_instr[1].cache & 1;

assert(jump_happened ? (next_instr == computed_jump_instr) : (next_instr == computed_next_instr));

uint32_t uopcode = BRANCH_TO_GUARD[opcode - POP_JUMP_IF_FALSE][jump_happened];

ADD_TO_TRACE(uopcode, 0, 0, INSTR_IP(jump_happened ? computed_next_instr : computed_jump_instr, old_code));

int bp = compute_branch_penalty(target_instr[1].cache);

tracer->translator_state.fitness -= bp;

DPRINTF(3, " branch penalty: -%d (history=0x%04x, taken=%d) -> fitness=%d\n",

bp, target_instr[1].cache, jump_happened,

tracer->translator_state.fitness);

break;

}

case JUMP_BACKWARD_JIT:

// This is possible as the JIT might have re-activated after it was disabled

case JUMP_BACKWARD_NO_JIT:

case JUMP_BACKWARD:

ADD_TO_TRACE(_CHECK_PERIODIC, 0, 0, target);

break;

case JUMP_BACKWARD_NO_INTERRUPT:

break;

case RESUME:

case RESUME_CHECK:

case RESUME_CHECK_JIT:

/* Use a special tier 2 version of RESUME_CHECK to allow traces to

* start with RESUME_CHECK */

ADD_TO_TRACE(_TIER2_RESUME_CHECK, 0, 0, target);

break;

default:

{

const struct opcode_macro_expansion *expansion = &_PyOpcode_macro_expansion[opcode];

// Reserve space for nuops (+ _SET_IP + _EXIT_TRACE)

int nuops = expansion->nuops;

if (nuops == 0) {

DPRINTF(2, "Unsupported opcode %s\n", _PyOpcode_OpName[opcode]);

goto unsupported;

}

assert(nuops > 0);

uint32_t orig_oparg = oparg; // For OPARG_TOP/BOTTOM

uint32_t orig_target = target;

int record_idx = 0;

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

oparg = orig_oparg;

target = orig_target;

uint32_t uop = expansion->uops[i].uop;

uint64_t operand = 0;

// Add one to account for the actual opcode/oparg pair:

int offset = expansion->uops[i].offset + 1;

switch (expansion->uops[i].size) {

case OPARG_SIMPLE:

assert(opcode != _JUMP_BACKWARD_NO_INTERRUPT && opcode != JUMP_BACKWARD);

break;

case OPARG_CACHE_1:

operand = read_u16(&this_instr[offset].cache);

break;

case OPARG_CACHE_2:

operand = read_u32(&this_instr[offset].cache);

break;

case OPARG_CACHE_4:

operand = read_u64(&this_instr[offset].cache);

break;

case OPARG_TOP: // First half of super-instr

assert(orig_oparg <= 255);

oparg = orig_oparg >> 4;

break;

case OPARG_BOTTOM: // Second half of super-instr

assert(orig_oparg <= 255);

oparg = orig_oparg & 0xF;

break;

case OPARG_SAVE_RETURN_OFFSET: // op=_SAVE_RETURN_OFFSET; oparg=return_offset

oparg = offset;

assert(uop == _SAVE_RETURN_OFFSET);

break;

case OPARG_REPLACED:

uop = _PyUOp_Replacements[uop];

assert(uop != 0);

uint32_t next_inst = target + 1 + _PyOpcode_Caches[_PyOpcode_Deopt[opcode]];

if (uop == _TIER2_RESUME_CHECK) {

if (this_instr[-1].op.code == LOAD_SPECIAL) {

// Don't check eval breaker immediately after LOAD_SPECIAL

uop = _NOP;

}

else {

target = next_inst;

}

}

else {

int extended_arg = orig_oparg > 255;

uint32_t jump_target = next_inst + orig_oparg + extended_arg;

/* Jump must be to an "END" either END_FOR or END_SEND */

assert((

_Py_GetBaseCodeUnit(old_code, jump_target).op.code == END_FOR &&

_Py_GetBaseCodeUnit(old_code, jump_target+1).op.code == POP_ITER

)

||

_Py_GetBaseCodeUnit(old_code, jump_target).op.code == END_SEND

);

if (is_for_iter_test[uop]) {

target = jump_target + 1;

}

}

break;

case OPERAND1_1:

assert(uop_buffer_last(trace)->opcode == uop);

operand = read_u16(&this_instr[offset].cache);

uop_buffer_last(trace)->operand1 = operand;

continue;

case OPERAND1_2:

assert(uop_buffer_last(trace)->opcode == uop);

operand = read_u32(&this_instr[offset].cache);

uop_buffer_last(trace)->operand1 = operand;

continue;

case OPERAND1_4:

assert(uop_buffer_last(trace)->opcode == uop);

operand = read_u64(&this_instr[offset].cache);

uop_buffer_last(trace)->operand1 = operand;

continue;

default: