optimization/4108: optimizer produces incorrect assembly output for a bit test equality expression

[ben at proximity dot com dot au]

>Number:         4108
>Category:       optimization
>Synopsis:       optimizer produces incorrect assembly output for a bit test equality expression
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          wrong-code
>Submitter-Id:   net
>Arrival-Date:   Thu Aug 23 19:06:02 PDT 2001
>Closed-Date:
>Last-Modified:
>Originator:     Ben Ross
>Release:        3.0.1
>Organization:
Proximity Pty Ltd
>Environment:
System: Linux mantis 2.4.2-2 #1 Sun Apr 8 20:41:30 EDT 2001 i686 unknown
Architecture: i686

	
host: i686-pc-linux-gnu
build: i686-pc-linux-gnu
target: i686-pc-linux-gnu
configured with: ../gcc-3.0.1/configure --prefix=/usr/local/gcc3 --enable-shared=libstdc++
>Description:
In a particular circumstance, the optimizer makes an incorrect assumption about the value
of a given expression, only if one of the inputs is a particular value. This assumption
results in assembly output with a constant value for the expression such that the expression
is completely optimized into a constant.

The expression is as follows:

byte & bit == bit

where byte and bit are of type short. Iff bit == 0x8000 and byte is only known at runtime
the optimizer incorrectly assumes this expression always evaluates to 0. When bit is some
other value, e.g. 0x0001, the assembly version of the expression is output and the program
executes correctly. Observing the difference in assembly output for different values of bit
reveals a combination of a right shift (shrl) and bitwise and with constant 1 (andl) being
used to (correctly) evaluate the expression where the amount of right-shift depends on the
value of bit.

Pure speculation follows:

Perhaps in the case where bit == 0x8000 the right-shift is shifting this value to 0, which
could cause the optimizer to assume the lhs of the original expression is always 0 causing
it to produce constant 0.
>How-To-Repeat:
I have put together a test program. Compiling without the optimizer produces the following
(correct) output:

testbyte = 0xffff8332 checkbit = 1

Compiling with -O2 produces:

testbyte = 0xffff8332 checkbit = 0

Here is the compiler output during the compile:

Reading specs from /usr/local/gcc3/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/specs
Configured with: ../gcc-3.0.1/configure --prefix=/usr/local/gcc3 --enable-shared=libstdc++
Thread model: single
gcc version 3.0.1
 /usr/local/gcc3/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/cc1plus -v -D__GNUC__=3 -D__GNUC_MINOR__=0 -D__GNUC_PATCHLEVEL__=1 -D__ELF__ -Dunix -Dlinux -D__ELF__ -D__unix__ -D__linux__ -D__unix -D__linux -Asystem=posix -D__OPTIMIZE__ -D__STDC_HOSTED__=1 -D_GNU_SOURCE -Acpu=i386 -Amachine=i386 -Di386 -D__i386 -D__i386__ -D__tune_i686__ -D__tune_pentiumpro__ bittest.C -D__GNUG__=3 -D__GXX_DEPRECATED -D__EXCEPTIONS -D__GXX_ABI_VERSION=100 -quiet -dumpbase bittest.C -O2 -version -o /tmp/ccvEmfPh.s
GNU CPP version 3.0.1 (cpplib) (i386 Linux/ELF)
GNU C++ version 3.0.1 (i686-pc-linux-gnu)
        compiled by GNU C version 3.0.1.
ignoring nonexistent directory "/usr/local/include"
ignoring nonexistent directory "/usr/local/gcc3/i686-pc-linux-gnu/include"
#include "..." search starts here:
#include <...> search starts here:
 /usr/local/gcc3/include/g++-v3
 /usr/local/gcc3/include/g++-v3/i686-pc-linux-gnu
 /usr/local/gcc3/include/g++-v3/backward
 /usr/local/gcc3/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include
 /usr/include
End of search list.
 as --traditional-format -V -Qy -o /tmp/cc43wWkx.o /tmp/ccvEmfPh.s
