#ifdef _Py_TIER2
#include "Python.h"
#include "opcode.h"
#include "pycore_interp.h"
#include "pycore_backoff.h"
#include "pycore_bitutils.h" // _Py_popcount32()
#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_uop_ids.h"
#include "pycore_jit.h"
#include
#include
#include
#define NEED_OPCODE_METADATA
#include "pycore_uop_metadata.h" // Uop tables
#undef NEED_OPCODE_METADATA
#define MAX_EXECUTORS_SIZE 256
#ifdef Py_DEBUG
static int
base_opcode(PyCodeObject *code, int offset)
{
int opcode = _Py_GetBaseOpcode(code, offset);
if (opcode == ENTER_EXECUTOR) {
int oparg = _PyCode_CODE(code)[offset].op.arg;
_PyExecutorObject *ex = code->co_executors->executors[oparg];
return ex->vm_data.opcode;
}
return opcode;
}
#endif
static bool
has_space_for_executor(PyCodeObject *code, _Py_CODEUNIT *instr)
{
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 = 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;
}
static int
never_optimize(
_PyOptimizerObject* self,
_PyInterpreterFrame *frame,
_Py_CODEUNIT *instr,
_PyExecutorObject **exec,
int Py_UNUSED(stack_entries))
{
// This may be called if the optimizer is reset
return 0;
}
PyTypeObject _PyDefaultOptimizer_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
.tp_name = "noop_optimizer",
.tp_basicsize = sizeof(_PyOptimizerObject),
.tp_itemsize = 0,
.tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION,
};
static _PyOptimizerObject _PyOptimizer_Default = {
PyObject_HEAD_INIT(&_PyDefaultOptimizer_Type)
.optimize = never_optimize,
};
_PyOptimizerObject *
_Py_GetOptimizer(void)
{
PyInterpreterState *interp = _PyInterpreterState_GET();
if (interp->optimizer == &_PyOptimizer_Default) {
return NULL;
}
Py_INCREF(interp->optimizer);
return interp->optimizer;
}
static _PyExecutorObject *
make_executor_from_uops(_PyUOpInstruction *buffer, int length, const _PyBloomFilter *dependencies);
static int
init_cold_exit_executor(_PyExecutorObject *executor, int oparg);
/* It is impossible for the number of exits to reach 1/4 of the total length,
* as the number of exits cannot reach 1/3 of the number of non-exits, due to
* the presence of CHECK_VALIDITY checks and instructions to produce the values
* being checked in exits. */
#define COLD_EXIT_COUNT (UOP_MAX_TRACE_LENGTH/4)
static int cold_exits_initialized = 0;
static _PyExecutorObject COLD_EXITS[COLD_EXIT_COUNT] = { 0 };
static const _PyBloomFilter EMPTY_FILTER = { 0 };
_PyOptimizerObject *
_Py_SetOptimizer(PyInterpreterState *interp, _PyOptimizerObject *optimizer)
{
if (optimizer == NULL) {
optimizer = &_PyOptimizer_Default;
}
else if (cold_exits_initialized == 0) {
cold_exits_initialized = 1;
for (int i = 0; i < COLD_EXIT_COUNT; i++) {
if (init_cold_exit_executor(&COLD_EXITS[i], i)) {
return NULL;
}
}
}
_PyOptimizerObject *old = interp->optimizer;
if (old == NULL) {
old = &_PyOptimizer_Default;
}
Py_INCREF(optimizer);
interp->optimizer = optimizer;
return old;
}
int
_Py_SetTier2Optimizer(_PyOptimizerObject *optimizer)
{
PyInterpreterState *interp = _PyInterpreterState_GET();
_PyOptimizerObject *old = _Py_SetOptimizer(interp, optimizer);
Py_XDECREF(old);
return old == NULL ? -1 : 0;
}
/* Returns 1 if optimized, 0 if not optimized, and -1 for an error.
* If optimized, *executor_ptr contains a new reference to the executor
*/
int
_PyOptimizer_Optimize(
_PyInterpreterFrame *frame, _Py_CODEUNIT *start,
PyObject **stack_pointer, _PyExecutorObject **executor_ptr)
{
PyCodeObject *code = _PyFrame_GetCode(frame);
assert(PyCode_Check(code));
PyInterpreterState *interp = _PyInterpreterState_GET();
if (!has_space_for_executor(code, start)) {
return 0;
}
_PyOptimizerObject *opt = interp->optimizer;
int err = opt->optimize(opt, frame, start, executor_ptr, (int)(stack_pointer - _PyFrame_Stackbase(frame)));
if (err nuops > 0) {
// Reserve space for nuops (+ _SET_IP + _EXIT_TRACE)
int nuops = expansion->nuops;
RESERVE(nuops + 1); /* One extra for exit */
int16_t last_op = expansion->uops[nuops-1].uop;
if (last_op == _POP_FRAME || last_op == _RETURN_GENERATOR || last_op == _YIELD_VALUE) {
// Check for trace stack underflow now:
// We can't bail e.g. in the middle of
// LOAD_CONST + _POP_FRAME.
if (trace_stack_depth == 0) {
DPRINTF(2, "Trace stack underflow\n");
OPT_STAT_INC(trace_stack_underflow);
goto done;
}
}
uint32_t orig_oparg = oparg; // For OPARG_TOP/BOTTOM
for (int i = 0; i < nuops; i++) {
oparg = orig_oparg;
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_FULL:
assert(opcode != JUMP_BACKWARD_NO_INTERRUPT && opcode != JUMP_BACKWARD);
break;
case OPARG_CACHE_1:
operand = read_u16(&instr[offset].cache);
break;
case OPARG_CACHE_2:
operand = read_u32(&instr[offset].cache);
break;
case OPARG_CACHE_4:
operand = read_u64(&instr[offset].cache);
break;
case OPARG_TOP: // First half of super-instr
oparg = orig_oparg >> 4;
break;
case OPARG_BOTTOM: // Second half of super-instr
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);
#ifdef Py_DEBUG
{
uint32_t next_inst = target + 1 + INLINE_CACHE_ENTRIES_FOR_ITER + (oparg > 255);
uint32_t jump_target = next_inst + oparg;
assert(base_opcode(code, jump_target) == END_FOR ||
base_opcode(code, jump_target) == INSTRUMENTED_END_FOR);
assert(base_opcode(code, jump_target+1) == POP_TOP);
}
#endif
break;
default:
fprintf(stderr,
"opcode=%d, oparg=%d; nuops=%d, i=%d; size=%d, offset=%d\n",
opcode, oparg, nuops, i,
expansion->uops[i].size,
expansion->uops[i].offset);
Py_FatalError("garbled expansion");
}
if (uop == _POP_FRAME || uop == _RETURN_GENERATOR || uop == _YIELD_VALUE) {
TRACE_STACK_POP();
/* Set the operand to the function or code object returned to,
* to assist optimization passes. (See _PUSH_FRAME below.)
*/
if (func != NULL) {
operand = (uintptr_t)func;
}
else if (code != NULL) {
operand = (uintptr_t)code | 1;
}
else {
operand = 0;
}
ADD_TO_TRACE(uop, oparg, operand, target);
DPRINTF(2,
"Returning to %s (%s:%d) at byte offset %d\n",
PyUnicode_AsUTF8(code->co_qualname),
PyUnicode_AsUTF8(code->co_filename),
code->co_firstlineno,
2 * INSTR_IP(instr, code));
goto top;
}
if (uop == _PUSH_FRAME) {
assert(i + 1 == nuops);
int func_version_offset =
offsetof(_PyCallCache, func_version)/sizeof(_Py_CODEUNIT)
// Add one to account for the actual opcode/oparg pair:
+ 1;
uint32_t func_version = read_u32(&instr[func_version_offset].cache);
PyCodeObject *new_code = NULL;
PyFunctionObject *new_func =
_PyFunction_LookupByVersion(func_version, (PyObject **) &new_code);
DPRINTF(2, "Function: version=%#x; new_func=%p, new_code=%p\n",
(int)func_version, new_func, new_code);
if (new_code != NULL) {
if (new_code == code) {
// Recursive call, bail (we could be here forever).
DPRINTF(2, "Bailing on recursive call to %s (%s:%d)\n",
PyUnicode_AsUTF8(new_code->co_qualname),
PyUnicode_AsUTF8(new_code->co_filename),
new_code->co_firstlineno);
OPT_STAT_INC(recursive_call);
ADD_TO_TRACE(uop, oparg, 0, target);
ADD_TO_TRACE(_EXIT_TRACE, 0, 0, 0);
goto done;
}
if (new_code->co_version != func_version) {
// func.__code__ was updated.
// Perhaps it may happen again, so don't bother tracing.
// TODO: Reason about this -- is it better to bail or not?
DPRINTF(2, "Bailing because co_version != func_version\n");
ADD_TO_TRACE(uop, oparg, 0, target);
ADD_TO_TRACE(_EXIT_TRACE, 0, 0, 0);
goto done;
}
if (opcode == FOR_ITER_GEN) {
DPRINTF(2, "Bailing due to dynamic target\n");
ADD_TO_TRACE(uop, oparg, 0, target);
ADD_TO_TRACE(_DYNAMIC_EXIT, 0, 0, 0);
goto done;
}
// Increment IP to the return address
instr += _PyOpcode_Caches[_PyOpcode_Deopt[opcode]] + 1;
TRACE_STACK_PUSH();
_Py_BloomFilter_Add(dependencies, new_code);
/* Set the operand to the callee's function or code object,
* to assist optimization passes.
* We prefer setting it to the function (for remove_globals())
* but if that's not available but the code is available,
* use the code, setting the low bit so the optimizer knows.
*/
if (new_func != NULL) {
operand = (uintptr_t)new_func;
}
else if (new_code != NULL) {
operand = (uintptr_t)new_code | 1;
}
else {
operand = 0;
}
ADD_TO_TRACE(uop, oparg, operand, target);
code = new_code;
func = new_func;
instr = _PyCode_CODE(code);
DPRINTF(2,
"Continuing in %s (%s:%d) at byte offset %d\n",
PyUnicode_AsUTF8(code->co_qualname),
PyUnicode_AsUTF8(code->co_filename),
code->co_firstlineno,
2 * INSTR_IP(instr, code));
goto top;
}
DPRINTF(2, "Bail, new_code == NULL\n");
ADD_TO_TRACE(uop, oparg, 0, target);
ADD_TO_TRACE(_DYNAMIC_EXIT, 0, 0, 0);
goto done;
}
// All other instructions
ADD_TO_TRACE(uop, oparg, operand, target);
}
break;
}
DPRINTF(2, "Unsupported opcode %s\n", _PyOpcode_OpName[opcode]);
OPT_UNSUPPORTED_OPCODE(opcode);
goto done; // Break out of loop
} // End default
} // End switch (opcode)
instr++;
// Add cache size for opcode
instr += _PyOpcode_Caches[_PyOpcode_Deopt[opcode]];
} // End for (;;)
done:
while (trace_stack_depth > 0) {
TRACE_STACK_POP();
}
assert(code == initial_code);
// Skip short traces like _SET_IP, LOAD_FAST, _SET_IP, _EXIT_TRACE
if (progress_needed || trace_length < 5) {
OPT_STAT_INC(trace_too_short);
DPRINTF(2,
"No trace for %s (%s:%d) at byte offset %d (%s)\n",
PyUnicode_AsUTF8(code->co_qualname),
PyUnicode_AsUTF8(code->co_filename),
code->co_firstlineno,
2 * INSTR_IP(initial_instr, code),
progress_needed ? "no progress" : "too short");
return 0;
}
if (trace[trace_length-1].opcode != _JUMP_TO_TOP) {
ADD_TO_TRACE(_EXIT_TRACE, 0, 0, target);
}
DPRINTF(1,
"Created a proto-trace for %s (%s:%d) at byte offset %d -- length %d\n",
PyUnicode_AsUTF8(code->co_qualname),
PyUnicode_AsUTF8(code->co_filename),
code->co_firstlineno,
2 * INSTR_IP(initial_instr, code),
trace_length);
OPT_HIST(trace_length, trace_length_hist);
return trace_length;
}
#undef RESERVE
#undef RESERVE_RAW
#undef INSTR_IP
#undef ADD_TO_TRACE
#undef DPRINTF
#define UNSET_BIT(array, bit) (array[(bit)>>5] &= ~(15] |= (15] & (1oparg = 0;
inst->operand = 0;
inst->format = UOP_FORMAT_TARGET;
inst->target = target;
}
/* Convert implicit exits, errors and deopts
* into explicit ones. */
static int
prepare_for_execution(_PyUOpInstruction *buffer, int length)
{
int32_t current_jump = -1;
int32_t current_jump_target = -1;
int32_t current_error = -1;
int32_t current_error_target = -1;
int32_t current_popped = -1;
int32_t current_exit_op = -1;
/* Leaving in NOPs slows down the interpreter and messes up the stats */
_PyUOpInstruction *copy_to = &buffer[0];
for (int i = 0; i < length; i++) {
_PyUOpInstruction *inst = &buffer[i];
if (inst->opcode != _NOP) {
if (copy_to != inst) {
*copy_to = *inst;
}
copy_to++;
}
}
length = (int)(copy_to - buffer);
int next_spare = length;
for (int i = 0; i < length; i++) {
_PyUOpInstruction *inst = &buffer[i];
int opcode = inst->opcode;
int32_t target = (int32_t)uop_get_target(inst);
if (_PyUop_Flags[opcode] & (HAS_EXIT_FLAG | HAS_DEOPT_FLAG)) {
uint16_t exit_op = (_PyUop_Flags[opcode] & HAS_EXIT_FLAG) ?
_EXIT_TRACE : _DEOPT;
int32_t jump_target = target;
if (is_for_iter_test[opcode]) {
/* Target the POP_TOP immediately after the END_FOR,
* leaving only the iterator on the stack. */
int extended_arg = inst->oparg > 255;
int32_t next_inst = target + 1 + INLINE_CACHE_ENTRIES_FOR_ITER + extended_arg;
jump_target = next_inst + inst->oparg + 1;
}
if (jump_target != current_jump_target || current_exit_op != exit_op) {
make_exit(&buffer[next_spare], exit_op, jump_target);
current_exit_op = exit_op;
current_jump_target = jump_target;
current_jump = next_spare;
next_spare++;
}
buffer[i].jump_target = current_jump;
buffer[i].format = UOP_FORMAT_JUMP;
}
if (_PyUop_Flags[opcode] & HAS_ERROR_FLAG) {
int popped = (_PyUop_Flags[opcode] & HAS_ERROR_NO_POP_FLAG) ?
0 : _PyUop_num_popped(opcode, inst->oparg);
if (target != current_error_target || popped != current_popped) {
current_popped = popped;
current_error = next_spare;
current_error_target = target;
make_exit(&buffer[next_spare], _ERROR_POP_N, 0);
buffer[next_spare].oparg = popped;
buffer[next_spare].operand = target;
next_spare++;
}
buffer[i].error_target = current_error;
if (buffer[i].format == UOP_FORMAT_TARGET) {
buffer[i].format = UOP_FORMAT_JUMP;
buffer[i].jump_target = 0;
}
}
}
return next_spare;
}
/* Executor side exits */
static _PyExecutorObject *
allocate_executor(int exit_count, int length)
{
int size = exit_count*sizeof(_PyExitData) + length*sizeof(_PyUOpInstruction);
_PyExecutorObject *res = PyObject_GC_NewVar(_PyExecutorObject, &_PyUOpExecutor_Type, size);
if (res == NULL) {
return NULL;
}
res->trace = (_PyUOpInstruction *)(res->exits + exit_count);
res->code_size = length;
res->exit_count = exit_count;
return res;
}
#ifdef Py_DEBUG
#define CHECK(PRED) \
if (!(PRED)) { \
printf(#PRED " at %d\n", i); \
assert(0); \
}
static int
target_unused(int opcode)
{
return (_PyUop_Flags[opcode] & (HAS_ERROR_FLAG | HAS_EXIT_FLAG | HAS_DEOPT_FLAG)) == 0;
}
static void
sanity_check(_PyExecutorObject *executor)
{
for (uint32_t i = 0; i < executor->exit_count; i++) {
_PyExitData *exit = &executor->exits[i];
CHECK(exit->target < (1 trace[0].opcode == _START_EXECUTOR || executor->trace[0].opcode == _COLD_EXIT);
for (; i < executor->code_size; i++) {
const _PyUOpInstruction *inst = &executor->trace[i];
uint16_t opcode = inst->opcode;
CHECK(opcode format) {
case UOP_FORMAT_TARGET:
CHECK(target_unused(opcode));
break;
case UOP_FORMAT_EXIT:
CHECK(opcode == _EXIT_TRACE);
CHECK(inst->exit_index < executor->exit_count);
break;
case UOP_FORMAT_JUMP:
CHECK(inst->jump_target < executor->code_size);
break;
case UOP_FORMAT_UNUSED:
CHECK(0);
break;
}
if (_PyUop_Flags[opcode] & HAS_ERROR_FLAG) {
CHECK(inst->format == UOP_FORMAT_JUMP);
CHECK(inst->error_target < executor->code_size);
}
if (opcode == _JUMP_TO_TOP || opcode == _EXIT_TRACE || opcode == _COLD_EXIT) {
ended = true;
i++;
break;
}
}
CHECK(ended);
for (; i < executor->code_size; i++) {
const _PyUOpInstruction *inst = &executor->trace[i];
uint16_t opcode = inst->opcode;
CHECK(
opcode == _DEOPT ||
opcode == _EXIT_TRACE ||
opcode == _ERROR_POP_N);
if (opcode == _EXIT_TRACE) {
CHECK(inst->format == UOP_FORMAT_EXIT);
}
}
}
#undef CHECK
#endif
/* Makes an executor from a buffer of uops.
* Account for the buffer having gaps and NOPs by computing a "used"
* bit vector and only copying the used uops. Here "used" means reachable
* and not a NOP.
*/
static _PyExecutorObject *
make_executor_from_uops(_PyUOpInstruction *buffer, int length, const _PyBloomFilter *dependencies)
{
int exit_count = count_exits(buffer, length);
_PyExecutorObject *executor = allocate_executor(exit_count, length);
if (executor == NULL) {
return NULL;
}
/* Initialize exits */
assert(exit_count < COLD_EXIT_COUNT);
for (int i = 0; i < exit_count; i++) {
executor->exits[i].executor = &COLD_EXITS[i];
executor->exits[i].temperature = initial_temperature_backoff_counter();
}
int next_exit = exit_count-1;
_PyUOpInstruction *dest = (_PyUOpInstruction *)&executor->trace[length];
assert(buffer[0].opcode == _START_EXECUTOR);
buffer[0].operand = (uint64_t)executor;
for (int i = length-1; i >= 0; i--) {
int opcode = buffer[i].opcode;
dest--;
*dest = buffer[i];
assert(opcode != _POP_JUMP_IF_FALSE && opcode != _POP_JUMP_IF_TRUE);
if (opcode == _EXIT_TRACE) {
executor->exits[next_exit].target = buffer[i].target;
dest->exit_index = next_exit;
dest->format = UOP_FORMAT_EXIT;
next_exit--;
}
if (opcode == _DYNAMIC_EXIT) {
executor->exits[next_exit].target = 0;
dest->oparg = next_exit;
next_exit--;
}
}
assert(next_exit == -1);
assert(dest == executor->trace);
assert(dest->opcode == _START_EXECUTOR);
_Py_ExecutorInit(executor, dependencies);
#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
}
if (lltrace >= 2) {
printf("Optimized trace (length %d):\n", length);
for (int i = 0; i < length; i++) {
printf("%4d OPTIMIZED: ", i);
_PyUOpPrint(&executor->trace[i]);
printf("\n");
}
}
sanity_check(executor);
#endif
#ifdef _Py_JIT
executor->jit_code = NULL;
executor->jit_side_entry = NULL;
executor->jit_size = 0;
if (_PyJIT_Compile(executor, executor->trace, length)) {
Py_DECREF(executor);
return NULL;
}
#endif
_PyObject_GC_TRACK(executor);
return executor;
}
static int
init_cold_exit_executor(_PyExecutorObject *executor, int oparg)
{
_Py_SetImmortalUntracked((PyObject *)executor);
Py_SET_TYPE(executor, &_PyUOpExecutor_Type);
executor->trace = (_PyUOpInstruction *)executor->exits;
executor->code_size = 1;
executor->exit_count = 0;
_PyUOpInstruction *inst = (_PyUOpInstruction *)&executor->trace[0];
inst->opcode = _COLD_EXIT;
inst->oparg = oparg;
executor->vm_data.valid = true;
executor->vm_data.linked = false;
for (int i = 0; i < BLOOM_FILTER_WORDS; i++) {
assert(executor->vm_data.bloom.bits[i] == 0);
}
#ifdef Py_DEBUG
sanity_check(executor);
#endif
#ifdef _Py_JIT
executor->jit_code = NULL;
executor->jit_side_entry = NULL;
executor->jit_size = 0;
if (_PyJIT_Compile(executor, executor->trace, 1)) {
return -1;
}
#endif
return 0;
}
#ifdef Py_STATS
/* Returns the effective trace length.
* Ignores NOPs and trailing exit and error handling.*/
int effective_trace_length(_PyUOpInstruction *buffer, int length)
{
int nop_count = 0;
for (int i = 0; i < length; i++) {
int opcode = buffer[i].opcode;
if (opcode == _NOP) {
nop_count++;
}
if (opcode == _EXIT_TRACE ||
opcode == _JUMP_TO_TOP ||
opcode == _COLD_EXIT) {
return i+1-nop_count;
}
}
Py_FatalError("No terminating instruction");
Py_UNREACHABLE();
}
#endif
static int
uop_optimize(
_PyOptimizerObject *self,
_PyInterpreterFrame *frame,
_Py_CODEUNIT *instr,
_PyExecutorObject **exec_ptr,
int curr_stackentries)
{
_PyBloomFilter dependencies;
_Py_BloomFilter_Init(&dependencies);
_PyUOpInstruction buffer[UOP_MAX_TRACE_LENGTH];
OPT_STAT_INC(attempts);
int length = translate_bytecode_to_trace(frame, instr, buffer, UOP_MAX_TRACE_LENGTH, &dependencies);
if (length '0') {
length = _Py_uop_analyze_and_optimize(frame, buffer,
length,
curr_stackentries, &dependencies);
if (length = 1);
/* Fix up */
for (int pc = 0; pc < length; pc++) {
int opcode = buffer[pc].opcode;
int oparg = buffer[pc].oparg;
if (_PyUop_Flags[opcode] & HAS_OPARG_AND_1_FLAG) {
buffer[pc].opcode = opcode + 1 + (oparg & 1);
}
else if (oparg < _PyUop_Replication[opcode]) {
buffer[pc].opcode = opcode + oparg + 1;
}
else if (opcode == _JUMP_TO_TOP || opcode == _EXIT_TRACE) {
break;
}
assert(_PyOpcode_uop_name[buffer[pc].opcode]);
assert(strncmp(_PyOpcode_uop_name[buffer[pc].opcode], _PyOpcode_uop_name[opcode], strlen(_PyOpcode_uop_name[opcode])) == 0);
}
OPT_HIST(effective_trace_length(buffer, length), optimized_trace_length_hist);
length = prepare_for_execution(buffer, length);
assert(length trace[1].operand;
Py_DECREF(opt);
uop_dealloc(self);
}
PyTypeObject _PyCounterExecutor_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
.tp_name = "counting_executor",
.tp_basicsize = offsetof(_PyExecutorObject, exits),
.tp_itemsize = 1,
.tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION | Py_TPFLAGS_HAVE_GC,
.tp_dealloc = (destructor)counter_dealloc,
.tp_methods = executor_methods,
.tp_traverse = executor_traverse,
.tp_clear = (inquiry)executor_clear,
};
static int
counter_optimize(
_PyOptimizerObject* self,
_PyInterpreterFrame *frame,
_Py_CODEUNIT *instr,
_PyExecutorObject **exec_ptr,
int Py_UNUSED(curr_stackentries)
)
{
PyCodeObject *code = _PyFrame_GetCode(frame);
int oparg = instr->op.arg;
while (instr->op.code == EXTENDED_ARG) {
instr++;
oparg = (oparg op.arg;
}
if (instr->op.code != JUMP_BACKWARD) {
/* Counter optimizer can only handle backward edges */
return 0;
}
_Py_CODEUNIT *target = instr + 1 + _PyOpcode_Caches[JUMP_BACKWARD] - oparg;
_PyUOpInstruction buffer[4] = {
{ .opcode = _START_EXECUTOR, .jump_target = 3, .format=UOP_FORMAT_JUMP },
{ .opcode = _LOAD_CONST_INLINE_BORROW, .operand = (uintptr_t)self },
{ .opcode = _INTERNAL_INCREMENT_OPT_COUNTER },
{ .opcode = _EXIT_TRACE, .target = (uint32_t)(target - _PyCode_CODE(code)), .format=UOP_FORMAT_TARGET }
};
_PyExecutorObject *executor = make_executor_from_uops(buffer, 4, &EMPTY_FILTER);
if (executor == NULL) {
return -1;
}
Py_INCREF(self);
Py_SET_TYPE(executor, &_PyCounterExecutor_Type);
*exec_ptr = executor;
return 1;
}
static PyObject *
counter_get_counter(PyObject *self, PyObject *args)
{
return PyLong_FromLongLong(((_PyCounterOptimizerObject *)self)->count);
}
static PyMethodDef counter_optimizer_methods[] = {
{ "get_count", counter_get_counter, METH_NOARGS, NULL },
{ NULL, NULL },
};
PyTypeObject _PyCounterOptimizer_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
.tp_name = "Counter optimizer",
.tp_basicsize = sizeof(_PyCounterOptimizerObject),
.tp_itemsize = 0,
.tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION,
.tp_methods = counter_optimizer_methods,
.tp_dealloc = (destructor)PyObject_Del,
};
PyObject *
_PyOptimizer_NewCounter(void)
{
_PyCounterOptimizerObject *opt = (_PyCounterOptimizerObject *)_PyObject_New(&_PyCounterOptimizer_Type);
if (opt == NULL) {
return NULL;
}
opt->base.optimize = counter_optimize;
opt->count = 0;
return (PyObject *)opt;
}
/*****************************************
* Executor management
****************************************/
/* We use a bloomfilter with k = 6, m = 256
* The choice of k and the following constants
* could do with a more rigourous analysis,
* but here is a simple analysis:
*
* We want to keep the false positive rate low.
* For n = 5 (a trace depends on 5 objects),
* we expect 30 bits set, giving a false positive
* rate of (30/256)**6 == 2.5e-6 which is plenty
* good enough.
*
* However with n = 10 we expect 60 bits set (worst case),
* giving a false positive of (60/256)**6 == 0.0001
*
* We choose k = 6, rather than a higher number as
* it means the false positive rate grows slower for high n.
*
* n = 5, k = 6 => fp = 2.6e-6
* n = 5, k = 8 => fp = 3.5e-7
* n = 10, k = 6 => fp = 1.6e-4
* n = 10, k = 8 => fp = 0.9e-4
* n = 15, k = 6 => fp = 0.18%
* n = 15, k = 8 => fp = 0.23%
* n = 20, k = 6 => fp = 1.1%
* n = 20, k = 8 => fp = 2.3%
*
* The above analysis assumes perfect hash functions,
* but those don't exist, so the real false positive
* rates may be worse.
*/
#define K 6
#define SEED 20221211
/* TO DO -- Use more modern hash functions with better distribution of bits */
static uint64_t
address_to_hash(void *ptr) {
assert(ptr != NULL);
uint64_t uhash = SEED;
uintptr_t addr = (uintptr_t)ptr;
for (int i = 0; i < SIZEOF_VOID_P; i++) {
uhash ^= addr & 255;
uhash *= (uint64_t)PyHASH_MULTIPLIER;
addr >>= 8;
}
return uhash;
}
void
_Py_BloomFilter_Init(_PyBloomFilter *bloom)
{
for (int i = 0; i < BLOOM_FILTER_WORDS; i++) {
bloom->bits[i] = 0;
}
}
/* We want K hash functions that each set 1 bit.
* A hash function that sets 1 bit in M bits can be trivially
* derived from a log2(M) bit hash function.
* So we extract 8 (log2(256)) bits at a time from
* the 64bit hash. */
void
_Py_BloomFilter_Add(_PyBloomFilter *bloom, void *ptr)
{
uint64_t hash = address_to_hash(ptr);
assert(K bits[bits >> 5] |= (1 >= 8;
}
}
static bool
bloom_filter_may_contain(_PyBloomFilter *bloom, _PyBloomFilter *hashes)
{
for (int i = 0; i < BLOOM_FILTER_WORDS; i++) {
if ((bloom->bits[i] & hashes->bits[i]) != hashes->bits[i]) {
return false;
}
}
return true;
}
static void
link_executor(_PyExecutorObject *executor)
{
PyInterpreterState *interp = _PyInterpreterState_GET();
_PyExecutorLinkListNode *links = &executor->vm_data.links;
_PyExecutorObject *head = interp->executor_list_head;
if (head == NULL) {
interp->executor_list_head = executor;
links->previous = NULL;
links->next = NULL;
}
else {
assert(head->vm_data.links.previous == NULL);
links->previous = NULL;
links->next = head;
head->vm_data.links.previous = executor;
interp->executor_list_head = executor;
}
executor->vm_data.linked = true;
/* executor_list_head must be first in list */
assert(interp->executor_list_head->vm_data.links.previous == NULL);
}
static void
unlink_executor(_PyExecutorObject *executor)
{
if (!executor->vm_data.linked) {
return;
}
_PyExecutorLinkListNode *links = &executor->vm_data.links;
assert(executor->vm_data.valid);
_PyExecutorObject *next = links->next;
_PyExecutorObject *prev = links->previous;
if (next != NULL) {
next->vm_data.links.previous = prev;
}
if (prev != NULL) {
prev->vm_data.links.next = next;
}
else {
// prev == NULL implies that executor is the list head
PyInterpreterState *interp = PyInterpreterState_Get();
assert(interp->executor_list_head == executor);
interp->executor_list_head = next;
}
executor->vm_data.linked = false;
}
/* This must be called by optimizers before using the executor */
void
_Py_ExecutorInit(_PyExecutorObject *executor, const _PyBloomFilter *dependency_set)
{
executor->vm_data.valid = true;
for (int i = 0; i < BLOOM_FILTER_WORDS; i++) {
executor->vm_data.bloom.bits[i] = dependency_set->bits[i];
}
link_executor(executor);
}
/* Detaches the executor from the code object (if any) that
* holds a reference to it */
void
_Py_ExecutorDetach(_PyExecutorObject *executor)
{
PyCodeObject *code = executor->vm_data.code;
if (code == NULL) {
return;
}
_Py_CODEUNIT *instruction = &_PyCode_CODE(code)[executor->vm_data.index];
assert(instruction->op.code == ENTER_EXECUTOR);
int index = instruction->op.arg;
assert(code->co_executors->executors[index] == executor);
instruction->op.code = executor->vm_data.opcode;
instruction->op.arg = executor->vm_data.oparg;
executor->vm_data.code = NULL;
code->co_executors->executors[index] = NULL;
Py_DECREF(executor);
}
static int
executor_clear(_PyExecutorObject *executor)
{
if (!executor->vm_data.valid) {
return 0;
}
assert(executor->vm_data.valid == 1);
unlink_executor(executor);
executor->vm_data.valid = 0;
/* It is possible for an executor to form a reference
* cycle with itself, so decref'ing a side exit could
* free the executor unless we hold a strong reference to it
*/
Py_INCREF(executor);
for (uint32_t i = 0; i < executor->exit_count; i++) {
const _PyExecutorObject *cold = &COLD_EXITS[i];
const _PyExecutorObject *side = executor->exits[i].executor;
executor->exits[i].temperature = initial_unreachable_backoff_counter();
if (side != cold) {
executor->exits[i].executor = cold;
Py_DECREF(side);
}
}
_Py_ExecutorDetach(executor);
Py_DECREF(executor);
return 0;
}
void
_Py_Executor_DependsOn(_PyExecutorObject *executor, void *obj)
{
assert(executor->vm_data.valid);
_Py_BloomFilter_Add(&executor->vm_data.bloom, obj);
}
/* Invalidate all executors that depend on `obj`
* May cause other executors to be invalidated as well
*/
void
_Py_Executors_InvalidateDependency(PyInterpreterState *interp, void *obj, int is_invalidation)
{
_PyBloomFilter obj_filter;
_Py_BloomFilter_Init(&obj_filter);
_Py_BloomFilter_Add(&obj_filter, obj);
/* Walk the list of executors */
/* TO DO -- Use a tree to avoid traversing as many objects */
bool no_memory = false;
PyObject *invalidate = PyList_New(0);
if (invalidate == NULL) {
PyErr_Clear();
no_memory = true;
}
/* Clearing an executor can deallocate others, so we need to make a list of
* executors to invalidate first */
for (_PyExecutorObject *exec = interp->executor_list_head; exec != NULL;) {
assert(exec->vm_data.valid);
_PyExecutorObject *next = exec->vm_data.links.next;
if (bloom_filter_may_contain(&exec->vm_data.bloom, &obj_filter)) {
unlink_executor(exec);
if (no_memory) {
exec->vm_data.valid = 0;
} else {
if (PyList_Append(invalidate, (PyObject *)exec) < 0) {
PyErr_Clear();
no_memory = true;
exec->vm_data.valid = 0;
}
}
if (is_invalidation) {
OPT_STAT_INC(executors_invalidated);
}
}
exec = next;
}
if (invalidate != NULL) {
for (Py_ssize_t i = 0; i < PyList_GET_SIZE(invalidate); i++) {
_PyExecutorObject *exec = (_PyExecutorObject *)PyList_GET_ITEM(invalidate, i);
executor_clear(exec);
}
Py_DECREF(invalidate);
}
return;
}
/* Invalidate all executors */
void
_Py_Executors_InvalidateAll(PyInterpreterState *interp, int is_invalidation)
{
while (interp->executor_list_head) {
_PyExecutorObject *executor = interp->executor_list_head;
assert(executor->vm_data.valid == 1 && executor->vm_data.linked == 1);
if (executor->vm_data.code) {
// Clear the entire code object so its co_executors array be freed:
_PyCode_Clear_Executors(executor->vm_data.code);
}
else {
executor_clear(executor);
}
if (is_invalidation) {
OPT_STAT_INC(executors_invalidated);
}
}
}
#endif /* _Py_TIER2 */