For example you have a function sort(int* numbers, size_t count) with a bubblesort implementation and a C compiler recognizes this pattern. Would the compiler be allowed to change it to another example? Like Quicksort.
Another example would be adding all numbers from 0 to n, where the compiler could replace the for loop with (n*(n-1))/2.
The word algorithm here might be a little strong, but Yes, the default settings of modern compilers generally provide as much freedom to change your code as the current compiler technology allows, but at the same time just about every modern compiler written provides the application programmer some control over what the compiler can and cannot do.
Given the default settings, modern compilers have the ability to use replacement constructs for simple algorithms and to some extent, can even be directed how they choose to replace them based on programmer settable preferences. Compilers provide many variations and levels of optimization options, most commonly related to speed, and/or memory usage. But the scope of what is changed is limited to simpler constructs that can be made more efficient, or totally ignored, depending on the construct.
In your specific example, of a function with the sort algorithm, the algorithm itself would not be replaced, but some of the component sections within it could be optimized, depending on how they are coded.
Conversely, you can also set current compilers to leave your code just as you wrote it. For example in newer versions of GCC (since v4.4) you can completely disable optimizations using these pragma surrounds:
#pragma GCC push_options
#pragma GCC optimize ("O0")
normal C code
#pragma GCC pop_options
If the called function is within the optimization domain, which there are ways to do even if the function is another file then yes. In the same way that having the called function in the same file. But that doesn't mean that the compiler assumes based on the name of a function what the called code really is, you can easily make your own C library and link it in and have the named functions (qsort for example) do whatever you want. So this is undesireable, yet the tools do it:
#include <stdio.h>
void fun ( void )
{
printf("0");
}
Disassembly of section .text:
00000000 <fun>:
0: e3a00030 mov r0, #48 ; 0x30
4: eafffffe b 0 <putchar>
The compiler has replaced the desired function call with some other function call.
So yes, can and will do this if the optimizer is programmed to. If it has visibility it is more likely to optimize the two parts as a whole:
unsigned int more_fun ( unsigned int a, unsigned int b )
{
return(a+b);
}
unsigned int fun ( void )
{
return(more_fun(1,2));
}
Disassembly of section .text:
00000000 <more_fun>:
0: e0800001 add r0, r0, r1
4: e12fff1e bx lr
00000008 <fun>:
8: e3a00003 mov r0, #3
c: e12fff1e bx lr
which is not replacing one function with another like the printf example but it is replacing the optimized function with a possibly more optimized inline solution.
And yes certainly some compilers will optimize out a dead-ish loop:
unsigned int fun ( void )
{
unsigned int ra;
for(ra=0;ra<10;ra++)
{
}
return(ra);
}
00000000 <fun>:
0: e3a0000a mov r0, #10
4: e12fff1e bx lr
Granted this is a trivial one but I have generated pseudo randomizers that were dead code like this, depends on the compiler/optimizer and the code and if it has been programmed to it will reduce the loop/code into something simpler.
Or perhaps this is what you were asking:
unsigned int more_fun ( unsigned int n )
{
return((n*(n-1))/2);
}
unsigned int fun ( void )
{
return(more_fun(10));
}
00000000 <more_fun>:
0: e2403001 sub r3, r0, #1
4: e0020093 mul r2, r3, r0
8: e1a000a2 lsr r0, r2, #1
c: e12fff1e bx lr
00000010 <fun>:
10: e3a0002d mov r0, #45 ; 0x2d
14: e12fff1e bx lr
The math is removed where possible.
You can't assume a particular compiler will do this, nor expect two compilers to produce the same code/optimization. But CAN and WILL a compiler do this, yes, if it is programmed to and has visibility into all the code it needs to optimize.
As far as "allowed", the compilers job is to functionally replace one language with another, which is in part why any two compilers that translate from one language to another (same input language to same output target) can and will produce different output code, its a functional replacement there isn't a single right answer for the output of a compile, it can vary. So where possible per the language, as shown above the compiler generates functionally equivalent code, that's its job so it is allowed to do that job. Although I would not consider putchar as a printf replacement as the compiler didnt look at my printf code, but at the same time I assume this compiler (gcc) has a command line option to not permit that. Likewise not uncommon for compilers to replace say a struct assignment, two structs of the same type a = b; with a memcpy, but at the same time have a command line option indicating I don't want to you to replace the code I asked for with a memcpy, I wanted it done discretely.
Between gcc and clang you will see these behaviors so as far as the word "allowed" goes, I guess it is allowed. As shown you can examine the compilers output and see for your use case, what the compiler did.
Compilers do this regularly for simpler patterns recognised by the optimiser.
In your particular case, the change of algorithm might have counterproductive side-effects as bubble sort is more efficient than quick sort on arrays that are mostly sorted.
Note also that the optimisation must keep the same semantics: replacing a stable sorting algorithm with a non-stable one such as quick sort is only acceptable if it can be asserted that stability is not required. Sorting a simpler arrays of int seems unaffected by this issue, but on architectures with negative zeroes or padding bits, it would make a difference. If the array has a floating type, stability of the sorting algorithm definitely can impact the final order.
Yes, compilers can and will do so. As an example, consider this population count function using Kernighan's algorithm:
int popcount(unsigned x)
{
int c;
for (c = 0; x != 0; x &= x - 1)
c++;
return (c);
}
Modern clang and gcc versions recognise this algorithm and given suitable flags, compile it down to two instructions:
popcount:
popcntl %edi, %eax
retq
This is because the compiler recognises that the function implements a population count and replaces the whole algorithm with a machine instruction that performs the same purpose. Isn't that neat?
The compiler technology is not able to recognize such complex patterns (and the engineers do not even try to do it, it's undecidable issue) -- but yes --, for the recognized patterns it is allowed by the C standard to replace the initial code with another code whose semantics does not change.
The optimization techniques use different representations of the code for each particular optimization. A complex compiler can translate the input code in lots of different intermediate languages and the representation of each language allows better searching for patterns of some optimization.
But in no case the compilers try to look for pattersn representing complex algorithms. Of course you can try to do it, but this is useless and it is more affordable to employ a good programmer than to try to implement a system that would try to solve the halting problem.
Even if a compiler could recognize an algorithm it should not be allowed to replace the algorithm with a functional equivalent algorithm.
The reason is that the algorithm may have been chosen because of idiosyncrasies of the data it has to process and the compiler cannot know about these.
Note that I say algorithm. That is a lot more than e.g. calculating the length of a string such as strlen.
In the sort example, if the data are always nearly sorted then bubble may have the least overhead. Though bubble is generally not efficient, it could be the most efficient here.
Theoretically it is possible and compiler is free to chose the way program is executed if the observable behaviour of the program will be the same.
