This implements a subset of partial evaluation (specifically, constant propagation), using a technique described for our type propagation in ourTier 2 interpreter report and abstract interpretation over uops.

The main goal of upstreaming this PR is to set up the infrastructure for optimization passes of CPython uops. With constant propagation, turning global loads or attribute loads to constants at the region formation phase will open up further optimizations in subsequent passes. This PR also makes CPython uops ready for type propagation, thus allowing wide-scale typed operations.

Features:

An automatically generated abstract interpreter from the interpreter DSL.
Abstract interpretation of uops.
~~Partitioning of values on the stack and locals into static/dynamic using the concept of "partitions of nodes".~~
~~Introduces the concept of "pure" operations, and what can be ascertained about them.~~
~~Constant propagation purely via abstract interpretation of bytecode, with no requirement for SSA or AST.~~
~~An optimization pass to remove redundantSAVE_IPs after partial evaluation.~~
~~Jump target/instruction numbering, which allows us to freely relocate jump targets/instructions, as a final pass will fix them up.~~

Example:
We have the following test case.

        def testfunc(loops):            num = 0            while num < loops:                x = 0                y = 1                z = 2                a = x + y + z + x + y + z + x + y + z                num += 1            return a

This is now essentially simplified down to:

        def testfunc(loops):            num = 0            while num < loops:                x = 0                y = 1                z = 2                a = 9                num += 1            return a

Which roughly halves the trace length.

TODO:

Uselltrace convention commonly seen in rest of the uops codebase.
Cleanup.

Issue:Tier 2 abstract interpreter for the optimizer #107557

Fidget-Spinnerand others added30 commits

August 2, 2023 17:52

pythongh-107557: Tier 2 abstract interpreter barebones

d20fbb8

📜🤖 Added by blurb_it.

2aeea51

Copy Guido's input and output code, and fix build

1a728ab

Co-Authored-By: Guido van Rossum <gvanrossum@users.noreply.github.com>

fix separator

17fccbc

credit Jules

a1da69d

add jules to co-authors

b458e17

Co-Authored-By: Jules <57632293+juliapoo@users.noreply.github.com>

add pycore_optimizer.h to headers in makefile

f81f888

fix: remove whitespace

0020320

fix make smelly

1f93072

fix: build

dac63e3

fix wrong symbol

e62e015

ignore static globals check for abstract interpreter

a7f654c

Merge remote-tracking branch 'upstream/main' into abstract_interpreter

f4040b8

merge Guido's changes

ec58145

remove unused stuff

4292767

Turn on the abstract interpreter

fdcca90

Merge remote-tracking branch 'upstream/main' into abstract_interpreter

5110fb9

Merge remote-tracking branch 'origin/abstract_interpreter' into parti…

9f443a2

…tion_algo

(leaky) data structures for constant propagation

7632ed1

(with cycles) try to fix the type prop

0d0c4c4

Co-Authored-By: Jules <57632293+juliapoo@users.noreply.github.com>

fix: cycles

4c8953e

Co-Authored-By: Jules <57632293+juliapoo@users.noreply.github.com>

cleanup

3bd36fa

Co-Authored-By: Jules <57632293+juliapoo@users.noreply.github.com>

