Currently the compiler operates in three main passes:

Code-gen
Optimize
Assemble

The problem is that these passes use the same basic-block based CFG, leading to unnecessary coupling and inefficiencies.
A basic block CFG is awkward and error-prone for the code-gen, but not very efficient for the optimizer and assembler.

A better design would be for the code-gen to create a single linear sequence of instructions. The optimizer would take this and produce a list of extended-blocks for the assembler to consume.

code-gen -> (list of instructions) -> optimizer
optimizer -> (list of extended blocks) -> assembler

(Extended blocks have a single entry and multiple exits, unlike basic blocks which have a single entry and single exit)

This would:

1. Reduce memory use considerably (the size of instruction and block data structures would be about 60% of current)
2. Be faster (Less CFG management).
3. Produce better code (extended blocks are a better unit for optimization that basic blocks).
4. Be easier to maintain:
   a) Code-gen wouldn't have to worry about creating a correct CFG.
   b) The optimizer wouldn't need to handle empty blocks and track which basic blocks form an extended block.

Apart from the changes to the compiler, it would help if we made all branch instructions absolute (or have a backward dual) to accommodate free reordering of blocks in the optimizer.

SGTM. But I’m not the one who has to work with it.

I've been struggling to determine where to draw the line between the optimization stage and the assembly stage.

I think the solution is to add a fourth stage, between optimization and assembly, which prepares the CFG for assembly. It does all the normalisation of pseudo-stuff (instructions, targets, etc) into actual stuff (real opcodes, offsets, etc).

I don't know if there is a name for this stage in compilers parlance. We could call it "resolve instructions" or something like that.

It will include everything to do with:

(1) calculating stackdepth and except targets, replacing exception related opcodes by NOP
(2) moving cold blocks to end of block-list
(3) everything related to making sure line numbers are correct
(4) replacing pseudo-op jumps by actual jumps, including figuring out the direction and translating conditional backwards jumps into real jumps
(5) Finally, calculating the jump offsets

I don't know what that should be called either, but after this is done, are EXTENDED_ARG prefixes for jumps all set? I'm guessing, maybe make a similar list of responsibilities for the assembler? Because I'm not sure what those are.

The responsibility of the assembler is to turn a list of instructions to a code object:

(1) write the bytecode for the instructions
(2) create the lineno table
(3) create the exception table
(4) create a code object from those + metadata about the compilation unit.

Bytecode generation in stage (1) adds EXTENDED_ARG bytecodes when an instruction has a large oparg that requires it. The part that calculates jump offsets ((5) in the "resolve" list) takes into account the EXTENDED_ARGs when calculating block sizes.

The idea is that all the complex calculations would be in the new stage, and we can write tests for them. Then the assembler's job is to transform the instructions representation to what we need in the code object (but all the exception/jump targets, lineno, block order etc is already resolved before). Then we can write tests just for this translation stage.

SG. May the name can be inspired by “settle” or “tidy” or “clean”? Or maybe “resolve” is fine.

From the list above:
(1) calculating stackdepth and except targets, replacing exception related opcodes by NOP
(2) moving cold blocks to end of block-list
(3) everything related to making sure line numbers are correct
(4) replacing pseudo-op jumps by actual jumps, including figuring out the direction and translating conditional backwards jumps into real jumps
(5) Finally, calculating the jump offsets

And splitting (1) into 1x (exception targets) and 1s (stack depth calculation) and adding O (other cfg optimizations)

In a normal compiler, there are de-sugaring and semantic analysis passes after parsing, but before optimization.
(3) and (1x) belongs in there, as does computing except targets.

(2) belongs in the optimizer

(1s), (4) and (5) belong in the assembler.

Is this a good order of passes? 3, 1x, 2, O, 4, 5, 1s

I like the idea or moving some of the resolution to before optimisations. I think the order you suggest is fine, by and large. I’ll need to check whether all the line number business is safe to move up front. Some of it involves duplicating blocks,etc.

The lineno calculation needs to duplicate blocks that have no lineno but more than one predecessors. So it needs to come after mark_reachable, which is currently somewhere in the middle of the optimization stage. So that part of Mark's suggested reordering might be a problem. At least it needs to be done carefully.