On 5/31/2014 5:02 PM, "Nordlöw" wrote:
> Could you elaborate a bit on what data flow optimizations mean?

http://en.wikipedia.org/wiki/Data-flow_analysis


> What other kinds of optimizations will become possible?

Escape analysis, for one.

http://en.wikipedia.org/wiki/Escape_analysis


> Is this something that other langs/compilers offer?

All modern compilers use DFA in the optimizer pass (including dmd), but that is not set up to provide information back to the front end.

On Saturday, 31 May 2014 at 23:30:41 UTC, Walter Bright wrote:
> There isn't a suitable place. To make it work, data flow analysis would have to be added to the front end. While doable, this is not a simple addition. Eventually, we'll have to do it as a lot of things become possible & better with data flow analysis, not just bounds check elimination.

I've always wondered if VRP can be leveraged in certain situations. I can't remember exactly how it's supposed to work, but very basically, isn't it just numeric variables (and expressions?) having an associated range that they carry around with them at compile time, so something like this is possible:

long n1 = long.max;
int n2 = n1 % 3; //No cast needed due to VRP

Couldn't this be used for other things as well, such as detecting numeric overflow at compile time, or like Nordlow suggested, figuring out when it's safe to elide an array bounds check?

"Meta"  wrote in message news:pogogtdjyetukennyras@forum.dlang.org...

> I've always wondered if VRP can be leveraged in certain situations. I can't remember exactly how it's supposed to work, but very basically, isn't it just numeric variables (and expressions?) having an associated range that they carry around with them at compile time, so something like this is possible:
>
> long n1 = long.max;
> int n2 = n1 % 3; //No cast needed due to VRP
>
> Couldn't this be used for other things as well, such as detecting numeric overflow at compile time, or like Nordlow suggested, figuring out when it's safe to elide an array bounds check?

It can, and it already is.  The problem is that n1 above is not guaranteed to _stay_ equal to long.max.  Without data flow analysis the compiler doesn't know that it is never re-assigned, so the possible range is any value that fits in a long.

There are cases where it should be able to tell without data flow analysis but are currently not implemented. 

Daniel Murphy:

> There are cases where it should be able to tell without data flow analysis but are currently not implemented.

Such cases are not rare:

https://issues.dlang.org/show_bug.cgi?id=10594
https://issues.dlang.org/show_bug.cgi?id=10615
https://issues.dlang.org/show_bug.cgi?id=10749
https://issues.dlang.org/show_bug.cgi?id=10751
(There is one more of similar suggestions).

In general in your D code use immutable/const everywhere you can.

Bye,
bearophile

Dmitry Olshansky:

> Who are those people that are not disabling bounds checks in system language ? :)

If you show D code on Reddit and you show to compile with -noboundscheck you hear some people growl. I don't remember this happening much in past. So I think the attitude toward disabling bound checks is changing.

-----------

Once some more logic for bound checks removal is in D, it can even be added a @bounded expression attribute:

foreach (immutable i; 0 .. a.length)
    a[@bounded i]++;

@bounded {
    foreach (immutable i; 0 .. a.length)
        a[@bounded i]++;
}

The purpose of @bounded is just to give a compile-time error if the compiler is not able to remove one (or more if used with the {} syntax) array bound check.

Bye,
bearophile

On 5/31/14, 6:47 PM, Meta wrote:
> On Saturday, 31 May 2014 at 23:30:41 UTC, Walter Bright wrote:
>> There isn't a suitable place. To make it work, data flow analysis
>> would have to be added to the front end. While doable, this is not a
>> simple addition. Eventually, we'll have to do it as a lot of things
>> become possible & better with data flow analysis, not just bounds
>> check elimination.
>
> I've always wondered if VRP can be leveraged in certain situations. I
> can't remember exactly how it's supposed to work, but very basically,
> isn't it just numeric variables (and expressions?) having an associated
> range that they carry around with them at compile time, so something
> like this is possible:
>
> long n1 = long.max;
> int n2 = n1 % 3; //No cast needed due to VRP
>
> Couldn't this be used for other things as well, such as detecting
> numeric overflow at compile time, or like Nordlow suggested, figuring
> out when it's safe to elide an array bounds check?

For $/n VRP can't be used because it's geared toward constants, not relative to variables. So VRP could inform of something like "this number is between 0 and 5", not "this number is between 0 and a.length". -- Andrei

01-Jun-2014 14:21, bearophile пишет:
> Dmitry Olshansky:
>
>> Who are those people that are not disabling bounds checks in system
>> language ? :)
>
> If you show D code on Reddit and you show to compile with -noboundscheck
> you hear some people growl. I don't remember this happening much in
> past. So I think the attitude toward disabling bound checks is changing.
>
> -----------
>
> Once some more logic for bound checks removal is in D, it can even be
> added a @bounded expression attribute:

An expression attribute? Why turn language into a mess over this tiny problem?

It seems to me that you are considering solutions that add arbitrary amounts of complexity to solve relatively small problems.

>
> foreach (immutable i; 0 .. a.length)
>      a[@bounded i]++;
>
> @bounded {
>      foreach (immutable i; 0 .. a.length)
>          a[@bounded i]++;
> }
>
> The purpose of @bounded is just to give a compile-time error if the
> compiler is not able to remove one (or more if used with the {} syntax)
> array bound check.

That "just" epithet is remarkable self-destruction.

-- 
Dmitry Olshansky

On Saturday, 31 May 2014 at 10:56:06 UTC, bearophile wrote:
> void main() {
>     int[5] data;
>     foreach (const i; 0 .. 10)
>         data[i] = 0;
>     foreach (immutable i; 0 .. 10)
>         data[i] = 0;
>     int[10] big;
>     foreach (const i, x; big)
>         data[i] = x;
> }
>
>
> But the compiler must recognize this as correct code:
>
>
> void main() {
>     int[5] data;
>     foreach (const i; 0 .. 10)
>         if (i < 5)
>             data[i] = 0;
> }
>
>
> Can this logic be added to D?
>
>
> More info on the topic:
> http://en.wikipedia.org/wiki/Bounds-checking_elimination
> http://ssw.jku.at/Research/Papers/Wuerthinger07/Wuerthinger07.pdf
>
> Bye,
> bearophile

What do GDC or LDC generate for these sample code with optimizations on ?

> For $/n VRP can't be used because it's geared toward constants, not relative to variables. So VRP could inform of something like "this number is between 0 and 5", not "this number is between 0 and a.length". -- Andrei

That's what I thought of aswell. Are there any plans to formalize the structures and algorithms of such expressions and their propagations? I guess LLVM or GCC must have thought of these things, right?

deadalnix:

> What do GDC or LDC generate for these sample code with optimizations on ?

This is not an interesting question because those two programs are meant as parts of larger programs. ldc2 optimizes away both programs to "xorl %eax, %eax".

And I can't test on GDC because GDC compiler crashes on my system since years.

Bye,
bearophile