Upwards exposed uses
Upwards exposed uses or reachable uses,[1] is a concept in compiler theory which occurs in the copy propagation stage of compilation.[2]
Uses
During the copy propagation stage of program compilation, instances of a target are replaced with assignments to their values. During this process, it is necessary for the compiler to understand which instances of a target are being accessed so that appropriate substitution may occur, related to the concept of reaching definition in reaching analysis.[3] This is done with the purpose of simplifying code before execution: if the number of upwards exposed uses of an assignment is zero, it does not contribute to the end result of the code and can be safely removed.[1] This is also useful for improving code security during the compilation stages.[4]
Example
Consider the following pseudocode:
x = 1
y = z
if False:
x = 0
else:
x = y + 2
It is safe to assume that line 5 will never occur, as demonstrated by the number of upwards exposed uses for this point being zero. This can therefore be simplified:
y = z
x = z + 2
This leads to an end result which is less complex to compile, and more efficient to run.[2] This also meets the definition of reaching definition: In this context, upwards flow analysis was the technique used to demonstrate the needs for reaching definition. Additional techniques allow for more complex analysis of more deeply intertwined or complex control flow problems, such as those with various forms of loops.[4]
See also
References
- ^ a b Harrold, Mary Jean (Fall 2009). "Basic Analysis" (PDF). Georgia Tech - College of Computing. CS 6340: Software Analysis and Testing. Atlanta, Georgia, USA: Georgia Institute of Technology. Archived (PDF) from the original on 2020-06-20. Retrieved 2020-06-12.
- ^ a b Aho, Alfred Vaino; Lam, Monica Sin-Ling; Sethi, Ravi; Ullman, Jeffrey David (2006). Compilers: Principles, Techniques, and Tools (2 ed.). Boston, Massachusetts, USA: Addison-Wesley. ISBN 0-321-48681-1. OCLC 70775643.
- ^ Kore, Aamod (2020). "Upwards Exposed Uses". Toronto, Ontario, Canada: Department of Computer Science, University of Toronto. Archived from the original on 2020-06-20. Retrieved 2020-06-12.
- ^ a b Bergeretti, Jean-Francois; Carré, Bernard A. (1985-01-02). "Information-Flow and Data-Flow Analysis of while-Programs". ACM Transactions on Programming Languages and Systems. 7 (1). Association for Computing Machinery: 37–61. doi:10.1145/2363.2366. Archived from the original on 2020-06-20. Retrieved 2020-06-20.