Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

gh-107557: Setup abstract interpretation#107847

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
Fidget-Spinner merged 54 commits intopython:mainfromFidget-Spinner:partition_algo
Aug 15, 2023
Merged
Show file tree
Hide file tree
Changes from1 commit
Commits
Show all changes
54 commits
Select commitHold shift + click to select a range
d20fbb8
gh-107557: Tier 2 abstract interpreter barebones
Fidget-SpinnerAug 2, 2023
2aeea51
📜🤖 Added by blurb_it.
blurb-it[bot]Aug 2, 2023
1a728ab
Copy Guido's input and output code, and fix build
Fidget-SpinnerAug 2, 2023
17fccbc
fix separator
Fidget-SpinnerAug 2, 2023
a1da69d
credit Jules
Fidget-SpinnerAug 2, 2023
b458e17
add jules to co-authors
Fidget-SpinnerAug 2, 2023
f81f888
add pycore_optimizer.h to headers in makefile
Fidget-SpinnerAug 2, 2023
0020320
fix: remove whitespace
Fidget-SpinnerAug 2, 2023
1f93072
fix make smelly
Fidget-SpinnerAug 2, 2023
dac63e3
fix: build
Fidget-SpinnerAug 2, 2023
e62e015
fix wrong symbol
Fidget-SpinnerAug 2, 2023
a7f654c
ignore static globals check for abstract interpreter
Fidget-SpinnerAug 2, 2023
f4040b8
Merge remote-tracking branch 'upstream/main' into abstract_interpreter
Fidget-SpinnerAug 4, 2023
ec58145
merge Guido's changes
Fidget-SpinnerAug 4, 2023
4292767
remove unused stuff
Fidget-SpinnerAug 4, 2023
fdcca90
Turn on the abstract interpreter
Fidget-SpinnerAug 4, 2023
5110fb9
Merge remote-tracking branch 'upstream/main' into abstract_interpreter
Fidget-SpinnerAug 5, 2023
9f443a2
Merge remote-tracking branch 'origin/abstract_interpreter' into parti…
Fidget-SpinnerAug 5, 2023
7632ed1
(leaky) data structures for constant propagation
Fidget-SpinnerAug 5, 2023
0d0c4c4
(with cycles) try to fix the type prop
Fidget-SpinnerAug 6, 2023
4c8953e
fix: cycles
Fidget-SpinnerAug 6, 2023
3bd36fa
cleanup
Fidget-SpinnerAug 6, 2023
229097f
Fix+Refactor: Handling of root nodes in special-cased type prop (#40)
JuliaPooAug 7, 2023
ca0fab7
partially partially evaluate
Fidget-SpinnerAug 8, 2023
68c684f
rename vars
Fidget-SpinnerAug 8, 2023
46c5777
fixx off by one
Fidget-SpinnerAug 8, 2023
b839ee4
partial eval working for real this time
Fidget-SpinnerAug 9, 2023
6ecf3d2
Fix: Inconsistent `AbstractInterpContext` used in `PARTITIONNODE_OVER…
JuliaPooAug 9, 2023
b6eeb25
fix test, refactor, bugfix
Fidget-SpinnerAug 9, 2023
d5cceb9
re-compute jump offsets and targets
Fidget-SpinnerAug 10, 2023
8c0d65f
Fix+Refactor: Extra EXIT_TRACE emitted (#42)
JuliaPooAug 10, 2023
95db909
fix: overallocate buffer and virtual/real stack offset calculation
Fidget-SpinnerAug 10, 2023
1e05ef8
more bugfix
Fidget-SpinnerAug 10, 2023
d7d8b52
Merge remote-tracking branch 'upstream/main' into partition_algo
Fidget-SpinnerAug 10, 2023
4d7abc7
Perf+Cleanup: Removed temporary allocation in `remove_duplicate_save_…
JuliaPooAug 11, 2023
3d76f9a
clean up code
Fidget-SpinnerAug 11, 2023
e81def2
Merge branch 'partition_algo' of https://github.com/Fidget-Spinner/cp…
Fidget-SpinnerAug 11, 2023
9a5a3f7
make static
Fidget-SpinnerAug 11, 2023
df490d0
make types static
Fidget-SpinnerAug 11, 2023
1e4fc94
make const and ignore in c analyzer
Fidget-SpinnerAug 11, 2023
6de77a7
fix c-analyzer ignored list
Fidget-SpinnerAug 11, 2023
a11fc80
more cleanup
Fidget-SpinnerAug 13, 2023
c61015b
Merge remote-tracking branch 'upstream/main' into partition_algo
Fidget-SpinnerAug 13, 2023
56c62eb
regen files
Fidget-SpinnerAug 13, 2023
3c08ebe
address review
Fidget-SpinnerAug 14, 2023
d5f16be
regen
Fidget-SpinnerAug 14, 2023
1e61c49
and env var to block tests
Fidget-SpinnerAug 14, 2023
6c24b49
regen again
Fidget-SpinnerAug 14, 2023
2be404d
fix generated files
Fidget-SpinnerAug 14, 2023
29e255d
Address review
Fidget-SpinnerAug 15, 2023
3c44117
fix up INSERT
Fidget-SpinnerAug 15, 2023
b758b47
remove experimental parts
Fidget-SpinnerAug 15, 2023
80c7f18
revert more changes
Fidget-SpinnerAug 15, 2023
6a2b204
use memmove
Fidget-SpinnerAug 15, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
PrevPrevious commit
NextNext commit
clean up code
  • Loading branch information
@Fidget-Spinner
Fidget-Spinner committedAug 11, 2023
commit3d76f9a66666a956073e2c109ca9f7db2a6b46a6
21 changes: 13 additions & 8 deletionsPython/abstract_interp_cases.c.h
View file
Open in desktop

Some generated files are not rendered by default. Learn more abouthow customized files appear on GitHub.

122 changes: 74 additions & 48 deletionsPython/optimizer_analysis.c
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -20,6 +20,13 @@

#define OVERALLOCATE_FACTOR 2

#ifdef Py_DEBUG
#define DPRINTF(level, ...) \
if (lltrace >= (level)) { printf(__VA_ARGS__); }
#else
#define DPRINTF(level, ...)
#endif

// TYPENODE is a tagged pointer that uses the last 2 LSB as the tag
#define _Py_PARTITIONNODE_t uintptr_t

Expand DownExpand Up@@ -420,11 +427,17 @@ partitionnode_overwrite(_Py_UOpsAbstractInterpContext *ctx,
}
}

