Theory test — Chapter 10¶

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

Question 1 uniquing-pointer-eq · mapping · 1 pt · 01-ownership-and-containers

C1 and C2 are two different LLVMContexts. For each pair, is the first pointer
equal to the second (yes/no)?

key	first	second
`a`	`IntegerType::get(C1, 32)`	`Type::getInt32Ty(C1)`
`b`	`Type::getInt32Ty(C1)`	`Type::getInt32Ty(C2)`
`c`	`StructType::get(C1, {I32, I64})`	`StructType::get(C1, {I32, I64})` (called again)
`d`	`StructType::create(C1, {I32}, "T")`	`StructType::create(C1, {I32}, "U")`
`e`	`ConstantInt::get(I32, 42)`	`ConstantInt::get(C1, APInt(32, 42))`
`f`	`ConstantInt::get(I64, 42)`	`ConstantInt::get(I32, 42)`

(I32 and I64 are the i32/i64 types of C1.)

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

Answer format: a: yes/no, one line per key

Question 2 llvm-where-zero-one-slots · set · 1 pt · 01-ownership-and-containers

Find where LLVM does it (Lesson 10.1 §7). In llvm/lib/IR/Constants.cpp at
llvmorg-23.1.2, ConstantInt::get(LLVMContext &, const APInt &) does not look up the
values 0 and 1 in the general IntConstants map. Give the names of the two
LLVMContextImpl members it uses for them instead.

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

Question 3 erase-vs-remove · single · 1 pt · 01-ownership-and-containers

A pass calls I->removeFromParent() on an instruction that has users, and then returns
without re-inserting or deleting I. What is the state afterwards?

I is freed, and its users now have null operands
I is still alive with a null parent, owned by nobody (leaked), and its users still point to it, so the function is now invalid
I is freed, and the verifier reports the dangling uses
I is moved to the end of the block

Answer format: one letter

Question 4 ownership-subtree · set · 1 pt · 01-ownership-and-containers

A module M contains, among other things, this function:

define i32 @h(i32 %p) {
entry:
  %t = add i32 %p, 1
  br label %exit
exit:
  ret i32 %t
}

No other function refers to @h. Which of the objects h, p, entry, exit, t,
br, ret, i32 (the type), one (the constant i32 1) and M are freed by
H->eraseFromParent()?

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

Question 5 early-inc-trace · sequence · 1 pt · 01-ownership-and-containers

Block entry of a function holds %a, %b, %c, ret in that order. The loop

for (Instruction &I : make_early_inc_range(BB)) {
  if (I.getName() == "a") I.eraseFromParent();
  else if (I.getName() == "b") /* create %n */ BinaryOperator::Create(Instruction::Mul, X, X, "n", C->getIterator());   // before %c
  else if (I.getName() == "c") /* create %m */ BinaryOperator::Create(Instruction::Mul, X, X, "m", Ret->getIterator()); // before ret
}

runs the body on which instructions, in order? (Write ret for the return.)

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

Question 6 ilist-size-cost · number · 1 pt · 01-ownership-and-containers

A block holds exactly 1000 instructions, and nothing is inserted or erased. How many list
nodes are stepped over in total by the BB.size() calls in

for (Instruction &I : BB)
  if (BB.size() > Limit) { /* never taken */ }

(Count one step per element that size() walks past.)

Answer format: a number

Question 7 early-inc-where · single · 1 pt · 01-ownership-and-containers

Find where LLVM does it (Lesson 10.1 §7). In llvm/include/llvm/ADT/STLExtras.h,
early_inc_iterator_impl wraps an iterator I. Where is the wrapped iterator advanced?

In operator++, after the body has run
In operator*, which returns *I++: dereferencing both yields the element and advances past it
In the constructor, once, for the whole loop
In operator==, when the loop tests for the end

Answer format: one letter

Question 8 arena-stale-ref · single · 1 pt · 01-ownership-and-containers

A Cranelift pass saves let i: Inst = … for an instruction, and later a different
transformation removes that instruction from the Layout. What does the pass get when it
reads dfg.insts[i] afterwards?

A crash: the entry was freed
The removed instruction's old data: valid memory, but stale. Nothing flags it, unless the pass checks layout membership (layout.inst_block(i) is None)
Whatever instruction was created next, because the slot was reused
A compile-time error from the borrow checker

Answer format: one letter

Question 9 arena-layout-trace · sequence · 1 pt · 01-ownership-and-containers

An arena holds instructions with references 0, 1, 2, 3, and the layout order is
$0 \to 1 \to 2 \to 3$. Apply Algorithm 10.1.10 and layout removal in this order:

MakeInst(D), then insert it before reference 1;
remove reference 2 from the layout;
MakeInst(E), then insert it before reference 3.

Give the final layout order as references.

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

Question 10 uselist-order-trace · sequence · 1 pt · 02-values-uses-and-def-use-chains

The parser builds this function top to bottom:

