Floating Point Range Checks in the LLVM Compiler
The presence of a framework for range analysis of floating point variables in LLVM will be very useful for many applications such as vectorisation, safety checks, dead branch removals and many more. Currently LLVM includes only the range analysis for integer values. The aim of this project is to implement a similar static analysis pass for floating point variables which can return guaranteed ranges of floating point variables in the program.
The objective of this project is to add a range analysis pass for floating point numbers into LLVM. This pass would return the ranges within which a given floating point variable lies. The project will also tweak some existing passes such as the Auto-Vectorization pass SLPVectorizer to demonstrate the application of this floating point range analysis.
As given in [1] the implementation of sqrt in Julia checks whether the argument is positive or not. These checks prevent the vectorisation of the function, but in most cases such as sqrt(x*x+y*y) the argument can be argued to be positive and the check be removed to allow for vectorisation. Range analysis of floating point variables will enable such applications.
int foo(float a) {
if (a > 5.0) {
if (a > 3.0) {
return 2;
}
}
return 101;
}
int bar(float a) {
if (a > 3.0) {
if (a > 5.0) {
return 2;
}
}
The inspiration for this project came from a post [1] on the mailing list by Arch Robinson, who pointed out a corresponding issue in the Julia compiler when trying to vectorize functions such as sqrt which are implemented using conditional checks. The discussion in the mailing list gives good support for the idea to be implemented in LLVM.
In relation to range analysis, I have looked through various papers [3, 4, 5, 9] but I feel that the approach mentioned by Arch in the mailing list, along with his code snippet, is the most feasible approach at this point of time. During the project timeline I would also do a comparison of these different methods before deciding on the approach for implementation.
A floating point range analysis framework is present in the Frama-C [10] static analysis tool developed in INRIA, France. The above tool is able to handle some basic cases of floating point range analysis. Understanding the implementation of this framework would serve as a good starting point for this project.
I have started to write the predicate rules for floating point arithmetic as lattice equations involving the values {-inf,<0,-0,+0,>0,+inf,-nan,+nan}. These equations are mainly derived from Dr. Goldberg’s paper on floating points [7] as well as the 2008 IEEE-754 standard for Floating Point Arithmetic [8].
I have a basic understanding of the integer range analysis currently in the LazyValueInfo pass in LLVM. The plan is to modify the pass sufficiently to enable floating point range checks and make this data available to other passes that use LazyValueInfo.
There might also be need to introduce fast-math flags to floating point operations in the IR to enhance the functionality and accuracy of the range analysis pass.
The testing methodology for this project can be broadly divided into 2 phases.
The first phase of testing would include the testing of the analysis pass in isolation to check the correctness of the ranges returned. This would be done with custom examples with ranges manually checked by me. Care would be taken to make the test cases exhaustive to handle tough cases.
The second phase of testing would be to test the use of the range analysis information in the SLPVectorizer pass to enable vectorisation of sqrt in Julia in cases when the argument is positive. Further tests can be done to check the usefulness of the range information on common FP benchmarks.
Each of these tests cases would also be added to the LLVM test framework.
Weeks 1,2,3 - Understanding the existing approaches as discussed and evaluating them.
Weeks 4,5 - Coming with proper provable predicates to handle floating point arithmetic range analysis.
Weeks 6 - Deeper understanding of LazyValueInfo pass
Weeks 7,8,9,10 - Implementation of the range analysis and changes to at least one pass using LVI.
Weeks 11,12 - Testing and documentation.
I am final year undergraduate student at Indian Institute of Technology Hyderabad (IIT Hyderabad). I have a really good academic background throughout my academic life, and have initially started researching in the field of computer networking, especially software defined networking. I worked on a research paper which was published at ICCCN 2014, and also on a research project at University of Southern California on implementation of a measurement framework in OpenVSwitch kernel module.
I recently started working in the field of compilers and my first project began with writing a front end for LLVM for the Cool language developed at Stanford [2]. I also have developed a good understanding of the LLVM code base and have a looked through some optimisation passes such as the BasicAliasAnalysis and ScalarEvolution pass.
I am proficient in C and C++ and have good code browsing skills.
Since I would be graduating in the month of May, I will have only GSoC in my hands during the summer, and hence will be able to devote my full attention towards it.
Please find my resume at the link for further details.