Compiler improvements

[iritkatriel]

@markshannon suggested that I look into improving the compiler's implementation.

There are two major objectives/problem areas. One is that the code evolved into a state where it is hard to understand/maintain.
The second problem is that the complexity is probably hurting the quality of the compiler's optimizations.

A few initial points:

The basicblock generation embeds jumps/exception handlers in the code and this complicates the CFG analysis later. We saw this in python/cpython#30544 (comment) where adding an explicit jump that should not have changed anything (because it was to the same target as the implicit jump) created a significant difference in the generated code.

Each basic block can have one exit, so we can store the jump target on the basicblock. Currently there could be more than one exception target, because SETUP_FINALLY et al. can appear in the middle of the block. But if we change this so that those opcodes must be at the beginning (or end?) of a basic block, then we can have the except_target on the basicblock struct as well (the stack of targets will be maintained by the compiler in the code generation stage rather than in the second pass that needs to read the opcodes). The generation of the exception table is simpler, and we no longer need the pass that replaces the virtual opcodes by NOPs (we can emit NOPs to begin with for tracing until that issue is resolved).

Currently all basic blocks are considered equal by the optimizations. If we add a hot/cold field to a basicblock then the optimizer can make better tradeoffs (like not inline code in cold block). basicblocks that belong to an exception handler are an example of a cold block. The hot/cold flag can also be used to decide about code layout - for instance cold blocks can be laid out at the end of the function. Currently code is laid out in the order in which the blocks are created, I believe.

[markshannon]

BPO issue for splitting up compiler: https://bugs.python.org/issue42926

[iritkatriel]

Following up on the suggestion on the bpo to change all jumps to be absolute, so that code can be moved around more easily.

I looked at the code, and it seems that the jump labels are resolved quite late, so maybe it's fine to leave the relative ones, as long as we do all code reorgs before this.

The complexity in this is related to jumps with extended_args (see the "awful hack" comment).

I got some stats from the top PYPI packages.

9,943 files
223,112 code objects
3,468,890 lines
11,372,743 opcodes
288,866 number of absolute jumps
88,280 number of relative jumps
16,081 number of absolute jumps with extended args
335 number of relative jumps with extended args

So about 5% of the absolute jumps have extended args.

Idea: We add an opcode for them, JUMP_EXTENDED which takes the target from a targets array on the code object, co_targets[arg].

That would simplify assemble_jump_offsets, because the code size won't change in it. In ceval it's the difference between constructing the target from multiple opcodes, vs a table lookup (+ a new opcode).

[iritkatriel]

Could inline caches have made a difference to backwards jumps? Wouldn't they have been backwards jumps before as well?

[iritkatriel]

I added a counter for jumps backwards, and there do seem to be many more of those now.

Current main:

15,128 files;
333,926 code objects;
5,336,282 lines;
44,619,617 opcodes;
2,169,508 total size of co_consts;
270,630 number of co_consts; 
447,685 number of absolute jumps; 
136,753 number of relative jumps; 
116,057 number of absolute jumps with extended args; 
4,781 number of relative jumps with extended args; 
74,772 number of absolute jumps backwards; 
10,897 number of absolute jumps backwards with extended args

Jan 28 checkout:

15,128 files;
333,926 code objects;
5,336,282 lines;
18,777,467 opcodes;
2,169,794 total size of co_consts;
270,630 number of co_consts;
447,685 number of absolute jumps;
136,751 number of relative jumps;
28,179 number of absolute jumps with extended args;
604 number of relative jumps with extended args;
74,772 number of absolute jumps backwards;
2,952 number of absolute jumps backwards with extended args

[iritkatriel]

I've recalculated the numbers because there was a bug in the first set. It makes more sense now - we have more extended args, but we don't have more backwards jumps.

[markshannon]

Of the absolute jumps, how many have deltas in range(-256, 256)?

My hunch is that using relative jumps, we wouldn't need as many EXTENDED_ARGs.

[iritkatriel]

If I didn't mess it up this time, then virtually all of them are short.

Now:

447,685 number of absolute jumps
440,798 number of absolute jumps with delta < 256

In Jan 28:

447,685 number of absolute jumps; 
446,815 number of absolute jumps with delta < 256

[markshannon]

It doesn't matter whether absolute or relative. What matters is that any jump can go backwards.
For example, FOR_ITER can only go forwards, which certain orderings of basic blocks illegal.

[iritkatriel]

After implementing the split between codegen and basic block construction, I managed to get multi-exit basicblocks to work with a few changes to the code (remove assertions that jumps are the last instruction in the block, chop off unreachable suffixes of blocks, etc).

I then realized that the refactor is not actually necessary for this - I can achieve the same effect in a much simpler way by making NEXT_BLOCK() be a noop, and letting the codegen stage produce the extended basic block directly. (Then we can just remove the NEXT_BLOCK() calls).

I don't currently see an advantage to separating codegen from basicblock construction, so I will go with this change for now, and if there is another reason for the refactor we can do it then.

[markshannon]

In my mind there are two advantages to separating code gen from block construction.

