The commonly used programming language in the OI community is C++. Since we use this language, we are inevitably bound to deal with compilers and language standards. As everyone knows, C++ is extremely chaotic and evil; this article aims to provide practical compiler-related knowledge sufficient for competitions.
Introduction to Compiler Optimizations
What Is Optimization (Optimization)
According to the as-if Rule (The as-if Rule), improvements can be made to program execution speed and executable-file size while preserving semantics.
<!-- ### Which competitions enable optimizations? --> <!-- TODO: Competitions enabling O2 -->Common Compiler Optimizations
Constant Folding (Constant Folding)
Constant folding, also called constant propagation (Constant Propagation), can propagate a constant if an expression can be determined to be a constant, before its next definition (Definition).
int x = 1;
int y = x; // x = 1, => y = 1
x = 3;
int z = 2 * y; // z => 2 * y = 2 * 1 = 2
int y2 = x * 2; // x = 3, => y2 = 6
This code can be transformed during compilation into:
int x = 1;
int y = 1;
x = 3;
int z = 2;
int y2 = 6;
Example: https://godbolt.org/z/oEfY35TTd
Dead Code Elimination (Deadcode Elimination)
As the name suggests, a piece of code is deleted if it is not used.
int test() {
int a = 233;
int b = a * 2;
int c = 234;
return c;
}
It will be transformed into
int test() { return 234; }
Note that this code first undergoes constant folding, making the return value determinable as 234. Since a and b are inactive variables, they are deleted.
Loop Rotation (Loop Rotate)
Convert a loop from the "for" form to the "do-while" form, adding a condition check before it. This transformation mainly prepares for other transformations.
for (int i = 0; i < n; ++i) {
auto v = *p;
use(v);
}
Transform into
if (0 < n) {
do {
auto v = *p;
use(v);
++i;
} while (i < n);
}
Loop Invariant Code Motion (Loop Invariant Code Motion)
Based on alias analysis (Alias Analysis), move code proved to be invariant in a loop (possibly involving memory accesses and load/store operations, and therefore depending on alias analysis) out of the loop body, reducing the amount of code inside the loop body.
for (int i = 0; i < n; ++i) {
auto v = *p;
use(v);
}
At first glance, this code can be moved out as follows:
auto v = *p;
for (int i = 0; i < n; ++i) {
use(v);
}
In reality, however, if n <= 0, the loop is never entered, but we have still executed one extra instruction (which may have side effects!). Therefore, loops are usually rotated into the do-while form, which makes it convenient to insert a "loop guard". Loop-invariant code motion is then performed.
if (0 < n) { // loop guard
auto v = *p;
do {
use(v);
++i;
} while (i < n);
}
Loop Unrolling (Loop Unroll)
A loop contains a loop body and various branch statements, requiring modern CPUs to perform some branch prediction. Unroll the loop directly, trading a certain amount of code size for execution time.
for (int i = 0; i < 3; i++) {
a[i] = i;
}
Transform into:
a[0] = 0;
a[1] = 1;
a[2] = 2;
Loop Unswitching (Loop Unswitching)
Loop unswitching moves the condition in a loop outside the loop, then places two loops under the two conditions outside. This can increase the possibility of loop vectorization and parallelization (simple loops are generally easier to vectorize).
// clang-format off
void before(int x) {
for(;/* i in some range */;) {
/* A */;
if (/* condition */ x % 2) {
/* B */;
}
/* C */;
}
}
void after(int x) {
if (/* condition */ x % 2) {
for(;/* i in some range */;) {
/* A */;
/* B */; // Execute B directly, without checking the loop condition
/* C */;
}
} else {
for(;/* i in some range */;) {
/* A */;
// Do not execute B
/* C */;
}
}
}
Code Layout Optimizations (Code Layout Optimizations)
When a program executes, its execution paths can be divided into hot and cold paths (cold/hot path). CPU jumps are, in most cases, slower than direct sequential execution; the latter is often called "fallthrough" by compiler authors. Correspondingly, code that is executed frequently is called hot code, while code opposite to it is called cold code. In OI code, if a piece of code handles a special boundary condition in a loop, exception handling, or similar logic, that part is cold code.
A basic block (Basic Block) is a fundamental structure of control flow. A procedure (Procedure) consists of several basic blocks that form a directed graph. During executable-file generation, the compiler must arrange a layout (Layout) for placing the basic blocks; how to arrange this layout is the focus of this optimization.
In principle, hot code should preferably be placed together, while cold code should be separated. The reason is that this makes better use of the instruction cache and improves the locality of hot code.
// clang-format off
int hotpath; // <-- Hot!
if (/* Boundary condition */ false) {
// <-- Cold!
}
int hotpath_again; // <-- Hot!
Basic Block Placement (Basic Block Placement)
We use labels to express a kind of “pseudo-machine code.” This C++ program has two translation methods:
Layout 1
// clang-format off
hotblock1:
Stmts; // <-- Hot!
if (/* Boundary condition is false */ true)
goto hotblock2; // Happens frequently! ------+
coldblock: /* | */
Stmt; // <- Cold |
Stmt; // <- Cold |
Stmt; // <- Cold | Crossing many instructions is costly!
Stmt; // <- Cold |
Stmt; // <- Cold |
Stmt; // <- Cold |
Stmt; // <- Cold |
hotblock2: /* | */
Stmts; // <- Hot! <----------+
The other layout is:
Layout 2
// clang-format off
hotblock1:
Stmts; // <-- Hot!
if (/* Boundary condition */ false)
goto coldblock; // Happens rarely
hotblock2: /* | Low cost! */
Stmts; // <- Hot! <-----------------+
coldblock:
Stmt; // <- Cold
Stmt; // <- Cold
Stmt; // <- Cold
Stmt; // <- Cold
Stmt; // <- Cold
We can see that in the latter layout, the two hot code blocks are placed together, resulting in better execution efficiency.
To tell the compiler whether a branch is likely to be executed, you can use C++20 [[likely]] and [[unlikely]]:https://en.cppreference.com/w/cpp/language/attributes/likely
If the competition does not use a standard above C++20, __builtin_expect (GNU Extension) can be used.
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (unlikely(/* Some boundary condition check */ false)) {
// Cold code
}
Hot-Cold Splitting (Hot Cold Splitting)
A procedure (Procedure) contains both hot and cold paths, and when the cold code is long, it is better to make the cold code a function call rather than block the hot path. This also reminds us not to be clever and make every function inline. Cold code hinders execution speed much more than a function call does.
Bad Code Layout
// clang-format off
void foo() {
// clang-format off
hotblock1:
Stmts; // <-- Hot!
if (/* Boundary condition is false */ true)
goto hotblock2; // Happens frequently! ------+
coldblock: /* | */
Stmt; // <- Cold |
Stmt; // <- Cold |
Stmt; // <- Cold | Crossing many instructions is costly!
Stmt; // <- Cold |
Stmt; // <- Cold |
Stmt; // <- Cold |
Stmt; // <- Cold |
hotblock2: /* | */
Stmts; // <- Hot! <----------+
}
Good Code Layout
// clang-format off
void foo() {
hotblock1:
Stmts; // <-- Hot!
if (/* Boundary condition */ false)
coldBlock(); // Separate cold code, making the hot path friendlier to the cache
hotblock2:
Stmts; // <- Hot!
}
void coldBlock() {
Stmt; // <- Cold
Stmt; // <- Cold
Stmt; // <- Cold
Stmt; // <- Cold
Stmt; // <- Cold
Stmt; // <- Cold
Stmt; // <- Cold
}
Hot-cold splitting is actually the reverse operation of function inlining (Function Inlining). The existence of this optimization shows that function inlining does not necessarily make a program run faster. In fact, if the inlined code is cold code, it can make the program run slower! Some compilers have compiler options for forced inlining, but their use is not recommended. Compilers have an internal static analysis process that calculates the probabilities of each basic block and branch, as well as a cost model related to function calls, and uses these to decide whether to inline. Making this decision yourself is not necessarily better than the compiler's decision.
In fact, without additional information, compilers usually assume that the probabilities of taking and not taking a branch are equal, and use this to propagate the hotness and coldness of each control-flow path. Part of PGO (Profile Guided Optimization) is to obtain the actual branch probabilities in the real environment through several performance tests and experiments. This information can produce a better code layout.
Function Inlining (Function Inlining)
Function calls usually need to pass parameters through registers and the stack. Both the caller and callee need to save certain register states; this process is usually called the calling convention (calling convention). A function call therefore incurs some time overhead, while an inline function means writing the function directly in the caller's procedure without making an actual function call.
int add(int x) { return x + 1; }
int foo() {
int a = 1;
a = add(a);
}
add() can be inlined into foo():
int foo() {
int a = 1;
a = a + 1; // <-- The function body of add(), without passing parameters
}
always_inline,__force_inline
https://clang.llvm.org/docs/AttributeReference.html#always-inline-force-inline
Some compilers provide a way to manually inline a function call by adding __attribute__((always_inline)) before the function. Using this is not necessarily faster than a function call; the compiler trusts that the programmer has sufficient judgment in this case.
Tail Call Optimization (Tail Call Optimization)
When a function call is located at the end of a function body, this type of function call is called a tail call (Tail Call). Special optimizations can be performed for this special form of call. Most architectures have a Frame Pointer (a.k.a FP) and Stack Pointer (a.k.a SP), which maintain the function's call frame (Frame). If the call is at the end of the function, we do not need to retain the outer function's call record and can directly replace it with the inner function.
Replace Function Calls with Jump Instructions
Under most architectures, a function call needs to save the position of the current program counter $pc and several caller-saved registers so that execution can return to the original context. A tail call does not need this process and is translated directly into a jump instruction, because tail recursion never returns to the position where the function was running.
A simple example: https://godbolt.org/z/e7b1safaW
int test(int a);
int tailCall(int x) { return test(x); }
tailCall(int): ; @tailCall(int)
jmp test(int)@PLT ; TAILCALL
Automatic Tail-Recursion Rewriting
If a function's tail call is to itself, the function is tail-recursive. In a broad sense, indirect recursion (recursion jointly formed by two or more functions) also forms recursion, and if all calls are tail calls, it also belongs to the category of tail recursion. Tail recursion can be optimized by the compiler into a non-recursive form, reducing extra stack overhead and function-call costs. Many algorithmic competition contestants prefer to write non-recursive code; without optimization, this can greatly reduce the constants in the code. However, with optimization enabled, the quality of the binary generated from recursive code is no different from hand-written code.
int fac(int n) {
if (n < 2) return 1;
return /* use */ n * fac(n - 1); /* n is used, so tail-recursion optimization cannot be performed directly!*/
}
Notice that this function is not tail-recursive, but it can be rewritten as:
int fac(int acc, int n) {
if (n < 2) return acc;
return fac(acc * n, n - 1);
}
The new code is tail-recursive.
Modern compilers can complete this process automatically. If your code can be rewritten as tail recursion, the compiler can recognize this form and complete the rewrite.
Tail-Recursion Elimination -Rpass=tailcallelim
Since the function is already tail-recursive, the recursive statement can be deleted directly, and the function can be converted into a non-recursive form through some static analysis. We will not delve into how compiler authors accomplish this here. In practice, for the vast majority of OI code, if both recursive and non-recursive versions exist, the code can generally be automatically optimized into the non-recursive version. Here are some specific examples:
GCD
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
Fibonacci Sequence
// Expand the term fib(n - 2)
// fib(n - 1) cannot be transformed into a non-recursive form, so the optimized code is still exponential
int fib(int n) {
if (n < 2) return 1;
return fib(n - 1) + fib(n - 2);
}
Factorial
// Expand into a scalar loop, then perform automatic vectorization; the generated code is SIMD
unsigned fac(unsigned n) {
if (n < 2) return 1;
return n * fac(n - 1);
}
The assembly generated after these functions are optimized is exactly the same as that of the non-recursive versions; the recursion is directly eliminated. For OI contestants, with O2 enabled, it is safe to write recursive versions of various algorithms; they will be no different from the non-recursive versions. If your function itself cannot be rewritten into a non-recursive form, the compiler cannot help either.
Strength Reduction (Strength Reduction)
A common compiler optimization. The simplest example is changing x * 2 into x << 1; the latter form is quite common in OI. Compilers automatically perform similar optimizations, and with optimization enabled, x * 2 and x << 1 are completely equivalent. Strength reduction (Strength Reduction) converts high-cost instructions into low-cost instructions.
Scalar Operator Transformation
Replacing Multiplication with Shifting
int a;
a = x * 2; // bad!
a = x << 1; // good!
Note that signed and unsigned numbers differ significantly at the levels of shifting and type promotion. The sign bit receives special treatment during shifting, including arithmetic and logical shifts. This is particularly evident when writing binary search, segment trees, and other code containing many divisions by two: signed integer division cannot be directly optimized into a single right-shift operation.
int l, r;
/* codes */
int mid = (l + r) / 2; /* If the compiler cannot assume l and r are nonnegative, it will generate inferior code */
// Cannot be optimized into
// mid = (l + r) >> 1
// Counterexample:
// mid = -127
// mid / 2 = -63
// mid >> 1 = -64
int mid = (l + r);
int sign = mid >> 31; /* Logical right shift, obtaining the sign bit */
mid += sign;
mid >>= 1; /* Arithmetic right shift */
Possible solutions:
- Use
unsigned l, r;; indices should be unsigned in the first place. - Use shifting in the source code.
Replacing Division with Multiplication
int x = a / 3;
This process can be transformed into x = a * 0x55555556 >> 32. For details, see this Zhihu answer or the original paper.
Strength Reduction of Index Variables (IndVars)
The compiler automatically identifies index variables in loops and converts related high-cost operations into low-cost operations.
int a = 0;
for (int i = 1; i < 10; i++) {
a = 3 * i; // bad!
a = a + 3; // good!
}
Using a = 3 * i directly is common in OI, but the compiler can automatically analyze that the equivalent transformation is a = a + 3, using a lower-cost addition instead of multiplication. Analyzing the iteration process of a loop variable is called SCEV (Scalar Evolution).
SCEV can also optimize some loops:
int test(int n) {
int ans = 1;
for (int i = 0; i < n; i++) {
ans += i * (i + 1);
}
return ans;
}
This function is optimized into an formula sum; see https://godbolt.org/z/ET8d89vv. At present, this behavior only occurs with LLVM-based compilers; GCC is more conservative.
test(int): # @test(int)
test edi, edi
jle .LBB0_1
lea eax, [rdi - 1]
lea ecx, [rdi - 2]
imul rcx, rax
lea eax, [rdi - 3]
imul rax, rcx
shr rax
imul eax, eax, 1431655766
and ecx, -2
lea eax, [rax + 2*rcx]
lea eax, [rax + 2*rdi]
dec eax
ret
.LBB0_1:
mov eax, 1
ret
Automatic Vectorization (Auto-Vectorization)
Single instruction, multiple data is a good way to provide single-core parallelism. Using these instructions can take advantage of CPU SIMD registers, which are wider than general-purpose registers—for example, placing four integers in them at once and then calculating. OI contestants do not need to understand the details of automatic vectorization. Generally speaking, the Clang compiler performs more aggressive automatic vectorization than GCC:
// https://godbolt.org/z/h1hx5sWoE
void test(int *a, int *b, int n) {
for (int i = 0; i < n; i++) {
a[i] += b[i];
}
}
__restrict type specifier (GNU, MSVC)
The regions corresponding to two arbitrary pointers may overlap (overlap). In that case, a special check is needed to determine whether vector code can be used. The figure below shows an example of pointer overlap:
__restrict is a convention that makes the compiler assume that the memory regions pointed to by two pointers will never overlap.
void test(int* __restrict a, int* __restrict b, int n) {
for (int i = 0; i < n; i++) {
a[i] += b[i];
}
}
__restrict is not part of the C++ standard, but it can be used with all major compilers. This keyword affects the quality of code generation for automatic vectorization and can be used in extreme constant-optimization situations.
Common Language Misuses Related to Compiler Optimizations
inline - Inlining
Function inlining is usually completed automatically by the compiler when O2 is enabled. inline in a structure definition is completely redundant; if the competition you are preparing for enables O2 optimization, there is no need to declare functions as inline at all. If O2 is not enabled, using inline will not make the compiler actually inline the function either.
In modern C++, the inline keyword is treated as semantic behavior related to linkage and exported symbols, rather than as function inlining.
register - False Register Advice
Modern compilers directly ignore your register keyword. Your own idea of register allocation is generally not as clever as the compiler running a register-allocation algorithm directly. This keyword was deprecated in C++11 and removed in C++171.
https://en.cppreference.com/w/cpp/keyword/register
Undefined Behavior (Undefined Behavior) and Compiler Optimizations
The compiler can assume that a C++ program has no undefined behavior (undefined behavior, UB). Therefore, when compiling a program containing UB, the compiler may produce unexpected results. At the same time, it can perform more aggressive and unconstrained optimizations under the assumption that UB does not exist.
Common types of UB include:
- Signed overflow;
- Using uninitialized variables;
- Out-of-bounds access;
- Null pointer dereference;
- Infinite loops without side effects.
Other UB and examples can be learned about in detail through further reading.
Signed Overflow
int f(int x) { return x * 2 / 2; }
The compiler can assume that the program has no signed overflow, so this function may be optimized into
int f(int x) { return x; }
Examples: https://godbolt.org/z/WKv3W5hvM, https://godbolt.org/z/qqE9nxP1j.
This assumption can be disabled with the -fwrapv option. Examples: https://godbolt.org/z/5x3K5KGnr, https://godbolt.org/z/4r4a4EzMW.
Using Uninitialized Variables
int f(int x) {
int a;
if (x) // either x nonzero or UB
a = 42;
return a;
}
The compiler can assume that the program does not use uninitialized variables, so a must be initialized. Consequently, this function may be optimized into
int f(int) { return 42; }
Examples: https://godbolt.org/z/8WYMYYjdG, https://godbolt.org/z/qvGd1nvv9.
Out-of-Bounds Access
int table[4] = {};
bool exists_in_table(int v) {
// return true in one of the first 4 iterations or UB due to out-of-bounds
// access
for (int i = 0; i <= 4; i++)
if (table[i] == v) return true;
return false;
}
The compiler can assume that the program has no out-of-bounds access, so this function must return before an out-of-bounds access occurs. Consequently, this function may be optimized into
bool exists_in_table(int) { return true; }
Example: https://godbolt.org/z/xfePeYsE3.
Null Pointer Dereference
int f(int* p) {
int x = *p;
if (!p)
return x; // Either UB above or this branch is never taken
else
return 0;
}
The compiler can assume that the program has no null pointer dereference, so !p is always false, and this function may therefore be optimized into
int f(int*) { return 0; }
Examples: https://godbolt.org/z/GY1jvsrb5, https://godbolt.org/z/4ronPsnxf.
Infinite Loops Without Side Effects
Verifying Fermat's Last Theorem
It follows from Fermat's Last Theorem that the Diophantine equation has no positive integer solutions. The following program attempts to enumerate the integers in to verify whether this equation holds. If it returns true, it means that an integer solution was found in the range , and Fermat's Last Theorem would therefore be false.
#include <iostream>
bool fermat() {
const int max_value = 1000;
// Endless loop with no side effects is UB
for (int a = 1, b = 1, c = 1; true;) {
if (((a * a * a) == ((b * b * b) + (c * c * c))))
return true; // disproved :()
a++;
if (a > max_value) {
a = 1;
b++;
}
if (b > max_value) {
b = 1;
c++;
}
if (c > max_value) c = 1;
}
return false; // not disproved
}
int main() {
std::cout << "Fermat's Last Theorem ";
fermat() ? std::cout << "has been disproved!\n"
: std::cout << "has not been disproved.\n";
}
The compiler can assume that the program has no infinite loop without side effects, and thus assume that the for loop in the fermat() function will terminate and return true at some point. The final program may output:
Fermat's Last Theorem has been disproved!
Examples: https://godbolt.org/z/d834MK7bz, https://godbolt.org/z/Eov9nsKqf.
Sanitizer
The sanity guarantor. It checks at runtime whether your program has undefined behavior, out-of-bounds array access, null pointers, and so on. In local debug mode, it is recommended to enable some sanitizers, which can greatly shorten your debugging time. These sanitizers were developed by Google, and most of them can be used with GCC and Clang. Sanitizers are more mature in LLVM, so contestants are recommended to use the Clang compiler locally for related debugging.
Address Sanitizer -fsanitize=address
https://clang.llvm.org/docs/AddressSanitizer.html
Both GCC and Clang support this sanitizer. It includes the following checks:
- Out-of-bounds access
- Use-after-free
- Use-after-return
- Double-free
- Memory leaks
- Use-after-scope
Enabling this check makes your program approximately 2x slower.
Undefined Behavior Sanitizer -fsanitize=undefined
https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html
Undefined Behavior Sanitizer (a.k.a. UBSan) is used to check for undefined behavior in code. Both GCC and Clang support this sanitizer. It automatically checks whether your program has undefined behavior. UBSan's checks include:
- Shift overflow, such as shifting a 32-bit integer left by 72 bits
- Signed integer overflow
- Overflow when converting floating-point data to an integer
UBSan checks are optional; see the provided webpage for their impact on the program.
Miscellaneous
Compiler Explorer
Observe the behavior and assembly code of various compilers here: https://godbolt.org
Further Reading
- The LLVM Project Blog: What Every C Programmer Should Know About Undefined Behavior #1/3
- The LLVM Project Blog: What Every C Programmer Should Know About Undefined Behavior #2/3
- The LLVM Project Blog: What Every C Programmer Should Know About Undefined Behavior #3/3