Viewing: raw.githubusercontent.com

[ Web Proxy ]

Viewing: https://raw.githubusercontent.com/python/cpython/3.14/Python/optimizer.c

#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_code.h" // _Py_GetBaseCodeUnit #include "pycore_function.h" // _PyFunction_LookupByVersion() #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 #include #include #define NEED_OPCODE_METADATA #include "pycore_uop_metadata.h" // Uop tables #undef NEED_OPCODE_METADATA #define MAX_EXECUTORS_SIZE 256 #define _PyExecutorObject_CAST(op) ((_PyExecutorObject *)(op)) 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 _PyExecutorObject * make_executor_from_uops(_PyUOpInstruction *buffer, int length, const _PyBloomFilter *dependencies); static int uop_optimize(_PyInterpreterFrame *frame, _Py_CODEUNIT *instr, _PyExecutorObject **exec_ptr, int curr_stackentries, 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, _Py_CODEUNIT *start, _PyExecutorObject **executor_ptr, int chain_depth) { _PyStackRef *stack_pointer = frame->stackpointer; 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; } // 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: chain_depth %= MAX_CHAIN_DEPTH; bool progress_needed = chain_depth == 0; PyCodeObject *code = _PyFrame_GetCode(frame); assert(PyCode_Check(code)); if (progress_needed && !has_space_for_executor(code, start)) { return 0; } int err = uop_optimize(frame, start, executor_ptr, (int)(stack_pointer - _PyFrame_Stackbase(frame)), progress_needed); if (err 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(&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(_Py_GetBaseCodeUnit(code, jump_target).op.code == END_FOR); assert(_Py_GetBaseCodeUnit(code, jump_target+1).op.code == POP_ITER); } #endif break; case OPERAND1_1: assert(trace[trace_length-1].opcode == uop); operand = read_u16(&instr[offset].cache); trace[trace_length-1].operand1 = operand; continue; case OPERAND1_2: assert(trace[trace_length-1].opcode == uop); operand = read_u32(&instr[offset].cache); trace[trace_length-1].operand1 = operand; continue; case OPERAND1_4: assert(trace[trace_length-1].opcode == uop); operand = read_u64(&instr[offset].cache); trace[trace_length-1].operand1 = operand; continue; 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 == _RETURN_VALUE || 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); if (opcode == FOR_ITER_GEN || opcode == LOAD_ATTR_PROPERTY || opcode == BINARY_OP_SUBSCR_GETITEM || opcode == SEND_GEN) { DPRINTF(2, "Bailing due to dynamic target\n"); OPT_STAT_INC(unknown_callee); return 0; } assert(_PyOpcode_Deopt[opcode] == CALL || _PyOpcode_Deopt[opcode] == CALL_KW); 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; } // 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"); OPT_STAT_INC(unknown_callee); return 0; } if (uop == _BINARY_OP_INPLACE_ADD_UNICODE) { assert(i + 1 == nuops); _Py_CODEUNIT *next_instr = instr + 1 + _PyOpcode_Caches[_PyOpcode_Deopt[opcode]]; assert(next_instr->op.code == STORE_FAST); operand = next_instr->op.arg; // Skip the STORE_FAST: instr++; } // 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]]; if (opcode == CALL_LIST_APPEND) { assert(instr->op.code == POP_TOP); instr++; } top: // Jump here after _PUSH_FRAME or likely branches. first = false; } // End for (;;) done: while (trace_stack_depth > 0) { TRACE_STACK_POP(); } assert(code == initial_code); // Skip short traces where we can't even translate a single instruction: if (first) { OPT_STAT_INC(trace_too_short); DPRINTF(2, "No trace for %s (%s:%d) at byte offset %d (no progress)\n", PyUnicode_AsUTF8(code->co_qualname), PyUnicode_AsUTF8(code->co_filename), code->co_firstlineno, 2 * INSTR_IP(initial_instr, code)); return 0; } if (!is_terminator(&trace[trace_length-1])) { /* Allow space for _EXIT_TRACE */ max_length += 2; 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->operand0 = 0; inst->format = UOP_FORMAT_TARGET; inst->target = target; #ifdef Py_STATS inst->execution_count = 0; #endif } /* 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].operand0 = 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; } } if (opcode == _JUMP_TO_TOP) { assert(buffer[0].opcode == _START_EXECUTOR); buffer[i].format = UOP_FORMAT_JUMP; buffer[i].jump_target = 1; } } 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); 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_JUMP: CHECK(inst->jump_target < executor->code_size); break; } if (_PyUop_Flags[opcode] & HAS_ERROR_FLAG) { CHECK(inst->format == UOP_FORMAT_JUMP); CHECK(inst->error_target < executor->code_size); } if (is_terminator(inst)) { 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); } } #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 */ for (int i = 0; i < exit_count; i++) { executor->exits[i].executor = NULL; 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].operand0 = (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) { _PyExitData *exit = &executor->exits[next_exit]; exit->target = buffer[i].target; dest->operand0 = (uint64_t)exit; next_exit--; } } assert(next_exit == -1); assert(dest == executor->trace); assert(dest->opcode == _START_EXECUTOR); // Note: we MUST track it here before any Py_DECREF(executor) or // linking of executor. Otherwise, the GC tries to untrack a // still untracked object during dealloc. _PyObject_GC_TRACK(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; // This is initialized to true so we can prevent the executor // from being immediately detected as cold and invalidated. executor->vm_data.warm = true; if (_PyJIT_Compile(executor, executor->trace, length)) { Py_DECREF(executor); return NULL; } #endif return executor; } #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 (is_terminator(&buffer[i])) { return i+1-nop_count; } } Py_FatalError("No terminating instruction"); Py_UNREACHABLE(); } #endif static int uop_optimize( _PyInterpreterFrame *frame, _Py_CODEUNIT *instr, _PyExecutorObject **exec_ptr, int curr_stackentries, bool progress_needed) { _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, progress_needed); 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 (oparg < _PyUop_Replication[opcode]) { buffer[pc].opcode = opcode + oparg + 1; assert(strncmp(_PyOpcode_uop_name[buffer[pc].opcode], _PyOpcode_uop_name[opcode], strlen(_PyOpcode_uop_name[opcode])) == 0); } else if (is_terminator(&buffer[pc])) { break; } assert(_PyOpcode_uop_name[buffer[pc].opcode]); } OPT_HIST(effective_trace_length(buffer, length), optimized_trace_length_hist); length = prepare_for_execution(buffer, length); assert(length 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 < _Py_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 < _Py_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 < _Py_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(PyObject *op) { _PyExecutorObject *executor = _PyExecutorObject_CAST(op); 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++) { executor->exits[i].temperature = initial_unreachable_backoff_counter(); Py_CLEAR(executor->exits[i].executor); } _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 */ PyObject *invalidate = PyList_New(0); if (invalidate == NULL) { goto error; } /* 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) && PyList_Append(invalidate, (PyObject *)exec)) { goto error; } exec = next; } for (Py_ssize_t i = 0; i < PyList_GET_SIZE(invalidate); i++) { PyObject *exec = PyList_GET_ITEM(invalidate, i); executor_clear(exec); if (is_invalidation) { OPT_STAT_INC(executors_invalidated); } } Py_DECREF(invalidate); return; error: PyErr_Clear(); Py_XDECREF(invalidate); // If we're truly out of memory, wiping out everything is a fine fallback: _Py_Executors_InvalidateAll(interp, is_invalidation); } /* 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((PyObject *)executor); } if (is_invalidation) { OPT_STAT_INC(executors_invalidated); } } } void _Py_Executors_InvalidateCold(PyInterpreterState *interp) { /* Walk the list of executors */ /* TO DO -- Use a tree to avoid traversing as many objects */ PyObject *invalidate = PyList_New(0); if (invalidate == NULL) { goto error; } /* 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 (!exec->vm_data.warm && PyList_Append(invalidate, (PyObject *)exec) < 0) { goto error; } else { exec->vm_data.warm = false; } exec = next; } for (Py_ssize_t i = 0; i < PyList_GET_SIZE(invalidate); i++) { PyObject *exec = PyList_GET_ITEM(invalidate, i); executor_clear(exec); } Py_DECREF(invalidate); return; error: PyErr_Clear(); Py_XDECREF(invalidate); // If we're truly out of memory, wiping out everything is a fine fallback _Py_Executors_InvalidateAll(interp, 0); } static void write_str(PyObject *str, FILE *out) { // Encode the Unicode object to the specified encoding PyObject *encoded_obj = PyUnicode_AsEncodedString(str, "utf8", "strict"); if (encoded_obj == NULL) { PyErr_Clear(); return; } const char *encoded_str = PyBytes_AsString(encoded_obj); Py_ssize_t encoded_size = PyBytes_Size(encoded_obj); fwrite(encoded_str, 1, encoded_size, out); Py_DECREF(encoded_obj); } static int find_line_number(PyCodeObject *code, _PyExecutorObject *executor) { int code_len = (int)Py_SIZE(code); for (int i = 0; i < code_len; i++) { _Py_CODEUNIT *instr = &_PyCode_CODE(code)[i]; int opcode = instr->op.code; if (opcode == ENTER_EXECUTOR) { _PyExecutorObject *exec = code->co_executors->executors[instr->op.arg]; if (exec == executor) { return PyCode_Addr2Line(code, i*2); } } i += _PyOpcode_Caches[_Py_GetBaseCodeUnit(code, i).op.code]; } return -1; } /* Writes the node and outgoing edges for a single tracelet in graphviz format. * Each tracelet is presented as a table of the uops it contains. * If Py_STATS is enabled, execution counts are included. * * https://graphviz.readthedocs.io/en/stable/manual.html * https://graphviz.org/gallery/ */ static void executor_to_gv(_PyExecutorObject *executor, FILE *out) { PyCodeObject *code = executor->vm_data.code; fprintf(out, "executor_%p [\n", executor); fprintf(out, " shape = none\n"); /* Write the HTML table for the uops */ fprintf(out, " label = \n"); fprintf(out, "]\n\n"); /* Write all the outgoing edges */ for (uint32_t i = 0; i < executor->code_size; i++) { _PyUOpInstruction const *inst = &executor->trace[i]; uint16_t flags = _PyUop_Flags[inst->opcode]; _PyExitData *exit = NULL; if (inst->opcode == _EXIT_TRACE) { exit = (_PyExitData *)inst->operand0; } else if (flags & HAS_EXIT_FLAG) { assert(inst->format == UOP_FORMAT_JUMP); _PyUOpInstruction const *exit_inst = &executor->trace[inst->jump_target]; assert(exit_inst->opcode == _EXIT_TRACE); exit = (_PyExitData *)exit_inst->operand0; } if (exit != NULL && exit->executor != NULL) { fprintf(out, "executor_%p:i%d -> executor_%p:start\n", executor, i, exit->executor); } if (inst->opcode == _EXIT_TRACE || inst->opcode == _JUMP_TO_TOP) { break; } } } /* Write the graph of all the live tracelets in graphviz format. */ int _PyDumpExecutors(FILE *out) { fprintf(out, "digraph ideal {\n\n"); fprintf(out, " rankdir = \"LR\"\n\n"); PyInterpreterState *interp = PyInterpreterState_Get(); for (_PyExecutorObject *exec = interp->executor_list_head; exec != NULL;) { executor_to_gv(exec, out); exec = exec->vm_data.links.next; } fprintf(out, "}\n\n"); return 0; } #else int _PyDumpExecutors(FILE *out) { PyErr_SetString(PyExc_NotImplementedError, "No JIT available"); return -1; } #endif /* _Py_TIER2 */

Web Proxy Viewer | New URL | Original Page