Expand description
Making an assignment true in the function it was worked out for.
Design: spec/10-backend.md section 10.4.
crate::assign says where every value goes and touches nothing. This is the other half: every
operand is rewritten to the place its value was given, and the moves that the places do not
already say are collected. After it the function names no virtual register and no block asks
for anything, which is the point at which machine IR stops being in SSA form and starts being
something an encoder could read.
§Why the moves are handed back rather than written
A move is an instruction, and an instruction has an opcode, and an opcode belongs to a target.
spec/10-backend.md section 10.8 says no pipeline crate holds target specific code, so this
crate is not the one that can write x64.mov. What it hands back is an Edit: a move
between two places, the class it is in, and where in the function it goes. rucc-codegen turns
each one into whatever its target moves a register with, which for a value on the stack is a
load or a store rather than a move at all.
The edits at any one place are in the order they have to be made in. That matters in two places: a spilled operand is read into a scratch register before the instruction that wants it, and a two address instruction’s copy has to come after that read, because what it is copying may be the thing that was just read in.
§How many scratch registers one instruction wants
Two of a class, and a target holds two of each back for exactly this. The instruction that asks for most reads two values and writes a third with nothing of the three in a register, and the arithmetic works out because the two reads are what use the two scratch registers and the answer is written back into one of them. Writing over it destroys nothing, since it holds a copy of a value whose home is a stack slot and the instruction has already read it, and the answer is stored away from it afterwards. Giving the answer a scratch register of its own would want a third, which a program with enough live values around a call reaches, and that was issue #350.
Which register the answer goes back into depends on what wrote it. A two address instruction
writes the register the operand it reuses was read into, because that is what two address means.
A three address one, which is lea and the compare and set pairs, writes a register that is
none of its operands, and there the answer takes the first scratch register of the class again:
the reads are done by the time the write happens, so the two uses of that register do not meet.
Counting the two jobs in one running number is what made a three address instruction with every
end on the stack ask for a third register and abort, which was issue #726.
It is only a scratch register the answer may have either way. Where the operand a two address instruction reuses is in a register the assignment gave out, the value in it may be wanted after the instruction, and the assignment only lets one be written over when it is not, which it says by giving the answer that register in the first place. So the answer takes a scratch register there and the two address copy fills it. That one is filled in front of the instruction rather than by it, so it cannot share with a read, and the count still comes to two, because an operand that is in a register is not holding a scratch register.
Deciding either way needs to know where the operand it reuses went, so an operand that reuses another and has no register of its own is placed in a second pass over the operands.
The count is per class. An instruction reading a spilled value out of each of two files wants the first register of each, since a class holds its own back and nothing on the instruction is in the other’s.
§What a fixed register turns into
A move each way. The assignment deliberately gave the value some other register, so a division
whose dividend has to be in rax gets a move into rax in front of it and a move out of rax
behind it. That is the cost of the rule the assignment follows, and it is the rule that keeps
the -O0 allocator one pass.
§What an edge turns into
The moves that write the block’s parameters, in an order they can be made in one at a time,
which is what crate::moves is for. Where they go depends on the shape of the edge. A block
with one successor puts them at its own end, in front of the branch it finishes with, and a
block with several puts them at the start of the block the edge goes to, which is safe exactly
because that block has no other predecessor. An edge that is critical has neither place to put
them and has to have been split before allocation ran, which this checks rather than assumes.
An edge is also the one place a value can be asked to go from one stack slot to another, which happens when a spilled value is passed to a parameter that was itself spilled. No machine here has that instruction, so the move goes through a register, and the register is a second scratch rather than the one the ordering may be holding a value in for the length of a cycle. Expanding it here rather than leaving it to the target is the same decision as everything else in this file: a move through a temporary is a fact about places, and which register is free to be the temporary is a fact only this crate has.
Structs§
- Edit
- One move the places did not already make true.
Enums§
- At
- Where an edit goes.
Functions§
- rewrite
- Rewrites a function to the places it was given, and says what moves are still wanted.