Is this a valid optimisation?
ThosRTanner
int32_t get_val(char const *s, std::size_t len, uint8_t base)
{
bool is_neg;
// set isneg
int32_t min = std::numeric_limits<int32_t>::min();
int32_t max = std::numeric_limits<int32_t>::max();
int32_t lim = isneg ? (-(min / base)) : (max / base);
//blah
}
Now on one compiler, when you switch on optimisation, the last line
appears to be evaluated as:
int32_t lim = (isneg ? -min : max) / base;
which doesn't work, as -min is still negative, and lim gets a negative
result, whereas it should be positive.
So - is this a valid optimisation or not? I thought only negating the
most negative integer was undefined.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Bart van Ingen Schenau
> I've seen one compiler where this:
>
> int32_t get_val(char const *s, std::size_t len, uint8_t base)
> {
> bool is_neg;
> // set isneg
> int32_t min = std::numeric_limits<int32_t>::min();
> int32_t max = std::numeric_limits<int32_t>::max();
> int32_t lim = isneg ? (-(min / base)) : (max / base);
> //blah
>
> }
>
> Now on one compiler, when you switch on optimisation, the last line
> appears to be evaluated as:
> int32_t lim = (isneg ? -min : max) / base;
>
> which doesn't work, as -min is still negative, and lim gets a negative
> result, whereas it should be positive.
>
> So - is this a valid optimisation or not? I thought only negating the
> most negative integer was undefined.
For this particular case, the optimisation is not valid. My guess is
that the compiler does not take this corner-case into account when
applying the optimisation.
Negating a value is only UB if the result can not be represented. This
is only the case when the implementation uses 2-s complement
representation for negative integers and you try to negate the most
negative value.
Bart v Ingen Schenau
Jens Schmidt
> I've seen one compiler where this:
>
> int32_t get_val(char const *s, std::size_t len, uint8_t base)
> {
> bool is_neg;
> // set isneg
> int32_t min = std::numeric_limits<int32_t>::min();
> int32_t max = std::numeric_limits<int32_t>::max();
> int32_t lim = isneg ? (-(min / base)) : (max / base);
> //blah
> }
>
> Now on one compiler, when you switch on optimisation, the last line
> appears to be evaluated as:
> int32_t lim = (isneg ? -min : max) / base;
Source code as an intermediate format for optimisation is very unusual.
How did you get that line? Re-sourcing an assembly listing? A guess
from debugging?
> which doesn't work, as -min is still negative, and lim gets a negative
> result, whereas it should be positive.
>
> So - is this a valid optimisation or not?
It is not. A valid optimisation is one where the actual hardware produces
the same result as the abstract machine for all defined cases.
> I thought only negating the most negative integer was undefined.
I don't understand, what 'only' means in this context. There are a lot of
undefined cases, most of them not having to do with negating. Let's suppose
you meant 'Negating integers is undefined only for the most negative value.'
As Bart already answered, this depends on the representation. Also, the
compiler knows a lot more about the target machine than the C++ standard.
It may use this knowledge of how the target machine works even in cases
where the standard defines no specific behaviour. The very similar line
int32_t lim
= static_cast<int32_t>((isneg ? static_cast<uint32_t>(-min)
: static_cast<uint32_t>(max)) / base);
still invokes undefined behaviour in C++, but most (the compiler might know:
the one that is currently the target) processors will produce the correct
result, because static_cast between int32_t and uint32_t is often the same
as reinterpret_cast. The only difference is an unsigned division versus a
signed one.
--
Greetings,
Jens Schmidt
Mathias Gaunard
> I've seen one compiler where this:
>
> int32_t get_val(char const *s, std::size_t len, uint8_t base)
> {
> bool is_neg;
> // set isneg
> int32_t min = std::numeric_limits<int32_t>::min();
> int32_t max = std::numeric_limits<int32_t>::max();
> int32_t lim = isneg ? (-(min / base)) : (max / base);
> //blah
>
> }
>
> Now on one compiler, when you switch on optimisation, the last line
> appears to be evaluated as:
> int32_t lim = (isneg ? -min : max) / base;
>
> which doesn't work, as -min is still negative, and lim gets a negative
> result, whereas it should be positive.
>
> So - is this a valid optimisation or not? I thought only negating the
> most negative integer was undefined.
Without looking too much into it, I'd say it's valid if the target
machine uses one's complement signed integers, but not with two's
complement, since -min would overflow and be -1.
But then it could even be optimized to int32_t lim = max / base;
ThosRTanner
> ThosRTanner wrote:
> > I've seen one compiler where this:
>
> > int32_t get_val(char const *s, std::size_t len, uint8_t base)
> > {
> > bool is_neg;
> > // set isneg
> > int32_t min = std::numeric_limits<int32_t>::min();
> > int32_t max = std::numeric_limits<int32_t>::max();
> > int32_t lim = isneg ? (-(min / base)) : (max / base);
> > //blah
> > }
>
> > Now on one compiler, when you switch on optimisation, the last line
> > appears to be evaluated as:
> > int32_t lim = (isneg ? -min : max) / base;
>
> Source code as an intermediate format for optimisation is very unusual.
> How did you get that line? Re-sourcing an assembly listing? A guess
> from debugging?
A guess from the observed behaviour. Also, a single line of C++ is
probably a lot easier to comprehend than the equivalent assembler.
>
> > which doesn't work, as -min is still negative, and lim gets a negative
> > result, whereas it should be positive.
>
> > So - is this a valid optimisation or not?
>
> It is not. A valid optimisation is one where the actual hardware produces
> the same result as the abstract machine for all defined cases.
>
> > I thought only negating the most negative integer was undefined.
>
> I don't understand, what 'only' means in this context. There are a lot of
> undefined cases, most of them not having to do with negating. Let's
suppose
> you meant 'Negating integers is undefined only for the most negative
value.'
I meant that when playing with the most negative signed twos
complement integer, a simple negation (or * or / by - 1) was likely to
result in surprising behaviour (at least more surprising than say
subtracting one), whereas a division by any other non-zero number
would do as expected.
The theory was that using numeric_limits for this operation would
avoid issues with underlying number representations.
--
ThosRTanner
> Without looking too much into it, I'd say it's valid if the target
> machine uses one's complement signed integers, but not with two's
> complement, since -min would overflow and be -1.
> But then it could even be optimized to int32_t lim = max / base;
>
Nick Maclaren
Jens Schmidt <Jens.Sc...@gmx.de> wrote:
>ThosRTanner wrote:
>
>> I've seen one compiler where this:
>>
>> int32_t get_val(char const *s, std::size_t len, uint8_t base)
>> {
>> bool is_neg;
>> // set isneg
>> int32_t min = std::numeric_limits<int32_t>::min();
>> int32_t max = std::numeric_limits<int32_t>::max();
>> int32_t lim = isneg ? (-(min / base)) : (max / base);
>> //blah
>> }
>>
>> Now on one compiler, when you switch on optimisation, the last line
>> appears to be evaluated as:
>> int32_t lim = (isneg ? -min : max) / base;
>
>Source code as an intermediate format for optimisation is very unusual.
>How did you get that line? Re-sourcing an assembly listing? A guess
>from debugging?
>
>> which doesn't work, as -min is still negative, and lim gets a negative
>> result, whereas it should be positive.
>>
>> So - is this a valid optimisation or not?
>
>It is not. A valid optimisation is one where the actual hardware produces
>the same result as the abstract machine for all defined cases.
Er, no. The 'abstract machine' is not specified precisely enough
to claim that it supports that operation with those values. While
there is wording to support your viewpoint, it's sufficiently vague
as to allow for different interpretations of this. This specific
question arose on the WG14 reflector, and there was no consensus.
There MIGHT be something more precise in C++, but I haven't found it.
Regards,
Nick Maclaren.
--
Timothy Madden
> ThosRTanner wrote:
>
>> I've seen one compiler where this:
>>
>> int32_t get_val(char const *s, std::size_t len, uint8_t base)
>> {
>> bool is_neg;
>> // set isneg
>> int32_t min = std::numeric_limits<int32_t>::min();
>> int32_t max = std::numeric_limits<int32_t>::max();
>> int32_t lim = isneg ? (-(min / base)) : (max / base);
>> //blah
>> }
>>
>> Now on one compiler, when you switch on optimisation, the last line
>> appears to be evaluated as:
>> int32_t lim = (isneg ? -min : max) / base;
>
> Source code as an intermediate format for optimisation is very unusual.
> How did you get that line? Re-sourcing an assembly listing? A guess
> from debugging?
>
>> which doesn't work, as -min is still negative, and lim gets a negative
>> result, whereas it should be positive.
>>
>> So - is this a valid optimisation or not?
>
> It is not. A valid optimisation is one where the actual hardware produces
> the same result as the abstract machine for all defined cases.
I do not understand, what is the difference between the two lines ?
I mean the expression
is_neg ? -min/base : max/base
is mathematically the same as
(is_neg ? -min : max) / base
no matter the representation, hardware or whatever ...
Besides, if -min overflows on a certain representation, than the entire
expression is undefined, so the compiler can optimize it in whatever
wrong ways it sees fit, since it was wrong from the beginning anyway.
You see, trying to optimize undefined behavior results in even more
undefined behavior, and that is legal ... :)
See "A Guide to Undefined Behavior in C and C++" at
http://blog.regehr.org/archives/213
Thank you,
Timothy Madden
--
ThosRTanner
>
> I do not understand, what is the difference between the two lines ?
>
> I mean the expression
> is_neg ? -min/base : max/base
> is mathematically the same as
> (is_neg ? -min : max) / base
> no matter the representation, hardware or whatever ...
Well, no it isn't. A computer implementation doesn't provide a
mathematical field, because the underlying group isn't prime and isn't
infinite.
>
> Besides, if -min overflows on a certain representation, than the entire
> expression is undefined, so the compiler can optimize it in whatever
> wrong ways it sees fit, since it was wrong from the beginning anyway.
Well, no, that is what is open to query, and currently there doesn't
seem to be a consensus on this. You say it is a valid optimisation
because -min isn't well defined. However -(min / base) where base is
known to be > 1 is perfectly well defined.
>
> You see, trying to optimize undefined behavior results in even more
> undefined behavior, and that is legal ... :)
>
> See "A Guide to Undefined Behavior in C and C++" at
> http://blog.regehr.org/archives/213
Interesting, but not entirely helpful, as the operation is only
undefined under certain situations which aren't possible in this
context.
Seungbeom Kim
The original poster wrote -(min / base), not -min / base.
They are different. The former may not be undefined if base > 1,
even though -min is undefined.
--
Seungbeom Kim