ABSTRACT
We present an approach for optimizing programs that uncovers additional opportunities for optimization of a statement by predicating the statement. In this paper predication algorithms for achieving partial dead code elimination (PDE) are presented. The process of predication embeds a statement in a control flow structure such that the statement is executed only if the execution follows a path along which the value computed by the statement is live. The control flow restructuring performed to achieve predication is expressed through slicing transformations. This approach achieves PDE that is not realizable by existing algorithms. We prove that our algorithm never increases the operation count along any path, and that for acyclic code all partially dead statements are eliminated. The slicing transformation that achieves predication introduces into the program additional conditional branches. These branches are eliminated in a branch deletion step based upon code duplication. We also show how PDE can be used by acyclic schedulers for VLIW processors to reduce critical path lengths along frequently executed paths.
- 1.Rastislav Boch3c, Rajiv Gupta, and Mary Lou Sofia. lnterprocedural conditional branch elimination. SIG- PLAN Notices, 1997. Proceedings of the A CM SIG- PLAN '97 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 2.Preston Briggs and Keith D. Cooper. Effective partial redundancy elimination. SIGPLAN Notices, 29(6):159- 170, June 1994. Proceedings of the A CM SIGPLAN '94 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 3.Pohua P. Chang, Scott A. Mahlke, and Wen-Mei W. Hwu. Using profile information to assist dassic code optimizations. Software-Practice and Experience, 21(12):1301-1321, December 1991. Google ScholarDigital Library
- 4.Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark K. Wegman, and F. Kenneth Zadeck. An efficient method of computing static single assignment form. In 16th Annual A CM Symposium on Principles of Programming Languages, pages 25-35, 1989. Google ScholarDigital Library
- 5.James C. Dehnert, Peter Y.-T. Hsu, and Joseph P. Bratt. Overlapped loop support in the Cydra 5. In Proceedings of the Third International Conference on Architectural Support for Programming Languages and Operating Systems, pages 26-38, Boston, Massachusetts, 1989. Google ScholarDigital Library
- 6.Scott A. Mahlke et al. Effective compiler support for predicated execution using the hyperblock. In ~Jth Annual IEEE/A CM International Symposium on Microarchitecture, November 1992. Google ScholarDigital Library
- 7.Wen-reel W. Hwu et al. The superblock: An effective technique for VLIW and superscalar compilation. The Journal of Supercomputing, 7(1):229-248, January 1993. Google ScholarDigital Library
- 8.Lawrence Feigen, David Klappholz, Robert Cassazza, and Xing Xue. The revival transformation. In Conference Record of POPL '9j: 21st A CM SIGPLAN- SIGACT Symposium on Principles of Programming Languages, pages 421-434, Portland, Oregon, January 1994. Google ScholarDigital Library
- 9.Joseph A. Fisher. Trace scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, 30(7), July 1981.Google ScholarDigital Library
- 10.Rajiv Gupta and Mary Lou Sofia. Region scheduling: An approach for detecting and redistributing paranelism. IEEE Transactions on Software Engineering, 16(4):421-431, April 1990. Google ScholarDigital Library
- 11.Susan Horwitz, Alan J. Demers, and Tim Teitelbaum. An efficient general iterative algorithm for datafiow analysis. Acta lnformatica, 24(6):679-694, 1987. Google ScholarDigital Library
- 12.Vinod Kathail, Michael S. Schlamker, and B. Ramakrishna Rau. HPL PlayDoh architecture specification: Version 1.0. Technical Report HPL-93-80, Hewlett- Packard Laboratories, February 1994.Google Scholar
- 13.Jells Knoop, Oliver Riithing, and Bernhard Steffen. Partial dead code elimination. SIGPLAN Notices, 29(6):147-158, June 1994. Proceedings of the ACM SIGPLAN '9$ Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 14.Scott A. Mahlke, William Y. Chen, Wen-reel W. Hwu, B. Ramakrishna Rau, and Michael S. Schlansker. Sentinel scheduling for VLIW and superscalar processors. In Proceedings of the Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 238-247, Boston, Massachusetts, 1992. Google ScholarDigital Library
- 15.Frank Mueller and David B. Whalley. Avoiding conditional branches by code replication. SIGPLAN Norices, 30(6):56--66, June 1995. Proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 16.Michael S. Schlansker and Vinod Kathail. Critical path reduction for scalar programs. In ~8th Annual IEEE/ACM International Symposium on Microarchitecture, Ann Arbor, Michigan, November 1995. Google ScholarDigital Library
- 17.Bernhard Steffen. Property oriented expansion. In SAS/ALP/PLILP'96, pages 22-41, Aachen (D), September 1996. Springer Verlag. Proc. Int. Static Analysis Symposium (SAS'96). Google Scholar
- 18.Nancy J. Warter, Scott A. Mahlke, Wen mei W. Hwu, and B. Ramakrishna Rau. Reverse if-conversion. SIG- PLAN Notices, 28(6):290-299, June 1993. Proceedings of the A CM SIGPLAN '93 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 19.Mark Weiser. Program slicing. IEEE Transactions on Software Engineering, 10(4):352-357, August 1984.Google ScholarDigital Library
Index Terms
- Partial dead code elimination using slicing transformations
Recommendations
Partial dead code elimination
A new aggressive algorithm for the elimination of partially dead code is presented, i.e., of code which is only dead on some program paths. Besides being more powerful than the usual approaches to dead code elimination, this algorithm is optimal in the ...
Partial dead code elimination using slicing transformations
We present an approach for optimizing programs that uncovers additional opportunities for optimization of a statement by predicating the statement. In this paper predication algorithms for achieving partial dead code elimination (PDE) are presented. The ...
Partial dead code elimination on predicated code regions
This paper presents the design, implementation and experimental evaluation of a practical region-based partial dead code elimination (PDE) algorithm on predicated code in the Open Research Compiler framework. Existing PDE algorithms are not applicable ...
Comments