向量化計畫¶
摘要¶
向量化轉換可能相當複雜，涉及多種潛在的替代方案，特別是對於外層迴圈 [1]，但也可能適用於最內層迴圈。這些替代方案可能對效能產生顯著的影響，包括正面和負面影響。因此，採用成本模型來識別最佳替代方案，包括完全避免任何轉換的替代方案。
向量化計畫是一個明確的模型，用於描述向量化候選方案。它可用於最佳化候選方案，包括可靠地估算其成本，以及執行其最終轉換為 IR。這有助於處理多個向量化候選方案。
目前狀態¶
VPlan 目前用於驅動迴圈向量化中的程式碼生成。VPlan 在所有基於成本的決策和大多數與合法性相關的決策做出後構建。由於配方之間的定義-使用鏈現在已完全在 VPlan 中建模，因此基於 VPlan 的分析和轉換用於簡化和模組化向量化過程 [10]。這些包括轉換以
合法化初始 VPlan，例如，透過為歸約和交錯群組引入專門的配方。
最佳化合法化的 VPlan，例如，透過移除冗餘配方或引入活動通道遮罩。
應用特定於展開和向量化因子的最佳化，例如，根據 VF 和 UF 移除用於迭代向量迴圈的回邊。
請參考 圖 3 以取得目前轉換管線的概述。
請注意，某些合法性檢查已在 VPlan 中完成，包括檢查固定順序遞迴的所有使用者是否可以重新排序。這被實作為 VPlan 到 VPlan 的轉換，它可以應用有效的重新排序，或在將 VPlan 標記為無效時跳出。
圖 3 2024 年的 VPlan 轉換管線¶
VPlan 目前對完整的向量迴圈以及向量化骨架的其他部分進行建模。請參考 圖 4 以取得 VPlan 涵蓋範圍的概述。
圖 4 2024 年 VPlan 中建模的範圍¶
高階設計¶
向量化工作流程¶
基於 VPlan 的向量化涉及三個主要步驟，採用「基於情境的方法」進行向量化規劃
合法性步驟：檢查迴圈是否可以合法地向量化；如果可以，則編碼約束和產物。
計畫步驟
遵循合法性步驟 1 所採取的約束和決策，建立初始 VPlan，並計算其成本。
將最佳化應用於 VPlan，可能會分支額外的 VPlan。修剪具有相對較高成本的次佳 VPlan。
執行步驟：實現最佳 VPlan。請注意，這是唯一修改 IR 的步驟。
設計準則¶
在接下來的內容中，「輸入 IR」一詞指的是饋入向量化器的程式碼，而「輸出 IR」一詞指的是由向量化器產生的程式碼。輸出 IR 包含已根據迴圈向量化因子 (VF) 向量化或「加寬」的程式碼，和/或根據展開因子 (UF) 迴圈展開和阻塞的程式碼。VPlan 的設計遵循幾個高階準則
類似分析：建立和操作 VPlan 絕不能修改輸入 IR。特別是，如果最佳選項是不進行向量化，則向量化過程會在達到步驟 3 之前終止，並且編譯應像未建立 VPlan 一樣繼續進行。
對齊成本與執行：每個 VPlan 都必須支援估算成本和產生輸出 IR 程式碼，以便成本估算可靠地評估待產生的程式碼。
支援向量化額外結構
有效率地支援多個候選方案。特別是，與一系列可能的 VF 和 UF 相關的相似候選方案必須有效率地表示。需要有效率地支援潛在的版本控制。
支援向量化慣用語，例如交錯的跨步載入或儲存群組。這是透過使用「配方」對一系列輸出指令進行建模來實現的，「配方」負責計算其成本並產生其程式碼。
封裝單一入口單一出口區域 (SESE)。在向量化期間，可能需要對這些區域進行例如，預測和線性化，或複製 VF*UF 次以處理純量化和預測指令。內層迴圈也建模為 SESE 區域。
支援指令級分析和轉換，作為規劃步驟 2.b 的一部分：在向量化期間，可能需要遍歷、移動指令、用其他指令替換指令或建立指令。例如，向量慣用語偵測和形成涉及搜尋和最佳化指令模式。
定義¶
VPlan 的低階設計包含以下類別。
- LoopVectorizationPlanner:
LoopVectorizationPlanner 旨在處理迴圈或迴圈巢狀結構的向量化。它可以構建、最佳化和捨棄一個或多個 VPlan，每個 VPlan 都對迴圈或迴圈巢狀結構的不同向量化方式進行建模。一旦確定了最佳 VPlan，包括最佳 VF 和 UF，此 VPlan 將驅動輸出 IR 的生成。
- VPlan:
給定輸入 IR 迴圈或迴圈巢狀結構的向量化候選方案模型。此候選方案使用階層式 CFG 表示。VPlan 支援估算成本並驅動其表示的輸出 IR 程式碼的生成。
- 階層式 CFG:
控制流程圖，其節點是基本區塊或階層式 CFG。階層式 CFG 資料結構類似於 Tile Tree [5]，其中跨 Tile 邊緣被提升以連接 Tile，而不是像 Sharir [6] 中的原始基本區塊一樣，從而促進 Tile 封裝。術語 Region 和 Block 用於代替 Tile [5]，以避免與迴圈平鋪混淆。
- VPBlockBase:
階層式 CFG 的建構區塊。VPBasicBlock 和 VPRegionBlock 的純虛擬基底類別，請參閱下文。VPBlockBase 對與其他 VPBlock 的階層式控制流程關係進行建模。請注意，與 IR BasicBlock 相反，VPBlockBase 直接對其控制流程後繼者和前導者進行建模，而不是透過終止分支或透過「使用」VPBlockBase 的前導分支。
- VPBasicBlock:
VPBasicBlock 是 VPBlockBase 的子類別，並充當階層式 CFG 的葉節點。它表示將連續出現在輸出 IR 基本區塊中的一系列輸出 IR 指令。此基本區塊的指令源自一個或多個 VPBasicBlock。VPBasicBlock 保留零個或多個 VPRecipe 的序列，這些 VPRecipe 對輸出 IR 指令的成本和生成進行建模。
- VPRegionBlock:
VPRegionBlock 是 VPBlockBase 的子類別。它對 VPBasicBlock 和 VPRegionBlock 的集合進行建模，這些集合形成輸出 IR CFG 的 SESE 子圖。VPRegionBlock 可能指示其內容在生成輸出 IR 時要複製恆定次數，有效地表示將完全展開的恆定行程計數迴圈。這用於支援具有單一模型的多個候選 VF 和 UF 的純量化和預測指令。
- VPRecipeBase:
純虛擬基底類別，對一個或多個輸出 IR 指令的序列進行建模，這些指令可能基於一個或多個輸入 IR 指令。這些輸入 IR 指令稱為配方的「成分」。配方可以指定如何轉換其成分以產生輸出 IR 指令；例如，複製一次、複製多次或根據選定的 VF 加寬。
- VPValue:
VPlan 的定義-使用關係類別階層的基礎。實例化後，它會在 VPlan 中對常數或 live-in 值進行建模。它有使用者，類型為 VPUser，但沒有運算元。
- VPUser:
VPUser 表示將多個 VPValue 用作運算元的實體。VPUser 在某些方面類似於 LLVM 的 User 類別。
- VPDef:
VPDef 表示定義零個、一個或多個 VPValue 的實體。它用於對 VPlan 中的配方可以定義多個 VPValue 的事實進行建模。
- VPInstruction:
VPInstruction 是一種配方，其特徵是單一運算碼和可選標誌，沒有成分或其他元資料。VPInstruction 還使用豐富向量化器語義的慣用運算擴展了 LLVM IR 的運算碼。
- VPTransformState:
儲存用於產生輸出 IR 的資訊，從 LoopVectorizationPlanner 傳遞到其選定的 VPlan 以執行，並用於將額外資訊向下傳遞到 VPBlock 和 VPRecipe。
規劃流程與 VPlan 藍圖¶
將迴圈向量化器轉換為使用 VPlan 遵循分階段方法。首先，VPlan 僅用於記錄最終向量化決策並執行它們：階層式 CFG 對計畫的控制流程進行建模，而配方捕獲基本區塊內採取的決策。目前，VPlan 也用作制定這些決策的基礎，有效地將它們轉變為一系列 VPlan 到 VPlan 的演算法。最後，VPlan 將支援規劃過程本身，包括用於制定這些決策的基於成本的分析，以完全支援組合式和迭代式決策制定。
某些決策是迴圈中指令的本地決策，例如是否將其加寬為向量指令或複製它，並保持產生的指令在原位。然而，其他決策涉及移動指令、用其他指令替換它們，和/或引入新指令。例如，轉換可能會下沉到後續指令之後，並被加寬以處理一階遞迴；交錯的跨步收集或分散群組可能會有效地移動到一個位置，在該位置它們被混洗和常見的寬向量載入或儲存替換；可能會引入新指令來計算遮罩、混洗向量的元素，以及將純量值封裝到向量中或反之亦然。
為了使 VPlan 支援制定指令級決策和分析，它需要對相關指令及其定義/使用關係進行建模。這也遵循分階段方法：首先，計算遮罩的新指令與其誘導的定義/使用子圖一起建模為 VPInstruction。這有效地在 VPlan 中對遮罩進行建模，從而促進基於 VPlan 的預測。接下來，每個配方中用於在 VPlan 執行時產生其指令的邏輯，將透過將它們建模為 VPInstruction 來參與規劃過程。最後，只有適用於指令組的邏輯將保留在配方中，例如交錯群組和可能具有協同成本的其他慣用語群組。