Value range analysis: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 15:17, 5 October 2024

In computing, in particular compiler construction, value range analysis is a type of data flow analysis that tracks the range (interval) of values that a numeric variable can take on at each point of a program's execution.^[1] The resulting information can be used in optimizations such as redundancy elimination, dead code elimination, instruction selection, etc., but can also be used to improve the safety of programs, e.g. in the detection of buffer overruns.^[2] Techniques for value range analysis typically use symbolic analysis extensively.^[3]

Value range analysis is often implemented in the Intel C++ Compiler and is implemented in GCC.^[4]

References

^ Harrison, William H. (1977). "Compiler Analysis of the Value Ranges for Variables". IEEE Transactions on Software Engineering. 3 (3): 243–250. doi:10.1109/TSE.1977.231133. S2CID 17018610.
^ Wagner, D.; Foster, J. S.; Brewer, E. A.; Aiken, A. (2000). A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities. NDSS.
^ Birch, Johnnie; van Engelen, Robert; Gallivan, Kyle. "Value Range Analysis of Conditionally Updated Variables and Pointers" (PDF).
^ MacLeod, Andrew (28 April 2021). "Value range propagation in GCC with Project Ranger".

[1] Harrison, William H. (1977). "Compiler Analysis of the Value Ranges for Variables". IEEE Transactions on Software Engineering. 3 (3): 243–250. doi:10.1109/TSE.1977.231133. S2CID 17018610.

[2] Wagner, D.; Foster, J. S.; Brewer, E. A.; Aiken, A. (2000). A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities. NDSS.

[3] Birch, Johnnie; van Engelen, Robert; Gallivan, Kyle. "Value Range Analysis of Conditionally Updated Variables and Pointers" (PDF).

[4] MacLeod, Andrew (28 April 2021). "Value range propagation in GCC with Project Ranger".

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
+In [[computing]], in particular [[compiler]] construction, '''value range analysis''' is a type of [[data flow analysis]] that tracks the range (interval) of values that a numeric variable can take on at each point of a program's execution.<ref>{{cite journal |title=Compiler Analysis of the Value Ranges for Variables |first=William H. |last=Harrison |year=1977 |journal=IEEE Transactions on Software Engineering |volume=3 |issue=3 |pages=243–250 |doi=10.1109/TSE.1977.231133|s2cid=17018610 }}</ref>
-{{New page}}
+The resulting information can be used in optimizations such as redundancy elimination, [[dead code elimination]], instruction selection, etc., but can also be used to improve the safety of programs, e.g. in the detection of [[Buffer overflow|buffer overruns]].<ref>{{cite conference |last1=Wagner |first1=D. |last2=Foster |first2=J. S. |last3=Brewer |first3=E. A. |last4=Aiken |first4=A. |year=2000 |title=A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities |conference=NDSS}}</ref> Techniques for value range analysis typically use [[Symbolic computation|symbolic analysis]] extensively.<ref>{{cite web |first1=Johnnie |last1=Birch |first2=Robert |last2=van Engelen |first3=Kyle |last3=Gallivan |title=Value Range Analysis of Conditionally Updated Variables and Pointers |url=http://www.cs.fsu.edu/~engelen/cpcpaper.pdf}}</ref>
-'''Value range analysis''' is a technique for analysis on compiler optimizations like redundancy elimination, dead code elimination, instruction selection, etc. that tracks various properties of values defined and changed in a program, such as min-max integer bounds and set-reset bits.<ref>{{cite web|title=Writing a Client Pass|url=http://code.google.com/p/range-analysis/wiki/HowToUseRangeAnalysisInAnotherPass|accessdate=9 February 2014}}</ref>
-Value range analysis is often implemented in the Intel compiler and is to be implemented in GNU GCC, etc.
+Value range analysis is often implemented in the [[Intel C++ Compiler]] and is implemented in [[GNU Compiler Collection|GCC]].<ref>{{cite web | first1=Andrew |last1=MacLeod |title=Value range propagation in GCC with Project Ranger |date=28 April 2021 |url=https://developers.redhat.com/blog/2021/04/28/value-range-propagation-in-gcc-with-project-ranger}}</ref>
 == References ==
 {{Reflist}}
+{{Compiler optimizations}}
+[[Category:Static program analysis]]
 [[Category:Compiler optimizations]]

v t e Compiler optimizations
Basic block	Peephole optimization Local value numbering
Loop	Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction
Data-flow analysis	Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Upwards exposed uses Use-define chain Reaching definitions
SSA-based	Global value numbering Sparse conditional constant propagation
Code generation	Instruction scheduling Instruction selection Register allocation Rematerialization
Functional	Deforestation Tail-call elimination
Global	Interprocedural optimization
Other	Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization
Static analysis	Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis