Skip to content

Theory test — Chapter 18

69 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 18                                   # interactive
./course quiz template 18 -o answers/ch18.yaml  # or fill in a file ...
./course quiz grade 18                             # ... and grade it
Question 1 licm-hoistable-set · set · 1 pt · 01-loop-invariant-code-motion

A rotated loop in loop-simplify form (the exit test is in L). a b c n are defined
before the loop; arrays Y and Z are distinct; / is unsigned division (undefined for a
zero divisor).

P:  goto B
B:  i = phi(0 from P, i2 from L)
    t1 = a * b
    t2 = t1 + i
    t3 = a / c
    t4 = c / 4
    t5 = t1 - 7
    t6 = load Y[b]
    t7 = load Y[i]
    t8 = t6 + t1
    if (i & 1) goto C else goto L
C:  store Z[i] = t2
    goto L
L:  i2 = i + 1
    if i2 < n goto B else goto X

Which of t1…t8 does LICM (Algorithm 18.1.4) hoist to P?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 2 licm-find-safe-exec · single · 1 pt · 01-loop-invariant-code-motion

In LLVM 23.1.2's llvm/lib/Transforms/Scalar/LICM.cpp, the static function
isSafeToExecuteUnconditionally decides whether an invariant instruction may be hoisted.
What does it check, in which order?

  1. First whether the loop is rotated, then whether the instruction is a load.
  2. First isSafeToSpeculativelyExecute (if speculation is allowed); if that fails, whether the instruction is guaranteed to execute (isGuaranteedToExecute), emitting a missed-optimization remark for a conditionally executed invariant load.
  3. First isGuaranteedToExecute; only if that fails, isSafeToSpeculativelyExecute.
  4. Only MemorySSA clobber queries; speculation is decided in hoistRegion.
Answer format: one letter
Question 3 licm-sink-condition · multi · 1 pt · 01-loop-invariant-code-motion

Which conditions does Definition 18.1.5 require before LICM may sink a (pure) instruction
I of loop L into the exit blocks?

  1. I has no use inside L.
  2. Every use of I outside L is an LCSSA phi in an exit block reached from an exiting block that I's block dominates.
  3. I is guaranteed to execute on every iteration.
  4. I is safe to speculate.
  5. Every operand of I is defined outside L or in a block whose innermost loop is L.
Answer format: letters, e.g. a, c
Question 4 licm-sink-count · number · 1 pt · 01-loop-invariant-code-motion

In the last function of Lesson 18.1's sinking box
(for (i = 0; i < n; i++) t = a[i] * k; return t;), LICM sinks the getelementptr,
the load and the mul into the exit block. For n = 1000, how many of these three
instructions' executions are saved by sinking (executions before minus after)?

Answer format: a number
Question 5 promotion-conditions · multi · 1 pt · 01-loop-invariant-code-motion

for (i = 0; i < n; i++) *total += a[i]; — which facts are needed (Definition 18.1.7)
before LICM may keep *total in a register during the loop?

  1. Every access in the loop that may alias *total is a simple load or store that must-alias it (for example, total and a are restrict).
  2. Loading *total in the preheader is safe: the load in the loop is guaranteed to execute, or the pointer is dereferenceable.
  3. Storing to *total at the exits adds no store on a path that had none, or no other thread can observe the location.
  4. The loop has a constant trip count.
  5. *total is a local variable of the function.
Answer format: letters, e.g. a, c
Question 6 promotion-loads · mapping · 1 pt · 01-loop-invariant-code-motion

For for (i = 0; i < n; i++) *total += a[i]; with n = 50, count the memory operations on
*total that execute, before and after scalar promotion (Algorithm 18.1.8). Give
before: N and after: N.

Keys: before, after
Answer format: one value per key
Question 7 iv-classic-found · set · 1 pt · 02-induction-variables

One loop block in SSA form (n is defined before the loop):

i  = phi(0, i1)
s  = phi(0, s1)
p  = phi(n, i)
t  = i * 3
u  = t - 1
s1 = s + t
i1 = i + 2