GNU assembler version 2.10.91 (i386-redhat-linux) using BFD version 2.10.91.0.2
 /usr/local/gcc3/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/collect2 -m elf_i386 -dynamic-linker /lib/ld-linux.so.2 /usr/lib/crt1.o /usr/lib/crti.o /usr/local/gcc3/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/crtbegin.o -L/usr/local/gcc3/lib/gcc-lib/i686-pc-linux-gnu/3.0.1 -L/usr/local/gcc3/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/../../.. /tmp/cc43wWkx.o -lstdc++ -lm -lgcc -lc -lgcc /usr/local/gcc3/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/crtend.o /usr/lib/crtn.o

And here is a uuencoded bzipped tar file (bittest.tar.bz2) containing the following files:

-rw-r--r-- ben/px          521 2001-08-20 11:44:26 bittest.C
-rw-r--r-- ben/px        26018 2001-08-20 11:48:49 bittest.ii

the first is the test program and the second is the preprocessed version.

begin 644 bittest.tar.bz2
M0EIH.3%!62936>^*9*$`%U__@OPP__M_____O^_?KO____X@``0(8!COOO@!
M;S7CO/5F2JB[;8RM>]ZYZH77G9WN<UP-.SLY[GKR@>J:TUA=M9D@`!30'4F`
M0Z;=<G"1(4Q/29)HU--IJ1IZGJ#:)Z0/4P:3U&F$:-``#0`R`](-3T":B2;U
M1M3"#0:&@9&1H9#0/4`T``:!IHTT:`'```-`T-#0TR`#0``:`:&@``9```DT
MDB$T3(GJ::AY-0:-&@&FFFC0``#0``T]1Z1D`"))$U3U/TFIZ:9-(&FC34--
M&@#(-&@`&F@#0&@:::,@(D@@@331,3294_4GJ?J:1ZCU-&@```T```:`&@'X
M'V]?H'D_D9>P'8(1K3(`Z7#$'3&=-CH&1*8`*6,8)]!186P+0!%F]"$BUTMQ
M\)<*"'5`\$VHBR(ES"HDB%,25#&$P,L`6+/DCIALPT%?7XFAUIR(H@Q1!%18
MJL$$46"P5:R6#SMKN5F&U_/0!XDA-T6:8HNTQBXE9>#0,5%@6I5%B(%6J$HI
M5LL152I_3VSSL#>&T9%$3XSWM5B@]QJQ@*L6*@J*+$66EK=I4=J&.2I46MK9
M;2LHBJM+1515J$JBHL9PDH8EEKA6UJRB5A1%%&"@B,6I1;$6Q8TLK+G[>HZ#
M(>VA_74A[75_;8X]`.,QBOT3D0N+N_L%#60$>3!1_HB*)E12#T,61'XQ"I"#
M(`2(,@$@RB*!ADY/5I@X`8X:8"QI@K&!WH%OI)%7A0Y>J5$3!=P&!"B4J11H
M1ZH\62EC3*FQF5!D#MBT/S]-QG>:6+K7:^,%Y+>$_,2T2?XH`8/[[[(SNBF\
MQ\-A]\K9AEJ@8[-Y8=-J$(MJB6FS+FO$-X$BK)<.Z^=7G#.M"G%OH5(Q;M2R
MWE<DKZY<MXB1,VX[Q;D;*HNK!*16<0VS!L;PR%6\N:D3F]J@07T^%;BI1EP8
M5(=[TQHID)?/O;-Y,F!P9R591#!M![(5:FL!BKW,8*'>.%A89],#29C@E@82
M5A9X!,#?4%4,L@-K)F+QU`AK>ZP;UX5$BE&5$O5W9#TOAE)VR>:)['OJ/4$;
MZ1J=FD&RV1UJV0.B5"09(L44%$2A"L-0T$4)/R"=,G?\PTE3Y7MV.YW+VV!K
M2.\6-.TKNB[+KM[G<N0Q#H.6A/XB'"V<W+DDX3[%J2TT8D>.`;":PY*0/?#I
M%X0&UOKEC0/ERV.)&\!P]"#:"V9`]Q=]&19(H)O3:'.DW9T(;ZI;;;;9%G/5
M)H.-)."`/$=%ICAF'Z8R35AT)O-YO(0`XP3ML:D.%P20`S=*@:Q*=R!>/&-0
M7B,6H0FA.K"`2&I<X6&)-#J)(&<@-2C(@84/I'HFY8CG$9P@MY>$@A40XB;#
M>%S*&QHZH[%#AOMFRFFP-C1OK1FK#=TFB7+MOEK5D,I8%O!+YTO<2\%F5F&]
MJK--Y8VPQ.$.L:],%%$APD,K%@FV,XG#+!0:%UP&7;9@(GH;S#&:]*F*@S<-
M1.V0)-@NVVV*3#(`I9NTT:#!T%XA+)3>O@8"O9UK:X_GGTB,B@$-BR*C>&EP
MOBZC0'`R&N5B0'`XHM0TKG:,T0'K9(2D4-%A(24@BC!")WQ*1/G*!#MU"47C
M,4#6+%AL10^UDK3U/YF2*_GF_)W(6V=8YZX-T4\1I>,>*IA,D>8LJ1F#BLF7
M.XAW[U]W5$?FTKP25Z;CCQY..M&5J<'LSN7AJ;8SHN;/#A<O7C:YLYQ-G*9#
MBF.2]M#KSG&=[YRIZOH7&S:.Y-V0YP[%'F:1$.PO#I0Z21)!Z1*@VUI;2$-,
MO?Y8P+(E]\V;Q`D(16-RSI]5^$Y^%[6@:>0'`@G1$)09#&2(K%BQ8`9%A:"2
M",8C&*JY2Z?<]O3A).[GYZ=+-\6HQ*1.5"(?1R.^ED3@VK"!VT`R^LSLZ/W^
M[ARX889R`7H^LY0]0(PMD[1[$GK$\-NU8^#S(:O(R:#C2[`MJM1:$*Q4&14.
M<:C""28,N`Z`+::Y@2ARN8@<*KD%7UE7A%+U-*KG#:SYZ.Q`KU&M/?]TP3MS
M2[[RFQA=+FIA<IB6ZS,LJKB`WRTNNHR$#C=,QZ?@5=:#EB_VJ[ZK0TJ\`1^*
MK!.JK<6E7*4I(@2,TJE\T5**(NYH>_4GT3X80]BKD/J/:,.`D*PM(+7O^.S(
MYJK,A,[A(*#/Z,R#+8=HQK@&3:$O^K9H@&DQ!',+\['V\4:YJCXV"M2`Z1K"
M%SZ+H+NXTK?C.,TJ0Q"S#2QC07%Q0-H&(G$X\7<..$5.GCON<-.?'5/@J_?*
MM`;YZAIPV,F\X\2519V)FM-.*Z3<UHJP43:(<["FM]R.$D*OM?#H;JNSG[6W
MK]:3[!\US?4S\\B2.G5J6)]?!H<S[:K!V.70[H9T)>\ZE(V"AN%K<TDKIWCL
MMR70:RPC(CU]6_L5T;4<?1$FOIW"8;W"05!#DAK#BXL/.U9L_*9.2;@P:;`<
M-E;8-S16G!;TKA!1FX3AHK?*K[&7D-9($J_0<*[F["=Z-5"Z$I&^1DQ"LEX2
M4C<)+V1?_C-BG(+X@A:3I7Q:<=S<N66)!)!,$JH4W2+(-R!P[9$+02$3$I7C
MW'='OJ=.5G3?IX2[9J!=]=IC\))(U-'>0#1^OB?B_;FG?74#$M6M7>/*"]^+
MJ@(7MC7B3.W/JLQG<=ND@HDNZT80,_C^_V?9U7^'DO"3C2BQ5!06$1A2DB$@
MZB`T=ZD#M,>\JC![Y%%-$UNS=DV:N-E$>Q]VAW^ZWYZDXYU?*APC[2\X"Y\[
M5?(BGMDN8FCIMJ0M5:G#;I'D&SGG:4:'6P;Y]U@GFX3K,XNM\'`;GA.0WSIG
MR=<[(^Z9L.27,0"DMI=>6/'VCS?`]=J0K&$X!=\#2@@D%/[LE1=!`-IB?/![
ML1/2)`EB#3(,OXH&''.<=A0VQ-A'GAX-X1.J%B#$@P&*!,!LAC8#&JB,%$$\
MOM9D]37E]H=CUO5NEIZWG:)R.?N<\KY+L;0T"J"S]@,*A)DA2,:15!9(JP5C
M.759S2G*_WZ;`#CQL"L@@V)%D%B,D&(,8Q+(D*P9(056`J1(*6)*P!2*H@**
MH(@LBJ+(T!B4+!2(@I\6\CXY%#>Y]BKMVUKS)!R$4<.W1V7)2<4.)ZX%@`?=
MCX4.B3V+XWJ=^N):6E9R`03G.M+^[==F>.DT36%U^*YFLP7;5S)TG`L-_D55
MZ&Y^[FI5%55D0[@Q@L-=^,S%DOA$(10]'"LS,*,UG4E]2-1;T@F&6OOW*QB=
ME`Q-=9-F&4OP<4BV;Z0W8;<5S$%S9:O^D><E:S:9:,$.[/.<IP*YE9%(EF?I
M`TK,^U).LZPP/&+?B2!"ZRMRSU"23GSN'5S2;Z3CFRBG2(;OI2)H<L60W=\&
M9?CRH#:"'J3MA*!`X)L<>Q#YG=>63,IIH_+/3-S=-#;*D/#NKF0.P-:VKHS+
M#33GN<O!G@Y<#'WJ"0%E2M58A[TPUT2QO6A78)6VD83O?F62!BUMI6I/'Z)/
M#+2GE;(7#,PV)L;&DC6VPUYK?!*-ASEA>YD@RP<S1QUR)&EA.1J-JR1=77;,
M4[$8.2EYI>=<Q+X#N('`%`PMK(@F^!(1Q/^S88%+&MW9!FWG#ZK4DL=,%MD^
M92;B$D`X$9QKH)@`ZEA1#<@<'N[6>!2G0FX=YI$]E^GFF1'07BIQYZ?">/=I
M97FNOH;AWBKUF1"VS?I,2JK1[!0DV2.J@+^RO)J.=NX9VV8FK(O<G+S[:)K<
MHA#O5H.I(1/6(7=HLB'DJ^JK%6VE_#&5Y*W,JNX,_D%6QX\`KK-0]@G,"*K(
MQ(20(#WQ4PIC`58=P.W"$",&08SJ,`"FYH<_7Y6"N0JG4]T)<3<B&I!!D.9#
MZB(\>]%\(CO<=(,D>E!`+>"F\0-`Y21!HD+0"H01"%E"(%@DSN;0.%R&&+>+
M1![HT*6(E(L"`$2)33-[W*:-AU/-RF".6BG^S4D,(S!!-[3$#2\:8V*=O`@N
M.M@+IQ%4[E-"Q$$?4#_1Y:.YN4::H7$O<`*J]^>$-CTT51:>5<LN?9;86[M;
M310RS"8E*%Y,]C+(DQN)V*:)#$T14JI,;7JUYG!>-K>E%NU[*Z!V=.=#*TX5
M56DZ+)3A`K)!C`YV\7GACHH.L`0U.J\_@.#_XX)ZJF!!P8UYVO9R%F'0.JH-
MB^`T&\#*@O+12DIZ8VRC>+48IIT:*J6RC.Q&FBN1FYOAYUI@,O+`#JE6[-TO
MW>)WG@G+OT5`-\:DKJ<#OJCCC;RJ')#A.,8C$:!3`@A)#8,3Q0!15F2%N=&M
MI1G1#L\H]Y4ODO:XR&BXX+)$86C<R?Z=)H*XFF&DT@B6YA61$E2FKIU:'6<N
M2]<\6=VZF"C`J$]JH-8.4,LN!0E.7"T67)E/0BIP<*Y+KL:PEK5@B7T4P,#*
M!J,PZ\N_5#A)G:'1EO:L47J.>I`YRRA`W%45\%>UO2)?!'>&+R.K"S`EX)4A
MPV3TB)P!H#8=V0`WA`WXW3SS55Q;>S4Z7/'OT$![:KQ[*W&,*R_:BIIE5:"*
M%,5Z+GL#NB`EV/'5;<O@10S*\W&E%+<DKG4HGCQ]NGMVQ=0U/C[`-1![4)SB
MFW(;$/`Z)(="_WO5%3QYAJ;L!Y1.KJ$&O>>WWD*JCL7G*$#B!B$91%"=:FHI
MP1`J)4NB*$BVU$DDDD.0,V*,S*LSZEA(0)`A`A)",I"1#W'FG432^-M5#34`
M@91/83R"Z!42;BC1M[OA`/="HD"+OO0EK!2IJ&2ERH>=C[%S0-*D(9.``<H>
M@0M[R$![N>IN<..0/55^"K\]"[]'3N*/`[U)=*U5:`,$Y+GI"=Y<MUMP5=TW
MRGC).MK02T!T^S4E8NOD*2@+*>/?853EU]0R6R3,A*@"%$P:,E2T]Q/2!V$8
M&8F4,ZVK%%&-2P!WE=Q4)H-W:QDU0\]+AH$@74"!`0?\7<X3>,F2D)"%;PW&
MU$H*TY-QSPA3G(JE<1*I-HE!!N7*O8N@?6$&9")VI,"8`NQ1@:2$0+PH!TJ2
M6/4YZ`&B:(IE*`0SH@H]6!?!2V:*PP%W53#>RK<%)K[/#VV+BA>U^Q+B5!HC
M<X'B0C0@?/$!Z9\!Z)!.8\-A=($CJBDY(E4=M?!AR!O0.BC9*$0/0F>[AX\K
M6^>L1RT(\Q3C*F(&C$,4-HS39'%0`P4KD/8]_)8$98]A!VRF\^95[MO#W*@X
MI"UA-"[Y$"G7P\SSPE'1*8DCY[S9/$V,&<>.@=@AQ@PB"AY\H3(HDZ'7"OGN
M594D_H+@Y]Y._SA>ZH-R`;)[2H$&T!+`5),>-+=3JBIC,+D[MG,\L7S09S*+
MMMC2EN`8HY>'N#E!(Q($")$M33D!#EEQT(9L<E]UD5,`[K@741&N!D%]PI;E
MD-3)81N[+!80D4!D0-VX\5`"PZ$$RI6Z`%M1)17O,-@V:+DQ3)CNL6+UY2S&
M+:-+P]]*>NZ!E=C-7&9*4I52+!@QP-,9LD6EY>.UPMC<TDUYFE#T`V-N]*&G
M?V9"B&;RS;@T2%7.C5TMP@IBDIL;!-B&P;2DC5G>/'RV'8U_8\DVV,.7DIR<
MM#N-!8-WQ&$+5"YJE+2A)$1-!O(>P"$/)('P6[H3XPLD<*_,)ZV^255E3[DN
M\8XPKPY)\K*@;**:*5`^4#\':QACXTRZ#*/B;HHJBPT?'IU<N17%]$ZB8AZ6
M0,PG;22Y1PF!0B"&48G?D&@BF`A"MC$%A4`1)!N6F6R(J-EK*E&6"4MJRC<N
M#B,I2E`2LLD986A02R`D8GHI#&,:RCDFJ,"3+)+5L$9$401U-2D#0@N`V1!$
MF&P@79769FH=^6R][O)N.&2@-H7;1PX8-A9)G3I201H+%OIJUK@8AK>E'>&8
M:3)G82O/AF$DH,Z(3Y:"WX:HLVWE6$C4C`@PA"A(Q1-_H61-(53A6@"DA/D^
M?)-!O$,'(G/"(!;;Z$[SQ)Y?CDM8D.;H*])5LIO`PD`609$6133R-9LT!;0A
MX/>G8*T8''B`]4DN`9`0I6`J'@=#0X(%50\$3$6RDA>_3T9)%^S%>T%`OIV9
MII/,124\24:ZP`S129X?BI(2&D`-M0ZHGD[ERN\@!O*J7]``PZD4,4MO;M5]
MO%019=G4"1(UD@X6'N-$A:1D"'"&'C'!N"&T$N=&B^\UHJ?\95.`'6KXC0:J
MK]Y`>"ASY37XGI26Q"9HZLDGX<:"$DD5BSYIB!U2M%`#>(2'"QNL#OG52!=J
MRID<+]DX8`5`VSK':+N)5I=1F815`T:->U<0L@+MINJ\0H[9JA"$!A(119YE
2H016`+23_XNY(IPH2'?%,E"`
`
end
>Fix:
This isn't a real fix, but in the case where bit only has one bit set
then doing the following is equivalent, and produces the correct output:

byte & bit

Of course, if bit has more than one bit set, then the compiler might
produce the correct output (I didn't test this)
>Release-Note:
>Audit-Trail:
>Unformatted: