Upwards exposed uses or reachable uses,
is a concept in
compiler theory
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
which occurs in the
copy propagation In compiler theory, copy propagation is the process of replacing the occurrences of targets of direct assignments with their values. A direct assignment is an instruction of the form x = y, which simply assigns the value of y to x.
From the follow ...
stage of compilation.
Uses
During the
copy propagation In compiler theory, copy propagation is the process of replacing the occurrences of targets of direct assignments with their values. A direct assignment is an instruction of the form x = y, which simply assigns the value of y to x.
From the follow ...
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 compiler theory, a reaching definition for a given instruction is an earlier instruction whose target variable can reach (be assigned to) the given one without an intervening assignment. For example, in the following code:
d1 : y := 3
d2 : x : ...
in reaching analysis.
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.
This is also useful for improving code security during the compilation stages.
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.
This also meets the definition of
reaching definition In compiler theory, a reaching definition for a given instruction is an earlier instruction whose target variable can reach (be assigned to) the given one without an intervening assignment. For example, in the following code:
d1 : y := 3
d2 : x : ...
: 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.
See also
*
Dead code elimination
References
{{Reflist, refs=
[{{Cite web , title=Basic Analysis , series=CS 6340: Software Analysis and Testing , last=Harrold , first=Mary Jean , date=Fall 2009 , work=Georgia Tech - College of Computing , publisher=]Georgia Institute of Technology
The Georgia Institute of Technology, commonly referred to as Georgia Tech or, in the state of Georgia, as Tech or The Institute, is a public research university and institute of technology in Atlanta, Georgia. Established in 1885, it is part of ...
, location=Atlanta, Georgia, USA , url=https://www.cc.gatech.edu/~harrold/6340/cs6340_fall2009/Slides/BasicAnalysis3.pdf , access-date=2020-06-12 , url-status=live , archive-url=https://web.archive.org/web/20200620130147/https://www.cc.gatech.edu/~harrold/6340/cs6340_fall2009/Slides/BasicAnalysis3.pdf , archive-date=2020-06-20
[{{Cite book , title=Compilers: Principles, Techniques, and Tools , title-link=Compilers: Principles, Techniques, and Tools , last1=Aho , first1=Alfred Vaino , author-link1=Alfred Vaino Aho , last2=Lam , first2=Monica Sin-Ling , author-link2=Monica Sin-Ling Lam , last3=Sethi , first3=Ravi , author-link3=Ravi Sethi , last4=Ullman , first4=Jeffrey David , author-link4=Jeffrey David Ullman , date=2006 , isbn=0-321-48681-1 , edition=2 , publisher=]Addison-Wesley
Addison-Wesley is an American publisher of textbooks and computer literature. It is an imprint of Pearson PLC, a global publishing and education company. In addition to publishing books, Addison-Wesley also distributes its technical titles through ...
, location=Boston, Massachusetts, USA , oclc=70775643
[{{Cite web , title=Upwards Exposed Uses , last=Kore , first=Aamod , date=2020 , publisher=Department of Computer Science, ]University of Toronto
The University of Toronto (UToronto or U of T) is a public research university in Toronto, Ontario, Canada, located on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution ...
, location=Toronto, Ontario, Canada , url=https://www.cs.toronto.edu/~aamodkore/notes/dfa-tutorial/hw3-exposed-uses.html , access-date=2020-06-12 , url-status=live , archive-url=https://web.archive.org/web/20200620130828/https://www.cs.toronto.edu/~aamodkore/notes/dfa-tutorial/hw3-exposed-uses.html , archive-date=2020-06-20
[{{Cite journal , title=Information-Flow and Data-Flow Analysis of while-Programs , last1=Bergeretti , first1=Jean-Francois , last2=Carré , first2=Bernard A. , date=1985-01-02 , journal= ACM Transactions on Programming Languages and Systems , volume=7 , issue=1 , publisher=]Association for Computing Machinery
The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...
, doi=10.1145/2363.2366 , pages=37–61 , s2cid=19682896 , url=https://dl.acm.org/doi/pdf/10.1145/2363.2366 , access-date=2020-06-20 , url-status=live , archive-url=https://web.archive.org/web/20200620131544/https://dl.acm.org/doi/pdf/10.1145/2363.2366 , archive-date=2020-06-20
Compiler theory
Compiler optimizations
Data-flow analysis