article

Open access

A schema for interprocedural modification side-effect analysis with pointer aliasing

Authors:

Rita AltucherAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 23, Issue 2

Pages 105 - 186

https://doi.org/10.1145/383043.381532

Published: 01 March 2001 Publication History

PDF eReader

Abstract

The first interprocedural modification side-effects analysis for C (MOD_C) that obtains better than worst-case precision on programs with general-purpose pointer usage is presented with empirical results. The analysis consists of an algorithm schema corresponding to a family of MOD_C algorithms with two independent phases: one for determining pointer-induced aliases and a subsequent one for propagating interprocedural side effects. These MOD_C algorithms are parameterized by the aliasing method used. The empirical results compare the performance of two dissimilar MOD_C algorithms: MOD_C(FSAlias) uses a flow-sensitive, calling-context-sensitive interprocedural alias analysis; MOD_C(FIAlias uses a flow-insensitive, calling-context-insensitive alias analysis which is much faster, but less accurate. These two algorithms were profiled on 45 programs ranging in size from 250 to 30,000 lines of C code, and the results demonstrate dramatically the possible cost-precision trade-offs. This first comparative implementation of MOD_C analyses offers insight into the differences between flow-/context-sensitive and flow-/context-insensitive analyses. The analysis cost versus precision trade-offs in side-effect information obtained are reported. The results show surprisingly that the precision of flow-sensitive side-effect analysis is not always prohibitive in cost, and that the precision of flow-insensitive analysis is substantially better than worst-case estimates and seems sufficient for certain applications. On average MOD_C(FSAlias) for procedures and calls is in the range of 20% more precise than MOD_C(FIAlias); however, the performance was found to be at least an order of magnitude slower than MOD_C(FIAlias).

References

[1]

AHO,A.V.,SETHI, R., AND ULLMAN, J. D. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA.]]

Digital Library

Google Scholar

[2]

ALLEN, F. E. 1974. Interprocedural data flow analysis. In Proceedings of 1974 IFIP Congress, Amsterdam, Holland, pp. 398-402. Institute of Electrical and Electronics Engineers, Inc., North Holland Publishing Company.]]

Google Scholar

[3]

ANDERSEN, L. O. 1994. Program analysis and specialization for the C programming language. Ph.D. Thesis, DIKU, University of Copenhagen. Also available as DIKU report 94/19.]]

Google Scholar

[4]

ATKINSON,D.AND GRISWOLD, W. 1996. The design of whole-program analysis tools. In Proceedings of the 18th International Conference on Software Engineering, pp. 16-27.]]

Digital Library

Google Scholar

[5]

ATKINSON,D.AND GRISWOLD, W. 1998. Effective whole-program analysis in the presence of pointers. In Proceedings of the ACMSIGSOFT '98 Symposium on the Foundations of Software Engineering, pp. 46-55.]]

Digital Library

Google Scholar

[6]

BANERJEE, U. 1988. Dependence Analysis for Supercomputing. Kluwer Academic Publishers, Norwell, MA.]]

Digital Library

Google Scholar

[7]

BANNING, J. 1979. An efficient way to find the side effects of procedure calls and the aliases of variables. In Conference Record of the Sixth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages. pp. 29-41.]]

Digital Library

Google Scholar

[8]

BARTH, J. M. 1978. A practical interprocedural data flow analysis algorithm. Communications of the ACM 21, 9, 724-736.]]

Digital Library

Google Scholar

[9]

BATES,S.AND HORWITZ, S. 1993. Incremental program testing using dependence graphs. In Conference Record of the Twentieth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 384-396.]]

Digital Library

Google Scholar

[10]

BURKE, M. 1990. An interval-based approach to exhaustive and incremental interprocedural data flow analysis. ACM Transactions on Programming Languages and Systems, 12, 3, 341-395.]]

Digital Library

Google Scholar

[11]

BURKE,M.AND RYDER, B. G. 1990. A critical analysis of incremental iterative data flow analysis algorithms. IEEE Transactions on Software Engineering, 16,7.]]

Digital Library

Google Scholar

[12]

BURKE, M., CARINI, P., CHOI, J.-D., AND HIND, M. 1994. Flow-insensitive interprocedural alias analysis in the presence of pointers. In Proceedings of the Seventh International Workshop on Languages and Compilers for Parallel Computing, pp. 234-250. Springer-Verlag.]]

Digital Library

Google Scholar

[13]