Fix+Refactor: Handling of root nodes in special-cased type prop (#40)

229097f

* Fix+Refactor: Handling of root nodes in special-cased type prop* Style: Removed trailing space

partially partially evaluate

ca0fab7

rename vars

68c684f

fixx off by one

46c5777

partial eval working for real this time

b839ee4

Fix: InconsistentAbstractInterpContext used in `PARTITIONNODE_OVER…

6ecf3d2

…WRITE` and mis-port of `PARTITIONNODE_OVERWRITE` (#41)* Fix: Inconsistent AbstractInterpContext used in PARTITIONNODE_OVERWRITE and typo in PARTITIONNODE_OVERWRITE* Style: Removed whitespace

fix test, refactor, bugfix

b6eeb25

re-compute jump offsets and targets

d5cceb9

gvanrossum reviewed

Aug 14, 2023

View reviewed changes

Copy link

Member

gvanrossum left a comment

Choose a reason for hiding this comment

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

Here are some nits for everything except optimizer_analysis.c

Lib/test/test_capi/test_misc.py OutdatedShow resolvedHide resolved

Makefile.pre.inShow resolvedHide resolved

Python/bytecodes.c OutdatedShow resolvedHide resolved

Include/internal/pycore_uops.h Outdated

Comment on lines 14 to 15

		int32_topcode;
		int32_toparg;

Copy link

Member

gvanrossumAug 13, 2023

Choose a reason for hiding this comment

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

I'm curious about this change. Are you using negative opcodes or opargs? IIUC oparg really is treated as a 32-bit unsigned int in ceval.c and bytecodes.c.

Copy link

MemberAuthor

Fidget-SpinnerAug 14, 2023•
edited
Loading

Choose a reason for hiding this comment

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

I'm using both negative ints and opargs, but only during the analysis phase. They are converted back to unsigned after the last pass.

For all intents and purposes outside of the optimizer pass, they can be treated as unsigned.

Include/internal/pycore_uops.h OutdatedShow resolvedHide resolved

Tools/cases_generator/generate_cases.py OutdatedShow resolvedHide resolved

Tools/cases_generator/generate_cases.py

		ifinstr.is_viable_uop()andinstr.namenotinSPECIALLY_HANDLED_ABSTRACT_INSTR:
		self.out.emit("")
		withself.out.block(f"case{thing.name}:"):
		instr.write(self.out,tier=TIER_TWO)

Copy link

Member

gvanrossumAug 13, 2023

Choose a reason for hiding this comment

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

Note that ingh-107760 I'm removingInstruction.write altogether.

Tools/cases_generator/generate_cases.py

Comment on lines +707 to +708

		a.write_abstract_interpreter_instructions(args.abstract_interpreter_cases,
		args.emit_line_directives)

Copy link

Member

gvanrossumAug 13, 2023

Choose a reason for hiding this comment

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

Heh, I noticed this too. :-)

Tools/cases_generator/generate_cases.py OutdatedShow resolvedHide resolved

gvanrossum reviewed

Aug 14, 2023

View reviewed changes

Copy link

Member

gvanrossum left a comment

Choose a reason for hiding this comment

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

Looking at optimizer_analysis.c I am wondering if that code is ready for prime time. Maybe there's a way that we can add most of theinfrastructure code (that is likely relatively stable) without adding any of the code that's still under heavy development? E.g. I'm fine with the extra optimizer argument and generating a new .c.h file, and even with having a dummy optimizer_analysis.c file, but I worry that the latter will undergo many serious changes that will cause a lot of churn.

It is also by far the largest amount of code, and of a highly algorithmic nature that I won't be able to review meaningfully until you and I have sat down for a review of the algorithm. Compare this to most of the Tier 2 work so far, which is mostly just engineering -- e.g. splitting bytecodes into guard and action uops that use at most one cache entry feels more like a refactoring, and the superblock generator and interpreter are also mostly just hard work, not deep thinking.

Copy link

MemberAuthor

Fidget-Spinner commentedAug 14, 2023•
edited
Loading

Yeah I'm concerned with the changes in the analysis file as well. The other problem I also thought of is that new uops (especially calls) would need modifications to the analysis file and that requires deep understanding of the algorithm.

Would you be amenable if I guarded the optimization pass behind a define that is by default off? That way we can still experiment with things but not impede other efforts.

Copy link

Member

gvanrossum commentedAug 14, 2023

That would totally work. Can you update the PR?

Fidget-Spinner added4 commits

August 14, 2023 19:56

address review

3c08ebe

regen

d5f16be

and env var to block tests

1e61c49

regen again

6c24b49

Copy link

MemberAuthor

Fidget-Spinner commentedAug 14, 2023

I've decided to use an env var instead, because it's easier for testing. With a define, we would not be able to run any tests except with a custom branch of cpython.

fix generated files

2be404d

gvanrossum reviewed

Aug 14, 2023

View reviewed changes

Python/bytecodes.c Outdated

		// Inserts TOS at position specified by oparg
		PyObject*tos=TOP();
		for (inti=1;i<oparg+1;i++) {
		stack_pointer[i]=stack_pointer[i-1];

Copy link

Member

gvanrossumAug 14, 2023

Choose a reason for hiding this comment

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

Hm, doesn't this repeat the first stack element over and over? Maybememmove() would do what you want? (It is supposed to be good at overlaps, unlikememcpy().)

Copy link

MemberAuthor

Fidget-SpinnerAug 15, 2023•
edited
Loading

Choose a reason for hiding this comment

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

Woops yeah thanks for catching this! Forgot to negate the indexes.

Python/bytecodes.c OutdatedShow resolvedHide resolved

Python/executor_cases.c.h OutdatedShow resolvedHide resolved

Tools/cases_generator/generate_cases.py

Comment on lines 645 to 650

		caseparsing.InstDef():
		instr=AbstractInstruction(self.instrs[thing.name].inst)
		ifinstr.is_viable_uop()andinstr.namenotinSPECIALLY_HANDLED_ABSTRACT_INSTR:
		self.out.emit("")
		withself.out.block(f"case{thing.name}:"):
		instr.write(self.out,tier=TIER_TWO)

Copy link

Member

gvanrossumAug 14, 2023

Choose a reason for hiding this comment

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

I wonder if you even need theAbstractInstruction class. Maybe you could just call a different method onInstruction?

Copy link

MemberAuthor

Fidget-SpinnerAug 15, 2023

Choose a reason for hiding this comment

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

I was thinking of how we might need to expand on it more in the future, so a separate class might be better.

Copy link

Member

gvanrossumAug 15, 2023

Choose a reason for hiding this comment

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

When that happens in the future you can refactor the code. Until then, I recommend less code.

As you may have noticed this code gets refactored a lot. :-) It's easy because the generator is not a public API -- all we care about is whether it generates a handful of files correctly from bytecodes.c at build time. But I worry about copying and pasting code, because that's harder to refactor.

Python/optimizer.c OutdatedShow resolvedHide resolved

Address review

29e255d

Copy link

MemberAuthor

Fidget-Spinner commentedAug 15, 2023

Guido, thanks for the multiple rounds of reviews. It's a gigantic PR, and I truly appreciate your time on this!

gvanrossum reviewed

Aug 15, 2023

View reviewed changes

Copy link

Member

gvanrossum left a comment

Choose a reason for hiding this comment

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

I'm still concerned that we have that 1000+ line experimental file. I think requiring you to have a branch with just the changes to that file in it makes sense until it all works reliably. (For comparison, Brandt's copy-and-patch is also still a branch.)

Python/executor_cases.c.h Outdated

		caseINSERT: {
		PyObject*top;
		PyObject**stuff;
		PyObject**stuff1;

Copy link

Member

gvanrossumAug 15, 2023

Choose a reason for hiding this comment

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

Hm, the warnings are kind of annoying -- let's see if we can rid of those.

Fidget-Spinner added2 commits

August 15, 2023 13:30

fix up INSERT

3c44117

remove experimental parts

b758b47

Copy link

MemberAuthor

Fidget-Spinner commentedAug 15, 2023

I'm still concerned that we have that 1000+ line experimental file. I think requiring you to have a branch with just the changes to that file in it makes sense until it all works reliably. (For comparison, Brandt's copy-and-patch is also still a branch.)

Got it. I removed the experimental optimizer part and pushed it to another branch.