Compilation Optimizations

The commonly used programming language in the OI community is C++. Since this language is used, it inevitably involves dealing with compilers and language standards. As is well known, C++ is quite chaotic and evil. This article aims to provide practical knowledge about compilers, sufficient for competitive programming.

Introduction to Compiler Optimizations

What is Optimization

According to the as-if Rule, improvements are made to program execution speed and executable file size while preserving semantics.

Common Compiler Optimizations

Constant Folding

Constant folding, also known as constant propagation, if an expression can be determined to be a constant, constant propagation can be performed before its next 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

As the name suggests, code that is not used will be removed.

int test() {
  int a = 233;
  int b = a * 2;
  int c = 234;
  return c;
}

Will be transformed into

int test() { return 234; }

Note that this code first undergoes constant folding, making the return value determinable as 234, and a, b become inactive variables, thus they are removed.

Loop Rotate

Transform a loop from "for" form to "do-while" form, with an additional conditional check in front. This transformation mainly prepares for other transformations.

for (int i = 0; i < n; ++i) {
  auto v = *p;
  use(v);
}

Transformed into

if (0 < n) {
  do {
    auto v = *p;
    use(v);
    ++i;
  } while (i < n);
}

Loop Invariant Code Motion

Based on alias analysis, code within the loop that is proven to be invariant (may involve memory access, load/store, thus relying on alias analysis) is hoisted out of the loop body, reducing code inside the loop.

for (int i = 0; i < n; ++i) {
  auto v = *p;
  use(v);
}

Intuitively, this code can be hoisted as:

auto v = *p;
for (int i = 0; i < n; ++i) {
  use(v);
}

However, if n <= 0, the loop is never entered, but we executed an extra instruction (which may have side effects!). Therefore, loops are usually rotated into do-while form, making it convenient to insert a "loop guard". Then loop invariant code motion is performed.

if (0 < n) {  // loop guard
  auto v = *p;
  do {
    use(v);
    ++i;
  } while (i < n);
}

Loop Unroll

Loops contain loop bodies and various branch statements, requiring modern CPUs to perform branch prediction. Directly unrolling the loop trades code size for execution time.

for (int i = 0; i < 3; i++) {
  a[i] = i;
}

Transformed into:

a[0] = 0;
a[1] = 1;
a[2] = 2;

Loop Unswitching

Loop unswitching moves conditional expressions inside the loop outside, then places two loops under each external condition, increasing the possibility of loop vectorization and parallelization (usually simpler loops are 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 */; // directly execute B, no loop condition check
      /* C */;
    }
  } else {
     for(;/* i in some range */;) {
      /* A */; 
               // do not execute B
      /* C */;
    }
  }
}

Code Layout Optimizations

During program execution, execution paths can be divided into cold/hot paths. CPU jumps are generally slower than sequential execution, the latter often referred to as "fallthrough" by compiler writers. Correspondingly, frequently executed code is called hot code, while the opposite is cold code. In OI code, if there is a special boundary condition check within a loop, or exception handling, similar logic, such code is cold code.

A basic block is the basic structure of control flow. A procedure consists of several basic blocks forming a directed graph. During executable generation, the compiler needs to arrange a layout for placing basic blocks, and how to arrange the layout is the focus of this optimization.

In principle, hot code should be placed together, while cold code should be separated. The reason is to better utilize instruction cache, improving locality for hot code.

// clang-format off
int hotpath; // <-- hot!
if (/* boundary condition */ false) {
    // <-- cold!
}
int hotpath_again;  // <-- hot!

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 false */ true)
        goto hotblock2; // frequent! ------+
coldblock:                           /*   |   */
    Stmt; // <- cold                        |
    Stmt; // <- cold                        |
    Stmt; // <- cold                        |  costly across many instructions!
    Stmt; // <- cold                        |
    Stmt; // <- cold                        |
    Stmt; // <- cold                        |
    Stmt; // <- cold                        |
hotblock2:                          /*    |   */
    Stmts; // <- hot!           <----------+

Another layout is:

Layout 2

// clang-format off
hotblock1:
    Stmts; // <-- hot!
    if (/* boundary condition */ false)
        goto coldblock; // rare
hotblock2:                         /*   |   low cost!  */
    Stmts; // <- hot!  <-----------------+
coldblock:
    Stmt; // <- cold
    Stmt; // <- cold
    Stmt; // <- cold
    Stmt; // <- cold
    Stmt; // <- cold

We see in the latter layout, two hot code blocks are placed together, resulting in better execution efficiency.

To inform the compiler whether a branch is likely to be taken, C++20 [[likely]] and [[unlikely]] can be used: https://en.cppreference.com/w/cpp/language/attributes/likely

If the competition does not use C++20 or above, __builtin_expect (GNU Extension) can be utilized.

#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

A procedure contains both cold and hot paths, and the cold code is long. A better approach is to make the cold code a function call rather than blocking the hot path. This also suggests we should not be overly clever by making all functions inline. Cold code hinders execution speed much more than function calls.

Bad Code Layout

