Legalizer

此 pass 轉換通用機器指令，使其成為合法的指令。

合法的指令定義為

• 可選擇的 (selectable) — 目標後續將能夠選擇它，轉換為目標特定的（非通用）指令。這不一定表示 InstructionSelect 必須處理它。這僅表示某些東西必須處理它。

• 操作於可以載入和儲存的 vreg – 如果必要，目標可以選擇每個 gvreg 運算元的 G_LOAD/G_STORE。

與 SelectionDAG 相反，沒有合法化階段。特別是，「類型 (type)」和「操作 (operation)」合法化不是分開的。

合法化是迭代的，並且所有狀態都包含在 GMIR 中。為了保持中間碼的有效性，引入了以下指令

• G_MERGE_VALUES — 將多個相同大小的暫存器串連成單個更寬的暫存器。

• G_UNMERGE_VALUES — 從單個更寬的暫存器中提取多個相同大小的暫存器。

• G_EXTRACT — 從單個更寬的暫存器中提取一個簡單的暫存器（作為連續的位元序列）。

由於它們預期是合法化過程的臨時副產品，因此它們在 Legalizer pass 的末尾被組合起來。如果任何指令仍然存在，它們應始終是可選擇的，必要時使用載入和儲存。

指令的合法性可能僅取決於指令本身，並且不得取決於指令使用的任何上下文。但是，在決定指令不合法後，允許使用指令的上下文來決定如何合法化指令。例如，如果我們有一個 G_FOO 指令的形式如下

%1:_(s32) = G_CONSTANT i32 1
%2:_(s32) = G_FOO %0:_(s32), %1:_(s32)

則不可能說 G_FOO 合法若且唯若 %1 是值為 1 的 G_CONSTANT。但是，以下指令

%2:_(s32) = G_FOO %0:_(s32), i32 1

可以說它是合法的，若且唯若運算元 2 是值為 1 的立即值，因為該資訊完全包含在單個指令中。

API：LegalizerInfo

推薦的 [1] API 看起來像這樣

getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SHL})
    .legalFor({s32, s64, v2s32, v4s32, v2s64})
    .clampScalar(0, s32, s64)
    .widenScalarToNextPow2(0)
    .clampNumElements(0, v2s32, v4s32)
    .clampNumElements(0, v2s64, v2s64)
    .moreElementsToNextPow2(0);

並描述了一組規則，透過這些規則，我們可以宣告指令為合法的，或者決定採取哪些動作使其更合法。

此規則集的核心是 LegalityQuery，它描述了指令。我們使用描述而不是指令，既允許其他 pass 在不必建立指令的情況下確定合法性，也限制了謂詞可依賴的安全資訊。目前，確定合法性的謂詞可用的資訊包含

• 指令的運算碼 (opcode)

• 每個類型索引的類型（請參閱 type0、type1 等）

• 每個 MachineMemOperand 的位元組大小和原子順序

注意

值得研究的替代方案是將 API 泛化為使用 std::function 表示動作，該 std::function 實現了該動作，而不是顯式的枚舉 token（Legal、WidenScalar、…），這些 token 指示它呼叫函數。這會有一些好處，最顯著的是可以移除 Custom。

腳註

[1]

有一個 API 廣泛地類似於 SelectionDAG/TargetLowering，但由於有更強大的 API 可用，因此不建議使用。

規則處理和宣告規則

getActionDefinitionsBuilder 函數為給定的運算碼 (opcode) 生成一個規則集，可以將規則添加到該規則集中。如果給定多個運算碼，它們都將永久綁定到相同的規則集。規則集中的規則從上到下執行，如果指令由於規則而被合法化，則將從頭開始重新執行。如果規則集已耗盡而沒有滿足任何規則，則認為它是不受支援的。

當它不宣告指令為合法時，每次遍歷規則都可能請求將一種類型更改為另一種類型。有時這可能會導致多種類型發生更改，但我們盡可能避免這種情況，因為進行多項更改可能會使避免無限迴圈變得困難，例如，縮小一種類型會導致另一種類型太小，而擴大該類型會導致第一種類型太大。

一般來說，建議盡可能在規則的頂部宣告指令為合法，並將任何昂貴的規則放在盡可能低的位置。這有助於提高效能，因為測試合法性的頻率高於合法化，並且合法化可能需要多次遍歷規則。

作為一個具體的例子，考慮以下規則

getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SHL})
    .legalFor({s32, s64, v2s32, v4s32, v2s64})
    .clampScalar(0, s32, s64)
    .widenScalarToNextPow2(0);

