Semiring Optimizations: Dynamic Elision of Expressions with Identity and Absorbing Elements
summary
A compiler pass detects semiring patterns (c = c + ab) in LLVM IR and inserts speculative checks so identity/absorbing elements elide work; implemented in LLVM 6.0.1, tested on an Intel Core i7 against Clang -O3 and TACO. It finds the pattern in 126 LLVM tests, evaluates 35 long-running benchmarks, and yields average speedup 1.06 with some kernels hitting nearly 3x speedup; some slowdowns occur. Four strategies include silent store elimination and pre-loop profiling (PLP)*, with PLP the fastest and matching TACO when zeros exceed ~50–55%.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:18Semiring Optimization: Dynamic Elision of Expressions with Identity and Absorbing Elements
- 1:18Goal
- 1:38Possible Optimization
- 2:58The Algorithm For Identifying Insertion Points
- 4:40Proposed Solutions
- 5:10Matrix Multiplication Algorithm
- 5:25Silent Store Elimination (SSE)
- 5:57Elision of Absorbing Elements (EAE)
- 7:12What if?
- 7:29Intra-Loop Profile (ALP)
- 10:28Setup
- 10:53Prevalence of Ring Patterns
- 11:55Speedup
- 13:27Comparison with TACO
- 15:13Final Notes
related talks
27mCompiler Support for Control-Flow Linearization Using Architectural Mimicry
20mVectorizing Sparse Coiteration for Two-finger Loop Structure (Extended Abstract)
25mThe Road Not Taken: Exploring Alias Analysis Based Optimizations Missed by the Compiler
21mTowards Compiler-Guided Static Analysis
37mDealing with aliasing using contracts
16mReconciling Optimization With Secure Compilation
19mExploiting Undefined Behavior in C/C++ Programs for Optimization: A Study on the(…)
26mWhen C++ Zero-Cost Abstraction fails: how-to Fix Your Compiler