Type Alias flowistry::infoflow::FlowDomain

pub type FlowDomain<'tcx> = RustcIndexMatrix<Place<'tcx>, LocationOrArg>;

Represents the information flows at a given instruction. See FlowResults for a high-level explanation of this datatype.

FlowDomain represents $\Theta$ that maps from places $p$ to dependencies $\kappa$. To efficiently represent $\kappa$, a set of locations, we use the bit-set data structures in rustc_index::bit_set. However instead of using a bit-set directly, we use the indexical crate to map between raw indices and the objects they represent.

The IndexMatrix maps from a Place to a LocationOrArgSet via the IndexMatrix::row_set method. The LocationOrArgSet is an IndexSet of locations (or arguments, see note below), which wraps a rustc_index::bit_set::HybridBitSet and has roughly the same API. The indexical crate has a concept of an IndexedDomain to represent the mapping from a set of values to the indexes those values — LocationOrArgDomain is the implementation for locations.

Note: reading dependencies from FlowDomain

In general, you should not use FlowDomain::row_set directly. This is because the FlowDomain does not have exactly the same structure as the $\Theta$ described in the paper. Based on performance profiling, we have determined that the size of the FlowDomain is the primary factor that increases Flowistry’s memory usage and runtime. So we generally trade-off making FlowDomain smaller in exchange for making dependency lookups more computationally expensive.

Instead, you should use FlowAnalysis::deps_for to read a place’s dependencies out of a given FlowDomain.

Note: arguments as dependencies

Because function arguments are never initialized, there is no “root” location for argument places. This fact poses a problem for information flow analysis: an instruction bb[0]: _2 = _1 (where _1 is an argument) would set $\Theta(\verb|_2|) = \Theta(\verb|_1|) \cup \{\verb|bb0[0]|\}$. However, $\Theta(\verb|_1|)$ would be empty, so it would be imposible to determine that _2 depends on _1. To solve this issue, we enrich the domain of locations with arguments, using the LocationOrArg type. Any dependency can be on either a location or an argument.