Skip to content

Commit 33988cf

Browse files
Fidget-SpinnerFidget-Spinner
authored
fix: recursive generation of basic blocks (python#29)
1 parent ab8d1e3 commit 33988cf

10 files changed

Lines changed: 105 additions & 68 deletions

File tree

‎Include/internal/pycore_code.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@ typedef struct {
1212
// The LSB indicates whether the bb branch is a type guard or not.
1313
// To get the actual BB ID, do a right bit shift by one.
1414
uint16_t bb_id_tagged;
15+
uint16_t successor_jumpby;
1516
} _PyBBBranchCache;
1617

1718
#define INLINE_CACHE_ENTRIES_BB_BRANCH CACHE_ENTRIES(_PyBBBranchCache)

‎Include/internal/pycore_opcode.h‎

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

‎Include/opcode.h‎

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

‎Lib/dis.py‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -62,8 +62,7 @@
6262
if uop.startswith('BB_BRANCH') or uop.startswith('BB_JUMP'):
6363
if uop.startswith('BB_JUMP'):
6464
_bb_jumps.append(uop_opcode)
65-
if uop.startswith('BB_BRANCH'):
66-
_inline_cache_entries[uop_opcode] = 1
65+
_inline_cache_entries[uop_opcode] = 2
6766
_uop_hasoparg.append(uop_opcode)
6867

6968
deoptmap = {

‎Lib/opcode.py‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -386,6 +386,10 @@ def pseudo_op(name, op, real_ops):
386386
"SEND": [
387387
"SEND_GEN",
388388
],
389+
"BB_BRANCH": [
390+
"BB_BRANCH_IF_FLAG_SET",
391+
"BB_BRANCH_IF_FLAG_UNSET",
392+
]
389393
}
390394
_specialized_instructions = [
391395
opcode for family in _specializations.values() for opcode in family
@@ -440,6 +444,10 @@ def pseudo_op(name, op, real_ops):
440444
"SEND": {
441445
"counter": 1,
442446
},
447+
"BB_BRANCH" : {
448+
"bb_id": 1,
449+
"forward_jumpby": 1
450+
},
443451
}
444452

445453
_inline_cache_entries = [

‎Python/bytecodes.c‎

Lines changed: 20 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -3284,7 +3284,7 @@ dummy_func(
32843284

32853285
// Tier 2 instructions
32863286
// Type propagator assumes this doesn't affect type context
3287-
inst(BB_BRANCH, (unused/1 --)) {
3287+
inst(BB_BRANCH, (unused/2 --)) {
32883288
_Py_CODEUNIT *t2_nextinstr = NULL;
32893289
_PyBBBranchCache *cache = (_PyBBBranchCache *)next_instr;
32903290
_Py_CODEUNIT *tier1_fallback = NULL;
@@ -3314,14 +3314,14 @@ dummy_func(
33143314
DISPATCH();
33153315
}
33163316
}
3317-
// Their addresses should be the same. Because
3318-
// The first BB should be generated right after the previous one.
3319-
assert(next_instr + INLINE_CACHE_ENTRIES_BB_BRANCH == t2_nextinstr);
3317+
Py_ssize_t forward_jump = t2_nextinstr - next_instr;
3318+
assert((uint16_t)forward_jump == forward_jump);
3319+
cache->successor_jumpby = (uint16_t)forward_jump;
33203320
next_instr = t2_nextinstr;
33213321
DISPATCH();
33223322
}
33233323

3324-
inst(BB_BRANCH_IF_FLAG_UNSET, (unused/1 --)) {
3324+
inst(BB_BRANCH_IF_FLAG_UNSET, (unused/2 --)) {
33253325
if (!BB_TEST_IS_SUCCESSOR(bb_test)) {
33263326
_Py_CODEUNIT *curr = next_instr - 1;
33273327
_Py_CODEUNIT *t2_nextinstr = NULL;
@@ -3341,17 +3341,22 @@ dummy_func(
33413341
_PyTier2_RewriteForwardJump(curr, next_instr);
33423342
DISPATCH();
33433343
}
3344+
_PyBBBranchCache *cache = (_PyBBBranchCache *)next_instr;
3345+
JUMPBY(cache->successor_jumpby);
3346+
DISPATCH();
33443347
}
33453348

3346-
inst(BB_JUMP_IF_FLAG_UNSET, (unused/1 --)) {
3349+
inst(BB_JUMP_IF_FLAG_UNSET, (unused/2 --)) {
33473350
if (!BB_TEST_IS_SUCCESSOR(bb_test)) {
33483351
JUMPBY(oparg);
33493352
DISPATCH();
33503353
}
3351-
// Fall through to next instruction.
3354+
_PyBBBranchCache *cache = (_PyBBBranchCache *)next_instr;
3355+
JUMPBY(cache->successor_jumpby);
3356+
DISPATCH();
33523357
}
33533358

3354-
inst(BB_BRANCH_IF_FLAG_SET, (unused/1 --)) {
3359+
inst(BB_BRANCH_IF_FLAG_SET, (unused/2 --)) {
33553360
if (BB_TEST_IS_SUCCESSOR(bb_test)) {
33563361
_Py_CODEUNIT *curr = next_instr - 1;
33573362
_Py_CODEUNIT *t2_nextinstr = NULL;
@@ -3371,14 +3376,19 @@ dummy_func(
33713376
_PyTier2_RewriteForwardJump(curr, next_instr);
33723377
DISPATCH();
33733378
}
3379+
_PyBBBranchCache *cache = (_PyBBBranchCache *)next_instr;
3380+
JUMPBY(cache->successor_jumpby);
3381+
DISPATCH();
33743382
}
33753383

3376-
inst(BB_JUMP_IF_FLAG_SET, (unused/1 --)) {
3384+
inst(BB_JUMP_IF_FLAG_SET, (unused/2 --)) {
33773385
if (BB_TEST_IS_SUCCESSOR(bb_test)) {
33783386
JUMPBY(oparg);
33793387
DISPATCH();
33803388
}
3381-
// Fall through to next instruction.
3389+
_PyBBBranchCache *cache = (_PyBBBranchCache *)next_instr;
3390+
JUMPBY(cache->successor_jumpby);
3391+
DISPATCH();
33823392
}
33833393

33843394
// Type propagator assumes this doesn't affect type context

‎Python/generated_cases.c.h‎

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

‎Python/opcode_metadata.h‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -835,7 +835,7 @@ _PyOpcode_num_pushed(int opcode, int oparg, bool jump) {
835835
}
836836
#endif
837837

838-
enum InstructionFormat { INSTR_FMT_IB, INSTR_FMT_IBC, INSTR_FMT_IBC000, INSTR_FMT_IBC00000000, INSTR_FMT_IBIB, INSTR_FMT_IX, INSTR_FMT_IXC, INSTR_FMT_IXC000 };
838+
enum InstructionFormat { INSTR_FMT_IB, INSTR_FMT_IBC, INSTR_FMT_IBC0, INSTR_FMT_IBC000, INSTR_FMT_IBC00000000, INSTR_FMT_IBIB, INSTR_FMT_IX, INSTR_FMT_IXC, INSTR_FMT_IXC0, INSTR_FMT_IXC000 };
839839
struct opcode_metadata {
840840
bool valid_entry;
841841
enum InstructionFormat instr_format;
@@ -1041,11 +1041,11 @@ const struct opcode_metadata _PyOpcode_opcode_metadata[256] = {
10411041
[SWAP] = { true, INSTR_FMT_IB },
10421042
[EXTENDED_ARG] = { true, INSTR_FMT_IB },
10431043
[CACHE] = { true, INSTR_FMT_IX },
1044-
[BB_BRANCH] = { true, INSTR_FMT_IBC },
1045-
[BB_BRANCH_IF_FLAG_UNSET] = { true, INSTR_FMT_IBC },
1046-
[BB_JUMP_IF_FLAG_UNSET] = { true, INSTR_FMT_IBC },
1047-
[BB_BRANCH_IF_FLAG_SET] = { true, INSTR_FMT_IXC },
1048-
[BB_JUMP_IF_FLAG_SET] = { true, INSTR_FMT_IBC },
1044+
[BB_BRANCH] = { true, INSTR_FMT_IBC0 },
1045+
[BB_BRANCH_IF_FLAG_UNSET] = { true, INSTR_FMT_IBC0 },
1046+
[BB_JUMP_IF_FLAG_UNSET] = { true, INSTR_FMT_IBC0 },
1047+
[BB_BRANCH_IF_FLAG_SET] = { true, INSTR_FMT_IXC0 },
1048+
[BB_JUMP_IF_FLAG_SET] = { true, INSTR_FMT_IBC0 },
10491049
[BB_JUMP_BACKWARD_LAZY] = { true, INSTR_FMT_IB },
10501050
};
10511051
#endif

‎Python/opcode_targets.h‎

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

‎tier2_test.py‎

Lines changed: 19 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -236,7 +236,6 @@ def test_guard_elimination(a,b):
236236
"CHECK_FLOAT", # First ladder check
237237
"NOP",
238238
"BB_JUMP_IF_FLAG_SET", # Rewrite to jump to float case
239-
"POP_TOP", # Pop result
240239

241240
# The same as above
242241
"CHECK_INT",
@@ -498,7 +497,6 @@ def f(x,l):
498497
######################################################################
499498
with TestInfo("tier 2 BB_TEST_POP_IF_FALSE flag setting"):
500499
# See https://github.com/pylbbv/pylbbv/issues/23 for more information.
501-
import sys
502500

503501
class A:
504502
def __init__(self): ...
@@ -518,4 +516,23 @@ def f(a):
518516

519517
# As long as it doesn't crash, everything's good.
520518

519+
######################################################################
520+
# Tests for: Tier 2 recursive functions block generation #
521+
######################################################################
522+
with TestInfo("tier 2 BB_TEST_POP_IF_FALSE flag setting"):
523+
# See https://github.com/pylbbv/pylbbv/issues/23 for more information.
524+
def f(x):
525+
# Force specialisation
526+
x + x
527+
if x == 3:
528+
return 1
529+
return f(x-1) + 1
530+
531+
trigger_tier2(f, (8,))
532+
533+
assert f(8) == 6
534+
assert f(8) == 6
535+
536+
# As long as it doesn't crash, everything's good.
537+
521538
print("Tests completed ^-^")

0 commit comments

Comments
 (0)