Which values does classic induction-variable detection (Algorithm 18.2.2: basic IVs, then
derived IVs to a fixed point) classify as induction variables?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 8 iv-find-givs · text · 1 pt · 02-induction-variables

Open GCC 15's gcc/tree-ssa-loop-ivopts.cc near find_bivs. Basic induction variables
are "bivs". What abbreviation does the file use for the derived (general) induction
variables it finds next (as in find_givs_in_stmt)?

Answer format: a short answer
Question 9 iv-scc-order · sequence · 1 pt · 02-induction-variables

Run Tarjan's algorithm on the SSA graph of the loop of question iv-classic-found
(edges from a use to its operands, defined in the loop), starting DFS from the values in
the order i s p t u s1 i1. In which order are the SCCs completed? Name each SCC by its
header phi or, for a trivial SCC, by its value: e.g. i s p t u.

Answer format: items in order, e.g. A B C
Question 10 iv-classes · mapping · 1 pt · 02-induction-variables

Classify each value of the loop of question iv-classic-found as the SCC method does
(Definition 18.2.5): linear, polynomial, geometric, wrap-around, periodic or
monotonic. Give lines i: …, t: …, s: …, p: ….

Keys: i, t, s, p
Answer format: one value per key
Question 11 cr-product · text · 1 pt · 03-scalar-evolution-and-trip-counts

Using Lemma 18.3.4, give the chain of recurrences of the product
\(\{1,+,2\} \cdot \{0,+,1\}\) in the form {a,+,b,+,c}.

Answer format: a short answer
Question 12 cr-value · number · 1 pt · 03-scalar-evolution-and-trip-counts

Evaluate the chain of recurrences \(\{2,+,3,+,4\}\) at iteration \(n = 5\) (Definition 18.3.1).

Answer format: a number
Question 13 scev-gep-bytes · mapping · 1 pt · 03-scalar-evolution-and-trip-counts

In for (long i = 0; i < n; i++) s += a[4*i + 3]; with long *a (8-byte elements),
ScalarEvolution gives the address &a[4*i + 3] the add recurrence {(S + %a),+,T}.
Give the start offset S and the step T, both in bytes, as start: S and step: T.

Keys: start, step
Answer format: one value per key
Question 14 scev-find-addrec · text · 1 pt · 03-scalar-evolution-and-trip-counts

In LLVM 23.1.2's llvm/lib/Analysis/ScalarEvolution.cpp, createNodeForPHI hands a
loop-header phi to the function that recognizes {start,+,step} from the phi and its
latch value. What is that function called?

Answer format: a short answer
Question 15 tc-ne-i8 · number · 1 pt · 03-scalar-evolution-and-trip-counts

for (u8 i = 0; i != 100; i += 3) with wrapping 8-bit arithmetic. How many times does
the body run (Theorem 18.3.13)?

Answer format: a number
Question 16 tc-wrap · mapping · 1 pt · 03-scalar-evolution-and-trip-counts

Unsigned 8-bit loops with wrapping addition (Theorem 18.3.14). Give the trip count of
each, or infinite:

  • A: for (u8 i = 248; i < 254; i += 5)
  • B: for (u8 i = 252; i < 255; i += 2)
Keys: A, B
Answer format: one value per key
Question 17 ack-temp-init · mapping · 1 pt · 04-strength-reduction

Allen–Cocke–Kennedy strength reduction (Algorithm 18.4.2) of the derived induction
variable j = 6*i + 5, where i is basic with start 2 and step 3: give the new
temporary's initial value in the preheader and its increment per iteration, as
init: N and step: N.

Keys: init, step
Answer format: one value per key
Question 18 ack-counts · single · 1 pt · 04-strength-reduction