和指令

%2:_(s7) = G_ADD %0:_(s7), %1:_(s7)

這不滿足 .legalFor() 的謂詞，因為 s7 不是列出的類型之一，因此它會落到 .clampScalar()。它確實滿足此規則的謂詞，因為類型小於 s32，並且此規則指示合法化器將類型 0 更改為 s32。然後它從頭開始重新啟動。這次它確實滿足 .legalFor()，結果輸出為

%3:_(s32) = G_ANYEXT %0:_(s7)
%4:_(s32) = G_ANYEXT %1:_(s7)
%5:_(s32) = G_ADD %3:_(s32), %4:_(s32)
%2:_(s7) = G_TRUNC %5:_(s32)

其中 G_ADD 是合法的，而其他指令則排定由合法化器處理。

規則動作

有各種規則工厂將規則附加到規則集，但它們有一些共同的動作

• legalIf()、legalFor() 等。如果滿足謂詞，則宣告指令為合法。

• narrowScalarIf()、narrowScalarFor() 等。如果滿足謂詞，則宣告指令為不合法，並指示將其中一個類型中的純量縮小為特定類型會使其更合法。此動作支援純量和向量。

• widenScalarIf()、widenScalarFor() 等。如果滿足謂詞，則宣告指令為不合法，並指示將其中一個類型中的純量擴大為特定類型會使其更合法。此動作支援純量和向量。

• fewerElementsIf()、fewerElementsFor() 等。如果滿足謂詞，則宣告指令為不合法，並指示將其中一個類型中的向量元素數量減少為特定類型會使其更合法。此動作支援向量。

• moreElementsIf()、moreElementsFor() 等。如果滿足謂詞，則宣告指令為不合法，並指示將其中一個類型中的向量元素數量增加為特定類型會使其更合法。此動作支援向量。

• lowerIf()、lowerFor() 等。如果滿足謂詞，則宣告指令為不合法，並指示將其替換為等效指令會使其更合法。每個運算碼對此動作的支援程度不同。這些可能會提供一個可選的 LegalizeMutation，其中包含嘗試以不同類型執行擴展的類型。

• libcallIf()、libcallFor() 等。如果滿足謂詞，則宣告指令為不合法，並指示將其替換為 libcall 會使其更合法。每個運算碼對此動作的支援程度不同。

• customIf()、customFor() 等。如果滿足謂詞，則宣告指令為不合法，並指示後端開發人員將提供使其更合法的方法。

• unsupportedIf()、unsupportedFor() 等。如果滿足謂詞，則宣告指令為不合法，並指示沒有辦法使其合法，並且編譯器應失敗。

• fallback() 回退到較舊的 API，僅應在從該 API 移植現有程式碼時使用。

規則謂詞

規則工厂也具有共同的謂詞

• legal()、lower() 等始終滿足。

• legalIf()、narrowScalarIf() 等。如果使用者提供的 LegalityPredicate 函數傳回 true，則滿足條件。此謂詞可以存取 LegalityQuery 中的資訊以做出決策。使用者提供的謂詞也可以使用 all(P0, P1, ...) 組合。

• legalFor()、narrowScalarFor() 等。如果類型與給定類型集中的其中一個類型匹配，則滿足條件。例如，.legalFor({s16, s32}) 宣告指令合法，如果類型 0 是 s16 或 s32。通常提供兩個和三個類型索引的附加版本。對於這些版本，所有一起考慮的類型索引都必須與其中一個元組中的所有類型匹配。因此，.legalFor({{s16, s32}, {s32, s64}}) 將僅接受 {s16, s32} 或 {s32, s64}，但不會接受 {s16, s64}。

• legalForTypesWithMemSize()、narrowScalarForTypesWithMemSize() 等。與 legalFor()、narrowScalarFor() 等類似，但還需要 MachineMemOperand 在每個元組中具有給定的大小。

• legalForCartesianProduct()、narrowScalarForCartesianProduct() 等。如果每個類型索引與每個獨立集合中的一個元素匹配，則滿足條件。因此，.legalForCartesianProduct({s16, s32}, {s32, s64}) 將接受 {s16, s32}、{s16, s64}、{s32, s32} 和 {s32, s64}。

複合規則

有一些用於常見情況的複合規則，它們是使用上述設施構建的

• widenScalarToNextPow2() 類似於 widenScalarIf()，但僅在類型大小（以位元為單位）不是 2 的冪時才滿足，並選擇下一個最大的 2 的冪的目標類型。

