<div>Dear LLVMers,</div><div><br></div><div>   I have been working on Douglas's range analysis, and today, after</div><div>toiling with it for two years, we have a very mature and robust</div><div>implementation, which is publicly available at</div>




<div><a href="http://code.google.com/p/range-analysis/" target="_blank">http://code.google.com/p/range-analysis/</a>. We can, at this point,</div><div>perform range analysis on very large benchmarks in a few seconds. To</div>



<div>give you an idea, we take less than 10 seconds to globally analyze</div>
<div>SPEC 2006 gcc benchmark with function inlining enabled. And the</div><div>analysis is fairly precise. We have a gallery of examples at</div><div><a href="http://code.google.com/p/range-analysis/wiki/gallery" target="_blank">http://code.google.com/p/range-analysis/wiki/gallery</a> that will give</div>




<div>you an idea of what kind of information we can find. Our analysis</div><div>comes together with a dynamic profiler that points the minimum and</div><div>maximum values that each variable assumes during program execution</div>




<div>too. And it uses a live range splitting strategy to obtain data-flow</div><div>sparsity that is lightning fast. It is more than 100x faster than the</div><div>original implementation of SSI in LLVM 2.7, for instance. There are a</div>




<div>number of LLVMers, outside my university, that use our analysis.</div><div>   So, I would like to propose a summer of code that consists in (i)</div><div>integrating our infra-structure in the LLVM main tree, and (ii)</div>




<div>writing a dead-code elimination pass that uses the analysis as a</div><div>client. So far people have been using our analysis to check for buffer</div><div>overflows, and to eliminate array bound checks. Yet, I think there is</div>




<div>a lot of potential to optimizations. Dead code elimination at branches</div><div>would be one such optimization. Given that the analysis is pretty</div><div>mature, I think that it would not be too difficult to integrate it in</div>




<div>the current infra-structure that LLVM offers, e.g., Lazy Values. As</div><div>for dead-code, we already can flag variables that have impossible</div><div>intervals, in which the lower bound is larger than the upper bound.</div>




<div>So, it is only a matter of adapting it to remove this code.</div><div><br></div><div>I would like to hear from you what you think about this Summer of Code</div><div>project. If you think it could be interesting, I will write a proposal</div>




<div>richer in details.</div><div><br></div><div>Sincerely yours,</div><div><br></div><div>Victor</div>