On the lab corpus, classic ACK strength reduction left one multiplication in matrix
and weighted (Lesson 18.4's measurement table). Why can't ACK remove a multiplication
like j * m inside the inner loop of a matrix walk when m is defined outside the loop
but j is an induction variable of the outer loop only?

  1. Because m is not a constant: ACK only reduces multiplications by literal constants.
  2. Because in the inner loop j * m is loop-invariant, not an induction variable of that loop: it is LICM's job (hoist it), and only after that can the outer loop's reduction apply.
  3. Because ACK never handles nested loops.
  4. Because the multiplication might overflow.
Answer format: one letter
Question 19 osr-reduce-cr · mapping · 1 pt · 04-strength-reduction

OSR reduces t = i * 4 where i = phi(0, i1), i1 = i + 1 (Algorithm 18.4.6). The new
phi it creates for t is r = phi(A, r1) with r1 = r + B. Give A and B as
start: A and step: B.

Keys: start, step
Answer format: one value per key
Question 20 osr-find-slsr · single · 1 pt · 04-strength-reduction

Open GCC 15's gcc/gimple-ssa-strength-reduction.cc. What kind of code does this pass
strength-reduce?

  1. Only loop induction variables, like OSR.
  2. Straight-line code: related multiplications and address computations (candidates with a common base and stride) in the dominator tree, independently of loops.
  3. Only floating-point divisions.
  4. Only vector code after vectorization.
Answer format: one letter
Question 21 lsr-scale-illegal · number · 1 pt · 04-strength-reduction

LSR prices formulae with the target's addressing modes (Definition 18.4.8). On x86-64 a
memory operand is base + index*scale + disp with scale ∈ {1, 2, 4, 8}, so for the use
a[3*i] with 8-byte elements the formula reg(%a) + 24*reg(%i) is not a legal
addressing mode. LSR instead chooses a single pointer induction variable p with
address [p]. By how many bytes does p step per iteration?

Answer format: a number
Question 22 lsr-find-solve · text · 1 pt · 04-strength-reduction

In LLVM 23.1.2's LoopStrengthReduce.cpp, which LSRInstance member function
recursively searches for the cheapest assignment of one formula per use?

Answer format: a short answer
Question 23 lftr-limit · number · 1 pt · 04-strength-reduction

After strength reduction, the only use of i (i = 0, 1, …, exit when i == 100) is the exit
test, and a pointer IV p = {a,+,8} remains. LFTR (Algorithm 18.4.11) rewrites the test
as p != a + L. What is L in bytes?

Answer format: a number
Question 24 lftr-wrap · single · 1 pt · 04-strength-reduction

LFTR replaces i32 i < n by a test on a wider or narrower counter only under some
condition. Which condition does Theorem 18.4.13 need for the replacement to be correct?

  1. The new counter must not wrap before reaching its limit, i.e. the limit expression is reached exactly (no overflow between the start and the exit value).
  2. The new counter must be a pointer.
  3. The loop must have a constant trip count.
  4. No condition: LFTR is always legal.
Answer format: one letter
Question 25 rotate-guard · single · 1 pt · 05-loop-restructuring

After rotating for (i = 0; i < n; i++) body; (Algorithm 18.5.2), what does the guard
before the loop test?

  1. 0 < n: whether the first iteration runs at all (a copy of the header test on the initial values).
  2. i + 1 < n.
  3. n > 1.
  4. Nothing: rotated loops have no guard.
Answer format: one letter
Question 26 rotate-tests · mapping · 1 pt · 05-loop-restructuring

for (i = 0; i < n; i++) body; executes its test n + 1 times (for n ≥ 0). Count the
tests executed after rotation (guard plus latch tests) for n0: … (n = 0) and n5: …
(n = 5).

Keys: n0, n5
Answer format: one value per key
Question 27 peel-wraparound · single · 1 pt · 05-loop-restructuring

In x = 0; for (i = 0; i < n; i++) { use(x); x = i; }, x is a wrap-around variable.
What does peeling one iteration (Algorithm 18.5.4) achieve?

  1. In the remaining loop x is a linear induction variable (x = i − 1), so it can be strength-reduced or replaced.
  2. It removes the loop.
  3. It makes x loop-invariant.
  4. Nothing: peeling only helps conditions like i == 0.
Answer format: one letter
Question 28 peel-iterations · mapping · 1 pt · 05-loop-restructuring

Peel k = 2 iterations of for (i = 0; i < n; i++) body(i) (Algorithm 18.5.4). For
n = 1 and n = 7, how many iterations run in the peeled copies and how many in the loop?
Give n1_peeled, n1_loop, n7_peeled, n7_loop.

Keys: n1_peeled, n1_loop, n7_peeled, n7_loop
Answer format: one value per key
Question 29 unroll-remainder · mapping · 1 pt · 05-loop-restructuring

Runtime unrolling by u = 4 with an epilogue remainder (Algorithm 18.5.8) for
for (i = 0; i < n; i++). For n = 10 and n = 3, how many iterations of the unrolled loop
run and how many remainder iterations? Give n10_unrolled, n10_rem, n3_unrolled,
n3_rem.

Keys: n10_unrolled, n10_rem, n3_unrolled, n3_rem
Answer format: one value per key
Question 30 unroll-find-threshold · mapping · 1 pt · 05-loop-restructuring

In LLVM 23.1.2's LoopUnrollPass.cpp, find the size threshold for the unrolled loop used
in all optimization levels except -O3. Give the option name as name: … and its
default as value: ….

Keys: name, value
Answer format: one value per key
Question 31 unswitch-trivial · single · 1 pt · 05-loop-restructuring

When is an unswitch trivial (Definition 18.5.9)?

  1. When one successor of the invariant branch leaves the loop, so the unswitched loop needs no copy: the test moves before the loop and one outcome skips the loop.
  2. When the condition is a constant.
  3. When the loop has one block.
  4. When both successors stay in the loop.
Answer format: one letter
Question 32 unswitch-copies · number · 1 pt · 05-loop-restructuring

A loop body contains 3 independent if statements on invariant flags, none of which
exits the loop. Unswitching all of them (each unswitch applied to all copies made so
far) produces how many copies of the loop (Proposition 18.5.18)?

Answer format: a number
Question 33 version-check · mapping · 1 pt · 05-loop-restructuring

Versioning for (i = 0; i < 4; i++) a[i] += b[i]; with 8-byte elements (Algorithm
18.5.12) tests whether \([a, a + 32)\) and \([b, b + 32)\) are disjoint. With byte addresses
a = 1000, which version runs for b = 1024 and for b = 1032? Give b1024: optimized|original
and b1032: optimized|original.

Keys: b1024, b1032
Answer format: one value per key
Question 34 version-pairs · number · 1 pt · 05-loop-restructuring

A loop accesses 5 pointer groups whose relations are unknown, and every pair needs a
runtime overlap check (Proposition 18.5.18). How many checks does versioning emit?

Answer format: a number
Question 35 gcd-verdict · mapping · 1 pt · 06-dependence-analysis

Apply the GCD test (Theorem 18.6.5) to each write/read pair in a 2-deep nest over i, j
(ignore bounds). Give independent or maybe for each:

  • P1: A[2*i + 4*j] = A[2*i + 4*j + 1]
  • P2: A[4*i + 2*j] = A[6*i + 2]
  • P3: A[3*i + 6*j] = A[9*i + 1]
Keys: P1, P2, P3
Answer format: one value per key
Question 36 gcd-ignores-bounds · single · 1 pt · 06-dependence-analysis

for (i = 1; i <= 10; i++) A[i] = A[i + 100] + 1; Which statement is right?

  1. The GCD test proves independence.
  2. The GCD test says 'maybe' (gcd 1 divides 100), but Banerjee's test proves independence because |x − y| ≤ 9 over the bounds.
  3. Neither test can prove independence.
  4. Only the Omega test can prove independence.
Answer format: one letter
Question 37 banerjee-bounds · mapping · 1 pt · 06-dependence-analysis

By Lemma 18.6.7, give the minimum and maximum of \(2x - y\) over \(1 \le x, y \le 10\) under
the direction < (\(x \le y - 1\)) and the direction = (\(x = y\)). Answer with
lt_min, lt_max, eq_min, eq_max.

Keys: lt_min, lt_max, eq_min, eq_max
Answer format: one value per key
Question 38 banerjee-directions · set · 1 pt · 06-dependence-analysis

for (i = 1; i <= 10; i++) A[i + 3] = A[i] + 1; For the write (instance x) and the read
(instance y), which directions among <, =, > survive Banerjee's test (Algorithm
18.6.9)?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 39 da-find-default · text · 1 pt · 06-dependence-analysis

