Polyvariance Explained

In program analysis, a polyvariant or context-sensitive analysis (as opposed to a monovariant or context-insensitive analysis) analyzes each function multiple times - typically once at each call site - to improve the precision of the analysis.^[1] Polyvariance is common in data-flow and pointer analyses.

Forms of polyvariance include:

• Call-site sensitivity
• The Cartesian product algorithm^[2]
• Object sensitivity
• Type sensitivity

The first two are more often used for dataflow analyses, the latter two are more frequently used for pointer analyses.

References

Sources

• Smaragdakis . Yannis . Balatsouras . George . 2015 . Pointer Analysis . Foundations and Trends in Programming Languages . 2 . 1 . 1–69 . May 30, 2019. 10.1561/2500000014 .

Notes and References

1. Jens. Palsberg. Jens Palsberg. Christina. Pavlopoulou. Christina Pavlopoulou. From Polyvariant Flow Information to Intersection and Union Types. Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '98). 11. 3. 197 - 208. 10.1017/S095679680100394X. 2001. 10.1.1.36.4441. 16895848 .
2. Book: Gilray . Thomas . Adams . Michael D. . Might . Matthew . Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming . Allocation characterizes polyvariance: A unified methodology for polyvariant control-flow analysis . 2016-09-04 . https://doi.org/10.1145/2951913.2951936 . ICFP 2016 . New York, NY, USA . Association for Computing Machinery . 407–420 . 10.1145/2951913.2951936 . 978-1-4503-4219-3. 7768606 .