Module bindgen::ir::analysis

Fix-point analyses on the IR using the “monotone framework”.

A lattice is a set with a partial ordering between elements, where there is a single least upper bound and a single greatest least bound for every subset. We are dealing with finite lattices, which means that it has a finite number of elements, and it follows that there exists a single top and a single bottom member of the lattice. For example, the power set of a finite set forms a finite lattice where partial ordering is defined by set inclusion, that is a <= b if a is a subset of b. Here is the finite lattice constructed from the set {0,1,2}:

                   .----- Top = {0,1,2} -----.
                  /            |              \
                 /             |               \
                /              |                \
             {0,1} -------.  {0,2}  .--------- {1,2}
               |           \ /   \ /             |
               |            /     \              |
               |           / \   / \             |
              {0} --------'   {1}   `---------- {2}
                \              |                /
                 \             |               /
                  \            |              /
                   `------ Bottom = {} ------'

A monotone function f is a function where if x <= y, then it holds that f(x) <= f(y). It should be clear that running a monotone function to a fix-point on a finite lattice will always terminate: f can only “move” along the lattice in a single direction, and therefore can only either find a fix-point in the middle of the lattice or continue to the top or bottom depending if it is ascending or descending the lattice respectively.

For a deeper introduction to the general form of this kind of analysis, see Static Program Analysis by Anders Møller and Michael I. Schwartzbach.

Structs

CannotDerive

An analysis that finds for each IR item whether a trait cannot be derived.

HasDestructorAnalysis

An analysis that finds for each IR item whether it has a destructor or not

HasFloat

An analysis that finds for each IR item whether it has float or not.

HasTypeParameterInArray

An analysis that finds for each IR item whether it has array or not.

HasVtableAnalysis

An analysis that finds for each IR item whether it has vtable or not

SizednessAnalysis

An analysis that computes the sizedness of all types.

UsedTemplateParameters

An analysis that finds for each IR item its set of template parameters that it uses.

Enums

ConstrainResult

Whether an analysis’s constrain function modified the incremental results or not.

DeriveTrait

Which trait to consider when doing the CannotDerive analysis.

HasVtableResult

The result of the HasVtableAnalysis for an individual item.

SizednessResult

The result of the Sizedness analysis for an individual item.

Traits

HasVtable

A convenience trait for the things for which we might wonder if they have a vtable during codegen.

MonotoneFramework

An analysis in the monotone framework.

Sizedness

A convenience trait for querying whether some type or id is sized.

Functions

analyze

Run an analysis in the monotone framework.

as_cannot_derive_set

Convert a HashMap<ItemId, CanDerive> into a HashSet<ItemId>.

generate_dependencies

Generate the dependency map for analysis