BURKE, M., CARINI, P., CHOI, J.-D., AND HIND, M. 1997. Interprocedural pointer alias analysis. Research Report RC 21055, IBM T. J. Watson Research Center.]]

Google Scholar

[14]

CARROLL, M. D. 1988. A new pointer-removing program transformation. Unpublished manuscript.]]

Google Scholar

[15]

CARROLL,M.D.AND RYDER, B. G. 1988. Incremental data flow analysis via dominator and attribute updates. In Conference Record of the Fifteenth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 274-284.]]

Digital Library

Google Scholar

[16]

CHASE, D. R., WEGMAN, M., AND ZADECK, F. K. 1990. Analysis of pointers and structures. In Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, pp. 296-310. SIGPLAN Notices, Vol. 25, No. 6.]]

Digital Library

Google Scholar

[17]

CHATTERJEE, R. 1999. Modular data-flow analysis of statically typed object-oriented programming languages. Ph.D. Thesis, Department of Computer Science, Rutgers University.]]

Digital Library

Google Scholar

[18]

CHATTERJEE,R.AND RYDER, B. G. 1999. Data-flow-based testing of object-oriented libraries. Department of Computer Science Technical Report DCS-TR-382, Rutgers University.]]

Google Scholar

[19]

CHATTERJEE, R., RYDER,B.G.,AND LANDI, W. A. 1999. Relevant context inference. In Conference Record of the Twenty-Sixth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages.]]

Digital Library

Google Scholar

[20]

CHOI, J.-D., BURKE, M., AND CARINI, P. 1993. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Conference Record of the Twentieth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 232-245.]]

Digital Library

Google Scholar

[21]

COOPER, K. 1985. Analyzing aliases of reference formal parameters. In Conference Record of the Twelfth Annual ACMSIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 281-290.]]

Digital Library

Google Scholar

[22]

COOPER, B. G. 1989. Ambitious data flow analysis of procedural programs. Master's Thesis, University of Minnesota.]]

Google Scholar

[23]

COOPER,K.AND KENNEDY, K. 1984. Efficient computation of flow insensitive interprocedural summary information. In Proceedings of the ACM SIGPLAN Symposium on Compiler Construction, pp. 247-258. SIGPLAN Notices, Vol. 19, No. 6.]]

Digital Library

Google Scholar

[24]

COOPER,K.AND KENNEDY, K. 1987. Complexity of interprocedural side-effect analysis. Computer Science Department Technical Report TR87-61, Rice University.]]

Google Scholar

[25]

COOPER,K.AND KENNEDY, K. 1988. Interprocedural side-effect analysis in linear time. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation,pp. 57-66.]]

Digital Library

Google Scholar

[26]

COUTANT, D. S. 1986. Retargetable high-level alias analysis. In Conference Record of the Thirteenth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 110-118.]]

Digital Library

Google Scholar

[27]

DAS, M. 2000. Unification-based pointer analysis with directional assignments. In Proceedings of the ACM SIGPLAN '00 Conference on Programming Language Design and Implementation, pp. 35-46.]]

Digital Library

Google Scholar

[28]

DEUTSCH, A. 1990. On determining lifetime and aliasing of dynamically allocated data in higherorder functional specifications. In Conference Record of the Seventeenth Annual ACM SIGACT/ SIGPLAN Symposium on Principles of Programming Languages, pp. 157-168.]]

Digital Library

Google Scholar

[29]

DEUTSCH, A. 1992. A storeless model of aliasing and its abstractions using finite representations of right-regular equivalence relations. In Proceedings of the IEEE 1992 Conference on Computer Languages, pp. 2-13.]]

Crossref

Google Scholar

[30]

DEUTSCH, A. 1994. Interprocedural may alias for pointers: Beyond k-limiting. In Proceedings of the SIGPLAN '94 Conference on Programming Language Design and Implementation, pp. 230- 241.]]

Digital Library

Google Scholar

[31]

DUESTERWALD, E., GUPTA, R., AND SOFFA, M. L. 1995. Demand-driven computation of interprocedural data flow. In Conference Record of the Twenty-Second Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages.]]

Digital Library

Google Scholar

[32]