define i32 @g(i32 %x) {
  %a = add i32 %x, 1
  %b = mul i32 %x, %a
  %c = sub i32 %a, %x
  %d = and i32 %c, %x
  ret i32 %d
}

Give uses(%x) head first (the order for (Use &U : X->uses()) visits), writing each use
as user[operand number], e.g. %a[0].

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

Question 11 llvm-where-hasuselist · text · 1 pt · 02-values-uses-and-def-use-chains

Find where LLVM does it (Lesson 10.2 §7). In llvm/include/llvm/IR/Value.h,
Value::addUse(Use &U) links U into the value's list only if a predicate holds. Which
member function is that predicate? (Name only, without ().)

Answer format: a short answer

Question 12 operand-layout-offset · number · 1 pt · 02-values-uses-and-def-use-chains

%s = select i1 %c, i32 %x, i32 %y is a user with 3 co-allocated operands. In LLVM 23
on x86-64, sizeof(Use) = 32. At what byte offset from the SelectInst object's own
address is operand 0 (%c) stored?

Answer format: a number

Question 13 operand-layout-kinds · set · 1 pt · 02-values-uses-and-def-use-chains

Which of these LLVM 23 instructions keep their operands in a hung-off array (a
separate allocation that can grow): phi, switch, add, store, landingpad,
indirectbr, call, ret?

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

Question 14 rauw-result-trace · sequence · 1 pt · 02-values-uses-and-def-use-chains

In the function of uselist-order-trace, uses(%x) = %d[1] %c[1] %b[0] %a[0] and
uses(%a) = %c[0] %b[1]. After A->replaceAllUsesWith(X) (RAUW %a → %x), give
uses(%x) head first.

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

Question 15 rauw-dominance · set · 1 pt · 02-values-uses-and-def-use-chains

In the running example

define i32 @f(i32 %x, i32 %y) {
entry:
  %a = add i32 %x, %y
  %b = mul i32 %a, %a
  %c = sub i32 %b, %a
  %d = xor i32 %x, %c
  ret i32 %d
}

which of these calls leave the function satisfying the SSA dominance property?

r1: RAUW(%c, %a)
r2: RAUW(%a, %c)
r3: RAUW(%b, %x)
r4: RAUW(%d, i32 0)
r5: RAUW(%a, %d)

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

Question 16 vh-after-rauw · single · 1 pt · 02-values-uses-and-def-use-chains

Find where LLVM does it (Lesson 10.2 §7). ValueHandleBase::ValueIsRAUWd(Old, New) in
llvm/lib/IR/Value.cpp walks Old's handle list and switches on each handle's kind
(Assert, Weak, WeakTracking, Callback). What does it do?

It re-points Weak and WeakTracking handles to New
It re-points only WeakTracking handles to New, calls allUsesReplacedWith(New) on Callback handles, and leaves Assert and Weak handles alone
It nulls every handle
It re-points every handle kind to New

Answer format: one letter

Question 17 vh-kinds · mapping · 1 pt · 02-values-uses-and-def-use-chains

In a function with instructions %a, %b, %c (all i32), a pass creates

WeakVH w1(A); WeakTrackingVH w2(A); WeakVH w3(B);
A->replaceAllUsesWith(B); A->eraseFromParent();
B->replaceAllUsesWith(C); B->eraseFromParent();

What does each handle point to at the end? Answer null, %a, %b or %c.

Keys: w1, w2, w3

Answer format: one value per key

Question 18 mav-type · single · 1 pt · 02-values-uses-and-def-use-chains

In call double @llvm.experimental.constrained.fadd.f64(double %x, double %y, metadata !"round.dynamic", metadata !"fpexcept.strict"),
what is the third call operand, as a C++ object?

An MDString directly: metadata can be an operand
A MetadataAsValue of type metadata, wrapping the MDString
A ConstantDataArray holding the string
A ValueAsMetadata wrapping a global string

Answer format: one letter

Question 19 mav-uniquing · mapping · 1 pt · 02-values-uses-and-def-use-chains

A function contains three constrained adds:

%s1 = call double @llvm.experimental.constrained.fadd.f64(double %x,  double %y, metadata !"round.dynamic",    metadata !"fpexcept.strict")
%s2 = call double @llvm.experimental.constrained.fadd.f64(double %s1, double %y, metadata !"round.dynamic",    metadata !"fpexcept.strict")
%s3 = call double @llvm.experimental.constrained.fadd.f64(double %s2, double %y, metadata !"round.towardzero", metadata !"fpexcept.strict")

wrappers: how many distinct MetadataAsValue objects are used as the metadata
operands of the three calls? strict-uses: how many uses does the wrapper of
!"fpexcept.strict" have?

Keys: wrappers, strict-uses

Answer format: one value per key

Question 20 direct-construction-fold · number · 1 pt · 03-building-ir-with-irbuilder

F is define i32 @f(i32 %x) with an empty block BB, and B is an IRBuilder<>
appending to BB. How many instructions does BB contain after these five calls?

