Skip to content

[WIP] lay out cold blocks at end of function #91804

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

Jump to bottom
Closed
wants to merge 6 commits into from
Closed

[WIP] lay out cold blocks at end of function #91804

wants to merge 6 commits into from

Conversation

iritkatriel
Copy link
Member

@iritkatriel iritkatriel commented Apr 21, 2022 •
edited
Loading

This pushes the except blocks to the end of the function so that there is no jump over this code when there is no exception.

Example:

def f():
   try:
     x = "try"
   except:
     x = "except"
   finally:
     x = "finally"
     return x

Becomes:

  1           0 RESUME                            0

  2           2 NOP

  3           4 LOAD_CONST                        1 ('try')
              6 STORE_FAST                        0 (x)
              8 NOP

  7          10 LOAD_CONST                        3 ('finally')
             12 STORE_FAST                        0 (x)

  8          14 LOAD_FAST                         0 (x)
             16 RETURN_VALUE

  5     >>   18 NOP

  7          20 LOAD_CONST                        3 ('finally')
             22 STORE_FAST                        0 (x)

  8          24 LOAD_FAST                         0 (x)
             26 RETURN_VALUE
        >>   28 PUSH_EXC_INFO

  7          30 LOAD_CONST                        3 ('finally')
             32 STORE_FAST                        0 (x)

  8          34 LOAD_FAST                         0 (x)
             36 SWAP                              2
             38 POP_TOP
             40 SWAP                              2
             42 POP_EXCEPT
             44 RETURN_VALUE
        >>   46 COPY                              3
             48 POP_EXCEPT
             50 RERAISE                           1
        >>   52 PUSH_EXC_INFO

  4          54 POP_TOP

  5          56 LOAD_CONST                        2 ('except')
             58 STORE_FAST                        0 (x)
             60 POP_EXCEPT
             62 JUMP_BACKWARD                    23 (to 18)
        >>   64 COPY                              3
             66 POP_EXCEPT
             68 RERAISE                           1
ExceptionTable:
  4 to 6 -> 52 [0]
  28 to 40 -> 46 [1] lasti
  52 to 58 -> 64 [1] lasti
  60 to 68 -> 28 [0]

instead of:

  1           0 RESUME                            0

  2           2 NOP

  3           4 LOAD_CONST                        1 ('try')
              6 STORE_FAST                        0 (x)
              8 JUMP_FORWARD                      9 (to 28)    <-- This jump was removed
        >>   10 PUSH_EXC_INFO

  4          12 POP_TOP

  5          14 LOAD_CONST                        2 ('except')
             16 STORE_FAST                        0 (x)
             18 POP_EXCEPT
             20 JUMP_FORWARD                      8 (to 38)
        >>   22 COPY                              3
             24 POP_EXCEPT
             26 RERAISE                           1

  3     >>   28 NOP

  7          30 LOAD_CONST                        3 ('finally')
             32 STORE_FAST                        0 (x)

  8          34 LOAD_FAST                         0 (x)
             36 RETURN_VALUE

  5     >>   38 NOP

  7          40 LOAD_CONST                        3 ('finally')
             42 STORE_FAST                        0 (x)

  8          44 LOAD_FAST                         0 (x)
             46 RETURN_VALUE
        >>   48 PUSH_EXC_INFO

  7          50 LOAD_CONST                        3 ('finally')
             52 STORE_FAST                        0 (x)

  8          54 LOAD_FAST                         0 (x)
             56 SWAP                              2
             58 POP_TOP
             60 SWAP                              2
             62 POP_EXCEPT
             64 RETURN_VALUE
        >>   66 COPY                              3
             68 POP_EXCEPT
             70 RERAISE                           1
ExceptionTable:
  4 to 6 -> 10 [0]
  8 to 8 -> 48 [0]
  10 to 16 -> 22 [1] lasti
  18 to 26 -> 48 [0]
  48 to 60 -> 66 [1] lasti

@iritkatriel iritkatriel marked this pull request as draft April 21, 2022 22:35
@iritkatriel iritkatriel mentioned this pull request Apr 21, 2022
Closed
@markshannon
Copy link
Member

Rather than have the front-end decide which blocks are cold, would it make sense for the back-end to do it?

A cold block is one where all the branches to it are from SETUP_ pseudo instructions.
We already track the number of predecessors of a block. If we also tracked the number of exceptional predecessors, then a block would be cold if b->exceptional_predecessors == b->predecessors

@iritkatriel
Copy link
Member Author

Rather than have the front-end decide which blocks are cold, would it make sense for the back-end to do it?

A cold block is one where all the branches to it are from SETUP_ pseudo instructions. We already track the number of predecessors of a block. If we also tracked the number of exceptional predecessors, then a block would be cold if b->exceptional_predecessors == b->predecessors

Are we sure we only want except blocks to be cold? I was wondering if there are other cases, which the front end can identify.

@markshannon
Copy link
Member

Which other blocks would be cold?

@markshannon
Copy link
Member

Any block that ends with a RAISE_VARARGS or RERAISE is probably cold.
The optimizer can easily identify these, but it is harder for the front-end to do so.

@iritkatriel
Copy link
Member Author

iritkatriel commented May 9, 2022 •
edited
Loading

Rather than have the front-end decide which blocks are cold, would it make sense for the back-end to do it?

A cold block is one where all the branches to it are from SETUP_ pseudo instructions. We already track the number of predecessors of a block. If we also tracked the number of exceptional predecessors, then a block would be cold if b->exceptional_predecessors == b->predecessors

I'm not sure how to detect the end of the except body.

@iritkatriel
Copy link
Member Author

I'm not sure how to detect the end of the except body.

I thought of looking for POP_EXCEPT or POP_EXCEPT_AND_RERAISE (accounting for nesting) but I don't know if that's robust.

@markshannon
Copy link
Member

There is no need to detect the end of the except body. If a basic block is cold, it is cold, it doesn't matter where it ends.

What I would suggest, is to modify the code that determines reachability.
Everything that is reachable from the entry, but not through an exceptional edge is "warm". Everything that is reachable and is not warm is "cold".

This should be reasonably straightforward to implement. Have a "warm" bit and a "cold" bit.
Make a first pass using the current reachable function, ignoring exceptional edges, setting reachable blocks to "warm".
Then make a second pass, including exceptional edges, setting reachable blocks that aren't "warm" to "cold".

@iritkatriel
Copy link
Member Author

Yes, makes sense.

@iritkatriel
Copy link
Member Author

Another option is to roll the start-cold/end-cold into the compuler_push_flock/compiler_pop_fblock calls, then it happen implicitly in the front end.

@iritkatriel
Copy link
Member Author

Closing in favour of #92769.

@iritkatriel iritkatriel deleted the cold_code branch October 18, 2022 14:24
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@markshannon markshannon Awaiting requested review from markshannon markshannon is a code owner

Assignees
No one assigned
Labels
awaiting core review
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@iritkatriel @markshannon @bedevere-bot