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 runs it puts together

Two of them. A value read out of memory and then used once, by arithmetic that this machine could have read it out of memory itself, which is loads:

  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.

And the same value written back where it came from, which is stores:

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

Three instructions become one, and this is what a C program writes as *p += x. The register in the middle goes the way the load’s register goes above, and so does the second addressing mode, which was the same address written down twice.

stores takes the same run with a constant in it, which is what a C program writes as *p += 1 and is the commoner of the two:

  movq 16(%rax), %rcx
  addq $1, %rcx          ->    addq $1, 16(%rax)
  movq %rcx, 16(%rax)

Nothing is left holding a register here at all. The instruction that comes out reads the place, adds the constant the instruction carries and writes the place, so the whole run costs the addressing mode and the constant and no operand the allocator has to answer for.

stores runs first. Its run is three instructions as the selector wrote them, and folding the load into the middle one first would leave the same run written a second way that the walk would then have to know about. Whatever it does not take is still a pair for loads.

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 program may have said what that order is. 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. The flag that says so reaches here now, so the walk could ask about each access one at a time, and it does not: stopping at every access rules the same thing out and costs almost nothing, since the load the arithmetic reads is nearly always the last access before it and so 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::swapped says.

Which comparisons

The comparisons are in FOLDS too, and they are the reason that field is a name rather than a flag. A comparison writes a byte neither source has a claim on, so both of its sources are free the way an addition’s second one is, and it still does not commute: the machine reads the right hand side out of memory and subtracts it from the left. What saves the other arrangement is that reading the two sides backwards asks the same question backwards, so a load feeding the left hand side becomes the same instruction with the condition turned over, and *p < x is x > *p. Equality and inequality turn over into themselves and the other eight go in pairs.

A comparison against a constant has one register rather than two and folds too, which is what a C program writes as if (*p == 7):

  movl 16(%rax), %ecx
  cmpl $7, %ecx          ->    cmpl $7, 16(%rax)

Nothing is arranged either way round here. The constant is on the instruction and has nowhere else to be, so the side the load filled is the left hand side and stays the left hand side, and the condition is the one the comparison already had. What is left holding a register is the byte the comparison sets, and the block layout usually takes that too.

What a volatile access gets

Nothing. Both walks stop at one, so volatile int *p; *p += x; comes out as the load, the arithmetic and the store, and volatile int *p; return *p + x; keeps its load.

What the flag says is that the access happens exactly once and is never moved or merged with another, and the first two of those were already true here: the walk in loads stops at any instruction that touches memory, so nothing ever passes an access, and no fold in this module turns one access into two or none. Merging is the one that was not. Reading a place, adding to it and putting it back is one read and one write of the address whether it is three instructions or one, so the counts the standard talks about are the same either way, and what the two differ on is whether the reading and the writing are one instruction. A device register whose memory does something when it is touched is where that difference is the whole point.

This is a place where the answer is the spec’s rather than the reference compiler’s. spec/optimizer/09-memory-ssa.md section 9.5 says a volatile access is never moved, never eliminated, never duplicated and never merged, and that last word is this. GCC 16 writes addl %esi, (%rdi) for the read modify write and cmpl $7, (%rdi) for a volatile compare, and GCC 13 writes three instructions and two for the same programs, so the merge is something GCC started doing rather than something it has always done. Both are conforming and neither changes how many times the address is touched. Taking the spec’s side costs an instruction on code that asked to be watched, which is the trade that document says to make.

The flag is on the machine instruction because rucc_mir::Flags carries it now and selection sets it from the load or the store it matched. Before that it could not be read here at all: a volatile access and an ordinary one were the same opcode over the same address, so there was nothing to stop at. That was tamnd/rucc#1302.

What makes the three one

The same three questions as the pair, and one more. The word the load read is read by the arithmetic and by nothing else, the answer the arithmetic wrote is read by the store and by nothing else, and nothing between the load and the store touches memory or writes a register the instruction that is left still reads. The run collapses onto the store, so the read of memory moves down the block to where the write already was, which is the move the memory rule is about.

The one more is that the two addressing modes have to name the same place. The same registers, the same scale, the same displacement and the same symbol is most of it, and the frame is the rest: the displacement of a local is a number crate::finish has still to add the frame’s own offset to, so two locals can be the same three registers and the same zero here and be two different places. The list itself is what tells those apart, and the entry the load was waiting on comes off the list when the run is joined, since the store is already waiting on the same one.

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.

Arithmetic against a constant, in either run. addq $1, 16(%rcx) is *p += 1, which is at least as common as *p += x, and the target has no form that carries an addressing mode and an immediate together. That is a third instruction description rather than a rule, the way the comparison above is.

Anything longer than the two runs above. Section 37.3 says GCC goes to four instructions, and the longer of the two here is three. What makes a fourth worth having is a rule set that has something to say about four, and the rule set here grows one measured entry at a time.

Structs

Bump

One arithmetic instruction against a constant that could work on memory, and the load and the store that would be the rest of the run.

Fold

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

Update

One arithmetic instruction that could work on memory rather than on a register, and the load and the store that would be the rest of the run.

Constants

WINDOW

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

Statics

BUMPS

The arithmetic against a constant that can work on memory in place on this machine.

FOLDS

The arithmetic a load can move into on this machine.

UPDATES

The arithmetic that can work on memory in place on this machine.

Functions

loads

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

stores

Puts every run that reads a place, computes on it and writes it back into the one instruction this machine has for all three, and gives back how many.