BinaryOperator::Create(Instruction::Add, B.getInt32(2), B.getInt32(3), "k", BB->end());
B.CreateAdd(B.getInt32(2), B.getInt32(3), "k2");
B.CreateMul(X, B.getInt32(1), "m");
BinaryOperator::Create(Instruction::Mul, X, B.getInt32(1), "m2", BB->end());
B.CreateRet(X);

Answer format: a number

Question 21 direct-construction-position · sequence · 1 pt · 03-building-ir-with-irbuilder

Block entry initially holds %a = add and ret. Then:

auto *S = BinaryOperator::Create(Instruction::Sub, Y, A, "s", Ret->getIterator());
BinaryOperator::Create(Instruction::Mul, Y, Y, "m", BB->begin());
auto *Xo = BinaryOperator::Create(Instruction::Xor, Y, A, "x", nullptr);
Xo->insertBefore(S->getIterator());

Give the final order of the block (write ret for the return).

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

Question 22 headbit-order · sequence · 1 pt · 03-building-ir-with-irbuilder

Block entry is

entry:
    #dbg_value(i32 %x, !9, !DIExpression(), !10)
  %y = add i32 %x, 1, !dbg !10
  ret i32 %y, !dbg !10

Then:

B.SetInsertPoint(&BB.front());      // Instruction *: %y
B.CreateMul(X, X, "p");
B.SetInsertPoint(&BB, BB.begin());  // iterator from begin()
B.CreateMul(X, X, "q");

Give the printed order of the block's lines, writing dbg for the #dbg_value record
and ret for the return.

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

Question 23 llvm-where-headbit · text · 1 pt · 03-building-ir-with-irbuilder

Find where LLVM does it (Lesson 10.3 §7). In llvm/lib/IR/Instruction.cpp,
Instruction::insertBefore(BasicBlock &, InstListType::iterator InsertPos) contains the
assertion "Inserting PHI after debug-records!". It is reachable only when a certain
bit of InsertPos is clear. Which bit is it? (Name it as the lesson does.)

Answer format: a short answer

Question 24 folder-trace · mapping · 1 pt · 03-building-ir-with-irbuilder

An IRBuilder<InstSimplifyFolder> emits into define i8 @f(i8 %x, i8 %y):

Value *a = B.CreateMul(X, B.getInt8(1));
Value *b = B.CreateAdd(B.getInt8(200), B.getInt8(100));
Value *c = B.CreateXor(a, a);
Value *d = B.CreateOr(c, Y);
Value *e = B.CreateSub(d, b);

For a–e, what does the call return: an existing value (%x, %y), a constant
(decimal, as an unsigned i8), or new (an instruction was inserted)? Also give
inserted: how many instructions a callback inserter would have counted.

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

Answer format: one value per key

Question 25 inserter-count · number · 1 pt · 03-building-ir-with-irbuilder

An IRBuilder<ConstantFolder, IRBuilderCallbackInserter> whose callback increments a
counter emits into define i32 @f(i32 %z):

Value *A = B.CreateAdd(Z, B.getInt32(0), "a");
B.CreateMul(B.getInt32(6), B.getInt32(7), "m");
Value *S = B.CreateSub(A, B.getInt32(42), "s");
B.CreateICmpEQ(B.getInt32(1), B.getInt32(1), "c");
B.CreateRet(S);

What is the counter at the end?

Answer format: a number

Question 26 fmf-guard · mapping · 1 pt · 03-building-ir-with-irbuilder

FastMathFlags NNaN; NNaN.setNoNaNs();
FastMathFlags Fast; Fast.setFast();
B.setFastMathFlags(NNaN);
Value *a = B.CreateFAdd(x, y, "a");
{
  IRBuilderBase::FastMathFlagGuard G(B);
  B.setFastMathFlags(Fast);
  b = B.CreateFMul(a, x, "b");
  B.clearFastMathFlags();
  c = B.CreateFSub(b, y, "c");
}
Value *d = B.CreateFDiv(c, x, "d");

Which flags does each instruction carry? Answer none, nnan or fast.

Keys: a, b, c, d

Answer format: one value per key

Question 27 builder-state-dbg · mapping · 1 pt · 03-building-ir-with-irbuilder

Instruction %i carries the debug location line 7. The builder is positioned before
%i:

B.SetCurrentDebugLocation(L1);                 // line 1
B.CreateFAdd(v, v, "a");
{
  IRBuilderBase::InsertPointGuard G(B);
  B.SetInsertPoint(I);                         // I = %i
  B.CreateFMul(v, v, "b");
  B.SetCurrentDebugLocation(L9);               // line 9
  B.CreateFSub(v, v, "c");
}
B.CreateFDiv(v, v, "d");
B.SetInsertPoint(Exit);                        // another block, still empty
Value *e = B.CreateFNeg(v, "e");

Which line does each of a–e get?

Keys: a, b, c, d, e

Answer format: one value per key

Question 28 cast-eval · mapping · 1 pt · 04-casting-and-dispatch

