Module combine 

Putting a run of machine instructions together into the shorter run the machine has for it.

Design: spec/10-backend.md section 10.9, and spec/optimizer/37-machine-level-optimization.md sections 37.3 and 37.4.

Section 37.4 names this pass first of the ten it says are genuinely machine level, and says what shape it should be: a match over machine instructions in SSA form, inside one block, over a window of a few instructions, which is gcc/late-combine.cc rather than gcc/combine.cc. The reason for the smaller of the two is in the same section. Combine is fifteen thousand lines because it was written without def-use chains and had to find them again each time, and every RTL pass GCC has written since is on the SSA form it added later for exactly that.

Section 37.3 says what the pass does once it has found a run: substitute the earlier instruction into the later one, and ask the machine description whether what came out is an instruction this target has. That is crate::changes and this pass does not repeat any of it.

The run it puts together

A value read out of memory and then used once, by arithmetic that this machine could have read it out of memory itself:

  movq 16(%rax), %rcx
  addq %rcx, %rdx        ->    addq 16(%rax), %rdx

Two instructions become one. The register the load wrote is not written at all, which is one fewer value for the allocator to find a place for, and the bytes come down because an addressing mode costs what it costs whichever instruction carries it and the load’s own opcode byte goes.

It is the commonest pair in the machine IR this compiler writes. Counting adjacent instructions over the corpus at -O2, where the first writes what the second reads, the largest family by a long way is a move into arithmetic, and an addition at eight bytes is the largest single entry in it. What the pass gets over that corpus is 865 of these at -O2 and 845 fewer instructions once the allocator has had its say, with the difference between the two explained below.

Why no rule does it

The selector matches a term, and a term is one value. A load is a term and an addition is a term, and the pattern that would cover both is an addition with a load under it, which the selector does offer: it shows a rule the operands of its operands. What it cannot offer is the rest of the condition. Whether the load may move down to where the addition is depends on what is written between the two, and whether the load’s value is wanted anywhere else depends on the whole function. Neither is a fact about the term, so neither can be in a pattern.

When the load may move

The load stops being where it was and starts being part of an instruction further down the block, so everything between the two has to be something the load can pass. Two things are not.

Anything that touches memory, whether it reads or writes. A write is the obvious half: whether it writes the bytes this load reads is a question about two addresses, and telling two addresses apart is an analysis nothing below selection has, so the walk below stops at a store rather than guessing. MachineInsts::touches_mem is the target’s answer and MachineInsts::calls is the rest of it, since what a call does to memory is not in the instruction at all.

A read is the half that is easy to argue away and is the one that matters. Moving a read past a read changes the order two accesses happen in, and the machine IR does not say which accesses the program insisted on: a volatile read and an ordinary one are the same instruction with the same operands here, as crate::copies says at more length about the same problem. So volatile int a, b; return b - a; is two loads and a subtract, and folding the first of them into the subtract would read b before a when the program said otherwise. Stopping at any access at all is what rules that out, and it costs almost nothing: the load that the arithmetic reads is nearly always the last access before it, so it is still the one that folds.

What follows from that is the shape of the walk. There is one load in hand rather than a list of them, and it is always the last memory access there was.

Anything that writes a register the address reads. Machine IR is in SSA form until the allocator has run, so a virtual register cannot be written twice, but the stack pointer and the frame pointer are physical here and an address into the frame reads one of them.

When the load is wanted elsewhere

Exactly one instruction may read what the load wrote, and it has to be the one taking the load in. Reads is that count, kept across the commits of the pass the way crate::fold keeps it, and a count of one is the whole of the test because a virtual register is written once. Two readers and the load has to stay where it is, so putting it into one of them buys nothing and costs a second read of memory.

An argument an edge carries is a read like any other and is in no operand vector, which is the one place a count of this shape is easy to get wrong. Reads::of counts those, which is what keeps a load whose value leaves the block out of this.

Which arithmetic

FOLDS is the list, and it is a list rather than a rule about names because the two ends of each entry are instructions the target describes separately and the widths have to agree. A sixty four bit addition takes a sixty four bit load and nothing else: reading four bytes where the program asked for eight is a different instruction, and reading eight where it asked for four is three bytes nobody said were there.

The eight bit multiply is the one member of the family with no entry. This machine has no two-operand multiply narrower than sixteen bits, so an eight bit one is written as a thirty two bit imul and reads a register whose upper bits nothing looks at. A memory operand has no upper bits to not look at, so there is nothing to read there and the entry is left out.

Either source, when the operation does not care

An addition reads two registers and it is the second of them the memory operand replaces, because the first is the one the destination is tied to. Where the load feeds the first instead, the two sources are swapped first, which is a change to the instruction and not to what it computes as long as the operation commutes. Five of the six here do and subtraction does not, which is what Fold::commutes says.

The window

A load is carried forward at most WINDOW instructions and then dropped. The bound is what makes the pass cost a fixed amount per instruction rather than an amount that grows with the block, which section 37.3 records as GCC’s own answer: max-combine-insns is four and has been for decades.

It is also nearly all of it already at one. The measurement in WINDOW is that a bound of one finds 852 folds over the corpus and a bound of thirty two finds 865, which follows from the rule above about memory rather than from anything about how the selector writes code: the load that folds is the last access to memory before the arithmetic, and the last access before it is usually the instruction in front of it. The window is there to bound the walk and it earns thirteen folds along the way.

Where it costs something

A fold takes out exactly one instruction, so the number of folds and the number of instructions saved should be the same number, and they are not: 865 folds against 845 instructions over the corpus at -O2, and 1609 against 1444 over the SQLite amalgamation. The gap is the allocator.

Taking the load out changes which values are live where, so the allocator makes different choices, and a few of them are worse. Two programs in the corpus come out two instructions longer at every level above -O0, both for the same reason: the folded addition is given a callee saved register while a caller saved one was free, which buys a push, a pop and a copy for a value that dies before the next call. That is the allocator preferring the wrong end of its own list rather than anything this pass did, and it is worth fixing where it is rather than worth not folding over.

The trade is the other thing the gap is, and it is a real one rather than an accounting error. Two instructions become one and the one that is left both reads memory and computes, so it is two operations in one slot rather than one, which a machine that issues several instructions at once may not want. The measurement that settles it is run time rather than instruction count, and section 38.6’s scheduler is where that argument belongs, since a scheduler is the pass that can see whether the slot was going to be used.

What it does not do yet

A comparison. This machine compares against memory as readily as it adds to it, and the reason there is no entry for one is that a comparison here is one opcode holding a compare and the byte behind it, so the memory form is a third instruction rather than a second and the target has to describe it before this can write it.

A store the arithmetic feeds. addq %rax, 16(%rcx) is the same saving again on the other side and this machine has the instruction, as rucc_target::x86_64::Form::Rmw already. What it needs is the reverse of the walk below, a store looking back at what wrote the value it is storing, and that is a second entry in the list rather than a second pass.

Anything that is not a pair. Section 37.3 says GCC goes to four instructions, and the run this finds is two. What makes three worth having is a rule set that has something to say about three, and the rule set here grows one measured entry at a time.

Structs

Fold

One arithmetic instruction that could read its second source out of memory, and the load that would fill it.

Constants

WINDOW

How far a load is carried looking for the instruction that takes it in.

Statics

FOLDS

The arithmetic a load can move into on this machine.

Functions

loads

Puts every load that can move into the arithmetic that reads it, and gives back how many.