Module load 

A load of something the block has already read or written is that value, not a second read.

Design: spec/optimizer/16-gvn-and-pre.md section 16.2, which calls redundant load elimination the real prize of that document. Value numbering over arithmetic is worth less than people expect on C, because the front end does not generate the same expression twice and the programmer does not write it twice. Loads are different. p->x three times in a function is three reads of memory, and if nothing wrote through an aliasing pointer in between, two of them are work the program does not have to do.

The restricted version, and why this is it

Section 16.2 asks for two of these. The one at -O2 walks memory SSA back from each load to its clobbering definition, translates an address backwards through a block’s parameters, and sees through a memcpy. The one here is the other: same block only, no phi translation, no memcpy, and no memory SSA at all. That is the version the section says should be at -O1, and it says why: it catches the repeated p->x in one basic block, which is the majority of the opportunities, for a fraction of the machinery.

The two are not alternatives and this is not a stand-in for the other one. What it is is the part that can be written without an alias oracle, and the part whose cost is one walk over each block.

What it knows

One table per block, from an address to the value that address holds, thrown away at the end of the block because what reaches a block from its predecessors is the question this version does not ask. A store writes what it stored. A load that had to happen writes what it read. Either way the next load of that address is that value.

An address is one SSA value, compared by identity. Two pointers that are the same address by arithmetic and not by name are two addresses here, which costs opportunities and no correctness: an address computed twice out of the same parts is tracked twice and neither copy is forwarded to the other. What would give the two one name is value numbering over the arithmetic, which is the other half of document 16 and is not built. It costs more than it sounds like it should. a[i] = v; total += a[i]; written in C is a store and a load whose addresses are two separate runs of the same multiply and add, because the front end emits the subscript twice, so the shape this pass is most obviously for is one it cannot see until that lands.

What throws the table away

Anything that could write anywhere, and what that means is the alias oracle’s answer. A call, a store and a safety plane access each take out the entries the oracle says they may write and leave the rest standing. Everything else that touches memory, which is an atomic, a fence, a memcpy and anything else Opcode::touches_memory is true of, empties the table and records nothing. That predicate is the conservative one, so an opcode added to the IR later throws the table away rather than being quietly assumed harmless.

The plane access is there because of what it costs to leave it out. On a build with -fsafety=detect there is a meta_ or a check_ beside almost every access in the program, so a pass that empties the table at each of them has an empty table almost all of the time. None of them is a write to the address it names, which is what Opcode::touches_only_planes says and what the oracle now answers with.

The oracle arrived late and this pass is the first consumer it has ever had. Until tamnd/rucc#1467 a call and a store both emptied the whole table, because crate::alias wanted the module and a pass is handed one function. What the whole table cost was the second address: *p = v; total += *q; with two locals was refused even where the two cannot be the same object. It is not refused now.

What the oracle is worth here rests on the escape analysis more than on anything else in it. spec/optimizer/08-alias-analysis.md section 8.4 calls that the cheapest interprocedural flavoured fact there is, and it is what answers the ordinary case: a local whose address never leaves the function cannot be touched by any call in it, whatever the callee does.

A volatile access empties the table and records nothing either way. Whether a volatile store could be forwarded from is an argument about what volatile promises, and this pass does not need to have it.

The width, which is where the miscompilation would be

Section 16.6 names it as the single most likely wrong answer in that document: a load forwarded from a store of a different size. Section 09.5 has the three-way distinction, which is that a store covering the load exactly is the value, one covering it partially needs an extract, and one not covering it at all means the walk should continue.

This pass only ever takes the first of the three. The address has to be the same SSA value and the type has to be equal, which is the same width and the same reading of the bits, and anything else is left alone and counted. Two-way is what somebody writes first and it is right most of the time, which is what makes it worth being explicit that this is not that.

What it leaves behind

The load goes, rather than staying and having its result forwarded. crate::dce would not remove it: has_effects is true of every load, because a pass that removed one would need to know the address is dereferenced anyway, and this is the pass that knows it. The load being removed is safe for a reason nothing else in the pipeline has: something already read or wrote that exact address in this block, so the address is one the program dereferences whatever happens next.

The store stays. Removing a store that a later store covers is dead store elimination, which is document 17 and a different pass.

Structs

LoadForward

The pass.

Constants

NAME

What this pass is called, which the pipeline matches on to decide whether to build the module facts the oracle asks for.