DUESTERWALD, E., GUPTA, R., AND SOFFA, M. L. 1996. A demand-driven analyzer for data flow testing at the integration level. In Proceedings of the International Conference on Software Engineering (ICSE'96).]]

Digital Library

Google Scholar

[33]

EMAMI, M. 1993. A practical interprocedural alias analysis for an optimizing/parallelizing C compiler. Master's Thesis, McGill University, Montreal, Canada.]]

Google Scholar

[34]

EMAMI, M., GHIYA, R., AND HENDREN, L. J. 1994. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the SIGPLAN '94 Conference on Programming Language Design and Implementation, pp. 242-257. Published as SIGPLAN Notices, 29 (6).]]

Digital Library

Google Scholar

[35]

FAHNDRICH, M., REHOF,J.,AND DAS, M. 2000. Scalable context-sensitive flow analysis using instantiation constraints. Proceedings of the ACMSIGPLAN '00 Conference on Programming Language Design and Implementation, pp. 253-263.]]

Digital Library

Google Scholar

[36]

FRANKEL,P.AND IAKOUNENKO, O. 1998. Further empirical studies of test effectiveness. In ACM SIGSOFT '98 Sixth International Symposium on the Foundations of Software Engineering,pp. 153-162.]]

Digital Library

Google Scholar

[37]

FRANKEL,P.AND WEISS, S. 1993. An experimental comparison of the effectiveness of branch testing with data-flow testing. IEEE Transactions on Software Engineering 19, 8, 774-787.]]

Digital Library

Google Scholar

[38]

FOSTER, J., FAHNDRICH, M., AND AIKEN, A. 2000. Polymorphic versus monomorphic flow-insensitive points-to analysis for C. In Proceedings of International Symposium on Static Analysis (SAS '00).]]

Digital Library

Google Scholar

[39]

GALLAGHER,K.AND LYLE, J. 1991. Using program slices in software maintenance. IEEE Transactions on Software Engineering 17, 8, 751-761.]]

Digital Library

Google Scholar

[40]

GHIYA,R.AND HENDREN, L. 1996a. Connection analysis: A practical interprocedural heap analysis for C. International Journal of Parallel Programming.]]

Google Scholar

[41]

GHIYA,R.AND HENDREN, L. 1996b. Is it a tree, a dag or a cyclic graph? A shape analysis for heap-directed pointers in C. In Conference Record of the Twenty-Third Annual ACM SIGACT/ SIGPLAN Symposium on Principles of Programming Languages, pp. 1-15.]]

Digital Library

Google Scholar

[42]

GHIYA,R.AND HENDREN, L. 1998. Putting pointer analysis to work. In Conference Record of the Twenty-Fifth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 121-133.]]

Digital Library

Google Scholar

[43]

GUARNA, C. A. 1988. A technique for analyzing pointer and structure references in parallel restructuring compilers. In Proceedings of the International Conference on Parallel Processing, pp. 212-220.]]

Google Scholar

[44]

GUPTA,R.AND SOFFA, M. L. 1996. Hybrid slicing: An approach for refining static slices using dynamic information. In Proceedings of Third ACM SIGSOFT Symposium on Foundations of Software Engineering, pp. 29-40.]]

Digital Library

Google Scholar

[45]

HARRISON, W. L., III AND AMMARGUELLAT, Z. 1990. Parcel and Miprac: Parallelizers for symbolic and numeric programs. In Proceedings of International Workshop on Compilers for Parallel Computers, pp. 329-346. Ecole des Mines de Paris-CAI, UPMC-Laboratoire MASI, Paris, France.]]

Google Scholar

[46]

HARROLD,M.J.AND CI, N. 1998. Reuse-driven interprocedural slicing. In Proceedings of the Twentieth International Conference on Software Engineering, pp. 74-83.]]

Digital Library

Google Scholar

[47]

HARROLD,M.J.AND SOFFA, M. L. 1991. Selecting and using data for integration testing. IEEE Software 8, 2, 58-65.]]

Digital Library

Google Scholar

[48]

HARROLD,M.J.AND SOFFA, M. L. 1994. Efficient computation of interprocedural definitionuse chains. ACM Transactions on Programming Languages and Systems 16, 2, 175-204.]]

Digital Library

Google Scholar

[49]

HASTI,R.AND HORWITZ, S. 1998. Using static single assignment form to improve flow-insensitive pointer analysis. In Proceedings of the ACMSIGPLAN '98 Conference on Programming Language Design and Implementation, pp. 97-105.]]

Digital Library

Google Scholar

[50]

HENDREN,L.AND NICOLAU, A. 1990. Parallelizing programs with recursive data structures. IEEE Transaction on Parallel and Distributed Systems.]]

Digital Library

Google Scholar

[51]

HENDREN, L., HUMMEL,J.,AND NICOLAU, A. 1992. Abstractions for recursive pointer data structures: Improving analysis and transformations of imperative languages. In Proceedings of the SIGPLAN '92 Conference on Programming Language Design and Implementation, pp. 249-260. SIGPLAN Notices, Vol. 27, No. 6.]]

Digital Library

Google Scholar

[52]

HIND,M.AND PIOLI, A. 1998. Assessing the effects of flow sensitivity on pointer alias analysis. In Proceedings of International Static Analysis Symposiusm (SAS'98), pp. 57-81. Springer- Verlag.]]

Digital Library

Google Scholar

[53]

HIND,M.AND PIOLI, A. 2000. Evaluating the effectiveness of pointer alias analyses. In Proceedings of ACM SIGSOFT International Symposium on Software Testing and Analysis. Also available as IBM Research Center Technical Report RC21510.]]

Google Scholar

[54]

HIND, M., BURKE, N., CARINI,P.,AND CHOI, J.-D. 1999. Interprocedural pointer alias analysis. ACM Transactions on Programming Languages and Systems 21, 4, 848-894.]]

Digital Library

Google Scholar

[55]

HORWITZ, S., PFEIFFER,P.,AND REPS, T. 1989. Dependence analysis for pointer variables. In Proceedings of the ACM SIGPLAN Symposium on Compiler Construction, pp. 28-40.]]

Digital Library

Google Scholar

[56]

HORWITZ, S., REPS,T.,AND BINKLEY, D. 1990. Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems 12,1.]]

Digital Library

Google Scholar

[57]

HORWITZ, S., REPS,T.,AND SAGIV, M. 1995. Demand interprocedural dataflow analysis. In Proceedings of the Third ACM SIGSOFT Symposium on the Foundations of Software Engineering,pp. 104-115.]]

Digital Library

Google Scholar

[58]

HUTCHINS, M., FOSTER, H., GORADIA,T.,AND OSTRAND, T. 1994. Experiments on the effectiveness of dataflow- and controlflow-based test adequacy criteria. In Proceedings of the Sixteenth International Conference on Software Engineering, pp. 191-200.]]

Digital Library

Google Scholar

[59]

JONES,N.D.AND MUCHNICK, S. 1982a. Flow analysis and optimization of LISP-like structures. In Program Flow Analysis: Theory and Applications. S. Muchnick and N. Jones, Ed. Prentice Hall, Englewood, Cliff., NJ, pp. 102-131.]]

Google Scholar

[60]

JONES,N.D.AND MUCHNICK, S. S. 1982b. A flexible approach to interprocedural data flow analysis and programs with recursive data structures. In Conference Record of the Ninth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 66-74.]]

Digital Library

Google Scholar

[61]

KAM,J.B.AND ULLMAN, J. D. 1977. Monotone data flow analysis frameworks. Acta Informatica 7, pp. 305-317.]]

Digital Library

Google Scholar

[62]

KILDALL, G. 1973. A unified approach to global program optimization. In Conference Record of the ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 194-206.]]

Digital Library

Google Scholar

[63]

LANDI, W. 1992a. Interprocedural aliasing in the presence of pointers. Ph.D. Thesis, Rutgers University. LCSR-TR-174.]]

Digital Library

Google Scholar

[64]

LANDI, W. 1992b. Undecidability of static analysis. ACMLetters on Programming Languages and Systems 1, (4):323-337.]]

Digital Library

Google Scholar

[65]

LANDI,W.AND RYDER, B. G. 1991. Pointer-induced aliasing: A problem classification. In Conference Record of the Eighteenth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 93-103.]]

Digital Library

Google Scholar

[66]

LANDI,W.AND RYDER, B. G. 1992. A safe approximation algorithm for interprocedural pointer aliasing. In Proceedings of the SIGPLAN '92 Conference on Programming Language Design and Implementation, pp. 235-248.]]

Digital Library

Google Scholar

[67]

LANDI,W.AND RYDER,B.G.AND ZHANG, S. 1993. Interprocedural modification side effect analysis with pointer aliasing. In Proceedings of the SIGPLAN '93 Conference on Programming Language Design and Implementation, pp. 56-67.]]

Digital Library

Google Scholar

[68]

LARSEN,L.AND HARROLD, M. J. 1996. Slicing object-oriented software. In Proceedings of the Eighteenth International Conference on Software Engineering, pp. 495-505.]]

Digital Library

Google Scholar

[69]

LARUS,J.R.AND HILFINGER, P. N. 1988. Detecting conflicts between structure accesses. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, pp. 1-34. SIGPLAN NOTICES, Vol. 23, No. 7.]]

Digital Library

Google Scholar

[70]

LIANG,D.AND HARROLD, M. J. 1999. Efficient points-to analysis for whole-program analysis. In Proceedings of the Seventh Annual ACM SIGSOFT Symposium on the Foundations of Software Engineering, LNCS, Vol. 1687, pp. 199-215.]]

Digital Library

Google Scholar

[71]

MARLOWE,T.J.AND RYDER, B. G. 1990a. An efficient hybrid algorithm for incremental data flow analysis. In Conference Record of the Seventeenth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 184-196.]]

Digital Library

Google Scholar

[72]

MARLOWE,T.J.AND RYDER, B. G. 1990b. Properties of data flow frameworks: A unified model. Acta Informatica 28, 121-163.]]

Digital Library

Google Scholar

[73]

MARLOWE,T.J.AND RYDER, B. G. 1991. Hybrid incremental alias algorithms. In Proceedings of the Twenty-Fourth Hawaii International Conference on System Sciences, Vol. II, Software.]]

Crossref

Google Scholar

[74]

MARLOWE,T.J.,LANDI, W. A., RYDER,B.G.,CHOI, J., BURKE, M., AND CARINI, P. 1993. Pointerinduced aliasing: A clarification. ACM SIGPLAN Notices 28, 9, 67-70.]]

Digital Library

Google Scholar

[75]

NEIRYNCK, A., PANANGADEN,P.,AND DEMERS, A. 1987. Computation of aliases and support sets. In Conference Record of the Fourteenth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, 274-283.]]

Digital Library

Google Scholar

[76]

OSTRAND, T. J. 1990. Data-flow testing with pointers and function calls. In Proceedings of the Pacific Northwest Software Quality Conference.]]

Google Scholar

[77]

OTTENSTEIN,K.J.AND OTTENSTEIN, L. M. 1984. The program dependence graph in a software development environment. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, pp. 177-184.]]

Digital Library

Google Scholar

[78]

PANDE,H.D.,LANDI,W.,AND RYDER, B. G. 1994. Interprocedural def-use associations for C systems with single level pointers. IEEE Transactions on Software Engineering 20, 5, 385- 403.]]

Digital Library

Google Scholar

[79]

PIOLI, A. 1999. Conditional pointer aliasing and constant propagation. Master's Thesis, SUNY at New Paltz. Available at http://www.mcs.newpaltz/tr as Technical Report 99-102.]]

Google Scholar

[80]

POLLOCK,L.AND SOFFA, M. 1989. An incremental version of iterative data flow analysis. IEEE Transactions on Software Engineering 15, 12.]]

Digital Library

Google Scholar

[81]

POLYCHRONOPOLOUS, C. D. 1988. Parallel Programming and Compilers. Kluwer Academic Publishers.]]

Digital Library

Google Scholar

[82]

RAMALINGAM, G. 1994. The undecidability of aliasing. ACM Transactions on Programming Languages and Systems 16, 5, 1467-1471.]]

Digital Library

Google Scholar

[83]

REPS,T.AND ROSAY, G. 1995. Precise interprocedural chopping. In Proceedings of the Third ACM SIGSOFT Symposium on Foundations of Software Engineeering, pp. 41-52.]]

Digital Library

Google Scholar

[84]

REPS, T., HORWITZ,S.AND SAGIV, M. 1995. Precise interprocedural dataflow analysis via graph reachability. In Conference Record of the Twenty-Second Annual ACM SIGACT/SIGPLAN Sym-posium on Principles of Programming Languages, pp. 49-61.]]

Digital Library

Google Scholar

[85]

ROUNTEV,A.AND CHANDRA, S. 2000. Off-line variable substitution for scaling points-to analysis. In Proceedings of the ACM SIGPLAN '00 Conference on Programming Language Design and Implementation, pp. 47-56.]]

Digital Library

Google Scholar

[86]

ROUNTEV, A., MILANOVA, A., AND RYDER, B. G. 2000. Points-to analysis for Java using annotated inclusion constraints. To appear in Proceedings of OOPSLA'01: Conference on Object-Oriented Programming Systems, Languages and Applications. Also available as Rutgers University Department of Computer Science Technical Report DCS-TR-428.]]

Digital Library

