clang and over-done inlining of functions

joelkp

In many ways, I guess clang is reasonable and roughly as good as GCC. But one thing I've begun to find fairly annoying is the over-done inlining of functions with -O2 or above.

In a fairly simplistic recursive-descent parser I've written, I ended up adding the noinline attribute 5 times to functions to prevent the size of the program from bumping up another 4 KB, usually after simplifying the code a little which brought a function under some threshold causing it to be inlined. The first instance of this was with the warning function in the parser. (A macro used in the parser becoming slightly simpler caused the program size to increase, and investigating the mystery revealed that the warning function in the parser had now become inlined because its size had slightly decreased.)

Now I solve that by compiling the main parser file with -Os, but whenever -O2 or -O3 are used for a file, noinline attributes can be needed once in a while to prevent clang from doing something silly. It doesn't matter either way with GCC, which is more conservative about inlining of functions. Usually nothing of significance happens with GCC when the noinline attribute was added to keep clang from being too gung-ho on inlining.

What prompted this post is when I tonight had to add noinline to prevent a slow-down in array-filling code in a file compiled with -O3. But that's part 3 of 3 of recent changes. (Current version of ramp.c has all the changes.)

First, after speeding up the program when built with GCC by compiling some files with -O3, I found that it became slower instead with clang because of one file, that one. This was solved by changing the fill-functions to handle pointers and indexes more simply and moving the use a value-multiplying array down into each of them. Then -O3 made for a speed-up with clang, too, my current test for the program running roughly 10% faster (the value-filling stuff matters a lot) on an old laptop with i386 OpenBSD and its standard clang 10.0.1, compared to before using -O3.

Second, another much smaller change added a NULL-check near a call to one fill-with-value function which NULL-checks a pointer copied from the same pointer. The presence of both NULL checks caused clang to not only inline that function, but also in turn the loss of roughly half of the 10% speed-up.

Third, adding a noinline to the function which was called restored the performance to the same as before the extra NULL check had been added. (In cases like this, it's great when the compiler optimizes the loops inside loop-containing functions as aggressively as possible, but not when it inlines those functions themselves. I don't know exactly what ended up happening before the noinline was added, but perhaps it hurt efficient cache use in some way.)

(Edit: That slow-down does not happen on the amd64 system I have with clang. It may be something other than too much inlining which however happens along with that on the i386 system.)

Well, that's my experience so far and with the versions of the compilers used with modern *BSD (and the modern GCC on Linux installations I've used) the past few years. (Before that, too little knowledge and experience with clang to say much of anything.) I think they must have set the default inline threshold too liberally, compared to what GCC does, years and major versions ago.

rvp

joelkp If all your compiler is doing in the name of "optimization" is inlining a few functions behind your back, then you don't have any problems. Consider, instead, this case of aggressive compiler optimization which bit me some time back. The compiler in question is GCC (version doesn't matter--as you'll see presently).

There was this network-packet processing code I'd written--standard stuff: read an ethernet packet from the card, do some munging on it, pass it up to the main program. I made some trivial change, and then the program started crashing on some inputs. After a day or two of hair-pulling, I discovered that my code was OK (arguably--you'll see why further on), and that this was a case of code improvement by the compiler aka. optimization. Here's a test code which demonstrates what was going on:

$ cat -n t.c
     1	#include <stdio.h>
     2	#include <string.h>
     3	#include <stdlib.h>
     4	
     5	int
     6	main(int argc, char* argv[])
     7	{
     8		enum { N = 32 };
     9		char buf[N];
    10		char *s = NULL;	/* Initialize */
    11		size_t n = 0;	/*     "      */
    12	
    13		if (argc > 1) {
    14			s = argv[1];
    15			if ((n = strlen(s)) >= N) {
    16				fprintf(stderr, "%s: arg too long\n", *argv);
    17				exit(EXIT_FAILURE);
    18			}
    19		}
    20	
    21		memmove(buf, s, n);
    22		buf[n] = 0;
    23	
    24		if (s == NULL)
    25			printf("`s' is null--compiler OK.\n");
    26		else		/* GCC says s is not NULL when it is! */
    27			printf("compiler says `s' is not NULL when it is!\n");
    28	
    29		return 0;
    30	}
$

Notice that if no argument is passed to the program, s is not touched. Let's run it:

$ gcc -O -o t t.c
$ ./t
compiler says `s' is not NULL when it is!
$

Huh? I mean: WTF!?
Try w/o optimizatons:

$ gcc -o t t.c
$ ./t
`s' is null--compiler OK.
$

