optimiser emits ud2 (invalid-opcode trap) for a fully defined C loop at -Ot and

[KEL26]

Code Select Expand


Hello Pelle,

First, thank you for Pelles C — it has just carried a full port of CFITSIO
4.7.0 (NASA's FITS library, 59 sources), zlib, libpng and FFTW 3.3.11 to a
clean finish, so the report below comes from a codebase your compiler
otherwise handles admirably.

SUMMARY
-------
Pelles C 14.50.0 for Windows x64, compiling the attached self-contained
program (about one screen of code), translates the loop

    for (i = 0; i < 200; i += 1) {
        data[i] = (unsigned char)(i % 256);
    }

(over a local  unsigned char data[200])  into a loop body whose FIRST
instruction is  ud2 , so the program dies with exception 0xC000001D on the
first iteration. The store that follows the trap reads  al , which no
instruction in the function ever writes — the value computation has been
deleted entirely. The statement is fully defined ISO C: i is in [0,200),
so i % 256 is well defined and non-negative, the conversion to unsigned
char is well defined, and the store is in bounds.

ENVIRONMENT
-----------
    Pelles C 14.50.0, Windows 10 x64 (build 19045)
    pocc -Tx64-coff -Ot -W1 -std:C17 -Ze pelle_repro.c
    polink -machine:x64 -subsystem:console pelle_repro.obj kernel32.lib

OBSERVED (same source, three settings)
--------------------------------------
    -Ot          RESULT : EXCEPTION 0xC000001D
    -Os          RESULT : EXCEPTION 0xC000001D
    (no -O...)   RESULT : SURVIVED   checksum 19900 (expect 19900)

DISASSEMBLY (podump /disasm of the -Ot object, the loop in full)
----------------------------------------------------------------
    [0050] 0F0B            ud2
    [0052] 4863D3          movsxd  rdx,ebx
    [0055] 888414EC000000  mov     byte ptr [rsp+rdx+0ECh],al
    [005C] 83C301          add     ebx,1
    [005F] 81FBC8000000    cmp     ebx,0C8h
    [0065] 7CE9            jl      0050

NOTES THAT MAY HELP LOCATE IT
-----------------------------
1. The mistranslation is sensitive to the surrounding frame: the identical
   loop in a different function (static buffer, checksum in a separate
   loop) compiles correctly at -Ot on the same machine. The attached
   reproducer therefore keeps the exact frame of the function in which the
   fault was first observed — the same locals in the same order, and calls
   through a volatile function pointer where the original code called into
   a library. Simplifying the frame may make the fault vanish.
2. The pattern (unsigned char)(expr % 256) appears in a dozen other files
   of the same project that compile correctly, consistent with note 1.
3. Discovered because a unit test of the CFITSIO port died with
   "CRT: unhandled exception" before its first library call; an
   __try/__except wrapper reported 0xC000001D, and podump named the ud2.

A SECOND, UNRELATED ISSUE, MENTIONED FOR COMPLETENESS
-----------------------------------------------------
The same project also hit what the evidence indicates is a stack-slot
assignment fault at -Ot in one large function of CFITSIO's imcompress.c:
two live locals (a 4-byte char array, address escaping through a pointer
array, and a 12-byte char array) appear to have shared storage, so a
12-byte strcpy destroyed the 4-byte string; rearranging the locals into
one union cured it. An isolated replica of the declarations does NOT
reproduce it — the full function seems to be needed — so I am not
attaching that one until it has a reproducer worth your time. I can supply
the full analysis on request.

With thanks and best regards,
Kelly
Attachment: pelle_repro.c

[TimoVJL]

A smaller test:

Code Select Expand

//#include <stdio.h>
int __cdecl printf(const char * restrict format, ...);
int __cdecl main(void)
{
    int i;
    unsigned char data[200];
    for (i = 0; i < 200; i += 1) {     /* the suspect loop, verbatim    */
        data[i] = (unsigned char)(i % 256);
    }
    for (i = 0; i < 200; i++)
        printf("%i ", data[i]);
    return 0;
}


Code Select Expand

test_loop.c(8): warning #2803: Attempt to divide by zero.

[Michele]

The instruction UD2 should have been designed specifically for testing.
Perhaps this is a typo from the compiler testing phase.

[KEL26]

Code Select Expand

Thank you TimoVJL for minimising my test case. Your version was much better than
mine, and it changed what I think the bug is.

My original file preserved the whole stack frame of the function where I met
the fault. That was based on a real
observation but the inference was wrong. You removed the frame and the fault
survived, so please treat my frame-sensitivity note as withdrawn.

What your version did that mine did not was move the fault to compile time,
where the compiler names its own reason:

    test_loop.c  ( 8 )   :   warning #2803: Attempt to divide by zero

on   data[i] = (unsigned char)(i % 256);

I have since measured it: thirty-two variants, four optimisation levels, both
extension switch sets, all first validated under gcc -O2 -Wall -Wextra where
all thirty-two pass without a diagnostic.

THE PART THAT MATTERS MOST
--------------------------
The trap is the lucky case. Change 256 to 300 and there is no warning, no
trap, and no ud2 for anyone to find:

    int CDECL main(void)
    {
        unsigned char data[200];
        int i; unsigned long sum = 0;

        for (i = 0; i < 200; i += 1)
            data[i] = (unsigned char)(i % 300);

        for (i = 0; i < 200; i += 1)
            sum += data[i];

        printf("checksum %lu (correct 19900)\n", sum);
        return 0;
    }

    -Ot            checksum 4060
    no optimising  checksum 19900
    gcc anything   checksum 19900

i is bounded to [0,200) and 300 is larger than 199, so i % 300 is i and the
answer must be 19900. 4060 is the sum of i % 44, and 300 modulo 256 is 44.

THE RULE, AS FAR AS I CAN MEASURE IT
------------------------------------
    IF   the operator is %  (not /)
    AND  the divisor is a signed integer literal K
    AND  the compiler can prove the numerator stays below 256
    AND  the result is converted to an unsigned type narrower than int
    AND  optimisation is on
    THEN K is replaced by K mod 256.

         K mod 256 == 0  ->  #2803 and ud2
         K mod 256 != 0  ->  nothing said, wrong number computed

The eight is fixed. It does not come from the destination type:

    (unsigned char)((i*300) % 256)   numerator to 59700, dest 8 bits   CORRECT
    (unsigned short)(i % 65536)      numerator to 199,   dest 16 bits  TRAPS

and it is not the exact width of the numerator's range either:

    (unsigned char)((i*3) % 1024)    numerator to 597, exactly 10 bits  CORRECT
    (unsigned char)((i*300) % 65600) numerator to 59700, 16 bits        CORRECT

WHAT IT IS NOT
--------------
Division is unaffected. 256u is correct but 256L is not, so the signedness of
the literal matters and its width does not. A non-literal divisor is correct,
even a plain int k = 256 that propagation would fold. A signed destination is
correct. A numerator of rank above int is correct. Unoptimised code is always
correct. And -Ze makes no difference at all: 256 combinations run twice,
identical results.

WHY IT MAY HAVE GONE UNNOTICED
------------------------------
In every failing case the numerator can never reach the divisor, so the
remainder was mathematically redundant to begin with. Ordinary code, where
the divisor actually bites, is untouched. The shape that breaks is the
defensive one -- a remainder written as a safety net over a value already
known to be a byte.

The cure, for anyone who needs one today:

    int t = i % 256;
    data[i] = (unsigned char)t;      /* correct at every level */

My full set: the twelve-line case above, all thirty-two
tests, the harness, the generators, etc and the raw logs - no idea where to post them, if they are needed.


Kelly


[Vortex]

There is something unclear about this line :

Code Select Expand

  data = (unsigned char)(i % 300);
Whay not this one?

Code Select Expand

  data[i] = (unsigned char)(i % 300);

[John Z]

HI KEL26,

First, thank you for Pelles C — it has just carried a full port of CFITSIO
4.7.0 (NASA's FITS library, 59 sources), zlib, libpng and FFTW 3.3.11 to a
clean finish, so the report below comes from a codebase your compiler
otherwise handles admirably.

If you are allowed, and if you don't mind, could you please post the pelles .ppj for the zlib build?
If not, no worries, thought I'd ask because I tried to build this in the past but seemed to run into issues.
 
Thanks either way for posting on the forum!

John Z

[KEL26]

Thank you Vortex, but the [ i ] is still there — the forum ate it.   [ i ] is the BBCode italics tag, so outside a code block 'data [ i ] =' ... renders as 'data = ' .... My source is correct. Reposting inside code tags:

Code Select Expand

        data[i] = (unsigned char)(i % 300);

Apologies — I should have wrapped the whole report in code tags. Anywhere else in the post that reads 'data = '  should read ' data [ i ] = '

The rest of the thread: every line with data [ i ] outside a code block will have been mangled the same way.


More than happy to share my code John Z  , I need to know how to do that - anyone guide me or direct me to instructions please?

[TimoVJL]

Code Select Expand

int __cdecl printf(const char * restrict format, ...);
int __cdecl main(void)
{
    int i;
    unsigned long sum = 0;
    unsigned char *pdata;    // pointer to data
    unsigned char data[200];    // safer stack place at end ?

    pdata = data;
    for (i = 0; i < 200; i++)
        *pdata++ = (unsigned char)(i % 300);

    pdata = data;
    for (i = 0; i < 200; i++)
        sum += *pdata++;
        //sum += (*data)++;

    printf("checksum %lu (correct 19900)\n", sum);
    return 0;
}
also with

Code Select Expand

sum += (*data)++;output

Code Select Expand

checksum 19900 (correct 19900)
EDIT: a simple check

Code Select Expand

int __cdecl printf(const char * restrict format, ...);
int __cdecl main(void)
{
unsigned char *pdata; // pointer to data
int i;
unsigned char data[200];

pdata = data;
for (i = 0; i < 200; i++)
{
*pdata = (unsigned char)(i % 300);
if (*pdata != i)
{
printf("\nerror: %u != %u\n", i, *pdata);
break;
}
printf("%u ", *pdata);
pdata++;
}
return 0;
}



[KEL26]

Thank you TimoVJL for looking at this again.

I have built your version and I am afraid I cannot reproduce your result. On
Pelles C 14.50.0 it prints 4060, not 19900, and the object code shows why.

Code Select Expand

pocc -Tx64-coff -std:C17 -Ze -Zx -Ot -W1 timo.c
checksum 4060 (correct 19900)

Unoptimised, the same file prints 19900.


WHAT THE OBJECT CODE SHOWS
--------------------------
podump /DISASM on the -Ot object, x64:

Code Select Expand

mov     r8b,2C          ; 0x2C is 44
mov     al,dl
xor     ah,ah
div     r8b             ; 8-bit unsigned divide
mov     al,ah           ; take the remainder
mov     byte ptr [rcx],al

and the same file built for x86:

Code Select Expand

mov     cl,2C           ; 0x2C is 44 here too
mov     al,bl
xor     ah,ah
div     cl
mov     al,ah
mov     byte ptr [esi],al

The source says % 300. The emitted code divides by 44. 300 modulo 256 is 44,
and the divide is the 8-bit form. So the pointer store does not avoid the
rewrite: it is present on both targets and in both spellings.

I also built the array-subscript version with the identical declaration order,
and a pointer version with the array declared first. All three give 4060. So
neither the store form nor the position of the array in the frame changes
anything, and I do not think the stack placement is involved.


WHY I THINK YOUR RUN PRINTED 19900
----------------------------------
Your post mentions that it also gives 19900 with

Code Select Expand

sum += (*data)++;

That line does not read the array. It reads data[0] two hundred times, adding
the old value and incrementing it each time. Starting from data[0] == 0 it
sums 0+1+2+...+199, which is exactly 19900, whatever the other 199 bytes
contain.

I checked this rather than assuming it. Filling the array with 0xFF on
purpose, setting only data[0] to zero, and then running that loop:

Code Select Expand

for (i = 0; i < 200; i++) data[i] = 0xFF;   /* deliberately wrong */
data[0] = 0;
for (i = 0; i < 200; i++) sum += (*data)++;
checksum 19900

19900 from an array that is wrong in every byte. So that particular check
cannot distinguish a good build from a bad one, and I suspect it is where the
19900 came from.

If you ran the *pdata++ version with sum += *pdata++ and still saw 19900,
then something in your settings differs from mine in a way I would very much
like to know about, because it would bound the fault further. Would you say
which target and which optimisation setting you used?


WHERE THIS LEAVES THE WORKAROUND
--------------------------------
For anyone hitting this today, the form I would suggest is still

Code Select Expand

int t = i % 300;
data[i] = (unsigned char)t;

not because it dodges the trigger, but because the remainder is computed in
int and stored in an int object, so the narrowing-to-unsigned-char condition
is never met at all. It is correct at every optimisation level I have tested,
and it stays correct for a reason that does not depend on which shapes this
release happens to recognise.

I would avoid % 256u for the same reason in reverse: it works, but only
because the rewrite does not reach the unsigned-literal path in 14.50, and
that is a property of the release rather than of the language.

Thanks again for minimising the original case. That edit is what moved the
fault to compile time and gave us the #2803 message to work backwards from.
===========================================================================

[John Z]

Hi KEL26,

More than happy to share my code John Z  , I need to know how to do that - anyone guide me or direct me to instructions please?

Thanks very much!

Pelles makes it fairly easy.  Under Projects Menu there is a ZIP File menu selection.  This will ZIP the entire currently open project (zlib) into one file which then can be posted as an attachment, at the bottom of a post.  Up to four attachments can be made on one posting.

If the file is too large delete the object directory from the zip file.

This is also a convenient method to archive and store inactive projects or to keep back-up versions.  Unzip with standard tools and the project continues from where it was.  Also no need to unzip into the same path/structure.

Appreciate the help!

John Z

[KEL26]

Code Select Expand


The defect, stated exactly,

At -Os, -Ot and -Ox, Pelles C 14.50 for Windows x64 can replace the
constant divisor K of an integer remainder by K modulo 256.

I attach a zipped folder (edited) showing how to build a bug/defect free zlib (no source patch is required) and folder of code which shows evidence for this bug and my bug tracing code!

Hope it helps others - and hope soon this excellent IDE and compiler become open source - it would make the process of bug tracking and fixing super-fast - I am from a Linux background.



[John Z]

Hi KEL26,

Wow what can I say? Thank you!
Exemplary, superb, an excellent piece of work.
Thanks for your work and help and I appreciate the
time you spent doing the extra extensive documentation.

John Z

[KEL26]

Please reply with the information I request. Thank you, TimoVJL.

Your second program is a better test than my checksum,
because it can fail on the exact element that goes wrong, and I have adopted it.

Compiled exactly as you posted it, with no changes, on Pelles C 14.50.0 for x64:

Code Select Expand

pocc -Tx64-coff -std:C17 -Ze -Zx -W1 -Ot check.c
polink -subsystem:console -machine:x64 check.obj crt64.lib kernel32.lib -out:check.exe
check.exe

it prints

Code Select Expand

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
error: 44 != 0

The same with -Os and with -Ox. With no -O switch at all it prints all
two hundred values and no error line.

The object code for the store that your check reads back, at -Ot:

Code Select Expand

mov     dl,2C            ; 0x2C is 44, and 300 mod 256 is 44
mov     al,dil
xor     ah,ah
div     dl               ; the 8-bit divide
mov     al,ah            ; the remainder
mov     byte ptr [rsi],al
cmp     byte ptr [rsi],dil

44 mod 44 is 0, which is the 0 in the error line.

Your first program, the pointer checksum,
behaves the same way here: 4060 at -Ot, -Os and -Ox,
and 19900 with no optimisation.
So the pointer form does not avoid it on this machine,
and neither does the position of the array in the frame.

That leaves exactly one difference between us: the optimisation switch.
Would you run your own check with -Ot given explicitly on the command line, as above,
and say what it prints? If it prints the error line, we have the same result.
If it prints all two hundred values for you at -Ot,
then something differs between our installations that I would very much like to identify,
and the first line of

Code Select Expand

pocc /?

would help.

For anyone hitting this today, the form I would still suggest is

Code Select Expand

int t = i % 300;
*pdata = (unsigned char)t;  /* see my note below, just in case any one wants to write to me! */

which keeps the remainder in an int object, so the narrowing to unsigned char
is never part of the same expression and the rewrite has nothing to attach to.

Code Select Expand

N.B.
Why *pdata is right in TimoVJL's loop

TimoVJL's check walks the array with the pointer itself:
it stores through *pdata, compares, and then does pdata++ at the bottom of the loop.
Inside that loop the current element is *pdata, full stop.
My suggestion keeps his loop shape and changes only the two lines that matter — compute in int,
then narrow — so he can drop it straight into his own program.
I verified it: at -Ot it stores all two hundred elements correctly and the check never fires.


Using pdata[i] inside TimoVJL's loop would compile, but combined with his pdata++ it would
advance twice per iteration and write to the wrong places.
Using *pdata inside an indexed loop would write every value to element zero.
Each form is right in its own loop; *pdata[i] is right in neither.



[TimoVJL]

Kelly,
You found a bug and now we have a small example code for it, so now just wait Pelle's opinion.
Using pointer was just an another test for it.

EDIT: for minimal executable for debugging, but needs msvcrt.libs :

Code Select Expand

#pragma comment(lib, "msvcrt.lib")
int __cdecl printf(const char * restrict format, ...);
int __stdcall ExitProcess(int);
void __cdecl mainCRTStartup(void)
{
    unsigned char *pdata; // pointer to data
    int i;
    unsigned char data[200];

    pdata = data;
    for (i = 0; i < 200; i++)
    {
        *pdata = (unsigned char)(i % 300);
        if (*pdata != i)
        {
            printf("\nerror: %u != %u\n", i, *pdata);
            break;
        }
        printf("%u ", *pdata);
        pdata++;
    }

    ExitProcess(0);
}
EDIT: useful Add-Ins ?

https://forum.pellesc.de/index.php?topic=5248.0

https://forum.pellesc.de/index.php?topic=4467.0

https://forum.pellesc.de/index.php?msg=26516

[Robert]

Code Select Expand

int __cdecl printf(const char * restrict format, ...);
int __cdecl main(void)
{
    int i;
    unsigned long sum = 0;
    unsigned char *pdata;    // pointer to data
    unsigned char data[200];    // safer stack place at end ?

    pdata = data;
    for (i = 0; i < 200; i++)
        *pdata++ = (unsigned char)(i % 300);

    pdata = data;
    for (i = 0; i < 200; i++)
        sum += *pdata++;
        //sum += (*data)++;

    printf("checksum %lu (correct 19900)\n", sum);
    return 0;
}
also with

Code Select Expand

sum += (*data)++;output

Code Select Expand

checksum 19900 (correct 19900)
EDIT: a simple check

Code Select Expand

int __cdecl printf(const char * restrict format, ...);
int __cdecl main(void)
{
    unsigned char *pdata; // pointer to data
    int i;
    unsigned char data[200];

    pdata = data;
    for (i = 0; i < 200; i++)
    {
        *pdata = (unsigned char)(i % 300);
        if (*pdata != i)
        {
            printf("\nerror: %u != %u\n", i, *pdata);
            break;
        }
        printf("%u ", *pdata);
        pdata++;
    }
    return 0;
}



Code Select Expand

int __cdecl printf(const char * restrict format, ...);
int __cdecl main(void)
{
    int i;
    unsigned long sum = 0;
    unsigned char *pdata;    // pointer to data
    unsigned char data[200];    // safer stack place at end ?

    pdata = data;
    for (i = 0; i < 200; i++)
        *pdata++ = (unsigned char)(i % 300);

    pdata = data;
    for (i = 0; i < 200; i++)
        {
        printf("%i ", data[i]);
        // sum += *pdata++;
         sum += (*data)++;
        }

    printf("checksum %lu (correct 19900)\n", sum);
    return 0;
}

/*
/O2 optimization
using "sum += *pdata++;"
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 checksum 4060 (correct 19900)
*/

/*
/O2 optimization
using "sum += (*data)++;"
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 checksum 19900 (correct 19900)
*/
 
/*
No /O2 optimization
using "sum += *pdata++;"
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 checksum 19900 (correct 19900)
*/

/*
No /O2 optimization
using "sum += (*data)++;"
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 checksum 19900 (correct 19900)
*/