Google Scholar

[87]

ROUNTEV, A., RYDER,B.G.,AND LANDI, W. A. 1999. Data-flow analysis of program fragments. In Proceedings of Sixth ACMSIGSOFT Symposium on Foundations of Software Engineering, LNCS 1687, pp. 235-252.]]

Digital Library

Google Scholar

[88]

RUGGIERI,C.AND MURTAGH, T. 1988. Lifetime analysis of dynamically allocated objects. In Conference Record of the Fifteenth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 285-293.]]

Digital Library

Google Scholar

[89]

RUGINA,R.AND RINARD, M. 1999. Pointer analysis for multithreaded programs. In Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pp. 77-90.]]

Digital Library

Google Scholar

[90]

RYDER, B. G. 1983. Incremental data flow analysis. In Conference Record of the Tenth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 167-176.]]

Digital Library

Google Scholar

[91]

RYDER,B.G.AND PAULL, M. C. 1988. Incremental data flow analysis algorithms. ACM Transactions on Programming Languages and Systems 10, 1, 1-50.]]

Digital Library

Google Scholar

[92]

RUF, E. 1995. Context-insensitive alias analysis reconsidered. In Proceedings of the SIGPLAN '95 Conference on Programming Language Design and Implementation, pp. 13-22.]]

Digital Library

Google Scholar

[93]

RUF, E. 1997. Partitioning data flow analysis using types. In Conference Record of the Twenty- Fourth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 15-26.]]

Digital Library

Google Scholar

[94]

SAGIV, S., FRANCEZ, N., RODEH, M., AND WILHELM, R. 1990. A logic-based approach to data flow analysis. In Proceedings of the Second International Workshop in Programming Language Implementation and Logic Programming. pp. 277-292. Volume 456 of Lecture Notes in Computer Science.]]

Digital Library

Google Scholar

[95]

SAGIV, M., REPS,T.,AND WILHELM, R. 1998. Solving shape-analysis problems in languages with destructive updating. ACM Transactions on Programming Languages and Systems 20,1,1- 50.]]

Digital Library

Google Scholar

[96]

SHAPIRO,M.AND HORWITZ, S. 1997a. The effects of the precision of pointer analysis. In Proceedings of the Fourth International Symposium on Static Analysis (SAS'97), pp. 16- 34.]]

Digital Library

Google Scholar

[97]

SHAPIRO,M.AND HORWITZ, S. 1997b. Fast and accurate flow-insensitive points-to analysis. In Conference Record of the Twenty-Fourth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pp. 1--14.]]

Digital Library

Google Scholar

[98]

SHARIR,M.AND PNUELI, A. 1981. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications, S. Muchnick and N. Jones, Ed., Prentice Hall, Englewood, Cliff., pp. 189-234.]]

Google Scholar

[99]

SHIVERS, O. 1988. Control flow analysis in scheme. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, pp. 164-174.]]

Digital Library

Google Scholar

[100]

SINHA, S., HARROLD,M.J.,AND ROTHERMEL, G. 1999. System-dependence-graph-based slicing of programs with arbitrary interprocedural control flow. In Proceedings of the Twenty-First International Conference on Software Engineering, pp. 432-441.]]

Digital Library

Google Scholar

[101]

SPILLMAN, T. 1971. Exposing side effects in a PL-I optimizing compiler. In Proceedings of IFIPS Conference, pp. TA-3-56-TA-3-62.]]

Google Scholar

[102]

STEENSGAARD, B. 1996a. Points-to analysis by type inference of programs with structures and unions. In Proceedings of the Sixth International Conference on Compiler Construction, pp. 136- 150. Also available as LNCS 1060.]]

Digital Library

Google Scholar

[103]

STEENSGAARD, B. 1996b. Points-to analysis in almost linear time. In Conference Record of the Twenty-Third Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Lan-guages, pp. 32-41.]]

Digital Library

Google Scholar

[104]

TIP, F. 1996. A survey of program slicing techniques. Journal of Programming Languages 3,3, pp. 121-189.]]

Google Scholar

[105]

TIP, F., CHOI, J.-D., FIELD,J.,AND RAMALINGAM, G. 1996. Slicing class hierarchies in CCC.InProceedings of OOPSLA'96: Conference on Object-Oriented Programming Systems, Languages and Applications, pp. 179-197.]]

Digital Library

Google Scholar

[106]

