tree 95fdb9c908e0978cf21f1e26f84e8478e151b78c
parent 08351004125c4d49aa757f2c3ec2340f7469ea91
parent b4e94d9a3a04798201676be8f18ee483eb292104
author Mazdak Farrokhzad <twingoow@gmail.com> 1568861591 +0200
committer GitHub <noreply@github.com> 1568861591 +0200
gpgsig -----BEGIN PGP SIGNATURE-----
 
 wsBcBAABCAAQBQJdgu2XCRBK7hj4Ov3rIwAAdHIIAE8C8ogVV8dgz1z0HCXGivgX
 ihld9YQC4Kk1QDbcBJ9GaU6uSqPpsxgqBO/4oUbF2vpQMaU+D3XveHd29QcRCi1y
 tUlJyZ7kZc2W5UwDQXdYT+pyS6krhDRUioHJjXPYxi6e7CGvkrHvWNvIngbmujS4
 SGMOxC4LdY5aOsyUmcjxTPfQHy14rR9HYXniyuvBTCDfL1Vl+fSP2y8Mh9vXeDYn
 w5ixfRYciDTyNK1dPbeanhpjDX7+ZEj67Eyhc7xeK+YNnh4DdAbBIPxPk9FT1IJ0
 Xz7iamKJbE+cfK/1Aoemh7+tpWAD1UKL8W6fyg5EO24/+x++W9wPyf08jtKGLSA=
 =aJbU
 -----END PGP SIGNATURE-----
 

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