www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Value Range Propigation Spec

reply Shammah Chancellor <email domain.com> writes:
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.
Oct 22 2014
next sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
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…
Oct 22 2014
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Oct 22 2014
next sibling parent reply Shammah Chancellor <email domain.com> writes:
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
Oct 23 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Oct 23 2014
parent reply "deadalnix" <deadalnix gmail.com> writes:
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 ?
Oct 23 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Oct 23 2014
parent reply "Stefan Koch" <uplink.coder googlemail.com> writes:
Hi, I am the guy who implemented the (currently incomplete) vrp 
for sdc.

I see vrp as a tool to avoid _unnecessary_ casts. _Not_ as means 
to avoid _all_ casts.


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


The problem with vrp for non-static immutable values is, that vrp 
becomes a runtime-thing and I would like to avoid that!
Tracking the range of a Variable at runtime could cause 
significant overhead!

Doing static analysis and tracking Variable-Ranges and 
assignments at compile-time, is possible but difficult and there 
are a number of reasons why not to do it.

1. Slows compilation down
2. implementation is not straight-forward and bugs could be hard 
to find.
3. Code that relays on this may not be easy to read, and it may 
be hard for the programmer to see why a particular assignment 
does not need a cast!

For simple code like the one posted above it is easy to see why 
it works.
anything mod 10 can only be in the range of [-9 .. 9]

But if we have much logic and control-flow between the assignment 
and the definition of the assigning variable then not haveing an 
explicit cast could cause a bit of puzzlement.
Oct 24 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Stefan Koch:


 The problem with vrp for non-static immutable values is, that 
 vrp becomes a runtime-thing and I would like to avoid that!
 Tracking the range of a Variable at runtime could cause 
 significant overhead!


Nope, the value range tracking is purely compile-time.



 2. implementation is not straight-forward and bugs could be 
 hard to find.


It's much better to remove bugs from the compiler than from an 
unbound amount of user code that uses casts incorrectly.



 3. Code that relays on this may not be easy to read,


I don't believe this. Please show one or more examples.



 and it may be hard for the programmer to see why a particular 
 assignment does not need a cast!


And this is bad because?



 But if we have much logic and control-flow between the 
 assignment and the definition of the assigning variable then 
 not haveing an explicit cast could cause a bit of puzzlement.


I think most D programmers are used to C/C++ coding, that doesn't 
require most of those casts. I don't think that "puzzlement" is 
real, or problematic.

Bye,
bearophile
Oct 24 2014
parent "Stefan Koch" <uplink.coder googlemail.com> writes:
you are right. I misread the code-snippt above. Of course this is 
staticly checkable!
Oct 24 2014
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Oct 23 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Oct 23 2014
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
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.
Oct 23 2014
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10/22/2014 10:32 PM, Walter Bright wrote:

 The specification is straightforward - a narrowing conversion can be
 implicitly performed if it can be proved that it would not lose
 information.


This is only straightforward to state because it is so ill-defined.
The main aspect in need of specification is the procedure to perform 
those automated proofs with.
Oct 24 2014
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/22/14 1:32 PM, 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.


I think specification is equally tricky because it needs to specify the 
exact algorithms. -- Andrei
Oct 27 2014
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10/22/2014 11: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.


AFAIK:

- arithmetic operators: new range is given by the minimum and maximum 
values that the whole expression can attain given that operands are 
arbitrary values from their respective ranges. (DMD currently does 
something worse for bitwise operators, and probably modulo.) If overflow 
may occur, the full data type range is assumed. Likewise if divide by 
zero may occur. (This despite the fact that divide by zero is supposedly 
undefined behaviour. Go figure.)

- mutable variables: full data type range is assumed

- immutable variables: range of initializer is assumed. If it is a 
foreach range index variable, combine value ranges of lower and upper 
bound appropriately.
Oct 24 2014