[LLVMdev] Question about Value Range Propagation

[Gratian Lup]

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

[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

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Andrey Belevantsev]

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

[Duncan Sands]

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.

[Reid Kleckner]

On Tue, Feb 22, 2011 at 6:19 AM, Duncan Sands <bald...@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]

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

[John Criswell]

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.

[Chris Lattner]

On Feb 22, 2011, at 7:25 AM, Reid Kleckner wrote:

> On Tue, Feb 22, 2011 at 6:19 AM, Duncan Sands <bald...@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.

Hi Reid,

-O3 compile time matters. We don't turn things on in -O3 or -O4 that just burn compiler cycles but don't add value.

-Chris

[Douglas do Couto Teixeira]

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 <ab...@ispras.ru>

[Chuck Zhao]

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
О©╫О©╫О©╫ 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 <ab...@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

[Douglas do Couto Teixeira]

I'm sorry. I fixed it.

Douglas

2011/2/25 Chuck Zhao <cz...@eecg.toronto.edu>

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

    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 <ab...@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
LLV...@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev