article

Open access

Empirical study of optimization techniques for massive slicing

Authors:

Jens KrinkeAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 30, Issue 1

Pages 3 - es

https://doi.org/10.1145/1290520.1290523

Published: 01 November 2007 Publication History

Abstract

This article presents results from a study of techniques that improve the performance of graph-based interprocedural slicing of the System Dependence Graph (SDG). This is useful in “massive slicing” where slices are required for many or all of the possible set of slicing criteria. Several different techniques are considered, including forming strongly connected components, topological sorting, and removing transitive edges.

Data collected from a test bed of just over 1,000,000 lines of code are presented. This data illustrates the impact on computation time of the techniques. Together, the best combination produces a 71% reduction in run-time (and a 64% reduction in memory usage). The complete set of techniques also illustrates the point at which faster computation is not viable due to prohibitive preprocessing costs.

References

[1]

Agrawal, H. and Horgan, J. R. 1990. Dynamic program slicing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (White Plains, NY). ACM, New York, 246--256.

Digital Library

[2]

Anderson, P., Binkley, D., Rosay, G., and Teitelbaum, T. 2001. Flow insensitive points-to sets. In Proceedings of the 1st IEEE Workshop on Source Code Analysis and Manipulation (Florence, Italy). IEEE Computer Society Press, Los Alamitos, CA, 79--89.

[3]

Balmas, F. 2002. Using dependence graphs as a support to document programs. In Proceedings of the 2st IEEE International Workshop on Source Code Analysis and Manipulation (Montreal, Que, Canada). IEEE Computer Society Press, Los Alamitos, CA, 145--154.

Digital Library

[4]

Beszédes, A. and Gyimóthy, T. 2002. Union slices for the approximation of the precise slice. In Proceedings of the IEEE International Conference on Software Maintenance (Montreal, Que, Canada). IEEE Computer Society Press, Los Alamitos, CA, 12--20.

[5]

Bieman, J. M. and Ott, L. M. 1994. Measuring functional cohesion. IEEE Trans. Softw. Engin. 20, 8 (Aug.), 644--657.

Digital Library

[6]

Binkley, D. and Harman, M. 2005a. Forward slices are smaller than backward slices. In Proceedings of the 5th IEEE International Workshop on Source Code Analysis and Manipulation (Budapest, Hungary, Sept. 30--Oct. 1). IEEE Computer Society Press, Los Alamitos, CA, 15--24.

Digital Library

[7]

Binkley, D. and Harman, M. 2005b. Locating dependence clusters and dependence pollution. In Proceedings of the 21st IEEE International Conference on Software Maintenance (Budapest, Hungary, Sept. 30--Oct. 1). IEEE Computer Society Press, Los Alamitos, CA, 177--186.

Digital Library

[8]

Binkley, D. W. 1998. The application of program slicing to regression testing. Inf. Softw. Technol. Special Issue on Program Slicing 40, 11 and 12, 583--594.

[9]

Binkley, D. W. and Gallagher, K. B. 1996. Program slicing. In Adv. Comput. 43 Academic Press, Orlando, FL, 1--50.

[10]

Binkley, D. W. and Harman, M. 2003a. A large-scale empirical study of forward and backward static slice size and context sensitivity. In Proceedings of the IEEE International Conference on Software Maintenance (Amsterdam, The Netherlands). IEEE Computer Society Press, Los Alamitos, CA, 44--53.

Digital Library

[11]

Binkley, D. W. and Harman, M. 2003b. Results from a large--scale study of performance optimization techniques for source code analyses based on graph reachability algorithms. In Proceedings of the IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2003) (Amsterdam, The Netherlands). IEEE Computer Society Press, Los Alamitos, CA, 203--212.

[12]

Binkley, D. W. and Harman, M. 2004. Analysis and visualization of predicate dependence on formal parameters and global variables. IEEE Trans. Softw. Engineering 30, 11, 715--735.

Digital Library

[13]