1. Labels are much easier to understand for anyone adding new language features or maintaining the front-end.
2. The optimizer will want to be able to form blocks according to its needs. It may want re-order the basic blocks and perform tail duplication before superblock formation, so it is best if the front-end doesn't attempt block formation.

[Btw, "superblocks" is the term used in academic literature for blocks with one entry and multiple exits. If a block has more than one exit, it isn't "basic".]

[iritkatriel]

Labels are much easier to understand for anyone adding new language features or maintaining the front-end.

If we remove the requirement to explicitly state where basic blocks start (with NEXT_BLOCK) calls then all we have is b = get_new_block() and then use_block(b) when you want to generate code into this block. I don't think it's less clear than lbl = new_label() followed by place_label_here(lbl).

The optimizer will want to be able to form blocks according to its needs. It may want re-order the basic blocks and perform tail duplication before superblock formation, so it is best if the front-end doesn't attempt block formation.

This is why I'm saying that I don't currently see an advantage for separating codegen from block formation. The point of what I'm doing now is to remove from the compiler code the NEXT_BLOCK() calls that explicitly mark basicblock starts, and instead make the compiler deduce the block structure from the instructions. Once we have that, changing what criteria (if any) the front end is using to create blocks, and chopping up instruction sequences (in codegen or later) into whatever blocks we need, is easy to do.

[arhadthedev]

But if we change this so that those opcodes must be at the beginning (or end?) of a basic block

Can SETUP_FINALLY and friends be replaced with properties of a basic block placed in its beginning, before any instruction?

[markshannon]

How would that help?

[arhadthedev]

1. It eliminates neccesity to check/verify if an instruction is placed correctly, in the end of a block.

2. Instructions are semantically allowed to be in any order. If some instruction doesn't have this flexibility, it just falls out showing a sign of something else. That's why I proposed to nail in-block values set by these instructions into a block header.

[markshannon]

I don't follow. SETUP_FINALLY is a branch, so it is always at the end of the a basic block.
It can't be placed incorrectly; it is the branch that defines the blocks, not the other way around.

[arhadthedev]

SETUP_FINALLY is a branch, so it is always at the end of the a basic block

After this clarification I got it so I retract my proposal. Initially I've thought that SETUP_FINALLY is not a branch but a setter for some internal register, being confused by "SETUP" (aka "prepare") part of SETUP_FINALLY.

[iritkatriel]

It turns out that we can remove NEXT_BLOCK without any other changes - I did this in python/cpython#31448.

This will create more empty basic blocks, where there is a jump followed by an explicit block (now it will create an empty implicit block after the jump, and then the explicit block). The empty blocks are discarded in the first step of the code generation, I don't know if it's worth trying to avoid creating them in the first place. I'd probably need to count/measure.

If we remove the implicit block creation, then we get superblocks. We need to update the cfg analysis code in a few places, where it assumes that jumps are the last instruction in a block. I have a patch that does this and all tests pass, except a couple of tests that check line numbers / trace output. However, putting aside the line number propagation issue for the moment, I don't think this makes anything simpler - it just makes us loop over the instructions in each block multiple times to find the jumps.

It's not currently clear to me what we want to get from a refactor, and what we need at each stage.

• As I explained above, basic blocks are better for the cfg analysis stage. Should we create superblock by merging the basic blocks, rather than the other way around?
• For block reordering - how would that work with the exception table, and why would superblocks help?
• For peephole optimisations - can we come up with some examples of optimisations that can work across jumps (i.e., at a granularity larger than a basicblock)?

[iritkatriel]

This will create more empty basic blocks, where there is a jump followed by an explicit block (now it will create an empty implicit block after the jump, and then the explicit block). The empty blocks are discarded in the first step of the code generation, I don't know if it's worth trying to avoid creating them in the first place. I'd probably need to count/measure.

I counted how many empty basic blocks are detected by the optimizer during "python -m test", and it went from 41798 to 107623. So x2.5.

[iritkatriel]

I made a change to delay creation of the implicit block until we know that we need it (when we try to add an instruction and we did not start using another block since the jump that made us want to add an implicit block). Now the total number of empty blocks is down to 35405, which is an improvement over the current compiler.

This makes sense because there are places where the current compiler can create empty implicit blocks, like:

NEXT_BLOCK()
VISIT_SEQ(c, stmt, s->v.For.orelse);
compiler_use_next_block(c, end);

If that orelse block is empty (say it's from a for loop that doesn't have an else) then the implicit block is empty. With my change, the implicit block will not be created because the use_next_block cancels it.

In summary: my change makes the code significantly simpler and insignificantly more efficient.

[iritkatriel]

For reference, this is the branch I mentioned above where NEXT_BLOCK becomes a NOOP and we create superblocks instead of basicblocks (all tests pass except a couple due to incorrect line numbers in the trace).

[markshannon]

I've made #297 to discuss the implementation of jumps.

[iritkatriel]

In the spirit of not calculating in the front end things that can be easily deduced in the backend, I made a PR to remove b_nofallthrough, b_return and b_exit from the basicblock struct.

Issue python/cpython#93444
PR python/cpython#93445