Lesson 20.7 — Devirtualization: whole-program, speculative and profile-guided¶

Techniques: whole-program devirtualization (LLVM's WholeProgramDevirt over type metadata: single-implementation devirtualization, virtual constant propagation, uniform and unique return values, branch funnels); speculative devirtualization and indirect-call promotion (type feedback, Hölzle & Ungar 1994; GCC's speculative devirtualization; LLVM's pgo-icall-prom with value profiles) · Pebble implements: nothing in the compiler (Pebble has no virtual calls); the CHA/RTA lab (Lesson 20.1) computes the target sets these transformations start from · Prerequisites: Lesson 20.1 (CHA, closed world); Lesson 20.3 (a direct call can be inlined); profiles (Lesson 20.10, read either first) · Time: 5–6 hours

A virtual call s.area() compiles to: load the object's vtable pointer, load the function pointer from a slot, call it indirectly. The indirect call is cheap on a modern CPU when predicted, but it blocks every interprocedural optimization of this chapter — no inlining, no constant propagation into the callee, no attributes. Devirtualization turns it into a direct call. It is sound when the call graph proves a single target (Lesson 20.1's CHA/RTA in a closed world), and speculative when only a profile or a heuristic says one target is likely — then a guard keeps the indirect call as a fallback. The running example is shapes.cpp:

struct Shape { virtual int area() const = 0; virtual int sides() const = 0; };
struct Circle : Shape { int r; Circle(int r) : r(r) {} int area() const override { return 3 * r * r; }
                        int sides() const override { return 0; } };
struct Square : Shape { int s; Square(int s) : s(s) {} int area() const override { return s * s; }
                        int sides() const override { return 4; } };
struct Log { virtual void put(int v) const; };
void Log::put(int v) const { __builtin_printf("%d\n", v); }
__attribute__((noinline)) int total(const Shape &a, const Shape &b) { return a.area() + b.area(); }
__attribute__((noinline)) int corners(const Shape &a) { return a.sides(); }
__attribute__((noinline)) void report(const Log &l, int v) { l.put(v); }
int main(int argc, char **) {
  Circle c(argc); Square s(argc + 1); Log l;
  report(l, total(c, s) + corners(s));
  return 0;
}

1. Problem and motivation¶

Whole-program devirtualization¶

C++ compilers see one translation unit at a time, where a class hierarchy is never known to be complete: another file may derive from Log and override put. With link-time optimization (Lesson 20.9) and a promise that no code outside the program extends the hierarchy (-fwhole-program-vtables, and hidden visibility or -fvisibility=hidden), the whole hierarchy is known. Clang records it as type metadata — each vtable lists the class types whose vtable layout it is compatible with, and each virtual call is preceded by a llvm.type.test of the loaded vtable pointer against the static type — and LLVM's WholeProgramDevirt resolves each call slot over the compatible vtables [LLVM-TypeMetadata, LLVM-WPD]. With one target it makes the call direct (single-implementation devirtualization); with several targets that all return a constant for the call's constant arguments, it stores those constants next to the vtables and replaces the call by a load (virtual constant propagation); on x86 it can replace a multi-target call with a branch funnel that jumps to the target based on the vtable address. This is CHA (Lesson 20.1) implemented over IR metadata.

Speculative devirtualization and indirect-call promotion¶

When the call graph allows several targets — or the world is open — a compiler can still guess: compare the target with the likely one and call it directly on the fast path. Hölzle and Ungar's type feedback collected receiver types at run time in the SELF system and inlined the frequent ones behind a type test [HU94]; profile-guided C++ compilers do the same from training runs. GCC performs speculative devirtualization even without a profile when its type analysis finds exactly one likely target (-fdevirtualize-speculatively, on at -O2) [GCC-Devirt]; LLVM performs indirect-call promotion (ICP) from the value profiles of instrumented or sampled runs: the most frequent targets of each indirect call site are promoted behind if (fp == @target) guards [LLVM-ICP]. Once direct, the call can be inlined (Lesson 20.3) — which is where most of the speed-up comes from.