Binkley, D. W., Harman, M., Raszewski, L. R., and Smith, C. 2000. An empirical study of amorphous slicing as a program comprehension support tool. In Proceedings of the 8th IEEE International Workshop on Program Comprehension (Limerick, Ireland). IEEE Computer Society Press, Los Alamitos, CA, 161--170.

Digital Library

[14]

Binkley, D. W., Horwitz, S., and Reps, T. 1995. Program integration for languages with procedure calls. ACM Trans. Softw. Engin. Meth. 4, 1, 3--35.

Digital Library

[15]

Black, S. E. 2001. Computing ripple effect for software maintenance. J. Softw. Maint. Evol.: Res. Pract. 13, 263--279.

Digital Library

[16]

Canfora, G., Cimitile, A., De Lucia, A., and Lucca, G. A. D. 1994a. Software salvaging based on conditions. In International Conference on Software Maintenance (Victoria, BC, Canada). IEEE Computer Society Press, Los Alamitos, CA, 424--433.

Digital Library

[17]

Canfora, G., Cimitile, A., and Munro, M. 1994b. RE²: Reverse engineering and reuse re-engineering. J. Softw. Mainten.: Res. Pract. 6, 2, 53--72.

[18]

Chilimbi, T., Davidson, B., Larus, J., and Hill, M. 1999. Cache-conscious structure definition. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (Atlanta, GA). ACM, New York, 13--24.

Digital Library

[19]

Cimitile, A., De Lucia, A., and Munro, M. 1995a. Identifying reusable functions using specification driven program slicing: A case study. In Proceedings of the IEEE International Conference on Software Maintenance (Nice, France). IEEE Computer Society Press, Los Alamitos, CA, 124--133.

Digital Library

[20]

Cimitile, A., De Lucia, A., and Munro, M. 1995b. Qualifying reusable functions using symbolic execution. In Proceedings of the 2nd Working Conference on Reverse Engineering (Toronto, Ont., Canada). IEEE Computer Society Press, Los Alamitos, CA, 178--187.

Digital Library

[21]

Danicic, S., De Lucia, A., and Harman, M. 2004. Building executable union slices using conditioned slicing. In Proceedings of the 12th International Workshop on Program Comprehension (Bari, Italy). IEEE Computer Society Press, Los Alamitos, CA, 89--97.

Digital Library

[22]

Eisenbarth, T., Koschke, R., and Vogel, G. 2002. Static trace extraction. In Proceedings of the IEEE Working Conference on Reverse Engineering (Richmond, VA). IEEE Computer Society Press, Los Alamitos, CA, 128--137.

Digital Library

[23]

Fähndrich, M., Foster, J. S., Su, Z., and Aiken, A. 1998. Partial online cycle elimination in inclusion constraint graphs. In Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation (Montréal, Que., Canada). ACM, New York, 85--96.

Digital Library

[24]

Ferrante, J., Ottenstein, K. J., and Warren, J. D. 1987. The program dependence graph and its use in optimization. ACM Trans. Prog. Lang. Syst. 9, 3 (July), 319--349.

Digital Library

[25]

Fischer, C. N. and LeBlanc, R. J. 1988. Crafting a Compiler. Benjamin/Cummings Series in Computer Science. Benjamin/Cummings Publishing Company, Menlo Park, CA.

Digital Library

[26]

Fox, C., Harman, M., Hierons, R. M., and Danicic, S. 2001. Backward conditioning: a new program specialisation technique and its application to program comprehension. In Proceedings of the 9th IEEE International Workshop on Program Comprenhesion (Toronto, Ont., Canada). IEEE Computer Society Press, Los Alamitos, CA, 89--97.

Digital Library

[27]

Gallagher, K. B. and Lyle, J. R. 1991. Using program slicing in software maintenance. IEEE Trans. Softw. Engin. 17, 8 (Aug.), 751--761.

Digital Library

[28]

Harman, M. and Danicic, S. 1995. Using program slicing to simplify testing. Softw. Test. Verif. Reliab. 5, 3 (Sept.), 143--162.

[29]

Harman, M. and Hierons, R. M. 2001. An overview of program slicing. Softw. Focus 2, 3, 85--92.

[30]

