Repository navigation
Split compiler into code-gen, optimizer and assembler. #87092
Description
| 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 = []Metadata
Metadata
Assignees
Labels
No labels
Activity
markshannon commentedon Jan 13, 2021
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:
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.
gvanrossum commentedon Jan 13, 2021
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 (
iritkatriel commentedon Sep 4, 2022
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
gvanrossum commentedon Sep 5, 2022
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.
iritkatriel commentedon Sep 5, 2022
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.
49 remaining items
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
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… (