2. Definitions and algorithms¶

Definition 20.7.1 (Vtables, slots, type identifiers, compatibility)

A vtable $V$ is a constant array of function pointers; a virtual call through static type $T$ at slot offset $o$ loads the function pointer at $\mathrm{vptr} + o$, where $\mathrm{vptr}$ points to an address point inside some vtable. A type identifier $\mathrm{tid}(T)$ names a class (Itanium mangling _ZTS5Shape). The type metadata !type !{i64 k, !"tid"} on $V$ says that $V$'s address point at offset $k$ is compatible with $\mathrm{tid}$: an object whose dynamic type is a subclass of $T$ may have its vptr there. Let $\mathrm{Compat}(T) = \{(V, k) \mid V \text{ has } !\mathrm{type}\ (k, \mathrm{tid}(T))\}$.

Definition 20.7.2 (Closed type hierarchy)

The hierarchy below $T$ is closed if every object created in any execution whose dynamic type is a subclass of $T$ has its vptr at an address point in $\mathrm{Compat}(T)$ — i.e. no vtable compatible with $T$ exists outside the IR being optimized. Clang asserts this with -fwhole-program-vtables for classes with hidden LTO visibility (!vcall_visibility metadata); the linker can assert it for the whole program (--lto-whole-program-visibility).

Algorithm 20.7.3 (Whole-program devirtualization, per call slot)

Input: a module with type metadata; for each (tid, offset) slot, the call sites type.test(vptr, tid) followed by a load at vptr + offset and a call.
Output: the rewritten call sites and, for virtual constant propagation, extended vtables.
Precondition: the hierarchy below each $T$ is closed (Definition 20.7.2).
Postcondition: each rewritten call executes the function the indirect call would have called (Theorems 20.7.6–20.7.7).
Invariant: $\mathrm{Targets}(T, o) = \{\, \text{function pointer at } V + k + o \mid (V, k) \in \mathrm{Compat}(T) \,\}$ is computed from constant vtable initializers only.

