向量化計畫¶
摘要¶
向量化轉換可能會相當複雜，涉及多種潛在的替代方案，特別是對於外層迴圈 [1]，但也可能對於最內層迴圈。這些替代方案可能會對效能產生顯著影響，包括正面和負面影響。因此，採用成本模型來識別最佳替代方案，包括完全避免任何轉換的替代方案。
向量化計畫是一個用於描述向量化候選者的明確模型。它既可以用於優化候選者（包括可靠地估計其成本），也可以用於將其最終轉換為 IR。這有助於處理多個向量化候選者。
目前狀態¶
VPlan 目前用於驅動 LoopVectorize 中的程式碼生成。在所有基於成本的決策和大多數與合法性相關的決策都已做出之後，便會建構 VPlan。由於配方之間的定義-使用鏈現在已在 VPlan 中完全建模，因此基於 VPlan 的分析和轉換可用於簡化和模組化向量化過程 [10]。這些轉換包括：
使初始 VPlan 合法化，例如通過為歸約和交錯群組引入專用配方。
優化合法化的 VPlan，例如通過移除冗餘配方或引入活動通道遮罩。
應用展開和向量化因子特定的優化，例如根據 VF 和 UF 移除用於迭代向量迴圈的回邊。
有關當前轉換管道的概述，請參閱 圖 3。
請注意，某些合法性檢查已在 VPlan 中完成，包括檢查固定順序遞迴的所有使用者是否可以重新排序。這被實現為 VPlan 到 VPlan 的轉換，它要么應用有效的重新排序，要么標記 VPlan 為無效並放棄。
圖 3 2024 年的 VPlan 轉換管道¶
VPlan 目前對完整的向量迴圈以及向量化骨架的其他部分進行建模。有關 VPlan 涵蓋範圍的概述，請參閱 圖 4。
圖 4 2024 年 VPlan 中建模的範圍¶
高階設計¶
向量化工作流程¶
基於 VPlan 的向量化涉及三個主要步驟，採用“基於情境的向量化規劃方法”
合法性步驟：檢查迴圈是否可以合法地向量化；如果可以，則編碼約束和偽像。
規劃步驟
根據 Legal Step 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 樹 [5]，其中跨 Tile 的邊緣被提升到連接 Tile，而不是像 Sharir [6] 中那樣連接原始基本區塊，從而提升了 Tile 的封裝性。這裡使用術語「區域」和「區塊」而不是「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 進行建模，這些 VPBasicBlock 和 VPRegionBlock 形成輸出 IR CFG 的 SESE 子圖。VPRegionBlock 可以指示在生成輸出 IR 時，其內容要複制常數次，有效地表示一個循環次數恆定的循環，該循環將被完全展開。這用於支持具有針對多個候選 VF 和 UF 的單一模型的標量化和謂詞化指令。
- VPRecipeBase：
一個純虛擬基類，對一個或多個輸出 IR 指令的序列進行建模，這些指令可能基於一個或多個輸入 IR 指令。這些輸入 IR 指令被稱為 Recipe 的「成分」。Recipe 可以指定如何轉換其成分以生成輸出 IR 指令；例如，根據選定的 VF 複製一次、複制多次或加寬。
- VPValue：
VPlan 定義-使用關係類層次結構的基礎。實例化後，它會對 VPlan 中的常數或活躍值進行建模。它具有使用者，這些使用者的類型為 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 對計劃的控制流程進行建模，而 Recipes 則捕獲在基本塊內做出的決策。目前，VPlan 也被用作做出這些決策的基礎，有效地將它們轉變為一系列 VPlan 到 VPlan 的算法。最後，VPlan 將支持規劃過程本身，包括用於做出這些決策的基於成本的分析，以完全支持組合和迭代決策。
一些決策是針對循環中的指令的局部決策，例如是將其擴展為向量指令還是複製它，並將生成的指令保留在原處。然而，其他決策涉及移動指令、用其他指令替換它們和/或引入新指令。例如，強制轉換可能會沉到後面的指令之後，並被擴展以處理一階遞歸；一組跨步收集或分散的交織組實際上可能會移動到一個位置，在那裡它們被替換為洗牌和一個共同的寬向量加載或存儲；可以引入新的指令來計算掩碼、洗牌向量元素，以及將標量值打包到向量中，反之亦然。
為了讓 VPlan 支持做出指令級決策和分析，它需要對相關指令及其定義/使用關係進行建模。這也遵循分階段的方法：首先，計算掩碼的新指令被建模為 VPInstructions，以及它們誘導的定義/使用子圖。這有效地在 VPlan 中對掩碼進行建模，促進了基於 VPlan 的謂詞。接下來，嵌入在每個 Recipe 中以在 VPlan 執行時生成其指令的邏輯，將通過將它們建模為 VPInstructions 來參與規劃過程。最後，只有適用於指令組的邏輯才會保留在 Recipes 中，例如交織組和可能具有協同成本的其他習慣用法組。