Theory test — Chapter 9¶

67 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 9                                   # interactive
./course quiz template 9 -o answers/ch09.yaml  # or fill in a file ...
./course quiz grade 9                             # ... and grade it

Question 1 module-components · set · 1 pt · 01-modules-globals-functions

A module, in full:

target triple = "x86_64-unknown-linux-gnu"
%struct.P = type { i32, i32 }
@g = global i32 0
@s = private unnamed_addr constant [3 x i8] c"hi\00"
@a = alias i32, ptr @g
$grp = comdat any
declare i32 @puts(ptr)
define i32 @main() {
  %r = call i32 @puts(ptr @s)
  ret i32 %r
}
!llvm.ident = !{!0}
!0 = !{!"hand-written"}

Give the set of global values \(\mathcal{GV}(M)\) of Definition 9.1.1, i.e. the names
in the module's symbol table. Write the names without the @ sigil.

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

Question 2 find-undefined-global · text · 1 pt · 01-modules-globals-functions

Find where LLVM does it (Lesson 9.1 §7, llvm/lib/AsmParser/LLParser.cpp). A module
contains call void @nope() in a function body, and @nope is neither declared nor
defined anywhere in the module. Which error message does llvm-as print (quote it without
the file position)?

Answer format: a short answer

Question 3 linkage-resolution · mapping · 1 pt · 01-modules-globals-functions

Three modules are linked in the order m1, m2, m3 (llvm-link m1.ll m2.ll m3.ll),
and a function in m1 loads from all four names, so nothing is dropped as unused.

name	`m1.ll`	`m2.ll`	`m3.ll`
`@x`	`weak global i32 1`	`linkonce global i32 2`	`external global i32` (declaration)
`@y`	`common global [2 x i32] zeroinitializer`	`common global [4 x i32] zeroinitializer`	`weak global i32 6`
`@z`	`external global i32` (declaration)	`available_externally global i32 3`	`linkonce_odr global i32 3`
`@w`	`global i32 4` (external definition)	`weak global i32 5`	`common global i32 0`

Run Algorithm 9.1.4 for each name. Which module's definition does the linked module
keep? Answer x: m1 style.

Keys: x, y, z, w

Answer format: one value per key

Question 4 linkage-discardable · set · 1 pt · 01-modules-globals-functions

Six functions, all dso_local, each with a body:

function	linkage
`f1`	`weak`
`f2`	`linkonce_odr`
`f3`	`internal`
`f4`	`external`
`f5`	`linkonce`
`f6`	`available_externally`

Which of them may the optimizer both inline into a caller and delete once no
call is left? (Use Definition 9.1.2.)

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

Question 5 find-discardable · set · 1 pt · 01-modules-globals-functions

Find where LLVM does it (Lesson 9.1 §7). In llvm/include/llvm/IR/GlobalValue.h,
GlobalValue::isDiscardableIfUnused(LinkageTypes) is a disjunction of three linkage
predicates. Give the set of linkages for which it returns true (spell them as in the
IR, e.g. linkonce_odr).

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

Question 6 slot-numbering · mapping · 1 pt · 01-modules-globals-functions

The parser of LLVM 23 accepts this text (the entry block has no label):

define i32 @f(i32, i32 %y) {
  %3 = add i32 %0, %y
  %cmp = icmp sgt i32 %3, 0
  br i1 %cmp, label %7, label %done
7:
  %9 = mul i32 %3, 2
  br label %done
done:
  %12 = phi i32 [ %3, %1 ], [ %9, %7 ]
  ret i32 %12
}

llvm-as | llvm-dis prints it again with Algorithm 9.1.7. Which number does each of the
following get in the printed text? Answer %3: %N style (for the block, 7: N).

Keys: %3, 7, %9, %12

Answer format: one value per key

Question 7 ssa-def-count · number · 1 pt · 01-modules-globals-functions

A C fragment (all variables are int locals; a, b, c are parameters):

int x = a + b;
x = x * 2;
if (c) x = x - 1;
return x;

After clang -O0 and mem2reg (minimal SSA), how many distinct SSA values stand for
the C variable x, counting phis?

Answer format: a number

Question 8 signless-integers · set · 1 pt · 02-type-system-and-data-layout

Operations on i8 values, without flags. For which of them is the result bit pattern
the same whether the operands are read as unsigned or as two's-complement signed numbers
— i.e. which need no signed/unsigned twin?

add, mul, udiv, shl, lshr, xor, icmp ult, trunc to i4, zext to i16