Harman, M., Hierons, R. M., Danicic, S., Howroyd, J., Laurence, M., and Fox, C. 2001. Node coarsening calculi for program slicing. In Proceedings of the 8th Working Conference on Reverse Engineering (Stuttgart, Germany). IEEE Computer Society Press, Los Alamitos, CA, 25--34.

Digital Library

[31]

Heintze, N. and Tardieu, O. 2001. Ultra-fast aliasing analysis using CLA: A million lines of C code in a second. In Proceedings of the ACM SIGPLAN '01 Conference on Programming Language Design and Implementation, C. Norris and J. J. B. Fenwick, Eds. ACM SIGPLAN Notices, vol. 36.5. ACM, New York, 254--263.

Digital Library

[32]

Hierons, R. M., Harman, M., and Danicic, S. 1999. Using program slicing to assist in the detection of equivalent mutants. Softw. Test. Verif. Reliab. 9, 4, 233--262.

[33]

Hierons, R. M., Harman, M., Fox, C., Ouarbya, L., and Daoudi, M. 2002. Conditioned slicing supports partition testing. Softw. Test., Verif. Reliab. 12, 23--28.

[34]

Horwitz, S., Pfeiffer, P., and Reps, T. 1989a. Dependence analysis for pointer variables. In Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation (Portland, OR). ACM SIGPLAN Notices, ACM, New York, 28--40.

Digital Library

[35]

Horwitz, S., Prins, J., and Reps, T. 1989b. Integrating non-interfering versions of programs. ACM Trans. Prog. Lang. Syst. 11, 3 (July), 345--387.

Digital Library

[36]

Horwitz, S., Reps, T., and Binkley, D. W. 1988. Interprocedural slicing using dependence graphs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (Atlanta, GA). ACM, New York, 25--46. (Proceedings in SIGPLAN Notices, 23(7), 35--46, 1988.)

Digital Library

[37]

Horwitz, S., Reps, T., and Binkley, D. W. 1990. Interprocedural slicing using dependence graphs. ACM Trans. Progr. Lang. Syst. 12, 1, 26--61.

Digital Library

[38]

Jackson, D. and Rollins, E. J. 1994. Chopping: A generalisation of slicing. Tech. Rep. CMU-CS-94-169, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA. July.

Digital Library

[39]

Koschke, R. 1999. An incremental semi-automatic method for component recovery. In Proceedings: Sixth Working Conference on Reverse Engineering (Atlanta, GA). IEEE Computer Society Press, Los Alamitos, CA, 256--269.

Digital Library

[40]

Krinke, J. 2002. Evaluating context-sensitive slicing and chopping. In IEEE International Conference on Software Maintenance (Montreal, Que., Canada). IEEE Computer Society Press, Los Alamitos, CA, 22--31.

Digital Library

[41]

Krinke, J. 2003. Advanced slicing of sequential and concurrent programs. Ph.D. dissertation, Universität Passau.

[42]

Lee, Y. and Ryder, B. G. 1994. Effectively exploiting parallelism in data flow analysis. J. Supercomput. 8, 3 (Nov.), 233--262.

Digital Library

[43]

Liang, D. and Harrold, M. J. 1999. Efficient points-to analysis for whole-program analysis. In ESEC/FSE '99, O. Nierstrasz and M. Lemoine, Eds. Lecture Notes in Computer Science, vol. 1687. Springer-Verlag /ACM Press, New York, 199--215.

Digital Library

[44]

Longworth, H. D., Ott, L. M., and Smith, M. R. 1986. The relationship between program complexity and slice complexity during debugging tasks. In Proceedings of the Computer Software and Applications Conference (COMPSAC'86). 383--389.

[45]

Meyers, T. and Binkley, D. W. 2004. Slice-based cohesion metrics and software intervention. In Proceedings of the 11th IEEE Working Conference on Reverse Engineering (Delft University of Technology, the Netherlands). IEEE Computer Society Press, Los Alamitos, CA, 256--266.

Digital Library

[46]

Mock, M., Atkinson, D. C., Chambers, C., and Eggers, S. J. 2002. Improving program slicing with dynamic points-to data. In Proceedings of the 10th ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE-02), W. G. Griswold, Ed. ACM, New York, 71--80.

