Skip to content

gh-116168: Remove extra _CHECK_STACK_SPACE uops #117242

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.

Sign up for GitHub

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

Already on GitHub? Sign in to your account

Merged
gvanrossum merged 20 commits into from
Apr 3, 2024
Merged

gh-116168: Remove extra _CHECK_STACK_SPACE uops #117242

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
20 commits
Select commit Hold shift + click to select a range
548fb94
gh-116168: Remove extra _CHECK_STACK_SPACE uops
lazorchakp Mar 21, 2024
1a7cb94
Merge remote-tracking branch 'upstream/main' into gh-116168-remove-ex…
lazorchakp Mar 26, 2024
5eca7ca
Assorted cleanup and pipeline fix
lazorchakp Mar 26, 2024
76e540a
Merge remote-tracking branch 'upstream/main' into gh-116168-remove-ex…
lazorchakp Mar 26, 2024
1b1d8e1
Fix loss of data warning and revert changes to optimizer.c
lazorchakp Mar 26, 2024
781590d
Merge remote-tracking branch 'upstream/main' into gh-116168-remove-ex…
lazorchakp Mar 26, 2024
617e4f3
Move all _CHECK_STACK_SPACE consolidation to optimizer_analysis.c
lazorchakp Mar 28, 2024
49a1fa9
Merge remote-tracking branch 'upstream/main' into gh-116168-remove-ex…
lazorchakp Mar 28, 2024
95ef823
Use get_co in peephole_opt
lazorchakp Mar 28, 2024
defdc2b
clean up diff
lazorchakp Mar 28, 2024
df0d589
Update with PR feedback, still need to move logic to optimizer_byteco…
lazorchakp Mar 29, 2024
83c57a2
Merge remote-tracking branch 'upstream/main' into gh-116168-remove-ex…
lazorchakp Mar 29, 2024
3f7ba5b
Merge remote-tracking branch 'upstream/main' into gh-116168-remove-ex…
lazorchakp Mar 29, 2024
c12119f
Make combine_stack_space_checks as similar to peephole_opt as possible
lazorchakp Mar 30, 2024
f0b2133
Integrate combine_stack_space_checks with peephole_opt
lazorchakp Mar 30, 2024
486ece6
Address style nits
lazorchakp Apr 1, 2024
5b797e8
Merge remote-tracking branch 'upstream/main' into gh-116168-remove-ex…
lazorchakp Apr 1, 2024
64fac38
Undo accidental newline removal
lazorchakp Apr 2, 2024
77e94cb
Merge remote-tracking branch 'upstream/main' into gh-116168-remove-ex…
lazorchakp Apr 3, 2024
7b62c2b
Fix variables names in large-framesize test comment
lazorchakp Apr 3, 2024
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
Prev Previous commit
Next Next commit
Update with PR feedback, still need to move logic to optimizer_byteco… 
…des.c
  • Loading branch information
@lazorchakp
lazorchakp committed Mar 29, 2024
commit df0d5890ea0eb8cdb30699def05a2f0ce53b6866
28 changes: 0 additions & 28 deletions Lib/test/test_capi/test_opt.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -579,14 +579,6 @@ def testfunc(n):
@requires_specialization
@unittest.skipIf(os.getenv("PYTHON_UOPS_OPTIMIZE") == "0", "Needs uop optimizer to run.")
class TestUopsOptimization(unittest.TestCase):
FRAMESIZE_ADJUSTMENT = 1 if platform.architecture()[0] == "32bit" else 0

def _assert_framesize_cross_platform(self, fn_obj, expected_framesize):
self.assertEqual(
_testinternalcapi.get_co_framesize(fn_obj.__code__),
expected_framesize + self.FRAMESIZE_ADJUSTMENT
)

def _run_with_optimizer(self, testfunc, arg):
res = None
opt = _testinternalcapi.new_uop_optimizer()
Expand Down Expand Up @@ -974,8 +966,6 @@ def testfunc(n):
a += b + c + d
return a

@gvanrossum gvanrossum Apr 1, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

One blank line is enough. :-)

(Ditto below.)

self._assert_framesize_cross_platform((dummy12), 12)
self._assert_framesize_cross_platform((dummy13), 13)

res, ex = self._run_with_optimizer(testfunc, 32)
self.assertEqual(res, 832)
Expand Down Expand Up @@ -1004,8 +994,6 @@ def testfunc(n):
a += b + c
return a

self._assert_framesize_cross_platform((dummy12), 12)
self._assert_framesize_cross_platform((dummy15), 15)

res, ex = self._run_with_optimizer(testfunc, 32)
self.assertEqual(res, 224)
Expand Down Expand Up @@ -1042,9 +1030,6 @@ def testfunc(n):
a += b + c + d + e
return a

self._assert_framesize_cross_platform((dummy12), 12)
self._assert_framesize_cross_platform((dummy13), 13)
self._assert_framesize_cross_platform((dummy18), 18)