In define i1 @c(i32 %x) { %p = icmp slt i32 %x, 7 ret i1 %p }, evaluate each
expression. Answer true, false, null, ptr (a non-null pointer) or assert
(an assertion failure in a debug build).

key	expression
`e1`	`isa<Instruction>(ConstantInt i32 7)`
`e2`	`dyn_cast<BinaryOperator>(%p)`
`e3`	`isa<CmpInst>(%p)`
`e4`	`isa<Constant>(@c)` (the `Function *`)
`e5`	`isa_and_present<Argument>(nullptr)`
`e6`	`isa<User>(%x)` (the `Argument *`)
`e7`	`cast<Instruction>(%x)`

Keys: e1, e2, e3, e4, e5, e6, e7

Answer format: one value per key

Question 29 classof-range · mapping · 1 pt · 04-casting-and-dispatch

A hierarchy with abstract classes Node, Expr, BinOp, Stmt and concrete leaves:

Node
├── Expr
│   ├── Lit
│   └── BinOp
│       ├── Add
│       └── Mul
└── Stmt
    ├── Assign
    └── Return

Number the concrete classes in depth-first preorder from 0, as Theorem 10.4.10 requires.
Give the first and last kind of each abstract class's interval.

Keys: Expr-first, Expr-last, BinOp-first, BinOp-last, Stmt-first, Stmt-last

Answer format: one value per key

Question 30 llvm-where-constant-classof · single · 1 pt · 04-casting-and-dispatch

Find where LLVM does it (Lesson 10.4 §7). Constant::classof in
llvm/include/llvm/IR/Constant.h is return V->getValueID() <= ConstantLastVal;, next
to static_assert(ConstantFirstVal == 0, …). Why is one comparison enough?

Because constants are never instructions, so no range is needed
Because the constant kinds are numbered first in Value.def: the interval starts at 0, so the lower test >= ConstantFirstVal is always true, and the static_assert breaks the build if someone ever reorders the IDs
Because getValueID() is unsigned and can never be negative, which is all that matters
Because Constant is a final class

Answer format: one letter

Question 31 value-not-polymorphic · single · 1 pt · 04-casting-and-dispatch

What happens with bool isBin(Value *V) { return dynamic_cast<BinaryOperator *>(V); }
compiled against LLVM 23 headers, even though this LLVM is built with RTTI enabled?

It works, but is slower than isa
It always returns false
It does not compile: llvm::Value is not polymorphic (no virtual functions, so no vtable to find the dynamic type)
It links only if the client is built with -frtti

Answer format: one letter

Question 32 dynamic-cast-cases · mapping · 1 pt · 04-casting-and-dispatch

struct A { virtual ~A() {} };
struct B : A {};
struct C { virtual ~C() {} };
struct D : B, C {};
struct E : A {};
D d; A *pa = &d;

For each cast, is the result null or nonnull? For k5, also decide whether the result
equals &d (same) or not (different).

key	expression
`k1`	`dynamic_cast<B *>(pa)`
`k2`	`dynamic_cast<C *>(pa)`
`k3`	`dynamic_cast<D *>(pa)`
`k4`	`dynamic_cast<E *>(pa)`
`k5`	`(void )dynamic_cast<C >(pa)` compared with `(void *)&d`

Keys: k1, k2, k3, k4, k5

Answer format: one value per key

Question 33 variant-exhaustive · single · 1 pt · 04-casting-and-dispatch

A pass represents nodes as std::variant<Bin, Cmp, Sel> and dispatches with
std::visit(overloaded{[](const Bin &)…, [](const Cmp &)…, [](const Sel &)…}, N).
Someone adds Load to the variant and forgets this visitor. What happens?

At run time, visit on a Load throws bad_variant_access
The program compiles, and Load falls to the first handler
Compilation fails: std::visit instantiates the visitor for every alternative, and none accepts Load
The call is silently skipped for Load

Answer format: one letter

Question 34 variant-cost · number · 1 pt · 04-casting-and-dispatch

With variant.cpp's visitor (Lesson 10.4, the std::visit real-world box):

if constexpr (std::is_same_v<T, Bin>) return X.Op == 3 ? 4 : 1;
else if constexpr (std::is_same_v<T, Cmp>) return 1;
else return 2;                                      // Sel

what is the sum of cost(N) over the nodes Bin{3}, Cmp{0}, Sel{}, Bin{1},
Sel{}?

Answer format: a number

Question 35 instvisitor-delegation · mapping · 1 pt · 04-casting-and-dispatch

An InstVisitor subclass overrides exactly visitBinaryOperator, visitCmpInst,
visitTerminator, visitCallInst, visitUnaryInstruction and visitInstruction.
Which of them runs for each instruction? Answer with the handler name, e.g.
visitCmpInst.

key	instruction
`add`	`add i32 %x, 1`
`fcmp`	`fcmp olt float %f, 1.0`
`memcpy`	`call void @llvm.memcpy.p0.p0.i64(…)`
`load`	`load i32, ptr %p`
`zext`	`zext i32 %v to i64`
`store`	`store i32 %v, ptr %q`
`invoke`	`invoke void @may_throw() to label %ok unwind label %lp`
`ret`	`ret void`