#if PARTITION_DEBUG
#ifdef Py_DEBUG

void
print_ctx_node(_Py_UOpsAbstractInterpContext *ctx, int i, bool is_printing_stack, int nstack_use, int nstack)
{
char *uop_debug = Py_GETENV("PYTHONUOPSDEBUG");
int lltrace = 0;
if (uop_debug != NULL && *uop_debug >= '0') {
lltrace = *uop_debug - '0'; // TODO: Parse an int and all that
}

bool is_local = false;
bool is_stack = false;

Expand All@@ -438,7 +451,7 @@ print_ctx_node(_Py_UOpsAbstractInterpContext *ctx, int i, bool is_printing_stack
_Py_PARTITIONNODE_t *root = partitionnode_get_rootptr(node);

if (is_printing_stack) {
fprintf(stderr, "%s", i == nstack_use - 1 ? "." : " ");
DPRINTF(3, "%s", i == nstack_use - 1 ? "." : " ");
}

if (tag == TYPE_REF) {
Expand All@@ -456,10 +469,10 @@ print_ctx_node(_Py_UOpsAbstractInterpContext *ctx, int i, bool is_printing_stack


_Py_PartitionRootNode *ptr = (_Py_PartitionRootNode *)partitionnode_clear_tag(*root);
fprintf(stderr, "%s:",
DPRINTF(3, "%s:",
ptr == NULL ? "?" : (ptr->static_or_dynamic == STATIC ? "static" : "dynamic"));
if (ptr != NULL && ptr->static_or_dynamic == STATIC) {
PyObject_Print(ptr->const_val,stderr, 0);
if (lltrace >= 4 &&ptr != NULL && ptr->static_or_dynamic == STATIC) {
PyObject_Print(ptr->const_val,stdout, 0);
}

if (tag == TYPE_REF) {
Expand All@@ -468,8 +481,7 @@ print_ctx_node(_Py_UOpsAbstractInterpContext *ctx, int i, bool is_printing_stack
: is_stack
? "stack"
: "const";
fprintf(stderr, "->%s[%d]",
wher, parent_idx);
DPRINTF(3, "->%s[%d]", wher, parent_idx);
}
}

Expand All@@ -479,26 +491,32 @@ print_ctx_node(_Py_UOpsAbstractInterpContext *ctx, int i, bool is_printing_stack
static void
print_ctx(_Py_UOpsAbstractInterpContext *ctx)
{
char *uop_debug = Py_GETENV("PYTHONUOPSDEBUG");
int lltrace = 0;
if (uop_debug != NULL && *uop_debug >= '0') {
lltrace = *uop_debug - '0'; // TODO: Parse an int and all that
}

_Py_PARTITIONNODE_t *locals = ctx->locals;
_Py_PARTITIONNODE_t *stackptr = ctx->stack_pointer;

int nstack_use = (int)(stackptr - ctx->stack);
int nstack = ctx->stack_len;
int nlocals = ctx->locals_len;

fprintf(stderr, " Stack: %p: [", ctx->stack);
DPRINTF(3, " Stack: %p: [", ctx->stack);
for (int i = 0; i < nstack; i++) {
print_ctx_node(ctx, i, true, nstack_use, nstack);
fprintf(stderr, " | ");
DPRINTF(3, " | ");
}
fprintf(stderr, "]\n");
DPRINTF(3, "]\n");

fprintf(stderr, " Locals %p: [", locals);
DPRINTF(3, " Locals %p: [", locals);
for (int i = 0; i < nlocals; i++) {
print_ctx_node(ctx, i, false, nstack_use, nstack);
fprintf(stderr, " | ");
DPRINTF(3, " | ");
}
fprintf(stderr, "]\n");
DPRINTF(3, "]\n");
}
#endif

Expand DownExpand Up@@ -588,7 +606,6 @@ number_jumps_and_targets(_PyUOpInstruction *trace, int trace_len, int *max_id)
jump_id_to_instruction[-target_id] = trace[target];
trace[target].opcode = target_id;
jump_and_target_id--;
fprintf(stderr, "op %d oparg %d\n", jump_id_to_instruction[-target_id].opcode, jump_id_to_instruction[-target_id].oparg);
}

// 1 for the jump
Expand All@@ -611,6 +628,14 @@ number_jumps_and_targets(_PyUOpInstruction *trace, int trace_len, int *max_id)
static int
remove_duplicate_save_ips(_PyUOpInstruction *trace, int trace_len)
{
#ifdef Py_DEBUG
char *uop_debug = Py_GETENV("PYTHONUOPSDEBUG");
int lltrace = 0;
if (uop_debug != NULL && *uop_debug >= '0') {
lltrace = *uop_debug - '0'; // TODO: Parse an int and all that
}
#endif

_PyUOpInstruction *temp_trace = PyMem_New(_PyUOpInstruction, trace_len);
if (temp_trace == NULL) {
return trace_len;
Expand All@@ -629,9 +654,7 @@ remove_duplicate_save_ips(_PyUOpInstruction *trace, int trace_len)
memcpy(trace, temp_trace, temp_trace_len * sizeof(_PyUOpInstruction));
PyMem_Free(temp_trace);

#if PARTITION_DEBUG
fprintf(stderr, "Removed %d SAVE_IPs\n", trace_len - temp_trace_len);
#endif
DPRINTF(3, "Removed %d SAVE_IPs\n", trace_len - temp_trace_len);
return temp_trace_len;
}

Expand DownExpand Up@@ -730,6 +753,14 @@ _Py_uop_analyze_and_optimize(
#define PARTITIONNODE_SET(src, dst, flag) partitionnode_set((src), (dst), (flag))
#define PARTITIONNODE_OVERWRITE(src, dst, flag) partitionnode_overwrite(ctx, (src), (dst), (flag))
#define MAKE_STATIC_ROOT(val) partitionnode_make_root(0, (val))
#ifdef Py_DEBUG
char *uop_debug = Py_GETENV("PYTHONUOPSDEBUG");
int lltrace = 0;
if (uop_debug != NULL && *uop_debug >= '0') {
lltrace = *uop_debug - '0'; // TODO: Parse an int and all that
}
#endif

PyObject *co_const_copy = NULL;
_PyUOpInstruction *jump_id_to_instruction = NULL;

Expand All@@ -740,7 +771,8 @@ _Py_uop_analyze_and_optimize(

int buffer_trace_len = 0;

_Py_UOpsAbstractInterpContext *ctx = _Py_UOpsAbstractInterpContext_New(co->co_stacksize, co->co_nlocals, curr_stacklen);
_Py_UOpsAbstractInterpContext *ctx = _Py_UOpsAbstractInterpContext_New(
co->co_stacksize, co->co_nlocals, curr_stacklen);
if (ctx == NULL) {
PyMem_Free(temp_writebuffer);
return trace_len;
Expand DownExpand Up@@ -775,9 +807,7 @@ _Py_uop_analyze_and_optimize(

// Is a special jump/target ID, decode that
if (opcode < 0 && opcode > max_jump_id) {
#if PARTITION_DEBUG
fprintf(stderr, "Special jump target/ID %d\n", opcode);
#endif
DPRINTF(2, "Special jump target/ID %d\n", opcode);
oparg = jump_id_to_instruction[-opcode].oparg;
opcode = jump_id_to_instruction[-opcode].opcode;
}
Expand DownExpand Up@@ -830,9 +860,8 @@ _Py_uop_analyze_and_optimize(
goto abstract_error;
}

#if PARTITION_DEBUG
fprintf(stderr, "Emitting LOAD_CONST\n");
#endif
DPRINTF(2, "Emitting LOAD_CONST\n");

temp_writebuffer[buffer_trace_len] = load_const;
buffer_trace_len++;

Expand All@@ -846,9 +875,8 @@ _Py_uop_analyze_and_optimize(
insert.opcode = INSERT;
insert.oparg = offset_from_target;

#if PARTITION_DEBUG
fprintf(stderr, "Emitting INSERT %d\n", offset_from_target);
#endif
DPRINTF(2, "Emitting INSERT %d\n", offset_from_target);

temp_writebuffer[buffer_trace_len] = insert;
buffer_trace_len++;
}
Expand All@@ -858,19 +886,18 @@ _Py_uop_analyze_and_optimize(
for (; trace[temp].opcode != SAVE_IP && temp < trace_len; temp++);
assert(trace[temp].opcode == SAVE_IP);

#if PARTITION_DEBUG
fprintf(stderr, "Emitting SAVE_IP\n");
#endif
DPRINTF(2, "Emitting SAVE_IP\n");

temp_writebuffer[buffer_trace_len] = trace[temp];
buffer_trace_len++;
num_dynamic_operands++;
}

}
}
#if PARTITION_DEBUG
fprintf(stderr, "Emitting %s\n", (opcode >= 300 ? _PyOpcode_uop_name : _PyOpcode_OpName)[opcode]);
#endif

DPRINTF(2, "Emitting %s\n", (opcode >= 300 ? _PyOpcode_uop_name : _PyOpcode_OpName)[opcode]);

temp_writebuffer[buffer_trace_len] = trace[i];
buffer_trace_len++;
}
Expand All@@ -879,14 +906,12 @@ _Py_uop_analyze_and_optimize(
* @TODO: shift these to the DSL
*/

#ifdef PARTITION_DEBUG
#ifdef Py_DEBUG
fprintf(stderr, " [-] Type propagating across: %s{%d} : %d. {reader: %d, writer: %d}\n",

DPRINTF(2, " [-] Type propagating across: %s{%d} : %d. {reader: %d, writer: %d}\n",
(opcode >= 300 ? _PyOpcode_uop_name : _PyOpcode_OpName)[opcode],
opcode, oparg,
i, buffer_trace_len);
#endif
#endif

switch (opcode) {
#include "abstract_interp_cases.c.h"
// @TODO convert these to autogenerated using DSL
Expand DownExpand Up@@ -987,11 +1012,11 @@ _Py_uop_analyze_and_optimize(
}
}
default:
fprintf(stderr, "Unknown opcode in abstract interpreter\n");
DPRINTF(1, "Unknown opcode in abstract interpreter\n");
Py_UNREACHABLE();
}

#if PARTITION_DEBUG
#ifdef Py_DEBUG
print_ctx(ctx);
#endif

Expand All@@ -1003,14 +1028,14 @@ _Py_uop_analyze_and_optimize(

if (opcode == EXIT_TRACE) {
// Copy the rest of the stubs over, then end.
#if PARTITION_DEBUG
fprintf(stderr, "Exit trace encountered, emitting the rest of the stubs\n");
#endif

DPRINTF(2, "Exit trace encountered, emitting the rest of the stubs\n");

i++; // We've already emitted an EXIT_TRACE
for (; i < trace_len; i++) {
#if PARTITION_DEBUG
fprintf(stderr, "Emitting %s\n", (opcode >= 300 ? _PyOpcode_uop_name : _PyOpcode_OpName)[opcode]);
#endif

DPRINTF(2, "Emitting %s\n", (opcode >= 300 ? _PyOpcode_uop_name : _PyOpcode_OpName)[opcode]);

temp_writebuffer[buffer_trace_len] = trace[i];
buffer_trace_len++;
}
Expand All@@ -1022,11 +1047,12 @@ _Py_uop_analyze_and_optimize(
fix_jump_side_exits(temp_writebuffer, buffer_trace_len, jump_id_to_instruction, max_jump_id);
assert(buffer_trace_len <= trace_len);

#if PARTITION_DEBUG
#ifdef Py_DEBUG
if (buffer_trace_len < trace_len) {
fprintf(stderr, "Shortened trace by %d instructions\n", trace_len - buffer_trace_len);
DPRINTF(2, "Shortened trace by %d instructions\n", trace_len - buffer_trace_len);
}
#endif

Py_DECREF(ctx);

PyObject *co_const_final = PyTuple_New(PyList_Size(co_const_copy));
Expand Down
12 changes: 2 additions & 10 deletionsTools/cases_generator/stacking.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -418,13 +418,5 @@ def _write_components_for_abstract_interp(
# NULL out the output stack effects
for poke in mgr.pokes:
if not poke.effect.size and poke.effect.name not in mgr.instr.unmoved_names:
out.emit(f"PARTITIONNODE_OVERWRITE((_Py_PARTITIONNODE_t *)PARTITIONNODE_NULLROOT, PEEK(-({poke.offset.as_index()})), true);")
# out.assign(
# StackEffect(
# poke.as_variable(),
# poke.effect.type,
# poke.effect.cond,
# poke.effect.size,
# ),
# StackEffect("partitionnode_nullroot()"),
# )
out.emit(f"PARTITIONNODE_OVERWRITE((_Py_PARTITIONNODE_t *)"
f"PARTITIONNODE_NULLROOT, PEEK(-({poke.offset.as_index()})), true);")
[8]ページ先頭
©2009-2025 Movatter.jp