Hi, Gratian,<br><br>   I did that Summer of Code. I used a different algorithm than Patterson's. It is a constraint system by Su and Wagner, which is more modern, and has some advantages over older works. In particular, it is non-iterative. I found it very hard to compare it with Patterson's analysis, because there is not much description in that paper. However, there is another paper, by Stephenson, which gives a nice description of an iterative analysis. Although I have not compared it with an implementation of Stephenson's algo yet, I believe Su's technique would converge much faster. <br>


<br>I have an explanation about our implementation here: (<a href="http://homepages.dcc.ufmg.br/%7Edouglas/RangeAnalysis.html" target="_blank">http://homepages.dcc.ufmg.br/~douglas/RangeAnalysis.html</a>). We have been able to apply it on the whole LLVM test suite, and also on the SPEC CPU 2006 programs. Results are good for small programs (about 40% bitwidth reduction in Stanford benchmark, for instance), but are a bit disappoint for big programs (around 8% reduction for SPEC CPU 2006). In any case, Stephenson's algo probably would lead to the same results, although it does one thing that Su does not do: Stephenson assume that the program is correct, so, upon having a use like a[v], it assumes that v is inside the boundaries of the array, and uses this information to constraint the value range of v a bit more.<br>


<br>My work is not part of the LLVM mainline yet. But I would be happy to contribute with the code of my range analysis implementation if it can help you in something else.<br><br>Best,<br><br>Douglas<br><br><div class="gmail_quote">

On Sun, Feb 20, 2011 at 2:30 PM, Gratian Lup <span dir="ltr"><<a href="mailto:lgratian@gmail.com" target="_blank">lgratian@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">


<span style="border-collapse: collapse; font-family: arial,sans-serif; font-size: 13px;">Hi!<div>I'm a student who would like to participate on Google SOC for LLVM, and was thinking about what project to pick. I saw on the "Open projects" page that Value Range Propagation is not implemented and thought about doing it, based on a paper by Patterson (it's also used by GCC). But then I saw that last year someone did a Range Analysis pass that seems to do pretty much the same thing, but using a different algorithm. </div>



<div>Am I missing something? It's possible that these do something different/have different usage scenarios?. </div><div>If they are the same, I think it would be better to remove it from the open project list, so other people don't start thinking about how to do it, only to see later that it's already done :)</div>



<div><br></div><font color="#888888"><div>Gratian</div></font></span>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br>