Module alias 

Alias analysis: whether two memory references can touch the same byte.

Design: spec/optimizer/08-alias-analysis.md, with the switch section 41.9 of spec/optimizer/41-correctness.md asks for.

The one question

There is one primitive and everything else is built on it. Given two memory references, can they touch the same byte. Every memory optimization documents 16, 17 and 27 will bring is gated on it, an answer that is too conservative costs performance quietly and forever, and an answer that is too aggressive miscompiles in the way that produces a bug report three years later from somebody whose program worked on every other compiler.

So the answer is an Answer, which is either Answer::May or a no carrying the layer that concluded it. Section 8.5 asks for that and it is the best decision in spec 9.4: a miscompilation from an alias bug is localised to one layer rather than bisected across the whole analysis, the layer statistics come for free, and a user asking why something was not optimized gets a real answer. It costs one byte in a return value that was going in a register anyway.

The layers, in the order they run

Section 8.2 lists six. This is the first five, and the order they run in is load bearing.

Two volatile accesses conflict, and that is checked before anything else. Not may conflict: they are treated as conflicting so that neither can be moved across the other, which is what volatile is for.

Distinct storage and provenance, layers 1 and 2, are one walk here because the IR names the object a pointer came from. origin chases a pointer back through ptr_add and bitcast to the alloca or the global_addr it started at, and two different objects never alias. GCC gets the same answer less directly, out of tracking base declarations through a tree walk. This layer answers a startling fraction of the queries real code asks and it is the only one -O1 needs.

Offsets, layer 4, run next and only for two references to the same object, and running them before the type-based layer rather than after is the whole of what makes union type punning work. Writing through one member of a union and reading another is two accesses to one object at overlapping offsets with unrelated types. It is undefined in ISO C, it is defined by GCC, an enormous amount of real C rests on it, and a layer that asked about the types first would answer no and miscompile all of it. GCC’s comment at gcc/tree-ssa-alias.cc:2461 says exactly this and rucc reproduces the ordering rather than the accident.

Escape, which section 8.4 counts as the cheapest interprocedural-flavoured fact there is: a local whose address never leaves the function is not the object some pointer this function cannot follow is pointing at, and it is not one a call can touch either.

restrict, layer 5, is two small numbers on the access and one comparison, which is all GCC’s is. See rucc_ir::Restrict, including the trap.

Type-based aliasing, layer 3, runs last of the five. Two accesses conflict when one of their type nodes is at or above the other in the metadata tree, so an access through char, whose node is the root, conflicts with everything. -fno-strict-aliasing is one condition in one place, Options::strict_aliasing, which is what section 41.9 means by the flag having to actually work.

Layer 6 is points-to, and it is not here. It is a module-wide fixed point rather than a fact the IR already carries, section 8.3 has an open question about which solver it should be, and section 8.6 is emphatic that provenance and points-to are different things that must not be confused. So Origin is provenance, there is no points-to type for it to be converted into, and the solver lands separately with the constraint generator split out from it the way GCC 16 split its own.

What the front end still owes this

Layer 3 is fed. rucc_lower::aliasing builds the tree and every load and every store an access through a C type becomes carries the node for that type, keyed on a canonical spelling rather than on the order the walk met it, which is what section 8.2 asks for so that document 35’s LTO does not silently gain disambiguations when two modules are merged. The tree is one level deep: char is the root and every other scalar hangs under it, so a struct member is not yet separated from the struct it is in. A member of a union carries the root rather than the node for its own type, which this layer would not have needed, since layer 4 runs first and settles it. It is there for the type plane, which has no layer 4, and it costs this layer nothing but a disambiguation between a union member and an unrelated object of a different scalar type.

Layer 5 is fed for the accesses that go through a restrict parameter, which is where the qualifier is nearly always written and which the front end works out. A restrict pointer declared inside a block does not carry one yet, which is tamnd/rucc#970, and neither does an access through a pointer that came out of memory, which is not a question about names and never will be.

Structs

Access

One memory reference: which bytes an instruction touches and what it says about them.

Alias

The analysis over one function.

Counts

How many queries each layer answered.

Escapes

Which of a function’s locals had their address leave it.

Options

What the command line turns off.

Enums

Answer

What the analysis answers.

Origin

Where a pointer came from, as far as this function can tell.

Reason

Which rule concluded that two references cannot touch the same byte.

Functions

keeps_address

Whether a use of a pointer at this operand leaves the address inside the function.

origin

Where a pointer came from, and how many bytes past the start of it the pointer is.