rb tree: quiet gcc -Wmaybe-uninitialized

[rlibby]

Summary

The comment explains that the variable should never be used
uninitialized according to the algorithm, but the compiler can't be
expected to infer that.

There are many GCC -Wmaybe-unintialized warnings in the build, but this
one was particularly noisy due to being in a system header and due to
being triggered via multiple function inlining paths. This squelches
around 250 warning messages.

Test Plan

env CROSS_TOOLCHAIN=amd64-gcc13 make buildkernel
env CROSS_TOOLCHAIN=amd64-gcc13 make buildworld
kyua test

[kib]

Might be s/compiler/gcc/

[rlibby]

kib feedback

[dougm]

This is adding a needless instruction to every RB_INSERT. Can that be avoided somehow?

sys/sys/tree.h

542

With this change, it would be a NULL 'child', not an uninitialized one.

[rlibby]

@dougm, do you have a preference here? I'm happy to follow a suggestion or have you take it over.

I thought about this a little. I don't have an algorithm suggestion for convincing gcc that child will be initialized before use (except actually initializing it). I was not able to find a clang/gcc variable attribute or statement attribute to suppress the warning, except for #pragma warning disable directives, which I don't think we want.

I did come up with a way to lie to clang/gcc about it being initialized. I tried

/* (Mis)inform the compiler that an object has been initialized. */
#define _RB_FAKE_INIT(x)	do {					\
	__asm("" : "=r" (x));						\
} while (0)

...

	_RB_FAKE_INIT(child);						\

i.e. tell the compiler that we wrote the object, but actually do nothing.

Doing it this way avoids affecting code generation. Unfortunately apparently I have to use the "=r" constraint (must be in a register), more generic formulations I tried ("=rm", "=g", "=X") result in clang moving child to be a stack variable instead of a register variable -- i.e. actually results in worse codegen. It's a bit of a hack but it seems to work on amd64 at least. I am unsure if it is robust enough to be in a system header and I haven't tried the tinderbox build with it yet.

FWIW, the amd64 codegen for initializing child = NULL does not look bad to me. On amd64 both clang and gcc keep child in a register, and with the initialization change they zero it with a 2-byte xor instruction. For clang, the extra instruction only takes up nop padding space before the top of the loop. gcc doesn't have nop padding at the top of the loop but does adjust later padding.

[dougm]

It seems to me that a sufficiently smart compiler could use this to figure out that child would not be used uninitialized.

--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -540,6 +540,11 @@ name##_RB_INSERT_COLOR(struct name *head,                          \
        struct type *child, *child_up, *gpar;                           \
        __uintptr_t elmdir, sibdir;                                     \
                                                                        \
+       gpar = _RB_UP(parent, field);                                   \
+       if ((_RB_BITS(gpar) & _RB_LR) == _RB_LR) {                      \
+               __unreachable();                                        \
+               return (NULL);                                          \
+       }                                                               \
        do {                                                            \
                /* the rank of the tree rooted at elm grew */           \
                gpar = _RB_UP(parent, field);                           \

but I don't know how to do a gcc13 build test to verify that. Copying the first "TEST PLAN" just gives me a "not found" error message.

[rlibby]

In D52940#1210706, @dougm wrote:

It seems to me that a sufficiently smart compiler could use this to figure out that child would not be used uninitialized.

--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -540,6 +540,11 @@ name##_RB_INSERT_COLOR(struct name *head,                          \
        struct type *child, *child_up, *gpar;                           \
        __uintptr_t elmdir, sibdir;                                     \
                                                                        \
+       gpar = _RB_UP(parent, field);                                   \
+       if ((_RB_BITS(gpar) & _RB_LR) == _RB_LR) {                      \
+               __unreachable();                                        \
+               return (NULL);                                          \
+       }                                                               \
        do {                                                            \
                /* the rank of the tree rooted at elm grew */           \
                gpar = _RB_UP(parent, field);                           \

Apparently gcc is not a sufficiently smart compiler. I tried this patch and gcc still issues the warnings. I had been working with gcc13 but I tried gcc14 here too with no change.

I also tried restructuring the loop a bit and making the unreachable condition be (_RB_BITSUP(elm, field) & _RB_LR) != 0, but that didn't do the trick either: https://github.com/rlibby/freebsd/commit/29be8ed914bc6850ed6ead2937670c3f82286a76?diff=split&w=1

but I don't know how to do a gcc13 build test to verify that. Copying the first "TEST PLAN" just gives me a "not found" error message.

I think pkg install amd64-gcc13 (or 14) should be enough, or install devel/freebsd-gcc13 (or 14) from ports. I also omitted that I usually set e.g. MAKEOBJDIRPREFIX=/usr/obj/gcc14 to keep the build bits separated for the different toolchains.

[kib]

You might hide the workaround under some sort of ifdef gcc. It would be tricky, though, since this needs to happen inside the macro.