Manuel Fähndrich
Jeffrey S. Foster
Zhendong Su
Alexander Aiken
ABSTRACT
Many program analyses are naturally formulated and implemented using inclusion constraints. We present new results on the scalable implementation of such analyses based on two insights: first, that online elimination of cyclic constraints yields orders-of-magnitude improvements in analysis time for large problems; second, that the choice of constraint representation affects the quality and efficiency of online cycle elimination. We present an analytical model that explains our design choices and show that the model's predictions match well with results from a substantial experiment.
- And94.L.O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994. DiKU report 94/19.Google Scholar
- AW92.A. Aiken and E. Wimmers. Solving Systems of Set Constraints. In Symposium on Logic in Computer Science, pages 329-340, June 1992.Google Scholar
- AW93.A. Aiken and E. Wimmers. Type Inclusion Constraints and Type Inference. in Proceedings of the 1993 Conference on Functional Programming Languages and Computer Architecture, pages 31- 41, Copenhagen, Denmark, June 1993. Google ScholarDigital Library
- AWL94.A. Aiken, E. Wimmers, and T.K. Lakshman. Soft typing with conditional types. In Twenty-First Annual A CM Symposium on Principles of Programming Languages, January 1994. Google ScholarDigital Library
- FA96.M. F'~hndrich and A. Aiken. Making Set- Constraint Based Program Analyses Scale. In First Workshop on Set Constraints at CP'96, Cambridge, MA, August 1996. Available as Technical Report CSD-TR-96-917, University of California at Berkeley. Google ScholarDigital Library
- FF97.C. Flanagan and M. Felleisen. Componential Set- Based Analysis. In PLDr97 {PLD97}. Google ScholarDigital Library
- FFA97.J. Foster, M. F'~hndrich, and A. Aiken. Flowinsensitive Points-to Analysis with Term and Set Constraints. Technical Report UCB//CSD-97- 964, U. of California, Berkeley, August 1997. Google ScholarDigital Library
- FFK+96.C. Flanagan, M. Flatt, S. Krishnamurthi, S. Weirich, and M. Felleisen. Catching Bugs in the Web of Program Invariants. In Proceedings of the 1996 A CM SiGPLAN Con/erence on Programming Language Design and Implementation, pages 23-32, May 1996. Google ScholarDigital Library
- GJS96.James Gosling, Bill Joy, and Guy Steele. The Java Language Specification, chapter 10, pages 199-200. Addison Wesley, 1996. Google ScholarDigital Library
- Hei92.N. Heintze. Set Based Program Analysis. PhD thesis, Carnegie Mellon University, 1992. Google ScholarDigital Library
- Hei94.N. Heintze. Set Based Analysis of ML Programs. In Proceedings of the 1994 A CM Conference on LiSP and Functional Programming, pages 306- 17, June 1994. Google ScholarDigital Library
- HJ90.N. Heintze and J. Jaffar. A decision procedure for a class of Herbrand set constraints. In Symposium on Logic in Computer Science, pages 42-51, June 1990.Google Scholar
- HM97.N. Heintze and D. McAllester. Linear-Time Subtransitive Control Flow Analysis. In PLDI'97 {PLD97}. Google ScholarDigital Library
- JM79.N.D. Jones and S. S. Muchnick. Flow Analysis and Optimization of LISP-like Structures. In Sixth Annual A CM Symposium on Principles of Programming Languages, pages 244-256, Januaxy 1979. Google ScholarDigital Library
- Knu73.D. Knuth. The Art of Computer Programming, Fundamental Algorithms, volume 1. Addison- Wesley, Reading, Mass., 2 edition, 1973. Google ScholarDigital Library
- Koz93.D. Kozen. Logical Aspects of Set Constraints. In E. BSrger, Y. Gurevich, and K. Meinke, editors, Proc. 1993 Conf. Computer Science Logic (CSL '93), volume 832 of Lecture Notes in Computer Science, pages 175-188. Springer-Verlag, 1993. Google ScholarDigital Library
- Mos96.C. Mossin. Flow Analysis of Typed Higher-Order Programs. PhD thesis, DIKU, Department of Computer Science, University of Copenhagen, 1996.Google Scholar
- MTH90.Robin Milner, Mads Torte, and Robert Harper. The Definition of Standard ML. MIT Press, 1990. Google ScholarDigital Library
- MW97.S. Marlow and P. Wadler. A Practical Subtyping System For Erlang. In Proceedings of the International Conference on Functional Programming (ICFP '97), June 1997. Google ScholarDigital Library
- PLD97.Proceedings of the 1997 ACM SIGPLAN Conference on Programming Language Design and Implementation, June 1997.Google Scholar
- Pot96.F. Pottier. Simplifying Subtyping Constraints. In Proceedings of the 1996 A CM SIGPLAN international Conference on Functional Programming (iCFP '96), pages 122-133, January 1996. Google ScholarDigital Library
- PS91.J. Palsberg and M. I. Schwartzbach. Object- Oriented Type Inference. In Proceedings of the A CM Conference on Object-Oriented programming: Systems, Languages, and Applications, October 1991. Google ScholarDigital Library
- Rey69.J.C. Reynolds. Automatic Computation of Data Set Definitions, pages 456-461. Information Processing 68. North-Holland, 1969.Google Scholar
- SH97.M. Shapiro and S. Horwitz. Fast and Accurate Flow-Insensitive Points-To Analysis. In Proceedings of the 2~th Annual A CM SIGPLAN- SIGA CT Symposium on Principles of Programming Languages, pages 1-14, January 1997. Google ScholarDigital Library
- Shi88.O. Shivers. Control Flow Analysis in Scheme. In Proceedings of the A CM SIGPLAN '88 Conference on Programming Language Design and Implementation, pages 164-174, June 1988. Google ScholarDigital Library
- Shm83.O. Shmueli. Dynamic Cycle Detection. Information Processing Letters, 17(4):185-188, 8 November 1983.Google Scholar
- Ste95.B. Steensgaard. Points-to Analysis in Almost Linear Time. In Proceedings of the 23rd Annual A CM SIGPLAN-S~GA CT Symposium on Principles of Pro~ramming Languages, pages 32-41, January 1996. Google ScholarDigital Library
- TS96.V. Trifonov and S. Smith. Subtyping Constrained Types. In Proceedings of the 3rd International Static Analysis Symposium, pages 349- 365, September 1996. Google ScholarDigital Library
Recommendations
Efficient field-sensitive pointer analysis of C
The subject of this article is flow- and context-insensitive pointer analysis. We present a novel approach for precisely modelling struct variables and indirect function calls. Our method emphasises efficiency and simplicity and is based on a simple ...
Precise interprocedural dataflow analysis via graph reachability
POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languagesThe paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem. The only restrictions are that the set of dataflow facts ...
SVF: interprocedural static value-flow analysis in LLVM
CC 2016: Proceedings of the 25th International Conference on Compiler ConstructionThis paper presents SVF, a tool that enables scalable and precise interprocedural Static Value-Flow analysis for C programs by leveraging recent advances in sparse analysis. SVF, which is fully implemented in LLVM, allows value-flow construction and ...
Comments