Unexpected optimization of strlen when aliasing 2-d array

Question

Here is my code:

#include <string.h>
#include <stdio.h>

typedef char BUF[8];

typedef struct
{
    BUF b[23];
} S;

S s;

int main()
{
    int n;

    memcpy(&s, "1234567812345678", 17);

    n = strlen((char *)&s.b) / sizeof(BUF);
    printf("%d\n", n);

    n = strlen((char *)&s) / sizeof(BUF);
    printf("%d\n", n);
}

Using gcc 8.3.0 or 8.2.1 with any optimization level except -O0, this outputs 0 2 when I was expecting 2 2. The compiler decided that the strlen is bounded to b[0] and therefore can never equal or exceed the value being divided by.

Is this a bug in my code or a bug in the compiler?

This isn't spelled out in the standard clearly, but I thought the mainstream interpretation of pointer provenance was that for any object X, the code (char *)&X should generate a pointer that can iterate over the whole of X -- this concept should hold even if X happens to have sub-arrays as internal structure.

(Bonus question, is there a gcc flag to turn off this specific optimization?)

Answer 1

I checked this and it reproduced with -O1 on gcc 8.3, so I just opened list of gcc optimization flags here and started experimenting with them one by one. It turned out that disabling only sparse conditional constant propagation with -fno-tree-ccp made the problem disappear (oh luck, I planned to test couples of flags if testing one by one gives no result).

Then I switched to -O2 but did not erase -fno-tree-ccp flag. It reproduced again. I said "OK" and just started testing additional -O2 flags. It again appeared that disabling single Value Range Propagation additionaly leads to intended 2 2 output. I then erased that first -fno-tree-ccp flag, but it started reproducing again. So for -O2 you can specify -O2 -fno-tree-ccp -fno-tree-vrp to make yor program work as expected.

I did not erase these flags, but switched to -O3 then. Problem did not reproduced.

So both of these two optimization techniques in gcc 8.3 lead to such a strange behaviour (maybe they use something common internally):

• Sparse conditional constant propagation on trees
• Value Range Propagation on trees

I'm not pro in all that stuff to explain what and why is happening there, maybe someone else could explain. But for sure you can specify -fno-tree-ccp -fno-tree-vrp flags to disable these optimizaton techniques for your code to work as expected.

“The harder I work, the luckier I get.” – Samuel Goldwyn

Edit

As @KamilCuk noted in question comments, -fno-builtin-strlen leads to inteded behaviour too, so most probably there is a compiler bug in combination of built-in strlen and another optimization, that is intended to cut off dead code, statically determine possible expression values and propagate constants through a program. I thought compiler most probably mistakenly considered something, that determines string length in its strlen implementation (maybe in combination with integer division and/or two-dimensional arrays) as dead code and cut it off or calculated it as 0 at compile time. So I decided to play a little bit with the code to check the theories and eliminate other possible "participants" of the bug. I came to this minimal example of the behaviour, which confirmed my thoughts:

int main()
{
    // note that "7" - inner arrays size, you can put any other number here
    char b[23][7]; // local variable, no structs, no typedefs
    memcpy(&b[0][0], "12345678123456781234", 21);

    printf("%d\n", strlen(&b[0][0]) / 8); // greater than that "7" !!!
    printf("%d\n", strlen(&b[0][0]) / 7);
    printf("%d\n", strlen(&b[0][0]) / 6); // less than that "7" !!!
    printf("%d\n", strlen(&b[0][0])); // without division
}

0

0

3

20

I think we can consider this a bug in gcc.

I think -fno-builtin-strlen is better solution for the problem, as it works for all optimization levels alone and built-in strlen seems to be less powerful optimization technique, especially if your program doesn't use strlen() a lot. Still -fno-tree-ccp -fno-tree-vrp is also an option.

Answer 2

The way you defined the struct confused me at first because I don't think I've ever tried creating a type of an array. Doing it that way can be dangerous too because the if someone tried to pass it in to a function, they might think they're passing by value but would actually pass by reference. Regardless of style, if I needed to create a type like that, I would do something like:

//typedef char BUF[8];

//do it this way instead
typedef struct
{
    char x[8];
} BUF;

typedef struct
{
    BUF b[23];
} S;

If I define it that way, then it returns the expected value either way. See it here.

Answer 3

There are some issues that I can see and they can be affected by how the compiler decides to layout memory.

    n = strlen((char *)&s.b) / sizeof(BUF);
    printf("%d\n", n);

In the above code s.b is a 23 entry array of an array of 8 characters. When you refer to just s.b you are getting the address of the first entry in the 23 byte array (and the first byte in the 8 character array). When the code says &s.b, this is asking for the address of the address of the array. Under the covers, the compiler is more than likely generating some local storage, storing the address of the array in there and supplying the address of the local storage to strlen.

You have 2 possible solutions. They are:

    n = strlen((char *)s.b) / sizeof(BUF);
    printf("%d\n", n);

or

    n = strlen((char *)&s.b[0]) / sizeof(BUF);
    printf("%d\n", n);

I also tried to run your program and demonstrate the issue, but both clang and the version of gcc I have with any -O options still worked as you expected. For what it's worth, I'm running clang version 9.0.0-2 and gcc version 9.2.1 on x86_64-pc-linux-gnu).

Answer 4

I think this is may be a bug in gcc. I found a couple solutions, but the easiest seems to be to create a proxy function with the noinline attribute. Then you're not losing out on any other optimizations, just the ones related to strlen.

int  __attribute__ ((noinline)) _strlen(char *x) { return strlen(x); }
#define strlen _strlen

int main(){
    int n;

    memcpy(&s, "1234567812345678", 17);
    n = strlen((char *)&s.b) / sizeof(BUF);
    printf("%d\n", n);

    n = strlen((char *)&s) / sizeof(BUF);
    printf("%d\n", n);
}

You can see the output in the Compiler Explorer. https://godbolt.org/z/U2L9us

Answer 5

There are errors in the code.

 memcpy(&s, "1234567812345678", 17);

for example, is risky, even though s starts with b should be:

 memcpy(&s.b, "1234567812345678", 17);

The second strlen() has also errors

n = strlen((char *)&s) / sizeof(BUF);

for example, should be:

n = strlen((char *)&s.b) / sizeof(BUF);

The string s.b, if copied correctly, should be 17 letters long. Not sure how structs are stored in memory, if they are aligned. Have you checked that s.b actually contains the 17 characters copied?

So a strlen(s.b) should show 17

The printf only shows integer numbers, as %d is integer, and the variable n is declared to be an integer. sizeof(BUF), should be 8

So a 17 divided by 8 (17/8) should print 2 as n is declared as integer. As memcpy was used to copy data to s and not to s.b, I would guess that as this has to do with memory alignments; assuming it is a 64 bit computer, than there can be 8 characters on one memory address.

For instance, lets assume that someone has called a malloc(1), than the next "free space" are not aligned...

The second strlen call, shows the correct number, as the string copy was done to the s struct instead of to s.b