In LLVM 23.1.2's DependenceAnalysis.cpp, the enum DependenceTestType has a Default
value used by -da-enable-dependence-test. Which test does Default leave disabled?

Answer format: a short answer
Question 40 siv-distance · number · 1 pt · 06-dependence-analysis

Strong SIV test (Theorem 18.6.12): for (i = 0; i < 100; i++) A[2*i + 6] = A[2*i] + 1;
What is the dependence distance (in iterations) from the write to the read that uses its
value?

Answer format: a number
Question 41 siv-weak-crossing · set · 1 pt · 06-dependence-analysis

for (i = 1; i <= 19; i++) A[i] = A[20 - i] + 1; The subscript pair is weak-crossing
SIV. Which directions (<, =, >) occur between the write instance x and the read
instance y (with x + y = 20)?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 42 omega-coupled · single · 1 pt · 06-dependence-analysis

for i, j = 1..10: A[i + j][i - j] = A[i + j + 1][i - j] + 1. What do the tests conclude?

  1. GCD proves independence on the first subscript.
  2. Each subscript alone has integer solutions (GCD says maybe for both), but together they require 2x_i = 2y_i + 1, which has no integer solution: an exact test (Omega) proves independence.
  3. Banerjee's test on each subscript proves independence.
  4. There is a dependence with distance (1, 0).
