Skip to content

Commit 3c2ac64

Browse files
JuliaPooJuliaPoo
authored
Fix: Buggy type propagation across SWAP (#30)
1 parent d95cdb6 commit 3c2ac64

3 files changed

Lines changed: 84 additions & 121 deletions

File tree

‎Python/tier2.c‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -376,6 +376,74 @@ __type_propagate_TYPE_OVERWRITE(
376376
}
377377
}
378378

379+
// src and dst are assumed to already be within the type context
380+
static void
381+
__type_propagate_TYPE_SWAP(
382+
_PyTier2TypeContext *type_context,
383+
_Py_TYPENODE_t *src, _Py_TYPENODE_t *dst)
384+
{
385+
// Check if they are the same tree
386+
_Py_TYPENODE_t *srcrootref = src;
387+
_Py_TYPENODE_t *dstrootref = dst;
388+
uintptr_t dsttag = _Py_TYPENODE_GET_TAG(*dst);
389+
uintptr_t srctag = _Py_TYPENODE_GET_TAG(*src);
390+
switch (dsttag) {
391+
case TYPE_REF: dstrootref = __typenode_get_rootptr(*dst);
392+
case TYPE_ROOT:
393+
switch (srctag) {
394+
case TYPE_REF: srcrootref = __typenode_get_rootptr(*src);
395+
case TYPE_ROOT:
396+
if (srcrootref == dstrootref) {
397+
// Same tree, no point swapping
398+
return;
399+
}
400+
break;
401+
default:
402+
Py_UNREACHABLE();
403+
}
404+
break;
405+
default:
406+
Py_UNREACHABLE();
407+
}
408+
409+
// src and dst are different tree,
410+
// Make all children of src be children of dst and vice versa
411+
412+
_Py_TYPENODE_t src_child_test = _Py_TYPENODE_MAKE_REF(
413+
_Py_TYPENODE_CLEAR_TAG((_Py_TYPENODE_t)src));
414+
_Py_TYPENODE_t dst_child_test = _Py_TYPENODE_MAKE_REF(
415+
_Py_TYPENODE_CLEAR_TAG((_Py_TYPENODE_t)dst));
416+
417+
// Search locals for children
418+
int nlocals = type_context->type_locals_len;
419+
for (int i = 0; i < nlocals; i++) {
420+
_Py_TYPENODE_t *node_ptr = &(type_context->type_locals[i]);
421+
if (*node_ptr == src_child_test) {
422+
*node_ptr = dst_child_test;
423+
}
424+
else if (*node_ptr == dst_child_test) {
425+
*node_ptr = src_child_test;
426+
}
427+
}
428+
429+
// Search stack for children
430+
int nstack = type_context->type_stack_len;
431+
for (int i = 0; i < nstack; i++) {
432+
_Py_TYPENODE_t *node_ptr = &(type_context->type_stack[i]);
433+
if (*node_ptr == src_child_test) {
434+
*node_ptr = dst_child_test;
435+
}
436+
else if (*node_ptr == dst_child_test) {
437+
*node_ptr = src_child_test;
438+
}
439+
}
440+
441+
// Finally, actually swap the nodes
442+
*src ^= *dst;
443+
*dst ^= *src;
444+
*src ^= *dst;
445+
}
446+
379447
static void
380448
__type_stack_shrink(_Py_TYPENODE_t **type_stackptr, int idx)
381449
{
@@ -489,6 +557,7 @@ type_propagate(
489557

490558
#define TYPE_SET(src, dst, flag) __type_propagate_TYPE_SET((src), (dst), (flag))
491559
#define TYPE_OVERWRITE(src, dst, flag) __type_propagate_TYPE_OVERWRITE(type_context, (src), (dst), (flag))
560+
#define TYPE_SWAP(src, dst) __type_propagate_TYPE_SWAP(type_context, (src), (dst))
492561

493562
#define STACK_GROW(idx) *type_stackptr += (idx)
494563

@@ -504,8 +573,18 @@ type_propagate(
504573

505574
switch (opcode) {
506575
#include "tier2_typepropagator.c.h"
576+
TARGET(SWAP) {
577+
_Py_TYPENODE_t *top = TYPESTACK_PEEK(1);
578+
_Py_TYPENODE_t * bottom = TYPESTACK_PEEK(2 + (oparg - 2));
579+
TYPE_SWAP(top, bottom);
580+
break;
581+
}
507582
default:
583+
#ifdef Py_DEBUG
584+
fprintf(stderr, "Unsupported opcode in type propagator: %s : %d\n", _PyOpcode_OpName[opcode], oparg);
585+
#else
508586
fprintf(stderr, "Unsupported opcode in type propagator: %d\n", opcode);
587+
#endif
509588
Py_UNREACHABLE();
510589
}
511590

‎Python/tier2_typepropagator.c.h‎

Lines changed: 0 additions & 104 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎Tools/cases_generator/generate_cases.py‎

Lines changed: 5 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -53,9 +53,9 @@
5353

5454
TYPE_PROPAGATOR_FORBIDDEN = [
5555
# Type propagator shouldn't see these
56-
"JUMP_IF_FALSE_OR_POP",
57-
"JUMP_IF_TRUE_OR_POP",
5856
"FOR_ITER",
57+
"SWAP",
58+
# Not supported
5959
"SEND",
6060
"SEND_GEN",
6161
"YIELD_VALUE",
@@ -71,12 +71,6 @@
7171
"MATCH_KEYS",
7272
"EXTENDED_ARG",
7373
"WITH_EXCEPT_START",
74-
# Type propagation across these instructions are forbidden
75-
# due to conditional effects that can't be determined statically
76-
# The handling of type propagation across these opcodes are handled elsewhere
77-
# within tier2.
78-
"BB_TEST_IF_FALSE_OR_POP",
79-
"BB_TEST_IF_TRUE_OR_POP" # Type propagator handles this in BB_BRANCH
8074
]
8175

8276
arg_parser = argparse.ArgumentParser(
@@ -344,10 +338,7 @@ def __init__(self, inst: parser.InstDef):
344338
def write_typeprop(self, out: Formatter) -> None:
345339
"""Write one instruction's type propagation rules"""
346340

347-
if self.name in TYPE_PROPAGATOR_FORBIDDEN:
348-
out.emit(f'fprintf(stderr, "Type propagation across `{self.name}` shouldn\'t be handled statically!\\n");')
349-
out.emit("Py_UNREACHABLE();")
350-
return
341+
# TODO: Detect loops like in SWAP
351342

352343
need_to_declare = []
353344
# Stack input is used in local effect
@@ -644,11 +635,6 @@ def write_body(self, out: Formatter, dedent: int, cache_adjust: int = 0) -> None
644635
def write_typeprop(self, out: Formatter) -> None:
645636
"""Write one instruction's type propagation rules"""
646637

647-
if self.name in TYPE_PROPAGATOR_FORBIDDEN:
648-
out.emit(f'fprintf(stderr, "Type propagation across `{self.name}` shouldn\'t be handled statically!\\n");')
649-
out.emit("Py_UNREACHABLE();")
650-
return
651-
652638
need_to_declare = []
653639
# Stack input is used in local effect
654640
if self.local_effects and \
@@ -1328,6 +1314,8 @@ def write_typepropagator(self) -> None:
13281314
self.out = Formatter(f, 8)
13291315

13301316
for thing in self.everything:
1317+
if thing.name in TYPE_PROPAGATOR_FORBIDDEN:
1318+
continue
13311319
match thing:
13321320
case parser.InstDef(kind=kind, name=name):
13331321
match kind:

0 commit comments

Comments
 (0)