Strange shifting behaviour

Strange shifting behaviour

[Ulf Magnusson]

When shifting an int by its size in bits, the results seems to vary
depending on whether variables are involved or not. For example, the
following program will produce the output

0
-1

and not the expected

0
0

int main() {
    int a = 24, b = 8;
    printf("%d\n%d", ~0 << 32, ~0 << (a + b));
}

It seems that C << (a + b), where C is some constant integer and a and
b are variables that add up to 32 (I have only compiled and run this
program on 32 bit systems), will always get evaluated to C.

Changing  ~0 << 32  to  ~0 << 32 + a - a  does not change the
behaviour, I'm guessing as the optimizer realizes that this is still a
constant expression. Changing it to ~0 << 32 + a + a - 2*a , however,
Does change the behaviour, as the optimizer isn't smart enough to
realize that this too is a constant expression. Now, the output is,

-1
-1

This suggests that the problem lies in how shifts are handled in
non-constant expressions. Interestingly, the behaviour changes to the
expected (correct?) one when compiling with optimizations (any of the
-O's).

gcc -v output:
Using built-in specs.
Configured with: FreeBSD/i386 system compiler
Thread model: posix
gcc version 3.4.2 [FreeBSD] 20040728

The system is FreeBSD 5.4. I'm using the gcc that came prebuilt with
it. I had the following compilation warnings:

In function `main':
3: warning: left shift count >= width of type

Ulf

Re: Strange shifting behaviour

[Eljay Love-Jensen]

Hi Ulf,

>When shifting an int by its size in bits...

That is undefined behavior (implementation dependent), as per C and C++ standards.  Ever since C was first taking it's first baby steps.

By "undefined behavior", that means any given particular implementation can:
+ not do anything
+ do what you expect
+ SEGV
+ format your hard drive

--Eljay

Re: Strange shifting behaviour

[corey taylor]

> Are you going to issue a warning on every shift operation
> for which you cannot prove that the shift count is within
> the "defined behavior" range?

Well no, or you could and simply have it implement "up to" the defined
behavior range.

However, Ulf's example seems to show that a shift never happens
(although I'd like to see the code generated and cannot generate my
own at this time (hurricane issues had me take down gcc/g++ dev
machines).  A more severe warning at least is called for here.

corey

RE: Strange shifting behaviour

[Eljay Love-Jensen]

Hi John,

>It depends on whether you want acknowledge the impression that your compiler makes on users who are not language lawyers.

It's not a GCC issue.  The behavior is undefined by the C and C++ standards.

In my opinion, I prefer that the compiler-at-compiler-time didn't perform the "format my hard drive" as the compiler specific undefined behavior that may occur during the executable run of my own program.

But that's just me.  YMMV.

Sincerely,
--Eljay

RE: Strange shifting behaviour

[John Yates]

It depends on whether you want acknowledge the impression
that your compiler makes on users who are not language
lawyers.

Now that gcc has adopted SSA and implemented the Wegman-
Zadeck ConditionalConst scheme for partial evaluation
I believe (in fact I know from having implemented that
same algorithm over ten year ago [1]) that the compiler
will be evaluating expressions at compile time that are
not identified as CTCEs by the language standard.

Are you going to issue a warning on every shift operation
for which you cannot prove that the shift count is within
the "defined behavior" range?

It just makes a poor impression to say "the compiler
is inconsistent in how it evaluates a given expression
because the language standard allows it to be".  This
is even harder to justify when the fix does not degrade
the quality of generated code but rather requires the
compile-time simulation of run-time computation to be
more faithful.

/john

[1] http://gcc.gnu.org/wiki/JohnYates

-----Original Message-----
From: corey taylor [mailto:corey.taylor@gmail.com]
Sent: Wednesday, July 13, 2005 2:19 PM
To: John Yates
Cc: Eljay Love-Jensen; Ulf Magnusson; gcc-help@gcc.gnu.org
Subject: Re: Strange shifting behaviour


Would the warning generated not suffice?  

corey

On 7/13/05, John Yates <jyates@netezza.com> wrote:
> Eljay,
> 
> Though I agree with your point about the standards and
> undefined behavior, I do believe that Ulf has identified
> a quality of implementation issue.
> 
> Would you not agree that compile-time expression evaluation
> should mimic run-time as much as possible?  Or to put it
> another way, the more often compile-time and run-time
> evaluated results diverge, the lower the subject quality
> of the compiler.
> 
> If the shift operator at run-time examines only the lower
> order 5 bits of the shift count (as Ulf's x86 does) then
> a "high-quality" compile-time expression evaluator ought
> to do the same.
> 
> /john
> 
> -----Original Message-----
> From: Eljay Love-Jensen [mailto:eljay@adobe.com]
> Sent: Tuesday, July 12, 2005 6:46 PM
> To: Ulf Magnusson; gcc-help@gcc.gnu.org
> Subject: Re: Strange shifting behaviour
> 
> 
> Hi Ulf,
> 
> >When shifting an int by its size in bits...
> 
> That is undefined behavior (implementation dependent), as per C and C++ standards.  Ever since C was first taking it's first baby steps.
> 
> By "undefined behavior", that means any given particular implementation can:
> + not do anything
> + do what you expect
> + SEGV
> + format your hard drive
> 
> --Eljay
> 
>

Re: Strange shifting behaviour

[corey taylor]

Would the warning generated not suffice?  

corey

On 7/13/05, John Yates <jyates@netezza.com> wrote:
> Eljay,
> 
> Though I agree with your point about the standards and
> undefined behavior, I do believe that Ulf has identified
> a quality of implementation issue.
> 
> Would you not agree that compile-time expression evaluation
> should mimic run-time as much as possible?  Or to put it
> another way, the more often compile-time and run-time
> evaluated results diverge, the lower the subject quality
> of the compiler.
> 
> If the shift operator at run-time examines only the lower
> order 5 bits of the shift count (as Ulf's x86 does) then
> a "high-quality" compile-time expression evaluator ought
> to do the same.
> 
> /john
> 
> -----Original Message-----
> From: Eljay Love-Jensen [mailto:eljay@adobe.com]
> Sent: Tuesday, July 12, 2005 6:46 PM
> To: Ulf Magnusson; gcc-help@gcc.gnu.org
> Subject: Re: Strange shifting behaviour
> 
> 
> Hi Ulf,
> 
> >When shifting an int by its size in bits...
> 
> That is undefined behavior (implementation dependent), as per C and C++ standards.  Ever since C was first taking it's first baby steps.
> 
> By "undefined behavior", that means any given particular implementation can:
> + not do anything
> + do what you expect
> + SEGV
> + format your hard drive
> 
> --Eljay
> 
>

RE: Strange shifting behaviour

[John Yates]

Eljay,

Though I agree with your point about the standards and
undefined behavior, I do believe that Ulf has identified
a quality of implementation issue.

Would you not agree that compile-time expression evaluation
should mimic run-time as much as possible?  Or to put it
another way, the more often compile-time and run-time
evaluated results diverge, the lower the subject quality
of the compiler.

If the shift operator at run-time examines only the lower
order 5 bits of the shift count (as Ulf's x86 does) then
a "high-quality" compile-time expression evaluator ought
to do the same.

/john

-----Original Message-----
From: Eljay Love-Jensen [mailto:eljay@adobe.com]
Sent: Tuesday, July 12, 2005 6:46 PM
To: Ulf Magnusson; gcc-help@gcc.gnu.org
Subject: Re: Strange shifting behaviour


Hi Ulf,

>When shifting an int by its size in bits...

That is undefined behavior (implementation dependent), as per C and C++ standards.  Ever since C was first taking it's first baby steps.

By "undefined behavior", that means any given particular implementation can:
+ not do anything
+ do what you expect
+ SEGV
+ format your hard drive

--Eljay