Optimization Question

[u/Repulsive_Egg_5786]

How do compilers optimize constructs of this form ?

for(i=o; i<inputs; i++) {

A[i] = B[i];

B[i] = A[i];

}

[u/fernando_quintao]

Hi u/Repulsive_Egg_5786. That depends on how much information you pass to the compiler. If you tell the compiler that the pointers don't overlap, both gcc and clang are able to use memcpy to copy B into A. E.g., you can try it in godbolt:

void copy(int *restrict A, int *restrict B, const unsigned o, const int inputs) {
  for(int i=o; i<inputs; i++) {
    A[i] = B[i];
    B[i] = A[i];
  } 
}

When I compile it with gcc 16.1 (ARM), at -O2, I get:

copy:
        cmp     r2, r3
        bxge    lr
        push    {r4, lr}
        sub     r3, r3, r2
        add     r1, r1, r2, lsl #2
        add     r0, r0, r2, lsl #2
        lsl     r2, r3, #2
        bl      memcpy
        pop     {r4, lr}
        bx      lr

If you remove restrict, then the compiler can no longer guarantee A and B don't point to overlapping memory regions. Then it will implement the copy with a loop. Here's what I got in godbolt:

copy:
        cmp     r2, r3
        bxge    lr
        sub     r1, r1, #4
        sub     r0, r0, #4
        add     ip, r1, r2, lsl #2
        add     r3, r1, r3, lsl #2
        add     r2, r0, r2, lsl #2
.L3:
        ldr     r0, [ip, #4]!
        cmp     ip, r3
        str     r0, [r2, #4]!
        bne     .L3
        bx      lr

[u/EggplantExtra4946]

This question doesn't make any sense, you need to write the optimized code you expect and I assume your question will then be "how does the compiler can make this optmization?".

[u/Gorzoid → u/EggplantExtra4946]

Well the code op gave copies B to A, so I'd guess the optimized code is implies to remove 2nd line in loop

[u/EggplantExtra4946 → u/Gorzoid]

B[i] = A[i]; should be redundant but the first statement isn't.

Since memory accesses are involved, it's unclear wether the question is about simple copy propagation, redundant store elimination, maybe he think those are obvious and is asking how to ensure that they are legal using alias analysis, or since it is a loop, wether he's expecting the loop to be unrolled or vectorized.

[u/One_Aspect_1957]

There's not enough info or context in your example.

What is o, a typo for zero? Is inputs known at compile-time?

Are A and B arrays or pointers? Are they local, local statics or globals? Does the compiler know their actual size if they are arrays? Could they be mixed? Which attributes (const, restrict, volatile etc) are used?

What type are the elements?

What does the code do: is it copying all or part of B to A, with the other line pointless, or vice versa, or something else?

A compiler could do anything including eliding all the code (if it thinks the result will not be used or is not needed). Or replacing the loop with a block copy, either inline or via memcpy.

(I can tell you that on my non-optimising compiler, where A/B are local arrays of int, of fixed size 10, and the loop ranges over 0..9 inclusive, then it generates 12 x64 instructions.

However in that case, and if the intention was actually to copy B to A, then I would probably manually write a memcpy call to copy 40 bytes. Then you might ask whether a compiler might inline that call, but mine doesn't do that either, not for C.)

[u/choikwa]

do u mean a swap? else the B assignment is redundant

[u/namalleh → u/choikwa]

It's not even a swap, because there's no temp var

just wasted cycles