Home Explore Blog CI



rustc

2nd chunk of `src/mir/dataflow.md`
88f19aefca541fdeb193c8da390a00284bc6d449677c251a0000000100000d19
multiple effects for each statement makes it difficult for consumers to know
where they should be looking. However, the "before" variants can be useful in
some scenarios, such as when the effect of the right-hand side of an assignment
statement must be considered separately from the left-hand side.

### Convergence

Your analysis must converge to "fixpoint", otherwise it will run forever.
Converging to fixpoint is just another way of saying "reaching equilibrium".
In order to reach equilibrium, your analysis must obey some laws. One of the
laws it must obey is that the bottom value[^bottom-purpose] joined with some
other value equals the second value. Or, as an equation:

> *bottom* join *x* = *x*

Another law is that your analysis must have a "top value" such that

> *top* join *x* = *top*

Having a top value ensures that your semilattice has a finite height, and the
law state above ensures that once the dataflow state reaches top, it will no
longer change (the fixpoint will be top).

    state. Each basic block's entry state is initialized to bottom before the
    analysis starts.

## A Brief Example

This section provides a brief example of a simple data-flow analysis at a high
level. It doesn't explain everything you need to know, but hopefully it will
make the rest of this page clearer.

Let's say we want to do a simple analysis to find if `mem::transmute` may have
been called by a certain point in the program. Our analysis domain will just
be a `bool` that records whether `transmute` has been called so far. The bottom
value will be `false`, since by default `transmute` has not been called. The top
value will be `true`, since our analysis is done as soon as we determine that
`transmute` has been called. Our join operator will just be the boolean OR (`||`)
operator. We use OR and not AND because of this case:

```rust
# unsafe fn example(some_cond: bool) {
let x = if some_cond {
    std::mem::transmute::<i32, u32>(0_i32) // transmute was called!
} else {
    1_u32 // transmute was not called
};

// Has transmute been called by this point? We conservatively approximate that
// as yes, and that is why we use the OR operator.
println!("x: {}", x);
# }
```

## Inspecting the Results of a Dataflow Analysis

Once you have constructed an analysis, you must call `iterate_to_fixpoint`
which will return a `Results`, which contains the dataflow state at fixpoint
upon entry of each block. Once you have a `Results`, you can inspect the
dataflow state at fixpoint at any point in the CFG. If you only need the state
at a few locations (e.g., each `Drop` terminator) use a [`ResultsCursor`]. If
you need the state at *every* location, a [`ResultsVisitor`] will be more
efficient.

```text
                         Analysis
                            |
                            | iterate_to_fixpoint()
                            |
                         Results
                         /     \
 into_results_cursor(…) /       \  visit_with(…)
                       /         \
               ResultsCursor  ResultsVisitor
```

For example, the following code uses a [`ResultsVisitor`]...


```rust,ignore
// Assuming `MyVisitor` implements `ResultsVisitor<FlowState = MyAnalysis::Domain>`...
let mut my_visitor = MyVisitor::new();

// inspect the fixpoint state for every location within every block in RPO.

Title: Convergence and Inspecting Dataflow Results
Summary
This section discusses the importance of convergence to a fixpoint in dataflow analysis and illustrates it with laws governing bottom and top values. It then provides a brief example of a dataflow analysis to detect `mem::transmute` calls, using a boolean domain and the OR operator for joining states. Finally, it outlines how to inspect the results of a dataflow analysis using `iterate_to_fixpoint`, which returns a `Results` struct. It describes how to use `ResultsCursor` and `ResultsVisitor` for efficient state inspection at specific locations or every location, respectively.