Answer format: one letter
Question 43 omega-shadow · mapping · 1 pt · 06-dependence-analysis

Eliminate z from \(y \le 3z\) and \(2z \le y + 1\) (Definition 18.6.13). The real shadow is
\(y \ge R\) and the dark shadow is \(y \ge D\). Give real: R, dark: D, and
count: N, the number of values y ∈ {−3, −2, −1, 0} for which an integer z exists.

Keys: real, dark, count
Answer format: one value per key
Question 44 laa-maxvf · number · 1 pt · 06-dependence-analysis

for (i = 0; i < n; i++) a[i + 4] = a[i] * 2; with 4-byte int. By Definition 18.6.16,
what is the largest vectorization factor for which this dependence is safe?

Answer format: a number
Question 45 laa-find-kind · text · 1 pt · 06-dependence-analysis

In LoopAccessAnalysis.cpp (LLVM 23.1.2), find the DepType kinds of
MemoryDepChecker::Dependence. Which kind did LAA print for a[i + 3] = a[i] + 1 in
Lesson 18.6's box?

Answer format: a short answer
Question 46 fission-order · sequence · 1 pt · 07-dependence-driven-transformations

Distribute this loop by Algorithm 18.7.2 (one loop per strongly connected component, in
topological order, ties by textual order):

for (i = 1; i < n; i++) {
  S1: x[i] = y[i - 1] + 1;
  S2: y[i] = z[i] * 2;
  S3: w[i] = x[i] + y[i];
}

In which order are the statements' loops emitted? Answer like S1 S2 S3.

Answer format: items in order, e.g. A B C
Question 49 interchange-direction · single · 1 pt · 07-dependence-driven-transformations

In a 2-deep nest, which direction vector of a dependence makes interchanging the two
loops illegal?

  1. (=, <)
  2. (<, =)
  3. (<, <)
  4. (<, >)
Answer format: one letter
Question 51 tiling-skew-factor · number · 1 pt · 07-dependence-driven-transformations

A 2-deep nest (i outer, j inner) has distances (1, −3), (2, −1) and (0, 1). What is the
smallest skewing factor f (j' = j + f·i) that makes the band fully permutable (Lemma
18.7.8, Algorithm 18.7.7)?

Answer format: a number
Question 52 tiling-permutable · multi · 1 pt · 07-dependence-driven-transformations

