26 September 2006 - 21:55Neat tricks with C Arrays and Pointers

In C, arrays are really just pointers with some “syntactic sugar” around them to make access easier. When you use square brackets to access ar[2], ar is a pointer and the compiler translates ar[2] into *(ar + 2). The pointer arithmetic increments the pointer ar by two times the size of an element of ar. Then, it is dereferenced. This has an interesting consequence in that ar[2] == 2[ar]. Both of these allow you to access the the same location in memory and thus the same array member!

Why is this? Remember that a pointer is just an integer value that references a location in memory. So, when you write 2[ar] it translates to *(2 + ar). The address 2, plus the base address of the array. Which is the same as the base address of the array plus two. A really quick snippet of C can verify that this is true:

int main(int argc, char* argv[]) {
    char test[10] = "ABCDEFG";
    if (test[2] == 2[test]) {
        puts("whoa!n");
    }
    return 0;
}

If you compile and run this, it will print “whoa!” as expected, because C == C. But is that really the reason? I compiled this code with gcc -S test.c to get the results (note some code including the string initialization is omitted):

main:
.LFB2:
    pushq   %rbp
.LCFI0:
    movq    %rsp, %rbp
.LCFI1:
    subq    $32, %rsp
.LCFI2:
    movl    %edi, -20(%rbp)
    movq    %rsi, -32(%rbp)
    movq    .LC0(%rip), %rax
    movq    %rax, -16(%rbp)
    movw    $0, -8(%rbp)
    movl    $.LC1, %edi
    call    puts
    movl    $0, %eax
    leave
    ret

There are no compare or conditional branch instructions in there! That means that without any optimization options turned on GCC has generated code which will always execute the code within the if. This is even without the “constant folding” code which attempts to recognize and optimize constant sections of code. The compiler recognizes that *(ar + 2) = *(2 + r). If the C code is changed slightly so the value is assigned to a temporary variable before the comparison:

char tmp = 2[test];
if (test[2] == tmp) {
    puts("whoa!n");
}

main:
.LFB2:
    pushq   %rbp
.LCFI0:
    movq    %rsp, %rbp
.LCFI1:
    subq    $32, %rsp
.LCFI2:
    movl    %edi, -20(%rbp)
    movq    %rsi, -32(%rbp)
    movq    .LC0(%rip), %rax
    movq    %rax, -16(%rbp)
    movw    $0, -8(%rbp)
    movzbl  -14(%rbp), %eax    /*  Move element 2 to EAX */
    movb    %al, -1(%rbp)        /*  Move low order byte of EAX to temporary stack location */
    movzbl  -14(%rbp), %eax    /*  Move element 2 to EAX */
    cmpb    -1(%rbp), %al        /*  Compare temporary stack location and low order byte of EAX */
    jne .L2                             /*  Jump if not zero (equal) */
    movl    $.LC1, %edi
    call    puts
.L2:
    movl    $0, %eax
    leave
    ret

In this case you can clearly see the array element value being retrieved from the stack and placed into the temporary value (seen here as an offset off the base pointer) and then the identical address array element being retrieved into the EAX register, then compared with the temporary value. Interestingly enough, if I compile the same code with the GCC optimization option -O2 it yields a dramatically less complicated set of assembly instructions:

main:
.LFB24:
    subq    $8, %rsp      /* Allocate memory on the stack? */
.LCFI0:
    movl    $.LC0, %edi   /* Move address of "whoa!n" into %edi */
    call    puts          /* Call puts to output %edi string */
    xorl    %eax, %eax    /* Zero out %eax (return 0) */
    addq    $8, %rsp      /* Unwind the stack pointer */
    ret

Optimization really does improve the code! In this case GCC has once again figured out that the two array references are identical. But it has gone much farther this time and optimized away the temp variable, the comparison, and the array altogether! No memory at all was allocated for the array, and all references to it were gone from the assembly language code. Of course, the compiler is correct. The array has absolutely no purpose in our code given the foregone conclusion of the if block executing. You can even see that GCC has changed to using an xor instruction to zero out %eax (return register) instead of using a mov instruction - which is probably faster (note that anything xor’d with itself is always 0). Optimized code really does make a difference.

I don’t know why the compiler has created the two instructions which manipulate the stack pointer. After some thought, the 8 byte allocation would correspond to a pointer to the string literal at label .LC0. I’m not as familiar with how the assembler treats strings. Obviously 8 bytes does not correspond to the entire string, which was previously confusing me. If you know more, please drop a comment. Thanks to Stu for pointing out the obfuscated array trick.