// clang-format off
void foo() {
      // clang-format off
hotblock1:
    Stmts; // <-- hot!
    if (/* boundary condition false */ true)
        goto hotblock2; // frequent! ------+
coldblock:                           /*   |   */
    Stmt; // <- cold                        |
    Stmt; // <- cold                        |
    Stmt; // <- cold                        |  costly across many instructions!
    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 out, making hot path more cache-friendly
hotblock2:
  Stmts;  // <- hot!
}

void coldBlock() {
  Stmt;  // <- cold
  Stmt;  // <- cold
  Stmt;  // <- cold
  Stmt;  // <- cold
  Stmt;  // <- cold
  Stmt;  // <- cold
  Stmt;  // <- cold
}

Hot cold splitting is essentially the reverse operation of function inlining. The existence of this optimization reveals that function inlining does not necessarily make programs faster. If the inlined code is cold, it might even slow down the program! Some compilers have forced inlining options, but they are not recommended. Compilers internally have a static analysis process, calculating probabilities for each basic block and branch, and a cost model related to function calls, to decide whether to inline. Self-decided inlining may not be better than the compiler's decision.

In fact, without additional information, compilers typically assume branch taken and not-taken probabilities are equal, propagating cold/hot degrees of control flow paths accordingly. Part of PGO (Profile Guided Optimization) involves obtaining actual program branch probabilities through several performance tests and experiments, making code layout better.

Function Inlining

Function calls usually require registers and stack to pass parameters, both caller and callee need to save certain register states, a process often called calling convention. A function call thus incurs some time overhead. Inlining a function means writing the function directly into the caller's procedure, avoiding actual function calls.

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;  // <-- body of add(), without parameter passing
}

`always_inline`,`__force_inline`

https://clang.llvm.org/docs/AttributeReference.html#always-inline-force-inline

Some compilers provide manual function inlining methods, adding __attribute__((always_inline)) before a function. Using this does not necessarily make it faster than a function call; the compiler trusts the programmer has good judgment at this point.

Tail Call Optimization

When a function call is at the tail position of a function body, such a call is called a tail call. For this special form of call, some special optimizations can be performed. Most architectures have Frame Pointer (a.k.a FP) and Stack Pointer (a.k.a SP), maintaining function frames. If the call is at the tail, we can discard the outer function's call record and directly replace it with the inner function.

Using Jump Instructions Instead of Function Calls

Function calls on most architectures require saving the current program counter $pc location, saving some caller-saved registers to return to the context. Tail calls do not need this process and are directly translated into jump instructions, because tail recursion never returns to the function's execution position.

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. Broadly speaking, indirect recursion (formed by two or more functions) where all are tail calls also falls into tail recursion. Tail recursion can be optimized by the compiler into non-recursive form, reducing extra stack overhead and function call cost. Many algorithm competition enthusiasts prefer writing non-recursive code; without optimizations, this greatly optimizes code constants. However, with optimizations enabled, recursive code generates binary quality almost identical to hand-written code.

int fac(int n) {
  if (n < 2) return 1;
  return /* using */ n * fac(n - 1); /* uses variable n, cannot directly do tail recursion optimization! */
}

Note this function is not tail recursive, but 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 automatically perform this process. If your code can be rewritten as tail recursive, 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 directly removed. Through certain static analysis, the function can be transformed into non-recursive form. We won't delve into how compiler authors achieve this here. From practical experience, most OI code, if there are both recursive and non-recursive versions, can generally be automatically optimized into non-recursive version. Here are some concrete examples for readers:

GCD

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

Fibonacci Sequence

