Split compiler into code-gen, optimizer and assembler.

@gvanrossum

BPO	42926
Nosy	@gvanrossum, @markshannon, @corona10, @brandtbucher, @iritkatriel

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = None
created_at = <Date 2021-01-13.15:03:23.987>
labels = []
title = 'Split compiler into code-gen, optimizer and assembler.'
updated_at = <Date 2022-02-03.22:11:26.525>
user = 'https://github.com/markshannon'

bugs.python.org fields:

activity = <Date 2022-02-03.22:11:26.525>
actor = 'iritkatriel'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = []
creation = <Date 2021-01-13.15:03:23.987>
creator = 'Mark.Shannon'
dependencies = []
files = []
hgrepos = []
issue_num = 42926
keywords = ['patch']
message_count = 2.0
messages = ['385033', '385043']
nosy_count = 5.0
nosy_names = ['gvanrossum', 'Mark.Shannon', 'corona10', 'brandtbucher', 'iritkatriel']
pr_nums = ['31116']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = None
url = 'https://bugs.python.org/issue42926'
versions = []

PR: gh-87092: do not allocate PyFutureFeatures dynamically #98913

PR: gh-87092: remove unused SET_LOC/UNSET_LOC macros #98914

PR: gh-87092: expose the compiler's codegen to python for unit tests #99111

PR: gh-87092: move all localsplus preparation into separate function called from assembler stage #99869

PR: gh-87092: Make jump target label equal to the offset of the target in the instructions sequence #102093

PR: gh-87092: compiler's CFG construction moved to after codegen stage #102320

PR: gh-87092: refactor assemble() to a number of separate functions, which do not need the compiler struct #102562

PR: gh-87092: create new opcode_utils.h file and move macros there, so they can be shared #102926

PR: gh-87092: move CFG related code from compile.c to flowgraph.c #103021

PR: gh-87092: move assembler related code from compile.c to assemble.c #103277

PR: gh-87092: fix refleak in peepholer test harness #103448

PR: gh-87092: fix a few cases of incorrect error handling in compiler #103456

PR: gh-87092: change assembler to use instruction sequence instead of CFG #103933

PR: gh-87092: update CODEOWNERS for split of compile.c to 3 files #103941

PR: gh-87092: Expose assembler to unit tests #103988

PR: gh-87092: avoid gcc warning on uninitialized struct field in assemble.c #104460

PR: gh-87092: avoid gcc warning on uninitialized struct field in assemble… #105243

PR: gh-87092: remove unused macros #105247

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:

Reduce memory use considerably (the size of instruction and block data structures would be about 60% of current)
Be faster (Less CFG management).
Produce better code (extended blocks are a better unit for optimization that basic blocks).
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.

pythongh-87092: create a 'jump target label' abstraction so that the …

gh-87092: create a 'jump target label' abstraction so that the compil…

gh-87092: compiler's codegen stage uses int jump target labels, and t…

pythongh-87092: use basicblock_last_instr consistently

gh-87092: use basicblock_last_instr consistently in the compiler (GH-…

pythongh-87092: use basicblock_last_instr consistently in the compiler (

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.

pythongh-87092: Expose assembler to unit tests

gh-87092: change assembler to use instruction sequence instead of CFG (…

pythongh-87092: Expose assembler to unit tests

Merge branch 'main' into supermon

gh-87092: Expose assembler to unit tests (#103988)

Merge branch 'main' into inlinecomp2

Merge branch 'main' into cached_property_docs

gh-87092: avoid gcc warning on uninitialized struct field in assemble…

Merge branch 'main' into supermon

Merge branch 'main' into cached_property_docs

pythongh-87092: avoid gcc warning on uninitialized struct field in as…

gh-87092: avoid gcc warning on uninitialized struct field in assemble… (

Navigation Menu

Repository navigation

Split compiler into code-gen, optimizer and assembler. #87092

49 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Split compiler into code-gen, optimizer and assembler. #87092

Description

Activity

markshannon commented on Jan 13, 2021

gvanrossum commented on Jan 13, 2021

iritkatriel commented on Sep 4, 2022

gvanrossum commented on Sep 5, 2022

iritkatriel commented on Sep 5, 2022

49 remaining items

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions