Alive2: Bounded Translation Validation for LLVM
Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, 2021 · paper · Computer science
Presents Alive2, an automatic bounded translation validation tool for LLVM's intermediate representation that checks whether optimized code refines the original. Run on LLVM's unit tests, it found 47 new bugs, 28 already fixed, and prompted eight patches to the LLVM language reference.
Checked: PDF from web.ist.utl.pt, fetched 4 Oct 2026. Page numbers are those of that PDF.
5 findings
Substance The final refinement formula in §5.2 (p.8) begins "∀Isrc, Itgt, Otgt . valid(Isrc, Itgt) ∧ ..." and drops the premise Isrc ⊒ Itgt that appears in both earlier formulas (p.7).
- p. 8 Section 5.2, final refinement formula (top of left column)
∀Isrc, Itgt, Otgt . valid(Isrc, Itgt) ∧
- p. 7 Section 5.2, previous formula
∀Isrc, Itgt, Otgt . Isrc ⊒ Itgt ∧ valid(Isrc, Itgt) ∧
Only the authors can say what is right here.
Judge's note: Pages 7 and 8 checked. The p.7 formulas read '∀Isrc, Itgt . Isrc ⊒ Itgt ∧ valid(Isrc, Itgt)' and '∀Isrc, Itgt, Otgt . Isrc ⊒ Itgt ∧ valid(...)'. The p.8 text says it 'extend[s] the previous refinement condition', yet the printed final formula has only valid(Isrc, Itgt). valid is defined as the global precondition (non-null, disjoint globals) and does not cover input refinement. As printed, the condition quantifies over unrelated input pairs. Only the authors can confirm whether the omission is intended.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [8] DOI printed as "https://doi.org/110.1145/3434321" with a spurious leading '1' in the ACM prefix.
- p. 14 Reference [8]
https://doi.org/110.1145/3434321
Judge's note: The page 14 crop shows '110.1145'. Every other ACM DOI in the list (e.g. [6], [11], [26]) uses '10.1145', so the fix is evident from the paper itself.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [42] DOI printed as "https://doi.org/10.1007/978-3-642-22110-159", without the underscore found in the other Springer chapter DOIs (e.g. [9] '978-3-319-71237-6_7').
- p. 14 Reference [42]
3-642-22110-159
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the exact chapter DOI (presumably 978-3-642-22110-1_59). The page 14 crop shows '22110-159' with no underscore, while the other Springer DOIs on the page have one.
Second check: another model agreed
Report a problem with this finding
Wording Section 3: "skip inserting code to cleanup the stack and return to the callee" should say return to the caller.
- p. 4 Section 3, paragraph on final state / noreturn
to skip inserting code to cleanup the stack and return to the callee
Judge's note: Page 4 image checked (left column, end of the final-state paragraph). The skipped epilogue code returns control from the current function to its caller, so 'callee' reverses the direction.
Second check: another model agreed
Report a problem with this finding
Wording Related work: LLVM-MD and Peggy "work by rewriting the source program until it is syntactically equal to the source"; the second 'source' should be 'target'.
- p. 12 Section 9, Translation validation, last paragraph
work by rewriting the source program until it is syntactically equal to the source
- p. 12 Section 9, Translation validation
rewriting the source program until it is syntactically equal to the source
- p. 12 Related Work, LLVM-MD and Peggy
rewriting the source program until it is syntactically
- p. 12 Section 9, Translation validation
until it is syntactically equal to the source
Judge's note: Page 12 crop checked. Rewriting a program until it equals itself is vacuous. In the source/target TV context the intended comparison is with the target program.
Second check: another model agreed
Report a problem with this finding
6 minor (typos and the like; most checked by the judge only)
Wording Intro bullet "Contributing 8 patches to LLVM IR's specification document" reads as 8 patches by the authors, while §8.3 says "we wrote 5 patches and contributed advice or ideas to 3 patches written by LLVM developers".
- p. 2 Introduction, contributions list
Contributing 8 patches to LLVM IR’s specification doc-
- p. 11 Section 8.3
we wrote 5 patches and contributed advice or ideas to 3 patches written by LLVM developers
Judge's note: Both crops checked. The total is consistent (5+3=8) and the abstract's 'led to eight patches' matches §8.3. Only the intro's wording blurs authorship, so this is a minor wording point.
Second check: another model agreed
Report a problem with this finding
Typo Author block prints truncated email domains "juneyoung.lee@sf.snu.ac.k" and "gil.hur@sf.snu.ac.k" (presumably .ac.kr).
- p. 1 Author block, Juneyoung Lee
juneyoung.lee@sf.snu.ac.k
- p. 1 Author block, Chung-Kil Hur
gil.hur@sf.snu.ac.k
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: Seoul National University addresses use the .ac.kr domain. The crop of page 1 shows both addresses ending in '.ac.k', so this is not a text-layer artefact.
Second check: none (judge only)
Report a problem with this finding
Typo Figure 1 prints "%c = icmp eq %t, 0" without the operand type (i32), unlike every other typed instruction in the figure.
- p. 3 Figure 1
%c = icmp eq %t, 0
Judge's note: The page 3 crop shows 'icmp eq %t, 0', while add/shl/and all carry 'i32'. LLVM IR syntax requires the operand type, so this is a cosmetic slip in an example presented as LLVM IR.
Second check: none (judge only)
Report a problem with this finding
Typo §6 "the jth call in |C^f_src| is refined" uses the cardinality |C^f_src| where the set C^f_src is meant.
- p. 8 Section 6, SMT encoding paragraph
the jth call in |C
Judge's note: Page 8 image and text layer (line 906) both show the bars. C^f_src is defined as the set of calls and |C^f_src| is used as a number in the bound 0 ≤ i ≤ |C^f_src|. Notational slip.
Second check: none (judge only)
Report a problem with this finding
Typo Figure 5 CALL rule writes the target UB output as ub_{o'} in the premise "(M'_o, v'_o, ub_{o'}) = call(fn, args', M')" but as ub'_o in the conclusion "(ub'_o ⟹ ub_o)".
- p. 8 Figure 5, CALL rule
(M′o, v′o, ubo′) = call(fn, args′, M′)
Judge's note: Page 8 image and text layer (line 815: 'ub𝑜′' inline, while M′ and v′ carry a superscript prime) show the inconsistent prime placement. Cosmetic notation inconsistency.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [47] spells the co-author as "Sophia Drossopolou" (presumably Drossopoulou).
- p. 15 Reference [47]
Sophia Drossopolou
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the author's name is spelled Drossopoulou. The page 15 crop shows 'Drossopolou'.
Second check: none (judge only)