TONELLA, P., ANTONIOL, G., FIUTERN, R., AND MERLO, E. 1997. Flow-insensitive CCC pointers and polymorphism analysis and its application to slicing. In Proceedings of the Nineteenth International Conference on Software Engineering (ICSE97), pp. 433-443.]]

Digital Library

Google Scholar

[107]

VENKATESH, G. A. 1991. The semantic approach to program slicing. In Proceedings of the SIG- PLAN '91 Conference on Programming Language Design and Implementation, pp. 107-119.]]

Digital Library

Google Scholar

[108]

WEIHL, W. E. 1980. Interprocedural data flow analysis in the presence of pointers, procedure variables and label variables. Master's Thesis, M.I.T.]]

Google Scholar

[109]

WEISER, M. 1984. Program slicing. IEEE Transactions on Software Engineering SE-10, 4, 352- 357.]]

Digital Library

Google Scholar

[110]

WEYUKER, E. 1994. More experience with data flow testing. IEEE Transactions on Software Engineering 19, 9, 912-919.]]

Digital Library

Google Scholar

[111]

WILSON,R.AND LAM, M. 1995. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the SIGPLAN '95 Conference on Programming Language Design and Implementation, pp. 1-12. Also available as SIGPLAN Notices, Vol. 30, No. 6.]]

Digital Library

Google Scholar

[112]

WOLFE, M. 1989. Optimizing Supercompilers for Supercomputers. The MIT Press, Cambridge, MA.]]

Digital Library

Google Scholar

[113]

YONG, S. H., HORWITZ,S.,AND REPS, T. 1999. Pointer analysis for programs with structures and casting. In Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pp. 91-103.]]

Digital Library

Google Scholar

[114]

YUR, J., RYDER,B.G.,AND LANDI, W. 1999. An incremental flow- and context-sensitive pointer aliasing analysis. In Proceedings of the Twenty-First International Conference on Software Engineering, pp. 442-451.]]

Digital Library

Google Scholar

[115]

YUR, J., RYDER,B.G.,LANDI,W.,AND STOCKS, P. 1997. Incremental analysis of side effects for C software systems. In Proceedings of the Nineteenth International Conference on Software Engineering, pp. 422-432.]]

Digital Library

Google Scholar

[116]

ZHANG, S. 1995. Program decomposition. Student poster presentation at PLDI'95.]]

Google Scholar

[117]

ZHANG, S. 1998. Practical pointer aliasing analyses for C. Ph.D. Thesis, Rugters University. Also available as Dept. of Computer Science Technical Report DCS-TR-367.]]

Digital Library

Google Scholar

[118]

ZHANG, S., RYDER,B.G.,AND LANDI, W. 1996. Program decomposition for pointer aliasing: A step towards practical analyses. In Proceedings of the Fourth Annual ACM SIGSOFT Symposium on the Foundations of Software Engineering, pp. 81-92.]]

Digital Library

Google Scholar

[119]

ZHANG, S., RYDER,B.G.,AND LANDI, W. A. 1998. Experiments with combined analysis for pointer aliasing. In Proceedings of ACM SIGPLAN Workshop on Program Analysis and Software Tools for Engineering, pp. 11-18.]]

Digital Library

Google Scholar

Cited By

View all

Gharat PKhedker UMycroft A(2020)Generalized Points-to GraphsACM Transactions on Programming Languages and Systems10.1145/338209242:2(1-78)Online publication date: 19-May-2020
https://dl.acm.org/doi/10.1145/3382092
Tzannes AHeumann SEloussi LVakilian MAdve VHan M(2019)Region and effect inference for safe parallelismAutomated Software Engineering10.1007/s10515-019-00257-326:2(463-509)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10515-019-00257-3
Gao QMa SShao SSui YZhao GMa LMa XDuan FDeng XZhang SChen XKhomh FRoy CSiegmund J(2018)CoBOTProceedings of the 26th Conference on Program Comprehension10.1145/3196321.3196367(385-388)Online publication date: 28-May-2018
https://dl.acm.org/doi/10.1145/3196321.3196367
Show More Cited By

Index Terms

A schema for interprocedural modification side-effect analysis with pointer aliasing
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis
    2. Program semantics

Recommendations

Interprocedural pointer alias analysis

We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Interprocedural modification side effect analysis with pointer aliasing

We present a new interprocedural modification side effects algorithm for C programs, that can discern side effects through general-purpose pointer usage. Ours is the first complete design and implementation of such an algorithm. Preliminary performance ...
Practical pointer aliasing analysis

