Expand description
Proposing a set of machine level changes, asking whether the target takes them, and either committing the set or dropping it.
Design: spec/optimizer/37-machine-level-optimization.md sections 37.2 and 37.3.
Section 37.3 quotes gcc/combine.cc on what a machine level rewrite is: substitute the earlier
instruction into the later one, ask the machine description whether the result is an instruction
this target has, install it if it is and put everything back if it is not. Section 37.2 reads
gcc/rtl-ssa/changes.cc and says the same thing about the arrangement rather than the rewrite,
which is that the propose, validate and commit belongs to one named component rather than to
each pass in its own words. This is that component.
§Nothing is written until the whole set is taken
A proposal holds what the instruction would become by value: the operands in a vector of their
own, the addressing mode as an mir::Amode rather than as a reference into the function’s
arena, the immediate as a number. So abandoning a set is dropping it and there is no undo to
get wrong. That is the difference between this and GCC’s, which edits the RTL in place and
keeps a list of what to put back, and it is available here because machine IR keeps an
instruction’s parts in arenas the proposal can stay out of until the last moment.
§Why a set rather than an instruction
Because the interesting rewrites are all of them or none. Folding an address into the three
instructions that read it is worth doing when the address computation goes, and folding it into
two of the three is worth nothing: the computation stays for the third, the address is worked
out twice, and the registers it reads are live across all three. crate::fold had that rule
written into it by hand and so would every pass after it.
§What the target is asked
MachineInsts is the whole of it, and every question in it is answered out of the same
description the allocator and the encoder read. An opcode this machine does not have, an
operand vector that is not the shape the opcode’s form says, an immediate on an instruction
that carries none, an addressing mode on one that has none, a scale this machine cannot write:
each of those is a refusal, and a refusal is the whole set’s.
What is checked beyond the target’s description is the part that is about the function rather
than about the machine. An instruction may be named once in a set, it has to still be in the
function, and taking an instruction out is refused while anything still reads what it wrote.
That last one is what the set is for, so Changes is the thing that knows it rather than
each pass.
§What the read counts are worth after allocation
Less, and they are still true. A count is how many operands in the function name a register,
and while machine IR is in SSA form that is the whole answer to whether anything reads what an
instruction wrote, because the register is written once. Once the allocator has run it is not:
%rax is written all over the function and a count of the reads of it is a count of the reads
of every one of those writes together.
What that costs is optimizations rather than correctness. A count of zero still means nothing
anywhere reads the register, so a removal the framework takes is a removal nothing was reading;
what it will not take is the many where the register is read further down about a different
write. So a pass that runs after allocation and removes instructions has to have its own reason,
which is why crate::copies has one and says what it is, and a pass that rewrites rather than
removes has the whole of the framework as usual.
§Reading a register somewhere else
A pass that takes an instruction out has to send whatever read it somewhere, and what that is
is one register in place of another in an instruction that is otherwise the instruction it
already was. That is Changes::rename, and it is a proposal of its own rather than a plan
with one operand changed, because the shape is what the description has something to say about
and a rename changes no shape. An instruction this machine has with one register in an operand
is one it has with another of the same class, so the class is the whole of what is checked.
It is also the only way to say it about the instructions whose operand vector the description
does not name, which on this machine is a call. How many registers a call passes is a fact about
the signature rather than about the instruction, so crates/rucc-target/src/x86_64/insts.rs
writes nothing down for it and a plan for one would be turned down for a shape nobody ever
claimed.
§The arguments an edge carries
Those are reads too, and they are in no operand vector. A block’s parameters are where the
values a block is reached with arrive, the arguments on the edge are where they come from, and
a pass sending every reader of a register somewhere else has these to send as well.
Changes::carry is that, and like a plan it is by value: what the edge would carry rather
than what to do to what it carries.
Structs§
- Changes
- A set of changes to one function, proposed together and taken together.
- Plan
- What an instruction would become.
- Reads
- How many times each register is read, kept across the commits of one pass.
Enums§
- Refusal
- Why the target or the function would not have a set.