Struct CallGraph 

pub struct CallGraph { /* private fields */ }

The unit’s call graph, its condensation, and the order to walk it in.

Built once from the module, for the reason every module-level analysis here is built once: the answer belongs to the callee and a pass is handed one function.

Implementations

impl CallGraph

pub fn of(module: &Module, pic: Pic) -> Self

Builds the graph over everything the module can name.

The pic argument is what the link is going to be, and it decides which definitions may be interposed. See CallGraph::trusted_body.

pub fn nodes(&self) -> impl Iterator<Item = Node> + use<>

Every node, in the graph’s order.

pub fn len(&self) -> usize

How many nodes there are.

pub fn is_empty(&self) -> bool

Whether the module named nothing at all.

pub fn node(&self, name: Symbol) -> Option<Node>

The node for that name, if the graph has one.

pub fn name(&self, node: Node) -> Symbol

The name this node is.

pub fn func(&self, node: Node) -> Option<FuncId>

The module’s function of this name, whether or not it has a body and whether or not the body may be read.

For the attributes and the signature, which are what the declaration is there to say. To read the body use CallGraph::trusted_body instead.

pub fn trusted_body(&self, node: Node) -> Option<FuncId>

The body an analysis may derive facts from, and nothing when there is not one.

Section 34.1’s gate. Three things have to hold. The module has to define the function rather than only declare it. The linkage has to be one the linker will keep, which rules out weak and common, because either of those is a definition another object is allowed to win over. And the symbol has to be one the dynamic linker cannot interpose, which under -fPIC means hidden, protected or internal, unless the build promised -fno-semantic-interposition.

pub fn calls(&self, node: Node) -> &[Node]

The nodes this one calls directly, each once, in the order the body calls them.

pub fn reaches_unknown(&self, node: Node) -> bool

Whether this node can reach code the graph has no node for.

True for a body with a call through an address, inline assembly or a target intrinsic in it, true for an ifunc, and true for every node with no trusted body, since a declaration’s edges are not in this unit. An analysis that ignores this and reads only CallGraph::calls will decide that a call to printf reaches nothing.

pub fn address_taken(&self, node: Node) -> bool

Whether anything other than a direct call in this unit can reach this function.

A global_addr naming it in some body, a relocation naming it in some global’s image, or an ifunc resolving through it. What it is for is the exclusion section 34.5 states for parameter removal, “which is why a function whose address escapes is excluded”, and the same question the inliner asks before it considers a function to have no callers left.

It is not a statement about who calls it. A static function whose address is never taken and whose callers are all in this unit is the case every caller-to-callee analysis wants, and that is this being false together with the linkage being internal.

pub fn components(&self) -> &[Vec<Node>]

The strongly connected components, callees before callers.

Tarjan gives them in that order already, because it closes a component only once everything reachable from it has been closed, and the edges here point from a caller to a callee. A component of one node is the usual case and a component of more than one is recursion, either a function calling itself or a cycle of them calling each other.

pub fn component_of(&self, node: Node) -> usize

Which component this node landed in, as an index into CallGraph::components.

pub fn solve<T, S, F>(&self, start: S, transfer: F) -> Vec<T>

where T: Clone + PartialEq, S: Fn(Node) -> T, F: FnMut(Node, &[T]) -> T,

Walks the condensation callee before caller, settling each component before moving on.

start gives each node the value the walk begins at and transfer works out a node’s value from everything already known. The slice transfer is handed is indexed by Node::index and holds the current value of every node, which for a callee outside this component is its settled answer and for a callee inside it is wherever it has got to.

Inside a component the nodes are visited in ascending index and the round repeats until no value changes. A component of one node with no edge back to itself is not a cycle, so it is evaluated once and not checked again, which is the shape of almost every component in a real unit.

transfer has to be monotone over a lattice of finite height, in the sense that a value it produces from larger inputs is not smaller. That is what makes the round terminate, and it is the consumer’s to get right: section 34.5 is specific that the optimistic start this enables “is only sound after the fixpoint, so nothing may read the lattice mid-flight”.

Panics

In a checked build, if a component has not settled after a number of rounds far past what any lattice this is for could need. That is a transfer function that is not monotone rather than anything about the graph.

Trait Implementations

impl Clone for CallGraph

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for CallGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for CallGraph

fn default() -> Self

Returns the “default value” for a type.