README

LLVM Chapter 8 Validation

This directory contains a small LLVM IR harness for checking how opt + llc lower representative Chapter 8 multiplication patterns to x86_64.

Run:

./run-ch8-validation.sh

Outputs:

• ch8-multiplication.opt.ll
• ch8-multiplication.s
• ch8-multiplication.clean.s

Suggested workflow:

1. Start from a pattern in Hacker’s Delight.
2. Encode the exact operation in LLVM IR.
3. Run opt -O2 and llc -O2.
4. Inspect *.clean.s.
5. Decide whether LLVM recognized the intended machine idiom, or whether the transform is still a source-level/manual optimization.

Current findings from ch8-multiplication.ll:

• Small constant multiplies are strength-reduced on x86_64. Examples:
  • x * 3 → lea
  • x * 5 → lea
  • x * 7 → lea plus sub
  • x * 9 → lea
  • x * 10 → add plus lea
  • x * 45 → two lea
• Larger constants are not necessarily strength-reduced. Example:
  • x * 1000 stays as imul
• The 3-multiply complex product form is preserved if you write that form in IR.
• LLVM does not rewrite the naive 4-multiply complex product into the 3-multiply variant in this test.
• Portable widened IR for high-half multiply (zext/sext → mul i64 → shift-right 32) lowered to imulq plus shrq, not to the x86 one-instruction high-half idiom using %edx:%eax.

Interpretation:

• LLVM covers a good subset of the machine-level strength reductions from the book, especially “multiply by constant” lowering.
• LLVM does not generally rediscover higher-level algebraic rewrites from the book once they are not already present in the IR.
• For validation, you should separate:
  • backend/codegen idioms that LLVM should recognize from straightforward IR
  • source-level algebraic rewrites that need to be written explicitly or taught to InstCombine/other middle-end passes