June 19, 2014 Re: RFC: Value range propagation for if-else | ||||
---|---|---|---|---|
| ||||
Posted in reply to H. S. Teoh | H. S. Teoh:
> This is a different instance of the same problem as above, isn't it?
> If Bound has access to compiler knowledge about value ranges, then it
> would be able to statically reject out-of-range values.
Yes, with the latest patch by Kenji it's thankfully an instance of the same problem above, because every literal in the array gets used to instantiate a Bound!().
Bye,
bearophile
|
June 20, 2014 Re: RFC: Value range propagation for if-else | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | On 19/06/14 15:59, Timon Gehr wrote:
> On 06/18/2014 09:54 PM, Meta wrote:
>> ...
>>
>> This could be a bad thing. It makes it pretty enticing to use contracts
>> as input verification instead of logic verification.
>
> The following is doable as well with a standard range analysis:
>
> byte foo(immutable int x){
> if(x<byte.min || x>byte.max)
> throw new InvalidArgumentException("...");
> return x; // ok
> }
That will only work now if you use an "else".
|
June 20, 2014 Re: RFC: Value range propagation for if-else | ||||
---|---|---|---|---|
| ||||
Posted in reply to Lionello Lunesu | On Wednesday, 18 June 2014 at 06:40:21 UTC, Lionello Lunesu wrote: > Hi, > https://github.com/lionello/dmd/compare/if-else-range > > There, I've also added a __traits(intrange, <expression>) which returns a tuple with the min and max for the given expression. > Destroy? The compiler uses value range propagation in this {min, max} form, but I think that's an implementation detail. It's well suited for arithmetic operations, but less suitable for logical operations. For example, this code can't overflow, but {min, max} range propagation thinks it can. ubyte foo ( uint a) { return (a & 0x8081) & 0x0FFF; } For these types of expressions, {known_one_bits, known_zero_bits} works better. Now, you can track both types of range propagation simultaneously, and I think we probably should improve our implementation in that way. It would improve the accuracy in many cases. Question: If we had implemented that already, would you still want the interface you're proposing here? |
June 20, 2014 Re: RFC: Value range propagation for if-else | ||||
---|---|---|---|---|
| ||||
Posted in reply to Don | On 20/06/14 15:53, Don wrote:
> On Wednesday, 18 June 2014 at 06:40:21 UTC, Lionello Lunesu wrote:
>> Hi,
>
>> https://github.com/lionello/dmd/compare/if-else-range
>>
>> There, I've also added a __traits(intrange, <expression>) which
>> returns a tuple with the min and max for the given expression.
>
>> Destroy?
>
> The compiler uses value range propagation in this {min, max} form, but I
> think that's an implementation detail. It's well suited for arithmetic
> operations, but less suitable for logical operations. For example, this
> code can't overflow, but {min, max} range propagation thinks it can.
>
> ubyte foo ( uint a) {
> return (a & 0x8081) & 0x0FFF;
> }
>
> For these types of expressions, {known_one_bits, known_zero_bits} works
> better.
> Now, you can track both types of range propagation simultaneously, and I
> think we probably should improve our implementation in that way. It
> would improve the accuracy in many cases.
>
> Question: If we had implemented that already, would you still want the
> interface you're proposing here?
>
You could have different __traits in that case:
__traits(valueRange,...) // for min/max
__traits(bitRange,...) // mask
You example seems rather artificial though. IRL you'd get a compiler warning/error and could fix it by changing the code to "& 0xFF". I personally have not yet had the need for these bit-masks.
L.
|
June 22, 2014 Re: RFC: Value range propagation for if-else | ||||
---|---|---|---|---|
| ||||
Posted in reply to Lionello Lunesu | Lionello Lunesu: > Have a look at the branch: > https://github.com/lionello/dmd/compare/if-else-range The need for this D improvement is sufficiently common, a just appeared question: http://forum.dlang.org/thread/jwfvuaohvlvwzjlmztsj@forum.dlang.org Lionello needs some cheering & support to create the patch that implements the value range propagation for if-else. Exposing the range and implementing value range propagation for if-else are sufficiently distinct needs. Bye, bearophile |
June 22, 2014 Re: RFC: Value range propagation for if-else | ||||
---|---|---|---|---|
| ||||
Posted in reply to Lionello Lunesu | > That will only work now if you use an "else".
So you mean something like
if(x<byte.min || x>byte.max)
throw new InvalidArgumentException("...
else {}
?
That seems like a strange restriction. Why is that?
|
June 22, 2014 Re: RFC: Value range propagation for if-else | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | > static if (this.min <= r[0] &&
> r[1] <= this.max)
BTW: I believe valueRange also enables specialization of constant arguments inside existing functions without having to move them to template arguments of specialized functions. Showcase:
auto pow(T)(T arg, uint n)
{
enum vr = __traits(valueRange, arg);
static if (vr.min == vr.max) // if arg is constant
static if (vr.min == 0)
return 1;
else static if (vr.min == 1)
return arg;
else static if (vr.min == 2)
return arg*arg;
else static if (vr.min == 3)
return arg*arg*arg;
// etc...
// generic case
}
I guess a __trait, named something like has[Fixed|Constant]Value, would be useful here.
I bet there are more possibilities with these traits we haven't thought of yet.
|
June 22, 2014 Re: RFC: Value range propagation for if-else | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | Correction: It should of course be auto pow(T)(T arg, uint n) { enum vr = __traits(valueRange, n); .... } |
June 22, 2014 Re: RFC: Value range propagation for if-else | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | Nordlöw:
> auto pow(T)(T arg, uint n)
> {
> enum vr = __traits(valueRange, arg);
> static if (vr.min == vr.max) // if arg is constant
I think that unfortunately this currently can't work, you can't tell the range of the input value like that. I have explained why in one of my posts in this thread. Please try to explain me why I'm wrong.
Bye,
bearophile
|
June 23, 2014 Re: RFC: Value range propagation for if-else | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | On Sunday, 22 June 2014 at 21:10:31 UTC, bearophile wrote:
> Nordlöw:
>
>> auto pow(T)(T arg, uint n)
>> {
>> enum vr = __traits(valueRange, arg);
>> static if (vr.min == vr.max) // if arg is constant
>
> I think that unfortunately this currently can't work, you can't tell the range of the input value like that. I have explained why in one of my posts in this thread. Please try to explain me why I'm wrong.
Don't know what you're referring to, but I guess you mean that - because of separate compilation - the code generated for `pow` needs to be generic? This is not really a problem, because the compiler can generate _additional_ specialized functions for it. But then, a normal `if` would also do, because dead code elimination can remove the unused parts in these specializations.
|
Copyright © 1999-2021 by the D Language Foundation