Theory test — Chapter 20¶

63 questions; you pass at 80 %. This page shows the questions only: take the test in the terminal, where every answer is graded and explained.

./course quiz 20                                   # interactive
./course quiz template 20 -o answers/ch20.yaml  # or fill in a file ...
./course quiz grade 20                             # ... and grade it

Question 1 direct-cg-root · set · 1 pt · 01-call-graph-construction

An LLVM module, in module order:

@table = global ptr @b
define internal void @a() { ret void }
define internal void @b() { ret void }
define void @c() { call void @a()  ret void }
declare void @d()
define internal void @e() { ret void }

Which functions does LLVM's CallGraph connect to the external calling node (the root that
stands for "code outside this module may call it")?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 2 llvm-where-callgraph-root · multi · 1 pt · 01-call-graph-construction

In llvm/lib/Analysis/CallGraph.cpp, CallGraph::addToCallGraph decides whether the external calling
node gets an edge to function F. Which conditions does it test (either one suffices)?

F does not have local linkage
F has its address taken (ignoring callback and assume-like uses)
F is a declaration
F is called from main
F is not marked noinline

Answer format: letters, e.g. a, c

Question 3 cha-targets · mapping · 1 pt · 01-call-graph-construction

Lab-language program (Lesson 20.1; choose does not occur):

class Animal
class Dog extends Animal
class Puppy extends Dog
class Cat extends Animal
global pet: Animal
func main    { var a: Animal  var d: Dog  d = new Dog  a = d  k1: a.speak()  pet = a  call vet }
func vet     { var x: Animal  var c: Animal  c = new Cat  x = pet  k2: x.speak()  k3: c.eat() }
func shelter { var p: Dog  p = new Puppy  k4: p.speak() }
method Animal.speak { }     method Animal.eat { k5: this.speak() }
method Dog.speak { }        method Puppy.speak { }
method Cat.speak { }        method Cat.eat { }

Give the CHA targets (Algorithm 20.1.5, reachable from main) of k1, k3, k4 and k5.

Keys: k1, k3, k4, k5

Answer format: one value per key (a set: {x, y})

Question 4 cha-closed-world · single · 1 pt · 01-call-graph-construction

A compiler uses CHA to replace a virtual call s.area() (declared type Shape, one override below
Shape in the program) by a direct call. When is that transformation sound?

Always: CHA is sound by Theorem 20.1.13, whatever code is linked or loaded later
Only if no subclass of Shape can exist outside the code the compiler analyzed (a closed hierarchy: whole program, or classes with hidden visibility)
Only if s is a local variable
Only if Shape.area is declared final

Answer format: one letter

Question 5 rta-targets · mapping · 1 pt · 01-call-graph-construction

Same program as in cha-targets (Animal/Dog/Puppy/Cat; main, vet, shelter). Give the RTA
targets (Algorithm 20.1.6) of k1, k2, k3 and k4.

Keys: k1, k2, k3, k4

Answer format: one value per key (a set: {x, y})

Question 6 rta-edges · number · 1 pt · 01-call-graph-construction

Same program as in cha-targets. CHA reports 14 call edges ($\sum_{\text{sites}} |T(c)|$). How many
edges does RTA report?

Answer format: a number

Question 7 xta-sets · mapping · 1 pt · 01-call-graph-construction

Same program as in cha-targets. Run XTA (Algorithm 20.1.8: one class set per reachable body and
per global; a call passes the receiver class into the target's set). Give the final sets
$S[\mathtt{main}]$, $S[\mathtt{vet}]$, $S[@\mathtt{pet}]$ and $S[\mathtt{Animal.eat}]$.

Keys: main, vet, @pet, Animal.eat

Answer format: one value per key (a set: {x, y})

Question 8 vta-precision · single · 1 pt · 01-call-graph-construction

Same program. XTA gives k3: c.eat() the targets {Animal.eat, Cat.eat}; VTA gives only {Cat.eat}.
Why?

VTA is flow-sensitive: it knows c = new Cat executes before k3
VTA keeps one type set per variable (a type propagation graph), so c only receives Cat, while XTA has one set for the whole body of vet, which also contains Dog from pet
VTA uses the dynamic call graph
VTA ignores globals

Answer format: one letter

Question 9 pta-cg-edges · mapping · 1 pt · 01-call-graph-construction

C code (flow-insensitive, Andersen-style points-to, Ch 19):

void f(void); void g(void); void h(void);
void (*p)(void); void (*q)(void);
void run(void) {
  void (**pp)(void) = &p;
  p = f;
  q = g;
  *pp = h;
  c1: p();
  c2: q();
}

Which functions may each indirect call site call?

Keys: c1, c2

Answer format: one value per key (a set: {x, y})

Question 10 pta-cg-onthefly · single · 1 pt · 01-call-graph-construction

Why is a points-to analysis that builds the call graph on the fly more precise than one that first
builds a CHA call graph and then computes points-to sets over it?

It uses a more precise heap abstraction
It only adds parameter and return constraints for call edges that the points-to sets themselves justify, so bodies that CHA considers reachable but no object reaches contribute no constraints
It is flow-sensitive
It is not more precise, only faster

Answer format: one letter

Question 11 scc-order-calc · mapping · 1 pt · 02-scc-traversal

Call graph in the drill format (f: g h = call sites in order; static = internal; & = address
taken; declare = defined elsewhere):

main: lex parse
static lex:
parse: expr
static expr: term
static term: factor
static factor: expr lex
static &cb: log
declare log
static unused: main

Run Tarjan's algorithm as LLVM's scc_iterator does (root = external calling node, successors in
module order; call sites in order). Give the position (1, 2, …) of each function's SCC in the emitted
bottom-up sequence, for lex, expr, term, factor, parse, main, log, cb.

Keys: lex, expr, term, factor, parse, main, log, cb

Answer format: one value per key

Question 12 llvm-where-scc-done · text · 1 pt · 02-scc-traversal

In llvm/include/llvm/ADT/SCCIterator.h, when scc_iterator emits an SCC it overwrites each member's
visit number so that later min computations ignore it. Which value does it store (as written in the
source)?

Answer format: a short answer

Question 13 bottomup-summary · mapping · 1 pt · 02-scc-traversal

Summary: for each function, the set of external functions it may call, directly or transitively
(a bottom-up summary in the sense of Algorithm 20.2.5). Call graph:

main: parse run
parse: lex
lex: getc
run: eval
eval: apply print
apply: eval
declare getc
declare print

Give the summaries of parse, eval, apply and main.

Keys: parse, eval, apply, main

Answer format: one value per key (a set: {x, y})

Question 14 topdown-norecurse · set · 1 pt · 02-scc-traversal

main is already known norecurse. All other functions are internal and not address-taken; log is
an external declaration (it cannot call back into the module's internal functions).

main: helper walk
static helper: log leaf
static walk: walk2
static walk2: walk leaf
static leaf: log
declare log

Which additional functions does the top-down rule of rpo-function-attrs mark norecurse (a
non-recursive SCC {f} whose callers are all norecurse)?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 15 cgscc-split · mapping · 1 pt · 02-scc-traversal

The CGSCC walk (Algorithm 20.2.7) is visiting the SCC {a, b, c} with call edges a→b, b→c, c→a and
c→b. A function pass simplifies c and deletes its call to a. The update recomputes the SCCs inside
the old one and queues them in postorder. Give, for each of a, b, c, the position (1, 2, …) of its new
SCC in the order the walk visits them.

Keys: a, b, c

Answer format: one value per key

Question 16 cgscc-ref-edges · single · 1 pt · 02-scc-traversal

Why does LLVM's LazyCallGraph keep ref edges (a function merely referencing another, e.g.
storing @g in a table) in addition to call edges?

To compute the inline cost of indirect calls
Because devirtualization can turn a reference into a call; RefSCCs (SCCs over call ∪ ref edges) guarantee that such a promotion never creates a cycle between RefSCCs already visited, so the postorder walk stays valid
Ref edges are only used for dead-code elimination
To make the call graph acyclic

Answer format: one letter

Question 17 inline-knapsack · set · 1 pt · 03-inlining

One caller, four independent call edges, size budget: total growth $\sum \Delta \le 10$.
Benefits and growths $(b, \Delta)$: e1 (7, 6), e2 (5, 5), e3 (5, 5), e4 (2, 1).
Which set of edges maximizes the total benefit (Definition 20.3.3)?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 18 inline-size-rule · mapping · 1 pt · 03-inlining

pebble-inline<size> with $N = 12$ (inline iff the callee has at most 12 counted instructions; no
folding). Three call sites:

small(x): 12 counted instructions;
mode(x, 0): 40 counted instructions, but with mode = 0 a branch folds and only 4 would remain;
big(x): 30 counted instructions, marked alwaysinline.

Which are inlined (yes/no)?

Keys: small, mode, big

Answer format: one value per key

Question 19 inline-cost-lastcall · mapping · 1 pt · 03-inlining

The course cost model (Definitions 20.3.6–20.3.8), no profile, base threshold 225:

define internal @clamp(v, lo)
  entry: 3 instruction(s); cbr (lo == 0), zero, gen
  zero: 2 instruction(s); br done
  gen: 60 instruction(s); br done
  done: 1 instruction(s); ret
call site: @clamp(?, ?)

Give the cost and the decision (yes/no) when this is clamp's only call site
(cost1, inline1), and when the module has two call sites of clamp (cost2, inline2).

Keys: cost1, inline1, cost2, inline2

Answer format: one value per key

Question 20 llvm-where-last-call-bonus · number · 1 pt · 03-inlining

In LLVM 23, InlineCostCallAnalyzer::updateThreshold (llvm/lib/Analysis/InlineCost.cpp) gets the
last-call-to-static bonus from a TTI hook. What does the default implementation
getInliningLastCallToStaticBonus() return?

Answer format: a number

Question 21 mlgo-reward · single · 1 pt · 03-inlining

What signal does MLGO's inlining-for-size policy learn from?

The InlineCost estimate of each call site
The native size of the whole compiled module, known only at the end of compilation — one delayed reward per module, compared with the default policy's size
The run time of a benchmark
Labels written by compiler engineers for each call site

Answer format: one letter

Question 22 mlgo-features · mapping · 1 pt · 03-inlining

MLGO's callsite_height feature is the caller's level in the call graph, computed once per module by
MLInlineAdvisor's constructor over the SCCs bottom-up: a function's level is 1 + the maximum level of
its callees outside its own SCC (0 if there are none), and all members of an SCC share a level. Call graph:

main: parse run
parse: lex
lex:
run: eval
eval: apply
apply: eval

What is callsite_height for a call site located in main, parse, run and apply?

Keys: main, parse, run, apply

Answer format: one value per key

Question 23 funcspec-clones · set · 1 pt · 04-specialization-and-outlining

g(p1, p2) is internal. Its call sites: c1: g(4, x), c2: g(4, 7), c3: g(y, 7), c4: g(5, 7)
(x, y unknown). The specializer creates the clone $g_\varphi$ with $\varphi = \{p_1 \mapsto 4\}$.
Which call sites may be redirected to it (Definition 20.4.1)?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 24 llvm-where-funcspec · text · 1 pt · 04-specialization-and-outlining

In llvm/lib/Transforms/IPO/FunctionSpecialization.cpp, which member function of FunctionSpecializer
decides, for one function, which call sites to specialize for and with which score?

Answer format: a short answer

Question 25 partial-inline-region · set · 1 pt · 04-specialization-and-outlining

g's CFG: entry → early, rest; early → exit; rest → loop; loop → loop, done; done → exit;
exit returns. entry tests a cheap condition and early has no side effects. Which blocks does the
partial inliner (Algorithm 20.4.5) outline into $g_{\mathrm{slow}}$?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 26 partial-inline-why · single · 1 pt · 04-specialization-and-outlining

Why is partial inlining worthwhile for a function of the form
if (cache_valid) return cached; ...expensive computation...?

It makes the expensive computation faster
The common case (the early return) runs inline without a call, while the large slow path is not duplicated at every call site: the benefit of inlining at a fraction of the size
It removes the function from the program
It converts the function into a loop

Answer format: one letter

Question 27 outline-benefit · number · 1 pt · 04-specialization-and-outlining

A repeated sequence of $\ell = 5$ instructions occurs $k = 4$ times without overlap. A call costs
$\kappa_c = 1$ instruction per occurrence and the outlined function adds $\kappa_f = 1$ (its return).
What is the benefit $b(w)$ in instructions (Definition 20.4.6)?

Answer format: a number

Question 28 hotcold-cold-blocks · set · 1 pt · 04-specialization-and-outlining

No profile. CFG of f: entry → check; check → ok, err; ok: ret; err: call @report(); br fatal;
fatal: call @abort() (noreturn); unreachable. Which blocks does hot/cold splitting's static rule
consider cold (Algorithm 20.4.8: a block is cold if every path from it leads to cold code)?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 29 ipsccp-return · number · 1 pt · 05-interprocedural-analysis

static int version(void) { return 3; }
static int limit(int level) { return level > 2 ? 64 : 16; }
int size(void) { return limit(version()) * 2; }

Both static functions have only these call sites. After IPSCCP, which constant does size return?

Answer format: a number

Question 30 llvm-where-ipsccp · text · 1 pt · 05-interprocedural-analysis

In llvm/lib/Transforms/IPO/SCCP.cpp, which static function implements the module-level IPSCCP driver
called from IPSCCPPass::run?

Answer format: a short answer

Question 31 summary-vs-callstring · single · 1 pt · 05-interprocedural-analysis

Compare the functional (summary-based) approach with $k$-limited call strings (Sharir & Pnueli) for a
distributive problem over a finite domain. Which statement is right?

Call strings with k = 1 always compute the meet over valid paths
Summaries (as in IFDS) compute the meet over valid paths exactly; k-limited call strings merge contexts that differ beyond depth k and can lose precision on deeper call chains
Summaries are always less precise than call strings
Both are equally precise but call strings are cheaper

Answer format: one letter

Question 32 context-insensitive-spurious · set · 1 pt · 05-interprocedural-analysis

Taint analysis (the drill's rules):

proc main():
  n1: a = source()
  n2: b = 0
  n3: x = call f(a, b)
  n4: y = call f(b, a)
  n5: sink(x)
  n6: return y
proc f(p, q):
  n7: r = q
  n8: return r

A context-insensitive analysis (every return of f flows to every call site) and IFDS disagree before
n5. Which variables does the context-insensitive analysis report as tainted there that IFDS does not?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 33 ifds-path-edges · mapping · 1 pt · 05-interprocedural-analysis

Same program as in context-insensitive-spurious. Run IFDS tabulation (Algorithm 20.5.4). Give the
facts (tainted variables) that hold before n4, n5, n7 and n8 (a callee's nodes collect the
facts of all its calling contexts).

Keys: n4, n5, n7, n8

Answer format: one value per key (a set: {x, y})

Question 34 ide-linear · number · 1 pt · 05-interprocedural-analysis

IDE, linear constant propagation (Definition 20.5.5). main: n1 x = 2; n2 y = call f(x); n3 z = call f(y)
and f(p): r = 3*p - 1; return r. The jump function of f from $p$ to $r$ is $\lambda v.\,3v - 1$.
What constant does IDE compute for z?

Answer format: a number

Question 35 funcattrs-memory · mapping · 1 pt · 06-attributes-and-signatures

Drill format (f [e]: g h = own memory effect e and calls; declare with known attributes):

f [read]: g
g [none]: f len
h [write]:
k [none]: g
m [none]: m
p [none]: h
declare len readonly norecurse

Give each defined function's inferred memory effect (none, read or write) by Algorithm 20.6.5.

Keys: f, g, h, k, m, p

Answer format: one value per key

Question 36 llvm-where-norecurse · text · 1 pt · 06-attributes-and-signatures

In llvm/lib/Transforms/IPO/FunctionAttrs.cpp, addNoRecurseAttrs calls a helper to decide whether
any call in the (single-function) SCC may lead back to the function. What is the helper's name?

Answer format: a short answer

Question 37 dae-dead-args · set · 1 pt · 06-attributes-and-signatures

static int g(int x, int y) { return x + 1; }
static int f(int a, int b, int c) { return g(b, a); }
int main(void) { return f(1, 2, 3); }

Which parameters are dead (Definition 20.6.7)? Name them f.a, f.b, f.c, g.x, g.y.

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 38 dae-conditions · multi · 1 pt · 06-attributes-and-signatures

Which conditions must a function satisfy for dead-argument elimination to change its signature
(Algorithm 20.6.8)?

Local (internal) linkage
Its address is not taken (every call site is a known direct call)
No musttail call uses it
It is norecurse
It has no loops

Answer format: letters, e.g. a, c

Question 39 argpromotion-conditions · multi · 1 pt · 06-attributes-and-signatures

Argument promotion replaces a pointer parameter p of an internal function by the values loaded from
it. Which conditions does Algorithm 20.6.9 require?

Every use of p is a load at a constant offset (possibly through a GEP)
Nothing in the function (or its callees) may write those locations before the loads
Each loaded location is dereferenceable at every call site, so loading it early cannot trap
p is marked noalias
The function has exactly one call site

Answer format: letters, e.g. a, c

Question 40 argpromotion-parts · number · 1 pt · 06-attributes-and-signatures

Internal int f(struct S *p, int k) whose only uses of p are loads of i32 at offset 0 (twice)
and i32 at offset 8; all conditions of Algorithm 20.6.9 hold. How many parameters does the promoted
function have?

Answer format: a number

Question 41 globalopt-rules · mapping · 1 pt · 06-attributes-and-signatures

All globals are internal i32s whose address does not escape unless stated. Which GlobalOpt rule of
Algorithm 20.6.10 applies to each (constant, delete, shrink, localize, none)?

g1 = 42: only loaded.
g2 = 0: stored to, never loaded.
g3 = 0: loaded; the only value ever stored is 7.
g4 = 0: loaded and stored with many values, only inside main, which is norecurse.
g5 = 0: its address is passed to an external function.

Keys: g1, g2, g3, g4, g5

Answer format: one value per key

Question 42 globalopt-sra · single · 1 pt · 06-attributes-and-signatures

An internal global @s = global { i32, i64, i32 } is only accessed through constant-index GEPs to
fields 0 and 2, and its address does not escape. What does GlobalOpt's SRA rule do?

Nothing: aggregates are never split
It replaces @s by one global per accessed field (@s.0, @s.2); field 1 is never accessed and disappears
It turns @s into an alloca in main
It makes @s constant

Answer format: one letter

Question 43 wpd-single-impl · mapping · 1 pt · 07-devirtualization

Closed hierarchy, whole-program devirtualization (Algorithm 20.7.3). Four slots with their targets:

s1 (Parser, 16): {JsonParser::parse}.
s2 (Node, 0): {Leaf::kind, Inner::kind}, both readnone, both return 1, called with no arguments besides this.
s3 (Node, 8): {Leaf::isLeaf → true, Inner::isLeaf → false}, readnone, return i1.
s4 (Node, 24): {Leaf::size, Inner::size}, both read fields of this.

Which rule applies (single, uniform, unique, vcp, none)?

Keys: s1, s2, s3, s4

Answer format: one value per key

Question 44 llvm-where-single-impl · text · 1 pt · 07-devirtualization

In llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp, which member function of DevirtModule
devirtualizes a slot with exactly one target?

Answer format: a short answer

Question 45 icp-guard-sound · single · 1 pt · 07-devirtualization

Indirect-call promotion rewrites call %fp(x) into if (%fp == @inc) call @inc(x) else call %fp(x).
Why is this correct even if the profile was stale or wrong?

Because the profile is always accurate
Because the guard compares the actual pointer: the direct call runs only when %fp is @inc, and every other target still takes the original indirect call
Because @inc is readnone
It is not correct with a wrong profile

Answer format: one letter

Question 46 icp-threshold · set · 1 pt · 07-devirtualization

A value profile for one indirect call site: A 800, B 150, C 40, D 10 (total $N = 1000$). LLVM's
rule: promote targets in decreasing count while $100 \cdot n \ge 30 \cdot \text{remaining}$ and
$100 \cdot n \ge 5 \cdot N$ (remaining = count not yet promoted), at most 3. Which targets are promoted?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 47 tce-position · set · 1 pt · 08-tail-calls

Which calls to b are in tail position (Definition 20.8.1), after mem2reg?

int  b(int);
int  f1(int x) { return b(x); }                /* c1 */
int  f2(int x) { int r = b(x); return r; }     /* c2 */
int  f3(int x) { return b(x) + 1; }            /* c3 */
void f4(int x) { b(x); }                       /* c4 */
int  f5(int x) { if (x) return b(x); return 0; } /* c5 */

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 48 tce-escape · single · 1 pt · 08-tail-calls

int f(int n) { int buf[4]; fill(buf); return g(n); } — why may LLVM not mark g(n) tail, although
it is in tail position?

Because g may be recursive
Because buf's address escapes (to fill), so g might access f's frame through a saved pointer; a tail call would free that frame before g runs
Because f returns an int
Because tail calls are only allowed for self-recursion

Answer format: one letter

Question 49 tre-accumulator-trace · sequence · 1 pt · 08-tail-calls

int sum(int n) { return n == 0 ? 0 : n + sum(n - 1); } after TRE with an accumulator
(Algorithm 20.8.4, $\oplus = $ add, identity 0). Give the value of accumulator.tr at each visit of
the loop header tailrecurse for sum(4), in order.

Answer format: items in order, e.g. A B C

Question 50 tre-must-not · mapping · 1 pt · 08-tail-calls

Does pebble-tre (and LLVM's tailcallelim) eliminate the recursive call (yes/no)?

int f1(int n) { return n == 0 ? 0 : f1(n - 1) + n; }
int f2(int n) { return n == 0 ? 1 : 2 * f2(n - 1) + 1; }
int f3(int n) { return n == 0 ? 0 : n - f3(n - 1); }
int f4(int n, int *p) { int t = n; if (n == 0) return *p; return f4(n - 1, &t); }
int f5(int n, int a) { return n == 0 ? a : f5(n - 1, a ^ n); }

Keys: f1, f2, f3, f4, f5

Answer format: one value per key

Question 51 llvm-where-tre-accumulator · multi · 1 pt · 08-tail-calls

In llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp, canTransformAccumulatorRecursion(I, CI)
first tests two properties of the instruction I after the recursive call. Which?

I is associative
I is commutative
I has the nsw flag
I is an add
I is in the entry block

Answer format: letters, e.g. a, c

Question 52 lto-internalize · set · 1 pt · 09-lto-and-thinlto

Monolithic LTO of main.o and lib.o into an executable. Resolutions (p = prevailing, x = visible
to regular objects): main.o: main px, helper p, printf undefined; lib.o: scale p, api px
(exported to a plugin through the dynamic symbol table), dead p. Which symbols does the LTO step
internalize (Definition 20.9.2)?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 53 lto-resolution · single · 1 pt · 09-lto-and-thinlto

Why must the linker, not the compiler, tell LTO which symbols are visible to regular objects?

Because the compiler does not know the symbol names
Because only the linker sees every object file, archive and the export list; a symbol referenced from a native object, assembly or the dynamic symbol table must keep external linkage, or internalization would break the program
Because the linker runs the optimizer
It does not matter who decides

Answer format: one letter

Question 54 thinlto-import-chain · set · 1 pt · 09-lto-and-thinlto

ThinLTO, Algorithm 20.9.5 with $L = 100$, $\alpha = 0.7$, no profile. Module A's main calls f
(80 instructions, in module B); f calls g (75, in C); g calls h (30, in D). Which functions are
imported into A?

Answer format: items separated by commas or spaces, e.g. {a, b}

Question 55 llvm-where-import-factor · text · 1 pt · 09-lto-and-thinlto

In llvm/lib/Transforms/IPO/FunctionImport.cpp, which command-line option multiplies the import
threshold by 0.7 at each level of an import chain? (Give the option name without the leading dash.)

Answer format: a short answer

Question 56 ipgo-counters · number · 1 pt · 10-profile-guided-optimization

A function's CFG has blocks entry, header, body, then, else, join, exit and edges
entry→header, header→body, header→exit, body→then, body→else, then→join, else→join, join→header, then→exit. With the virtual edge exit→entry added, how many counters does spanning-tree
instrumentation (Knuth–Stevenson, as in LLVM's IR PGO) need?

Answer format: a number

Question 57 ipgo-context-scaling · number · 1 pt · 10-profile-guided-optimization

g(p) { if (p) A else B } is called 900 times from site $k_1$, always with p = 1, and 100 times from
site $k_2$, always with p = 0. Its context-insensitive profile is inlined at $k_1$ with scaled counts
(Theorem 20.10.4). What count does the inlined copy at $k_1$ give the edge into B (the true count is 0)?

Answer format: a number

Question 58 llvm-where-pgo-mst · single · 1 pt · 10-profile-guided-optimization

The header of llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp cites the paper behind its
counter placement and names the class that computes the spanning tree. Which pair is right?

Ball & Larus 1996 (path profiling); BallLarusDag
Knuth & Stevenson 1973 (optimal measurement points); CFGMST
Pettis & Hansen 1990; CodeLayout
Tarjan 1972; scc_iterator

Answer format: one letter

Question 59 autofdo-block-weight · mapping · 1 pt · 10-profile-guided-optimization

A sample profile gives, per line offset: 1 → 900, 2 → 900, 3 → 120, 4 → 80, 5 → 780 (no record for 7).
Blocks and the line offsets of their instructions: B1 {1, 2}, B2 {3, 4}, B3 {5, 5}, B4 {7}.
Give each block's weight by Definition 20.10.3 (none if it has no weight).

Keys: B1, B2, B3, B4

Answer format: one value per key

Question 60 autofdo-line-offsets · single · 1 pt · 10-profile-guided-optimization

Why do AutoFDO sample profiles key counts by the line offset from the function's first line (plus
a discriminator) rather than by absolute line numbers?

Offsets are smaller numbers, so the profile is shorter
Edits above the function (other functions, comments) shift absolute lines but not offsets, so the profile stays usable across source changes; the discriminator separates several blocks on one line
Because the binary has no line information
To make the profile context-sensitive

Answer format: one letter

Question 61 bolt-ph-order · sequence · 1 pt · 10-profile-guided-optimization

Algorithm 20.10.6 (Pettis–Hansen function ordering; edges in decreasing weight; for $u \in A$, $v \in B$
choose among $AB$, $AB^r$, $A^rB$, $A^rB^r$ the first one that minimizes the distance between $u$ and
$v$). Weights: loop–step 500, main–loop 40, main–init 30, init–log 20, step–log 5, main–fini 1.
Give the final order.

Answer format: items in order, e.g. A B C

Question 62 bolt-ph-not-optimal · mapping · 1 pt · 10-profile-guided-optimization

Weights $w(a,b) = 5$, $w(a,d) = 4$, $w(b,d) = 3$, $w(a,c) = 2$ (unit-size functions,
$\Phi = \sum w(u,v)\,|\mathrm{pos}(u) - \mathrm{pos}(v)|$). Give $\Phi$ of the order Algorithm 20.10.6
produces (ph) and the optimal $\Phi$ (opt).

Keys: ph, opt

Answer format: one value per key

Question 63 postlink-why · single · 1 pt · 10-profile-guided-optimization

A server binary is already built with PGO and ThinLTO. Why can a post-link optimizer (BOLT, Propeller)
still make it faster?

It re-runs the inliner with a larger threshold
It lays out the code of the final linked binary — including code from other units and libraries the compiler never saw together — from a profile of that exact binary, improving i-cache and TLB locality (block order, hot/cold splitting, function order)
It removes the PGO instrumentation
It vectorizes loops the compiler missed

Answer format: one letter