function DevirtModule(M):
    for each slot S = (tid, o) used by some virtual call site:
        Targets ← { load(V + k + o) : (V, k) ∈ Compat(tid) }       # constant initializers
        if |Targets| = 1:                                            # single implementation
            replace every call in S by a direct call of the target; continue
        if every target is readnone, returns an integer, and the call passes only constant arguments:
            for each argument tuple A used at the sites of S:
                R ← { (V, Evaluate(t, A)) : t the target in V }         # run each target at compile time
                if all results equal c:  replace the calls by c            # uniform return value
                else if the type is i1 and exactly one V gives true:
                    replace the calls by (vptr == that V's address point)  # unique return value
                else: store each result in bytes next to its V; replace the calls by a load at vptr + d
                                                                             # virtual constant propagation
            continue
        if the target is x86 and |Targets| ≤ threshold: replace by a branch funnel on vptr

Definition 20.7.4 (Speculative call, promotion)

A speculative (promoted) call of an indirect call r = call %fp(args) for a candidate target $g$ is if (%fp == @g) r1 = call @g(args) else r2 = call %fp(args); r = phi(r1, r2). For a virtual call the test may compare the loaded function pointer (as here) or the vtable pointer against $g$'s vtable. Indirect-call promotion chooses candidates from a value profile: the targets whose count is at least a fraction of the site's total (LLVM: -icp-remaining-percent-threshold, -icp-total-percent-threshold), at most -icp-max-prom of them.

Algorithm 20.7.5 (Indirect-call promotion from a value profile)

Input: an indirect call site $c$ with a value profile $\{(g_i, n_i)\}$ (target, count), total $N$.
Output: a chain of guarded direct calls, most frequent first, ending with the original indirect call.
Precondition: each $g_i$ has a type compatible with the call (otherwise it is skipped).
Postcondition: semantics preserved in every execution (Theorem 20.7.8); branch weights $(n_i, N - n_i)$ attached to each guard.
Invariant: $N$ is reduced by $n_i$ after promoting $g_i$ (the remaining indirect call's profile).

function PromoteIndirectCall(c, profile):
    sort profile by count, descending
    for (g, n) in profile, at most MaxProm times:
        if n < Threshold(N) or not compatible(g, c): break
        c ← SpeculativeCall(c, g) with branch weights (n, N − n)    # Definition 20.7.4; c is the fallback
        N ← N − n

3. Worked example¶

Whole-program devirtualization¶

Type metadata (box in §7): _ZTV6Circle and _ZTV6Square are both compatible with _ZTS5Shape at offset 16 (and with their own class); _ZTV3Log only with _ZTS3Log. The three slots:

call site	slot	$\mathrm{Targets}$	rule	result
`l.put(v)` in `report`	(`_ZTS3Log`, 0)	{`Log::put`}	single implementation	`call @_ZNK3Log3putEi` direct
`a.sides()` in `corners`	(`_ZTS5Shape`, 8)	{`Circle::sides`, `Square::sides`}	both `readnone`, no arguments besides `this`; results 0 and 4	virtual constant propagation: 0 and 4 stored 20 bytes before each address point, the call replaced by `load i32` at `vptr − 20`
`a.area()`, `b.area()` in `total`	(`_ZTS5Shape`, 0)	{`Circle::area`, `Square::area`}	two targets, they read `this->r`/`this->s` (not readnone)	unchanged (a branch funnel is possible on x86 only with `-wholeprogramdevirt-branch-funnel-threshold`)

The constants live in the 8 bytes WPD prepends to each vtable: for Square the bytes 00 00 00 00 04 00 00 00 — the i32 4 at offset 4 — which is exactly 20 bytes before the address point (16 bytes into the vtable proper, which starts 8 bytes after the prefix: $8 + 16 - 20 = 4$).

Speculative devirtualization and indirect-call promotion¶

GCC, no profile (§7): area_of(const Shape &s) with only Circle defined in the unit: the target list is "partial" (other units may define subclasses), with one known target, Circle::area; GCC speculates: if (vfn == Circle::area) inline body else indirect call, with an 80 %/20 % guessed probability.

LLVM, value profile (pgo.c, §7): the indirect call f(x) in apply has the profile {(inc, 999 000), (dbl, 1 000)}, $N = 1\,000\,000$. Algorithm 20.7.5 promotes inc (99.9 % ≥ threshold); dbl's remaining share is below the threshold, so it stays in the fallback. After inlining apply into main, the guard f == inc becomes, through constant folding of the table load, the loop's own test i % 1000 == 999 — both arms become direct calls, with branch weights (1 000, 999 000).

4. Invariants and correctness¶

Theorem 20.7.6 (Single-implementation devirtualization is sound in a closed hierarchy)

If the hierarchy below $T$ is closed and every vtable in $\mathrm{Compat}(T)$ holds the same function $g$ at slot $o$, then replacing a virtual call through $T$ at slot $o$ by a direct call of $g$ preserves behavior.

Proof

Consider an execution reaching the call with object $x$ of dynamic type $C \preceq T$. By the language's rules, $x$'s vptr points to the address point of $C$'s vtable for $T$ (the llvm.type.test + llvm.assume pair records this fact in the IR). By closedness (Definition 20.7.2) that address point is some $(V, k) \in \mathrm{Compat}(T)$. The indirect call calls the pointer stored at $V + k + o$, which is $g$ by hypothesis (vtables are constant, so the stored pointer never changes). A direct call of $g$ with the same arguments performs the same call.

Theorem 20.7.7 (Virtual constant propagation and uniform/unique return values are sound)

Under closedness, if every target $t$ at slot $o$ is readnone, deterministic, returns an integer, and the call passes constant arguments $A$ (besides this, which none of them reads), then for every vtable $V$ the value $r_V = t_V(A)$ can be computed at compile time, and replacing the call by a load of $r_V$ stored at a fixed offset $d$ from each compatible address point preserves behavior.

Proof

As in Theorem 20.7.6, the call executes $t_V(\mathtt{this}, A)$ for the $V$ that vptr points into. A readnone function's result depends only on its arguments; it does not read this's memory (and this itself is not used, else evaluation would be refused), so the result is $t_V(A) = r_V$ in every execution. The pass evaluates each $t_V(A)$ with a constant evaluator; it places $r_V$ at address point + d in a layout where $d$ is the same for all compatible vtables, so the load at vptr + d reads exactly $r_V$. Uniform return values are the case where all $r_V$ are equal (no load needed); unique return value is the case of an i1 result true for exactly one $V$, equivalent to comparing vptr with that $V$'s address point.

Theorem 20.7.8 (Speculative calls are always sound)

Replacing an indirect call by the speculative call of Definition 20.7.4 preserves behavior in every execution, for any candidate $g$, closed world or not.

Proof

In an execution where $\%fp = @g$, the fast path calls $g$ with the same arguments, which is what the indirect call does; otherwise the fallback is the original indirect call. The comparison has no side effects, and the phi delivers the result of whichever call ran. (A profile that is wrong only makes the fast path rare: slower, never wrong.)

Closedness is a promise the programmer makes

-fwhole-program-vtables asserts that no other code — a shared library, a plugin loaded with dlopen — derives from classes with hidden LTO visibility. If one does, Theorem 20.7.6's hypothesis is false and a devirtualized call jumps to the wrong function. Clang therefore applies it only to classes it can prove or is told are hidden; -fsanitize=cfi-vcall uses the same type metadata to check the promise at run time.

5. Complexity¶

$S$ = virtual call sites, $V$ = vtables, $t$ = targets per slot, $P$ = profile entries per site.

Technique	Time (worst)	Time (typical)	Space	Justification
Whole-program devirtualization	$O(S + V \cdot \mathrm{slots})$ + evaluation of $t \times \lvert A \rvert$ calls	linear in the LTO module; evaluation is tiny	extra bytes per vtable for VCP	each slot's target set is read from constant initializers once; each call site is rewritten once
Speculative devirtualization / ICP	$O(S \cdot P \log P)$	linear; `-icp-max-prom` (3) guards per site	one guard + direct call per promotion	sort each site's profile; each promotion splits a block

Pathological family. For VCP: a slot with $t$ targets called with $a$ distinct constant argument tuples needs $t \cdot a$ compile-time evaluations and $a$ extra words per vtable; LLVM bounds the bytes it adds per vtable. For ICP: a megamorphic site with $P$ equally frequent targets never passes the per-target threshold — promotion would add $P$ compares to every call and save nothing, so none is done.

At scale. Whole-program devirtualization is one of the reasons Chromium and other large C++ programs ship with LTO; its effect depends on the program, and the pass's own remarks (-pass-remarks=wholeprogramdevirt) report each devirtualized call — five remarks for the three slots of the running example (§7).

Index-based (ThinLTO) WPD: the same analysis over the summary index (vtable and type-id summaries), then applied in each backend (-wholeprogramdevirt-summary-action); Lesson 20.9.
Speculative WPD without whole-program visibility (-devirtualize-speculatively): speculate on the single target visible in the LTO unit, guarded as in Definition 20.7.4.
Vtable-based ICP (-enable-vtable-value-profiling, -icp-compare-vtable): compare the vtable pointer instead of the loaded function pointer — one load fewer on the fast path.
Type propagation for devirtualization (GCC ipa-polymorphic-call.cc, Java JITs): flow-sensitive tracking of the dynamic type from new/constructors (Lesson 20.1's VTA, flow-sensitive), finding exact types without whole-program assumptions.
Deoptimization-based speculation (HotSpot, V8): speculate on CHA ("only one implementation is loaded") without a guard and deoptimize when class loading breaks the assumption — zero-cost fast path, requires a runtime.
Class hierarchy checks with RTTI (Aigner & Hölzle 1996): the C++ precursor of type-feedback-based promotion.

7. In real compilers¶

Whole-program devirtualization¶

LLVM: llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp — DevirtModule::run groups call sites by (type id, offset); trySingleImplDevirt, tryVirtualConstProp (with tryUniformRetValOpt, tryUniqueRetValOpt, tryEvaluateFunctionsWithArgs) and applyICallBranchFunnel implement the cases of Algorithm 20.7.3 [LLVM-WPD]; llvm/docs/TypeMetadata.rst specifies the metadata [LLVM-TypeMetadata]. GCC: ipa-devirt.cc — possible_polymorphic_call_targets over its type inheritance graph, devirtualizing when the list is complete and has one element [GCC-Devirt].

WholeProgramDevirt: single implementation and virtual constant propagation

Reproduce (clang 23.1.2, opt 23.1.2; shapes.cpp as in the introduction; on Linux the conda-forge toolchain needs --gcc-install-dir=/usr/lib/gcc/x86_64-linux-gnu/14 for the C++ headers — this example includes none, but the driver still wants a GCC installation):

clang++-23 --gcc-install-dir=/usr/lib/gcc/x86_64-linux-gnu/14 -O2 -flto -fwhole-program-vtables -fvisibility=hidden -fno-discard-value-names -S -emit-llvm shapes.cpp -o shapes.ll
grep -E '^@_ZTV6Circle|^!7 =' shapes.ll | cut -c1-110
opt -passes=wholeprogramdevirt -pass-remarks=wholeprogramdevirt -S shapes.ll -o shapes.wpd.ll
sed -n '/define hidden noundef i32 @_Z7corners/,/^}/p;/define hidden void @_Z6report/,/^}/p' shapes.wpd.ll | sed 's/, !tbaa ![0-9]*//; s/ !guid ![0-9]*//'
grep -E '^@1 = ' shapes.wpd.ll | cut -c1-110

Output:

@_ZTV6Circle = linkonce_odr hidden constant { [4 x ptr] } { [4 x ptr] [ptr null, ptr @_ZTI6Circle, ptr @_ZNK6C
!7 = !{i64 16, !"_ZTS5Shape"}
remark: <unknown>:0:0: single-impl: devirtualized a call to _ZNK3Log3putEi
remark: <unknown>:0:0: virtual-const-prop: devirtualized a call to _ZNK6Circle5sidesEv
remark: <unknown>:0:0: devirtualized _ZNK3Log3putEi
remark: <unknown>:0:0: devirtualized _ZNK6Circle5sidesEv
remark: <unknown>:0:0: devirtualized _ZNK6Square5sidesEv
define hidden noundef i32 @_Z7cornersRK5Shape(ptr noundef nonnull align 8 dereferenceable(8) %a) local_unnamed_addr #2 {
entry:
  %vtable = load ptr, ptr %a, align 8
  %0 = tail call i1 @llvm.type.test(ptr %vtable, metadata !"_ZTS5Shape")
  tail call void @llvm.assume(i1 %0)
  %vfn = getelementptr inbounds nuw i8, ptr %vtable, i64 8
  %1 = load ptr, ptr %vfn, align 8
  %2 = getelementptr i8, ptr %vtable, i32 -20
  %3 = load i32, ptr %2, align 4
  ret i32 %3
}
define hidden void @_Z6reportRK3Logi(ptr noundef nonnull align 8 dereferenceable(8) %l, i32 noundef %v) local_unnamed_addr #2 {
entry:
  %vtable = load ptr, ptr %l, align 8
  %0 = tail call i1 @llvm.type.test(ptr %vtable, metadata !"_ZTS3Log")
  tail call void @llvm.assume(i1 %0)
  %1 = load ptr, ptr %vtable, align 8
  tail call void @_ZNK3Log3putEi(ptr noundef nonnull align 8 dereferenceable(8) %l, i32 noundef %v)
  ret void
}
@1 = private constant { [8 x i8], { [4 x ptr] }, [0 x i8] } { [8 x i8] c"\00\00\00\00\04\00\00\00", { [4 x ptr

What to notice: the three rows of §3. report's call is direct (single implementation); corners no longer calls anything — it loads sides()'s result from 20 bytes before the address point, where the new 8-byte prefix of Square's vtable holds 4 (and Circle's holds 0); the dead loads of %vfn are left for later cleanup. total keeps its two indirect calls. With -fvisibility=hidden, clang emits llvm.type.test (not public.type.test), which lets opt run the pass outside a linker.

Speculative devirtualization and indirect-call promotion¶

GCC: ipa-devirt.cc — ipa_devirt makes speculative edges when a call has one likely target (-fdevirtualize-speculatively) [GCC-Devirt]. LLVM: llvm/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp — IndirectCallPromoter::tryToPromoteWithFuncCmp promotes profiled targets (the guard and the branch weights come from promoteIndirectCall in CallPromotionUtils.cpp) [LLVM-ICP].

GCC speculates on the only known subclass

Reproduce (gcc 14.2.0):

cat > spec.cpp <<'EOF'
struct Shape { virtual int area() const = 0; };
struct Circle : Shape { int r; Circle(int r) : r(r) {} int area() const override { return 3 * r * r; } };
__attribute__((noinline)) int area_of(const Shape &s) { return s.area(); }
int main(int argc, char **) { Circle c(argc); return area_of(c); }
EOF
g++-14 -O2 -fdump-ipa-devirt -fdump-tree-optimized -c spec.cpp
grep -E '^  Targets of|partial list|^       virtual int|^Indirect call ->|polymorphic calls,' spec.cpp.*i.devirt
sed -n '/^int area_of/,/^}/p' spec.cpp.*t.optimized | grep -E 'PROF_7 =|if \(PROF|goto <bb [34]>|_11 = MEM'

Output:

  Targets of polymorphic call of type 0:struct Shape token 0
    This is partial list; extra targets may be defined in other units. (derived types included)
       virtual int Circle::area() const/6
Indirect call -> speculative call int area_of(const Shape&)/7 => virtual int Circle::area() const/6
1 polymorphic calls, 0 devirtualized, 1 speculatively devirtualized, 0 cold
  PROF_7 = [obj_type_ref] OBJ_TYPE_REF(_2;(const struct Shape)s_4(D)->0B);
  if (PROF_7 == area)
    goto <bb 3>; [80.00%]
    goto <bb 4>; [20.00%]
  _11 = MEM[(const struct Circle *)s_4(D)].r;

What to notice: the target list is partial (an open world), so GCC cannot devirtualize soundly (Theorem 20.7.6 does not apply) but speculates (Theorem 20.7.8): compare the loaded function pointer with Circle::area, inline its body (r * r * 3) on the 80 % path, keep the indirect call on the other.

LLVM promotes a profiled indirect call

Reproduce (clang 23.1.2, llvm-profdata 23.1.2, and compiler-rt 23.1.2 for the profile runtime — on the course's conda-forge toolchain build the resource directory $RD as in the Ch 12 README, "Tools outside the course toolchain"; elsewhere drop -resource-dir):

cat > pgo.c <<'EOF'
int printf(const char *, ...);
typedef long (*op_t)(long);
__attribute__((noinline)) long inc(long x) { return x + 1; }
__attribute__((noinline)) long dbl(long x) { return 2 * x; }
long apply(op_t f, long x) { return f(x); }
int main(int argc, char **argv) {
  op_t ops[2] = {inc, dbl};
  long s = 0;
  for (long i = 0; i < 1000000; i++)
    s = apply(ops[(i % 1000) == 999], s) % 1000003;   /* inc 99.9% of the time */
  printf("%ld\n", s);
  return 0;
}
EOF
clang-23 --gcc-install-dir=/usr/lib/gcc/x86_64-linux-gnu/14 -resource-dir="$RD" -O2 -fprofile-generate=. pgo.c -o pgo.instr
./pgo.instr
llvm-profdata merge -o pgo.profdata *.profraw
llvm-profdata show --function=main --ic-targets pgo.profdata | grep -A2 'Indirect Target'
clang-23 -O2 -fprofile-use=pgo.profdata -fno-discard-value-names -S -emit-llvm pgo.c -o pgo.use.ll -Rpass=pgo-icall-prom
sed -n '/^define dso_local noundef i32 @main/,/^}/p' pgo.use.ll | grep -E 'br i1 %cmp1|call i64 @(inc|dbl)' | sed -E 's/, !dbg ![0-9]+//'

Output:

265650
    Indirect Target Results:
    [  0, inc,     999000 ] (99.90%)
    [  0, dbl,       1000 ] (0.10%)
pgo.c:5:37: remark: Promote indirect call to inc with count 999000 out of 1000000 [-Rpass=pgo-icall-prom]
    5 | long apply(op_t f, long x) { return f(x); }
      |                                     ^
  br i1 %cmp1, label %call.1, label %if.true.direct_targ, !prof !69
  %0 = tail call i64 @inc(i64 noundef %s.08) #5, !inline_history !70
  %1 = tail call i64 @dbl(i64 noundef %s.08) #5, !inline_history !70

What to notice: the value profile of the one indirect call site (inlined into main in the instrumented build) lists both targets; ICP promotes inc (Algorithm 20.7.5), then inlining apply and constant-folding the ops table turn the guard into i % 1000 == 999 and both arms into direct calls, weighted 1 000 : 999 000.

Find where LLVM does it. Open llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp and find the member function of DevirtModule that devirtualizes a slot with exactly one target. What is its name? (Quiz llvm-where-single-impl.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Whole-program devirtualization	Exact single targets and constant results in a closed hierarchy; no guard	linear in the LTO module · cheap	Remarks per devirtualized call; relies on a programmer promise	High (type metadata in the front end, LTO plumbing)	Clang/LLVM with `-flto -fwhole-program-vtables` (Chromium, Android)
Speculative devirtualization / ICP	Any likely target, open world; a guard keeps the fallback	linear · a compare per promoted target	Branch weights show the expected frequencies; wrong guesses only cost time	Medium (profiles or a heuristic single target)	GCC `-fdevirtualize-speculatively` (-O2), LLVM PGO/AutoFDO (`pgo-icall-prom`), JITs

Choose whole-program devirtualization when you link the whole program with LTO and can promise closed class hierarchies. Choose speculative promotion when the world is open (libraries, plugins) or the call is polymorphic but skewed, and you have a profile (or, as GCC, a single known target).

9. Assessment¶

Quiz (./course quiz 20): wpd-single-impl, llvm-where-single-impl (tag wpd); icp-guard-sound, icp-threshold (tag spec-devirt).
Drill: none specific: the targets that decide single-implementation devirtualization are the CHA/RTA sets of ./course drill cha-rta (a slot with one target in the drill's CHA answer is devirtualizable); speculative promotion is an arithmetic threshold on a profile, asked in icp-threshold.
Flashcards: tags wpd, spec-devirt.
Exercises: none in Pebble (no virtual calls); lab part A computes the target sets.

References¶

See the chapter references.

Technique	Time (worst)	Time (typical)	Space	Justification
Whole-program devirtualization	\(O(S + V \cdot \mathrm{slots})\) + evaluation of \(t \times \lvert A \rvert\) calls	linear in the LTO module; evaluation is tiny	extra bytes per vtable for VCP	each slot's target set is read from constant initializers once; each call site is rewritten once
Speculative devirtualization / ICP	\(O(S \cdot P \log P)\)	linear; `-icp-max-prom` (3) guards per site	one guard + direct call per promotion	sort each site's profile; each promotion splits a block

Lesson 20.7 — Devirtualization: whole-program, speculative and profile-guided¶

1. Problem and motivation¶

Whole-program devirtualization¶

Speculative devirtualization and indirect-call promotion¶

2. Definitions and algorithms¶

3. Worked example¶

Whole-program devirtualization¶

Speculative devirtualization and indirect-call promotion¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

7. In real compilers¶

Whole-program devirtualization¶

Speculative devirtualization and indirect-call promotion¶

8. Comparison¶

9. Assessment¶

References¶