Definite assignment analysis
In computer science, definite assignment analysis is a data-flow analysis used by compilers to conservatively ensure that a variable or location is always assigned to before it is read.
Motivation
In C and C++ programs, a source of particularly difficult-to-diagnose errors is the nondeterministic behavior that results from reading uninitialized variables; this behavior can vary between platforms, builds, and even from run to run.
There are two common ways to solve this problem. One is to ensure that all locations are written before they are read. Rice's theorem establishes that this problem cannot be solved in general for all programs; however, it is possible to create a conservative (imprecise) analysis that will accept only programs that satisfy this constraint, while rejecting some correct programs, and definite assignment analysis is such an analysis. The Java[1] and C#[2] programming language specifications require that the compiler report a compile-time error if the analysis fails. Both languages require a specific form of the analysis that is spelled out in meticulous detail. In Java, this analysis was formalized by Stärk et al[3], and some correct programs are rejected and must be altered to introduce explicit unnecessary assignments. In C#, due to other language restrictions, this analysis is precise as well as sound, and was formalized by Fruja.[4]
The second way to solve the problem is to automatically initialize all locations to some fixed, predictable value at the point at which they are defined, but this introduces new assignments that may impede performance. In this case, definite assignment analysis enables a compiler optimization where redundant assignments — assignments followed only by other assignments with no possible intervening reads — can be eliminated. In this case, no programs are rejected, but programs for which the analysis fails to recognize definite assignment may contain redundant initialization. The Common Language Infrastructure relies on this approach.[5]
Terminology
A variable or location can be said to be in one of three states at any given point in the program:
- Definitely assigned: The variable is known with certainty to be assigned.
- Definitely unassigned: The variable is known with certainty to be unassigned.
- Unknown: The variable may be assigned or unassigned; the analysis is not precise enough to determine which.
The analysis
References
- ^ "The Java Language Specification, 3rd Edition". pp. Chapter 16 (pp.527–552). Retrieved Dec 2.
{{cite web}}: Check date values in:|accessdate=(help); Unknown parameter|accessyear=ignored (|access-date=suggested) (help); Unknown parameter|authors=ignored (help) - ^ "Standard ECMA-334, C# Language Specification". ECMA International. pp. Section 12.3 (pp.122–133). Retrieved Dec 2.
{{cite web}}: Check date values in:|accessdate=(help); Unknown parameter|accessyear=ignored (|access-date=suggested) (help) - ^ Stärk, Robert F. (2001). Java and the Java Virtual Machine: Definition, Verification, Validation. Secaucus, NJ, USA: Springer-Verlag New York, Inc. pp. Section 8.3. ISBN 3540420886.
{{cite book}}: Unknown parameter|coauthors=ignored (|author=suggested) (help) - ^ Fruja, Nicu G. (2004). "The Correctness of the Definite Assignment Analysis in C#". Journal of Object Technology. 3 (9): 29–52. Retrieved 2008-12-02.
We actually prove more than correctness: we show that the solution of the analysis is a perfect solution (and not only a safe approximation).
{{cite journal}}: Unknown parameter|month=ignored (help) - ^ "Standard ECMA-335, Common Language Infrastructure (CLI)". ECMA International. pp. Section 1.8.1.1 (Partition III, pg. 19). Retrieved Dec 2.
{{cite web}}: Check date values in:|accessdate=(help); Unknown parameter|accessyear=ignored (|access-date=suggested) (help)