about summary refs log tree commit diff
path: root/src/librustc_mir/dataflow
AgeCommit message (Collapse)AuthorLines
2019-09-28Don't treat locals as mutably borrowed after they're droppedDylan MacKenzie-12/+5
2019-09-28Add analysis to determine if a local is indirectly mutableDylan MacKenzie-4/+157
This adds a dataflow analysis that determines if a reference to a given `Local` or part of a `Local` that would allow mutation exists before a point in the CFG. If no such reference exists, we know for sure that that `Local` cannot have been mutated via an indirect assignment or function call.
2019-09-27Remove global_tcx from TyCtxtMark Rousskov-2/+1
The non-global context was removed; there's only one context now. This is a noop method that only serves to confuse readers -- remove it.
2019-09-25Rename `sty` to `kind`varkor-3/+3
2019-09-19Rollup merge of #64566 - ecstatic-morse:generic-dataflow, r=oli-obkMazdak Farrokhzad-0/+513
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
2019-09-18Rollup merge of #64532 - ecstatic-morse:dataflow-cursor-get, r=tmandryTyler Mandry-26/+2
Replace `state_for_location` with `DataflowResultsCursor` These are two different ways of getting the same data from the result of a dataflow analysis. However, `state_for_location` goes quadratic if you try to call it for every statement in the body.
2019-09-18Rollup merge of #64207 - sinkuu:pub_dataflow, r=tmandryTyler Mandry-9/+9
Make rustc_mir::dataflow module pub (for clippy) I'm working on fixing false-positives of a MIR-based clippy lint (https://github.com/rust-lang/rust-clippy/pull/4509), and in need of the dataflow infrastructure.
2019-09-18Fix bug where `is_call_return_effect_applied` was never setDylan MacKenzie-0/+1
2019-09-18Add summary of the current state and future plansDylan MacKenzie-0/+18
2019-09-18Publish `rustc_mir::dataflow` and remove `#[allow(unused)]`Dylan MacKenzie-5/+0
2019-09-18Fix typoDylan MacKenzie-1/+1
2019-09-18Use an associated const for `name`Dylan MacKenzie-2/+2
2019-09-18Fix `Analysis` exampleDylan MacKenzie-2/+4
2019-09-17Add ignore reason to placate `tidy`Dylan MacKenzie-1/+1
2019-09-17Temporarily add `#[allow(unused)]` for CIDylan MacKenzie-0/+2
This can be removed once dataflow-based const validation is merged.
2019-09-17Document new dataflow analysisDylan MacKenzie-0/+50
2019-09-17Add generic dataflow implDylan MacKenzie-0/+445
2019-09-16Remove `dataflow::state_for_location`Dylan MacKenzie-28/+0
2019-09-16Add a getter for the current state to `DataflowResultsCursor`Dylan MacKenzie-0/+4
2019-09-11Make Place Boxed on Statement to reduce size from 64 bytes to 32 bytesSantiago Pastorino-5/+5
2019-09-09Use slice patterns to match projection baseSantiago Pastorino-2/+1
2019-09-09Make move_path_children_matching closure take a PlaceElem instead of a sliceSantiago Pastorino-4/+7
2019-09-09Convert Place's projection to a boxed sliceSantiago Pastorino-92/+85
2019-09-06Make rustc_mir::dataflow module pubShotaro Yamada-9/+9
2019-09-05Auto merge of #62800 - albins:polonius-initialization-1, r=nikomatsakisbors-134/+153
Extend Polonius fact generation for (some) move tracking This PR will extend rustc to emit facts used for tracking moves and initialization in Polonius. It is most likely the final part of my master's thesis work.
2019-09-05Rollup merge of #64005 - ecstatic-morse:is-indirect, r=oli-obkMazdak Farrokhzad-13/+4
Add a `Place::is_indirect` method to determine whether a `Place` contains a `Deref` projection Working on #63860 requires tracking some property about each local. This requires differentiating `Place`s like `x` and `x.field[index]` from ones like `*x` and `*x.field`, since the first two will always access the same region of memory as `x` while the latter two may access any region of memory. This functionality is duplicated in various places across the compiler. This PR adds a helper method to `Place` which determines whether that `Place` has a `Deref` projection at any point and changes some existing code to use the new method. I've not converted `qualify_consts.rs` to use the new method, since it's not a trivial conversion and it will get replaced anyway by #63860. There may be other potential uses besides the two I change in this PR. r? @oli-obk
2019-09-04Rustfmt the files I touchedAlbin Stjerna-135/+147
2019-09-04Polonius: emit initialization/move tracking factsAlbin Stjerna-1/+8
- var_starts_path - parent - initialized_at - moved_out_at This also switches to the intended emission of `var_drop_used` fact emission, where that fact is always emitted on a drop-use of a variable, regardless of its initialization status, as Polonius now handles that.
2019-08-31Kill borrows from assignments after generating new borrowsMatthew Jasper-4/+4
2019-08-30Use new `Place::is_indirect` API where possibleDylan MacKenzie-13/+4
2019-08-24Allow lifetime parameters to be inferredSantiago Pastorino-1/+1
2019-08-08Use associated_type_bounds where applicable - closes #61738Ilija Tovilo-8/+3
2019-08-05Fiddle param env through to `try_eval_bits` in most placesOliver Scherer-1/+5
2019-07-22Place::as_place_ref is now Place::as_refSantiago Pastorino-9/+9
2019-07-20Avoid unneeded else branchesSantiago Pastorino-22/+13
2019-07-20Avoid cloning Place in gather_initSantiago Pastorino-13/+13
2019-07-20Avoid cloning Place in report_use_of_moved_or_uninitialized and friendsSantiago Pastorino-9/+9
2019-07-20Migrate from Place enum to Place structSantiago Pastorino-21/+47
2019-07-14Actually call `visit_block_entry` in `DataflowResultsConsumer`Dylan MacKenzie-0/+2
Previously, this callback was never actually called.
2019-07-03Remove needless lifetimesJeremy Stucki-1/+1
2019-07-02Auto merge of #61922 - tmandry:moar-generator-optimization, r=matthewjasperbors-13/+244
Don't store locals that have been moved from in generators This avoids reserving storage in generators for locals that are moved out of (and not re-initialized) prior to yield points. Fixes #59123. This adds a new dataflow analysis, `RequiresStorage`, to determine whether the storage of a local can be destroyed without being observed by the program. The rules are: 1. StorageLive(x) => mark x live 2. StorageDead(x) => mark x dead 3. If a local is moved from, _and has never had its address taken_, mark it dead 4. If (any part of) a local is initialized, mark it live' This is used to determine whether to save a local in the generator object at all, as well as which locals can be overlapped in the generator layout. Here's the size in bytes of all testcases included in the change, before and after the change: async fn test |Size before |Size after -----------------|------------|---------- single | 1028 | 1028 single_with_noop | 2056 | 1032 joined | 5132 | 3084 joined_with_noop | 8208 | 3084 generator test |Size before |Size after ----------------------------|------------|---------- move_before_yield | 1028 | 1028 move_before_yield_with_noop | 2056 | 1032 overlap_move_points | 3080 | 2056 ## Future work Note that there is a possible extension to this optimization, which modifies rule 3 to read: "If a local is moved from, _**and either has never had its address taken, or is Freeze and has never been mutably borrowed**_, mark it dead." This was discussed at length in #59123 and then #61849. Because this would cause some behavior to be UB which was not UB before, it's a step that needs to be taken carefully. A more immediate priority for me is inlining `std::mem::size_of_val(&x)` so it becomes apparent that the address of `x` is not taken. This way, using `size_of_val` to look at the size of your inner futures does not affect the size of your outer future. cc @cramertj @eddyb @Matthias247 @nikomatsakis @RalfJung @Zoxc
2019-07-01Clean up extra lifetime, add assertionsTyler Mandry-14/+18
2019-06-30Rollup merge of #62062 - ecstatic-morse:dataflow-order, r=nagisaMazdak Farrokhzad-2/+18
Use a more efficient iteration order for forward dataflow Currently, dataflow begins by visiting each block in order of ID (`BasicBlock(0)`, `BasicBlock(1)`, etc.). This PR changes that initial iteration to reverse post-order (see [this blog post](https://eli.thegreenplace.net/2015/directed-graph-traversal-orderings-and-applications-to-data-flow-analysis/#data-flow-analysis) for more info). This ensures that the effects of all predecessors will be applied before a basic block is visited if the CFG has no back-edges, and should result in less total iterations even when back-edges exist. This should not change the results of dataflow analysis. The current ordering for basic blocks may be pretty close to RPO already--`BasicBlock(0)` is already the start block--in which case the cost of doing the traversal up front will outweigh the efficiency gains. A perf run is needed to check this. r? @pnkfelix (I think).
2019-06-28Use RequiresStorage to determine which locals can overlapTyler Mandry-4/+0
2019-06-28Remove Clone requirementTyler Mandry-4/+1
2019-06-27Use a more efficient iteration order for forward dataflowDylan MacKenzie-2/+18
Currently, dataflow begins by visiting each block in order of ID (`BasicBlock(0)`, `BasicBlock(1)`, etc.). This PR changes that initial iteration to reverse post-order. This ensures that the effects of all predecessors will be applied before a basic block is visited if the CFG has no back-edges, and should result in less total iterations even when back-edges exist. This should not change the results of dataflow analysis. The current ordering for basic blocks is pretty close to RPO already--`BasicBlock(0)` is already the start block, so the gains from this are pretty small, especially since we need to do an extra traversal up front. Note that some basic blocks are unreachable from the `START_BLOCK` during dataflow. We add these blocks to the work queue as well to preserve the original behavior.
2019-06-25Add RequiresStorage pass to decide which locals to save in generatorsTyler Mandry-1/+131
This avoids reserving storage in generators for locals that are moved out of (and not re-initialized) prior to yield points.
2019-06-25Add DataflowResultsCursorTyler Mandry-0/+94
2019-06-25Make FlowAtLocation support borrowing flow dataTyler Mandry-11/+21
2019-06-25Implement From<Local> for Place and PlaceBaseSantiago Pastorino-5/+5
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-03-12 03:34:29 +0000