llvm dev - Feb 2011 - [LLVMdev] Question about Value Range Propagation

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>

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