• minScalar() 類似於 widenScalarIf()，但僅在類型大小（以位元為單位）小於給定的最小值時才滿足，並選擇最小值作為目標類型。同樣，還有一個 maxScalar() 用於最大值，以及一個 clampScalar() 一次執行兩者。

• minScalarSameAs() 類似於 minScalar()，但最小值取自另一個類型索引。

• moreElementsToNextMultiple() 類似於 moreElementsToNextPow2()，但基於 X 的倍數而不是 2 的冪。

最小規則集

GlobalISel 的合法化器在給定目標如何塑造後端其餘部分必須處理的 GMIR 方面具有很大的靈活性。但是，所有目標都必須滿足少量要求。

在討論最低要求之前，我們需要一些術語

生產者類型集 (Producer Type Set)

類型集，它是至少一個合法指令產生的所有可能類型的聯集。

消費者類型集 (Consumer Type Set)

類型集，它是至少一個合法指令消耗的所有可能類型的聯集。

這兩個集合通常相同，但不保證如此。例如，通常無法消耗 s64，但仍然可以為一些特定指令產生它。

純量的最低規則

• G_ANYEXT 對於來自生產者類型集的所有輸入和來自消費者類型集的所有較大輸出都必須是合法的。

• G_TRUNC 對於來自生產者類型集的所有輸入和來自消費者類型集的所有較小輸出都必須是合法的。

G_ANYEXT 和 G_TRUNC 具有強制合法性，因為 GMIR 需要一種連接不同類型大小的操作的方法。它們通常很容易支援，因為 G_ANYEXT 不定義額外位元的值，而 G_TRUNC 則丟棄位元。其他轉換可以降低為 G_ANYEXT/G_TRUNC，並帶有一些額外操作，這些操作會受到進一步的合法化。例如，G_SEXT 可以降低為

%1 = G_ANYEXT %0
%2 = G_CONSTANT ...
%3 = G_SHL %1, %2
%4 = G_ASHR %3, %2

並且 G_CONSTANT/G_SHL/G_ASHR 可以進一步降低為其他操作或目標指令。同樣，G_FPEXT 沒有合法性要求，因為它可以降低為 G_ANYEXT，然後是目標指令。

G_MERGE_VALUES 和 G_UNMERGE_VALUES 沒有合法性要求，因為前者可以降低為 G_ANYEXT 和一些其他可合法化的指令，而後者可以降低為一些可合法化的指令，然後是 G_TRUNC。

向量的最低合法性

在向量類型中，LLVM IR 中沒有定義的轉換，因為向量通常透過重新解釋位元或透過分解向量並將其重構成不同的類型來轉換。因此，G_BITCAST 是唯一需要考慮的操作。我們通常不要求它是合法的，因為它通常可以降低為 COPY（或使用 replaceAllUses() 降為無）。但是，在某些情況下，G_BITCAST 是非平凡的（例如，大端資料的小端向量，例如大端 MIPS MSA 和大端 ARM NEON，請參閱 _i_bitcast）。為了說明這一點，G_BITCAST 對於所有更改值中位元模式的類型組合都必須是合法的。

G_BUILD_VECTOR 或 G_BUILD_VECTOR_TRUNC 沒有合法性要求，因為這些可以透過以下方式處理：* 宣告它們合法。* 將它們純量化。* 將它們降低為 G_TRUNC+G_ANYEXT 和一些可合法化的指令。* 將它們降低為根據定義合法的目標指令。

相同的推理也允許 G_UNMERGE_VALUES 對於向量輸入缺乏合法性要求。

指標的最低合法性

指標沒有最低規則，因為 G_INTTOPTR 和 G_PTRTOINT 可以由合法化器選擇為從暫存器類別到另一個暫存器類別的 COPY。

操作的最低合法性

上面已經註明了 G_ANYEXT、G_MERGE_VALUES、G_BITCAST、G_BUILD_VECTOR、G_BUILD_VECTOR_TRUNC、G_CONCAT_VECTORS、G_UNMERGE_VALUES、G_PTRTOINT 和 G_INTTOPTR 的規則。除了這些之外，以下操作還有要求

• 對於任何指令可以產生的每種類型，G_IMPLICIT_DEF 必須是合法的。

• G_PHI 對於生產者和消費者類型集中的所有類型都必須是合法的。這通常很簡單，因為它不需要選擇任何程式碼。

• 至少一個 G_FRAME_INDEX 必須是合法的

• 至少一個 G_BLOCK_ADDR 必須是合法的

還有許多其他您期望具有合法性要求的操作，但它們可以降低為根據定義合法的目標指令。