Module expand 

The IR rewrites the machine needs before a rule can be asked anything.

Design: spec/10-backend.md section 10.2, which is where the ordering comes from.

Everything else in this crate turns an instruction into instructions. There are two things a rule cannot do, and what is done about each of them instead is here.

The first is a new shape of control flow. A rule replaces a term with a term and the replacement has nowhere to put a block, so a construct that becomes blocks has to be rewritten before selection rather than during it. There is one such construct today and it is switch. Every other terminator leaves a block with one successor or two, which is what the block layout writes jumps for, and a switch leaves it with as many as the program had cases.

The second is arithmetic on what a rule matched. A rule may name a constant and pass it along, and it may not add to one or read it as something else, because the pattern language is a pattern language and giving it a way to compute would make a rule set a program the solver has to reason about rather than a table it can check a line of at a time. So an instruction whose lowering needs a value worked out from another one is rewritten here into instructions whose lowerings do not. Four of them are floats: a float constant, a negation, and the two conversions between a float and an unsigned integer. The other two move a block of memory, where the arithmetic is the offset of each word from the front of it.

Why a copy is a run of moves and not a call

A memcpy in the IR is not a call to memcpy. It is what the front end writes for a structure assigned, passed or returned by value, and a memset is what it writes for the part of an object an initialiser left unnamed, so a program with a struct in it reaches one almost at once and the size is a constant every time.

A constant size is what makes the moves the right answer. A four byte copy written as a call costs the call and the two arguments and gives back four bytes moved, which is more instructions than the move it replaced and slower than all of them. Every real compiler writes the moves under some threshold for that reason, and above the threshold writes the call, which is where this stops: the call needs a memcpy to exist, and a statically linked program has nowhere to get one from until the compiler runtime in tamnd/rucc#277 exists. So a copy larger than the threshold is refused by name rather than written wrong.

Why the chain a switch becomes is the backend’s and not the front end’s

What a switch should become is a target decision and not a language one. A chain of compares is right for three cases and wrong for two hundred, where the answer is a jump table, and wrong again for twenty spread over a million, where it is a binary search on the value. A front end that picked one would be picking for every target at once, and the IR would no longer hold what the program said. So the switch survives as far as here, and here is where it is given up.

What is written today is the chain, which spec/10-backend.md calls the version every compiler starts with. It is correct for any number of cases and it is slow for a large one. A jump table wants a read only section to put the table in and a relocation to reach it, and neither exists yet, so the chain is also the only one that could be written today.

Constants

UNROLL

The most moves a copy or a fill becomes before it is left alone for a call instead.

Functions

blocks_for

The blocks a chain of n cases needs beyond the ones the program already had.

bulk

Rewrites every bulk copy and bulk fill, into moves when that is worth it and into a call to the runtime when it is not.

floats

Rewrites the float instructions no rule can be written for, and leaves the rest alone.

switches

Rewrites every switch in the function into branches, and leaves everything else alone.