C++Now 2021 has ended
Back To Schedule
Thursday, May 6 • 9:00am - 10:30am
Algorithms from a Compiler Developer's Toolbox

Log in to save this to your schedule, view media, leave feedback and see who's attending!

Compiler construction is one of the most researched topics in computer science. As a result, there is a vast library of elegant algorithms that can find optimization opportunities in our programs. While these algorithms have excellent coverage in academic literature and advanced compiler courses, there is little discussion devoted to this topic at industrial conferences.

This session is intended to give a glimpse of the foundations modern optimizing compilers are built on, hopefully helping to develop some intuition about the capabilities of modern compilers. In this talk, I want to present two algorithms that mesmerized me with their unreasonable effectiveness. The first algorithm involves chains of recurrences, which is the theory behind LLVM's scalar evolution analysis. The second is value numbering, which is one of the first optimization passes compiler developers get to implement when they start working on a new compiler.

I will cover the theory and basic math behind these algorithms (high school math knowledge is sufficient), as well as some of the implementations in popular compilers. The talk includes lots of examples and some pointers on how to implement some of these algorithms yourself.

avatar for Gábor Horváth

Gábor Horváth

Software Engineer, Microsoft
Gabor started a Ph.D. in 2016. He is a contributor to research projects related to static analysis since 2012. He is a clang contributor, participated in Google Summer of Code twice as a student and many times as a mentor, interned for Apple, Microsoft and Google. He taught C++ and... Read More →

Thursday May 6, 2021 9:00am - 10:30am MDT