[LLVMdev] Summer of Code

[Nuno Lopes]

>> Well, there are many other applications. In short, I would like to know 
>> if
>> the LLVM community would be interested in such a project. I have been
>> working on this for two months, and I am pretty confident I can implement
>> a good range analysis. I am basing my work on a paper by Zhendong and
>> Wagner: "A class of polynomially solvable range constraints for interval
>> analysis without widenings". I have opted for this work, instead of
>> Stephenson's more well known paper because I found Zhendong's easier to
>> understand and implement. As I told you, I can already infer correct
>> ranges on very simple loops, such as:
>>
>
> I believe the SAFECode project (http://safecode.cs.illinois.edu) could
> benefit from a strong range analysis since we want to do better static
> array bounds checking.  Range analysis could also benefit our points-to
> analysis algorithm.

I second that. I could also find several uses for such an analysis. I wrote 
a very simple one for llvm 2.6, but it doesn't work with trunk anymore. 
Integrating a range analysis in llvm comes very handy to implement several 
optimizations.


> I have a few questions about your proposed analysis:
>
> 1) Would your range analysis be more accurate or work in more scenarios
> than the current SCEV pass?  Is it primarily designed for finding value
> ranges within loops, or can it find accurate value ranges for values
> outside of loops, too?

As far I as understand, it would subsume SCEV (by maybe reusing its code). I 
think a good interface for this analsysis would follow alias analysis, like 
Value* -> range. Also, will it be path- or flow-sensitive?


> 2) Would your analysis be intra-procedural or inter-procedural?

If inter-procedural, it should be optional.

Nuno