[LLVMdev] Question about Value Range Propagation

[Douglas do Couto Teixeira]

Hi, guys,

    my current implementation goes over the whole LLVM test suite plus SPEC
CPU 2006 in less than one minute. So, in term of runtime, the results seem
good. However, the analysis is not very precise yet. Compared to
Stephenson's original work, I reduce about 31% of the bits from bitwise
(Stephenson's benchmark). He reduced it by 53%. But he would assume that the
program was correct. So, if he found an operand like a[v], he could assume
that v < size(a). Or, if he found an instruction like a[0:15] = b + c, then
he could assume that both b and c are less than 17 bits. In any case, for
small benchmarks, such as Stanford, MiBench and Bitwise my implementation
gets some non-trivial bit size reductions. For very big benchmarks such as
gcc (SPEC 2006), the reduction is not good (around 8%).

    About SSI, actually I am using e-SSA, the same IR used in ABCD. The size
is much smaller (10% of SSI), and the time to build it is negligible.

Regards,

Douglas

On Tue, Feb 22, 2011 at 8:19 AM, Duncan Sands <baldrick at free.fr> wrote:

> Hi Andrey,
>
> > 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.
>
> the big problem with Patterson's VRP is that it is expensive in terms of
> compile time.  LLVM used to have some passes (ABCD, predsimplify) that did
> this kind of thing, but they were removed essentially because their compile
> time was too great for the goodness they brought.
>
> Ciao, Duncan.
> _______________________________________________
> 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/20110222/f47e9851/attachment.html>