Abstract
Redundancy elimination identifies repeated computations that yield the same results in the course of program execution. It transforms the program code to avoid recomputations by saving the results computed earlier and reusing them, thus speeding up program execution. We distinguish between two different views of redundant computations, resulting in redundancy elimination approaches being designated as either syntax-driven or value-driven. The dominant redundancy elimination concept under the syntax-driven approach is partial redundancy elimination (PRE). We explain why PRE and SSA are intimately related and how a particular version of PRE, called SSAPRE, actually works by exploiting the many useful properties of SSA form. We explain how the SSAPRE algorithm can be adapted to add the speculative flavor. A different version of SSAPRE, called SSUPRE, can also be derived to perform the PRE of store operations. Furthermore, combining the PRE of loads with the PRE stores will accomplish the effects of register promotion. This chapter finishes by discussing the value-driven redundancy elimination approach to contrast it with the syntax-driven approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
All values referred to in this chapter are static values viewed with respect to the program code. A static value can map to different dynamic values during program execution.
- 2.
The opposite of maximal expression tree form is the triplet form in which each arithmetic operation always defines a temporary.
- 3.
Adhering to the SSAPRE convention, we use lower case ϕs in the SSA form of variables and upper case Φs in the SSA form for expressions.
References
Chow, F., et al. (1997). A new algorithm for partial redundancy elimination based on SSA form. In International Conference on Programming Languages Design and Implementation. PLDI ’97 (pp. 273–286).
Dhamdhere, D. M. (2002). E-path_PRE: Partial redundancy made easy. Sigplan Notices, 37(8), 53–65.
Drechsler, K.-H., & Stadel, M. P. (1993). A variation of knoop, rüthing and steffen’s lazy code motion. Sigplan Notices, 28(5), 29–38.
Kennedy, R., et al. (1999). Partial redundancy elimination in SSA form. ACM Transactions on Programming Language and Systems, 21(3), 627–676 (1999).
Knoop, J., Rüthing, O., & Steffen, B. (1992). Lazy code motion. In International Conference on Programming Languages Design and Implementation. PLDI ’92 (pp. 224–234).
Knoop, J., Rüthing, O., & Steffen, B. (1994). Optimal code motion: Theory and practice. ACM Transactions on Programming Language and Systems, 16(4), 1117–1155.
Paleri, V. K., Srikant, Y. N., & Shankar, P. (2003). Partial redundancy elimination: a simple, pragmatic and provably correct algorithm. Science of Programming Programming, 48(1), 1–20.
Xue, J., & Knoop, J. (2006). A fresh look at PRE as a maximum flow problem. In International Conference on Compiler Construction. CC ’06 (pp. 139–154).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Chow, F. (2022). Redundancy Elimination. In: Rastello, F., Bouchez Tichadou, F. (eds) SSA-based Compiler Design. Springer, Cham. https://doi.org/10.1007/978-3-030-80515-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-80515-9_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-80514-2
Online ISBN: 978-3-030-80515-9
eBook Packages: Computer ScienceComputer Science (R0)