]> git.lizzy.rs Git - rust.git/commit
Rollup merge of #64566 - ecstatic-morse:generic-dataflow, r=oli-obk
authorMazdak Farrokhzad <twingoow@gmail.com>
Thu, 19 Sep 2019 02:53:11 +0000 (04:53 +0200)
committerGitHub <noreply@github.com>
Thu, 19 Sep 2019 02:53:11 +0000 (04:53 +0200)
commit67565ae4ae0bfe686ecbbb7808c601a87bde5efe
tree95fdb9c908e0978cf21f1e26f84e8478e151b78c
parent08351004125c4d49aa757f2c3ec2340f7469ea91
parentb4e94d9a3a04798201676be8f18ee483eb292104
Rollup merge of #64566 - ecstatic-morse:generic-dataflow, r=oli-obk

A more generic interface for dataflow analysis

#64470 requires a transfer function that is slightly more complex than the typical `gen`/`kill` one. Namely, it must copy state bits between locals when assignments occur (see #62547 for an attempt to make this fit into the existing framework). This PR contains a dataflow interface that allows for arbitrary transfer functions. The trade-off is efficiency: we can no longer coalesce transfer functions for blocks and must visit each statement individually while iterating to fixpoint.

Another issue is that poorly behaved transfer functions can result in an analysis that fails to converge. `gen`/`kill` sets do not have this problem. I believe that, in order to guarantee convergence, flipping a bit from `false` to `true` in the entry set cannot cause an output bit to go from `true` to `false` (negate all preceding booleans when `true` is the bottom value). Perhaps someone with a more formal background can confirm and we can add a section to the docs?

This approach is not maximally generic: it still requires that the lattice used for analysis is the powerset of values of `Analysis::Idx` for the `mir::Body` of interest. This can be done at a later date. Also, this is the bare minimum to get #64470 working. I've not adapted the existing debug framework to work with the new analysis, so there are no `rustc_peek` tests either. I'm planning to do this after #64470 is merged.

Finally, my ultimate plan is to make the existing, `gen`/`kill`-based `BitDenotation` a special case of `generic::Analysis`. Currently they share a ton of code. I should be able to do this without changing any implementers of `BitDenotation`. Something like:

```rust
struct GenKillAnalysis<A: BitDenotation> {
    trans_for_block: IndexVec<BasicBlock, GenKillSet<A::Idx>>,
    analysis: A,
}

impl<A> generic::Analysis for GenKillAnalysis<A> {
    // specializations of `apply_{partial,whole}_block_effect`...
}
```

r? @pnkfelix
src/librustc_mir/dataflow/mod.rs
src/librustc_mir/lib.rs