Use Profile-Guided Optimization (PGO) to Improve Performance

Topic Overview

Train the Compiler With Real Profiles

Profile-Guided Optimization (PGO) runs a instrumented binary on representative input, records edge frequencies, then rebuilds with fprofile-use so the compiler lays out hot branches and inlines the right callees. Chrome, Firefox, and LLVM itself ship PGO-trained builds.

Two-Phase Flow

Phase 1: -fprofile-generate run workload. Phase 2: -fprofile-use recompile using .profraw merged to .profdata.

bashCopy
Loading…

• Training input must resemble production or hot paths mislead layout
• Cold error paths should stay cold in the profile
• LTO plus PGO compounds gains on large binaries
• BOLT can optimize further on top of PGO binaries

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will generate and consume a profile to build a PGO-optimized binary. This exercise requires comparing branch layout or speed against a non-PGO build.

Your Task

Profile-guided optimisation feeds real branch counts back into the compiler. One of its biggest wins is basic-block layout: put each block right after its most likely predecessor, so the hot path falls through instead of jumping, and push never-executed blocks (error handling) out of the way. Implement the classic Pettis. Hansen greedy chain-merging layout, and compare it against source order.

Input

cCopy
Loading…

Rules

• Execution count of a block = the sum of its incoming edge counts. For the entry block, use its outgoing sum if that is larger.
• Pettis: Hansen:
  1. Every block starts as its own chain. Visit edges from the heaviest count down (stable on ties). Skip edges with count 0 and edges into the entry.
  2. Join A -> B only if A is the tail of its chain, B is the head of its chain, and they are different chains. The chain of B is appended to the chain of A.
  3. Emit the chain containing the entry first. Then repeatedly emit the remaining chain whose hottest block has the largest execution count, breaking ties by the chain head's source order.
• Cost of a layout: an edge whose target is placed directly after its source is a fall-through, and every other edge execution is a taken branch. Also report the bytes of executed blocks, and the span from the first executed block to the end of the last one.
• Errors: block NAME: rejected (duplicate, size < 1, or more than 32 blocks), edge A B: rejected, edge A B: a block has at most two successors, and entry NAME: no such block.

Output

cCopy
Loading…

The percentage is rounded half up to 1 decimal with integer arithmetic.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Merge chains only tail-to-head, so every chain stays a straight-line sequence that can really be laid out.
2. Derive every number from the edge profile. Never special-case block names like "error".

Hidden tests cover an if/else diamond with a biased branch, a different entry block, a chain that cannot grow because its tail already has a successor, ties between equally hot chains, a block with three successors, and unknown blocks.