整合 LLVM SandboxIR 於超字階層平行性向量化器以支援IR還原機制藉以提升儲存指令鏈向量化效能

Abstract

超字階層平行性（Superword-Level Parallelism, SLP）是一種關鍵的向量化技術，用於從循序執行的程式碼中提取資料平行性。然而，其在現代編譯器中的效能，往往受到其底層貪婪式啟發（greedy heuristics）演算法的限制。傳統的由下而上（bottom-up）SLP 向量化器所做的決策是局部且不可逆的，這種方法雖然計算效率高，卻常常因錯失更具全域效益的指令分組機會，而導致次優的向量化結果。本論文旨在針對此一根本性限制，提出一種新穎的混合式搜索算法，該算法能系統性地探索解空間，以在成本模型之上找出真正的最優向量化序列。 我們的研究方法將 SLP 儲存指令鏈向量化問題，重新建構成一個狀態空間搜索問題，其目標是找到一條成本效益最高的向量化決策路徑。此方法的核心在於整合 LLVM SandboxIR 框架，此框架提供了一個交易式（transactional）的環境，使我們能夠執行一連串的轉換、評估其對全域成本的影響，並在必要時將其復原。這種能力讓我們得以反覆探索不同的向量化策略，而無需過早地鎖定於次優的選擇。 我們所提出的演算法搜索所有可能的向量化序列所構成的狀態空間。此方法的一項關鍵創新，是整合了基於動態規劃（Dynamic Programming, DP）的提早終止條件。這種混合設計能有效修剪搜尋空間的大部分，使尋找全域最優解在多數實際程式碼中成為可行。我們詳細分析了演算法設計、在 LLVM SLP 向量化器中的實作，以及其計算複雜度，並展示其在理論與實務上相較傳統貪婪法的優勢。本研究證明，藉由超越貪婪啟發式並善用 SandboxIR 框架，LLVM 編譯器能實現更高品質的向量化，並在成本模型下釋放更大的效能潛力。

Superword-Level Parallelism (SLP) is a crucial vectorization technique for extracting data-level parallelism from straight-line code, yet its effectiveness in modern compilers is often constrained by its underlying greedy heuristics based on the estimated-based cost model. The traditional bottom-up SLP vectorizer makes localized, irreversible decisions that, while computationally efficient, can lead to sub-optimal vectorization plans by forgoing opportunities for more globally efficient instruction groupings. This thesis addresses this fundamental limitation by proposing a novel hybrid search algorithm that systematically explores the solution space to identify a better vectorization sequence. Our methodology re-frames the SLP store-chain vectorization problem as a state-space search problem, where the goal is to find the most cost-effective path of vectorization decisions. Central to our approach is the integration of the LLVM SandboxIR, a transactional framework that enables us to apply sequences of transformations, evaluate their global cost impact, and subsequently roll them back. This capability allows for an iterative exploration of different vectorization strategies without committing to premature, sub-optimal choices. The proposed algorithm employs a iterative search to traverse the state space of possible vectorization sequences. A key innovation of our approach is the integration of a dynamic programming (DP) based early-exit condition. When the algorithm detects that the remaining un-vectorized operations have no inter-dependencies, it switches from the computationally intensive state-space search to a highly efficient DP routine to solve the remainder of the problem optimally. This hybrid design effectively prunes large portions of the search space, making the quest for a global optimum computationally feasible for a wide range of real-world code. We provide a detailed analysis of the algorithm's design, its implementation within the LLVM SLP vectorizer, and its computational complexity, demonstrating its theoretical and practical advantages over the traditional greedy approach. Our work shows that by moving beyond greedy heuristics and leveraging SandboxIR frameworks, LLVM compiler can achieve a higher quality of vectorization and unlock greater performance on the cost model.