If-conversion is a fundamental technique for vectorization. It accounts for the fact that in a SIMD program, several targets of a branch might be executed because of divergence. Especially for irregular data-parallel workloads, it is crucial to avoid if-converting non-divergent branches to increase SIMD utilization. In this paper, we present partial linearization, a simple and efficient if-conversion algorithm that overcomes several limitations of existing if-conversion techniques. In contrast to prior work, it has provable guarantees on which non-divergent branches are retained and will never duplicate code or insert additional branches. We show how our algorithm can be used in a classic loop vectorizer as well as to implement data-parallel languages such as ISPC or OpenCL. Furthermore, we implement prior vectorizer optimizations on top of partial linearization in a more general way. We evaluate the implementation of our algorithm in LLVM on a range of irregular data analytics kernels, a neutronics simulation benchmark and NAB, a molecular dynamics benchmark from SPEC2017 on AVX2, AVX512, and ARM Advanced SIMD machines and report speedups of up to 146 % over ICC, GCC and Clang O3.

Simon Moll

Sebastian Hack

ACM SIGPLAN Notices

ACM 编程语言特别兴趣小组探索编程语言概念和工具，重点关注设计、实现、实践和理论。其成员包括编程语言开发者、教育者、实施者、研究人员、理论家和用户。 SIGPLAN 赞助了数个重要的年度会议，包括编程语言原理研讨会（POPL）、并行编程原理与实践研讨会（PPOPP）、编程语言设计与实现会议（PLDI）、函数式编程国际会议(ICFP)、面向对象编程、系统、语言和应用程序国际会议 (OOPSLA)，以及其他十多个规模较小或与其他 SIG 合作的活动。每月的“ACM SIGPLAN 通知”发布选定赞助活动的记录和关于 SIGPLAN 活动的年度报告。会员可享受会议注册折扣，并可免费访问 ACM 数字图书馆中的 ACM SIGPLAN 出版物。 SIGPLAN 通过各种奖项表彰个人的重大研究和服务贡献，通过专业活动委员会支持现有成员，并通过频繁的编程语言指导研讨会 (PLMW) 鼓励未来的编程语言爱好者。

ACM SIGPLAN Notices is the journal of the ACM Special Interest Group on Programming Languages, focusing on concepts and tools related to programming languages, including design, implementation, practice, and theory. Its members include developers, educators, implementers, researchers, theorists, and users of programming languages. SIGPLAN sponsors several important annual conferences, including the Symposium on Principles of Programming Languages (POPL), the Symposium on Principles and Practice of Parallel Programming (PPOPP), the Conference on Programming Language Design and Implementation (PLDI), the International Conference on Functional Programming (ICFP), the International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), and more than a dozen smaller events in collaboration with other SIGs. The monthly ACM SIGPLAN Notices publishes records of selected sponsored events and annual reports on SIGPLAN activities. Members benefit from discounted conference registrations and free access to ACM SIGPLAN publications in the ACM Digital Library. SIGPLAN recognizes significant research and service contributions through various awards, supports existing members through its professional activities committee, and encourages future programming language enthusiasts through frequent Programming Language Mentoring Workshops (PLMW).

ACM SIGPLAN Notices 是 ACM 编程语言特别兴趣小组的期刊，专注于编程语言的概念和工具，涵盖设计、实现、实践和理论等方面。该小组的成员包括编程语言的开发者、教育者、实施者、研究人员、理论家和用户。SIGPLAN 赞助多个重要的年度会议，包括编程语言原理研讨会（POPL）、并行编程原理与实践研讨会（PPOPP）、编程语言设计与实现会议（PLDI）、函数式编程国际会议（ICFP）、面向对象编程、系统、语言和应用程序国际会议（OOPSLA），以及其他十多个规模较小或与其他 SIG 合作的活动。每月发布的“ACM SIGPLAN 通知”记录了选定赞助活动的情况，并提供关于 SIGPLAN 活动的年度报告。会员可享受会议注册折扣，并可免费访问 ACM 数字图书馆中的 ACM SIGPLAN 出版物。SIGPLAN 通过各种奖项表彰个人在研究和服务方面的重大贡献，并通过专业活动委员会支持现有成员，同时通过频繁的编程语言指导研讨会（PLMW）鼓励未来的编程语言爱好者。

Partial control-flow linearization

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info