evaluations

Evaluations

LLVM opt

Call type	Resolved %
static dispatch	100%
dynamic dispatch	0%
generic 1	100%
function pointer	0%
macro	100%
conditionally compiled	50% 2

LLVM opt is able to resolve static dispatch calls. On the other hand, it is unable to resolve function calls that have dynamic features, i.e., dynamic dispatch and function pointer calls.

Regarding calls that reside in conditionally compiled code blocks, only those that are inside code blocks whose condition evaluates to true are analyzed.

A potential limitation of LLVM opt is that it is not able to analyze the dependencies of a package. Of course, this can turn to an advantage if we want to analyze only the application code and ignore the dependencies (library) code.

¹ Generic calls (and generics in general) are monomorphized (concretized) during LLVM IR code generation. This way they are basically equivalent to static dispatch calls and are fully resolved by LLVM opt, which operates on the LLVM IR level. However, such an analysis decides to not take into account possible concretizations of generic functions that are not yet known due to the unavailability of the code that could potentially call these functions. In other words the analysis assumes all the codes that could possibly call these generic functions are available and can be analyzed.

² Conditional compilation conditions are evaluated by cargo before rustc's main compilation task begins. The result of 50% is not indicative, as in our benchmark each branch of a conditional compilation condition contains the same number of calls. Depending on the analyzed code the resolution percentage could be anywhere between 0% and 100%. The way LLVM opt works, it is unable to consider all conditional compilation branches and be sound under any compilation scenario.

MIRAI-CGG

MIRAI is a static analysis tool that performs abstract interpretation on Rust's mid-level intermediate representation (MIR). One of MIRAI's features is call graph generation (MIRAI-CGG), which was used to produce the benchmark results below. To see how to run MIRAI-CGG for this benchmark please see the included readme.

Below are the results of running MIRAI-CGG on this benchmark; MIRAI is able to resolve all call types besides conditionally compiled calls².

Call type	Resolved %
static dispatch	100%
dynamic dispatch	100% 1
generic	100%
function pointer	100%
macro	100%
conditionally compiled	50% 2

The call graphs generated by MIRAI-CGG can optionally be put through a series of graph reductions to remove extraneous call nodes (e.g., calls within the standard library). It is not necessary to apply any reductions to see the above results; they simply serve to make the graph more readable.

For the MIRAI-CGG-generated dot files (in mirai-cgg), we have applied three reductions (specified in the call graph config):

1. Fold: This removes calls associated with crates not specified in the "included_crates" field of the config. We have included all of the benchmark's crates.
2. Clean: This removes nodes from the graph that have no callers or callees.
3. Deduplicate: MIRAI-CGG associates an edge for every argument type of a call. This reduction removes all edges but one.

Note that nodes in the call graph are named using the call's DefId. The upshot of this is that names use an {impl#} naming scheme. This means that rather than seeing the name of an impl as found in the source code, one will see something like {impl#0}, meaning that the impl being referenced is the first impl defined in the crate. Looking at the definitions in the crate will allow one to find the given name of the impl.

¹ For non-generic dynamic dispatch calls, the generated call graph includes a node for the trait's method definition as well as a node for the concrete call itself.

² Conditional compilation conditions are evaluated by cargo before rustc's main compilation task begins, which is when MIRAI's analysis and call graph generation is performed. As such, MIRAI-CGG only has access to the calls compiled under the current `cfg` flags.