Digital Library

[47]

Müller, H. A. and Klashinsky, K. 1988. Rigi---A system for programming-in-the-large. In Proceedings of the 10th International Conference on Software Engineering (Singapore. Apr. 11--15). IEEE Computer Society Press, Los Alamitos, CA, 80--86.

Digital Library

[48]

Ott, L. M. 1992. Using slice profiles and metrics during software maintenance. In Proceedings of the 10th Annual Software Reliability Symposium. 16--23.

[49]

Ott, L. M. and Bieman, J. M. 1992. Effects of software changes on module cohesion. In Proceedings of the IEEE Conference on Software Maintenance. IEEE Computer Society Press, Los Alamitos, CA, 345--353.

[50]

Ott, L. M. and Thuss, J. J. 1989. The relationship between slices and module cohesion. In Proceedings of the 11th ACM Conference on Software Engineering. ACM, New York, 198--204.

Digital Library

[51]

Ott, L. M. and Thuss, J. J. 1993. Slice based metrics for estimating cohesion. In Proceedings of the IEEE-CS International Metrics Symposium (Baltimore, MA). IEEE Computer Society Press, Los Alamitos, CA, 71--81.

[52]

Ottenstein, K. J. and Ottenstein, L. M. 1984. The program dependence graph in software development environments. Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environmt, SIGPLAN Notices 19, 5, 177--184.

Digital Library

[53]

Podgurski, A. and Clarke, L. 1990. A formal model of program dependences and its implications for software testing, debugging, and maintenance. IEEE Trans. Softw. Engin. 16, 9, 965--79.

Digital Library

[54]

Reps, T. 1998. Program analysis via graph reachability. Inf. Softw. Tech. Special Issue on Program Slicing 40, 11 and 12, 701--726.

[55]

Reps, T., Horwitz, S., Sagiv, M., and Rosay, G. 1994. Speeding up slicing. In Proceedings of the ACM Foundations of Software Engineering (New Orleans, LA). ACM SIGSOFT Software Engineering Notes 19, 5 (December 1994), 11--20.

Digital Library

[56]

Rilling, J., Seffah, A., and Lukas, J. 2001. MOOSE -- A software comprehension framework. In Proceedings of the 5th World Multi-Conference on Systemics, Cybernetics and Informatics (Orlando, FL). 312--318.

[57]

Rountev, A. and Chandra, S. 2000. Off-line variable substitution for scaling points-to analysis. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation. ACM Sigplan Notices, vol. 35.5. ACM, New York, 47--56.

Digital Library

[58]

Snelting, G., Robschink, T., and Krinke, J. 2006. Efficient path conditions in dependence graphs for software safety analysis. ACM Trans. Softw. Engin. Methodol. 15, 4, 410--457.

Digital Library

[59]

Tip, F. 1995. A survey of program slicing techniques. J. Prog. Lang. 3, 3 (Sept.), 121--189.

[60]

Weiser, M. 1979. Program slices: Formal, psychological, and practical investigations of an automatic program abstraction method. Ph.D. dissertation, University of Michigan, Ann Arbor, MI.

Digital Library

[61]

Weiser, M. 1981. Program slicing. In Proceedings of the 5th International Conference on Software Engineering (San Diego, CA). 439--449.

Digital Library

[62]

Weiser, M. 1982. Programmers use slices when debugging. Commun. ACM 25, 7 (July), 446--452.

Digital Library

[63]

Weiser, M. 1984. Program slicing. IEEE Trans. Softw. Engin. 10, 4, 352--357.

Digital Library

[64]

Zhao, J. 2002. Slicing aspect-oriented software. In Proceedings of the 10th IEEE International Workshop on Program Comprehension (Paris, France). IEEE Computer Society Press, Los Alamitos, CA, 351--260.

Digital Library

Cited By

