Expand description
Who calls whom in one translation unit, which components they form, and the order to walk them.
Design: spec/optimizer/34-ipa.md sections 34.1 and 34.6. Section 34.6 puts this first and
prices it at roughly five hundred lines: “A callgraph over the unit’s functions, with direct
edges from calls and a flag for indirect ones; visibility computed per symbol per 34.1; the
condensation and its topological order; and an SCC-iterating driver that a pass supplies a
transfer function to.” Section 34.1 adds why the order is the one it is: “The traversal order is
the callgraph’s condensation in topological order, and every pass in this document is either
callee-to-caller or caller-to-callee over it, with strongly connected components iterated to a
fixpoint.”
Nothing in the pipeline reads this yet. It is here on its own because it is the walk every interprocedural analysis in document 34 performs, and a walk is much easier to argue about before there is an analysis sitting on top of it to argue about at the same time.
§Why the components rather than a loop until nothing changes
crate::nofree already does this walk by hand, and what it does is go round every body in the
module until no answer moves. That is correct and it is what a first one of these looks like, and
it costs a round over the whole unit for every step an answer has to travel. A chain of callers a
hundred deep is a hundred rounds over every function in the file, and the SQLite amalgamation has
two and a half thousand of them.
Over the condensation it is one visit per component in an order that settles each of them before anything that calls into it, so an answer never has to travel between components twice. The only iteration left is inside a component, which is exactly where recursion is, and a component is almost always one function. That is not a micro-optimization, it is the difference between the analysis being quadratic in the unit and being linear in its edges, which is the thing section 34.5 warns about under “The analysis is quadratic on a large unit”.
§What a node is
A node is a name, not a body. Every function the module has, defined or only declared, gets one,
and so does every name some body calls that the module has no function of any kind for. That last
kind exists because rucc-safety emits calls to names it interns without adding a function to
hang them on, which is what tamnd/rucc#810 was about, and a graph that only knew about the
functions would have no node to put those calls on and would quietly drop the edge.
An alias gets a node as well when what it aliases is a function this module has, because a call to the alias is a call to that body and an analysis walking callee to caller needs the edge to see it. An ifunc does not get that edge: what it resolves to is chosen at load time and is not something this module can name, so the ifunc’s node reaches the unknown and the resolver it names is recorded as having had its address taken, because the dynamic linker is going to call it and no edge here says so.
§Trusting a body, which is section 34.1’s gate
“Every fact derived from a function body is conditional on the body being the one that runs.”
CallGraph::trusted_body is the only way to reach a body through this graph and it hands one
back only when three things hold: the module has a definition, the linkage is not one the linker
may throw away in favour of another object’s, and the symbol is not one the dynamic linker may
interpose. That is the same test crate::nofree applies and it is the same test for the same
reason, and it is here so that the next analysis does not write it a third time.
§Reaching the unknown
CallGraph::reaches_unknown is one bit per node and it says the node can get to code this
graph has no node for. It is set for a call through an address, for inline assembly, and for a
target intrinsic, which is the “flag for indirect ones” section 34.6 asks for. It is also set for
every node with no trusted body at all, which is the part worth saying out loud: a declaration
calls nothing as far as this graph can see, and an analysis that read the edges alone would
conclude that a call to printf reaches nothing and is therefore harmless. Folding that into the
same bit means the safe reading is the one a consumer gets without having to remember anything.
§Determinism
Spec 03 requires the same input to give the same output, and this is one of the places where it is easy to lose by accident. Nodes come out in the order the module has its functions, then its aliases, then in the order the bodies first mention a name that had no node. Edges come out in the order the body makes the calls, with a repeat of the same callee dropped. A component’s nodes are sorted by node index, and a component is iterated in that order. Nothing here iterates a hash map: the one that is here answers “which node is this name” and is never walked.
§Where this lives
Section 34.1 names a crate rucc-ipa once and document 15’s crate table has no such crate, so
there is nothing to be consistent with. Every module-level analysis this compiler has is already
in rucc-opt, which is crate::nofree, crate::heap, crate::params,
crate::extents, crate::image and crate::outside, and the pipeline that would build
this is in rucc-opt too. A crate holding one file that only rucc-opt calls is a layer
boundary that buys nothing today. crate::nofree records the same kind of deviation for the
same kind of reason.