Hi! 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. Am I missing something? It's possible that these do something different/have different usage scenarios?. 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 :) Gratian -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110220/c435f660/attachment.html>
Douglas do Couto Teixeira
2011-Feb-21 17:27 UTC
[LLVMdev] Question about Value Range Propagation
Hi, Gratian, 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. I have an explanation about our implementation here: ( http://homepages.dcc.ufmg.br/~douglas/RangeAnalysis.html). 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. 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. Best, Douglas On Sun, Feb 20, 2011 at 2:30 PM, Gratian Lup <lgratian at gmail.com> wrote:> Hi! > 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. > Am I missing something? It's possible that these do something > different/have different usage scenarios?. > 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 :) > > Gratian > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110221/41b7da1b/attachment.html>
Hi Douglas, On 21.02.2011 20:27, Douglas do Couto Teixeira wrote:> 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.We were thinking of adding VRP to LLVM too, though we were mostly interested in Patterson's approach (i.e. not connected with SSI form). It would be great if you can share the code nevertheless. Andrey