// expand fib(n - 2) term
// fib(n - 1) cannot be transformed to non-recursive, optimized code remains exponential
int fib(int n) {
  if (n < 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

Factorial

// expand into scalar loop, then auto-vectorize, generated code is SIMD
unsigned fac(unsigned n) {
  if (n < 2) return 1;
  return n * fac(n - 1);
}

The assembly of these functions after optimization is identical to the non-recursive version; recursion is directly eliminated. For OI participants, you can safely write recursive versions of various algorithms with O2 enabled; there will be no difference from non-recursive versions. If the function you write cannot be rewritten into non-recursive form, the compiler can do nothing.

Strength Reduction

A common compilation optimization. The simplest example is x * 2 becoming x << 1, the latter being quite common in OI. Compilers automatically perform similar optimizations; with optimization switches on, x * 2 and x << 1 are completely equivalent. Strength reduction converts high-cost instructions to low-cost instructions.

Scalar Operator Transformations

Bitwise Operations Instead of Multiplication

int a;
a = x * 2;   // bad!
a = x << 1;  // good!

Note that signed and unsigned numbers have distinct differences in shifting and promotion. The sign bit receives special treatment during shifting, including arithmetic shift and logical shift. This is prominent when writing binary search/segment trees with many divide-by-two operations; signed integer division cannot be directly optimized to a single right shift.

int l, r;
/* codes */
int mid = (l + r) / 2; /* if compiler cannot assume l, r non-negative, generates poorer code */
                       // cannot optimize to
                       // mid = (l + r) >> 1
                       // counterexample:
                       // mid = -127
                       // mid / 2 = -63
                       // mid >> 1 = -64

int mid = (l + r);
int sign = mid >> 31; /* logical right shift, get sign bit */
mid += sign;
mid >>= 1; /* arithmetic right shift */

Possible solutions:

Use unsigned l, r;, indices should be unsigned anyway.
Use shift in source code.

Multiplication Instead of Division

int x = a / 3;

This can be transformed into x = a * 0x55555556 >> 32. For details, see this Zhihu answer or the original paper.

Induction Variable Strength Reduction (IndVars)

Compiler automatically identifies induction variables in loops and converts related high-cost processes to low-cost.

int a = 0;
for (int i = 1; i < 10; i++) {
  a = 3 * i;  // bad!
  a = a + 3;  // good!
}

Here, directly using a = 3 * i is common in OI, but the compiler can automatically analyze that the equivalent transformation is a = a + 3, using lower-cost addition instead of multiplication. Analyzing loop variable evolution 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 will be optimized to an $O(1)$ summation formula. Refer to https://godbolt.org/z/ET8d89vvK. Currently, only LLVM-based compilers exhibit this behavior; 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

Auto-Vectorization

Single Instruction Multiple Data (SIMD) is a good method for single-core parallelism. Using such instructions utilizes CPU's SIMD registers, which are wider than general-purpose registers, e.g., holding 4 integers at once for computation. OI participants need not understand auto-vectorization details. Generally, Clang performs more aggressive auto-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)

Two arbitrary pointers may have overlapping regions, requiring special checks for vector code usability. The following diagram shows an example of pointer overlap:

__restrict is a convention making the compiler assume two pointers never point to overlapping memory regions.

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 is available in major compilers. This keyword affects auto-vectorization code generation quality and can be used in extreme constant optimization scenarios.

inline - Inlining

Function inlining is usually automatically done by the compiler with O2 enabled. inline in struct definitions is completely redundant. If the competition enables O2 optimization, there is no need to declare functions as inline. If O2 is not enabled, using inline won't make the compiler actually inline.

The inline keyword in modern C++ is treated as a linking and symbol export semantic behavior, not for function inlining.

register - False Register Hint

Modern compilers ignore your register keyword; your own register allocation ideas are generally not as smart as the compiler's register allocation algorithm. This keyword was deprecated in C++11 and removed in C++17¹.

https://en.cppreference.com/w/cpp/keyword/register

Undefined Behavior and Compilation Optimizations

Compilers can assume C++ programs have no undefined behavior (UB). Therefore, when compiling programs with UB, compilers may produce unexpected results. Meanwhile, compilers can also perform more aggressive and free optimizations under the assumption of no UB.

Common UB includes:

Signed overflow;
Using uninitialized variables;
Out-of-bounds access;
Null pointer dereference;
Infinite loops without side effects.

Other UB and examples can be understood through extended reading.

Signed Overflow

int f(int x) { return x * 2 / 2; }

The compiler can assume the program has no signed overflow, so this function might be optimized to

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 the program has no use of uninitialized variables, so a must be initialized, thus this function might be optimized to

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 the program has no out-of-bounds access, so the function must return before out-of-bounds access occurs, thus this function might be optimized to

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 the program has no null pointer dereference, so !p is always false, thus this function might be optimized to

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

According to Fermat's Last Theorem, the equation $a^3=b^3+c^3$ has no positive integer solutions. The following program attempts to enumerate integers in $[1,1000]$ to verify whether the equation holds. If it returns true, it means a set of integer solutions is found within $[1,1000]$, thus disproving Fermat's Last Theorem.

#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 the program has no infinite loops without side effects, thus believing the for loop in fermat() will terminate at some point and return true. The program may eventually output:

1	`Fermat's Last Theorem has been disproved!`

Examples: https://godbolt.org/z/d834MK7bz, https://godbolt.org/z/Eov9nsKqf.

Sanitizer

Sanity checkers. Check at runtime whether your program has undefined behavior, array out-of-bounds, null pointers, etc. In local debugging mode, enabling some sanitizers is recommended, greatly shortening debug time. These sanitizers are developed by Google and most can be used in GCC and Clang. Sanitizers are more mature in LLVM, so participants are recommended to use Clang compiler locally for debugging.

Address Sanitizer -fsanitize=address

https://clang.llvm.org/docs/AddressSanitizer.html

Both GCC and Clang support this sanitizer. Includes checks for:

Out-of-bounds
Use-after-free
Use-after-return
Double-free
Memory leaks
Use-after-scope

Applying this check slows your program by about 2x.

Undefined Behavior Sanitizer -fsanitize=undefined

https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html

Undefined Behavior Sanitizer (a.k.a UBSan) checks for undefined behavior in code. Both GCC and Clang support this sanitizer. Automatically checks your program for undefined behavior. UBSan checks include:

Bitwise overflow, e.g., 32-bit integer left shift by 72 bits
Signed integer overflow
Floating-point to integer overflow

UBSan checks are optional; impact on program refers to provided web pages.

Miscellaneous

Compiler Explorer

Observe behaviors and assembly of various compilers here: https://godbolt.org

Extended Reading

References and Notes

Remove Deprecated Use of the register Keyword (open-std.org) ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用