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
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.
On Tue, Feb 22, 2011 at 6:19 AM, Duncan Sands <baldrick at free.fr> wrote:> 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.Any reason not to just leave them on at O3? Based on the discussion around your simple condition propagation pass, it seemed predsimplify did delete dead code, but it didn't really improve generated code performance. O3 seems the appropriate place to put expensive optimizations with diminishing returns. Reid
Douglas do Couto Teixeira
2011-Feb-22 16:21 UTC
[LLVMdev] Question about Value Range Propagation
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>
On 2/22/11 5:19 AM, Duncan Sands 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.I was under the impression that ABCD was removed because no one was maintaining and improving it. Is my impression incorrect? The SAFECode compiler adds additional run-time checks for array bounds checking. If the ABCD code was working but just wasn't useful for regular C code, I'd like to know. It may still have value for projects like SAFECode. -- John T.> Ciao, Duncan. > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Douglas do Couto Teixeira
2011-Feb-25 17:16 UTC
[LLVMdev] Question about Value Range Propagation
Hi, Andrey,
sorry for the delay: I made a page with the code available for download:
http://homepages.dcc.ufmg.br/~douglas/projects/RangeAnalysis/RangeAnalysis.html
Feel free to get it, and if you need some help, I will be happy to tell
you how to set the analysis up, in case the explanation in the page is not
good.
I also have a report describing the implementation here: (
http://homepages.dcc.ufmg.br/~douglas/projects/RangeAnalysis/RangeAnalysis.paper.pdf
)
Indeed, if any of you guys have some free time, and want to give me a
review, that would be very kind of you :)
Warm regards,
Douglas
2011/2/22 Andrey Belevantsev <abel at ispras.ru>
> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110225/8a5200d1/attachment.html>
Can't read your paper because the permission is not set. Chuck On 2/25/2011 12:16 PM, Douglas do Couto Teixeira wrote:> Hi, Andrey, > > sorry for the delay: I made a page with the code available for > download: > http://homepages.dcc.ufmg.br/~douglas/projects/RangeAnalysis/RangeAnalysis.html > <http://homepages.dcc.ufmg.br/%7Edouglas/projects/RangeAnalysis/RangeAnalysis.html> > Feel free to get it, and if you need some help, I will be happy to > tell you how to set the analysis up, in case the explanation in the > page is not good. > I also have a report describing the implementation here: > (http://homepages.dcc.ufmg.br/~douglas/projects/RangeAnalysis/RangeAnalysis.paper.pdf > <http://homepages.dcc.ufmg.br/%7Edouglas/projects/RangeAnalysis/RangeAnalysis.paper.pdf>) > Indeed, if any of you guys have some free time, and want to give > me a review, that would be very kind of you :) > > Warm regards, > > Douglas > > 2011/2/22 Andrey Belevantsev <abel at ispras.ru <mailto:abel at ispras.ru>> > > 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 > > > > _______________________________________________ > 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/20110225/6a77c53e/attachment.html>