Keys: add, fcmp, memcpy, load, zext, store, invoke, ret

Answer format: one value per key

Question 36 instvisitor-memcpy · text · 1 pt · 04-casting-and-dispatch

Find where LLVM does it (Lesson 10.4 §7). In llvm/include/llvm/IR/InstVisitor.h,
delegateCallInst routes calls to intrinsics. A visitor overrides only
visitIntrinsicInst and visitCallInst. Which of the two handles a call to
llvm.memcpy?

Answer format: a short answer

Question 37 handwritten-commuted · mapping · 1 pt · 05-pattern-matching

Algorithm 10.5.4 (MatchAddSubCancel) recognizes add (sub Y, X), X in either operand
order of the add and returns Y. What does it return for each instruction? Answer the
value name or none.

key	instruction
`i1`	`add (sub %y, %x), %x`
`i2`	`add %x, (sub %y, %x)`
`i3`	`add (sub %y, %x), %y`
`i4`	`add (sub %x, %y), %y`
`i5`	`add (sub %y, %x), (sub %y, %x)` (the same `sub` twice)

Keys: i1, i2, i3, i4, i5

Answer format: one value per key

Question 38 pm-bindings · mapping · 1 pt · 05-pattern-matching

Value *A, *B; ConstantInt *C;
match(S, m_c_Add(m_Value(A), m_Mul(m_Value(B), m_ConstantInt(C))));

with %m = mul i32 %x, 8 and S = %s = add i32 %m, %y. The match succeeds. What are
A, B and C afterwards? (Give C as a decimal.)

Keys: A, B, C

Answer format: one value per key

Question 39 pm-nested-incomplete · mapping · 1 pt · 05-pattern-matching

