https://www.slideshare.net/nikita_ppv/a-whirlwind-tour-of-the-llvm-optimizerpdf HomeExplore [ ]Submit Search UploadLoginSignup Advertisement A whirlwind tour of the LLVM optimizer Report Nikita Popov Nikita PopovFollow May. 10, 2023*0 likes 1 likes x Be the first to like this Show More *1,064 views views x Total views 0 On Slideshare 0 From embeds 0 Number of embeds 0 A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer A whirlwind tour of the LLVM optimizer Check these out next SR-IOV+KVM on Debian/Stable SR-IOV+KVM on Debian/Stable juet-y MySQLbatsukuatsupunoJi Ben MySQLbatsukuatsupunoJi Ben yoyamasaki Container Storage Interface nosubete Container Storage Interface nosubete You Si Yi Teng 20111015 Mian Qiang Hui (PCIe / SR-IOV) 20111015 Mian Qiang Hui (PCIe / SR-IOV) Kentaro Ebisawa Understanding DPDK Understanding DPDK Denys Haryachyy Linux Kernel Crashdump Linux Kernel Crashdump Marian Marinov Velocity 2017 Performance analysis superpowers with Linux eBPF Velocity 2017 Performance analysis superpowers with Linux eBPF Brendan Gregg LinuxkaneruwoDu ndeGai meteZhi rupurosesutosuretsudonoWei i LinuxkaneruwoDu ndeGai meteZhi rupurosesutosuretsudonoWei i Retrieva inc. 1 of 109 thumbTop clipped slide A whirlwind tour of the LLVM optimizer May. 10, 2023*0 likes 1 likes x Be the first to like this Show More *1,064 views views x Total views 0 On Slideshare 0 From embeds 0 Number of embeds 0 Download NowDownload to read offline Report Technology A high level overview of the LLVM middle-end optimization pipeline, as well as the most important optimization passes. Nikita Popov Nikita PopovFollow Advertisement Advertisement Advertisement Recommended [Container Plumbing Days 2023] Why was nerdctl made?[Container Plumbing Days 2023] Why was nerdctl made? [Container Plumbing Days 2023] Why was nerdctl made?Akihiro Suda119 views*20 slides Kernel Recipes 2015: Kernel packet capture technologiesKernel Recipes 2015: Kernel packet capture technologies Kernel Recipes 2015: Kernel packet capture technologiesAnne Nicolas 2.7K views*44 slides oreLiu noOpenJDKnoKai Fa Huan Jing (JJUG CCC 2019 FallJiang Yan Zi Liao )oreLiu no OpenJDKnoKai Fa Huan Jing (JJUG CCC 2019 FallJiang Yan Zi Liao ) oreLiu noOpenJDKnoKai Fa Huan Jing (JJUG CCC 2019 FallJiang Yan Zi Liao )NTT DATA Technology & Innovation1.8K views*41 slides Stargz Snapshotter: imezinopullwoSheng Lue shicontainerddekontenawoGao Su niQi Dong suruStargz Snapshotter: imezinopullwoSheng Lue shicontainerddekon tenawoGao Su niQi Dong suru Stargz Snapshotter: imezinopullwoSheng Lue shicontainerddekontenawoGao Su niQi Dong suruKohei Tokunaga1.3K views*26 slides CXL_Shuo Ming _Gong Kai Yong .pdfCXL_Shuo Ming _Gong Kai Yong .pdf CXL_Shuo Ming _Gong Kai Yong .pdfYasunori Goto3.2K views*59 slides ML2/OVN akitekuchiyaGai Guan ML2/OVN akitekuchiyaGai Guan ML2/OVN akitekuchiyaGai Guan Yamato Tanaka327 views*56 slides More Related Content Slideshows for you(20) SR-IOV+KVM on Debian/StableSR-IOV+KVM on Debian/Stable SR-IOV+KVM on Debian/Stable juet-y*13K views MySQLbatsukuatsupunoJi Ben MySQLbatsukuatsupunoJi Ben MySQLbatsukuatsupunoJi Ben yoyamasaki*44.3K views Container Storage Interface nosubeteContainer Storage Interface nosu bete Container Storage Interface nosubete You Si Yi Teng *9K views 20111015 Mian Qiang Hui (PCIe / SR-IOV)20111015 Mian Qiang Hui (PCIe / SR-IOV) 20111015 Mian Qiang Hui (PCIe / SR-IOV) Kentaro Ebisawa*8.4K views Understanding DPDKUnderstanding DPDK Understanding DPDK Denys Haryachyy*100.8K views Linux Kernel CrashdumpLinux Kernel Crashdump Linux Kernel Crashdump Marian Marinov*2.3K views Velocity 2017 Performance analysis superpowers with Linux eBPF Velocity 2017 Performance analysis superpowers with Linux eBPF Velocity 2017 Performance analysis superpowers with Linux eBPF Brendan Gregg*695.2K views LinuxkaneruwoDu ndeGai meteZhi rupurosesutosuretsudonoWei iLinuxkaneru woDu ndeGai meteZhi rupurosesutosuretsudonoWei i LinuxkaneruwoDu ndeGai meteZhi rupurosesutosuretsudonoWei i Retrieva inc.*5K views ZabbixdeDockermoJian Shi ZabbixdeDockermoJian Shi ZabbixdeDockermoJian Shi Atsushi Tanaka*12.9K views The ideal and reality of NVDIMM RASThe ideal and reality of NVDIMM RAS The ideal and reality of NVDIMM RAS Yasunori Goto*1.1K views BGP Session Culling - BGPniYou shiiIXnomentenansuwoMu Zhi shiteBGP Session Culling - BGPniYou shiiIXnomentenansuwoMu Zhi shite BGP Session Culling - BGPniYou shiiIXnomentenansuwoMu Zhi shite Yuya Rin*2.1K views I/OJia Xiang Hua Zui Qian Xian ~ netsutowakuI/OwoZhong Xin ni~ I/OJia Xiang Hua Zui Qian Xian ~ netsutowa kuI/OwoZhong Xin ni~ I/OJia Xiang Hua Zui Qian Xian ~ netsutowakuI/OwoZhong Xin ni~ Ryousei Takano*10.3K views JVMniLi karaShou woChu su!JVMTIniHong retemiyou(opunsosukanhuaren su2020 Online/Hiroshima Jiang Yan Zi Liao )JVMniLi karaShou woChu su!JVMTIniHong rete miyou(opunsosukanhuarensu2020 Online/Hiroshima Jiang Yan Zi Liao ) JVMniLi karaShou woChu su!JVMTIniHong retemiyou(opunsosukanhuaren su2020 Online/Hiroshima Jiang Yan Zi Liao ) NTT DATA Technology & Innovation*911 views AS45679 on FreeBSDAS45679 on FreeBSD AS45679 on FreeBSD Tomocha Potter*479 views Faster packet processing in Linux: XDPFaster packet processing in Linux: XDP Faster packet processing in Linux: XDP Daniel T. Lee*1.2K views Interrupt AffinitynitsuiteInterrupt Affinitynitsuite Interrupt Affinitynitsuite Takuya ASADA*13K views FreeBSD CapsicumFreeBSD Capsicum FreeBSD Capsicum Yuichiro Naito*834 views SR-IOV Networking in OpenStack - OpenStackZui Xin Qing Bao semina 2016Nian 3Yue SR-IOV Networking in OpenStack - OpenStackZui Xin Qing Bao semina 2016Nian 3Yue SR-IOV Networking in OpenStack - OpenStackZui Xin Qing Bao semina 2016Nian 3Yue VirtualTech Japan Inc.*3.3K views Zhi tsuteiruyoudeZhi ranaiNeutron -Jia Xiang rutanoRong Chang toFen San - - OpenStack Zui Xin Qing Bao semina 2016Nian 3Yue Zhi tsuteiruyoudeZhi ranaiNeutron -Jia Xiang ruta noRong Chang toFen San - - OpenStackZui Xin Qing Bao semina 2016Nian 3Yue Zhi tsuteiruyoudeZhi ranaiNeutron -Jia Xiang rutanoRong Chang toFen San - - OpenStack Zui Xin Qing Bao semina 2016Nian 3Yue VirtualTech Japan Inc.*7.9K views [ZigBee Qian Ru Shi Xi Tong ] ZigBee Ying Yong Shi Zuo - Shi Yong TI Z-Stack Firmware[ZigBee Qian Ru Shi Xi Tong ] ZigBee Ying Yong Shi Zuo - Shi Yong TI Z-Stack Firmware [ZigBee Qian Ru Shi Xi Tong ] ZigBee Ying Yong Shi Zuo - Shi Yong TI Z-Stack Firmware Simen Li*6.1K views Similar to A whirlwind tour of the LLVM optimizer(20) synopsys logic synthesissynopsys logic synthesis synopsys logic synthesis ssuser471b66*5 views Performance tweaks and tools for Linux (Joe Damato)Performance tweaks and tools for Linux (Joe Damato) Performance tweaks and tools for Linux (Joe Damato) Ontico*2.1K views Postgres Vision 2018: Making Postgres Even FasterPostgres Vision 2018: Making Postgres Even Faster Postgres Vision 2018: Making Postgres Even Faster EDB*352 views Debugging RubyDebugging Ruby Debugging Ruby Aman Gupta*7.2K views Debugging Ruby SystemsDebugging Ruby Systems Debugging Ruby Systems Engine Yard*4.3K views Network Programming: Data Plane Development Kit (DPDK)Network Programming: Data Plane Development Kit (DPDK) Network Programming: Data Plane Development Kit (DPDK) Andriy Berestovskyy*2.1K views LCA14: LCA14-412: GPGPU on ARM SoC sessionLCA14: LCA14-412: GPGPU on ARM SoC session LCA14: LCA14-412: GPGPU on ARM SoC session Linaro*1.3K views Cisco data center supportCisco data center support Cisco data center support Krunal Shah*4.8K views Pragmatic Optimization in Modern Programming - Ordering Optimization ApproachesPragmatic Optimization in Modern Programming - Ordering Optimization Approaches Pragmatic Optimization in Modern Programming - Ordering Optimization Approaches Marina Kolpakova*1.3K views Channel 2010Channel 2010 Channel 2010 Jing Lun Lin *748 views C++ CoreHard Autumn 2018. Concurrency and Parallelism in C++17 and C++20/23 -...C++ CoreHard Autumn 2018. Concurrency and Parallelism in C++17 and C++20/23 -... C++ CoreHard Autumn 2018. Concurrency and Parallelism in C++17 and C++20/23 -... corehard_by*165 views Lec15 Computer Architecture by Hsien-Hsin Sean Lee Georgia Tech -- EPIC VLIWLec15 Computer Architecture by Hsien-Hsin Sean Lee Georgia Tech -- EPIC VLIW Lec15 Computer Architecture by Hsien-Hsin Sean Lee Georgia Tech -- EPIC VLIW Hsien-Hsin Sean Lee, Ph.D.*825 views Modern Linux Tracing LandscapeModern Linux Tracing Landscape Modern Linux Tracing Landscape Sasha Goldshtein*1.9K views XDP in Practice: DDoS Mitigation @CloudflareXDP in Practice: DDoS Mitigation @Cloudflare XDP in Practice: DDoS Mitigation @Cloudflare C4Media*2K views design-compiler.pdfdesign-compiler.pdf design-compiler.pdf FrangoCamila*50 views Adapting to Adaptive Plans on 12cAdapting to Adaptive Plans on 12c Adapting to Adaptive Plans on 12c Mauro Pagano*1.7K views Output drops due to qo s on cisco 2960 3560 3750 switchesOutput drops due to qo s on cisco 2960 3560 3750 switches Output drops due to qo s on cisco 2960 3560 3750 switches candy tang*3.2K views CONFidence 2017: Escaping the (sand)box: The promises and pitfalls of modern ...CONFidence 2017: Escaping the (sand)box: The promises and pitfalls of modern ... CONFidence 2017: Escaping the (sand)box: The promises and pitfalls of modern ... PROIDEA*54 views When the OS gets in the wayWhen the OS gets in the way When the OS gets in the way Mark Price*198 views Building Network Functions with eBPF & BCCBuilding Network Functions with eBPF & BCC Building Network Functions with eBPF & BCC Kernel TLV*2.9K views Advertisement More from Nikita Popov(11) Opaque Pointers Are ComingOpaque Pointers Are Coming Opaque Pointers Are Coming Nikita Popov*908 views What's new in PHP 8.0?What's new in PHP 8.0? What's new in PHP 8.0? Nikita Popov*3.1K views Just-In-Time Compiler in PHP 8Just-In-Time Compiler in PHP 8 Just-In-Time Compiler in PHP 8 Nikita Popov*1.6K views What's new in PHP 8.0?What's new in PHP 8.0? What's new in PHP 8.0? Nikita Popov*10K views PHP Performance TriviaPHP Performance Trivia PHP Performance Trivia Nikita Popov*6.5K views Typed Properties and more: What's coming in PHP 7.4?Typed Properties and more: What's coming in PHP 7.4? Typed Properties and more: What's coming in PHP 7.4? Nikita Popov*10.8K views Static Optimization of PHP bytecode (PHPSC 2017)Static Optimization of PHP bytecode (PHPSC 2017) Static Optimization of PHP bytecode (PHPSC 2017) Nikita Popov*7.7K views PHP Language TriviaPHP Language Trivia PHP Language Trivia Nikita Popov*15K views PHP 7 - What changed internally? (Forum PHP 2015)PHP 7 - What changed internally? (Forum PHP 2015) PHP 7 - What changed internally? (Forum PHP 2015) Nikita Popov*7.5K views PHP 7 - What changed internally? (PHP Barcelona 2015)PHP 7 - What changed internally? (PHP Barcelona 2015) PHP 7 - What changed internally? (PHP Barcelona 2015) Nikita Popov*12.2K views PHP 7 - What changed internally?PHP 7 - What changed internally? PHP 7 - What changed internally? Nikita Popov*13.2K views Recently uploaded(20) Computational Complexity.pptxComputational Complexity.pptx Computational Complexity.pptx EnosSalar*0 views Upgrade to zOS V2.5 - Planning and Tech Actions.pdfUpgrade to zOS V2.5 - Planning and Tech Actions.pdf Upgrade to zOS V2.5 - Planning and Tech Actions.pdf Marna Walle*0 views (1)PROGRAMMING.pptx(1)PROGRAMMING.pptx (1)PROGRAMMING.pptx RavinduDolawatta1*0 views Upgrade to zOS V2.5 - Planning and Tech Actions.pdfUpgrade to zOS V2.5 - Planning and Tech Actions.pdf Upgrade to zOS V2.5 - Planning and Tech Actions.pdf Marna Walle*0 views sqlserver.pptxsqlserver.pptx sqlserver.pptx ssuser5b53e3*0 views Next.js - ReactPlayIO.pptxNext.js - ReactPlayIO.pptx Next.js - ReactPlayIO.pptx DivyanshGupta922023*0 views Giantess VR Game_ The Next Frontier in Gaming Technology.docxGiantess VR Game_ The Next Frontier in Gaming Technology.docx Giantess VR Game_ The Next Frontier in Gaming Technology.docx DenissZaletilo1*0 views WooCommerce vs Shopify: Which is Better For Your Online Store WooCommerce vs Shopify: Which is Better For Your Online Store WooCommerce vs Shopify: Which is Better For Your Online Store Andolasoft Inc*0 views GLPI in numbers (Presentacion (169)) (2).pdfGLPI in numbers (Presentacion (169)) (2).pdf GLPI in numbers (Presentacion (169)) (2).pdf DanielaBuxo1*0 views OpenACC and Hackathons Monthly Highlights: April 2023OpenACC and Hackathons Monthly Highlights: April 2023 OpenACC and Hackathons Monthly Highlights: April 2023 OpenACC*0 views Blockchain & CryptoBlockchain & Crypto Blockchain & Crypto Deepu Kurian, Ph.D*0 views Architectural Decisions: Smoothly and ConsistentlyArchitectural Decisions: Smoothly and Consistently Architectural Decisions: Smoothly and Consistently Comsysto Reply GmbH*0 views Become-GLPI-partner.pdfBecome-GLPI-partner.pdf Become-GLPI-partner.pdf DanielaBux*0 views hping3.pdfhping3.pdf hping3.pdf emadkarimi2*0 views PC Components.pptPC Components.ppt PC Components.ppt Vida533595*0 views Caper Pro Tempered Glass for Samsung Galaxy devices - Mobilesentrix.pptxCaper Pro Tempered Glass for Samsung Galaxy devices - Mobilesentrix.pptx Caper Pro Tempered Glass for Samsung Galaxy devices - Mobilesentrix.pptx Mobile Sentrix*0 views Improving Child learning through a home tutoring app.pdfImproving Child learning through a home tutoring app.pdf Improving Child learning through a home tutoring app.pdf Sandrawaniwroth*0 views 00_BVMS ExpertMaster Level Info Agenda PGV78.pdf00_BVMS ExpertMaster Level Info Agenda PGV78.pdf 00_BVMS ExpertMaster Level Info Agenda PGV78.pdf Rezaputra94*0 views Anypoint Tools and MuleSoft Automation (DRAFT).pptxAnypoint Tools and MuleSoft Automation (DRAFT).pptx Anypoint Tools and MuleSoft Automation (DRAFT).pptx Akshata Sawant*0 views Paylocity BenefitPitch Ad Slideshow.pptxPaylocity BenefitPitch Ad Slideshow.pptx Paylocity BenefitPitch Ad Slideshow.pptx AnneMarieKiel*0 views Advertisement A whirlwind tour of the LLVM optimizer 1. A whirlwind tour of the LLVM optimizer Nikita Popov @ EuroLLVM 2023 2. Agenda * High-level overview of the middle-end optimization pipeline * Brief description of important optimization passes * Get basic idea about pass responsibilities * Learn about key restrictions/constraints 2 3. About Me * Software Engineer on Platform Tools team at Red Hat * Packaging of LLVM for Fedora, CentOS and RHEL * Upstream work on LLVM and Clang 3 4. About Me * Software Engineer on Platform Tools team at Red Hat * Packaging of LLVM for Fedora, CentOS and RHEL * Upstream work on LLVM and Clang * I work on: * The LLVM middle-end * LLVM / Rust integration * Compilation time improvements (LLVM Compile-Time Tracker) 4 5. ...ends 5 Frontend Middle-end Backend Clang Rust Swift Julia ... X86 AArch64 ARM RISCV ... 6. Default (non-LTO) pipeline 6 Module 1 Module 1' Optimize Module 2 Module 2' Module 3 Module 3' 7. Full LTO pipeline 7 Module 1 Module 1' Pre-link optimize Module 2 Module 2' Module 3 Module 3' Module M Module M' Post-link optimize Merge 8. Thin LTO pipeline 8 Module 1 Module 1' Pre-link optimize Module 2 Module 2' Module 3 Module 3' Module 2'' Module 2''' Post-link optimize Cross import Module 1'' Module 3'' Module 3''' Module 1''' 9. Default pipeline 9 Module Simplification Module Optimization Backend 10. Default pipeline 10 Module Simplification Module Optimization Backend More canonical Less canonical 11. Default pipeline 11 Module Simplification Module Optimization Backend More canonical Less canonical Inlining Mem2Reg LICM (Loop Invariant Code Motion) ... Make further opts easier 12. Default pipeline 12 Module Simplification Module Optimization Backend More canonical Less canonical Vectorization Runtime unrolling ... Make further opts harder Inlining Mem2Reg LICM ... Make further opts easier 13. Default pipeline 13 Module Simplification Module Optimization Backend More canonical Less canonical Vectorization Runtime unrolling ... Make further opts harder Inlining Mem2Reg LICM ... Make further opts easier Target-specific optimization Lowering to machine code 14. ThinLTO pipeline 14 Module 1 Simplification Module 1' Simplification Module 1' Optimization Module 2 Simplification Module 2' Simplification Module 2' Optimization Cross import Post-link Pre-link 15. ThinLTO pipeline 15 Module 1 Simplification Module 1' Simplification Module 1' Optimization Module 2 Simplification Module 2' Simplification Module 2' Optimization Cross import Post-link Pre-link Second round of inlining 16. ThinLTO pipeline 16 Module 1 Simplification Module 1' Simplification Module 1' Optimization Module 2 Simplification Module 2' Simplification Module 2' Optimization Cross import Post-link Pre-link Second round of inlining Don't run decanonicalizing transforms pre-link 17. Module Simplification 17 Early Cleanup Inlining Function Simplification Late Cleanup CGSCC Pipeline 18. CGSCC Pipeline 18 g h i f 19. CGSCC Pipeline 19 g h i simplify f simplify 20. CGSCC Pipeline 20 g,h i f simplify try inline 21. CGSCC Pipeline 21 g,h i f simplify try inline simplify 22. CGSCC Pipeline 22 g,h i f simplify try inline simplify try inline simplify 23. CGSCC Pipeline 23 g,h i f simplify try inline simplify try inline simplify Inlining sees already simplified functions! 24. Call-Graph Strongly Connected Components 24 g h i f SCC 1 SCC 2 SCC 3 No well-defined order within SCC 25. Running pipelines * opt -passes='default' == opt -O3 * opt -passes='thinlto-pre-link' * opt -passes='thinlto' * opt -passes='lto-pre-link' * opt -passes='lto' 25 26. opt -passes='default' -print-pipeline-passes annotation2metadata,forceattrs,inferattrs,coro-early,function (lower-expect,simplifycfg,sroa,early-cse <>,callsite-splitting),openmp-opt,ipsccp,called-value-propagation,globalopt,function (mem2reg,instcombine ,simplifycfg),require ,function(invalidate),require,cgscc(devirt<4>(inline ,inline,function-attrs ,argpromotion,openmp-opt-cgscc,function< eager-inv;no-rerun>(sroa,early-cse ,speculative-execution,jump-threading,correlated-propagation,simplifycfg ,instcombine ,aggressive-instcombine,constraint-elimination,libcalls-shrinkwrap ,tailcallelim,simplifycfg,reassociate,loop-mssa (loop-instsimplify,loop-simplifycfg,licm ,loop- rotate,licm ,simple-loop-unswitch),simplifycfg,instcombine,loop (loop-idiom,indvars,loop-deletion,loop-unroll-full),sroa ,vector-combine,mldst-motion,gvn <>,sccp,bdce,instcombine,jump-threading,correlated-propagation,adce,memcpy opt,dse,move-auto-init,loop-mssa(licm ),coro-elide,simplifycfg,instcombine),function-attrs,function(require ),coro-split)),deadargelim,coro-cleanup,globalopt,glob aldce,elim-avail-extern,rpo-function-attrs,recompute-globalsaa,function (float2int,lower-constant-intrinsics,chr,loop( loop-rotate,loop-deletion),loop-distribute,inject-tli-mappings,loop-vectorize ,loop-load-elim,instcombine,simplifycfg,slp-vectorizer,vector-combine,instcombine,loop-unroll ,transform-warning,sroa,instcombine ,loop-mssa(licm ),alignment-from-assumptions,loop-sink,instsimplify,div-rem-pairs,tailcallelim,simpl ifycfg),globaldce,constmerge,cg-profile,rel-lookup-table-converter,function (annotation-remarks),verify,print 26 Defined in PassBuilderPipelines.cpp 27. godbolt.org - LLVM Opt Pipeline 27 28. godbolt.org - LLVM Opt Pipeline 28 29. godbolt.org - LLVM Opt Pipeline 29 Or run opt -print-after-all locally 30. 30 31. SSA Construction 31 32. Mem2Reg int test(int x, int y) { return x + y; } 32 33. Mem2Reg define i32 @test(i32 %x, i32 %y) { entry: %x.addr = alloca i32 %y.addr = alloca i32 store i32 %x, ptr %x.addr store i32 %y, ptr %y.addr %0 = load i32, ptr %x.addr %1 = load i32, ptr %y.addr %add = add nsw i32 %0, %1 ret i32 %add } 33 34. Mem2Reg define i32 @test(i32 %x, i32 %y) { entry: %add = add nsw i32 %x, %y ret i32 %add } 34 35. SROA: Scalar Replacement of Aggregates * Break up allocas into smaller allocas based on access pattern * %vec = alloca { ptr, i64, i64 } * -> %vec.ptr = alloca ptr * -> %vec.size = alloca i64 * -> %vec.capacity = alloca i64 35 36. SROA: Scalar Replacement of Aggregates * Break up allocas into smaller allocas based on access pattern * %vec = alloca { ptr, i64, i64 } * -> %vec.ptr = alloca ptr * -> %vec.size = alloca i64 * -> %vec.capacity = alloca i64 * Then run Mem2Reg to convert alloca/load/store to SSA values 36 37. SROA: Scalar Replacement of Aggregates * Break up allocas into smaller allocas based on access pattern * %vec = alloca { ptr, i64, i64 } * -> %vec.ptr = alloca ptr * -> %vec.size = alloca i64 * -> %vec.capacity = alloca i64 * Then run Mem2Reg to convert alloca/load/store to SSA values * Knows many tricks for overlapping accesses * For example inserting/extracting bits of a larger integer 37 38. Control-Flow Optimization 38 39. SimplifyCFG * The kitchen sink of control-flow transforms * If it fits nowhere else, put it here! 39 40. SimplifyCFG: Hoist if (cond) { foo(); a(); } else { foo(); b(); } 40 foo(); if (cond) { a(); } else { b(); } 41. SimplifyCFG: Speculate if (cond) { x = foo(); } else { x = 0; } 41 tmp = foo(); x = cond ? tmp : 0; 42. SimplifyCFG: Switch to lookup table switch (x) { case 0: return 10; case 1: return 42; case 2: return 123; case 3: return 7; default: return 13; } 42 int table[] = {10, 42, 123, 7}; if (x < 4) { return table[x]; } else { return 13; } 43. SimplifyCFG * The kitchen sink of control-flow transforms * If it fits nowhere else, put it here! * Invoked with many different options at different pipeline positions * Some transforms only run late in the pipeline 43 44. SimplifyCFG * The kitchen sink of control-flow transforms * If it fits nowhere else, put it here! * Invoked with many different options at different pipeline positions * Some transforms only run late in the pipeline * Can use target-dependent cost model (via TargetTransformInfo) 44 45. Instruction Combining (Peephole Optimization) 45 46. InstCombine * The kitchen sink of non-CFG transforms * If it fits nowhere else, put it here! 46 47. InstCombine: Analysis helpers 47 InstCombine InstSimplify ConstantFolding 48. InstCombine: Analysis helpers * ConstantFolding * Folds instructions with constant operands to constants * 1 + 2 => 3 48 49. InstCombine: Analysis helpers * ConstantFolding * Folds instructions with constant operands to constants * 1 + 2 => 3 * InstSimplify * Folds instructions to existing values or constants * x + 0 => x * x - x => 0 49 50. InstCombine: Analysis helpers * ConstantFolding * Folds instructions with constant operands to constants * 1 + 2 => 3 * InstSimplify * Folds instructions to existing values or constants * x + 0 => x * x - x => 0 * InstCombine * Tries constant folding and instruction simplification first * Performs folds that create or modify instructions * x * 4 => x << 2 50 51. InstCombine * The kitchen sink of non-CFG transforms * If it fits nowhere else, put it here! * Use InstSimplify / ConstantFolding for transforms that don't create/modify instructions. 51 52. InstCombine * The kitchen sink of non-CFG transforms * If it fits nowhere else, put it here! * Use InstSimplify / ConstantFolding for transforms that don't create/modify instructions. * Also used to paper over phase ordering issues * InstCombine re-implements weak versions of transforms from other passes * For example: Basic store-to-load forwarding (usually done by EarlyCSE/GVN) 52 53. ...Combine * InstCombine * Canonicalization pass: Cannot be target-dependent * Backend implements reverse/undo transform if necessary 53 54. ...Combine * InstCombine * Canonicalization pass: Cannot be target-dependent * Backend implements reverse/undo transform if necessary * AggressiveInstCombine * For expensive transforms, only runs once in pipeline * Target-dependence discouraged but sometimes allowed 54 55. ...Combine * InstCombine * Canonicalization pass: Cannot be target-dependent * Backend implements reverse/undo transform if necessary * AggressiveInstCombine * For expensive transforms, only runs once in pipeline * Target-dependence discouraged but sometimes allowed * VectorCombine * For target-dependent, cost-model driven vector transforms 55 56. CVP: CorrelatedValuePropagation * Optimizations based on value range information (from LazyValueInfo) * Important for bounds check elimination * icmp ult i32 %x, 10 => i1 true if %x in [0, 10) 56 57. CVP: CorrelatedValuePropagation * Optimizations based on value range information (from LazyValueInfo) * Important for bounds check elimination * icmp ult i32 %x, 10 => i1 true if %x in [0, 10) * Other range based optimizations * sdiv i32 %x, %y => udiv i32 %x, %y if %x, %y non-negative 57 58. Same transform, different analysis 58 * Some folds (e.g. sdiv -> udiv) are implemented in multiple passes * Folds are driven by different analyses, which are good at different things 59. Same transform, different analysis 59 InstCombine ValueTracking (KnownBits) CorrelatedValue Propagation LazyValueInfo IndVarSimplify ScalarEvolution IPSCCP ValueLattice + PredicateInfo * Some folds (e.g. sdiv -> udiv) are implemented in multiple passes * Folds are driven by different analyses, which are good at different things 60. Redundancy Elimination 60 61. EarlyCSE: Common Subexpression Elimination 61 add1 = x + y; // ... add2 = x + y; use(add1); use(add2); add1 = x + y; // ... use (add1); use(add1); 62. EarlyCSE: Common Subexpression Elimination * Basic CSE based on scoped hash table * Load CSE and store-to-load forwarding using MemorySSA 62 63. EarlyCSE: Store to load forwarding 63 *p = v1; // p not written here v2 = *p; use(v1); use(v2); *p = v1; use(v1); use(v1); 64. GVN: Global Value Numbering * More general (and much more expensive!) than EarlyCSE * Uses MemoryDependenceAnalysis * Non-local load CSE * Partial redundancy elimination (PRE) 64 65. GVN: Non-local load CSE 65 if (...) { v1 = *p; } else { *p = v2; } v3 = *p; use(v3); if (...) { v1 = *p; } else { *p = v2; } v3 = phi(v1, v2); use(v3); 66. GVN: Load PRE 66 if (...) { } else { *p = v1; } v2 = *p; use(v2); if (...) { v2_pre = *p; } else { *p = v1; } v2 = phi(v2_pre, v1); use(v2); 67. Memory Optimizations 67 68. MemCpyOpt * Optimize memcpy and memset using MemorySSA 68 69. MemCpyOpt: Memcpy forwarding 69 memcpy(y, x, 16); // y not written here memcpy(z, y, 16); memcpy(y, x, 16); // y not written here memcpy(z, x, 16); 70. MemCpyOpt: Call Slot Optimization 70 Ty tmp; foo(tmp); memcpy (dst, tmp, sizeof(Ty)); foo(dst); 71. DSE: Dead Store Elimination * Remove dead stores using MemorySSA 71 72. DSE: Dead Store Elimination 72 *p = v1; // p not read here *p = v2; // p not read here *p = v2; 73. DSE: Dead before return 73 %p = alloca i32 ; ... store i32 %v, ptr %p ; %p not read here ret void %p = alloca i32 ; ... ; %p not read here ret void 74. Loop Optimization 74 75. Loop pass manager * Visit child loops first, then parent loops * Constructs LoopSimplify and LCSSA (Loop-Closed SSA) form before running 75 76. 76 Preheader Exit Loop LICM: Hoist x = foo(); use(x); y = bar(); use(y); 77. 77 Preheader Exit Loop LICM: Hoist use(x); y = bar(); use(y); x = foo(); 78. 78 Preheader Exit Loop LICM: Sink use(x); y = bar(); use(y); x = foo(); 79. 79 Preheader Exit Loop LICM: Sink use(x); y = bar(); use(y); x = foo(); 80. 80 Preheader Exit Loop LICM: Promote v = *p; vn = v + 1; *p = vn; 81. 81 Preheader Exit Loop LICM: Promote v = phi(v0, vn); vn = v + 1; *p = vn; v0 = *p; 82. LICM: Loop Invariant Code Motion * Transforms: * Hoist instructions into preheader * Sink instructions into exits * Promote scalars * Uses MemorySSA * Canonicalization pass: Cannot be target or PGO dependent * May be undone by LoopSink or MachineSink 82 83. IndVarSimplify * Uses ScalarEvolution analysis * Simplify induction variables (IVs) and their uses * Simplify loop exit conditions 83 84. IndVarSimplify: Loop exit value replacement unsigned test (unsigned n) { unsigned sum = 0; for (unsigned i = 0; i <= n; i++) { sum += i; } return sum; } 84 85. IndVarSimplify: Loop exit value replacement unsigned test (unsigned n) { unsigned sum = 0; for (unsigned i = 0; i <= n; i++) { sum += i; } return sum; } unsigned test(unsigned n) { for (unsigned i = 0; i <= n; i++) {} return (n * (n - 1))/2 + n; } 85 86. IndVarSimplify: Loop exit value replacement unsigned test (unsigned n) { unsigned sum = 0; for (unsigned i = 0; i <= n; i++) { sum += i; } return sum; } unsigned test(unsigned n) { for (unsigned i = 0; i <= n; i++) {} return (n * (n - 1))/2 + n; } 86 Later removed by LoopDeletion 87. LoopUnroll: Full unrolling 87 Iteration #1 Iteration #2 Iteration #3 Iteration #4 Iteration #1-4 88. LoopUnroll: Loop peeling 88 Iteration #1-N Iteration #1 Iteration #2-N 89. LoopUnroll: Partial unrolling 89 Iteration #(4i+1) Iteration # (4i+2) Iteration #(4i+3) Iteration #(4i+4) Iteration #1-400 90. LoopUnroll: Runtime unrolling 90 Iteration #(4i+1) Iteration # (4i+2) Iteration #(4i+3) Iteration #(4i+4) Iteration #1-N Tail iterations 91. LoopUnroll * Simplification: * Full unrolling (requires known constant trip count) * Loop peeling * Optimization: * Partial unrolling (requires known constant trip count/multiple) * Runtime unrolling 91 92. Vectorization 92 93. LoopVectorize * VPlan to model vectorization without IR changes * LoopAccessAnalysis to ensure memory dependences are safe * May require inserting runtime checks and LoopVersioning 93 94. SLPVectorize * SLP = Superword-Level Parallelism * Vectorizes straight-line code 94 95. Inter-Procedural Optimization (IPO) 95 96. FunctionAttrs * Infer attributes on function, arguments and return values * nounwind, readonly, nonnull, etc. 96 97. FunctionAttrs * Infer attributes on function, arguments and return values * nounwind, readonly, nonnull, etc. * General approach: * Optimistically all functions in the SCC are nounwind * Check whether there are any non-nounwind instructions * If not, mark all functions in the SCC nounwind 97 98. FunctionAttrs * Infer attributes on function, arguments and return values * nounwind, readonly, nonnull, etc. * General approach: * Optimistically all functions in the SCC are nounwind * Check whether there are any non-nounwind instructions * If not, mark all functions in the SCC nounwind * New "Attributor" implements much stronger version of this, but not enabled by default (too slow) 98 99. IPSCCP: Inter-Procedural Sparse Conditional Constant Propagation * Propagates constants and constant ranges across functions * Uses PredicateInfo to take branch conditions into account 99 100. IPSCCP: Inter-Procedural Sparse Conditional Constant Propagation * Propagates constants and constant ranges across functions * Uses PredicateInfo to take branch conditions into account * Runs very early, before most simplification (which may lose information) 100 101. IPSCCP: Inter-Procedural Sparse Conditional Constant Propagation * Propagates constants and constant ranges across functions * Uses PredicateInfo to take branch conditions into account * Runs very early, before most simplification (which may lose information) * Also does function specialization (since recently) 101 102. Thank You! Questions? 102 103. The End * Blog: https://www.npopov.com/ * Reach me at: * npopov@redhat.com * https://twitter.com/nikita_ppv 103 104. Bonus Slides 104 105. JumpThreading 105 if (x > 10) { greater10(); } always(); if (x > 0) { greater0(); } if (x > 10) { greater10(); always(); greater0 (); } else { always(); } 106. JumpThreading * Optimizes conditional branches where one condition implies another * Uses LazyValueInfo analysis, which provides value range information 106 107. 107 Header Latch Preheader Exit 1 Exit 2 Loop Backedge Loop 108. 108 Header Latch Preheader Exit 1 Exit 2 Loop Backedge LoopSimplify Form 109. SimpleLoopUnswitch while (...) { if (c) { foo(); } else { bar(); } } 109 if (c) { while (...) { foo(); } } else { while (...) { bar(); } } Advertisement AboutSupportTermsPrivacyCopyrightCookie PreferencesDo not sell or share my personal information English Current LanguageEnglish Espanol Portugues Francais Deutsche --------------------------------------------------------------------- (c) 2023 SlideShare from Scribd