Abstract
The role of liveness analysis is to determine, for all variables, the set of program points where these variables are live, i.e., where their values are potentially used by subsequent operations. For strict SSA form programs, the live range of a variable has valuable properties that can be expressed in terms of the loop nesting forest of the CFG and its corresponding directed acyclic graph, the forward-CFG. A direct consequence of this property is the possible design of a data-flow algorithm that, as opposed to standard approaches, computes liveness sets without the requirement of any iteration to reach a fixed point: at most, two passes over the CFG are necessary. Another application of this property is the design of a simple liveness check algorithm, which in contrast to classical data-flow analysis, does not provide the set of variables live at a block, but provides a query system to answer questions such as “Is variable v live at location q?” After detailing the aforementioned property, this chapter illustrates how the use of strict SSA can both simplify and accelerate liveness analysis. For this purpose, several liveness set and liveness check algorithms are provided.
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
References
Aho, A. V., Sethi, R., & Ullman, J. D. (1986). Compilers: Principles, techniques, and tools. Addison-Wesley series in computer science/World student series edition.
Janssen, J., & Corporaal, H. (1997). Making graphs reducible with controlled node splitting. ACM Transactions on Programming Language and Systems, 19, 1031–1052.
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
Boissinot, B., Rastello, F. (2022). Liveness. In: Rastello, F., Bouchez Tichadou, F. (eds) SSA-based Compiler Design. Springer, Cham. https://doi.org/10.1007/978-3-030-80515-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-80515-9_9
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)