Ojdanic MSoremekun EDegiovanni RPapadakis MLe Traon Y(2023)Mutation Testing in Evolving Systems: Studying the Relevance of Mutants to Code EvolutionACM Transactions on Software Engineering and Methodology10.1145/353078632:1(1-39)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1145/3530786
Ma WChekam TPapadakis MHarman M(2021)MuDeltaProceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00086(897-909)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00086
Netravali RMickens J(2019)ReverbProceedings of the ACM Symposium on Cloud Computing10.1145/3357223.3362733(428-440)Online publication date: 20-Nov-2019
https://dl.acm.org/doi/10.1145/3357223.3362733
Show More Cited By

Index Terms

Recommendations

Actor-based slicing techniques for efficient reduction of Rebeca models

Slicing is a program analysis technique which can be used for reducing the size of the model and avoid state space explosion in model checking. In this work a static slicing technique is proposed for reducing Rebeca models with respect to a property. ...
Slicing-based Reductions for Rebeca

Slicing is a program analysis technique which can be used for reducing the size of the model and avoid state explosion in model checking. In this work a static slicing technique is proposed for reducing Rebeca models with respect to a property. For ...
Properties of Slicing Definitions
SCAM '09: Proceedings of the 2009 Ninth IEEE International Working Conference on Source Code Analysis and Manipulation

Weiser's original papers on slicing defined the concept in an informal way. Since then there have been several attempts to formalise slicing using various formal methods and semantics of programs. In this paper we start by defining some properties that ...

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 30, Issue 1

November 2007

241 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/1290520

Issue’s Table of Contents

Copyright © 2007 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2007

Published in TOPLAS Volume 30, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
605
Total Downloads

Downloads (Last 12 months)45
Downloads (Last 6 weeks)7

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ojdanic MSoremekun EDegiovanni RPapadakis MLe Traon Y(2023)Mutation Testing in Evolving Systems: Studying the Relevance of Mutants to Code EvolutionACM Transactions on Software Engineering and Methodology10.1145/353078632:1(1-39)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1145/3530786
Ma WChekam TPapadakis MHarman M(2021)MuDeltaProceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00086(897-909)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00086
Netravali RMickens J(2019)ReverbProceedings of the ACM Symposium on Cloud Computing10.1145/3357223.3362733(428-440)Online publication date: 20-Nov-2019
https://dl.acm.org/doi/10.1145/3357223.3362733
Armaly AMcMillan C(2016)Pragmatic source code reuse via execution record and replayJournal of Software: Evolution and Process10.1002/smr.179028:8(642-664)Online publication date: 10-May-2016
https://doi.org/10.1002/smr.1790
KASHIMA YISHIO TINOUE K(2015)Comparison of Backward Slicing Techniques for JavaIEICE Transactions on Information and Systems10.1587/transinf.2014EDP7310E98.D:1(119-130)Online publication date: 2015
https://doi.org/10.1587/transinf.2014EDP7310
Beal JViroli M(2015)Formal foundations of sensor network applicationsSIGSPATIAL Special10.1145/2826686.28266937:2(36-42)Online publication date: 17-Sep-2015
https://dl.acm.org/doi/10.1145/2826686.2826693
Resch BBlaschke T(2015)Fusing human and technical sensor dataSIGSPATIAL Special10.1145/2826686.28266927:2(29-35)Online publication date: 17-Sep-2015
https://dl.acm.org/doi/10.1145/2826686.2826692
Nittel S(2015)Real-time sensor data streamsSIGSPATIAL Special10.1145/2826686.28266917:2(22-28)Online publication date: 17-Sep-2015
https://dl.acm.org/doi/10.1145/2826686.2826691
Duckham MZhong XToohey K(2015)Challenges to using decentralized spatial algorithms in the fieldSIGSPATIAL Special10.1145/2826686.28266907:2(14-21)Online publication date: 17-Sep-2015
https://dl.acm.org/doi/10.1145/2826686.2826690
Giffhorn DSnelting G(2015)A new algorithm for low-deterministic securityInternational Journal of Information Security10.1007/s10207-014-0257-614:3(263-287)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s10207-014-0257-6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents