[LLVMdev] Question about Value Range Propagation

[Douglas do Couto Teixeira]

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>