That worked. But, what's going on here? Compiling with -fsanitize=undefined gives a clue (in the old days, before ubiquitous static analysis, sanitizers and such-like, we used to look at the assembly output):

$ gcc -O -fsanitize=undefined -o t t.c
$ ./t
t.c:21:2: runtime error: null pointer passed as argument 2, which is declared to never be null
`s' is null--compiler OK.
$

Notice how program behaviour has changed. Line 21 is the memmove. Check declaration of memmove:

$ fgrep -A1 memmove /usr/include/string.h
extern void *memmove (void *__dest, const void *__src, size_t __n)
     __THROW __nonnull ((1, 2));
$

Ahh! memmove is annotated. It says: args. 1 and 2 to the function can be assumed to be nonnull.
So, what gcc has done is look at that annotation and gone: Oh! I see you've called memmove, so I can therefore assume that s is not-NULL--even if n is 0 and memmove hasn't done anything--and optimize the other case out completely (and throw away your initialization statement too).

This is the kind of (infamous) GCC "optimization" that led to a root exploit in the Linux kernel a few years ago.

What about NetBSD, where memmove (and other similar functions) are not annotated (at least, I couldn't find it)? We'll, GCC still optimizes away my useful code.

What gets my goat is that other people have also stumbled on this GCC issue. And the GCC folks won't fix it because: well... standards, annotations, droit du compiler, whatever... Even the latest GCC, 10.2.0, does this.

clang, BTW, does the correct thing here. Try it.

20-100

The purpose of in-lining functions is to take advantage of the processor's optimization mechanisms. The less branch instructions, the more efficient predictive execution and instruction caching.

Today's computers have plenty of memory and run applications that are much more computing-intensive than in the past, so processors and compilers are designed for speed. Nowadays, only a few embedded devices are strongly memory constrained, so we can say the need to optimize for size has disappeared at 99.99%.

Very clearly, trying and save 4 kilobytes is crucial on a Z80 but makes no sense on an x86 or amd64 machine.

This means that if you begin defeating the compiler's algorithms by adding noinline here and there, expect unpredictable consequences. Don't forget that optimizations built into processors and compilers are based on statistics, so they are only efficient on "large" amounts of code executed "intensively", whereas a developer can only analyze a few lines at a time.

Lastly, if you're in a use case where you really need to control the code the compiler generates, it may be a better idea to code that part of your application in assembly language instead of C or C++. It would avoid you the unpleasant surprise to see the object code change when using a different compiler, or a newer version of the same one.

joelkp

20-100
You're plainly right that there's no practical need to save 4KB here and there on x86 and amd64. How people relate to more and less bloat in programs is in very large part a matter of aesthetics rather than anything practical.

My first post conflated two separate problems, by the way. The first is what I've found a minor annoyance for a few years: clang inlining some functions uselessly when gcc doesn't with noticeable size bloat as a result. It turns out that there's an actual single threshold parameter for how llvm behaves where the default allows a fairly large inlining "cost", and statistically it probably makes clang better in benchmarks. Personally, I just think that value is a bit too high for -O2 (but it goes hand in hand with the general trend of the "inline" keyword mattering less and less). Others want it cranked even higher because it makes their programs faster.

The second problem, which I falsely believed an instance of the first at first, is some kind of x86-specific issue, as I noted in the edited-in note. The function which was inlined is not actually a valid example of the first problem, the "inlining cost" is much smaller, the size bloat likewise, and it turns out gcc also inlined it. It just triggered a hasty reaction in me, because it was yet another clang-specific inlining thing happening where this time performance instead of size took a hit when I set out to optimize performance.

I think using noinline in particular will generally have an effect similar to moving a function to a separate compilation unit (but a bit less severe). For functions where the performance of the call simply doesn't matter, like something which prints errors, it should be harmless for how the compiler optimizes the rest of the code.

Do I care enough to actually go the route of using assembly for this project for complete control? No, not at present. I'm currently not nearly that deep in understanding of how to make things perform. Actually, currently, I appreciate how well modern compilers made that array filling code work when -O3 combined with the use of the restrict keyword on 64-bit systems. Filling float arrays became so much faster that attempts to make the program faster by avoiding it when only a single value is needed paled in comparison.

joelkp

rvp
That's spooky in how something expected to be an ordinary function suddenly changes the meaning of code in which it's referred to.

It seems the reason it happens regardless of annotations in the library used is that the gcc built-in version also has the annotation. I just tested this:

Before commenting out #include <string.h> on my Linux system:

$ cc -O t.c
$ ./a.out                                                                      
compiler says `s' is not NULL when it is!
$ cc -O -fno-builtin t.c                                                       
$ ./a.out                                                                      
compiler says `s' is not NULL when it is!

After commenting out string.h:

$ cc -O t.c                                                                    
t.c: In function 'main':
t.c:15:12: warning: implicit declaration of function 'strlen' [-Wimplicit-function-declaration]
   15 |   if ((n = strlen(s)) >= N) {
      |            ^~~~~~
t.c:15:12: warning: incompatible implicit declaration of built-in function 'strlen'
t.c:4:1: note: include '<string.h>' or provide a declaration of 'strlen'
    3 | #include <stdlib.h>
  +++ |+#include <string.h>
    4 | 
t.c:21:2: warning: implicit declaration of function 'memmove' [-Wimplicit-function-declaration]
   21 |  memmove(buf, s, n);
      |  ^~~~~~~
t.c:21:2: warning: incompatible implicit declaration of built-in function 'memmove'
t.c:21:2: note: include '<string.h>' or provide a declaration of 'memmove'
$ ./a.out                                                                      
compiler says `s' is not NULL when it is!
$ cc -O -fno-builtin t.c                                                       
t.c: In function 'main':
t.c:15:12: warning: implicit declaration of function 'strlen' [-Wimplicit-function-declaration]
   15 |   if ((n = strlen(s)) >= N) {
      |            ^~~~~~
t.c:4:1: note: 'strlen' is defined in header '<string.h>'; did you forget to '#include <string.h>'?
    3 | #include <stdlib.h>
  +++ |+#include <string.h>
    4 | 
t.c:21:2: warning: implicit declaration of function 'memmove' [-Wimplicit-function-declaration]
   21 |  memmove(buf, s, n);
      |  ^~~~~~~
t.c:21:2: note: 'memmove' is defined in header '<string.h>'; did you forget to #include <string.h>'?
$ ./a.out                                                                      
`s' is null--compiler OK.

So it appears you can get rid of it by both not using a library declaration with the annotation and building with -fno-builtin.

joelkp

joelkp
Of course, it would be ugly to take that approach (replacing library declarations and disabling built-ins for a specific compiler) in portable code. I don't mean to say it would be a nice fix.

For now, clang may avoid that kind of thing, but I searched a bit and it looks like this could change in future clang versions. Current documentation: "Note that the nonnull attribute indicates that passing null to a non-null parameter is undefined behavior, which the optimizer may take advantage of to, e.g., remove null checks." So they note they may do what gcc already does.

rvp

joelkp I don't mean to say it would be a nice fix.

The way I fixed my code was to add an extra check for a 0-sized buffer after processing.

joelkp "Note that the nonnull attribute indicates that passing null to a non-null parameter is undefined behavior, which the optimizer may take advantage of to, e.g., remove null checks." So they note they may do what gcc already does.

That's exactly the rationale the GCC folks have used to defend their "optimization": OK, so, I have to be a C language-lawyer and now have to go to night-school to understand your compiler-specific extensions as well? Yeesh!

joelkp That's spooky in how something expected to be an ordinary function suddenly changes the meaning of code in which it's referred to.

That's just it, mate. You try to write as portable and standards-safe a code as possible, then along comes some other bit of code which relies on extensions, and it throws a spanner in the whole works.

joelkp

rvp
I figured out how this works; there's related more general features in both compilers ("assume", "unreachable", etc.). The optimizer is basically given a logical formula when the attribute is used. It is then allowed to remove any code specific to when the opposite is true. To ensure nothing can be removed, make sure the optimizer ends up with a tautology, always true, after looking at the surrounding code, so that the opposite is always false.

Going back to the example you posted, where s can be NULL but buf can not, the solution is to ensure memmove is guarded with a NULL-check for s:

if (s != NULL) memmove(buf, s, n);

Then the problem goes away. Logically, the optimizer ends up dealing with: "if s is not null, then s is not null", a tautology. The opposite goes from "s is null" to simply "false".

If such a check is forgotten in any place where it's needed, the feature shifts compiler semantics towards: "I see you left out that null check... Muhahahaha!" (More recent gcc versions than I now use seem to move in the direction of being more helpful, by actually providing warnings: -Wnonnull.)

To put it simply, each time there's a nonnull attribute to a called function, and your argument could be NULL, ensuring the call is wrapped in defensive NULL-checking avoids giving the optimizer room to rip code out. (The paranoid, future-proof solution is to have a check whenever it's not explicitly documented that a library function allows a pointer argument to be NULL and you write code where NULL values are handled.)

rvp

joelkp Going back to the example you posted, where s can be NULL but buf can not, the solution is to ensure memmove is guarded with a NULL-check for s:

if (s != NULL) memmove(buf, s, n);

You know what the problem with that is, right? Sometimes such checks themselves are optimized away. This is the kernel exploit I mentioned earlier: Fun with NULL pointers, part 1

joelkp To put it simply, each time there's a nonnull attribute to a called function, and your argument could be NULL, ensuring the call is wrapped in defensive NULL-checking avoids giving the optimizer room to rip code out. (The paranoid, future-proof solution is to have a check whenever it's not explicitly documented that a library function allows a pointer argument to be NULL and you write code where NULL values are handled.)

Right. But, this adds redundancy to the code, is wasteful, and is ugly to boot. Consider a simple implementation of memcpy:

void
mcpy(char* s, const char* t, size_t n)
{
        while (n-- > 0)
                *t++ = *s++;
}

The code will work for all valid arguments. And as long as n holds the correct size of the buffers (even 0), both s and t can be NULL. Now, I'm being asked to code it in this way just to work around the compiler:

void
mcpy(char* s, const char* t, size_t n)
{
        if (s == NULL || t == NULL || n == 0)
                return;
        while (n-- > 0)
                *t++ = *s++;
}

I don't mind adding necessary checks, but, this kind of a check is just a waste. The code works fine without it. My original code was the same. If the buffer I was working on ended up with a size of 0, the control flow would just pass through without doing anything. But, then the compiler changed the code path underneath me.

And what about systems like NetBSD, where memcpy is not annotated like this, but, the compiler still feels free to change the code flow in the name of optimization? Mind you, I'm not against this kind of optimization, just, you know, keep it out of the system libraries.

joelkp

rvp You know what the problem with that is, right? Sometimes such checks themselves are optimized away. This is the kernel exploit I mentioned earlier: Fun with NULL pointers, part 1

As it relates to "nonnull", that article makes clear that dereferencing a pointer is basically treated in the same way as passing it as a nonnull argument.

If you consider a chain of nonnull uses of a pointer, you can think of each place where a check may crucially be present or absent as a node in a head-and-tail list moved down. Node after node, if the check is there, the head will be kept; but otherwise the tail is removed along with the head. In the function in the article, checking for a pointer became "headless" when a pointer-dereferencing was added before the first check, and that's why the check was removed.

(Anyway, here's what seems like the solution if you want to ensure gcc never deletes NULL checks: -fno-delete-null-pointer-checks. Adding that to compilation options is also another fix for the original example code you posted. That option was mentioned in the follow-up article to the article you linked to, as something the Linux project ended up using, given the peculiarities of kernels (where NULL can actually be a valid address, unlike normal code).)

rvp Now, I'm being asked to code it in this way just to work around the compiler:

Actually, it should kind of be the opposite. The onus is all on the caller to do the checking, exactly like the onus is on the pointer user to ensure it's not NULL before dereferencing it, but without warning messages, people are likely to unknowingly keep using code with what's now formally bugs in it.

If/when warnings are actually produced - gcc used to lack warnings for these nonnull-issues due to some kind of technical debt for a very long time, and versions without warnings will be in wide use for years to come - people should be alerted to having to change their code and add checks to avoid ominous undefined behavior.

rvp And what about systems like NetBSD, where memcpy is not annotated like this, but, the compiler still feels free to change the code flow in the name of optimization? Mind you, I'm not against this kind of optimization, just, you know, keep it out of the system libraries.

That's because the annotation also exists in gcc's built-in versions of the functions. Which makes sense if the built-ins are in sync with the standard libc, but not as much if not. I think that may be feasible to change as part of tweaking the default gcc build which comes with NetBSD, changing such details to more closely match NetBSD libc. That's far beyond my detail-knowledge, but the people wrestling with gcc versions and updates in NetBSD may have the know-how (if they would turn out motivated to work on such a change).

rvp

joelkp That's because the annotation also exists in gcc's built-in versions of the functions.

~~There is no annotation for gcc's builtins~~, the compiler just inlines the appropriate code ~~(so no annotation is needed)~~(the annotation, I think, are picked up from .../gcc/builtins.def). Using -fno-builtin does the trick on NetBSD (unlike Linux as in your example), but, then everything is undone if you add -D_FORTIFY_SOURCE=N because then another set of builtins are used. This what I dislike about this mess: playing hunt the correct option against the compiler.

BTW, look at the assembly for -O. It's instructive. Compare it to -O -fno-builtin on NetBSD. For the first case, gcc completely elides one of the code paths--as you would expect it to.