2018 EuroLLVM Developers’ Meeting: J. Absar “Scalar Evolution - Demystified”

http://llvm.org/devmtg/2018-04/ — Scalar Evolution - Demystified - J. Absar, Arm Slides: http://llvm.org/devmtg/2018-04/slides/Absar-ScalarEvolution.pdf — This is a tutorial/technical-talk proposal for an illustrative and in-depth exposition of Scalar Evolution in LLVM. Scalar Evolution is an LLVM analysis that is used to analyse, categorize and simplify expressions in loops. Many optimizations such as - generalized loop-strength-reduction, parallelisation by induction variable (vectorization), and loop-invariant expression elimination - rely on SCEV analysis. However, SCEV is also a complex topic. This tutorial delves into how exactly LLVM performs the SCEV magic and how it can be used effectively to implement and analyse different optimisations. This tutorial will cover the following topics: What is SCEV? How does it help improve performance? SCEV in action (using simple clear examples). hain of Recurrences - which forms the mathematical basis of SCEV. Simplifying/rewriting rules in CR that SCEV uses to simplify expressions evolving out of induction variables. Terminology and SCEV Expression Types (e.g. AddRec) that is common currency that one should get familiar with when trying to understand and use SCEV in any context. LLVM SCEV implementation of CR - what's present and what's missing? How to use SCEV analysis to write your own optimisation pass? Usage of SCEV by LSR (Loop Strength Reduce) and others. How to generate analysis info out of SCEV and how to interpret them. The last talk on SCEV was in LLVM-Dev 2009. This tutorial will be complementary to that and go further with examples, discussions and evolution of scalar-evolution in llvm since then. The author has previously given a talk on machine scheduler in llvm - https://www.youtube.com/watch?v=brpomKUynEA&t=310s — Videos Filmed & Edited by Bash Films: http://www.BashFilms.com