Pattern m_c_Add(m_c_Mul(m_Value(X), m_Value(Y)), m_Deferred(X)) ("an add of a
product and one of its factors"), with %mab = mul i32 %a, %b. Does match succeed
(match/no)?

key	instruction
`r1`	`add i32 %mab, %a`
`r2`	`add i32 %mab, %b`
`r3`	`add i32 %b, %mab`
`r4`	`add i32 %a, %mab`

Keys: r1, r2, r3, r4

Answer format: one value per key

Question 40 llvm-where-binaryop-match · single · 1 pt · 05-pattern-matching

Find where LLVM does it (Lesson 10.5 §7). In llvm/include/llvm/IR/PatternMatch.h,
BinaryOp_match<LHS, RHS, Opcode, Commutable>::match tries the operands how?

(L.match(Op1) && R.match(Op0)) || (L.match(Op0) && R.match(Op1)), resetting the bindings in between
(L.match(Op0) && R.match(Op1)) || (Commutable && L.match(Op1) && R.match(Op0)), with no reset: a failed first attempt may leave bindings behind
It sorts the operands by complexity first, and then tries one order
It tries all orders of every nested commutative node (full backtracking)

Answer format: one letter

Question 41 dsl-termination · single · 1 pt · 05-pattern-matching

Which rule set is guaranteed to terminate by Theorem 10.5.8, using the measure
$\mu = (\#\text{instructions}, \#\texttt{mul})$ compared lexicographically?

x * 2 → x + x and x + x → x * 2
x + 0 → x, x * 1 → x, x * 2 → x << 1
a + b → b + a (for all a, b)
x → x + 0

Answer format: one letter

Question 42 dsl-alternatives · number · 1 pt · 05-pattern-matching

You state the rule (xor (and a, b), b) → (and (not a), b) in a DSL without a
commutativity flag (like a GlobalISel GICombinePatFrag), so each operand order is a
separate pattern alternative. Both xor and and are commutative, and the repeated
b may be either operand of the and. How many alternatives do you need so that the
matcher is complete, as a hand-written matcher looping over every order would be?

Answer format: a number

Question 43 dsl-rewrite-trace · sequence · 1 pt · 05-pattern-matching

Rules: R1: x + 0 → x, R2: x + x → x * 2, R3: x * 2 → x << 1. Start from the term
(a + a) + 0 and always rewrite the leftmost innermost redex (operands before their
users, as a bottom-up combiner visits them) until no rule applies. Give the sequence
of rules applied.

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

Question 44 smallvector-growth · number · 1 pt · 06-adts

Find where LLVM does it (Lesson 10.6 §7). In llvm/lib/Support/SmallVector.cpp, find
getNewCapacity. A SmallVector has size 9 and capacity 9 (it has already grown). What
is its capacity after one more push_back?

Answer format: a number

Question 45 smallvector-moves · number · 1 pt · 06-adts

A SmallVector<int, 2> starts empty and receives 25 push_back calls. How many element
moves do the reallocations perform in total? (Each growth moves every element already
stored.)

Answer format: a number

Question 46 densemap23-trace · mapping · 1 pt · 06-adts

An LLVM 23 SmallDenseMap<unsigned, unsigned, 8> (8 buckets, linear probing, hash
$37k \bmod 2^{32}$, so $\mathrm{home}(k) = 5k \bmod 8$) receives:

insert 3, insert 11, insert 19, insert 2, erase 3, insert 27

In which bucket (0–7) is each remaining key at the end?

Keys: 19, 27, 2, 11

Answer format: one value per key

Question 47 densemap22-tombstone · mapping · 1 pt · 06-adts

The same operations on an LLVM 22 SmallDenseMap<unsigned, unsigned, 8> (quadratic
probing with offsets 0, 1, 3, 6, …, tombstones on erase, same hash):

insert 3, insert 11, insert 19, insert 2, erase 3, insert 27

In which bucket is each remaining key at the end?

Keys: 11, 19, 2, 27

Answer format: one value per key

Question 48 llvm-where-algorithm-r · single · 1 pt · 06-adts

Find where LLVM does it (Lesson 10.6 §7). In LLVM 23's llvm/include/llvm/ADT/DenseMap.h,
eraseFromFilledBucket walks the buckets J after the hole I. When is the key in J
moved into I?

When J's key has the same hash as the erased key
When ((I - Ideal) & Mask) < ((J - Ideal) & Mask), where Ideal is the home bucket of J's key: the hole lies on that key's probe path
Always, until an empty bucket is reached (a plain backward shift)
Never: the bucket is marked as a tombstone

Answer format: one letter

Question 49 setvector-order · sequence · 1 pt · 06-adts

A SetVector<int> receives insert 7, insert 2, insert 7, insert 9, insert 2, insert 4,
then remove(9), insert 9, and pop_back_val(). Give the iteration order at the end.

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

Question 50 setvector-determinism · single · 1 pt · 06-adts

A pass collects the blocks to visit in a DenseSet<BasicBlock *> and then iterates the
set to emit code. Its output differs between two runs on the same input. Why, and what is
the standard fix?

DenseSet is not thread-safe; add a lock
DenseSet iterates in bucket order, which depends on the pointers' hash, and heap addresses change between runs (ASLR). Use a SetVector (insertion order), or sort by a stable key
DenseSet drops duplicates nondeterministically; use a SmallVector
The pass has a data race in BasicBlock::getName

Answer format: one letter

Question 51 twine-dangling · mapping · 1 pt · 06-adts

StringRef A = "block", B = "exit"; unsigned N = 42; and each line is followed by a use
of T (or S, R) in the next statement. Is that use safe or dangling?

key	code
`t1`	`const Twine T = A + "." + B;`
`t2`	`const Twine T = A + ".exit";`
`t3`	`std::string S = (A + "." + B).str();`
`t4`	`F->setName(A + "." + Twine(N));` (the use is `F->getName()`)
`t5`	`const Twine T = Twine(N);`

Keys: t1, t2, t3, t4, t5

Answer format: one value per key

Question 52 stringref-lifetime · set · 1 pt · 06-adts

Which of these uses read memory that is no longer valid?

s1: StringRef N = I->getName(); I->setName("x"); outs() << N;
s2: StringRef N = F->getName(); then 2000 new functions are added to the module; outs() << N;
s3: std::vector<int> V{1, 2}; ArrayRef<int> R = V; V.push_back(3); use(R[0]);
s4: ArrayRef<int> R = {1, 2, 3}; use(R[0]); (in the next statement)
s5: StringRef S = "literal"; outs() << S;

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

Question 53 stringmap-stable · mapping · 1 pt · 06-adts

StringMap<int> M; contains add and mul. You take StringRef K = M.find("add")->getKey();.
Is K still valid or dangling after each of these steps, applied in order?

p1: 1000 more keys are inserted (the table grows several times)
p2: M.erase("mul")
p3: M.erase("add")

Keys: p1, p2, p3

Answer format: one value per key

Question 54 bitvector-words · mapping · 1 pt · 06-adts

The set $\{5, 70, 200\}$ is stored in a BitVector(256) and in a SparseBitVector<128>.
Give:

words: the number of 64-bit words of the BitVector;
word-of-200 and bit-of-200: where element 200 lives in it;
sparse-elements: the number of 128-bit elements of the SparseBitVector.

Keys: words, word-of-200, bit-of-200, sparse-elements

Answer format: one value per key

Question 55 bitset-choice · single · 1 pt · 06-adts

Which representation fits which set in a compiler?

BitVector for points-to sets over all memory objects of a program, SparseBitVector for liveness over a function's virtual registers
BitVector for liveness over a function's (few thousand) virtual registers, where sets are dense-ish and unions run constantly; SparseBitVector for points-to sets over hundreds of thousands of objects, where each set has few members
Always std::set<unsigned>: it is the most memory-efficient
Always SparseBitVector: it is never slower

Answer format: one letter

Question 56 pointer-bits · mapping · 1 pt · 06-adts

struct alignas(16) N16 { char c[16]; }; and
PointerIntPair<N16 *, 2, unsigned> P(reinterpret_cast<N16 *>(0x1000), 3);

free-bits: how many low bits of an N16 * are free?
stored: the opaque word P stores, in hex (0x…).
union-tag-bits: how many tag bits does PointerUnion<A *, B *, C *> need?

Keys: free-bits, stored, union-tag-bits

Answer format: one value per key

Question 57 pointer-packing-limit · single · 1 pt · 06-adts

What happens with PointerIntPair<char *, 1, bool> P;?

It works: every heap pointer is at least 8-byte aligned
It compiles but corrupts the pointer at run time
It fails to compile: char has alignment 1, so NumLowBitsAvailable is 0 and the static_assert "PointerIntPair with integer size too large for pointer" fires
It silently uses a separate bool field

Answer format: one letter

Question 58 apint-sdiv · mapping · 1 pt · 06-adts

Two APInts of width 8: a = 240 (bits 11110000) and b = 7. Give each result as a
decimal, reading it as the question says:

udiv: a.udiv(b), unsigned
sdiv: a.sdiv(b), signed
sdiv-unsigned: the same sdiv result read as unsigned
srem: a.srem(b), signed
add: a + 30, unsigned

Keys: udiv, sdiv, sdiv-unsigned, srem, add

Answer format: one value per key

Question 59 apint-overflow · mapping · 1 pt · 06-adts

With 8-bit APInts and bool Ov, give the result (as the operation's reading) and the
overflow flag (0/1):

sadd, sadd-ov: APInt(8, 100).sadd_ov(APInt(8, 50), Ov)
uadd-ov: APInt(8, 100).uadd_ov(APInt(8, 50), Ov)
umul, umul-ov: APInt(8, 20).umul_ov(APInt(8, 13), Ov)

Keys: sadd, sadd-ov, uadd-ov, umul, umul-ov

Answer format: one value per key

Question 60 error-bool-failure · single · 1 pt · 07-error-handling

Find where LLVM does it (Lesson 10.7 §7). Error::operator bool in
llvm/include/llvm/Support/Error.h is setChecked(getPtr() == nullptr); return getPtr() != nullptr;.
After if (E) { … } on a failing E, and with nothing else done to E, what does a
checking build do when E is destroyed?

Nothing: the if checked it
It aborts: testing a failure leaves it unchecked (checked = 0) and still holding its payload, so the destructor's assertIsChecked fires. You must consume it (return E;, consumeError, handleAllErrors, …)
It logs a warning and continues
It throws std::runtime_error

Answer format: one letter

Question 61 must-check-trace · mapping · 1 pt · 07-error-handling

In a checking build, f() fails:

Expected<int> R = f();          // (1)
if (!R) {                       // (2)
  Error E = R.takeError();      // (3)
  if (E) { }                    // (4)
  consumeError(std::move(E));   // (5)
}

Give the checked bit (0/1) at each point: R-after-2, R-after-3, E-after-3,
E-after-4, E-after-5.

Keys: R-after-2, R-after-3, E-after-3, E-after-4, E-after-5

Answer format: one value per key

Question 62 handle-dispatch · mapping · 1 pt · 07-error-handling

BadDigit : ErrorInfo<BadDigit, ParseErr> and ParseErr : ErrorInfo<ParseErr>. An
Error holds an ErrorList with three payloads: a BadDigit, a StringError and a
ParseErr. It is passed to

handleErrors(std::move(E),
             [](const ParseErr &) { … },     // h1
             [](const BadDigit &) { … });    // h2

Which handler takes each payload (h1, h2 or unhandled, meaning returned in the
result)?

Keys: BadDigit, StringError, ParseErr

Answer format: one value per key

Question 63 eh-zero-cost · single · 1 pt · 07-error-handling

Under the Itanium ABI's table-based ("zero-cost") exception handling, what does a call
inside a try block cost when it does not throw?

A test of a global "exception pending" flag after the call
A setjmp at the start of the try
Nothing extra at run time on that path: the invoke becomes an ordinary call, and the landing pad is found through the LSDA tables only during unwinding. The costs are table size, constrained optimization around invoke, and very expensive throws
A heap allocation for the exception object

Answer format: one letter

Question 64 eh-invoke-count · number · 1 pt · 07-error-handling

struct G { ~G(); };
void a(); void b(); void c(); void d() noexcept;
void f() {
  try { a(); d(); b(); } catch (...) {}
  G g;
  c();
}

compiled with clang++-23 -O0 -S -emit-llvm (exceptions enabled). How many invoke
instructions does @_Z1fv contain?

Answer format: a number

Question 65 std-expected-and-then · mapping · 1 pt · 07-error-handling

auto r = f1("12")        // parses: returns 12
           .and_then(f2)  // x -> expected(x * 2)
           .and_then(f3)  // x -> x > 20 ? unexpected("big") : expected(x)
           .and_then(f4); // x -> expected(x + 1)

Was each function called or skipped? What is result: the value, or the error
string?

Keys: f1, f2, f3, f4, result

Answer format: one value per key

Question 66 std-expected-unchecked · single · 1 pt · 07-error-handling

Which statement about ignoring a failing std::expected<int, E> is true?

Its destructor aborts, like an unchecked llvm::Expected in a checking build
std::expected has no checked state: a failure that is simply ignored is not detected at run time. The only guard is the [[nodiscard]] warning when the whole return value is discarded
It throws bad_expected_access when it goes out of scope
It logs the error to stderr

Answer format: one letter

Question 67 interp-crossover · number · 1 pt · 08-running-ir-and-linking-llvm

The interpreter takes $t_i = 62$ ns per executed IR instruction, compiled code takes
$t_c = 2$ ns, and LLJIT's compilation costs $K = 18$ ms up front. Above how many executed
instructions $I$ is the JIT faster? (Proposition 10.8.12.)

Answer format: a number

Question 68 interp-intrinsics · single · 1 pt · 08-running-ir-and-linking-llvm

What happens when lli -force-interpreter runs a module whose main calls
llvm.abs.i32?

It returns an llvm::Error that lli prints
The process aborts with "LLVM ERROR: Code generator does not support intrinsic function 'llvm.abs.i32'!" (a report_fatal_error from IntrinsicLowering)
It computes the result correctly, since all intrinsics are interpretable
It silently returns 0

Answer format: one letter

Question 69 mcjit-status · single · 1 pt · 08-running-ir-and-linking-llvm

Which statement about MCJIT in LLVM 23 is right?

It was removed in LLVM 17
It is still in the tree (lli -jit-kind=mcjit, EngineBuilder), compiles whole modules with the regular code generator and links them with RuntimeDyld, and is superseded by ORC for new code
It is the default for lli
It compiles one function at a time, lazily

Answer format: one letter

Question 70 mcjit-compile-set · set · 1 pt · 08-running-ir-and-linking-llvm

Three modules are added to one MCJIT ExecutionEngine:

m1 defines entry (which calls used and helper), used and never_called;
m2 defines helper and unrelated;
m3 defines other, and nothing refers to it.

The host calls EE->getFunctionAddress("entry"). Which functions have been compiled
when it returns?

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

Question 71 lljit-compile-set · set · 1 pt · 08-running-ir-and-linking-llvm

With LLJIT, addIRModule adds m1 = {entry, parse, report} and
m2 = {emit, log} to the main JITDylib. entry calls only parse, report calls log,
and nothing calls emit. The host does lookup("entry") and then calls entry once.
Which functions does LLJIT compile?

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

Question 72 llvm-where-addlazy · mapping · 1 pt · 08-running-ir-and-linking-llvm

Find where LLVM does it (Lesson 10.8 §7). In
llvm/include/llvm/ExecutionEngine/Orc/LLJIT.h, class LLLazyJIT adds modules lazily.
Give the method name, and the jitdylib that its one-argument overload uses (the name
of the LLJIT member it passes).

Keys: method, jitdylib

Answer format: one value per key

Question 73 lazy-order · sequence · 1 pt · 08-running-ir-and-linking-llvm

Under LLLazyJIT (per-function partitions), one module defines entry, parse,
check, emit, log and unused. The host looks up entry and calls it once. During
that call, entry calls parse and then emit, parse calls check twice, and
emit calls check and then log. In which order are functions compiled?

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

Question 74 cmake-rtti · single · 1 pt · 08-running-ir-and-linking-llvm

Your tool derives struct MyStream : llvm::raw_ostream { … } and is compiled with
-frtti, but your LLVM was built with LLVM_ENABLE_RTTI=OFF. What typically happens?

Nothing: RTTI only matters for dynamic_cast
A link error: MyStream's type info refers to typeinfo for llvm::raw_ostream, which a -fno-rtti LLVM never emitted. Build your code with -fno-rtti (read LLVM_ENABLE_RTTI / llvm-config --has-rtti)
A crash at run time in raw_ostream::write
The compiler silently disables RTTI for MyStream

Answer format: one letter

Question 75 cxxflags-std · single · 1 pt · 08-running-ir-and-linking-llvm

This course's llvm-config --cxxflags contains -std=c++17. Which standard is in effect
for clang++-23 -std=c++23 $(llvm-config --cxxflags) f.cpp?

C++23: the first -std wins
C++17: the last -std on the command line wins, so the flag from --cxxflags overrides yours
An error: two -std flags conflict
The newer of the two

Answer format: one letter

Question 76 cmake-closure · set · 1 pt · 08-running-ir-and-linking-llvm

A (simplified) static LLVM has these "requires" edges between component libraries:

Core → BinaryFormat, Remarks, Support
Remarks → BitstreamReader, Support
BitstreamReader → Support
BinaryFormat → Support, TargetParser
TargetParser → Support
Support → Demangle
IRReader → AsmParser, BitReader, Core, Support

Which libraries must a static link of the component core contain (Definition 10.8.7)?

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