Reviews

Reviewer: Uwe Kastens

Interprocedural compile-time analysis of side effects is crucial for compiler optimization and program transformation, as well as for software engineering tools. In the presence of pointers, as in current languages, an accurate analysis of pointer aliasing is needed to determine potential modifications of variables precisely, through function calls. This paper presents variants of methods for pointer analysis, modification analysis, and combinations thereof. In particular, techniques that are sensitive or insensitive with respect to control flow and calling contexts are compared. The second part of the paper evaluates the techniques on a large amount of data taken from a significant set of realistic programs. The two extreme strategies are compared under various views, and cost-precision tradeoffs are carefully elaborated. The main contribution of the paper is its complete coverage of the topic. Methods for analysis of pointer aliasing and modification by side effects are carefully explained using well-chosen examples, an experimental comparison is presented, and a brief overview on numerous contributions on related work is given. The experimental results are not very surprising. For example, the flow- and context-sensitive techniques yield much more precise results than the insensitive variants, but the results of the latter are significantly better than worst-case assumptions made without any analysis. The sensitive analysis needs runtime that is comparable to that of a complete non-optimizing compilation, and is of an order of magnitude larger than that of the insensitive variants. However, the great value of the paper lies in the thorough justification of such observations, based on a large set of data and on different views of presentation. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 23, Issue 2

March 2001

168 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/383043

Editor:
William Pugh
Univ. of Maryland, College Park

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2001

Published in TOPLAS Volume 23, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

119
Total Citations
View Citations
1,091
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)5

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gharat PKhedker UMycroft A(2020)Generalized Points-to GraphsACM Transactions on Programming Languages and Systems10.1145/338209242:2(1-78)Online publication date: 19-May-2020
https://dl.acm.org/doi/10.1145/3382092
Tzannes AHeumann SEloussi LVakilian MAdve VHan M(2019)Region and effect inference for safe parallelismAutomated Software Engineering10.1007/s10515-019-00257-326:2(463-509)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10515-019-00257-3
Gao QMa SShao SSui YZhao GMa LMa XDuan FDeng XZhang SChen XKhomh FRoy CSiegmund J(2018)CoBOTProceedings of the 26th Conference on Program Comprehension10.1145/3196321.3196367(385-388)Online publication date: 28-May-2018
https://dl.acm.org/doi/10.1145/3196321.3196367
Paisante VMaalej MBarbosa LGonnord LQuintão Pereira FFranke BWu YRastello F(2016)Symbolic range analysis of pointersProceedings of the 2016 International Symposium on Code Generation and Optimization10.1145/2854038.2854050(171-181)Online publication date: 29-Feb-2016
https://dl.acm.org/doi/10.1145/2854038.2854050
Tzannes AHeumann SEloussi LVakilian MAdve VHan MCohen MGrunske LWhalen M(2015)Region and effect inference for safe parallelismProceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2015.59(512-523)Online publication date: 9-Nov-2015
https://dl.acm.org/doi/10.1109/ASE.2015.59
Tang XJärvi J(2015)Axioms as generic rewrite rules in C++ with conceptsScience of Computer Programming10.1016/j.scico.2014.05.00697:P3(320-330)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.scico.2014.05.006
Sui YYe DXue J(2014)Detecting Memory Leaks Statically with Full-Sparse Value-Flow AnalysisIEEE Transactions on Software Engineering10.1109/TSE.2014.230231140:2(107-122)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1109/TSE.2014.2302311
Chen NJohnson RDenney EBultan TZeller A(2013)JFlowProceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2013.6693080(202-212)Online publication date: 11-Nov-2013
https://dl.acm.org/doi/10.1109/ASE.2013.6693080
Tao BQian JZhou XBodden EHendren LLam PSherman E(2012)Side-effect analysis with fast escape filterProceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysis10.1145/2259051.2259054(15-20)Online publication date: 14-Jun-2012
https://dl.acm.org/doi/10.1145/2259051.2259054
Zhou HJin DGong Y(2012)An Interval-Based Model for Detecting Software Defect Using Alias AnalysisProceedings of the 2012 19th Asia-Pacific Software Engineering Conference - Volume 0210.1109/APSEC.2012.14(136-144)Online publication date: 4-Dec-2012
https://dl.acm.org/doi/10.1109/APSEC.2012.14
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Interprocedural pointer alias analysis

Interprocedural modification side effect analysis with pointer aliasing

Practical pointer aliasing analysis

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations