A couple of us working on SDC are trying to get ValueRange propigation implemented.   I was wonder if someone could offer some insight as to how VRP works in DMD.   If for example, trying to get the value range of a global, what is the expected behavior?

It seems as though VRP is a language feature, and not a compiler feature -- since this allows some code to compile and not others.   Is there a specification for how it should work somewhere?  If not, it's hard to implement other compilers that will not generate errors in the same circumstances as DMD.

On Wednesday, 22 October 2014 at 09:27:09 UTC, Shammah Chancellor wrote:
> A couple of us working on SDC are trying to get ValueRange propigation implemented.

Nice! Maybe you should also consider establishing error in floating point calculations by extending to interval arithmetic?

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

Then D would have to add some way to express acceptable tolerance. The advantage is that the compiler could then do heavy duty optimization on floating point. Like using single precision, a more SIMD friendly evaluation order, a look up table etc…

On 10/22/2014 2:31 AM, Shammah Chancellor wrote:
> A couple of us working on SDC are trying to get ValueRange propigation
> implemented.   I was wonder if someone could offer some insight as to how VRP
> works in DMD.   If for example, trying to get the value range of a global, what
> is the expected behavior?
>
> It seems as though VRP is a language feature, and not a compiler feature --
> since this allows some code to compile and not others.   Is there a
> specification for how it should work somewhere?  If not, it's hard to implement
> other compilers that will not generate errors in the same circumstances as DMD.
>

VRP is definitely a language feature, not a compiler feature. The specification is straightforward - a narrowing conversion can be implicitly performed if it can be proved that it would not lose information.

How it works, though, is kinda tricky, and the only guide to it is the compiler source code.

On 2014-10-22 20:32:35 +0000, Walter Bright said:

> On 10/22/2014 2:31 AM, Shammah Chancellor wrote:
>> A couple of us working on SDC are trying to get ValueRange propigation
>> implemented.   I was wonder if someone could offer some insight as to how VRP
>> works in DMD.   If for example, trying to get the value range of a global, what
>> is the expected behavior?
>> 
>> It seems as though VRP is a language feature, and not a compiler feature --
>> since this allows some code to compile and not others.   Is there a
>> specification for how it should work somewhere?  If not, it's hard to implement
>> other compilers that will not generate errors in the same circumstances as DMD.
>> 
> 
> VRP is definitely a language feature, not a compiler feature. The specification is straightforward - a narrowing conversion can be implicitly performed if it can be proved that it would not lose information.
> 
> How it works, though, is kinda tricky, and the only guide to it is the compiler source code.


Walter,

Several of us working on it were a little surprised that DMD does not compile this:

void main() {
	long l = 42;
	int i = l;
}

Is this expected to compile?  Planned?     My post was based on my thought that this *did* compile and we were wondering rules for when the range would be reset.   If `l` were __gshared for example, the range wouldn't be deterministic.

Surely there should be some rules document?  What we've implemented, is that the value range is calculated at float80 precision, and it's min and max can fit in the ultimate type for a cast, then it's good to go.  We only look at the actual expression being implicitly cast.


Thanks,
-Shammah

Shammah Chancellor:

> Several of us working on it were a little surprised that DMD does not compile this:
>
> void main() {
> 	long l = 42;
> 	int i = l;
> }
>
> Is this expected to compile?  Planned?

Currently this doesn't compile, and it's expected to not compile. Currently VRP works only inside one expression (I guess to keep low the compiler complexity). So the value range of l is lost when it's assigned to i.

Very recently VRP was improved and now the value range of immutable values is kept.

I don't know if there are plans to improve the VRP. I hope to see some improvements, like:

void foo(in uint x)
in {
    assert(x < 10_000);
} body {
    ushort y = x;
    if (x < 100) {
        ubyte z = x;
    }
}


Another example:

uint bar()
out(result) {
    assert(result < 100);
} body {
    return 99;
}
void spam(in ubyte x) {}
void main() {
    spam(bar());
}


Other improvements are possible, and very useful. I have some more enhancement requests in Bugzilla.

Bye,
bearophile

On 10/23/2014 8:29 AM, Shammah Chancellor wrote:
> Several of us working on it were a little surprised that DMD does not compile this:
>
> void main() {
>      long l = 42;
>      int i = l;
> }
>
> Is this expected to compile?

No. As bearophile mentioned, VRP only applies to an expression. The compiler front end does not do dataflow analysis to affect semantics. (The optimizer does, but that is a later pass and does not affect the semantics.)


> Planned?

Not currently.


> My post was based on my thought that
> this *did* compile and we were wondering rules for when the range would be
> reset.   If `l` were __gshared for example, the range wouldn't be deterministic.

To do it reliably would require dataflow analysis.


> Surely there should be some rules document?  What we've implemented, is that the
> value range is calculated at float80 precision, and it's min and max can fit in
> the ultimate type for a cast, then it's good to go. We only look at the actual
> expression being implicitly cast.

Just be careful with floats about accumulated roundoff errors. This is not a simple problem.

Walter Bright:

> To do it reliably would require dataflow analysis.

There are still several useful cases where dataflow analysis is not needed (like for immutable values) that are still missing. They could be added.

Bye,
bearophile

On Wednesday, 22 October 2014 at 20:32:39 UTC, Walter Bright wrote:
> On 10/22/2014 2:31 AM, Shammah Chancellor wrote:
>> A couple of us working on SDC are trying to get ValueRange propigation
>> implemented.   I was wonder if someone could offer some insight as to how VRP
>> works in DMD.   If for example, trying to get the value range of a global, what
>> is the expected behavior?
>>
>> It seems as though VRP is a language feature, and not a compiler feature --
>> since this allows some code to compile and not others.   Is there a
>> specification for how it should work somewhere?  If not, it's hard to implement
>> other compilers that will not generate errors in the same circumstances as DMD.
>>
>
> VRP is definitely a language feature, not a compiler feature. The specification is straightforward - a narrowing conversion can be implicitly performed if it can be proved that it would not lose information.
>
> How it works, though, is kinda tricky, and the only guide to it is the compiler source code.

Seeing as it affects semantics, should there not be a minimum standard of what must be provable by a D compiler?

Inference is great, but portability matters too.

On Thursday, 23 October 2014 at 15:39:55 UTC, bearophile wrote:
> Other improvements are possible, and very useful. I have some more enhancement requests in Bugzilla.
>

The problem is not really what enhancement to do. But what limit
do we fix to ourselves (ie, what is a bug and what is not).

There are possibilities to do more, but compatibility require
that we put the line somewhere.

The current line seems to be to do VRP on expression and compile
time know values. Is that right ?

deadalnix:

> There are possibilities to do more, but compatibility require
> that we put the line somewhere.

The line is still moving forward.


> The current line seems to be to do VRP on expression and compile
> time know values. Is that right ?

No, it's not right. VRP was recently improved to keep the value range of run-time immutable values. And some VRP was added to foreach loops. So now this is accepted:


void main(in string[] args) {
    immutable size_t len = args.length % 10;
    ubyte x = len;
    ubyte[] a;
    foreach (immutable i; 0u .. len)
        a ~= i;
}

Bye,
bearophile