Answer format: set of operation names, e.g. {add, udiv}; write `trunc` and `zext` without the target type

Question 9 opaque-pointer-consequence · single · 1 pt · 02-type-system-and-data-layout

define double @pun(ptr %p) {
  %i = load i64, ptr %p
  %d = load double, ptr %p
  ret double %d
}

What does LLVM 23 say about this function?

It is rejected: %p was first used as a pointer to i64, so loading a double through it needs a bitcast.
It is valid: a ptr has no pointee type, and each load names the type it reads.
It is valid only if %p is declared ptr addrspace(0) explicitly.
It is valid, and the type-based alias analysis concludes from the two load types that the loads cannot alias.

Answer format: one letter

Question 10 struct-layout-x86 · mapping · 1 pt · 02-type-system-and-data-layout

On x86-64 (target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"):

%T = type { i16, i64, i8, <4 x float>, i8 }

Give the byte offset of each field (f0 … f4), the struct's alloc size (size) and
its ABI alignment (align).

Keys: f0, f1, f2, f3, f4, size, align

Answer format: one value per key

Question 11 literal-vs-identified · number · 1 pt · 02-type-system-and-data-layout

A module declares

%A = type { i32, ptr }
%B = type { i32, ptr }

and its functions use, among others, the types { i32, ptr } (in two different
functions), <{ i32, ptr }> and %A. How many distinct struct type objects does the
context hold for these (Definition 9.2.3 and Algorithm 9.2.4)?

Answer format: a number

Question 12 scalable-size · number · 1 pt · 02-type-system-and-data-layout

An Arm SVE machine has 384-bit vector registers, so vscale = 3 for the whole run.
How many bytes does store <vscale x 2 x double> %v, ptr %p write?

Answer format: a number

Question 13 vector-alloc · mapping · 1 pt · 02-type-system-and-data-layout

On x86-64 (no v96 entry in the data layout), give for <3 x i32> its store size
(store), ABI alignment (align) and alloc size (alloc) in bytes, and the offset of
the vector field in { i8, <3 x i32> } (field).

Keys: store, align, alloc, field

Answer format: one value per key

Question 14 token-phi · multi · 1 pt · 02-type-system-and-data-layout

Which of these are rejected by LLVM 23 (by the parser or by the verifier)?

%t = phi token [ %t1, %entry ], [ %t1, %a ]
define void @f(label %l) { ret void }
define token @g() { ret token none }
define void @h(target("spirv.Image", float, 1, 0, 0, 0, 0, 0, 0) %img) { ret void }
%t = select i1 %c, token %t1, token %t1
%t = call token @llvm.experimental.convergence.entry() in a convergent function

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

Question 15 find-token-check · text · 1 pt · 02-type-system-and-data-layout

Find where LLVM does it (Lesson 9.2 §7). In llvm/lib/IR/Verifier.cpp, the check
that rejects token-typed phis prints "PHI nodes cannot have token type!". In which
Verifier::visit… member function is it?

Answer format: a short answer

Question 16 datalayout-i686 · mapping · 1 pt · 02-type-system-and-data-layout

On 32-bit x86 Linux the data layout is
"e-m:e-p:32:32-p270:32:32-p271:32:32-p272:64:64-i128:128-f64:32:64-f80:32-n8:16:32-S128".

%R = type { i16, double, i32, i64 }

Give the byte offsets of the double (d), the i32 (i) and the i64 (q), and
the alloc size of %R (size).

Keys: d, i, q, size

Answer format: one value per key

Question 17 datalayout-default-i64 · mapping · 1 pt · 02-type-system-and-data-layout

What is the alloc size in bytes of { i32, i64 } under the empty data layout
(target datalayout absent, all defaults of Definition 9.2.5), and under the x86-64
layout (which contains i64:64)? Answer empty: N and x86_64: N.

Keys: empty, x86_64

Answer format: one value per key

Question 18 switch-successors · mapping · 1 pt · 03-control-flow-and-ssa

entry:
  switch i8 %c, label %d [ i8 1, label %a
                           i8 2, label %b
                           i8 3, label %a
                           i8 4, label %d ]

Blocks a, b and d each start with a phi and have no predecessor other than
entry. How many entries ([ v, %entry ] pairs) must each of the three phis have for
the verifier to accept the function?

Keys: a, b, d

Answer format: one value per key

Question 19 invoke-normal-edge · set · 1 pt · 03-control-flow-and-ssa

entry:
  %call = invoke i32 @r(i32 %x) to label %cont unwind label %lpad
cont:
  br label %join
lpad:
  %lp = landingpad { ptr, i32 } cleanup
  br label %join
join:
  %p = phi i32 [ %call, %cont ], [ 0, %lpad ]
  ret i32 %p

In which of the blocks entry, cont, lpad, join may a non-phi instruction
(say %u = add i32 %call, 1, placed before the block's terminator) use %call?

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

Question 20 find-switch-table · text · 1 pt · 03-control-flow-and-ssa

Find where LLVM does it (Lesson 9.3 §7). simplifySwitchLookup in
llvm/lib/Transforms/Utils/SimplifyCFG.cpp turns
switch (op) { case 0: return 10; case 1: return 20; case 7: return 30; default: __builtin_unreachable(); }
into a constant table indexed by op. What does the table hold at the indices 2–6,
which no case lists? (One word.)

Answer format: a short answer

Question 21 phi-parallel · mapping · 1 pt · 03-control-flow-and-ssa

loop:
  %x = phi i32 [ 1, %entry ], [ %y, %loop ]
  %y = phi i32 [ 2, %entry ], [ %x, %loop ]
  %z = phi i32 [ 0, %entry ], [ %s, %loop ]
  %s = add i32 %x, %z
  ...
  br i1 %again, label %loop, label %done

Give the values of %x, %y and %z at the start of the third execution of
loop (the first comes from entry).

Keys: x, y, z

Answer format: one value per key

Question 22 select-poison · mapping · 1 pt · 03-control-flow-and-ssa

With %x = add i32 5, 0, what does each select evaluate to? Answer an integer or
poison.

%r1 = select i1 true,   i32 %x,     i32 poison
%r2 = select i1 poison, i32 1,      i32 1
%r3 = select i1 false,  i32 %x,     i32 poison
%r4 = select i1 true,   i32 poison, i32 %x

Keys: r1, r2, r3, r4

Answer format: one value per key

Question 23 branch-to-select · multi · 1 pt · 03-control-flow-and-ssa

A diamond br i1 %c, label %t, label %e joins with %r = phi [ %v, %t ], [ %w, %e ].
Arm %t contains a single instruction computing %v, arm %e just branches with
%w = %x. For which contents of %t may simplifycfg hoist it into the branching
block and replace the phi by select i1 %c, i32 %v, i32 %x (Proposition 9.3.10)?
Nothing is known about %x, %y, %n or %p.

%v = add nsw i32 %x, 1
%v = sdiv i32 %x, %y
%v = load i32, ptr %p (nothing known about %p)
%v = udiv i32 %x, 7
%v = call i32 @log_and_get()
%v = shl i32 %x, %n

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

Question 24 verifier-rule-of-error · mapping · 1 pt · 03-control-flow-and-ssa

Name the rule of Definition 9.3.4 (W1–W7) that each LLVM 23 message reports:

m1: "Entry block to function must not have predecessors!"
m2: "PHI nodes not grouped at top of basic block!"
m3: "PHINode should have one entry for each predecessor of its parent basic block!"
m4: "Only PHI nodes may reference their own value!"
m5: "'%c' defined with type 'i32' but expected 'i1'" (at a br i1 %c, …)
m6: "Instruction does not dominate all uses!"

Keys: m1, m2, m3, m4, m5, m6

Answer format: one value per key

Question 25 dominance-use · set · 1 pt · 03-control-flow-and-ssa

CFG (entry A; G has no predecessors and is unreachable):

A -> B, C
B -> D
C -> D
D -> E, F
E -> D
G -> F

%v is defined in D (not as a phi). In which blocks may a non-phi instruction use
%v without violating W6? (For D itself, assume the use comes after the definition.)

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

Question 26 find-phi-dup-check · single · 1 pt · 03-control-flow-and-ssa

Find where LLVM does it (Lesson 9.3 §7). In llvm/lib/IR/Verifier.cpp, the message
"PHI node has multiple entries for the same basic block with different incoming
values!" is emitted by visitBasicBlock. Which rule of Definition 9.3.4 does it enforce?

W3: phis come before all other instructions.
W4: one entry per incoming edge, and entries for the same predecessor carry the same value.
W6: every use is dominated by its definition.
W2: the entry block has no predecessors.

Answer format: one letter

Question 27 promotable-alloca · set · 1 pt · 04-memory-and-addresses

@gp = global ptr null
declare void @use(ptr)
define i32 @f(i32 %x, float %y) {
entry:
  %a = alloca i32
  %b = alloca i32
  %c = alloca i32
  %d = alloca [2 x i32]
  %e = alloca i32
  %f = alloca ptr
  %h = alloca i32
  store i32 %x, ptr %a
  %va = load i32, ptr %a
  store i32 %x, ptr %b
  call void @use(ptr %b)
  store volatile i32 %x, ptr %c
  %vc = load i32, ptr %c
  %d1 = getelementptr [2 x i32], ptr %d, i64 0, i64 1
  store i32 %x, ptr %d1
  store i32 %x, ptr %e
  %ve = load atomic i32, ptr %e monotonic, align 4
  store ptr %f, ptr @gp
  store float %y, ptr %h
  %vh = load i32, ptr %h
  ...

Which allocas does opt -passes=mem2reg promote to SSA values? (Names without %.)

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

Question 28 find-promotable-volatile · single · 1 pt · 04-memory-and-addresses

Find where LLVM does it (Lesson 9.4 §7). In
llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp, isAllocaPromotable walks the
users of an alloca. What does it do with a volatile load of the alloca?

Accepts it: the volatile flag is dropped because the slot is private to the function.
Rejects the alloca: if (LI->isVolatile()) return false;.
Accepts it but keeps the load, turning only the other accesses into SSA values.
Accepts it if the load is also atomic.

Answer format: one letter

Question 29 hoist-plain-load · mapping · 1 pt · 04-memory-and-addresses

int flag, counter; void ext(void); are globals. For each loop, may the compiler replace
the loop's repeated reads of flag by one load before the loop (Proposition 9.4.13)?
Answer yes or no.

w1: while (!flag) {}
w2: while (!__atomic_load_n(&flag, __ATOMIC_ACQUIRE)) {}
w3: while (!*(volatile int *)&flag) {}
w4: while (!flag) { ext(); }
w5: while (!flag) { counter++; }

Keys: w1, w2, w3, w4, w5

Answer format: one value per key

Question 30 seqcst-store-x86 · mapping · 1 pt · 04-memory-and-addresses

llc -O1 for x86-64. Which instruction mnemonic implements each operation on
@r (write it without lock prefix or size suffix, e.g. mov)?

rel: store atomic i32 1, ptr @r release
sc: store atomic i32 1, ptr @r seq_cst
acq: load atomic i32, ptr @r acquire
scl: load atomic i32, ptr @r seq_cst
rmw: atomicrmw add ptr @r, i32 1 seq_cst

Keys: rel, sc, acq, scl, rmw

Answer format: one value per key

Question 31 gep-offset-langref · number · 1 pt · 04-memory-and-addresses

With the LangRef's structs on x86-64 (Lesson 9.4 §3:
%struct.RT = type { i8, [10 x [20 x i32]], i8 }, alloc size 808, field 1 at 4;
%struct.ST = type { i32, double, %struct.RT }, alloc size 824, field 2 at 16),
what byte offset \(\Delta\) does Algorithm 9.4.4 give for

getelementptr %struct.ST, ptr %s, i64 -1, i32 2, i32 1, i64 9, i64 19

Answer format: a number

Question 32 gep-leading-zero · multi · 1 pt · 04-memory-and-addresses

%s points to a %struct.ST = type { i32, double, %struct.RT } on x86-64 (double at
offset 8). Which instructions compute the same address as the C expression &s->Y
(field 1)?

getelementptr %struct.ST, ptr %s, i32 1
getelementptr %struct.ST, ptr %s, i64 0, i32 1
getelementptr double, ptr %s, i64 1
getelementptr %struct.ST, ptr %s, i64 1, i32 0
getelementptr i8, ptr %s, i64 8

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

Question 33 gep-canonical-form · mapping · 1 pt · 04-memory-and-addresses

On x86-64, with

%struct.E = type { i16, i32 }             ; size 8
%struct.Q = type { i64, [8 x %struct.E] } ; field 1 at 8, size 72
%q = getelementptr inbounds %struct.Q, ptr %p, i64 %i, i32 1, i64 %j

opt -passes=instcombine rewrites %q into three GEPs in byte-offset form
(Algorithm 9.4.9): a scaled piece [n1 x i8] indexed by %i, a constant piece
i8 by c, and a scaled piece [n2 x i8] indexed by %j. Give n1, c and n2.

Keys: n1, c, n2

Answer format: one value per key

Question 34 gep-inbounds-null · multi · 1 pt · 04-memory-and-addresses

Which of these functions does opt -passes=instcombine fold to ret i1 false?

%q = getelementptr inbounds i8, ptr %p, i64 4 · %c = icmp eq ptr %q, null
%q = getelementptr i8, ptr %p, i64 4 · %c = icmp eq ptr %q, null
%q = getelementptr nuw i8, ptr %p, i64 %x · %c = icmp ult ptr %q, %p
%q = getelementptr inbounds i8, ptr %p, i64 %x · %c = icmp eq ptr %q, null
%q = getelementptr inbounds i8, ptr %p, i64 -4 · %c = icmp ugt ptr %q, %p

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

Question 35 fptosi-poison · mapping · 1 pt · 04-memory-and-addresses

What does each cast produce? Answer an integer or poison.

a: fptosi double 3.9e9 to i32
b: fptosi double -2.7 to i32
c: fptoui double -0.5 to i32
d: fptosi double NaN to i32

Keys: a, b, c, d

Answer format: one value per key

Question 36 trunc-zext-roundtrip · mapping · 1 pt · 04-memory-and-addresses

%x is the i8 with bit pattern 0xC8 (−56 signed, 200 unsigned).
%s = sext i8 %x to i32 and %z = zext i8 %x to i32. What does each trunc produce?
Answer the i8 result as a signed decimal, or poison.

t1: trunc nsw i32 %s to i8
t2: trunc nuw i32 %s to i8
t3: trunc nuw i32 %z to i8
t4: trunc nsw i32 %z to i8

Keys: t1, t2, t3, t4

Answer format: one value per key

Question 37 vararg-promotion · mapping · 1 pt · 05-calls-attributes-intrinsics

int printf(const char *, ...);
void f(short s, unsigned char uc, float x, _Bool b, long l) {
  printf("%hd %hhu %f %d %ld\n", s, uc, x, b, l);
}

clang for x86-64 must apply C's default argument promotions itself (Definition 9.5.2).
Which cast instruction produces each variadic argument of the call? Answer sext,
zext, fpext or none.

Keys: s, uc, x, b, l

Answer format: one value per key

Question 38 cc-mismatch · single · 1 pt · 05-calls-attributes-intrinsics

define fastcc i32 @callee_fast(i32 %x) { ret i32 %x }
define i32 @mismatch(i32 %x) {
  %r = call i32 @callee_fast(i32 %x)      ; default convention: ccc
  ret i32 %r
}

What happens to @mismatch under opt -passes=instcombine?

The verifier rejects the module: call and callee conventions must match.
InstCombine adds fastcc to the call, because the callee is known.
InstCombine replaces the call by its unreachable marker (store i1 true, ptr poison) and the function returns poison.
Nothing: the mismatch is only diagnosed by llc.

Answer format: one letter

Question 39 memory-effects-join · mapping · 1 pt · 05-calls-attributes-intrinsics

Run Algorithm 9.5.5 (as opt -passes=function-attrs does) on

@g = global i32 0
define void @a(ptr %p) {
  store i32 0, ptr %p
  ret void
}
define i32 @b() {
  %v = load i32, ptr @g
  ret i32 %v
}
define i32 @c(ptr %p, ptr %q) {
  call void @a(ptr %q)
  %v = call i32 @b()
  ret i32 %v
}
define i32 @d(ptr %p) {
  %x = alloca i32
  store i32 1, ptr %x
  call void @a(ptr %x)
  %v = load i32, ptr %x
  ret i32 %v
}

Give the access (none, read, write or readwrite) that the inferred memory(…)
allows to argument memory and to other memory, for b, c and d.

Keys: b.argmem, b.other, c.argmem, c.other, d.argmem, d.other

Answer format: one value per key

Question 40 find-memloc · set · 1 pt · 05-calls-attributes-intrinsics

Find where LLVM does it (Lesson 9.5 §7). In llvm/include/llvm/Support/ModRef.h,
list the enumerators of enum class IRMemLocation (without the First/Last helpers),
spelled as in the source.

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

Question 41 intrinsic-mangling · mapping · 1 pt · 05-calls-attributes-intrinsics

Give the full mangled name (Definition 9.5.6) of each overloaded intrinsic call:

k1: umul.with.overflow on <4 x i16> operands
k2: memcpy from a ptr (address space 0) to a ptr addrspace(1) with an i32 length
k3: ctpop on <vscale x 2 x i64>
k4: fabs on double

Keys: k1, k2, k3, k4

Answer format: one value per key

Question 42 find-smul-overflow · single · 1 pt · 05-calls-attributes-intrinsics

Find where LLVM does it (Lesson 9.5 §7). In llvm/include/llvm/IR/Intrinsics.td,
def int_smul_with_overflow : DefaultAttrsIntrinsic<RET, PARAMS>. What is RET?

[llvm_anyint_ty, LLVMScalarOrSameVectorWidth<0, llvm_i1_ty>]
[llvm_i64_ty, llvm_i1_ty]
[LLVMMatchType<0>, LLVMMatchType<0>]
[llvm_anyint_ty]

Answer format: one letter

Question 43 tbaa-noalias · mapping · 1 pt · 06-metadata-and-representation

A front end emits this scalar TBAA tree (every access tag is !{T, T, i64 0} for its
type T):

R  (root)
└─ any
   ├─ int
   │  └─ myint
   └─ float
R2 (another root)
└─ o

Run Algorithm 9.6.3 on each pair of access types. Answer NoAlias or MayAlias.

q1: myint vs int
q2: myint vs float
q3: int vs float
q4: any vs float
q5: o vs int

Keys: q1, q2, q3, q4, q5

Answer format: one value per key

Question 44 range-fold · mapping · 1 pt · 06-metadata-and-representation

Each function loads %v = load i8, ptr %p, !range !0 with !0 = !{i8 0, i8 5} and
returns one comparison. Does opt -passes=instcombine fold the comparison? Answer
true, false or kept.

c1: icmp ult i8 %v, 10
c2: icmp eq i8 %v, 7
c3: icmp ult i8 %v, 3
c4: icmp sgt i8 %v, -1

Keys: c1, c2, c3, c4

Answer format: one value per key

Question 45 find-tbaa-root · text · 1 pt · 06-metadata-and-representation

Find where LLVM does it (Lesson 9.6 §7). In clang/lib/CodeGen/CodeGenTBAA.cpp, the
root of clang's C/C++ TBAA tree is named "Simple C/C++ TBAA". What is the name of the node
directly under it, from which every scalar C type (int, float, pointers…) descends?

Answer format: a short answer

Question 46 loop-md-distinct · single · 1 pt · 06-metadata-and-representation

clang attaches !llvm.loop !5 with !5 = distinct !{!5, !6, !7} to a loop's latch
branch. Why is the node distinct with itself as first operand?

So that the verifier can find the loop header by following the self-reference.
So that two loops with identical properties do not share one node: uniqued nodes with equal operands are merged, and updating one loop's properties would change the other's.
Because metadata cycles are required for the bitcode writer to emit the node before its uses.
To mark that the loop must be vectorized; a non-distinct node means the hints are optional.

Answer format: one letter

Question 47 loop-mustprogress · set · 1 pt · 06-metadata-and-representation

Compiled as C11 with clang-23 -std=c11 -O0 -S -emit-llvm (ext is an external function):

void l1(int n) { for (int i = 0; i < n; i++) ext(); }
void l2(void)  { while (1) ext(); }
void l3(int n) { int i = 0; do { ext(); } while (++i < n); }
void l4(void)  { for (;;) ext(); }

Which functions' loops get an !llvm.loop node containing !{!"llvm.loop.mustprogress"}
(Definition 9.6.5)?

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

Question 48 debug-records-not-instructions · mapping · 1 pt · 06-metadata-and-representation

A basic block contains 5 instructions and, compiled with -g, 3 variable-location
annotations. How many elements does for (Instruction &I : BB) visit when the
annotations are LLVM 23's debug records (records), and how many when they are the old
call void @llvm.dbg.value(…) intrinsics (intrinsics)?

Keys: records, intrinsics

Answer format: one value per key

Question 49 debug-record-values · mapping · 1 pt · 06-metadata-and-representation

In the -O1 -g output of sum_pos (Lesson 9.6 §7, box "Debug records in the running
example"), !23 is the variable s and !24 is i. The loop block is

for.body:
  %i.010 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
  %s.09 = phi i64 [ %spec.select, %for.body ], [ 0, %entry ]
    #dbg_value(i64 %i.010, !24, !DIExpression(), !27)
    #dbg_value(i64 %s.09, !23, !DIExpression(), !26)
  %arrayidx = getelementptr inbounds nuw [8 x i8], ptr %a, i64 %i.010, !dbg !32
  %0 = load i64, ptr %arrayidx, align 8, !dbg !32, !tbaa !34
  %add = tail call i64 @llvm.smax.i64(i64 %0, i64 0), !dbg !36
  %spec.select = add nuw nsw i64 %add, %s.09, !dbg !36
    #dbg_value(i64 %spec.select, !23, !DIExpression(), !26)
  %inc = add nuw nsw i64 %i.010, 1, !dbg !37
    #dbg_value(i64 %inc, !24, !DIExpression(), !27)
  ...

Which SSA values does the block say hold s, and which hold i? (Names without %.)

Keys: s, i

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

Question 50 vbr-encode · mapping · 1 pt · 06-metadata-and-representation

Encode the value 100 with Algorithm 9.6.7. How many chunks does vbr4 use, and what is
the first emitted chunk as an unsigned number (continuation bit included)? Same for
vbr6.

Keys: vbr4_chunks, vbr4_first, vbr6_chunks, vbr6_first

Answer format: one value per key

Question 51 compat-policy · multi · 1 pt · 06-metadata-and-representation

Which statements are part of LLVM's IR backwards-compatibility policy
(llvm/docs/DeveloperPolicy.md, "IR Backwards Compatibility")?

The current LLVM version supports loading any bitcode since version 3.0.
Textual .ll files written for LLVM 3.0 are guaranteed to parse with the current version.
Non-debug metadata is defined to be safe to drop, so dropping it is a valid way to upgrade it.
Bitcode written by the current version can be read by the previous release.
Newer releases can ignore features from older releases, but they cannot miscompile them.

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

Question 52 ub-or-poison · mapping · 1 pt · 07-poison-undef-and-ub

For each i8 instruction with these constant operands, is the result immediate UB,
poison, or a defined value? Answer ub, poison or defined.

a: udiv i8 7, 0
b: add nsw i8 127, 1
c: shl i8 1, 9
d: sdiv i8 -128, -1
e: lshr exact i8 5, 1
f: add i8 127, 1

Keys: a, b, c, d, e, f

Answer format: one value per key

Question 53 branch-on-poison · multi · 1 pt · 07-poison-undef-and-ub

%v is an i32 poison value and %c an i1 poison value. Which of these instructions
is immediate UB when executed?

br i1 %c, label %a, label %b
%s = select i1 %c, i32 1, i32 2
%q = udiv i32 1, %v
%r = udiv i32 %v, 7
call void @f(i32 noundef %v)
store i32 %v, ptr %p (with %p a valid pointer)
%k = icmp eq i32 %v, 0

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

Question 54 poison-trace · mapping · 1 pt · 07-poison-undef-and-ub

Evaluate with Definition 9.7.4 (Algorithm 9.7.5). Answer a number, true/false, or
poison.

%x = add i8 200, 0
%a = add nuw i8 %x, 100
%b = or disjoint i8 12, 3
%c = or disjoint i8 12, 4
%d = select i1 false, i8 %a, i8 %b
%e = mul i8 %c, 0
%f = icmp samesign ult i8 3, 5
%g = zext nneg i8 -3 to i16

Keys: a, b, c, d, e, f, g

Answer format: one value per key

Question 55 freeze-sub · mapping · 1 pt · 07-poison-undef-and-ub

%p is i8 poison. For each value, answer its number if it is the same for every
choice freeze can make, poison, or depends:

%f  = freeze i8 %p
%d  = sub i8 %f, %f
%f1 = freeze i8 %p
%f2 = freeze i8 %p
%e  = sub i8 %f1, %f2
%g  = sub i8 %p, %p
%h  = and i8 %f, 0

Keys: d, e, g, h

Answer format: one value per key

Question 56 undef-twice · mapping · 1 pt · 07-poison-undef-and-ub

%u is i8 undef. How many different results can each instruction produce
(Definition 9.7.6)?

add: add i8 %u, %u
mul: mul i8 %u, 2

Keys: add, mul

Answer format: one value per key

Question 57 undef-vs-poison · multi · 1 pt · 07-poison-undef-and-ub

Which statements about undef and poison hold in LLVM 23?

and i8 undef, 1 can only be 0 or 1, while and i8 poison, 1 is poison.
Replacing a poison constant by undef is a refinement.
Replacing an undef constant by poison is a refinement.
sub i8 %x, %x may be folded to 0 even if %x may be undef.
freeze i8 undef yields one fixed, arbitrary value that all its uses share.

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

Question 58 nsw-fold · mapping · 1 pt · 07-poison-undef-and-ub

Is each rewrite (on i8) a correct refinement? Answer valid or invalid.

f1: icmp sgt (add nsw %x, 1), %x → true
f2: icmp ugt (add nsw %x, 1), %x → true
f3: icmp ugt (add nuw %x, 1), %x → true
f4: sdiv (mul nsw %x, 4), 4 → %x
f5: sdiv (mul %x, 4), 4 → %x

Keys: f1, f2, f3, f4, f5

Answer format: one value per key

Question 59 flags-allowed · mapping · 1 pt · 07-poison-undef-and-ub

Algorithm 9.7.10 on two rewrites (i8). For each target, which flags may it keep so
that it still refines the source? Answer the allowed set as none, nuw, nsw or
both.

r1: or disjoint i8 %x, %y → add i8 %x, %y
r2: mul nuw i8 %x, 2 → shl i8 %x, 1

Keys: r1, r2

Answer format: one value per key

Question 60 find-propagates-poison · mapping · 1 pt · 07-poison-undef-and-ub

Find where LLVM does it (Lesson 9.7 §7). In llvm/lib/Analysis/ValueTracking.cpp,
propagatesPoison(const Use &PoisonOp) says whether an instruction's result is poison
whenever the given operand is. What does it return (true/false) for:

sel_cond: the condition of a select
sel_arm: the true or false operand of a select
phi: an incoming value of a phi
freeze: the operand of freeze
icmp: an operand of icmp
call: an argument of a call to an ordinary (non-intrinsic) function

Keys: sel_cond, sel_arm, phi, freeze, icmp, call

Answer format: one value per key

Question 62 blockargs-translate · sequence · 1 pt · 08-ir-comparison

Apply Algorithm 9.8.3 (phis to block arguments) to

entry:
  br label %loop
loop:
  %a = phi i64 [ 0, %entry ], [ %b, %loop ]
  %b = phi i64 [ 1, %entry ], [ %sum, %loop ]
  %k = phi i64 [ %n, %entry ], [ %k1, %loop ]
  %sum = add i64 %a, %b
  %k1 = sub i64 %k, 1
  %c = icmp eq i64 %k1, 0
  br i1 %c, label %exit, label %loop

loop gets the parameters (a, b, k) in phi order. Which arguments does the back edge
loop → loop pass, in order? (Names without %.)

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

Question 63 ir-coordinates · mapping · 1 pt · 08-ir-comparison

Definition 9.8.1's merges coordinate: how does each IR combine values that reach a
join from different paths? Answer phi, blockargs (block parameters/arguments) or
locals (assignments to mutable locals, including Wasm's locals and operand stack).

llvm, gimple, sil, mir, clif, wasm, pir

Keys: llvm, gimple, sil, mir, clif, wasm, pir

Answer format: one value per key

Question 64 gimple-phi · single · 1 pt · 08-ir-comparison

GCC's -fdump-tree-optimized for sum_pos (Lesson 9.8 §7) contains, at the top of
<bb 4>, the line # s_15 = PHI <s_5(6), 0(3)>. What do (6) and (3) denote?

The SSA version numbers of the two incoming values.
The numbers of the predecessor basic blocks from which each value arrives.
Branch probabilities in tenths.
The source lines where s was assigned.

Answer format: one letter

Question 65 mir-assert · single · 1 pt · 08-ir-comparison

rustc's MIR for sum_pos (Lesson 9.8 §7) contains

assert(move _9, "index out of bounds: the length is {} but the index is {}", copy _5, copy _8) -> [success: bb3, unwind continue];

Which statement is right?

assert is a statement that is removed in release builds (-C opt-level=2), like C's assert.
assert is a terminator: if _9 is true control goes to bb3; otherwise the function panics, and unwind continue means the unwinding simply continues into the caller because this function has no cleanup to run.
unwind continue means execution continues at bb3 even when the check fails.
It is lowered to llvm.assume(_9), so LLVM may assume the index is in bounds.

Answer format: one letter

Question 66 clif-no-poison · mapping · 1 pt · 08-ir-comparison

Cranelift compiles these i32 operations (CLIF iadd, udiv, ishl, sdiv, as
translated from the Wasm instructions i32.add, i32.div_u, i32.shl, i32.div_s).
What happens? Answer the result as a signed decimal, or trap.

a: 2147483647 + 1
b: 7 ÷ 0 (unsigned)
c: 1 shifted left by 33
d: −2147483648 ÷ −1 (signed)

Keys: a, b, c, d

Answer format: one value per key

Question 67 wasm-structured · mapping · 1 pt · 08-ir-comparison

(block            ;; B
  (loop           ;; L
    ...
    (br_if 0 (local.get $again))   ;; x
    ...
    (br_if 1 (local.get $done))    ;; y
    ...
  )
  (block          ;; C
    (br 0)                          ;; z
  )
)

Where does each branch go (Definition 9.8.5)? Answer L-start, L-end, B-end or
C-end.

Keys: x, y, z

Answer format: one value per key