Partial dead code elimination using extended value graph

Munehiro Takimoto, Kenichi Harada

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

This paper presents an efficient and effective code optimization algorithm for eliminating partially dead assignments, which become redundant on execution of specific program paths. It is one of the most aggressive compiling techniques, including invariant code motion from loop bodies. Since the traditional techniques proposed to this optimization would produce the second-order effects such as sinking-sinking effects, they should be repeatedly applied to eliminate dead code completely, paying higher computation cost. Furthermore, there is a restriction that assignments sunk to a join point on ow of control must be lexically identical. Our technique proposed here can eliminate possibly more dead assignments without the restriction at join points, using an explicit representation of data dependence relations within a program in a form of SSA (Static Single Assignment). Such representation called Extended Value Graph (EVG), shows the computationally equivalent structure among assignments before and after moving them on the control ow graph. We can get the final result directly by once application of this technique, because it can capture the second-order effects as the main effects, based on EVG.

Original languageEnglish
Title of host publicationStatic Analysis - 6th International Symposium, SAS 1999, Proceedings
EditorsGilberto File, Agostino Cortesi
PublisherSpringer Verlag
Pages179-193
Number of pages15
ISBN (Print)3540664599, 9783540664598
DOIs
Publication statusPublished - 1 Jan 1999
Event6th International Symposium on Static Analysis, SAS 1999 - Venice, Italy
Duration: 22 Sep 199924 Sep 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1694
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Symposium on Static Analysis, SAS 1999
CountryItaly
CityVenice
Period22/09/9924/09/99

    Fingerprint

Cite this

Takimoto, M., & Harada, K. (1999). Partial dead code elimination using extended value graph. In G. File, & A. Cortesi (Eds.), Static Analysis - 6th International Symposium, SAS 1999, Proceedings (pp. 179-193). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1694). Springer Verlag. https://doi.org/10.1007/3-540-48294-6_12