SPLASH 2020
Sun 15 - Sat 21 November 2020 Online Conference
Wed 18 Nov 2020 17:40 - 18:00 at SPLASH-I - W-6 Chair(s): Anitha Gollamudi, Hans-J. Boehm
Thu 19 Nov 2020 05:40 - 06:00 at SPLASH-I - W-6 Chair(s): John Wickerson, Jan Vitek

This paper describes a compiler optimization to eliminates dynamic occurrences
of expressions in the format $a \leftarrow a \oplus b \otimes c$.
The operation $\oplus$ must admit an identity element $z$, such that
$a \oplus z = a$.
Also, $z$ must be the absorbing element of $\otimes$, such
that $b \otimes z = z \otimes c = z$.
Semirings where $\oplus$ is the additive operator and $\otimes$ is the
multiplicative operator meet this contract.
This pattern is common in high-performance benchmarks—its canonical
representative being the multiply-add operation $a \leftarrow a + b \times c$.
However, several other expressions involving arithmetic and logic operations
satisfy the required algebra.
We show that the runtime elimination of such assignments can be implemented in
a performance-safe way via online profiling.
The elimination of dynamic redundancies involving identity and absorbing
elements in 35 programs of the LLVM test suite that present semiring patterns
brings an average speedup of 1.19x (total optimized time over total
unoptimized time) on top of clang -O3.
When projected onto the entire test suite (259 programs) the optimization leads
to a speedup of 1.025x.
Once added onto \texttt{clang}, semiring optimizations approximates it to TACO,
a specialized tensor compiler.

Conference Day
Wed 18 Nov

Displayed time zone: Central Time (US & Canada) change

17:00 - 18:20
W-6OOPSLA at SPLASH-I +12h
Chair(s): Anitha GollamudiHarvard University, Hans-J. BoehmGoogle
17:00
20m
Talk
Programming with a Read-Eval-Synth Loop
OOPSLA
Hila PelegUniversity of California at San Diego, Roi GabayTechnion, Shachar ItzhakyTechnion, Eran YahavTechnion
Link to publication DOI Media Attached
17:20
20m
Talk
Sound Garbage Collection for C using Pointer Provenance
OOPSLA
Subarno BanerjeeUniversity of Michigan, David DevecseryGeorgia Institute of Technology, Peter M. ChenUniversity of Michigan, Satish NarayanasamyUniversity of Michigan
Link to publication DOI Media Attached
17:40
20m
Talk
Semiring Optimizations: Dynamic Elision of Expressions with Identity and Absorbing Elements
OOPSLA
Guilherme Vieira LeobasFederal University of Minas Gerais, Fernando Magno Quintão PereiraFederal University of Minas Gerais
Link to publication DOI Pre-print Media Attached
18:00
20m
Talk
CompCertELF: Verified Separate Compilation of C Programs into ELF Object Files
OOPSLA
Yuting WangShanghai Jiao Tong University, Xiangzhe XuNanjing University, Pierre WilkeCentraleSupélec, Zhong ShaoYale University
Link to publication DOI Media Attached

Conference Day
Thu 19 Nov

Displayed time zone: Central Time (US & Canada) change

05:00 - 06:20
W-6OOPSLA at SPLASH-I
Chair(s): John WickersonImperial College London, Jan VitekNortheastern University / Czech Technical University
05:00
20m
Talk
Programming with a Read-Eval-Synth Loop
OOPSLA
Hila PelegUniversity of California at San Diego, Roi GabayTechnion, Shachar ItzhakyTechnion, Eran YahavTechnion
Link to publication DOI Media Attached
05:20
20m
Talk
Sound Garbage Collection for C using Pointer Provenance
OOPSLA
Subarno BanerjeeUniversity of Michigan, David DevecseryGeorgia Institute of Technology, Peter M. ChenUniversity of Michigan, Satish NarayanasamyUniversity of Michigan
Link to publication DOI Media Attached
05:40
20m
Talk
Semiring Optimizations: Dynamic Elision of Expressions with Identity and Absorbing Elements
OOPSLA
Guilherme Vieira LeobasFederal University of Minas Gerais, Fernando Magno Quintão PereiraFederal University of Minas Gerais
Link to publication DOI Pre-print Media Attached
06:00
20m
Talk
CompCertELF: Verified Separate Compilation of C Programs into ELF Object Files
OOPSLA
Yuting WangShanghai Jiao Tong University, Xiangzhe XuNanjing University, Pierre WilkeCentraleSupélec, Zhong ShaoYale University
Link to publication DOI Media Attached