Polonius notes

Roadmap-like thingy --- # Polonius notes ## 1. Make it work ### Correctness 1. With PR #62736 UI tests pass except one overflow in fact generation, Matthew identified it to something easily fixable once initialization facts are integrated (since it'll be a simple filtering of those, and seems like both an optimization and fixing this case). 2. Run pass tests succeed except one OOM (is this case fixable, or would it require changing the approach ?) 3. Not all Polonius errors actually show up as rustc errors (examples from in the UI test suite and rand when killing loans on Calls only, 7 of the run-pass tests which pass in rustc fail if we assert that there should be no Polonius errors): [run-pass (polonius)] run-pass/array-slice-vec/check-static-mut-slices.rs [run-pass (polonius)] run-pass/array-slice-vec/check-static-slice.rs [run-pass (polonius)] run-pass/consts/const-vec-of-fns.rs [run-pass (polonius)] run-pass/drop/dynamic-drop-async.rs [run-pass (polonius)] run-pass/generator/addassign-yield.rs [run-pass (polonius)] run-pass/generator/issue-52398.rs [run-pass (polonius)] run-pass/generator/static-generators.rs There were more cases like this in the ui tests, but run-pass was easier to capture at the time. I've started looking at a couple cases and they seemed related to statics, maybe they all are ? ### Completeness 1. illegal subset relations 2. NLL optimizations disabled in Polonius mode 3. Higher rank concerns, and relation to Chalk 4. Move/initialization analysis (with open PRs from Albin here) ### Keeping it correct 1. Enabling the polonius compare mode on CI, current blockers: * OOM on materializing placeholder region subsets at all points of the CFG * slowness in fact generation (not including the liveness facts known to be slow, and which will probably be fixed with Albin's open PRs) --- ## II. Make it good ### 1. precision of the analysis The new variant which better distinguishes instantaneous data flow from persistent data flow: - WIP implementation, still not 100% correct - with early filtering, runs in tractable time on clap - ran the UI test with it, over the PR #62736 fixes, it had 15 failures, including some which look like soundness issues, and may be coming from bugs in the prototype variant. ### 2. refactoring: - deciding on naming and terminology: some of that has already been decided but not implemented, eg borrows to loans, universal regions or free regions to placeholder regions, the requires relation to contains. Some more work on what a good name for regions would be. - code organization: * in polonius itself, eg unit tests written as-is won't scale * fact generation in rustc is a bit ad-hoc and spaghetti (understandably so, but we can probably make it clearer) * passing data between rustc and polonius, eliminating clones, sharing data between Polonius steps (and not just partial resuts between the locinsensitive and regular analysis, but also input data: no need to create Relations multiple times) * the more analyses polonius does, the less a single type of errors makes sense in the communication between rustc and polonius * taking better control of allocation, related to both code organization and performance ### 3. Misc - leapjoins/datafrog: encode WF-ness of leapjoins in the API if possible, loosen the requirements so we can have leapjoins that only filter - a plan for testing (maybe also better architecture/tools for writing tests): testing is still better done in rustc, which is unfortunate/hard. Do we copy all of rustc's tests, how do we synchronize facts ? - is the optimized variant still necessary ? (what about the location insensitive one ?) - docs - more videos ? - issues for new contributors / quest issues / etc - limit the dependencies of the polonius bin (not polonius-engine) to make it faster to compile (I have a WIP branch for this) --- ## III. Make it fast - pushing the filtering as early as possible: on loans, regions, subsets; and the conflict between doing this and how to implement illegal subset relations (3 different ways) - datafrog leapjoins (and the WF-ness question) - maybe the more precise variant has different performance characteristics - CFG compression (but heavy filtering seems to have even more of a performance boost; maybe combining both would be interesting, as it seems sensible data structure to compute some analyses, maybe arielb's iterated dominance frontier but I'm not sure yet I agree/understand it makes sense for liveness per se) - benchmarks: Albin has lots of benchmarks and data but imprecise as timing the polonius binary and not polonius-engine itself or rustc; lokalmatador was working on instrumenting rustc with measureme/-Z self-profile but deleted their github account so this WIP work is lost - regenerating clap made it 2x faster, maybe add the old version back ? - is it possible/easy to compare liveness via polonius vs the existing liveness computations ? can we measure NLL borrowck with just "polonius liveness" ? would that data be useful ? - optimizing datafrog itself: can we use subsumptive tabling ? sorting networks w/ SIMD ? compression and intersection (surely via SIMD as well) ? specific hash joins or bitmap structures, for relations known to be "small" (a bounded max number of tuples really) ? parallelizing the 3 joins/steps per iteration of the semi-naive evaluation ?