res, ex = self._run_with_optimizer(testfunc, 32)
self.assertEqual(res, 800)
Expand Down Expand Up @@ -1082,9 +1067,6 @@ def testfunc(n):
a += b + c + d + e
return a

self._assert_framesize_cross_platform((dummy12), 12)
self._assert_framesize_cross_platform((dummy13), 13)
self._assert_framesize_cross_platform((dummy18), 18)

res, ex = self._run_with_optimizer(testfunc, 32)
self.assertEqual(res, 800)
Expand Down Expand Up @@ -1130,13 +1112,6 @@ def testfunc(n):
a += b + c + d
return a

self._assert_framesize_cross_platform(dummy0, 11)
self._assert_framesize_cross_platform(dummy1, 14)
self._assert_framesize_cross_platform(dummy2, 14)
self._assert_framesize_cross_platform(dummy3, 14)
self._assert_framesize_cross_platform(dummy4, 16)
self._assert_framesize_cross_platform(dummy5, 14)
self._assert_framesize_cross_platform(dummy6, 18)

res, ex = self._run_with_optimizer(testfunc, 32)
self.assertEqual(res, 96)
Expand Down Expand Up @@ -1198,8 +1173,6 @@ def testfunc(n):
b += dummy15(7)
return b

self._assert_framesize_cross_platform((dummy_large), repetitions + 12)
self._assert_framesize_cross_platform((dummy15), 15)

res, ex = self._run_with_optimizer(testfunc, 32)
self.assertEqual(res, 32 * (repetitions + 9))
Expand Down Expand Up @@ -1235,7 +1208,6 @@ def testfunc(n):
a += dummy15(n)
return a

self._assert_framesize_cross_platform((dummy15), 15)

res, ex = self._run_with_optimizer(testfunc, 32)
self.assertEqual(res, 42 * 32)
Expand Down
2 changes: 1 addition & 1 deletion Python/bytecodes.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4103,7 +4103,7 @@ dummy_func(
}

tier2 op(_CHECK_STACK_SPACE_OPERAND, (framesize/2 --)) {
assert(framesize < INT_MAX);
assert(framesize <= INT_MAX);
DEOPT_IF(!_PyThreadState_HasStackSpace(tstate, framesize));
DEOPT_IF(tstate->py_recursion_remaining <= 1);
}
Expand Down
2 changes: 1 addition & 1 deletion Python/executor_cases.c.h
View file
Open in desktop

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

125 changes: 59 additions & 66 deletions Python/optimizer_analysis.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -529,15 +529,13 @@ remove_unneeded_uops(_PyUOpInstruction *buffer, int buffer_size)
}
}
}
Py_FatalError("No terminating instruction");
Py_UNREACHABLE();
}