For which distance sets can the (i, j) band be tiled directly, without skewing
(Theorem 18.7.16)?

  1. {(1, 0), (0, 1)}
  2. {(1, −1), (0, 1)}
  3. {(1, 2), (1, 0)}
  4. {(0, 1), (2, −3)}
Answer format: letters, e.g. a, c
Question 53 poly-wavefront · number · 1 pt · 07-dependence-driven-transformations

A statement S(i, j) over 1 ≤ i, j ≤ 5 has uniform dependences (0, 1) and (1, −2). Feautrier's
one-dimensional schedule θ(i, j) = a·i + b·j needs θ(d) ≥ 1 for each distance; the
latency-minimal choice is a = 3, b = 1. How many sequential time steps (distinct values
of θ) does the schedule have?

Answer format: a number
Question 54 poly-dataflow · number · 1 pt · 07-dependence-driven-transformations

for (i = 0; i < 10; i++) S: A[i] = A[i - 2] + 1; (A[-2], A[-1] are defined before the
loop). By exact array dataflow (Algorithm 18.7.11), which iteration's write produced the
value that iteration i = 7 reads?

Answer format: a number
Question 55 lv-iterations · mapping · 1 pt · 08-vectorization

A loop vectorized like Lesson 18.8's saxpy: VF = 8, IC = 4 (32 elements per vector
iteration), a vectorized epilogue with VF = 4, then a scalar remainder. For n = 45, how
many iterations does each part run? Give main, epilogue, scalar.

Keys: main, epilogue, scalar
Answer format: one value per key
Question 56 lv-find-epilogue · mapping · 1 pt · 08-vectorization

In LLVM 23.1.2's LoopVectorize.cpp, find the command-line option that turns epilogue
vectorization on or off. Give name: … and default: true|false.

Keys: name, default
Answer format: one value per key
Question 57 vplan-recipes · single · 1 pt · 08-vectorization

In the VPlan printed for saxpy (Lesson 18.8), the address computation
getelementptr … %x, i appears as a CLONE recipe followed by vector-pointer, while the
load appears as WIDEN. Why is the address not widened?

  1. The addresses of consecutive lanes are consecutive, so one scalar address (lane 0 of each part) and a vector load of VF adjacent elements suffice; widening it would build a vector of pointers for a gather.
  2. VPlan cannot widen getelementptr instructions.
  3. Because the address is loop-invariant.
  4. Because SSE2 has no vector loads.
Answer format: one letter
Question 58 vplan-range · mapping · 1 pt · 08-vectorization

The printed plan VF={2,4},UF>=1 serves both factors. Executed with VF = 4 and UF = 1 (no
vector epilogue) for n = 18, how many vector iterations run, and how many scalar remainder
iterations? Give vector and scalar.

Keys: vector, scalar
Answer format: one value per key
Question 59 slp-pack · set · 1 pt · 08-vectorization

Straight-line code, all arrays restrict doubles:

S0: r[0] = a[0] + b[0];
S1: r[1] = a[1] + b[1];
S2: r[2] = a[2] * b[2];
S3: r[3] = a[3] + b[3];
S4: r[5] = a[5] + b[5];

Which statements can form the largest isomorphic pack of adjacent stores rooted at
r[0] (Definition 18.8.6, without alternate-opcode nodes)?

Answer format: items separated by commas or spaces, e.g. {a, b}
Question 60 slp-cost · number · 1 pt · 08-vectorization

A 2-lane SLP tree for r[0] = a[0] + b[0]; r[1] = a[1] + b[1]; (doubles). Assume every
scalar and every vector load, store and fadd costs 1. What is the tree's cost
(vector cost minus scalar cost; negative means profitable)?

Answer format: a number
Question 61 pred-mask · mapping · 1 pt · 08-vectorization

clampneg (if (a[i] < 0) a[i] = 0;) vectorized with VF = 4 and a masked store
(Algorithm 18.8.9). For lanes a[0..3] = (−1.5, 2, −0.5, 0), give the mask as a string of
bits lane 0 first (e.g. mask: 1010) and the array after the vector iteration as
after: … in the form 0 2 0 0.

Keys: mask, after
Answer format: one value per key
Question 62 tail-fold-iterations · mapping · 1 pt · 08-vectorization

A tail-folded SVE loop (Algorithm 18.8.10) with VF = vscale × 4 runs n = 10 iterations on
a machine with vscale = 2. How many vector iterations run, and how many lanes are active in
the last one? Give iterations and last_active.

Keys: iterations, last_active
Answer format: one value per key
Question 63 bce-range · mapping · 1 pt · 09-bounds-check-elimination

xs has length 4. For each loop, does Theorem 18.9.2 make the check of the access
redundant? Answer removed or kept:

  • L1: for i in 0..4 { s += xs[i] }
  • L2: for i in 0..3 { s += xs[i + 1] }
  • L3: for i in 1..5 { s += xs[i - 1] }
  • L4: for i in 0..4 { s += xs[i + 1] }
Keys: L1, L2, L3, L4
Answer format: one value per key
Question 64 bce-wrap · single · 1 pt · 09-bounds-check-elimination

In Lesson 18.9's wrap function, if (i + 2 < len) return AT(a, len, i); with unsigned
64-bit i and len, no LLVM pass removes the check i < len. Why is that correct?

  1. Because LLVM cannot reason about unsigned values.
  2. Because i + 2 may wrap: for i = 2^64 − 1, i + 2 = 1, which can be < len while i itself is ≥ len, so the check can fail.
  3. Because the check is in a different function.
  4. Because constraint elimination is disabled at -O2.
Answer format: one letter
Question 65 bce-find-indvar · text · 1 pt · 09-bounds-check-elimination

In LLVM 23.1.2's llvm/lib/Transforms/Utils/SimplifyIndVar.cpp, which SimplifyIndvar
member function replaces a comparison involving an induction variable by a constant when
ScalarEvolution can decide it?

Answer format: a short answer
Question 66 abcd-path · number · 1 pt · 09-bounds-check-elimination

ABCD's inequality graph (Definition 18.9.4) for a check t < len contains the edges
len →(−2) n (from n ≤ len − 2), n →(−1) i₁ (π-node of i < n) and i₁ →(+2) t
(t = i₁ + 2). What is the weight of the path from len to t? (The check is redundant if
the weight is ≤ −1.)

Answer format: a number
Question 67 abcd-cycle · single · 1 pt · 09-bounds-check-elimination

While proving an upper bound, ABCD's search returns to a φ-vertex it is already visiting.
When may it answer "true" there (Algorithm 18.9.5)?

  1. Always: cycles are loops, and loops are bounded.
  2. When the bound required on the second visit is at least as large as the one it was entered with (a harmless cycle): the cycle then gives the inductive step, and the φ's other inputs give the base case.
  3. When the bound required on the second visit is smaller (an amplifying cycle).
  4. Never: ABCD gives up on cycles.
Answer format: one letter
Question 68 irce-split · mapping · 1 pt · 09-bounds-check-elimination

IRCE on for (i = 0; i < n; i++) s += AT(a, len, i); (check 0 ≤ i < len) with n = 10 and
len = 6 (Algorithm 18.9.8). Give the main loop's exit bound main_end (the value of
exit.mainloop.at), the number of main-loop iterations main_iters, and the value of i at
which the post-loop's check fails trap_at.

Keys: main_end, main_iters, trap_at
Answer format: one value per key
Question 69 predication-widen · single · 1 pt · 09-bounds-check-elimination

Loop predication widens guard(i <u len) in for (i = 0; i < n; i++) (n > 0). Which
loop-invariant condition does the widened guard test (Algorithm 18.9.9)?

  1. (0 <u len) ∧ (n − 1 <u len), i.e. the check at the first and the last iteration — equivalently n ≤ len for len ≥ 0.
  2. n <u len only.
  3. i <u len, evaluated in the preheader with i = 0.
  4. len > 0 only.
Answer format: one letter