Loop unrolling confuses __builtin_dynamic_object_size() and __builtin_constant_p()

[kees]

This is from ClangBuiltLinux/linux#2076 where commit 2d1e8a0 seems to have exposed some recent Linux kernel code to the loop unroller (though oddly only on ARM). Attempting to extract a minimal reproducer has been a challenge, but it appears that something about loop unrolling confuses __builtin_constant_p(). Loop variables assigned from __builtin_dynamic_object_size() appear constant, whereas if it is left in a macro, they correctly stay dynamic.

It seems that a noreturn branch is also be required to trigger this. Anything that disables the loop unrolling fixes the problem (via #pragma or via changes in loop size via NUM_ADDRS). Bringing the external loop constraint explicitly down into the inner loop (j < NUM_ADDRS) also fixes it.

I'm not sure what to do next to narrow this down further.

// clang -Wall -O2 -c repro.c -o repro.o
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#define __compiletime_warning(msg)      __attribute__((__warning__(msg)))
#define __noreturn                      __attribute__((__noreturn__))

extern void variable_calc_constant(size_t) __compiletime_warning("variable calculation is constant");
extern void macro_calc_constant(size_t) __compiletime_warning("macro calculation is constant");
extern void freakout(void) __noreturn;
extern int check(int);

extern int unknown;

// must be less than 10 (loop unrolling limit?)
#define NUM_ADDRS 4

struct inner {
        unsigned char addr[2]; // must be greater than 1 to show warnings in unroll
};

struct middle {
        struct inner bytes;
};

struct outer {
        struct middle array[NUM_ADDRS];
};

void repro(void) {
        struct outer *outer;
        struct middle *middle;
        int i, c;

        outer = malloc(sizeof(*outer));
        middle = outer->array;
        for (i = 0, c = 0; i < unknown && c < NUM_ADDRS; i++) {
                struct inner addr = { };
                int j;

                if (check(i))
                        continue;

//#pragma clang loop unroll(disable)
                for (j = 0; j < c /*&& j < NUM_ADDRS*/; j++) {
                        const size_t v_size = __builtin_dynamic_object_size(&middle[j].bytes, 0);
                        #define      m_size   __builtin_dynamic_object_size(&middle[j].bytes, 0)

                        if (__builtin_constant_p(v_size))
                                variable_calc_constant(v_size);
                        if (__builtin_constant_p(m_size))
                                macro_calc_constant(m_size);

                        if (m_size < sizeof(addr))
                                freakout();

                        if (__builtin_memcmp(&middle[j].bytes, &addr, sizeof(addr)) == 0)
                                break;
                }
                if (j == c)
                        c++;
        }
}

Produces (on x86_64 host, FWIW):

$ clang -Wall -O2 -c repro.c -o repro.o
repro.c:53:5: warning: call to 'variable_calc_constant' declared with 'warning' attribute: variable calculation is constant [-Wattribute-warning]
   53 |                                 variable_calc_constant();
      |                                 ^
repro.c:53:5: warning: call to 'variable_calc_constant' declared with 'warning' attribute: variable calculation is constant [-Wattribute-warning]
repro.c:53:5: warning: call to 'variable_calc_constant' declared with 'warning' attribute: variable calculation is constant [-Wattribute-warning]
repro.c:53:5: warning: call to 'variable_calc_constant' declared with 'warning' attribute: variable calculation is constant [-Wattribute-warning]
repro.c:53:5: warning: call to 'variable_calc_constant' declared with 'warning' attribute: variable calculation is constant [-Wattribute-warning]
5 warnings generated.

Without loop unrolling, this does not emit warnings. The macro-based uses of __builtin_dynamic_object_size() aren't resolved (which itself seems to be a bug), but the variable based ones are. Specifically, when __builtin_dynamic_object_size() is being determined at compile time as part of the loop unrolling, it cannot reach 0 -- the loop unroller is exceeding the maximum loop counter and producing an iteration beyond the bounds of the array. This can be seen in the fifth (impossible) call in the binary output:

        xor     edi, edi
        call    variable_calc_constant@PLT

https://godbolt.org/z/eT5KdTxbv

[efriedma-quic]

For macro_calc_constant, the frontend folds it away; not sure what exactly the interaction is there, but I suspect the constant evaluator is being overly aggressive. I don't think it's relevant to the rest of the issue.

Anyway, it looks like we're computing the range of "c" imprecisely due to SCEV limitations, which leads to extra unrolling. And the unrolling itself leads to all the other symptoms you're seeing.

This is one of the reasons I don't like __compiletime_warning: it turns missed optimizations into build breakage.

[kees]

I think the macro vanishes because __builtin_constant_p() immediately (and not too unreasonably) decides __builtin_dynamic_object_size() can't be constant.

Yeah, the "extra loop" is for sure what is tripping the compile-time size check. But Linux's FORTIFY has no way to know it's being used in part of a dangling loop unrolling -- it just sees that __bdos == 0 is a compile-time constant state and freaks out.

Thanks for finding the specific area this has gone weird: the SCEV implementation. Is there any chance this can be improved, or should we just keep an eye out for this state in the future? (I've proposed a work-around in Linux for this particular situation.)

[efriedma-quic]

The relevant bit of SCEV output (-passes="print<scalar-evolution>" from just before the unroller runs):

Loop %for.body5: constant max backedge-taken count is i64 4
Loop %for.body5: symbolic max backedge-taken count is (4 umin (-1 + (sext i32 %c.050 to i64))<nsw>)
  symbolic max exit count for if.end7: i64 4
  symbolic max exit count for if.end13: ***COULDNOTCOMPUTE***
  symbolic max exit count for for.inc: (-1 + (sext i32 %c.050 to i64))<nsw>

The "4" comes from the m_size < sizeof(addr): on that iteration, the loop exits to call freakout(). The other expression is the actual trip count of the loop, i.e. "c". It should be possible to figure out, in this particular case, that "c-1" must be less than 4; SCEV currently doesn't try very hard.

---

But really, I'm reluctant to chase this sort of thing; no matter how hard we try, there's always going to be some optimization that doesn't work the way a Linux kernel developer expects. And because of the way the "warning" attribute works, "doesn't work the way a Linux kernel developer expects" means "breaks the build".

[kees]

I appreciate your taking the time to dig into this! Having the examples of where in the code base it's happening and how to reach their debug diagnostics helps me narrow my search. :)

Yeah, there is certainly a tension between the expectation in Linux that "things that can be determined at compile time" are fully deterministic. When something like the loop unroller creates that extra loop, leaving the various associated values as compile-time constant ends up confusing the logic that expected them to be correct. I mean, I get how it happens, but it's too bad there's no way to mark things in the extra loop as "I dunno if we can actually reach this" instead of "we absolutely will reach this".

Having some way to check if an evaluation is happening in an "maybe not perfect" state would be good too. For example, in this case, the FORTIFY routine is just saying "Can I know if this will always run out of space?". If it's evaluated once (no unrolling) the size isn't compile-time knowable, so it gives up and uses run-time checking. After unrolling, it gets analyzed 5 times and each are compile-time knowable, but the last is out of space. If FORTIFY could ask "have I been converted from non-const to const?" then it could short-circuit the check and rely on the run-time checking. I dunno how feasible this is, though -- a simple "did I get optimized?" isn't useful.