[LLVMdev] GSoC - Range Analysis

[Victor Campos]

Dear LLVMers,

   I have been working on Douglas's range analysis, and today, after
toiling with it for two years, we have a very mature and robust
implementation, which is publicly available at
http://code.google.com/p/range-analysis/. We can, at this point,
perform range analysis on very large benchmarks in a few seconds. To
give you an idea, we take less than 10 seconds to globally analyze
SPEC 2006 gcc benchmark with function inlining enabled. And the
analysis is fairly precise. We have a gallery of examples at
http://code.google.com/p/range-analysis/wiki/gallery that will give
you an idea of what kind of information we can find. Our analysis
comes together with a dynamic profiler that points the minimum and
maximum values that each variable assumes during program execution
too. And it uses a live range splitting strategy to obtain data-flow
sparsity that is lightning fast. It is more than 100x faster than the
original implementation of SSI in LLVM 2.7, for instance. There are a
number of LLVMers, outside my university, that use our analysis.
   So, I would like to propose a summer of code that consists in (i)
integrating our infra-structure in the LLVM main tree, and (ii)
writing a dead-code elimination pass that uses the analysis as a
client. So far people have been using our analysis to check for buffer
overflows, and to eliminate array bound checks. Yet, I think there is
a lot of potential to optimizations. Dead code elimination at branches
would be one such optimization. Given that the analysis is pretty
mature, I think that it would not be too difficult to integrate it in
the current infra-structure that LLVM offers, e.g., Lazy Values. As
for dead-code, we already can flag variables that have impossible
intervals, in which the lower bound is larger than the upper bound.
So, it is only a matter of adapting it to remove this code.

I would like to hear from you what you think about this Summer of Code
project. If you think it could be interesting, I will write a proposal
richer in details.

Sincerely yours,

Victor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120329/450d809a/attachment.html>