/* _PUSH_FRAME/_POP_FRAME's operand can be 0, a PyFunctionObject *, or a
* PyCodeObject *. Retrieve the code object if possible.
*/
static PyCodeObject *
get_co(_PyUOpInstruction *op) {
static PyCodeObject *get_co(_PyUOpInstruction *op) {

@gvanrossum gvanrossum Apr 1, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Style nit:

Suggested change
static PyCodeObject *get_co(_PyUOpInstruction *op) {
static PyCodeObject *
get_co(_PyUOpInstruction *op)
{

assert(op->opcode == _PUSH_FRAME || op->opcode == _POP_FRAME);
PyCodeObject *co = NULL;
uint64_t operand = op->operand;
Expand All @@ -556,103 +554,98 @@ get_co(_PyUOpInstruction *op) {
return co;
}

// _PUSH_FRAME is 3 ops in front of _CHECK_STACK_SPACE
#define _CHECK_STACK_TO_PUSH_FRAME_OFFSET 3
/* Get the frame size from a _PUSH_FRAME/_POP_FRAME instruction,
* -1 if the information isn't available.
*/
static int get_framesize(_PyUOpInstruction *op) {
PyCodeObject *co = get_co(op);
if (co == NULL) {
return -1;
}
return co->co_framesize;
}

/* Compute the maximum stack space needed for this trace and consolidate
* all possible _CHECK_STACK_SPACE ops to one _CHECK_STACK_SPACE_OPERAND.
* This calculation is essentially a traversal over the tree of function
* calls in this trace.
*/
static void
combine_stack_space_checks(

@markshannon markshannon Mar 28, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Rather than make this a separate pass, could you integrate into optimize_uops by adding it to optimizer_bytecodes.c.

@lazorchakp lazorchakp Mar 29, 2024

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Happy to do this, but to confirm - do you definitely prefer integration into optimize_uops over peephole_opt or remove_unneeded_uops? Any of these would prevent an extra pass.

@lazorchakp lazorchakp Mar 29, 2024

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@Fidget-Spinner may also have an opinion here

@Fidget-Spinner Fidget-Spinner Mar 29, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Both peephole_opt or optimize_uops is fine to me. peephole_opt would likely be clearer as this pass does not use any information from the abstract interpreter.

_PyUOpInstruction *buffer,
int buffer_size
)
{
#ifdef Py_DEBUG
// assume there's a _PUSH_FRAME after every _CHECK_STACK_SPACE
bool expecting_push = false;
// if we ever can't get a framesize from _PUSH_FRAME, must exit soon
bool must_exit = false;
#endif
int depth = 0;
uint32_t space_at_depth[MAX_ABSTRACT_FRAME_DEPTH];
uint32_t curr_space = 0;
uint32_t max_space = 0;
int curr_framesize = -1;
int curr_space = 0;
int max_space = 0;
_PyUOpInstruction *first_valid_check_stack = NULL;
_PyUOpInstruction *corresponding_check_stack = NULL;
for (int pc = 0; pc < buffer_size; pc++) {
int opcode = buffer[pc].opcode;
switch (opcode) {
case _CHECK_STACK_SPACE: {
#ifdef Py_DEBUG
assert(expecting_push == false);
assert(must_exit == false);
expecting_push = true;
#endif
uint32_t framesize = 0;
if (pc + _CHECK_STACK_TO_PUSH_FRAME_OFFSET < buffer_size) {
_PyUOpInstruction *uop = &buffer[
pc + _CHECK_STACK_TO_PUSH_FRAME_OFFSET
];
assert(uop->opcode == _PUSH_FRAME);
PyCodeObject *code = get_co(uop);
if (code != NULL) {
framesize = code->co_framesize;
}
assert(corresponding_check_stack == NULL);
corresponding_check_stack = &buffer[pc];
break;
}
case _PUSH_FRAME: {
assert(corresponding_check_stack != NULL);
curr_framesize = get_framesize(&buffer[pc]);
if (curr_framesize == -1) {
goto finish;
}
if (framesize == 0) {
#ifdef Py_DEBUG
must_exit = true;
#endif
break;
assert(curr_framesize > 0);
curr_space += curr_framesize;
if (curr_space < 0 || curr_space > UINT32_MAX) {
// overflow or won't fit in operand

@gvanrossum gvanrossum Apr 1, 2024

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It will fit in operand (which is always 64 bits) but not in the cache entry for the new instruction (which is always unsigned 32 bits) or won't be able to be converted to signed int (which it must be for the _PyThreadState_HasStackSpace() call). So the check is right but the comment feels like it is misrepresenting the situation. My suggestion:

Suggested change
// overflow or won't fit in operand
// won't fit in signed 32-bit int

goto finish;
}
max_space = curr_space > max_space ? curr_space : max_space;
if (first_valid_check_stack == NULL) {
first_valid_check_stack = &buffer[pc];
first_valid_check_stack = corresponding_check_stack;
}
else {
// delete all but the first valid _CHECK_STACK_SPACE
buffer[pc].opcode = _NOP;
corresponding_check_stack->opcode = _NOP;
}
space_at_depth[depth] = framesize;
curr_space += framesize;
max_space = curr_space > max_space ? curr_space : max_space;
depth++;
assert(depth < MAX_ABSTRACT_FRAME_DEPTH);
corresponding_check_stack = NULL;
break;
}
case _POP_FRAME: {
#ifdef Py_DEBUG
assert(expecting_push == false);
assert(must_exit == false);
#endif
depth--;
assert(depth >= 0);
curr_space -= space_at_depth[depth];
assert(corresponding_check_stack == NULL);
assert(curr_framesize > 0);
assert(curr_framesize <= curr_space);
curr_space -= curr_framesize;
curr_framesize = get_framesize(&buffer[pc]);
assert(curr_framesize > 0);
if (curr_framesize == -1) {
goto finish;
}
break;
}
case _JUMP_TO_TOP:
case _EXIT_TRACE: {
goto finish;
}
#ifdef Py_DEBUG
case _PUSH_FRAME: {
assert(expecting_push == true);
expecting_push = false;
case _CHECK_STACK_SPACE_OPERAND: {
/* We should never see _CHECK_STACK_SPACE_OPERANDs.
* They are only created at the end of this pass. */
assert(false);
break;
}
#endif
case _JUMP_TO_TOP:
case _EXIT_TRACE: {
if (first_valid_check_stack != NULL) {
assert(first_valid_check_stack->opcode == _CHECK_STACK_SPACE);
assert(max_space > 0);
assert(max_space < INT_MAX);
first_valid_check_stack->opcode = _CHECK_STACK_SPACE_OPERAND;
first_valid_check_stack->operand = max_space;
}
return;
}
}
}
Py_FatalError("No terminating instruction");
Py_UNREACHABLE();
finish:
if (first_valid_check_stack != NULL) {
assert(first_valid_check_stack->opcode == _CHECK_STACK_SPACE);
assert(max_space > 0);
assert(max_space <= INT_MAX);
assert(max_space <= UINT32_MAX);
first_valid_check_stack->opcode = _CHECK_STACK_SPACE_OPERAND;
first_valid_check_stack->operand = max_space;
}
}

static void
Expand Down