Dear LLVM community,
I would like to contribute to LLVM in the Google Summer of Code project. My proposal is listed below. Please let me know your comments.
Adding Range Analysis to LLVM
Abstract
The objective of this work is patch our implementation of range analysis into LLVM. I have a running implementation of range analysis in LLVM, but it is not currently part of the main distribution. I propose to integrate our range analysis implementation into the Lazy Value Info (LVI) interface that LLVM provides. Range analysis finds the intervals of values that may be bound to the integer variables during the execution of programs and is useful in several scenarios: constant propagation, detection of potential buffer overflow attacks, dead branch elimination, array bound check elimination, elimination of overflow tests in scripting languages such as JavaScript and Lua, etc.
Objective
The objective of this project is to augment LLVM with range analysis. We will do this integration by patching the current implementation of range analysis that we have onto the Lazy Value Info (LVI) interface that LLVM already provides. In addition, we will develop new optimizations using LVI. In particular, we will provide a pass that performs conditional constant propagation [5], and elimination of dead-branches.
Criteria of Success
- To improve substantially the precision of the current implementation of LVI. Currently, LVI’s interface only allows a client to know if a variable contains a constant. We want to allow LVI to report that a variable either contains a constant, or a known-range.
- To improve the current implementation of constant propagation that LLVM uses. We hope to obtain a small performance gain on the C benchmarks in the LLVM test suite, and a larger gain on Java programs that are compiled using VMKit.
- To improve the implementation of JumpThreading, in such a way that more dead-branches will be eliminated. Again, we hope to achieve a small speed-up on the C benchmarks, and a larger speed-up on the Java benchmarks.
Background
Range Analysis is a technique that maps integer variables to the possible ranges of values that they may assume through out the execution of a program. Thus, for each integer variable, a range analysis determines its lower and upper limits. A very simple range analysis would, for instance, map each variable to the limits imposed by its type. That is, an 8-bit unsigned integer variable can be correctly mapped to the interval [0, 255], and an 16-bit signed integer can be mapped to [-32767, 32766]. However, the precision of this analysis can greatly be improved from information inferred from the program text.
Ideally this range should be as constrained as possible, so that an optimizing compiler could learn more information about each variable. However, the range analysis must be conservative, that is, it will only constraint the range of a variable if it can prove that it is safe to do so. As an example, consider the program:
i = read();
if (i < 10) {
print (i + 1);
else {
print(i - 1);
}
In this program we know, from the conditional test, that the value of ‘i’ in the true side of the branch is in the range [-INF, 9], and in the false side is in the range [10, +INF].
During the Summer of Code 2010 I have designed and implemented, under the orientation of Duncan Sands, a non-iterative range analysis algorithm. Our implementation is currently fully functional, been able to analyze the whole LLVM test suite. For more details, see [4]. However, this implementation has never been integrated into the LLVM main trunc, for two reasons:
- We use an intermediate representation called extended static assignment form [6], which the LLVM contributors were reluctant to use;
- During the SoC 2010 we did not have time to completely finish our implementation, and runtime numbers were available only by the end of 2010.
- There was not really an infra-structure already in place in LLVM to take benefit of our analysis.
In order to address the first item, we propose to integrate the intermediate representation directly into our analysis, yet, as a module that can be used in separate by other clients, if necessary. We are splitting the live ranges of variables using single-arity phi-functions, which are automatically handled by the SSA elimination pass that LLVM already includes. This live range splitting is only necessary for greater precision. We can do our live range analysis without it, although the results are less precise. A previous Summer of Code, authored by Andre Tavares, has shown that the e-SSA form increases the number of phi-functions in the program code by less than 10%, and it is very fast to build [6].
The second item of our list of hindrances is no longer a problem. Our implementation is ready for use. We have been able to analyze the whole LLVM test suite, plus SPEC CPU 2006 - over 4 million LLVM bytecoes - in 44 seconds on a 2.4GHz machine. We obtain non-trivial bit size reductions for the small benchmarks, having results that match those found by previous, non-conservative works, such as Stephenson’s et al’s [2]. Moreover, our implementation is based on a very modern algorithm, by Su and Wagner [1], augmented with Gawlitza’s technique to handle cycles [3]. We believe that this is the fastest implementation of such an analysis.
Finally, the third item is also no longer a problem. Presently LLVM offers the Lazy Value Info interface that reports when variables are constants. The current LVI implementation also provides infra-structure to deal with ranges of integer intervals. However, it does not contain a fully functional implementation yet, an omission that we hope to fix with this project.
Timeline and Testing Methodology
- Change the LVI interface, adding a new method to it: getRange(Value *V), so that we can, not only know if a variable is a constant, but also know its range of values whenever it is not a constant.
- Change the implementation of the prototype range analysis that LVI already uses, so that it will use our implementation.
- Implement the sparse conditional constant propagation to use LVI. This, in addition to JumpThreading will be another client that will use LVI.
- Run experiments on the LLVM test suite to verify that our new optimization improves on the current dead branch elimination pass that LLVM already uses.
- Run experiments using VMKit, to check the impact of dead branch elimination on Java programs. We hope to deliver better performance numbers in this case because Java, as a memory safe language, is notorious for using many checks to ensure that memory is used only in ways that obey the contract of the variable types.
Biograph
I am currently a third year Computer Science student at the Federal University of Minas Gerais, Brazil, and I work as a research assistant at the Programming Languages Lab (LLP), in that university.
I believe I am a good candidate to work in the proposed project because I have already a good knowledge of LLVM. I have implemented range analysis, and currently it can find the ranges of integer variables used in the programs. In addition to this, I have been working as a programmer for three years, before joining the LLP as a research assistant, and I am experienced with C++, the language in which LLVM is implemented. Furthermore, I am a student at a very good university (UFMG). To ground this statement I would like to point that the Department of Computer Science of UFMG got the best mark in the Brazilian National Undergrad Exam (ENADE). Finally, I work on a lab in which three other students work with LLVM. We had three Summer of Codes on LLVM in the past, and a number of papers have been published out of these experiences.
References
-
A Class of Polynomially Solvable Range Constraints for Interval Analysis without Widenings and Narrowings, Zhendong Su and David Wagner, In Theoretical Computer Science, Volume 345 , Issue 1, 2005.
-
Bitwidth Analysis with Application to Silicon Compilation, Mark Stephenson, Jonathan Babb, and Saman Amarasinghe, In Proceedings of the SIGPLAN conference on Programming Language Design and Implementation, 2000.
-
Polynomial Precise Interval Analysis Revisited. Thomas Gawlitza, Jérôme Leroux, Jan Reineke, Helmut Seidl, Grégoire Sutre, Reinhard Wilhelm: Efficient Algorithms 2009: 422-437
-
Linear Time Range Analysis with Affine Constraints. Douglas do Couto Teixeira and Fernando Magno Quintao Pereira (http://homepages.dcc.ufmg.br/~douglas/projects/RangeAnalysis/RangeAnalysis.paper.pdf)
-
Constant propagation with conditional branches. Mark N. Wegman and F. Kenneth Zadeck, In ACM Transactions on Programming Languages and Systems (TOPLAS), 181-210, 1991.
-
Efficient SSI Conversion. André Luiz C. Tavares, Fernando Magno Quintão Pereira, Mariza A. S. Bigonha and Roberto S. Bigonha. Simpósio Brasileiro de Linguagens de Programação. 2010.
-
ABCD: eliminating array bounds checks on demand, Rajkslav Bodik, Rajiv Gupta and Vivek Sarkar, In Proceedings of the SIGPLAN conference on Programming Language Design and Implementation, 2000.
Contact Info
Name: Douglas do Couto Teixeira
e-mail 1: douglas at dcc dot ufmg dot br
e-mail 2: douglasdocouto at gmail dot com