bpo-41323: Perform 'peephole' optimizations directly on the CFG. by markshannon · Pull Request #21517 · python/cpython · GitHub

Saves about 200 lines of code
Breaks the coupling between the optimizer and the bytecode and line number table formats.

https://bugs.python.org/issue41323

…y on the CFG.

Did you forget this?

Yes, thanks.

Mostly, this looks pretty good. Consider removing the peephole.c file altogether. It was originally part of compile.c and got separated out when it got too large. We can more the PyCode_Optimize() function back to compile.c. Ideally, we could drop it from the public api as part of Victor's PEP to overhaul the C API.

One small loss is that the current code has macros that provide meaningful opcode groupings like UNCONDITIONAL_JUMP, CONDITIONAL_JUMP, ABSOLUTE_JUMP, and JUMPS_ON_TRUE. I always found those grouping helpful for reasoning about the code.

You can use Py_UNUSED for the ones that are not code in the function declaration.

done

🤖 New build scheduled with the buildbot fleet by @pablogsal for commit 6b7019a 🤖

If you want to schedule another build, you need to add the ":hammer: test-with-buildbots" label again.

Suggested change

      
                if (!names || !varnames)
          
                    goto error;
          
                if (!names || !varnames) {
          
                    goto error;
          
                }

done

Does this converge on one single iteration? What happens if you have a sequence of many jumps all together between blocks?

No. Some jumps that can be eliminated will still remain.

This PR is aimed at closely mimicking the behavior of the existing peephole optimizer.
We can improve it later.

This looks great and very compact! This is a very good work @markshannon ! I will do a more thorough review over the weekend but I have left some minor comments for now

Huh? Why we need a new blocks here for connecting the jumps?

All instructions following a jump or branch must start a new basic block.

We now need the CFG generated by the code generation pass to be correct, as we perform jump elimination on it, rather than the CFG recreated in peephole.c.

Longer term, I think the front end should use labels and CFG creation should be a pass in between the code generation pass and the optimizer.

@rhettinger
I've removed peephole.c as you suggested.

The UNCONDITIONAL_JUMP, CONDITIONAL_JUMP, ABSOLUTE_JUMP, and JUMPS_ON_TRUE don't seem that useful in an instruction based optimizer.
I initially created versions of them, but it turned out they were unused. So I deleted them.
For jump-to-jump elimination, it turns out that the exact opcode is more important that whether a jump is conditional and/or relative.

Don't we need one of these?

Suggested change

      
                }
          
                }
          
                PyObject_Free(stack);

Yes, thanks.

🤖 New build scheduled with the buildbot fleet by @pablogsal for commit fda0bed 🤖

If you want to schedule another build, you need to add the ":hammer: test-with-buildbots" label again.

One final tweak. Jumps to empty blocks that were immediately followed by jumps were not being eliminated. The final commit fixes that.

…honGH-21517) * Move 'peephole' optimizations into compile.c and perform them directly on the CFG.

Move 'peephole' optimizations into compile.c and perform them directl…

d5b4bda

…y on the CFG.

the-knights-who-say-ni added the CLA signed label Jul 17, 2020

bedevere-bot added the awaiting core review label Jul 17, 2020

markshannon assigned pablogsal Jul 17, 2020

markshannon changed the title bpo-41323: Move 'peephole' optimizations directly on the CFG. bpo-41323: Perform 'peephole' optimizations directly on the CFG. Jul 17, 2020

Regenerate frozen importlib.

c480401

remilapeyre reviewed Jul 17, 2020

View reviewed changes

Remove commented out code.

6b7019a

pablogsal reviewed Jul 17, 2020

View reviewed changes

pablogsal added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Jul 17, 2020

bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Jul 17, 2020

pablogsal reviewed Jul 17, 2020

View reviewed changes

Two minor code tidy ups.

a2915d5

markshannon force-pushed the move-peephole-optimizations-to-cfg branch from 7845d6f to 8551d33 Compare July 20, 2020 09:33

Remove peephole.c

7bc2522

markshannon force-pushed the move-peephole-optimizations-to-cfg branch from 8551d33 to 7bc2522 Compare July 20, 2020 09:49

markshannon requested a review from a team as a code owner July 20, 2020 09:49

sweeneyde reviewed Jul 20, 2020

View reviewed changes

Fix leak in mark_reachable.

fda0bed

pablogsal added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Jul 20, 2020

bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Jul 20, 2020

rhettinger approved these changes Jul 21, 2020

View reviewed changes

bedevere-bot removed the awaiting core review label Jul 21, 2020

bedevere-bot added the awaiting merge label Jul 21, 2020

pablogsal approved these changes Jul 21, 2020

View reviewed changes

Treat jumps to empty blocks as jumps to the following block.

17541b6

Regenerate importlib

1b57a42

pablogsal approved these changes Jul 21, 2020

View reviewed changes

markshannon merged commit 6e8128f into python:master Jul 30, 2020

bedevere-bot removed the awaiting merge label Jul 30, 2020

shihai1991 pushed a commit to shihai1991/cpython that referenced this pull request Aug 4, 2020

bpo-41323: Perform 'peephole' optimizations directly on the CFG. (pyt…

2c6db7b

…honGH-21517) * Move 'peephole' optimizations into compile.c and perform them directly on the CFG.

shihai1991 pushed a commit to shihai1991/cpython that referenced this pull request Aug 20, 2020

bpo-41323: Perform 'peephole' optimizations directly on the CFG. (pyt…

9b6d58d

…honGH-21517) * Move 'peephole' optimizations into compile.c and perform them directly on the CFG.

xzy3 pushed a commit to xzy3/cpython that referenced this pull request Oct 18, 2020

bpo-41323: Perform 'peephole' optimizations directly on the CFG. (pyt…

5f56f9c

…honGH-21517) * Move 'peephole' optimizations into compile.c and perform them directly on the CFG.

markshannon deleted the move-peephole-optimizations-to-cfg branch October 19, 2020 13:45

ezio-melotti mentioned this pull request Nov 14, 2022

Use :cpy-file: throughout the Devguide python/devguide#984

Merged

ezio-melotti mentioned this pull request Dec 9, 2022

Fix links to missing CPython files python/devguide#1003

Open

ezio-melotti mentioned this pull request Dec 25, 2022

Fix remaining broken links. python/devguide#1013

Merged

                   PyObject *freevars = NULL;
                   PyObject *cellvars = NULL;
-                  PyObject *bytecode = NULL;
+                  // PyObject *bytecode = NULL;

-                  Py_XINCREF(code);
-                  PyMem_Free(blocks);
-                  PyMem_Free(codestr);
+                  Py_INCREF(code);

                   for (i = 0; i < n; ++i) {
                       VISIT(c, expr, (expr_ty)asdl_seq_GET(s, i));
                       ADDOP_JABS(c, jumpi, end);
+                      basicblock *next = compiler_new_block(c);

+              optimize_cfg(struct assembler *a, PyObject *consts)
+              {
+                  for (int i = 0; i < a->a_nblocks; i++) {
+                      if (optimize_basic_block(a->a_reverse_postorder[i], consts)) {

+                              }
+                          }
+                      }
+                  }

bpo-41323: Perform 'peephole' optimizations directly on the CFG. by markshannon · Pull Request #21517 · python/cpython · GitHub

Uh oh!

Uh oh!

bpo-41323: Perform 'peephole' optimizations directly on the CFG. - #21517

bpo-41323: Perform 'peephole' optimizations directly on the CFG.#21517markshannon merged 8 commits intopython:masterpython/cpython:masterfrom markshannon:move-peephole-optimizations-to-cfgmarkshannon/cpython:move-peephole-optimizations-to-cfgCopy head branch name to clipboard

Conversation

markshannon commented Jul 17, 2020 • edited by bedevere-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

rhettinger commented Jul 17, 2020

Uh oh!

pablogsal Jul 17, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

bedevere-bot commented Jul 17, 2020

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

pablogsal Jul 17, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

pablogsal left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

markshannon commented Jul 20, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

bedevere-bot commented Jul 20, 2020

Uh oh!

markshannon commented Jul 21, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

bpo-41323: Perform 'peephole' optimizations directly on the CFG.#21517
markshannon merged 8 commits into
python:masterfrom
markshannon:move-peephole-optimizations-to-cfg

markshannon commented Jul 17, 2020 •
edited by bedevere-bot
Loading

pablogsal Jul 17, 2020 •
edited
Loading

pablogsal Jul 17, 2020 •
edited
Loading

markshannon commented Jul 20, 2020 •
edited
Loading